系统设计::设计短链接

设计短链接

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

了解问题并确定设计范围

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

应聘者：你能举个例子说明短链接的工作原理吗？
面试官：假设 URL https://www.systeminterview.com/q=chatsystem&c=loggedin&v=v3&l=long 是原始的 URL。你的服务创建了一个长度更短的别名： https://tinyurl.com/y7keocwj 。如果你点击这个别名，它就会把你重定向到原来的网址。
应聘者：流量是多少？
面试官：每天有 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 = 11,600
  • 假设短链接服务将运行 10 年，这意味着我们必须支持 1 亿 * 365 * 10 = 3650 亿条记录。
  • 假设平均 URL 长度为 100。
  • 10 年内的存储需求。3650 亿 * 100 字节 * 10 年=365TB

重要的是，你要和你的面试官一起走过这些假设和计算，以便你们两个人达成共识。

提出高水平的设计并获得认同

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

API 端点

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

  1. URL 缩短。为了创建一个新的短 URL，客户端发送一个 POST 请求，其中包含一个参数：原来的长 URL。该 API 看起来像这样。

POST api/v1/data/shorten

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

GET api/v1/shortUrl

  • 为 HTTP 重定向返回 longURL

URL 重定向

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

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

这里值得讨论的一点是 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 缩短

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

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

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

哈希函数的详细设计将在深入研究中讨论。

设计深挖

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

数据模型

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

哈希函数

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

哈希值的长度

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

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

我们将探索两种类型的 URL 短链接的哈希函数。第一种是 “哈希+碰撞解决”，第二种是 “base62 转换”。让我们逐一来看看它们。

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

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

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

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

base62 转换 基数转换是另一种常用于 URL 短链接的方法。基数转换有助于同一数字在其不同的数字表示系统之间的转换。基数 62 转换被使用，因为有 62 个可能的字符用于 hashValue。让我们用一个例子来解释转换是如何进行的：将 11157 10 转换成基数 62 表示法

  • 从它的名字来看，base 62 是一种使用 62 个字符进行编码的方式。其映射方式为：。0-0，…，9-9，10-a，11-b，…，35-z，36-A，…，61-Z，其中’a’代表 10，‘Z’代表 61，等等。

  • 11157 = 2 x 62^2 + 55 x 62^1 + 59 x 62^0 = [2, 55, 59] -> [2, T, X] 在基数 62 的表示。图 8-6 显示了转换的过程。

两种方法的比较，表 8-3 显示了两种方法的区别。

URL 缩短的深入研究

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

URL 缩短的深入研究

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

  1. longURL 是输入。
  2. 系统检查 longURL 是否在数据库中。
  3. 如果是，说明 longURL 之前已经转换为 shortURL。在这种情况下，从数据库中获取 shortURL 并将其返回给客户端。
  4. 如果不是，说明 longURL 是新的。一个新的唯一 ID（主键）由唯一 ID 生成器生成。
  5. 用 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 所示。

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

URL 重定向的深入研究

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

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

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

总结

在这一章中，我们谈到了 API 设计、数据模型、哈希函数、URL 缩短和 URL 重定向。

如果在采访结束时有多余的时间，这里有几个额外的谈话要点。

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

祝贺你走到这一步! 现在给自己拍拍胸脯吧。干得好!

参考资料

[1] a restful tutorial
[2] bloom filter