作者：vivo 互联网服务器团队- Yuan Jian Wei

从内部需求出发，我们基于 TiKV 设计了一款兼容 Redis 的 KV 存储。基于 TiKV 的数据存储机制，对于窗口数据的处理以及过期数据的 GC 问题却成为一个难题。本文希望基于从 KV 存储的设计开始讲解，到 GC 设计的逐层优化的过程，从问题的存在到不同层面的分析，可以给读者在类似的优化实践中提供一种参考思路。

一、背景介绍

当前公司内部没有统一的 KV 存储服务，很多业务都将 Redis 集群当作 KV 存储服务在使用，但是部分业务可能不需要 Redis 如此高的性能，却承担着巨大的机器资源成本（内存价格相对磁盘来说更加昂贵）。为了降低存储成本的需求，同时尽可能减少业务迁移的成本，我们基于 TiKV 研发了一套磁盘 KV 存储服务。

1.1 架构简介

以下对这种 KV 存储(下称磁盘 KV)的架构进行简单描述，为后续问题描述做铺垫。

1.1.1 系统架构

磁盘 KV 使用目前较流行的计算存储分离架构，在 TiKV 集群上层封装计算层（后称 Tula）模拟 Redis 集群（对外表现是不同的 Tula 负责某些 slot 范围），直接接入业务 Redis 客户端。

图 1：磁盘 KV 架构图示

业务写入数据基于 Tula 转换成 TiKV 中存储的 KV 对，基于类似的方式完成业务数据的读取。

注意：Tula 中会选举出一个 leader，用于进行一些后台任务，后续详细说。

1.1.2 数据编码

TiKV 对外提供的是一种 KV 的读写功能，但是 Redis 对外提供的是基于数据结构提供读写能力（例如 SET，LIST 等），因此需要基于 TiKV 现有提供的能力，将 Redis 的数据结构进行编码，并且可以方便地在 TiKV 中进行读写。

TiKV 提供的 API 比较简单：基于 key 的读写接口，以及基于字典序的迭代器访问。

因此，Tula 层面基于字典序的机制，对 Redis 的数据结构基于字典序进行编码，便于访问。

注意：TiKV 的 key 是可以基于字典序进行遍历（例如基于某个前缀进行遍历等），后续的编码，机制基本是基于字典序的特性进行设计。

为了可以更好地基于字典序排列的搜索特性下对数据进行读写，对于复杂的数据结构，我们会使用另外的空间去存放其中的数据（例如 SET 中的 member，HASH 中的 field）。而对于简单的数据结构（类似 STRING），则可以直接存放到 key 对应的 value 中。

为此，我们在编码设计上，会分为 metaKey 和 dataKey。metaKey 是基于用户直接访问的 key 进行编码，是编码设计中直接对外的一层；dataKey 则是 metaKey 的存储指向，用来存放复杂数据结构中的具体内部数据。

另外，为了保证访问的数据一致性，我们基于 TiKV 的事务接口进行对 key 的访问。

（1）编码 &字段

以下以编码中的一些概念以及设定，对编码进行简述。

key 的编码规则如下：

图 2：key 编码设计图示

以下对字段进行说明

• namespace

为了方便在一个 TiKV 集群中可以存放不同的磁盘 KV 数据，我们在编码的时候添加了前缀 namespace，方便集群基于这个 namespace 在同一个物理 TiKV 空间中基于逻辑空间进行分区。

• dbid

因为原生 Redis 是支持 select 语句，因此在编码上需要预留字段表示 db 的 id，方便后续进行 db 切换（select 语句操作）的时候切换，表示不同的 db 空间。

• role

用于区分是哪种类型的 key。

对于简单的数据结构（例如 STRING），只需要直接在 key 下面存储对应的 value 即可。

但是对于一些复杂的数据结构（例如 HASH，LIST 等），如果在一个 value 下把所有的元素都存储了，对与类似 SADD 等指令的并发，为了保证数据一致性，必然可以预见其性能不足。

因此，磁盘 KV 在设计的时候把元素数据按照独立的 key 做存储，需要基于一定的规则对元素 key 进行访问。这样会导致在 key 的编码上，会存在 key 的 role 字段，区分是用户看到的 key（metaKey），还是这种元素的 key（dataKey）。

其中，如果是 metaKey，role 固定是 M；如果是 dataKey，则是 D。

• keyname

在 metaKey 和 dataKey 的基础上，可以基于 keyname 字段可以较方便地访问到对应的 key。

• suffix

针对 dataKey，基于不同的 Redis 数据结构，都需要不同的 dataKey 规则进行支持。因此此处需要预留 suffix 区间给 dataKey 在编码的时候预留空间，实现不同的数据类型。

以下基于 SET 类型的 SADD 指令,对编码进行简单演示：

图 3: SADD 指令的编码设计指令图示

1. 基于 userKey,通过 metaKey 的拼接方式,拼接 metaKey 并且访问

2. 访问 metaKey 获取 value 中的

3. 基于 value 中的 uuid,生成需要的 dataKey

4. 写入生成的 dataKey

（2）编码实战

编码实战中，会以 SET 类型的实现细节作为例子，描述磁盘 KV 在实战中的编码细节。

在这之前，需要对 metaKey 的部分实现细节进行了解

（3）metaKey 存储细节

所有的 metaKey 中都会存储下列数据。

图 4：metaKey 编码设计图示

1. uuid：每一个 metaKey 都会有一个对应的 uuid，表示这个 key 的唯一身份。

2. create_time：保存该元数据的创建时间

3. update_time: 保存该元数据的最近更新时间

4. expire_time: 保存过期时间

5. data_type: 保存该元数据对应的数据类型，例如 SET，HASH，LIST，ZSET 等等。

6. encode_type: 保存该数据类型的编码方式

（4）SET 实现细节

基于 metaKey 的存储内容，以下基于 SET 类型的数据结构进行讲解。

SET 类型的 dataKey 的编码规则如下：

• keyname：metaKey 的 uuid

• suffix：SET 对应的 member 字段

因此，SET 的 dataKey 编码如下：

图 5：SET 数据结构 dataKey 编码设计图示

以下把用户可以访问到的 key 称为 user-key。集合中的元素使用 member1，member2 等标注。

这里，可以梳理出访问逻辑如下：

图 6：SET 数据结构访问流程图示

简述上图的访问逻辑：

1. 基于 user-key 拼接出 metaKey，读取 metaKey 的 value 中的 uuid。

2. 基于 uuid 拼接出 dataKey，基于 TiKV 的字典序遍历机制获取 uuid 下的所有 member。

1.1.3 过期 &GC 设计

对标 Redis，目前在 user-key 层面满足过期的需求。

因为存在过期的数据，Redis 基于过期的 hash 进行保存。但是如果磁盘 KV 在一个 namespace 下使用一个 value 存放过期的数据，显然在 EXPIRE 等指令下存在性能问题。因此，这里会有独立的编码支持过期机制。

鉴于过期的数据可能无法及时删除（例如 SET 中的元素），对于这类型的数据需要一种 GC 的机制，把数据完全清空。

（1）编码设计

针对过期以及 GC（后续会在机制中详细说），需要额外的编码机制，方便过期和 GC 机制的查找，处理。

• 过期编码设计

为了可以方便地找到过期的 key（下称 expireKey），基于字典序机制，优先把过期时间的位置排到前面，方便可以更快地得到 expireKey。

编码格式如下：

图 7：expireKey 编码设计图示

其中：

• expire-key-prefix：标识该 key 为 expireKey，使用固定的字符串标识

• slot：4 个字节，标识 slot 值，对 user-key 进行 hash 之后对 256 取模得到，方便并发扫描的时候线程可以分区扫描，减少同 key 的事务冲突

• expire-time：标识数据的过期时间

• user-key：方便在遍历过程中找到 user-key，对 expireKey 做下一步操作

• GC 编码设计

目前除了 STRING 类型，其他的类型因为如果在一次过期操作中把所有的元素都删除，可能会存在问题：如果一个 user-key 下面的元素较多，过期进度较慢，这样 metaKey 可能会长期存在，占用空间更大。

因此使用一个 GC 的 key（下称 gcKey）空间，安排其他线程进行扫描和清空。

编码格式如下：

图 8：gcKey 编码设计图示

（2）机制描述

基于前面的编码，可以对 Tula 内部的过期和 GC 机制进行简述。

因为过期和 GC 都是基于事务接口，为了减少冲突，Tula 的 leader 会进行一些后台的任务进行过期和 GC。

• 过期机制

因为前期已经对过期的 user-key 进行了 slot 分开，expireKey 天然可以基于并发的线程进行处理，提高效率。

图 9：过期机制处理流程图示

简述上图的过期机制：

1. 拉起各个过期作业协程，不同的协程基于分配的 slot，拼接协程下的 expire-key-prefix，扫描 expireKey

2. 扫描 expireKey，解析得到 user-key

3. 基于 user-key 拼接得到 metaKey，访问 metaKey 的 value，得到 uuid

4. 根据 uuid，添加 gcKey

5. 添加 gcKey 成功后，删除 metaKey

就目前来说，过期速度较快，而且 key 的量级也不至于让磁盘 KV 存在容量等过大负担，基于 hash 的过期机制目前表现良好。

• GC 机制

目前的 GC 机制比较落后：基于当前 Tula 的 namespace 的 GC 前缀（gc-key-prefix），基于 uuid 进行遍历，并且删除对应的 dataKey。

图 10：GC 机制处理流程图示

简述上图的 GC 机制：

1. 拉起一个 GC 的协程，扫描 gcKey 空间

2. 解析扫描到的 gcKey，可以获得需要 GC 的 uuid

3. 基于 uuid，在 dataKey 的空间中基于字典序，删除对应 uuid 下的所有 dataKey

因此，GC 本来就是在 expire 之后，会存在一定的滞后性。

并且，当前的 GC 任务只能单线程操作，目前来说很容易造成 GC 的迟滞。

1.2 问题描述

1.2.1 问题现象

业务侧多次反馈，表示窗口数据（定期刷入重复过期数据）存在的时候，磁盘 KV 占用的空间特别大。

我们使用工具单独扫描对应的 Tula 配置 namespace 下的 GC 数据结合，发现确实存在较多的 GC 数据，包括 gcKey，以及对应的 dataKey 也需要及时进行删除。

1.2.2 成因分析

现网的 GC 过程速度比不上过期的速度。往往 expireKey 都已经没了，但是 gcKey 很多，并且堆积。

这里的问题点在于：前期的设计中，gcKey 的编码并没有像 expireKey 那样提前进行了 hash 的操作，全部都是 uuid。

如果有一个类似的 slot 字段可以让 GC 可以使用多个协程进行并发访问，可以更加高效地推进 GC 的进度，从而达到满足优化 GC 速度的目的，窗口数据的场景可以得到较好的处理。

下面结合两个机制的优劣，分析存在 GC 堆积的原因。

图 11：GC 堆积成因图示

简单来说，上图的流程中：

1. 过期的扫描速度以及处理速度很快，expireKey 很快及时的被清理并且添加到 gcKey 中

2. GC 速度很慢，添加的 gcKey 无法及时处理和清空

从上图分析可以知道：如果窗口数据的写入完全超过的 GC 的速度的话，必然导致 GC 的数据不断堆积，最后导致所有磁盘 KV 的存储容量不断上涨。

二、优化

2.1 目标

分析了原始的 GC 机制之后，对于 GC 存在滞后的情况，必然需要进行优化。

如何加速 GC 成为磁盘 KV 针对窗口数据场景下的强需求。

但是，毕竟 TiKV 集群的性能是有上限的，在进行 GC 的过程也应该照顾好业务请求的表现。

这里就有了优化的基本目标：在不影响业务的正常使用前提下，对尽量减少 GC 数据堆积，加速 GC 流程。

2.2 实践

2.2.1 阶段 1

在第一阶段，其实并没有想到需要对 GC 这个流程进行较大的变动，看可不可以从当前的 GC 流程中进行一些简单调整，提升 GC 的性能。

• 分析

GC 的流程相对简单：

图 12：GC 流程图示

可以看到，如果存在 gcKey，会触发一个批次的删除 gcKey 和 dataKey 的流程。

最初设计存在 sleep 以及批次的原因在于减少 GC 对 TiKV 的影响，降低对现网的影响。

因此这里可以调整的范围比较有限：按照批次进行控制，或者缩短批次删除之间的时间间隔。

• 尝试

缩短 sleep 时间（甚至缩短到 0，去掉 sleep 过程），或者提高单个批次上限。

• 结果

但是这里原生 sleep 时间并不长，而且就算提高批次个数，毕竟单线程，提高并没有太大。

• 小结

原生 GC 流程可变动的范围比较有限，必须打破这种局限才可以对 GC 的速度得以更好的优化。

2.2.2 阶段 2

第一阶段过后，发现原有机制确实局限比较大，如果需要真的把 GC 进行加速，最好的办法是在原有的机制上看有没有办法类似 expireKey 一样给出并发的思路，可以和过期一样在质上提速。

但是当前现网已经不少集群在使用磁盘 KV 集群，并发提速必须和现网存量 key 设计一致前提下进行调整，解决现网存量的 GC 问题。

• 分析

如果有一种可能，更改 GC 的 key 编码规则，类似模拟过期 key 的机制，添加 slot 位置，应该可以原生满足这种多协程并发进行 GC 的情况。

但是基于当前编码方式，有没有其他办法可以较好地把 GC key 分散开来？

把上述问题作为阶段 2 的分析切入点，再对当前的 GC key 进行分析：

图 13：gcKey 编码设计图示

考虑其中的各个字段：

• namespace：同一个磁盘 KV 下 GC 空间的必然一致

• gc-key-prefix：不管哪个磁盘 KV 的字段必然一致

• dbid：现网的磁盘 KV 都是基于集群模式，dbid 都是 0

• uuid：映射到对应的 dataKey

分析下来，也只有 uuid 在整个 gcKey 的编码中是变化的。

正因为 uuid 的分布应该是足够的离散，此处提出一种比较大胆的想法：基于 uuid 的前若干位当作 hash slot，多个协程可以基于不同的前缀进行并发访问。

因为 uuid 是一个 128bit 长度（8 个 byte）的内容，如果拿出前面的 8 个 bit（1 个 byte），可以映射到对应的 256 个 slot。

• 尝试

基于上述分析，uuid 的前一个 byte 作为 hash slot 的标记，这样，GC 流程变成：

图 14：基于 uuid 划分 GC 机制图示

简单描述下阶段 2 的 GC 流程：

1. GC 任务使用协程，分成 256 个任务

2. 每一个任务基于前缀扫描的时候，从之前扫描到 dbid 改成后续补充一个 byte，每个协程被分配不同的前缀，进行各自的任务执行

3. GC 任务执行逻辑和之前单线程逻辑保持不变，处理 gcKey 以及 dataKey。

这样，基于 uuid 的离散，GC 的任务可以拆散成并发协程进行处理。

这样的优点不容置疑，可以较好地进行并发处理，提高 GC 的速度。

• 结果

基于并发的操作，GC 的耗时可以缩短超过一半。后续会有同样条件下的数据对比。

• 小结

阶段 2 确实带来一些突破：再保留原有 gcKey 设计的前提下，基于拆解 uuid 的方法使得 GC 的速度有质的提高。

但是这样会带来问题：对于 dataKey 较多（可以理解为一个 HASH，或者一个 SET 的元素较多）的时候，删除操作可能对 TiKV 的性能带来影响。这样带来的副作用是：如果并发强度很高地进行 GC，因为 TiKV 集群写入（无论写入还是删除）性能是一定的，这样是不是可能导致业务的正常写入可能带来了影响？

如何可以做到兼顾磁盘 KV 日常的写入和 GC？这成了下一个要考虑的问题。

2.2.3 阶段 3

阶段 2 之后，GC 的速度是得到了较大的提升，但是在测试过程中发现，如果在过程中进行写入，写入的性能会大幅度下降。如果因为 GC 的性能问题忽视了现网的业务正常写入，显然不符合线上业务的诉求。

磁盘 KV 的 GC 还需要一种能力，可以调节 GC。

• 分析

如果基于阶段 2，有办法可以在业务低峰期的时候进行更多的 GC，高峰期的时候进行让路，也许会是个比较好的方法。

基于上面的想法，我们需要在 Tula 层面可以比较直接地知道当前磁盘 KV 的性能表现到底到怎样的层面，当前是负荷较低还是较高，应该用怎样的指标去衡量当前磁盘 KV 的性能？

• 尝试

此处我们进行过以下的一些摸索：

• 基于 TiKV 的磁盘负载进行调整

• 基于 Tula 的时延表现进行调整

• 基于 TiKV 的接口性能表现进行调整

暂时发现 TiKV 的接口性能表现调整效果较好，因为基于磁盘负载不能显式反馈到 Tula 的时延表现，基于 Tula 的时延表现应该需要搜集所有的 Tula 时延进行调整（对于同一个 TiKV 集群接入多个不同的 Tula 集群有潜在影响），基于 TiKV 的接口性能表现调整可以比较客观地得到 Tula 的性能表现反馈。

在阶段 1 中，有两个影响 GC 性能的参数：

• sleep 时延

• 单次处理批次个数

加上阶段 2 并发的话，会有三个可控维度，控制 GC 的速度。

调整后的 GC 流程如下：

图 15：自适应 GC 机制图示

阶段 3 对 GC 添加自适应机制，简述如下：

①开启协程，搜集 TiKV 节点负载

• 发现 TiKV 负载较高，控制 GC 参数，使得 GC 缓慢进行

• 发现 TiKV 负载较低，控制 GC 参数，使得 GC 激进进行

②开启协程，进行 GC

• 发现不需要 GC，控制 GC 参数，使得 GC 缓慢进行

• 结果

基于监控表现，可以明显看到，GC 不会一直强制占据 TiKV 的所有性能。当 Tula 存在正常写入的时候，GC 的参数会响应调整，保证现网写入的时延。

• 小结

阶段３之后，可以保证写入和但是从 TiKV 的监控上看，有时候 GC 并没有完全把 TiKV 的性能打满。

是否有更加高效的 GC 机制，可以继续提高磁盘 KV 的 GC 性能？

2.2.4 阶段 4

基于阶段 3 继续尝试找到 GC 性能更高的 GC 方式。

• 分析

基于阶段 3 的优化，目前基于单个节点的 Tula 应该可以达到一个可以较高强度的 GC，并且可以给现网让路的一种情况。

但是，实际测试的时候发现，基于单个节点的删除，速度应该还有提升空间（从 TiKV 的磁盘 IO 可以发现，并没有占满）。

这里的影响因素很多，例如我们发现 client-go 侧存在获取 tso 慢的一些报错。可能是使用客户端不当等原因造成。

但是之前都是基于单个 Tula 节点进行处理。既然每个 Tula 都是模拟了 Redis 的集群模式，被分配了 slot 区间去处理请求。这里是不是可以借鉴分片管理数据的模式，在 GC 的过程直接让每个 Tula 管理对应分片的 GC 数据？

这里先 review 一次优化阶段 2 的解决方式：基于 uuid 的第一个 byte，划分成 256 个区间。leader Tula 进行处理的时候基于 256 个区间。

反观一个 Tula 模拟的分片范围是 16384（0-16383），而一个 byte 可以表示 256（0-255）的范围。

如果使用 2 个 byte，可以得到 65536（0-65535）的范围。

这样，如果一个 Tula 可以基于自己的分片范围，映射到 GC 的范围，基于 Tula 的 Redis 集群模拟分片分布去做基于 Tula 节点的 GC 分片是可行的。

假如某个 Tula 的分片是从 startSlot 到 endSlot（范围：0-16383），只要经过简单的映射：

• startHash = startSlot* 4

• endHash = （endSlot + 1）* 4 - 1

基于这样的映射，可以直接把 Tula 的 GC 进行分配，而且基本在优化阶段 2 中无缝衔接。

• 尝试

基于分析得出的机制如下：

图 16：多 Tula 节点 GC 机制图示

可以简单地描述优化之后的 GC 流程：

① 基于当前拓扑划分当前 Tula 节点的 startHash 与 endHash

② 基于步骤 1 的 startHash 与 endHash，Tula 分配协程进行 GC，和阶段 2 基本一致：

• GC 任务使用协程，分成多个任务。

• 每一个任务基于前缀扫描的时候，从之前扫描到 dbid 改成后续补充 2 个 byte，每个协程被分配不同的前缀，进行各自的任务执行。

• GC 任务执行逻辑和之前单线程逻辑保持不变，处理 gcKey 以及 dataKey。

基于节点分开之后，可以满足在每个节点并发地前提下，各个节点不相干地进行 GC。

• 结果

基于并发的操作，GC 的耗时可以在阶段 2 的基础上继续缩短。后续会有同样条件下的数据对比。

• 小结

基于节点进行并发，可以更加提高 GC 的效率。

但是我们在这个过程中也发现，client-go 的使用上可能存在不当的情况，也许调整 client-go 的使用后可以获得更高的 GC 性能。

三、优化结果对比

我们基于一个写入 500W 的 SET 作为写入数据。其中每一个 SET 都有一个元素，元素大小是 4K。

因为阶段 2 和阶段 4 的提升较大，性能基于这两个进行对比：

表 1：各阶段 GC 耗时对照表

可以比较明显地看出：

1. 阶段 2 之后的 GC 时延明显缩减

2. 阶段 4 之后的 GC 时延可以随着节点数的增长存在部分缩减

四、后续计划

阶段 4 之后，我们发现 Tula 的单节点性能应该有提升空间。我们会从以下方面进行入手：

1. 补充更多的监控项目，让 Tula 更加可视，观察 client-go 的使用情况。

2. 基于上述调整跟进 client-go 在不同场景下的使用情况，尝试找出 client-go 在使用上的瓶颈。

3. 尝试调整 client-go 的使用方式，在 Tula 层面提高从指令执行，到 GC，过期的性能。

五、总结

回顾我们从原来的单线程 GC，到基于编码机制做到了多线程 GC，到为了减少现网写入性能影响，做到了自适应 GC，再到为了提升 GC 性能，进行多节点 GC。

GC 的性能提升阶段依次经历了以下过程：

1. 单进程单协程

2. 单进程多协程

3. 多进程多协程

突破点主要在于进入阶段 2（单进程多协程）阶段，设计上的困难主要来源于：已经存在存量数据，我们需要兼顾存量数据的数据分布情况进行设计，这里我们必须在考虑存量的 gcKey 存在的前提下，原版 gcKey 的编码设计与基于字典序的遍历机制对改造造成的约束。

但是这里基于原有的设计，还是有空间进行一些二次设计，把原有的问题进行调优。

这个过程中，我们认为有几点比较关键：

• 在第一次设计的时候，应该从多方面进行衡量，思考好某种设计会带来的副作用。

• 在上线之前，对各种场景（例如不同的指令，数据大小）进行充分测试，提前发现出问题及时修正方案。

• 已经是存量数据的前提下，更应该对原有的设计进行重新梳理。也许原有的设计是有问题的，遵循当前设计的约束，找出问题关键点，基于现有的设计尝试找到空间去调整，也许存在调优的空间。