设计一个系统将长链接地址转为短链接地址

背景

最近遇到一个面试题,问请你设计一个系统将长链接转为短链接。起初回答的不是很好,之后通过自己思考和查阅资料将这块的内容进行整理。

研究

定义

短地址(也叫 短网址:Short URL)就是为了让一个很长的网站链接缩短为一个短的链接,因为微博内有字数限制,所以短地址就是为了这个而产生的。大部分微博、手机短信提醒等地方已经有很多应用了。

优势

  • 节省网址长度,便于社交化传播。
  • 方便后台跟踪点击量、地域分布等用户统计。
  • 规避关键词、域名屏蔽手段。
  • 隐藏真实地址,适合做付费推广链接。

总之

1、链接变短,在对内容长度有限制的平台发文,可编辑的文字就变多了

最典型的就是微博,限定了只能发 140 个字,如果一串长链直接怼上去如连接后面是100个“has11nut06bab2y3”这样的字符的时候,其他可编辑的内容就所剩无几了,用短链的话,链接长度大大减少,自然可编辑的文字多了不少。再比如一般短信发文有长度限度,如果用长链,一条短信很可能要拆分成两三条发,本来一条一毛的短信费变成了两三毛。另外用短链在内容排版上也更美观。

2、我们经常需要将链接转成二维码的形式分享给他人,如果是长链的话二维码密集难识别,短链就不存在这个问题了。

跳转原理

设计一个系统将长链接地址转为短链接地址

我们可以认为他是整个交互的流程,具体的流程细节如下:

(1)用户访问短链接:https://dwz.date/fn4w

(2)短链接服务器dwz.date收到请求,根据URL路径fn4w获取到原始的长链接(KV缓存数据库中去查找):https://www.cnblogs.com/lingyejun/p/15894620.html

(3)服务器返回302状态码,将响应头中的Location设置为:https://www.cnblogs.com/lingyejun/p/15894620.html

(4)浏览器重新向https://www.cnblogs.com/lingyejun/p/15894620.html发送请求;

(5)返回响应;

具体方案

设计一个系统将长链接地址转为短链接地址

优化方案

算法优化

短链接标识一般是 [0-9, a-z, A-Z] 随机组合而成的字符串,字符一共有 62 个,因此短链接标识可以用 62 进制的字符串表示。

首先维护一个自增的 ID,当生成短链接时,将 10 进制的自增 ID 转换成 62 进制字符串,这个字符串就可以唯一标识一个长链接。由于 ID 是自增的,对应的 62 进制字符串是不同的,这样就不会出现一个短链接对应多个长链接的问题,62 个字符排列组合,可以保证短链接是用不完的,就算仅限于 6 位长度标识的短链接,也有 558 亿多种情况,这种算法在网上被称为自增序列算法。

1、62 进制的顺序并不一定严格按照 0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ 的顺序来表示,这个顺序可以是打乱的,这样生成的短链接标识更随机不易被破解。

2、长链接与短链接是否需要一对多关系,同一个长链接使用自增主键 ID 算法生成的短链接是不同的,因为自增主键 ID 不同,生成的 62 进制字符串自然也不同。如果我们有一个长链接唯一对应一个短链接需求,可以将长链接进行 md5 加密,将加密后的 md5 值存储在 DB 中,每次生成短链接前都根据长链接 md5 值查询 DB,如果存在,则直接返回短链接,当然也可以使用其他方式维护这种关系。

短地址发号器优化方案

1、算法优化

采用以上算法,如果不加判断,那么即使对于同一个原始URL,每次生成的短链接也是不同的,这样就会浪费存储空间(因为需要存储多个短链接到同一个URL的映射),如果能将相同的URL映射成同一个短链接,这样就可以节省存储空间了。主要的思路有如下两个:

方案1:查表

每次生成短链接时,先在映射表中查找是否已有原始URL的映射关系,如果有,则直接返回结果。很明显,这种方式效率很低。

方案2:使用LRU本地缓存,空间换时间

使用固定大小的LRU缓存,存储最近N次的映射结果,这样,如果某一个链接生成的非常频繁,则可以在LRU缓存中找到结果直接返回,这是存储空间和性能方面的折中。

2、可伸缩和高可用

如果将短链接生成服务单机部署,缺点一是性能不足,不足以承受海量的并发访问,二是成为系统单点,如果这台机器宕机则整套服务不可 用,为了解决这个问题,可以将系统集群化,进行“分片”。

在以上描述的系统架构中,如果发号器用Redis实现,则Redis是系统的瓶颈与单点,因此,利用数据库分片的设计思想,可部署多个发号器实例,每个实例负责特定号段的发号,比如部署10台Redis,每台分别负责号段尾号为0-9的发号,注意此时发号器的步长则应该设置为10(实例个数)。

另外,也可将长链接与短链接映射关系的存储进行分片,由于没有一个中心化的存储位置,因此需要开发额外的服务,用于查找短链接对应的原始链接的存储节点,这样才能去正确的节点上找到映射关系。

参考文章:

https://blog.csdn.net/xlgen157387/article/details/80026452

https://blog.csdn.net/codejas/article/details/106102452

https://blog.csdn.net/coderising/article/details/105085655

上一篇:Observable & Observer 既是可监听序列也是观察者


下一篇:get和post的区别