系统设计面试的行家指南（上）（3）https://developer.aliyun.com/article/1481933
总结
本章涵盖了许多概念和技术。为了提醒您，下表总结了分布式键值存储所使用的功能和相应的技术。
参考资料
[1] Amazon DynamoDB: https://aws.amazon.com/dynamodb/ [2] memcached: https://memcached.org/ [3] Redis: https://redis.io/ [4] Dynamo: Amazon’s Highly Available Key-value Store: https://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf [5] Cassandra: https://cassandra.apache.org/ [6] Bigtable: A Distributed Storage System for Structured Data: https://static.googleusercontent.com/media/research.google.com/en//archive/bigtable-osdi06.pdf [7] Merkle tree: https://en.wikipedia.org/wiki/Merkle_tree [8] Cassandra architecture: https://cassandra.apache.org/doc/latest/architecture/ [9] SStable: https://www.igvita.com/2012/02/06/sstable-and-log-structured-storage-leveldb/ [10] Bloom filter https://en.wikipedia.org/wiki/B
七、设计分布式系统中的唯一 ID 生成器
在这一章中，你被要求在分布式系统中设计一个唯一的 ID 生成器。您首先想到的可能是在传统数据库中使用带有 auto_increment 属性的主键。然而， auto_increment 在分布式环境中不起作用，因为单个数据库服务器不够大，并且在最小延迟的情况下跨多个数据库生成唯一的 id 具有挑战性。
这里有几个唯一 id 的例子：
步骤 1 -了解问题并确定设计范围
提出澄清性问题是解决任何系统设计面试问题的第一步。下面是一个应聘者与面试官互动的例子：
候选人 :唯一 id 有什么特点？
采访者 :身份证必须是唯一的，可排序的。
候选人 :每增加一条新记录，ID 增加 1 吗？
面试官：ID 随时间递增，但不一定只递增 1。同一天晚上创建的 id 比早上创建的 id 大。
候选人：id 只包含数值吗？
面试官 :是的，没错。
考生 :身份证长度有什么要求？
采访者 :身份证应该是 64 位的。
候选人 :系统的规模是多少？
面试官 :系统每秒应该能生成 10000 个 id。
以上是你可以问面试官的一些问题。理解需求和澄清歧义是很重要的。对于这个面试问题，要求如下：
id 必须唯一。
id 仅为数值。
IDs 适合 64 位。
id 按日期排序。
每秒生成超过 10，000 个唯一 id 的能力。
第二步——提出高水平的设计并获得认同
在分布式系统中，可以使用多个选项来生成唯一的 id。我们考虑的选项有：
多主复制
UUID
票务服务器
推特雪花逼近
让我们来看看每一种方法，它们是如何工作的，以及每种方法的优缺点。
多主机复制
如图 7-2 所示，第一种方法是多主机复制。
这种方式使用了数据库的 auto_increment 特性。我们没有将下一个 ID 增加 1，而是增加了k， ，其中 k 是正在使用的数据库服务器的数量。如图 7-2 所示，要生成的下一个 ID 等于同一服务器中的前一个 ID 加 2。这解决了一些可伸缩性问题，因为 IDs 可以随着数据库服务器的数量而伸缩。然而，这种策略有一些主要的缺点：
难以扩展多个数据中心
跨多台服务器的 IDs 不随时间上升。
添加或删除服务器时，它无法很好地扩展。
UUID
UUID 是获得唯一 ID 的另一种简单方法。UUID 是一个 128 位的数字，用于识别计算机系统中的信息。UUID 获得共谋的概率非常低。引用维基百科，“在大约 100 年内每秒生成 10 亿个 UUIDs 后，创建一个单一副本的概率会达到 50%”[1]。
下面举个 UUID 的例子：09 c93e 62-50 B4-468d-bf8a-c 07e 1040 bfb 2。可以独立生成，不需要服务器之间的协调。图 7-3 展示了 UUIDs 的设计。
在这个设计中，每个 web 服务器都包含一个 ID 生成器，一个 web 服务器独立负责生成 ID。
优点：
生成 UUID 很简单。服务器之间不需要协调，所以不会有任何同步问题。
这个系统很容易扩展，因为每个 web 服务器负责生成它们所使用的 id。ID 生成器可以很容易地与 web 服务器一起伸缩。
缺点：
id 是 128 位长，但我们的要求是 64 位。
id 不随时间而涨。
id 可以是非数字的。
票务服务器
票证服务器是另一种生成唯一 id 的有趣方式。Flicker 开发了票证服务器来生成分布式主键[2]。值得一提的是这个系统是如何工作的。
这个想法是在单个数据库服务器(票证服务器)中使用集中式的 自动增量 功能。要了解这方面的更多信息，请参考 flicker 的工程博客文章[2]。
优点：
数字标识。
易于实现，适用于中小型应用。
缺点：
单点故障。单一票证服务器意味着如果票证服务器宕机，所有依赖它的系统都将面临问题。为了避免单点故障，我们可以设置多个票证服务器。然而，这将引入新的挑战，例如数据同步。
推特雪花接近
上面提到的方法给了我们一些关于不同 ID 生成系统如何工作的想法。然而，它们都不符合我们的具体要求；因此，我们需要另一种方法。Twitter 独特的 ID 生成系统叫做“雪花”[3]很有启发性，可以满足我们的要求。
分而治之是我们的朋友。我们不是直接生成 ID，而是将 ID 分成不同的部分。图 7-5 显示了一个 64 位 ID 的布局。
每一部分解释如下。
标志位：1 位。它将永远是 0。这是为将来使用而保留的。它可以潜在地用于区分有符号和无符号数。
时间戳：41 位。自纪元或自定义纪元以来的毫秒数。我们使用 Twitter 雪花默认纪元 1288834974657，相当于 2010 年 11 月 4 日 01:42:54 UTC。
数据中心 ID: 5 位，这给了我们 2 ^ 5 = 32 数据中心。
机器 ID: 5 位，即每个数据中心有 2 ^ 5 = 32台 机器。
序号：12 位 。对于在该机器/进程上生成的每个 ID，序列号增加 1。该数字每毫秒重置为 0。
步骤 3 -设计深度潜水
在概要设计中，我们讨论了在分布式系统中设计唯一 ID 生成器的各种方案。我们决定采用一种基于 Twitter 雪花 ID 生成器的方法。让我们深入研究一下这个设计。为了提醒我们，下面重新列出了设计图。
数据中心 id 和机器 id 在启动时选择，通常在系统启动运行后固定。数据中心 ID 和机器 ID 的任何更改都需要仔细检查，因为这些值的意外更改会导致 ID 冲突。ID 生成器运行时会生成时间戳和序列号。
时间戳
最重要的 41 位组成时间戳部分。随着时间戳随着时间的增长，id 可以按时间排序。图 7-7 显示了一个二进制表示如何转换成 UTC 的例子。您也可以使用类似的方法将 UTC 转换回二进制表示。
可以用 41 位表示的最大时间戳是
2 ^ 41 - 1 = 2199023255551 毫秒(ms)，由此我们得到：~ 69 年 = 2199023255551 毫秒 / 1000 秒 / 365 天 / 24 小时 / 3600 秒。这意味着 ID 生成器将工作 69 年，拥有一个接近今天日期的自定义纪元时间会延迟溢出时间。69 年后，我们将需要一个新的纪元时间或采用其他技术来迁移 IDs。
序号
序列号是 12 位，这给我们 2 ^ 12 = 4096 个组合。除非在同一台服务器上一毫秒内生成了多个 ID，否则该字段为 0。理论上，一台机器每毫秒最多可以支持 4096 个新 id。
步骤 4 -总结
在本章中，我们讨论了设计唯一 ID 生成器的不同方法：多主机复制、UUID、票据服务器和 Twitter 雪花型唯一 ID 生成器。我们选择了雪花，因为它支持我们所有的用例，并且可以在分布式环境中扩展。
如果在采访结束时有额外的时间，这里有一些额外的谈话要点：
时钟同步。在我们的设计中，我们假设 ID 生成服务器具有相同的时钟。当服务器在多个内核上运行时，这种假设可能不成立。在多机场景中也存在同样的挑战。时钟同步的解决方案超出了本书的范围；然而，了解问题的存在是很重要的。网络时间协议是解决这个问题的最流行的方法。感兴趣的读者可以参考参考资料[4]。
分段长度调谐。例如，更少的序列号但更多的时间戳位对于低并发性和长期应用程序是有效的。
高可用性。因为 ID 生成器是一个任务关键型系统，所以它必须高度可用。
祝贺你走到这一步！现在给自己一个鼓励。干得好！
参考资料
[1] Universally unique identifier: https://en.wikipedia.org/wiki/Universally_unique_identifier [2] Ticket Servers: Distributed Unique Primary Keys on the Cheap: https://code.flickr.net/2010/02/08/ticket-servers-distributed-unique-primary-keys-on-the-cheap/ [3] Announcing Snowflake: https://blog.twitter.com/engineering/en_us/a/2010/announcing-snowflake.html [4] Network time protocol: https://en.wikipedia.org/wiki/Ne
八、设计 URL 缩短器
在这一章中，我们将解决一个有趣而经典的系统设计面试问题：设计一个像 tinyurl 这样的 URL 缩短服务。
第一步——了解问题并确定设计范围
系统设计面试问题有意留有开放性。要设计一个精心制作的系统，提出澄清性问题至关重要。
候选人 :你能举例说明网址缩写是如何工作的吗？
面试官 :假设 URL https://www.systeminterview.com/q=chatsystem&c=loggedin&v=v3&l=long 是原 URL。您的服务创建了一个较短的别名：https://tinyurl.com/y7keocwj。如果您单击别名，它会将您重定向到原始 URL。
候选人 :车流量是多少？
面试官 :每天产生 1 亿个网址。
候选人 :网址缩短后有多长？
面试官 :尽量简短。
候选人 :网址缩写中允许使用哪些字符？
面试官 :网址缩写可以是数字(0-9)和字符(a-z，A-Z)的组合。
候选人 :可以删除或更新缩短的网址吗？
采访者 :为了简单起见，我们假设被缩短的网址不能被删除或更新。
以下是基本用例：
1。URL 缩短：给定一个长 URL => 返回一个短得多的 URL
2。URL 重定向：给定一个较短的 URL => 重定向到原来的 URL
3。高可用性、可扩展性和容错考虑
信封估算的背面
写操作：每天产生 1 亿个 URL。
每秒写操作数：1 亿 / 24 / 3600 = 1160
读操作：假设读操作与写操作之比为 10:1，每秒读操作数：1160 * 10 = 11600
假设网址缩写服务将运行 10 年，这意味着我们必须支持1 亿 * 365 = 365 亿条记录。
假设平均 URL 长度为 100。
超过 10 年的存储需求：3650 亿* 100 字节* 10 年= 365 TB
对你来说，和你的面试官一起回顾假设和计算是很重要的，这样你们两个就能达成共识。
第二步——提出高层次设计并获得认同
在本节中，我们将讨论 API 端点、URL 重定向和 URL 缩短流程。
API 终点
API 端点促进了客户端和服务器之间的通信。我们将设计 REST 风格的 API。如果对 restful API 不熟悉，可以参考外部资料，比如参考资料[1]中的那个。一个 URL shortener primary 需要两个 API 端点。
1。URL 缩短。为了创建一个新的短 URL，客户端发送一个 POST 请求，其中包含一个参数：原始的长 URL。API 看起来是这样的：
POST api/v1/data/shorten
请求参数：{longURL: longURLString}
返回快捷链接
2。URL 重定向。为了将短 URL 重定向到相应的长 URL，客户端发送 GET 请求。API 看起来是这样的：
GET api/v1/shortURL
返回 HTTP 重定向的 longURL
网址重定向
图 8-1 显示了当你在浏览器上输入一个短 url 时会发生什么。一旦服务器接收到短 url 请求，它会使用 301 重定向将短 url 更改为长 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)
一旦获得长 URL，就执行 URL 重定向。
网址缩短
让我们假设短 URL 是这样的：www.tinyurl.com/{hashvalue}。为了支持 URL 缩短用例，我们必须找到一个哈希函数 nfx 将一个长 URL 映射到哈希值，如图 8-3 所示。
哈希函数必须满足以下要求：
每个 长 URL 都必须哈希为一个 哈希值 。
每个 的哈希值 都可以映射回 长 URL 。
深入讨论哈希函数的详细设计。
步骤 3 -设计深度潜水
到目前为止，我们已经讨论了 URL 缩短和 URL 重定向的高级设计 - 。在本节中，我们将深入探讨以下内容：数据模型、哈希函数、URL 缩短和 URL 重定向。
数据模型
在高层设计中，一切都存储在哈希表中。这是一个很好的起点；然而，这种方法对于真实世界的系统是不可行的，因为存储器资源是有限的并且昂贵的。更好的选择是在关系数据库中存储 < 短 URL，长 URL > 映射。图 8-4 显示了一个简单的数据库表设计。表格的简化版包含 3 列： id ， 短 URL，长 URL 。
哈希函数
哈希函数用于将一个长 URL 哈希成一个短 URL，也称为哈希值。
哈希值长度
的哈希值 由[0-9, a-z, A-Z]的字符组成，包含 10 + 26 + 26 = 62 个可能的字符。求 的长度有一个值 ，求最小的 n 使得62^n ≥ 3650亿 。该系统必须支持高达 3650 亿网址的基础上回来的信封估计。表 8-1 显示了哈希值的长度及其对应的可以支持的最大 URL 数。
当 n = 7，62 ^ n = ~3.5 万亿 时，3.5 万亿容纳 3650 亿个 URL 绰绰有余，所以哈希值的长度为 7。
我们将探讨两种类型的 URL 缩写哈希函数。第一个是“哈希+冲突解决”，第二个是“base 62 转换”。让我们一个一个来看。
哈希+冲突解决
为了缩短一个长 URL，我们应该实现一个哈希函数，将一个长 URL 哈希成一个 7 个字符的字符串。一个简单的解决方案是使用众所周知的哈希函数，如 CRC32、MD5 或 SHA-1。下表比较了对该 URL 应用不同哈希函数后的哈希结果：https://en.wikipedia.org/wiki/Systems_design.
如表 8-2 所示，即使是最短的哈希值(来自 CRC32)也太长(超过 7 个字符)。怎么才能让它变短？
第一种方法是收集哈希值的前 7 个字符；但是，这种方法会导致哈希冲突。为了解决哈希冲突，我们可以递归地添加一个新的预定义字符串，直到不再发现冲突。这个过程如图 8-5 所示。
这种方法可以消除碰撞；然而，查询数据库来检查是否每个请求都有一个 短 URL 是很昂贵的。一种叫做 bloom filters [2]的技术可以提高性能。布隆过滤器是一种节省空间的概率技术，用于测试元素是否是集合的成员。更多详情请参考参考资料[2]。
基数 62 转换
基本转换是 URL 缩写常用的另一种方法。基本转换有助于在不同的数字表示系统之间转换相同的数字。由于 的哈希值 有 62 个可能的字符，所以使用 62 进制转换。让我们用一个例子来说明转换是如何进行的：将 1115710 转换为基数为 62 的表示(1115710 在基数为 10 的系统中表示 11157)。
顾名思义，base 62 是使用 62 个字符进行编码的一种方式。映射的是： 0-0、…、9-9、10-a、11-b、…，35-z，36-A，…，61-Z，其中a代表 10，Z代表 61，以此类推。
1115710 = 2 X 622+55 X 621+59 X 620 = [2, 55, 59] -> [2, T, X]以 62 为基数表示。图 8-6 显示了对话过程。
这样，短网址就是 https://tinyurl.com/2TX
两种方法的比较
表 8-3 显示了这两种方法的区别。
网址缩短深度剖析
作为系统的核心部分之一，我们希望 URL 缩短流程在逻辑上简单且实用。我们的设计采用 62 进制转换。我们构建了下图(图 8-7)来演示这个流程。
1。长 URL 是输入。
2。系统检查长 URL 是否在数据库中。
3。如果是，则意味着 长 URL 之前被转换为 短 URL。在这种情况下，从数据库获取 短 URL 并将其返回给客户端。
4。如果不是，则 长 URL 是新的。唯一 ID 生成器生成新的唯一 ID(主键)。
5。使用 base 62 转换将 ID 转换为 短 URL。
6。用 ID、短 URL 和 长 URL 创建新的数据库行。
为了让流程更容易理解，让我们看一个具体的例子。
假设输入的 长 URL 是：https://en.wikipedia.org/wiki/Systems_design
唯一 ID 生成器返回 ID: 2009215674938。
使用 62 进制转换将 ID 转换为 短 URL。ID (2009215674938)转换为zn9edcu。
将 ID、短 URL 和 长 URL 保存到数据库，如表 8-4 所示。
值得一提的是分布式唯一 ID 生成器。它的主要功能是生成全局唯一的 id，用于创建 短 URLs。在高度分布式的环境中，实现唯一的 ID 生成器是一项挑战。幸运的是，我们已经在“第七章：在分布式系统中设计唯一的 ID 生成器”中讨论了一些解决方案。你可以回头参考一下，以唤起你的记忆。
URL 重定向深潜
图 8-8 显示了 URL 重定向的详细设计。由于读取比写入多， < 短 URL，长 URL > 映射存储在缓存中以提高性能。
URL 重定向的流程总结如下：
1。用户点击一个短的网址链接：https://tinyurl.com/zn9edcu
2。负载平衡器将请求转发给 web 服务器。
3。如果 短 URL 已经在缓存中，则直接返回 长 URL。
4。如果 短 URL 不在缓存中，则从数据库中获取 长 URL。如果它不在数据库中，则可能是用户输入了无效的 短 URL。
5。将 长 URL 返回给用户。
步骤 4 -总结
在本章中，我们讨论了 API 设计、数据模型、哈希函数、URL 缩短和 URL 重定向。
如果在面试结束时有额外的时间，这里有一些额外的谈话要点。
限速器：我们可能面临的一个潜在安全问题是，恶意用户会发送大量 URL 缩短请求。速率限制器帮助过滤出基于 IP 地址或其他过滤规则的请求。如果你想回忆一下速率限制，请参考“第四章：设计一个速率限制器”。
web 服务器扩展：由于 web 层是无状态的，所以通过添加或删除 Web 服务器来扩展 Web 层是很容易的。
数据库伸缩：数据库复制和分片是常见的技术。
分析：数据对商业成功越来越重要。将分析解决方案集成到 URL shortener 中有助于回答一些重要问题，比如有多少人点击了一个链接？他们什么时候点击链接？等等。
可用性、一致性和可靠性。这些概念是任何大型系统成功的核心。我们在第一章中详细讨论了它们，请刷新您对这些主题的记忆。
祝贺你走到这一步！现在给自己一个鼓励。干得好！
参考资料
[1] A RESTful Tutorial: https://www.restapitutorial.com/index.html [2] Bloom filter: https://en.wikipedia.org/wiki/Blo
