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

 关注
发布于: 2020 年 08 月 03 日
短链服务的鼻祖是 TinyURL，是最早提供短链服务的网站，目前国内也有很多短链服务：新浪（t.cn）、百度（dwz.cn）、腾讯（url.cn）等等。
﻿
不得不问一句，为什么要用短链？这个问题的另外一层意思是，短链服务有必要存在吗？
﻿
套用万金油答案：存在即合理。
﻿
短链服务存在的合理性﻿
我们先说说短链服务存在的合理性。
﻿
短链唯一的一个优点是短。
﻿
微博的早期用户都知道，每条微博只能限制在 140 个字以内，如果想要分享一个链接，就需要减少描述的文字。
﻿
同样，如果想要在营销短信中放入一个链接，就需要考虑成本问题。如果是早期的手机，还需要考虑用户可能接收到三条断开的短信，严重影响短信触达和点击。
﻿
这个情况下，如果链接足够短，那其他内容就可以更加丰富了。但是我们可能根据不同业务定义不同长度的链接，而且为了满足其他需求（比如，统计营销数据），还会在普通链接上增加参数。因此短链由此而生，通过重定向跳转，通过一个很短的链接代替一条其他链接，比如只需要通过 <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>。
﻿
上面的两个例子证明了短链有存在的价值，我们总结几个短链的附加用处：
﻿
发送营销短信，更省钱：链接变短，短信长度就变小，所需要支付的短信费用就减少了，比如上面短链 20 个字符，原始链接 146 个字符，差出来的都是钱啊。
转为二维码，可识别度更高，比如下面两个二维码的图片，相同尺寸，因为内容数量的不同，单元格的密度也就随之不同
﻿
   
﻿
灵活可配置，因为短链跳转原始链接经过了一次重定向，如果在某个时间发现原始链接中有问题，或者需要跳转到其他地方，可以通过修改重定向的目标地址就可以了。这点对于线下物料投放非常有利，比如已经投放了二维码物料，这个时候发现期望跳转到其他网站或者活动，只需要修改短链的目标地址就行，而不需要全部替换已经投放的物料。
﻿
短链的原理﻿
其实前面已经提到，短链是通过服务器重定向到原始链接实现的。我们来观察下新浪微博的短链，控制台执行命令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 内容。整个交互流程如下：
﻿
﻿
短链生成方式﻿
根据 网页数量统计 信息，目前全球有 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 算法，这种算法是一种非加密型哈希函数，适用于一般的哈希检索操作，目前 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 附加上特殊字符串，直到躲开碰撞为止。具体操作如下图：
﻿
﻿
生成方式2：统一发号器﻿
这个就是不管来的是什么，通过集中的统一发号器，分配一个 ID，这个 ID 就是短链的内容，比如第一个来的就是https://tinyurl.com/1，第二个就是https://tinyurl.com/2，以此类推。当然可能一些分布式ID算法上来就是很长的一个序号了。为了获取更短路，还可以将其转为 62 进制字符串。
﻿
Redis 自增：Redis性能好，单机就能支撑10W+请求，如果作为发号器，需要考虑Redis持久化和灾备。
MySQL 自增主键：这种方案和Redis的方案类似，是利用数据库自增主键的提醒实现，保证ID不重复且连续自动创建。
Snowflake：这是一种目前应用比较广的ID序列生成算法，美团的Leaf是对这种算法的封装升级服务。但是这个算法依赖于服务器时钟，如果有时钟回拨，可能会有ID冲突。（有人会较真毫秒中的序列值是这个算法的瓶颈，话说回来了，这个算法只是提供了一种思路，如果觉得序列长度不够，自己加就好，但是每秒百万级的服务真的又这么多吗？）
等等。。。
﻿
>后续会有一篇单独介绍统一发号器的文章，完后会修改这里，并附上链接，或者你也可以关注我（微信号：看山的小屋），获取第一手资料。
﻿
对于统一发号器这种方式，还需要解决的一个问题是：如果同一个原始链接，应该返回相同的短链还是不同的短链？
﻿
答案是根据用户、地点等维度，相同的原始链接，返回不同的短链。如果判断维度都相同，则返回相同短链。这样做的好处是，我们可以根据短链的点击、请求信息，做数据统计。对于短链，我们牺牲的只是一些存储和运算，但是收集的信息却是无价的。
﻿
存储短链﻿
一般这种数据的存储无非就两种：关系型数据库或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算法淘汰非热点短链数据。流程如下图：
﻿
﻿
图中的布隆过滤器是为了防止缓存击穿，造成服务器压力过大。
﻿
这里还有一个问题：HTTP返回重定向编码时使用301还是302，为什么新浪微博会返回302，而不是更加符合语义的 301 跳转？（对于 HTTP 状态码不太了解的同学，可以从 《HTTP 状态码总结》 获得更多信息）
﻿
301，代表永久重定向。也就是说，浏览器第一次请求拿到重定向地址后，以后的请求，都是直接从浏览器缓存中获取重定向地址，不会再请求短链服务。这样可以有效减少服务请求数，降低服务器负载，但是因为后续浏览器不再向后端发送请求，因此获取不到真实的点击数。
302，代表临时重定向。也就是说，每次浏览器都会向服务器发起请求获取新的地址，虽然会给服务器增加压力，但在硬件过剩的今天，这点压力比起数据简直不值一提。所以，302 重定向才是短链服务的首选。
﻿
总结﻿
短链服务其实比较简单，没有太多的业务逻辑，主要考察对于分布式系统常用设计的理解，也是经常被用在面试过程中的一道题。这里只是提供大家一些设计思路，文中涉及到的发号器（分布式ID）、布隆过滤器、MurmurHash等都没有太过深入，因为每一个都不是三言两语可以说明白的，需要大家自行解决了。
﻿
﻿