写点什么

一致性算法 Raft 简述

用户头像
flyer0126
关注
发布于: 2020 年 05 月 28 日
一致性算法 Raft 简述

一、Raft算法概述

当我们只有一个服务节点的情况下,是不存在节点共识的问题的,当存在多个不同服务节点时,才会引入分布式一致性的问题。

Raft是一种实现分布式共识的协议。所谓共识,就是多个节点对某个事情达成一致的看法,即使是在部分节点故障、网络延时、网络分割的情况下。

主要应用场景:

  • Redis Sentinel的选举Leader

  • Etcd 主要是共享配置和服务发现,实现一致性使用了Raft算法

  • 加密货币(比特币、区块链)的共识算法

主要解决什么问题?

分布式存储系统通常通过维护多个副本来提高系统的可用性,带来的代价就是分布式存储系统的核心问题之一:维护多个副本的数据一致性。

 

二、Raft算法实现流程

为了提高理解性,Raft将一致性算法分为了几个部分,包括领导选取(leader selection)、日志复制(log replication)、安全(safety),并且使用了更强的一致性来减少了必须需要考虑的状态。

本文通过一个小故事做示例,来便于大家快速理解。

2.1 Leader选举

为了便于后期统一调配资源及管理需要,现需要从三名同学中选举出一名小组Leader。

A觉得自己有能力做好Leader职务,就向B、C说“来投票给我,我想当Leader”,这时候A成了候选人,并为自己事先投了一票。

1)假如B、C之前都没有想过要自己当Leader,那就说“好吧,投给你” → A获得3张选票,当选Leader

2)假如B之前想过自己当Leader,B投了自己一票 而C投了一票给A → A获得2张选票(3人中已超过半数),当选Leader

3)假如B、C都已经把票投给了自己 → A、B、C各获得自己的一票,选举失败重新发起

4)假如B之前想过自己当Leader,而且C已经把票投给了B → B获得2张选票(3人中已超过半数),当选Leader

Leader选举示意



从以上选举流程可以发现,一个节点任一时刻肯定处于以下三状态之一:

  • Leader(领导者)

  • Follower(跟随者)

  • Candidate(候选人)



这三个状态的转移过程如下图所示:



选举过程

第一步:Follower成为Candidate

如果Follower听不到Leader的意见,他们就可以成为Candidate

第二步:候选人争取票

投自己一票,并发送投票请求到其他节点,节点收到请求后进行回应

第三步:等待其他节点回复

如果候选人得到了超半数的节点的投票(包含自己的一票),它就成为Leader

如果候选人被告知Leader已产生,则自行切换为Follower

一段时间内没有收到超半数投票,保持候选人状态,重新发起选举

第四步:候选人 赢得选举 

新Leader会立刻给所有节点发消息,避免其他节点触发新的选举。

2.2 日志同步

在经过上述2.1 的Leader选举之后,已经选定了小组Leader,这里我们假定A已当选Leader。可以承担一些对接方同学(称为Client 端)提出的操作任务了。

规定每次需求对接,必须要经过小组Leader才可以。那员工提出操作请求,Leader接收到后记录下来,同时向组内其他同学进行同步,直到其他同学都确认了此需求后Leader才会确认操作并同步执行结果到员工(Follower节点)。

请求处理日志同步



Log Replication(日志复制)

经过Leader选举流程,产生了新的Leader节点,系统的所有变更都要通过Leader节点来实现。

第一步:Leader追加日志项(append log entry)

系统的每个更改都作为一个entry 添加到节点的日志中

第二步:Leader并行发出Append Entries RPC,并等待响应

Leader会一直等到超半数节点都写入entry,Leader节点提交,然后Leader通知Follower entry已提交。

第三步:Leader得到大多数回应,向状态机应用entry

状态机:可理解为一个确定的应用程序,所谓确定是指只要是相同的输入,那么任何状态机都会计算出相同地输出。

第四步:Leader回复Client,同时通知Follower应用log

目前集群已就系统状态达成了共识



log-based replicated state machine示意图:



关于应用过程中的几个问题

Q1:假如Client 请求访问到了Follower节点怎么办?

解答:Follower节点会转发请求到Leader节点。

Q2:当Leader与Follower的日志不一致,需要如何处理?

解答:

  1)Leader通过强制Followers复制它的日志来处理日志的不一致,Followers上的不一致的日志会被Leader的日志覆盖。

  2)Leader为了使Followers的日志同自己的一致,Leader需要找到Followers同它的日志一致的地方,然后覆盖Followers在该位置之后的条目。

  3)Leader会从后往前试,每次AppendEntries失败后尝试前一个日志条目,直到成功找到每个Follower的日志一致位点,然后向后逐条覆盖Followers在该位置之后的条目。

2.3 安全性保障

为了保证团队运行的稳定,有几个默认的要求:

2.3.1 选举安全

即任一任期内最多一个leader被选出。假如系统中同时有多于一个leader,被称之为脑裂(brain split),这会导致数据的覆盖丢失。

一个团队某个时期内仅允许存在一个Leader(选举失败情况特殊情况除外),否则多个Leader同时处理需求发号施令,容易造成团队内步调不一致情况。



在raft中,两点保证了这个属性:

1)一个节点某一任期内最多只能投一票;

2)只有获得majority投票的节点才会成为leader。

2.3.2 Log 匹配完整性

同一团队内两名同学假如目前手头负责的事务是一致的,那之前他们的工作记录应该也是一致的。即:相同的初始状态+相同的操作=相同的结束状态



Raft日志同步结论:

1)如果不同日志中的两个条目有着相同的索引和任期号(term),则它们所存储的命令是相同的。

2)如果不同日志中的两个条目有着相同的索引和任期号(term),则它们之前的所有条目都是完全一样的。

2.3.3 leader数据完整性

团队内后继的leader,肯定应该知晓这个团队之前的工作内容,因为所有Leader任期内的工作记录是会做交接的。



如果一个log entry 在某个任期被提交,那么这条log一定会出现在所有更高term的leader的日志里面。

Raft日志覆盖规则:

1)一个日志被复制到majority节点才算committed

2)一个节点得到majority的投票才能成为leader,而节点A给节点B投票的其中一个前提是,B的日志不能比A的日志旧。

三、总结

所有的算法实现原理,其实都是真实社会工作模式的影射,联系生活中的实际案例来理解复杂的一致性算法,可以让我们达到事半功倍的效果。

本文是让大家对raft协议有一个简单了解入门,如有兴趣去更深入了解,推荐给大家两个不错的链接:

1)Raft可视化测试以及各语言版本实现的Raft:https://raft.github.io/

2)Raft算法-动画演示(很好的入门教程):http://thesecretlivesofdata.com/raft/



发布于: 2020 年 05 月 28 日阅读数: 160
用户头像

flyer0126

关注

做难事者,必有所得! 2018.02.26 加入

「架构精进之路」公号作者 坚持原创总结、沉淀和分享,希望能带给大家一些引导和启发,坚信做难事者,必有所得!

评论

发布
暂无评论
一致性算法 Raft 简述