码农翻墙去美帝 ―― 系统设计准备 | ITint5

码农翻墙去美帝 ―― 系统设计准备 | 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(功能边界和系统约束），选择最适合的方案。

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之。这里有一点补充：

 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

Read full article from 码农翻墙去美帝 ―― 系统设计准备 | ITint5