如何实现百亿级短URL生成器

示例代码

注：将ppt后缀名改为zip后解压

jdk版本：1.8.0_181

​

分享内容

1. 短URL生成器业务介绍
2. 短URL生成器需求分析(存储空间、吞吐量、网络带宽)
3. 短URL生成器概要设计(生成算法、预生成、部署模型)
4. 短URL生成器详细设计(重定向问题、自定义生成、Base64编码生成)
5. 总结

业务介绍

我们先来看看，当高并发遇到海量数据处理时的架构。在社交媒体上，人们经常需要分享一些 URL，但是有些 URL 可能会很长，比如：

https://example.com/hybrid/pvip?utm_source=pcdiscover-banner&utm_term=pc-discover-banner

这样长的 URL 显然体验并不友好。我们期望分享的是一些更短、更易于阅读的短 URL，比如像 https://link.com/6sINa6QMGeOUEI 这样的。当用户点击这个短 URL 的时候，可以重定向访问到原始的链接地址。为此我们将设计开发一个短 URL 生成器，产品名称是 “Fuxi（伏羲）”。

我们预计 Fuxi 需要管理的短 URL 规模在百亿级别，并发吞吐量达到数万级别。这个量级的数据对应的存储方案是什么样的？用传统的关系数据库存储，还是有其他更简单的办法？此外，如何提升系统的并发处理能力呢？这些是我们今天要重点考虑的问题。

1、需求分析

短 URL 生成器，也称作短链接生成器，就是将一个比较长的 URL 生成一个比较短的 URL，当浏览器通过短 URL 生成器访问这个短 URL 的时候，重定向访问到原始的长 URL 目标服务器，访问时序图如下:

​

对于需要展示短 URL 的应用程序，由该应用调用短 URL 生成器生成短 URL，并将该短 URL 展示给用户，用户在浏览器中点击该短 URL 的时候，请求发送到短 URL 生成器（短 URL 生成器以 HTTP 服务器的方式对外提供服务，短 URL 域名指向短 URL 生成器），短 URL 生成器返回 HTTP 重定向响应，将用户请求重定向到最初的原始长 URL，浏览器访问长 URL 服务器，完成请求服务。

1、短 URL 生成器的用例图

​

1. 用户 client 程序可以使用短 URL 生成器 Fuxi 为每个长 URL 生成唯一的短 URL，并存储起来。
2. 用户可以访问这个短 URL，Fuxi 将请求重定向到原始长 URL。
3. 生成的短 URL 可以是 Fuxi 自动生成的，也可以是用户自定义的。用户可以指定一个长 URL 对应的短 URL 内容，只要这个短 URL 还没有被使用。
4. 管理员可以通过 web 后台检索、查看 Fuxi 的使用情况。
5. 短 URL 有有效期（2 年），后台定时任务会清理超过有效期的 URL，以节省存储资源，同时回收短 URL 地址链接资源。

2、性能指标估算

Fuxi 的存储容量和并发量估算如下：

预计每月新生成短 URL 5 亿条，短 URL 有效期 2 年，那么总 URL 数量 120 亿

5亿 × 12月 × 2年 = 120亿

1、存储空间

每条短 URL 数据库记录大约 1KB，那么需要总存储空间 12TB（不含数据冗余备份）：

120 亿 × 1_KB_ = 12_TB_

2、吞吐量

每条短 URL 平均读取次数 100 次，那么平均访问吞吐量（每秒访问次数）2 万：

（5 亿 × 100） ÷ （30 × 24 × 60 × 60） ≈ 20000

一般系统高峰期访问量是平均访问量的 2 倍，因此系统架构需要支持的吞吐能力应为 4 万。

3、网络带宽

短 URL 的重定向响应包含长 URL 地址内容，长 URL 地址大约 500B，HTTP 响应头其他内容大约 500B，所以每个响应 1KB，高峰期需要的响应网络带宽 40MB

4 万（每秒）次请求 × 1_KB_ = 40_MB_

Fuxi 的短 URL 长度估算如下:

1. 短 URL 采用 Base64 编码，如果短 URL 长度是 7 个字符的话，大约可以编码 4 万亿个短 URL

如果短 URL 长度是 6 个字符的话，大约可以编码 680 亿个短 URL。

按我们前面评估，总 URL 数 120 亿，6 个字符的编码就可以满足需求。因此 Fuxi 的短 URL 编码长度 6 个字符，形如 https://link.com/ScW4dt 。

3、非功能需求

1. 系统需要保持高可用，不因为服务器、数据库宕机而引起服务失效。
2. 系统需要保持高性能，服务端 80% 请求响应时间应小于 5ms，99% 请求响应时间小于 20ms，平均响应时间小于 10ms。
3. 短 URL 应该是不可猜测的，即不能猜测某个短 URL 是否存在，也不能猜测短 URL 可能对应的长 URL 地址内容。

2、概要设计

短 URL 生成器的设计核心就是短 URL 的生成，即长 URL 通过某种函数，计算得到一个 6 个字符的短 URL。短 URL 有几种不同的生成算法。