Lesson 02 · Partitioning & tail latency
Choosing Your Failure Mode
Discord has moved its messages between three databases in seven years. The interesting part is not which one they landed on — it is that the same mistake followed them across all three, because it was never in the database. It was in the key.
The win in this lesson: you will be able to look at a proposed partition key and predict the shape of the outage it will cause — and know why the graph that proves it is a p99, never an average.
1. The other way to add machines
Lesson 01 was about replication: make copies. Every replica holds the whole dataset, which buys read capacity and survivability, and buys you exactly nothing on writes — every replica still has to apply every write.
Partitioning is the other move: split the data, so each machine holds a slice and every machine takes a share of the writes. This is the only thing that buys write capacity, and the price is a decision you can never take back cheaply: which slice does a given row belong to? That decision is the partition key.
2. Discord's first two answers
They started on MongoDB. It failed at around 100 million stored messages, in a way worth memorising because it is the standard shape of a database outgrowing one box:
"the data and the index could no longer fit in RAM and latencies started to become unpredictable"
Discord, How Discord Stores Billions of Messages (2017)
Before picking a replacement they wrote down requirements — and this list is worth stealing wholesale, because it is a design doc doing its job in seven lines, quoted here in full:
- Linear scalability — "We do not want to reconsider the solution later or manually re-shard the data."
- Automatic failover — "We love sleeping at night and build Discord to self heal as much as possible."
- Low maintenance — "It should just work once we set it up. We should only have to add more nodes as data grows."
- Proven to work — "We love trying out new technology, but not too new."
- Predictable performance — "We have alerts go off when our API's response time 95th percentile goes above 80ms. We also do not want to have to cache messages in Redis or Memcached."
- Not a blob store — "Writing thousands of messages per second would not work great if we had to constantly deserialize blobs and append to them."
- Open source — "We believe in controlling our own destiny and don't want to depend on a third party company."
"Cassandra was the only database that fulfilled all of our requirements."
Three of these repay a second read. Predictable performance fixes the number that defines "working" as a percentile, not a mean — in 2015, before any of the trouble started. That is what made the failure in §5 visible at all.
Proven to work — "we love trying out new technology, but not too new" — is a requirement most teams feel and few write down. Putting conservatism on the list makes it reviewable rather than a matter of whoever argues hardest.
And Open source ("controlling our own destiny") is the line that quietly decides the 2023 ending. A team that requires the ability to own its stack is a team that can migrate when the runtime turns out to be the problem.
Buried in the tail of a performance requirement, Discord rules out the entire Lesson 01 architecture — no look-aside cache, no invalidation, no staleness window. Three reasons, and the third is the one worth carrying around.
The reads are random, so a cache has nothing to hold. They describe the workload as "extremely random", roughly 50/50 read/write, and getting worse: "the ability to view your mentions for the last 30 days then jump to that point in history, viewing plus jumping to pinned messages, and full-text search." A look-aside cache pays off when a hot working set is hit repeatedly. Scattered reads across trillions of historical messages give a poor hit rate no matter how much RAM you buy.
The part that is hot is already cached, for free. Their own measurement: big servers "almost always are requesting messages sent in the last hour and they are requesting them often. Because of that the data is usually in the disk cache." That is the operating system's page cache, with no cluster to run and nothing to invalidate. A Redis layer would pay to duplicate the kernel's cache in a second system. The hot set is handled; the cold set is not cacheable; there is no middle where the cache earns its keep.
And a cache cannot answer a percentile requirement anyway. Note where the sentence sits — immediately after "alerts go off when our API's response time 95th percentile goes above 80ms". A cache lifts the average; every cold read still pays full price, so the tail barely moves. "We'll put a cache in front of it" is a way to make a mean look healthy while the slow requests stay exactly as slow. If you need a cache to meet a p95 target, you chose the wrong store — and you will find out during the incident, not during the benchmark.
They chose Cassandra, and keyed messages on (channel_id, message_id). Which broke, for a
reason that had nothing to do with Cassandra.
3. What a partition key actually does
A composite key in this family of databases does two completely different jobs, and conflating them is where most bad keys come from. Discord's own framing is the clearest one-liner on it:
"The best way to describe Cassandra to a newcomer is that it is a KKV store. The two Ks comprise the primary key. The first K is the partition key and is used to determine which node the data lives on and where it is found on disk."
Discord, 2017
The partition key — a placement decision
The partition key is hashed. The resulting number picks a position on a ring of nodes, and that position — plus the next two around the ring, for a replication factor of three — is where the data lives. Nothing about the value matters except its hash, so you cannot reason about "nearby" keys: consecutive channel ids land nowhere near each other, deliberately.
Three consequences follow, and they are the whole reason this key deserves a design review of its own:
- Co-location. Every row sharing a partition key is stored together, on the same replicas, contiguously on disk. That is what makes reading one channel cheap.
- Every query must supply it. Give the database the partition key and it goes straight to three nodes. Omit it and there is nowhere to look but everywhere — a scatter-gather across the whole cluster, which gets worse as you add machines. The key is effectively a contract about how the data may be asked for.
- It is permanent. Changing it changes where every row belongs, so it means rewriting every row you have. Discord never did — the key below is still the key they run today, hot partitions and all. §7 explains what they did instead.
The clustering key — a layout decision
Inside a partition, the clustering key decides the order rows are physically stored in:
"The clustering key acts as both a primary key within the partition and how the rows are sorted. You can think of a partition as an ordered dictionary."
Discord, 2017
"Ordered dictionary" is exactly right, and it pays off in one specific way: a range of rows is a contiguous read, not a query plus a sort. "The last fifty messages in this channel" becomes: hash the partition key, seek, walk backwards fifty rows, stop. Discord's phrasing — "when loading a channel we could tell Cassandra exactly where to range scan for messages."
The catch: that order is fixed at write time. A partition has one physical ordering, so "sort these messages by author" is not a variation on this query — it is a different table.
| Partition key | Clustering key | |
|---|---|---|
| Decides | Which nodes hold the row | The order of rows within those nodes |
| Scope | Global — placement across the cluster | Local — layout inside one partition |
| Applied by | Hashing | Sorting |
| If a query omits it | Scatter-gather across every node | Fine — you just read the whole partition |
| Changing it later | Rewrite every row in the dataset | A new table, or a migration |
| Failure it causes | Hot partitions | An awkward query, at worst |
Which is the sentence at the foot of the diagram, spelled out: the clustering key is a performance detail you can revisit. The partition key is a distribution decision you are married to. When reviewing a schema, spend your attention accordingly.
Their first key, (channel_id, message_id), put one partition per channel — unbounded, growing
forever. So they bucketed it:
"We decided to bucket our messages by time" — giving
Discord, 2017. The target was partitions under 100 MB, because "Large partitions put a lot of GC pressure on Cassandra."((channel_id, bucket), message_id), with the interval chosen to hold "about 10 days of messages within a bucket".
That fixed unbounded growth. It did not fix the thing that eventually took them off Cassandra entirely.
4. The failure bucketing cannot fix
Bucketing bounds how big a partition gets. It does nothing about how busy one is. And traffic is not distributed like data:
"a server with just a small group of friends tends to send orders of magnitude fewer messages than a server with hundreds of thousands of people"
Discord, How Discord Stores Trillions of Messages (2023)
This is a hot partition, and the mechanism is worth stating precisely, because it is not "the cluster got busy". A partition key routes every request for that channel-and-bucket to the same three nodes. Adding nodes to the cluster does not help: the key still points at the same three. You can have 175 idle machines and an outage.
"One channel and bucket pair received a large amount of traffic, and latency in the node would increase as the node tried harder and harder to serve traffic and fell further and further behind."
Discord, 2023
A partition key is a bet that your traffic is distributed like your data. Discord keyed on channel, and channels are made by people — so the distribution is not uniform, it is a power law. Any key derived from a human-chosen grouping will be skewed: tenant, customer, account, organisation, video, celebrity user. The uniform-looking key is nearly always the one nobody wants to query by.
They never did. The ScyllaDB cluster runs the same
((channel_id, bucket), message_id) as the Cassandra one — ScyllaDB is schema-compatible, and
the migration deliberately changed the store and nothing else.
Because the key is not wrong. Every read is "messages in this channel", so
channel_id has to be in the partition key; drop it and every read becomes a scatter-gather.
The usual escape is salting — (channel_id, bucket, salt) spreads one hot channel over
N partitions — but then every read on every channel must fan out to N partitions and merge, in
order to fix the handful that are hot. You would tax the entire workload to protect the tail.
So the skew is not a mistake in the schema. It is a property of the domain: people gather in big rooms, and the query pattern demands you key by room. The key is correct and skewed at the same time — and recognising that case is what stops a design review from chasing a schema change that cannot exist.
5. Why the graph has to be a p99
Now the part that makes hot partitions a systems lesson rather than a Cassandra anecdote. Suppose 99.5% of your channels are fine and a handful are on fire. Your average latency is excellent. It will stay excellent right up until the incident review, because the healthy majority drowns the broken minority in the mean.
The p99 — the latency the slowest 1% of requests experience — is the only number that moves. And Discord's fourth requirement, written in 2015, was already an alert on the 95th percentile exceeding 80 ms. They instrumented for this class of failure before they had it.
Here is what it was worth to them, in the numbers they published after moving to ScyllaDB:
| Cassandra | ScyllaDB | |
|---|---|---|
| Historical message read, p99 | 40–125 ms | 15 ms |
| Message insert, p99 | 5–70 ms | 5 ms |
| Nodes in the largest cluster | 177 | 72 |
| Disk per node | ~4 TB | 9 TB |
Read the Cassandra column as ranges, not numbers. "40–125 ms" is not imprecision — it is the symptom. Unpredictability was the outage, and a steady 15 ms would have been an improvement even if the average had not moved at all.
6. The second villain: garbage collection
Cassandra runs on the JVM. Large partitions and heavy traffic meant heap pressure, and heap pressure meant the garbage collector stopping the world at the worst possible moment:
"super long consecutive GC pauses that got so bad that an operator would have to manually reboot and babysit the node in question back to health"
Discord, 2023
By early 2022 the cluster was 177 nodes holding trillions of messages and was, in their words, "a high-toil system — our on-call team was frequently paged for issues with the database, latency was unpredictable". The compaction backlog was bad enough to need a ritual they named: the gossip dance, where "we'd take a node out of rotation to let it compact without taking traffic."
ScyllaDB is Cassandra's data model and protocol reimplemented in C++ with a shard-per-core architecture and no JVM — so the GC pause class of failure disappears by construction rather than by tuning. That is the actual argument for the migration: not "faster", but "one entire failure mode removed".
7. The fix that was not a database
Here is the part most summaries skip, and it is the most reusable thing in the whole story. Swapping the database could not fix hot partitions — same key, same skew — and Discord says so without flinching: "We're still seeing hot partitions and increased latency on our Cassandra cluster, just not quite as frequently." Less often is the whole claim. So they also changed the shape of the workload arriving at the store, with an intermediate layer of data services written in Rust:
"If multiple users are requesting the same row at the same time, we'll only query the database once. The first user that makes a request causes a worker task to spin up in the service. Subsequent requests will check for the existence of that task and subscribe to it."
Discord, 2023
And one detail makes the whole thing work, which is easy to read past:
"consistent hash-based routing to our data services to enable more effective coalescing… all requests for the same channel go to the same instance of the service"
Discord, 2023
Coalescing can only merge requests that meet. Spread the same channel's traffic across twenty service instances and each sees a thinly-scattered handful, merging almost nothing. So they deliberately concentrated a hot channel onto one instance — the opposite of load balancing — because the win from merging beats the cost of the hotspot they just created.
This is the same family as the thundering herd you will meet in the next lesson: N simultaneous identical requests for something expensive, collapsed into one. Facebook solved it inside the cache with leases. Discord solved it in a service layer with subscriptions. The generalisation: when a miss is expensive, the second concurrent asker should wait for the first, not race it. Reach for this any time a cache miss, a cold start, or a slow query can be requested by many callers at once.
Put the two moves together and neither one removes the hot partition. Coalescing means fewer duplicate requests reach it; a C++ shard-per-core runtime means that when one does get hammered, the node degrades instead of falling into GC pauses that need an operator to nurse it back. The pressure is inherent to the domain and stays. What they removed was the machinery that turned pressure into an outage — which is what most real systems work looks like, and it is worth saying out loud in a design review rather than promising a fix you cannot deliver.
8. Check yourself
Two of these are from Lesson 01. That is deliberate — mixing old material into new practice is harder and works better than reviewing it in a block.
9. Back to your world
You will meet this long before you run 177 nodes. The moment anything is keyed by tenant, customer, account, or organisation — a queue partitioned by customer, a rate limiter bucketed by account, a cache keyed by workspace — you have made the same bet Discord made, and the same power law is waiting. The question to carry out of this lesson: what is the biggest one of these, how much bigger is it than the median, and what breaks when it doubles?