Consensus
Raft, Paxos and how replicas agree on one order.
All topics · 2 lessons · 27 resources
Learn Consensus on System Design Atlas
- 01Consensus: Raft and PaxosHow a group of machines agrees on one order of operations even when some crash or messages are delayed, and why a majority is the magic number.Advanced Distributed Systems · 12 min read · start here
- 02Distributed locks and leader electionMaking sure only one worker does a job at a time, and why a lock needs a lease and a fencing token to be safe.Core Concepts: How Things Actually Work · 9 min read
Related topics
These share a lesson with Consensus.
Curated Consensus resources
GitHub
- Apache ZooKeeperThe source of the coordination service.GitHub
- Awesome Distributed SystemsA curated list of distributed-systems papers, books, talks and courses.GitHub
- CockroachDBA distributed SQL database built on ranges, Raft and MVCC.GitHub
- etcd Raft libraryThe production Raft implementation used by etcd, Kubernetes and others.CNCF / etcd
- HashiCorp RaftA Go implementation of Raft used by Consul and Vault.GitHub
- TiDBA distributed SQL database with a Raft-based storage layer.GitHub
Case Studies
- Building and Deploying MySQL Raft at MetaWe’re rolling out MySQL Raft with the aim to eventually replace our current MySQL semisynchronous databases. The biggest win of MySQL Raft was simplification of the operation and making MyS…Meta
- How Ringpop from Uber Engineering Helps Distribute Your ApplicationA library that uses gossip and consistent hashing to share work between application instances without a central coordinator.Uber
- ZippyDB: Facebook's key-value storeFacebook's strongly consistent key-value store built on RocksDB and Paxos, with data sharded and replicated.Meta
Blogs
- Cockroach Labs BlogDistributed SQL internals: consensus, transactions and multi-region design.Cockroach Labs
- Distributed systems theory for the distributed systems engineerA reading guide to the theory that matters for building distributed systems: failure, time, consensus.The Paper Trail
- Google SRE Book: Distributed Periodic Scheduling with CronRunning scheduled jobs reliably across machines: leader election, state in a replicated store and avoiding duplicate runs.Google
- Google SRE Book: Managing Critical State (Distributed Consensus)Why systems with critical state use consensus, and how the CAP trade-off plays out in practice.Google
- How to do distributed lockingWhy a lock without fencing tokens is unsafe, with a critique of the Redlock approach.martin.kleppmann.com
- Patterns of Distributed SystemsA catalogue of named building blocks (replicated log, lease, quorum, gossip, high-water mark) found in systems like Kafka and Cassandra.Martin Fowler
- Paxos Made Live – An Engineering PerspectiveGoogle's paper on the engineering challenges of building a fault-tolerant database on the Paxos consensus algorithm, and how the authors solved them.Google
Books
Documentation
- etcd DocumentationThe Raft-based key-value store behind Kubernetes: concepts, API and operations.CNCF / etcd
- The Raft Consensus Algorithm (site and visualisation)An interactive animation of Raft plus links to the paper, talks and implementations. The quickest way to see elections and replication happen.raft.github.io
Papers
- In Search of an Understandable Consensus Algorithm (Raft paper)The Raft paper: leader election, log replication and safety explained so that engineers can implement them.Stanford University
- Megastore: Providing Scalable, Highly Available Storage (paper)Synchronous replication across data centres with Paxos while keeping a transactional data model.Google
- Paxos Made Simple (paper)A short, plain-language account of the Paxos protocol for reaching agreement among unreliable machines.Microsoft Research
- Spanner: Google's Globally Distributed Database (paper)A globally distributed database that gives strongly consistent transactions by combining consensus groups with clocks whose uncertainty is bounded.Google
- The Byzantine Generals Problem (paper)The classic account of agreement when some participants may lie or fail arbitrarily.Microsoft Research
- The Chubby Lock Service (paper)A coarse-grained lock and small-file service built on consensus, used for leader election and configuration; the idea behind ZooKeeper and etcd.Google
- ZooKeeper: Wait-free Coordination for Internet-scale Systems (paper)The coordination service used for configuration, leader election and locking, and its API of simple wait-free primitives.Yahoo! Research