使用set cover算法优化大型分布式系统的查询延迟

13-08-25 banq
    

来自LinkedIn的一篇文章Using set cover algorithm to optimize query latency for a large scale distributed graph

LinkedIn在实现一个人的连接距离时,需要查询这个人的关系连接,这两个连接有可能存储在不同分区服务器,也可能存储在同一个服务器,但是原来系统不管是否存储在同一个节点,都看成存储在不同服务器,导致缓存等利用率低,延迟高。

他们使用了set cover算法,能够寻找一个集合中最小子集,这样能够提高查询合并延迟,提升性能。

该算法实现源码:github

[该贴被banq于2013-08-25 08:52修改过]