PolarDB-X 一致性共识协议 (X-Paxos)

背景

分布式一致性算法（Consensus Algorithm ）是一个分布式计算领域的基础性问题，其最基本的功能是为了在多个进程之间对某个（某些） 值达成一致（强一致），进而解决分布式系统的可用性（高可用）。Paxos是最重要的分布式一致性算法，很多人都把它作为“分布式一致性协议”的代名词（Mike Burrows, inventor of the Chubby service at Google, says that “there is only one consensus protocol, and that’s Paxos”）。

回顾Paxos的理论从1990年提出到现在已经有近30年了，但是真正工业级、独立的Paxos基础库还是相当的少见。Google并没有开源其任何Paxos基础库（连包含Paxos的项目都没有开源过）；Facebook也没有公布过包含paxos的产品; Apache有Zookeeper，但是其协议并不能支持一个高吞吐的状态机复制，且并没有提供独立的第三方库，可供快速接入；在Github上能找到的Paxos的独立库，star数最高是腾讯云开源的phxpaxos库，18年之后也基本没有更新。

近几年NewSQL和云原生数据库的不断兴起，极大地推动了关系数据库和一致性协议的结合，PolarDB-X也是在这样的背景下应运而生。

X-Paxos 诞生和发展

2014年，阿里随着业务的高速增长，同城主备部署的方式已经无法满足阿里对可扩展的部署、国际化、以及容灾方面的需求，“异地多活”成为了公司应用的新标准。基于这样的业务背景驱动，PolarDB-X早期，在阿里集团MySQL设计了分布式一致性协议模块，并把它独立命名为X-Paxos，基于单机MySQL实现了一致性能力，配合TDDL分库分表的模式部分解决了业务诉求。随着技术的不断发展和演进，以及面向云的时代的全面普及，我们PolarDB-X 2.0中融合了分布式SQL引擎和基于X-Paxos的数据库存储技术，提供全新的云原生分布式数据库。

在PolarDB-X 2.0中，我们也进一步扩展了分布式和Paxos的协同，比如多副本的一致性读、副本的动态迁移和管理能力等。反过来，PolarDB-X有了X-Paxos的加持，可以做到金融级数据库的高可用和容灾能力，做到RPO=0的生产级别可用性。Paxos协议对于面向云的架构是非常必要的，云的本质是虚拟化和资源池化，节点的变化和弹性是一个常规操作，我们需要解决面向用户透明运维的能力，任何情况下数据都不能丢、不能错。

除此以外，X-Paxos除了为数据库解决了分布式一致性问题，同样可以快速赋予其他系统分布式一致性能力。我们把Paxos的能力独立成一个基础库，希望能够把这个能力带给更多的其他系统。ps. 我们也做过快速的尝试，把X-Paxos融入到单机KV数据库RocksDB中，就可以很快速实现了一个分布式KV引擎。

Google的论文《Paxos made live》中有一段话说的很好，大意是说：Paxos从理论到现实世界的实现之间有巨大的鸿沟，在真正实现一个Paxos的时候，往往需要对Paxos的经典理论做一些扩展，（尤其是在实现一个高性能的Paxos的时候，扩展点就更多了，可以参考后文的功能增强和性能优化），这往往会导致真正的Paxos实现其实都是基于一个未被完全证明的协议。这也就是传说中，理论证明一个Paxos的实现，比实现这个Paxos还要难的原因了。因此一个成熟的Paxos实现很难独立产生，往往需要和一个系统结合在一起，通过一个或者多个系统来验证其的可靠性和完备性。这也是为什么大部分成熟的Paxos案例都是和分布式数据库相结合的，例如最早的Paxos实现（Chubby），当前的主要Paxos案例（Google的MegaStore、Spanner，AWS的DynamoDB、S3等）。而X-Paxos正是依托于PolarDB-X验证了其可靠性和完备性。

X-Paxos 整体架构

X-Paxos的整体架构如上图所示，主要可分为网络层、服务层、算法模块、日志模块4个部分。

网络层
网络层基于libeasy网络库实现。libeasy的异步框架和线程池非常契合我们的整体异步化设计，同时我们对libeasy的重连等逻辑进行了修改，以适应分布式协议的需求。

服务层
服务层是驱动整个Paxos运行的基础，为Paxos提供了事件驱动，定时回调等核心的运行功能。每一个paxos实现都有一个与之紧密相关的驱动层，驱动层的架构与性能和稳定性密切相关。

X-Paxos的服务层是一个基于C++11特性实现的多线程异步框架。常见的状态机/回调模型以其开发效率低，可读性差等缺点，一直被开发者所诟病；而协程又因其单线程的瓶颈，而使其应用场景受到限制。C++11以后的新版本提供了完美转发（argument forwarding）、可变模板参数（variadic templates）等特性，为我们能够实现一种全新的异步调用模型提供了可能。

例如这是X-Paxos内实际的一行创建单次定时任务的代码

new ThreadTimer(srv_->getThreadTimerService(), srv_, electionTimeout_, ThreadTimer::Oneshot,
                &Paxos::checkLeaderTransfer, this, targetId, currentTerm_.load(), log_->getLastLogIndex());

注：左右滑动阅览*

以上一行程序，包含了定时器的创建，任意回调函数的设置，回调函数参数的转发，并保证在回调触发后（Oneshot）内存的自动回收。

算法模块
X-Paxos当前的算法基于强leadership的multi-paxos[3]实现，大量理论和实践已经证明了强leadership的multi-paxos，性能好于multi-paxos/basic paxos，当前成熟的基于paxos的系统，都采用了这种方式。

算法模块的基础功能部分本文不再重复，感兴趣的同学可以参考相关论文[1,2,4]。在基础算法的基础上，结合阿里业务的场景以及高性能和生态的需求，X-Paxos做了很多的创新性的功能和性能的优化，使其相对于基础的multi-paxos，功能变的更加丰富，性能也有明显的提升。后面将对这些优化进行详细的介绍。

日志模块
日志模块本是算法模块的一部分，但是出于对极致性能要求的考虑，我们把日志模块独立出来，并实现了一个默认的高性能的日志模块；有极致性能以及成本需求的用户，可以结合已有的日志系统，对接日志模块接口，以获取更高的性能和更低的成本。这也是X-Paxos作为高性能独立库特有的优势，后面也会对这块进行详细介绍。

X-Paxos 特色功能

在线添加/删除节点，在线转让leader
X-Paxos在标准multi-paxos的基础上，支持在线添加/删除多种角色的节点，支持在线快速将leadership节点转移到其他节点（有主选举）。这样的在线运维能力，将会极大地方便分布式节点的有计划性的运维工作，将RTO降低到最低。

策略化多数派和权重化选主
阿里目前多地架构会有中心机房的诉求，比如：应用因其部署的特点，往往要求在未发生城市级容灾的情况下，仅在中心写入数据库，数据库的leader节点在正常情况下只在中心地域；同时又要求在发生城市级容灾的时候（同一个城市的多个机房全部不可用），可以完全不丢失任何数据的情况下，将leader点切换到非中心。

而经典的multi-paxos并不能满足这些需求。经典理论中，多数派强同步以后即可完成提交，而多数派是非特定的，并不能保证某个/某些节点一定能得到完整的数据，并激活服务。在实际实现中，往往地理位置较近的节点会拥有强一致的数据，而地理位置较远的节点，一直处于非强一致节点，在容灾的时候永远无法激活为主节点，形同虚设。

同时当中心单节点出现故障需要容灾的时候，往往需要将主节点就近切换到同中心的另外一个节点，而经典理论中同样没有类似的功能。

X-Paxos在协议中实现了策略化多数派和权重化选主。

1. 基于策略化多数派，用户可以通过动态配置，指定某个/某些节点必须保有强一致的数据，在出现容灾需求的时候，可以立即激活为主节点。

2. 基于权重化选主，用户可以指定各个节点的选主权重，只有在高权重的节点全部不可用的时候，才会激活低权重的节点。

节点角色定制化（Proposer/Accepter/Learner的独立配置）
在经典的multi-paxos实现中，一般每个节点都包含了Proposer/Accepter/Learner三种功能，每一个节点都是全功能节点。但是某些情况下我们并不需要所有节点都拥有全部的功能，例如：

1. 经典的三个副本部署中，我们可以裁剪其中一个节点的状态机，只保留日志（无数据的纯日志节点，但是在同步中作为多数派计算），此时我们需要裁剪掉协议中的Proposer功能（被选举权），保留Accepter和Learner功能。

2. 我们希望可以有若干个节点可以作为下游，订阅/消费协议产生的日志流，而不作为集群的成员（不作为多数派计算，因为这些节点不保存日志流），此时我们裁剪掉协议的Proposer/Accepter功能，只保留Learner功能。

当然还有其他的组合方式，通过对节点角色的定制化组合，我们可以开发出很多的定制功能节点，即节约了成本，又丰富了功能。比如下面的三副本部署，其中一个Follower节点配置为仅做logger模式(参与多数派投票，但不存储数据)，这样可以将三副本的3份数据成本优化为只有2份：

Witness SDK
基于上节节点角色定制化中的单独Learner角色的功能，引发了无穷的想象力。Learner角色，可以抽象成一个数据流订阅者（Witness Node），整个集群中可以加入无数个订阅者，当有新的日志被提交的时候，这些订阅者会收到其关心的日志流，基于订阅者功能，我们可以让一个集群很容易的实现下游订阅消费，日志即时备份，配置变更推送等等的功能。

因此我们把Learner角色单独封装成了一个SDK。基于这个SDK，用户可以快速的为自己的集群添加，订阅注册，流式订阅定功能；结合特定的用途打造一个完成的生态。采用了X-Paxos也可以利用Witness SDK快速实现分布式系统和下游的其他系统的对接，形成一个完整的生态。

Leader 主动回切
在现实应用场景中，Follower 和 Leader 的状态机难免会存在回放延迟，比如一个大的 DDL 会导致 Follower 的回放延迟被无限放大，而如果在回放延迟存在的情况下 Leader 挂掉新主选出时，新主无法对外提供服务，而此时老 Leader 可能已经重启恢复，所以在这种情况下 X-Paxos 会主动探测状态机的健康状况，如果在一段时间内回放延迟无法追平，则会尝试 Leader 主动回切，让没有回放延迟的老 Leader 对外提供服务。

多连接
传统方式leader和learner之间采用单连接同步数据，在跨IDC场景中，网络延时往往比较大，会导致leader和learner之间的数据差异较大。leader和learner之间通过多连接并发的发送数据，可以有效提升吞吐，减少数据差异，在弱一致的模式下，可以更好地对外提供读能力。同时在单IDC出现完全不可用的情况下，提供更好的灾备能力。

X-Paxos 性能优化

Batching & Pipelining
X-Paxos除了设计之初的强一致和高可用以外，其高性能也是至关重要的，尤其是应用于PolarDB-X分布式数据库，对协议的吞吐和延迟都提出了很高的要求。同时作为可全球部署的分布式一致性协议，在高延迟下的性能挑战变得尤为重要。

X-Paxos针对高延迟网络做了大量的协议优化尝试和测试，并结合学术界现有的理论成果[5,6,7]通过合理的Batching和Pipelining，设计并实现了一整套自适应的针对高延迟高吞吐和低延迟高吞吐网络的通信模式，极大地提升了X-Paxos的性能。

1. Batching是指，将多个日志合并成单个消息进行发送；Batching可以有效的降低消息粒度带来的额外损耗，提升吞吐。但是过大Batching容易造成单请求的延迟过大，导致并发请求数过高，继而影响了吞吐和请求延迟。

2. Pipelining是指在上一个消息返回结果以前，并发的发送下一个消息到对应节点的机制，通过提高并发发送消息数量（Pipelining数量），可以有效的降低并发单请求延迟，同时在transmission delay小于propagation delay的时候（高延迟高吞吐网络），有效提升性能。

R为网络带宽，D为网络传播延迟（propagation delay，约为RTT/2），经推导可知 Batching（消息大小:M）和Pipeling（消息并发:P）在如下关系下，达到最高吞吐。

M/R * P = D

X-Paxos结合以上理论，通过内置探测，针对不同节点的部署延迟，自适应的调整针对每个节点的Batching和Pipeling参数，达到整体的最大吞吐。因Pipeling的引入，需要解决日志的乱序问题，特别是在异地场景下，window加大，加大了乱序的概率。X-Paxos实现了一个高效的乱序处理模块，可以对底层日志实现屏蔽乱序问题，实现高效的乱序日志存储。

多线程的全异步Paxos库
由于Paxos的内部状态复杂，实现高效的单实例多线程的Paxos变成一个非常大的挑战。比如开源产品phxpaxos、Oracle MySQL Group Replication中使用的xcom，都是单线程的实现。phxpaxos采用了单分配单线程，多实例聚合的方式提升总吞吐，但是对单分区的性能非常的有限；xcom是一个基于协程的单线程实现。单线程的Paxos实现，在处理序列化/反序列化，分发、发包等逻辑的时候都为串行执行，性能瓶颈明显。

X-Paxos完全基于多线程实现，可以在单个分区Paxos中完全的使用多线程的能力，所有的任务都有通用的worker来运行，消除了CPU的瓶颈。依赖于服务层的多线程异步框架和异步网络层，X-Paxos除了必要的协议串行点外，大部分操作都可以并发执行，并且部分协议串行点采用了无锁设计，可以有效利用多线程能力，实现了Paxos的单分片多线程能力，单分区性能远超竞品，甚至超过了竞品的多实例性能。

可插拔日志
X-Paxos和现有的大部分Paxos库很大的不同点就是X-Paxos支持可插拔的日志模块。日志模块是Paxos中一个重要的模块，它的持久化关系到数据的一致性，它的读写性能很大程度上会影响协议整体的读写性能。当前大部分独立Paxos库都是内置日志模块，并且不支持插拔的。这会带来2个弊端：

1. 默认的日志模块提供通用的功能，很难结合具体的系统做针对性的优化

2. 现有的系统往往已经存在了WAL（Write Ahead Log），而Paxos协议中需要再存一份。这使得 a) 单次commit本地需要sync 2次（影响性能）；b) 双份日志浪费了大量的存储

例如：phxpaxos内置的日志模块采用LevelDB，作为日志系统其操作大量冗余，无针对优化；同时采用phxpaxos的phxsql单节点需要即保存binlog，又保存paxos log（在独立的phxbinlogsvr中），会有性能性能、以及浪费存储空间。而采用X-Paxos的MySQL存储引擎可直接改造现有的binlog模块，对接到X-Paxos的日志模块，单节点仅一份日志，既降低了存储，又提高了性能。

X-Paxos 正确性验证

《Paxos made live》中有过一个说法，证明一个Paxos实现是正确的，比实现这个Paxos本身会更难。因此我们在设计和实现X-Paxos的时候，投入了大量的精力在Paxos的原理证明和实现验证。

1 Jepsen

• Jepsen是开源社区比较公认的分布式数据库的测试框架。Jepsen验证过包括VoltDB、CockroachDB、Galera、MongoDB、etcd在内的几乎所有的主流分布式数据库/系统，检验出了不少的问题。
• X-Paxos完成了和Jepsen的对接，并验证了各个分布式数据库已有的case。

2 TLA+

• TLA+是Paxos创始人、图灵奖获得者Leslie Lamport老爷子发明的一种形式化规约语言。TLA+专用于设计、建模和验证分布式并发系统。Amazon DynamoDB/S3/EBS和Microsoft Cosmos DB都通过TLA+的模型验证发现了不少问题
• X-Paxos目前已经通过了TLA+的模型验证。

3 随机异常系统

• 我们搭建了一套自动随机异常验证系统，可以自动化验证各种异常场景下的协议正确性和稳定性。验证X-Paxos在模拟网络丢包、闪断、隔离，磁盘故障等情况下的功能正确和数据一致。

4 异常回归系统

• X-Paxos拥有一套异常case回归系统，对于曾经出现过或者预期的并发异常case，都会加到异常case库中，进行日常回归验证。同时异常case库也在不断的丰富中。

未来

Paxos是分布式系统的基石，即使是近几年，学术界关于Paxos的文章，新的演进方向一直在不断的涌现，我们的PolarDB-X分布式数据库也会在X-Paxos的基础上不停的发展，比如多分区Paxos、基于Paxos多副本的HTAP架构、以及Geo-Partition的特性等。

参考文档

[1] The part-time parliament
[2] The Chubby lock service for loosely-coupled distributed systems
[3] Paxos Made Simple
[4] Paxos Made Live - An Engineering Perspective
[5] Everything You Ever Wanted to Know About Message Latency
[6] Adaptive Batching for Replicated Servers
[7] Tuning Paxos for high-throughput with batching and pipelining
[8] The Totem single-ring ordering and membership protocol
[9] Group Replication: A Journey to the Group Communication Core
[10] Mencius: Building Efficient Replicated State Machines for WANs