文档章节

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

A
 AlexT
发布于 2017/06/29 17:41
字数 761
阅读 60
收藏 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
海淀
Raft系列文章之一: 什么是Raft?

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

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

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

cloud-coder
2016/07/14
1K
0
etcd:用于服务发现的键值存储系统

etcd是一个高可用的键值存储系统,主要用于共享配置和服务发现。etcd是由CoreOS开发并维护的,灵感来自于 ZooKeeper 和 Doozer,它使用Go语言编写,并通过Raft一致性算法处理日志复制以保证强...

夕水溪下
2014/07/29
33.5K
7
【深度】分布式数据库数据一致性原理说明与实现

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

巨杉数据库
2017/10/20
0
0
从分布式一致性到共识机制(二)Raft算法

春秋五霸说开 春秋五霸,是指东周春秋时期相继称霸主的五个诸侯,“霸”,意为霸主,即是诸侯之领袖。 典型的比如齐桓公,晋文公,春秋时期诸侯国的称霸,与今天要讨论的Raft算法很像。 一、...

邴越
04/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

docker中安装了RabbitMQ后无法访问其Web管理页面

在官网找了"$ docker run -d --hostname my-rabbit --name some-rabbit -p 8080:15672 rabbitmq:3-management"这条安装命令,在docker上安装了RabbitMQ,,结果输入http://localhost:8080并不......

钟然千落
32分钟前
0
0
spring-cloud | 分布式session共享

写在前面的话 各位小伙伴,你们有福了,这一节不仅教大家怎么实现分布式session的问题,还用kotlin开发,喜欢kotlin的小伙伴是不是很开心! 以前在写Android的时候,就对客户端请求有一定的认...

冯文议
51分钟前
0
0
c语言之内存分配笔记

先看一个数组: short array[5] = {1,2} // 这儿定义的一个int类型的数组,数组第1和第2个元素值是1和2.其余后面默认会给值为0; 或者 short array[] = {1,2};//这儿数组第1和第2个元素,数组...

DannyCoder
今天
4
0
Shell | linux安装包不用选择Y/N的方法

apt-get install -y packageOR echo "y" | sudo apt-get install package

云迹
今天
2
0
Hadoop的大数据生态圈

基于Hadoop的大数据的产品圈 大数据产品的一句话概括 Apache Hadoop: 是Apache开源组织的一个分布式计算开源框架,提供了一个分布式文件系统子项目(HDFS)和支持MapReduce分布式计算的软件架...

zimingforever
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部