东半球最接地气的短链接系统设计

作者：孤独烟

引言

今天下午，烟哥和同事在厕所里排队等坑的时候(人多坑少)。想象一下一个场景，我正在一边排队，一边拿着手机撩妹。前面一个同事，拿着手机短信转过头来和我聊天。

于是，我们就开始讨论下面这种短链接的实现原理(没错，上厕所也不忘学习！)。

点击其中短链接后，我们会跳到如下地址http://h5.dangdang.com/mix_20191015_or4x本文，我们来讨论一下其实现原理！

正文

需求缘起

这里说一下，为什么需要短链接？这个简单，比如大家发微博有字数限制

如果 URL 地址过长，显然可以写的关键字就越少!

再比如发短信如果短信内容过长，那么一条短信就要拆成两条发，浪费钱!

因此采用短链接，不仅节约资源，还十分美观!

请求流程

首先，我们先看看当当的短链接http://dwz.win/nXR

它是由两个部分组成

1. http://dwz.win:短链接系统的域名地址
2. nXR:请求参数

请求http://dwz.win/nXR地址后，返回状态如下所示

于是，我们可以推断出，敲下http://dwz.win/nXR地址后，发生了什么呢？

这里渣渣烟就要多嘴一句了。上图所示短链接系统，返回的状态可以为 301 或者 302，只是当当网用的是 301。

这里我要说一下，大家应该明白30X状态，在 HTTP 协议中，代表的是重定向的状态。那么301和302区别在哪呢，继续往下看。

301 代表什么？

301 代表的是永久重定向。什么意思呢? 对于 GET 请求, 301 跳转会默认被浏览器 cache。也就是说，用户第一次访问某个短链接后，如果服务器返回 301 状态码，则这个用户在后续多次访问同一短链接地址，浏览器会直接请求跳转地址，而不会再去短链接系统上取！

这么做优点很明显，降低了服务器压力，但是无法统计到短链接地址的点击次数。

302 代表什么？

302 代表的是临时定向。什么意思呢? 对于 GET 请求, 302 跳转默认不会被浏览器缓存，除非在 HTTP 响应中通过 Cache-Control 或 Expires 暗示浏览器缓存。因此，用户每次访问同一短链接地址，浏览器都会去短链接系统上取。

这么做的优点是，能够统计到短地址被点击的次数了。但是服务器的压力变大了。

下面说最关键的一段，怎么将http://h5.dangdang.com/mix_20191015_or4x压缩为nXR字符

算法原理

首先呢，我们需要一张表来存储，长短链接间的映射关系。表结构如下

好的，假设我们此时表里的数据如下

我们此时拿自增 id 作为短链接的 key。假设域名http://dwz.win是短链接系统，也就是说请求:

• (1)http://dwz.win/1会跳转http://h5.dangdang.com/mix_20191015_or4x;
• (2)http://dwz.win/2会跳转http://h5.dangdang.com/mix_20191102_ad3x;

这么做，也不是不行，有两个缺点你要评估能不能接受！

• (1)如果数据比较大，比如几百亿，你的 url 地址依然过长
• (2)你的数据具有规律性，别人用一个简单的脚本就可以遍历出你的跳转地址！

为了解决上面的两个缺点，我们增加一个列，用来存储 key 值。此时表结构如下

我们为了缩短 id 的长度呢，一般可以这么做。由于我们的短链接是由 a-z、A-Z 和 0-9 共 62 个字符可以选择。因此，我们可以将十进制的数字 id，转换为一个 62 进制的数，例如 201314 就可以转换为 Qn0。算法如下

private static final String BASE = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

public static String toBase62(long num) {
    StringBuilder sb = new StringBuilder();
    do {
        int i = (int) (num % 62);
        sb.append(BASE.charAt(i));
        num /= 62;
    } while (num > 0);

    return sb.reverse().toString();
}

另外，我们需要引入一个全局发号器，一直返回全局自增的 ID。相当于，我们的短链接系统先去请求这个全局自增 ID，然后将全局自增 ID 转换为 62 进制的数，作为 key。

接下来，解决第二个问题！数据具有规律性的问题。毕竟你转换为 62 进制后，只是解决了数据过长的问题，数据规律性问题还是没解决。因此，我们需要引入一个随机算法。

那么此时，你的考虑点在于，你是否要根据 key 值，反推出全局 id 值！来抉择不同的随机算法！

(1)不希望反推出全局 ID

OK，那就用一个洗牌算法，打乱算出的值。比如十进制的 201314 就可以转换为 Qn0。然后再使用洗牌算法，可以返回 n0Q、Q0n....其中之一。但是会有一定几率冲突，多洗几次就行。

(2)希望反推出全局 ID

OK，那就在得到 Qn0 这个数字后，将其转换为二进制数。然后在固定位，第五位，第十位...(等等)插入一个随机值即可。至于如何反推也很简单，你拿到短链接 key 后，将固定位的数字去除，再转换为十进制即可。

讲到这里，就基本将 key 如何生成的逻辑讲清楚了。那么用户在点击短链接的时候，例如地址http://dwz.win/nXR，短链接系统解析出 key 为 nXR，根据唯一索引去表中将 nXR 对应的 url 返回即可。

细节优化

(1)分库分表

如果这个系统是放在公网，给大家使用的。建议上来就分库分表，数据量过 1000 万是很容易的。这里涉及到一个问题，拿全局发号器给的自增 id 做分片健，还是拿转换后的 key 做分片键。

显然，用转换后的 key 做分片键会更容易一些。如果用 ID 做为分片键，存在两个问题！

1. 用户请求的 key，需要做一个逆运算推算回 ID，然后根据 ID，再去对应表里去找，增加响应时间。
2. 根据选择的随机算法不同，key 不一定能够推算回 ID 值。这种情况下，只能每张表去查，更慢。

所以用 key 做分片键，再适合不过了。拿到用户请求的 KEY 后，直接定位到对应的表里将 url 取出即可。

(2)读写分离

这种系统显然，读远大于写。建议可以考虑做读写分离。

(3)引入缓存

假设，我们在一个时间，给手机推送短信链接的短信后。显然，后面的一段时间内，对该短链接的请求量会大大提升。没有必要每次都去数据库查询，因此可以引入 redis 缓存。

(4)全局发号器

用其他算法行不行 ？可以。这里只是要一个全局唯一 ID 而已。自己要估算好，使用其他算法所带来的性能影响。以及采用其他算法，会不会造成生成的生成的 ID 过于规律。

(5)防攻击

做好被恶意攻击的准备，防止自增 ID 的值，被全部耗光