How Redis Cut Memory Usage for Large Bitmaps with Native Roaring Compression

#redis #bitmaps #compression #c

Why Bitmap Compression Matters in Redis

Bitmaps are a fundamental data structure in Redis, used for everything from user tracking to analytics. Yet, before this change, Redis stored bitmaps as plain strings. This meant memory usage scaled with the highest bit set, not the number of bits actually set — a costly inefficiency for large or sparse bitmaps.

If you’ve ever worked with large bitmaps in Redis, you know how quickly memory can balloon. This article dives into how Redis introduced native compressed bitmaps using the Roaring bitmap format to solve this problem, cutting memory usage dramatically without sacrificing performance or compatibility.

The Problem: Dense Bitmap Storage Wastes Memory

Redis represented bitmaps as strings where each byte corresponds to 8 bits, stretching out to the highest set bit. Imagine a bitmap with just a few bits set near the end of a large range — Redis still allocated memory for all bits up to that point.

This dense representation is simple but inefficient for sparse or very large bitmaps. It results in wasted memory and can degrade performance due to increased memory pressure.

The Root Cause: Lack of Compression or Sparse Representation

The core issue was that Redis’s bitmap type had no concept of compression or sparse storage. It was a flat, byte-array representation:

Memory allocated proportional to the highest bit offset.
No differentiation between set and unset bits beyond the raw string.
No ability to store bitmaps compactly when bits are few and far apart.

This meant that even a bitmap with a few scattered bits set could consume megabytes of memory if the highest set bit was large.

The Solution: Integrating Roaring Bitmaps into Redis

The PR introduces a new native bitmap type in Redis backed by the CRoaring library, a high-performance C implementation of Roaring bitmaps.

What Are Roaring Bitmaps?

Roaring bitmaps are a compressed bitmap format designed for fast operations and efficient memory usage, especially with sparse or clustered bitmaps. They achieve compression by splitting the bitmap into chunks and encoding each chunk using the most efficient method (arrays, bitmaps, or runs).

How Redis Uses Roaring Bitmaps

New Object Type: A new Redis object type OBJ_BITMAP with encoding OBJ_ENCODING_BITMAP_ROARING is introduced.
Vendored CRoaring: The PR vendors the CRoaring library to handle bitmap operations internally.
Config Option: A new configuration bitmap-default-roaring allows automatic creation and conversion to Roaring bitmaps on writes.
Command Compatibility: Bit commands transparently work on both the old string bitmaps and new Roaring bitmaps, preserving existing semantics.
Persistence: A new RDB type is added, leveraging CRoaring’s compact serialization format for efficient persistence and loading.

Technical Integration Details

The integration required careful handling to maintain compatibility:

Type System: Redis’s type system was extended to distinguish between string and Roaring bitmap encodings.
Command Layer: Bit commands like SETBIT, GETBIT, and bitwise operations were adapted to dispatch to the appropriate underlying representation.
Conversion Logic: When bitmap-default-roaring is enabled, writes create Roaring bitmaps by default. Existing string bitmaps can be converted lazily or eagerly.
Persistence: The RDB format was extended to store Roaring bitmaps efficiently, avoiding the overhead of raw strings.

The Takeaway: Compression Requires Thoughtful Integration

This change shows the power of choosing the right data structure for the job. Roaring bitmaps dramatically reduce memory usage for sparse or large bitmaps while preserving exact semantics.

However, integrating compressed data structures into an existing system is non-trivial. It requires:

Extending type systems to support multiple encodings.
Ensuring command compatibility and seamless user experience.
Supporting persistence formats that respect compression.

For engineers building high-performance systems, this PR is a great example of balancing new data structures’ benefits with the complexity of integration.

This article is based on the Redis PR "Redis native compressed bitmaps (redis-roaring)". Read the full breakdown on nossletter.tech.

Originally published on Nossletter.

DEV Community