ProjectsBitcask
A key-value store, driven from the command line, that keeps its data in a folder of append-only log files and finds each value through an in-memory index of positions, following the design of Bitcask, the storage engine from the Riak database. Building it teaches what it takes for data to be truly saved, how to lay out records on disk so that a crash can't fool the reader, and how updates, deletes, file rotation and compaction work when nothing is ever overwritten.
From Coding Challenges #96 ↗ by John Crickett
No sign-up. You tell the mentor your language: Java, Python or Node.js.
What you'll learn · 9 concepts
In the order the steps use them. Each one links to the best places to learn it, and you explain it in your own words once its steps are built.
Step 1 rewrites the whole file after every change, and each command is a separate process, so the store has to decide when a change counts as saved. The page doesn't cover flushing, so this goes deeper than it.
Covers: what saved really means · the page cache between a write and the disk · fsync and its cost · the directory entry of a new file · replacing a file safely with a temporary file and a rename · choosing how often to flush
fsync(2), Linux manual page ↗ · Files are hard (Dan Luu) ↗ · Atomic Commit In SQLite ↗
Step 2 replaces the full rewrite with appends, and every later step relies on records never changing once they're written.
Covers: appending instead of overwriting · why sequential writes are fast · why a crash can only hurt the end · the data files as the log · space that grows with every write
Operating Systems: Three Easy Pieces, Hard Disk Drives (Arpaci-Dusseau) ↗ · Operating Systems: Three Easy Pieces, Log-structured File Systems (Arpaci-Dusseau) ↗ · Apache Kafka design: Persistence ↗
Step 2 replaces step 1's placeholder lines with binary records that start with a CRC-32. The page only guesses at the byte order, so the format is yours to define and write down.
Covers: a fixed-size header, then the key and the value · length prefixes instead of separators · fixed-width integers and byte order · the checksum and what it covers · keys and values as bytes
LevelDB log format ↗ · Endianness (Wikipedia) ↗ · Cyclic redundancy check (Wikipedia) ↗
Step 2 asks you to start a new file once the active one passes a size limit. With the limit as a setting, tests can use a few hundred bytes and see rotation quickly.
Covers: one active file and many closed ones · the size limit and when to roll over · file ids that keep their order · why closed files never change · what a restart does to the active file
Bitcask: A Log-Structured Hash Table for Fast Key/Value Data (Sheehy and Smith) ↗ · Riak KV documentation: Bitcask ↗
Step 3 swaps the values in the table for their positions, and step 4 reads every value through it. Each command is a new process, so the index is rebuilt on every run.
Covers: key to file id, position and size · one disk read per lookup · rebuilding the index at start-up · replay order decides the winner · every key must fit in memory
Bitcask: A Log-Structured Hash Table for Fast Key/Value Data (Sheehy and Smith) ↗ · Riak KV documentation: Bitcask Capacity Calculator ↗
Step 4 checks that an update appends a new record and moves the index, and step 5 adds deletes, which must still hold after a restart.
Covers: the latest record wins · old values as garbage on disk · a tombstone as a delete record · why removing the key from memory isn't enough · ordering by place in the log, not by clock
Tombstone (data store) (Wikipedia) ↗ · Apache Cassandra documentation: Tombstones ↗
Step 6 adds the merge and the hint files and asks start-up to load the index from the hints wherever they exist.
Covers: live records versus dead ones · merging closed files into new ones · when a tombstone can be dropped · switching over safely, then deleting · hint files for a fast start-up
Bitcask: A Log-Structured Hash Table for Fast Key/Value Data (Sheehy and Smith) ↗ · Redis persistence: log rewriting ↗ · Apache Kafka design: Log Compaction ↗
Step 6 asks start-up to check each record's CRC and drop the incomplete or damaged ones a crash leaves behind. Cutting a few bytes off the end of the newest file is how you test it.
Covers: torn writes at the end of the log · checking each record's checksum at start-up · bounding a length before trusting it · cutting back to the last good record · damage in the middle versus at the end
Operating Systems: Three Easy Pieces, Data Integrity and Protection (Arpaci-Dusseau) ↗ · RocksDB wiki: WAL Recovery Modes ↗ · All File Systems Are Not Created Equal: On the Complexity of Crafting Crash-Consistent Applications (OSDI 2014) ↗
The page says only one process may use a database at a time, and the optional server turns that one process into a service that many clients share.
Covers: why two writers corrupt a log · locking the data folder · a server as the one owner · reading closed files side by side · group commit
flock(2), Linux manual page ↗ · File Locking And Concurrency In SQLite Version 3 ↗
What you'll build · 7 steps
Steps of 30 to 60 minutes, in your own editor and language. Each one has a check, so you know when it works.
Create the project: a small library that holds the store, with a command-line tool on top that takes the data folder as a setting. If you want the optional network server later, the page points to the Redis challenge for its protocol.
Works whenThe tool runs, accepts the data folder setting, and treats an empty folder as an empty database.
Keep keys and values in an in-memory hash table. Set stores a value and then writes the whole table to a file in the data folder, replacing what was there, and get prints a value. At start-up, load the file back into the table. Each command runs as its own process, so get only finds what an earlier run left on disk. Keep the data folder a setting, so that tests can give each run a fresh one.
Works whenSetting a key in one run and getting it in the next prints the value, and keys set in earlier runs are still there after later runs set other keys.
Concepts: durability and what the operating system buffers
Replace the full rewrite with an append-only log. Each set adds one binary record to the end of the active file: a CRC-32 checksum first, then a timestamp, the key and value sizes, the key and the value, with the checksum covering every byte after it. When a write takes the active file past a size limit, close it and start a new file. Make the limit a setting, so that tests can use a few hundred bytes and see rotation quickly.
Works whenA hex dump with xxd shows each set as one new record at the end of the active file, laid out as you designed it, and enough sets create a second data file. Get still returns the latest value in a later run.
Concepts: the append-only log and sequential writes · record framing on disk · file rotation and immutable segments
Change the in-memory table so that, for each key, it holds where the latest value lives instead of the value itself: the file id, the value's position and size, and the timestamp. Set records these after each append, and start-up rebuilds the table by reading every data file in order.
Works whenThe page gives no test here. Printed for debugging, the table after a restart matches the one before it entry for entry, and it holds no values.
Concepts: the in-memory index of positions
Make get look the key up in the table, open the data file named by its file id, move to the stored position and read exactly the stored number of bytes.
Works whenAfter enough sets to fill several data files, every key returns its value in a later run. Setting a key again adds a new record to the log and moves its entry in the table, and get returns the new value.
Concepts: the in-memory index of positions · updates and tombstones in an append-only store
Add a del command that appends a tombstone record for the key and removes the key from the table. The page's version records the time of the delete and sets the position, size and file id to their largest values, and any marker works as long as no real record can look like it. Get on a deleted key prints (nil).
Works whenSet, get, del and get, each in its own run, print the value and then (nil), and the key stays deleted through later runs. Setting it again returns the new value.
Concepts: updates and tombstones in an append-only store
Add a merge command. It reads the closed data files, writes only the latest live record of each key into new files, writes a hint file beside each one with every key's timestamp, sizes and position, and then deletes the old files. At start-up, load the table from hint files where they exist and read the remaining files record by record, checking each CRC and dropping the incomplete or damaged records a crash leaves behind.
Works whenThe page gives no test. After many overwrites and deletes, merge makes the data folder clearly smaller, every live key returns its latest value, and deleted keys stay deleted. Cutting a few bytes off the end of the newest data file loses at most its last record, and the store still starts.
Concepts: compaction and hint files · crash recovery from torn writes
Run the store as a long-lived server that speaks a protocol such as RESP, the one from the Redis challenge, so that clients can set, get and delete keys over the network. The server becomes the one process that owns the data folder.
Works whenA Redis client such as redis-cli can set, get and delete keys, several clients at once get consistent answers, and the data is still there after the server restarts.
Concepts: one writer and many clients