CHAPTER 12
Algorithms and Data Structures for Scale
Probabilistic structures, geo-indexing, unique IDs and tools that appear in large system designs
Source: Chapter 12 PDF, pp. 1–7
Learning objective
Recognize the problem a data structure solves, understand its trade-offs, and know when to use it in a system design.
PDF page 11. Why do large systems need specialized data structures? p. 1
Imagine a website with one billion users. You want to know whether a URL has been seen, estimate unique visitors, find trending topics, locate nearby drivers, or generate unique IDs across many servers. A straightforward solution may use too much memory, take too long, or require too much coordination.
2. Bloom filters: "definitely not" or "possibly present" p. 1
A Bloom filter is a compact structure that helps determine whether an item may belong to a set. It uses several hash functions to set bits in a bit array.
- Definitely absent: the item is not in the set, so the application can safely skip the source lookup.
- Possibly present: the item may exist; check the actual data source to confirm.
A standard Bloom filter can produce false positives, but it does not produce false negatives when used correctly. A false positive means an absent item is reported as possibly present; the database still protects correctness.
PDF page 23. Sketches: estimate huge datasets cheaply p. 2
Some systems need useful estimates rather than exact answers. A sketch summarizes a large stream using limited memory, with a defined approximation or error profile.
| Structure | Question answered | Typical use | Important trade-off |
|---|---|---|---|
| Bloom filter | Is x present? | Skip unnecessary lookups | False positives possible; no false negatives in standard use |
| HyperLogLog | How many distinct items? | Unique visitors, distinct counts | Approximate count; compact memory |
| Count-Min Sketch | How often did x occur? | Frequent searches, rate limiting | Basic estimates can overcount |
| Top-K / Space- Saving | Which k items are most frequent? | Trending hashtags, leaderboards | Bounded memory; guarantees depend on algorithm |
| t-digest / HDR histogram | What are latency percentiles? | p95/p99 across services | Compact summaries; approximation differs by method |
| Reservoir sampling | How to sample a stream of unknown size? | Representative log or trace samples | Stores only a bounded sample |
| MinHash / SimHash / LSH | Which items are similar? | Near-duplicate documents and crawl deduplication | Similarity is approximate |
PDF page 34. Finding nearby locations efficiently p. 3
Imagine a delivery app searching for drivers within 2 km of a customer. Calculating the distance to every driver may be expensive at large scale. A geospatial index narrows down candidates first; the application then calculates exact distances for the final selection.
Grid-based indexes p. 3
| Index | How it works | Consideration |
|---|---|---|
| Geohash | Encodes latitude/longitude into a string; longer shared prefixes often indicate proximity. | Nearby points can fall across cell edges, so query neighboring cells too. |
| S2 | Divides the globe into hierarchical spherical cells. | Supports hierarchical location and region queries. |
| H3 | Uses hierarchical hexagonal cells. | Useful for neighborhood and regional aggregation. |
Adaptive spatial indexes p. 3
- Quadtree: recursively subdivides dense map regions into smaller areas while leaving sparse regions larger.
- R-tree: organizes spatial objects by bounding boxes; used for spatial queries such as intersections and nearby regions.
For frequently moving drivers, a hot in-memory grid or Redis geospatial feature can maintain current locations between updates.
PDF page 45. Generating unique IDs across many servers p. 4
If many application servers create orders at once, asking one central database counter for every ID can add coordination and contention. A distributed ID generator can let workers create IDs independently while preserving the required uniqueness guarantees.
| Method | Advantages | Trade-offs |
|---|---|---|
| Database auto- increment | Simple, compact, ordered | Central contention; sequence can reveal volume; harder across shards |
| UUID v4 | Random IDs; no coordination needed | 128-bit; not time-sortable; can have worse index locality |
| UUID v7 / ULID | Time-oriented ordering and index-friendly behavior | 128-bit; ordering depends partly on clock behavior and format |
| Snowflake / Sonyflake | 64-bit, time-sortable, distributed generation | Worker-ID coordination and clock discipline required |
| Ticket server / ID ranges | Workers lease blocks of IDs to generate locally | Gaps possible; range allocator remains a dependency |
How a Snowflake-style ID works p. 4
The identifier typically combines a timestamp, a worker identifier and a sequence number. The timestamp supports approximate time ordering, worker identity distinguishes generators, and the sequence allows multiple IDs within the same time unit. The supplied design describes a configuration capable of about 4,096 IDs per millisecond per node, or roughly 4 million per second. This is configuration-specific, not a universal guarantee.
PDF page 56. Other data structures that appear in system design p. 5
Focus on the operation each structure makes efficient rather than memorizing implementation details.
| Structure / idea | Plain-English purpose | Example |
|---|---|---|
| Trie / radix tree | Organizes strings by shared prefixes | Autocomplete |
| Skip list | Keeps ordered data with efficient search and updates | Sorted in-memory collections |
| Merkle tree | Compares data using hashes of groups of records | Replica repair and integrity verification |
| Consistent / rendezvous hashing | Assigns keys to nodes while limiting remapping when nodes change | Distributed caches and partitioning |
| Content-defined chunking + rolling hash | Splits files at content-dependent boundaries | Deduplication and delta sync |
| Inverted index | Maps terms to documents | Full-text search |
| Heap / priority queue | Efficiently retrieves highest or lowest priority item | Scheduling and top-K |
| LRU: hash map + doubly linked list | Supports constant-time lookup and recency updates in a standard implementation | LRU cache |
| Reed-Solomon / erasure coding | Adds recovery fragments rather than storing full duplicate copies | Durable distributed storage |
| HNSW / IVF / product quantization | Speeds up approximate nearest-neighbor search over vectors | Semantic search and RAG |
Trie: follow a shared prefix p. 5
Merkle tree: narrow down differing data p. 5
A Merkle tree lets replicas compare hashes from the root downward. If the root hashes differ, the system compares child hashes to narrow down which ranges need repair.
PDF page 67. More structure examples p. 6
Heap / priority queue p. 6
A heap keeps the item with the highest or lowest priority at the root, so the next job can be retrieved efficiently without fully sorting all waiting jobs after every change.
Other concepts to recognize p. 6
8. How do you choose the right structure? p. 6
| If you need to… | Consider… |
|---|---|
| Avoid lookups for missing items | Bloom filter |
| Estimate unique visitors | HyperLogLog |
| Find frequent items | Count-Min Sketch or Top-K |
| Find nearby locations | Geospatial index |
| Generate IDs on many servers | Snowflake-style IDs or UUIDs |
| Find similar content | MinHash / SimHash / LSH, or vector ANN indexes depending on the task |
| Compare replica data | Merkle tree |
| Pick the next urgent job | Heap / priority queue |
PDF page 7Chapter recap p. 7
- Bloom filters answer "definitely not" or "possibly present."
- Sketches estimate distinct counts, frequencies, percentiles and samples with limited memory.
- Geospatial indexes narrow down nearby candidates efficiently.
- Distributed ID generators issue unique identifiers without a central request for every ID.
- Tries, heaps, Merkle trees and inverted indexes solve different search, ordering and comparison problems.
- Erasure coding improves storage efficiency while preserving recovery capability.
- Approximate nearest-neighbor indexes accelerate similarity search over embeddings.
Check your understanding p. 7
| Question | Options | Answer and why |
|---|---|---|
| 1. Avoid lookups for keys that may not exist? | A. Bloom filter B. Priority queue C. Trie | A — Bloom filter. It can identify definitely absent items. |
| 2. Estimate unique visitors across billions of events? | A. HyperLogLog B. LRU cache C. Merkle tree | A — HyperLogLog. It estimates distinct counts compactly. |
| 3. Find nearby delivery drivers? | A. Bloom filter B. Geospatial index C. Priority queue | B — Geospatial index. It narrows the candidates before exact distance checks. |
| 4. Generate time-sortable IDs across workers? | A. Snowflake-style ID B. SQL encryption C. HyperLogLog | A — Snowflake-style ID. It combines time, worker identity and a sequence. |
| 5. Compare data across replicas efficiently? | A. Merkle tree B. Rate limiter C. UUID v4 | A — Merkle tree. Hashes help narrow down differing ranges. |
| 6. Retrieve the highest-priority job efficiently? | A. Heap / priority queue B. Bloom filter C. HyperLogLog | A — Heap / priority queue. It exposes the next priority item efficiently. |
Review questions for this chapter have not been written and reviewed yet. The chapter text above is the full source content.
References
Chapter 12 PDF, pp. 1–7; figures 1, 2, 3, 4, 5, 6, 7.
Tip: use ← and → keys to move between chapters.