无垃圾回收的键值分离存储系统优化设计与实现

发布时间：2020-06-04 11:29

【摘要】：键值存储是现代存储系统的重要组成部分,由于LSM-tree数据结构针对磁盘的随机写做了优化,大幅度提升了键值存储系统的写性能,因此基于LSM-tree的键值存储成为主流。为了克服LSM-tree在读写操作中仍然产生较高的读写放大现象,进一步发展成为采用键值分离的键值存储系统。然而,采用键值分离的键值存储系统在更新密集型工作负载下会频繁的触发垃圾回收(GC)操作,导致其无法实现较高性能。针对上述问题,设计并实现了一个无需GC的键值分离存储系统,该系统通过对失效数据的有效管理,实现就地更新,从而消除存储过程中的垃圾回收操作,避免存储系统中有效数据的频繁重写,减少系统的写放大,提升系统的性能。首先,通过收集、管理和复用失效数据索引对失效数据实现就地更新、覆盖回收,去除GC过程,避免了由于GC而产生的开销。其次,实现失效索引管理模块,并通过构建生产者-消费者模型,对该模块进行优化,使其在系统中能够灵活高效的实现失效数据的管理、复用,为系统去除GC操作提供了基础保障。最后,通过逻辑设计为数据的就地更新写入方式提供了更新一致性的保证,同时通过增加、管理操作日志,实现了系统崩溃后的数据恢复,避免了数据丢失。测试表明,无需GC的键值分离存储系统可以有效减少系统写入量,在更新密集型工作负载下,相比于现有的键值分离的键值存储系统WiscKey和HashKV,本系统可以减少30%~50%的写入量,从而减小系统写放大。本系统去除了GC过程,使写性能得到了提升,同时,系统性能也不会受到预留空间大小和键值对数据大小的影响。
【图文】：

结构图,结构图,键值,工作负载

随机访问未排序的 value。第三，WiscKey 特别设计了崩溃一致性和垃圾回收技术，能够有效管理 value 的保存日志文件，增强系统的可靠性。第四，WiscKey 在不牺牲一致性的条件下通过删除 LSM-tree 日志来优化性能，从而减少写入带来的系统调用开销。在现代键值存储工作负载中，key 通常很小（例如，16B），但是 value 的大小远大于 key 的大小（例如，100B 到大于 4KB），而 WiscKey 旨在为此类工作负载提供更高的读写性能。WiscKey 是一个衍生于 LevelDB 的单机的持久化键值存储系统，它可以作为关系型数据库（如 MySQL）或分布式键值存储（如 MongoDB）的存储引擎，它提供了与 LevelDB相同的 API，包括Put(key, value)、Get(key)、Delete(key)和 Scan(start, end)。WiscKey 的体系结构如图 2-1 所示，这个图显示了 WiscKey 在单个 SSD 设备上的数据布局，key 和 value 的地址存储在 LSM-tree 中，而 value 追加写入到单独的日志文件中。

垃圾回收,数据布局,指针

将类似于 tuple(key size, value size, key, value)这样的结构存储在 Value Log 中，，如2 所示，这个图显示了 WiscKey 的新数据布局，以支持有效的垃圾回收。Wisc垃圾回收旨在将有效值（不对应于已删除的键）保存在 Value Log 的连续范围图 2-2 所示，这个范围的一端用 head 指针标记，总是与 Value Log 的末尾相对新的数据值添加到 Value Log 的末尾时，都会追加写入到 head 指针的位置，而范围的另一端是 tail 指针，每当触发垃圾回收时，它就开始释放空间，只有垃圾线程会更改 tail 指针。所有有效值的地址范围都处于 head 和 tail 之间，为了查能够快速搜索，head 和 tail 指针被保存在内存中，并持久化存储到 LSM-tree 中。圾回收执行时，WiscKey 首先从 Value Log 的 tail 指针处读取一系列键值对（例如个 MB），然后通过查询 LSM-tree 判断哪些是还没有被重写或删除的有效值，有效值追加到 Value Log 的 head 指针处，最后，更新 tail 指针，释放所读取键值据的空间。
【学位授予单位】：华中科技大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP333

【相似文献】