Replication

One replica (the leader) accepts all writes and streams them, in order, to read-only followers.

There is a single order of writes, so there are no write conflicts. The cost is that every write goes through one node, and reads from followers may be out of date.

The leader confirms a write to the client only after a follower has also confirmed it.

An acknowledged write survives the loss of the leader. But one slow or failed follower blocks every write, so a fully synchronous setup is fragile.

One follower is synchronous and the rest are asynchronous. If the synchronous one becomes slow, an asynchronous follower takes its place.

This guarantees an up-to-date copy on at least two nodes without letting a single straggler stop all writes.

The leader acknowledges a write as soon as it is stored locally and sends it to followers in the background.

Writes are fast and keep working when followers fail. However, writes that were acknowledged but not yet replicated are lost if the leader dies.

The stream of changes a leader sends to its followers. It can be statement-based, write-ahead-log shipping, a logical (row-based) log, or trigger-based.

Replicating statements breaks on nondeterminism (NOW(), RAND()). Shipping the WAL ties followers to the leader's storage format. A logical row log is decoupled from the storage engine and can feed change data capture.

A follower that restarts or falls behind asks the leader for every change after the last log position it processed.

Because the log has positions, a follower that was down can recover without a full copy. New followers start from a consistent snapshot and then catch up the same way.

When the leader fails, the system detects it (usually with a timeout), promotes the most up-to-date follower, and redirects clients and other followers to it.

If the timeout is too short, the system fails over when nothing is wrong. If it is too long, recovery is slow. With async replication, writes the old leader had not replicated are thrown away.

Two nodes both believe they are the leader and both accept writes.

Their data diverges and there is no automatic way to reconcile it. Systems use fencing (STONITH, epoch numbers) to shut down or reject the deposed leader.

The delay between a write on the leader and that write appearing on a follower. In normal operation it is under a second, but under load or during failures it can be minutes.

Asynchronous followers converge only eventually, and the delay has no upper bound. Applications that read from followers have to decide which anomalies they can tolerate.

A user always sees their own updates after a page reload. Other users' updates may still be delayed.

Without it, a user who has just posted something reloads the page and the post seems to be gone. Fixes include reading recently modified data from the leader, or tracking the user's last write position and serving reads only from replicas that have caught up to it.

If a user has read a value, later reads never return an older one.

Reads that hit a fresh replica and then a stale one make time appear to move backwards. Pinning each user to one replica (for example by a hash of the user ID) prevents this.

Anyone reading a sequence of writes sees them in the order they happened.

In a partitioned database, partitions replicate independently, so an answer can show up before its question. Putting causally related writes in the same partition, or tracking their dependencies, fixes it.

Several nodes accept writes (for example one leader per datacenter) and exchange their changes asynchronously.

Writes are local in each datacenter and the system survives a datacenter or network outage. In exchange, the same record can be changed concurrently in two places, and those conflicts have to be resolved.

A way to make every replica reach the same final value after concurrent writes: last write wins, replica priority, merging values, or keeping all versions for the application or user to resolve.

If each replica simply applies writes in the order they arrive, replicas end up permanently different. Any automatic rule has to be deterministic so that all replicas reach the same result.

Each write carries a timestamp, the highest one is kept, and the others are silently discarded.

Replicas converge, but at the cost of durability: concurrent writes are lost, and with clock skew even a write that really happened later can lose.

The client (or a coordinator) sends every write and every read to several replicas in parallel. No node is in charge of ordering writes.

There is no failover, and a few slow or dead nodes are tolerated. Stale replicas are repaired by readers and by background processes.

With n replicas, a write must be confirmed by w of them and a read must query r of them. If w + r > n, every read set overlaps every write set.

Overlap means at least one queried replica has the latest successful write. There are still edge cases: sloppy quorums, concurrent writes, failed writes that are not rolled back, and a node restored from a stale replica.

Read repair: a client that sees a stale response writes the newer value back to that replica. Anti-entropy: a background process compares replicas and copies the missing data.

Read repair only fixes values that get read. Without anti-entropy, rarely read keys can stay stale on some replicas indefinitely.

When a key's home nodes are unreachable, writes are accepted by other nodes. Those nodes hand the data back to the home nodes once they recover.

Writes stay available during network problems, but w + r > n no longer guarantees a fresh read, because the w writes may land outside the n home nodes.

Operation B happens after A if B knew about A, depended on it, or built on it. If neither knew about the other, the two are concurrent, whatever their wall-clock times.

When one operation happened before the other, the later one may overwrite the earlier. When they are concurrent, there is a real conflict and both values have to be kept or merged.

One version counter per replica, sent with every read and write. The server overwrites the values a write has seen and keeps concurrent values as siblings.

This tells overwrites apart from concurrent writes without depending on clocks, so no data is silently dropped. The application merges siblings, for example by taking the union of shopping carts (deletions need tombstones).