我最近通过一个简单的问题很难回答你的求职面试:LinkedIn这样的网站如何有效地显示你与页面上显示的每个人之间的关系距离(第一/第二/第三)(例如,在人们搜索结果中,工作人员列表)在公司等)？
<编辑>我得到了解决方案的基本"技巧":找到"与我的距离"是一种常见的操作(例如,单页上20x +,每次登录会话100次),所以你可以做到"我的距离"的一部分X",缓存它,然后多次重复使用缓存的部分结果,以使其他操作更便宜.我还猜测部分结果很可能是我的二级连接,因为"缓存所有第三级连接"在RAM和CPU中成本太高.
但是当我试图将这种洞察力转化为解决方案时,我想出了一个笨拙的答案,涉及在网站上创建每个人的二级连接的持久缓存(这将是非常昂贵的性能和复杂的维护),我采取了一种莫名其妙的转向使用布鲁姆过滤器的方式几乎没有技术意义.在这样的答案之后,我不会雇用自己!
后来,当我在没有面试压力的情况下思考问题时,我提出了一个更合理的答案.
构建一种非常快速的方法来获得每批用户ID的第一级连接(批量大小可达~1000？).这可能意味着一个由大量RAM服务器组成的专用集群,它可以将整个网络的第一级连接缓存在内存中.幸运的是,50M会员x平均.每个成员100个连接x每个成员4个字节ID = <25GB缓存在RAM中,这对于价格合理的硬件是可行的.并且每天的更改次数将低于1%,因此保持缓存最新并不太难.(请注意,关系数据库可能是实现此缓存的不良选择,因为"大量随机I/O"访问模式会破坏关系数据库性能.)
当用户登录时,通过获取每个第一级连接的第一级连接来缓存其第二级连接,并粘贴在哈希表中(key =第二级ID,值=连接你的第一级连接数组) .同时缓存您的第一级连接,这样您就可以通过一次回调将第一级和第二级都拉回到远程缓存服务器.用户ID很容易分区,因此像memcached这样的分布式缓存可以很好地解决这个问题.
对于任何用户ID,要查找它是否在您的"网络"中以及它与您(第1,第2,第3)的关系,请执行以下操作:
如果ID在您的第一级连接中,请停止.
尝试在缓存的二级连接哈希表中查找ID.如果找到,请返回连接您的连接数组.
获取ID的第一级连接,并为每个连接重复步骤#2.将所有结果聚合到一个数组中并返回它们.
但我相信有更好的答案.你的是啥呢？如果您想要额外的挑战,请尝试模拟一个inteview情境(无法在Web上查找解决方案).
请注意,问题是关于最佳解决方案,无论LinkedIn今天如何实际执行,我在上面写了自己的答案之后就查了一下.
您可以利用关于小型世界网络的公理来优化这种类型的遍历.
小世界网络的特征在于"集线器",代表其他节点的非常密集的互连.网络中的大多数节点通常将在几跳内连接到拓扑附近的节点(1-4跳)或者将路由通过一个或多个这样的集线器.这是小型世界网络以他们的方式行事的主要原因之一.
京公网安备 11010802040832号 | 京ICP备19059560号-6 
