algorithm - Find Top 10 Most Frequent visited URl，数据跨网络存储

Question

来源:谷歌面试问题

给定一个大型计算机网络，每台计算机都保存访问过的 url 的日志文件，找到访问次数最多的前 10 个 url。

有很多大<string (url) -> int (visits)> maps .

计算 < string (url) -> int (sum of visits among all distributed maps) , 并获得组合图的前十名。

主要限制: map 太大，无法通过网络传输。也不能直接使用MapReduce。

我现在遇到了很多这种类型的问题，其中处理需要在大型分布式系统上完成。我想不出也找不到合适的答案。

我所能想到的就是蛮力，它以某种或其他方式违反了给定的约束。

Answer 1

它说你不能直接使用 map-reduce，这暗示问题的作者想让你思考 map reduce 是如何工作的，所以我们只会模仿映射减少:

1. 预处理:令 R 为集群中服务器的数量，给每个 来自 0,1,2,...,R-1 的服务器唯一 ID
2. (map) 对于每个 (string,id) - 将元组发送到具有 id hash(string) % R 的服务器。
3. (减少)完成第 2 步(简单的控制通信)后，为每个服务器生成前 10 个字符串的 (string,count)。请注意，那些在步骤 2 中发送到此特定服务器的元组。
4. (map) 每个服务器会将他所有的前 10 个发送到 1 个服务器(让它成为服务器 0)。应该没问题，只有10*R条记录。
5. (减少)服务器 0 将产生整个网络的前 10 名。

注意事项:

• 算法的问题，就像大多数大数据算法一样 不要使用框架来处理故障服务器。 MapReduce 需要 为你照顾它。
• 上述算法可以非常直接地转换为 2 阶段 map-reduce 算法。