基于压力反馈的MapReduce负载均衡策略

数据倾斜是严重影响MapReduce性能的因素之一.数据倾斜问题的现有解决方法需要用户对应用类型提供针对的分区函数,或是为MapReduce编写额外的采样过程,增加了用户的负担.为解决上述问题,提出了一种基于压力统计的负载均衡策略.该策略充分利用MapReduce中的混洗阶段,在reducer准备数据的同时进行统计,以获取全局数据分布.系统根据数据分布情况对负载较重节点进行调度,平衡整个集群负载,而无需用户提供额外的输入.此外,考虑到上层不同的应用类型,引入了压力反馈机制来进一步提高调度策略的性能.实验结果表明,提出的负载均衡调度策略的性能优于默认策略性能.     

基于MapReduce的数据倾斜连接算法

连接操作是大规模数据集在数据分析应用中最常用的操作,针对MapReduce自身不能有效地处理数据倾斜情况下的连接操作,提出了基于MapReduce的频次分类连接算法。根据数据在连接数据集中出现的频率将整个数据集分为3类,对倾斜数据利用分区算法和广播算法实现数据重分布,以消除数据倾斜的影响;对非倾斜数据采用Hash算法实现数据重分布。重分布后的数据在单节点内即可完成数据连接操作,避免了MapReduce框架下连接操作的跨节点传输代价;同时有效地均衡了MapReduce各节点的任务负载,从而提高了数据倾斜状态下连接操作的效率。通过与传统连接算法的对比,证明了所提算法的有效性和实用性。     

非均匀数据分布下的MapReduce连接查询算法优化

MapReduce分布式计算框架有助于提升大规模数据连接查询的效率,但当连接属性分布不均匀时,其简单的散列策略容易导致计算节点间负载不均衡,影响作业的整体性能。针对连接查询操作中的数据倾斜问题,研究了MapReduce框架下大规模数据连接查询操作的优化算法。首先对经典的改进重分区连接查询算法进行实验分析,研究了传统MapReduce计算框架下连接查询操作的执行流程,找出了基于MapReduce计算框架的连接查询算法在数据分布不均匀时的性能瓶颈;进而提出了组合分割平衡分区优化策略,设计并实现了基于组合分割平衡分区优化策略的改进型连接查询算法。实验结果表明,提出的优化策略在大规模数据的连接查询处理上很好地解决了数据倾斜带来的性能影响,具有好的时间性能和可扩展性。     

一种周期性MapReduce作业的负载均衡策略

MapReduce任务负载均衡主要是通过分区函数来实现的,Hadoop默认的分区函数并不能很好地保证reducer的负载均衡。针对周期性的业务处理提出了一种基于权重计算的负载均衡策略,周期性任务的数据分布与历史数据相比具有相似性。本策略根据历史数据运行的信息运算出数据权重信息(文中用权重表示每条记录的处理复杂 度),再通过Map阶段抽样分析当前这批数据的分布特征来预测待处理数据带权重的整体近似分布情况,从而指导Reduce分区,以保证其负载均衡。通过简单的例子仿真了整个策略的运作过程,并且对比了与TeraSor、思路的不同点。最后通过分析用户访问视频的日志证明了文中提到的策略比默认的策略性能提高了接近1倍。     

离散粒子群优化算法实现MapReduce负载平衡

MapReduce是Hadoop的核心模型之一,广泛应用于大数据处理。MapReduce模型将计算分为Map和Reduce两个处理阶段。但由于其自身的分区机制,导致在Reduce阶段处理数据时,会出现负载不平衡的数据倾斜问题。为了解决数据倾斜问题,提出利用离散粒子群算法解决Reduce阶段数据负载平衡问题。将数据分区策略与粒子群算法相结合,提高系统的稳定性。通过设置使数据分区均衡的目标函数,利用离散粒子群算法求解目标函数。试验结果证明,当设置不同数量的Reduce时,离散粒子群分区方式的运行时间均为最短,可有效解决数据分区的不平衡问题,并大大提升系统的计算效率。     

数据本地性感知的MapReduce负载均衡策略

现有针对MapReduce的负载均衡调度的研究均未考虑中间数据的分布特点及网络传输的开销,导致额外的网络传输代价与系统效率的下降。为解决上述问题,提出了一种数据本地性感知的负载均衡策略。充分利用YARN中资源管理的新特性,在Map阶段对内存数据溢写的同时进行统计以获取数据分布,根据数据分布情况及各节点的计算能力进行任务调度,减少网络传输开销的同时尽量保证各节点的负载平衡。此外,通过引入细粒度分区与分区的自适应分裂策略,进一步提高在数据倾斜时调度策略的性能。对比实验结果表明,提出的负载均衡调度策略能有效提升性能,同时较好地降低网络总开销。     

BHP：面向BSP模型的负载均衡Hash图数据划分

图数据划分是基于BsP（bulksynchronousparallel）编程模型的大规模图处理系统中一个关键技术问题。传统的图划分技术需要多次迭代,时间复杂度过高,且划分结果不具有图顶点到分区的映射信息,因此这些算法并不适用于BSP模型下的数据划分。提出了一种新的面向BSP模型的负载均衡Hash数据划分算法（balancedHashpartition,BHP）。为了实现各个分区的出边数尽可能均衡,该算法引入了虚拟桶的概念,通过贪婪算法将虚拟桶重组为实际分区,保证了每个实际分区负载均衡,同时数据本地化策略使本分片上的数据尽可能地保留在本节点上,从而减小在数据加载时的数据迁移开销。从三个方面对比了BHP算法和经典Hash算法的性能,结果表明BHP算法能够提高作业的执行效率,减少消息发送的数量,有效解决了经典Hash算法的负载不均衡和分区间交互边过多的问题,当数据量变大时,效果尤为明显。     

数据倾斜情况下基于MapReduce模型的连接算法研究

基于MapReduce的连接算法的研究是海量数据研究领域的一个重要内容,但都集中在数据分布均匀的情况下进行算法优化,而在实际应用中数据分布往往是不均匀的。本文基于此背景,提出一种适合在数据严重倾斜时使用基于MapReduce编程模型的连接算法Skew Control Join,算法通过采样获取数据集的整体分布,通过全局分区将数据集进行分割,使倾斜数据的处理平均分配到所有的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负载平衡方法.将聚类算法融合到MapReduce连接操作中,提出MapReduce并行聚类连接算法的实现方法;根据聚类结果动态调整抽样率的无偏分层图抽样算法,从而实现连接操作目标数据的准确、平衡抽样.通过合成数据集和真实数据集下的数据处理实验,与Hash连接算法及基于NS抽样的聚类算法进行对比,验证了所提出的算法方案在不同数据倾斜程度下都具有良好的负载平衡性能,其运行效率也没有因为新采样算法的采用而受到影响.     

Balancing reducer workload for skewed data using sampling-based partitioning

MapReduce has emerged as a popular tool for distributed processing of massive data. However, it is not efficient when handling skewed data and it often leads to reducer load imbalance. In this paper, we address the problem of how to efficiently partition intermediate keys to balance the workload of all reducers when processing skewed data. We present a sampling scheme to compute the approximate distribution of key frequency, estimate the overall distribution and then make a partition scheme in advance. Then, we apply it to map phase of the executing MapReduce job. This work not only provides a load-balanced partition strategy, but also keeps a high performance of synchronous mode of MapReduce. We also propose two partition methods based on sampling results: cluster combination and cluster split combination. The experimental results show that our methods achieve a better time and load balancing results.     

基于列存储的MapReduce分布式Hash连接算法

大数据具有规模大、深度大、宽度大、处理时间短、硬件系统普通化、软件系统开源化的特点。传统关系型数据库在对大数据进行操作时存在系统性能严重下降、计算效率提升有限以及可扩展性差等问题,因此引入MapReduce并行计算模型,提出一种大数据上基于列存储的MapReduce分布式Hash连接算法。首先,设计面向大数据的分布式计算模型,在设计的分片聚集并行连接的基础上,利用Hash连接以及动态探测方法优化了数据并行连接处理效率;然后,针对该算法开发了基于Hadoop的原型系统。通过实验证明,在大数据分析处理中,所提算法在执行时间和负载能力上都有很好的性能表现,也能提供良好的可扩展性。     

Fair multi-agent task allocation for large datasets analysis

MapReduce is a design pattern for processing large datasets distributed on a cluster. Its performances are linked to the data structure and the runtime environment. Indeed, data skew can yield an unfair task allocation, but even when the initial allocation produced by the partition function is well balanced, an unfair allocation can occur during the reduce phase due to the heterogeneous performance of nodes. For these reasons, we propose an adaptive multi-agent system. In our approach, the reducer agents interact during the job and the task reallocation is based on negotiation in order to decrease the workload of the most loaded reducer and so the runtime. In this paper, we propose and evaluate two negotiation strategies. Finally, we experiment our multi-agent system with real-world datasets over heterogeneous runtime environment.     

基于两阶分区的MapReduce实验室系统负载均衡研究

在实验室系统处理海量原始数据时,实际应用场景中存在采样率高、偏度（skewness）高的特殊情况,导致在使用两阶分区算法在平衡同构环境下的Reducer节点负载时,无法有效地处理这些问题。为此,引入MapReduce的并行化处理,可以提高实验室系统中采样数据利用率;同时,为了解决数据偏度和采样度高的问题,则采用了ICSC（Improved Cluster Split Combination）分区调度的算法。经过实验证明,基于两阶分区的MapReduce负载均衡算法能够有效减少Mapper和Reducer节点空转的时间。随着数据偏度的增加,算法的执行时长基本不产生变化,即数据偏度对该算法执行时间的影响较小。此外,数据采样度的增加,ICSC分区调度算法也保持着对比模型中最少的时间开销。因此,基于两阶分区的MapReduce负载均衡算法弱化了Reducer节点间的依赖性,并提升MapReduce任务的执行效率和容错率,从而高效地实现MapReduce框架下的实验室系统中数据处理的负载均衡。     

基于MapReduce和改进密度峰值的划分聚类算法

对于基于划分的聚类算法随机选取初始聚类中心导致初始中心敏感,聚类结果不稳定、集群效率低等问题,提出一种基于MapReduce框架和改进的密度峰值的划分聚类算法(based on MapReduce framework and im-proved density peak partition clustering algorithm,MR-IDPACA).首先,通过自然最近邻定义新的局部密度计算方式,将搜索样本密度峰值点作为划分聚类算法的初始聚类中心;其次针对算法在大规模数据下运行时间复杂,提出基于E2LSH(exact Euclidean locality sensitive hashing)的一种分区方法,即KLSH(K of locality sensitive hashing).通过该方法对数据分区后结合MapReduce框架并行搜寻初始聚类中心,有效减少了算法在搜索初始聚类中心时的运行时间;对于MapReduce框架中的数据倾斜问题,提出ME(multistage equilibrium)策略对中间数据进行多段均衡分区,以提升算法运行效率;在MapReduce框架下并行聚类,得到最终聚类结果.实验得出MR-IDPACA算法在单机环境下有着较高的准确率和较强的稳定性,集群性能上也有着较好的加速比和运行时间,聚类效果有所提升.     

MapReduce中连接负载均衡优化研究

数据分析和处理是大规模分布式数据处理应用中的重要任务。由于简单易用和具有灵活性, MapReduce编程模型逐渐成为大规模分布式数据处理系统（如Hadoop系统）的核心模型。由于所处理的数据可能不是均匀分布的,MapReduce编程模型在处理连接操作时,会出现数据倾斜问题。数据倾斜问题严重降低了MapReduce执行连接操作的效率。针对MapReduce中连接操作的数据倾斜问题,分析了造成MapReduce连接性能瓶颈的原因并建立负载均衡代价模型,提出了用范围分割方法控制连接过程中的数据倾斜问题实现负载均衡的策略。实验结果表明,所提方法明显提高了连接的效率。     

An improved partitioning mechanism for optimizing massive data analysis using MapReduce

In the era of Big Data, huge amounts of structured and unstructured data are being produced daily by a myriad of ubiquitous sources. Big Data is difficult to work with and requires massively parallel software running on a large number of computers. MapReduce is a recent programming model that simplifies writing distributed applications that handle Big Data. In order for MapReduce to work, it has to divide the workload among computers in a network. Consequently, the performance of MapReduce strongly depends on how evenly it distributes this workload. This can be a challenge, especially in the advent of data skew. In MapReduce, workload distribution depends on the algorithm that partitions the data. One way to avoid problems inherent from data skew is to use data sampling. How evenly the partitioner distributes the data depends on how large and representative the sample is and on how well the samples are analyzed by the partitioning mechanism. This paper proposes an improved partitioning algorithm that improves load balancing and memory consumption. This is done via an improved sampling algorithm and partitioner. To evaluate the proposed algorithm, its performance was compared against a state of the art partitioning mechanism employed by TeraSort. Experiments show that the proposed algorithm is faster, more memory efficient, and more accurate than the current implementation.