文档章节

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

戴的天
 戴的天
发布于 2015/08/13 00:14
字数 1590
阅读 154
收藏 4
点赞 0
评论 0

首先,翻一下图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
博文 59
码字总数 79768
作品 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
《算法之道》精华 经典算法部分

《算法之道》精华 经典算法部分 本书作者邹恒明,作者另有一本书《数据结构之弦》,以及《操作系统之哲学原理》都是很好的书 这本书可以算得上是深入浅出,文笔很好,作者添加了很多自己的思...

modernizr
2014/08/11
489
1
Raft算法官方论文中文翻译

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

满小茂
2016/04/14
241
0
如何入门学算法?

随着科学技术的发展,人工智能已渗透到各个行业,算法工程师非常火爆,急缺大量人才,年薪也越来越高。很多人想入手学习算法,那么多算法,究竟该如何下手呢? 很多人看到招聘要求,知道算法...

rainchxy
2017/11/23
0
0
《Java 进阶之路》 下

真正想提升自己,我感觉最主要的是先把 JVM、并发、网络这三块知识点学会、学通,这三块是基础,后面所有的框架、中间件等相关的都是基于这三块知识点之上的。学完这三块知识点,可以快速的掌...

jijs
2017/11/29
0
0
图解分布式一致性协议Paxos

Paxos协议/算法是分布式系统中比较重要的协议,它有多重要呢? <分布式系统的事务处理>: Google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法,那就是Paxos,其它的算法都是残...

wangdy
2016/06/22
15
0
数据存储系统--CockroachDB

CockroachDB (蟑螂数据库)是一个可伸缩的、支持地理位置处理、支持事务处理的数据存储系统。 CockroachDB 提供两种不同的的事务特性,包括快照隔离(snapshot isolation,简称SI)和顺序的快...

红薯
2014/05/31
11.8K
7

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Elasticsearch学习(7)—— 查询API

1. ElasticSearchRepository的基本使用 @NoRepositoryBean public interface ElasticsearchRepository<T, ID extends Serializable> extends ElasticsearchCrudRepository<T, ID> { <S exten......

叶枫啦啦
3分钟前
0
0
TextView设置行间距、字体间距

一、设置行间距 1、设置行间距:android:lineSpacingExtra,取值范围:正数、负数和0,正数表示增加相应的大小,负数表示减少相应的大小,0表示无变化 2、设置行间距的倍数:android:lineSpa...

王先森oO
11分钟前
0
0
适配器模式

适配器模式(Adapter):将一个类的接口转换成客户端希望的另外一个接口,适配器模式使得原本由于接口不兼容而不能一起工作的那些类可以一起工作。 适配器用于连接两种不同种类的对象,使其毫...

阿元
11分钟前
0
0
CoreText进阶(四)-文字行数限制和显示更多

CoreText进阶(四)-文字行数限制和显示更多 用例和效果 Demo:CoreTextDemo 效果图: 默认的截断标识和自定义的截断标识符效果图  点击查看更多之后的效果图  为了可以设置显示的行数以...

aron1992
13分钟前
0
0
nginx的五种负载算法

nginx的五种负载算法 2017年04月26日 15:01:11 阅读数:1297 1.round robin(默认) 轮询方式,依次将请求分配到各个后台服务器中,默认的负载均衡方式。 适用于后台机器性能一致的情况。 挂...

linjin200
15分钟前
0
0
Android RecyclerView快速上手

RecyclerView mainMenu = findViewById(R.id.fragmentMain); mainMenu.setLayoutManager(new GridLayoutManager(getActivity(),4)); mainMenu.setAdapter(new MainAdapter......

燕归南
17分钟前
0
0
RabbitMQ实战:理解消息通信 

应用RabbitMQ的5种队列 一、简单队列 P:消息的生产者 C:消息的消费者 红色:队列 简单队列的生产者和消费者关系一对一 但有时我们的需求,需要一个生产者,对应多个消费者,那就可以采用第...

spinachgit
18分钟前
0
0
Linux的使用技巧:到底要不要会用?[图]

Linux的使用技巧:到底要不要会用?[图] 最近有个项目接近了尾声,要进入到调试测试阶段。这是一个使用Springboot框架为后台程序,mpvue构建的小程序项目。服务器我最终仍旧选择了Linux操作系...

原创小博客
20分钟前
0
0
记elasticdump 备份数据导出导入

版本: elasticsearch 5.5.2 elasticdump 2.2 系统 CentOS7.3 因项目需求 从生产导出一份索引到测试 帮助文档 https://github.com/taskrabbit/elasticsearch-dump?utm_source=dbweekly&utm_m......

雁南飞丶
21分钟前
0
0
saltstack配置目录管理

1.服务端配置 -接着编辑之前的 top.sls 文件 #vim /srv/salt/top.sls //修改为如下 base: 'slaver.test.com': - filedir -新建 filedir.sls 文件 # vim /srv/salt/filedir.sls file-dir: fi......

硅谷课堂
21分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部