江苏龙网

  1. 主页 > 生活百科 > >

Raft一致性算法( 七 )

算法


5.3 日志复制
一旦一个领导人被选举出来，他就开始为客户端提供服务 。客户端的每一个请求都包含一条被复制状态机执行的指令 。领导人把这条指令作为一条新的日志条目附加到日志中去，然后并行地发起附加条目 RPCs 给其他的服务器，让他们复制这条日志条目 。当这条日志条目被安全地复制（下面会介绍），领导人会应用这条日志条目到它的状态机中然后把执行的结果返回给客户端 。如果跟随者崩溃或者运行缓慢，再或者网络丢包，领导人会不断的重复尝试附加日志条目 RPCs （尽管已经回复了客户端）直到所有的跟随者都最终存储了所有的日志条目 。

Raft一致性算法

文章插图
 
 
图 6：日志由有序序号标记的条目组成 。每个条目都包含创建时的任期号（图中框中的数字），和一个状态机需要执行的指令 。一个条目当可以安全地被应用到状态机中去的时候，就认为是可以提交了 。
 
日志以图 6 展示的方式组织 。每一个日志条目存储一条状态机指令和从领导人收到这条指令时的任期号 。日志中的任期号用来检查是否出现不一致的情况，同时也用来保证图 3 中的某些性质 。每一条日志条目同时也都有一个整数索引值来表明它在日志中的位置 。
领导人来决定什么时候把日志条目应用到状态机中是安全的；这种日志条目被称为已提交 。Raft 算法保证所有已提交的日志条目都是持久化的并且最终会被所有可用的状态机执行 。在领导人将创建的日志条目复制到大多数的服务器上的时候，日志条目就会被提交（例如在图 6 中的条目 7） 。同时，领导人的日志中之前的所有日志条目也都会被提交，包括由其他领导人创建的条目 。5.4 节会讨论某些当在领导人改变之后应用这条规则的隐晦内容，同时他也展示了这种提交的定义是安全的 。领导人跟踪了最大的将会被提交的日志项的索引，并且索引值会被包含在未来的所有附加日志 RPCs （包括心跳包），这样其他的服务器才能最终知道领导人的提交位置 。一旦跟随者知道一条日志条目已经被提交，那么他也会将这个日志条目应用到本地的状态机中（按照日志的顺序） 。
我们设计了 Raft 的日志机制来维护不同服务器日志之间的高层次的一致性 。这么做不仅简化了系统的行为也使其更具有可预测性，同时它也是安全性保证的一个重要组件 。Raft 维护着以下的特性，这些特性共同组成了图 3 中的日志匹配特性（Log Matching Property）：
 
  • 如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们存储了相同的指令 。
  • 如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们之前的所有日志条目也全部相同 。
 
第一个特性来自这样的一个事实，领导人最多在一个任期里在指定的一个日志索引位置创建一条日志条目，同时日志条目在日志中的位置也从来不会改变 。第二个特性由附加日志 RPC 的一个简单的一致性检查所保证 。在发送附加日志 RPC 的时候，领导人会把新的日志条目前紧挨着的条目的索引位置和任期号包含在日志内 。如果跟随者在它的日志中找不到包含相同索引位置和任期号的条目，那么他就会拒绝接收新的日志条目 。一致性检查就像一个归纳步骤：一开始空的日志状态肯定是满足日志匹配特性的，然后一致性检查在日志扩展的时候保护了日志匹配特性 。因此，每当附加日志 RPC 返回成功时，领导人就知道跟随者的日志一定是和自己相同的了 。
在正常的操作中，领导人和跟随者的日志保持一致性，所以附加日志 RPC 的一致性检查从来不会失败 。然而，领导人崩溃的情况会使得日志处于不一致的状态（老的领导人可能还没有完全复制所有的日志条目） 。这种不一致问题会在领导人和跟随者的一系列崩溃下加剧 。图 7 展示了跟随者的日志可能和新的领导人不同 。跟随者可能会丢失一些在新的领导人中存在的日志条目，他也可能拥有一些领导人没有的日志条目，或者两者都发生 。丢失或者多出日志条目可能会持续多个任期 。
Raft一致性算法

文章插图
 
 
图 7：当一个领导人成功当选时，跟随者可能是任何情况（a-f） 。每一个盒子表示是一个日志条目；里面的数字表示任期号 。跟随者可能会缺少一些日志条目（a-b），可能会有一些未被提交的日志条目（c-d），或者两种情况都存在（e-f） 。例如，场景 f 可能会这样发生，某服务器在任期 2 的时候是领导人，已附加了一些日志条目到自己的日志中，但在提交之前就崩溃了；很快这个机器就被重启了，在任期 3 重新被选为领导人，并且又增加了一些日志条目到自己的日志中；在任期 2 和任期 3 的日志被提交之前，这个服务器又宕机了，并且在接下来的几个任期里一直处于宕机状态 。


推荐阅读


上一篇：选Redis做MQ的人，是脑子里缺根弦儿吗？

下一篇：Python面向对象详解