Databases: Replication, Partitioning and Choosing a Store

It is 8:45 pm on the night of a cricket World Cup final, and the innings break has just begun. Across India, people open the same food delivery app at once: 1,000 orders a second, about eight times the daily average, and twenty menu and tracking reads for every order. The fifty stateless app servers cope. The one database behind them does not. Its CPU sits at 100%, orders take eight seconds to confirm, and at 8:52 it crashes. For 40 seconds, nobody can order anything.

Stateless servers, from the availability chapter, work only because the state lives in the database, and you cannot run ten copies of it and hope they agree. A growing database hits three walls, each with its own tool.

Large systems use both tools, partitioning the data and replicating each partition. First, though, the choice of database and layout decides how far one machine can go.

The first decision is which kind of database to use. Families differ in the shape of the data they store and the questions they answer fast, so choose by the queries your product runs most, not by fashion.

Relational is the usual start; every other family gives up general queries to serve one access pattern very well. Time-series stores and search indexes, met later, usually sit beside a main database.

Next, lay out the data. The food app has restaurants, dishes and orders, and two broad choices.

Normalising stores each fact once, like a contacts list that keeps each number in one place. An order points to its restaurant by restaurant_id, so a rename changes one row, and reads join the tables (combine matching rows) to show the name. Denormalising copies data to where it is read: each order also stores the restaurant's name, so "my orders" needs no join, but a rename must update every copy.

Normalise first, then denormalise one measured hot path at a time. Some apparent copies are separate facts: an order's price is what was paid on 3 March, and must not change with the menu.

Key-value and wide-column stores have no joins, so you model by query: list the queries first and give each its own table. "A customer's orders, newest first" is keyed by customer_id; "a restaurant's orders today" needs a second table keyed by restaurant_id, written on every order. In a document store, embed what is read together, such as an order's items, and reference what grows without limit, such as reviews.

The restaurant dashboard asks for restaurant 77's orders today. Without help, the database reads every row, a full scan: many seconds across 50 million orders. An index works like the index at the back of a textbook: a separate sorted structure that maps a column's values to their rows, so the lookup takes about a millisecond.

Most relational databases store tables and indexes as B-trees: shallow trees of fixed-size pages sorted by key, each pointing to hundreds of children, so a billion rows sit 3 or 4 levels deep. Write-heavy stores often use LSM trees (log-structured merge trees): writes go to a log and to memory, then out to sorted files that merge in the background. These two storage engines shift work between writes and reads.

LSM trees make writes cheap and pay later, in background merging that uses disk bandwidth; for mixed work a B-tree is the safer default.

An index on (restaurant_id, created_at) is sorted by restaurant, then by time, like a phone book sorted by surname, then first name. It answers the dashboard with one short range read, but not a query on created_at alone: put equality columns first, the range column last. An index that also holds every column the query needs is a covering index: the table is never touched.

Fast reads are half the job; the other half is staying correct while many orders happen at once. A transaction groups several reads and writes into one unit, and relational databases give it four promises known as ACID. Take Asha paying ₹450 for biryani from her app wallet: the wallet is debited and an order row is created.

Atomicity and durability come from the write-ahead log: the database appends every change to a log on disk before applying it, so after a crash it redoes committed work and discards the rest. Isolation is the subtle letter, and the next page shows where it leaks.

Many key-value and document stores drop or limit multi-row transactions to scale more easily, keeping only single-item writes atomic. If a core flow must change several rows together, like Asha's debit and order, start relational.

Isolation comes in levels, like the gap between one cashier serving a queue and two cashiers sharing one cash box. Serializable behaves as if transactions ran one at a time. Most databases default to something weaker that blocks less: read committed, where you never see another transaction's uncommitted changes, or snapshot isolation, where each transaction reads one frozen, consistent view. Each weaker level lets a known anomaly through.

Snapshot isolation catches two writers on the same row, but not two writers on different rows that together break a rule.

Every fix makes the check and the write happen as one step. A conditional update does both in one statement: UPDATE riders SET order_id = 42 WHERE id = 7 AND order_id IS NULL changes the row for the first dispatcher and nothing for the second. SELECT … FOR UPDATE locks the rows you read until you commit. A unique constraint refuses the second row. Serializable aborts one transaction, so your code must retry.

Indexes and isolation make one machine fast and correct, but it can still crash at 8:52. Replication keeps copies on other machines. Picture a head cashier who alone writes in the ledger, while assistants copy each entry into their own books and answer questions from them.

In single-leader replication, one node, the leader (or primary), accepts every write. It records each change in a replication log and streams it to the other nodes, the followers (or replicas), which apply the changes in the same order. A follower can answer reads, and it is a warm standby if the leader dies.

On final night the app reads 20 times more than it writes. Send menu and tracking reads to followers, and each one adds read capacity: if a machine serves 20,000 simple reads a second, five followers serve about 100,000. But every write still goes through one leader, so followers never add write capacity.

Each follower also stores a full copy and replays every write. Two questions follow: does the leader wait for followers before confirming, and what does a reader see on a follower that is behind?

When a write reaches the leader, the leader can wait for a follower before it says "done", or reply at once and copy in the background, like a shop that updates the second ledger before handing over the receipt, or after.

Synchronous copying buys zero loss with latency and a risk of stalls; asynchronous copying buys speed with a small loss window.

Most systems take a middle path, semi-synchronous replication: the leader waits for any one follower, so every confirmed write exists on two machines, and the rest copy in the background. One slow follower then stalls nothing, because another can answer. For orders and the wallet, that extra millisecond is cheap insurance; rider locations, replaced every few seconds, can stay asynchronous.

With asynchronous followers, the gap behind the leader is the replication lag: usually well under a second, but seconds or minutes under heavy load. Lag loses nothing, yet it can show a user an old version of their own data.

Lag stays invisible until someone reads their own change. Kiran is about to order dinner and fixes the flat number in the delivery address.

Nothing was lost, yet the save looked broken, and a rider might have gone to the old flat. Kiran needs read-your-writes, from the abstractions chapter, and routing provides it, not a faster database. Four routing rules give users the guarantees they expect:

• Read your own data from the leader: a customer's own address and orders from the leader; menus from followers.
• Pin to the leader briefly: for a minute after a write, that user's reads go to the leader.
• Wait for the follower: read only from a follower that has applied the user's last write position.
• Stick each user to one follower, so a refresh never shows older data than the last: monotonic reads.

Each rule moves some reads back to the leader, so keep them narrow: route a user's own data, not every page.

Back to 8:52: the leader crashes, and a follower must take over, which is called failover. The hard part is deciding safely that the leader is dead, and who replaces it. A small consensus group of three nodes decides by majority vote, and each new leader gets a higher term, a number that goes up with every election.

The vote makes failover safe: a watcher on one machine would be a single point of failure, and in a network split only the side with a majority can elect a leader. Fencing refuses anything carrying an old term. Failover is not instant, though: writes fail until the timeout fires, often several seconds to half a minute.

Failover sounds simple: notice the dead leader, promote a follower, send writes to it. Each step hides a trap, and the defences are where most of the cost goes.

Each defence costs something: latency, extra machines or slower recovery. Voting groups run on 3 or 5 nodes across zones, surviving 1 or 2 failures; the next chapter shows how they vote.

Single-leader replication sends every write to one place. Two other designs remove that limit, and both pay with write conflicts: two copies accepting different values for the same row.

Multi-leader replication runs one leader per region. If the food app expands to the Gulf, a manager in Mumbai writes to the Indian leader, one in Dubai writes to the Gulf leader, and the leaders exchange changes in the background. Writes stay fast, and one region can fail alone. But if both managers change the same dish's price at once, both edits succeed locally, then collide. Three strategies handle that.

Choose multi-leader only when several regions must write fast or keep writing through a regional outage; offline-first apps, which sync each phone's edits later, are multi-leader too.

Leaderless replication drops the leader. The client sends each write to all N replicas and counts it successful once W confirm; a read asks R replicas and keeps the newest version. If R + W > N, the two groups share a replica, so the read sees the latest successful write. N = 3, W = 2, R = 2 overlaps and survives one replica down; W = 1, R = 1 is fastest but can miss the last write. The key-value store chapter builds this design.

Every follower holds the whole database, so replication cannot help when writes or data outgrow one leader. Then you split the data into partitions (shards), the way a booking office sends trains 1 to 999 to one counter and the rest to another. A partition key, such as customer_id, decides each row's partition, and each partition is still replicated. Two rules are common.

Use range for reads in key order and hash for exact-key access. A compound key blends them: hash the first part to pick the partition, then sort by the second inside it, so a customer's orders by time are one read.

Hashing spreads load across keys but cannot split one key. A write-hot key like this counter is split into sub-keys added up at read time, as the sharded counters chapter shows. A read-hot key, such as a famous restaurant's menu, needs a cache or more replicas instead.

The sale showed one kind of hot spot, a partition that gets far more traffic than the rest. The other common cause is keys that arrive in order: range-partition orders by time, and every new order on final night lands in the last partition while the others idle. Hash the key, or prefix it with a shard number, to spread them.

Growth brings the other chore. Moving data onto new nodes is called rebalancing, and the placement rule decides how much moves.

Fixed partitions keep every move small and predictable; pick a count well above the nodes you expect, because changing it later means splitting every partition.

Requests find their partition through a routing tier or a client that caches the partition map, kept in a small, strongly consistent coordination service so every router agrees.

Partitioning makes queries by the partition key fast and every other query awkward. Partition orders by customer_id, and "my orders" hits one partition, but "today's orders for restaurant 77" touches them all. A secondary index on restaurant_id can be built in two ways.

A local index makes the dashboard pay on every read; a global index makes every order pay a little at write time and accepts a moment of lag.

Joins and transactions across partitions are hard for the same reason: several machines must cooperate, and the slowest sets the latency. If restaurants mostly read their own orders and customers theirs, store each order twice, once keyed by each.

Everything so far comes together in choosing a store. Ask the same five questions every time; each answer narrows the field.

The food app shows the result: different data, different stores. Keep the number small, because each store is one more thing to run, back up and repair at 2 am.

Only orders and payments need transactions, so only they pay for a relational primary; the rest use the simplest store for their one pattern.

When a design needs a database, state the access pattern first, then the decision it forces, with a number.