我最近搞砸了一次面试,因为一个简单的问题回答得不好:LinkedIn 之类的网站如何有效地显示您与页面上显示的每个人的关系距离(第一/第二/第三)(例如,在人员搜索结果中,工作人员列表中)在公司等)?
<EDIT>我得到了解决方案的基本“技巧”:找到“与我的距离”是一种常见操作(例如,单个页面上 20x+,每个登录会话 100 次),所以你可以做部分“我到的距离” X",缓存它,然后多次重复使用缓存的部分结果,以使其他操作更便宜。我还猜测部分结果可能是我的二级连接,因为“缓存所有三级连接”在 RAM 和 CPU 中的成本太高。</编辑>
但是当试图将这种见解转化为解决方案时,我想出了一个笨拙的答案,涉及为网站上每个人创建二级连接的持久缓存(这在性能上会非常昂贵并且维护起来很复杂),我接受了以一种几乎没有技术意义的方式使用布隆过滤器的莫名其妙的绕道。在得到这样的答案后,我不会雇用自己!
后来,在没有面试压力的情况下思考这个问题,我想出了一个更合理的答案。
构建一种非常快速的方法来获取每批用户 ID 的第一级连接(批量大小高达 ~1000?)。这可能意味着一个由大量 RAM 服务器组成的专用集群,可以将整个网络的第一级连接缓存在内存中。幸运的是,50M 会员 x 平均。每个成员 100 个连接 x 每个成员 ID 4 个字节 = <25GB 缓存在 RAM 中,这对于价格合理的硬件是可行的。而且每天的更改数量将低于 1%,因此保持缓存最新并不难。(请注意,关系数据库可能不是实现此缓存的错误选择,因为“大量随机 I/O”访问模式会扼杀关系数据库的性能。)
当用户登录时,通过获取每个一级连接的一级连接来缓存他或她的二级连接,并粘贴在哈希表中(key = 二级 ID,值 = 连接的一级连接数组你)。还缓存您的第一级连接,这样您就可以通过一次回调远程缓存服务器来拉回第一级和第二级。用户 ID 很容易分区,因此像 memcached 这样的分布式缓存可能会很好地解决这个问题。
对于任何用户 ID,要查找它是否在您的“网络”中以及它与您的关系(第 1、第 2、第 3),请执行以下操作:
- 如果 ID 在您的第一级连接中,请停止。
- 尝试在缓存的 2 级连接哈希表中查找 ID。如果找到,返回连接你的连接数组。
- 获取 ID 的第一级连接,并为每个连接重复步骤 #2。将所有结果聚合到一个数组中并返回它们。
- <EDIT>重构为批处理实现(“查找从我到 N 个不同用户的距离”),因此您可以从第 3 步获得所有远程结果,而无需进行 N 个远程调用。</编辑>
但我确信对此有更好的答案。你的是啥呢?如果您想要额外的挑战,请尝试模拟面试情况(无法在 Web 上查找解决方案)。
请注意,这个问题是关于一个最佳解决方案的,不管LinkedIn今天实际上是如何做的,我在上面写了自己的答案后查阅了这个问题。