专业书籍精读 · System Design Interview 卷一 · 第 8 章
System Design Interview Vol 1 · Ch 8 · Alex Xu · 2020
你在社交平台上贴一条长得吓人的链接，发出去往往变成七八个字符的小尾巴。《System Design Interview》第 8 章就是让你从零造出这么一个服务：把长网址换成短网址，再在有人点击时把他送回原处。题面小得像道作业题，骨架却最清楚——一张对照表、一个发号器、一层缓存，大系统的三大件全在里面。
把它想成商场的寄存处：你把厚大衣（长网址）交过去，柜台给你一张小小的号码牌（短网址）。号码牌上没有任何关于大衣的信息——它薄薄一张，全靠柜台那本账本把号码和大衣一一对上。所以这门生意的全部本事就两件：发牌子的规矩，和那本永远不能弄丢的账本。
难点在三个要求同时成立：牌子要短到人能顺手抄下来（七个字符上下）；十年下来几千亿张牌一张也不能重号；而且几个发牌柜台之间最好别互相打招呼——一问一答就慢了。
还有个容易被忽略的性质：这门生意是极端的写一次、读很多次。一条链接登记一次，可能被点上万次。设计的重心因此天然压在「被点击」那一侧，而不是「被创建」那一侧。
第一种，把大衣揉出一个指纹：对长网址算一个特征值，截前七位当牌号。快，但两件不同的大衣可能算出同一个指纹——撞上了就改一改重算，直到不撞为止。
第二种，先领个流水号，再换种写法：柜台按顺序发 1、2、3……然后把这个十进制数字改写成一种更省位数的记法——只用 0-9、a-z、A-Z 这 62 个符号（就像把十进制写成十六进制，符号多了、位数就短了）。62 个符号排七位，能表示三万五千亿个牌号，够用几百年。
既然一万次点击才对应一次登记，柜台不必每次都翻账本：把最近最常被问到的那些「号码牌—大衣」对应关系抄一份放在手边，绝大多数人来了当场就能答上，只有冷门号码才去翻账本。这一摞抄本就是缓存，而它答上来的比例，几乎直接等于你的服务器账单。
把人送走的时候，你可以说两种话。说「这地方永久搬走了」——浏览器会记住，下次他直接飞过去、不再经过你，你省了机器；但你也永远数不到这次点击。说「暂时去那边一趟」——每次点击都还得经过你，你能完整记下谁在什么时候点了什么，代价是这些流量全得自己扛。要数据还是要省钱，只能挑一个。
诚实说一句代价：这本账本你得永远维护下去——服务一旦关停，全世界散落各处的短链会在同一天集体变成死链。
短网址服务的本质是一本不能丢的账本：发牌要短且不重号，读远多于写所以缓存决定成本，而跳转时说「永久」还是「暂时」，就是在省服务器和要点击数据之间二选一。
想进到具体机制、记号和示意图？ → 切到精读版
这道题的考点不在「怎么变短」，而在它是「一张 key→value 映射表 + 一个发号器 + 一层缓存」的最小完整形态：把每天 1 亿条、读写比 10:1、十年 3650 亿条这几个数摆上桌，短链长度、要不要缓存、怎么分片全都是被数字倒推出来的；而重定向该用 301 还是 302 这一行状态码，直接决定你是省服务器还是拿得到点击数据。
tiny.url/2TX），它不包含原地址的任何信息，只是映射表里的一把钥匙。Location 头，告诉浏览器「真正的东西在那边，你自己再去一趟」。301 / 302：两种重定向状态码。301 = 永久搬迁（浏览器可缓存这条跳转），302 = 临时跳转（浏览器每次仍来问）。0-9 a-z A-Z 共 62 个符号表示数字的写法。符号越多、同一个数写出来位数越少——和十进制写成十六进制是同一回事。本章位于卷一 Part II「系统案例」，紧接 Ch 7「分布式唯一 ID」——那一章发出来的 ID，正是这一章用来编码短码的原料；它也是 Ch 11 信息流、Ch 12 聊天这些大题之前，最适合完整跑一遍四步法（澄清需求 → 高层设计 → 深挖 → 收尾）的小题。对应现实里 bit.ly、t.co 这类链接服务，以及公司内网的 go/ 短链。
先把题目变成数字——这一步才是本章真正的骨架。书里给的假设：每天生成 1 亿 条短链，读写比 10:1，服务至少跑 10 年，平均一条记录 100 字节。由此：
1160/秒；读 QPS ≈ 11600/秒。3650 亿 条记录。36.5 TB。三个数字各自逼出一个不可回避的约束：3650 亿决定了短码至少要能编出这么多个（下一节会看到 6 位不够、7 位刚好）；11600 读/秒且全是按主键点查决定了必须有缓存层；36.5 TB 决定了单机放不下、要分片。
不做这一步会怎样？你会凭手感说「就用 6 位吧」，然后在第 156 亿条链接上撞到号段耗尽；或者把 11600 QPS 直接怼到数据库上，用十倍的机器买一件缓存本该白送的事。这题看着像哈希函数选型题，其实是容量估算题。
整个服务对外只有两个接口：POST /api/v1/data/shorten（收长网址、返回短网址），和 GET /api/v1/{shortUrl}（收短网址、回一个重定向）。写路径每天跑 1 亿次，读路径跑 10 亿次——两条路径的频次差一个数量级，优化的注意力也该差一个数量级。
短码用 base62——0-9 a-z A-Z 共 62 个符号。为什么不用 base64？因为 base64 的 + 和 / 在 URL 里要转义，反而更长更难抄。
剩下就是一道算术：需要能编 3650 亿个。62⁶ ≈ 568 亿——不够；62⁷ ≈ 3.5 万亿——够，还留了近十倍余量。所以短码取 7 位。这个「7」不是拍脑袋，是从十年容量推回来的。
路线 A：哈希 + 碰撞解决。拿 CRC32 / MD5 / SHA-1 之类对长网址求哈希，截取前 7 位当短码。麻烦在于碰撞：不同长网址可能截出同一串。书里的做法是撞了就在长网址后面拼一个预定字符串再哈希，循环直到不撞。这意味着每发一个号都要先查一次库确认没被占——而这正是布隆过滤器的用武之地：它能以极小内存挡掉绝大多数「其实不存在」的查询，把回表次数压下去。
路线 B：唯一 ID 转 base62。先向发号器（如上一章的 Snowflake）要一个全局唯一 ID，再把它转成 base62。天生不会碰撞，因此完全不用查库，写路径只剩一次插入。代价是：ID 递增 ⇒ 短码可枚举，而且长度随 ID 增长（早期短、后期长），不再是整齐的 7 位。
还有一个书里在深挖流程中点到、面试里常被追问的细节：同一个长网址被提交两次，要不要返回同一个短码？路线 A 天然幂等（同样的输入哈希出同样的码）；路线 B 想做到就得额外维护一张 长网址 → 短码 的反查索引，存储和写放大都要加一份。
读侧的负载画像好得不能再好：按主键点查、value 几乎永不变更、访问高度倾斜（少数链接吃掉绝大多数点击）。这三条加起来，缓存几乎是白送的性能。因为映射一旦写入就不再修改，可以放心设很长的过期时间，用 LRU 淘汰冷链接即可，不必操心缓存一致性。
算一笔账就知道这层有多值钱：读侧 11600 QPS，命中率 90% 时落到数据库的只有 1160 QPS；命中率掉到 50%，数据库就要扛 5800 QPS——同一套硬件，命中率差 40 个百分点，数据库压力差 5 倍。短链服务的成本曲线，基本就是这条命中率曲线。
301 还是 302：一行状态码，两种生意这是本章最容易被当成细节、实际上决定商业模式的一处选择。301 告诉浏览器「永久搬迁」，浏览器会缓存这条跳转——从第二次点击起，请求根本不再到达你的服务器。服务器负载显著下降，但你也彻底失去了后续所有点击数据。302 告诉浏览器「临时跳转」，每次点击都要先回到你这里，你能记下完整点击流（时间、来源、地域），代价是这些流量一次不落全归你扛。
限流。写接口不限流，一个脚本一小时就能把你的号段和存储吃掉——按 IP 或 API key 做速率限制，是这道题「收尾」环节的标准答案。无状态扩展。Web 层不存会话，直接加机器；真正有状态的只有发号器和数据库。分片。36.5 TB 单机放不下，按短码哈希分片即可——读全是点查、不需要范围扫描，这是最容易分的一类负载。
表 1 · 两种发号路线：哈希截断 vs 唯一 ID 转 base62
| 哈希 + 碰撞解决 | 唯一 ID → base62 | |
|---|---|---|
| 短码长度 | 固定 7 位，整齐 | 随 ID 增长而变长，早期短、后期长 |
| 写路径开销 | 每次需查库确认未占用（可用布隆过滤器挡掉大部分） | 不用查库，一次插入即可 |
| 碰撞 | 必须处理：拼预定串重哈希，直到不撞 | 不存在——ID 本就唯一 |
| 可枚举性 | 短码分散，不易顺序猜到 | 递增 ID ⇒ 短码可枚举，能推出下一个 |
| 幂等 | 天然：同一长网址恒得同一短码 | 需额外维护「长网址 → 短码」反查表 |
| 依赖 | 只依赖哈希函数 | 依赖一个可用的分布式发号器（Ch 7） |
表 2 · 301 vs 302：一行状态码定生意
301 永久 | 302 临时 | |
|---|---|---|
| 浏览器行为 | 缓存该跳转，第二次起不再请求你 | 每次都回你的服务器问一遍 |
| 服务器负载 | 显著降低（热门链接尤其明显） | 全量点击都要接住 |
| 点击分析 | 基本丢失，只数得到首次 | 完整点击流：时间、来源、地域 |
| 改目标地址 | 难——已缓存的浏览器可能长期不回来问 | 随时可改，下次点击即生效 |
| 适用 | 内部 go/ 短链、纯导航、不在乎数据 | 商业短链、营销投放、反滥用监控 |
tiny.url/mycompany 会带来命名空间争抢与抢注问题，还得单独一套占位与审核；书里的基础设计不含这一层。短网址是面试里出现频率最高的「小题」之一，但它考的东西一点不小：面试官真正看的是你会不会从几个数字倒推出设计，而不是你会不会背 base62。它也是极少数能在 45 分钟里完整走完四步法、还能深挖出真实取舍的题目。
落到真实系统，这套骨架就是 bit.ly、t.co 这类链接服务的核心：一张巨大的映射表、一层高命中率缓存、一个发号器，外加围绕点击流做起来的分析业务。而它最被低估的一条性质是：短链的价值 100% 押在那张映射表的持久性上——短码本身不含任何信息，服务停了，链接就是一串无意义字符。
10%——碰撞不是罕见事件，是每十次发号就会遇到一次的常态。碰撞处理是主路径，不是边角料。301 发出去就很难收回。浏览器可能长期持有缓存，之后想改目标地址、想加安全拦截，都触达不到那批用户。36.5 TB 是裸记录，短码主键索引、以及路线 B 需要的「长网址 → 短码」反查表都要另加。① 短网址服务的本体是一张 短码 → 长网址 的映射表；短码不含原地址信息，价值全押在这张表的持久性上。
② 全部设计由容量估算倒推：1 亿条/天 → 写 1160 QPS；读写比 10:1 → 读 11600 QPS；十年 3650 亿 条；36.5 TB。
③ 短码取 7 位是算出来的：62⁶ ≈ 568 亿 不够，62⁷ ≈ 3.5 万亿 够。base62 而非 base64，因为 + / 在 URL 里要转义。
④ 发号两条路：哈希截断 + 碰撞解决（长度固定、天然幂等、但每次要查库）vs 唯一 ID 转 base62（不碰撞、不查库、但可枚举且长度会变）。
⑤ 读路径是点查 + 值不可变 + 访问倾斜的完美缓存场景；命中率从 90% 掉到 50%，数据库压力涨 5 倍。
⑥ 301 vs 302 是本章最容易被忽略的商业决策：省服务器 vs 拿点击数据，二选一。
⑦ 收尾三件事：写接口限流防刷、Web 层无状态易扩、按短码哈希分片撑住 36.5 TB。
⑧ 最大的误区是把短码当秘密——短链服务从设计上就不提供保密性，安全得靠目标资源自己的鉴权。