Support graceful caching

Our current cache system is mostly a key-value store. A cache entry has an explicit expiry time, and some unspecified period after the expire time the entry will be garbage-collected.

This very simple system has some drawbacks. When a cache entry is garbage-collected or is manually cleared, it causes a “thundering herd” of n threads to all start generating the cache in parallel. This can be mitigated by wrapping the cache generation in a semaphore, but the n-1 threads then have to wait for the cache to be generated rather than just using the stale entry (of course it doesn't always make sense to use the old one, but often it does).

I suggest that we extend the caching system, either by extending the responsibilities of the individual cache backends or by adding a wrapper layer around them, to allow stale entries to be returned for a specified period of time, and to help the developer avoid thundering herd problems.

cache_get() currently takes just a $cid argument. This could be extended with an $options argument:

• allow_stale (integer): If the current cache entry is stale, return the old one for this period of time (in seconds). If this is not specified, a stale entry is never returned (this is different from today).
• acquire_lock (boolean, default is FALSE): If no cache entry exists, or the current cache entry is stale, then try to acquire a lock for the specific $cid (e.g. lock_acquire('cache_get:' . $bin . ':' . $cid)). If the lock was successfully acquired, return an empty result, otherwise return a stale result if it is not older than allowed by allow_stale. When this argument is specified, the caller promises to fill the cache for the specified $cid and release the lock.
• wait_for_cache (integer): If no cache entry exists, or the current cache entry is stale and older than allowed by allow_stale, and another thread currently holds a lock for generating this cache, then wait for up to this period of time (in seconds) for the other thread to finish.
• callback (string): If specified, instead of returning an empty cache entry, call this function with the arguments specified by callback_arguments. The return value is stored in the cache and returned to the user.
• callback_arguments (array): See above.
• ensure_result (boolean, default is TRUE): If FALSE, return empty rather than calling the callback, if another thread holds the lock for regenerating the cache.

The object return by cache_get() should reflect the various values in use.

cache_set() currently takes a $cid, a $value argument, and an $expire time. This could be extended (or $expire could be replaced) with an $options argument:

• garbage_collect (int): A Unix timestamp (later than the expiry time) specifiying the earliest time the entry should garbage-collected under optimal conditions. This is no guarantee that the entry will exist for that long (e.g. the cache backend may decide to garbage-collect it anyway, if memory is low), but should be considered a hint from the setter that the object may be considered somewhat relevant for that long. E.g. if regenerating a cache entry takes very long, it may be reasonable to keep the stale entry for a long time.
• release_lock (bool): Release the lock previously acquired by specifying get_lock for cache_get().

Finally, cache_clear_all() should have a way of marking a cache entry as stale without removing it from the cache.

I'm not quite sure about the different TTL's (the “soft” one, indicating that a cache entry is stale, and the “hard” one, indicating that the entry is completely flushed from the cache), and whether it is best to supply these for cache_get() or for cache_set().

A slightly different approach than the above is to use the specified $expiry as the “soft” expire, and allow cache_get() to receive stale data for up to $expire + .1 * $ttl (with $ttl being $expire - time() when cache_set() was called), i.e. as if 'allow_stale' defaults to .1 * $ttl, until the entry is flushed. Perhaps the entry could be kept around for even longer, e.g. $expire + 10 * $ttl, i.e. allowing that a caller of cache_get() to get the entry, if he explicitly sends a high allow_stale value. These values are defaults that of course should be overrideable.

Today, if a cache_set() is called with an $expire time other that CACHE_PERMANENT and CACHE_TEMPORARY, it is usually doesn't mean that the cache is known to expire exactly at the specified time, so assuming that the entry may still be relevant (but theoretically stale) for another 10% of the TTL (the .1 factor mentioned earlier) should be a reasonable default.

In practice there is usually a big difference between a cache entry that is stale, because the expiry time has passed, and one that is stale because it has been marked as such using cache_clear_all()

This issue is the product of discussions with gielfeldt and is inspired by his Cache Graceful module: http://drupal.org/project/cache_graceful