Why does an open-addressed cache with a flat entry count show p95 lookup latency climbing over days?

## The workload that produces this shape A payments order cache: each order is inserted when it arrives, read a handful of times while it is in flight, then deleted when it settles. Inserts and deletes run at roughly equal rates, so the number of live entries hovers around a fixed value and every capacity dashboard looks calm. Over days, p95 lookup latency drifts upward with no deploy, no traffic change and no growth in stored entries. ## The mechanism In an open-addressed table, deletion cannot free the slot — clearing it would cut the probe path for any key that collided with the deleted one. So delete writes a **tombstone**: a marker meaning "occupied once, keep probing". The arithmetic that follows is unforgiving: - Insert of a new key on a path with no tombstone consumes one EMPTY slot. - Delete turns OCCUPIED into DELETED: non-empty count unchanged. - Reuse of a tombstone turns DELETED back into OCCUPIED: non-empty count unchanged. So **the number of non-empty slots only ever grows**, no matter how balanced the insert/delete rates are. Tombstone reuse helps, but only opportunistically — it recycles a tombstone only when some future key's probe path happens to cross it. Under churn with a wide key space, most tombstones lie on paths nothing revisits. Probe length is governed by the non-empty fraction, because a step over a tombstone costs the same slot read and state test as a step over a live entry. At 20% live occupancy but 90% non-empty occupancy, the table performs like a table that is 90% full. ## Why misses degrade first A successful lookup terminates the instant it matches its key, frequently within one or two probes. An unsuccessful lookup has no early exit: it must reach the first EMPTY slot to conclude the key is absent. As EMPTY slots grow scarce, miss cost rises far faster than hit cost. This is diagnostic gold — split your latency metric by hit and miss, and a widening gap points straight at the dead space rather than at anything upstream. ## Confirming it rather than guessing Latency drifting with flat volume invites the usual suspects — garbage collection, a noisy neighbour, a slow downstream call — and teams burn days there. Two measurements settle it quickly: 1. **Occupancy split**: live entries, tombstones and empty slots as fractions of capacity. Live at 0.3 with non-empty at 0.85 is conclusive. 2. **Probe-length histogram**: average and p99 probes per operation, ideally separated by hit and miss. A mean drifting from 1.4 to 9 over a week is the same story told in the units that matter. Both are cheap counters. Their absence is the actual root cause of most long investigations here — the table's internal state was never observable. ## The fix **Change what the load-factor test counts.** Compare non-empty slots to capacity, not live entries to capacity. That single change makes this table trip its rebuild threshold in hours rather than never. **Rebuild by reinserting live entries only.** Allocate a fresh slot array, walk the old one, and re-insert every OCCUPIED entry by probing it into the new array from its home slot. Tombstones are simply not carried across — they were only ever a repair for the *old* layout's probe paths, and the new layout's paths are built correctly from scratch. Cleanup is therefore free: it is not a separate compaction pass, it is a property of rebuilding. **Capacity is a separate decision from cleanup.** Because the live count never grew, the rebuild can legitimately target the same capacity — the goal is to compact, not to grow. Rebuilding into a larger array when only tombstones were the problem wastes memory permanently and postpones rather than solves the next occurrence. ## Operating it A rebuild is a bulk operation, so on a latency-sensitive path it has to be scheduled rather than triggered blindly at p99 time: run it on a maintenance tick, at a low-traffic window, or migrate a fixed number of slots per operation into the new array while reads consult both. Where the workload's deletes are extreme and pauses are unacceptable at all, the deeper answer may be that the structure is wrong for the workload rather than that the threshold is wrong. ## What interviewers listen for The tell is whether the candidate distinguishes *live size* from *space consumed*. Almost everyone knows tombstones exist; the senior signal is saying "the size metric is flat because size is the wrong metric — show me the non-empty fraction", naming misses as the first casualty, and then choosing to compact at the same capacity rather than reflexively doubling.