Skip to content

四火的唠叨

一个纯正程序员的啰嗦

Menu
  • 所有文章
  • About Me
  • 关于四火
  • 旅行映像
  • 独立游戏
  • 资源链接
Menu

Hadoop 的 Secondary Sorting

Posted on 06/04/201406/23/2019 by 四火

map-reduce 这几天项目中使用 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 链接)。

secondarySorting

这张图其实已经可以说明,把 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 放满时提交一次即可。

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

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

×Scan to share with WeChat

你可能也喜欢看:

  1. Notes: Hadoop-based open source projects
  2. 给我一把榔头,满世界都是钉子
  3. 不适合 Hadoop 解决的问题
  4. Hadoop 的 Map-side join 和 Reduce-side join
  5. 排序算法一览(上):交换类、选择类和插入类排序

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

订阅·联系

四火,啰嗦的程序员一枚,现居西雅图

Amazon Google Groovy Hadoop Haskell Java JavaScript LeetCode Oracle Python Spark 互联网 前端 华为 历史 同步 团队 图解笔记 基础设施 工作 工作流 工具 工程师 应用系统 异步 微博 思考 技术 数据库 曼联 测试 生活 程序员 管理 系统设计 缓存 编码 编程范型 英语 西雅图 设计 评审 问题 面试 项目

分类

  • Algorithm and Data Structure (30)
  • Concurrency and Asynchronization (6)
  • System Architecture and Design (43)
  • Distributed System (18)
  • Tools Frameworks and Libs (13)
  • Storage and Data Access (8)
  • Front-end Development (33)
  • Programming Languages and Paradigms (55)
  • Testing and Quality Assurance (4)
  • Network and Communication (6)
  • Authentication and Authorization (6)
  • Automation and Operation Excellence (13)
  • Big Data and Machine Learning (5)
  • Product Design (7)
  • Hiring and Interviews (14)
  • Project and Team Management (14)
  • Engineering Culture (17)
  • Critical Thinking (25)
  • Career Growth (57)
  • Life Experience and Thoughts (45)

推荐文章

  • 谈谈分布式锁
  • 常见分布式系统设计图解(汇总)
  • 系统设计中的快速估算技巧
  • 从链表存在环的问题说起
  • 技术面试中,什么样的问题才是好问题?
  • 从物理时钟到逻辑时钟
  • 近期面试观摩的一些思考
  • RSA 背后的算法
  • 谈谈 Ops(汇总 + 最终篇):工具和实践
  • 不要让业务牵着鼻子走
  • 倔强的程序员
  • 谈谈微信的信息流
  • 评审的艺术——谈谈现实中的代码评审
  • Blog 安全问题小记
  • 求第 K 个数的问题
  • 一些前端框架的比较(下)——Ember.js 和 React
  • 一些前端框架的比较(上)——GWT、AngularJS 和 Backbone.js
  • 工作流系统的设计
  • Spark 的性能调优
  • “残酷” 的事实
  • 七年工作,几个故事
  • 从 Java 和 JavaScript 来学习 Haskell 和 Groovy(汇总)
  • 一道随机数题目的求解
  • 层次
  • Dynamo 的实现技术和去中心化
  • 也谈谈全栈工程师
  • 多重继承的演变
  • 编程范型:工具的选择
  • GWT 初体验
  • java.util.concurrent 并发包诸类概览
  • 从 DCL 的对象安全发布谈起
  • 不同团队的困惑
  • 不适合 Hadoop 解决的问题
  • 留心那些潜在的系统设计问题
  • 再谈大楼扔鸡蛋的问题
  • 几种华丽无比的开发方式
  • 我眼中的工程师文化
  • 观点的碰撞
  • 谈谈盗版软件问题
  • 对几个软件开发传统观点的质疑和反驳
  • MVC 框架的映射和解耦
  • 编程的未来
  • DAO 的演进
  • 致那些自嘲码农的苦逼程序员
  • Java 多线程发展简史
  • 珍爱生命,远离微博
  • 网站性能优化的三重境界
  • OSCache 框架源码解析
  • “ 你不适合做程序员”
  • 画圆画方的故事

近期评论

  • + 1.943624 BTC.NEXT - https://graph.org/Ticket--58146-05-02?hs=9a9c6f8dfe3cdbe0074006e3e640b19b& on 所有文章
  • Anonymous on 闲聊投资:亲自体验和护城河
  • 四火 on 关于近期求职的近况和思考
  • YC on 关于近期求职的近况和思考
  • mafulong on 常见分布式基础设施系统设计图解(四):分布式工作流系统
  • 四火 on 常见分布式基础设施系统设计图解(八):分布式键值存储系统
  • Anonymous on 我裸辞了
  • https://umlcn.com on 资源链接
  • Anonymous on 我裸辞了
  • Dylan on 我裸辞了
© 2025 四火的唠叨 | Powered by Minimalist Blog WordPress Theme