【系统设计】设计一个短链接系统

短链接系统可以把比较长的 URL 网址转换成简短的网址字符串,短链接的优势是方便传播。适合在一些对字符串长度有要求的场景中使用,比如短信,微博等,比如

https://www.cnblogs.com/myshowtime/p/16227260.html

转换成短链接为

https://bit.ly/3z0QtB9

设计要求

《【系统设计】设计一个短链接系统》

根据面试的要求,你需要设计一个短链接系统, 链接的长度尽量比较短,每天生成 1 亿个URL,服务要运行 10 年。

首先,我们看一下短链接的工作原理。

工作原理

在 Chrome 上输入短链接,会发生什么?

打开开发者工具, 可以看到, 服务器收到请求后,会把短链接转换成长链接,然后返回浏览器,进行 301 重定向,请求到长链接地址。

《【系统设计】设计一个短链接系统》

另外一个问题,如何把长链接转换成短链接?

能否使用一些加密算法呢?明显是行不通的,因为字符串加密后会变的更长。

《【系统设计】设计一个短链接系统》

哈希算法

实际上,我们可以使用哈希算法和哈希表实现,如下

《【系统设计】设计一个短链接系统》

长链接经过哈希算法后, 会生成固定长度的哈希值 key,也就是短链接的值,并保存到哈希表中。

使用短链接查询长链接时,只需要查询哈希表即可。

《【系统设计】设计一个短链接系统》

上面是常见的哈希算法,最少也要8位。

那我们需要多少位的短链接呢?根据上面的要求,一天生成一个亿的短链接,运行10年,1亿 * 365 * 10 = 3650 亿。

短链接的字符在 [0-9,a-z,A-Z] 之间,总共 62 个不同的字符,可以计算出下面的数据。

《【系统设计】设计一个短链接系统》

可以看出,要满足系统要求的话,短链接的长度最少为 7 位。在实际中,很多短链接系统的长度也是 7 位。有兴趣的同学还可以看一下,米勒定律 7±2 法则。

上面的 CRC32 算法,最少也是 8 位。不过我们可以截取前 7 位,最后一位丢弃。但是这样可能会出现哈希冲突的问题,我们可以给长链接递归地拼接一个值,直到不再发现冲突,当然也可以用其他的哈希冲突解决方法。

Base 62 转换

这是另外一种常见的方法,Base 62 字符由大写字母 A-Z、小写字母 a-z 和数字 0-9 组成, 总共 62 位,如下

《【系统设计】设计一个短链接系统》

base 62 和 base 64 相比,只不过少了2个字符 + 和 /,大家可以想一下,这里我们为什么不用 base 64。

Base 62 和上面的哈希算法的思路是不一样的,哈希算法是根据长链接计算哈希值,然后保存到哈希表中。而 base 62 需要给每条长链接生成一个唯一的数字 ID,如下

《【系统设计】设计一个短链接系统》

那么如何计算短链接 ShortURL 呢? 因为 Id 是唯一的 10 进制数字,我们只需要把它转成 62 进制即可, 这里和从2进制转换到10进制是一样的。

假如有一个 ID 为 11157, 转换的过程如下

《【系统设计】设计一个短链接系统》

最终得到的短链接的值为 https://xxx.com/2TX。

《【系统设计】设计一个短链接系统》

总结

在本文中,介绍了两种实现短链接的方法,分别是哈希算法和 base 62。

哈希算法的特点是,固定的短链接长度,不需要生成唯一ID,可能会出现哈希冲突。

base 62 转换的特点是,长度不固定,取决于 ID 的大小,1000 转换后是 G8, 1000 亿 转换后是 1l9Zo9o。另外还需要生成唯一数字 ID,没有哈希冲突的问题。

希望对您有用!

译:等天黑

作者:Alex Xu

来源:《System Design Interview》

简介: Alex Xu 是一位经验丰富的软件工程师, 曾在 Twitter, Apple 和 Oracle 任职,来自CS名校卡内基梅隆大学,热衷于系统设计。

《【系统设计】设计一个短链接系统》

    原文作者:SpringLeee
    原文地址: https://www.cnblogs.com/myshowtime/p/16316654.html
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞