8 min read

Storage engines

Discord stores every message ever sent on the platform. In 2017 they moved those messages from MongoDB to Cassandra, and in 2023 they wrote about moving again, to ScyllaDB, at trillions of messages. Both destinations share one design decision underneath, the same one inside RocksDB, which in turn sits under CockroachDB, TiDB and many others: they never change data in place on disk. They only ever append.

Every database has a storage engine: the part that decides how rows are laid out on disk and how they are found again. Almost all of them belong to one of two families, the B-tree and the LSM-tree. Knowing which one a database uses tells you, before you benchmark anything, whether it will love or hate your workload.

Your answer

Why might a database that never updates data in place on disk accept writes faster than one that does? What would you expect it to be worse at?

The B-tree family: update in place#

Postgres, MySQL's InnoDB, SQLite, Oracle, SQL Server, and MongoDB's default WiredTiger engine all keep data in B-trees: fixed size pages arranged in a shallow, sorted tree, the structure from the indexes chapter.

A write finds the page that holds the row and changes that page. The change is first recorded in the write ahead log for safety, and the page itself is written back to disk later. Reads are excellent: a few page lookups and you are there. Writes are fine, but every write eventually rewrites a whole 8 or 16 KB page somewhere on disk to change a few bytes, and those pages are scattered, so heavy write traffic means lots of small random writes.