caching - 像 LinkedIn 这样的网站如何在每个人的名字旁边有效地显示第一/第二/第三级关系？

Question

我最近因为回答不好一个简单的问题而搞砸了一次工作面试:像LinkedIn这样的网站如何有效地显示你与页面上显示的每个人的关系距离(第一/第二/第三)(例如在人员搜索结果中，列表中)在公司等工作的人员)？

<编辑> 我得到了解决方案的基本“技巧”:查找“距我的距离”是一个常见操作(例如，单个页面上 20 倍以上，每个登录 session 100 倍)，因此您可以做“我到X的距离”的一部分，缓存它，然后多次重复使用缓存的部分结果，以使其他操作更便宜。我还猜测部分结果可能是我的二级连接，因为“缓存所有三级连接”在 RAM 和 CPU 上的成本太高。

但是，当尝试将这种见解转化为解决方案时，我想出了一个笨拙的答案，涉及为站点上每个人的二级连接创建持久缓存(这在性能方面非常昂贵，并且维护起来很复杂)，我莫名其妙地绕道使用 Bloom Filters以一种几乎没有技术意义的方式。在得到这样的回答后我不会雇用自己!

后来，当我在没有面试压力的情况下思考这个问题时，我得出了一个更合理的答案。

• 构建一种非常快速的方法来获取每批用户 ID 的一级连接(批量大小高达 ~1000？)。这可能意味着一个由大量 RAM 服务器组成的专用集群，可以将整个网络的第一级连接缓存在内存中。幸运的是，5000 万成员(member) x 平均人数。每个成员 100 个连接 x 每个成员 ID 4 字节 = <25GB 缓存在 RAM 中，这对于价格合理的硬件来说是可行的。而且每天的更改数量将低于 1%，因此保持缓存最新并不是太难。 (请注意，关系数据库可能不是实现此缓存的糟糕选择，因为“大量随机 I/O”访问模式会降低关系数据库性能。)

• 当用户登录时，通过获取每个第一级连接的第一级连接来缓存他或她的第二级连接，并粘贴在哈希表中(键=第二级ID，值=数组连接您的第一级连接)。还可以缓存您的第一级连接，以便您可以通过对远程缓存服务器的单个回调来拉回第一级和第二级连接。用户 ID 很容易分区，因此像 memcached 这样的分布式缓存可能很适合此目的。

• 对于任何用户 ID，要了解它是否在您的“网络”中以及它与您的关系(第一、第二、第三)，请执行以下操作:

  1. 如果该 ID 在您的第一级连接中，请停止。
  2. 尝试在缓存的二级连接哈希表中查找 ID。如果找到，则返回连接您的连接数组。
  3. 获取 ID 的第一级连接，并对每个连接重复步骤 #2。将所有结果聚合到一个数组中并返回它们。
  4. 重构为批量实现(“查找我到 N 个不同用户的距离”)，这样您就可以获得步骤 #3 中的所有远程结果，而不必弥补 N远程调用。

但我确信对此有更好的答案。你的是啥呢？如果您想要额外的挑战，请尝试模拟面试情况(无法在网络上查找解决方案)。

请注意，问题是关于最佳解决方案，无论how LinkedIn actually does it today如何，我在上面写下自己的答案后查了一下。

Answer 1

您也许可以利用关于 small world networks 的公理来优化这种类型的遍历。

小世界网络的特点是“集线器”，代表其他节点的非常密集的互连。网络中的大多数节点通常会在几跳内连接到拓扑上附近的节点(相距 1-4 跳)，或者通过一个或多个此类集线器进行路由。这是小世界网络行为方式的主要原因之一。