`
samuschen
  • 浏览: 405494 次
  • 性别: Icon_minigender_2
  • 来自: 北京
社区版块
存档分类
最新评论

混洗和排序

阅读更多


在mapreduce过程中,map输出的结果默认是按照key进行排序的,这个排序的过程加上与将map的输出结果传送到reducer作为输入的过程统称为混洗。理解混洗的过程对于理解整个hadoop很有帮助,书中也提到混洗就是hadoop发挥它威力的地方。

1. map side:
map函数执行后会不断的产生结果,这些结果不是简单的写入磁盘的。每个map任务都有一个循环队列,map输出结果首先会存放在队列中,当队列 中存放的内容超过一个门限值的时候(通过io.sort.spill.percent设置,默认为0.8, 80%),一个后台线程将队列中的内容写到磁盘中,此时map结果的写入到队列的过程并没有停止,当队列慢了以后,map现成会被阻塞直到队列中所有的数 据都写入到磁盘。

在队列的内容被写入磁盘之前,线程首先将数据进行分组,分组的自然是按照最终会传送到哪个reducer进行。对于每个组,线程会对组中的数据按key排序,如果声明了combiner函数,在此时调用,然后将结果写入到一个文件中。

每次队列达到门限值的时候,都会产生一个这样的文件,文件达到一定数目或map任务要结束的时候,这些文件会merge成一个已经分组的有序的文 件,如果声明了combiner函数,并且至少有三个这样的中间文件进行merge,就会调用此combiner。最终将这个已分区的有序的文件写入磁盘 中。

2. reduce side:
在reduce side,混洗分为三个阶段:拷贝阶段、排序(归并)阶段、reduce阶段
reduce task默认有5个线程来拷贝已完成的map任务的相应分区。当map任务完成并将最终的那个文件写入到磁盘后,拷贝就会开始,reduce task不会等所有的map task都完成,而是有map task完成后,拷贝阶段就开始。reduce task将map task的结果通过http协议传送到队列中,当超过队列规定的容量或者已经获得从map task结果的数目达到门限值,就开始将这些数据写入磁盘中。

当所有的map task的结果都拷贝结束后,reduce task进入排序(归并)阶段,这个阶段会按照设置的归并因子来进行归并,比如有50个map结果,归并因子是10,则会归并5次,每次将10个文件归并为一个文件。

进行一次归并后,便进入到reduce阶段,将上阶段生成的多个文件作为reduce的输入,进行reduce操作,获得的结果进行最后一个归并,得到最终结果并将结果写入到HDFS中。

至此整个mapreduce的执行过程结束了,整个过程书上的图描述的很清楚:


我们可以优化混洗的过程来优化整个job的性能。在map side,我们应该尽量避免map的结果不断的写入到磁盘,可以提高io.sort.mb来增加循环队列的容量;在reduce side,应尽量保证中间数据都在内存中,我们可以设置接受map结果的门限值为0和设置缓冲区溢出百分比为100%来获得最佳性能。

分享到:
评论

相关推荐

    栈混洗——火车进站出站的可能次序

    栈混洗,也被称为栈排序或栈操作序列,是一种基于栈的数据结构操作序列问题,它涉及到如何通过一系列的入栈和出栈操作,使得最终出栈的元素序列满足特定的顺序要求。在这个特定的场景中,火车进站出站的过程可以被视...

    【图像分割】基于混洗Shuffled Complex Evolution实现图像分割附matlab代码.zip

    混洗复杂演化算法是一种优化算法,源自混沌搜索理论,它结合了复数算子和进化策略,旨在解决复杂的全局优化问题。在图像分割场景中,SCE算法可以用于寻找最佳阈值分割策略,以区分图像中的不同对象或区域。具体来说...

    反-逆混洗光电混合循环排序网

    排序网的互连级采用自由空间光学反-逆混洗(Comega)互连, 比较交换节点列阵采用硅互补金属-氧化物-半导体-自由光效应器件(CMOS-SEED)光电混合集成电路来实现。 由于反-逆混洗多级网络各互连级完全相同, 该排序网络...

    matlab_混洗复杂进化图像分割

    6. **SortPopulation.m** - 这个函数负责根据某种适应度函数对种群进行排序,以确定下一代的个体。 7. **IsInRange.m** - 这个函数可能检查某个值是否在特定范围内,确保算法过程中的参数约束。 8. **ts.jpg** - 一...

    具有块混洗和混沌映射的高效图像加密

    - 阿诺德变换(Arnold Transform):一种常用于图像处理中的变换方法,能够实现图像像素的重新排序,常用于图像扰乱和加密。 - 块混洗(Block Shuffling):一种图像加密技术,通过改变图像中像素块的顺序来打乱图像...

    数据结构往年考试题1

    以上内容涵盖了数据结构中的查找算法(如Fibonacci查找、二分查找)、排序算法(插入排序)、时间复杂度分析、栈的应用、以及动态规划和分治策略等核心概念。这些知识点在数据结构的学习和实际编程中都是非常重要的...

    数据结构-2011-期中-解析1

    3. **排序算法**:包括选择排序(P255)、插入排序(P270)和归并排序(P277)。选择排序每次选择最小(或最大)的元素放到正确的位置,时间复杂度为O(N^2)。插入排序将元素逐个插入到已排序的序列中,时间复杂度也...

    数据结构-2011-期中1

    无论是有序向量还是有序列表,最坏情况下的查找可以在O(log n)时间内完成,这是针对二分查找的特性来说的,而对于基于比较的排序算法,第七题提到的至少需要O(n log n)的时间,这是排序算法的下界,如快速排序和归并...

    C++实现洗牌发牌排序功能的示例代码

    C++实现洗牌发牌排序功能的示例代码 本篇文章主要介绍了C++实现洗牌发牌排序功能的示例代码,展示了如何使用C++...该示例代码展示了如何使用C++语言来实现洗牌发牌排序功能,包括构建一副牌、洗牌、发牌和排序等步骤。

    全混洗互连网络中RPS、LPS和IPS的矩阵处理 (2005年)

    例如,可以通过连续应用左混洗和右混洗操作实现逆混洗的效果。具体的转换公式可以通过矩阵运算来表达,如矩阵乘法、加法等。 #### 完善理论分析 本文还讨论了左混洗、右混洗及其逆混洗之间的相互转换关系,并提出了...

    ggnn.tensorflow:选通图神经网络的Tensorflow实现用于源代码分类-tensorflow source code

    存储桶:将具有相似大小的批处理图放在一起,而不是随机混洗和批处理。 对于小图,请使用密集图表示;对于大图,请使用稀疏图表示。 我们根据的论文的详细信息,将文件解析为图形表示形式。 有关为方法名称预测...

    2011数据结构期中考试题无答案版.docx

    - **定义与应用**: 所有的基于比较的排序算法(如快速排序、归并排序等)在最坏情况下都需要\(O(nlogn)\)的时间来完成排序任务。 - **时间复杂度**: 即使对于有序数组,基于比较的排序算法仍然需要\(O(nlogn)\)的...

    数据结构-2010-1-期中1

    - 插入排序的平均和最好情况时间复杂度是O(n^2),但若借助二分查找确定插入位置,时间复杂度可以降低到O(n log n)。 - 对于有序向量或列表,二分查找可以在O(log n)时间内完成查找,但最坏情况并不总是这样,例如...

    2011数据结构期中考试题_解析.docx

    1. **栈混洗方案**:这个问题涉及栈的操作及其输出顺序。根据题目描述,字符序列的输出保持原样,需要考虑不同的入栈和出栈组合方式。 2. **数学推理**:这类题目通常涉及数学证明的基本方法,如代数变换、等价...

    ArrayV-v4.0:https的新家

    改进了w0rthy的Array Visualizer 超过75种排序算法,具有12种独特的图形设计 该程序的新版本的功能受到Timo Bingmann的“分类...新的混洗类型,包括反转的,几乎相似的数字,几乎已排序且已排序 跳过排序按钮 声音柔

    SortingNetworks:适用于小整数数组(2-6个元素)的最快的CPU SIMD(SSE4)分拣网络,还具有最佳的amd64汇编,并提供了有关使编译器生成最佳分拣网络的说明

    简介:作为示例,我使用SSE4提出了新颖且先进的4 int32_t排序和6 int8_t排序,以及一些有关对小型固定大小数组进行快速排序的想法和注释。 这些是现代CPU上最快的已知方法。 它们是完全无分支的并且非常快。 例如,...

    Hadoop平台技术 模块3 分布式计算框架MapReduce-单元设计.docx

    其核心理念是将复杂的并行计算任务分解为两个主要阶段:Map(映射)和Reduce(规约),同时引入Shuffle(混洗)作为中间数据处理环节。 1. **Map阶段**:在Map阶段,输入数据被分割成多个块,每个块由一个Map任务...

    JavaCardDeck:编码分配

    通过数组内部的置换实现混洗。 3)。 使用 Collections 排序方法排序(懒惰)。 4)。 实现了 Card Deck 快速排序方法来对洗牌后的数组进行排序。 5)。 已实现从洗牌的牌库中获取所有同花色的牌。 6). 6 Junit ...

Global site tag (gtag.js) - Google Analytics