# 前言 我们很高兴您决定加入我们学习系统设计面试。系统设计面试问题是所有技术问题中最难解决的面试。这些问题要求受访者设计软件的体系结构系统，可以是新闻源、谷歌搜索、聊天系统等。这些问题是令人生畏，而且没有特定的模式可循。问题通常很大范围广泛且模糊。流程是开放式的，不明确，没有标准或正确 答复。 公司广泛采用系统设计面试，因为在这些面试中测试的沟通和解决问题的技能与软件工程师的日常工作要求相似。根据受访者如何分析一个模糊的问题以及她如何一步一步地解决这个问题。测试的能力还包括她如何解释想法，与他人讨论，并对系统进行评估和优化。在英语中，使用“she”比“他或她”或在两者之间跳跃更流畅。为了使阅读更容易，我们使用贯穿本书的女性代词。并非有意不尊重男性工程师。 系统设计问题是开放式的。就像在现实世界中一样，有很多系统中的差异和变化。期望的结果是提出一个架构以实现系统设计目标。讨论可能会以不同的方式进行 取决于面试官。一些面试官可能会选择高级架构进行面试各方面；而有些人可能会选择一个或多个领域来关注。通常应充分理解需求、限制和瓶颈，以确定 面试官和被面试者。 本书的目的是提供一种可靠的策略来进行系统设计问题。正确的策略和知识对面试的成功至关重要。 这本书提供了构建可扩展系统的坚实知识。知识越多从阅读这本书中获得的经验，你在解决系统设计方面的问题时就越有能力。 本书还提供了一个关于如何解决系统设计问题的循序渐进的框架。它提供了许多例子来说明系统化的方法，并提供了详细的步骤可以跟随。通过不断的练习，您将具备应对系统设计的能力面试问题。 # 第 1 章：从零到百万用户规模 设计一个支持数百万用户的系统是一项挑战，这是一个需要不断改进和无尽改进的旅程。在本章中，我们构建了一个支持单个用户的系统，并逐步扩大其服务于数百万用户。在阅读完本章之后，您将掌握一些技巧，这将帮助您破解系统设计的面试问题。 ## 单服务器设置 千里之行始于足下，建立一个复杂的系统也不例外。从一些简单的事情开始，一切都运行在一台服务器上。图 1-1 显示了一个单个服务器设置的说明，其中所有内容都运行在一台服务器上： web 应用程序、数据库、缓存等。 要理解此设置，调查请求流和流量源会很有帮助。让我们先看一下请求流（图 1-2) 1. 用户可以通过 api.mysite.com 等域名来访问网站。通常，域名系统（DNS）是由第三方提供的付费服务，而不是由我们的服务器托管的。 2. 互联网协议（IP）地址被返回到浏览器或移动应用程序。在该示例中，将返回 IP 地址 15.125.23.214。 3. 一旦获得了 IP 地址，超文本传输协议（HTTP）[1] 请求将直接发送到您的 web服务器。 4. web 服务器返回 HTML 页面或 JSON 响应以进行呈现。 接下来，让我们检查一下流量源。到 web 服务器的流量来自两个来源： web 应用程序和移动应用程序。 - Web 应用程序：它使用服务器端语言（Java、Python 等）的组合。来处理业务逻辑、存储等，以及用来进行演示的客户端语言（HTML 和 JavaScript）。 - 移动应用： HTTP 协议是移动应用与 web 服务器之间的通信协议。JavaScript 对象表示法（JSON）由于其简单性，是通常用于传输数据的 API 响应格式。一个 JSON 格式的 API 响应示例如下所示： ```json // GET /users/12 – Retrieve user object for id = 12 { "id": 12, "firstName": "John", "lastName": "Smith", "address": { "streetAddress": "21 2nd Street", "city": "New York", "state": "NY", "postalCode": 10021 }, "phoneNumbers": [ "212 555-1234", "646 555-4567" ] } ``` ## 数据库 随着用户基础的增长，一个服务器是不够的，我们需要多个服务器：一个用于 web /移动流量，另一个用于数据库（图 1-3）。分离 Web /移动流量(web 层）和数据库（数据层）服务器可以独立扩展。 ### 使用哪个数据库？ 您可以在传统的关系数据库和非关系数据库之间进行选择。让我们来看看他们之间的差异。 关系数据库也被称为关系数据库管理系统（RDBMS）或 SQL 数据库。最流行的版本是 MySQL、Oracle 数据库、PostgreSQL 等。关系数据库在表和行中表示和存储数据。您可以使用跨不同数据库表的 SQL 来执行连接操作。 非关系数据库也被称为 NoSQL 数据库。最受欢迎的产品有 CouchDB、Neo4j、Cassandra、HBase、亚马逊 DynamoDB 等。[2].这些数据库被分为四类：键值存储、图存储、列存储和文档存储。在非关系型数据库中，通常不支持连接（join）操作。 对于大多数开发人员来说，关系数据库是最好的选择，因为它们已经存在了 40 多年，而且从历史上看，它们工作得很好。但是，如果关系数据库不适合特定的用例，那么在关系数据库之外进行探索是非常重要的。非关系数据库可能是正确的选择，如果： - 您的应用程序需要超低的延迟。 - 您的数据是非结构化的，或者您没有任何关系数据。 - 您只需要序列化和反序列化数据（JSON、XML、YAML等）。 - 您需要存储大量的数据。 ### 垂直缩放 vs 水平缩放 垂直缩放（vertical scaling），被称为“scale up”，是指给您的服务器增加更多性能的过程（CPU、RAM 等）。水平缩放称为“scale-out”，允许您通过在资源池中添加更多服务器来扩展。 当流量较低时，垂直缩放是一个很好的选择，而垂直缩放的简单性是其主要优势。不幸的是，它带有严重的局限性。 - 垂直缩放有一个很硬的限制。不可能为一台服务器添加无限的CPU和内存。 - 垂直缩放没有故障转移和冗余性。如果一个服务器宕机，网站/应用程序就会完全宕机。 由于垂直缩放的限制，水平缩放更适合用于大规模应用。 在之前的设计中，用户可以直接连接到 web 服务器。如果 web 服务器处于脱机状态，则用户将无法访问该网站。在另一种情况下，如果许多用户同时访问 web 服务器，并且它达到了 web 服务器的负载限制，那么用户通常会经历较慢的响应或无法连接到服务器。负载平衡器是解决这些问题的最佳技术。 ## 负载均衡器 负载均衡器在负载均衡集中定义的 web 服务器之间均匀地分配传入的流量。图 1-4 显示了负载平衡器的工作原理。 如图 1-4 所示，用户直接连接到负载均衡器的公共 IP。有了这个设置，客户端就再也无法直接访问 web 服务器了。为了获得更好的安全性，私有 IP 用于服务器之间的通信。私有 IP 是指只能在同一网络中的服务器之间可访问的 IP 地址；然而，它在互联网上是无法访问的。负载均衡器通过私有 IP 与 web 服务器进行通信。 在图 1-4 中，在添加了一个负载平衡器和第二个 web 服务器后，我们成功地解决了没有发生故障转移的问题，并提高了 web 层的可用性。详细说明如下： - 如果服务器 1 脱机，那么所有的流量都将被路由到服务器 2。这可以防止网站脱机。我们还将向服务器池中添加一个新的健康的 web 服务器，以平衡负载。 - 如果网站流量的增长迅速，并且两个服务器不足以处理流量，则负载均衡器可以优雅地处理这个问题。您只需要向 web 服务器池中添加更多的服务器，并且负载平衡器就会自动开始向它们发送请求。 现在 web 层看起来不错，那么数据层呢？当前的设计有一个数据库，因此它不支持故障转移和冗余。数据库复制是解决这些问题的一种常用技术。让我们来看看吧。 ## 数据库复制 引用维基百科：“数据库复制可以用于许多数据库管理系统，通常在原始（主）和副本（从）之间的主/从关系”[3]。 主数据库通常只支持写操作。从属数据库从主数据库获取数据的副本，并且只支持读取操作。所有数据修改命令都必须发送到主数据库。大多数应用程序需要更高的读写比；因此，系统中从数据库的数量通常大于主数据库的数量。图 1-5 显示了一个具有多个从属数据库的主数据库。 数据库复制的优点： - 更好的性能：在主从模型中，所有的写入和更新都发生在主节点中；然而，读取操作分布在各个从节点之间。这个模型提高了性能，因为它允许并行处理更多的查询。 - 可靠性：如果您的一个数据库服务器被自然灾害破坏，如台风或地震，数据仍然被保存。您不需要担心数据丢失，因为数据是跨多个位置复制的。 - 高可用性：通过在不同的位置复制数据，即使数据库脱机，您的网站仍然可以运行，因为您可以访问存储在另一个数据库服务器中的数据。 在上一节中，我们将讨论负载平衡器如何帮助提高系统的可用性。我们在这里问同样的问题：如果其中一个数据库脱机了怎么办？图 1-5 中讨论的架构设计可以处理以下情况： - 如果只有一个从数据库可用，并且它脱机，则读取操作将暂时引导到主数据库。一旦发现问题，新的从数据库将取代旧数据库。如果有多个从数据库可用，则读取操作重定向到其他健康从数据库。一个新的数据库服务器将取代旧的数据库服务器。 - 如果主数据库脱机，一个从数据库将被提升为新的主数据库。所有的数据库操作都将在新的主数据库上临时执行。一个新的从数据库将立即取代旧的从数据库以进行数据复制。在生产系统中，升级新的主数据更为复杂，因为从数据库中的数据可能不是最新的。丢失的数据需要通过运行数据恢复脚本来进行更新。虽然其他一些复制方法，如多主复制和循环复制可以提供帮助，但这些设置更为复杂；他们的讨论超出了这本书的范围。有兴趣的读者应参考所列出的参考资料[4] [5]。 图 1-6 显示了添加负载平衡器和数据库复制后的系统设计。 让我们来看一下设计： - 用户从 DNS 获得负载均衡器的 IP 地址。 - 一个用户将负载均衡器与此 IP 地址连接起来。 - HTTP 请求被路由到服务器 1 或服务器 2。 - web 服务器从从属数据库中读取用户数据。 - web 服务器会将任何数据修改操作路由到主数据库。这包括写入、更新和删除操作。 现在，您对 web 和数据层有了深入的了解，是时候提高加载/响应时间了。这可以通过添加一个缓存层，并将静态内容（JavaScript/CSS/图像/视频文件）转移到内容传递网络（CDN）来实现。 ## 缓存 缓存是一个临时存储区域，它将昂贵的响应或频繁访问的数据的结果存储在内存中，以便更快地提供后续的请求。如图 1-6 所示，每次加载一个新的网页时，都会执行一个或多个数据库调用来获取数据。反复调用数据库对应用程序性能的影响很大。高速缓存可以缓解这个问题。 ### 缓存层 缓存层是一个临时的数据存储层，比数据库要快得多。拥有一个单独的缓存层的好处包括更好的系统性能、减少数据库工作负载的能力，以及独立扩展缓存层的能力。图 1-7 显示了一个高速缓存服务器的可能设置： 在收到一个请求后，web 服务器首先检查该缓存是否有可用的响应。如果有，它会将数据发送回客户端。如果没有，它将查询数据库，将响应存储在缓存中，并将其发送回客户端。这种缓存策略称为通读缓存。根据数据类型、大小和访问模式，还可以使用其他缓存策略。之前的一项研究解释了不同的缓存策略是如何工作的[6]。 与缓存服务器的交互很简单，因为大多数缓存服务器都为通用编程语言提供 api。下面的代码片段显示了典型的 mem 缓存 api： ```python SECONDS = 1 cache.set('myKey', 'hi there', 3600 * SECONDS) cache.get('myKey') ``` ### 考虑使用缓存 以下是在使用高速缓存系统时需要考虑的一些注意事项： - 决定何时使用高速缓存。当数据经常读取但很少修改时，请考虑使用缓存。由于缓存的数据存储在易失性内存中，因此缓存服务器不适合持久化数据。例如，如果高速缓存服务器重新启动，则内存中的所有数据都将丢失。因此，重要的数据应该保存在持久的数据存储中。 - 过期政策。实施过期策略是一个很好的做法。缓存数据过期，将从缓存中删除。当没有过期策略时，缓存的数据将永久存储在内存中。建议不要使过期日期太短，因为这将导致系统太频繁地从数据库中重新加载数据。同时，建议不要配置过期时间太长，以免数据可能过时。 - 一致性：这涉及到保持数据存储和高速缓存的同步状态。由于数据存储和缓存上的数据修改操作不在单个事务中，因此可能会发生不一致。当跨多个区域进行缩放时，保持数据存储和缓存之间的一致性具有挑战性。有关更多细节，请参考脸书发布的题为“扩展脸书内存缓存”的论文[7]。 - 减轻故障：单个缓存服务器代表一个潜在的单点故障（SPOF），在维基百科中定义如下：“单点故障（SPOF）是系统的一部分，如果它失败，将停止整个系统工作”[8]。因此，建议跨不同的数据中心使用多个高速缓存服务器，以避免使用SPOF。另一种推荐的方法是按一定的百分比过剩供应所需的内存。随着内存使用量的增加，这就提供了一个缓冲区。 - 驱逐策略：一旦缓存已满，任何将项目添加到缓存中的请求都可能导致现有项目被删除。这被称为高速缓存驱逐。最近最少使用的（LRU）是最流行的高速缓存驱逐策略。其他驱逐策略，如最少常用（LFU）或第一出（FIFO），可以用来满足不同的用例。 ## 内容分发网络（CDN） CDN 是一个由地理上分散的服务器组成的网络，用于交付静态内容。CDN 服务器可以缓存静态内容，如图像、视频、CSS、JavaScript 文件等。 动态内容缓存是一个相对较新的概念，并且超出了这本书的范围。它支持缓存基于请求路径、查询字符串、Cookie 和请求头的 HTML 页面。有关此信息，请参考参考材料[9]中提到的文章。这本书重点介绍了如何使用 CDN 来缓存静态内容。 以下是 CDN 在高级级别上的工作方式：当用户访问一个网站时，最接近该用户的 CDN 服务器将提供静态内容。直观地说，来自 CDN 服务器的用户越多，网站加载就越慢。例如，如果 CDN 服务器在旧金山，洛杉矶的用户将比欧洲的用户更快地获得内容。图 1-9 是一个很好的示例，它显示了 CDN 如何改进加载时间。 图 1-10 演示了 CDN 的工作流。 1. 用户 A 尝试通过使用图像 URL 来获取 image.png。该 URL 的域名由 CDN 提供程序提供。以下两个图像 URL 是用于演示亚马逊和 Akamaicdn 上的图像 URL 的外观的示例： - https://mysite.cloudfront.net/logo.jpg - https://mysite.akamai.com/image-manager/img/logo.jpg 2. 如果 CDN 服务器缓存中没有 image.png，CDN 服务器将从源请求文件，源可以是 web 服务器，也可以是像 Amazon S3 这样的在线存储。 3. 源将 image.png 返回到 CDN 服务器，其中包括可选的 HTTP 头实时时间（TTL），它描述了映像缓存的时间。 4. CDN 缓存图像并将其返回给用户 A。图像一直缓存在 CDN 中，直到 TTL 过期。 5. 用户 B 发送一个获取相同图像的请求。 6. 只要 TTL 没有过期，图像就会从缓存中返回。 ### 使用 CDN 的考虑事项 - 成本：CDN 由第三方提供商运行，您需要收取进出 CDN 的数据传输费用。缓存不常用的资产不会提供显著的好处，因此您应该考虑将它们移出 CDN。 - 设置适当的缓存过期时间：对于对时间敏感的内容，设置缓存过期时间非常重要。缓存过期时间既不应太长也不应太短。如果它太长，内容可能就不再新鲜了。如果太短，可能会导致内容从原始服务器重新加载到 CDN。 - CDN 回退：你应该考虑你的网站/应用程序如何处理 CDN 失败。如果存在临时的 CDN 中断，客户端应该能够检测到问题并从源请求资源。 - 无效文件：您可以通过执行以下操作之一，在 CDN 文件过期之前从其删除文件： - 使用 CDN 供应商提供的 API 使 CDN 对象无效。 - 使用对象版本控制来服务于对象的不同版本。要版本一个对象，您可以向 URL 添加一个参数，例如版本号。例如，版本号 2 被添加到查询字符串中：image.png?v=2。 图 1-11 显示了添加了 CDN 和高速缓存后的设计。 1. 静态资产（JS、CSS、图像等）不再由 web 服务器提供服务。它们从 CDN 中获取，以获得更好的性能。 2. 通过缓存数据，可以减轻数据库的负载。 ## 无状态 Web 层 现在是时候考虑水平缩放 web 层了。为此，我们需要将状态（例如用户会话数据）从 web 层中移动出来。一个好的做法是将会话数据存储在持久存储中，如关系数据库或 NoSQL。集群中的每个 web 服务器都可以从数据库中访问状态数据。这被称为无状态的 web 层。 ### 状态体系结构 有状态服务器和无状态服务器有一些关键的区别。有状态服务器从一个请求到下一个请求都会记住客户端数据（状态）。无状态服务器不保存任何状态信息。 图 1-12 显示了一个有状态的体系结构的示例。 在图 1-12 中，用户 A 的会话数据和配置文件图像存储在服务器 1 中。要对用户 A 进行认证，必须将 HTTP 请求路由到服务器 1。如果将请求发送到服务器 2 等其他服务器，则身份验证将失败，因为服务器 2 不包含用户 A 的会话数据。类似地，来自用户 B 的所有 HTTP 请求都必须路由到服务器 2；来自用户 C 的所有请求都必须发送到服务器 3。 问题是来自同一客户端的每个请求必须路由到相同的服务器。这可以在大多数负载平衡器中的粘性会话来完成[10]；然而，这增加了开销。使用这种方法，添加或删除服务器要困难得多。处理服务器故障也是一个挑战。 ### 无状态体系结构 图 1-13 显示了一种无状态的体系结构。 在这种无状态体系结构中，来自用户的 HTTP 请求可以发送到任何 web 服务器，这些服务器从共享数据存储中获取状态数据。状态数据存储在一个共享的数据存储器中，并远离 web 服务器。无状态系统更简单、更健壮和可伸缩。 图 1-14 显示了使用无状态 web 层的更新设计。 在图 1-14 中，我们将会话数据从 web 层中移出，并将它们存储在持久性数据存储区中。共享的数据存储可以是一个关系数据库、内存缓存/Redis、NoSQL 等。选择 NoSQL 数据存储是因为它易于缩放。自动缩放是指根据流量负载自动添加或删除 web 服务器。在从 web 服务器中删除状态数据后，通过根据流量负载添加或删除服务器，可以很容易地实现 web 层的自动缩放。 你的网站发展迅速，并吸引了大量的国际用户。为了提高可用性并在更广泛的地理区域内提供更好的用户体验，支持多个数据中心至关重要。 ## 数据中心 图 1-15 显示了一个具有两个数据中心的示例设置。在正常运行中，用户被 geoDNS 路由，也称为地理路由，到最近的数据中心，美国东部的分割流量为 x%，美国西部为（100-x）%。geoDNS 是一种 DNS 服务，它允许根据用户的位置将域名解析为 IP 地址。 在发生任何重大的数据中心中断时，我们将所有流量引导到一个健康的数据中心。在图 1-16 中，数据中心 2（US-West）脱机，100% 的流量被传输至数据中心 1（US-East）。 要实现多数据中心的设置，必须解决几个技术挑战： - 流量重定向：需要有效的工具来将流量引导到正确的数据中心。GeoDNS 可以根据用户所在的位置将流量引导到最近的数据中心。 - 数据同步：来自不同地区的用户可以使用不同的本地数据库或缓存。在故障转移的情况下，流量可能会被路由到数据不可用的数据中心。一种常见的策略是跨多个数据中心复制数据。之前的一项研究显示了 Netflix 如何实现异步多数据中心复制[11]。 - 测试和部署：通过多数据中心的设置，在不同的地点测试您的网站/应用程序是很重要的。自动化部署工具对于保持所有数据中心的服务一致性至关重要[11]。 为了进一步扩展我们的系统，我们需要解耦系统的不同组件，以便它们可以独立地缩放。消息传递队列是许多现实世界的分布式系统用来解决这一问题的关键策略。 ## 消息队列 消息队列是存储在内存中的持久组件，它支持异步通信。它作为一个缓冲区，并分发异步请求。消息队列的基本架构很简单。输入服务，称为生产者/发布者，它创建消息，并将它们发布到消息队列中。其他服务或服务器，称为消费者/订阅者，连接到队列，并执行由消息定义的操作。该模型如图 1-17 所示。 解耦使消息队列成为构建可伸缩和可靠的应用程序的首选体系结构。使用消息队列，当使用者无法处理该队列时，生产者可以将消息发布到该队列。即使生产者不可用，消费者也可以从队列中读取消息。 考虑以下用例：您的应用程序支持照片定制，包括裁剪、锐化、模糊等。这些定制任务需要一段时间来完成。在图 1-18 中，web 服务器会将照片处理作业发布到消息队列中。照片处理工作者从消息队列中获取作业，并异步地执行照片定制任务。生产者和消费者可以独立地进行缩放。当队列的大小变大时，会添加更多的工作者，以减少处理时间。但是，如果队列大部分时间都是空的，则可以减少工作者的数量。 ## 日志记录、度量、自动化 当使用运行在一些服务器上的小网站时，日志记录、指标和自动化支持是很好的实践，但不是必要的。然而，现在你的网站已经发展为服务于一个大型企业，投资于这些工具是至关重要的。 日志记录：监视错误日志很重要，因为它有助于识别系统中的错误和问题。您可以在每个服务器级别的错误日志，或者使用工具将它们聚合到集中服务，以便于搜索和查看。 指标：收集不同类型的指标有助于帮助我们获得业务见解，并了解系统的健康状况。以下一些指标是有用的： - 主机级指标：CPU、内存、磁盘I/O等。 - 聚合级别指标：例如，整个数据库层、高速缓存层等的性能。 - 关键业务指标：每日活跃用户、留存率、收入等。 自动化：当一个系统变得大而复杂时，我们需要构建或利用自动化工具来提高生产率。持续集成是一种很好的实践，其中每个代码签入都通过自动化进行验证，允许团队及早发现问题。此外，自动化您的构建、测试、部署过程等等。可以显著提高开发人员的生产力。 ## 添加消息队列和不同的工具 图 1-19 显示了更新后的设计。由于空间的限制，图中只显示了一个数据中心。 1. 该设计包括一个消息队列，这有助于使系统更松散地耦合和故障弹性。 2. 其中包括日志记录、监控、度量标准和自动化工具 随着数据的不断增长，数据库就会越来越超载。是时候缩放数据层了。 ## 数据库缩放 数据库缩放有两种主要的方法：垂直缩放和水平缩放。 ### 垂直缩放 垂直缩放，也被称为向上缩放，是通过增加更多的功率（CPU、RAM、磁盘等）来进行的缩放。到一个现有的机器。这里有一些功能强大的数据库服务器。根据 Amazon 关系数据库服务（RDS）[12]，您可以获得一个具有 24 TB 内存的数据库服务器。这种功能强大的数据库服务器可以存储和处理大量的数据。例如，stackoverflow.com 在 2013 年每月有超过 1000 万的独立访问者，但它只有一个主数据库[13]。然而，垂直缩放也带有一些严重的缺点： - 你可以添加更多的 CPU、RAM 等。到您的数据库服务器，但有硬件限制。如果您有一个很大的用户基础，那么单台服务器是不够的。 - 单点故障的风险更大。 - 垂直缩放的总成本较高。功能强大的服务器要贵得多。 ### 水平缩放 水平缩放，也称为分片，是添加更多服务器的做法。图 1- 20 将垂直缩放和水平缩放进行了比较。 分片将大型数据库分离成更小、更容易管理的部分，称为片（shards）。每个片共享相同的模式（schema），尽管每个片上的实际数据对片是唯一的。 图 1-21 显示了一个分片数据库的示例。用户数据根据用户 id 分配给数据库服务器。每当访问数据时，将使用哈希函数来查找相应的碎片。在我们的示例中，user_id % 4 被用作哈希函数。如果结果等于 0，则片 0 用于存储和获取数据。如果结果等于1，则使用片1。同样的逻辑也适用于其他的片。 图 1-22 显示了分形数据库中的用户表。 在实施分片策略时，需要考虑的最重要的因素是分片键的选择。分片键（称为分区键）由一个或多个决定数据如何分布的列组成。如图 1-22 所示，“user_id”是分片键。分片键允许您通过将数据库查询路由到正确的数据库来有效地检索和修改数据。在选择分片键时，最重要的标准之一是选择一个可以均匀分布数据的键。 分片是一种扩展数据库的伟大技术，但它远不是一个完美的解决方案。它给这个系统带来了复杂性和新的挑战： **重分片数据**：当 1) 由于快速增长，一个单一的片不能再保存更多的数据时，就需要重分片数据。2) 由于数据分布不均匀，某些片可能会比其他片更快地经历片耗尽（shard exhaustion）。当片耗尽发生时，它需要更新分片函数和移动数据。一致性散列是解决这个问题的一种常用技术，这将在第 5 章中讨论。 **名人问题**：这也被称为热点键问题。对特定片的过度访问可能会导致服务器过载。想象一下，凯蒂·佩里、贾斯汀·比伯和 Lady Gaga 的数据都在同一个片。对于社交应用程序来说，这些片将被阅读操作所淹没。为了解决这个问题，我们可能需要为每个名人分配一块片。每个片甚至可能需要进一步的分割。 **连接和去规范化**：一旦一个数据库已经跨多个服务器进行了共享，就很难跨数据库片执行连接操作。一个常见的解决方法是将数据库去规格化，以便可以在单个表中执行查询。 在图 1-23 中，我们分割了数据库，以支持快速增长的数据流量。同时，一些非关系功能被移到 NoSQL 数据存储中，以减少数据库负载。这里有一篇介绍了许多 NoSQL [14] 用例的文章。 ## 数百万用户及以上的用户 缩放一个系统是一个迭代的过程。重复我们在这一章中学到的东西可以让我们走得更远。需要更多的微调和新的策略来扩展超过数百万用户。例如，您可能需要优化系统，并将系统解耦到更小的服务。本章中所学到的所有技术都应该为应对新的挑战提供一个良好的基础。在这一章中，我们总结了我们如何扩展系统以支持数百万用户： - 保持web层无状态 - 在每个层构建冗余 - 尽可能缓存数据 - 支持多个数据中心 - 将静态资产放在CDN主机 - 通过分片进行数据层缩放 - 分割各个层到单独的服务 - 监控您的系统和使用自动化工具 祝贺你能走到这一步！现在拍拍自己的背。干得好！ # 第 2 章：粗略估计 在系统设计面试中，有时会要求您使用粗略估计（back-of-the-envelope estimation）来估计系统容量或性能要求。据谷歌高级研究员 Jeff Dean 说，“粗略估计是你结合使用思想实验和通用性能数字来创建的估计，以良好地了解哪些设计将满足你的需求”[1]。 您需要有良好的可伸缩性基础，以有效地执行粗略估计。我们应该很好地理解以下概念：2 的次方 [2]、每个程序员都应该知道的延迟号和可用性号。 ## 二的次方 尽管在处理分布式系统时，数据量可能会变得巨大，但计算归根结底是基础。为了获得正确的计算，关键是要知道使用 2 的幂的数据量单位。一个字节是一个 8 位的序列。ASCII 字符使用一个字节的内存（8 位）。下表解释了数据量单位（表 2-1）。 | 次方 | 约等于值 | 全名 | 简写名 | | ---- | -------- | -------------------- | ------ | | 10 | 一千 | 1 千字节（Kilobyte） | 1 KB | | 20 | 一百万 | 1 兆字节（Megabyte） | 1 MB | | 30 | 十亿 | 1 吉字节（Gigabyte） | 1 GB | | 40 | 一万亿 | 1 太字节（Terabyte） | 1 TB | | 50 | 一千万亿 | 1 拍字节（Petabyte） | 1 PB | ## 每个程序员都应该知道的延迟数 来自谷歌的 Dean 博士揭示了 2010 年[1]中典型计算机操作的长度。随着计算机变得更快和更强大，一些数字已经过时了。然而，这些数字仍然能够让我们了解不同计算机操作的速度和缓慢。 | 操作名 | 时间 | | ---------------------------------- | ----------------------- | | L1 缓存引用 | 0.5 ns | | 分支预测错误 | 5 ns | | L2 缓存引用 | 7 ns | | 互斥锁/解锁 | 100 ns | | 主存引用 | 100 ns | | 使用 Zippy 压缩 1K 字节 | 10,000 ns = 10 μs | | 通过 1 Gbps 网络发送 2K 字节 | 20,000 ns = 20 μs | | 从内存中连续读取 1 MB | 250,000 ns = 250 μs | | 在同一数据中心内的往返 | 500,000 ns = 500 μs | | 磁盘寻道 | 10,000,000 ns = 10 ms | | 从网络连续读取 1 MB | 10,000,000 ns = 10 ms | | 从磁盘连续读取 1 MB | 30,000,000 ns = 30 ms | | 发包 CA（加利福尼亚）-> 荷兰 -> CA | 150,000,000 ns = 150 ms | 一位谷歌软件工程师开发了一个工具来可视化迪恩博士的数字。该工具还考虑到了时间因素。图 2-1 显示了截至 2020 年的可视化延迟数（数据来源：参考材料[3])。 通过分析图 2-1 中的数字，我们得出以下结论： - 内存速度快，但磁盘速度慢。 - 尽可能避免进行磁盘寻道。 - 简单的压缩算法速度很快。 - 如果可能的话，在将数据发送到互联网之前压缩数据。 - 数据中心通常位于不同的区域，在它们之间发送数据需要时间。 ## 可用性数字 高可用性是指系统在所期望的长时间持续运行的能力。高可用性是以百分比来衡量的，100% 表示服务的停机时间为 0。大多数服务下降在 99% 到 100% 之间。 服务级别协议（SLA）是表示服务提供者的常用术语。这是您（服务提供商）和您的客户之间的协议，该协议正式定义了您的服务将提供的正常运行时间水平。云服务提供商 Amazon [4]、谷歌[5]和微软[6]将其 SLA 设置在 99.9% 或以上。正常运行时间传统上以 9 个为单位来衡量。9 个数字越多越好。如表 2-3 所示，9 的数量与预期的系统停机时间相关。 | 可用性 % | 平均每天停机时间 | 平均每年停机时间 | | -------- | ---------------- | ---------------- | | 99% | 14.40 分钟 | 3.65 天 | | 99.9% | 1.44 分钟 | 8.77 小时 | | 99.99% | 8.64 秒 | 52.60 分钟 | | 99.999% | 864.00 毫秒 | 5.26 分钟 | | 99.9999% | 86.40 毫秒 | 31.56 秒 | ## 示例：估计推特的 QPS 和存储需求 请注意，以下数字仅用于本练习，因为它们不是推特上的真实数字。 假设： - 活跃用户为每月 3 亿。 - 50% 的用户每天都在使用推特。 - 用户平均每天发布 2 条推特。 - 10% 的推文包含多媒体。 - 数据存储时间 5 年 估计： 每秒查询次数（Query per second，QPS）估计： - 每天活跃用户（Daily active users，DAU）= 3 亿 * 50 % = 1.5 亿 - 推特 QPS = 1.5 亿 * 2 推特 / 24 小时 / 3600 秒 = ~3500 - 查看 QPS = 2 * QPS = ~7000 这里我们将只评估多媒体存储 - 平均推特大小： - 推特 id 64 字节 - 文本 140 字节 - 多媒体 1 MB - 多媒体存储：1.5 亿 * 2 * 10 % * 1 MB = 30 TB 每天 - 5 年多媒体存储：30 TB * 365 * 5 = ~55 PB ## 提示 粗略估计就是关于这个过程的。解决问题比取得结果更重要。面试官可能会测试你解决问题的能力。以下是一些提示： - 取整和近似。在面试过程中，很难执行复杂的数学操作。例如，“99987/9.1”的结果是什么？没有必要花宝贵的时间来解决复杂的数学问题。精度不是预期的。最好使用整数和近似值。前面的除法问题可以简化为：“100000/10”。 - 写下你的假设。写下你的假设以供以后引用是个好主意。 - 标记你的单位。当你写下“5”时，它是指 5 KB 还是 5 MB？你可能会把自己搞混了。写下单位，因为“5MB”有助于消除歧义。 - 通常要求的粗略估计： QPS、峰值 QPS、存储、缓存、服务器数量等。你可以在准备面试时练习这些计算。熟能生巧。 祝贺你能走到这一步！现在拍拍自己的背。干得好！ # 第 3 章：系统设计面试的框架 你刚刚在你梦想中的公司得到了一个令人垂涎的现场面试。招聘协调员会给你发送当天的时间表。浏览一下列表，你会感觉很好，直到你的目光落在这个面试环节-系统设计面试。 系统设计面试通常会令人生畏。它可能就像“设计一个著名的产品X？”一样模糊。这些问题都很模棱两可，而且似乎过于宽泛。你的疲倦是可以理解的。毕竟，怎么能在一个小时内设计出一个需要数百数千名工程师制造的流行产品呢？ 好消息是，没有人希望你这么做。现实世界的系统设计非常复杂的。例如，谷歌搜索看似简单；然而，支持这种简单性的技术数量确实是惊人的。如果没有人期望你在一个小时内设计出一个真实世界的系统，那么系统设计面试有什么好处呢？ 系统设计访谈模拟了现实生活中的问题解决，两个同事合作解决一个模棱两可的问题，并提出一个满足他们目标的解决方案。这个问题是开放式的，而且没有一个完美的答案。与你在设计过程中投入的工作相比，最终的设计就不那么重要。这允许您展示您的设计技能，捍卫您的设计选择，并以建设性的方式回应反馈。 让我们翻翻桌子，考虑一下面试官走进会议室迎接你时脑子想的是什么。面试官的主要目标是准确地评估你的能力。她最不希望做的是给出一个不确定的评估，因为会议进展不佳，而且没有足够的信号。面试官在系统设计面试中是在寻找什么？ 许多人认为，系统设计面试完全都是关于一个人的技术设计技能。这远不止于此。一个有效的系统设计面试提供了一个人的协作、在压力下工作以及建设性地解决模糊性的能力。问好问题的能力也是一项必不可少的技能，许多面试官特别寻找这种技能。 一个好的面试官也会寻找危险信号。过度工程是许多工程师的一种真正的疾病，因为他们喜欢设计的纯度，而忽略了权衡。他们往往不到过度设计系统的复合成本，许多公司为这种无知付出了高昂的代价。您当然不想在系统设计面试中展示这种趋势。其他的危险信号还包括心胸狭窄、固执等。 在本章中，我们将介绍一些有用的技巧，并介绍一个简单而有效的框架来解决系统设计面试问题。 ## 有效系统设计面试的 4 步步骤 每个系统设计面试都是不同的。一个伟大的系统设计面试是开放式的，没有一刀切的解决方案。然而，在每个系统设计访谈中都有一些步骤和共同点。 ### 第 1 步 - 了解问题，确定设计范围 “老虎为什么会吼？” 一只手在教室后面伸起。 ”是的，吉米？“，老师回答说。 ”因为他饿了。” “很好，吉米。” 在他的整个童年时代，吉米一直是班上第一个回答问题的人。每当老师问一个问题时，教室里总是有一个孩子喜欢回答这个问题，不管他是否知道答案。那是吉米。 吉米是一名优秀的学生。他为自己很快就知道了所有的答案而感到自豪。在考试中，他通常是第一个完成问题的人。他是任何学术竞赛的首选。 别像吉米。 在系统设计面试中，不加思考地快速给出答案不会给你任何奖励。没有彻底理解要求的回答是一个巨大的危险信号，因为面试不是一个琐事比赛。目前还没有正确的答案。 所以，不要直接进去给出一个解决方案。慢下来深入思考，提出问题，以澄清要求和假设。这是非常重要的。 作为一名工程师，我们喜欢解决一些困难的问题，并跳入最终的设计之中；然而，这种方法很可能会导致你设计出错误的系统。作为一名工程师，最重要的技能之一是提出正确的问题，做出适当的假设，并收集构建系统所需的所有信息。所以，不要害怕提问。 当你问一个问题时，面试官要么直接回答你的问题，要么要求你做出假设。如果发生了后者，就在白板或纸上写下你的假设。你以后可能会需要它们。 该问什么样的问题？问一些问题，以理解确切的要求。这里有一些问题可以帮助你开始工作： - 我们要构建哪些具体的功能？ - 该产品有多少个用户？ - 该公司预计扩大规模的速度有多快？3 个月、6 个月和一年的预期规模是多少？ - 该公司的技术堆栈是什么？您可以利用哪些现有的服务来简化设计？ #### 示例 如果您被要求设计一个新闻推送系统，您就想问一些能帮助您澄清要求的问题。你和面试官之间的对话可能是这样的： **候选人**：这是一个手机应用程序吗？还是一个网络应用程序？或者两者都有？ **面试官**：两者兼而有之。 **候选人**：该产品最重要的功能是什么？ **面试官**：能够发布一个帖子和查看朋友的动态消息。 **候选人**：新闻推送是按时间顺序排序还是按特定顺序排序？特定的顺序意味着每个帖子都被赋予了不同的权重。例如，来自亲密朋友的帖子比来自群组的帖子更重要。 **面试官**：为了保持事情的简单性，让我们假设提要是按时间倒序排序的。 **候选人**：一个用户可以有多少个朋友？ **面试官**：5000 **候选人**：交通量是多少？ **面试官**：1000 万每日活跃用户（DAU） **候选人**：feed 可以包含图像，视频，或只是文本？ **面试官**：它可以包含媒体文件，包括图像和视频。 以上是一些你可以问面试官的样本问题。理解需求和澄清歧义是很重要的 ### 第 2 步 - 提出高级设计，并获得支持 在这一步中，我们的目标是开发一个高水平的设计，并与面试官就设计达成协议。在这个过程中与面试官合作是个好主意。 - 提出了一个设计的初步蓝图。要求反馈。把你的面试官当作队友，一起工作。许多优秀的面试官都喜欢交谈和参与进来。 - 在白板或纸上绘制包含关键组件的方框图。这可能包括客户机（移动/web）、api、web 服务器、数据存储、缓存、CDN、消息队列等。 - 进行后台计算，以评估您的蓝图是否符合比例约束。大声想想。如果有必要粗略估计，请在深入前与面试官沟通。 如果可能，请浏览一些具体的用例。这将帮助您构建高层次的设计。用例也可能帮助您发现尚未考虑的边缘用例。 我们应该在这里包括 API 端点和数据库模式吗？这取决于问题所在。对于像“设计谷歌搜索引擎”这样的大型设计问题，这有点太低了。对于像为多人扑克游戏设计后端这样的问题，这是一个公平的游戏。与面试官沟通。 #### 示例 让我们使用“设计一个新闻推送系统”来演示如何接近高级设计。在这里，您不需要了解系统是如何工作的。所有的细节将在第11章中解释。 在高层，设计分为两个流程：提要发布和新闻提要建设。 - 提要发布：当用户发布一篇文章时，相应的数据将被写入缓存/数据库，该文章将被填充到朋友的新闻提要中。 - 新闻推送建设：新闻推送是通过按反时间顺序聚合朋友的帖子来构建的。 图 3-1 和图 3-2 分别展示了饲料发布和新闻构建流的高层设计 ### 第 3 步 - 深入设计 在这一步，你和你的面试官应该已经实现了以下目标： - 同意总体目标和功能范围 - 概述高层蓝图 - 从你的面试官获得关于高层设计的反馈 - 根据她的反馈，对需要深入研究的领域有一些初步的想法 您应与面试官一起确定体系结构中的组件和优先级。值得强调的是，每一次面试都是不同的。有时，面试官可能会暗示她喜欢专注于高级设计。有时，对于高级候选人的面试，讨论可能是关于系统性能特征，可能集中在瓶颈和资源估计上。在大多数情况下，面试官可能希望您深入了解一些系统组件的细节。对于 URL 缩短器，深入研究可将长 URL 转换为短 URL 的哈希函数设计是很有趣的。对于一个聊天系统来说，如何减少延迟和如何支持在线/离线状态是两个有趣的话题。 时间管理是必不可少的，因为它很容易被不能证明你的能力的微小细节所迷惑。你必须携带信号来展示你的面试官。尽量不要谈到不必要的细节。例如，在系统设计面试中，详细讨论 Facebook feed 排名的 EdgeRank 算法并不理想，因为这将花费大量宝贵的时间，也不能证明你设计可伸缩系统的能力。 #### 示例 在这一点上，我们已经讨论了一个新闻推送系统的高级设计，面试官对你的建议很满意。接下来，我们将调查两个最重要的用例： 1. 推送发布 2. 新闻推送获取 图 3-3 和图 3-4 显示了这两个用例的详细设计，这将在第 11 章中详细说明。 ### 第 4 步 - 总结 在最后一步，面试官可能会问你一些后续问题，或者给你自由讨论其他额外的问题。这里有几个方向要遵循： - 面试官可能想让你识别系统的瓶颈，并讨论潜在的改进。永远不要说你的设计是完美的，没有什么是可以改进的。总有一些东西需要改进的。这是一个很好的机会来展示你的批判性思维，并留下最后的好印象。 - 给面试官回顾一下你的设计可能会很有用。如果你提出了一些解决方案，这一点尤为重要。在长时间的培训后，刷新面试官的记忆会很有帮助。 - 错误情况（服务器故障、网络丢失等）谈论这些话题都很有趣。 - 操作问题值得一提。如何监控指标和错误日志？如何推出该系统？ - 如何处理下一个比例曲线也是一个有趣的话题。例如，如果您当前的设计支持 100 万用户，那么您需要做哪些更改来支持 1000 万用户？ - 如果你有更多的时间，还会提出你需要的其他改进。 最后，我们总结了一个关于要做和不要做的清单。 #### 要做 - 总是要求澄清。不要假设你的假设是正确的。 - 了解问题的要求。 - 这里既没有正确的答案，也没有最好的答案。一种旨在解决年轻初创公司问题的解决方案不同于一家拥有数百万用户的成熟公司。确保你理解了这些要求。 - 让面试官知道你在想什么。与你的面试对象进行沟通。 - 如果可能的话，建议采用多种方法。 - 一旦你同意面试官的蓝图，请详细了解每个组件。首先设计最关键的组件。 - 反馈想法给面试官。一个好的面试官作为队友和你一起工作。 - 永不放弃。 #### 不要做 - 不要对典型的面试问题毫无准备。 - 不要在没有澄清需求和假设之前直接进入解决方案。 - 不要在开始时过多单个组件的细节。首先给出高级别的设计，然后深入研究。 - 如果你被卡住了，请不要犹豫地寻求提示。 - 再次，沟通。不要默默地思考。 - 不要认为一旦你的设计，面试就完成了。直到面试官说你已经完成了，你才会被完成。尽早并经常寻求反馈。 ## 在每个步骤上的时间分配 系统设计的面试问题通常非常宽泛，45 分钟或一个小时不足以涵盖整个设计。时间管理是必不可少的。每一步你应该花多少时间？以下是一个非常粗略的指南，指导你分配 45 分钟的面试时间。请记住，这是一个粗略的估计，实际的时间分布取决于问题的范围和面试官的要求。 步骤 1 了解问题并确定设计范围：3 - 10 分钟 步骤 2 提出高级设计并获得支持： 10 - 15 分钟 步骤 3 深入设计： 10 - 25 分钟 步骤 4 总结： 3 - 5 分钟 # 第 4 章：设计一个限速器 在网络系统中，速率限制器用于控制由客户端或服务发送的流量的速率。在 HTTP 世界中，速率限制器限制在指定时间内允许发送的客户端请求数量。如果 API 请求计数超过速率限制器定义的阈值，则将阻止所有多余的调用。以下是以下几个例子： - 一个用户每秒可以写不超过 2 篇文章。 - 您每天最多可以从同一 IP 地址创建 10 个帐户。 - 你可以每周申请奖励不超过 5 次。 在本章中，我们将要求您设计一个速率限制器。在开始设计之前，我们首先来看看使用 API 速率限制器的好处： - 防止由拒绝服务（DoS）攻击[1]造成的资源短缺。几乎所有由大型科技公司发布的 API 都会强制执行某种形式的费率限制。例如，推特将推文的数量限制在每 3 小时[2]的 300 条。谷歌文档 API 有以下默认限制：对于读取请求[3]，每个用户每 60 秒有 300 个默认限制。速率限制器通过阻止过量的呼叫来防止有意或无意的 DoS 攻击。 - 降低成本。限制超额请求意味着更少的服务器，并向高优先级的 API 分配更多的资源。费率限制对于使用付费第三方 API 的公司来说是极其重要。例如，您需要对以下外部 API 进行每次呼叫的收费：检查信用证、付款、检索运行状况记录等。限制通话数量对于降低成本至关重要。 - 防止服务器超载。为了减少服务器负载，使用速率限制器过滤由机器人或用户不当行为引起的过量请求。 ## 第 1 步 - 了解问题，确定设计范围 速率限制可以使用不同的算法来实现，每种算法都有其优缺点。面试官和候选人之间的互动有助于澄清我们正在试图建立的速率限制器的类型。 **候选人**：我们要设计什么样的限速器？它是一个客户端速率限制器还是一个服务器端 API 速率限制器？ **面试官**：很好的问题。我们主要关注服务器端 API 速率限制器。 **候选者**：速率限制器是否基于 IP、用户 ID 或其他属性来限制 API 请求？ **面试官**：限速器应该足够灵活，以支持不同的限流规则集。 **候选人**：这个系统的规模是多少？它是为初创公司还是为拥有庞大用户基础的大公司而设计的？ **面试官**：系统必须能够处理大量的请求。 **候选人**：该系统能在分布式环境中工作吗？ **面试官**：是的。 **候选人**：速率限制器是一个单独的服务，还是应该在应用程序代码中实现它？ **面试官**：这是一个由你来决定的设计决定。 **候选人**：我们是否需要通知那些被限制的用户？ **面试官**：是的。 ### 需求 以下是对系统需求的摘要： - 准确地限制过多的请求。 - 低延迟。速率限制器不应减缓 HTTP 的响应时间。 - 使用尽可能少的内存。 - 分布式速率限制。该速率限制器可以跨多个服务器或进程进行共享。 - 异常处理。当用户被限制请求时，向用户显示明确的异常。 - 高容错能力。如果速率限制器有任何问题（例如，缓存服务器脱机），则不会影响整个系统。 ## 第 2 步 - 提出高级设计，并获得支持 让我们保持事情的简单性，并使用一个基本的客户机和服务器模型来进行通信。 ### 把速率限制器放在哪里？ 直观地说，您可以在客户端或服务器端实现一个速率限制器。 - 客户端方面的实现。一般来说，客户端是一个不可靠的强制执行速率限制的地方，因为客户端请求很容易被恶意参与者伪造。此外，我们可能无法控制客户端的实现。 - 服务器端实现。图 4-1 显示了放置在服务器端的一个速率限制器。 除了客户机和服务器端实现之外，还有另一种方法。我们没有在 API 服务器上设置一个速率限制器，而是创建了一个速率限制器中间件，它可以限制对 API 的请求，如图 4-2 所示。 让我们使用图 4-3 中的一个示例来说明速率限制在这个设计中是如何工作的。假设我们的 API 允许每秒发送 2 个请求，并且客户端在每秒内向服务器发送 3 个请求。前两个请求被路由到 API 服务器。然而，速率限制器中间件限制第三个请求并返回一个 HTTP 状态代码 429。HTTP 429 响应状态代码表示用户发送了太多的请求。 云微服务[4]已经变得广泛流行，速率限制通常在一个称为 API 网关的组件中实现。API 网关是一种完全管理的服务，支持速率限制、SSL 终止、身份验证、IP 白名单、静态服务内容等。目前，我们只需要知道 API 网关是一个支持速率限制的中间件。 在设计速率限制器时，我们自己要问的一个重要问题是：速率限制器应该在哪里、在服务器端或在网关中实现？目前还没有绝对的答案。这取决于您的公司当前的技术堆栈、工程资源、优先级、目标等。以下是一些一般的指导方针： - 评估您当前的技术堆栈，如编程语言、缓存服务等。确保您当前的编程语言在服务器端实现速率限制。 - 确定适合您的业务需求的速率限制算法。当您在服务器端实现所有内容时，您就可以完全控制算法。但是，如果您使用第三方网关，那么您的选择可能会受到限制。 - 如果您已经使用了微服务体系结构，并在设计中包含了一个 API 网关来执行身份验证、IP 白名单等，那么您可以向 API 网关添加一个速率限制器。 - 建立你自己的速率限制服务需要时间。如果您没有足够的工程资源来实现速率限制器，那么商业 API 网关是一个更好的选择。 ### 速率限制算法 速率限制可以使用不同的算法来实现，而且每一种算法都有不同的优缺点。尽管本章没有关注算法，但在高层理解它们有助于选择正确的算法或算法组合来适应我们的用例。以下是一个流行的算法列表： - 令牌桶 - 漏桶 - 固定窗口计数器 - 滑动窗口日志 - 滑动窗口计数器 #### 令牌桶算法 令牌桶算法被广泛用于速率限制。它很简单，理解良好，并被互联网公司广泛使用。Amazon [5]和 Stripe [6]都使用这个算法来限制他们的 API 请求。 令牌桶算法的工作原理如下： - 令牌桶是一个具有预定义容量的容器。令牌会定期以预设的速率放入桶中。一旦桶满了，就不再添加令牌。如图 4-4 所示，令牌桶容量为 4。重新填充器每秒钟在桶中放入 2 个代币。一旦桶装满了，额外的标记就会溢出。 - 每个请求都会消耗一个令牌。当一个请求到达时，我们会检查桶中是否有足够的令牌。图 4-5 解释了它是如何工作的。 - 如果有足够的令牌，我们将为每个请求取出一个令牌，然后请求将被通过。 - 如果没有足够的令牌，则会删除该请求。 图 4-6 说明了令牌消耗、补充和速率限制逻辑的工作原理。在本例中，令牌桶大小为4，补充率为每 1 分钟 4 次。 令牌桶算法采用两个参数： - 桶大小：桶中允许的最大代币数量 - 补充率：每秒钟注入桶中的代币数量 我们需要多少个桶？这是不同的，它取决于速率限制规则。这里有几个例子。 - 通常需要为不同的 API 端点有不同的桶。例如，如果一个用户被允许每秒发布 1 个帖子，每天添加 150 个朋友，比如每秒发布 5 个帖子，每个用户需要 3 个桶。 - 如果我们需要根据 IP 地址来限制请求，那么每个 IP 地址都需要一个桶。 - 如果系统允许每秒最多 10,000 个请求，那么让所有请求共享一个全局桶是有意义的。 优点： - 该算法易于实现。 - 内存效率。 - 令牌桶允许短时间内的流量爆发。只要还剩下令牌，请求就可以通过。 缺点： - 该算法中的两个参数是桶的大小和令牌的再填充率。然而，正确地调整它们可能很具有挑战性。 #### 漏桶算法 泄漏桶算法类似于令牌桶，只是请求以固定的速率处理。它通常是通过一个先入先出（FIFO）队列来实现的。该算法的工作原理如下： - 当一个请求到达时，系统将检查该队列是否已满。如果请求未满，则将请求添加到队列中。 - 否则，将删除该请求。 - 请求从队列中提取并定期处理。 图 4-7 解释了该算法的如何工作原理。 泄漏桶算法采用以下两个参数： - 桶大小：它等于队列大小。该队列保存要以固定速率处理的请求。 - 流出速率：它定义了可以以固定速率处理多少个请求，通常以秒为单位。 电子商务公司 Shopify 使用漏桶进行速率限制的[7]。 优点： - 由于有限的队列大小，内存非常高效。 - 请求以固定的速率处理，因此它适用于需要稳定的流出率的用例。 缺点： - 大量的流量用旧的请求填充队列，如果没有及时处理，最近的请求将受到速率限制。 - 在算法中有两个参数。要正确地调整它们可能并不容易。 #### 固定窗口计数器算法 固定窗口计数器算法的工作原理如下： - 该算法将时间轴划分为固定大小的时间窗口，并为每个窗口分配一个计数器。 - 每个请求将计数器增加 1。 - 一旦计数器达到预定义的阈值，新的请求将被删除，直到一个新的时间窗口开始。 让我们用一个具体的例子来看看它是如何工作的。在图 4-8 中，时间单位为 1 秒，系统每秒最多允许 3 个请求。在每秒个窗口中，如果接收到超过 3 个请求，则会删除额外的请求，如图 4-8 所示。 该算法的一个主要问题是，在时间窗口边缘的流量突发可能会导致比允许的配额更多的请求。考虑以下情况： 在图 4-9 中，系统允许每分钟最多有 5 个请求，并且在人类友好的每分钟内将可用的配额重置。如前所见，在 2：00：00 到 2：01：00 之间有 5 个请求，在 2：01：00 到 2：02：00 之间还有 5 个请求。对于在 2：00：30 到 2：01：30 之间的一分钟窗口，将通过 10 个请求。这是允许的请求的两倍。 优点： - 内存效率较高。 - 易于理解。 - 在单位时间窗口结束时重置可用配额适合某些用例。 缺点： - 窗口边缘的流量激增可能会导致比允许的配额更多的请求。 #### 滑动窗口日志算法 如前所述，固定窗口计数器算法有一个主要问题：它允许在窗口的边缘通过更多的请求。滑动窗口日志算法解决了这个问题。它的工作原理如下： - 该算法可以跟踪请求的时间戳。时间戳数据通常保存在缓存中，例如 Redis [8]的排序集。 - 当一个新的请求出现时，请删除所有过时的时间戳。过期的时间戳被定义为那些超过当前时间窗口开始时间的时间戳。 - 向日志中的新请求添加时间戳。 - 如果日志大小相同或低于允许的计数，则会接受请求。否则，将被拒绝。我们用图 4-10 所示的一个例子来解释这个算法。 我们将用图 4-10 中所示的一个示例来解释该算法。 在本例中，速率限制器允许每分钟发出 2 个请求。通常，Linux 时间戳存储在日志中。然而，在我们的示例中使用了人类可读的时间表示，以获得更好的可读性。 - 当一个新的请求在 1：00：01 到达时，该日志将为空。因此，该请求是允许的。 - 一个新的请求在 1：00：30 到达，时间戳 1：00：30 被插入到日志中。插入后，日志大小为 2，不大于允许的计数。因此，该请求是允许的。 - 一个新的请求在 1：00：50 到达，并且时间戳被插入到日志中。插入后，日志大小为 3，大于允许的大小 2。因此，即使时间戳仍保留在日志中，此请求也会被拒绝。 - 一个新的请求到达1：01：40。范围 [1：00：40、1：01：40) 中的请求是在最新的时间范围内，但在 1：00：40 之前发送的请求已过期。两个过时的时间戳，1：00：01 和 1：00：30，将从日志中删除。删除操作后，日志大小变为 2；因此，接受请求。 优点： - 该算法实现的速率限制非常准确。在任何滚动窗口中，请求都不会超过速率限制。 缺点： - 该算法会消耗大量内存，因为即使请求被拒绝，它的时间戳也可能仍然存储在内存中。 #### 滑动窗口计数器算法 滑动窗口计数器算法是一种将固定窗口计数器和滑动窗口日志相结合的混合方法。该算法可以通过两种不同的方法来实现。我们将在本节中解释一个实现，并在本节的末尾为其他实现提供参考。图 4-11 说明了该算法是如何工作的。 假设速率限制器每分钟最多允许 7 个请求，并且在前几分钟有 5 个请求，在当前几分钟有 3 个请求。对于在当前分钟内到达 30% 位置的新请求，滚动窗口中的请求数使用以下公式计算： - 当前窗口中的请求 + 请求在之前的滚动窗口和之前窗口的重叠百分比 - 使用此公式，我们得到 3 + 5 * 0.7% = 6.5 请求。根据用例，数字可以向上舍入或向下舍入。在我们的示例中，它被四舍五入到 6。 由于速率限制器每分钟最多允许 7 个请求，因此当前的请求可以通过。但是，在收到一个请求后将达到限制。 由于空间的限制，我们将在这里不讨论其他的实现。有兴趣的读者应参考参考资料[9]。这个算法并不完美。它有利有弊。 优点： - 它平滑流量峰值，因为速率是基于上一个窗口的平均速率。 - 内存效率。 缺点： - 它只适用于不那么严格的回顾窗口。它是实际速率的近似值，因为它假定上一个窗口中的请求是均匀分布的。然而，这个问题可能并不像看起来那么严重。根据 Cloudflare [10]所做的实验，在 4 亿个请求中，只有 0.003% 的请求被错误允许或速率限制。 ### 高级架构 速率限制算法的基本思想很简单。在高级级别，我们需要一个计数器来跟踪来自同一用户、IP 地址的多少请求，IP 地址等。如果计数器大于限制，则不允许执行该请求。 我们应该把计数器存放在哪里？由于磁盘访问速度缓慢，使用数据库不是一个好主意。选择内存中的缓存是因为它速度快，并且支持基于时间的过期策略。例如，Redis [11]是实现速率限制的一个流行选择。它是一个内存存储，提供两个命令：INCR 和 EXPIRE。 - INCR：它将存储的计数器增加 1 个。 - EXPIRE：它为计数器设置了一个超时时间。如果超时过期，计数器将自动删除。 图 4-12 显示了速率限制的高级体系结构，其工作原理如下： - 客户端向进行速率限制的中间件发送一个请求。 - 速率限制中间件从 Redis 中的相应桶中获取计数器，并检查是否达到了限制。 - 如果达到了该限制，则该请求将被拒绝。 - 如果未达到限制，则将请求发送到 API 服务器。同时，系统会增加计数器，并将其保存回 Redis。 ## 第 3 步 - 深入设计 图 4-12 中的高级设计并没有回答以下问题： - 如何创建速率限制规则？这些规则存储在哪里？ - 如何处理速率有限的请求？ 在本节中，我们将首先回答有关速率限制规则的问题，然后详细介绍处理速率限制请求的策略。最后，我们将讨论分布式环境中的速率限制、详细的设计、性能优化和监控。 ### 速率限制规则 Lyft 开源了他们的速率限制组件[12]。我们将查看组件的内部，并查看一些速率限制规则的例子： ```yaml domain: messaging descriptors: - key: message_type Value: marketing rate_limit: unit: day requests_per_unit: 5 ``` 在上面的示例中，系统被配置为每天最多允许 5 条营销消息。下面是另一个示例： ```yaml domain: auth descriptors: - key: auth_type Value: login rate_limit: unit: minute requests_per_unit: 5 ``` 此规则显示客户端在 1 分钟内登录超过 5 次。规则通常被写在配置文件中，并保存在磁盘上。 ### 超出速率限制 在请求速率有限的情况下，API 向客户端返回一个 HTTP 响应代码 429（请求过多）。根据用例，我们可能会排队等待稍后处理的受速率限制的请求。例如，如果某些订单由于系统过载而受到限制，我们可能会保留这些订单以便以后处理。 ### 速率限制器标头 客户如何知道它是否被限制了？那么客户端如何知道在被限制之前允许的剩余请求的数量呢？答案在于 HTTP 响应头。速率限制器向客户端返回以下 HTTP 头： *X-Ratelimit-Remaining*：窗口内允许的剩余请求数。 *X-Ratelimit-Limit*：它指示客户端每个时间窗口可以进行多少次呼叫。 *X-Ratelimit-Retry-After*：直到您可以再次发出请求而不被限制而需要等待的秒数。 当用户发送了太多的请求，429 太多的请求错误和 *X-Ratelimit-Retry-After* 头返回给客户端。 ### 详细设计 图 4-13 为系统的详细设计。 - 规则存储在磁盘上。工作人员经常从磁盘中提取规则，并将它们存储在缓存中。 - 当客户端向服务器发送请求时，该请求将首先发送到速率限制器中间件。 - 速率限制器中间件从高速缓存中加载规则。它从 Redis 缓存中获取计数器和最后一个请求时间戳。根据响应，速率限制器决定： - 如果请求没有速率限制，则将其转发到API服务器。 - 如果请求受速率限制，速率限制器向客户端返回 429 太多的请求错误。同时，请求将被删除或转发到队列中。 ### 分布式环境中的限速器 构建一个可以在单一服务器环境中工作的速率限制器并不难。然而，将系统扩展到支持多个服务器和并发线程则是另一回事。有两个挑战： - 竞态 - 同步问题 #### 竞态 如前所述，速率限制器在高级级别的工作原理如下： - 从 Redis 读取计数器值。 - 检查（计数器 + 1）是否超过了阈值。 - 如果没有，在 Redis 中将计数器值增加 1。 竞态可以发生在一个高度并发的环境中，如图 4-14 所示。 假设 Redis 中的计数器值为 3。如果两个请求在读回计数器值之前同时读取计数器值，那么每个请求都将增加一个计数器，并在不检查另一个线程的情况下将其写回来。两个请求（线程）都认为它们有正确的计数器值 4。但是，正确的计数器值应该是 5。 锁是解决竞态的最明显的解决方案。然而，锁会大大降低系统的速度。通常使用两种策略来解决这个问题： Lua 脚本[13]和 Redis [8]中的排序集数据结构。对于对这些策略感兴趣的读者，请参考相应的参考资料[8] [13]。 #### 同步问题 同步性是在分布式环境中需要考虑的另一个重要因素。为了支持数百万用户，一个速率限制器服务器可能不足以处理流量。当使用多个速率限制器服务器时，就需要进行同步。例如，在图 4-15 的左侧，客户端 1 向速率限制器 1 发送请求，而客户端 2 向速率限制器 2 发送请求。由于 web 层是无状态的，因此客户端可以将请求发送到不同的速率限制器，如图 4-15 的右侧所示。如果没有发生同步，则速率限制器 1 不包含有关客户端 2 的任何数据。因此，速率限制器不能正常工作。 一种可能的解决方案是使用粘性会话，允许客户端将流量发送到相同的速率限制器。这种解决方案是不可取的，因为它既不可扩展，也不灵活。一个更好的方法是使用像 Redis 这样的集中式数据存储。设计图如图 4-16 所示。 ### 性能优化 性能优化是系统设计访谈中常见的话题。我们将涵盖两个方面需要改进。 首先，多数据中心的设置对于速率限制器是至关重要的，因为对于位于远离数据中心的用户来说，延迟很高。大多数云服务提供商在世界各地建立了许多边缘服务器位置。例如，截至 2020 年 5 月 20 日，Cloudflare 有 194 个地理上分布的边缘服务器[14]。流量被自动路由到最近的边缘服务器，以减少延迟。 第二，将数据与最终的一致性模型进行同步。如果您不清楚最终的一致性模型，请参阅“第6章：设计键值存储”中的“一致性”部分。 ### 监控 在限速器放置到位后，收集分析数据来检查限速器是否有效是很重要的。首先，我们想确保： - 速率限制算法是有效的。 - 速率限制规则是有效的。 例如，如果速率限制规则过于严格，则会删除许多有效的请求。在这种情况下，我们想放松一点规则。在另一个例子中，我们注意到，当流量突然增长时，我们的速率限制器就会变得无效。在这种情况下，我们可以替换该算法来支持突发流量。令牌桶在这里很适合你。 ## 第 4 步 - 总结 在本章中，我们讨论了不同的速率限制算法及其优缺点。讨论的算法包括： - 令牌桶 - 漏桶 - 固定窗口 - 滑动窗口日志 - 滑动窗口计数器 然后，我们讨论了系统架构、分布式环境中的限速器、性能优化和监控。与任何系统设计面试问题类似，如果时间允许，你还可以提到一些额外的谈话要点： - 硬速率限制和软速率限制。 - 硬：请求的数量不能超过该阈值。 - 软：请求可以在短时间内超过阈值。 - 在不同的层次上进行速率限制。在本章中，我们只讨论了在应用程序级别上的速率限制（HTTP：第7层）。可以在其他层上应用速率限制。例如，您可以使用Iptables [15]（IP：层3）通过IP地址应用速率限制。注：开放系统互连模型(OSI 模型）有 7 层[16]：第 1 层：物理层，第 2 层：数据链路层，第 3 层：网络层，第 4 层：传输层，第 5 层：会话层，第 6 层：表示层，第 7 层：应用层。 - 避免被速率限制。使用最佳实践设计您的客户端： - 使用客户端缓存以避免频繁进行API调用。 - 了解该限制，并且不会在短时间内发送太多请求。 - 包含捕获异常或错误的代码，以便您的客户端可以优雅地从异常中恢复。 - 添加足够的关闭时间来重试逻辑。 祝贺你能走到这一步！现在拍拍自己的背。干得好！ # 第 5 章：设计一致性哈希 为了实现水平扩展，必须在服务器之间有效和均匀地分发请求/数据。一致性哈希是实现这一目标的一种常用技术。但首先，让我们深入看看这个问题。 ## 重散列问题 如果您有 n 个缓存服务器，那么平衡负载的一种常用方法是使用以下哈希方法： 服务器索引 = 哈希（键）% N，其中 N 是服务器池的大小。 让我们用一个例子来说明它是如何工作的。如表 5-1 所示，我们有 4 个服务器和 8 个字符串键。 | key | hash | hash % 4 | | ---- | -------- | -------- | | key0 | 18358617 | 1 | | key1 | 26143584 | 0 | | key2 | 18131146 | 2 | | key3 | 35863496 | 0 | | key4 | 34085809 | 1 | | key5 | 27581703 | 3 | | key6 | 38164978 | 2 | | key7 | 22530351 | 3 | 要获取存储密钥的服务器，我们执行模块化操作 f(key) % 4。例如，hash(key0) % 4 = 1 意味着客户端必须与服务器 1 联系以获取缓存的数据。图 5-1 显示了基于表 5-1 的键的分布情况。 当服务器池的大小固定，且数据分布均匀时，这种方法工作得很好。但是，当添加新服务器或删除现有服务器时，就会出现问题。例如，如果服务器 1 脱机，则服务器池的大小将变为 3。使用相同的哈希函数，我们可以为一个键得到相同的哈希值。但是应用模块化操作给了我们不同的服务器索引，因为服务器的数量减少了 1 个。通过应用 hash % 3，结果得到如表 5-2 所示： | key | hash | hash % 3 | | ---- | -------- | -------- | | key0 | 18358617 | 0 | | key1 | 26143584 | 0 | | key2 | 18131146 | 1 | | key3 | 35863496 | 2 | | key4 | 34085809 | 1 | | key5 | 27581703 | 0 | | key6 | 38164978 | 1 | | key7 | 22530351 | 0 | 图 5-2 显示了基于表 5-2 的键的新分布。 如图 5-2 所示，大多数密钥都被重新分配，而不仅仅是最初存储在离线服务器（服务器 1）中的那些密钥。这意味着当服务器 1 脱机时，大多数缓存客户端将连接到错误的服务器来获取数据。这将导致一场高速缓存丢失的风暴。一致性散列是缓解这一问题的一种有效技术。 ## 一致性哈希 引用维基百科的话：“一致哈希是一种特殊的哈希，当重新使用哈希表的大小并使用一致哈希时，平均只需要重新映射 k / n 键，其中 k 是键的数量，n 是插槽的数量。相比之下，在大多数传统的哈希表中，数组槽数量的变化会导致几乎所有的键被重新映射[1]”。 ## 哈希空间和哈希环 现在我们理解了一致散列的定义，让我们来了解它是如何工作的。假设 SHA-1 被用作哈希函数 f，并且哈希函数的输出范围为： x0、x1、x2、x3、...，xn。在密码学中，SHA-1 的哈希空间从 0 扩展到 2^160 - 1。这意味着 x0 对应 0，xn 对应 2^160 - 1，中间的所有其他哈希值都落在 0 到 2^160 - 1 之间。图 5-3 显示了哈希空间。 通过收集两端，我们得到了一个哈希环，如图 5-4 所示： ## 哈希服务器 使用相同的哈希函数 f，我们根据服务器的 IP 或名称将服务器映射到环上。图 5-5 显示了 4 台服务器被映射到哈希环上。 ## 哈希键 值得一提的是，这里使用的哈希函数与“重哈希问题”中的一个不同，并且没有模块化操作。如图 5-6 所示，4 个缓存键（键 0、键 1、键 2 和键 3）被散列到哈希环上 ## 服务器查找 为了确定密钥存储在哪个服务器上，我们从环上的密钥位置顺时针方向移动，直到找到服务器。图 5-7 解释了这个过程。顺时针方向，键 0 存储在服务器 0 上，密钥 1 存储在服务器 1 上，密钥 2 存储在服务器 2 上，密钥 3 存储在服务器 3 上。 ## 添加服务器 使用上述逻辑，添加一个新的服务器将只需要重新分配一小部分密钥。 在图 5-8 中，在添加了一个新的服务器 4 后，只需要重新分配密钥 0。k1、k2 和 k3 保持在相同的服务器上。让我们仔细看看它的逻辑。在添加服务器 4 之前，密钥 0 将存储在服务器 0 上。现在，键 0 将存储在服务器 4 上，因为服务器 4 是它从环上键 0 的位置顺时针方向遇到的第一个服务器。其他的键不基于一致的哈希算法进行重新分配。 ## 删除服务器 当删除服务器时，只有一小部分键需要使用一致的哈希方式进行重新分配。在图 5-9 中，当服务器 1 被删除时，只能将键 1 重新映射到服务器 2。其余的键不受影响。 ## 基本方法中的两个问题 一致哈希算法是由 MIT [1]的 Karger 等人提出的。基本步骤是： - 使用均匀分布的哈希函数将服务器和密钥映射到环上。 - 要找出键映射到哪个服务器，请从键位置顺时针方向移动，直到找到环上的第一个服务器。 用这种方法确定了两个问题。首先，考虑到可以添加或删除一个服务器，因此不可能在所有服务器的环上保持相同大小的分区。分区是相邻服务器之间的散列空间。分配给每个服务器的环上的分区的大小可能非常小或相当大。在图 5-10 中，如果删除了 s1，则 s2 的分区（用双向箭头高亮显示）是 s0 和 s3 的分区的两倍大。 其次，在环上有可能有一个不均匀的密钥分布。例如，如果服务器被映射到图 5-11 中列出的位置，那么大多数密钥都存储在服务器 2 上。但是，服务器 1 和服务器 3 没有数据。 使用一种称为虚拟节点或副本的技术来解决这些问题。 ## 虚拟节点 一个虚拟节点是指真实的节点，每个服务器由环上的多个虚拟节点表示。在图 5-12 中，服务器 0 和服务器 1 都有 3 个虚拟节点。3 是任意选择的；在现实系统中，虚拟节点的数量要大得多。我们没有使用 s0，而是使用 s0_0、s0_1 和 s0_2 来表示环上的服务器 0。类似地，s1_0、s1_1 和 s1_2 表示环上的服务器 1。对于虚拟节点，每个服务器都负责多个分区。标签为 s0 的分区（边缘）由服务器 0 管理。另一方面，带有标签 s1 的分区由服务器 1 管理。 为了找到密钥存储在哪个服务器上，我们从密钥的位置开始，沿顺时针方向前进，并找到在环上遇到的第一个虚拟节点。在图 5-13 中，为了找出 k0 存储在哪个服务器上，我们从 k0 的位置开始顺时针方向找到虚拟节点 s1_1，即服务器 1。 随着虚拟节点数量的增加，密钥的分布变得更加平衡。这是因为虚拟节点越多的话，标准差越小，导致数据分布越平衡。标准差衡量的是数据的分布方式。在线研究[2]进行的一项实验结果显示，对于 1 个或 200 个虚拟节点，标准差在平均值的 5%（200 个虚拟节点）和 10%（100 个虚拟节点）之间。当我们增加虚拟节点的数量时，标准差将会更小。但是，需要更多的空间来存储关于虚拟节点的数据。这是一种权衡，我们可以调整虚拟节点的数量来适应我们的系统需求。 ## 查找受影响的密钥 当添加或删除服务器时，需要重新分配一小部分数据。我们如何找到受影响的范围来重新分配密钥？ 在图 5-14 中，服务器 4 被添加到环上。受影响的范围从 s4（新添加的节点）开始，然后绕着环逆时针移动，直到找到一个服务器（s3）。因此，位于 s3 和 s4 之间的密钥需要重新分配到 s4。 如图 5-15 所示，删除服务器（s1）时，受影响的范围从 s1（移除节点）开始，绕环逆时针移动，直到找到服务器（s0）。因此，位于 s0 和 s1 之间的密钥必须被重新分配到 s2 中。 ## 总结 在本章中，我们对一致的散列进行了深入的讨论，包括为什么需要它以及它如何工作。一致散列的好处包括： - 当添加或删除服务器时，将重新分配最小化的密钥。 - 由于数据的分布更为均匀，所以很容易进行水平缩放。 - 缓解了热点的关键问题。对特定碎片的过度访问可能会导致服务器过载。想象一下，凯蒂·佩里、贾斯汀·比伯和 Lady Gaga 的数据都在同一个碎片。一致的散列可以通过更均匀地分布数据来缓解这个问题。 一致散列广泛应用于现实世界的系统，包括一些值得注意的： - 分区组件的 Amazon 的 Dynamo 数据库[3] - Apache Cassandra 中的跨集群数据分区[4] - Discord 聊天应用程序[5] - Akamai 内容交付网络[6] - Maglev 网络负载平衡器[7] 祝贺取得这一步！现在拍拍自己的背。干得好！ # 第 6 章：设计一个键值存储 键值存储，也称为键值数据库，是一个非关系数据库。每个唯一标识符都被存储为一个具有关联值的键。这种数据配对被称为“键-值”对。 在键-值对中，键必须是唯一的，并且可以通过键访问与键关联的值。键可以是纯文本值或散列值。出于性能的原因，短键效果更好。键是什么样的？这里是一些例子： - 纯文本键："last_logged_in_at" - 哈希键：253DDEC4 键-值对中的值可以是字符串、列表、对象等。在键值存储中，该值通常被视为一个不透明的对象，如 Amazon Dynamo[1]、Memcached[2]、Redis [3]等。 下面是一个键值存储区中的一个数据片段： | 键 | 值 | | ---- | ----- | | 145 | john | | 147 | bob | | 160 | Julia | 在本章中，您被要求设计一个支持以下操作的键值存储： - put(key, value) // 插入与“键”关联的“值” - get(key) // 获取与“键”关联的“值” ## 了解存在的问题，确定设计范围 没有什么完美的设计。每个设计都实现了关于读、写和内存使用的权衡的特定平衡。另一个必须做出的权衡是在一致性和可用性之间。在本章中，我们设计了一个包含以下特征的键值存储： - 键值对的大小很小：小于 10 KB。 - 能够存储大数据 - 高可用性：系统响应迅速，即使是在故障期间。 - 高可伸缩性：该系统可以进行缩放，以支持大型数据集。 - 自动缩放：服务器的添加/删除应该根据流量自动进行。 - 可调性的一致性。 - 低延迟。 ## 单服务器密钥值存储 开发驻留在单个服务器中的键值存储区很容易。一种直观的方法是将键值对存储在哈希表中，它将所有内容都保存在内存中。尽管内存访问速度很快，但由于空间的限制，可能无法在内存中安装所有内容。可以进行两种优化来在单个服务器中容纳更多的数据： - 数据压缩 - 只存储内存中常用的数据，其余的存储在磁盘上。 即使进行了这些优化，单个服务器也可以很快达到其容量。需要一个分布式的键值存储来支持大数据。 ## 分布式密钥值存储 分布式密钥值存储也称为分布式散列表，它将密钥值对分布到许多服务器上。在设计分布式系统时，理解 CAP（一致性、可用性、分区容忍性）定理很重要的。 ## CAP 定理 CAP定理指出，一个分布式系统不可能同时提供这三种保证中的两种以上：一致性、可用性和分区容忍性。让我们建立几个定义。 **一致性**：一致性意味着所有客户端都能同时看到相同的数据，无论它们连接到哪个节点。 **可用性**：可用性意味着任何请求数据的客户端，即使某些节点关闭，也会得到响应。 **分区容忍性**：分区表示两个节点之间的通信中断。分区容忍性意味着系统不顾网络分区而继续运行。 CAP 定理指出，必须牺牲这三个属性中的一个来支持这 3 个属性中的 2 个，如图 6-1 所示。 现在，键值存储是根据它们支持的两个 CAP 特征进行分类的： **CP（一致性和分区容忍性）系统**： CP 键值存储支持一致性和分区容忍性，同时牺牲了可用性。 **AP（可用性和分区容忍性）系统**：AP 键值存储支持可用性和分区容忍性，同时牺牲一致性。 **CA（一致性和可用性）系统**：CA 密钥值存储支持一致性和可用性，同时牺牲分区容忍性。由于网络故障是不可避免的，所以一个分布式系统必须容忍网络分区。因此，CA系统不能存在于现实世界的应用程序中。 你在上面读到的主要是定义部分。为了让它更容易理解，让我们来看看一些具体的例子。在分布式系统中，数据通常会被复制多次。假设数据被复制到三个复制节点 n1、n2 和 n3 上，如图 6- 2 所示。 ## 理想情况 在理想的世界中，网络分区永远不会发生。写入 n1 的数据会自动复制到 n2 和 n3。同时实现了一致性和可用性。 ## 现实世界的分布式系统 在分布式系统中，分区无法避免，当分区发生时，我们必须在一致性和可用性之间进行选择。在图 6-3 中，n3 会下降，无法与 n1 和 n2 进行通信。如果客户端将数据写入 n1 或 n2，则数据不能传播到 n3。如果数据写入 n3 但没有传播到 n1 和 n2，n1 和 n2 的数据将过时。 如果我们选择一致性而不是可用性（CP 系统），我们必须阻止对 n1 和 n2 的所有写操作，以避免这三台服务器之间的数据不一致，从而使得系统不可用。银行系统通常有极高的一致性要求。例如，对于银行系统显示最新的余额信息是至关重要的。如果由于网络分区而出现不一致，则银行系统将在解决该不一致之前返回一个错误。 但是，如果我们选择可用性而不是一致性（AP 系统），系统就会继续接受读取，即使它可能会返回陈旧的数据。对于写操作，n1 和 n2 将继续接受写操作，当网络分区被解析时，数据将被同步到 n3。 选择正确的 CAP 可以保证适合您的用例是构建分布式键值存储的重要步骤。你可以和面试官讨论这个问题，并相应地设计这个系统。 ## 系统组件 在本节中，我们将讨论以下核心组件和技术用于构建一个键值存储： - 数据分区 - 数据复制 - 一致性 - 不一致性解决方案 - 处理失败 - 系统架构图 - 写路径 - 读路径 下面的内容很大程度上是基于三个流行的键值存储系统：Dynamo[4]，Cassandra[5]和 BigTable[6]。 ### 数据分区 对于大型应用程序，在单个服务器中拟合完整的数据集是不可行的。实现这一点的最简单的方法是将数据分割成更小的分区，并将它们存储在多个服务器中。在分区数据时存在两个挑战： - 跨多个服务器均匀地分发数据。 - 在添加或删除节点时，最小化数据移动。 第 5 章中讨论的一致散列是解决这些问题的一种好技术。让我们重新讨论一致的散列在高级级别上是如何工作的。 - 首先，服务器被放置在一个哈希环上。在图 6-4 中，由 s0、s1、...，s7 表示的 8 个服务器被放置在哈希环上。 - 接下来，一个键被散列在同一个环上，它被存储在沿顺时针方向移动时遇到的第一个服务器上。例如，键 0 使用此逻辑存储在 s1 中。 对分区数据使用一致的哈希方式具有以下优点： **自动缩放**：服务器可以根据负载自动添加和删除服务器。 **异构性**：服务器的虚拟节点数量与服务器容量成正比。例如，为具有更高容量的服务器分配了更多的虚拟节点。 ### 数据复制 为了实现高可用性和可靠性，数据必须在 N 台服务器上进行异步复制，其中 N 是一个可配置的参数。使用以下逻辑选择这 N 个服务器：在一个键映射到哈希环上的一个位置后，从该位置顺时针走，并选择环上的第一个 N 个服务器来存储数据副本。在图 6-5（N = 3）中，键 0 在 s1、s2 和 s3 处被复制。 对于虚拟节点，环上的第一个 N 个节点可能由少于 N 个的物理服务器拥有。为了避免这个问题，我们在执行顺时针行走逻辑时只选择唯一的服务器。 同一数据中心中的节点经常因停电、网络问题、自然灾害等原因而同时发生故障。为了获得更好的可靠性，副本被放置在不同的数据中心中，数据中心通过高速网络连接。 ### 一致性 由于数据可以在多个节点上进行复制，因此必须跨副本进行同步。仲裁共识可以保证读操作和写操作的一致性。让我们先建立几个定义。 **N** = 副本数量 **W** = 大小为 W 的写仲裁。要认为写操作成功，必须从 W 副本中确认写操作。 **R** = 大小为 R 的读取仲裁。要认为读取操作成功，读取操作必须等待至少 R 个副本的响应。 考虑以下图 6-6 所示的 N = 3 示例。 W = 1 并不意味着数据被写在一台服务器上。例如，使用图 6-6 中的配置，数据在 s0、s1 和 s2 处被复制。W = 1 表示协调器在认为写操作成功之前必须至少收到一次确认。例如，如果我们从 s1 得到了一个确认，我们就不再需要等待来自 s0 和 s2 的确认。协调器充当客户机和节点之间的代理。 W、R 和 N 的配置是延迟和一致性之间的典型权衡。如果是 W = 1 或 R = 1，则会快速返回一个操作，因为协调器只需要等待来自任何一个副本的响应。如果是 W 或 R > 1，则系统将提供更好的一致性；但是，查询将会变慢，因为协调器必须等待来自最慢的副本的响应。 如果是 W + R > N，则保证了较强的一致性，因为必须至少有一个重叠的节点具有最新的数据，以确保一致性。 如何配置 N、W 和 R 以适应我们的用例？这里是一些可能的设置： 如果 R = 1 和 W = N，系统被优化为一个快速读取。 如果 W = 1 和 R = N，则系统进行快速写入优化。 如果为 W + R > N，则保证了强一致性（通常为 N = 3，W = R = 2）。 如果是 W + R <= N，则不能保证强一致性。 根据需求，我们可以调整 W、R，N 的值，以达到所需的一致性水平。 #### 一致性模型 一致性模型是在设计键值存储时需要考虑的另一个重要因素。一致性模型定义了数据一致性的程度，并且存在广泛的一致性模型： - 强一致性：任何读取操作返回一个与最更新的写数据项结果对应的值。客户端从不看不到过时的数据。 - 弱一致性：后续的读取操作可能看不到最新更新的值。 - 最终一致性：这是一种特殊的弱一致性形式。如果有足够的时间，将传播所有更新，并且所有副本都是一致的。 强一致性通常是通过强制一个副本不接受新的读/写来实现的，直到每个副本都同意当前的写。这种方法对于高可用性的系统并不理想，因为它可能会阻止新的操作。Dynamo 和 Cassandra 采用最终一致性，这是我们的键值存储推荐的一致性模型。在并发写入中，最终一致性允许不一致的值进入系统，并强制客户端读取值以协调。下一节将解释如何对版本控制进行协调。 ### 不一致性解决方案：版本控制 复制提供了高可用性，但会导致副本之间的不一致。版本控制和向量锁用于解决不一致的问题。版本控制意味着将每个数据修改视为一个新的不可变的数据版本。在讨论版本控制之前，让我们使用一个示例来解释不一致性是如何发生的： 如图 6-7 所示，副本节点 n1 和 n2 都具有相同的值。让我们把这个值称为原始值。服务器 1 和服务器 2 为 *get("name")* 操作获得相同的值。 接下来，服务器 1 将名称更改为“johnSanFrancisco”，服务器 2 将名称更改为“johnNewYork”，如图 6-8 所示。这两个更改将同时执行。现在，我们有了相互冲突的值，称为版本 v1 和 v2。 在本例中，可以忽略原始值，因为修改是基于该值的。然而，目前还没有明确的方法来解决最后两个版本的冲突。为了解决这个问题，我们需要一个能够检测冲突并协调冲突的版本控制系统。矢量时钟是解决这一问题的一种常用技术。让我们来看看矢量时钟是如何工作的。 矢量时钟是与数据项相关联的[服务器、版本]对。它可以用于检查一个版本是否优先、成功或与其他版本发生冲突。 假设一个向量时钟由D（[S1，v1]，[S2，v2]，...，[Sn，vn]）表示，其中 D 是一个数据项，v1 是一个版本计数器，s1 是一个服务器号，等等。如果数据项 D 被写入服务器 Si，则系统必须执行以下任务之一。 - 增量 vi，如果[Si，vi]存在。 - 否则，请创建一个新的条目[Si，1]。 上述抽象逻辑通过一个如图 6-9 所示的具体示例进行了解释。 1. 客户端将数据项 D1 写入系统，并且写入由服务器 Sx 处理，服务器 Sx 现在具有矢量时钟 D1[（Sx，1）]。 2. 另一个客户端读取最新的 D1，将其更新到 D2，并将其写回来。D2 从 D1 生成，所以它覆盖了 D1。假设写入由同一服务器 Sx 处理，该服务器现在具有矢量时钟D2（[Sx，2]）。 3. 另一个客户端读取最新的 D2，将其更新到 D3，并将其写回来。假设写入操作由服务器 Sy 处理，该服务器现在具有向量时钟 D3（[Sx，2]，[Sy，1]）)。 4. 另一个客户端读取最新的 D2，将其更新到 D4，并将其写回。假设写入操作由服务器 Sz 处理，而它现在具有 D4（[Sx、2]、[Sz、1]）)。 5. 当另一个客户端读取 D3 和 D4 时，它发现一个冲突，这是由数据项被 Sy 和 Sz 修改 D2 引起的。该冲突由客户端解决，并将更新后的数据发送到服务器。假设写入由 Sx 处理，它现在有 D5（[Sx、3]、[Sy、1]、[Sz、1]）。我们将很快解释如何检测冲突。 使用向量时钟，很容易看出版本 X 是版本 Y 的祖先（即没有冲突），如果版本参与者的版本计数器大于或等于版本 X。例如，向量时钟 D（[s0、1]，[s1、1]）] 是 D 的祖先（[s0、1]，[s1、2]）。因此，没有记录任何冲突。 类似地，如果 Y 的 X 中有计数器小于对应计数器，则 X 是兄弟（即存在冲突）。例如，以下两个矢量时钟表示存在冲突： D（[s0、1]、[s1、2]）和D（[s0、2]、[s1、1]）。 尽管矢量时钟可以解决冲突，但也有两个显著的缺点。首先，向量时钟增加了客户端的复杂性，因为它需要实现冲突解决逻辑。 第二，向量时钟中的[服务器：版本]对可以快速增长。为了解决这个问题，我们为长度设置了一个阈值，如果它超过了限制，则删除最古老的对。这可能导致和解的效率低下，因为无法准确地确定后代关系。然而，基于 Dynamo 论文[4]，亚马逊在生产中还没有遇到这个问题；因此，对大多数公司来说，这可能是一个可接受的解决方案。 ### 处理失败 与任何大规模的大型系统一样，故障不仅不可避免，而且很常见。处理故障场景非常重要。在本节中，我们首先将介绍检测故障的技术。然后，我们将讨论常见的故障解决策略。 #### 故障探测 在分布式系统中，因为另一个服务器这么说，所以要相信服务器停机是不够的。通常，它需要至少两个独立的信息源来标记一个服务器。 如图 6-10 所示，全对全多播是一个简单的解决方案。但是，当系统中存在许多服务器时，这是低效的。 一个更好的解决方案是使用分散的故障检测方法，如 Gossip 协议。Gossip 协议的工作原理如下： - 每个节点维护一个节点成员关系列表，其中包含成员 id 和心跳计数器。 - 每个节点定期地增加其心跳计数器。 - 每个节点周期性地向一组随机节点发送心跳，这些随机节点依次传播到另一组节点。 - 一旦节点收到心跳，成员列表将更新为最新的信息。 - 如果心跳没有增加超过预定义的周期，则认为该成员为脱机。 如图 6-11 所示： - 节点 s0 维护左侧显示的节点成员关系列表。 - 节点 s0 注意到节点 2 的（成员 ID = 2）心跳计数器已经很长时间没有增加了。 - 节点 s0 向包含 s2 信息的心跳发送到一组随机节点。一旦其他节点确认 s2 的心跳计数器有很长时间没有更新，节点 s2 将被标记下来，并将该信息传播到其他节点。 #### 处理临时故障 在通过 Gossip 协议检测到故障后，系统需要部署某些机制，以确保可用性。在严格的仲裁方法中，可以阻止读取和写操作，如仲裁共识部分所示。 一种被称为“草率群体(sloppy quorum)”[4]的技术被用来提高可用性。系统不是强制执行仲裁要求，而是选择第一个 W 健康服务器进行写，第一个 R 健康服务器在哈希环上读取。脱机服务器将被忽略。 如果服务器由于网络或服务器故障而不可用，另一个服务器将临时处理请求。当停机服务器启动时，更改将被推迟，以实现数据一致性。这个过程被称为暗示交接(hinted handoff)。由于 s2 在图 6- 12 中不可用，所以读写将由 s3 临时处理。当 s2 恢复上线时，s3 会将把数据交还给 s2。 #### 处理永久故障 提示切换用于处理临时故障。如果一个复制副本永久不可用怎么办？为了处理这种情况，我们实现了一个反熵协议来保持副本的同步。反熵包括比较副本上的每个数据片段，并将每个副本更新到最新版本。Merkle 树用于不一致性检测和最小化传输的数据量。 引用维基百科[7]的话：“哈希树或 Merkle 树是一种树，其中每个非叶子节点都用其子节点的标签或值（如果是叶子）的哈希进行标记。哈希树允许对大型数据结构的内容进行高效和安全的验证”。 假设密钥空间从 1 到 12，下面的步骤将展示如何构建 Merkle 树。有突出显示的方框表示不一致。 步骤 1：将键空间划分为桶（示例中为 4），如图 6-13 所示。桶被用作根级节点，以保持树的有限深度。 步骤 2：创建桶后，将使用统一散列方法对桶中的每个键进行散列（图 6-14)。 步骤 3：为每个桶创建单个哈希节点（图 6-15)。 步骤 4：通过计算子项的哈希值，使树向上构建直到根值（图 6-16)。 要比较两个 Merkle 树，首先要比较根散列。如果根散列匹配，则两个服务器具有相同的数据。如果根散列不同意，则比较左子散列，然后比较右子散列。您可以遍历树来查找哪些桶没有同步，并且只同步这些桶。使用 Merkle 树，需要同步的数据量与两个副本之间的差异成正比，而不是它们所包含的数据量。在现实世界的系统中，桶的大小相当大。例如，一个可能的配置是每 10 亿个键有 100 万个桶，因此每个桶只包含 1000 个键。 #### 处理数据中心中断 由于停电、网络停电、自然灾害等原因，可能会发生数据中心停电。要构建一个能够处理数据中心中断的系统，跨多个数据中心复制数据非常重要。即使一个数据中心完全离线，用户仍然可以通过其他数据中心访问数据。 ### 系统架构图 现在我们已经讨论了在设计键值存储时的不同技术考虑，我们可以将重点转移到架构图上，如图 6-17 所示。 该架构的主要特性如下： - 客户端通过简单的 api 与键值存储进行通信：*get(key)* 和 *put(key, value)*。 - 协调器是作为客户端和键值存储之间的代理的节点。 - 节点使用一致性散列分布在一个环上。 - 该系统是完全去中心的，因此可以自动添加和移动节点。 - 数据将在多个节点上进行复制。 - 不存在单点故障，因为每个节点都有相同的责任集。 由于设计是去中心的，每个节点执行许多任务，如图 6-18 所示。 ### 写路径 图 6-19 解释了将写入请求定向到特定节点后发生的情况。请注意，建议的写/读路径的设计主要是基于 Cassandra[8] 的架构。 1. 写入请求被持久地保存在提交日志文件上。 2. 数据被保存在内存缓存中。 3. 当内存缓存已满或达到预定义的阈值时，数据将被刷新到磁盘上的 SSTable [9]。注意：排序字符串表（SSTable）是<键、值>对的排序列表。如果您有兴趣了解更多关于 SStable 的读者，请参阅参考材料[9]。 ### 读路径 读请求定向到特定节点后，它首先检查数据是否在内存缓存中。如果是这样，则数据将返回给客户端，如图 6-20 所示。 如果数据不在内存中，则将从磁盘中检索该数据。我们需要一种有效的方法来找出哪个 SSTable 包含该密钥。布隆（Bloom）过滤器[10]通常被用来解决这个问题。 当数据不在内存中时，读取路径如图 6-21 所示。 1. 系统首先检查内存中是否有数据。如果没有，请转到步骤2。 2. 如果数据不在内存中，系统将检查布隆过滤器。 3. 布隆过滤器用于找出哪些 SSTables 可能包含该键。 4. SSTBables 返回数据集的结果。 5. 该数据集的结果将返回给客户端。 ## 总结 本章涵盖了许多概念和技术。要刷新内存，下表总结了用于分布式键值存储的特性和相应的技术。 | 目标/问题 | 技术 | | ----------------------- | --------------------------------------------------------- | | 存储大数据的能力 | 使用一致性哈希来在服务器间扩展负载 | | 高可用性读取 | 数据复制、多数据中心配置 | | 高可用性写入 | 使用向量时钟来进行版本和冲突解析 | | 数据集分片 | 一致性哈希 | | 增加可扩展性 | 一致性哈希 | | 异质性（Heterogeneity） | 一致性哈希 | | 可调一致性 | 法定人数共识 | | 处理临时失败 | 懒散法定人数（Sloppy quorum）和暗示交接（hinted handoff） | | 处理永久失败 | Merkle 树 | | 处理数据中心断连 | 跨数据中心复制 | # 第 7 章：在分布式系统里设计一个唯一 ID 生成器 在本章中，我们将要求您在分布式系统中设计一个唯一 ID 生成器。您的第一个想法可能是在传统数据库中使用带有 auto_increment 属性的主键。但是，auto_increment 在分布式环境中不起作用，因为单个数据库服务器不够大，并且在多个数据库中以最小的延迟跨多个数据库生成唯一的 id 具有挑战性。 以下是几个独特的 id 的例子： ## 第 1 步 - 理解问题和建立设计域 询问澄清问题是解决任何系统设计面试问题的第一步。以下是一个候选人-面试者互动的例子： **候选人**：唯一 ID 的特点是什么？ **面试官**：ID 必须是唯一的和可排序的。 **候选人**：对于每条新记录，ID 是否增加 1？ **面试官**：ID 随时间增加，但不一定只增加 1。在晚上创建的 ID 比在当天早上创建的 ID 要大。 **候选人**：ID 只包含数值吗？ **面试官**：是的，没错。 **候选人**：ID 长度的要求是什么？ **面试官**：ID 应该适合于 64 位的位置。 **候选人**：这个系统的规模是多少？ **面试官**：该系统应该能够每秒生成 10,000 个 ID 以上是一些你可以问面试官的样本问题。理解需求和澄清歧义是很重要的。对于这个面试问题，要求如下： - ID 必须是唯一的。 - ID 仅为数值。 - ID 适合于 64 位。 - ID 是按日期排序的。 - 每秒能够生成超过 10,000 个唯一的 ID。 ## 第 2 步 - 提出高级设计并获得支持 可以使用多个选项在分布式系统中生成唯一的 ID。我们考虑的选项是： - 多主复制 - 通用唯一标识符（UUID） - 票证服务器 - 推特雪花方法 让我们看看每一个，它们是如何工作的，以及每个选项的优缺点。 ### 多主复制 如图 7-2 所示，第一种方法是多主服务器复制。 此方法使用了数据库的自动增量特性。我们没有将下一个 ID 增加 1，而是将其增加 k，其中 k 是正在使用的数据库服务器的数量。如图 7-2 所示，要生成的下一个 ID 等于同一台服务器上的前一个 ID 加上 2。这解决了一些可伸缩性问题，因为 ID 可以随着数据库服务器的数量而扩展。然而，这种策略有一些主要的缺点： - 很难扩展到多个数据中心 - ID 不能跨多个服务器随时间增加。 - 当添加或删除服务器时，它不能正常扩展。 ### UUID UUID 是获取唯一 ID 的另一种简单方法。UUID 是一个 128 位的数字，用于识别计算机系统中的信息。UUID 发生碰撞的可能性很低。引用维基百科的话，“在大约 100 年里每秒生成 10 亿个 UUID 后，创建一个重复的概率将达到 50%”[1]。 这里是 UUID 的一个例子： 09c93e62-50b4-468d-bf8a-c07e1040bfb2。UUID 可以独立生成，而不需要服务器之间的协调。图 7-3 显示了 UUID 的设计。 在这个设计中，每个 web 服务器都包含一个 ID 生成器，并且一个 web 服务器负责独立地生成 ID。 优点： - 生成 UUID 很简单。服务器之间不需要进行协调，因此不会出现任何同步问题。 - 该系统很容易扩展，因为每个 web 服务器都负责生成它们所使用的 ID。ID 生成器可以很容易地扩展到 web 服务器。 缺点： - ID 有 128 位长，但我们的要求是 64 位。 - ID 不会随时间的推移而增加。 - ID 可以是非数字的。 ### 票证服务器 票证服务器（ticket servers）是生成唯一 ID 的另一种有趣的方法。Flicker 开发了票证服务器来生成分布式主密钥[2]。值得一提的是，这个系统是如何工作的。 其想法是在单个数据库服务器（票证服务器）中使用集中的自动增量功能。要了解更多相关信息，请参考 flicker 的工程博客文章[2]。 优点： - 数字 ID。 - 它易于实现，并且适用于中小型应用程序。 缺点： - 单点故障。单票证服务器意味着如果票证服务器宕机，所有依赖于它的系统都将面临问题。为了避免单点故障，我们可以设置多个记录单服务器。然而，这将引入新的挑战，如数据同步。 ### 推特雪花算法 上面提到的方法给了我们一些关于不同的 ID 生成系统如何工作的想法。但是，它们都不满足我们的具体要求；因此，我们需要另一种方法。推特独特的 ID 生成系统“雪花”[3]非常鼓舞人心，可以满足我们的需求。 分而治之是我们的朋友。我们不是直接生成 ID，而是将 ID 划分为不同的部分。图 7-5 显示了一个 64 位 ID 的布局。 | 0 | 时间戳 | 数据中心 ID | 机器 ID | 序列号 | | ----- | ------- | ----------- | ------- | ------- | | 1 bit | 41 bits | 5 bits | 5 bits | 12 bits | 每个部分的解释如下。 - 符号位：1 位。它将始终是 0。这是留给将来使用的。它可以被用于区分有符号数字和无符号数字。 - 时间戳： 41 位。从这个时代(epoch)或自定义时代开始的毫秒。我们使用 Twitter 雪花默认时代 1288834974657，相当于 2010 年 11 月 04 日，01：42：54 UTC。 - 数据中心 ID： 5 位，这给了我们 2 ^ 5 = 32 个数据中心。 - 机器 ID： 5 位，每个数据中心有 2 ^ 5 = 32 台机器。 - 序列号： 12 位。对于在该机器/进程上生成的每个 ID，序列号将增加 1。该数字被重置为每毫秒间隔 0 次。 ## 第 3 步 - 深入设计 在高级设计中，我们讨论了在分布式系统中设计一个独特的 ID 生成器的各种选项。我们选择了一种基于 Twitter 雪花 ID 生成器的方法。让我们深入研究一下这个设计吧。为了刷新我们的记忆，下面重新列出了设计图。 | 0 | 时间戳 | 数据中心 ID | 机器 ID | 序列号 | | ----- | ------- | ----------- | ------- | ------- | | 1 bit | 41 bits | 5 bits | 5 bits | 12 bits | 数据中心 ID 和机器 ID 在启动时选择，通常在系统运行后进行修复。数据中心 ID 和机器 ID 中的任何更改都需要仔细检查，因为这些值中的意外更改可能会导致 ID 冲突。时间戳和序列号是在 ID 生成器运行时生成的。 ### 时间戳 最重要的 41 位构成了时间戳部分。随着时间戳随时间的增长，ID 可以按时间排序。图 7-7 显示了一个如何将二进制表示法转换为 UTC 的示例。您还可以使用类似的方法将 UTC 转换为二进制表示。 ``` 0-00100010101001011010011011000101101011000-01010-01100-000000000000 ↓ 转为十进制 297616116568 ↓ + Twitter 时代 1288834974657 1586451091225 ↓ 将毫秒转为 UTC 时间 Apr 09 2020 16:51:31 UTC ``` 可以用 41 位表示的最大时间戳为：2 ^ 41 - 1 = 2199023255551 毫秒（ms），这给了我们： ~ 69年= 2199023255551 ms / 1000 秒 / 365 天 / 24 小时 / 3600 秒。这意味着 ID 生成器将工作 69 年，并且有一个接近今天的日期的自定义历元时间的话，将会延迟溢出时间。69 年后，我们将需要一个新的时代时间或采用其他技术来迁移 ID。 ### 序列号 序列号是 12 位，给我们 2 ^ 12 = 4096 组合。除非在同一服务器上在毫秒内生成多个 ID，否则此字段为 0。理论上，一台机器每毫秒最多可以支持 4096 个新 ID。 ## 第 4 步 - 总结 在本章中，我们讨论了设计唯一 ID 生成器的不同方法：多主复制、UUID、票证服务器和类似 Twitter 雪花的唯一 ID 生成器。我们选择雪花，因为它支持我们所有的用例，并且在分布式环境中是可扩展的。 如果在面试结束时有额外的时间，这里有一些额外的谈话要点： - 时钟同步。在我们的设计中，我们假设 ID 生成服务器具有相同的时钟。当服务器在多个核上运行时，这种假设可能不正确。同样的挑战也存在于多机器场景中。时钟同步的解决方案超出了这本书的范围；然而，理解这个问题的存在是很重要的。网络时间协议是解决这个问题的最流行的解决方案。对于感兴趣的读者，请参考参考资料[4]。 - 部分长度调整。例如，更少的序列号和更多的时间戳位对于低并发性和长期应用程序是有效的。 - 高可用性。由于 ID 生成器是一个关键任务系统，因此它必须具有高度的可用性。 祝贺你能走到这一步！现在拍拍自己的背。干得好 # 第 8 章：设计一个 URL 缩短器 在本章中，我们将讨论一个有趣而又经典的系统设计面试问题：设计一个像 tinyurl 这样的 URL 缩短服务。 ## 第 1 步 - 了解问题，确定设计范围 系统设计的面试问题是故意保持开放式的。要设计一个精心设计的系统，提出澄清问题是至关重要的。 **候选人**：你能举一个URL缩短器如何工作的例子吗？ **面试官**：假设 URL https://www.systeminterview.com/q=chatsystem&c=loggedin&v=v3&l=long 是原始的 URL。您的服务将创建一个长度较短的别名： https://tinyurl.com/y7keocwj。如果单击别名，它将将您重定向到原始 URL。 **候选人**：访问流量是多少？ **面试官**：每天生成 1 亿个 URL。 **候选人**：缩短的 URL 是多长？ **面试官**：尽可能的简短。 **候选人**：在缩短的 URL 中允许使用哪些字符？ **面试官**：缩短的 URL 可以是数字（0-9）和字符（a-z、A-Z）的组合。 **候选人**：缩短的 URL 可以被删除或更新吗？ **面试官**：为了简单起见，让我们假设缩短的 URL 不能被删除或更新。 下面是最基本的用例： 1. URL 缩短：给定一个较长的 URL，=> 返回一个更短的 URL 2. URL 重定向：给定一个较短的 URL => 重定向到原始的 URL 3. 具有高可用性、可伸缩性和容错性的考虑 ### 粗略估计 - 写操作：每天生成 1 亿个 URL。 - 写操作每秒：1 亿 / 24 / 3600 = 1160 - 读操作：假设读操作写操作是 10：1，读操作每秒：1160 * 10=11600 - 假设 URL 缩短服务将运行 10 年，这意味着我们必须支持 1 亿 * 365 * 10= 3650 亿记录。 - 假设平均 URL 长度为 100。 - 超过 10 年的存储需求：3650 亿 * 100 字节 * 10 年 = 365 TB 对你来说，和面试官一起进行假设和计算是很重要的，这样你们俩都意见一致。 ## 第 2 步 - 提出高级设计并获得支持 在本节中，我们将讨论 API 端点、URL 重定向和 URL 缩短流。 ### API 端点 API 端点促进了客户机和服务器之间的通信。我们将 API 设计为 REST 风格。如果您不熟悉 restful API，您可以查阅外部材料，如参考材料[1]中的材料。URL 缩短器主节点需要两个 API 端点。 1. URL 的缩短。要创建一个新的短 URL，客户端将发送一个 POST 请求，其中包含一个参数：原始的长 URL。API 看起来如下： POST api/v1/data/shorten - 请求参数：{longUrl: longURLString} - 返回短 URL 2. URL 重定向。要将一个短 URL 重定向到相应的长 URL，客户端将发送一个 GET 请求。API 看起来是这样的： GET api/v1/shortUrl - 返回长 URL 到 HTTP 重定向 ### URL 重定向 图 8-1 显示了当您在浏览器上输入 tinyurl 时发生的情况。一旦服务器收到一个 tinyurl 请求，它将将短 URL 更改为具有 301 重定向的长 URL。 客户机和服务器之间的详细通信如图 8-2 所示。 这里值得讨论的一件事是 301 重定向 vs 302 重定向。 **301 重定向**。301 重定向显示所请求的 URL 被“永久”移动到长 URL。由于它是永久重定向的，因此浏览器会缓存响应，并且对相同 URL 的后续请求将不会被发送到 URL 缩短服务。相反，请求被直接重定向到长 URL 服务器。 **302 重定向**。302 重定向意味着 URL 被“暂时”移动到长 URL，这意味着对相同 URL 的后续请求将首先被发送到 URL 缩短服务。然后，它们被重定向到长 URL 服务器。 每种重定向方法都有其优缺点。如果优先级是减少服务器负载，使用 301 重定向是有意义的，因为只有相同 URL 的第一个请求被发送到 URL 缩短服务器。然而，如果分析是重要的，302 重定向是一个更好的选择，因为它可以更容易地跟踪点击率和点击的来源。 实现 URL 重定向的最直观的方法是使用哈希表。假设散列表存储 `<短 URL，长 URL>` 对，URL 重定向可以通过以下方式实现： - 获取长 URL：longURL = hashTable.get(shortURL) - 一旦获得 longURL 后，执行 URL 重定向。 ### 缩短 URL 让我们假设短 URL 的外观如下： www.tinyurl.com/{hashValue}。为了支持 URL 缩短用例，我们必须找到一个哈希函数 fx，它映射一个长 URL 到 hashValue，如图 8-3 所示。 散列函数必须满足以下要求： - 每个长 URL 必须散列到一个哈希值。 - 每个哈希值都可以映射回长 URL。 在深度研究中讨论了哈希函数的详细设计。 ## 第 3 步 - 深入设计 到目前为止，我们已经讨论了 URL 缩短和 URL 重定向的高级设计。在本节中，我们将深入研究以下内容：数据模型、哈希函数、URL 缩短和 URL 重定向。 ### 数据模型 在高级设计中，所有内容都存储在一个哈希表中。这是一个很好的起点；然而，由于内存资源有限且昂贵，这种方法对于现实系统是不可行的。一个更好的选择是在关系数据库中存储 映射。图 8-4 显示了一个简单的数据库表设计。该表的简化版本包含 3 列： id、shortURL、longURL。 ### 哈希函数 散列函数用于将一个长 URL 散列到一个短 URL，也称为散列值（hashValue）。 ### 哈希值长度 哈希值由来自 [0-9、a-z、A-Z] 的字符组成，其中包含 10 + 26 + 26 = 62 个可能的字符。要计算出哈希值的长度，找到最小的 n，即 62^n ≥ 3650 亿。基于粗略估计，该系统必须支持多达 3650 亿个 URL。表 8-1 显示了散列值的长度及其所能支持的最大 URL 数。 | N | URL 数量最大值 | | ---- | ------------------------------------ | | 1 | 62^1 = 62 | | 2 | 62^2 = 3,844 | | 3 | 62^3 = 238,328 | | 4 | 62^4 = 14,776,336 | | 5 | 62^5 = 916,132,832 | | 6 | 62^6 = 56,800,235,584 | | 7 | 62^7 = 3,521,614,606,208 = ~3.5 万亿 | 当 n = 7, 62 ^ n = ~3.5 万亿，3.5 万亿足以超过 3650 亿个 URL，所以哈希值的长度是 7。 我们将探索一个 URL 缩短器的两种类型的哈希函数。第一个是“哈希 + 碰撞解析”，第二个是“基 62 转换”。让我们一个接一个地看它们。 ### 哈希 + 碰撞解析 为了缩短一个长的 URL，我们应该实现一个哈希函数，它将一个长的 URL 散列到一个包含 7 个字符的字符串中。一个简单的解决方案是使用著名的哈希函数，如CRC32、MD5 或 SHA-1。下表比较了在此 URL 上应用不同的哈希函数后的哈希结果： https://en.wikipedia.org/wiki/Systems_design。 | 哈希函数 | 哈希值（十六进制） | | -------- | ---------------------------------------- | | CRC32 | 5cb54054 | | MD5 | 5a62509a84df9ee03fe1230b9df8b84e | | SHA-1 | 0eeae7916c06853901d9ccbefbfcaf4de57ed85b | 如表 8-2 所示，即使是最短的哈希值（来自 CRC32）也太长（超过 7 个字符）。我们怎样才能让它更短呢？ 第一种方法是收集哈希值的前 7 个字符；但是，这种方法可能会导致哈希冲突。为了解决哈希冲突，我们可以递归地附加一个新的预定义字符串，直到没有发现更多的冲突为止。图 8-5 解释了这个过程。 该方法可以消除冲突；但是，查询数据库以检查每个请求是否存在 shortURL 是代价高昂的。一种叫做布隆过滤器[2]的技术可以提高性能。布隆过滤器是一种空间有效的概率技术，用于测试一个元素是否是一个集合的成员。详情请参考参考资料[2]。 ### 基 62 转换 基转换是 URL 缩短器常用的另一种方法。基转换有助于在其不同的数字表示系统之间转换相同的数字。使用基 62 转换，因为散列值有 62 个字符。让我们用一个例子来解释转换是如何工作的：将 $11157_{10}$ 转换为基 62 表示。 （$11157_{10}$ 表示基底 10 系统中的 11157）。 - 从它的名字来看，基 62 是一种使用 62 个字符进行编码的方式。映射分别是： 0-0、...，9-9、10-a、11-b、...，35-z、36-A、...，61-Z，其中“a”代表10，“Z”代表61，等等。 - $11157_{10} = 2 \times 62^2 + 55 \times 62^1 + 59 \times 62^0$ = [2, 55, 59] -> 在基 62 中表达为 [2, T, X]。图 8-6 显示了会话过程。 - 因此，较短的 URL 是 https://tinyurl.com/2TX ### 这两种方法的比较 表 8-3 显示了两种方法的差异 | 哈希 + 碰撞解析 | 基 62 转换 | | ----------------------------------------------- | ------------------------------------------------------------ | | 固定的短 URL 长度 | 短 URL 的长度是不确定的。它随 ID 增长 | | 它不需要一个唯一 ID 生成器 | 这个选择依赖于一个唯一 ID 生成器 | | 可能碰撞且必须被处理 | 不可能碰撞因为 ID 是唯一的 | | 不可能判断出下一个可用短 URL，因为它不取决于 ID | 如果 ID 按 1 递增则很容易判断下一个可用短 URL。这可能是一个安全问题。 | ### 深入研究 URL 缩短 作为系统的核心部分之一，我们希望 URL 缩短流在逻辑上具有简单性和功能性。我们的设计中使用了基 62 转换。我们构建了下面的图表（图 8-7）来演示这个流程。 1. longURL 是输入。 2. 系统会检查该 longURL 是否在数据库中。 3. 如果是，则意味着 longURL 之前已被转换为 shortURL。在这种情况下，从数据库中获取 shortURL 并将其返回给客户端。 4. 如果不是，则该 longURL 是新的。一个新的唯一 ID（主键）由唯一 ID 生成器生成。 5. 将 ID 转换为 shortURL。 6. 创建一个具有 ID、shortURL 和 longURL 的新数据库行。 为了使流程更容易理解，让我们来看看一个具体的例子。 - 假设输入的长 URL 为： https://en.wikipedia.org/wiki/Systems_design - 唯一 ID 生成器返回 ID：2009215674938。 - 使用基 62 转换将 ID 转换为 shortURL。ID（2009215674938）被转换为“zn9edcu”。 - 将 ID、shortURL 和 longURL 保存到数据库中，如表 8-4 所示。 分布式唯一 ID 生成器值得一提。它的主要功能是生成全局唯一的 id，用于创建 shortURL。在高度分布式的环境中，实现唯一的 ID 生成器是一项挑战。幸运的是，我们已经在“第 7 章：在分布式系统中设计一个唯一 ID 生成器”中讨论了一些解决方案。你可以参考它来刷新你的记忆。 ### 深入研究 URL 重定向 图 8-8 显示了 URL 重定向的详细设计。由于读多于写，<短 URL，长 URL>映射存储在缓存中以提高性能。 URL 重定向的流程总结如下： 1. 用户单击一个简短的 URL 链接： https://tinyurl.com/zn9edcu 2. 负载均衡器将请求转发到 web 服务器。 3. 如果缓存中已经在 shortURL 中，请直接返回 longURL。 4. 如果缓存中不存在 shortURL，请从数据库中获取 longURL。如果它不在数据库中，则很可能是一个用户输入了一个无效的 shortURL。 5. 该 longURL 将返回给该用户。 ## 第 4 步 - 总结 在本章中，我们将谈到 API 的设计、数据模型、哈希函数、URL 缩短和 URL 重定向。 如果在面试结束时有额外的时间，这里有一些额外的谈话要点。 - 速率限制器：我们可能面临的一个潜在的安全问题是，恶意用户发送了压倒性的大量 URL 缩短请求。速率限制器有助于基于 IP 地址或其他过滤规则过滤出请求。如果你想刷新你的关于速率限制的记忆，请参考“第 4 章：设计一个速率限制器”。 - Web 服务器缩放：由于 Web 层是无状态的，因此通过添加或删除 Web 服务器很容易扩展 Web 层。 - 数据库缩放：数据库复制和分片化是常见的技术。 - 分片：数据对业务的成功越来越重要。将一个分片解决方案集成到 URL 缩短器中可以帮助回答一些重要的问题，比如有多少人点击了一个链接？他们什么时候点击链接？等 - 可用性、一致性和可靠性。这些概念是任何大型系统成功的核心。我们在第一章中详细讨论了它们，请刷新您对这些主题的记忆。 祝贺你能走到这一步！现在拍拍自己的背。干得好！ # 第 9 章：设计一个网络爬虫 在本章中，我们将重点关注网页爬虫设计：一个有趣而经典的系统设计面试问题。 网络爬虫被称为机器人或蜘蛛。它被搜索引擎广泛用于发现网络上新的或更新的内容。内容可以是网页、图像、视频、PDF 文件等。一个网络爬虫者首先收集一些网页，然后跟踪这些页面上的链接来收集新的内容。图 9-1 显示了这个爬行过程的一个可视化示例。 爬虫可用于许多用途： - 搜索引擎索引：这是最常见的用例。一个爬虫会收集网页，为搜索引擎创建一个本地索引。例如，谷歌机器人是谷歌搜索引擎背后的网络爬虫。 - Web 存档：这是一个从网络中收集信息以保存数据以供将来使用的过程。例如，许多国家图书馆运行爬虫来存档网站。值得注意的例子是美国国会图书馆的[1]和欧盟的网络档案[2]。 - 网络挖掘：网络的爆炸性增长为数据挖掘提供了前所未有的机会。网络挖掘有助于从互联网上发现有用的知识。例如，顶级金融公司使用爬虫程序下载股东大会和年度报告，以了解公司的关键举措。 - 网络监控。这些爬虫程序帮助监控互联网上的版权和商标侵权行为。例如，数字弧[3]利用爬虫来发现盗版作品和报告。 开发一个网络爬虫的复杂性取决于我们打算支持的规模。它可以是一个只需要几个小时就能完成的小型学校项目，也可以是一个需要由专门的工程团队持续改进的大型项目。因此，我们将在下面探讨所支持的规模和特性。 ## 第 1 步 - 了解问题，确定设计范围 网络爬虫的基本算法很简单： 1. 给定一组 URL，请下载该 URL 地址所在的所有网页。 2. 从这些网页中提取 URL 3. 向要下载的 URL 列表中添加新的 URL。重复这 3 个步骤。 一个网络爬虫的工作原理真的像这个基本的算法一样简单吗？不完全是。设计一个非常可伸缩的网络爬虫是一项极其复杂的任务。任何人都不太可能在面试期间设计出一个巨大的网络爬虫。在进入设计之前，我们必须提出问题，以理解要求并确定设计范围： **候选人**：爬虫器的主要目的是什么？它是用于搜索引擎索引、数据挖掘还是其他东西？ **面试官**：搜索引擎索引。 **候选人**：网络爬虫每月收集多少个网页？ **面试官**：10 亿页。 **候选人**：包括哪些内容类型？仅限 HTML 或其他内容类型，如 PDF 和图像，以及？ **面试官**：仅 HTML。 **候选人**：我们是否应该考虑新添加或编辑的网页？ **面试官**：是的，我们应该考虑新添加或编辑的网页。 **候选人**：我们需要存储从网络爬取的 HTML 页面吗？ **面试官**：是的，长达 5 年 **候选人**：我们如何处理带有重复内容的网页？ **面试官**：应该忽略内容重复的页面。 以上是一些你可以问面试官的样本问题。理解需求和澄清歧义是很重要的。即使你被要求设计一个像网络爬虫一样简单的产品，你和你的面试官也可能没有相同的假设。 除了与面试官澄清的功能外，注意一个好的网络爬虫的以下特征也很重要： - 可伸缩性：网络非常大。那里有数十亿个网页。使用并行化，Web 爬行应该非常高效。 - 健壮性：网络上充满了陷阱。错误的 HTML，无响应的服务器，崩溃，恶意链接等。都是很常见的。爬虫必须处理所有这些边缘的情况。 - 礼貌：爬虫不应该在很短的时间间隔内对一个网站发出太多的请求。 - 可扩展性：该系统非常灵活，因此需要进行最小限度的更改来支持新的内容类型。例如，如果我们想在将来抓取图像文件，我们不需要重新设计整个系统。 ### 粗略估计 下面的估计是基于许多假设的，与面试官的沟通是很重要的。 - 假设每月下载 10 亿个网页。 - QPS：10000000000 / 30 天 / 24 小时 / 3600 秒= ~400 页每秒。 - 峰值 QPS = 2 * QPS = 800 - 假设平均网页大小为 500k。 - 10 亿页 x 500k = 500 TB存储。如果您不清楚数字存储单元，请再次阅读第二章中的“二的次方”部分。 - 假设数据存储 5 年，500 TB * 12 个月 * 5 年 = 30 PB。需要一个 30 PB 的存储空间来存储五年期的内容。 ## 第 2 步 - 提出高级设计，并获得支持 一旦需求明确了，我们就会转向高级设计。受之前关于网络爬行[4] [5]的研究的启发，我们提出了一个如图 9-2 所示的高级设计。 首先，我们将探索每个设计组件，以理解它们的功能。然后，我们一步一步地检查爬虫工作流。 ### 种子 URL web 爬虫程序使用种子 URL 作为爬虫过程的起点。例如，要从一个大学的网站上抓取所有的网页，选择种子 URL 的一个直观的方法是使用该大学的域名。 为了爬行整个网络，我们需要在创造性地选择种子 URL。一个好的种子 URL 可以作为一个很好的起点，爬虫可以利用它来遍历尽可能多的链接。一般的策略是将整个 URL 空间分成更小的空间。第一种方法是基于地点，因为不同的国家可能有不同的流行网站。另一种方法是根据主题选择种子 URL；例如，我们可以将 URL 空间划分为购物、体育、医疗保健等。种子 URL 的选择是一个开放式的问题。你不被期望给出完美的答案。只需要大声把想法说出来。 ### URL 边界 大多数现代的网络爬虫程序将爬网状态分为两部分：要下载和已经下载。存储要下载的 URL 的组件称为 URL 边界（Frontier）。您可以将其称为先入先出（FIFO）队列。有关 URL 边界的详细信息，请参考深入研究。 ### HTML 下载器 HTML 下载器从互联网上下载网页。这些 URL 是由 URL 边界提供的。 ### DNS 解析器 要下载网页，必须将 URL 转换为 IP 地址。HTML 下载器调用 DNS 解析器以获取 URL 的相应 IP 地址。例如，URL www.wikipedia.org 在 2019 年 3 月 5 日被转换为 IP 地址 198.35.26.96。 ### 内容解析器 下载网页后，必须对其进行解析和验证，因为格式错误的网页可能会引发问题并浪费存储空间。在爬网服务器中实现内容解析器将减缓爬行进程。因此，内容解析器是一个单独的组件。 ### 是否看过内容？ 在线研究[6]显示，29% 的网页是重复的内容，这可能会导致相同的内容被多次存储。我们介绍了“内容看过了吗？”采用数据结构，消除数据冗余，缩短处理时间。它可以帮助检测以前存储在系统中的新内容。为了比较两个 HTML 文档，我们可以逐字符比较它们。然而，这种方法是缓慢和耗时的，特别是当涉及到数十亿个的网页时。完成这项任务的一个有效方法是比较两个网页[7]的哈希值。 ### 内容存储 它是一个用于存储 HTML 内容的存储系统。存储系统的选择取决于数据类型、数据大小、访问频率、使用寿命等因素。同时使用了磁盘和内存。 - 大部分内容都存储在磁盘上，因为数据集太大，无法存储在内存中。 - 流行的内容被保存在内存中，以减少延迟。 ### URL 提取器 URL 提取器从 HTML 页面中解析和提取链接。图 9-3 显示了一个链接提取过程的示例。通过添加“https://en.wikipedia.org”前缀，相对路径被转换为绝对 URL。 ### URL 过滤器 URL 过滤器排除了某些“黑名单”站点中的内容类型、文件扩展名、错误链接和 URL。 ### 网址看过了吗？ “网址看过了吗？”是一种数据结构，它跟踪在边界之前或已经访问过的 URL。“网址被看过了吗？”有助于避免多次添加相同的 URL，因为这可能会增加服务器负载，并导致潜在的无限循环。 Bloom 过滤器和哈希表是实现“已看过的 URL？”组成部分。我们将不介绍 bloom 过滤器和哈希表的详细实现。有关更多信息，请参考参考资料[4] [8]。 ### URL 存储 URL 存储存储已经访问了的 URL。 到目前为止，我们已经讨论了每一个系统组件。接下来，我们将它们放在一起来解释工作流程。 ### Web 爬虫工作流 为了更好地逐步解释工作流程，在设计图中添加了序列号，如图 9-4 所示。 步骤 2： HTML 下载器从 URL 边界获取一个 URL 列表。 步骤 3： HTML 下载器从 DNS 解析器获得 URL 的 IP 地址并开始下载。 步骤 4：内容解析器解析 HTML 页面，并检查页面是否格式错误。 步骤 5：解析和验证内容后，将其传递到“看过的内容？”组成部分 步骤 6：“已看过内容”组件检查 HTML 页面是否已经在存储中。 - 如果它在存储中，这意味着已经处理了不同 URL 中的相同内容。在这种情况下，HTML 页面将被丢弃。 - 如果它不在存储器中，则系统以前没有处理过相同的内容。该内容将被传递给链接提取器。 步骤 7：链接提取器从 HTML 页面中提取链接。 步骤 8：已提取的链接被传递到 URL 过滤器。 步骤 9：过滤链接后，它们被传递到“看过的 URL？”组成部分 步骤 10：“看过的 URL”组件检查 URL 是否已经在存储中，如果是，则之前进行处理，不需要做任何操作。 步骤 11：如果以前没有处理过 URL，则将其添加到 URL 边界中。 ## 第 3 步 - 深入设计 到目前为止，我们已经讨论了高级设计。接下来，我们将深入讨论最重要的构建组件和技术： - 深度优先搜索（DFS）和广度优先搜索（BFS） - URL 边界 - HTML 下载器 - 健壮性 - 可扩展性 - 检测和避免有问题的内容 ### DFS vs BFS 您可以将 web 看作是一个有向图，其中 web 页面作为节点，而超链接（URL）作为边。爬网过程可以看作是将一个有向图从一个网页到其他网页。两种常见的图遍历算法分别是 DFS 和 BFS。然而，DFS 通常不是一个很好的选择，因为 DFS 的深度可能很深。 BFS 通常被 web 爬虫使用，并由先入先出（FIFO）队列实现。在 FIFO 队列中，URL 按其排队的顺序退出队列。但是，这个实现有两个问题： - 来自同一网页的大多数链接都被链接回同一个主机。在图 9-5 中，wikipedia.com 中的所有链接都是内部链接，这使得爬虫程序忙于处理来自同一主机（wikipedia.com）的 URL。当爬虫者试图并行下载网页时，维基百科的服务器将会收到大量的请求。这被认为是“不礼貌的”。 - 标准 BFS 没有考虑到 URL 的优先级。网络很大，并不是每个页面都有相同的质量和重要性水平。因此，我们可能希望根据 URL 的页面排名、网络流量、更新频率等，对其进行优先排序。 ### URL 边界 URL 边界技术有助于解决这些问题。URL 边界是存储要下载的 URL 的数据结构。URL 边界是确保礼貌、URL 优先级和新鲜度的重要组成部分。在参考文献[5] [9]中提到了一些关于 URL 边界的值得注意的论文。这些论文的研究结果如下： ### 礼貌性 一般来说，web 爬虫应该避免在短时间内向同一主机服务器发送太多的请求。发送过多的请求被认为是“不礼貌的”，甚至被视为拒绝服务（DOS）攻击。例如，在没有任何约束的情况下，爬虫程序可以每秒钟向同一个网站发送数千个请求。这可能会淹没 web 服务器。 加强礼貌的一般想法是一次从同一台主机上下载一个页面。可以在两个下载任务之间添加一个延迟。礼貌约束是通过维护一个从网站主机名到下载（工作人员）线程的映射来实现的。每个下载器线程都有一个单独的 FIFO 队列，并且只下载从该队列获得的 URL。图 9-6 显示了管理礼貌的设计。 - 队列路由器：它确保每个队列（b1、b2、... bn）只包含来自同一主机的 URL。 - 映射表：它将每个主机映射到一个队列。 - FIFO 队列 b1、b2 到 bn：每个队列包含来自同一主机的 URL。 - 队列选择器：每个工作线程都被映射到一个 FIFO 队列，并且它只从该队列中下载 URL。队列选择逻辑将由队列选择器来完成。 - 工作线程 1 到 N。一个工作线程从同一主机逐个下载网页。可以在两个下载任务之间添加一个延迟。 ### 优先级 一个论坛上随机发布的关于苹果产品的帖子与苹果主页上的帖子非常不同。尽管他们都有“苹果”的关键字，但爬虫先爬取苹果主页是明智的。 我们根据有用性对 URL 进行优先排序，这可以通过页面排名[10]、网站流量、更新频率等来衡量。“优先级器”是处理 URL 优先级化的组件。有关此概念的深入信息，请参阅参考材料[5] [10]。 图 9-7 显示了管理 URL 优先级的设计。 - 优先级器：它以 URL 作为输入并计算优先级。 - 队列 f1 到 fn：每个队列都有一个指定的优先级。选择优先级高的队列。 - 队列选择器：随机选择一个偏向于具有更高优先级的队列的队列。 图 9-8 展示了 URL 边界设计，它包含两个模块： - 前端队列：管理优先级 - 后退队列：管理礼貌 ### 新鲜度 网页不断地被添加、删除和编辑。一个网络爬虫必须定期重新计算下载的页面，以保持我们的数据集的新鲜感。重新爬取所有的 URL 是耗时和资源密集型的。优化新鲜度的策略如下： - 根据网页的更新历史重新创建。 - 优先考虑 URL，并更频繁地重新绘制重要页面。 ### URL 边界的存储 在搜索引擎的现实爬行中，前沿的 URL 数量可能是数亿[4]。把所有东西放在内存中既不持久也不能可扩展。保持在磁盘中的所有东西是不可取的，因为磁盘很慢；而且它很容易成为爬网的瓶颈。 我们采用了一种混合的方法。大多数 URL 都存储在磁盘上，因此存储空间不是问题。为了减少从磁盘读取和写入磁盘的成本，我们在内存中维护缓冲区以用于排队/脱队列操作。缓冲区中的数据会定期被写入磁盘。 ### HTML 下载器 HTML 下载器使用 HTTP 协议从互联网上下载网页。在讨论 HTML 下载器之前，我们要先看看机器人排除协议。 ### Robots.txt Robots.txt，被称为机器人排除协议，是网站用于与爬虫通信的标准。它指定了允许下载哪些页面爬虫程序。在尝试抓取一个网站之前，爬虫应该首先检查它相应的 robots.txt 并遵循它的规则。 为了避免重复下载 robots.txt 文件，我们缓存了该文件的结果。文件定期下载并保存到缓存。这是一个来自 https://www.amazon.com/robots.txt 的 robots.txt 文件。部分文件夹，例如 createrhub，对于谷歌机器人来说是不允许的。 ``` User-agent: Googlebot Disallow: /creatorhub/* Disallow: /rss/people/*/reviews Disallow: /gp/pdp/rss/*/reviews Disallow: /gp/cdp/member-reviews/ Disallow: /gp/aw/cr/ ``` 除了 robots.txt 之外，性能优化也是我们将介绍的 HTML 下载器的另一个重要概念。 ### 性能优化 下面是针对 HTML 下载器的性能优化列表。 #### 1. 分布式爬网 为了实现高性能，爬网作业被分配到多个服务器中，每个服务器运行多个线程。URL 空间被划分成更小的部分；因此，每个下载器都负责 URL 的一个子集。图 9-9 显示了一个分布式爬网的示例。 #### 2. 缓存DNS解析器 DNS 解析器是爬虫程序的一个瓶颈，因为由于许多 DNS 接口的同步特性，DNS 请求可能需要时间。DNS 响应时间范围为 10 ms到 200 ms。一旦一个爬虫线程执行了对 DNS 的请求，其他线程就会被阻塞，直到第一个请求完成。维护我们的 DNS 缓存以避免频繁调用 DNS 是一种有效的速度优化技术。我们的 DNS 缓存保持域名到 IP 地址映射，并通过 cron 作业定期更新。 #### 3. 局部性 在地理位置上分发爬网服务器。当爬网服务器更接近网站主机时，爬虫会体验到更快的下载时间。设计局部性适用于大多数系统组件：爬网服务器、缓存、队列、存储等。 #### 4. 超时时间短 一些 web 服务器响应缓慢或可能根本不响应。为了避免长时间等待，指定了最大等待时间。如果主机在预定义的时间内没有响应，爬虫将停止作业并抓取其他页面。 ### 健壮性 除了性能优化外，鲁棒性也是一个重要的考虑因素。我们提出了几种方法来提高系统的鲁棒性： - 一致性哈希：这有助于在下载者之间分配负载。可以使用一致性哈希方式来添加或删除新的下载器服务器。更多细节请参考第 5 章：设计一致性哈希。 - 保存爬网状态和数据：为了防止故障，系统会将爬网状态和数据写入存储系统。通过加载已保存的状态和数据，可以轻松地重新启动中断的爬网。 - 异常处理：错误在大规模系统中是不可避免的和常见的。爬虫程序必须优雅地处理异常，而不会使系统崩溃。 - 数据验证：这是防止系统错误的一个重要措施。 ### 扩展性 随着几乎每个系统的发展，设计目标之一是使系统足够灵活，以支持新的内容类型。该爬虫器可以通过插入新的模块来进行扩展。图 9-10 显示了如何添加新的模块。 - PNG 下载器模块已插入以下载 PNG 文件。 - Web 监控模块，以监控网络，防止版权和商标侵权。 ### 检测并避免有问题的内容 本节讨论对冗余、无意义或有害内容的检测和预防。 #### 1. 冗余内容 如前所述，近 30% 的网页是重复的。哈希值或校验和值有助于检测重复的[11]。 #### 2. 蜘蛛陷阱 蜘蛛陷阱是一个网页，它会导致一个无限循环中的爬虫。例如，一个无限深度的目录结构如下： www.spidertrapexample.com/foo/bar/foo/bar/foo/bar/... 这种蜘蛛陷阱可以通过设置 URL 的最大长度来避免。然而，没有一个适合全部场景的大小的解决方案来检测蜘蛛陷阱。包含蜘蛛陷阱的网站很容易被识别，因为在这些网站上发现了异常大量的网页。很难开发出自动算法来避免蜘蛛陷阱；然而，用户可以手动验证和识别蜘蛛陷阱，并将这些网站从爬虫中排除出来，或者应用一些定制的 URL 过滤器。 #### 3. 数据噪音 有些内容只有很少或根本没有价值，比如广告、代码片段、垃圾邮件 URL 等。这些内容对爬虫没有用处，如果可能，应该排除在外。 ## 第 4 步 - 总结 在本章中，我们首先讨论了一个良好的爬虫器的特征：可伸缩性、礼貌性、可扩展性和鲁棒性。然后，我们提出了一个设计方案，并讨论了关键组件。构建一个可伸缩的 web 爬虫并不是一个简单的任务，因为 web 非常大，而且充满了陷阱。虽然我们已经涵盖了许多主题，但我们仍然错过了许多相关的谈话要点： - 服务器端渲染：许多网站使用像 JavaScript、AJAX 等这样的脚本来动态地生成链接。如果我们直接下载和解析网页，我们将无法检索动态生成的链接。为了解决这个问题，我们在解析页面[12]之前也先执行服务器端渲染（也称为动态渲染）。 - 过滤掉不需要的页面：由于有限的存储容量和爬行资源，反垃圾邮件组件有利于过滤掉低质量和垃圾邮件页面[13] [14]。 - 数据库复制和分片：诸如复制和分片等技术被用于提高数据层的可用性、可伸缩性和可靠性。 - 水平缩放：对于大规模抓取，需要数百甚至数千台服务器来执行下载任务。关键是要保持服务器的无状态状态。 - 可用性、一致性和可靠性：这些概念是任何大型系统成功的核心。我们在第一章中详细地讨论了这些概念。刷新你对这些主题的记忆。 - 分析：收集和分析数据是任何系统的重要组成部分，因为数据是微调的关键成分。 祝贺你能走到这一步！现在拍拍自己的背。干得好！ # 第 10 章：设计一个通知系统 近年来，通知系统已经成为许多应用程序中一个非常流行的功能。通知提醒用户提供重要的信息，如突发新闻、产品更新、事件、产品等。它已成为我们日常生活中不可或缺的一部分。在本章中，我们将要求您设计一个通知系统。 一个通知不仅仅是移动推送通知。三种类型的通知格式是：移动推送通知、短信和电子邮件。图 10-1 显示了每个这些通知的一个示例。 ## 第 1 步 - 了解问题，确定设计范围 建立一个能够每天发送数百万个通知的可扩展系统并不是一项容易的任务。它需要对通知生态系统的深入了解。面试问题是故意设计为开放式的和模棱两可的，你有责任提出问题来澄清要求。 **候选人**：系统支持什么类型的通知？ **面试官**：推送通知、短信和电子邮件。 **候选人**：它是一个实时系统吗？ **面试官**：让我们说这是一个软实时系统。我们希望用户能尽快收到通知。但是，如果系统处于高工作负载下，则有轻微的延迟是可以接受的。 **候选人**：支持的设备？ **面试官**： iOS设备，安卓设备，和笔记本电脑/台式机。 **候选人**：什么触发通知？ **面试官**：通知可以由客户端应用程序触发。它们也可以位于服务器端。 **候选人**：用户可以选择退出吗？ **面试官**：是的，选择选择退出的用户将不再收到通知。 **候选人**：每天发送多少个通知？ **面试官**：1000 万条手机推送通知，100 万条短信和 500 万封电子邮件。 ## 第 2 步 - 提出高级设计，并获得支持 本节展示了支持各种通知类型的高级设计： iOS 推送通知、Android 推送通知、短信和电子邮件。其结构如下： - 不同类型的通知 - 联系信息收集流 - 通知发送/接收流 ### 不同类型的通知 我们首先观察每种通知类型在高级级别上是如何工作的 #### iOS 推送通知 我们主要需要三个组件来发送一个 iOS 推送通知： - 提供程序。提供商构建并发送通知到苹果推送通知服务（APNS）的通知请求。若要构造推送通知，提供程序将提供以下数据： - 设备令牌：这是用于发送推送通知的唯一标识符。 - 有效负载：这是一个 JSON 字典，其中包含一个通知的有效负载。下面是一个示例： ```json { "aps": { "alert": { "title": "Game Request", "body": "Bob wants to play chess", "action-loc-key": "PLAY" }, "badge": 5 } } ``` - APNS：这是苹果公司提供的一项远程服务，用来向 iOS 设备传播推送通知。 - iOS 设备：它是终端客户端，它接收推送通知。 #### 安卓推送通知 安卓系统也采用了类似的通知流。火基云消息传递（Firebase Cloud Messaging, FCM）通常用于向安卓设备发送推送通知。 #### 短信 对于短信，第三方短信服务如 Twilio [1]，Nexmo [2] 和许多其他的都很常用。其中大多数都是商业服务公司。 #### 电子邮件 虽然许多公司可以建立自己的电子邮件服务器，但其中许多公司都选择了商业电子邮件服务。Sendgrid[3] 和 Mailchimp[4]是最受欢迎的电子邮件服务之一，它们提供更好的交付率和数据分析。 图 10-6 显示了包含所有第三方服务后的设计 ### 联系人信息收集流程 要发送通知，我们需要收集移动设备令牌、电话号码或电子邮件地址。如图 10-7 所示，当用户安装了我们的应用程序或首次注册时，API 服务器会收集用户的联系信息并将其存储在数据库中。 图 10-8 显示了用于存储联系信息的简化数据库表。电子邮件地址和电话号码存储在用户表中，而设备令牌存储在设备表中。一个用户可以有多个设备，这表明可以向所有的用户设备发送一个推送通知。 ### 通知收发流程 我们将首先介绍初始设计；然后，提出一些优化方案。 ### 高级设计 图 10-9 显示了设计，并对每个系统组件的解释如下。 **服务 1 到 N**：服务可以是微服务、cron 作业，也可以是触发通知发送事件的分布式系统。例如，一个账单服务会发送电子邮件提醒客户，他们的到期付款，或者一个购物网站告诉客户，他们的包裹明天将通过短信送达。 **通知系统**：通知系统是发送/接收通知的核心部分。从一些简单的事情开始，只使用了一个通知服务器。它为服务 1 到 N 提供 API，并为第三方服务构建通知有效负载。 **第三方服务**：第三方服务负责向用户发送通知。在与第三方服务集成时，我们需要特别关注可扩展性。良好的可扩展性意味着一个灵活的系统，可以轻松地插拔第三方服务。另一个重要的考虑因素是，第三方服务可能在新的市场或未来无法使用。例如，FCM 在中国就没有了。因此，在那里使用了替代的第三方服务，如 Jpush、PushY 等。 **iOS、安卓、短信、电子邮件**：用户在他们的设备上收到通知。 本设计中发现了三个问题： - 单点故障（SPOF）：单个通知服务器意味着 SPOF。 - 难以扩展：通知系统处理一个服务器中与推送通知相关的所有内容。独立地缩放数据库、缓存和不同的通知处理组件具有挑战性。 - 性能瓶颈：处理和发送通知可能是资源密集型的。例如，构建 HTML 页面并等待来自第三方服务的响应可能需要时间。在一个系统中处理所有内容可能会导致系统过载，特别是在高峰时段。 ### 高级设计（改进） 在列举了初始设计中的挑战之后，我们改进了如下所示的设计： - 将数据库和缓存移出通知服务器。 - 添加更多的通知服务器，并设置自动水平缩放。 - 引入消息队列以解耦系统组件。 图10-10显示了改进后的高级设计。 查看上图的最佳方法是从左到右： **服务 1 到 N**：它们代表通过通知服务器提供的 API 发送通知的不同服务。 **通知服务器**：它们提供以下功能： - 为发送通知的服务提供 API。这些 API 只能在内部或经过验证的客户端访问，以防止垃圾邮件。 - 执行基本的验证，以验证电子邮件、电话号码等。 - 查询数据库或高速缓存，以获取呈现通知所需的数据。 - 将通知数据放到消息队列中以进行并行处理。 下面是一个发送电子邮件的API示例： ```json // POST https://api.example.com/v/sms/send // Request body { "to": [ { "user_id": 123456 } ], "from": { "email": "from_address@example.com" }, "subject": "Hello, World!", "content": [ { "type": "text/plain", "value": "Hello, World!" } ] } ``` **缓存**：用户信息，设备信息，通知模板被缓存。 **数据库**：它存储有关用户、通知、设置等的数据。 **消息队列**：它们删除了组件之间的依赖关系。当要发送大量通知时，消息队列将作为缓冲区。每个通知类型都分配了一个不同的消息队列，因此一个第三方服务中的中断将不会影响其他通知类型。 **工作者**：工作者是从消息队列中提取通知事件并将它们发送到相应的第三方服务的服务器列表。 **第三方服务**：已在初始设计中进行了解释。 **iOS，安卓，短信，电子邮件**：在最初的设计中已经解释过了。 接下来，让我们研究一下每个组件是如何一起工作来发送一个通知的： 1. 一个服务调用由通知服务器提供的 API 来发送通知。 2. 通知服务器从缓存或数据库获取用户信息、设备令牌和通知设置。 3. 通知事件被发送到相应的队列以进行处理。例如，一个 iOS 推送通知事件被发送到 iOS PN 队列。 4. 工作人员从消息队列中提取通知事件。 5. 工作者们向第三方服务机构发送通知。 6. 第三方服务会向用户设备发送通知。 ## 第 3 步 - 深入设计 在高级设计中，我们讨论了不同类型的通知、联系信息收集流和通知发送/接收流。我们将深入探讨以下问题： - 可靠性。 - 附加组件和注意事项：通知模板、通知设置、速率限制、重试机制、推送通知中的安全性、监视队列通知和事件跟踪。 - 更新设计。 ### 可靠性 在分布式环境中设计通知系统时，我们必须回答几个重要的可靠性问题。 #### 如何防止数据丢失？ 通知系统中最重要的要求之一是它不能丢失数据。通知通常可以被延迟或重新订购，但永远不会丢失。为了满足这一要求，通知系统将通知数据持久保存在数据库中，并实现了一种重试机制。通知日志数据库用于数据持久性，如图 10-11 所示。 #### 收件人会只收到一次通知吗？ 简短的答案是否定的。尽管大多数时候通知只发送一次，但分布式的性质可能会导致重复的通知。为了减少重复的发生，我们引入了一个重复数据消除机制，并仔细处理每个故障情况。下面是一个简单的重复数据删除逻辑： 当一个通知事件第一次到达时，我们通过检查事件 ID 来检查之前是否看到了它。如果人们在以前看到过它，它就会被丢弃。否则，我们将发出通知。想让感兴趣的读者了解为什么我们不能有精确一次交付（exactly once delivery），请参考材料 [5]。 ### 其他组件和注意事项 我们已经讨论了如何收集用户的联系信息、发送和接收通知。一个通知系统远不止于此。这里我们将讨论其他组件，包括模板重用、通知设置、事件跟踪、系统监控、速率限制等。 #### 通知模板 一个大型的通知系统每天发送数百万个通知，其中许多通知都遵循类似的格式。引入通知模板是为了避免从头开始构建每个通知。通知模板是一个预格式化的通知，通过自定义参数、样式、跟踪链接等来创建唯一的通知。下面是一个推送通知的示例模板。 ``` BODY: You dreamed of it. We dared it. [ITEM NAME] is back — only until [DATE]. CTA: Order Now. Or, Save My [ITEM NAME] ``` 使用通知模板的好处包括保持一致的格式、减少边际错误和节省时间。 #### 通知设置 用户通常每天都会收到太多的通知，他们很容易感到不知所措。因此，许多网站和应用程序让用户对通知设置进行细粒度的控制。这个信息存储在通知设置表中，与以下字段： ``` user_id bigInt channel varchar # push notification, email or SMS opt_in boolean # opt-in to receive notification ``` 任何通知发送到用户之前，我们首先检查用户是否选择接收这种类型的通知。 #### 限速 为了避免用户收到太多的通知，我们可以限制用户可以接收到的通知的数量。这一点很重要，因为如果我们发送得太频繁，接收器可以完全关闭通知。 #### 重试机制 当第三方服务无法发送通知时，该通知将被添加到消息队列中以进行重试。如果问题仍然存在，将向开发人员发送警报。 #### 推送通知中的安全性 对于 iOS 或安卓应用程序，appKey 和 appSecret 用于保护推送通知 API[6] 的安全。只有经过身份验证或已验证的客户端才允许使用我们的 API 发送推送通知。有兴趣的用户应参考参考资料[6]。 #### 监视排队通知 要监视的一个关键指标是排队通知的总数。如果数量很大，那么工作者处理通知事件的速度就不够快。为了避免通知交付中的延迟，需要更多的工作者。图 10-12（感谢[7])显示了待处理的排队消息的示例。 #### 事件跟踪 通知指标，如开放率、点击率和参与度，对于理解客户行为非常重要。分析服务实现了事件跟踪。通常需要进行通知系统和分析服务之间的集成。图 10-13 显示了一个可能为分析目的而跟踪的事件的示例。 ### 更新的设计 将所有内容放在一起，图 10-14 显示了更新后的通知系统设计。 在此设计中，与之前的设计相比，添加了许多新的组件。 - 通知服务器配备了两个更关键的功能：身份验证和速率限制。 - 我们还添加了一个重试机制来处理通知失败。如果系统无法发送通知，它们将被放回消息传递队列中，工作人员将重试一个预定义的次数。 - 此外，通知模板还提供了一个一致和高效的通知创建过程。 - 最后，监测和跟踪系统添加了系统健康检查和未来的改进。 ## 第 4 步 - 总结 通知是必不可少的，因为它们会给我们提供重要的信息。它可以是在 Netflix 上发布的关于你最喜欢的电影的推送通知，一封关于新产品折扣的电子邮件，或者是一条关于你的网上购物付款确认的消息。 在本章中，我们描述了一个可扩展的通知系统的设计，它支持多种通知格式：推送通知、短信和电子邮件。我们采用了消息队列来解耦系统组件。 除了高级设计之外，我们还深入研究了更多的组件和优化。 - 可靠性：我们提出了一个稳健的重试机制来最小化故障率。 - 安全： AppKey/appSecret 对用于确保只有已验证的客户端才能发送通知。 - 跟踪和监控：这些都可以在通知流的任何阶段实现，以捕获重要的统计数据。 - 尊重用户设置：用户可以选择不接收通知。我们的系统在发送通知之前要先检查用户的设置。 - 速率限制：用户将欣赏他们收到的通知数量的频率限制。 祝贺你能走到这一步！现在拍拍自己的背。干得好！ # 第 11 章：设计一个新闻推送系统 在本章中，我们将要求您设计一个新闻推送系统。什么是新闻源？根据脸书的帮助页面，“新闻推送是你主页中间不断更新的故事列表。新闻动态包括状态更新、照片、视频、链接、应用程序活动，以及你在脸书[1]上关注的人、页面和群组的赞”。这是一个很受欢迎的面试问题。类似的常见问题有：设计脸书新闻动态，Instagram 动态，推特时间轴等。 ## 第 1 步 - 理解问题并建立设计范围 第一组澄清问题是了解面试官在要求你设计一个新闻推送系统时的想法。至少，您应该弄清楚应该支持哪些特性。以下是一个候选人-面试官互动的例子： **候选人**：这是一个手机应用程序吗？还是一个网络应用程序？或者两者都有？ **面试官**：两者都有。 **候选人**：重要的特点是什么？ **面试官**：用户可以发布一条消息，并在新闻推送页面上看到她朋友的帖子。 **候选人**：新闻推送是按时间顺序排序还是按特定顺序排序，比如主题分数？例如，来自你的亲密朋友的帖子得分更高。 **面试官**：为了保持事情的简单性，让我们假设提要是按时间倒序排序的。 **候选人**：一个用户可以有多少个朋友？ **面试官**：5000 **候选人**：交通量是多少？ **面试官**：一千万 DAU **候选人**：能否包含图像、视频或文本？ **面试官**：它可以包含媒体文件，包括图像和视频 现在您已经收集到了需求，我们将专注于设计系统。 ## 第 2 步 - 提出高级设计，并获得支持 设计分为两个流程：推送发布和新闻推送构建。 - 推送发布：当用户发布一篇文章时，相应的数据会被写入高速缓存和数据库中。她朋友的新闻推送里有一条帖子。 - 新闻推送构建：为了简单起见，让我们假设新闻推送是通过按反时间顺序聚合朋友的帖子来构建的。 ### 新闻推送 API 新闻推送 API 是客户机与服务器通信的主要方式。这些 API 是基于 HTTP 的，允许客户端执行操作，其中包括发布状态、检索新闻推送、添加朋友等。我们将讨论两个最重要的 API：推送发布 API 和获取新闻推送 API。 #### 推送发布 API 要发布一篇文章，将向服务器发送一个 HTTP POST 请求。内容如下： *POST /v1/me/feed* 参数： - content：内容是文章的文本。 - auth_token：它用于验证 API 请求。 #### 获取新闻推送 API 检索新闻推送的 API 如下所示： *GET /v1/me/feed* 参数： - auth_token：它用于对 API 请求进行身份验证 ### 推送发布 图 11-2 显示了推送发布流程的高级设计。 - 用户：用户可以在浏览器或移动应用程序上查看新闻订阅推送。用户通过 API： */v1/me/feed？content=Hello&auth_token={auth_token}* 发布一个内容为 “Hello” 的帖子。 - 负载均衡器：将流量分配到 web 服务器 - Web 服务器：web 服务器将流量重定向到不同的内部服务。 - Post 服务：在数据库中缓存和缓存。 - 分发（fanout）服务：将新的好友新闻推送内容。新闻推送数据存储在高速缓存中，以便于快速检索。 - 通知服务：通知朋友有新的内容可用，并发送推送通知。 ### 新闻推送构建 在本节中，我们将讨论如何在幕后建立新闻推送。图 11-3 显示了高级别设计： - 用户：用户发送请求检索她的消息。请求的外观如下：*/v1/me/feed*。 - 负载均衡器：负载均衡器将流量重定向到 web 服务器。 - Web 服务器：web 服务器将请求路由到新闻订阅服务。 - 新闻推送服务：新闻推送服务从缓存中获取新闻推送。 - 新闻推送缓存：存储呈现新闻推送所需的新闻推送 ID。 ## 第 3 步 - 深入设计 高级设计简要介绍了两个流程：推送发布和新闻推送构建。在这里，我们将更深入地讨论这些主题。 ### 深入推送发布 图 11-4 概述了推送发布的详细设计。我们已经讨论了高级设计中的大多数组件，我们将重点关注两个组件： web 服务器和分发（fanout）服务。 ### Web 服务器 除了与客户端通信之外，web 服务器还强制执行身份验证和速率限制。 只有使用有效的 *auth_token* 登录的用户才被允许发布文章。该系统限制了用户在一定时间内可以发布的帖子的数量，这对防止垃圾邮件和滥用内容至关重要。 ### 分发服务 分发（fanout）是指向所有朋友发送一个帖子的过程。两种方式的分发模式分别是：写（也称为推送模型）和读（也称为拉模型）。这两种方式都有利弊有弊。我们将解释他们的工作流程，并探索支持我们的系统的最佳方法。 **写时分发**。使用这种方法，可以在写时预先计算新闻推送。新帖子在发布后立即送到朋友的缓存中。 优点： - 新闻动态消息是实时生成的，可以立即推送给朋友。 - 获取新闻推送的速度很快，因为新闻推送是在写时预先计算好的。 缺点： - 如果一个用户有很多朋友，那么获取好友列表并为他们所有人生成新闻推送都是缓慢而耗时的。这叫做热键问题。 - 对于非活动用户或很少登录的用户，预计算新闻会浪费计算资源。 **读时分发**。新闻推送是在读取时间期间生成的。这是一种按需应变的模式。当用户加载她的主页时，最近的帖子就会被拉取。 优点： - 对于不活跃的用户或那些很少登录的用户，读时分发的效果更好，因为它不会浪费他们身上的计算资源。 - 数据不会被推送给朋友，因此没有热键问题。 缺点： - 获取新闻推送很慢，因为新闻推送不是预先计算的。 我们采用了一种混合的方法来获得这两种方法的好处，并避免其中的陷阱。由于快速获取新闻推送是至关重要的，所以我们对大多数用户使用了推送模型。对于有很多朋友/粉丝的名人或用户，我们让粉丝按需获取新闻内容，以避免系统过载。一致散列是减轻热键问题的一种有用的技术，因为它有助于更均匀地分发请求/数据。 让我们仔细看看如图 11-5 所示的分发服务。 分发服务按下面方式运作： 1. 从图形数据库中获取朋友 ID。图形数据库适合于管理朋友关系和朋友推荐。有兴趣的读者希望了解更多关于这个概念，请参考参考材料[2]。 2. 从用户缓存中获取朋友的信息。然后，该系统会根据用户的设置过滤掉好友。例如，如果你让某人静音，她的帖子就不会出现在你的动态消息上，即使你仍然是朋友。帖子可能无法显示出信息的另一个原因是，用户可以有选择地与特定的朋友分享信息，或向其他人隐藏信息。 3. 将好友列表和新的帖子 ID 发送到消息队列。 4. 分发（fanout）工作者从消息队列中获取数据，并将新闻推送数据存储在新闻推送缓存中。您可以将新闻推送缓存看作是一个 `` 映射表。每当发布一个新帖子时，它将被附加到新闻订阅表中，如图 11-6 所示。如果我们将整个用户并发布对象存储在缓存中，内存消耗可能会变得非常大。因此，只存储 ID。为了保持内存大小较小，我们设置了一个可配置的限制。用户在新闻推送中浏览数千篇帖子的机会很小。大多数用户只对最新的内容感兴趣，因此缓存错过率很低。 5. 在新闻推送缓存中存储 ``。图 11-6 显示了新闻推送在缓存中的样子的一个示例。 ### 深入获取新闻推送 图 11-7 说明了新闻推送检索的详细设计。 如图 11-7 所示，媒体内容（图像、视频等）存储在 CDN 中以进行快速检索。让我们来看看客户机是如何检索新闻推送的。 1. 用户发送请求检索她的消息。这个请求看起来是这样的：*/v1/me/feed* 2. 负载平衡器会将请求重新分配到 web 服务器。 3. Web 服务器调用新闻推送服务来获取新闻推送。 4. 新闻推送服务从新闻推送缓存中获得一个列表发布 ID。 5. 用户的新闻推送不仅仅是一个推送 ID 的列表。它包含用户名，个人资料图片，发布内容，发布图片等。因此，新闻推送服务从缓存（用户缓存和后置缓存）中获取完整的用户和后置对象，以构造完全化的新闻推送。 6. 完全化的新闻推送将以 JSON 格式返回给客户端进行渲染。 ### 缓存体系 高速缓存对于新闻推送系统来说是非常重要的。我们将高速缓存层划分为 5 个层，如图 11-8 所示。 - 新闻推送：它存储新闻推送的 ID。 - 内容：它存储每个发布数据。流行的内容存储在热缓存中。 - 社交图：它存储用户关系数据。 - 动作：它存储关于用户是否喜欢帖子、回复帖子或采取其他操作的信息。 - 计数器：它存储了喜欢、回复、追随者、跟随者等的计数器。 ## 第 4 步 - 总结 在本章中，我们设计了一个新闻推送系统。我们的设计包含两个流程：推送发布和新闻推送检索。就像任何系统设计面试问题一样，没有一个完美的方法来设计一个系统。每个公司都有其独特的约束条件，你必须设计一个系统来适应这些约束条件。理解你的设计和技术选择的权衡是很重要的。如果还剩几分钟，您可以讨论可伸缩性问题。为了避免重复的讨论，下面只列出了高层的谈话要点。 缩放数据库： - 垂直缩放与水平缩放 - SQL vs NoSQL - 主从复制 - 读取副本 - 一致性模型 - 数据库分片 其他讨论点： - 保持 web 层无状态 - 尽可能缓存数据 - 支持多个数据中心 - 松耦合组件与消息队列 - 监控关键指标。例如，在高峰时间的 QPS 和用户刷新他们的动态消息的延迟，这些是很有趣的监控。 祝贺你能走到这一步！现在拍拍自己的背。干得好！ # 第 12 章：设计一个聊天系统 在本章中，我们将探讨一个聊天系统的设计。几乎每个人都在使用聊天应用程序。图 12-1 显示了市场上最流行的应用程序。 一个聊天应用程序对不同的人执行不同的功能。确定确切的要求是极其重要的。例如，当面试官想要一对一的聊天时，你并不想设计一个专注于群聊的系统。探索特性需求是很重要的。 ## 第 1 步 - 了解问题，确定设计范围 就聊天应用程序的设计类型达成一致是至关重要的。在市场上，有一对一的聊天应用程序，如 Facebook Messenger，微信和 WhatsApp，专注于群组聊天，如 Slack，或游戏聊天应用程序，如 Discord，专注于大群组互动和低语音聊天延迟。 第一组澄清问题应该确定面试官在要求你设计一个聊天系统时的确切想法。至少，弄清楚你应该专注于一对一的聊天还是群聊应用。你可能会问以下一些问题： **候选人**：我们应该设计什么样的聊天应用程序？1 对 1 的还是基于组的？ **面试官**：它应该同时支持 1 对 1 和群聊。 **候选人**：这是一个手机应用程序吗？还是一个网络应用程序？或者两者都有？ **面试官**：两者兼而有之。 **候选人**：这个应用程序的规模是多少？是创业应用还是大规模应用？ **面试官**：它应该支持 5000 万日活跃用户（DAU）。 **候选人**：对于群聊，群组成员的限制是多少？ **面试官**：最多可 100 人 **候选人**：哪些功能对聊天应用程序是重要的？它能支持附件吗？ **面试官**：1 对 1 的聊天，群聊，在线指标。该系统只支持文本消息。 **候选人**：是否有消息大小限制？ **面试官**：是的，文本长度应该小于 10 万个字符。 **候选人**：是否需要端到端加密？ **面试官**：现在还不需要，但如果时间允许，我们会讨论一下。 **候选人**：我们应该存储聊天历史记录多长时间？ **面试官**：永远。 在这一章中，我们专注于设计一个像 Facebook messenger 这样的聊天应用程序，并强调以下功能： - 低交付延迟的一对一的聊天 - 小群聊天（最多 100 人） - 在线显示 - 多设备支持。同一个帐户可以同时登录到多个帐户。 - 推送通知 就设计规模达成一致也很重要。我们将设计一个支持 5000 万 DAU 的系统。 ## 第 2 步 - 提出高级设计，并获得支持 为了开发一个高质量的设计，我们应该有一个关于客户端和服务器如何通信的基本知识。在聊天系统中，客户端可以是移动应用程序或 web 应用程序。客户之间不直接交流。相反，每个客户端都连接到一个聊天服务，它支持上面提到的所有功能。让我们专注于基本的操作。聊天服务必须支持以下功能： - 接收来自其他客户端的消息。 - 为每个邮件找到正确的收件人，并将邮件中继给收件人。 - 如果收件人不在线，请保存服务器上该收件人的消息，直到她在线为止。 图 12-2 显示了客户端（发送方和接收方）与聊天服务之间的关系。 当客户端打算开始聊天时，它会使用一个或多个网络协议来连接聊天服务。对于聊天服务来说，网络协议的选择是很重要的。让我们和面试官讨论这个问题。 客户端会为大多数客户机/服务器应用程序启动请求。对于聊天应用程序的发送方端也是如此。在图 12-2 中，当发送方通过聊天服务向接收方发送消息时，它使用久经时间考验的 HTTP 协议，这是最常见的 web 协议。在这种情况下，客户端打开与聊天服务的 HTTP 连接并发送消息，通知服务将消息发送给接收方。keep-alive 头是有效的，因为 keep-alive 头允许客户端维护与聊天服务的持久连接。它还减少了 TCP 握手的数量。HTTP 在发送方是一个很好的选择，许多流行的聊天应用程序，如 Facebook [1]最初使用 HTTP 发送消息。 然而，接收端稍微复杂一些。由于 HTTP 是由客户端启动的，因此从服务器发送消息并不简单。多年来，许多技术被用来模拟服务器启动的连接：轮询、长轮询和 WebSocket。这些都是系统设计访谈中广泛使用的重要技术，所以让我们检查每一个。 ### 轮询 如图 12-3 所示，轮询是客户端定期询问服务器是否有可用的消息的一种技术。根据轮询频率的不同，轮询的成本可能会很高。它可能会消耗宝贵的服务器资源来回答一个在大多数情况下不提供答案的问题。 ### 长轮询 因为轮询可能效率很低，所以下一个进程是长时间轮询（图 12-4)。 在长轮询中，客户端保持连接打开，直到实际有新的消息或达到超时阈值。一旦客户端收到新消息，它将立即向服务器发送另一个请求，并重新启动该进程。长时间轮询有一些缺点： - 发送方和接收方可能无法连接到同一个聊天服务器。基于 HTTP 的服务器通常是无状态的。如果使用轮询来进行负载平衡，则接收消息的服务器可能与接收消息的客户端没有长时间轮询连接。 - 服务器没有很好的方法来判断客户端是否断开连接。 - 它的效率很低。如果用户不经常聊天，长时间轮询在超时后仍然会进行定期连接。 ### WebSocket WebSocket 是为从服务器到客户端发送异步更新的最常见的解决方案。图 12-5 显示了它的工作原理。 WebSocket 连接由客户机启动。它是双向的和持久性的。它以 HTTP 连接开始使用，并可以通过一些定义良好的握手“升级”到 WebSocket 连接。通过这种持久的连接，服务器可以向客户端发送更新。即使有防火墙，WebSocket 连接通常也可以工作。这是因为它们使用端口 80 或 443，这些端口也被 HTTP/HTTPS 连接使用。 之前我们说过，在发送端，HTTP 是一个很好的协议使用，但是由于 WebSocket 是双向的，没有强烈的技术理由不使用它来发送。图 12-6 显示了 WebSocket（ws）如何用于发送端和接收端。 通过使用 WebSocket 同时进行发送和接收，它简化了设计，并使在客户机和服务器上的实现更加简单。由于 WebSocket 连接是持久性的，因此高效的连接管理在服务器端至关重要。 ### 高级设计 刚才我们提到 WebSocket 被选为客户端和服务器之间的双向通信协议，需要注意的是，其他一切不一定是 WebSocket。事实上，聊天应用程序的大多数功能（注册、登录、用户配置文件等）都可以使用传统的 HTTP 方法上的请求/响应方法。让我们深入一下，看看系统的高级组件。 如图 12-7 所示，聊天系统主要分为三大类：无状态服务、有状态服务和第三方集成。 #### 无状态服务 无状态服务是传统的面向公共的请求/响应服务，用于管理登录、注册、用户配置文件等。这些都是许多网站和应用程序的共同功能。 无状态服务位于负载均衡器的后面，其任务是根据请求路径将请求路由到正确的服务。这些服务可以是整体的，也可以是单个的微服务。我们不需要自己建立许多这样的无状态服务，因为市场上有可以很容易地集成的服务。我们将进一步深入讨论的一个服务是服务发现。它的主要工作是为客户端提供一个客户端可以连接到的聊天服务器的 DNS 主机名列表。 #### 有状态服务 唯一的带有状态的服务是聊天服务。该服务是有状态的，因为每个客户端都维护一个与聊天服务器的持久网络连接。在此服务中，只要服务器仍然可用，客户端通常不会切换到另一个聊天服务器。服务发现与聊天服务紧密协调，以避免服务器超载。我们将深入研究。 #### 第三方集成 对于一个聊天应用程序来说，推送通知是最重要的第三方集成。这是一种在新消息到达时通知用户的方式，即使应用程序没有运行。正确地集成推送通知是至关重要的。更多信息请参考第 10 章设计通知系统。 ### 可扩容性 在小规模范围内，上面列出的所有服务都可以容纳一个服务器。即使在我们设计的规模上，理论上也可以将所有用户连接安装到一个现代云服务器中。服务器可以处理的并发连接的数量很可能是一个限制因素。在我们的场景中，在 100 万并发用户中，假设每个用户连接在服务器上需要 10K 的内存（这是一个非常粗略的数字，非常依赖于语言选择），它只需要大约 10GB 的内存就可以保存一个盒子上的所有连接。 如果我们提出一个一切都在一个服务器上被满足的设计，这可能会在面试官的脑海中产生一个巨大的危险信号。没有一个技术人员会在一台服务器上设计出这样的规模。由于许多因素，单服务器设计是一个交易中断器（deal breaker）。单点失败是其中最大的。 但是，从单一的服务器设计开始是完全可以的。只要确保面试官知道这是一个起点。将我们提到的一切放在一起，图 12-8 显示了调整后的高级设计。 在图 12-8 中，客户端维护到聊天服务器的持久 WebSocket 连接，以进行实时消息传递。 - 聊天服务器，方便了消息的发送/接收。 - 存在服务器管理在线/脱机状态。 - API 服务器处理一切，包括用户登录，注册，更改配置文件等。 - 通知服务器发送推送通知。 - 最后，将键值存储用于存储聊天历史。当一个离线用户上线时，她将看到她之前所有的聊天记录。 ### 存储 此时，我们已经准备好了服务器，服务正在运行，第三方集成已经完成。在技术堆栈的最深处是数据层。数据层通常需要付出一些努力才能做到正确。我们必须做出的一个重要决定是决定使用正确的数据库类型：关系数据库还是 NoSQL 数据库？为了做出明智的决定，我们将检查数据类型和读/写模式。 在一个典型的聊天系统中存在两种类型的数据。第一个是通用数据，如用户配置文件、设置、用户朋友列表。这些数据存储在稳健和可靠的关系数据库中。复制和分片是满足可用性和可伸缩性需求的常用技术。 第二种是聊天系统所独有的：聊天历史数据。理解读/写模式是很重要的。 - 对于聊天系统来说，数据量是巨大的。之前的一项研究[2]显示，Facebook messenger 和 Whatsapp 每天处理 600 亿条信息。 - 只有最近的聊天记录才会经常被访问。用户通常不会向上查找旧的聊天内容。 - 虽然在大多数情况下都可以查看最近的聊天历史，但用户可能会使用需要随机访问数据的功能，比如搜索、查看你提到的内容、跳转到特定的消息等。这些情况应该由数据访问层来支持。 - 一对一聊天应用程序的读写比约为1：1 选择支持我们所有用例的正确的存储系统是至关重要的。我们推荐键值存储，原因如下： - 键值存储允许简单的水平缩放。 - 键值存储为访问数据提供了非常低的延迟。 - 关系数据库不能很好地处理数据的长尾[3]。当索引变大时，随机访问是昂贵的。 - 键值存储被其他已被证明可靠的聊天应用程序所采用。例如，Facebook messenger 和 Discord 都使用键值对存储。Facebook messenger 使用 HBase [4]，而 Discord 则使用 Cassandra[5]。 ### 数据模型 刚才，我们讨论到了使用键值存储作为存储层。最重要的数据是消息数据。让我们仔细观察一下。 #### 1 对 1 聊天的消息表 图 12-9 显示了 1 对 1 聊天的消息表。主键是 message_id，它可以帮助决定消息序列。我们不能依赖 created_at 来决定消息序列，因为可以同时创建两个消息。 | message_id | bigint | | ------------ | --------- | | message_from | bigint | | message_to | bigint | | content | text | | created_at | timestamp | #### 用于群聊功能的消息表 图 12-10 显示了群聊的消息表。复合主键是（channel_id，message_id）。通道和组在这里代表相同的意思。channel_id 是分区键，因为群组聊天中的所有查询都在一个通道中操作。 | channel_id | bigint | | ---------- | --------- | | message_id | bigint | | user_id | bigint | | content | text | | created_at | timestamp | #### 消息 ID 如何生成 message_id 是一个值得探索的有趣话题。*Message_id* 负责确保消息的顺序。要确定消息的顺序，*message_id* 必须满足以下两个要求： - id 必须是唯一的。 - id 应该按时间排序，这意味着新行比旧的 id 具有更高的 id。 我们如何才能实现这两个保证？我想到的第一个想法是 MySql 中的“自动增量”关键字。然而，NoSQL 数据库通常不提供这样的特性。 第二种方法是使用一个全局的 64 位序列数生成器，如雪花[6]。这在“第 7 章：在分布式系统中设计一个唯一 ID 生成器”中讨论。 最后一种方法是使用局部序列号生成器。本地意味着 ID 只在一个组中是唯一的。本地 ID 能够工作的原因是，在一对一的通道或一个组通道中维护消息序列就足够了。与全局 ID 实现相比，这种方法更容易实现。 ## 第 3 步 - 深入设计 在系统设计面试中，通常您需要深入研究高级设计中的一些组件。对于聊天系统，服务发现、消息流、在线/离线指标值得深入探索。 ### 服务发现 服务发现的主要作用是根据地理位置、服务器容量等标准为客户机推荐最好的聊天服务器。Apache Zookeeper[7]是一个流行的用于服务发现的开源解决方案。它注册所有可用的聊天服务器，并根据预定义的标准为客户端选择最好的聊天服务器。 图 12-11 显示了服务发现（Zookeeper）的工作原理。 1. 用户 A 尝试登录到应用程序。 2. 负载平衡器将登录请求发送到 API 服务器。 3. 后端对用户进行身份验证后，服务发现将找到适合用户的最佳聊天服务器 A。在本例中，选择了服务器 2，并将服务器信息返回给用户 A。 4. 用户 A 通过 WebSocket 连接到聊天服务器 2。 ### 消息流 了解聊天系统的端到端流是很有趣的。在本节中，我们将探讨 1 对 1 的聊天流、跨多个设备的消息同步和群组聊天流。 #### 1 对 1 的聊天流 图 12-12 解释了当用户 A 向用户 B 发送消息时所发生的情况。 1. 用户 A 向聊天服务器 1 发送聊天消息。 2. 聊天服务器 1 从 ID 生成器获取消息 ID。 3. 聊天服务器 1 将该消息发送到消息同步队列。 4. 该消息存储在一个键值存储区中。 5. a. 如果用户 B 联机，则将消息转发到连接用户 B 的聊天服务器 2。 b. 如果用户 B 脱机，则会从推送通知（PN）服务器发送推送通知。 6. 聊天服务器 2 将消息转发给用户 B。用户 B 和聊天服务器 2 之间存在持久的 WebSocket 连接。 #### 跨多个设备的消息同步 许多用户都有多个设备。我们将解释如何在多个设备之间同步消息。图 12-13 显示了消息同步的一个示例。 在图 12-13 中，用户 A 有两个设备：手机和笔记本电脑。当用户 A 用她的手机登录到聊天应用程序时，它会与聊天服务器 1 建立一个网络套接字连接。类似地，在笔记本电脑和聊天服务器 1 之间也有一个连接。 每个设备都维护一个名为 *cur_max_message_id* 的变量，它可以跟踪设备上的最新消息 ID。满足以下两个条件的消息将被视为新闻消息： - 收件人 ID 等于当前登录的用户 ID。 - 键值存储中的消息 ID 大于 *cur_max_message_id*。 由于每个设备上都有不同的 *cur_max_message_id*，消息同步很容易，因为每个设备都可以从 KV 存储中获得新的消息。 #### 小组聊天流 与一对一聊天相比，群聊的逻辑更为复杂。图 12-14 和 12-15 解释了该流程。 图 12-14 解释了用户 A 在群聊中发送消息时发生的情况。假设组中有 3 个成员（用户 A、用户 B 和用户 C）。首先，来自用户 A 的消息被复制到每个组成员的消息同步队列中：一个用于用户 B，第二个用于用户 C。您可以将消息同步队列看作是收件人的收件箱。这个设计选择很适合小群聊天，因为： - 它简化了消息同步流，因为每个客户端只需要检查自己的收件箱就可以获得新消息。 - 当组数较小时，在每个收件人的收件箱中存储一个副本并不会太贵。 微信也使用了类似的方法，它将一个组限制在 500 名成员[8]。但是，对于具有大量用户的组，不能为每个成员存储一个消息副本。 在收件人方面，收件人可以接收来自多个用户的消息。每个收件人都有一个收件箱（消息同步队列），其中包含来自不同发件人的邮件。图 12-15 说明了该设计。 ### 在线显示 在线状态指示器是许多聊天应用程序的一个基本特征。通常，您可以在用户的个人资料图片或用户名旁边看到一个绿点。本节解释了在幕后发生的事情。 在高级设计中，存在服务器负责管理在线状态，并通过 WebSocket 与客户端进行通信。有一些流会触发在线状态更改。让我们检查一下每一个。 #### 用户登录 用户登录流程已在“服务发现”部分中进行了说明。在客户端和实时服务之间建立 WebSocket 连接后，用户 A 的在线状态和最后激活的时间戳将保存在 KV 存储中。状态指示器显示用户在登录后已在线。 #### 用户登出 当用户登出时，它会通过用户登出流，如图 12-17 所示。KV 存储中的联机状态更改为脱机。状态指示器显示用户脱机。 #### 用户断开连接 我们都希望我们的互联网连接是一致的和可靠的。然而，情况并非总是如此；因此，我们必须在设计中解决这个问题。当用户断开与互联网的连接时，客户端和服务器之间的持久连接将丢失。处理用户断开连接的一种简单方法是将用户标记为脱机，并在连接重新建立时将状态更改为联机。然而，这种方法有一个主要的缺陷。用户经常在短时间内断开并重新连接到互联网是很常见的。例如，当用户通过隧道时，可以开关网络连接。每次断开/重新连接时更新在线状态会使状态指示器变化过于频繁，导致用户体验不佳。 我们引入了一个心跳机制来解决这个问题。联机客户端会定期向存在服务器发送心跳事件。如果存在服务器在一定时间内接收到心跳事件，比如从客户端接收到 x 秒，则用户被视为在线。否则，它将脱机。在图 12-18 中，客户端每隔 5 秒钟向服务器发送一个心跳事件。在发送 3 个心跳事件后，客户端将断开连接，并且在 x = 30 秒内不重新连接（这个数字是任意选择来演示逻辑的）。联机状态将更改为脱机状态。 #### 在线状态分发 用户 A 的朋友如何知道状态的变化？图 12-19 解释了它是如何工作的。存在服务器使用发布-订阅模型，其中每个朋友对维护一个通道。当用户 A 的在线状态改变时，它将事件发布到通道 A-B、A-C 和 A-D 三个通道。这三个通道分别由用户 B、C 和 D 订阅。因此，朋友们很容易获得在线状态更新。客户端和服务器之间的通信是通过实时的 WebSocket 来进行的。 上述设计对一个小的用户组是有效的。例如，微信也使用了类似的方法，因为它的用户组的上限为 500。对于较大的群体，告知所有成员在线状态是昂贵和耗时的。假设一个群组有 10 万名成员。每次状态更改将产生 10 万个事件。为了解决性能瓶颈，一个可能的解决方案是只有在用户进入一个组或手动刷新好友列表时才获取联机状态。 ## 第 4 步 - 总结 在本章中，我们介绍了一个同时支持一对一聊天和小群组聊天的聊天系统架构。WebSocket 用于客户机和服务器之间的实时通信。聊天系统包含以下组件：用于实时消息传递的聊天服务器、用于管理在线存在的存在服务器、用于发送推送通知的推送通知服务器、用于聊天历史记录持久性的键值存储和用于其他功能的 API 服务器。 如果你在面试结束时有额外的时间，这里有额外的谈话要点： - 扩展聊天应用程序，以支持媒体文件，如照片和视频。媒体文件的大小明显大于文本文件。压缩、云存储和缩略图都是值得讨论的有趣话题。 - 端到端加密。Whatsapp 支持对消息的端到端加密。只有发件人和收件人可以读取邮件。有兴趣的读者应参考参考资料[9]中的文章。 - 在客户端上缓存消息可以有效地减少客户端和服务器之间的数据传输。 - 提高了负载时间。Slack 建立了一个地理分布的网络来缓存用户的数据、通道等，为了获得更好的加载时间[10]。 - 错误处理。 - 聊天服务器错误。一个聊天服务器可能有数十万个，甚至更持久的连接。如果聊天服务器脱机，服务发现（Zookeeper）将为客户端提供一个新的聊天服务器，以建立新的连接。 - 消息重新发机制。重试和排队是重新发送消息的常见技术。 祝贺你能走到这一步！现在拍拍自己的背。干得好！ # 第 13 章：设计一个搜索自动补全系统 当你在谷歌上搜索或在亚马逊上购物时，当你输入搜索框时，就会有一个或多个搜索词的匹配项呈现给你。此功能被称为自动完成、提前打印、按类型搜索或增量搜索。图 13-1 展示了一个谷歌搜索的例子，显示了在搜索框中输入“晚餐”时自动完成的结果列表。搜索自动完成是许多产品的一个重要特性。这就引出了一个面试问题：设计一个搜索自动完成系统，也称为“设计 top k”或“设计 top k 搜索最多的查询”。 ## 第 1 步 - 了解问题，确定设计范围 处理任何系统设计面试问题的第一步是提出足够多的问题来澄清要求。以下是一个候选人-面试官互动的例子： **候选人**：匹配只在搜索查询的开始还是中间也支持？ **面试官**：仅在搜索查询的开始阶段。 **候选人**：系统应该返回多少个自动完成的建议？ **面试官**：5 **候选人**：系统如何知道要返回哪 5 条建议？ **面试官**：这是由受欢迎程度和历史查询频率决定的。 **候选人**：系统是否支持拼写检查？ **面试官**：不支持，不支持拼写检查或自动更正。 **候选人**：搜索查询是用英语进行的吗？ **面试官**：是的。如果时间允许，我们可以讨论多语言支持。 **候选人**：我们允许大写和特殊字符吗？ **面试官**：不，我们假设所有的搜索查询都有小写字母字符。 **候选人**：有多少用户使用该产品？ **面试官**：1000 万 DAU。 ### 需求 这里是需求的摘要： - 快速响应时间：当用户输入搜索查询时，自动完成建议必须显示得足够快。一篇关于脸书的自动完成系统[1]的文章显示，该系统需要在 100 毫秒内返回结果。否则就会导致卡顿。 - 相关性：自动补全建议应该与搜索词相关。 - 排序：系统返回的结果必须根据受欢迎程度或其他排名模型进行排序。 - 可扩展性：该系统可以处理高流量。 - 高可用性：当部分系统处于脱机状态、速度变慢或出现意外的网络错误时，系统应保持可用性和可访问性。 ### 粗略估计 - 假设有 1000 万的日活跃用户（DAU）。 - 平均每人每天进行 10 次搜索。 - 每个查询字符串 20 字节的数据： - 假设我们使用 ASCII 字符编码。1 个字符 = 1 个字节 - 假设一个查询包含 4 个单词，每个单词平均包含 5 个字符。 - 每个查询为 4 x 5 = 20 字节。 - 对于搜索框中输入的每个字符，客户端向后端发送请求以获得自动完成建议。每个搜索查询平均发送 20 个请求。例如，在您输入“晚餐”时，下面 6 个请求被发送到后端。 `search?q=d` `search?q=di` `search?q=din` `search?q=dinn` `search?q=dinne` `search?q=dinner` - ~每秒 24,000 个查询（QPS）= 10,000,000 个用户 * 10 个查询/天 * 20 个字符 / 24 小时 / 3600 秒。 - 峰值 QPS = QPS * 2 = ~48,000 - 假设 20% 的每日查询是新的。1000 万 * 10 个查询/天 * 20 个字节每个查询 * 20% = 0.4 GB。这意味着每天都要增加到存储空间中的 0.4 GB 的新数据。 ## 第 2 步 - 提出高级设计，并获得支持 在高级级别，系统分为两部分： - 数据收集服务：收集用户输入查询并实时聚合。实时处理对于大数据集并不实用；然而，这是一个很好的起点。我们将在深入研究中探索一个更现实的解决方案。 - 查询服务：给定一个搜索查询或前缀，返回 5 个最频繁搜索的术语。 ### 数据收集服务 让我们使用一个简化的例子来看看数据收集服务是如何工作的。假设我们有一个频率表来存储查询字符串及其频率，如图 13-2 所示。在一开始，频率表为空。之后，用户会依次输入 “twitch”, “twitter”, “twitter” 和 “twillo” 等查询。图 13-2 显示了频率表的更新方式。 ### 查询服务 假设我们有一个如表 13-1 所示的频次表。它有两个字段。 - 查询：它存储查询字符串。 - 频次：它表示搜索一个查询的次数。 | 查询 | 频次 | | -------------- | ---- | | Twitter | 35 | | twitch | 29 | | twilight | 25 | | twin peak | 21 | | twitch prime | 18 | | twitter search | 14 | | twillo | 10 | | twin peak sf | 8 | 当用户在搜索框中输入“tw”时，将显示以下前 5 个搜索查询（图 13-3），假设频次表是基于表 13-1 的。 要获得前 5 个经常搜索的查询，请执行以下 SQL 查询： ```sql SELECT * FROM frequency_table WHERE query Like `prefix%` ORDER BY frequency DESC LIMIT 5 ``` 当数据集很小时，这是一个可接受的解决方案。当数据库很大时，访问数据库将成为一个瓶颈。我们将在深入研究中探索优化。 ## 第 3 步 - 深入设计 在高级设计中，我们讨论了数据收集服务和查询服务。高级别的设计不是最优的，但它是一个很好的起点。在本节中，我们将深入研究一些组件，并探索如下优化： - Trie 数据结构 - 数据收集服务 - 查询服务 - 扩展存储 - Trie 操作 ### Trie 数据结构 关系数据库用于高级设计中的存储。然而，从关系数据库中获取前 5 个搜索查询是效率低下的。利用数据结构 trie（前缀树）来克服这个问题。由于 trie 数据结构对系统至关重要，我们将投入大量时间设计定制的 trie。请注意，其中的一些想法来自于文章[2]和[3]。 理解基本的 trie 数据结构对于这个面试问题至关重要。然而，这更多的是一个数据结构问题，而不是一个系统设计问题。此外，许多在线材料也解释了这个概念。在本章中，我们将只讨论对 trie 数据结构的概述，并重点讨论如何优化基本的 trie 以提高响应时间。 Trie（发音为“try”）是一种树状的数据结构，可以紧凑地存储字符串。该名称来自于单词检索，这表明它是为字符串检索操作而设计的。trie 的主要思想包括： - trie 是一种树状的数据结构。 - 根目录表示一个空字符串。 - 每个节点存储一个字符，并有 26 个子节点，每个可能的字符对应一个。为了节省空间，我们不绘制空链接。 - 每个树节点代表一个单个单词或一个前缀字符串 图 13-5 显示了一个包含搜索查询 “tree”, “try”, “true”, “toy”, “wish”, “win” 的测试区域。搜索查询用较粗的边框突出显示。 基本的 trie 数据结构在节点中存储字符。为了支持按频次排序，频次信息需要包含在节点中。假设我们有以下的频次表。 | 查询 | 频次 | | ---- | ---- | | tree | 10 | | try | 29 | | true | 35 | | toy | 14 | | wish | 25 | | win | 50 | 向节点添加频次信息后，更新后的 trie 数据结构如图 13-6 所示。 如何自动完成与 trie 一起工作？在深入研究算法之前，让我们定义一些术语。 - *p*：前缀的长度 - *n*：trie 中的节点总数 - *c*：给定节点的子节点数 下面列出了获得搜索最多的查询的步骤： 1. 找到该前缀。时间复杂度：O(p)。 2. 从前缀节点遍历子树以获得所有有效的子节点。如果一个子项可以形成一个有效的查询字符串，那么它就是有效的。时间复杂度： O(c) 3. 对孩子们进行排序，得到前 k。时间复杂度：O(clogc） 让我们使用图 13-7 所示的一个例子来解释该算法。假设 k 等于 2，并且有一个用户在搜索框中输入“tr”。该算法的工作原理如下： - 步骤 1：找到前缀节点“tr”。 - 步骤 2：遍历子树以获得所有有效的子项。在这种情况下，节点 [tree: 10], [true: 35], [try: 29] 都是有效的。 - 步骤 3：对孩子们进行排序，然后得到前 2 名。[true: 35] 和 [try: 29] 是前缀为“tr”的前两个查询。 该算法的时间复杂度是在上述每个步骤上花费的时间之和： **O(p) + O(c) + O(clogc)** 上述算法都很简单。然而，它太慢了，因为我们需要遍历整个 trie 才能在最坏的情况下得到前 k 个结果。下面是两个优化： 1. 限制前缀的最大长度 2. 在每个节点上缓存顶级搜索查询 让我们一个接一个地看看这些优化。 #### 限制前缀的最大长度 用户很少在搜索框中键入一个长的搜索查询。因此，可以肯定地说 p 是一个很小的整数，比如 50。如果我们限制一个前缀的长度，“找到前缀”的时间复杂度可以从 O(p) 减少到 O(小常数），也就是O(1)。 #### 在每个节点上缓存顶级搜索查询 为了避免遍历整个区域，我们在每个节点上存储最常用的查询。由于 5 到 10 个自动完成建议对用户来说就足够了，所以k是一个相对较小的数字。在我们的具体情况下，只有前 5 个搜索查询被缓存。 通过在每个节点上缓存顶级搜索查询，我们大大降低了检索前 5 个查询的时间复杂度。然而，这种设计需要大量的空间来存储每个节点上的顶级查询。交换时间的空间是非常值得的，因为快速的响应时间是非常重要的。 图 13-8 显示了更新后的 trie 数据结构。前 5 个查询存储在每个节点上。例如，前缀为“be”的节点存储以下内容：[best: 35, bet: 29, bee: 20, be: 15, beer: 10]。 让我们在应用这两个优化后，重新讨论算法的时间复杂度： 1. 找到前缀节点。时间复杂度：O(1) 2. 返回 top k。由于缓存了前 k 个查询，因此这一步的时间复杂度为 O(1)。当每个步骤的时间复杂度降低到 O(1)时，我们的算法只需要 O(1)来获取前 k 个查询。 ### 数据收集服务 在我们之前的设计中，每当用户键入搜索查询时，数据都会实时更新。这种方法不实用，原因有以下两个： - 用户每天可能输入数十亿个查询。在每个查询上更新 trie 会显著降低查询服务的速度。 - 一旦 trie 被建立起来，顶端建议可能不会有太大的变化。因此，没有必要频繁地更新该 trie。 为了设计一个可伸缩的数据收集服务，我们将检查数据来自哪里以及如何使用数据。像 Twitter 这样的实时应用程序需要最新的自动完成建议。然而，许多谷歌关键字的自动完成建议可能不会有太大的变化。 尽管用例存在差异，但数据收集服务的基础基础仍然是相同的，因为用于构建 trie 的数据通常来自分析或日志记录服务。 图 13-9 显示了重新设计的数据收集服务。每个组件都被逐个检查。 **分析日志**。它存储关于搜索查询的原始数据。日志仅附加，没有索引。表 13-3 显示了该日志文件的一个示例。 | 查询 | 时间 | | ---- | ------------------- | | tree | 2019-10-01 22:01:01 | | try | 2019-10-01 22:01:05 | | tree | 2019-10-01 22:01:30 | | toy | 2019-10-01 22:02:22 | | tree | 2019-10-02 22:02:42 | | try | 2019-10-03 22:03:03 | **聚合器**。分析日志的大小通常非常大，而且数据的格式也不正确。我们需要聚合数据，以便我们的系统可以很容易地处理它。 根据用例，我们可能会以不同的方式聚合数据。对于像 Twitter 这样的实时应用程序，我们在更短的时间间隔内聚合数据，因为实时结果很重要。另一方面，减少聚合数据的频率，比如每周一次，对于许多用例来说可能已经足够好了。在面试过程中，验证实时测试结果是否重要。我们假设 trie 是每周重建一次的。 **聚合数据**。表 13-4 显示了每周汇总数据的一个示例。“时间”字段表示一周的开始时间。“频次”字段是该周中相应查询的出现次数的总和。 | 查询 | 时间 | 频次 | | ---- | ---------- | ----- | | tree | 2019-10-01 | 12000 | | tree | 2019-10-08 | 15000 | | tree | 2019-10-15 | 9000 | | toy | 2019-10-01 | 8500 | | toy | 2019-10-08 | 6256 | | toy | 2019-10-15 | 8866 | **工作者**。工作者是一组定期执行异步作业的服务器。他们构建了 trie 数据结构，并将其存储在 Trie DB中。 **快速缓存**。Trie 缓存是一个分布式缓存系统，它将 Trie 保存在内存中以便快速读取。它每周对 DB 进行一次快照。 **Trie 数据库**。Trie DB 是一个持久性存储器。有两个选项可以存储数据： 1. 文档存储：由于每周构建一个新的 trie，所以我们可以定期对它进行快照，序列化它，并将序列化的数据存储在数据库中。像 MongoDB [4]这样的文档存储非常适合序列化数据。 2. 键值存储：通过应用以下逻辑，trie 可以以哈希表[4]形式表示： - trie 中的每个前缀都被映射到哈希表中的一个键。 - 每个 trie 节点上的数据被映射到哈希表中的一个值。 图 13-10 显示了 trie 表和哈希表之间的映射。 在图 13-10 中，左边的每个 trie 节点都映射到 `` 对。如果您不清楚键值存储是如何工作的，请参阅第 6 章：设计一个键值存储。 ### 查询服务 在高级设计中，查询服务直接调用数据库来获取前 5 个结果。图 13-11 显示了改进后的设计，因为以前的设计效率低下。 1. 一个搜索查询将被发送到负载均衡器。 2. 负载均衡器将请求路由到 API 服务器。 3. API 服务器从 trie 缓存中获取 trie 数据，并为客户机构造自动完成建议。 4. 如果数据不在 Trie 缓存中，我们将数据补充回缓存。这样，相同前缀的所有后续请求都从缓存返回。当缓存服务器内存不足或脱机时，可能会发生缓存丢失。 查询服务需要闪电般快的速度。我们建议采用以下优化方案： - AJAX 请求。对于 web 应用程序，浏览器通常会发送 AJAX 请求来获取自动完成的结果。AJAX 的主要好处是，发送/接收请求/响应不会刷新整个网页。 - 浏览器缓存。对于许多应用程序，自动完成搜索建议可能不会在短时间内有太大变化。因此，自动完成建议可以保存在浏览器缓存中，以便允许后续请求直接从缓存中获得结果。谷歌搜索引擎使用相同的高速缓存机制。图 13-12 显示了您在谷歌搜索引擎上键入“系统设计面试”时的响应标题。正如您所看到的，谷歌会将结果在浏览器中缓存 1 小时。请注意：缓存控制中的“private”意味着结果是为单个用户准备的，并且不能由共享缓存进行缓存。“max-age=3600” 意味着缓存有效为 3600 秒，即一小时。 - 数据采样：对于大规模系统，记录每个搜索查询需要大量的处理能力和存储空间。数据采样很重要。例如，系统只记录了每个 N 个请求中的 1 个。 ### Trie 操作 Trie 是自动完成系统的核心组件。让我们来看看 trie 操作（创建、更新和删除）是如何工作的。 #### 创建 Trie 是由工作者使用聚合数据创建的。数据的来源来自于分析日志/DB。 #### 更新 有两种方法可以更新这个 trie。 选项 1：每周更新一次测试信息。一旦创建了新的 trie，新的就将取代旧的。 选项 2：直接更新各个 trie 节点。我们尽量避免这个操作，因为它很慢。然而，如果 trie 的尺寸很小，这是一个可接受的解决方案。当我们更新一个 trie 节点时，它的祖先必须一直更新到根节点，因为祖先存储了子节点的顶级查询。图 13-13 显示了该更新操作如何工作的一个示例。在左侧，搜索查询“beer”的原始值为 10。在右边，它被更新到 30。如您所看到的，节点及其祖先的“beer”值已更新为 30。 #### 删除 我们必须删除可恨、暴力、性露骨或危险的自动补全建议。我们在 Trie 缓存的前面添加了一个过滤器层（图 13-14），以过滤掉不需要的建议。有了一个过滤层，我们就可以灵活地删除基于不同过滤规则的结果。不需要的建议会被异步地从数据库中删除，因此正确的数据集将用于在下一个更新周期中构建 trie。 ### 扩展存储空间 现在我们已经开发了一个系统来为用户带来自动完成查询，当 trie 变得太大而一个服务器无法容纳时，是时候解决可伸缩性问题了。 由于英语是唯一被支持的语言，一种天真的碎片处理方式是基于第一个字符。这里有一些例子。 - 如果我们需要两个服务器进行存储，我们可以在第一个服务器上存储以“a”到“m”开头的查询，在第二个服务器上存储“n”到“z”开头的查询。 - 如果我们需要三个服务器，我们可以将查询分为“a”到“i”、“j”到“r”和“s”到“z”。 按照这个逻辑，我们可以将查询分割为 26 个服务器，因为英语中有 26 个字母字符。让我们将基于第一个字符的分片定义为第一级分片。为了存储超过 26 台服务器的数据，我们可以在第二层甚至第三层碎片。例如，以“a”开头的数据查询可以被分成 4 台服务器：“aa-ag”、“ahan”、“ao-au” 和 “av-az”。 乍一看，这种方法似乎是合理的，直到你意识到以字母 “c” 开头的单词比 “x” 多得多。这就造成了分布的不均匀性。 为了缓解数据不平衡的问题，我们分析了历史数据的分布模式，并应用了更智能的分片逻辑，如图 13-15 所示。碎片映射管理器维护一个查找数据库，用于标识应该存储行的位置。例如，如果对“s”和“u”、“v”、“w”、“x”、“y”和“z”合并的历史查询数量相似，我们可以保持两个碎片：一个为“s”，一个为“u”到“z”。 ## 第 4 步 - 总结 在你完成深入学习后，面试官可能会问你一些后续的问题。 **面试官：您如何扩展您的设计以支持多种语言？** 为了支持其他非英语查询，我们在 trie 节点中存储 Unicode 字符。如果你不熟悉Unicode，这里的定义是：“一个编码标准涵盖了世界上所有书写系统的所有字符，现代和古代”[5]。 **面试官：如果一个国家的顶级搜索查询与其他国家不同呢？** 在这种情况下，我们可能会为不同的国家建立不同的 trie。为了提高响应时间，我们可以在 CDN 中存储 trie。 **面试官：我们如何支持趋势（实时）搜索查询？** 假设发生了一个新闻事件，一个搜索查询就会突然流行起来。我们最初的设计将不会工作，因为： - 离线的工作者还没有计划更新 trie，因为它计划每周运行一次。 - 即使是计划好的，构建 trie 也需要太长的时间。 建立一个实时搜索自动完成是复杂的，超出了本书的范围，所以我们只给出一些想法： - 通过分片来减少工作数据集。 - 更改排名模型，并为最近的搜索查询分配更多的权重。 - 数据可能以流的形式出现，所以我们不能一次性访问所有的数据。流式数据意味着数据是连续生成的。流处理需要一组不同的系统：Apache Hadoop MapReduce [6], Apache Spark Streaming [7], Apache Storm [8], Apache Kafka [9], 等等。因为所有这些主题都需要特定的领域知识，所以我们在这里不详细讨论。 祝贺你能走到这一步！现在拍拍自己的背。干得好！ # 第 14 章：设计 Youtube 在本章中，您将被要求设计 YouTube。这个问题的解决方案也可以应用到其他的面试问题上，比如设计一个视频分享平台，比如 Netflix 和 Hulu。图 14-1 显示了 YouTube 的主页。 YouTube 看起来很简单：内容创造者可以上传视频，观众可以点击播放。它真的有那么简单吗？不是真的。在简单性之下有许多复杂的技术。让我们来看看 2020 年的一些令人印象深刻的统计数据、人口统计数据和有趣的事实 [1] [2]。 - 每月活跃用户总数：20 亿。 - 每天观看的视频数量：50 亿次。 - 73% 的美国成年人使用 YouTube。 - 在 YouTube 上的 5000 万创作者。 - YouTube 2019 年全年的广告收入为 151 亿美元，较 2018 年增长了 36%。 - YouTube 占所有移动互联网流量的 37%。 - YouTube 有 80 种不同语言的版本。 从这些统计数据中，我们知道 YouTube 是巨大的，全球性的，赚了很多钱。 ## 第 1 步 - 了解问题，确定设计范围 如图 14-1 所示，除了观看视频外，你还可以在 YouTube 上做更多的事情。例如，评论、分享或喜欢视频，将视频保存到播放列表，订阅频道等等。我们不可能在一个 45 分钟或 60 分钟的采访中设计出所有的东西。因此，提出问题以缩小研究范围是很重要的。 **候选人**：哪些功能是重要的？ **面试官**：能够上传视频和观看视频。 **候选人**：我们需要支持什么客户？ **面试官**：移动应用程序、网络浏览器和智能电视。 **候选人**：我们有多少个日常活跃的用户？ **面试官**：5 百万。 **候选人**：每天花在这个产品上的平均时间是多少？ **面试官**：30分钟。 **候选人**：我们需要支持国际用户吗？ **面试官**：是的，很大一部分用户都是国际用户。 **候选人**：所支持的视频分辨率是多少？ **面试官**：该系统可以接受大部分的视频分辨率和格式。 **候选人**：您需要加密吗？ **面试官**：是的。 **候选人**：对视频有什么文件大小的要求吗？ **面试官**：我们的平台专注于中小型视频。允许的最大视频大小为 1GB。 **候选人**：我们能利用亚马逊、谷歌或微软提供的一些现有的云基础设施吗？ **面试官**：这是一个很好的问题。对大多数公司来说，从零开始构建一切都是不现实的，建议你利用一些现有的云服务。 在本章中，我们重点设计一个具有以下特点的视频流服务： - 能够快速上传视频 - 平滑视频流的能力 - 改变视频质量 - 低基础设施成本 - 高可用性、可扩展性和可靠性要求 - 客户端支持：移动应用程序、网络浏览器和智能电视 ### 粗略估计 下面的估计是基于许多假设的，所以与面试官沟通以确保她在同一页上是很重要的。 - 假设该产品有 500 万日活跃用户（DAU）。 - 用户每天观看 5 个视频。 - 有 10% 的用户每天上传 1 个视频。 - 假设平均视频大小为 300 MB。 - 每日所需的总存储空间：500 万 * 10% * 300 MB = 150 TB - CDN 成本。 - 当云 CDN 提供视频时，您将为从 CDN 传输的数据收费。 - 让我们使用亚马逊的 CDN 云前来进行成本估算（图 14-2）[3]。假设 100% 的交通服务都来自美国。每 GB 的平均成本是 0.02 美元。为简单起见，我们只计算视频流的成本。 - 500 万 * 5 个视频 * 0.3 GB * 0.02 美元 = 每天 15 万美元。 从粗略的成本估算来看，我们知道提供来自 CDN 的视频要花费很多钱。尽管云服务提供商愿意大幅降低大客户的 CDN 成本，但成本仍然相当可观。我们将讨论在深入研究中降低 CDN 成本的方法。 ## 第 2 步 - 提出高级设计，并获得支持 如前所述，面试官建议利用现有的云服务，而不是从头开始构建所有的东西。CDN 和 blob 存储是我们将利用的云服务。有些读者可能会问，为什么不自己建造一切呢？原因如下： - 系统设计面试并不是关于从头开始构建一切的。在有限的时间范围内，选择正确的技术来做正确的工作比详细解释技术如何工作更重要。例如，提到用于存储源视频的小块存储对采访来说就足够了。谈论斑点存储的详细设计可能有点过头了。 - 构建可扩展的 blob 存储或 CDN 是极其复杂和昂贵的。即使是像奈飞或脸书这样的大公司也不是自己建造一切的。网飞利用了亚马逊的云服务[4]，脸书使用了 Akamai 的 CDN [5]。 在高层次中，系统由三个组成部分组成（图 14-3)。 **客户端**：你可以在电脑、手机和智能电视上观看 YouTube。 **CDN**：视频存储在 CDN 中。当你按播放键时，会从 CDN 播放视频。 **API 服务器**：除了视频流之外，其他一切都要通过 API 服务器。这包括推送推荐、生成视频上传 URL、更新元数据数据库和缓存、用户注册等。 在问答环节中，面试官对两种流程表现出了兴趣： - 视频上传工作流 - 视频流工作流。 我们将探索每个流程的高级设计。 ### 视频上传流程 图 14-4 为视频上传的高级设计。 这包括了以下组件： - 用户：用户在电脑、手机或智能电视等设备上观看 YouTube。 - 负载均衡器：一个负载均衡器在 API 服务器之间均匀地分配请求。 - API 服务器：除视频流外，所有用户请求都要通过 API 服务器。 - 元数据数据库：视频元数据存储在元数据数据库中。它被分割和复制，以满足性能和高可用性的要求。 - 元数据缓存：为了获得更好的性能，需要缓存视频元数据和用户对象。 - 原始存储：一个 blob 存储系统用于存储原始视频。维基百科中关于 blob 存储的引文显示：“二进制大对象（BLOB）是作为单一实体存储在数据库管理系统中的二进制数据的集合”[6]。 - 转码服务器：视频转码也被称为视频编码。它是将视频格式转换为其他格式（MPEG、HLS 等）的过程，这为不同的设备和带宽能力提供了最好的视频流。 - 转码存储器：它是一个存储转码的视频文件的 blob 存储器。 - CDN：视频被缓存在 CDN 中。当您点击播放按钮，一个视频从 CDN 获取流。 - 完成队列：它是存储有关视频转码完成事件的信息的消息队列。 - 完成处理程序：它包含一个从完成队列中提取事件数据并更新元数据缓存和数据库的工作者列表。 现在我们已经单独了解了每个组件，让我们来研究一下视频上传流是如何工作的。该流程被分成两个并行运行的进程。 1. 上传实际的视频。 2. 更新视频元数据。元数据包含有关视频 URL、大小、分辨率、格式、用户信息等的信息。 #### 流程 a：上传实际的视频 图 14-5 显示了如何上传实际的视频。具体说明如下图所示： 1. 视频会被上传到原始的存储器中。 2. 转码服务器从原始存储器中获取视频并开始转码。 3. 当转码完成后，将并行执行以下两个步骤： 3a. 转码的视频被发送到转码存储器。 3b. 转码完成事件将在完成队列中排队。 3a.1. 转码的视频被分发给 CDN。 3b.1. 完成处理程序包含一群连续地从队列中提取事件数据的工作者。 3b.1.a. 和 3b.1.b. 完成处理程序会在视频转码完成时更新元数据数据库和高速缓存。 4. API 服务器通知客户端视频已成功上传并准备好流媒体。 #### 流程 b：更新元数据 当文件上传到原始存储时，客户端并行发送更新视频元数据的请求，如图 14-6 所示。该请求包含视频元数据，包括文件名、大小、格式等。API 服务器会更新元数据高速缓存和数据库。 ### 视频流工作流 每当你在 YouTube 上观看视频时，它通常会立即开始流媒体，你不会等到整个视频被下载。下载意味着整个视频被复制到你的设备上，而流媒体意味着你的设备不断接收来自远程源视频的视频流。当你观看流媒体视频时，你的客户一次加载一点数据，这样你就可以立即和连续地观看视频。 在我们讨论视频流工作流之前，让我们看看一个重要的概念：流媒体协议。这是一种控制视频流的数据传输的标准化方法。流行的流媒体协议有： - MPEG-DASH。MPEG 代表“移动图像专家组（Moving Picture Experts Group）”，DASH 代表“HTTP 上的动态自适应流媒体（Dynamic Adaptive Streaming over HTTP）”。 - Apple HLS。HLS 代表“HTTP 直播流（HTTP Live Streaming）”。 - Microsoft Smooth Streaming - Adobe HTTP Dynamic Streaming（HDS）。 您不需要完全理解甚至记住那些流协议名称，因为它们是需要特定领域知识的底层细节。这里重要的是要了解不同的流媒体协议支持不同的视频编码和播放播放器。当我们设计一个视频流媒体服务时，我们必须选择正确的流媒体协议来支持我们的用例。要了解更多关于流媒体协议的信息，这里是一篇优秀的文章[7]。 视频直接从 CDN 上播放。最接近您的边缘服务器将发送视频。因此，延迟时间非常小。图 14-7 显示了视频流的高级设计 ## 第 3 步 - 深入设计 在高层设计中，整个系统被分为视频上传工作流和视频流工作流两部分。在本节中，我们将通过重要的优化来优化这两个流程，并引入错误处理机制。 ### 视频转码 当你录制视频时，设备（通常是手机或相机）会给视频文件提供一定的格式。如果您希望视频在其他设备上流畅播放，视频必须编码成兼容的比特率和格式。比特率是指随着时间的推移而处理比特的速率。较高的比特率通常意味着更高的视频质量。高比特率流需要更多的处理能力和快速的网速。 视频转码之所以重要，原因如下： - 原始视频会消耗了大量的存储空间。以每秒 60 帧的速度录制一个小时的高清视频可以占用几百 GB 的空间。 - 许多设备和浏览器只支持某些类型的视频格式。因此，出于兼容性的原因，将视频编码为不同的格式是很重要的。 - 为了确保用户在保持平稳播放的同时观看高质量的视频，最好向具有高网络带宽的用户提供高分辨率的视频，向具有低带宽的用户提供低分辨率的视频。 - 网络条件可能会改变，特别是在移动设备上。为了确保视频的连续播放，根据网络条件自动或手动切换视频质量对于流畅的用户体验至关重要。 有许多类型的编码格式可用；但是，其中大多数都包含两部分： - 容器：这就像一个包含视频文件、音频和元数据的篮子。您可以通过文件扩展名来区分容器格式，例如 .avi、.mov 或 .mp4。 - 编解码器：这些是压缩和解压缩算法，旨在减少视频大小，同时保持视频质量。最常用的视频编解码器是 H.264、VP9 和 HEVC。 ### 有向无环图（DAG）模型 转换一个视频在计算上是昂贵的和耗时的。此外，不同的内容创造者可能会有不同的视频处理要求。例如，一些内容创造者要求在他们的视频上设置水印，一些人自己提供缩略图，还有一些人上传高清视频，而另一些人则没有。 为了支持不同的视频处理管道并保持高并行性，添加一定程度的抽象并让客户机程序员定义要执行哪些任务是很重要的。例如，脸书的流媒体视频引擎使用有向无环图（DAG）编程模型，该模型分阶段定义任务，以便可以顺序或并行执行[8]。在我们的设计中，我们采用了一个类似的 DAG 模型来实现灵活性和并行性。图 14-8 表示用于视频转换编码的 DAG。 在图 14-8 中，原始视频被分割为视频、音频和元数据。这里是一些可以应用于视频文件的任务： - 检查：确保视频有良好的质量，没有畸形。 - 视频编码：视频被转换为支持不同的分辨率，编解码器，比特率等。图 14-9 显示了一个视频编码文件的示例。 - 缩略图。缩略图既可以由用户上传，也可以由系统自动生成。 - 水印：视频上的图像覆盖包含有关视频的识别信息 ### 视频转码体系结构 建议的利用云服务的视频转换编码架构如图 14-10 所示。 该体系结构有六个主要组件：预处理器、DAG 调度器、资源管理器、任务工作者、临时存储和作为编码视频的输出。让我们仔细看看每个组件。 #### 预处理器 预处理器有 4 个职责： 1. 视频分割。视频流被分割或进一步分割成更小的图片组（GOP）排列。GOP 是按特定顺序排列的一组帧。每个块都是一个独立的播放单元，通常只有几秒钟的长度。 2. 一些旧的移动设备或浏览器可能不支持视频分割。预处理器按 GOP 排列分割视频给旧客户端。 3. DAG 的生成。处理器根据客户机程序员编写的配置文件生成 DAG。图 14-12 是一个简化的 DAG 表示形式，它有 2 个节点和 1 条边： 此 DAG 表示方式由以下两个配置文件生成（图 14-13)： 4. 缓存数据。预处理器是分段视频的高速缓存。为了获得更好的可靠性，预处理器将 GOP 和元数据存储在临时存储中。如果视频编码失败，系统可以使用持久化数据进行重试操作。 #### DAG 调度器 DAG 调度程序将 DAG 图划分为任务阶段，并将它们放入资源管理器中的任务队列中。图 14-15 显示了 DAG 调度程序如何工作的一个示例。 如图 14-15 所示，原始视频被分为三个阶段：阶段 1：视频、音频和元数据。视频文件在阶段 2 中被进一步分为两个任务：视频编码和缩略图。音频文件需要将音频编码作为阶段 2 任务的一部分。 #### 资源管理器 资源经理负责管理资源分配的效率。它包含 3 个队列和一个任务调度程序，如图 14-17 所示。 - 任务队列：它是一个所要执行的包含任务的优先级队列。 - 工作者队列：它是一个包含工作者利用率信息的优先级队列。 - 运行队列：它包含关于当前运行的任务和运行任务的工作人员的信息。 - 任务调度程序：它选择最佳任务/工作者，并指示所选择的任务工作者执行作业。 资源管理器的工作方式如下： - 任务调度器从任务队列中获得最高优先级的任务。 - 任务调度程序从工作程序队列中获取要运行该任务的最佳任务工作程序。 - 任务调度程序将指示所选的任务工作者运行该任务。 - 任务调度程序将绑定任务/工作者信息，并将其放入正在运行的队列中。 - 任务完成后，任务调度程序将从正在运行的队列中删除作业。 #### 任务工作者 任务工作者运行在 DAG 中定义的任务。不同的任务工作者可以运行不同的任务，如图 14-19 所示。 #### 临时存储 这里使用了多个存储系统。存储系统的选择取决于数据类型、数据大小、访问频率、数据寿命等因素。例如，工作者经常访问元数据，而且数据的大小通常很小。因此，在内存中缓存元数据是一个好主意。对于视频或音频数据，我们将它们放在 blob 存储器中。一旦相应的视频处理完成，临时存储器中的数据就会被释放出来。 #### 编码视频 被编码的视频是编码管道的最终输出。下面是输出的一个例子：funny_720p.mp4。 ### 系统优化 此时，视频上传流应该对视频转码和视频流有很好的了解。接下来，我们将通过优化来优化系统，包括速度、安全性和节省成本。 #### 速度优化：并行化视频上传 上传一个视频作为一个整体的单元是效率低下的。我们可以按 GOP 排列将一个视频分割成更小的块，如图 14-22 所示。 这允许在上次上载失败时快速恢复上载。客户端可以实现通过 GOP 分割视频文件的工作，以提高上传速度，如图 14-23 所示。 #### 速度优化：将上传中心放置在用户附近 另一种提高上传速度的方法是在全球各地建立多个上传中心（图 14-24）。美国人可以将视频上传到北美上传中心，中国人可以将视频上传到亚洲上传中心。为了实现这一点，我们使用 CDN 作为上传中心 #### 速度优化：处处具有并行性 实现低延迟需要认真的努力。另一个优化方法是建立一个松散耦合的系统，并实现高并行性。 我们的设计需要做一些修改来实现高并行性。让我们放大视频如何从原始存储传输到 CDN 的流程。流程如图 14-25 所示，表明输出取决于上一步的输入。这种依赖性使并行性变得困难。 为了使系统更松散地耦合，我们引入了如图 14-26 所示的消息队列。让我们使用一个例子来解释消息队列如何使系统更松散地耦合。 - 在引入消息队列之前，编码模块必须等待下载模块的输出。 - 在引入消息队列后，编码模块不再需要等待下载模块的输出。如果消息队列中存在事件，则编码模块可以并行地执行这些作业。 #### 安全优化：预先签名的上传 URL 安全是任何产品中最重要的方面之一。为了确保只有经过授权的用户才能将视频上传到正确的位置，我们引入了预签名的 URL，如图 14-27 所示。 上传流更新如下： 1. 客户端向 API 服务器发出 HTTP 请求，以获取预签名的 URL，该 URL 授予对 URL 中标识的对象的访问权限。预签 URL 一词用于上传文件到 Amazon S3。其他云服务提供商可能会使用不同的名称。例如，微软 Azure blob 存储支持相同的功能，但称之为“共享访问签名”[10]。 2. API 服务器用一个预先签名的 URL 进行响应。 3. 一旦客户端收到响应，它就会使用预先签名的 URL 上传视频。 #### 安全优化：保护您的视频 许多内容制作者不愿在网上发布视频，因为他们担心自己的原创视频会被盗。为了保护受版权保护的视频，我们可以采用以下三个安全选项之一： - 数字版权管理（DRM）系统：三个主要的 DRM 系统是 Apple FairPlay，Google Widevine，和 Microsoft PlayReady。 - AES 加密：您可以加密视频并配置授权策略。加密的视频将在回放时被解密。这就确保了只有经过授权的用户才能观看加密的视频。 - 视觉水印：这是一个图像覆盖在您的视频之上，包含为您的视频的识别信息。它可以是你的公司标志或公司名称。 #### 节约成本的优化 CDN 是我们系统的一个重要组成部分。它确保了在全球范围内的快速视频交付。然而，从粗略计算，我们知道 CDN 是昂贵的，特别是当数据大小很大时。我们如何才能降低成本？先前的研究表明，YouTube 视频流遵循长尾分布的 [11] [12]。这意味着一些流行的视频经常被访问，但其他许多视频很少或没有观众。基于这一观察结果，我们实现了一些优化： 1. 仅提供来自 CDN 的最受欢迎的视频和来自我们的高容量存储视频服务器的其他视频（图 14-28）。 2. 对于不太受欢迎的内容，我们可能不需要存储许多编码的视频版本。短视频可以按需编码。 3. 有些视频只在某些地区很受欢迎。没有必要向其他地区分发这些视频。 4. 建立你自己的 CDN，比如 Netflix，并与互联网服务提供商（ISP）合作。构建你的 CDN 是一个巨大的项目；然而，这对大型流媒体公司来说可能是有意义的。互联网服务提供商可以是康卡斯特（Comcast）、美国电话电报公司（AT&T）、威瑞森（Verizon）或其他互联网提供商。ISP 位于世界各地，与用户关系密切。通过与 ISP 合作，您可以改善观看体验，减少带宽费用。 所有这些优化都是基于内容的流行程度、用户访问模式、视频大小等。在进行任何优化之前，分析历史查看模式是很重要的。以下是一些关于这个主题的有趣的文章： [12] [13]。 ### 错误处理 对于一个大规模的系统，系统错误是不可避免的。要构建一个高度容错的系统，我们必须优雅地处理错误并快速恢复错误。存在两种类型的错误： - 可恢复的错误。对于可恢复的错误，如视频段无法转码，一般的想法是重试几次操作。如果任务继续失败，并且系统认为它是不可恢复的，那么它会向客户端返回一个正确的错误代码。 - 不可恢复的错误。对于不可恢复的错误，如格式错误的视频格式，系统将停止与视频相关联的运行任务，并将正确的错误代码返回给客户端。 以下剧本涵盖了每个系统组件的典型错误： - 上传错误：重试几次。 - 分割视频错误：如果旧版本的客户端不能通过 GOP 排列分割视频，则将整个视频被传递给服务器。拆分视频的工作是在服务器端完成的。 - 转码错误：重试。 - 预处理器错误：重新生成 DAG 图。 - DAG 调度程序错误：重新调度一个任务。 - 资源管理器队列：使用一个复制副本。 - 任务工作者关闭：在新的工作者上重试该任务。 - API 服务器关闭：API 服务器是无状态的，因此请求将被定向到一个不同的 API 服务器。 - 元数据缓存服务器关闭：数据被复制多次。如果一个节点宕机，您仍然可以访问其他节点来获取数据。我们可以打开一个新的缓存服务器来替换死的。 - 元数据数据库服务器关闭： - 主机宕机。如果主机倒下了，提升其中一个从机成为新的主机。 - 从机宕机。如果一个从服务器宕机，您可以使用另一个从服务器进行读取，并打开另一个数据库服务器来替换死去的数据库服务器。 ## 第 4 步 - 总结 在本章中，我们介绍了诸如 YouTube 等视频流媒体服务的架构设计。如果在面试结束时有额外的时间，以下几点： - 扩展 API 层：因为 API 服务器是无状态的，所以很容易水平扩展 API 层。 - 扩展数据库：您可以讨论数据库复制和分片。 - 直播：它指的是如何实时录制和播放视频的过程。虽然我们的系统不是专门为直播而设计的，但直播和非直播有一些相似之处：两者都需要上传、编码和流媒体。显著的区别是： - 直播流媒体有更高的延迟要求，因此它可能需要一个不同的流媒体协议。 - 直播流媒体对并行性的要求较低，因为小块数据已经被实时处理了。 - 直播流媒体需要不同的错误处理集。任何需要太多时间的错误处理都是不可接受的。 - 视频删除：删除侵犯版权、色情或其他违法行为的视频。有些可以在上传过程中发现，而另一些可能通过用户标记发现。 祝贺你能走到这一步！现在拍拍自己的背。干得好！ # 第 15 章：设计谷歌 Drive 近年来，云存储服务如谷歌 Dropbox、微软 OneDrive 和苹果 iCloud 已经变得非常流行。在本章中，您将被要求设计谷歌 Drive。 在投入设计之前，让我们花一点时间来了解谷歌 Drive。谷歌 Drive 是一个文件存储和同步服务，它可以帮助您在云中存储文档、照片、视频和其他文件。您可以从任何电脑、智能手机和平板电脑上访问您的文件。您可以很容易地与朋友、家人和同事[1]共享这些文件。图 15-1 和 15-2 分别显示了谷歌 Drive 在浏览器和移动应用程序上的外观。 ## 第 1 步 - 了解问题，确定设计范围 设计一个谷歌 Drive 是一个大项目，所以问问题来缩小范围是很重要的。 **候选人**：最重要的特征是什么？ **面试官**：上传和下载文件，文件同步，和通知。 **候选人**：这是一个移动应用程序，一个网络应用，还是两者都有？ **面试官**：两者兼而有之。 **候选人**：所支持的文件格式是什么？ **面试官**：任何文件类型。 **候选人**：文件需要加密吗？ **面试官**：是的，存储器中的文件必须被加密。 **候选人**：你有文件大小的限制吗？ **面试官**：是的，文件必须是 10 GB 或更小的文件。 **候选人**：该产品有多少个用户？ **面试官**：一千万 DAU。 在本章中，我们将重点关注以下特性： - 添加文件。添加文件最简单的方法是将文件拖放到谷歌 Drive 中。 - 下载文件。 - 跨多个设备同步文件。当一个文件被添加到一个设备时，它将自动同步到其他设备。 - 请参见文件修订版。 - 与您的朋友、家人和同事共享文件 - 当编辑、删除或与您共享文件时发送通知。 本章未讨论的功能包括： - 谷歌文档编辑和协作。谷歌文档允许多个人同时编辑同一个文档。这超出了我们的设计范围。 除了明确需求外，理解非功能性需求也很重要： - 可靠性。可靠性对于一个存储系统来说是非常重要的。数据丢失是不可接受的。 - 快速同步速度。如果文件同步花费太多时间，用户会放弃产品。 - 带宽的使用情况。如果一个产品占用了大量不必要的网络带宽，用户将会不满意，特别是当他们正在使用移动数据计划时。 - 可伸缩性。该系统应该能够处理大量的流量。 - 高可用性。当某些服务器脱机、变慢或出现意外网络错误时，用户仍然能够使用系统。 ### 粗略估计 - 假设该应用程序有 5000 万注册用户和 1000 万 DAU。 - 用户有 10 GB 的空闲空间。 - 假设用户每天上传 2 个文件。平均文件大小为 500 KB。 - 1：1 的读写比。 - 总分配空间：5000 万 * 10 GB = 500 PB - QPS 用于上传 API：1000 万 * 2 上传 / 24 小时 / 3600 秒 = ~240 - 峰值 QPS = QPS * 2 = 480 ## 第 2 步 - 提出高级设计，并获得支持 我们将使用一种稍微不同的方法，而不是从一开始就显示高级设计图。我们将从一些简单的事情开始：在一个服务器中构建所有内容。然后，逐步扩大其规模，以支持数百万用户。通过做这个练习，它可以让你重新想起书中所涵盖的一些重要主题。 让我们从如下所列的单一服务器设置开始： - 一个上传和下载文件的 web 服务器。 - 一个跟踪元数据的数据库，如用户数据、登录信息、文件信息等。 - 一个用来存储文件的存储系统。我们分配了 1 TB 的存储空间来存储文件。 我们花了几个小时建立了一个 Apache web 服务器，一个 MySql 数据库，和一个名为 *drive/* 的目录，作为根目录来存储上传的文件。在 *drive/* 目录下，有一个目录列表，称为名称空间。每个名称空间都包含该用户的所有上载文件。服务器上的文件名与原始文件名保持相同。每个文件或文件夹都可以通过连接名称空间和相对路径来唯一标识。 图 15-3 显示了 */drive* 目录的左侧和右侧的展开视图的情况。 ### APIs API 是什么样的？我们主要需要 3 个 API：上传一个文件，下载一个文件，并获得文件修订。 #### 1. 上传一个文件到谷歌 Drive 支持两种类型的上传： - 简单上传。当文件大小较小时，请使用此上载类型。 - 可恢复的上传。当文件大小较大且存在网络中断的可能性很高时，请使用此上载类型。 下面是一个可恢复的上传 API 的例子： *https://api.example.com/files/upload?uploadType=resumable* 参数： - uploadType=resumable - 数据：要上传的本地文件 通过以下的 3 个步骤来实现可恢复的上传 [2]： - 发送初始请求以恢复可恢复的 URL。 - 上传数据并监控上传状态。 - 如果上传中断，请继续上传。 #### 2. 从谷歌 Drive 下载一个文件 示例 API： https://api.example.com/files/download 参数： - path：下载文件路径。 示例参数： ```json { "path": "/recipes/soup/best_soup.txt" } ``` #### 3. 获取文件修订 示例 API：https://api.example.com/files/list_revisions 参数： - path：你想要获取修订历史的文件路径 - limit：返回的修订的最大数量 示例参数： ```json { "path": "/recipes/soup/best_soup.txt", "limit": 20 } ``` 所有的 API 都需要用户身份验证并使用 HTTPS。安全套接字层（SSL）可以保护客户端和后端服务器之间的数据传输。 ### 从单个服务器出发 随着更多文件的上传，最终您会得到空间满警报，如图 15-4 所示。 只剩下 10 MB 的存储空间了！这是一个紧急情况，因为用户不能再上传文件了。我想到的第一个解决方案是分割数据，以便将其存储在多个存储服务器上。图 15-5 显示了一个基于 user_id 的分片示例。 你拉一个通宵来设置数据库分片并密切监视它。一切又顺利了。您已经阻止了火灾，但您仍然担心在存储服务器中断时可能出现的数据丢失。你四处询问，你的后端大师朋友弗兰克告诉你，许多领先的公司，如 Netflix 和 Airbnb，都使用亚马逊 S3 进行存储。“亚马逊简单存储服务（Amazon S3）是一项对象存储服务，提供业界领先的可伸缩性、数据可用性、安全性和性能”[3]。你决定做一些调查，看看它是否合适。 经过大量阅读，您对 S3 存储系统有了很好的了解，并决定在 S3 中存储文件。Amazon S3 支持同区域复制和跨区域复制。区域是亚马逊网络服务（AWS）有数据中心的地理区域。如图 15-6 所示，数据可以在同一区域（左侧）和跨区域（右侧）进行复制。冗余文件存储在多个区域中，以防止数据丢失和确保可用性。一个桶就像一个文件系统中的一个文件夹。 在将文件放入 S3 后，你终于可以睡了一个好觉，而不用担心数据丢失。为了防止类似的问题在未来发生，你决定对你可以改进的领域进行进一步的研究。以下是你能找到的几个方面： - 负载均衡器：添加一个负载均衡器来分配网络流量。负载均衡器可以确保了均匀分布的流量，如果 web 服务器宕机，它将重新分配流量。 - Web 服务器：在添加了负载均衡器后，可以根据流量负载轻松地添加/删除更多的 Web 服务器。 - 元数据数据库：将数据库移出服务器，以避免单点故障。同时，设置数据复制和分片，以满足可用性和可伸缩性的需求。 - 文件存储： Amazon S3 用于文件存储。为了确保可用性和持久性，文件将在两个独立的地理区域中进行复制。 在应用上述改进之后，您成功地从单个服务器分离了 web 服务器、元数据数据库和文件存储。更新后的设计如图 15-7 所示。 ### 同步冲突 对于像谷歌 Drive 这样的大型存储系统，同步冲突会不时发生。当两个用户同时修改同一个文件或文件夹时，就会发生冲突。我们如何解决冲突？我们的策略是：得到处理的第一个版本将获胜，稍后得到处理的版本将收到冲突。图 15-8 显示了一个同步冲突的示例。 在图 15-8 中，用户 1 和用户 2 尝试同时更新相同的文件，但是用户 1 的文件首先由我们的系统处理。用户 1 的更新操作会通过，但是，用户 2 会发生同步冲突。我们如何解决用户 2 的冲突？我们的系统提供了同一文件的两个副本：user 2 的本地副本和来自服务器的最新版本（图 15-9）。用户 2 可以选择合并两个文件或用一个版本覆盖另一个版本。 当多个用户同时编辑同一文档时，保持文档同步具有挑战性。有兴趣的读者应参考参考材料[4] [5]。 ### 高级设计 图 15-10 说明了所建议的高层设计。让我们检查一下系统的每个组成部分。 **用户**：用户通过浏览器或移动应用程序使用该应用程序。 **块服务器**：块服务器将块上载到云存储。块存储，称为块级存储，是一种在基于云的环境中存储数据文件的技术。一个文件可以被分成几个块，每个块都有一个唯一的哈希值，存储在我们的元数据数据库中。每个块都被视为一个独立的对象，并存储在我们的存储系统（S3）中。为了重建文件，块按特定的顺序连接。至于块的大小，我们使用 Dropbox 作为参考：它将块的最大大小设置为 4 MB [6]。 **云存储**：一个文件被分割成更小的块，并存储在云存储中。 **冷库**：冷库是一种设计用来存储非活动数据的计算机系统，这意味着文件不能长时间被访问。 **负载均衡器**：负载均衡器在 API 服务器之间均匀地分配请求。 **API 服务器**：除了上传流之外，它们还负责几乎所有的事情。API 服务器用于用户身份验证、管理用户配置文件、更新文件元数据等。 **元数据数据库**：存储用户、文件、块、版本等的元数据。请注意，文件存储在云中，而元数据数据库中只包含元数据。 **元数据缓存**：一些元数据被缓存以供快速检索。 **通知服务**：它是一个发布者/订阅者系统，允许在某些事件发生时将数据从通知服务传输到客户端。在我们的具体情况下，当文件在其他地方添加/编辑/删除时，通知服务会通知相关客户，以便他们可以提取最新的更改。 **脱机备份队列**：如果客户端脱机并且无法提取最新的文件更改，则脱机备份队列将存储该信息，以便在客户端联机时同步更改。 我们已经在高层讨论了谷歌 Drive 的设计。其中一些组件很复杂，值得仔细检查；我们将在深入设计中详细讨论这些问题。 ## 第 3 步 - 深入设计 在本节中，我们将仔细了解以下内容：块服务器、元数据数据库、上载流、下载流、通知服务、节省存储空间和故障处理。 ### 块服务器 对于定期更新的大型文件，在每次更新时发送整个文件会消耗大量带宽。提出了两种优化方法来最小化被传输的网络通信量： - 增量同步。当一个文件被修改时，只有修改后的块被同步，而不是使用同步算法[7] [8]同步整个文件。 - 压缩。在块上应用压缩可以显著减少数据的大小。因此，根据文件类型，使用压缩算法来压缩块。例如，gzip 和 bzip2 用于压缩文本文件。需要不同的压缩算法来压缩图像和视频。 在我们的系统中，块服务器做上传文件的繁重工作。阻止服务器通过将文件分割为块、压缩每个块并对它们进行加密来处理从客户端传递的文件。不将整个文件上传到存储系统，而是只传输修改后的存储系统。图 15-11 显示了在添加新文件时，块服务器的工作方式。 - 一个文件被分割成更小的块。 - 每个块都使用压缩算法进行压缩。 - 为了确保安全性，每个块在被发送到云存储之前都要进行加密。 - 块将被上传到云存储中。 图 15-12 说明了增量同步，这意味着只有修改后的块才会被转移到云存储中。高亮显示的块“块 2”和“块 5”表示改变的块。使用增量同步，只有这两个块被上传到云存储。 块服务器允许我们通过提供增量同步和压缩来节省网络流量。 ### 高一致性要求 我们的系统默认要求很强的一致性。不同的客户端同时显示不同的文件是不可接受的。系统需要为元数据缓存和数据库层提供强大的一致性。 默认情况下，内存缓存采用了最终的一致性模型，这意味着不同的副本可能有不同的数据。为了实现强大的一致性，我们必须确保以下内容： - 缓存副本中的数据和主数据是一致的。 - 无效数据库写入时的缓存，以确保缓存和数据库保持相同的值。 在关系数据库中实现强大的一致性很容易，因为它维护了 ACID（原子性、一致性、隔离性、持久性）属性[9]。但是，NoSQL 数据库在默认情况下不支持 ACID 属性。ACID 属性必须以编程方式合并到同步逻辑中。在我们的设计中，我们选择关系数据库是因为 ACID 是本机支持的。 ### 元数据数据库 图 15-13 显示了数据库模式的设计。请注意，这是一个高度简化的版本，因为它只包括最重要的表和有趣的字段。 **用户**：用户表包含有关用户的基本信息，如用户名、电子邮件、个人资料照片等。 **设备**：设备表中存储设备信息。Push_id 用于发送和接收移动推送通知。请注意，一个用户可以有多个设备。 **命名空间**：名称空间是用户的根目录。 **文件**：文件表存储与最新文件相关的所有内容。 **文件版本**：它存储一个文件的版本历史记录。现有的行是只读的，以保持文件修订历史记录的完整性。 **块**：它存储与文件块相关的所有内容。任何版本的文件都可以通过以正确的顺序连接所有的块来重建。 ### 上传流 让我们讨论一下当客户端上传文件时会发生什么。为了更好地理解流程，我们绘制了如图 15-14 所示的序列图。 在图 15-14 中，并行发送了两个请求：添加文件元数据，并将文件上传到云存储中。这两个请求都来自于客户端 1。 - 添加文件元数据。 1. 客户端 1 发送一个添加新文件的元数据的请求。 2. 将新的文件元数据存储在元数据数据库中，并将文件上载状态更改为“挂起”。 3. 通知通知服务正在添加一个新文件。 4. 通知服务通知相关客户端（客户端 2）正在上传文件。 - 正在将文件上载到云存储器中。 1. 客户端 1 将文件的内容上载到阻止服务器。 2. 块服务器将文件块成块，压缩、加密块，并将它们上传到云存储。 3. 文件上传后，云存储将触发上传完成回调。该请求将被发送到 API 服务器。 4. 在元数据数据库中的文件状态已更改为“上载”。 5. 通知通知服务，文件状态已更改为“已上载”。 6. 通知服务通知相关客户端（客户端 2）文件已完全上传。 当编辑一个文件时，流是类似的，因此我们不会重复它。 ### 下载流程 当在其他地方添加或编辑文件时，将触发下载流。客户端如何知道文件是由其他客户端添加还是编辑的？客户端可以知道两种方法： - 如果客户端 A 在线，而文件被另一个客户端更改，通知服务将通知客户端 A 在某个地方进行了更改，因此它需要提取最新的数据。 - 如果客户端 A 脱机，而文件被其他客户端更改，数据将保存到缓存中。 当脱机客户端再次联机时，它会提取最新的更改。一旦客户端知道文件被更改，它首先通过 API 服务器请求元数据，然后下载块来构建文件。图 15-15 显示了详细的流程。注意，由于空间的限制，图中只显示了最重要的组件。 1. 通知服务通知客户端 2 文件在其他地方被更改。 2. 一旦客户端 2 知道新的更新可用，它就会发送一个获取元数据的请求。 3. API 服务器调用元数据数据库来获取更改的元数据。 4. 元数据将返回给 API 服务器。 5. 客户端 2 获取元数据。 6. 一旦客户端收到了元数据，它就会发送请求来阻止服务器来下载块。 7. 阻止服务器首先从云存储中下载块。 8. 云存储将块返回到块服务器。 9. 客户端 2 下载所有新的块来重建文件。 ### 通知服务 为了保持文件的一致性，在本地执行的任何文件突变都需要通知其他客户端，以减少冲突。通知服务是为满足此目的而建立的。在高级级别上，通知服务允许在事件发生时将数据传输到客户端。以下是几个选择： - 长轮询。Dropbox 使用长轮询[10]。 - WebSocket。WebSocket 提供了客户机和服务器之间的持久连接。沟通是双向的。 尽管这两个选项都很有效，但我们选择长时间轮询有以下两个原因： - 通知服务的通信不是双向的。服务器将向客户端发送有关文件更改的信息，反之则不会。 - 网络套接字适合于实时双向通讯，如聊天应用程序。对于谷歌 Drive，通知很少发送，没有数据爆发。 通过长轮询，每个客户机都建立了一个到通知服务的长轮询连接。如果检测到对文件的更改，客户端将关闭长轮询连接。关闭连接意味着客户端必须连接到元数据服务器以下载最新的更改。在收到响应或达到连接超时后，客户端会立即发送一个新的请求，以保持连接打开。 ### 节省存储空间 为了支持文件版本历史记录并确保可靠性，同一文件的多个版本存储在多个数据中心上。所有文件修订版的快速备份可以快速填满存储空间。提出了三种技术来降低存储成本： - 消除重复数据的数据块。消除帐户级别的冗余块是节省空间的一种简单方法。如果两个块具有相同的哈希值，则它们是相同的。 - 采用智能数据备份策略。可以应用两种优化策略： - 设置限制：我们可以为要存储的版本数量设置限制。如果达到了这个限制，最旧的版本将被替换为新版本。 - 只保留有价值的版本：一些文件可能会经常被编辑。例如，为一个严重修改的文档保存每个编辑过的版本可能意味着该文件在短时间内保存超过 1000 次。为了避免不必要的副本，我们可以限制保存的版本的数量。我们更重视最近的版本。实验有助于找出要保存的最佳版本数量。 - 将很少使用的数据移动到冷藏库。冷数据是指数月或数年不活跃的数据。 ### 失败处理 故障可能发生在一个大规模的系统中，我们必须采用设计策略来解决这些故障。您的面试官可能有兴趣了解您如何处理以下系统故障： - 负载平衡器失败：如果负载平衡器失败，辅助系统将变得活跃并接收流量。负载平衡器通常使用心跳相互监测，心跳是负载平衡器之间发送的周期性信号。如果负载均衡器有一段时间没有发送心跳，则认为它失败了。 - 块服务器失败：如果块服务器失败，其他服务器将接收未完成或挂起的作业。 - 云存储失败： S3桶在不同的区域被复制多次。如果文件在一个区域中不可用，则可以从不同的区域获取这些文件。 - API 服务器故障：它是一个无状态的服务。如果 API 服务器出现故障，则该流量将由负载平衡器重定向到其他 API 服务器。 - 元数据缓存失败：元数据缓存服务器被复制多次。如果一个节点下降，您仍然可以访问其他节点来获取数据。我们将引入一个新的缓存服务器来替换失败的服务器。 - 元数据数据库失败。 - 主节点宕机：如果主节点关闭，请将其中一个从节点提升为新的主节点，并启用新的从节点。 - 从节点宕机：如果从节点关闭，可以使用另一个从进行读取操作，并使用另一个数据库服务器来替换失败的数据库服务器。 - 通知服务失败：每个在线用户都与通知服务器保持一个长时间的轮询连接。因此，每个通知服务器都与许多用户相连接。根据 2012 年的 Dropbox 谈话[6]，每台机器有超过 100 万个连接被打开。如果服务器宕机，所有的长轮询连接都将丢失，因此客户端必须重新连接到另一个服务器。即使一个服务器可以保留许多打开的连接，它也不能一次重新连接所有丢失的连接。重新连接到所有丢失的客户机是一个相对缓慢的过程。 - 脱机备份队列失败：队列被复制多次。如果一个队列失败，该队列的使用者可能需要重新订阅备份队列。 ## 第 4 步 - 总结 在本章中，我们提出了一个支持谷歌 Drive 的系统设计。强一致性、低网络带宽和快速同步的结合使设计变得有趣。我们的设计包含两个流：管理文件元数据和文件同步。通知服务是系统的另一个重要组件。它使用长时间的轮询来保持客户端与文件更改的更新。 像任何系统设计面试问题一样，没有完美的解决方案。每个公司都有其独特的约束条件，你必须设计一个系统来适应这些约束条件。了解你的设计和技术选择的权衡是很重要的。如果还剩下几分钟，你可以讨论不同的设计选择。 例如，我们可以从客户端将文件上传到云存储，而不是通过块服务器。这种方法的优点是，它使文件上传速度更快，因为文件只需要传输到云存储一次。在我们的设计中，一个文件首先被转移到块服务器，然后再转移到云存储。然而，这种新的方法也有一些缺点： - 首先，相同的分块、压缩和加密逻辑必须在不同的平台（iOS、Android、Web）上实现。它容易出错，需要大量的工程工作。在我们的设计中，所有这些逻辑都是在一个集中的地方实现的：块服务器。 - 其次，由于客户端很容易被黑客攻击或操作，因此在客户端实现加密逻辑并不理想。 该系统的另一个有趣的发展过程是将在线/离线逻辑转移到一个单独的服务上。让我们称之为存在服务。通过将存在服务移出通知服务器，在线/脱线功能可以很容易地被其他服务集成。 祝贺你能走到这一步！现在拍拍自己的背。干得好！ # 第 16 章：学习仍在继续 设计良好的系统需要多年的知识积累。一个快捷方式是深入了解真实世界的系统架构。以下是一些有用的阅读材料。我们强烈建议您同时注意共享的原则和底层技术。研究每一种技术，了解它所解决的问题，是加强你的知识基础和完善设计过程的好方法。