Monday, April 24, 2017

Design Post System



Post 系统的设计
实现前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


但是系统的角度出发,会存在这样一些问题:



1
如果QPS比较高,比如 1m,这个数据结构因为要加锁才能处理,所以会很慢。
2
分享的数据本身是分布式的,而不是中心化的,也就是说,比如有1000台web服务器,那么这1000台web服务器的是最先获得哪个帖子被分享的数据的,但是这些数据又都分布在这1000台web服务器中,如果用一个中心化的节点来做这个数据结构的服务,那么很显然这个中心节点会成为瓶颈。
3
比如这个系统用在twitter 这样的服务中,根据长尾理论,有80%或者更多的帖子连 Top 20% 都排不进去。而通常来说,从产品的角度,我们可能只需要知道 Top 20 最多是 Top 100 的数据就可以了。整个系统浪费了很多时间去统计那些永远不会成为Top 100的数据。
4
题目的要求是“5分钟,1小时,24小时”,而不是“最近2分零30秒”,“最近31秒”,也存在较大的优化空间
5
真实产品实时性要求和准确性没有那么高。你需要查询最近5分钟的Top K,结果得出的是最近5分02秒的Top K在产品中是没有太大问题的。
6
查询Top k 的次数远低于count + 1和 count -1 的次数。


综上所述我们给出一些针对性优化策略:

01
分布式统计 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发生了多少次。
02
分阶段统计 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/
03
数据抽样 Sample
可以进行一定程度的抽样,因为那些Top K 的post,一定是被分享了很多很多次的,所以可以进行抽样记录。

如果是5分钟以内的数据,就不抽样,全记录。如果是最近1小时,就可以按照比如 1/100 的概率进行 sample。

这个思想我们在Web Crawler 的那节课中提到过。

04
缓存 Cache
对于最近5分钟的结果,每隔5s才更新一次。
对于最近1小时的结果,每隔1分钟更新一次。
对于最近24小时的结果,每隔10分钟才更新一次。
用户需要看结果的时候,永远看的是 Cache 里的结果。另外用一个进程按照上面的更新频率去逐渐更新Cache。
总结
以上的这些优化方法,基本都基于一个基本原则:在很多的系统设计问题中,不需要做到绝对精确和绝对实时。

特别是这种统计类的问题。如果你刷算法题刷很多,很容易陷入设计一个绝对精确和绝对实时的系统的误区。一般来说面试中不会这么要求,如果这么要求了,那说明考你的是算法,算法才需要绝对准确和实时。


沃玛的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就是小问题


Labels

Review (572) System Design (334) System Design - Review (198) Java (189) Coding (75) Interview-System Design (65) Interview (63) Book Notes (59) Coding - Review (59) to-do (45) Linux (43) Knowledge (39) Interview-Java (35) Knowledge - Review (32) Database (31) Design Patterns (31) Big Data (29) Product Architecture (28) MultiThread (27) Soft Skills (27) Concurrency (26) Cracking Code Interview (26) Miscs (25) Distributed (24) OOD Design (24) Google (23) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Interview Q&A (20) System Design - Practice (20) Tips (19) Algorithm (17) Company - Facebook (17) Security (17) How to Ace Interview (16) Brain Teaser (14) Linux - Shell (14) Redis (14) Testing (14) Tools (14) Code Quality (13) Search (13) Spark (13) Spring (13) Company - LinkedIn (12) How to (12) Interview-Database (12) Interview-Operating System (12) Solr (12) Architecture Principles (11) Resource (10) Amazon (9) Cache (9) Git (9) Interview - MultiThread (9) Scalability (9) Trouble Shooting (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Cassandra (8) Company - Uber (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Design (7) Interview Corner (7) JVM (7) Java Basics (7) Kafka (7) Mac (7) Machine Learning (7) NoSQL (7) C++ (6) Chrome (6) File System (6) Highscalability (6) How to Better (6) Network (6) Restful (6) CareerCup (5) Code Review (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Leetcode (5) Must Known (5) Python (5)

Popular Posts