概述#

系統設計題看似艱難，實際上可以是最容易的題型之一。這類題目沒有「陷阱」、沒有技巧，也不需要記憶特定演算法。面試官想看的是你如何在真實工作中解決問題：提問、與人溝通、討論取捨。

系統設計題重視的是過程，而非最終設計本身。沒有完美的解答，只有在特定假設下良好的解答。

處理系統設計題的原則#

  • Communicate：主動與面試官溝通，坦承系統的限制與問題。
  • Go broad first：先掌握全局，不要一開始就深入某一細節或演算法。
  • Use the whiteboard：利用白板畫出系統架構，幫助面試官理解你的設計。
  • Acknowledge interviewer concerns：面試官提出疑慮時，不要漠視，應驗證並做出相應調整。
  • Be careful about assumptions：錯誤假設可能徹底改變問題方向，例如「資料是否需要即時更新」是完全不同的設計考量。
  • State your assumptions explicitly：明確說出你的假設，讓面試官有機會糾正你。
  • Estimate when necessary：在沒有精確數據時，善用估算（例如：儲存 10 億個 URL 需要多少空間）。
  • Drive：你要主導討論，持續提問、深入探討、提出改進，而非被動等待。

設計步驟（Design: Step-By-Step）#

Step 1：界定問題範圍（Scope the Problem）#

在開始設計前，必須清楚了解要設計什麼。

以設計 TinyURL 為例，需要釐清：

  • 用戶可以自訂短網址，還是系統自動產生？
  • 是否需要追蹤點擊次數的統計？
  • 短網址是否有過期時間？

列出主要功能或使用情境，例如：

  • 將長網址縮短為 TinyURL
  • 查詢某個 TinyURL 對應的統計資料
  • 根據 TinyURL 取得原始網址
  • 帳號管理與連結管理

Step 2：做出合理假設（Make Reasonable Assumptions）#

假設應合乎常理。例如：

  • 每天最多處理一百萬個新 URL（合理）
  • 系統有無限記憶體（不合理）

某些假設可能帶有「產品直覺」，例如短網址建立後是否應立即可用（通常是的），或統計資料可以延遲十分鐘（可接受）。

Step 3：畫出主要元件（Draw the Major Components）#

離開椅子，到白板上畫圖。可能包含：

  • 前端伺服器（或伺服器群）
  • 後端資料儲存
  • 爬蟲伺服器
  • 分析處理伺服器

從使用者行為出發，走過整個系統流程：使用者輸入一個新 URL，接下來發生什麼？

Step 4：找出關鍵問題（Identify the Key Issues）#

確定基本設計後，思考瓶頸與主要挑戰：

  • 某些 URL 可能會突然爆紅（例如被 Reddit 分享），造成流量暴增
  • 不宜對每次請求都直接查詢資料庫

面試官可能在此給予提示，善加利用。

Step 5：針對關鍵問題重新設計（Redesign for the Key Issues）#

根據找到的問題調整設計，可能是：

  • 加入快取層
  • 重新架構部分元件

持續更新白板上的圖，並坦承設計的限制。

可擴展演算法步驟（Algorithms that Scale: Step-By-Step）#

當題目要求設計一個可擴展的單一演算法（而非整個系統）時，使用以下方法：

Step 1：提問#

確保完全理解題目，不要在模糊的需求上設計。

Step 2：假設資料都在單一機器上（Make Believe）#

先假設沒有記憶體限制，在單機上解決問題，這給出了解法的基本輪廓。

Step 3：回到現實（Get Real）#

思考：一台機器能放多少資料？拆分資料時會產生什麼問題？

  • 如何將資料邏輯切分？
  • 一台機器如何知道去哪裡查找另一台機器的資料？

Step 4：解決問題（Solve Problems）#

針對 Step 3 找到的問題，逐一解決。可以繼續沿用 Step 2 的方法（加以修改），或在必要時徹底改變方法。

此過程通常是迭代的：解決一批問題後，可能出現新的問題，需要再次迭代。目標是展示你能分析和解決問題，而非重建頂級系統。

關鍵概念（Key Concepts）#

Horizontal vs. Vertical Scaling#

  • Vertical Scaling（垂直擴展）：增加單一節點的資源，例如為伺服器增加記憶體或 CPU。容易實施，但有上限。
  • Horizontal Scaling（水平擴展）：增加節點數量，例如新增多台伺服器，分散負載。

Load Balancer（負載平衡器）#

將流量均勻分配到多台伺服器，避免單點故障。需要配合一組具有相同程式碼和資料存取能力的克隆伺服器。

Database Denormalization and NoSQL#

隨著系統規模增大，SQL 資料庫的 JOIN 操作會變得非常緩慢。

  • Denormalization（反正規化）：在資料庫中儲存冗餘資料以加速讀取。例如，將 Teacher 的名字直接存入 Task 資料表，避免 JOIN。
  • NoSQL：不支援 JOIN，以不同方式組織資料，天生適合擴展。

Database Partitioning / Sharding（資料庫分片）#

將資料分散到多台機器，並確保能找到每筆資料所在的機器。常見方案：

  • Vertical Partitioning（垂直分片）：依功能分區，例如 profiles、messages 放不同分區。缺點：若某分區資料量過大，需要再次分片。
  • Key-Based (Hash-Based) Partitioning（雜湊分片）：以 mod(key, N) 決定資料放在哪台機器。缺點：新增伺服器時需重新分配所有資料，成本極高。
  • Directory-Based Partitioning（目錄分片）：維護一張查找表記錄資料的位置。優點：易於新增伺服器；缺點：查找表本身可能成為單點故障，且持續查詢會影響效能。

Caching（快取）#

記憶體中的快取提供極快的資料存取，通常是 key-value 結構，位於應用層與資料庫之間。

工作方式：

  1. 應用程式先查詢快取
  2. 若快取命中，直接返回結果
  3. 若未命中，從資料庫取得資料（並可選擇性地寫入快取）

可以快取查詢結果，也可以快取已渲染的頁面片段（例如最新文章列表）。

Asynchronous Processing & Queues（非同步處理與佇列）#

慢速操作應該非同步進行，避免使用者等待。

兩種模式：

  • 預先處理：用一個作業佇列定期更新資料（例如重新渲染熱門文章列表），資料可能稍微過時，但比讓使用者等待好。
  • 通知使用者：讓使用者知道處理需要時間，完成後再通知（例如匯入資料）。

Networking Metrics（網路指標）#

  • Bandwidth（頻寬）：單位時間內可傳輸的最大資料量，通常以 bits per second 表示。
  • Throughput（吞吐量）：單位時間內實際傳輸的資料量。
  • Latency（延遲）：資料從一端送到另一端所需的時間，即使是極小的資料量也有延遲。

用傳送帶比喻：

  • 加寬傳送帶 → 增加頻寬和吞吐量，但不改變延遲
  • 縮短傳送帶 → 降低延遲，但不改變吞吐量
  • 加快傳送帶速度 → 三者皆改善

延遲在某些情境（如即時遊戲）非常關鍵，且不像吞吐量可以透過壓縮來改善。

MapReduce#

MapReduce 是一個用於處理大量資料的框架，廣泛應用於大數據處理。

  • Map：接收資料，輸出 <key, value> 對
  • Reduce：接收一個 key 和對應的 value 集合，將其「歸納」並輸出新的 key-value

MapReduce 允許大量平行處理，使大規模資料處理具備可擴展性。

設計考量（Considerations）#

在設計系統時，應額外考慮以下問題：

  • Failures（故障）：系統的任何部分都可能故障，需要為各種故障情境制定計畫。
  • Availability and Reliability（可用性與可靠性）：可用性是系統正常運作時間的百分比；可靠性是在特定時間段內系統正常運作的機率。
  • Read-heavy vs. Write-heavy（讀取密集 vs. 寫入密集）：若寫入頻繁，可以考慮佇列化寫入；若讀取頻繁，可以考慮快取。兩者的設計決策大相徑庭。
  • Security（安全性）：安全威脅可能對系統造成毀滅性影響，需思考系統可能面臨的安全問題並設計相應防護。

這些只是起點。在面試中，要對取捨保持開放的態度，並坦承你的設計的局限性。

沒有「完美」的系統#

對於同一個系統（例如 TinyURL 或 Google Maps），兩個人可能在不同假設下設計出截然不同但都優秀的方案。你的目標是：

  1. 理解使用情境
  2. 界定問題範圍
  3. 做出合理假設
  4. 基於假設設計出可靠的方案
  5. 坦承設計的弱點

範例問題解析#

題目：給定數百萬份文件，如何找出所有包含特定詞彙列表的文件？詞彙可以任意順序出現，但必須是完整的詞彙。

Step 1（單機解法）#

預先處理每份文件，建立 Hash Table 索引，將每個詞彙映射到包含該詞彙的文件列表：

"books" -> {doc2, doc3, doc6, doc8}
"many"  -> {doc1, doc3, doc7, doc8, doc9}

查詢「many books」時，對兩個列表取交集，得到 {doc3, doc8}。

Step 2（分散式問題）#

資料量龐大時，需要將資料和 Hash Table 分散到多台機器。關鍵挑戰：

  1. 如何切分 Hash Table？依關鍵字切分，還是依文件切分？
  2. 若依關鍵字切分，處理一份文件的結果可能需要推送到多台機器
  3. 需要一張查找表，記錄哪台機器存有哪些資料

Step 3（解決方案）#

依字母順序切分關鍵字，每台機器負責一個範圍（例如 “after” 到 “apple”）。查詢時，先排序查詢詞彙，再將請求分送給對應的機器，各機器分別找出交集後，最終對所有結果取交集。

Backward Recursion and Dynamic Programming Sorting and Searching Forward