File-Backed Key-Value Store

Project roadmap

1. 01

   Design the record format

   ~1.5h

   Write DESIGN.md: each record is a header (a flag for a normal record or a tombstone, the key length and the value length, as fixed-size integers) followed by the key bytes and the value bytes, appended to the end of the data file. Write functions to write a record and to read the record at a given offset, checking the lengths are sensible so a damaged file can't cause huge allocations. Done when: records written then read back are identical.

2. 02

   Build the hash table index

   ~2h

   Implement a hash table with chaining: an array of buckets, each a linked list of entries with the key (a copy made with malloc) and the offset of its latest record, using a string hash such as FNV-1a, and growing (rehashing) when the load gets high. Provide put, get and remove, and free everything properly. Done when: unit tests with thousands of keys pass, and valgrind shows no leaks.

3. 03

   Implement set and get

   ~1.5h

   SET appends a record, flushes it with fflush, and updates the index with its offset (found with ftell before writing). GET looks up the offset, seeks there with fseek and reads the value. At startup, scan the whole data file from the beginning to rebuild the index, so the latest record for each key wins. Done when: values set in one run are returned by GET in the next.

4. 04

   Delete with tombstones

   ~1h

   DEL appends a tombstone record for the key and removes it from the index; when rebuilding at startup, a tombstone removes the key. GET on a deleted key returns not found. Done when: deleted keys stay deleted after restarting.

5. 05

   Compact the file

   ~2h

   Write COMPACT: write every live key's latest value to a new file, flush and close it, rename it over the old file, and rebuild the index with the new offsets. If anything fails before the rename, the old file must remain intact. Print the file size before and after. Done when: after many overwrites and deletes, compaction shrinks the file and all live keys still read correctly.

6. 06

   Build the prompt

   ~1h

   Write a prompt loop reading lines with fgets and handling SET key value (the value is the rest of the line), GET key, DEL key, LIST (all live keys, sorted), COMPACT, STATS (keys, file size and stale bytes) and QUIT, with clear messages for bad commands. Done when: every command works interactively.

7. 07

   Test it

   ~1.5h

   Write a test program that performs thousands of random SET, GET and DEL operations while checking them against a simple in-memory reference, restarting (closing and reopening the store) and compacting at random points. Also test a file cut off in the middle of a record (the incomplete record at the end is ignored). Run it under valgrind. Done when: all checks pass with no memory errors.

Resources

• ArticleBitcask: a log-structured hash table (paper)
• ArticleHash table (Wikipedia)
• Docsfseek (cppreference)
• Docsrename(2) man page
• DocsValgrind quick start