PolarDB-X 存储架构之“基于Paxos的最佳生产实践”

MySQL数据库从诞生以来就以其简单开放、易用、开源为其主打的特点，成为不少开发者首选的数据库系统。阿里在09年开始提出去IOE的口号，也选择基于开源MySQL进行深度发展，结合TDDL的技术完成了去IOE的工作，这也是早期的PolarDB-X发展的技术栈。 2014年开始，随着业务高速的增长，以及“异地多活”的新需求驱动，基于MySQL的一致性协议技术X-Paxos在阿里集团得到了全面的发展和验证，可参见：PolarDB-X 的诞生和发展，PolarDB-X 一致性共识协议 (X-Paxos)。

从19年开始，PolarDB-X 2.0结合了分布式SQL引擎和基于X-Paxos的数据库存储技术，基于阿里集团多年双十一的技术积累和稳定性验证，以云的方式提供云原生分布式数据库产品，为传统企业、金融业务数字化转型和去IOE过程提供更好的技术产品和服务。

上图展示的是一个部署三个节点的存储集群，设计上引入了多分组X-Paxos技术替换传统的复制协议，上图中Paxos Group 0~N代表不同的X-Paxos分组，基于多分组技术可支持多点写入+多点可读的能力，同时分布式下多个分片可以属于不同的Paxos分组。

多分组Paxos

我们在设计上，在同一个物理节点中允许管理多个X-Paxos实例。每个节点上基于分布式的数据分区(Partition)，将不同分区的数据绑定到某一个X-Paxos实例，通过将每个X-Paxos实例的Leader分散到多个物理节点中，从而提供不同分区数据的多点可写能力，除了解决了传统MySQL数据库下的单点写瓶颈的问题。

多分组Paxos相比于单分组的Paxos，并不是简单的启动多份X-Paxos实例，而是需要做一定的合并优化，来降低多分组Paxos所带来的资源开销，主要包含三个模块的优化：消息服务、分区管理、协调者。

1. 消息服务

多分组引出两个风险，连接风暴和消息风暴。连接风暴是指，假设沿用原有单分组X-Paxos架构的设计，如果一个集群有3个节点，每个节点有3个分组，那么单节点需要监听3个不同的端口，并维持6个独立的连接。多分组X-Paxos消息服务提供一套共享的网络层，多个分组之间复用同样的网络连接。消息风暴是指，假设同步的总量不变，数据由多节点分散写入会让单个网络包变小，同时每个分组的Leader还会定期维持租约心跳，当分组数变多之后，网络会充斥大量小包导致收发包质量降低。因此共享的消息服务需要提供日志聚合和心跳聚合的能力。此外，我们还可以通过共享Timer模块让同一节点上多个分组的Leader共享任期，减少Leader租约管理的成本。

2. 分区管理

分区管理模块维护X-Paxos分组和数据分片的映射关系。多分组X-Paos对接分布式下的数据分区，存储上收到计算层发送的DML操作后，以物理库或表做为分区键（Partition Key）传递到Consensus层。Consensus层接收字符串类型的分区键，转换成对应X-Paxos分组的Group ID。其中Hash Table模块提供快速的查询能力，Meta Store模块负责映射关系的持久化。当映射关系出现改变时，Hash Table会把最新的变更同步给Meta Store。Meta Store提供统一的接口，数据持久化是借助InnoDB引擎的MySQL系统表来保证数据修改的原子性和持久性。如上图所示，Consensus层保留了独立性和通用性，不依赖分布式下的分区逻辑，管理分区键和Group ID的关系，并驱动元数据表的同步更新。

3. 协调者

当集群需要负载均衡时，我们可能会增加新的X-Paxos分组，还会把一部分数据分片从某个分组切换到新的分组中。这些分区管理模块的修改行为称为分组变更（Group Change）。需要考虑以下几个问题：如何确保同一数据分片不会同时属于两个分组，即跨Group信息的分布式一致？如何让集群中多个实例的分区元数据一致，防止双写造成数据冲突？如何保证在做分组变更的过程中，任意分组内部的节点变更（Membership Change，如切主、加减节点）不会影响分组变更的正确性？这类问题一般有两种解决方案，集中式和分布式。前者是引入一个外部的配置中心（如Placement Driver/PD），通过集中化的单点管理规避掉分布式一致性的问题。该方案的缺点是有单点故障的风险，因此一般情况下，PD也会部署成主备甚至三节点的形式，借助冗余来提高可用性，这又进一步增加了系统交付的成本。在PolarDB-X中，我们采用的是分布式的方案，集群中每一个节点既是参与者，也可以是协调者。通过两阶段日志同步，解决跨X-Paxos分组分布式一致性的问题。此外，Paxos协议保证了参与者和协调者的高可用，传统2PC协议中协调者或参与者宕机引出的一系列问题都自然而然的规避掉了。

事务提交和复制

基于MySQL发展的存储节点DN，其复制流程是基于X-Paxos驱动Consensus日志进行复制。Leader节点在事务prepare阶段会将事务产生的日志收集起来，传递给X-Paxos协议层后进入等待。X-Paxos协议层会将Consensus日志高效地转发给集群内其他节点。当日志在超过集群半数实例上落盘后 X-Paxos会通知事务可以进入提交步骤。否则如果期间发生Leader变更，期间prepare的事务会根据Paxos日志的状态进行相应的回滚操作。

Follower节点也使用X-Paxos进行日志的管理操作，为提升接收效率，收到Leader传递过来的日志以后将日志内容Append到Consensus Log末尾，Leader会异步的将达成多数派的日志的消息发送给Follower，Follower的协调者线程会负责读取达成多数派的日志并加以解析，并传递给各个回放工作线程进行并发的数据更新。 Follower的并发回放可以有多种方式，包括按照Leader上的Group Commit维度或者是按照表级别的维度，未来会引入最新的writeset方式来精确控制最大并发。

相比于传统的MySQL基于binlog的semi-sync复制模式，我们引入X-Paxos做了比较多的优化。

1. 异步化事务提交

传统的MySQL都是 One Thread per Connection的工作模式， 在引入线程池后是以一个线程池孵化一定数量的工作线程， 每个线程负责处理一次query的解析、优化、修改数据、提交、回网络包等等。集群需要跨地域部署下，一次事务的提交由于需要在集群之间同步事务日志，受限于网络的RTT的限制，会达到数十毫秒的级别，那么对于一个普通的写事务来说，大量的时间会耗费在同步节点日志等待事务提交的过程。在大压力下，很快数据库内部的工作线程会耗尽， 吞吐达到瓶颈。 如果一味的放大数据库内部的工作线程数目，那么线程上下文的代价会大幅增加。 如果将整个事务的提交异步化，将工作线程从等待X-Paxos日志同步中解放出来，去处理新的连接请求，在大负载下可以拥有更高的处理能力。

异步化提交核心思想是将每个事务的请求分成两个阶段，提交之前一个阶段，提交和回包一个阶段。两个阶段都可以由不同的工作线程来完成。 为了完成异步化的改造，我们增加了等待同步队列和等待提交队列，用于存储处于不同阶段的事务。前者队列中的事务是等待Paxos多数派日志同步的事务，后者是等待提交的事务。

异步化流程： a. 当用户发起Commit/Rollback/XA_Prepare时， 处理用户连接的线程池Worker产生事务日志并将事务上下文存储到等待同步的队列中。 b. 等待同步队列的消费由少量数目的worker线程来完成，其余工作线程可以直接参与其他任务的处理。 事务等待多数派完成后会被推入等待提交队列。 c. 等待提交队列里的事务都是可以被立即提交的，所有的worker线程发现该队列里有事务，就可以顺道取出来执行提交操作。

这样一来，系统中只有少数的线程在等待日志同步操作， 其余的线程可以充分利用CPU处理客户端的请求，异步化提交结合MySQL的Group Commit逻辑，将原有需要等待的操作全部异步化，让Worker线程可以去执行新的请求响应。在测试中，异步化改造在同城部署的场景中相比同步提交有10%的吞吐率提升，跨区域的部署后有500%的吞吐提升。

2. 热点更新优化

热点更新原本就是数据库的一个难题，受制于行锁竞争，性能吞吐一直很难提升上去。X-Paxos下面对跨域场景下的长传网络更加是雪上加霜，提交的时间变长，事务占据行锁的时间也显著增加。 为了解决此问题，PolarDB-X在AliSQL的热点功能之上优化了复制，使得在保证数据强一致的情况下，热点更新性能提升非常明显。

如上图所示，针对热点行更新的基本思路是合并多个事务对同一行的更新。为了让批量的更新事务能够同时进行提交，PolarDB-X在存储引擎中增加了一种新的行锁类型——热点行锁。热点行锁下，热点更新的事务之间是相容的，为了保证数据的一致性，对同一批的热点更新事务日志打上特殊tag， X-Paxos会根据tag将这一整批事务的日志组成一个单独的网络包进行集群间的数据同步，保证这些事务是原子的提交/回滚。除此之外为了提升日志回放的效率，PolarDB-X将每个批次事务中对于热点行的更新日志也做了合并。

多副本配置和部署

PolarDB-X设计目标是支持跨地域部署，在多地域保证集群数据强一致，即使某个城市的机房全部宕机，只要保证集群多数派节点存活，所有的数据都不会丢失。我们在部署方式设计上也比较灵活，支持容灾成本和多样化的部署需求。

1. 选主优先级。应用往往对于容灾后新主节点是有要求的，比如机房流量均衡、以及应用和地域之间的关联性(比如新疆业务的应用，期望对应的分区数据在新疆机房)。 针对这样的需求，PolarDB-X可以根据不同的分区优先级，在分区级别X-Paxos级别设置不同的优先级，在原有Leader节点故障时，选举Leader的顺序会按照集群存活节点的权重顺序进行，同时在运行过程中如果发现有权重更高的节点，会主动发起一次Leader Transfer将Leader角色过继过去。
2. 策略化多数派。一致性复制可分为两档，强复制和弱复制。可以搭配选主优先级，比如设置同城机房的节点为强同步复制，我们可以配置在规定日志复制到多数节点的基础上必须还要复制到了所有强复制的节点才可以推进状态机并返回客户端事务提交成功的响应。这是一个类Max protection模式的设计，如果检测到强一致节点宕机，可自动降级。
3. 日志型副本。默认三副本的机制，相比于传统的主备模式，会在存储成本上会多一份数据。PolarDB-X在副本设计上分为普通型(Normal)和日志型(Log)两类。日志型节点可以和普通型节点组成Paxos的一致性投票，不过它只有投票权，没有被选举权。通过日志型副本只记录Paxos日志，在满足RPO=0的前提下，也可以和普通的主备模式的存储成本对齐。
4. Follower Read。针对只读Leaner节点在跨机房部署下，如果所有Leaner节点的日志都从Leader节点复制会对Leader节点造成过大的网络和IO瓶颈，PolarDB-X也支持Leaner挂载到Follower节点获取一致性数据。
5. 多副本一致性读。在分布式环境下，基于Paxos的副本相比于主副本会有一定的Apply延迟，如果要实现多副本的线性一致性读时，需要有一定的保证机制。PolarDB-X里会有两种一致性读的方案。第一种是基于Paxos的LogIndex来，首先在Leader节点上获取一下index，然后观察follower/leaner副本的LogIndex是否已经超过，如果超过说明所需要的数据已经在了，可以直接读取。第二种是基于TSO全局版本号，查询的时候获取一个全局版本，指定版本在follower/leaner副本中进行读取，在存储上我们支持版本的阻塞读能力，用户可以设置等待时间直到对应版本数据同步到该副本上。这两种方案，前者只满足RC级别的当前读，后者可满足RR级别的历史读，结合PolarDB-X的HTAP架构，可以分流部分AP查询到只读副本上，并满足事务RC/RR的隔离级别。

推荐的两种部署：

高可用检测和恢复

PolarDB-X 引入Paxos的一致性协议，基于Paxos算法已有的租约自动选举的策略，可以避免“双主”的问题出现。如果当前Leader被网络隔离，其他节点在租约到期之后，会自动重新发起选主。而那个被隔离的Leader，发送心跳时会发现多数派节点不再响应，从而续租失败，解除Leader的状态。Follower约定在lease期间不发起新的选主，Leader先于Follower lease超时，从时序上最大程度上规避了“双主”问题的出现。

除了常规的租约策略之外，考虑云环境的各种异常情况，我们还需要有更进一步的优化：

1. 状态机诊断

从数据一致性角度来说，选主流程结束后，新的Leader必须回放完所有的老日志才能接受新的数据写入。因此，成功选主并不等价于服务可用，实际的不可用时间是选主时间（10s）和日志回放追平时间之和。在遇到大并发和大事务场景下，Follower可能会产生比较大的回放延迟。假如此时恰好主库出现故障，新选主的节点由于回放延迟，服务不可用时间充满了不确定性。

故障有可恢复和不可恢复之分，通过我们观察，除了那种机器宕机、磁盘坏块这类彻底恢复不了的场景，大部分故障都是短期的。比如网络抖动，一般情况下网络架构也是冗余设计的，可能过一小段时间链路就重新正常了。比如主库OOM、Crash等场景，mysqld_safe会迅速的重新拉起实例。恢复后的老主一定是没有延迟的，对于重启的场景来说，会有一个Crash Recovery的时间。这个时候，最小不可用时间变成了一个数学问题，到底是新主追回放延迟的速度快，还是老主恢复正常的速度快。因此，我们做了一个状态机诊断和主动切换的功能。在数据库内核中，通过状态机诊断接口，可以收集回放延迟、Crash Recovery、系统负载等状态。当状态机健康状况影响服务可用性时，会尝试找一个更合适的节点主动切换出去。主动切换功能和权重选主也是深度整合的，在挑选节点的时候，也会考虑选主权重的信息。最终，服务恢复可用后诊断逻辑会自动停止，避免在稳定Leader的情况下产生不必要的切换。

2. 磁盘探活

对于数据库这样有状态的服务来说，存储是影响可用性的重要因素之一。在本地盘部署模式下，数据库系统会遇到Disk Failure或者Data Corruption这样的问题。我们曾经遇到过这样的情况，磁盘故障导致IO卡住，Client完全无法写入新的数据。由于网络是连通状态，节点之前的选举租约可以正常维持，三节点自动容灾失效导致故障。有时候还会发生一些难以捉摸的事情，由于IO已经完全不正常了，进程在kernel态处于waiting on I/O的状态，无法正常kill，只有重启宿主机才能让节点间通信完全断掉触发选主。

针对这类问题，我们实现了磁盘探活功能。对于本地盘，系统自动创建了一个iostate临时文件，定期向其中执行随机数据读写操作。对于云盘这类分布式存储，我们对接了底层的IO采样数据，定期来感知IO hang或者Slow IO的问题。探测失败次数达到某个阈值后，系统会第一时间断开协议层的网络监听端口，之后配合重启实例可以恢复。

3. 反向心跳

基于已有的策略，我们已经可以覆盖99%的常规可用性问题。在长时间的线上实践中，我们发现有些问题从节点内部视角发现不了，比如主库连接数被占满，open files limit配置不合理导致“Too many open files”报错，以及代码bug导致的各种问题......对于这些场景，从选举租约、状态机、磁盘探活的角度，都无法正确的检测故障，因此最好有一个能从App视角去建连接、执行业务查询和返回结果的全链路检测流程。因此催生了Follower反向心跳的需求，即Follower通过业务查询SQL接口去主动探测Leader的可用性。该设计有两个优势：首先是内核自封闭，借助三节点的其他非Leader节点，不依赖外部的HA agent进行选主判定，就不用再考虑HA agent本身的可用性问题；其次和内核逻辑深度整合，不破坏原有的选主逻辑。

整个流程如图所示，假设Node 1是Leader，给其他两个Follower正常发送心跳，但是对外的App视角已经不可服务。当Node 2和Node 3通过反向心跳多次尝试发现Leader的SQL接口不可服务之后，这两个Follower不再承认Leader发来的Heartbeat续租消息。之后若Node 2的选举权重相对较高，他会首先超时，并用新的term发起requestVote由Node 3投票选成主，对外开始提供服务。这个时候Node 2作为新主，也会同时开始给Node 1和Node 3发续租心跳。Node 1在收到新主发来的心跳消息之后，发现term比自己当前term大，就会主动降级成Follower。整个三节点又能回到正常的状态。

PolarDB-X融合了基于X-Paxos的数据库存储技术，通过经历阿里集团多年双十一的技术积累和稳定性验证，PolarDB-X在稳定性、易用性、高可用特性上都会有不错的表现。未来，我们也会在Paxos副本在多节点混部和迁移、跨地域容灾的Paxos Quorum自动降级、Geo-Partition特性、以及分布式热点分区优化上做更多的探索和尝试，给用户提供更好的分布式数据库体验。