并行计算框架Spark的自适应缓存管理策略

doi:10.3969/j.issn.0372-2112.2017.02.003

电子学报 ›› 2017, Vol. 45 ›› Issue (2): 278-284.DOI: 10.3969/j.issn.0372-2112.2017.02.003

并行计算框架Spark的自适应缓存管理策略

卞琛^1,2, 于炯¹, 英昌甜¹, 修位蓉¹

1. 新疆大学信息科学与工程学院, 新疆乌鲁木齐 830046;
2. 乌鲁木齐职业大学信息工程学院, 新疆乌鲁木齐 830002

收稿日期:2015-09-02 修回日期:2015-11-16 出版日期:2017-02-25
- 作者简介:
- 卞琛,男,1981年出生.博士研究生,CCF会员.主要研究方向包括:内存计算、高性能计算、分布式系统等.E-mail:bianchen0720@126.com;于炯,男,1964年出生.教授、博士生导师,CCF高级会员.主要研究方向包括:网格计算、并行计算、分布式系统等.
- 基金资助:
- 国家自然科学基金 (No.61262088，No.61462079）

Self-Adaptive Strategy for Cache Management in Spark

BIAN Chen^1,2, YU Jiong¹, YING Chang-tian¹, XIU Wei-rong¹

1. School of Information Science and Engineering, Xinjiang University, Urumqi, Xinjiang 830046, China;
2. School of Information and Engineering, Urumqi Vocational University, Urumqi, Xinjiang 830002, China

Received:2015-09-02 Revised:2015-11-16 Online:2017-02-25 Published:2017-02-25

摘要/Abstract

摘要：

并行计算框架Spark缺乏有效缓存选择机制，不能自动识别并缓存高重用度数据；缓存替换算法采用LRU，度量方法不够细致，影响任务的执行效率.本文提出一种Spark框架自适应缓存管理策略（Self-Adaptive Cache Management，SACM），包括缓存自动选择算法（Selection）、并行缓存清理算法（Parallel Cache Cleanup，PCC）和权重缓存替换算法（Lowest Weight Replacement，LWR）.其中，缓存自动选择算法通过分析任务的DAG（Directed Acyclic Graph）结构，识别重用的RDD并自动缓存.并行缓存清理算法异步清理无价值的RDD，提高集群内存利用率.权重替换算法通过权重值判定替换目标，避免重新计算复杂RDD产生的任务延时，保障资源瓶颈下的计算效率.实验表明：我们的策略提高了Spark的任务执行效率，并使内存资源得到有效利用.

关键词: 并行计算, 缓存管理策略, Spark, 弹性分布式数据集

Abstract:

As a parallel computation framework,Spark does not have a good strategy to select valuable RDD to cache in limited memory.When memory has been full load,Spark will discard the least recently used RDD while ignoring other factors such as the computation cost and so on.This paper proposed a self-adaptive cache management strategy (SACM),which comprised of automatic selection algorithm(Selection),parallel cache cleanup algorithm (PCC) and lowest weight replacement algorithm (LWR).Selection algorithm can seek valuable RDDs and cache their partitions to speed up data intensive computations.PCC clean-up the valueless RDD sasynchronously to improve memory utilization.LWR takes comprehensive consideration of the usage frequency of RDD,the RDD's computation cost,and the size of RDD.Experiment results show that Spark with our selection algorithm calculates faster than traditional Spark,parallel cleanup algorithm contributes to the improvement of memory utilization,and LWR shows better performance in limited memory.

Key words: parallel computing, cache management strategy, Spark, resilient distribution datasets

中图分类号:

TP311

卞琛, 于炯, 英昌甜, 修位蓉. 并行计算框架Spark的自适应缓存管理策略[J]. 电子学报, 2017, 45(2): 278-284.

BIAN Chen, YU Jiong, YING Chang-tian, XIU Wei-rong. Self-Adaptive Strategy for Cache Management in Spark[J]. Acta Electronica Sinica, 2017, 45(2): 278-284.

参考文献

[1] Zaharia M,Das T,Li H,et al.Discretized streams:An efficient and fault-tolerant model for stream processing on large clusters[A].Proceedings of the 4th USENIX Workshop on Hot Topics in Cloud Computing[C].Boston,MA:USENIX,2012.1-6.
[2] Apache Spark.Spark Overview[EB/OL].http://spark.apache.org,2015-01-21/2015-03-18.
[3] Zaharia M,Chowdhury M,Das T,et al.Resilientdistributed datasets:A fault-tolerant abstraction for in-memory cluster computing[A].Proceedings of the 9th USENIX Conference on Networked Systems Design and Implementation[C].Berkeley,CA:USENIX,2012.1-14.
[4] Young N.On-line file caching[A].Proceedings of the 9th Annual ACM-SIAM Symposium on DiscreteAlgorithms[C].Baltimore,MD:ACM,1999.82-86.
[5] Swain D,Paikaray B,Swain D.AWRP:Adaptive weight ranking policy for improving cache performance[EB/OL].http://arxiv.org/abs/1107.4851,2011-07-25/2015-03-18.
[6] FANG Juan,WANG Jing,LI Chengyan,et al.Partition-based cache replacement to manage shared L2 caches[J].Chinese Journal of Electronics,2014,23(3):464-467.
[7] 司成祥,孟晓烜,许鲁.一种针对websearch应用的缓存替换算法[J].电子学报,2011,39(5):1205-1209. SI Chengxiang,MENG Xiaoxuan,XU Lu.A novel replacement algorithm designed for websearchapplications[J].Acta Electronica Sinica,2011,39(5):1205-1209.(in Chinese)
[8] Byan S,Lentini J,Madan A,et al.Mercury:Host-side flash caching for the datacenter[A].Proceedings of the 28th Symposium on Mass Storage Systems and Technologies[C].New York,NY:ACM,2012.1-12.
[9] HaoyuanLi,Ghodsi A,Zaharia M,et al.Tachyon:Reliable,memory speed storage for cluster computing frameworks[A].Proceedings of the 27th IEEE Conference on SYSTEM-ON-CHIP[C].Las Vegas,NV:IEEE,2014.1-15.
[10] Ongaro D,Rumble S M,Stutsman R,et al.Fast crash recovery in RAMCloud[A].Proceedings of 23th ACM Symposium on Operating Systems Principles[C].New York,NY:ACM,2011.29-41.
[11] Ghodsi A,Zaharia M,Shenker S,et al.Choosy:Max-min fair sharing for datacenter jobs with constraints[A].Proceedings of the 8th ACM European Conference on Computer Systems[C].New York,NY:ACM,2013.365-378.
[12] Jure L.Stanford Network Analysis Project[EB/OL].http://snap.stanford.edu/,2013-05-16/2015-03-18.

[1]	袁海英, 曾智勇, 成君鹏. 面向灵活并行度的稀疏卷积神经网络加速器[J]. 电子学报, 2022, 50(8): 1811-1818.
[2]	田春生, 陈雷, 王源, 王硕, 周婧, 张瑶伟, 庞永江, 周冲, 马筱婧, 杜忠, 薛钰. 面向FPGA的布局与布线技术研究综述[J]. 电子学报, 2022, 50(5): 1243-1254.
[3]	廖彬, 黄静莱, 王鑫, 孙瑞娜, 葛晓燕, 国冰磊. SCEA:一种适应高维海量数据的并行聚类集成算法[J]. 电子学报, 2021, 49(6): 1077-1087.
[4]	王卫杰, 胡少亮, 郑宇腾, 赵振国, 周海京. 并行预处理有限元方法及其在系统级封装结构电磁模拟中的应用[J]. 电子学报, 2021, 49(1): 58-63.
[5]	晋云霞, 杨贺昆, 冯朝胜, 刘帅南, 李航, 邹莉萍, 万国根. 一种支持解密外包的KP-ABE方案[J]. 电子学报, 2020, 48(3): 561-567.
[6]	刘公绪, 史凌峰, 辛东金. 基于FPGA的零误差大数阶乘算法的设计与实现[J]. 电子学报, 2019, 47(5): 1180-1184.
[7]	王卫杰, 陈晓洁, 周海京. 基于区域分解的大规模并行有限元快速算法[J]. 电子学报, 2019, 47(3): 741-747.
[8]	曲志坚, 陈宇航, 李盘靖, 刘晓红, 李彩虹. 基于多算子协同进化的自适应并行量子遗传算法[J]. 电子学报, 2019, 47(2): 266-273.
[9]	杨林峰, 胡桂莉, 张晨, 张振荣. 基于CPU-GPU协同并行内点算法求解结构化非线性规划[J]. 电子学报, 2019, 47(2): 382-389.
[10]	潘剑飞, 董一鸿, 陈华辉, 钱江波, 戴明洋. 基于结构紧密性的重叠社区发现算法[J]. 电子学报, 2019, 47(1): 145-152.
[11]	金宏桥, 董一鸿, 陈华辉, 钱江波. 分布式环境下基于马尔科夫链的图流三角近似计算[J]. 电子学报, 2018, 46(9): 2139-2148.
[12]	冯晓, 戴紫彬, 蔡路亭, 李伟. 基于Amdahl定律扩展的多核处理器性能模型研究[J]. 电子学报, 2017, 45(6): 1424-1430.
[13]	潘卫国, 何宁, 薛健, 吕科, 翟锐, 代双凤. 海量超声数据体可视化研究[J]. 电子学报, 2016, 44(2): 472-478.
[14]	周旭, 周炎涛, 李肯立, 欧阳艾嘉, 潘果. 基于Tile自组装模型的最大匹配问题算法研究[J]. 电子学报, 2015, 43(2): 262-268.
[15]	徐红, 黄朝耿, 宋洪波, 周志光, 李刚. 并行计算的全通数字滤波器结构[J]. 电子学报, 2015, 43(10): 2034-2039.

并行计算框架Spark的自适应缓存管理策略

Self-Adaptive Strategy for Cache Management in Spark

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics