Bitcask: a log-structured hash table for fast key/value data

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.

• 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