第 8 章 设计短网址服务

引言

本章讨论如何设计一个类似 TinyURL 的短网址服务（URL Shortener）。该系统的主要目标包括 URL 缩短、重定向，以及能够应对大流量的高可扩展性。

需求

• 缩短后的 URL 必须唯一，并且尽可能短。
• 每天要处理 1 亿次 URL 生成，并能支撑 10 年。
• 支持高效的读操作，读写比为 10:1。
• 需要存储 3650 亿条记录，10 年下来大约需要 365 TB 的存储空间。

第 1 步：高层设计

API 端点

1. URL 缩短：

   • 端点：POST api/v1/data/shorten
   • 参数：{longUrl: longURLString}
   • 返回：shortURL

2. URL 重定向：

   • 端点：GET api/v1/shortUrl

   • 返回：用于重定向的 longURL。

     

URL 重定向

• 301 重定向： 301 重定向表示所请求的 URL 已被「永久」移动到长 URL。浏览器会缓存该响应， 之后对同一 URL 的请求将不会再发送到短网址服务。

• 302 重定向： 临时重定向；适用于点击跟踪之类的数据分析。

URL 缩短

• 使用哈希函数生成短 URL，把长 URL 映射为唯一的缩短版本。
• 哈希函数必须满足以下要求：
  • 每个 longURL 必须被哈希为一个 hashValue。
  • 每个 hashValue 都能映射回对应的 longURL。

第 2 步：深入设计

数据模型

把 <shortURL, longURL> 映射存储在关系型数据库中，以优化内存使用。表结构包括：

• id（主键），
• shortURL，

• longURL。

  

哈希函数

1. Base 62 转换：

• 使用 [0-9, a-z, A-Z] 这些字符对数字进行编码，共有 62 个可用字符。
• 进制转换是短网址服务中另一种常用的方法。
• 可以为短 URL 分配一个唯一 ID，再对该 ID 进行 Base 62 转换，得到短 URL。
• 7 个字符的哈希值最多可支持 3.5 万亿个唯一 URL，足以容纳 3650 亿个 URL。

示例：
把 ID 2009215674938 转换为 Base 62：

• 2009215674938 → zn9edcu。

2. 哈希 + 冲突解决：

• 使用 CRC32、MD5 或 SHA-1 等哈希函数。

  

• 一种做法是取哈希值的前 7 个字符，但这种方法可能导致哈希冲突。

• 为了解决冲突，可以递归地追加一个预定义的新字符串，直到不再冲突为止，但这样做的开销可能很大。

• 使用布隆过滤器（Bloom Filter）来解决冲突，实现高效查找。

  

对比

• 哈希 + 冲突解决：

  • 短 URL 长度固定
  • 不需要唯一 ID 生成器
  • 可能发生冲突，需要解决冲突
  • 由于不依赖 ID，无法找出下一个可用的短 URL

• Base 62 转换

  • 长度不固定，随 ID 增大而增长
  • 需要唯一 ID 生成器
  • 不可能发生冲突
  • 如果 ID 每次加 1，很容易推算出下一个短 URL（可能带来安全隐患）

URL 缩短流程

1. 检查数据库中是否已存在该 longURL。
2. 如果存在，返回已有的 shortURL。
3. 否则：
   • 使用分布式 ID 生成器生成一个唯一 ID。
   • 通过 Base 62 把该 ID 转换为 shortURL。
   • 把 <id, shortURL, longURL> 映射存储到数据库中。

URL 重定向流程

1. 用户点击一个 shortURL。
2. 查询 <shortURL, longURL> 映射：
   • 先查缓存，以加快访问速度。
   • 如果缓存中没有，再查询数据库。
3. 把用户重定向到 longURL。

其他考虑

限流器

• 通过限制每个 IP 的请求数来防止滥用。

可扩展性

1. Web 层： 无状态，可以通过增减 Web 服务器来扩展。
2. 数据库层： 使用复制和分片。

数据分析

• 收集点击率、来源和时间戳等数据，用于获取业务洞察。

高可用与可靠性

• 通过数据库复制和容错设计，保证服务一致、可靠。