How Caches Fail

Four ways a cache fails

Four problems arrive once real traffic arrives. Interviewers ask about these because they separate people who have run a cache from people who have read about one.

Stale copies you have already met. Your copy disagrees with the database, and the time limit is how long you have agreed to live with that. Choose it as a product question, not a technical one. A stock count might need thirty seconds. A product description can sit for an hour. An account balance probably should not be cached at all.

Full memory comes next. A cache has a fixed size, so when it fills, something has to go, and the rule for choosing is called an eviction policy. LRU throws out whatever has gone longest without being read, and it is the sensible default because things you just used tend to get used again. LFU throws out whatever is read least often, which suits a catalogue with a stable set of favourites. Note that a time limit is not an eviction policy. It bounds how stale a copy can get and happens to free memory as a side effect, but it makes no choice about what to drop when you are full.

The third one is the dangerous one, because it takes systems down. When a busy key expires, every request that wanted it misses at the same instant and goes to the database together. One query becomes three thousand. This is called a stampede, and the classic version is a homepage that expires at exactly midnight. Let one request rebuild the key while the others wait for it, and add a few random seconds to your time limits so keys written together do not all expire together.

The fourth is the opposite problem. A hot key is one that gets far more traffic than any other, and whichever cache server holds it saturates while the rest sit idle. Splitting your data across more servers does not help, because a single key cannot be split. Copy that one value under several keys and read one at random, or keep it in each server's own memory.

Product getProduct(long id) {
  String key = "product:" + id;
  String copy = redis.get(key);
  if (copy != null) return Product.fromJson(copy);

  // Only one caller wins this and rebuilds. Everyone else waits
  // a moment and reads again, rather than all hitting the database.
  if (redis.setnx(key + ":lock", "1", 10)) {
    try {
      Product p = db.queryOne("SELECT ... WHERE id = ?", id);
      // Random seconds on the end, so keys stored together do not
      // expire together and cause this all over again.
      int ttl = 300 + new Random().nextInt(60);
      redis.setex(key, ttl, p.toJson());
      return p;
    } finally {
      redis.del(key + ":lock");
    }
  }

  Thread.sleep(50);
  return getProduct(id);
}

Worked example

The deploy that emptied Arjun's cache was a stampede in its purest form. Three thousand requests a second, every one a miss, all landing on the database inside the same second.

The rebuild lock changed the next one completely. When a migration flushed the cache again, his database saw about 200 queries a second instead of 3,000, because for each key one request did the work and the rest waited fifty milliseconds and found it waiting for them. His database peaked at 31 percent that time, against 100 the first time.