背景图

Raft算法简介

分布式一致性算法中大家最熟悉还是Paxos,但是这个算法理解起来比较难,实现这个算法的难度也很高,最后都会对协议本身进行修改实现。

为了提高理解性,Raft 将一致性算法分为了几个部分,例如领导选取(leader selection),日志复制(log replication)和安全性(safety),同时它使用了更强的一致性来减少了必须需要考虑的状态。

几个特性

  • 强领导者(Strong Leader):Raft 使用一种比其他算法更强的领导形式。例如,日志条目只从领导者发送向其他服务器。这样就简化了对日志复制的管理,使得 Raft 更易于理解。
  • 领导选取(Leader Selection):Raft 使用随机定时器来选取领导者。这种方式仅仅是在所有算法都需要实现的心跳机制上增加了一点变化,它使得在解决冲突时更简单和快速。
  • 成员变化(Membership Change):Raft 为了调整集群中成员关系使用了新的联合一致性(joint consensus)的方法,这种方法中大多数不同配置的机器在转换关系的时候会交迭(overlap)。这使得在配置改变的时候,集群能够继续操作。

复制状态机

分布式一致性的解决方案就是复制状态机, 在一组服务器的状态机产生同样的状态的副本因此即使有一些服务器崩溃了这组服务器也还能继续执行。但是集群中有一个Leader节点,Leader选举是使用一个单独的复制状态机,并存储配置信息,防止leader崩溃。

从图上我们可以发现共识模块是处理分布式一致性的,Log模块记录操作的记录(这个操作很重要),最后是每台机器的状态机。复制状态机是通过复制日志实现的,每台服务器都保存一份日志,日志中包含一系列的命令,状态机会按照顺序执行这些命令。

应用于实际系统的一致性算法一般有以下特性:

  • 确保安全性(从来不会返回一个错误的结果),即使在所有的非拜占庭(Non-Byzantine)情况下,包括网络延迟、分区、丢包、冗余和乱序的情况下。
  • 高可用性,只要集群中的大部分机器都能运行,可以互相通信并且可以和客户端通信,这个集群就可用。
  • 不依赖时序保证一致性,时钟错误和极端情况下的消息延迟在最坏的情况下才会引起可用性问题。
  • 通常情况下,一条命令能够尽可能快的在大多数节点对一轮远程调用作出相应时完成,一少部分慢的机器不会影响系统的整体性能。

易于理解的设计

设计 Raft 的目标有如下几个(我想任何算法都应该是这样的):

  • 能提供一个完整的、实际的基础来进行系统构建,减少开发者的工作
  • 在任何情况下都能保证安全可用。
  • 对于常规的操作,必须是高效的。
  • 易于理解(这样才能便于应用)
  • 它必须能让开发者有一个直观的认识,这样才能使系统构建者们去对它进行扩展。(其实我觉得这点有点啰嗦)

Raft使用了两种方式来简化算法的复杂度。

一是问题分解:尽可能将问题分解成为若干个可解决的、可被理解的小问题。例如,在 Raft 中,我们把问题分解成为了领导选取(leader election)日志复制(log replication)安全(safety)成员变化(membership changes)

第二个方法是通过减少需要考虑的状态的数量将状态空间简化,这能够使得整个系统更加一致并且尽可能消除不确定性。特别地,日志之间不允许出现空洞,并且 Raft 限制了限制了日志不一致的可能性。尽管在大多数情况下,我们都都在试图消除不确定性,但是有时候有些情况下,不确定性使得算法更易理解。尤其是,随机化方法使得不确定性增加,但是它减少了状态空间。我们使用随机化来简化了 Raft 中的领导选取算法。

Raft 一致性算法

状态

在所有服务器上持久存在的:(在响应远程过程调用 RPC 之前稳定存储的)

名称 描述
currentTerm 服务器最后知道的任期号(从0开始递增)
votedFor 在当前任期内收到选票的候选人 id(如果没有就为 null)
log[] 日志条目;每个条目包含状态机的要执行命令和从领导人处收到时的任期号

在所有服务器上不稳定存在的:

名称 描述
commitIndex 已知的被提交的最大日志条目的索引值(从0开始递增)
lastApplied 被状态机执行的最大日志条目的索引值(从0开始递增)

在领导人服务器上不稳定存在的:(在选举之后初始化的)

名称 描述
nextIndex[] 对于每一个服务器,记录需要发给它的下一个日志条目的索引(初始化为领导人上一条日志的索引值+1)
matchIndex[] 对于每一个服务器,记录已经复制到该服务器的日志的最高索引值(从0开始递增)

这个是每台机器内部的状态量,根据这些信息我们可以查看相应的节点状态,每个节点也可以通过这些状态来检查网络中各节点的状态,最终需要leader节点进行同步。

附加日志远程过程调用 (AppendEntries RPC)

由领导人来调用复制日志(5.3节);也会用作heartbeat

参数 描述
term 领导人的任期号
leaderId 领导人的 id,为了其他服务器能重定向到客户端
prevLogIndex 最新日志之前的日志的索引值
prevLogTerm 最新日志之前的日志的领导人任期号
entries[] 将要存储的日志条目(表示 heartbeat 时为空,有时会为了效率发送超过一条)
leaderCommit 领导人提交的日志条目索引值
返回值 描述
term 当前的任期号,用于领导人更新自己的任期号
success 如果其它服务器包含能够匹配上 prevLogIndex 和 prevLogTerm 的日志时为真

接受者需要实现:

  1. 如果 term < currentTerm返回 false(5.1节)(这个应该是发现了最新的leader)
  2. 如果在prevLogIndex处的日志的任期号与prevLogTerm不匹配时,返回 false(5.3节)(发现问题,3解决)
  3. 如果一条已经存在的日志与新的冲突(index 相同但是任期号 term 不同),则删除已经存在的日志和它之后所有的日志(5.3节)(解决2中存在的问题,回滚)
  4. 添加任何在已有的日志中不存在的条目(恢复数据)
  5. 如果leaderCommit > commitIndex,将commitIndex设置为leaderCommit和最新日志条目索引号中较小的一个(获取新日志后更新)

这个心跳检测和同步日志消息其实就是检测当前节点与Leader节点异同,如果发现数据异常,根据Leader节点的数据进行回滚,拉取最新的日志,根据日志恢复状态机。如果发现漏了很多日志就同步日志恢复状态机。

投票请求RPC(RequestVote RPC)

由候选人发起收集选票(5.2节)

参数 描述
term 候选人的任期号
candidateId 请求投票的候选人 id
lastLogIndex 候选人最新日志条目的索引值
lastLogTerm 候选人最新日志条目对应的任期号
返回值 描述
term 目前的任期号,用于候选人更新自己
voteGranted 如果候选人收到选票为 true

接受者需要实现:

  1. 如果term < currentTerm返回 false(5.1节)(可能是旧的Leader,但现在有新的了,忽略)
  2. 如果votedFor为空或者与candidateId相同,并且候选人的日志和自己的日志一样新,则给该候选人投票(5.2节 和 5.4节)

服务器需要遵守的规则:

所有服务器:

  • 如果commitIndex > lastApplied,lastApplied自增,将log[lastApplied]应用到状态机(5.3节)
  • 如果 RPC 的请求或者响应中包含一个 term T 大于 currentTerm,则currentTerm赋值为 T,并切换状态为追随者(Follower)(5.1节)

追随者(followers): 5.2节

  • 响应来自候选人和领导人的 RPC
  • 如果在超过选取领导人时间之前没有收到来自当前领导人的AppendEntries RPC或者没有收到候选人的投票请求,则自己转换状态为候选人

候选人:5.2节

  • 转变为选举人之后开始选举:
    • currentTerm自增
    • 给自己投票
    • 重置选举计时器
    • 向其他服务器发送RequestVote RPC
  • 如果收到了来自大多数服务器的投票:成为领导人
  • 如果收到了来自新领导人的AppendEntries RPC(heartbeat):转换状态为追随者
  • 如果选举超时:开始新一轮的选举

领导人:

  • 一旦成为领导人:向其他所有服务器发送空的AppendEntries RPC(heartbeat);在空闲时间重复发送以防止选举超时(5.2节)
  • 如果收到来自客户端的请求:向本地日志增加条目,在该条目应用到状态机后响应客户端(5.3节)
  • 对于一个追随者来说,如果上一次收到的日志索引大于将要收到的日志索引(nextIndex):通过AppendEntries RPC将 nextIndex 之后的所有日志条目发送出去
  • 如果发送成功:将该追随者的 nextIndex和matchIndex更新
  • 如果由于日志不一致导致AppendEntries RPC失败:nextIndex递减并且重新发送(5.3节)
  • 如果存在一个满足N > commitIndex和matchIndex[i] >= N并且log[N].term == currentTerm的 N,则将commitIndex赋值为 N

Raft 一致性算法的特性

Raft 算法保证这些特性任何时刻都成立

性质 描述
选举安全原则(Election Safety) 一个任期(term)内最多允许有一个领导人被选上(5.2节)
领导人只增加原则(Leader Append-Only) 领导人永远不会覆盖或者删除自己的日志,它只会增加条目
日志匹配原则(Log Matching) 如果两个日志在相同的索引位置上的日志条目的任期号相同,那么我们就认为这个日志从头到这个索引位置之间的条目完全相同(5.3 节)
领导人完全原则(Leader Completeness) 如果一个日志条目在一个给定任期内被提交,那么这个条目一定会出现在所有任期号更大的领导人中
状态机安全原则(State Machine Safety) 如果一个服务器已经将给定索引位置的日志条目应用到状态机中,则所有其他服务器不会在该索引位置应用不同的条目(5.4.3节)

Raft 通过首先选出一个领导人来实现一致性,然后给予领导人完全管理复制日志(replicated log)的责任。领导人接收来自客户端的日志条目,并把它们复制到其他的服务器上,领带人还要告诉服务器们什么时候将日志条目应用到它们的状态机是安全的。通过选出领导人能够简化复制日志的管理工作。例如,领导人能够决定将新的日志条目放到哪,而并不需要和其他的服务器商议,数据流被简化成从领导人流向其他服务器。如果领导人宕机或者和其他服务器失去连接,就可以选取下一个领导人。

通过选出领导人,Raft 将一致性问题分解成为三个相对独立的子问题:

  • 领导人选取(Leader election): 在一个领导人宕机之后必须要选取一个新的领导人(5.2节)
  • 日志复制(Log replication): 领导人必须从客户端接收日志然后复制到集群中的其他服务器,并且强制要求其他服务器的日志保持和自己相同
  • 安全性(Safety): Raft 的关键的安全特性是 表-3 中提到的状态机安全原则(State Machine Safety):如果一个服务器已经将给定索引位置的日志条目应用到状态机中,则所有其他服务器不会在该索引位置应用不同的条目。5.4节阐述了 Raft 是如何保证这条原则的,解决方案涉及到一个对于选举机制另外的限制,这一部分会在 5.2节 中说明。

在说明了一致性算法之后,本章会讨论有关可用性(availability)的问题和系统中时序(timing)的问题。

总结

raft的Leader选举机制和策略总觉得和redis的集群模式很像,后来查看资料,果然redis内部使用的就是raft协议。也就大概明白raft协议的意思了。这里就不再过多地去说明了。

但是论文的后面还有大量的实现说明,我在讨论了,可以查看论文原文,里面提到了很多细节问题,都是我们不得不考虑的事情。

参考和引用

Raft 一致性算法论文译文
图解分布式协议-RAFT
redis集群实现(五) sentinel的架构与raft协议
etcd 中的raft协议

0%