基于LSM-Tree的持久化存储系统设计与实现

发布时间：2020-05-30 21:52

【摘要】：随着互联网的高速发展,人们生活的各个方面都离不开互联网,人们在享受互联网带来便捷生活的同时,也使得互联网数据高速增长。如何快速查询和存储海量数据已成为人们研究的重点,这也使得NoSQL数据库快速发展。比较典型的NoSQL数据存储形式是键值存储,即一个键对应一个值。键值存储系统可以理解为一个可持久化的更大容量的哈希表。存储系统最重要的部分是存储引擎,本文研究了当前最流行的日志结构合并树(LSM-Tree)存储引擎。基于日志结构合并树的存储引擎核心思想是顺序写入,将修改的数据排序后保存在内存,达到一定规模后再将内存中修改的数据批量刷入磁盘,并且在写入过程中与之前已经存在的磁盘数据进行合并,合并的过程中丢弃掉旧的键值数据。日志结构合并树最大的问题就是合并操作产生的磁盘I/O开销,极大地影响了写性能,严重情况下写速度取决于合并速度。本文的研究目的就是解决日志结构合并树的写放大问题,提高合并效率,从而提升日志结构合并树的写入性能。与传统的日志结构合并树实现相比,本文通过增加一层索引层,并采用键值分开存储的方式。键的后面紧跟着的不再是值,而是指向值所在的地址,称其为值索引,以此避免值参与合并压缩操作,从而减少合并带来的磁盘I/O开销,提升合并速度。键值分开存储在牺牲一定读性能的前提下,大大减少了合并操作引起的磁盘I/O开销,极大地提高了写性能。本文基于日志结构合并树,采取了键值分离的存储方式,增加了索引层以及独特的旧数据回收算法,设计与实现了一个键值存储系统。并与基于传统的日志结构合并树的存储系统Leveldb进行读写性能对比,实验结果表明了本系统具有更好的写性能,特别是在值字节数较多以及写压力大的场景下,性能优势更加明显。
【图文】：

功能测试,键值,索引表

.2 第零层磁盘索引表文件测试因为磁盘索引表模块的第零层文件比较特殊，文件间键范围冲突，为测试件读写是否正常，首先插入两条键值对<foo，v1>和<zoo，z1>，接着强制存索引表的内容写入磁盘索引表模块的第零层文件；再插入键值对<foo，强制刷入第零层文件，此时第零层有两个文件，均包含有关 foo 的键值对用读接口查询 foo 对应的值，用测试框架判断是否为最新值 v2。.3 故障恢复测试为模拟故障恢复，先向系统插入键值对<foo，v1>，以及键值对<bar，v2>两条键值记录的索引记录均在内存索引表中，随后关闭数据库并重新打开通过数据日志文件的日志重新生成两条键值记录的索引记录，调用读接取 foo 对应的值，用测试框架判断是否为最新值 v2。除了上述功能测试外，测试模块还有其他上百个功能测试用例，，因篇幅有不再详细介绍，测试结果如图 5-1 所示。

数据规模,性能测试,键值

第五章测试与分析试系统对大值（值字节数较多）随机写入的性能，将每个写入的键值为 100000 个字节，随机写入若干条这样的键值记录，并根据总时间计机写一条大值记录所花费的时间。测试结果与分析试方案提到性能测试共分为五组，每组测试的数据规模不一样，下面系统在不同数据规模下的测试结果。
【学位授予单位】：电子科技大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP333;TP311.13

【参考文献】