3 Paxos 存在问题吗

在过去的10多年中，Leslie Lamport 的 Paxos 协议 [15] 几乎称为一致性算法的代名词：它是教学中最常用到的算法，同时很多一致性算法实现都基于 Paxos。首先，Paxos 定义了能够在单一决策

上达成一致的协议，比如单个复制日志条目。我们把这个子集称为 Single-decree Paxos。然后合并这个协议的多个实例来实现一系列决策，例如一个日志（ 多 Paxos）。Paxos 能够确保安全和活性（Liveness），并支持集群成员变更。它的正确性已被证明，通常情况下也非常有效。

不幸的是，Paxos 存在两个致命的缺陷。第一个是 Paxos 非常难懂，其完整的解释晦涩难懂，很少有人能完全理解，只有少数人以付出巨大努力为代价才算理解了 Paxos。因此，很多人尝试用一些简单的术语来解释 Paxos [16, 20, 21]。这些解释都集中在 Single-decree 子集，但仍是很有挑战的。在 NSDI 2012 会议上的一次非正式调查显示，我们发现很少有人熟悉 Paxos，即使是一些有经验的研究人员也不例外。我们自己也曾受其折磨，直到我们读过几篇简化对 Paxos 理解的文章，并设计了我们自己的算法之后，才算理解了整个 Paxos 协议，然而这个过程花费了我们将近一年的时间。

我们假定 Paxos 的晦涩来源于它以 Single-decree 子集为基础的。Single-decree Paxos 晦涩且微妙：它被分为两个阶段，但没有简单直观的解释，且难以单独去理解。正因为如此，它很难直观地说明为什么 Single-decree 协议是有效的。多 Paxos 的组成规则反倒增加了额外的复杂和微妙。我们认为，在多决策上达成一致的整个问题，是可以采用其它更加直接和明显的方式来进行分解的。

Paxos 的第二个缺陷是，它难以为实际环境中的系统实现提供良好的基础。原因之一是，业界并没有广泛的对 多 Paxos 算法进行商讨。Lamport 的描述大部分都是关于 Single-decree Paxos 的，他只是给出了实现 多 Paxos 的一些可能的方式，缺少很多细节。有许多实现和优化 Paxos 的尝试，比如 [26]、[39] 和 [13]，但它们都互不相同，且与 Lamport 给出的说法也不同。像 Chubby 系统已经实现了类似 Paxos 的算法，但是大多数情况下都没有披露更多的细节。

此外，Paxos 的架构并没有对构建实际系统带来优势，这也是 Single-decree 分解带来的另一个后果。例如，独立地挑选出一组日志条目，然后把它们变成一个连续的日志，并没有带来什么好处，反倒增加了复杂性。基于日志来设计系统是更加简单而有效的，新的日志条目只需按照指定的顺序追加到日志中去。另一个问题是，Paxos 使用对等的 peer-to-peer 方式作为其核心（尽管最终提出了一种使用弱 Leader 形式来优化性能的建议）。这种方法只有在做出单个决策的情况下才有意义，但几乎没有实际系统会选择使用这种方式。如果需要做一系列决策，简单高效的做法是：先选出一个 Leader，然后由 Leader 来协调做出决策。

因此，构建实际系统无法从 Paxos 获取更大的益处。每个始于 Paxos 的实现，都会发现很难实现它，然后开发了一个完全不同的架构。这很耗时而且容易出错，并且理解 Paxos 的难度又加剧了这个问题。证明理论的正确性，Paxos 公式可能是一个很好的选择，但是实现上有很大的不同，Paxos 理论证明根本体现不出价值。下面是来自 Chubby 实现的一条有代表性的评论：

Paxos 算法的描述与实际实现之间存在巨大的鸿沟…最终的系统将会基于一个没有被证明的协议而构建起来。

由于这些问题，我们认为 Paxos 没有为系统构建或者教学提供一个良好的基础。鉴于一致性算法对于构建大规模软件系统的重要性，我们决定尝试设计一种比 Paxos 更好的一致性算法，Raft 算法就这样被设计出来。