08-bitmaps-hyperloglog-bloom.md

Chapter 8 — Bitmaps, HyperLogLog & Bloom Filters

Part II — Data Structures

Not every problem needs exact answers. Redis offers three complementary families for compact set representations and approximate cardinality:

1. Bitmaps — bit-level flags on string values; exact membership per offset
2. HyperLogLog (HLL) — probabilistic cardinality estimation in ~12 KB per key
3. Bloom filters — probabilistic membership via the RedisBloom module (Redis Stack)

This chapter walks through production recipes for daily active users, bitwise analytics, unique visitor counts, and when to trade accuracy for memory.

Bitmaps piggyback on Redis strings — the same type used for SET/GET — so they inherit key-level TTL, replication, and persistence semantics. HyperLogLog is a dedicated encoding with fixed size regardless of insert count. Bloom filters live in the RedisBloom module and allocate bit arrays sized from your declared error rate and capacity.

Redis 7.x note: Core Redis includes bitmap and HLL commands natively. Bloom and Cuckoo filters require Redis Stack or loading redisbloom.so. Verify module availability with MODULE LIST before deploying Recipe 8.4.

---

Recipe 8.1 — Daily Active Users with SETBIT

Problem

You need to count how many distinct users were active today, answer "was user 847 active on March 3?", and compare DAU across days — without storing 10 million user IDs as a set.

Solution

Treat a Redis string as a bit array. User ID N maps to bit offset N. One key per day: dau:2026-03-03.

redis-cli

127.0.0.1:6379> SETBIT dau:2026-03-03 1001 1
(integer) 0
127.0.0.1:6379> SETBIT dau:2026-03-03 1002 1
(integer) 0
127.0.0.1:6379> SETBIT dau:2026-03-03 1001 1
(integer) 1
127.0.0.1:6379> GETBIT dau:2026-03-03 1001
(integer) 1
127.0.0.1:6379> GETBIT dau:2026-03-03 9999
(integer) 0
127.0.0.1:6379> BITCOUNT dau:2026-03-03
(integer) 2
127.0.0.1:6379> EXPIRE dau:2026-03-03 7776000
(integer) 1

SETBIT returns the previous bit value — 1 on the second write to user 1001 confirms they were already marked active.

For user IDs exceeding 2³², use Roaring Bitmap patterns or shard: dau:2026-03-03:shard-0 for IDs 0–999999, etc.

Python

import datetime
import redis

r = redis.Redis(decode_responses=False)  # binary-safe

def dau_key(d: datetime.date | None = None) -> str:
    d = d or datetime.date.today()
    return f"dau:{d.isoformat()}"

def mark_active(user_id: int, d: datetime.date | None = None) -> bool:
    """Returns True if user was newly active today."""
    was_set = r.setbit(dau_key(d), user_id, 1)
    return was_set == 0

def was_active(user_id: int, d: datetime.date | None = None) -> bool:
    return r.getbit(dau_key(d), user_id) == 1

def dau_count(d: datetime.date | None = None) -> int:
    return r.bitcount(dau_key(d))

Node.js

function dauKey(d = new Date()) {
  return `dau:${d.toISOString().slice(0, 10)}`;
}

async function markActive(userId, d = new Date()) {
  const prev = await r.setbit(dauKey(d), userId, 1);
  return prev === 0; // newly active
}

async function dauCount(d = new Date()) {
  return r.bitcount(dauKey(d));
}

Go

func dauKey(t time.Time) string {
	return "dau:" + t.Format("2006-01-02")
}

func markActive(rdb *redis.Client, userID int64, t time.Time) (bool, error) {
	prev, err := rdb.SetBit(ctx, dauKey(t), int64(userID), 1).Result()
	return prev == 0, err
}

func dauCount(rdb *redis.Client, t time.Time) (int64, error) {
	return rdb.BitCount(ctx, dauKey(t), nil).Result()
}

Discussion

• Memory: Redis allocates string space up to the highest set bit. User ID 5,000,000 alone costs ~625 KB for that day — still far less than 5M set members (~50+ MB).
• Sparse IDs: If user IDs are UUID hashes or snowflakes in the trillions, bitmaps are wrong — use HyperLogLog (Recipe 8.3) or a hash-then-modulo shard strategy.
• BITCOUNT is O(N) over the string length; for huge bitmaps use BITCOUNT key start end on byte ranges, or sample for estimates.
• Set EXPIRE on daily keys (90-day retention is typical for analytics).
• BITFIELD (Redis 3.2+) supports get/set/increment on arbitrary bit-width fields in one command — useful for multi-metric counters packed into one key (e.g., 32-bit page-view sub-counts per user segment).

See Also

• Chapter 5 — Sets — exact membership when cardinality is modest
• Recipe 8.2 for cross-day bitwise operations

---

Recipe 8.2 — Cross-Day Analytics with BITOP

Problem

Compute weekly active users (WAU), users active Monday and Tuesday, or users who churned (active last week but not this week) using bitwise set algebra.

Solution

BITOP applies AND, OR, XOR, and NOT across bitmap keys and stores the result in a destination key.

redis-cli

127.0.0.1:6379> SETBIT dau:2026-03-01 1001 1
(integer) 0
127.0.0.1:6379> SETBIT dau:2026-03-01 1002 1
(integer) 0
127.0.0.1:6379> SETBIT dau:2026-03-02 1002 1
(integer) 0
127.0.0.1:6379> SETBIT dau:2026-03-02 1003 1
(integer) 0
127.0.0.1:6379> BITOP OR wau:2026-W09 dau:2026-03-01 dau:2026-03-02 dau:2026-03-03
(integer) 625
127.0.0.1:6379> BITCOUNT wau:2026-W09
(integer) 3
127.0.0.1:6379> BITOP AND both:0301-0302 dau:2026-03-01 dau:2026-03-02
(integer) 625
127.0.0.1:6379> BITCOUNT both:0301-0302
(integer) 1
127.0.0.1:6379> BITOP AND churned-candidates dau:2026-03-01 dau:2026-03-02
(integer) 625
127.0.0.1:6379> BITOP XOR tmp dau:2026-03-01 dau:2026-03-02
(integer) 625
127.0.0.1:6379> BITOP AND churned churned-candidates tmp
(integer) 625
127.0.0.1:6379> BITCOUNT churned
(integer) 1

Pattern for A and not B: BITOP AND tmp A B, then BITOP XOR diff A tmp, or use BITOP NOT carefully (NOT pads with ones in the extended length).

Python

def weekly_active(dates: list[datetime.date]) -> int:
    keys = [dau_key(d) for d in dates]
    dest = f"wau:{dates[0].isocalendar()[1]}"
    r.bitop_or(dest, *keys)
    r.expire(dest, 86400)  # temp aggregate
    return r.bitcount(dest)

def active_both_days(d1: datetime.date, d2: datetime.date) -> int:
    dest = f"both:{d1}:{d2}"
    r.bitop_and(dest, dau_key(d1), dau_key(d2))
    count = r.bitcount(dest)
    r.delete(dest)
    return count

Node.js

async function weeklyActive(dates) {
  const keys = dates.map(dauKey);
  const dest = `wau:${dates[0].toISOString().slice(0, 10)}`;
  await r.bitop("OR", dest, ...keys);
  return r.bitcount(dest);
}

Go

func weeklyActive(rdb *redis.Client, dates []time.Time) (int64, error) {
	keys := make([]string, len(dates))
	for i, d := range dates {
		keys[i] = dauKey(d)
	}
	dest := "wau:temp"
	rdb.BitOpOr(ctx, dest, keys...)
	return rdb.BitCount(ctx, dest, nil).Result()
}

Discussion

• BITOP is O(N) over the longest input string — weekly OR across seven large bitmaps can spike CPU; run aggregation jobs off-peak or on a replica.
• Destination key is overwritten each run; use TTL on scratch keys (wau:temp, both:...).
• BITPOS finds the first set/clear bit — useful for debugging sparse bitmaps.
• For real-time WAU/MAU at scale, many teams export bitmaps to an analytics warehouse nightly rather than interactive BITOP.

See Also

• Recipe 8.1 — building daily bitmaps
• Chapter 12 — Search & Analytics

---

Recipe 8.3 — Approximate Unique Counts with HyperLogLog

Problem

Count unique visitors to a landing page, distinct IPs in a DDoS window, or unique search terms — where ±2% error is acceptable and you cannot afford a set with millions of strings.

Solution

HyperLogLog structures in Redis use PFADD to observe elements and PFCOUNT to estimate cardinality. PFMERGE combines sketches from multiple periods.

redis-cli

127.0.0.1:6379> PFADD uv:homepage:2026-03-03 "user:1001" "user:1002" "session:abc"
(integer) 1
127.0.0.1:6379> PFADD uv:homepage:2026-03-03 "user:1001" "user:1003"
(integer) 1
127.0.0.1:6379> PFCOUNT uv:homepage:2026-03-03
(integer) 3
127.0.0.1:6379> PFADD uv:homepage:2026-03-04 "user:1002" "user:1004"
(integer) 1
127.0.0.1:6379> PFMERGE uv:homepage:2026-03-03-04 uv:homepage:2026-03-03 uv:homepage:2026-03-04
OK
127.0.0.1:6379> PFCOUNT uv:homepage:2026-03-03-04
(integer) 4

Python

def track_unique(key: str, *identifiers: str) -> int:
    r.pfadd(key, *identifiers)
    return r.pfcount(key)

def merge_unique(dest: str, *source_keys: str) -> int:
    r.pfmerge(dest, *source_keys)
    return r.pfcount(dest)

# Example: page view deduplication
def record_page_view(page: str, visitor_id: str) -> None:
    key = f"uv:{page}:{datetime.date.today().isoformat()}"
    r.pfadd(key, visitor_id)
    r.expire(key, 86400 * 90)

Node.js

async function recordPageView(page, visitorId) {
  const key = `uv:${page}:${new Date().toISOString().slice(0, 10)}`;
  await r.pfadd(key, visitorId);
  await r.expire(key, 86400 * 90);
}

async function uniqueCount(key) {
  return r.pfcount(key);
}

Go

func recordPageView(rdb *redis.Client, page, visitorID string) error {
	key := fmt.Sprintf("uv:%s:%s", page, time.Now().Format("2006-01-02"))
	if err := rdb.PFAdd(ctx, key, visitorID).Err(); err != nil {
		return err
	}
	return rdb.Expire(ctx, key, 90*24*time.Hour).Err()
}

Discussion

• Fixed ~12 KB per HLL key regardless of whether you tracked 1,000 or 10 million uniques (standard precision).
• Standard error ~0.81% for Redis's 2¹⁴ registers. Not suitable for billing or compliance counts.
• PFADD return value: 1 if internal estimate changed, 0 if not (not "was this element new?").
• HLL cannot tell you which elements were seen — only how many distinct values. For membership tests, use bitmaps (exact, dense IDs) or Bloom filters (Recipe 8.4).
• PFMERGE is additive for union estimates; there is no native HLL intersection in core Redis — approximate intersections require different structures or post-processing in application code.

See Also

• Recipe 8.5 — decision matrix for probabilistic structures
• Redis HLL documentation

---

Recipe 8.4 — Bloom Filters with RedisBloom (Redis Stack)

Problem

You need to answer "have we probably seen this email / URL / cache key before?" with bounded false positives, zero false negatives (for inserts you've made), and far less memory than a hash set — at billions of items.

Solution

Install Redis Stack or load the RedisBloom module. Use BF.ADD, BF.EXISTS, and BF.MADD for batch inserts.

redis-cli (Redis Stack)

127.0.0.1:6379> BF.ADD seen:urls "https://example.com/a"
(integer) 1
127.0.0.1:6379> BF.EXISTS seen:urls "https://example.com/a"
(integer) 1
127.0.0.1:6379> BF.EXISTS seen:urls "https://example.com/unknown"
(integer) 0
127.0.0.1:6379> BF.ADD seen:urls "https://example.com/a"
(integer) 0
127.0.0.1:6379> BF.MADD seen:emails "a@x.com" "b@y.com" "c@z.com"
1) (integer) 1
2) (integer) 1
3) (integer) 1

Create a filter with explicit capacity and error rate:

127.0.0.1:6379> BF.RESERVE seen:products 0.01 1000000
OK
127.0.0.1:6379> BF.ADD seen:products "SKU-9912"
(integer) 1

Python (requires Redis Stack / RedisBloom)

# redis-py 5.x — Bloom commands via execute_command or redisbloom client
def bloom_add(key: str, item: str) -> bool:
    """Returns True if item was newly added (might still FP on EXISTS elsewhere)."""
    return r.execute_command("BF.ADD", key, item) == 1

def bloom_exists(key: str, item: str) -> bool:
    return r.execute_command("BF.EXISTS", key, item) == 1

def ensure_filter(key: str, error_rate: float = 0.01, capacity: int = 1_000_000) -> None:
    try:
        r.execute_command("BF.RESERVE", key, error_rate, capacity)
    except redis.ResponseError as e:
        if "item exists" not in str(e).lower():
            raise

Node.js

async function bloomAdd(key, item) {
  return (await r.call("BF.ADD", key, item)) === 1;
}

async function bloomExists(key, item) {
  return (await r.call("BF.EXISTS", key, item)) === 1;
}

async function reserveFilter(key, errorRate = 0.01, capacity = 1_000_000) {
  try {
    await r.call("BF.RESERVE", key, errorRate, capacity);
  } catch (e) {
    if (!String(e.message).includes("exists")) throw e;
  }
}

Go

func bloomAdd(rdb *redis.Client, key, item string) (bool, error) {
	n, err := rdb.Do(ctx, "BF.ADD", key, item).Int()
	return n == 1, err
}

func bloomExists(rdb *redis.Client, key, item string) (bool, error) {
	n, err := rdb.Do(ctx, "BF.EXISTS", key, item).Int()
	return n == 1, err
}

Discussion

• False positives: BF.EXISTS may return 1 for an item never inserted — design downstream idempotency accordingly (e.g., duplicate upload handler checks object storage).
• No deletion in standard Bloom filters. RedisBloom offers Cuckoo filters (CF.*) supporting delete at higher memory cost.
• BF.RESERVE must run before first add unless you accept auto-scaling sub-filters (RedisBloom 2.x BF.ADD on missing key creates default filter).
• Use Bloom filters for cache penetration guard ("skip DB if definitely not cached"), web crawler URL dedup, and spam address screening.
• BF.INFO reports capacity, size, number of filters, and expansion rate — essential for capacity planning when using auto-scaling Bloom sub-filters.
• Scaling tip: For multi-tenant SaaS, isolate filters per tenant (seen:urls:tenant-42) to avoid one tenant's growth evicting another's filter state and to simplify GDPR deletion (drop key vs rebuild global filter).

See Also

• Chapter 23 — Modules & Redis Stack
• Recipe 8.5 — when Bloom beats HLL and bitmaps

---

Recipe 8.5 — When to Use Probabilistic Structures

Problem

Your team debates: "Should this metric be a Set, a bitmap, HyperLogLog, or a Bloom filter?" Wrong choices waste memory or produce silently wrong business numbers.

Solution

Use this decision framework:

Requirement	Structure	Why
Exact DAU for numeric user IDs (dense, < 512M)	Bitmap	BITCOUNT is exact; ~1 bit/user/day
Exact unique set, cardinality < ~100k	Set	Simple; SCARD is exact
Approximate UV count, any string ID	HyperLogLog	~12 KB fixed; 0.81% error
"Probably seen before?" membership	Bloom filter	Bounded FP; no FN for inserts
Range / percentile analytics over time	Sorted Set / TimeSeries	HLL and Bloom don't preserve values
Must delete arbitrary members	Set or Cuckoo filter	Standard Bloom cannot delete

Combined pattern — layered deduplication:

Request → Bloom filter (cheap reject) → Set or DB (confirm true novelty)

redis-cli sketch

127.0.0.1:6379> BF.EXISTS seen:events "evt-uuid-99"
(integer) 0
127.0.0.1:6379> SADD confirmed:events "evt-uuid-99"
(integer) 1
127.0.0.1:6379> BF.ADD seen:events "evt-uuid-99"
(integer) 1
127.0.0.1:6379> PFADD stats:events:2026-03-03 "evt-uuid-99"
(integer) 1

Bloom guards the hot path; Set (with TTL or capped sampling) holds exact recent IDs for audit; HLL tracks aggregate stats.

Python — structure picker

def track_visitor(page: str, visitor_id: str, user_id: int | None = None) -> dict:
    day = datetime.date.today().isoformat()
    stats = {"approx_uv": None, "exact_dau_bit": None}

    # Always track approximate UV
    uv_key = f"uv:{page}:{day}"
    r.pfadd(uv_key, visitor_id)
    stats["approx_uv"] = r.pfcount(uv_key)

    # Exact DAU only for logged-in users with numeric IDs
    if user_id is not None and user_id < 100_000_000:
        stats["exact_dau_bit"] = mark_active(user_id)

    return stats

Node.js

async function trackVisitor(page, visitorId, userId = null) {
  const day = new Date().toISOString().slice(0, 10);
  const uvKey = `uv:${page}:${day}`;
  await r.pfadd(uvKey, visitorId);
  const approxUv = await r.pfcount(uvKey);

  let exactDau = null;
  if (userId !== null && userId < 100_000_000) {
    exactDau = (await r.setbit(`dau:${day}`, userId, 1)) === 0;
  }
  return { approxUv, exactDau };
}

Go

type VisitorStats struct {
	ApproxUV int64
	NewDAU   *bool
}

func trackVisitor(rdb *redis.Client, page, visitorID string, userID *int64) (VisitorStats, error) {
	day := time.Now().Format("2006-01-02")
	uvKey := fmt.Sprintf("uv:%s:%s", page, day)
	rdb.PFAdd(ctx, uvKey, visitorID)
	uv, err := rdb.PFCount(ctx, uvKey).Result()
	if err != nil {
		return VisitorStats{}, err
	}
	stats := VisitorStats{ApproxUV: uv}
	if userID != nil && *userID < 100_000_000 {
		prev, _ := rdb.SetBit(ctx, "dau:"+day, *userID, 1).Result()
		b := prev == 0
		stats.NewDAU = &b
	}
	return stats, nil
}

Discussion

• Don't use HLL for DAU dashboards executives trust to the unit — explain the ~1% variance or back with bitmaps for numeric IDs.
• Bitmap vs Bloom: Bitmaps need integer offsets; Bloom accepts arbitrary strings. Bitmaps are exact; Bloom allows false positives.
• Memory at 1B users: Single bitmap ≈ 128 MB/day. HLL still ≈ 12 KB/day but approximate. Sharded bitmaps (dau:day:shard-N) spread load on Cluster.
• Observability: Monitor INFO memory, key sizes, and BF.INFO / MEMORY USAGE key when adopting probabilistic types — silent key growth is rare with HLL but common with mis-sized bitmaps.

See Also

• Chapter 3 — Strings and Keys — bitmaps live on string types
• Chapter 20 — Performance & Tuning
• Chapter 23 — Modules & Redis Stack

---

Chapter Summary

Structure	Commands	Exact?	Best for
Bitmap	SETBIT, GETBIT, BITCOUNT, BITOP	Yes (per bit)	DAU/WAU with numeric IDs
HyperLogLog	PFADD, PFCOUNT, PFMERGE	No (~0.81%)	Unique visitor estimates
Bloom filter	BF.ADD, BF.EXISTS, BF.RESERVE	FP only	"Probably seen" guards

Core Redis ships bitmaps and HyperLogLog; Bloom filters require Redis Stack. Choose exact structures when errors have dollar signs attached; choose probabilistic ones when you're counting grains of sand on a beach.

---

Previous: Chapter 7 — Sorted Sets ←
Next: Chapter 9 — Streams & Geospatial →