Stratum

Streaming Top-K, heavy-hitters, cardinality, and set-membership primitives for hot paths where p99.99 latency matters. C++17 core + Python (dual backend) + Rust crate + an Arrow bridge into any SQL engine.

The core is not novel work. It's a collection of well-known streaming algorithms — EVT-membrane Top-K, Galois bipartite filter (Ribbon family), Misra-Gries heavy hitters, HyperLogLog — composed into one library with a shared architectural shape (shared-nothing per-shard workers, lock-free SPSC ring buffers, mmap snapshots, deterministic merge). What's shipped here is the engineering: cache-line padding, branchless GF(2) parity, async double-buffered nth_element, the Arrow interop, and an honest set of benchmarks against the obvious alternatives.

Measured numbers — Apple M-series, single thread

Operation	Latency
EVT membrane check	0.26 ns
Galois filter contains()	5.94 ns
Galois filter build	4.1 Mkeys/s
HLL accuracy at p=14	0.03% / 1M
HLL merge accuracy	1.36% / 750k
Bits/key (default)	10.41
Bits/key (asymptotic)	8.67
Galois FP rate (measured)	0.76% (predicted 0.78%)

Head-to-head — same workload, three implementations

Top-K of 2 M random uint64 events, K=100:

Approach	Throughput	Memory	Honest weakness
Python heapq min-heap	12.0 M ev/s	3,720 B	GC tail spikes; GIL
Stratum (python backend)	191.3 M ev/s	800 B	bulk-only; needs numpy
Stratum (native backend)	25.5 M ev/s*	3,200 B	C build required

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

Build

./scripts/setup_venv.sh     # creates .venv with numpy / duckdb / pyarrow / matplotlib
./scripts/build.sh          # cmake -B code/build, runs the native test suite

Requires: C++17, CMake ≥ 3.16, POSIX (mmap), Python ≥ 3.9. On x86 the AVX-512 VPOPCNTDQ filter path is enabled when the compiler sees __AVX512VPOPCNTDQ__; otherwise the scalar __builtin_parityll path is used (default on ARM).

Run

source .venv/bin/activate

./scripts/run_explainer.sh                # head-to-head benchmark (start here)
python demo/06_mergeable.py               # persistence, distributed merge, frequencies
python demo/07_sql_bridge.py              # SQL via Arrow → DuckDB
python demo/08_visual_benchmark.py        # regenerates benchmarks/comparison.png

./scripts/run_server.sh                   # live HTTP/SSE dashboard at http://127.0.0.1:8080/

C++ side:

code/build/test_basic                     # all C++ tests
code/build/bench_micro                    # microbench (membrane, filter, build)
code/build/stratum_server --port 8080     # the dashboard server, standalone

Rust side:

cd rust/stratum
DYLD_LIBRARY_PATH=../../code/build cargo test --release

Python API

from stratum import TopK, HeavyHitters, Cardinality, Filter, sql

# Top-K largest values (Python backend by default — no C build required)
tk = TopK(k=100); tk.add_many(numpy_uint64_array); tk.top()

# Top-K most frequent keys (Misra-Gries, mergeable)
hh = HeavyHitters(k=32, backend="native")
hh.add_many(arr); hh.top(10)

# COUNT(DISTINCT) via HyperLogLog
hl = Cardinality(precision=14); hl.add_many(arr); hl.estimate()

# Set membership (Galois bipartite filter, ~10 bits/key)
f = Filter(expected_keys=1_000_000); f.build_shard(0, keys); f.contains(0, q)

# Push any of the above into DuckDB as a queryable Arrow table
import duckdb; con = duckdb.connect()
sql.register(con, "hh", hh)
con.sql("SELECT * FROM hh WHERE count > 1000")

All four primitives are mergeable: T.merge(a, b) returns the summary you'd have built from a's input ++ b's input. This is what gives Stratum persistence (snapshot + merge on recovery, no WAL) and distribution (merge across nodes without consensus).

C++ API

#include "stratum/pipeline.hpp"

stratum::PipelineConfig cfg;
cfg.shards = 4; cfg.local_k = 1024;
stratum::Pipeline p(cfg);

p.ingest(/*shard=*/0, value);
auto top = p.global_topk();

See docs/api.md for the full surface.

C ABI

#include "stratum_c_api.h"
stratum_pipeline_t* p = stratum_pipeline_new(&cfg);
stratum_ingest(p, shard, value);
stratum_global_topk(p, out, capacity);

The same C ABI backs the Rust crate in rust/stratum/.

Limitations

• Not novel research. Every primitive in this library has a 1980s–2010s paper behind it (see References). The engineering — shared-nothing shards, the dual Python/native backend, the Arrow bridge, the mergeable-snapshot persistence story — is what's new.
• uint64 keys only. Strings, tuples, structs need an upstream hash the caller supplies.
• No durability inside the hot path. Persistence is by mergeable snapshot — recovery loses at most the events between snapshots. Adequate for analytics; not for a database.
• No distributed transport. Cross-node merge works (the math is ready) but you supply the transport (HTTP, gRPC, gossip).
• Honest about the streaming-add() FFI cost. Python→C per-call overhead is ~600 ns. For real per-event streaming from Python, batch into 1k+ chunks and use add_many. For sub-microsecond tails, link the C ABI from C++ / Rust directly.
• No AVX-512 query path validated. Build flag exists; needs Sapphire Rapids / Zen 4 hardware to confirm bit-for-bit correctness against the scalar reference.

Repository layout

code/        C++17 core (headers, src, C ABI, HTTP server, tests, CMake)
python/      ctypes FFI + pure-Python backends + Arrow / SQL bridge
rust/        safe wrappers over the C ABI
web/         live dashboard (HTML + vanilla JS, no build step)
demo/        runnable demos
math/        algorithm notes — EVT, GF(2), jitter, capacity, mergeable, SQL
docs/        architecture, API, deployment, when-to-use
benchmarks/  reproducible perf numbers + the headline image
scripts/     build / venv / run helpers

When to use this (and when not to)

See docs/why_stratum.md. Short version:

• Python heapq for prototypes and streams under ~1 M ev/s.
• Redis sorted-sets when you need durability and your throughput is under ~100 K ev/s per client.
• Kafka + Flink / Materialize when you need distributed durability + replay + SQL over the stream itself.
• Stratum when p99.99 latency is a contract, you need >10 M ev/s on a single node, or you need a single embeddable library you can call from C++ / Rust / Python.

License

MIT. Copyright © 2026 Vico Bonfioli.

References

• Misra, J. & Gries, D. Finding Repeated Elements. Science of Computer Programming, 1982.
• Flajolet, P. et al. HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm. AofA 2007.
• Heule, S., Nunkesser, M. & Hall, A. HyperLogLog in Practice. EDBT 2013.
• Agarwal, P.K. et al. Mergeable Summaries. PODS 2013.
• Dillinger, P.C. & Walzer, S. Ribbon filter: practically smaller than Bloom and Xor. SEA 2021.
• Shapiro, M. et al. Conflict-free Replicated Data Types. SSS 2011.
• Demers, A. et al. Epidemic algorithms for replicated database maintenance. PODC 1987.