Paxos, Raft, EPaxos: How Has Distributed Consensus Technology Evolved?

What Is Distributed Consensus?

Distributed consensus, in short, is to make all processes in a system to agree on a single value after one or more processes propose this value.

Paxos

As one of the main algorithms in distributed consensus, Paxos requires at least two phases to reach an agreement: the preparation phase (the request to prepare) and the acceptance phase (the request to accept).

  • Learn the values that have been proposed.

Multi-Paxos

The basic Paxos algorithm requires at least two network trips to reach a resolution. In the case of concurrency, the algorithm might need more. In extreme cases, it might even produce a livelock, which is inefficient. To address this issue, Multi-Paxos was proposed.

Raft

Unlike Paxos, which is derived directly from the distributed consensus problem, Raft is proposed from the multi-replicated state machine. It uses stronger assumptions to reduce the states to be considered, making it easy to understand and implement.

  • The term of Raft is essentially the proposal ID of Multi-Paxos.
  • The log entry of Raft is the proposal of Multi-Paxos.
  • The log index of Raft is the instance ID of Multi-Paxos.
  • The leader election of Raft is essentially the preparation phase of Multi-Paxos.
  • The log replication of Raft is the acceptance phase of Multi-Paxos.
  • Leader Stickiness: The follower with the unexpired Leader Lease rejects the new leader election request.

EPaxos

Egalitarian Paxos (EPaxos) was put forward by SOSP’13 and come out earlier than Raft. However, when Raft was popular in the industry, no one noticed EPaxos for a long time until recently.

Comparative Analysis

From Paxos to Raft and then to EPaxos, a comparison among the algorithms can be conducted to present the evolution. The following section mainly compares and analyzes the algorithms in terms of understandability, efficiency, availability, and applicable scenarios.

1. Understandability

As we all know, Paxos is notoriously obscure. It is not only difficult to understand, but also difficult to implement. On the other hand, Raft, however, aims at improved understandability and easy implementation. It greatly reduces the threshold of using distributed consensus and makes distributed consensus more popular. After Raft was proposed, it quickly gained popularity and greatly promoted the engineering application of distributed consensus.

2. Efficiency

Has any efficiency improvement been achieved from Paxos to Raft and then to EPaxos? The following sections compare Multi-Paxos, Raft, and EPaxos in terms of load balancing performance, message complexity, pipelining, and concurrent processing.

3. Availability

Any replica in EPaxos can provide services. When a replica becomes unavailable, the service can be immediately switched to another replica, with a minor impact on availability. However, Multi-Paxos and Raft depend on the leader. If the leader becomes unavailable, leader reelection is required. As a result, the service is unavailable until a new leader is elected. Obviously, EPaxos has better availability than Multi-Paxos and Raft. Between Multi-Paxos and Raft, which has better availability than the other?

4. Application Scenarios

EPaxos is more applicable to cross-AZ and cross-region scenarios. In scenarios with demanding usability requirements, the leader is prone to creating a bottleneck. Multi-Paxos and Raft have similar application scenarios, such as the internal network. For general high-availability scenarios, the leader is less prone to creating a bottleneck.

Original Source:

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store