TiKV 笔记 -Raft 复制状态机 -- 未完

作者： benmaoer 原文来源：https://tidb.net/blog/e6a8c25d

[toc]

理解 Raft 复制状态机才能更好的理解 TiKV 引擎，后续分成三篇文章由浅入深来逐步讲解 Raft 相关的内容：

• Raft 复制状态机

• TiKV 中的 Multi Raft

• TiKV 中关于 Raft 的优化

本文重点介绍 Raft 的入门基础，也就是 Raft 的复制状态机。

1. Raft 背景以及基础概念

1.1 Raft 提出背景

分布式存储系统通常通过维护多个副本来进行容错，提高系统的可用性。要实现此目标，就必须要解决分布式存储系统的最核心问题：维护多个副本的一致性。

首先需要解释一下什么是一致性（consensus）, 它是构建具有容错性（fault-tolerant）的分布式系统的基础。 在一个具有一致性的性质的集群里面，同一时刻所有的结点对存储在其中的某个值都有相同的结果，即对其共享的存储保持一致。集群具有自动恢复的性质，当少数结点失效的时候不影响集群的正常工作，当大多数集群中的结点失效的时候，集群则会停止服务（不会返回一个错误的结果）。一致性协议就是用来干这事的，用来保证即使在部分 (确切地说是小部分) 副本宕机的情况下，系统仍然能正常对外提供服务。

1.2 TiKV 为什么选择 Raft？

• Raft 提供了线性一致性的保证，适合数据库等一致性要求高的系统。

• Raft 过半节点失败不可用，延迟稳定，适合事务处理；对比全部节点失败才不可用，

• 工程实现成熟，实现简单。

• 选举算法、成员变更算法实现细节完备。

1.3 Raft 基础概念

1.3.1 Raft 复制状态机

一致性协议通常基于复制状态机，即所有结点都从同一个状态出发，都经过同样的一些指令，最后到达同一个状态。复制状态机用于解决分布式系统中的各种容错问题，例如具有单个 Leader 的大规模系统，GFS、HDFS 等等通常使用单独的复制状态机来进行 Leader 的选举和存储 Leader 崩溃后重新选举需要的配置信息。Chubby、Zookeeper 等都是复制状态机。复制状态机要能容忍很多错误场景。复制状态机的典型实现是基于复制日志，如下图所示：

复制状态机包含了三个组件：

状态机: 当我们说一致性的时候，实际就是在说要保证这个状态机的一致性。状态机会从日志里面取出所有的命令，然后顺序执行一遍，得到的结果就是我们对外提供的保证了一致性的数据。

Log: 保存了所有修改指令的日志。

一致性模块: 一致性模块算法就是用来保证写入的日志的一致性，这也是 Raft 算法核心内容。

状态机可以理解为一个确定的应用程序，所谓确定是指只要是相同的输入，那么任何状态机都会计算出相同的输出。至于如何实现日志完全一致的复制，则是 Raft 一致性模块（Consensus Module）需要做的事。

每个节点上存储了一个包含一系列指令的日志，复制状态机按序执行这些指令。每一个日志在相同的位置存放相同的指令，所以每一个状态机都执行了相同序列的指令。

1.3.2 Raft 节点状态

Raft 的节点被称为 peer，节点的状态是 Raft 算法的关键属性，在任何时候，Raft 节点可能处于以下三种状态：

• Leader：Leader 负责处理客户端的请求，同时还需要协调日志的复制。在任意时刻，最多允许存在 1 个 Leader，其他节点都是 Follower。注意，集群在选举期间可能短暂处于存在 0 个 Leader 的场景。

• Follower：Follower 是被动的，它们不主动提出请求，只是响应 Leader 和 Candidate 的请求。注意，节点之间的通信是通过 RPC 进行的。

• Candidate：Candidate 是节点从 Follower 转变为 Leader 的过渡状态。因为 Follower 是一个完全被动的状态，所以当需要重新选举时，Follower 需要将自己提升为 Candidate，然后发起选举。

下图展示了这些状态以及它们之间的转化：

从状态转换图可以看到，所有的节点都是从 Follower 开始，如果 Follower 经过一段时间后收不到来自 Leader 的心跳，那么 Follower 就认为需要 Leader 已经崩溃了，需要进行新一轮的选举，因此 Follower 的状态变更为 Candidate。Candidate 有可能被选举为 Leader，也有可能回退为 Follower。如果 Leader 发现自己已经过时了，它会主动变更为 Follower。Leader 如何发现自己过时了？下文会引入 Term 继续分析。

1.3.3 Term

Raft 的一个关键属性是任期（Term），在分布式系统中，由于节点的物理时间戳都不统一，因此需要一个逻辑时间戳来表明事件发生的先后顺序，Term 正是起到了逻辑时间戳的作用。Raft 的运行过程被划分为一系列任意长度的 Terms，一次 Leader 选举会开启一个新的 Term，如下图所示：

Terms 有连续单调递增的编号，每个 Term 开始于选举，这一阶段每个 Candidate 都试图成为 Leader。如果一个 Candidate 选举成功，它就在该 Term 剩余周期内履行 leader 职责。一次 Term 也可能选不出 Leader，这是因为可能多个 Candidate 都获得了相同数量的选票，此时下一次会进行下一次选举。

每个节点都会维护自己当前的 Term（Current Term），并且持久化存储 Current Term。当 Leader 宕机后再恢复，Leader 仍然会认为自己是 Leader，除非发现自己已经过时了。节点利用 Current Term 判断过时的信息。节点的 Term 在节点之间通信时改变：如果某个节点的当前 Term 小于其它节点，那么这个节点必须更新它的 Term，与集群其他节点保持一致；如果一个 Candidate 或者 Leader 发现自己的 Term 过期，它就必须要放下身段变成 Follower；如果某个节点收到一个过时的请求（拥有过时的 Term），它会拒绝该请求。

目前我们需要知道的是 Term 在 Raft 中是一个非常关键的属性，Term 始终保持单调递增，而 Raft 认为一个节点的 Term 越大，那么它所拥有的日志就越准确。

前面对 Raft 算法进行了简要的介绍，这里开始对它进行深入分析。Raft 实现一致性的机制是这样的：日志是由 Leader 到 Follower 的单向传递。也就是说 Leader 相当于一个总控节点，由它负责接受 Client 的请求，并且把日志发送各个 Follower，进行复制。也是只有 Leader 能决定何时提交一个日志。通过 Leader 机制，Raft 将一致性难题分解为三个相对独立的子问题：

• Leader 选举：一开始每个节点都是 Follower，那么需要决定由谁来做 Leader，这里延伸出 Leader 选举的问题，而且当 Leader 宕机的时候也需要重新进行选举。

• 日志复制：当 Leader 选举出来之后，需要把日志复制到每个 Follower。这里复制需要保证所有日志都有序且正确的复制到 Follower 上。也就是说 Follower 上的日志不管是顺序还是内容都要和 Leader 上的一样。

• 安全性：一但 Leader 把一项日志复制到绝大多数的 Follower 时，需要执行这个日志。这里的安全性是指所有的服务器都要在这同一个位置执行同一个 Log，通俗的说，就是集群中所有节点都需要按照相同的顺序执行相同的日志。