『架构实践』探索亿级短URL生成器的架构设计与源码分享

📣读完这篇文章里你能收获到

• 了解博主的短链生成的架构设计思路
• 学习不同的短链技术方案选择
• 学习基于混淆的自增短URL算法
• 了解博主造的轮子SuperShortLink短链开源项目
• 感谢点赞+收藏，避免下次找不到~

一、需求分析

1. 短链生成及访问需求

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

用户访问短URL时序描述：

1. 由应用调用短链服务生成短 URL，并将该短URL 展示给用户
2. 用户在浏览器中点击该短 URL 的时候，请求发送到短 URL 生成器
3. 短URL 生成器返回 HTTP 重定向响应，将用户请求重定向到最初的原始长 URL
4. 浏览器访问长 URL 服务器，完成请求服务

2. 短链应用授权管理需求

短链管理，短链系统管理员可以在管理后台做以下操作：

• 查看已生成的短链列表以及短链的访问次数统计
• 直接在线输入长URL生成短URL
• 管理短链系统的授权秘钥（只有已授权的应用才可通过HTTP请求生成短链）

秘钥使用时序图如下：

秘钥使用流程描述：

1. 由管理员在管理后台创建应用秘钥
2. 将秘钥配到应用程序中
3. 应用程序携带秘钥加密后的Token信息请求短链服务生成短URL
4. 短链服务接收到请求时校验Token是否合法，合法则返回相应的短URL

3. 非功能性需求

1. 系统需要保持高可用，不因单一服务器宕机而引起服务失效，即需保证服务是支持伸缩的
2. 短 URL 应该是不可猜测的，即不能猜测某个短 URL 是否存在，也不能猜测短 URL 可能对应的长 URL 地址内容

二、概要设计

概要设计阶段主要关注短链服务的用例、部署模型、领域设计及短链生成方案的选择

1. 短链服务用例图

1. 用户可以访问短URL，短链服务会将请求进行重定向
2. 应用程序可以通过短链服务为长URL生成唯一的短URL
3. 应用程序可以存储，统计分析短URL的相关数据，比如访问次数
4. 管理员可以在Web后台检索、查看短链的生成及使用情况
5. 管理员可以在Web后台管理授权访问的应用秘钥

2. 整体部署模型

短链服务的业务逻辑比较简单，相对比较有挑战的就是高并发的短URL的访问请求如何处理。高并发访问主要通过负载均衡与缓存解决。具体的架构图如下：

3. 领域设计

领域设计这块分为两部分，一部分是短链生成记录，另一部分是应用授权

4. 短链生成技术方案选择

短 URL 生成器的设计核心就是短 URL 的生成，即长 URL 通过某种函数，计算得到n个字符的短 URL。短 URL 有几种不同的生成算法。由于Base64后面两位的“+”和“/”在 URL 中会被编码为“%2B”以及“%2F”，需要进行再编码，因此不考虑后两位符号，下文皆以Base62编码（[A-Z]，[a-z]，[0-9]）作为描述

4.1 单项散列函数生成短 URL

散列函数可以将任意长度的输入（又叫做预映射， pre-image），通过执行复杂的运算，变成固定长度的输出又叫散列值， hash value）。在短URL生成中，散列函数可用于将长URL映射到短URL，从而达到缩短URL的效果。
通常的设计方案：

1. 将长URL作为散列函数的输入
2. 执行散列函数（MD5 或者 SHA256），将长URL转换为固定长度的哈希值
3. 将哈希值进行进一步处理，进行Base62编码，防止冲突
4. 将编码后的字符串截取N个字符作为短URL

具体流程如图：

• 优点：生成速度快
• 缺点：存在哈希碰撞，相同的哈希值对应不同的长URL，需要进行特殊处理以避免这一问题。虽然哈希碰撞的概率极低，但是 Base62 编码后再截断的 N 个字符有可能会冲突的概率就很高了。所以在生成的时候，需要先校验该短 URL 是否已经映射为其他的长 URL，如果是，那么需要重新计算（换单向散列算法，或者换 Base62 编码截断位置）。重新计算得到的短 URL 依然可能冲突，需要再重新计算

这样的冲突处理需要多次到存储中查找 URL，无法保证短链服务的性能要求，不考虑该方案

4.2 预生成短 URL

预生成短URL是指提前生成一些短URL并保存到数据库中，当用户需要缩短长URL时，直接从数据库中获取一个未被使用过的短URL，而不是现场生成新的短URL。
通常的设计方案：

1. 采用随机算法离线预生成一批短URL，为了避免短URL冲突，每次生成的时候都需要检查该URL是否已存在
2. 将预生成的短URL存到数据库
3. 从数据库的短URL池中取一部分放到缓存中
4. 当用户需要缩短一个长URL时，缓存中获取一个短URL
5. 当缓存中的短URL快用完时，需从数据库再加载一部分到缓存中
6. 当数据库中的预生成短URL快用完时，需要生成更多的短URL并添加到数据库中

具体流程如图：

• 优点：由于生成URL是离线计算，不会对服务器性能产生过大的负担，使用的时候读取短URL速度快
• 缺点：预生成短 URL 会生成大量未被使用的短URL，浪费了存储空间和资源。此外，如果预生成的短URL数量不足，用户可能需要等待新的短URL被生成才能完成操作。越到后期随机算法生成的URL产生冲突的概率会越大，导致需要对比的次数越多

由于需要提前占用大量的存储空间，所以暂不考虑该方案

4.3 基于混淆的自增短 URL

自增短 URL 一种免冲突的算法是用自增长自然数来实现，即维持一个自增长的二进制自然数，然后将该自然数进行 Base62 编码即可得到一系列的短 URL。这样生成的的短 URL 必然唯一，通常采用自增序列号的方式进行生成。原理是将每一个长链接映射到一个唯一的自增序列号，然后将自增序列号转换为指定长度的短链接
比如：

• 自然数 1 的常规Base62 编码是字符“B”
• 就可以用 http://1.***/B 作为短 URL。

弊端：但是这种算法将导致短URL是可猜测的，只要知道了其中一个短 URL，就可以猜测下一个短 URL

为了解决上述问题，基于上面的方式在生成时加入随机打乱编码Base62等混淆方法，可以增加被预测的概率，增强短URL的安全性
通常的设计方案：

1. 初始化一个计数器，用于记录已经生成的短URL数量
2. 当用户输入长URL时，将计数器自增1，并将自增后的值前面补0，比如自然数1变成0001
3. 然后将该值倒转，也就是0001变成1000
4. 为了防止短URL被预测，对转换后的Base62编码进行打乱或加密，以作混淆
5. 将倒转后的值转换为混淆加密后的Base62编码，得到短URL

具体流程如图：

• 优点：编码保证绝对唯一，不会出现碰撞冲突，生成速度较快，不需要提前占用存储空间
• 缺点：该方法需要维护一个计数器，如果生成短URL的并发量较大，性能瓶颈取决于计数器，计数器常见的方案：
  • Redis原子自增
  • 数据库自增主键

我们就是采用了基于混淆的自增短URL，计数器避免引入过多的中间件，因此选择了数据库自增主键

三、详细设计

在详细设计阶段，主要考虑重定向码、高并发场景应对方案、混淆加解密算法的解析及API授权校验的流程

1. 混淆自增算法详解

• 标准Base64编码表如下：

其中“+”和“/”在 URL 中会被编码为“%2B”以及“%2F”，需要进行再编码，因此直接使用标准 Base64 编码进行短URL 编码并不合适，所以，我们需要针对 URL 场景对 Base64 编码进行改造，Base64 编码表中的 62，63 进行编码移除，更新为Base62编码

1.1 混淆加密算法设计

1. 将标准编码随机打乱 ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789

举例：打乱成：s9LFkgy5RovixI1aOf8UhdY3r4DMplQZJXPqebE0WSjBn7wVzmN2Gc6THCAKhaut

2. 6位长度标准编码与打乱后编码的对应关系

可以看出，虽然打乱了，但还顺序性还是很明显

3. 将前面补0再倒转，由于6位长度最大11位，为了避免倒转后超过该数值，因此补到10位

1.2 恢复混淆解密算法设计

将请求收到的短链Key根据打乱后的Base62编码转成十进制数，补0到10位，然后倒转就得到原来的短链Id

1.3 算法量级支撑

2. 重定向响应码

满足短 URL 重定向要求的 HTTP 重定向响应码有 301 和 302 两种

• 301 表示永久重定向，即浏览器一旦访问过该短 URL，就将重定向的原始长 URL 缓存在本地，此后不再请求短 URL 生成器，直接根据缓存在浏览器（HTTP 客户端）的长 URL 路径进行访问
• 302 表示临时重定向，每次访问短 URL 都需要访问短 URL 生成器

一般来说，使用 301 状态码可以降低短链服务器的负载压力，但无法统计短 URL 的使用情况，而短链服务的架构设计完全可以承受这些负载压力，因此短链服务使用 302 状态码构造重定向响应

3. 高并发挑战方案

系统调用可以分成两种情况：

1. 应用请求生成短URL的过程
2. 用户访问短URL，通过短链跳转到长URL的过程

情况1：请求生成短URL不会太频繁，因为是手动点击生成的，因此第一点并发量会比较低，生成URL的性能瓶颈取决于计数器
情况2：由于是直接触达客户，一个短链可能被成千上万的客户访问，上述部署模型中也提到，主要通过负载均衡与缓存解决，在此的缓存选择了本地内存缓存，减少与分布式缓存网络请求的链路耗时，用户访问短链的泳道图如下：

具体流程：

1. 用户点击短URL，请求短链服务
2. 短链服务解密短链Key生成短链的自增Id
3. 通过自增Id到缓存中匹配是否有对应的长URL
4. 缓存匹配不到则根据主键Id查询数据库
5. 数据库中如果查不到长URL，则返回HTTP 404响应
6. 数据库中如果查到长URL，则更新缓存，再更新数据库的访问次数，然后重定向到长URL

4. API授权校验

授权校验主要做了三重校验：

1. Body携带的时间戳timestamp必须在60秒内
2. Body携带的应用Code（app_code）必须是数据库中已存在的
3. Headers携带的Token必须有效

Token的加密：由时间戳 + 应用秘钥 取大写Md5，具体值为：

$"timestamp={timestampStr}&&app_secret={appSecretStr}".ToMd5().ToUpper()

具体的授权流程如下：

四、Web管理后台

• 登录页

• 短链列表页

• 在线生成页

• 授权应用页

五、项目源码

这是一个基于.***开源的短链生成及监控系统，它包含了在线生成短链、短链跳转长链、支持短链访问次数以及Web监控页面，可以帮助我们更容易地生成短链、监控短链！

• https://github.***/Bryan-Cyf/SuperShortLink
• 欢迎大家提出PR，共同讨论进步

六、思考

1. 用户每次请求生成短 URL 的时候，短链服务都会返回一个新生成的短 URL，也就意味着，如果用户重复提交同一个长 URL 请求生成短 URL，每次都会返回一个新的短 URL。你认为这将导致什么问题？
2. 用户如果同时请求大量的无效短链过来，会遇到什么问题？

欢迎在评论区提出解决方法，没有思路的可私聊或者看源码