截止到2020/10，根据官网的资料整理的pingcap对raft算法的优化

1.multi raft,不同于大部分的单raft，tidb采用每个数据分片都分隔开的multi raft，采用自己的分片分裂算法可以保证每个raft group的节点数量不大，这样能保证大数据情况下raft的性能，又能支持节点的横向扩展

2.lease read读优化，平常的读操作需要走一遍raft流程，效率很低效，优化一点的readindex算法可以提高效率，并且安全性可以得到保障；更优化一点的lease read更将readindex算法中的确认当前时间leader是raft组的leader的步骤优化掉，又节省了一次网络时间，不过需要依赖于cpu时钟的安全性，不同服务器的时钟频率不同，可能会出问题。tidb两种方式都有提供，不过由于本身代码的限制，lease read实现方式和论文中略有不同，不是靠心跳来确认，而是靠写操作来确认。

3.Batch and Pipeline优化，tidb认为raft理论按照论文来写，性能完全不行，所以需要增加优化。一个是批优化，也就是每次不是发单个，而是缓存一批一起。Pipeline优化是说，因为网络通常情况下是稳定的，所以可以不用等反馈直接发下一个next位置的日志，如果出错了就调一下next日志，然后重新发

4.Append Log Parallelly优化，简单来说就是leader节点落盘日志和给follower节点发送日志同时进行，因为根据论文来说，leader需要大多数follower落盘日志后才能落盘日志。一，如果大多数follower落盘了日志，leader自然需要落盘日志,可以提前落盘；二，如果大多数follower没有落盘日志，leader已经落盘日志，可以重新发送让大多follower落盘，如果不行，则说明当前集群没有大多数follower节点正常运行，集群崩溃；三，如果大多数follower落盘了日志，但是leader落盘失败，则说明leader节点crash了，重新选举，也不会造成影响

5.Asynchronous Apply优化，就是日志的commit线程和apply线程并发执行。因为当一个 log 被大部分节点 append 之后，我们就可以认为这个 log 被 committed 了，被 committed 的 log 在什么时候被 apply 都不会再影响数据的一致性。所以当一个 log 被 committed 之后，可以用另一个线程去异步的 apply 这个 log。这样处理，集群的吞吐和并发量就会上去了。

6.Asynchronous Lease Read优化，就是读写分离，在另一个线程异步实现 Lease Read，保证 Raft 的 write 流程不会影响到 read。

7.Follower Read优化，直接管leader要commitindex，等follower运行到这个index，就返回，，虽然还是要过一次网络，但是可以减轻leader的负担

 

 下面的是个人觉得重要的内容的截取

基于 Raft 构建弹性伸缩的存储系统的一些实践

在 TiKV 中，我们选择了按 range 的 sharding 策略，每一个 range 分片我们称之为 region，因为我们需要对 scan 的支持，而且存储的数据基本是有关系表结构的，我们希望同一个表的数据尽量的在一起。另外在 TiKV 中每一个 region 采用 Raft 算法在多个物理节点上保证数据的一致性和高可用。

从社区的多个 Raft 实现来看，比如 Etcd / LogCabin / Consul 基本都是单一 raft group 的实现，并不能用于存储海量的数据，所以他们主要的应用场景是配置管理，很难直接用来存储大量的数据，毕竟单个 raft group 的参与节点越多，性能越差，但是如果不能横向的添加物理节点的话，整个系统没有办法 scale。

scale 的办法说来也很简单，采用多 raft group，这就很自然的和上面所说的 sharding 策略结合起来了，也就是每一个分片作为一个 raft group，这是 TiKV 能够存储海量数据的基础。但是管理动态分裂的多 raft group 的复杂程度比单 group 要复杂得多，目前 TiKV 是我已知的开源项目中实现 multiple raft group 的仅有的两个项目之一。

正如之前提到过的我们采用的是按照 key range 划分的 region，当某一个 region 变得过大的时候（目前是 64M），这个 region 就会分裂成两个新的 region，这里的分裂会发生在这个 region 所处的所有物理节点上，新产生的 region 会组成新的 raft group。

 How do we build TiDB

这是整个 TiKV 的架构图，从这个看来，整个集群里面有很多 Node，比如这里画了四个 Node，分别对应了四个机器。每一个 Node 上可以有多个 Store，每个 Store 里面又会有很多小的 Region，就是说一小片数据，就是一个 Region 。从全局来看所有的数据被划分成很多小片，每个小片默认配置是 64M，它已经足够小，可以很轻松的从一个节点移到另外一个节点，Region 1 有三个副本，它分别在 Node1、Node 2 和 Node4 上面， 类似的Region 2，Region 3 也是有三个副本。每个 Region 的所有副本组成一个 Raft Group, 整个系统可以看到很多这样的 Raft groups。

如果一个 Region 太大以后我们会自动做 SPLIT，这是非常好玩的过程，有点像细胞的分裂。 

TiKV 源码解析系列 - multi-raft 设计与实现

因为 TiKV 目标是支持 100 TB+ 以上的数据，一个 Raft 集群是铁定没法支持这么多数据的，所以我们需要使用多个 Raft 集群，也就是 Multi Raft。在 TiKV 里面，Multi Raft 的实现是在 Raftstore 完成的，代码在 raftstore/store 目录。

因为我们要支持 Multi Raft，所以我们需要将数据进行分片处理，让每个 Raft 单独负责一部分数据。使用 Range，主要原因是能更好的将相同前缀的 key 聚合在一起，便于 scan 等操作，这个 Hash 是没法支持的，当然，在 split/merge 上面 Range 也比 Hash 好处理很多，很多时候只会涉及到元信息的修改，都不用大范围的挪动数据。当然，Range 有一个问题在于很有可能某一个 Region 会因为频繁的操作成为性能热点，当然也有一些优化的方式，譬如通过 PD 将这些 Region 调度到更好的机器上面，提供 Follower 分担读压力等。

TiKV 功能介绍 - Lease Read

大家知道，因为每次 read 都需要走 Raft 流程，所以性能是非常的低效的，所以大家通常都不会使用。

我们可以认为，如果当前 leader 能确定一定是 leader，那么我们就可以直接在这个 leader 上面读取数据。

第一种就是 ReadIndex，使用了 heartbeat 的方式来让 leader 确认自己是 leader，省去了 Raft log 那一套流程。

1. 将当前自己的 commit index 记录到一个 local 变量 ReadIndex 里面。
2. 向其他节点发起一次 heartbeat，如果大多数节点返回了对应的 heartbeat response，那么 leader 就能够确定现在自己仍然是 leader。
3. Leader 等待自己的状态机执行，直到 apply index 超过了 ReadIndex，这样就能够安全的提供 linearizable read 了。
4. Leader 执行 read 请求，将结果返回给 client。

使用 ReadIndex，我们也可以非常方便的提供 follower read 的功能，follower 收到 read 请求之后，直接给 leader 发送一个获取 ReadIndex 的命令，leader 仍然走一遍之前的流程，然后将 ReadIndex 返回给 follower，follower 等到当前的状态机的 apply index 超过 ReadIndex 之后，就可以 read 然后将结果返回给 client 了。

但这里，需要注意，实现 ReadIndex 的时候有一个 corner case，在 etcd 和 TiKV 最初实现的时候，我们都没有注意到。也就是 leader 刚通过选举成为 leader 的时候，这时候的 commit index 并不能够保证是当前整个系统最新的 commit index，所以 Raft 要求当 leader 选举成功之后，首先提交一个 no-op 的 entry，保证 leader 的 commit index 成为最新的。

虽然 ReadIndex 比原来的 Raft log read 快了很多，但毕竟还是有 Heartbeat 的开销，所以我们可以考虑做更进一步的优化。

leader 发送 heartbeat 的时候，会首先记录一个时间点 start，当系统大部分节点都回复了 heartbeat response，那么我们就可以认为 leader 的 lease 有效期可以到 start + election timeout / clock drift bound 这个时间点。

虽然采用 lease 的做法很高效，但仍然会面临风险问题，也就是我们有了一个预设的前提，各个服务器的 CPU clock 的时间是准的，即使有误差，也会在一个非常小的 bound 范围里面，如果各个服务器之间 clock 走的频率不一样，有些太快，有些太慢，这套 lease 机制就可能出问题。

TiKV 使用了 lease read 机制，主要是我们觉得在大多数情况下面 CPU 时钟都是正确的，当然这里会有隐患，所以我们也仍然提供了 ReadIndex 的方案。TiKV 的 lease read 实现在原理上面跟 Raft 论文上面的一样，但实现细节上面有些差别，我们并没有通过 heartbeat 来更新 lease，而是通过写操作。对于任何的写入操作，都会走一次 Raft log，所以我们在 propose 这次 write 请求的时候，记录下当前的时间戳 start，然后等到对应的请求 apply 之后，我们就可以续约 leader 的 lease。

TiKV 功能介绍 - Raft 的优化

raft流程是一个典型的顺序操作，如果真的按照这样的方式来写，那性能是完全不行的.

我们通常不会每次写入一个值，而是会用一个 WriteBatch 缓存一批修改，然后在整个写入。 size 来限制每次最多可以发送多少数据。

通常情况下面，只要 Leader 跟 Follower 建立起了连接，我们都会认为网络是稳定互通的。所以当 Leader 给 Follower 发送了一批 log 之后，它可以直接更新 NextIndex，并且立刻发送后面的 log，不需要等待 Follower 的返回。如果网络出现了错误，或者 Follower 返回一些错误，Leader 就需要重新调整 NextIndex，然后重新发送 log 了。

因为 append log 会涉及到落盘，有开销，所以我们完全可以在 Leader 落盘的同时让 Follower 也尽快的收到 log 并 append。

所以整个 Raft 流程就可以变成：

1. Leader 接受一个 client 发送的 request。
2. Leader 将对应的 log 发送给其他 follower 并本地 append。
3. Leader 继续接受其他 client 的 requests，持续进行步骤 2。
4. Leader 发现 log 已经被 committed，在另一个线程 apply。
5. Leader 异步 apply log 之后，返回结果给对应的 client。

使用 asychronous apply 的好处在于我们现在可以完全的并行处理 append log 和 apply log，虽然对于一个 client 来说，它的一次 request 仍然要走完完整的 Raft 流程，但对于多个 clients 来说，整体的并发和吞吐量是上去了。

TiDB 新特性漫谈：从 Follower Read 说起

Leader 只要告诉 Follower 当前最新的 Commit Index 就够了，因为无论如何，即使这个 Follower 本地没有这条日志，最终这条日志迟早都会在本地 Apply。

TiDB 目前的 Follower Read 正是如此实现的，当客户端对一个 Follower 发起读请求的时候，这个 Follower 会请求此时 Leader 的 Commit Index，拿到 Leader 的最新的 Commit Index 后，等本地 Apply 到 Leader 最新的 Commit Index 后，然后将这条数据返回给客户端，非常简洁。

 

对于第一点，虽然确实不满足线性一致性了，但是好在是永远返回最新的数据，另外我们也证明了这种情况并不会破坏我们的事务隔离级别（Snapshot Isolation），证明的过程在这里就不展开了，有兴趣的读者可以自己想想。

对于第二个问题，虽然对于延迟来说，不会有太多的提升，但是对于提升读的吞吐，减轻 Leader 的负担还是很有帮助的。总体来说是一个很好的优化。

1. 因为 TiKV 的异步 Apply 机制，可能会出现一个比较诡异的情况：破坏线性一致性，本质原因是由于 Leader 虽然告诉了 Follower 最新的 Commit Index，但是 Leader 对这条 Log 的 Apply 是异步进行的，在 Follower 那边可能在 Leader Apply 前已经将这条记录 Apply 了，这样在 Follower 上就能读到这条记录，但是在 Leader 上可能过一会才能读取到。
2. 这种 Follower Read 的实现方式仍然会有一次到 Leader 请求 Commit Index 的 RPC，所以目前的 Follower read 实现在降低延迟上不会有太多的效果。