简介： 分布式一致性（Consensus）作为分布式系统的基石，始终都是计算机系统畛域的热点。近年来随着分布式系统的规模越来越大，对可用性和一致性的要求越来越高，分布式一致性的利用也越来越宽泛。纵观分布式一致性在工业界的利用，从最开始的鼻祖 Paxos 的一统天下，到横空出世的 Raft 的风行，再到现在 Leaderless 的 EPaxos 开始备受关注，背地的技术是如何演进的？本文将从技术角度探讨分布式一致性在工业界的利用，并从可了解性、可用性、效率和实用场景等几个角度进行比照剖析。
分布式一致性
分布式一致性，简略的说就是在一个或多个过程提议了一个值后，使零碎中所有过程对这个值达成统一。
为了就某个值达成统一，每个过程都能够提出本人的提议，最终通过分布式一致性算法，所有正确运行的过程学习到雷同的值。
工业界对分布式一致性的利用，都是为了构建多正本状态机模型（Replicated State Machine），实现高可用和强统一。
分布式一致性使多台机器具备雷同的状态，运行雷同的确定性状态机，在多数机器故障时整体仍能失常工作。
Paxos
Paxos 达成一个决定至多须要两个阶段（Prepare 阶段和 Accept 阶段）。
Prepare 阶段的作用：
- 争取提议权，争取到了提议权能力在 Accept 阶段发动提议，否则须要从新争取。
- 学习之前曾经提议的值。
Accept 阶段使提议造成多数派，提议一旦造成多数派则决定达成，能够开始学习达成的决定。Accept 阶段若被回绝须要从新走 Prepare 阶段。
Multi-Paxos
Basic Paxos 达成一次决定至多须要两次网络来回，并发状况下可能须要更多，极其状况下甚至可能造成活锁，效率低下，Multi-Paxos 正是为解决此问题而提出。
Multi-Paxos 选举一个 Leader，提议由 Leader 发动，没有竞争，解决了活锁问题。提议都由 Leader 发动的状况下，Prepare 阶段能够跳过，将两阶段变为一阶段，提高效率。Multi-Paxos 并不假如惟一 Leader，它容许多 Leader 并发提议，不影响安全性，极其状况下进化为 Basic Paxos。
Multi-Paxos 与 Basic Paxos 的区别并不在于 Multi（Basic Paxos 也能够 Multi），只是在同一 Proposer 间断提议时能够优化跳过 Prepare 间接进入 Accept 阶段，仅此而已。
Raft
不同于 Paxos 间接从分布式一致性问题登程推导进去，Raft 则是从多正本状态机的角度提出，应用更强的假如来缩小须要思考的状态，使之变的易于了解和实现。
Raft 与 Multi-Paxos 有着千头万绪的关系，上面总结了 Raft 与 Multi-Paxos 的异同。
Raft 与 Multi-Paxos 中类似的概念：
- Raft 的 Leader 即 Multi-Paxos 的 Proposer。
- Raft 的 Term 与 Multi-Paxos 的 Proposal ID 实质上是同一个货色。
- Raft 的 Log Entry 即 Multi-Paxos 的 Proposal。
- Raft 的 Log Index 即 Multi-Paxos 的 Instance ID。
- Raft 的 Leader 选举跟 Multi-Paxos 的 Prepare 阶段实质上是雷同的。
- Raft 的日志复制即 Multi-Paxos 的 Accept 阶段。
Raft 与 Multi-Paxos 的不同：
Raft 假如零碎在任意时刻最多只有一个 Leader，提议只能由 Leader 收回（强 Leader），否则会影响正确性；而 Multi-Paxos 尽管也选举 Leader，但只是为了提高效率，并不限度提议只能由 Leader 收回（弱 Leader）。
强 Leader 在工程中个别应用 Leader Lease 和 Leader Stickiness 来保障：
- Leader Lease：上一任 Leader 的 Lease 过期后，随机期待一段时间再发动 Leader 选举，保障新旧 Leader 的 Lease 不重叠。
- Leader Stickiness：Leader Lease 未过期的 Follower 回绝新的 Leader 选举申请。
Raft 限度具备最新已提交的日志的节点才有资格成为 Leader，Multi-Paxos 无此限度。
Raft 在确认一条日志之前会查看日志连续性，若查看到日志不间断会回绝此日志，保障日志连续性，Multi-Paxos 不做此查看，容许日志中有空洞。
Raft 在 AppendEntries 中携带 Leader 的 commit index，一旦日志造成多数派，Leader 更新本地的 commit index 即实现提交，下一条 AppendEntries 会携带新的 commit index 告诉其它节点；Multi-Paxos 没有日志连接性假如，须要额定的 commit 音讯告诉其它节点。
EPaxos
EPaxos（Egalitarian Paxos）于 SOSP’13 提出，比 Raft 还稍早一些，但 Raft 在工业界大行其道的工夫里，EPaxos 却长期无人问津，直到最近，EPaxos 开始被工业界所关注。
EPaxos 是一个 Leaderless 的一致性算法，任意正本均可提交日志，通常状况下，一次日志提交须要一次或两次网络来回。
EPaxos 无 Leader 选举开销，一个正本不可用可立刻拜访其余正本，具备更高的可用性。各正本负载平衡，无 Leader 瓶颈，具备更高的吞吐量。客户端可抉择最近的正本提供服务，在跨 AZ 跨地区场景下具备更小的提早。
不同于 Paxos 和 Raft，当时对所有 Instance 编号排序，而后再对每个 Instance 的值达成统一。EPaxos 不当时规定 Instance 的程序，而是在运行时动静决定各 Instance 之间的程序。EPaxos 不仅对每个 Instance 的值达成统一，还对 Instance 之间的绝对程序达成统一。EPaxos 将不同 Instance 之间的绝对程序也做为一致性问题，在各个正本之间达成统一，因而各个正本可并发地在各自的 Instance 中发动提议，在这些 Instance 的值和绝对程序达成统一后，再对它们依照绝对程序从新排序，最初按程序利用到状态机。
从图论的角度看，日志是图的结点，日志之间的程序是图的边，EPaxos 对结点和边别离达成统一，而后应用拓扑排序，决定日志的程序。图中也可能造成环路，EPaxos 须要解决循环依赖的问题。
EPaxos 引入日志抵触的概念（与 Parallel Raft 相似，与并发抵触不是一个概念），若两条日志之间没有抵触（例如拜访不同的 key），则它们的绝对程序无关紧要，因而 EPaxos 只解决有抵触的日志之间的绝对程序。
若并发提议的日志之间没有抵触，EPaxos 只须要运行 PreAccept 阶段即可提交（Fast Path），否则须要运行 Accept 阶段能力提交（Slow Path）。
PreAccept 阶段尝试将日志以及与其它日志之间的绝对程序达成统一，同时保护该日志与其它日志之间的抵触关系，如果运行完 PreAccept 阶段，没有发现该日志与其它并发提议的日志之间有抵触，则该日志以及与其它日志之间的绝对程序曾经达成统一，间接发送异步的 Commit 音讯提交；否则如果发现该日志与其它并发提议的日志之间有抵触，则日志之间的绝对程序还未达成统一，须要运行 Accept 阶段将抵触依赖关系达成多数派，再发送 Commit 音讯提交。
EPaxos 的 Fast Path Quorum 为 2F，可优化至 F + [(F + 1) / 2 ]，在 3 正本和 5 正本时，与 Paxos、Raft 统一。Slow Path 为 Paxos Accept 阶段，Quorum 固定为 F + 1。
EPaxos 还有一个被动 Learn 的算法，在复原的时候可用来追赶日志，这里就不做具体的介绍了，感兴趣的能够看论文。
比照剖析
从 Paxos 到 Raft 再到 EPaxos，背地的技术是怎么样演进的，咱们能够从算法自身来做个比照，上面次要从可了解性、效率、可用性和实用场景等几个角度进行比照剖析。
1 可了解性
家喻户晓，Paxos 是出了名的艰涩难懂，不仅难以了解，更难以实现。而 Raft 则以可了解性和易于实现为指标，Raft 的提出大大降低了应用分布式一致性的门槛，将分布式一致性变的大众化、平民化，因而当 Raft 提出之后，迅速失去青眼，极大地推动了分布式一致性的工程利用。
EPaxos 的提出比 Raft 还早，但却长期无人问津，很大一个起因就是 EPaxos 切实是难以了解。EPaxos 基于 Paxos，但却比 Paxos 更难以了解，大大地妨碍了 EPaxos 的工程利用。不过，是金子总会发光的，EPaxos 因着它独特的劣势，终于被人们发现，具备广大的前景。
2 效率
从 Paxos 到 Raft 再到 EPaxos，效率有没有晋升呢？咱们次要从负载平衡、音讯复杂度、Pipeline 以及并发解决几个方面来比照 Multi-Paxos、Raft 和 EPaxos。
负载平衡
Multi-Paxos 和 Raft 的 Leader 负载更高，各正本之间负载不平衡，Leader 容易成为瓶颈，而 EPaxos 无需 Leader，各正本之间负载齐全平衡。
音讯复杂度
Multi-Paxos 和 Raft 选举出 Leader 之后，失常只须要一次网络来回就能够提交一条日志，但 Multi-Paxos 须要额定的异步 Commit 音讯提交，Raft 只须要推动本地的 commit index，不应用额定的音讯，EPaxos 依据日志抵触状况须要一次或两次网络来回。因而音讯复杂度，Raft 最低，Paxos 其次，EPaxos 最高。
Pipeline
咱们将 Pipeline 分为程序 Pipeline 和乱序 Pipeline。Multi-Paxos 和 EPaxos 反对乱序 Pipeline，Raft 因为日志连续性假如，只反对程序 Pipeline。但 Raft 也能够实现乱序 Pipeline，只须要在 Leader 上给每个 Follower 保护一个相似于 TCP 的滑动窗口，对应每个 Follower 上保护一个接管窗口，容许窗口外面的日志不间断，窗口里面是曾经间断的日志，日志一旦间断则向前滑动窗口，窗口外面可乱序 Pipeline。
并发解决
Multi-Paxos 沿用 Paxos 的策略，一旦发现并发抵触则回退重试，直到胜利；Raft 则应用强 Leader 来防止并发抵触，Follwer 不与 Leader 竞争，防止了并发抵触；EPaxos 则直面并发抵触问题，将抵触依赖也做为一致性问题看待，解决并发抵触。Paxos 是抵触回退，Raft 是抵触防止，EPaxos 是抵触解决。Paxos 和 Raft 的日志都是线性的，而 EPaxos 的日志是图状的，因而 EPaxos 的并行性更好，吞吐量也更高。
3 可用性
EPaxos 任意正本均可提供服务，某个正本不可用了可立刻切换到其它正本，正本生效对可用性的影响微不足道；而 Multi-Paxos 和 Raft 均依赖 Leader，Leader 不可用了须要从新选举 Leader，在新 Leader 未选举进去之前服务不可用。显然 EPaxos 的可用性比 Multi-Paxos 和 Raft 更好，但 Multi-Paxos 和 Raft 比谁的可用性更好呢。
Raft 是强 Leader，Follower 必须等旧 Leader 的 Lease 到期后能力发动选举，Multi-Paxos 是弱 Leader，Follwer 能够随时竞选 Leader，尽管会对效率造成肯定影响，但在 Leader 生效的时候能更快的复原服务，因而 Multi-Paxos 比 Raft 可用性更好。
4 实用场景
EPaxos 更实用于跨 AZ 跨地区场景，对可用性要求极高的场景，Leader 容易造成瓶颈的场景。Multi-Paxos 和 Raft 自身十分类似，实用场景也相似，实用于内网场景，个别的高可用场景，Leader 不容易造成瓶颈的场景。
思考
最初留下几个思考题，感兴趣的同学能够思考思考：
1）Paxos 的 Proposal ID 须要惟一吗，不惟一会影响正确性吗？
2）Paxos 如果不辨别 Max Proposal ID 和 Accepted Proposal ID，合并成一个 Max Proposal ID，过滤 Proposal ID 小于等于 Max Proposal ID 的 Prepare 申请和 Accept 申请，会影响正确性吗？
3）Raft 的 PreVote 有什么作用，是否肯定须要 PreVote？