Enter your search text in the box above

Select a result to preview

QR Code 產生器 (Design a QR Code Generator)

#case-study #system-design #url-shortener #read-heavy
一句話定位 + TL;DR（含 35 分鐘心智時鐘）

設計一個把 URL 轉成可掃描 QR code、掃描後 redirect 回原 URL 的服務（本質是 URL shortener 的近親）。系統 讀多寫少（write:read ≈ 1:100）、要求 redirect < 100ms。
招牌取捨：redirect 回 302（Temporary）而非 301（Permanent）——放棄瀏覽器快取省下的那一跳延遲，換取「QR code 擁有者隨時能改 / 刪對應 URL、且每次掃描都拿到最新狀態」。其餘決勝點：唯一 token 產生（SHA-256 + Base62 + DB UNIQUE 重試）、read-heavy 快取 + CDN offload、stateless 水平擴展 + read replica。
配速（35 min 預算）：~5 min 釐清需求 → ~5 min 容量估算 → ~3 min API + ~4 min 資料模型 → ~6 min 高階架構 → ~8 min deep dive（唯一 token / redirect 加速）→ ~5 min 擴展瓶頸 → ~2 min 收尾。開場先用一句話複述題目、宣告這個配速、並把細節標記為「待會 deep dive」——宣告配速本身就是高分動作，讓面試官知道你有限時面試的心智模型，也替你爭取「先框架、後細節」的許可。

1. 釐清需求與範圍 (Clarify & Scope ~5 min)

開場後先問清楚邊界，別急著畫架構（弱候選人最常見死因就是沒釐清就開始畫）。建議問題：

釐清問題 為何要問 / 影響到哪個決策 本題假設（依來源）
輸入是什麼？只有 URL 嗎？ 決定 token 產生與驗證邏輯 URL，ASCII，最長 20 字元
規模多大？多少使用者 / 多少 code？ 直接驅動估算與儲存選型 1 億使用者、10 億 QR codes
延遲要求？哪條路徑最敏感？ 決定是否需要 cache / CDN redirect < 100ms
讀寫比例？ 決定 read-heavy 架構走向 write:read ≈ 1:100
使用者需要管理（改 / 刪）已建立的 code 嗎？ 直接決定 301 vs 302 需要（可 edit / delete）
QR 圖像要支援自訂嗎（尺寸 / 顏色 / 邊框）？ 影響圖像生成 API 與是否快取圖檔 需要（dimension / color / border）
可用性要求？ 決定 replica / 容錯設計 High Availability，24/7
defer 話術

「唯一 token 怎麼產生 我先標記，等到 deep dive 再展開——現在先當成一個會回傳全域唯一 qr_token 的 black box，這樣我們能先把端到端流程串起來。」這招把細節推遲，保住架構敘事的連貫性。

2. 功能性與非功能性需求 (FR / NFR 與設計北極星)

設計北極星（NFR 直接導出後續所有選型的判準）：

NFR 導出的設計北極星 後續對映選型
低延遲 + read-heavy 讀路徑必須避開 DB 全表掃描、盡量打 cache / edge index on token、cache、CDN
10 億 code / 1 億用戶 token 空間要夠大、儲存要可估算、要能水平擴展 SHA-256+Base62、stateless app server
擁有者可改 / 刪 redirect 不可被永久快取 302（而非 301）
High Availability 單點不可成為故障點 read replica + failover、stateless 多實例
一句話北極星

「這是一個 read-heavy、低延遲、可變對應關係 的系統」——記住這三個詞，後面每個選型都能從它推回去。

3. 容量估算 (Back-of-Envelope ~5 min)

估算的目的不是算到精確，而是 驅動 DB / cache / sharding 決策（估算 → 選型的 hand-off）。回連 02-Distributed-Systems/05-Numbers-to-Know。

讀流量（redirect QPS）

每用戶每天 redirect 次數 ≈ 5
總 redirects/day = 100,000,000 users × 5 = 500,000,000 / day
QPS = 500,000,000 ÷ 86,400 s ≈ 5,787 redirects / sec

寫流量（create QPS）

write:read ≈ 1:100
create QPS ≈ 5,787 ÷ 100 ≈ 58 / sec   （遠低於讀，寫不是瓶頸）

儲存

10 億（1B）筆 × 200 bytes/row ≈ 200 GB
→ 單一 DB instance 在可預見未來足以承載（不需要立刻 sharding）

下表 QPS / 儲存量皆為 推導值（由「使用者數 × 每人次數」與「筆數 × 每筆大小」算出，來源僅給出 1 億用戶 / 10 億 code / 1:100 / <100ms 等輸入）。

維度 數字 對後續決策的意義
Redirect QPS ≈ 5,787 /sec（推導值） 必須靠 cache（甚至 CDN）扛住，不能每次打 DB
Create QPS ≈ 58 /sec（推導值，= 5,787 ÷ 100） 寫很輕，單一 write node 綽綽有餘
儲存量 ≈ 200 GB（推導值） 單台 DB 即可，本題不需要 sharding（關鍵結論）
讀寫比 1:100 印證 read-heavy → 讀路徑是所有優化重心
估算的最大收穫

200 GB 落在單機可承受範圍 → 本題刻意不上 sharding。能說清「為什麼不需要 sharding」比硬塞一個 sharding 方案更高分。對比 05-Database-Advanced/02-Sharding 的適用門檻。

4. 用到的積木 / Building Blocks Used

架構即目錄：先給導覽圖，再展開。下表每個決策都對映一個既有 concept note（無 alias 連結）；本表即「本案例練到哪些積木」的單一事實來源（single source of truth）。

設計決策 積木 在本題的作用（≤1 行）
容量估算驅動選型 02-Distributed-Systems/05-Numbers-to-Know 算出 ~5,787 QPS / 200GB，決定 cache 與「不 sharding」
REST endpoint 設計 03-API-Design/02-REST 以資源（qr_code）為中心定義 CRUD + 圖像取得
token 唯一性與快速查找 04-Database-Indexing/01-Indexing-Overview qr_token 建 index + UNIQUE，避免全表掃描、保證唯一
read-heavy 快取 07-Caching-Storage/01-Caching 把熱門 token→URL 對應放 cache，讀先打 cache
讀路徑擴展模式 10-Design-Patterns/01-Scaling-Reads cache + read replica + CDN 三層卸載讀流量
圖像靜態資源儲存 07-Caching-Storage/02-Blob-Storage QR 圖像存 object store，DB 只存 metadata + location
容錯與讀擴展 05-Database-Advanced/03-Replication 多個 read replica；write node 掛掉時升級 replica
stateless 水平擴展 02-Distributed-Systems/03-Scalability app server 無狀態，加機器即擴容
流量分散 11-Infrastructure/02-Load-Balancer LB 把請求平均分到多個 stateless app server
HTTP redirect 語意 01-Networking/03-HTTP-and-HTTPS 301 vs 302 的快取語意，本題選 302
edge 快取 / 圖像分發 11-Infrastructure/05-CDN 熱門 redirect 與 QR 圖像下放 edge node 降延遲

5. API 設計 (API Design ~3 min)

由資料模型與 FR 驅動，採 REST 資源風格（理據見 03-API-Design/02-REST）。

Method Path 用途 重點
POST v1/qr_code 建立 QR code（body 帶 url） 驗證 URL → 產生 qr_token → 回 { qr_token }
GET v1/qr_code_image/:qr_token?dimension=&color=&border= 取得 QR 圖像 依 query 指定 spec，回 { image_location }
PUT v1/qr_code/:qr_token 編輯對應 URL（body 帶 url） 改對應關係，回 { url }
GET v1/qr_code/:qr_token 取得原始 URL 後端查 QrCodes table
DELETE v1/qr_code/:qr_token 刪除 QR code 連帶做 cache invalidation
細節話術

圖像 API 回傳的是 image_location（資源位置）而非 inline binary——這替後面把圖像放 object store / CDN 留好伏筆，也讓回應輕量。

6. 資料模型與儲存選型 (Data Model & Storage Choice ~4 min)

核心只有一張表，它是後續所有決策的地基（故獨立成段）。

QrCodes
--------------------------------------------------
qr_token     VARCHAR  PK / UNIQUE / INDEX   ← 全域唯一短碼
url          VARCHAR  原始長網址（ASCII ≤ 20）
owner_id     BIGINT   建立者（管理 / 權限）
image_location VARCHAR object store 上的 QR 圖像位置（可選）
created_at   TIMESTAMP
last_accessed_at TIMESTAMP  ← 供清理 cron 判斷「長期未點」
--------------------------------------------------
~200 bytes / row × 1B rows ≈ 200 GB

儲存選型：

選項 適配本題嗎 理由
關聯式 DB（含 UNIQUE 約束 + index） ✅ 主選 需要 qr_token UNIQUE（碰撞偵測靠它）；schema 固定簡單；200GB 單機可扛
NoSQL KV △ 也行 token→url 本質是 KV，但本題還要 UNIQUE 保證與簡單 secondary 查詢，關聯式更直接
Object Store（Blob） ✅ 輔助 QR 圖像本身是靜態大物件，放 object store，DB 只存 image_location metadata

→ 積木：DB 選型理據見 06-Database-Tech/01-Database；圖像走 07-Caching-Storage/02-Blob-Storage；index/UNIQUE 見 04-Database-Indexing/01-Indexing-Overview。

邊界

「200GB 單機足夠」是 本題在當前規模下 的結論。若日後資料量 / QPS 暴增到單機放不下或寫入成瓶頸，才需要引入 05-Database-Advanced/02-Sharding——詳見第 9 段「What if 100x」。

7. 高階架構 (High-Level Design ~6 min)

把前面的積木串成端到端流程。先看兩條核心 flow，再看 scaled 架構。

(A) 建立 / 編輯 flow（create / edit）

Client
  │  POST v1/qr_code { url }
  ▼
App Server (stateless)
  │ 1. 驗證 URL 合法性
  │ 2. 產生全域唯一 qr_token  (black box → deep dive)
  │ 3. INSERT INTO QrCodes (qr_token UNIQUE, url, owner_id ...)
  │       └─ 若 UNIQUE 衝突 → 重新產生 token 重試
  ▼
DB (write node)  ──┐
  │                │（圖像為可選，需要時生成後存 object store）
  ▼                ▼
回傳 { qr_token }   Object Store (QR image, 取得 image_location)

(B) 掃描 / 取回 flow（redirect / retrieval）

使用者用相機掃描 QR  →  內嵌 URL: https://myqrcode.com/<qr_token>
        │  GET /<qr_token>
        ▼
   App Server (stateless)
        │ 1. 先查 Cache：token → url ?
        │      ├─ HIT  → 直接組 redirect
        │      └─ MISS → 查 DB（走 qr_token index，非全表掃描）→ 回填 cache
        ▼
   回傳 HTTP 302 Location: <original_url>
        │
        ▼
   瀏覽器跳轉到原始 URL（302 不被永久快取 → 下次仍經過我們 server）

(C) Scaled 架構（端到端）

                         ┌──────────────────────────────┐
   掃描熱門 QR 的請求 ─────►│           CDN (edge)          │  ← 見 11-Infrastructure/05-CDN
                         │  快取 QR 圖像 + 熱門 token→url  │
                         │  熱門 redirect 可直接在 edge 完成│
                         └───────────────┬──────────────┘
                                         │ (cache miss / 非熱門)
   Client ──────────────► Load Balancer ─┤
                          (流量分散)       │
                                         ▼
                         ┌───────────────────────────────┐
                         │   Stateless App Servers (N 台)  │  ← 加機器即水平擴展
                         └───────────────┬───────────────┘
                                         │ 1) 先查 ↓
                                         ▼
                              ┌────────────────────┐
                              │  Distributed Cache  │ (Redis/Memcached)
                              └─────────┬──────────┘
                                  cache miss
                                         ▼
                ┌──────────────────────────────────────────────┐
                │  DB:  Write node ──(replication)──► Read Replicas│
                │       (create/edit 走 write)   (redirect 讀走 replica)│
                └──────────────────────────────────────────────┘

   QR 圖像 (靜態 blob) ──► Object Store ──回源──► CDN ──► Client

關鍵 hand-off：LB → stateless app（任一台都能處理）→ cache（先擋）→ DB（read replica 扛讀，write node 扛寫）；圖像走 object store + CDN 與主資料路徑解耦。

8. 深入探討 (Deep Dives ~8 min)

不重複原則（link-don't-restate）

通用機制（caching 策略、index 原理、replication 細節）只在 concept note 解釋；這裡只講「本題怎麼用、選哪個、為什麼」。任一機制超過 ~3 行就砍掉改連結。本題無 home note 的新材料（SHA-256 token、Base62、UNIQUE 碰撞重試）才在此 inline 教學並登記到 new_concepts_introduced。

8.1 如何產生全域唯一 token

問題：每個 QR code 需要一個 全域唯一 的短碼 qr_token，且要能在 10 億規模下保持唯一。
為何是瓶頸：碰撞會讓兩個不同 URL 指向同一 token（資料正確性災難）；若每次產生都查一次 DB 確認唯一，又會拖慢 create。

新材料：SHA-256 + Base62（本案例首次 introduce，尚無 atomic note → 已登記 new_concepts_introduced）

  • SHA-256：把任意輸入雜湊成固定長度的值，提供足夠 熵（entropy） 讓輸出盡量唯一。純雜湊是 確定性的——同一長網址永遠得同一短碼，不需查 DB。若要「同輸入也得不同輸出」，在輸入加 secret / nonce（只用一次的隨機值）即可。
  • Base62：用 [0-9A-Za-z] 共 62 個字元表示數字，把雜湊的二進位輸出轉成更短、更好傳輸的字串。例：3842 → 3842÷62=61 餘 60 ("y")；61÷62=0 餘 61 ("z")；反向讀餘數 [61,60] → "zy"。取前 N 個字元當精簡 token，N 由 key space 大小決定，把碰撞機率壓到可接受。本題 10 億（1B）codes → 62^6 ≈ 568 億 >> 10^9，故 N=6（推導值） 即綽綽有餘（來源未硬性指定 N，重點是 N 取決於 key space 大小這個推導方法）。

方案 做法 優點 缺點
A. 純確定性雜湊 Base62(SHA-256(url)) 取前 N 碼 不查 DB、可重現 同 URL 永遠同 token（多人共用 / 無法區分擁有者）
B. 雜湊 + secret/nonce 輸入加隨機值再雜湊 每次都不同、可區分 需處理碰撞重試

選擇與理由：採 B（雜湊 + nonce）並以 DB 的 qr_token UNIQUE 兜底。即使 key space 夠大仍可能碰撞，故 碰撞偵測交給 DB：INSERT 時若 UNIQUE 衝突，DB 回錯 → 重新產生 token 重試 即可（碰撞率低，重試極少發生）。
→ 積木：04-Database-Indexing/01-Indexing-Overview（UNIQUE / index 機制）

8.2 如何確保 redirect 夠快（< 100ms）

問題：redirect QPS ≈ 5,787/sec，且要 < 100ms。
為何是瓶頸：若每次 redirect 都打 DB，流量一上來 DB 很快成為瓶頸（read-heavy 的典型死法）。

手段 做什麼 取捨
Index on qr_token 避免 full table scan；可設 primary（兼 UNIQUE）或 secondary index 幾乎無腦上，寫入略增成本
Cache（讀先打 cache） 熱門 token→url 存 cache，miss 才打 DB；寫入時更新 DB、刪除時做 invalidation local cache 簡單但 hit rate 低；distributed cache（Redis/Memcached）hit rate 高但複雜 / 成本高
CDN（edge 快取） 熱門 token→url 與 QR 圖像 下放 edge；熱門 redirect 甚至可直接在 CDN 完成，不經 app server 需處理 edge 失效；圖像是天生適合 CDN 的 static data

選擇與理由：三層疊加——index 保底（任何查詢都不全表掃描）、distributed cache 擋住大部分熱讀（hit rate 高，值得其複雜度）、CDN 把最熱的 redirect 與圖像推到使用者最近的 edge。多數 DB 自身在存取磁碟前也有 buffer cache，但 彈性與功能不如獨立 cache layer，故仍引入獨立 cache。
→ 積木：07-Caching-Storage/01-Caching、10-Design-Patterns/01-Scaling-Reads、11-Infrastructure/05-CDN

8.3 redirect 用 301 還是 302（招牌取捨）

問題：掃描後要回哪種 HTTP redirect？
為何重要：這決定了「擁有者改 / 刪 URL 後，舊掃描還會不會經過我們的 server」。

301 Permanent 302 Temporary
瀏覽器快取 會快取，未來可能 直接跳過我們 server 不快取，每次都經過我們 server
延遲 後續更快（少一跳） 每次都要一次 server 往返
對應關係可變？ ❌ 舊客戶端可能永遠指向舊 URL ✅ 改 / 刪後立即生效

選擇與理由：選 302。因為 FR 要求 擁有者可以刪除或修改對應關係，必須確保 每次掃描都取得最新狀態——這比 301 省下的那一跳延遲更重要。這就是本題的 core_tradeoff。
→ 積木：01-Networking/03-HTTP-and-HTTPS

9. 擴展與瓶頸 (Scaling & Bottlenecks ~5 min)

主動找出系統會先在哪裂開並補強（訓練 drive 而非被動回答）。

瓶頸 / 風險 補強手段 積木
App server 成為單點 / 算力不足 stateless 設計 → 回應後不留 request state → 加 instance 水平擴展，前面擺 LB 02-Distributed-Systems/03-Scalability、11-Infrastructure/02-Load-Balancer
讀流量壓垮 DB read replica（讀遠多於寫）分攤讀；redirect 走 replica 05-Database-Advanced/03-Replication
Write node 故障 把一個 read replica 升級為新的 write node（failover） 05-Database-Advanced/03-Replication
圖像請求 QPS 高、不想每次回源 object store CDN 讓各地使用者就近低延遲取圖 11-Infrastructure/05-CDN
長期沒被點擊的 URL 累積 cron job 定期掃描清理：先通知使用者即將刪除，再移除過期紀錄（靠 last_accessed_at） —
資料量 / QPS 暴增（100x） 屆時才考慮 sharding（當前 200GB 單機足夠，故先不做） 05-Database-Advanced/02-Sharding
drive 的關鍵句

「系統會 先在讀路徑裂開（5,787 QPS 全打 DB）→ 所以我用 cache + read replica + CDN 三層卸載；寫只有 ~58 QPS，寫不是當前瓶頸。」先指出最可能裂開處再補強，比逐項羅列更有說服力。

10. 取捨總表與收尾 (Trade-off Recap & Wrap-up ~2 min)

決策點 選擇 放棄了什麼 為什麼值得
Redirect 類型 302 301 的瀏覽器快取 / 少一跳延遲 換取擁有者可改 / 刪、每次取最新（招牌取捨）
唯一性保證 DB UNIQUE + 碰撞重試 「先查再寫」的直覺 原子、無 race condition、少一次 round-trip
讀路徑 index + cache + CDN 額外複雜度 / 成本 read-heavy + <100ms 的硬需求
圖像儲存 object store + CDN 放 DB 的簡單 圖像是大型 static data，與主資料解耦
DB 規模策略 單機 + read replica，不 sharding 「預先 sharding」的炫技 200GB 單機足夠，避免不必要複雜度
App 層 stateless + LB sticky session 的便利 任意水平擴展、容錯
收尾話術

「整題的單一錨點是 302：我們刻意不要瀏覽器快取，因為 QR 對應關係必須可變。其餘都是 read-heavy 的標準打法——index 保底、cache 擋熱、CDN 推到 edge、read replica + failover 撐可用性。當前規模 200GB 單機足夠，所以 我不會過早 sharding；若放大到 100x 才會走第 9 段提到的 sharding。」引用既有決策用連結，不重新推導。

後續追問演練 (Interviewer Follow-ups — "What if…")

為什麼這個系統選 302 而不是 301？

redirect QPS 怎麼估出來的？

兩個不同 URL 雜湊出相同 token 怎麼辦？

流量突然放大 100x（≈ 58 萬 redirects/sec），架構哪裡先撐不住？怎麼補？

某張 QR code 突然爆紅（hot key），單一 token 的讀全壓在一個 cache shard 上怎麼辦？

Write node 掛了，create / edit 全失敗，怎麼恢復可用性？

如果之後出現 TinyURL（URL shortener）這類近親題，QR 的哪些積木可直接遷移？（一般推論，非本來源所述）

為什麼這題刻意「不上 sharding」，但同樣 read-heavy 的某些系統卻需要？判斷準則是什麼？

cache 用 local（每台 app 自己一份）還是 distributed（Redis）？取捨怎麼權衡？

主動回想：白板重建 (Whiteboard from Scratch)

不看上文，照下面提示把整個設計重建一次。每格都該能 30 秒內口述。

常見陷阱 (Exam Traps for This Problem)