如何完美实现Paxos算法成员组变更
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实例是否可以实现成员组变更？但事实并不如此简单，下图就是一个失败的例子：
开始时集群为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被选定。
成员a向C-old集群发起一个commit请求，修改集群成员组为C-old-new={abc，cde}，使所有learner都学习刚通过的提案I的值。
多数派Q-old={bc}通过commit请求后，成员组C-old-new生效，集群之后使用Q-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被选定后，为使所有learner都学习提案J的值，向C-old-new集群发起commit请求，learner接收到请求后修改自己的成员组为C-new={abc，cde}，对于已不在集群配置中的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成员组变更的应用
白山的云存储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成员信息变更的同时可正常提供数据访问。相比每次只能变更一个成员信息的一阶段成员变更算法，可大大提高变更效率。
作者：吴义谱，花名“哈尔塔”，白山高级研发工程师，云存储CWN-X团队唯一指定表情包。先后就职于新浪、百度等知名互联网公司，爱好挑战百PB级存储数据可用性天花板，曾成功将ObjectStorage系统可用性提高至99.9999%；2015年参加小文件合并存储项目，减少小文件访问IO次数的同时，大幅提高其存储性能。
责编：钱曙光，关注架构和算法领域，寻求报道或者投稿请发邮件[email protected]，另有「CSDN 高级架构师群」，内有诸多知名互联网公司的大牛架构师，欢迎架构师加微信qianshuguangarch申请入群，备注姓名+公司+职位。