Consensus Protocols

tags : Two Phase Locking (2PL) & Two Phase Commit (2PC), Distributed Systems, Concurrency Consistency Models, Data Replication, Eventual Consistency, Zookeeper, Data Replication

OG Blogposts - https://medium.com/@adamprout/categorizing-how-distributed-databases-utilize-consensus-algorithms-492c8ff9e916 🌟 - Consensus Resources - Durability and the Art of Consensus by Joran Dirk Greef - YouTube

“making sure participants come to the same conclusion about something and nobody has the wrong answer”

FAQ §

Partial Quorum §

Consensus is NOT for Scaling §

The way that horizontally scaling databases like Cockroach or Yugabyte or Spanner work is by sharding the data, transparent to the client. Within each shard data is replicated with a dedicated distributed consensus cluster.

So, yes, distributed consensus can be a part of horizontal scaling. But again what distributed consensus primarily solves is high availability via replication while remaining linearizable.

This is not a trivial point to make. etcd, consul, and rqlite are examples of databases that do not do sharding, only replication, via a single Raft cluster that replicates all data for the entire system.

For these databases there is no horizontal scaling. If they support “horizontal scaling”, they support this by doing non-linearizable (stale) reads. Writes remain a challenge.

• consensus is not for scaling
• consensus impedes scaling
• An intuition for distributed consensus in OLTP systems | notes.eatonphil.com

Approaches §

Paxos §

Variants §

• Replicated State Machine (RSM)

  See Local First Software (LoFi)

• chain replication type advanced atomic storage protocols

Raft §

See Raft

Viewstamped Replication Protocol §

VR vs Raft §

• Viewstamped Replication relies on Message Passing, while RAFT relies on RPC
• “VSR is also described in terms of message passing, whereas Raft took VSR’s original message passing and coupled it to RPC—shutting out things like multipath routing and leaving the logical networking protocol misaligned to the underlying physical network fault model.” - Joran
• Comparing the 2012 VSR and 2014 Raft papers, they are remarkably similar.
• VSR better in prod than raft (opinion)
  • It’s all the little things. All the quality, clear thinking and crisp terminology coming from Liskov, Oki and Cowling.
  • Oki’s VSR was literally the first to pioneer consensus in ‘88, so it’s well aged, and the ‘12 revision again by Liskov and Cowling is a great vintage!

Resources §

• Paper: VR Revisited - An analysis with TLA+ — Jack Vanlightly
• Viewstamped Replication explained
• https://github.com/tigerbeetle/viewstamped-replication-made-famous
• Implementing Viewstamped Replication protocol – Distributed Computing Musings
• Paper #74. Viewstamped Replication Revisited - YouTube

Election §

Links §

• https://github.com/kellabyte/holocron