文档章节

一致性算法探寻(扩展版)图解

戴的天
 戴的天
发布于 2015/08/13 00:14
字数 1590
阅读 155
收藏 4

首先,翻一下图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的条目是最新的。


© 著作权归作者所有

共有 人打赏支持
戴的天
粉丝 16
博文 63
码字总数 83564
作品 0
杭州
技术主管
Google App Engine SDK 1.5.1 发布

Google I/O 2011 结束一月后,Google 发布了新版 Google App Engine SDK。本月 Google 将 ProtoRPC 作为正式 Python API 发布,在 SDK 中提供 High Replication Datastore (HRD) 特性帮助开发...

老枪
2011/06/22
871
1
一致性算法探寻(扩展版)10

8 Client interaction This section describes how clients interact with Raft, including how clients find the cluster leader and how Raft supports linearizable semantics [10]. Thes......

戴的天
2015/08/11
80
0
一致性算法探寻(扩展版)9

7 Log compaction Raft’s log grows during normal operation to incorporate more client requests, but in a practical system, it cannot grow without bound. As the log grows longer......

戴的天
2015/08/10
88
0
推荐书籍:《算法图解》

本书示例丰富,图文并茂,以让人容易理解的方式阐释了算法,旨在帮助程序员在日常项目中更好地发挥算法的能量。书中的前三章将帮助你打下基础,带你学习二分查找、大O表示法、两种基本的数据...

ddddd8
2017/11/26
0
0
Raft算法官方论文中文翻译

寻找一种易于理解的一致性算法(扩展版) https://github.com/maemual/raft-zhcn/blob/master/raft-zhcn.md

满小茂
2016/04/14
241
0

没有更多内容

加载失败,请刷新页面

加载更多

【mpvue】三

使用了快1个月,陆续整理发现的坑 1、pageA-pageB-pageA-pageC 如果以这种顺序,大概理解成,列表进详情B, 返回列表进入详情C,那么进入详情C的时候,会因为缓存,先展现详情B的内容。解决方...

登天的感觉
11分钟前
0
0
在EXCEL指定SHEET页,指定文字位置,插入批注

Java操作EXCEL文件,利用POI,在EXCEL指定SHEET页中指定文字位置处插入批注 package excel; import java.io.FileInputStream; import java.io.FileOutputStream; import org.apache.poi.hssf......

zhaochaochao
12分钟前
0
0
一些网站。

UI schema,可以用json定义UI表单:https://jsonforms.io/examples/array

王坤charlie
19分钟前
0
0
百万连接,百亿吞吐量服务的JVM性能调优实战

转载占小狼博客 应用:shark-新美大移动端网络优化(每日接受移动端请求约150亿) 应用特点 : qps比较高,新生代增长飞快 用户的连接需要维持一段时间 单机需要维持海量连接,几十万的级别 以...

BakerZhu
22分钟前
0
0
iOS涂色涂鸦效果、Swift仿喜马拉雅FM、抽屉转场动画、拖拽头像、标签选择器等源码

iOS精选源码 LeeTagView 标签选择控件 为您的用户显示界面添加美观的加载视图 Swift4: 可拖动头像,增加物理属性 Swift版抽屉效果,自定义转场动画管理器 Swift 仿写喜马拉雅FM 可能是最好用...

sunnyaigd
22分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部