我最近通过差劲回答一个直截了当的问题来搞砸了工作面试：像LinkedIn这样的网站如何有效地显示从您到页面上显示的每个人（例如，人搜索结果，公司工作的人等）？
但是，当试图将这种见解转化为解决方案时，我想到了一个令人困惑的答案，涉及创建站点上每个人的二级连接的持久性缓存（这在性能和维护方面将是非常重要的），并且我以一种毫无意义的方式绕开了Bloom Filters的使用。这样的回答后，我就不会再雇用自己了！
稍后，当我想到这个问题而没有面试的压力时，我想出了一个更合理的答案。
构建一种非常快速的方法来获取每批用户ID（批量大小最大为〜1000？）的第一级连接。这可能意味着一个由大量RAM服务器组成的专用集群，可以将整个网络的第一级连接缓存在内存中。幸运的是，有5000万会员x平均每个成员100个连接x每个成员ID 4个字节= <25GB以缓存在RAM中，这可以通过价格合理的硬件实现。而且每天的更改数量将不到1％，因此保持高速缓存的最新状态并不是一件难事。 （请注意，关系数据库可能不是实现此缓存的最佳选择，因为“大量随机I / O”访问模式会破坏关系数据库的性能。）
当用户登录时，通过获取每个第1级连接的第1级连接来缓存其第2级连接，并粘贴在哈希表中（键=第2级ID，值=第1级数组连接您的水平连接）。此外，还缓存您的第一级连接，因此您可以通过一次调用远程缓存服务器来拉回第一级和第二级。用户ID易于分区，因此像memcached这样的分布式缓存可能会很好地工作。
对于任何用户ID，要查找它是否在您的“网络”中以及与您的关系（第一，第二，第三），请执行以下操作：
[请注意，问题是关于最佳解决方案的，与how LinkedIn actually does it today无关，我在上面写下自己的答案后便查询了该问题。
您可以创建树型数据结构，然后递归爬网索引，以根据当时的需要查找所有父节点或子节点及其父节点或子节点。
或者您可以在创建所有关系时写出它们（空间很便宜）。这将是一次写入的过程（您不会以任何方式经常更新所有过程）。创建或撤消关系时，您将对索引进行更新排队（排队，因为您不想为单个请求打开写入操作...为索引更新添加批处理）。然后，您可以阅读这个非常扁平的结构来获取有问题的ID。
手头的ID（您执行的搜索类型来自于您，然后您可以去数据库获取周围所需的信息。然后缓存您的输出，以进一步最小化非常快速的搜索，数据库查询，数据构建...但是如果它只是来自缓存，则速度更快。
使用Velocity，MemCached或MemCached Win32之类的东西进行Web场的集中式缓存。
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)
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-两个用户的连接数。