sorting - 我们真的需要在 MapReduce 框架中进行排序吗？

Question

我是 MapReduce 的新手，只是无法理解根据每个分区中的键对映射器输出进行排序的需要。最终我们想要的只是一个 reducer 被提供一个由几对 <key,List of Values> 组成的分区。并且每一对中的键不仅对于相应的分区是唯一的，而且对于馈送到不同 reducer 的所有分区也是唯一的。

为此需要做 sort在任何阶段。我们不能使用 hash table 吗？将对应于同一键的值分组？

将其分解为每个阶段。在映射器阶段，对于每个输出对，我们简单地散列键以找到分区号，然后我们将相应的对附加到属于同一分区的所有此类对的链表中。所以最后，单个映射器获得的输出将是 hashtable .其中对于每个分区号，我们都有一个链表 <key,value>没有基于键的顺序配对，即没有相似键值的位置。

然后来自不同 mapper 任务的分区被洗牌到一个 reducer。我们现在需要确保我们首先将对应于同一键的所有值分组(一种合并)，然后提供那些合并的 <key,List of Values> 对。到一个单独的 reducer 函数。在这里我们可以再次使用 hashtable为此，我们只需遍历所有分区，并将每个键映射到哈希表中的索引，并将相应的值附加到哈希表中的链表。 与我们对每个映射器的输出进行排序的方法相比，这种方法不会节省更多时间吗？

我已经完成了 link (我目前无法对该线程发表评论，所以我写了一个单独的问题。)最上面的答案提到了

Sorting saves time for the reducer, helping it easily distinguish when a new reduce task should start. It simply starts a new reduce task, when the next key in the sorted input data is different than the previous, to put it simply. Each reduce task takes a list of key-value pairs, but it has to call the reduce() method which takes a key-list(value) input, so it has to group values by key. It's easy to do so, if input data is pre-sorted (locally) in the map phase and simply merge-sorted in the reduce phase (since the reducers get data from many mappers)

但是我们还是可以通过使用哈希表来做同样的事情，或者我们不能吗？

Answer 1

嗯，是的，只要所有内容都适合内存，您就可以使用哈希表。但是，一旦您处理的数据量超过计算机的内存容量，就会出现问题。

解决方案是将数据输出到磁盘文件中，并进行外部排序。