开源｜WPaxos：一致性算法Paxos的生产级高性能Java实现

开源项目专题系列

（七）

1.开源项目名称： WPaxos

2.github地址：

https://github.com/wuba/WPaxos

3.简介： WPaxos是58同城推出的一种Paxos分布式一致性算法的生产级Java实现，用于解决高并发、高可靠分布式系统中多副本数据一致性问题以及分布式共识问题。

WPaxos于2020年4月份开源，具备的功能特性如下：

• 高性能：Multi-Paxos算法与Basic-Paxos算法结合，支持多Paxos分组，有序确定多个值

• 节点间可通过状态机checkpoint或逐条数据流两种方式对落后数据快速对齐

• 具有网络分区容错性，集群少数节点故障服务高可用性

• 提供有Master自动选举功能

• 集群可通过Paxos协议动态、安全的增加节点、删除节点

• 高扩展性：支持存储模块与异步通信模块自定义

• 一个Paxos实例可以同时挂载多个状态机

• 提交的数据支持增量checksum校验

• 可添加不参与提案投票，仅用于备份数据的follower节点

• 默认存储支持按照时间与holdcount两种清理paxoslog方式

项目背景

为了解决数据访问的高性能、高可靠性及高扩展性等问题，在数据密集型系统的开发中常会使用数据复制及分区等技术，但异步通信环 境下难免会遇到各种各样复杂的异常情况，如网络故障、机器宕机、时钟不一致等，导致数据在网络传输或者存储落地时出现丢失、错乱或重复等问题，如何保证在分布式场景下各节点数据强一致性是一个业界难题。 常见的解决方案有同步/异步复制、两阶段提交等方法，但这些方法很难同时保证数据的强一致性与服务高可用性。 在实际的分布式系统实现中，往往会通过降低对一致性的要求，在一致性、可用性、容错性之间做出权衡，选择最终一致性来保证系统整体的服务质量，而分布式共识算法就是这种设计理念的最好体现。

分布式系统中最著名的共识算法就是Paxos，最早由Leslie Lamport在论文《The Part-Time Parliament》中提出。Basic Paxos 是 Paxos 中最为基础的协议，也是最难理解的分布式一致性协议，详细算法实现可参看论文，这里只做简单介绍。如下图所示：

• 分布式Paxos集群中的每个节点都同时具有Proposer、Acceptor、Learner三个角色，每个节点都可以作为Proposer并行发起数据同步请求， P roposer : 提案的发起者，Accepter : 提案的接受者，Learner : 提案的学习者；

• Proposer只需要与多数派的Acceptor交互，通过prepare、accept两个阶段，收到过半节点返回Ack，即可完成一个值的确定(chosen)；

• 同步落后的数据，由Learner向其它节点学习；

• 同一instance一旦一个值被确定，应用于状态机，无论Proposer再发起任何值的写入，该instance数据都不会再被修改；

由于Basic-Paxos每个提案的确定需要经过两阶段与多数派节点交互才能达成共识，性能比同步多写方式有提升，但还是不太适用于高并发场景，因此又出现了很多Paxos协议实现变种，如Multi-Paxos、Zab、Raft等，其中Multi-Paxos支持并行确定多个值，并将满足某种规则的请求，跳过prepare阶段，直接进入accept阶段，优化提交过程；Raft、Zab在Multi-Paxos基础上添加了Leader选举限制，简化了实现更易让人理解，但强依赖Leader使灵活性略逊于Multi-Paxos。目前Multi-Paxos较为成熟的开源实现是微信团队C++语言开发的PhxPaxos生产级类库，该类库在实现上有以下一些优化：

1. 添加Leader选举机制，可指定由Leader串行发起propose，但propose的权限并不严格受限于Leader节点；

2. 在上一次提案提交成功后，无请求超时或冲突情况下，可跳过prepare阶段，网络RTT与写盘次数优化(2,2)->(1,1)；

3. Multi-Group-Paxos，支持多分组，并行确定多个值

4. 将同一个group并发的多个请求进行异步批量合并，具有高吞吐量

5. 扩展性强：状态机、存储、异步通信模块可自定义

6. 数据落后的节点可向Paxos集群内任意数据更全的节点学习同步数据

7. 可添加不参与提案投票，仅用于备份数据的follower节点

WPaxos项目于2018年3月份启动开发，在此之前，开源的分布式一致性算法生产级实现主要有微信团队的PhxPaxos（C++）、百度的Braft（C++）以及etcd内嵌Raft（Go），Java语言生产级实现并不多，而PhxPaxos类库当时已经应用到很多微信开源产品中，如PaxosStore、PhxSql、PhxQueue等，并支持百万级吞吐能力，考虑到Paxos算法相对于Raft算法使用更灵活，最后，我们参照Phxpaxos类库，在批量化提交、Master负载均衡、存储等方面做了些调整优化，采用Java语言实现了WPaxos分布式一致性组件，针对一些网络分区、机器宕机、进程异常（OOM、卡顿、强制关闭）等突发情况，已经过一系列实际应用场景的验证。

项目架构

WPaxos核心Multi-Paxos算法实现主要还是参考的PhxPaxos，整体架构如下：

其中，每个group的Master并不是要求强制存在的，任何一个节点都可以发起propose，只不过会容易发生冲突，由Multi-Paxos退化为Basic-Paxos，性能有损耗。

1. Paxos Node

WPaxos服务集群包括多个独立运行的Node物理节点，每个Node节点有固定数量的Paxos Group，每个group下运行一个Paxos 实例，多个Paxos Group可以同时确定多组instanceID递增的有序序列，Paxos实例每确定一个值并提交至状态机执行成功，则instanceID增加1，一旦一个instanceID对应的值被确定，之后不会被修改。

2. 存储

存储模块业务可自定义实现。为了保证任何情况下已提交的instance数据不丢，Node节点日志存储PaxosLog需要实时持久化存储Acceptor已接受的所有instance数据，并且每条instance数据需支持随机读取。为此，WPaxos默认PaxosLog存储由物理文件和IndexDB索引两部分构成，如下图所示，IndexDB默认采用LevelDB实现，physiclog采用文件顺序追加写+同步刷盘方式，IndexDB则采用异步刷盘，当进程异常挂掉时，只要保证physiclog数据不丢，即可通过PaxosLog重放，恢复IndexDB中的索引数据。

但在实际测试中发现，LevelDB异步写接口时常会发生几百毫秒的存储抖动，为了解决这个问题，在Paxos group数量比较少时，我们将IndexDB实现改为了内存缓存+异步写文件方式，解决了抖动问题，同时便于历史日志以文件为单位批量清理，具体性能数据在下文中可以看到。

WPaxos同时支持按照instance保留数量（HoldCount）、保留时间（HoldTime）以及磁盘空间占用率三种方式清理PaxosLog历史日志。

3. 状态机

一个Paxos实例可以挂载多种状态机，其中Master StateMachine与System StateMachine为服务内置状态机，前者用来实现Master选举、续约状态管理，后者用来实现Member Ship成员动态变更管理。用户可以将核心业务逻辑添加到自定义状态机exe cute方法中执行。一个Paxos实例中任何节点，在执行同一条instance数据的时候，看到的状态机所有数据状态，都是一致的。

4. Checkpoint

Checkpoint为状态机某一时刻的数据快照， Checkpoint的存在使PaxosLog不会一直增长可被删除，但Checkpoint同步是个比较重的过程，需要删除所有历史数据来重构状态机。在Paxos实例中任何节点都可以作为Learner，定时向其它节点询问自己数据是否有落后，若某节点最大instanceID小于一定时间内返回Ack的所有节点最小chosen instanceID，则选择同步checkpoint来对齐数据。

5. 网络模块

同样，网络通信模块用户也可自定义。WPaxos默认实现中，可指定创建多少组网络IO实例，每组实例中会初始化一个本节点与Paxos实例中其它所有节点的TCP连接以及UDPClient。在一个Paxos实例中，来自同一个节点的所有请求都是串行的，因此默认初始化IO实例数为Paxos Group数量，即可满足性能最大化需求。

性能测试

1. 测试运行环境

CPU：20 x Intel(R) Xeon(R) Silver 4114 CPU @ 2.20GHz

内存：192 GB

硬盘：ssd

网卡：万兆网卡 

集群机器个数：3个

2. 测试结果

采用源码中Simple demo为测试样例，为了排除其它干扰，状态机空跑；instance索引采用默认的Leveldb方式；直接在服务节点本地调propose接口测试，group数量大于等于3时，master均匀分布于集群3个节点，每个group由master节点发起propose。

场景一：无批量提交

场景二：批量提交

批量合并有时间、size、请求数量三个维度的阈值最大限制，满足任何一个都可以触发batch propose，但在并发比较低的时候，会出现单条请求延迟比较大，为此，WPaxos在实现时，去掉了时间维度的限制，只做实时批量合并，不做延迟等待合并处理。

不同size数据在批量提交时，每个group达到最大性能的最佳batch取值及索引方式也有所不同，下面分别是数据size为100B、2KB时，不同group数量，达到的最大qps。

场景三：Leveldb索引与文件索引对比

下面是size 100B数据非批量提交时，不同group下Leveldb与文件两种索引方式的性能对比，从结果分析，在group数量比较小时，文件索引性能要优于Leveldb索引。

未来规划

未来我们会对WPaxos持续迭代优化，计划开源如下：

• Master负载均衡策略。多Paxos分组的Master均衡分布于集群中的不同Node节点，能够显著提升系统吞吐量与稳定性，已在实际应用场景中验证。

• 线性一致性读策略。保证任何时刻从master或slave读取数据，都可以获取到最新数据。

如何贡献&问题反馈

诚挚邀请各位开发者对WPaxos提出宝贵的意见和建议。

您可以在 https://github.com/wuba/WPaxos 阅读WPaxos项目源码、了解使用方法，有建议和问题可通过提交issue与Pull Request反馈给我们。

作者简介

刘丹，58同城后端架构师，58分布式消息队列、分布式锁等服务负责人；

刘研，58同城后端高级开发工程师，主要负责58分布式消息队列、分布式锁等服务的研发工作；

参考文献

1. PhxPaxos源码地址：

https://github.com/Tencent/phxpaxos

2. PhxPaxos wiki：

https://github.com/Tencent/phxpaxos/wiki

3. 微信自研生产级paxos类库PhxPaxos实现原理介绍：

4. Paxos理论介绍(2): 

Multi-Paxos与Leader : https://zhuanlan.zhihu.com/p/21466932

5. 状态机Checkpoint详解 : 

https://github.com/Tencent/phxpaxos/wiki/%E7%8A%B6%E6%80%81%E6%9C%BACheckpoint%E8%AF%A6%E8%A7%A3

想了解更多开源项目信息？

与项目成员零距离交流？

扫码加小秘书 微信

一切应有尽有

阅读推荐