System Design Interview Misc

http://meetqun.com/thread-11634-1-1.html
系统设计知识考察点
比如面向对象，接口设计，设计模式，数据库表，分布式。

首先在性能耗在什么地方之前不要优化。所谓杞人忧天，你不是百度或者facebook的流量，根本考虑不到很多细节，大多数直接用云计算平台，直接帮你做了。但面试中还是会考察

这里就针对Scalability，有一些常见的优化技术，我就把他们列出。

Cache：缓存，万金油，哪里不行优先考虑
Queue：消息队列，常见使用Linkedin的kafka
Asynchronized：批处理＋异步，减少系统IO瓶颈
Load Balance: 负载均衡，可以使用一致性hash技术做到尽量少的数据迁移
Parallelization：并行计算，比如MapReduce
Replication：提高可靠性，如HDFS，基于位置感知的多块拷贝
Partition：数据库sharding，通过hash取摸


http://dongfei.baijia.baidu.com/article/52449

问题：对于初级程序员的面试，最难的部分可能就是所谓的设计题。这部分是什么流程？

设计题可以分成两个部分，系统架构设计和利用面向对象编程原理进行程序设计。前者所涉及的技术往往包括数据库，并发处理和分布式系统等等，对于经验要求和知识要求比较高。系统面试的流程如下:

1. 题目描述

往往非常简单，如：设计一个XX系统。 或者：你有没有用过XXX，给你看一下什么界面和功能，你来设计一个。

2. 阐述题意

面试者需向面试官询问系统的具体要求。如，需要什么功能，需要承受的流量大小，是否需要考虑可靠性，容错性等等。

3. 面试者提供一个初步的系统设计

4. 面试官这对初步的系统中提出一些Follow-Up的问题：如果要加某个功能怎么办，如果流量大了怎么办，如何考虑Consistent怎么办，如果机器挂了怎么办。

5. 面试者根据面试官的Follow Up逐个解决问题

总体特点是以交流为主，画图和代码为辅。

问题：从面试官的角度给出一些系统设计上的考量标准是什么？

我先给一个内部培训面试官的方法，大致说了考量环节。根据我的经验，也列出一些关注点

Adapt to the changing requirements （适应变化的需求）

Produce a system that is clean, elegant, well thought （设计干净，优美，考虑周到的系统）

Explain why you choose this implementation （解释为何这么实现）

Be familiar with your experience level to make decisions （对自己的能力水平很熟练）

Answer in high level of scale and complexity （在一些高层结构和复杂性方面有设计）

其实大家大可不必追求完美，在真正的面试中，没有人能对答如流，往往面试官也会给出善意的提示，就算你没回答某个子问题，在面试后的评价中也会综合衡量，跟其他的面试者比较，最终打出一个分数。很多人在2到3分左右，目标是尽量在3分以上。

http://www.raychase.net/3165

作为系统设计学习的一部分，不久前在梳理面试中典型的系统设计问题，发现大部分都可谓有套路可寻。我把思路梳理了一下，简单整理到下面这张图表里面：

对于其中的内容，稍微补充几句：

• 系统设计需要经验的积累，但也确确实实有章可循。问的问题考察的类型很集中，比如同步、异步，消息push和pull，根据实际问题设计存储的数据结构，对于scalability、availability的认识等等。最喜欢被问到的问题，我在《系统设计典型问题的思考》这里列了几个。
• pull on demand 和 push on change 是消息系统里两种极其典型的消息传播方式，基本上设计twitter、weibo，xx聊天系统等等，都要涉及到这个问题。这二者各有优劣，需要结合具体问题分析。
• 复杂的系统的cache的设计和storage的设计一样，往往需要考虑分层。比如说，存储分成hot/warm/cold storage，读写性能和查询的灵活性依次降低，但是成本也依次降低。cache的设计有时还需要引入centralized cache来帮助提高hit ratio。
• 服务端的设计最典型的就是分成三层（上图右）：presentation layer，比如website的页面部分和service的request/response处理的部分，它可能叫做front-end layer更好一点；business logic layer，放置业务逻辑的地方；data access layer，也可以说infrastructure layer，数据访问层，花头最多，涉及的问题最多。
• DB partition 和 sharding 的问题又是一个非常常见的典型。
• 如果是性能问题，基本上都是围绕着throughput和latency展开的。
• 一致性要出问题，一定要满足两个条件，一个是节点必须是有状态的，另一个是数据必须有冗余。而我们在讨论storage的时候，第一个条件一定满足；而对于第二个条件的满足，下一条目说明。
• 一致性模型可以说是大数据系统问题的核心。而availability既包括服务的可用性，又包括数据的可靠性。二者关系紧密。比如说考虑到availability，对于有状态的节点需要有backup，那么这几个节点状态之间的同步就会成为问题，这就是consistency的问题；再比如说由于考虑到reliability，必然需要引入replication，而这时多个数据备份的consistency就会成为问题。
• 读写模型的问题往往是和存储数据结构的设计放在一起的，这样的问题很容易从算法问题衍伸过来，我在这篇文章中总结过。
• 对于前端和部分CS或BS交互的要点和优化，这里没有列出来，几年前整理过，部分内容可以参考这篇文章。
• 最后，我在《资源链接》的“零散资源”部分，列出了系统设计很多我认为有价值的参考材料。

系统设计典型问题的思考

系统设计方面的问题问题是非常考验经验和思维过程的，而且和常见的算法问题、语言基础问题不同，涉及的面很广，还没有比较一致的判别标准。但无论如何，还是可以归纳一些常见的思路和典型问题的线索。

首先，反复沟通和澄清系统需求。只有把需求澄清清楚了，才可以开始思考并落到纸面上。但是需求的沟通应该是持续和循序渐进的，问题很难从一开始就思考全面。最重要的条目包括：

• use cases，通常问题只需要2~3个use cases需要考虑，其他的部分会晚些考虑，或者不考虑。这样就可以简化问题。
• 用户数量（用户可以是下游系统或者人）、数据数量，澄清这个事实无疑非常重要，对系统设计的决策有重大意义。
• 请求模型，比如读远大于写，比如60%的请求都访问top 20的记录。

其次，尝试抽象一个简单的模型，从简单模型开始，思考不同的场景和约束，逐步完善。落实到代码上的时候，最核心的部分包括：

• 模型的定义。
• 代码接口，API。
• 数据是怎样被存储的，比如表结构和文件结构。

在此基础上，考虑最基础的组件和架构划分，整个系统要分几层，有哪些组件，各自什么作用，可能的瓶颈是什么等等。还有前面的API、模型分别被安插到哪部分上面，同时反复比较第一步的几个use case是否都被满足。

再次，细化层结构和组件，比如：

• 存储层。是否需要持久化存储？选择文件、关系数据库，还是NoSQL数据库？
  • 如果选择关系数据库，是否需要sharding或partition？参考Quora：What’s the difference between sharding and partition?
  • 如果选择NoSQL数据库，CAP中分别牺牲和优先保证哪一个？参考：Visual Guide to NoSQL System。扩容的策略（比如一致性hash）？
  • 存储是否需要分层（比如冷层——文件、暖层——关系型数据库、热层——缓存，不同成本的存储介质，用以应付不同的数据访问频率）？
• 集群。所有节点对等还是中心节点主备？请求负载分担的策略？如何增减节点？如何判定节点健康状况？是否需要会话？会话如何同步？Scale up和Scale out的区别，参考Wikipedia：Scalability。
• 消息模型。生产者和消费者的速率？无法应付时是否需要缓冲队列？消息流量控制？速率控制的精细度？
• 缓存系统。缓存的分层？分布式部署还是集中式缓存服务？使用什么缓存淘汰算法（比如LRU）？参考：In-Process Caching vs. Distributed Caching。

其中，系统瓶颈的识别和scale是紧密联系着的两个话题。在需求驱使的基础上着手优化，比如缓存的应用，这需要建立在系统瓶颈被识别或者假定被识别的基础上，否则就是乱枪打鸟。在瓶颈解决之后再考虑scale。

最后，不断讨论和完善，每一个讨论迭代都要得出一个实际的结论，避免持续停留在过高抽象层面。这里涉及的部分可以很多，包括可扩展性、数据规模、吞吐量、可维护性、实时性、数据一致性等等。

所以，归纳起来的四部分为，先从系统外部理清楚需求，接着设计核心模型和API，再进行基本的分层和组件划分，最后才是细化每一层或者每个组件的设计。从外到内，逐层剖析。

这些点说起来容易做起来难，通过反复阅读和思考一些常见的系统设计场景，其实我们还是可以从中总结出若干规律来。

下面列出几个非常常见和典型的系统设计问题的hints：

1、怎样设计一个微博/Twitter系统（news feed系统）

• 思考读写模型，latency上看明显是读的要求明显高于写的模式。
• 转发和回复，拷贝原微博文字还是存储转发/回复树形关系？分析利弊。另外，这里涉及到产品设计，参见：Twitter Vs. Weibo: 8 Things Twitter Can Learn From The Latter。
• 区分两种典型消息传播的触发方式：push on change和pull on demand，两种方式利弊明显。参考：Why Are Facebook, Digg, And Twitter So Hard To Scale?
• 存储分级。这里CAP中A最为重要，往往C可以被牺牲，达到最终一致性。
• 缓存设计，分层的数据流动？如何识别热门？
• 删除微博功能的设计。

2、怎样设计一个短网址映射系统（tiny url系统）

• 思考读写模型，明显是读优先级高于写的服务，但是通常不需要修改。读写服务分离，在写服务崩溃时保证读服务健康运行。
• 链接缩短使用的加密和映射的方式中，算法如何选择？短链接可以接受那些字符？此处可以估算特定的规则下长度为n的短链接最多可能表示多少种实际链接。
• 如果使用统一的短链接序列分配机制，如何分布式设计这个分配逻辑？它不能够成为瓶颈。例如，一种常见的思路是让关系数据库的自增长索引给出唯一id，但是如果不使用关系数据库，在分布式系统中如何产生唯一序列号且避免冲突？参考：如何在高并发分布式系统中生成全局唯一Id。
• 是否需要保留原始链接最后部分？如http://abc.def.com/p/124/article/12306.html压缩成http://short.url/asdfasdf/12306.html，以增加可读性。
• 由于协议部分可以预见或者需要支持的数量很少（比如就支持http和https），是否可以考虑把协议部分略去，以枚举方式和短链接正文放在一起？
• 由于属于web服务，考虑判定URL合法性，考虑怎样控制请求流量和应对恶意访问。

3、怎样设计一个实时聊天系统？可以是MSN、QQ这样的CS结构的，也可以是Facebook Chat或者微博私信这样的BS结构的。

• 登陆时需要获取好友状态列表，这通常也是priority 0的use case。
• 这个问题的特点是客户端和服务端已经天然地分开了，核心问题之一是把服务端和客户端的交互梳理清楚。如果是BS结构的，怎样使得从服务端到客户端的消息推送成为可能？Ajax+Comet是一个办法，hang住连接，消息推送。还有一种办法是客户端轮询，但是显然实时性无法胜任。
• 如果使用Comet，服务端将存在大量的空闲连接。参考，select、poll、epoll之间的区别总结[整理]。对于消息的处理，引入协程，减少线程调度开销，参考：Difference between a “coroutine” and a “thread”?。
• 如果是CS的，消息和状态还可以通过P2P的方式；但是如果是BS的，就必须实现一个服务端的消息系统，参考：实时通信协议XMPP。
• 存储方面，CAP怎么权衡？可以牺牲掉哪一个？
• 如果要求完成历史消息功能，那又是另一番故事了。其他值得讨论的扩展的功能包括系统消息群发、好友状态更新和消息搜索等等。

还有一些系统设计典型和经典问题，想到的先列在下面，等后续有时间总结了再补充到上面去：

• 搜索引擎设计（包括网页爬虫）
• 邮件系统设计（例如GMail）

无论如何，对于这些问题的解决，反复思考是非常有趣的。这些东西貌似可以直接拿来学习的材料比较少，而且也不像算法那样丁是丁卯是卯的，评判的标准模糊得很。

http://www.raychase.net/730

1. DAO接口和实现全部都要开发人员自己实现；
2. 抽象出部分共同的基础增删改查方法不需要实现；
3. 将所有实现全部约束到同一个DAOImpl中，开发人员只需要实现各个模型的DAO接口。

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=118547&extra=page%3D1%26filter%3Dtypeid%26typeid%3D200%26typeid%3D200
https://www.evernote.com/shard/s576/sh/7e58b450-1abe-43a8-bf82-fbf07f1db13c/049802174415b418a2e65f75
Palantir 的官方说法 中文版http://t.cn/RAutUUi 英文版http://t.cn/RAut4gF

http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=77556&extra=page%3D1%26filter%3Dtypeid%26typeid%3D200%26typeid%3D200
可以看一些design pattern的书比如Design Patterns: Elements of Reusable Object-Oriented Software（我们上课用的这本）
关于系统设计，这个其实很看积累的，system本来就是考功底的地方，如果没时间上一些system的课(os, distributed system什么的），可以抽空去看下这些课的slides
另外读一些现在很成熟系统或者nosql的paper，比如
Google旧三驾马车 BigTable, GFS, MapReduce, Amazon的dynamo DB等等
最后极力推荐去看一下Google码农之神Jeff Dean的一些关于large scale system design的talk，给几个链接
http://static.googleusercontent. ... anford-295-talk.pdf
http://www.cs.cornell.edu/projec ... ynote-ladis2009.pdf

http://www.jiuzhang.com/qa/262/
Given a flat text file that contains a range of IP addresses that map to a location (e.g. 192.168.0.0-192.168.0.255 = Boston, MA), come up with an algorithm that will find a city for a specific ip address if a mapping exists.

Trie
http://www.jiuzhang.com/qa/214/
1，设计百度新闻搜索实时(1分钟)最热词

1,news大概一天1亿pv，假设1%的pv比例会搜query，大概100w次搜索
qps = 100w/86400 = 12qps
高峰使用时段大概 12qps * 100 = 1200qps
10台机器能稳定地抗住检索

那么一分钟也就72000 query，假设每次query都是不同的词，一次不会超过10个汉字，30个Byte，72000大概216KB构成KEY。

可以用一个hash(key=query, value=Queue)存query，设置crontab定时每一分钟去离线分析一下hash里那些key的count比较大，排个序【这样展示给用户的是伪实时1分钟了，并不是当前时间点往前推一分钟，如果要完全实时，估计要用top k loosy count了】。

因为我们知道1200qps，所以Queue平均下来是没多大的。内存完全放得下。

Queue里只记录timestamp，【time1, time2,...timek】 当time k+1 来时，队列头的time如果已超过一分钟，出队列。

2，我们有一些反动，黄色相关的词表，如果过滤百度文库找出那些有问题的文章

2， 假设词表大小是K（大概1w），每个词条平均长度10，文章长度是N。如果用KMP的吧
需要 K(10+N) 次比较，才能用所有词条对对一篇文章进行检查。代价略高

所以考虑把词表做成trie树，1w * 10 * 3B = 300KB 300KB * 3 ~= 1MB 就足够做成Trie树放内存中

Trie每次最多10次比较I就能找到敏感词。 所以最坏的情况下 10 * N

KMP是 KN + 10K, K是1w左右，远大于10.

所以Trie树在效率和生产环境都非常实用