8. Design A Url Shortener #

设计URL缩短器

我们正在解决一个经典的系统设计问题: 设计一个类似于tinyurl的URL缩短服务。

8.1 第一步: 理解问题并确定设计范围 #

• C：你能举个例子说明URL缩短服务如何工作的吗？
• I：给定URLhttps://www.systeminterview.com/q=chatsystem&c=loggedin&v=v3&l=long和短链接https://tinyurl.com/y7keocwj。如果点击这个短链接，它就可以把你重定向至原URL。
• C：业务量有多大？
• I：每天生成1亿个URL。
• C：缩短后的短链接有多长？
• I：尽可能短。
• C：短链接中允许哪些字符？
• I：数字(0～9)和字母(a～z、A～Z)的组合。
• C：短链接可以被更新或删除吗？
• I：为了简单起见，我们假设他们不能。

其他非功能性需求：高可用性、可扩展性、容错性。

8.1.1 封底估算 #

• 每天1亿个URL -> 每秒约1200个URL。(1亿/24/3600≈1160) -> 每秒写操作数1200次
• 假设读写比为10:1 -> 每秒短读操作数12000次
• 假设URL缩短器将运行10年 -> 我们需要支持3650亿条记录。
• URL平均长度为100个字符 -> 10年的存储量需求为36.5TB (3650亿*100bytes)

8.2 第二步: 提出高层级设计并获得认可 #

8.2.1 API端点 #

我们将创建一个REST API。

URL缩短服务需要两个端点：

• POST /api/v1/data/shorten - 接受长URL并返回短URL。
  • 请求参数：{longUrl：longURLString}。
• GET /api/v1/${shortURL} - 返回给定短URL的长URL，用于http重定向

8.2.2 URL重定向 #

URL重定向的工作原理：

图8.2:

301和302状态码之间的区别是什么？

• 301 (Permanently moved) - 表示URL永久指向新URL。这指示浏览器在后续调用中绕过tinyurl服务。
• 302 (Temporarily moved) - 表示URL暂时移动到新URL。浏览器在将来的调用中不会绕过tinyurl服务。

每种重定向方法都有自己的优缺点:

• 如果降低服务器的负载是首先要考虑的内容，适合使用301重定向
• 如果数据分析很重要，那么302重定向就是更好的选择，因为它可以更轻松地跟踪点击率和点击来源。

实现URL重定向的最简单方法是将<shortURL, longURL>对存储在内存哈希表中。

8.2.3 缩短URL #

为了支持URL缩短，我们需要找到一个合适的哈希函数。

图8.3:

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

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

8.3 第三步: 深入设计 #

我们将探讨数据模型、哈希函数、URL 缩短和重定向。

8.3.1 数据模型 #

在简化版本中，我们将URL存储在哈希表中。这存在问题，因为将会耗尽内存，而且内存中的内容在服务器重新启动后不会保留。

现在我们可以使用一个简单的关系表：

图8.4:

8.3.2 哈希函数 #

哈希值由[0-9a-zA-Z]的字符组成，最多可能包含62种字符。

为了确定合适的哈希值长度，我们需要找到最小的n，使得62的n次幂小于或等于3650亿。

当n=7时，627≈3.5万亿，足够支持3650亿个URL，所以哈希值的长度应该是7位

对于哈希函数，存在hash + collision detection或base62 conversion两种方案。

• hash + collision detection 不推荐
• base62 conversion推荐

Base Conversion(基数转换)是被广泛用于URL缩短器的另一种方法。

Base 62转换是因为一个哈希值中有62种可能的字符。

hash + collision detection(哈希+冲突检测) #

📝 实际中不该推荐此方案

CRC32、MD5 和 SHA-1的哈希值，当以十六进制形式表示时，都只使用以下16种字符组成：

• 数字： 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
• 字母： a, b, c, d, e, f (或 A, B, C, D, E, F，大小写通常不敏感)

这是不满足我们的需求的，我们的需求是哈希值由[0-9a-zA-Z]的字符组成可能包含62种字符。

要用此方案还得把计算出来的十六进制的哈希值，转换成62进制的？

此方案直接使用那些有名的哈希函数，例如CRC32、MD5或者SHA-1等。

在上表格中，即使是最短的哈希值(CRC32算法)都超过7个字符了​。怎么能让它变得短一些呢？

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

这种方法可以消除哈希冲突，但是对每一个请求都要查询数据库以检查是否冲突，这个成本是很高的。一种叫作布隆过滤器的技术可以提升性能。

图8.5:

base62 conversion #

base conversion是URL缩短器常用的另一种方法。base conversion有助于在不同的数字表示系统之间转换相同的数字。使用基数6base62 conversion是因为哈希值有62个可能的字符。

让我们用一个例子来解释转换是如何工作的：将十进制数11157转换为62进制表示。

base62是一种使用62个字符进行编码的方法。映射关系为：0-0，...，9-9，10-a，11-b，...，35-z，36-A，...，61-Z，其中a代表10，Z代表61，等等。

11157 = 2 x 62² + 55 x 62¹ + 59 x 62⁰ = [2, 55, 59] -> base62表示为[2, T, X]

图8.6: 展示的是将十进制数 11157 转换为六十二进制数的过程(除法取余法)

hash + collision detection vs. base62 conversion #

📝 如果新条目的ID递增1，则很容易计算出下一个可用的短链接。这可能是一个安全隐患。

如果ID是连续递增的，那么攻击者可以通过猜测ID来遍历所有短链接，这可能会导致一些安全问题，例如：

• 信息泄露： 如果短链接指向的内容是私密的，攻击者可以通过遍历短链接来获取这些信息。
• 恶意攻击： 攻击者可以利用遍历到的短链接进行恶意攻击，例如DDoS攻击等。

Base62(SnowflakeID)是否可以呢？SnowflakeID也有递增趋势，而且SnowflakeID在理论上也是可以穷举的。

8.3.3 深入URL缩短 #

为了保持我们的服务简单，我们将使用base62编码进行URL缩短。

以下是整个工作流：

图8.7:

为了确保我们的ID生成器在分布式环境中工作，我们可以使用Twitter的雪花算法Snowflake。

8.3.4 深入URL重定向 #

由于读取比写入多，我们引入了一个缓存，以提高读取性能。

图8.8:

• 用户点击短URL
• 负载均衡器将请求转发到其中一个服务实例
• 如果shortURL在缓存中，直接返回longURL
• 否则，从数据库中获取 longURL并存储在缓存中。如果未找到，则短URL不存在

8.4 第四步: 总结 #

我们讨论了API设计、数据模型、哈希函数、URL缩短和URL重定向。

其他要点：

• 限流器：恶意用户发送海量的URL缩短请求是系统可能遇到的一个安全问题。限流器可以帮助我们基于IP地址或者其他过滤条件来拦截请求。
• Web服务器伸缩：因为Web服务层是无状态的，所以很容易通过添加或移除Web服务器来对Web层进行伸缩。
• 数据库扩展：数据库复制和分片是常用的技术。
• 数据分析：对于业务而言，数据变得越来越重要。将数据分析解决方案整合到URL缩短器中可以帮助我们回答一些重要问题，比如“有多少用户点击了一个链接？​”​“他们是什么时候点击的？​”​。
• 可用性、一致性和可靠性。这些概念是所有大型系统成功的关键。

📝 使用场景

微博和Twitter都有字数的限制，如果分享一个长网址，加上文字内容，可能会超出限制。

短信和消息推送中的消息一半也有字数限制。