# Raft 与 Multi Raft

__*Raft*__
__*leader*__
__*follower*__
__*candidate*__
__*Raft Group*__
__*Multi Raft*__

![left](./student-guide/diagram/RaftAndMultiRaft_aa_001_20220511.png)
-------------------------------------------------------------
首先,同步一下咱们在 Raft 共识算法中的几个名词:

1. leader:集群中的管理者,所有客户端（client）的流量都从 leader 这里经过,正常情况下只有一个 leader,会周期性的向 follower 发出心跳维持统治。当发现自己不是 leader 的时候会转为 follower。

2. follower:集群中的被管理者,只会对其它服务器的命令做出响应。在长时间得不到 leader 响应之后会转为 candidate。

3. candidate:集群的候选者,会发起投票试图当选 leader。

在之前的课程中我们了解到,TiKV 使用 Raft 共识算法实现了分布式环境下面数据的强一致性,TiDB 数据库只能通过 leader 进行写入,leader 会将写入指令通过 log 的形式复制到 followers,当集群的大多数节点都收到了这个 log,我们就认为这个 log 是 committed,可以 apply 到数据持久化存储引擎（ State Machine ）里面。

TiDB 默认提供的是三个副本支持,这三个副本形成了一个 Raft Group。因为一个 Raft Group 处理的数据量有限,所以我们会将数据切分成多个 Raft Group,我们叫做 Multi Raft。切分的方式是按照 range 进行切分,也就是我们会将数据的 key 按照字节序进行排序,也就是一个无限的 key - value 的 map数据结构,然后将其切分成一段一段（连续）的 key range,每个 key range 当成一个 Region。

两个相邻的 Region 之间不允许出现间隙,也就是前面一个 Region 的 end key 就是后一个 Region 的 start key。Region 的 range 使用的是前闭后开的模式 [start, end),对于 key start 来说,它就属于这个 Region,但对于 end 来说,它其实属于下一个 Region。

TiKV 的 Region 会有最大 size 的限制,当超过这个阈值之后,就会分裂成两个 Region,譬如 [a, c) -> [a, b) + [b, c),当然,如果 Region 里面没有数据,或者只有很少的数据,也会跟相邻的 Region 进行合并,变成一个更大的 Region,譬如 [a, b) + [b, c) -> [a, c)。

上面说的,多个 Region 形成的多个 Raft Group,我们就称之为 Multi Raft。

接下来,我们会着重介绍 Raft 共识算法对于 TiKV 的几个重要功能:
1. 日志复制
2. Leader 选举