一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 269|回复: 4
收起左侧

[系统设计/OOD] 系統設計救星! 一天內手把手教你面試System design Facebook chat

[复制链接] |试试Instant~ |关注本帖
jyt0532 发表于 2016-11-11 13:08:40 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
前言:感謝各位的支持與愛戴 希望前一篇文章http://www.1point3acres.com/bbs/thread-208829-1-1.html 會讓你對system design不那麼陌生 主要要注意的考點跟workflow上一篇文章已經cover了 接下來就是實戰演練 這篇主要的flow來自於InterviewBit的design messenger 搭配我其他Facebook blog的知識整合在一起用簡單的方式介紹

千萬別忘了我上篇講的5個step
Step1:Feature/Requirement
基本上每個問題的數字都可以問面試官或跟面試官確認 但他可能會要你自己估算 這時候就是考你對他們公司的產品有沒有sense

多少user? 多少message?  10B message/day, 300M users
average num of characters per message? 160 characters
1-1 only? group chat?  1-1
attachment? no
Max size of message? 64KB
notification? no
user presence? no

感覺到了嗎 你問得越細節 他就會知道你越瞭解他們的產品 特別是facebook是個要求你喜歡他們產品的公司 這種feature基本上interview不太會要你implement(時間不夠), 但你只要有提到就有加分 別忘了system design 50%考problem solving 50%考交流

Step2:Constrain
Data storage: 10B*160Byte = 1.6TB/day
If we want to store message for 10 years: 1.6*365*10 = 6PB storage
Traffic: 10B/24/60/60 = 115K message/s
Latency matters? Yes
A or C? C
像AorC你就要自己想一下 這個service哪個比較重要 得出結論後再跟面試官確認一下 像messenger一定是C比較重要的 其他service就可能比較product decision的就自己先比較一下優缺點後再問面試官

Step3:算一下你需要多大的machine多少台
迷途書僮:嘿我知道 可以apply上一篇文章中算幾台machine的例子!
6PB/72GB = 83333台...
別傻了兄弟 要會見招拆招 之前的例子是design cache 所以才需要用RAM(fast in memory read/write)現在並不需要
現在是用machine的storage space, assume我們的一台machine 有10TB space
6PB/10TB = 600台, 115K/600 = 191 QPS簡直輕鬆愉快

想更深入了解可以看一下amazon S3 http://docs.aws.amazon.com/AWSEC2/latest/UserGuide/AmazonS3.html
他可以跟EC2完美融合搭配使用
但interviewer也不會要求你知道EC2/S3 machine的spec
所以就自己make assumption 不要太誇張就好 當然要經過面試官同意

Step4:畫出大架構

                               
登录/注册后可看大图

別懷疑就是這麼簡單 所有架構都是從小開始
先想像你是個小公司 先做出基本需求 再來scale

既然這是messenger 那就勢必要design server的api
視情況可能還要對不同的client device設計不同的api

SendMessenge(senderId, receiverId, content)
getConversationByUserId(userid, page number, pagesize, latest updated timestamp)
getMessengeByConversationId(userId, page number, pagesize, latest updated timestamp)

1.這時候一定要提一下網路世界裡面很容易出現的問題 就是先送的封包後到或是後送的封包先到 所以在server端要記錄每個messenger的timestamp
這樣別人在fetch messenge的時候才不會出現錯誤的順序 可是這並不需要當成SendMessenge的input 因為前端不可信任(可能有惡意的前端改變你messenge的順序)
2.pagesize, pagenumber就是可以適用在不同的前端(不同螢幕大小 解析度) 所以前端要自己算這一次fetch要跟server要多少conversations/messenge 後兩個api 其實很像 但都不可或缺
3.給latest updated timestamp這樣同樣的messenge不用每次都重複傳到前端 前端只需要request user上次fetch之後的messg就好了

Step5: 喇賽時間
面試官: 現在開始處理scaling問題 上面那張圖只有一個Application Server 要是掛了怎麼辦
迷途書僮: 輕鬆 用多個application 處理 每個application都是stateless 要是問某個AS沒回應在問下一個

                               
登录/注册后可看大图

面試官: 這樣太浪費時間了 而且client的logic太過複雜
迷途書僮: 沒問題 那就加個中間層吧 世界上第一個拿CS Phd的人David Wheeler 說過
All problems in computer science can be solved by another level of indirection, except of course for the problem of too many indirection
CS領域的所有問題都可以透過加中間層來解決 除非這個問題是由太多中間層引起的
面試官: 那他還說過什麼名言你知道嗎?
迷途書僮: Compatibility means deliberately repeating other people's mistakes
面試官: 非常好 名師出高徒 想必你一定有在認真看一畝三分地J大的文章
迷途書僮: 所以加一層load balancer 就讓Client always 問LB 讓LB去maintain哪台AS還活著哪台掛了 Client不應該有任何Server端的資訊

                               
登录/注册后可看大图

面試官 可是這個diagram還是會有single point of failure的問題 那怎麼辦呢
迷途書僮: 我有認真看J大的文章 Active-Active LB 搞定!
面試官: 好 這樣你已經處理好AS端availablity的問題了 那接下來換Data Layer 你選RDBM還是NoSQL
迷途書僮: 剛剛算過要很多台機器 才存的下所有messenger 而且messenger是個write heavy的service, RMDB會非常難做 更不用說需要sharding, 這樣每次join都需要從不同的data server拿table來join 會崩潰 所以我們選擇denormalized NoSQL
面試官: 好 哪種NoSQL比較好呢
迷途書僮: 下一篇jyt0532的救世文會告訴你各個NoSQL的比較 我先告訴你答案 支援write heavy的NoSQL不是Cassandra就是HBase 還有Amazon DynamoDB
面試官: 很好 事實上FB一開始是用Cassandra 後面改成HBase 有興趣的話可以看這篇文章https://www.facebook.com/notes/f ... sages/454991608919/
迷途書僮: 然後用用user_id來當index sharding, Consistent hash! http://blog.csdn.net/cywosp/article/details/23397179/
面試官: 那如果單台DB掛了怎麼辦
迷途書僮: replication! consistent hash搭配replication的方法參考這個網站http://horicky.blogspot.com/2009/11/nosql-patterns.html 搜尋data replication
面試官: 好已經解決single point of failure的問題了 可是現在performance太差 怎麼辦       
迷途書僮: Cache 但我們這裡要求要strong consistency 所以選擇write through方式
面試官: 非常好 還有個concurrency的問題 DB level通常這些常用的nosql都有implement atomic write(Cassandra, HBase) 可是你的cache layer沒有
迷途書僮: 只好忍痛加個user level lock 一次只有一個thread可以寫入我的cache
面試官: 好現在來總結一下

                               
登录/注册后可看大图



有興趣瞭解更多的 推薦以下兩個link 不過對於new grad上面講的已經很夠了
http://www.cnblogs.com/piaoger/archive/2012/08/19/2646530.html
https://code.facebook.com/posts/ ... ture-for-messenger/
看完之後你要知道什麼是long polling 跟一般的http request有什麼差別

累死我了 google明天送HC 希望地裏版眾大家把力量借給我 求RP 下一篇design twitter



补充内容 (2016-11-13 06:47):
請大家看這篇就好 感恩http://www.1point3acres.com/bbs/thread-210147-1-1.html

评分

2

查看全部评分

FTD2014 发表于 3 天前 | 显示全部楼层
感谢楼主,求问facebook的blog地址能否发一下,感谢!
回复 支持 反对

使用道具 举报

qxr 发表于 前天 10:12 | 显示全部楼层
谢谢楼主分享!mark一下
回复 支持 反对

使用道具 举报

30048686 发表于 昨天 18:02 | 显示全部楼层
图好像看不了了 不过干货很多感谢lz
回复 支持 反对

使用道具 举报

hoter 发表于 13 小时前 | 显示全部楼层
感谢楼主,不过图好像挂掉了,请问楼主哪里可以看到你发的那些图呢,你的blog里面有吗?
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 21:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表