Bitmaps, HyperLogLog, and the Sketches

Topics Covered

A Bitmap Is a String Seen Differently

The commands, and the shape they imply

Setting a high offset allocates everything below it

The size limit, and what it means for the subject space

The pattern bitmaps were made for

Ranges, and the flag that was missing

BITOP, and the cost of combining

The sparse case, and how it goes wrong

Operational notes

There is no bitmap type in Redis. There is a set of commands that treat a string as an array of bits, and that is the whole of it, which means everything from the strings lesson still applies: the encoding rules, the memory arithmetic, the 512 megabyte cap and the fact that TYPE reports a string.

The commands, and the shape they imply

SETBIT key offset value sets the bit at a zero-based offset to 0 or 1 and returns the previous value. GETBIT reads one. BITCOUNT counts the set bits, over the whole string or a range. BITPOS finds the first bit with a given value. BITOP combines several strings with AND, OR, XOR or NOT into a destination key. And BITFIELD treats the string as packed integers, which is the next section.

Bits are numbered from the most significant bit of the first byte, so offset 0 is the high bit of byte 0 and offset 7 is the low bit of byte 0. This ordering surprises people who expect the natural little-endian reading, and it matters only when interoperating with a bitmap produced elsewhere, where getting it wrong produces a bitmap that is correct and byte-reversed.

Setting a high offset allocates everything below it

SETBIT key 1000000 1 on an empty key creates a string of 125,001 bytes, because the bit at offset one million needs a string long enough to contain it and everything before it is zero-filled. The allocation is immediate and is proportional to the offset, not to the number of bits set.

That is the single most important property of a bitmap, and it cuts both ways. For a dense population it is ideal: one bit per subject with no per-subject overhead at all, which is 125 kilobytes for a million subjects and 1.25 megabytes for ten million. For a sparse population it is catastrophic: setting one bit at offset 100 million allocates 12.5 megabytes to record one fact.

A bitmap is a string read one bit at a time, numbered from the most significant bit of the first byte. Setting a bit at a high offset allocates the whole string up to it, so the memory follows the largest offset rather than the number of bits set.

The size limit, and what it means for the subject space

A string caps at 512 megabytes, so a bitmap holds at most about 4.29 billion bits and the maximum offset is 2 to the 32 minus 1. That is a generous subject space and it is a hard ceiling: there is no bitmap spanning more than that, so a design keyed by an identifier larger than 4 billion needs the identifier mapped down to a dense range first.

That mapping is the usual practical obstacle. A bitmap wants consecutive small integers as its subjects, and real identifiers are rarely that: a UUID cannot be an offset at all, and a numeric identifier with gaps wastes a bit per gap. The standard answer is a dense internal sequence allocated with INCR and a mapping held in a hash, which is one extra lookup per operation and is the price of using bitmaps at all.

The pattern bitmaps were made for

Daily active users is the canonical example and shows every property at once. One bitmap per day, keyed by the date, with a bit per user identifier. Marking a user active is one SETBIT. The day's active count is one BITCOUNT. Users active on both of two days is BITOP AND into a temporary key followed by BITCOUNT. Users active on any day of a week is BITOP OR across seven keys.

For ten million users that is 1.25 megabytes per day, 456 megabytes per year, and a weekly unique count is seven inputs of 1.25 megabytes combined in a few milliseconds. The equivalent with sets is ten million members per day at tens of bytes each, so hundreds of megabytes per day rather than per year, and a weekly union is a set operation over seventy million members. The factor is two or three orders of magnitude, which is why the pattern survives despite the identifier mapping being a nuisance.

Ranges, and the flag that was missing

BITCOUNT key start end originally counted over a byte range, which is awkward when the interesting boundary is a bit rather than a byte. Redis 7.0 added a BIT option, so BITCOUNT key 0 999 BIT counts the first thousand bits, and BYTE remains the default for compatibility.

BITPOS gained the same option. The most common use of BITPOS is finding a free slot in a dense allocation bitmap, BITPOS key 0, which returns the first zero bit and is a constant-ish operation that replaces scanning. The caveat worth knowing is that BITPOS key 0 on a string of all ones returns the first bit past the end of the string rather than -1, because the string is conceptually followed by zeros, while a range-limited search returns -1 when nothing matches. That asymmetry is documented and is a real source of off-by-one bugs.

BITOP, and the cost of combining

BITOP is proportional to the length of the longest input, and it writes a destination key of that length. Shorter inputs are treated as zero-padded, which is the correct semantics and means combining a bitmap of a million bits with one of a billion costs the billion.

Two practices follow. Keep bitmaps that will be combined the same length, which they naturally are if they are keyed by date over the same subject space. And remember that the destination is a real key consuming real memory, so a weekly aggregation that writes a temporary key should delete it or give it a short TTL, and a dashboard computing several such aggregations per refresh should cache the results rather than recomputing them.

Interview Tip

BITOP writes a destination key as long as its longest input, so an aggregation across seven daily bitmaps of ten million users creates a 1.25 megabyte key every time it runs. Set a short TTL on the destination in the same script, or delete it after reading the count. A dashboard that recomputes a weekly union on every refresh and never cleans up is a slow memory leak that looks like growth in the dataset.

The sparse case, and how it goes wrong

The failure mode is a bitmap keyed by something sparse. A bitmap of which product identifiers were viewed today, where product identifiers run to 500 million but only 10,000 products were viewed, allocates 62 megabytes to record 10,000 facts, where a set would use perhaps half a megabyte.

The arithmetic that decides it is simple: a bitmap costs one bit per unit of the identifier space, and a set costs roughly 50 to 80 bytes per member actually present. So a bitmap wins when the fill rate exceeds roughly one in 500; below that, a set is smaller. That single ratio settles the choice, and it is worth computing rather than assuming, because the intuition that bitmaps are always compact is wrong by orders of magnitude in the sparse case.

A bitmap costs one bit per unit of identifier space and a set costs 50 to 80 bytes per member present, so the crossover is a fill rate of about one in 500. Below it a set is smaller, and the intuition that bitmaps are always compact is wrong by orders of magnitude.

Operational notes

Three things to carry. A bitmap is a string, so it has one TTL for the whole thing, which suits the one-key-per-day pattern exactly and suits nothing per-subject. A large bitmap is a large key with the usual consequences, though 1.25 megabytes is small by large-key standards so this rarely bites.

And SETBIT at a high offset on an existing key can reallocate and grow the string, with the doubling behaviour from the strings lesson, so a bitmap written in increasing offset order grows incrementally while one written in a random order allocates its full size on the first high write. Pre-sizing with a single SETBIT at the maximum offset is a legitimate trick when the size is known, because it makes the allocation happen once at a predictable moment rather than during traffic.