The Log-Structured Merge-Tree (LSM-Tree)

Discord decided early on to keep every chat message forever, and by 2017 that meant more than 120 million new messages a day, stored in a database called Cassandra. Its engineers measured something that sounds backwards: writes were under a millisecond, and reads were under five. Writing usually means finding the right place for your data, so how can saving be faster than reading?

Cassandra doesn't put your message in its final place right away. It appends the write to a commit log, keeps it in memory, and acknowledges it; later it flushes whole batches to disk as sorted files, and in the background it keeps merging those files. Cassandra's docs say the storage engine "is based on Log Structured Merge (LSM) trees." Why would a database refuse to put your data where it belongs, and keep it spread over so many files? The design comes from a 1996 paper by Patrick O'Neil, Edward Cheng, Dieter Gawlick and Elizabeth O'Neil.

A note on sources: the published article in Acta Informatica (vol. 33, 1996, pp. 351 to 385) is behind a paywall, so every quote and page number below is from the authors' copy, pages 1 to 32.

The Bank's History Table

The paper starts from a bank described by a standard benchmark of the time, TPC-A: 1,000 transactions a second, each withdrawing money from a randomly chosen account. Every transaction also writes one 50-byte row into a table called History, with the account, branch, teller, amount and time. History only ever grows.

Customers want their recent activity ("everything on account 512 from the last week"). Without an index, that query has to read every row in History. So you add an index: a separate list of small entries kept sorted by account number and then by time, each pointing at its row. Discord's first database had exactly this kind of index, on channel_id and created_at; around 100 million stored messages, Discord wrote, "the data and the index could no longer fit in RAM and latencies started to become unpredictable."

The paper sizes it: