文档章节

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

A
 AlexT
发布于 2017/06/29 17:41
字数 761
阅读 69
收藏 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

没有更多内容

加载失败,请刷新页面

加载更多

大数据框架对比:Hadoop、Storm、Samza、Spark和Flink

简介 大数据是收集、整理、处理大容量数据集,并从中获得见解所需的非传统战略和技术的总称。虽然处理数据所需的计算能力或存储容量早已超过一台计算机的上限,但这种计算类型的普遍性、规模...

hblt-j
26分钟前
2
0
正则介绍及grep/egrep用法

10月16日任务 9.1 正则介绍_grep上 9.2 grep中 9.3 grep下 扩展 把一个目录下,过滤所有*.php文档中含有eval的行 grep -r --include="*.php" 'eval' /data 9.1 正则介绍_grep上 什么是正则 ...

zgxlinux
42分钟前
2
0
想用Unity3D引擎软件赚点钱的看过来

前言: 你可以不拥有很多钱 但你一定要有赚钱的能力 目前手上有项目, 需要熟练Unity3D引擎软件的伙伴 有意向的给我发私信

猿神出窍
44分钟前
2
0
Spring Boot全局异常处理

Spring Boot默认的异常处理机制 默认情况下,Spring Boot为两种情况提供了不同的响应方式。 一种是浏览器客户端请求一个不存在的页面或服务端处理发生异常时,一般情况下浏览器默认发送的请求...

狼王黄师傅
今天
8
0
Thinkphp5 优雅配置两个数据库

工作需要需要配置两个数据库,框架5.0的,步骤如下: 1、在database.php同级创建一个database2.php文件 在里面配置第二个数据库信息, 2、在config中配置这个数据库信息: 3、创建第二个表的...

wqzbxh
今天
5
1

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部