分布式一致性协议三部曲-深入理解一致性协议Paxos

2024-03-29 14:20:52

在理解分析分布式一致性协议前，我们必须先看下CAP理论

CAP

CAP是指在一个分布式系统中，一致性（Consistency）、可用性（Availability）、分区容错性（Partition tolerance）这三个要素最多只能同时实现两点，不可能三者兼顾。

Consistency 一致性

一致性指“all nodes see the same data at the same time”，即更新操作成功并返回客户端完成后，所有节点在同一时间的数据完全一致。等同于所有节点拥有数据的最新版本。

Availability 可用性

可用性指“Reads and writes always succeed”，即服务一直可用，而且是正常响应时间。

对于一个可用性的分布式系统，每一个非故障的节点必须对每一个请求作出响应。如果不考虑一致性，这个是很好实现的，立即返回本地节点的数据即可，而不需要等到数据一致才返回。

Partition Tolerance 分区容忍性

Tolerance也可以翻译为容错，分区容忍性具体指“the system continues to operate despite arbitrary message loss or failure of part of the system”，即系统容忍网络出现分区，分区之间网络不可达的情况，分区容忍性和扩展性紧密相关，Partition Tolerance特指在遇到某节点或网络分区故障的时候，仍然能够对外提供满足一致性和可用性的服务。

比如一个服务有3个节点，中国，美国，新加坡，如果数据只有一份，如果数据只在中国，那么美国用户访问数据流程是“美国节点->中国节点->中国数据“来实现的。这时如果美国和中国之间的网络断/高延时了，即出现分区，美国用户就没法访问到该数据。为了解决这个问题，目前都是每个节点都有一份数据备份，即中国，美国，新加坡都有一份数据，这样美国节点和中国节点哪怕临时中断，美国用户还是可以访问美国的数据。但是数据分处不同地区，需要同步，但同步有延时，数据可能不一致。要保障一致，那就必须等写操作在所有节点完成才读，这个时间又是不确定的，又会带来可用性问题，这就是C，A，P不可兼得即CAP理论。

具体工程场景
- 传统数据库都是假设不保证P的，因为传统数据库都是单机或者很小的本地集群，假设网络不存在问题，出现问题手工修复。所以，损失分区容错(P)只保证CA相当于就是一个单体应用，根本不是分布式，其实在分布式出现之前都是这么搭系统，但是倘若这种系统的节点之一挂了，整个系统就直接宕掉了，不符合目前现实需求(高扩展容错)。分布式是要求单个节点故障(概率太高了)系统仍能完成运行。搭建分布式就是间接要求必须保证P，即P是现实，那C和A就无法同时做到，需要在这两者之间做平衡。
- 像银行系统，是通过损失可用性(A)来保障CP，银行系统是内网，很少出现分区不可达故障状态，一旦出现，不可达的节点对应的ATM就没法使用，即变为不可用。同时如果数据在各分区未达到一致，ATM也是Loading状态即不可用。
- 在互联网实践中，可用性又是极其重要的，因此大部分是通过损失一致性(C)来保障AP，当然也非完全牺牲一致性，使用弱一致性，即一定时间后一致的弱一致性，当数据还在同步时(WRITE之后)，使用上一次的数据。

下面我们就来分析讨论今天的重点分布式一致性算法, 在理解Paxos之前我们必须先了解2PC和3PC。

二阶段提交协议（2PC）

协议详情

改进

相比一阶段协议，分两步可以让事务先执行然后再提交，让事务在提交前尽可能地完成所有能完成的工作，这样，最后的提交阶段将是耗时极短，耗时极短意味着操作失败的可能性也就降低。

缺陷

同步阻塞问题

执行过程中，所有参与节点都是事务阻塞型的。当参与者占有公共资源时，其他第三方节点访问公共资源不得不处于阻塞状态。
单点故障

由于协调者的重要性，一旦协调者发生故障，参与者会一直阻塞下去。尤其在第二阶段，协调者发生故障，那么所有的参与者还都处于锁定事务资源的状态中，而无法继续完成事务操。尽管协调者挂掉后可以重新选举一个协调者，但是无法解决因为协调者宕机导致的参与者处于阻塞状态的问题。
数据不一致

在P2A中，当协调者向参与者发送commit请求之后，发生了局部网络异常或者在发送commit请求过程中协调者发生了故障，这会导致只有一部分参与者接受到commit请求。而在这部分参与者接到commit请求之后就会执行commit操作。但是其他部分未接到commit请求的机器则无法执行事务提交，于是整个分布式系统便出现了数据不一致性的现象。

三阶段提交（3PC）

协议详情

改进

三阶段提交针对两阶段提交做了改进：

在第一阶段和第二阶段中插入一个准备阶段，第一阶段canCommit并不执行事务，这样当第一阶段失败或者timeout时，不占用事务资源不需要回滚(提高效率减少事务阻塞)。
引入超时机制。在2PC中，只有协调者拥有超时机制，3PC同时在协调者和参与者中都引入超时机制，主要是避免了参与者在长时间无法与协调者节点通讯（协调者挂掉了）的情况下，无法释放资源的问题，因为参与者自身拥有超时机制会在超时后主动提交释放资源，降低了阻塞时间。由于有第一阶段canCommit的yes才会进入第三阶段，因而该阶段极大概率是commit而不是rollback，因而当协调者挂掉后，默认执行commit是最接近正确的行为。

缺陷

和2CP一样，3CP还是可能会存在不一致性问题，比如，因而适合本地(无网络情况)或者网络非常好的情况。

Paxos

二阶段算法存在一个致命缺点，就是每个阶段协调者需要等到所有参与者的ack, 即只要有一个节点有故障，就会导致无效甚至整个系统出现问题，这个概率还是很高。因而Paxos算法来了，Paxos有个很特别的就是协调者(proposer)只需等到超过1/2(多数派)的节点同意而不是全部节点，这样只有当1/2的节点同时出现故障整个系统才会有问题，加上同时这个限定条件后，这个系统的故障概率是极低极低的。由于只需超过1/2节点同意就执行操作，很明显不是所有节点都保持一致了，因而需要额外的逻辑来保障一致性，这个就是paxos的锁定，即一旦一个值被多数节点同意并提交，该值就被锁定了，剩下的少于1/2节点没法修改该值，并能从其他节点获取到这个设定的值，这个过程也叫learning过程，这个过程的proposer是learner角色。从这个角度我们可以看出参与者也可以是协调者，如果是数据同步过程，这个过程中参与者从协调者角色切换成了学习者。

协议详情

第一阶段A

Proposer选择一个提议编号round_n，向所有的Acceptor广播Prepare（round_n）请求。

第一阶段B

Acceptor接收到Prepare（round_n）请求，若提议编号round_n比之前接收的Prepare请求都要大，则承诺将不会接收提议编号比round_n小的提议，并且带上之前Accept的提议中编号小于n的最大的提议，否则不予理会。

第二阶段A

Proposer得到了多数Acceptor的承诺后，如果没有发现有一个Acceptor接受过一个值，那么向所有的Acceptor发起自己的值和提议编号round_n，即(round_n, my_value)，否则，从所有接受过的值中选择对应的提议编号最大的，作为提议的值，提议编号仍然为round_n,即(round_n, old_accepted_value)。

第二阶段B

Acceptor接收到提议后，如果该提议编号round_n不违反自己做过的承诺，则接受该提议并Ack Proposer。不违背承诺有两个部分。

round_n >= prepare/accepted的round

如果已经有accepted value

proxs的核心

所有节点都是诚实的，即都按照规则行事

一个提议只需被1/2半数以上节点同意(Promise)，Proposer即可进行下一步。
当一个提议被多数派接受(Accepted)后，这个提议对应的值被Chosen（选定），一旦有一个值被Chosen，那么只要按照协议的规则继续交互，后续被Chosen的值都是同一个值，也就是这个Chosen值被锁定，所有节点只能获取到这个值。
所以一个值在Acceptor看来有3种状态：未赋值，Acceptor, Choosen状态

如何确定编号

上面提到的编号round是具体一个人的round, 它不是全局的，全局的就存在同步问题。因而proposer的真正编号是nodeid 【+】 round, 具体的方案有如下几种。

实例推演分析

接下来我们来具体分析各种case，假设总共有5个节点

【1-P1A】 Node1发起proposer, prepare(1), 【1-P1B】然后收到2个Promised{1, {null, null}}, 加上自己总数3>5*1/2
【1-P2A】因而Node1发起Accept{1, value}, 这时又分两种情况
- 【1-P2B】收到2个Node的Accepted{1, value}, 加上自己总数3>5*1/2, 这个value就被Chosen, 后续不管发起多少propose, 该值都会被不会被改变。其实目前只有Node1知道该值被Chosen了，如果客户端访问这个值，Node1是可以直接返回该值的。但是其他节点Node2~Node5并不知道该值有>1/2的节点Accepted, 因而并不认为该值被Chosen, 因而如果有client访问Node2节点该值，Node2是不能立即返回该值的，但Node2可通过发起一次Propose即prepare(2)【2-P1A】, 这时就有几种情况
- - 【2-P1B-1】从其他节点收到过Promised{2, {1, value}}, 然后会接下来会发起【2-P2A】 Accept{2, value}，如果收到超过1/2节点的 Accepted{2, value} 【2-P2B】，表明该值已经被Chosen是确定状态了，然后Node2就可以返回给客户端了，这个过程就是Learn过程(也称重确认)。这个过程发起的Accept动作会让更多节点Accepted(value)，即让更多人知道该值，既是Learn也是传播。
  - 【2-P1B-2】从其他节点未收到过Promised{2, {1, value}} (【1-P2B】中所有Accepted的节点都offline/timeout才会出现这种case), 只收到Promised{2, {null, null}}, 由前面的协议可知，Promised{2, {null, null}}的数量不可能超过1/2s数量，因而这次Propose会失效，Node2会重新发起Propose(3), 重复前面的流程【2-P1A】，这时前面Accepted(1, value)中的任意节点online了，就会进入到【2-P1B-1】分支，然后Node2就Chosen了value, 直接返回给客户端，这个过程也说明一个值被Chosen后，其他节点可能会有短暂的异常非同步状态，但是最终还是会Chosen该值，是收敛的，专业词汇叫活性。
- 【1-P2B-2】收到1个Node(假设Node5)的Accepted{1, value}, 加上自己总数2<5*1/2, 未超过多数，这时尽管该值未被Chosen，但是该值被部分节点Accepted, 在下次propose时被Chosen的概率也是很大的, 因为下次节点(假如Node2)发起新的propose, prepare(2) 【2-P1A】。
- - 【2-P1B-1】只要Node5在线，那么Node2就会收到Node5的Promised(2, {1, value}}, 进而接受Node5已经Accepted的值value, 然后继续发起Accept(2, value), 这一次value被Accepted的节点数就增大了，进而可能过半，进而被Chosen，这个过程充分体现了尽可能达成一致的规则，即尽可能使用上次多数人promised(表决)的结果, 然后尽力广播这个表决结果让更多的节点Accepted(执行)，达到被chosen(确定)的结果。
  - 【2-P1B-2】Node5未在线，且Node2就会收到2个的Promised(2, {null, null}}, 超过多数，因而会发起Accept(2, value2)，然后又有两种情况。
  - 收到超过半数的Accept(2, value2), 那么value2就被chosen确定了。
- 未收到超过半数的Accept(2, value2), 那么说明系统被分为两个小组存在分歧了，一个组支持value, 一组支持value2。如果Node1和Node2交替重试propose, 这个冲突甚至可能会一直持续，这个就是paxos里的死锁现象，即当有多个proposer交错提交时，会导致大量节点不停的提交新的propose覆盖未被Chosen的老propose，进而持续导致没有任何一个propose达到chosen(确定)状态。这个很明显是因为Paxos允许任何参与者都可以是proposer并提出Propose。

Paxos的落地

Multi-Poxis, Raft, Zab(中心化分布式一致性协议)

Paxos相对偏学术，是一种广义抽象，理解和落地相对复杂，同时Accept和Learn阶段存在不同程度的活锁情况, 总的来说主要有如下缺点

由于有多个 Proposer，可能会出现活锁
Paxos只能确定一个值，无法用作数据的连续写同步
提案的最终结果可能只有部分 Acceptor 知晓，不是每个节点都同步到Log被chosen确定这一信息。

因而工程落地上有不同的优化, 具体如下:

活锁优化

因而在工程落地上有了针对具体场景添加约束来尽量降低活锁概率的方案，比如Fast Paxos算法在此基础上作了一些优化，通过选举产生一个leader (领导者)，只有leader才能提交proposer。选择Leader的方法有很多，采用前面标准的Paxos协议也能选出Leader。但是在实际工程中，针对Leader这个可以优化，比如标准的Paxos协议prepare阶段，优先级是按照round值的，由于在迭代的过程中round值会不停变化，会导致promise的返回值不停的变化，不利于收敛。如果我们把优先级规则从round变成节点序号node_id，那么规则就趋向于收敛固定的。比如节点id越小的，优先级越高，那么不论怎么迭代，promise都是优先同意node_id=0的提议，也就是说能更快的进入到Accept阶段。比如Multi-Paxos就是采用Basic-Paxios来选择Leader。当然考虑到Leader选举确定后（chosen后）需要最快速的同步到所有节点，且有更复杂的优先级规范，同时标准paxos协议偏复杂，其他工程实践中很少使用这种优化的标准paxos协议来选取Leader。Leader选举协议有如下Zookeeper的FastLeaderElecetion, Redis的哨兵模式哨兵leader选举和集群模式leader选举, 我将单独列一篇文章来详细描述这些Leader选举协议。

多条数据记录同步优化

从上面的Paxos的介绍可以看出，Paxos只能写入一条记录，一旦被Chosen就不能被修改，当时我们现实情况是经常要连续不断的写入新数据的，Paxos如何解决呢？这个比较好解决，Paxos的一次提交只做一件事我们称为一个paxos实例，比如写一条日志Log1(delete id=1)。如果要写多条日志比如Log2(delete id=2)，那就需新建一个paxos实例，实例和实例之间是完全独立的，具体实现上，每个参与者可建立这样的一个三维数据(instance_id, round, value), 每个instance_id的交互按照poxis协议的规范处理处理round和value值。由于Basic-Paxos并不假设一段时间内只有唯一的proposer，因此可能由集群内的任意server发起redolog同步，因此不能由单一server维护instance_id，而是需要进行分布式协商，为不同的Log分配全局唯一且有序的instance_id(LogId)。同时Accept应答prepare消息和Accept消息前都要持久化本地Log，因而一次Log同步需要3次网络交互加2次写本地磁盘。并且在高并发的情况下，不同Log可能被分配到相同的LogId，这时最差可能会在accept阶段才会失败重试。

Multi-Paxos:在Paxos集群中利用Basic-Paxos协议选举唯一的leader，在leader有效期内所有的议案都只能由leader发起，这里强化了协议的假设：即leader有效期内不会有其他server提出的议案。因此对于Log的同步过程，我们可以简化掉产生LogId阶段和prepare阶段，而是由唯一的leader产生logID，然后直接执行accept，得到多数派确认即表示Log同步成功。事实上，Multi-Paxos协议并不假设全局必须只能有唯一的leader来生成日志，它允许有多个“自认为是leader的server”来并发生成日志，这样的场景即退化为Basic-Paxos。

Learn优化(数据确认)

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

Leader模式"幽灵复现"问题

Mutlti-Paxos下存在Leader切换情况，并且每个记录(Paxos实例)是完全独立的，因而是可能存在非顺序确认的，当然同一个Leader下日志是有顺序的，这个有点像多线程并发执行，同一个线程里的顺序是确定，线程之间的执行顺序谁知道呢？日志非顺序确认，就会出现客户端开始访问不到第7条记录，但是能访问到第20条记录，然后后面7确认后，客户端又能访问到第7条日志了。具体示例如下：

第一轮中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 号日志又像幽灵一样重新出现了。

怎么解决“幽灵复现”问题？新任 Leader 在完成日志重确认，开始写入新的 Log 之前，先写出一条被称为 StartWorking 的日志，这条日志的内容中记录了当前 Leader 的 EpochID（可以使用 Proposalid 的值），并且 Leader 每写一条日志都在日志内容中携带现任 Leader 的 EpochID。回放时，经过了一条 StartWorking 日志之后，再遇到 EpochID 比它小的日志，就直接忽略掉，比如按照上面例子画出的这张图，7 - 19 号日志要在回放时被忽略掉。

Multi-Paxos就是使用上述几个优化的Paxos算法， ZAB和Raft都是衍生自Multi-Paxos，由于Multi-Paxos提出的Leader概念，ZAB和Raft就强化Leader视角，以Leader这个前提和现实需求来设计实现，本质上都是Paxos基础理论来保障一致性的。这三个协议的不同主要体现在下面几点

Leader选举方式不同
- Mutil-Paxos采用Base-Paxos选举
- Raft广播式互相计数方式
- raft是选自己，节点发起投票，大家根据规则选择投与不投，看自己的票数是否成为Leader
raft集成了成员管理，这个比较精妙
Raft, zab能保障日志连续性
raft增加了committed状态，这个在paxos里没有具体说
raft给你的基本是伪代码的描述，方便实现

PBFT(去中心分布式一致性协议)

中心化一致性协议有一个重要的前提是参与者不作恶，因为参与者都是由一个实体管理，参与者都是不会违背协议的规范。而去中心化就不一样，参与者(节点机器)分散在各地，参与者是有可能故意不遵守规范的，比如Paxos中，如果Proposer在没有收到多数派的promise反馈仍发起Accept消息，就会导致该节点有无上权力，可以更新已经被Chosen的数据, 完全违背了规范。那是不是就不存在去中心化一致性协议呢？其实很简单，去中心化的情况下节点作恶会造成影响的原因是参与者没法验证Proposer是否在遵守规则，如果每个节点的回复都加上签名就能解决这个问题。比如每个参与者在回复promise时都通过自己的私钥对promise回复签名，那么一个Proposer如果没有收到多数派的promise"同意"，Proposer就没法拿到多数派的"同意"签名，哪怕它违背规范发起Accept，其他的参与者也会因为它没有多数派的签名而不响应，也就是你可以作恶但是没用。

那在去中心化的分布式系统中，如果Paxos要能容忍f个故障节点和f个作恶节点，多数派要为多少?故障节点收到通信后不会返回结果，作恶节点收到通信后会返回错误的结果。

假设节点总数是n，其中故障节点有f，那么剩下的正确节点为n- f，意味着只要收到n - f个消息就能做出决定，但是这n - f个消息有可能有f个是由作恶节点冒充的，那么正确的消息就是n-f-f个，为了多数一致，正确消息必须占多数，也就是n - f - f > f 但是节点必须是整数个，所以n最少是3f+1个。所以在去中心化场景下，Paxos的多数派为n-1/3f +1, 即收到2/3*n+1个节点的消息即可做出决定，可见这个节点数比中心化时的1/2*n + 1要严格不少。接下来我们规范化中心化paxos和去中心化下poxis的流程来对比下这种的区别。

标准Paxos交互图

Basic-paxos, Proposer在接收到多数派的Accepted消息后知道该值已经被chosen(confirm不可变更), 此时proposer已经可以回复Client, 但是其他节点不知道该值已经被confirm, 仍然不能reply客户端，需要通过一次propose过来来确认值。

带confirm的paxios交互图

上面我们提到过，basic-poxis, 在proposer收到多数派的accepted后，也只有proposer知道该值被chosen(confirm)，其他节点要确定这个值，需要通过一次propose过来来确认值, 因此raft等协议增加一个confirm交互来向其他节点广告该值已经被confirm, 从而避免复杂的Propose交互，也能加快reply, PBFT也是类似的。

PBFT

从上面来看，一次提议需要5次交互，在中心化系统中，节点之间有专线连接，时延一般较低，可能还好。但在分布式系统中，节点之间可能分布在不同的个人设备上，时延往往较大，因而需要减少交互次数。PBFT实现上就是通过广播来减少交互次数的，即Acceptor不仅仅和proposer交互还和其他Acceptor交互。Basic-Paxos下，Accepter接收到的Accept消息是Proposer统计promise消息发出来的，在PBFT下，Acceptor之间互相广播promise消息，因而自己就可以统计自己收集到的promise消息，如果超过多数promise消息就可以直接accept并发出Accepted消息。

优化后的交互图

当然在PBFT里，这些交互过程名称有所变化。propose叫做pre-prepare, promise叫做prepare, accepted叫做commit, 当节点收到2/3*n+1各节点的commit即认为数据被confirm了，可以直接reply。

而区块链TenderMint里的PBFT协议里各个阶段的名字又不一样，propose这个名字是一样的，promise对应prevote, accepted对应precommit, 节点等到2/3*n+1个节点的precommit即认为数据被chosen(confirm), 执行commit将数据写入到区块里。