System Design Fundamentals

What You Should Understand

• 能清楚比較 vertical vs horizontal scaling，並解釋為什麼 stateless service 是水平擴展的前提
• 能區分 latency 和 throughput，並用 p50/p95/p99 percentiles 描述系統效能（而不是只講平均值）
• 能定義 SLA/SLO/SLI，背出 nines 對應的年停機時間，並說明 redundancy 與 failover 的設計
• 能用 CAP theorem 解釋 CP vs AP 的取捨，舉出真實資料庫的例子
• 能在 2 分鐘內做 back-of-the-envelope estimation：QPS、storage、bandwidth，且熟記 latency numbers
• 能解釋 consistent hashing、bloom filter、token bucket 等面試常考演算法的直覺與取捨

Scalability

Scalability is the ability of a system to handle growing load by adding resources. There are two fundamental directions:

直覺：vertical scaling 像把一台卡車換成更大的卡車；horizontal scaling 像改用一整個車隊。車隊需要調度系統（load balancer）、每台車不能記住「只有它知道」的事（stateless），但車隊可以無限加車、壞一台也不影響出貨。

Stateless Services: The Prerequisite for Horizontal Scaling

A stateless service keeps no client session data in local memory or disk — every request can be served by any instance.

• Stateful 的問題：如果 user session 存在 server A 的記憶體，load balancer 就必須用 sticky session 把同一個 user 永遠導到 A。A 掛掉 → session 消失；A 過熱 → 無法把流量分給 B。
• Stateless 的做法：把 state externalize 到 shared store（Redis 存 session、DB 存資料、S3 存檔案）。Web tier 的每台機器變成可以隨意增減、隨意替換的「牛」而不是「寵物」。
• Auto-scaling 因此成為可能：流量高峰加機器、離峰砍機器，因為任何一台新機器都能立刻服務任何 request。

Why Horizontal Wins at Scale

1. Fault tolerance: N 台機器壞 1 台，剩 N-1 台照常服務；一台大機器壞了就是全掛。
2. Cost: commodity server 的性價比遠勝頂規機器；cloud 上 horizontal scaling 還能隨流量彈性計費。
3. No ceiling: 世界上最大的單機也撐不起 Google 級的流量；水平擴展理論上沒有上限。
4. Rolling deploy: 一台一台更新，服務不中斷 — 單機做不到 zero-downtime deploy。

代價是複雜度：你需要 load balancing、service discovery、distributed cache、data partitioning — 這些正是後面章節（Scalability Patterns、Caching Strategies、Databases & Storage）的主題。

Latency vs Throughput

Two different questions about performance:

• Latency = how long one request takes（單一 request 從發出到收到回應的時間，單位 ms）。使用者「感覺到」的就是 latency。
• Throughput = how many requests the system completes per unit time（單位時間完成的工作量，例如 QPS、requests/sec、MB/s）。系統「扛得住」的量就是 throughput。

直覺：latency 是一台車過高速公路要多久；throughput 是這條高速公路每小時能通過幾台車。拓寬車道（加機器）能提高 throughput，但不會讓單一台車開得更快；想降 latency 要縮短路徑（cache、CDN、減少 round trips）。

Percentiles: Why Averages Lie

Latency is never a single number — it is a distribution. Report percentiles:

平均值會說謊的原因：latency 分布是右偏（right-skewed）的 — 大部分 request 很快，少數 request 因為 GC pause、cache miss、slow disk、lock contention 而非常慢。假設 99 個 request 花 10ms、1 個花 2000ms：平均是 29.9ms（看起來不錯），但 p99 是 2000ms — 每 100 個使用者就有 1 個等了 2 秒。

面試時的標準句型：「I would set an SLO on p95 and p99, not the mean, because latency distributions are right-skewed and the tail dominates user-perceived quality.」

Availability & Reliability

Availability = the fraction of time the system is operational and serving requests. Reliability = the probability the system performs correctly for a given duration（不出錯地連續運作）。一個每天閃斷 1 秒的系統 availability 很高但 reliability 差。

SLA / SLO / SLI

記法：SLI 是「量到什麼」、SLO 是「想達到什麼」、SLA 是「答應客戶什麼（沒做到要賠）」。SLA 通常比 SLO 寬鬆，留 buffer。SLO 和 SLI 之間的差距就是 error budget — 還可以「揮霍」的失敗額度，用來決定要衝 feature 還是先還穩定性的債。

The Nines Table

Availability is usually quoted in "nines":

直覺換算：一年約 525,600 分鐘；99.9% 的失效預算是 0.1% ≈ 526 分鐘 ≈ 8.76 小時。每多一個 9，允許的 downtime 除以 10 — 而達成成本大約乘以 10（更多 redundancy、更快的 failover、更嚴的變更管理）。5 個 9 意味著全年只能掛 5 分鐘，連「人工重開機」都來不及，一切 failover 必須全自動。

Redundancy and Failover

Eliminate single points of failure (SPOF) at every layer:

Failover patterns:

• Active-passive（hot standby）：備援機平時待命同步資料，主機掛掉時接手。切換有秒級空窗，但實作簡單。
• Active-active：多台同時服務、互為備援，容量利用率高，但要處理資料同步與衝突。
• Serial availability 的數學：串聯的元件會拉低整體 availability — 兩個 99.9% 的服務串在一起是 0.999 × 0.999 ≈ 99.8%。並聯（redundancy）則拉高：兩台各 99% 的機器同時掛掉的機率是 0.01 × 0.01 = 0.0001 → 整體 99.99%。

這條公式是面試金句：依賴鏈越長，可用性越低；備援越多，可用性越高 — 所以要縮短 critical path、為關鍵元件加 redundancy、為非關鍵依賴加 graceful degradation（降級而不是整個掛掉）。

CAP Theorem & Consistency Models

CAP theorem: in the presence of a network Partition, a distributed system must choose between Consistency (every read sees the latest write) and Availability (every request gets a response).

關鍵理解：P 不是選項，是現實 — 網路一定會斷（switch 壞掉、跨機房光纖被挖斷）。所以真正的選擇題只有一題：分區發生時，你要拒絕服務保資料一致（CP），還是繼續服務容忍舊資料（AP）？

Strong vs Eventual Consistency

直覺：strong consistency 像全公司共用一份即時同步的 Google Doc；eventual consistency 像大家各自改本地檔案、晚上再合併 — 白天看到的版本可能不同，但最終會一樣。

Quorum 的經典公式（N replicas, W write acks, R read acks）：

例如 N=3, W=2, R=2 → 任何 read 至少會碰到一個有最新寫入的 replica。調 W=1, R=1 就變成 eventual consistency，換來更低的 latency。

Back-of-the-Envelope Estimation

面試官問「設計 Twitter」時，第一步永遠是把模糊需求變成數字。目的不是算得準，是展現量級感與合理假設能力。

Powers of Two and Data Volume

常用速算：一天 86,400 秒（心算用 100K）；一年約 3,150 萬秒（心算用 30M）；1 million requests/day ≈ 12 QPS；1 billion requests/day ≈ 12K QPS。

QPS, Storage, Bandwidth

Standard estimation formulas:

範例（做給面試官看的心算過程）：一個服務有 100M DAU，每人每天 10 個 requests：

• Requests per day = 100M × 10 = 1B → Average QPS = 1B ÷ 86,400 ≈ 12K QPS
• Peak QPS ≈ 2.5 × 12K = 30K QPS
• 若 10% 的 requests 是寫入、每筆 1 KB → 每天寫入 100M × 1 KB = 100 GB/day → 一年 36.5 TB，乘 replication factor 3 ≈ 110 TB/year
• Bandwidth（read 為主）：12K QPS × 10 KB response ≈ 120 MB/s average

Latency Numbers Every Engineer Should Know

從這張表推出的設計原則（面試常考的「為什麼」）：

1. Memory is fast, disk is slow → cache 熱資料在記憶體（Redis/Memcached）。
2. 避免 disk seek → 資料庫用 sequential write（WAL、LSM-tree）而不是 random write。
3. 跨資料中心 round trip 是 ms 級 → 跨區同步複寫很貴；用 CDN 把內容推近使用者。
4. 壓縮便宜、網路貴 → 傳輸前先壓縮。
5. 一次 request 內的 RPC 次數決定 latency 下限 → 減少 round trips（batch API、parallel fan-out）。

Top 20 System Design Concepts

面試前的總複習清單 — 每個概念一句話，以及本站深入介紹的章節：

Key Algorithms for System Design Interviews

這些演算法是 system design 題的「積木」— 面試官不會叫你證明，但會期待你講得出直覺、複雜度與使用場景。

Consistent Hashing

Problem: 用 hash(key) mod N 把資料分到 N 台 server 時，N 一變（加減機器）幾乎所有 key 都要搬家 → cache 全滅、DB 大遷移。

Solution: 把 hash space 想成一個環（0 到 2^32 - 1）。Server 和 key 都 hash 到環上，key 由順時針方向遇到的第一台 server 負責。加一台 server 只影響它逆時針方向那一段的 keys — 平均只需搬移 K/N 的資料。

Virtual nodes: 每台實體 server 在環上放 100-200 個虛擬節點。目的：（1）讓負載更平均（單點 hash 可能讓某台接手超大區段）；（2）容量不同的機器可以放不同數量的 virtual nodes 實現 weighted 分配；（3）一台掛掉時，它的負載平均分給所有存活機器，而不是全砸給順時針的下一台。

Bloom Filter

A space-efficient probabilistic data structure answering "is this element possibly in the set?"

• 一個 m bits 的陣列 + k 個 hash functions。加入元素：把 k 個 hash 位置設為 1。查詢：k 個位置全是 1 → 「可能存在」；任一是 0 → 「絕對不存在」。
• No false negatives, possible false positives：說「不在」一定對；說「在」可能誤判（其他元素恰好填滿了那些 bits）。
• 不能刪除（清 0 會誤傷別的元素）— 需要刪除用 counting bloom filter 或 cuckoo filter。
• False positive rate approximately equals（n 個元素、m bits、k 個 hash）：

經典用途：cache 前擋掉「絕對不存在」的查詢避免 cache penetration、爬蟲判斷 URL 是否看過、Cassandra/HBase 判斷 SSTable 是否含某 key（省掉 disk read）、瀏覽器檢查惡意網址。

Rate Limiting Algorithms

Token bucket 和 leaky bucket 的直覺差異：token bucket 管「你平均不能超速，但允許短暫衝刺」；leaky bucket 管「不管你怎麼來，我輸出永遠等速」。

Spatial Indexing: Quadtree vs Geohash

用於「找出我附近的餐廳/司機」這類 proximity 查詢 — 直接對千萬個點算距離是 O(n)，需要空間索引。

HyperLogLog

Problem: 精確計算「今天有幾個 unique visitors」需要一個巨大的 set — 1 億個 user id 可能要幾 GB。

Intuition: 把每個元素 hash 成均勻隨機的 bit string。觀察到「開頭連續 k 個 0」的 hash，大約代表看過 2^k 個不同元素（就像連續丟出 10 次正面硬幣，大概暗示你丟了上千次）。HyperLogLog 把元素分到多個 buckets、各自記錄最長前導零、再取調和平均數 — 用約 12 KB 的記憶體估出上億級的 cardinality，誤差約 0.81%（Redis 的 PFCOUNT 實作）。

用途：unique search queries、DAU 估算、廣告 unique impressions — 任何「大量、可容忍小誤差」的去重計數。

Real-World Use Cases

Case 1: 推薦系統 API 的容量估算

你在電商公司負責推薦系統，PM 說「首頁要加個性化推薦模組」。開工前你要回答：需要幾台 serving 機器？feature store 要多大？

套用本頁概念：先做 back-of-the-envelope，再讓數字驅動架構決策。

# Assumptions (state them out loud in an interview)
dau = 20_000_000                  # 20M daily active users
views_per_user = 6                # homepage visits per user per day
requests_per_day = dau * views_per_user            # 120M requests/day

avg_qps = requests_per_day / 86_400                # ~1,400 QPS average
peak_qps = avg_qps * 3                             # ~4,200 QPS at peak

# Storage: user embeddings in the online feature store
embedding_bytes = 128 * 4         # 128-dim float32 vector = 512 B
total_users = 100_000_000         # all registered users
storage = total_users * embedding_bytes           # ~51 GB -> fits in a Redis cluster

# Latency budget: 200 ms end-to-end
# feature fetch ~20 ms + candidate generation ~50 ms
# + ranking ~50 ms + network/serialization ~30 ms -> ~50 ms buffer

結論會直接影響設計：4,200 peak QPS × 單台 model server 500 QPS → 約 9 台加上 redundancy 開 12 台；51 GB embeddings 放得進 memory → 用 Redis 而不是掃 DB；latency budget 200ms 內要塞 4 個步驟 → 每步都要有 p99 預算，而不是只管平均。

Interview follow-ups：

• 如果 DAU 成長 10 倍，哪個元件先爆？（feature store 的 QPS 和 model serving 的機器數 — storage 只是線性長）
• 為什麼用 p99 訂每個步驟的 latency budget？（串聯步驟的 tail 會疊加，平均值會低估使用者實際體驗）
• Peak 用 3 倍夠嗎？（電商有大促 — 需要看歷史峰值，大促可能是 10 倍，見 Case 3）

Case 2: 詐欺偵測系統的 Availability 設計

你的詐欺偵測模型攔在交易鏈路上：每筆刷卡都要先過你的 API 才能放行。風控主管問：「你的服務掛掉，全公司交易都停 — 你要怎麼保證不掛？」

套用本頁概念：這是 availability、redundancy、graceful degradation 的綜合題。

• 訂 SLO：交易鏈路要求 99.99%（每年只能停 52.6 分鐘）→ 人工介入來不及，failover 必須全自動。
• 消除 SPOF：model server 至少 3 個 instances 跨 AZ 部署（並聯公式：單台 99.9%，三台同掛的機率趨近 0）；load balancer 用 active-passive pair；feature store（Redis）開 replica。
• Graceful degradation（關鍵設計）：ML model 超時或全掛時，降級到 rule-based fallback（例如金額低於閾值 + 熟悉裝置 → 直接放行），而不是擋掉所有交易。寧可短時間多放過一點詐欺，也不能停止全公司收單。
• CAP 的應用：詐欺判斷讀的 user 歷史特徵可以接受秒級 stale（AP、eventual consistency，換取低延遲高可用）；但「這筆交易已被判定並記錄」的決策日誌必須強一致（CP），否則重複扣款爭議無法追溯。
• Timeout budget：交易整體 SLA 500ms，分給詐欺偵測 100ms — 超時即觸發 fallback，絕不讓下游等。

Interview follow-ups：

• Fallback 規則放行的詐欺損失 vs 停止收單的營收損失怎麼權衡？（量化：停機一分鐘的 GMV vs 降級一分鐘的預期詐欺額）
• 怎麼知道系統正在降級？（監控 fallback 觸發率的 SLI + 告警 — 降級是設計好的行為，但必須看得見）
• 為什麼不做同步跨 region 的強一致複寫？（跨區 round trip 約 150ms，會吃光 100ms 的 latency budget — latency numbers 直接否決這個方案）

Case 3: 電商大促的 Rate Limiting

雙 11 開賣瞬間，流量從平常的 4K QPS 衝到 80K QPS，其中一半是搶購腳本。你要保護下單服務不被打爆，同時不誤傷真實使用者。

套用本頁概念：rate limiting 演算法選型 + 分層限流 + idempotency。

• 演算法選擇：API gateway 層用 token bucket（允許真人操作的合理 burst，例如刷新兩次頁面），參數如每 user 桶容量 10、補充速率 2 tokens/sec。下單寫入層用 leaky bucket 概念的 queue — 下單請求進 message queue，以 DB 能承受的固定速率消化（削峰填谷）。
• 分層限流：全域限流（保護整體容量）→ per-user 限流（防單一腳本）→ per-IP 限流（防分散式腳本）。counter 存 Redis（單機 in-memory counter 在 horizontal scaling 下會失效 — 每台機器各數各的）。
• 避免 fixed window 陷阱：促銷開始的整點正是 window 邊界 — fixed window 會在 59 秒和 61 秒各放一整個配額，瞬間 2 倍流量。用 sliding window counter。
• Idempotency：被限流的 client 會 retry；下單 API 必須帶 idempotency key，確保 retry 不會產生重複訂單。
• 回應設計：被限流回 HTTP 429 + Retry-After header，讓正常 client 退避，而不是無腦立刻重試造成 retry storm。

Interview follow-ups：

• Rate limiter 本身掛掉怎麼辦？（fail-open 放行保可用 vs fail-closed 擋下保護後端 — 大促期間通常 fail-open 加上下游自我保護）
• 限流 counter 放 Redis，Redis 成為新瓶頸怎麼辦？（local cache + 週期同步的近似限流，犧牲精確度換 scalability）
• 怎麼區分搶購腳本和真人？（rate limiting 只是第一層 — 再疊加 device fingerprint、行為特徵、CAPTCHA 挑戰）

Hands-on: Core Algorithms in Python

Consistent Hashing Ring with Virtual Nodes

import hashlib
from bisect import bisect_right

class ConsistentHashRing:
    """Hash ring with virtual nodes for even key distribution."""

    def __init__(self, replicas=150):
        self.replicas = replicas          # virtual nodes per physical node
        self.ring = {}                    # hash value -> physical node name
        self.sorted_hashes = []           # sorted hash values for binary search

    def _hash(self, key):
        # md5 gives a uniform 128-bit hash; take the integer value
        return int(hashlib.md5(key.encode()).hexdigest(), 16)

    def add_node(self, node):
        # place `replicas` virtual nodes on the ring for this physical node
        for i in range(self.replicas):
            h = self._hash(node + "#" + str(i))
            self.ring[h] = node
            self.sorted_hashes.append(h)
        self.sorted_hashes.sort()

    def remove_node(self, node):
        # only keys owned by this node's virtual nodes are remapped (~K/N)
        for i in range(self.replicas):
            h = self._hash(node + "#" + str(i))
            del self.ring[h]
            self.sorted_hashes.remove(h)

    def get_node(self, key):
        # walk clockwise: first virtual node at or after hash(key)
        h = self._hash(key)
        idx = bisect_right(self.sorted_hashes, h)
        if idx == len(self.sorted_hashes):
            idx = 0                       # wrap around the ring
        return self.ring[self.sorted_hashes[idx]]

# Usage: adding a 4th node remaps only ~25% of keys, not ~100%
ring = ConsistentHashRing()
for node in ["cache-a", "cache-b", "cache-c"]:
    ring.add_node(node)

owner = ring.get_node("user:12345")       # deterministic owner for this key
ring.add_node("cache-d")                  # most keys keep their old owner

Token Bucket Rate Limiter

import time

class TokenBucket:
    """Allows bursts up to `capacity`; sustains `rate` requests/sec on average."""

    def __init__(self, capacity, rate):
        self.capacity = capacity          # max tokens (burst size)
        self.rate = rate                  # tokens added per second
        self.tokens = capacity            # start with a full bucket
        self.last_refill = time.monotonic()

    def _refill(self):
        # lazy refill: add tokens proportional to elapsed time, cap at capacity
        now = time.monotonic()
        elapsed = now - self.last_refill
        self.tokens = min(self.capacity, self.tokens + elapsed * self.rate)
        self.last_refill = now

    def allow(self, tokens_needed=1):
        # returns True if the request may proceed, False if rate-limited
        self._refill()
        if self.tokens >= tokens_needed:
            self.tokens -= tokens_needed
            return True
        return False                      # caller should return HTTP 429

# Per-user limiters: burst of 10 requests, sustained 2 requests/sec
limiters = {}

def is_allowed(user_id):
    if user_id not in limiters:
        limiters[user_id] = TokenBucket(capacity=10, rate=2)
    return limiters[user_id].allow()

Interview Signals

What interviewers listen for:

• 你會先問 requirements 和做估算（QPS、latency budget、availability target），而不是直接畫架構圖
• 你用 p95/p99 討論 latency，並能解釋為什麼平均值會誤導
• 你能背出 nines 對應的停機時間，並理解「每多一個 9 成本乘以 10」的含義
• 你講 CAP 時聚焦在「分區發生時的取捨」，並能舉出 CP（etcd、ZooKeeper）和 AP（Cassandra、DynamoDB）的真實例子
• 你講演算法時給的是直覺與取捨（bloom filter 無 false negative、token bucket 允許 burst），而不是死背定義

Practice

Flashcards

Quiz