东邪老师讲解 Post 系统的设计

正文

请到「今天看啥」查看全文

{3: [b]} --> {2: [a ->c]} --> {1: [d]}

然后另外还需要一个hashmap，key是element，value是这个element在链表上的具体位置。

因为每一次的操作都是 count + 1和 count - 1，那么每次你通过 hashmap 找到对应的element在数据结构中的位置，+1的话，就是往头移动一格，-1的话，就是往尾巴移动一格。总而言之复杂度都是 O(1)。当你需要找 Top K 的时候，也是 O(k)的时间 可以解决的。

这个数据结构来自 LFU 的论文：
http://dhruvbird.com/lfu.pdf
LintCode上有LFU的题， 可以做一下：
www.lintcode.com/problem/lfu-cache

从系统设计的角度分析

所以一般来说，你可能首先需要按照 LFU 的思路答出上述的方法。这个就过了第一关， 算法关 。但是还没结束，这个题还有第二关，那就是 系统设计关 。上面的算法从算法的角度没办法更优了，每个分享操作都是O(1)的代价，每个求Top K都是O(k)的代价。已经很棒了。但是系统的角度出发，会存在这样一些问题：

1

如果QPS比较高，比如 1m，这个数据结构因为要加锁才能处理，所以会很慢。

2

分享的数据本身是分布式的，而不是中心化的，也就是说，比如有1000台web服务器，那么这1000台web服务器的是最先获得哪个帖子被分享的数据的，但是这些数据又都分布在这1000台web服务器中，如果用一个中心化的节点来做这个数据结构的服务，那么很显然这个中心节点会成为瓶颈。

3

比如这个系统用在twitter 这样的服务中，根据长尾理论，有80%或者更多的帖子连 Top 20% 都排不进去。而通常来说，从产品的角度，我们可能只需要知道 Top 20 最多是 Top 100 的数据就可以了。整个系统浪费了很多时间去统计那些永远不会成为Top 100的数据。

请到「今天看啥」查看全文