Counting at Scale: Bloom Filters, HyperLogLog, Count-Min Sketch and Top-K.

The week's store runs its weekend flash sale again. Yesterday's query layer is fast, late data is handled, and the CFO trusts the numbers. Then the marketing team adds three tiles to the live dashboard. (An illustrative scene: the times and sizes are made up; each failure is a classic one.)

None of these tiles was wrong to ask for. What broke is the assumption that counting means remembering. Today's tools count with a fixed, small amount of memory and a known, bounded error.

Yesterday (Day 5) listed "approximate algorithms — HyperLogLog, sketches" and "Bloom filters — skip blocks without matches" among the query-layer tools. Today we open them up: how each works, what it costs, how wrong it can be, and where it fits in this week's pipeline.

01Chapter 1: Why Exact Counting Breaks#

1.1 Four Questions, Four Structures#

Almost every "counting" question in analytics is one of four kinds:

The exact answers all have the same cost: memory that grows with the number of distinct keys, not with the number of events. Ten billion page views of one product cost one counter; ten million different visitors cost ten million entries.

1.2 Memory per Distinct Key#

A set of keys is never just the keys. Redis's own documentation sizes a plain set at roughly capacity × (192 bits + value), about 40 bytes per IP address (Redis docs, Bloom filter). Hash sets in Java or Python cost the same order: the key, pointers, and empty slots so the table stays fast.

Day 2's streaming DAU job kept a set() of user ids per day. That is fine for one number. It breaks when the same question is asked per slice: every user appears in several slices, and every slice keeps its own set.

1.3 The Sketch Contract#

A sketch is a small summary of a stream that answers one kind of question approximately. The useful ones share four properties:

1. Fixed (or slowly growing) memory, chosen up front from the error you can accept, not from the data's size.
2. A known error with a known direction. A Bloom filter never says "no" to a key it has seen; a Count-Min Sketch never under-counts. Knowing which way the error goes tells you where it's safe to use.
3. One pass. Each event is touched once, so it fits a Flink operator.
4. Mergeable. Sketches built on different partitions, hours or machines combine into the sketch of the union: build in parallel, merge at query time.

Bloom filters, HyperLogLog and Count-Min hash each key to random-looking bits and keep a tiny statistic of those bits, so a biased hash biases every estimate. (Space-Saving and Misra-Gries keep the keys themselves.)

02Chapter 2: Bloom Filters#

2.1 How It Works#

Burton Bloom proposed saving memory by "exploiting the possibility that a small fraction of errors of commission may be tolerable", using "a smaller core resident hash area" plus "some secondary and perhaps time-consuming test to 'catch' the small fraction of errors" (Bloom, Communications of the ACM, 1970). His example: a hyphenation program whose in-memory filter avoids most lookups in a disk dictionary.

The structure, his "method 2", is an array of m bits and k hash functions:

• Insert x: set the k bits at positions h₁(x)…h_k(x).
• Query x: if any of the k bits is 0, x was definitely never inserted. If all are 1, x was probably inserted: other keys may have set those bits.

So a Bloom filter has false positives but no false negatives. That one-sided error is the whole point: "no" is free and certain, "maybe" sends you to the slow, exact check.

import hashlib, math

class BloomFilter:
    def __init__(self, n_expected: int, fp_rate: float):
        self.m = math.ceil(-n_expected * math.log(fp_rate) / math.log(2) ** 2)  # bits
        self.k = max(1, round(self.m / n_expected * math.log(2)))               # hash functions
        self.bits = bytearray((self.m + 7) // 8)

    def _positions(self, key: str):
        d = hashlib.blake2b(key.encode(), digest_size=16).digest()
        h1, h2 = int.from_bytes(d[:8], "little"), int.from_bytes(d[8:], "little")
        return [(h1 + i * h2) % self.m for i in range(self.k)]   # k indexes from two hashes

    def add(self, key: str) -> None:
        for p in self._positions(key):
            self.bits[p >> 3] |= 1 << (p & 7)

    def might_contain(self, key: str) -> bool:
        return all(self.bits[p >> 3] & (1 << (p & 7)) for p in self._positions(key))

seen = BloomFilter(n_expected=100_000_000, fp_rate=0.01)   # ~120 MB, k = 7

2.2 The False-Positive Maths#

After inserting n keys with k hashes into m bits, the chance that a given bit is still 0 is about e^(−kn/m). A key that was never inserted is a false positive when all k of its bits are 1:

p ≈ (1 − e^(−kn/m))^k

Two results follow, and they are the ones to remember:

• Best k = (m/n) · ln 2, which leaves about half the bits set. Bloom found the same balance point: the smallest hash area "occurs when half the bits are 1 and half are 0" (Bloom, 1970).
• Bits per key for a target p: m/n = −ln p / (ln 2)² ≈ 1.44 · log₂(1/p).

Redis's docs agree: "1% error rate requires 7 hash functions and 9.585 bits per item". Each 10× drop costs about 4.8 more bits per key, whatever the key's size. So one billion keys at 1% take ≈ 1.2 GB; a hash set of them at ~40 bytes each, about 40 GB.

2.3 Sizing: n Is a Promise#

The formula assumes you know n. A Bloom filter can't grow in place: once more keys arrive than it was sized for, more bits are 1 and the false-positive rate climbs, silently.

2.4 Deletes: Counting Bloom and Cuckoo Filters#

A Bloom filter can't delete: clearing a bit might remove other keys that share it, creating false negatives. Two variants fix that:

• Counting Bloom filter: each position is a small counter instead of a bit; insert increments, delete decrements. Fan et al. note the counters need "four or more bits", so it "requires 4× more space than a standard Bloom filter" (Fan, Andersen, Kaminsky & Mitzenmacher, CoNEXT 2014).
• Cuckoo filter (same paper): a cuckoo hash table of short fingerprints, filled to about 95%. It supports deletes and "uses less space than Bloom filters in many practical applications, if the target false positive rate ϵ is less than 3%". Caveats: a deleted item "must have been previously inserted" (or you may remove another item with the same fingerprint), and it is "not suitable for applications that insert the same item more than 2b times" (b is the bucket size).

2.5 Where Bloom Filters Earn Their Keep#

LSM storage engines. In Cassandra's read path, "to avoid checking every SSTable data file for the partition being requested, Cassandra employs a data structure known as a bloom filter" that says the data "definitely does not exist in the given file" or "probably exists" (Apache Cassandra docs). The per-table bloom_filter_fp_chance defaults to 0.1 with LeveledCompactionStrategy and 0.01 otherwise, and 0.01 "will require about three times as much memory" as 0.1. RocksDB's wiki: "9.9 bits per key (1% false positive rate) is 99% as effective as 100 bits per key", and SST filters commonly use "~10% of system RAM" (RocksDB wiki). Day 5's "skip blocks without matches" is the same idea.

%% title: A point read in an LSM engine, with one Bloom filter per SSTable
flowchart TD
  R@{ icon: "sd:api", label: "get(user:42)" }
  MT@{ icon: "sd:cache", label: "Memtable (RAM)" }
  B1{"SSTable 1 Bloom:<br/>user:42?"}
  B2{"SSTable 2 Bloom:<br/>user:42?"}
  B3{"SSTable 3 Bloom:<br/>user:42?"}
  S1@{ icon: "sd:file", label: "SSTable 1 (disk)" }
  S2@{ icon: "sd:file", label: "SSTable 2 (disk)" }
  S3@{ icon: "sd:file", label: "SSTable 3 (disk)" }
  NF(["Not found<br/>no SSTable read from disk"]):::ok
  R --> MT
  MT -->|"miss"| B1
  B1 -->|"no: skip file"| B2
  B1 -.->|"maybe"| S1
  B2 -->|"maybe (false for ~1% of absent keys)"| S2
  B2 -->|"no: skip file"| B3
  B3 -.->|"maybe"| S3
  B3 -->|"no"| NF
  class R client
  class MT cache
  class S1,S2,S3 store

CDN caches and one-hit wonders. On one Akamai cluster over two days, "74% of the roughly 400 million objects in cache were accessed only once". Caching those "one-hit-wonders" wastes disk, so Akamai caches an object only on its second request, remembering first requests in a Bloom filter. With filtering on, "the byte hit rate increases from around 74% to 83%", and disk writes drop "from an average of 10209 writes per second to 5738 writes per second, a decrease of 44%" (Maggs & Sitaraman, ACM SIGCOMM CCR, 2015). The false positives here are harmless: an occasional one-hit object gets cached anyway.

Deduplication in the pipeline. Day 1 gave every event a client-generated event_id so retries can be dropped. A Bloom filter of recent ids looks like a cheap dedup check; check which way its error goes first.

03Chapter 3: HyperLogLog#

3.1 The Intuition#

Hash every user id to a random-looking 64-bit number. Look at the position of the first 1-bit. Half of all hashes start with 1, a quarter with 01, an eighth with 001. If the longest run of leading zeros you have seen is 20, you have probably seen around 2²⁰ ≈ a million distinct values. Duplicates don't matter: the same id always hashes to the same bits, so seeing it again changes nothing.

One maximum is noisy (one lucky hash doubles it), so HyperLogLog averages many:

1. Use the first p bits of the hash to pick one of m = 2^p registers.
2. In that register keep the maximum "position of the first 1-bit" seen in the remaining bits.
3. Estimate with a normalized harmonic mean of 2^register across all registers. The harmonic mean tames outliers that the earlier LogLog's geometric mean let through (Flajolet, Fusy, Gandouet & Meunier, AofA 2007). Each register holds a count of zeros, so 5–6 bits suffice.

3.2 Error and Memory#

The paper's headline: the standard error is "typically about 1.04/√m", and the algorithm can "estimate cardinalities well beyond 10⁹ with a typical accuracy of 2% while using a memory of only 1.5 kilobytes" (Flajolet et al., 2007).

The error is a standard deviation: about two-thirds of estimates fall within ±1σ, 95% within ±2σ. Halving it costs 4× the memory, and memory doesn't depend on n.

3.3 Small and Huge Counts: HLL++#

The raw estimator is biased for small sets: with few values, most registers are still 0. The original paper switches to linear counting, m · ln(m / empty registers), when the estimate is below 5m/2, and applies a correction near 2³² because it used 32-bit hashes (Flajolet et al., 2007).

Google's HyperLogLog++ engineered this for PowerDrill, its interactive column store, where some count-distinct queries "exceeded the available memory". PowerDrill ran "about 5 million such count distinct computations" a day, "99% of these computations yield a result of 100 or less", while "about 100 computations a day yield a result greater than 1 billion" (Heule, Nunkesser & Hall, EDBT 2013). The three changes:

• A 64-bit hash. Registers grow from 5 to 6 bits (memory 6 · 2^p bits), and the large-range correction "is no longer needed".
• Empirical bias correction for the middle range, where the raw estimate overestimates.
• A sparse representation: when most registers are empty, store only (index, value) pairs, and switch to the dense array once the list would exceed 6m bits. At precision 14 the sparse form cuts the average error "for cardinalities up to roughly 12000" by "a factor of 4".

3.4 Merging: the Property That Makes HLL Work in Pipelines#

Two HLLs with the same precision and hash merge by taking the register-wise maximum: exactly the sketch of the union of both streams. So you build sketches per partition, minute or slice in parallel, and answer "unique visitors last 30 days, Electronics, India" by merging 30 daily sketches. And re-adding an element is a no-op, so replays and duplicates don't inflate the count: HLL inserts are idempotent.

What merging can't do well is intersection. "Users who visited both Electronics and Books" by inclusion-exclusion, |A| + |B| − |A ∪ B|, subtracts large noisy numbers to get a small one, so its relative error explodes when the overlap is small. Apache DataSketches' Theta sketches were built for this: the framework's combining function "is extended to set Intersections and Differences as well" (Apache DataSketches docs).

import hashlib, math

class HyperLogLog:
    def __init__(self, p: int = 14):
        self.p, self.m = p, 1 << p
        self.reg = bytearray(self.m)
        self.alpha = 0.7213 / (1 + 1.079 / self.m)        # bias constant for m >= 128

    def add(self, item: str) -> None:
        x = int.from_bytes(hashlib.blake2b(item.encode(), digest_size=8).digest(), "big")
        idx = x >> (64 - self.p)                          # first p bits pick the register
        rest = x & ((1 << (64 - self.p)) - 1)
        rank = (64 - self.p) - rest.bit_length() + 1      # position of the first 1-bit
        self.reg[idx] = max(self.reg[idx], rank)

    def count(self) -> int:
        est = self.alpha * self.m ** 2 / sum(2.0 ** -r for r in self.reg)
        zeros = self.reg.count(0)
        if est <= 2.5 * self.m and zeros:                 # small range: linear counting
            est = self.m * math.log(self.m / zeros)
        return round(est)

    def merge(self, other: "HyperLogLog") -> "HyperLogLog":
        assert self.p == other.p, "same precision and same hash, or the merge is meaningless"
        out = HyperLogLog(self.p)
        out.reg = bytearray(max(a, b) for a, b in zip(self.reg, other.reg))
        return out

3.5 HyperLogLog in Production#

Redis. PFADD adds elements, PFCOUNT returns the estimate, PFMERGE combines keys. The implementation "uses up to 12 KB of memory and provides a standard error rate of 0.81%", and can count sets of up to 2⁶⁴ members (Redis docs). The dense form is "a Redis string of 12288 bytes in order to store 16384 6-bit counters"; small HLLs use a run-length-encoded sparse form, and Redis switches automatically. Two details matter at scale: PFCOUNT with several keys merges them on the fly, which "may take a time in the order of magnitude of the millisecond, and should be not abused", and because the last bytes cache the computed cardinality, "PFCOUNT is technically a write command" (Redis docs, PFCOUNT).

BigQuery. APPROX_COUNT_DISTINCT "is less accurate than COUNT(DISTINCT expression), but performs better on very large input". It returns a number, not a sketch, and "doesn't allow partial aggregations, re-aggregations, and custom precision". For stored, mergeable sketches use the HLL++ functions: HLL_COUNT.INIT(input, precision) builds a sketch as BYTES, with precision from 10 to 24 and a default of 15; HLL_COUNT.MERGE_PARTIAL merges sketches into a sketch; HLL_COUNT.MERGE and HLL_COUNT.EXTRACT return counts. If merged sketches have different precisions, "the precision will be downgraded to the lowest precision involved". BigQuery's sketches are larger than Redis's: the documented maximum at precision 14 is 16 KiB + 30 B, against Redis's 12 KB (Google Cloud docs).

-- Nightly: one sketch per day, category and country (the fact table from Day 3)
CREATE TABLE agg_daily_visitors AS
SELECT DATE(event_time) AS day, category, country,
       HLL_COUNT.INIT(user_id, 14) AS visitors_hll          -- BYTES, ~16 KB at most
FROM fact_page_views
GROUP BY day, category, country;

-- Dashboard: unique visitors for any range, without touching raw events
SELECT category, HLL_COUNT.MERGE(visitors_hll) AS unique_visitors
FROM agg_daily_visitors
WHERE day BETWEEN '2026-10-01' AND '2026-10-28' AND country = 'IN'
GROUP BY category;

Apache DataSketches. A library of mergeable sketches with Druid and Hive integrations; its HLL sketch takes lgK "from 4 to 21" and 4-, 6- or 8-bit registers (Apache DataSketches docs).

%% title: Answering "unique visitors, last 28 days" from stored sketches (illustrative numbers)
sequenceDiagram
  participant D as Dashboard
  participant Q as Query API
  participant C as Result cache
  participant W as Warehouse (sketch table)
  D->>Q: unique visitors, Electronics, IN, 1-28 Oct
  Q->>C: lookup (range, slice)
  C-->>Q: miss
  Q->>W: HLL_COUNT.MERGE over 28 daily sketches
  Note over W: reads 28 rows of at most ~16 KB each, not 28 days of raw events
  W-->>Q: 1,184,203 (plus or minus about 0.8%)
  Q->>C: store with a TTL
  Q-->>D: ~1.18M unique visitors

04Chapter 4: Count-Min Sketch#

4.1 How It Works#

A Count-Min Sketch (CMS) is a table of d rows × w counters, with one hash function per row (Cormode & Muthukrishnan, Journal of Algorithms, 2005):

• Update (x, c): in each row j, add c to counter[j][h_j(x)].
• Query x: return the minimum of x's d counters.

Each of x's counters holds x's true count plus whatever collided into it. Collisions only add, so the minimum is the least-polluted estimate.

4.2 The Bounds#

With w = ⌈e/ε⌉ and d = ⌈ln(1/δ)⌉, the paper's Theorem 1 gives, for every key i:

aᵢ ≤ âᵢ ≤ aᵢ + ε · N, with probability at least 1 − δ,

where aᵢ is the true count, âᵢ the estimate and N the total of all counts (Cormode & Muthukrishnan, 2005). Three consequences:

• Never under-counts: the estimate is an upper bound.
• The error is relative to the whole stream: ε = 0.001 means "within 0.1% of all events", enormous for a rare key, tiny for a popular one.
• Memory ignores the number of keys: ε = 0.001, δ = 0.01 gives w = 2,719, d = 5: about 53 KB of 4-byte counters for a thousand products or a hundred million.

4.3 Conservative Update#

Estan and Varghese introduced a simple change for counter arrays like this, conservative update: when x arrives, raise each of its counters only as far as needed, to max(counter, current estimate + c), instead of adding c to all of them. In their words, "no counter is increased to more than the size of the smallest counter plus the size of the packet", and they call it "an important optimization for multistage filters that improves performance by an order of magnitude" (Estan & Varghese, SIGCOMM 2002).

Why it is still safe: x's true count is at most its current minimum plus c, so raising counters to that level never makes any key's estimate lower than its true count. What it costs: counters no longer equal sums of updates, so the sketch can't take decrements (no deletes, no negative updates), and the clean linear analysis no longer applies. For page views and clicks, which only grow, it is a free accuracy gain.

4.4 From Counts to Heavy Hitters#

A CMS stores counters, not keys: it can answer "how many views did product 42 get?" but not "which products are hot?". Cormode and Muthukrishnan define the φ-heavy hitters as the keys whose count exceeds φ · N. The usual pattern pairs the sketch with a small heap of candidates: after each update, query x's estimate; if it passes φ · N, keep x in the heap.

import hashlib, heapq

class CountMin:
    def __init__(self, width: int = 2719, depth: int = 5, conservative: bool = True):
        self.w, self.d, self.cu = width, depth, conservative
        self.rows = [[0] * width for _ in range(depth)]
        self.total = 0

    def _cols(self, key: str):
        return [int.from_bytes(hashlib.blake2b(key.encode(), digest_size=8,
                salt=bytes([j])).digest(), "big") % self.w for j in range(self.d)]

    def add(self, key: str, c: int = 1) -> int:
        cols, self.total = self._cols(key), self.total + c
        if self.cu:                                   # conservative update: only lift the low counters
            target = min(self.rows[j][col] for j, col in enumerate(cols)) + c
            for j, col in enumerate(cols):
                self.rows[j][col] = max(self.rows[j][col], target)
        else:
            for j, col in enumerate(cols):
                self.rows[j][col] += c
        return self.estimate(key)

    def estimate(self, key: str) -> int:
        return min(self.rows[j][col] for j, col in enumerate(self._cols(key)))

def heavy_hitters(stream, phi=0.001, k=10):
    cms, candidates = CountMin(), {}
    for product_id in stream:
        est = cms.add(product_id)
        if est >= phi * cms.total:                    # passes the phi * N threshold
            candidates[product_id] = est
    return heapq.nlargest(k, candidates.items(), key=lambda kv: kv[1])

05Chapter 5: Space-Saving, Misra-Gries and Windows#

5.1 Counter-Based Summaries#

A more direct family keeps a fixed number of (key, counter) pairs and decides what to evict.

Misra-Gries (Misra & Gries, 1982) keeps up to k − 1 counters. A monitored key increments its counter; a new key takes a free counter; if none is free, every counter is decremented by one (and zeros are freed). Each decrement round removes k counts at once (the k − 1 counters plus the new event), so it can happen at most N/k times: every count is an under-estimate by at most N/k, and any key occurring more than N/k times is guaranteed to be kept. Apache DataSketches' frequent-items sketch "implements a variant of what is commonly known as the 'Misra-Gries algorithm'"; its bounds satisfy (UB − LB) ≤ W · ε with ε = 3.5/M for a map of M entries, and it can "merge itself with another sketch" (Apache DataSketches docs).

Space-Saving (Metwally, Agrawal & El Abbadi, ICDT 2005) keeps m counters and, when a new key arrives with no free counter, replaces the key with the minimum counter, gives the newcomer that minimum + 1, and records the inherited amount as its possible over-estimation ε. Its guarantees:

• The counters always sum to the stream length N (Lemma 1).
• Every monitored key's count is over-estimated by at most the current minimum: fᵢ ≤ countᵢ ≤ fᵢ + min (Lemma 3), and min ≤ ⌊N/m⌋.
• Any key whose true frequency exceeds min "must exist in Stream-Summary" (Theorem 1), and count − ε gives a guaranteed lower bound, so you can tell which of the reported top-k are certain.

%% title: Space-Saving: one update with m counters
flowchart TD
  E(["Event: product x"]):::core
  M{"Is x already<br/>monitored?"}
  F{"Is a counter<br/>free?"}
  I["count[x] += 1"]:::ok
  N["Add x with<br/>count 1, err 0"]:::ok
  R["Evict y with the minimum count<br/>x gets count = min + 1<br/>err[x] = min"]:::bad
  Q(["Top-k: highest counts<br/>certain if count - err beats<br/>the (k+1)th count"]):::service
  E --> M
  M -->|"yes"| I
  M -->|"no"| F
  F -->|"yes"| N
  F -->|"no"| R
  I --> Q
  N --> Q
  R --> Q

class SpaceSaving:
    """m counters; counts over-estimate by at most err[key] <= N/m."""
    def __init__(self, m: int = 1000):
        self.m, self.count, self.err = m, {}, {}

    def add(self, key: str, c: int = 1) -> None:
        if key in self.count:
            self.count[key] += c
        elif len(self.count) < self.m:
            self.count[key], self.err[key] = c, 0
        else:                                            # O(m) here; the paper's Stream-Summary makes it O(1)
            victim = min(self.count, key=self.count.get)
            floor = self.count.pop(victim); self.err.pop(victim)
            self.count[key], self.err[key] = floor + c, floor

    def top(self, k: int):
        ranked = sorted(self.count.items(), key=lambda kv: kv[1], reverse=True)
        kth_next = ranked[k][1] if len(ranked) > k else 0
        return [(key, n, n - self.err[key] >= kth_next) for key, n in ranked[:k]]   # (key, count, guaranteed?)

For the trending tile, m = 1,000 counters (tens of KB) track the top 10 of a million products, each count off by at most N/1,000, and far less on skewed traffic.

Redis's Top-K type instead uses HeavyKeeper's "count-with-exponential-decay", "biased against mouse (small) flows", plus "a min heap that holds the K items with the highest counts" (Redis docs).

5.2 Top-K Over Windows#

"Trending this hour" is a windowed question. A typical design:

• Panes: keep one summary per one-minute event-time window, keyed by Day 4's watermarks. A late event updates its own minute's pane until the watermark closes it.
• Sliding hour: every minute, merge the last 60 panes and read the top-k. Drop the oldest pane, never "subtract" it: Space-Saving and Misra-Gries summaries merge but don't subtract cleanly.
• Trending, not just popular: rank this hour's count against a baseline (the same hour last week), or the phone case sits at #1 forever.
• Distinct, not raw: to stop one bot pushing an item up, count unique users per candidate with an HLL on top of the top-k.

06Chapter 6: Which Sketch, and Where It Sits#

6.1 The Trade-off#

Three questions settle most choices: which direction of error can you live with; must it combine across time or partitions (then the same parameters and hash everywhere); and is the number audited (billing and finance stay exact in Day 2's batch layer; dashboards and trending take sketches).

6.2 In the Week's Pipeline#

%% title: Sketches in the week's pipeline
flowchart TD
  K@{ icon: "tech:kafka", label: "Kafka<br/>validated events" }
  F@{ icon: "tech:flink", label: "Flink<br/>keyed by event time" }
  BL["Dedup gate<br/>Bloom says #quot;new#quot; → accept<br/>#quot;maybe#quot; → exact state check"]:::core
  HL["HLL per minute ×<br/>category × country"]:::core
  TK["Space-Saving per minute<br/>(keyed by product)"]:::core
  CH@{ icon: "tech:clickhouse", label: "Real-time store<br/>sketch columns" }
  BQ@{ icon: "tech:bigquery", label: "Warehouse<br/>HLL_COUNT sketches per day" }
  R@{ icon: "tech:redis", label: "Redis<br/>trending top 10, PFCOUNT tiles" }
  DB@{ icon: "sd:dashboard", label: "Dashboards<br/>merge at query time" }
  K --> F
  F --> BL
  BL --> HL
  BL --> TK
  HL -->|"minute sketches"| CH
  HL -->|"daily rollup (merge)"| BQ
  TK -->|"merge last 60 panes"| R
  CH --> DB
  BQ --> DB
  R --> DB
  class K queue
  class F service
  class CH,BQ store
  class R cache
  class DB client

How the week's ideas meet the sketches:

• Exactly-once (Day 1, Day 2). HLL and Bloom inserts are idempotent, so a replay after a restart can't inflate them. CMS, Space-Saving and plain counters are not: a replayed event is counted twice. Keep them in Flink's checkpointed state so a restart rolls them back with the offsets, or deduplicate first.
• Late data (Day 4). A late event updates the sketch of its own event-time window. Because sketches merge, a correction is a merge of a small "late" sketch into the stored one, not a recompute of the day.
• Data modeling and queries (Days 3 and 5). Store sketches as rollup columns (visitors_hll BYTES) at the finest grain you'll merge from: you can merge minutes into days, never split days into minutes. A range query on uniques becomes as cheap as one on sums.

07Chapter 7: Edge Cases and Failure Modes#

Privacy: a sketch keeps hashed bits, not ids, but it is built from personal identifiers, so a typical design gives stored sketches the same retention and deletion rules as the events (Week 9 covers deletion).

08Chapter 8: How Real Systems Do It#

09Chapter 9: Common Mistakes to Avoid#

9.1 Mistake 1: Adding Up Unique Counts#

9.2 Mistake 2: Trusting the Error in the Wrong Direction#

9.3 Mistake 3: Reading Small Counts From a Count-Min Sketch#

9.4 Mistake 4: Merging Sketches That Don't Match#

10Chapter 10: Interview Tips and Phrases#

10.1 When to Bring It Up#

• "Unique users", "DAU/MAU" or "reach", sliced or over arbitrary ranges: HLL.
• "Top / trending" over a stream: Space-Saving, or CMS plus a heap, in windows.
• "Have we seen this?" in front of something slow (disk, a database, a crawler, a cache fill): Bloom filter.
• "How does the job's state grow?": sketches for counting state.

10.3 Questions to Ask the Interviewer#

• Which numbers are audited or billed, and which are for dashboards? How much error is acceptable on each?
• Do we need arbitrary date ranges and slices, or a fixed set of reports?
• Do counts ever decrease (cancellations, deletions)?

10.4 Common Follow-Up Questions#

11Chapter 11: Practice Problems#

Summary#

Week 8 Complete!#

What's Next#

The Week 8 Capstone will integrate all these concepts into designing a complete analytics system for a video streaming platform.

Further Reading#

Papers#

• Paper

  Burton H. Bloom — Space/Time Trade-offs in Hash Coding with Allowable Errors (Communications of the ACM, July 1970): https://doi.org/10.1145/362686.362692

• Paper

  Flajolet, Fusy, Gandouet & Meunier — HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm (AofA 2007): https://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf

• Blog

  Heule, Nunkesser & Hall — HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm (EDBT 2013): https://research.google/pubs/hyperloglog-in-practice-algorithmic-engineering-of-a-state-of-the-art-cardinality-estimation-algorithm/

• Paper

  Cormode & Muthukrishnan — An Improved Data Stream Summary: The Count-Min Sketch and its Applications (Journal of Algorithms, 2005): https://www.cs.tufts.edu/~nr/cs257/archive/graham-cormode/count-min.pdf

• Paper

  Estan & Varghese — New Directions in Traffic Measurement and Accounting (SIGCOMM 2002): https://www.cs.tufts.edu/~nr/cs257/archive/cristian-estan/traffic-flows.pdf

• Paper

  Metwally, Agrawal & El Abbadi — Efficient Computation of Frequent and Top-k Elements in Data Streams (ICDT 2005; UCSB TR 2005-23): https://www.cs.ucsb.edu/sites/default/files/documents/2005-23.pdf

• Paper

  Fan, Andersen, Kaminsky & Mitzenmacher — Cuckoo Filter: Practically Better Than Bloom (CoNEXT 2014): https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf

• Paper

  Maggs & Sitaraman — Algorithmic Nuggets in Content Delivery (ACM SIGCOMM CCR, 2015): https://people.cs.umass.edu/~ramesh/Site/HOME_files/CCRpaper_1.pdf

Official Documentation#

• Docs

  Redis — HyperLogLog: https://redis.io/docs/latest/develop/data-types/probabilistic/hyperloglogs/

• Docs

  Redis — PFCOUNT: https://redis.io/docs/latest/commands/pfcount/

• Docs

  Redis — Bloom filter: https://redis.io/docs/latest/develop/data-types/probabilistic/bloom-filter/

• Docs

  Redis — Count-min sketch: https://redis.io/docs/latest/develop/data-types/probabilistic/count-min-sketch/

• Docs

  Redis — Top-K: https://redis.io/docs/latest/develop/data-types/probabilistic/top-k/

• Docs

  BigQuery — Approximate aggregate functions: https://cloud.google.com/bigquery/docs/reference/standard-sql/approximate_aggregate_functions

• Docs

  BigQuery — HyperLogLog++ functions: https://cloud.google.com/bigquery/docs/reference/standard-sql/hll_functions

• Docs

  Apache DataSketches — HLL sketches: https://datasketches.apache.org/docs/HLL/HllSketches.html

• Docs

  Apache DataSketches — Theta sketches: https://datasketches.apache.org/docs/Theta/ThetaSketches.html

• Docs

  Apache DataSketches — Frequent items: https://datasketches.apache.org/docs/Frequency/FrequentItemsOverview.html

• Docs

  Apache Cassandra — Bloom filters: https://cassandra.apache.org/doc/latest/cassandra/managing/operating/bloom_filters.html

• Wiki

  RocksDB wiki — RocksDB Bloom Filter: https://github.com/facebook/rocksdb/wiki/RocksDB-Bloom-Filter