返回 登录
0

如何完美实现Paxos算法成员组变更

阅读2314

Paxos算法在分布式系统中至关重要,凡是多个过程需要达成某种一致的场景都使用该算法,比如,一台机器多个进程数据一致;分布式文件系统或分布式数据库中多客户端并发读写;分布式存储多个副本响应读写请求等。白山云科技(简称“白山”)的云存储团队在实现数据一致性技术方面,基于Paxos 算法,独创了二次Paxos成员组变更算法,以新思路完美实现Paxos成员组变更问题,本文主要对其实现方法进行了相关介绍。

一、 Paxos算法介绍

Paxos是Leslie Lamport为解决分布式系统一致性问题,提出的一种基于消息传递一致性算法。在基于消息传递通信模型的分布式系统中,进程可能会因错误而停止、异常而重启,消息可能在网络传输过程中出现延迟、丢失、重复。在不考虑拜占庭将军问题(即消息篡改)的情况下,Paxos算法可解决分布式系统中就某个值如何达成一致的问题。

Paxos将参与者分为proposer、acceptor和learner;一个参与者可同时扮演多个不同角色。proposer提出提案,信息包括提案编号n和提议的value;acceptor作为提案处理者,有权决定接受(accept)或拒绝提案,若提案获得多数acceptors的接受,则称该提案被选定(chosen);learner只能学习已被选定的提案。Paxos通过活性约束和安全性约束保证算法的正确性:

(1)活性约束确保最终有一个提案被选定;
(2)安全性约束包括:

  • 约束1:acceptor只能选定由proposer提出的提案;
  • 约束2:一次Paxos instance算法中只能有一个值被选定;
  • 约束3:learner只能学习已被选定提案的值。

Lamport通过加强以上3个约束(尤其是约束2)得到Paxos算法,Lamport在《Paxos Made Simple》中用大量篇幅加强约束2,得到Paxos两阶段提交过程:

  • phase1a. proposer选择一个提案编号N,并将prepare请求发送给acceptors;
  • phase1b. acceptor收到提案N的prepare请求后,如果N不小于它之前响应过prepare请求的编号,那么acceptor响应通过该prepare请求,并返回之前通过编号最大的提案的value(如果存在的话),同时不会通过任何编号小于N的提案。
  • phase2a. proposer收到多数派个的acceptor对编号为N的prepare请求时,它将发送一个value为V、提案为N的accept请求给acceptors。(V是phase1b中响应提案N中编号最大的value,或proposer此次Paxos需要提交的值。)
  • phase2b. acceptor收到提案N的accept请求,只要它尚未对编号大于N的prepare请求作出响应,就可以通过这个提案。

通过以上两个阶段完成一次Paxos,一次Paxos实例中只确定一个value值。Lamport在论文中证明了算法的正确性,但在实践中Paxos算法还有许多细节问题需进一步解决,如Paxos成员组变更问题。

二、Paxos成员组变更

上述分析基于集群成员组配置不变的假设,但在实践中,机器宕机导致成员下线、新旧成员替换不可避免,在成员组配置信息发生变更之后,如何保持成员组配置信息的一致性,Lamport在论文中并没有给出具体解决方案,但保持成员组配置信息在集群中一致是正确运行Paxos的前提。

(1)暂停集群, 修改所有成员的配置信息,再重启整个集群,这种方式可以解决成员组配置信息一致性的问题,但同时透露出的问题也是明显的——集群暂停过程中无法提供服务。
(2)Paxos本身就是解决如何保持一致性问题的,把成员组作为Paxos提案的value,在集群中运行一次Paxos实例是否可以实现成员组变更?但事实并不如此简单,下图就是一个失败的例子:

图片描述

一次Paxos成员组变更实例

开始时集群为a,b,c 3个成员,成员组为{abc},记C-old;变更后为c,d,e 3个成员,成员组为{cde},记C-new, 假设在t1时刻,成员a提交一个value为{cde}的提案N, 在t2时刻, 成员a和b还未完成phase2b,其成员组仍为C-old;成员c和d已完成phase2b, 其成员组为C-new;如果此时集群重启,重新选举leader,那么集群将选举出2个,一个通过多数派成员{ab}选举成功,另一个通过多数派{cd}选举成功。显然不符合Paxos的安全性约束。

为有效解决Paxos成员组变更问题,白山云存储CWN-X推出基于二次Paxos成员组变更算法。

三、白山独创二次Paxos成员组变更算法

通过以上分析可知,Paxos成员组变更必须满足以下3个约束条件:

  • 约束1:成员组变更过程中不影响正常服务,集群可正常提供读写请求;
  • 约束2:成员组变更过程中不能出现多主的情况;
  • 约束3:成员组变更过程在任何异常情况下中断,恢复后能继续完成变更操作。

一次Paxos成员组变更方案失败,是由于违反了约束2:在变更过程中C-old、C-new成员组同时独立形成多数派quorum-B。二次Paxos成员组算法就是打破这种情况,即:在任何时刻C-old、C-new只能形成一个多数派quorum-B。

二次Paxos成员组变更算法先运行1次Paxos将成员组C-old设置为C-old-new的中间状态, 再运行1次将成员组C-old-new设置为C-new。

二次Paxos的成员组变更过程中,每次Paxos instance用一个version标识, version单调递增, 且约束只有大于当前version的提案才能被提交成功。

假设集群初始成员组为C-old, 变更后的成员组为C-new,中间状态为C-old-new, Q-old为C-old的多数派,Q-new为C-new的多数派,Q-old-new为C-old-new的多数派(即同时满足Q-old和Q-new)。为方便叙述,假设C-old为{abc},C-new为{cde},则C-old-new为{abc,cde}。

图片描述

集群初始状态

假设成员a提交提案编号为I、version为K、value为C-old-new={abc,cde}的成员组变更请求,在Q-old={ab}多数派通过提案I后,提案I被选定。

图片描述

提案I被选定

成员a向C-old集群发起一个commit请求,修改集群成员组为C-old-new={abc,cde},使所有learner都学习刚通过的提案I的值。

图片描述

learner接收commit请求

多数派Q-old={bc}通过commit请求后,成员组C-old-new生效,集群之后使用Q-old-new通过任何一个提案;此时,为使d、e也知道已被加入到集群中, 需将C-old-new同步到d、e。

图片描述

C-old-new同步到d、e

此时,a还有可能是C-old={abc},但不影响Paxos的安全性约束2,因为a提交的提案被选定则必然Q-old多数派通过了该提案,而满足Q-old必然无法满足Q-old-new,所以这个过程可以保证不会同时存在两个多数派Q-old和Q-old-new通过2个Paxos决议。

如果过程中集群全部宕机, 在此之前没有任何acceptor通过该提案I,恢复后集群仍使用C-old配置提供服务;如果宕机前已有acceptor通过提案I, 根据phase2a提案value是C-old-new, 完成这次决议后, 集群使用C-old-new提供服务,满足约束1和约束3。

完成第一次Paxos后, 集群多数派Q-old-new的成员组为C-old-new, 此时进行第二次Paxos, 第二次Paxos将配置C-old-new设置为C-new。成员a将version为M(M>K)、 value为C-new的提案J发送给C-old-new成员组, 当Q-old-new多数派通过提案J时, 意味着该提案已被选定。

图片描述

提案J被选定

提案J被选定后,为使所有learner都学习提案J的值,向C-old-new集群发起commit请求,learner接收到请求后修改自己的成员组为C-new={abc,cde},对于已不在集群配置中的a、b直接自行删除。

图片描述

删除a、b

与第一次Paxos类似, 不可能同时存在2个多数派Q-new和Q-old-new完成2个Paxos决议,集群宕机恢复后可正常提供服务,满足约束1,2和3。

用二次Paxos成员组算法解决图1中的问题,如下图,开始时集群成员组C-old, 需要变更为C-new, 假设a提交一个value为{abc,cde}的提案I,在t3时刻提案I完成;随后开始第二次Paxos, a提交一个value为{cde}的提案J, 直到提案J完成, 整个过程中始终未出现同时存在两个多数派完成二次paxos决议。

图片描述

二次Paxos成员组变更实例

四、Paxos成员组变更的应用

白山的云存储CWN-X中使用EC算法将1个group(一组文件的集合)的数据编码成N个数据块和M个校验块,N+M个块分布在不同磁盘上,每个块所在磁盘被称为1个member,N+M个member组成一个集群。使用Paxos可保证集群中所有member成员信息的一致性。

日常运维中EC数据块损坏或者磁盘下线时需要变更EC集群中member成员信息,白山的云存储CWN-X使用基于二次Paxos成员组变更算法变更EC集群中member成员信息,在确保数据块安全的情况下一次同时变更M个成员。

图片描述

EC集群member成员组信息

目前该算法服务于生产线上百万个EC集群,member成员信息变更的同时可正常提供数据访问。相比每次只能变更一个成员信息的一阶段成员变更算法,可大大提高变更效率。

作者:吴义谱,花名“哈尔塔”,白山高级研发工程师,云存储CWN-X团队唯一指定表情包。先后就职于新浪、百度等知名互联网公司,爱好挑战百PB级存储数据可用性天花板,曾成功将ObjectStorage系统可用性提高至99.9999%;2015年参加小文件合并存储项目,减少小文件访问IO次数的同时,大幅提高其存储性能。
责编:钱曙光,关注架构和算法领域,寻求报道或者投稿请发邮件qianshg@csdn.net,另有「CSDN 高级架构师群」,内有诸多知名互联网公司的大牛架构师,欢迎架构师加微信qianshuguangarch申请入群,备注姓名+公司+职位。

评论