系统设计系列之如何设计一个短链服务

梦里梦外; 2021-09-24 13:56 418阅读 0赞

短链服务的鼻祖是 [TinyURL][]，是最早提供短链服务的网站，目前国内也有很多短链服务：新浪（t.cn）、百度（dwz.cn）、腾讯（url.cn）等等。

不得不问一句，为什么要用短链？这个问题的另外一层意思是，短链服务有必要存在吗？

套用万金油答案：存在即合理。

## 短链服务存在的合理性 ##

我们先说说短链服务存在的合理性。

短链唯一的一个优点是**短**。

微博的早期用户都知道，每条微博只能限制在 140 个字以内，如果想要分享一个链接，就需要减少描述的文字。

同样，如果想要在营销短信中放入一个链接，就需要考虑成本问题。如果是早期的手机，还需要考虑用户可能接收到三条断开的短信，严重影响短信触达和点击。

这个情况下，如果链接足够短，那其他内容就可以更加丰富了。但是我们可能根据不同业务定义不同长度的链接，而且为了满足其他需求（比如，统计营销数据），还会在普通链接上增加参数。因此短链由此而生，通过重定向跳转，通过一个很短的链接代替一条其他链接，比如只需要通过 [http://t.cn/A6ULvJho][http_t.cn_A6ULvJho] 这种 20 个字符的链接，就可以重定向到长度为 146 个字符的原始链接 [https://www.howardliu.cn/how-to-use-branch-efficiently-in-git/index.html?spm=5176.12825654.gzwmvexct.d118.e9392c4aP1UUdv&scm=20140722.2007.2.1989][https_www.howardliu.cn_how-to-use-branch-efficiently-in-git_index.html_spm_5176.12825654.gzwmvexct.d118.e9392c4aP1UUdv_scm_20140722.2007.2.1989]。

上面的两个例子证明了短链有存在的价值，我们总结几个短链的附加用处：

1.  发送营销短信，更省钱：链接变短，短信长度就变小，所需要支付的短信费用就减少了，比如上面短链 20 个字符，原始链接 146 个字符，差出来的都是钱啊。
2.  转为二维码，可识别度更高，比如下面两个二维码的图片，相同尺寸，因为内容数量的不同，单元格的密度也就随之不同
    
    ![http://t.cn/A6ULvJho][http_t.cn_A6ULvJho 1]  
    ![https://www.howardliu.cn/how-to-use-branch-efficiently-in-git/index.html??spm=5176.12825654.gzwmvexct.d118.e9392c4aP1UUdv&scm=20140722.2007.2.1989][https_www.howardliu.cn_how-to-use-branch-efficiently-in-git_index.html_spm_5176.12825654.gzwmvexct.d118.e9392c4aP1UUdv_scm_20140722.2007.2.1989 1]
3.  灵活可配置，因为短链跳转原始链接经过了一次重定向，如果在某个时间发现原始链接中有问题，或者需要跳转到其他地方，可以通过修改重定向的目标地址就可以了。这点对于线下物料投放非常有利，比如已经投放了二维码物料，这个时候发现期望跳转到其他网站或者活动，只需要修改短链的目标地址就行，而不需要全部替换已经投放的物料。

## 短链的原理 ##

其实前面已经提到，短链是通过服务器重定向到原始链接实现的。我们来观察下新浪微博的短链，控制台执行命令`curl -i http://t.cn/A6ULvJho`，结果如下：

HTTP/1.1 302 Found
    Date: Thu, 30 Jul 2020 13:59:13 GMT
    Content-Type: text/html;charset=UTF-8
    Content-Length: 328
    Connection: keep-alive
    Set-Cookie: aliyungf_tc=AQAAAJuaDFpOdQYARlNadFi502DO2kaj; Path=/; HttpOnly
    Server: nginx
    Location: https://www.howardliu.cn/how-to-use-branch-efficiently-in-git/index.html??spm=5176.12825654.gzwmvexct.d118.e9392c4aP1UUdv&scm=20140722.2007.2.1989
    
    <HTML>
    <HEAD>
    <TITLE>Moved Temporarily</TITLE>
    </HEAD>
    <BODY BGCOLOR="#FFFFFF" TEXT="#000000">
    <H1>Moved Temporarily</H1>
    The document has moved <A HREF="https://www.howardliu.cn/how-to-use-branch-efficiently-in-git/index.html??spm=5176.12825654.gzwmvexct.d118.e9392c4aP1UUdv&scm=20140722.2007.2.1989">here</A>.
    </BODY>
    </HTML>

从上面的信息可以看出来，新浪做了 302 跳转，同时为了兼容性，还返回用于手动调整的 HTML 内容。整个交互流程如下：

![短链跳转流程][format_png]

## 短链生成方式 ##

根据 [网页数量统计][Link 1] 信息，目前全球有 58 亿的网页，Java 中 int 取值最多是 2^32 = 4294967296 < 43 亿 < 58 亿，long 取值是 2^64 > 58 亿。所以如果是用数字的话，int 勉强能够支撑（毕竟不是所有网址都会调用短链服务创建短链），使用 long 就比较保险，但会造成空间浪费，具体使用哪种类型，需要根据业务自己判断了。

新浪微博使用 8 位字符串表示原始链接，这种字符串可以理解为数字的 62 进制表示，62^8 = 3521614606208 > 3521 亿 > 58 亿，也就是可以解决目前全球已知的网址。62 进制就是由 10 个数字 + (a-z)26 个小写字母 + (A-Z)26 个大写字母组成的数。

### 生成方式1：Hash ###

对原始链接取 Hash 值，是一种比较简单的思路。有很多现成的算法可以实现，但是有个避不开的问题就是：Hash 碰撞，所以选一个碰撞率低的算法比较重要。

推荐 [MurmurHash 算法][MurmurHash]，这种算法是一种非加密型哈希函数，适用于一般的哈希检索操作，目前 Redis，Memcached，Cassandra，HBase，Lucene 都在用这种算法。

借助 Guava 中的 MurmurHash 实现：

final String url = "https://www.howardliu.cn/how-to-use-branch-efficiently-in-git/index.html?spm=5176.12825654.gzwmvexct.d118.e9392c4aP1UUdv&scm=20140722.2007.2.1989";
    final HashFunction hf = Hashing.murmur3_128();
    final HashCode hashCode = hf.newHasher().putString(url, Charsets.UTF_8).hash();
    final int hashCodeAsInt = hashCode.asInt();// 这里选择返回 int 值，也可以选择返回 long 值
    System.out.println(hashCodeAsInt);// 输出的结果是：1810437348，转换成 62 进制是：1Ywpso

对于碰撞问题，最简单的一种思路是，如果发生碰撞，就给原始 URL 附加上特殊字符串，直到躲开碰撞为止。具体操作如下图：

![Hash+Bloom][Hash_Bloom]

### 生成方式2：统一发号器 ###

这个就是不管来的是什么，通过集中的统一发号器，分配一个 ID，这个 ID 就是短链的内容，比如第一个来的就是https://tinyurl.com/1，第二个就是https://tinyurl.com/2，以此类推。当然可能一些分布式ID算法上来就是很长的一个序号了。为了获取更短路，还可以将其转为 62 进制字符串。

1.  Redis 自增：Redis性能好，单机就能支撑10W+请求，如果作为发号器，需要考虑Redis持久化和灾备。
2.  MySQL 自增主键：这种方案和Redis的方案类似，是利用数据库自增主键的提醒实现，保证ID不重复且连续自动创建。
3.  Snowflake：这是一种目前应用比较广的ID序列生成算法，美团的Leaf是对这种算法的封装升级服务。但是这个算法依赖于服务器时钟，如果有时钟回拨，可能会有ID冲突。（有人会较真毫秒中的序列值是这个算法的瓶颈，话说回来了，这个算法只是提供了一种思路，如果觉得序列长度不够，自己加就好，但是每秒百万级的服务真的又这么多吗？）
4.  等等。。。

> 后续会有一篇单独介绍统一发号器的文章，完后会修改这里，并附上链接，或者你也可以关注我（微信号：看山的小屋），获取第一手资料。

对于统一发号器这种方式，还需要解决的一个问题是：如果同一个原始链接，应该返回相同的短链还是不同的短链？

答案是根据用户、地点等维度，相同的原始链接，返回不同的短链。如果判断维度都相同，则返回相同短链。这样做的好处是，我们可以根据短链的点击、请求信息，做数据统计。对于短链，我们牺牲的只是一些存储和运算，但是收集的信息却是无价的。

## 存储短链 ##

一般这种数据的存储无非就两种：关系型数据库或NoSQL数据库。有了上面的创建逻辑，存储就是水到渠成的了。下面给出MySQL存储的建表语句：

CREATE TABLE IF NOT EXISTS tiny_url
    (
        sid                INT AUTO_INCREMENT PRIMARY KEY,
        create_time        DATETIME  DEFAULT CURRENT_TIMESTAMP NULL,
        update_time        TIMESTAMP DEFAULT CURRENT_TIMESTAMP NULL ON UPDATE CURRENT_TIMESTAMP,
        version            INT       DEFAULT 0                 NULL COMMENT '版本号',
        tiny_url           VARCHAR(10)                         NULL COMMENT '短链',
        original_url       TEXT                                NOT NULL COMMENT '原始链接',
        # 其他附加信息
        creator_ip         INT       DEFAULT 0                 NOT NULL,
        creator_user_agent TEXT                                NOT NULL,
        # 用户其他信息，用于后续统计，对于这些数据，只要存储影响创建短链的必要字段就行，其他的都可以直接发送到数据服务中
        instance_id        INT       DEFAULT 0                 NOT NULL,
        # 创建短链服务实例ID
        state              TINYINT   DEFAULT 1                 NULL COMMENT '-1无效 1有效'
    );

再啰嗦一句，存储需要考虑数据量级，提前规划是否需要分表分库。

## 短链请求 ##

存储完成后，接下来就该使用了。

通常的做法是会根据请求的短链字符串，从存储中找到数据，然后返回HTTP重定向到原始地址。如果存储使用关系型数据库，对于短链字段一般需要创建索引，而且为了避免数据库成为瓶颈，数据库前面还会通过缓存铺路。而且为了提高缓存合理使用，一般通过LRU算法淘汰非热点短链数据。流程如下图：

![短链请求][format_png 1]

图中的布隆过滤器是为了防止缓存击穿，造成服务器压力过大。

这里还有一个问题：HTTP返回重定向编码时使用301还是302，为什么新浪微博会返回302，而不是更加符合语义的 301 跳转？（对于 HTTP 状态码不太了解的同学，可以从 [《HTTP 状态码总结》][HTTP] 获得更多信息）

*  301，代表永久重定向。也就是说，浏览器第一次请求拿到重定向地址后，以后的请求，都是直接从浏览器缓存中获取重定向地址，不会再请求短链服务。这样可以有效减少服务请求数，降低服务器负载，但是因为后续浏览器不再向后端发送请求，因此获取不到真实的点击数。
 *  302，代表临时重定向。也就是说，每次浏览器都会向服务器发起请求获取新的地址，虽然会给服务器增加压力，但在硬件过剩的今天，这点压力比起数据简直不值一提。所以，302 重定向才是短链服务的首选。

## 总结 ##

## 短链服务其实比较简单，没有太多的业务逻辑，主要考察对于分布式系统常用设计的理解，也是经常被用在面试过程中的一道题。这里只是提供大家一些设计思路，文中涉及到的发号器（分布式ID）、布隆过滤器、MurmurHash等都没有太过深入，因为每一个都不是三言两语可以说明白的，需要大家自行解决了。 ##

个人主页：[https://www.howardliu.cn][https_www.howardliu.cn]  
个人博文：[系统设计系列之如何设计一个短链服务][Link 2]  
CSDN 主页：[http://blog.csdn.net/liuxinghao][http_blog.csdn.net_liuxinghao]  
CSDN 博文：[系统设计系列之如何设计一个短链服务][Link 3]

![公众号：看山的小屋][format_png 2]

[TinyURL]: https://tinyurl.com/
[http_t.cn_A6ULvJho]: http://t.cn/A6ULvJho
[https_www.howardliu.cn_how-to-use-branch-efficiently-in-git_index.html_spm_5176.12825654.gzwmvexct.d118.e9392c4aP1UUdv_scm_20140722.2007.2.1989]: https://www.howardliu.cn/how-to-use-branch-efficiently-in-git/index.html?spm=5176.12825654.gzwmvexct.d118.e9392c4aP1UUdv&scm=20140722.2007.2.1989
[http_t.cn_A6ULvJho 1]: /images/20210923/d90bca2a235d4ba3b857781863436e82.png
[https_www.howardliu.cn_how-to-use-branch-efficiently-in-git_index.html_spm_5176.12825654.gzwmvexct.d118.e9392c4aP1UUdv_scm_20140722.2007.2.1989 1]: /images/20210923/f93fd26148744e3387f61ebaa4fd1f11.png
[format_png]: /images/20210923/6ed0049612594b8889dc319f98e9351b.png
[Link 1]: https://www.worldwidewebsize.com
[MurmurHash]: https://zh.wikipedia.org/wiki/Murmur%E5%93%88%E5%B8%8C
[Hash_Bloom]: /images/20210923/3411e2b138aa4b9899d1cedcfe93614a.png
[format_png 1]: /images/20210923/1fc5c46e553d43a8b2fb3ffaacead9ed.png
[HTTP]: https://www.howardliu.cn/the-introduction-of-http-status-codes/
[https_www.howardliu.cn]: https://www.howardliu.cn
[Link 2]: https://www.howardliu.cn/
[http_blog.csdn.net_liuxinghao]: http://blog.csdn.net/liuxinghao
[Link 3]: https://blog.csdn.net/liuxinghao/article/details/107754046
[format_png 2]: /images/20210923/f93d5eaf63de4f47b6d770ed2d600328.png