系统设计典型问题的思考

2015-04-19 09:54


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

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

  • 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)

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

(题图来自:raintecirrigationsystems.com)