计算机研究与发展

作者：吴尚宇,谢婧雯,王毅,

关键词：计算机体系结构, 键值存储, 日志结构合并树, 访问频率, 数据上浮,

日志结构合并树(log-structuredmergetree,LSM-Tree)是一种针对写优化的数据结构，广泛应用于当代主流键值存储系统之中，用于处理当今世界海量多样化的数据.LSM-Tree通过批量处理的方式将随机写请求转换为顺序写请求，以保持极高的写效率.但LSM-Tree仍存在2个不足：一是数据的流动方向是单向的且固定不变.存储在LSM-Tree底部的数据将被一直保留底部，直到它们成为旧数据被压缩操作删除.访问这些数据将使读放大问题变得更加严重.二是LSM-Tree中的数据分布并未考虑访问频率的影响，这将导致访问延迟不平衡的问题.访问高频的低层数据将产生更高的访问延迟.提出了一种基于访问频率分布的上浮式键值存储结构(floatingkey-value,FloatKV).FloatKV首先在内存中提出了一种新的数据存储结构(LRUandFIFO,LRFO)，其次在外存中设计了一种基于访问频率分布的上浮式键值存储策略.FloatKV记录外存中数据的访问频率，并根据访问频率来调整数据的存储位置，以减少访问延迟.为了验证FloatKV的可行性以及性能，使用标准数据库性能测试工具YSCB(yahoo!cloudservingbenchmark)来进行评估，并将FloatKV与当前主流的技术进行比较.实验结果表明，FloatKV能够显著地提高读效率，并有效地减少了读放大问题.

来源：2020年第11期

《计算机研究与发展》期刊编辑部

查看计算机研究与发展杂志2020年第11期