Raft算法
2020-05-26 18:42:43 0 举报
AI智能生成
Raft算法
作者其他创作
大纲/内容
选举Leader(leader election)
三种节点状态
leader
follower
candidate
term(任期)
log replication
Replicated state machines(重复制机器状态)
选举过程
0、Raft 使用心跳(heartbeat)触发Leader选举。当服务器启动时,初始化为Follower。
Leader向所有Followers周期性发送heartbeat。如果Follower在选举超时时间内没有收到Leader的heartbeat,就会等待一段随机的时间后发起一次Leader选举。
1、Follower将其当前term加一然后转换为Candidate。它首先给自己投票并且给集群中的其他服务器发送 RequestVote RPC;
2、等待其他节点的回复
a)收到多数的投票(含自己的一票),则赢得选举,成为leader
b)被告知别人已当选,那么自行切换到follower
c)一段时间内没有收到大多数投票,则保持candidate状态,重新发出选举
投票者如何决定是否给一个选举请求投票呢?
在任一任期内,单个节点最多只能投一票
候选人知道的信息不能比自己的少
first-come-first-served 先来先得
注:每一个follower都有一个时钟,是一个随机的值,表示的是follower等待成为leader的时间,谁的时钟先跑完,则发起leader选举。
RPC
RequestVote RPC(候选人在选举中发起)
AppendEntries RPC(领导者发送“心跳”)
InstallSnapshot RPC(领导者发送“快照”)
Leader选举的限制
能被选举成为Leader的节点,一定包含了所有已经提交的日志条目。
发起选举条件
刚启动时,所有节点都是follower,这个时候发起选举,选出一个leader;
当leader挂掉后,时钟最先跑完的follower发起重新选举操作,选出一个新的leader。
成员变更的时候会发起选举操作。
候选者(Candidate)给候选人投票前提
Raft确保新当选的Leader包含所有已提交(集群中大多数成员中已提交)的日志条目。这个保证是在RequestVoteRPC阶段做的,candidate在发送RequestVoteRPC时,会带上自己的last log entry的term_id和index,follower在接收到RequestVoteRPC消息时,如果发现自己的日志比RPC中的更新,就拒绝投票。
日志比较的原则是,如果本地的最后一条log entry的term id更大,则更新,如果term id一样大,则日志更多的更大(index更大)。
日志复制(Log replication
过程
客户端的每一个请求都包含被复制状态机执行的指令。
leader把这个指令作为一条新的日志条目添加到日志中,然后并行发起 RPC 给其他的服务器,让他们复制这条信息。
假如这条日志被安全的复制,领导人就应用这条日志到自己的状态机中,并返回给客户端。
如果 follower 宕机或者运行缓慢或者丢包,leader会不断的重试,直到所有的 follower 最终都复制了所有的日志条目。
组成
日志由有序编号(log index)的日志条目组成。每个日志条目包含它被创建时的任期号(term)和用于状态机执行的命令。
如果一个日志条目被复制到大多数服务器上,就被认为可以提交(commit)了。
1、有序编号;
2、任期号;
3、状态机执行的执行命令;
一致性
日志复制的保证
如果不同日志中的两个条目有着相同的索引和任期号,则它们所存储的命令是相同的(原因:leader 最多在一个任期里的一个日志索引位置创建一条日志条目,日志条目在日志的位置从来不会改变)。
如果不同日志中的两个条目有着相同的索引和任期号,则它们之前的所有条目都是完全一样的(原因:每次 RPC 发送附加日志时,leader 会把这条日志条目的前面的日志的下标和任期号一起发送给 follower,如果 follower 发现和自己的日志不匹配,那么就拒绝接受这条日志,这个称之为一致性检查)。
日志不正常的情况
如何保证日志的正常复制
安全性(Safety)
拥有最新的已提交的log entry的Follower才有资格成为leader。
Leader只能推进commit index来提交当前term的已经复制到大多数服务器上的日志,旧term日志的提交要等到提交当前term的日志来间接提交(log index 小于 commit index的日志被间接提交)。
日志压缩(Log compaction)
SnapShot 内容
日志元数据,最后一条已提交的 log entry的 log index和term。这两个值在snapshot之后的第一条log entry的AppendEntries RPC的完整性检查的时候会被用上。
系统当前状态。
成员变更
常规处理成员变更存在的问题
我们先将成员变更请求当成普通的写请求,由领导者得到多数节点响应后,每个节点提交成员变更日志,将从旧成员配置(Cold)切换到新成员配置(Cnew)。但每个节点提交成员变更日志的时刻可能不同,这将造成各个服务器切换配置的时刻也不同,这就有可能选出两个领导者,破坏安全性。
考虑以下这种情况:集群配额从 3 台机器变成了 5 台,可能存在这样的一个时间点,两个不同的领导者在同一个任期里都可以被选举成功(双主问题),一个是通过旧的配置,一个通过新的配置。
简而言之,成员变更存在的问题是增加或者减少的成员太多了,导致旧成员组和新成员组没有交集,因此出现了双主。
解决方法
每次成员变更只允许增加或删除一个成员(如果要变更多个成员,连续变更多次)
问题
网络分区下的一致性解决?
发生了网络分区或者网络通信故障,使得Leader不能访问大多数Follwer了,那么Leader只能正常更新它能访问的那些Follower,而大多数的Follower因为没有了Leader,他们重新选出一个Leader,然后这个 Leader来接受客户端的请求,如果客户端要求其添加新的日志,这个新的Leader会通知大多数Follower。
如果这时网络故障修复 了,那么原先的Leader就变成Follower,在失联阶段这个老Leader的任何更新都不能算commit,都回滚,接受新的Leader的新的更新(递减查询匹配日志)。
Raft数据一致性如何实现?
主要是通过日志复制实现数据一致性,leader将请求指令作为一条新的日志条目添加到日志中,然后发起RPC 给所有的follower,进行日志复制,进而同步数据。
Paxos和Raft区别?
Raft的leader有限制,拥有最新日志的节点才能成为leader,multi-paxos中对成为Leader的限制比较低,任何节点都可以成为leader。
Raft中Leader在每一个任期都有Term号。
Raft里面怎么保证数据被commit,leader宕机了会怎样,之前的没提交的数据会怎样?
leader会通过RPC向follower发出日志复制,等待所有的follower复制完成,这个过程是阻塞的。
老的leader里面没提交的数据会回滚,然后同步新leader的数据。
老哥们感觉不错可以关注我个人微信公众号:coder的特殊身份
0 条评论
下一页