Bi-directional Log-Structured Merge Tree
Bi-directional Log-Structured Merge Tree
复制标题
DOI：
10.1145/3538712.3538730
复制
发表时间：
2022-07
期刊：
影响因子：
--
通讯作者：
Xin Zhang;Qizhong Mao;Ahmed Eldawy;Vagelis Hristidis;Yihan Sun
中科院分区：
文献类型：
--
作者：
Xin Zhang;Qizhong Mao;Ahmed Eldawy;Vagelis Hristidis;Yihan Sun
日志结构合并（LSM）树已成为现代NoSQL和新SQL数据库系统中一种流行的存储方案。LSM树方案通过首先在内存中缓冲写入操作，然后使用顺序I/O将其刷新到磁盘来实现高写入吞吐量。LSM树是一种异地结构，因此树中某一层的键范围可能与其他层的键范围重叠。这对范围查询性能产生负面影响，因为必须扫描多个层。需要注意的是，范围查询是其他类型查询（如连接或时空查询）的基本操作符。为了提高LSM树的读取性能，本文提出了双向LSM树，它与经典LSM树的不同之处在于，热点记录可以移动到更高层，以改善LSM的整体组织结构并有利于未来的范围查询。双向LSM树重用在范围查询期间执行的工作，有选择性地生成一种特殊类型的组件，称为哨兵组件。我们的实验表明，与标准的分层LSM树相比，双向LSM树可以节省超过10%的磁盘I/O。
The Log-Structured Merge (LSM) Tree has become a popular storage scheme for modern NoSQL and New SQL database systems. The LSM-tree scheme achieves high write throughput by first buffering writes in memory, then flushing them to the disk with sequential I/O. LSM-tree is an out-of-place structure, so the key range of a level in the tree can overlap with those of other levels. This negatively impacts range query performance, as multiple levels have to be scanned. Note that range queries are fundamental operators for other types of queries such as joins or spatiotemporal queries. To improve the read performance of LSM-trees, this paper proposes the Bi-directional LSM-tree, which differs from the classical LSM-tree in that hot records can move to higher levels to improve the overall LSM organization and benefit future range queries. The Bi-directional LSM-tree reuses the work performed during range queries to selectively generate a special type of components, called sentinel components. Our experiments show that the Bi-directional LSM-tree can save more than 10% of disk I/O compared to a standard Leveled LSM-tree.