redis/redis #15331

Roaring Bitmaps
in Redis

Native compressed bitmaps in Redis core:
the design, the review, and what it unlocks.

Antonio Viggiano · redisroaring.com

October 8, 2026

The same command, two representations

Redis today: bitmap as a string

127.0.0.1:6379> SETBIT clicks 4000000000 1
(integer) 0
127.0.0.1:6379> MEMORY USAGE clicks
(integer) 536870944   # 512 MiB

with bitmap-default-roaring yes

127.0.0.1:6379> SETBIT clicks 4000000000 1
(integer) 0
127.0.0.1:6379> MEMORY USAGE clicks
(integer) 313   # 313 bytes

Same command, same reply.

1,744×

less memory on real census data

19×

faster BITCOUNT on sparse data

13×

faster BITOP on census data

Agenda

What we'll cover

01 Who am I

Security Researcher, redis-roaring maintainer, Database engineer.

02 The problem

Why string bitmaps are expensive for sparse data, and how Roaring bitmaps fix it.

03 Design decisions

Type vs encoding, determinism, replication, persistence, and what changed during review.

04 Capabilities

Memory savings and the BelugaDB workload.

05 Under the hood

A closer look at key conversion.

06 Security & performance

Testing, fuzzing, bugs found, and benchmark results.

~45 minutes of content · 15 minutes Q&A

01

Who am I

Fuzzing, redis-roaring, BelugaDB.

Who am I

Antonio Viggiano

2026–present · Senior Security Researcher, Monad Foundation.Applying fuzzing and AI to catch bugs in cryptocurrency projects.
2017–present · Author of redis-roaring, the Roaring bitmap module for Redis.Now being upstreamed into Redis core: redis/redis#15331.
2014–2017 · Co-founder, BelugaDB: high-performance, column-oriented analytics data store in C.Columnar storage, bitmap indexes, real-time segmentation queries over terabytes.
2014 · Software Engineer Intern, RevMob: Latin America's largest mobile ad network.Managed cloud architecture with thousands of ad servers.

Who am I · BelugaDB

How BelugaDB was born

RevMob, Latin America's largest mobile ad network

5,000

transactions per second

Our MongoDB setup could not handle the workload.
Commercial alternatives were too expensive.
We decided to spin out and build BelugaDB.

Who am I · BelugaDB

OLAP queries are bitmap algebra

events stream

{"country":"Brazil","gender":"male","action":"click"}
{"country":"United States","gender":"female","action":"impression"}
{"country":"Brazil","gender":"female","action":"click"}
{"country":"United States","gender":"male","action":"click"}
{"country":"United States","gender":"female","action":"install"}
{"country":"United States","gender":"female","action":"impression"}
{"country":"Israel","gender":"male","action":"impression"}
{"country":"United States","gender":"female","action":"install"}

Each column value becomes a bitmap over row IDs; the WHERE clause is boolean logic (AND / OR / NOT) over those sets.

row	country	gender	action
0	Brazil	male	click
1	United States	female	impression
2	Brazil	female	click
3	United States	male	click
4	United States	female	install
5	United States	female	impression
6	Israel	male	impression
7	United States	female	install

the canonical OLAP query

SELECT COUNT(*) FROM events
WHERE country = 'Brazil' AND action = 'click'
→ 2   # rows 0 and 2

Who am I · CONCISE

Some background: CONCISE by hand (circa 2015)

CONCISE: Compressed 'n' Composable Integer Set (Colantonio & Di Pietro, 2010), a run-length encoded bitmap.
Literal words store bits directly. Fill words represent long runs of 0s or 1s.
Implemented in C from the paper. Set operations merge two compressed streams.

✅ What it did well

Excellent compression for sparse and clustered data; set algebra without decompressing.

⚠️ The limitation

No random access: reading bit N means scanning from the start. More data means more scanning.

Who am I · redis-roaring

Some background: Porting to CRoaring (circa 2016)

Ported from CONCISE to Roaring bitmaps. The founding paper reports intersections up to 900× faster than RLE bitmaps.
May 2017: published redis-roaring, wrapping CRoaring in Redis commands (R.SETBIT, R.BITCOUNT, …).
385 ★ · production use · census benchmarks on every push: O(1) parity, up to 8× faster on O(N) ops.

💡 Why go native

Compression through the existing bitmap API, with Redis handling persistence. No separate R.* commands, and existing workloads get cheaper.

02

The problem

What bitmaps are used for, and why Redis needs compressed bitmaps.

The problem

Redis bitmaps today: commands over a string

There is no bitmap type: a bitmap is a string, addressed bit by bit.
Seven command families: SETBIT · GETBIT · BITCOUNT · BITPOS · BITOP · BITFIELD · BITFIELD_RO
Writing bit N allocates (N>>3)+1 bytes: the string covers the highest offset ever touched.
Optimal for dense data; wasteful for sparse data.

redis-cli

127.0.0.1:6379> SETBIT b 7 1
(integer) 0
127.0.0.1:6379> TYPE b
string
127.0.0.1:6379> GET b
"\x01"   # it really is just bytes

The problem → the fix

Inside a Roaring bitmap

The problem → the fix

Adoption elsewhere

Introduced by Chambi, Lemire, Kaser & Godin (2014); a cross-language spec with implementations in every major ecosystem.
CRoaring, the reference C implementation: vectorized kernels, a portable serialization format, continuously fuzzed.
Redis vendors CRoaring, inheriting a widely deployed and continuously fuzzed format instead of inventing a new one.

Lucene · Elasticsearch · Solr

Apache Druid

ClickHouse

Apache Spark · Hive

Apache Pinot · Doris · Kylin

InfluxDB

Netflix Atlas

Google Procella (YouTube)

YDB · StarRocks · Redpanda

Iceberg · Pulsar · Flink · …

Roaring bitmaps are the standard structure behind inverted indexes and segmentation engines.

03

Design decisions

The decisions that shaped the PR.

Design decisions

Goals & guardrails

Zero breaking changes. Every bitmap command returns the same values, errors, and edge-case semantics on both representations.
No new API to learn. The existing seven command families are the entire public surface.
Opt-in. Gated behind bitmap-default-roaring (default no); off means behavior mirrors upstream Redis exactly.
Same limits. Offsets stay bounded by proto-max-bulk-len × 8 bits: at defaults the highest valid offset is 2³² − 1, the historical string-bitmap limit.

🎯 Built for adoption

Zero breaking changes means workloads that stay on the bitmap commands adopt compression with a config flip and no code changes. It also gives redis-roaring module users a portability path into core, with one command surface everywhere.

Design decisions · the object model

A type, not an encoding

Original proposal: a transparent string encoding (like listpack → hashtable).
But encodings must be invisible, and a compressed bitmap cannot serve GET / APPEND / SETRANGE without materializing gigabytes.
Decision: a new bitmap object type. String commands return WRONGTYPE, the same behavior as every other non-string type.

"Define a 'real' bitmap data type instead of relying on String."LiorKogan

measured on the PR build

127.0.0.1:6379> TYPE clicks
bitmap
127.0.0.1:6379> OBJECT ENCODING clicks
"bitmap-roaring"
127.0.0.1:6379> GET clicks
(error) WRONGTYPE Operation against a key
holding the wrong kind of value
127.0.0.1:6379> BITCOUNT clicks
(integer) 1   # bitmap commands work unchanged

Design decisions · what changed

Other options we considered

🔀 A transparent string encodingconsidered

Cannot serve GET / APPEND without expanding the bitmap.

✅ A first-class bitmap typelanded

WRONGTYPE makes the boundary explicit.

📏 32-bit Roaring, hard 512 MB capconsidered

Too restrictive for some redis-roaring users.

✅ 64-bit internals, bounded surfacelanded

roaring64 inside, the same public limits as string bitmaps.

"I'm ok with 32-bit only, at least as a first step."LiorKogan

light panels: designs we considered and moved away from

Design decisions · conversion

How a key becomes Roaring

Path	When	Notes
SETBIT / BITFIELD write	config on	new keys created Roaring; existing string bitmaps convert in place, preserving TTL & module metadata
BITOP	any config	≥ 1 Roaring source → Roaring destination; with config on, all-string sources also produce Roaring
RESTORE / MIGRATE	payload is Roaring	DUMP payloads carry the representation
replication / AOF / RDB	master decides	replicas never re-derive the decision (next slide)

CONFIG SET bitmap-default-roaring yes

🔒 Never implicit

With the config off, bitmap writes keep creating plain strings. The default applies on the primary, when the write can propagate to both AOF and replicas.

↩️ No silent demotion

Roaring keys are never demoted back to strings. The type boundary is strict and one-way in v1.

Design decisions · determinism

The determinism problem

Nondeterminism is acceptable for invisible encoding decisions, never for WRONGTYPE-visible type decisions.

Design decisions · propagation

What actually crosses the wire

Internal commands: BITCONVERT and BITROAROP; regular clients get unknown command.
SETBIT/BITFIELD conversion and write are wrapped in MULTI/EXEC and apply atomically.
Config-selected BITOP results use BITROAROP: direct native storage, with the same notifications.
Replicas and AOF replay the stream verbatim; a replica with the config off still builds the Roaring key.
Writes to Roaring values and BITOP with Roaring sources propagate as plain commands.

replication / AOF stream, asserted by the test suite

# SETBIT that creates or converts a key
MULTI
BITCONVERT clicks
SETBIT clicks 65536 1
EXEC

# BITOP: config selects a Roaring result
BITROAROP OR dest src1 src2

Design decisions · what changed

Other propagation designs we considered

RESTORE … REPLACE KEEPMETADATA

Ship the converted value as a blob. Deterministic, but preserving metadata needed a specialized option.

BITOP + BITCONVERT in MULTI/EXEC

Replay BITOP, then convert its result. But replicas briefly saw a string and emitted different notifications.

internal BITROAROP ✓

Store the native result directly: same notifications and callbacks. Public BITOP syntax stays unchanged.

light panels: designs we considered and moved away from

Design decisions · what changed

Challenges of AI-assisted code

Aug 21

Agreed replication design merges: BITOP + BITCONVERT, duplicate command deleted.

Aug 21, one hour later

An automated review-fix PR for unrelated bot findings silently re-adds the rejected command. CI stays green.

Aug 22

sundb's review: "Why this command come back again?"

Aug 23

Reverted byte-identical to the agreed design; replay tests added.

Sep 22–28

New notification tests justify a deliberate return: BITROAROP.

🤖 Lessons

Coding agents helped ship many tests, but also reintroduced rejected designs that only design-level review caught.

Design decisions · persistence

Persistence: the portable format

Roaring keys persist as CRoaring's portable serialization: a cross-language spec, not a Redis-private blob.
Prefixed by the logical byte length. Roaring stores only set bits, so "string length" semantics (trailing zeros, ranges) must be carried alongside.
Dedicated RDB type id (RDB_TYPE_BITMAP) plus a version bump: old tools fail cleanly instead of misreading.
Same encoding everywhere: RDB, DUMP/RESTORE, full sync, AOF preamble.
trade-off RDB consumers can no longer treat bitmaps as byte arrays; the format is documented & versioned.

Design decisions · what changed

Other persistence formats we considered

💥 The blocker that turned it back

Saving raw bytes materializes the full logical range, and on replicated paths the "length ≤ proto-max" assumption does not hold. One set bit at offset 2⁴⁰ means ~128 GiB materialized at save time.

📐 The lesson

A compressed type must stay compact on every path: command replies, replication, RDB, DUMP. And a serialization format is a commitment to external tooling, not just to Redis.

Design decisions · bounded edges

Bounded worst cases

💣 BITOP NOT amplification

src/bitroar.h, the minimum budget (trimmed)

/* BITOP NOT fills every missing 2^16-bit Roaring
 * chunk in the logical range. Bound that allocation
 * amplification rather than the source's byte length:
 * dense sources above 512 MiB can remain cheap to
 * complement, while a sparse source cannot make one
 * command materialize an unbounded number of chunks.
 * This is a floor: the effective limit grows with
 * proto-max-bulk-len to cover client-created values. */
#define BITROAR_BITOP_NOT_MAX_MISSING_CHUNKS (1ULL << 16)

A flat 512 MB cap was rejected, since strings can legitimately hold that. The 65,536-chunk floor grows with proto-max-bulk-len, including BITFIELD edge cases. The check costs O(resident containers).

🚪 Dense reads are debug-only

Dense materialization of a Roaring key is confined to a debug path (DEBUG BITMAP-RAW), and even that respects proto-max-bulk-len. A sparse bitmap cannot produce a huge reply through a normal command.

📏 64-bit capable, string-parity bounded

Internals are 64-bit (roaring64), but the exposed offset range stays exactly what string bitmaps allow. Raising the limit is a separate, deliberate decision.

Design decisions · scope

What v1 deliberately leaves out

Guiding rule: ship the smallest reviewable change that delivers the value. Every extra knob multiplies the review and test matrix.

Cut	Why
BITMAP CONVERT (public)	covered by the config; replication uses the internal BITCONVERT primitive
conversion thresholds / heuristics	threshold decisions depend on allocator state and cannot be replayed deterministically
new roaring-only commands future proposals	BITSETARRAY: bulk integer load BITGETBITS: batch membership BITSETRANGE: fill a range
64-bit offsets at the surface	internals ready; raising the limit is its own compatibility discussion
demotion (roaring → string)	a one-way boundary keeps the model explainable; revisit with evidence

04

Capabilities

Memory savings and the BelugaDB workload.

Capabilities · memory

Memory usage on real datasets

string bitmapRoaring bitmapMEMORY USAGE, live allocator · log scale

census1881

896 KiB → 526 B (1,744×)

wikileaks-noquotes

192 KiB → 384 B (512×)

synthetic sparse

3.0 MiB → 25 KiB (122×)

synthetic clustered

512 KiB → 13 KiB (39×)

weather_sept_85

224 KiB → 20 KiB (11×)

synthetic dense

160 KiB → 161 KiB (+0.6%)

Sparse: pay per member, not per address. Dense: ≈ parity; the overhead when compression cannot help is small.
Compression survives RDB, AOF, replication, and MIGRATE.

Capabilities · algebra

The BelugaDB workload, now a test in Redis core

tests/unit/bitroar.tcl · fork PR #337 merged

# The ad-tech dataset from the start of the talk,
# one bitmap per value:
country:brazil        {0 2}
country:united-states {1 3 4 5 7}
country:israel        {6}
gender:male           {0 3 6}
gender:female         {1 2 4 5 7}
metric:clicks         {0 2 3}
metric:impressions    {1 5 6}
metric:installs       {4 7}
universe              {0 1 2 3 4 5 6 7}

BITOP mixes string and Roaring operands freely. All 8 operators:
AND · OR · XOR · NOT · DIFF · DIFF1 · ANDOR · ONE

the test's query: "female users who clicked but did not install"

# Extend the length beyond the universe
SETBIT metric:installs 8 0
BITOP NOT raw metric:installs
# a NOT must be bounded by the universe
BITOP AND not-installs universe raw
BITOP AND result gender:female metric:clicks
          not-installs
# result = {2}: the Brazilian female clicker

🌐 The universe pattern

Complement queries ("users NOT from the US") need a bitmap of all valid rows to bound the NOT. Building that universe efficiently is what motivated the SETFULL discussion; range fills are a proposed extension.

Capabilities · operations

Observability & the module contract

TYPE → bitmap · OBJECT ENCODING → bitmap-roaring: always inspectable.
Keyspace notifications: new class b for bitmap events; conversion fires type_changed under class c, deliberately not in A, so listeners opt in.
Modules: REDISMODULE_KEYTYPE_BITMAP + NOTIFY_BITMAP; conversion is in-place: TTL & metadata preserved, no overwritten event, no unlink callbacks.
Ops toolbox: DEBUG BITMAP-RAW (bounded), DEBUG DIGEST, bitmap-size histogram in INFO KEYSIZES, new bitmap ACL category.

watching conversions

127.0.0.1:6379> CONFIG SET notify-keyspace-events Ebc
OK   # b = bitmap events, c = type_changed
127.0.0.1:6379> SUBSCRIBE __keyevent@0__:type_changed
# fires when a string converts to a Roaring bitmap

127.0.0.1:6379> DEBUG BITMAP-RAW clicks
"\x00\x00..."  # bounded by proto-max-bulk-len

05

Under the hood

A closer look at key conversion.

Under the hood · source

Converting a key safely

src/bitops.c · SETBIT conversion (condensed)

if (transition) {
    /* 1. Queue conversion before the write */
    bitroarPropagateConvert(c, c->argv[1]);

    /* 2. Convert and notify listeners */
    bitroarConvertKey(c, c->argv[1], o, link);

    /* 3. Look up the key again */
    link = NULL;
    o = lookupKeyWriteWithFlags(c->db, c->argv[1],
                                LOOKUP_NOTOUCH);
    ...
}

1 Queue the conversion

Replicas must convert the key before replaying the write.

2 Convert and notify

Code listening for the change can replace or delete the key.

3 Look up the key again

Continue from the current value. The old reference may no longer be valid.

06

Security & performance

Testing, fuzzing, the bugs found along the way, and benchmark results.

Security & performance · testing

Testing against the string implementation

The string implementation is the specification. The oracle suite runs every scenario in both modes; only TYPE may differ.

Differential fuzz: random strings loaded as both representations; all 8 BITOP ops compared on replies, dest bytes, and source immutability.
200+ bitmap test blocks across four suites (bitroar, bitroar-oracle, bitops, bitfield).
Infrastructure parity: replication-stream assertions, full-resync digests, corrupt dumps, defrag, cluster MIGRATE, keyspace events, AOF.
93.8% line coverage on the core implementation file (Codecov, July 2026).

Security & performance · fuzzing

Fuzzing the deserialization paths

Threat model: hostile serialized payloads via RESTORE, RDB load, or the replication stream.
Validation is unconditional: exact-length framing, safe deserializer, CRoaring internal_validate, and highest-bit-fits-length, on every load, not just sanitize-dump-payload.
Corrupt-dump fuzzer: seeds 5 Roaring shapes and flips bytes inside the portable blob; the server must reject, never crash. Run with sanitize both on and off.
Module repo: 10 libFuzzer targets (ASan+UBSan); a manifest maps every command to a fuzzer, enforced in CI + daily cron.
Upstreaming the practice: a core fuzzing scaffold for Redis itself, proposed as its own PR.

the required behavior

# hostile payload, any sanitize setting
127.0.0.1:6379> RESTORE k 0 "\x21...corrupted..."
(error) ERR Bad data format
# the payload is rejected, not parsed

Security & performance · findings

Bugs found during development

🐛 BITOP self-target use-after-free

A review-requested restructure moved operand cleanup after the keyspace store; BITOP AND k k on an empty Roaring key freed an operand still in use. Caught the same day; regression test added.

💥 Event-ordering segfault

Conversion once serialized the value after the notification path invalidated the pointer, calling createDumpPayload(NULL). Rule extracted: dump before you notify. Caught by the local test battery before any push.

🧟 Defrag pointer bugs

Bitset relocation computed an offset from freed storage; fixed offset-first, verified under ASan/UBSan. And CRoaring's ART node table leaves slot 0 uninitialized by design, so defrag walks are bounded to typecodes 1–5; otherwise the defrag allocator receives uninitialized pointers.

⬆️ Fixed upstream in CRoaring

Review of the vendored library found the non-atomic refcount decrement comparing the pointer instead of the value, so the last reference was never released. Fixed upstream in CRoaring #859 (Aug 2026). Redis itself was unaffected.

Security & performance · benchmarks

Latency on real data (census1881)

GETBIT

1.02× 34→34 µs

BITPOS

1.1× 40→35 µs

BITCOUNT

1.9× 68→36 µs

BITOP AND

5.2× 355→68 µs

BITOP XOR

10.3× 714→69 µs

BITOP OR

12.6× 860→68 µs

BITOP ONE

13.6× 950→70 µs

Geomean across all workloads (vs string): point/count/scan 0.455× · algebra 0.305× the latency.

vs the module: ≈ parity on commands, and 21× faster AOF rewrite. Moving from the module to core does not cost performance.

bars = speedup factor, core Roaring vs string · three-way benchmark posted on the PR, July 2026 · real dataset, 5 samples/workload

Security & performance · regressions

Where it is slower

Workload	vs string	Context
mixed string ↔ roaring BITOP	30–40× slower	the one that matters: conversion runs inside the measured path; disappears once keys are converted, and a batch-conversion path is a natural next step
DUMP/RESTORE sparse native	≈26% perf	one-off load and migration operations; known serialization headroom
sparse key built via SETBIT	≈16% perf	one-off ingest; the proposed bulk-load command removes it
dense all-native BITOP AND	23 vs 7 µs	µs-scale and near run variance; not the workload compression targets
dense data memory	+0.6%	parity by design; compression cannot help dense data

July 2026 measurements. Mixed-input conversion has since changed; current-head ratios need a new benchmark.

Wrapping up

Where we are

Jun 2

redis/redis#15296: proposal issue opened

Jun 11

#15331 opens as draft

Jul 18–20

Ready for review · three-way benchmark posted

Aug

Persistence format settles · CRoaring fix lands upstream

Oct 5

329 / 336 threads resolved · conflict-free · coverage check running · targeting Redis 8.12

Open: final maintainer review rounds.
Docs: redis/docs#3715, approved; branch conflicts remain.
Benchmarks: bitmap write-path specs landed in redis-benchmarks-specification.
v2 conversation: the roaring-only command surface, after v1 ships.

🙏 Thanks

Reviews & design: sundb, LiorKogan, moticless, oranagra.

Coordination & planning: yaacov.hazan, eyal.boumgarten, bosmat.tuvel, pieter.

Wrapping up

Three things to remember

1

Same API, compressed engine

No new public commands. Flip bitmap-default-roaring and a sparse key drops from 512 MiB to 313 bytes, measured.

2

Determinism is the design

Types are visible, so the master decides once. BITCONVERT and BITROAROP carry that decision to replicas.

3

Review made it better

17 tracked decisions, several reversed during review. Replication evolved again to preserve notifications. The result is simpler than the first draft.

Thank you

Questions?

redis/redis #15331 · redisroaring.com · github.com/aviggiano

Antonio Viggiano · Roaring Bitmaps in Redis

Roaring Bitmapsin Redis

The same command, two representations

What we'll cover

01 Who am I

02 The problem

03 Design decisions

04 Capabilities

05 Under the hood

06 Security & performance

Who am I

Antonio Viggiano

How BelugaDB was born

OLAP queries are bitmap algebra

Some background: CONCISE by hand (circa 2015)

✅ What it did well

⚠️ The limitation

Some background: Porting to CRoaring (circa 2016)

💡 Why go native

The problem

Redis bitmaps today: commands over a string

Inside a Roaring bitmap

Adoption elsewhere

Design decisions

Goals & guardrails

🎯 Built for adoption

A type, not an encoding

Other options we considered

🔀 A transparent string encodingconsidered

✅ A first-class bitmap typelanded

📏 32-bit Roaring, hard 512 MB capconsidered

✅ 64-bit internals, bounded surfacelanded

How a key becomes Roaring

🔒 Never implicit

↩️ No silent demotion

The determinism problem

What actually crosses the wire

Other propagation designs we considered

Challenges of AI-assisted code

🤖 Lessons

Persistence: the portable format

Other persistence formats we considered

💥 The blocker that turned it back

📐 The lesson

Bounded worst cases

💣 BITOP NOT amplification

🚪 Dense reads are debug-only

📏 64-bit capable, string-parity bounded

What v1 deliberately leaves out

Capabilities

Memory usage on real datasets

The BelugaDB workload, now a test in Redis core

🌐 The universe pattern

Observability & the module contract

Under the hood

Converting a key safely

1 Queue the conversion

2 Convert and notify

3 Look up the key again

Security & performance

Testing against the string implementation

Fuzzing the deserialization paths

Bugs found during development

🐛 BITOP self-target use-after-free

💥 Event-ordering segfault

🧟 Defrag pointer bugs

⬆️ Fixed upstream in CRoaring

Latency on real data (census1881)

Where it is slower

Where we are

🙏 Thanks

Three things to remember

Same API, compressed engine

Determinism is the design

Review made it better

Questions?

Roaring Bitmaps
in Redis