当前位置：首页 > news >正文

面试场景题系列：设计URL短链

news 来源：原创 2025/7/27 5:00:42

1.场景需求界定

1.缩短URL：提供一个长URL，返回一个短很多的URL。

2.重定向URL：提供一个缩短了的URL，重定向到原URL。

3.高可用、可扩展性和容错性考量。

•写操作：每天生成1亿个URL。

•每秒的写操作数：1亿÷24÷3600≈1160。

•每秒的读操作数：假设读操作与写操作的比例是10∶1，那么每秒的读操作数是1160×10=11，600。

•假设URL缩短器会运行10年，这意味着我们必须支持1亿×365×10=3650亿条记录。

•假设URL的平均长度是100个字符，那么10年的存储容量需求是：3650亿×100字节≈36.5TB。

2.顶层设计

在这一节，我们将讨论API端点、URL重定向和URL缩短的相关流程。

2.1 API端点

API端点有利于客户端和服务器之间的通信。我们会把API设计成REST风格。如果你不熟悉REST风格的API，可以参阅一些文章，比如RestapiTutorial网站上的文章。一个URL缩短器主要需要两个API端点。

1.缩短URL。为了创建一个短URL，客户端会发送一个POST请求，它包含一个参数——原始的长URL。API看起来像下面这样：

POST api/v1/data/shorten

•请求参数：{longUrl：longURLString}。

•返回短URL。

2.重定向URL。为了把短URL重定向到对应的长URL，客户端会发送GET请求。API看起来像下面这样：

POST api/v1/shorturl

返回长URL以进行HTTP重定向。

2.2 URL重定向

图-1展示了当你在浏览器中输入一个经过缩短的TinyURL网址时会发生什么。

一旦服务器收到一个TinyURL请求，就会通过301重定向把短URL换成长URL。

客户端和服务器之间的详细通信信息如图-2所示。

图-2

**301重定向：**意味着所请求的URL“永久”移动到长URL。因为是永久重定向，所以浏览器会缓存该响应，以后对同一个URL的请求就不会发给URL缩短服务器了，而会将其直接重定向到长URL服务器。

**302重定向：**意味着URL“暂时”移动到长URL，这也意味着对于同一个URL的后续请求会先发给URL缩短服务器，然后它们才会被重定向到长URL服务器。

每种重定向方法都有自己的优缺点。如果降低服务器的负载是需要优先考虑的事项，使用301重定向就是合适的，因为对于同一个URL只有第一次请求会被发到URL缩短服务器上。但是如果数据分析很重要，那么302重定向就是更好的选择，因为它可以更轻松地跟踪点击率和点击来源。

实现URL重定向的最直观的方法就是使用哈希表。假设哈希表存储了<shortURL，longURL＞键值对，可以通过以下步骤实现URL重定向。

•获取长URL：longURL=hashTable.get(shortURL)。

•一旦获取了长URL，就实施URL重定向。

2.3 缩短URL

我们假设短URL的格式为：www.tinyurl.com/{hashValue}。为了支持URL缩短的使用场景，我们必须找到一个哈希函数fx，它可以把长URL(longURL)映射成哈希值，如图-3所示。

图-3

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

•每个长URL必须可以通过哈希函数转换成一个哈希值(hashValue)。

•每个哈希值可以被映射回原始的长URL。

我们将在第3节探讨哈希函数的详细设计。

3. 设计继续深入

到目前为止，我们讨论了URL缩短和URL重定向的高层级设计。在本节中，我们会深入探讨以下内容：数据模型、哈希函数、URL缩短和URL重定向。

3.1 数据模型

在高层级设计中，所有的数据都被存储在哈希表中。这是一个很好的起点，但是在现实世界中内存资源是有限且昂贵的，因此这个方法并不可行。更好的选择是在关系型数据库中存储

图-4

3.2 哈希函数

哈希函数用于将长URL哈希成短URL，这个短URL也叫作哈希值(hashValue)。

哈希值的长度

哈希值由数字(0～9)和字母(a～z、A～Z)组成，包含62种可能的字符（10个数字+26个小写字母+26个大写字母=62）。为了确定合适的哈希值长度，我们需要找到最小的n，使得62的n次幂小于或等于3650亿。根据之前的估算，系统需要支持高达3650亿个URL。表8-1展示了随n的变化其对应支持的最大URL数量。

表-1

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

我们会探讨两种用于URL缩短器的哈希函数。第一种是“哈希+解决冲突”，第二种是“Base 62转换”。下面我们逐一来看一下。

为了缩短一个长URL，我们需要实现一个哈希函数将长URL哈希成7个字符的字符串。最直接的解决方案是使用那些有名的哈希函数，比如CRC32、MD5或者SHA-1等。下面的表8-2比较了对长URL“https://en.wikipedia.org/wiki/Systems_design”使用不同哈希函数的结果。

表-2

如表-2所示，即使是最短的哈希值（通过CRC32算法得到）都太长了（超过7个字符）。怎么能让它变得短一些呢？第一个方法是取哈希值的前7个字符，但是这个方法会导致哈希冲突(Hash Collision)。

为了解决哈希冲突，我们可以递归地添加一个新的预先设定好的字符串，直到不再发现冲突为止。图-5解释了这个过程。

图-5

这个方法可以消除哈希冲突，但是对每一个请求都要查询数据库以检查是否存在对应的短URL，这个成本是很高的。一种叫作布隆过滤器的技术可以提升性能。布隆过滤器是一种高效利用空间的概率性技术，可以用来检测一个元素是否属于某个集合。参考维基百科中“Bloom Filter”词条的相关介绍，可以了解更多细节。

Base 62转换

基数转换(Base Conversion)是被广泛用于URL缩短器的另一种方法。基数转换可以将同一个数字在不同的数值表示系统之间进行转换。用Base 62转换是因为一个哈希值中有62种可能的字符。下面用一个例子来解释如何进行转换：把1115710转换成Base 62的表示（1115710表示的是十进制数11，157）。

•从名字可以看出，Base 62是一种使用62个字符来进行编码的方式。其映射关系为：0→0，…，9→9，10→a，11→b，…，35→z，36→A，…，61→Z，其中“a”代表10，“Z”代表61，依此类推。

•1115710=2×622+55×621+59×620=[2，55，59]，转换为Base 62的表示就是[2，T，X]。图-6展示了转换过程。•因此，短URL就是https://tinyurl.com/2TX。

图-6

表-3展示了两种方法的不同点。

表-3

3.3 深入探讨URL缩短流程

作为系统的核心组成部分之一，UR L缩短流程应该是逻辑简单的，而且能提供我们想要的功能。在我们的设计里使用了Base 62转换。图-7展现了这个流程。

1.长URL是输入。

2.系统检查数据库中是否有这个长URL。

3.如果有，则意味着这个长URL此前曾经被转换为短URL。在这种情况下，从数据库中获取短URL并返回给客户端。

4.如果没有，则说明这是一个新的长URL。系统通过唯一ID生成器生成新的唯一ID（主键）。5.采用Base 62转换把这个ID转换成短URL。

6.创建一个新的数据库记录，其中包含ID、短URL和长URL。

为了更好地理解这个流程，我们来看一个具体的示例。

•假设输入的长URL是https://en.wikipedia.org/wiki/Systems_design。

•唯一ID生成器返回的ID为2009215674938。

•用Base 62转换把ID转成短URL，即ID(2009215674938)被转换成“zn9edcu”。

•将ID、短URL和长URL保存到数据库，如表-4所示。

这里，分布式唯一ID生成器值得一提。它主要的功能是生成全局唯一的ID，这个ID被用来创建短URL。在高度分布式的环境中，实现唯一ID生成器是很有挑战性的。

3.4 深入探讨URL重定向流程

图-8展示了URL重定向的详细设计。因为读操作远多于写操作，所以

图-8

URL重定向的流程总结如下：

1.用户点击一个短URL“https://tinyurl.com/zn9edcu”。

2.负载均衡器将请求转发给Web服务器。

3.如果短URL已经在缓存中，则直接返回对应的长URL。

4.如果短URL不在缓存中，则从数据库中获取对应的长URL；如果这个短URL不在数据库中，那么有可能用户输入了无效的短URL。

5.将长URL返回给用户。

4 总结

在本文中，我们讨论了API设计、数据模型、哈希函数、URL缩短和URL重定向。如果在面试的最后还有多余的时间，以下是一些可以讨论的议题。

•限流器：恶意用户发送海量的URL缩短请求是系统可能遇到的一个安全问题。限流器可以帮助我们基于IP地址或者其他过滤条件来拦截请求。如果你想回顾关于流量限制的知识，可以参考第4章。

•Web服务器伸缩：因为网络层是无状态的，所以很容易通过添加或移除Web服务器来对网络层进行伸缩。

•数据库扩展：数据库复制和分片是常用的技术。

•数据分析：对于业务而言，数据变得越来越重要。将数据分析解决方案整合到URL缩短器中可以帮助我们回答一些重要问题，比如“有多少用户点击了一个链接？”“他们是什么时候点击的？”。•可用性、一致性和可靠性。这些概念是所有大型系统成功的关键。我们在第1章中详细讨论过它们，请回顾这些内容。