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 requests only the 100 shared chunks of 2,000. The other 1,900 are never requested by key: each object’s one opening read takes its last 256 KiB (the default), where its index of keys sits.
Which chunks, decided before a chunk is requested
Each segment's chunk keys come out of its index, and every key of the smaller one is looked up in the other's. A key present in only one segment cannot contribute to an intersection, so it is dropped without being requested — 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, compared first
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 the chunks are fetched from it. Every chunk is one whole, checksum-verified chunk of one generation, never a merge of two sources, so a read cannot be torn. What a call can meet — a long one most often — is a second instant: a cache.genTtlMs refresh after a publish, the reader cache evicting the segment on a store with no timed refresh, the resolution cache letting the segment's resolution go on a store with one, a sweep of the generation it was reading, met by this read or another, or an invalidation moves the rest of its chunks to whichever generation is current then. To hold one generation for as long as a job runs, take a pin, seg.pin() — a hold, not a lease: a pinned read fails rather than read another generation once its own is collected, so keep enough generations for the job.
- 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 100 of 2,000 chunks The payload in flight is bounded by concurrency × operands × the 1 MiB a range may be — the window, not the segment size. The store holds two more things under caps you set: up to cache.maxChunks decoded chunks in its cache, and the open segments' indices, up to cache.readerMaxBytes. The call itself holds each operand's chunk keys, at most 65,536 of them. Sizing a function for a many-operand intersection is that window, those two caps and the keys.
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. Always on, capped by cache.maxChunks, 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 every chunk a reader fetches is whole, and a superseded generation stays readable until it is collected — which is what a rollback moves back to. | $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, before it fetches a chunk. | one row per segment |
Loading a generation
Data enters exactly one way: store.load streams a set of ids into one immutable object, then the publish moves the pointer to it by compare-and-swap. 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 a segment's first single-part store.load() costs $11.20 per million loads, pointer included — measured requests on S3, priced at list prices — so batch the refresh. A multipart store.load(), measured the same way, made 5 PUT-class + 3 GET, $26.20 per million.
Exact counts, zero payload reads
The registry row records the current generation's id count, and each chunk's cardinality is stored beside its key, so count() answers from metadata, in one request when cold, and never opens a payload. It is exact, not estimated — no HyperLogLog, no error bars.
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 fenced on the generation it streamed — if a load or another erasure moves the pointer meanwhile, the fence refuses the rewrite and the ledger says superseded, so you re-run. Then it collects the generation that held the bit. An id found only outside the current generation (a retained older generation, one above the pointer, a first load's object on a segment with no generation yet) is deleted with those generations, and the ledger reports erased: true all the same. There is no tombstone to honour on the read path, and nothing to compact later: for every segment the ledger reports erased: true, the bit is physically gone from the bucket when the call returns. A noncurrent version, a soft-deleted copy, a replica or a backup keeps the old object until its own lifecycle removes it (how an erasure stays correct).
The new generation is written beside the old one, and the pointer flips last, by compare-and-swap, and only forward. A load's swap is also fenced on what it read, the row or its absence: if another write lands in between, the load reports superseded rather than overwrite it. Until the flip, 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 next load collects it. Every write of a segment's contents is this protocol; the one call that moves a pointer back is an operator's rollback, and it writes no object at all.
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, so at the default 8 MiB part the ceiling is 78 GiB; maxObjectBytes raises it, up to S3's 5 TiB, and grows the part to match. Exceeding the ceiling raises a typed ValidationError — never a raw S3 400, and never silent truncation.
- ✓ All tier bytes are untrusted safe decode + cap Payloads pass a hard size cap and a structural check before the safe deserialiser sees them, 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. By default the store retries it, with jittered backoff, on a segment's reads: has, count, iterate, a combine or a pin, and the reads inside subjectReport, exportSegments and an *Into. A write — a load, an *Into's publish, an erasure, a drop — is retried only where that is safe: a throttled write-once object on S3 and GCS is sent again, and a registry write that got no answer is settled by reading the row. Any other transient fault on a write, and a call that goes to the drivers directly, such as exists, generations or rollback, hands it to you. | On segment reads |
| WriteConflictError | A write lost a race. An *Into write raises it when another writer took the generation number or the destination's row changed while it was in flight — another publish, a retention change, a purge — and so does a rollback whose row moved. A collection pass raises it when it cannot prove the segment is still the one it started on, which can be after a publish has landed. A load reports the same race as superseded instead, and an erasure records it in its ledger. Working, not failing. | Re-read, then decide |
| IntegrityError | Bytes came back that do not match their checksum, or a stored registry row is malformed. Something is corrupt; the same request will return the same corruption. | Never |
| KeyUnavailableError | An encrypted segment's key cannot be unwrapped — the store has no keystore, or holds none of the keys that wrapped it — or a store that requires encryption met a cleartext segment. No retry changes it; the key or the wiring has to. A destroyed segment reads as empty instead. | 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: when the pointer's compare-and-swap loses, the publish re-reads the row and decides again — it advances a pointer that has moved only if its fences still hold, so a load fenced on the row it read stands down as superseded rather than overwrite what moved it — 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. Transient faults split too, along a different line: a read of segment data retries them automatically, while a write is retried only where the retry can be told from a second write. A conditional write that lands and then loses its response would, replayed blindly, report its own write as a conflict, so on S3 and GCS the registry row is sent once, on Azure Blob the client's retry can replay it (a replay that meets a conflict is read back by its id, which is not definitive for a row), and either way it is reconciled by its effect: the load reads the row back, takes a write the row shows landed as published, and sends a row that is unchanged again as a fresh compare-and-swap, a few times and after a wait, which the fence refuses if anything moved in between. A write-once object is sent again after a throttle on S3 and GCS under a write id that tells its own replay from another writer's. Nothing is deleted after an outcome that stayed unknown. Any other fault reaches the caller, and re-running the call is the retry: a re-run load with the same ids takes a fresh generation number, so once the first attempt has settled it publishes whether or not that attempt landed, though under the default keep: 1 it can cost the generation before the load.
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. Two sinks, wired in two places: metrics go to the one you pass the store as metrics, and audit events to the one you pass each call that takes one, as audit. A short adapter maps either 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 chunk a read fetches reports its payload bytes and its duration — 0 bytes, with no request behind it, for a chunk the index does not hold — the cache reports hit or miss, and op times has, count, the *Into verbs and materializeMany on the injected clock. Pointer and index reads emit no storage.get, nor do an erasure's reads, which go through the raw drivers, and a PUT emits nothing, so a bill needs the backend's own request counts. 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 read's 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: the store retries a read's transient faults, and retries a write only where a replay can be told from a second write. A write-once object is sent again after a throttle on S3 and on GCS, under a write id the object carries, and on Azure Blob, and on GCS above its simple-upload threshold, the client's own retry can replay it and the driver tells that from another writer's object by reading the write id back. A registry row is sent once on S3 and GCS, and on Azure Blob the client's retry can replay it, and a replay that meets a conflict is read back by its id, which is not definitive for a row. Either way it is reconciled by its effect: a publish that gets no answer, or loses its compare-and-swap, re-reads the row and advances only if its fences still hold, and otherwise says so to its caller. Nine kinds of change are audit events beside it, on the sink the call was given: segment.publish, segment.rollback, segment.load-refused, segment.rewrite, segment.collect, segment.erase, segment.tombstone, segment.dispose, namespace.erase. A retention policy's write (setRetention, clearRetention), a collection pass and the retention sweep's purge of its own tombstones emit none. Each segment.* event carries incarnation, the id of the registry row it found or wrote (absent on a refused first load that found no row), so a purged-and-recreated segment's generation numbers are told apart.
- 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 reports it, leaving the object that beat it 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 while its reader stays cached the pointer is read again at most once per cache.genTtlMs, 2 s by default. Object-store latency, in other words: a first read on an open segment took 27.37 ms at the median in the in-region run of 2026-11-03, and what is not yet measured is listed as owed.
- 02 Sustained high read rates lose to a standing cluster 329.15 reads/s Past that rate, with a cold cache, the metered bill overtakes $346/mo for a three-node Redis-HA cluster. 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 retires expired segments 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 standing cluster is cheaper.
npm i @cloudbitmaps/roaring @cloudbitmaps/s3
# the codec, and the storage you have —
# or @cloudbitmaps/gcs · @cloudbitmaps/azure-blob
# the memory and local drivers need the codec alone