短網址系統設計#

將長 URL 轉換為短 URL 的服務，如 https://github.com/xxx → http://t.cn/abc123

系統功能#

1. 生成短網址：長 URL → 短 URL
2. 重定向：用戶訪問短 URL → 跳轉到原始 URL

方案一：雜湊演算法#

流程#

1. 對原始 URL 使用 MurmurHash 計算雜湊值
2. 將十進位雜湊值轉為 62 進位（0-9, a-z, A-Z）
3. 拼接域名形成短網址

https://github.com/xxx
    ↓ MurmurHash
181338494
    ↓ 轉 62 進位
cgSqq
    ↓ 拼接域名
http://t.cn/cgSqq

處理雜湊衝突#

原始 URL + "[DUPLICATED]" → 重新計算雜湊

性能優化#

問題：每次生成需查詢 + 寫入兩次 SQL

優化方案：

1. 唯一索引：給短網址加唯一索引，直接嘗試寫入

   • 成功 → 無衝突
   • 失敗 → 再執行衝突處理

2. 布隆過濾器：先查布隆過濾器

   • 不存在 → 直接寫入
   • 存在 → 查詢資料庫確認

大部分情況不會衝突，直接寫入策略可減少 50% 的 SQL 查詢。

方案二：ID 生成器#

流程#

1. 維護一個自增 ID 生成器
2. 新 URL 請求一個 ID
3. 將 ID 轉為 62 進位作為短網址

請求 ID → 12345
    ↓ 轉 62 進位
3D7
    ↓ 拼接域名
http://t.cn/3D7

問題：相同 URL 可能對應不同短網址#

處理方案：

1. 不處理：用戶不關心短網址是否相同，只關心能否跳轉
2. 加索引查重：給原始 URL 加索引，先查再生成
   • 缺點：兩個索引增加存儲和維護成本

高性能 ID 生成#

單一計數器無法應對高並發：

        ID 生成器
           ↓ 批量發號
    [發號器1] [發號器2] [發號器3]
       ↓        ↓        ↓
    請求1     請求2     請求3

生成器1：尾號 0 (0, 10, 20, ...)
生成器2：尾號 1 (1, 11, 21, ...)
生成器3：尾號 2 (2, 12, 22, ...)
...

兩種方案對比#

62 進位轉換#

使用 62 個字元：0-9、a-z、A-Z

CHARS = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

def to_base62(num):
    if num == 0:
        return CHARS[0]
    result = []
    while num:
        result.append(CHARS[num % 62])
        num //= 62
    return ''.join(reversed(result))

6 位 62 進位數可表示 $62^6 ≈ 568$ 億個短網址，足夠使用。

關鍵技術點#

擴展：自定義短網址#

用戶可自定義短網址部分：

1. 檢查自定義部分是否已存在
2. 若衝突，提示用戶修改
3. 若無衝突，直接存入資料庫