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等等。所以，加油吧！心愿共识畛域放弃着以后新陈代谢的旺盛势头，尽早把希腊群岛的名字给用光了：）

作者｜朱云峰

点击立刻收费试用云产品 开启云上实际之旅！

原文链接

本文为阿里云原创内容，未经容许不得转载