System Design Interview

先建立框架再逐步细化的方式翻译

从零到百万用户量

设计一个百万级用户的系统是有挑战的，并且这是个需要持续的精炼和无尽的改善的过程。在这一章中，我们构建一个支持一个用户的系统并且逐渐扩大规模到服务数百万用户。读完本章后，你将掌握一些可以帮助你破解系统设计面试问题的技巧。

单服务器

千里之行始于足下，构建一个复杂系统也是如此。先来一点简单的，所有东西都跑在单个服务器上。图1-1展示了一个所有东西跑在一个服务器上的单服务器架构图示，其中包括webapp,database,cache等。

image.png

搞清楚请求流程和流量来源对理解这种架构是有帮助的。我们首先来看请求流(图1-2)

image.png

1. 用户通过域名访问网站，比如api.mysite.com。通常Domain Name System(DNS)是由第三方付费提供，并且不是部署在我们的服务器上。
2. IP地址被返回到浏览器或者移动app上。在这里返回的地址是 15.125.23.214。
3. 一旦地址被获取到，HTTP请求会被直接发送到你的web服务器上。
4. web服务器返回HTML页面或者JSON响应用于渲染。

接下来我们来考察流量来源。你的web服务器的流量主要有两个来源: web应用和移动应用。

• web应用: 它组合了服务端语言(Java,Python等)用于处理业务逻辑和存储等，以及客户端语言(HTML和JavaScript)用于展示。

• 移动应用: HTTP协议是移动应用和web服务之间的通讯协议。JSON是常用的API响应数据的格式，因为它很简单。JSON格式的API响应的例子如下:
  GET /users/12 – Retrieve user object for id = 12

  
  
  image.png

数据库

随着用户群的增长，一个服务器已经不够了，我们需要多服务器：一个用于web/移动流量，另一个用于数据库(图1-3)。分离的web/移动流量(web层)和数据库(数据层)服务器可以让它们独立扩展。

image.png

选择哪种数据库?

你可以选择传统的关系型数据库和非关系型数据库。我们来考察下它们的不同之处。
关系型数据库也被成为一个关系型数据库管理系统(RDBMS)或者sql数据库。最流行的是MYSQL，Oracle数据库，PostgreSQL等。关系型数据库用行和列的方式表示和存储数据。你可以使用SQL在不同的数据表间执行交集操作。
非关系型数据库也被称为NoSQL数据库。流行的有CouchDB,Neo4j,Cassandra,HBase,Amazon DynamoDB等。这些数据库可以分为四类:key-value存储，图储存，列存储和文档存储。非关系型数据库一般不支持交集操作。
对于大多数的开发者来说，关系型数据库是最好的选择，因为它们已经超过40年的历史了，并且一直表现良好。然而，如果关系型数据库不适用于你的特殊的用例，在关系型数据库之外探索是很重要的。非关系型数据库可能是以下场景的好选择:

• 你的应用需要非常低的延迟。
• 你的数据是非结构性的或者你没有任何互相关联的数据。
• 你只需要序列化和反序列化数据(JSON,XML,YAML等)。
• 你需要存储海量的数据。

垂直扩展VS水平扩展

垂直扩展，也被叫做scale up。是指添加服务器性能(CPU,RAM等)的过程。水平扩展也叫scale-out,允许你通过添加更多的服务器到资源池中来扩展。
当流量小的时候，垂直扩展是一个比较好的选项，简单是垂直扩展的主要优势。不幸的是，它有严重的局限性。

• 垂直扩展有严格的限制。不可能无限的添加cpu和内存到一台服务器上。
• 垂直扩展没有故障切换和冗余机制。如果一个服务器宕机了，整个网站/app会完全故障。

对于大规模扩展的应用来说水平扩展更可取，因为垂直扩展有限制。

在之前的设计中，用户直接连接到web服务器。如果整个服务器下线了，用户就不能访问网站了。在另一个场景中，如果大量用户同时访问web服务器，达到了服务器的负载上限，用户通常会经历更慢的响应或者直接就不能连接到服务器。负载均衡器是处理这个问题的最好技术。

负载均衡器

负载均衡器在web服务器群直接均匀的分配进入的流量。图1-4展示了负载均衡器是如何工作的。

image.png

正如在图1-4中展示的，用户直接连接到负载均衡器的公网IP。这样设置后，web服务器就不能直接接触到web服务器了。为了更好的安全性，服务器之间使用私有IP通信。私有IP只有在同一个网络的服务器之间是可达的，跨网络不可达。负载均衡器和web服务器通过私有IP通信。
在图1-4中，在负载均衡器之后，又一个web服务器被添加了，我们成功解决了没有故障切换的问题并且提高了web层的可用性。细节如下:

• 如果服务器1下线了，所有的流量会被路由到服务器2。这防止了网站的下线。我们将可以添加一个新的健康的web服务器到服务器池中均衡负载。
• 如果网站流量急剧增长，两个服务器不足以应对，负载均衡器可以优雅的解决这个问题。你只需要添加更多的服务器到服务器池，负载均衡器自动的将请求发给它们。

现在web层看起来还不错，那数据层呢？目前的设计有一个数据库，所以ta不支持故障转移和冗余机制。数据库备份是常见的解决这个问题的技术。

数据库备份

维基解密的解释是““Database replication can be used in many database management systems, usually with a master/slave relationship between the original (master) and the copies (slaves)” 数据库备份可以被用在多数据库管理系统， 通常是有主/从关系在原始数据库和备份数据库之间。
一个主数据库通常只支持写入操作。从数据库获取从主数据库而来的备份并且只支持读操作。所有的数据修改操作，比如增删改都必须被发送给主数据库。相对于写操作，大部分的系统需要非常高的读操作。因此从数据库的数量通常比主数据库多。图1-5展示了一主多从的结构。

image.png

数据库备份机制的优点:

• 更好的性能： 在主从模型中，所有的写和更新发生在主节点，读操作分布在从节点。这样就处理更多的并行查询操作，从而提高性能。
• 可靠性：如果你的一个数据库服务器被自然灾害摧毁了，比如台风或者地震，数据仍然保留着。你不需要担心数据丢失，因为数据是被分在多个地方。
• 高可用性：通过备份数据在不同的地方，你的网站保持可操作。即使一个数据库下线了，也可以访问存在其他地方的数据库服务器。

之前的章节中，我们讨论了负载均衡器是如何提高系统的可用性的。这里我们同样发问：如果其中一个数据库下线会怎样? 图1-5中讨论的架构设计可以处理这样的情况：

• 如果只有一个从数据库可用，并且下线了，读操作会被暂时转到主数据库。这种情况一旦发生，一个新的从数据库会替代旧的那个。在多个从数据库的情况下，读操作被重发到其他的健康的从数据库。也会启一个新从数据库替代之前的。
• 如果主数据库下线，一个从数据库会被提升为新的主数据库。所有的数据库操作会被暂时执行在新的主数据库。一个新的从属数据库将取代旧数据库，以便立即进行数据复制。在生产系统中，提升数据库为主数据库是比较复杂的，因为从数据库中的数据可能不是最新的。丢失的数据需要通过数据恢复脚本更新。虽然其他的备份方法，比如多主和循环复制也有用，但是这些方法更复杂，此书暂不讨论。有兴趣可以查看...

图1-6展示了添加负载均衡和数据库备份后的系统设计。

image.png

如下：

• 用户从DNS获取到负载均衡器的IP
• 用户和负载均衡器IP建立连接
• HTTP请求被路由到服务器1或者服务器2
• web服务器从一个从数据库读取数据
• web服务器路由任何数据修改操作到主数据库。包括增删改。

现在你已经对web和数据层有了扎实的理解，是时候改善下加载/响应时间了。这可以通过添加缓存层和更换静态内容(JavaScript/CSS/image/video files)到CDN。

缓存

缓存是一块存储昂贵(时间)响应或者频繁访问的数据结果的暂时的内存区域，缓存有利于后续请求更快的处理。如图1-6中说明的，每次新的网页加载，一个或者更多的数据库调用就被执行来获取数据。应用的性能受重复的数据库调用影响很大。缓存可以缓解这个问题。

缓存层

缓存层是一个暂存数据存储层，一定要比数据库快。有分离的缓存层的好处包括更好的系统性能，减少数据库负载的能力和独立扩展缓存层的能力。图1-7展示了一种可能的缓存服务器设置方式：

image.png

收到请求后，web服务器首先检查缓存中有没有可用的响应。如果有就返回，如果没有就查询数据库，把响应存到缓存中，然后返回给客户端。这种缓存策略被称为read-through缓存。其他的缓存策略也可以选用，但是要取决于数据的类型，大小和访问模式。有一项研究解释了不同的缓存策略是如何工作的[6]。

和缓存服务器的交互是很简单的，因为大部分的缓存服务器都提供了API给常见的编程语言。下面的代码段展示了典型的API:

image.png

使用缓存的考虑

• 决定什么时候使用缓存。数据是被访问很频繁修改不频繁时考虑使用缓存。因为缓存数据是存在易失的内存中的，对于存储持久性的数据来说缓存并不理想。比如，如果服务器重启了，内存中所有数据都会丢失。因此，重要的数据应该被被持久化存储。
• 过期策略：实现过期策略是一个比较好的实践。一旦数据过期了，就从缓存中将它去掉。如果没有过期策略，数据就会一直存在缓存里面。建议过期时间不要设置的太短，这样会导致太频繁的从数据库重载数据。也不要设置的太长，这样数据会变得陈旧。
• 数据一致性： 这关系到保持数据存储和缓存的同步。不一致可能是不在同一个事务中的修改缓存和数据库数据操作导致的。在跨越不同区域的尺度上，保持数据存储和缓存的一致性是具有挑战性的。更多的细节可以参考Facebook的书“Scaling Memcache at Facebook”[7]。

• 降低故障率: 一个单缓存服务器意味着潜在的单点故障(SPOF)，维基中的定义是“A single point of failure (SPOF) is a part of a system that, if it fails, will stop the entire system from working”，单点故障是系统中的某部分，如果这部分故障了，会使整个系统不能工作[8]。所以建议使用跨数据中心得多缓存服务器来避免单点故障。另一个推荐得方法是按一定比例提供过量的内存。在内存使用量升高的时候提供缓冲。

  
  
  image.png
• 驱逐策略：一旦缓存满了，任何添加数据的请求可能会移除缓存中已有的数据。这就是缓存驱逐，最近最少使用(LRU)是最常见的内存驱逐策略。其他策略，比如最不常用法(LFU)或者先进先出(FIFO)，都可以适用不同的场景。

内容分发网络(CDN)

CDN是地理上分散的用于分发静态内容的服务器网络。CDN服务器缓存像图片，视频，CSS，JS文件等静态内容。

动态内容缓存是一个与此相关的新概念不过不在本书的讨论范围。它可以基于缓存请求路径，查询字符串，cookies以及请求头缓存HTML页面。查询[9]中的文章获取更多。本书关注如何适用CDN缓存静态内容。

以下是CDN整体上如何工作的：当用户访问一个网页，一个靠用户最近的CDN服务器会发送静态内容。可以想到，离CDN服务器越远，网页加载越慢。比如，如果CDN服务器在旧金山，洛杉矶的用户会比在欧洲的用户获取内容更快。图1-9较好的展示了CDN如何降低加载时间。

image.png

图1-10表明了CDN的工作流。

image.png

1. A用户尝试通过图像URL获取image.png，URL的域名是CDN提供的。下面两个例子展示了Amazon和Akamai CDN的图像URL的样子：

• https://mysite.cloudfront.net/logo.jpg
• https://mysite.akamai.com/image-manager/img/logo.jpg

2. 如果CDN服务器没有image.png，就会从源头请求文件，可能是web服务器或者像S3一样的在线存储。
3. 文件源返回image.png给CDN服务器，HTTP可选头中会包括描述图像需要被缓存多久的TTL。
4. CDN缓存图像并且返回给用户A。并且图片在CDN中存留到TTL过期。
5. 用户B发送请求获取同样的图片。
6. 只要TTL没有过期就从缓存中获取。

CDN需要考虑的点

• 花销：CDN是由第三方运营的。你是按照进出的数据量收费的。缓存不常用的数据没有多大好处，所以你应该考虑将他们移出CDN。
• 设置一个合适的缓存时间：对于时间敏感的内容，设置缓存过期时间很重要。过期时间不能太长或太短。太长会导致内容不新鲜。太短会导致重复地从源服务器的重载。
• CDN应急计划：你应该考虑你的网站/应用如何应对CDN失效。如果CDN发生了短暂的停机，客户端应该能够检测到这个问题并且直接从源头请求到资源。

• 失效文件：你可以通过以下操作在文件过期前就移除它们：
  - 通过CDN供应商提供的API移除CDN对象。
  - 使用版本化的对象来提供对象的不同版本 你可以在URL添加一个参数，比如版本号。加入到查询串中：image.png?v=2。
  图1-11 展示了添加了CDN和缓存之后的样子。

  
  
  image.png

1. 静态对象(JS,CSS,image等)不在从web服务器获取。从CDN获取得到了更好的性能。
2. 数据库加载操作被缓存减少了。

无状态网络层

是时候考虑

状态架构

数据中心

消息队列

日志，指标，自动化

添加消息队列和不同的工具

数据库扩展

水平扩展

垂直扩展

百万级用户及以上

引用

信封背面估计法

“A back-of-the-envelope calculation is a rough calculation, typically jotted down on any available scrap of paper such as an envelope. It is more than a guess but less than an accurate calculation or mathematical proof. The defining characteristic of back-of-the-envelope calculations is the use of simplified assumptions.”

2的幂

每个程序员需要知道的延迟

可用性数字指标

例子：估计推特QPS和存储要求

提示

引用

系统设计面试的框架

高效系统设计面试的四步法

第一步：理解问题和建立设计范围

第二步：提出高级设计并获得buy-in(认可?)

第三步：深入分析设计

第四步：包装

要做的

不要做的

每一步的时间分配

设计一个限流器

关键词： 哪里放置限流器，限流算法，令牌桶算法，漏桶算法，固定窗口计数法，滑动窗口对数法，滑动窗口计数法，限流规则，超过限流，限流器头，分布式环境下的限流器，竞态条件，同步问题，性能优化，监控，

设计一致性hash

关键词：rehashing问题，hash空间，hash环，hash服务器，hash key，添加服务器，移除服务器，虚拟节点，找到受影响的key。

设计key-value存储

关键词：单服务器key-value存储，分布式key-value存储，CAP理论，理想情况，现实情况，系统组件， 数据分区，自动扩展，不均匀性，数据备份，一致性，一致性模型，不一致方案：版本，出错处理，错误检测，处理临时错误，处理数据中心停电，写路径，读路径

设计分布式唯一ID生成器

关键词：多主复制，UUID，发号服务器，推特雪花算法，序列号。

设计短链系统

关键词：api终端，URL重定向，URL缩短，数据模型，Hash函数，Hash长度，碰撞解决，Base62转换。

设计网络爬虫

关键词：种子URLs, URL边界，HTML下载器，DNS解析器，内容解析器，内容可见？，内容存储，URL提取器，URL过滤器，URL可见？，URL存储，网络爬虫工作流，DFS vs BFS，Politeness，优先级，新鲜度，分布式爬取，缓存DNS解析，地理位置，短时超时，稳健性，扩展性，检测和避免问题内容，冗余的内容，蜘蛛困境，数据噪声。

设计通知系统

关键词：IOS推送，安卓推送，SMS推送，Email，联系人信息收集流，通知发送/接受流，推送服务器，可靠性，如何防止数据丢失，如何只接受一次推送，推送模板，通知设置，限流，重试，安全性，监控推送队列，事件追踪。

设计新闻流系统

关键词：新闻源API，推送发布API，新闻提要API，源推送，web服务器，扇出服务，扇入服务，写入时扇出，读时扇出，缓存架构。

设计聊天系统

关键词： 轮询，长轮询，WebSocket，无状态服务，有状态服务，第三方集成，可扩展性，存储，数据模型，1v1聊天，聊天群，服务发现，消息流，1v1聊天流，多设备消息同步，小群聊天流，在线状态，用户登录，用户登出，用户断线，在线状态扇出。

设计搜索自动补全系统

关键词：数据采集服务，查询服务，字典树数据结构，限制最大长度前缀，每个节点缓存最多查询，分析日志，聚合器，聚合数据，Worker，字典缓存，字典数据库，查询服务，树操作，增删改，存储扩展。

设计Youtube

关键词：客户端，CDN，API服务器，视频上传流，上传实际视频，更新元数据，视频流，视频转码，有向无环图模型，视频转码架构，预处理器，有向无环图调度，资源管理器，任务worker，零时存储，编码视频，并行上传视频，靠近用户的上传中心，处处并行，预签名上传URL，保护视频，成本优化，错误处理。

设计谷歌云盘

关键词：上传文件到谷歌云盘，下载文件，后去文件修订，同步冲突，分块服务器，云存储，冷藏，负载均衡，元数据数据库，元数据缓存，下线备份队列，高一致性要求，文件版本，上传流，下载流，通知服务，节约存储空间，出错处理。

持续学习

• Back of the envelope estimationbo
• A framework for system design interviews
• Rate limiter
• Consistent hashing
• Key value store
• Unique id generator in distributed systems
• Url shortener
• Web crawler
• Notification system
• News feed system
• Chat system
• Search autocomplete system