Bitmaps: One Bit per User

In one line

A bitmap is a string treated as an array of bits, addressed by offset. With dense integer IDs, you can track a yes/no fact for 100M users in 12 MB, count them with BITCOUNT, and combine days with BITOP.

0/6 · 0%

Think of it like this

An attendance register with one tick box per student number. Student 57 is always box 57. Counting who came today is counting ticks, and "came on both Monday and Tuesday" is laying one sheet over the other.

Key ideas

01
Commands: SETBIT key offset 0|1 (returns the previous bit), GETBIT, BITCOUNT key [start end [BYTE|BIT]], BITPOS (first set or clear bit), BITOP AND|OR|XOR|NOT dest src..., and BITFIELD for reading and writing packed integers of any width (for example many 4-bit counters in one key) with overflow control.
02
Memory: a bitmap is as long as its highest set offset: 100M users → 100M bits = 12.5 MB, whether 1 user or 100M users are active. SETBIT key 4294967295 1 (the max offset, 2^32 − 1) allocates 512 MB at once and blocks while doing it.
03
Bitmaps need dense, small integer IDs. With UUIDs or sparse 64-bit IDs, map them to a dense index first (an ID → index table), or use a set or HyperLogLog instead.
04
Complexity: SETBIT/GETBIT are O(1); BITCOUNT and BITOP are O(N) in bytes, fast in practice (BITCOUNT on 12.5 MB takes a few ms) but they do block. For 30-day windows, compute BITOP results in a background job and cache them.
05
Uses: daily and monthly active users, feature flags per user, "has seen onboarding step", per-question answered flags, bloom-like presence for dense IDs, and compact time-series of booleans (one bit per minute of uptime).

Code & diagrams

dau.redisredis

127.0.0.1:6379> SETBIT dau:2026-09-27 1 1
(integer) 0
127.0.0.1:6379> SETBIT dau:2026-09-27 42 1
(integer) 0
127.0.0.1:6379> SETBIT dau:2026-09-28 42 1
(integer) 0
127.0.0.1:6379> SETBIT dau:2026-09-28 100000000 1
(integer) 0
127.0.0.1:6379> BITCOUNT dau:2026-09-28
(integer) 2
127.0.0.1:6379> STRLEN dau:2026-09-28
(integer) 12500001                      # ~12 MB, sized by the highest offset
127.0.0.1:6379> BITOP AND active:both dau:2026-09-27 dau:2026-09-28
(integer) 12500001
127.0.0.1:6379> BITCOUNT active:both      # active on both days
(integer) 1
127.0.0.1:6379> BITOP OR active:any dau:2026-09-27 dau:2026-09-28
127.0.0.1:6379> BITCOUNT active:any       # active on either day
(integer) 3
127.0.0.1:6379> BITFIELD counters INCRBY u4 #10 1 OVERFLOW SAT
1) (integer) 1                          # 4-bit counter number 10, saturating

Interview problem

The problem

Daily active users

Track daily active users for user IDs 1 to 100,000,000, stored as DAU:2026-09-28. Discuss memory efficiency, sparse IDs, bitmap vs set, counting users, and users active on several days.

You're given

User IDs 1..100M, dense
~30M active per day
Show DAU, WAU, 'active 7 days in a row'

The interviewer follows up

How do you get "users active today but not yesterday" (new or returning)?

When it breaks

Using bitmaps with sparse or hashed user IDs

What you see

A single SETBIT with offset 4,000,000,000 allocates ~500 MB and blocks Redis while it zero-fills; memory usage explodes.

Fix & prevent

Only use bitmaps with dense IDs; validate offsets; use sets or HyperLogLog for sparse IDs.

Explain it without notes

Why is a bitmap 150× smaller than a set for DAU here, and when does that flip?

Practice

Compute 7-day retention: of users active on day 1, how many were active on day 7?

Trade-offs

↔
Bitmaps: exact and tiny for dense IDs, but memory scales with the ID range, not the number of set bits.
↔
Server-side BITOP is convenient but blocking; for heavy analytics, export to a warehouse.

Done when you can

I can build DAU, WAU and retention with bitmaps.
I know when bitmaps beat sets and when they're a trap.

Command Palette