0%

Raft(五) Proof of safety

安全性证明

Raft里的特性

选举安全特性

对于一个给定的任期号,最多只会有一个领导人被选举出来
随机的选举超时机制,选举成功后发送心跳包告知他人。

存在的问题:splite vote,通过随机的选举超时机制,进行多轮的超时选举

  • 任期号:非常重要的成分,在Raft算法中起到一个逻辑时钟的作用,单调递增。各个节点心跳、投票请求、复制log都会交换任期号(得到更大的任期号),候选人或者领导者收到更大的任期号,会自动变成跟随者。
  • major:同一任期获取大多数投票,follower在一个term里只能投一票
  • 选票瓜分:在一个任期里无法选举出领导者,进行下一轮选举,经过一个新的选举时间,任期号+1,发起投票请求…直到选出领导者。

领导人只附加原则

  • 领导人处理不一致是通过强制跟随者直接复制自己的日志来解决了。
  • 在发送附加日志 RPC的时候,领导人会把新的日志条目紧接着之前的条目的索引位置和任期号包含在里面。如果跟随者在它的日志中找不到包含相同索引位置和任期号的条目,那么他就会拒绝接收新的日志条目。

日志匹配原则

如果在不同的日志中的两个条目拥有相同的索引和任期号,那么他们之前的所有日志条目也全部相同。

  • 附加日志 RPC 的一个简单的一致性检查所保证。

领导人完全特性

如果某个日志条目在某个任期号中已经被提交,那么这个条目必然出现在更大任期号的所有领导人中

反证法


描述场景:如果 S1 (任期 T 的领导者)提交了一条新的日志在它的任期里,然后 S5 在之后的任期 U 里被选举为领导人,然后至少会有一个机器,如 S3,既拥有来自 S1 的日志,也给 S5 投票了。

我们假设领导人完全性特性是不存在的,然后我们推出矛盾来。假设任期 T 的领导人(领导人T)在任期内提交了一条日志条目,但是这条日志条目没有被存储到未来某个任期的领导人的日志中。

设大于 T 的最小任期 U 的领导人 U 没有这条日志条目。

细节:

  1. 由于假设,领导人完全性特性不存在的。term U的领导人S5没有term U的日志条目,收到了来自至少一个拥有termT的日志条目的一票(图中的S3)
  2. 根据另外一个假设,大于 T 的最小任期 U 的领导人 U 没有这条日志条目。也就是说在[T…U)之间的领导人都是存在term T的该日志的,U是没有此日志的。
  3. 投票者把自己选票投给领导人 U 时,领导人 U 的日志必须和投票者自己一样新。这就导致了两者矛盾。
  • 两个矛盾:
    • 如果voter和U的最后的term相同,那么leaderU则至少在最后的term的日志和voter的一样长,即包含了leader T提交的log entry;
    • 如果voter和U的最后的term不相同,那么U的必定大于voter的,则leader U必须包含term T的所有日志,因为U > T;(日志匹配原则)
  1. 因此,假设不成立,不可能存在term U,使得term U中的leader不包含之前leader已经提交过的log entry。

状态机安全特性

如果一个领导人在给定的索引值的日志项应用到状态机中,那么其他任何的服务器在这个索引的位置不会提交一个不同的日志

现在我们来考虑在任何一个服务器应用一个指定索引位置的日志的最小任期;领导人完全特性保证拥有更高任期号的领导人会存储相同的日志条目,所以之后的任期里应用某个索引位置的日志条目也会是相同的值。因此,状态机安全特性是成立的。

最后,Raft 要求服务器按照日志中索引位置顺序应用日志条目。和状态机安全特性结合起来看,这就意味着所有的服务器会应用相同的日志序列集到自己的状态机中,并且是按照相同的顺序。