系统设计准备

核心考察的是大流量下的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之类的都结合起来的一个系统