基于LSM-tree的KV数据库性能优化

发布时间：2021-08-20 09:33

　　近年来,由于非结构化数据比例的不断提升以及数据密集型应用场景的逐渐增加,越来越多的企业采用KV数据库来支撑其上层应用的数据存储和访问服务。但是随着数据量和用户访问量的不断增长,KV数据库也面临着来自性能方面的考验。本文主要研究了基于LSM-tree的KV数据库系统中读写性能优化问题,具体包括减少系统的写放大来提升系统的写性能,减少布隆过滤器的误报率来提升系统的读性能以及针对数据频繁更新场景进行相关的优化。本文主要研究内容与贡献如下:1)基于LSM-tree的KV数据库写性能优化由于数据量以及写密集型应用场景的逐渐增多,越来越多的企业选择基于LSM-tree的KV数据库作为底层的存储引擎。尽管LSM-tree具有出色的写性能,但是面对日益增加的用户写请求,系统仍然需要不断提升自身的写性能。LSM-tree会定期对外存中的数据进行排序整理,而这一操作会带来严重的写放大问题。一方面,写放大问题会造成系统整体吞吐量的下降;另一方面,当外存使用SSD时,严重的写放大会大幅降低其使用寿命,进而会影响系统的可靠性并带来高昂的存储开销。因此减少写放大可以节约出更多的I/O资源去服务用户请求,并且还可以... 

【文章来源】：中国科学技术大学安徽省 211工程院校 985工程院校

【文章页数】：101 页

【学位级别】：博士

【部分图文】：

图１．１研宄内容关系图??

传统的ＫＶ数据库，例如ＢｅｒｋｅｌｅｙＤＢ［４６］，往往采用Ｂ－ｔｒｅｅ来存储和管理数??据。Ｂ－ｔｒｅｅ中的节点大小通常和外存的存储单元大小相匹配。Ｂ－ｔｒｅｅ的节点可以??分为内部节点和叶子节点两个部分，如图２．１所示。内部节点用来存放索引信息，??而叶子节点存储真正的数据（即Ｋｅｙ－Ｖａｌｕｅ对）。数据按照Ｋｅｙ的大小顺序存放??在叶子节点中，叶子节点的位置以及叶子节点存储的Ｋｅｙ的范围信息都被保存??在内部节点中。所以在查询一个指定Ｋｅｙ对应的Ｖａｌｕｅ值的时候，我们需要从??Ｂ－ｔｒｅｅ的根节点出发，自上而下进行搜索，直至读取到叶子节点。例如，在图２．１中??查询Ｋｅｙ＝７８对应的Ｖａｌｕｅ值时，Ｂ－ｔｒｅｅ根据Ｋｅｙ值从根节点出发并通过索引信??息确定数据存储的叶子节点。系统随后将叶子节点读入内存，然后在内存中查找??指定的Ｋｅｙ－Ｖａｌｕｅ对。因为在叶子节点内部数据是按照Ｋｅｙ的大小进行排布的，??所以在叶子节点中对指定的Ｋｅｙ使用二分查找。如果在叶子节点中找到需要查??询的Ｋｅｙ时，系统会返回对应的Ｖａｌｕｅ值，如果没有找到则返回值为空。内部节??点占用的存储空间相对较小

?ｅｘｔｅｒｎａｌ?Ｓｔｏｒａｇｅ??｜?１?２?１?１?９?１０?ｉＲＴ?１８?１９?ｉｎ＾ｌｌ?６９?７８?９２?Ｈ?１０１?１０３?２３４１??图２．１?Ｂ－ｔｒｅｅ结构图??传统的ＫＶ数据库，例如ＢｅｒｋｅｌｅｙＤＢ［４６］，往往采用Ｂ－ｔｒｅｅ来存储和管理数??据。Ｂ－ｔｒｅｅ中的节点大小通常和外存的存储单元大小相匹配。Ｂ－ｔｒｅｅ的节点可以??分为内部节点和叶子节点两个部分，如图２．１所示。内部节点用来存放索引信息，??而叶子节点存储真正的数据（即Ｋｅｙ－Ｖａｌｕｅ对）。数据按照Ｋｅｙ的大小顺序存放??在叶子节点中，叶子节点的位置以及叶子节点存储的Ｋｅｙ的范围信息都被保存??在内部节点中。所以在查询一个指定Ｋｅｙ对应的Ｖａｌｕｅ值的时候，我们需要从??Ｂ－ｔｒｅｅ的根节点出发，自上而下进行搜索，直至读取到叶子节点。例如，在图２．１中??查询Ｋｅｙ＝７８对应的Ｖａｌｕｅ值时，Ｂ－ｔｒｅｅ根据Ｋｅｙ值从根节点出发并通过索引信??息确定数据存储的叶子节点。系统随后将叶子节点读入内存，然后在内存中查找??指定的Ｋｅｙ－Ｖａｌｕｅ对。因为在叶子节点内部数据是按照Ｋｅｙ的大小进行排布的


本文编号：3353258