3.4 二次排序
MapReduce在清洗(shuffle)和排序(sort)阶段用键来为中间键值对排序,如果reducer中的计算依赖于排序顺序的话就非常简单(即之前章节说到的顺序反转模式)。然而,如果除了用键排序之外,我们也需要用值来排序呢?Google的MapReduce实现提供了内置的二次排序的机制,它可以保证值是以排序顺序到达的。Hadoop,不幸的是没有内置这种机制。
(t1,m1, r80521)
(t1,m2, r14209)
(t1,m3, r76042)
…
(t2,m1, r21823)
(t2,m2, r66508)
(t2,m3, r98347)
考虑下一个科学实验的传感器的数据例子:有m个传感器每个都在不间断地读数,m有可能是个很大的数。一个传感器的导出数据是这样的,每一个时间戳后的rx代表着真实的传感器读数(在这次讨论中不重要,但可能是一系列的值,一个或多个复杂的记录,或者甚至是图片文件的字节流)。
假设我们想重新构建各个传感器的活性。MapReduce程序来完成这些,搜集原始数据,以传感器的id作为中间键,
m1 → (t1, r80521)
这样做可以使同一传感器的所有读数一起传到reducer中。然而,因为MapReduce并不保证同一键不同值的排序,传感器读数可能不按照预定的顺序排列。最容易想到的解决方案是在处理这些数据之前先缓存这些读数然后以时间戳来排序。然而,现在需要说的是任何在内存中缓存数据的做法都会带来潜在的伸缩性瓶颈。如果我们需要处理高读数频率的传感器或运行了很长时间的传感器呢?如果传感器的读数本身就是一个大并且复杂的对象呢?这个方法在这个案例中不适用---reducer有可能会因为缓存同一键的所有值而用完内存。
这是一个共同的问题,因为在很多应用程序中,我们希望首先使数据以某种条件(例如,通过传感器的id号)来分组,然后在分组的过程中通过另一种条件(例如,通过时间)排序。幸运的是,有一个普通的解决方案,我们称为“键值转换”(value-to-key conversion)模式。基本思想是把部分值和中间键组成一个混合键,让MapReduce来处理排序。在上面的例子中,我们将发送传感器的id和时间戳作为一个混合键而不是单单用传感器的id作为键:
(m1, t1) → (r80521)
现在传感器读数成为了值。我们必须定义中间键排序顺序来首先使用传感器id(pair的左元素)排序然后用时间戳(pair的右边元素)排序。我们也要实现一个自定的partitioner来让所有同一传感器的对传到同一个reducer中。
经过合适的排序后,键值对会以正确的顺序到达reducer中。
(m1, t1) → [(r80521)]
(m1, t2) → [(r21823)]
(m1, t3) → [(r146925)]
…
然而,现在传感器的读数被拆分到多个键上。Reducer就必须保存之前的状态和跟踪当前传感器的读数在那结束,下一个传感器在那开始。
上面讨论的两个方法(缓存和在内存中排序 vs. “键值转换”模式)的权衡是在那执行排序。一个可以直接在reducer中实现二次排序,这可能运行起来比较快但可能会遇到伸缩性瓶颈的问题10。在键值转换中,排序并不是基于MapReduce框架。要知道这个方法可以任意扩展到三次,四次或跟多的排序。使用这个模式的后果是产生更多的键来让MapReduce框架来排序,不过分布式排序是MapReduce擅长的,但是这种做法违背了Mapreduce编程模型的本质。
分享到:
相关推荐
马里兰大学教授新书,用Mapreduce 来处理大规模文本数据,非常值得一读
本书重点介绍MapReduce算法设计,重点介绍自然语言处理,信息检索和机器学习中常见的文本处理算法。
Data-Intensive+Text+Processing+with+MapReduce
书名 Data-Intensive[1].Text.Processing.With.MapReduce 用mapreduce处理海量文本数据(本人翻译) 本书的作者是:jimmy and chirs,2010 2月出版。 目录: 1 mapreduce basics 2 mapreduce algorithm desgin 3 ...
3 MapReduce Algorithm Design 3.1 Local Aggregation 3.1.1 Combiners and In-Mapper Combining 3.1.2 Algorithmic Correctness with Local Aggregation 3.2 Pairs and Stripes 3.3 Computing Relative ...
这本免费书籍重点介绍MapReduce算法设计,重点介绍自然语言处理,信息检索和机器学习中常见的文本处理算法。
设计数据敏感型应用,对多种存储组件进行分析,可以用于存储组件的技术选型,深入理解各种存储组件的优劣:Data-intensive applications are pushing the boundaries of what is possible by making use of these ...
Designing Data-Intensive Applications 英文原版 pdf
Data-intensive systems are a technological building block supporting Big Data and Data Science applications.This book familiarizes readers with core concepts that they should be aware of before ...
Designing Data-Intensive Applications 中文 epub 版本
1.Designing Data-Intensive Applications The Big Ideas Behind Reliable Scalable And Maintainable Systems 2017; 2.英文原版,PDF格式; 3.内容简介: If you develop applications that have some kind of server/...
This book examines the key principles, algorithms, and trade-offs of data systems, using the internals of various popular software packages and frameworks as examples. Tools at your disposal are ...
Designing Data-Intensive Applications-The Big Ideas Behind Reliable,Scalable and Maintainable Systems——大数据精选,要译本继续关注我
Designing Data-Intensive Applications pdf 英文版 NoSQL… Big Data… Scalability… CAP Theorem… Eventual Consistency… Sharding…
Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems Want to know how the best software engineers and architects structure their applications to ...
Designing.Data-Intensive.Applications.pdf 介绍大数据时代如何建设数据密集型应用以及最佳实践。
Mitigating GPU Memory Divergence for Data-Intensive Applications, A degree paper for PHD