Negative Caching

Caching the answer that something does not exist, so repeated lookups for missing keys stop reaching the database. Covers sentinel entries and their TTLs, DNS and HTTP negative caching, and Bloom filters against cache penetration.

Overview

A cache normally stores things that exist. When a request asks for something that does not exist, a user ID that was never created or a product that was deleted, the cache has nothing to return, so the request goes to the database, which also finds nothing. The next request for the same missing key does the same thing again.

That pattern is called cache penetration: requests pass straight through the cache because the key is never in it. It happens by accident (a mobile app polling for a deleted item, a broken link crawled a thousand times an hour) and on purpose (a scraper or attacker asking for random IDs to hit the database directly).

Negative caching is the fix: store the answer 'not found' in the cache, with a short lifetime, so the next lookup for that key is answered without the database. DNS has required it of resolvers since RFC 2308 in 1998, HTTP caches and CDNs cache 404 responses, and application caches do it with a sentinel value.

What you will be able to do

  • Explain cache penetration and how it differs from a stampede and an avalanche.
  • Store and read negative entries correctly, including clearing them when the key is created.
  • Choose a negative TTL, and explain how DNS derives one from the SOA record.
  • Configure negative caching in an HTTP cache or CDN, and know which status codes are cached.
  • Put a Bloom filter in front of the cache for large key spaces, sized with real numbers.

Key concepts

  • Cache penetration
  • Negative entry (sentinel)
  • Negative TTL
  • Invalidate on create
  • NXDOMAIN and NODATA
  • SOA MINIMUM
  • Caching 404s
  • Bloom filter gate
  • Miss rate limiting

Interview questions

  • What is cache penetration, and how does negative caching help?
  • How do you implement negative caching without hiding newly created records?
  • How does DNS negative caching work?
  • Should a CDN cache 404 responses?
  • When would you add a Bloom filter in front of the cache, and how big is it?
  • Compare cache penetration, cache stampede and cache avalanche.

Sign up free to read the full topic

More System Design topics

Start free on Cariara · Coding problems · System design studio