写在前面

这是一个面试高频问题，今天好好总结一下，希望读者能学到，自己也记录一下

短链好处

链接变短，在对内容长度有限制的平台发文，可编辑的文字就变多了
最典型的就是微博，限定了只能发 140 个字，如果一串长链直接怼上去，其他可编辑的内容就所剩无几了，用短链的话，链接长度大大减少，自然可编辑的文字多了不少。
再比如一般短信发文有长度限度，如果用长链，一条短信很可能要拆分成两三条发，本来一条一毛的短信费变成了两三毛，何苦呢。另外用短链在内容排版上也更美观。
我们经常需要将链接转成二维码的形式分享给他人，如果是长链的话二维码密集难识别，短链就不存在这个问题了,如图示

链接太长在有些平台上无法自动识别为超链接，会被切断

短链基本原理

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

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

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

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

需求分析

1.用户收到的是一个很短的网址，常用于短信、通知等。

2.短链接不能重复，全局唯一。如何快速检测是否重复。可用雪花算法生成id、hash算法、布隆过滤器判重。

3.访问量大，考虑高并发。常用于秒杀系统，具有瞬间高并发、时效性等特点。

4.考虑有效期。

下面针对上述4个问题，分别进行设计

问题一：如何生成短链接

假设有如下长链接

https://www.baidu.com/s?ie=utf-8&f=8&rsv_bp=1&tn=baidu&wd=ascii&oq=assici&rsv_pq=c1f8e1ac00028cfe&rsv_t=4aefd2UxMsyWWg1ahio%2FdCD5%2BbTGrARPGFxesfK3mYQRSFXyZ%2FVn4tqGz48&rqlang=cn&rsv_dl=tb&rsv_enter=1&rsv_sug3=10&rsv_sug1=10&rsv_sug7=100&rsv_sug2=0&rsv_btype=t&inputT=5226&rsv_sug4=5509

如何生成短链接呢？短链接格式一般如下

hash算法

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

能够满足这样的哈希算法有很多，这里推荐 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，于是我们现在得到的短链为固定短链域名+哈希值 = gk.link/a/3002604296

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

于是我们有 (3002604296)10 = (3hcCxy)10，一下从 10 位缩短到了 6 位！于是现在得到了我们的短链为 gk.link/a/3hcCxy。6 位 62 进制数可表示 568 亿的数，应付长链转换绰绰有余

为什么是62进制？因为62进制可以用0-9,a-z,A-Z表示，确保url中不会有奇怪字符。

自增id

（1）redis自增

用 Redis 是个不错的选择，性能好，单机可支撑 10 w+ 请求，足以应付大部分的业务场景，但有人说如果一台机器扛不住呢，可以设置多台嘛，比如我布置 10 台机器，每台机器分别只生成尾号0，1，2，… 9 的 ID, 每次加 10即可，只要设置一个 ID 生成器代理随机分配给发号器生成 ID 就行了。

需要考虑持久化、备灾、高并发等问题。

（2）数据库自增

数据库需要考虑单点故障问题。

snowflake

用 Snowflake 也是个不错的选择，不过 Snowflake 依赖于系统时钟的一致性。如果某台机器的系统时钟回拨，有可能造成 ID 冲突，或者 ID 乱序。

uuid

简单地说就是用 UUID uuid = UUID.randomUUID(); 这种方式生成的 UUID，UUID(Universally Unique Identifier)全局唯一标识符,是指在一台机器上生成的数字，它保证对在同一时空中的所有机器都是唯一的，但这种方式生成的 id 比较长，且无序，在插入 db 时可能会频繁导致页分裂，影响插入性能。

问题二：短链接不能重复

首先无论如何，需要设计一张表，保存短链接和长链接的映射关系

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 '短地址',
  `created_at` int(11) DEFAULT NULL COMMENT '创建时间',
  `effective_time` int(11) DEFAULT NULL COMMENT '有效时间',
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

生成短链接步骤如下：

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

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

基本操作是在短链接字段上增加索引，在高并发场景下还可以加上布隆过滤器。

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