什么是短网址

缩短的 URL 用于为长 URL 创建较短的别名。我们将这些缩短的别名称为“短链接”

当用户点击这些短链接时，他们会被重定向到原始 URL。短链接可以在显示、打印、消息传递或推特时节省大量空间；此外，用户输入错误短 URL 的可能性也较小。

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

你可以得到：

缩短的 URL 的大小大约是实际 URL 大小的三分之一。

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

那么我们应该如何设计短链接这样的服务呢？喜欢 TinyURL

需求和目标：

首先我们应该从一开始就明确要求，考虑到系统的具体范围。

我们的 URL 缩短系统受一些规则的约束。

功能要求：给定一个 URL，我们的服务应该生成一个较短且唯一的 URL 别名，称为短链接。此链接应该足够短，以便轻松复制并粘贴到应用程序中。当用户访问短链接时，我们的服务应该将他们重定向到原始链接。用户应该能够为其 URL 选择自定义短链接。链接将在默认时间间隔后过期，用户应该能够指定过期时间。非功能性需求：系统应该是高可用的。因为如果我们的服务停止，所有的 URL 重定向都会开始失败。 URL 重定向应该以最小的延迟实时发生。缩短的链接不应该是可猜测的（不可预测的）。扩展要求：分析；例如，发生了多少重定向？我们的服务也应该可以通过 REST api 被其他服务访问。容量估计和约束

与新的 URL 缩短器相比，我们的系统会有很多读取，并且会有很多重定向请求。假设读取与写入的比率为 100:1。

流量估算：假设我们每个月将有 5 亿个新的 URL 缩短器，以 100:1 的读/写比率，我们可以预期在同一时期有 50B 的重定向：

“100 * 500 => 50b”

每秒添加 URL 缩短器：

5 亿/（30 天 * 24 小时 * 3600 秒）= ~200 urls/s

考虑到 100:1 的读/写比率，每秒的 url 重定向为：

100 * 200 网址/秒 = 20K/秒

存储估计：假设我们将每个 URL 缩短请求（和相关的缩短链接）存储 5 年，因为我们预计每月有 5 亿个新 URL，我们预计存储的对象总数将是 300 亿：

5 亿 * 5 年 * 12 个月 = 300 亿

让我们假设每个存储的对象大约是 500 字节（这只是一个粗略的估计 - 我们稍后会深入研究）。我们将需要 15TB 的总存储空间：

300 亿 * 500 字节 = 15tb

带宽估计：对于写入请求，由于我们预计每秒有 200 个新 url，因此我们服务的总传入数据将是每秒 100KB：

200 * 500 字节 = 100kb/s

对于读取请求，由于我们预计每秒有 20K 的 url 重定向，我们服务的总输出数据将是每秒 10MB：

20K * 500 字节 = ~ 10mb/s

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

由于我们每秒有 20,000 个请求，因此我们每天将收到 17 亿个请求：

20K * 3600 秒 * 24 小时 = ~ 17 亿

为了缓存 20% 的这些请求，我们需要 170GB 的内存。

0.2 * 17 亿 * 500 字节 = ~170GB

这里需要注意的一点是，我们的实际内存使用量将小于 170GB，因为会有很多重复请求（相同的 URL）。

高阶估算：假设每月新增 5 亿个 URL，读写比为 100:1，以下是我们服务的高阶估算摘要：

系统接口设计

一旦我们确定了需求，最好定义系统 API，明确声明系统期望什么。

我们可以使用 SOAP 或 REST api 来公开服务的功能。下面是创建和删除url的api定义：

createURL(api_dev_key, original_url, custom_alias=None, user_name=None, expire_date=None)

参数：

api_dev_key（字符串）：注册账户的 API 开发者密钥。这将用于根据分配的配额限制用户；

original_url(string)：要缩短的原始网址；

custom_alias（字符串）：URL 的可选自定义键。

user_name（字符串）：用于编码的可选用户名。

expire_date（字符串）：缩短 URL 的可选到期日期。

returns: (string) 成功插入返回缩短的 URL；否则返回错误码。

删除URL（api_dev_key url_key）

其中“url_key”是一个字符串，表示要检索的缩短网址，删除成功将返回“网址已删除”。

我们如何检测和防止滥用行为？恶意用户是否会通过使用当前设计短链接中的所有 URL 键来耗尽我们的精力？

为了防止滥用，我们可以通过 api_dev_key 限制用户。每个 api_dev_key 可以限制为每个周期创建和重定向的一定数量的 URL（可以为每个用户的密钥设置不同的持续时间）。

数据库设计

在面试早期定义数据库架构将有助于了解不同组件之间的数据流，并指导以后进行数据分区。

关于我们将要存储的数据的性质的一些观察：

我们需要存储数十亿条记录。我们存储的每个对象都很小（小于 1K）。记录之间没有关系——除了存储哪个用户创建了 URL。我们的服务是多读书。数据库结构

我们需要两张表，一张存储有关 URL 映射的信息，另一张存储用于创建短链接的用户数据：

我们应该使用什么样的数据库？由于我们希望存储数十亿行并且我们不需要使用对象之间的关系 - 像 DynamoDB、Cassandra 或 Riak 这样的 NoSQL 存储是更好的选择。

NoSQL 选择也更容易扩展。有关详细信息，请参阅 SQL 与 NoSQL。

系统设计短链接与算法

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

在第 1 节的 TinyURL 示例中，缩写的 URL 是“”。这个 URL 的最后七个字符是我们要生成的短键，我们将在这里探索两种解决方案：

一个。对实际 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 亿个可用字符串，一个 8 个字母长的密钥将产生 64^8 = ~281 万亿个可用字符串。

对于 68.7B 个唯一字符串，我们假设六个字母的密钥对我们的系统来说就足够了。

如果我们使用 MD5 算法作为我们的哈希函数，它将产生一个 128 位的哈希值。经过 base64 编码后，我们最终会得到一个超过 21 个字符的字符串（因为每个 base64 字符编码一个 6 位哈希）。

现在每个快捷键只能容纳 8 个字符，我们如何选择快捷键？我们可以将前 6 个（或 8) 字母）作为键。这会导致密钥重复，为了解决这个问题，我们可以从编码的字符串中选择一些其他字符或交换一些字符。

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

如果多个用户输入相同的 URL，他们可以获得相同的缩短 URL，这是不可接受的。如果 URL 的一部分是 URL 编码的怎么办？例如，除了 URL 编码之外，与 %3Fid%3Ddesign 相同。

问题的解决方法：

我们可以为每个输入的 URL 添加一个递增的序列号，使其唯一，然后生成它的哈希。

但是，我们不需要将此序列号存储在数据库中，这种方法的一个可能问题是序列号不断增加。能溢出吗？增加序列号也会影响服务的性能。

另一种解决方案是将用户ID（应该是唯一的）附加到输入的URL，但是如果用户没有登录，我们必须要求用户选择一个唯一的键。即使在这之后，如果发生冲突，我们也必须不断生成一个密钥，直到我们得到一个唯一的。

b.离线密钥生成

我们可以有一个独立的密钥生成服务 (KGS)，它会在我们想要缩短 URL 时预先生成随机的六字母字符串并将它们存储在数据库中（我们称之为 Key-db）。获取一个已经生成的密钥并使用它。

这种方法将使事情变得非常简单和快速。我们不仅不必对 URL 进行编码，而且不必担心重复或冲突。 KGS 将确保插入到 key-DB 中的所有密钥都是唯一的。

并发会导致问题吗？一旦使用了密钥，就应该在数据库中对其进行标记，以确保它不会被重复使用。如果有多个服务器同时读取key值，我们可能会遇到这样的情况：

两台或多台服务器试图从数据库中读取相同的键值，我们如何解决这个并发问题？

服务器可以使用 KGS 读取/标记数据库中的密钥，而 KGS 可以使用两个表来存储密钥：

一个用于尚未使用的密钥，另一个用于所有已使用的密钥。只要 KGS 为其中一个服务器提供密钥，它就可以将密钥移动到使用的密钥表中。 KGS 可以始终在内存中保留一些密钥，以便在服务器需要它们时快速提供它们。

为简单起见，只要 KGS 将一些键加载到内存中，它就可以将它们移动到已使用的键表中。这样可以确保每个服务器都获得一个唯一的密钥。如果 KGS 在将所有加载的密钥分配给某个服务器之前就死了，我们将浪费这些密钥 - 考虑到我们拥有的密钥数量，这是可以接受的。

KGS 还必须确保不会将相同的密钥提供给多个服务器。为此，它必须同步（或锁定）保存密钥的数据结构，然后从该结构中删除密钥并将它们交给服务器。

key-DB 的大小是多少？使用 base64 编码，我们可以生成 68.7B 个唯一的 6 字母密钥。如果我们需要一个字节来存储字母数字字符，我们可以将所有这些键存储在：

6 个字符（每个键）* 68.7B（唯一键）= 412 GB。

KGS 不是单点故障吗？是的。

为了解决这个问题，我们可以设置一个KGS的备份副本，它可以在主服务器出现故障时接管生成并提供密钥。

每个应用服务器可以在 key-DB 中缓存一些键吗？是的，这肯定会加快速度。虽然在这个例子中，如果应用服务器在所有密钥都用完之前就死掉了，我们最终会丢失这些密钥。这是可以接受的，因为我们只有 68B 的六个字母的密钥。

如何执行密钥查找？我们可以在数据库中查找密钥以获取完整的 URL。如果它出现在数据库中，则向浏览器发出“HTTP 302 重定向”状态，并在请求的“位置”字段中传递存储的 URL。如果我们的系统中不存在该密钥，则发出“HTTP 404 not Found”状态或将用户重定向回主页。

我们应该对自定义别名施加大小限制吗？我们的服务支持自定义别名。用户可以选择他们喜欢的任何“键”，但提供自定义别名不是强制性的。

但是，对自定义别名施加大小限制是合理的（并且通常是可取的），以确保我们拥有一致的 URL 数据库。假设用户可以为每个客户键指定最多 16 个字符（如上面的数据库架构所示）：

数据分区和复制

为了扩展我们的数据库，我们需要对其进行分区，以便它可以存储有关数十亿个 URL 的信息。我们需要想出一个分区方案来将我们的数据划分并存储到不同的数据库服务器中。

一个。基于范围的分区

我们可以根据哈希键的第一个字母将 url 存储在单独的分区中。因此，我们将所有以字母“A”（和“A”）开头的 url 保存在一个分区中，将那些以字母“B”开头的 URL 保存在另一个分区中，依此类推。这种方法称为基于范围的分区。

我们甚至可以将某些不太频繁出现的字母组合到一个数据库分区中。我们应该提出一个静态分区方案，这样我们就可以始终以可预测的方式存储/查找 URL。

这种方法的主要问题是：它可能导致数据库服务器不平衡。

例如，我们决定将所有以字母“E”开头的 url 放入一个 DB 分区，但后来我们意识到我们有太多以字母“E”开头的 url。

b.基于哈希的分区

在这个方案中，我们获取存储对象的哈希值，然后根据哈希值计算出使用哪个分区。

在本例中，我们可以通过“key”或短链接的哈希值来确定数据对象存储的分区。

我们的散列函数将随机分配 url 到不同的分区（例如，我们的散列函数总是可以将任何“键”映射到 [1...256] 之间的数字），而这个数字将代表我们存储我们的对象。

这种方法仍然会导致分区过载，可以通过使用一致性哈希来解决。

缓存

我们可以缓存经常访问的 url。我们可以使用一些现成的解决方案，例如：

Memcached，它可以存储完整的 url 及其各自的哈希值。应用服务器可以在访问后端存储之前快速检查缓存是否具有所需的 URL。

我们应该有多少缓存内存？我们可以从每天 20% 的流量开始，根据客户的使用模式，我们可以调整需要多少缓存服务器。

如上所述，我们需要 170GB 的 RAM 来缓存 20% 的日常流量。由于今天的服务器可以拥有 256GB 的内存，我们可以轻松地将所有缓存放入一台机器中。或者短链接失效，我们可以使用几个较小的服务器来存储所有这些热门 url。

哪种缓存驱逐策略最适合我们的需求？当缓存已满，我们想用较新/较热的 URL 替换链接时，我们应该如何选择？最近最少使用 (LRU) 我们系统的合理策略。

根据此政策短链接失效，我们会首先丢弃最近最少使用的网址。我们可以使用链接 hashmap 或类似的数据结构来存储我们的 url 和哈希表，这也将跟踪最近访问的 url。

为了进一步提高效率，我们可以复制缓存服务器以在它们之间分配负载。

如何更新每个缓存副本？每当缓存未命中时，我们的服务器就会访问后端数据库，每当发生这种情况时，我们都可以更新缓存并将新条目传递给所有缓存副本，每次每个副本都可以通过添加新条目来更新其缓存。

如果副本已经拥有该条目需求解决方案:如何设计短链接短url地址服务？，则可以忽略它。

负载平衡

我们可以在系统的三个地方添加负载均衡层：

在客户端和应用服务器之间，在应用服务器和数据库服务器之间，在应用服务器和缓存服务器之间。

最初，我们可以使用简单的循环方法在后端服务器之间平均分配传入请求。这个 LB 实现简单，不会引入任何开销。这种方法的另一个好处是，如果服务器死机，LB 会停止轮换并停止向其发送任何流量。

Round Robin LB 的一个问题是我们没有考虑服务器负载。如果服务器负载过重或运行缓慢，LB 不会停止向该服务器发送新请求。

为了解决这个问题，可以放置一个更智能的负载均衡解决方案，定期查询后端服务器的负载并相应地调整流量。

清除或数据库清理

该条目应该永远存在还是应该被清除？如果达到用户指定的过期时间，链接会发生什么情况？

如果我们选择主动搜索过期链接并删除它们，这会给我们的数据库带来很大的压力。取而代之的是，我们可以慢慢删除过期链接，懒惰地清理。我们的服务将确保只删除过期的链接短链接失效，虽然有些过期的链接可以存活更长的时间但永远不会返回给用户。

当用户尝试访问过期链接时，我们可以删除该链接并向用户返回错误。可以定期运行单独的清理服务，以从我们的存储和缓存中删除过期链接。该服务应该是非常轻量级的，并且应该只在预计用户流量较低时运行。

我们可以为每个链接设置一个默认的过期时间（例如两年）。

删除过期链接后，我们可以将密钥放回key-db中以供重复使用。

我们应该删除一段时间（比如 6 个月）未访问过的链接吗？这可能很棘手。随着存储越来越便宜，我们可以决定永远保持联系。

特殊场景注意事项

短网址使用了多少次，用户所在位置等？我们如何存储这些统计数据？如果是在每个视图上更新的 DB 行的一部分，当一个流行的 URL 被大量并发请求攻击时会发生什么？

一些值得跟踪的统计数据：访问者所在的国家/地区、访问日期和时间、点击的页面、浏览器或访问页面的平台。

安全和权限

用户能否创建私有 URL 或允许特定用户组访问 URL？

我们可以在数据库中存储每个 URL 的权限级别（公共/私有）。我们还可以创建一个单独的表来存储有权查看特定 URL 的用户 ID。如果用户没有权限并尝试访问该 URL，我们可以返回一个错误（HTTP 40 1).

假设我们将数据存储在像 Cassandra 这样的 NoSQL 宽列数据库中，表存储权限的键将是“哈希”（或 KGS 生成的“键”）。这些列将存储那些有权查看 URL 的用户的用户 ID。

以上就是关于《需求解决方案：如何设计短链接url？》的全部内容了，感兴趣的话可以点击右侧直接使用哦！》》在线短链接生成器