文档章节

Raft一致性协议

openthings
 openthings
发布于 2018/02/02 10:00
字数 2948
阅读 95
收藏 0

Raft 一致性协议

概念入门:http://www.jdon.com/artichect/raft.html

原文来自:https://www.cnblogs.com/foxmailed/p/3418143.html

分布式存储系统通常通过维护多个副本来进行fault-tolerance,提高系统的availability,带来的代价就是分布式存储系统的核心问题之一:维护多个副本的一致性。一致性协议就是用来干这事的,即使在部分副本宕机的情况下。Raft是一种较容易理解的一致性协议。一致性协议通常基于replicated state machines,即所有结点都从同一个state出发,都经过同样的一些操作序列,最后到达同样的state。

为了便于理解,Raft大概将整个过程分为三个阶段,leader election,log replication和commit(safety)。

每个server处于三个状态:leader,follower,candidate。正常情况下,所有server中只有一个是leader,其它的都是follower。server之间通过RPC消息通信。follower不会主动发起RPC消息。leader和candidate(选主的时候)会主动发起RPC消息。

Leader election

时间被分为很多连续的随机长度的term(一段时间),一个term由一个唯一的id标识。每个term一开始就进行leader election:

    1. followers将自己维护的current_term_id加1。

    2. 然后将自己的状态转成candidate。

    3. 发送RequestVoteRPC消息(带上current_term_id) 给 其它所有server

这个过程会有三种结果:

    1. 自己被选成了主。当收到了majority的投票后,状态切成leader,并且定期给其它的所有server发心跳消息(其实是不带log的AppendEntriesRPC)以告诉对方自己是current_term_id所标识的term的leader。每个term最多只有一个leader,term id作为logical clock,在每个RPC消息中都会带上,用于检测过期的消息,比如自己是一个过期的leader(term id更小的leader)。当一个server收到的RPC消息中的rpc_term_id比本地的current_term_id更大时,就更新current_term_id为rpc_term_id,并且如果当前state为leader或者candidate时,将自己的状态切成follower。如果rpc_term_id比本地的current_term_id更小,则拒绝这个RPC消息。

    2. 别人成为了主。如1所述,当candidate在等待投票的过程中,收到了大于或者等于本地的current_term_id的声明对方是leader的AppendEntriesRPC时,则将自己的state切成follower,并且更新本地的current_term_id。

    3. 没有选出主。当投票被瓜分,没有任何一个candidate收到了majority的vote时,没有leader被选出。这种情况下,每个candidate等待的投票的过程就超时了,接着candidates都会将本地的current_term_id再加1,发起RequestVoteRPC进行新一轮的leader election。

投票策略:

每个server只会给每个term投一票,具体的是否同意和后续的Safety有关。

 

当投票被瓜分后,所有的candidate同时超时,然后有可能进入新一轮的票数被瓜分,为了避免这个问题,Raft采用一种很简单的方法:每个candidate的election timeout从150ms-300ms之间随机取,那么第一个超时的candidate就可以发起新一轮的leader election,带着最大的term_id给其它所有server发送RequestVoteRPC消息,从而自己成为leader,然后给他们发送心跳消息以告诉他们自己是主。

Log Replication

当leader被选出来后,leader就可以接受客户端发来的请求了,每个请求包含一条需要被replicated state machines执行的命令。leader会把它作为一个log entry,append到它的日志中,然后给其它的server发AppendEntriesRPC。当leader确定一个log entry被safely replicated了,就apply这条log entry到状态机中然后返回结果给客户端。如果某个follower宕机了或者运行的很慢,或者网络丢包了,则会一直给这个follower发AppendEntriesRPC直到日志一致。

当一条日志是commited时,leader才能决定将它apply到状态机中。Raft保证一条commited的log entry已经持久化了并且会被所有的server执行。

当一个新的leader选出来的时候,它的日志和其它的follower的日志可能不一样,这个时候,就需要一个机制来保证日志是一致的。如下图所示,一个新leader产生时,集群状态可能如下:

image

最上面这个是新leader,a~f是follower,每个格子代表一条log entry,格子内的数字代表这个log entry是在哪个term上产生的。

新leader产生后,log就以leader上的log为准。其它的follower要么少了数据比如b,要么多了数据,比如d,要么既少了又多了数据,比如f。

需要有一种机制来让leader和follower对log达成一致,leader会为每个follower维护一个nextIndex,表示leader给各个follower发送的下一条log entry在log中的index,初始化为leader

的最后一条log entry的下一个位置。leader给follower发送AppendEntriesRPC消息,带着(term_id, (nextIndex-1)), term_id即(nextIndex-1)这个槽位的log entry的term_id,follower接收到AppendEntriesRPC后,会从自己的log中找是不是存在这样的log entry,如果不存在,就给leader回复拒绝消息,然后leader则将nextIndex减1,再重复,知道AppendEntriesRPC消息被接收。

以leader和b为例:

初始化,nextIndex为11,leader给b发送AppendEntriesRPC(6,10),b在自己log的10号槽位中没有找到term_id为6的log entry。则给leader回应一个拒绝消息。接着,leader将nextIndex减一,变成10,然后给b发送AppendEntriesRPC(6, 9),b在自己log的9号槽位中同样没有找到term_id为6的log entry。循环下去,直到leader发送了AppendEntriesRPC(4,4),b在自己log的槽位4中找到了term_id为4的log entry。接收了消息。随后,leader就可以从槽位5开始给b推送日志了。

Safety

1.哪些follower有资格成为leader?

Raft保证被选为新leader的server拥有所有的已经committed的log entry,这与ViewStamped Replication不同,后者不需要这个保证,而是通过其他机制从follower拉取自己没有的commited的log entry。

这个保证是在RequestVoteRPC阶段做的,candidate在发送RequestVoteRPC时,会带上自己的最后一条log entry的term_id和index,server在接收到RequestVoteRPC消息时,如果发现自己的日志比RPC中的更新,就拒绝投票。日志比较的原则是,如果本地的最后一条log entry的term id更大,则更新,如果term id一样大,则日志更多的更大(index更大)。

2. 哪些log entry被认为是commited?

 

Image[6]

 

两种情况:

1. leader正在replicate当前term即term2的log entry给其它follower,一旦leader确认了这条log entry被majority写盘了,这条log entry就被认为是committed。如图a,S1作为当前term即term2的leader,log index为2的日志被majority写盘了,这条log entry被认为是commited

2. leader正在replicate更早的term的log entry给其它follower。图b的状态是这么出来的:

S1作为term2的leader,给S1和S2 replicate完log index=2的日志后crash,当前状态为:

S1 1 2 宕机

S2 1 2

S3 1

S4 1

S5 1

S5被选为term3的leader(由于S5的最后一条log entry比S3,S4的最后一条log entry更新或一样新,接收到S3,S4,S5的投票),自己产生了一条term3的日志,没有给任何人复制,就crash了,当前状态如下:

S1 1 2

S2 1 2

S3 1

S4 1

S5 1 3 宕机

接着S1重启后,又被选为term4的leader(接收到S1,S2,S3的投票,文中没有指出S4?),然后S1给S3复制了log index为2的log entry,当前状态如下:

S1 1 2

S2 1 2

S3 1 2

S4 1

S5 1 3 宕机

这个时候S5重启,被选为了term5的主(接收了S2,S3,S4,S5的投票),那么S5会把log index为2的日志3复制给其它server,那么日志2就被overwrite了。

所以虽然这里日志2被majority的server写盘了,但是并不代表它是commited的。

 

对commit加一个限制:主的当前term的至少一条log entry被majority写盘

如:c图中,就是主的当前term 4的一条log entry被majority写盘了,假设这个时候S1宕机了,S5是不可能变成主的。因为S2和S3的log entry的term为4,比S5的3大。

 

关于算法的正确性证明见:Raft implementations

Log Compaction

在实际的系统中,不能让日志无限增长,否则系统重启时需要花很长的时间进行回放,从而影响availability。Raft采用对整个系统进行snapshot来处理,snapshot之前的日志都可以丢弃。

snapshot技术在Chubby和ZooKeeper系统中都有采用。

3TN$U25}D`IMYP9NGXXIO~Q

每个server独立的对自己的系统状态进行snapshot,并且只能对已经committed log entry(已经apply到了状态机)进行snapshot,snapshot有一些元数据,包括last_included_index,即snapshot覆盖的最后一条commited log entry的 log index,和last_included_term,即这条日志的termid。这两个值在snapshot之后的第一条log entry的AppendEntriesRPC的consistency check的时候会被用上,之前讲过。一旦这个server做完了snapshot,就可以把这条记录的最后一条log index及其之前的所有的log entry都删掉。

snapshot的缺点就是不是增量的,即使内存中某个值没有变,下次做snapshot的时候同样会被dump到磁盘。

当leader需要发给某个follower的log entry被丢弃了(因为leader做了snapshot),leader会将snapshot发给落后太多的follower。或者当新加进一台机器时,也会发送snapshot给它。

发送snapshot使用新的RPC,InstalledSnapshot。

做snapshot有一些需要注意的性能点,1. 不要做太频繁,否则消耗磁盘带宽。 2. 不要做的太不频繁,否则一旦server重启需要回放大量日志,影响availability。系统推荐当日志达到某个固定的大小做一次snapshot。3. 做一次snapshot可能耗时过长,会影响正常log entry的replicate。这个可以通过使用copy-on-write的技术来避免snapshot过程影响正常log entry的replicate。

 

Cluster membership changes

Raft将有server加入集群或者从集群中删除也纳入一致性协议中考虑,避免由于下线老集群上线新集群而引起的不可用。集群的成员列表重配置也是一条log entry,log内容包含了集群成员列表。

老集群配置用Cold表示,新集群配置用Cnew表示。

当集群成员配置改变时,leader收到人工发出的重配置命令从Cold切成Cnew,leader 给其它server复制一条特殊的log entry给其它的server,内容包括Cold∪Cnew,一旦server收到了这条特殊的配置log entry,其后的log entry会被replicate到Cold∪Cnew中,一条log entry被认为是committed的需要满足这条日志既被Cold的majority写盘,也被Cnew的majority写盘。一旦Cold∪Cnew这条log entry被确认为committed,leader就会产生一条只包含了Cnew的log entry,同样复制给所有server,server收到log后,老集群的server就可以自动下线了。

Performance

image

 

横坐标代表没有leader的ms数,每条线代表election timeout的随机取值区间。

上图说明只要给个5ms的区间,就能避免反复的投票被瓜分。超过10s没有leader的情况都是因为投票被瓜分的情况。

150-150ms的election timeout区间,没有主的时间平均287ms。

系统推荐使用150ms~300ms。

 

参考资料:

In Search of an Understandable Consensus Algorithm

本文转载自:https://www.cnblogs.com/foxmailed/p/3418143.html

上一篇: Gossip协议简介
下一篇: qTox源码编译
openthings
粉丝 322
博文 1134
码字总数 685726
作品 1
东城
架构师
私信 提问
从分布式一致性到共识机制(二)Raft算法

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

邴越
2018/04/16
0
0
Raft 与 Paxos的区别

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

cloud-coder
2016/07/14
1K
0
Raft和它的三个子问题

这篇文章来源于一个经常有人困惑的问题:Quorum与Paxos,Raft等一致性协议有什么区别,这个问题的答案本身很简单:一致性协议大多使用了Quorum机制,但仅仅有Quorum(R+W>N)机制是保证不了一致...

CatKang
2017/07/16
0
0
TIDB 架构及分布式协议Paxos和Raft对比

近来newsql大热,尤以TIDB最火,pingcap不断打磨TiDB,现如今版本已经迭代到3.0,产品已经基本趋于成熟。 对于TiDB,整体架构图如下图所示 是由四个模块组成,TiDB Server,PD Server,TiKV ...

liuminkun
04/11
0
0
iNexus 0.13 发布,基于 Raft 的分布式协调组件

iNexus (简称ins) 是一个基于Raft协议实现的高可用的分布式Key-Value数据库,支持数据变更通知(Watch)和分布式锁,可用于大型分布式系统的协调工作 猛击:https://github.com/baidu/ins 简...

fxsjy
2016/02/01
1K
1

没有更多内容

加载失败,请刷新页面

加载更多

 介绍一款优秀的通用管理权限快速开发框架

这是一套以权限管理为主的轻量化快速开发框架,配置有流程、专业表单、权限、app、企业微信等基础功能模块,在开发通用软件的效率上很有优势。 软件平台常用研发需求分析 《那些年我们一起做...

我想造火箭
30分钟前
8
0
ElasticDL:蚂蚁金服开源基于 TensorFlow 的弹性分布式深度学习系统

9 月 11 日,蚂蚁金服在2019谷歌开发者大会上海站上开源了 ElasticDL 项目,这是业界首个基于 TensorFlow 实现弹性深度学习的开源系统。 开源地址为:https://github.com/sql-machine-learni...

SOFAStack
37分钟前
6
0
CSS--渐变

一、什么是渐变 多种颜色平缓变化的一种显示效果 二、渐变的主要元素 色标:一种颜色,以及出现的位置,一个渐变至少两种色标 三、渐变的分类 1、线性渐变 以直线的方式来填充渐变色 backgr...

wytao1995
52分钟前
13
0
Java通过模板生成PDF再转换为图片

1、添加maven依赖 <dependency> <groupId>com.itextpdf</groupId> <artifactId>itextpdf</artifactId> <version>5.5.13.1</version></dependency><dependency> <g......

醉美閑聖
59分钟前
7
0
SpringBoot-MVC RequestBody中LocalDateTime的自适应配置

请求的json报文中可能会出现 一下几种: ['2019-01-01','2019-01-01 12:03:34','20190101120334'] 但是接收的Request实体类日期字段是LocalDateTime类型 LocalDateTime applyDate; 希望的情况......

汉堡OSC
今天
17
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部