设计一个短 URL 系统

提出问题

短 URL 是互联网基础设施中最常见的服务之一：微博的 t.cn、淘宝的 tb.cn、腾讯的 url.cn，每天处理数十亿次重定向。面试官问这个题，表面考的是"怎么生成唯一的短码"，但真正的考点是：高并发读场景下的缓存策略、发号器的可用性、以及短码的安全性。短 URL 服务的核心链路很简单：用户提交长 URL → 系统生成短码 → 存储映射关系 → 访问时 302 重定向。但简单背后藏着三个棘手的工程问题：短码如何保证全局唯一且不可猜测？读多写少（一般是 99:1 甚至更高）的流量怎么抗百万 QPS？短码过期和回收怎么处理？

分析问题

短码生成方案选型

生成短码有三种主流方案，各有取舍。下面这张对比表可以帮你快速判断面试场景该选哪个：

方案	原理	碰撞风险	依赖	可用性	适用场景
Hash 截断法	MD5/SHA1 取前 6-8 位	极低（亿级数据约 0.03%）	无中心化依赖	客户端可离线计算	短 URL 生成不需要持久化的临时场景
发号器法	Snowflake / Leaf 自增 ID → Base62	零碰撞	依赖发号器高可用	发号器挂了整个服务不可用	生产环境 90% 以上的选择
预生成池法	提前在 Redis 生成一批短码	零碰撞	依赖池大小预判 + 异步补充	写入路径极快	写入 QPS > 10 万的高压场景

Hash 截断法：对长 URL 取 MD5 或 SHA1，截取前 6-8 位作为短码。优点是客户端可独立计算，无需中心化发号器。缺点是存在碰撞概率（虽然很低），且需要额外检测碰撞并加后缀重试。以 6 位 62 进制（a-z + A-Z + 0-9）为例，共 62^6 ≈ 568 亿种组合，碰撞概率在亿级数据量下约 0.03%，但一旦碰撞，两个不同的长 URL 会映射到同一个短码，后写入的覆盖前者，导致旧短码跳到一个错误的长 URL。

import hashlib, base64

def generate_short_code(url: str, length: int = 6) -> str:
    # MD5 取前 6 字节，Base64 编码后截取
    md5_bytes = hashlib.md5(url.encode()).digest()[:6]
    code = base64.urlsafe_b64encode(md5_bytes).decode().rstrip('=')[:length]
    return code

发号器法：用 Snowflake 或 DB 自增 ID 生成唯一 ID，再转 62 进制编码为短码。天然无碰撞，但依赖发号器可用性。Google 的短链接服务就用了类似方案。发号器一旦故障，整个服务不可用，所以发号器本身需要高可用（如 Leaf 的双 Buffer 预加载）。

预生成池法：提前在 Redis 或 DB 中维护一批预生成短码，取用时直接标记，减少实时写入路径。适合写入压力大但可用性要求极高的场景，但预生成池大小需要提前估算。池大小估算公式：pool_size = peak_write_QPS × max_allowed_latency_ms。例如峰值写入 5 万 QPS、允许 50ms 延迟，池至少需要 2500 个短码的缓冲。

实际生产多用发号器 + 混淆位：用 Leaf 发号器拿到 ID，转 Base62 后再 XOR 一个固定掩码，使短码看起来随机，防止遍历爬取。Leaf 发号器的核心流程：

用户请求短码生成
  → Leaf 发号器从 DB 获取当前 segment（号段，如 [1000000, 2000000)）
  → 内存中递增分配，双 Buffer 异步预加载下一个 segment
  → 分配到的 ID 与掩码 XOR 混淆
  → 转 Base62 得到短码
  → 写 DB 持久化映射
  → 写缓存
  → 返回短码

缓存策略：读多写少的极致优化

短 URL 的访问模式是极端的读多写少——一个短码可能被访问数十万次，但只被创建一次。以微博 t.cn 的真实数据为例：一条热门微博的短链接在发布后 1 小时内被访问超过 50 万次，但该短码只被创建一次。写入与读取的比例约为 1:10000。

缓存策略遵循 Cache Aside 模式：

// 伪代码：短 URL 查询
public String getLongUrl(String shortCode) {
    // 1. 查缓存
    String longUrl = redis.get("short:" + shortCode);
    if (longUrl != null) return longUrl;

    // 2. 缓存未命中，查 DB
    longUrl = db.query("SELECT long_url FROM short_url_map WHERE short_code = ?", shortCode);
    if (longUrl == null) {
        return null; // 或 404
    }

    // 3. 回写缓存，设置 TTL
    redis.setex("short:" + shortCode, 86400, longUrl);
    return longUrl;
}

缓存命中率可以达到 99%+，因为每个短码被大量访问。但这里有个坑：缓存 TTL 设置不当会导致缓存雪崩。如果所有短码缓存都设置了相同的 TTL（比如 86400 秒），那么每天同一时刻大量缓存同时过期，瞬间的 DB 压力会把 MySQL 打爆。解决方案是缓存 TTL 加随机偏移，如 86400 + rand(0, 3600)，让过期时间均匀分布。

缓存穿透保护：如果查询的短码本身不存在（恶意攻击随机短码，每秒扫 10 万次），每次都会穿透到 DB。解决方案是布隆过滤器（Bloom Filter）加一层前置拦截，判断短码是不是已知的。布隆过滤器的三个参数需要根据数据量调优：

# 布隆过滤器参数计算
import math

n = 10_000_000  # 预期的短码总数
p = 0.0001      # 期望的误判率

# 位数组大小
m = int(-n * math.log(p) / (math.log(2) ** 2))  # ≈ 1.7 亿位 ≈ 20MB
# 哈希函数个数
k = int(m / n * math.log(2))  # ≈ 13

布隆过滤器只占用 20MB 内存，就能以 0.01% 的误判率过滤 1000 万短码。存在误判的短码会穿透到 DB（每天约 864 次），但 DB 完全可以承受。

短码安全与可猜测性

发号器生成的自增 ID 转 62 进制后，短码是严格递增的：aaaaaa → aaaaab。攻击者只要知道一个短码，就能遍历前后所有短码，爬取所有长 URL。现实案例：某知名短 URL 服务因为短码纯递增，被安全研究人员爬取了 30 万条短 URL 映射，暴露了用户隐私数据。

# Base62 编码函数
BASE62 = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"

def id_to_base62(num: int) -> str:
    if num == 0: return BASE62[0]
    chars = []
    while num > 0:
        chars.append(BASE62[num % 62])
        num //= 62
    return ''.join(reversed(chars))

假设发号器从 1 开始，连续发 10 个短码：

• 1 → b → 302 跳转到用户 A 的私人链接
• 2 → c → 302 跳转到用户 B 的账单页面
• 攻击者只需要知道 b，就能猜到 c、d 直到 000001，全部爬一遍。

解决方案：ID 混淆。在发号器拿到 ID 后，与一个固定掩码 XOR，再转 Base62。这样短码不再是递增的，而是看起来随机。掩码需要固定且不可逆推（如用 HMAC 派生的掩码）：

# ID 混淆示例
MASK = 0xDEADBEEF_CAFEBABE  # 64 位掩码，由 HMAC-SHA256 派生

def obfuscate_id(original_id: int) -> int:
    # 先 XOR 掩码，再乘以一个奇数（可逆乘）
    return (original_id ^ MASK) * 0x9E3779B97F4A7C15  # 黄金分割倒数

def deobfuscate_id(obfuscated_id: int) -> int:
    # 逆运算
    return ((obfuscated_id * 0xBF58476D1CE4E5B9) & 0xFFFFFFFFFFFFFFFF) ^ MASK

另一个方案是随机化发号：发号器不连续递增，而是步长随机（如每次 + 一个 1-1000 的随机数），牺牲一点 ID 空间利用率换取不可猜测性。

短码过期与回收

短码不是永久有效的。业务上需要支持 TTL 机制：营销链接有效 7 天、临时链接有效 24 小时。过期后短码可以被回收重用，但回收前必须确保旧映射已被清除或用 410 告知"已过期"。这里有个常见的生产事故陷阱：回收后新用户可能拿到旧用户用过的短码。如果旧用户发过一条微博用了这个短码，回收后新用户的内容可能被误关联。某短 URL 服务确实出过这样的问题——一个旧短码被回收后，新用户用它指向另一个页面，导致旧用户分享的链接跳转到不相关的页面，最终被用户投诉。

所以大厂的做法是短码一生只绑定一个长 URL，永不回收，只用业务层的 TTL 做 302 → 410 的切换，短码本身不释放。DB 中保留 short_code, long_url, expired_at, status 四列，status 标记 ACTIVE 或 EXPIRED，过期后返回 HTTP 410 Gone，不再分配新短码。

一致性保证：发号器与 DB 写

短 URL 系统在写入时有一个关键的一致性要求：短码一旦返回给用户，必须保证它在 DB 中已持久化。如果写入 DB 后返回给用户，但缓存未写入，用户访问时缓存未命中就会查 DB——这没问题。但如果反过来：先写缓存后写 DB，缓存写成功后服务宕机，DB 没写，用户访问时缓存命中但 DB 里没有，这种情况就叫数据丢失。

正确的写入顺序是：先写 DB，再写缓存。写 DB 失败则返回错误，用户拿不到短码，不会产生脏数据。

100 万 QPS 怎么扛

假设日活用户 1 亿，每人每天点 10 次短链接，总 QPS 约 11500。但峰值可能是平均值的 10 倍（比如微博热搜事件），需要考虑 10 万+ QPS 的流量。

分层架构：

• CDN 层：对短 URL 的 302 响应可以做 CDN 边缘缓存，但 CDN 通常不缓存 302，需要 CDN 厂商支持。不支持的场景下，需要 Nginx 层做 Lua 缓存。
• Nginx + Lua 层：在 Nginx 用 Lua 脚本直接读本地 Redis 缓存，不走 Java 应用层。QPS 可以从 5 万提升到 30 万+。
• Redis 主从集群：缓存命中率 99%+，单机 Redis 扛 10 万 QPS。读多写少场景下，Redis 主从 + 哨兵模式完全够用，不需要 Redis Cluster。
• MySQL 落库：写入量低（每天几百万条），MySQL 单库完全扛得住。分表按 short_code 哈希分 64 张表，每张表不到 1000 万数据。

总结

短 URL 系统的设计重心不在"短码怎么生成"（那是基本功），而在缓存策略、安全性和可用性。关键点：

• 发号器优先选 Leaf-segment 方案，天然无碰撞且支持高可用
• 短码必须加混淆位，禁止纯递增 Base62。面试时主动提混淆方案是加分项
• 缓存用 Cache Aside + 布隆过滤器防穿透，命中率 99%+
• 缓存 TTL 加随机偏移，防止雪崩
• 短码不回收，只做业务层 TTL 过期提示，返回 HTTP 410
• 写入顺序：先 DB 后缓存，不允许反序
• 读多写少场景下，Nginx Lua + Redis 主从 + MySQL 分表是最优解，不需要引入 ES 等复杂组件
• 分层架构可扛 10 万+ QPS，瓶颈在 MySQL 写入而非读取

参考：微博短 URL 实现、TinyURL 设计、美团 Leaf 发号器、布隆过滤器参数调优实践