Putting the pieces together: the five currencies and the four compositions
Which few fixed arrangements explain how real systems combine these structures?
This mechanism in one frame
This mechanism spent five currencies, and the groups map onto them almost exactly.
| Group | Currency spent | What it buys |
|---|---|---|
| Lookup and ordering structures (Lookup structures and Ordering structures) | Read, write and space, traded against each other inside the RUM triangle | Fast lookup or fast order, at the price of the other two |
| Probabilistic structures (Probabilistic structures) | Correctness | Leaving the triangle: the complexity class of the state changes (for example, a count of distinct values in a few KB instead of GB) |
| Bit-level and succinct structures (Bit-level structures) | Space turned into speed | At the bit level the space/time trade inverts: compactness becomes speed, because the machine is bandwidth-bound and packed data is processed many values per word |
| Concurrency-friendly structures (Concurrency-friendly structures) | Coordination | The only currency whose cost is superlinear in the resources you spend on it |
Every structure here is a bet about the access distribution, priced in some combination of those five currencies. The failure mode is the same everywhere: when the bet is wrong, the loss is not proportional. It is a cliff. Examples are spills to disk, full scans, a range join that becomes a cross product, useless zone maps, and retry storms. The structure had no graceful middle because nobody designed one.
The compositions matter more than the pieces
After five groups, the honest observation is that the pieces are not independent. They combine in a small number of fixed ways, and the compositions carry more information than the individual structures. Four patterns cover most of what gets built.
The pruning cascade
Each stage is a cheaper test than the next. Each stage has one-sided error: it can only produce false positives ("maybe there") and never false negatives ("not there, but you said yes" is allowed; "there, but you said no" is not). Each stage is ordered by cost per unit of selectivity (how much data it lets you skip per unit of effort).
That ordering is not a convention. It is forced. A stage with false negatives would break correctness. A stage more expensive than the one it guards would be dead weight, because you would do better to run the guarded stage directly.
Every modern storage engine's read path is this cascade. Once you see it as one pattern, the zone maps, the Bloom filters of Probabilistic structures and the sparse index of Lookup structures stop being three topics.
Rows examined: about 8,192 out of 5,000,000,000, which is a fraction of 0.00016%.
The buffer-runs-merge write path
LSM-trees, Lucene (the search library behind Elasticsearch), Iceberg tables and the state backends of stream processors are all instances. The only real variable is the merge policy, and the merge policy is the RUM dial: merge often and reads are cheap but writes are amplified; merge rarely and the reverse.
The columnar stack
Encoding goes first because it preserves queryability (you can still filter on the encoded values). General-purpose compression goes last because it does not (you must decompress a block before you can look inside it).
Partition, localize, merge
Distributed sort, shuffle joins, sharded indexes, parallel aggregation and sketch rollups are all this pattern. Its universal failure mode is skew: one partition gets far more than its share, and the whole job waits for it. Concurrency-friendly structures's single-writer shards are the same pattern, applied inside one machine.
| Composition | Pieces | The bet | Failure mode |
|---|---|---|---|
| Pruning cascade | zone map, Bloom, sparse index, scan | Most data can be skipped by cheap one-sided tests | Data not clustered, so nothing is skipped |
| Buffer-runs-merge | buffer, sorted runs, merge, manifest, collector | Writes can be batched; reads can tolerate several runs | Merge falls behind; the slowest reader blocks cleanup |
| Columnar stack | dictionary, bit-pack/RLE, statistics, codec | Queries touch few columns and the data is repetitive | High-cardinality, random data compresses poorly |
| Partition-localize-merge | range partition, local structure, merge | Keys spread evenly | Skew |
One practical rule follows from the compositions. Keep three decisions separate in any design discussion: physical layout and the decision to cluster data, the structure that indexes it, and what happens when it exceeds memory. Without this separation, sorted runs, zone maps and hash tables get described three times under different names.
Only homomorphisms distribute
The partition-localize-merge pattern works only when the partial results can be merged, and one law says when that is. We call it the Homomorphism law. An aggregate can be computed in parallel, incrementally, or over a window if and only if it is a homomorphism from the data's merge operation into a bounded state with an associative merge. (Associative means (a + b) + c = a + (b + c), so partial results can be combined in any grouping.) That single condition explains:
- map-side combiners and two-phase aggregation (partial sums per worker, then add);
- incremental view maintenance;
- mergeable sketches;
- state-based CRDTs (replicated data types whose copies converge by merging);
- the invertible/decomposable/holistic classification from monotonic windows, which was this law in a special case.
It also tells you at once why the median resists everything that sum accepts: there is no small state from which two medians can be merged into the median of the union.
And one connection worth making explicit. A mergeable sketch whose merge is associative, commutative and idempotent is a state-based CRDT. HyperLogLog is a join-semilattice over register vectors: merging is element-wise max, and merging a vector with itself or in any order gives the same result. This is not an analogy. It is the same algebraic object. It is the deep reason these structures tolerate retries, reordering and duplicate delivery without any coordination between replicas.