Four Algorithms That Run Inside Every Kafka Cluster
Not the API surface — the machinery underneath it. Four interactive simulations of the algorithms every Kafka cluster runs: Boyer-Moore majority vote, consistent hashing, ISR and the high watermark, and sparse-index binary search. Drive each one and watch the invariants hold or break.
Not the API surface — the machinery underneath it. Each algorithm below is running live; drive the controls and watch the invariants hold or break.
Boyer-Moore majority vote
One pass, two variables, no buffering. Finds an element occurring more than n/2 times, or reports garbage if none does.
IN KAFKA: the shape of every Streams aggregator — bounded state small enough to survive a changelog restore
The counter never exceeds a handful regardless of stream length. That constant-space property is what makes it viable as a Streams aggregator: the whole state is a two-field record backed by a changelog topic. Cancellation is the mechanism — every non-candidate destroys one unit of candidate evidence, and only a true majority has more evidence than everything else combined.
Consistent hashing
Map keys to nodes so that adding or removing a node relocates a minimal share of keys instead of reshuffling everything.
IN KAFKA: partition assignment and the sticky assignor's attempt to minimise rebalance churn
Naive modulo hashing reshuffles nearly every key when the broker count changes. The ring moves only the keys that sat between the departed node and its successor. Raise the vnode count and the load distributes more evenly, at the cost of a larger routing table — the same trade Kafka's sticky partition assignor makes when it tries to preserve existing ownership across a rebalance.
ISR and the high watermark
A min-reduction over a dynamic set. The set shrinks when a replica falls behind, and the reduction decides what any consumer is allowed to see.
IN KAFKA: replication safety — acks=all, min.insync.replicas, and the durability/availability trade
The high watermark is a min-reduction over the in-sync set, and it is the only offset consumers may read. Kill enough replicas and min.insync.replicas stops accepting acks=all writes — the cluster chooses unavailability over silent data loss. Everything a consumer sees is bounded by the slowest replica still counted as in sync.
Sparse index binary search
Binary search over an index that intentionally omits most entries, followed by a bounded linear scan.
IN KAFKA: every consumer fetch and seek against an on-disk log segment
This is why an offset lookup costs microseconds against a multi-gigabyte segment. The index is deliberately incomplete — mmap'd, a fraction of the log's size, and it only has to get the reader close. Binary search narrows to a floor entry, then a short linear scan finishes the job. index.interval.bytes is the dial: denser index, faster scan, more memory.
The common thread: bounded state under unbounded input. Every one of these trades exactness or completeness for a memory ceiling that does not move as the stream grows.