Incremental learning based proactive caching mechanism for RocksDB key-value system

doi:10.11772/j.issn.1001-9081.2019091616

Journal of Computer Applications ›› 2020, Vol. 40 ›› Issue (2): 321-327.DOI: 10.11772/j.issn.1001-9081.2019091616

• DPCS 2019 • Previous Articles Next Articles

Incremental learning based proactive caching mechanism for RocksDB key-value system

Keyun LUO¹, Baoliu YE¹(), Bin TANG¹, Feng MEI², Wenda LU²

^1.State Key Laboratory for Novel Software Technology （Nanjing University），Nanjing Jiangsu 210023，China
^2.State Grid Zhejiang Electric Power Company Limited，Hangzhou Zhejiang 310007，China

Received:2019-07-31 Revised:2019-09-24 Accepted:2019-09-29 Online:2019-10-14 Published:2020-02-10
Contact: Baoliu YE
About author:LUO Keyun， born in 1993， M. S. candidate. His research interests include distributed storage.
TANG Bin， born in 1986， Ph. D.， assistant research fellow. His research interests include distributed computing， coding theory.
MEI Feng， born in 1977， M. S.， senior engineer. His research interests include power information system， big data.
LU Wenda， born in 1989， M. S.， assistant engineer. His research interests include data mining， cloud computing.
Supported by:
the National Key Research and Development Program of China(2018YFB1004704);the National Natural Science Foundation of China(61832005);the Science and Technology Project of State Grid Corporation of China(52110418001M)

基于增量学习的RocksDB键值系统主动缓存机制

骆克云¹, 叶保留¹(), 唐斌¹, 梅峰², 卢文达²

^1.计算机软件新技术国家重点实验室（南京大学），江苏南京 210023
^2.国网浙江省电力有限公司，浙江杭州 310007

通讯作者: 叶保留
作者简介:骆克云（1993—），男，安徽芜湖人，硕士研究生，主要研究方向：分布式存储
唐斌（1986—），男，江苏东台人，助理研究员，博士，CCF会员，主要研究方向：分布式计算、编码理论
梅峰（1977—），男，浙江湖州人，高级工程师，硕士，主要研究方向：电力信息系统、大数据
卢文达（1989—），男，吉林松原人，助理工程师，硕士，主要研究方向：数据挖掘、云计算。
基金资助:
国家重点研发计划项目(2018YFB1004704);国家自然科学基金资助项目(61832005);国家电网公司科技项目(52110418001M)

Abstract

Abstract:

RocksDB key-value storage system based on Log-Structured Merge （LSM） tree has the problem of low read performance caused by the constraints of its hierarchical structure. One effective solution is to cache hot spot data proactively， but it faces two challenges. One is how to predict the hot spot data when the data distribution keeps on changing constantly， the other is how to integrate the proactive caching mechanism with the RocksDB storage structure. To tackle these challenges， a proactive caching framework for RocksDB key-value system with multiple components including data collection， system interaction and system evaluation was built， which can cache the hot spot data at the low levels of the LSM tree. And with the modeling of data access patterns， an incremental learning based prediction analysis method for hot spot data was designed and implemented， which can reduce the number of I/O operations of storage medium. Experimental results show that the proposed mechanism can effectively improve the read performance of RocksDB under different dynamic workloads.

Key words: RocksDB, proactive caching, incremental learning, Log-Structured Merge (LSM) tree

摘要：

由于分层结构的约束，基于日志结构合并（LSM）树的RocksDB键值存储系统面临着读取性能低下的问题。一种有效的解决方法是对热点数据进行主动缓存，但其面临两个挑战：一是如何在数据分布持续动态变化时对热点数据进行预测，二是如何将主动缓存机制与RocksDB存储结构衔接起来。针对这些挑战，基于预测分析技术，构建了由数据采集、系统交互、系统测试等部分组成的面向RocksDB键值系统的主动缓存框架，能够将热点数据缓存在LSM树的较低层级中；并对数据访问模式进行建模，设计并实现了基于增量学习的热点数据预测分析方法，能够有效减少存储介质的I/O访问次数。实验结果表明该机制能有效提升RocksDB在不同动态工作负载下的数据读取性能。

关键词: RocksDB, 主动缓存, 增量学习, 日志结构合并树

CLC Number:

TP311

Keyun LUO, Baoliu YE, Bin TANG, Feng MEI, Wenda LU. Incremental learning based proactive caching mechanism for RocksDB key-value system[J]. Journal of Computer Applications, 2020, 40(2): 321-327.

骆克云, 叶保留, 唐斌, 梅峰, 卢文达. 基于增量学习的RocksDB键值系统主动缓存机制[J]. 《计算机应用》唯一官方网站, 2020, 40(2): 321-327.

Figures/Tables 7

Fig. 1 Schematic diagram of log-structured merge tree

Fig. 2 Prediction and analysis based proactive caching framework

Tab. 1 Rest routing on server side with proactive caching

URL	请求类型	参数/返回值	说明
/state	Get	返回状态	客户端请求系统状态
/keys	Get	返回键集合	客户端请求重放的键集合
/files	Get	返回max_open_files	客户端请求打开的文件数设置
/task	Post	发送任务请求	客户端发送训练或预测请求

Fig. 3 Sequence diagram of proactive caching system

Fig. 4 Training and prediction process of proactive caching model

Fig. 5 Line chart of performance of proactive caching model

Fig. 6 Line chart of number of queries per second of proactive caching model

References 21

1	Facebook. A library that provides an embeddable， persistent key-value store for fast storage［EB/OL］. ［2019-03-30］.. 10.1145/3483840
2	O’NEIL P， CHENG E， GAWLICK D， et al. The Log-Structured Merge-tree （LSM-tree）［J］. Acta Informatica， 1996， 33（4）： 351-385. 10.1007/s002360050048
3	BRODER A， MITZENMACHER M. Network applications of Bloom filters： a survey［J］. Internet Mathematics， 2004， 1（4）： 485-509. 10.1080/15427951.2004.10129096
4	DAYAN N， ATHANASSOULIS M， IDREOS S. Monkey： optimal navigable key-value store［C］// Proceedings of the 2017 ACM International Conference on Management of Data. New York： ACM， 2017： 79-94. 10.1145/3035918.3064054
5	DAYAN N， IDREOS S. Dostoevsky： better space-time trade-offs for LSM-tree based key-value stores via adaptive removal of superfluous merging［C］// Proceedings of the 2018 International Conference on Management of Data. New York： ACM， 2018： 505-520. 10.1145/3183713.3196927
6	SHVACHKO K， KUANG H， RADIA S， et al. The Hadoop distributed file system［C］// Proceedings of the IEEE 26th Symposium on Mass Storage Systems and Technologies. Piscataway： IEEE， 2010： 1-10. 10.1109/msst.2010.5496972
7	BUI D M， HUSSAIN S， HUH E N， et al. Adaptive replication management in HDFS based on supervised learning［J］. IEEE Transactions on Knowledge and Data Engineering， 2016， 28（6）： 1369-1382. 10.1109/tkde.2016.2523510
8	PARETO. Pareto principle［EB/OL］. ［2019-02-22］.. 10.24108/preprints-3112193
9	骆克云.基于机器学习的RocksDB存储引擎配置优化［D］.南京：南京大学，2019：16-21. 10.35745/ecei2019v2.035
	LUO K Y. Configuration optimization of RocksDB storage engine based on machine learning［D］. Nanjing： Nanjing University， 2019： 16-21. 10.35745/ecei2019v2.035
10	Google. LevelDB is a fast key-value storage library written at Google that provides an ordered mapping from string keys to string values［EB/OL］. ［2019-03-30］.. 10.4324/9781315877549-13
11	GEORGE L. HBase： The Definitive Guide： Random Access to Your Planet-Size Data［M］. Sebastopol， CA： O’Reilly Media， 2011.
12	GRUMMON J L， FRANKLIN C R. System and method for disk control with snapshot feature including read-write snapshot half： US 6341341［P］. 2002-01-22 ［2019-01-12］.
13	LIEDTKE J， HARTIG H， HOHMUTH M. OS-controlled cache predictability for real-time systems［C］// Proceedings of the 3rd IEEE Real-Time Technology and Applications Symposium. Piscataway： IEEE， 1997： 213-224. 10.1109/rttas.1997.601360
14	DONG S， CALLAGHAN M， GALANIS L， et al. Optimizing space amplification in RocksDB［EB/OL］. ［2019-02-22］.. 10.1016/j.disc.2007.09.028
15	秦秀磊，张文博，魏峻，等.云计算环境下分布式缓存技术的现状与挑战［J］.软件学报，2013，24（1）：50-66. 10.3724/SP.J.1001.2013.04276
	QIN X L， ZHANG W B， WEI J， et al. Progress and challenges of distributed caching techniques in cloud computing［J］. Journal of Software， 2013 ，24（1）：50-66. 10.3724/SP.J.1001.2013.04276
16	周志华.机器学习［M］.北京：清华大学出版社，2016：108-109. 10.21436/inbom.12382432
	ZHOU Z H. Machine Learning［M］. Beijing： Tsinghua University Press， 2016： 108-109. 10.21436/inbom.12382432
17	LIVELY T， SCHROEDER L， MENDIZÁBAL C. Splaying log-structured merge-trees［C］// Proceedings of the 2018 International Conference on Management of Data. New York： ACM， 2018： 1839-1841. 10.1145/3183713.3183723
18	ROSS S M.应用随机过程：概率模型导论［M］.龚光鲁，译.11版.北京：人民邮电出版社，2016：39-49.
	ROSS S M. Introduction to Probability Models［M］. GONG G L， translated.11st ed. Beijing： Posts and Telecom Press， 2016： 39-49.
19	PEDREGOSA F， VAROQUAUX G， GRAMFORT A， et al. Scikit-learn： machine learning in Python［J］. Journal of Machine Learning Research， 2011， 12： 2825-2830. 10.3389/fninf.2014.00014
20	VAROQUAUX G， GRISEL O. Joblib： running python function as pipeline jobs［EB/OL］. ［2019-02-22］. .
21	GOUTTE C， GAUSSIER E. A probabilistic interpretation of precision， recall and F-score， with implication for evaluation［C］// Proceedings of the 2005 European Conference on Information Retrieval， LNCS3408. Berlin： Springer， 2005： 345-359.

[1]	LUO Changyin, CHEN Xuebin, MA Chundi, WANG Junyu. Online federated incremental learning algorithm for blockchain [J]. Journal of Computer Applications, 2021, 41(2): 363-371.
[2]	DENG Wenhan, ZHANG Ming, WANG Lijin, ZHONG Yiwen. Hybrid population-based incremental learning algorithm for solving closed-loop layout problem [J]. Journal of Computer Applications, 2021, 41(1): 95-102.
[3]	LIU Dan, YAO Lishuang, WANG Yunfeng, PEI Zuofei. Classification model for class imbalanced traffic data [J]. Journal of Computer Applications, 2020, 40(8): 2327-2333.
[4]	YANG Liangdong, YANG Zhixia. Incremental robust non-negative matrix factorization with sparseness constraints and its application [J]. Journal of Computer Applications, 2019, 39(5): 1275-1281.
[5]	CHEN Ping, GONG Xun. Face alignment method based on scale self-adaption and incremental learning [J]. Journal of Computer Applications, 2018, 38(7): 2064-2069.
[6]	HU Lisha, WANG Suzhen, CHEN Yiqiang, HU Chunyu, JIANG Xinlong, CHEN Zhenyu, GAO Xingyu. Objective equilibrium measurement based kernelized incremental learning method for fall detection [J]. Journal of Computer Applications, 2018, 38(4): 928-934.
[7]	WANG Jintao, CAO Yudong, SUN Fuming. Incremental learning algorithm based on graph regularized non-negative matrix factorization with sparseness constraints [J]. Journal of Computer Applications, 2017, 37(4): 1071-1074.
[8]	HUO Weigang, QU Feng, CHENG Zhen. Incremental fuzzy associative classification method based on evolving vector quantization clustering algorithm [J]. Journal of Computer Applications, 2017, 37(11): 3075-3079.
[9]	XING Zhiwei, TANG Yunxiao, LUO Qian. Dynamic estimation about service time of flight support based on Bayesian network [J]. Journal of Computer Applications, 2017, 37(1): 299-304.
[10]	CHEN Bin, DONG Yizhou, MAO Mingrong. Spam detection model of campus network based on incremental learning algorithm [J]. Journal of Computer Applications, 2017, 37(1): 206-211.
[11]	PI Wenjun, GONG Xiujun. Data driven parallel incremental support vector machine learning algorithm based on Hadoop framework [J]. Journal of Computer Applications, 2016, 36(11): 3044-3049.
[12]	HU Yinhui, CHEN Lin. Incremental learning method for fault diagnosis in large-scale InfiniBand network [J]. Journal of Computer Applications, 2015, 35(11): 3092-3096.
[13]	LI Pinghong WANG Yong TAO Xiaoling. A Semi-supervised Network Traffic Classification Method Based on Support Vector Machine [J]. Journal of Computer Applications, 2013, 33(06): 1515-1518.
[14]	XU Ming-ying WEI Yong-qing ZHAO Jing. Incremental learning method of Bayesian classification combined with feedback information [J]. Journal of Computer Applications, 2011, 31(09): 2530-2533.
[15]	REN Lei. Hybrid recommendation approach based on incremental learning [J]. Journal of Computer Applications, 2010, 30(05): 1287-1289.

Incremental learning based proactive caching mechanism for RocksDB key-value system

基于增量学习的RocksDB键值系统主动缓存机制

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 21

Related Articles 15

Recommended Articles

Metrics