码农翻墙去美帝 ―― 系统设计准备 | ITint5
tinyurl一定要非常充分的准备。我在F,L,G三家面试时都被问到了这题。这题看似简单,其实可以将上面讨论的大部分东西多装进来,可以讨论的地方很多。
Read full article from 码农翻墙去美帝 ―― 系统设计准备 | ITint5
核心考察的是大流量下的distributed backend service design。因为这几家都是大公司,面对的都是每天至少billion级别的request,因此需要对这个场景的design有深刻认识。而design的核心思路就是trade-off。每个方案都不是十全十美的,比较postive的应对是:可以给出多种方案,在给出每种方案时,同时给出该方案的优点和缺点,并结合我们正在讨论的设计场景(给定的约束条件下),做出该方案好坏的点评,并最终选择一种“最适合”的方案。
模板套路大致为:
1. user case:和面试官讨论该系统需要实现什么功能,大部分设计都需要实现“读”和“写”两个基本功能。这样就确定了功能边界。(避免你和面试官聊high了想出很多新功能,从而偏题)
2. system constraint:和面试官明确max requests/day, QPS, storage size, latency,availability等基本系统约束。也有可能面试官不会给你,而是让你估算,比如面试官会说,如果这个是Facebook主页上的feature,你就需要结合Facebook本身的traffic, active user等数值进行估算(这就要求对各家的这些number要有大概认知)。这一部分是确定性能边界,也会决定你的设计框架。
3. abstract design: 先给出high level的design,自顶向下逐步细化。一般来讲,high level都是三层:API, application layer, data layer。其中API是interface,负责和调用方打交道。application layer实现所有业务逻辑,为了实现distributed和scalability,要求application layer是stateless的(无状态:即server不保存任何request相关的data, 所有server的code base完全一致). 这样,如果application不能host更多request时,简单的增加更多机器即可(horizontal scalability)。为了实现load balance和failover, 在application layer入口加入load balancer(比如ZooKeeper)。data layer实现所有业务数据的读写。一般分为cache和persistant storage两层。cache让high request data能够快速读写(write through/write back),persistant storage保证所有数据不会丢失。
4. drill down:一般面试官会开始提问题,针对具体部分展开深入头论。
比如针对业务逻辑的实现方案(比如twitter timeline到底是用fan-out-write还是fan-out-read),针对data layer的实现方案(cache的设计,比如从基本的LRU问到distributed cache,或者是cache+storage设计,比如BigTable+GFS or Cassandra or Dynamo)。当你给出每个idea时,需要同时给出这种方案本身的优缺点,并最终结合我们之前确定的1,2(功能边界和系统约束),选择最适合的方案。
比如针对业务逻辑的实现方案(比如twitter timeline到底是用fan-out-write还是fan-out-read),针对data layer的实现方案(cache的设计,比如从基本的LRU问到distributed cache,或者是cache+storage设计,比如BigTable+GFS or Cassandra or Dynamo)。当你给出每个idea时,需要同时给出这种方案本身的优缺点,并最终结合我们之前确定的1,2(功能边界和系统约束),选择最适合的方案。
5. bottleneck: 如果还有时间,可以回顾我们已经设计好的系统,提出这个系统从整体上看,最可能出现瓶颈的地方,并和面试官互动的讨论。
有了以上框架,就需要针对框架里提到的各种主流技术去进行深入了解。在看文档或paper时,要多思考总结,互相比较,抽象理解。
比如大家都知道Google三驾马车(MapReduce, BigTable, GFS),我当时就想为什么这三个系统奠定了云计算的基础?个人理解是,这三个系统正好在distributed环境下拆解了传统数据库的三大基本功能(GFS: distributed persistent storage, BigTable: distributed structured data access/indexing,MapReduce:distributed data processing)。而Cassandra/Dynamo本质上也是为了实现distributed structured data access and persistent storage,因此功能上和BigTable+GFS是近似的。再回到NoSQL的基本原则之一,不保证数据的consistency,由业务层来完成数据的join/processing,这就是MapReduce上场的地方了。因此这三家马车组合起来,正好是distributed环境下的一个database。
另外一个例子,同样是timeline, twitter用fan-out-write(将new feed直接写到follower的timeline里),而Facebook却用fan-out-read(在读的时候实时抓取相关用户的feeds并merge/rank)。why?我的理解是,这两个timeline是有本质不同的,twitter的timeline是比较传统的按时间顺序呈现你follow的人的feeds,而Facebook的news feeds更像一个timeline + social graph search, 不仅有好友最新的post,还有基于social graph搜索之后的相关结果(可能是你朋友的朋友,或者朋友赞过的照片,等),并且可能会有个性化结果。回归到fan-out-read/fan-out-write一个本质区别是,如果request/answer pattern越不确定(比如web search就是一个极端例子,query pattern趋近无限),或者answer features需要agile的变化,那么用fan-out-read越好(read所有candidate后,灵活的组织结果)。
需要关注的系统和技术:
- Google三驾马车的paper(MapReduce, BigTable, GFS) 对应Hadoop,HDFS,
HBase - Cassandra, Dynamo paper (关注点:consistent hash, decentralized system design(gossip))
- Memcached (distributed cache)
- Redis (all-in-memory solution)
- ZooKeeper (load balancer/configuration center/name service/distributed lock etc..)
- Thrift(cross language interface and RPC)
- Storm(realtime streaming processing, 应对类似统计过去1分钟的count一类的题目), spark
一些常见面试题目,mitbbs上已经有高人进行了全面总结,我会转载贴在下面,我基本上是follow之。这里有一点补充:
这道题我觉得很有价值的文章:
http://www.hiredintech.com/app#system-design (讲design的框架,我引用了很多他的方法论,其中以tinyurl做例子,讲的很透彻)
其实针对一家的design准备过程,就是了解这家technology stack的过程。当你熟悉之后,在design环节灵活使用这些系统设计的idea来回答面试官的提问,会和面试官产生更多的认同感(可能他每天也在使用这些系统)。这比现场凭空想象,两人各执一词互相挑战的氛围,要轻松有爱很多吧:)
另外一块需要充分准备的就是个人的background project,这也是design环节可能会涉及的。对于之前工作上做过的项目,一定要力求没有死角,理解全面深刻。更进一步,能够从更高的角度去看这个项目。比如我在Google面试时,有一轮基本上大部分时间在讨论我做过的一个项目。因为之前针对这个项目做了很多深入思考,比如如何将这个项目的方案推广到更泛化的语义搜索。正好在那次面试中,面试官在讨论清楚已有项目之后,就问到了这个问题,因为之前已经总结了一些思路,所以侃侃而谈。后来才了解,面试官在G家也是做类似工作,我之前思考总结的那些idea也给了他不少启发,可以说是英雄惜英雄,氛围很融洽:)。个人感觉,这几家公司都会匹配和你简历背景非常吻合(大部分情况下)的面试官来和你聊,因此如果你对你简历的上的东西不熟悉,理解不全面,不深刻,面试官是很容易发现的,但如果你能带给他惊喜,那么恭喜你,你很有机会能拿到一个strong hire.
=============以下为转载MITBBS上的高人总结帖================
1. 入门级的news feed
http://www.quora.com/What-are-best-practices-for-building-somet
http://www.infoq.com/presentations/Scale-at-Facebook
http://www.infoq.com/presentations/Facebook-Software-Stack
一般的followup question是估算需要多少server
另外这个帖子有讨论
http://www.mitbbs.ca/article_t/JobHunting/32463885.html
这篇文章稍微提到要怎么approach这种题,可以稍微看看
http://book.douban.com/reading/23757677/
2. facebook chat,这个也算是挺常问的
http://www.erlang-factory.com/upload/presentations/31/EugeneLet
https://www.facebook.com/note.php?note_id=14218138919
http://www.cnblogs.com/piaoger/archive/2012/08/19/2646530.html
http://essay.utwente.nl/59204/1/scriptie_J_Schipers.pdf
3. typeahead search/search suggestion,这个也常见
https://www.facebook.com/video/video.php?v=432864835468
问题在这个帖子里被讨论到,基本上每个问题,在视频里都有回答
http://www.mitbbs.com/article_t/JobHunting/32438927.html
4. Facebook Messaging System(有提到inbox search, which has been asked before)
messaging system就是一个把所有chat/sms/email之类的都结合起来的一个系统
http://www.infoq.com/presentations/HBase-at-Facebook
http://sites.computer.org/debull/A12june/facebook.pdf
http://www.slideshare.net/brizzzdotcom/facebook-messages-hbase/
https://www.youtube.com/watch?v=UaGINWPK068
5. 任给一个手机的位置信号(经纬度),需要返回附近5mile 的POI
这个这里有讨论,这题貌似nyc很爱考...
http://www.mitbbs.ca/article0/JobHunting/32476139_0.html
6. Implement second/minute/hour/day counters
这题真不觉得是system design,但万一问道,还是要有准备,貌似在总部面试会被问
道....
这个帖子有讨论
http://www.mitbbs.com/article_t/JobHunting/32458451.html
7. facebook photo storage,这个不太会被问起,但是知道也不错
https://www.usenix.org/legacy/event/osdi10/tech/full_papers/Beaver.pdf
https://www.facebook.com/note.php?note_id=76191543919
8. facebook timeline,这个也不太是个考题,看看就行了
https://www.facebook.com/note.php?note_id=10150468255628920
http://highscalability.com/blog/2012/1/23/facebook-timeline-bro
除了这些,准备一下这些题目
implement memcache
http://www.adayinthelifeof.nl/2011/02/06/memcache-internals/
implement tinyurl(以及distribute across multiple servers)
http://stackoverflow.com/questions/742013/how-to-code-a-url-sho
determine trending topics(twitter)
http://www.americanscientist.org/issues/pub/the-britney-spears-
http://www.michael-noll.com/blog/2013/01/18/implementing-real-t
copy one file to multiple servers
http://vimeo.com/11280885
稍微知道一下dynamo key value store,以及google的gfs和big table
另外推荐一些网站
http://highscalability.com/blog/category/facebook
这个high scalability上有很多讲system design的东西,不光是facebook的,没空的
话,就光看你要面试的那家就好了..
facebook engineering blog
http://www.quora.com/Facebook-Engineering/What-is-Facebooks-arc
http://stackoverflow.com/questions/3533948/facebook-architectur
其他家的
http://www.quora.com/What-are-the-top-startup-engineering-blogs
http://www.quora.com/What-are-best-practices-for-building-somet
http://www.infoq.com/presentations/Scale-at-Facebook
http://www.infoq.com/presentations/Facebook-Software-Stack
一般的followup question是估算需要多少server
另外这个帖子有讨论
http://www.mitbbs.ca/article_t/JobHunting/32463885.html
这篇文章稍微提到要怎么approach这种题,可以稍微看看
http://book.douban.com/reading/23757677/
2. facebook chat,这个也算是挺常问的
http://www.erlang-factory.com/upload/presentations/31/EugeneLet
https://www.facebook.com/note.php?note_id=14218138919
http://www.cnblogs.com/piaoger/archive/2012/08/19/2646530.html
http://essay.utwente.nl/59204/1/scriptie_J_Schipers.pdf
3. typeahead search/search suggestion,这个也常见
https://www.facebook.com/video/video.php?v=432864835468
问题在这个帖子里被讨论到,基本上每个问题,在视频里都有回答
http://www.mitbbs.com/article_t/JobHunting/32438927.html
4. Facebook Messaging System(有提到inbox search, which has been asked before)
messaging system就是一个把所有chat/sms/email之类的都结合起来的一个系统
http://www.infoq.com/presentations/HBase-at-Facebook
http://sites.computer.org/debull/A12june/facebook.pdf
http://www.slideshare.net/brizzzdotcom/facebook-messages-hbase/
https://www.youtube.com/watch?v=UaGINWPK068
5. 任给一个手机的位置信号(经纬度),需要返回附近5mile 的POI
这个这里有讨论,这题貌似nyc很爱考...
http://www.mitbbs.ca/article0/JobHunting/32476139_0.html
6. Implement second/minute/hour/day counters
这题真不觉得是system design,但万一问道,还是要有准备,貌似在总部面试会被问
道....
这个帖子有讨论
http://www.mitbbs.com/article_t/JobHunting/32458451.html
7. facebook photo storage,这个不太会被问起,但是知道也不错
https://www.usenix.org/legacy/event/osdi10/tech/full_papers/Beaver.pdf
https://www.facebook.com/note.php?note_id=76191543919
8. facebook timeline,这个也不太是个考题,看看就行了
https://www.facebook.com/note.php?note_id=10150468255628920
http://highscalability.com/blog/2012/1/23/facebook-timeline-bro
除了这些,准备一下这些题目
implement memcache
http://www.adayinthelifeof.nl/2011/02/06/memcache-internals/
implement tinyurl(以及distribute across multiple servers)
http://stackoverflow.com/questions/742013/how-to-code-a-url-sho
determine trending topics(twitter)
http://www.americanscientist.org/issues/pub/the-britney-spears-
http://www.michael-noll.com/blog/2013/01/18/implementing-real-t
copy one file to multiple servers
http://vimeo.com/11280885
稍微知道一下dynamo key value store,以及google的gfs和big table
另外推荐一些网站
http://highscalability.com/blog/category/facebook
这个high scalability上有很多讲system design的东西,不光是facebook的,没空的
话,就光看你要面试的那家就好了..
facebook engineering blog
http://www.quora.com/Facebook-Engineering/What-is-Facebooks-arc
http://stackoverflow.com/questions/3533948/facebook-architectur
其他家的
http://www.quora.com/What-are-the-top-startup-engineering-blogs
a) 首先你可以从整体上了解一下facebook的architecture
http://www.quora.com/Facebook-Engineering/What-is-Facebooks-arc
http://www.ece.lsu.edu/hpca-18/files/HPCA2012_Facebook_Keynote.
http://www.quora.com/Facebook-Engineering/What-have-been-Facebo
除了下面给出的一些资料,fb engineering page里还有很多不错的内容
https://www.facebook.com/Engineering
b) news feed
这里有个talk
http://www.infoq.com/presentations/Facebook-News-Feed
对应的slides
http://readme.skplanet.com/wp-content/uploads/2012/11/0-3_Faceb
还有一些quora上的讨论
http://www.quora.com/Activity-Streams/What-are-the-scaling-issu
http://www.quora.com/What-are-best-practices-for-building-somet
http://www.quora.com/What-is-the-best-storage-solution-for-buil
c) facebook chat
这里有两个notes,其中第二个里面还有相应的tech talk links
https://www.facebook.com/notes/facebook-engineering/facebook-chat/
14218138919
https://www.facebook.com/notes/facebook-engineering/chat-stability-and-
scalability/51412338919
d) typeahead search & graph search
关于typeahead search的tech talk和notes
https://www.facebook.com/video/video.php?v=432864835468
https://www.facebook.com/note.php?note_id=365915113919
https://www.facebook.com/note.php?note_id=389105248919
关于graph search的paper, tech talk, notes。其中paper很值得一看。
http://db.disi.unitn.eu/pages/VLDBProgram/pdf/industry/p871-cur
https://newsroom.fb.com/Photos-and-B-Roll/4362/Graph-Search-Whiteboard
https://www.facebook.com/note.php?note_id=10151240856103920
https://www.facebook.com/note.php?note_id=10151347573598920
https://www.facebook.com/note.php?note_id=10151361720763920
https://www.facebook.com/note.php?note_id=10151432733048920
https://www.facebook.com/note.php?note_id=10151755593228920
e) facebook messages
两个tech talks
http://www.youtube.com/watch?v=XAuwAHWpzPc
http://www.infoq.com/presentations/HBase-at-Facebook
以及eng notes
https://www.facebook.com/note.php?note_id=10150148835363920
https://www.facebook.com/note.php?note_id=10150162742108920
f) photo storage
相关的papers和notes
https://www.usenix.org/conference/osdi10/finding-needle-haystack-facebooks-
photo-storage
https://www.usenix.org/legacy/events/osdi10/tech/full_papers/Beaver.pdf
https://www.usenix.org/legacy/events/osdi10/tech/slides/beaver.pdf
https://www.facebook.com/note.php?note_id=76191543919
g) social graph data store
相关的note, video, paper
https://www.facebook.com/notes/facebook-engineering/tao-the-power-of-the-
graph/10151525983993920
https://www.usenix.org/conference/atc13/technical-sessions/presentation/
bronson
http://www.cs.cmu.edu/~pavlo/courses/fall2013/static/papers/117
h) tiny URL
这里有一些讨论
http://n00tc0d3r.blogspot.com/2013/09/big-data-tinyurl.html
http://stackoverflow.com/questions/742013/how-to-code-a-url-sho
http://stackoverflow.com/questions/3376163/what-are-the-things-
i) POI
参考这里
http://www.slideshare.net/mmalone/scaling-gis-data-in-nonrelati
http://www.mitbbs.ca/article_t/JobHunting/32476139.html
http://www.quora.com/Facebook-Engineering/What-is-Facebooks-arc
http://www.ece.lsu.edu/hpca-18/files/HPCA2012_Facebook_Keynote.
http://www.quora.com/Facebook-Engineering/What-have-been-Facebo
除了下面给出的一些资料,fb engineering page里还有很多不错的内容
https://www.facebook.com/Engineering
b) news feed
这里有个talk
http://www.infoq.com/presentations/Facebook-News-Feed
对应的slides
http://readme.skplanet.com/wp-content/uploads/2012/11/0-3_Faceb
还有一些quora上的讨论
http://www.quora.com/Activity-Streams/What-are-the-scaling-issu
http://www.quora.com/What-are-best-practices-for-building-somet
http://www.quora.com/What-is-the-best-storage-solution-for-buil
c) facebook chat
这里有两个notes,其中第二个里面还有相应的tech talk links
https://www.facebook.com/notes/facebook-engineering/facebook-chat/
14218138919
https://www.facebook.com/notes/facebook-engineering/chat-stability-and-
scalability/51412338919
d) typeahead search & graph search
关于typeahead search的tech talk和notes
https://www.facebook.com/video/video.php?v=432864835468
https://www.facebook.com/note.php?note_id=365915113919
https://www.facebook.com/note.php?note_id=389105248919
关于graph search的paper, tech talk, notes。其中paper很值得一看。
http://db.disi.unitn.eu/pages/VLDBProgram/pdf/industry/p871-cur
https://newsroom.fb.com/Photos-and-B-Roll/4362/Graph-Search-Whiteboard
https://www.facebook.com/note.php?note_id=10151240856103920
https://www.facebook.com/note.php?note_id=10151347573598920
https://www.facebook.com/note.php?note_id=10151361720763920
https://www.facebook.com/note.php?note_id=10151432733048920
https://www.facebook.com/note.php?note_id=10151755593228920
e) facebook messages
两个tech talks
http://www.youtube.com/watch?v=XAuwAHWpzPc
http://www.infoq.com/presentations/HBase-at-Facebook
以及eng notes
https://www.facebook.com/note.php?note_id=10150148835363920
https://www.facebook.com/note.php?note_id=10150162742108920
f) photo storage
相关的papers和notes
https://www.usenix.org/conference/osdi10/finding-needle-haystack-facebooks-
photo-storage
https://www.usenix.org/legacy/events/osdi10/tech/full_papers/Beaver.pdf
https://www.usenix.org/legacy/events/osdi10/tech/slides/beaver.pdf
https://www.facebook.com/note.php?note_id=76191543919
g) social graph data store
相关的note, video, paper
https://www.facebook.com/notes/facebook-engineering/tao-the-power-of-the-
graph/10151525983993920
https://www.usenix.org/conference/atc13/technical-sessions/presentation/
bronson
http://www.cs.cmu.edu/~pavlo/courses/fall2013/static/papers/117
h) tiny URL
这里有一些讨论
http://n00tc0d3r.blogspot.com/2013/09/big-data-tinyurl.html
http://stackoverflow.com/questions/742013/how-to-code-a-url-sho
http://stackoverflow.com/questions/3376163/what-are-the-things-
i) POI
参考这里
http://www.slideshare.net/mmalone/scaling-gis-data-in-nonrelati
http://www.mitbbs.ca/article_t/JobHunting/32476139.html