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

CharlotteOlga 发布于3月前

开源项目专题系列

(七)

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 中最为基础的协议,也是最难理解的分布式一致性协议,详细算法实现可参看论文,这里只做简单介绍。如下图所示:

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

  • 分布式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,整体架构如下:

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

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

1. Paxos Node

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

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

2. 存储

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

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

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

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

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

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来对齐数据。

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

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。

场景一:无批量提交

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

场景二:批量提交

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

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

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

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

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

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

未来规划

未来我们会对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

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

与项目成员零距离交流?

扫码加小秘书 微信 开源|WPaxos:一致性算法Paxos的生产级高性能Java实现

一切应有尽有

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

微信号 : jishu-58

添加小秘书微信后由小秘书拉您进项目交流群

Live

58技术沙龙活 动第四期直播

“58同城推荐系统系列话题”

点击图片即可报名抢座

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

阅读推荐

查看原文: 开源|WPaxos:一致性算法Paxos的生产级高性能Java实现

  • redleopard