Raft learner

发表于 |

TiFlash 的整个 replication 机制建立在 Raft learner 协议之上。

在本文中介绍 Raft learner 相关的 case 以及优化，主要包括：

  • 涉及 Learner 的活性问题
  • Learner Snapshot
  • Learner Read
    • 作为前置，还会说明 Leader 的 Lease Read
    • 作为直接的扩展，还会说明 Stale Read

本文大部分是从 关于 TiKV、TiDB、TiFlash 的一些思考中取出的，并进行了扩展。

Learner 的总体作用

  • 新增的 Voter 节点以 Learner 角色先追进度
  • 观测 Raft Group 中的数据变更
  • 支持 Replica Read

Learner peer

活性

Add Learner

Raft 中添加一个 Learner 并不需要经过该 Learner。我引入了一些测试来描述相关的行为。

但是，如果 Learner peer 始终不 ready，则它会变为 pending-peer 甚至 down-peer。

Orphan Learner

Learner 尽管在 Raft Group 中，但不参与投票。所以当 Voter 节点因为 Region 被销毁（通常因为 merge）全部被销毁后，Learner 节点就无法找到 Leader 节点。对于 Voter 节点来说，这种情况它可以发起选举，然后发现其他节点上的 Tombstone 标记，从而确认 Region 已经被摧毁了。但因为 Learner 不参与投票，所以是无法发现这种情况的，从而僵死。

上述的卡死在之前需要等待 2h 之后触发存活性检查才会被发现，后续会发送一个 Tombstone 消息从而执行 gc peer 的操作。否则，就需要人工将僵死的 Region peer 设置为 Tombstone 状态。因此，后续进行了优化，将 Tombstone 消息的发送间隔调小。

Learner 可能因为多种原因导致丢失 Leader，从而变为孤儿节点：

  1. 在 Region 销毁的场景如 CommitMerge，target region 的 Voter 至少可以在 Leader 销毁之后，因为超时触发选举，从而启动自毁。而 Learner 则不行，会 miss leader 然后卡死
    特别地，CommitMerge 本身对 Source Peer 也会有检查，这里还可能造成连环等待。比如如果在等待 Source 追数据，就会 Yield 为 WaitMergeSource。如果卡在 CommitMerge 上，那么后续的 RemovePeer 也无法执行。
  2. 在 ConfChange 中，如果删除了某个 Learner，但又没有能够将该日志复制给 Learner，那么稍后 Learner 就不会得到 Leader 的任何消息，从而一样卡死。
  3. 在 BatchSplit 中，如果新 Split 出来的 Region 在 TiFlash apply BatchSplit 命令前就在所有 Voter 节点中被删除的话，后续 TiFlash 节点即使 apply 完 BatchSplit，也无法再收到任何日志，因为 Leader peer 已经不存在了。

Snapshot

Raft Log GC 也需要 respect Learner 的进度，原因：

  • 诸如 TiFlash 这样的引擎，底层存储非 Rocksdb，因此不能直接 ingest。因此对 Raft Snapshot 进行转换存在大量 CPU 开销。并且，Snapshot 本身被用来 bootstrap 一个 Region peer，所以在它被处理完之前，无法处理后续的 append。因此，异步转换 Snapshot 的收益不是特别大，不如后续引入 Remote Decoder 去 offload 一部分开销。
  • 进一步，如果 Snapshot 处理时间过长，则可能超过下一轮的 Raft Log GC，导致需要处理新一轮的 Snapshot，由此往复，该副本始终无法追齐进度。

Follower Replication 和 Follower Snapshot

Follower Snapshot 的好处有：

  1. 因为是有处于一个 Zone 的 Follower 发送 Snapshot，所以可能更快。并且跨 Zone 流量也少
  2. 减少 Leader 的负担

TiFlash 做了 Learner Snapshot，相比 Follower Snapshot，它甚至是一个异构的 Snapshot。CRDB 做了类似的工作，称为 Delegate Snapshot。TiKV 目前还不支持。

Lease read

为了讲明白 Learner Read，首先需要了解 Leader 的 Lease read，因此就在这里一起讨论了。

Why Lease？

如果没有 lease，那么 Raft 集群中读取要么就是提交一条新的日志，要么就是去询问所有的节点，从而确认自己依旧是 leader。lease 的作用是保证一段时间中，只有某个节点可能是 leader。

lease 的主要实现问题是，不同节点上的时间不一定一致，也就是可能出现 clock drift。

是否有单独的 Lease Leader？

CRDB 的实现中，有单独的 lease leader，而 TiKV 的 lease leader 一定是 raft leader。因此就形成了一些区别：

  1. 在时钟依赖上，TiKV 依赖 NTP，CRDB 依赖 HLC。
  2. 在“谁操作读”上，TiKV 通过 Raft Leader 来读，crdb 通过 lease leader 来读。

Lease 绑定 node 还是 raft group？

CRDB 将 Lease 和机器绑定而不是和 Data Range 绑定，从而减少网络开销。它的做法是每个 Data Range 的 “Leader” 会去维护一个 meta 表（也是一个 Data Range）上的 liveness 记录。我理解是以一个比较低的频率去更新 liveness 记录，因为如果不是节点挂了下线，或者是重新调度到当前 Raft Leader 的节点上这两种情况，Raft Leader 就还是同一个，那么就完全没有必要续期。而 TiKV 的绑定方式则必须要求 Lease 是比 Election Timeout 要短的。

当某个 node 宕掉之后，CRDB 还是要重新选出一个新的 Lease Leader，而这个依旧是通过 Raft 选举来实现的。

当然，对于 meta 表，就不能像上面那样去做了。否则会导致循环依赖。对于 meta 表自己的 Lease，是通过 expiration time 来维护的。此时：

  1. 如果一个节点依旧能够不停地 propose，那么它就能够一直续期 lease
  2. 否则，下一个尝试对这个 range 读写的 node 会成为 leader

Learner read

关于读

Raft 的一个问题就是读的时候无论是 Leader 还是 Follower 都需要 Read Index。比如，对 Leader 而言，它需要问 quorum 自己当前是否还是 Leader。TiKV 一般 Leader Read 提供两种方案，第一种是 read_local，也就是 Leader 节点上 lease 读，另一种是 read_index，也就是在不确定自己是否还是 Leader 的时候，进行 ReadIndex。

Follower Read

TiDB 支持多种读取方式，例如最近 Peer、Leader、Follower、Learner、自适应等多种模式，这些依赖于 Follower Read，在这之前都需要从 Raft Leader 读取。

不同于 ParallelRaft 和 MultiPaxos 的部分实现，TiKV 会串行地 apply raft log。

  1. 这样的好处是，更容易通过 Read Index 实现 Follower Read 了。TiKV 在这一点上行得通，主要还是因为它的数据和 Raft Group 绑定的缘故。也就是以 scheduler 为代价来实现 Partitioning，从而减少各个 Raft Group 的压力。
  2. 这样的坏处是，引入了更强的全序关系。因为我们实现共识层的目的是服务上层的事务层，而事务层本身就允许并行事务以任意的顺序被提交，所以在共识层排成强序，实际上是多余的。当然，Partitioning 分成多个 Raft Group 能减少这部分的强序关系的数量。

总的来说，TiKV 实现的 Follower Read，是通常被称作 Strong Follower Read 的类型。

Non-stale Read

从共识层上来讲，强一致或者说线性一致有明确的定义。CRDB将其“推广”到事务层之上，也就是归结到所谓的 non-stale 读上。因为 CRDB 只有 leaseholder 也就是所谓的 Leader 能服务读请求。不过还是推广到有 Follower Read 的场景下。此时，在任意的节点上：

  1. 在 SERIALIZABLE 下，读事务应该能看到在它之前已经提交了的所有的写事务。这里的“它之前”我理解取决于如何给事务排序，但至少要在事务的第一个读之前。比如 Percolator 模型中就是 start_ts。
  2. 在 RC 级别上，事务中的每一个读语句能看到在它之前已经提交了的所有的写事务。

Stale Read

Stale Read 的作用是让读请求被分配到任一节点上，从而避免某热点机器，或者跨数据中心的 read index 请求产生的延迟。

这样的事务只能服务读，并且 staleness 也是需要被严格控制的。

Stale Read 是读 ts 时间点上所有已提交事务的旧数据。因为读不到最新的写入，所以不是强一致的。但它仍然保持有全局事务记录一致性，并且不破坏隔离级别。我理解可能就是所谓的 Time travel query。

一般提供两种：

  1. 精确时间戳
  2. 有界时间
    在给定的时间范围内选择一个合适的时间戳，该时间戳能保证所访问的副本上不存在开始于这个时间戳之前且还没有提交的相关事务，即能保证所访问的可用副本上执行读取操作而且不会被阻塞。
    因此这样的读取方式能提高可用性。

使用 Stale Read 需要 NTP 的支持。

所以它并不是“弱一致读”，无论从哪一个节点返回的结果都是一致的，不会出现 A 返回 1000 笔记录，而 B 返回 1111 笔记录的情况。

Learner Read

不同于 Follower，Learner 不是 Voter，没有选举功能。所以 Learner Read 和 Follower Read 有不同。
Learner Read 在 TiFlash 场景下更为丰富，在 TiFlash 章节讨论。

Learner Read 和 commit_ts

即使有在 read index 的时候推进 max ts 的机制，依然会发生在收到 Leader 关于带有 read_ts 的 Read Index 请求的回复后，在 Wait Index 超过返回的 applied_index 之后，看到具有更小的 commit_ts 的提交。但这种情况并不会导致问题，因为在 applied_index 之前，我们至少可以看到对应的锁。

比如 read_ts 是 10，返回了 applied_index 是 1000。那么在 apply 到 1001 时，可能它对应了一个 commit_ts 为 5 的事务。这里可以参考我对并发事务的讨论。

Read index

TiFlash 自己给自己发送一个 ReadIndex Command，后者会触发一个 ReadIndex Message。为什么要这么做呢？因为走 ReadIndex Command 的链路才是完整的，否则会丢掉包括要求 Concurrency manager 推高 max_ts 的部分。

  1. 对 Leader，会检查 Lease 并续约，之后再 Read
  2. 对 Follower，会推动 Raft 发送 RaftIndex 类型的 RaftMessage 给 Leader。这个 RaftMessage 包含一个 raft_cmdpb::ReadIndexRequest 作为 entry.data。

在处理 ReadIndex RaftMessage 时候，会推进 maxts 并且返回 memlock。

具体来说：

  1. 根据 read tso 和 range 构造一个 kvrpcpb::ReadIndexRequest
  2. ReadIndex 接受这个 kvrpcpb::ReadIndexRequest
  3. 创建一个 raft_cmdpb::Request
    其类型为 CmdType::ReadIndex。将 kvrpcpb::ReadIndexRequest 中的数据移动到 raft_cmdpb::Request 中。
  4. 通过 RaftRouter 发送这个请求，并等待回调。

这里 ReadIndexRequest 中传入的 start_ts 会间接推高 min_commit_ts。其原理是一个事务涉及多个 key，则这些 key 依次 prewrite 的时候，后面 prewrite 的 key 的 min_commit_ts 会因为 max_ts 变得更高，尽管前面 key 的 min_commit_ts 是一直不变的。最终事务提交的 ts 是所有的 key 的 min_commit_ts 取最大。

Batch read index

  1. 在同一个查询中，如果一个 Region 上已经被做过 read index，则复用
  2. 在同一个 Region 上的每个 Read index 请求前，首先查询历史记录，看看是否有对应 ts 的记录可以复用
  3. 同一个 Region 上的多个 Read index 请求组成一个 batch，用其中的最大的 ts 去请求 TiKV leader。如果发现有 memlock，则返回这个 lock。这说明这个 ts 上有 lock，而其他的 ts 则不确定需要重试。如果返回没有 lock 则使用最大的 index 来重试

注意，没有 memlock 并不代表没有 lock。一个 key 上是否有 lock，还需要读 lock cf 来判断。memlock 的引入是 Async Commit 导致的。memlock 指的是在某个短暂阶段，事务层上有一些锁在内存中，还没有写到 raftstore。

Remote Read 机制

TiFlash 中存在 Remote Read 机制，在 BatchCop 的 prepare 阶段，会分析哪些 Region 是可以本地读的，哪些 Region 是需要从其他 TiFlash 读的。在存算分离版本的 TiFlash 中，CN 通常都需要进行 Remote Read 从对应的 WN 读取最新的数据。

在 Remote Read 的过程中，也会触发 Resolve Lock 机制，从而推动 TiKV 去判断事务提交与否。这个通常对应了 Cop 请求的发送和处理。Remote Read 请求可能最终还是发送给自己。