Cassandra's Compaction Wars
Sources (19)Watch it on YouTube ↗
Contents
- Three bills on one node
- Size-tiered: cheap writes, a double disk
- When the space isn’t there
- Leveled: small merges, many rewrites
- One rule, two waits
- Pricing the two ends
- Why leveled falls behind, and what UCS does instead
- Density and shards cut the disk bill
- A delete is a write
- Zombies and gc_grace_seconds
- Time windows: deleting whole files
- Should you pick Cassandra in 2026?
- Choosing a compaction setting
- Sources and further reading
At the beginning of 2022, Discord kept its messages in Cassandra: 177 nodes with trillions of messages, and in their own words “a high-toil system”. The problem that kept coming back was compaction:
We were prone to falling behind on compactions, where Cassandra would compact SSTables on disk for more performant reads. Not only were our reads then more expensive, but we’d also see cascading latency as a node tried to compact.
Their workaround had a name, the gossip dance. They would “take a node out of rotation to let it compact without taking traffic, bring it back in to pick up hints from Cassandra’s hinted handoff, and then repeat until the compaction backlog was empty.”
A database that has to be pulled out of service to tidy its own files is paying a bill somewhere. Over the years Cassandra has shipped five compaction strategies, and each one is a bet on which bill hurts least.
Three bills on one node
Cassandra combines Amazon Dynamo’s replication with Google Bigtable’s storage model: each row’s key is hashed onto a ring of nodes, each row lives on several replicas (three, in Discord’s case), and every node runs its own LSM tree. Writes land in an in-memory table, get flushed to disk as immutable sorted files called SSTables, and a background process, compaction, merges those files. Each node compacts on its own.
Compaction exists to trade one cost for another. The RUM conjecture says you can lower two of read cost, write cost and space cost, never all three. On a single node, those three costs become three things you can watch:
- Files per read: how many SSTables a lookup may have to check.
- Rewrites per byte: how many times compaction copies the same data.
- Disk: the room the files take, plus the room a merge needs while it runs.
Discord’s problem was the first one. When compaction falls behind, flushed files pile up and every read digs through more of them.
There are two classic shapes for doing that job. Tiered compaction is a messy desk: let piles of similar size grow, then merge them. Few rewrites, but a read has to check every pile. Leveled compaction is a set of shelves: a read checks one file per level, but you are always rewriting to keep them tidy.
Size-tiered: cheap writes, a double disk
Cassandra started on the desk. Its size-tiered strategy waits for “a set number (default: 4) of similar-sized SSTables” and merges them into one. Jonathan Ellis described it in 2011 as “very similar to the one described in Google’s Bigtable paper”, and it is still what a table gets when it asks for nothing else.
Follow a node as it fills. Four small files merge into a medium one, four medium ones into a large one. In 2017 Discord ran nearly 1 TB of compressed data on each node; on a node like that, the top pile ends up with files of a couple of hundred gigabytes each.
When those four merge, the output is written as a brand new file, and the inputs cannot be deleted until it is complete. Reads are still served from them, and if the node crashes halfway through, nothing may be lost. For the length of that merge, the node holds the same data twice.
The STCS documentation admits it: “the amount of disk space needed for both the new and old SSTables simultaneously during STCS compaction can outstrip a typical amount of disk space on a node.” Cassandra’s release notes for 1.0 put a number on the worst case: 50% of the disk kept free. A terabyte of data wants a two-terabyte disk.
This is not the space amplification you get at rest, where old versions of a key wait in upper levels for compaction to reach them. It is temporary: it exists only while a merge runs, and it is as large as the merge itself.
When the space isn’t there
Before each compaction, Cassandra estimates the size of the output. If it won’t fit, it logs “insufficient space to compact all requested files”, removes the largest input and tries again. If nothing fits, the compaction is aborted with “Not enough space for compaction”.
Notice which file gets left out: the biggest one, which holds the oldest data. The overwritten values and deletes inside it stay on disk, and every read keeps checking it. The disk bill turns into a read bill.
Leveled: small merges, many rewrites
The fix for the disk bill arrived with Cassandra 1.0 in October 2011: leveled compaction, “based on LevelDB from the Chromium team at Google”, as Ellis put it. The same release notes say it means “you only need to keep a few MB of space free for compaction instead of (in the worst case) 50%.”
Each level is ten times larger than the one below, and its files are small: 160 MiB by default. A compaction merges one file into the ten or so it overlaps on the next level, so it touches about 11 × 160 MiB, under 2 GB. The LCS docs list the price: it is more IO and CPU intensive, and a poor choice for write-heavy tables. Leveled pays in rewrites instead.
So size-tiered paid in disk and leveled in rewrites, and changing your mind was expensive. The UCS documentation notes that STCS, LCS and TWCS “will require full compaction of the data if the compaction strategy is changed”.
One rule, two waits
Cassandra 5.0, announced on September 5, 2024, shipped the Unified Compaction Strategy. Branimir Lambov proposed it as CEP-26, and its docs make a bold claim:
There is no need to use legacy compaction strategies, because UCS can be configured to behave like any of them.
The idea starts with an observation from its design document. Both shapes build levels that grow by a fixed factor, the fanout: four on the desk, ten on the shelves. And both merge for the same reason. Files that cover the same keys stack up, and every file in a stack is one more for a read to check. So each level waits until a stack is too tall, then merges it.
The only thing they disagree on is how tall.
- Tiered waits for four. Four files pile up, then merge into one four times bigger, a level up. Each byte is copied about once per level, but a read checks every file still waiting.
- Leveled merges at two. As soon as a second file lands in a level, it is merged into the one already there. A read checks one file per level, but that file is rewritten again and again until it is ten times bigger and moves up.
Wait longer and you save rewrites; merge sooner and you save reads. Researchers drew that line first. In a Microsoft Research talk, Niv Dayan, then at Harvard, mapped key-value stores onto “a trade-off continuum, where at the extremes, we have the log and the sorted array”, with the point “where the tiered and the leveled designs converge” at a size ratio of two. Never wait and you approach a sorted array; wait forever and you have a log. The paper form is Dostoevsky.
UCS writes its position on that line as a letter and a number. The letter is the shape, T for tiered and L for leveled; the number is the fanout. The docs map the old strategies onto it: T4 is size-tiered, waiting for four; L10 is leveled, growing by ten. T4 is the default.
Pricing the two ends
The design doc gives proportions, not exact numbers: write amplification grows with the number of levels for tiered, and with fanout minus one times the levels for leveled; read amplification goes the other way. Plugging in our own numbers for one node (illustrative, not measured): 1 TB of data, flushes of about 100 MB, so 10,000× growth from bottom to top.
| Setting | Levels | Rewrites per byte | Files per read |
|---|---|---|---|
| T4 | log₄ 10,000 ≈ 7 | about 1 per level ≈ 7 | up to 3 waiting per level ≈ 20 |
| L10 | log₁₀ 10,000 = 4 | up to 9 per level, ≤ 36 | about 1 per level = 4 |
Why leveled falls behind, and what UCS does instead
Leveled has a weak spot under heavy writes. A new file in level 0 cannot be merged into level 1 while the level 1 files it overlaps are busy in another compaction, so level 0 piles up. Cassandra’s own code says so in a comment: picking the level with the highest score “falls apart spectacularly once you get behind.”
UCS picks its next merge by the read bill. Per the design doc, when it is behind “we select a compaction bucket whose overlap is the highest”, on whatever level that stack sits, which prevents the failure the doc names: “all resources consumed by L0 and sstables accumulating on L1”. The docs also name the knob for a table that can’t keep up: move the setting toward T, which rewrites less. A level can even have its own setting, tiered at the bottom where bursts land and leveled above for reads.
Discord never got to use any of it. They switched their messages database over in May 2022, more than two years before UCS shipped.
Density and shards cut the disk bill
Reads against rewrites is one trade. The desk’s disk bill is another, and UCS cuts it by splitting files into smaller pieces. That creates a problem: a small piece of a huge level looks exactly like a fresh flush if you judge by size alone.
The fix is density: a file’s size divided by the fraction of the node’s token range it covers. A 1 GB file that covers a quarter of the range has a density of 4 GB, so it belongs on the same level as a 4 GB file covering everything.
With levels measured by density, UCS can cut every file at fixed boundaries across the node’s key range. The docs call the slices shards, but nothing moves between machines: it is only where one node cuts its own files. Per the design doc, the boundaries are powers of two, so bigger levels get more boundaries, never different ones. Since every level is cut on the same lines, no merge crosses one, slices compact side by side, and each merge only needs free room for its own slice.
Even a full compaction runs slice by slice: the design doc says it splits into about one job per shard, “reducing the space overhead by a factor close to” the shard count. The exception is when nodes join or leave the ring: the boundaries move, and a full compaction needs a full copy again.
Density also makes the shape changeable while the table runs. The docs say a parameter change “only initiates compactions that are necessary” to reach the new shape; nothing is rewritten from scratch.
A delete is a write
Every bill so far was for data you wanted to keep. Deletes cost too, because in an LSM tree a delete is a write: Cassandra inserts “a time-stamped deletion marker called a tombstone”, and the value it hides stays on disk until compaction merges the two.
Back in 2017, Discord ran on twelve nodes. Each message was a row in a partition keyed by channel and a ten-day bucket, PRIMARY KEY ((channel_id, bucket), message_id). Their post from that year found two surprises:
Deleting a column and writing null to a column are the exact same thing. They both generate a tombstone.
Their schema had 16 columns and the average message set 4, so every message wrote 12 tombstones. About six months in, a public server’s channel took 20 seconds to load. It had exactly one message left; the server had deleted millions of them through the API, and every read waded through their tombstones.
That is the read bill again, paid in dead rows (the same cost scans pay in any LSM). Cassandra has alarms for it: a warning at 1,000 tombstones in one query, and at 100,000 it aborts the query.
Zombies and gc_grace_seconds
Why not drop tombstones sooner? On a single machine the rule is simple: a tombstone can go once nothing older is left below it. Cassandra’s compaction checks exactly that, and adds a second condition, because one node isn’t the whole database.
When a node goes quiet, the others can’t tell whether it died or is slow; each one decides on its own, from heartbeats. Any replica can accept a delete by itself, but forgetting that delete safely takes every replica, including the one that is late.
Here is how it goes wrong. A row with value A lives on three replicas. A delete reaches two while the third is down. The coordinator saves a hint for the missing replica, but only if that replica has been down for less than the hint window, three hours by default. Past that, only a repair delivers the tombstone. Days later, the two live replicas compact and drop the tombstone together with the value. Then the third comes back, still holding A. Repair sees a value on one node and nothing on the others, and copies A back everywhere.
The tombstone docs call the result a zombie. The guard is a grace period: compaction won’t purge a tombstone until it is older than gc_grace_seconds, 864,000 seconds (ten days) by default, even when nothing older is left below it. The repair docs turn that into a schedule: “With a default gc grace period of 10 days, repairing every node in your cluster at least once every 7 days will prevent this”.
Discord cut the slack: “We lowered the lifespan of tombstones from 10 days down to 2 days because we run Cassandra repairs (an anti-entropy process) every night on our message cluster.” Fewer days of tombstones means less garbage for every read to step over. But a short grace is only safe while repair keeps running inside it, and making sure it does is the operator’s job. Cassandra 6.0, still in alpha, adds a built-in repair scheduler that is off by default, and its docs repeat the rule: “attempt to run repairs at a smaller interval than gc_grace_seconds to avoid data resurrection”.
This is the bill no compaction setting can cut. T4 or L10 decides when files merge; when a tombstone may leave is decided by the other replicas and by repair.
Discord got the bill at the end. In 2022, while copying everything out of Cassandra, the migration “got stuck at 99.9999% complete (no, really)”. The last token ranges held “gigantic ranges of tombstones that were never compacted away in Cassandra.” They compacted that range, “and seconds later, the migration is complete!”
Time windows: deleting whole files
Some data never waits for a delete; it is written with an expiry. Metrics, logs and sensor readings are written once, in time order, and kept for a fixed time: 90 days in the TWCS docs’ example. When a value’s TTL runs out, it is treated like a tombstone and waits out the grace period like any other.
On the size-tiered desk, files are grouped by size, not age, so one merged file mixes last quarter’s readings with this morning’s. It can’t be thrown away until everything in it has expired, and until then compaction keeps rewriting it.
Cassandra’s first answer for time series, date-tiered compaction, came from a Spotify master’s thesis in 2014. The Last Pickle found it “very hard to reason about”, and it was removed in 5.0. In 2015 Jeff Jirsa, then at CrowdStrike, proposed an alternative, and as the first slide of his Cassandra Summit 2016 talk put it, he did it “because everything else made him sad”.
His time-window strategy groups files by time instead of size. Each file goes into the window of its newest write. Inside the current window, files still merge size-tiered; once a window closes, its files are compacted into one, and then they are left alone.
When the oldest window’s data is past its TTL and the grace period, and no other file holds older data for the same keys, Cassandra drops the whole SSTable without reading it. It is the same trick as Pebble’s delete-only compactions: when a whole file is dead, delete the file, not the keys in it. No read, no rewrite, and the disk comes back at once.
The docs suggest aiming for “approximately 20-30 windows”: with a 90-day TTL, 3-day windows. You end up with about thirty files plus a few for the grace period, and every three days one arrives and one leaves.
The catch is order. If an old value is written today, with a client-set timestamp or pulled into the memtable by a read repair, it lands in today’s file. That file now overlaps the old windows and holds up their drop. An option, unsafe_aggressive_sstable_expiration, skips the check, and the docs warn it “can lead to data loss or deleted data re-appearing”: the zombie again.
UCS covers this case too. Within a level, the design doc says it groups files by timestamp, where size-tiered “easily loses time order”, and for time series the docs suggest T8 with a check for expired files every 300 seconds.
Should you pick Cassandra in 2026?
Plenty of teams do. Netflix wrote in 2024 that “Cassandra serves as the backbone for a diverse array of use cases within Netflix”, from sign-ups to viewing histories. Bloomberg is quoted on the project’s homepage serving “more than 20 billion requests per day on a nearly 1 PB dataset across a fleet of 1,700+ Cassandra nodes.”
It fits when writes never stop, when data has to stay up across data centers with no single leader to fail over, and when you know your queries before you design your tables; the docs say it plainly: “In Cassandra, data modeling is query-driven.” It does not fit when your data fits on one big Postgres server. Cassandra has no joins, and transactions across partitions (Accord) first arrive in 6.0, still in alpha. If you want the model without running the cluster, managed services such as Amazon Keyspaces speak the same query language.
Choosing a compaction setting
UCS is recommended for new tables, but it is not the default: trunk’s cassandra.yaml still falls back to size-tiered. The second file, cassandra_latest.yaml, turns on UCS at T4, along with a trie-based memtable and the trie-indexed BTI SSTable format, both added in 5.0.
Then tune by the bill that hurts:
| If this hurts | Do this |
|---|---|
| Rewrites, or compaction falling behind | Stay toward T (T4 default) |
| Reads, and Bloom filters can’t help (wide partitions) | Move toward L (L10) |
| In-order data with a TTL | T8, or time windows |
And three ways to get burned: time windows on rows that get edited or deleted, like chat messages; a grace period shorter than how often you actually repair; size-tiered on a disk more than half full.
Sources and further reading
Sources
- Bo Ingram, How Discord Stores Trillions of Messages, Discord, 2023.
- Stanislav Vishnevskiy, How Discord Stores Billions of Messages, Discord, 2017.
- Apache Cassandra, Size-tiered compaction (STCS).
- Apache Cassandra, Leveled compaction (LCS).
- Apache Cassandra, Unified compaction (UCS).
- Apache Cassandra, UnifiedCompactionStrategy.md, the design document.
- Apache Cassandra, Time-window compaction (TWCS).
- Apache Cassandra, Tombstones.
- Apache Cassandra, Repair and Hints.
- Apache Cassandra, Dynamo architecture.
- Apache Cassandra, NEWS.txt, CompactionTask.java, LeveledManifest.java, Config.java, trunk at b110470 (2026-09-28).
- Apache Cassandra, Cassandra 5.0 announcement, 2024, and CEP-26: Unified Compaction Strategy.
- Jonathan Ellis, Leveled Compaction in Apache Cassandra, DataStax, 2011 (archived).
- CASSANDRA-1608: Redesigned Compaction, CASSANDRA-6602 (DTCS), CASSANDRA-9666 (TWCS).
- Alex Dejanovski, TWCS part 1: how does it work and when should you use it?, The Last Pickle, 2016.
- Niv Dayan, Scaling Log Structured Key-Value Stores, Microsoft Research.
- Netflix Technology Blog, Introducing Netflix’s Key-Value Data Abstraction Layer, 2024 (archived).
- Apache Cassandra, project homepage (Bloomberg testimonial) and Data modeling.
- Amazon Web Services, Amazon Keyspaces.
Further reading
- Aleksey Yeschenko, Cassandra Anti-Patterns: Queues and Queue-like Datasets, DataStax, 2013 (archived).
- Branimir Lambov, The Unified Compaction Strategy in Cassandra 5, The ASF (the designer’s own walkthrough).
- Niv Dayan and Stratos Idreos, Dostoevsky: Better Space-Time Trade-Offs for LSM-Tree Based Key-Value Stores, SIGMOD 2018.
- Raphael S. Carvalho, Incremental Compaction 2.0, ScyllaDB, 2021.