skip to content

In an item-lookup API that caches not-found results, why might a newly created item keep returning 404 for minutes, and how do you fix it?

level: seniorimportance: should knowfreq 42%

answer

  1. Absence that became false
  2. Create path forgets the cache
  3. Slow reader writes last
  4. Replica had no row yet
  5. Occupy the slot, conditional tombstone

basics

~20 s

A tombstone written before the item existed is still live: the create path never replaced it, or a slow reader wrote it after the create's invalidation. Overwrite the key on create, write tombstones conditionally, and keep the negative TTL short.

solid answer

~40 s

The stale 404 is a **tombstone that outlived the item's absence**. There are two usual causes. First, the create path never touches the cache, so the tombstone lives out its TTL. Second, a **race**: a reader misses the database just before the create commits, the create deletes the key, and the reader then writes its now-false tombstone. Replica lag widens that window when the reader queried a replica that had not yet received the row. The fixes stack: after commit, the create path **writes the new value** into the key instead of only deleting it; readers write tombstones with **set-if-absent**, so they cannot replace a real value; the **negative TTL** bounds whatever still slips through; and when another service creates the item, an event or change feed triggers the overwrite.

code

pseudocode · 16 lines
pseudocode
function readItem(id):
    v = cache.get(key(id))
    if v == ABSENT:
        return NOT_FOUND
    if v != MISS:
        return v
    row = db.findById(id)
    if row == NONE:
        cache.setIfAbsent(key(id), ABSENT, ttl = 60s)   // fails if a value is already there
        return NOT_FOUND
    cache.set(key(id), row, ttl = 3600s)
    return row

function createItem(item):
    db.insert(item)                                    // commit first
    cache.set(key(item.id), item, ttl = 3600s)         // replaces any tombstone, occupies the slot

go deeper

for a junior

Remember that a cached 'not found' can outlive the moment an item is created, so the code that creates items has to update the cache too.

for a middle

Explain the late-writer interleaving step by step and why the negative TTL sets the worst-case delay before a new item appears.

for a senior

Diagnose the stale 404 from its timing, and combine overwrite-on-create, conditional tombstone writes and replica-aware misses into a fix you can justify.

for a principal

Weigh how much consistency machinery negative caching deserves across services, including event-driven invalidation, against simply keeping the negative TTL short.

## The symptom An item-lookup API caches not-found results as **tombstones** (negative entries) so that repeated requests for missing IDs stop reaching the database. A user creates an item, gets its ID back, opens the link, and receives **404 Not Found**. The row is committed and a direct database query finds it, yet the API keeps returning 404 for minutes, then suddenly starts working. That delay is almost always the length of the negative TTL, and it means a tombstone for that key was live after the item existed. ## Cause 1: nobody replaces the tombstone The simplest cause is that the create path writes the database and never touches the cache. If anything asked for the ID before it existed (a client polling for the new item, a retry, a link generated ahead of time), a tombstone sits in the key. Positive-entry invalidation is often wired only into update and delete paths, because a new item "has nothing to invalidate". With negative caching that assumption is wrong. ## Cause 2: the late-writer race Even when the create path deletes the key, a reader can put the tombstone back: 1. Reader R misses the cache for `item:77` and queries the database. No row yet. 2. Writer W commits the insert of item 77. 3. W deletes `item:77` from the cache. The slot is empty. 4. R, which was slow (a pause, a slow network, a busy thread), now writes its tombstone for `item:77`. 5. Every reader sees 404 until the tombstone expires. This is the same interleaving that can leave a stale positive value after an update, applied to absence. It is easy to miss in tests because the window is short, but a busy API hits it regularly. ## Why replica lag makes it worse If readers query a **read replica**, step 1 can happen *after* the commit: the replica simply has not received the row yet. The window is then as long as the replication lag, not just the gap between a query and a cache write. A reader that got "no row" from a replica is making a much weaker claim than one that asked the primary. ## Fixes that close the window | Fix | What it closes | Cost | |---|---|---| | Create path writes the new value after commit | Cause 1, and most of cause 2 when combined with the next row | One extra cache write per create | | Readers write tombstones with set-if-absent | A late tombstone can no longer replace a real value | Needs a conditional write in the cache | | Short negative TTL | Bounds any stale tombstone that still slips through | More repeat database misses | | Delayed second delete after create | Removes a tombstone written by a late reader | The delay is a guess | | Confirm absence on the primary before caching it | Replica-lag variant | Extra primary load on misses | | Create event or change feed triggers the overwrite | Creates made by other services | Asynchronous, so the TTL still bounds the gap | The first two rows work as a pair. If the create **writes** the value, the slot is occupied, and the late reader's conditional write fails. If the create only **deletes**, the slot is empty and the conditional write succeeds, so deleting alone does not close the race. One gap remains: the new value could be evicted between the create's write and the late tombstone write. That is rare, and the negative TTL bounds it. ## Choosing the combination - Always make the create path aware of the cache. This is the cheap, essential fix. - Add conditional tombstone writes where the cache supports them. It costs almost nothing. - Set the negative TTL from the staleness a new user will tolerate. For illustration, a 60-second TTL means a residual stale 404 lasts at most 60 seconds. - If readers use replicas, either skip tombstone writes for IDs newer than the lag window or confirm absence on the primary. - If items are created elsewhere, subscribe to their creation and treat it like a local create. No single fix removes every interleaving. Together they make the stale window rare and short, and the TTL keeps the worst case known.

  • Why is deleting the key on create weaker than writing the new value?
    A delete leaves the slot empty, so a reader that queried the database before the commit can still write its tombstone afterwards, and a set-if-absent write succeeds. Writing the value fills the slot, so that late conditional write fails. The remaining gap, the value being evicted in between, is rare and bounded by the negative TTL.
  • How do you handle this when a different service creates the items?
    The creating service should not need to know the reader's cache keys. Publish a 'created' event or consume the database's change feed, and have the service that owns the cache overwrite the key when it arrives. Delivery is asynchronous, so the negative TTL still bounds the gap. Keep it shorter than the delay users will accept.
  • Would a delayed second delete help instead of conditional writes?
    Partly. Delete right after commit and again after a delay longer than a typical read, which removes a tombstone written by a late reader. It narrows the window without needing conditional writes, but the delay is a guess: a reader slower than the delay still leaves a stale tombstone until its TTL runs out.

saying these in an interview costs you the question

  • Deleting the key on create always prevents a stale tombstone
  • The database must be at fault because the row is committed
  • A long negative TTL is harmless once the create path deletes the key
  • Reading from a replica cannot affect what gets cached as absent
  • New items have nothing cached, so creates never need invalidation