介绍一种KV存储的GC优化实践
从内部需求出发，我们基于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指令的编码设计指令图示
基于userkey,通过metakey的拼接方式,拼接metakey并且访问
访问metakey获取value中的
基于value中的uuid,生成需要的datakey
写入生成的datakey
（2）编码实战
编码实战中，会以set类型的实现细节作为例子，描述磁盘kv在实战中的编码细节。
在这之前，需要对metakey的部分实现细节进行了解
（3）metakey存储细节
所有的metakey中都会存储下列数据。
图4：metakey编码设计图示
uuid：每一个metakey都会有一个对应的uuid，表示这个key的唯一身份。
create_time：保存该元数据的创建时间
update_time: 保存该元数据的最近更新时间
expire_time: 保存过期时间
data_type: 保存该元数据对应的数据类型，例如set，hash，list，zset等等。
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数据结构访问流程图示
简述上图的访问逻辑：
基于user-key拼接出metakey，读取metakey的value中的uuid。
基于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：过期机制处理流程图示
简述上图的过期机制：
拉起各个过期作业协程，不同的协程基于分配的slot，拼接协程下的expire-key-prefix，扫描expirekey
扫描expirekey，解析得到user-key
基于user-key拼接得到metakey，访问metakey的value，得到uuid
根据uuid，添加gckey
添加gckey成功后，删除metakey
就目前来说，过期速度较快，而且key的量级也不至于让磁盘kv存在容量等过大负担，基于hash的过期机制目前表现良好。
gc机制
目前的gc机制比较落后：基于当前tula的namespace的gc前缀（gc-key-prefix），基于uuid进行遍历，并且删除对应的datakey。
图10：gc机制处理流程图示
简述上图的gc机制：
拉起一个gc的协程，扫描gckey空间
解析扫描到的gckey，可以获得需要gc的uuid
基于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堆积成因图示
简单来说，上图的流程中：
过期的扫描速度以及处理速度很快，expirekey很快及时的被清理并且添加到gckey中
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流程：
gc任务使用协程，分成256个任务
每一个任务基于前缀扫描的时候，从之前扫描到dbid改成后续补充一个byte，每个协程被分配不同的前缀，进行各自的任务执行
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耗时对照表
可以比较明显地看出：
阶段2之后的gc时延明显缩减
阶段4之后的gc时延可以随着节点数的增长存在部分缩减
四、后续计划
阶段4之后，我们发现tula的单节点性能应该有提升空间。我们会从以下方面进行入手：
补充更多的监控项目，让tula更加可视，观察client-go的使用情况。
基于上述调整跟进client-go在不同场景下的使用情况，尝试找出client-go在使用上的瓶颈。
尝试调整client-go的使用方式，在tula层面提高从指令执行，到gc，过期的性能。
五、总结
回顾我们从原来的单线程gc，到基于编码机制做到了多线程gc，到为了减少现网写入性能影响，做到了自适应gc，再到为了提升gc性能，进行多节点gc。
gc的性能提升阶段依次经历了以下过程：
单进程单协程
单进程多协程
多进程多协程
突破点主要在于进入阶段2（单进程多协程）阶段，设计上的困难主要来源于：已经存在存量数据，我们需要兼顾存量数据的数据分布情况进行设计，这里我们必须在考虑存量的gckey存在的前提下，原版gckey的编码设计与基于字典序的遍历机制对改造造成的约束。
但是这里基于原有的设计，还是有空间进行一些二次设计，把原有的问题进行调优。
这个过程中，我们认为有几点比较关键：
在第一次设计的时候，应该从多方面进行衡量，思考好某种设计会带来的副作用。
在上线之前，对各种场景（例如不同的指令，数据大小）进行充分测试，提前发现出问题及时修正方案。
已经是存量数据的前提下，更应该对原有的设计进行重新梳理。也许原有的设计是有问题的，遵循当前设计的约束，找出问题关键点，基于现有的设计尝试找到空间去调整，也许存在调优的空间。
无线充电是未来智能手机的充电未来
双电源自动开关的应用与维护说明
盘点2016自动驾驶热点事件TOP10
显示企业加速布局Micro LED,AR时代未来皆可期
太阳诱电将支持 Bluetooth® 5 的无线通信模块的使用温度提高到+105℃
介绍一种KV存储的GC优化实践
魅蓝Note6和小米5X哪个拍照最好
8AI/DI/DO混合信号转RS-485/232信号采集数据模块
无线电测向仪DF2020T接线图
魅族Pro7什么时候上市？最新消息：魅族Pro7真机图曝光！2K全屏+电子墨水屏，瞬间完爆小米、华为！
全差分可编高速放大器LMH6881的主要特性和典型应用电路分析
苹果官方上架翻新iPhone6S/6S Plus 最低3000元起并提供保修服务
索尼PSVita游戏掌机将停止生产和出货，将永远离我们而去了
LG计划明年发布LG G7,将首次带来屏下指纹解锁
粒子加速器的加速原理是啥呢？
基于51单片机秒表计时
磁敏二极管构成的磁场检测电路
摩根大通报告:台积电最快2024年2纳米可量产
矩形平面阵列天线旁瓣电平优化的遗传算法
AEC-Q200车用额定功率电阻
一、背景介绍
当前公司内部没有统一的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指令的编码设计指令图示
基于userkey,通过metakey的拼接方式,拼接metakey并且访问
访问metakey获取value中的
基于value中的uuid,生成需要的datakey
写入生成的datakey
（2）编码实战
编码实战中，会以set类型的实现细节作为例子，描述磁盘kv在实战中的编码细节。
在这之前，需要对metakey的部分实现细节进行了解
（3）metakey存储细节
所有的metakey中都会存储下列数据。
图4：metakey编码设计图示
uuid：每一个metakey都会有一个对应的uuid，表示这个key的唯一身份。
create_time：保存该元数据的创建时间
update_time: 保存该元数据的最近更新时间
expire_time: 保存过期时间
data_type: 保存该元数据对应的数据类型，例如set，hash，list，zset等等。
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数据结构访问流程图示
简述上图的访问逻辑：
基于user-key拼接出metakey，读取metakey的value中的uuid。
基于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：过期机制处理流程图示
简述上图的过期机制：
拉起各个过期作业协程，不同的协程基于分配的slot，拼接协程下的expire-key-prefix，扫描expirekey
扫描expirekey，解析得到user-key
基于user-key拼接得到metakey，访问metakey的value，得到uuid
根据uuid，添加gckey
添加gckey成功后，删除metakey
就目前来说，过期速度较快，而且key的量级也不至于让磁盘kv存在容量等过大负担，基于hash的过期机制目前表现良好。
gc机制
目前的gc机制比较落后：基于当前tula的namespace的gc前缀（gc-key-prefix），基于uuid进行遍历，并且删除对应的datakey。
图10：gc机制处理流程图示
简述上图的gc机制：
拉起一个gc的协程，扫描gckey空间
解析扫描到的gckey，可以获得需要gc的uuid
基于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堆积成因图示
简单来说，上图的流程中：
过期的扫描速度以及处理速度很快，expirekey很快及时的被清理并且添加到gckey中
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流程：
gc任务使用协程，分成256个任务
每一个任务基于前缀扫描的时候，从之前扫描到dbid改成后续补充一个byte，每个协程被分配不同的前缀，进行各自的任务执行
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耗时对照表
可以比较明显地看出：
阶段2之后的gc时延明显缩减
阶段4之后的gc时延可以随着节点数的增长存在部分缩减
四、后续计划
阶段4之后，我们发现tula的单节点性能应该有提升空间。我们会从以下方面进行入手：
补充更多的监控项目，让tula更加可视，观察client-go的使用情况。
基于上述调整跟进client-go在不同场景下的使用情况，尝试找出client-go在使用上的瓶颈。
尝试调整client-go的使用方式，在tula层面提高从指令执行，到gc，过期的性能。
五、总结
回顾我们从原来的单线程gc，到基于编码机制做到了多线程gc，到为了减少现网写入性能影响，做到了自适应gc，再到为了提升gc性能，进行多节点gc。
gc的性能提升阶段依次经历了以下过程：
单进程单协程
单进程多协程
多进程多协程
突破点主要在于进入阶段2（单进程多协程）阶段，设计上的困难主要来源于：已经存在存量数据，我们需要兼顾存量数据的数据分布情况进行设计，这里我们必须在考虑存量的gckey存在的前提下，原版gckey的编码设计与基于字典序的遍历机制对改造造成的约束。
但是这里基于原有的设计，还是有空间进行一些二次设计，把原有的问题进行调优。
这个过程中，我们认为有几点比较关键：
在第一次设计的时候，应该从多方面进行衡量，思考好某种设计会带来的副作用。
在上线之前，对各种场景（例如不同的指令，数据大小）进行充分测试，提前发现出问题及时修正方案。
已经是存量数据的前提下，更应该对原有的设计进行重新梳理。也许原有的设计是有问题的，遵循当前设计的约束，找出问题关键点，基于现有的设计尝试找到空间去调整，也许存在调优的空间。
无线充电是未来智能手机的充电未来
双电源自动开关的应用与维护说明
盘点2016自动驾驶热点事件TOP10
显示企业加速布局Micro LED,AR时代未来皆可期
太阳诱电将支持 Bluetooth® 5 的无线通信模块的使用温度提高到+105℃
介绍一种KV存储的GC优化实践
魅蓝Note6和小米5X哪个拍照最好
8AI/DI/DO混合信号转RS-485/232信号采集数据模块
无线电测向仪DF2020T接线图
魅族Pro7什么时候上市？最新消息：魅族Pro7真机图曝光！2K全屏+电子墨水屏，瞬间完爆小米、华为！
全差分可编高速放大器LMH6881的主要特性和典型应用电路分析
苹果官方上架翻新iPhone6S/6S Plus 最低3000元起并提供保修服务
索尼PSVita游戏掌机将停止生产和出货，将永远离我们而去了
LG计划明年发布LG G7,将首次带来屏下指纹解锁
粒子加速器的加速原理是啥呢？
基于51单片机秒表计时
磁敏二极管构成的磁场检测电路
摩根大通报告:台积电最快2024年2纳米可量产
矩形平面阵列天线旁瓣电平优化的遗传算法
AEC-Q200车用额定功率电阻