vlambda博客
学习文章列表

不知道大家有没有听过拜占庭将军问题？

中世纪的拜占庭有10只军队，每只军队有一个将军，因该国地域辽阔，10只军队分布在不同的战线，同时该国还是个军事民主制国家，各将军地位平等，没有中心指挥，战斗中军队按照将军指令进攻或撤回，10名将军依靠手下信使与其他将军保持通信，信使经过严格审查和训练，保证信息传递无误。

恰逢敌国大军压境，需要至少6只拜占庭军队同时进攻，才有机会灭掉敌国。现在将军们面临的问题是，若出现叛徒，可能会传递迷惑或错误消息，信使如果半路被暗杀，信息则无法传递，在这种状态下，如何让10只军队找到一种分布式协作的方式，让将军们通过远程准确无误的协作，从而取得战斗胜利？

拜占庭将军问题是分布式系统中点对点通信中可能会产生的状态同步及容错问题，是分布式领域最复杂最严格的容错模型，该问题最早由莱斯利·兰伯特提出。在实际分布式系统中情况没有那么复杂，通常节点不一致的原因是节点故障或是网络超时，这两种情况下，容错模型的主要功能是保持集群的一致性。

看到这里，相信大家已经知道这一期要讲什么内容了！没错，这一期还是熟悉的区块链技术～

上期区块链序言提到，区块链是在对等网络下通过透明可信规则，构造的一种不可伪造不可篡改可追溯的数据结构，用来管理和实现事务，区块链系统是分布式的集群，分布式集群模式必定会面临一个问题，那就是如何保证集群稳定和一致的目标。

关于这个问题，提出过许多的解决方案，首先被证明的是该问题提出者莱斯利·兰伯特提出的paxos容错算法，但是由于该算法复杂晦涩，难以具体实现（因paxos难以具体实现，zookeeper参考paxos实现了自己的zab算法🐂🍺），直到斯坦福大学的教授于2014年发布Raft协议，后由国内大佬实现具体算法，并被Hyperledger Fabric采用。Raft是分布式环境下的一致性算法，Raft非常类似paxos，但是比paxos好理解易实现。

本文将会介绍Raft算法原理，为方便大家理解，多以图和小故事为主 ，不涉及过多算法推理和实现细节（手动@小马哥）。

继续以拜占庭虚空战争为例。以下故事纯属虚构，如有雷同，实属故意 巧合。

拜占庭军队其中一位天选将军因神赐机缘，穿越到了2014年的斯坦福大学，有幸认识了提出Raft的教授，学习到了原来可以用Raft算法解决将军间信息同步问题。当他回到拜占庭后，他向其他将军提出建议，我们互相信任、没有叛徒，但是如果意见不一致，则兵败如山倒，不如通过选举方式解决一致性问题，选举制度如下：

1、选举一位大将军统一发号施行，其他将军都听令于他，大将军信使送达命令后，诸位将军必须回复收到，假设笔者荣幸首次当选，则笔者在任期间作为一个任期并标记为1；

2、若一段时间内未收到大将军发送的号令，此时将军需判断目前军队为大将军空位期；

3、空位期判断完成后的将军需推举自己为大将军，此时为选举期，将军身份变成候选大将军，选举期时派发信使向除自己外的其他将军发送自荐信函；

4、收到推荐信函的将军，需要把选票投给先来提交推荐函的A号候选大将军信使，把选票已投的消息告诉后到的B号候选大将军推荐函使者，让信使把消息传递回去，候选大将军收到选票数（包括自己）大于将军总数的半数以上，则当选为新任大将军，此时任期为2；

5、如果有两位将军同时竞选，收到票数相同或都小于将军总数的一半，则选举期倒计时结束后，候选大将军回归空位期，重复步骤2；

6、如果候选将军在选举期内收到大将军发布指令，则退出选举期；

7、如果任意两个或以上的将军每次判断空位期或选举期相同，会陷入步骤5的死循环，所以为了保证不会出现这种情况，每位将军判断空位期的方式需各不相同，比如可以由军队所处地理位置计算时间，处峰峦，则以白云为期，处山林，则以归鸟为期，处平原，则以日影为期，只要保证不会每次相同就行。

小剧场中大将军的选举基本实现了Raft算法所有节点达成一致性的目标。下面我们将以详细图解的方式，为大家介绍算法具体实现时的原理。

Raft算法将自己定位为key-value型数据库，集群保证一致性的共识机制，其实是集群内的节点角色变换和日志同步的过程，下面来介绍Raft算法的选举制度和日志管理。

通过上面的拜占庭新编，大家可以大致了解Raft算法中的选举制度，在实际算法中，小故事中角色对应Raft算法如下：

容小编先来说明一下人物和任期对应关系👇👇👇

Leader节点（领导者）：响应和分发来自客户端的日志请求；

Follower节点（跟随者）: 接收和复制来自leader节点的日志，受leader监管;

Candidate节点（候选者）：候选人向集群中的所有节点发送投票请求，获得投票占总数的半数以上的候选人将成为leader节点；

Follower Timeout : Follower在一段时间内未收到leader节点发送心跳检测或日志复制请求，这段倒计时为空位期；

Candidate Timeout : candidate节点发送选举请求开始计时到成功当选或竞选结束的时间；

Term ：标明当前集群所处的世界状态，时间区间为candidate节点选举成功后，到下一个candidate节点开始选举并成功的时间，若出现两个leader节点时，领导权交由任期大的leader；

Election Timeout ：延选时间，节点设置空档期和选举期长度，官方推荐时间长短为150ms~300ms；

Heartbeat : 心跳检测，每隔一段时间，leader节点会发送一则附带日志同步的请求给集群内除自己外的所有follower节点，follower节点收到心跳检测后，需回复请求方。

为方便大家了解选举规则，每个节点中心会标记所处任期，节点图例如下：

在小剧场中，大将军选举时会面临来自各种因素导致的信息无法同步问题，我们以gif图来模拟展示选举情况👇👇👇。

正常选举

集群初期无leader节点，S1~S5节点均为follower节点，任期均为1期， S1空位期倒计时率先结束，S1推选自己为候选人，进入候选者状态，任期更迭为2期，并向集群中S2~S4节点发送投票请求，S2~S4节点在自己空位期结束前，投票给S1，S1当选为leader节点，集群进入正常同步状态，集群保持大多数一致。

Leader节点故障

当S1突发故障，未给其余follower节点发送心跳监测，S2节点空位期先结束，进入选举期，任期变更为3期，后续如前面正常选举出leader节点，集群保持大多数一致。

这里有个问题要注意，若故障节点数量为f时，正常节点数量必须为f+1,选举制度才能保证少数服从多数的规则，所以Raft节点设置数应为n=2f+1。

细心的同学应该发现，S1的任期并未变更为集群任期3，这个知识点我们会在下一节日志同步中介绍。

选举冲突

当S1故障后,任期变更为2，S2、S3、S4先后进入候选者状态，其中 S2得1票、S3得2票、S4 得1票，均小于半数，任期2无leader节点，因S1故障，推荐选举心跳检测未回应，所以候选者们再次发送单独心跳检测给S1，任期2无leader节点当选，待S3选举期率先结束，重新发起选举，任期变更为3，S3获得投票数大于总数的一半成功当选Leader节点，集群保持大多数一致。

日志同步是指leader接受到客户端消息或指令，同步给集群中的flower的过程。区块链集群的各节点中大多数节点日志保持一致的过程就是共识机制。

1）leader接收消息，并保存在本地

Leader本地消息内容为：马八进七

Leader本地消息状态为：uncommitted

2）Follower接收日志并同步到本地

Follower本地消息内容为：马八进七

Follower本地消息状态为：uncommitted

3)Follower回复给Leader成功收到消息

Leader本地消息状态为：committed

4）在多数的Follower回复收到消息后，Leader会判断此条消息有效，提交该日志，存储到磁盘中，并向其他节点发送存储指令的心跳检测，各节点接受到提交指令后，将日志存储到各自的磁盘中

Follower本地消息状态为：committed

1）集群任期为2，节点日志同步为马八进七：

2）因网络原因，集群如图分为两部分，上半部分A块任期依旧为2，Leader功能正常并接收到客户端的同步日志请求，内容为车一进一 ：

此时向A块的Follower发送同步请求，但是因为日志提交前的Follower响应数小于集群总数一半，此时Leader与Follower的本地日志状态均为uncommited，并向客户端返回日志未提交的报错信息，日志存储无效。

网络下半部分B块因原Leader隔离，剩下的Follower节点重新选举新Leader。

新Leader选举成功后，B块任期为3：

新Leader从客户端收到日志消息，内容为炮二平五：

B块Follower响应数大于半数，Leader与Follower的本地日志状态均为commited：

网络故障修复后，集群同时出现2个Leader，当任期为2的A块Leader接收到任期为3的B块Leader的heartbeat后，自动降级为Follower：

加入新任期的集群时，原A块旧节点会删除未提交的错误日志：

待Leader节点同步正确的日志信息，最后结果如下：

Raft是较容易理解的分布式一致算法，其核心功能为选主和日志同步，适用于集群中没有作恶节点的情况，目前Raft算法可以找到各种主流语言，比如C/C++/Java/Python/Javascript等，其流行程度可见一斑。由此可见，一项技术能否在工业界大行其道，有时“可理解性”和“可实现性”是至关重要的。