暂无图片
暂无图片
暂无图片
暂无图片
暂无图片
首页 / 分布式共识算法-Raft算法

分布式共识算法-Raft算法

Lord Lean Notes 2021-06-05
575
在分布式共识算法-Raft算法中，对如何选举领导者和复制日志条目做了详细描述。但是这两种机制还不足以保证每个状态机以相同的顺序执行完全相同的命令。比如一个领导者提交几条日志记录时，某个追随者是不可用的状态。然后这个追随者被选为了新的领导者，那么其就可以用新的日志记录覆盖前一个领导者的提交记录。所以不同的状态机可能执行不同的命令序列。于是Raft算法采用几种限制来完成算法。
选举限制
在任何基于领导者的共识算法中，领导者最终必须存储所有已经提交的记录。Raft算法保证每个新的领导人都有以往任期的领导者承诺提交的日志记录，这意味着日志记录只会向一个方向流动，领导者和追随者都不会覆盖掉他们已经承诺提交的现有日志。
Raft使用投票过程来阻止候选人赢得选举，除非其日志包含所有已提交的记录。在选举过程中，如果投票者的日志比候选人更新，那么则拒绝投票。Raft通过比较两个日志中最后一条记录的索引和任期来确定哪个日志更新。如果任期不同，那么哪个任期值大，则最新；如果相等那么则相等。
提交以前任期中的记录
如果一个领导者在提交一条记录之前崩溃(但这是在大部分服务器上已经存在)，下一任领导者将尝试完成这条记录的复制。但是领导者不能立即得出这条结论，所以还是会存在一条旧的日志记录存在于多数服务器上，但仍然被覆盖的情况。比如图1的情况

为了消除图1中的情况，Raft不会通过计算副本数量来提交以前任期的日志记录，只有当前任期的领导者才会这样来提交，这样会把本次任期内的以前的日志记录也间接的提交。
Raft在提交规则中带来了这种额外的复杂性，因为当一个leader从以前的术语复制条目时，日志条目保留了它们原来的术语编号。这样容易对日志记录进行推理，并且新的领导者发送上一任期内的日志记录要少的多。
追随者或候选人崩溃
如果追随者或候选人发生了崩溃，那么将无限期重试。Raft rpc请求是支持幂等的，不会对追随者或候选人造成伤害
时间和可用性
Raft的安全性是不依赖于时间的，其不会因为某些事件比预期发生的更快或更慢而产生不正确的结果。但是可用性是必须依赖于时间的。选举领导者是Raft的一个关键因素，而选择一个合适的时机则是重中之重。Raft通过广播时间(broadcastTime)<=选举超时时间(electionTimeout)<=MTBF来选举和保持一个稳定的领导者。
broadcastTime是领导者将rpc请求并行发送到集群中服务器并接收响应所用的平均时间，electionTimeout是选举超时时间，MTBF是单个服务器每个故障之间的平均时间。
广播时间比选举超时时间小，这样可以方便领导者发送心跳信息，这样也使分裂投票的概率变小。选举超时时间比MTBF时间小，这样保证系统的稳定运行。
Cluster资格更改
当集群中的服务器需要更改配置时，例如在服务器失败时替换服务器或更换复制程度，这样虽然可以通过使集群脱机、更新配置文件、重启集群的方式来实现，但这种方式会导致集群在转换期间不可用。
Raft通过将配置自动化，避免了这些问题。其通过切换到一个过渡配置，在Raft中称为联合共识，一旦联合共识提交，系统就提交到新的配置，在联合共识中结合了新旧配置：

  • 将日志记录复制到两个配置中的所有服务器

  • 任何一种配置的服务器都可以作为领导者

  • 关于选举和加入承诺的协议要求新旧组合的多数票分开

                                                图2:新旧集群配置的更迭

集群配置使用带有特殊标识的日志记录进行存储和通信，当含有new配置的领导者收到将集群配置从old配置更改为new配置时，会将此日志在含有old配置的服务器和含有new配置的服务器中全部复制同步，而一旦new配置添加到新的服务器集群日志中后，含有old配置和new配置的服务器集群将使用new的配置来做决策。这意味着领导者将使用old配置来决定合适提交含有old配置和new配置的日志记录。如果含有new规则的服务器被选中成为了候选人，在任何情况下，含有new规则的领导者都不能单方面做决定。
并且只有同时含有new配置和old配置的特殊标识的日志才能被选为领导者，这样领导者就可以安全的创建一个描述new配置的日志记录并复制到集群中，同时new配置在提交后每个服务器都可以看到，当按照new配置提交时，old配置是不生效的，同时不再new配置中的服务器就可以关闭。
对于重新配置，还有三个问题需要解决，第一个问题是新的服务器最初可能不会存储任何的日志记录，Raft算法在配置之前改变之前引入了一个额外的阶段，在这个阶段中，如果日志记录未赶上集群中的服务器时，是没有表决权的。
第二个问题是集群领导者可能不是含有新配置机器的一部分，这种情况下领导者一旦提交new配置，就会退回到追随者的状态。这意味着将有一段时间(在提交new配置时)，领导者将管理不包括刚刚从old配置中选出的机器，其复制日志记录，但不会将自身计入到大多数。在提交new配置时会发生领导者交接，因为这是第一次new配置可以独立的运行。说明在此之前，可能有来自old配置的服务器可以被选为领导者。
第三个问题是删除的服务器(不在new配置中的)可能会破坏集群，这些服务器不会接收到心跳，所以其会超时并开始新的选举。当选出新的领导者后，被删除的服务器仍会超时，并重复此过程，导致可用性降低。
为了防止第三个问题，当服务器相信现任领导存在时，会拒绝投票的rpc请求，不会更新自己的任期或授予投票权。这样是不会影响正常选举的，即每个服务器开始选举前要至少等待一个最小的选举超时，避免服务器造成的中断。
数据库
文章转载自Lord Lean Notes，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

评论