关键词:
文章目录
Raft 算法
Raft 算法概念
Raft 是一种分布式一致性算法。Raft 出现之前,Paxos 一直是分布式一致性算法的标准。
Paxos 难以理解,更难以实现。Raft 的设计目标是简化 Paxos,使得算法既容易理解,也容易实现。
Paxos 和 Raft 都是分布式一致性算法,这个过程如同投票选举领袖(Leader),参选者(Candidate)需要说服大多数投票者(Follower)投票给他,一旦选举出领袖,就由领袖发号施令。Paxos 和 Raft 的区别在于选举的具体过程不同。
Paxos 和 Raft 都是分布式一致性算法,这个过程如同投票选举领袖(Leader),参选者(Candidate)需要说服大多数投票者(Follower)投票给他,一旦选举出领袖,就由领袖发号施令。Paxos 和 Raft 的区别在于选举的具体过程不同。
Raft 可以解决分布式 CAP 理论中的 CP,即 一致性(C:Consistency) 和 分区容忍性(P:Partition Tolerance),并不能解决 可用性(A:Availability) 的问题。
Raft 角色
一个 Raft 集群包含若干节点,Raft 把这些节点分为三种状态:Leader、 Follower、Candidate,每种状态负责的任务也是不一样的。正常情况下,集群中的节点只存在 Leader 与 Follower 两种状态。
- Leader(领导者) :负责日志的同步管理,处理来自客户端的请求,与Follower保持heartBeat的联系;
- Follower(追随者) :响应 Leader 的日志同步请求,响应Candidate的邀票请求,以及把客户端请求到Follower的事务转发(重定向)给Leader;
- Candidate(候选者) :Leader选举过程中的临时角色。负责选举投票,集群刚启动或者Leader宕机时,状态为Follower的节点将转为Candidate并发起选举,选举胜出(获得超过半数节点的投票)后,从Candidate转为Leader状态。
Raft 算法流程
通常,Raft 集群中只有一个 Leader,其它节点都是 Follower。Follower 都是被动的,不会发送任何请求,只是简单地响应来自 Leader 或者 Candidate 的请求。Leader 负责处理所有的客户端请求(如果一个客户端和 Follower 联系,那么 Follower 会把请求重定向给 Leader)。
针对以上分析,可以将整个 Raft 算法分解为三部分:
Leader 选举:当 Leader 宕机或者集群初创时,一个新的 Leader 需要被选举出来;
Leader 选举要点如下:
-
只有一个 Server 能作为 Leader
-
一旦此 Server 崩溃,选举新 Leader
执行操作(日志复制):Leader 接收来自客户端的请求并将其以日志条目的形式复制到集群中的其它节点,并且强制要求其它节点的日志和自己保持一致;
日志复制要点如下:
-
由 Leader 执行自己的日志记录
-
将日志复制到其它 Server,会覆盖掉不一致的部分
-
多数派记录日志成功,Leader 才能执行命令,向客户端返回结果
确保安全:如果有任何的服务器节点已经应用了一个确定的日志条目到它的状态机中,那么其它服务器节点不能在同一个日志索引位置应用一个不同的指令。
确保安全要点如下:
-
保证日志记录的一致性
-
拥有最新日志的 Server 才能成为 Leader
Raft 算法原理
角色关系
Follower 只响应来自其他服务器的请求。在一定时限内,如果 Follower 接收不到消息,就会转变成 Candidate,并发起选举。
Candidate 向 Follower 发起投票请求,如果获得集群中半数以上的选票,就会转变为 Leader。
在一个 Term(任期,下面讲) 内,Leader 始终保持不变,直到下线了。Leader 需要周期性向所有 Follower 发送心跳消息,以阻止 Follower 转变为 Candidate。
任期原理
Raft 把时间分割成任意长度的 任期(Term),任期用连续的整数标记。每一段任期从一次选举开始。Raft 保证了在一个给定的任期内,最多只有一个领导者。
任期(Term)与领导者(Leader)选举过程中会出现两种情况:
-
如果选举成功,Leader 会管理整个集群直到任期结束。
-
如果选举失败,那么这个任期就会因为没有 Leader 而结束。
例如下图,存在没有Leader和有Leader两种强开
并且不同服务器节点观察到的任期转换状态可能不一样:
-
服务器节点可能观察到多次的任期转换。
-
服务器节点也可能观察不到任何一次任期转换。
任期在 Raft 算法中充当逻辑时钟的作用,使得服务器节点可以查明一些过期的信息(比如过期的 Leader)。每个服务器节点都会存储一个当前任期号,这一编号在整个时期内单调的增长。当服务器之间通信的时候会交换当前任期号。
- 如果一个服务器的当前任期号比其他人小,那么他会更新自己的编号到较大的编号值。
- 如果一个 Candidate 或者 Leader 发现自己的任期号过期了,那么他会立即恢复成跟随者状态。
- 如果一个节点接收到一个包含过期的任期号的请求,那么他会直接拒绝这个请求。
数据可视化的应用场景越来越广泛,数据可以呈现为更多丰富的可视化形式,使用户能够更加轻易、便捷的获取并理解数据传达的信息。
通信原理
Raft 算法中服务器节点之间的通信使用 远程过程调用(RPC)。
基本的一致性算法只需要两种RPC:
- RequestVote RPC - 请求投票 RPC,由 Candidate 在选举期间发起。
- AppendEntries RPC - 附加条目 RPC,由 Leader 发起,用来复制日志和提供一种心跳机制。
图解算法流程
图解学习网站:https://raft.github.io/raftscope/index.html
选举过程
-
Leader 会不断向选民发送 AppendEntries 请求,证明自己活着
-
选民收到 Leader AppendEntries 请求后会重置自己的 timeout 时间
- 选民收不到 AppendEntries 请求超时后,转换角色为候选者,并将任期加1,发送 RequestVote 请求,推选自己
- 选民收到第一个 RequestVote,会向该候选者投一票,这样即使有多个候选者,必定会选出一个 Leader,选票过半即当选,如果落选会变回选民
-
每一任期最多有一个 Leader,但也可能没有(选票都不过半的情况,需要再进行一轮投票,timeout 在 T~2T 间随机)
-
任期由各个 server 自己维护即可,无需全局维护,在超时后加1,在接收到任意消息时更新为更新的任期,遇到更旧的任期,视为错误
执行操作过程(日志复制)
- 客户端发送命令至 Leader
- Leader 将命令写入日志(S1虚框),并向所有选民发送 AppendEntries 请求
- 多数派通过后,执行命令(即提交,S1虚框变实),此时就可以向客户端返回结果
- 在后续的 AppendEntries 请求中通知选民,选民执行命令(即提交,S2,S3,S4,S5虚框变实)
- 如果选民挂了,则 Leader 会不断尝试,待到选民重启,会将其缺失的日志陆续补齐
确保安全
Leader 日志的完整性
- Leader 被认为拥有最完整的日志
- 一旦 Leader 完成了某条命令提交,那么未来的 Leader 也必须存有该条命令提交信息
- 投票时,会将候选者最新的
<Term,Index>
随 RequestVote 请求发送,如果候选者的日志还没选民的新,则投否决票
- 图中 S2 如果超时,发起选举请求,其它服务器只会对它投否决票,因为它的 Index 比其它人都旧
- 图中 S5 如果超时,发起选举请求,其它服务器也不会选它,因为他的 Term 太旧
选民日志的一致性
-
以 Leader 为准,对选民的日志进行补充或覆盖
-
AppendEntries 请求发送时会携带最新的
<Term,Index,Command>
以及上一个的<Term,Index>
-
如果选民发现上一个的
<Term,Index>
能够对应上则成功,否则失败,继续携带更早的信息进行比对
- 图中 Leader 发送了
<3,4,Command>
和<2,3>
给 follower,follower 发现<2,3>
能够与当前最新日志对应,这时直接执行<3,4,Command>
即可
- 图中 Leader 发送了
<3,4,Command>
和<2,3>
给 follower,follower 发现<2,3>
不能与当前最新日志对应,会央求 Leader 发送更早日志
- Leader 这次发送了
<3,4,Command>
,<2,3,Command>
,<1,2>
给 follower,follower 发现<1,2>
能够与当前最新日志对应,这时补全<3,4,Command>
,<2,3,Command>
即可
分布式共识算法——gossip协议(图解)
文章目录Gossip协议Gossip协议概念Gossip协议工作流程图解Gossip协议原理消息类型通信方式Gossip协议优点Gossip协议Gossip协议概念说到共识算法,大家首先想到的应该都是Raft、Paxos、Zab算法这类理解起来比较困难的强一致性算法。... 查看详情
分布式共识算法——gossip协议(图解)
文章目录Gossip协议Gossip协议概念Gossip协议工作流程图解Gossip协议原理消息类型通信方式Gossip协议优点Gossip协议Gossip协议概念说到共识算法,大家首先想到的应该都是Raft、Paxos、Zab算法这类理解起来比较困难的强一致性算法。... 查看详情
图解raft算法(代码片段)
在现实的分布式系统中,不能可能保证集群中的每一台机器都是100%可用可靠的,集群中的任何机器都可能发生宕机、网络连接等问题导致集群中的某个节点不可用,这样,那个节点的数据就有可能和集群不一致,所以需要有一... 查看详情
分布式共识算法raft(代码片段)
...ader,如果网络正常了会发生什么?前言Raft是一种分布式共识算法,目前被consul和etcd使用。Raft中的角色Follower:追随者Candidate:竞选者Leader:领导者算法过程我们以一个简单的集群为例说明,这个集群有三... 查看详情
raft共识算法
raft共识算法分布式一致性问题如果说,服务器只有一个节点,那么,要保证一致性,没有任何问题,因为所有读写都在一个节点上发生。那如果server端有2个、3个甚至更多节点,要怎么达成一致性呢?下面就来介绍其中一种分布... 查看详情
详解分布式共识(一致性)算法raft
参考技术A所谓分布式共识(consensus),与CAP理论中的一致性(consistency)其实是异曲同工,就是在分布式系统中,所有节点对同一份数据的认知能够达成一致。保证集群共识的算法就叫共识算法,它与一致性协议这个词也经常互... 查看详情
一致性算法raft简易入门
...点共识的问题的,当存在多个不同服务节点时,才会引入分布式一致性的问题。Raft是一种实现分布式共识的协议。所谓共识,就是多个节点对某个事情达成一致的看法,即使是在部分节点故障、网络延时、网络分割的情况下。... 查看详情
java-raft框架之atomix进行分布式管理(代码片段)
共识算法在一个分布式的系统中,管理各个节点的一致性(共识)一直是个很有难度的问题。在近几十年的发展中,于1990年诞生的Paxos算法是其中最为经典的代表,并一统江湖数几十载。如著名的zookeeper、chubb... 查看详情
超详细教程!手把手带你使用raft分布式共识性算法
导语 |从头理一遍Raft会给你带来新的体验与收获,让你从根本上理解Raft,理解它被提出的背景,在此背景下又是如何解决实际问题的,这才是从头实现一个Raft所带来的真正收益。本文聚焦在Raft算法的实现上... 查看详情
java-raft框架之atomix进行分布式管理(代码片段)
共识算法在一个分布式的系统中,管理各个节点的一致性(共识)一直是个很有难度的问题。在近几十年的发展中,于1990年诞生的Paxos算法是其中最为经典的代表,并一统江湖数几十载。如著名的zookeeper、chubb... 查看详情
java-raft框架之atomix进行分布式管理(代码片段)
共识算法在一个分布式的系统中,管理各个节点的一致性(共识)一直是个很有难度的问题。在近几十年的发展中,于1990年诞生的Paxos算法是其中最为经典的代表,并一统江湖数几十载。如著名的zookeeper、chubb... 查看详情
拜占庭将军问题和raft共识算法讲解
作者:京东物流郭益如导读在分布式系统中,什么是拜占庭将军问题?产生的场景和解决方案是什么?什么是Raft共识算法?Raft算法是如何解决拜占庭将军问题的?其核心原理和算法逻辑是什么?除了Raft,还有哪些共识算法?共... 查看详情
分布式共识算法——paxos算法(图解)
文章目录PaxosPaxos概念Paxos角色Paxos算法流程Paxos算法两个阶段第一阶段:准备阶段第二阶段:批准阶段总结:图解算法流程举例说明算法流程图解说明一个简单的提案情况1:正常情况两个提案并发进行情况2:S3... 查看详情
分布式共识算法——paxos算法(图解)
文章目录PaxosPaxos概念Paxos角色Paxos算法流程Paxos算法两个阶段第一阶段:准备阶段第二阶段:批准阶段总结:图解算法流程举例说明算法流程图解说明一个简单的提案情况1:正常情况两个提案并发进行情况2:S3... 查看详情
共识算法之争(pbft,raft,pow,pos,dpos,ripple)(代码片段)
目录一.拜占庭容错技术(ByzantineFaultTolerance,BFT)二.PBFT:PracticalByzantineFaultTolerance,实用拜占庭容错算法。三.Raft协议。1.LeaderElection 2.LogReplication四.POW:ProofofWork,工 查看详情
fabric中的raft共识算法
Fabric中的RAFT共识算法什么是共识算法HyperldgerFabric的不同Fabric中的共识算法之Raft节点状态主导节点的选举日志复制OSN(OrderingServiceNode)的Raft排序实现Raft和PBFT的对比什么是共识算法共识机制(consensus)是所有区块链项目中最基础最根... 查看详情
共识算法系列之一:私链的raft算法和联盟链的pbft算法
...链:私链的共识算法即区块链这个概念还没普及时的传统分布式系统里的共识算法,比如zookeeper的zab协议,就是类paxos算法的一种。私链的适用环境一般是不考虑集群中存在作恶节点,只考虑因为系统或者网络原因导致的故障节... 查看详情
分布式系统(代码片段)
...一个raft算法的门槛很低,以至于现在基于raft算法的分布式KV系统都烂大街了,github上能搜出各种语言版本的数十个项目出来。质量层次不齐,需要读者分辨一下。不过我觉得这是raft算法的优势之一,因为简单ÿ... 查看详情