设计 TinyURL 和 Instagram：系统设计面试教程

本文由 Aaron Xie 撰写，最初发表于Educative.io

在当今的科技行业，理解系统设计比以往任何时候都更加重要。随着应用程序规模越来越大，设计高效可靠的架构模式至关重要。如今，系统设计通常是获得理想软件工程师职位的必备条件。

今天，我们将通过设计 Instagram 和 TinyURL 来回顾系统设计原则。

您将学习：

如何设计 TinyURL
如何设计 Instagram
总结和资源

如何设计 TinyURL

TinyURL 是什么

TinyURL是一项 URL 缩短 Web 服务，可以为长 URL 创建更短的别名。点击短链接后，用户将被重定向到原始 URL。这项服务非常有用，因为短链接可以节省空间，并允许用户更轻松地输入长 URL。

系统的要求和目标

在设计类似 TinyURL 的应用程序时，需要考虑一些功能性和非功能性需求。

非功能性需求：

系统必须高可用，一旦服务故障，所有短链接都将无法使用。
URL 重定向应实时进行，且延迟最小。
缩短的链接不应该以任何方式可预测。

功能要求：

当输入 URL 时，我们的服务会生成原始 URL 的更短别名。这个新链接将被大幅缩短，以便于轻松复制和粘贴。
短链接应该将用户重定向到原始链接。
用户应该可以选择为他们的 URL 选择一个自定义短链接。
短链接将在默认时间跨度后过期，但用户可以指定过期时间。

容量估算和约束

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

流量估算：假设我们每月将有 5 亿个新的 URL 缩短，读/写比率为 100：1，我们预计同期将有 500 亿个重定向：

100*500M => 50B

我们的系统每秒查询次数 (QPS) 是多少？每秒新 URL 的缩短次数：

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

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

100 * 200 个 URL/秒 = 20K/秒

存储估算：假设我们将所有 URL 缩短请求（以及相关的缩短链接）存储五年。由于我们预计每月会有 5 亿个新 URL，因此预计需要存储的对象总数将达到 300 亿个：

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

假设每个存储对象大约为 500 字节（这只是一个大概的估计，我们稍后会深入探讨）。我们需要 15TB 的总存储空间：

300亿 * 500字节 = 15 TB

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

200 * 500 字节 = 100 KB/秒

对于读取请求，由于我们预计每秒会有大约 20K 个 URL 重定向，因此我们服务的总传出数据量为每秒 10MB：

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

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

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

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

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

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

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

系统 API

我们可以使用 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(字符串)：要缩短的原始 URL。

custom_alias(字符串)：URL 的可选自定义键。

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

expire_date(字符串)：缩短 URL 的可选到期日期。

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

deleteURL(api_dev_key, url_key)

是url_key用于描述需要删除的缩短 URL 的字符串。删除成功后将返回URL Removed。

数据库设计

让我们看一下有关我们存储的数据的一些观察结果：

该服务需要存储数十亿条记录。
该服务读取量很大。
每个对象都很小（小于 1K）。
除了存储哪个用户创建了短链接之外，每条记录之间没有任何关系。

架构：

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

我们使用什么类型的数据库？

最好的选择是使用像DynamoDB或 Cassandra 这样的 NoSQL 数据库存储，因为我们存储了数十亿行数据，而对象之间没有关系。

基本系统设计和算法

我们的服务面临的最大问题是，如何在给定 URL 的情况下生成一个简短且唯一的密钥。今天我们将探讨的方法是对实际 URL 进行编码。

我们可以计算给定 URL 的唯一哈希值（例如 MD5 或 SHA256 等）。然后可以对该哈希值进行编码以供显示。编码可以是 base36 ([az,0-9]) 或 base62 ([AZ, az, 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 个）字母作为密钥。这可能会导致密钥重复。为了解决这个问题，我们可以从编码字符串中选择一些其他字符，或者交换一些字符。

采用这种方法存在一些潜在的障碍：

如果多个用户输入相同的URL，他们将获得相同的短链接。
URL 的某些部分可以进行 URL 编码。

解决方法：为了解决部分问题，我们可以将序列中的数字添加到每个短链接 URL 中。这样，即使多个用户提供相同的 URL，也能确保其唯一性。

另一个可能的解决方案是将用户 ID 附加到输入 URL。如果用户未登录，则此方法无效，我们需要生成一个唯一键。

数据分区和复制

不可避免地，我们需要扩展我们的数据库，这意味着我们必须对其进行分区，以便能够存储有关数十亿个 URL 的信息。

基于范围的分区：我们可以根据 URL 哈希键的首字母将其存储在不同的分区中。因此，我们将所有哈希键首字母相同的 URL 存储A在一个分区中，以此类推。

这种方法是有问题的，因为它会导致数据库服务器不平衡，从而产生不平等的负载。

基于哈希的分区：使用基于哈希的分区，我们可以对存储的对象进行哈希运算，然后计算要使用的分区。哈希函数会将数据随机分布到不同的分区中。

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

缓存

我们的服务应该能够缓存经常访问的 URL。我们可以通过 Memcached 之类的解决方案来实现这一点，它可以存储完整的 URL 及其对应的哈希值。

我们应该配置多少缓存？首先，我们可以从每日流量的 20% 左右开始，然后根据使用模式进行调整。根据之前的估算，我们需要 170GB 的内存来缓存 20% 的每日流量。

我们应该使用哪种缓存驱逐策略？因为我们想用更流行的 URL 替换链接，所以我们可以为系统使用最近最少使用 (LRU) 策略。

负载均衡器 (LB)

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

客户端与应用服务器之间
在应用程序服务器和数据库服务器之间
在应用程序服务器和缓存服务器之间

首先，我们可以简单地使用循环调度方法，将传入的请求平均分配给各个服务器。这种方法很容易实现，而且不会产生任何开销。

如果服务器通过这种方式过载，负载均衡器将不会停止向该服务器发送新请求。为了解决这个问题，可以开发一个更智能的负载均衡器解决方案，根据服务器负载定期调整流量。

掌握系统设计。

Educative 的系统设计课程会教您针对常见面试问题的各种系统设计模式，包括 Dropbox 和 Facebook。

理解系统设计面试

设计 Instagram

Instagram 是什么？

Instagram是一个社交媒体平台，允许用户与其他用户分享照片和视频。与许多其他社交媒体平台一样，用户可以公开或私下分享他们的信息。

今天，我们将设计一个简易版的 Instagram，用户可以在其中分享照片、关注其他用户以及访问动态消息。动态消息中包含用户关注用户的热门照片。

要求和目标

在设计类似 Instagram 的应用程序时，需要考虑一些功能性和非功能性要求。

非功能性需求：

该服务应具有高可用性。
对于新闻推送，系统可接受的延迟应该在 200 毫秒左右。
该系统应具有高度的可靠性，以确保系统中的任何照片或视频都不会丢失。

功能要求：

用户应该能够根据照片或视频标题进行搜索。
用户应该能够上传、下载和查看照片和视频。
用户应该能够关注其他用户。
该系统应该能够生成显示的新闻提要，其中包含用户关注的人的热门照片和视频。

该项目不涵盖的一些内容包括为照片添加标签、使用标签搜索照片、评论照片、标记用户等。

容量估算和约束

假设我们总共有 5 亿用户，其中每日活跃用户为 100 万。
每天新增 200 万张照片，每秒新增 23 张照片。
平均照片文件大小 => 200KB
1 天的照片所需的总空间：

2M * 200KB => 400 GB

10 年所需的总空间：

400GB * 365（一年天）* 10（年）~= 1425TB

高层系统设计

从高层次来看，系统应该能够支持用户上传媒体，并允许其他用户查看照片。因此，我们的服务需要服务器来存储照片和视频，以及另一个数据库服务器来存储媒体的元数据。

数据库架构

虽然我们可以采取一种简单的方法，将上述模式存储在关系数据库管理系统（RDBMS）中，但在使用关系数据库时会出现一些挑战，尤其是在扩展应用程序时。

我们可以使用 NoSQL 数据库以键值对的形式存储上述模式。照片和视频的元数据将归属于一个表，其中是key，PhotoID是value一个包含PhotoLocation、UserLocation、CreationTimestamp等的对象。

我们可以使用 Cassandra（一种宽列数据存储）来存储用户与照片之间的关系以及用户关注的人员列表。key该UserPhoto表的将是UserID，而value将是用户拥有的的列表PhotoIDs，它们将存储在不同的列中。此模式类似于UserFollow表。

照片和视频可以存储在像 HDFS 这样的分布式文件存储中。

数据大小估计

让我们估算一下每个表中将有多少数据以及 10 年内我们需要多少总存储空间。

用户：假设每个int和dateTime为四个字节，则用户表中的每一行将为 68 个字节：

用户 ID（4 字节）+ 姓名（20 字节）+ 电子邮件（32 字节）+ 出生日期（4 字节）+ 创建日期（4 字节）+ 上次登录（4 字节）= 68 字节

如果我们有 5 亿用户，我们将需要 32GB 的总存储空间。

5亿*68~=32GB

照片：照片表中的每一行将有 284 个字节：

PhotoID（4 字节）+ UserID（4 字节）+ PhotoPath（256 字节）+ PhotoLatitude（4 字节）+ PhotLongitude（4 字节）+ UserLatitude（4 字节）+ UserLongitude（4 字节）+ CreationDate（4 字节）= 284 字节

如果每天上传 200 万张新照片，那么我们一天就需要 0.5GB 的存储空间：

2M * 284 字节 ~= 0.5GB/天

10 年后我们将需要 1.88TB 的存储空间。

UserFollow： UserFollow 表中的每一行包含 8 个字节。如果我们有 5 亿用户，平均每个用户关注 500 个用户，那么 UserFollow 表将需要 1.82TB 的存储空间：

5亿用户 * 500名关注者 * 8字节 ~= 1.82TB

所有表 10 年所需的总空间为 3.7TB：

32GB + 1.88TB + 1.82TB ~= 3.7TB

组件设计

照片上传通常很慢，因为数据会写入磁盘，而读取则要快得多。由于上传过程缓慢，上传用户会占用所有可用连接。因此，当系统写入请求过多时，读取请求就无法得到响应。为了解决这一瓶颈，我们可以将读取和写入操作拆分到不同的服务器上，以避免系统过载。

这将使我们能够有效地优化每个操作。

可靠性和冗余

由于该应用程序注重可靠性，我们不能丢失任何文件。因此，我们会为每张照片和视频存储多个副本，这样即使一台服务器宕机，系统也能从副本服务器中检索媒体。

这种设计将应用于我们架构的其他组件。我们将在系统中运行多个服务副本，这样即使某个服务宕机，系统也能继续运行。创建系统冗余机制使我们能够在系统故障时创建备份。

数据分片

元数据分片的一个可能方案是根据PhotoID进行分区。

如果我们可以先生成唯一的 PhotoID，然后通过找到分片编号PhotoID % 10，上述问题就能迎刃而解。在这种情况下，我们无需将 PhotoID 附加到 ShardID 上，因为 PhotoID 本身在整个系统中都是唯一的。

想了解更多关于数据分片的知识吗？请查看我们的“什么是数据分片”专题，了解基础知识。

我们如何生成 PhotoID？这里我们无法在每个分片中都使用一个自增序列来定义 PhotoID，因为我们需要先知道 PhotoID，才能找到存储它的分片。一个解决方案是，我们可以使用一个单独的数据库实例来生成自增 ID。如果我们的 PhotoID 可以容纳在 64 位中，我们可以定义一个只包含 64 位 ID 字段的表。这样，每当我们想在系统中添加照片时，都可以在这个表中插入一个新行，并将该 ID 作为新照片的 PhotoID。

这个生成键的数据库会不会成为单点故障？是的，会的。一个解决方法是定义两个这样的数据库，一个生成偶数 ID，另一个生成奇数 ID。对于 MySQL，以下脚本可以定义这样的序列：

KeyGeneratingServer1:
auto-increment-increment = 2
auto-increment-offset = 1

KeyGeneratingServer2:
auto-increment-increment = 2
auto-increment-offset = 2

我们可以在这两个数据库前面放置一个负载均衡器，以便在它们之间进行轮询并处理停机时间。这两个服务器可能不同步，其中一个服务器生成的键比另一个服务器多，但这不会对我们的系统造成任何问题。我们可以扩展此设计，为用户、照片评论或系统中存在的其他对象定义单独的 ID 表。

负载均衡

该服务需要一个大规模的照片传输系统，以便向全球用户提供数据。我们可以使用地理分布的缓存服务器，将内容推送到更靠近用户的地方。

总结和资源

做得好！现在你应该对如何设计像 Instagram 和 TinyURL 这样的应用程序有了一定的了解。不过，还有很多系统设计模式需要学习。想学习如何在 Instagram 上创建新闻推送生成服务吗？快来学习我们的“系统设计面试入门”课程吧！

本课程将涵盖 Dropbox、Facebook Messenger、Twitter 等其他应用程序！通过实际案例学习系统设计的行业标准。

资源

理解系统设计面试（课程）
面向开发人员的可扩展性和系统设计（学习轨迹）
7 种最重要的软件设计模式：在下一次软件工程面试之前了解一些最常见的设计模式（文章）。

文章来源：https://dev.to/educative/design-tinyurl-and-instagram-system-design-interview-tutorial-35cf