MRI:面向并行迭代的MapReduce模型

机器学习领域内的多数模型均需要通过迭代计算以求解其最优参数,而MapReduce模型在迭代计算中的缺陷不足导致其在迭代计算中无法得到广泛应用。为解决上述矛盾,基于MapReduce模型提出并实现了一种可用于模型参数求解的并行迭代模型MRI。MRI模型在保持Map以及Reduce阶段的基础上,新增了Iterate阶段以及相关通信协议,实现了迭代过程中模型参数的更新、分发与迭代控制;通过对MapReduce状态机进行增强,实现了节点任务的重用,避免了迭代过程中节点任务重复创建、初始化以及回收带来的性能开销;在任务节点实现了数据缓存,保障了数据的本地性,并在Map节点增加了基于内存的块缓存机制,进一步提高训练集加载效率,以提高整体迭代效率。基于梯度下降算法的实验结果表明:MRI模型在并行迭代计算方面性能优于MapReduce模型。     

MapReduce:新型的分布式并行计算编程模型

MapReduce是Google提出的分布式并行计算编程模型,用于大规模数据的并行处理。Ma-pReduce模型受函数式编程语言的启发,将大规模数据处理作业拆分成若干个可独立运行的Map任务,分配到不同的机器上去执行,生成某种格式的中间文件,再由若干个Reduce任务合并这些中间文件获得最后的输出文件。用户在使用MapReduce模型进行大规模数据处理时,可以将主要精力放在如何编写Map和Reduce函数上,其它并行计算中的复杂问题诸如分布式文件系统、工作调度、容错、机器间通信等都交给MapReduce系统处理,在很大程度上降低了整个编程难度。MapReduce日益成为云计算平台的主流编程模型。Apache Hadoop项目提供开源的MapReduce系统还有待进一步完善。     

Hadoop环境下基于数据本地化的Reduce任务调度策略

在MapReduce模型任务处理过程中,当Reduce任务开始执行,远程拉取Map阶段的输出数据时,会消耗大量的网络带宽,甚至会出现网络瓶颈问题。本文提出基于数据本地化和负载均衡的任务分配策略。该策略中用户首先设置采样数据量M,在Map阶段对前M个数据块进行采样;其次根据采样结果,同时考虑数据本地化因素,将Reduce任务进行分配;然后基于负载均衡将Reduce任务进行再分配,通过任务分配,系统生成一个任务分配表;最后启动Reduce任务,系统开始数据拉取,未被采样的数据根据任务分配表进行任务分配。通过大量实验验证,基于数据本地化和负载均衡的任务分配策略,既能减少Shuffle阶段数据的传输量,又能降低网络带宽的消耗,同时可以避免出现某些节点空闲而其它节点任务量大甚至处理不了的情况,从而提高了集群处理数据的整体能力。      

基于多阶段划分的MapReduce模型

针对已有的MapReduce模型阶段划分粒度不合理导致模型精度和复杂度存在的问题,提出了阶段划分粒度为5的多阶段MapReduce模型(MR-Model)。首先综述了MapReduce模型的研究现状;然后将MapReduce划分为Read、Map、Shuffle、Reduce、Write共5个阶段,并对每个阶段的具体运行时间进行研究;最后通过实验对模型的预测性能进行验证。实验结果表明,提出的MR-Model可用来描述MapReduce实际任务的执行过程,与另外两种不同划分粒度的模型P-Model和H-Model相比,MR-Model模型的运行时间预测精度可以提高10%~30%,在Reduce阶段的运行时间预测精度可以提高2~3倍,综合性能较好。     

GCPR:一种在MapReduce平台上基于图划分的PageRank加速方法

随着应用的扩展,大规模图数据不断涌现,如何对拥有大量结点的图进行分析成为研究者关注的焦点问题之一.结点的海量性与分析的复杂性使得图分析任务需要借助MapReduce平台多机并行完成.在该平台上,现有的PageRank算法每轮迭代都须扫描、传输所有网页的完整状态,I/O和网络传输的开销严重影响了计算效率.为此,本文提出一种在MapReduce平台上基于图划分的PageRank加速方法:GCPR(Graph-clustering PageRank).GCPR利用图划分、数据两层压缩技术在MapReduce平台上进行PageRank迭代计算,不仅减少了Map到Reduce中间阶段I/O和网络传输的开销(MapReduce运算的主要瓶颈之一),而且平衡了计算资源.实验证明GCPR能极大提升MapReduce平台上的PageRank计算效率.     

基于Hadoop的MapReduce模型的研究与改进

针对MapReduce模型中存在的多个Reduce任务之间完成时间差别较大的问题,分析了影响Reduce任务完成时间的因素,指出了MapReduce模型中Reduce任务节点存在数据倾斜问题,提出了一种改进型的MapReduce模型MBR(Map-Balance-Reduce)模型。通过添加Balance任务,对Map任务处理完成的中间数据进行均衡操作,使得分配到Reduce任务节点的数据比较均衡,从而确保Reduce任务的完成时间基本一致。仿真实验结果表明,经过Balance任务后,Map任务产生的中间数据能够比较均衡的分配给Reduce任务节点,达到数据计算均衡的目的,在一定程度上减少了整个作业的执行时间。     

Hadoop平台中一种Reduce负载均衡贪心算法

MapReduce是目前广泛应用的并行计算框架,是Hadoop平台的重要组成部分。主要包括Map函数和Reduce函数。Map函数输出key-value键值对作为Reduce的输入,由于输入的动态性,不同主机上的Reduce处理的输入量存在不均衡性。如何解决Reduce的负载均衡是优化MapReduce的一个重要研究方向。本文首先对整体数据进行抽样,通过适量的样本分析数据,达到较小的代价获得可靠的key分布;然后,提出贪心算法代替Hadoop平台默认的hash算法来划分数据,实现Reduce负载均衡。本文所提贪心算法主要思想是根据抽样数据,求取所有key频次的和对于Reduce节点数量的平均值,然后依次为每一个Reduce分配一个接近平均值的负载,从而达到整体的负载均衡。模拟实验表明,本文所提算法与默认的hash分区算法相比,运行时间节约10.6%,达到更好的负载均衡。     

支持高并发数据流处理的MapReduce中间结果缓存

针对面向大规模历史数据的高并发数据流处理需求,为改进MapReduce的实时处理能力,提出了一种内存Hash B树、外存SSTable文件的key/value中间结果缓存,该结构具有可划分性、可扩展性和高效性.在此基础上,利用B树的平衡性特征提出了一种基于概率的B树构造算法和多路查询算法,利用读写开销估算和缓冲区信息改造了外存文件读写策略和内外存替换算法,进一步优化了中间结果的高并发读写性能.算法分析和实验证明了该缓存的有效性.     

恒速机上的MapReduce在线排序算法下界研究

本文研究源自于MapReduce模型系统的一类排序问题。给定两台恒速机和一批按列表到达的工件,每个工件包含两类任务:Map任务和Reduce任务。假设Map任务和Reduce任务都是不可中断的,Map任务可以并行处理,即可以任意分割成若干小的任务并在两台机器上同时处理,而Reduce任务只可以在单台机器上处理。一旦工件到达,必须为其指派机器和开工时间,目标是使得这批工件的最后完工时间最小。对|M_j|≥|R_j|的情形,我们证明了任意在线算法的竞争比不小于1+(1/(2s+2)).     

基于位图的键值存储哈希优化

内存键值存储系统中索引方法决定了系统的时间性能和空间开销,是改进和优化的关键因素。哈希索引提供了O（1）时间复杂度的访问操作,但会产生存储冲突,引起访问性能下降。为此,提出了一种基于位图的键值存储哈希优化方法,可以避免存储冲突提升访问性能。该方法将共前缀的键哈希到同一个块,减少键存储空间;在块内使用层次位图结构,全域位图表示所有键的后缀部分来避免存储冲突,摘要位图支持快速定位和范围查询加速。实验结果表明,优化后的哈希索引在多种负载上均能取得较高吞吐量并具有良好的并发性能,同时内存占用较现有方案大大降低。