CloudBitmaps

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.

Step through a measured run → The API that does it

None of this depends on the codec, so it stays true for every flavor.

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.

Key alignmentBoth segments, key by key
Segment A
Segment B

5 in both — fetched 6 in one segment only — skipped 7 in neither 18 keys, compared first

A key in only one segment cannot contribute to an intersection, so it is dropped after a comparison and nothing more — no request, no transfer, no bill. Five of these eighteen are fetched; on the real segments it is 100 of 2,000.

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.

  1. 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.
  2. 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.
  3. 03 Plan the fetch 3,800 skipped Every non-aligned key in either segment. Not deferred and not cached — the request is never issued.
  4. 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.

Two tiers, one pointerScrolls sideways on narrow screens
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.

An erasureOne bit, one rewrite
Gen 6
The id
Gen 7

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).

A publishNever in place
Load · stream
Storage objects
Pointer

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.

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.

What you will catch 5 of 12 error classes
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.

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.

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.

Apache-2.0 · v0.27.0 · zero-dependency core · 4 storage drivers

InstallA codec and a storage
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