系统设计实践 (01) - 短链服务

前言

系统设计实践篇的文章将会根据《系统设计面试的万金油》^[1]为前置模板，讲解数十个常见系统的设计思路。

设计目标

设计一个像TinyURL^[2]这样的URL缩短服务。该服务将提供一个较短的URL，重定向到原本长的URL。

一. 为什么我们需要URL短链

URL 缩短用于为长 URL 创建更短的别名。我们称这些缩短的别名为短链接。当用户点击这些短链接时，它们会被重定向到原始URL。短链接在展示、打印、发送或发推时可以节省大量空间，而且便于用户手动输入。

例如，如果我们通过 TinyURL 缩短这个 URL

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

可以得到:

http://tinyurl.com/jlg8zpc

缩短后的网址几乎是实际网址的三分之一大小。

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

如果您以前没有使用过tinyurl.com，请尝试创建一个新的短网址，并花一些时间浏览他们提供的各种服务选项，对你理解有很大帮助。

二. 系统的需求与目标

你应该在面试一开始就明确需求。一定要问问题，找出面试官脑海中系统的确切范围。

我们的网址缩短系统应该满足以下要求:

功能性需求:

•给定一个URL，我们的服务应该生成一个更短且唯一的别名。•当用户访问一个短链接时，我们的服务应该将他们重定向到原始链接。•用户应该能够选择一个自定义的短链接为他们的URL。•链接将在标准的默认时间间隔之后过期。用户应该能够指定过期时间。

非功能性需求:

•系统应该是高度可用的。这是必须的，因为如果我们的服务停止，所有的URL重定向将开始失败。•URL重定向应该实时发生，延迟最小。•缩短的链接不应该是可猜测的(不可预测的)。

扩展性需求:

•分析: 例如，发生了多少次重定向?•我们的服务也应该可以通过 REST API 被其他服务访问。

三. 容量估算与约束

短链系统从请求读写量上来说，属于是读取量很大的。与缩短一个URL相比，访问短链将会有大量的重定向请求。可以假设读和写的比率是100:1。

流量估算

假设我们每个月有 500M 的新 URL 缩短，读/写比为 100:1，我们可以预期在同一时期有 50B 的重定向。

100 * 500M => 50B

我们系统的每秒查询(QPS)是多少?

500 million / (30 days * 24 hours * 3600 seconds) = ~200 URLs/s

考虑到 100:1 的读/写比率，每秒 URL 重定向将是：

100 * 200 URLs/s = 20K/s

存储估计

假设我们将每个URL目标链接(以及相关的缩短链接)存储5年。因为我们预计每个月有5亿个新url，所以我们预计存储的对象总数将达到300亿个

500 million * 5 years * 12 months = 30 billion

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

带宽估计

对于写请求，由于我们预计每秒有200个新url，所以我们服务的总传入数据将是每秒100KB

200 * 500 bytes = 100 KB/s

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

20K * 500 bytes = ~10 MB/s

内存估计

如果我们想缓存一些经常被访问的热点url，我们需要多少内存来存储它们?

如果我们遵循80-20原则，即20%的url产生80%的流量，我们希望缓存这些20%的热点url。

由于我们每秒有2万次请求，我们每天将会收到17亿次请求。

20K * 3600 seconds * 24 hours = ~1.7 billion

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

0.2 * 1.7 billion * 500 bytes = ~170GB

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

估算概述

假设每个月有5亿个新url，读:写比率为100:1，下面是对我们服务容量估算的总结。

•创建短链 200/s•短链重定向 20K/s•入口流量 100KB/s•出口流量 10MB/s•五年需要存储量 15TB•内存用量 170GB

四. 系统API设计

一旦我们确定了需求，定义系统API总是一个好主意。这时候应该明确说明系统期望做到什么。

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

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

参数

•api_dev_key (string) : 注册帐号的api开发密钥。此外，这将用于根据用户分配的配额限制用户•original_url (string): 可选的短链地址•custom_alias (string) : URL 的可选自定义键•user_name (string) : 用于编码的可选用户名•• expire_date (string) : 可选的过期时间

返回

成功将返回缩短的URL。否则，它将返回错误代码。

deleteURL(api_dev_key, url_key)

其中url键是一个字符串，表示要检索的缩短的url。成功的删除返回URL Removed。

我们如何发现和预防滥用?

恶意用户可能会请求占用当前系统中所有URL键，从而让我们的业务失去新建短链的能力。为了防止滥用，我们可以通过api_dev_key来限制用户。每个api_dev_key可以被限制在一段时间特定数量的URL创建和重定向。

五. 数据库设计

在早期阶段定义DB模式将有助于理解不同组件之间的数据流，并在之后帮助我们处理数据分区。

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

•我们需要存储数十亿条记录•我们存储的每个对象都很小(小于1K)。•除了存储哪个用户创建了URL之外，记录之间没有任何关系。•我们的服务读请求量很大。

数据库模型

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

URL	User
[PK] Hash: varchar(16)	[PK] UserID: int
OriginalURL: varchar(512)	Name: varchar(20)
CreationDate: datetime	Email: varchar(20)
ExpirationDate: datatime	CreationDate: datetime
	LastLoginDate: datetime

我们应该使用什么样的数据库？

因为我们预期存储数十亿行数据，而且我们不需要使用对象之间的关系，像DynamoDB这样的NoSQL键值存储，Cassandra或Riak是一个更好的选择。选择NoSQL也更容易扩展。请参阅SQL vs NoSQL^[3]了解更多细节

六. 基本系统设计与算法

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

在第一节为什么我们需要URL短链示例中，缩短的 URL 是http://tinyurl.com/jlg8zpc。这个 URL 的最后六个字符就是我们要生成的主键。

我们将在这里探索两种解决方案。

方案一. 编码URL

我们可以计算给定URL的唯一哈希值(例如，MD5或SHA256等)。然后可以对哈希进行编码以用于显示。

编码方式可以是base36 ([a-z,0-9])或base62 ([A-Z, a-z, 0-9])，如果加上-和.我们可以使用base64编码。问题是，短键的长度应该是多少?

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

68.7B唯一的字符串对于我们的系统来说就足够了，所以我们可以使用6个字母的键。

如果我们使用 MD5 算法作为我们的哈希函数，它将产生一个 128 位的哈希值。base64 编码后，我们将得到一个超过 21 个字符的字符串（因为每个 base64 字符编码 6 位哈希值）。既然我们每个快捷键只有8个字符的空间，那么我们将如何选择我们的密钥呢？我们可以取前 6 个（或 8 个）字母作为密钥。不过，这可能会导致密钥重复，在此基础上我们可以从编码字符串中选择一些其他字符或交换一些字符。

该解决方案有哪些不同的问题？

我们的编码方案有以下几个问题

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

2. 如果 URL 的一部分是 URL 编码的怎么办？

例如，http://www.education.io/distributed.php?id=design 和 http://www.education.io/distributed.php%3Fid%3Ddesign

解决方法

我们可以向每个输入URL添加递增的序列号，使其惟一，然后生成它的散列。我们不需要把这个序列号存储在数据库中。这种方法可能存在的问题是不断增加的序列号它会溢出，附加递增的序列号也会影响服务的性能。

另一种解决方案是在输入URL中附加用户id(它应该是唯一的)。但是，如果用户还没有登录，我们就必须要求用户选择唯一密钥。即使在这之后如果我们有冲突，我们必须不断生成一个密钥，直到我们得到一个唯一的密钥。

方案二. 离线生成密钥

我们可以有一个独立的密钥生成服务(KGS)，它事先生成随机的6个字母字符串，并将它们存储在一个数据库中(我们称之为Key-db)。当我们想要缩短一个URL时，我们只需要一个已经生成的键并使用它。这种方法将使事情变得非常简单和快速。我们不仅没有对URL进行编码，而且还不必担心重复或冲突。KGS将确保插入到key-DB中的所有键都是唯一的。

并发性问题

一旦密钥被使用，就应该在数据库中进行标记，以确保不会再次使用。如果有多个服务器并发地读取密钥，我们可能会遇到两个或更多服务器试图从数据库读取相同密钥的场景。我们如何解决这个并发问题？

服务器可以使用 KGS 读取/标记数据库中的密钥。KGS 可以使用两张表来存储密钥：一张用于存储尚未使用的密钥，另一张用于存储所有使用过的密钥。一旦 KGS 将密钥提供给其中一台服务器，它就可以将它们移动到已使用的密钥表中。KGS 可以始终在内存中保留一些密钥，以便在服务器需要时快速提供它们。

为了简单起见，一旦KGS在内存中加载了一些键，它就可以将它们移动到所使用的键表中。这确保了每个服务器获得唯一的密钥。如果KGS在将所有加载的密钥分配给某个服务器之前挂掉，这部分密钥将会被浪费，这是可以接受的，因为我们有大量的密钥。

KGS还必须确保不向多个服务器提供相同的密钥。为此，它必须同步(或获得锁)持有密钥的数据结构，然后从该数据结构中删除密钥并将它们交给服务器。

密钥数据库大小是多少?

使用 base64 编码，我们可以生成 68.7B 个唯一的六个字母键。如果我们需要一个字节来存储一个字母数字字符，我们可以将所有键存储在412GB的磁盘。

6 (characters per key) * 68.7B (unique keys) = 412 GB

KGS不是单点故障吗?

是的。为了解决这个问题，我们可以有一个备用的KGS副本，当主服务器死亡时，备用服务器可以接管生成并提供密钥。

每个应用服务器是否可以从key-DB中缓存一些key?

是的，而且可以加快响应速度。尽管在这种情况下，如果应用服务器在使用所有密钥之前就死掉了，我们最终会丢失这些密钥。但这是可以接受的，因为我们有68B唯一的6个字母的key。

如何执行键查找?

我们可以在数据库或键值存储中查找键以获得完整的URL。如果存在，则向浏览器发出一个HTTP 302重定向状态，并在请求的Location字段中传递存储的URL。如果该密钥不在我们的系统中，则发出HTTP 404 not Found状态或将用户重定向回主页。

我们应该对自定义别名施加大小限制吗？

我们的服务支持自定义别名。用户可以选择他们喜欢的任何密钥，但提供自定义别名不是强制性的。但是，对自定义别名施加大小限制以确保我们拥有一致的 URL 数据库是合理的（并且通常是可取的）。假设用户可以为每个客户键指定最多 16 个字符（如数据库架构所示）

七. 数据分区与备份

为了扩展我们的数据库，我们需要对它进行分区，以便它能够存储数十亿url的信息。我们需要想出一个分区方案，将我们的数据划分并存储到不同的DB服务器上。

区间划分

我们可以根据 URL 的第一个字母或哈希键将 URL 存储在单独的分区中。因此，我们将所有以字母A开头的 URL 保存在一个分区中，将那些以字母`B``开头的 URL 保存在另一个分区中，依此类推。这种方法称为基于范围的分区。我们甚至可以将某些不太频繁出现的字母组合到一个数据库分区中。我们应该提供一个静态分区方案，以便我们可以以可预测的方式存储/查找文件。

这种方法的主要问题是，它可能导致服务器不平衡。例如: 我们决定将所有以字母E开头的url放到一个DB分区中，但后来我们意识到有太多的url以字母E开头。

基于散列分区

在这个方案中，我们取所存储对象的哈希值。然后根据散列计算要使用哪个分区。在本例中，我们可以使用键或实际URL的哈希值来确定存储数据对象的分区。我们的哈希函数将随机地将url分配到不同的分区中(例如，我们的哈希函数总是可以将任意键映射到[1…256]之间的一个数字)，这个数字将代表我们存储对象的分区。

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

八. 缓存

我们可以缓存频繁访问的url。可以使用一些现成的解决方案，如Memcache，它可以存储带有各自散列的完整url。应用服务器在访问后端存储之前，可以快速检查缓存是否具有所需的URL。

缓存容量应该有多大?

我们缓存每日流量的20%，然后根据客户端使用模式调整我们需要多少缓存服务器。如上所述，我们需要170GB内存来缓存每日流量的20%。因为现在的服务器可以有256GB的内存，我们可以很容易地把所有的缓存放到一台机器上。或者，我们可以使用一些较小的服务器来存储所有这些热点URL。

哪种缓存驱逐策略最适合我们的需求？

当缓存已满，而我们想用更新/更热的 URL 替换链接时，我们将如何选择？最近最少使用 (LRU) 可能是比较合适的。根据此策略，我们首先丢弃最近最少使用的 URL。我们可以使用 LinkedHashMap 或类似的数据结构来存储我们的 URL 和 Hash，这也可以跟踪最近访问过的 URL。

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

如何更新每个缓存副本?

每当缓存丢失时，我们的服务器就会击中后端数据库。每当发生这种情况时，我们就可以更新缓存并将新条目传递给所有缓存副本。每个副本都可以通过添加新条目来更新它们的缓存。如果副本已经有该条目，则可以简单地忽略它。

九. 负载均衡

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

1.客户端和应用服务器之间2.应用服务器与数据库服务器之间的连接3.应用服务器和缓存服务器之间

最初，我们可以使用简单的Round Robin方法，将传入请求平均分配到后端服务器。这种LB实现简单，而且不引入任何开销。这种方法的另一个好处是，如果一个服务器死机了，LB将停止向它发送任何流量。

轮询LB的问题是没有考虑服务器负载。如果服务器负载过重或速度变慢，LB不会停止向该服务器发送新的请求。为了解决这个问题，可以放置一个更智能的LB解决方案，定期查询后端服务器的负载，并基于此调整流量。

十. 数据清理

短链是应该永久保存还是应该到期清除? 如果到达用户指定的过期时间，该链接将发生什么情况？

如果我们选择主动搜索过期链接来删除它们，这将给我们的数据库带来很大的压力。相反，我们可以缓慢地删除过期链接，并进行惰性清理。我们的服务将确保只有过期的链接将被删除，尽管一些过期链接可以活得更长，但永远不会返回给用户。

•当用户试图访问过期链接时，我们可以删除链接并向用户返回一个错误•可以定期运行一个单独的Cleanup服务，从存储和缓存中删除过期的链接。该服务应该是非常轻量级的，并且只在用户流量预期较低时才可以调度运行•我们可以为每个链接设置一个默认的过期时间(例如，两年)。•在删除过期链接之后，我们可以将密钥放回key-db中以供重用。•应该删除6个月没有访问过的链接吗? 这可能有点棘手。由于存储变得越来越便宜，我们可以决定永远保持链接。

十一. 追踪扩展

一个短 URL 被使用了多少次，用户位置是什么，等等？我们将如何存储这些统计信息？如果它是在每个视图上更新的 DB 行的一部分，那么当一个热点的 URL 受到大量并发请求的冲击时会发生什么？

一些值得跟踪的统计数据: 访问者的国家、访问日期和时间、涉及点击的网页、浏览器或访问页面的平台。

十二. 安全与权限

用户是否可以创建私有URL或允许特定用户组访问URL。

我们可以在数据库中存储每个 URL 的权限级别（公共/私有）。我们还可以创建一个单独的表来存储有权查看特定 URL 的用户 ID。如果用户没有权限并尝试访问 URL，我们可以发回错误 (HTTP 401)。鉴于我们将数据存储在像 Cassandra 这样的 NoSQL 宽列数据库中，表存储权限的密钥将是哈希（或 KGS 生成的密钥）。这些列将存储有权查看 URL 的那些用户的用户 ID。

References

[1] 《系统设计面试的万金油》: http://antzuhl.cn/archives/%E7%B3%BB%E7%BB%9F%E8%AE%BE%E8%AE%A1%E9%9D%A2%E8%AF%95%E7%9A%84%E4%B8%87%E9%87%91%E6%B2%B9
[2] TinyURL: https://tinyurl.com/app
[3] SQL vs NoSQL: https://www.educative.io/collection/page/5668639101419520/5649050225344512/5728116278296576/