Systems and protocols · Intermediate

RocksDB LSM: buffering writes and compacting sorted files

Trace WAL, memtables, sorted files and compaction while distinguishing write, read and space amplification.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Follow the write path
  2. Trace versions and deletion markers
  3. Understand compaction work
  4. Measure the complete workload
  5. Ask Logeia about this articleCheck your understanding

Follow the write path

RocksDB is an embedded key-value store using an LSM-style organization. Writes enter a memtable and commonly a write-ahead log, then data is flushed into sorted SST files. WAL and synchronization options affect what a successful return guarantees about persistence. A memtable does not make the store purely memory-resident, and SST files do not mean that every update rewrites the complete database immediately. Follow the stages separately to identify what survives a crash and which work happens on the caller’s path versus later background maintenance.

Trace versions and deletion markers

Suppose key k first stores 10 and is then updated to 20. The new version need not overwrite the old value in its existing SST location. It can be recorded elsewhere, with reads resolving the visible version. A deletion can similarly introduce a tombstone instead of immediately erasing every older occurrence from all files. Snapshots can require older versions to remain meaningful. Consequently, the logical size of current key-value data and the physical space occupied by database files can differ. Reclamation must respect visibility, not simply remove everything that is not the newest value.

Understand compaction work

Compaction reads sorted files and produces new files that reorganize overlapping ranges and eligible obsolete versions. This can reduce lookup work while requiring data to be read and written again. Write amplification asks how much storage writing is caused by an amount of application writing; read amplification concerns lookup work, and space amplification concerns occupied storage. Compaction policies trade these quantities differently. Suppressing maintenance can make a short measurement look better while allowing debt to accumulate. A sustained workload must account for background progress, temporary space and eventual write stalls.

Measure the complete workload

Bloom filters can avoid some unnecessary file lookups for absent keys, but false positives remain and the filter does not retrieve an existing value. Block caching, compression, key distribution and point-versus-range access also change performance. A fair comparison states whether data fits in memory, whether compaction has reached a sustainable state and whether durability options match. Distinguish the embedded engine’s guarantees from transactions or replication implemented around it. A fast point-lookup benchmark under warm-cache conditions cannot establish the throughput or recovery behavior of an entire distributed application.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Understand the systems behind the web · STEP 13

Choose a learning path