前言
上篇文章说解决问题要分而治之,先把分片的问题解决了再考虑多个副本的一致性问题。那么什么是一致性问题?
因为同一数据存在多个副本,在并发的众多客户端读/写请求下,如何维护数据一致性视图非常重要,即在存储系统外部使用者看起来即使是多个副本数据,其表现也和单份数据一样。
简单来说,要使多个副本的数据一致,需要通过某种一致性协议来对副本进行更新。如果不按照某种一致性协议进行更新,数据就可能会出现不一致的情况。
比方说,两个副本A,B,有两个客户端分别对A,B进行不同的更新,这样两个副本的数据显然就不一致了。假如有某一种协议,多个客户端对副本的更新,只能在一个副本上更新,然后这个副本把更新操作同步到其它副本,成功之后再返回给客户端,这样就有可能实现多个副本的一致性。今天要学习的Raft协议就是类似这样的一种一致性协议。
当然,数据的一致性也可以分为强一致性和弱一致性,Raft协议是一种强一致性协议。
Raft协议概述
Raft 是一种实现了分布式一致性的协议。假设我们有三个副本节点,来看一下Raft 协议如何工作:
节点状态
Raft 协议中的节点有三种状态:
- Follower
- Candidate
- Leader
在下面的图形用,分别用无边框,虚线边框,实线边框表示这三种状态。
领导选举
在开始阶段,所有节点都处于Follower 状态,如下图所示:
如果Follower 没有收到Leader 发过来的信息,则可变成Candidate:
然后Candidate 向其它节点发送投票自己为Leader 的请求,如果得到了大多数节点的投票响应,则成为Leader:
这个过程称为领导选举,选出Leader 之后,系统的所有变更操作都需要通过Leader 节点。
日志复制
假设某个客户端(绿色圈圈)对某个数据进行更新:
所有的变更请求先发送到Leader 节点,每个变更操作都会作为一条日志记录保存在Leader 节点上。
目前日志记录处于未提交状态,所以节点的数据目前还没有更新。
要提交日记记录,首先得先把日志记录复制到其它Follower 节点:
Leader 节点等待大多数节点已经完成日志复制的响应,然后才会把日志记录提交,Leader 节点的数据才会更新:
然后Leader 节点通知Follower 节点日志记录已经提交,Follower 节点也进行提交,数据达到一致性状态。
这个过程就称为日志复制。
领导选举
Raft 协议中有两个超时设置用于领导选举:
- 选举超时:每个Follower 都会等待一个超时时间,然后就可以成为 Candidate,这个超时时间就称为选举超时。选举超时时间一般随即分配为150ms到300ms之间。
如上图所示,节点C 将会先到达超时时间,成为Candidate 然后开始一个新的选举任期(election term) :
如上图所示,成为Candidate 的节点会将自己的term 加1,然后给自己投票,再发送请求投票信息到其他节点:
接收请求的节点在这个term 内如果还没有投票,则会将选票投给这个Candidate,然后重置自身的超时时间:
一旦Candidate 收到了大多数的投票,那么它将成为Leader 。
然后Leader 会发送Append Entries
消息给Follower,发送这个消息的时间间隔就是心跳超时(heartbeat timeout)。
- 心跳超时: Leader 发送Append Entries信息的时间间隔。
Followers 将会响应每一条Append Entries 消息,然后重置自身的超时时间:
这个选举任期将会持续到一个Follower没有收到Leader 的心跳信息,然后成为Candidate。也就是说,Leader 会在任期期间不断发送心跳信息来重置其他的Follower的超时时间,让他们没有机会成为Candidate。只有当Leader 挂掉了,其他Follower 才有机会成为Candidate 进行新的选举。所以Raft 协议正是用选举超时和心跳超时
我们来看一下Leader 挂了,然后开始一个新的选举:
上图中,当Leader 挂掉之后,剩余的两个Follower 将会等待超时然后成为Candidate。由上面的超时时间可以看出,A 节点将会先超时,然后成为Candidate 将自己的term 加1,然后给自己投票,再发送请求投票信息到其他节点。当收到节点B 的投票请求之后成为新的Leader :
需要得到大多数节点的投票才能成为Leader 保证了每个任期只有一个节点能成为Leader 。如果两个节点同时成为Candidate ,那么他们可能会得到一样多的投票,这种情况下将继续等待下一个超时,然后重新发起投票,直到选出一个Leader 为止。
日志复制
当选举出了新的Leader 之后,需要将系统中的所有变化复制到其他节点。这跟发送心跳信息的方式一样,也是通过发送Append Entries
消息来完成这一动作,只是心跳信息中没有日志信息。我们来看一下这个过程:
首先,客户端发送更新操作到Leader 节点:
变更会先被追加到Leader 节点的日志,然后在发送下一个心跳信息的时候将变更信息发送到Follower :
当大多数Follower 确认这个信息,那么该变更日志将会被提交,然后Leader 将会响应给客户端:
然后Leader 节点会在下一个心跳信息时通知Follower 节点日志记录已经提交,Follower 节点也进行提交,数据达到一致性状态。
网络分区
Raft 在面对网络分区的时候也能保持一致性。
假设A,B节点与C,D,E 节点形成了网络分区。C,D,E节点由于收不到原Leader B的心跳信息,那么他们之间将会选举出一个新的Leader ,但是这个Leader 的term 跟原来Leader B 的 term不一样,这时就会存在两个不同term 的Leader:
现在,假设有两个客户端同时更新不同的Leader,客户端1将更新请求发送到Leader B 将某个值设置为3,Leader B 不能复制到大多数的节点(因为只有1个Follower节点),所以这个更新日志是处于未提交状态。
客户端2将某个值设置为8,因为它将会得到大多数节点的响应,所以这个更新操作能够成功:
现在,假设网络分区问题已经修复,这时节点B 会收到比他更高任期(term) 的信息,然后就会变成Follower:
节点A和B 未提交的日志记录将会被回滚然后匹配新Leader 的日志:
现在,日志在集群中达成一致性。
总结
本文只是介绍了Raft 协议的大致流程,并没有关注很多细节问题。主要从领导选举和日志复制两个方面分析了Raft 协议的工作过程,领导选举重点是要了解两个超时时间,日志复制是Master-Slave模式,后续的日志一致性维护由领导者来完成。
相关推荐
raft算法,原版论文,英文版 摘要 Raft 是一种用来管理日志复制的一致性算法。它和 Paxos 的性能和功能是一样的,但是它和 Paxos 的结构不一样;这使得 Raft 更容易理解并且更易于建立实际的系统。为了提高理解性,...
Raft 是用来管理复制日志(replicated log)的一致性协议。它跟 multi-Paxos 作用相同,效率也相当,但是它的组织结构跟 Paxos 不同。这使得 Raft 比 Paxos 更容易理解并且更容易在工程实践中实现。为了使 Raft 协议...
Raft是一种用于替代Paxos的共识算法。相比于Paxos,Raft的目标是提供更清晰的逻辑分工使得算法本身能被更好地理解,同时它安全性更高,并能提供一些额外的特性。[1][2]:1Raft能为在计算机集群之间部署有限状态机提供...
Raft 是一种用来管理日志复制的一致性算法。它和 Paxos 的性能和功能是一样的,但是它和 Paxos 的结构不一样;这使得 Raft 更容易理解并且更易于建立实际的系统。为了提高理解性,Raft 将一致性算法分为了几个部分,...
用于加载steam游戏raft木筏求生mod启动器。 本启动器包含mod下载网站! 启动器官网在国外,正常下载会很缓慢,需要的自取。
Raft论文解析中文版
python库。 资源全名:tf-raft-0.1.4.tar.gz
因此,将ylene衍生物连接到可聚合的乙烯基上,并在RAFT条件(可逆加成断裂链转移)下分别与苯乙烯和甲基丙烯酸甲酯共聚,以得到尺寸在40 nm或更小且分子量分布窄的荧光ONP。多分散性PD为1.1或更低。
raft, Raft协议的C 实现,BSD许可协议 Raft协议的C 实现,BSD许可协议。有关完整文档,请参阅 raft.h 。请参见 ticketd 了解这里库的实际使用情况。网络已经超出这里项目范围。 实现者将需要完成所有的管道。 库不...
raft, Raft协议的Golang实现 raft raft是管理复制日志并可以与FSM一起管理复制状态机的转到库。 它是一个提供一致性协议的库。当复制状态机是许多分布式系统的关键组件时,这种库的使用情况非常接近。 它们支持构建...
raft 是一种类似于 paoxs 的分布式算法,相对于 paxos 算法, raft 更容易于理解以及实现,这也是一种典型的 半数协议算法 。这里不详细介绍 raft 算法
raft, Raft分布式一致协议的实现 raft这是一个实现了 Raft的consensus协议。 这对的benbjohnson实现有很大的影响。 它专注于提供一个干净和可用的API,以及良好的内部结构。 用法Raft网络中的node 由一个服务器的...
Raft算法讲解---关于在分布式系统下的Raft算法自我理解。
图解分布式系统raft协议-完整版 图解分布式系统raft协议-完整版
基于Raft分布式一致性协议实现的局限及其对数据库的风险.docx
Raft一致性协义手写Demo,就简单的写了个逻辑思想,帮助学习使用,不喜欢不要下载。。。。。。。。
Raft - 基于共识的分布式数据库协同算法及其在 Neo4j 集群中的实现.pdf
改进型RAFT聚合法合成低分子量PAA的研究 ,余志勇,魏玉峰,提出了一种类似于RAFT(可逆加成断裂链转移)聚合的制备低分子量PAA(聚丙烯酸)的新方法。该方法以偶氮二异丁腈做引发剂,以异丙�