Summary and key takeaways
The currencies
| Currency | Where it appears | What it buys |
|---|---|---|
| Read, write and space (the RUM triangle: optimize any two and the third degrades) | Lookup and ordering structures (Lookup structures and Ordering structures) | Fast point lookup, fast range scans, or fast ingest, never all three |
| Correctness | Probabilistic structures (Probabilistic structures) | A change of complexity class: tiny state for distinct counts, membership, frequencies, quantiles, similarity |
| Space turned into speed | Bit-level and succinct structures (Bit-level structures) | Compact data that is queryable in compressed form; compactness pays at memory-tier boundaries |
| Coordination | Concurrency-friendly structures (Concurrency-friendly structures) | The only cost that grows superlinearly (and can go negative) with the resources you add |
What each article taught, in one line
- The big picture: structures are bets priced in read, write and space amplification; the medium charges per dependent fetch.
- Lookup structures: hash tables follow the queueing curve of the load factor; B+trees have a fanout set by page size (about 680 for 16 KB); LSM-trees buy write throughput with compaction amplification; tries, skip lists, sparse indexes, perfect hashing and interval trees each fit one question.
- Ordering structures: a bounded heap answers top-k in O(n log k) with tiny memory; external sort is set by fan-in and range partition boundaries; merge is the universal primitive; sliding windows depend on the algebra class of the aggregate.
- Probabilistic structures: Bloom, cuckoo and XOR filters give one-sided membership answers; Count-Min, HyperLogLog, t-digest, reservoir sampling and top-K trade a controlled error for tiny, mergeable state; error falls as 1/√m.
- Bit-level structures: roaring bitmaps, rank/select and succinct structures stay queryable while compressed; zone maps work only if data is clustered.
- Concurrency-friendly structures: partition to a single writer, do not mutate, or gamble and retry, in that order of preference. False sharing (a 40–100× penalty) is physical contention with an address. Safe reclamation is bounded by the slowest reader.
- Putting the pieces together: four compositions cover most real systems.
The four compositions
- Pruning cascade: zone map, Bloom filter, sparse index, block scan; each stage has one-sided error and is cheaper than the next.
- Buffer-runs-merge: mutable buffer, immutable sorted runs, background merge, a manifest and a collector; the merge policy is the RUM dial.
- Columnar stack: dictionary, bit-packing or run-length encoding, statistics, optional byte codec; encode first, compress last.
- Partition, localize, merge: range-partition, run a local structure, merge; skew is the universal failure.
The laws
| Law | In one sentence |
|---|---|
| Mismatch law | A gap between what you want and the unit the machine handles creates amplification; stacked layers multiply it |
| Batch-size law | Fixed cost per operation gives a natural batch size; as hardware speeds up, the fixed cost moves up into software |
| Little's Law | In-flight work = throughput × latency |
| Conservation of cost | Costs are never removed, only moved |
| Variance law | Variance costs more than volume |
| Immutability law | A layout that cannot update in place grows an indirection layer and a collector, and the collector's progress is bounded by the slowest reader |
| Growth law | A fixed rate meeting exponential growth breaks designs |
| Independence law | Independence is assumed everywhere and true almost nowhere |
| Queueing law | Contended resources cost 1/(1 − ρ): flat, then vertical |
| Randomization law | Randomness can replace coordination, at a price in worst-case guarantees |
| Approximation law | Error ∝ 1/√m: four times the memory halves the error |
| Homomorphism law | Only operations that can be combined from partial results distribute |
| Tier-boundary law (candidate) | Compactness pays discontinuously, at memory-tier boundaries |
| Physical-contention law | Contention is set by which cache lines are written, not by which operations conflict |
Equations worth remembering
| Equation | Meaning |
|---|---|
| fanout ≈ page size ÷ (key + pointer size) | How many keys one page-sized node can route |
| linear-probing miss ≈ ½(1 + 1/(1−α)²) | Hash table cost at load factor α: 2.5 probes at 0.5, about 50 at 0.9 |
| WAF-like ratio: page size ÷ row size | Amplification when you update one row in a page |
| Concurrency = Throughput × Latency | How many requests to keep in flight; also the size of a bounded queue |
| C(N) = N / (1 + α(N−1) + βN(N−1)), peak at N* = √((1−α)/β) | Coordination makes throughput peak and then fall |
Patterns that repeat
- Match granularity to the transfer unit (fanout, fan-in, page size, padding, batch publishing).
- Immutable layout ⇒ indirection layer + collector, from SSD translation layers to LSM manifests, table snapshots, MVCC and memory reclamation.
VACUUM RETAIN 168 HOURSand a hazard-pointer scan are the same mechanism 12 orders of magnitude apart. - Make growth not relocate (extendible hashing, consistent hashing, split-ordered lists).
- Bin the domain; discard the dominated; adapt the representation to local density; use two random choices.
- Rebuild-only structures are free riders inside systems that already rebuild.
- When the bet is wrong the loss is a cliff, not a slope: spills, full scans, degenerate joins, useless zone maps, retry storms. Averages hide cliffs; watch the tail and the skew.
Parcelo in the end. Arjun's one-page design: single-writer shards with SPSC rings; a buffer-runs-merge write path with leveled merging; a pruning cascade for reads; a columnar stack with mergeable sketches for reports; persistent index snapshots with epoch reclamation. For each choice he can state the bet, the currency, and the cliff.