短鏈接 (Short URL) 系統設計原理與實戰

常見誤區：試圖用「壓縮算法」實現長短雙向映射

許多候選人會想：找一個算法將長 URL 壓縮為短碼，並能逆向還原。這在信息論上是不可能的——短碼空間 (如 62¹⁰⁰) 遠小於長 URL 空間，必然發生碰撞；若真能無損壓縮任意長度到固定短度，所有壓縮軟體都可歇業了。

正確原理：發號器 (ID Generator) + 映射存儲

核心邏輯：不壓縮，只分配唯一 ID。

1. 用戶提交長 URL
2. 系統從發號器獲取唯一遞增 ID (1, 2, 3...)
3. 將 ID 轉為 62 進制短碼 (0-9, a-z, A-Z)
4. 存儲 短碼 → 長 URL 映射
5. 返回短鏈接 https://domain/短碼

例：第 1 條 → 0，第 11 條 → a，第 62 條 → 10。

關鍵子問題與解決方案

1. 62 進制轉換實現

存儲層用 10 進制 ID，輸出時轉 62 進制：

string toBase62(long long id) {
    const char* chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    if (id == 0) return "0";
    string res;
    while (id > 0) {
        res.push_back(chars[id % 62]);
        id /= 62;
    }
    reverse(res.begin(), res.end());
    return res;
}

2. 同一長 URL 返回同一短碼 (去重)

方案：LRU 緩存「最近」映射，而非全量存儲。

• 寫入時：檢查緩存，命中則刷新 TTL 並返回；未命中則發號、寫入緩存 (TTL 1h)、返回
• 緩存淘汰：低頻 URL 自動過期，釋放空間
• 權衡：極低頻 URL 可能獲不同短碼，但節省海量存儲，工程上極具性價比

3. 高併發發號器設計

邏輯分片：N 個發號器，第 i 個只發尾號 ≡ i (mod N) 的 ID，步長 N。
例：1000 節點，步長 1000，互不干擾，線性擴展。物理部署可從邏輯分片平滑遷移。

4. 存儲選型建議

• 小規模：MySQL 自增主鍵 + 索引
• 大規模：Redis Cluster / Cassandra / 自研 KV (如 RocksDB 集群)
• 關鍵指標：寫入吞吐、讀取延遲、可用性、一致性需求

5. 301 vs 302 重定向選擇

短鏈點擊數據是極高價值的用戶行為數據源，**302 雖增壓力，但數據價值遠超成本**。

架構總覽

[Client] → [API Gateway] → [Shorten Service] → [ID Generator (Sharded)]
                                    ↓
                            [Cache: LRU Long→Short]
                                    ↓
                            [Storage: KV (Short→Long)]
                                    ↓
[Redirect] ← [Resolve Service] ← [Storage]