Monoid-Augmented FIFOs, Deamortised

Summary

Nothing novel, just a different presentation for a decade-old data structure. I want to nail the presentation because this data structure is useful in many situations. Augmented FIFOs come up frequently in streaming analytics. For example, to compute the sum of the last \(k\) values observed in a stream (or more generally, in the turnstile model), we can increment an accumulator by each value as it’s pushed onto the FIFO, and decrement the accumulator by the exiting value (increment by the value’s additive inverse) when it’s popped off the FIFO. This simple increment/decrement algorithm works because the underlying algebraic structure is a group (addition is associative, and we have additive inverses). However, that can be too strong of an assumption: a lot of times, we want windowed aggregates over operators that are associative but lack inverses. For a toy example, a service could summarise its tail latencies by tracking the two longest (top-K with \(k=2\)) request durations over a sliding 1-second time window. Let’s say there was no request in the past second, so the window is initially empty, and requests start trickling in: An initial 2 ms request gives us a worst-case latency of 2 ms A second 1 ms request gives us top-2 latencies of {1 ms, 2 ms} A third 100 ms request (with [2 ms, 1 ms, 100 ms] in the 1-second window) gives a top-2 of {2 ms, 100 ms} Eventually, the 2 ms request ages out of the 1-second window, so we’re left with [1 ms, 100 ms] in the window, and a top-2 of {1 ms, 100 ms}. Common instances of aggregates over inverse-less associative operators include min/max, sample variance, heavy hitters, K-min values cardinality estimators, and miscellaneous statistical sketches. In all these cases, we want to work with monoids. As the number of values in the window grows, maintaining such aggregates becomes far from trivial; adding values is easy, the challenge is handling deletions efficiently. This post explains one way to augment an arbitrary FIFO queue ...