文档章节

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

A
 AlexT
发布于 2017/06/29 17:41
字数 761
阅读 81
收藏 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 与 Paxos的区别

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

cloud-coder
2016/07/14
1K
0
Raft系列文章之一: 什么是Raft?

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

cccyb
2016/10/11
13
0
Raft实现指南

之前有篇文章提到Mushroom(我项目的名字)下一步的计划是分布式索引,经过一段时间的努力我已经实现了一致性算法Raft并完成了单机上的测试。 文章大致分为3个部分,提供Raft相关资料,介绍R...

UncP
2017/05/28
0
0
【深度】分布式数据库数据一致性原理说明与实现

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

巨杉数据库
2017/10/20
0
0
Raft算法分析以及在软负载中的实现研究

分布式系统下数据的一致性和系统可用性一直是个难题,工程上也有多种解决方案,如:mysql/RocketMQ的主备复制方案,本文将借助软负载服务的研究对Raft分布式一致性协议做分析和讨论。 本文主...

zqrferrari
2017/11/15
0
0

没有更多内容

加载失败,请刷新页面

加载更多

java框架学习日志-7(静态代理和JDK代理)

静态代理 我们平时去餐厅吃饭,不是直接告诉厨师做什么菜的,而是先告诉服务员点什么菜,然后由服务员传到给厨师,相当于服务员是厨师的代理,我们通过代理让厨师炒菜,这就是代理模式。代理...

白话
45分钟前
6
0
Flink Window

1.Flink窗口 Window Assigner分配器。 窗口可以是时间驱动的(Time Window,例如:每30秒钟),也可以是数据驱动的(Count Window,例如:每一百个元素)。 一种经典的窗口分类可以分成: 翻...

满小茂
46分钟前
3
0
my.ini

1

architect刘源源
今天
6
0
docker dns

There is a opensource application that solves this issue, it's called DNS Proxy Server It's a DNS server that solves containers hostnames, if could not found a hostname that mat......

kut
今天
7
0
寻找数学的广度——《这才是数学》读书笔记2700字

寻找数学的广度——《这才是数学》读书笔记2700字: 文|程哲。数学学习方式之广:国内外数学教育方面的专家,进行了很多种不同的数学学习方式尝试,如数学绘本、数学游戏、数学实验、数学步道...

原创小博客
今天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部