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 条评论
下一页
