skip to content

You keep one Redis bitmap per day with a bit set for every active user. How would you use BITOP and BITPOS to answer questions like 'how many users were active on all seven days of last week', and what does that computation cost on the server?

level: seniorimportance: nice to knowfreq 28%

answer

  1. AND = retained, OR = union, XOR = exactly one, NOT = complement
  2. shorter sources zero-padded; dest = longest length
  3. NOT sets every unallocated id → always AND it with a real population
  4. BITOP is O(N) x sources and writes a full-size key
  5. BITPOS to walk members; schedule the job, TTL the destination

basics

~20 s

BITOP AND/OR/XOR/NOT combines bitmaps into a destination key, then BITCOUNT gives the answer: AND of seven day keys counts users active every day. It is O(total bytes) and writes a full-size result key, so batch it off the hot path, give the result a TTL, and mind memory.

solid answer

~60 s

`BITOP <AND|OR|XOR|NOT> destkey src [src ...]` applies the operator bit by bit across the source strings and stores the result. Shorter sources are treated as zero-padded to the longest one, and the destination is always that longest length. NOT takes exactly one source. So: - **Retained all week** — `BITOP AND wk:all dau:d1 ... dau:d7` then `BITCOUNT wk:all`. - **Active at least once** — `BITOP OR`. - **Churned (active Monday, gone Tuesday)** — `BITOP NOT tmp dau:d2`, then `BITOP AND churn dau:d1 tmp`. - **Which users** — walk with `BITPOS wk:all 1 <from>` rather than testing every offset. Cost: `BITOP` is O(N) over the longest source in bytes, times the number of sources, and it **allocates and writes a destination key of full size**. Seven 6 MB bitmaps means ~42 MB read and a 6 MB key written, all inside one command that runs to completion before other clients are served. So: run it as a scheduled job, not per request; put a TTL on the destination; consider running it on a replica or a dedicated analytics instance; cache the resulting count.

code

text · 20 lines
text
# users active on every day of the week
> BITOP AND wk:all dau:d1 dau:d2 dau:d3 dau:d4 dau:d5 dau:d6 dau:d7
(integer) 6250000            # destination length in bytes
> BITCOUNT wk:all
(integer) 812934
> EXPIRE wk:all 86400
(integer) 1

# churn: active on d1 but not on d2
> BITOP NOT tmp:notd2 dau:d2
> BITOP AND churn:d1d2 dau:d1 tmp:notd2
> BITCOUNT churn:d1d2
(integer) 41022
> DEL tmp:notd2

# enumerate the first few retained ids
> BITPOS wk:all 1 0
(integer) 17
> BITPOS wk:all 1 3        # continue scanning from byte 3
(integer) 25

go deeper

for a junior

Recognise that AND/OR/NOT over daily bitmaps answer retention questions, and that BITCOUNT turns the result into a number.

for a middle

State the padding rule, the fact that the destination is a full-size key, and the NOT pitfall.

for a senior

Reason about cost: O(N) per source, a full-size write that replicates, and the scheduling/replica strategy that keeps it off the latency-critical path.

for a principal

Decide where this workload belongs at all — bitmaps for a small fixed set of boolean questions over dense ids, an analytics store for open-ended cohort work.

## Set algebra without sets If a bit at offset *u* means "user *u* was active", then boolean algebra over those bitmaps is set algebra over user populations, executed at memory-bandwidth speed: - **AND** = intersection → active on *every* listed day (retention / stickiness). - **OR** = union → active on *any* day (weekly or monthly actives). - **XOR** = symmetric difference → active on exactly one of two days. - **NOT** = complement → "not active", used to build "was, then wasn't". `BITOP op destkey src...` writes the result into `destkey`, replacing whatever was there. `BITCOUNT destkey` then converts a population into a number. ## The padding rule Sources of different lengths are treated as if the shorter ones were zero-padded on the right to the length of the longest, and the destination is created with that longest length. Two consequences: 1. **AND with a short source is destructive in the useful way** — ids beyond the short source's length are absent, i.e. 0, so they drop out of the intersection. That is the semantics you want. 2. **The destination is always full size.** OR-ing 31 daily bitmaps of 6 MB produces a 6 MB key, and BITOP holds the working buffer while it runs. Repeating that per request quickly becomes the dominant memory and CPU consumer. **NOT** is special: it accepts exactly one source, and its result is the complement across the *entire allocated length*, so every unused id below the high-water mark becomes a 1. Always intersect a NOT result with a real population bitmap (as in the churn example) instead of counting it directly — otherwise you count phantom ids that were never allocated. ## A worked funnel With `dau:2026-08-08` … `dau:2026-08-14`: - *Active all seven days*: `BITOP AND wk:20260808:all dau:2026-08-08 … dau:2026-08-14`, then `BITCOUNT`. - *Weekly actives*: same with `OR`. - *Stickiness*: daily-active count ÷ weekly-active count. - *Churn from day 1 to day 2*: `BITOP NOT tmp:notd2 dau:2026-08-09`; `BITOP AND churn:d1d2 dau:2026-08-08 tmp:notd2`; `BITCOUNT churn:d1d2`; `DEL tmp:notd2`. - *New on day 2*: complement of day 1 intersected with day 2. Bitmaps can express any of these because the operator, not the storage, does the work. ## Enumerating members Bitmaps store no member list, only flags, so "which users" means scanning. `BITPOS key 1 [start [end [BYTE|BIT]]]` returns the position of the first set bit at or after a starting point; loop calling it with `from = previous + 1` to walk the population. This is far better than 50 million GETBITs, but it is still linear in the bitmap and returns one id per round trip. If enumeration is a routine need rather than an occasional export, keep the membership in a structure meant for iteration and use the bitmap only for counting. ## Cost and operational discipline BITOP's complexity is O(N) where N is the length of the longest source, multiplied by the number of sources; BITCOUNT is O(N) over what it scans. Every Redis command runs to completion before the next one starts, so a 40 MB BITOP is 40 MB of work during which the server serves nobody else. On top of that: - The write is **replicated as a normal write of the destination key**, so the result is also replication traffic and snapshot content. - Destination keys accumulate. Always `EXPIRE` them or `DEL` them in the same job. - Ranged counting helps: `BITCOUNT key start end` limits the scan when you only care about a subrange of ids. The standard pattern in production is: a scheduled job (nightly or hourly) computes the aggregates, stores the *numbers* in small keys, and deletes or expires the intermediate bitmaps; dashboards read the numbers. If the analysis is heavy or ad hoc, point it at a replica or a separate instance loaded from a snapshot so the operational cache is untouched. Chunking also works: run BITOP over byte subranges only if you split the source keys that way to begin with, since BITOP itself has no range argument. ## When not to do this in Redis at all If you need many-dimensional cohort analysis, per-user attributes, or historical re-slicing, an analytics store is the right home. Bitmaps are unbeatable for a fixed set of high-frequency boolean questions over a dense id space — and awkward for everything else.

  • Why is it wrong to run BITCOUNT directly on the output of BITOP NOT?
    NOT complements every bit across the whole allocated length, so every id below the high-water mark that was never active becomes 1 — including ids that do not correspond to any real user. The count is therefore meaningless on its own. The result is only useful when intersected with a bitmap representing an actual population, such as 'active on day 1 AND not active on day 2'.
  • Seven daily bitmaps of 6 MB each need to be intersected every minute for a live dashboard. What would you change?
    Move the computation off the request path: compute it on a schedule, store the resulting integer in a small key, and have the dashboard read that. If the freshness requirement is real, run the BITOP on a replica or a separate analytics instance fed from a snapshot, so the ~42 MB of scanning does not occupy the primary's command execution. Also expire the destination keys so intermediates do not accumulate.

saying these in an interview costs you the question

  • Expecting BITOP to accept a range so you can process a bitmap in chunks
  • Counting a BITOP NOT result directly as 'inactive users'
  • Running multi-megabyte BITOPs per request on the primary instance
  • Assuming the destination key is small because few bits are set
  • Forgetting to expire or delete intermediate destination keys

context

resolving links…