文档章节

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

戴的天
 戴的天
发布于 2015/08/13 00:14
字数 1590
阅读 158
收藏 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
915
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

没有更多内容

加载失败,请刷新页面

加载更多

FTP 协议 1.0

自己制作的FTP协议:

Explorer0
21分钟前
1
0
Android 通过DrawableInflater加载自定义Drawable

一、Drawable 在Android系统张,图形图像的绘制需要在画布上进行操作和处理,但是绘制需要了解很多细节以及可能要进行一些复杂的处理,因此系统提供了一个被称之为Drawable的类来进行绘制处理...

IamOkay
32分钟前
1
0
灵活无处安放,所以选择流浪....《漆黑的空间》& 《灰色轨迹》

灵活无处安放,所以选择流浪....《漆黑的空间》& 《灰色轨迹》

yizhichao
39分钟前
1
0
Kafka+Flink 实现准实时异常检测系统

1.背景介绍 异常检测可以定义为“基于行动者(人或机器)的行为是否正常作出决策”,这项技术可以应用于非常多的行业中,比如金融场景中做交易检测、贷款检测;工业场景中做生产线预警;安防...

架构师springboot
今天
7
0
DecimalFormat 类基本使用

/* * DecimalFormat 类主要靠 # 和 0 两种占位符号来指定数字长度 * 0 表示如果位数不足则以 0 填充 * # 表示只要有可能就把数字拉上这个位置 * */ public static void main(String[] args){...

嘴角轻扬30
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部