高性能短链系统的一些设计思考

前言

最近遇到一个需求，需要短时间内将大量的长链转换成短链然后再转成二维码，由于我们的短链服务是通过接口外部进行调用的，而且不能批量转换，所以这里就会出现一个情况就是短时间的大量请求接口会以失败告终，如果能自己设计一个短链系统，这个问题就能解决了。那么今天就来谈谈如何设计一个高性能短链系统。

本文将会从以下几个方面来进行探讨

为啥要用短链长链存在哪些问题
短链是如何实现跳转的
如何生成短链以及如何存储
如何保证高性能高可用

为啥要用短链长链存在哪些问题

下面是自如给我发的推送短信，点击下方蓝色的链接（短链）

浏览器接着会跳转到一个确认跳转页面。

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

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

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

再比如上面的短信如果一个长链直接怼上去满屏都是一个链接，非常不美观。

2、像我前言中的需求需要将链接转成二维码，如果是长链的话二维码非常密集而且很难识别，短链的话就会清爽很多,如下图所示

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

短链是如何实现跳转的

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

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

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

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

如何生成短链以及如何存储

1、Hash

短链怎么生成，我的第一反应,这不就是以不定长输入(长链)转换成定长输出(短链)【哈希的定义】，观察上面的短链很明显可以看到短链是由固定短链域名 + 长链映射成的一串字母组成(不定长输入–>定长输出)，那么这个哈希函数该怎么取呢，相信肯定有很多人说用 MD5，SHA 等算法，网上确实有很多是用md5先生成32位串，然后均分4段做hash处理，最后再随机取其中之一作为最后结果，只是我在想这个md5先生成32位串是否一定有必要，而且既然是加密就意味着性能上会有损失，其实我觉得这里的重点应该是hash并不是加解密，如何提升哈希的运算速度和减少冲突概率才是重点。以下属于借鉴内容了这里推荐 Google 出品的 MurmurHash 算法，MurmurHash 是一种非加密型哈希函数，适用于一般的哈希检索操作。与其它流行的哈希函数相比，对于规律性较强的 key，MurmurHash 的随机分布特征表现更良好。非加密意味着着相比 MD5，SHA 这些函数它的性能肯定更高（实际上性能是 MD5 等加密算法的十倍以上），也正是由于它的这些优点，所以虽然它出现于 2008，但目前已经广泛应用到 Redis、MemCache、Cassandra、HBase、Lucene 等众多著名的软件中。

MurmurHash 提供了两种长度的哈希值，32 bit，128 bit，为了让网址尽可通地短，我们选择 32 bit 的哈希值，32 bit 能表示的最大值近 43 亿，对于中小型公司的业务而言绰绰有余。对上文提到的极客长链做 MurmurHash 计算，得到的哈希值为 3002604296，于是我们现在得到的短链为固定短链域名+哈希值 = http://xxx.com/a/3002604296

上述结果还是有点长？

觉得10位的短链还是有点长怎么办？首先3002604296 这个结果是10进制数字，有一种方案就是将它转为 62 进制就可以缩短它的长度，10 进制转 62 进制如下，也就是按62取模，对应的余数在下面的字符串中取对应值：

62进制思路 : 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ

经过上面的取模运算然后取映射值，就可以将(3002604296)10进制数字转换成 (3hcCxy)62进制，立马又缩短了4位，因此最终的短链为 http://xxx.com/a/3hcCxy，6 位 62 进制数可表示 568 亿的数，应付长链转换绰绰有余，如果需要更短一点也是可以的，根据实际需求进行取舍吧，我们公司目前用的是8位https://xxx.com/r8CpSjCN

hash冲突了怎么办？

既然是哈希函数，那么很有可能两个不同的长链经过hash之后生成的短链是一样的，那么这个问题要怎么解决？这里给出的思路就是在长链的基础上添加随机字符串然后重试生成短链。

由上文知道访问短链能跳转到长链，那么长短链的关系一定是有一个地方存储的， Redis 或 Mysql ？，一般来说 Mysql 存储首选，redis缓存首选。表结构如下所示

CREATE TABLE `long_short_url_map` (
  `id` int(11) unsigned NOT NULL AUTO_INCREMENT,
  `long_url` varchar(160) DEFAULT NULL COMMENT '长链',
  `short_url` varchar(10) DEFAULT NULL COMMENT '短链',
  `created_at` datetime NOT NULL DEFAULT CURRENT_TIMESTAMP COMMENT '创建时间'
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

基于上面的组件可以做出如下的设计。

长链（longurl）经过 MurmurHash 后取模62得到最终短链。
再根据短链去 long_short_url_map 表中查找看是否存在相关记录，如果不存在，将长链与短链对应关系插入数据库中，存储。
如果存在，说明已经有相关记录了，此时在长串上拼接一个自定义好的字段，比如「duplicate+RandomNum」，「longurl + duplicate+RandomNum」去重试第一步操作，如果最后还是重复就继续重拾，如果没有重复了就把原longurl和短链的关系存储即可。

上面的步骤是没有加入缓存的，插入一条记录是需要经过两次(甚至三次(概率微乎其微)) sql 查询（1.根据短链查记录是否存在 2.将长短链对应关系插入数据库中），像我前言中的需求在高并发下，明显还是会有瓶颈出现的。一般数据库和应用服务（只做计算不做存储）会部署在两台不同的 server 上，执行两条 sql 就需要两次网络通信，这两次网络通信与两次 sql 执行是整个短链系统的性能瓶颈所在！

引入缓存减少第一次的sql查询？

很显然插入数据那一次的sql肯定没跑了，无论怎样那一次的sql都是要执行的

方案一 : 给短链字段 short_url 加上唯一索引，把唯一性校验直接交给数据库去做，可行但是数据库压力很大（唯一索引懂的都懂）
方案二 : 数据量很大的情况下，冲突的概率会增大，此时我们可以使用加Bloomfilter(缓存)来进行优化。

用所有生成的短网址构建布隆过滤器，当一个新的长链生成短链后，先将此短链在Bloomfilter中进行查找，如果不存在，说明 db 里不存在此短网址，可以插入，插入db之前先将短链放入Bloomfilter。Bloomfilter是一种非常省内存的数据结构，长度为 10 亿的布隆过滤器，只需要 125 M 的内存空间。

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

用哈希算法生成的短链其实已经能满足我们的业务需求，本人目前工作中遇到的短链就是用hash生成的只不过保留的是8位。其实还有另外一种是通过自增序列

2、Sequence

待完善

高性能短链的架构设计

在电商公司，经常有很多活动，秒杀，抢红包等等，在某个时间点的 QPS 会很高，考虑到这种情况，可以引入了 openResty，它是一个基于 Nginx 与 Lua 的高性能 Web 平台，由于 Nginx 的非阻塞 IO 模型，使用 openResty 可以轻松支持 100 w + 的并发数，一般情况下你只要部署一台即可，不过为了避免单点故障，两台为宜，同时 openResty 也自带了缓存机制，集成了 redis 这些缓存模块，也可以直接连 mysql。不需要再通过业务层连这些中间件，性能自然会高不少

上图所示，使用 openResty 可以直接跳过了业务层这一步，直达缓存层与数据库层，对性能也有大量提升。

总结

本文对短链设计方案作了一点总结，文中涉及到像Bloomfilter，openResty 等技术，后续再去详细讨论。值得说明的是Bloomfilter的确是一个强大的缓存层有必要好好学习一番。

前言

为啥要用短链 长链存在哪些问题