基于日志结构合并树的轻量级分布式索引实现方法

doi:10.11772/j.issn.1001-9081.2020091543

计算机应用 ›› 2021, Vol. 41 ›› Issue (3): 630-635.DOI: 10.11772/j.issn.1001-9081.2020091543

所属专题：第37届CCF中国数据库学术会议(NDBC 2020)

• 第37届CCF中国数据库学术会议(NDBC 2020) • 上一篇下一篇

基于日志结构合并树的轻量级分布式索引实现方法

崔双双, 王宏志

哈尔滨工业大学计算学部, 哈尔滨 150001

收稿日期:2020-09-07 修回日期:2020-12-10 出版日期:2021-03-10 发布日期:2020-12-31
通讯作者: 王宏志
作者简介:崔双双(1997-),女,黑龙江哈尔滨人,硕士研究生,CCF会员,主要研究方向:数据库、查询优化;王宏志(1978-),男,辽宁丹东人,教授,博士生导师,博士,主要研究方向:数据库、大数据、数据质量。
基金资助:
国家重点研发计划项目（2018YFB1004700）；国家自然科学基金资助项目（U1866602，61602129，61772157）。

Implementation method of lightweight distributed index based on log structured merge-tree

CUI Shuangshuang, WANG Hongzhi

Faculty of Computer Science, Harbin Institute of Technology, Harbin Heilongjiang 150001, China

Received:2020-09-07 Revised:2020-12-10 Online:2021-03-10 Published:2020-12-31
Supported by:
This work is partially supported by the National Key Research and Development Program of China (2018YFB1004700), the National Natural Science Foundation of China (U1866602, 61602129, 61772157).

摘要/Abstract

摘要： 针对现有基于日志结构合并树（LSM-Tree）实现的分布式数据库仅支持高效的主键查询，无法让用户快速地应用在自己的集群中的问题，提出了基于LSM-Tree的轻量级分布式索引实现方法SIBL。首先，通过对主键属性列建立索引来提高非主键属性的查询效率；然后，提出了分布式索引构建算法以及基于等距取样的索引区间划分算法，从而保证了索引在系统中的均匀分布，并且优化了传统索引的查询算法，将索引文件看作特殊的数据文件分布式地存储在系统中，从而保证了系统的负载均衡和可扩展性；最后，将该方法与华为二级索引方案HIndex在HBase数据库上进行实验来比较二者的索引构建的时间和空间开销、索引的查询性能和系统的负载均衡等性能，验证得出所提出的方法使查询性能提升了50~200倍。

关键词: 日志结构合并树, 分布式索引, HBase, 查询优化

Abstract: To solve the problem that the existing distributed database based on Log Structured Merge-Tree (LSM-Tree) only supports efficient primary key query and cannot allow users to quickly apply it in their own clusters, a light-weight distributed index implementation method based on LSM-Tree, called SIBL (Secondary Index Based LSM-Tree), was proposed. Firstly, the query efficiency of the non-primary key attributes was improved by indexing the primary key attribute columns. Then, a distributed index construction algorithm and an index interval division algorithm based on equidistant sampling were proposed to ensure the even distribution of indexes in the system. And the query algorithm of the traditional index was optimized, and the index file was regarded as a special data file and stored in the system in a distributed manner, ensuring the load balance and scalability of the system. Finally, experiments of the proposed method with Huawei's secondary index scheme HIndex were carried out on the HBase database to compare performances such as time and space overhead of index construction, index query performance and system load balance, verifying that the proposed method improves query performance by 50 to 200 times.

Key words: Log Structured Merge-Tree (LSM-Tree), distributed index, HBase, query optimization

中图分类号:

TP312

崔双双, 王宏志. 基于日志结构合并树的轻量级分布式索引实现方法[J]. 计算机应用, 2021, 41(3): 630-635.

CUI Shuangshuang, WANG Hongzhi. Implementation method of lightweight distributed index based on log structured merge-tree[J]. Journal of Computer Applications, 2021, 41(3): 630-635.

参考文献

[1] 王文贤, 陈兴蜀, 王海舟, 等. 一种基于Solr的HBase海量数据二级索引方案[J]. 信息网络安全,2017(8):39-44.(WANG W X, CHEN X S,WANG H Z,et al. A secondary index scheme of big data in HBase based on Solr[J]. Netinfo Security,2017(8):39-44.)
[2] ZHANG C,LI F,JESTES J. Efficient parallel kNN joins for large data in MapReduce[C]//Proceedings of the 15th International Conference on Extending Database Technology. New York:ACM, 2012:38-49.
[3] GRAEFE G. B-tree indexes for high update rates[J]. ACM SIGMOD Record,2006,35(1):39-44.
[4] 孟必平, 王腾蛟, 李红燕, 等. 分片位图索引:一种适用于云数据管理的辅助索引机制[J]. 计算机学报,2012,35(11):2306-2316.(MENG B P,WANG T J,LI H Y,et al. Regional bitmap index:a secondary index for data management in could computing environment[J]. Chinese Journal of Computers,2012,35(11):2306-2316.)
[5] ZOU Y, LIU J, WANG S, et al. CCIndex:a complemental clustering index on distributed ordered tables for multi-dimensional range queries[C]//Proceedings of the 2010 IFIP International Conference on Network and Parallel Computing, LNCS 6289. Berlin:Springer,2010:247-261.
[6] TAN W,TATA S,TANG Y. Diff-Index:differentiated index in distributed log-structured data stores[C]//Proceedings of the 17th International Conference on Extending Database Technology. New York:ACM,2014:700-711.
[7] ALSUBAIEE S, BEHM A, BORKAR V, et al. Storage management in AsterixDB[J]. Proceedings of the VLDB Endowment,2014,7(10):841-852.
[8] ALSUBAIEE S,ALTOWIM Y,ALTWAIJRY H,et al. AsterixDB:a scalable,open source BDMS[J]. Proceedings of the VLDB Endowment,2014,7(14):1905-1916.
[9] 翁海星. 面向读写分离、批量更新存储机制的高效分布式索引[D]. 上海:华东师范大学,2016:8.(WENG H X. A high performance distributed index designed for read/write isolated and batch-update storage[D]. Shanghai:East China Normal University,2016:8.)
[10] MUSA O,CHEN X,ZHOU C. Combustion characteristics and turbulence modeling of swirling reacting flow in solid fuel ramjet[J]. Acta Astronautica,2017,139:1-17.
[11] 马文龙, 朱妤晴, 蒋德钧, 等. Key-Value型NoSQL本地存储系统研究[J]. 计算机学报,2018,41(8):1722-1751.(MA W L, ZHU Y Q,JIANG D J,et al. A survey on local Key-Value store of NoSQL system[J]. Chinese Journal of Computers,2018,41(8):1722-1751.)
[12] 周敬才, 胡华平, 岳虹. 基于Lucene全文检索系统的设计与实现[J]. 计算机工程与科学,2015,37(2):252-256.(ZHOU J C, HU H P,YUE H. Design and implementation of Lucene-based full-text retrieval system[J]. Computer Engineering and Science, 2015,37(2):252-256.)
[13] WANG L,CHEN B,LIU Y. Distributed storage and index of vector spatial data based on HBase[C]//Proceedings of the 21st International Conference on Geoinformatics. Piscataway:IEEE, 2013:1-5.
[14] 徐江峰, 谭玉龙. 基于HBase的多维索引查询机制的优化[J]. 计算机应用,2020,40(2):571-577.(XU J F,TAN Y L. Optimization of multi-dimensional index query mechanism based on HBase[J]. Journal of Computer Applications,2020,40(2):571-577.)
[15] 李斌, 郭景维, 彭骞. 面向大数据存储的HBase二级索引设计[J]. 计算技术与自动化,2019,38(2):124-129.(LI B,GUO J W,PENG Q. Design of HBase secondary indexes for big data storage[J]. Computing Technology and Automation,2019,38(2):124-129.)
[16] YOON H,YANG J,KRISTJANSSON S F,et al. MUTANT:balancing storage cost and latency in LSM-tree data stores[C]//Proceedings of the 2018 ACM Symposium on Cloud Computing. New York:ACM,2018:162-173.
[17] QADER M A,CHENG S,HRISTIDIS V. A comparative study of secondary indexing techniques in LSM-based NoSQL databases[C]//Proceedings of the 2018 International Conference on Management of Data. New York:ACM,2018:551-566.
[18] ZOU Z,ZHENG L,XIA D,et al. CSIndex:a coprocessor-based classified secondary index mechanism for efficient HBase query[C]//Proceedings of the 2019 IEEE International Conference on Parallel and Distributed Processing with Applications,Big Data & Cloud Computing, Sustainable Computing & Communications, Social Computing & Networking. Piscataway:IEEE, 2019:897-904.
[19] YE F,ZHU S,LOU Y,et al. Research on index mechanism of HBase based on coprocessor for sensor data[C]//Proceedings of the IEEE 43rd Annual Computer Software and Applications Conference. Piscataway:IEEE,2019:598-603.
[20] ZHANG P, XING L, YANG N, et al. Redis++:a high performance in-memory database based on segmented memory management and two-level hash index[C]//Proceedings of the 16th IEEE International Symposium on Parallel and Distributed Processing with Applications/17th IEEE International Conference on Ubiquitous Computing and Communications/8th IEEE International Conference on Big Data and Cloud Computing/11th IEEE International Conference on Social Computing and Networking/8th IEEE International Conference on Sustainable Computing and Communications. Piscataway:IEEE, 2018:840-847.

基于日志结构合并树的轻量级分布式索引实现方法

Implementation method of lightweight distributed index based on log structured merge-tree

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	张凌哲, 黄向东, 乔嘉林, 勾王敏浩, 王建民. 面向时序数据的两阶段日志结构合并树文件合并框架[J]. 计算机应用, 2021, 41(3): 618-622.
[2]	骆克云, 叶保留, 唐斌, 梅峰, 卢文达. 基于增量学习的RocksDB键值系统主动缓存机制[J]. 计算机应用, 2020, 40(2): 321-327.
[3]	裴泽锋, 牛保宁, 张锦文, Amjad Muhammad. 并行查询下查询执行计划的选择[J]. 计算机应用, 2020, 40(2): 420-425.
[4]	徐江峰, 谭玉龙. 基于HBase的多维索引查询机制的优化[J]. 计算机应用, 2020, 40(2): 571-577.
[5]	冯钧, 李顶圣, 陆佳民, 张立霞. 基于HBase的路网移动对象时空索引方法[J]. 计算机应用, 2018, 38(6): 1575-1583.
[6]	崔晨, 郑林江, 韩凤萍, 何牧君. 基于内存的HBase二级索引设计[J]. 计算机应用, 2018, 38(6): 1584-1590.
[7]	吴仁彪, 刘超, 屈景怡. 基于HBase和Hive的航班延误平台的存储方法[J]. 计算机应用, 2018, 38(5): 1339-1345.
[8]	房俊, 李冬, 郭会云, 王嘉怡. 面向海量交通数据的HBase时空索引[J]. 计算机应用, 2017, 37(2): 311-315.
[9]	刘青, 付印金, 倪桂强, 梅建民. 基于Hadoop平台的分布式重删存储系统[J]. 计算机应用, 2016, 36(2): 330-335.
[10]	邳文君, 宫秀军. 基于Hadoop架构的数据驱动的SVM并行增量学习算法[J]. 计算机应用, 2016, 36(11): 3044-3049.
[11]	翁海星, 宫学庆, 朱燕超, 胡华梁. 集群环境下分布式索引的实现[J]. 计算机应用, 2016, 36(1): 1-7.
[12]	李振举, 李学军, 谢剑薇, 李雁南. 基于HBase的海量地形数据存储[J]. 计算机应用, 2015, 35(7): 1849-1853.
[13]	陆婷, 房俊, 乔彦克. 基于HBase的交通流数据实时存储系统[J]. 计算机应用, 2015, 35(1): 103-107.
[14]	冯汝伟谢强丁秋林. 基于文本聚类与分布式Lucene的知识检索[J]. 计算机应用, 2013, 33(01): 186-188.
[15]	陈庆奎周利珍. 基于HBase的大规模无线传感网络数据存储系统[J]. 计算机应用, 2012, 32(07): 1920-1923.