[系统设计]短链服务

[PeterChen1997]

在上一篇开篇文章中，针对 什么是系统设计，为什么要进行系统设计和从哪些角度和步骤思考系统设计 进行了一波简单的分析

本周的第一个实践从设计一个简单的短链服务开始

前言

短链接在我们的日常生活中随处可见，比如抖音、淘宝和 B 站等站点的对外分享链接。

【【LPL夏季赛TOP5】常规赛W8D4：骤雨急飘呼引狂刀 锁链命敌破其阵局-哔哩哔哩】https://b23.tv/vcDRbT

5👈信g6hgXPUBXJ2！ https://m.tb.cn/h.4APguQb?sm=dbd70d 【小狮子桌游】现代艺术 正版繁体中文附拍卖槌画架锤垫

当用户点击这些链接后，短链 URL 会通过服务端重定向到原始的 URL 上

• 原始 URL：https://www.bilibili.com/video/BV18b4y1z7sx?p=1&share_medium=android&share_plat=android&share_session_id=7f22a0ea-b397-48d8-8ce3-fbdf6ddeb5a8&share_source=COPY&share_tag=s_i&timestamp=1627715191&unique_k=vcDRbT
• 短链 URL：https://b23.tv/vcDRbT

这其中扮演关键角色的服务，即将网址从原始 URL 转换为短链 URL 的服务，就是短链服务

目前网上使用率比较高的一些在线短链服务如下，感兴趣的朋友可以尝试一下

• tinyURL
• is.gd
• 小码短链接
• 新浪短网址

一、需求分析

那么开始之前，我们可以简单思考一下：

• 我们真的需要短链服务来达到我们的目的吗
• 短链服务能够帮助我们解决什么问题
• 带来的收益和我们付出的成本是否匹配

我想了下，目的、问题、收益和成本 大概如下：

• 目的： 降低信息流动的阻力
• 问题： URL 过长导致信息流动受阻
  • 目前的网络链接（即通俗意义上的 URL）作为大部分浏览器识别信息的唯一载体，自身需要承载较多的页面信息、用户环境信息和自定义信息，而不断增多的互联网信息维度也会让 URL 不断变长，过长的 URL 可能会在传播的过程中被截断，导致链接失效或信息丢失
• 就拿分享这个功能来说，分享信息中至少需要携带：分享内容的主题和访问的方法，如果分享 URL 过长，除了可能导致用户对于链接的可用性产生怀疑，还可能由于设备访问窗口较小，导致文本顶部的分享主题信息超过设备窗口，从而导致用户的访问欲望大幅降低
• 收益：
  • 优化用户体验。 较短的 URL 也大大提高了用户输入的正确率
  • 可扩展性强。 URL 上往往需要携带大量的信息用于后续的数据统计，根据 URL 进行数据分析后的结果可以用于产品各方面的优化，在不断新增需求面前，短链可以保证 URL 在长度在稳定的范围内不受影响，可用于优化跨设备链接、跟踪单个链接以分析受众、衡量广告活动的效果或隐藏关联的原始 URL
  • **节省空间，增加文本信息容量。**在展示、打印、发送限制长度消息（微博等）的使用场景中，短链可以节省大量的空间
• **成本：**这个我们后面的内容会详细讨论

所以粗略来看，这个需求没有偏离解决问题的方向，值得尝试

二、需求功能确认

开始设计之前，我们需要明确我们设计系统所支持的功能和预期的目标

功能要求：

• 给定 URL，生成更短且唯一的短链 URL
• 当用户访问短链 URL 后，服务端可以重定向到原始 URL 上
• 支持用户自定义短链
• 链接在默认时间后过期，用户可以手动指定过期时间

非功能性要求：

• 系统高可用。短链服务一旦失效，所有短链都将无法访问
• URL 重定向时延短。时延过长会明显影响用户体验
• 短链应该是不可预测的。原理同 ID 生成，避免被轮询接口导致数据泄露

三、流量成本预估

这是服务设计最为关键的一个环节，成本的不同会直接影响后续的方案设计

读写估算

• **读写比例：**读大于写，假设比例为 100：1
• **流量估算：**预计每月制造 5亿 条短链
  • 写：
    • **次数：**5 亿次
    • **QPS：**5 亿 / (30 天 * 24 小时 * 3600 秒) = 200 calls / s
  • 读
    • **次数：**500 亿次
    • **QPS：**2 万 calls / s

存储估算

假设每条链接我们存储 5 年 时间

• **条数：**5 亿 * 5 年 * 12 月 = 300 亿条
• 大小：（假设每条 500B）500B * 300 亿 = 15 TB

带宽估算

• **写：**200 * 500B = 100 KB/s
• **读：**写 * 100 = 10 MB/s

内存估算

对于这么大量级的读服务，必然需要上个缓存，那么根据 2-8 法则，大概百分之二十的短链会被经常访问，那么来看看，我们假设只缓存这部分的内容，我们大概会需要多少内存

• **总条数：**2W * 3600秒 * 24 小时 = 17 亿
• **缓存条数：**17 亿 * 0.2 = 3.4 亿条
• **缓存内存：**3.4 亿 * 500B = 170 GB

这里 170G 使用量，假设的是 20%的访问都不重复，所以应该是最大值了，实际使用可能比这个小得多

总计

• 接口调用
  • 写调用：200 calls/s
  • 读调用：2W calls/s
• 流量
  • 入流量：100 KB/s
  • 出流量：10 MB/s
• 存储相关（存储五年）
  • 本地存储：15 TB
  • 内存缓存：170 GB

四、API 设计

一旦需求确定，先进行 API 设计是一个不错的选择， API 声明了系统可以对外提供的所有功能

API 仅支持写和删除即可，访问的重定向由服务处理即可，不需要提供接口

// 创建
function createURL(
    apiKey: string, // 调用凭证，可用于限制调用频率
    originURL: string, // 原始 URL
    customAlias: string, // 自定义 alias
    userName: string, // 用户名
    expire: string // 过期时间
): string {}

// 删除
function deleteURL(apiKey: string, urlKey: string): boolean {}

这里的 apiKey 属于附加特性了，如果仅希望提供简单的短链服务，可以不考虑 apiKey 的逻辑，但时只要支持了此特性，就可让系统低成本支持多调用方的流量调控

5. 数据库设计

进行数据库设计可以帮助我们更好地理解多个模块中的数据流向，并为后面的数据分区作铺垫

我们在前面的预估中了解到，此系统的存储部分具有以下几个特征：

• 存储上亿的数据
• 每条数据的体积很小
• 每条 URL 数据之间不存在关系，但是和用户数据存在关联
• 系统以读取为主

DB Schema

简单来看，我们所需的数据可以通过两张表来存储

关于数据库的选型，很明显选择非关系数据库（NoSQL）会是一个更好的选择。相比于关系数据库，非关系数据库在扩展上更具优势

六、基础系统设计与生成算法

在此系统中，比较复杂的点在于，如何通过一段 URL，生成一段唯一的 key 用于短链服务的识别，就比如 https://b23.tv/vcDRbT 中的 vcDRbT 就是唯一 key

业界的最优方案很多，这里简单介绍下面两个解决方案，大家可以参考一下其中的思路

1. 使用 Hash 算法编码实际 URL

我们可以使用一些常见的 Hash 算法来计算实际 URL 的编码（如 MD5、SHA256 等）

MD5("The quick brown fox jumps over the lazy dog")
= 9e107d9d372bb6826bd81d3542a419d6

这里 128 位的 MD5 散列被表示为32位十六进制(base16)数字，我们如果使用基于 base64 的编码规则（regex: [A-Za-z0-9+/] ），使用多少位表达 key 比较合适呢

我们预计存储的 key 在 300 亿条左右，那么基本上使用 6 位 表示即可（64^6=687亿）。假设我们使用 MD5 算法生成 key，那么我们至少会拿到 22 个字符（128/6=21.3）

如果使用 MD5 的话，根据功能需求不同，会存在一些 tradeoff：

• key 长度较长 （可以丢弃较长内容，但是生成的 key 可能会重复）
• 相同 url 携带了编码不同但含义相同的 query，生成的 key 不相同（问题不大，可以做一次编码转换）
  • A: www.baidu.com?id=123 ⇒ key: A
  • B: www.baidu.com%3Fid%3D123 ⇒ key：B
• 相同 url 生成的 key 相同 (问题不大，可以通过给生成函数传入的 key append 唯一值解决)

2. 使用 Key Generate Service 生成 key

如果我们拥有一套 key 生成服务，则可以在生成 URL key 的时候请求这个服务获取唯一的 Key

这个 KGS 可以再没请求之前存储一些独立的 key 到 key-DB 中，不仅通过避免编码优化了请求时的性能，还能够通过 DB 保证 key 的唯一性，并且生成的算法会更加简单，直接随机生成我们想要的六位数字符串即可

高并发场景

当 key 被使用后，key 就会从 DB 中被标记为使用过。在高并发的访问场景下，如果 KGS 拥有多个实例，如何保证每次返回的 key 在之前都没有被使用过呢。如果需要严格保证 key 的有效性，可以引入消息队列按顺序缓存所有请求，并异步返回

存储空间

按照我们需要的 687 亿个 keys 来看，每个 key 有六个 char，按一个 char 一个字节计算，大概需要 412GB 的 key-DB

自定义 alias

如果使用 KGS 支持自定义 alias，则尽量需要限制传入的字符串长度，避免导致 key-DB 过大

七、数据分区和复制

为了扩大我们的数据库的数据容量，我们需要使用数据划分来将数据分别存储在不同的 DB Server 上

这里简单介绍两种划分方案

1. 基于范围划分

比如根据字母划分分区，A(a) 字母开头的 key 一个分区，B(b) 字母开头的 key 一个分区。为了优化空间使用情况，还可以将多个低频字母合并为一个分区

这种划分方案可能 导致 DB server 的访问量级相差过大，导致服务负载不均。如果我们发现 A 字母开头的 key 占了50%，那么支持 A 分区的 DB 可能访问压力就会过大

2. 基于 Hash 划分

基于 Hash 划分相对于给予固定范围划分会更加均衡，但是依然会有上面方案的负载不均的问题

这里如果对于服务扩展性和稳定性要求较高，可以考虑使用一致性哈希解决，较为复杂，可以考虑查看下知乎的这篇文章

八、缓存

对于经常访问的 keys，我们可以使用 cache 缓存至内存，不仅可以加速查找效率，也可以降低 DB 的查询压力

需要多大的内存

前面根据 2-8 法则粗略计算过需要 170GB 的大小，一般的服务器内存能够支持到 256GB 的内存（王思聪最近装的电脑就用了32 条 64G 的内存），所以说绰绰有余

选取哪种缓存淘汰策略

Last Recently Used(LRU)会是比较合理的选择，相比 LFU 实现成本更低，LRU消耗CPU资源较少，LFU消耗CPU资源较多

整体携带缓存流程的工作流如下：

九、负载均衡

负载均衡层可以放在服务的各层之前，主要用来平衡实例之间的访问压力，并且在服务出现问题时，能够快速控制打向此服务的流量，保证服务可用性

现代的负载均衡服务，如 nginx，都支持了比较智能的健康监测算法，比如一台机器出现问题，根据不稳定的频率会自动控制访问的流量

http {
		# fail_timeout 和 max_fails 的默认值分别为 10s 和 1次
      upstream onmpw {
          server 192.168.144.128;
		 # 失败三次后，等待 30s 再次尝试
          server 192.168.144.132 max_fails=3 fail_timeout=30s;
		 # 失败两次后，等待默认时间后尝试
          server 192.168.144.131 max_fails=2;
      }
      server {
          listen 80;
          location / {
              proxy_pass http://onmpw;
          }
      }
  }

十、数据库清理

当用户设定的短链有效期到期后，DB 可以进行清理工作，避免过多的无效存储占用

删除可以用这两个方案中的一个：

• 懒清除。当用户访问，获取 keys 和对应的 URL 后，发现已经过期，则返回错误，并触发删除流程
• 定时任务。通过定时任务，确认 DB 中所有数据的过期状态，针对过期的数据进行清除，此过程可以选取低 DB 压力时进行

考虑到用户的访问频率基本都不是很高，选取后者可能是更为合理的一个选择

---

本期的系统设计分享就到这结束了，简单按步骤确认了下实现一个简单短链服务需要考虑的设计要点

其中关于 key 生成算法的内容比较简略，如果展开介绍可能内容就过多了，并且实用 KGS 随机生成也是一个不错的方案，毕竟最多也就是重试几次，在 key-DB 内多存储一些备用的 key，也能满足性能要求

后面如果有时间，会不定期更新这个栏目，感兴趣的朋友可以关注一波哈

参考链接

• 系统设计系列之如何设计一个短链服务
• 短网址服务系统如何设计
• 高性能短链设计