理解Raft简述

Raft是一种共识算法，用于解决分布式系统中的一致性问题。Raft细节虽多，但算法并不晦涩、神秘

声明：本文参考Raft中文翻译结合自己理解完成，更深入全面的Raft，请关注Raft官网

为了详细解释Raft算法，作者将问题分解成三个问题：领导人选举、日志复制和安全性及成员变更。

但是，在这之前，还需要了解下Raft的背景和基础设计。

‍

一、Raft背景及基础

1.1 复制状态机

一致性算法是从复制状态机的背景下提出的。在这种方法中，一组服务器上的状态机产生相同状态的副本，并且在一些机器宕掉的情况下也可以继续运行。

​​

复制状态机通常都是基于复制日志实现的，因此Raft算法其实保证的就是集群日志的一致性。

‍

1.2 Raft算法基础概念

Raft共识算法中包含以下角色：

• 领导者（Leader）：负责接收客户端的请求，并将其复制到其他节点的日志中。领导者负责发起选举、维护心跳以及处理来自其他节点的请求。
• 跟随者（Follower）： 跟随者是Raft集群中的普通节点角色，它们只是被动地响应来自领导者的请求，并根据领导者的指示更新自己的状态。
• 候选人（Candidate）： 当Raft集群中没有领导者时，节点会转变为候选人角色，并发起选举以尝试成为新的领导者。候选人会向其他节点发送投票请求，如果获得多数节点的投票，则成为新的领导者。

角色流转示意图：

​

Raft用任期(term)来表示角色变更的基本时间单位：

​​

时间被划分成一个个的任期，每个任期始于一次选举。在选举成功后，领导人会管理整个集群直到任期结束。有时候选举会失败，那么这个任期就会没有领导人而结束

‍

二、Leader选举

Raft 使用一种心跳机制来触发领导人选举。
要开始一次选举过程，跟随者先要增加自己的当前任期号并且转换到候选人状态。然后他会并行地向集群中的其他服务器节点来给自己投票。

选举的结果可能有3中结果：1）自己成为Leader 2）别人成为Leader 3）选票被瓜分，选举失败

三、日志复制

3.1 理想的日志复制

​​

3.2 会导致冲突的日志复制

​​

领导人和跟随者日志不一致场景，丢失或者多出日志条目可能会持续多个任期。例如，场景 f 可能会这样发生，某服务器在任期 2 的时候是领导人，已附加了一些日志条目到自己的日志中，但在提交之前就崩溃了；很快这个机器就被重启了，在任期 3 重新被选为领导人，并且又增加了一些日志条目到自己的日志中；在任期 2 和任期 3 的日志被提交之前，这个服务器又宕机了，并且在接下来的几个任期里一直处于宕机状态。

‍

在 Raft 算法中，领导人是通过强制跟随者直接复制自己的日志来处理不一致问题的。

要使得跟随者的日志进入和自己一致的状态，领导人必须找到最后两者达成一致的地方，然后删除跟随者从那个点之后的所有日志条目，并发送自己在那个点之后的日志给跟随者。所有的这些操作都在进行附加日志 RPCs 的一致性检查时完成。

‍

四、安全性

通过选举和日志复制，并不能保证每一个状态机会按照相同的顺序执行相同的指令。例如，一个跟随者可能会进入不可用状态同时领导人已经提交了若干的日志条目，然后这个跟随者可能会被选举为领导人并且覆盖这些日志条目。因此，需要在领导选举的时候增加一些限制来完善 Raft 算法。

4.1 选举限制

在任何基于领导人的一致性算法中，领导人都必须存储所有已经提交的日志条目。

4.2 提交之前任期内的日志条目

当领导人复制之前任期里的日志时，Raft 会为所有日志保留原始的任期号。

4.3 安全性论证

假设领导人完全性特性是不存在的，通过反推出矛盾来论证算法的安全性。

‍

• 一个关于 Raft 一致性算法的浓缩总结（不包括成员变换和日志压缩）

  特性	解释
  选举安全特性	对于一个给定的任期号，最多只会有一个领导人被选举出来（5.2 节）
  领导人只附加原则	领导人绝对不会删除或者覆盖自己的日志，只会增加（5.3 节）
  日志匹配原则	如果两个日志在某一相同索引位置日志条目的任期号相同，那么我们就认为这两个日志从头到该索引位置之间的内容完全一致（5.3 节）
  领导人完全特性	如果某个日志条目在某个任期号中已经被提交，那么这个条目必然出现在更大任期号的所有领导人中（5.4 节）
  状态机安全特性	如果某一服务器已将给定索引位置的日志条目应用至其状态机中，则其他任何服务器在该索引位置不会应用不同的日志条目（5.4.3 节）

‍

‍