RocksDB Engineering Blog

Ideas you will meet

Storage Engines

Write-ahead logs, B-trees and LSM-trees.

What we already know about this

Our own lessons on these ideas. Read them here before you start, so it makes sense.

• Advanced Distributed Systems · 13 minWrite-ahead logs, B-trees and LSM-treesHow databases make writes durable and fast: the log first, then two ways of organising data on disk and the trade-offs between them.Read hereClose

  Durability needs a log

  A database holds data in memory pages for speed, but memory is lost on a crash. To be durable it must put a record of every change on disk before it tells the client "committed". That record is the write-ahead log (WAL): an append-only file of changes.

  100%

  Figure SDA-ADS-02-1 · Write-ahead log flow · © forcsguy.com

  The same idea appears everywhere: databases, file systems (journaling), message brokers (the log is the data) and replication (followers replay the primary's log).

  Two ways to organise data on disk

  B-trees: update in place

  A B-tree keeps sorted keys in fixed-size pages arranged as a shallow tree. Finding a key takes a few page reads; changing a key updates a page in place (plus a WAL record for safety).

  • Strengths: predictable reads, efficient range scans, mature, used by most relational databases.
  • Costs: writes touch random pages (random I/O); page splits and fragmentation; every write is written twice (WAL and page).

  LSM-trees: append and merge

  A log-structured merge tree buffers writes in a sorted in-memory table (the memtable), also logged to a WAL. When full, it is flushed as an immutable sorted file (an SSTable). Background compaction merges files and discards overwritten and deleted values.

  100%

  Figure SDA-ADS-02-2 · LSM-tree write and read path · © forcsguy.com

  • Strengths: very fast sequential writes, good compression, high write throughput.
  • Costs: a read may check several files (helped by bloom filters and caches); background compaction creates write amplification and I/O spikes; deletes leave tombstones until compaction.

  Choosing

  Question	B-tree	LSM-tree
  Write-heavy ingestion	Slower	Faster
  Point reads and range scans	Steady	Good, depends on compaction
  Predictable latency	Easier	Compaction can add tail latency
  Space usage	Some fragmentation	Temporary extra during compaction
  Typical users	PostgreSQL, MySQL (InnoDB)	Cassandra, RocksDB, HBase, many time-series stores

  There is no winner: choose by workload, and measure. This lesson explains why a store behaves the way it does under load, which helps when diagnosing slow writes or sudden I/O spikes.

  Related ideas

  • Checkpoints and snapshots bound recovery time.
  • Replication often ships the WAL to replicas.
  • Fsync policy (flush every write, or every few milliseconds) is a durability versus speed knob.
  • Bloom filters appear in the probabilistic-structures lesson of the core-concepts course.

  Real-world reading

  Related reading

  • The Log-Structured Merge-Tree (paper)O'Neil et al. · UMass BostonPapers
  • Amazon Aurora: Design Considerations for High Throughput Cloud-Native Relational Databases (paper)Verbitski et al. · Amazon Web ServicesPapers
  • RocksDBMeta · GitHubGitHub
  • ClickHouse BlogClickHouse engineers · ClickHouseBlogs

  Show 6 moreShow fewer

  • The Google File System (paper)Ghemawat, Gobioff and Leung · GooglePapers
  • Inside the Magic PocketDropboxCase Studies
  • Database InternalsAlex Petrov · O'ReillyBooks
  • How SQLite WorksSQLite team · SQLiteDocumentation
  • Bigtable: A Distributed Storage System for Structured Data (paper)Chang et al. · GooglePapers
  • Tumblr Engineering BlogTumblr engineers · TumblrBlogs

  Open this lesson with its quiz and exercise

• Storage, Queues and Real-time · 11 minBitcask: a tiny log-structured key-value storeHow an append-only data file plus an in-memory key directory gives one-seek reads and fast writes, how deletes and merges work, and the limits of the design.Read hereClose

  The idea in one paragraph

  Keep all data in append-only files. Never modify old bytes. Keep, in memory, a hash table called the keydir that says where the latest value of each key lives. A write appends to the file and updates the keydir. A read looks up the keydir and does one disk read at the recorded position.

  100%

  Figure SDA-SQR-01-1 · Bitcask write and read paths · © forcsguy.com

  The record format

  Each record in a data file looks like: CRC, timestamp, key size, value size, key, value. The CRC lets the engine detect torn or corrupt writes after a crash. When the active file reaches a size limit it is closed (becomes immutable) and a new active file starts.

  Deletes and updates

  • An update simply appends a newer record; the keydir points to it. The older record becomes garbage.
  • A delete appends a special tombstone record and removes the key from the keydir.

  Merging (compaction)

  Over time the files fill with stale records. A merge process reads the immutable files, keeps only the latest live record per key, writes them into new files and deletes the old ones. It can run in the background without blocking reads and writes.

  100%

  Figure SDA-SQR-01-2 · Merge reclaims space · © forcsguy.com

  Recovery

  On start, the keydir is gone and must be rebuilt. Reading every record of every file works but is slow for large stores. Hint files hold just the keys and positions for each data file, so recovery reads much less data. Torn writes at the end of the last file are detected by the CRC and truncated.

  Strengths and limits

  Strength	Limit
  Very fast writes: sequential appends	Every live key must fit in RAM
  Reads need one seek	No range scans: the keydir is a hash table, not ordered
  Simple crash recovery from an append-only log	Merge needs spare disk space and I/O
  Easy backups: files are immutable	Single writer per store

  When keys do not fit in memory or you need ordered scans, an LSM-tree (memtable, sorted files, compaction) is the usual answer, as in RocksDB. When you need transactions and ad hoc queries, use a database.

  Real-world reading

  Related reading

  • Bitcask: a log-structured hash table for fast key/value dataJustin Sheehy and David Smith · Basho TechnologiesPapers
  • RocksDB Engineering BlogRocksDB engineers · RocksDBBlogs
  • RocksDBMeta · GitHubGitHub
  • Use The Index, LukeMarkus Winand · use-the-index-luke.comCourses

  Open this lesson with its quiz and exercise