Replication, quorum, and consistency - the distributed storage discipline

Distributed storage replicates data across nodes and maintains consistency through quorum. This lesson covers the discipline.

Replication factor

Replication factor (RF) is the number of copies of each piece of data:

• RF=1: no replication. Single point of failure.
• RF=2: one primary, one replica. Tolerates one failure.
• RF=3: two replicas. Tolerates two failures. Standard for production.

Higher RF: more reliability, more storage cost.

Write quorum and read quorum

For a write to be acknowledged, it must be written to a write quorum (Wq) of nodes. For a read to be considered current, it must be read from a read quorum (Rq) of nodes.

Strong consistency: Wq + Rq > N (e.g. Wq=2, Rq=2, N=3).

For RF=3:

• Wq=2, Rq=2: strong consistency. Reads always see the latest write.
• Wq=1, Rq=1: weak consistency. Reads may see stale data.

For most production: Wq=2, Rq=2 (or Wq=3, Rq=1 for read-heavy).

Sync vs async replication

• Sync: write is acknowledged only after all replicas confirm. High latency, strong consistency.
• Async: write is acknowledged immediately, replicas catch up. Low latency, eventual consistency.

For RF=3, sync replication means the write is acked after 2 of 3 replicas confirm. The third catches up later.

CAP theorem

CAP says you can have at most two of:

• Consistency: all nodes see the same data at the same time.
• Availability: every request gets a response.
• Partition tolerance: the system continues despite network partitions.

In practice, partition tolerance is required (networks fail). So the choice is between consistency and availability. Most distributed systems choose availability (eventual consistency).

Quorum and split brain

A partition splits the cluster. Each side has some nodes. For a write to be acknowledged, a quorum must be reached:

• 3 nodes, RF=3, Wq=2: 2 nodes on one side, 1 on the other. The side with 2 has quorum. The side with 1 does not.
• The minority cannot write. Reads may be stale or refused.

Quorum prevents split brain. The minority cannot make decisions.

Erasure coding

Replication is expensive (3x for RF=3). Erasure coding is a more efficient alternative:

• Split data into k data fragments.
• Generate m parity fragments.
• Total: k + m fragments.
• Can recover from up to m lost fragments.

For k=4, m=2: 6 fragments total, can recover from 2 lost. Storage efficiency: 4/6 = 67% (vs 33% for RF=3).

Ceph supports erasure coding. For cold data, EC is significantly cheaper.

Knowledge check