系统设计典型问题的思考

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

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

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

在此基础上，考虑最基础的组件和架构划分，整个系统要分几层，有哪些组件，各自什么作用，可能的瓶颈是什么等等。还有前面的 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 怎么权衡？可以牺牲掉哪一个？
如果要求完成历史消息功能，那又是另一番故事了。其他值得讨论的扩展的功能包括系统消息群发、好友状态更新和消息搜索等等。

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