Skip to main content

系统设计准备

http://gengwg.blogspot.com/核心考察的是大流量下的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(功能边界和系统约束),选择最适合的方案。

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一类的题目)
一些常见面试题目,mitbbs上已经有高人进行了全面总结,我会转载贴在下面,我基本上是follow之。这里有一点补充:

tinyurl一定要非常充分的准备。我在F,L,G三家面试时都被问到了这题。这题看似简单,其实可以将上面讨论的大部分东西多装进来,可以讨论的地方很多。

这道题我觉得很有价值的文章:

http://n00tc0d3r.blogspot.jp/2013/09/big-data-tinyurl.html

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

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

Comments

Popular posts from this blog

CKA Simulator Kubernetes 1.22

  https://killer.sh Pre Setup Once you've gained access to your terminal it might be wise to spend ~1 minute to setup your environment. You could set these: alias k = kubectl                         # will already be pre-configured export do = "--dry-run=client -o yaml"     # k get pod x $do export now = "--force --grace-period 0"   # k delete pod x $now Vim To make vim use 2 spaces for a tab edit ~/.vimrc to contain: set tabstop=2 set expandtab set shiftwidth=2 More setup suggestions are in the tips section .     Question 1 | Contexts Task weight: 1%   You have access to multiple clusters from your main terminal through kubectl contexts. Write all those context names into /opt/course/1/contexts . Next write a command to display the current context into /opt/course/1/context_default_kubectl.sh , the command should use kubectl . Finally write a second command doing the same thing into /opt/course/1/context_default_no_kubectl.sh , but without the use of k

OWASP Top 10 Threats and Mitigations Exam - Single Select

Last updated 4 Aug 11 Course Title: OWASP Top 10 Threats and Mitigation Exam Questions - Single Select 1) Which of the following consequences is most likely to occur due to an injection attack? Spoofing Cross-site request forgery Denial of service   Correct Insecure direct object references 2) Your application is created using a language that does not support a clear distinction between code and data. Which vulnerability is most likely to occur in your application? Injection   Correct Insecure direct object references Failure to restrict URL access Insufficient transport layer protection 3) Which of the following scenarios is most likely to cause an injection attack? Unvalidated input is embedded in an instruction stream.   Correct Unvalidated input can be distinguished from valid instructions. A Web application does not validate a client’s access to a resource. A Web action performs an operation on behalf of the user without checking a shared sec