A key/value store looks like the simplest database there is: put, get, delete. The hard part is not the API. It is what happens when the power goes out in the middle of a write, when the data files grow forever because old values are never reclaimed, and when the process restarts and must find every key again.
The Bitcask paper, written for the Riak database, answers all three with one idea: never modify data in place. Append every write to a log, keep an index in memory, and clean up in the background. The paper is a few pages long, which makes it a good first storage engine to build. bitcask-kv is my implementation in Rust: append-only data files, an in-memory hash index (the "keydir"), merge/compaction, hint files for fast startup, and crash recovery of torn writes. Here is what I built and what it teaches.
What I built
Append-only data files. Files named 0000000000.data and so on hold records in this layout, little endian:
crc32 | key_len | val_len | key | value
Only the newest file is written to. When it reaches max_file_size (64 MiB by default) it is closed and a new one starts. A delete does not remove anything: it appends a tombstone, a record whose val_len is u32::MAX.
The keydir. A HashMap<key, (file_id, offset, len)> with one entry for every live key. A get looks the key up in memory, then does one pread at the right offset and checks the CRC of the record. So a read costs one system call, whatever the size of the store.
Startup. Opening a store replays the files from oldest to newest and rebuilds the keydir. A file that has a hint file is indexed from the hint instead. Hint entries are key_len | rec_len | rec_pos | key, protected by a CRC, so the store learns where each value is without reading the values.
Crash recovery. Replay stops at the first record that is truncated or fails its CRC, and the file is truncated at that point. A torn write at the tail is discarded, and new writes continue after the last good record. The stats command reports how many bytes were dropped.
Merge. Over time the files fill up with overwritten values and tombstones. merge copies the live records into new files, which get the highest ids, writes their hint files, then deletes the old files, oldest first. The order matters: a crash at any point during the merge leaves a set of files whose replay gives the correct state.
A lock. A LOCK file with an OS advisory lock keeps two processes from opening the same directory.
How to use it
Clone the repository and build it. The command-line tool is called bitcask.
git clone https://github.com/AbdeldjalilChougui/bitcask-kv
cd bitcask-kv
cargo build --release
B=target/release/bitcask
$B ./db put greeting "hello"
echo -n "from stdin" | $B ./db put note
$B ./db get greeting
$B ./db keys
$B ./db del greeting
$B ./db stats
$B ./db merge
The first argument is the directory of the store. put takes the value as an argument or from stdin.
It is also a library:
let mut db = bitcask_kv::Bitcask::open("./db")?;
db.put(b"k", b"v")?;
assert_eq!(db.get(b"k")?, Some(b"v".to_vec()));
db.delete(b"k")?;
db.merge()?;
To use the library in another project, add it as a git dependency:
cargo add --git https://github.com/AbdeldjalilChougui/bitcask-kv
A good first experiment: put the same key a few thousand times, look at stats and the size of the directory, run merge, and look again. Then open one of the .data files in a hex viewer and find your keys.
What it teaches
Appending is the cheapest write, and the safest. A write never touches existing data, so a crash can only damage the last record. Recovery becomes a simple rule: read until something does not check out, cut there.
The CRC is what makes that rule work. A half-written record at the tail is not always shorter than expected. It can be the right length with garbage inside. The checksum at the front of every record is how replay tells a good record from a torn one. The tests cover both a truncated tail and a garbage tail.
Deletes are writes. In a log you cannot erase, you can only say "this key is gone" in a newer record. The tombstone has to survive until merge can prove that no older file still holds a value for that key.
The order of operations is the crash safety. Merge gives new files the highest ids and deletes old files oldest first. Because replay goes from oldest to newest, every intermediate state replays to the right answer. Nothing here needs a transaction log. It needs the right order.
Startup time is a design problem. Rebuilding the index by reading every value is slow for a large store. Hint files are the fix: a small side file with keys and positions only.
A model check finds what examples miss. The store tests compare the store against a plain in-memory map across reopens, merges and file rotation. If the two ever disagree, there is a bug.
Things to know
This is a learning project. The README states these limits:
-
Single writer, not thread-safe. Writes take
&mut self. There is no concurrent merge. - The whole keydir lives in memory, as in Bitcask. Every key must fit in RAM. A scan also reads each data file fully into memory.
- Corruption in the middle of an older file is treated like a torn tail: everything after it in that file is dropped.
-
Durability is opt-in.
sync_on_writeis off by default. The CLI fsyncs after each command; the library does it only onsync(), rotation and merge. - No key expiry and no range scans. A hash index has no order.
-
Unix only. It uses
FileExt::read_exact_at.
What was tested. cargo test covers the record codec and the store: the model check across reopens, merges and rotation, truncated-tail and garbage-tail recovery, CRC corruption, and the CLI. cargo bench runs criterion benchmarks. The README gives example numbers from a laptop with 100-byte values and no fsync: about 7 µs for a put, about 7 µs for a get, about 10 ms to open by scanning 10k records, and about 12 ms to merge 10k writes over 1k keys. Without fsync, those numbers measure the code path and the page cache, not a disk.
Why I built it
I wanted to understand how a storage engine survives a crash, and I wanted to learn it on a design small enough to hold in my head. Bitcask is that design. There is no B-tree to balance and no write-ahead log separate from the data: the log is the database.
The limits are part of the lesson too. Keeping every key in memory and giving up range scans are the price of one-seek reads, and seeing that trade in your own code explains why other engines, like LSM trees, made different choices.
Get the code
The source, tests and benchmarks are on GitHub: https://github.com/AbdeldjalilChougui/bitcask-kv. It's MIT licensed. Issues and pull requests are welcome. The Bitcask paper it follows is linked from the README.
Originally published at abdeldjalilchougui.biz.
Top comments (0)