Flavors · roaring · shipped v0.4.1
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. The bitset flavor will offer the flat bitset on purpose — for dense id spaces it is the right shape, and it needs no native dependency.
| 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. |
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 because Redis is one of our warm drivers, you can have the adaptive one inside Redis — the node then holds compressed chunk deltas instead of an uncompressed bit array, and your history stays in cold object storage rather than in RAM.
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. That is what @cloudbitmaps/bitset is for — same engine, no native dependency.
A native dependency
This flavor wraps CRoaring through roaring-node, so it brings a platform matrix and something to compile. On an edge runtime that is disqualifying, and it is the honest cost of choosing this row.
Sub-millisecond p99
No codec fixes this. A RAM store answers a single membership check 10–20× faster than any warm-tier round trip. Use Redis.
Very small segments
A few thousand ids fit in a single cache entry anywhere. The tiering, the compaction 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, MemoryWarmDriver, MemoryColdChunkSource } from '@cloudbitmaps/roaring';
const store = new CloudRoaring({
warm: new MemoryWarmDriver(),
cold: new MemoryColdChunkSource(),
});
const vips = store.segment('high-value-shoppers');
await vips.addMany([75, 99_999, 1_234_567_890]);
await vips.has(1_234_567_890); // true