浅谈短链的设计

背景

目前在很多场景下，都需要短链，尤其是涉及到一些 URL 下发的逻辑。之前做小马 AI 课的业务时，销售通过短信下发的链接就是一个短链。为什么需要短链呢？考虑到一个 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等自增的序号，然后把长链和序号的映射保存在数据库里面，然后得到如 http://fake.short/1、http://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生成器：

1. UidGenerator

由百度开源的分布式 UID 生成器。http://github.com/baidu/uid-generator

2. Leaf

Leaf 是美团开源的分布式ID生成器，能保证全局唯一，趋势递增，但需要依赖关系数据库、Zookeeper等中间件。http://tech.meituan.com/2017/04/21/mt-leaf.html

进一步缩短

如果我们得到『1536389934』这个序号的话，看起来还是有点长，如果想进一步缩短，可以把十进制数转换成62进制数。然后就得到一个比原序号更短的 ID 了。

为什么要用62进制转换？

• 62进制转换是因为62进制转换后只含数字+小写+大写字母。而64进制转换会含有 / , + 这样的符号（不符合正常URL的字符）encodeURIComponent('+') => %xx

• 10进制转62进制可以缩短字符，如果我们要6位字符的话，已经有560亿个组合了。

重定向是 301 还是 302

众所周知，301 是永久重定向，浏览器会把重定向后的地址缓存下来，下次访问的时候，就不会向原地址发起请求；按理来说通过 301 的重定向性能会更好，对服务的压力也更小。

但是，正因为 301 会在浏览器中有缓存，所以服务端就没办法知道有多少用户是通过这个短链访问的，在现如今什么数据都可以分析一波的时代，这些数据的缺失，就失去了分析活动的能力。所以一般都通过 302 进行重定向，便于记录使用的数据，稍微增加点 Server 的压力。（没有什么是不能通过加机器解决的

参考资料

http://juejin.cn/post/6990275533057556494

http://tech.meituan.com/2017/04/21/mt-leaf.html

http://zhuanlan.zhihu.com/p/85837641

http://www.zhihu.com/question/29270034

http://www.zhihu.com/question/20103344