泽民博客 ☰ Menu

Paxos

使用Basic-Paxos协议的日志同步与恢复
在保证数据安全的基础上，保持服务的持续可用，是核心业务对底层数据存储系统的基本要求。业界常见MySQL/Oracle的1主N备的方案面临的问题是“最大可用（Maximum Availability）”和“最大保护（Maximum Protection）”模式间的艰难抉择，其中“最大可用”模式，表示主机尽力将数据同步到备机之后才返回成功，如果备机宕机或网络中断那么主机则单独提供服务，这意味着主备都宕机情况下可能的数据丢失；“最大保护”模式，表示主机一定要将数据同步到备机后才能返回成功，则意味着在任意备机宕机或网络中断情况下主机不得不停服务等待备机或网络恢复。可见传统主备方式下，如果要求数据不丢，那么基本放弃了服务的持续可用能力。
基于Paxos协议的数据同步与传统主备方式最大的区别在与Paxos只需任意超过半数的副本在线且相互通信正常，就可以保证服务的持续可用，且数据不丢失。本文不再分析Paxos协议本身（参考原始论文，以及这篇比较通俗的分析http://mp.weixin.qq.com/s?__biz=MjM5MDg2NjIyMA==&mid=203607654&idx=1&sn=bfe71374fbca7ec5adf31bd3500ab95a&key=8ea74966bf01cfb6684dc066454e04bb5194d780db67f87b55480b52800238c2dfae323218ee8645f0c094e607ea7e6f&ascene=1&uin=MjA1MDk3Njk1&devicetype=webwx&version=70000001&pass_ticket=2ivcW%2FcENyzkz%2FGjIaPDdMzzf%2Bberd36%2FR3FYecikmo%3D ），而是基于Paxos协议，讨论一种在多副本上持久化数据的高可用方案。需要注意的是，本方案不考虑运行性能，只是为了帮助说清协议的工程实现。
我们将数据持久化的需求抽象为：在N个server的机群上，持久化数据库或者文件系统的操作日志，并且为每条日志分配连续递增的logID，我们允许多个客户端并发的向机群内的任意机器发送日志同步请求。对于高可用的需求为：在N个server中只要有超过半数的server（majority）正常服务，并且相互通信正常，那么这个机器就可以持续的提供日志持久化和查询服务。
将每条日志的持久化流程都看作一个“Paxos Instance”，不同的logID代表不同的Paxos Instance形成的“决议（decision）”。即每一个logID标识着一轮完整paxos协议流程的执行，最后形成decision。机群内的每个server同时作为paxos的acceptor和proposer。
获取LogID



Server收到客户端的持久化日志请求后，先要决定这条日志的logID，为了尽量减少后续Paxos协议流程中处理并发冲突造成的回退，要尽量分配与目前已经持久化和正在持久化中的日志不重复的logID，同步也要容忍少于半数的server宕机与网络故障。因此向所有acceptor查询它们本地目前已写盘的最大logID，而只需收集到majority返回的结果，并选择其中最大的logID+1作为本次待持久化日志的logID。从上面的描述可以看出，这里并不能保证并发提交的两条日志一定被分配到不同的logID，而是依靠后续的paxos协议流程来达到对一个logID形成唯一的decision的目的。
产生ProposalID



获取LogID后，server作为proposer开始针对当前logID，执行Paxos Instance，先产生proposalID，根据paxos协议的要求，proposalID要满足全局唯一和递增序，即对同一个server来说后产生的proposalID一定大于之前产生的，这里我们使用server的timestamp联合ip作为proposalID，其中timestamp在高位，ip在低位，只要时钟的误差范围小于server重启的时间，就可以满足“同一个server后产生的proposalID一定大于之前产生的”。
Prepare阶段



Proposer准备好proposalID后，将proposalID作为 “提案（proposal）”发送给所有的acceptor。根据Paxos协议P1b的约束，这个阶段发送的proposal并不需要携带日志内容，而只需要发送proposalID。Acceptor收到proposal后，根据Paxos协议P1b判断是否要“回应（response）”：只有在这个Paxos Instance内（即针对这个logID）没有response过proposalID大于等于当前proposal的，并且也没有“接受（accept）”过proposalID大于当前proposal的，才可以response，并承诺不再accept那些proposalID小于当前proposal的。



如果已经accept过proposal，那么连同proposalID最大的日志内容一同response。为了遵守P1b的约束，在宕机恢复后也能满足，因此在response前，需要将当前proposalID写到本地磁盘。



上述Prepare阶段的处理流程暗示，对于分配到相同logID的不同日志，由于他们的proposalID不同，acceptor在response一个较小proposalID后，是允许继续response后来的较大的proposalID的。
Accept请求阶段



Proposer收集到majority的response后，来决定后续是否将要发出的“accept请求（accept request）”，判断如果majority的response中的日志内容都为空，那么可以向所有acceptor发出accept request并携带上当前日志内容；而如果有任意的response中的日志内容有效，那么说明当前logID已经别其他日志占用，且其他日志可能已经在majority上持久化，因此需要回退，回到第一步“获取logID”重新执行。
Accept处理阶段



Acceptor收到proposer的accept request后，根据上文中“Prepare阶段”的承诺，判断当前logID下，曾经response过的最大proposalID，如果小于等于当前proposal的，则可以继续执行后续的accept处理逻辑；而如果大于当前proposal的，则说明有logID切proposalID更大的proposal在并发执行，当前proposal会被覆盖，因此回复proposer要求回退到第一步“获取logID”重新执行。



然后Accept处理逻辑将当前proposal连同proposalID一起写到本地磁盘，给proposer回复成功。Proposer收集到majority的回复成功后，说明本条日志已经在机群上持久化成功，可以保证后续一定不会被覆盖或丢失，可以给客户端返回了。



上述accept处理阶段的流程暗示，可能会存在针对一个logID，日志只在少于半数的acceptor上写到本地磁盘，而acceptor同时response了proposalID更大的proposal，而使得当前logID下没有任何日志在机群上持久化成功。即一个logID可能没有标识任何有效日志，这种情况是可以接受的。
日志内容读取



已经在机群上持久化成功的日志，需要能够被读取出来，一般的应用模式是按照logID的顺序依次读取并回放日志。读取的时候针对每一条logID，需要执行一轮完整的paxos协议流程，将accept处理阶段成功的日志内容返回。需要注意的是，在accept请求阶段的处理逻辑变化：Proposer收集到majority的response后，判断如果majority的response中的日志内容都为空，那么向所有acceptor发出日志内容为空的accept request；而如果有任意的response中的日志内容有效，则选择proposalID最大的日志内容放入accept request。后续收到majority的accept回复成功后，才可以返回日志内容作为读取结果。



这里的流程暗示，针对一个logID，如果之前已经有日志内容持久化成功，那么这条日志一定会被选为accept request；而如果之前日志内容仅仅在小于半数的server上写到磁盘，那么最终这条logID的内容有可能是有效日志，也有可能内容为空。
为什么读取也需要执行Paxos流程



这是基于一致性的考虑，即针对一条logID，读取出的内容后续应该永远不变。因此如果一条logID在写入过程中，并未在majority上持久化，那么需要在读取返回结果前，将这个结果在机群上持久化成功。

使用Multi-Paxos协议的日志同步与恢复
本文是Paxos三部曲中的第二篇。在前一篇文章《使用Basic-Paxos协议的日志同步与恢复》（http://oceanbase.org.cn/?p=90）中，我们讨论了基于Basic-Paxos协议的日志同步方案，在这个方案中，所有成员的身份都是平等的，任何成员都可以提出日志持久化的提案，并且尝试在成员组中进行持久化。而在实际的工程应用中，往往需要一个成员在一段时间内保持唯一leader的身份，来服务对数据的增删改操作，产生redolog，并尝试在成员组中进行持久化。本文讨论如何利用Paxos协议选举唯一的leader，以及使用leader将redolog在成员组中进行持久化和恢复的方法。



Basic-Paxos协议回顾
让我们先来回顾下Basic-Paxos协议的执行流程：为了简化描述，我们假设一个Paxos集群，每个server同时担任proposer和acceptor，任何server都可以发起持久化redolog的请求，首先要向所有的server查询当前最大logID，从多数派的应答结果中选择最大的logID，加1后作为执行本次Paxos Instance的唯一标识；然后进入Paxos的prepare阶段，产生proposalID，并决定出要投票的redolog（即议案）；在accept阶段对prepare阶段产生的议案进行投票，得到多数派确认后返回成功。由此我们可以看出Basic-Paxos协议的执行流程针对每条redolog都至少存在三次网络交互的延迟（1. 产生logID；2. prepare阶段；3. accept阶段）。下面我们逐个分析每个阶段的必要性：



产生logID，由于Basic-Paxos并不假设一段时间内只有唯一的proposer，因此可能由集群内的任意server发起redolog同步，因此不能由单一server维护logID，而是需要进行分布式协商，为不同的redolog分配全局唯一且有序的logID。
prepare阶段，上述一阶段的分布式协商logID并不能保证并发多个server分配得到得logID是唯一的，即会出现若干条不同的redolog在同一个Paxos Instance中投票的情况，而这正是Basic-Paxos协议的基本假设，因此需要执行prepare，以决定出这个Paxos Instance内的要进行投票的redolog（即议案）。如果执行prepare决定出的议案与server自己要投票的redolog内容不同，则需要重新产生logID。
accept阶段，对prepare阶段决定出的议案进行投票，得到多数派确认后表示redolog同步成功，否则需要重新产生logID。
在这三个阶段中，根据Paxos协议的约束，server应答prepare消息和accept消息前都要持久化本地redolog，以避免重启后的行为与重启前自相矛盾。因此最终可以得到使用Basic-Paxos进行redolog同步的延迟包括了3次网络交互加2次写本地磁盘。并且在高并发的情况下，不同redolog可能被分配到相同的logID，最差可能会在accept阶段才会失败重试。



Multi-Paxos协议概述
在Paxos集群中利用Paxos协议选举唯一的leader，在leader有效期内所有的议案都只能由leader发起，这里强化了协议的假设：即leader有效期内不会有其他server提出的议案。因此对于redolog的同步过程，我们可以简化掉产生logID阶段和prepare阶段，而是由唯一的leader产生logID，然后直接执行accept，得到多数派确认即表示redolog同步成功。



leader的产生
首先，需要明确的是Multi-Paxos协议并不假设全局必须只能有唯一的leader来生成日志，它允许有多个“自认为是leader的server”来并发生成日志，这样的场景即退化为Basic-Paxos。



Multi-Paxos可以简单的理解为，经过一轮的Basic-Paxos，成功得到多数派accept的proposer即成为leader（这个过程称为leader Elect），之后可以通过lease机制，保持这个leader的身份，使得其他proposer不再发起提案，这样就进入了一个leader任期。在leader任期中，由于没有了并发冲突，这个leader在对后续的日志进行投票时，不必每次都向多数派询问logID，也不必执行prepare阶段，直接执行accept阶段即可。



因此在Multi-Paxos中，我们将leader Elect过程中的prepare操作，视为对leader任期内将要写的所有日志的一次性prepare操作，在leader任期内投票的所有日志将携带有相同的proposalID。需要强调的是，为了遵守Basic-Paxos协议约束，在leader Elect的prepare阶段，acceptor应答prepare成功的消息之前要先将这次prepare请求所携带的proposalID持久化到本地。



对于leader Elect过程，我们并不关心leader Elect提案和决议的具体内容，因为无论执行多少次leader Elect，从Basic-Paxos的角度来看，都是同一个Paxos Instance在对已经形成的决议反复进行投票而已。而执行leader Elect这个过程，我们最关注的是要得到最近一次形成决议的proposer是谁，以及它的proposalID。在leader Elect过程中，得到多数派accept的proposer将成为leader，而它本次所用的proposalID即成为它任期内对所有日志（包括新增日志和后文将提到的重确认日志）进行投票时将要使用的proposalID（称为leader ProposalID）。



这里还需要考虑的一个问题是，由于多个server并发执行leader Elect，可能出现两个server在相近的时间内，先后执行leader Elect都成功，都认为自己是leader的情况。因此，当选leader在开始以leader身份提供服务之前，要使用leader ProposalID写一条日志（称为StartWorking日志），得到多数派确认后，再开始提供服务。这是因为根据Basic-Paxos的约束，可以推断出：先执行leader Elect成功的leader（称为L1），它的proposalID（称为P1）一定会小于后执行leader Elect成功的leader（称为L2）的proposalID（称为P2），而经过了两轮leader Elect，机群内多数派持久化的proposalID一定是P2，而此时L1使用P1执行accept时，由于P1<P2，它将无法得到机群内多数派的accept。



Confirm日志的优化
在Paxos协议中，对于决议的读取也是需要执行一轮Paxos过程的，在实际工程中做数据恢复时，对每条日志都执行一轮Paxos的代价过大，因此引入需要引入一种被成为confirm的机制，即leader持久化一条日志，得到多数派的accept后，就再写一条针对这条日志的confirm日志，表示这条日志已经确认形成了多数派备份，在回放日志时，判断如果一条日志有对应的confirm日志，则可以直接读取本地内容，而不需要再执行一轮Paxos。confirm日志只要写本地即可，不需要同步到备机，但是出于提示备机及时回放收到日志的考虑（备机收到一条日志后并不能立即回放，需要确认这条日志已经形成多数派备份才能回放），leader也会批量的给备机同步confirm日志。出于性能的考虑，confirm日志往往是延迟的成批写出去，因此仍然会出现部分日志已经形成多数派备份，但是没有对应的confirm日志的情况，对于这些日志，需要在恢复过程中进行重确认。



在实际的工程实践中，可以使用基于logID的滑动窗口机制来限制confirm日志与对应的原始日志的距离，以简化日志回放与查询逻辑。



新任leader对日志的重确认
如上一节所述，在恢复过程中，拥有对应confirm日志的原始日志，可以被直接回放。而没有对应confirm日志的原始日志，则需要执行一轮Paxos，这个过程被成为重确认。



此外日志中的“空洞”，也需要进行重确认，因为当前leader再上一任leader的任期内可能错过了一些日志的同步，而这些日志在其他机器上形成多了多数派。由于logID连续递增，被错过的日志就成了连续logID连续递增序列中的“空洞”，需要通过重确认来补全这些“空洞”位置的日志。



新任leader在开始执行重确认前，需要先知道重确认的结束位置，因为leader本地相对于集群内多数派可能已经落后很多日志，所以需要想集群内其他server发送请求，查询每个server本地的最大logID，并从多数派的应答中选择最大的logID作为重确认的结束位置。也即开始提供服务后写日志的起始logID。



对于每条日志的重确认，需要执行一轮完整的Paxos过程，可能有些日志在恢复前确实未形成多数派备份，需要通过重新执行Paxos来把这些日志重新持久化才能回放。这种不管日志是否曾经形成多数派备份，都重新尝试持久化的原则，我们称之为“最大commit原则”。之所以要遵守“最大commit原则”，是因为我们无法区分出来未形成多数派备份的日志，而这些日志在上一任leader任期内，也必然是“未决”状态，尚未应答客户端，所以无论如何都重新持久化都是安全的。比如A/B/C三个server，一条日志在A/B上持久化成功，已经形成多数派，然后B宕机；另一种情况，A/B/C三个server，一条日志只在A上持久化成功，超时未形成多数派，然后B宕机。上述两种情况，最终的状态都是A上有一条日志，C上没有，在恢复时无法区分这条日志是否曾经形成过多数派，因此干脆按照“最大commit原则”将这条日志尝试重新在A/C上持久化后再回放。



需要注意的是，重确认日志时，要使用当前的leader ProposalID作为Paxos协议中的proposalID来对日志执行Paxos过程。因此在回放日志时，对于logID相同的多条日志，要以proposalID最大的为准。



“幽灵复现”日志的处理
使用Paxos协议处理日志的备份与恢复，可以保证确认形成多数派的日志不丢失，但是无法避免一种被称为“幽灵复现”的现象，如下图所示：



Leader



A



B



C



第一轮



A



1-10



1-5



1-5



第二轮



B



宕机



1-6,20



1-6,20



第三轮



A



1-20



1-20



1-20



第一轮中A被选为Leader，写下了1-10号日志，其中1-5号日志形成了多数派，并且已给客户端应答，而对于6-10号日志，客户端超时未能得到应答。
第二轮，A宕机，B被选为Leader，由于B和C的最大的logID都是5，因此B不会去重确认6-10号日志，而是从6开始写新的日志，此时如果客户端来查询的话，是查询不到6-10号日志内容的，此后第二轮又写入了6-20号日志，但是只有6号和20号日志在多数派上持久化成功。
第三轮，A又被选为Leader，从多数派中可以得到最大logID为20，因此要将7-20号日志执行重确认，其中就包括了A上的7-10号日志，之后客户端再来查询的话，会发现上次查询不到的7-10号日志又像幽灵一样重新出现了。
对于将Paxos协议应用在数据库日志同步场景的情况，“幽灵复现”问题是不可接受，一个简单的例子就是转账场景，用户转账时如果返回结果超时，那么往往会查询一下转账是否成功，来决定是否重试一下。如果第一次查询转账结果时，发现未生效而重试，而转账事务日志作为幽灵复现日志重新出现的话，就造成了用户重复转账。



       为了处理“幽灵复现”问题，我们在每条日志的内容中保存一个generateID，leader在生成这条日志时以当前的leader ProposalID作为generateID。按logID顺序回放日志时，因为leader在开始服务之前一定会写一条StartWorking日志，所以如果出现generateID相对前一条日志变小的情况，说明这是一条“幽灵复现”日志（它的generateID会小于StartWorking日志），要忽略掉这条日志。


总结
本文介绍了在Basic-Paxos协议基础之上构建Multi-Paxos协议的几个要点：通过使用Paxos选举leader来避免对每条日志都执行Paxos的三阶段交互，而是将绝大多数场景简化为一阶段交互，并且讨论了基于Paxos协议的“最大commit原则”；通过引入confirm日志来简化回放处理；通过引入Start Working日志和generateID来处理“幽灵复现”问题。



Paxos成员组变更



本文是Paxos三部曲的第三篇，在前一篇文章《使用Multi-Paxos协议的日志同步与恢复》（http://oceanbase.org.cn/?p=111）中，我们讨论了基于Multi-Paxos协议的日志同步方案，在这个方案中，我们有一个隐含的前提，就是Paxos成员组是确定的，并且所有成员启动后都能加载一致的成员组信息。而在实际的工程应用中，往往需要在不停服务的情况下修改成员组，最典型的比如类似spanner的系统，对子表的迁移操作过程，就包含了对其Paxos成员组的变更操作。本文将基于Raft论文，讨论通用的成员组变更方法，和简化的一阶段成员组变更方法，以及成员组变更与日志同步操作的关系。



请注意，本文假设读者已了解Basic-Paxos和Multi-Paxos协议，并且本文假设集群工作在上一篇文章所述的Multi-Paxos协议之下。



在线成员组变更的难点
Paxos执行两阶段投票协议的前提是有一个明确的Paxos成员组，而对于完全无中心化的Paoxs协议来说，成员组的内容本身又需要通过Paxos协议来维护一致性。对于变更后的新成员组从什么时机开始生效，存在“先有鸡还是先有蛋”的问题，如果还像同步普通日志一样来同步新成员组，那么在新旧成员组交接的过程中宕机，则可能出现选票分裂的情况，比如由成员组ABC变更为ABCDE过程中宕机，AB未持久化新成员组，CED已持久化新成员组，那么在宕机重启后，会出现AB形成了旧成员组的多数派，而CDE形成了新成员组的多数派，会出现两个leader的情况。



因此我们可以总结对在线成员组变更方案的几个基本要求：



P1. 成员组正常Paxos日志同步服务不中断



P2. 任何情况下宕机都能够保证存活的多数派成员间能够选举leader



P3. 不会出现1个以上的多数派选出大于1个leader的情况



成员组变更的基本思路
成员组变更代表了“旧朝代”的结束和“新朝代”的开启，可以理解为依次执行如下两个投票操作：



Pa. “旧朝代”的多数派成员对“旧朝代结束”这件事达成一致，达成一致后旧成员组不再投票



Pb. “新朝代”的多数派成员对“新朝代开启”这件事达成一致，达成一致后新成员组开始投票



但是简单的按照这种两阶段的操作进行成员变更，虽然能够保证上述P3的约束，但是无法满足P1和P2，比如Pa执行成功后，在Pb执行成功之前：没有成员组可以投票，服务会中断；如果集群宕机重启，新的成员组的各个成员由于还未对新成员组达成一致，而无法选出leader。



为了保证P1和P2的约束，我们在上述基本成员变更的基础上，将Pa和Pb合并为一步操作，即新旧成员组一起对“旧朝代结束+新朝代开启”这件事达成一致后，才表示成员组变更成功。在开始成员变更的投票后，集群就进入了一个“中间状态”，在这个过程中宕机恢复后可能退回“旧朝代”也可能进入“新朝代”，因此在这个中间状态过程中投票的日志，要求在新旧成员组中都达成一致。



在这个基本思路的指导下，可以抽象出一个通用的成员变更方法：Jonit-Consensus。



通用成员组变更方法–Joint-Consensus
Joint-Consensus是Raft论文中提到的两阶段成员变更方案，这个方案比较通用，甚至可以做到完整的成员组替换，但是两阶段方案的工程实现都比较复杂，而通用的场景需求又不多，因此在他博士论文最终版的成员变更一章中，更多篇幅分析了简化的一阶段方案（下一节讨论），而把Joint-Consensus的篇幅省略了很多。但是作为成员变更方案的基础，我这里还是希望能够从Joint-Consensus开始，分析它的正确性，并且尝试推导出一阶段的成员变更方法。



Joint-Consensus的方案如下，设成员变更前的成员组为C(old)，变更后的成员组为C(new)，成员组内容中包含单调增长的Version。



变更操作
成员变更操作前，C(old)的多数派中持久化的成员组为[[C(old)]]
成员变更操作由leader执行，leader收到命令后，将成员组[[C(old),C(new)]]发送给C(old)∪C(new)的所有成员，在此之后新的日志同步需要保证得到C(old)和C(new)两个多数派的确认
leader收到C(old)和C(new)两个多数派确认后，将成员组[[C(new)]]发送给C(new)的所有成员，收到C(new)多数派确认后，表示成员变更成功，后续的日志只要得到C(new)多数派确认即可
协议约束
Version投票约束：持有Version较大的成员，不能给持有Version较小的候选人投票
最大commit原则：
持有[[C(old),C(new)]]的成员当选leader后，要重新对[[C(old),C(new)]]分别在C(old)和C(new)内投票达成多数派，然后继续成员变更流程，对[[C(new)]]在C(new)内投票达成多数派。然后才能开始leader恢复流程和leader服务
持有[[C(old)]]的成员当选leader后，要重新对[[C(old)]]在C(old)内投票达成多数派，然后才能开始leader恢复流程和leader服务
持有[[C(new)]]的成员当选leader后，要重新对[[C(new)]]在C(new)内投票达成多数派，然后才能开始leader恢复流程和leader服务
选主投票原则
持有[[C(old),C(new)]]的候选人要得到C(old)和C(new)两个多数派都确认，才能当选leader
持有[[C(old)]]的候选人要得到C(old)多数派确认，才能当选leader
持有[[C(new)]]的候选人要得到C(new)多数派确认，才能当选leader
Joint-Consensus的协议分析
成员变更过程中，对[[C(old),C(new)]]的投票要求在C(old)和C(new)中都得到多数派的确认，是为了保证在C(old)投票“旧朝代结束”成功的同时，“新朝代开启”能够在C(new)生效，不会出现服务中断或者宕机重启后无法选出leader的情况。
对于成员变更的第二步，在[[C(old),C(new)]]形成两个多数派确认后，还要对[[C(new)]]在C(new)中进行投票，是为了结束需要向C(old)和C(new)都同步数据的“中间状态”。[[C(new)]]得到C(new)的多数派确认后，由于后面将要提到的“Version投票约束”原则的保证，可以确保后续宕机重启只有C(new)中的成员能够当选leader，因此无需再向C(old)同步数据。
Version投票约束，实际上是Paxos协议Prepare阶段对ProposalID的约束，如本系列的前一篇Multi-Paxos一文所述，选主过程本质上是Paoxs的Prepare过程，我们将成员组内容视为Paxos提案，那么Version就是ProposalID，Paxos不允许Prepare阶段应答ProposalID更低的提案，所以我们要求持有较大Version的成员不能给持有较小Version的候选人投票。从直观上来分析，Version投票约束可以保证，在[[C(new)]]形成多数派确认后，C(old)中那些错过了成员变更日志的成员，不可能再得到C(old)多数派的选票。
最大commit原则，是Paxos最重要的隐含规则之一，在成员变更过程中的宕机重启，持有[[C(old),C(new)]]的成员可能当选leader，但是[[C(old),C(new)]]可能并未形成多数派，根据成员变更协议，成员变更过程要在[[C(old),C(new)]]形成两个多数派确认后，才能对[[C(new)]]进行投票。否则如果立即对[[C(new)]]进行投票，宕机重启后，可能出现C(old)和C(new)两个投票组各自选出一个leader。因此，持有[[C(old),C(new)]]的成员当选leader后，无论[[C(old),C(new)]]是否已经形成两个成员组的多数派确认，我们都按照最大commit原则对它重新投票确认形成多数派后，才能继续leader后续的上任处理。
选主投票原则，持有[[C(old),C(new)]]的成员当选leader，需要得到C(old)和C(new)两个多数派都确认，是为了避免C(old)与C(new)各自形成多数派选出两个leader的情况。在成员变更过程中，可以归结为如下两种情况：
对[[C(old),C(new)]]的投票已开始，但未形成两个多数派确认，集群宕机。那么重启选主时，要么持有[[C(old)]]的成员当选leader，要么持有[[C(old),C(new)]]的成员当选leader。
对[[C(new)]]的投票已开始，但未形成多数派确认，集群宕机。那么重启选主时，要么持有[[C(new)]]的成员当选leader，要么持有[[C(old),C(new)]]的成员当选leader。
如上文所述，持有[[C(old),C(new)]]的leader要先完成成员变更流程。之后再执行Multi-Paxox中的日志“重确认”，因此日志“重确认”过程不会进入“要得到两个成员组确认”的情况。



Joint-Consensus允许C(old)与C(new)交集为空，在这种情况下成员变更后，旧leader要卸任，并且将leader权限转让给确认[[C(new)]]的一个多数派成员。



Joint-Consensus方案比较通用且容易理解，但是实现比较复杂，同时两阶段的变更协议也会在一定程度上影响变更过程中的服务可用性，因此我们期望增强成员变更的限制，以简化操作流程，考虑Joint-Consensus成员变更，之所以分为两个阶段，是因为对C(old)与C(new)的关系没有做任何假设，为了避免C(old)和C(new)各自形成多数派选出两个leader，才引入了两阶段方案。因此如果增强成员组变更的限制，假设C(old)与C(new)任意的多数派交集不为空，这两个成员组就无法各自形成多数派，那么成员变更方案就可能简化为一阶段。



一阶段成员变更方法
Raft作者在他博士论文最终版的成员变更一章中，简化了Joint-Consensus的篇幅，而着重介绍了一阶段的成员变更方法，在工程上一阶段的成员变更方法确实更简单实用，下面是我对一阶段成员变更方案的一些分析。



每次只变更一个成员
如上一节所述，如果做到C(old)与C(new)任意的多数派交集都不为空，那么即可保证C(old)与C(new)无法各自形成多数派投票。方法就是每次成员变更只允许增加或删除一个成员。假设C(old)的成员数为N，分析如下：



C(new)成员数为N+1
假设选出的leader持有C(new)，那么一定是C(new)中有多数派，即(N+1)/2+1的成员给leader投票，那么持有C(old)且未给leader投票的成员最多为(N+1)-((N+1)/2+1)=(N-1)/2，这个值小于C(old)的多数派值N/2+1，无法选出leader
假设选出的leader持有C(old)，那么一定是C(old)中有多数派，即N/2+1的成员给leader投票，那么持有C(new)且未给leader投票的成员最多为(N+1)-(N/2+1)=N/2，这个值小于C(new)的多数派值(N+1)/2+1，无法选出leader
C(new)成员数为N-1
假设选出的leader持有C(new)，那么一定是C(new)中有多数派，即(N-1)/2+1的成员给leader投票，那么持有C(old)且未给leader投票的成员最多为N-((N-1)/2+1)=(N-1)/2，这个值小于C(old)的多数派值N/2+1，无法选出leader
假设选出的leader持有C(old)，那么一定是C(old)中有多数派，即N/2+1的成员给leader投票，那么持有C(new)且未给leader投票的成员最多为N-(N/2+1)=(N-2)/2，这个值小于C(new)的多数派值(N-1)/2+1，无法选出leader
启用新成员组的时机
启用新成员组的时机是指从何时开始，对日志的投票开始使用C(new)进行，这里需要考虑的问题是成员变更过程中宕机，重启选主后，持有[[C(old)]]的成员被选为leader，在宕机前使用C(new)同步的日志是否可能丢失。分析如下几种情况：



下线成员，C(new)与C(old)多数派成员数相同，比如ABCDE变更为ABCD，C(new)的任意多数派集合一定是C(old)的某个多数派，变更过程中使用C(new)同步的日志，在C(old)中依然能够保持多数派。
下线成员，C(new)的多数派成员数小于C(old)，比如ABCD变更为ABC，这个情况比较特殊，我们来仔细分析，这种情况下在C(new)中形成的多数派成员只能达到C(old)成员数的一半，从严格的Basic-Paxos协议来分析，只做到N/2的成员确认，是不能保证决议持久化的。但是我们放在Multi-Paxos的环境中，使用lease机制保证leader有效（leader“有效”的意思是：StartWorking日志已形成多数派，且完成日志“重确认”，参考上一篇《使用Multi-Paxos协议的日志同步与恢复》）的前提下，因为不会有1个以上的成员并发提出议案，同时又因为在N为偶数时，N/2的成员集合与N/2+1的成员集合的交集一定不为空，可以分析出：在leader 有效 的前提下，只要N/2（N为偶数）的成员确认，即可保证数据持久化。因此，在这种情况下，在C(new)形成多数派的日志，宕机重启后，在C(old)中可以被多数派“重确认”，不会丢失。
上线成员，C(new)的多数派成员数大于C(old)，比如ABC变更为ABCD，C(new)的任意多数派集合一定包含了C(old)的某个多数派，变更过程中使用C(new)同步的日志，在C(old)中依然能够保持多数派。
上线成员，C(new)与C(old)多数派成员数相同，比如ABCD变更为ABCDE，某些情况下可能产生C(new)的多数派（如ABE）与C(old)的多数派（如AB）交集只达到C(old)的一半，情况与第2点相同。
最大commit原则
这里的最大commit原则体现在，同步[[C(new)]]的过程中集群宕机，持有[[C(new)]]的成员当选leader，重启后无法确认当前多数派持有的成员组是[[C(new)]]还是[[C(old)]]，需要leader将当前持有的成员组重新投票形成多数派确认后，才能开始leader后续的上任处理。否则可能出现连续变更情况下，成员组分裂选出2个leader的情况，如Raft报出的这个bug，https://groups.google.com/forum/#!topic/raft-dev/t4xj6dJTP6E，修正方法也很简单就是实用最大commit原则，对成员组重新投票得到多数派确认。



阶段成员变更方案总结
成员变更限制每次只能增加或删除一个成员
成员变更由有效的leader发起，确认新的成员组得到多数派确认后，返回成员变更成功
一次成员变更成功前不允许开始下一次成员变更,因此新任leader在开始提供服务前要将自己本地保存的最新成员组重新投票形成多数派确认
leader只要开始同步新成员组后，即可开始使用新的成员组进行日志同步
成员组实用Version标记，持有更大Version的成员不能给持有较小Version的成员投票
成员组变更与日志同步
Log Barrier
对于下线成员的场景，我们需要保证所有日志在剩余在线的机器上能够形成多数派备份，否则可能丢失日志。比如下面的场景，logID为2的日志，在连续成员变更后，仅A上有，无法在A/B/C上形成多数派:



paxos_barrier_log



因此我们要求leader在持久化新的成员组时，要像普通日志一样为它分配logID（称为成员变更日志），它是一个“单向barrier”，即要求所有成员保证logID小于它的日志都持久化本地后，才能持久化成员变更日志，而logID大于它的日志则不受此约束。在上面的例子中,要求B/C保证在持久化 Cnew1之前,一定先保证2号日志持久化。
背景
Paxos算法是Lamport于1990年提出的一种基于消息传递的一致性算法。由于算法难以理解起初并没有引起人们的重视，使Lamport在八年后重新发表到TOCS上。即便如此paxos算法还是没有得到重视，2001年Lamport用可读性比较强的叙述性语言给出算法描述。可见Lamport对paxos算法情有独钟。近几年paxos算法的普遍使用也证明它在分布式一致性算法中的重要地位。06年google的三篇论文初现“云”的端倪，其中的chubby锁服务使用paxos作为chubby cell中的一致性算法，paxos的人气从此一路狂飙。



Paxos是什么
Paxos 算法解决的问题是一个分布式系统如何就某个值（决议）达成一致。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致，是分布式计算中的重要问题。



Paxos的两个原则
安全原则—保证不能做错的事




  1. 只能有一个值被批准，不能出现第二个值把第一个覆盖的情况




  2. 每个节点只能学习到已经被批准的值，不能学习没有被批准的值





存活原则—只要有多数服务器存活并且彼此间可以通信最终都要做到的事




  1. 最终会批准某个被提议的值




  2. 一个值被批准了，其他服务器最终会学习到这个值





Paxos的两个组件
Proposer
提议发起者，处理客户端请求，将客户端的请求发送到集群中，以便决定这个值是否可以被批准。



Acceptor
提议批准者，负责处理接收到的提议，他们的回复就是一次投票。会存储一些状态来决定是否接收一个值



Paxos定义
接下来用举例的方式一步一步解释Paxos为了完成一致性，必须要解决的一些问题。这里为了方便解释，假设每一台服务器都是一个Proposer，也是一个Acceptor



一个Acceptor
首先从最简单的方式开始，假设只有一个Acceptor，让它做决定是否批准一个值



如上图，每一个proposer提议一个值给Acceptor来批准，然后Acceptor批准一个值作为最终的值。



但是这种简单的方式，没有办法解决Acceptor crash的问题，如果唯一的Acceptor crash了，就没有办法知道哪个值被选择了，就需要等待它重启，这一条违反了存活原则，这个时候有4台服务器存活，但已经没有办法工作了。



多个Acceptor
为了解决这个问题，就必须要用到一种多数选择的方法。使用一个Acceptor的集合。然后只有其中的多数批准了一个值，这个值才可以确实是被最终被批准的。为了达到目的也需要一些技巧。



批准第一个达到的值
首先规定每个Acceptor必须批准第一个到达的值。哪个值达到多数批准就是最终批准的值



但是有一个问题，比如上图，因为没有值被多数批准，无法批准一个最终的值出来。这就需要Acceptor批准了一个值之后还要根据某种规则批准不同的值



批准每个提议的值
接下来规定Acceptor批准每个提议的值，但是这也会带来一个问题，可能会批准出多个值



如图，S1发出提议，S1，S2，S3批准 red为最终批准的值。S5随后发出提议，s3，S4，S5批准，blue又为最终批准的值。此时S1，S2最终批准red，S3，S4，S5最终批准blue，这就违背了我们的一致性原则，最终只有一个值被选择。



二段提交原则
要解决这个问题，就要S5在发送自己的提议之前，优先检查有没有已经被批准的值，如果有应该提议已经被批准的值而放弃自己的值，也就是放弃自己的blue改为提议red，这样最终只有一个值被批准就是red。这个就是经典的二段提交原则。



不幸的是，二段提交还是存在另一个问题。



如图，S1在发送提议之前，检查没有值被批准，因此提议red。但同时在所有Acceptor批准之前，S5也要进行提议，这个时候也检查出没有值被批准，所以它也把自己的blue作为提议发送给acceptor。接下来S5的提议优先到达S3，S4，S5，这些Acceptor先批准了blue，达到多数所以blue最终被批准了。但是随后S1，S2，S3接收到了red进行批准。所以又出现了批准出多个值的问题。



提议排序
这个问题要解决，就需要一旦Acceptor批准了某个值，其他有冲突的值都应该被拒绝。也就是说S3随后到达的red应该被拒绝，为了做到这一点。需要对Proposer进行排序，将排序在前的赋予高优先级，Acceptor批准优先级高的值，拒绝排序在后的值。



为了将提议进行排序，可以为每个提议赋予一个唯一的ID，规定这个ID越大，优先级越高



在提议者发送提议之前，就需要生成一个唯一的ID，而且需要比之前使用的或者生成的都要大



提议ID生成算法
在Google的Chubby论文中给出了这样一种方法：假设有n个proposer，每个编号为ir(0<=ir<n)，proposor编号的任何值s都应该大于它已知的最大值，并且满足：s %n = ir => s = m*n + ir



proposer已知的最大值来自两部分：proposer自己对编号自增后的值和接收到acceptor的reject后所得到的值



以3个proposer P1、P2、P3为例，开始m=0,编号分别为0，1，2





  1. P1提交的时候发现了P2已经提交，P2编号为1 > P1的0，因此P1重新计算编号：new P1 = 1*3+0 = 4




  2. P3以编号2提交，发现小于P1的4，因此P3重新编号：new P3 = 1*3+2 = 5





Paxos算法
到此阶段，要保证Paxos的两个原则已经都满足了，Paxos也就顺利的实现了。



二段提交
prepare 阶段：




  1. Proposer 选择一个提案编号 n 并将 prepare 请求发送给 Acceptors 中的一个多数派；




  2. Acceptor 收到 prepare 消息后，如果提案的编号大于它已经回复的所有 prepare 消息，则 Acceptor 将自己上次接受的提案回复给 Proposer，并承诺不再回复小于 n 的提案；





acceptor阶段：




  1. 当一个 Proposer 收到了多数 Acceptors 对 prepare 的回复后，就进入批准阶段。它要向回复 prepare 请求的 Acceptors 发送 accept 请求，包括编号 n 和根据 prepare阶段 决定的 value（如果根据 prepare 没有已经接受的 value，那么它可以自由决定 value）。




  2. 在不违背自己向其他 Proposer 的承诺的前提下，Acceptor 收到 accept 请求后即接受这个请求。





prepare阶段有两个目的，第一检查是否有被批准的值，如果有，就改用批准的值。第二如果之前的提议还没有被批准，则阻塞掉他们以便不让他们和我们发生竞争，当然最终由提议ID的大小决定。


Category spark