推荐星级：
- 1
- 2
- 3
- 4
- 5
并行计算框架Spark的自适应缓存管理策略
资料介绍
并行计算框架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的自适应缓存管理策略.pdf | 1M |
部分页面预览
（完整内容请下载后查看）2
Vol． 45 No． 2
Feb． 2017
第
期
电
子
学
报
2017
2
ACTA ELECTRONICA SINICA
年
月
Spark
并行计算框架
的自适应缓存管理策略
1，2
1
1
1
， ， ，
卞 琛 于 炯 英昌甜 修位蓉
( 1．
，
新疆大学信息科学与工程学院 新疆乌鲁木齐
830046; 2．
，
乌鲁木齐职业大学信息工程学院 新疆乌鲁木齐
830002)
:
Spark ， ;
缺乏有效缓存选择机制 不能自动识别并缓存高重用度数据 缓存替换算法采用
摘
要
并行计算框架
LRU， ， ．
度量方法不够细致 影响任务的执行效率 本文提出一种
Spark
( Self-Adaptive Cache
框架自适应缓存管理策略
Management，SACM) ，
包括缓存自动选择算法
( Selection) 、 ( Parallel Cache Cleanup，PCC)
并行缓存清理算法
和权重缓存
， DAG( Directed Acyclic Graph)
其中 缓存自动选择算法通过分析任务的
( Lowest Weight Replacement，LWR) ．
替换算法
，
RDD
．
RDD，
．
提高集群内存利用率 权重替换算法
结构 识别重用的
通过权重值判定替换目标 避免重新计算复杂
Spark
并自动缓存 并行缓存清理算法异步清理无价值的
，
RDD
， ． :
产生的任务延时 保障资源瓶颈下的计算效率 实验表明 我们的
，
．
策略提高了
的任务执行效率 并使内存资源得到有效利用
; Spark;
弹性分布式数据集
:
;
关键词
中图分类号
URL: http: / /www． ejournal． org． cn
并行计算 缓存管理策略
:
TP311
:
A
: 0372-2112 ( 2017) 02-0278-07
DOI: 10． 3969 /j． issn． 0372-2112． 2017． 02． 003
文献标识码
文章编号
电子学报
Self-Adaptive Strategy for Cache Management in Spark
1，2
1
1
1
BIAN Chen ，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)
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 in-
tensive computations． PCC clean-up the valueless RDD sasynchronously to improve memory utilization． LWR takes compre-
hensive 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
， ． ， Spark
要因素 度量方法不够细致 因此 研究 框架自适
1
引言
．
应缓存策略具有一定的现实意义
典型 的 缓 存 替 换 算 法 包 括
LRFU、MIN
利用内存的低延迟特性改进系统性能成为并行计
: FIFO、LRU、LFU、
等 这些算法在并行计算框架得到广泛应
［1，2］
． Spark
Hadoop
算新的研究方向
是继
之后出现的通
( Resil-
．
，
用高性能并行计算框架 采用弹性分布式数据集
， ．
用 但性能表现并不理想 另外的一些研究成果则在缓
［3］
ient Distributed Datasets，RDD)
． Spark
作为数据结构
， ［4］ FIFO
存替换算法中加入了不同的参数 文献 在
和
， ，
缓存管理策略中 程序员掌握缓存对象的选择权 增加
LRU
，
算法的基础上进行改进 引入附加参数进行置换
．
了缓存策略的不确定性 缓存替换算法采用
LRU，
未考
，
目标的计算 但其参数选择不适用于
Spark．
［5］
文献
提
RDD
虑
计算代价及容量等影响应用程序执行效率的重
AWRP( Adaptive Weight Ranking Policy)
出的
算法为每
: 2015-09-02;
: 2015-11-16; :
责任编辑 蓝红杰
收稿日期
修回日期
:
基金项目 国家自然科学基金
( No． 61262088，No． 61462079)
279
2
: Spark
琛 并行计算框架 的自适应缓存管理策略
第
期
卞
，
个缓存对象计算权重 并优先转换权重值最低的缓存
2. 2
内存资源模型
，
在并行计算集群中 资源池由一系列工作节点构
， ．
对象 但权重计算方法不具有普适性 其他一些研究成
．
果则考虑的是不同的系统特性和应用场景 文献
［6］
针
，
成 定义工作节点集合
W = { 1，2，…，m} ，
集群内存资源
，
对多核处理器的高速缓存 设计了基于分区结构缓存
R = { r ，r ，…，r } ．
集合
时间段内运行的任务
Tasks = { 1，2，…，n}
为同一
记
1
2
m
; ［7］ websearch
替换算法 文献 提出了针对 应用的缓存
，A
i m
为任务 在工作节点 上的
im
; ［8］ ，
替换算法 文献 则利用闪存的低延迟优势 设计了
，
内存分配量 则任务的内存资源总量可表示为
:
．
基于闪存的多级缓存管理系统
A = A ，i Tasks
∈
∑
im
( 1)
i
m
W
∈
，
近年来 一些研究人员致力于内存文件系统的研
Spark
，
保证所有任务的并发执行 当且仅当每
由于
． ［9］
发 文献 提出了
Tachyon，
一种基于内存的分布式文
， :
个工作节点的内存资源都不会溢出 即
．
件系统 但在
Tachyon
，
的实 现中 替换算法 仍然采用
A
＜ r ，m
W
( 2)
根据任务对资源需求的贪婪效应 当内存资源充
RDD
∈
∑
im
m
LRU．
［10］ RAMCloud，
提 出 了 内 存 文 件 系 统 但
文献
i
Tasks
∈
RAMCloud
Spark
，
都属于高内存占用型系统 无法相
和
，
．
互兼容
本文提出一种基于
，
i
足时 集群为任务 分配的内存资源应与任务所有
Spark
框架的自适应缓存管理
， ，
大小之和相等 而当内存资源不足时 分配内存小于
( Self-Adaptive Cache Management，SACM) ，
包括缓
策略
RDD
．
大小之和 即
:
、
存自动化 有效缓存替换和提高内存利用率等方面的
RDD
A
≥
i
( 3)
∑
ij
j
Task
i
∈
， ，
多项改进措施 最大限度消除内存资源瓶颈影响 使集
1
．
内存有效利用原则 在不影响任务执行效
定理
． ，
群发挥最佳效能 相比于已有的研究工作 自适应缓存
， ，
率的前提下 任务的内存占用率越低 集群内存资源的
Spark
．
框架的性能优化
管理策略更适宜于
．
利用率越高
2
问题的建模与分析
i
证明 记任务 调度时集群的空闲内存容量为
S
， i A
则任务 在分配方案 下成功调度的概率为
i
:
vacant
Spark
，
任务的执行机制 建立内存资
本节首先分析
S
vacant
、
源模型 任务执行效率模型和
RDD
，
权重模型 最后提出
P =
( 4)
A 、A ， A ＞ A ．
A
i
．
自适应缓存管理策略的问题定义
i
设任务 的两种内存分配方案为
且
x
y
x
y
2. 1 Spark
任务执行机制
t，
两种分配方案下任务的执行时间均为 由于
S
为常
vacant
Spark
，
的任务执行采用了延时调度机制 即当用户
RDD Action RDD
的
，
数 因此
P ＜ P ，
即内存占用率越低的分配方案调度成
y
x
，
对一个
lineage
执行
操作时 调度器会根据
，
功的概率越高 集群内存的利用率也越高
．
DAG，
然后为工作结点分配子任务
来构建一个
． Spark
2. 3
任务执行效率模型
Spark RDD
DAG 1 ．
的典型示例如图 所示 其
执行程序
中实线圆角方框表示
Stage． Spark
任务
，
划分成多个分区 交由工作节点并行
将
RDD， ，
填充矩形表示分区 虚线框
． ， i，
计算 因此 对于每一个任务 记其
RDD
Task
集合为
i
Stage，
每个
Stage
都包含
为
根据宽依赖划分
= { RDD ，RDD ，…，RDD } ，
这里
ij
RDD
i
表示任务 中
i1
i2
ij
，Stage
尽可能多的连续窄依赖
Stage
内部的窄依赖前后连接
j
第 个
RDD．
RDD， RDD =
记其分区集合为
ij
对于每个
，
构成流水线 而各
，
则同步顺序执行 直到最终得出
{ P P ，…，P } ，
其中
ij1， ij2
P
RDD
k
中的第 个分区
．
表示
ijk
ijk
ij
RDD．
目标
1
RDD
． Spark
，
任务中 分区是以一
定义
计算代价
，
个或多个父节点为输入数据计算生成 设
Parents
为分
ijk
P
．
的父节点集合 分区的计算要读取所有的输入数
区
ijk
， ． P
据 然后根据闭包和操作类型进行计算 因此分区 的
ijk
，
计算代价为数据读取代价与数据处理代价之和 我们
， :
以分区计算时间作为衡量计算代价的唯一指标 即
T
= read( Parents ) + proc( Parents )
ijk
( 5)
Pijk
ijk
Parents
，
集合所有分区都存储在内存中 则数据
若
ijk
， read( Parents ) = 0． RDD
读取代价可以忽略 即
ijk
的所有
，
分区由集群工作节点并行计算生成 因此其计算代价
， :
为所有分区计算代价的最大值 即
T
= max( T ，T ，…，T
P
ij2
)
( 6)
RDDij
P
P
ijk
ij1
全部评论(0)