Stratum — Streaming Primitives on Top of Classical Math

Overview

Spent a week composing four classical streaming algorithms into one library with a shared architectural shape. Top-K via EVT-membrane, heavy hitters via Misra-Gries (1982), distinct count via HyperLogLog, set membership via a Galois bipartite filter from the Ribbon family. Dual Python/native backend, Rust crate, an Arrow bridge into any SQL engine, and a single-binary HTTP dashboard. None of the algorithms are novel. Every primitive has a 1980s–2010s paper behind it. The interesting work was the composition: noticing that mergeable summaries is one property that simultaneously gives you persistence, distribution, and time-window rollups for free, and that Apache Arrow is the right boundary between a streaming primitive and a SQL engine.

Final Results (Apple M-series, single thread)

Against the canonical Python solution, same workload (Top-100 over 2 M random uint64):

* Python→C FFI overhead dominates the one-shot bulk case here. For per-event streaming where the tail matters, integrate from C++ / Rust directly — that's where 0.26 ns / 5.94 ns become visible.

The Brief

"Take the lock-free streaming-analytics code we have and turn it into a real product. Beat std::priority_queue and std::unordered_set in HFT-style hot paths. Keep p99.99 in nanoseconds. Pure C++17. Ship it with bindings, with benchmarks against the obvious alternatives, with honest documentation about what's borrowed math versus what's engineering."

Starting point: a handoff from a previous session — a working but bench-grade C++17 core implementing two ideas. An "EVT membrane" Top-K (replace a min-heap with a single std::atomic<uint64_t>::load(relaxed) as the cutoff), and a Galois bipartite filter (GF(2) linear-algebra encoding of set membership — which turns out to be a Ribbon Filter variant; I didn't know that at the start either).

Development Journey

v0.1 → v0.2 — Production hardening

The handoff code worked but was a sketch. Added an mmap-backed arena allocator so the Galois filter can load from a file with zero copy, and share across processes via MAP_SHARED. Added a C ABI so Python and Rust can bind without writing C++. Wrote a ctypes-based Python package with numpy zero-copy bulk ingest. CMake, unit tests, microbench, a global merger thread that periodically aggregates per-shard Top-Ks into a final snapshot.

At v0.2 the code worked but the Galois filter's "placer" was lossy — it could in principle produce false negatives. I had told myself that was fine for benchmark purposes. It wasn't.

v0.3 — The math actually works

Replaced the lossy placer with a real two-step Gaussian-elimination Cuckoo builder.

Step 1 — two-choice load balancing. Each key has two candidate blocks (h1, h2); assign it to whichever is less loaded. Standard power-of-two-choices result. Default load factor 50 keys/block (10.41 bits/key) gives reliable builds; the asymptotic 8.67 bits/key requires load factor 60 with seed retry.

Step 2 — per-block GF(2) solve. For each block, set up the linear system V · P_j = F_j over 8 right-hand sides at once (share the elimination across columns). Solve via standard row reduction. If inconsistent, increment the seed and retry. 256 seeds is enough that build failure probability is astronomically small.

Honest about it: the asymptotic 8.67 bits/key from the original handoff requires the seed-retry budget; the reliable default I ship is 10.41 bits/key with guaranteed zero false negatives. Both knobs documented.

Also shipped: AVX-512 VPOPCNTDQ filter path (compile-time gated; I don't have Sapphire Rapids to validate it), SSTable file format with magic+version header, Rust crate.

v0.4 — See it run

Wanted a way to demo the engine without making people read a Python script. Built a single-binary HTTP/1.1 + SSE server in ~400 lines of C++. Hand-rolled HTTP parser, no httplib, no Boost. Endpoints: /, /topk, /ingest, /stream, /metrics, /healthz. Browser dashboard in vanilla JS with no build step.

The SSE stream is delta-encoded — every tick, the server diffs the current sorted Top-K against the previous one and emits only items that entered or exited. Steady-state bandwidth ~30 bytes per event. Unintended side effect: the rate of delta events doubles as a distribution-drift signal. Stationary stream = empty deltas. Non-stationary stream = bursts. You can grep the SSE feed for drift. I did not plan this; it fell out of the encoding.

v0.5 — heapq is shockingly fast (and a real bug)

Wrote an honest side-by-side benchmark against the canonical Python solution (heapq.heappush + set). Expected Stratum to win comfortably. It didn't:

5M events, K=100:
  python heapq:     11.6 M ev/s
  stratum (native): 33.7 M ev/s  (only ~3× faster)
  correctness:      17/100 of the top-K match  (!!)

Two problems, both real.

(1) heapq is faster than I assumed. It's a C-implemented heap under a Python for loop. The inner loop is tight, allocations are amortized, GC barely triggers at K=100. Beating it by a small constant on throughput isn't an interesting story.

(2) 17/100 correctness mismatch. Took an hour to track down. AsyncTopK keeps a partial "active" buffer and only flushes to the merger when the buffer fills. With a finite stream that ends mid-buffer, the last few hundred events per shard never reach the merger — and some of those events were the actual top values. The pipeline had been "working" for days; what had been working was the throughput. Correctness against a reference implementation hadn't been tested until I wrote the side-by-side.

Fix for the bug: added a request_flush() flag the worker polls on idle, and a Pipeline::drain() end-of-stream barrier. Verified 100/100 match across three runs.

Fix for the throughput finding: didn't fight the FFI boundary. Built a parallel pure-Python backend that uses numpy.argpartition (O(N), SIMD) for the bulk case. For one-shot bulk it now beats heapq by ~16×; the native backend keeps the 5.94 ns story for per-event streaming where the tail matters. Dual backend, one API:

from stratum import TopK
tk = TopK(k=100)                       # backend="python" by default.
tk.add_many(arr)                       # numpy.argpartition, O(N), SIMD.
tk = TopK(k=100, backend="native")     # libstratum C++ pipeline.

v0.6 — Mergeable summaries (one math idea, three properties)

Three honest limitations remained: no persistence, no distributed view, no frequency tracking. Tried to attack them separately. Then noticed the same idea solves all three: mergeable summaries (Agarwal, Cormode et al. 2013). A summary S is mergeable iff there exists a deterministic associative commutative ⊕ such that:

S(stream_a) ⊕ S(stream_b)  ==  S(stream_a ++ stream_b)

— exactly, or with the same error bound. The same concept appears in five fields under five names:

• Streaming algorithms call it a mergeable summary.
• Distributed systems call it a CRDT (Shapiro 2011).
• Database systems call it a linearizable aggregate.
• Algebra calls it a commutative monoid.
• Category theory calls it a monoid object.

When five disciplines independently rediscover the same shape, the shape is fundamental. If your primitive is mergeable, three operational properties fall out free:

1. Persistence without a write-ahead log. Snapshot to disk on whatever cadence you want; recovery is merge(load(snapshot), in_memory). The hot path never touches disk. Loss bound: bounded by the gap between snapshots, which you choose.
2. Distributed view without consensus. Each node builds its own summary. Periodically gossip and merge. Global view is exact (or has the same bounded error) without Raft or Paxos. This is the algebraic foundation under Cassandra's anti-entropy and Riak's sloppy quorums.
3. Time-window rollups without rescanning. Build one summary per minute; the hourly summary is the merge of 60 of them.

For frequency tracking, picked Misra-Gries (1982). Four pages, beats most modern streaming sketches, mergeable. ~10 ns per add via an open-address hash table.

v0.7 — The SQL bridge (without writing a query engine)

Last limitation: no SQL, no joins, no window aggregates.

The wrong answer: build a query engine inside Stratum. Every "streaming SQL" startup that died tried that.

The right answer: make the primitives queryable by every SQL engine that already exists. The interop layer is Apache Arrow. DuckDB, Polars, DataFusion, ClickHouse, Velox all accept Arrow tables as virtual tables in zero-copy. All I had to write was:

def to_arrow(primitive) -> pyarrow.Table: ...
def register(con, name, primitive):
    con.register(name, to_arrow(primitive))

That's ~80 lines of Python. Now:

import duckdb, stratum
hh = stratum.HeavyHitters(k=32, backend="native")
hh.add_many(user_ids)

con = duckdb.connect()
stratum.sql.register(con, "hh", hh)
con.sql("""
    SELECT h.key, h.count, u.name, u.status
    FROM hh h LEFT JOIN users u ON h.key = u.id
    ORDER BY h.count DESC LIMIT 10
""")

Stratum does the streaming heavy lifting; DuckDB does the JOIN. Both stay good at what they're good at. Each primitive maps to one SQL pattern exactly:

The right column is what makes the bridge interesting: those are queries that, run via a generic engine, scan all input rows. Run via Stratum's mergeable summaries, they touch only K-sized state. On the explainer benchmark (5M events, JOIN against a users dimension table): Stratum-then-SQL = 61 ms, DuckDB-only = 180 ms.

Also shipped: HyperLogLog as a second mergeable primitive. Measured accuracy 0.03% over 1M cardinality at precision 14; merge accuracy 1.36% on a 750k-element union.

Final v0.7 Metrics

What I Learned

The cross-disciplinary borrow that worked

The single most useful insight wasn't a clever algorithm — it was noticing that "mergeable summary" from streaming-algorithms, "CRDT" from distributed-systems, and "commutative monoid" from algebra are all the same thing. Once you see it, three operational properties (persistence, distribution, time-window rollups) collapse into one property, and that single property is what's needed to compose primitives into systems. Borrowing across fields is high variance, but when it lands, it tends to land structurally rather than incrementally.

Don't fight the FFI boundary

I lost a couple of hours assuming Stratum's native backend had to win on raw throughput against heapq at every scale. It doesn't and shouldn't. Python→C FFI has ~600 ns of overhead per call; that swamps any 0.26 ns hot path when called one event at a time from Python. The right move was to admit it, build a parallel pure-Python backend on numpy.argpartition for the bulk case, and reserve the native backend for streams that actually care about per-event tail latency. Dual-backend ended up being the right product shape; I got there the painful way.

End-of-stream behavior is the most common bug

Streaming primitives don't naturally have a "stop" — they assume more data is coming. When the stream actually ends, edge cases surface. The v0.5 17/100 correctness mismatch was exactly this: partial buffers never flushed because no more events arrived to trigger the flush. Every streaming primitive needs at least one test where it has to match a known-correct reference on the same input, including end-of-stream. If I'd written that test on day one I'd have caught the bug on day one.

Workloads that violate an algorithm's guarantee aren't bugs in the algorithm

Three times during this work I saw "the demo is broken" when the demo was correctly showing the algorithm refusing to lie. Twice with Misra-Gries (attacker frequencies below N/(K+1)), once with an HLL bucket count that was too small for the merge case. The sanity check that would have prevented all three: derive the algorithm's guarantee constraints first, then design the workload to sit comfortably inside them. Demos that violate the guarantee zone are giving you the right answer; they're just answering a different question than the one the demo's prose claims.

Composition beats invention

None of the four primitives are new. The interesting work was making them fit: same architectural skeleton (shared-nothing per-shard workers, lock-free SPSC ring buffers, mmap snapshots), same API surface (add, add_many, top, save, load, merge), same dual backend (python / native), same Arrow representation for SQL handoff. The fit is the contribution. None of it would matter without the underlying math from Misra-Gries (1982), Flajolet (2007), Heule (2013), Dillinger-Walzer (2021), and Agarwal-Cormode (2013) — and nothing in the math required new ideas to compose this way; it just required someone choosing to.

What I Will NOT Claim

• None of the algorithms are novel. EVT-membrane Top-K, Galois bipartite filter (Ribbon variant), Misra-Gries, and HyperLogLog all have 1980s–2010s papers. The engineering, the composition, and the dual-backend API are what's new here.
• All numbers are Apple M-series. I don't own x86 hardware. The AVX-512 VPOPCNTDQ filter path is gated on __AVX512VPOPCNTDQ__ and compiles, but I have not measured it on real hardware. The reference Sapphire Rapids / Zen 4 numbers from the original handoff are someone else's.
• Streaming add() from Python is FFI-bound, not nanosecond. The 0.26 ns and 5.94 ns numbers are the C-side hot path, measured by bench_micro. From Python, per-call overhead is ~600 ns. Use add_many with chunks of 1k+, or call the C ABI from C++ / Rust directly.
• This is not a database. No transactions, no streaming joins, no late-data handling, no SQL of its own. It's a primitive that hands off cleanly to a query engine via Arrow.
• Persistence is bounded-loss, not durable. Snapshot + merge on recovery loses at most the events between the last snapshot and the crash. Adequate for analytics; not for a database log.
• This took a week of wall-clock — heavily AI-assisted (Claude wrote most of the C++ under my direction; I designed the architecture, picked the math, decided what to ship vs cut). It is what one person + a strong LLM can produce when the problem decomposes cleanly into small primitives. The artifact is what got built; the time is what got spent.

Numbers I Will Defend

If any of those don't reproduce on the same hardware, the writeup is wrong and I want to know.

Meta

Built over a week in May 2026 on a single Mac mini M-series, with one person and one LLM. The math is from Misra & Gries (1982), Flajolet et al. (2007), Heule et al. (2013), Dillinger & Walzer (2021), Agarwal et al. (2013), Shapiro et al. (2011), and the extreme-value-theory literature. The engineering, the benchmarks, the bugs, the failures, and this writeup are mine.

License: MIT.