Mulit Raft Group

通过对 Raft 协议的描述我们知道：用户在对一组 Raft 系统进行更新操作时必须先经过 Leader，再由 Leader 同步给大多数 Follower。而在实际运用中，一组 Raft 的 Leader 往往存在单点的流量瓶颈，流量高便无法承载，同时每个节点都是全量数据，所以会受到节点的存储限制而导致容量瓶颈，无法扩展。

Mulit Raft Group 正是通过把整个数据从横向做切分，分为多个 Region 来解决磁盘瓶颈，然后每个 Region 都对应有独立的 Leader 和一个或多个 Follower 的 Raft 组进行横向扩展，此时系统便有多个写入的节点，从而分担写入压力，图如下： multi-raft

具体细节可以参考TiKV 的文章

Multi-Raft需要解决的一些核心问题：

  1. 数据何如分片
  2. 分片中的数据越来越大，需要分裂产生更多的分片，组成更多Raft-Group
  3. 分片的调度，让负载在系统中更平均（分片副本的迁移，补全，Leader切换等等）
  4. 一个节点上，所有的Raft-Group复用链接（否则Raft副本之间两两建链，链接爆炸了）
  5. 如何处理stale的请求（例如Proposal和Apply的时候，当前的副本不是Leader、分裂了、被销毁了等等） Snapshot如何管理（限制Snapshot，避免带宽、CPU、IO资源被过度占用）

数据何如分片

通常的数据分片算法就是 Hash 和 Range，TiKV 使用的 Range 来对数据进行数据分片。为什么使用 Range，主要原因是能更好的将相同前缀的 key 聚合在一起，便于 scan 等操作，这个 Hash 是没法支持的，当然，在 split/merge 上面 Range 也比 Hash 好处理很多，很多时候只会涉及到元信息的修改，都不用大范围的挪动数据。

当然，Range 有一个问题在于很有可能某一个 Region 会因为频繁的操作成为性能热点，当然也有一些优化的方式，譬如通过 PD 将这些 Region 调度到更好的机器上面，提供 Follower 分担读压力等。

总之，在 TiKV 里面，我们使用 Range 来对数据进行切分，将其分成一个一个的 Raft Group，每一个 Raft Group，我们使用 Region 来表示。

分片如何调度

Elasticell实现细节 作为参考: 这部分的思路就和TiKV完全一致了。PD负责调度指令的下发，PD通过心跳收集调度需要的数据，这些数据包括：节点上的分片的个数，分片中leader的个数，节点的存储空间，剩余存储空间等等。一些最基本的调度:

  1. PD发现分片的副本数目缺少了，寻找一个合适的节点，把副本补全
  2. PD发现系统中节点之间的分片数相差较多，就会转移一些分片的副本，保持系统中所有节点的分片数目大致相同（存储均衡）
  3. PD发现系统中节点之间分片的Leader数目不太一致，就会转移一些副本的Leader，保持系统中所有节点的分片副本的Leader数目大致相同（读写请求均衡）

新的分片如何形成Raft-Group

假设这个分片1有三个副本分别运行在Node1,Node2,Node3三台机器上，其中Node1机器上的副本是Leader，分片的大小限制是1GB。

当分片1管理的数据量超过1GB的时候，分片1就会分裂成2个分片，分裂后，分片1修改数据范围，更新Epoch，继续服务。

分片2形也有三个副本，分别也在Node1，Node2，Node3上，这些是元信息，但是只有在Node1上存在真正被创建的副本实例，Node2，Node3并不知道这个信息。这个时候Node1上的副本会立即进行Campaign Leader的操作，这个时候，Node2和Node3会收到来自分片2的Vote的Raft消息(整个描述指的是Leader Election)，Node2，Node3发现分片2在自己的节点上并没有副本，那么就会检查这个消息的合法性和正确性，通过后，立即创建分片2的副本，刚创建的副本没有任何数据，创建完成后会响应这个Vote消息，也一定会选择Node1的副本为Leader，选举完成后，Node1的分片2的Leader会给Node2，Node3的副本直接发送Snapshot，最终这个新的Raft-Group形成并且对外服务。

按照Raft的协议，分片2在Node1 的副本成为Leader后不应该直接给Node2，Node3发送snapshot，但是这里我们沿用了TiKV的设计，Raft初始化的Log Index是5，那么按照Raft协议，Node1上的副本需要给Node2，Node3发送AppendEntries，这个时候Node1上的副本发现Log Index小于5的Raft Log不存在，所以就会转为直接发送Snapshot。

Snapshot如何管理

我们的底层存储引擎使用的是RocksDB，这是一个LSM的实现，支持对一个范围的数据进行Snapshot和Apply Snapshot，我们基于这个特性来做。Raft中有一个RPC用于发送Snapshot数据，但是如果把所有的数据放在这个RPC里面，那么会有很多问题：

  • 一个RPC的数据量太大（取决于一个分片管理的数据，可能上GB，内存吃不消）
  • 如果失败，整体重试代价太大
  • 难以流控

我们修改为这样：

  • Raft的snapshot RPC中的数据存放，snapshot文件的元信息（包括分片的ID，当前Raft的Term，Index，Epoch等信息）
  • 发送Raft snapshot的RPC后，异步发送具体数据文件
  • 数据文件分Chunk发送，重试的代价小
  • 发送 Chunk的链接和Raft RPC的链接不复用
  • 限制并行发送的Chunk个数，避免snapshot文件发送影响正常的Raft RPC
  • 接收Raft snapshot的分片副本阻塞，直到接收完毕完整的snapshot数据文件

如何处理stale的请求

由于分片的副本会被调度（转移，销毁），分片自身也会分裂（分裂后分片所管理的数据范围发生了变化），所以在Raft的Proposal和Apply的时候，我们需要检查Stale请求，如何做呢？其实还是蛮简单的，TiKV使用Epoch的概念，我们沿用了下来。一个分片的副本有2个Epoch，一个在分片的副本成员发生变化的时候递增，一个在分片数据范围发生变化的时候递增，在请求到来的时候记录当前的Epoch，在Proposal和Apply的阶段检查Epoch，让客户端重试Stale的请求。