Paxos

Paxos 是一个分布式系统共识算法，由 Leslie Lamport 在1990年代提出。它被设计用来处理分布式系统中的一致性问题，确保在一个包含多个节点的网络中，即使部分节点发生故障或者网络出现问题，系统仍能达成一致和正确的决定。Paxos 主要用于日志复制或系统状态的一致性维护，是构建可靠分布式系统的基础算法之一。

Paxos 的基本概念

Paxos 算法主要分为三种角色：

1. Proposer（提议者）：提议某个值应该被系统的所有成员接受。
2. Acceptor（接受者）：接受提议者提出的值。这些节点对提议值进行投票，决定是否接受该值。
3. Learner（学习者）：学习已被多数接受者接受的值，并最终从接受者那里学到系统的决定结果。

Paxos 的工作流程

Paxos 的执行可以分为两个主要阶段：

1. 准备阶段（Prepare phase）：

   • Proposer 选择一个提案编号（必须唯一且递增），然后向 Acceptor 发送一个包含这个编号的准备请求（Prepare request）。
   • Acceptor 收到准备请求后，如果该请求的编号高于它之前响应的任何请求的编号，它将承诺不再接受编号小于此编号的任何其他提议。同时，Acceptor 将告诉 Proposer 它已经接受的最高编号提议的值（如果有的话）。

2. 接受阶段（Accept phase）：

   • Proposer 在第一阶段结束后，根据 Acceptor 返回的信息决定提议的值。如果多数 Acceptor 返回了之前接受的值，Proposer 应当提议其中编号最高的那个值；如果没有 Acceptor 返回之前接受的值，Proposer 可以自由决定提议的值。
   • 然后，Proposer 向所有 Acceptor 发送接受请求（Accept request），包含提案编号和提议的值。
   • Acceptor 收到接受请求后，只有在它仍然承诺接受这个编号（即没有承诺过更高编号的提案）的情况下，才会接受这个提案。

Paxos 的特点和挑战

• 可靠性：即使有节点失败，只要大多数节点正常工作，系统仍然可以达成一致。
• 活锁：Paxos 算法可能会因为多个 Proposer 同时试图完成各自的提议而导致活锁，这需要通过算法或实现中的优化来解决。
• 效率：标准 Paxos 的效率并不高，尤其是在有多个竞争 Proposer 的情况下。为了提高效率，通常会实现多种优化版本的 Paxos，如 Multi-Paxos。

Paxos 是理解和实现分布式一致性问题的一个重要基石，尽管它的复杂性使得实际的工程应用需要仔细的设计和实现。

Raft

Raft 是一种为了更易于理解而设计的分布式一致性协议，它于 2013 年由 Diego Ongaro 和 John Ousterhout 在 Stanford 大学提出。Raft 和 Paxos 一样，用于解决分布式系统中的一致性问题，尤其是日志复制。Raft 通过提供相对直观的结构，使其比 Paxos 更容易理解和实现。

Raft 的核心概念

Raft 将系统的所有成员分为三种角色：

1. Leader（领导者）：处理所有客户端交互，日志复制等任务。
2. Follower（追随者）：被动地响应来自领导者的请求。
3. Candidate（候选人）：用于选举新的领导者。

Raft 的工作流程

Raft 的操作可以分为几个主要部分：

1. 领导者选举

• 选举开始：当 Follower 在一定时间内未收到来自 Leader 的消息时（这个时间段称为选举超时），它会认为 Leader 已经失效，并将自己转变为 Candidate，开始新一轮的选举。
• 投票：Candidate 为自己投票，并向其他节点发送请求投票的请求。如果接收节点在此轮选举中尚未投票给其他节点，且 Candidate 的日志与其自己的日志一样新，它就会给该 Candidate 投票。
• 选举结果：如果 Candidate 收到了大多数节点的投票，它就变成了 Leader。

2. 日志复制

• 操作接收：Leader 接收来自客户端的操作请求，将操作作为新的日志条目追加到它的日志中。
• 日志复制：Leader 将这些日志条目并行发送到所有 Follower，并要求它们将这些条目写入其日志。
• 日志提交：当 Leader 确认一个日志条目已被大多数的 Follower 复制，该条目被提交，之后 Leader 将结果返回给客户端。同时，Leader 也负责通知 Follower 哪些条目是已提交的。

3. 安全性

• 条目匹配原则：Raft 通过确保所有复制的日志条目在不同服务器上的日志中具有相同的索引位置和任期号（Term），来保证一致性。
• 日志覆盖：如果两个日志在同一位置的条目冲突（即任期号不同），则需要删除这个位置及其后面的所有条目，并用新 Leader 的日志条目来替换。

Raft 的优点

• 可理解性：Raft 通过减少状态数量和明确化角色职责，提高了协议的易理解性。
• 安全性：确保了即使在领导者更换的不稳定时期内，也不会丢失已提交的日志条目。
• 效率：在常见情况下，一个客户端的请求只需要一次 Leader 和大多数 Follower 之间的交互。

Raft 因其简明的结构和强调易于实现的特性，在工业界和学术界都得到了广泛应用。它是构建可靠分布式系统的一个强有力的工具，广泛应用于各种分布式存储和服务中，如 etcd 和 Consul。

Paxos vs Raft

Paxos 和 Raft 在处理分布式系统共识的方法上有本质的不同，尤其是在领导者选举的过程中。Paxos 本身并不内置一个固定的领导者选举机制，而是更加专注于如何在多个提议者之间达成一致的值。

Paxos 中的领导者选举

在原始的 Paxos 协议中，并没有明确的“领导者选举”步骤。任何节点都可以作为提议者（Proposer），尝试发起提议并让接受者（Acceptor）接受其提议。这里的关键在于：

• 多个提议者：在实际应用中，多个提议者可能同时尝试提交提议，这可能会导致提议冲突和效率低下。
• 提议编号：每个提议都有一个独一无二的编号，接受者会根据收到的提议编号做出响应。接受者承诺仅响应编号最大的提议，并可能拒绝较小编号的提议。

因为 Paxos 没有固定的领导者机制，这可能导致提议频繁被覆盖，从而影响系统的效率和响应速度。为了解决这个问题，Multi-Paxos 引入了一个类似“领导者”的概念：

• 固定提议者：在 Multi-Paxos 中，一般会选举一个固定的提议者作为“领导者”，以减少提议的冲突和提高效率。
• 领导者选举：这种领导者选举通常是通过额外的协调机制来实现，比如使用另一个分布式协议或者额外的选举算法。

Raft 的简化

与 Paxos 相比，Raft 在设计上的一大简化是它将领导者选举作为协议的核心部分，简化了决策过程：

• 明确的角色分离：Raft 明确分为 Leader、Follower 和 Candidate，每种角色的职责和行为都非常清晰。
• 定期的领导者选举：Raft 通过定时器和选举超时来触发领导者选举，这保证了即使在领导者失败的情况下，系统也能迅速恢复并选举出新的领导者。
• 日志复制：Leader 在 Raft 中负责日志条目的复制和管理，这减少了协议运行中的冲突和不确定性。

结论

尽管 Paxos 在理论上非常优雅，它的实现和理解可能因为缺乏固定领导者和多个提议者同时活跃带来的复杂性而变得复杂。相比之下，Raft 通过引入固定的领导者和清晰的状态转换，使得协议的理解和实现更为直观和简单。这也是 Raft 被广泛采纳的原因之一。

Zab

Zab（ZooKeeper Atomic Broadcast）协议是一个为分布式协调服务 Apache ZooKeeper 特别设计的一致性协议。ZooKeeper 是一个广泛用于分布式系统中来维护配置信息、命名、提供分布式同步和提供组服务等功能的开源服务器。Zab 用于保证 ZooKeeper 中数据的一致性和可靠性。

Zab 的核心概念

Zab 主要用于管理 ZooKeeper 服务的复制状态机，确保所有 ZooKeeper 服务实例（称为服务器）在存在任意数量的故障时仍能正确、一致地处理客户端请求。Zab 通过以下几个关键概念来实现这一目标：

1. 事务日志：Zab 确保所有的更新（比如配置变更等）都以事务日志的形式广播给所有的服务器。
2. 领导者选举：Zab 在领导者崩溃或网络分区情况下实现自动领导者选举。所有更新都由领导者协调，这简化了一致性的保证。
3. 数据同步：新的或重新启动的服务器必须与领导者同步数据状态，只有在完成同步之后，服务器才能加入到集群中提供服务。

Zab 的工作流程

Zab 协议的执行可以分为两个主要阶段：

1. 发现阶段（Discovery Phase）

• 当集群需要选举新的领导者时（例如，因为当前领导者崩溃），这一阶段被触发。
• 服务器相互交换信息以确定最新的事务状态和选出一个具有最新状态的领导者。
• 领导者是那个具有系统中最高事务ID的服务器。

2. 同步阶段（Synchronization Phase）

• 一旦选出领导者，它会开始与集群中的其他服务器同步其状态。
• 这包括发送缺失的事务日志条目到其他服务器，以确保所有的服务器都有完整且一致的数据副本。
• 服务器在完全同步之后才能开始处理来自客户端的请求。

3. 广播阶段（Broadcast Phase）

• 一旦完成同步，领导者就开始从客户端接收新的事务请求并将这些请求作为新的日志条目广播给所有服务器。
• 事务只有在大多数服务器写入日志后才被认为是已提交的，从而确保了数据的一致性和持久性。

Zab 的特点和优势

• 容错性：通过在不同服务器之间复制数据和自动领导者选举，Zab 提高了系统的可靠性和容错性。
• 一致性：Zab 保证了即使在发生故障的情况下，所有服务器的数据状态也保持一致。
• 可用性：领导者选举和数据同步确保了服务的高可用性，即使在领导者故障后也能快速恢复。

Zab 协议是 ZooKeeper 的核心组成部分，使得 ZooKeeper 能够在分布式环境中提供高效、可靠的协调服务。

Paxos&Raft&Za VS 2PC&3PC

分布式共识算法

• Paxos、Raft、Zab：这些算法解决的是在分布式系统中多个节点如何就某个值（例如日志条目、系统状态等）达成一致的问题。这些算法的核心是确保系统的一致性和可靠性，即使在出现节点故障或网络分区的情况下也能保持系统的正常运作。它们通常用于分布式日志服务、分布式数据库的数据复制和分布式系统的状态同步等。

事务一致性算法

• 2PC和3PC：这些算法通常用于确保在执行跨多个数据库或系统的操作时保持事务的原子性。2PC和3PC尽管可以在分布式系统中实现节点之间的协调，但它们本质上依赖于一个协调者（通常是一个中心节点）来管理事务的提交或回滚，这使得它们在某种程度上带有“中心集权”的性质。
  • 2PC：涉及一个协调者和多个参与者。协调者先询问所有参与者是否可以提交事务，如果所有参与者都同意，则进行提交；如果任何一个参与者拒绝，整个事务将回滚。
  • 3PC：是2PC的改进版，添加了一个额外的预提交阶段来减少因协调者失败导致的挂起状态，提供更好的容错性。

应用场景和限制

• 分布式共识算法如Paxos和Raft在没有中央协调者的情况下通过节点间的通信达成一致，适用于需要高可用性和容错性的环境。
  • 事务一致性算法如2PC和3PC虽然也可以应用于分布式环境，但由于它们对协调者的依赖，可能会成为系统性能的瓶颈或单点故障的来源，尤其是在网络分区或协调者节点故障的情况下（SAGA其实也一样）。

因此，选择哪种算法取决于系统的需求、环境的复杂性以及对容错性和性能的不同要求。