Why not a JSON file?

A database is a program whose whole job is to keep your data safe on disk and hand it back fast, even when the machine crashes or ten programs are writing at once. Most of us start without one: a Python dict, saved to a JSON file, works fine until the day it quietly doesn’t.

That day comes sooner than you’d think. A cache for a crawler, the results of an eval run, the labels behind your ranker’s training data: all of them start life as “just a file”, and all of them eventually slow to a crawl, lose records, or come back half-written. Knowing exactly why, and what a real database does about each failure, is also the difference between “I’d just use a real database” and an answer that survives a follow-up question in an interview.

This builds on What happens when you save a file?, which showed how bytes travel from your program to the disk and how a save can be made crash-safe. Here you’ll build a tiny database of your own on top of those tricks. It sets up the next three lessons: indexes for finding things fast, transactions for many writers at once, and normalization for deciding how to shape the data.

Today

• Name the four ways a JSON file fails as a database, and make each one happen on your Mac: saves that get slower as the data grows, a crash that wrecks the file mid-save, two programs erasing each other’s work, and having to read everything to find one record.
• Build the simplest real database core: a file you only ever add to the end of, plus a dict in memory that remembers where each record lives. Riak, a real database, shipped exactly this design under the name Bitcask.
• Make it survive the process being killed mid-write and a half-written record at the end of the file, by re-reading the file on startup and giving every record a small fingerprint that proves it’s whole. Then add a cleanup step so the file doesn’t grow forever.
• Explain the one idea under almost every database, “write down what you’re about to do before you do it”, and sketch the two big ways real databases organize data on disk, one picture each.
• Say what a database does beyond storing bytes (keeping many writers from colliding, letting you ask questions in a query language, promising what survives a crash), and when SQLite, a database that lives in a single file, is the right answer and when you want Postgres, a database that runs as a separate server.

You should have done What happens when you save a file? first, because this lesson leans on its ideas about the operating system’s write buffer, forcing data to disk, and crash-safe saves. Plan on one evening to read and one to build.

The Problem

You’re writing a crawler cache for work. Before fetching a URL, the crawler checks whether it fetched it recently; after fetching, it records the status code, a content hash and a timestamp. You need it by Friday, so it’s a dict, and the dict lives in cache.json:

cache = json.load(open("cache.json"))
cache[url] = {"status": 200, "sha": h, "ts": time.time()}
json.dump(cache, open("cache.json", "w"))

It works. Then it gets used.

At 5,000 URLs nobody notices anything. At 200,000 URLs the file is 30 MB and every single update rewrites all 30 MB, so the crawler spends more time saving its cache than fetching pages. Someone runs it with 8 worker processes to go faster, and entries start silently disappearing: two workers each loaded the file, each added one URL, and whoever saved second erased the other’s work. Then a worker gets OOM-killed while saving and the next run dies on json.decoder.JSONDecodeError: Unterminated string, because open(..., "w") truncated the file and only half of the new one got written. And when someone asks “how many URLs returned 429 yesterday?”, the only way to answer is to load all 30 MB and loop.

None of this is a bug in your code exactly. It’s four separate problems that every program storing data eventually hits:

1. Cost grows with size. Changing one record costs as much as writing all of them.
2. Crashes. A save that dies halfway can destroy the old data and the new data together.
3. Concurrency. Two writers who each read, modify and write the whole file lose updates.
4. Finding things. No structure on disk means every question is a full scan.

A database is the accumulated set of answers to those four problems. This lesson builds a small one from scratch so that when you reach for SQLite or Postgres, you know what you’re buying.

The Idea

Failure one: every write rewrites everything

JSON is a serialization formatserialization formatA way of turning in-memory objects into a flat sequence of bytes (and back), so they can be saved to a file or sent over a network., not a storage format. It has no way to say “change the value at byte 4,812”. The bytes after any change shift, so the only safe way to update one key is to write the whole file again. That makes a single put cost O(N)O(N)Cost grows in proportion to N, the number of records. Twice the data, twice the time, for the same one-record change. instead of constant.

I measured it on an M4 Pro MacBook (Python 3.14): a dict of N keys with 100-byte values, saved with the safe temp-file-plus-rename recipe from the files lesson after every put.

Two details in those numbers. First, fsync made no visible difference at large N: the 12 MB rewrite (serializing, then copying into the page cache) dwarfs one Mac fsync. Second, it really is linear, which you can see coming from back-of-the-envelope math: Python’s json.dump writes on the order of a few hundred MB per second, and 12 MB at that rate is tens of milliseconds. At a million keys, extrapolate to around half a second per put. Your crawler would be doing two saves a second, and nothing else.

Failure two: a crash in the middle

You already know this one from the checkpoint lesson. open("cache.json", "w") truncatestruncatesCuts the file to zero bytes immediately, before anything new is written. the file, so a crash anywhere during the dump leaves you with neither the old cache nor the new one. Temp-file-plus-fsync-plus-rename fixes it, at the cost of making every save a full copy plus an fsync. You can make a JSON file crash-safe. You can’t make it crash-safe and cheap to update.

Failure three: two writers

Two crawler workers, A and B. Each one does the natural thing: read the whole file, add one key, write the whole file.

This is the same lost updatelost updateTwo writers each read a value, change their copy, and write it back. The second write overwrites the first, so one change vanishes without any error. as the counter += 1 race in the threads lesson, just with a file instead of an integer and processes instead of threads. The fix there was a lock. You could put a lock on the file (fcntl.flock), but now only one worker can do anything at a time, and each turn holding the lock costs a full rewrite. The workers queue up behind a 43 ms save.

Failure four: finding one record

To read one key from cache.json, you parse all of it. 100,000 keys took about 21 ms to json.load on my Mac; a dict lookup after that takes well under a microsecond. Fine if you load once and keep the dict in memory. But then you’re back to failure three the moment anyone else writes the file, because your in-memory copy is stale. And “every URL that returned 429 since yesterday” is a loop over everything, every time, because nothing on disk is organized by status or time.

What a storage engine is

Pull the four problems apart and a pattern shows. Problems one, two and four are about how bytes are laid out on disk: can you change one record without touching the others, can you tell a half-written record from a whole one, can you find a record without reading everything. Problem three, and the question-asking part of four, live a layer above.

The bottom layer has a name. A storage enginestorage engineThe part of a database that stores and retrieves records on disk. Its job is a handful of operations: put, get, delete, and usually “scan a range of keys in order”. It decides the on-disk layout. is the part of a database that answers exactly these calls:

put(key, value)
get(key) -> value or nothing
delete(key)
scan(from_key, to_key) -> records in key order     (some engines)

Everything a database does sits on top of this. A SQL table in SQLite is a storage-engine structure keyed by row ID; an index on a column is another one, keyed by that column. MySQL even lets you swap engines underneath the same SQL (InnoDB, MyISAM, others). So let’s build one.

The simplest engine: just append

The cheapest thing you can do to a file is add to the end of it. No bytes move, nothing old is rewritten, and sequential writes are what disks and the page cache are best at (the files lesson measured why). So: never update in place. To put a key, append a record key, value to the end of a file. To change it, append another record. The newest record for a key wins. That file is an append-only logappend-only logA file you only ever add to the end of, never modify in the middle. Each entry is a record of one change, in the order the changes happened..

Writes are now constant-time, whatever the size. Reads are terrible: to find the newest value of a key, you scan the whole log and keep the last match. Worse than JSON.

The fix for reads is to keep, in RAM, a dict from every key to where its newest record starts in the file: a byte offsetoffsetA position in a file, counted in bytes from the start. “Offset 4,812” means the 4,813th byte.. That dict is a hash indexhash indexAn in-memory hash table (a Python dict, basically) mapping each key to the location of its value on disk. One lookup, no scanning.. Now:

• put: append the record, then set index[key] = offset.
• get: offset = index[key], then read that one record from the file. One hash lookup and one small read.
• delete: you can’t erase from an append-only log, so append a special tombstonetombstoneA record that means “this key was deleted”. It’s needed because the old values are still in the log, and replaying them would bring the key back. record, and remove the key from the index.

The old records for a key are still in the file. Nothing points at them. They’re garbage, and we’ll deal with them shortly.

Play with it. Put a few keys, overwrite some, get one, delete one, compact. Then crash it and replay. Then turn on “tear the last write” and crash again.

Things to notice:

1. Every operation that changes something is an append. Put, delete, even the tombstone. The only time old bytes are touched is compaction, and compaction writes new files rather than editing old ones.
2. The index is a cache of the log. It holds nothing the log doesn’t. That’s why losing it in a crash costs time, not data: you can always rebuild it.
3. Garbage grows with overwrites, not with keys. Put a fifty times and the log holds fifty a records, one live.

Records that can prove they’re whole

What does “the log survives a crash” actually mean? Go back to the layers from the files lesson. When your process calls write(), the bytes go into the kernel’s page cache; write returns; much later the kernel writes them to the SSD.

• If your process dies (kill -9, OOM killer, a segfault), anything already handed to write() is safe in the page cache. The kernel finishes writing it. What’s lost is whatever was still in your own process: your Python-side buffer, and the in-memory index.
• If the machine dies (power cut, kernel panic), anything not yet fsynced may be lost, and it may be lost partially: the first 2 KB of a record made it to flash and the last 2 KB didn’t. That’s a torn writetorn writeA write that was only partly saved when a crash hit, leaving a record with its beginning on disk and its end missing or garbage..

So the log can end with a half-record, and recovery must be able to tell. Each record carries its own length and a checksumchecksumA small number computed from a block of bytes, such that changing any byte almost certainly changes the number. Store it with the data; recompute it on read; if they differ, the data is damaged., specifically a CRC32CRC32Cyclic redundancy check, 32 bits. A fast checksum built to catch accidental damage like flipped bits and truncation. Not cryptographic: it doesn’t stop someone deliberately forging data. Python has it as zlib.crc32. computed over everything after it.

Recovery is now a loop:

1. Read 12 bytes. If there aren’t 12, stop.
2. Unpack the CRC and the two lengths. If the file doesn’t have that many more bytes, stop.
3. Recompute the CRC over the lengths, key and value. If it doesn’t match, stop.
4. Otherwise apply the record to the index (set the offset, or delete the key for a tombstone) and go to 1.
5. Wherever you stopped, truncate the file to that point, so the next append starts on a clean boundary.

Stopping at the first bad record, rather than skipping it and carrying on, matters. Records were appended in order, so everything after a torn record was written after the crash point and can’t be trusted either. It also means a bug that silently corrupts a record in the middle of a big log would truncate everything after it. Real systems are more careful there (they distinguish “torn tail” from “corruption in the middle” and refuse to start on the latter), but the tail rule is the core.

Durability: when is a put really done?

The CRC tells you whether a record is whole. It doesn’t make the record survive a power cut. For that, you need fsync after the append, exactly as in the files lesson, and then you pay for it. On my Mac, a 100-byte put was 3.7 µs without fsync and 28 µs with plain fsync. (Remember the macOS caveat: plain fsync doesn’t flush the drive’s own cache; F_FULLFSYNC does, and costs milliseconds.) On a Linux box with a consumer SSD, an honest fsync is often hundreds of microseconds to a few milliseconds. Measure the Spark.

That gives you a dial with three positions, and every database has some version of it:

• No fsync. Fast. Survives your process crashing. Loses recent writes on power loss (the log is still consistent, thanks to the CRC; it’s just shorter).
• fsync every put. Every acknowledged put survives anything short of the disk dying. Throughput is capped at one fsync’s latency per put: at 3 ms, about 330 puts per second.
• fsync every N puts, or every few milliseconds, and only tell callers “done” after the fsync covering their put returns. This is group commitgroup commitBatching many writes into one fsync. Each writer waits a little longer, but the fsync cost is shared, so throughput goes way up while every acknowledged write is still durable., and it’s how real databases get both durability and throughput: one 3 ms fsync covering 500 puts is 6 µs per put.

Compaction

The log only grows. A crawler that rechecks the same 100,000 URLs every day appends 100,000 records a day while the number of live keys stays at 100,000. After a month, 97% of the log is garbage.

CompactionCompactionRewriting a log to keep only the newest record for each live key, dropping overwritten values and tombstones. Also called merging. fixes it. Walk the index, copy each live record to a new file, fsync it, atomically rename it over the old one, fsync the directory. That last part is the crash-safe save recipe from the files lesson, used here because compaction is exactly “replace a file with a new version”. A crash during compaction leaves the old log untouched and a partial temp file you delete on startup.

My test: 1,000 keys, each overwritten 100 times. 11.6 MB of log, 116 KB live. Compaction took 5.5 ms and the result was exactly 1% of the size.

Two refinements real engines add:

• Segments. Instead of one file, the log is a series of files. Only the newest one, the active segment, gets appended to; when it reaches a size limit it’s closed and a new one starts. Closed segments never change, so they can be compacted in the background while writes continue into the active one, and the index switches its pointers to the new files when the merge is done. That’s what the segments in Figure 003 are.
• Hint files. Recovery has to read the entire log. Bitcask’s merge also writes a small “hint” file next to each merged data file, containing just the keys and their offsets, no values. On startup it reads the hint files instead of the data, so recovery reads megabytes instead of gigabytes.

How bad is recovery without hints? Measured on my Mac, with the file freshly written (so in the page cache): 100,000 small records replayed in 48 ms; a 628 MB log of 156,000 records with 4 KB values in 156 ms. Cold from the SSD it would be bounded by read speed instead, roughly a few GB/s on a good NVMe drive, so a 50 GB log would take tens of seconds to start. That is the price of this design, and hint files are how you stop paying it.

What this design can’t do

Bitcask is genuinely good: one disk read per get, one sequential append per put, trivial crash recovery, and code you can fit in your head. It has two hard limits, and they’re the reason it’s not the only engine in the world.

Every key must fit in RAM. The index holds every key. In my Python version, 1 million keys cost about 180 MB of index (Python dicts, strings and tuples are not compact; Bitcask’s Erlang/C keydir is tighter, but still tens of bytes per key plus the key itself). A billion small keys is hundreds of GB of RAM. Values can be bigger than RAM; keys can’t.

No range queries. A hash table has no order. “All URLs starting with https://example.com/” or “every record between 9 am and 10 am” means walking every key. Failure four, half-solved: point lookups are fast, anything else is a scan.

Fixing those two is where the two big families of storage engine come from.

Write-ahead logging: the idea under everything

Before the two families, notice what you just built. The log is the truth; the index is a fast view of it you can always rebuild. Most databases keep their data in a fancier structure than a log (a tree, usually), but they keep the log too, for exactly this reason.

The rule is called write-ahead loggingwrite-ahead loggingBefore changing the main data structure on disk, append a description of the change to a log and make that log durable. After a crash, replay the log to redo changes that hadn’t reached the main structure yet. Abbreviated WAL.: before you modify the real data structure, append a record describing the change to a log, and fsync the log. Only then apply the change to the structure, which can happen lazily, in memory, and be written to disk whenever it’s convenient. If you crash, replay the log on startup to finish whatever didn’t make it.

Why bother, if you have to write the change twice? Because the two writes have very different shapes. The log append is small and sequential, and it’s the only thing you have to fsync before saying “committed”. The changes to the real structure are scattered random writes all over a big file, and they can be batched up and written later in big efficient chunks, or overwritten in memory five times before they’re written once. The WAL turns “durably update a complex structure” into “durably append some bytes”, which is the one thing disks are fast at.

You’ve seen this twice already. The ext4 journal in the files lesson is a WAL for filesystem metadata. And Bitcask is the degenerate case where the log is the data structure: there’s nothing to apply later.

Periodically the database does a checkpointcheckpointWriting all changes the log describes into the main data files, so the log up to that point is no longer needed for recovery and can be deleted or reused. Keeps recovery time bounded.: flush every changed page of the main structure to disk, note “everything before log position X is applied”, and throw away the log before X. That bounds recovery time, the same job compaction and hint files do for Bitcask.

Two engine shapes, in one picture each

Here are the two answers to “keys don’t fit in RAM, and I want ranges”. Both keep keys sorted, which gives you range scans for free. They differ in whether they update in place.

B-trees (Bayer and McCreight, early 1970s) store keys in sorted order in fixed-size pagepageThe fixed-size block a database reads and writes as a unit, commonly 4 KB to 16 KB. SQLite’s default is 4 KB, Postgres uses 8 KB. Matches how disks and the OS page cache move data.s, arranged as a wide, shallow tree. Each page holds hundreds of keys, so three or four levels are enough for billions of rows. A write finds the right leaf page and changes it in place, after first writing the change to a WAL. Reads are predictable: one page per level, and the top levels are almost always in cache. This is SQLite, Postgres, MySQL’s InnoDB, and most of the databases you’ll touch.

LSM-trees (log-structured merge trees, O’Neil and others, 1996) are the Bitcask idea grown up. Writes go to a WAL and to a sorted in-memory table, the memtablememtableAn in-memory sorted structure (often a skip list or balanced tree) that collects recent writes in an LSM engine. When it’s big enough, it’s written out to disk as one sorted file.. When the memtable fills up, it’s written out as an immutable, sorted file (an SSTableSSTableSorted String Table: an immutable file of key-value records sorted by key, with a small index of where each key range starts. Never modified after it’s written.), in one big sequential write. Background compaction merges those files, dropping overwritten values and tombstones, exactly like Bitcask’s merge except the output stays sorted. To avoid opening every file on a read, each file carries a Bloom filterBloom filterA compact bit array that answers “is this key possibly in this file?” with either “definitely not” or “maybe”. A few bits per key; lets a read skip most files without touching them.. Only a sparse sample of keys needs to be in RAM, since within a sorted file you can find a key from its neighbours. This is LevelDB, RocksDB, Cassandra, and the storage under many of the big distributed databases.

The trade-off in one line: B-trees do more work on writes so reads are cheap; LSM-trees do less work on writes and pay for it on reads and in background compaction. Indexes and B-trees builds the B-tree for real.

Everything else a database does

A storage engine gives you put and get that survive crashes. A database wraps three more jobs around it, and each one is a direct answer to one of the four failures.

Concurrency control (failure three). When many clients read and write at once, someone has to decide what each one sees and stop them from erasing each other’s work. The crudest answer is one big lock: one writer at a time. Better answers lock individual rows, or keep several versions of each row so readers never wait for writers (MVCCMVCCMulti-version concurrency control. A write creates a new version of a row instead of overwriting it, so each reader sees a consistent snapshot as of when it started, without blocking writers. Postgres works this way.). The unit of “all of these changes, or none of them, and nobody sees half” is a transactiontransactionA group of reads and writes the database treats as one indivisible step: either every change is applied or none is, and other clients never see it half-done., which has its own lesson.

A query language (failure four). Codd’s point: you say what you want, SELECT url FROM fetches WHERE status = 429 AND ts > ?, and a query plannerquery plannerThe part of a database that turns a declarative query into an actual plan: which index to use, which order to join tables in, whether to just scan. Postgres’s EXPLAIN shows you its choice. decides how, using whatever indexes exist. Add an index on status next month and the same query gets faster without changing a line of your code. That’s data independence, fifty-five years later.

Durability guarantees (failures one and two). A database makes an explicit promise about when “committed” means “survives a power cut”, and lets you tune it. The four-letter summary of these promises is ACIDACIDAtomicity (all or nothing), Consistency (rules like “no negative balances” always hold), Isolation (concurrent transactions don’t see each other’s half-done work), Durability (committed means it survives a crash). The four promises a transactional database makes.; the transactions lesson takes it apart. Right now the important one is that the D is a setting you can change, and you should know which position your database is in.

SQLite: a file, but a real database

SQLiteSQLiteAn embedded SQL database: a C library linked into your program that stores an entire database (tables, indexes, everything) in one ordinary file. No server process. Python ships it as the sqlite3 module. is a full SQL database, with B-tree storage, transactions, a query planner and crash recovery, that runs as a library inside your process and keeps everything in one file. D. Richard Hipp wrote it in 2000 while working on software for a US Navy destroyer; as he tells it, the program depended on a database server, and whenever the server was down, the program was useless. Its own documentation says it “does not compete with client/server databases. SQLite competes with fopen().” In other words: it’s the thing to use instead of your JSON file.

It’s probably the most deployed database engine there is (every iPhone and Android phone, every major browser, Python’s standard library), and it’s tested to an extreme: the project has hundreds of times more test code than library code, including tests that simulate power loss at every write.

Two modes matter:

• Rollback journal (the default, journal_mode=DELETE). Before changing a page in the database file, SQLite copies the original page to a separate -journal file and fsyncs it. If it crashes, the next open copies the originals back. This is an undo log rather than a redo log, but the same idea: durably record enough to recover before touching the real data. A writer locks the whole database while it commits.
• WAL mode (PRAGMA journal_mode=WAL). Changes are appended to a -wal file, and readers read the database file plus whatever the WAL says has changed. Readers no longer block the writer and the writer no longer blocks readers. Still only one writer at a time; a second writer waits (Python’s sqlite3 waits up to 5 seconds by default, the timeout argument). Periodically, SQLite checkpoints the WAL back into the main file.

And PRAGMA synchronous is the fsync dial. FULL (the default) fsyncs at every commit. NORMAL in WAL mode fsyncs less often: a commit survives your process crashing but the last few may be lost on power loss, and the database is never corrupted. One more Mac detail: SQLite on macOS uses plain fsync unless you also set PRAGMA fullfsync=ON, the same gap as in the files lesson.

When SQLite, when Postgres

(*Copy it while nothing is writing, or use SQLite’s .backup command or VACUUM INTO, which make a consistent copy while the database is in use.)

Reach for SQLite when one machine owns the data: a CLI tool, a crawler’s cache, an eval harness’s results, a desktop or phone app, a single-server web app with modest write traffic, a test fixture. It’s zero setup, a query is a function call instead of a network round trip, and the “file” is a real database with real transactions. The limit is writes: one writer at a time for the whole database. Thousands of small write transactions per second on one machine is fine (you’ll measure it); many machines writing to the same file is not, and SQLite over a network filesystem like NFS is explicitly warned against in its docs, because the file locking it relies on is unreliable there.

Reach for Postgres when many processes on many machines need to write at once, when you want users and permissions, replication to a standby, point-in-time recovery, or the big ecosystem (pgvector for embeddings, PostGIS for maps, JSONB columns when you really do want documents). The cost is a server to run, connections to manage, and a network hop on every query.

For your crawler cache: SQLite, today. If the crawler later becomes a fleet on twenty machines, Postgres, or something built for that scale.

Build It

Everything goes in ~/workbench/kv/. Standard library only: json, os, struct, zlib, sqlite3, time. Same three methods for every version, so the benchmark doesn’t care which store it’s timing.

# bench.py
import os, sys, time, importlib

VAL = b"x" * 100

def fresh(path: str) -> None:
    for p in (path, path + ".tmp", path + "-wal", path + "-shm", path + "-journal"):
        if os.path.exists(p):
            os.remove(p)

def time_puts(store, n: int, prefix: str = "key") -> float:
    """Seconds per put, averaged over n puts of new keys."""
    t = time.perf_counter()
    for i in range(n):
        store.put(f"{prefix}{i:08d}", VAL)
    return (time.perf_counter() - t) / n

def time_gets(store, n: int) -> float:
    t = time.perf_counter()
    for i in range(n):
        store.get(f"key{i:08d}")
    return (time.perf_counter() - t) / n

if __name__ == "__main__":
    print("python", sys.version.split()[0])
    import sqlite3; print("sqlite", sqlite3.sqlite_version)

# jsonkv.py
class JsonKV:
    def __init__(self, path: str, fsync: bool = True):
        """Load the whole file into self.d (empty dict if missing)."""
        ...
    def get(self, key: str) -> bytes | None: ...
    def put(self, key: str, value: bytes) -> None:
        """Update self.d, then save the WHOLE dict crash-safely:
        write path + '.tmp', flush, optionally os.fsync, os.replace."""
        ...
    def delete(self, key: str) -> None: ...

crc32 (4 bytes) | key_len (4) | val_len (4) | key bytes | value bytes
val_len = 0xFFFFFFFF means tombstone (no value bytes follow)
crc32 covers everything after itself: key_len, val_len, key, value

# logkv.py
import os, struct, zlib

HDR = struct.Struct("<III")   # crc, key_len, val_len  -> 12 bytes
TOMB = 0xFFFFFFFF

class LogKV:
    def __init__(self, path: str, sync: bool = False):
        """Open path for appending and reading ('a+b'), then self.recover()."""
        self.index: dict[str, tuple[int, int]] = {}   # key -> (value_offset, value_len)
        ...

    def _append(self, key: bytes, value: bytes | None) -> int:
        """Build one record, write it with ONE write() call, flush,
        fsync if self.sync. Return the offset where the record starts."""
        ...

    def put(self, key: str, value: bytes) -> None: ...
    def delete(self, key: str) -> None: ...
    def get(self, key: str) -> bytes | None:
        """One dict lookup, then os.pread(fd, length, offset). No seeking the shared file object."""
        ...

    def recover(self) -> None:
        """Read the log from the start. For each record: need 12 header bytes,
        need key_len + val_len more bytes, CRC must match. Apply it to the index.
        Stop at the first record that fails any check, truncate the file there,
        and print how many bytes you cut."""
        ...

# writer.py
from logkv import LogKV
db = LogKV("crash.log"); i = 0
while True:
    db.put(f"key{i}", b"v" * 4000); i += 1

rm -f crash.log; python3 writer.py & sleep 1; kill -9 $!
python3 -c "from logkv import LogKV; db = LogKV('crash.log'); print(len(db.index), 'keys')"

def _put_torn(self, key: str, value: bytes) -> None:
    """Build the record exactly like _append, write only rec[: len(rec) // 2],
    flush, then os.kill(os.getpid(), signal.SIGKILL)."""

def compact(self) -> None:
    """Write every live key's current value to path + '.compact' as fresh records,
    flush + fsync it, os.replace it over self.path, fsync the directory,
    then reopen and rebuild the index."""

# sqlkv.py
import sqlite3

class SqliteKV:
    def __init__(self, path: str, journal: str = "DELETE", synchronous: str = "FULL"):
        """connect with isolation_level=None (autocommit: each statement is its own transaction),
        set PRAGMA journal_mode and PRAGMA synchronous,
        CREATE TABLE IF NOT EXISTS kv(k TEXT PRIMARY KEY, v BLOB)."""
        ...
    def put(self, key, value): ...   # INSERT OR REPLACE
    def get(self, key): ...          # SELECT v FROM kv WHERE k = ?
    def delete(self, key): ...

# two.py   usage: python3 two.py json|sql NAME N
# json: N times: load two.json (empty dict if missing or unparseable),
#       add key f"{NAME}-{i}", save via a per-process temp file + os.replace
# sql:  N times: INSERT INTO kv VALUES (f"{NAME}-{i}", i) on two.db,
#       WAL mode, autocommit, connect(timeout=10)

python3 two.py json A 2000 & python3 two.py json B 2000; wait
python3 two.py sql  A 2000 & python3 two.py sql  B 2000; wait

Measure

Mine, M4 Pro MacBook Pro, macOS, APFS, Python 3.14, SQLite 3.53. Shape over exact numbers.

What the numbers should tell you:

JSON: 10x the keys, 10x the time. It’s O(N) per put, so O(N²) to build up N keys one put at a time. The 43 ms at 100k is nearly all serialization and copying 12 MB; the fsync is noise by comparison.

The log: about 4 µs regardless of size. That’s a Python function call, building a small bytes object, one write() syscall into the page cache, and a dict store. It’s within a factor of two of the “4 KB write only” number from the files lesson, because that’s basically all it is.

fsync dominates whenever you ask for it. 3.7 → 28 µs on the Mac. On the Spark you’ll likely see more. And SQLite’s default mode is about 10x slower again than your log with fsync, because a rollback-journal commit does several fsyncs and creates and deletes a file. WAL mode brings it within 2x of your log at the same promise, with a B-tree, SQL and transactions on top.

One transaction makes SQLite faster than your Python log. 1.3 µs per row. The work per row moved into C and the commit cost was paid once. This is the single most useful SQLite performance fact.

Recovery reads the whole log. ~50 ms per 100k records here; it scales with log size, not key count, which is why compaction and hint files exist. Cold from disk it will be slower; drop the page cache on the Spark (sync; echo 3 | sudo tee /proc/sys/vm/drop_caches) and try it.

kill -9 didn’t tear anything; deliberate tearing did, and the CRC caught it. The checksum is for the crashes kill -9 can’t produce: power loss, split writes, and silent corruption.

Two writers: JSON lost half, SQLite lost nothing. SQLite didn’t make the writers faster; it made them take turns (a file lock and a busy timeout), and each insert changed one row instead of replacing the whole world.

Break It

1. Write the JSON file in place, with a reader running. Change JsonKV.put to json.dump straight into open(path, "w"). Run one process writing in a loop and another process doing json.load in a loop. The reader will hit JSONDecodeError regularly: it opened the file between the truncate and the end of the dump. No crash needed, just two processes. A database never shows a reader a half-written state; that’s the I in ACID, and the reason temp-plus-rename exists for files.

2. Remove the CRC check. Keep the lengths but skip the CRC comparison in recover, then flip a byte in a value. Recovery happily loads it and get returns a wrong value with no error. Now flip a byte in a length field instead: recovery reads garbage as a header, and either stops early, losing every record after it, or tries to allocate a 4 GB key. Silent wrong answers are worse than crashes, and this is why every serious storage format (SQLite’s WAL, Postgres’s WAL, RocksDB’s blocks, ZFS) checksums its records.

3. Two LogKV writers on the same file. Start two processes that each open shared.log and put different keys. Appends from both land in the file (append mode makes each write() go to the current end), so the log on disk is fine; reopen it and recovery finds everything. But while running, each process’s index only knows about its own puts, and process A’s get can’t see what B wrote. Your engine has no concurrency control, it just has a log. Locks, a single writer process, or a server in front are the three ways out, and SQLite and Postgres each picked one.

4. Fill RAM with the index. Put 10 million distinct small keys and watch the process memory (ps -o rss= -p <pid>). My 1M-key Python index was about 180 MB, so expect a couple of GB. Then multiply by the number of URLs TinyFish’s crawlers know about. This is Bitcask’s hard limit, and the reason the next lesson is about trees.

Explain It Back

Answer out loud, in plain words, then check.

Go Deeper

• Martin Kleppmann, Designing Data-Intensive Applications, Chapter 3 “Storage and Retrieval” (O’Reilly, 2017; a second edition is in progress). Starts from a two-line bash database, builds up to hash indexes, SSTables, LSM-trees and B-trees. This lesson follows its path; read it next.
• Justin Sheehy and David Smith, “Bitcask: A Log-Structured Hash Table for Fast Key/Value Data” (Basho, 2010). Six pages. Exactly what you just built, plus hint files and the keydir, with the reasoning for each choice.
• E. F. Codd, “A Relational Model of Data for Large Shared Data Banks”, Communications of the ACM, June 1970. Read the first section for the problem he was solving (programs breaking when storage changed); the rest is the math of relations.
• SQLite documentation: “Appropriate Uses For SQLite”, “Atomic Commit In SQLite”, and “Write-Ahead Logging”. The first is the honest SQLite-vs-server guide. The second walks through a rollback-journal commit step by step, including every fsync, and is the best short explanation of crash-safe commits anywhere.
• Patrick O’Neil, Edward Cheng, Dieter Gawlick, Elizabeth O’Neil, “The Log-Structured Merge-Tree (LSM-Tree)”, Acta Informatica, 1996. The origin of the LSM idea. Dense; read Kleppmann’s version first and come here for the cost model.
• Alex Petrov, Database Internals (O’Reilly, 2019). Part I goes deep on B-trees, LSM-trees, page layouts and recovery. The book to keep open while doing the indexes lesson.
• CMU 15-445/645 Database Systems, Andy Pavlo’s lectures (free on YouTube and the course site). The storage, buffer pool, logging and recovery lectures cover the same ground at university depth, with good humour.
• PostgreSQL documentation, “Reliability and the Write-Ahead Log” chapter. How a production database explains its WAL, checkpoints, synchronous_commit and what fsync it relies on.

Connections

This lesson stands on Why did my checkpoint come back broken?: the page cache is why kill -9 doesn’t tear records, fsync is the durability dial, temp-plus-rename is how compaction swaps files, and the ext4 journal was your first write-ahead log. The two-writers race is the threads lesson’s lost update, moved from memory to disk.

Next, Indexes and B-trees fixes the two things your hash index can’t do: keys that don’t fit in RAM and range queries. Then Transactions takes apart the concurrency-control box in Figure 006: what exactly SQLite and Postgres promise when two writers meet, and what goes wrong at each isolation level. And Caching and Redis is, underneath, an in-memory hash table with an append-only log for durability. You’ll recognise it.