怎么样设计一个高性能短链系统？

fny5jt9

前言

今天，咱们来谈谈怎样设计一个高性能短链系统，短链系统设计看起来很简单，但每一个点都能展开非常多知识点，亦是在面试中非常适合考察侯选人的一道设计题，本文将会结合咱们生产上稳定运行两年之久的高性能短链系统给大众简单介绍下设计这套系统所触及的有些思路，期盼对大众能有有些帮忙。

本文将会从以下几个方面来讲解，每一个点包括的信息量都不少，相信大众看完肯定有收获

短链有啥好处，用长链不香吗短链转的基本原理短链生成的几种办法高性能短链的架构设计

注：里面触及到不少布隆过滤器，snowflake 等技术，因为不是本文重点，因此意见大众看完后再自己去深入认识，否则展开讲篇幅会很长

短链有啥好处，用长链不香吗

来看下以下别人给我发的营销短信，点击下方蓝色的链接（短链）

浏览器的位置栏上最后会表示一条如下的长链。

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

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

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

再例如通常短信发帖有长度限度，倘若用长链，一条短信很可能要拆分成两三条发，本来一条一毛的短信费变成为了两三毛，何苦呢。另一用短链在内容排版上亦更美观。

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

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

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

短链转的基本原理

从上文可知，短链好处多多，那样它是怎样工作的呢。咱们在浏览器抓下包瞧瞧

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

重点过程便是拜访短网址后重定向拜访 B，那样问题来了，301 和 302 都是重定向，到底该用哪个，这儿需要重视一下 301 和 302 的区别

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

短链生成的几种办法

1、哈希算法

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

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

能够满足这般的哈希算法有非常多，这儿举荐 Google 出品的 MurmurHash 算法，MurmurHash 是一种非加密型哈希函数，适用于通常的哈希检索操作。与其它流行的哈希函数相比，针对规律性较强的 key，MurmurHash 的随机分布特征表现更良好。非加密寓意着着相比 MD5，SHA 这些函数它的性能肯定更高（实质上性能是 MD5 等加密算法的十倍以上），亦正是因为它的这些优点，因此虽然它显现于 2008，但日前已然广泛应用到 Redis、MemCache、Cassandra、HBase、Lucene 等众多著名的软件中。

画外音：这儿有个小插曲，MurmurHash 成名后，作者拿到了 Google 的 offer，因此多做些开源的项目，说不定成名后你亦能不经意间收到 Google 的 offer ^_^。

MurmurHash 供给了两种长度的哈希值，32 bit，128 bit，为了让网址尽可通地短，咱们选取 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 来存储。表结构应该如下所示

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」做第1步操作，倘若最后还是重复呢，再拼一个字段串啊，只要到时按照短链取出长链的时候把这些自定义好的字符串移除即是原来的长链。

以上过程显然是要优化的，插进一条记录居然要经过两次 sql 查找（按照短链查记录，将长短链对应关系插进数据库中），倘若在高并发下，显然会作为瓶颈。

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

因此该怎么优化呢

首要咱们需要给短链字段 surl 加上独一索引当长链经过 MurmurHash 得到短链后，直接将长短链对应关系插进 db 中，倘若 db 里不含有此短链的记录，则插进，倘若包括了，说明违反了独一性索引，此时只要给长链再加上咱们上文说的自定义字段「DUPLICATE」,重新 hash 再插进就可，看起来在违反独一性索引的状况下是多执行了过程，但咱们要晓得 MurmurHash 出现冲突的概率是非常低的，基本上不太可能出现，因此这种方法是能够接受的。

当然倘若在数据量很大的状况下，冲突的概率会增大，此时咱们能够加布隆过滤器来进行优化。

用所有生成的短网址构建布隆过滤器，当一个新的长链生成短链后，先将此短链在布隆过滤器中进行查询，倘若不存在，说明 db 里不存这里短网址，能够插进！

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

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

用哈希算法生成的短链其实已然能满足咱们的业务需要，接下来咱们再来瞧瞧怎样用自增序列的方式来生成短链

2、自增序列算法

咱们能够守护一个 ID 自增生成器，例如 1，2，3 这般的整数递增 ID，当收到一个长链转短链的请求时，ID 生成器为其分配一个 ID，再将其转化为 62 进制，拼接到短链域名后面就得到了最后的短网址，那样这般的 ID 自增生成器该怎样设计呢。倘若在低峰期发号还好，高并发下，ID 自增生成器的的 ID 生成可能会系统瓶颈，因此它的设计就显出尤为重要。

重点有以下四种获取 id 的办法

1、类 uuid

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

2、Redis

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

不外用 Redis 这种方法，需要思虑持久化（短链 ID 总不可同样吧），灾备，成本有点高。

3、Snowflake

用 Snowflake 亦是个不错的选择，不外 Snowflake 依赖于系统时钟的一致性。倘若某台设备的系统时钟回拨，有可能导致 ID 冲突，或 ID 乱序。

4、Mysql 自增主键

这种方式运用简单，扩展方便，因此咱们运用 Mysql 的自增主键来做为短链的 id。简单总结如下：

那样问题来了，倘若用 Mysql 自增 id 做为短链 ID，在高并发下，db 的写压力会很大，这种状况该怎么办呢。

思虑一下，必定要在用到的时候去生成 id 吗，是不是能够提前生成这些自增 id ?

方法如下：

设计一个专门的发号表，每插进一条记录，为短链 id 预留  （主键 id * 1000 - 999） 到  (主键 id  * 1000) 的号段，如下

发号表：url_sender_num

如图示：tmp_start_num 表率短链的初始 id，tmp_end_num 表率短链的终止 id。

当长链转短链的请求打到某台设备时，先看这台设备是不是分配了短链号段，未分配就往发号表插进一条记录，则这台设备将为短链分配范围在 tmp_start_num 到 tmp_end_num 之间的 id。从 tmp_start_num 起始分配，始终分配到 tmp_end_num，倘若发号 id 达到了 tmp_end_num，说明这个区间段的 id 已然分配完了，则再往发号表插进一条记录就又获取了一个发号 id 区间。

画外音：思考一下这个自增短链 id 在机器上该怎么实现呢， 能够用 redis, 不外更简单的方法是用 AtomicLong，单机上性能不错，亦保准了并发的安全性，当然倘若并发量很大，AtomicLong 的表现就不太行了，能够思虑用 LongAdder，在高并发下表现更加优秀。

整体设计图如下

处理了发号器问题，接下来就简单了，从发号器拿过来的 id ，即为短链 id，接下来咱们再创建一个长短链的映射表就可， 短链 id 即为主键，不外这儿有个需要重视的地区，咱们可能需要防止多次相同的长链生成区别的短链 id 这种状况，这就需要每次先按照长链来查询 db 看是不是存在关联记录，通常的做法是给长链加索引，但这般的话索引的空间会很大，因此我们能够对长链适当的压缩，例如 md5，再对长链的 md5 字段做索引，索引就会小非常多。这般只要按照长链的 md5 去表里查是不是存在相同的记录就可。因此咱们设计的表如下

CREATE TABLE `short_url_map`

(

`id` int(11) unsigned NOT NULLAUTO_INCREMENTCOMMENT 短链 id

,

`lurl` varchar(10) DEFAULT NULL COMMENT 长链

,

`md5` char(32) DEFAULT NULL COMMENT 长链md5

,

`gmt_create` int(11) DEFAULT NULL COMMENT 创建时间

,

PRIMARY KEY (`id`

)

) ENGINE=InnoDB DEFAULT CHARSET

=utf8;

当然了，数据量倘若很大的话，后期就需要分区或分库分表了。

高性能短链的架构设计

在电商机构，经常有非常多活动，秒杀，抢红包等等，在某个时间点的 QPS 会很高，思虑到这种状况，咱们引入了 openResty，它是一个基于 Nginx 与 Lua 的高性能 Web 平台，因为 Nginx 的非阻塞 IO 模型，运用 openResty 能够容易支持 100 w + 的并发数，通常状况下你只要安排一台就可，不外为了避免单点故障，两台为宜，同期 openResty 亦自带了缓存机制，集成为了 redis 这些缓存模块，亦能够直接连 mysql。不需要再经过业务层连这些中间件，性能自然会高不少

如图示，运用 openResty 省去了业务层这一步，直达缓存层与数据库层，亦提高了不少性能。

总结

本文对短链设计方法作了仔细地剖析，旨在给大众供给几种区别的短链设计思路，文中触及到挺多像布隆过滤器，openResty 等技术，文中无展开讲，意见大众回头可以再仔细认识一下。再例如文中说到的 Mysql 页分裂亦需要对底层运用的 B+ tree 数据结构，操作系统按页获取等知识有比较仔细地认识，相信大众各个知识点都吃透后会收获不小。

巨人的肩膀

https://www.cnblogs.com/rjzheng/p/11827426.html

https://time.geekbang.org/column/article/80850

欢迎大众扫码关注公众号，一块探讨

30天打卡活动：

第九期30天打卡赠书和红包活动，今天正式起步！

近期热文：

1、别总写代码，这130个网站比涨工资都重要2、2月份Github上最热门的开源项目3、Linux命令详解：ping 和 traceroute命令4、一样用Vim编辑器，为何别人比你更有效？5、知名网站的 404 页面都长啥样？6、【限时免费】加入咱们的社群！

4lqedz

“板凳”（第三个回帖的人）‌