1. 学习资料
个人觉得不错的阅读顺序是：作者的演讲视频+算法可视化工具 > 大学课程(mit/剑桥) > 论文
光看论文看字不好懂，学算法时visualization很重要
Videos
论文作者（推荐。但没讲成员变更，下面的视频作为补充）：
https://www.youtube.com/watch?v=vYp4LYbnnW8
论文拿来做对比试验的Raft教学视频：
https://www.youtube.com/watch?v=YbZ3zDzDnrw
以及Mit 6.824的课程讲解
https://www.zhihu.com/column/c_1273718607160393728
剑桥（我没看）
https://www.youtube.com/watch?v=IPnesACYRck&list=PLeKd45zvjcDFUEv_ohr_HdUFe97RItdiB&index=18
Visualization
https://raft.github.io/raftscope/index.html
2. 用自己的话解释算法
先选主，选完主之后主从复制，但是复制策略是过半2pc（不是普通的主从同步或异步复制）。
而paxos是每个log都先选主再过半2pc
2.1. 一些影响理解的、论文没提的前提假设
- 每个节点事先知道整个集群的成员列表(membership list)。共识算法不管你一开始怎么同步成员列表（算法假设你已经同步好了），但是算法会管你运行时动态变更成员列表，因为你变更的时候不小心可能影响算法的正确性
例如etcd每个节点启动的时候要配成员列表
- 允许leader批量（并发）写，即使前一个写没commit，leader接收到新的写请求也可以直接做主从复制
所以才会出现Server 5这种情况，222222，一堆2但是很多没commit
image.png
这其实是一种性能优化，提高并发度，并且刷盘时能批量刷盘、减少刷盘次数。见https://zhuanlan.zhihu.com/p/203485444
2.2. 复制的细节
2.2.1. 过半2pc（我自己起的名字）
主从复制本质上是过半2pc，但是单独的commit请求被省掉了，随着下次写操作一起带上。（感觉这种piggyback的思想在分布式算法里很常见？SWIM也有这种策略）
如果新的log没commit时leader fail,会有不确定
算法设计上要想办法“一旦commit、被state machine执行了，将来的leader一定得有这条log”
image.png
image.png
2.2.2. 怎么保证“一旦commit、被state machine执行了，将来的leader一定得有这条log”
选举约束（只选拥有所有commit log的节点当leader）
+leader强势复制（选举成功后，leader强制让follower的log和自己一样）
选举约束
https://zhuanlan.zhihu.com/p/201199555
复制时leader强势让follower日志和自己一样
复制时，Leader“线性退避”试验follower和自己相同的最新log槽位
https://zhuanlan.zhihu.com/p/201198000
2.2.3. 既然允许leader并发批量写，如果follower落后很多的话，会不会导致复制特别慢？
正常情况follower不会落后很多，还好。
异常情况会落后很多，比如机器刚重启要重放所有log,比如新加了一台机器，这种情况follower会落后很多，所以raft算法设计了一套日志压缩和快照机制，就是把某个时刻的所有内存状态作为一个log，那么之前的log就可以忽略
可以看下https://zhuanlan.zhihu.com/p/208393872
2.2.4. 反思：为啥raft不是单纯的给每个log递增id、选举时候比哪个副本的log id最大，为啥还要单独加个任期id？
其实还是会出现脑裂，只不过脑裂的时候少数派leader没法过半写，少数派leader可能自high式的写了很多新log id，和多数派leader的log id重复
所以如果是协调服务+主从复制的架构，不会出现脑裂，那么选举时候比较log id就行了
2.3. 如何处理成员变更(Membership change)
2.3.1. 可能存在的问题
如果是朴素做法，同一时间可能有不同成员配置，可能导致脑裂（两个majority)
image.png
2.3.2. 怎么解决
论文给出的思路：2pc
加一个中间阶段（混合共识），保证全old和全new不可能重叠
image.png
Etcd的实现
https://doczhcn.gitbook.io/etcd/index/index-1/clustering/runtime-reconf-design
思想也是2pc，但是具体细节和论文不一样，很巧妙：
第一阶段保证新节点没启动，是fail状态，写配置变更，直到commit
第二阶段启动新成员
这样就避免了上文提到的、在新配置uncommitted时出现脑裂的问题
2.4. 如何避免"client明明请求失败了，数据还是写进去了?"
从上面描述可以看出来，假设一个复制还没过半时发生了网络分区，旧leader怎么都没法复制过半，而新leader可能有本来没复制过半的log（没commit的log)，但最终还是提交了，这对client来说可能会很困惑
因此个人理解，raft leader如果复制过不了半，不应该返回fail给client，因为可能client重试时发现其实已经提交了。
补充：问了下开发Raft的技术同学，复制没过半的话Leader会无限重试、不响应client，client自己超时停止
2.5. 怎么响应读操作
2.5.1. 方案
听课的理解是两种风格，一种是读请求只访问leader，而且leader要做一个空写
Q: 为什么空写,为什么不能直接读已commit的log？
A: 因为leader可能已经不是leader了，但不自知。raft可能在分区时有两个节点自以为是leader，只不过少数派leader没法写
另一种是quorum读
2.5.2. 能否优化读性能
提高性能的优化有：
-
读leader，leader空写，但是不进日志（不持久化）；包括leader接收到读请求后做一次心跳，看看自己是不是还是leader。论文有写这种优化
-
读leader，leader使用租约，这样leader只要租约还在就不用去确认自己是不是leader。记得把时间设置小于选举超时时间。spanner的paxos扩展算法是这种思想。但是这种方案的问题是时钟不可靠，spanner可以这么做是以为TrueTime API保证时钟可靠
https://www.zhihu.com/question/485919606 -
读任意副本，通过一套时间戳机制保证线性一致。参考spanner设计，要有TrueTime API
-
能否读任意副本，但是不用TrueTime API？比如搞一套能保证因果一致的版本号
3. 业界实现
3.1. Examples
3.2. 实现原理
3.2.1. 如何基于全序广播实现线性一致性存储?尤其是，如何实现读线性一致？
-
zk咋做的？让用户显示用sync，其实就是写一个log，等到能读到这个log
直觉上，这相当于线性读请求也依赖主节点，主节点成为读写操作的单点瓶颈，一点都不scale，zk server机器越多性能越差 -
etcd咋做的?
-
SOFA-JRaft咋做的
-
DDIA怎么说
-
Multi Group
-
实现上的优化?
3.2.2. 咋管理成员列表
Etcd：提前配好
不管是启动时配置，还是启动时借助naming服务，本质上都是提前配好membership list
然后允许运行时动态修改
image.png
https://doczhcn.gitbook.io/etcd/index/index-1/clustering
https://etcd.io/docs/v3.5/op-guide/clustering/
SOFA-JRaft
提前配好
image.png
https://www.sofastack.tech/projects/sofa-jraft/jraft-user-guide/
https://www.sofastack.tech/projects/sofa-jraft/counter-example/
4. 工程优化
4.1. 课程说 raft snapshot太大，不适合kv数据库等海量数据场景。是不是可以优化raft算法、解决这个问题?
a. 论文有写，让每个服务器独立创建快照，快照压缩事件不写进log。压缩后的日志只在发生节点落后、需要快照复制的时候才用上
但是这里其实还是有问题，网络抖动/节点重启等导致节点落后时，可能会发生快照传输，但其实没落后那么多、用不到那么多
解决的思路课程有提，设计一套协议，leader维护follower进度，压缩不能超过follower进度。不过比较复杂
b. 个人理解,把快照异步复制到一个备份存储里，新节点先基于备份存储重建
c. 分块压缩，类似LSM tree思想
5. 遗留问题
- 怎么解raft的一个edge case，选主抖动问题？
http://www.zhihu.com/question/483967518
- Leader“线性退避”去试follower的log位置，这个会不会导致消息复杂度太高（消息太多），感觉可以优化一下?
很多优化思路，比如让follower给出更多的信息（我有哪些log提交了），以及这些信息是不是可以piggyback（比如之前选举投票的时候就带上这些信息）
或者二分/倍增?
论文提了一种优化思路，follower多带一些信息，让Leader按任期做批量回退。见https://zhuanlan.zhihu.com/p/203483680
教授也说这方面其实有很多优化思路可以做，只不过论文没做展开。
可以看看工程实现中怎么优化的、有没有更好的办法，能不能给这些实现提pull request做优化 - 选举时有可能重试很多次，感觉可以用确定性算法做优化，加快选举速度？
网友评论