字數總計：0 個 | 閱讀時長：0 分鐘 |閱讀次數： 次

第08章：設計短網址生成器

第一步驟：了解問題並確立設計的範圍

系統設計面試問題通常會刻意保持開放，不把細節說清楚。如果想做出一個精心設計的系統，詢問並釐清問題的過程至關重要。

問題釐清對話

應試者：關於短網址生成器的運作方式，你能舉個例子嗎？

面試官：假設原始的網址為 https://www.systeminterview.com/q=chatsystem&c=loggedin&v=v3&l=long，你的服務就是要創建出一個長度比較短的等效網址，例如：https://tinyurl.com/y7keocwj。只要點擊這個短網址，就會把你重定向到原始的網址。

應試者：使用的流量會有多少呢？

面試官：每天要生成1億個網址。

應試者：短網址的長度能有多長？

面試官：越短越好。

應試者：短網址內可使用哪些字元？

面試官：短網址可以是數字(0-9)與大小寫字母(a-z、A-Z)的組合。

應試者：可以刪除或更新短網址嗎？

面試官：為了簡單起見，我們姑且假設不能刪除或更新短網址。

基本需求與核心功能

  1. 縮短網址：提供一個長網址，回傳一個短網址
  2. 網址重定向：使用一個短網址，能重新導向至原始的長網址
  3. 系統考量：應具備高可用性、可擴展性與容錯性

粗略的估算

寫入操作

  • 每天生成：1億個網址
  • 每秒寫入：1億 ÷ 24 ÷ 3600 ≈ 1,160 次

讀取操作

  • 假設讀寫比為 10:1
  • 每秒讀取：1,160 × 10 = 11,600 次

儲存需求（10年）

  • 總記錄數：1億 × 365 × 10 = 3,650億筆記錄
  • 儲存空間：3,650億 × 100 Bytes = 36.5 TB（假設平均網址長度為100字元）

第二步驟：提出高階設計並取得認可

API 端點

採用 REST 風格設計 API：

1. 縮短網址 (POST)

  • 路徑：POST api/v1/data/shorten
  • 請求參數：{ "longUrl": "longURLString" }
  • 回傳：短網址 (shortURL)

2. 網址重定向 (GET)

  • 路徑：GET api/v1/shortUrl
  • 回傳：透過 HTTP 重定向回傳 longURL

網址重定向流程

當伺服器收到短網址請求時，會透過 HTTP 301 重定向回應，將瀏覽器導向至原始的長網址。

Request URL: https://tinyurl.com/qtj503u
Request Method: GET
Status Code: 301
Location: https://www.amazon.com/dp/dp/B817V4NTFA?pLink=63eaef76...

重定向類型比較

  • 301 重定向（永久）
    • 瀏覽器會快取此重定向
    • 未來請求直接發送到長網址伺服器
    • 可降低短網址伺服器的負載
  • 302 重定向（臨時）
    • 瀏覽器不會快取
    • 每次請求都會先經過短網址伺服器
    • 有利於進行點擊率等數據分析

網址縮短流程

透過雜湊函式 f(x) 將長網址轉換為雜湊值（hashValue），這個雜湊值就是短網址的一部分。

要求：

  • 每個長網址都能轉換成一個雜湊值
  • 每個雜湊值都能對應回原始的長網址

第三步驟：深入設計

資料模型

將 <shortURL, longURL> 的對應關係保存在關聯式資料庫中。

簡化的資料表結構：

欄位類型說明
idPrimary Key主鍵
shortURLString短網址
longURLString長網址

雜湊函式

雜湊值長度計算

  • 字元集：[0-9, a-z, A-Z]，共 62 種可能字元
  • 需求：支援 3,650 億筆記錄
  • 計算：找到最小的 n 值，使得 62^n > 3,650億
  • 結果：當 n=7 時，62^7 ≈ 3.5 兆，足以滿足需求

兩種實現方法

方法一：雜湊 + 衝突解決
  1. 使用 MD5 或 SHA-1 等雜湊函式處理長網址
  2. 截取前 7 個字元
  3. 若發生衝突，在長網址後附加預定義字串，重新計算
  4. 可使用 Bloom 篩選器優化效能
方法二：Base 62 轉換
  1. 為每筆新的長網址生成唯一 ID（資料庫主鍵）
  2. 將 ID 從 10 進位轉換為 62 進位
  3. 例如：ID 11157 → 2TX

方法比較

特性雜湊+衝突解決Base 62 轉換
短網址長度固定不固定，隨ID值遞增
ID生成器不需要需要唯一ID生成器
衝突處理可能出現，需解決不可能出現
安全性不可預知下一個短網址可預知，有安全性疑慮

深入研究短網址流程（採用 Base 62）

  1. 輸入：使用者提供長網址 (longURL)
  2. 檢查：系統檢查 longURL 是否已存在於資料庫
  3. 若存在：直接從資料庫取出對應的 shortURL 並回傳
  4. 若不存在：由唯一 ID 生成器產生新的唯一 ID
  5. 轉換：使用 Base 62 轉換方法將 ID 轉換為 shortURL
  6. 儲存：將新的 ID、shortURL 與 longURL 存入資料庫

📌 BASE62轉換動畫範例

深入探討網址重定向流程

  1. 使用者點擊短網址連結
  2. 負載平衡器將請求轉發至 Web 伺服器
  3. 伺服器檢查快取中是否存在該 shortURL
    • 若存在：直接回傳 longURL
    • 若不存在：從資料庫查詢
  4. 若資料庫中也不存在，表示這是無效的 shortURL
  5. 將查詢到的 longURL 送回給使用者，觸發重定向

📌 短網址製作動畫範例

第四步驟：彙整總結

可額外討論的要點

  • 網路限速器：為防止惡意用戶大量請求，可根據 IP 位址等規則進行速率限制
  • Web 伺服器擴展：由於 Web 層是無狀態的，可以輕易地增加或移除伺服器來進行擴展
  • 資料庫擴展：可使用資料庫複寫（replication）與分片（sharding）等技術來擴展
  • 分析：整合分析功能，以追蹤連結的點擊次數與時間等資訊
  • 可用性、一致性與可靠性：這些是任何大型系統成功的核心概念
在GitHub上在編輯此頁面
Table of Contents