In a lookup service that caches 'not found' results, how should a negative entry be represented and expired?

## What a negative entry is In a cache-fronted lookup service, a request for an ID with no database row normally stores nothing, so every repeat goes back to the database. A **negative entry** (also called a **tombstone** or **null sentinel**) fixes that by caching the fact of absence: "`item:99999` has no row". The next request for the same key becomes a hit that returns not-found without touching the database. The idea is simple. Most of the design work is in three details: how absence is **represented**, which results are allowed to **become** tombstones, and how long they **live**. ## Representing absence unambiguously The reader has to tell three states apart: *present* (a value), *absent* (a tombstone) and *unknown* (a real miss). Many cache clients report a miss as an empty or null result, so the encoding matters. | Encoding | Problem | |---|---| | Empty string or null value | Often indistinguishable from a miss, so the reader queries the database anyway; some serialisers fail on it | | Reserved sentinel string | Works, as long as no legitimate value can ever equal the sentinel | | Typed envelope (`state: present` / `state: absent`) | Clearest; every entry says what it is, and adding states later is easy | Whichever you choose, the read path must check for the sentinel **before** treating the value as a row. A tombstone that leaks into business logic as a real object is a bug that is hard to trace. ## What is allowed to become a tombstone A tombstone asserts that the item does not exist. Only cache that when you actually know it: - **A query that completed and found no row**: cache it. - **A timeout, connection error or overload rejection**: do not cache it. The row may well exist, and caching absence would turn a short database problem into not-found responses for the whole negative TTL. - **A row that exists but is hidden from this caller**: do not store a shared tombstone. Either cache the caller-independent fact and apply permissions after the cache, or include the permission scope in the key. - **Soft-deleted rows**: decide explicitly whether they count as absent for readers, and cache whatever the API would return. ## Choosing the TTL Negative entries normally get a **much shorter TTL** than positive ones: for illustration, 30 to 300 seconds against an hour. Three forces push it down: - **Staleness in the dangerous direction.** If the item is created after the tombstone is written, readers see not-found until the tombstone expires or is replaced. The negative TTL is the worst case when invalidation fails. - **Memory.** A tombstone holds no row, but its key, the sentinel and the cache's per-entry overhead still take space, and absence can be requested for an unbounded number of keys. - **Low value per entry.** A not-found query on an indexed key is usually cheap to repeat, so a long tombstone saves little. Against that, a TTL that is too short stops absorbing repeats. A reasonable target is the shortest TTL that still turns most repeat requests for the same missing key into hits. Measure it: log how soon repeat requests for a missing key arrive, and pick a TTL that covers most of those gaps. If repeats mostly arrive within seconds, a few seconds of absence is enough. ## Keeping the create path honest The TTL is only the backstop. When an item is created, the write path should **overwrite the key with the new value** (or at least delete it) after the database commit, so a tombstone does not hide a real item for the rest of its life. Races between that write and a slow reader need extra care, but the principle is the same: absence is a cached claim, and the code that makes it false must correct it. ## Checklist 1. Encode absence with a sentinel or envelope the reader cannot mistake for a miss. 2. Write it only after a successful query that returned no row. 3. Keep caller-dependent results out of shared tombstones. 4. Give it a TTL far shorter than positive entries. 5. Overwrite or clear it when the item is created. Following these steps turns repeat requests for missing keys into cheap hits without hiding real items for long or letting errors pass as absence.