TLDR

• How RocksDB came about and its implementation

Context

• LevelDB kv store
  • need to saturate IO capacity of fast storage (flash,…)
  • LevelDB benchmark on flash storage not so good, too much mutex contention
  • reason
    • running on Linux 2.6.38 which has mutex contention issues on virtual mem management
    • mmap db large than RAM -> constantly getting to VM mem map -> use pread instead of mmap
• Experimentation at Facebook
  • LevelDB not meant for server workload, trade-off was made for good target workload
  • compaction is single-threaded -> if need sustainable IO compaction, LevelDB not good
  • above point was learned the hard way for several LevelDB forks
  • optimizations taken
    • for monitoring, write-amplification of compaction
    • multi-threaded compaction
    • backup
• open-sourced above as RocksDB by Facebook 2013

Architecture

• based-on LSM Tree, data is organized into many files by levels
• writes come to memtable —flushed—> level-0 —compacted—> level-1 —> …
• each level usually configured to be 10x bigger than previous one
• files in level-0 cover whole keyspace

Put life-cycle

• foreground, (key, value) is written to WAL, then applied to memtable (skiplist by default)
• background
  • when memtable is full e.g. > 64MB, flushed to level-0
  • when level is full, compaction happens pushing file(s) e.g. from level-2 to level-3

Reads

• if finds key in memtable -> recent write -> returns immediately
• point queries
  • bloom filter used to check if key in file -> at most 1 physical read
  • read = consult many bloom filters + read 1 file instead of reading many files from disk.
• range queries
  • bloom filter cannot help
  • short scans at most 1, 2 physical reads

Data Format, Files

rocksdb/> ls 
MANIFEST-003 # db metadata
000024.sst
000031.sst
000025.sst
000028.sst
000029.sst
000033.sst
000034.sst
LOG
LOG.old.1441234029851978

MANIFEST

• allows atomic updates to db metadata
• when flushing, 2 updates
  • 1 to WAL to mark log not replay
  • 1 to
• compaction = remove files from + add files to LSM tree -> 2 needs to be atomic

WAL (Write-ahead log)

• adding multiple updates to WAL can be an atomic operation -> useful e.g. for being storage engine of RDBMS: update to table file and index file at the same time

Table Files

• data blocks: compressed and prefix encoded
• index blocks: pointer to data blocks <key, block>
• filter block: persistent bloom filter
• statistics block
• meta index block: pointers to block

LOG files

• debugging output
• tuning options
• information about flushes and compactions (flushes normally 10s, compaction minutes)
• performance statistics

Backups

• Table files are immutable
• Other files are append-only
• easy and fast incremental backups

WIP

Manage ingest

• ingest x write-amplification <= compaction throughput

Reference

• Igor Canadi + Mark Callaghan - RocksDB (The Databaseology Lectures - CMU Fall 2015)