关于kv存储:一种KV存储的GC优化实践

作者：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 的参数会响应调整，保障现网写入的时延。

• 小结

阶段3之后，能够保障写入和然而从 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 的编码设计与基于字典序的遍历机制对革新造成的束缚。

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

这个过程中，咱们认为有几点比拟要害：

• 在第一次设计的时候，应该从 多方面进行掂量，思考好某种设计会带来的副作用。
• 在 上线之前 ，对各种场景（例如不同的指令，数据大小）进行 充沛测试，提前发现出问题及时修改计划。
• 曾经是 存量数据 的前提下，更应该对原有的设计进行从新梳理。兴许原有的设计是有问题的，遵循以后 设计的 束缚，找出问题关键点，基于现有的设计尝试找到空间去调整，兴许存在调优的空间。