作者：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的编码设计与基于字典序的遍历机制对革新造成的束缚。

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

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

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