使用分布式缓存加速并行作业执行—PACMan(NSDI2012)

二月 10th, 2012 by klose | Posted under 海量数据存储与处理.

背景

Hadoop的数据本地性,通过在集群中数据节点和计算节点的复用(co-locate storage and computation),MapTask调度到数据分片所在的DataNode节点上。HDFS将大数据按照Block的方式进行切分、复制存储,保证了数据分片存在多个节点,从而提高本地性的命中率。然而,Hadoop目前所提供的本地性,仅仅是指节点文件的本地读取,而根据存储体系结构的hierarchy,本地内存的访问速度比本地磁盘高一个数量级,同时,近些年来,内存价格的下降,服务器集群配置单点32GB64GB成为了一个普遍的现象。因此,如果想进一步提升作业的执行效率,将数据放入内存缓存,保证良好的本地性特征,成为了提升数据处理系统性能的重要突破口。

Berkeley的最新研究成果PACManCoordinated Memory Caching for Parallel Jobs(NSDI2012),在如上的背景下,提出的一个支撑并行作业的内存缓存系统。

 

大型生产系统的日志分析

PACMan对于FacebookYahoo!、Microsoft Bing的生产集群的log进行了分析,得到的如下的结论:

1)集群的内存资源没有得到很好的使用。Facebook集群平均(Median)只使用19%的内存,内存资源没有得到广泛使用。

2)作业的数据载入处理阶段,例如(HadoopMapDryadextract),属于IO密集型,占用79%的作业执行时间和69%的集群资源。

3)大多数的数据被多次访问,只有6%的数据只处理一次。

pacman-1.png

 

上图给出了一个大型集群中作业统计信息。其中figure3,指出大部分的作业访问了不到10%的数据。figure4指出输入数据集与jobtask的个数强相关。figure5指出了大部分的作业的输入数据都可以完全载入内存。figure6指出文件的大小和并行执行的task的个数(wave-width)相关。

基于此,缓存作业的输入数据到分布式内存系统,可以加快作业IO-intensive阶段的处理。

 

核心问题

使用内存缓存数据,是一个在操作系统、数据库、web系统中常用的方式。通过将数据缓存在内存,使用高一级的Cache来加速数据读取。然而,在分布式数据处理系统,尤其在DFS之上,有一些新的问题和矛盾。

1)是否缓存作业的全部输入数据,还是缓存一部分,两者是否有区别。

2)如何选择一个合适的内存替换算法,是缓存系统成败的关键。

3)如何与原始的分布式数据处理交互,提供Memory-locality特性。

4System Architecture

 

 

系统设计和解决方案

1 内存替换算法

针对Whole-Jobs缓存和替换数据。

pacman-2.png

 

这里回答核心问题1),假设J1J2被执行,它们的输入数据块分别为J1{A.B}, J2{C ,D},作业执行完成之后,Cache的状况为{A, B, C, D},那么在新的数据块到来,应该如何替换Cache中的数据呢?MIN算法会淘汰将来最迟访问的数据块,当再次执行J1 J2时,J1J2的其中一个task都会出现cache miss现象,根据并行作业执行的一个leveltask按照最迟完成的task来计算的话,J1J2都没有缩短执行时间。

quote: MIN will evict the blocks accessed farthest in the future: B and D. Then, when J1 and J2 run, they both experience a cache miss on one of their tasks. These cache misses bound completion time for both jobs, meaning that MIN cache replacement resulted in no reduction in completion time for either J1 or J2.

PACMan使用Whole-Jobs的方式,按照作业的并行粒度(wave-width)来做整体替换,例如Figure9J2的两个数据块CDCache中清除,使得再次运行J1时,仍然有全部的Cache hit-ratio,而J2的执行时间不受影响。

An input-aware scheduler would recognize the dependency between each job’s inputs, and instead of evicting the blocks accessed farthest-in-the-future, would evict at the granularity of a job’s wave-width. In this situation with two single-wave jobs, the input-aware scheduler in Figure 9 chooses to evict the input set of J2 (C and D). This results in a reduction in completion time for J1, since its wave’s entire input set of A and B is cached).J2’s completion time is unaffected. Note that the cache hit-ratio for MIN and whole-jobs is the same (50%).

PACMan使用whole-Job替换策略,但是应该替换什么样作业的数据,是核心问题2)。

采用什么样的需求,要根据系统的特点和要达到的目标来评估。PACMan提出两种不同的内存替换算法:LIFESIFE

LIFE致力于缩短集群作业的平均执行时间,即提高系统的作业吞吐率,采用了替换最大作业的数据块。(这里的最大作业、最小作业在每个数据分片相当的情况下,可以理解为并行粒度的大小,论文中的Wave-Width)。至于为什么要Cache小作业的数据,而替换大作业的数据,先查看下图。

pacman-3.png

这里width=2width=4,缩短相同的执行时间,但w=2却节省了更多的资源。因此,LIFE在替换大作业的数据。

SIFE算法与LIFE算法相反,优先替换最小作业的不完整数据。这里主要考虑到Large Jobs往往是一个生产系统中的核心业务作业,提高这些作业执行效率,有利于为上层应用提高更好的服务质量。

下面是两种算法的描述。

pacman-4.png

注意,算法中为了防止某些数据只被计算了一次,而长期占据Cache的情况,加入了Aging的统计信息,这样在一段时间内长期不被访问的数据,也会被替换。

2 与数据处理系统的交互

Hadoop为例介绍,Hadoop调度系统会根据Block的信息,向PACMan获取缓存Blockhostlist,同时,向HDFS接口获取数据块磁盘存储的hostlist,然后调度系统优先选择Memory-locality的节点,部署task

3 系统架构

pacman-5.png

PACMan采用了传统的Master-Slave架构,

PACMan Client跟踪数据Memory Cache中数据块的updageaddevict等,并上报给PACMan Coordinator

PACMan Coord 支持插件式的替换算法。它维护了整个缓存系统的全局视图,

1)维护了元数据信息,<every Cached block, the locations of client nodes that cache it>

2)在添加新的block时,决定如何布置数据块的位置。

3)保证一个合理的数据块替换机制。

 

实验评测

PACMan这篇论文中给出了很多的评测结果,这里仅列出一个代表性的数据表供参考。

pacman-6.png

 

总结

PACMan以实际生产集群的作业log信息为研究依据,分析了在大型集群中作业的数据访问模型,借鉴数据本地性的做法,通过Memory-Cache,提出更快的Locality解决方案,从而大大缩短了并行作业的IO-Intensive阶段的执行时间。

 

参考资料:

[Min 算法]Laszlo A. Belady. A Study of Replacement Algorithms for Virtual-Storage Computer. IBM Systems Journal, 1966.

本文下载:PACMan: Coordinated Memory Caching for Parallel Jobs [NSDI2012]  Berkeley

原创文章,转载请注明: 转载自 Binospace

本文链接地址: http://www.binospace.com/index.php/pacman/

 

From Binospace, post 使用分布式缓存加速并行作业执行—PACMan(NSDI2012)

文章的脚注信息由WordPress的wp-posturl插件自动生成





Tags: , ,

Comments

4 Responses to “使用分布式缓存加速并行作业执行—PACMan(NSDI2012)”
  1. klose 说道:

    test

  2. nickname 说道:

    test

  3. GaoYun 说道:

    虽然看不懂,不过看起来很厉害的样子……

Do you have any comments on 使用分布式缓存加速并行作业执行—PACMan(NSDI2012) ?