Replication

Wikipedia · Cambridge Distributed Systems · Replication

Copy data to multiple nodes for fault tolerance and lower latency. The hard part is keeping copies consistent. Three architectures: leader/follower, multi-leader, leaderless. The quorum condition R + W > N guarantees you read at least one up-to-date copy.

Why replicate

Single copies are single points of failure. Replication buys you: (1) fault tolerance: if a node dies, others have the data; (2) lower latency: serve reads from the nearest copy; (3) higher throughput: spread read load across replicas. The cost is consistency: when one copy is updated, others lag behind.

Leader/follower (primary/backup)

One node is the leader. All writes go to the leader. The leader replicates to followers. Reads can go to any replica (but might be stale). If the leader dies, a follower must be promoted. Simple, but the leader is a bottleneck and a single point of failure for writes.

Scheme

; Leader/follower replication.
; Leader accepts writes, replicates to followers.

(define leader-data 0)
(define follower-1 0)
(define follower-2 0)

(define (write-to-leader value)
  (set! leader-data value)
  ; replicate to followers (synchronous)
  (set! follower-1 value)
  (set! follower-2 value)
  (display "Wrote ") (display value) (display " to leader + 2 followers")
  (newline))

(define (read-from node)
  (cond
    ((equal? node "leader") leader-data)
    ((equal? node "follower-1") follower-1)
    ((equal? node "follower-2") follower-2)))

(write-to-leader 42)
(display "Read from leader: ") (display (read-from "leader")) (newline)
(display "Read from follower-1: ") (display (read-from "follower-1")) (newline)
(display "Read from follower-2: ") (display (read-from "follower-2"))

Quorum reads and writes

In a leaderless system with N replicas, write to W nodes and read from R nodes. If R + W > N, at least one node in every read set has the latest write. This is the quorum condition. With N=3, R=2, W=2: every read overlaps every write.

Scheme

; Quorum condition: R + W > N
; With N=3, which R, W pairs guarantee consistency?

(define N 3)

(define (quorum? R W)
  (> (+ R W) N))

(display "N = ") (display N) (newline)
(display "R=1, W=1: ") (display (quorum? 1 1)) (newline)  ; no
(display "R=1, W=2: ") (display (quorum? 1 2)) (newline)  ; no
(display "R=1, W=3: ") (display (quorum? 1 3)) (newline)  ; yes
(display "R=2, W=2: ") (display (quorum? 2 2)) (newline)  ; yes
(display "R=3, W=1: ") (display (quorum? 3 1)) (newline)  ; yes
(display "R=2, W=1: ") (display (quorum? 2 1))            ; no

Consistency models

Strong consistency: every read sees the most recent write. Requires coordination (slow). Eventual consistency: replicas converge eventually, but reads may be stale. Causal consistency: if A caused B, everyone sees A before B, but concurrent events may appear in any order. Stronger is safer, weaker is faster.

Scheme

; Consistency models as guarantees about read results.

(define (strong-consistency writes reads)
  ; Every read returns the last write
  (display "Strong: every read sees latest write") (newline)
  (display "Read returns: ") (display (car (reverse writes))))

(define (eventual-consistency writes reads)
  ; Eventually all reads return the last write
  (display "Eventual: reads may be stale for a while") (newline)
  (display "Read might return: ") (display (car writes))  ; old value
  (display " (will converge to ")
  (display (car (reverse writes))) (display ")"))

(strong-consistency (list 1 2 3) "any-read")
(newline)
(eventual-consistency (list 1 2 3) "any-read")

Neighbors

Cross-references

🌐 Ch.7 CAP Theorem — the fundamental tradeoff between consistency and availability
🌐 Ch.10 CRDTs — eventual consistency without coordination
june.kim/caches-all-the-way-down — replication as caching: every replica is a cache of the leader's state

← Time and Clocks by june.kim Consensus →