短链接方案设计

短链优点

那么为啥要用短链表示，直接用长链不行吗，用短链的话有如下好外

1、链接变短，在对内容长度有限制的平台发文，可编辑的文字就变多了

最典型的就是微博，限定了只能发 140 个字，如果一串长链直接怼上去，其他可编辑的内容就所剩无几了，用短链的话，链接长度大大减少，自然可编辑的文字多了不少。

再比如一般短信发文有长度限度，如果用长链，一条短信很可能要拆分成两三条发，本来一条一毛的短信费变成了两三毛，何苦呢。另外用短链在内容排版上也更美观。

2、我们经常需要将链接转成二维码的形式分享给他人，如果是长链的话二维码密集难识别，短链就不存在这个问题了,如图示

3、链接太长在有些平台上无法自动识别为超链接

如图示，在钉钉上，就无法识别如下长链接，只能识别部分，用短地址无此问题

短链跳转

短链好处多多，那么它是如何工作的呢。我们在浏览器抓下包看看

可以看到请求后，返回了状态码 302（重定向）与 location 值为长链的响应，然后浏览器会再请求这个长链以得到最终的响应,整个交互流程图如下

主要步骤就是访问短网址后重定向访问 B，那么问题来了，301 和 302 都是重定向，到底该用哪个，这里需要注意一下 301 和 302 的区别

301，代表永久重定向，也就是说第一次请求拿到长链接后，下次浏览器再去请求短链的话，不会向短网址服务器请求了，而是直接从浏览器的缓存里拿，这样在 server 层面就无法获取到短网址的点击数了，如果这个链接刚好是某个活动的链接，也就无法分析此活动的效果。所以我们一般不采用 301。
302，代表临时重定向，也就是说每次去请求短链都会去请求短网址服务器（除非响应中用 Cache-Control 或 Expired 暗示浏览器缓存）,这样就便于 server 统计点击数，所以虽然用 302 会给 server 增加一点压力，但在数据异常重要的今天，这点代价是值得的，所以推荐使用 302！

短链生成

哈希算法

怎样才能生成短链，仔细观察上例中的短链，显然它是由固定短链域名 + 长链映射成的一串字母组成，那么长链怎么才能映射成一串字母呢，哈希函数不就用来干这事的吗，于是我们有了以下设计思路

那么这个哈希函数该怎么取呢，相信肯定有很多人说用 MD5，SHA 等算法，其实这样做有点杀鸡用牛刀了，而且既然是加密就意味着性能上会有损失，我们其实不关心反向解密的难度，反而更关心的是哈希的运算速度和冲突概率。

能够满足这样的哈希算法有很多，这里推荐 murmurhash 算法.为了让网址尽可通地短，我们选择 32 bit 的哈希值，32 bit 能表示的最大值近 43 亿，对于中小型公司的业务而言绰绰有余。对上文提到的极客长链做 MurmurHash 计算，得到的哈希值为 3002604296，于是我们现在得到的短链为固定短链域名+哈希值 = http://gk.link/a/3002604296

有人说这个域名还是有点长，还有一招，3002604296 得到的这个哈希值是十进制的，那我们把它转为 62 进制可缩短它的长度，10 进制转 62 进制如下：

于是我们有 (3002604296)10 = (3hcCxy)10，一下从 10 位缩短到了 6 位！于是现在得到了我们的短链为 http://gk.link/a/3hcCxy

画外音：6 位 62 进制数可表示 568 亿的数，应付长链转换绰绰有余

如何解决哈希冲突的问题？

既然是哈希函数，不可避免地会产生哈希冲突（尽管概率很低），该怎么解决呢。

我们知道既然访问访问短链能跳转到长链，那么两者之前这种映射关系一定是要保存起来的，可以用 Redis 或 Mysql 等，这里我们选择用 Mysql 来存储。表结构应该如下所示

1
2
3
4
5
6
7


CREATE TABLE `short_url_map` (
  `id` int(11) unsigned NOT NULL AUTO_INCREMENT,
  `lurl` varchar(160) DEFAULT NULL COMMENT '长地址',
  `surl` varchar(10) DEFAULT NULL COMMENT '短地址',
  `gmt_create` int(11) DEFAULT NULL COMMENT '创建时间',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

于是我们有了以下设计思路。

将长链（lurl）经过 MurmurHash 后得到短链。
再根据短链去 short_url_map 表中查找看是否存在相关记录，如果不存在，将长链与短链对应关系插入数据库中，存储。
如果存在，说明已经有相关记录了，此时在长串上拼接一个自定义好的字段，比如「DUPLICATE」，然后再对接接的字段串「lurl + DUPLICATE」做第一步操作，如果最后还是重复呢，再拼一个字段串啊，只要到时根据短链取出长链的时候把这些自定义好的字符串移除即是原来的长链。

以上步骤显然是要优化的，插入一条记录居然要经过两次 sql 查询（根据短链查记录，将长短链对应关系插入数据库中），如果在高并发下，显然会成为瓶颈。

画外音：一般数据库和应用服务（只做计算不做存储）会部署在两台不同的 server 上，执行两条 sql 就需要两次网络通信，这两次网络通信与两次 sql 执行是整个短链系统的性能瓶颈所在！

所以该怎么优化呢

首先我们需要给短链字段 surl 加上唯一索引
当长链经过 MurmurHash 得到短链后，直接将长短链对应关系插入 db 中，如果 db 里不含有此短链的记录，则插入，如果包含了，说明违反了唯一性索引，此时只要给长链再加上我们上文说的自定义字段「DUPLICATE」,重新 hash 再插入即可，看起来在违反唯一性索引的情况下是多执行了步骤，但我们要知道 MurmurHash 发生冲突的概率是非常低的，基本上不太可能发生，所以这种方案是可以接受的。

我们返回的短URL一般是将数字转换成62进制,这样子可以更加有效的缩短URL长度,那么62进制的数字对计算机来说只是字符串,怎么存储呢?直接存储字符串对等值查找好找,对范围查找等太不友好了.

其实可以直接存储10进制的数字,这样不仅占用空间少,对查找的支持较好,同时还可以更加方便的转换到更多/更少的进制来进一步缩短URL.

当然如果在数据量很大的情况下，冲突的概率会增大，此时我们可以加布隆过滤器来进行优化。

用所有生成的短网址构建布隆过滤器，当一个新的长链生成短链后，先将此短链在布隆过滤器中进行查找，如果不存在，说明 db 里不存在此短网址，可以插入！

画外音：布隆过滤器是一种非常省内存的数据结构，长度为 10 亿的布隆过滤器，只需要 125 M 的内存空间。

综上，如果用哈希函数来设计，总体的设计思路如下

用哈希算法生成的短链其实已经能满足我们的业务需求，接下来我们再来看看如何用自增序列的方式来生成短链.

如果要杜绝哈希冲突,可以使用下面的自增序列算法.

自增序列算法

我们可以维护一个 ID 自增生成器，比如 1，2，3 这样的整数递增 ID，当收到一个长链转短链的请求时，ID 生成器为其分配一个 ID，再将其转化为 62 进制，拼接到短链域名后面就得到了最终的短网址.

如果使用自增id算法，会有一个问题就是不法分子是可以穷举你的短链地址的。原理就是将10进制数字转为62进制，那么别人也可以使用相同的方式遍历你的短链获取对应的原始链接。打个比方说：http://tinyurl.com/a3300和 http://bit.ly/a3300，这两个短链网站，分别从a3300 - a3399，能够试出来多次返回正确的url。所以这种方式生成的短链对于使用者来说其实是不安全的。

可以在 62 进制的转换过程中把排序好的 62 个字母数字随机打乱，比如 ABCD1234 打乱成 1BC43A2D, 转换的 62 进制也就更难 hack 了；

最后如果仍不放心，还可以在某些位置（比如 1，3，5）插入随机数，让人无法看出规律来也可以达到良好的效果。

解决了发号器问题，接下来就简单了，从发号器拿过来的 id ，即为短链 id，接下来我们再创建一个长短链的映射表即可，短链 id 即为主键，不过这里有个需要注意的地方，我们可能需要防止多次相同的长链生成不同的短链 id 这种情况，这就需要每次先根据长链来查找 db 看是否存在相关记录，一般的做法是根据长链做索引，但这样的话索引的空间会很大，所以我们可以对长链适当的压缩，比如 hash，再对长链的 hash 字段做索引，这样索引就会小很多。这样只要根据长链的 hash 去表里查是否存在相同的记录即可。所以我们设计的表如下

1
2
3
4
5
6
7


CREATE TABLE `short_url_map` (
  `id` int(11) unsigned NOT NULL AUTO_INCREMENT COMMENT '短链 id',
  `lurl` varchar(10) DEFAULT NULL COMMENT '长链',
  `hash` char(32) DEFAULT NULL COMMENT '长链hash',
  `gmt_create` int(11) DEFAULT NULL COMMENT '创建时间',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

但是上述方式仍要进行一次长链的hash,性能不佳,如果不判断长地址是否已转过,所以造成结果就是一长对多短,有人说浪费空间,建立一个长对短的map存储即可,但是用map存储本身就是浪费大量空间,甚至是用大空间换小空间,这就要考虑是否真有必要做一一对应,不能一对多;

最简单方案:建一个长对短的map,空间换空间,

更好的方案:用map存储"最近"生成的长对短关系,一小时过期机制实现LRU淘汰

长对短流程:

这个“最近”表中查看一下，看长地址有没有对应的短地址
有就直接返回，并且将这个key-value对的过期时间重置为一小时
如果没有，就通过发号器生成一个短地址，并且将这个“最近”表中，过期时间为1小时

当一个地址被频繁使用，那么它会一直在这个key-value表中，总能返回当初生成那个短地址，不会出现重复的问题。如果它使用并不频繁，那么长对短的key会过期，LRU机制自动就会淘汰掉它。

这样在空间和发号数量之间取得了一个平衡，此处也应该看具体的业务需求来，是否会存在一对多的情况。比如下单未支付，给用户发短信召回，短信内的短url里面存在用户昵称，订单号等个性化信息，即不需要增加这一逻辑环节了。

缓存

查询需求

个人认为对于几百个G的数据量都放在缓存肯定是不合适的，所以有个折中的方案：将最近3个月内有查询或者有新增的url放入缓存，使用LRU算法进行热更新。这样最近有使用的发概率会命中缓存，就不用走库。查不到的时候再走库更新缓存。

新增需求

对于新增的链接就先查缓存是否存在，缓存不存在再查库，数据库已经分表了，查询的效率也不会很低。

缓存的设计

查询的需求是用户拿着短链查询对应的真实地址，那么缓存的key只能是短链，可以使用 KV的形式存储。

存储

其实也可以考虑别的存储方案，比如HBase，HBase作为NOSQL数据库，性能上仅次于redis但是存储成本比redis低很多个数量级，存储基于HDFS，写数据的时候会先先写入内存中，只有内存满了会将数据刷入到HFile。读数据也会快，原因是因为它使用了LSM树型结构，而不是B或B+树。HBase会将最近读取的数据使用LRU算法放入缓存中，如果想增强读能力，可以调大blockCache。

其次，也可以使用ElasticSearch，合适的索引规则效果不输缓存方案。

分库分表

对于单条数据10b以内，一亿条数据总容量大约为 953G，单表肯定无法撑住这么大的量，所以有分表的需要，如果你对服务很有信心2年内能达到这个规模，那么你可以从一开始设计就考虑分表的方案。

那么如何定义分表的规则呢？

如果按照单表500万条记录来算，总计可以分为20张表，那么单表容量就是47G，还是挺大，所以考虑分表的 key 和单表容量，如果分为100张表那么单表容量就是10G，并且通过数字后缀路由到表中也比较容易。可以对short_code 做encoding编码生成数字类型然后做路由。

参考

高性能短链设计

答面试官问：如何设计短url服务

如何实现一个短链接服务

文章目录