本文首发于公众号：托尼学长，立个写 1024 篇原创技术面试文章的flag，欢迎过来视察监督~
短链系统的核心功能，通过将长链接转换为短字符串的方式，提升链接的可读性和传播性，适用于消息通知、广告推广、社交媒体等场景。
如下图所示：
短链系统的核心功能有两个，短链跳转和短链生成，我们来一一看下具体实现，最后再讲讲如何实现高并发的短链系统。
短链跳转的实现原理
短链跳转有HTTP 302和HTTP 301两种实现方式，我们来分别讲解一下。
永久重定向（301）
浏览器会缓存第一次请求短链所重定向的长链，之后再有相同的短链请求，就可以直接从浏览器缓存中获取了，无须再给短链服务器发送请求获取。
StatusCode： 301 Moved Permanently
Location: https://origin.com/long-url?param=value
临时重定向（302）
当用户访问短链接的时候，短链服务器会返回原始的长链并进行HTTP重定向，将其转发到长链服务器上，这一切对于用户是无感的。
浏览器不会对请求短链所重定向的长链进行缓存，每次都需要请求短链服务器进行获取。
Status Code： 302 Moved Temporarily
Location: https://origin.com/long-url?param=value
那问题来了，我们到底应该选择HTTP 301还是302进行重定向呢？
如果我们的短链服务处于高并发场景，优先选择HTTP 301永久重定向的方式减少对服务的请求数，从而降低服务器的压力。
反之，在非高并发场景且对访问短链服务有计数诉求，那我们可以选择HTTP 302临时重定向。
短链生成的实现原理
接下来，我们来讲讲短链生成的实现原理：长链哈希、自增序列、随机字符串和预生成四种方案。
如下图所示：
长链哈希
（1）目前常见的哈希算法有MD5、SHA1、MurmurHash等，先将长链通过这些算法生成一个哈希值。
如：将长链“www.example.com/very/long/u…
（2）将生成的结果字符串进行截断，留下前6位短码，得到结果“3a6bd3”。
目前，6位短码已经能够满足绝大多数使用场景，因为6位的短码可以提供568亿种的组合。
（3）将截取后得到的短码和原始的长链建立一一映射关系，并存储在数据库或缓存中。
这样，当用户访问短码对应的短链时，系统就可以通过查询映射关系找到原始的长链，并进行重定向。
该方案的优点是实现简单，但存在哈希碰撞的可能性，在碰撞时需要在原来的哈希值上增加随机数再进行哈希。
自增序列
（1）目前有两种主流的实现方式，通过雪花算法或数据库自增ID来生成唯一数字ID。
前者则强依赖机器时钟，如果机器上时钟回拨，会导致ID重复。
后者的ID生成涉及到数据库操作，性能相对不高，且引入数据库会导致链路变长，增加出错概率。
（2）以进制转换的方式将数字ID进行缩短，如：十进制数字1234567890的六十二进制为1l3MoK。
（3）将截取得到的短码和原始的长链建立一一映射关系，并存储在数据库或缓存中。
该方案的优点是不存在长链哈希的碰撞问题，但如上文所述，也会根据实现方式不同引入其他问题。
随机字符串
（1）可以通过取UUID前8位字符的方式生成短码，将实现起来非常简单。
import java.util.UUID;
public class GenerateUUID {
public static void main(String[] args) {
// 生成一个随机的 UUID
UUID uuid = UUID.randomUUID();
// 输出生成的 UUID
String uuidString = uuid.toString();
// 截取前八位
String firstEightChars = uuidString.substring(0, 8);
// 输出截取的前八位
System.out.println("First eight characters: " + firstEightChars);
}
}
（2）以进制转换的方式将数字ID进行缩短，如：十六进制数字5ca877b6的六十二进制为k3v6bO。
（3）将截取得到的短码和原始的长链建立一一映射关系，并存储在数据库或缓存中。
该方案的优点是实现简单，通过JDK自带的工具类即可实现，连jar包都不需要引入，但会存在数字ID重复的问题。
预生成
该方案主要解决上述方案中，临时生成哈希值存在哈希碰撞，或临时生成数字ID存在重复的问题。
预先生成一批短码并存储在数据库中，当需要生成短链时，直接将未使用的短码与长链接进行关联即可。
当然，该方案相比于其他三种方案，实现起来更复杂一些。
实现高并发的短链系统
以阿里、字节、拼多多等互联网大厂的电商链接、短视频分享为例，每天会产生几亿条短链，访问短链的QPS会达到几百万。
如此高的并发量，对于短链系统承载力是个巨大的考验。
高并发短链系统架构设计如下：
（1）如上文所说，如果我们的短链服务处于高并发场景，优先选择HTTP 301永久重定向的方式减少对服务的请求数，从而降低服务器压力。
（2）雪花算法，每个服务器节点理论上可生成4096000个不重复的数字ID，然后再转换为62进制的短链。
由于雪花算法不会出现重复数字ID的情况，可以在代码中省去短链判重步骤，提升生成短链的吞吐量。
（3）采用Redis + Caffine双缓存机制存储热点短链，由于短链不会出现变更的情况，所以不用考虑数据一致性的问题。
（4）每天产生几亿条短链，换算下来每秒钟生成短链的峰值TPS可达到几万，采用分库分表的方案来均摊写操作带来的性能瓶颈，Sharding Key为短链值。
分片算法：
数据库ID = 短链码哈希值 % 数据库数量
数据表ID = 短链码哈希值 / 数据库数量 % 数据表数量
另外，短链映射表中的数据是冷热分明的，可通过三个月或半年进行归档的方式降低数据库的存储压力。
