八、设计 URL 缩短器
在这一章中，我们将解决一个有趣而经典的系统设计面试问题:设计一个像 tinyurl 这样的 URL 缩短服务。
第一步——了解问题并确定设计范围
系统设计面试问题有意留有开放性。要设计一个精心制作的系统，提出澄清性问题至关重要。
候选人 :你能举例说明网址缩写是如何工作的吗？
面试官 :假设 URL https://www.systeminterview.com/q=chatsystem&c = logged in&v = v3&l = long 是原 URL。您的服务创建了一个较短的别名:https://tinyurl.com/ y7 keocwj。如果您单击别名，它会将您重定向到原始 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 看起来是这样的:
发布 api/v1/data/shorten
请求参数:{longUrl: longURLString}
返回快捷链接
2。URL 重定向。为了将短 URL 重定向到相应的长 URL，客户端发送 GET 请求。API 看起来是这样的:
获取 api/v1/shortUrl
返回 HTTP 重定向的 longURL】
网址重定向
图 8-1 显示了当你在浏览器上输入一个 tinyurl 时会发生什么。一旦服务器接收到 tinyurl 请求，它会使用 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 重定向最直观的方法是使用哈希表。假设哈希表存储了 < shortURL，longURL > 对，URL 重定向可以通过以下方式实现:
获取 longURL:longURL = hashtable . Get(short URL)
一旦获得长 URL，就执行 URL 重定向。
网址缩短
让我们假设短 URL 是这样的:www.tinyurl.com/{ hash value }。为了支持 URL 缩短用例，我们必须找到一个哈希函数nfx将一个长 URL 映射到 hashValue ，如图 8-3 所示。
哈希函数必须满足以下要求:
每个 长 URL 都必须哈希为一个 哈希值 。
每个 的哈希值 都可以映射回 longURL 。
深入讨论哈希函数的详细设计。
步骤 3 -设计深度潜水
到目前为止，我们已经讨论了 URL 缩短和 URL 重定向的高级设计 - 。在本节中，我们将深入探讨以下内容:数据模型、哈希函数、URL 缩短和 URL 重定向。
数据模型
在高层设计中，一切都存储在哈希表中。这是一个很好的起点；然而，这种方法对于真实世界的系统是不可行的，因为存储器资源是有限的并且昂贵的。更好的选择是在关系数据库中存储 < shortURL，longURL > 映射。图 8-4 显示了一个简单的数据库表设计。表格的简化版包含 3 列: id ， shortURL，longURL 。
哈希函数
Hash 函数用于将一个长 URL 哈希成一个短 URL，也称为 hashValue 。
哈希值长度
的哈希值 由[0-9，a-z，A-Z]的字符组成，包含 10 + 26 + 26 = 62 个可能的字符。求 的长度有一个值 ，求最小的 n 使得62^n≥3650 亿 。该系统必须支持高达 3650 亿网址的基础上回来的信封估计。表 8-1 显示了 hashValue 的长度及其对应的可以支持的最大 URL 数。
当 n = 7，62 ^ n = ~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.
如表 8-2 所示，即使是最短的哈希值(来自 CRC32)也太长(超过 7 个字符)。怎么才能让它变短？
第一种方法是收集哈希值的前 7 个字符；但是，这种方法会导致哈希冲突。为了解决哈希冲突，我们可以递归地添加一个新的预定义字符串，直到不再发现冲突。这个过程如图 8-5 所示。
这种方法可以消除碰撞；然而，查询数据库来检查是否每个请求都有一个 shortURL 是很昂贵的。一种叫做 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。longURL 是输入。
2。系统检查长 URL 是否在数据库中。
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 所示。
值得一提的是分布式唯一 ID 生成器。它的主要功能是生成全局唯一的 id，用于创建 shortURLs。在高度分布式的环境中，实现唯一的 ID 生成器是一项挑战。幸运的是，我们已经在“第 7 章:在分布式系统中设计唯一的 ID 生成器”中讨论了一些解决方案。你可以回头参考一下，以唤起你的记忆。
URL 重定向深潜
图 8-8 显示了 URL 重定向的详细设计。由于读取比写入多， < shortURL，longURL > 映射存储在缓存中以提高性能。
URL 重定向的流程总结如下:
1。用户点击一个短的网址链接: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 shortener 中有助于回答一些重要问题，比如有多少人点击了一个链接？他们什么时候点击链接？等等。
可用性、一致性和可靠性。这些概念是任何大型系统成功的核心。我们在第 1 章中详细讨论了它们，请刷新您对这些主题的记忆。
祝贺你走到这一步！现在给自己一个鼓励。干得好！
参考资料
