Why does a log-ingest service see p99 append spikes even though appends are amortized O(1)?

## The observation A log-ingest service appends event records to a growable in-memory buffer between flushes. Mean append latency is flat and boring. But a p99 alert fires a handful of times per flush cycle, and someone notices the spikes land at particular buffer sizes. The first instinct — "the append path is amortized O(1), so this must be the network or garbage collection" — is the wrong answer this scenario exists to catch. ## What amortized actually claims Amortized O(1) says: for any sequence of n appends, the *total* cost is O(n), so the cost per append averaged over the sequence is bounded by a constant. It is a guarantee about the aggregate. It explicitly permits individual operations to be arbitrarily expensive, as long as expensive ones are rare enough and the cheap ones make up for them. Two things it is not: - It is **not** worst-case per operation. A structure with worst-case O(1) append never stalls; a structure with amortized O(1) append stalls on schedule. - It is **not** an average over random inputs. Nothing here depends on the input distribution; the expensive appends are determined entirely by where the capacity boundaries fall. A percentile metric measures individual operations. So a metric that reports the 99th percentile is measuring precisely the thing the amortized bound declined to bound. ## Why the spikes are shaped the way they are Under a multiplicative growth rule the capacity boundaries are geometrically spaced. That gives the spike pattern a very recognisable signature: - **They get rarer.** The interval between growths grows by the same factor each time, so the number of cheap appends between stalls keeps multiplying. - **They get bigger.** Each growth copies the whole current prefix, so the k-th stall copies roughly a factor more elements than the (k-1)-th. - **The product is constant.** Rarity and size cancel, which is precisely why the amortized bound holds while the tail keeps stretching. So the latency histogram does not degrade smoothly. Mean and median do not move. p99 steps up at particular sizes, and p99.9 or p99.99 — where the biggest, rarest copies live — steps up hardest. A buffer holding tens of millions of records with references several bytes wide is copying hundreds of megabytes in one call; that is milliseconds even at full memory bandwidth, and worse if the new block is large enough that the allocator requests fresh pages from the operating system and the copy faults each one in. ## Confirming it rather than guessing The diagnosis is cheap because the pattern is so specific: 1. **Correlate spikes with buffer size, not with wall-clock time or request rate.** If the stalls land at reproducible element counts and those counts sit in a geometric progression, growth is the cause. Load unrelated to buffer size — collection pauses, network retries, contention — does not line up that way. 2. **Check the spacing.** Growth stalls double their separation. Almost nothing else in a service has that signature. 3. **Check the magnitude against arithmetic.** Estimate elements copied times bytes per element divided by achievable memory bandwidth. If the spike duration matches the estimate, you are done. 4. **Test the hypothesis directly.** Pre-size the buffer to the expected final count and re-run. If the spikes vanish, the cause is confirmed and you have most of the fix. ## Fixing it, in increasing order of commitment **Pre-size from a known upper bound.** If yesterday's peak was 40 million events, reserve capacity for that before the run starts. One allocation and one copy-free run. This is the cheapest fix by far and usually the right one. Its weakness is honest: it is an estimate, and an estimate that is 10x low simply reintroduces the growth stalls after the reserve is exhausted (though with fewer, later spikes than starting from nothing). Treat the reserve as an optimisation, never as a bound. **Bound the buffer and flush.** Cap the buffer at a fixed number of records and flush when it fills. Capacity never grows, so no copy ever happens, and the tail is governed by the flush rather than by memory movement. This also gives you a memory ceiling, which the growable buffer never had. **Change the layout.** Store records in a sequence of fixed-size blocks rather than one contiguous run. Adding a block is O(1) and copies nothing, so the worst-case append is genuinely constant. You give up perfectly contiguous storage, which costs a little on scans and on anything that wants the whole run as one region. **Migrate incrementally.** Keep both the old and the new block live after a growth and copy a few elements per subsequent append until the migration completes. This turns the amortized bound into a worst-case one at the cost of extra memory during the migration and a considerably more complicated structure — worth it for hard real-time budgets, rarely worth it otherwise. ## The one-line version Amortized O(1) is a promise about the bill at the end of the month, not about the price of any single item. Percentile alerts read the individual prices.