文档章节

分布式一致性算法----Raft

A
 AlexT
发布于 2017/06/29 17:41
字数 761
阅读 295
收藏 0

阿里云携手百名商业领袖、技术大咖,带您一探行进中的数字新基建!>>>

Raft 是解决分布式一致性的协议。Raft将分布式系统中的结点分成三种状态:Leader,Follower,Candidate。大致分为如下几步:

一、 Leader Election

(1)所有的结点初始都为 follower状态。

(2)如果followers 不能从Leader听见任何消息就会变成Candidate。

(3)Candidate会从其他结点那请求vote,其他结点会返回自己的vote。

(4)如果这个Candidate从大部分结点那得到vote,则此Candidate变成Leader。

 

二、Log Replication

(1)所有对系统的set等改变都会途径这个Leader。

(2)每一个对系统set的改变都会作为一个Entry添加到结点的log中。下面场景是说向分布式系统中提交set 5。

(3)若Log没有提交,则Node a的值不会改变,并且向Node b与 Node c 同步修改日志

(4)之后leader等待,知道大部分结点将这个Entry写入等待提交。

(5)leaderNode提交,并且node的State变为5,同时告知所有followers ,Entry已经被提交了。

(6) 集群系统状态被同步了。

 

三、TimeOut

在集群中有两个地方可能timeout,第一个是Election timeout。

(1)ElectionTimeout 选举超时是一个Follower等到变成一个Candidate的时间,election timeout 在150ms和300ms之间取随机值。

(2) 在 ElectionTimeout 超时之后,follower 变成了一个candidate 并且开始一个新的election term---即发起vote请求给其他结点。

(3) 如果结点没有为这个vote,则vote并重置自己的ElectionTimeout的时间。若一个候选人拥有大多数的vote,则变成leader。

(4) Leader开始发出Append Entries 消息给所有的folllowers。

(5) 在发消息内部有个timeOut 叫做 heartbeat timeout,所有的消息都是以heartBeat的方式传输的。

(6) Followers 回复每一个Append Entires消息。

(7) 这个election term会继续 直到一个follower停止接受心跳并且变成一个candidate。

(8)若node A挂了,重新选举。node B变成新的leader。

四、 split-brain脑裂处理

split-brain(脑裂) ,若node是偶数个,如下图:Node A和Node C同时发起选举:

    之后 node A与 node C 都有了两个votes,并且不会接受更多的vote。

之后Node A与 Node C会等待等到有新的Candidate 发出 requests vote。

 

五、分区容错

若有5个节点,Node B是leader,假设在A,B与 C D E之间做了分隔,那这时会出现两个leader在不同的terms里。

如果有两个客户端,一个客户端向Node B发送了一个SET 3的请求,然后Node B得到大多数的结点的回复,所有一直不会提交。

另一个客户端,发送set 8到Node C,这时Node C提交。

Node B 需要更高的election term 并且 step down。

Node A和B都会回滚未提交的日志,并且同步新Leader的log。 这时,集群又重新同步了。

 

后续有时间解读一下 Redis的集群方案。

参考资料:

http://thesecretlivesofdata.com/raft/

© 著作权归作者所有

A
粉丝 1
博文 13
码字总数 28763
作品 0
海淀
私信 提问
加载中

评论(0)

分布式理论(六)—— Raft 算法

前言 我们之前讲述了 Paxos 一致性算法,虽然楼主尝试用最简单的算法来阐述,但仍然还是有点绕。楼主最初怀疑自己太笨,后来才直到,该算法的晦涩难懂不是只有我一个人这么认为,而是国际公认...

osc_ht9rr956
2018/05/19
6
0
Raft系列文章之一: 什么是Raft?

简单的说,Raft是一种易于理解的一致性算法,其功能相当于Paxos。目前很多提供一致性服务的系统都采用Paxos, 例如Chubby, ZooKeeper, 那么为何还需要Raft?自Lamport 1998年提出Paxos以来, 该...

cccyb
2016/10/11
142
0
Raft 与 Paxos的区别

Raft Raft概述 Raft一致性算法用于保证在分布式的条件下,所有的节点可以执行相同的命令序列,并达到一致的状态。这类的问题可以归结为“Replicated state machines”问题。 Raft一致性算法的...

cloud-coder
2016/07/14
2.4K
0
理解分布式一致性与Raft算法

理解分布式一致性与Raft算法 永远绕不开的CAP定理 出于可用性及负载方面考虑,一个分布式系统中数据必然不会只存在于一台机器,一致性简单地说就是分布式系统中的各个部分保持数据一致 但让数...

osc_i6ddt53t
04/16
6
0
【深度】分布式数据库数据一致性原理说明与实现

前言 分布式数据库的数据一致性管理是其最重要的内核技术之一,也是保证分布式数据库满足数据库最基本的 ACID特性中的 “一致性”(Consistency)的保障。在分布式技术发展下,数据一致性的解...

巨杉数据库
2017/10/20
1K
0

没有更多内容

加载失败,请刷新页面

加载更多

URL 中文链接 编码错误 完美解决

直接上代码 str = "%25E4%25B8%25AD%25E6%2596%2587";console.log(str);str =decodeURIComponent(decodeURIComponent(str));console.log(str); 输出结果 %25E4%25B8%25AD%25E6%2596%25......

放只虎归个山
21分钟前
7
0
.NET中小数,浮点数和双精度之间的区别? - Difference between decimal, float and double in .NET?

问题: What is the difference between decimal , float and double in .NET? .NET中的decimal , float和double float什么区别? When would someone use one of these? 有人什么时候会使用......

fyin1314
今天
22
0
如何找出Windows上正在侦听端口的进程? - How can you find out which process is listening on a port on Windows?

问题: 如何找出Windows上正在侦听端口的进程? 解决方案: 参考一: https://stackoom.com/question/CXO/如何找出Windows上正在侦听端口的进程 参考二: https://oldbug.net/q/CXO/How-can...

技术盛宴
今天
10
0
OSChina 周三乱弹 —— 一家动物都快饿成标本了~

@黑觉非常君 :前天晚上9点开始睡觉,睡到昨天上午8点起床,昨天下午2点又睡,睡到下午7点多,晚上10点又困了,又睡,睡到今天上午8点,中途没醒过,怎么这么能睡,是不是快挂了。 能睡不是好...

小小编辑
今天
15
0
神剧推荐全剧最污片段精剪

神剧推荐,全剧最污片段精剪 豆瓣评分最高,脑洞最大,脑回路最曲折,恶搞无数经典,没有一条差评的神剧 整个系列完整版 到这里观看

a57571735
今天
22
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部