后端面试之系统设计-短网址（Short URL）服务怎么设计？

​ 原文地址：码农在新加坡的个人博客

短网址（short url），就是将长网址缩短为一个很短的网址，用户访问这个短网址可以重定向到原本的长网址（还原）。

可能你会问了，短链接有哪些使用场景呢？
事实上你一定见到过短网址，比如短信里面的网址，微博里面的链接。 短网址可以减少文本字数，隐藏链接参数等，有利于短信推广的作用，常用于有字数限制的短信、微博、二维码等场景。

比如我收到以下的短信：

点开短信链接：http://tb.cn/9GLkgHx

对应的实际的网址就是：

http://huodong.m.aliyun.com/act/v3jtax.html?gotoUrl=aliyun%3A%2F%2Fforward%2Ff6b8f0a4fa8cfd25da51a182807d5c25%3Ftarget_%3D%2Fapp%2Fhome%26tab_%3Dconsole

短信里面的那个url就是短网址，而实际的网址却又非常长。我们就需要一个服务去接收短网址，并转换成长网址访问。

我们常见的短网址如下，可以看到，短网址的域名都很短。

实践是最好的老师，我们自己实践一下，看一下浏览器输入短网址转换成具体的长网址的流程。

我们随便选择一个开放的短网址转换服务：

把我的长链接（微信公众号链接）转换成短网址。

https://mp.weixin.qq.com/s?__biz=MzkwNzMwNzI1Ng==&mid=2247483810&idx=1&sn=e252816ee1d5fc1358bf77b8146f3dba&chksm=c0da7035f7adf923ce0beef38a729f305e0d1cc8cc3c18cc491b1c37bffc0786962eaac41772&token=2107487666&lang=zh_CN#rd) 

如图可以看到： 生成了 https://t.hk.uy/aBpj 的短网址。

浏览器打开这个短网址（同时打开开发者模式）：

一图胜千言，我想你就能明白它的运行原理了。

原理

当我们在浏览器里输入 https://t.hk.uy/aBpj 时

1. DNS首先解析获得 https://t.hk.uy/aBpj 的 IP 地址
2. 当 DNS 获得 IP 地址以后（比如：1.2.3.4），会向这个地址发送 HTTP GET 请求，查询短码 aBpj
3. https://t.hk.uy 服务器会通过短码 aBpj 获取对应的普通网址
4. 请求通过 HTTP 301 转到对应的普通网址

301 HTTP状态码
301表示永久重定向，就是说浏览器在拿到服务器返回的这个状态码后会自动跳转到一个新的URL地址，这个地址可以从响应的Location首部中获取。

现在的互联网公司，基本上都会有自己的短网址服务，来解决类似的业务需求，短网址服务一般为公司内部的其他业务提供服务。

我们就来设计一个完整的适合生产环境使用的短网址服务，看一下这个短网址服务的实现需要考虑哪些方面。

首先会有一个短域名，一般域名也会非常短，为公司普通的域名的一些缩写。

比如: https://ab.cd/

然后生成一个短码， abCD12 映射到 正常的网址：https://www.leftpocket.cn/post/redis/multithreading/

那么 https:/ab.cd/abCD12 就是你的短网址。当用户点击这个短链接就自动跳转到正常的网站。

首先我们需要设计一个短码，要能负责把长链接转成短码。不同的长链接要能转成不同的短码。 短码一般是由 [a - z, A - Z, 0 - 9] 这62 个字母或数字组成，短码的长度也可以自定义，但一般不超过8位。

• 我上面生成的是4位短码：有 1440万。 (26+26+10)^4 = 14776336
• 5位短码：有91亿。(26+26+10)^5 = 916132832
• 6位短码：568亿。(26+26+10)^6 = 56800235584
• 7位短码：35216亿。(26+26+10)^6 = 35216亿

以上只是让大家对生成的数量有一个大概的概念。其实6位短码已经足够大部分场景了，我司的线上的短地址服务器使用的是7位。

目前比较流行的生成短码的方式有以下几种：自增ID，摘要算法，随机数，雪花算法。

一、自增ID

利用MySQL数据库的自增ID属性，每增加一个短码，就在上次添加的短码ID上加1，然后把10进制的id值，转化成一个62进制的字符串。这样就可以减少长度的目的。

比如 十进制的数字 10000000000 转换成62进制就是 aUKYOA， 只需要6位就足够了。

二、摘要算法

摘要算法又称哈希算法，它表示输入任意长度的数据，输出固定长度的数据。相同的输入数据始终得到相同的输出，不同的输入数据尽量得到不同的输出。

算法过程：

1. 将长网址md5生成32位签名串,分为4段, 每段8个字节；
2. 对这四段循环处理, 取8个字节, 将他看成16进制串与0x3fffffff(30位1)与操作, 即超过30位的忽略处理；
3. 这30位分成6段, 每5位的数字作为字母表的索引取得特定字符, 依次进行获得6位字符串；
4. 总的md5串可以获得4个6位串；取里面的任意一个就可作为这个长url的短url地址；

这种算法,虽然会生成4个,但是仍然存在重复几率。 虽然几率很小，但是该方法依然存在碰撞的可能性，解决冲突会比较麻烦。不过该方法生成的短码位数是固定的，也不存在连续生成的短码有序的情况。

三、普通随机数

该方法是从62个字符串中随机取出一个6位短码的组合，然后去数据库中查询该短码是否已存在。如果已存在，就继续循环该方法重新获取短码，否则就直接返回。

该方法是最简单的一种实现，不过由于Math.round()方法生成的随机数属于伪随机数，碰撞的可能性也不小。在数据比较多的情况下，可能会循环很多次，才能生成一个不冲突的短码。

四、雪花算法

雪花算法作为分布式ID生成方案，在分布式服务场景下使用方便，生成的ID区间递增。一直被广泛使用。

我们就是使用雪花算法生成的唯一ID。它相比于自增ID不依赖于数据库，同时方便支持分布式，性能更好。

然后根据ID生成62进制的短码，为了避免生成的短码有规律，我们先反转ID，然后再转换成62进制。最终生成的短码是无规律的。避免被恶意识别。

我们使用了MySQL作为短码的储存方案。

我们针对这个DB有两个主要的需求：

1. 根据原始网址生成短码，可以根据url_hash查询数据库，如果有存在的，更新过期时间，直接返回。
2. 用户点击短码，查询数据库，有记录，返回301重定向到实际的网址。

生成流程

• 指定的服务器调用 短网址服务 对普通网址生成一个短网址；
• 根据普通网址进行MD5 Hash生成一个MD5码；
• 根据MD5码（索引）和网址从数据库里面查询短网址记录；
• 有记录就把更新过期时间，并直接返回；
• 无记录则使用雪花算法生成一个分布式唯一ID，反转ID，并转换成62进制；
• 完整映射记录写入数据库并返回；

系统架构图

我们的服务有以下功能：

• 一个短网址服务，负责接收其他服务的 短网址生成 请求，同时接收用户的 短网址查询 请求。
• 其他服务根据业务需求向短网址服务申请生成短网址，并通过通知服务发送给用户。
• DB负责查询和生成短网址记录，Cache负责高并发情况下降低DB压力。
• 后台服务负责控制权限，只有特定的服务可以生成短网址。
• CronJob负责定时清理过期数据，防止数据库数据量过大。

如果业务量增大，数据库读写存在性能瓶颈，我们可以进行优化。

分库分表

为了支持写优化，可以进行分库分表。

缓存

读优化，我们就可以给数据库加一层缓存。

1. Redis/Memcached分布式缓存。 设置过期时间，避免占用过多内存。
2. 内存缓存。 使用LRU缓存来淘汰不经常访问的网址。

一个短网址服务的设计相对还是比较简单的，主要是考察一些细节：

• 短网址生成算法
• 数据库怎么设计
• 怎么重定向
• 高并发情况下的高可用
• 数据量过大怎么处理

<全文完>

欢迎关注我的微信公众号：码农在新加坡，有更多好的技术分享。