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。
还有三个问题要解决:
- 新的服务器以没有投票权身份加入到集群中来(leader 也复制日志给它们,但是考虑过半的时候不用考虑它们)。直到日志完成同步到新的服务器。
- 第二个问题是,集群的 leader 可能不是新配置中的一员。这是一个非常极端的情况,发生在新配置刚提交,但是未复制到大多数结点时,leader就崩溃了。这个时间新leader是个旧配置结点,它可以处理客户端的请求,但是一旦新配置日志提交,新leader就会变成follower,集群将重新进行选举。
- 第三个问题是,被移除的服务器会发起新选举。这个好解决,执行下线的服务器程序上把rpc请求也关闭就ok了。
日志量太大的问题引申出日志压缩的需求
即 raft快照。
带着问题去学习raft
- leader在什么时机会将日志提交给状态机?
- follower如何确认自己的日志是完整的?
- 除了随机超时时间,还有什么方法可以避免candidate瓜分选票的问题?
- 只有一个领导人,单结点和性能问题如何解决?
- 新旧leader交接时,旧leader的日志未提交,如何保证日志完整?
- leader的日志比follower还少,怎么最终一致?
- raft不保证每个结点按相同的顺序执行所有日志,那如何保证所有结点的状态最终一致?
- 投票者是否可以重复投票?如可不行,如何处理的?
开源实现sofa-jraft(java) braft(c++) edc/raft(go)
相关推荐
setse 2020-07-05
setse 2020-07-04
setse 2020-05-04
遗世紫丁香 2020-04-30
86103155 2020-02-16
abun 2020-01-16
遗世紫丁香 2020-01-11
ShiShuo 2019-12-31
MojitoBlogs 2019-12-17
86103155 2019-12-05
abun 2016-12-05
兒戲BLOG 2019-11-04
阿义 2017-03-10
setse 2019-09-08
MinerAG 2019-09-06
hhahaa 2018-12-25
来信了上校 2018-07-25
兒戲BLOG 2019-07-11
exzhulw 2019-07-04