《》RaftRaft将问题分解和具体化统一处理

　　《》RaftRaft将问题分解和具体化统一处理

　　木筏

　　Raft 将问题分解具体化：Leader 统一处理变更操作请求，执行一致性协议保证节点间日志复制的一致性，使用term 作为逻辑时钟保证时序。节点运行相同的状态机并获得一致的结果。 Raft协议的具体流程如下：

　　

　　Client发起一个请求，每个请求收录一个由Leader处理的操作指令请求。 Leader将操作指令（entry）追加到操作日志中，然后向Follower发起AppendEntries请求，尝试获取操作日志的副本登陆Follower，如果follower多数（quorum）同意AppendEntries请求，leader执行commit操作，将指令传递给状态机处理，状态机处理完后将结果返回给客户端。

　　1 个leader选举

　　1.1 一开始，所有服务器都以follower状态启动

　　然后等待leader或候选者的RPC请求，否则超时。

　　以上三种情况处理如下：

　　1.2 候选人采集选票的过程

　　候选人将为此状态设置随机超时。一旦出现在本届任期内，大家都没有获得过半数的选票，即分裂选票。如果超时时间短，则更容易获得过半票。

　　Candidate 会向所有服务器发送 RequestVote RPC 请求，请求参数如下图所示

　　

　　votedFor 是服务器保存的投票对象。一个服务器在一个任期内只能投票一次。如果此时已经投过票，即votedFor不为空，那么此时可以直接拒绝本次投票（当然要检查votedFor是否是被请求的候选人）。

　　如果你还没有投票：比较候选人的日志和当前更新的服务器的日志，比较方法是哪个lastLog项越大越新。如果词条相同，则lastLog索引较大且较新的为比较方法。

　　候选人统计投票信息。如果超过一半的候选人同意，他们被认为是领导者并改变为领导者状态。如果没有超过一半，则等待新的领导者产生。如果是这样，则更改为跟随者状态。然后，如果超时，则开始下一次选举。

　　2 日志副本

　　2.1 所有请求都交给leader

　　一旦leader选举成功，所有客户端请求最终都会交给leader（如果客户端连接了follower，follower会转发给leader）

　　2.2 处理请求流程

　　2.2.1 客户端请求到达leader

　　leader首先将请求转换为一个条目，然后将其添加到其日志中以获取该条目的索引信息。该条目收录当前leader的任期信息和日志中的索引信息

　　2.2.2 leader 将以上条目复制给所有关注者

　　看官方的AppendEntries RPC请求

　　

　　

　　从上图可以看出，对于每个follower，leader维护了两个属性，一个是nextIndex，是leader发送给follower的下一个entry的索引，另一个是matchIndex，就是follower发送给leader的确认索引。

　　一开始会初始化一个leader：

　　nextIndex=领导者日志的最大索引+1

　　匹配索引=0

　　然后开始准备AppendEntries RPC请求的参数

　　prevLogIndex=nextIndex-1

　　prevLogTerm=从日志中获取上述prevLogIndex对应的term

　　然后准备entries数组信息

　　从leader的日志的prevLogIndex+1开始到lastLog，此时为空

　　然后将leader的commitIndex作为参数传给

　　leaderCommit=commitIndex

　　至此，所有参数准备就绪，向所有follower发送RPC请求，follower收到请求后，处理如下：

　　如果词条回复错误

　　如果日志不收录 prevLogIndex 的条目，则回复 false

　　匹配 prevLogTerm

　　这里可能不一致，因为初始的prevLogIndex和prevLogTerm是leader上日志的lastLog。如果不一致，则返回false，并将follower上日志的lastIndex发送给leader。

　　上面的macthIndex=lastIndex

　　nextIndex=lastIndex+1 以上

　　然后leader会按照上面的规则从头开始发送新的prevLogIndex、prevLogTerm、entries数组

　　2.2.3 leader 占复制条目的一半以上

　　一旦leader发现某些条目已经被超过一半的follower复制了，它就会提交条目并将commitIndex提升到条目的索引。 （这个是按照入口index的顺序提交的），具体实现可以通过follower发送给macthIndex来判断是否超过一半。

　　一旦可以提交，leader就会将该entry应用到状态机，然后向客户端回复OK

　　然后在下一次heartBeat心跳中，commitIndex被传递给所有follower，对应follower就可以将commitIndex和之前的entry应用到各自的状态机中。

　　3 安全

　　3.1 选举约束

　　重点强调了上述*敏*感*词*选举。

　　The elected leader must contain all entries that have already been submitted

　　比如leader提交了一半以上replication的entry，但是一些follower可能没有这些entry。 When the leader dies, if the follower is elected as the leader, the above entries may be overwritten, resulting in The problem of inconsistency, so the newly elected leader must meet the above constraints

　　目前，上述约束的简单实现是：

　　只要当前服务器的日志比服务器日志的一半新，这里的新鲜度就是我上面说的：

　　lastLog 的项越大，越新越新。如果term相同，则lastLog的索引越大越新。

　　但正是这种实现并没有完全实现约束，这会导致下面的另一个问题。一个详细的案例稍后会解释这个问题

　　3.2 当前任期的leader是否可以直接提交上一任期的条目

　　raft给出的答案是：

　　本期的leader不能“直接”提交上一期的参赛作品

　　即可以间接提交。来看看Raft给出的不能直接提交的情况

　　

　　最上面一行数字表示索引，s1-s5表示服务器服务器，a-e表示不同场景，框内数字表示术语

　　详细解释如下：

　　这里是日志覆盖问题的详细解释

　　日志覆盖包括2种情况：

　　我们从这个案例中得到的一个新约束是：

　　本期的leader不能“直接”提交上一期的参赛作品

　　必须等到本学期有一半以上的条目后，才能一起提交上一学期的条目

　　所以 raft 依靠这两个约束来进一步保证一致性。

　　让我们仔细分析一下这个案例。问题在于上面的leader选举。如果 s1 在 c 场景中提交了索引为 2、term=2 的条目，则 s5 不收录所有 commitLog。可以，但是s5还是可以按照最新的日志对比方式选举leader的，也就是说，最新的日志对比方式并不能保证3.1中的选举约束。

　　The elected leader must contain all entries that have already been submitted

　　所以可以理解为：正是因为上面提到的选举约束的执行存在缺陷，才增加了这样一个不能直接提交给上届参赛作品的约束。

　　3.3 安全演示

　　Leader Completeness：如果提交了一个条目，该条目必须存在于后续的Leader中。

　　经过以上两个约束，可以得出Leader Completeness的结论。

　　由于上述“不能直接提交上一学期的条目”的限制，任何条目的提交都必须存在于当前任期的条目下。此时，超过一半的所有服务器都收录当前术语（也是当前最大术语）的条目。假设serverA以后会成为leader，serverA的lastlog的term不能大于当前的term。成为leader，即其日志与其他服务器pk是最新的，必须满足大于他们的日志的索引，所以必须收录提交的条目。

　　4 其他注意事项

　　4.1 客户端

　　从客户的角度来看：

　　如果客户端发送请求，leader返回ok响应，则客户端认为请求执行成功，则请求需要真正落地，不能丢失。

　　如果leader没有返回ok，那么客户端可以认为请求没有执行成功，可以通过重试继续请求。

　　对于领导者来说：

　　一旦客户端回复OK然后挂断，必须保证这个请求对应的entry被应用到状态机上，也就是需要另一个leader来继续应用到状态机上。

　　一旦leader在回复客户端之前挂了，这个请求对应的entry就不能应用到状态机上。如果应用于状态机，客户端认为执行失败，但服务器缺乏持久性。这个请求的结果有点不一致。

　　这个原理也和消息队列是一致的。先说消息队列的消息丢失（很多人还没有真正理解这个问题）：客户端向服务器发送消息，服务器回复OK，然后由于内部机制导致消息丢失服务器。 ，这种情况称为消息队列的消息丢失。如果服务器没有给你回复OK，那么这种情况不属于消息队列丢失消息的范畴。

　　让我们看看 raft 能否再次满足这个原则：

　　leader已经复制了一个条目的一半以上，认为可以提交，所以应用到状态机，然后向客户端响应OK。 leader挂掉后，可以保证该entry存在于后续leader中

　　leader被复制了一半以上的条目，然后就挂了，也就是没有给客户端回复OK。在raft机制下，后续leader可能会收录入口并提交，也可能直接覆盖。入口。如果是前者，将entry应用到状态机，那么这时候就有问题了：客户端没有收到OK回复，但是服务端可以保存成功

　　为了掩盖这种情况，需要在client端做一个trick，就是client会重试所有没有回复OK的，并且client的请求会携带一个唯一的request id，即重试时也是如此。使用之前的请求 ID 重试

　　服务器发现提交日志中已经存在请求id，然后直接响应OK。如果没有，则再次执行请求。

　　4.2 关注者挂断

　　关注者已关闭。只要leader还满足一半以上的条件，就一切正常。挂断并恢复后，leader会继续重试，follower依然可以恢复正常

　　Follower 在接收 AppendEntries RPC 时是幂等操作

　　扎布

　　Zab 代表 Zookeeper 原子广播协议，是 Zookeeper 内部使用的共识协议。与Paxos相比，Zab最大的特点就是保证了强一致性（强一致性，或线性化一致性）。

　　与 Raft 一样，Zab 需要唯一的领导者参与决策。 Zab 可以分为三个阶段：发现、同步和广播：

　　

　　Leader 和 Follower 通过心跳判断健康状态。正常情况下，Zab 处于转播阶段。当出现Leader宕机、网络隔离等异常情况时，Zab会回到发现阶段。

　　Zab 通过约束交易的顺序来实现强一致性。第一个广播事务被提交，先入先出。 Zab 称其为一级订单（以下简称 PO）。实现PO的核心是zxid。

　　Each transaction in Zab corresponds to a zxid, which is composed of two parts: e is the epoch generated when the leader is elected, and c is the number of the transaction in the current epoch, increasing in sequence.假设两笔交易的zxid分别为z和z’，当z.e

　　为了实现PO，Zab对Follower和Leader有如下约束：

　　有交易 z 和 z'。如果Leader先广播z，Follower需要保证commit z对应的事务先有事务z和z'，z由Leader p广播，z'由Leader q广播，Leader p在Leader q之前，然后Follower需要保证commit z对应的事务先有事务z和z'，z由Leader p广播，z'由Leader q广播，Leader p在Leader q之前，如果Follower已经提交z，那么q需要确保你已经提交 z 来广播 z'

　　1、2点保证事务FIFO，第三点保证所有提交的事务在Leader上可用。

　　与Paxos相比，Zab限制了事务的顺序，适用于一致性要求强的场景。

　　Zab 协议源码实现

　　

　　1.1 重要数据介绍

　　加上上一节已经介绍过的名词

　　对于以上参数，整个Broadcast过程可以描述为：

　　1.2 快速*敏*感*词*选举

　　leader选举过程中需要注意的要点：

　　投票过程中有3个重要数据：

　　以下是这个过程的详细说明：

　　serverA 然后向所有其他服务器发送通知，通知内容为上述投票信息和选举纪元信息

　　pk完成后，如果本机被pk投票否决，投票信息会更新为对方的投票信息，同时投票信息会重新发送给所有服务器。

　　如果本机没有被pk投票否决，请看下面的一半判断过程

　　因为目前leader和follower都在测试是否进入leader选举过程。如果leader检测不到服务器ping回复的一半，leader会进入LOOKING状态，但是follower有自己的检测，需要一定的时间才能感知到这个事件。在此期间，如果其他服务器加入集群，则可能会收到。超过一半的其他追随者投票给了前任领导者，但此时领导者不再处于 LEADING 状态，因此需要进行这样的检查以排除这种情况。

　　1.3 恢复阶段

　　一旦leader选举完成，就会进入recovery阶段，即follower需要同步leader上的数据信息

　　LearnerHandler 中的 lastProcessedZxid 与 leader 的 lastProcessedZxid 相同，表示已经同步。

　　如果 lastProcessedZxid 在 minCommittedLog 和 maxCommittedLog 之间

　　proposal从lastProcessedZxid开始到maxCommittedLog结尾的部分会重发给LearnerHandler对应的follower，同时会发送proposal对应的commit命令

　　上面可能有问题：虽然lastProcessedZxid在它们之间，但是没有找到lastProcessedZxid对应的motion，也就是这个zxid​​在leader中是没有的。这个时候的策略是完全按照leader同步，删除follower。部分交易日志，然后重新发送这部分提案，并提交这些提案

　　如果 lastProcessedZxid 大于 maxCommittedLog

　　然后删除follower大于一部分的事务日志

　　如果 lastProcessedZxid 小于 minCommittedLog

　　然后直接用快照的方法恢复

　　2 特殊情况下的注意事项

　　让我们再谈谈恢复：

　　由此可以看出，在初始化和恢复时，所有最新的事务日志都会作为提交事务处理

　　也就是说，可能有一些事务日志还没有提交，都被当作提交了。这个过程简单粗暴，而raft对旧数据的恢复控制更严格。

　　2.2关注者的恢复过程挂断重启

　　一旦leader死亡，上述2组leader

　　无效。当leader恢复时它们不起作用，但是当系统正常执行并且follower被暂停和恢复时。

　　我们可以看到，在上面2.3的恢复过程中，会先恢复快照日志和事务日志，然后补充leader的上面2条数据的内容。

　　2.3 关注者同步失败

　　目前，leader和follower的同步是通过BIO来实现的。一旦链接异常，将关闭链接，重新建立与leader的连接，并重新同步最新数据

　　2.4 客户端也一样吗？

　　如果客户端收到OK回复，会丢失数据吗？

　　如果客户端没有收到OK回复，它会存储更多数据吗？

　　如果客户端收到OK回复，说明已经复制过半，请求对应的事务日志肯定会被收录在leader选举中，不会丢失数据

　　客户端连接的leader或follower挂断，客户端没有收到OK响应。目前可能会丢失也可能不会丢失，因为服务器端的处理也非常简单粗暴，未来leader上的事务日志会被当作commit来处理。所有处理过的都将应用到内存树中。