There is no compression algorithm for experience. — Andy Jassy, CEO of AWS
一、缘起
共识协定，对于从事分布式系统研发的同学们来说真堪称是最相熟的陌生人。一方面，共识协定面向有状态分布式系统的数据一致性与服务容错性这两大难题提供了近乎完满的解决方案，绝大部分同学或多或少据说过 / 钻研过 / 应用过 / 实现过 Paxos/Raft 等经典共识协定；另一方面，共识协定确实很简单，事实上，学习并弄懂共识协定原理倒是没有那么难，然而要在理论零碎中用好用正确共识协定绝非易事，共识畛域外面的“双主脑裂”，“幽灵复现”等传说，也让很多同学望而却步。这篇文章与读者敌人们好好聊一聊共识这个技术畛域，冀望可能让大伙儿对共识协定的前世今生以及这些年的技术演进有个大体理解。虽说教训这种货色没有压缩算法，得本身一点一点实际过才真正算数，然而认知学习是能够减速的，所谓：今日格一物，明日又格一物，豁然贯通，终知天理。
咱们晓得，分布式系统最浮夸的指标是把一堆一般机器的计算 / 存储等能力整合到一起，而后整体上可能像一台超级机器一样对外提供可扩大的读写服务，设计原则上要实现即便其中的局部机器产生故障，零碎整体服务不受影响。对于有状态的分布式系统而言，实现上述容错性指标的无效伎俩绕不开赫赫有名的复制状态机。该模型的原理是为一个服务器汇合里的每台服务器都保护着雷同机制的确定无限状态机（DFSM，Determinate Finite State Machine），如果可能保障每个状态机输出的是完全一致的命令序列，那么这个汇合中的每个状态机最终都能够以雷同状态对外提供服务，同时也具备了容忍局部状态机故障的能力。
$$
图 1. 让分布式系统像“单机”一样工作的复制状态机模型
$$
图 1 展现了典型的复制状态机模型，在理论利用中，上文提到的状态机的命令序列通常会应用「只读可追加日志」来实现，即每个状态机上都保护着一个日志，日志外面保留着本状态机待执行的命令序列。在图 1 的例子中，每台状态机看到的日志序列都必须是严格统一的「x<-3」，「y<-1」，「y<-9」，…，每个状态机执行雷同的命令序列，对外出现的最终状态均为：x 的值是 3，y 的值是 9。显然，在复制状态机模型中，如何保障状态机之间数据统一的问题转换成了如何保障各台机器上日志序列统一的问题，这个成为了复制状态机模型最外围的挑战，而这，也正是共识协定神圣的职责（不容易呀，话题总算引回来了）。
分布式共识协定的鼻祖，通常认为是 Leslie Lamport 提出的 Paxos。这里有个乏味的典故，事实上 Lamport 在 1990 年的时候就向 TOCS（ACM Transactions on Computer Systems）投递了《The Part-Time Parliament》这篇大作，通篇以考古希腊 Paxos 小岛为背景，形容了现代该小岛上议会制订法令的流程，冀望读者可能从中领悟出共识协定的精华，并且可能了解到大神的「幽默感」。奈何这种形容形式太过费解，编辑们没看进去这层含意，幽默感当然也没 get 到，后果即使这是大神投稿的文章也落得杳无音信的终局。工夫来到了 1998 年，编辑部在整顿旧的文献资料的时候，从某个文件柜中发现了这篇旧文并试着从新浏览了一下，这次终于意识到了这外面蕴含着的共识问题的武学奥义。最终这篇扛鼎之作得以重见天日！不过，实话实说，这个版本论文形容的确实是艰涩难懂，明天广为流传的解说 Paxos 原理的论文其实是 2001 年 Lamport 再发表的《Paxos Made Simple》。话说这篇 Paxos 论文的摘要挺节约版面费的，就一句话：
The Paxos algorithm, when presented in plain English, is very simple.
说实话，从明天的角度来浏览此文，Basic Paxos 的思路确实是比拟好懂。咱们能够简略回顾一下，如图 2 中所展现的，Basic Paxos 中一共有三类角色：其一提议者 Proposer，其二接收者 Acceptor，其三学习者 Learner。基于实现就某个值达成共识这个具体指标，Basic Paxos 全异步地经验如下三个阶段：
- PREPARE 阶段，Proposer 会生成全局惟一且枯燥递增的 Proposal ID，向所有的 Acceptor 发送 PREPARE 提案申请，这里无需携带内容，只携带提案的 Proposal ID 即可；
相应的，Acceptor 收到 PREPARE 提案音讯后，如果提案的编号（无妨即为 N）大于它曾经回复的所有 PREPARE 音讯，则 Acceptor 将本人上次承受的决定内容回复给 Proposer，承诺有二：不再回复（或者明确回绝）提案编号小于等于 N（这里是 <=）的 PREPARE 提案；不再回复（或者明确回绝）提案编号小于 N（这里是 <）的 ACCEPT 决定；
- ACCEPT 阶段，如果 Proposer 收到了多数派 Acceptors 对 PREPARE 提案的必定回复，那么进入决定阶段。它要向所有 Acceptors 发送 ACCEPT 决定申请，这里包含编号 N 以及依据 PREPARE 阶段决定的 VALUE（如果 PREPARE 阶段没有收集到决定内容的 VALUE，那么它能够自在决定 VALUE；如果存在曾经承受决定内容 的 VALUE，那么 Proposer 就得持续决定这个值）；
相应的，Acceptor 收到 ACCEPT 决定申请后，依照之前的承诺，不回复或者明确回绝掉提案编号小于曾经长久化的 N 的决定申请，如果不违反承诺，Acceptor 承受这个决定申请；
- COMMIT 阶段，如果 Proposer 收到了多数派 Acceptors 对于 ACCEPT 决定的必定回复，那么该决定曾经正式通过，异步地，Proposer 把这个好消息播送给所有的 Learners；
$$
图 2. 原始 Basic Paxos 的根本流程，其实真的还挺简略
$$
以上就是根底版的 Basic Paxos 协定，完满地解决了分布式系统中针对某一个值达成共识的问题，其实也挺好了解的，对不对？然而，理论的分布式系统显然不可能仅仅基于一个值的共识来运行。依照图 1 外面的复制状态机模型的要求，咱们是要解决日志序列一系列值的共识问题呀。咋办？好办！直观地，咱们能够重复地一轮一轮执行 Basic Paxos，为日志序列中每一条日志达成共识，这个就是通常所谓的 Multi Paxos。这里的所谓一轮一轮的轮号就是咱们常说的 Log ID，而前者提到的 Proposal ID，则是咱们常说的 Epoch ID。对于采纳 Multi Paxos 的有状态分布式系统而言，日志序列的 Log ID 必须是严格间断递增并且无空洞地利用到状态机，这个是 Multi Paxos 反对乱序提交所带来的束缚限度，否则咱们无奈保障各状态机最终利用的命令序列是完全一致的。这里须要课代表记下笔记，一句话重点就是：
Proposal ID（Epoch ID）的全局惟一且枯燥递增的束缚次要还是出于效率的思考，Log ID 的全局惟一且枯燥递增的约束则是出于正确性的思考。
分享到这，特地怕读者敌人来这么一句：报告，下面的内容我都看懂了，请问什么时候能够上手开发共识协定？！其实，从 Basic Paxos 到 Multi Paxos，这之间存在着微小的鸿沟，实际中有着太多的挑战须要一一应答。这里咱们通过两个经典的共识效率难题来感受一下：
- LiveLock 问题，其实活锁问题源于 Basic Paxos 本身，如图 3 所示，在并发度较高的场景下，如果某一轮有多个 Proposer 同时发动 PREPARE 提案，那么有的 Proposer 会胜利，譬如 R1，有的会失败，譬如 R5，失败的 R5 会晋升 Proposal ID 从新发动 PREPARE 提案，如果这个足够快，会导致开始 PREPARE 提案胜利的 R1 持续发动的 ACCEPT 决定会失败，R1 会晋升 Proposal ID 从新发动 PREPARE 提案，. . .，两个正本就这样周而复始，始终在争抢提议权，造成了活锁。解决方案也是有的，一者是管制各 Proposer 发动提案的频率，二者是在提议失败重试的时候减少超时退却。当然，这个只能升高活锁的概率，毕竟依据驰名的 FLP 实践，此时属于放松零碎 liveness 去谋求共识协定立身之本 linearzability，因而，实践上 Paxos 就是可能永远也完结不了；
- CatchUp 问题，在 Multi Paxos 中，某个 Proposer 在收到客户端申请后，首先要决定这条申请的 Log ID，后面咱们提到了，为了保障复制状态机的数据一致性，Log ID 必须是全局严格间断递增的，即这个值不可能与曾经长久化或者正在长久化中的日志 Log ID 反复，否则 Proposer 会陷入发现这个 Log ID 曾经被某个决定占据、递增本地保护的 Max Log ID 并尝试从新提议、发现新的 Log ID 还是被某个决定占据、持续减少本地的 Max Log ID 并尝试从新提议 . . .，始终循环至发现了一个全新未启用的 Log ID。多累呀，是不是？解决方案也是有的，Proposer 向所有 Acceptors 查问它们本地曾经写盘的最大 Log ID，收到了多数派的返回后果并抉择其中最大值加一作为本次待提议的提案申请的 Log ID。当然，这种计划的实现逻辑也不轻，并且仍旧存在着争抢失败而后退却重试的概率；
$$
图 3. Basic Paxos 在多个提议者同时提议的状况下面临着活锁问题
$$
这么一剖析，应该都能感触到从 Basic Paxos 到 Multi Paxos 这般降级打怪的难度。即使数学家出身的 Lamport 大神此时也意识到须要给工程师们指引一个可行的工程化方向，否则他们势必不会上船的 …… 大神提供的解决方案很是简略间接，大伙儿就是喜爱这种奢侈：如果 Basic Paxos 中相对偏心意味着低效，那么无妨在 Multi Paxos 中引入选举并产生惟一 Leader，只有入选为 Leader 才可能提议申请。这样的益处很显著，首先由惟一的 Leader 做 Log ID 调配，比拟容易实现全局惟一且间断递增，解决了 CatchUp 难题；其次，惟一的 Leader 提议不存在并发提议抵触问题，解决了 LiveLock 难题；进一步地，原本 PREPARE 就是为了抢夺提议权，当初既然只有 Leader 可能提议，就至多在 Leader 任职工夫内就不用每个提议都要再走一遍 PREPARE，这样大幅晋升了造成决定的效率。当然啦，引入了 Leader 之后，Multi Paxos 也是要解决好 Leader 切换前后的数据一致性问题，并且新的 Leader 如何填补日志空洞等难题也须要好好设计。问题还是不少，不过，这些都是后话，大方向不会错，跟着大神冲吧！
二、野望
Lamport 推出了 Multi Paxos，明确了共识协定生产落地的大方向。然而，生产零碎到底应该怎么正确、高效地应用 Paxos，还是存在很多不确定性，工程师们始终在一直摸索、尝试，然而并没有造成现实的后果产出，业界整体上还是处于一种张望状态。始终等到 2007 年，来自 Google 的工程师们通过《Paxos Made Live – An Engineering Perspective》一文，具体地介绍了他们在 Chubby（GFS 中提供分布式锁服务的要害组件，Apache ZooKeeper 在很大水平上借鉴了 Chubby 的设计思维）中落地 Multi Paxos 的最佳实际。这篇文章十分经典，即便十六年后的明天读起来也齐全不过时，倡议有趣味理解学习 Paxos/Raft 协定的读者敌人们肯定要读一读。咱们来总结一下这篇文章提到的 Multi Paxos 生产落地过程遇到的种种挑战：
- 磁盘故障（disk corruption）：在 Lamport 的 Paxos 论文中顺便提到过长久化的问题：
Stable storage, preserved during failures, is used to maintain the information that the acceptor must remember. An acceptor records its intended response in stable storage before actually sending the response.
然而事实零碎中，用于数据长久化的设施，譬如磁盘，也会产生故障，一旦 Acceptor 机器上的磁盘产生了故障，那么上述长久化的性质就被突破，这个是原则性问题，显然此时的 Acceptor 就不再具备持续应答提议或者决定的资格，怎么办？Google 工程师们想到的解决方案是，为这类产生了长久化设施故障的 Acceptor 机器引入一个重建窗口（这个期间不再参加提议或者决定应答），相似下面提到的 Multi Paxos 的 CatchUp 机制，通过继续的学习已有的提议，啥时候是个头？始终等到重建窗口开始后发动的提议都曾经被开始学习到了，那么此时 Acceptor 很明确，本人能够平安地加回决定军团了；
- Master 租约（master lease）：Multi Paxos 通过选主来无效晋升提议效率，而后通过租约机制来保护入选 Leader 的主权。然而，基于租约的选主机制都会面临“双主”问题，即因为网络分区等缘故，旧的 Leader 仍旧在工作，并不知道新的 Leader 曾经产生并也曾经对外提供服务。这种双主问题，对于写申请没有影响（毕竟写是走多数派决定的，旧的 Leader 的 Epoch ID 比拟低，多数派 Acceptors 不会承受它的申请提议），可是对于读申请，特地是强一致性读，这就是个很大危害了，因为从旧的 Leader 可能会读到过期数据。Google 工程师们想到的解决方案是，强化租约机制，即 Follower 收到 Leader 的租约更新后，严格承诺在租约有效期内不发动 / 接管新一轮选举，包含与 Leader 断连以及本身过程重启等场景，这样强化的租约机制可能将不同代的 Leader 之间实现物理工夫上的隔离，确保同一时刻最多只有一个 Leader 提供内存态的强统一读服务；
- Master 纪元（master epoch）：这个其实就是咱们所谓的“幽灵复现”问题，即旧的 Leader 解决某个提议申请超时了，没有造成多数派决定，在几轮从新选举之后，这条决定可能会被从新提议并最终造成多数派。这个问题的最大危害在于让客户端莫衷一是：提议申请超时，客户端并不知道后端系统理论处于什么情况，申请到底是胜利或失败不分明，所以客户端做法通常是重试，这个要求后盾零碎的业务逻辑须要反对幂等，不然重试会导致数据不统一。Google 的工程师们想到的解决方案是，为每个日志都保留以后的 Epoch ID，并且 Leader 在开始服务之前会写一条 StartWorking 日志，所以如果某条日志的 Epoch ID 绝对前一条日志的 Epoch ID 变小了，那么阐明这是一条“幽灵复现”日志，疏忽这条日志；
- 共识组成员（group membership）：理论零碎中显然是要面对成员变更这个需要。通过冷启动形式天然是能够实现成员变更的，然而这种机制对于在线服务无奈承受。是否在不停服的状况下进行成员变更？事实上，成员变更自身也是一个共识问题，须要所有节点对新成员列表达成统一。然而，成员变更又有其特殊性，因为在成员变更的过程中，参加投票的成员会发生变化。所以这个性能该怎么实现就十分有考究，如果新旧两个成员组的多数派能够不相交，那么就会呈现脑裂，导致数据不统一的严重后果。Multi Paxos 论文中提到了成员变更自身也要走共识协定，然而在理论零碎中实现这个性能的时候，还是遇到了很多挑战，譬如新配置什么时候失效？譬如变更到一半，产生从新选举，那么前面到底要不要持续成员变更；
- 镜像快照（snapshots）：Google 的工程师们在 Multi Paxos 的实际中，详细描述了快照机制的引入，这里的目标有二：其一放慢节点重入的复原，这样就不必逐条日志学习；其二无效管制日志对磁盘空间量的占用。须要特地留神的是（肯定要牢记心里），打快照齐全是业务逻辑，底层一致性引擎能够告诉下层业务状态机何时打快照，至于快照怎么打，保留到哪里，如何加载快照，这些都是业务状态机须要反对的。快照实现自身也面临着诸多挑战，譬如快照与日志要配合且保障整体数据一致性；譬如打快照自身耗时耗力，尽可能要异步实现，不影响失常申请的决定流程；譬如打快照长久化后可能也会损坏，要减少多重备份以及必要校验等等；
以上是 Multi Paxos 算法在 Google Chubby 理论落地过程遇到的诸多挑战，我置信读者敌人们应该都可能感触到 Paxos 从实践到实际确实是有很多技术点须要欠缺。其实就下面这些还是搂着说的，实际上 Google 的工程师们还探讨了更多不确定性：如何保障正确地实现了 Multi Paxos 的实在语义？如何对一个基于共识协定的分布式系统进行无效测试验证？如何进行状态机运行态正确性查看，特地是版本升级等场景状态机前后语义可能不兼容？
读到这里，我置信，读者敌人会跟我有一样的感叹，Google 的工程师们真的太强，着实让人拜服，在 2007 年的时候，敢为人先，把 Paxos 扎扎实实地利用到了生产，你看看人家下面提到的这些个问题，基本上做有状态分布式系统的研发同学在这些年的工作中或多或少都踩过相似的坑吧？想一想，早些年 Google 发表了号称大数据畛域三驾马车的巨作：GFS，BigTable，MapReduce，算是拉开了云计算的大幕，近些年 Google 又开源了云原生的 Kubernetes，公开了大模型 Transformer …… 不得不感叹一句，Google 确实是云计算畛域的弄潮儿 ……
$$
图 4. 总结起来，这些年共识畛域大体能够划分为六大演进方向
$$
话说回来，咱们有理由置信，人们对于 Paxos 共识协定的激情被 Google 的这篇文章给重新点燃，越来越多的厂商、钻研工作者投身其中，摸索并继续改良共识协定，而后等到了 2014 年 Raft 的横空出世 …… 如图 4 所示，咱们梳理了这些年的共识畛域的各类钻研工作，把共识畛域的演进工作分为六大方向，接下来的篇幅，咱们集中注意力，逐个说道说道共识畛域的这六大门派：
- 强主派：横空出世的 Raft，真正让共识协定在工业界遍地开花，从前王谢堂前燕，由此飞入寻常百姓家；
- 无主派：你有张良计，我有过墙梯。Generalized Paxos/Mencius/EPaxos 等接力摸索去除单点瓶颈依赖；
- 规范派：Corfu/Delos 为共识协定引入模块化档次设计，反对热降级可插拔，实现标准化接入通用化移植；
- 异步派：缘起 EPaxos，Skyros/Tempo/Rabia 推延线性定序，主推异步共识，谋求世间完满的一跳决定；
- 灵便派：FPaxos/WPaxos 脑洞大开，解耦共识的提议组与决定组的成员列表，灵便应答跨地区容灾场景；
- 软硬一体派：NOPaxos/P4xos 顺应时代大潮，摸索共识各模块硬件卸载的可行性，软硬一体化减速共识；
- ……
三、进击
我集体比拟喜爱读历史类的书籍，其中《大秦帝国》这部著述重复浏览过几遍。这个系列共计有六部，讲述了从秦孝公变法图强开始，直至秦末群雄并起的这段恢弘历史。我察觉《大秦帝国》六个篇章的显明题目（彩色裂变，国命纵横，金戈铁马，阳谋春秋，铁血文化，帝国烽火）用来概括共识畛域这些年六大演进方向还算是比拟贴合，为了减少文章浏览的趣味性，斗胆引征了过去，诸君请听我细细道来。
3.1 彩色裂变
彩色裂变这个篇章，必须要留给 Raft，并且为了示意尊重，这个章节咱们只放 Raft 这一个共识协定。正是 Raft 的横空出世，解决了共识协定工业落地艰难的问题，并且 Raft 在古代分布式系统的状态一致性放弃这个要害性质上起到了巨大作用。事实上，明天咱们在 GitHub 上搜寻带有 Raft 关键字的开源库，能够查看有 1300+ 个开源库，其中 stars 破 1000 的也有 30+，不乏 etcd-io/etcd，tikv/tikv，baidu/braft，polardb/polardbx-sql，sofastack/sofa-jraft，hashicorp/raft 等业界各大出名厂商的代表作。这里，特地致敬一下 Raft 的提出者，Diego Ongaro。
正如前文所言，Multi Paxos 的工业落地并不顺畅，如何解决活锁，如何无效选举，如何打快照，如何解决空洞等问题。要害这些问题的解决让 Multi Paxos 变得异样简单，咱们怎么保障实现正确呢？来自 Standford 的计算机博士 Diego Ongaro 没有抉择跟 Multi Paxos 死磕，他的博士期间的钻研关注点都放在了探寻一种可了解性以及易于生产利用这两大维度上更优的全新共识协定，最终在 2014 年 USENIX ATC 展现了他「探寻」的答案，Raft。
我认为 Raft 最出色的中央是在共识协定中引入了强主。是的，你没有听错。读者敌人们必定有纳闷：你明明在方才介绍中提到了 Multi Paxos 同样是引入 Leader 来解决提议效率问题的。这么说吧，相较于 Raft 中的 Leader 被定义为「强主」模式，我更违心把 Multi Paxos 中的 Leader 定义为「代理」模式。先说 Multi Paxos，事实上，每个 Proposer 都能够成为那个惟一提议者，这里仅仅是须要一个「代理」上位，省得七嘴八舌效率低。并且「代理」是能够随时被更换的，大家没有心理累赘；而到了 Raft，Leader 成为了智者，是领有最多信息的那个 Proposer，Leader 的规范就是整个分组的规范，不统一的中央通通以 Leader 为准。事实上，其余角色都指着 Leader 存活，成为了 Leader 的附丽，更换 Leader 也就成为了一件十分谨慎的事件，两头甚至会产生共识停服的窗口。「强主」模式体现了 Raft 的「简略无效好实现」的设计理念，也间接撑持了其它如日志复制、一致性保障等模块的简化。
具体的请看图 5，在 Raft 共识协定中，所有的日志流均是严格按程序从 Leader 发送给 Follower，这个共识组外面并不存在其它通信通道。此外，Leader 给 Follower 发送的每条日志 X 都蕴含有 Leader 记录的该 Follower 上一条生产的日志 Y，在 Follower 这边收到 Leader 发送过去的日志 X 并筹备承受之前，会查看本地记录的上一条日志是否是 Y，如果不统一，那么所有以 Leader 为规范，Follower 持续往前追溯，找到与 Leader 分叉点，打消掉本地分叉并坚定学习 Leader 的日志。通过这个强主逻辑的设计，日志复制治理失去了质的简化，而且服务器的状态空间也被大为简化，是不是？
另外，不晓得大家留神没有，通过这种强主逻辑的设计，Raft 事实上打消了日志空洞的情景，这也将更加不便拉平两个节点的最新日志。回顾一下，Multi Paxos 反对提议的乱序提交，容许日志空洞存在，这个尽管是提供了协定的灵活性，并发性也更优，然而确实让协定变得更加的简单，妨碍了协定的工业落地。
$$
图 5. 引入强主模式 Leader，简化了日志复制治理，大大晋升了协定可了解性
$$
咱们持续来说一说 Raft 的选举算法，它摒弃了 Multi Paxos 应用原生共识协定来进行选举的简单机制，而是解耦进去，通过引入简略的“随机超时 + 多数派”机制来进行无效选举。图 6 展现了 Raft 共识协定中角色状态转换图，所有角色初始状态都是 Follower，有个随机的选举超时工夫，如果在这个工夫内没有 Leader 被动联系过去，进入 Candidata 状态，将选举的 Epoch 加一，发动新一轮选举：1）如果收到本轮多数派选举投票，那么入选 Leader，告诉其它同代的角色进入 Follower 状态；2）如果发现了本轮 Leader 的存在，则本身转换成 Follower 状态；3）如果超时工夫内没有产生上述两类事件，随机超时后再次发动新一轮选举。留神，在 Raft 选举算法中，依据多数派准则，每一代（通过 Epoch 来示意）至少产生一个 Leader。并且，为了保证数据一致性，仅容许领有最新日志的节点入选为 Leader。这里我要再次敲一敲小黑板，Multi Paxos 中任意节点都能够入选 Leader，益处是灵便，毛病是补全空洞等事宜让 Leader 上任过程变得很简单；Raft 中只有领有最新日志的节点能够入选 Leader，新官上任无需三把火。Raft 的这个设计好，真好，怎么那么好呢？！
$$
图 6. Raft 着重简化设计，独自剥离进去的选举算法次要依赖随机超时机制
$$
在 Raft 原生的选举协定中，如果 Leader 发现了更大的 Epoch，会被动退出角色。这个在理论落地时候会产生一个所谓 StepDown 问题：如果某个 Follower 与其余正本之间产生了网络分区，那么它会继续地选举超时，继续地触发新一轮选举，而后它的 Epoch 会越来越大。此时，一旦网络复原，Leader 会发现这个更大 Epoch，间接退出以后角色，零碎服务被中断，显然这个是零碎可用性的隐患。依据多数派准则，每个 Epoch 至少只有一个 Leader 入选，因而，每次发动选举之前晋升 Epoch 是必要的操作，那应该怎么面对这个 StepDown 挑战？通常的解决方案是，在正式选举之前，即把 Epoch 正式晋升并发动选举之前，先发动一轮预选举 PreVote，只有 PreVote 确认本人可能获胜，那么才会发动正式选举。留神，这里的奇妙之处是，PreVote 不会批改任何正本的选举状态。
最初咱们聊一聊 Raft 的成员变更，这个就是 Raft 的特点，方方面面给你思考的透透的，巴不得帮你把实现的代码都写了。Raft 首次提出了 Joint Consensus（联结统一）的成员变更办法，将过程拆分成旧成员配置 Cold 失效，到联结统一成员配置 Cold,new 失效，而后再到新成员配置 Cnew 失效这三个阶段。如图 7 所示，Leader 收到成员变更申请后，先向 Cold 和 Cnew 同步一条 Cold,new 日志，这条日志比拟非凡，须要在 Cold 和 Cnew 都达成多数派之后方可提交，并且这个之后其它的申请提议也都得在 Cold 和 Cnew 都达成多数派之后方可提交。在 Leader 意识到 Cold,new 日志曾经造成了决定，那么持续再向 Cold 和 Cnew 同步一条只蕴含 Cnew 的日志，留神，这条日志只须要 Cnew 的多数派确认即可提交，不在 Cnew 中的成员则自行下线，此时成员变更即算实现。在 Cnew 之后的其它的申请提议也都得在 Cnew 达到多数派即可。成员变更过程中如果产生 failover，譬如老 Leader 宕机，那么 Cold,new 中任意一个节点都可能成为新 Leader，如果新 Leader 上没有 Cold,new 日志，则持续应用 Cold，本次成员变更宣告失败；如果新 Leader 上有 Cold,new 日志，那么它会持续将未实现的成员变更流程走完直至 Cnew 失效。
Raft 提出的 Joint Consensus 成员变更比拟通用并且容易了解，之所以分为两个阶段是为了防止 Cold 和 Cnew 各自造成不相交的多数派而选出两个 Leader 导致数据写坏。实际中，如果加强成员变更的限度，假如 Cold 与 Cnew 任意的多数派交加不为空（这个并非强假如，日常咱们的分布式一致性零碎做的成员变更简直都是加一 / 减一 / 换一，确实就是可能满足「Cold 与 Cnew 无奈单独造成多数派」），则成员变更就能够进一步简化为一阶段。
$$
图 7. Raft 独创的 Joint Consensus 成员变更法，清晰领导工业实现
$$
共识协定通常被用以解决分布式系统中数据一致性这个难题，是个强需要强依赖。Raft 协定的问世无疑大大降低了实现一个正确共识协定的门槛，业界有十分多不错的实际，很多也开源了相干的一致性库，特地是国内的一众厂商，如图 8 所展现的。说实话，在正确性根底之上，要实现一个高效稳固的一致性库，保障分布式系统可能继续的安稳运行，还是要花费很多很多心理的。这里咱们介绍几个业界比拟出名的一致性库：
- 蚂蚁的 Oceanbase，OB 应该是在 2012 年就开始捣鼓 Paxos 协定了，工夫上在 Raft 问世之前，应该算是 Google 之外，另一个把 Paxos 整明确的团队。网上很多经典的 Paxos 科普文也是 OB 团队以前的一些成员分享的。事实上，在解决了高高的技术门槛之后，业务是能够充沛享受 Multi Paxos 乱序提交日志带来的可用性和同步性能的晋升。我记得阳振坤老师之前有提过，Raft 的「要求严格依照程序决定事务」的局限对数据库的事务有着潜在性能和稳定性危险，让不相干的事务产生了相互牵制，相较而言 Multi Paxos 就没了这个束缚。不过，总的来说，Multi Paxos 还是有些曲高和寡，业界理论采纳的比比皆是；
- 腾讯的 PhxPaxos，PhxPaxos 是腾讯公司微信后盾团队自主研发的一套基于 Paxos 协定的多机状态拷贝类库，2016 年正式开源，比拟忠诚地遵循了 Basic Paxos 本来协定的工业级实现，声称在微信服务外面通过一系列的工程验证和大量顽劣环境下的测试，数据一致性有着很强健壮性保障，微信外部反对了 PhxSQL，PaxosStore 等存储产品。不过，因为 PhxPaxos 对于申请提议解决同样做了串行化的解决，并且选举进去的 Leader 必须有最新日志，这些优化设定曾经比拟多地参考借鉴了 Raft 的设计；
- 百度的 Braft，这个堪称是开源外面 Raft 协定的工业级实现。百度是在 2018 年 2 月初开源了其基于 Brpc 的 Raft 一致性算法和可复制状态机的工业级 C ++ 实现，Braft。这个我的项目最后是为了解决百度各业务线上的状态服务单点隐患，起初则帮忙业务疾速实现反对高负载和低提早的分布式系统。作为一款开源根底库，除了在业界有宏大的拥趸群体，Braft 在百度外部利用非常宽泛，包含块存储、NewSQL 存储以及强一致性 MYSQL 等等，都是原生基于 Braft 构建的其可容错的高效有状态分布式系统；
$$
图 8. 国内各大厂商在共识开源这块激情很高，简直人手一个代表作
$$
3.2 国命纵横
看完 Raft 的横空出世，是不是有种「物理学的大厦已根本建成」的感觉？那不可能。无论是代理模式的 Multi Paxos，抑或是强主模式的 Raft，都是抉择引入 Leader 来解决提议抵触问题，这个事实上也就产生了性能、稳定性的单点瓶颈：一旦 Leader 挂掉，整个零碎进行服务进入从新选举阶段，在新 Leader 产生之前这段时间即为零碎不可用窗口。那么，是否存在可能无效解决提议抵触，同时又可能去 Leader 依赖的更优雅的计划呢？所谓“你有张良计，我有过墙梯”，正如战国时代的合纵连横个别，很多钻研工作者在手不释卷地寻找、摸索去 Leader 依赖或者是弱 Leader 依赖的共识协定。该方向比拟有代表性的工作有 Fast Paxos，Generalized Paxos, Multicoordinated Paxos，Mencius，EPaxos 等等。这里咱们筛选 Generalized Paxos，Mencius 以及 EPaxos 给大伙儿介绍一下。
Generalized Paxos 很值得一提，它同样是来自 Lamport 大神的作品。这个共识协定源于对理论零碎的察看：对于复制状态机而言，通过一轮一轮强共识敲定每一轮的值，而后业务状态机拿到的日志序列齐全一样，这样当然没什么故障，然而束缚过于强了。如果某些并发提议申请之间并不相干，譬如 KV 存储中批改不同 KEY 的申请，那么这些并发申请的先后顺序其实并不会影响状态机的最终一致性，此时就没有所谓提议抵触这一说，那么这里是不是就不须要引入 Leader 来做提议仲裁了？回顾一下，Multi Paxos 定义了三类角色：Proposer，Acceptor，Learner，并引入 Leader 多协定仲裁。在 Generalized Paxos 协定中，Proposer 间接发送提议申请（包含提议的值）给 Acceptors，每个 Acceptor 会把收到的提议申请的序列发送给 Learners。每个 Learner 独立解决接管到的提议申请序列，依据申请抵触断定规定，如果可能确认某些申请没有仲裁的必要并且曾经造成多数派，那么 Learner 将这些提议申请间接利用于状态机，整个过程 2 个 RTT 搞定；如果申请之间存在抵触须要仲裁，那么 Leader 会被动参加进来，进一步给 Learners 再发一跳申请，领导它们行为统一地定序抵触提议并利用至业务状态机。整个过程起步得要 3 个 RTT 能力搞定。理论生产零碎外面，间接利用 Generalized Paxos 的很少。不过，咱们认为它更多提供了一个翻新思路：通过开掘生产零碎中申请之间的不相关性，能够减速决定提交，弱化对 Leader 的强依赖。
接着来说一说 Mencius，取自春秋战国期间儒家巨匠孟子之名。这个共识协定的取名就很讨喜，咱们都记得正是孟子提出的「民为贵，社稷次之，君为轻」的思维，这个是不是跟弱化 Leader 依赖这个课题很符合？！该共识协定的想法也很浮夸：如果单个 Leader 是性能以及稳定性的瓶颈，那么就让每个正本通过某种策略轮流成为某些轮次的 Leader。在同构的环境外面，这种 Leader 轮转策略能够最大水平摊派拜访压力，晋升零碎整体吞吐，很好很弱小，对不对？不过，这里的问题也很显著：在理论零碎中，某些正本会变慢甚至挂掉，那么这种轮转机制就运行不上来了，怎么办？Mencius 的解决方案是，找其它正本长期替个班，其它正本可能通过发送 NO-OP 申请的形式（这类申请在经典的 Basic Paxos 论文中就提到过，不影响业务状态机的状态，能够认为是占位某轮提议），为出问题的正本跳过当值轮次的申请提议，期待出问题的正本复原。总的来说，Mencius 的轮转值班顺次提议堪称是弱化 Leader 依赖的一次很不错的尝试，并且很大水平上启发了起初共识协定的演进。当初生产零碎外面用到的反对分区的 Raft 共识协定，灵感很大水平即来源于此处。
$$
图 9. EPaxos 引入二维序号空间解决了提议抵触，焦点转移到多正本如何统一定序
$$
下面这两个共识协定，Generalized Paxos 在开掘申请之间的不相关性，Mencius 则是在所有正本之间轮转 Leader，计划不一，都是为了弱化单点瓶颈。不过，要说无主共识协定的集大成者，绕不开 Egalitarian Paxos，简称 EPaxos。EPaxos 引入了二维序号空间，让每个节点都能够独立的、无竞争的提议申请。当然，分布式畛域有一句至理名言：复杂度不会隐没，只会转移。EPaxos 面临的挑战转换成了如何让多个正本可能统一地给提议申请的二维序号进行线性定序。换句话说，Paxos/Raft 定义的共识是针对一个具体的值的，EPaxos 重定义的共识是针对一系列申请的提议程序的，并且进一步奇妙地将这个过程拆分成两阶段：a）针对一个提议申请，以及其依赖项（在最终全局程序中必须要恪守的线性依赖）达成共识；b）异步地，针对一系列值以及依赖项，做个确定性的、全局统一的线性排序。
以图 10 为例，正本 R1 提议申请 A，收集多数派状况没有发现有依赖关系，间接发送 COMMIT 音讯；而正本 R5 发送的提议 B 申请，多数派回复收集回来发现有 B 依赖 A 的关系，那么再将 B ->{A} 这个依赖作为 ACCEPT 申请播送给其余正本。在收到多数派相应之后（申请之间依赖关系是面向过来的，因而多数派反馈的依赖合集就能够作为决定间接应用），播送 COMMIT 给各个正本。进一步地，正本 R1 再提议申请 C，多数派响应都是 C ->{B, A}，那么也是间接达成共识，播送 COMMIT 给各个正本。
$$
图 10. EPaxos 须要一个额定排序过程失去确定性的、全局统一决定序列
$$
当申请提议以及它的依赖项达成共识之后，申请就算提交胜利，能够返回客户端了。然而，此时申请决定在全局申请序列中的程序还没有最终确定，无奈间接利用至业务状态机，因而，EPaxos 还须要一个额定的排序过程，对已提交的决定进行排序。当决定以及其依赖汇合中所有决定都曾经实现提交后，正本就能够开始排序过程。咱们在图 10 中给出了一个示例：将每个长久化的决定看作图的节点，决定之间的依赖看作节点的出边，因为每个二维序号对应的决定和依赖项是达成全局共识的，即图的节点和出边在各正本之间曾经达成了统一，因而各正本会看到雷同依赖图。接下来对决定的排序过程，相似于对图进行确定性拓扑排序，后果即为提议申请的线性程序。
须要留神的是，如图 10，申请决定之间的依赖可能会造成环，即图中可能会有环路，因而这里也不齐全是拓扑排序。为了解决循环依赖，EPaxos 对申请决定排序的算法须要先寻找图的强连通重量，环路都蕴含在了强连通重量中，此时如果把一个强连通重量整体看作图的一个顶点，则所有强连通重量形成一个有向无环图，而后对所有的强连通重量形成的有向无环图再进行拓扑排序。寻找图的强连通重量个别应用 Tarjan 算法，这是一个递归实现，在咱们实际过程中发现这里的递归实现很容易爆栈，这点将给 EPaxos 的工程利用带来肯定挑战。此外，随着新的申请提议一直产生，旧的提议可能依赖新的提议，新的提议又可能依赖更新的提议，如此上来可能导致依赖链一直延长，没有终结，排序过程始终无奈进行从而造成新的活锁问题，这个是 EPaxos 工程利用的另一大挑战。
总结一下，无主共识畛域的摸索方向工作还蛮多，有开掘申请之间不相关性的，有正本间轮转申请提议权的，还有引入二维序号空间将问题转移成异步线性定序的 …… 上述这些无主方向的技术摸索，最终工业落地的不多，咱们认为这个跟该方向的协定广泛比较复杂有很大关系，有点高射炮打蚊子的滋味。不过，必须要补充一句，业界齐全是须要这类摸索存在的。事实上，正是 Generalized Paxos 这类开掘申请之间不相关性的工作，启发了 Paralle Raft 这些工业界的尝试；正是 Mencius 这类轮转申请提议权的工作，启发了多分区的 Raft 这些工业界的尝试；EPaxos 更是在很大水平上启发了前面介绍的「异步共识」这个流派 …… 所以怎么说呢，每一次尝试都是胜利的序曲。现实还是要有的，万一实现了呢？
3.3 金戈铁马
「金戈铁马」这个命名能够用来形容共识畛域的「灵便派」。共识协定从提出之初，在 AZ 内的有状态的分布式系统中堪称大杀四方。随着业务零碎的疾速倒退，逐渐演进出多 AZ 容灾甚至是跨地区容灾的需要。那么，此时的共识协定还能应答自若吗？毕竟印象中传统共识协定的最佳利用场景还得是同构环境的，多 AZ 以及跨地区则是引入了异构场景，共识协定该如何征战这片疆场？
「灵便派」的开山之作被称为 Flexible Paxos，它的灵感来自一个非常简单的察看：假如共识协定中成员总数是 N，PREPARE 阶段参加的成员数是 Q1，ACCEPT 阶段参加的成员数是 Q2，那么 Basic Paxos 正确性保障最实质的述求是 Q1 与 Q2 两个阶段要有重合成员，以确保信息能够传承。满足上述要求最直观的机制是 Q1 与 Q2 两个阶段都抉择多数派（majority）成员参加。可是，咱们发现只有保障 PREPARE 与 ACCEPT 两个阶段参加的成员数超过成员总数，即 Q1+Q2>N，那一样可能满足 Q1 与 Q2 两个阶段要有重合成员的要求，并且这里的参数抉择挺多，也很灵便，是不是？嗯，「灵便派」所有的故事就是从这里开始讲起的 ……
兴许有人会说，是不是闲的慌，调整这两参数有啥意义？别急，咱们回顾一下这两个阶段，PREPARE 阶段事实上做的是 Leader 选举，ACCEPT 阶段则是做日志同步，前者能够认为是管控依赖，后者是 IO 依赖，那么咱们是否能够把 Q1 调大，而 Q2 调小？这样 IO 门路依赖能够更加高效更加牢靠。还是没有心动的感觉？？好吧，再看一个更加具体的例子，如图 11 所示，咱们十分相熟的 3 AZ 场景，处于业务 IO 链路依赖的角色通常会抉择“3+3+3”部署模式，即 Q1=Q2=5，实现「挂 1 个 AZ+ 挂另一个 AZ 的 1 个节点」这样高标准容灾能力。3 AZ 部署讲求个对称构造，如果“2+2+2”部署模式，对于传统的 Multi Paxos 来说，相较于“2+2+1”不会减少额定容灾能力，ACCEPT 阶段还得多同步一个节点，吃力不讨好。而在“2+2+2”部署模式下，咱们选用 Flexible Paxos 的话，Q1 无妨设置为 4，Q2 无妨设置为 3。那么首先这种模式可能抗住挂 1 个 AZ，即便此时故障 AZ 内有 Leader 节点，残余 AZ 内的节点也可能迅速选举出新的 Leader，并且在失常 ACCEPT 阶段，该部署模式同样具备「挂 1 个 AZ+ 挂另一个 AZ 的 1 个节点」这样高标准容灾能力。感觉到 Flexible Paxos 的美了吗？咱们的观点是，Flexible Paxos 思维领导下的“2+2+2”模式是非常适合一些有状态的管控类服务选用为 3 AZ 部署计划的。
$$
图 11. 面对越来越常见的 3 AZ 场景，逐渐发现了 Flexible Paxos 的美
$$
事实上 Flexible Paxos 还提供了一个思路，能够选择性的确定参加 PREPARE 阶段的成员列表与参加 ACCEPT 阶段的成员列表，这里连 Q1+Q2>N 这个条件都不须要，而放松至仅仅须要 Q1 与 Q2 有重合成员即可，这种成员列表确定思路也被称为 GRID QUORUM 模式，这种模式跟跨地区场景十分的搭。后续钻研工作者相继推出的 DPaxos，WPaxos 都是这个思路领导下的共识协定跨域容灾方面的最佳实际。这里咱们介绍一下 WPaxos。该共识协定明确引入了 AZ 容灾以及节点容灾两个维度的容灾规范，假设参数 fn 是一个 AZ 能够容忍的挂的节点数，fz 是能够容忍挂的 AZ 数目，咱们来看看 WPaxos 原文《WPaxos: Wide Area Network Flexible Consensus》是怎么进行参数抉择的。论文外面也有具体证实为什么这样的抉择下，尽管 Q1+Q2 不大于 N，然而 Q1 与 Q2 肯定是有交加的，这里证实咱们就不开展介绍了，次要看看参数是如何抉择的：
In order to tolerate fn crash failures in every zone, WPaxos picks any fn + 1 nodes in a zone over l nodes, regardless of their row position. In addition, to tolerate fz zone failures within Z zones, q1 ∈ Q1 is selected from Z – fz zones, and q2 ∈ Q2 from fz + 1 zones.
持续举个具体的例子来活泼地了解 WPaxos 的意义吧。譬如有些区域如果是 2 AZ，怎么做容灾呢？咱们能够在邻近一个区域抉择一个 AZ，这样也是一个 3 AZ 部署。如图 12 所示，如果 AZ1，AZ2 是本地区的 2 AZ，而 AZ3 是跨地区的 AZ。依照 WPaxos 的协定束缚，咱们能够设定 9 节点部署，每个 AZ 部署 3 个节点。基于“挂 1 个 AZ+ 挂另一个 AZ 的 1 个节点”这个容灾能力的束缚，参考下面的 WPaxos 的参数抉择机制，咱们能够设定：fz = fn = 1，即 Q1 是“任意 2 AZ，每个 AZ 任意 2 个节点”，Q2 亦如此。这样的设定真的跟跨地区容灾很搭：无论是 PREPARE 阶段，还是 ACCEPT 阶段，提议者都是给所有的节点发送提议或者决定申请，因为就近解决的延时比拟低，很大概率咱们会先迎回来 AZ1/AZ2 的申请回应。因而，在常态状况下，咱们的 IO 申请都会在本区域实现。当然，选举也是能够在本区域即可实现。当产生 AZ1 或者 AZ2 挂掉的劫难场景，那么两个阶段的参与者会主动切换到 AZ2/AZ3，或者是 AZ2/AZ3，此时提早会有所增加，然而服务可用性还在。
$$
图 12. 进一步地，共识协定 WPaxos 在跨地区场景下的最佳容灾实际
$$
AZ 容灾甚至是地区容灾越来越多地呈现了云产品的建设要求外面，咱们置信，「灵便派」共识协定的灵便设计思路会在容灾场景下施展着越来越大的作用。
3.4 阳谋春秋
《大秦帝国》的「阳谋春秋」这个篇章次要讲述了六国对立者嬴政上位之前，秦国间断经验的三次重大交接危机的这段恢弘历史。共识畛域里「异步共识」发祥点应该说是 EPaxos (SOSP’13)，后面章节也具体介绍过，现实很美妙，理论落地却存在诸多挑战。在 EPaxos 提出之后，畛域外面也始终陆陆续续有钻研工作跟进，譬如来自 OSDI’16 的 Janus。始终等到了 2021 年，这一年堪称是「异步共识」门派倒退历史上里程碑式的一年，该方向的研究成果在各大顶会遍地开花（有来自 SOSP’21 的 Skyros，Rabia；有来自 NSDI’21 的 EPaxos Revisited；以及来自 EuroSys’21 的 Tempo）。正如阳谋春秋字面的意思，如果把传统的 Paxos/Raft 等共识协定都视为同步共识协定的话，那么「异步共识」算是站到了对立面，并且确实找到了可能最大施展其劣势的典型利用场景。
咱们首先来介绍下「异步共识」是如何开脑洞的。传统的共识协定就像一个简单精细的仪器，如图 13 所示，一个申请从提交至返回，大体会经验三个阶段：1）申请会被复制给多个正本，这一个阶段是为了保证数据持久性（durability）；2）每个申请都会被指定一个全局惟一，枯燥递增的序号，这一个阶段是为了保障申请之间的线性程序（linearizability）；3）申请会被最终在业务状态机执行保证数据外显性（externality）。留神，这个阶段是依据前一阶段确定的程序顺次执行。这么一个流程执行下来，一个申请至多要 2 RTT 能力返回，并且因为并发申请线性定序人造会存在抵触导致的效率问题，传统共识协定的最佳实际就是要引入一个 Leader 来做高效定序，这个就反过来让申请提议阶段存在服务单点的问题。所以「异步共识」的阳谋就是：用户提议的申请仅需经验数据复制阶段即返回，服务端异步地执行申请的线性定序以及决定执行阶段。这样解构的益处是能够专项优化数据复制阶段的延时，甚至实现无主的高可用。当然，这里的难点是，在数据复制阶段，申请要留下足够的痕迹，这些痕迹要足够反对服务端仅依据大部分正本即可异步地复原出申请之间正确的线性程序。异步共识最大的挑战就在于此，目前业界复制留痕有三大思路：1）依赖申请落在每个正本上的偏序；2）依赖复制阶段加锁强定序；3）引入工夫戳，给每个申请调配枯燥递增的工夫戳。
$$
图 13. 依据申请类型是否须要「即时外显」，咱们能够把共识分为同步与异步两类
$$
「异步共识」这里其实蕴含有一个强假如，理论分布式系统中，是否存在这样的写申请，它不须要即时执行状态机，只有确保该申请被长久化了就能够返回。咋一听还是有些反直觉的，不过事实上理论存储系统中这类写申请接口并不少见。最典型的是 Key/Value 存储系统，譬如 Put 接口，并不需要即时 APPLY，即返回客户端的时候并不需要告知相应的 KEY 是否曾经存在；譬如 Delete 接口，也并不需要即时 APPLY，即返回客户端的时候并不需要告知相应的 KEY 是否并不存在。业界相似的零碎，包含有 RocksDB，LevelDB 等 LSM-Tree 构造的存储系统，还有 Memcached 外面的 Set 申请，ZippyDB 外面的 Put/Delete/Merge 等次要接口均是如此。意识到这些，置信读者敌人们也会认同「异步共识」的出发点，也可能看清「异步共识」想要打的靶子。
在正式介绍「异步共识」的各类协定之前，咱们要重新学习一下何谓申请的线性序。在传统共识协定的强主模式下，所谓线性序来的是天经地义，然而在异步共识之下，咱们要尝试复原并放弃申请之间的线性序，天然，咱们要十分明确它的要求。上面这个摘自 EPaxos 对于线性序的定义：如果两个申请 γ 和 δ，如果 δ 是在 γ 被确认造成决定之后才发动的，那么咱们就称 δ 是线性依赖的 γ，每个正本状态机都须要先执行 γ，再执行 δ。
Execution linearizability: If two interfering commands γ and δ are serialized by clients (i.e., δ is pro- posed only after γ is committed by any replica), then every replica will execute γ before δ.
这个章节以 SOSP’21 的 Skyros 为例来介绍异步共识，它是属于依赖偏序复原线性序的流派。咱们认为这篇文章在提取异步共识的利用场景这方面做的十分杰出。如下图 14 所示，Skyros 的思路很简略，在同步复制阶段引入一个 Leader，客户端间接写包含 Leader 在内的 super-majority 的正本，一旦返回则申请实现。在失常状况下，后盾以 Leader 的申请程序作为执行程序，按照该申请程序执行状态机；在 Leader 节点挂掉的状况下，残余正本中选举出新的 Leader，收集存活正本中申请的偏序汇合，尝试复原申请之间理论的线性序（这里的做法很大水平上会参考 EPaxos 的图排序算法），而后持续履行 Leader 的职责。通过这样的设计，Skyros 实现了极致的一跳申请决定提交提早，并且这个计划看起来非常简单，是不是？
$$
图 14. Skyros 明确提出推延定序以及执行过程，极致优化提议过程
$$
绝大多数时候，事实没有设想的那么美妙，当然，也没有设想的那么蹩脚。Skyros 美妙的有些不实在。事实也如此，在 Skyros 的机制外面，很大篇幅是在解决一旦 Leader 挂掉之后，新入选的 Leader 如何复原出曾经长久化的申请之间的线性程序，这里理论新的 Leader 可能利用的信息只有申请在每个正本上的偏序关系，然而咱们发现这些信息并不足以撑持线性程序的复原！图 15 给出了一个咱们用来证伪 Skyros 的简略例子，有三个申请 W1，W2，W3，有四个正本 R1，R2，R3，R4，其中 R4 是 Leader，从理论事实来看，能够确定是 W1 是先产生的，线性程序早于 W2，而 W3 则是跟 W1 以及 W2 齐全并发的一个申请。此时如果正本 R4 挂掉了，试问，此时依据什么信息可能推断得出这个理论的线性序。毕竟，此时依据残余节点上申请的偏序关系，你失去了 W1，W2，W3 之间的循环依赖，并且，没有更多的信息可能反对破除这个循环依赖！
$$
图 15. Skyros 的依赖偏序对来推导线性序的做法有概率存在循环依赖，无奈破环
$$
来自 EuroSys’21 的 Tempo 找到了可能是解决异步共识里线性定序难题的最佳计划：引入逻辑工夫戳。咱们即使从直观上感触，也会感觉逻辑工夫戳的计划确实更加高效，毕竟相较于 EPaxos/Skyros 动不动就给你上个图排序，逻辑工夫戳的间接比大小的线性定序办法要简略很多。在 Tempo 中，每个提议申请会有指定的 Coordinator 来负责最终决定申请的逻辑工夫戳，它收集各正本曾经调配的逻辑序号状况，确定具体调配哪个工夫戳序号给相干申请，并且这样的调配要确保起初的申请不会被调配更小的逻辑序号。对于可能产生的提议抵触的状况，Tempo 参考了 Fast Paxos 来解决，多走几轮共识给有抵触的提议申请提供确定、线性的逻辑工夫戳调配。思路大体如此。Tempo 引入工夫戳的做法很有新意，然而一方面引入独自的 Coordinator 角色，另一方面依赖 Fast Paxos 仲裁提议抵触。整体的协定复杂度又上来了，不利于工业落地实现。
3.5 铁血文化
共识协定对于有状态的分布式系统至关重要，事实的状况是，一个有状态的分布式系统可能破费了九牛二虎之力才把一个共识协定实现正确并且无效运维起来。然而接下来面临的问题是，这个贵重的积攒很难间接复制到另外一个零碎，并且这个零碎也就绑定上了一开始抉择的共识协定，简直没有可能持续演进迭代至全新的共识协定。以 Apache ZooKeeper 为例，其至今应用的共识协定还是十多年前的 ZAB，并且该共识协定也没有被 ZooKeeper 以外其它零碎所采纳。咱们看看其它畛域，像 OS 操作系统，像 Network 网络系统等，这些零碎的模块化以及清晰的分层设计使得新的机制甚至是现有机制的迭代都可能以可插拔的形式被疾速引入，促成了这些技术畛域的蓬勃发展。看着真是眼馋呀，咱们不禁要问，共识协定可能实现这样可移植，可插拔，热降级吗？当然，这个其实也就是 Corfu/Delos 等共识协定发力的点，指标 Replication-as-a-Service，打造出属于共识协定的的铁血文化！
首先要探讨一个问题，咱们是否以 LIB 模式提供通用一致性引擎库？答曰，很难。不可行的起因是各种共识协定譬如 Multi Paxos，Raft，ZAB 以及 EPaxos 等等，语义差异还是很大的，很难给出一个通用的接口可能兼容现有的这些共识协定。持续来探讨第二个问题，应用确定的某个共识协定的一致性引擎库，老本高吗？答曰，很高。尽管说像 Braft 等开源库在接口设计上曾经尽量简洁了，然而作为一个库，本身没有状态，必然要裸露状态治理的细节，譬如角色信息、成员信息、甚至镜像信息等给到业务过程并与之耦合，包含状态机的 runtime consistency 查看等等，所以要用正确用好任何一个开源的一致性引擎库，是须要业务长年累月地打磨投入的。最初再探讨一个问题，作为一致性引擎库，可能反对继续演进包含协定的更新换代吗？答曰，至今没见过 ……
$$
图 16. Share Log 对共识协定做了形象，暗藏了实现细节，有利于模块解耦独立演进
$$
聊回这个章节的配角，Share Log，这个我认为也是 NSDI’12 Corfu 这篇文章最为出彩的奉献，为共识协定提供了一个简略奢侈而又精准的形象（这外面学习到一个情理：当咱们对一个问题无奈给出通用解释的时候，那么肯定是形象的还不够），答案就是日志序列，这个日志序列是可容错，强统一，反对线性定序的可追加日志序列。如图 16 所示，Share Log 提供的 APIs 有如下四个：
- O = append(V)：追加日志 V，返回日志所占据的逻辑序号 O；
- V = read(O)：读取逻辑序号 O 对应的日志；
- trim(O)：标记逻辑序号 O（包含之前的序号）对应的日志不再须要，可清理；
- check()：返回下一个可写的逻辑序号 O；
相当于，下层业务状态机基于 Share Log 的接口来实现具体业务逻辑，无需关怀长久化、线性放弃、一致性等难点技术。以复制状态机模型为例，业务状态机间接向底层的 Share Log 追加日志，Share Log 外部应用共识协定将日志复制到其它节点，业务状态机从 Share Log 中学习最新日志，顺次利用到状态机。基于这层形象，共识协定的细节被暗藏在 Share Log 外部，业务逻辑和共识协定能够独立演进，互不影响，并且 Share Log 能够做成通用模块，移植给不同的业务应用。事实上，Share Log 这层形象是那么的简略奢侈并且精确，相似这种机制曾经成为了古代分布式系统设计的基石，咱们来看到 Share Log 广泛应用的三大场景：
- Pub/Sub：共享日志其中一大利用场景是作为可扩缩的异步消息传递服务，将生成音讯的服务与解决这些音讯的服务拆散开来。这种解耦的设计大大简化了分布式应用开发，Pub/Sub 在生产零碎中被宽泛部署利用。各大云厂商也都推出了音讯队列的重磅产品，譬如 Alibaba MQ，Amazon Kinesis，Google Pub/Sub，IBM MQ，Microsoft Event Hubs 以及 Oracle Messaging Cloud Service。音讯队列对日志需要是持久性（durability），惟一定序（uniquely ordered）以及线性定序（linearizability）。Share Log 天然可能满足此类场景需要。分布式存储系统在做跨地区容灾的时候，异步复制计划通常要求对 IO 链路的影响降到最低，同时尽可能地升高 RPO，此时规范的技术选型就是基于音讯队列来拖 Redo Log；
- Distributed Journal：LSM-Tree 在古代存储系统中失去了广泛应用，该这外面要害的 journaling 机制很好地解决了写放大问题，每次仅长久化增量的更改数据，而不须要全量数据长久化，同时通过严格程序写入的设计大幅晋升了写入性能，对于写多读少的场景尤其的敌对。在分布式场景下，journaling 也会降级为一个 append-only 的分布式日志零碎，相似 GFS、HDFS 等等。这正是 Share Log 主打场景。依据业务申请是否须要即时外显，又细分出两个场景：1）要求即时外显，那么这里的 append-only 的分布式日志零碎必须单写，即同一时间某个文件最多只容许一个客户端操作，否则状态机 APPLY 的申请序列与长久化的日志序列可能不一样，failover 场景下数据一致性将被突破。此时分布式日志对日志的需要是持久性（durability），外显性（externality），惟一定序（uniquely ordered），以及线性定序（linearizability）；2）不要求即时外显，这里的 append-only 的分布式日志零碎须要反对多写定序，最大水平晋升拜访吞吐，升高申请提早。此时分布式日志对日志的需要是持久性（durability），可定序（orderable）以及线性定序（linearizability）；
- Replicated State Machie：如前文所言，复制状态机模型是以后有状态的分布式系统宽泛采纳的容错机制。正如图 1 外面形容的，Share Log 能够面向复制状态机提供线性枯燥，强统一，可容错的日志序列，再适合不过了。复制状态机对日志的需要是持久性（durability），外显性（externality），惟一定序（uniquely ordered），以及线性定序（linearizability）。事实上，传统的消息中间件 Apache Kafka，Apache Pulsar 同样可能胜任此职责（所谓艺多不压身，Kafka 这类中间件曾经打造的十八般武艺样样精通），业界很多数据库公司也是基于音讯队列解决了同步复制的需要。该场景下，Share Log 处于业务的间接 IO 依赖，事实上是跟业务耦合了，因而会产生新的挑战。以基于分区调度架构的分布式存储场景为例，其在依赖 Share Log 的时候，如何反对业务的分区变配（即保障变配前后日志线性程序）就变得很辣手；
自从 Corfu 提出了 Share Log 这个概念之后，钻研畛域相继推出 Tango，Scalog 以及 Chariots 等演进版本，工业界外面 CorfuDB，LogDevice，Aurora 也都借鉴了相似 Share Log 的设计思维，实现了共识协定的平替。仔细的读者应该还记得咱们的第三问，共识协定可能反对可插拔，热降级吗？这个就要提到 Corfu 之后集大成者 Delos 了。事实上，共识协定本身也是存在管制与数据立体的，其中管制立体负责选主，元数据管理，成员变更，服务容错等简单能力，而数据立体仅仅须要定序以及数据长久化。相似 Multi Paxos/Raft/ZAB 等传统共识协定耦合了管制与数据立体，事实上，Share Log 对外展现的恰好就是共识协定的数据立体，这个是能够解耦进去独自演进的，而这也就是 Delos 外面推出的所谓 Virtual Log 的思路。总结起来就是，让传统的共识协定负责管制立体的实现，而数据立体仅负责日志定序及数据长久化，因而能够有各种更加高效的实现（有点套娃的意思，共识外面套共识）。这个思路在业界并不陈腐，曾经被宽泛采纳，譬如 Apache Kafka 外面即应用 Apache ZooKeeper（新版本是自研的 KRaft）来治理元数据的管制立体，应用 ISR 协定负责高吞吐灵便的数据立体；Apache BookKeeper（这个读者可能会比拟生疏，基于它长进去的 EventBus，Pulsar，DistributedLog，Pravega 等明星开源产品，你总据说过一款吧）也是应用了 Apache ZooKeeper 来做管制立体治理，而自研的 Quorum 协定负责高吞吐的写以及低提早的读；相似的例子还有很多，像 Microsoft 的 PacificA 也是采纳管控数据立体拆散的架构。
$$
图 17. Facebook Delos 的共识技术架构，在共识迭代这块可插拔反对热降级
$$
当然，出身名门的 Delos 做了更多形象，特地是创新性地在 Share Log 根底 API 之上，引入 SEAL 能力。如图 17 所示，Delos 反对客户端通过 SEAL 接口将前一个日志序列禁写（譬如原先是基于 ZK 共识协定实现的申请定序），进而开启全新的可写日志序列（新的能够是基于 Raft 实现的申请定序），通过这样的实现达到了 Share Log 底层的共识协定可能热切换热降级的目标。这个是不是很好地解答了咱们的第三问？
在这个章节的最初，我要特地举荐一下赫赫有名的 Jay Kreps 在 2013 年发表的大作《The Log: What every software engineer should know about real-time data’s unifying abstraction》。这个文章真的十分不错，值得大家耐着性子好好读一读。Jay Kreps 把日志这个概念讲的十分分明，以一个十分广的视角揭示了日志其实是很多分布式系统最实质的货色，解释了为什么日志是更好的形象（绝对于共识协定自身）。如果用一段话来概括日志对于分布式系统的意义，那么我认为应该是文章里的这段形容：
At this point you might be wondering why it is worth talking about something so simple? How is a append-only sequence of records in any way related to data systems? The answer is that logs have a specific purpose: they record what happened and when. For distributed data systems this is, in many ways, the very heart of the problem.
事实上，作为 Kafka 创始人之一，Jay Kreps 在文中也预言了日志最终应该会做成通用的产品组件，在分布式系统中将被宽泛应用。无关日志的深度思考，对于 Jay Kreps 本人也很重要，他集体命运的齿轮开始转动 ……，很快推出了 Kafka（这个应该不必多做一句介绍吧？），商业化也做的十分的胜利（它的一个口号是：More than 80% of all Fortune 100 companies trust, and use Kafka ……，母公司 Confluent 的最新市值也曾经达到了 100 亿美金）。另外，有个有意思的小插曲，在发表这篇日志博文的时候，Raft 刚面世，Jay Kreps 对这个协定十分的赏识，文中也强力举荐了 Raft，真堪称英雄惜英雄也。
这个章节也聊了那么多，总结起来是，Share Log 对共识协定对了很好的形象，标准化了共识协定对外的应用界面，实现了可插拔；进一步的形象来自升级版的 Virtual Log，通过管制立体与数据立体的拆散，实现了共识协定热降级的现实。如果说还可能进一步再形象的话，咱们认为那应该是以 Kafka/Pulsar 为首的日志复制服务所代表的 Replication-as-a-Service（RaaS）的趋势。随着云原生大潮的降临，应用程序开发者肯定须要学会借力开发，升高业务零碎的复杂性，譬如能够应用 RaaS 解决状态同步问题，能够采纳 OSS 等元原生存储解决状态存储问题，以及能够倚赖 Etcd/ZooKeeper 等组件解决状态治理问题等等。
3.6 帝国烽火
哇呜，能保持看到当初的你们，确实是共识协定的真爱粉。咱们可能领略到，这么些年钻研工作者们在跟随着 Lamport 巨匠指引的方向上，逐渐建设起了宏大的共识帝国。不过，以上咱们介绍的所有钻研方向都是软件算法层面的优化。而在这个章节，咱们将讲述的是全新的软硬一体化视角下的共识协定钻研工作。在智能网卡，RDMA，可编程交换机等数据中心的各类技术疾速倒退的当下，摸索共识协定硬件卸载（offline）的各种可能性，很多时候可能突破咱们的既定认知，带来降维打击般的改良成果。所以，这个章节，咱们选用“帝国烽火”作为题目来揭示传统的共识协定的钻研人员。话说这个题目起的呀，一个字，绝！
大体上，咱们能够把迄今为止软硬一体化方向的共识协定的钻研工作分成三类：1）随着数据中心技术的疾速迭代，预期网络能够提供更多的承诺，譬如牢靠传输不丢包，譬如可线性定序的传输。基于这样的假设，共识协定围绕着异步网络（信息传输回失落，乱序，超时等等）做的很多简单设计能够拿掉，进而更简略更高效地达成决定；2）可编程的交换机技术的疾速倒退，提供了将整个共识协定的三阶段能力都卸载到交换机上的可能性，这将相当于把共识变成网络提供的原语服务。从提议申请的解决吞吐角度而言，交换机的能力显然是要远胜于节点的 CPU 能力，那么能够预期共识吞吐能够取得几个数量级的晋升；3）异步共识很适宜存储畛域的分布式日志场景，其中数据复制逻辑简略，对稳定性要求高，吞吐提早的指标也很敏感，比拟适宜将这部分逻辑卸载到智能网卡外面实现。而线性定序以及状态机执行者两个阶段逻辑简单，能够保留在软件层面灵便管制，异步地执行。
$$
图 18. 随着对网络依赖的强弱变动，所谓共识的实现难度会产生巨大变化
$$
咱们首先来看第一类钻研工作，减少网络能力的承诺。咱们晓得，Lamport 提出共识协定时候对于网络的假如是齐全异步的，也就是说信息传输可能会失落，可能会乱序，也可能产生提早抖动甚至超时等等。基于这样的假如，Paxos 等共识从协定层面减少了各种设计，保障了一致性的性质，然而也减少了软件复杂性并且存在执行效率的瓶颈。必须得说，Lamport 的异步网络假设对于 Internet 网络是正当的人设设定。不过以后数据中心内的网络状态显然要可控多了，是否提供一些可靠性的保障呢？如图 18 所示，事实上，如果网络侧可能做出更多可靠性承诺，共识达成的难度会升高很多。这个方向曾经有很多相干研究成果，譬如 NetPaxos，Speculative Paxos，NOPaxos，Hydra 等。这里咱们着重介绍一下来自 OSDI’16 的 NOPaxos（留神，这个取名是抖了个伶俐，理论是指 Network Ordering Paxos），它的假设即网络能够提供牢靠的定序保障，尽管可能会失落一些链路的申请包。
$$
图 19. NOPaxos 定义的反对全局定序的申请播送接口，相干性能卸载到交换机实现
$$
具体来说，NOPaxos 定义了一组名为 OUM（Ordered Unreliable Multicast）的网络接口，通过可编程的交换机（例如 P4）在交换机硬件上间接反对这样的播送接口，如图 19。在指定的网络定序者（最佳抉择是基于可编程交换机实现）为每个 OUM 组都保护了一个计数器，在每个转发过去的 OUM 申请的包头填充严格间断递增的计数。最终达成的成果如图 20 所示，包含 Leader 在内的各个正本收到的申请是严格有序的，失常状况下都不须要有协同动作，十分高效。每个正本本人会查看是否产生丢包，如果产生了丢包，非 Leader 正本向 Leader 学习具体失落的申请包；Leader 正本则通过 NO-OP 申请走 Basic Paxos 来学习失落的申请包。另外，客户端一旦收到包含 Leader 在内的多数派正本的申请回复，即可认为申请实现，这里仅仅须要一跳网络提早。
当然，NOPaxos 这个工作存在一个设计上的硬伤，即作为定序的交换机是个单点，这个就导致了零碎在可扩展性、容错性以及负载平衡等诸多方面存在限度。这个工作的连续是 Hydra，进一步引入多台交换机来做定序，缓解了上述的单点瓶颈。可能读到这里，读者敌人们会有点诧异，看了共识畛域其余门派各种精美简单的协定设计，这个来自 OSDI’16 的 NOPaxos 共识协定是不是有点简略过头了？好吧，确实有点降维打击的滋味，事实上，如果网络定序自身不是问题的话，复制的难度确实没有那么大。对该方向感兴趣的读者敌人们能够持续钻研下 Hydra，Speculative Paxos 等工作，感触下更牢靠的网络是如何无效晋升共识的。
$$
图 20. NOPaxos 利用交换机的定序能力实现了高效一跳共识，容错、成员变更等能力由软件侧保障
$$
咱们持续看第二类钻研工作，整个卸载掉共识的能力。这个方向的代表作是 P4xos，看这个协定的名字就明确是把共识的能力间接给卸载到了 P4 可编程交换机。如图 21 所示，P4xos 的工作是在数据中心基于传统的三层网络架构来设计的，所有的申请会通过 ToR（Top of Rack）交换机，Aggregate 汇聚交换机，以及 Spine 外围交换机。基于这种网络架构，咱们看到传统的 Paxos 共识协定从 Proposer 提议到 Leader 学到决定共经验 3 /2 RTT。P4xos 把三层网络架构下的交换机都安顿成共识协定中的角色：Spine 外围交换机做 Leader 定序，Aggregate 汇聚交换机做 Accept 接管决定，ToR 交换机则做 Learner 学习决定。整个链路下来仅须要 RTT/2。我想聊到当初，大家应该也有点感觉到传统共识协定的瓶颈之所在：从提早上来讲，次要耗费在网络传输；从整体吞吐上来讲，次要瓶颈在单机 CPU 解决能力。P4xos 通过将共识三阶段能力整体卸载到 P4 交换机，相较于传统共识协定，不仅仅是提早失去了明显改善，整体的共识吞吐能力有了质的飞跃（P4xos 的论文中声称有 4 个数量级的晋升）。当然，这里选用 Spine 外围交换机做 Leader 定序同样存在单点问题，须要引入传统共识协定的从新选举过程。
$$
图 21. P4xos 尝试全面卸载 Paxos 的共识协定，试验展现了惊人的优化成果
$$
软硬一体化方向的第三类钻研工作，跟前文提到的异步共识的工作严密相干。回顾一下，异步共识将简单的线性定序以及状态机执行等逻辑推延解决，而用户的申请仅仅在后面简略的复制阶段实现即可返回。这个思路跟硬件卸载的极简主义的准则十分符合，实现了存储系统的外围 IO 链路和周边性能拆散，并且无效避免故障扩散，在整个集群管控都不可用的状况下，IO 申请还是能够失常工作。所以试着 YY 一下，下一代存储的技术选型会不会就长这样？行将复制阶段卸载到智能网卡，而将定序、转储的工作放在存储软件侧，从而实现极致高吞吐，极致低提早，稳固高牢靠？
随着时代的演进，软硬一体化技术还在疾速迭代，咱们十分期待并也积极参与了其中。“莫道桑榆晚，为霞尚满天”，咱们置信共识协定可能搭上软硬一体化这列时代的高铁，持续在将来有状态分布式系统的构建中施展着中流砥柱的作用！
四、序幕
写到最初，咱们也不得不感叹，共识真的很重要，共识畛域也真的是钻研红海，凡是你能想到的方面都有一堆钻研工作者在涉猎，这个恰好也验证了共识协定对于分布式系统的至关重要性。写这篇文章，很大一部分目标也在于，通知更多的分布式系统的从业者，共识畛域的研究成果相对不仅仅只有 Paxos/Raft。事实上，随着业务的蓬勃发展，分布式畛域的越来越丰盛的场景都对共识协定提出了更多更新的要求，这里也绝非依附 Paxos/Raft 就能够一招鲜吃遍天的。这个世界很大，大到足以包容 Paxos，Raft，EPaxos，FPaxos, Skyros，P4xos ……
$$
图 22. 希腊群岛被各种类型的共识协定拿来命名，有点不够用了 . .
$$
最初说一个乏味的景象，从新近年 Leslie Lamport 考古希腊群岛，并以其中的 Paxos 小岛命名初始的共识协定开始，这个小岛成为了共识畛域的圣地，至今围绕着 Paxos 岛的很多希腊小岛也都被用来命名新的共识协定，譬如 Corfu，Delos，Skyros，Hydra 等等。所以，加油吧！心愿共识畛域放弃着以后新陈代谢的旺盛势头，尽早把希腊群岛的名字给用光了：）
作者|朱云峰
点击立刻收费试用云产品 开启云上实际之旅！
原文链接
本文为阿里云原创内容，未经容许不得转载