【基于Raft的KV共识算法】-序：Raft概述

1.为什么会有Raft？

简单来说就是数据会随着业务和时间的增长，单机不能存的下，这个时候需要以某种方式切片分成多个分片（Shard、Partition、Region）。分片之后可以将单个数据集分散到多个机器上面。

但是随着集群的使用，单个机器的故障的概率会增大，所以为了保证CAP理论中的可用性，会将分片冗余多份在多个机器上面，每个冗余称之为一个副本，但如果有分片持续写入进来，从属该分片的多个副本，可能会由于网络问题、故障问题等导致数据不一致，这个时候需要引入共识算法，所以也就是为了保证多个副本之间的数据一致性。在Redis的相关主从问题上我们能够看到一些Raft的影子。

CAP理论

一致性（Consistency）

指系统中的所有节点在任何时刻看到的数据都是最新的，或者是一致的。例如，当一个节点更新了数据后，其他节点立即看到更新后的数据。

可用性（Availability）
指系统能够持续对外提供服务，即使部分节点出现故障，用户仍然可以访问系统并获得响应。

分区容错性（Partition Tolerance）
指系统能够容忍网络分区故障，即在部分网络通信失效的情况下，系统仍然能够正常运行。

根据CAP理论，一个分布式系统在设计时最多只能同时满足其中的两个特性。

2.Raft基本原理

首先Raft会把客户端的请求序列化成操作序列，也就是操作日志 Operation log，然后会确保Raft所有的服务器都会看到相同的日志。

每个Raft Server就是一个进程，运行在各自的服务器机器上，后续我们通过多线程来模拟这个点。Raft Server，很多地方也叫做Raft Peer、Raft Instance，是同一个意思。

通常业务中一个Raft Server会包含多个数据分片的状态机，即数据分片的一个副本，不同机器上的同一个数据分片的副本联合起来就是一个Raft Group，这样一个集群中就有多个Raft Group。比如下面这个图，绿色的Raft Group在node 1 2 4中联合起来了。

当某个Server宕机重启之后，Raft算法会负责将日志进行追评。

有超过一半的Sever存活，并且可以互相通信，Raft就可以正常运行，否则就会停止，不接受客户端来的新的请求。当Server超过一半了，就可以继续工作。

流程

在论文中可以看到对应的流程图，Raft的客户端就是Client。服务器Raft Server，组成Raft集群的单个进程。 状态机State Machine：每个Raft Server中都会有一个本地的状态机，可以理解为一个小型的KV存储，客户端的读取请求会转为操作日志Log，然后打到状态机里面。

简单来说就是：

1. 客户端发送请求：客户端向服务器发送一个请求（例如，设置变量的值）。
2. 日志记录：服务器的共识模块接收到请求后，将其作为日志条目追加到日志中。
3. 状态机应用：一旦日志条目被共识并持久化存储，服务器的状态机将应用这些日志条目，更新其内部状态。
4. 响应客户端：状态更新完成后，服务器将响应发送回客户端，告知操作结果。

为什么要以日志作为中间载体？

这里有几个点：

• 顺序保证：日志确保所有节点以相同的顺序执行相同的操作。这是实现一致性的关键，因为分布式系统中的节点可能在不同时间接收到相同的请求。
• 持久化存储：日志条目被持久化存储，这意味着即使节点发生故障，日志中记录的操作也不会丢失。这保证了系统的容错性。
• 可复制性：日志条目可以被复制到其他节点，确保所有节点最终都能达到相同的状态。这是实现高可用性和分区容错性的关键。
• 简化状态机操作：通过将操作记录在日志中，状态机只需要顺序地应用这些操作，而不需要处理并发操作的复杂性。这简化了状态机的设计和实现。
• 一致性检查：日志可以用于检查节点之间的一致性。例如，Raft算法中的领导者会检查跟随者节点的日志是否与自己的日志一致，以确保所有节点的状态一致。
• 故障恢复：在节点故障后，日志可以用于恢复状态机的状态。通过从日志中重新应用操作，故障节点可以快速恢复到与其他节点一致的状态。

3.实现思路

将每个Raft实例化一个定义好的结构体，每个Raft实例在逻辑上会维护一个操作序列，每个操作都有下标，从而完成共识的一个设计。

每个操作就是 日志条目 log entry，一旦日志条目在多个机子上达成了共识，就可以进行提交，然后就可以被应用在状态机，这样状态机就可以修改保存的数据了。

正常的Raft有几个关键的环节：领导者选举、日志同步、状态持久化、日志压缩、配置变更。
在论文中还有配置变更，这个部分通常是Server的个数进行增加或者删除，通常也是用于多个Raft Group的分裂和合并，这部分如果实现了Raft也被成为Multi-Raft。

任期

任期其实大家很好理解，比如班长半个学期选一次这个意思。

如果通信的时候网络有分区，那么某些Server被隔绝，就不知道其他的Server到了哪个任期，所以等重新通信之后，第一个要做的就是对齐任期，才能进行后期的通信。所有的RPC通信都必须对齐任期。

这里还有几个点，也侧面说明了任期的重要性和优先级。

1、低任期的 Peer 收到高任期的 Peer 任何信息后，会自动“跟上”（Follow）任期变成跟随者（Follower）。
2、高任期的 Peer 收到低任期 Peer 的任何请求时，会直接拒绝。

领导选举

Raft的领导拥有绝对的话语权，在任期内，日志里面是什么内容都是领导说了算。一个任期必须只有一个领导。同一个时刻可能会有多个领导，但是这些领导一定处于不同的任期中（可能会因为时间分区的原因导致有多个领导）。

因为权力很大，所以选举领导的时候需要慎之又慎，以此能够选出一个优秀的领导，也就是具备所有已提交日志的候选者才有可能作为领导（这个领导必须非常全面，可以这么理解）。

所以想选领导的时候一般都是比谁的日志更全面，更新。当某些跟随者投票之后，就需要重置选举钟，表示在这个时间段内不会再发起新的选举。

领导当选了之后，就要开始通过发送心跳的方式告诉其他节点，让其他节点收到心跳之后，重置选举时钟。

然后领导就会周期性的发出某些信息，直到某一时刻收到更高“任期”的消息，也就是需要换领导了。任期高，优先级就越高。比如说 Leader 与多数 Follower 发生了网络隔离后，也自动交权出去。

日志同步

领导收到客户端的请求之后，会将其序列化为日志，然后附带到周期性的广播心跳上，传给每个跟随者。

最简单的一种方式就是领导会把自己本地的所有日志都附加到心跳上，所有跟随者收到之后直接替换本地即可，但是这样会带来很大的通信代价，因此采用一种乐观+回撤的方法进行同步。

乐观：也就是一开始心跳不带任何的日志，只带一些标志信息过去，跟随者通过这些标志信息发现自己的日志跟领导完全一样，就直接回复领导一致即可，之后的心跳也不需要加任何的日志了。

回撤：如果跟随者发现自己的日志和领导不一样，就告诉领导下次发送心跳的时候需要附带日志了，下次领导就会附加一些末尾的日志，如果还是不一样，就要回撤更多，也就是多向前发送一些日志信息，直到跟随者回复肯定的消息。

这个标志信息就是领导 所附带日志 的 前一条日志信息的二元组<下标，任期>，如果心跳没有任何附加日志，那么这个标志信息就是领导最后一条日志的相关信息。

为了保证领导附带日志前总有一条日志，对日志初始化的时候会放一条空日志，从而避免一些边界条件的判断。

来一张论文里面的图，这里有个很核心的点。

Leader 不能直接宣布前任的“政令”（日志）生效，而要在本任期内发布“政令”（日志）后，通过“生效”本任期“政令”来间接“追认”前序任期的相关“政令”。

这是由于选举时会通过比最后一条日志的“大小”来决定是否 Leader 当选，因此前任的日志，如果没有通过本任期“盖棺定论”，是有可能被其他在 相同下标 具有更新日志的 Server 当选 Leader 后“冲掉的”，也就是上图 c、d、e 的情况——没有 4 日志的“压一道”， S5 是可以当选 Leader 的，之后 S1~S3 的 2 日志是有可能被 S5 的 3 的日志冲掉。

图中的S1-5是5个Server，然后就是对应的任期123。

图中 d 和 e 的结果是互斥的。其意思是如果我们在 c 中提交 2 是不对的，因为可能发生 d 中 2 被冲掉的情况；但是我们在 e 中通过提交 4 间接提交 2 就没有问题