Negative caching
Negative caching stores the answer not found for a key. If 99 percent of lookups ask for IDs that do not exist, a normal cache passes all of them to the database. A negative entry answers them in 0.1 ms.
See it on the board
The same traffic runs on two boards. The simulator measured both when this page was built.
| Measure | Goal | Missing IDs reach the database | Not found is cached |
|---|---|---|---|
| p99 latency | under 150 ms | 10.1 s Fail | 23 ms Pass |
| CPU use | under 70% | 990.9% Fail | 20% Pass |
| Monthly cost | 8 USD/mo | 8 USD/mo | |
| Error rate | 92.8% | 0% |
Key numbers
| Number | Value |
|---|---|
| Cache read, median | 0.1 ms |
| Database read, median | 0.5 ms |
| Reads per second, one cache | 100,000 ops/s |
With not-found entries · 1 of 100 lookups reach the database
How it works
A normal cache stores only values that it found. A lookup for an ID that does not exist finds nothing, so nothing is stored. The next lookup for the same ID goes to the database again. A crawler or a bug can send thousands of such lookups each second, and the cache does not help.
A negative entry stores the result not found, with a time to live. The next lookup for that ID hits the cache and returns not found at once. In the mini board 99 percent of lookups ask for missing IDs. Without negative entries, p99 passes 10 s and 93 percent of requests fail. With them, almost all lookups stop at the cache.
Keep the time to live short. If the item is created later, readers still get not found until the entry expires. You can also remove the negative entry when a write creates the key.
A Bloom filter is a second option. It is a small summary of all IDs that exist. A no from the filter is always right, and the lookup skips the database. A yes can be wrong, so that lookup still reads the database. The filter needs less memory than one entry for each missing ID.
In the levels you stop reads for missing keys before they reach the source.