第 3 章 / 共 57 章 · 约 7 分钟
案例 1：短链接服务
先花 10 分钟自己设计：需求、核心实体、API 和高层架构，各写几行。写完或者跳过之后，下面的讲解才会展开。
先写你的思路
只存在这台设备上；登录后会存进你的账号。
短链接是系统设计面试里最常见的“热身题”。业务逻辑几乎为零，所以面试官真正考的是：你能不能把一个简单需求拆清楚，算清读写比，讲明白 ID 怎么生成，以及热路径怎么做到毫秒级。
1. 需求澄清
功能需求
- 输入长链接，返回短链接；可选自定义别名（custom alias）和过期时间
- 访问短链接时重定向到原始地址
- （可选）点击统计：次数、来源、地区
非功能需求
- 重定向延迟低：服务端 p99 在 10~20 ms 级别（不含公网往返）
- 高可用：短链一旦失效，别人发出去的推文、邮件里的链接全部变成死链
- 读远多于写，假设 100:1
- 统计数据允许最终一致；短码不应被轻易顺序枚举
同时说清楚不做什么：用户体系、链接编辑、付费功能都放到范围外。这一步能帮你把时间留给真正的考点。
2. 容量估算
| 指标 | 估算 |
|---|---|
| 新建 | 1 亿条/天 ≈ 1.2k QPS，峰值按 3 倍 ≈ 3.5k |
| 重定向 | 100 亿次/天 ≈ 115k QPS，峰值 ≈ 350k |
| 单条大小 | 长 URL + 元数据 ≈ 500 B |
| 存储 | 50 GB/天，5 年 ≈ 90 TB（不含副本） |
短码长度：Base62（a-z、A-Z、0-9）7 位可表示 62^7 ≈ 3.5 万亿个；5 年总量约 1800 亿，只占约 5%，足够。估算的目的是得出结论：单机数据库存不下，读路径必须靠缓存扛。
3. API
POST /v1/links
body: { long_url, custom_alias?, expires_at? }
201 → { code, short_url }
GET /{code}
302 Location: <long_url> // 不存在或已过期返回 404
301 还是 302？ 301 是永久重定向，浏览器会缓存，之后的点击不再经过你的服务器：省流量，但统计不到，也无法中途下线恶意链接。302/307 每次都回源，方便统计和管控。大多数商业短链选 302，这是一个值得主动说出来的取舍。
4. 数据模型
links
code string PK -- 7 位 Base62
long_url string
owner_id string
created_at timestamp
expires_at timestamp NULL
访问模式只有“按 code 点查”，没有 join，也没有范围查询，因此 KV 存储（DynamoDB、Cassandra）或按 hash(code) 分片的 MySQL 都合适。说清选择理由比选哪个更重要。
5. 高层架构
查看图表源码
flowchart LR
accTitle: 短链接：写路径与读路径
c1["Client（创建）"] --> lb["LB"] --> linksvc["Link Service"] --> gen["短码生成"] --> kv[("KV Store")]
c2["Client（点击）"] --> cdn["CDN/Edge"] --> redirect["Redirect Service"] --> redis[("Redis")]
redis -->|"miss"| kv
redirect --> evt["点击事件"] --> kafka["Kafka"] --> stats["统计管道"]
写服务和重定向服务分开部署：两者 QPS 相差两个数量级，扩缩容策略完全不同。
读路径最前面的 CDN/Edge 要和统计、下线放在一起考虑。CDN 一旦缓存了 302，命中边缘的点击根本到不了 Redirect Service，统计会漏掉；下线恶意链接也得先清 CDN。三种做法任选其一，并在面试里说清楚：
- 重定向响应带
Cache-Control: private, no-store，CDN 只负责 TLS 终止和抗 DDoS，不缓存重定向 - 允许边缘缓存，但 TTL 很短（比如 60 秒），点击统计改用 CDN 访问日志或边缘函数上报
- 下线链接时调用 CDN 的 purge 接口主动清除
本文默认第 1 种：每次点击都经过 Redirect Service，由它投递点击事件。
6. 深入讨论
6.1 短码生成（核心考点）
| 方案 | 做法 | 优点 | 问题 |
|---|---|---|---|
| 哈希截断 | MD5(url) 取若干位转 Base62，截成 7 位 | 无状态 | 必然有碰撞，要查重重试；同一 URL 总得到同一码，按用户区分需加盐 |
| 全局自增 + Base62 | 自增 ID 转 62 进制 | 无碰撞 | 中心化计数器是单点；码连续，可被枚举 |
| 号段（range） | 每台机器从 ZooKeeper/DB 领一段，如 1000 个 | 无碰撞，几乎不需协调 | 机器宕机浪费号段（可接受）；仍需打散 |
| 随机 + 条件写 | 随机 7 位，PUT IF NOT EXISTS | 实现最简单，不可预测 | 占用率越高碰撞越多，需监控 |
推荐答案之一：号段计数器 + 可逆打散。对 ID 做一次双射置换（例如乘以一个与 62^7 互质的数再取模，或用小型 Feistel 网络），既保证唯一，又让相邻 ID 生成的码看起来随机。注意这不是加密，只是防止被肉眼顺序枚举。另一种同样站得住的答案是“随机 + 条件写”：5% 占用率下首次碰撞概率约 5%，重试一次基本就能成功。
6.2 读路径
- Cache-aside：先查 Redis，未命中再查 KV 并回填。按二八分布，缓存 20% 的热点链接就能覆盖大部分流量。
- 负缓存：不存在的 code 也缓存一个短 TTL 的空值，或在存储前放布隆过滤器，防止有人用随机 code 打穿数据库。布隆过滤器的规模要先算：5 年 1800 亿个 key、1% 误判率，大约需要 200 GB，必须按 code 分片；标准布隆过滤器也不支持删除，过期的短码要靠 counting 布隆过滤器或定期重建来清掉。对异常来源 IP 限流可以同时使用。
- 爆款链接：进程内 LRU 兜底，避免单个 Redis 分片过热。
6.3 自定义别名：依赖存储的唯一约束（条件写）解决并发抢注；为避免与生成码冲突，可要求别名长度不等于 7，或使用保留前缀。
6.4 过期：读取时检查 expires_at 保证正确性；后台依靠存储自带 TTL 或批处理任务删除。
6.5 统计：重定向服务只往 Kafka 异步投递事件，绝不能同步写统计库，否则统计系统一抖动就会拖垮主链路。
6.6 防滥用：创建接口限流；对长链接做异步恶意网址检测，命中后封禁 code 并清除 Redis 缓存，如果 CDN 也缓存了重定向还要 purge（这也是选 302 的理由之一）。
6.7 多区域：重定向是全球流量，可以在每个区域部署只读副本和缓存，写入集中到主区域；或者给每个区域分配互不重叠的号段，让各区域独立生成短码而不冲突。新建链接复制到其他区域可能有几百毫秒延迟，本地读不到时回源主区域即可。
7. 关键取舍
- 301 省成本 vs 302 可控、可统计
- 计数器无碰撞 vs 随机码不可预测
- 别名唯一性要强一致 vs 统计数据最终一致
8. 常见追问
- 同一个长链接重复提交，要返回同一个短码吗？ 取决于产品。若要去重，就需要一张
hash(long_url) → code的反向索引，多一次写入，也多一个一致性问题；多数场景直接生成新码更简单，也方便按用户分别统计。 - 怎么统计独立访客（UV）？ 精确去重成本高，可以用 HyperLogLog 按天近似计数，约 1% 的误差在统计场景完全可以接受。
- 存储挂了还能重定向吗？ 热点链接仍在缓存里，大部分流量不受影响；可以适当拉长缓存 TTL，存储故障期间继续返回旧值（serve stale），先保可用。
9. 回答分级
Bad：开口就是“MD5 存 MySQL”；没有估算；不提碰撞；统计在重定向时同步写库；缓存只有一句“加个 Redis”。
Good：需求清晰；算出 7 位 Base62 够用；读写服务分离；cache-aside；讲清 301/302；至少对比两种短码生成方案。
Great：用数字论证选型（碰撞率、号段大小）；主动提出枚举风险和可逆打散；考虑负缓存、热点链接；说明号段服务宕机时各节点仍持有剩余号段可继续工作；也清楚哪些地方不值得过度设计。
10. 不同级别的期望
| 级别 | 期望 |
|---|---|
| Mid（L4） | 在提示下给出完整可用的设计，API、数据模型、缓存都正确 |
| Senior（L5） | 自己驱动节奏，量化论证生成方案，主动找出读路径瓶颈并深入 1~2 个点 |
| Staff（L6+） | 从业务出发谈取舍（统计 vs 成本、滥用治理），覆盖多区域部署、故障模式和演进路径，并说明哪里刻意保持简单 |
11. 面试节奏建议
45 分钟里，需求和估算控制在 8 分钟以内，API 与数据模型约 5 分钟，高层架构约 10 分钟，剩下的时间留给短码生成和读路径这两个深入点。估算的作用是支撑结论，不是展示算术，算到能做决定就停。