URL缩短器

理解问题

假设 https://www.systeminterview.com/q=chatsystem&c=loggedin&v=v3＆l=long 是原 URL, 你的服务应该可以创建一个更短的 URL （短链接） : https://tinyurl.com/y7keocwj, 将其作为原 URL 的别名。 如果点击这个短链接，它就可以把你重新导向至原URL。

1. 缩短URL：提供一个长URL，返回一个短很多的URL
2. 重定向URL：提供一个缩短了的URL，重定向到原URL
3. 高可用、可扩展性和容错性考量

封底估算

• 写操作，每天生成1亿个URL
• 每秒的写操作数，1160
• 每秒的读操作，假设读操作与写操作的比例为10:1，每秒的读操作数是11600
• 假设URL缩短器会运行10年，意味着必须支持3650亿条记录
• 假设URL的平均长度100个字符，10年的存储容量需求是36.5TB

API 端点

API 端点有利于客户端和服务器之间的通信，把API设计成REST风格。一个URL缩短器主要需要两个API端点：

1. 缩短 URL 。为 了创 建 一个短 URL, 客户端会发送一个 POST 请求，它包含 一个参数——原始的长 URL 。 API 看起来像下面这样：POST api/v1/data/shorten 请求参数 {longUrl: longURLString} 返回短URL
2. 重定向URL，为了把短 URL 重定 向到对应 的 长 URL, 客户端会发送 GET 请求。GET api/v1/shortURL 返回长URL以进行HTTP重定向

URL 重定向

当在浏览器输入经过缩短的TinyURL网址时，服务器收到一个TinyURL请求，会通过301重定向把短URL换成长URL。

301重定向和302重定向区别：

1. 301重定向：意味着所请求 的 URL“ 永久“移动到长 URL 。因为是永久重定向 ，所以浏览器会缓存该响应，以后对同一个 URL 的请求就不会发给 URL 缩短服务器了，而会将其直接重定向到长 URL 服务器。
2. 302重定向：意味着 URL“ 暂时“移动到长 URL ，这也意味着对 千同一 个 URL 的后续请求会先发给 URL 缩短服务器，然后它们才会被重定向到长 URL 服务器。

缩短 URL

假设短URL的格式为 www.tinyurl.com/{hashValue}

这个哈希函数必须满足下面的要求：

1. 每个长URL必须可以通过哈希函数转换成一个哈希值
2. 每个哈希值可以被映射回原始的长URL

数据模型

高层级设计中，所有数据都被存储在哈希表中，但是现实世界内存资源是有限且昂贵的，因此方法不可行。

可以选择关系型数据库中存储 <shortURL, longURL>，例如简化版的表包含3列： id、shortURL、longURL。

哈希函数

哈希函数用于将长URL哈希成短URL，这个短URL也叫做哈希值。

哈希值的长度：由数字字母，10+26+26=62 种可能的字符，

哈希解决冲突

需要实现一个哈希函数将长URL哈希成7个字符的字符串，最直接的解决方法是使用那些有名的哈希函数，如 CRC32、MD5、SHA-1等。

但是哈希值都太长了。

第一个办法是取哈希值的前7个字符，但这个方法会导致哈希冲突。为了解决哈希冲突，可以 递归地添加一个新的预先设定好的字符串，直到不再发现冲突为止。

可以消除哈希冲突，但对每个请求都要查询数据库检查是否已经存在，成本很高。

布隆过滤器可以提升性能，是一种高效利用空间的概率性技术，可以用来检测一个元素 是否属于某个集合。

Base 62 转换

例如吧 十进制数字 11157 转换为 Base62 的表示：

• Base62使用62个字符进行编码，映射关系 0->0...9->9 10->a...35->z 36->A 61->Z
• 转换后的标识 https://tinyurl.com/2TX

URL 缩短流程

URL 缩短流程应该是逻辑简单的，而且能提供我们想要的功能：

利用缓存提高性能

URL 重定向的详细设计，因为读操作远多于写操作，所以 <shortURL, longURL> 映射关系被存储在缓存中以提高性能

URL 重定向流程总结：

1. 用户点击一个短URL https://tinyurl.com/zn9edcu
2. 负载均衡器将请求转发给Web服务器
3. 如果短URL已经在缓存中，则直接返回对应的长URL
4. 如果短URL不在缓存中，则从数据库中获取对应的长URL，如果这个短URL不在数据库中，那么有可能用户输入了无效的短URL
5. 将长URL返回给用户