skip to content

Redis has no dedicated bitmap type — SETBIT, GETBIT and BITCOUNT operate on ordinary strings. How does that work, how much memory does a daily-active-user flag for 50 million user ids cost, and what is the trap when the bit offsets are sparse?

level: middleimportance: should knowfreq 42%

answer

  1. bitmaps are strings; TYPE says 'string'
  2. offset 0 = most significant bit of byte 0
  3. SETBIT returns the OLD bit → first-time-today check
  4. 50M bits ≈ 6 MB per day
  5. highest offset sets allocation, not number of set bits

basics

~20 s

A bitmap is just a string addressed bit by bit. SETBIT key offset 0|1 sets a bit and returns the old one; BITCOUNT counts set bits. 50 million bits is about 6 MB. The trap: setting a high offset allocates every byte below it, so a single sparse id can allocate hundreds of MB.

solid answer

~60 s

Bitmaps are a **view over the string type**, not a separate structure. `SETBIT key offset 0|1` sets the bit at a zero-based offset and returns its previous value; `GETBIT` reads one (missing key or offset beyond the end reads as 0); `BITCOUNT` counts set bits, optionally within a byte range, or a bit range with the `BIT` modifier. Memory is exactly one bit per offset: 50,000,000 bits ≈ 6.25 MB for a whole day's active-user flags — cheap enough to keep a key per day for a year. The trap is **density**. Because the underlying string is contiguous, setting a high offset zero-fills everything below it: `SETBIT dau:2026-08-14 4000000000 1` allocates 500 MB in one command. So bitmaps only work when the offset space is dense and small — sequential internal user ids, not UUIDs, snowflake ids or hashes. If ids are sparse, map them to a dense sequence first (for example with an INCR-backed id allocator) or use a different structure. Other limits: offsets are capped so the string stays under 512 MB (max offset 2^32−1), and BITCOUNT is O(n) over the scanned bytes.

code

text · 15 lines
text
> SETBIT dau:2026-08-14 8 1     # user id 8 seen today; returns previous bit
(integer) 0
> SETBIT dau:2026-08-14 8 1     # already seen → returns 1, so no double count
(integer) 1
> GETBIT dau:2026-08-14 9
(integer) 0
> BITCOUNT dau:2026-08-14
(integer) 1
> STRLEN dau:2026-08-14
(integer) 2                      # 2 bytes cover ids 0..15

> SETBIT dau:2026-08-14 4000000000 1   # one sparse id ...
(integer) 0
> STRLEN dau:2026-08-14
(integer) 500000001              # ... allocated ~500 MB

go deeper

for a junior

Know that bitmaps are strings addressed by bit, that SETBIT/GETBIT/BITCOUNT are the basic commands, and that one bit per user is very compact.

for a middle

Do the memory arithmetic out loud, explain that SETBIT returns the previous bit, and name the sparse-offset allocation trap.

for a senior

Discuss offset validation as a memory-exhaustion defence, the O(n) cost of BITCOUNT across many day keys, and when a bitmap is the wrong structure because ids are sparse or payloads are needed.

for a principal

Frame it as an id-space design decision: adopting bitmaps commits you to a dense internal identifier and to keeping the analytics workload off the latency-critical path.

## The type that isn't a type Redis exposes no `bitmap` type — `TYPE dau:2026-08-14` on a bitmap answers `string`. The bit commands simply address a string by bit index. Offset 0 is the **most significant bit of byte 0**, offset 7 the least significant bit of byte 0, offset 8 the MSB of byte 1, and so on. That ordering matters if you ever inspect the raw bytes: setting bit 0 gives you the byte `0x80`, not `0x01`. Because it is a string underneath, everything you know about strings applies: the 512 MB size limit (hence a maximum bit offset of 2^32−1), TTLs, DUMP/RESTORE, replication as a normal write. ## The commands - **`SETBIT key offset 0|1`** — sets the bit and returns the bit's *previous* value. That return value is the whole trick behind "first time today" logic: if SETBIT returns 0, this user had not been seen yet in this window, all in one atomic command with no read-then-write race. - **`GETBIT key offset`** — returns the bit; a missing key or an offset past the end returns 0, never an error. - **`BITCOUNT key [start end [BYTE|BIT]]`** — population count. With no range it scans the whole value; with a range it counts within it. The range is expressed in **bytes** by default (negative indexes allowed), and in bits when you append the `BIT` modifier. - **`BITPOS key bit [start [end [BYTE|BIT]]]`** — index of the first 0 or 1 bit, useful for allocating slots ("first free id"). All of these are atomic single commands. ## Sizing the classic use case Daily-active users: one key per day, one bit per user id. - 50,000,000 bits = 6,250,000 bytes ≈ **6.0 MiB** per day. - 365 such keys ≈ **2.2 GiB** — an entire year of exact per-user daily activity in a couple of gigabytes. - Answering "how many were active on the 14th" is one `BITCOUNT` over 6 MB, a low-millisecond operation. Compare that with a set of 50 million member ids, which costs on the order of a gigabyte for a single day. This density is the reason bitmaps exist. ## The sparsity trap The cost model above assumes offsets are packed from 0 upward. The underlying string is contiguous, so **the allocated size is determined by the highest offset you ever set, not by how many bits are set.** `SETBIT k 4000000000 1` on an empty key produces a 500 MB string containing exactly one set bit, in one command — and that command also has to zero-fill and allocate 500 MB, which is a serious latency event, and 500 MB then flows to replicas and into the next snapshot. Practical consequences: - Use **dense, small, sequential internal ids**. If your public identifier is a UUID or a hash, keep a mapping (an `INCR`-backed allocator writing `HSETNX uid:map <uuid> <n>`) and use the dense number as the offset. - **Validate the offset** before calling SETBIT. A user-controlled id passed straight through is a memory-exhaustion vector. - If your population is small but the id space is huge, a set, or a probabilistic cardinality structure when you only need approximate counts, is the correct choice — bitmaps are not. ## Cost of the operations SETBIT and GETBIT are O(1) *except* when SETBIT has to grow the string, where the cost is proportional to the new size. BITCOUNT and BITPOS are O(n) over the bytes scanned — 6 MB is fine on demand, but counting hundreds of large bitmaps in a loop is real work for the server, so restrict the range where you can (`BITCOUNT k 0 999` covers only the first 8000 ids) and consider caching the daily total in a separate counter key once the day is closed. ## What bitmaps are good and bad at Good: boolean attributes over a dense id space — active today, feature flag exposure, consent given, seen this notification, per-slot occupancy. Also good: cheap exact set arithmetic across those flags using bit operators. Bad: anything needing per-member metadata (a bit stores no payload), anything where ids are sparse, and anything requiring iteration over members — you can only scan bit by bit or with BITPOS, so "list the users active today" means walking 50 million offsets. If you need to enumerate, keep the membership in a structure designed for it.

  • How would you count a user only the first time they appear on a given day, without a read-then-write race?
    Use SETBIT's return value: it reports the bit's previous state, so `SETBIT dau:<day> <id> 1` returning 0 means this is the user's first appearance today. Because it is one atomic command, two concurrent requests for the same user cannot both see 0. Increment a separate counter only when the reply is 0.
  • Your user ids are UUIDs. Can you still use bitmaps for daily-active tracking?
    Not directly — a UUID cannot be an offset, and hashing it into a large space would make the bitmap enormous and lossy. Introduce a dense internal id: allocate sequential numbers with INCR the first time you see a UUID and store the mapping, then use that number as the offset. Bitmaps only pay off when the offset space is dense and bounded by your actual population.

Think of a stadium seating chart printed as one long strip of paper: one tick box per seat, in seat-number order. Ticking box number four billion means you first have to print all four billion boxes before it, even if every other seat is empty.

  • Believing memory depends on how many bits are set rather than on the highest offset used
  • Passing an externally supplied id straight into SETBIT as the offset
  • Thinking Redis has a dedicated bitmap type separate from strings
  • Assuming BITCOUNT is O(1) because it 'just counts'
  • Expecting GETBIT beyond the end of the value to raise an error instead of returning 0

context