3.1 Distributed Consensus Algorithm: Paxos

1. Basic Paxos

1.1. What Is Basic Paxos?

• Abbreviated as Paxos.
• A distributed consensus algorithm invented by Lamport and the foundation of Raft and ZAB.

1.2. Basic Paxos Algorithm Process

1.2.1. Roles

• client: request initiator. Not important here.
• proposer: proposal proposer. Similar to a coordinator.
• acceptor: proposal voter. Similar to a participant.
• learner: proposal learner. Not important here.

1.2.2. Two Phases

1.2.2.1. Prepare Phase

• The proposer puts forward a proposal numbered N and sends it to all acceptors.
• After each acceptor receives the number, it compares it with its saved maximum number maxN.
  • If N < maxN, reject it.
  • If N > maxN, update maxN to N and return (acceptorId, maxN, proposal content) to the proposer.

1.2.2.2. Accept Phase

• If proposal N receives responses from half of the acceptors during the prepare phase, the proposer sends the actual proposal content to the acceptors.
• After an acceptor receives the proposal, it checks whether the proposal number is greater than its own. If yes, it returns ok; otherwise, it rejects it.
• After the proposer receives confirmations from half of the acceptors, it succeeds; otherwise, it increments the proposal number and continues with the prepare phase.

1.2.3. Example

• Suppose there are three proposers and three acceptors. The leader-election phase is as follows:

1.3. Problems with Basic Paxos

1.3.1. Livelock

• Basic Paxos is a continuously looping 2PC. Therefore, if multiple clients write to multiple machines and every machine is a Proposer, concurrent conflicts will be frequent. In other words, each node may need to execute multiple loops before one log entry can be determined.

1.3.2. Performance

• Confirming one log entry requires at least two RTTs + two disk writes (one for the Prepare broadcast and reply, and one for the Accept broadcast and reply).

2. Multi Paxos

2.1. What Is Multi Paxos?

• It introduces the concept of a Leader, and all requests go through that Leader.

2.2. Why Is Multi Paxos Needed?

• It solves the livelock and performance problems of Basic Paxos.
  • Livelock: change multiple writers into a single writer. Elect one Leader and allow only the Leader to act as the Proposer. When other machines receive write requests, they forward the requests to the Leader; alternatively, clients send all write requests to the Leader.
  • Performance: change multiple writers into a single writer by electing one Leader.

3. Fast Paxos

4. References

• Paxos | The Fenix Project
• Multi Paxos | The Fenix Project
• Software Architecture Design: Integrating Large-Scale Website Technical Architecture and Business Architecture - Yu Chunlong - WeRead