Engineering Atlas › System Design Fundamentals

Approximate data structures for huge scale

14 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

How it works

The question decides the structure

Before reaching for a clever structure, write down the exact question, over how many items, and how wrong the answer may be. Teams skip the last part. "Unique visitors today, within 1%?" is 12 KB of HyperLogLog registers in Redis (Redis docs). "Exactly how many?" may need gigabytes.

QuestionStructureMemory for a typical settingErrorLesson
Have I seen this key?Bloom filterAbout 1.2 MB for 1 million keys at 1% false positivesFalse positives onlyBloom Filters
Have I seen it, and can I delete it?Cuckoo filterSimilar to Bloom at low false-positive ratesFalse positives onlyCuckoo Filter
How many distinct items?HyperLogLog12 KB for about 0.8% standard error, at any countRelative, two-sidedHyperLogLog
How often has this item appeared?Count-min sketchAbout 54 KB for 0.1% of total count error at 99% confidenceOverestimates onlyCount-Min Sketch
How similar are two sets?MinHashA few hundred integers per setShrinks with signature lengthMinHash
What is near this point?Geohash, quadtree, R-tree, S2 or H3An index over the pointsExact after a filter stepGeohash, Quad Trees, R-Trees, S2 and H3
What comes next in key order?Skip listAbout 1.33 pointers per key at p = 1/4ExactSkip Lists
Do these two replicas match?Merkle treeOne hash per nodeExact, with negligible collision riskMerkle Trees

One newer family is worth knowing even though it has no lesson of its own. When a set is built once and never changes, such as the keys in an immutable file, static filters beat both Bloom and cuckoo on space. Xor filters sit within 23% of the theoretical minimum, binary fuse filters within 13%, against 44% for a Bloom filter (Graf and Lemire). Ribbon filters make the same trade, and RocksDB ships them (RocksDB wiki).

Two databases-section lessons belong to the same family: LSM Trees, which make writes sequential and lean on Bloom filters to skip files, and B-Trees and B+ Trees, which shape an index to the disk page. Consistent Hashing applies the same thinking to placing keys on machines.

Three tricks underneath

Nearly every structure here combines three ideas.

Hashing to spread items uniformly. A good hash turns any key into random-looking bits, so a fixed-size array can summarise an unbounded stream: Bloom filters set hashed bits, HyperLogLog picks a register and counts leading zeros, count-min increments hashed counters.

Accepting collisions and bounding their effect. Two items may land on the same bit or counter. The structure is designed so collisions push the error in one known direction (Bloom: a false "maybe present"; count-min: a count that is too high) and the size parameter controls how often.

Summaries that merge. Bloom filters with the same parameters combine with bitwise OR, HyperLogLogs by register-wise maximum, count-min sketches by adding counters. Each shard or hour builds its own summary, and a query merges them without touching raw data.

The spatial and ordered structures use hierarchical subdivision instead: split space or key order into levels so a query descends a few levels rather than scanning. Geohash and S2 turn two dimensions into a one-dimensional key that a B-tree can index.

Recognising the problem shape

This section is the "finding things fast" and "trust but verify" shapes at large scale. The membership question appears in a crawler checking if a URL was fetched and in a password service checking a breached-password list. The cardinality question appears in analytics, in a query planner estimating distinct values, and in counting distinct source IPs during an attack.

Down the stack

Layer 1The contract

Each probabilistic structure promises an error bound as a function of its size, and the bound is precise enough to test. A Bloom filter with m bits, n items and k hash functions has a false-positive rate near (1 - e^(-kn/m))^k, minimised at k = (m/n) ln 2, giving about 9.6 bits per key for 1% and 14.4 for 0.1% (Broder and Mitzenmacher). It never returns a false negative, unless items are deleted, which a plain Bloom filter does not support. HyperLogLog with m registers has a relative standard error of about 1.04 / sqrt(m), so 16,384 registers give 0.81% whether the true count is ten thousand or ten billion (Flajolet et al.). A count-min sketch with width ceil(e / eps) and depth ceil(ln(1 / delta)) overestimates any item's count by at most eps times the total count, with probability at least 1 - delta (Cormode and Muthukrishnan).

These bounds assume random hashing, not adversaries; untrusted input needs seeded or keyed hashes.

Layer 2The mechanism

The concrete layouts are small and specific. Redis stores a HyperLogLog as 16,384 six-bit registers, 12,288 bytes in the dense encoding, and uses a sparse run-length encoding while most registers are still zero; PFMERGE takes the per-register maximum (antirez). BigQuery exposes HyperLogLog++ sketches directly: HLL_COUNT.INIT takes a precision from 10 to 24, default 15, and the sketches can be stored and merged later, which plain APPROX_COUNT_DISTINCT cannot do (BigQuery docs). RocksDB attaches a filter to each SST file; the Bloom implementation introduced with format_version=5 (RocksDB 6.6) confines each key's probes to a single 64-byte cache line, and the Ribbon filter added in 6.15 saves about 30% of filter memory for 3 to 4 times the build CPU (RocksDB wiki). Cassandra keeps a Bloom filter per SSTable, off-heap, and lets you set bloom_filter_fp_chance per table: 0.01 by default, 0.1 under leveled compaction (Cassandra docs). Redis sorted sets use a skip list with span counters so rank queries are logarithmic. Git and Certificate Transparency logs are Merkle trees: change one byte in one file and every hash up to the root changes.

Layer 3The machine

These structures win because of the memory hierarchy. An L1 cache hit costs about 1 ns, L2 about 4 ns, a main memory reference about 100 ns. A 12 KB HyperLogLog fits in a 32 or 48 KB L1 data cache, so updating it is a hash plus one cache-resident write. A plain Bloom filter with k = 7 touches up to 7 random cache lines, about 700 ns if they miss, which is why blocked Bloom filters keep all probes in one 64-byte line for a small rise in false positives.

Exact structures pay per-entry overhead that dwarfs the key. A 64-bit ID is 8 bytes, but a Java HashSet<Long> spends around 50 bytes per entry on the boxed Long, hash node and table slot. A billion distinct IDs is tens of gigabytes; the HyperLogLog is still 12 KB. The network shows the same gap: merging HyperLogLogs from 200 shards moves 2.4 MB, while merging exact sets moves the data.

Why it's built this way

  1. Memory is fast but small, and the data is huge. So keep a compact summary in memory and the full data elsewhere.
  2. Exact answers need state proportional to the data. So for questions that tolerate error, trade exactness for state proportional to the accuracy wanted.
  3. Unbounded error is useless. So choose structures whose error is bounded, tunable by size, and ideally one-sided, so a cheap "no" can skip expensive work safely.
  4. Data is spread across machines and time. So prefer summaries that merge by OR, max or sum, and compute global answers from partial ones.

Diagram

flowchart TD
    Q["What must the system answer?"] --> M{"Membership?"}
    M -->|yes| X{"Exact set fits budget?"}
    X -->|yes| E["Hash set or index"]
    X -->|no| B["Bloom or cuckoo filter"]
    M -->|no| C{"Count distinct?"}
    C -->|yes| H["HyperLogLog"]
    C -->|no| F{"Frequency per item?"}
    F -->|yes| K["Count-min sketch"]
    F -->|no| S{"Near a point?"}
    S -->|yes| G["Geohash, quadtree, R-tree, S2, H3"]
    S -->|no| O["Skip list, Merkle tree, MinHash"]

Worked example

An ad platform reports daily unique users per campaign for 50,000 campaigns, plus weekly uniques that are not the sum of daily ones because the same user appears on several days.

Exact. Campaigns average 400,000 unique users a day. A hash set of 64-bit IDs at about 40 bytes per entry in a compact native implementation needs 50,000 × 400,000 × 40 bytes, which is 800 GB per day, and weekly uniques need the union of seven sets per campaign.

HyperLogLog. At precision 14, each campaign-day is 12 KB: 50,000 × 12 KB is 600 MB per day, with 0.81% standard error. A weekly figure is the register-wise maximum of seven daily sketches, still 12 KB and still 0.81%. Ninety days of history is 54 GB, small enough for an ordinary database column.

When to stay exact. Billing charges per unique user and must reconcile. The team keeps HyperLogLog for dashboards and computes exact uniques for invoiced campaigns in a nightly batch over raw logs: approximate for interactive questions, exact for money.

A second question. The platform must not show a user the same ad twice a day. A Bloom filter over user:ad pairs costs 9.6 bits per pair at 1% false positives. A false positive wrongly skips an ad, costing a little revenue but never annoying the user, so the one-sided error points the right way. The practice task turns this reasoning into a sizing tool.

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
Exact hash set or indexNo error, supports any later queryMemory grows with data, plus per-entry overheadData fits, or answers must reconcile exactly
Bloom or cuckoo filterBits per key, one-sided error, fastNo listing, plain Bloom cannot deleteCheap "definitely not" in front of expensive lookups
HyperLogLogFixed tiny size, mergeableOnly counts, cannot list itemsDistinct counts across shards and windows
Count-min sketchFixed size, mergeable, never undercountsOverestimates rare items under heavy loadHeavy hitters and rate tracking
SamplingSimple, supports many queriesMisses rare items; error depends on sampleExploratory analytics on huge datasets

Pitfalls in production

Leadership lens

Check yourself

  1. Why is a one-sided error more useful than a two-sided one of the same size?

    Show answer

    A one-sided structure gives one answer you can trust completely. A Bloom filter's "absent" is always right, so it can safely skip a disk read, and only the "maybe" answers pay for the exact check.

  2. Why does HyperLogLog use the same memory for ten thousand and ten billion distinct items?

    Show answer

    It stores a fixed number of registers, each holding the longest run of leading zeros seen; the error depends on the register count, not on the number of items.

  3. Two services each keep an hourly Bloom filter. How do you answer "seen in either hour" without the raw keys?

    Show answer

    If both filters use the same size and hash functions, OR them bit by bit; the result is the filter of the union. With different parameters you cannot merge them.

  4. Why can't a count-min sketch tell you which items are the most frequent on its own?

    Show answer

    It only answers point queries for items you name. Finding heavy hitters needs a small heap of candidates updated as items stream past.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →