约 12 分钟5 张卡

短链接设计

短链接服务保存“短码 → 目标 URL”的映射，访问短码时，通过 HTTP 重定向让客户端前往目标地址。长 URL 并没有被压缩到几个字符里；短码只是查询映射的键，映射丢失后通常无法靠短码恢复原地址。

设计重点在于映射的生命周期：并发创建时不能覆盖别人的链接，返回成功后映射应能继续查询，禁用或过期后也不能被旧缓存长期放行。短码算法、数据库、缓存和跳转响应需要一起满足这些要求。

1. 面试核心

先记住这几条，再读正文

先确定短码唯一范围、目标是否可修改、过期与禁用的生效要求，再设计创建和跳转链路。卡 · 综合题
Base62 是表示方法，不负责制造唯一性。随机或截断哈希方案需要原子唯一约束和有界冲突重试，不能先查不存在就直接覆盖写入。卡 · Base62、编号与随机码
同一次请求重试，与两次创建同一个 URL，是不同的重复问题。前者使用幂等键；后者是否合并由产品语义决定。卡 · 创建流程与重复请求
可变映射可以选择临时重定向，但状态码不能代替缓存策略。禁用要求要同时覆盖服务端缓存和浏览器、CDN 中的跳转响应。卡 · 跳转与失效
缓存减少重复查询，不证明数据库一定承受不了某个 QPS。容量判断要结合索引、负载、延迟目标及缓存故障后的回源量。卡 · 综合题

2. 需求与容量假设

卡 · 短链接生成系统的核心流程是什么？卡 · 加入缓存后，怎样判断短链接服务能否承受热点与缓存故障？

先约定本文的场景：公开短链接使用同一个短域名，短码区分大小写；创建后目标 URL 不修改，但允许提前禁用和设置过期时间。不同创建可以指向同一个 URL，已经使用的短码不重新分配给其他目标。跳转入口只接受 GET 和 HEAD，不承担表单提交或任意 HTTP 方法转发。

目标不修改可以减少缓存更新，但禁用状态仍会变化。普通业务可以约定有限的禁用传播窗口；要求禁用提交后新请求立即不再跳转时，需要查询足够新的权威状态或采用满足该要求的同步协议，不能仅依赖异步删缓存。已经发给客户端的目标地址无法被收回。

假设每天新增 100 万条映射，保留一年可查询数据，每天有 1 亿次跳转，峰值是日均的 10 倍。以下只是估算输入，不是产品实测：

项目	计算	结果
日均创建速率	`1,000,000 / 86,400`	约 11.6 次/秒
日均跳转速率	`100,000,000 / 86,400`	约 1157 次/秒
假定峰值跳转速率	日均的 10 倍	约 1.16 万次/秒
一年映射数量	`1,000,000 × 365`	3.65 亿条
每条按 500 字节估算的逻辑数据	`365,000,000 × 500`	约 182.5 GB，十进制

500 字节是假设的平均记录大小，不包含索引、复制、日志、备份和存储引擎开销。URL 长度分布会明显改变结果。不复用短码还意味着过期记录即使移除目标信息，也要保留已用码的占用记录，或使用能够保证不重复分配的编号机制；这部分状态会继续增长。

若峰值约 1.16 万次/秒，命中率为 99%，理想情况下正常回源约为 116 次/秒；缓存不可用时，回源可能接近全部流量。因此不能只按命中后的数字配置数据库。更完整的估算方法见容量规划。

3. 映射与短码

卡 · 短码生成使用什么算法？哈希碰撞时怎样处理？

3.1 数据归属与查询键

权威存储至少保存 code、target_url、expires_at 和 state，管理功能还需要创建者和创建时间。跳转按 code 精确查询，唯一约束也落在 code 上。若多个短域名允许重复使用相同短码，唯一键应改为“域名与短码”的组合，缓存键与路由规则也要使用同一个范围。

数据库、缓存和入口路由必须一致地区分大小写。若算法生成 Ab12 和 ab12 两个码，数据库却按不区分大小写的规则比较，名义上的 62 字符空间就与实际约束不一致。

本方案先以同一个权威写入范围保证唯一性。将来按短码分片时，同一个码必须确定地路由到同一分片，并在迁移期间维持该约束。随机选一个分库再检查本库是否冲突，不能保证整个短域名下唯一。

3.2 Base62、编号与随机码

Base62 用数字、小写字母和大写字母共 62 个字符表示值。固定 8 位且区分大小写时，有 62^8 = 218,340,105,584,896 种字符串。它只是编码空间，不表示这些字符串已经被安全地分配。

方案	唯一性从哪里来	需要处理什么
唯一整数转 Base62	原整数的分配机制与无损编码	分配方故障、编码长度、顺序值易于枚举
独立随机短码	大空间降低碰撞概率，存储约束阻止重复占用	随机源、碰撞重试、空间增长
URL 哈希后截断并编码	相同输入便于得到相同候选码	截断碰撞、URL 语义、冲突后的重新选码

如果采用唯一整数，沿用分布式 ID中的分配方案，不要在转成 Base62 后又截断低几位，否则会破坏原来的唯一性。

随机码也会碰撞。在独立均匀生成的假设下，空间为 M、已经占用 n 个不同码时，下一个候选与已有码冲突的概率是 n / M。这与“累计生成过程中至少碰撞过一次”的概率不是一回事。8 位空间中生成 100 万个候选，至少发生一次碰撞的概率按生日近似约为 1 - exp(-n(n-1)/(2M)) ≈ 0.23%；空间很大仍应正确处理碰撞。

随机短码可以降低顺序枚举的便利程度，但不能当作访问权限。这里的 8 位仅用于公开链接示例，不作为密码重置或私密文件的令牌强度承诺，权限校验见 Web 应用安全。

3.3 原子插入与冲突重试

创建时直接尝试插入，由唯一约束判断短码是否已经被占用。发生短码冲突后重新生成候选，达到次数上限就明确失败。不能把冲突处理写成覆盖已有映射，否则用户 A 的链接可能跳转到用户 B 的地址。

下面用 Python 3.12 与 SQLite 演示这个局部机制。输入 target_url 已经通过接口校验，连接使用 sqlite3.connect(...) 的默认事务设置，由本次操作独占且没有未提交事务；例子不实现完整创建接口、URL 校验、幂等记录或分库路由。

CREATE TABLE short_link (
    code TEXT COLLATE BINARY PRIMARY KEY NOT NULL,
    target_url TEXT NOT NULL,
    expires_at INTEGER NOT NULL,
    state TEXT NOT NULL DEFAULT 'active'
        CHECK (state IN ('active', 'disabled'))
);

import secrets
import sqlite3

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

def new_code():
    return "".join(secrets.choice(ALPHABET) for _ in range(8))

def create_mapping(conn, target_url, expires_at, next_code=new_code):
    for _ in range(8):
        code = next_code()
        try:
            with conn:
                conn.execute(
                    "INSERT INTO short_link(code, target_url, expires_at) "
                    "VALUES (?, ?, ?)",
                    (code, target_url, expires_at),
                )
        except sqlite3.IntegrityError as exc:
            if exc.sqlite_errorcode == sqlite3.SQLITE_CONSTRAINT_PRIMARYKEY:
                continue
            raise
        return code
    raise RuntimeError("short code collision budget exhausted")

create_mapping 在事务提交成功后才返回短码。若第一次生成已存在的 Ab12Cd34，第二次生成空闲的 Zx98Yw76，结果是保留原映射、插入并返回 Zx98Yw76。连续 8 次冲突会抛出异常；非主键约束错误不会被误判成碰撞，数据库不可用等错误也不由这个循环无限重试。

这里的 next_code 用于测试时注入固定候选，生产调用应使用约定的生成器。真实系统还要区分“确认失败”与“提交成功但响应丢失”：后者不能靠换一个码重新插入解决，应通过下面的幂等记录查明同一次创建的结果。SQLite 示例验证的是原子约束与错误分类，不代表其他数据库的并发调度或吞吐结果。

4. 创建流程与重复请求

卡 · 短链接生成系统的核心流程是什么？卡 · 两次创建相同 URL，与一次创建超时重试，应该共用一种去重规则吗？

创建接口先验证调用者、目标 URL、有效期和配额，再分配短码、提交映射，最后返回完整短链接。缓存是加速副本，不应把“只写进 Redis”当作持久创建成功。

URL 校验需要使用解析器，限定允许的 http、https 方案和有效主机，并拒绝控制字符及不符合产品策略的地址。不要随意排序查询参数、删除重复参数或改写路径大小写：两个看上去相似的 URL 可能有不同含义。若增加抓取网页标题、预览图片等能力，服务端才会主动访问目标，必须另外处理 Web 应用安全中的 SSRF 风险；返回重定向本身与服务端抓取不是同一步。

重复请求分两类：

客户端同一次创建超时后重试，应携带同一个幂等键。以“创建者与幂等键”为唯一范围，保存请求参数摘要与结果短码，并与映射在同一事务里提交；相同键却改变目标或有效期时拒绝复用。
用户另发一次创建，目标 URL 恰好相同，本文允许产生新短码。这样两个链接可以有不同的创建者、有效期和统计归属。若产品要求合并，需要明确这些字段是否也参与合并条件。

因此，给 target_url 建一个全局唯一索引并不能代替请求幂等。响应丢失后应查询已提交的幂等记录并返回原结果，具体机制见幂等键。

5. 跳转与失效

卡 · 短链接生成系统的核心流程是什么？卡 · 短链接过期或被禁用后，为什么删掉数据库记录还不够？

5.1 查询与 HTTP 响应

跳转服务读取映射后，要检查状态和绝对过期时间，再决定是否返回 Location。数据库清理任务负责回收空间，不负责决定链接是否已过期；即使清理尚未执行，过期记录也不能继续放行。

本方案对有效链接返回 302 Found 和目标地址，表示临时重定向，并设置 Cache-Control: no-store，避免符合 HTTP 规范的浏览器与共享缓存保存这份跳转响应。这是让禁用更可控的选择，会增加请求到达跳转服务的次数。

302 本身并不等于永不缓存。若决定在 CDN 或浏览器缓存跳转结果，要显式约定新鲜期、失效方式，以及它与链接过期、禁用要求的关系。301、308 表示永久重定向，不宜仅为了“更快”就用于需要撤销的映射。307、308 保留请求方法；本方案仅支持 GET、HEAD，不承诺把任意提交请求安全地转发到另一站点。

不存在、禁用或过期的链接可以统一返回 404，避免额外透露状态；若产品希望明确表达永久失效，也可约定 410。这些失败响应同样需要受控的缓存策略，否则刚创建的短码可能继续命中旧的“不存在”结果。

5.2 服务端缓存与禁用窗口

服务端缓存保存目标地址、状态和 expires_at。每次命中都检查绝对时间；设置缓存 TTL 时不超过业务剩余有效期。应用时钟存在偏差时，要为过期判断定义允许误差并监控时钟，不能只依赖各机器自行计时。

禁用时先提交权威状态，再失效缓存，并可靠记录待重试的失效任务。删除失败会留下旧状态；并发慢查询还可能在删除之后重新回填旧状态，具体时序见缓存一致性。延迟双删只能缩小部分窗口，不能凭固定等待时间证明所有慢读都结束了。

普通链接可以接受约定的传播窗口，同时使用有限 TTL、加载超时、可靠失效事件和必要的版本水位控制旧值回填。若要求禁用提交后新请求立即失败，则读取必须经过足够新的权威检查，并处理在途请求与已发响应的边界。仅给每个缓存值加 version，或者只清除 Redis 而保留本地副本，都不能自动满足这个要求。

过期后不把原短码重新分配给另一目标，能避免旧短信、二维码和浏览器历史把访问者带到无关地址。删除目标 URL 与释放短码是两个不同动作，可以清理前者，同时保留不可再次分配的占用标记。

6. 热点、故障与观测

卡 · 加入缓存后，怎样判断短链接服务能否承受热点与缓存故障？

缓存是否必要要看实际查询成本。按短码唯一索引查询、返回少量字段的数据库，与没有合适索引、连接频繁新建的数据库，在相同 QPS 下表现可能完全不同。面试给出“5000 QPS”时，应先询问延迟目标、硬件、记录大小、索引和读写比例，再用压测确认，不能直接宣布 PostgreSQL 或 MySQL 必然达到瓶颈。

场景	处理方向	仍需保留的边界
大量随机不存在的短码	格式校验、入口限流、短期负缓存，必要时增加布隆过滤器	新增映射要处理旧负缓存；布隆过滤器可能误判存在
一条热门链接缓存失效	合并同码加载，限制回源并发，必要时提前刷新	合并范围通常有限，跨实例仍需核对总回源量
一条链接持续高热	适度使用本地副本或缓存读扩展	多副本都需要禁用、过期与失效机制
缓存整体不可用	对数据库保护性限流，优先保证可承受的读取	不能无上限地让全部请求穿透，也不能在禁用状态未知时随意跳转
权威存储不可用	创建失败或进入明确的结果核对流程；读取按缓存新鲜度合同降级	不伪造持久创建成功，也不把陈旧副本称为最新状态