raft算法学习记录

分布式系统中考虑得最多的一个问题：节点崩溃

• raft算法中节点分三类： leader、follower、candidate。
• 其中最复杂的问题都和leader节点崩溃有关，follower和candidate简单直观。

如何比较两个节点的日志条目，哪个节点的日志更加新？

• 任期大者，更新
• 任期相同者，index大者更新

leader日志完整性特性(Leader Completeness Prop-erty)

leader日志完整性特性的意思解读：leader能当选，必须拥有完整日志。这一特性保证了raft算法是安全的，任何一致性算法必须保证这一点。不然，意味着算法存在丢数据的漏洞。

论证过程的翻译： 在5.4.3章节

三个关键时间

广播时间（broadcastTime） << 选举超时时间（electionTimeout） << 平均故障间隔时间（MTBF）

• 广播时间指的是一个服务器并行地发送 RPCs 给集群中所有的其他服务器并接收到响应的平均时间；
• 选举超时时间就是在 5.2节中介绍的选举超时时间；
• 平均故障间隔时间就是对于一台服务器而言，两次故障间隔时间的平均值。

广播时间必须比选举超时时间小一个量级，选举超时时间需要比平均故障间隔时间小上几个数量级.

集群成员变更问题

当集群配置变更时，以日志的方式来处理配置变更之后的各节点的最终一致。配置变更但未最终一致期间，如果leader结点崩溃，同样遵循日志同步的规则。即拥有配置变更日志的结点才可能当选为leader。

还有三个问题要解决：

1. 新的服务器以没有投票权身份加入到集群中来（leader 也复制日志给它们，但是考虑过半的时候不用考虑它们）。直到日志完成同步到新的服务器。
2. 第二个问题是，集群的 leader 可能不是新配置中的一员。这是一个非常极端的情况，发生在新配置刚提交，但是未复制到大多数结点时，leader就崩溃了。这个时间新leader是个旧配置结点，它可以处理客户端的请求，但是一旦新配置日志提交，新leader就会变成follower,集群将重新进行选举。
3. 第三个问题是，被移除的服务器会发起新选举。这个好解决，执行下线的服务器程序上把rpc请求也关闭就ok了。

日志量太大的问题引申出日志压缩的需求

即 raft快照。

带着问题去学习raft

• leader在什么时机会将日志提交给状态机？
• follower如何确认自己的日志是完整的？
• 除了随机超时时间，还有什么方法可以避免candidate瓜分选票的问题？
• 只有一个领导人，单结点和性能问题如何解决？
• 新旧leader交接时，旧leader的日志未提交，如何保证日志完整？
• leader的日志比follower还少，怎么最终一致？
• raft不保证每个结点按相同的顺序执行所有日志，那如何保证所有结点的状态最终一致？
• 投票者是否可以重复投票？如可不行，如何处理的？

开源实现sofa-jraft(java) braft(c++) edc/raft(go)