系统设计-Ch8-设计一个短链接生成器

设计一个短链接生成器

Step1：Understand the problem and establish design scope

对于”设计一个短链接生成器“这个系统设计话题，我们可以向面试官提出以下问题：

  • Q：我见过，是类似于B站那种b23.tv/xxxxxx的链接，然后重定向到bilibili.com/xxxx的？

    A：是的

  • Q：短链接可以删除或者更新吗？

    A：为了简单起见，生成后的短链接不能被主动删除或更新，但会有过期时间

  • Q：短链接的长度有要求吗？

    A：域名后的字串长度尽可能短

  • Q：域名后的字串有要求吗，纯数字或是纯字母，还是可以混合？

    A：可以是数字(0 ~ 9)和大小写字母(a~z, A~Z)的组合

  • Q：短链接对长链接的重定向是永久的还是临时的？

    A：临时的

  • Q：有没有性能要求？比如每天支持生成多少个URL短链接？

    A：每天生成一亿个url短链接

Step2：Propose high-level design and get buy-in

API Endpoints

通过上述分析，这个URL短链接生成器系统需要提供以下两个API：

  1. URLShorten(string long_URL)

    Post请求，接受一个长链接参数，判断该长连接是否有效（格式是否有效）

    • 无效则返回提示界面，有效则生成短链接并返回

  2. URLRedirect(string short_URL)

    Get请求，接收一个短链接参数，判断该短链接是否有效（格式是否有效，是否生成过，是否过期）:

    • 无效则返回提示界面，有效则重定向到对应长链接

本质上，我们需要做的就是找一个方式将long_URL转换成short_URL（long_URL->short_URL），然后把<short_URL， long_URL>这个键值对映射存储到一个非关系型key-value数据库中，简化的数据库表设计如下图所示：

URL Shortening

将long_URL转换成short_URL，这里介绍哈希+冲突解决和Base62编码两种方式。

Hash + collision resolution(哈希 + 冲突解决)

为了将long_URL转换为7位的字符串，我们可以用一些常见的Hash函数（如CRC32、MD5、SHA-1）来生成hashValue，然后取hashValue的前面7位：

然而，只取前面7位这样做避免不了冲突的，为了避免冲突，我们可以使用再哈希：

具体而言，就是当出现冲突后，给long_URL加上一个预设的字符串(predefined string)，然后重新输入到hash函数中生成hash值，如下图所示：

这个方法确实可以避免碰撞，然而，每次哈希都要查询数据库中是否已经存在short_URL是非常昂贵的。

如果一定要用上述方法，布隆过滤器(bloom filter)是一种高效的空间概率技术，可以提高性能。

Base 62 Conversion(Base62转换)

Base62编码其实很简单，就是62进制，最大能表示627=352161460620862^7=3521614606208(约3521亿)个网址如下所示：

// 62进制 = 10个数字0-9 + 26个大写字母A-Z + 26个小写字母A-Z
private static String chars =  "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

其思想就是说我们抛开long_URL，把目光转向数据库ID，把10进制的数据库ID转为62进制，来作为shory_URL的字符串，其工作原理就是用辗转相除法，如下图所示：

数据库ID是11157,转为62进制变成2TX,那么短链接就是https://tinyurl.com/2TX

那么问题就转变为保证数据库ID唯一----这不就是分布式ID生成器吗？（因此可以参考第7章）

下面这张表是对上述两种方法的优缺点总结：

Hash + collision resolutionBase 62 conversion
短链接长度固定短链接长度不固定
不需要分布式ID生成器依赖于分布式ID生成器
可能发生碰撞不可能发生碰撞，因为ID是唯一的
找出下一个可用的hashValue可能代价高昂找出下一个可用的hashValue很简单，如果设置数据库ID自增1

综上，我们一般采用Base 62 conversion来生成short_URL.

URL Redirecting

由Http协议，URL重定向有两种，301重定向和302重定向:

301 Redirect：301重定向表示短链接对长链接的重定向是永久的，因此浏览器会缓存这个映射，下次在搜索栏输入短链接不会调用URLRedirect(string short_URL)这个API，而是直接根据缓存重定向到长链接。

302 Redirect：302重定向表示短链接对长链接的重定向是临时的，因此浏览器不会缓存这个映射，每次在搜索栏输入短链接都会调用URLRedirect(string short_URL)这个API，然后由服务器返回对应长链接

一般来说，302重定向是更好的选择，因为它能够更容易的跟踪点击率和点击源。

Step3：Design deep dive

URL Shortening deep dive

URL缩短的流程如下：

  1. 用户输入long_URL
  2. 系统检查long_URL是否在数据库中（也可以不检查，直接为相同的长链接生成新的短链接）
  3. 如果存在数据库中，则直接返回数据库中的short_URL
  4. 如果不存在数据库中，则生成一个新的unique 数据库ID。
  5. 使用base62编码将数据库ID转换为short_URL
  6. 使用ID，short_URL，long_URL创建一个新的数据库行，然后存储。

URL Redirecting deep dive

URL重定向的流程如下：

  1. 用户输入short_URL
  2. 负载均衡器将请求转发到web服务器
  3. 如果缓存(Cache)中已经存在shortURL，则直接返回longURL
  4. 如果缓存(Cache)中不存在shortURL，则在数据库中寻找，如果数据库中同样不存在，则很可能是用户输入了无效的shortURL
  5. 返回长链接给用户。

Step4：Warm up

如何设计short_URL过期？

以下引用一个知乎的回答：

这里很容易陷入到“我要怎么把一个长网址转换成一个短网址=>映射=>设计一个hash函数”这样一个误区当中。
如果真要实现这样一个hash算法，那必然是会出现碰撞的，也就是多个长地址转成了同一个短地址，

正确答案是参考分布式ID生成策略，直接使用数据库的自增索引作为短网址发号。

我们并不需要在存储中用62进制，用10进制就好了(10进制也方便统计已使用的短网址个数）。可以在后端做一个10进制到62进制的转换。

我们通过数据库索引自增，实际上是把短网址作为key，长地址作为value，短对长的一种kv存储映射。
如果不判断某个长网址被转换过，直接递增，会造成多个短网址对应一个长网址。

那我再建立长对短的kv存储映射不行吗？可以，但是长对短的kv存储浪费大量空间

可以用一台Redis缓存服务器，存储的不是短网址->长网址，而是长网址->短网址，保存“最近”生成的长对短的一个对应关系。注意是“最近”，也就是说，我并不保存全量的长对短的关系，而只保存最近的。比如采用一小时过期的机制来实现LRU淘汰。

长转短的流程变成这样：

1 在这个Redis缓存服务器的“LRU”表中查看一下，看长地址有没有对应的短地址

​ 1.1 有就直接返回短网址，并且将这个key-value对的过期时间再延长成一小时

​ 1.2 如果没有，就通过发号器生成一个短网址，并且将这个“最近”表中，过期时间为1小时

这样也同时解决了过期策略。

Ref