分布式技术专题带你彻底认识Paxos算法Zab协议和Raft协议的原理和本质 _技术专题

高斋晓开卷，独共圣人语。这篇文章主要讲述分布式技术专题带你彻底认识Paxos算法Zab协议和Raft协议的原理和本质相关的知识，希望能为你提供帮助。
内容简介指南

Paxo算法指南
Zab算法指南
Raft算法指南

Paxo算法指南
Paxos算法的背景Paxos算法的前提Paxos算法的介绍在Paxos算法中，有三种角色：

文章图片

proposer：提案Proposal提出者。
Acceptor：决策者，可以批准议案。
Learner：最终决策的学习者。

文章图片

Paxos算法安全性前提如下：

只有被提出的value才能被选定。
只有一个value被选定。
如果某个进程认为某个value被选定了，那么这个value必须是真的被选定的那个。

Paxos算法的过程描述：prepare阶段

proposer提出一个编号为N的proposal，发送给半数以上的acceptor。
acceptor收到编号为N的prepare请求后:
- 如果小于它已经响应过的请求，则拒绝回复或者回复error；
- 如果N大于该Acceptor已经响应过的所有Prepare请求的编号，那么它就会将它已经接受过（已经经过第二阶段accept的提案）的编号最大的提案（如果有的话，如果还没有的accept提案的话返回{pok，null，null}）作为响应反馈给Proposer，同时存储更新本地对应的提案编号，并且该Acceptor承诺不再接受任何编号小于N的提案。
- 分为两种情况：
  - 如果acceptor已经接受过提案，返回接受提案的最大value；
  - 如果还没有接受过提案，就返回{pok，null，null})

accept阶段

如果proposer收到半数以上的acceptor回复的编号为N的提案的prepare响应，那么会发送一个针对[N,V]提案的Accept请求给半数以上的Acceptor。

如果响应中不包含任何提案，那么V就由Proposer自己决定，可以是任意值。
如果Acceptor收到一个针对编号为N的提案的Accept请求，只要该Acceptor没有对编号大于N的Prepare请求做出过响应，它就接受该提案。
如果N小于Acceptor以及响应的prepare请求，则拒绝，不回应或回复error（当proposer没有收到过半的回应，那么他会重新进入第一阶段，递增提案号，重新提出prepare请求）。

过半的acceptor都接受提案后，learner会自动感知到，并开始学习提案。（同一个进程可以同时扮演多个角色）
Learner的学习过程 learner学习过程包含两种场景：

Learner所在节点参与了提案选举，Learner需要知道其接受(accept)的提案值是否被选中(chosen)。
Learner所在节点已落后于其他节点，Learner需要选择合适的策略快速完成追赶，并重新参与到提案选举当中。

选中通知

本节点Proposer的某个提案被选中(chosen)时，通过(MsgType_PaxosLearner_ProposerSendSuccess)消息通知到各个节点。
正常情况下，所有节点处于online状态，共同参与paxos选举。因此为了避免instance id冲突，paxos建议只由主节点的proposer发起提案，这样保证接受提案和习得提案编号一致。
【分布式技术专题带你彻底认识Paxos算法Zab协议和Raft协议的原理和本质】此时，Learn习得的提案值实际上就是本节点Accept的数据，因此learner只更新内存状态即可，无需再次落盘(acceptor已落盘)。
最后，如果存在follower节点，数据同步到follower(follower节点不参与paxos算法，相当于某个paxos节点的同步备)。

提案值追赶

一旦节点处于落后状态，它无法再参与到paxos提案选举中来。这时需要由learner发起主动学习完成追赶。
Paxos启动时，启动learner定时器，定时发送learn请求到各个节点，发送请求携带本节点的Instance ID、Node ID信息。各节点收到该请求后，回复数据自主完成学习过程。

文章图片

数据各节点保持数据一致性

文章图片

为什么要有两段提交

一方面，第一次预提交后可能被告知已经有观点了，此时他不应该提出自己的观点，而应该尽快收敛，支持最新的观点。
另一方面，进行预加锁。

怎么保证Proposal编号唯一

假设有K台Server运行paxos算法，那么他们初始编号为0…k-1。以后编号每次增加k，从而保证全局唯一递增。
正式提案被半数以上Acceptor接受后，就可以确定最终被接受的提案就是该观点。
两个半数以上的集合的一定存在交集。

Paxos算法有活锁问题存在。介绍了Paxos的算法逻辑，但在算法运行过程中，可能还会存在一种极端情况，当有两个proposer依次提出一系列编号递增的议案，那么会陷入死循环，无法完成第二阶段，也就是无法选定一个提案。如下图：

文章图片

Paxos算法的过半依据

在Paxos算法中，采用了“过半”理念，也就是少数服从多数，这使Paxos算法具有很好的容错性。那么为什么采用过半就可以呢？
Paxos基于的过半数学原理：我们称大多数（过半）进程组成的集合为法定集合，两个法定（过半）集合必然存在非空交集，即至少有一个公共进程，称为法定集合性质。例如A,B,C,D,F进程组成的全集，法定集合Q1包括进程A,B,C，Q2包括进程B,C,D，那么Q1和Q2的交集必然不在空，C就是Q1，Q2的公共进程。如果要说Paxos最根本的原理是什么，那么就是这个简单性质。也就是说：两个过半的集合必然存在交集，也就是肯定是相等的，也就是肯定达成了一致。
Paxos是基于消息传递的具有高度容错性的分布式一致性算法。Paxos算法引入了过半的概念，解决了2PC，3PC的太过保守的缺点，且使算法具有了很好的容错性，另外Paxos算法支持分布式节点角色之间的轮换，这极大避免了分布式单点的出现，因此Paxos算法既解决了无限等待问题，也解决了脑裂问题，是目前来说最优秀的分布式一致性算法。其中，Zookeeper的ZAB算法和Raft一致性算法都是基于Paxos的。在后边的文章中，我会逐步介绍优秀的分布式协调服务框架，也是极优秀的工业一致性算法的实现Zookeeper使用和实现。

ZAB算法指南

fast leader election：快速选举阶段
recovery：恢复阶段
- Discovery；
- Synchrozation
broadcasting：广播阶段

先了解一些基本概念

electionEpoch：每执行一次leader选举，electionEpoch就会自增，用来标记leader选举的轮次
peerEpoch：每次leader选举完成之后，都会选举出一个新的peerEpoch，用来标记事务请求所属的轮次
zxid：事务请求的唯一标记，由leader服务器负责进行分配高32位是上述的peerEpoch，低32位是请求的计数，从0开始。
lastprocessZxid：最后一次commit的事务请求的zxid
LinkedList< Proposal> committedLog、long maxCommittedLog、long minCommittedLog：ZooKeeper会保存最近一段时间内执行的事务请求议案，个数限制默认为500个议案。committedLog就是用来保存议案的列表，maxCommittedLog表示最大议案的zxid，minCommittedLog表示committedLog中最小议案的zxid。
ConcurrentMap< Long, Proposal> outstandingProposals：Leader拥有的属性，每当提出一个议案，都会将该议案存放至outstandingProposals，一旦议案被过半认同了，就要提交该议案，则从outstandingProposals中删除该议案。
ConcurrentLinkedQueue< Proposal> toBeApplied：Leader拥有的属性，每当准备提交一个议案，就会将该议案存放至该列表中，一旦议案应用到ZooKeeper的内存树中了，然后就可以将该议案从toBeApplied中删除。
state：当前服务器的状态
recvQueue：消息接收队列，用于存放那些从其他服务器接收到的消息。
queueSendMap：消息发送队列，用于保存那些待发送的消息，按照SID进行分组。
senderWorkerMap：发送器集合，每个SenderWorker消息发送器，都对应一台远程Zookeeper服务器，负责消息的发送，也按照SID进行分组。
lastMessageSent：最近发送过的消息，为每个SID保留最近发送过的一个消息。

在ZAB协议中，服务的的状态state有四种：

LOOKING：进入leader选举状态
FOLLOWING：leader选举结束，进入follower状态
LEADING：leader选举结束，进入leader状态
OBSERVING：处于观察者状态

协议算法的具体描述 Broadcasting过程

leader针对客户端的事务请求，创造出一个提案，zxid由leader决定，并将该提案的zxid，提案放到outstandingProposals Map中。
leader向所有的follower发送该提案，如果过半的follower回复OK的话，则leader认为可以提交该议案，则将该议案从outstandingProposals中删除。
然后存放到toBeApplied中leader对该议案进行提交，会向所有的follower发送提交该议案的命令，leader自己也开始执行提交过程，会将该请求的内容应用到ZooKeeper的内存树中。
然后更新lastProcessedZxid为该请求的zxid，同时将该请求的议案存放到上述committedLog，同时更新maxCommittedLog和minCommittedLog。
leader回复客户端，并将提案中ToBeApplied中删除

fast leader election过程

HashMap< Long, Vote> recvset：用于收集LOOKING、FOLLOWING、LEADING状态下的server的投票
HashMap< Long, Vote> outofelection：用于收集FOLLOWING、LEADING状态下的server的投票（说明leader选举已经完成）

具体的过程有：

服务器先自增electionEpoch，给自己投票：

从快照日志和事务日志中加载数据，得到本机器的内存树数据，以及lastProcessedZxid。投票内容为：
- proposedLeader：server自身的myid值，初始为本机器的id
- proposedZxid：最大事务zxid，初始为本机器的lastProcessedZxid
- proposedEpoch:peerEpoch值，由上述的lastProcessedZxid的高32得到
- 然后向所有的服务器发送投票。

server接收到投票通知后，进行PK。
- 如果收到的通知中的electionEpoch比自己的大，则更新自己的electionEpoch为serverA的electionEpoch；
- 如果、收到的通知中的electionEpoch比自己的小，则向serverA发送一个通知，将自己的投票以及electionEpoch发送给serverA，serverA收到后就会更新自己的electionEpoch。
- 如果electionEpoch相同，PK的规则是proposedZxid，然后再是myId。
根据server的状态来判定leader
- 如果当前发来的投票的server的状态是LOOKING状态，则只需要判断本机器的投票是否在recvset中过半了，如果过半了则说明leader选举就算成功了，如果当前server的id等于上述过半投票的proposedLeader,则说明自己将成为了leader，否则自己将成为了follower。
- 如果当前发来的投票的server的状态是FOLLOWING、LEADING状态，则说明leader选举过程已经完成了，则发过来的投票就是leader的信息，这里就需要判断发过来的投票是否在recvset或者outofelection中过半了，同时还要检查leader是否给自己发送过投票信息，从投票信息中确认该leader是不是LEADING状态。

Recovery过程

通信初始化

重新为peerEpoch选举出一个新的peerEpoch
- follower会向leader发送一个Leader，FOLLOWERINFO信息，包含自己的peerEpoch信息。
- leader的LearnerHandler会获取到上述peerEpoch信息，从中选出一个最大的peerEpoch，然后加1作为新的peerEpoch。
- 然后leader的所有LearnerHandler会向各自的follower发送一个Leader.LEADERINFO信息，包含上述新的peerEpoch；
- follower会使用上述peerEpoch来更新自己的peerEpoch，同时将自己的lastProcessedZxid发给leader，leader的根据这个lastProcessedZxid和leader的lastProcessedZxid之间的差异进行同步。
已经处理的事务议案的同步
- 判断LearnerHandler中的lastProcessedZxid是否在minCommittedLog和maxCommittedLog之间
- LearnerHandler中的lastProcessedZxid和leader的lastProcessedZxid一致，则说明已经保持同步了
- 如果lastProcessedZxid在minCommittedLog和maxCommittedLog之间，从lastProcessedZxid开始到maxCommittedLog结束的这部分议案，重新发送给该LearnerHandler对应的follower，同时发送对应议案的commit命令。

如果lastProcessedZxid大于maxCommittedLog，则删除该follower大于部分的事务日志
如果lastProcessedZxid小于minCommittedLog，则直接采用快照的方式来恢复。

未处理的事务议案的同步
- LearnerHandler还会从leader的toBeApplied数据中将大于该LearnerHandler中的lastProcessedZxid的议案进行发送和提交（toBeApplied是已经被确认为提交的）
- LearnerHandler还会从leader的outstandingProposals中大于该LearnerHandler中的lastProcessedZxid的议案进行发送，但是不提交（outstandingProposals是还没被被确认为提交的）
将LearnerHandler加入到正式follower列表中
LearnerHandler发送Leader.NEWLEADER以及Leader.UPTODATE命令。
- leader开始进入心跳检测过程，不断向follower发送心跳命令，不断检是否有过半机器进行了心跳回复，如果没有过半，则执行关闭操作，开始进入leader选举状态；
- LearnerHandler向对应的follower发送Leader.UPTODATE，follower接收到之后，开始和leader进入Broadcast处理过程。

事务持久化和恢复过程

事务持久化分为：broadcasting持久化和leader shutdown过程的持久化。
- leader针对每次事务请求都会生成一个议案，然后向所有的follower发送该议案。follower收到提案后，将该议案记录到事务日志中，每当记满100000个（默认），则事务日志执行flush操作，同时开启一个新的文件来记录事务日志
- 同时会执行内存树的快照，snapshot.[lastProcessedZxid]作为文件名创建一个新文件，快照内容保存到该文件中
- 一旦leader过半的心跳检测失败，则执行shutdown方法，在该shutdown中会对事务日志进行flush操作

事务的恢复分为快照恢复和日志恢复。

事务快照的恢复：会在事务快照文件目录下找到最近的100个快照文件，并排序，最新的在前；对上述快照文件依次进行恢复和验证，一旦验证成功则退出，否则利用下一个快照文件进行恢复。恢复完成更新最新的lastProcessedZxid；
事务日志的恢复：从事务日志文件目录下找到zxid大于等于上述lastProcessedZxid的事务日志，然后对上述事务日志进行遍历，应用到ZooKeeper的内存树中，同时更新lastProcessedZxid，同时将上述事务日志存储到committedLog中，并更新maxCommittedLog、minCommittedLog

Raft算法指南
Raft背景

由于Paxos算法过于复杂、实现困难，极大地制约了其应用，而分布式系统领域又亟需一种高效而易于实现的分布式一致性算法，在此背景下，Raft 算法应运而生。
Raft是一个共识算法（consensus algorithm），所谓共识，就是多个节点对某个事情达成一致的看法，即使是在部分节点故障、网络延时、网络分割的情况下。
共识算法的实现一般是基于复制状态机（Replicated state machines），何为复制状态机：简单来说：相同的初识状态 + 相同的输入 = 相同的结束状态。

Raft 角色

leader：负责日志的同步管理，处理来自客户端的请求，与Follower保持heartBeat的联系；
follower：响应 Leader 的日志同步请求，响应Candidate的邀票请求，以及把客户端请求到Follower的事务转发（重定向）给Leader；
candidate：负责选举投票，集群刚启动或者Leader宕机时，状态为Follower的节点将转为Candidate并发起选举，选举胜出（获得超过半数节点的投票）后，从Candidate转为Leader状态。

Raft的3个子问题为简化逻辑和实现，Raft 将一致性问题分解成了三个相对独立的子问题。

选举（Leader Election）：当 Leader 宕机或者集群初创时，一个新的 Leader 需要被选举出来；
日志复制（Log Replication）：Leader 接收来自客户端的请求并将其以日志条目的形式复制到集群中的其它节点，并且强制要求其它节点的日志和自己保持一致；
安全性（Safety）：如果有任何的服务器节点已经应用了一个确定的日志条目到它的状态机中，那么其它服务器节点不能在同一个日志索引位置应用一个不同的指令。

选举过程第一阶段：所有节点都是 Follower。

文章图片

第二阶段：Follower 转为 Candidate 并发起投票。投票过程有：

增加节点本地的current term ，切换到candidate状态
投自己一票，并行给其他节点发送 RequestVote RPCs
等待其他节点的回复，可能出现三种结果：
- 收到majority的投票（含自己的一票），则赢得选举，成为leader
- 被告知别人已当选，那么自行切换到follower
- 一段时间内没有收到majority投票，则保持candidate状态，重新发出选举

第三阶段：投票策略投票的约束条件有：

在一个term内，一个节点只允许发出一次投票；
候选人知道的信息不能比自己的少（这一部分，后面介绍log replication和safety的时候会详细介绍）
first-come-first-served 先来先得
如果参加选举的节点是偶数个，raft通过randomized election timeouts来尽量避免平票情况，也要求节点的数目都是奇数个，尽量保证majority的出现。

log Replication原理

当leader选举成功后，客户端所有的请求都交给了leader，leader调度请求的顺序性和followers的状态一致性。
在集群中，所有的节点都可能变为leader，为了保证后续leader节点变化后依然能够使集群对外保持一致，需要通过Log Replication机制来解决如下两个问题：
Follower与Leader节点相同的顺序依次执行每个成功提案;
每个成功提交的提案必须有足够多的成功副本，来保证后续的访问一致

第一阶段：客户端请求提交到 Leader。Leader 在收到client请求提案后，会将它作为日志条目（Entry）写入本地log中。需要注意的是，此时该 Entry 的状态是未提交（Uncommitted），Leader 并不会更新本地数据，因此它是不可读的。
第二阶段：Leader 将 Entry 发送到其它 Follower

Leader 与 Floolwers 之间保持着心跳联系，随心跳 Leader 将追加的 Entry（AppendEntries）并行地发送给其它的 Follower，并让它们复制这条日志条目，这一过程称为复制（Replicate）。
为什么 Leader 向 Follower 发送的 Entry 是 AppendEntries，因为 Leader 与 Follower 的心跳是周期性的，而一个周期间 Leader 可能接收到多条客户端的请求，因此，随心跳向 Followers 发送的大概率是多个 Entry，即 AppendEntries。
Leader 向 Followers 发送的不仅仅是追加的 Entry（AppendEntries）在发送追加日志条目的时候，Leader 会把新的日志条目紧接着之前条目的索引位置（prevLogIndex）， Leader 任期号（Term）也包含在其中。如果 Follower 在它的日志中找不到包含相同索引位置和任期号的条目，那么它就会拒绝接收新的日志条目，因为出现这种情况说明 Follower 和 Leader 不一致。
如何解决 Leader 与 Follower 不一致的问题，正常情况下，Leader 和 Follower 的日志保持一致。然而，Leader 和 Follower 一系列崩溃的情况会使它们的日志处于不一致状态。

有三种情况：

Follower落后新的leader，丢失一些在新的 Leader 中有的日志条目
Follower领先新的leader，有一些 Leader 没有的日志条目，
或者两者都发生。丢失或者多出日志条目可能会持续多个任期。

第三阶段：Leader 等待 Followers 回应。Followers 接收到 Leader 发来的复制请求后，有两种可能的回应：

写入本地日志中，返回 Success；
一致性检查失败，拒绝写入，返回 False，原因和解决办法上面已做了详细说明。
当 Leader 收到大多数 Followers 的回应后，会将第一阶段写入的 Entry 标记为提交状态（Committed），并把这条日志条目应用到它的状态机中。

第四阶段：Leader 回应客户端。完成前三个阶段后，Leader会向客户端回应 OK，表示写操作成功。
第五阶段，Leader 通知 Followers Entry 已提交Leader 回应客户端后，将随着下一个心跳通知 Followers，Followers 收到通知后也会将 Entry 标记为提交状态。至此，Raft 集群超过半数节点已经达到一致状态，可以确保强一致性。
raft safety保证1） election safety: 在一个term内，至多有一个leader被选举出来。raft算法通过
一个节点某一任期内最多只能投一票；
只有获得majority投票的节点才会成为leader。
2）log matching：说如果两个节点上的某个log entry的log index相同且term相同，那么在该index之前的所有log entry应该都是相同的。leader在某一term的任一位置只会创建一个log entry，且log entry是append-only。
3）consistency check。leader在AppendEntries中包含最新log entry之前的一个log 的term和index，如果follower在对应的term index找不到日志，那么就会告知leader不一致。当出现了leader与follower不一致的情况，leader强制follower复制自己的log。
3）leader completeness ：如果一个log entry在某个任期被提交（committed），那么这条日志一定会出现在所有更高term的leader的日志里面。
一个日志被复制到majority节点才算committed
一个节点得到majority的投票才能成为leader，而节点A给节点B投票的其中一个前提是，B的日志不能比A的日志旧。
4）stale leader: 落后的leader，但在网络分割（network partition）的情况下，可能会出现两个leader，但两个leader所处的任期是不同的。而在raft的一些实现或者raft-like协议中，leader如果收不到majority节点的消息，那么可以自己step down，自行转换到follower状态。
5）leader crash：新的节点成为Leader，为了不让数据丢失，希望新Leader包含所有已经Commit的Entry。为了避免数据从Follower到Leader的反向流动带来的复杂性，Raft限制新Leader一定是当前Log最新的节点，即其拥有最多最大term的Log Entry。
6）State Machine Safety
某个leader选举成功之后，不会直接提交前任leader时期的日志，而是通过提交当前任期的日志的时候“顺手”把之前的日志也提交了，具体的实现是：如果leader被选举后没有收到客户端的请求呢，论文中有提到，在任期开始的时候发立即尝试复制、提交一条空的log。
总结：raft将共识问题分解成两个相对独立的问题，leader election，log replication。流程是先选举出leader，然后leader负责复制、提交log（log中包含command）
log replication约束：一个log被复制到大多数节点，就是committed，保证不会回滚
leader一定包含最新的committed log，因此leader只会追加日志，不会删除覆盖日志
不同节点，某个位置上日志相同，那么这个位置之前的所有日志一定是相同的
Raft never commits log entries from previous terms by counting replicas.