hadoop - MapReduce 堆排序

Question

我正在尝试分析包含 follower 和 followee 对的社交网络数据。我想找到使用 MapReduce 的追随者最多的 前 10 位用户。

我用一个 MapReduce 步骤制作了一对 userID 和 number_of_followee。

但是，对于这些数据，我不确定如何在分布式系统中对它们进行排序。

我不确定如何在 Mappers 和 Reducers 中使用 priority queue，因为它们具有分布式数据。

谁能解释一下如何使用数据结构对海量数据进行排序？

非常感谢。

Answer 1

如果您有格式为user_id = number_of_followers 的大输入文件(文件)，用于查找前N 用户的简单map-reduce 算法是:

1. 每个 mapper 处理自己的输入并在其文件中找到前 N 个用户，将它们写入单个 reducer
2. 单个 reducer 接收 number_of_mappers * N 行并在其中找到前 N 个用户