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

hadoop shuffle机制中针对中间数据的排序过程详解(源代码级)---转载

 
阅读更多

转载--http://blog.csdn.net/riverm/article/details/6883606

 

在所有公开资料中,很少有对Hadoop 中间数据的sort过程进行详细介绍的。如果想要深入了解hadoop对中间数据的排序机制,只有通过阅读源代码才能达到。而hadoop的这段代码本身具有非常大的迷惑性,如果不注意细节,很容易会发生错误的理解。 本篇文章从原理上详细介绍了hadoop针对中间数据的排序机制,并且对一些重要的源代码段进行了介绍。阅读本文对理解该机制或者深入阅读该部分的hadoop源代码都有较大帮助。

      本篇文章是建立在对于hadoop0.20.2版本的源代码研究之上。其他更高级版本如果有所变动,希望读者能够给予反馈。

      如果对hadoop的shuffle机制有所了解的人都知道,map所产生的中间数据在送给reduce进行处理之前是要经过排序的。具体的过程实际上是快速排序,堆排序和归并排序的完美结合。

      首先,当map函数处理完输入数据之后,会将中间数据存在本机的一个或者几个文件当中,并且针对这些文件内部的记录进行一次快速排序,这里的排序是升序排序。这段代码是在MapTask的内部类MapOutputBuffer中实现的。

      当map阶段完成后,系统会启动reduce过程。reduce过程会把这些由map输出的中间文件拷贝到本地,然后生成一个或者几个Segment类的实例,以下我们称这些实例为segment。Segment类封装了这些中间数据,并且提供了一些针对这些中间数据的操作,比如读取记录等。在reduce端,这些中间数据可以存在内存中,也可以存在硬盘中。同时,系统还会启动两个merge(归并)线程,一个是针对内存中的segment进行归并,一个是针对硬盘中的segment进行归并。merge过程实际上就是调用了Merge类的merge方法。

     Merge类的merge方法生成了一个MergeQueue类的实例,并且调用了该类的merge方法。MergeQueue类是PriorityQueue类的一个子类,同时实现了RawKeyValueIterator接口。PriorityQueue类实际上是一个小根堆,而MergeQueue的merge方法实际上就是将segment对象存储进父类的数据结构中,并且建立一个小根堆的过程。因此,hadoop的归并和排序不是两个分开的过程,而是一个过程。在将segment归并的同时进行了排序。

     需要注意的是,这里针对segment排序的过程是以segment为单位的,而不是以segment中存储的记录(record)为单位的。而这里排序过程中对两个segment对象的比较是对segment中存储的第一个记录的键的比较。也就是说假设有两个segment,一个叫a,一个叫b,a<b仅仅是因为a的第一个记录的键小于b的第一个记录的键。具体的比较方法由用户定义的comparator类定义的。具体的比较过程在MergeQueue类中的lessThan方法中定义。

      现在,我们已经得到了一个以segment为单位,以segment中第一个记录的键为比较依据的小根堆,至此在系统中所谓的sort阶段就已经结束了

      接下来,系统会不停的从这个小根堆里取出位于根节点的segment的第一个记录交给reduce函数处理。注意,因为该小根堆是以每一个segment的第一个记录的键为排序依据的,所以根节点的第一个记录的键一定是所有segment中第一个记录的键的最小值。由于segment存储的是map输出的数据,而这些数据在传送给reduce之前已经经过排序(升序),所以,每个segment的第一个记录的键一定是该segment中所有键的最小值。从而根segment的第一个记录的键一定是所有记录的键的最小值。这里实际就是利用了归并排序。在从根segment中取出第一个记录之后,系统还会对该小根堆进行调整,以保证小根堆的性质。

      以上是shuffle过程中排序的完整过程。虽然在hadoop的shuffle过程中有一个明确的sort阶段,但是实际上可以看出中间数据的排序是贯穿于整个shuffle阶段的。

分享到:
评论

相关推荐

    深入云计算:Hadoop应用开发实战详解 源代码

    5. **实战详解与源代码**:"深入云计算:Hadoop应用开发实战详解 源代码"可能包含了作者对Hadoop在实际项目中的应用案例,包括数据预处理、数据清洗、数据分析等环节的详细步骤和源代码。通过阅读这些源代码,开发者...

    hadoop源代码存档

    【Hadoop源代码存档详解】 Hadoop是Apache软件基金会的一个开源项目,它是一个分布式文件系统,旨在提高数据处理和存储的效率。这个"hadopp源代码存档"包含了Hadoop项目的完整源代码,供开发者深入理解其内部机制,...

    hadoop应用开发技术详解代码

    本书“Hadoop应用开发技术详解”的源代码涵盖了第3、4、5、7、8、10、11和12章的内容,为读者提供了丰富的实践示例,帮助理解并应用Hadoop生态系统中的关键组件。以下是对这些章节涉及知识点的详细解释: 1. **...

    hadoop权威指南源代码

    7. **Hadoop容错机制**:数据副本的检查、故障检测及恢复、JobTracker和TaskTracker的容错等机制,都在源代码中有体现,这些是保证Hadoop集群稳定运行的关键。 8. **Hadoop生态系统**:除了核心组件,Hadoop还包括...

    006_hadoop中MapReduce详解_3

    在Hadoop生态系统中,MapReduce是一种分布式计算框架,主要用于...通过阅读`TestMR.java`和`WordCount.java`的源代码,我们可以深入理解MapReduce的编程模型和实现机制,这对于理解和应用Hadoop大数据处理至关重要。

    Hadoop源代码分析(类TaskStatus)

    通过对Hadoop源代码中`TaskStatus`类的详细解析,我们可以看到,该类在MapReduce任务执行过程中扮演着极其重要的角色。它不仅提供了丰富的状态信息,还为任务的监控和故障排查提供了必要的支持。此外,通过了解`...

    hadoop-common-2.6.0-bin-master.zip.rar

    同时,了解Hadoop的源代码和API文档将对深入理解Driver的工作原理大有裨益。 总的来说,Hadoop Common 2.6.0版本为MapReduce Driver测试提供了坚实的基础。通过细致的测试,我们可以确保在大数据处理过程中,Driver...

    Hadoop从入门到上手企业开发

    060 MapReduce执行流程之Shuffle和排序流程以及Map端分析 061 MapReduce执行流程之Reduce端分析 062 MapReduce Shuffle过程讲解和Map Shuffle Phase讲解 063 Reduce Shuffle Phase讲解 064 源代码跟踪查看Map Task和...

    Hadoop源代码分析(MapReduce概论)

    本文通过对Hadoop MapReduce的核心原理及其源代码的分析,帮助读者深入理解MapReduce的工作机制。 #### 二、Hadoop MapReduce概述 Hadoop MapReduce是一种分布式计算模型,用于处理和生成大型数据集。它将大规模...

    hadoop-3.3.6-src.tar.gz

    `hadoop-3.3.6-src.tar.gz`是一个源代码压缩包,包含了Hadoop项目在版本3.3.6中的所有源代码。这个版本可能包含了一些性能优化、新功能的添加以及对之前版本中bug的修复。 一、Hadoop架构概述 Hadoop由两个主要组件...

    005_hadoop中MapReduce详解_2

    在Hadoop生态系统中,MapReduce是一种分布式计算框架,它允许我们处理海量数据并行化,非常适合大规模数据集的处理。本文将深入解析MapReduce的工作原理、核心组件以及如何编写一个基本的MapReduce程序。 MapReduce...

    《Hadoop权威指南(第四版)》中-英文pdf+源码

    6. **源代码分析**:配合提供的源代码,读者可以更直观地理解书中的示例和概念,加深对Hadoop核心功能的理解。 英文PDF(805页)则为原版书籍,内容与中文版大体一致,对于英语阅读能力较强的读者,可以获取更准确...

    实战Hadoop源码--刘鹏

    《实战Hadoop源码》是刘鹏先生撰写的一本深入解析Hadoop的专著,针对对云计算技术感兴趣的读者,特别是那些希望通过源代码学习Hadoop内在机制的开发者。这本书旨在帮助读者理解Hadoop如何实现分布式计算,以及如何在...

    Hadoop开发

    - **Hadoop源代码Eclipse编译教程**:首先需要安装Eclipse IDE,然后配置Eclipse的插件以支持Hadoop开发,接下来下载Hadoop源代码,设置编译路径和依赖库等。 - **在Windows上使用Eclipse编写Hadoop应用程序**:通过...

    hadoop-2.7.7.zip

    这里的“hadoop-2.7.7.zip”是一个包含了Hadoop 2.7.7版本的所有源代码、编译后的库文件、配置文件以及文档的压缩包。这个版本的Hadoop在大数据处理领域被广泛应用,因为它提供了高效、可扩展的数据存储和处理能力。...

    Hadoop开发者入门专刊.pdf

    编译Hadoop源代码的过程主要包括以下几个步骤: 1. **下载Hadoop源代码**:首先需要从Apache官网下载最新的Hadoop源代码。 2. **配置开发环境**:确保已经安装了Java JDK,并正确配置了环境变量。 3. **导入项目到...

    非常好的hadoop入门资料

    这个过程中涉及到排序、合并、分区等操作,是理解MapReduce内部机制的重要部分。 - **Hadoop性能调优**:随着Hadoop集群规模的扩大,性能问题逐渐显现。通过调整Hadoop配置参数、优化数据分布等方式可以有效提高系统...

    Hadoop开发者第一期

    - **Shuffle过程**:Map阶段和Reduce阶段之间的数据传输过程被称为Shuffle过程,它涉及数据排序、分区和合并等操作,是MapReduce中性能优化的关键点之一。 #### 国内应用情况 在中国,Hadoop技术已经被广泛应用于...

Global site tag (gtag.js) - Google Analytics