Raft 总结
## 重点
通常一致性算法保证以下几点:
- 安全性保证:在非拜占庭错误下,都能返回非错误的结果。
- 可用性:集群只要保证 n/2 + 1 节点可用,那么这个集群就是可用的。
- 不依赖物理时钟保证一致性:由于分布式的机器的物理时钟是不可靠的,因此,绝不会使用物理时钟。
- 性能:通常一条指令只需要一轮 RPC 调用即可返回结果,小部分节点响应较慢,不影响整体性能。
Raft 特点:
- 日志复制是 Raft 的核心,保证日志复制一致是分布式一致性算法的核心。
- Raft 设计的整体思路:将一致性工作进行分解(牺牲原子性,提高可理解性),并且从最简单的策略触发,使用遇到问题打补丁的方式,实现了一个可靠的一致性算法。
- Raft 和 正统的 Paxos 不同的地方在于,Raft 的一致性前提:必须要有一个强领导者,这个强领导者,保证了日志复制的一致。
- Raft 在处理成员增减的策略是:将可能出现两种配置的场景,原子化为一个配置。
- 日志复制基于状态机,相当于一个函数,当数据输入状态机,执行固定的指令,将状态改变。
- Raft 为了实现可理解:做了 2 个工作,第一,只要可能,就将复杂问题分解,例如 Raft 被分成 leader 选举,日志复制,安全性和成员变更等几个部分;第二,通过减少状态的数量。
Raft 算法浓缩总结
特性 | 解释 |
---|---|
选举安全特性 | 对于一个给定的任期号,最多只会有一个领导人被选举出来 |
领导人只附加原则 | 领导人绝对不会删除或者覆盖自己的日志,只会增加 |
日志匹配原则 | 如果两个日志在相同的索引位置的日志条目的任期号相同,那么我们就认为这个日志从头到这个索引位置之间全部完全相同 |
领导人完全特性 | 如果某个日志条目在某个任期号中已经被提交,那么这个条目必然出现在更大任期号的所有领导人中 |
状态机安全特性 | 如果一个领导人已经在给定的索引值位置的日志条目应用到状态机中,那么其他任何的服务器在这个索引位置不会提交一个不同的日志 |
注意:日志匹配规则
,领导人完全特性
,是非常非常核心的重点,保证这2个特性,才能实现一致性,同时,这两个特性在某个场合, 将是证明一致性的依据(当然,其他 3 个特性也非常的重要)。
Raft 回顾
- 状态: 节点在 3 个状态直接转换(跟随者, 候选者,领导者),同时,还有加时赛的概念。
- leader 选举时,会交换任期号,如果任期比自己小,那么则直接拒接。如果 leader 发现自己任期号过期了,则直接恢复成跟随者状态。
- 任期:每个选举都是一个任期,即使没成功选举出 leader ,也会更新任期,任期充当逻辑时钟,是保证系统的一致性重要手段。
- 日志复制:日志由 3 部分组成:
下标
,任期号
,具体命令内容
。其中,下标和任期号是保证日志在系统中一致的重要属性。下标保证了日志的唯一,任期保证了日志在整个系统的一致。
刚刚上面说的 2 大特性,日志匹配原则和领导人完全特性
,也是基于这个前提。 - 一致性检查: leader 每次同步日志,都会进行一致性检查(nextIndex + term)。
- 如果新 leader 和 followers 的日志不一致,以 leader 为准进行覆盖—— 即删除 follower 冲突的日志。
- 选举时:想成为leader,需要满足 2 个重要的规则,先判断任期号大小,再判断日志的下标大小。值较大的才能成为 leader。
- 7 号条件有缺陷:),因此需要增加限制条件,即 leader 不能直接提交之前任期的日志条目。
- 集群成员变化:通过使用 2 阶段提交的方式,而不是直接从 old 配置变成 new 配置,Raft 在中间使用 <Cold,Cnew> 这样一个共同配置,即可防止集群同时出现两个 leader。
参考
Raft paper 中文翻译 —— 寻找一种易于理解的一致性算法(扩展版)
EOF
Raft 总结
http://thinkinjava.cn/2018/10/26/2018/2018-10-26-Raft 总结/