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

用户头像
看山
关注
发布于: 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>。



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



  1. 发送营销短信,更省钱:链接变短,短信长度就变小,所需要支付的短信费用就减少了,比如上面短链 20 个字符,原始链接 146 个字符,差出来的都是钱啊。

  2. 转为二维码,可识别度更高,比如下面两个二维码的图片,相同尺寸,因为内容数量的不同,单元格的密度也就随之不同





  1. 灵活可配置,因为短链跳转原始链接经过了一次重定向,如果在某个时间发现原始链接中有问题,或者需要跳转到其他地方,可以通过修改重定向的目标地址就可以了。这点对于线下物料投放非常有利,比如已经投放了二维码物料,这个时候发现期望跳转到其他网站或者活动,只需要修改短链的目标地址就行,而不需要全部替换已经投放的物料。



短链的原理



其实前面已经提到,短链是通过服务器重定向到原始链接实现的。我们来观察下新浪微博的短链,控制台执行命令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 进制字符串。



  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算法淘汰非热点短链数据。流程如下图:





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



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



  • 301,代表永久重定向。也就是说,浏览器第一次请求拿到重定向地址后,以后的请求,都是直接从浏览器缓存中获取重定向地址,不会再请求短链服务。这样可以有效减少服务请求数,降低服务器负载,但是因为后续浏览器不再向后端发送请求,因此获取不到真实的点击数。

  • 302,代表临时重定向。也就是说,每次浏览器都会向服务器发起请求获取新的地址,虽然会给服务器增加压力,但在硬件过剩的今天,这点压力比起数据简直不值一提。所以,302 重定向才是短链服务的首选。



总结



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





发布于: 2020 年 08 月 03 日 阅读数: 114
用户头像

看山

关注

公众号:看山的小屋 2017.10.26 加入

主业:程序猿,兼职:架构师。游于码界,戏享人生。

评论

发布
暂无评论
系统设计系列之如何设计一个短链服务