Design a Highly Available Database

The ask

The ask is a database that survives machine and site failures. Downtime is measured in minutes a year, not hours.

The target is 99.99% availability. That target allows about 53 minutes down a year.

Copies of the data live in two data centers. A fire or a flood in one place cannot take the data.

Survival, not raw speed, drives the design. Every choice is judged by what happens on a bad day.

Estimate the scale

Writes reach 10,000,000 a day.

10,000,000 writes / 86,400 seconds = 116 writes per second.

The write load is modest. Survival, not speed, drives the machinery.

Reads can be far heavier than writes. Copies in both data centers share the read load.

Each write must land on several machines. Write cost multiplies with every copy kept.

Two stances, one system

A network partition is a split where machines stay up but cannot reach each other. The split is the moment of truth for both stances.

The availability stance keeps accepting writes on both sides. The copies settle their differences after the split heals.

The consistency stance refuses writes on the side that cannot prove it holds the latest data. Some callers wait, and the data stays correct.

Both stances use the same copies and the same machinery. A requirement setting picks the behaviour during a split.

API and data

Callers use plain get and put operations. Each put can name how safe it must be.

A put can ask for one copy, most copies, or all copies. Stronger asks cost more time and fail more often during trouble.

Each record carries a version marker. The marker shows which copy of a value is newer when copies disagree.

Safety settings can differ per operation. A password change can demand more copies than a page view count.

High-level design

Each data center holds a full copy of the data. Either data center can serve reads on its own.

Copies exchange writes constantly in calm times. A write in one place appears in the other within moments.

A synchronous copy inside one region loses zero finished writes on a crash. The second data center receives writes without that promise and can lag slightly.

Callers are redirected to the surviving data center during a failover. Redirection is automatic, not manual.

Deep dive: leaderless replication

Leaderless replication is a copy arrangement with no single leader, where any copy can accept a write.

Three copies hold each value in the availability stance. A write counts when 2 copies confirm it.

A read asks 2 copies and takes the newest answer.

2 + 2 = 4, which is more than 3 copies. The read set and the write set always overlap on at least one copy.

Copies that missed a write catch up from their neighbours. Hinted handoff and read repair, the standard repairs, run in the background.

The consistency stance at work

One leader accepts writes for each part of the data. Followers copy the leader's log in order.

A write counts only after a follower in the same region confirms it. Distant copies receive the write right after.

If the leader falls silent, the followers elect a new leader. Consensus among the copies picks one leader and blocks the old one.

A fencing token stops the old leader from writing after an election. The token is a number that only grows, checked on every write.

During a split, the side without a proven leader refuses writes. Refusal is the price of never showing two different truths.

When a data center fails

The surviving data center takes over reads and writes. A regional failover completes in about 60 seconds.

Writes accepted on the failed side during a split need care at reunion. Version markers show which values diverged.

Conflicting writes settle by a stated rule. Newest wins for simple values, and counters add both sides.

No finished write vanishes in the consistency stance. In the availability stance, a losing conflict can drop one side's write, by design.

Keeping copies honest

Copies compare summaries of their data in the background. A Merkle tree is a tree of checksums that finds differing parts fast.

Anti-entropy is the background process that repairs drift between copies. Drift is the slow divergence that calm traffic hides.

Checks that a server answers feed a failure detector. The failure detector decides when a silent copy counts as down.

Repairs stay quiet during peak load. Drift grows a little, then shrinks in calm hours.

Evaluation and trade-offs

Availability first keeps the doors open through a split. The cost is stale reads and conflicts to settle later.

Consistency first keeps one truth through a split. The cost is refused writes on the cut-off side.

Latency separates the stances in calm times too. A write that waits for a copy across an ocean pays about 150 milliseconds of round trip.

Copies on several machines keep the database working through failures. The chosen stance decides what a failure feels like to callers.

Two stances compared