深入剖析共识性算法 Raft
Kirito的技术分享
共 8990字,需浏览 18分钟
·
2021-09-22 12:18
安全性保证(绝对不会返回一个错误的结果):在非拜占庭错误情况下,包括网络延迟、分区、丢包、冗余和乱序等错误都可以保证正确。 可用性:集群中只要有大多数的机器可运行并且能够相互通信、和客户端通信,就可以保证可用。因此,一个典型的包含 5 个节点的集群可以容忍两个节点的失败。服务器被停止就认为是失败。他们当有稳定的存储的时候可以从状态中恢复回来并重新加入集群。 不依赖时序来保证一致性:物理时钟错误或者极端的消息延迟只有在最坏情况下才会导致可用性问题。 通常情况下,一条指令可以尽可能快的在集群中大多数节点响应一轮远程过程调用时完成。小部分比较慢的节点不会影响系统整体的性能。
分布式锁服务,比如 Zookeeper 分布式存储系统,比如分布式消息队列、分布式块系统、分布式文件系统、分布式表格系统等,比如大名鼎鼎的 Redis 就是基于 Raft 实现分布式一致性 高可靠元信息管理,比如各类 Master 模块的 HA
二、 Raft基础
Leader - 领导者,通常一个系统中是一主(Leader)多从(Follower)。Leader 负责处理所有的客户端请求。 Follower - 跟随者,不会发送任何请求,只是简单的 响应来自 Leader 或者 Candidate 的请求。 Candidate - 参选者,选举新 Leader 时的临时角色。
Follower 只响应来自其他服务器的请求。在一定时限内,如果 Follower 接收不到消息,就会转变成 Candidate,并发起选举。 Candidate 向 Follower 发起投票请求,如果获得集群中半数以上的选票,就会转变为 Leader。 在一个 Term 内,Leader 始终保持不变,直到下线了。Leader 需要周期性向所有 Follower 发送心跳消息,以阻止 Follower 转变为 Candidate。
如果选举成功,Leader 会管理整个集群直到任期结束。 如果选举失败,那么这个任期就会因为没有 Leader 而结束。
服务器节点可能观察到多次的任期转换。 服务器节点也可能观察不到任何一次任期转换。
如果一个服务器的当前任期号比其他人小,那么他会更新自己的编号到较大的编号值。 如果一个 Candidate 或者 Leader 发现自己的任期号过期了,那么他会立即恢复成跟随者状态。 如果一个节点接收到一个包含过期的任期号的请求,那么他会直接拒绝这个请求。
RequestVote RPC - 请求投票 RPC,由 Candidate 在选举期间发起。 AppendEntries RPC - 附加条目 RPC,由 Leader 发起,用来复制日志和提供一种心跳机制。
三、选举Leader
自己成为 Leader 其他的服务器成为 Leader
没有任何服务器成为 Leader
3.1.1自己成为 Leader
当一个 Candidate 从整个集群半数以上的服务器节点获得了针对同一个 Term 的选票,那么它就赢得了这次选举并成为 Leader。每个服务器最多会对一个 Term 投出一张选票,按照先来先服务(FIFO)的原则。要求半数以上选票的规则确保了最多只会有一个 Candidate 赢得此次选举。 一旦 Candidate 赢得选举,就立即成为 Leader。然后它会向其他的服务器发送心跳消息来建立自己的权威并且阻止新的领导人的产生。
3.1.2 其他的服务器成为 Leader
如果这个 Leader 的 Term 号(包含在此次的 RPC 中)不小于 Candidate 当前的 Term,那么 Candidate 会承认 Leader 合法并回到 Follower 状态。 如果此次 RPC 中的 Term 号比自己小,那么 Candidate 就会拒绝这个消息并继续保持 Candidate 状态。
3.1.3 没有任何服务器成为 Leader
以至于在大多数情况下,只有一个服务器会超时,然后它赢得选举,成为 Leader,并在其他服务器超时之前发送心跳包。
同样的机制也被用在选票瓜分的情况下:每一个 Candidate 在开始一次选举的时候会重置一个随机的选举超时时间,然后在超时时间内等待投票的结果;这样减少了在新的选举中另外的选票瓜分的可能性。
3.2 单Candidate选举
3.3 多 Candidate 选举
四、日志复制
日志条目中的 Term 号被用来检查是否出现不一致的情况。 日志条目中的日志索引(一个整数值)用来表明它在日志中的位置。
这个特性基于这条原则:Leader 最多在一个 Term 内、在指定的一个日志索引上创建一条日志条目,同时日志条目在日志中的位置也从来不会改变。
如果不同日志中的两个日志条目有着相同的日志索引和 Term,则它们之前的所有条目都是完全一样的。
这个特性由 AppendEntries RPC 的一个简单的一致性检查所保证。在发送 AppendEntries RPC 时,Leader 会把新日志条目之前的日志条目的日志索引和 Term 号一起发送。如果 Follower 在它的日志中找不到包含相同日志索引和 Term 号的日志条目,它就会拒绝接收新的日志条目。
Leader 负责处理所有客户端的请求。 Leader 把请求作为日志条目加入到它的日志中,然后并行的向其他服务器发送 AppendEntries RPC 请求,要求 Follower 复制日志条目。 Follower 复制成功后,返回确认消息。 当这个日志条目被半数以上的服务器复制后,Leader 提交这个日志条目到它的复制状态机,并向客户端返回执行结果。
4.3.1 Leader 和 Follower 日志不一致的可能
存在未更新日志条目,如(a、b)。 存在未提交日志条目,如(c、d)。 或两种情况都存在,如(e、f)。
Leader 为了使 Followers 的日志同自己的一致,Leader 需要找到 Followers 同它的日志一致的地方,然后覆盖 Followers 在该位置之后的条目。 Leader 会从后往前试,每次日志条目失败后尝试前一个日志条目,直到成功找到每个 Follower 的日志一致位点,然后向后逐条覆盖 Followers 在该位置之后的条目。
五、安全性
先判断 Term,哪个数值大即代表哪个日志比较新。 如果 Term 相同,再比较 日志索引,哪个数值大即代表哪个日志比较新。
阶段 (a) ,S1 是 Leader,且 S1 写入日志条目为 (Term 2,日志索引 2),只有 S2 复制了这个日志条目。 阶段 (b),S1 下线,S5 被选举为 Term3 的 Leader。S5 写入日志条目为 (Term 3,日志索引 2)。 阶段 (c),S5 下线,S1 重新上线,并被选举为 Term4 的 Leader。此时,Term 2 的那条日志条目已经被复制到了集群中的大多数节点上,但是还没有被提交。 阶段 (d),S1 再次下线,S5 重新上线,并被重新选举为 Term3 的 Leader。然后 S5 覆盖了日志索引 2 处的日志。 阶段 (e),如果阶段 (d) 还未发生,即 S1 再次下线之前,S1 把自己主导的日志条目复制到了大多数节点上,那么在后续 Term 里面这些新日志条目就会被提交。这样在同一时刻就同时保证了,之前的所有旧日志条目就会被提交。
六、日志压缩
日志元数据。最后一条已提交的日志条目的日志索引和 Term。这两个值在快照之后的第一条日志条目的 AppendEntries RPC 的完整性检查的时候会被用上。 系统当前状态。
七、参考资料
- END -
「技术分享」某种程度上,是让作者和读者,不那么孤独的东西。欢迎关注我的微信公众号:「Kirito的技术分享」
评论