A matchmaking lobby queue misses its p99 budget on rare enqueues — how do you fix the backing?

## Reading the symptom The report is that a lobby queue meets its latency budget almost always and violates it occasionally. Before touching anything, the shape of the symptom should be checked against the shape of the suspected cause. A growth-driven copy has a distinctive signature: - The mean and p50 are unaffected — the vast majority of enqueues are still a slot write. - The spikes are **proportional to the current size**, so they get bigger as the lobby grows. - The spikes get **rarer as they get bigger**, because doubling means each growth buys twice as much headroom as the last. - Spikes correlate with the queue crossing a capacity boundary, not with arrival rate as such. If instead the spikes are of constant size, or track arrival rate, or appear at random depths, the resize is not the culprit and the investigation should go elsewhere. Naming a falsifiable signature before proposing a fix is most of what makes this a senior answer. ## Why "amortized O(1)" was never a promise about this request Amortized analysis bounds the total cost of a worst-case *sequence* of operations, then divides. It is a genuinely strong statement — stronger than average-case, because it makes no assumption about the input distribution — and it is exactly the right tool for reasoning about throughput. It says nothing about the latency of any individual operation, and a per-request deadline is a statement about individual operations. A structure can be amortized O(1) and still stall one caller for a long time; that is not a contradiction, it is what the word amortized means. This is the specific wrong answer to aim at. "Enqueue is amortized O(1), so it cannot be the source of a latency spike" reverses the direction of the guarantee. ## The fixes, in order of cost **1. Reserve capacity up front.** If the lobby's peak occupancy is known or boundable — and for matchmaking it usually is, because the population is known and there is a plausible ceiling — allocate that capacity once at startup. No growth happens during service, so enqueue becomes O(1) worst case with contiguous layout intact. This is almost always the right first move: it is a one-line change, it keeps every advantage of contiguous backing, and it converts an unpredictable spike into a predictable, one-time startup cost. **2. Bound the queue and reject or shed.** A fixed-capacity ring backing never resizes at all. Enqueue on a full queue then has to do something explicit — reject, apply backpressure, or drop — which is often better behaviour under overload than silently growing without limit. It converts an invisible latency failure into a visible, designed one. **3. Switch to linked backing.** With no buffer, there is no bulk copy, so no enqueue can stall proportionally to the queue's size. This is the answer when the peak is genuinely unbounded. It is not free: two to three times the memory for small entries, an allocation per enqueue, and worse locality when the queue is scanned. Those costs are steady and predictable, which is the trade being made — the whole point is exchanging a rare huge cost for a small constant one. **4. Do nothing, deliberately.** If the copy costs less than the budget even at peak size, the right call is to document the reasoning and move on. A senior answer includes the option of not spending. ## Defending the choice to a skeptic The pushback to expect is "linked backing is slower, everyone knows contiguous is faster" — and on throughput the skeptic is right. The defence is not that linked backing is faster; it is that the two options are optimising different objectives. Contiguous backing minimises total work; the requirement here is a bound on the worst single request. Under a per-request deadline, a structure whose worst case is a small constant beats one whose average is smaller but whose worst case scales with occupancy. The way to settle it is to state the objective explicitly, then measure the objective: p99 and p99.9 enqueue latency at realistic peak occupancy, not throughput and not the mean. And the strongest version of the answer notes that if the peak really is boundable, option 1 wins the argument outright — it gives the skeptic the contiguous layout they want *and* removes the spike, which is why it should be proposed before the more contentious swap. ## What to avoid saying Growing by a larger factor does not fix this. It makes the spikes rarer and each one larger, which under a tail-latency budget is either neutral or worse. Neither does moving the work to a background path unless the queue's contract genuinely allows it. And reporting the mean instead of the tail is measuring around the problem rather than solving it.