Every persistent system has a database at its core. Understanding how databases store data, find it quickly, and copy it across machines is essential to system design. The choices — append-only vs. page-based storage, B-trees vs. LSM trees, leader-follower vs. multi-leader — each introduce trade-offs in write throughput, read latency, and failure recovery.
The write-ahead log: the source of durability
A database's first responsibility is to not lose data. The write-ahead log (WAL) is an append-only file that records every change before it is applied to the main data structures. On a crash, the database replays the log to reconstruct its state. This is why a write is not durable until it is fsync'd to disk — the log must leave the kernel's buffer and reach stable storage.
A single fsync is 1-10 ms. That is the floor for synchronous durability. Asynchronous replication and batching amortize this cost across many writes, but the log is always the bottleneck for durable writes. This is the coordination cost mentioned in the latency and throughput primer.
Indexing: trading write cost for read speed
Without an index, a read scans every row — O(n) in the number of records. With an index, the database trades write overhead and extra storage for sub-linear reads.
B-trees keep keys sorted and balanced. A lookup is O(log n) comparisons, each requiring a disk seek. B-trees support range queries naturally — WHERE id BETWEEN 1000 AND 2000 walks a contiguous leaf chain. The cost: every write may cause page splits, which are expensive because they involve allocating new pages and moving data.
LSM trees buffer writes in memory, then flush sorted runs to disk and merge them in the background. Writes are fast because they are sequential appends. Reads may need to check multiple sorted runs, so they are slower than B-trees for point lookups. LSM trees dominate write-heavy workloads; B-trees dominate read-heavy ones with range queries.
Replication: copying data to survive failure
Leader-follower replication designates one node as the write leader. All writes go to the leader; followers replicate the log asynchronously. Reads can be served from followers, scaling read throughput. The catch: followers may lag behind the leader, so a read from a follower can return stale data. This is eventual consistency, and it is fine when the product allows it.
Read-after-write consistency (a user writes and immediately reads their own change) requires routing that user's reads back to the leader, at least for their own data. This is a common pattern: writes go to the leader, reads go to followers, but user-specific reads go to the leader.
Multi-leader replication allows writes on any node, which then propagate to others. It supports multi-region writes, but introduces conflict resolution — two regions may have written conflicting values, and the application must merge them.
The trace in action
Trace a database write through leader, WAL, replication, and acknowledgment in the leader-follower write trace. This complements the cache-hit-and-miss trace — together they show the full read and write paths through a typical service.