一致性算法探寻(扩展版)图解
一致性算法探寻(扩展版)图解
戴的天 发表于3年前
一致性算法探寻(扩展版)图解
  • 发表于 3年前
  • 阅读 146
  • 收藏 4
  • 点赞 0
  • 评论 0

【腾讯云】买域名送云解析+SSL证书+建站!>>>   

摘要: 有关《In Search of an Understandable Consensus Algorithm(Extended Version)》的图片解析

首先,翻一下图1的注释:复制状态机架构。一致性算法管理日志复制包括从可短接收的状态机命令。状态机处理日志里相同序列的命令,所以他们产生相同的输出。

正式图解,首先图1分为2个部分,客户端和服务器。箭头1由客户端指向服务器的一致性模块,表示由客户端发送请求至服务器由一致性模块接收,然后才有箭头2进行分发日志处理的命令。可以看到箭头2指向多层的log模块,表示多个服务器接收了该信息。日志处理完成后,出现箭头3,日志模块发送消息给状态机,最后由状态机返回结果给客户端。这里主要阐述状态机的实现。

再来由于图2太大,我手动做了切分,并且图2也是Raft通信的基础,一共4种信息类型。如上图2-1,这里描述了Raft的几种状态消息组成部分。

  1. Persistent state on all Serve:在响应RPC之前更新过时信息。该信息包括currentTerm、voteFor以及log[]3个部分。currentTerm就是服务器最新的term值(初始为0,依次增加)。votedFor是当前term里让你投票的candidate的id(如果没有则为null)。log[]就是日志条目数组了,每个条目包含状态机命令和leader接收到日志的term值。

  2. Volatile state on all Server:包含两部分,commitIndex和lastApplied。commitIndex是已知的已提交的日志条目的最大索引值(初始为0,依次增加)。lastApplied是向状态机申请的条目最大索引值(初始为0,依次增加)。

  3. Volatile state on leaders:包含两部分,nextIndex[]和matchIndex[]。nextIndex[]是发送给其他服务器的下一条日志条目的索引值(初始为leader最新日志索引+1)。matchIndex[]是服务器已知要被复制的日志条目的最大索引值(初始为0,依次增加)。

图2-2展示的是AppendEntries RPC(由leader提出用来复制日志条目,也用作心跳)的组成结构。参数有term,leaderId,preLogIndex,preLogTerm,entries[]和leaderCommit这些。因为AppendEntries RPC是由leader发出的,所以这里的参数都是leader的状态,没什么好解释的。返回结果由term和success两部分组成。term就是当前term,用来给leader升级自己的term的,success则在follower的日志条目匹配了preLogIndex和nextLogIndex的时候为true。同时,接收者实现了以下5个原则:1.如果term<currentTerm,返回false(5.1节)。2.如果日志没有匹配preLogTerm的条目在preLogIndex位置(5.3节)。3.如果一个已存在的条目和一个新的条目冲突了(相同的索引,不同的term值),删除已存在的条目并且跟随它(5.3节)。4.可以增加日志中不存在的条目。5.如果leaderCommit>commitIndex,则将commitIndex=min(leaderCommit,最新条目的索引)。


图2-3显示的是RequestVote RPC的结构。参数有term,candidateId,lastLogIndex,lastLogTerm4种。这是由candidate发送给follower的消息,4个参数代表了candidate的属性。返回结果由term和voteGranted两部分组成。term是用来给candidate升级自己的currentTerm值,而voteGranted则是回执,表示candidate接收了选票。接收者遵循以下2个条件:1.如果term<currentTerm返回false(5.1节)。2.如果voteFor为空或是candidateId,并且candidate的日志至少和接收的日志一样新,则拉票成功。

图2-4显示了服务器的几项准则。对于所有服务器来说:如果commitIndex>lastApplied,增加lastApplied并向状态机申请日志[lastApplied]。如果RPC请求或响应包含了term T>currentTerm,则currentTerm=T,转为follower状态。

对于follower来说:响应candidate和leader的RPC。如果选举超时,即没有接收到当前leader的AppendEntries RPC或candidate的拉票,则转为candidate。

对于candidate来说:一旦转为candidate就开始一次选举:增加currentTerm值,投票给自己,重置选举计数器,发送RequestVote PRC给其他服务器。如果获得大多数服务器的选票,则当选为leader;如果接收到新的leader发送的AppendEntries RPC,则转为follower;如果选举超时,则开始新一轮选举。

对于leader来说:当选后,发送初始为空的的AppendEntries RPC(心跳)给每个服务器;在空闲时间重复发送心跳以防止选举超时(5.2节)。如果接收到客户端发送的命令时,增加日志条目,在向状态机申请条目后响应客户端(5.3节)。如果一个follower的最新日志索引nextIndex,则发送带有nextIndex开始的新日志条目的AppendEntries RPC:如果成功,更新follower的nextIndex和matchIndex(5.3节);如果因为日志的不一致失败,则减少nextIndex并重新尝试。如果存在一个N>commitIndex,大部分的matchIndex[i]N,并且log[N].term == currentTerm,则设置commitIndex = N(5.3,5.4节)。

图3显示了Raft的几个特性。列举了选举安全性、leader增量、日志匹配、leader完整性和状态机安全性。

图4显示的是Raft算法三种状态的切换关系。首先,整个集群刚启动时,所有服务器都是follower,然后随机有follower因为没有接收到通信信息而转为candidate,参与竞选,如果得到集群中大部分认同则当选成为leader,没有获得大部分选票的则继续回到follower状态。如果leader发现有服务器的term比它高,则退位成为follower,并开始新一轮选举。其中如果candidate在选举过程中发现超时则继续为candidate并开始新一轮选举。

图5主要显示集群系统的term是线性增长的。

图6是日志提交的示例图。坐标横轴是log的index,可以看到leader的日志index是8,当前term是3。其他的follower则存在各种状态,其中最下面的follower条目已经提交到了第7条,即commitIndex=7,term=3。

图7展示了leader怎么保持commited的条目是最新的。


标签: raft
  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 16
博文 59
码字总数 79768
×
戴的天
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: