分布式系统开发之Raft一致性共识算法

2019-08-0110:00:40数据结构与算法Comments2,927 views字数 2182阅读模式

分布式系统除了提升整个体统的性能外还有一个重要特征就是提高系统的可靠性。提供可靠性可以理解为系统中一台或多台的机器故障不会使系统不可用或者丢失数据。保证系统可靠性的关键就是多副本,一旦有多副本,那么就面临多副本之间的一致性问题文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/14847.html

一致性算法正是用于解决分布式环境下多副本之间数据一致性的问题的。业界最著名的一致性算法就是大名鼎鼎的Paxos,但Paxos是出了名的难懂,而Raft正是为了探索一种更易于理解的一致性算法而产生的,它将一致性拆分为leader选举、日志复制、安全性三个关键元素。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/14847.html

1、leader选举文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/14847.html

Raft算法将时间划分成为任意不同长度的任期(term),任期用连续的数字表示,每一个任期的开始都是一次选举。如果一个侯选人赢得了选举,它就会在该任期的余下时间担任领导人,如果没有选出领导人,将会开始另一个任期,并且立刻开始下一次选举文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/14847.html

分布式系统开发之Raft一致性共识算法

那么什么时候开始选举呢?实际上leader会向所有follower周期性发送心跳,来保证它们的leader地位,如果一个follower在一个周期内没有收到heartbeat信息,那么它就会假定没有可用的leader,自已就转换状态成为候选人,并且开始一次选举来选出一个新的leader文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/14847.html

Raft选举过程有三个规则文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/14847.html

(1)、规则:如果请求投票的服务器任期比自己的任期大,则给该服务器投票文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/14847.html

分布式系统开发之Raft一致性共识算法

(2)、规则:在一个任期内,一台服务器最多能给一个侯选人投票,按照先到先得的原则文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/14847.html

分布式系统开发之Raft一致性共识算法

(3)、规则:随机选举超时文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/14847.html

为了避免选票被平分,没有服务器成为leader,每台服务器在一个固定的范围内随机选取,从而使每台服务器的选举超时时间均不相同,这种机制使得在大多数情况下只有一个服务器会率先超时,它会在其他服务器超时之前赢得选举并且向其它服务器发送heartbeat信息文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/14847.html

分布式系统开发之Raft一致性共识算法

当候选人收到大多数节点的选票则转换为leader,发现leader或者收到更高任期的请求则转换为follower,在角色转换的时候遵守选举安全原则,一个任期(term)内最多允许有一个leader被选上文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/14847.html

分布式系统开发之Raft一致性共识算法

2、日记复制文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/14847.html

要理解为日记复制得先搞明白日记匹配原则和可被提交的日记这两个概念
日记匹配原则描述的是,如果在不同日记中的两个条目有着相同的索引和任期号,则它们存储的命令是相同的。如果在不同日记中的两个条目有着相同的索引和任期号,则它们之间的所有条目都是完全相同的
可被提交的日记描述的是,一旦被leader创建的条目已经复制到了大多数服务器上,这个日记就称为可被提交的。leader日记中之前的条目都是可被提交的,包括由之前的leader创建的条目文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/14847.html

分布式系统开发之Raft一致性共识算法

在日记复制流程中,leader需要找到follower同它的日记一致的地方,然后删除follower在该位置之后的条目,然后将自己在该位置之后的条目发送给follower文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/14847.html

分布式系统开发之Raft一致性共识算法

完整流程是,client向leader发出请求,leader将日记条目加入到它的日志中,并行向follower服务器发起日记复制请求,leader确认日记条目被安全复制后,将该条目应用到状态机,然后向client返回结果,向follower发出可以提交该日记条目的请求。当一个服务器已经将给它索引位置的日记条目应用到状态机中,则所有其他服务器不会在该索引位置应用不同的条目文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/14847.html

分布式系统开发之Raft一致性共识算法

在日记复制中,可能会出现各种各样的异常文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/14847.html

(1)、异常:数据发送到leader,但未复制到follower文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/14847.html

分布式系统开发之Raft一致性共识算法

leader异常,client接收不到ack,重新选举后,client可重新向leader发出请求
(2)、异常:数据到达leader节点,成功复制到follower所有节点,但未向leader响应接收文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/14847.html

分布式系统开发之Raft一致性共识算法

重新选举后,虽然数据在follower节点处于未提交状态但保持一致,重新选举出leader后可完成数据提交,由于原leader异常,client无法接收到ack,会重新向leader发出请求,Raft要求RPC幂等,所以服务器要实现去重机制
(3)、异常:数据到达leader节点,成功复制到follower所有或多数节点,数据在leader处于已提交状态,但在follower处于未提交状态文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/14847.html

分布式系统开发之Raft一致性共识算法

这个阶段leader挂掉,重新选出新leader文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/14847.html

(4)、异常:由于网络”分区”导致出现双leader
以5个服务器节点为例,正常情况下A节点为leader,接收client的请求,并将日记同步到B、C、D、E四个follower节点。由于网络原因,A、B节点无法与C、D、E进行通信,C、D、E重新选举,选择leader,假设E节点胜出,此时出现双leader。随后网络恢复,A、B将做为E的follower文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/14847.html

3、安全性
Raft通过比较日记中最后一个条目的索引和任期号来决定两个日记哪一个更新,如果两个日记的任期号不同,任期号大的更新,如果任期号相同,更长的日记更新
Raft为了保证安全性,约定了一些选举限制,RequestVote RPC中包含候选人的日记信息,如果服务器自己的日记比候选人还要新,则会拒绝为该候选人投票文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/14847.html

分布式系统开发之Raft一致性共识算法

这个行为背后是leader完全原则,如果一个日记条目在一个给定任期内被提交,那么这个条目一定会出现在所有任期号更大的leader中。所有的日志条目都只会从leader节点往follower节点写入,且leader节点上的日志只会增加,绝对不会删除或者覆盖。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/14847.html

作者介绍:京东资深工程师-梁松华文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/14847.html

文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/14847.html
  • 本站内容整理自互联网,仅提供信息存储空间服务,以方便学习之用。如对文章、图片、字体等版权有疑问,请在下方留言,管理员看到后,将第一时间进行处理。
  • 转载请务必保留本文链接:https://www.cainiaoxueyuan.com/suanfa/14847.html

Comment

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定