您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

共识算法Raft为什么这么流行,及原理解析

时间:2020-01-02 16:50:10  来源:  作者:

拜占庭将军问题是分布式领域最复杂、最严格的容错模型。但在日常工作中使用的分布式系统面对的问题不会那么复杂,更多的是计算机故障挂掉了,或者网络通信问题而没法传递信息,这种情况不考虑计算机之间互相发送恶意信息,极大简化了系统对容错的要求,最主要的是达到一致性。

所以将拜占庭将军问题根据常见的工作上的问题进行简化:假设将军中没有叛军,信使的信息可靠但有可能被暗杀的情况下,将军们如何达成一致性决定?

对于这个简化后的问题,有许多解决方案,第一个被证明的共识算法是 Paxos,由拜占庭将军问题的作者 Leslie Lamport 在1990年提出,最初以论文难懂而出名,后来这哥们在2001重新发了一篇简单版的论文 Paxos Made Simple,然而还是挺难懂的。

因为 Paxos 难懂,难实现,所以斯坦福大学的教授在2014年发表了新的分布式协议 Raft。与 Paxos 相比,Raft 有着基本相同运行效率,但是更容易理解,也更容易被用在系统开发上。

针对简化版拜占庭将军问题,Raft 解决方案类比

我们还是用拜占庭将军的例子来帮助理解 Raft。

假设将军中没有叛军,信使的信息可靠但有可能被暗杀的情况下,将军们如何达成一致性决定?

Raft 的解决方案大概可以理解成 先在所有将军中选出一个大将军,所有的决定由大将军来做。选举环节:比如说现在一共有3个将军 A, B, C,每个将军都有一个随机时间的倒计时器,倒计时一结束,这个将军就会把自己当成大将军候选人,然后派信使去问其他几个将军,能不能选我为总将军?假设现在将军A倒计时结束了,他派信使传递选举投票的信息给将军B和C,如果将军B和C还没把自己当成候选人(倒计时还没有结束),并且没有把选举票投给其他,他们把票投给将军A,信使在回到将军A时,将军A知道自己收到了足够的票数,成为了大将军。在这之后,是否要进攻就由大将军决定,然后派信使去通知另外两个将军,如果在一段时间后还没有收到回复(可能信使被暗杀),那就再重派一个信使,直到收到回复。

故事先讲到这里,希望不做技术方面的朋友可以大概能理解 Raft 的原理,下面从比较技术的角度讲讲 Raft 的原理。

1. Raft 节点状态

从拜占庭将军的故事映射到分布式系统上,每个将军相当于一个分布式网络节点,每个节点有三种状态:Follower,Candidate,Leader,状态之间是互相转换的,可以参考下图,具体的后面说。

共识算法Raft为什么这么流行,及原理解析

 

每个节点上都有一个倒计时器 (Election Timeout),时间随机在 150ms 到 300ms 之间。有几种情况会重设 Timeout:

  1. 收到选举的请求
  2. 收到 Leader 的 Heartbeat (后面会讲到)

在 Raft 运行过程中,最主要进行两个活动:

  1. 选主 Leader Election
  2. 复制日志 Log Replication

2. 选主 Leader Election

2.1 正常情况下选主

共识算法Raft为什么这么流行,及原理解析

 

假设现在有如图5个节点,5个节点一开始的状态都是 Follower。

共识算法Raft为什么这么流行,及原理解析

 

在一个节点倒计时结束 (Timeout) 后,这个节点的状态变成 Candidate 开始选举,它给其他几个节点发送选举请求 (RequestVote)

共识算法Raft为什么这么流行,及原理解析

 

其他四个节点都返回成功,这个节点的状态由 Candidate 变成了 Leader,并在每个一小段时间后,就给所有的 Follower 发送一个 Heartbeat 以保持所有节点的状态,Follower 收到 Leader 的 Heartbeat 后重设 Timeout。

这是最简单的选主情况,只要有超过一半的节点投支持票了,Candidate 才会被选举为 Leader,5个节点的情况下,3个节点 (包括 Candidate 本身) 投了支持就行。

2.2 Leader 出故障情况下的选主

共识算法Raft为什么这么流行,及原理解析

 

一开始已经有一个 Leader,所有节点正常运行。

共识算法Raft为什么这么流行,及原理解析

 

Leader 出故障挂掉了,其他四个 Follower 将进行重新选主。

共识算法Raft为什么这么流行,及原理解析

 


共识算法Raft为什么这么流行,及原理解析

 


共识算法Raft为什么这么流行,及原理解析

 

4个节点的选主过程和5个节点的类似,在选出一个新的 Leader 后,原来的 Leader 恢复了又重新加入了,这个时候怎么处理?在 Raft 里,第几轮选举是有记录的,重新加入的 Leader 是第一轮选举 (Term 1) 选出来的,而现在的 Leader 则是 Term 2,所有原来的 Leader 会自觉降级为 Follower

共识算法Raft为什么这么流行,及原理解析

 

2.3 多个 Candidate 情况下的选主

共识算法Raft为什么这么流行,及原理解析

 

假设一开始有4个节点,都还是 Follower。

共识算法Raft为什么这么流行,及原理解析

 

有两个 Follower 同时 Timeout,都变成了 Candidate 开始选举,分别给一个 Follower 发送了投票请求。

共识算法Raft为什么这么流行,及原理解析

 

两个 Follower 分别返回了ok,这时两个 Candidate 都只有2票,要3票才能被选成 Leader。

共识算法Raft为什么这么流行,及原理解析

 

两个 Candidate 会分别给另外一个还没有给自己投票的 Follower 发送投票请求。

共识算法Raft为什么这么流行,及原理解析

 

但是因为 Follower 在这一轮选举中,都已经投完票了,所以都拒绝了他们的请求。所以在 Term 2 没有 Leader 被选出来。

共识算法Raft为什么这么流行,及原理解析

 

这时,两个节点的状态是 Candidate,两个是 Follower,但是他们的倒计时器仍然在运行,最先 Timeout 的那个节点会进行发起新一轮 Term 3 的投票。

共识算法Raft为什么这么流行,及原理解析

 

两个 Follower 在 Term 3 还没投过票,所以返回 OK,这时 Candidate 一共有三票,被选为了 Leader。

共识算法Raft为什么这么流行,及原理解析

 

如果 Leader Heartbeat 的时间晚于另外一个 Candidate timeout 的时间,另外一个 Candidate 仍然会发送选举请求。

共识算法Raft为什么这么流行,及原理解析

 

两个 Follower 已经投完票了,拒绝了这个 Candidate 的投票请求。

共识算法Raft为什么这么流行,及原理解析

 

Leader 进行 Heartbeat, Candidate 收到后状态自动转为 Follower,完成选主。

以上是 Raft 最重要活动之一选主的介绍,以及在不同情况下如何进行选主。

3. 复制日志 Log Replication

3.1 正常情况下复制日志

Raft 在实际应用场景中的一致性更多的是体现在不同节点之间的数据一致性,客户端发送请求到任何一个节点都能收到一致的返回,当一个节点出故障后,其他节点仍然能以已有的数据正常进行。在选主之后的复制日志就是为了达到这个目的。

共识算法Raft为什么这么流行,及原理解析

 

一开始,Leader 和 两个 Follower 都没有任何数据。

共识算法Raft为什么这么流行,及原理解析

 

客户端发送请求给 Leader,储存数据 “sally”,Leader 先将数据写在本地日志,这时候数据还是 Uncommitted (还没最终确认,红色表示)

共识算法Raft为什么这么流行,及原理解析

 

Leader 给两个 Follower 发送 AppendEntries 请求,数据在 Follower 上没有冲突,则将数据暂时写在本地日志,Follower 的数据也还是 Uncommitted。

共识算法Raft为什么这么流行,及原理解析

 

Follower 将数据写到本地后,返回 OK。Leader 收到后成功返回,只要收到的成功的返回数量超过半数 (包含Leader),Leader 将数据 “sally” 的状态改成 Committed。( 这个时候 Leader 就可以返回给客户端了)

共识算法Raft为什么这么流行,及原理解析

 

Leader 再次给 Follower 发送 AppendEntries 请求,收到请求后,Follower 将本地日志里 Uncommitted 数据改成 Committed。这样就完成了一整个复制日志的过程,三个节点的数据是一致的

3.2 Network Partition 情况下进行复制日志

在 Network Partition 的情况下,部分节点之间没办法互相通信,Raft 也能保证在这种情况下数据的一致性。

共识算法Raft为什么这么流行,及原理解析

 

一开始有 5 个节点处于同一网络状态下。

共识算法Raft为什么这么流行,及原理解析

 

Network Partition 将节点分成两边,一边有两个节点,一边三个节点。

共识算法Raft为什么这么流行,及原理解析

 

两个节点这边已经有 Leader 了,来自客户端的数据 “bob” 通过 Leader 同步到 Follower。

共识算法Raft为什么这么流行,及原理解析

 

因为只有两个节点,少于3个节点,所以 “bob” 的状态仍是 Uncommitted。所以在这里,服务器会返回错误给客户端

共识算法Raft为什么这么流行,及原理解析

 

另外一个 Partition 有三个节点,进行重新选主。客户端数据 “tom” 发到新的 Leader,通过和上节网络状态下相似的过程,同步到另外两个 Follower。

共识算法Raft为什么这么流行,及原理解析

 


共识算法Raft为什么这么流行,及原理解析

 


共识算法Raft为什么这么流行,及原理解析

 

因为这个 Partition 有3个节点,超过半数,所以数据 “tom” 都 Commit 了。

共识算法Raft为什么这么流行,及原理解析

 

网络状态恢复,5个节点再次处于同一个网络状态下。但是这里出现了数据冲突 “bob" 和 “tom"

共识算法Raft为什么这么流行,及原理解析

 

三个节点的 Leader 广播 AppendEntries

共识算法Raft为什么这么流行,及原理解析

 

两个节点 Partition 的 Leader 自动降级为 Follower,因为这个 Partition 的数据 “bob” 没有 Commit,返回给客户端的是错误,客户端知道请求没有成功,所以 Follower 在收到 AppendEntries 请求时,可以把 “bob“ 删除,然后同步 ”tom”,通过这么一个过程,就完成了在 Network Partition 情况下的复制日志,保证了数据的一致性。

共识算法Raft为什么这么流行,及原理解析

 

小总结

Raft 是能够实现分布式系统强一致性的算法,每个系统节点有三种状态 Follower,Candidate,Leader。实现 Raft 算法两个最重要的事是:选主和复制日志

参考链接:
Raft 官网:https://raft.github.io/

Raft 原理动画 (推荐看看):http://thesecretlivesofdata.com/raft/

Raft 算法解析图片来源:http://www.infoq.com/cn/articles/coreos-analyse-etcd

 

专注于技术热点大数据,人工智能JAVAPython、 C 、GO、JavaScript等语言最新前言技术,及业务痛点问题分析,请关注【编程我最懂】共同交流学习。



Tags:共识算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
前文《理解 Paxos》只包含伪代码,帮助了理解但又不够爽,既然现在都讲究 Talk is cheap. Show me the code.这次就把文章中的伪代码用 Go 语言实现出来,希望能帮助各位朋友更直...【详细内容】
2020-12-15  Tags: 共识算法  点击:(116)  评论:(0)  加入收藏
我们先从常见的拜占庭将军问题中理解一下什么是共识。 拜占庭将军问题 拜占庭位于如今的土耳其的伊斯坦布尔,是东罗马帝国的首都。由于当时拜占庭罗马帝国国土辽阔,为了防御目...【详细内容】
2020-11-11  Tags: 共识算法  点击:(81)  评论:(0)  加入收藏
拜占庭将军问题是分布式领域最复杂、最严格的容错模型。但在日常工作中使用的分布式系统面对的问题不会那么复杂,更多的是计算机故障挂掉了,或者网络通信问题而没法传递信息,这...【详细内容】
2020-01-02  Tags: 共识算法  点击:(64)  评论:(0)  加入收藏
摘 要 共识算法是区块链技术的核心要素, 也是近年来分布式系统研究的热点. 本文系统性地梳理和讨论了区块链发展过程中的 32 种重要共识算法, 介绍了传统分布式一致性算法...【详细内容】
2019-11-14  Tags: 共识算法  点击:(132)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(11)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(22)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(14)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯·奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(40)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条