> For the complete documentation index, see [llms.txt](https://learning-guide.gitbook.io/system-design-interview/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://learning-guide.gitbook.io/system-design-interview/xi-tong-she-ji-mian-shi-nei-mu-zhi-nan-di-yi-juan/chapter-08-design-a-url-shortener.md).

# 第08章：短网址设计

在这一章中，我们将解决一个有趣而经典的系统设计面试问题：设计一个像 tinyurl 一样的 URL 缩短服务。

### 第1步：了解问题并确定设计范围

系统设计的面试问题是故意留有余地的。为了设计一个精心设计的系统，关键是要问清楚问题。

候选人：你能举个例子说明 URL 缩短器的工作原理吗？

面试官：假设 URL `https://www.systeminterview.com/q=chatsystem&c=loggedin&v=v3&l=long` 是原始 URL。你的服务创建了一个长度较短的别名：`https://tinyurl.com/y7keocwj`。如果你单击较短的别名 URL，它会将你重定向到原始 URL。

候选人：流量是多少？

面试官：每天产生1亿个[URL](https://www.notion.so/f56f4bc43ae9455780d5c541cb762a83)。

候选人：缩短后的 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 = 11,600
* 假设 URL 缩短服务将运行 10 年，这意味着我们必须支持 1 亿 \* 365 \* 10 = 3650 亿条记录。
* 假设平均 URL 长度为 100。
* 10 年的存储需求：3650 亿 \* 100 字节 \* 10 年 = 365 TB

重要的是，你要与面试官一起探讨假设和计算，以便你们两个人都在同一起跑线上。

### 第2步：提出高层次的设计方案并获得认同

在本节中，我们将讨论 API 端点、URL 重定向和 URL 缩短。

#### API 端点

API 端点促进了客户和服务器之间的通信。我们将设计 REST 风格的 API。如果你不熟悉 restful API，你可以查阅外部资料，比如参考资料中的资料\[1]。一个 URL 缩短器主要需要两个 API 端点。

1. 网址缩短。 要创建一个新的短 URL，客户端发送一个 POST 请求，其中包含一个参数：原始长 URL。 API 如下所示：

   **POST api/v1/data/shorten**

   * 请求参数：{longUrl: longURLString}。
   * 返回 shortURL
2. URL 重定向。为了将一个短的 URL 重定向到相应的长的 URL，一个客户端发送一个 GET 请求。该 API 看起来像这样：

   **GET api/v1/shortUrl**

   * 返回用于 HTTP 重定向的 longURL

#### URL 重定向

图8-1显示了当你在浏览器上输入一个 tinyurl 时会发生什么。一旦服务器收到 tinyurl 请求，它就会用301重定向将短网址改为长网址。

![](/files/ePE4hRt8LoyQh76G9oP1)

客户端和服务器之间的详细通信情况如图8-2所示。

![](/files/VvUWUPYCS3aDKDKwmDGS)

值得在这里讨论的一件事是 301 重定向与 302 重定向。

* **301重定向**。301重定向表明，请求的 URL 被 "永久 "地移到了长 URL 上。由于是永久重定向，浏览器会缓存响应，对同一 URL 的后续请求将不会被发送到 URL 缩短服务上。相反，请求将直接被重定向到长网址服务器。
* **302重定向**。302重定向意味着 URL 被 "暂时 "移到长 URL 上，这意味着对同一 URL 的后续请求将首先被发送到 URL 缩短服务上。然后，它们会被重定向到长网址服务器。

每种重定向方法都有其优点和缺点。如果优先考虑**减少服务器负载**，使用301重定向是有意义的，因为只有同一 URL 的第一个请求被发送到 URL 缩短服务器。然而，如果分析是重要的，302重定向是一个更好的选择，因为它可以更容易地**跟踪点击率和点击的来源。**

实现 URL 重定向的最直观的方法是**使用哈希表**。假设哈希表存储\<shortURL, longURL>对，URL 重定向可以通过以下方式实现。

* 获取 longURL: `longURL = hashTable.get(shortURL)`
* 一旦你得到 longURL，就执行 URL 重定向。

#### 缩短网址

让我们假设短的 URL 看起来像这样：`www.tinyurl.com/{hashValue}`。为了支持缩短 URL 的用例，我们必须找到一个哈希函数 fx，将长 URL 映射到 hashValue，如图8-3所示。

![](/files/SaY3Dko9bn3EgnvM8Dc2)

哈希函数必须满足以下要求。

* 每个 longURL 必须被散列成一个 hashValue。
* 每个 hashValue 都可以被映射回 longURL。

哈希函数的详细设计将深入讨论。

### 第3步：深入设计

到目前为止，我们已经讨论了 URL 缩短和 URL 重定向的高层设计。在本节中，我们将深入探讨以下内容：数据模型、哈希函数、URL 缩短和 URL 重定向。

#### 数据模型

在高层设计中，所有的东西都存储在一个哈希表中。这是一个很好的起点；然而，这种方法在现实世界的系统中是不可行的，因为内存资源是有限的和昂贵的。一个更好的选择是将\<shortURL, longURL>映射存储在一个关系数据库中。图8-4显示了一个简单的数据库表设计。简化版的表包含3列：id、shortURL、longURL。

![](/files/EqRUt6aevi2cOeUnqRGw)

#### 哈希函数

哈希函数用于将一个长的 URL 哈希成一个短的 URL，也称为 hashValue。

**哈希值的长度**

hashValue 由\[0-9, a-z, A-Z]中的字符组成，包含 $$10+26+26=62$$ 个可能的字符。要计算 hashValue 的长度，请找出最小的 n，使 $$62^n \ge 365亿$$。根据估计，系统必须支持多达 3650 亿个 URL。 表 8-1 显示了 hashValue 的长度和它可以支持的相应的最大 URL 数。

![](/files/eh9mrXRQQx7Rdj6xny3c)

当 $$n = 7$$ 时， $$62 ^ n \approx 3.5万亿$$，3.5 万亿足以容纳 3650亿个 URL，所以 hashValue 的长度为 7。

我们将探讨两种类型的 URL 缩短器的哈希函数。第一种是 "哈希+碰撞解决"，第二种是 "base 62 转换"。让我们逐一来看看它们。

**哈希+碰撞解决**

为了缩短长的 URL，我们应该实现一个散列函数，将长的 URL 散列成一个7个字符的字符串。一个直接的解决方案是使用知名的哈希函数，如 CRC32、MD5 或 SHA-1。下表比较了在这个 URL（<https://en.wikipedia.org/wiki/Systems_design>）上应用不同哈希函数后的哈希结果：

![](/files/zcIdbs9iuNCMmnQEqSuY)

如表8-2所示，即使是最短的哈希值（来自 CRC32）也太长了（超过7个字符）。我们怎样才能使它更短呢？

第一种方法是收集哈希值的前7个字符；然而，这种方法会导致哈希碰撞。为了解决哈希碰撞，我们可以递归地追加一个新的预定义字符串，直到不再发现碰撞。这一过程在图8-5中得到了解释。

![](/files/ASgXJMvngZXXANvRewlQ)

这种方法可以消除碰撞；但是，查询数据库以检查每个请求是否存在短网址的成本很高。一种叫做**Bloom 过滤器**的技术\[2]可以提高性能。布隆过滤器是一种空间效率高的概率技术，用来测试一个元素是否是一个集合的成员。更多细节请参考参考资料\[2]。

**base 62 转换**

Base 转换是 URL 缩短器常用的另一种方法。 Base 转换有助于在不同的数字表示系统之间转换成相同的数字。 使用 Base 62 转换，因为 hashValue 有 62 个可能的字符。 让我们用一个例子来解释转换的工作原理：将 $$11157\_{10}$$ 转换为 base 62 表示（ $$11157\_{10}$$ 在 base 10 系统中表示 11157）。

* 从名字上看，base 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 = \left \[2, 55, 59 \right ] \rightarrow \left \[2, T, X \right]$$ 以 base 62 表示。

  转换过程如图8-6所示。

  ![](/files/1k20uIgFIWhIcYBtE9nx)
* 因此，短网址是：<https://tinyurl.com/2TX>

**两种方法的比较**

下表显示了两种方法的差异。

| 哈希+碰撞解决                     | base 62 转换                                    |
| --------------------------- | --------------------------------------------- |
| 固定短 URL 长度                  | 短 URL 长度不固定，它随着 id 变化                         |
| 不需要唯一 ID 生成器                | 该选项依赖于唯一 ID 生成器                               |
| 可能出现冲突，必须解决                 | 碰撞是不可能的，因为 ID 是唯一的                            |
| 不可能计算出下一个可用的短网址，因为它不依赖于 ID。 | 如果新条目的 ID 递增 1，则很容易找出下一个可用的短 URL。 这可能是一个安全问题。 |

#### URL 缩短的深入研究

作为系统的核心部分之一，我们希望 URL 缩短的流程在逻辑上是简单和实用的。在我们的设计中使用了62进制转换。我们建立了以下图表（图8-7）来演示这个流程。

![](/files/W7hFnac14Galk43FUhZa)

1. longURL 是输入的
2. 系统检查 longURL 是否存在于数据库中
3. 如果是的话，这意味着 longURL 之前被转换为 shortURL。在这种情况下，从数据库中获取 shortURL 并将其返回给客户端。
4. 如果不是，longURL 是新的。一个新的唯一 ID（主键）由唯一 ID 生成器生成。
5. 使用 base 62转换将 ID 转换为 shortURL。
6. 用 ID、shortURL 和 longURL 创建一个新的数据库记录。

为了使流程更容易理解，让我们看一个具体的例子。

* 假设输入的 longURL 是：<https://en.wikipedia.org/wiki/Systems\\_design>
* 唯一 ID 生成器返回 ID：2009215674938
* 使用62进制转换将 ID 转换为 shortURL。ID（2009215674938）被转换为 "zn9edcu"。
* 将 ID、shortURL 和 longURL 保存到数据库，如表8-4所示。

  ![](/files/qqz1vjfdakvVOAZ3d6vh)

值得一提的是分布式唯一 ID 生成器。 它的主要功能是生成全局唯一 ID，用于创建 shortURL。 在高度分布式的环境中，实现唯一 ID 生成器具有挑战性。 幸运的是，我们已经在“第 7 章：在分布式系统中设计唯一 ID 生成器”中讨论了一些解决方案。 你可以回过头来回顾它来刷新你的记忆。

#### URL 重定向的深入研究

图 8-8 显示了 URL 重定向的详细设计。 由于读取多于写入，`<shortURL, longURL>` 映射存储在缓存中以提高性能。

![](/files/H6lYmTybj06PrXZkJJEx)

URL 重定向的流程总结如下：

* 一个用户点击了一个短的 URL 链接：`https://tinyurl.com/zn9edcu`
* 负载均衡器将请求转发给网络服务器
* 如果 shortURL 已经在缓存中，直接返回 longURL。
* 如果短 URL 不在缓存中，从数据库中获取长 URL。如果它不在数据库中，很可能是用户输入了一个无效的短网址。
* longURL 被返回给用户。

### 第4步：总结

在本章中，我们讨论了 API 设计、数据模型、哈希函数、URL 缩短和 URL 重定向。

如果在面试结束时有多余的时间，这里有几个额外的谈话要点：

* 速率限制器：我们可能面临的一个潜在安全问题是恶意用户发送大量的 URL 缩短请求。 速率限制器有助于根据 IP 地址或其他过滤规则过滤掉请求。 如果您想重温有关速率限制的记忆，请参阅“第 4 章：设计速率限制器”。
* Web 服务器扩展：由于 Web 层是无状态的，因此很容易通过添加或删除 Web 服务器来扩展 Web 层。
* 数据库的扩展。数据库复制和分片是常见的技术。
* 分析。数据对商业成功越来越重要。将分析解决方案整合到 URL 缩短器中，可以帮助回答一些重要的问题，如有多少人点击一个链接？他们何时点击链接？等等。
* 可用性、一致性和可靠性。这些概念是任何大型系统成功的核心。我们在第1章中对它们进行了详细讨论，请对这些主题进行复习记忆

恭喜你走到了这一步！现在给自己一个鼓励，干得漂亮！

### 参考资料

\[1] A RESTful Tutorial: <https://www.restapitutorial.com/index.html>

\[2] Bloom filter: <https://en.wikipedia.org/wiki/Bloom_filter>