6. Replication

"The major difference between a thing that might go wrong and a thing that cannot possibly go wrong is that when a thing that cannot possibly go wrong goes wrong, it usually turns out to be impossible to get at or repair." — Douglas Adams

Replication = keeping a copy of the same data on multiple machines connected via a network.

Why:

• Latency — keep data geographically close to users
• Availability & durability — keep working even if parts have failed
• Read throughput — scale out the number of machines serving read queries

If the data doesn't change, replication is easy — copy it once and you're done. ALL the difficulty lies in handling CHANGES to replicated data.

Assumption for this chapter: the dataset is small enough that each machine holds a copy of the entire dataset. Ch 7 relaxes this (sharding).

Three families of algorithms — almost all distributed databases use one of these three:

   SINGLE-LEADER              MULTI-LEADER                 LEADERLESS
   ─────────────              ────────────                 ──────────
   client ──▶ [L]             client ──▶ [L₁]  [L₂] ◀── client    client ──▶ [R] [R] [R]
               │ │ │                     ╲    ╱                            ◀──  parallel
               ▼ ▼ ▼                      ╲  ╱                             writes AND reads
              [F][F][F]                    ╳                               to several nodes
                                          ╱  ╲
   ONE node orders writes    each leader also acts as     NO leader; no ordering
   followers apply in the    a FOLLOWER to the others     imposed; clients detect
   SAME order                                              and correct stale nodes

The principles haven't changed much since the 1970s, because the fundamental constraints of networks have remained the same. Nevertheless, concepts such as eventual consistency still cause confusion.