带堆的MapReduce排序

Question

我试图分析包含follower和followee对的社交网络数据。我想找到十大用户中使用MapReduce最多的用户。

我用一步userID和number_of_followee做了一对MapReduce。

然而，对于这些数据，我不知道如何在分布式系统中对它们进行排序。

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

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

非常感谢。

Answer 1

如果您有user_id = number_of_followers格式的大输入文件(文件)，那么查找顶级N用户的简单地图缩减算法是：

1. 每个映射器处理自己的输入，并在其文件中找到顶级的N个用户，并将它们写入一个减速器
2. 单减速器接收number_of_mappers * N行并在其中查找顶级N个用户

Answer 2

要按降序排序数据，您需要另一个mapreduce作业。Mapper将发出“追随者数”作为键，twitter句柄作为值。

class SortingMap extends Map<LongWritable, Text, LongWritable, Text> {
    private Text value = new Text();
    private LongWritable key = new LongWritable(0);

    @Overwrite
    public void map(LongWritable key, Text value, Context context) throws IOException {
        String line = value.toString();
        // Assuming that the input data is "TweeterId <number of follower>" separated by tab
        String tokens[] = value.split(Pattern.quote("\t"));
        if(tokens.length > 1) {
            key.set(Long.parseLong(tokens[1]));
            value.set(tokens[0]);
            context.write(key, value);
        }
    }
}

对于还原剂，请使用IdentityReducer

// SortedComparator Class

public class DescendingOrderKeyComparator extends WritableComparator {
    @Override
    public int compare(WritableComparable w1, WritableComparable w2) {
        return -1 * w1.compareTo(w2);
    }
}

在驱动程序类中，设置SortedComparator

job.setSortComparatorClass(DescendingOrderKeyComparator.class);