短链接、短网址使用的是什么算法？

我的文章可以带着不了解短链接的同学入门~

前言

只有光头才能变强。
文本已收录至我的GitHub仓库，欢迎Star：https://github.com/ZhongFuCheng3y/3y

最近接了一个需求，涉及到了短链接的相关的知识，于是去查阅了相关的资料，在这里给大家整理分享一下。

一、短链接介绍

举个例子，现在我的GitHub的地址是这个：https://github.com/ZhongFuCheng3y/3y (36个字符)

我通过百度的短链接服务可以将上面的地址转成https://dwz.cn/LwlrfG4j(23个字符)

那我为什么要将原有的URL转成较短的链接呢？比如我们发短信提醒用户去XXX，XXX有优惠活动，在文案上往往会带有一个链接进行跳转，方便用户快速去到对应的活动落地页。

而短信的发送是需要成本的，短信的成本主要有两方面组成：

1. 发送的人数（发的人越多，自然短信的花费就越大，这个我就不解释了）
2. 短信发送的字数（比如，文案总字数超过70个字，那就算两条短信计费，超过140个字就算三条短信计费）

所以在发送短信给用户时：要么就投放更加精准优质的用户，以便控制好发送的数量，要么就尽可能控制文案的字数。

显然，如果在短信上配上普通的URL，那真正的文案可写的字数就没多少了。于是我们可以发现，各大公司的短信推送的URL都是短链接。

比如在一些平台发布消息时会限制字数，如果我们的发的URL过长就很容易就被限制住了：

使用短链接的好处：短、字符少、美观、便于发布、传播。

二、短链接它是怎么干的呢？

我们先回到生成好的短链上https://dwz.cn/LwlrfG4j

虽然这个链接看起来有点奇怪，但他终究还是一个链接，从URL的特征我们可以分出：

• dwz.cn是域名
• LwlrfG4j是参数

我们在浏览器请求一下短链接看看是什么情况：

短链接的原理其实就是：

• 将长链接通过一定的手段生成一个短链接
• 访问短链接时实际访问的是短链接服务器，然后根据短链接的参数找回对应的长链接
• 重定向跳转

2.1 核心的要解决的问题

通过上面的分析我们可以知道的是，我们实际核心要做的是怎么从LwlrfG4j类似这样的参数找到对应的完整URL：https://github.com/ZhongFuCheng3y/3y

脑子第一时间想到的是：能不能通过一个压缩算法将https://github.com/ZhongFuCheng3y/3y压缩更小的字符？

显然，不能，压缩算法大多数都是针对大文本才奏效，本身的URL也不见得有多大...压缩出来肯定比原来的URL还大。

脑子第二时间想到的是：能不能用Hash算法？还是不能，用Hash存在哈希碰撞的问题

• 什么是哈希碰撞？两个不相同的字符串(值)进行Hash操作后，得到的哈希值相同。
• 这就意味着，两个完全不同的长链得到的哈希值一模一样，而我的短链是依赖哈希值去找到长链的(此时一个短链对应多个长链，这不合理)。

脑子第三时间想到的是？脑子想不到了。

现在业内用得比较多的是发号器（ID自增)+62进制编码：

• 比如，我将https://github.com/ZhongFuCheng3y/3y看作是10000，然后将10000进行62进制编码得到的结果是：2Bi

那我的短链URL就可以弄成https://3y.cn/2Bi，其中3y.cn是域名，2Bi是经过62进制转换后的参数。

为什么要用62进制转换？64进制转换倒是听得多了

• 62进制转换是因为62进制转换后只含数字+小写+大写字母。而64进制转换会含有/,+这样的符号（不符合正常URL的字符）
• 10进制转62进制可以缩短字符，如果我们要6位字符的话，已经有560亿个组合了。

总结：

• ID自增后，转成62进制，在DB保存映射关系，生成短链接

三、短信的链接直接跳转到APP

以下内容来源：https://sq.163yun.com/blog/article/158315832059072512 ，作者：西西吹雪

综合起来就是：

• 通过 Deep Links（iOS 则是Universal Links），可以实现点击短信链接直接唤起 App；
• 如果系统因为各种原因不支持 Deep Links，备选方案是 intent filter，不过会出弹框让用户选择用哪个 App 打开链接；
• 如果用户没有选择我们的 App 而是选择了浏览器打开，则通过 自定义 scheme 尝试唤起 App；
• 由于技术和成本问题，我们忽略不支持 自定义 scheme 的浏览器。

最后

这篇文章主要是简单了解一下短链接的相关知识，一个完备的短链服务肯定还要考虑更多的事，这里我就不展开了（毕竟我也没真正写过，可以在下方的链接继续学习）~

更多资料查阅：

• https://www.zhihu.com/question/29270034/answer/46446911
• https://hufangyun.com/2017/short-url/
• https://blog.csdn.net/c10WTiybQ1Ye3/article/details/78098840

乐于输出干货的Java技术公众号：Java3y。公众号内有200多篇原创技术文章、海量视频资源、精美脑图，关注即可获取！
关注我的GitHub，有人才交流群联系方式！：https://github.com/ZhongFuCheng3y/3y

觉得我的文章写得不错，点赞！

本文已收录至github仓库，更多分布式系统设计资料请参考

什么是短链接服务

短链接服务的目的是将普通url转换为比较短的url，当用户点击短链接的时候，会跳转到原始链接。短链接会带来几个好处：节省展示的空间、不容易出错、隐藏原始链接。常见的工具如：tinyurl，大家可以打开页面试用体验，帮助理解短链接服务的作用。

示例如下：

原始链接：

https://www.educative.io/collection/page/5668639101419520/5649050225344512/5668600916475904/

短链接：

http://tinyurl.com/jlg8zpc

系统功能需求分析

短链接服务需要满足如下需求：

• 功能性需求
• 指定一个url能够生成一个短链接
• 当用户点击短链接的时候会跳转到原始链接
• 用户可以定义短链接格式
• 用户可以设置链接的过期时间
• 非功能性需求
• 系统必须保证高可用，否则如果服务挂了，所有的链接跳转将会失败
• 链接跳转延迟须尽可能低
• 短链接内容不能被预测到
• 扩展性需求
• 服务可以通过REST API的方式被其他服务访问

系统容量评估

流量评估

假设每个月产生新的短链接是500M，读写流量比例是100：1.

100*500M=>50B

短链接生成请求QPS：

500Million /(30*24*3600)=~200 URLs/S

那么读，也即跳转请求QPS：

100*200=20K/S

存储空间

假设短链接会保存5年，那么总共需要保存的链接数：

500milion*5years*12months=30billion

估算每行数据所占存储大小是500bytes，那么需要的空间大小是：

30billion*500bytes=15TB。

网络带宽

写：

200*500bytes=100KB/S

读：

20K*500bytes=~10MB/S

内存

我们将频繁访问的热点url缓存在内存中，根据28原则，我们需要缓存20%的url。

那么每天的读请求量级是：

20K*3600S*24hours=~1.7billion

缓存20%：

0.2*1.7billion*500bytes=~170GB

系统API设计

//创建短链接
createURL(api_dev_key, original_url, custom_alias=None, user_name=None,
expire_date=None)
    
//删除短链接
deleteURL(api_dev_key, url_key)
    

数据库设计

在面试整个过程的早期进行数据库设计，能够帮助理解数据在不同组件之间的流向，以及为后续的数据分片提供必要的指引。

数据存储特性分析

关于数据存储，我们分析出具备如下特性：

• 需要存储的记录条数量级非常大，可能达到十亿级别
• 每条记录的大小比较小（<1K）
• 数据记录之间无关联关系
• 提供的服务读多写少

数据表的schema设计

我们需要创建2张表，分别存储URL的映射关系以及创建短连接的用户信息。

表-Url

表-User

数据库技术选型

由于我们需要存储的数据量级很大，而且我们不需要去关心记录之间的关系，因此我们可以采用nosql（如dynamodb、Cassandra、riak等），它比关系型数据库拥有更好的伸缩性。

系统概要设计

如何生成短连接？有2种可行的方案。

编码

我们可以通过编码计算的方式（MD5或SHA256）生成一个唯一hash串来组成短连接。如下面的短连接末尾的jlg8zpc是生成的hash字符串。

http://tinyurl.com/jlg8zpc

编码的方式存在如下问题：

• 如果不同的用户输入同样的url，那么得到的短连接是相同的，这是无法接受的
• 如果部分URL的部分内容是被编码过的呢？那么除了编码过的内容其他都是一样的。比如http://www.educative.io/distributed.php? id=design和http://www.educative.io/distributed.php%3Fid%3Ddesign）

对于短连接相同的情况，我们可以考虑在url后增加一个自增的唯一序列号来解决这个问题。而且我们无须存储这个序列号。但是带来一个新的问题是这个自增序列号是否会溢出。另一个问题是会带来性能上的损耗。

另一种方案是我们可以将用户userid拼接在url后面，但是如果用户没有登录，那么就拿不到userid。

离线生成key的方式

我们可以部署一个独立的key生成服务（key generation service），提前生成6位（假设我们要生成的短连接中hash长度是6位）并存储于db中。每当我们需要生成短连接的时候直接从db中取提前生成好的key即可。这种方案的好处是非常简单而且性能好。我们不仅不需要进行编码计算，也不需要担心重复的问题，KGS保证每个key是唯一的。

并发问题考虑

每一个key只能被使用一次，那么当一个key被取出使用之后需要进行打标。那么如果有多台服务器同时对外提供短连接生成服务，那么存在并发问题。

那么如何解决并发问题呢？KGS可以使用2张不同的表来分别存储未使用的key和已使用的key。每当KGS将一个key提供给一台短连接服务器的时候，就将其移动到已使用key存储表值。KGS在内存维持一个本地缓存，这样可以快速返回key给短连接服务器。

KGS是否存在单点失败问题？

是的，我们可以部署一主一备的方式，当主宕机后切换至备。

下图是短连接生成服务的整体概要设计图：

数据分片和副本

由于我们需要支撑十亿级别的数据量，我们必须对数据进行分片存储，需要定义对数据进行拆分和存储的schema。

• 按字符串内容的范围进行拆分。比如按照首字母进行拆分，A的在一个分片，B的在另一个分片，以此类推。或者可以将多个字符存储在同一个分片来减少区数。
• 这个方案最大的问题是可能导致数据倾斜。
• 基于hash的拆分。通过一个hash函数计算url得到一个hash值，比如得到1-256之间的数值，这个数值表示url应该落在哪个分片。推荐采用一致性hash的方式。

缓存

由于需要支持的读流量可能非常大，直接打到DB会对DB造成很大的压力。我们可以考虑使用缓存如memcache。

缓存大小评估

前面我们估计过，如果需要存放每天全量流量的20%需要170GB，对于现在的服务器来说内存大小是足够的。

缓存淘汰策略

比较合适的是使用LRU（Least recently used）策略，淘汰最近最少使用的url。我们可以使用类似Linked Hash Map来跟踪url的使用情况。

通常在海量流量的情况，为了性能和可用性考虑，缓存服务器需要设置多个副本。那么怎么更新缓存服务器？在某条数据缓存miss的时候，流量会打到后端DB，这个时候可以把DB返回的数据更新至所有的缓存服务器。

负载均衡

在我们的短连接服务系统中，有3个地方需要用到负载均衡：

1. 客户端和应用服务器之间
2. 应用服务器和缓存服务器之间
3. 缓存服务器和数据库之间

常见的负载均衡算法有如下几种：

1. 轮询法。将请求顺序轮流分配到后端服务器。好处是实现简单，不会给系统额外带来负荷，另外是一台服务器宕机后会自动停止发送流量至该服务器。缺点是没有考虑每台服务器的负载情况。
2. 随机法。随机将流量发送到一台服务器。
3. 源地址hash法。获取客户端的ip地址进行hash计算，用其数值对服务器数目进行取模运算，得到的结果即要发送到的服务器的序列号。
4. 加权轮询法。不同的服务器的配置和系统负载可能不同，因此可以给配置高负载低的机器配置更高的权重。将请求顺序按照权重分配到后端。
5. 加权随机法。和加权轮询法类似，不同的是按照权重随机请求后端服务器而不是顺序。
6. 最小连接法。根据后端服务器的连接请情况动态选择积压连接数最少的一台服务器。

数据库过期数据清除

过期的数据需要进行清除处理，可以降低数据库的存储空间，降低成本，提高查询性能。不过需要保证清除工作不会影响正常的短连接生成服务。可行的方案：

• 当用户请求到了一个过期的链接的时候，删除过期链接，并返回给用户错误码
• 单独设置一个过期数据清除服务，这个服务必须保证很轻量，可以在用户流量低峰期定时执行
• 若用户未设置过期时间，系统可以设置一个默认的过期时间，确保数据不会永久存在，导致DB无限增长

完整的短连接服务系统

完整的系统设计方案：