REMIX: Efficient Range Query for LSM-trees
REMIX: Efficient Range Query for LSM-trees
复制标题
DOI：
--
复制
发表时间：
2020-10
期刊：
影响因子：
--
通讯作者：
Wenshao Zhong;Chen Chen-Chen;Xingbo Wu;Song Jiang
中科院分区：
文献类型：
--
作者：
Wenshao Zhong;Chen Chen-Chen;Xingbo Wu;Song Jiang
基于LSM-TREE的键值（KV）存储在高速写入的多层结构中组织数据。该结构的范围查询必须从多个表文件中寻找和分类合并数据，这很昂贵，通常会导致平庸的读取性能。为了提高LSM-Trees的范围查询效率，我们引入了一个名为Remix的空间效能KV索引数据结构，该数据记录了跨越多个表文件的KV数据的全局排序视图。在多个数据文件上进行混音的范围查询可以使用二进制搜索快速定位目标键，并以排序顺序检索后续键，而无需键比较。我们构建了RemixDB，这是一种基于LSM-TREE的KV商店，采用了写入有效的压实策略，并采用了快速点和范围查询的混音。实验结果表明，混音可以在基于Write优化的LSM-TREE基础上大大提高范围查询性能。
LSM-tree based key-value (KV) stores organize data in a multi-level structure for high-speed writes. A range query on this structure has to seek and sort-merge data from multiple table files on the fly, which is expensive and often leads to mediocre read performance. To improve range query efficiency on LSM-trees, we introduce a space-efficient KV index data structure, named REMIX, that records a global sorted view of KV data spanning multiple table files. A range query with REMIX on multiple data files can quickly locate the target key using a binary search, and retrieve the subsequent keys in the sorted order without key comparisons. We build RemixDB, an LSM-tree based KV-store that adopts a write-efficient compaction strategy and employs REMIX for fast point and range queries. Experimental results show that REMIX can substantially improve range query performance in a write-optimized LSM-tree based KV-store.