Contents

Course · 07

How do you keep copies of data, and split it across many machines?

One database machine can break, and it can only hold and serve so much. Replication keeps copies so you survive failures. Sharding splits data so you can grow. This page shows how both really work, and what breaks.

TL;DR

Replication copies the same data to many machines; sharding gives each machine a different slice of the data.

Copies can be updated right away (sync, safe but slow) or a bit later (async, fast but can lose or show old data).
Leaderless stores like Dynamo use quorums: with R + W > N, reads and writes overlap on at least one copy.
The shard key decides everything: a bad key makes one hot shard while the others sit idle.
Consistent hashing moves only about 1/n of keys when you add a node; plain hash mod N moved 75% in our 3 to 4 node example.

(3,2,2)

Common Dynamo setting for N, R, W (Dynamo paper §6)

75%vs 25%

Keys that move going from 3 to 4 nodes: mod N vs consistent hashing (section 9)

1,000WCU

Write units per second one DynamoDB partition can take (AWS docs)

—Words you need

Each jargon word once, in plain words glossary

Replica

One full copy of the data on another machine.

Leader (primary)

The one copy that accepts writes and sends changes out.

Follower (replica, secondary)

A copy that receives changes from the leader. Often serves reads.

Replication lag

How far behind the leader a follower is, in time.

Quorum

The minimum number of copies that must say "yes".

Failover

Making a follower the new leader when the leader dies.

Split brain

Two machines both think they are the leader. Data forks.

Shard (partition)

One slice of the data, living on its own machines.

Shard key

The field that decides which shard a row goes to.

Hot partition

One shard getting far more traffic than the others.

Consistent hashing

Put keys and servers on a circle, so adding servers moves few keys.

Virtual node (vnode)

One server placed at many spots on the circle, for even spread.

Secondary index

A lookup by a field that is not the shard key.

Scatter-gather

Ask every shard, then merge the answers. Slow at scale.

Copies (replication)

01Why keep copies at all?

Four reasons, and the one big cost core

A copy of your data on another machine is called a replica. You keep replicas for four reasons.

Survive failure

High availability

A disk or machine dies. Another copy keeps serving. Users never notice.

02Who takes the writes?

Leader-follower, multi-leader, leaderless core

The biggest design choice is: which copies may accept a write? There are three answers.

Leader-follower: one door for writes, many doors for reads.

Model	Who accepts writes	Good at	Hard part	Examples
Leader-follower (single leader)	Only the leader	Simple. No write conflicts.	Leader is a bottleneck. Failover is tricky.	PostgreSQL, MySQL, MongoDB replica sets
Multi-leader	One leader per data center (or device)	Fast local writes in many regions. Works offline.	Two leaders change the same row: conflict.	MySQL group setups, CouchDB, calendar apps on phones
Leaderless	Any replica	No failover needed. Stays up when nodes die.	Quorum maths. Old values. Repair work.	Dynamo, Cassandra, Riak

Multi-leader conflicts are the main pain. If Mumbai sets a title to "A" and Virginia sets it to "B" at the same time, which wins? Common answers:

Last write wins (LWW): keep the one with the bigger timestamp. Simple, but silently throws the other write away.
Merge: keep both and let the app or user choose (Dynamo returns both versions to the app).
CRDTs (conflict-free replicated data types): data shapes, like counters and sets, that always merge the same way on every copy.

In everyday words

Leader-follower is one teacher writing on the board while students copy. Multi-leader is two teachers in two rooms editing the same notes, then comparing later.

Actually

The leader writes every change to a log (MySQL's binary log, PostgreSQL's write-ahead log, or WAL). Followers replay that log in the same order, so they end up in the same state. Dynamo, a leaderless store, keeps conflicting versions and tags each with a vector clock so the app can merge them: "Dynamo uses vector clocks in order to capture causality between different versions of the same object" (Dynamo paper §4.4).

Default to single leader. Pick multi-leader only for many regions or offline clients, and plan conflict handling first.

Source: Dynamo paper (DeCandia et al., SOSP 2007) · PostgreSQL streaming replication

03Sync, async, or semi-sync?

When does the leader say "saved"? interview favourite

When you write, the leader must decide when to tell you "OK". Before the followers have the change, or after?

Time runs down the page. The coral arrow is the promise to the user.

Mode	Leader says OK when…	Write speed	If leader dies right after OK
Synchronous	All sync followers have the change	Slowest. One slow follower slows every write.	No data lost
Asynchronous	Only its own disk has it	Fastest	Recent writes can be lost
Semi-synchronous	At least one follower has received it	Middle: one network round trip	Usually safe; falls back to async on timeout

In everyday words

Sync is posting a letter by registered mail and waiting for the signed receipt. Async is dropping it in the post box and walking away. Semi-sync is waiting until one friend texts "got your copy".

Actually

In MySQL 8.4 semi-sync, the replica acknowledges "only after the events have been written to its relay log and flushed to disk". The default wait point is AFTER_SYNC. If no replica answers within rpl_semi_sync_source_timeout (default 10000 ms), "the source reverts to asynchronous replication". PostgreSQL streaming replication "is asynchronous by default"; you turn on sync with synchronous_standby_names, and ANY 2 (a,b,c) means a quorum of any 2 (MySQL semi-sync, PostgreSQL docs).

postgresql.conf · wait for any 1 of 2 standbys

synchronous_standby_names = 'ANY 1 (replica_a, replica_b)'
synchronous_commit = on        # values: remote_apply, on, remote_write, local, off

Real systems mix: one sync copy for safety, the rest async for speed. Semi-sync silently becomes async when replicas are slow.

Source: MySQL 8.4 semi-sync · MySQL source options · PostgreSQL synchronous_commit

04Replication lag: "I saved it, where did it go?"

Read-your-writes, monotonic reads, and their fixes interview favourite

With async copies, a follower may be a few milliseconds or minutes behind. This delay is replication lag. Reading from a lagging follower shows old data.

The write succeeded. The read was sent to a copy that had not heard about it yet.

Two guarantees fix most user complaints. Both come from a 1994 paper on "session guarantees".

Guarantee	What the user expects	Common fix
Read-your-writes	"After I save, I see my change."	Read your own data from the leader for a short time (say 1 minute) after you write. Or remember the write's log position and only read from a follower that has reached it.
Monotonic reads	"Time never goes backwards for me."	Stick each user to one follower (pick it by `hash(user_id)`), so two refreshes never hit a newer then an older copy.
Consistent prefix	"I never see an answer before its question."	Keep related writes in the same shard so they are applied in order.

In everyday words

You post a letter and then ask a different post office if it arrived. It hasn't reached them yet. Asking the office you posted it at (the leader) fixes it.

Actually

Terry et al. (1994) define Read Your Writes as "read operations reflect previous writes" and Monotonic Reads as "successive reads reflect a non-decreasing set of writes". Werner Vogels (Amazon CTO) explains monotonic read as: "If a process has seen a particular value for the object, any subsequent accesses will never return any previous values." AWS says Aurora replica lag "is usually much less than 100 milliseconds" (Aurora replication doc). Even 100 ms is enough to break a "save then reload" screen.

Lag is normal, not a bug. Your job is to hide it where users would notice: their own writes, and going back in time.

Source: Terry et al. 1994, Session Guarantees · Vogels, Eventually Consistent · Aurora replication

05Leaderless quorums: the Dynamo way

N, R, W, sloppy quorum, hinted handoff, read repair, Merkle trees deep dive

In a leaderless store, the client (or a coordinator node) sends each write to N replicas. It waits for W of them to say yes. Each read asks replicas and waits for R answers.

R + W = 4 is more than N = 3, so any 2 readers and any 2 writers share at least one replica.

The rule is R + W > N. Then the set of replicas you read from must overlap the set that took the latest write. The reader compares versions and keeps the newest.

Setting (N, R, W)	Effect
(3, 2, 2)	Balanced. Survives 1 slow or dead node for both reads and writes. The common Dynamo setting.
(3, 1, 3)	Fast reads, but one dead node blocks all writes.
(3, 3, 1)	Fast writes, but one dead node blocks all reads.
(3, 1, 1)	Fastest. R + W = 2, not more than 3, so reads can be stale. Eventual consistency only.

What happens when nodes are down or behind

Sloppy quorum

Use the next healthy nodes

If a home replica is down, write to the next healthy node on the ring instead. Writes keep working, but R + W > N no longer promises overlap.

Hinted handoff

A note saying "this is not mine"

The stand-in node keeps the write plus a hint naming the real owner. When the owner comes back, it hands the data over.

Read repair

Fix old copies while reading

A read sees B has v2 and C has v1. It sends v2 to C. Popular keys heal fast; rarely read keys do not.

Anti-entropy

Merkle trees find differences

Each replica hashes its key ranges into a tree. Compare the top hash; only walk down branches that differ. Little data is sent.

In everyday words

Three friends keep a shared diary. You tell any two about each event, and when you check, you ask any two. Since two plus two is more than three, at least one friend you ask has heard the latest news.

Actually

From the Dynamo paper: "Setting R and W such that R + W > N yields a quorum-like system" (§4.5). "The common (N,R,W) configuration used by several instances of Dynamo is (3,2,2)" (§6). Dynamo "uses a 'sloppy quorum'; all read and write operations are performed on the first N healthy nodes from the preference list" (§4.6). Table 1 lists "Sloppy Quorum and hinted handoff" for temporary failures and "Anti-entropy using Merkle trees" for permanent ones. Read repair: "the coordinator updates those nodes with the latest version" (§6.4). Note: R + W > N alone does not give linearizable reads; concurrent writes, sloppy quorums and partly failed writes still allow surprises (Dynamo paper).

Quorums let any node take writes and survive failures. You pay in repair work and weaker guarantees than a leader gives.

Source: Dynamo paper §4.5, §4.6, §6, Table 1 · Cassandra tunable consistency

06Failover and split brain

The leader died. Or did it? interview favourite

Failover means: notice the leader is dead, pick the most up-to-date follower, make it leader, and point clients at it. Each step can go wrong.

Detect: no heartbeat (an "I'm alive" message) for, say, 30 seconds. Too short a timeout causes false failovers. Too long means minutes of downtime.
Choose: the follower with the most of the log. With async copies, the last few writes may be lost.
Switch: update DNS or the proxy so clients send writes to the new leader.

The worst case is split brain: the old leader was only cut off, not dead. Now two leaders take writes.

Both leaders are healthy. They just cannot see each other.

Defence	How it stops split brain
Majority quorum	A node may lead only if it can reach more than half the voters. With 5 voters, only one side of a cut can have 3. The minority side stops taking writes.
Epoch or term number	Every new leader gets a bigger number. Replicas reject writes carrying an older number. Raft calls this the term (page 08).
Fencing	Cut the old leader off: revoke its storage access, or power it off (STONITH: "shoot the other node in the head").
Odd number of voters	3 or 5, never 2 or 4. With 4, a 2 and 2 split leaves nobody with a majority.

In everyday words

A ship's captain is cut off by a storm. The crew picks a new captain. The storm clears and now two people give orders. The fix is a rule: you are captain only while more than half the crew can hear you.

Actually

Single-node managed failover hides much of this. AWS says RDS read replicas are updated "asynchronously", so promoting one can lose the last writes that had not arrived yet (RDS read replicas). The general fix, a majority vote plus a term number, is exactly what consensus algorithms like Raft provide; page 08 shows it step by step.

Failover is a vote, not a guess. Without a majority rule and a term number, a network cut becomes two leaders and forked data.

Source: AWS RDS read replicas · Raft paper

Splitting (sharding)

07Ways to split the data

Range, hash, directory, geography core

Copies don't help when the data is too big for one machine, or there are too many writes for one leader. Then you shard: each machine group holds a different slice. Most systems shard and replicate each shard.

Ranges keep neighbours together, which is great for scans and bad when "now" is the busy part.

Strategy	How a row finds its shard	Good at	Bad at	Used by
Range	Key falls between a start and end value	Range scans ("all orders in March")	Hot spots on time or growing IDs	MongoDB ranged sharding, HBase, Bigtable
Hash	`hash(key)` picks the shard	Even spread of load	Range scans need every shard	Cassandra, DynamoDB, MongoDB hashed sharding
Directory (lookup table)	A lookup service says "key K lives on shard 7"	Full control; move single tenants	The lookup service is an extra hop and must never go down	Vitess lookup vindexes, many multi-tenant SaaS apps
Geo	User's region picks the shard	Low latency, data-residency laws	Users who travel; uneven region sizes	MongoDB zones, Cassandra per-data-center replication

In everyday words

A library splits books across rooms. By range: A to H in room 1. Easy to browse, but if every new book starts with "S", one room overflows. By hash: a coin-toss-like rule spreads books evenly, but browsing "all books on cooking" means visiting every room.

Actually

MongoDB documents both: "Ranged sharding divides data into ranges based on the shard key values" and "Hashed Sharding computes a hash of the shard key field's value". It also lets you "create zones of sharded data based on the shard key", which is how geo sharding is done there. Its default range (chunk) size is 128 MB, and a balancer "automatically migrates data when there is an uneven distribution" (MongoDB sharding, data partitioning).

Hash for even load, range for scans, directory for control, geo for law and latency. Every choice makes some query expensive.

Source: MongoDB sharding · MongoDB ranges and balancer · Vitess vindexes

08Choosing a shard key, and the celebrity problem

The one decision that is hard to undo interview favourite

A good shard key has three properties.

Many values

High cardinality

Millions of different values. A "country" key gives only about 200 shards at most, and India is far bigger than Iceland.

Even traffic

No hot values

No single value gets a big share of reads or writes. Time stamps and growing IDs fail this for writes.

Matches queries

Your main query has it

The most common query includes the key, so it goes to one shard, not all.

Hot partitions still happen with a good key. One celebrity's post gets millions of likes. One big customer sends half the traffic. Every request for that key lands on one shard.

Fix	How	Cost
Add a random suffix (write sharding)	Store `post123#0` to `post123#9`. Writes spread over 10 partitions.	Reads must fetch all 10 and add them up.
Cache the hot key	Put the celebrity's data in Redis or a CDN.	Cache invalidation.
Split the hot shard	Give the hot range its own machine.	Only works if the heat is a range, not one key.
Treat celebrities differently	For feeds: push posts of normal users, pull posts of celebrities at read time.	Two code paths.

DynamoDB write sharding · spread one hot key over 10 partitions

pk = f"likes#post123#{random.randint(0, 9)}"   # write: pick 1 of 10
total = sum(get(f"likes#post123#{i}") for i in range(10))  # read: add all 10

In everyday words

A supermarket opens ten tills, but everyone queues at the one where the famous chef is signing books. More tills don't help. You need to split the chef's queue, or give him his own room.

Actually

DynamoDB: "Every partition in a DynamoDB table is designed to deliver a maximum capacity of 3,000 read units per second and 1,000 write units per second." Its fix for hot keys: "add a random number to the end of the partition key values. Then you randomize the writes across the larger space." Adaptive capacity also "rebalances your partitions such that frequently accessed items don't reside on the same partition". Discord hit the same wall in Cassandra: "Lots of concurrent reads as users interact with servers can hotspot a partition, which we refer to imaginatively as a 'hot partition'" (DynamoDB partition key design, Discord blog, 2023).

Pick a key with many values, even traffic, and present in your main query. Then plan for the one key that breaks the rule anyway.

Source: DynamoDB partition keys · DynamoDB write sharding · adaptive capacity · Discord

09Consistent hashing and resharding

Add a server without moving everything deep dive

The naive rule is shard = hash(key) mod N. It spreads load well. But change N and almost every key moves.

Worked example. Go from 3 to 4 servers. A key stays only if h mod 3 equals h mod 4. Check h = 0 to 11 (the pattern repeats every 12): only 0, 1 and 2 match. So 3 of 12 keys stay, and 9 of 12 = 75% move.

Consistent hashing puts servers and keys on the same circle of hash values (the "ring"). A key belongs to the first server you meet going clockwise. Adding a server only takes keys from its one neighbour.

Adding D steals one small arc. With mod N, nearly every key would move.

Share of keys that move when going from 3 to 4 servers

Worked out above. Consistent hashing moves about 1/n of keys, where n is the new server count.

hash mod N

75%

Consistent hashing

~25%

Show the full table

Method	Keys that move (3 to 4 servers)	Why
`hash mod N`	75%	Only `h mod 12` in 0, 1, 2 keep the same shard
Consistent hashing	~25%	New server takes a fair share, about 1/4, only from neighbours

Why virtual nodes? With one point per server, the arcs are random lengths, so one server may own 50% of the ring. And when a server dies, its whole arc lands on one neighbour. With many points per server (vnodes), arcs average out, and a dead server's load spreads over many others. A bigger machine can simply get more points.

Rebalancing in practice. Moving data is a copy job: copy the slice to the new owner, keep copying new changes, then switch ownership. Systems do this with fixed small units so moves are cheap: MongoDB moves 128 MB ranges; Vitess runs a Reshard workflow that copies with VReplication and then switches traffic.

In everyday words

Kids sit around a round table and each takes the sweets to their right, up to the next kid. A new kid sits down. Only the kid next to them gives up some sweets. Everyone else keeps theirs.

Actually

Consistent hashing (Karger et al., 1997) means "only n / m keys need to be remapped on average where n is the number of keys and m is the number of slots" (Wikipedia, citing Karger 1997; the original paper was not read directly). Dynamo: "Dynamo uses the concept of 'virtual nodes'. A virtual node looks like a single node in the system" (§4.2). Cassandra 4.0 changed the default num_tokens in cassandra.yaml "from 256 to 16" (CASSANDRA-13701), and its default partitioner is Murmur3Partitioner (Cassandra 4.0 NEWS).

Never shard with plain mod N if you plan to grow. Use a ring with vnodes, or many small fixed slices that you move between machines.

Source: Consistent hashing · Dynamo §4.2 · cassandra.yaml · Vitess Reshard

10Cross-shard queries and secondary indexes

What if the query does not have the shard key? deep dive

Orders are sharded by order_id. Now support wants "all orders for a@b.com". The email is not the shard key. Two choices.

Local index: cheap writes, expensive reads. Global index: cheap reads, every write touches two places.

Index type	Write cost	Read cost	Freshness	Example
Local (per shard)	Same shard, same transaction	Scatter-gather to all shards	Always up to date	Cassandra secondary indexes, DynamoDB LSI, MongoDB non-shard-key queries
Global (sharded by the indexed field)	Also updates a second shard	One index shard, then one data shard	Usually updated async: can lag	DynamoDB GSI, Vitess lookup vindex

Cross-shard joins and transactions. A join across shards means pulling rows from many shards and joining in the app or query router. A transaction across shards needs two-phase commit (page 08) or a saga. Best fix: avoid it by design. Put data that is read together under the same key. For example, shard both orders and order_items by customer_id, so one customer's data lives on one shard.

In everyday words

A phone book sorted by surname cannot find people by phone number. You either read every page (local index), or keep a second book sorted by number that points back to the page (global index), and update both when someone moves.

Actually

Cassandra: "the indexes are locally built on each Apache Cassandra node". MongoDB: "If queries do not include the shard key ... mongos performs a broadcast operation, querying all shards", and "These scatter/gather queries can be long running operations". DynamoDB: "Queries on global secondary indexes support eventual consistency only"; LSIs must be created with the table and "there is a 10 GB size limit per partition key value"; quotas are 5 LSIs and a default 20 GSIs per table (as of the AWS docs, checked 2026-10-25). Vitess calls lookup vindexes "cross-shard indexes" (DynamoDB secondary indexes).

Every query without the shard key either hits all shards or needs a second, lagging index. Design keys around your top queries.

Source: Cassandra 2i · MongoDB sharding · DynamoDB LSI · DynamoDB quotas · Vitess vindexes

11How real systems do it

Cassandra, DynamoDB, MongoDB, Vitess from docs

System	How it shards	How it replicates	Key facts
Apache Cassandra	Hash ring, `Murmur3Partitioner`, vnodes (`num_tokens: 16` in 4.0+ yaml)	Leaderless, Dynamo-style. `NetworkTopologyStrategy` sets a replication factor per data center.	Per-query consistency: `ONE`, `QUORUM` (n/2 + 1), `LOCAL_QUORUM`, `ALL`. Indexes are local.
Amazon DynamoDB	Hash of the partition key picks a partition. Partitions split automatically.	Managed by AWS across several zones.	Per partition max 3,000 RCU and 1,000 WCU. GSI reads are eventually consistent only.
MongoDB	Ranged or hashed shard key; zones for geo. `mongos` routes; config servers hold metadata.	Each shard is a replica set (one primary, several secondaries).	Default range size 128 MB. Queries without the shard key are broadcast.
Vitess (sharded MySQL)	A primary vindex maps a column to a keyspace ID. Shards are named by key range, like `-80` and `80-`.	Normal MySQL replication inside each shard.	Lookup vindexes for non-key queries; `Reshard` workflow to split shards online.

Actually

In Vitess shard names, "A - prefix means: anything less than the right value. A - postfix means: anything greater than or equal to the LHS value". So -80 holds keyspace IDs below 0x80 and 80- holds the rest: two equal halves (Vitess shard concept). Cassandra's QUORUM is "A majority (n/2 + 1) of the replicas must respond" (Cassandra docs).

All four do the same two things: hash or range a key into slices, then copy each slice 3 times. They differ in who decides and how much is automatic.

Source: Cassandra Dynamo architecture · DynamoDB · MongoDB · Vitess

Practice

—When to use what

Situation, pick, why decision table

Situation	Pick	Why
Read-heavy app, one region, data fits one machine	Single leader + async read replicas	Simple, no conflicts. Add replicas for reads.
Money or orders, must not lose a write	Sync or semi-sync to at least one replica	A crash right after "OK" loses nothing.
Users write in many regions, low latency needed	Multi-leader, or leaderless with `LOCAL_QUORUM`	Writes stay local. Plan conflict handling.
Must stay writable while nodes die	Leaderless quorum (3,2,2)	No failover step; any 2 of 3 is enough.
Data or writes too big for one leader	Shard, then replicate each shard	Replication alone never adds write capacity.
Main queries are ranges ("last 7 days")	Range sharding, with a non-time prefix	Scans stay on one shard without making "now" hot.
Main queries are by ID, need even load	Hash sharding	Spreads writes evenly.
Will add servers often	Consistent hashing with vnodes, or many fixed slices	Moves about 1/n of data, not most of it.
Multi-tenant SaaS with a few huge tenants	Directory-based sharding	Move one big tenant to its own shard.

—Common mistakes

Things that sound right and are wrong traps

Trap

"Replicas are my backup"

A bad delete is copied to every replica in milliseconds. Keep real backups.

Trap

"Add replicas to scale writes"

Every replica applies every write. Only sharding adds write capacity.

Trap

"R + W > N means strong consistency"

Sloppy quorums, concurrent writes and partial failures still give stale or odd reads.

Trap

Sharding by timestamp

All new writes hit the newest shard. Prefix with a hashed ID.

Trap

hash mod N for growing clusters

Going 3 to 4 nodes moved 75% of keys in our example.

Trap

Two-node clusters with auto failover

A cut gives 1 and 1: nobody has a majority, or both promote. Use 3.

Trap

Last write wins by wall clock

Clocks drift, so the "later" write may be the older one. Data silently lost.

Trap

Sharding too early

Sharding makes joins, transactions and ops hard. Scale up and add replicas first.

—Interview questions

20 questions, easy to hard, with model answers practice

Why would you replicate a database? easy

Show answer

Four reasons: availability (a copy keeps serving if a machine dies), read scaling (spread reads over replicas), latency (a copy near the user), and durability (data on two disks). The cost is that copies can disagree while changes travel. I'd also say what it does not do: it does not scale writes, because every replica applies every write, and it is not a backup, because a bad DELETE is copied too. Example: RDS read replicas are updated asynchronously, so they can serve slightly old data. Follow-up: "How would you scale writes?" (shard).

In leader-follower replication, where do reads and writes go? easy

Show answer

All writes go to the single leader. The leader writes them to its log (binlog or WAL) and followers replay that log in order. Reads can go to the leader (always fresh) or to followers (more capacity, maybe stale). The win is simplicity: one writer means no write conflicts. The cost: the leader is a write bottleneck and a failover point. Typical setup: one leader plus 2 replicas, reads for dashboards and search go to replicas, reads right after a user's own write go to the leader.

Compare sync and async replication. easy

Show answer

Sync: the leader replies "OK" only after followers have the change. No data loss if the leader dies, but every write waits for the slowest sync follower, and if that follower is down, writes stop. Async: the leader replies after its own disk write. Fast and unaffected by slow followers, but writes acknowledged in the last moments can be lost on failover. Most real setups mix: one sync (or semi-sync) follower and the rest async. PostgreSQL is async by default; you opt in with synchronous_standby_names.

What is semi-sync replication, and what happens when the replica is slow? medium

Show answer

The leader waits until at least one replica has received and logged the change, not applied it. In MySQL 8.4 the replica acks after writing to its relay log and flushing it. The default wait point is AFTER_SYNC. If no replica acks within rpl_semi_sync_source_timeout (default 10,000 ms), MySQL silently falls back to async. So the trap is: during a replica outage you think you have zero data loss, but you don't. Monitor the semi-sync status variable and alert when it flips.

A user edits their profile, refreshes, and sees the old one. Why, and how do you fix it? medium

Show answer

The write went to the leader; the refresh read hit an async follower that had not caught up. That breaks read-your-writes. Fixes: (1) read the user's own profile from the leader for a short window, say 60 seconds after any write, tracked in a cookie or session; (2) record the leader's log position after the write and only read from a follower that has applied it; (3) route that user's reads to the leader always if the data is small. Even Aurora's "usually much less than 100 ms" lag is enough to cause this on a fast reload.

What is a monotonic reads violation? Give an example and a fix. medium

Show answer

The user sees newer data, then older data, as if time went backwards. Example: a comment appears on the first refresh (follower A is up to date), then vanishes on the second (follower B is behind). Fix: pin each user to one replica, for example by hash(user_id) mod replicas, so successive reads never jump to a more stale copy. If that replica dies, re-pin and accept one possible jump. This is weaker than read-your-writes and cheaper: it doesn't need the leader at all.

Explain N, R, W. Why R + W > N? medium

Show answer

N is how many replicas store each key, W is how many must ack a write, R is how many must answer a read. If R + W > N, any read set and any write set share at least one replica, so the read sees the latest acknowledged write and keeps the newest version. Dynamo's common setting is (3,2,2): tolerate 1 failure on both paths. Tuning: (3,1,3) for read-heavy, (3,3,1) for write-heavy, (3,1,1) for speed with only eventual consistency. Follow-up: "Is that linearizable?" No: concurrent writes, sloppy quorums and partly failed writes still allow stale reads.

What are sloppy quorum and hinted handoff? What do you lose? hard

Show answer

With a strict quorum, if 2 of the 3 home replicas are down, W = 2 fails. A sloppy quorum instead writes to "the first N healthy nodes from the preference list" (Dynamo §4.6), even if they are not the key's home. The stand-in keeps a hint naming the real owner and hands the data back when it recovers: hinted handoff. You gain write availability during failures. You lose the overlap promise: a read of the home replicas may miss the write until handoff finishes. It is a deliberate choice of availability over consistency.

How do replicas find which data differs without sending everything? medium

Show answer

Merkle trees. Each replica splits its key range into buckets, hashes each bucket, then hashes pairs of hashes up to a single root. Two replicas compare roots. Equal: done, one hash sent. Different: compare children, and walk down only the branches that differ. Cost is about log of the bucket count in round trips, and only differing buckets are shipped. Dynamo uses this for "anti-entropy" to fix permanent divergence; read repair fixes keys that are read, and Merkle trees catch keys that are rarely read.

How does split brain happen, and how do you prevent it? hard

Show answer

A network cut hides the leader from the rest. They elect a new leader, but the old one is alive and still accepts writes from clients on its side. Now two leaders write and the data forks. Prevention: (1) majority quorum: lead only while you can reach more than half the voters, so with 5 voters only one side can have 3; (2) a term or epoch number that grows with each election, and replicas reject older terms; (3) fencing: revoke the old leader's storage access or power it off; (4) odd voter counts. Raft combines (1) and (2).

Range vs hash sharding? easy

Show answer

Range: each shard owns a span of key values. Good for range scans like "orders in March" because they hit one shard. Bad when keys grow over time, like timestamps or auto-increment IDs: all new writes hit the last shard. Hash: hash(key) picks the shard. Even spread, but a range scan must ask every shard. MongoDB supports both; Cassandra and DynamoDB hash the partition key. Middle ground: compound key such as (hash(user_id), timestamp): hash spreads users, range keeps one user's history together.

How would you choose a shard key for a chat app's messages? medium

Show answer

The main query is "latest messages in channel X". So shard by channel_id and sort by message time inside the shard. One channel's messages stay together and one query hits one shard. Risk: a huge channel is a hot partition and grows without limit. Fix: bucket by time, key = (channel_id, time_bucket), say one bucket per 10 days, so partitions stay bounded. Discord's blog describes exactly this kind of hot partition in Cassandra. Avoid message_id alone: reading a channel would hit every shard.

One celebrity's post gets millions of likes per minute. One partition melts. Fix it. hard

Show answer

The key is fine on average; one value is hot. Options: (1) write sharding: add a suffix 0 to 9 to the key so writes spread across 10 partitions, and sum them when reading (AWS recommends this for DynamoDB); (2) batch counts in memory or Redis and flush every second; (3) cache the read side in a CDN or Redis; (4) for feeds, don't fan out celebrity posts on write, pull them at read time. Number to cite: a DynamoDB partition caps at 1,000 write units per second, so 10 suffixes gives about 10,000.

Why is hash(key) mod N bad when you add servers? How many keys move from 3 to 4? medium

Show answer

Changing N changes the answer for most keys. A key stays only if h mod 3 == h mod 4. Over one cycle of 12 values, only 0, 1, 2 match, so 75% of keys move: huge network traffic and cache misses during the move. Consistent hashing moves only about 1/n of keys, around 25% here, and only from neighbours of the new node. Alternative used in practice: create many fixed slices up front (say 1,024) and only move whole slices between machines.

What are virtual nodes and why use them? medium

Show answer

Each physical server takes many points on the hash ring instead of one. Benefits: (1) even load, because many random arcs average out; (2) when a server dies, its arcs are spread over many servers, not dumped on one neighbour; (3) a bigger machine can get more points. Dynamo introduced the term; Cassandra calls them tokens and ships num_tokens: 16 in its 4.0 yaml, down from 256. Cost: more metadata, and with too many tokens, repair and streaming touch more peers.

Your table is sharded by user_id. How do you query by email? hard

Show answer

Two ways. Local index: each shard indexes its own rows; a query asks every shard and merges (scatter-gather). Writes are cheap and consistent; reads cost N shards and tail latency is set by the slowest. Global index: a separate table sharded by email that maps email to user_id. One lookup plus one shard read, but every write updates two shards, usually async, so it can lag. DynamoDB GSIs are "eventual consistency only". For login by email, I'd pick a global index and handle a "not found yet" retry on signup.

How do you handle a join or transaction across shards? hard

Show answer

First, avoid it: co-locate related data with the same shard key, such as orders and order_items both by customer_id. If unavoidable: for reads, fetch from each shard and join in the app or router (Vitess can do some of this). For writes, use two-phase commit if the store supports it, knowing it blocks if the coordinator dies, or a saga: a chain of local transactions with compensating steps. For analytics, copy data into a warehouse and join there.

Multi-leader: two regions edit the same row at once. What do you do? hard

Show answer

Options: (1) avoid it: route all writes for one record to its "home" region; (2) last write wins by timestamp: simple, but it silently drops one write and clock skew can drop the newer one; (3) keep both versions with version vectors and merge in the app, as Dynamo does with its shopping cart; (4) CRDTs: counters, sets and text types that merge the same way everywhere. I'd pick home-region routing for business data and CRDTs for collaborative features.

Design the storage for a URL shortener with 10 billion links. design

Show answer

Main query: short code to long URL, a key lookup. Shard by hash(short_code) for even load; no range scans needed. Size: 10 billion times about 500 bytes is about 5 TB, plus 3 copies is 15 TB, so roughly 16 to 32 shards of a few hundred GB each. Each shard is a replica set, or use a leaderless store like DynamoDB or Cassandra with RF 3. Reads dominate, so put a cache in front; popular links become hot keys and the cache absorbs them. Use consistent hashing or many fixed slices so adding shards moves little data.

How would you reshard a live MySQL from 4 to 8 shards with no downtime? design

Show answer

Split each shard in two. Steps: (1) create 8 new shards; (2) bulk copy rows by key range; (3) keep copying new changes by reading the binlog (change data capture) until the new shards are seconds behind; (4) verify row counts and checksums; (5) switch reads to the new shards; (6) briefly stop writes, let the last changes drain, switch writes; (7) keep the old shards for rollback. Vitess automates this with its Reshard VReplication workflow. Key ranges like -80 become -40 and 40-80, so each split is local.

—Cheat sheet

Numbers and facts to remember memorise

Fact	Value	Source
Quorum overlap rule	R + W > N	Dynamo §4.5
Common Dynamo setting	(N, R, W) = (3, 2, 2)	Dynamo §6
Majority of n voters	n/2 + 1 (3 of 5)	Cassandra QUORUM doc
Keys moved, mod N, 3 to 4 nodes	75%	Arithmetic on this page
Keys moved, consistent hashing	about 1/n	Karger 1997 via Wikipedia
DynamoDB per-partition limit	3,000 RCU, 1,000 WCU per second	AWS docs
DynamoDB index quotas	5 LSI, 20 GSI (default)	AWS quotas, checked 2026-10-25
DynamoDB LSI item collection	10 GB per partition key value	AWS docs
Cassandra default vnodes	`num_tokens: 16` (was 256)	Cassandra 4.0 NEWS
MongoDB default range size	128 MB	MongoDB docs
MySQL semi-sync timeout	10000 ms, then async	MySQL 8.4 docs
Aurora replica lag	"usually much less than 100 ms"	AWS Aurora docs

—Sources

All checked 2026-10-25 references

What	Where
Dynamo paper (DeCandia et al., SOSP 2007)	allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf
Session guarantees (Terry et al., 1994)	bayou-sessions94.pdf
Eventually Consistent (Vogels, 2008)	allthingsdistributed.com
Consistent hashing (cites Karger et al. 1997)	en.wikipedia.org/wiki/Consistent_hashing
MySQL 8.4 semi-sync replication	dev.mysql.com
MySQL 8.4 source options	dev.mysql.com
PostgreSQL streaming replication	postgresql.org
PostgreSQL synchronous_commit	postgresql.org
PostgreSQL synchronous_standby_names	postgresql.org
AWS RDS read replicas	docs.aws.amazon.com
AWS Aurora replication	docs.aws.amazon.com
DynamoDB partition key design	docs.aws.amazon.com
DynamoDB write sharding	docs.aws.amazon.com
DynamoDB adaptive capacity	docs.aws.amazon.com
DynamoDB secondary indexes, LSI, quotas	SecondaryIndexes, LSI, ServiceQuotas
Cassandra architecture (Dynamo), cassandra.yaml, 2i	dynamo.html, cass_yaml_file, 2i-concepts
Cassandra 4.0 NEWS (num_tokens 256 to 16)	NEWS.txt
MongoDB sharding, ranges and balancer	sharding, data partitioning
Vitess vindexes, shards, Reshard	vindexes, shard, reshard
Discord hot partitions (2023)	discord.com/blog
Raft paper (terms, majority)	raft.github.io/raft.pdf