(深圳大学计算机与软件学院 广东深圳 518060) (shangyuwu1006@gmail.com)
出版日期: 2020-11-01基金资助:国家自然科学基金项目(61972259)；广东省自然科学基金-****基金项目(2019B151502055)；广东省自然科学基金项目(2017B030314073)；深圳市基础研究项目(JCYJ20170817100300603)Optimization of LSM-Tree for Key-Value Stores
Wu Shangyu, Xie Jingwen, Wang Yi(College of Computer Science and Software Engineering, Shenzhen University, Shenzhen, Guangdong 518060)
Online: 2020-11-01Supported by:This work was supported by the National Natural Science Foundation of China (61972259), the Guangdong Natural Science Foundation-Distinguished Young Scholars (2019B151502055), the Guangdong Natural Science Foundation (2017B030314073), and the Shenzhen Natural Science Foundation (JCYJ20170817100300603).摘要/Abstract
摘要： 日志结构合并树(log-structured merge tree, LSM-Tree)是一种针对写优化的数据结构，广泛应用于当代主流键值存储系统之中，用于处理当今世界海量多样化的数据.LSM-Tree通过批量处理的方式将随机写请求转换为顺序写请求，以保持极高的写效率.但LSM-Tree仍存在2个不足：一是数据的流动方向是单向的且固定不变.存储在LSM-Tree底部的数据将被一直保留底部，直到它们成为旧数据被压缩操作删除.访问这些数据将使读放大问题变得更加严重.二是LSM-Tree中的数据分布并未考虑访问频率的影响，这将导致访问延迟不平衡的问题.访问高频的低层数据将产生更高的访问延迟.提出了一种基于访问频率分布的上浮式键值存储结构(floating key-value, FloatKV).FloatKV首先在内存中提出了一种新的数据存储结构(LRU and FIFO, LRFO)，其次在外存中设计了一种基于访问频率分布的上浮式键值存储策略.FloatKV记录外存中数据的访问频率，并根据访问频率来调整数据的存储位置，以减少访问延迟.为了验证FloatKV的可行性以及性能，使用标准数据库性能测试工具YSCB(yahoo! cloud serving benchmark)来进行评估，并将FloatKV与当前主流的技术进行比较.实验结果表明，FloatKV能够显著地提高读效率，并有效地减少了读放大问题.
参考文献
相关文章 10
| [1] | 韩书楷, 熊子威, 蒋德钧, 熊劲. 基于持久化内存的索引设计重新思考与优化[J]. 计算机研究与发展, 2021, 58(2): 356-370. |
| [2] | 安仲奇, 张云尧, 邢晶, 霍志刚. 基于用户级融合I/O的Key-Value存储系统优化技术研究[J]. 计算机研究与发展, 2020, 57(3): 649-659. |
| [3] | 王海涛,李战怀,张晓,赵晓南. 一种基于LSM树的键值存储系统性能优化方法[J]. 计算机研究与发展, 2019, 56(8): 1792-1802. |
| [4] | 方荣强，王晶，姚治成，刘畅，张伟功. 多层神经网络算法的计算特征建模方法[J]. 计算机研究与发展, 2019, 56(6): 1170-1181. |
| [5] | 陈游旻,陆游游,罗圣美,舒继武. 基于RDMA的分布式存储系统研究综述[J]. 计算机研究与发展, 2019, 56(2): 227-239. |
| [6] | 游理通,王振杰,黄林鹏. 一个基于日志结构的非易失性内存键值存储系统[J]. 计算机研究与发展, 2018, 55(9): 2038-2049. |
| [7] | 蒋捷,杨仝,张梦瑜,代亚非,黄亮,郑廉清. DCuckoo：基于片内摘要的高性能散列表[J]. 计算机研究与发展, 2017, 54(11): 2508-2515. |
| [8] | 何炎祥,沈凡凡,张军,江南,李清安,李建华. 新型非易失性存储器架构的缓存优化方法综述[J]. 计算机研究与发展, 2015, 52(6): 1225-1241. |
| [9] | 李玮,张大方,谢鲲,黎文伟,何杰. 一种面向闪存键值存储的矩阵索引布鲁姆过滤器[J]. 计算机研究与发展, 2015, 52(5): 1210-1222. |
| [10] | 田杭沛 高德远 樊晓桠 朱怡安. 面向实时流处理的多核多线程处理器访存队列[J]. , 2009, 46(10): 1634-1641. |
PDF全文下载地址:
https://crad.ict.ac.cn/CN/article/downloadArticleFile.do?attachType=PDF&id=4299
