USENIX Conferences

Ideas you will meet

Distributed Systems

Consensus, time, failure and the fundamentals of scale-out.

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