algorithm - 分布式数据并行前十算法

Question

这是一道面试题。假设有几台计算机，每台计算机都有一个非常大的访问 URL 日志文件。找到访问量最大的 前 10 个 URL。

例如:假设只有 3 台计算机，我们需要前两个访问量最大的 URL。

Computer A: url1, url2, url1, url3Computer B: url4, url2, url1, url1Computer C: url3, url4, url1, url3url1 appears 5 times in all logsurl2 2url3 3url4 2 So the answer is url1, url3

日志文件太大，RAM 放不下，无法通过网络复制。据我了解，使计算并行并使用所有给定的计算机也很重要。

你会怎么解决？

Answer 1

这是一个非常标准的问题，有一个众所周知的解决方案。您只需按 URL 对每台计算机上的日志文件进行排序，然后通过“主”计算机上大小为 k(您想要的项目数)的优先级队列合并它们。这种技术自 1960 年代以来一直存在，并且今天仍在使用(尽管略有修改)，形式为 MapReduce。 .

在每台计算机上，从日志文件中提取 URL 和计数，并按 URL 排序。由于日志文件大于内存，因此您需要进行磁盘合并。这需要读取日志文件的一大块，按 URL 排序，将大块写入磁盘。读取下一个 block 、排序、写入磁盘等。在某个时候，您有 M 个日志文件 block ，每个 block 都已排序。然后您可以进行 M 向合并。但不是将项目写入磁盘，而是按排序顺序(即按 URL 排序)将它们呈现给“主人”。

每台机器对自己的日志进行排序。

“主”计算机合并来自不同计算机的数据并进行前 K 个选择。这实际上是两个问题，但可以合并为一个。

master创建两个优先级队列:一个用于合并，一个用于top K选择。第一个的大小为 N，其中 N 是它从中合并数据的计算机的数量。第二个是大小 K:您要选择的项目数。我为此使用了一个最小堆，因为它既简单又相当快。

要设置合并队列，初始化队列并从每台“工作”计算机获取第一项。在下面的伪代码中，“从合并队列中获取最低项”意味着从合并队列中获取根项，然后从显示该项的工作计算机中获取下一个项。因此，如果队列包含 [1, 2, 3]，并且这些项目来自计算机 B、C、A(按此顺序)，那么获取最低的项目就意味着从计算机获取下一个项目B 并将其加入优先级队列。

然后 master 执行以下操作:

working = get lowest item from merge queue
while (items left to merge)
{
    temp = get lowest item from merge queue
    while (temp.url == working.url)
    {
        working.count += temp.count
        temp = get lowest item from merge queue
    }
    // Now have merged counts for one url.
    if (topK.Count < desired_count)
    {
        // topK queue doesn't have enough items yet.
        // so add this one.
        topK.Add(working);
    }
    else if (topK.Peek().count < working.count)
    {
        // the count for this url is larger
        // than the smallest item on the heap
        // replace smallest on the heap with this one
        topK.RemoveRoot()
        topK.Add(working)
    }
    working = temp;
}
// Here you need to check the last item:
if (topK.Peek().count < working.count)
{
    // the count for this url is larger
    // than the smallest item on the heap
    // replace smallest on the heap with this one
    topK.RemoveRoot()
    topK.Add(working)
}

此时，topK 队列具有计数最高的 K 个项目。

因此每台计算机都必须进行归并排序，时间复杂度为 O(n log n)，其中 n 是该计算机日志中的项目数。 master 上的合并是 O(n)，其中 n 是来自各个计算机的所有项目的总和。选择前 k 个项目的时间复杂度为 O(n log k)，其中 n 是 unique url 的数量。

当然，排序是并行进行的，每台计算机准备自己的排序列表。但是排序的“合并”部分是在主计算机合并的同时完成的，因此存在一些协调，所有机器都参与到那个阶段。