如何设计一个短网址系统
网址短链接就是一些长链接的别名，比如 bit.ly, goo.gl, qlink.me，输入这些链接会跳转到对应的长链接。
1.为什么需要短链接
短链接主要用来为长链接生成更短的别名，用户点击短链接会重定向到原来的长链接，在显示、打印、发送消息、发送推文等场景下，短链接节省了很大的显示空间，更重要的是，用户不太可能去拒绝输入一个短链接。
举个例子，为长链接 https://www.educative.io/collection/page/5668639101419520/5649050225344512/5668600 916475904/ 生成的短链接就是 http://tinyurl.com/jlg8zpc]，短链接的长度仅仅是原来的三分之一。
短链接主要用于优化，可以跟踪单个链接以进行分析受众群体和广告效果，并隐藏关联的原始网址。如果你从未使用过 tinyurl.com，请在上面尝试创建一个短网址，并了解一下他们的服务，这将有助于你理解需求。
2.系统的需求和目标
应在面试开始时就明确需求。面试时请务必提出问题，以找到所设计系统的确切范围。我们的 URL 短链接系统应满足以下需求：
功能需求：
1、 给定一个 URL，我们的服务应为其生成一个较短且唯一的别名，这也是最基本最核心的功能。
2、当用户访问短链接时，我们的服务应将其重定向到原始链接。
3、用户应该可以选择为其 URL 选择自定义格式的短链接。
4、链接将在默认时间间隔后过期，用户可以指定指定到期时间。
非功能需求：
1、该系统应具有很高的可用性。这是必需的，因为如果的服务中断，则所有 URL 重定向将失败。
2、URL 重定向应以最小的延迟实时进行。
3、生成的短链接是不可猜测的，也就是说长链接到短链接的转换是无规律的。
扩展需求
1、数据分析需求：例如，重定向发生了多少次？
2、其他服务可以通过 REST API 访问我们的服务。
3、短链接可以回收。
3.资源估算和约束
很明显，我们的系统将是读任务比写任务繁重，也就是说重定向的请求次数要远多于生成短网址的请求次数。假设读写之间的比例为 100：1，接下来进行一些估算：
流量估算
假设我们每月将有 500 M 新的 URL 生成，其中读写比为 100：1， 可以预测每月有 500 亿次重定向：
100 * 500M => 50B
预测下系统每秒的请求次数 QPS（Queries Per Second）：
500 million / (30 days * 24 hours * 3600 seconds) = ~200 URLs/s
也就是说每秒的写请求次数是 200 次。考虑到读写比就 100:1，那么重定向的 QPS 是：
100 * 200 URLs/s = 20K/s
也就是每秒 2 万次重定向请求。
存储估算
假设我们存储每个短链接的请求（以及相关的短 链接）为 5 年。由于我们预计每月会有 5 亿个新 URL，因此对象总数我们预计将存储 300 亿：
500 million * 5 years * 12 months = 30 billion
假设每个存储的对象大约为 500 个字节，当然，这仅是估算值，我们将需要 15 TB 的总存储空间：
30 billion * 500 bytes = 15 TB
带宽估计
对于写请求，由于我们期望每秒总共 200 个新 URL，我们服务的传入数据将为每秒 100 KB：
200 * 500字节= 100 KB / s
对于读请求，由于我们期望每秒进行约 20 K 的 URL 重定向，因此我们的总传出数据的服务将是每秒 10 MB：
20K * 500字节=〜10 MB / s
内存估算
如果要缓存一些经常访问的热门网址，则需要多少多大的内存来存储它们呢？
如果我们遵循 80-20 规则，则意味着 20％ 的网址生成 80％ 的流量，我们想缓存这 20％ 的热门 URL。
由于我们每秒有 2 万个请求，因此我们每天将收到 17 亿个请求：
20K * 3600秒* 24小时=约 17 亿
要缓存这些请求的 20％，我们将需要 170 GB 的内存。
0.2 * 17亿* 500字节=〜170GB
这里要注意的一件事是，由于会有很多重复的请求，即相同的 URL，因此，我们的实际内存使用量将小于 170 GB。
估算汇总
假设每月有 5 亿个新 URL，读/写比为 100：1，
新网址 200 / s/ URL 重定向 20 K / s 传入数据 100 KB / s 传出数据 10 MB / s 储存 5 年 15 TB 缓存内存 170 GB
4.系统 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 (字符串): 注册帐户的 API 开发人员密钥。这可以根据分配的配额限制用户。 original_url（字符串）：要缩短的原始 URL。 custom_alias（字符串）：URL 的可选自定义键。 user_name （字符串）：可选，用于编码的用户名 expire_date （字符串）：过期时间。
返回值：
如果成功则返回对应的短链接，否则返回错误代码。
还需要一个过期后删除短链接的 API，比如：
deleteURL(api_dev_key, url_key)
这里的 url_key 就是要删除的短链接。如果删除成功，则返回“url 已经删除”，必要时可以回收短链接资源。
如何检测并防止恶意调用
恶意用户可以通过消耗全部资源来使我们的服务不可用。当前设计中的 api_dev_key 就是为了防止滥用，可以通过其 api_dev_key 限制用户。比如为每一个 api_dev_key 每一段时间限制为一定数量的 URL 创建和重定向。
5.数据库设计
在面试的早期阶段定义数据库模式将有助于理解数据各个组件之间的交互，并指导数据分区。
我们要存储的数据有以下特点：
我们需要存储海量的数据，比如上亿条记录。 每一个对象都比较小，小于 1 K。 记录与记录之间没有关系。 任务是读繁重的。
数据库模式
我们需要建两个表，一个存储 url 映射信息，一个存储创建短链接的用户数据。
url 表：
id original-url short-url creation-date expiration-date user-id
user 表：
user-id name email creation-date last-login
选用哪一种数据库？
一方面要存储大量的数据，另一方面，数据对象之间的关系非常简单，使用非关系型数据库是更好的选择，比如 DynamoDB, Cassandra or Riak，而且选择 NoSQL 更容易规模化。
6. 基本的系统设计和算法
我们这里要解决的问题是如何为给定的 URL 生成短而唯一的密钥。
在第 1 节的 TinyURL 示例中，缩短的URL为 “ http://tinyurl.com/jlgzpc” 。最后六个 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 万亿个可能的字符串。前面已经估算过，5 年内产生 300 亿个新 URL，且短链接的保存期限也是 5 年，那么 687 亿足够满足 5 年内的使用，因此选择 6 个字母长度即可。
如果我们将 MD5 算法用作哈希函数，它将产生 128 个二进制位。在 base64 之后编码，我们将得到一个包含 21 个以上字符的字符串（因为每个 base64 字符代表 6 位 二进制位，128/6 = 21.3）。由于每个短链接只能容纳 6 个字符，因此可以选取 21 个字符的前 6 个作为短链接的 key，不过这可能会导致密钥重复，可以从编码字符串中选择其他一些字符或交换一些字符来降低重复的概率。
这样的方案会产生什么问题：
1、如果多个用户输入相同的长链接，获取的短链接也是相同的，这是不能接收的，即使相同的长链接，不同用户生成的短链接也是不同的，只有这样才可以跟踪单个链接以进行分析受众群体和广告效果。
2、如果长链接被编码了怎么办，比如：“ http://www.educative.io/distributed.php? id=design” 和 “ http://www.educative.io/distributed.php%3Fid%3Ddesign” 是相同的链接，但后者进行了编码，导致相同的 url 产生了不同的短链接。
如何解决呢？
针对第一个问题，我们可以为每一个 url 设置一个自增的序列号，确保每一个 url 的唯一性，然后 url 和序列号一起做哈希，数据库中可以不保存这个序列号，即使如此也可能产生问题，比如说这个自增序列号会不会溢出，自增序列号是全局唯一的，使我们的服务要先获取才能使用，一定程度上降低了并行度，降低了性能。
另一种方法是将 url 和 用户的 api-dev-key 一起编码，这种方式比前一种要好，但也不是没有缺点，就是用户必须注册并获取 api-dev-key 才能使用，我们的系统要能确保为用户生成的 api-dev-key 都是唯一的。
第二个问题比较简单，获取到 url 后统一存放编码后或编码前的 url 即可。
第二种：离线生成短链接 key
我们可以有一个独立的短链接 key 生成服务（KGS ：Key Generation Service），它可以生成随机的六个字母字符串，事先将它们存储在数据库中（我们称其为密钥数据库）。每当我们要缩短网址时，我们将只使用一个已经生成好的字符串并使用它。这种方法会使事情变得相当简单快捷。这样就不需要对 URL 进行编码，而且不必担心重复或哈希碰撞。KGS 将确保插入到数据库中的所有 key 都是唯一的。
这样的话，并发度高会产生问题吗？如果有多个服务器同时读取 key，该如何解决？
使用 key 后，应立即对其进行标记，确保不再使用它。服务器可以使用 KGS 来读取/标记数据库中的 key。KGS 可以使用两个表来存储 key ：一个存储尚未使用的 key，一个保存所有已使用的 key。一旦 KGS 将钥匙交给其中一个服务器，它可以将它移动到已使用的 key 表中。KGS 始终可以在内存中保留一些 key，以便服务器需要时更快的响应。
为简单起见，一旦 KGS 将一些 key 加载到内存中，它便可以将其移至已用的 key 表中。这样可以确保每个服务器都获得唯一的 key。如果在将所有已加载的 key 分配给某个服务器之前，KGS 服务宕机，我们将浪费那些已加载的 key，考虑到我们拥有的 key 数量巨大，这是可以接受的。
KGS 还必须确保不要将相同的 key 提供给多个服务器。为此，它必须同步（或锁定）持有 key 的数据结构，然后再从中删除，然后将其提供给服务器。
那么保存 key 的数据库的大小是多少？使用 base64 编码，我们可以生成 687 亿个唯一的六个字母的 key。一个字节来可以存储一个字符，则可以将所有这些键存储，需要的数据库大小为 412 GB：
6 (characters per key) * 68.7B (unique keys) = 412 GB.
KGS 存在单点故障吗？是的。为了解决这个问题，我们可以有一个 KGS 的备机，只要主服务器死机，备用服务器就可以接管生成并提供 key。
每个应用服务器都可以从 key-DB 缓存一些 key 吗？是的，这还可以加快速度。虽然 在这种情况下，如果应用服务器没有使用完 key 之前就宕机，我们最终将失去这些密 key。这是可以接受的，因为我们有 687 亿个唯一的六个字母 key。
如何执行 key 的查找？我们可以在数据库中根据 key 获取原始的 URL。如果存在，就向浏览器发出“ HTTP 302 重定向”状态，并重定向到原始的 URL。如果该 key 不存在于系统中，请发出“未找到 HTTP 404”，将用户重定向回首页。
应该对自定义别名施加大小限制吗？我们的服务支持自定义别名。用户可以选择 他们喜欢的任何“键”，但并非必须提供自定义别名。但是，这是合理的，而且通常 最好对自定义别名施加大小限制，以确保我们拥有一致的 URL 数据库，比如用户最多可指定 16 个字符，数据架构如下如所示：
7.数据分区
为了数据库便于扩展，我们需要对其进行分区，以便它可以存储数十亿个 URL 的信息。所谓的分区就是将数据划分并存储到不同的数据库服务器中。
一种方法是基于范围的分区：我们可以根据网址的第一个字母或 url 的哈希值 将网址存储在单独的分区中，比如将所有以字母“ A”开头的网址保存在一个分区中，字母“ B”开头的保存在另一个分区中，依此类推。这种方法称为基于范围的分区。甚至可以将某些不经常出现的字母组合，包含组合字母的 url 放到一个数据库分区中。这也是一种静态分区方案，提前规划好方案，每一个 url 存储到哪个分区都是可以预见的。
这种方法可能导致分区的不平衡。例如：将所有以字母 “E” 开头的 URL 放入数据库分区 A，但后来我们意识到我们有太多以字母“ E”开头的网址，于是分区 A 存储了过多的数据。
另一种方法就是基于散列的分区：在此方案中，我们对要存储的对象进行散列。然后我们根据哈希计算要使用的分区。例如，我们的哈希函数总是可以将任何 url 映射到 1…256 之间的数字，该数字代表数据的分区我们，这种方法仍然会导致分区不平衡，不过这可以通过使用一致性哈希技术来解决。(什么是一致性哈希技术，我立刻搜了一下)
node_number = hash(key) % N
8.缓存
对于经常访问的 URL 可以缓存。我们可以使用一些现成的解决方案，例如 Memcache，可以存储带有各自哈希值的完整 URL。应用服务器问后端存储之前，可以快速检查缓存是否具有所需的URL。
缓存多大比较好？我们可以从每日流量的 20％ 开始，并根据客户的使用情况调整所需的缓存服务器数量。前面内存估算时，我们需要 170 GB 内存来缓存每日流量的 20％。由于现代服务器可以拥有 256 GB 的内存，因此我们可以轻松的将所有缓存放入一台服务器。另外，我们可以使用几个较小的服务器来存储所有这些热点网址。
哪种高速缓存淘汰算法最适合我们的需求？当缓存已满时，我们想要用较新/较热门的 URL 替换掉较旧/较冷门的链接，最近最少使用（LRU）就是最适合这个需求人根据此算法，我们将首先丢弃最近最少使用的 URL。我们可以使用 Java 的 Linked Hash Map 来实现，或者使用自定义的数据结构来实现。
为了进一步提高效率，我们可以复制缓存服务器，然后配置负载均衡。这样会带来一个问题：如何更新每个缓存副本？每当发生缓存未命中时，我们的服务器就会访问后端数据库，每当发生这种情况时，我们可以更新缓存并将新条目传递给 所有缓存副本。每个副本都可以通过添加新条目来更新其缓存。如果副本已经存在 有该条目，它可以简单地忽略它。
9.负载均衡器（LB）
我们可以在系统的三个位置添加一个负载平衡器（LB） ：
在客户端和应用程序服务器之间 在应用程序服务器和数据库服务器之间 在应用程序服务器和缓存服务器之间
最初，我们可以使用简单的 Round Robin 方法，将传入请求平均分配 在后端服务器之间，这样易于实现，不会带来任何开销，如果某个服务器宕机，则负载平衡器会将其从循环中移出并停止向它发送任何流量。Round Robin LB 的问题是未考虑服务器负载。如果服务器是过载或速度较慢时，LB 不会停止向该服务器发送新请求。为了解决这个问题，可以放置智能 LB 解决方案，该解决方案定期向后端服务器查询有关其负载和负载的信息，以此来调整流量。
10.清除或数据库清理
url 记录应该永久存储还是应该物理删除？如果用户指定的到期时间为到达后，链接应该怎么处理？
如果我们选择主动搜索过期链接以将其删除，这将给数据库服务器带来很大压力 。相反，我们可以慢慢删除过期的链接并进行懒惰的清理。我们的服务会确保删除过期的链接，尽管某些过期的链接可以生存更长的时间，但永远不会返回给用户。
每当用户尝试访问过期的链接时，我们都可以删除该链接并向该用户返回错误提示。 可以定期运行单独的清理服务，从数据库和缓存进行清理，此服务应非常轻巧，并且可以安排在用户流量很低的时间段执行。 我们可以为每个链接设置默认的过期时间（例如，两年）。 删除过期的链接后，我们可以将短链接的 key 放回 key 数据库中以重新使用。 我们是否应该删除一段时间（例如六个月）未曾访问过的链接？由于存储设备价格便宜，我们可以永久保留链接。
11. 统计分析
短链接已使用了多少次，用户位置是什么，访问者所在的国家/地区，访问日期和时间，点击次数等等，我们将如何存储这些统计数据？
12.安全性和权限
用户可以创建私有 URL 还是允许特定的一组用户访问 URL？
我们可以使用数据库中的每个 URL 存储许可级别（公共/私有）。我们还可以创建一个单独的表来存储有权查看特定 URL 的 UserID。如果用户没有权限并尝试访问URL，我们可以将错误（HTTP 401）发送回去。
最后的话
系统设计设计软件开放的方方面面，往往难以一次回答全面，但是无外乎以上几个方面，按照梳理好的步骤去思考，展示自己的技术优势，面试就不会太差，本文内容整理自《Grokking the System Design Interview》，如果想看英文原版可以关注本号后台回复「系统设计」获取。
推荐阅读：如何一步一步设计一个大规模复杂的系统