Rehash pauses breach your p99 budget but memory per instance is capped — how do you choose the mitigation?
answer
- which constraint is actually binding
- every fix spends something else
- one big pause versus many small ones
- two live arrays under a memory cap
- who debugs the clever structure later
basics
~20 sPrice each option against both constraints. Pre-sizing buys zero pauses with permanent memory; incremental rehashing flattens the tail but keeps two arrays live at once; splitting into fixed sub-tables shrinks every pause proportionally and costs almost nothing.
solid answer
~50 sFirst measure how much of the budget the pause consumes and whether growth ever stops — a warm-up transient that ends in ten minutes is an SLO-window question, not an engineering one. If it is real in steady state, I rank by cost of ownership. **Splitting the counters across k fixed sub-tables** is usually the first move: each transfer moves about 1/k of the entries, so pauses shrink by k while becoming k times more frequent, and it needs no custom structure. **Pre-sizing** removes pauses outright, but tables do not shrink, so it spends the memory cap on a peak that may arrive once. **Incremental rehashing** — migrating a few buckets per operation while lookups consult both arrays — genuinely flattens the tail, but holding two arrays throughout is the one thing a hard cap forbids, and someone has to debug it later.
go deeper
Know that growing a hash table costs one slow operation, and that avoiding it generally means asking for more memory up front. You are not expected to weigh the options yet.
Be able to name the mitigations — pre-sizing, splitting into sub-tables, incremental migration, bounding the table — and say what each one costs in memory or complexity.
Show that you measure the pause against the budget before acting, and that you check a mitigation's transient memory peak fits the cap before adopting it.
Own the whole call: which constraint binds, what the team can maintain, whether the budget is contractual, and when the correct answer is to change the SLO window or fix an unbounded key space instead of the structure.
## Frame the decision before choosing a technique The question is not "which mitigation is cleverest" but "which constraint is actually binding, and what does each option spend to relieve it". Three numbers decide it: 1. **How much of the p99 budget the pause consumes.** A 40 ms transfer against a 200 ms budget is a nuisance; against a 10 ms budget it is fatal. 2. **How often growth happens in steady state.** If the key population saturates shortly after start-up, every pause is a warm-up artefact and the correct instrument is the SLO's warm-up exclusion, not the data structure. 3. **How much headroom the memory cap leaves.** This is what disqualifies options, and it is the constraint most engineers forget to price. ## The options and what each spends | Option | Buys | Spends | |---|---|---| | Do nothing, adjust the SLO window | No engineering cost | Only valid when growth is a bounded transient | | Pre-size to expected peak | Pauses removed entirely | Peak-sized memory held forever; needs a trustworthy estimate | | Split into k fixed sub-tables | Pause magnitude divided by k | k times more frequent pauses; slightly worse locality | | Incremental rehashing | Flat tail; no bulk pause at all | Two live arrays throughout migration; real implementation complexity | | Bound the table (expiry/eviction) | Growth stops entirely | Changes semantics — entries can disappear | **Pre-sizing** is the cheapest fix when you have a defensible estimate of the peak entry count. Its hidden cost is permanence: essentially no mainstream table shrinks on its own, so sizing for a peak that occurs during one daily burst means paying that footprint continuously. Under a hard per-instance cap, that alone can rule it out. **Splitting the table** into a fixed number of independent sub-tables, each owning a deterministic slice of the key space, is the most under-used answer. With 16 sub-tables each transfer moves a sixteenth of the entries, so the worst pause is sixteen times shorter. The pauses become more frequent, which is exactly the right trade when the constraint is a *tail percentile* — you are converting rare-and-huge into frequent-and-small, and percentiles reward that. It needs no exotic structure, only a stable index derived from the key, and it composes with pre-sizing. **Incremental rehashing** is the technique that directly attacks the problem: allocate the new array, keep the old one, and on each subsequent operation migrate a bounded number of buckets while lookups check the new array and fall back to the old. No operation ever pays more than a constant. The costs are real and often decisive: both arrays are live for the whole migration, so peak memory rises to roughly the sum of the two — under a hard cap, the mitigation can cause the outage it was meant to prevent. It also complicates every code path that touches the table (lookup, delete, iterate, and any concurrency control), and if you do not own the container implementation you cannot adopt it at all without writing one. **Bounding the table** deserves to be on the list because recurring growth in steady state usually means the key space is unbounded. If the table grows forever, no rehashing strategy saves you — the memory cap is breached eventually regardless. Expiry or eviction turns an unbounded structure into a bounded one, and the resize question evaporates. This is frequently the real answer hiding behind a latency ticket. ## The organisational half Runtimes have made genuinely different calls here, which is worth knowing when the argument turns into "why don't we just do what X does": Java's and Python's standard hash containers transfer the whole table in one step, while Go's map implementation spreads the migration across subsequent operations rather than doing it all at once. That divergence is the tradeoff in this question, decided differently by teams with different constraints — one optimising simplicity and throughput, the other tail behaviour. The decision you own is not only technical: - **Who maintains it.** A hand-rolled incremental table is a permanent tax on every engineer who touches that path, and its bugs are the worst kind: intermittent, load-dependent, and invisible in tests. "Would I be comfortable with this being debugged by someone who has never read this thread" is a legitimate filter. - **What you can actually change.** If the table is a standard container, pre-sizing and splitting are available and incremental rehashing is not without a rewrite. Constraints on what you can adopt are as real as constraints on latency. - **Whether the budget is contractual.** A p99 in a customer-facing contract justifies complexity that an internal dashboard target does not. ## What a strong answer sounds like Measure first; exclude the warm-up transient if that is what it is; reach for splitting and pre-sizing before writing a custom structure; check that the mitigation fits under the memory cap *including its transient peak*; and if growth never stops, fix the unbounded key space instead of the rehash. Naming incremental rehashing and then explaining why you would not ship it here is a stronger answer than proposing it.
- Why can splitting one table into sixteen sub-tables help a p99 without reducing total work?Total re-placement work is unchanged, but its distribution is not. Each transfer touches about a sixteenth of the entries, so the worst single operation is roughly sixteen times faster, while the pauses become sixteen times more frequent. Percentile metrics care about per-operation duration, so trading rare-and-huge for frequent-and-small moves the tail even at constant throughput cost.
- Under a hard memory cap, what disqualifies incremental rehashing?It keeps the old and new arrays live for the entire migration, so peak footprint is roughly their sum for as long as the migration lasts — far longer than a one-shot transfer's brief overlap. A mitigation aimed at latency can therefore trigger the memory exhaustion it was supposed to avoid. Under a tight cap, splitting or bounding the table is safer.
- When is the right answer to change nothing about the data structure?When growth is a bounded warm-up transient. If the distinct-key population saturates minutes after start-up, the table stops resizing on its own and the spikes never recur, so the honest fix is excluding the warm-up window from the SLO. Spending engineering effort and permanent memory on a transient is a worse outcome than the transient.
- The table's key population never stops growing. Does any rehashing strategy fix that?No. Every option here changes when and how the re-placement work is paid, not whether the table keeps expanding. Under a fixed memory cap an unbounded key space runs out of memory whatever the growth policy, so the real work is expiry, eviction, or moving the state out of process. Treating it as a rehash-tuning problem postpones the outage without preventing it.
saying these in an interview costs you the question
- Reaches for a custom structure before measuring the pause
- Prices latency but never prices the memory the fix consumes
- Ignores that incremental rehashing holds two arrays at once
- Treats unbounded key growth as a resize-tuning problem
- Assumes a pre-sized table gives the memory back after the peak