肝了一个月的ETCD，从Raft原理到实践（二）-阿里云开发者社区

肝了一个月的ETCD，从Raft原理到实践（二）

2022-05-30 158

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

本文涉及的产品

日志服务 SLS，月写入数据量 50GB 1个月

简介： 高能预警，本文是我今年年初写了，当时花了一个月时间，所以内容会比较长，其中的Raft协议非常硬核，由于当时对文章排版不熟练，所以可读性不高，现在对文章重新整理，提炼了比较核心的内容。

选举

领导人选举

为了便于后续的讲解，我画了一副简图，“选举定时器”其实就是每个节点的“超时时间”。

OKFSQQQK3Z1H74D7HXXA@@H.png

成为候选人：每个节点都有自己的“超时时间”，因为是随机的，区间值为150~300ms，所以出现相同随机时间的概率比较小，因为节点B最先超时，这时它就成为候选人。

)FQ3D3B%89~$7T~VMB6$JCL.png

选举领导人：候选人B开始发起投票，群众A和C返回投票，当候选人B获取大部分选票后，选举成功，候选人B成为领袖。

E2HFJIS0}]3SXM630T[)~4O.png

心跳探测：为了时刻宣誓自己的领导人地位，领袖B需要时刻向群众发起心跳，当群众A和C收到领袖B的心跳后，群众A和C的“超时时间”会重置为0，然后重新计数，依次反复。

这里需要说明一下，领袖广播心跳的周期必须要短于“选举定时器”的超时时间，否则群众会频繁成为候选者，也就会出现频繁发生选举，切换Leader的情况。

BYJO6VN3~SDC1%N49N]1)48.png

领袖挂掉情况

当领袖B挂掉，群众A和C会的“选举定时器”会一直运行，当群众A先超时时，会成为候选人，然后后续流程和“领导人选举”流程一样，即通知投票 -> 接收投票 -> 成为领袖 -> 心跳探测。

ES[]67G0(SDUXM{P6EEFWGS.png $YF7__BO}~1{TYP7C)$PEO]3.png$

出现多个候选者情况

当出现多个候选者A和D时，两个候选者会同时发起投票，如果票数不同，最先得到大部分投票的节点会成为领袖；如果获取的票数相同，会重新发起新一轮的投票。

当C成为新的候选者，此时的任期Term为5，发起新一轮的投票，其它节点发起投票后，会更新自己的任期值，最后选择新的领袖为C节点。

WIC7~W1A5@M0XGE2`KCE2RJ.png

MCK)H9X0_4`}F$5C29]R}R5.png

日志复制

复制状态机

复制状态机的基本思想是一个分布式的状态机，系统由多个复制单元组成，每个复制单元均是一个状态机，它的状态保存在操作日志中。如下图所示，服务器上的一致性模块负责接收外部命令，然后追加到自己的操作日志中，它与其他服务器上的一致性模块进行通信，以保证每一个服务器上的操作日志最终都以相同的顺序包含相同的指令。一旦指令被正确复制，那么每一个服务器的状态机都将按照操作日志的顺序来处理它们，然后将输出结果返回给客户端。

J%`[412QDP1$]8BH`QHOTBY.png

数据同步流程

数据同步流程，借鉴了“复制状态机”的思想，都是先“提交”，再“应用”。当Client发起数据更新请求，请求会先到领袖节点C，节点C会更新日志数据，然后通知群众节点也更新日志，当群众节点更新日志成功后，会返回成功通知给领袖C，至此完成了“提交”操作；当领袖C收到通知后，会更新本地数据，并通知群众也更新本地数据，同时会返回成功通知给Client，至此完成了“应用”操作，如果后续Client又有新的数据更新操作，会重复上述流程。

%BNU]}IS`5@ILFD}X73`)00.png

日志原理

每一个日志条目一般包括三个属性：整数索引Log Index、任期号Term和指令Commond。每个条目所包含的“整数索引”即该条目在日志文件中的槽位，“任期号”对应到图中就是每个方块中的数字，用于检测在不同服务器上日志的不一致问题，指令即用于被状态机执行的外部命令，图中就是带箭头的数字。

领导人决定什么时候将日志条目应用到状态机是安全的，即可被提交的呢？一旦领导人创建的条目已经被复制到半数以上的节点上了，那么这个条目就称为可被提交的。例如，图中的9号条目在其中4节点（一共7个节点）上具有复制，所以9号条目是可被提交的；但条目10只在其中3个节点上有复制，因此10号条目不是可被提交的。

XL0I`}P~N~MQ%F@2RJOVPJE.png

一般情况下，Leader和Follower的日志都是保存一致的，如果Leader节点在故障之前没有向其它节点完全复制日志文件之前的所有条目，会导致日志不一致问题。在Raft算法中，Leader会强制Follower和自己的日志保存一致，因此Follower上与Leader的冲突日志会被领导者的日志强制覆写。为了实现上述逻辑，就需要知道Follower上与Leader日志不一致的位置，那么Leader是如何精准找到每个Follower日志不一致的那个槽位呢？

Leader为每一个Follower维护了一个nextlndex，它表示领导人将要发送给该追随者的下一条日志条目的索引，当一个Leader赢得选举时，它会假设每个Follower上的日志都与自己的保持－致，于是先将 nextlndex初始化为它最新的日志条目索引数+1，在上图中，由于Leader最新的日志条目index是10 ，所以nextlndex的初始值是11。当Leader向Follower发送AppendEntries RPC时，它携带了（item_id，nextIndex - 1）二元组信息，item_id即为nextIndex - 1这个槽位的日志条目的term。Follower接收到AppendEntries RPC消息后，会进行一致性检查，即搜索自己的日志文件中是否存在这样的日志条目，如果不存在，就像Leader返回AppendEntries RPC失败，然后领导人会将nextIndex递减，然后进行重试，直到成功为止。之后的逻辑就比较简单，Follower将nextIndex之前的日志全部保留，之后的全部删除，然后将Leader的nextIndex之后的日志全部同步过来。

上面只是讲述了方法，下面举个例子，加深一下理解，还是以上面的图为例。Leader的nextlndex为11，向b发送AppendEntries RPC(6,10)，发现b没有，继续发送(6,9)(6,8) (5,7) (5,6) (4,5)，最后发送(4,4)才找到，所以对于b，nextlndex=4之后的日志全部删除，然后将Leader的nextlndex=4的日志全部追加过来。