日志结构合并树的查询优化技术

doi:10.3969/j.issn.1000-5641.2021.05.009

摘要/Abstract

摘要：

针对基于日志结构合并树(Log Structured Merge Tree, LSM-tree)的数据库查询性能较差的问题, 目前的研究工作主要集中在利用索引和缓存技术提升LSM-tree的查询性能. 本文主要从以下几个方面对LSM-tree的查询优化技术进行了综述. 第一, 介绍了LSM-tree的基础架构, 分析了影响查询的因素. 第二, 分析了当前的LSM-tree查询优化技术, 包括索引优化技术和缓存优化技术. 第三, 分析了索引和缓存技术是如何提升基于LSM-tree的数据库查询性能的, 并总结了一些现有的研究工作. 最后, 总结并给出了未来可能的研究方法.

关键词: 日志结构合并树, 索引, 缓存

Abstract:

Given challenges with poor query performance for databases using LSM-trees, the present research explores the use of index and cache technologies to improve the query performance of LSM-trees. First, the paper introduces the basic structure of an LSM-tree and analyzes the factors that affect query performance. Second, we analyze current query optimization technologies for LSM-trees, including index optimization technology and cache optimization technology. Third, we analyze how index and cache, in particular, can improve the query performance of databases using LSM-trees and summarize existing research in this area. Finally, we present possible avenues for further research.

Key words: LSM-tree, index, cache

中图分类号:

TP392

孙家博, 蔡鹏. 日志结构合并树的查询优化技术[J]. 华东师范大学学报（自然科学版）, 2021, 2021(5): 94-103.

Jiabo SUN, Peng CAI. Query optimization technology based on an LSM-tree[J]. Journal of East China Normal University(Natural Science), 2021, 2021(5): 94-103.

图/表 5

图1

图2

图3

图4

表1

参考文献 45

1	ARMSTRONG T G, PONNEKANTI V, BORTHAKUR D, et al. Linkbench: A database benchmark based on the facebook social graph [C]//Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. 2013: 1185-1196.
2	ATIKOGLU B, XU Y, FRACHTENBERG E, et al. Workload analysis of a large-scale key-value store [C]//Proceedings of the 12th ACM Sigmetrics/Performance Joint International Conference on Measurement and Modeling of Computer Systems. 2012: 53-64.
3	CAO Z, DONG S, VEMURI S, et al. Characterizing, modeling, and benchmarking rocksDB key-value workloads at facebook [C]//18th USENIX Conference on File and Storage Technologies (FAST’ 20). 2020: 209-223.
4	BU Y, BORKAR V, JIA J, et al. Pregelix: Big(ger) graph analytics on a dataflow engine[J]. Proceedings of the VLDB Endowment, 2015, 8(2): 161–172.
5	DECANDIA G, HASTORUN D, JAMPANI M, et al. Dynamo: Amazon's highly available key-value store. ACM SIGOPS Operating Systems Review, 2007, 41 (6): 205- 220. doi: 10.1145/1323293.1294281
6	RAJU P, PONNAPALLI S, KAMINSKY E, et al. Mlsm: Making authenticated storage faster in ethereum [C]//10th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage’ 18). 2018.
7	CAO Z, CHEN S, LI F, et al. LogKV: Exploiting key-value stores for event log processing [C/OL]// 6th Biennial Conference on Innovative Data Systems Research (CIDR’13). 2013. http://cidrdb.org/cidr2013/Papers/CIDR13_Paper46.pdf.
8	CHEN G J, WIENER J L, IYER S, et al. Realtime data processing at facebook [C]//Proceedings of the 2016 International Conference on Management of Data. 2016: 1087-1098.
9	KONDYLAKIS H, DAYAN N, ZOUMPATIANOS K, et al. Coconut palm: Static and streaming data series exploration now in your palm [C]//Proceedings of the 2019 International Conference on Management of Data. 2019: 1941-1944.
10	KONDYLAKIS H, DAYAN N, ZOUMPATIANOS K, et al. Coconut: Sortable summarizations for scalable indexes over static and streaming data series. The VLDB Journal, 2019, 28 (6): 847- 869. doi: 10.1007/s00778-019-00573-w
11	DGRAPH. Badger Key-value DB in Go[EB/OL]. [2021-08-23]. https://github.com/dgraphio/badger.
12	KYROLA A, GUSSTRIN C. GraphChi-DB: Simple design for a scalable graph database system—on just a PC[EB/OL]. (2014-03-04)[2021-08-23]. https://arxiv.org/pdf/1403.0701.pdf.
13	ALSUBAIEE S, CAREY M J, LI C. LSM-based storage and indexing: An old idea with timely benefits [C]//Second International ACM Workshop on Managing and Mining Enriched Geo-spatial Data. 2015: 1-6.
14	SHETTY P J, SPILLANE R P, MALPANI R R, et al. Building workload-independent storage with VT-trees [C]//11th USENIX Conference on File and Storage Technologies (FAST’ 13). 2013: 17-30.
15	JANNEN W, YUAN J, ZHAN Y, et al. BetrFS: A right-optimized write-optimized file system[C]//13th USENIX Conference on File and Storage Technologies (FAST’ 15). 2015: 301-315.
16	VINCON T, HARDOCK S, RIEGGER C, et al. Noftl-kv: Tackling write-amplification on kv-stores with native storage management [C]//Extending Database Technology. 2018: 457-460.
17	DAYAN N, BONNET P, IDREOS S. GeckoFTL: Scalable flash translation techniques for very large flash devices [C]//Proceedings of the 2016 International Conference on Management of Data. 2016: 327-342.
18	COMER D. Ubiquitous B-tree. ACM Computing Surveys (CSUR), 1979, 11 (2): 121- 137. doi: 10.1145/356770.356776
19	O’NEIL P, CHENG E, GAWLICK D, et al. The log-structured merge-tree (LSM-tree). Acta Informatica, 1996, 33 (4): 351- 385. doi: 10.1007/s002360050048
20	CHANG F, DEAN J, GHEMAWAT S, et al. Bigtable: A distributed storage system for structured data. ACM Transactions on Computer Systems, 2008, 26 (2): 1- 26.
21	Google. Leveldb[EB/OL]. [2021-08-23]. https://leveldb.org/.
22	Facebook. Rocksdb[EB/OL]. [2021-08-23]. https://rocksdb.org/.
23	Apache. Cassandra[EB/OL]. [2021-08-23]. http://cassandra.apache.org/.
24	HBase[EB/OL]. [2021-08-23]. https://hbase.apache.org/
25	ALSUBAIEE S, BEHM A, BORKAR V, et al. Storage management in AsterixDB[J]. Proceedings of the VLDB Endowment, 2014, 7(10): 841-852.
26	BEAVER D, KUMAR S, LI H C, et al. Finding a needle in haystack: Facebook's photo storage [J]. OSDI, 2010(10): 1-8.
27	MATSUNOBU Y, DONG S, LEE H. MyRocks: LSM-tree database storage engine serving Facebook's social graph[J]. Proceedings of the VLDB Endowment, 2020, 13(12): 3217-3230.
28	HUANG G, CHENG X, WANG J, et al. X-Engine: An optimized storage engine for large-scale E-commerce transaction processing [C]//Proceedings of the 2019 International Conference on Management of Data. 2019: 651-665.
29	CAO W, LIU Z, WANG P, et al. PolarFS: An ultra-low latency and failure resilient distributed file system for shared storage cloud database[J]. Proceedings of the VLDB Endowment, 2018, 11(12): 1849-1862.
30	BLOOM B H. Space/time trade-offs in hash coding with allowable errors. Communications of the ACM, 1970, 13 (7): 422- 426. doi: 10.1145/362686.362692
31	KIRSCH A, MITZENMACHER M. Less hashing, same performance: Building a better Bloom filter. Random Structures & Algorithms, 2008, 33 (2): 187- 218.
32	DAYAN N, ATHANASSOULIS M, IDREOS S. Optimal bloom filters and adaptive merging for LSM-trees. ACM Transactions on Database Systems, 2018, 43 (4): 1- 48.
33	DAYAN N, ATHANASSOULIS M, IDREOS S. Monkey: Optimal navigable key-value store[C]//Proceedings of the 2017 ACM International Conference on Management of Data. 2017: 79-94.
34	LI Y, TIAN C, GUO F, et al. Elasticbf: Elastic bloom filter with hotness awareness for boosting read performance in large key-value stores [C]//2019 USENIX Annual Technical Conference (USENIX ATC’19). 2019: 739-752.
35	ZHANG H, LIM H, LEIS V, et al. Surf: Practical range query filtering with fast succinct tries [C]//Proceedings of the 2018 International Conference on Management of Data. 2018: 323-336.
36	LUO S, CHATTERJEE S, KETSETSIDIS R, et al. Rosetta: A robust space-time optimized range filter for key-value stores [C]//Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data. 2020: 2071-2086.
37	ZHONG W, CHEN C, WU X, et al. {REMIX}: Efficient Range Query for LSM-trees [C]//19th USENIX Conference on File and Storage Technologies (FAST’ 21). 2021: 51-64.
38	O'NEIL E J, O'NEIL P E, WEIKUM G. The LRU-K page replacement algorithm for database disk buffering. Acm Sigmod Record, 1993, 22 (2): 297- 306. doi: 10.1145/170036.170081
39	TAILOR P, MORENA R D. A survey of database buffer cache management approaches. International Journal of Advanced Research in Computer Science, 2017, 8 (3): 409- 414.
40	AHMAD M Y, KEMME B. Compaction management in distributed key-value datastores[J]. Proceedings of the VLDB Endowment, 2015, 8(8): 850-861.
41	JAGADISH H V, NARAYAN P P S, SESHADRI S, et al. Incremental organization for data recording and warehousing [J]. VLDB, 1997, 97: 16-25.
42	YANG L, WU H, ZHANG T, et al. Leaper: A learned prefetcher for cache invalidation in LSM-tree based storage engines[J]. Proceedings of the VLDB Endowment, 2020, 13(12): 1976-1989.
43	TENG D, GUO L, LEE R, et al. LSbM-tree: Re-enabling buffer caching in data management for mixed reads and writes [C]//2017 IEEE 37th International Conference on Distributed Computing Systems (ICDCS). 2017: 68-79.
44	WU F, YANG M H, ZHANG B, et al. AC-Key: Adaptive caching for LSM-based key-value Stores [C]//2020 USENIX Annual Technical Conference (USENIX ATC’ 20). 2020: 603-615.
45	LI X, XU G, FAN H, et al. Improving read performance of LSM-tree based KV stores via dual grained caches [C]//2019 IEEE 21st International Conference on High Performance Computing and Communications, IEEE 17th International Conference on Smart City, IEEE 5th International Conference on Data Science and Systems (HPCC/SmartCity/DSS). 2019: 841-848.

方法	技术	缺点
Dedicated Compaction Servers	专用合并服务器处理合并操作, 预热算法替换缓存数据	对于访问较分散的负载并不适用
SM-tree	降低合并操作频率	范围查询差, 存在大量重复数据
Leaper	机器学习预取数据	不适合变化较大的负载, 离线模型训练增大模型复杂度
LSbM-tree	在磁盘上建立合并缓存	长范围查询较差, 合并缓存占用磁盘空间, 严重写放大
AC-Key	3 种缓存形式: key-value, key-pointer 和 block	缓存相同数据浪费内存资源
Dual Grained Caches	fine-grained cache, coarse-grained cache	细粒度缓存同步更新影响写性能

[1]	阳文灿, 胡卉芪, 段惠超, 胡耀艺, 钱卫宁. CedarAdvisor: 负载自适应的自动化索引推荐工具[J]. 华东师范大学学报（自然科学版）, 2020, 2020(6): 52-62.
[2]	卫孝贤, 刘文欣, 蔡鹏. 多主云数据库的全局事务日志[J]. 华东师范大学学报（自然科学版）, 2020, 2020(5): 10-20.
[3]	刘子豪, 胡卉芪, 徐瑞, 周烜. 基于LevelDB的二维数据二级索引实现[J]. 华东师范大学学报(自然科学版), 2019, 2019(5): 159-167.
[4]	隆飞, 翁海星, 高明, 张召. 基于LSM Tree的分布式索引实现[J]. 华东师范大学学报(自然科学版), 2016, 2016(5): 36-44.
[5]	董绍婵, 周敏奇, 张蓉, 周傲英. 内存数据索引：以处理器为核心的性能优化技术[J]. 华东师范大学学报(自然科学版), 2014, 2014(5): 192-206.
[6]	黄岚, 孙珂, 陈晓竹, 周敏奇. 内存集群计算:交互式数据分析[J]. 华东师范大学学报(自然科学版), 2014, 2014(5): 216-227.
[7]	张文杰, 彭智勇, 彭煜玮. 内存数据管理技术在族谱信息系统中的应用[J]. 华东师范大学学报(自然科学版), 2014, 2014(5): 311-319.
[8]	冯亮，沙朝锋. 电子商务网站搜索引擎检索串分析[J]. 华东师范大学学报(自然科学版), 2013, 2013(3): 79-83，105.
[9]	许文韬. 网页数据库动态同步技术研究[J]. 华东师范大学学报(自然科学版), 2006, 2006(1): 108-115.
[10]	王善平;袁美英;尤力群. 《学报》50年发表论文及被引用情况的统计与分析[J]. 华东师范大学学报(自然科学版), 2005, 2005(5/6): 7-12.