Design URL Shortener

我们来设计一个 URL shortener，类似 Bitly、TinyURL。

What is a URL Shortener?

URL shortener 服务会把长 URL 生成一个 alias（短链接）。用户访问短链接时会被重定向到原始 URL。

例如：

Long URL: https://karanpratapsingh.com/courses/system-design/url-shortener

Short URL: https://bit.ly/3I71d3o

Why do we need a URL shortener?

短链接更省空间，也不易输错。还可以跨设备优化链接，并支持点击追踪。

Requirements

Functional requirements

• 给定 URL，生成一个 更短且唯一 的 alias。
• 访问短链接时重定向到原 URL。
• 链接可设置过期时间（默认可永久）。
• 支持用户自定义 alias（custom short URL）。
• 返回 short link 的同时可提供 QR code / preview metadata（可选）。

Non-functional requirements

• 高 availability，低 latency。
• 系统可扩展且高效。

Extended requirements

• 防止滥用。
• 记录跳转 analytics 与 metrics。
• 黑名单/反钓鱼检测（可选）。

Estimation and Constraints

注意：和面试官确认规模假设。

Traffic

读多写少，假设 read/write = 100:1，每月生成 100M 链接。

Reads/Writes Per month

Reads:

$$ 100 \times 100 \space million = 10 \space billion/month $$

Writes:

$$ 1 \times 100 \space million = 100 \space million/month $$

Requests Per Second (RPS)

100M/月约 40 RPS：

$$ \frac{100 \space million}{(30 \space days \times 24 \space hrs \times 3600 \space seconds)} = \sim 40 \space URLs/second $$

read/write=100:1，则重定向约 4000 RPS：

$$ 100 \times 40 \space URLs/second = 4000 \space requests/second $$

Bandwidth

写入流量：

$$ 40 \times 500 \space bytes = 20 \space KB/second $$

读取流量：

$$ 4000 \space URLs/second \times 500 \space bytes = \sim 2 \space MB/second $$

Storage

存 10 年：

$$ 100 \space million \times 10\space years \times 12 \space months = 12 \space billion $$

每条 500 bytes：

$$ 12 \space billion \times 500 \space bytes = 6 \space TB $$

Cache

按 80/20 缓存 20% 热点：

$$ 4000 \space URLs/second \times 24 \space hours \times 3600 \space seconds = \sim 350 \space million \space requests/day $$

缓存约 35 GB/day：

$$ 20 \space percent \times 350 \space million \times 500 \space bytes = 35 \space GB/day $$

High-level estimate

Data model design

初期两张表：

users

用户信息：name、email、createdAt 等。

urls

短链接记录：expiration、hash、originalURL、userID、createdAt、isCustom。hash 可做 index 提升查询性能。

clicks (optional)

按天或按小时聚合：hash、ts_bucket、country、device、referrer、count。

选什么 database？

数据关系不强，可选 Amazon DynamoDB、Apache Cassandra、MongoDB。如需 SQL，可用 Azure SQL Database 或 Amazon RDS。

更多对比见 SQL vs NoSQL。

API design

Create URL

createURL(apiKey: string, originalURL: string, expiration?: Date, customAlias?: string): string

Get URL

getURL(apiKey: string, shortURL: string): string

Delete URL

deleteURL(apiKey: string, shortURL: string): boolean

为什么需要 API key？

用于防止滥用，限制用户 QPS/分钟请求数，是 developer API 的常见做法。

High-level design

URL Encoding

Base62 Approach

用 Base62（A-Z, a-z, 0-9）编码：

$$ Number \space of \space URLs = 62^N $$

N=7 时约 3.5 trillion：

$$ \begin{gather*} 62^5 = \sim 916 \space million \space URLs \ 62^6 = \sim 56.8 \space billion \space URLs \ 62^7 = \sim 3.5 \space trillion \space URLs \end{gather*} $$

简单但无法保证唯一。

MD5 Approach

$$ MD5(original_url) \rightarrow base62encode \rightarrow hash $$

会有 collision，需重算，开销大。

Counter Approach

$$ Counter(0-3.5 \space trillion) \rightarrow base62encode \rightarrow hash $$

单点问题明显。可用 Zookeeper 分配 range：

$$ \begin{align*} & Range \space 1: \space 1 \rightarrow 1,000,000 \ & Range \space 2: \space 1,000,001 \rightarrow 2,000,000 \ & Range \space 3: \space 2,000,001 \rightarrow 3,000,000 \ & ... \end{align*} $$

Key Generation Service (KGS)

独立 KGS 预生成 keys 存储。用两张表 + locking 处理并发，热点 keys 可缓存内存。

KGS database estimations

6 位 key 约 56.8B，存储 ~390GB：

$$ 6 \space characters \times 56.8 \space billion = \sim 390 \space GB $$

Caching

用 Redis 或 Memcached 缓存热点 20%。

Design

Create URL

1. API server 向 KGS 请求 key。
2. KGS 返回 key 并标记已用。
3. API server 写 DB + cache。
4. 返回 HTTP 201。

Access URL

1. 请求进 API server。
2. 命中 cache 返回 302（方便做 analytics）；未命中则查 DB 再 cache。
3. DB 无结果返回 404。

Detailed design

Data Partitioning

用 Sharding + Consistent Hashing 解决分布不均。

Database cleanup

Active cleanup：定期 cron 清理过期。

Passive cleanup：访问时发现过期再清除。

Custom alias

允许用户提供自定义 alias（例如长度 <= 16）。为了隔离写入负载，可把 custom URLs 放在单独的 DB / table。路由时先查 custom bucket，再查系统生成 bucket。

Redirect status (301 vs 302)

• 301：更 cache-friendly，但浏览器/中间缓存会减少你拿到的 click data。
• 302：每次都会打到 backend，更适合实时 analytics。

Cache

Eviction：LRU。

Cache miss：回源 DB，再更新 cache。

Metrics and Analytics

记录地区、平台、views 等。常见做法是把 redirect 事件写入 queue（Kafka / Pub/Sub），离线聚合统计。

Security

支持 private URLs + 授权表；不符合权限返回 401。可用 API Gateway 支持 auth / rate limit / load balancing。

Load balancer placement

• Client → App servers
• App servers → DB
• App servers → Cache

基础可以用 round-robin；更高级可按 latency / load 自适应。

Identify and resolve bottlenecks

提升 resilience：

• 多实例 API 与 KGS
• Load balancers
• DB read replicas
• KGS key DB standby
• 分布式 cache 多副本