Database Reads and Writes for System Design: WAL, B-Trees, LSM Trees, Caching, Replication and Sharding

On the same set of spinning disks, the Kafka team measured sequential writes at about 600MB/sec and random writes at about 100kB/sec. That is a gap of over 6,000x, and nearly every storage design you will meet is a clever way to dodge it. By the end of this blog you will know which tricks speed up reads, which speed up writes, and what each one costs the other side.

For this blog, we'll focus on a single database first and then scale it out: one machine's read and write paths, then caches, replicas and shards. We'll leave search indexes to How search engines work. If you want the wider database picture (families, transactions, isolation), the Databases for System Design Interviews guide goes deeper.

01Reads and writes are two different jobs

Picture a library. When a book comes back, the librarian can walk it to its exact shelf. That is a slow write, but anyone can find the book in seconds later. Or the librarian can drop it in the returns cart. That is a fast write, but finding that book is painful until someone sorts the cart. Every storage engine picks a spot between the shelf and the cart.

A few words we'll use all the way through:

• Read path: every step a read takes, from the request to the bytes coming back.
• Write path: every step a write takes, from the request to the database saying "committed".
• Latency: how long one request takes. p99 is the latency of the slowest 1 request in 100.
• Throughput: how many requests per second the system handles.
• Read-heavy vs write-heavy: which of the two your workload does more of. A news site is read-heavy; a metrics pipeline is write-heavy.
• Durability: once the database says "saved", the data survives a crash.
• Amplification: one logical read or write causing many physical ones on disk.

Why care about p99 and not the average? Because your unluckiest users live there. Amazon's Dynamo paper describes storage SLAs measured at the 99.9th percentile for exactly that reason.

Here is the whole picture we'll unpack.

02Why sequential beats random: the 6,000x gap

The numbers make the point better than any adjective. These are orders of magnitude, not benchmarks, from Peter Norvig's table and Colin Scott's interactive latency page:

Look at the last two rows. One seek costs almost half as much as reading a whole megabyte in a straight line. That is why the Kafka design docs report linear writes on six 7200rpm SATA disks at about 600MB/sec but random writes at only about 100kB/sec, "a difference of over 6000X". Kafka leans on this, and on the OS page cache: on a 32 GB machine it can use 28-30 GB of cache without holding it in the JVM.

The takeaway: appending to a log is the cheapest write you can make. Hold on to that, because the log shows up in almost every section below.

03The write path, step by step

Here is what a Postgres-style database does with an INSERT:

1. The client sends the INSERT.
2. The database writes a log record describing the change into the WAL buffer (a small area in RAM for log records).
3. It changes the table page in the buffer pool, the database's own RAM cache of disk pages. The page is now dirty: newer in memory than on disk.
4. On COMMIT, the WAL is flushed to disk with fsync, the system call that asks the OS to really put bytes on the device.
5. Only now does the client hear "committed".
6. Later, a checkpoint writes dirty pages to the data files in the background.

The sequence below shows when the client gets its OK.

So the answer to the guess is no. Only the log is guaranteed to be on disk. That is safe, because after a crash the database replays the log and redoes any committed change the data files missed. The Postgres WAL docs spell out why this is fast: the commit costs one sequential append to the log, while the scattered page writes happen later and get combined.

04Write-ahead logging: the idea you'll see everywhere

Think of it as a shop's daybook. The shopkeeper scribbles every sale in a notebook as it happens, and updates the neat ledger at closing time. If the ledger gets coffee on it, the notebook rebuilds it.

Once you see the pattern, you see it everywhere:

• SQLite has a WAL mode where readers don't block writers and I/O is more sequential. The docs are honest about the cost: for read-mostly apps it "might be very slightly slower (perhaps 1% or 2% slower)".
• Redis has the AOF, an append-only file of write commands it replays on startup (Redis persistence).
• Bigtable writes every change to a commit log of redo records before the in-memory table (Bigtable paper, section 5.3).
• RocksDB puts an optional WAL in front of its memtable (RocksDB Overview).
• Kafka takes the idea to its end: the log is the product.

05The read path, step by step

Now the other direction. A read for one user's profile goes roughly like this:

1. The app checks its cache. A cache hit means the answer is there; a cache miss means it isn't.
2. On a miss, the query goes to the database.
3. The query planner picks an index (a sorted structure that points at rows) or a full table scan (reading every row).
4. The index lookup finds where the row lives.
5. The database checks the buffer pool for that page.
6. On a buffer miss, it reads the page from disk. The OS page cache may still save you a device read.
7. The row comes back, and the app fills its cache for next time.

Most systems have hot data: a small set of rows read far more than the rest. The whole read path is designed to keep that set as high up the stack as possible. Why? Do the arithmetic with the table above. RAM at 100 ns vs an SSD random read at 16 µs is roughly 160x. An SSD read vs a disk seek at 8 ms is roughly 500x. (Those ratios are our own division, not measurements.) Most read tuning is about stopping earlier.

06B-Tree vs LSM tree: update in place, or append and merge

The shelf-or-cart choice from the library becomes a real data structure here.

The B-Tree is the default index type in Postgres, and a whole SQLite database file is a set of B-tree pages. Your phone is full of them.

That is the RocksDB write path, in the words of the RocksDB Overview. The idea dates to the 1996 LSM-tree paper by O'Neil and colleagues. They wrote it because, for a fast-growing indexed history table, a B-tree "will effectively double the I/O cost". Their fix batches changes in memory and cascades them to disk in a way "reminiscent of merge sort".

The catch is on the read side. A key might live in the memtable or in any of several files. So LSM engines add a Bloom filter per file: a tiny summary that answers "definitely not here" or "maybe here", letting a read skip most files (RocksDB Bloom filter).

Here are both shapes side by side.

07Indexes: faster reads, slower writes

Indexes are not free. The Postgres docs say it plainly: the system must update every index whenever the table changes. Every index taxes every write.

Uber's post Why Uber Engineering Switched from Postgres to MySQL is a sharp example. In their setup, Postgres secondary indexes pointed at physical row locations, so an update could touch every index on the table, and those extra writes also inflated replication traffic. Treat it as one company's view of its own workload, not a verdict on Postgres.

My rules of thumb: index what you filter and sort on, drop unused indexes, mind column order in composite indexes, and use a covering index (one holding every column the query needs) to skip the table read. Text, location and "similar to this" queries need other index shapes: inverted, geo and vector indexes.

08Caching: cache-aside, write-through and write-back

A cache is a fast copy of data that lives somewhere expensive. Think of the snacks on your desk versus the supermarket across town. Four more words:

• Hit ratio: the share of reads the cache answers.
• TTL (time to live): how long an entry stays before it expires.
• Invalidation: removing or updating an entry when the source changes.
• Stale read: reading an old value the source has already changed.

Cache-aside (also called look-aside or lazy loading) is the common default. The app reads the cache; on a miss it reads the database and fills the cache. On a write, it updates the database and then deletes the cache key so the next read refills it. Facebook's memcache is the classic example: a "demand-filled look-aside cache" that, per Scaling Memcache at Facebook, "handles billions of requests per second and holds trillions of items".

Write-through sends every write to the cache and the database together before the ack. AWS's caching best practices put it as the cache being "updated in real time when the database is updated". Reads after a write are fresh; writes get slower.

Write-back (or write-behind) writes to the cache, acks straight away and flushes to the database later. Writes are fast, but a crash loses whatever hadn't been flushed. You already use one: the OS page cache works this way. Redis offers the same dial for its AOF: with appendfsync everysec, "you can only lose one second worth of writes".

The three patterns differ in one arrow: where the ack happens.

Hit ratios are often modest. Jeff Dean's WSDM 2009 keynote reports Google's cache servers in front of the index had hit rates "typically 30-60%", with a big latency spike when the cache was flushed. The database behind the cache must still survive a cold start.

09Batching and group commit

Batching turns many small writes into one bigger one. Think of a postman who waits to fill the bag instead of driving each letter over separately. Group commit is the database version: when several transactions commit at once, one fsync of the log makes all of them durable. The Postgres WAL docs describe this, and Bigtable uses group commit too. It is a big reason databases often get more efficient per write as load rises, up to a point.

Some systems let you go further and trade a little safety for speed:

• Postgres asynchronous commit acks before the WAL flush. A crash can lose the last few transactions, but the docs stress it is "data loss, not data corruption".
• Redis appendfsync has three settings: always, everysec and no.
• Apps batch too: bulk inserts, or buffering writes in a queue. Discord indexes messages into Elasticsearch in bulk with refresh set to every 60 minutes, on purpose, because people mostly search older messages.

10Replication: leader-follower, read replicas and lag

A replica is a full copy of the data on another machine. In the common setup, one leader (or primary) takes all writes and one or more followers (standbys, read replicas) copy them. With synchronous replication, the leader waits for a follower before acking; with asynchronous replication, it doesn't. Replication lag is how far behind a follower is. Failover is promoting a follower when the leader dies.

Here is the neat part: in Postgres, the leader ships its WAL to standbys, which replay it. The same log that protects you from crashes now feeds your replicas. The log-shipping docs note this is asynchronous by default.

Read replicas scale reads, not writes. Every replica still applies every write.

Async replication creates a classic bug. Watch what happens when a user edits their profile and refreshes.

This breaks read-your-writes: the promise that you see your own changes. Common fixes: read from the leader for a short window after a user writes, or pin a user's session to the leader or an up-to-date replica.

Not every system has a single leader. Amazon's Dynamo is leaderless and "always writeable": with sloppy quorums and hinted handoff a shopping cart accepts writes even during failures, and Merkle trees repair differences later.

11Sharding: range, hash and hot keys

When one machine can't hold the data or take the writes, you split the data. A shard (or partition) is one slice, living on its own machine. The shard key decides which slice a row goes to. Think of a post office sorting letters into bins by PIN code.

• Range sharding splits keys by ranges. Neighbours stay together, so range scans are cheap. Bigtable works this way: "each row range is called a tablet" (Bigtable). The risk is a hot tail: if keys grow over time, all new writes land on the last range.
• Hash sharding hashes the key to pick a shard. Load spreads evenly, but ordering is lost.
• Consistent hashing places shards on a ring so adding a node moves only a slice of the keys, not all of them (Dynamo).
• A hot key or hot partition gets far more traffic than the rest. A cross-shard query needs data from more than one shard.

Compare the two main strategies and where each one runs hot.

Discord's How Discord Stores Trillions of Messages describes hot partitions on Cassandra causing cascading latency. Part of the fix was a layer of Rust data services that coalesce identical reads and route requests by channel ID with consistent hashing.

Choosing the shard key is the real decision. Figma's database team, whose stack grew "almost 100x since 2020", first split tables into separate databases (vertical partitioning), then sharded horizontally. They grouped tables sharing a shard key into "colos" and kept logical shards separate from physical machines. The price: cross-shard queries became limited. Instagram's Sharding & IDs post covers another wrinkle: generating unique IDs across Postgres shards.

If a query doesn't include the shard key, you must ask every shard and merge the answers. That is scatter-gather. Dean's WSDM keynote describes Google's index servers as sharded by document, so every shard processes every query.

12CQRS: separate models for writes and reads

You probably run a version of this already. Postgres is the source of truth, and an Elasticsearch index serves search. A search index is a read model. DoorDash goes further in its in-house search engine, splitting a non-replicated indexer from replicated searchers.

The honest caveat comes from Martin Fowler: for most systems, CQRS "adds risky complexity". The read side is always a little behind, so you are buying read speed with eventual consistency. Don't start here. Reach for it when the shape of your reads and writes really diverges.

13Real system: Discord's reads and writes at trillions of messages

Discord's storage story ties most of this blog together. It ran 12 Cassandra nodes in 2017 and 177 by early 2022, holding trillions of messages. After migrating, it ran 72 ScyllaDB nodes. The before and after:

Map the fixes to this blog: request coalescing tamed hot keys (caching), channel-ID routing used consistent hashing (sharding), both databases are LSM-based (B-Tree vs LSM), and the move had no downtime, at the cost of a big migration project.

14When it goes wrong: edge cases and failure modes

• Cache stampede. A hot key expires and thousands of misses hit the database at once. Coalesce identical requests (as Discord did) or refresh popular entries before they expire.
• Lost writes on failover. With async replication, the leader can ack a write, die and be replaced by a follower that never got it.
• Compaction debt. In an LSM, background merges compete with live traffic. Merging is also write amplification: McCandless measured Lucene merging copy 67.30 GB to build a 10.87 GB index, a factor of 6.19 (Visualizing Lucene's segment merges).
• Index bloat. Update-heavy tables with many indexes pay for every index on every write, and then again in replication (Uber).
• Hot shard. A celebrity key overloads one shard. Rebalancing moves data around; consistent hashing limits how much moves.

15How to optimise reads vs writes: the checklist

Cheapest rung first. Every rung costs the other side something.

16How to say it in the HLD interview

When I ask about storage, I'm listening for three things. Do you know your read/write ratio? Do you know where the ack happens? Can you name what each optimisation costs? Here's a talk track that hits all three.

Many candidates lose points in the same places: using replicas for write scaling, adding a cache with no invalidation story, sharding before trying indexes, caching and replicas, and picking a shard key that forces scatter-gather on the main query.