OpenAI 短链接面试题的完整解答：容量估算与 key 长度、key 生成方案对比、计数器范围、可猜测性、存储、全局重定向路径、301 与 302、热点 key 缓存、脱离热路径的点击分析，以及滥用防控。

由 The Forward Deployed 编辑团队撰写 已审阅

属于 OpenAI 系统设计题库。该题目具有该轮面试的代表性。分析与解答为本站原创。

问题描述

用户提交一个长 URL，然后得到类似

https://sho.rt/aZ3k9Qx

的短链接。任何人打开它都会被重定向到原始 URL。链接所有者可以查看点击次数。想法很简单，而高级别的面试轮次考察的是深度：大规模下的 key 生成、快速且低成本的全局重定向路径、绝不拖慢重定向的分析功能，以及滥用防控。

澄清问题

  • 规模？ 练习场景：每天 1 亿条新链接，读写比为 100:1。
  • Key 长度？ 尽可能短。根据数据推导出来。
  • 自定义别名？ 支持，可选。
  • 过期时间？ 每条链接可选。
  • 分析功能？ 按天、国家、来源统计点击次数，延迟一分钟可以接受。
  • 链接创建后能否修改？ 目标地址不变；链接可以被禁用。
  • 私有链接？ 有些链接指向私有文档，因此 key 不应可被猜出。

短链接服务难在哪里

小规模下没有什么是难的。大规模下，有三件事很难。

Key 生成必须以每秒数千次的速度、跨多台服务器生成数十亿个唯一且短的 key，既不能有中心化瓶颈，也不能出现冲突。

重定向路径承载了几乎全部流量，来自世界各地。它每增加一毫秒，就会加到每一次点击上；而它上面的每一次数据库读取，在每秒 10 万次读取的规模下都要花钱。

而且公开的短链接服务会招来滥用：钓鱼和恶意软件链接藏在短 URL 背后，扫描器会枚举 key 来寻找私有内容。

因此核心矛盾是读取延迟和成本与业务所需的簿记之间的权衡：分析、滥用检查和链接管理都必须在不触碰重定向热路径的情况下完成。

flowchart LR U([用户点击短链接]):::user --> EDGE[边缘 / CDN 区域]:::svc EDGE --> C[(区域缓存)]:::store C -->|未命中| KV[(键值存储副本)]:::store EDGE -->|302 Location| U EDGE -.点击事件.-> LOG[[点击流]]:::svc classDef user fill:#e6efec,stroke:#315e55,color:#171717; classDef svc fill:#f4f1e8,stroke:#315e55,color:#171717; classDef store fill:#fdf3dc,stroke:#c4492d,color:#171717;
核心思路。 把重定向做成靠近用户的缓存查找。其他一切，包括分析和滥用检查，都在这条路径之外进行。

关键概念

Base-62 编码

数字、小写和大写字母共提供 62 个符号。用 62 进制表示的数字很短：7 个字符可覆盖 62^7，约 3.5 万亿个值。

计数器区间

协调器为每台应用服务器分配一段 ID 区间，例如每次 10,000 个。服务器在自己的区间内生成键，无需每次请求都协调，区间用完后申请新区间。

301 和 302

301 重定向是永久性的：浏览器和代理可能会缓存它，下次直接跳过你的服务器。302 是临时性的：每次点击都会回到你的服务器。

热点键

链接的流行度极度倾斜：少数链接获得大部分点击。缓存这几个链接就能服务大部分流量。

核心思路。 用 62 进制生成短键，用计数器区间实现无需协调的规模化，用 302 保留控制权和数据分析，用缓存应对倾斜分布。

需求

在继续阅读之前。 先列出需求，再根据数字推导键的长度，然后选择方案。

1.1 功能需求

  • 为长 URL 创建短链接，可选自定义别名和过期时间。
  • 将短链接重定向到其目标地址。
  • 向所有者展示点击分析。
  • 禁用链接（所有者或信任与安全团队）。

1.2 非功能需求

  • 重定向延迟：全球 p95 低于 50 毫秒，不含目标站点。
  • 重定向的可用性：99.99% 或更高；文档中的链接必须持续可用。
  • 持久性：已创建的链接不会消失，除非被禁用。
  • 唯一性：任何两个链接不共享同一个键。
  • 对于可能指向私有内容的链接，键必须不可猜测。

1.3 约束与属性

重定向可用性是属性。 短链接会存在于文档、电子邮件和印刷材料中多年。读流量是约束。 平均每秒 116,000 次重定向，重定向路径决定了成本和延迟。

粗略估算

  • 写入：每天 1 亿条链接 / 86,400 ≈ 每秒 1,160 条。
  • 读取：写入的 100 倍 ≈ 平均每秒 116,000 次；峰值高出数倍。
  • 五年内的链接数：1 亿 × 365 × 5 = 1,825 亿。
  • 键长度：62^6 ≈ 570 亿太少；62^7 ≈ 3.5 万亿，覆盖五年还有余量。7 个字符。
  • 存储：1,825 亿 × 500 字节（URL、键、所有者、时间戳）≈ 五年约 91 TB，未计副本。
  • 缓存：如果最热门的 1% 链接获得大部分点击，而过去一年链接的 1% 约为 3.65 亿条、每条 500 字节，那么一个区域约需 180 GB 缓存；只缓存最热的一小部分链接即可捕获大部分命中。
  • 点击事件：每秒 116,000 次 × 200 字节 ≈ 23 MB/s 进入分析流，每天约 2 TB。
核心思路。 每秒 1,160 次写入和 116,000 次读取，7 字符键，五年 91 TB，点击流比链接数据本身还大。

API 设计

阅读前思考。 同一个长 URL 被两个不同用户缩短。他们应该得到相同的 key 吗？

通常不应该。不同的所有者想要各自的分析数据，并且能够独立禁用自己的链接。只有按所有者区分时，为相同 URL 返回相同 key 才有意义，作为一种便利。

POST /v1/links
  {long_url, custom_alias?, expires_at?}
  -> 201 {key, short_url: "https://sho.rt/aZ3k9Qx"}
  -> 409 alias taken
  -> 422 URL blocked by safety checks

GET /:key
  -> 302 Location: <long_url>      Cache-Control: private, max-age=0
  -> 404 unknown key
  -> 410 disabled or expired

GET    /v1/links/:key/stats?from=&to=   (owner)  -> clicks by day, country, referrer
PATCH  /v1/links/:key  {disabled: true}           (owner)

数据模型

links (key PRIMARY KEY, long_url, owner_id, created_at, expires_at, status)
      -- key-value store, partitioned by key, replicated to every region
owner_links (owner_id, created_at, key)          -- "my links" list
id_blocks   (range_start, range_end, server_id, allocated_at)
clicks_by_day (key, day, country, referrer_domain, count)   -- analytics store

重定向路径只涉及

links

，按精确 key 查找。没有连接，没有范围查询，这就是键值存储适合的原因。

高层设计

5.1 单台服务器和一张 SQL 表

单台服务器写入带自增 ID 的行，将 ID 转换为 base 62 作为 key，并通过查找进行重定向。它能工作到单机的极限，而且自增计数器使 key 连续且可被猜测。

5.2 修复 1：用计数器区间生成 key

多台 API 服务器各自从协调器（一个小型强一致服务）获取一段 ID 区间，并在本地从该区间生成 key。

flowchart LR COORD[(Range coordinator)]:::new -->|block 50,000,000-50,009,999| A1[API server 1]:::svc COORD -->|block 50,010,000-50,019,999| A2[API server 2]:::svc A1 -->|next id -> permute -> base62| K1[key]:::store classDef svc fill:#f4f1e8,stroke:#315e55,color:#171717; classDef store fill:#fdf3dc,stroke:#c4492d,color:#171717; classDef new fill:#ffffff,stroke:#c4492d,stroke-width:2px,stroke-dasharray:5 3,color:#171717;

5.3 修复 2：分布式键值存储

将链接存储在按 key 分区并跨区域复制的键值存储中。按 key 读取只需个位数毫秒。

5.4 修复 3：边缘的区域缓存

重定向在用户所在区域提供服务：边缘服务器先检查内存缓存，再查询区域副本。大多数点击不会离开该区域，且大多数命中缓存。

5.5 修复 4：将分析移出热路径

重定向将点击事件发送到流并立即返回。流处理器聚合计数。

5.6 修复 5：滥用控制

新 URL 在返回 key 之前会对照恶意软件和钓鱼网站名单进行检查，热门链接会被重新扫描。

5.7 组合后的设计

sequenceDiagram
  autonumber
  actor Cr as Creator
  participant API as API server
  participant S as Safety check
  participant KV as Key-value store
  actor V as Visitor
  participant E as Edge server
  participant C as Regional cache
  participant ST as Click stream
  Cr->>API: POST /links {long_url}
  API->>S: check URL
  S-->>API: ok
  API->>API: id from local block, permute, base62
  API->>KV: put key -> long_url (if absent)
  API-->>Cr: short_url
  V->>E: GET /aZ3k9Qx
  E->>C: get key
  alt hit
    C-->>E: long_url
  else miss
    E->>KV: get key (regional replica)
    E->>C: fill
  end
  E-->>V: 302 Location
  E--)ST: click event (async)
核心思想。 用 ID 区间生成 key，用复制的键值存储保存链接，用边缘缓存处理重定向，用流处理点击，并在创建时进行安全检查。

深入探讨

6.1 key 生成方案对比

阅读前思考。 比较四种生成 key 的方式。你会选哪一种？如果 key 必须不可被猜测，会有什么变化？
选项方式优点缺点
全局计数器 + base 62单一计数器，编码无冲突，简单中心瓶颈；key 连续、可被猜测
计数器区间每台服务器一段区间写入无需协调；无冲突崩溃的服务器浪费其区间（可接受）；除非做置换，否则仍可被猜测
URL 哈希取哈希的前 7 个字符相同 URL 得到相同 key；无需计数器冲突需要检测并重试；不同所有者得到相同 key
随机 + 校验7 个随机 base-62 字符；不存在时插入不可猜测；无需协调需要条件插入；随着空间填满，重试次数增加

计数器区间是吞吐量方面最强的默认方案。对于不可猜测的键，在编码之前，将每个计数器值通过一个可逆置换——即对 ID 空间的一个带密钥分组密码——进行处理。键保持唯一，因为置换是一对一的，且连续的 ID 会产生不相关的键。或者使用带条件插入的随机键：在 3.5 万亿个可能值中已有 1820 亿个链接时，五年后空间大约填满 5%，因此大约每 20 次插入会有 1 次冲突并重试一次，代价很低。

自定义别名共享键空间。使用同样的条件 put 插入它们；别名已被占用则返回 409。保留诸如

api

,

admin

和

login

.

区分答案优劣之处：键生成

WeakOne 全局计数器

使用自增键，没有针对扩展性或不可猜测性的规划。

GoodRanges 或随机键

使用计数器区间或带条件插入的随机键，并根据数字推导键长度。

Strong 对比并加固

对比所有方案，对计数器做置换或使用随机键以保证不可猜测性，计算空间填满时的冲突率，并处理自定义别名和保留词。

6.2 存储与复制

访问模式是单键读和带唯一性检查的单键写。分布式键值存储很合适：按键哈希分区，在每个区域内复制以保证持久性，并异步复制到其他区域以支持本地读取。

创建时以条件 put 写入键的主区域，因此唯一性在一个地方得到保证。其他区域会在大约一秒内收到该链接。另一个区域的访客若在链接复制完成前点击一个全新链接，会遇到缓存未命中和本地未命中；在返回 404 之前，回退到读取主区域。这个回退机制覆盖了链接生命周期的最初一秒。

6.3 重定向路径

在继续阅读之前。 301 还是 302？为你的选择辩护。

301 是永久重定向。浏览器会缓存它，通常是无限期缓存，因此该浏览器后续的点击会直接跳转到目标地址，而不再联系你。这节省了负载。但也意味着你会丢失分析中的这次点击，而且你永远无法对该浏览器进行不同的重定向，即使你因为链接变成恶意链接而将其禁用。

302 每次都会返回。你为每次点击付费，但保留了分析和控制能力。大多数商业短链接服务出于这个原因使用 302。添加

Cache-Control: private, max-age=0

，使共享缓存也不存储它。

延迟：从多个区域的边缘服务器提供重定向，每台服务器都有热点键的内存缓存和附近的键值副本。缓存命中可以在一两毫秒内响应，再加上到边缘的网络往返时间。

6.4 缓存热点链接

流量分布高度倾斜。一个病毒式传播的链接可能每秒获得数万次点击。每台边缘服务器上的进程内缓存，配合区域缓存集群作为后盾，可以吸收这些流量。带大小上限的最近最少使用策略效果很好。

有两种情况需要小心处理。负缓存：扫描器会请求随机键；对“未找到”的结果进行短时间缓存，以免它们不断冲击存储。禁用：当链接被禁用时，向每个区域发布失效通知，让缓存立即丢弃该链接，而不是等到生存时间过期。对于恶意链接，几分钟都至关重要。

6.5 分析

绝不要每次点击都写数据库。边缘服务器向流中发出一个小事件（键、时间戳、来自 IP 的国家、引荐域名、用户代理的哈希值），然后返回重定向。流处理器按分钟对每个键的计数进行聚合，并写入分析存储，以回答“按国家统计的每日点击量”。一分钟的延迟对用户是不可见的。

根据用户代理和请求频率对明显的机器人进行去重，并将其从计数中排除。不要将原始 IP 地址存储超过必要的时间。

6.6 滥用

  • 创建时：对照恶意软件和钓鱼网站名单检查目标地址；封锁已知恶意域名；按账户和 IP 限制创建频率。
  • 创建后：对突然变得热门的链接进行重新扫描，因为攻击者会先创建干净的链接，之后再在自己服务器上更换目标地址。
  • 快速禁用：信任与安全团队可以禁用某个键，这会使全球缓存失效，并返回 410 状态码和警告页面。
  • 枚举防护：使用不可猜测的键、按 IP 对 404 进行速率限制，且不采用顺序结构。

6.7 键生成，附代码

在继续阅读之前。 编写一个函数，将计数器值转换为不可猜测的 7 字符键，并证明它不会发生冲突。
import hashlib, hmac

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
SPACE = 62 ** 7                       # about 3.5 trillion keys

def to_base62(n: int, width: int = 7) -> str:
    chars = []
    for _ in range(width):
        n, r = divmod(n, 62)
        chars.append(ALPHABET[r])
    return "".join(reversed(chars))

def feistel_permute(n: int, secret: bytes, rounds: int = 4) -> int:
    # Balanced Feistel network over a power-of-two domain, then cycle-walk into SPACE.
    bits = (SPACE - 1).bit_length()
    half = (bits + 1) // 2
    mask = (1 << half) - 1
    while True:
        left, right = n >> half, n & mask
        for i in range(rounds):
            f = int.from_bytes(hmac.new(secret, bytes([i]) + right.to_bytes(8, "big"),
                                        hashlib.sha256).digest()[:8], "big") & mask
            left, right = right, left ^ f
        n = (left << half) | right
        if n < SPACE:                  # cycle-walk until inside the key space
            return n

def key_for(counter: int, secret: bytes) -> str:
    return to_base62(feistel_permute(counter, secret))

Feistel 网络是一个置换：每一轮都是可逆的，因此不同的输入产生不同的输出。循环行走使输出保持在键空间内，同时保持一一对应。因此不同的计数器产生不同的键，无需冲突检查，且连续的计数器产生互不相关的键。将密钥保存在密钥管理器中；如果密钥泄露，键会重新变得可预测，但绝不会重复。

6.8 重定向路径的实际成本

作为练习：平均每秒 116,000 次重定向。在边缘缓存命中率为 95% 的情况下，键值存储在所有区域每秒只需处理约 5,800 次读取，这是一个很小的集群。如果没有缓存，它将承受全部 116,000 次读取。缓存在每个区域需要几百 GB 的内存；节省下来的是存储层的大部分读取容量，以及每次点击的几毫秒延迟。

点击流是更大的成本：每天约 2 TB。在几分钟内完成聚合，并将原始事件保留一个较短的窗口（例如 7 天）用于滥用调查；之后只保留聚合数据。

什么能区分出优秀的回答：深度

弱对 URL 进行哈希并寄希望于运气

截取 URL 的哈希值，寄希望于冲突很少发生，且不做任何检查。

GoodA 无冲突方案

使用计数器区间或随机密钥，配合条件插入。

Strong无冲突且不可猜测，但有成本

使用带密钥的 Feistel 网络对计数器进行置换，解释为什么不会发生冲突，并量化边缘缓存和点击流带来的成本与节省。

变体

7.1 可编辑的目标地址

有些产品允许所有者修改目标地址。此时必须使用 302，编辑时缓存需要失效处理，并且应保留目标地址历史记录以便滥用审查。

7.2 Pastebin

存储文本而非 URL。内容存入对象存储；键值存储保存指针。读取通过 CDN 提供内容。

7.3 企业品牌域名

客户使用自己的域名，例如

go.company.com

。密钥按域名划分作用域；键值存储的键变为

(domain, key)

.

7.4 流量增长十倍时

在每秒一百万次重定向的情况下，架构上没有任何变化：更多边缘服务器、更大的缓存、更多的流分区。需要重新检查的是密钥空间：每天新增 10 亿条链接，五年就是 1.8 万亿，约为 62^7 的一半。在密钥空间用满一半之前迁移到 8 字符密钥，这样随机密钥冲突和置换的循环行走成本仍然很低。

可迁移的模式

URL 短链接服务本质上是一个带异步旁路通道的全球复制键值查找系统。同样的架构适用于功能开关、配置查找和会话存储：让热点读取命中本地缓存，保持写入稀少且带条件，并把所有记账工作移到流中。

复习：30 秒答案

  • 先说数字。 每秒 1,160 次写入和 116,000 次读取；五年内 1,820 亿条链接；7 个 base-62 字符。
  • 计数器区间、置换计数器或随机密钥。 每次写入无需协调；需要时不可猜测。
  • 键值存储，复制到多个区域。 在主区域执行条件写入；对全新链接提供回退读取。
  • 从边缘缓存返回 302。 控制与分析；负缓存；禁用时全局缓存失效。
  • 点击写入流；在创建时和流行时进行滥用检查。

测验

+如何推导密钥长度？

估算服务生命周期内的链接总数，这里是五年 1,825 亿条，然后选择空间有余量地超过该数的最短 base-62 长度。62^6 约为 570 亿，太小；62^7 约为 3.5 万亿。

+为什么计数器区间能避免中心瓶颈？

每台服务器一次性预留一段 ID 区间，然后在本地生成密钥。协调器每区间只需联系一次，而不是每条链接联系一次。

+如何让基于计数器的密钥不可猜测？

在编码之前，将每个计数值通过 ID 空间上的可逆带密钥置换。它保持一一对应，因此密钥仍然唯一，但连续的 ID 会映射到不相关的密钥。

+为什么大多数短链接服务使用 302 而不是 301？

301 可能会被浏览器无限期缓存，因此后续点击会跳过该服务。这会丢失分析数据，也无法再禁用或更改链接。而 302 每次都会回到该服务。

+为什么将点击发送到流中，而不是写入数据库？

每次点击都写数据库会给每个重定向增加延迟，并且在每秒 116,000 次点击的情况下产生巨大的写入负载。流将重定向与聚合处理解耦。

+为什么 Feistel 置换不会产生两个相同的密钥？

每一轮 Feistel 都是可逆的，因此整个网络是一个一一映射。循环行走（cycle-walking）确保它在密钥空间内保持一一对应。因此不同的计数器会得到不同的密钥。

+服务应该在什么时候迁移到 8 字符密钥？

远在 7 字符空间填满之前，例如当预计链接数达到 62^7 的一半时，这样冲突重试和循环行走仍能保持低成本。

资料来源与延伸阅读