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)

相关推荐