Cache validators versus cache invalidation

April 16, 2011

There are two general ways of handling out of date cache entries: cache invalidation, where you explicitly mark them invalid or remove them, and having validators, so that you check to see whether an entry is valid as you retrieve it from the cache.

Cache invalidation has a number of advantages. First, it's clearly superior to validators if you're running into the size limits of your cache, because it immediately frees up now-dead entries instead of leaving them around to steal space from the live entries that are actually useful. It's also probably more resource efficient, since it handles invalidation once (on write) instead of checking every time on reads. In most situations, cache entries are read more than they're written, ideally a lot more times; otherwise you're probably wasting cache space.

Validators have two potentially significant advantages, however. First, a validator only requires you to track what components got used when you build a page (or fragment, or etc). This is a far easier problem than knowing everywhere that depends on a particular component (so that the component can invalidate the cached versions of everyone who uses it when it changes), partly because you naturally discover this information in the progress of building a page or fragment.

The second is kind of an anti-requirement; with cache invalidation you have to be able to take immediate positive action on changes. If changes can happen behind your back, outside of your system, this doesn't work too well. Validators cope with this situation.

(To borrow from something I read via Hacker News recently, cache invalidation is edge triggered while validators are level triggered. Edge triggered systems require you to catch every edge transition and bad things happen if you can't.)

PS: since DWiki is file-based, almost everything happens behind its back and so it has to use validators for its cache.

(This is a secondary reason why requiring an explicit publication step is on my list of things I would do differently in a new file based blog.)

Written on 16 April 2011.
« Why a dynamic website with caching is simpler than a baked site
The ultimate (for now) answer for our ZFS ARC size problem »

Page tools: View Source, Add Comment.
Search:
Login: Password:
Atom Syndication: Recent Comments.

Last modified: Sat Apr 16 01:22:18 2011
This dinky wiki is brought to you by the Insane Hackers Guild, Python sub-branch.