Thursday, 12 November 2015

The Problem with Caching

Fig 1. Stampeding Elephants.
We cache things to avoid unnecessary load on our servers. It might therefore surprise you to learn that when you are most vulnerable, the kind of shared memory cache that is APC(u) will stab you in the face ...

APC(u) has had stampede protection for a long time, however, it is perniciously named, and ineffective when it is most needed.

You are most vulnerable to high load when the cache is empty,  because the work you were trying to avoid executing unnecessarily by caching it's result, must execute.

The problem is that the expensive-work-worth-avoiding is going to be executed in more than one process; It will be executed by however many processes you are using that are able to spin up in the time it takes the first process to warm the cache.

If you have large pools of processes, or generation of the entry is expensive, this becomes a very real problem.

The stampede protection built into APC(u) only stops a stampede of the cache, it doesn't stop the stampede, or competition, for CPU time while dozens, possibly hundreds, of processes are attempting to execute the very same code paths, only to fail to store the data, because the current stampede protection will prohibit the write, for most of the processes anyway.

What not to do ...

The most obvious, but most dangerous solution would be to expose a lock and unlock function to userland PHP.

If some process calls lock, and before it gets to call unlock, experiences an uncaught exception, or some other fatal error, it will deadlock the server.

Since so much can result in that kind of fatal error, it doesn't seem worth the risk, considering the price of failure is catastrophic deadlock.

The Solution

APCu >= 5.1.0 (PHP7+) will have the following function:

function apcu_entry(string key, callable generator, int ttl = 0);

If the entry identified by key cannot be found (or is invalidated by the ttl it was stored with), generator is called and the result stored with the optionally specified ttl.

All of this is done while an exclusive lock is held on the cache; This means that if many processes hit the same code path, only one of them will carry out generation.

Used correctly this allows truly atomic cache warming to take place, like so:
$config = apcu_entry("config", function($key){
 return [
  "child" => apcu_entry("config.child", function($key) {
   return "Hello World";
  "next" => apcu_entry("", function($key) {
   return "We've only just begun ...";
  /* ... */

Recursion is only natively supported when rwlocks are disabled (--disable-apcu-rwlocks)  at build time, it is otherwise supported with a thread local counter.

This requires much testing, consider this a call for testers ...