背??景分布式共识算法（ConsensusAlgorithm）是分布式计算领域的一个基本问题。);进而解决分布式系统的可用性问题（高可用）。Paxos是最重要的分布式共识算法，很多人把它当作“分布式共识协议”的代名词（谷歌Chubby服务的发明者MikeBurrows说“只有一种共识协议，那就是Paxos”）.关于Paxos的历史和原理，已经有很多经典论文可以参考，厂内外也有文章有详细的介绍，本文不再赘述。感兴趣的同学可以阅读这些论文[1,2,3,4]。虽然从业界提出Paxos的理论到现在已经17年了，从Paxos第一次工业化实现到现在也到现在已经11年了，但是直到最近几年，无论是最新的会议还是业界，Paxos相关的文章而项目依然层出不穷。转向行业，虽然使用Paxos及其各种变体的产品层出不穷；但真正工业级的、独立的、Paxos基础库还是相当少见：谷歌没有开源任何一个Paxos基础库（甚至包括Paxos开源的项目都没有）；Facebook尚未宣布包含Paxos的产品；Apache有Zookeeper，但是它的协议不支持高吞吐量的状态机复制，也没有提供独立的第三方库来快速访问。在Github上能查到的Paxos的独立库中，星级最高的是去年腾讯开源的phxpaxos（后面会作为竞品进行详细对比）。因此，到目前为止，业界还很少有成熟可靠、可以快速使用的独立第三方Paxos库，开源的Paxos生态还很不成熟。X-Paxos的愿景我们的初衷不是做一个Paxos的公共图书馆。X-Paxos诞生于阿里巴巴的分布式数据库AliSQLX-Cluster，但X-Paxos不属于AliSQLX-Cluster。Paxos是分布式系统的基石，X-Paxos可以用来解决各种分布式系统中的一致性问题。因此，在整个分布式数据库的设计之初，我们就自主设计了分布式共识协议模块，并自主命名为X-Paxos。X-Paxos为AliSQLX-Cluster解决了分布式一致性问题，也可以快速赋予其他系统分布式一致性能力。分布式一致性要求并不是AliSQLX-Cluster独有的。很多系统都有高可用和强一致性的需求。我们把Paxos的能力独立成一个基础库，希望把这个能力带到更多的其他系统中。例如：组内同学将X-Paxos集成到单机KV数据库RocksDB中，快速实现了分布式KV引擎。集团现有业务团队将X-Paxos集成到业务存储系统中，构建全新的分布式强一致存储服务。同时，正是AliSQLX-Cluster让X-Paxos成为可能。Google的论文《Paxos made live》中有一段说的非常好，大意是Paxos的理论与现实世界的实现差距巨大。在实际实现一个Paxos的时候，往往需要做一些经典的PaxosExtension，（尤其是在实现一个高性能的Paxos时，扩展点比较多，可以参考后面的功能增强和性能优化），这往往会导致事实上，真正的Paxos实现实际上是基于一个不完整的Proven协议。这就是为什么说理论证明一个Paxos的实现比这个Paxos的实现更难。因此，一个成熟的Paxos实现很难独立产生，往往需要与一个系统结合，通过一个或多个系统来验证其可靠性和完备性。这也是为什么大部分成熟的Paxos案例都结合了分布式数据库，比如最早的Paxos实现（Chubby），以及目前主要的Paxos实现（Google的MegaStore、Spanner、AWS的DynamoDB、S3等）。X-Paxos依赖于AliSQLX-Cluster来验证其可靠性和完整性。我们的愿景是提供一个经过验证、高度成熟和可靠的独立Paxos基础库。通过简单的接入，让后端服务具备Paxos算法赋予的强一致性、高可用、自动容灾等能力。真正把难懂易懂的Paxos做起来，带进千家万户。架构X-Paxos的整体架构如上图所示，可以分为网络层、服务层、算法模块、日志模块四个部分。网络层是基于阿里内部非常成熟的网络库libeasy实现的。libeasy的异步框架和线程池非常适合我们整体的异步设计。同时，我们修改了libeasy的重连逻辑，以满足分布式协议的需要。服务层服务层是驱动整个Paxos运行的基础。它为Paxos提供了事件驱动、定时回调等核心操作功能。每个Paxos实现都有一个与之密切相关的驱动层。驱动层的架构、性能和稳定性密切相关。X-Paxos的服务层是一个基于C++11特性实现的多线程异步框架。常见的状态机/回调模型存在开发效率低、可读性差等问题，被开发者诟病；而协程由于其单线程的瓶颈，在应用场景上受到限制。C++11之后的新版本提供了参数转发和可变参数模板等特性，使我们可以实现一种新的异步调用模型。例如，这是X-Paxos中创建单个计划任务的实际代码行(),log_->getLastLogIndex());上面一行程序包括定时器的创建，任意回调函数的设置，回调函数参数的转发，以及保证触发回调后内存的自动回收（Oneshot）。同时，服务层支持嵌套回调，即在回调函数中再次生成定时/即时任务，实现有限的定时循环逻辑。算法模块X-Paxos目前的算法是基于uniqueproposer的multi-paxos[3]实现的。大量的理论和实践证明，uniqueproposer-basedmulti-paxos比multi-paxos/basicpaxos具有更好的性能。目前成熟的基于Paxos的系统大部分采用了这种方式。算法模块的基本功能本文不再赘述，感兴趣的同学可以参考相关论文[1,2,4]。X-Paxos在基础算法的基础上，结合阿里业务场景和高性能、生态需求，做了很多功能创新和性能优化，使其比基础的multi-paxos功能丰富，性能有了显着提升在各种部署场景中得到改进。在下一章中，将详细介绍这些优化。日志模块日志模块本来是算法模块的一部分，但是出于对最佳性能需求的考虑，我们将日志模块分离出来，实现了一个默认的高性能日志模块；具有最佳的性能和成本需求用户可以结合现有的日志系统，接入日志模块接口，获得更高的性能和更低的成本。这也是X-Paxos作为高性能独立库的独特优势，下一章会详细介绍。功能增强结合广泛的业务场景构建开放生态1.在线增删节点，在线转移leaderX-Paxos在标准multi-paxos的基础上，支持在线增删多角色节点，以及支持快速在线转移领导节点转移到其他节点（有主选举）。2.主力集团的战略多数和加权选择以及蚂蚁目前的多中心结构。由于很多应用的部署特点，在没有市级容灾的情况下，往往需要只写在中心。数据库，或者调用其他分布式服务；同时要求在市级容灾时（同城多个机房全部不可用），写入点可以切换到非中心。经典的multi-paxos无法满足这些要求。经典理论中，多数可以在强同步后完成提交，但多数是非特定的，不保证某个/某个节点一定能够获取到完整的数据并激活服务。在实际实现中，地理位置较近的节点往往具有强一致性数据，而地理位置较远的节点始终是非强一致性节点，在容灾时永远无法激活为主节点，无用。同时，当中心单个节点出现故障需要容灾时，往往需要将主节点切换到就近的同一中心的另一个节点；因为应用在多地的部署往往是不对称的，只有当单个region全面宕机时，Writing才需要将master节点切到特定的region中。这些需求要求Paxos允许用户在选择leader时指定规则，而经典理论中没有类似的功能，而且增加权重也需要保证Paxos的正确性。X-Paxos在协议中实现了策略多数和加权选举。基于策略多数，用户可以通过动态配置指定某个/某些节点必须保持强一致性数据，当有容灾需要时可以立即激活为主节点。基于加权选举，用户可以指定每个节点的选举权重，只有当所有高权重节点都不可用时，才会激活低权重节点。3、节点角色自定义（独立配置Proposer/Accepter/Learner）在经典的multi-paxos实现中，一般每个节点都包括Proposer/Accepter/Learner这三个功能，每个节点都是一个全功能节点。但有些情况下我们并不需要所有的节点都具备所有的功能，例如：在经典的三副本部署中，我们可以将其中一个节点的状态机切掉，只保留日志（没有数据的纯日志节点，但在Synchronization中作为多数计算），这时我们需要把协议中的Proposer功能（被选举权）裁掉，保留Accepter和Learner功能。我们希望有几个节点可以作为下游，订阅/消费协议产生的日志流，而不是集群的成员（不算多数，因为这些节点不保存日志流），此时我们砍掉协议的Proposer/Accepter功能，只保留Learner功能，当然还有其他组合。通过节点角色的自定义组合，我们可以开发出很多自定义的功能节点，既节省了成本，又丰富了功能。4.WitnessSDK基于上节节点角色自定义中的个体Learner角色的功能，引发无限想象。Learner角色可以抽象为数据流订阅者（WitnessNode）。可以将无数订阅者添加到整个集群。当有新的日志提交时，这些订阅者会收到他们关心的日志流，基于subscription，我们可以让集群轻松实现下游订阅消费、日志实时备份、配置变更推送等功能。因此，我们将Learner角色单独打包成一个SDK。基于此SDK，用户可以快速为自己的集群添加、订阅注册、流式订阅设置功能；结合特定用途，打造完整生态。例如AliSQLX-Cluster:X-Paxos中日志流SDK打造的生态，也可以借助WitnessSDK快速实现分布式系统与其他下游系统的连接，形成完整的生态。以MySQL的日志（binlog）备份为例：常见方案?每隔固定时间Tb，将MySQL产生的binlog文件备份到最新的备份系统（OSS、S3等）?RPO（RecoveryPointObjective）是TbSDK方案?X-Paxos支持SDK订阅增量日志。备份系统只需要简单地将SDK流程接入OSS流程即可实现流式备份。?RPO（RecoveryPointObjective）为0，除了备份，WitnessSDK在下游有实际案例在流式订阅（DRC）、自闭高可用系统（X-Driver）、异步只读备库，以及更多的应用案例在不断的添加中。性能优化我们一直坚信网络延迟不应该影响吞吐量1.Batching&PipeliningPaxos除了在设计之初的强一致性和高可用性之外，其高性能也至关重要，尤其是对于高性能的分布式如AliSQLX-Cluster在使用数据库时，对协议的吞吐量和时延有很高的要求。同时，作为一种可以全球部署的分布式共识协议，高延迟下的性能挑战变得尤为重要。X-Paxos针对高延迟网络做了很多协议优化尝试和测试，并结合学术界已有的理论成果[5,6,7]，通过合理的Batching和Pipelining，设计并实现了一套自适应的通信high-latencyhigh-throughput和low-latencyhigh-throughputnetwork的模式大大提升了X-Paxos的性能（对比见下一节）。类似的优化在同类竞品中非常少见。批处理是指将多条日志组合成一条消息发送；批处理可以有效减少消息粒度带来的额外损失，提高吞吐量。但是Batching过大很容易造成单个请求的延迟过大，导致并发请求数很高，进而影响吞吐量和请求延迟。流水线是指在上一条消息的结果返回之前，将下一条消息并发发送到相应节点的机制。通过增加并发发送消息的数量（Pipeliningnumber），可以有效降低并发单次请求的延迟。同时，当传输延迟小于传播延迟时间（高延迟高吞吐网络），有效提升性能。经过推导可以看出Batching（消息大小：M）和Pipeling（消息并发数：P）在如下关系下可以达到最大吞吐量M/R*P=D，其中R为网络带宽，D为网络传播延迟（propagationdelay,AboutRTT/2）X-Paxos结合以上理论，通过内置检测，根据不同节点的部署延迟，自适应调整每个节点的Batching和Pipeling参数，实现整体最大吞吐量。Pipeling的引入需要解决日志的乱序问题，尤其是在远程场景下，窗口大小增大，增加了日志乱序的概率。X-Paxos实现了高效的乱序处理模块，可以为底层日志屏蔽乱序问题，实现高效的乱序日志存储。2.多线程、全异步的Paxos库由于Paxos内部状态的复杂性，实现高效的单实例多线程Paxos成为了一个非常大的挑战。不管我们上面提到的github中star最多的phxpaxos，还是OracleMySQLGroupReplication中使用的xcom，都是单线程实现的。Phxpaxos采用单分区单线程多实例聚合来提高总吞吐量，但单分区的性能非常有限；而xcom是基于协程的单线程实现。单线程Paxos实现在处理序列化/反序列化、分发、包投递等逻辑时串行执行，性能瓶颈明显。X-Paxos是完全基于多线程实现的。Paxos可以在单个分区中充分利用多线程能力。所有任务都由一个普通的woker运行，从而消除了CPU瓶颈。依托服务层和异步网络层的多线程异步框架，X-Paxos可以并发执行除必要的协议串口外的大部分操作，部分协议串口采用无锁设计，可以有效利用多线程能力实现了Paxos的单分区多线程能力，其单分区性能远超竞品，甚至超越了多分区竞品的分区性能。3.LocalityAwareContentDistribution基于唯一提议者的分布式系统的一个瓶颈点是主节点是唯一的内容输出源。当集群中节点数量较多时，主节点大量的网络收发任务会导致主节点负载过载。大，造成CPU和带宽瓶颈；在全国/全球部署中，所有节点与主节点直接通信，会造成区域间长途/国际链路带宽占用过大。X-Paxos是一个独立的Paxos库，旨在解决全局分布式强一致性问题，在设计之初就已经考虑到了。X-Paxos在稳定运行时会感知各节点间的网络延迟（物理距离），形成级联拓扑，有效降低主节点的负载，减少长距离链路的带宽占用；届时，它会自动重新组织拓扑结构，以保证存活节点之间的对等体的正常进行。同时，X-Paxos支持业务设置拓扑重组规则。业务可以根据自己的APP部署架构和时延特点，设置拓扑重组规则。4.可插拔日志X-Paxos与大多数现有的paxos库的最大区别在于X-Paxos支持可插拔日志模块。日志模块是Paxos中的一个重要模块。它的持久化关系到数据的一致性，它的读写性能会极大地影响协议的整体读写性能。目前大多数独立的Paxos库都内置了日志模块，不支持插件化。这样会带来两个弊端：默认的日志模块提供了通用的功能，很难结合特定的系统进行针对性的优化。现有系统往往已经有了WAL（WriteAheadLog），需要重新存储Paxos协议。一份。这使得a)单个提交需要在本地同步两次（影响性能）；b)双日志浪费大量存储空间。例如：phxpaxos内置的日志模块使用的是LevelDB。表现堪忧；同时使用phxpaxos的phxsql单节点需要同时保存binlog和Paxos日志（在独立的phxbinlogsvr中），严重影响性能，浪费存储空间。使用X-Paxos的AliSQLX-Cluster直接将已有的binlog模块改造，接入X-Paxos的日志模块。单个节点只有一个日志，减少存储，提高性能。分布式正确性验证对于分布式强共识协议，正确性是生命线。如上所述，分布式强共识协议很难在一个完整的理论中证明其正确性。再加上工程实施的问题，难度就更大了。我们用了大量的理论和技术手段，从理论和工程上保证了X-Paxos的正确性和完备性。1.JepsenJepsen是开源社区公认的分布式数据库测试框架。Jepsen验证了包括VoltDB、CockroachDB、Galera、MongoDB等几乎所有主流分布式数据库/系统，发现了很多问题。X-Paxos完成了与Jepsen的对接，验证了各分布式数据库的已有案例。2.TLA+TLA+是Paxos创始人、图灵奖获得者LeslieLamport发明的形式化规范语言。TLA+致力于设计、建模和验证分布式并发系统。AmazonDynamoDB/S3/EBSMicrosoftCosmosDB已经通过了TLA+模型验证，发现了很多问题。目前X-Paxos已经通过TLA+模型验证。3.随机异常系统我们构建了自动随机异常验证系统，可以在各种异常场景下自动验证协议的正确性和稳定性。验证X-Paxos在模拟网络丢包、闪断、隔离、磁盘故障等方面的正确功能和数据一致性。4.异常回归系统X-Paxos有异常情况回归系统。将已发生或预计并发的异常案例添加到异常案例库中，进行日常回归验证。同时，异常案例库也在不断丰富。竞品分析比较XCOM（MySQLGroupReplication）MySQLGroupReplication是基于Galera思想，在MySQL上构建分布式强一致性集群的MySQL插件。MySQLGroupReplication早期采用的分布式协议是CoroSync，它是RedHat基于Totem（TheTotemSingle-RingOrderingandMembershipProtocol）[8]协议开发的分布式共识协议库；由于Totem算法本身存在一些性能受限的原因，从MySQL5.7.9开始，官方采用了自主研发的基于Paxos(Mencius)[10]的一致性协议库XCOM。XCOM是MySQLGroupReplication的核心组件，称为GroupCommunicationCore[9]。我们分析了XCOM的源代码。XCOM内部是一个由纯C语言编写的核心模块和一个由C++实现的proxy实现的系统。纯C模块由单线程驱动，依赖协程实现任务调度。所以客户端（MySQLGroupReplication插件）必须使用tcp连接向XCOM发送请求。因此XCOM存在以下不足：1.单线程驱动，无多线程能力架构决定，难以突破2.通信流程需要额外的TCP协议栈。一个网络通信难以接受3.XCOM虽然实现了Batching和Pipelining，但是它们的值都是固定值，很难适应真实场景。在Region场景下表现非常不理想（参见AliSQLX-Cluster对比测试）phxpaxos（phxsql）phxpaxos是腾讯推出的基于Paxos协议的独立库。与MySQL结合后推出了phxsql项目，也是一个基于MySQL的分布式强大库。一致的MySQL集群。phxpaxos可以独立用于其他项目，是目前github上star最多（1000+）的Paxos独立库。phxsql的细节本文不再赘述，可以参考（AliSQLX-Cluster竞品分析篇），我们这里主要分析phxpaxos。phxpaxos也是一个基于multi-Paxos的独立库。其架构采用single-Paxos单线程设计，但支持多个Paxos分区扩展多线程能力。这种扩展需要预先对多个数据进行分区。因此，phxpaxos的不足之处在于：单个Paxos对象只支持单线程；可以支持多个Paxos对象，共享网络层不支持流水线。在跨Region环境下（高延迟），几乎不可能使用多日志冗余。日常基于LevelDB的系统性能瓶颈性能对比，我们依然使用腾讯的phxpaxos作为竞品进行对比（XCOM没有独立组件，可以间接参考MySQLGroupReplication和AliSQLX的对比测试结果-簇）。我们分别在a)Region3节点部署b)3个Region各节点部署调整下，以不同的请求大小进行压测。从上面两张对比图可以看出，X-Paxos在同一Region下的性能是phxpaxos的100多倍。在跨Region场景下，phxpaxos几乎不可用，而X-Paxos只有3.5%的下降几乎不影响吞吐量。当前状态和未来状态目前X-Paxos第一期已经发布上??线。基于X-Paxos的集团数据库团队产品AliSQLX-Cluster已在集团内广泛应用。X-Paxos与业务系统结合打造的分布式服务也相继上线。未来，Paxos将成为分布式系统的基石。甚至近年来，关于Paxos和新的演进方向的学术文章也不断涌现。我们的X-Paxos会不断的发展，更好的适应集团内外部的需求，未来的主要发展方向如下：高效，多分区支持?基于新的异步框架，实现深度底层共享多分区partitionPaxos多节点强一致性读?经典的multi-paxos只能在leader上提供强一致性读，Spanner和业界已经有一些解决方案可以在多节点上提供强一致性读，但是仍然存在明显的缺陷。【本文为专栏作者《阿里巴巴官方技术》原创稿件，转载请联系原作者】点此查看作者更多好文
