Let's Build a Key-Value Database

Databases have a reputation. They are the part of the stack people treat as furniture: you install one, you point your app at it, and you do not open the lid. Somewhere inside there is a B-tree, and B-trees are hard, and so the whole thing gets filed under "not for me".

That reputation is mostly undeserved. A database is four ideas stacked on top of each other, and each one is small enough to hold in your head. You can build a real one, with genuine crash recovery, in about two hundred lines.

So let's do that. Ours is called Nibble, named after half a byte, because it is small and because naming things is the fun part. It stores data, it survives being killed mid-write, it detects corrupted records, and it reclaims dead space. It is not a toy: it is a key-value store built the same way Riak's storage engine was, and that shipped in production for years.

By the end we will also have measured something that surprised me and might surprise you: what durability actually costs, and the fact that both Nibble and SQLite quietly decline to pay full price for it by default.

What a database actually is

Strip away the marketing and a database does four things.

It stores bytes somewhere they will outlive the process. That means a file. Every database you have used is files on a disk. Postgres is a directory of them. SQLite is one. There is no third thing.

It finds those bytes again without reading everything. This is what an index is. Without one, "find the user with id 4821" means reading the entire file. An index is any structure that turns that scan into a jump.

It does not lose your data when things go wrong. Processes get killed. Machines lose power. Disks write things out of order. A database is a set of promises about what survives, and the machinery to keep those promises.

It lets more than one thing ask at once, without those things tripping over each other. This is transactions and concurrency control, and it is the genuinely hard part.

That is the whole list. Everything else, SQL, replication, query planners, connection pooling, is built on top of those four. We are going to build the first three properly and be honest about skipping the fourth.

How they are built

Real databases layer up roughly like this, from the disk upward.

The storage engine owns the file. It decides how bytes are laid out, what a record looks like, and when things hit the disk. This is where B-trees and LSM trees live. In Postgres this is the heap and its access methods; in MySQL it is InnoDB; in SQLite it is the pager and the B-tree layer.

Above that sits the index, mapping keys to locations. Sometimes it is a separate structure, sometimes the storage layout is the index, which is what "clustered index" means.

The durability layer decides what happens when the power goes out. Almost always this is a write-ahead log: before changing anything, write down what you are about to do. If you die halfway, the log tells you what to finish or undo on restart.

The query layer turns a request into disk operations. A parser, a planner, an executor. This is the part people mean when they say "database", and it is the part sitting furthest from the data.

Then transactions and concurrency wrap the whole thing so that many callers each get a coherent view.

Nibble is going to be a storage engine with an index and a durability story, plus a REPL so it feels like a database rather than a library. We will skip the query planner and the transactions, and I will tell you exactly what that costs.

Start with the dumbest thing that could work

Before designing anything, write the version you would write if you had not thought about it. A dict, dumped to JSON, saved on every write:

class NaiveDB:
    def __init__(self, path):
        self.path = path
        self.data = json.load(open(path)) if os.path.exists(path) else {}

    def put(self, k, v):
        self.data[k] = v
        with open(self.path, "w") as f:
            json.dump(self.data, f)
            f.flush(); os.fsync(f.fileno())

    def get(self, k):
        return self.data.get(k)

Eleven lines. It persists, it survives restarts, and for a config file it is genuinely the correct answer. Ship it.

It also has two problems, and they are the two problems that produce every design decision in every database ever written.

Problem one: it gets slower as it grows. Writing one key rewrites every key. So the cost of a write is the size of your data:

   100 keys:  10,822 writes/sec  (  2.5 KB)
 1,000 keys:   3,928 writes/sec  ( 27.1 KB)
 5,000 keys:   1,043 writes/sec  ( 144.3 KB)
10,000 keys:     547 writes/sec  ( 290.8 KB)

A hundred times more data, twenty times slower per write. That curve does not flatten out; it keeps going. At a million keys you are rewriting megabytes to change one value.

Compare that with where we are going. Nibble, same workload, same machine:

   100 keys:  38,804 writes/sec
 1,000 keys:  34,289 writes/sec
 5,000 keys:  37,799 writes/sec
10,000 keys:  37,704 writes/sec

Flat. A hundred times more data, same speed. That is the difference between a write costing O(n) and costing O(1), and it is worth more than any micro-optimisation you will ever make.

Problem two is worse. Watch what happens when the process dies mid-save. open(path, "w") truncates the file to zero before json.dump writes anything, so there is a window where the file on disk is incomplete:

before crash: {"a": "1", "b": "2"}
after crash:  {"a": "1", "b

And on restart:

JSONDecodeError: Unterminated string starting at: line 1 column 12 (char 11)

Not "the last write was lost". Every key is gone. Both of them, including the one written minutes ago that had nothing to do with the crash. The file will not parse, so there is no data, so the database is dead.

That is the real lesson, and it is why databases are built the way they are. The naive version puts all your data at risk on every single write. A database's core promise is that the blast radius of a failure is small and bounded. Everything that follows is in service of that.

The design: an append-only log

Here is the trick that makes Nibble small.

Most people, asked to design a database, reach for something that updates data in place: find the record, overwrite it. That is where the difficulty lives. Overwriting means the record might be a different size than before. It means a crash halfway through leaves a record that is half old and half new. It means free space management.

So don't. Only ever append.

To set a key, write a new record at the end of the file. To update it, write another record at the end. To delete it, write a record that says "this key is gone". The newest record for a key wins. The file only grows, and we clean it up later.

This sounds wasteful and it is. It is also fast, because appending is the one thing spinning disks and SSDs both love, and it makes crash recovery almost trivial: a crash can only ever damage the last record, because that is the only one being written.

This design is called a log-structured hash table. Riak's storage engine, Bitcask, is exactly this. So it is a real thing, not a teaching aid.

The record format

Every record looks the same:

[crc32: 4 bytes][key_len: 4 bytes][val_len: 4 bytes][key bytes][value bytes]

Three fixed-size numbers, then the data. The CRC is a checksum over the key and value so we can tell whether a record is intact. A val_len of -1 means "this is a tombstone", our way of writing down a deletion.

In Python:

import os, struct, zlib

HEADER = struct.Struct("<IIi")   # crc32, key_len, val_len
TOMBSTONE = -1

<IIi is two unsigned 32-bit ints and one signed one, little-endian. The signed one is val_len, so it can hold -1.

Writing

Appending a record is the core of the whole thing:

def _append(self, key, value):
    kb = key.encode()
    vb = b"" if value is None else value.encode()
    vlen = TOMBSTONE if value is None else len(vb)
    body = kb + vb
    crc = zlib.crc32(body) & 0xFFFFFFFF
    record = HEADER.pack(crc, len(kb), vlen) + body

    self.file.seek(0, os.SEEK_END)
    offset = self.file.tell()
    self.file.write(record)
    self.file.flush()
    os.fsync(self.file.fileno())
    return offset

Seek to the end, write, flush, fsync, return where it landed. That returned offset is the important part: it is where the record lives, and it is what the index will remember.

put and delete are both this function wearing different hats:

def put(self, key, value):
    offset = self._append(key, value)
    self.index[key] = offset

def delete(self, key):
    if key not in self.index:
        return False
    self._append(key, None)
    del self.index[key]
    return True

A delete is a write. That is worth sitting with for a second, because it is unintuitive and it is how most real databases work too. Postgres does not erase a row when you delete it; it marks it dead and lets VACUUM deal with the corpse later. Nibble writes a tombstone and lets compact deal with it later. Same idea.

Reading, and the index

The index is a Python dict from key to file offset. That is it. That is the whole index.

def get(self, key):
    offset = self.index.get(key)
    if offset is None:
        return None
    self.file.seek(offset)
    head = self.file.read(HEADER.size)
    crc, klen, vlen = HEADER.unpack(head)
    body = self.file.read(klen + (0 if vlen == TOMBSTONE else vlen))
    if zlib.crc32(body) & 0xFFFFFFFF != crc:
        raise IOError(f"corrupt record for key {key!r} at offset {offset}")
    if vlen == TOMBSTONE:
        return None
    return body[klen:].decode()

One dict lookup, one seek, one read. Every read is exactly one disk seek regardless of how big the database is, which is a genuinely nice property and the main thing this design buys you.

The catch is sitting in plain sight: the index lives in memory. Every key you have ever stored must fit in RAM. Values can be enormous and live on disk, but the keys cannot. That is Bitcask's real constraint too, and it is the honest answer to "why doesn't everything work this way".

Recovery: rebuilding the index from the log

The index is in memory, so it dies with the process. On startup we have to rebuild it, which we do by reading the log start to finish and letting later records overwrite earlier ones:

def _load(self):
    self.file.seek(0, os.SEEK_END)
    size = self.file.tell()
    offset = 0
    while offset < size:
        self.file.seek(offset)
        head = self.file.read(HEADER.size)
        if len(head) < HEADER.size:
            self._truncate(offset, "short header")
            break
        crc, klen, vlen = HEADER.unpack(head)
        body_len = klen + (0 if vlen == TOMBSTONE else vlen)
        body = self.file.read(body_len)
        if len(body) < body_len:
            self._truncate(offset, "short body")
            break
        if zlib.crc32(body) & 0xFFFFFFFF != crc:
            self._truncate(offset, "bad checksum")
            break
        key = body[:klen].decode()
        if vlen == TOMBSTONE:
            self.index.pop(key, None)
        else:
            self.index[key] = offset
        offset += HEADER.size + body_len

Read a record. If it is a tombstone, forget the key. Otherwise remember where it is. Move on.

The three breaks are the crash recovery, and they are the reason append-only was worth it. If we hit a record with a short header, a short body, or a bad checksum, we have found the write that was in flight when the process died. Everything before it is intact. Everything from that point is garbage. So we truncate the file there and carry on:

def _truncate(self, offset, reason):
    self.file.truncate(offset)
    self.file.flush()
    os.fsync(self.file.fileno())
    print(f"nibble: discarded partial record at {offset} ({reason})")

That is the entire crash recovery mechanism. No log replay, no undo, no redo. Cut off the damaged tail and keep the rest.

Does it actually survive a crash?

Claims are cheap. Let's kill it.

We write two keys, close cleanly, then simulate a process dying mid-write by appending eight bytes of a record that never got finished:

db = Nibble("crash.db"); db.put("a","1"); db.put("b","2"); db.close()
with open("crash.db","ab") as f:
    f.write(b"\x99\x88\x77\x66\x05\x00\x00\x00")   # a torn write
db = Nibble("crash.db")

file was 28b, now 36b (torn write appended)
nibble: discarded partial record at 28 (short header)
recovered keys -> ['a', 'b']
a -> 1  b -> 2
file truncated back to 28b
still writable -> 3

It noticed the damage, threw away the partial record, recovered both keys, trimmed the file back to 28 bytes, and accepted new writes. That is a real database property, in fifteen lines.

Now corruption rather than truncation. Write two keys, then scribble a byte into the middle of the first record:

db = Nibble("corrupt.db"); db.put("k","hello world"); db.put("k2","second"); db.close()
with open("corrupt.db","r+b") as f:
    f.seek(20); f.write(b"X")
db = Nibble("corrupt.db")

nibble: discarded partial record at 0 (bad checksum)
keys after reopen -> []

The checksum caught it. But look at that result properly, because this is a design flaw and I am not going to pretend otherwise: one flipped byte in the first record threw away the entire database. Both keys are gone, including the perfectly healthy second one.

The recovery logic assumes damage only ever happens at the tail, which is true for a crash and false for bit rot. A real implementation would skip the bad record and keep reading, or keep the log in many smaller files so the blast radius is one segment. Nibble stops at the first problem. It is the right assumption for the failure it was designed for and the wrong one for the failure it just met.

Compaction: the price of only ever appending

The file only grows. Update the same key a thousand times and you have a thousand records, of which one matters.

db = Nibble("compact.db")
for i in range(1000):
    db.put("counter", str(i))

1000 writes to ONE key -> 21890 bytes on disk, 1 live key

Twenty-two kilobytes to store the number 999. Compaction fixes this by writing the live data to a fresh file and swapping it in:

def compact(self):
    live = {k: self.get(k) for k in self.index}
    tmp = self.path + ".compact"
    with open(tmp, "wb") as out:
        new_index = {}
        for key, value in live.items():
            kb, vb = key.encode(), value.encode()
            body = kb + vb
            crc = zlib.crc32(body) & 0xFFFFFFFF
            new_index[key] = out.tell()
            out.write(HEADER.pack(crc, len(kb), len(vb)) + body)
        out.flush()
        os.fsync(out.fileno())
    self.file.close()
    os.replace(tmp, self.path)
    self.file = open(self.path, "r+b")
    self.index = new_index

after compact() -> 22 bytes, value still '999'

21,890 bytes down to 22. Everything the index does not point at was dead, and now it is gone.

The os.replace is the interesting line. It is an atomic rename: the file is either the old one or the new one, never a mixture, even if we die during the swap. Build the replacement off to the side, then flip it into place in one indivisible step. This is how a lot of software updates files safely, and it is worth knowing outside of databases.

Postgres calls this VACUUM. LSM-tree databases call it compaction and spend enormous effort on when to run it. Nibble makes you call it yourself, which is the honest version of "we have not solved this".

DB Pro

Work With Your Databases Like A Pro

Query, explore, and manage your databases with a beautiful desktop app and built-in AI.

Download Now

What durability actually costs

Here is the part I did not expect to write.

Nibble calls os.fsync() after every write. That is supposed to mean the data is on the disk. So let's measure the cost. Twenty thousand writes, each one fsynced:

Nibble writes (fsync per write)     39,674 ops/sec
Nibble random reads                496,444 ops/sec

Then SQLite, same workload, committing on every write:

SQLite writes (commit per write)      3,293 ops/sec
SQLite random reads                 170,891 ops/sec

Nibble is twelve times faster than SQLite at durable writes. Which should make you suspicious rather than pleased, because SQLite is written by people who do this for a living and Nibble was written this afternoon.

The number is a lie, and the lie is fsync. Here is Apple's own man page for fsync(2):

Note that while fsync() will flush all data from the host to the drive (i.e. the "permanent storage device"), the drive itself may not physically write the data to the platters for quite some time and it may be written in an out-of-order sequence.

Specifically, if the drive loses power or the OS crashes, the application may find that only some or none of their data was written.

On macOS, fsync hands your data to the drive and the drive says "sure, later". If you want a real guarantee you need F_FULLFSYNC, which tells the drive to actually flush its cache. So let's measure all three levels honestly, on the same machine, two thousand appends each:

flush() only (no fsync at all)     489,926 ops/sec
os.fsync()   <- what Nibble does    40,967 ops/sec
F_FULLFSYNC  <- real durability        256 ops/sec

Two hundred and fifty-six. Real durability is 160 times slower than the fsync we were so pleased with, and nearly two thousand times slower than not bothering.

That number is the reason databases are hard. Everything else in this post is bookkeeping. This is physics, and every database you have used has had to decide how much of it to pay for.

So what does SQLite do? I assumed it used F_FULLFSYNC and that this explained its slower numbers. I was wrong:

PRAGMA fullfsync=1     75 ops/sec
PRAGMA fullfsync=0  3,088 ops/sec

And the default:

PRAGMA fullfsync -> 0

SQLite defaults to off. On macOS, out of the box, SQLite makes the same trade Nibble does: it calls fsync, the drive says "later", and everybody agrees not to think too hard about it. SQLite's 3,293 writes per second was never the cost of true durability. It is the cost of SQLite's journaling, on top of the same soft fsync.

If you want the real thing, it is 75 writes per second, and now you understand why nobody turns it on.

None of this means SQLite is careless or that Nibble is its equal. SQLite is doing vastly more work per write: journaling, page management, a B-tree, transactions. The point is narrower and more useful: the fsync in your code is probably not doing what you think, the gap is 160x, and the fastest way to look good in a benchmark is to quietly promise less. When you see a database benchmark, the first question is what it promised, not what it scored.

A REPL, so it feels real

A library is not a database until you can poke at it. Sixty lines of input() loop:

while True:
    line = input("nibble> ").strip()
    cmd, _, rest = line.partition(" ")

    if cmd == "set":
        key, _, value = rest.partition(" ")
        db.put(key, value); print("OK")
    elif cmd == "get":
        value = db.get(rest)
        print("(nil)" if value is None else value)
    elif cmd == "del":
        print("OK" if db.delete(rest) else "(nil)")
    elif cmd == "keys":
        print("\n".join(db.keys()) or "(empty)")
    elif cmd == "compact":
        before = db.size(); db.compact()
        print(f"{before} -> {db.size()} bytes")

And now it is a database you can talk to:

$ python3 cli.py music.db
nibble music.db (0 keys, 0 bytes)

nibble> set artist:1 Aphex Twin
OK
nibble> set artist:2 Boards of Canada
OK
nibble> get artist:1
Aphex Twin
nibble> set artist:1 Richard D. James
nibble> get artist:1
Richard D. James
nibble> del artist:2
OK
nibble> get artist:2
(nil)
nibble> stats
1 keys, 122 bytes
nibble> compact
122 -> 36 bytes

Quit, reopen, and it is all still there, because the index rebuilt itself from the log.

The whole thing is 193 lines: 128 for the database, 65 for the REPL.

What we skipped, and what it would cost

Nibble is a real storage engine with a real durability story. It is also missing most of a database, and the missing parts are where the difficulty actually lives.

Transactions. There is no way to say "these two writes happen together or not at all". Adding them means every record carrying a transaction id, plus a commit record, plus recovery logic that ignores writes belonging to transactions that never committed. That is genuinely the smallest version, and it is more code than the rest of Nibble combined.

Concurrency. One process, one thread. Two writers would interleave their appends and produce garbage. The usual answers are a single writer thread, or a lock, or MVCC where readers see a snapshot and never block. MVCC is what Postgres does, and it is why Postgres has VACUUM.

Range queries. A hash index can answer "what is key X" and nothing else. "All keys between X and Y" means reading everything. This is the reason B-trees exist and the reason most databases use one: a B-tree keeps keys in order, so a range is a walk instead of a scan. If you want ORDER BY, you want a tree.

Keys must fit in RAM. The dict is the whole index. Bitcask has this constraint too. Escaping it means putting the index on disk, and now you are writing a B-tree.

SQL. No parser, no planner, no optimizer. get and set are the API. This is the layer everyone thinks of as "the database" and it is the only one you could bolt on without redesigning anything underneath.

That list is not an apology. It is a map. Every item on it is a real problem with a known solution, and each one is roughly the size of what we just built. A database is not one big hard thing. It is a stack of small hard things, and we did four of them.

Bottom line

A database is a file, an index, a promise about crashes, and a way to let people share it. We built the first three in 193 lines and measured the fourth well enough to respect it.

The thing worth taking away is not the code. It is that os.fsync returns instantly and means less than you think, that the honest number on this machine was 256 writes per second, and that the difference between those two facts is where all the engineering went. Every database you have used is somewhere on that spectrum, and most of them are further toward "trust the drive" than their documentation implies.

Nibble is 193 lines and it survives being killed mid-write. That is not because I am clever. It is because append-only makes crash recovery into a truncate, and picking a design where the hard problem cannot happen is most of what good engineering is.

Go and open the lid on something. It is more approachable in there than you would think.

Jay