Architecture · codec-independent
Only the chunks that can possibly contribute.
Every id splits into a 16-bit chunk key and a 16-bit remainder. The key is metadata, the remainder is payload, and the two live apart — which is the whole trick. Intersecting two 2,000,000-id segments compares keys first and fetches only the 100 shared chunks of 2,000. The other 1,900 are never requested and never billed.
Which chunks, decided before a byte moves
A single cursor walks both sorted key lists. A key present in only one segment cannot contribute to an intersection, so it is dropped without being read — skipping is the default, not an optimisation applied after the fact.
5 in both — fetched 6 in one segment only — skipped 7 in neither 18 keys, one pass
The whole operation, in four steps
Each step names what it does and what it cost. The numbers are from the same measured run as the panel above.
- 01 Resolve the generation once per operand Each segment's current generation is read from its registry row before any fan-out, and every chunk this operation fetches comes from that generation. A read is never a merge of two sources, so it cannot be torn.
- 02 keys(A) ∩ keys(B) 100 / 2,000 Metadata only. Cardinality per chunk is stored beside the key, so this phase never opens a payload.
- 03 Plan the fetch 3,800 skipped Every non-aligned key in either segment. Not deferred and not cached — the request is never issued.
- 04 Stream the AND 3,000 bytes The payload footprint is bounded by concurrency × operands × chunk — the window, not the segment size. That is the whole term: there is no second source to snapshot alongside it, so sizing a function for a many-operand intersection is those three numbers multiplied and nothing else.
There is deliberately no code on this page. What it owes you is the sequence and its costs; the calls that produce it are on usage, once, where they can be copied.
Two tiers, and the pointer that picks the generation
A segment is not moved between tiers — it lives in the object store, and the cache tier is a cache in front of it. Only the pointer decides what a read sees.
| Layer | Role | Cost shape |
|---|---|---|
| CACHE · RAM | A bounded LRU of decoded chunks in your own process, keyed by generation. Optional and evictable — correctness never depends on it, only latency. | your memory |
| STORAGE · .crbm | Immutable, generation-keyed objects in your bucket. Never mutated in place, so a reader always sees a whole generation and a superseded one can be kept as a snapshot. | $0.03/mo · 1.2 GiB |
| GEN · REGISTRY | Not a tier: one small row per segment holding currentGen. It stores no bits — it is the compare-and-swap target a publish advances, and the thing a read resolves once so that every chunk it fetches comes from the same generation. | one row per segment |
Loading a generation
Data enters exactly one way: store.load streams a set of ids into one immutable object, then publishGeneration advances the pointer. There is no per-id write, so there is nothing to fold back in later and no background job on the read path. On S3 the write and the publish cost $11.20 per million loads, pointer included — measured request counts at list prices, for those two steps; store.load's listings and clean-up pass come on top, about doubling it — so batch the refresh.
Exact counts, zero payload reads
Cardinality per chunk is stored beside the chunk key, so count() sums metadata and never opens a payload. It is exact, not estimated — no HyperLogLog, no error bars. $0.14 per million counts in the July run, without the pointer read that the single-bucket store now adds.
An erasure, and a publish
The two operations most systems get wrong. Both are shown rather than asserted, and in both the order of events is the point.
in generation 6 the id being erased cleared in generation 7
eraseSubject streams the current generation, clears one bit, verifies the result and publishes it forward-only — then collects the generation that held the bit. There is no tombstone to honour on the read path, and nothing to compact later: when the call returns, the bit is physically gone from the bucket.
The new generation is written beside the old one, and the pointer flips last, by compare-and-swap, and only forward. Until it does, every reader still sees generation 6 — so a half-written publish cannot be observed, a crash between the two steps leaves 6 authoritative, and the superseded object stays readable for a grace window before the sweep collects it. Every write in the library is this same protocol.
Three more that hold
Not intentions. Each of these has a named test or a typed guard behind it, and the right-hand column is where to look for it.
- ✓ Intersect is commutative a named test a.intersect([b]) and b.intersect([a]) return the same set — asserted by a test called is commutative, not by a comment claiming it.
- ✓ The object ceiling is reachable 78 GiB S3 allows 10,000 multipart parts, and at an 8 MiB part that is the real ceiling. Exceeding it raises a typed ValidationError — never a raw S3 400, and never silent truncation.
- ✓ All tier bytes are untrusted safe decode + cap Payloads pass the safe deserialiser behind a hard size cap before they reach the native addon, and every chunk key and value coming back from storage is range-checked. A corrupt or hostile chunk is a typed error, not a crash.
Every hard correctness invariant carries named tests — property tests checking a loaded generation against a plain Set oracle, and crash and race tests over the write-then-publish path — and the whole suite runs on every commit. The test count is deliberately not printed here: it moves with almost every commit, and the invariants do not.
Errors, and which ones retry
Every failure is a typed error, never a thrown string, because the interesting question at a call site is not what went wrong but whether trying again could possibly help. That is a property of the error's kind, so the kind decides.
| Error | What it means | Retry |
|---|---|---|
| TransientError | The backend was briefly unavailable — throttled, a dropped connection, a 5xx. | Automatic |
| WriteConflictError | Another writer already took the generation number you were writing. Write-once storage refusing to be overwritten — working, not failing. | New generation |
| IntegrityError | Bytes came back that do not match their checksum. Something is corrupt; the same request will return the same corruption. | Never |
| KeyUnavailableError | An encrypted segment's key is gone or unreachable. If it was crypto-shredded, this is the correct and permanent answer. | Never |
| ValidationError | A bad argument reached a boundary. Your bug, and it fails immediately. | Never |
Deterministic failures are never retried. Replaying a request that failed for a reason that has not changed either cannot help or is actively wrong — and a retry loop that hides a corruption is worse than the corruption. Write conflicts are the one middle case, and they split in two: the publish's compare-and-swap re-reads the row and tries again, because advancing a pointer forward is idempotent, while a write-once collision on the object is never replayed — the identical PUT would fail identically, and the fix is a fresh generation number rather than another attempt at the same one.
Watching it, and knowing it holds
The engine emits neutral domain events — no vendor, no telemetry dependency, and no emission at all when no sink is wired, so the default costs nothing on the hot path. A short adapter maps them to OpenTelemetry, Datadog, or a log line.
- 01 The chunk-skipping is observable in production, not just in a benchmark intersect The intersect event carries fetchedChunks and skippedChunks for the real operation. The ratio the demo steps through on a recorded run is the same number you can graph off your own traffic — which is the only way to know the skipping is still working on your data.
- 02 Where the bytes and the milliseconds went storage.get · cache · op Every object-store GET reports its bytes and its duration, the cache reports hit or miss, and op times has, count and the *Into verbs on the injected clock. Events carry raw observations rather than dollars — turning bytes into money is the cost model's job, so rates stay yours to change.
- 03 Retries and state changes are events, not silence retry · audit A retry reports its reason with the attempt number and the delay, so backoff storms are visible rather than inferred — and there is exactly one reason, transient, because nothing does a read-modify-write to lose a race over. Every change of state is an audit event beside it: segment.publish, segment.rollback, segment.load-refused, segment.rewrite, segment.erase, segment.dispose, namespace.erase.
- 04 And why any of this should be believed a Set oracle Every generation in the property tests is written through the real load path and then checked, read back chunk by chunk, against a plain Set — deliberately the dumbest possible model of "a segment is a set of u32", so a dropped chunk, a mis-routed remainder or a stale generation shows up as a mismatch. The write protocol gets named tests of its own for the cases that are otherwise arguments: a crash between the object write and the publish leaves the previous generation authoritative; a publish arriving out of order, or onto a destroyed segment, is refused rather than applied; and a load that lost the write-once race takes the generation above the object that beat it, leaving that object intact. Time and randomness are injected rather than ambient, so a failure is reproducible instead of being a story about a flaky test.
What this design costs you
Every architecture is a set of trades. These are ours — and where a figure is owed rather than measured, the row says so instead of rounding it into a claim.
- 01 A miss in the cache is a trip to object storage one ranged GET Once a store has read a segment's pointer and index, a membership check the LRU cannot answer costs one ranged GET against your bucket — there is no middle tier to answer it more cheaply. The first read of a segment also reads its pointer and its index, and the pointer is read again at most once per cache.genTtlMs, 2 s by default. Object-store latency, in other words, and no in-region percentile for it is published: that run is listed as owed, not measured.
- 02 Sustained high read rates lose to a flat node 329.15 reads/s Past that rate, with a cold cache, the metered bill overtakes $346/mo for a Redis-HA node. Cache hits move it in your favour; we publish the crossover at a 0% hit rate rather than waiting to be asked. See it.
- 03 There is no small change a whole generation A set changes only by loading a new generation, so correcting one id costs a rewrite of the segment that holds it. Immutability is what buys the untearable read and the physical erasure; the price is that nothing is cheap to edit, and that the retention sweep which collects superseded generations is a job you schedule.
See it on a real run.
The demo steps through the intersection above with the recorded counters, and the benchmarks carry the measured costs, the real-cloud calibration, and the rate past which a flat node is cheaper.
npm i @cloudbitmaps/roaring @cloudbitmaps/s3
# the memory and local drivers need nothing else
# for a real backend, add its package:
# @cloudbitmaps/s3 · @cloudbitmaps/gcs · @cloudbitmaps/azure-blob