经典案例：短链系统设计 (URL Shortener / TinyURL)¶

短链系统（如 TinyURL, Bitly）是系统设计面试中最经典的高频入门题之一。它麻雀虽小五脏俱全，涵盖了高并发读取、数据模型选型、哈希与编码算法、分库分表与缓存优化等核心架构要点。

1. 需求分析与系统范围 (Requirements & Scope)¶

1.1 功能性需求 (Functional Requirements)¶

短链生成：用户输入任意长度的原始 URL，系统生成一个全局唯一的短 URL（例如 https://tiny.url/7bX9q）；
重定向跳转：当用户访问短 URL 时，系统迅速将其重定向（301 或 302）到原始长 URL；
过期机制（TTL）：短链支持设置有效期限（默认永久或指定天数后自动失效）；
自定义别名（可选扩展）：允许用户自定义短码后缀（如 https://tiny.url/my-promo）。

1.2 非功能性需求 (Non-Functional Requirements)¶

高可用性（High Availability）：作为互联网基础入口，必须保证 99.99% 的高可用；
极低延迟（Low Latency）：重定向跳转耗时必须控制在毫秒级（\(< 10\text{ ms}\)）；
短码不可猜测性（Security）：短码不能被攻击者通过顺序自增轻松遍历猜测，防范恶意爬取；
读多写少（High Read-to-Write Ratio）：读取请求量远大于写入请求量（典型比例为 \(100:1\)）。

2. 容量估算 (Back-of-the-Envelope Estimation)¶

2.1 流量与 QPS 估算¶

设系统每天生成 1 亿条新短链（\(10^8\text{ URLs/day}\)）；
读写比例为 \(100:1\)，则每日重定向读取请求量为 100 亿次；
写入 QPS：

\[ \text{Write QPS} = \frac{10^8}{86,400\text{ s}} \approx \frac{10^8}{10^5} \approx 1,000\text{ QPS} \]

峰值写入 QPS（按 2 倍计算）约为 \(2,000\text{ QPS}\)。

读取 QPS：

\[ \text{Read QPS} = 1,000 \times 100 = 100,000\text{ QPS} \]

峰值读取 QPS（按 2 倍计算）约为 \(200,000\text{ QPS}\)。

2.2 存储容量估算 (5 年规划)¶

5 年累计短链记录总数：\(10^8 \times 365 \times 5 \approx 1.8 \times 10^{11}\)（约 1800 亿条）；
单条记录数据结构大小估算：
short_code：7 字节（Base62 字符串）
original_url：平均 500 字节
created_at / expired_at / user_id：约 25 字节
单行合计约 \(532\text{ Bytes} \approx 0.5\text{ KB}\)。
5 年磁盘总存储量：

\[ 1.8 \times 10^{11} \times 0.5\text{ KB} \approx 9 \times 10^{13}\text{ Bytes} \approx 90\text{ TB} \]

2.3 内存缓存估算 (80/20 法则)¶

每日 100 亿次读取请求，根据帕累托法则，20% 的热点 URL 占据了 80% 的访问流量；
每日需缓存的热点数据量：

\[ 10^8 \times 100 \times 20\% \times 0.5\text{ KB} = 1\text{ TB} \]

即约需 1TB 内存。使用多台 Redis 节点（如 16 台 64GB 节点）构建集群即可完整承载热点缓存。

3. 核心算法设计：短码生成机制对比¶

短码必须短小精悍。我们通常使用 Base62 编码（字符集包含 [0-9], [a-z], [A-Z] 共 \(10 + 26 + 26 = 62\) 个字符）。

若短码长度设定为 7 个字符，所能表达的唯一组合数为（约 3.5 万亿）：

\[ 62^7 = 3,521,614,606,208 \approx 3.52 \times 10^{12} \]

\(3.5\) 万亿远大于 5 年规划所需的 \(1800\) 亿，因此 7 位 Base62 字符完全足够。

graph TD
    A["短码生成算法选型"] --> B["方案一: 哈希截断 (MD5 / SHA-256)"]
    A --> C["方案二: 分布式发号器 + Base62 进制转换 (推荐)"]

    B --> B1["长 URL 计算 MD5 -> 128 bit<br>取前 43 bit 映射为 7 位 Base62<br>缺点: 存在哈希碰撞, 需重复查库重试"]

    C --> C1["分布式 ID 生成器 (Snowflake / 号段)<br>生成全局唯一的 64 位纯数字 ID<br>直接转换为 7 位 Base62<br>优点: 绝对零碰撞, 单调递增写入极快"]

3.1 方案对比与推荐¶

维度	方案一：哈希算法截断 (Hash + Collision Resolution)	方案二：分布式 ID + Base62 (工业首选)
工作原理	计算 `MD5(long_url)` 得到 128-bit，截取前若干位转为 Base62。若数据库已存在则追加盐（Salt）重新哈希。	发号器先生成一个全局唯一的 64 位整数 ID（如 `1251341`），直接做除 62 取模进制转换。
碰撞问题	无法避免哈希碰撞！随着数据量增大，碰撞概率激增，导致多次查询数据库重试，写延迟陡增。	理论上绝对零碰撞（因为输入的数字 ID 全局唯一）。
写入性能	较差（每次生成必须先查库确认是否冲突）。	极快（发号器在内存中高速生成，直接转换落库）。
安全性与防遍历	天然随机分散。	纯自增数字易被黑客推算遍历。解决方案：采用 Feistel 密码或位混淆算法对自增数字打乱后再进行 Base62 转换。

4. HTTP 301 vs 302 重定向权衡¶

当客户端访问 https://tiny.url/7bX9q 时，服务端通过 HTTP 状态码指示重定向。选 301 还是 302？

      HTTP 301 Moved Permanently               HTTP 302 Found / 307 Temporary
  +--------------------------------+       +------------------------------------+
  | 浏览器会【强缓存】重定向目标。   |       | 浏览器【不缓存】重定向关系。        |
  | 下次点击直接跳转原始 URL，      |       | 每次点击都会再次向短链服务器发请求。  |
  | 不再经过短链服务器！            |       |                                    |
  | 优点: 极致减轻短链服务器压力。  |       | 优点: 能够精确统计每次点击的 PV/UV、 |
  | 缺点: 无法统计真实点击数据！    |       |       访问地域、设备、防范恶意钓鱼。|
  +--------------------------------+       +------------------------------------+

权衡结论：
工业界大多数短链服务（如营销短信、广告归因）都依赖点击数据进行效果统计与风控拦截，因此普遍采用 302 临时重定向（或 307）。如果公司纯粹为了给内网服务做域名缩写、且完全不需要任何统计数据，才考虑 301。

5. 整体系统架构图¶

flowchart TD
    User["用户客户端 (浏览器 / App)"] --> CDN["CDN / 边缘节点 (静态资源与极热点短链)"]
    CDN --> LB["负载均衡器 (L4 / L7)"]
    LB --> WebCluster["无状态 Web 服务集群 (短链解析 / 生成)"]

    subgraph "写链路 (生成短链)"
        WebCluster --> IDGen["分布式发号器 (Leaf / Snowflake)"]
        WebCluster --> DB_Master["关系型数据库 / NoSQL 主库"]
    end

    subgraph "读链路 (重定向)"
        WebCluster --> RedisCluster["Redis 缓存集群 (Cache-Aside)"]
        RedisCluster -- 未命中 --> DB_Slave["数据库从库 (读写分离)"]
    end

6. 数据表结构与分库分表设计¶

6.1 核心数据表设计 (DDL)¶

CREATE TABLE url_mapping (
    id BIGINT NOT NULL,                  -- 分布式唯一自增 ID (主键)
    short_code VARCHAR(7) NOT NULL,      -- 7 位 Base62 短码 (唯一索引)
    original_url VARCHAR(2048) NOT NULL, -- 原始长 URL
    user_id BIGINT DEFAULT NULL,         -- 创建者用户 ID
    created_at TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP,
    expired_at TIMESTAMP NULL,           -- 过期时间
    PRIMARY KEY (id),
    UNIQUE KEY uk_short_code (short_code)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

6.2 数据库分片键（Sharding Key）选择¶

以 short_code 进行哈希分片：
核心读场景是 SELECT original_url FROM url_mapping WHERE short_code = ?；
以 short_code 作为分片键，所有读取请求能够精准路由到单一数据库分片，完全无跨分片广播查询，性能最高；
如何处理自定义短码（Custom Alias）？
自定义短码同样作为 short_code 写入对应分片即可；若需要防重复，在写入时依赖对应分片的唯一索引拦截。