帮助理解MapReduce排序示例

Question

来自Google的纸描述MapReduce的5.3节。

“Map函数从文本行中提取一个10字节的排序键，并发出键和原始文本行作为中间键/值对。我们使用内置的标识函数作为约简操作符。该函数传递中间键/值对的值不变，作为输出键/值对。最后排序的输出被写入.”

我不明白实际的分类是怎么发生的。据我所知，Map函数提取一个键值对，然后约简函数以某种方式输出排序的数据。什么是“分类钥匙”？

Answer 1

排序取决于Google运行时的一些实现细节和附加功能。见第4.2节：

我们保证在给定的分区内，中间键/值对按递增键顺序处理。这种排序保证使每个分区生成一个排序的输出文件变得很容易，当输出文件格式需要支持高效的按键进行随机访问查找时，或者输出的用户发现对数据进行排序很方便时，这是非常有用的。

该系统还允许任意分区方案(在4.1节中提到)。分类系统使用此方案：

分区函数使用键的初始字节将其分隔为R片段之一。

因此，当在每个分区上运行simple函数时，对数据没有任何更改，但是可以保证输出的顺序是正确的(想必实现它没有什么特别之处-它只是一种简单的局部类型)。

一旦您有了已排序的分区，那么您所要做的就是按照用于创建分区的初始字节的顺序将它们连接起来，并且您有一个完全排序的列表。

(我把一个“排序键”作为设计值的摘要，这样，当键被排序时，值也会按照正确的排序顺序，至少在合理的近似下是这样的。简单地截断字符串的前几个字母就足以形成一个粗略的排序键)

Answer 2

请看一位教授的这段YouTube视频，他解释了MapReduce算法中涉及的概念。不幸的是，所有的代码都在Scheme中，所以可读性不是最好的，但是他很好地解释了所发生的事情。

基本上，MapReduce不仅仅是这两个步骤。事情是这样的：

• Map:对于每个输入，生成0、1或更多的键值对。
• 排序:将键值对收集起来，并按它们的键排序到一组桶中。
• 减少:每个桶与单个结果并行地减少。然后将每个桶的结果合并(减少)为最终结果。

排序步骤基本上就在那里，这样您就可以以分布式的并行方式运行减约操作，而不必连续地完成整个操作，这将要求整个减约任务由单个系统来处理，这就违背了目的。