43

我最近搞砸了一次面试，因为一个简单的问题回答得不好：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），请执行以下操作：

    1. 如果 ID 在您的第一级连接中，请停止。
    2. 尝试在缓存的 2 级连接哈希表中查找 ID。如果找到，返回连接你的连接数组。
    3. 获取 ID 的第一级连接，并为每个连接重复步骤 #2。将所有结果聚合到一个数组中并返回它们。
    4. <EDIT>重构为批处理实现（“查找从我到 N 个不同用户的距离”），因此您可以从第 3 步获得所有远程结果，而无需进行 N 个远程调用。</编辑>

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

请注意，这个问题是关于一个最佳解决方案的，不管LinkedIn今天实际上是如何做的，我在上面写了自己的答案后查阅了这个问题。

4

6 回答 6

6

您可以利用关于小世界网络的公理来优化这种类型的遍历。

小世界网络的特点是“集线器”，代表其他节点的非常密集的互连。网络中的大多数节点通常要么在几跳内连接到拓扑附近的节点（1-4 跳远），要么通过一个或多个这样的集线器进行路由。这是小世界网络以他们的方式行事的主要原因之一。

于 2009-10-12T20:09:41.817 回答
4

有趣的是，1970 年代的技术可以很好地对此进行建模。网络数据库模型有效地管理这种类型的关系。

它在临时查询或数据模型维护方面效率不高，因此随着关系数据模型的兴起而失宠。

于 2009-10-12T20:01:50.100 回答
1

如果您考虑一下，在 SQL 中执行此操作可能会占用大量处理器资源。

考虑到这一点，而且它最终会在所有地方使用，而且这个空间相对便宜……我建议根据您的语言偏好使用 Lucene（或 Lucene.NET）创建一个索引。你可以用这种方式做几件事。

您可以创建一个树型数据结构并递归地爬取您的索引，以查找所有父节点或子节点及其父节点或子节点，具体取决于您当时的需要。

或者您可以在创建时写出所有关系（空间是廉价的概念）。这将是一次写入过程（您不会以任何方式经常更新）。当创建或撤销关系时，您将对索引的更新进行排队（排队，因为您不想为单个请求打开写入...批量索引更新）。然后你可以阅读这个非常扁平的结构来获取有问题的 ID。

有了手中的 ID（从您执行的任何搜索类型），您就可以转到数据库以获取周围所需的信息。然后缓存您的输出以进一步最小化非常快速的搜索、数据库查询、数据构建......但如果它只是来自缓存，则速度更快。

使用 Velocity、MemCached 或 MemCached Win32 之类的东西在 Web 场中进行集中缓存。

于 2009-10-12T19:54:07.697 回答
1

我不确定表结构或系统的复杂性，但这是一个使用递归 CTE 的简单 SQL Server 示例：

DECLARE @People table (PersonID int, Name varchar(10))
DECLARE @Network table (PersonID int, NetworkedPersonID int)
INSERT INTO @People VALUES (1,'AAA')
INSERT INTO @People VALUES (2,'BBB')
INSERT INTO @People VALUES (3,'CCC')
INSERT INTO @People VALUES (4,'DDD')
INSERT INTO @People VALUES (5,'EEE')
INSERT INTO @People VALUES (6,'FFF')
INSERT INTO @People VALUES (7,'GGG')
INSERT INTO @People VALUES (8,'HHH')
INSERT INTO @Network VALUES (1,2)
INSERT INTO @Network VALUES (1,3)
INSERT INTO @Network VALUES (2,5)
INSERT INTO @Network VALUES (2,7)
INSERT INTO @Network VALUES (4,8)
INSERT INTO @Network VALUES (7,8)
INSERT INTO @Network VALUES (7,3)
INSERT INTO @Network VALUES (8,9)
DECLARE @TargetPersonID  int
SET @TargetPersonID=1

;WITH NetworkLevels AS
(   SELECT
        NetworkedPersonID,1 AS NetworkLevel
        FROM @Network
        WHERE PersonID=@TargetPersonID
    UNION ALL
    SELECT
        n.NetworkedPersonID, l.NetworkLevel+1
        FROM @Network                n
            INNER JOIN NetworkLevels l ON n.PersonID=l.NetworkedPersonID
    WHERE l.NetworkLevel<=2
)
SELECT * FROM NetworkLevels

输出：

NetworkedPersonID NetworkLevel
----------------- ------------
2                 1
3                 1
5                 2
7                 2
8                 3
3                 3

(6 row(s) affected)
于 2009-10-12T20:20:58.767 回答
1

实施

DistanceCategory(A,B): { 1, 2, 3+}

使用连接是双向的事实。

将第一级连接存储为一些 KV 疮中的排序列表：

Key: [UserFromId,UserToId].
Value: UserToId

伪代码：

DistanceCategory(A,B)
{
    if ( exists([A,B]) )
        return 1;
    if ( firstCommonElement(getAll([A,B]), getAll([A,B])) != null )
        return 2;
    return 3;
}

复杂度：O(C1+C2)。C1,C2 - 两个用户的连接数。

于 2015-10-23T08:58:51.117 回答
0

Linkedin 数据不是表示为一个大图吗？当一个人登录时，系统将拥有其节点的句柄，然后通过对3个级别进行广度优先遍历，系统会将这些节点保持为一个集合（以及哪个级别信息），并且当一个人出现在网页上时, 系统在这个节点集上进行查找并给出关系距离..

这是我的猜测。请随时指出，是什么使它不切实际。

于 2011-06-08T12:12:31.953 回答