Log-Structured KV Store

Project roadmap

1. 01

   Define the file format and API

   ~2h

   Write DESIGN.md describing the record format: a CRC32 checksum, a timestamp, key length, value length (a special value marks a deletion, called a tombstone), then the key and value bytes, with fixed-width little-endian integers. Write kv.h with kv_open, kv_get, kv_put, kv_delete, kv_compact and kv_close, all returning error codes. Set up the build with CMake (or Make) with -Wall -Wextra and a debug build using AddressSanitizer. Done when: the header compiles, and DESIGN.md explains every field.

2. 02

   Append records and build the index

   ~3h

   Implement kv_put and kv_delete: encode the record, append it with write() on a file opened with O_APPEND, and update an in-memory hash table (write your own with chaining, or a simple open-addressing one) mapping each key to the offset and size of its latest record. Deleting removes the key from the index after writing a tombstone. Done when: putting, overwriting and deleting 10,000 keys leaves the index correct, with no leaks reported by AddressSanitizer.

3. 03

   Read values

   ~1.5h

   Implement kv_get: look up the key in the index, read the record at the stored offset with pread(), verify its checksum, and copy the value into a buffer the caller frees (or a caller-provided buffer with its size). Return a distinct not-found code and a corruption code for a bad checksum. Done when: every written key reads back its latest value, and deleted keys return not-found.

4. 04

   Make writes durable

   ~1.5h

   Add a sync option to kv_open: always (fsync after every write), or never (rely on the operating system). Document in DESIGN.md exactly what each option guarantees after a power failure. Handle partial writes and EINTR from write() in a loop. Done when: with sync set to always, every acknowledged write survives killing the process with kill -9.

5. 05

   Recover after a crash

   ~2.5h

   On kv_open, scan the file from the start, rebuilding the index from every valid record. When a record at the end is cut short or its checksum fails, stop, truncate the file to the last good record with ftruncate, and report it. Write a test that appends random garbage or a half record to the end of a valid file. Done when: opening a damaged file recovers every complete record and discards only the broken tail.

6. 06

   Compact the log

   ~2.5h

   Implement kv_compact: write only the live records (the latest value per key, no tombstones) into a new file, fsync it, rename() it over the old file (rename is atomic on POSIX), fsync the directory, and rebuild the index offsets. If the process crashes midway, the old file must still be intact. Done when: compaction shrinks a file full of overwrites, and every key still reads back correctly.

7. 07

   Add a CLI and test everything

   ~2.5h

   Write a small CLI (kvcli db.log put key value, get key, del key, compact, stats). Write a test program comparing the store against a simple in-memory reference for 100,000 random operations, including reopening the file and compacting partway through. Run the tests under AddressSanitizer and UndefinedBehaviorSanitizer. Done when: the tests pass with no sanitizer errors.

Resources

• ArticleBitcask: a log-structured hash table (paper)
• Docsfsync(2) man page
• Docsrename(2) man page
• Docspread(2) man page
• DocsAddressSanitizer documentation