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

doi:10.11772/j.issn.1001-9081.2019091616

《计算机应用》唯一官方网站 ›› 2020, Vol. 40 ›› Issue (2): 321-327.DOI: 10.11772/j.issn.1001-9081.2019091616

• 2019年全国开放式分布与并行计算学术年会(DPCS 2019)论文 • 上一篇下一篇

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

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

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

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

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)

摘要/Abstract

摘要：

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

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

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

中图分类号:

TP311

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

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.

图/表 7

图1 日志结构合并树示意图

Fig. 1 Schematic diagram of log-structured merge tree

图2 基于预测分析的主动缓存框架

Fig. 2 Prediction and analysis based proactive caching framework

表1 主动缓存服务器端Rest路由

Tab. 1 Rest routing on server side with proactive caching

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

图3 主动缓存系统时序图

Fig. 3 Sequence diagram of proactive caching system

图4 主动缓存模型训练和预测流程

Fig. 4 Training and prediction process of proactive caching model

图5 主动缓存模型性能折线图

Fig. 5 Line chart of performance of proactive caching model

图6 主动缓存模型每秒查询数折线图

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

参考文献 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]	崔双双, 王宏志. 基于日志结构合并树的轻量级分布式索引实现方法[J]. 计算机应用, 2021, 41(3): 630-635.
[2]	张凌哲, 黄向东, 乔嘉林, 勾王敏浩, 王建民. 面向时序数据的两阶段日志结构合并树文件合并框架[J]. 计算机应用, 2021, 41(3): 618-622.
[3]	罗长银, 陈学斌, 马春地, 王君宇. 面向区块链的在线联邦增量学习算法[J]. 计算机应用, 2021, 41(2): 363-371.
[4]	邓文瀚, 张铭, 王李进, 钟一文. 混合群体增量学习算法求解闭环布局问题[J]. 计算机应用, 2021, 41(1): 95-102.
[5]	刘丹, 姚立霜, 王云锋, 裴作飞. 面向类不平衡流量数据的分类模型[J]. 计算机应用, 2020, 40(8): 2327-2333.
[6]	忽丽莎, 王素贞, 陈益强, 胡春雨, 蒋鑫龙, 陈振宇, 高兴宇. 基于目标均衡度量的核增量学习跌倒检测方法[J]. 计算机应用, 2018, 38(4): 928-934.
[7]	汪金涛, 曹玉东, 孙福明. 稀疏约束图正则非负矩阵分解的增量学习算法[J]. 计算机应用, 2017, 37(4): 1071-1074.
[8]	霍纬纲, 屈峰, 程震. 基于演进向量量化聚类的增量模糊关联分类方法[J]. 计算机应用, 2017, 37(11): 3075-3079.
[9]	陈斌, 东一舟, 毛明荣. 基于增量学习算法的校园网垃圾邮件检测模型[J]. 计算机应用, 2017, 37(1): 206-211.
[10]	邢志伟, 唐云霄, 罗谦. 基于贝叶斯网络的航班保障服务时间动态估计[J]. 计算机应用, 2017, 37(1): 299-304.
[11]	邳文君, 宫秀军. 基于Hadoop架构的数据驱动的SVM并行增量学习算法[J]. 计算机应用, 2016, 36(11): 3044-3049.
[12]	胡银辉, 陈琳. 大规模InfiniBand网络自学习的故障诊断方法[J]. 计算机应用, 2015, 35(11): 3092-3096.
[13]	李平红王勇陶晓玲. 支持向量机的半监督网络流量分类方法[J]. 计算机应用, 2013, 33(06): 1515-1518.
[14]	周雪燕韩建敏詹宇斌. 基于局部平滑性的通用增量流形学习算法[J]. 计算机应用, 2012, 32(06): 1670-1673.
[15]	许明英尉永清赵静. 一种结合反馈信息的贝叶斯分类增量学习方法[J]. 计算机应用, 2011, 31(09): 2530-2533.

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

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 21

相关文章 15

编辑推荐

Metrics