Raft基础

  • 一个Raft集群包含若干个节点,通常是5个,允许整个系统容忍2个节点的失效。
  • 任何时刻每一个节点都处于三个状态之一:领导者、跟随者、候选人。通常,系统中只有一个领导人,其它节点都是跟随者。跟随者是被动的:不会发送任何请求,只是简单响应领导者或候选人的请求。领导者处理所有客户端请求。
  • Raft把时间分割成任意长度的任期,每个节点存储当前任期号,单调递增。服务器之间通信时会交换任期号,自动更新到较大任期号;如果一个候选人或领导者发现自己的任期号过期了,会立即恢复成跟随者状态

领导人选举

  • 领导者周期性的向所有跟随者发送心跳包,如果跟随者在一定时间内未收到心跳包,即选举超时,会认为没有领导者,会递增自己的当前任期号并转成候选人,并发起选举,向其它节点发送RPC请求来给自己投票
  • 当一个候选人获取大多数服务器节点针对同一任期号的选票,它成为领导人,并向其他服务器发送心跳建立自己的权威并组织新的领导者产生
  • 每一个服务器节点最多会对一个任期号投出一张选票,按照先来先服务的原则
  • 等待投票时,候选人可能收到领导者的附加日志项RPC,如果这个领导者的任期号大于等于候选人当前的任期号,即候选人会承认领导者合法并变回跟随者,如果任期号比自己小,那么会拒绝RPC并继续保持候选者
  • 如果多个跟随者同时成为候选人,那么选票可能被瓜分以至于没有候选者可以得到大多数人的支持,此时每一个候选者都会超时,然后增加任期号,开始新一轮选举;Raft算法使用随机选举超时时间(150-300ms)的方式来确保很少会发生选票瓜分的情况,在大多数情况下,只有一个服务器会选举超时,然后赢得选举

日志复制

  • 一旦领导人被选举出,就开始为客户端服务,每一个客户端请求都包含一条指令,领导人将指令作为一条新的日志附加到日志中,然后并行的发起RPC给其他服务器,让它们复制这条日志,当被安全的复制,领导人会应用这条日志到它的状态机中然后把结果返回给客户端
  • 如果跟随者出现故障,领导者会不断重试直到所有跟随者都存储了所有日志(尽管已经回复了客户端)
  • 在 Raft 算法中,领导人处理不一致是通过强制跟随者直接复制自己的日志来解决了。这意味着在跟随者中的冲突的日志条目会被领导人的日志覆盖

安全性

在领导选举时增加一些限制,来保证任何的领导人对于给定的任期号,都拥有了之前任期的所有被提交的日志条目

选举限制

  • 保证所有之前的任期号中已经提交的日志条目在选举的时候都会出现在新的领导人中,不需要传送这些日志条目给领导人
  • 日志条目的传送是单向的,只从领导人传给跟随者,并且领导人从不会覆盖自身本地日志中已经存在的条目
  • Raft 使用投票的方式来阻止一个候选人赢得选举除非这个候选人包含了所有已经提交的日志条目
  • 请求投票 RPC 实现了这样的限制: RPC 中包含了候选人的日志信息,然后投票人会拒绝掉那些日志没有自己新的投票请求。
  • 通过比较两份日志中最后一条日志条目的索引值和任期号定义谁的日志比较新。如果两份日志最后的条目的任期号不同,那么任期号大的日志更加新。如果两份日志最后的条目任期号相同,那么日志比较长的那个就更加新

动画演示 Raft

http://thesecretlivesofdata.com/raft/