Preventing the Dogpile Effect

Dogpile effect - theory (problem and solution)

Implementing caching in web apps seems to be simple. You check if value is cached. If it is, you fetch cached value from cache and serve it. If it’s not, you generate new value and store in cache for future requests. Simple like that.

However, what if value expires and then you get hundreds of requests? It cannot be served from cache anymore, so your databases are hit with numerous processes trying to re-generate the value. And the more requests databases receive, the slower and less responsive they get. Load spikes. Until eventually they likely go down.

See picture below (green - in cache, red - no cache).

Preventing the dogpile effect boils down to having just one process (first one to come) regenerating new value while other subsequent processes serving stale value from cache until it’s refereshed by the first process.

Worried about serving stale data? Well, if your databases are overloaded and suffering, serving stale data is the smallest inconvenience you can have. And if takes long to regenerate new value, having multiple processes doing this (instead of one) won’t help really. It will just add more load.

Dogpile effect - prevention/implementation

Dogpile effect can be prevented using semaphore lock. If value expires, first process acquires a lock and starts generating new value. All the subsequent requests check if lock is acquired and serve stale content. After new value is generated, lock is released.

Important to note is that in fact values should be given an extended life time, so they’re not physically removed when they expire and they can be still served if there’s a need.

Here’s how it works in detail.

Get cache value from cache store.

$value = $this->store->get($key);

$value is a value object.

Check whether cached value expired or not. If not expired, serve it.

if ($value && !$value->isStale()) {
	return $value->getResult();
}

Otherwise, acquire lock so there’s just one process regenerating new value.

$lock_acquired = $this->acquireLock($key, $grace_ttl);

If lock cannot be acquired, it means there’s already other process regenerating it, so let’s just serve current (stale) value.

if (!$lock_acquired) {
	return $value->getResult();
}

Otherwise (lock has been acquired), regenerate new value.

$result = ...

Save regenerated value in cache store. Add grace period, so stale result might be served if needed by other processes.

$expiration_timestamp = time() + $ttl;
$value = new Value($result, $expiration_timestamp);

$real_ttl = $ttl + $grace_ttl;
$this->store->set($key, $value, $real_ttl);

Release lock.

$this->releaseLock($key);

Full implementation: https://github.com/sobstel/metaphore/blob/master/src/Cache.php.

Metaphore

Metaphore is open-sourced library to prevent dogpile effect in PHP apps. It’s actually rewrite of LSDCache, which has been successfully used in many high-traffic production web apps. I just believe that LSDCache has grown too big into multi-purpose cache library while metaphore strives to be simple to do just one thing and to do it well.

Usage is really simple.

In composer.json file:

"require": {
	"sobstel/metaphore": "dev-master"
}

In your PHP file:

use Metaphore\Cache;

// initialize $memcached object (new Memcached())

$cache = new Cache($memcached);
$cache->cache($key, function(){
    // generate content
}, $ttl);

Thanks

Thanks to Mariusz Gil for his talk about Memcached back in 2010 at PHPCon - which made me aware of dogpile effect issue - and for allowing me to use pics from slides.

by sobstel • July 2014

Preventing the Dogpile Effect

Dogpile effect - theory (problem and solution)

Dogpile effect - prevention/implementation

Metaphore

More reading

Thanks