一篇文章讲完URL缩短服务的所有内容

我们将设计一个类似TinyURL的URL缩短服务。此服务将提供用于重定向到长URL的短别名。

类似的服务有：bit.ly，goo.gl，qlink.me等。

难度等级：简单

1. 为什么我们需要URL缩短？

URL缩短用于为长URL创建更短的别名。我们称这些缩短的别名为“短链接”。当用户点击这些短链接时，他们将被重定向到原始URL。短链接在显示、打印、信息传递或推文时可以节省大量空间。此外，用户不太可能错误输入更短的URL。

例如，如果我们通过TinyURL缩短此页面：

https://www.educative.io/collection/page/5668639101419520/5668600916475904/

我们会得到：

http://tinyurl.com/jlg8zpc

缩短后的URL几乎只有实际URL大小的三分之一。

URL缩短用于优化跨设备的链接，跟踪单个链接以分析受众和活动表现，并隐藏关联的原始URL。

如果您以前没有使用过tinyurl.com，请尝试创建一个新的缩短URL，并花些时间浏览他们服务提供的各种选项。这将对您理解这一章节非常有帮助。

2. 系统的需求和目标

💡在面试开始时，您应该始终明确需求。一定要提问，以找出面试官心中的系统的确切范围。

我们的URL缩短系统应满足以下要求：

功能需求：

1. 1. 我们的服务应该能为给定的URL生成一个更短且唯一的别名。这就是我们所说的短链接。

2. 2. 当用户访问一个短链接时，我们的服务应该将他们重定向到原始链接。

3. 3. 用户应该可以选择为他们的URL选择一个自定义的短链接。

4. 4. 链接将在标准的默认时间跨度后过期。用户应该能够指定过期时间。

非功能性需求：

1. 1. 系统应高度可用。这是必要的，因为如果我们的服务停止，所有的URL重定向将开始失败。

2. 2. URL重定向应该实时进行，延迟最小。

3. 3. 缩短的链接不应该能被猜测出来（不可预测）。

扩展需求：

1. 1. 分析；例如，重定向发生了多少次？

2. 2. 我们的服务也应通过REST API供其他服务访问。

3. 容量估计和约束

我们的系统将主要读取数据。与新的URL缩短相比，将会有大量的重定向请求。让我们假设读取和写入的比例为100:1。

流量估计：假设，我们每个月将有5亿个新的URL缩短，以100:1的读写比例，我们预计在同一期间将会有5000亿次重定向：100 * 500M => 50B mathematica

那么我们的系统每秒的查询次数（QPS）是多少？每秒新URL缩短的数量：500 million / (30 days * 24 hours * 3600 seconds) = ~200 URLs/s makefile

考虑到100:1的读写比例，每秒的URL重定向数量将是：100 * 200 URLs/s = 20K/s mathematica

存储估计：假设我们将每个URL缩短请求（以及关联的缩短链接）存储5年。由于我们预计每月将有5亿个新的URL，所以我们预计要存储的对象总数``` 将是300亿：500 million * 5 years * 12 months = 30 billion

假设每个存储对象大约是500字节（只是一个大概的估计-我们稍后会深入研究）。我们需要15TB的总存储空间：30 billion * 500 bytes = 15 TB bash

image-20230710211822099

带宽估计：对于写请求，由于我们预计每秒有200个新的URL，我们的服务的总入站数据将是每秒100KB：200 * 500 bytes = 100 KB/s mathematica

对于读请求，由于我们预计每秒将有~20K个URL重定向，我们的服务的总出站数据将是每秒10MB：20K * 500 bytes = ~10 MB/s mathematica

内存估计：如果我们想要缓存一些经常访问的热门URL，我们需要多少内存来存储它们？如果我们遵循80-20的规则，即20%的URL产生80%的流量，我们希望缓存这20%的热门URL。

由于我们每秒有20K的请求，我们每天将接收到17亿的请求：20K * 3600 seconds * 24 hours = ~1.7 billion

为了缓存这20%的请求，我们将需要170GB的内存。0.2 * 1.7 billion * 500 bytes = ~170GB mathematica

需要注意的一点是，由于会有很多重复的请求（同一个URL），因此我们实际的内存使用将少于170GB。

高级估计：假设每月有5亿个新的URL并且读写比为100:1，以下是我们服务的高级估计总结：新URL 200/s

URL重定向 20K/s

入站数据 100KB/s

出站数据 10MB/s

5年的存储量 15TB

缓存的内存 170GB mathematica

4. 系统API

💡一旦我们确定了需求，定义系统API总是一个好主意。这应该明确地说明系统应期望的情况。

我们可以有SOAP或REST API来公开我们服务的功能。以下是创建和删除URL的API的定义：

image-20230710211909058

参数：api_dev_key (string)：已注册帐户的API开发者密钥。这将用于基于他们的配额进行限制用户等其他事情。original_url (string)：需要被缩短的原始URL。custom_alias (string)：URL的可选自定义关键字。user_name (string)：用于编码的可选用户名。expire_date (string)：缩短URL的可选过期日期。

返回：（字符串） 成功插入返回缩短的URL；否则，返回错误代码。

image-20230710211921734

其中“url_key”是表示要检索的缩短URL的字符串。成功删除返回'URL Removed'。

我们如何检测和防止滥用？恶意用户可以通过消耗当前设计中的所有URL键使我们破产。为了防止滥用，我们可以通过他们的api_dev_key来限制用户。每个api_dev_key可以限制在某个时间段内的URL创建和重定向的数量（每个开发者键可能设置不同的持续时间）。

5. 数据库设计

💡 在面试的早期阶段定义数据库模式将有助于理解各个组件之间的数据流，并会在后期指导数据划分。我们将存储的数据的一些特性：

1. 1. 我们需要存储数十亿的记录。

2. 2. 我们存储的每个对象都很小（小于1K）。

3. 3. 记录之间没有关系 —— 除了存储哪个用户创建了一个URL。

4. 4. 我们的服务读取重。

数据库模式：

image-20230710212000548

我们需要两个表：一个用于存储URL映射信息的表，和一个用于存储创建短链接的用户数据的表。

我们应该使用哪种类型的数据库？由于我们预计将存储数十亿行数据，而且我们不需要使用对象之间的关系 —— 一个NoSQL键-值存储，如DynamoDB、Cassandra或Riak，将是更好的选择。NoSQL选择也将更容易扩展。更多细节请参见 SQL vs NoSQL。

6. 基础系统设计和算法

我们在这里要解决的问题是，如何为给定的URL生成一个短且唯一的键。

在第1节的TinyURL示例中，缩短的URL是“http://tinyurl.com/jlg8zpc”。这个URL的最后六个字符就是我们要生成的短键。我们将在这里探索两种解决方案：

a. 编码实际URL

我们可以计算给定URL的唯一哈希（例如，MD5或SHA256等）。然后可以显示这个哈希的编码。这个编码可以是base36（[a-z ,0-9]）或base62（[A-Z, a-z, 0-9]），如果我们添加'-'和'.'我们可以使用base64编码。一个合理的问题是，短键的长度应该是多少？6、8还是10个字符。

使用base64编码，一个6个字母长的键将产生64^6 = ~687亿可能的字符串。

使用base64编码，一个8个字母长的键将产生64^8 = ~281万亿可能的字符串。

以68.7B个独特的字符串为例，我们假设我们的系统中六个字母的键应该足够了。

如果我们使用MD5算法作为我们的哈希函数，它将产生一个128位的哈希值。经过base64编码后，我们将得到一个超过21个字符的字符串（因为每个base64字符编码了哈希值的6位）。因为我们每个短键只有8个字符的空间，那么我们应该如何选择我们的键呢？我们可以取前6个（或8个）字母作为键。这可能会导致键的重复，在这种情况下，我们可以选择编码字符串中的其他字符或交换一些字符。

我们的解决方案有哪些不同的问题？我们的编码方案有以下几个问题：

1. 1. 如果多个用户输入相同的URL，他们可能会得到相同的缩短URL，这是不可接受的。

2. 2. 如果URL的部分被URL编码了怎么办？例如，http://www.educative.io/distributed.php?id=design, 和 http://www.educative.io/distributed.php%3Fid%3Ddesign 除了URL编码之外是相同的。

解决问题的方法：我们可以在每个输入URL后面添加一个递增的序列号，使其变得独特，然后生成它的哈希。虽然我们不需要在数据库中存储这个序列号。这种方法可能的问题```

7. 数据分区和复制

我们需要对我们的数据进行分区，以便有效地管理数十亿条URL记录。为了达到这个目标，我们需要对我们的数据进行分区，以便能够存储和处理巨大的URL记录。以下是一些常用的分区方法：

• • 分区的基础上，是基于哈希的键。在这种方案中，我们取每个URL的哈希，然后用哈希值的一部分来确定它应该放置在哪个分区/桶中。我们可以按顺序存储新的URL，并保持URL的有序性。我们可以使用哈希值的一部分（由分区键决定）作为我们的查找键。

• • 基于范围的分区：在这种策略下，范围内的所有键都将存储在一个分区中。如果我们按照URL的字母顺序存储，那么所有以‘A’开头的URL可以放在一个分区中，以‘B’开头的在另一个分区中，依此类推。这将有助于快速查找给定范围内的所有URL。

复制方法：我们需要进行数据复制以确保可用性和数据持久性。我们可以为每个分区创建多个副本，并将它们存储在不同的服务器上。我们的服务始终应该为所有读写操作选择一个主副本，并将其更改复制到其他所有副本。如果主副本死机，服务可以从任何健康的副本中选择一个新的主副本。

8. 缓存

我们的服务将是读取密集，所以我们可以利用内存缓存来提高查找速度。在最初的设计中，我们可以采用简单的解决方案，例如使用一个LRU缓存，其中最近/最常访问的URL将被保留在内存中，并且将很快提供给调用者。我们可以使用像Memcached这样的缓存来保存最常访问的URL和它们的短链接。

缓存大小：如果我们假设我们的短链接平均有6个字符，如果我们假设它们是base64编码的，那么它们需要6*8=48bits。如果我们需要支持500M个这样的链接，那么我们需要30GB的内存。由于我们也需要存储原始URL和访问时间戳等元数据，所以我们可能会需要更多的内存。

缓存策略：我们将采用LRU策略来替换不常访问的链接。

9. 负载均衡 (LB)

我们可以在几个地方添加负载均衡器以分散来自用户的请求流：

• • 在DNS级别：我们的DNS服务器可以轮询将一个新请求转发到我们的不同高级负载均衡器。我们也可以将用户请求分布到离用户最近的地区。

• • 在服务器级别：我们的高级负载均衡器可以将请求分布到底层的服务器。

• • 在数据库级别：如果我们假设我们有多个数据库副本（主/从设置），LB可以将读流量分散到所有从服务器上。写请求将直接发送到主服务器。

10. 故障恢复和备份

如果我们的主数据库出现问题，我们的复制方案将确保我们的系统不会丢失任何数据。一旦主数据库恢复健康，系统将应用所有挂起的操作以使主数据库与其他副本同步。

我们可以通过定期备份数据来进一步确保数据安全。对于备份，我们可以使用各种策略，比如每天一次全备份，然后每6小时一次增量备份。```

11. 数据复制和冗余

为了增加数据的可靠性和可用性，我们应该在多个地点复制和存储我们的数据。我们可以复制每个分区到多个服务器。这将确保即使出现硬件故障，我们的服务也将保持可用。

我们应该在哪里复制和存储数据？

a. 同一数据中心内的不同机架上 b. 不同数据中心内 c. 不同地理位置的数据中心

所有写操作都应写入原始分区以及其所有副本。在读取时，可以从任何副本读取。这将在我们的系统中引入一定的复杂性，因为我们现在需要处理复制延迟和数据版本问题。

12. 故障恢复

在硬件故障或其他严重问题的情况下，我们需要有备份策略来恢复我们的服务。

a. 如果我们的主数据库发生故障，我们需要从备份中立即恢复。我们可以使用我们的副本来提供服务，直到主数据库恢复。

b. 如果我们的缓存服务器发生故障，我们的服务将受到影响，但不会完全中断。我们需要立即替换缓存服务器。

13. 安全

我们的系统应该能够防止诸如DDoS攻击、SQL注入等安全威胁。因此，我们需要为这些可能的攻击配置适当的防御措施。

14. 监控

我们需要监控我们的系统以了解其健康状况。如果我们的服务在响应用户请求时出现故障或延迟，我们应该能够快速发现。我们可以收集详细的日志来帮助我们了解问题，以及如何在未来避免这些问题。

15. 容量规划和扩展

我们应该定期进行容量规划，以预测何时增加更多硬件以支持我们的业务。当业务增长时，我们需要更多的服务器来提供服务。

我们的服务应该能够轻松扩展以处理更多的流量。这可能意味着添加更多的应用服务器、数据库服务器或缓存服务器。在设计我们的系统时，我们应考虑到这一点。

我们的数据库设计应该能够轻松地扩展到更多的机器上。我们可能需要更改我们的数据库架构或者迁移到更大的机器上。

在大多数情况下，我们需要为我们的服务添加更多的硬件，以便它们可以处理更多的流量。我们的系统应该能够在没有任何停机时间的情况下添加或删除硬件。

为了达到这个目标，我们的系统应该是无状态的，这样我们就可以轻松地添加或删除服务器。无状态意味着每个请求都可以由任何服务器处理，而无需关心该请求是在哪个服务器上发起的。