raft算法

Posted on |

raft 一致性算法（论文总结）

CAP 定理

  • Consistency(一致性)： 数据一致更新，所有数据变动都是同步的
  • Availability(可用性)： 好的响应性能
  • Network partitioning(分区容错性)： 可靠性（当发生了分区的情况下，必须要在 C 和 A 之间做出选择）

根据定理，分布式系统只能满足三项中的两项而不可能满足全部三项[4]。理解CAP理论的最简单方式是想象两个节点分处分区两侧。允许至少一个节点更新状态会导致数据不一致，即丧失了C性质。如果为了保证数据一致性，将分区一侧的节点设置为不可用，那么又丧失了A性质。除非两个节点可以互相通信，才能既保证C又保证A，这又会导致丧失P性质。

对于一致性算法，一致性通常分为 三个级别 强一致性、弱一致性、最终一致性。 raft 算法是一种强一致性算法

raft 的新特性

Raft 和现有的一些一致性算法相似，但是它有一些新的特性

  • Strong leader: raft 和其他一致性算法相比， 采用了一种更强力的领导策略。 比如， 日志条目只允许从领导到服务器。 这样简化了对于重复日志的管理，并让 raft 更加容易理解。
  • Leader election: raft 采用随机定时器来选举领导。 这样只需要在心跳中加入少量的随机策略，就能简单迅速的解决冲突问题
  • Membership changes:: raft 在调整聚群成员的时候采用了一种联合一致性（ joint consensus）的机制。这样当配置改变的时候，集群可以继续运行

复制状态机（Replicated State Machine）

一致性算法是在复制状态机的背景中被提出来的。指的是在一组服务器中产生同样状态的副本，因此即使一些机器发生故障之后仍然能正常工作。复制状态机被用于解决分布式系统中的容错处理。zookeeper 中就使用了复制状态机。

State Machine

复制状态机是通过复制日志来实现的。每一台服务器保存着一份日志，日志中包含一系列的命令，状态机会按顺序执行这些命令。因为每一台计算机的状态机都是确定的，所以每个状态机的状态都是相同的，执行的命令是相同的，最后的执行结果也就是一样的了。如何保证复制日志的一致就是一致性算法的工作内容。

通常强况下，一致性算法有以下特性

  • 确保安全性（从来不会返回错误的结果）在所有的非拜占庭问题的条件下，包括网络延迟、分区、丢包、乱序等情况
  • 可用性 只要集群中大多数节点能够彼此通信，也能喝客户端保持通信、
  • 不依赖定时去确保日志的一致性
  • 通常情况下，只要集群中大多数节点对一轮 RPC 调用做出了相应，一条命令即可被视为已经完成。集群中少部分慢的节点不会影响整个系统的性能。

传统 Paxos 算法的缺点

  • Paxos 算法理解起来很困难
  • 并不能很好的解决实际问题
  • 工程中实现起来也很麻烦

raft 设计目标

  • 提供一个完整的、实际的基础用于系统构建，这样能显著的减少开发量
  • 在所有情况下必须安全， 在典型的情况下保证可用性
  • 最重要的是容易理解

Raft 算法

Raft 实现一致性靠的是首先先选举一个 Leader，然后 Leader 全权负责复制日志(replicated log).
Leader 从客户端接受日志条目， 将它们复制到其他服务器，然后告诉服务器什么时候可以将日志条目应用到它的状态机中。 有一个 Leader 简化了复制日志的管理过程， 如果Leader 宕机或者和其他服务器失去了联系，则会选出一个新的 Leader 。

Raft 将一致性问题分解成相对独立的三个子问题

  • Leader election (Leader 选举): 当集训中一个 Leader 宕机之后必须选出一个新的 Leader
  • Log replication (日志复制): leader 必须从客户端获取日志条目，并将其在集群中复制，强制其他日志和它的日志同步
  • Safety: 如果任何服务器将一条特定的日志条目应用到了自己的状态机中，其他服务器不能在相同的索引位置应用不同的条目。

raft 基础

一个 Raft 集群包含很多服务器节点， 5 是一个典型的数量，允许两个节点宕机。在任意的时候，每一台服务器节点属于以下三个状态中的一个。 Leader、follower、candidate。 正常情况下集群中有一个 leader、其他的节点全是 follower 。 follower 是被动的，不会处理任何请求，仅仅响应从 leader 和 candidates 的请求， leader 处理所有客户端的请求。 candidate 是在参与选举中的节点。
raft server state

raft 任期

raft 任期

raft 将时间分成任意长度的任期， 用连续的数字表示。 每一个任期都从一次选举开始，如果一个参与者赢得本次选举，那么在这次任期接下来的时间就作为集群的 Leader， 并负责管理这个集群。如果一次选举失败的情况下， 马上回开始另一轮选举， raft 保证了在灭一个任期内至少有一个 leader。

任期在 raft 算法中被视为逻辑时钟，允许服务器检测过期的信息如失效的 leader 等。 每一个服务器节点都存放了当前的任期号码，任期号码随着时间单调递增。服务器之间通信时回交换当前的任期号码。

如果一个节点的任期号比另一台服务器任期号小，它将立即更新自己的任期号。 如果一个 candidate 或者 leader 发现自己的任期过期，那么它会马上转变为 follower 状态，如果一台服务节点收到了一个过期的请求，它将拒绝该请求。

raft RPC

Raft 服务节点之间采用 RPC 调用， 通常的一致性算法只需要两种类型的 RPC 。 在集群选举的时候 candidate 触发 RequestVote RPCs，Leader 触发 AppendEntries RPC。raft 添加了在节点之间传输快照的 RPC。 如果服务节点没收到 RPC 的响应，会自动的重试。为了提升性能，这些 RPC 并发的被调用。

  • RequestVote RPCs
  • AppendEntries RPCs
  • Snapshot RPCs

Leader election

raft 采用心跳的机制来出发 leader 选举。

  • 当服务节点启动时，先作为一个 follower。
  • 如果一台服务只要能收到从 leader 或者 candidate 的 RPC 请求， 则该台服务器保持 follower 状态。
  • leader 周期性的发送心跳到所有的 follower 以保证其权威
  • follower 在一个周期内没收到通信请求叫做 election timeout，它假定没有可以到达的 leader。开始一轮选举， follower 增加自己的任期号码，将自己转变为 candidate 状态。
  • follower 为自己投一票并且并发的向集群中其他节点发起一个 RequestVote RPC 请求
  • candidate 在以下三种情况下会变成其他状态
    • 赢得本轮选举变为 leader
    • 另外一台服务器节点成为了 leader
    • 一个竞选周期结束之后没有选出 leader
  • 一个 candidate 如果在一个任期内赢得了整个集群中大多数节点的选票，就赢得了本次选举
  • 在一轮选举中，每一台服务节点最多只会投一票（因此一轮选举最多选出一个 leader）

  • 一旦一个节点赢得选举，自己变成 leader 状态， 并向其他节点发送心跳去建立自己的权威来阻止新的选举

  • candidate 在等待选票的时候，如果收到 其他声称自己时 leader A 节点的 AppendEntries RPC请求时

    • 如果收到 A 的 AppendEntries 的任期号码大于或等于自己的任期号码， 那么它会承认 A 的合法性， 并将自己转化 follower 状态
    • 如果 A 的任期号比自己小， candidate 拒绝这次 RPC 调用并继续返回自己的选举

  • 如果多个 follower 同时变成了 candidate， 选票将会被多个 candidate 分享，这样可能没有一个 candidate 获得大多数的选票， 所有的 candidate 都会增加自己的任期，并开始下一轮选举。如果不采取额外措施，这种情况可能一致持续下去

  • Raft 采用随机的选举超时来确保分票这种情况很少发生，而且即使出现了也能快速被解决。

log replication

一旦 leader 被选了出来，就开始响应客户端的请求。 每一条客户端的请求都包含一条需要被复制状态机执行的命令。

  • leader 接收客户端请求
  • leader 将命令作为一个日志条目加到它的日志中去
  • leader 并发的向其他节点发出 AppendEntries RPCs 请求
  • 当条目被安全的复制（）之后，leader 将条目添加到状态机中， 并向客户端返回结果

如果 follower 崩溃或者运行的很慢、或者发生了丢包， leader 不停的向 follower 发送AppendEntries RPC， 直到所有的 follower 存储了所有的 AppendEntries。

  • 每一个日志条目都有一个整数索引标记自己在日志中的位置
  • leader 决定什么时候可以安全的将 log 应用到状态机中 ， 这样的 日志条目被称为 提交的日志条目
  • Raft 确保了提交的日志条目是持久化的并且最终将会被所有可用的状态己执行。
  • 一旦创建的日志条目的 leader 收到了集群中的大多数节点的确认时，该条日志条目就变成了已提交
  • 在设计 Raft 的日志机制的时候，除了简化系统的行为和让其变的可预测之外，也是确保安全性中的一个很重要的组建。 Raft 维持了以下两种特性
    • 如果不同日志中的两个日志条目有相同的索引和任期，那么它们存储了相同的命令
    • 如果不同日志中的两个日志条目有相同的任期和索引，那么值钱的日志是相同的
      、

      参考文档

  • https://en.wikipedia.org/wiki/CAP_theorem

  • https://raft.github.io/raft.pdf

  • https://github.com/maemual/raft-zh_cn/blob/master/raft-zh_cn.md

如果你觉得本文对你有帮助，欢迎打赏！