Paxos和Raft的前世今生

前言

在保证数据安全的基础上,保持服务的持续可用,是核心业务对底层数据存储系统的基本要求。业界常见的1主N备的方案面临的问题是“最大可用(Maximum Availability)”和“最大保护(Maximum Protection)”模式间的艰难抉择:

“最大可用”模式,表示主机尽力将数据同步到备机之后才返回成功,如果备机宕机或网络中断那么主机则单独提供服务,这意味着主备都宕机情况下可能的数据丢失(MySQL的半同步模式);

“最大保护”模式,表示主机一定要将数据同步到备机后才能返回成功,则意味着在任意备机宕机或网络中断情况下主机不得不停服务等待备机或网络恢复(MySQL的全同步模式)。

可见传统主备方式下,如果要求数据不丢,那么基本放弃了服务的持续可用能力。

算法演进

Paxos

Paxos算法是Leslie Lamport在1990年提出的一种基于消息传递的一致性算法。由于算法难以理解,起初并没有引起大家的重视,Lamport在1998年将论文重新发表到TOCS上,即便如此Paxos算法还是没有得到重视,2001年Lamport用可读性比较强的叙述性语言给出算法描述。

06年Google发布了三篇论文,其中在Chubby锁服务使用Paxos作为Chubby Cell中的一致性算法,Paxos的人气从此一路狂飙。

基于Paxos协议的数据同步与传统主备方式最大的区别在于:Paxos只需超过半数的副本在线且相互通信正常,就可以保证服务的持续可用,且数据不丢失。

Basic-Paxos

Basic-Paxos解决的问题:在一个分布式系统中,如何就一个提案达成一致。

需要借助两阶段提交实现:

Prepare阶段:

  • Proposer选择一个提案编号n并将prepare请求发送给 Acceptor。
  • Acceptor收到prepare消息后,如果提案的编号大于它已经回复的所有prepare消息,则Acceptor将自己上次接受的提案回复给Proposer,并承诺不再回复小于n的提案。

Accept阶段:

  • 当一个Proposer收到了多数Acceptor对prepare的回复后,就进入批准阶段。它要向回复prepare请求的Acceptor发送accept请求,包括编号n和根据prepare阶段决定的value(如果根据prepare没有已经接受的value,那么它可以自由决定value)。
  • 在不违背自己向其他Proposer的承诺的前提下,Acceptor收到accept请求后即接受这个请求。

参考资料

The Part-Time Parliament》,Leslie Lamport,May 1998,论文原文

Paxos Made Simple》,Leslie Lamport,Nov 2001

《一步一步理解Paxos算法》,相对通俗易懂

使用Basic-Paxos协议的日志同步与恢复》,偏实现

Mulit-Paxos

Mulit-Paxos解决的问题:在一个分布式系统中,如何就一批提案达成一致。

当存在一批提案时,用Basic-Paxos一个一个决议当然也可以,但是每个提案都经历两阶段提交,显然效率不高。Basic-Paxos协议的执行流程针对每个提案(每条redo log)都至少存在三次网络交互:1. 产生log ID;2. prepare阶段;3. accept阶段。

所以,Mulit-Paxos基于Basic-Paxos做了优化,在Paxos集群中利用Paxos协议选举出唯一的leader,在leader有效期内所有的议案都只能由leader发起。

这里强化了协议的假设:即leader有效期内不会有其他server提出的议案。因此,对于后续的提案,我们可以简化掉产生log ID阶段和Prepare阶段,而是由唯一的leader产生log ID,然后直接执行Accept,得到多数派确认即表示提案达成一致(每条redo log可对应一个提案)。

相关产品

X-DB、OceanBase、Spanner都是使用Multi-Paxos来保障数据一致性。

MySQL Group Replication的xcom中也使用了Multi-Paxos。

参考资料

使用Multi-Paxos协议的日志同步与恢复

X-Paxos

X-Paxos是X-DB中的Multi-Paxos实现,通过异步流水线化、Batching和Pipeline等手段提升性能。

参考资料

阿里如何实现高性能分布式强一致的独立 Paxos 基础库

PaxosStore

PaxosStore是我司WXG基于Paxos实现的分布式一致性中间件,在微信的用户账号管理、用户关系管理、即使消息、社交网络、在线支付等场景中广泛应用。

参考资料

PaxosStore:High-availability Storage Made Practical in WeChat》,PaxosStore在VLDB发的论文

开源实现

PaxosStore(C++)

https://github.com/tencent/paxosstore

PaxosStore是腾讯公司WXG基于Paxos实现的分布式一致性中间件。

PhxPaxos(C++)

https://github.com/Tencent/phxPaxos

PhxPaxos是腾讯公司微信后台团队自主研发的一套基于Paxos协议的多机状态拷贝类库。它以库函数的方式嵌入到开发者的代码当中, 使得一些单机状态服务可以扩展到多机器,从而获得强一致性的多副本以及自动容灾的特性。这个类库在微信服务里面经过一系列的工程验证,并且其开发团队对它进行过大量的恶劣环境下的测试,使其在一致性的保证上更为健壮。

LibPaxos(C)

http://libPaxos.sourceforge.net/

LibPaxos的主要价值是可以用来做研究,可以让程序员对Paxos的细节了解更加清楚。

如果要基于LibPaxos实现一个可以用于生产环境的Paxos库,还需要做几个工作:

  • 各个单元的状态信息固化,防止宕机发生信息丢失;
  • 增加leader模型;
  • 改为多线程实现并合并learner、proposer、acceptor为一个进程;
  • 对库做充分细致的测试。 

Raft

Raft是斯坦福大学的Diego Ongaro、John Ousterhout两个人以易理解为目标设计的一致性算法,在2013年发布了论文:《In Search of an Understandable Consensus Algorithm》。从2013年发布到现在,已经有了十几种语言的Raft算法实现框架,较为出名的有etcd,Google的Kubernetes也是用了etcd作为他的服务发现框架。

与Paxos相比,Raft强调的是易理解、易实现,Raft和Paxos一样只要保证超过半数的节点正常就能够提供服务。

众所周知,当问题较为复杂时,可以把问题分解为几个小问题来处理,Raft也使用了分而治之的思想,把算法分为三个子问题:

  • 选举(Leader election)
  • 日志复制(Log replication)
  • 安全性(Safety)

 分解后,整个raft算法变得易理解、易论证、易实现。

相关产品

etcd使用Raft来保障数据一致性。

参考资料

In Search of an Understandable Consensus Algorithm》,Diego Ongaro,John Ousterhout,2013

一致性算法Raft详解

Mulit-Raft

许多NewSQL数据库的数据规模上限都定位在100TB以上,为了负载均衡,都会对数据进行分片(sharding),所以就需要使用多个Raft集群(即Multi-Raft),每个Raft集群对应一个分片。

在多个Raft集群间可增加协同来减少资源开销、提升性能(如:共享通信链接、合并消息等)。

相关产品

TiDB、CockroachDB、PolarDB都是使用Mulit-Raft来保障数据一致性。

Parallel-Raft

Parallel-Raft是PolarDB中的Multi-Raft实现,通过支持乱序日志复制(乱序确认、乱序提交、乱序应用)等手段来提升性能。

参考资料

面向云数据库,超低延迟文件系统PolarFS诞生了

PolarFS: An Ultra-low Latency and Failure Resilient Distributed File System for Shared Storage Cloud Database》,PolarDB在VLDB上发的论文

开源实现

etcd/raft(Go)

etcd里面使用raft做数据同步

https://github.com/etcd-io/etcd

应用广泛,成熟度高。因为是Go语言开发,集成到C/C++应用中比较困难。

TiKV/raft(Rust)

TiKV里面使用raft做数据同步

https://github.com/tikv/tikv

Rust语言目前还比较小众。

kudu/raft(C++)

kudu里面也使用了raft

https://github.com/apache/kudu

LogCabin(C++)

https://github.com/logcabin/logcabin

由Raft论文作者Diego Ongaro主导的开源项目,没有得到广泛应用,很久没更新了。

其他实现

目前有十几种语言实现的几十个Raft算法实现框架,参见:

https://raft.github.io

Raft和Multi-Paxos的区别

Raft是基于对Multi-Paxos的两个限制形成的:

  • 发送的请求的是连续的, 也就是说Raft的append 操作必须是连续的, 而Paxos可以并发 (这里并发只是append log的并发, 应用到状态机还是有序的)。
  • Raft选主有限制,必须包含最新、最全日志的节点才能被选为leader. 而Multi-Paxos没有这个限制,日志不完备的节点也能成为leader。

Raft可以看成是简化版的Multi-Paxos。

Multi-Paxos允许并发的写log,当leader节点故障后,剩余节点有可能都有日志空洞。所以选出新leader后, 需要将新leader里没有的log补全,在依次应用到状态机里。

参考资料

知乎里朱一聪做的比较相对客观、全面:

https://www.zhihu.com/question/36648084/answer/82332860

原文发布于微信公众号 - 腾讯技术工程(Tencent_TEG)

原文发表时间:2018-10-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏嵌入式程序猿

C8051F060单片机在数字电源控制器中的应用

引言 随着科技的发展,数字控制系统的应用越来越广泛。以前的模拟电源控制系统线路复杂,控制精度低,故障率高。因此开发全数字电源控制系统越来越重要。微控制器,微处理...

3176
来自专栏SDNLAB

ONOS系统架构之高可用实现方案的演进

在文章《ONOS高可用性和可扩展性实现初探》讲到了ONOS系统架构在高可用、可扩展方面技术概况,提到了系统在分布式集群中如何保证数据的一致性。在数据最终一致性方...

3466
来自专栏知识分享

4-51单片机WIFI学习(开发板51单片机自动冷启动下载原理)

上一篇链接 http://www.cnblogs.com/yangfengwu/p/8743936.html 这一篇说一下自己板子的51单片机自动冷启动下载原理...

4745
来自专栏黄奕坤的专栏

火焰图性能调优记

最近手头开发维护的一个辅助小工具经常接到投诉可用性问题, 于是抽时间定位了下, 一看吓一跳, 起初不起眼的一个组件的日志量直接翻了两个数量级。 这怎么吃得消 !

8252
来自专栏java思维导图

乐观锁和悲观锁的区别(最全面的分析)

如果你觉得文字太长,可以直接先看文末思维导图总结,小编已为你整理了作者的主要观点,供你回顾与快速阅读~

1244
来自专栏CodingToDie

微信机器人

使用它可以方便的完成 回复消息、搜索好友、被添加自动回复、获取好友信息等功能,当然功能不止于这些,这里我们用到了回复信息功能

1.2K2
来自专栏java工会

MVC设计模式

MVC模式(Model-View-Controller)是软件工程中的一种软件架构模式,把软件系统分为三个基本部分:模型(Model)、视图(View)和控制器...

1470
来自专栏安智客

《密码模块安全技术要求》解读

今天要讲到的是密码模块安全认证! 中国密码行业标准化技术委员会分别在2014年、2015年制定了GM/T 0028-2014《密码模块安全技术要求》和GM/T ...

6007
来自专栏玉树芝兰

如何用R和API免费获取Web数据?

API是获得Web数据的重要途径之一。想不想了解如何用R调用API,提取和整理你需要的免费Web数据呢?本文一步步为你详尽展示操作流程。

1332
来自专栏ThoughtWorks

被踢出去的用户

在还没有掌握全部证据之前就下结论会犯严重的错误,会使判断带有偏见。——《血字的研究》

772

扫码关注云+社区

领取腾讯云代金券