Hadoop的Secondary Sorting

标签: Distributed System Hadoop MapReduce Secondary Sorting 排序 | 发表时间:2014-06-04 23:31 | 作者:四火
出处:http://www.raychase.net

Hadoop的Secondary Sorting 这几天项目中使用Hadoop遇到一个问题,对于这样key-value的数据集合:id-biz object,对id进行partition(比如根据某特定的hash算法P),分为a份;使用数量为b的reducer,在reducer里面要使用第三方组件进行批量上传;上传成文件,文件数量为c,但是有两个要求:

  • 上述a、b、c都相等,从而使得每个partition的数据最终都通过同一个reducer上传到同一个文件中去;
  • 每个reducer中上传的数据要求id必须有序。

最开始,想到的办法是,为了保证reducer中的批量上传,需要使得传入reducer的key变成一个经过hash算法A计算得到的index,这样就使得reducer中的value是一个包含了数个biz boject的集合的iterator,从而实现在一次reducer调用中批量上传并且提交。在批量上传提交的过程中,按照每上限个(例如1000个)文件提交一次的办法进行,以保证内存占用控制在一定范围内。

如何保证有序?

Hadoop在Reduce之前会自动对key排序,但是上述的情况实际是要根据id来给value排序(因为在map之后key已经变成index了),凡是涉及到要给value排序的,都要使用Hadoop的Secondary Sorting(见 stackoverflow链接)。

Hadoop的Secondary Sorting

这张图其实已经可以说明,把value要排序的关键属性放到key里面去,这样key就变成了natural key(上述的index)和secondary key(上述的id)这样两部分组成的一个composite key。

1. Partition:Partition的时候仅使用natural key,保证所有index的数据都分在同一个partition;

JobConf.setPartitionClass(...);

2. Sort:真正给key排序的比较算法要对natural key和secondary key两部分进行排序,从而保证了key在id维度上是有序的,而id和value是一一对应的,因此value也就是有序的。

JobConf.setOutputKeyComparatorClass(...);

3. Group:grouping的比较算法忽略掉secondary key,只对natural keygrouping,使得属于同一index的数据都走到同一个reducer中去。

JobConf.setOutputValueGroupingComparatorClass(...);

总结一下,这样一来,在reducer中,input key是上述这样一个composite key对象,包含了index和id,input value是一个可以遍历的元素为原始biz object类型的对象。

后话:这是Secondary Sorting的过程,可以解决我的问题,但是后来发现,实际上,我的问题并不需要要用这样啰嗦的方式来解决:

  • 进入reducer的key只需要是id,Hadoop会对key自动排序;
  • partition策略不变,但是是在partitioner中计算index并根据它来partition;
  • 不需要单独指定Grouping和Sorting的算法;
  • 在reducer中建立一个大小为上限(如1000个)的容器对象p。

这样,既然对于每个partition的数据,都在同一个reducer中得到处理,而reducer中每次reduce方法彼此之间是根据id有序进行,那么就可以在每次调用时把数据放到p中,在p放满时提交一次即可。

测试通过。回头看看,真是刚开始的时候把问题想复杂了。

 

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

分享到:
你可能也喜欢:

相关 [hadoop secondary sorting] 推荐:

Hadoop的Secondary Sorting

- - 四火的唠叨
这几天项目中使用Hadoop遇到一个问题,对于这样key-value的数据集合:id-biz object,对id进行partition(比如根据某特定的hash算法P),分为a份;使用数量为b的reducer,在reducer里面要使用第三方组件进行批量上传;上传成文件,文件数量为c,但是有两个要求:.

浅析Hadoop Secondary NameNode,CheckPoint Node,Backup Node

- - CSDN博客云计算推荐文章
Hadoop SecondaryNameNode并不是Hadoop 第二个NameNode,它不提供NameNode服务,而仅仅是NameNode的一个工具. 这个工具帮助NameNode管理Metadata数据. NameNode的HDFS文件信息(即Metadata)记录在内存中,client的文件写操作直接修改内存中的Metadata,同时也会记录到硬盘的Edits文件,这是一个Log文件.

Hadoop二次排序关键点和出现时机(也叫辅助排序、Secondary Sort)

- - The Big Data Way,平凡但不乏味
    Hadoop二次排序在面试的时候出现频率还是比较高的. 今天花了点时间通过源码深入学习了一下. 后面内容以Hadoop自带实例——SecondarySort讲解.     它的作用是决定数据分区,说白了就是决定map输出key-value由哪个reduce处理,每个map task输出的key-value都会执行Partitioner的getPartition()方法,用于返回当前key-value由哪个reduce处理.

华为HBase二级索引(Secondary Index)细节分析

- - 数据库 - ITeye博客
华为在HBTC 2012上由其高级技术经理Anoop Sam John透露了其 二级索引方案,这在业界引起极大的反响,甚至有人认为,如果华为早点公布这个方案,hbase的某些问题早就解决了. 其核心思想是保证索引表和主表在同一个region server上. 目前该方案华为已经开源,详见: https://github.com/Huawei-Hadoop/hindex.

Phoenix二级索引(Secondary Indexing)的使用 - MOBIN - 博客园

- -
HBase只提供了一个基于字典排序的主键索引,在查询中你只能通过行键查询或扫描全表来获取数据,使用Phoenix提供的二级索引,可以避免在查询数据时全表扫描,提高查过性能,提升查询效率. 数据格式:(数据来自 搜狗实验室). 三节点集群(一主两从,hadoop和HBase属同一集群). Covered Indexes(覆盖索引).

Hadoop Streaming 编程

- - 学着站在巨人的肩膀上
Hadoop Streaming是Hadoop提供的一个编程工具,它允许用户使用任何可执行文件或者脚本文件作为Mapper和Reducer,例如:. 采用shell脚本语言中的一些命令作为mapper和reducer(cat作为mapper,wc作为reducer). 本文安排如下,第二节介绍Hadoop Streaming的原理,第三节介绍Hadoop Streaming的使用方法,第四节介绍Hadoop Streaming的程序编写方法,在这一节中,用C++、C、shell脚本 和python实现了WordCount作业,第五节总结了常见的问题.

Hadoop使用(一)

- Pei - 博客园-首页原创精华区
Hadoop使用主/从(Master/Slave)架构,主要角色有NameNode,DataNode,secondary NameNode,JobTracker,TaskTracker组成. 其中NameNode,secondary NameNode,JobTracker运行在Master节点上,DataNode和TaskTracker运行在Slave节点上.

Hadoop MapReduce技巧

- - 简单文本
我在使用Hadoop编写MapReduce程序时,遇到了一些问题,通过在Google上查询资料,并结合自己对Hadoop的理解,逐一解决了这些问题. Hadoop对MapReduce中Key与Value的类型是有要求的,简单说来,这些类型必须支持Hadoop的序列化. 为了提高序列化的性能,Hadoop还为Java中常见的基本类型提供了相应地支持序列化的类型,如IntWritable,LongWritable,并为String类型提供了Text类型.

Hadoop TaskScheduler浅析

- - kouu's home
TaskScheduler,顾名思义,就是MapReduce中的任务调度器. 在MapReduce中,JobTracker接收JobClient提交的Job,将它们按InputFormat的划分以及其他相关配置,生成若干个Map和Reduce任务. 然后,当一个TaskTracker通过心跳告知JobTracker自己还有空闲的任务Slot时,JobTracker就会向其分派任务.

HADOOP安装

- - OracleDBA Blog---三少个人自留地
最近有时间看看hadoop的一些东西,而且在测试的环境上做了一些搭建的工作. 首先,安装前需要做一些准备工作. 使用一台pcserver作为测试服务器,同时使用Oracle VM VirtualBox来作为虚拟机的服务器. 新建了三个虚拟机以后,安装linux,我安装的linux的版本是redhat linux 5.4 x64版本.