短链系统设计
作用
短链系统用于为长链接创建较短的别名，这些别名叫做短链接。当用户点击短链接时，他们会被重定向到原始 URL。
短链接在展示、发送博客时可以节省大量空间，另外，较短的 URL 更方便用户输入。
例如我们可以通过 tinyUrl 缩短链接 https://store.steampowered.com/app/1375870/Comrade_Trumps_Reelection/ 为 https://tinyurl.com/yx93wn76。
系统的要求与目标
功能需求
- 对于给定 URL，服务应该生成一个较短并且唯一的别名。
- 用户访问短链接时，服务应该将其重定向到原始链接。
- 用户可以为原 URL选择自定义的短链接。
- 短链接在默认时间间隔后过期，用户应该能够指定到期时间。
非功能需求：
- 系统高可用，因为如果服务不可用，会导致所有 URL 重定向失败。
- URL 重定向应该以最小的延迟进行。
- 生成的短链接应该是不可预测的。
扩展要求：
- 分析每个短链接的重定向会发生了多少次？
- 服务应该提供 REST API 接口给其他服务调用。
流量估算与约束
短链接系统是多读少写的系统。对于生成的短链接会被重定向很多次，假设每个短链接的读写比为 100:1。
流量估算
假设每个月会生成 500M 个新的短链接，由于读写比例为 100:1，所以一个月期望的重定向次数为 50B。
估算**短链接生成接口 QPS 为 **
URL 重定向接口 QPS 为
容量估算
假设每个原始链接及其短链接被存储 5 years，每个月会有 500M 个新链接产生，所以总共需要存储的对象为：
假设每个原始链接及其短链接大约为 500 个字节，需要的总存储空间为
带宽估算：
每秒会传入 200 个新 URL，因此每秒传入服务的数据流量为：
每秒传出的数据流量为：
内存估算
对于经常访问的热点数据，需要进行缓存。每秒有 20K 的读取请求，因此每天收到的读取总请求数为：
根据二八定律，我们选择缓存其中 20% 的请求，使用到的内存为：
因为在 170 亿请求中，会有大量的重复请求，所以实际使用到的内存会小于 170GB。
估算汇总
汇总上述估算数据，得到如下表格：
| 指标 | 数据量 |
|---|---|
| 新网址数量 | 200 /s |
| 重定向次数 | 20 K/s |
| 输入流量 | 100 KB/s |
| 输出流量 | 10 MB/s |
| 存储五年所需空间 | 15 TB |
| 缓存内存 | 170 GB |
API 设计
当我们确定需求之后，接下来应该开始设计系统 API。
创建短链接
String createUrl(String devKey,String originalUrl,String customAlias,String userName,LocalDateTime expireDate)
参数意义：
- devKey： API 调用方密钥，用来限制服务调用次数。
- originalUrl：待缩短的原始 URL。
- customAlias：URL 中的自定义字段（可选）
- userName：编码中使用的用户名（可选）
- expireDate：生成的短链接的到期实际（可选）
成功时返回生成的短链接，失败时返回对应的错误编码。
删除短链接
boolean deleteUrl(String devKey,String urlKey)
参数意义：
- devKey：API 调用方密钥
- urlKey：待删除的短链接 URL
通过 boolean 值返回是否成功，失败时再补充失败消息。
恶意访问控制
为了控制暴露的 API 接口被恶意访问，我们通过 devKey 限制用户调用接口数量。
每个 devKey 只能在一定时间段内创建一定数量的短链接并且会限制短链接的重定向次数。（可以会不同的 devKey 设置不同的限制时间）
数据库设计
我们的系统存储的数据的性质包括：
- 每个月产生 5亿个新的 URL，假设在数据库中存储最近一年的数据，则存储的记录总数为 60亿。
- 存储的每个对象都很小（1个英文或数字占 1个字节，因此原始链接应该都小于 1K）。
- 各个记录之间没有关系。
- 记录读写比例很大。
设计表包括两个：短链接映射表以及用户表
表设计
由于存在数十亿的数据，并且记录之间没有依赖关系，所以应该使用 DynamoDB/Cassandra/Riak 这样的 NoSQL 更合适。
基础系统设计与算法
对于短链接系统来说，一个重要的xx问题是对于给定的原始链接，如何生成一个唯一并且足够短的链接。
编码实际的 URL
我们可以使用 MD5 或 SHA256 计算原始 URL 的唯一哈希，之后再对哈希散列值进行编码。我们使用 MD5 作为哈希函数。
编码方式可以是 base36([a-z,0-9]) 或 base62([A-Z,a-z,0-9])，如果需要使用 '+' 与 '/'，则需要使用 Base64 进行编码。我们选择使用 base64 编码。
对于长 6 个字母的键，会有 亿个不同字符串。
对于长 8 个字母的键，会有 万亿个不同字符串。
假设 6 个字母的键已满足我们的要求。
MD5 产生的哈希值有 128 位。每个 base64 字符会编码 6 位哈希值，所以使用 base64 编码 128 位哈希值，会获得一个超过 21 个字符的字符串。由于短链接只有 6 个字符，我们可以使用编码字符串的前 6 位作为密钥。这样会导致重复密钥，为了解决这个问题，我们可以选择编码字符串中的其它字符或者交换一些字符。
算法缺陷
我们的方案存在以下几个问题：
- 不同用户输入相同 URL 时，他们会获得相同的短链接，这样是不能接受的。
- 未考虑 URL 中的一部分经过编码的问题。
解决方案
当用户输入相同 URL（包括不同用户输入相同 URL，以及相同用户输入部分编码后的 URL）时，我们可以在每个原始 URL 后增加一个递增的序列号使其唯一，然后生成一个哈希值。在存储时不需要存储添加到尾部的序列号。
这个方案需要注意控制不断递增的序列号不溢出，另外增加序列号会影响服务的性能。
另一个解决方案是将用户 ID（唯一）附加到原始 URL 中。如果用户未登录，则需要为用户生成唯一密钥，如果生成密钥之后依然存在重复链接，需要继续生成密钥，直到获得唯一的短链接。
生成离线密钥
我们可以创建一个独立的密钥生成服务（KGS），类似于发号器。
该服务可以提前生成随机的六位字符串并将其存在数据库中，每次当用户要生成短链接时，都将返回数据库中的一个字符串。这种方式不用对 URL 进行编码，并且不用担心重复。
KGS 可以使用两个表来存储密匙：一个表用于存储未使用的密钥，另一个存储已使用的密钥。当 KGS 将密钥提供给某个服务器之后，就可以将该密钥移动至已使用密钥表中。
KGS 可以始终将一些密钥保留在内存中，提高访问速度。对于加载到内存中的密钥，我们需要先将其移动到已使用密钥表中。如果 KGS 在将密钥标记为已使用与分配至服务器内存之间死亡，将会浪费一部分密钥。不过由于我们可以提前生成大量密钥，对于一部分丢失，是完全可以接受的。
关注问题
- 预先存储密钥的数据库大小
- KGS 单点故障问题
- 当多个服务器同时读取密钥时，如何解决并发问题，以防止取到重复的密钥
解决方案
-
使用 base64 编码，可以生成 67.8 billion个唯一的六位字符串密钥。假设我们存储数字字母都只需要一个字节，存储这些键需要的容量为：
- 可以为 KGS 准备一个备用副本。当主服务器死机时，备用服务器就可以接管服务。
- 由于 KGS 会预先分配一些密钥到内存中，所以单个服务器分配密钥时不会出现并发问题。关键在于 KGS 服务器向不同服务器分配密钥时，需要利用分布式锁控制分配密钥至不同服务器内存的操作。
数据分区
为了扩展数据库，我们需要进行数据分区，以便存储数十亿 URL 信息。
基于范围的分区
我们可以基于键的首字母分区。将字母 A 与 a 存在一个分区中，将 B 与 b 存在另一个分区中，依此类推。这种方法称为基于范围的分区。对于不经常出现的字母可以先组合到同一个数据库分区中。
这种方法的问题在于，它可能会导致数据库服务器不平衡，因为某个字母开头的链接会很多。
基于散列的分区
我们可以先对要存储的对象进行哈希计算，之后再根据分区数将 URL 随机分配到不同的分区中，比如设计哈希函数将任意对象映射为 [1...256] 之间的整数，该数字就代表存储对象的分区编号。
这种方法依赖于哈希算法的随机性来保障分区数据平衡性，不过我们也可以使用一致性哈希来解决哈希分布不均的问题。
缓存
我们可以缓存经常访问的 URL，使用 Redis 存储原始链接及其对应的短链接。在访问数据库之前，应用服务器可以先检查缓存中是否具有所需的 URL。
由计算得知，大概需要 170 GB 的内存来缓存 20% 的每日流量，这对于服务器来说不算问题。当数据占满缓存，并且我们要用较新的 URL 替换缓存时，我们需要使用缓存淘汰策略。对于我们的系统，使用 LRU 是合理的策略，这样我们会丢弃最近最少使用的 URL。
为了保证缓存服务器性能，我们可以使用 Redis Cluster 均衡负载。
负载均衡
系统中由三个位置可以设置负载均衡管理：
- 客户端与应用服务器之间
- 应用服务器与数据库服务器之间
- 应用服务器与缓存服务器之间
前期可以采用简单的轮询策略，这个策略实现很简单。对于已经宕机的服务器，负载均衡也会将其从循环中移除，停止向其发送任何流量。
但是当某个服务器过载或者运行缓慢时，轮询策略仍然会向其发送新请求。所以后期我们可以使用一致性哈希或者最小连接数法作为负载均衡算法。
数据清理
由于生成的短链接都是有一定有效期的，如果达到用户指定的到期时间时，链接该如何处理？
如果我们主动定时搜索过期链接并将其删除，会对数据库造成很大的压力。所以我们可以采取缓慢搜索加上延迟清理策略。
- 每当用户尝试访问过期的链接时，都可以删除该过期链接并返回错误给用户
- 可以在服务器用户流量较低时，运行一个轻量级的清理服务，从缓存及存储中删除过期链接
- 删除过期链接后，可以将密钥放回密钥数据库以便重新使用
网友评论