在分布式系统中设计一个唯一 ID 生成器 在本章中，你被要求设计一个分布式系统中的唯一 ID 生成器。你的第一个想法可能是在传统的数据库中使用一个带有自动增加属性的主键。然而，auto_increment 在分布式环境中不起作用，因为单个数据库服务器不够大，以最小的延迟在多个数据库中生成唯一的 ID 是具有挑战性的。 这里有几个唯一 ID 的例子。 了解问题并确定设计范围 提出明确的问题是解决任何系统设计面试问题的第一步。下面是一个候选人与面试官互动的例子。 候选人：唯一 ID 的特点是什么？ 面试官：ID 必须是唯一的，而且是可排序的。 候选者：对于每条新记录，ID 是否递增 1？ 面试官：ID 按时间递增，但不一定只按 1 递增。在晚上创建的 ID 比同一天早上创建的 ID 要大。 候选人：ID 是否只包含数值？ 面试官：是的，这是对的。 候选热：ID 的长度要求是什么？ 面试官：ID 最长 64 位。 候选热：系统的规模是多少？ 面试官：系统应该能够每秒生成 10,000 个 ID。 以上是一些你可以问面试官的样本问题。理解需求并澄清模糊之处非常重要。对于这个面试问题，要求列举如下。 ID 必须是唯一的。 ID 只能是数值。 IDs 最长 64 位的。 IDs 按日期排序。 有能力每秒产生超过 10,000 个唯一的 ID。 提出高层次的设计并获得认同 在分布式系统中，可以使用多种选项来生成唯一的 ID。我们考虑的选项是。 多主机复制 通用唯一标识符 UUID Ticket server Twitter Snowflake 让我们来看看他们中的每一个，他们是如何工作的，以及每个选项的优点/缺点。 ...

设计键值存储 键值存储，也被称为键值数据库，是一个非关系型数据库。每一个独特的标识符都被存储为一个带有相关值的键。这种数据配对被称为 “键-值"对。 在一个键值对中，键必须是唯一的，与键相关的值可以通过键来访问。key 可以是纯文本或散列值。出于性能方面的考虑，短键的效果更好。键是什么样子的？这里有几个例子。 普通文本 key：“last_logged_in_at” 哈希后的 key：253DDEC4 键值对中的值可以是字符串、列表、对象，等等。在键值存储中，值通常被视为不透明的对象，如 Amazon dynamo [1], Memcached [2], Redis [3], 等等。 下面是键值存储中的一个数据片段。 在本章中，要求你设计一个支持以下操作的键值存储。 - put(key, value) // 插入与 "key "相关的 "value"。 - get(key) // 获取与 "key "相关的 "value"。 理解问题并确定设计范围 没有完美的设计。每一个设计都要实现关于读、写和内存使用的权衡的具体平衡。另一个必须做出的权衡是在一致性和可用性之间。在本章中，我们设计了一个包括以下特征的键值存储。 一个键值对的大小很小：小于 10KB。 有能力存储大数据。 高可用性。系统响应迅速，即使在故障时也能响应。 高可扩展性。系统可以被扩展以支持大型数据集。 自动扩展。服务器的增加/删除应该是基于流量的自动。 可调整的一致性。 低延迟。 单个服务器键值存储 开发一个部署在单一服务器上的键值存储很容易。一个直观的方法是将键值对存储在一个哈希表中，这样可以将所有的东西保存在内存中。尽管内存访问速度很快，但由于空间的限制，在内存中容纳所有内容可能是不可能的。为了在单个服务器中容纳更多的数据，可以做两个优化。 数据压缩 只在内存中存储经常使用的数据，其余的存储在磁盘上。 即使进行了这些优化，单个服务器也会很快达到其容量。为了支持大数据，需要一个分布式的键值存储。 分布式键值存储 分布式键值存储也被称为分布式哈希表，它将键值对分布在许多服务器上。在设计分布式系统时，理解 CAP（一致性、可用性、分区容错）定理很重要。 CAP 定理 CAP 定理指出，一个分布式系统不可能同时提供这三种保证中的两种以上：一致性、可用性和分区容错。让我们建立几个定义。 一致性：一致性意味着所有客户在同一时间看到相同的数据，无论他们连接到哪个节点。 可用性：可用性意味着任何请求数据的客户端都能得到响应，即使有些节点发生了故障。 分区容错：分区表示两个节点之间的通信中断。分区容错意味着尽管网络分区，系统仍能继续运行。 CAP 定理指出，必须牺牲三个属性中的一个来支持三个属性中的两个，如图 6-1 所示。 现在，键值存储是根据它们支持的两个 CAP 特性来分类的。 CP（一致性和分区容忍）系统：CP 键值存储支持一致性和分区容忍，同时牺牲了可用性。 AP（可用性和分区容忍）系统：AP 键值存储支持可用性和分区容忍，同时牺牲了一致性。 CA（一致性和可用性）系统：CA 键值存储支持一致性和可用性，同时牺牲了分区容忍度。 由于网络故障是不可避免的，一个分布式系统必须容忍网络分区。因此，CA 系统不能存在于现实世界的应用中。 ...

设计一致性哈希 为了实现横向扩展，在服务器之间有效而均匀地分配请求/数据是很重要的。一致性哈希是实现这一目标的常用技术。但首先，让我们深入了解一下这个问题。 重哈希问题 如果你有 n 个缓存服务器，平衡负载的一个常用方法是使用下面的哈希方法。 serverIndex = hash(key) % N，其中 N 是服务器池的大小。 让我们用一个例子来说明它是如何工作的。如表 5-1 所示，我们有 4 个服务器和 8 个字符串 key 及其哈希值。 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 key8 22530351 3 Table 5-1 为了获取存储 key 的服务器，我们执行模块化操作 f(key) % 4。例如，hash(key0) % 4 = 1 意味着客户端必须联系服务器 1 来获取缓存的数据。图 5-1 显示了基于表 5-1 的 key 的分布。 ...

设计一个限流器 在网络系统中，限流器被用来控制客户端或服务所发送的流量速率。在 HTTP 世界中，限流器限制了允许在指定时间内发送的客户端请求的数量。如果 API 请求数超过了限流器定义的阈值，所有多余的调用都会被阻止。这里有几个例子。 一个用户每秒钟可以写不超过 2 个帖子。 你每天最多可以从同一个 IP 地址创建 10 个账户。 你每周从同一设备上领取奖励的次数不能超过 5 次。 在本章中，要求你设计一个限流器。在开始设计之前，我们首先看一下使用 API 限流器的好处。 防止由拒绝服务（DoS）攻击引起的资源饥饿。几乎所有大型科技公司发布的 API 都执行了某种形式的限流。例如，Twitter 将每 3 小时的推文数量限制为 300 条。Google docs APIs 有如下默认限制：每个用户每 60 秒读取请求 300 次。限流器通过阻止多余的调用来防止 DoS 攻击，无论是有意的还是无意的。 降低成本。限制多余的请求意味着更少的服务器和分配更多的资源分配给高优先级的 API。限流对于使用付费的第三方 API 的公司极为重要。例如，你对以下外部 API 的调用是按次数收费的：检查信用、付款、检索健康记录等。限制调用次数是降低成本的关键。 防止服务器过载。为了减少服务器的负荷，使用限流器来过滤掉由机器人或用户的不当行为造成的过多请求。 理解问题并确定设计范围 限流可以通过不同的算法来实现，每一种算法都有其优点和缺点。面试官和候选人之间的互动有助于澄清我们要建立的限流器的类型。 候选人：我们要设计什么样的限流器？是客户端的限流器还是服务器端的 API 限流器？ 面试官：好问题。我们的重点是服务器端的 API 限流器。 候选人：限流器是根据 IP、用户 ID 还是其他属性来节制 API 请求？ 面试官：限流器应该足够灵活，以支持不同的节流规则。 应聘者：系统的规模是多少？它是为初创公司还是拥有庞大用户群的大公司建立的？ 面试官：系统必须能够处理大量的请求。 应聘者：系统能否在分布式环境中工作？ 面试官：是的。 应聘者：限流器是一个单独的服务还是应该在应用程序代码中实现？ 面试官：是的。这是一个由你决定的设计。 应聘者：我们是否需要通知那些被限制的用户？ 面试官：是的。 需求: 以下是对该系统要求的总结。 准确地限制过多的请求。 低延时。限流器不应该减慢 HTTP 响应时间。 尽可能少地使用内存。 分布式限流。限流器可以在多个服务器或进程中共享。 异常处理。当用户的请求被节制时，向用户显示明确的异常。 高容错性。如果限流器有任何问题（例如，一个缓存服务器离线），它不会影响整个系统。 提出高层次的设计并获得认同 让我们保持简单，使用基本的客户和服务器模式进行通信。 ...

系统设计面试框架 你刚刚在你梦想中的公司获得了令人羡慕的现场面试机会。招聘协调员给你发了一份当天的时间表。扫视清单，你感觉很好，直到你的目光落在这个面试环节–系统设计面试。 系统设计面试往往令人生畏。它可能像 “设计一个众所周知的产品 X？“一样模糊。问题模棱两可，看起来不合理地宽泛。你的疲惫是可以理解的。毕竟，怎么可能有人在一个小时内设计出一个流行的产品，而这个产品是花了几百个甚至几千个工程师才建成的？ 好消息是，没有人期望你能做到。现实世界的系统设计是极其复杂的。例如，谷歌搜索具有欺骗性的简单性；然而，支撑这种简单性的技术数量确实令人吃惊。如果没有人期望你在一小时内设计出一个真实世界的系统，那么系统设计面试的好处是什么？ 系统设计面试模拟了现实生活中的问题解决，两个同事合作解决一个模糊的问题，并提出一个符合他们目标的解决方案。这个问题是开放式的，没有完美的答案。与你在设计过程中付出的努力相比，最终的设计并不那么重要。这使你能够展示你的设计技能，为你的设计选择辩护，并以建设性的方式回应反馈。 让我们切换角度，考虑一下当面试官走进会议室与你见面时，她的脑子里在想什么。面试官的首要目标是准确评估你的能力。她最不希望的是，因为会议进行得不顺利，没有足够的信号，而给出一个没有结论的评价。面试官在系统设计面试中寻找的是什么？ 许多人认为，系统设计面试是关于一个人的技术设计能力。它远不止于此。一个有效的系统设计面试给人以强烈的信号，表明一个人的合作能力，在压力下工作的能力，以及建设性地解决模糊性的能力。提出好问题的能力也是一项重要的技能，许多面试官专门寻找这种技能。 一个好的面试官也会寻找错误。过度工程化是许多工程师的一个真正的病症，因为他们喜欢设计的纯粹性，而忽视了权衡。他们往往没有意识到过度工程系统的复合成本，而许多公司为这种无知付出了高昂的代价。你当然不希望在系统设计面试中表现出这种倾向。其他的错误包括狭隘的心态、固执等等。 在这一章中，我们将讲述一些有用的技巧，并介绍一个简单而有效的框架来解决系统设计面试问题。 有效的系统设计面试的 4 个流程 每个系统设计面试都是不同的。一个好的系统设计面试是开放式的，没有一个放之四海而皆准的解决方案。然而，在每个系统设计面试中都有一些步骤和共同点。 理解问题并确定设计范围 “老虎为什么咆哮？” 班级后面有一只手举了起来。 “是的，吉米？"，老师回答。 “因为他很饿”。 “非常好，吉米”。 在整个童年时期，吉米一直是班上第一个回答问题的人。每当老师提出问题时，教室里总有一个孩子喜欢在问题上一试身手，不管他是否知道答案。这就是吉米。 吉米是一个王牌学生。他以能快速知道所有答案为荣。在考试中，他通常是第一个完成问题的人。在任何学术竞赛中，他都是老师的首选。 不要像吉米那样。 在系统设计面试中，不加思索地迅速给出答案不会给你加分。在没有彻底理解需求的情况下回答问题是一个巨大的错误，因为面试不是一个小游戏比赛。没有正确的答案。 所以，不要直接跳进去给出一个解决方案。慢下来。深入思考并提出问题以澄清需求和假设。这一点极为重要。 作为一个工程师，我们喜欢解决困难的问题并跳入最终的设计；然而，这种方法很可能导致你设计出错误的系统。作为一个工程师，最重要的技能之一是提出正确的问题，做出适当的假设，并收集建立一个系统所需的所有信息。因此，不要害怕提出问题。 当你提出问题时，面试官要么直接回答你的问题，要么要求你做出假设。如果是后者，请在白板或纸上写下你的假设。你以后可能会用到它们。 要问什么样的问题？提出问题以了解确切的要求。这里有一个问题清单，可以帮助你开始工作。 我们要建立什么具体的功能？ 该产品有多少用户？ 公司预计扩大规模的速度如何？3 个月、6 个月和 1 年后的预期规模是什么？ 该公司的技术栈是什么？你可以利用哪些现有的服务来简化设计？ 例子: 如果你被要求设计一个新闻源系统，你要问一些问题，帮助你澄清需求。你和面试官之间的对话可能是这样的。 候选人：这是一个移动应用程序吗？还是一个网络应用？或者两者都是？ 面试官。都是。 应聘者：产品最重要的功能是什么？面试官。能够发帖并看到朋友的新闻提要。 应聘者：新闻源是按时间倒序还是按特定顺序排序的？特定顺序意味着每个帖子都有不同的权重。例如，来自你的亲密朋友的帖子比来自一个小组的帖子更重要。 采访者。为了简单起见，让我们假设 feed 是按逆时针顺序排序的。 候选人：一个用户可以有多少个朋友？面试官。5000 考生：流量是多少？面试官。1000 万日活跃用户（DAU）。 应聘者：饲料可以包含图片、视频，还是只有文字？ 面试官：可以。它可以包含媒体文件，包括图片和视频。 以上是你可以问面试官的一些样本问题。理解要求并澄清含糊之处非常重要。 提出高层次的设计并获得认同 在这个步骤中，我们的目标是制定一个高层次的设计，并与面试官就设计达成一致。在这个过程中，与面试官合作是个好主意。 想出一个初步的设计蓝图。征求反馈意见。把你的面试官当作队友，一起工作。许多优秀的面试官喜欢交谈和参与。 在白板或纸上画出带有关键部件的方框图。这可能包括客户端（移动/网络）、API、网络服务器、数据存储、缓存、CDN、消息队列，等等。 做事后计算，评估你的蓝图是否符合规模限制。努力思考。在深入研究之前，如果有必要进行逆向计算，请与你的面试官沟通。 如果可能的话，通过一些具体的使用案例。这将帮助你确定高级设计的框架。也有可能这些用例会帮助你发现你还没有考虑过的边缘案例。 我们应该在这里包括 API 端点和数据库模式吗？这取决于问题的情况。对于像 “设计谷歌搜索引擎 “这样的大型设计问题，这有点太低级了。对于像为多人扑克游戏设计后端这样的问题，这是一个公平的游戏。与你的面试官沟通。 例子: 让我们用 “设计一个新闻源系统 “来演示如何进行高层设计。这里不要求你了解系统的实际工作情况。所有的细节将在第 11 章解释。 在高层次上，设计分为两个流程：Feed 发布和新闻源构建。 帖子发布：当用户发布帖子时，相应的数据被写入缓存/数据库，该帖子将被填充到朋友的新闻提要中。 新闻源构建：新闻源是通过将朋友的帖子按照逆时针顺序聚合起来而构建的。 图 3-1 和图 3-2 分别展示了新闻发布和新闻源构建流程的高级设计。 ...

粗略评估 在系统设计面试中，有时你会被要求用粗略评估系统容量或性能要求。根据 Google 高级研究员 Jeff Dean 的说法，“粗略计算是你使用思想实验和常见的性能数字的组合来创建的估计，以很好地感觉到哪些设计可以满足你的要求” 你需要对可扩展性的基础知识有一个很好的感觉，以便有效地进行粗略计算。你需要好地理解以下概念：二的幂，每个程序员都应该知道的延迟数字，以及可用性数字。 2 的幂 尽管在处理分布式系统时，数据量可能变得巨大，但计算都可以归结为基础知识。为了获得正确的计算结果，关键是要知道使用 2 的幂的数据量单位。一个字节是一个 8 位的序列。一个 ASCII 字符使用一个字节的内存（8 比特）。下面是一个解释数据量单位的表格 Power Approximate value Full name Short name 10 1 Thousand 1 Kilobyte 1 KB 20 1 Million 1 Megabyte 1 MB 30 1 Billion 1 Gigabyte 1 GB 40 1 Trillion 1 Terabyte 1 TB 50 1 Quadrillion 1 Petabyte 1 PB 每个程序都应该知道的延迟数字 来自谷歌的 Dr.Dean 展示了 2010 年典型计算机操作的时间长度。随着计算机变得更快、更强大，有些数字已经过时了。然而，这些数字应该仍然能够让我们了解不同计算机操作的快慢。 Operation name Time L1 cache reference 0.5 ns Branch mispredict 5 ns L2 cache reference 7 ns Mutex lock/unlock 100 ns Main memory reference 100 ns Compress 1K bytes with Zippy 10,000 ns = 10 us Send 2K bytes over 1 Gbps network 20,000 ns = 20 us Read 1 MB sequentially from memory 250,000 ns = 250 us Round trip within the same datacenter 500,000 ns = 500 us Disk seek 10,000,000 ns = 10 ms Read 1 MB sequentially from the network 10,000,000 ns = 10 ms Read 1 MB sequentially from disk 30,000,000 ns = 30 ms Send packet CA (California) -> Netherlands-> CA 150,000,000 ns = 150 ms 一位谷歌软件工程师建立了一个工具，将 Dr.Dean 的数字可视化。该工具还将时间因素考虑在内。下图显示了截至 2020 年的可视化延迟数字 ...

从零到一百万 设计一个支持数百万用户的系统是一个挑战，这是一个需要不断完善和无止境改进的历程。在本章中，我们将构建一个支持单个用户的系统，并逐步将其扩展到服务数百万用户。读完本章，你将掌握一手的技巧，帮助你破解系统设计的面试题。 单服务器设置 千里之行始于足下，构建一个复杂的系统也不例外。先从简单的东西开始，所有的东西都运行在一台服务器上。图 1-1 是单服务器设置的说明，所有的东西都在一台服务器上运行：Web 应用、数据库、缓存等。 为了理解这种设置，研究一下请求流程和流量来源是很有帮助的。我们先来看看请求流程（图 1-2）。 用户通过域名访问网站，如 api.mysite.com。通常，域名系统（DNS）是由第三方提供的付费服务，而不是由我们的服务器托管。 互联网协议（IP）地址返回给浏览器或移动应用。在本例中，返回的 IP 地址为 15.125.23.214。 获得 IP 地址后，超文本传输协议（HTTP）[1]请求直接发送到您的网络服务器。 Web 服务器返回 HTML 页面或 JSON 响应进行渲染。 接下来，我们来看看流量来源。你的 Web 服务器的流量来自两个方面：Web 应用和移动应用。 Web 应用：它使用服务器端语言（Java、Python 等）组合来处理业务逻辑、存储等，使用客户端语言（HTML 和 JavaScript）来进行展示。 移动应用。HTTP 协议是移动应用与 Web 服务器之间的通信协议。JavaScript 对象符号（JSON）由于其简单性，是常用的 API 响应格式来传输数据。JSON 格式的 API 响应示例如下所示。 { "firstName": "John", "lastName": "Smith", "address": { "streetAddress": "21 2nd street", "city": "New York", "state": "NY", "postal Code": 10021 }, "phoneNumbers": ["212 555-1234", "646 555-4567"] } GET /users/12 – Retrieve user object for id = 12 ...