URL 短链接服务如何工作？

在高级别上，URL 短链接服务执行以下操作：

  • 服务器为每个长 URL 生成唯一的短 URL
  • 服务器编码短 URL 以提高可读性
  • 服务器将短 URL 持久化到数据存储
  • 服务器针对短 URL 将客户端重定向到原始长 URL

术语

以下术语可能对你有用：

  • 微服务：设计由小型独立服务组成的软件，具有特定目的
  • 服务发现：自动检测网络上设备和进程的过程
  • CDN：一组地理分布的服务器，通过将内容靠近用户来加速 Web 内容交付
  • API：允许两个应用或服务相互交谈的软件中介
  • 编码：将数据从一种形式转换为另一种形式以保留数据可用性的过程
  • 加密：使用密钥安全编码数据以保护数据机密性
  • 哈希：数据的单向摘要，无法逆转，用于验证数据完整性
  • 布隆过滤器：内存高效的概率数据结构，用于检查元素是否存在于集合中

什么是 URL 短链接服务？

URL 短链接服务是一个大幅缩短统一资源定位符（URL）的网站。短 URL 将客户端重定向到原始网站的 URL。一些流行的面向公众的 URL 短链接服务是 tinyurl.com 和 bitly.com。

缩短 URL 的原因如下：

  • 跟踪点击进行分析
  • 美化 URL
  • 为联盟隐藏底层 URL
  • 一些即时消息服务限制 URL 上的字符数

面试问题

候选人问

  • 系统的使用案例是什么？
  • 写入的日活用户（DAU）数量是多少？
  • 我们默认应该将短 URL 持久化多少年？
  • 系统的预期读写比是多少？
  • 短 URL 的使用模式是什么？
  • 谁将使用 URL 短链接服务？
  • 短 URL 的合理长度是多少？

面试官回答

  • URL 短链接和重定向到原始长 URL
  • 1 亿 DAU
  • 5 年
  • 100:1
  • 大多数短 URL 在创建后只会被访问一次
  • 普通公众
  • 最多 9 个字符

需求

功能需求

  • 类似 TinyURL 或 Bitly 的 URL 短链接服务
  • 客户端（用户）在系统中输入长 URL，系统返回缩短的 URL
  • 访问短 URL 的客户端必须被重定向到原始长 URL
  • 多个用户输入相同的长 URL 必须收到相同的短 URL（1 对 1 映射）
  • 短 URL 应该可读
  • 短 URL 应该无冲突
  • 短 URL 应该不可预测
  • 客户端应该能够选择自定义短 URL
  • 短 URL 应该对 Web 爬虫友好（SEO）
  • 短 URL 应该支持分析（非实时），如来自短 URL 的重定向次数
  • 客户端可选定义短 URL 的过期时间

非功能需求

  • 高可用性
  • 低延迟
  • 高可扩展性
  • 持久
  • 容错

范围外

  • 用户注册账户
  • 用户设置短 URL 的可见性

API 设计

URL 短链接

客户端执行 HTTP PUT 请求到服务器以缩短 URL。使用 HTTP PUT 方法是因为 PUT 是幂等的，幂等质量与长 URL 和短 URL 之间 1 对 1 映射的给定要求产生共鸣。

请求：

PUT /url
Authorization: Bearer <JWT>
Content-Type: application/json


{
  "long-url": "https://en.wikipedia.org/wiki/URL_shortening",
  "tags": ["productivity"],
  "expires": "datetime",
  "custom": "short-id" (optional)
}

响应：

200 OK
Content-Type: application/json


{
  "long-url": "https://en.wikipedia.org/wiki/URL_shortening",
  "short-url": "xy725ab",
  "created-at": datetime,
  "is-active": true
}

URL 重定向

客户端执行 HTTP GET 请求以从短 URL 重定向到原始长 URL。HTTP GET 请求没有请求体。

请求：

GET /:short-url
Authorization: Bearer <JWT>

响应：

301 Moved Permanently
Cache-Control: public, expires=datetime
Location: <long-url>

服务器将 location HTTP 头设置为长 URL。浏览器然后自动向接收到的长 URL 发出另一个 HTTP 请求。原始网站（长 URL）显示给客户端。

HTTP 响应状态码对比：

  • 301：永久重定向。Web 爬虫收到 301 状态码时更新其记录。301 状态码默认在客户端存储缓存。
  • 302：临时重定向。302 状态码不改善原始网站的 SEO 排名。
  • 307：临时重定向。307 状态码让客户端在重定向时重用原始请求的 HTTP 方法和体。
  • 404：当客户端对数据库中不存在的短 URL 执行重定向请求时，服务器响应 404 Not Found。

总结：在 HTTP 响应中使用 301 状态码以满足系统要求。

数据库

URL 短链接系统是读重的。换句话说，主导使用模式是从短 URL 重定向到长 URL。

数据库模式设计

数据库（数据存储）的主要实体是 Users 表和 URL 表。Users 和 URL 表之间的关系是 1 对多。用户可以生成多个短 URL，但短 URL 只能由单个用户生成。

数据存储类型

NoSQL 数据存储（如 DynamoDB 或 MongoDB）用于存储 URL 表。选择 NoSQL 存储 URL 表的原因如下：

  • 非关系数据
  • 动态或灵活模式
  • 不需要复杂连接
  • 存储许多 TB（或 PB）数据
  • 非常高 IOPS 的数据密集型工作负载
  • 易于水平扩展

SQL 数据库（如 Postgres 或 MySQL）用于存储 Users 表。选择 SQL 存储 Users 表的原因如下：

  • 严格模式
  • 关系数据
  • 需要复杂连接
  • 按索引查找非常快
  • ACID 合规

当客户端请求识别短 URL 的所有者时，服务器从不同数据存储查询 Users 表和 URL 表，并在应用层连接表。

容量规划

注册用户数量相对有限，与生成的短 URL 数量相比。容量规划（粗略估计）计算专注于 URL 数据。然而，计算的数字是近似值。

流量

URL 短链接是读重的。写入的日活用户（DAU）是 1 亿。读的每秒查询数（QPS）大约是 10 万。

存储

缩短的 URL 默认在数据存储中持久化 5 年。每个字符大小假设为 1 字节。

总共，URL 记录大约 2.5 KB 大小。

设置存储的复制因子至少为三以提高持久性和灾难恢复。

带宽

入站是进入服务器的网络流量（客户端请求）。出站是离开服务器的网络流量（服务器响应）。

内存

URL 重定向流量（出站）被缓存以提高延迟。遵循 80/20 规则，80% 的出站由缓存服务器上存储的 20% URL 数据服务。剩余 20% 的出站由数据存储服务以提高延迟。1 天的生存时间（TTL）是合理的。

编码

编码是将数据从一种形式转换为另一种形式的过程。编码缩短 URL 的原因如下：

  • 提高短 URL 的可读性
  • 使短 URL 更不易出错

URL 短链接中使用的编码格式必须产生确定性（无随机性）输出。满足 URL 短链接用例的潜在数据编码格式如下：

编码格式基数字符集
Base6262a-z, A-Z, 0-9
Base5858类似 Base62，但避免不易区分字符（O、0、I、l）

Base58 编码格式类似于 Base62 编码，只是 Base58 避免不易区分字符如 O（大写 O）、0（零）、I（大写 I）、l（小写 L）。Base62 编码中的字符消耗 6 位（2⁶ = 64）。Base62 编码中 7 字符长度的短 URL 消耗 42 位。

以下通用公式用于计算使用特定编码格式和输出字符数产生的短 URL 总数：

短 URL 生成
短 URL 总数 = 分支因子 ^ 深度

其中分支因子是编码格式的基数，深度是字符长度。

编码格式和输出长度的组合生成以下短 URL 总数：

编码长度总数
Base627 字符3.5 万亿

短 URL 总数与编码输出长度成正比。然而，短 URL 的长度应尽可能短以提高可读性。7 字符长度的 Base62 编码输出生成 3.5 万亿短 URL。当每秒使用 1000 个短 URL 时，3.5 万亿短 URL 总数在 100 年内耗尽。

Base 转换的时间复杂度是 O(k)，其中 k 是字符数（k = 7）。Base 转换的时间复杂度降低到常数时间 O(1)，因为字符数是固定的。

总结：7 字符 Base62 编码输出满足系统要求。

写路径

服务器缩短客户端输入的长 URL。缩短的 URL 被编码以提高可读性。服务器将编码的短 URL 持久化到数据库。

单机解决方案不满足 URL 短链接系统的可扩展性要求。生成函数被移出服务器到专用密钥生成服务（KGS）以扩展系统。

短 URL 生成方案

1. 随机 ID 生成器方案

密钥生成服务（KGS）查询随机标识符（ID）生成服务以缩短 URL。服务使用随机函数或通用唯一标识符（UUID）生成随机 ID。必须配置随机 ID 生成服务的多个实例以满足可扩展性需求。

随机 ID 生成服务必须是无状态的以轻松复制服务进行扩展。入站使用负载均衡器分发到随机 ID 生成服务。路由流量的潜在负载均衡算法如下：

  • 轮询
  • 最少连接
  • 最少带宽
  • 模哈希函数
  • 一致性哈希

基于一致性哈希或模哈希函数的负载均衡算法可能在大量客户端同时输入相同长 URL 时导致不平衡（热）副本。KGS 必须验证生成的短 URL 是否已存在于数据库中，因为输出的随机性。

随机 ID 生成解决方案有以下权衡：

  • 由于随机性，冲突概率高
  • 破坏短 URL 和长 URL 之间的 1 对 1 映射
  • 服务器之间需要协调以防止冲突
  • 频繁验证短 URL 是否存在于数据库中是瓶颈

总结：不要使用随机 ID 生成器解决方案缩短 URL。

2. 哈希函数方案

KGS 查询哈希函数服务以缩短 URL。哈希函数服务接受长 URL 作为输入并执行哈希函数如消息摘要算法（MD5）生成短 URL。哈希函数服务被复制以满足系统的可扩展性需求。

哈希函数服务必须是无状态的以轻松复制服务进行扩展。入站使用负载均衡器分发到哈希函数服务。

MD5 哈希函数输出的 Base62 编码产生 22 字符，因为每个 Base62 编码字符消耗 6 位，MD5 输出是 128 位。编码输出必须通过仅考虑前 7 字符（42 位）来截断以保持短 URL 可读。然而，多个长 URL 的编码输出可能产生相同前缀（前 7 字符），导致冲突。随机位附加到编码输出的后缀使其不可预测，以短 URL 可读性为代价。

哈希函数方案的权衡如下：

  • 由于哈希函数，输出可预测
  • 冲突概率更高

总结：不要使用哈希函数解决方案缩短 URL。

3. 令牌范围方案

KGS 查询令牌服务以缩短 URL。令牌服务的内部计数器函数生成短 URL，输出单调递增。

令牌服务必须水平分区（分片）以满足系统的可扩展性需求。令牌服务的潜在分片方案如下：

  • 列表分区
  • 模分区
  • 一致性哈希

列表和模分区方案不满足系统的可扩展性需求，因为两种方案都限制令牌服务实例数量。基于一致性哈希的分片符合系统要求，因为令牌服务通过配置新实例扩展。

入站使用负载均衡器分发到令牌服务。百分比编码的长 URL 使用一致性哈希进行负载均衡，以保持长 URL 和短 URL 之间的 1 对 1 映射。然而，基于一致性哈希的负载均衡可能在大量客户端同时输入相同长 URL 时导致热分片。

令牌服务实例的输出必须不重叠以防止冲突。高可靠分布式服务如 Apache Zookeeper 或 Amazon DynamoDB 用于协调令牌服务实例的输出范围。协调令牌服务实例之间输出范围的服务命名为令牌范围服务。

当选择键值存储作为令牌范围服务时，法定人数必须设置为更高值以增加令牌范围服务的一致性。更强的一致性通过防止多个令牌服务获取相同输出范围来防止范围冲突。

当 provision 令牌服务实例时，新实例从令牌范围服务执行输出范围请求。当获取的输出范围完全耗尽时，令牌服务从令牌范围服务请求新输出范围。

令牌范围服务如果频繁查询可能成为瓶颈。必须增加输出范围或令牌范围服务副本数量以提高系统可靠性。令牌范围解决方案无冲突且可扩展。然而，由于单调递增输出范围，短 URL 可预测。以下操作降低缩短 URL 的可预测性：

  • 附加随机位到输出后缀
  • 令牌范围服务给出随机输出范围

本文为学习目的的个人翻译，译文仅供参考。

原文链接：URL Shortening System Design。

版权归原作者或原刊登方所有。本文为非官方译本；如有不妥，请联系删除。