Bitcask — Hash-Indexed Log Segments

So far we built an LSM tree (memtable + sorted SSTables + compaction). There is another fundamental design for log-structured storage: Bitcask, used by Riak.

Core idea: keep the data on disk as an append-only log, but maintain an in-memory hash index mapping each key to its position (file id + byte offset) in the log.

DISK (append-only):
  [PUT name alice] [PUT age 30] [DEL age] [PUT name bob]
  ^offset=0         ^offset=20    ^offset=38 ^offset=49

MEMORY (hash index):
  name -> (file=0, offset=49)   # latest position
  age  -> TOMBSTONE

Read path (point lookup only): hash-lookup the key, seek to that offset, read one record. One disk seek per read — best in class for point lookups on cold data.

Write path: append the record to the active log file, update the in-memory hash to point at the new position. O(1) amortized.

Trade-offs vs LSM:

Compaction in Bitcask: periodically, walk over an old log file, copy each still-live record into a new file, and delete the old file. This reclaims space from overwritten keys and tombstones. (Same idea as LSM compaction, but no sorting required.)

Why Riak picked Bitcask: Riak is a distributed KV — partition keys across many nodes — so point lookups dominate. Range scans go through a different secondary-index layer.

When you SHOULDN'T pick Bitcask: when the live key set doesn't fit in RAM (the hash index alone can dwarf the data), or when range scans matter.