Wandering Thoughts archives

2011-04-16

Cache validators versus cache invalidation

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.)

programming/CacheValidatorsVsInvalidation written at 01:22:18; Add Comment


Page tools: See As Normal.
Search:
Login: Password:
Atom Syndication: Recent Pages, Recent Comments.

This dinky wiki is brought to you by the Insane Hackers Guild, Python sub-branch.