Post 系统的设计
因为每一次的操作都是 count + 1和 count - 1,那么每次你通过 hashmap 找到对应的element在数据结构中的位置,+1的话,就是往头移动一格,-1的话,就是往尾巴移动一格。总而言之复杂度都是 O(1)。当你需要找 Top K 的时候,也是 O(k)的时间 可以解决的。
1 2 3 4 5 6
01
02 03
如果是5分钟以内的数据,就不抽样,全记录。如果是最近1小时,就可以按照比如 1/100 的概率进行 sample。
这个思想我们在Web Crawler 的那节课中提到过。
04
沃玛的TOP5商品
Round4,系统设计,实时的top5商品
https://www.1point3acres.com/bbs ... read&tid=494453
我就先做做思考,希望能够通过讨论来深化这个系统设计题目和不同设计的对比。
商品的出售应该是各个渠道的总和。沃尔玛有店,有网,可能还有其它途径比如eBay上。所以每个渠道都应该每隔K分钟向某个中央地区submit销售的delta。
我一开始想的简单,TOP5只能出自于每个渠道的TOP5,因此每个渠道需要sbumit不超过本渠道的top5。后来很快否定了这一flawed思路。也就是每个渠道要submit真实的自上次传送的变化值。
由于有退货,和纠错,所以delta可以允许有负值。
每个package里都应该有个Id和timestamp。这两个值可以用来解决是否重复submission的问题。
从发送方来说,应该保证严格的升序。比如上次网络坏了,没能submit上去,那么这个新产生的package只好等待。。。直到网络修好,才一个一个按照时许把拖延下来的package submit上去。
每件货物有沃尔玛自己的Unique商品ID:Delta
我们需要设计的这个系统在得到这些数据以后就可以进行计算并求TOP5了。
我们假设沃尔玛卖的商品很大很大,某个冷门的货物即便卖了一件,也需要写入数据库。考虑到数据库的写入能力的限制,我认为写入数据库不妨一天一次
实时计算TOP5,不需要数据库,假设我们分布计算各个产品的总销售值,每个分布节点负责+-每件商品结束后求出它负责的商品的总销售值,然后把它的TOP5(绝对值)送到下一个计算节点。
下一个计算节点在得到这些绝对值后,用quickselect也好,得到TOP5,把计算结果和该结果的时间戳送到某个地方,以后哪个报表或者显示什么的就不属于这个系统设计了
“假设沃尔玛卖的商品很大很大,某个冷门的货物即便卖了一件,也需要写入数据库。考虑到数据库的写入能力的限制,我认为写入数据库不妨一天一次。”
我不知道我理解你原话对没有,但是订单状态不可能要等到一天才更新一次,一般是写入的时候进行同步,乐观锁这里比较合适。
我认为walmart这种很有可能是垂直业务划分,所以去他们的网站跨大的department每次跳转延迟都很大。
将业务分片粒度做到写入可以承受就可,然后可以实时上报本地top5,汇总生成全局top5就是小问题
实现前5分钟,1小时,24小时内分享最多的post的系统
这个题是一个很好的面试题,因为可以从算法和系统两个角度进行考察。
从算法的角度分析
可以简单的称之为
Top K Frequent Elements in Recent X mins.
算法的角度,本质就是设计一个数据结构,支持给某个key的count+1(有一个post被分享了),给某个key的count-1(有一个分享的计数已经过期了),然后查询Top k。
做法是维护一个有序序列(用链表来维护),每个链表的节点的key是 count,value是list of elements that has this count,也用linked list串起来。 比如 a出现2次,b出现3次,c出现2次,d出现1次。那么这个链表就是:
{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 的思路答出上述的方法。这个就过了第一关,算法关。但是还没结束,这个题还有第二关,那就是系统设计关。上面的算法从算法的角度没办法更优了,每个分享操作都是O(1)的代价,每个求Top K都是O(k)的代价。已经很棒了。
http://massivealgorithms.blogspot.com/2016/11/leetcode-460-lfu-cache.html
但是系统的角度出发,会存在这样一些问题:
http://massivealgorithms.blogspot.com/2016/11/leetcode-460-lfu-cache.html
但是系统的角度出发,会存在这样一些问题:
如果QPS比较高,比如 1m,这个数据结构因为要加锁才能处理,所以会很慢。
分享的数据本身是分布式的,而不是中心化的,也就是说,比如有1000台web服务器,那么这1000台web服务器的是最先获得哪个帖子被分享的数据的,但是这些数据又都分布在这1000台web服务器中,如果用一个中心化的节点来做这个数据结构的服务,那么很显然这个中心节点会成为瓶颈。
比如这个系统用在twitter 这样的服务中,根据长尾理论,有80%或者更多的帖子连 Top 20% 都排不进去。而通常来说,从产品的角度,我们可能只需要知道 Top 20 最多是 Top 100 的数据就可以了。整个系统浪费了很多时间去统计那些永远不会成为Top 100的数据。
题目的要求是“5分钟,1小时,24小时”,而不是“最近2分零30秒”,“最近31秒”,也存在较大的优化空间
真实产品实时性要求和准确性没有那么高。你需要查询最近5分钟的Top K,结果得出的是最近5分02秒的Top K在产品中是没有太大问题的。
查询Top k 的次数远低于count + 1和 count -1 的次数。
综上所述我们给出一些针对性优化策略:
分布式统计 Distributed:
每隔5~10秒向中心节点汇报数据
也就是说,哪些帖子被分享了多少次这些数据,首先在 web server 中进行一次缓存,也就是说web server的一个进程接收到一个分享的请求之后,比如 tweet_id=100 的tweet被分享了。那么他把这个数据先汇报给web server上跑着的 agent 进程,这个agent进程在机器刚启动的时候,就会一直运行着,他接受在台web server上跑着的若干个web 进程(process) 发过来的 count +1 请求。
这个agent整理好这些数据之后,每隔5~10秒汇报给中心节点。这样子通过5~10s的数据延迟,解决了中心节点访问频率过高的问题。这个设计的思路在业界是非常常用的(做这种数据统计服务的都是这么做的),我们在《系统设计班》的datadog一节的课中,就讲到过用这种思路来统计每一个event发生了多少次。
分阶段统计 Level
在《系统设计班》的 ratelimiter 一节课中,我们也提到了这种分阶段统计的思想。
即如果我要去算最近5分钟的数据,我就按照1秒钟为一个bucket的单位,收集最近300个buckets里的数据。如果是统计最近1小时的数据,那么就以1分钟为单位,收集最近60个Buckets的数据,如果是最近1天,那么就以小时为单位,收集最近24小时的数据。那么也就是说,当来了一个某个帖子被分享了1次的数据的时候,这条数据被会分别存放在当前时间(以秒为单位),当前分钟,当前小时的三个buckets里,用于服务之后最近5分钟,最近1小时和最近24小时的数据统计。
你可能会疑惑,为什么要这么做呢?这么做有什么好处呢?
这样做的好处是,比如你统计最近1小时的数据的时候,就可以随着时间的推移,每次增加当前分钟的所有数据的统计,然后扔掉一小时里最早的1分钟里的所有数据。这样子就不用真的一个一个的+1或者-1了,而是整体的 +X 和 -X。当然,这样做之后,前面的算法部分提出来的数据结构就不work了,但是可以结合下面提到的数据抽样的方法,来减小所有候选 key 的数目,然后用普通的 Top K 的算法来解决问题。
参考练习题:http://www.lintcode.com/en/problem/top-k-frequent-words/
数据抽样 Sample
可以进行一定程度的抽样,因为那些Top K 的post,一定是被分享了很多很多次的,所以可以进行抽样记录。
如果是5分钟以内的数据,就不抽样,全记录。如果是最近1小时,就可以按照比如 1/100 的概率进行 sample。
这个思想我们在Web Crawler 的那节课中提到过。
缓存 Cache
对于最近5分钟的结果,每隔5s才更新一次。
对于最近1小时的结果,每隔1分钟更新一次。
对于最近24小时的结果,每隔10分钟才更新一次。
对于最近1小时的结果,每隔1分钟更新一次。
对于最近24小时的结果,每隔10分钟才更新一次。
用户需要看结果的时候,永远看的是 Cache 里的结果。另外用一个进程按照上面的更新频率去逐渐更新Cache。
总结
以上的这些优化方法,基本都基于一个基本原则:在很多的系统设计问题中,不需要做到绝对精确和绝对实时。
特别是这种统计类的问题。如果你刷算法题刷很多,很容易陷入设计一个绝对精确和绝对实时的系统的误区。一般来说面试中不会这么要求,如果这么要求了,那说明考你的是算法,算法才需要绝对准确和实时。
Round4,系统设计,实时的top5商品
https://www.1point3acres.com/bbs ... read&tid=494453
我就先做做思考,希望能够通过讨论来深化这个系统设计题目和不同设计的对比。
商品的出售应该是各个渠道的总和。沃尔玛有店,有网,可能还有其它途径比如eBay上。所以每个渠道都应该每隔K分钟向某个中央地区submit销售的delta。
我一开始想的简单,TOP5只能出自于每个渠道的TOP5,因此每个渠道需要sbumit不超过本渠道的top5。后来很快否定了这一flawed思路。也就是每个渠道要submit真实的自上次传送的变化值。
由于有退货,和纠错,所以delta可以允许有负值。
每个package里都应该有个Id和timestamp。这两个值可以用来解决是否重复submission的问题。
从发送方来说,应该保证严格的升序。比如上次网络坏了,没能submit上去,那么这个新产生的package只好等待。。。直到网络修好,才一个一个按照时许把拖延下来的package submit上去。
每件货物有沃尔玛自己的Unique商品ID:Delta
我们需要设计的这个系统在得到这些数据以后就可以进行计算并求TOP5了。
我们假设沃尔玛卖的商品很大很大,某个冷门的货物即便卖了一件,也需要写入数据库。考虑到数据库的写入能力的限制,我认为写入数据库不妨一天一次
实时计算TOP5,不需要数据库,假设我们分布计算各个产品的总销售值,每个分布节点负责+-每件商品结束后求出它负责的商品的总销售值,然后把它的TOP5(绝对值)送到下一个计算节点。
下一个计算节点在得到这些绝对值后,用quickselect也好,得到TOP5,把计算结果和该结果的时间戳送到某个地方,以后哪个报表或者显示什么的就不属于这个系统设计了
“假设沃尔玛卖的商品很大很大,某个冷门的货物即便卖了一件,也需要写入数据库。考虑到数据库的写入能力的限制,我认为写入数据库不妨一天一次。”
我不知道我理解你原话对没有,但是订单状态不可能要等到一天才更新一次,一般是写入的时候进行同步,乐观锁这里比较合适。
我认为walmart这种很有可能是垂直业务划分,所以去他们的网站跨大的department每次跳转延迟都很大。
将业务分片粒度做到写入可以承受就可,然后可以实时上报本地top5,汇总生成全局top5就是小问题