Skip to content
The Data EngineeringThe Data EngineeringBeta
About
Main content

Out-of-order handling and buffering

What does it cost to put a disordered stream back in order, and when can you skip ordering altogether?

Suppose you want to emit records in event-time order from a that arrives out of order. You need a deeper than the disorder.

If the disorder is bounded by K (no record arrives more than K after a record with an earlier timestamp), then sorting needs a heap (a data structure that always returns the smallest item) holding the records of one K-wide . That is O(K) memory and O(log K) work per record.

If the disorder is unbounded, the memory is unbounded too. That is why no production system actually sorts a stream. Real systems put records in window buckets and release a bucket when the passes it. That is the same reorder buffer, but divided into coarse pieces and given a stopping rule.

The cheapest escape: do not need order

The cheapest way out in this whole mechanism is to not need order at all.

  • Order does not matter ( and ): sum, count, minimum, maximum, (HyperLogLog, a small sketch that estimates how many distinct items were seen), Count-Min (a small sketch that estimates how often each item was seen). These need no buffer, because the arrival order cannot change the answer.
  • Order matters: first, last, sessionization (grouping a user's events into visits separated by gaps), pattern matching, exact , and floating-point sums, because floating-point addition is not associative (summing the same numbers in a different order can give a slightly different result).

So the first question is not "what δ should I use?" It is "is my operator commutative?" The answer changes the whole problem. This is the same trick as CRDTs (replicated data types, built so that updates can arrive in any order and still give the same result): .