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?
answer
- bitmaps are strings; TYPE says 'string'
- offset 0 = most significant bit of byte 0
- SETBIT returns the OLD bit → first-time-today check
- 50M bits ≈ 6 MB per day
- highest offset sets allocation, not number of set bits
basics
~20 sA 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 sBitmaps 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> 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 MBgo deeper
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.
Do the memory arithmetic out loud, explain that SETBIT returns the previous bit, and name the sparse-offset allocation trap.
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.
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.
saying these in an interview costs you the question
- 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