SilkStore：写优化与工作负载自适应的键值存储系统
发布时间：2021-12-17 11:06
键值存储系统,由于其简单的数据模型,被广泛应用于社交网络、电商、云计算基础设施等场景下,是现代存储系统的重要组成部分。其中比较重要一类系统是基于日志结构合并树（Log-structured Merge Tree,LSMT）的键值存储系统。这类系统因为有着优异的写入能力,已被广泛用在密集写入的场景下。但是基于LSMT的键值存储系统,如LevelDB/RocksDB,还是存在着写放大严重的问题,即实际写入存储设备的数据量要远大于用户请求写入的数据量,浪费I O能力以及加速存储设备损耗。学界也有不少关于降低写放大的研究工作,如WiscKey、PebblesDB、LSM-Trie,但是这类工作大多都需要牺牲读操作的性能。因此本文的首要研究目标是降低该类系统的写放大。为此,本文提出SilkSt ore,一个写优化的键值存储系统,来尝试解决这个问题。SilkStore的核心创新点在于设计了一个单层的LSMT结构以及高效的合并策略,降低了由于传统LS MT的多层设计以及合并算法导致的对键值的重复写入。同时本文从理论角度分析了SilkStore相比于其他LSMT设计的优劣势。除此之外,现有的LSMT设...
【文章来源】：浙江大学浙江省 211工程院校 985工程院校 教育部直属院校
【文章页数】：68 页
【学位级别】：硕士
【部分图文】：
原始LSMT合并示意图[8]
浙江大学硕士学位论文第2章相关工作13图2-2两种LSMT合并策略示意图[18]合并策略代价分析.为了理解两种策略的优缺点，我们可以针对不同合并策略配置下LSMT的读写IO次数做一个分析。为了简化分析，我们假设存储的键值对大小固定。我们定义为LSMT两层之间的大小比例，并且假设有层。在实际应用中，如果数据集中唯一键的数量不变，一般是一个固定值。我们采用页面作为IO单位,记为一个页面能容纳的记录数，为内存表能容大的最大页面数。因此内存表能容纳条键值记录，第层最多能容纳*条键值记录。给定条记录的数据集，则最后一层大约能存储,-%,条记录，因为最后一层比前一层大了倍。因此可以近似表示为7.#(0,-%,8。我们定义写代价为写入一条记录的均摊IO代价。对于Leveling来说，每一层需要合并1次，才能填满，并加入到下一层，因此一条记录在一层内平均情况下需要写,"次。因为一个页面含有条记录，那么一条记录在Leveling策略下总的写代价为(,()。对于Tiering来说，多个SSTable在一层只被合并一次之后就被推到下一层去了，所以一条记录在一层只需要被合并一次。类似的，Tiering策略下一条记录总的写代价为(1()。从这里可以看出Tiering的写代价要比Leveling小T倍，更加适合多写场景。我们定义读代价为读取一条键值记录的IO次数。对于Leveling来说，读代价为()；对于Tiering来说，读代价为()。在实际应用过程中，布隆过滤
浙江大学硕士学位论文第2章相关工作15图2-3Tiering策略下的分区优化[18]Tiering合并策略的分区优化难点在于如何确定组的分区范围，好的组分区应该使得每个组大小接近。PebblesDB[12]采用了类似的Tiering合并策略，并且做了分区优化。它提出用类似skip-list[20]基于概率性的思想来从插入的键中选择出组的分区范围，以此来达到组之间的数据量平衡。进一步的，PebblesDB利用现代SSD的高随机IO能力,提出了用并行查询来优化范围查询，。2.2.4基于新型存储硬件的LSMT写放大优化研究现状目前SSD已经渐渐成为数据中心存储的主流，随机读IO已经能赶上顺序读IO的带宽吞吐，因此产生了一些新的设计。LSMT尽管在写放大方面要优于B+树，但是合并策略的不同，写放大还是会有比较大的差异。学界也有不少研究尝试解决LSMT写放大问题。WiscKey论文指出，一般来说LSMT存储的值相比于键会大很多，并且这些值在合并的过程中需要被反复的读取和写入，因此造成大量的写放大。WiscKey因此提出了键值分离的概念，如图2-3所示，通过将值存储在一个单独的日志文件里，并且对这个日志文件按照键进行索引，即存储<键，值在日志文件中的位置>到另外一颗索引用的LSMT中，以完成各类查询操作，由此来降低写放大。这样的好处就是索引LSMT会比较小，写放大大大降低。这种设计在查询效率上也比较出色，因为SSD没有HDD的寻道时间，并发随机查询基本能够达到设备带宽上限。
本文编号：3539990
【文章来源】：浙江大学浙江省 211工程院校 985工程院校 教育部直属院校
【文章页数】：68 页
【学位级别】：硕士
【部分图文】：
原始LSMT合并示意图[8]
浙江大学硕士学位论文第2章相关工作13图2-2两种LSMT合并策略示意图[18]合并策略代价分析.为了理解两种策略的优缺点，我们可以针对不同合并策略配置下LSMT的读写IO次数做一个分析。为了简化分析，我们假设存储的键值对大小固定。我们定义为LSMT两层之间的大小比例，并且假设有层。在实际应用中，如果数据集中唯一键的数量不变，一般是一个固定值。我们采用页面作为IO单位,记为一个页面能容纳的记录数，为内存表能容大的最大页面数。因此内存表能容纳条键值记录，第层最多能容纳*条键值记录。给定条记录的数据集，则最后一层大约能存储,-%,条记录，因为最后一层比前一层大了倍。因此可以近似表示为7.#(0,-%,8。我们定义写代价为写入一条记录的均摊IO代价。对于Leveling来说，每一层需要合并1次，才能填满，并加入到下一层，因此一条记录在一层内平均情况下需要写,"次。因为一个页面含有条记录，那么一条记录在Leveling策略下总的写代价为(,()。对于Tiering来说，多个SSTable在一层只被合并一次之后就被推到下一层去了，所以一条记录在一层只需要被合并一次。类似的，Tiering策略下一条记录总的写代价为(1()。从这里可以看出Tiering的写代价要比Leveling小T倍，更加适合多写场景。我们定义读代价为读取一条键值记录的IO次数。对于Leveling来说，读代价为()；对于Tiering来说，读代价为()。在实际应用过程中，布隆过滤
浙江大学硕士学位论文第2章相关工作15图2-3Tiering策略下的分区优化[18]Tiering合并策略的分区优化难点在于如何确定组的分区范围，好的组分区应该使得每个组大小接近。PebblesDB[12]采用了类似的Tiering合并策略，并且做了分区优化。它提出用类似skip-list[20]基于概率性的思想来从插入的键中选择出组的分区范围，以此来达到组之间的数据量平衡。进一步的，PebblesDB利用现代SSD的高随机IO能力,提出了用并行查询来优化范围查询，。2.2.4基于新型存储硬件的LSMT写放大优化研究现状目前SSD已经渐渐成为数据中心存储的主流，随机读IO已经能赶上顺序读IO的带宽吞吐，因此产生了一些新的设计。LSMT尽管在写放大方面要优于B+树，但是合并策略的不同，写放大还是会有比较大的差异。学界也有不少研究尝试解决LSMT写放大问题。WiscKey论文指出，一般来说LSMT存储的值相比于键会大很多，并且这些值在合并的过程中需要被反复的读取和写入，因此造成大量的写放大。WiscKey因此提出了键值分离的概念，如图2-3所示，通过将值存储在一个单独的日志文件里，并且对这个日志文件按照键进行索引，即存储<键，值在日志文件中的位置>到另外一颗索引用的LSMT中，以完成各类查询操作，由此来降低写放大。这样的好处就是索引LSMT会比较小，写放大大大降低。这种设计在查询效率上也比较出色，因为SSD没有HDD的寻道时间，并发随机查询基本能够达到设备带宽上限。
本文编号：3539990
本文链接：https://www.wllwen.com/kejilunwen/jisuanjikexuelunwen/3539990.html
