# Build Your Own Key-Value Store (Python)
> Build a tiny persistent key-value database from scratch in Python - an append-only log, crash recovery, an in-memory index, compaction, and a TCP server - and come out understanding how real storage engines actually work.
---
# Build Your Own Key-Value Store (Python)
You use databases every day and trust them completely. You call `save()`, the power can die a millisecond later, and your data is still there when the machine comes back. Have you ever asked *how*? Most developers haven't - storage is the deepest magic in the stack, and everyone politely agrees not to look at it.
This weekend you're going to look at it. You'll build a real persistent key-value store in Python, from an empty folder: a store that survives crashes, recovers from half-written files, keeps reads fast with an index, cleans up after itself, and speaks a wire protocol so other programs can use it over TCP. The design you'll build - an append-only log plus an in-memory hash index - is not a toy pattern. It's **Bitcask**, the storage engine that shipped inside the Riak database, and its core moves (log-first writes, replay on startup, compaction) are the same moves inside Redis, LevelDB, and PostgreSQL.
This one runs **on your machine.** No sandbox, no framework, and remarkably: no dependencies. The entire project is Python's standard library - `struct`, `zlib`, `os`, and `socketserver`. The hard part of a database was never the libraries. It's the thinking.
## The one idea everything hangs on
Databases don't keep your data safe by carefully editing files in place. Editing in place is exactly how you corrupt data - a crash halfway through an edit leaves neither the old value nor the new one. Instead, real storage engines **append**: every change is written as a new record at the end of a log, and old bytes are never touched. The current state of the database is a *replay* of that log.
```mermaid
flowchart LR
C[Client] -->|SET / GET / DEL| S[TCP server]
S --> I[In-memory index
key → file offset]
S -->|append record| L[Append-only log on disk]
I -->|seek + read| L
```
Every phase of this project adds one piece of that picture, and every piece exists because the previous phase broke without it.
## What you'll need
- **Python 3.10 or newer.** Check with `python --version`. Nothing to `pip install`.
- A terminal and a text editor.
- Solid Python. This is the hard project in this section: you should be comfortable with classes, `bytes` vs `str`, file handles, and context managers. The database concepts are all explained; the Python is not.
If terms like *durability* or *index* are hazy, the databases section has your back - [What a Database Actually Is](/guides/what-a-database-is) and [Transactions & ACID](/guides/transactions-and-acid) are good grounding, and this project will make both feel concrete in a way reading never can.
Rough time: a weekend. Six to eight focused hours if you read as you go.
## What you'll learn
- Why "write the file out again" is not persistence, and what a torn write does to your data
- The append-only log: why every serious database writes changes to a log *first*
- What `fsync` actually promises, and the three layers a byte passes through before it's truly on disk
- How a database restarts: replaying the log, detecting a half-written record, and recovering
- What an index physically is: a map from key to file offset, so reads don't scan
- Compaction: why logs grow forever and how engines reclaim the space without downtime
- How to put a real wire protocol in front of it all with a threaded TCP server
- Where your engine sits next to Redis, LevelDB, and SQLite - measured plainly
## The phases
1. **[A Dict, and Why Persistence Is Hard](01-the-dict-and-the-problem.md)** - the in-memory store is ten lines; every naive way to save it to disk fails in an instructive way.
2. **[The Append-Only Log](02-the-append-only-log.md)** - the write path: a binary record format, checksums, and what `fsync` really buys you.
3. **[Replay and the Index](03-replay-and-the-index.md)** - the read path: rebuild state from the log on startup, survive a crash mid-write, and stop keeping values in RAM.
4. **[Compaction](04-compaction.md)** - the log grows forever; rewrite it live, swap it atomically, lose nothing.
5. **[A TCP Server](05-a-tcp-server.md)** - a SET/GET/DEL protocol over sockets, so any program on the machine can talk to your database.
6. **[Benchmarks, and What Redis Does Differently](06-benchmarks-and-real-databases.md)** - measure your engine for real, then compare its design to Redis, LevelDB, and SQLite without hand-waving.
Each phase ends with a store that runs. By phase 3 your data survives `kill -9`. By phase 5 it's a server. Let's break persistence first, so you believe the fix.
---
# A Dict, and Why Persistence Is Hard
Ask a senior engineer what a key-value store is and you'll get a shrug: "a dict with persistence." The shrug is earned - the dict part takes one minute. The persistence part is the rest of this guide, because *doing it without losing data* is one of the genuinely hard problems in computing, and every naive attempt fails in a way that teaches you something. This phase builds the dict, then breaks persistence twice on purpose, so that the design in phase 2 feels inevitable instead of clever.
Make a project folder and let's start with the one-minute part.
```bash
mkdir kvstore
cd kvstore
```
## The store, in memory
Create `kv.py`:
```python
class MemoryKV:
def __init__(self):
self._data = {}
def set(self, key, value):
self._data[key] = value
def get(self, key):
return self._data.get(key)
def delete(self, key):
self._data.pop(key, None)
```
That's a complete key-value store with one flaw: it *is* the process. Python dicts live in RAM, RAM belongs to the process, and when the process exits - cleanly, by crash, by `kill`, by power cut - the operating system reclaims that memory without ceremony. Every key you set is gone.
This isn't a strawman, by the way. Memcached is essentially this class, hardened and put behind a network port, and it's deployed everywhere - as a *cache*, where losing everything on restart is an accepted cost. The moment you need data to outlive the process, you need a **database**, and the difference between the two is everything below this line.
## Naive attempt #1: write the whole thing out
The obvious fix: serialize the dict to a file on every write, load it on startup.
```python
import json
class SnapshotKV:
def __init__(self, path):
self.path = path
try:
with open(path) as f:
self._data = json.load(f)
except FileNotFoundError:
self._data = {}
def set(self, key, value):
self._data[key] = value
with open(self.path, "w") as f:
json.dump(self._data, f)
def get(self, key):
return self._data.get(key)
def delete(self, key):
self._data.pop(key, None)
with open(self.path, "w") as f:
json.dump(self._data, f)
```
This works. Data survives restart. And it hides two failures that get worse the longer you don't notice them.
**Failure 1: every write rewrites everything.** Setting one key serializes and writes the *entire* dict. With ten keys, who cares. With a million keys totaling 2 GB, changing one 40-byte value costs a 2 GB disk write. Write cost grows with the size of the store, not the size of the change - O(total data) per write. No amount of hardware outruns that; the design is wrong.
**Failure 2: a crash mid-write destroys everything.** `open(path, "w")` truncates the file to zero bytes *before* writing the new content. If the process dies between the truncate and the final flush - crash, `kill -9`, power loss - you're left with a partial file. Watch what a partial JSON file is worth:
```console
$ python
>>> import json
>>> json.dump({"name": "Ada", "language": "python", "year": "1843"}, open("snapshot.json", "w"))
>>> # simulate the crash: keep only the first half of the file
>>> import os
>>> size = os.path.getsize("snapshot.json")
>>> with open("snapshot.json", "r+b") as f:
... f.truncate(size // 2)
...
>>> open("snapshot.json").read()
'{"name": "Ada", "language"'
>>> json.load(open("snapshot.json"))
Traceback (most recent call last):
...
json.decoder.JSONDecodeError: Expecting ':' delimiter: line 1 column 27 (char 26)
```
*What just happened:* We cut the file where a crash might have cut it, and `json.load` refused the remains. Note the blast radius: one interrupted write didn't lose one key - it lost **the entire database**, including keys written days ago that were sitting safely on disk until this write rewrote them. This is called a **torn write**, and defending against it is half of what a storage engine is for.
📝 **Terminology:** a *torn write* is any write that was interrupted partway, leaving a mix of new bytes, old bytes, and garbage. Disks and operating systems only promise atomicity for tiny writes (a sector), so any multi-byte file write can tear.
## The patch that half-works: atomic rename
There's a classic fix for failure 2: never overwrite the real file. Write the new snapshot to a temporary file, then rename it over the original.
```python
import os
def save_atomically(data, path):
tmp = path + ".tmp"
with open(tmp, "w") as f:
json.dump(data, f)
f.flush()
os.fsync(f.fileno()) # force it to disk before the swap
os.replace(tmp, path) # atomic on POSIX and Windows
```
`os.replace` is atomic: readers see the complete old file or the complete new file, never a mixture. If you crash before the rename, the original is untouched; if you crash after, the new one is complete. Torn writes: solved. Remember this move - it comes back as the finale of phase 4, doing serious work.
But look at what it *didn't* fix. Every write still serializes and rewrites the entire store. The atomic rename makes the O(total data) write safe, not cheap. Patch applied, disease intact.
## The reframe that fixes both
Both failures come from the same wrong idea: that the file should always contain *the current state* of the store. Keeping a file constantly equal to your state means rewriting it on every change - which is where both the cost and the tear risk come from.
Real storage engines flip the idea. The file doesn't store the state. The file stores **the history of changes** - and the state is whatever that history adds up to. A change is small, so writing one is cheap (failure 1 gone). A change is *appended* after the existing bytes, so a crash can only damage the newest record, never the accumulated past (failure 2's blast radius shrinks from "everything" to "the last write").
That file has a name: the **append-only log**. It's the beating heart of nearly every database you've ever used - PostgreSQL's write-ahead log, Redis's append-only file, Kafka's entire existence. In phase 2 you'll design its record format byte by byte and build the write path.
## Recap
1. The in-memory store is a dict; the entire project is about making it survive the death of its process.
2. Snapshotting the whole store per write costs O(total data) per change - the cost grows with the store, not the change.
3. A crash mid-rewrite is a torn write, and with a single snapshot file it destroys *everything*, not only the interrupted write.
4. Write-temp-then-`os.replace` makes a rewrite atomic, but not cheap. File this trick away for phase 4.
5. The fix for both is to stop storing state and start storing *changes*: the append-only log.
Before moving on, make sure the failure modes stuck - they justify every decision in the next two phases.
```quiz
[
{
"q": "SnapshotKV rewrites the whole store on every set(). What are its two fundamental problems?",
"choices": [
"JSON can't store nested data, and Python file writes are slow",
"Each write costs O(total data), and a crash mid-rewrite can corrupt the entire file",
"The dict uses too much RAM, and JSON files can't exceed 2 GB"
],
"answer": 1,
"explain": "Writing one key serializes everything (cost grows with the store), and because open(path, 'w') truncates first, a crash mid-write leaves a partial, unparseable file - losing even data written long ago."
},
{
"q": "The write-to-temp-file-then-os.replace() trick fixes which of the two problems?",
"choices": [
"The O(total data) cost of each write",
"Corruption from a crash mid-write",
"Both of them"
],
"answer": 1,
"explain": "os.replace is atomic, so readers see the complete old file or the complete new file - never a torn mixture. But you still rewrote the entire store to produce the temp file."
},
{
"q": "Why does an append-only log shrink the blast radius of a crash?",
"choices": [
"Appends are buffered in RAM until the file is closed",
"The log is written twice, so one copy always survives",
"A crash can only damage the newest record being appended - the bytes of every earlier record are never touched again"
],
"answer": 2,
"explain": "Appending never modifies existing bytes. The accumulated history is physically out of reach of the write that crashes, so at most the in-flight record is lost."
}
]
```
---
# The Append-Only Log - the Write Path
Phase 1 ended with a decision: the file on disk stores *changes*, not state. This phase builds the machinery that writes those changes - the record format, the append, and the part almost everyone gets wrong, which is what it actually takes to get bytes onto a disk. By the end, every `set` and `delete` will be recorded permanently, in a format that can detect its own corruption.
## Designing the record
A record has to carry a key and a value, back to back, in one file with thousands of siblings. That raises the first real design question of the project: when you read the file later, **how do you know where one record ends and the next begins?**
Text formats answer "a newline separates them" - and instantly ban newlines from your values. A database can't dictate what bytes your values contain; you might store JSON, a pickle, an image. The standard answer is the one nearly every binary format uses: **length prefixes**. Before the data, write how long the data is. The reader reads the lengths, then knows exactly how many bytes to consume.
Here's our record, byte by byte:
```text
[ crc:4 ][ key_len:4 ][ val_len:4 ][ key bytes... ][ value bytes... ]
```
- `key_len` and `val_len` are 4-byte integers giving the sizes of the key and value.
- `crc` is a 4-byte **checksum** of everything after it. When reading, recompute the checksum; if it doesn't match what's stored, the record is damaged - a torn write from a crash, a flipped bit. Without it, corrupt bytes parse as garbage data and you serve wrong answers with a straight face. With it, damage is *detectable*, and phase 3 turns detectable into recoverable.
- Deletes need recording too - "this key is gone" is a change like any other. We mark one with `val_len = -1` and no value bytes. A delete record is called a **tombstone**, and the name is standard vocabulary in storage engines.
📝 **Terminology:** *CRC32* is a fast 32-bit checksum, in Python's stdlib as `zlib.crc32`. It detects accidental corruption; it is not cryptographic and won't stop a malicious editor - the right tool here, where the enemy is crashes, not attackers.
Notice what a record *doesn't* have: types, encodings, field names. To a storage engine, keys and values are **bytes**, period. Meaning belongs to the caller. That's why everything below traffics in `b"name"` rather than `"name"` - the plain fact of `bytes` in, `bytes` out is exactly how real engines think.
## Your turn: encode_record
Before the full file, write the encoder yourself - the format above is everything you need: `[crc:4][key_len:4][val_len:4][key bytes][value bytes]`, little-endian, and a delete stores `val_len = -1` (`TOMBSTONE`) with no value bytes. The crc covers everything after itself.
```python
import struct
import zlib
TOMBSTONE = -1
def encode_record(key: bytes, value) -> bytes:
# your turn: pack the lengths (+ key + value, or TOMBSTONE for a delete),
# then prepend a 4-byte crc32 of everything after it
return b""
```
`struct.pack` and `zlib.crc32` are the only two stdlib pieces involved - `struct.pack(" bytes:
if value is None: # a delete
body = struct.pack(">> from kv import encode_record
>>> encode_record(b"name", b"Ada")
b'\x95GJ\xfb\x04\x00\x00\x00\x03\x00\x00\x00nameAda'
>>> len(encode_record(b"name", b"Ada"))
19
```
*What just happened:* 19 bytes - 4 of CRC (`\x95GJ\xfb`), then `\x04\x00\x00\x00` (key length 4, little-endian), `\x03\x00\x00\x00` (value length 3), then `nameAda`. You can read your own file format off the screen. Hold onto that feeling; it's rarer than it should be.
## The write path
Now the store. Writes append a record *and* update an in-memory dict, so reads stay instant:
```python
class KV:
def __init__(self, path):
self.path = path
self._data = {} # key -> value (rebuilt in phase 3)
self._log = open(path, "ab")
def set(self, key: bytes, value: bytes):
self._log.write(encode_record(key, value))
self._log.flush()
os.fsync(self._log.fileno())
self._data[key] = value
def get(self, key: bytes):
return self._data.get(key)
def delete(self, key: bytes) -> bool:
if key not in self._data:
return False
self._log.write(encode_record(key, None))
self._log.flush()
os.fsync(self._log.fileno())
del self._data[key]
return True
def close(self):
self._log.close()
```
`open(path, "ab")` is append-binary mode: every write lands at the end of the file, and the OS enforces it. There is no code path in this class that can modify an existing byte - the safety property from phase 1, guaranteed by construction.
Two details deserve a hard look.
**The order inside `set` is a law, not a preference.** Log first, memory second. If the process dies between the two lines, the log has a record the dict doesn't - harmless, since the dict is rebuilt from the log anyway. Flip the order and a reader could `get` a value that a crash then erases forever: the store *lied*. "Nothing is acknowledged or visible until the log has it" is the **write-ahead** principle, and it's the same rule that makes PostgreSQL's WAL work - the databases guides show it powering [durability in ACID](/guides/transactions-and-acid) and [point-in-time recovery](/guides/database-backups-and-restores). You've now written one.
**`flush` and `fsync` are not the same thing, and the difference is your data.** A byte you "write" crosses three layers before it's safe:
```text
your process (Python's buffer) --flush()--> OS page cache --fsync()--> the disk
```
`self._log.write(...)` may only copy bytes into Python's userspace buffer. `flush()` pushes them to the operating system - now they survive your *process* crashing, because the OS owns them. But the OS keeps them in RAM (the page cache) and writes them to the physical disk at its leisure, seconds later. If the *machine* loses power in that window, flushed data is gone. `os.fsync()` is the third push: it blocks until the disk itself confirms the bytes are persistent. Only after `fsync` returns can you truly tell a caller "your write is durable."
That certainty has a price - `fsync` waits for a physical device, thousands of times slower than a memory copy. Every real database sits somewhere on this durability-versus-speed dial, and in phase 6 you'll measure the gap on your own machine and see exactly why Redis offers three settings for it. For now we pay full price on every write, because correct-then-fast beats fast-then-sorry.
## Watch the log grow
```console
$ python
>>> from kv import KV
>>> db = KV("data.log")
>>> db.set(b"name", b"Ada")
>>> db.set(b"language", b"python")
>>> db.get(b"name")
b'Ada'
>>> db.close()
>>> open("data.log", "rb").read()
b'\x95GJ\xfb\x04\x00\x00\x00\x03\x00\x00\x00nameAda\xd7\x02\x19\x9f\x08\x00\x00\x00\x06\x00\x00\x00languagepython'
```
*What just happened:* Two records, 45 bytes, sitting end to end on disk. You can see the boundary yourself: 19 bytes for `name=Ada`, then the second CRC starts. That file is now a permanent, ordered history of every change this store has seen.
⚠️ **Gotcha:** overwriting a key does *not* modify its old record. `db.set(b"name", b"Grace")` appends a third record; the `Ada` bytes remain on disk, dead but present. The log accumulates every version of everything - that's the price of never touching old bytes, and it's the entire reason phase 4 exists.
## The hole we're leaving open
Restart the REPL and read a key back. You'll get `None`. The log holds the truth - you can see the bytes - but `__init__` never *reads* it; the dict starts empty every time. We've built a store that remembers everything and recalls nothing.
That's the read path, and it's phase 3's job: replay the log on startup, rebuild the state, and handle the record that was halfway written when the power died.
```quiz
[
{
"q": "Why length-prefix each record instead of separating records with a newline?",
"choices": [
"Length prefixes compress better than delimiters",
"A delimiter byte could legally appear inside a value, corrupting the framing - length prefixes let values contain any bytes at all",
"Newlines behave differently on Windows and Linux"
],
"answer": 1,
"explain": "A store can't dictate what bytes values contain. With a length prefix the reader knows exactly how many bytes to consume, so values can hold newlines, null bytes, anything."
},
{
"q": "Your write() and flush() both succeeded, then the machine lost power. Is the record safe without fsync?",
"choices": [
"Yes - flush() writes it to the file",
"No - flush() only hands the bytes to the OS page cache in RAM; only fsync() waits until the disk itself has them",
"Yes, as long as the file was opened in append mode"
],
"answer": 1,
"explain": "flush() protects you from your process dying. Power loss wipes the OS page cache too - fsync() is the call that blocks until the physical disk confirms persistence."
},
{
"q": "In set(), why must the log append happen before the in-memory dict update?",
"choices": [
"Because the dict update is faster, so total latency is lower this way",
"So that a reader can never observe a value that a crash could still erase - nothing is visible until the log has it",
"Because Python evaluates statements bottom to top inside methods"
],
"answer": 1,
"explain": "Memory-first would let a get() return a value that exists nowhere durable. Log-first means the worst crash outcome is a logged record nobody saw yet - harmless. That's the write-ahead principle."
}
]
```
---
# Replay and the Index - the Read Path
Your store writes everything and remembers nothing across a restart. This phase closes the loop: on startup, read the log front to back and rebuild the state it describes. Along the way you'll handle the ugliest moment in a database's life - waking up next to a record that was half-written when the machine died - and then make one more upgrade that turns "a dict with a log" into an actual storage engine design with a name.
## Replay: the log is the database
Here's the mental shift this phase runs on. The dict is not the database. The **log** is the database - the complete, ordered history of every change. The dict is a *cache of the log's final state*, disposable and rebuildable at any time by one procedure:
Walk the log record by record. For each `set`, put the key in the dict. For each tombstone, remove it. When you reach the end, the dict holds exactly the state the store had when it last ran. A key written five times shows up five times in the log; the walk naturally keeps the last one, because later records overwrite earlier ones in the dict. **Last write wins**, by construction.
This is not a startup hack - it's the deepest pattern in the field. PostgreSQL replays its WAL after a crash. Redis replays its append-only file on boot. A [database replica](/guides/scaling-a-database) is a machine replaying the leader's log a moment behind. You're about to write the same procedure they run.
## The torn record at the end
One thing stands between us and a working replay. Phase 2's crash story: the process died *mid-append*. The log now ends with a fragment - maybe half a header, maybe a full header promising 300 bytes of value with only 120 present, maybe all the bytes but garbage in them. Your replay will walk straight into it.
The CRC and length prefixes were built for this moment. Reading a record can fail three ways, and each one means the same thing - *the log ends here*:
1. **Short header.** Fewer than 12 bytes remain. Either the file ended cleanly, or a header was torn. Stop.
2. **Short body.** The header promises more key/value bytes than the file has. The append never finished. Stop.
3. **Bad checksum.** All the bytes are present but the CRC doesn't match. The bytes are damaged; and since everything after a damaged record has unknowable framing, trust nothing past it. Stop.
In all three cases the move is the same: keep everything up to the last record that verified, and **truncate the file** back to that point, amputating the torn tail. The failed write is erased as if it never happened - which is the correct semantics, because it was never acknowledged. No caller was ever told that write succeeded, so no promise is broken by dropping it.
## From values in RAM to an index
While we're rebuilding the read path, fix a scaling problem before it bites. So far the dict maps key → *value*, meaning every value in the database lives in RAM. A store holding 10 GB of values needs 10 GB of memory - the log made writes durable but did nothing for memory.
The fix: the dict stops holding values and starts holding **directions to values**. Each key maps to `(offset, length)` - where in the log file the current value's bytes sit, and how many there are. A `get` becomes: look up the offset (dict lookup, nanoseconds), `seek` there, read exactly `length` bytes (one disk read, usually served from the OS page cache). Now RAM holds only keys and two integers per key; values live on disk where 10 GB is cheap.
```mermaid
flowchart LR
G["get(b'name')"] --> X["index
{b'name': (16, 3)}"]
X -->|"seek(16), read(3)"| L["data.log"]
L --> V["b'Ada'"]
```
That dict-of-offsets is an **index** in the full database sense of the word: a structure that turns "search everything" into "go directly there." It's the same job an index does for [a slow SQL query](/guides/why-is-my-query-slow) - only here you can see the mechanism with no abstraction in the way: literally a Python dict pointing into a file. This exact design - append-only log plus in-memory hash of key → offset - is **Bitcask**, the engine that shipped inside the Riak database, where the index goes by "keydir."
The trade, stated plainly: every *key* must still fit in RAM (values don't), and a hash index can't answer range queries like "every key between `user:100` and `user:200`" - hash maps have no order. Phase 6 shows what LevelDB pays to lift those limits.
## The full engine
Here is the complete `kv.py` - replay, recovery, and the index, replacing phase 2's class. This is the heart of the whole project, about ninety lines:
```python
import os
import struct
import zlib
# One record on disk:
# [crc:4][key_len:4][val_len:4][key bytes][value bytes]
# crc covers everything after itself. val_len == -1 marks a delete.
HEADER = struct.Struct(" bytes:
if value is None: # a delete
body = struct.pack(" (value_offset, value_len)
self._replay()
self._log = open(path, "ab")
self._reader = open(path, "rb")
def _replay(self):
if not os.path.exists(self.path):
self._offset = 0
return
good = 0
with open(self.path, "rb") as f:
while True:
pos = f.tell()
header = f.read(HEADER.size)
if len(header) < HEADER.size:
break # clean end of file, or a torn header
crc, key_len, val_len = HEADER.unpack(header)
is_delete = val_len == TOMBSTONE
body_len = key_len + (0 if is_delete else val_len)
body = f.read(body_len)
if len(body) < body_len:
break # torn record: the write never finished
if zlib.crc32(header[4:] + body) != crc:
break # corrupt: trust nothing from here on
key = body[:key_len]
if is_delete:
self._index.pop(key, None)
else:
value_off = pos + HEADER.size + key_len
self._index[key] = (value_off, val_len)
good = f.tell()
if good < os.path.getsize(self.path):
with open(self.path, "r+b") as f:
f.truncate(good) # drop the torn tail
self._offset = good
def set(self, key: bytes, value: bytes):
record = encode_record(key, value)
self._log.write(record)
self._log.flush()
os.fsync(self._log.fileno())
self._index[key] = (self._offset + HEADER.size + len(key), len(value))
self._offset += len(record)
def get(self, key: bytes):
entry = self._index.get(key)
if entry is None:
return None
offset, length = entry
self._reader.seek(offset)
return self._reader.read(length)
def delete(self, key: bytes) -> bool:
if key not in self._index:
return False
record = encode_record(key, None)
self._log.write(record)
self._log.flush()
os.fsync(self._log.fileno())
self._offset += len(record)
del self._index[key]
return True
def close(self):
self._log.close()
self._reader.close()
```
Walk the parts that carry weight:
- **`_replay` is the read-side of the record format.** It reads a header, computes how much body to expect (tombstones have no value bytes), reads it, verifies the CRC over exactly the bytes the writer checksummed (`header[4:] + body` - the lengths, key, and value). The three `break`s are the three failure modes; `good` always marks the end of the last verified record, and the `truncate(good)` amputates anything after it.
- **Two file handles.** `_log` is opened in append mode and only writes; `_reader` is opened read-only and only seeks. Splitting them means the writer's position (always the end) and the reader's position (wherever the last `get` went) never fight over one shared file cursor. Real engines do the same - one appender, many readers.
- **The store tracks its own end.** `self._offset` is the file's length, maintained arithmetically. When `set` appends a record, it already knows the value's offset - `self._offset + HEADER.size + len(key)` - without asking the filesystem. Bookkeeping beats syscalls.
- **`get` never scans.** Index lookup, seek, read. The cost of a read does not depend on the size of the database. That sentence is what "indexed" means.
## Prove it survives
The demo the last two phases have been promising - kill the store, corrupt the file, watch it recover. Delete any old `data.log` first, then:
```console
$ python
>>> from kv import KV
>>> db = KV("data.log")
>>> db.set(b"name", b"Ada")
>>> db.set(b"language", b"python")
>>> db.set(b"name", b"Grace")
>>> db.delete(b"language")
True
>>> db.close()
>>> import os; os.path.getsize("data.log")
86
```
Four records: two sets, an overwrite, a tombstone. Now simulate the crash - a power cut halfway through appending a fifth record is indistinguishable from writing only its first 11 bytes:
```console
>>> from kv import encode_record
>>> record = encode_record(b"city", b"London")
>>> with open("data.log", "ab") as f:
... f.write(record[:11])
...
11
>>> os.path.getsize("data.log")
97
>>> db = KV("data.log") # reopen: replay + recovery run
>>> db.get(b"name")
b'Grace'
>>> db.get(b"language") is None
True
>>> db.get(b"city") is None
True
>>> os.path.getsize("data.log")
86
```
*What just happened:* Replay walked four good records - `name` ended up as `Grace` (last write wins), `language` came and went (the tombstone removed it) - then hit a header promising more bytes than existed, stopped, and truncated the file from 97 bytes back to 86. The torn write vanished; every acknowledged write survived. Compare that to phase 1, where the same crash cost the entire file.
## What you have now
A crash-safe, persistent key-value store: durable writes, startup recovery, and reads that go straight to the data through an index. It has one growing embarrassment - that overwrite of `name` left `Ada`'s corpse in the log, and the log never shrinks. A store that's written a billion updates to one key holds a billion records for it. Phase 4 takes out the garbage.
```quiz
[
{
"q": "What does the in-memory index map a key to?",
"choices": [
"The value itself, kept in RAM for speed",
"The file offset and length of the value's bytes in the log",
"The CRC32 checksum of the value"
],
"answer": 1,
"explain": "The index holds directions, not data: (offset, length). A get() seeks to the offset and reads exactly length bytes, so values live on disk and only keys plus two integers live in RAM."
},
{
"q": "During replay, the last record's header promises 300 value bytes but only 120 remain in the file. What does the store do?",
"choices": [
"Raise an exception and refuse to open - the database is corrupt",
"Keep the 120 bytes as a best-effort partial value",
"Truncate the file back to the end of the last verified record and carry on - the torn write was never acknowledged, so dropping it breaks no promise"
],
"answer": 2,
"explain": "A torn tail is the expected signature of a crash mid-append. Every record before it verified fine, and the interrupted write was never confirmed to any caller - amputating it restores a consistent store."
},
{
"q": "Where does the truth live in this design?",
"choices": [
"In the log - the index is a disposable cache that can always be rebuilt by replaying it",
"In the index - the log is a backup of it",
"Split evenly: keys in the index, values in the log"
],
"answer": 0,
"explain": "The log is the complete ordered history; replaying it reconstructs the index from nothing, which is exactly what __init__ does on every startup."
}
]
```
---
# Compaction - the Log Can't Grow Forever
Append-only bought you crash safety by promising to never touch old bytes. The bill for that promise arrives now: the old bytes pile up. Every overwrite leaves the previous value dead in the file; every delete *adds* bytes (a tombstone) to record a removal. A store whose live data fits in a kilobyte can sit on a gigabyte of history. This phase measures the waste, then reclaims it with the one trick you already know - and the crash-safety analysis of that trick is the best part of the whole project.
## Measure the damage
Start with a fresh log (delete `data.log`) and update one key a thousand times:
```console
$ python
>>> from kv import KV
>>> db = KV("data.log")
>>> for i in range(1000):
... db.set(b"counter", str(i).encode())
...
>>> db.get(b"counter")
b'999'
>>> import os; os.path.getsize("data.log")
21890
```
One live key, three live value bytes - and 21,890 bytes of file. Every one of the thousand records is still in there; 999 of them are unreachable, because the index points only at the last. The ratio only gets worse with time: the file grows with *write traffic*, while the useful content grows with *data size*. Those are different curves, and the gap between them is garbage.
## Your turn: wasted_bytes
Before the reveal, write it yourself. `wasted_bytes` returns how many bytes in the log are dead: work out what a file holding *only* the live records would take - one `HEADER.size` plus the key length plus the value length, per live key in `self._index` - then subtract that from the actual file size, `self._offset`.
```python
def wasted_bytes(self) -> int:
# your turn
return 0
```
`self._index` (key -> `(offset, length)`) and `self._offset` are already on `self` from phase 3; `HEADER.size` is the module-level constant from phase 2. Add it to `KV`, rerun the thousand-`set` loop above, and check your number against the `21868` a few lines down.
It's worth being able to see the gap from inside the store. Add this small method to `KV`:
```python
def wasted_bytes(self) -> int:
live = sum(HEADER.size + len(key) + length
for key, (_, length) in self._index.items())
return self._offset - live
```
It computes what a file holding *only* the live records would take (one header + key + value per live key) and subtracts that from the actual file size:
```console
>>> db.wasted_bytes()
21868
```
21,868 of 21,890 bytes are dead. Time to collect the garbage.
## The idea: rewrite only what's alive
The index already knows exactly which records matter - it points at the one live value per key. So: walk the index, read each live value, write it as a fresh record into a **new** file, and when the new file is complete, swap it in place of the old one. The dead 999 versions never get copied at all. This is **compaction**.
Two phase-old friends do the heavy lifting. The walk-and-copy produces what phase 1's snapshot writer produced - a file of exactly the current state - but produced *offline, on the side*, while the real log keeps its integrity. And the swap is phase 1's atomic rename, `os.replace`, finally deployed where it belongs.
```python
def compact(self):
tmp_path = self.path + ".compact"
new_index = {}
offset = 0
with open(tmp_path, "wb") as tmp:
for key, (old_off, length) in self._index.items():
self._reader.seek(old_off)
value = self._reader.read(length)
record = encode_record(key, value)
tmp.write(record)
new_index[key] = (offset + HEADER.size + len(key), length)
offset += len(record)
tmp.flush()
os.fsync(tmp.fileno())
self._log.close()
self._reader.close()
os.replace(tmp_path, self.path) # atomic swap
self._log = open(self.path, "ab")
self._reader = open(self.path, "rb")
self._index = new_index
self._offset = offset
```
Read it as three acts:
1. **Build the replacement.** Every live record is copied into `data.log.compact`, and a matching `new_index` is built as we go - the offsets in the new file differ from the old, so the index must be rebuilt to point at them. The `fsync` before the swap matters: the new file must be *fully on disk* before it's allowed to become the real one.
2. **Close, then swap.** `os.replace` atomically substitutes the new file for the old. The handles are closed first because Windows refuses to replace a file that's held open - on Linux you'd get away without it, and "works on my OS" is not a property you want in a storage engine.
3. **Point at the new world.** Fresh handles, the new index, the new (much smaller) offset.
## The crash-safety audit
Any operation that touches the live data file must survive this question: *what happens if we crash at every single line?* Walk it:
- **Crash while building `tmp`?** The real log was never touched - reopen, replay, nothing lost. A stale `data.log.compact` litters the directory and gets overwritten by the next compaction. (A tidy engine would delete stray `.compact` files on startup; ours tolerates them.)
- **Crash after the fsync, before the replace?** Same story. Old log intact, new file complete but unused. No harm.
- **Crash *during* the replace?** This is why it must be `os.replace` and not copy-over. The rename is atomic: after reboot the path names either the complete old file or the complete new file. Both are valid logs; replay works on either. There is no in-between to be caught in.
- **Crash after the replace?** The new compact log *is* the database now, and it's complete. Done.
Every line, a survivable crash. That's the standard your `compact` now meets, and it's the standard any code touching a data file has to meet.
One subtlety worth naming: tombstones don't survive compaction at all. A deleted key isn't in the index, so nothing about it is copied - the delete becomes true *absence* rather than a recorded event. That works because we compact into a single file that replaces all history. Engines that keep multiple log segments (Bitcask, LevelDB) must *retain* tombstones until every older segment that might still hold the key is merged away - drop the tombstone too early and a zombie value from an old segment comes back to life. Multi-file designs buy incremental compaction at the price of that kind of bookkeeping.
## Run it
Continuing the session from above:
```console
>>> before = os.path.getsize("data.log")
>>> db.compact()
>>> os.path.getsize("data.log")
22
>>> before
21890
>>> db.get(b"counter")
b'999'
>>> db.wasted_bytes()
0
>>> db.close()
>>> db = KV("data.log") # replay the compacted log
>>> db.get(b"counter")
b'999'
```
*What just happened:* 21,890 bytes became 22 - one header, seven key bytes, three value bytes - with the store live the whole time, and the compacted file replays like any other log, because it *is* one: a log whose history happens to contain no mistakes.
**When to trigger it** is a policy question, separate from the mechanism. A common rule: compact when `wasted_bytes()` exceeds half the file, checked occasionally rather than per-write. We leave `compact()` manual - you have the measuring stick and the lever, and wiring a threshold to them is a three-line `if` you can place where you like.
## You've now built what real engines run
This exact rhythm - append until wasteful, rewrite the live set, swap atomically - is everywhere once you know its shape. Redis calls it *AOF rewrite*: the append-only file is rewritten as the minimal command sequence producing the current state. Bitcask calls it *merging* its data files. LevelDB's *compaction* does it continuously in the background across sorted files (phase 6 digs into that). PostgreSQL's `VACUUM` is the same debt being paid in a page-based world - dead row versions from updates get reclaimed. Every database that never overwrites in place must, eventually, take out the garbage.
Your engine is complete: durable, crash-safe on both the write and compact paths, indexed, and now able to run forever without eating the disk. What it can't do yet is serve anyone but you. Phase 5 puts a network protocol in front of it.
```quiz
[
{
"q": "The store holds one key, updated a million times. Roughly what does the log contain before compaction?",
"choices": [
"One record - sets overwrite in place",
"A million records, of which exactly one is reachable through the index",
"Two records - the first and the latest"
],
"answer": 1,
"explain": "Append-only means every version is retained on disk. The index points only at the newest; the other 999,999 are dead bytes waiting for compaction."
},
{
"q": "Why is compact() safe even if the process dies halfway through writing the new file?",
"choices": [
"Because the new file is written with fsync after every record",
"Because the live log is never modified during the build - the swap via os.replace happens only after the replacement is complete and fsynced, and the rename itself is atomic",
"Because Python flushes all open files automatically when a process crashes"
],
"answer": 1,
"explain": "All work happens in a side file. Until os.replace, the old log is untouched and authoritative; after it, the new one is complete. The atomic rename leaves no in-between state to crash into."
},
{
"q": "Why can our compaction drop tombstones entirely, when multi-segment engines like Bitcask must keep them around during merges?",
"choices": [
"Our tombstones are smaller than Bitcask's",
"We compact everything into a single file that replaces all history, so a deleted key never appears at all - there's no older segment left that could resurrect it",
"Python's garbage collector removes them from the file"
],
"answer": 1,
"explain": "With multiple segments, an old segment may still hold a value for the deleted key; the tombstone must survive until that segment is merged away, or the old value comes back. Compacting to one file removes the entire past at once."
}
]
```
---
# A TCP Server - Speaking to Other Programs
Everything so far lives inside one Python process - to use the store, you have to *be* the store. Real databases are servers: a separate long-running process that any program can talk to over a socket, in any language, using an agreed protocol. That separation is the difference between a library and a database. This phase builds it, and in doing so runs into the problem that shapes every database server's architecture: two clients writing at once.
## Design the protocol
A wire protocol is a contract about bytes: what a request looks like, what a response looks like, and how everyone knows where messages end. Ours is line-based - one request per line, one response per line:
| Request | Response | Meaning |
|---|---|---|
| `SET ` | `OK` | Store the value under the key |
| `GET ` | `VALUE ` or `NOT_FOUND` | Fetch the current value |
| `DEL ` | `DELETED` or `NOT_FOUND` | Remove the key |
| anything else | `ERR unknown command` | You made a typo; the server survives it |
If that shape looks familiar, it should - it's a deliberate cousin of Redis's original inline protocol and memcached's text protocol. Text protocols win for a first version because you can debug them with your eyes.
The framing rule - "a message ends at `\n`" - has the exact flaw you identified in phase 2: a value containing a newline breaks the protocol. We accept the limitation knowingly for the wire (our record format on disk still handles arbitrary bytes fine), and the recap names how grown-up protocols fix it. Protocol design is trade-off design; the important thing is to *know* which corner you cut.
## The server
Create `server.py` next to `kv.py`:
```python
import socketserver
import threading
from kv import KV
store = KV("data.log")
lock = threading.Lock()
class Handler(socketserver.StreamRequestHandler):
def handle(self):
while True:
line = self.rfile.readline()
if not line:
break # client hung up
parts = line.strip().split(b" ", 2)
cmd = parts[0].upper()
if cmd == b"SET" and len(parts) == 3:
with lock:
store.set(parts[1], parts[2])
self.wfile.write(b"OK\n")
elif cmd == b"GET" and len(parts) == 2:
with lock:
value = store.get(parts[1])
if value is None:
self.wfile.write(b"NOT_FOUND\n")
else:
self.wfile.write(b"VALUE " + value + b"\n")
elif cmd == b"DEL" and len(parts) == 2:
with lock:
found = store.delete(parts[1])
self.wfile.write(b"DELETED\n" if found else b"NOT_FOUND\n")
else:
self.wfile.write(b"ERR unknown command\n")
class Server(socketserver.ThreadingTCPServer):
allow_reuse_address = True
daemon_threads = True
if __name__ == "__main__":
with Server(("127.0.0.1", 5555), Handler) as server:
print("kv server listening on 127.0.0.1:5555")
server.serve_forever()
```
The load-bearing pieces:
- **`ThreadingTCPServer` spawns one thread per client connection.** Each connected client gets its own `Handler` running `handle()` in its own thread, looping over that client's lines until it disconnects. The stdlib does the accept-loop and thread plumbing; you write only the conversation.
- **`StreamRequestHandler` gives you `rfile` and `wfile`** - the socket dressed up as file objects. `rfile.readline()` blocks until a full line arrives (the framing rule, implemented for free); an empty result means the client closed the connection.
- **`split(b" ", 2)` splits at most twice**, so in `SET user:1 Ada Lovelace` the value keeps its space: everything after the second space is value bytes.
- **`allow_reuse_address`** spares you the classic dev-loop pain: without it, restarting the server within a minute of stopping it can fail with "address already in use" while the OS holds the old socket in a cool-down state.
- **`daemon_threads`** lets Ctrl+C actually stop the process instead of waiting on every open client connection.
## The lock is not optional
The line that deserves the most respect in that file is `lock = threading.Lock()`, so let's earn it. With one thread per client, two clients can call `store.set` **at the same time**. Trace what's inside `set`: append to the log, then update the index and `self._offset`. Interleave two of those and you get real corruption, not theoretical ickiness:
- Thread A computes its record's offset from `self._offset`. Before A finishes, thread B does the same - *the same offset*. Both index entries are wrong; one points into the middle of the other's record. A later `get` returns spliced garbage - which the CRC won't catch, because CRCs are checked on *replay*, not on reads through the index.
- The interleaved `_offset += len(record)` updates can lose one of the additions entirely, shifting every future offset in the index.
The lock makes each command a critical section: one thread at a time touches the store, everyone else queues for microseconds. Simple, correct, and upfront about its ceiling - under heavy parallel load, one global lock becomes the bottleneck. It's the right first answer anyway, and it's in good company: Redis processes commands one at a time by design (an event loop rather than a lock, but the same serial guarantee) and derives famous simplicity from it. When people say "Redis is single-threaded," *this* is the problem being dodged.
⚠️ **Gotcha:** the lock protects you only because every client goes through this one server process. If a second *process* opened `data.log` in append mode, the OS would happily interleave records from both - the lock never sees it. One writer process per log file is a rule, not a suggestion. (Real engines enforce it with a lock file on disk; SQLite's famous "database is locked" is that enforcement talking.)
## A client
The server speaks a protocol, so prove it with a client that isn't you-in-a-REPL. Create `client.py`:
```python
import socket
import sys
def send(command: str) -> str:
with socket.create_connection(("127.0.0.1", 5555)) as sock:
sock.sendall(command.encode() + b"\n")
response = sock.makefile("rb").readline()
return response.decode().rstrip("\n")
if __name__ == "__main__":
print(send(" ".join(sys.argv[1:])))
```
Twelve lines, and note what they contain: connect, send a line, read a line back. Any language with sockets can implement this in the same twelve lines - Node, Go, Rust, a shell script with netcat. That's what "wire protocol" buys: your Python engine is now usable from software that has never heard of Python.
## Run it
Terminal 1 - the server:
```console
$ python server.py
kv server listening on 127.0.0.1:5555
```
Terminal 2 - the conversation:
```console
$ python client.py SET name Ada Lovelace
OK
$ python client.py GET name
VALUE Ada Lovelace
$ python client.py DEL name
DELETED
$ python client.py GET name
NOT_FOUND
$ python client.py SET counter 42
OK
```
Now the moment the whole guide has been building toward. In terminal 1, kill the server with **Ctrl+C**. Start it again. Then:
```console
$ python client.py GET counter
VALUE 42
```
*What just happened:* The server process died and took every in-memory structure with it - the index, the offsets, all of it. On restart, `KV("data.log")` replayed the log and rebuilt the world, and a client on the other side of a socket can't even tell it happened. Log, replay, index, recovery - every phase of this project fired in that one unremarkable `VALUE 42`. Unremarkable is the achievement.
## Recap
1. A database becomes a *server* when strangers can reach it through a socket and a protocol - the engine didn't change, its audience did.
2. Line-based text protocols are debuggable by eye and fine for v1; their framing bans newlines in values. The grown-up fix is length-prefixing - exactly what your on-disk record format already does, and what Redis's RESP protocol (`$5\r\nhello`) does on the wire.
3. One thread per client means concurrent access to shared state; the global lock serializes commands so log appends and index updates can't interleave into corruption.
4. One writer *process* per log file - a lock inside one process can't referee two processes.
```quiz
[
{
"q": "Two client threads call store.set() at the same instant with no lock. What's the realistic worst case?",
"choices": [
"One request is refused with an error by the OS",
"Both writes compute offsets from the same _offset value, corrupting the index so reads return spliced bytes from two different records",
"Nothing - Python's GIL makes the whole set() call atomic"
],
"answer": 1,
"explain": "The GIL makes single bytecode operations atomic, not multi-step methods - threads can interleave between the append and the bookkeeping. Both threads reading the same _offset leaves index entries pointing at wrong bytes."
},
{
"q": "Why can't a value contain a newline in this wire protocol, and what's the standard fix?",
"choices": [
"TCP can't transmit newline bytes; the fix is base64-encoding everything",
"The protocol frames messages by newline, so a newline inside a value would end the message early; the fix is length-prefixed framing, as in RESP or our own on-disk record format",
"Python's readline() strips newlines; the fix is using read() instead"
],
"answer": 1,
"explain": "Delimiter-based framing always bans the delimiter from the payload. Length prefixes ('the next 5 bytes are the value') let payloads contain anything - the same reasoning that shaped the record format in phase 2."
},
{
"q": "You restart the server process. Why do clients still see all their data?",
"choices": [
"The OS preserves the process's memory across restarts",
"The clients cache their own writes locally",
"KV's constructor replays the log on startup, rebuilding the index - the socket layer sits on top of the same crash-recovery machinery from phase 3"
],
"answer": 2,
"explain": "Nothing about the server is special: it constructs a KV, which replays data.log and rebuilds the index. Restarting a database is a controlled crash, and recovery is the same code path."
}
]
```
---
# Benchmarks, and What Redis Does Differently
You built a database. The final phase does what a good engineer does after building anything: measures it clearly, then walks the neighborhood to see how the professionals handled the same trade-offs. There's no better position to understand Redis or LevelDB from - you've personally hit every problem their designs answer.
## One knob first: make fsync optional
Phase 2 committed to `fsync` on every write - full durability, full price. To measure what that price *is*, the store needs a way to decline. Three small edits to `kv.py`:
```python
def __init__(self, path, fsync=True):
self.path = path
self._fsync = fsync
self._index = {} # key -> (value_offset, value_len)
self._replay()
self._log = open(path, "ab")
self._reader = open(path, "rb")
```
And in both `set` and `delete`, guard the sync:
```python
self._log.flush()
if self._fsync:
os.fsync(self._log.fileno())
```
With `fsync=False`, writes still reach the OS page cache (safe from *process* crashes, thanks to `flush`) but the disk write happens whenever the OS gets around to it - a power cut in that window loses recent writes. That's not a bug you're adding; it's a *durability policy* you're making explicit. Hold that thought for the Redis section.
## Measure it
Create `bench.py`:
```python
import os
import time
from kv import KV
N = 2000
def bench(label, fn):
start = time.perf_counter()
fn()
took = time.perf_counter() - start
print(f"{label:<26} {N / took:>12,.0f} ops/sec")
for fsync in (True, False):
if os.path.exists("bench.log"):
os.remove("bench.log")
db = KV("bench.log", fsync=fsync)
keys = [f"key:{i}".encode() for i in range(N)]
mode = "fsync every write" if fsync else "no fsync"
bench(f"set ({mode})", lambda: [db.set(k, b"x" * 100) for k in keys])
bench(f"get ({mode})", lambda: [db.get(k) for k in keys])
db.close()
os.remove("bench.log")
```
Here's one run on my machine - a Windows desktop with an SSD. **Your absolute numbers will differ; the *ratios* are the lesson:**
```console
$ python bench.py
set (fsync every write) 238 ops/sec
get (fsync every write) 3,442,341 ops/sec
set (no fsync) 161,993 ops/sec
get (no fsync) 4,327,131 ops/sec
```
*What just happened:* Three facts worth staring at.
- **The fsync cliff.** Same code, same data - roughly *seven hundred times* fewer writes per second when every one waits for the disk to confirm. A buffered write is a memory copy measured in microseconds; an fsync is a round trip to a physical device measured in milliseconds. Nothing in the software stack is more expensive than genuine durability, which is why every database makes it configurable and why "how often do you fsync?" is arguably *the* defining question of storage engine design.
- **Reads are absurdly fast.** Millions per second - because a `get` is a dict lookup plus a small file read that the OS serves from the page cache in RAM. Your index did its job: read cost is independent of database size.
- **Even the "slow" fully-durable mode is fine for many systems.** A couple hundred fully-durable writes per second is a real workload's worth. Know your requirements before buying complexity.
If you want a third data point, benchmark through `client.py` - you'll find TCP round trips and Python's per-request overhead flatten the fsync gap considerably, a useful reminder that the bottleneck is wherever you *haven't* measured yet.
## What Redis does differently
Redis's answer to the fsync cliff: don't put disk on the write path at all. Data lives in RAM - reads and writes touch memory only, which is where the legendary speed comes from. Persistence runs *beside* the data path, in two forms that you have already built both halves of:
- **The AOF (append-only file)** is your phase 2 log - every write command appended. And `appendfsync`, Redis's most famous config knob, is your `fsync` parameter with three positions: `always` (your `fsync=True` - durable, slow), `everysec` (fsync once per second - lose at most about a second of writes on power failure), and `no` (your `fsync=False` - the OS decides). Production overwhelmingly runs `everysec`: the middle of the dial you measured. When the AOF grows bloated, *AOF rewrite* regenerates it from live data - your phase 4 compaction.
- **RDB snapshots** are phase 1's write-everything-out idea, done right: forked into a child process so serving never pauses, written to a temp file, atomically renamed into place. Your `os.replace` trick, at production scale.
And commands execute one at a time on a single thread - the serial guarantee your phase 5 lock provides, achieved with an event loop instead of threads. You didn't build a toy that resembles Redis; you built the same architecture with fewer zeros on the throughput.
## What LevelDB does differently
Your engine has two real limits, both inherited from the hash index: every key must fit in RAM, and there are no range queries - "give me `user:100` through `user:200`" means checking each key, because a hash map has no order.
LevelDB (and its descendant RocksDB) restructures everything around *sorted order* to fix both. The design is the **LSM tree** - log-structured merge tree:
1. Writes go to a WAL (your log - the crash-safety layer never changes) and into an in-memory sorted structure called the **memtable**.
2. When the memtable fills, it's written out as an **SSTable** - an immutable, *sorted* file. Append-style writing, never modified after creation: still your discipline.
3. Reads check the memtable, then recent SSTables, oldest last. Because each file is sorted, a sparse index (one entry per few kilobytes, not per key) suffices - keys no longer need to all fit in RAM.
4. Background **compaction** continuously merges overlapping SSTables into fewer, larger sorted ones, discarding dead versions - your phase 4, made incremental and perpetual instead of stop-the-world.
Sorted files make range queries a seek-and-scan, and the sparse index frees RAM. The price: a read may probe several files (slower than your one-hop hash lookup), and background compaction consumes real I/O - the write traffic it generates even has a name, *write amplification*. Wins are purchased, never free.
## The clear-eyed scorecard
| | **Yours (Bitcask-style)** | **Redis** | **LevelDB/RocksDB** | **SQLite/PostgreSQL** |
|---|---|---|---|---|
| Data lives | Disk (log) + RAM index | RAM (disk is backup) | Disk (LSM tree) | Disk (B-tree pages) |
| Index | Hash: key → offset | Hash, in RAM | Sparse, per sorted file | B-tree |
| Range queries | No | Limited (`SCAN`) | Yes - files are sorted | Yes |
| All keys in RAM? | Required | Everything in RAM | No | No |
| Crash recovery | Replay log | Replay AOF / load RDB | Replay WAL | Replay WAL |
| Compaction story | Manual, stop-the-world | AOF rewrite (forked) | Continuous, background | VACUUM / autovacuum |
| Concurrency | One global lock | Single-threaded loop | Multi-threaded | MVCC, many readers+writers |
Read the recovery row twice: **every column replays a log.** Four radically different engines, one shared spine - the thing you built in phases 2 and 3 is the part nobody gets to skip. (The B-tree column is the [indexes](/guides/why-is-my-query-slow) and [WAL](/guides/database-backups-and-restores) story from the databases guides - same log, different index structure on top.)
## Where to take it
Each of these is a genuine weekend extension, in rough order of payoff:
| Want | What it takes |
|---|---|
| **Faster startup** | Replay is O(log size). Bitcask writes "hint files" - a compact dump of the index - at compaction time, so startup reads the small index file instead of the whole log. |
| **`everysec` durability** | A background thread that fsyncs once per second while writes only `flush()`. You'll have rebuilt Redis's default. |
| **Segmented logs** | Roll to a new log file every N MB and merge old segments in the background - compaction without pausing. Remember the tombstone rule from phase 4. |
| **Range queries** | Keep a sorted list of keys (`bisect`) beside the hash index, or go full memtable/SSTable. This is the door LSM trees live behind. |
| **Replication** | Ship the log to a second machine that replays it - your replay code *is* a replica's apply loop. [Scaling a Database](/guides/scaling-a-database) covers what leader-follower setups do about lag; you now know what they ship. |
| **Real protocol** | Implement RESP framing and point `redis-cli` at your server. There's no feeling quite like an off-the-shelf client accepting your homemade database. |
For the theory behind all of it, the Bitcask paper ([riak.com/assets/bitcask-intro.pdf](https://riak.com/assets/bitcask-intro.pdf)) is a short, readable description of exactly what you built - you'll recognize every diagram.
## What you built
From an empty folder, with nothing but the standard library: a persistent key-value store with a checksummed binary log format, durable writes with an explicit fsync policy, crash recovery that amputates torn writes and replays history, an in-memory index that keeps reads constant-time, live compaction with an atomic swap, and a TCP server with a wire protocol and a client.
More than the code, you own the ideas now. When PostgreSQL's docs mention the WAL, when Redis asks you to choose an `appendfsync` policy, when RocksDB's write amplification comes up in a design review - none of it is magic anymore. It's a log, an index, and a compactor. You've written all three.
```quiz
[
{
"q": "Redis's appendfsync everysec policy means what, concretely?",
"choices": [
"Every write blocks until the disk confirms it",
"Writes go to the AOF continuously but fsync runs once per second - a power failure can lose at most about the last second of writes",
"The database snapshots all of RAM to disk every second"
],
"answer": 1,
"explain": "It's the middle of the durability dial: writes hit the OS page cache immediately, and one fsync per second bounds the loss window. The benchmark's fsync cliff is exactly why this compromise is the production default."
},
{
"q": "What can LevelDB's LSM design do that our hash-indexed engine fundamentally cannot?",
"choices": [
"Survive a crash mid-write",
"Serve range queries efficiently and handle keysets too large for RAM, because its files are sorted and need only a sparse index",
"Append records to a log without rewriting old data"
],
"answer": 1,
"explain": "Crash safety and append-only logging we already have. Sorting is the genuinely new capability: ordered files make 'every key from A to B' a seek-and-scan and let a sparse index replace one-entry-per-key."
},
{
"q": "Why did enabling fsync on every write cost roughly three orders of magnitude in the set benchmark?",
"choices": [
"fsync recomputes the CRC32 of the whole log file",
"Python's fsync wrapper holds the GIL",
"A buffered write is a memory copy into the page cache; fsync is a blocking round trip to a physical storage device - you're comparing RAM speed to hardware speed"
],
"answer": 2,
"explain": "The gap is physics, not software: microseconds for a memory copy versus the milliseconds a device takes to confirm persistence. Every storage engine's design revolves around when to pay this exact cost."
}
]
```