TiKV 是如何存取数据的（上）

TiKV 由 Rust 语言编写，源码地址： https://github.com/tikv/tikv "TiKV is a distributed transactional key-value database, originally created to complement TiDB. "

作者：唐刘 siddontang

本文会详细的介绍 TiKV 是如何处理读写请求的，通过该文档，同学们会知道 TiKV 是如何将一个写请求包含的数据更改存储到系统，并且能读出对应的数据的。

本文分为上下两篇，在上篇中，我们将介绍一些基础知识，便于大家去理解后面的流程。

基础知识

Raft

TiKV 使用 Raft 一致性算法来保证数据的安全，默认提供的是三个副本支持，这三个副本形成了一个 Raft Group。

当 Client 需要写入某个数据的时候，Client 会将操作发送给 Raft Leader，这个在 TiKV 里面我们叫做 Propose，Leader 会将操作编码成一个 entry，写入到自己的 Raft Log 里面，这个我们叫做 Append。

Leader 也会通过 Raft 算法将 entry 复制到其他的 Follower 上面，这个我们叫做 Replicate。Follower 收到这个 entry 之后也会同样进行 Append 操作，顺带告诉 Leader Append 成功。

当 Leader 发现这个 entry 已经被大多数节点 Append，就认为这个 entry 已经是 Committed 的了，然后就可以将 entry 里面的操作解码出来，执行并且应用到状态机里面，这个我们叫做 Apply。

在 TiKV 里面，我们提供了 Lease Read，对于 Read 请求，会直接发给 Leader，如果 Leader 确定自己的 lease 没有过期，那么就会直接提供 Read 服务，这样就不用走一次 Raft 了。如果 Leader 发现 lease 过期了，就会强制走一次 Raft 进行续租，然后在提供 Read 服务。

Multi Raft

因为一个 Raft Group 处理的数据量有限，所以我们会将数据切分成多个 Raft Group，我们叫做 Region。切分的方式是按照 range 进行切分，也就是我们会将数据的 key 按照字节序进行排序，也就是一个无限的 sorted 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, b) -> [a, ab) + [ab, b)，当然，如果 Region 里面没有数据，或者只有很少的数据，也会跟相邻的 Region 进行合并，变成一个更大的 Region，譬如 [a, ab) + [ab, b) -> [a, b)

Percolator

对于同一个 Region 来说，通过 Raft 一致性协议，我们能保证里面的 key 操作的一致性，但如果我们要同时操作多个数据，而这些数据落在不同的 Region 上面，为了保证操作的一致性，我们就需要分布式事务。

譬如我们需要同时将 a = 1，b = 2 修改成功，而 a 和 b 属于不同的 Region，那么当操作结束之后，一定只能出现 a 和 b 要么都修改成功，要么都没有修改成功，不能出现 a 修改了，但 b 没有修改，或者 b 修改了，a 没有修改这样的情况。

最通常的分布式事务的做法就是使用 two-phase commit，也就是俗称的 2PC，但传统的 2PC 需要有一个协调者，而我们也需要有机制来保证协调者的高可用。这里，TiKV 参考了 Google 的 Percolator，对 2PC 进行了优化，来提供分布式事务支持。

Percolator 的原理是比较复杂的，需要关注几点：

首先，Percolator 需要一个服务 timestamp oracle (TSO) 来分配全局的 timestamp，这个 timestamp 是按照时间单调递增的，而且全局唯一。任何事务在开始的时候会先拿一个 start timestamp (startTS)，然后在事务提交的时候会拿一个 commit timestamp (commitTS)。

Percolator 提供三个 column family (CF)，Lock，Data 和 Write，当写入一个 key-value 的时候，会将这个 key 的 lock 放到 Lock CF 里面，会将实际的 value 放到 Data CF 里面，如果这次写入 commit 成功，则会将对应的 commit 信息放到入 Write CF 里面。

Key 在 Data CF 和 Write CF 里面存放的时候，会把对应的时间戳给加到 Key 的后面。在 Data CF 里面，添加的是 startTS，而在 Write CF 里面，则是 commitCF。

假设我们需要写入 a = 1，首先从 TSO 上面拿到一个 startTS，譬如 10，然后我们进入 Percolator 的 PreWrite 阶段，在 Lock 和 Data CF 上面写入数据，如下：

Lock CF: W a = lock

Data CF: W a_10 = value

后面我们会用 W 表示 Write，R 表示 Read，D 表示 Delete，S 表示 Seek。

当 PreWrite 成功之后，就会进入 Commit 阶段，会从 TSO 拿一个 commitTS，譬如 11，然后写入：

Lock CF: D a

Write CF: W a_11 = 10

当 Commit 成功之后，对于一个 key-value 来说，它就会在 Data CF 和 Write CF 里面都有记录，在 Data CF 里面会记录实际的数据，Write CF 里面则会记录对应的 startTS。

当我们要读取数据的时候，也会先从 TSO 拿到一个 startTS，譬如 12，然后进行读：

Lock CF: R a

Write CF: S a_12 -> a_11 = 10

Data CF: R a_10

在 Read 流程里面，首先我们看 Lock CF 里面是否有 lock，如果有，那么读取就失败了。如果没有，我们就会在 Write CF 里面 seek 最新的一个提交版本，这里我们会找到 11，然后拿到对应的 startTS，这里就是 10，然后将 key 和 startTS 组合在 Data CF 里面读取对应的数据。

上面只是简单的介绍了下 Percolator 的读写流程，实际会比这个复杂的多。

RocksDB

TiKV 会将数据存储到 RocksDB，RocksDB 是一个 key-value 存储系统，所以对于 TiKV 来说，任何的数据都最终会转换成一个或者多个 key-value 存放到 RocksDB 里面。

每个 TiKV 包含两个 RocksDB 实例，一个用于存储 Raft Log，我们后面称为 Raft RocksDB，而另一个则是存放用户实际的数据，我们称为 KV RocksDB。

一个 TiKV 会有多个 Regions，我们在 Raft RocksDB 里面会使用 Region 的 ID 作为 key 的前缀，然后再带上 Raft Log ID 来唯一标识一条 Raft Log。譬如，假设现在有两个 Region，ID 分别为 1，2，那么 Raft Log 在 RocksDB 里面类似如下存放：

1_1 -> Log {a = 1}

1_2 -> Log {a = 2}

…

1_N -> Log {a = N}

2_1 -> Log {b = 2}

2_2 -> Log {b = 3}

…

2_N -> Log {b = N}

因为我们是按照 range 对 key 进行的切分，那么在 KV RocksDB 里面，我们直接使用 key 来进行保存，类似如下：

a -> N

b -> N

里面存放了两个 key，a 和 b，但并没有使用任何前缀进行区分。

RocksDB 支持 Column Family，所以能直接跟 Percolator 里面的 CF 对应，在 TiKV 里面，我们在 RocksDB 使用 Default CF 直接对应 Percolator 的 Data CF，另外使用了相同名字的 Lock 和 Write。

PD

TiKV 会将自己所有的 Region 信息汇报给 PD，这样 PD 就有了整个集群的 Region 信息，当然就有了一张 Region 的路由表，如下：

当 Client 需要操作某一个 key 的数据的时候，它首先会向 PD 问一下这个 key 属于哪一个 Region，譬如对于 key a 来说，PD 知道它属于 Region 1，就会给 Client 返回 Region 1 的相关信息，包括有多少个副本，现在 Leader 是哪一个副本，这个 Leader 副本在哪一个 TiKV 上面。

Client 会将相关的 Region 信息缓存到本地，加速后续的操作，但有可能 Region 的 Raft Leader 变更，或者 Region 出现了分裂，合并，Client 会知道缓存失效，然后重新去 PD 获取最新的信息。

PD 同时也提供全局的授时服务，在 Percolator 事务模型里面，我们知道事务开始以及提交都需要有一个时间戳，这个就是 PD 统一分配的。

基础知识就介绍到这里，下篇我们将详细的介绍 TiKV 的读写流程