Reference · quick sheet

The Partitioning Playbook

Choosing a partition key, and recognising the outage when it was the wrong one.

Vocabulary

Partitioning (sharding)

Splitting data so each machine holds a slice. The only move that buys write capacity. Orthogonal to replication, which copies and buys reads.

Partition key

Hashed to pick a position on the node ring; that position and its neighbours hold the row. Rows sharing it are stored together and contiguously. Every query must supply it or become a scatter-gather that gets worse as the cluster grows. Changing it means rewriting the dataset.

Clustering key

The physical sort order of rows inside one partition — "an ordered dictionary". Makes a range of rows a contiguous read rather than a query plus a sort. One ordering per partition, fixed at write time; a different order is a different table.

Snowflake id

An id with its creation time in the high bits, so sorting by id is sorting by time. Lets one column serve as both identity and clustering order.

Hot partition

One partition receiving disproportionate traffic. Adding nodes does not help: the key still routes to the same replicas. You can have an idle cluster and an outage simultaneously.

p99

The latency the slowest 1% of requests see. The only metric that moves when a small number of requests fail badly — which is exactly the shape of a hot partition.

Request coalescing

Collapsing N concurrent identical requests into one: the first spawns the work, the rest subscribe to its result. Does the most work where load is heaviest.

Tombstone

A marker that a row was deleted, kept until compaction removes it. Until then it still has to be read in order to be skipped.

Discord's requirements list (2017) — a template worth stealing

• Linear scalability — no manual re-sharding later
• Automatic failover — "we love sleeping at night"
• Low maintenance — growth should mean adding nodes, nothing else
• Proven to work — "new technology, but not too new". Write your conservatism down.
• Predictable performance — alert on the 95th percentile, not the mean. And: no cache in front, the store must be fast enough by itself.
• Not a blob store — the write pattern must suit the engine
• Open source — "controlling our own destiny"; the line that made the 2023 migration possible

Choosing a key

1. Name the access pattern first. The key must contain whatever every read filters by, or every read becomes a scatter-gather across the cluster.
2. Bound the partition's size. Anything that grows forever needs a second component — usually a time bucket. Discord targeted <100 MB per partition.
3. Now bound its traffic. Size and heat are different problems, and bucketing only fixes the first.
4. Assume a power law. Any key derived from a human grouping — tenant, customer, account, channel, video, celebrity user — is skewed. The uniform key is usually the one nobody queries by.
5. Ask what happens when the biggest one doubles. If the answer is "we add nodes", check that adding nodes actually helps. For a hot partition it does not.

Spotting it

• Latency quoted as a range ("40–125 ms") rather than a number. Unpredictability is the symptom.
• p99 climbing while the mean is flat. Alert on percentiles; a mean over a skewed population reports health during a partial outage.
• One node hot, the rest idle. Not a capacity problem — a routing problem.
• Rituals with names ("the gossip dance"). A recurring manual remedy is a design defect with a nickname.

Fixes, and what they cost

Discord, in numbers