浅谈短链的设计

2023-02-28

id path bit

背景目前在很多场景下，都需要短链，尤其是涉及到一些URL下发的逻辑。为什么需要短链呢？考虑到一个URL上有path、query等参数，各种参数拼接在一起就成了一个长不拉几的字符串。在很多社交平台上，对于发送的文本是有长度限制，过长的URL很容易被截断，然后触达就无效了。当用户收到一个短链，心情可能更

背景

目前在很多场景下，都需要短链，尤其是涉及到一些 URL 下发的逻辑。为什么需要短链呢？考虑到一个 URL 上有 path、query 等参数，各种参数拼接在一起就成了一个长不拉几的字符串。

在很多社交平台上，对于发送的文本是有长度限制，过长的 URL 很容易被截断，然后触达就无效了。当用户收到一个短链，心情可能更加愉悦：

短链组成

知己知彼百战百胜，先来看看一个短链有哪些信息。

协议 + 域名 + path，协议可以直接忽略。域名是必须的（废话），并且足够短，否则的话就变成了长的短链（挺傻的）。最后 path 的部分才是关键，看起来是一个由 6 个字符组成的字符串，并且字符的范围是大小写字母+数字。

足够短的域名需要什么条件？大概率钱够就行。涉及到钱的部分，这里就不深入探究了。所以来研究一下这个 path 的生成。

Path 的生成

获取一个序号

哈希算法

Path 的其中一种方式就是通过哈希算法计算得到。常见的哈希函数有 MD5、SHA1 等大家常见的加密型哈希算法，也有 HighwayHash、MurmurHash 等非加密型哈希函数。以 MurmurHash 为例，目前已经迭代到 MurmurHash 3，能够产生 32bit 和 128 bit 的哈希值，并且对于规律性较强的 key，随机分布的特征表现的很不错。

不过哈希冲突是不可控的，我们虽然有 N 种解决哈希冲突的方式，但是会增加整个系统的整体复杂度。

自增 ID

也可以维护一个 ID 自增生成器，对于每一个长链生成1、2、3等自增的序号，然后把长链和序号的映射保存在数据库里面，然后得到如 https://fake.short/1、https://fake.short/2 等短链。考虑到单机容易造成单点故障，所以一般都是分布式的 ID 生成器。

Mysql 自增

假设有 10 台 Mysql 服务器，每一台初始值分别为 0……9，然后每生成一个需要就递增 10，这样确保这 10 台 Mysql 服务器产生的 ID 不重复。但这个方案缺点比较明显，就是 ID 是有迹可循的，爬虫的可以顺着顺序依次请求得到；水平扩展不容易，如之前约定 10 台机器，每台机器生产的步长是 10，如果需要增加一台机器，比较困难；数据库压力还是很大，每次获取ID都得读写一次数据库，只能靠堆机器来提高性能。

基于雪花算法

SnowFlake 是 Twitter 公司采用的一种算法，目的是在分布式系统中产生全局唯一且趋势递增的ID。

第一位占用 1bit，其值始终是0，没有实际作用。2.时间戳占用 41bit，精确到毫秒，总共可以容纳约 69 年的时间。3.工作机器id 占用10bit，其中高位 5bit 是数据中心ID，低位 5bit 是工作节点ID，最多可以容纳 1024 个节点。4.序列号占用12bit，每个节点每毫秒0开始不断累加，最多可以累加到4095，一共可以产生 4096 个ID。

SnowFlake算法在同一毫秒内最多可以生成 1024 X 4096 = 4194304 个全局唯一ID。

国内也有不少基于（类）雪花算法的开源分布式唯一ID生成器：