Amortized O(1) append still misses a 2 ms deadline on a sensor ingestion buffer — why?

## Two different questions, one number "How much does a thousand appends cost?" and "how long can *this* append take?" are different questions, and an amortized bound answers only the first. Amortized `O(1)` says: for any sequence of n appends, total work is `O(n)`. It is a guarantee about a whole run, and it is a strong one — it holds against an adversary choosing the operations, with no assumption about input distributions. What it deliberately does not do is bound any individual call. Inside that linear total sits one append that copied every element in the buffer, at cost `Theta(n)`. A hard per-append deadline is a contract of the second kind. If each reading must be accepted within 2 ms, the relevant number is the worst-case cost of one append, which for a growth-doubling buffer is linear in the current size. Once the buffer holds enough readings that copying them exceeds 2 ms, the deadline is missed on every resize, forever. No amount of good average behaviour repairs this, because the average was never the thing being promised. ## The signature of the failure Resize pauses are unusually easy to identify because they are structured, not random: - **They recur at exponentially spaced append counts.** With doubling, growths land at counts 1, 2, 4, 8, ..., so the pauses get further apart as the run continues. An engineer who expects a periodic problem (every N appends, every N seconds) will not see the pattern until they plot latency against append index rather than against wall-clock time. - **Each pause lasts about twice as long as the previous one**, because the buffer being copied has doubled. The worst observed pause is therefore a moving target that grows with the run, which is why a load test that stops early looks clean. - **The latency distribution is bimodal**, not skewed: a very tight fast mode (a store and an increment) and a distant slow mode (allocate plus a linear copy), with nothing in between. Skewed-but-continuous tails usually indicate contention or scheduling; a clean second mode whose position drifts with data volume points at rebuild work. - **Pause duration scales linearly with the current element count.** That correlation is the confirming measurement: log the buffer size alongside the slow appends and check that the ratio is roughly constant. ## What actually fixes it The amortized bound cannot be improved by tuning, because it is already optimal for the total; what has to change is the *worst case of a single operation*. **Reserve up front.** If the workload has a known ceiling — a fixed sampling rate times a fixed window gives a computable maximum number of readings — allocate that capacity before the hot path begins. No resize fires, so no append copies anything. This is the cheapest fix and the most common one, but be honest about its limit: it removes the cliff only while the count stays under the reservation. The first append past it still copies everything, so an estimate you might exceed has moved the problem rather than solved it. **Stop copying on growth.** A layout that stores elements in a chain of fixed-size blocks grows by allocating one more block and linking it, never touching the elements already stored. Worst-case append becomes constant. The price is that the elements no longer occupy one contiguous run, which costs you the locality and the constant-time-by-arithmetic indexing that made the flat buffer attractive. **Spread the copy out.** Incremental rebuilding keeps the old and new blocks alive at once and moves a few elements per append until the migration completes, so no single call does linear work. This converts the amortized bound into a worst-case one at the cost of extra memory during the transition and a genuinely more complicated structure to maintain — which is a real cost when the team on call is not the team that wrote it. **Take the work off the critical path.** If the deadline belongs only to the acquisition thread, hand readings to a fixed-capacity staging area with a bounded worst case and let a separate stage absorb the variable-cost work. Now the deadline is protected by a queue with an explicit overflow policy, and the design question becomes what to do when the staging area is full — which is a question you can answer in advance, unlike a latency spike you did not know about. ## How to state the guarantee afterwards The durable lesson is about which bound gets written down. Throughput-oriented consumers should be promised amortized cost, because that is what governs the total. Deadline-oriented consumers must be promised a worst-case per-operation cost, and if the structure cannot offer one, that must be surfaced as a design constraint rather than buried under an average. Quoting an amortized figure into a latency contract is the mistake this whole scenario is built out of, and it is the mistake worth naming explicitly in a review.