并行十大分布式数据算法

Question

这是一个面试问题.假设有几台计算机,每台计算机都保存一个非常大的访问URL日志文件.查找前十个访问量最大的网址.

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

Computer A: url1, url2, url1, url3
Computer B: url4, url2, url1, url1
Computer C: url3, url4, url1, url3

url1 appears 5 times in all logs
url2 2
url3 3
url4 2 

So the answer is url1, url3

日志文件太大而无法放入RAM并通过网络复制它们.据我了解,重要的是使计算并行并使用所有给定的计算机.

你会如何解决它？

Answer 1

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

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

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

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

主设备创建两个优先级队列:一个用于合并,另一个用于顶部K选择.第一个是大小为N,其中N是它合并数据的计算机数量.第二个是大小K:您要选择的项目数.我使用最小堆,因为它很容易且速度相当快.

要设置合并队列,请初始化队列并从每个"工作"计算机获取第一个项目.在下面的伪代码中,"从合并队列中获取最低项目"意味着从合并队列中获取根项目,然后从呈现该项目的任何工作计算机获取下一项目.因此,如果队列包含[1, 2, 3],并且项目来自计算机B,C,A(按此顺序),则获取最低项目将意味着从计算机B获取下一个项目并将其添加到优先级队列.

然后,主人执行以下操作:

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是该计算机日志中的项目数.主服务器上的合并是O(n),其中n是各个计算机的所有项目的总和.挑选前k项是O(n log k),其中n是唯一网址的数量.

当然,这些排序是并行完成的,每台计算机都准备了自己的排序列表.但是,排序的"合并"部分是在主计算机合并的同时完成的,因此存在一些协调,并且所有机器都参与该阶段.