Crash-Safe Key-Value Store with a Write-Ahead Log
A small embedded key-value store written from scratch with a write-ahead log, checksummed records, crash recovery and compaction, plus a crash test harness that proves no acknowledged write is lost. A computer science final year project and teaching tool for database and systems courses.
Intermediate
A small team, or one strong student willing to learn something new.8 to 12 weeks · 1 or 2 students
8 to ship
3 optional extrasSuggested stack
What you should ship
- Get, put and delete operations with records stored in an append-only data file and deletes as tombstones
- An in-memory hash index from keys to file offsets, rebuilt on startup or loaded from a hint file
- A write-ahead log with checksums, flushed with fsync before a write is acknowledged, and optional group commit
- Recovery on startup that replays the log and discards a torn final record detected by its checksum
- Compaction that rewrites live keys into a new file and switches over atomically without blocking reads for long
- A crash test harness that kills the process at random points hundreds of times and verifies every acknowledged write
- Benchmarks of write and read throughput with fsync per write, with group commit and without fsync
- A README describing the file format byte by byte, the recovery algorithm and the durability trade-offs
If you have time left
- Atomic multi-key transactions with a commit record
- A sorted on-disk structure, such as sorted string tables, to support range queries
- A small network protocol so several clients can connect, with a simple benchmark client
The problem this project makes real
Database courses teach ACID, write-ahead logging and recovery on paper. Students can define durability in an exam and still have no idea what happens when a process is killed halfway through writing a record. In real systems, that gap causes lost payments, corrupted configuration and "it worked on my machine" bugs that only appear after a power cut. Understanding durability properly means implementing it and then attacking your own implementation.
Who would use the result? First, students and lecturers: a small, readable store with a crash harness is an excellent teaching tool. Second, developers who need a tiny embedded store for a device or a tool and want something they fully understand.
What already exists and the gap
- Bitcask, the storage engine behind Riak, uses an append-only log with an in-memory hash index; its design paper is short and readable.
- LevelDB and RocksDB are log-structured merge-tree stores used inside many databases and services.
- bbolt is a B+tree key-value store in Go used by etcd.
- PingCAP Talent Plan and university labs such as MIT's distributed systems course include key-value store exercises.
The production engines are too large to read in a semester, and most course exercises test the happy path. The gap is a small store whose main deliverable is evidence of crash safety: a harness, hundreds of crash runs and a byte-level explanation of why nothing is lost.
What you build
- Data file format: each record holds a checksum, key length, value length, key and value, appended to the end of the file.
- Index: an in-memory map from each key to the offset of its latest record, rebuilt by scanning on startup.
- Deletes as tombstone records.
- Write-ahead log and a clear rule for when a write is acknowledged: only after its record is flushed with fsync.
- Recovery that detects a partially written last record by its checksum and discards it.
- Compaction that writes only live keys to a new file, then switches over with an atomic rename.
- Crash harness and benchmarks.
The technically interesting part
The crash harness is the centre of the project. It runs a workload, kills the process with SIGKILL at random moments, restarts it and checks that every acknowledged write is present and no corrupted value is returned. The subtle bugs are where the learning is: forgetting to fsync the directory after a rename, trusting a length field before checking the checksum, or acknowledging a write before the flush. Show your supervisor at least one real bug the harness found and how you fixed it. Then show the throughput trade-off: fsync on every write, group commit that batches several writes per flush, and no fsync at all, and explain which applications should choose which.
How to evaluate it
- Durability: at least 500 randomised crash runs with zero lost acknowledged writes and zero corrupted reads; report any failures found during development.
- Throughput: writes per second under the three durability settings, and reads per second with a warm index.
- Recovery time: startup time as the data file grows, with and without a hint file.
- Compaction: disk space before and after, and the longest read pause during compaction.
- Readability: another student implements a reader for your file format from the README alone.
Suggested plan
- Weeks 1 to 2: read the Bitcask paper, design the file format, write the README first.
- Weeks 3 to 4: put, get, delete, index rebuild.
- Weeks 5 to 6: write-ahead log, fsync rules, recovery.
- Weeks 7 to 8: crash harness and fixing what it finds.
- Weeks 9 to 10: compaction, benchmarks.
- Weeks 11 to 12: stretch goal or write-up.
Path to a product
This is not a SaaS idea, and forcing one would be silly. The realistic outcomes are: an open source teaching resource that lecturers adopt for database or operating systems labs; a portfolio centrepiece that gets interviews at infrastructure, database and storage companies; and a foundation for a follow-up project such as a replicated store. A well-documented repository with a crash harness is rare and gets noticed.
Scope warning
Keep keys in memory and values on disk; a key set that fits in RAM is fine. Do not add SQL, replication or networking until the crash harness passes. Do not use an existing embedded database for storage, since building the storage is the point.
Learn what you need on Sefism
- Programming roadmap : the language fundamentals you need before systems work.
- DSA cheat sheet : hash maps, logs and trees used by storage engines.
- CMU 15-445/645: Intro to Database Systems : logging, recovery and storage explained by experts.
- Operating Systems: Three Easy Pieces : file systems, crash consistency and fsync.
- Go Documentation : a practical language choice for this project.
Get help with this idea
The key decision is what to prove, not what to add. Tauseef can help you set the scope, design the crash harness and present the evaluation so examiners see real systems work. If you are new here, create a free account first.
Ideas and guidance, not finished projects
These are project ideas and scoping guidance, published free for students to use as a starting point. I do not build, write, or sell final-year projects, and I do not complete coursework for anyone. Take an idea, make it yours, and build it.
Not sure this one fits you?
I help students pick an idea that matches their skills and their deadline, then scope it down until it is finishable. Guidance only, never done for you.
Stuck on something specific?
Writing only gets you so far. If you want an answer to your situation rather than the general case, book a session and we will work through it together. Sessions are free for approved Sefism members, and a few slots open each week.
Follow along
New writing, resources and project ideas land here first.