設計短網址服務（URL Shortener）
問題定義
設計一個類似 TinyURL / bit.ly 的短網址服務，支援：將長 URL 轉為短 URL，點擊短 URL 時重定向到原始 URL。
ℹ️需求規模估算
假設每日新增 1 億個短網址、讀寫比 100:1（每日 100 億次讀取）。短網址需保留 5 年。 總儲存量：1 億 × 365 × 5 = 1,825 億筆。每筆約 500 bytes → 約 91 TB。
需求分析
- 功能性需求：輸入長 URL 回傳短 URL、短 URL 重定向到長 URL、可選自訂短碼（用戶指定
mylink作為短碼）、設定過期時間（預設 5 年，可自訂） - 非功能性需求：低延遲（重定向 P99 < 100ms，意味著 99% 的請求在 100ms 內完成）、高可用（99.99% = 每年最多 52 分鐘停機）、短碼不可預測（不能讓人猜到下一個短碼是什麼，避免被掃描）
- 讀寫比：讀遠大於寫（100:1），架構要針對讀取優化。具體數字：每日 1 億寫入 = 1,157 writes/s，每日 100 億讀取 = 115,740 reads/s
- 短碼長度計算：Base62（a-z, A-Z, 0-9）。6 位 = 62^6 ≈ 568 億（5 年每日 1 億 = 1,825 億，不夠）。7 位 = 62^7 ≈ 3.5 兆（綽綽有餘）。所以選 7 位
- 儲存估算：每筆記錄約 500 bytes（短碼 7B + 長 URL 平均 200B + 時間戳 + 索引開銷）。5 年 1,825 億筆 x 500B ≈ 91TB，需要 Sharding
注意事項
⚠️Hash 碰撞處理
無論用什麼 Hash 函數（MD5、SHA256），截取前 7 位都有碰撞風險。MD5 產生 128 bit，截取 7 個 Base62 字元只用了約 42 bit，碰撞機率隨資料量指數上升（生日悖論）。
處理碰撞的具體流程：1. 對長 URL 做 Hash 取前 7 位 → 2. 查詢 DB 該短碼是否已存在 → 3. 如已存在且對應不同長 URL，追加一個隨機字元重新 Hash → 4. 重複直到找到未使用的短碼。缺點是每次寫入都要查 DB。
推薦方案：用分散式 ID 生成器（Snowflake）產生全域唯一 ID，再 Base62 編碼，完全避免碰撞且不需要查 DB。
設計流程
需求釐清
讀寫比、儲存量、短碼長度、過期策略
短碼生成策略
Hash 截取 vs 自增 ID + Base62 編碼
API 設計
POST /shorten 建立短碼、GET /:code 重定向
資料庫設計
short_code 為主鍵，加上 original_url、created_at、expires_at
快取策略
熱門短碼放 Redis，Cache Aside pattern
擴展與高可用
資料庫 Sharding by short_code、多機房部署
架構設計
短碼生成（兩種方案）
// 方案一：Hash 截取（簡單但有碰撞風險）
public string GenerateByHash(string longUrl)
{
var hash = Convert.ToBase64String(
MD5.HashData(Encoding.UTF8.GetBytes(longUrl)));
return hash[..7].Replace("+", "a").Replace("/", "b");
}
// 方案二：自增 ID + Base62（推薦，無碰撞）
public class Base62Encoder
{
private const string Chars =
"0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
public static string Encode(long id)
{
if (id == 0) return "0";
var result = new StringBuilder();
while (id > 0)
{
result.Insert(0, Chars[(int)(id % 62)]);
id /= 62;
}
return result.ToString();
}
}
// ID 用分散式 ID 生成器（如 Snowflake）確保唯一性
var shortCode = Base62Encoder.Encode(snowflakeId); // e.g., "a7Bx9K2"重定向 API（TypeScript）
app.get("/:code", async (req, res) => {
const { code } = req.params;
// 1. 查 Cache
const cached = await redis.get(`url:${code}`);
if (cached) {
res.redirect(301, cached); // 301 永久重定向（瀏覽器會快取）
return;
}
// 2. 查 DB
const record = await db.query("SELECT original_url FROM urls WHERE short_code = $1", [code]);
if (!record) {
res.status(404).send("Not found");
return;
}
// 3. 寫入 Cache
await redis.set(`url:${code}`, record.original_url, "EX", 3600);
res.redirect(301, record.original_url);
});架構圖
架構圖解讀：Client 發送 HTTP 請求到 Load Balancer，LB 分配到 API Server。建立短網址時，API Server 向 ID Generator（Snowflake）取得唯一 ID，Base62 編碼後存入 DB。讀取短網址時，先查 Redis Cache（命中率可達 80%+），Cache Miss 才查 DB。DB 按 short_code 做 Sharding，確保讀寫均勻分佈。
實戰補充
💡301 vs 302 重定向
- 301 Moved Permanently：瀏覽器會快取，下次直接跳轉不經過伺服器。省伺服器資源，但無法追蹤點擊次數。
- 302 Found：每次都經過伺服器再跳轉。可以追蹤點擊數據、做 A/B 測試。
- 實務上 bit.ly 等服務使用 301 搭配非同步日誌記錄來兼顧效能和追蹤。
面試常見問題與參考答案：
Q：如果同一個長 URL 被多次提交，要回傳同一個短碼嗎？ A：看需求。如果要去重，就對長 URL 做 Hash 當 Cache Key 先查一次；如果不去重（不同用戶想各自追蹤點擊數），就每次產生新短碼。bit.ly 選擇不去重，因為每個用戶需要獨立的點擊統計。
Q：短碼用完了怎麼辦？ A：7 位 Base62 有 3.5 兆組合，每日 1 億個也夠用 96 年。真的不夠就擴展到 8 位（62^8 = 218 兆）。也可以回收過期的短碼。
Q：如何處理惡意 URL？ A：寫入時用 URL 黑名單 + Google Safe Browsing API 檢查。重定向時加一個中間頁面警告用戶「你即將離開本站」。
理解測驗
🤔 Base62 編碼 7 位短碼可以產生多少個唯一短網址？
🤔 為什麼自增 ID + Base62 編碼比 Hash 截取更好？
🤔 短網址服務的讀寫比是 100:1，架構設計應該優先優化什麼？
重點整理
💡一句話記住
唯一 ID → Base62 → Redis 快取 → 快速重定向。 記憶口訣：「生碼存查」— 生成唯一 ID、編碼為短碼、存入快取、查詢重定向。核心挑戰就兩個：短碼唯一性和讀取低延遲。
| 概念 | 說明 | |------|------| | Base62 編碼 | 62 個字元組合，7 位可產生 3.5 兆唯一碼 | | Snowflake ID | 分散式唯一 ID 生成器，避免碰撞 | | 301 vs 302 | 301 瀏覽器快取省資源，302 每次經過伺服器可追蹤 | | Cache 策略 | 熱門短碼放 Redis，Cache Aside 模式 | | Sharding | 按 short_code Hash 分片，均勻分散讀寫 |