系统设计资源

核心考察的是大流量下的distributed backend service design。因为这几家都是大公司，面对的都是每天至少billion级别的request，因此需要对这个场景的design有深刻认识。而design的核心思路就是trade-off。每个方案都不是十全十美的，比较postive的应对是：可以给出多种方案，在给出每种方案时，同时给出该方案的优点和缺点，并结合我们正在讨论的设计场景（给定的约束条件下），做出该方案好坏的点评，并最终选择一种"最适合"的方案。模板套路大致为：

user case：和面试官讨论该系统需要实现什么功能，大部分设计都需要实现"读"和"写"两个基本功能。这样就确定了功能边界。（避免你和面试官聊high了想出很多新功能，从而偏题）
system constraint：和面试官明确max requests/day, QPS, storage size, latency，availability等基本系统约束。也有可能面试官不会给你，而是让你估算，比如面试官会说，如果这个是Facebook主页上的feature，你就需要结合Facebook本身的traffic, active user等数值进行估算（这就要求对各家的这些number要有大概认知）。这一部分是确定性能边界，也会决定你的设计框架。
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保证所有数据不会丢失。
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(功能边界和系统约束），选择最适合的方案。
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上的高人总结帖================
入门级的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
typeahead search/search suggestion，这个也常见 https://www.facebook.com/video/video.php?v=432864835468 问题在这个帖子里被讨论到，基本上每个问题，在视频里都有回答 http://www.mitbbs.com/article_t/JobHunting/32438927.html
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
任给一个手机的位置信号(经纬度)，需要返回附近5mile 的POI 这个这里有讨论，这题貌似nyc很爱考… http://www.mitbbs.ca/article0/JobHunting/32476139_0.html
Implement second/minute/hour/day counters 这题真不觉得是system design，但万一问道，还是要有准备，貌似在总部面试会被问道…. 这个帖子有讨论 http://www.mitbbs.com/article_t/JobHunting/32458451.html
facebook photo storage，这个不太会被问起，但是知道也不错 https://www.usenix.org/legacy/event/osdi10/tech/full_papers/Beaver.pdf https://www.facebook.com/note.php?note_id=76191543919
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

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