9

资料来源：谷歌面试问题

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

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

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

主要限制：地图太大而无法通过网络传输。也不能直接使用 MapReduce。

我现在遇到了很多此类问题，需要在大型分布式系统上进行处理。我想不出或找到合适的答案。

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

4

2 回答 2

14

它说您不能直接使用 map-reduce ，这暗示了问题的作者希望您思考 map-reduce 的工作原理，因此我们将仅模仿 map-reduce 的操作：

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

笔记：

  • 与大多数不使用框架的大数据算法一样，该算法的问题在于处理故障服务器。MapReduce 会为您处理它。
  • 上述算法可以非常直接地转换为 2 阶段 map-reduce 算法。
于 2013-07-29T16:21:52.183 回答
3

在最坏的情况下，任何不需要传输整个频率表的算法都会失败。我们可以创建一个简单的案例，其中全球前 10 名都位于每台机器列表的底部。

如果我们假设 URI 的频率遵循 Zipf 定律，我们可以提出有效的解决方案。下面是一种这样的解决方案。

每台机器发送前 K 个元素。K 仅取决于可用的带宽。一台master机器聚合频率，找到第10个最大频率值“V10”（注意这是一个下限。由于全局top-10可能不在每台机器的top-K中，所以总和是不完整的）。

在下一步中，每台机器都会发送一个频率为 V10/M（其中 M 是机器数）的 URI 列表。所有这些的联合被发送回每台机器。每台机器依次发回这个特定列表的频率。一个主将这个列表聚合到前 10 个列表中。

于 2013-07-29T16:58:59.920 回答