Flavors · roaring · shipped · v0.10.0
Containers that pick themselves.
Every chunk of ids is stored in whichever of three encodings measures smallest — and that is measured on write, per chunk, with no configuration and no tuning knob. A real segment routinely holds all three at once.
Why not one big bitset?
Because the id space is 232 wide and almost all of it is empty. The bitset does not care: it costs the same whether you store five ids or five million.
One flat bitset over all 32 bits
4,294,967,296 possible ids, one bit each, is 512 MiB — allocated up front and paid in full for a segment holding five ids. Nothing about it scales with what you actually stored.
Roaring, same id space
The space is cut into 65,536 chunks of 65,536 ids. A chunk nobody has written to does not exist, and a chunk that does exist is stored in whichever encoding is smallest for its own contents.
That is the entire idea, and everything below is how the second half of it works. And note what Roaring does when a chunk really is dense: it stores that chunk as a flat bitset. The flat shape is not an alternative to this design, it is one of the three things this design picks between — which is why a separate plain-bitset flavor is not planned.
| If your set lives in | You get | Which is |
|---|---|---|
| Redis SETBIT / BITOP | A String treated as a bit array. That is all a Redis “bitmap” is. | One big bitset — the shape this section just argued against. Always the bitset container, for every chunk, dense or nearly empty. |
| Redis SADD / SINTER | A hash table of members. Small all-integer sets get a packed encoding, but that converts away as the set grows. | Per-member overhead rather than packed bits — the cost scales with cardinality, with no encoding decision anywhere. |
| Roaring | A per-chunk decision between array, bitset and run — the figure below. | Adaptive. The two rows above are each one of these three, chosen permanently and in advance. |
Measured One id set, encoded four ways by pnpm bench:encoding. Against the best fixed representation for each shape, at its own theoretical floor: a contiguous 1,000,000-id range is 543× smaller as roaring, a 2,000-run shape 63× smaller, scattered ids 1.88× smaller — and a half-dense block is 1.02× larger. Read that last one carefully, because it is not a shape where a flat bitset is the better idea: it is the shape where roaring becomes one. Every chunk there is past the array/bitset threshold, so each is stored as a flat 8 KiB bitset and the 2% is per-chunk bookkeeping. The floor of the adaptive choice is the fixed choice plus a rounding error. Encoded bytes, not Redis process memory: a real Set carries per-member overhead above the packed figure, so every alternative here is quoted at its best case.
Redis has no Roaring type of its own — there is a third-party module that wraps CRoaring, but a managed Redis service generally will not load arbitrary modules. So the honest comparison is not us versus Redis: it is Roaring versus a fixed representation. And the two are not exclusive. Redis is not one of our drivers — the storage here is your own bucket — but it is the easiest place to collect ids as events arrive one at a time, and a load is what turns what collected there into a single immutable object your intersections can skip through.
Coming from Redis bitmaps?
Then you are already using the shape this is built for. Here is exactly what carries over, and what does not.
| In Redis | Here | Difference |
|---|---|---|
| SETBIT key id 1 | No equivalent — no per-id write exists. | Ids are u32, same as a bit offset, but a segment changes only by getting a new generation. Compute the set upstream and store.load writes it as one object. |
| GETBIT key id | has | None in meaning. |
| BITCOUNT key | count | Exact, and read from the index without fetching payloads. |
| BITOP AND | intersect | Streams, and never fetches a chunk that cannot contribute. |
| BITOP OR | union | None in meaning. |
| BITOP DIFF (Redis 8.2+) | andNot | None in meaning. Reads each suppression list only where it overlaps. |
| BITOP AND dest a b | intersectInto | The destination form, which is the only form Redis has. The result becomes a new generation of dest — superseded, not added to — published forward-only, and you get back what it wrote. A combine that comes out empty is refused, not published over a non-empty destination, so a mistyped operand cannot wipe it. unionInto and andNotInto are the same for OR and DIFF. |
| EXPIRE key ttl | setRetention + retireExpired | Per segment, not per id: the writer records an absolute expiresAt and the sweep is a call you schedule — nothing here starts a timer. Never point an object-lifecycle rule at the bucket on its own; it deletes bytes the pointer still names. |
Not covered BITFIELD, BITPOS, BITOP NOT, and byte-range forms of BITCOUNT have no equivalent: this is a set of ids, not an addressable bit buffer, and there is no bounded universe to complement against. XOR and ANDOR have no single call but compose from the rows above.
Read this twice SETBIT flips one bit in place and is genuinely O(1), so a per-recipient loop is the natural Redis shape — and here it has nothing to port to. The loop becomes two decisions instead: where the ids collect as they arrive, and how often you load the set. If the set is defined by a query, run the query and load its result; if it is defined by events, accumulate them where they land and load on a cadence. A load bills per object, not per id — ten million ids are a handful of PUTs — so what you are paying for is the cadence, not the id count.
What that costs Two line items, and no third. A read that misses the cache is one ranged GET, once the segment's pointer and index are read; a publish is one object PUT plus the pointer's own PUT and reads. Storage is the segment sitting there, which is the cheap part. Nothing bills per id, and nothing bills while the segment is idle — which is the whole difference from a node you keep standing. Rates are region-specific and the vendor's to change; every figure we publish uses the default aws-us-east-1-ondemand profile, and estimateCost accepts your own.
One way in, and nothing to run A segment exists once you have loaded a generation into it; before that every read answers empty rather than erroring. There is no daemon, no compaction pass and no lifecycle worker — the only scheduled work is the retention sweep you trigger yourself (retireExpired), plus gcOrphanGenerations if you want superseded generations collected sooner than that.
You are not giving up the bitmap
A Redis bitmap is one flat bit array. Roaring stores each 65,536-id chunk as whichever of three encodings is smallest for that chunk — and past 4,096 ids in a chunk, 6.25% of it, the winner is a flat bit array. Byte for byte, the same thing you have now. The flat representation is not the alternative we rejected; it is the one this codec picks whenever it is the right answer. The figure below is that choice being made.
You stop paying where it is wrong
A sparse cohort in Redis still costs the whole span. Here a chunk nobody wrote to does not exist, and a thinly-populated one is stored as a list instead. Measured against the best fixed representation: 543× smaller on a contiguous range, 63× smaller on clustered runs, 1.88× smaller on scattered ids — and 1.02× larger on the one shape built to favour a flat array.
What genuinely does not carry over: the bytes. A .crbm object is not a flat bit array, so anything that reads your Redis bitmap's raw string — a job that GETs the key and indexes into it, a byte-for-byte backup, another service that already understands that layout — will not read ours. Raw bit-position import and export is a credible feature and is not built; if you need it, that is worth telling us, because it decides whether it gets built. Everything reached through bitmap operations transfers today; everything reached through the bytes does not.
How a chunk picks its representation
Four stages on the write path. The measurement in stage 03 is the whole mechanism: three encodings are costed for the same chunk and the smallest one is what gets stored.
01 Split
1_234_567_890
- key0x4996
- rem0x02D2
16 bits + 16 bits
02 Group
- 0x00002 ids
- 0x000161,904 ids
- 0x49969,001 ids
one chunk holds up to 65,536 ids
03 Choose
- array 17.6 KiB 2 B × 9,001 ids
- bitset 8.0 KiB 65,536 bits, flat
- run 23.8 KiB 4 B × 6,102 runs
smallest encoding wins, per chunk, on write
04 Store
- 0x0000array
- 0x0001bitset
- 0x4996bitset
one segment, mixed containers
The numbers above are a worked example on a stated premise — a chunk holding 9,001 ids across 6,102 runs — not a measurement of your data. Every cost is the arithmetic beside it, so you can check all three. The demo is where the measured figures live.
Where it stops paying
Adaptive containers do real work on sparse or clustered ids. They do nothing for you in two cases, and one of them is a reason to pick a different flavor rather than a different library.
Uniformly dense ids
If nearly every chunk is dense, every chunk picks bitset and you have paid for a decision engine that always returns the same answer. A plain-bitset flavor was the obvious answer, and we measured it before building it: past roughly 6% density a Roaring chunk already is an uncompressed bitset, so on the workload built to favour it a flat bitset came out 2% ahead — while Roaring won the other shapes by 543×, 63× and 1.88×. It is decided against, not queued.
A native dependency
This flavor wraps CRoaring through roaring-node, so it brings a platform matrix and something to compile. That is the honest cost of choosing this row: a prebuilt exists for common Linux and macOS targets, and anything else — Graviton, an unusual libc, a locked-down build that forbids compilation — compiles from source or does not install. Native addons do load on Deno, Bun and Lambda; what they cannot enter is an isolate runtime such as Cloudflare Workers. Note that today the engine itself does not run there either, for reasons that have nothing to do with the codec.
Sub-millisecond p99
No codec fixes this. A membership check that misses the cache costs one ranged GET against object storage, where a RAM store costs a memory read. Use Redis.
Very small segments
A few thousand ids fit in a single cache entry anywhere. The tiering, the generation bookkeeping and the key alignment are all overhead you do not need until a segment stops fitting in memory.
Six lines, no configuration.
The container choice needs nothing from you, and neither do the memory drivers. This runs as written.
import { CloudRoaring, MemoryStorage }
from '@cloudbitmaps/roaring';
const store = new CloudRoaring({ storage: new MemoryStorage() });
// the whole set, as one immutable generation
await store.load({ segment: 'high-value-shoppers' },
[75, 99_999, 1_234_567_890]);
await store.segment('high-value-shoppers').has(1_234_567_890); // true