這篇整理 SRE 面試高頻的 System Design 核心概念: Redis 的資料結構與使用場景、四種 Rate Limiting 演算法、Circuit Breaker 的三個狀態, 以及 Scaling Reads 和 Scaling Writes 的常見設計模式。

## Redis

### 為什麼需要 Redis

資料庫每次讀取都要走磁碟 I/O, 延遲約 1-10ms。Redis 把資料存在記憶體, 延遲約 0.1ms。對於熱資料 (頻繁讀取、不常變動), cache 可以讓資料庫壓力降低幾個數量級。

Redis 是 key-value store, 但不只是 cache — 它的資料結構讓它能勝任多種不同的角色。

### 五種資料結構

| 結構 | 類比 | 適合場景 |
|------|------|---------|
| String | 變數 | cache、session、計數器 |
| Hash | 物件/dict | 使用者資料、設定檔 |
| List | 雙向佇列 | 訊息佇列、最近活動紀錄 |
| Set | 無序集合 | 標籤、好友清單、去重 |
| Sorted Set | 有分數的集合 | 排行榜、優先隊列、時間序列 |

```text
String:
  SET user:123:name "Alice"
  GET user:123:name  -> "Alice"
  INCR user:123:loginCount  -> atomic increment

Hash:
  HSET user:123 name "Alice" age 30 city "Toronto"
  HGET user:123 name  -> "Alice"
  HGETALL user:123    -> all fields

List:
  RPUSH queue:tasks "job1" "job2"
  LPOP queue:tasks  -> "job1"  (FIFO)

Set:
  SADD user:123:tags "golang" "devops"
  SMEMBERS user:123:tags  -> {"golang", "devops"}

Sorted Set:
  ZADD leaderboard 9500 "user:123"
  ZADD leaderboard 8200 "user:456"
  ZREVRANGE leaderboard 0 9 WITHSCORES  -> top 10 with scores
```

### 七個使用場景

**Cache**: 最常見。讀資料庫後存入 Redis, 下次直接從 Redis 拿。TTL 控制過期。

**Distributed Lock**: 多個服務搶同一資源時 (例如搶票), 用 `SET key value NX EX 300` 建 lock。`NX` = 只有 key 不存在時才設定 (原子操作), 避免兩個 instance 同時拿到 lock。`EX 300` = 300 秒後自動釋放, 防止 lock 永遠不釋放。

**Leaderboard**: Sorted Set 天生支援排行榜。`ZADD` 加分數, `ZREVRANGE` 取前 N 名, 時間複雜度 O(log N)。

**Rate Limiting**: 用 `INCR` 計數, 每個 key 代表一個時間窗口。跨多個 API Gateway instance 共享同一個 Redis, 做到全域限流。

**Proximity Search**: `GEOADD` 加入座標, `GEODIST` 計算距離, `GEOSEARCH` 找範圍內的點。適合外送、叫車、地圖搜尋。

**Streams**: 類似 Kafka 的訊息流, 支援 consumer group、訊息持久化、重播。比 Pub/Sub 更可靠。

**Pub/Sub**: 發布/訂閱模式, 即時推送通知。特性是 fire-and-forget — 訊息送出後不保證對方收到, 斷線期間的訊息會遺失。適合即時通知, 不適合需要保證送達的場景。

### Hot Key 問題

Hot Key 是指被大量請求集中打到同一個 Redis key 的情況。例如明星發文, 幾百萬人同時讀同一個貼文的 cache key, 造成那個 key 所在的 Redis node 過載。

三種解法:

**本地快取 (Local Cache)**: 在每個應用服務 instance 上存一份記憶體內 cache, 減少打到 Redis 的請求數量。缺點是各 instance 的 cache 可能不一致, 且不同 instance 占用的記憶體加總起來會大很多。

**副本 (Replica)**: 把 Hot Key 複製到多個 Redis 節點, 例如 `post:viral:123:replica1`, `post:viral:123:replica2`。讀取時隨機選一個副本, 分散壓力。缺點是需要額外的管理邏輯來維護副本的一致性。

**Key 分散 (Key Sharding)**: 在 key 後面加隨機後綴 `post:viral:123:{0~9}`, 寫入時同時寫到所有後綴, 讀取時隨機選一個。本質上是把 Hot Key 打散到多個物理 key, 利用 Redis Cluster 的不同 slot 分流。這是最根本的解法, 因為它直接把流量分散到不同節點, 而不只是減少請求數量。

### 三種部署模式

| 模式 | 特性 | 適合 |
|------|------|------|
| Standalone | 單節點, 簡單 | 開發環境 |
| Sentinel | 主從複製 + 自動 failover | 中型系統, HA 需求 |
| Cluster | 自動分片, 多主節點 | 大型系統, 水平擴展 |

## Rate Limiting

### 四種演算法

**Fixed Window**: 把時間切成固定窗口 (例如每分鐘), 每個窗口有一個計數器。請求進來時計數器加一, 超過上限就拒絕。

```text
Window: 00:00 - 01:00
Counter: 95 requests
Limit: 100

request at 00:59 -> counter = 96 -> allowed
request at 01:00 -> new window, counter = 0 -> allowed
```

問題: 窗口交界處可以瞬間打兩倍流量 — 00:59 的 100 次 + 01:00 的 100 次 = 2 秒內 200 次。

**Sliding Window**: 計算的是「過去 N 秒內」的請求數, 而不是「這個窗口內」。解決 Fixed Window 的邊界問題。代價是需要記錄每筆請求的時間戳, 儲存成本較高。

**Token Bucket**: 令牌桶以固定速率產生令牌 (例如每秒 10 個), 桶有容量上限。每個請求消耗一個令牌, 桶空了就拒絕。允許短暫的流量爆發 (burst) 只要桶裡有令牌。適合允許一定彈性的 API。

```text
Bucket capacity: 100 tokens
Refill rate: 10 tokens/second

Burst scenario:
  - bucket is full (100 tokens)
  - 80 requests arrive at once -> allowed (80 tokens consumed)
  - next second: 10 tokens refilled
```

**Leaky Bucket**: 請求進入一個固定容量的佇列 (桶), 以固定速率從桶底流出處理。桶滿了就拒絕新請求。輸出速率絕對平滑, 沒有 burst。適合需要嚴格控制流量的場景 (例如付費 API)。

| 演算法 | Burst 支援 | 實作複雜度 | 適合場景 |
|--------|-----------|-----------|---------|
| Fixed Window | 是 (邊界) | 最低 | 簡單 API |
| Sliding Window | 否 | 中 | 精確限流 |
| Token Bucket | 是 (可控) | 中 | 一般 API |
| Leaky Bucket | 否 | 中 | 嚴格平滑輸出 |

### 分散式 Rate Limiting

多個 API Gateway instance 各自計數, 用戶可以把限流繞過去 — 打三個 instance 各打 100 次, 實際是 300 次。

解法: 所有 instance 共用 Redis 做計數器。

```text
Gateway A --\
Gateway B ----> Redis (shared counter) -> enforce global limit
Gateway C --/
```

```text
INCR rate:user:123:minute:1744840800   # key = user + current minute timestamp
EXPIRE rate:user:123:minute:1744840800 60
```

`INCR` 是原子操作 — Redis 保證同一時間只有一個操作能修改這個 key, 不會有兩個 instance 同時讀到相同的數字再各自加一的問題。

## Circuit Breaker

### 為什麼需要 Circuit Breaker

Service A 呼叫 Service B, B 開始回應很慢 (例如資料庫過載)。A 的請求堆積等待 B 的回應, A 的線程全部被卡住, A 也開始無法處理新請求。這就是 Cascading Failure (級聯失敗) — 一個服務的問題蔓延到上游。

Circuit Breaker 的設計: 偵測到下游失敗率超過閾值時, 直接短路 (不再嘗試呼叫 B), 立刻回傳錯誤或 fallback。讓 A 保持可用, 不被 B 拖垮。

### 三個狀態

```text
Closed -> (error rate > threshold) -> Open
Open   -> (after timeout)          -> Half-Open
Half-Open -> (test request fails)  -> Open
Half-Open -> (test request ok)     -> Closed
```

**Closed (正常)**: 所有請求正常送出。統計失敗率, 超過閾值就切到 Open。

**Open (斷開)**: 不再嘗試呼叫下游, 直接回傳錯誤或 fallback 結果。讓下游有時間恢復。

**Half-Open (試探)**: 等待一段時間後, 放行少量測試請求。如果成功, 切回 Closed。如果還是失敗, 回到 Open 繼續等待。

Fallback 可以是: 回傳快取的舊資料、回傳預設值、降級功能 (例如電商不顯示個人化推薦, 改顯示熱門商品)。

## Scaling Reads

讀流量擴展的標準路徑: Index → Denormalization → Read Replica → Sharding → Caching Layer → CDN。

### Cache Invalidation

Cache 的核心問題: 資料更新後, cache 裡的舊資料什麼時候失效?

**TTL**: 最簡單。設定過期時間, 時間到自動失效。缺點是資料更新到 TTL 過期這段時間, 用戶看到的是舊資料。

**Write-through**: 每次寫入資料庫時, 同步更新 cache。資料一致性最高, 但增加寫入延遲。

**Write-behind (Write-back)**: 先寫 cache, 非同步批次寫入資料庫。寫入速度快, 但 cache 當機時可能遺失資料。

**Tagged Invalidation**: 給 cache key 打標籤。更新資料時, 把該分類下的所有 cache key 一起失效。例如「所有 category:electronics 的商品 cache」。

**Versioned Keys**: key 加版本號, 例如 `product:123:v5`。更新資料時, 版本號加一, 舊 key 自然失效 (沒人讀就等 TTL 自動清除)。好處是不需要主動刪除 cache, 舊 key 繼續存在但不會被讀到。缺點是需要一個地方儲存「目前最新版本號是多少」。

TTL 和 Write-through 通常一起用 — Write-through 確保資料更新立刻反映, TTL 作為保底機制。

### CDN 與 Edge Caching

CDN (Content Delivery Network) 在全球多個節點 (edge) 儲存靜態資源的副本。用戶讀取時打到最近的 edge node, 不需要每次都打到 origin server。

動態內容也可以 cache 在 CDN — 例如 API 回應在 CDN edge 快取 30 秒。要注意 cache invalidation: 資料更新後要主動 purge CDN 的快取。

### Cache Stampede

Cache 過期的瞬間, 大量請求同時穿透到資料庫, 造成資料庫瞬間過載, 這叫 Cache Stampede (快取雪崩)。

三種解法:

**Request Coalescing (請求合併)**: 第一個打到 cache miss 的請求去查資料庫, 其他請求等待。資料庫回傳後, 所有等待的請求一起拿到結果。問題是需要一個協調機制判斷「誰是第一個」— 通常用 Distributed Lock 實作, 拿到 lock 的去查 DB, 其他人等 lock 釋放後再讀 cache。

**Stale-While-Revalidate**: 先回傳過期的舊資料給用戶 (不讓用戶等待), 同時非同步去更新 cache。用戶感受不到延遲, 但有短暫的資料不一致窗口。適合對時效性要求不高的場景。

**Probabilistic Early Refresh**: 在 cache 到期之前, 用機率決定是否提前刷新。越接近到期時間, 刷新的機率越高。這樣 cache 不會在同一時間大量到期, 流量分散到各個時間點。適合高流量系統, 不需要 Distributed Lock, 實作相對簡單。

實際使用上, Request Coalescing 和 Stale-While-Revalidate 常一起用, Probabilistic Early Refresh 是更進階的解法。

## Scaling Writes

寫流量擴展比讀流量複雜, 因為寫入需要保證一致性。

### 資料庫選型

選資料庫是寫 Scaling 的第一步, 不同 DB 對高寫入的支援能力差異很大。

| 資料庫 | 適合場景 | 寫入特性 |
|--------|---------|---------|
| PostgreSQL | 一般交易型系統 | ACID, 強一致 |
| Cassandra | 高寫入, 時間序列 | Write-optimized, eventual consistency |
| InfluxDB | IoT, metrics | 時序資料, 高壓縮率 |
| Column Store | 分析查詢 | 批次寫入, 不適合即時 |

### Horizontal Sharding

資料量太大時, 把資料水平切分到多個資料庫 instance。

**Partition Key 選擇**: 決定資料落在哪個 shard 的依據。選不好會造成 hot shard — 大量資料集中在同一個 shard。

```text
user_id % 4 -> shard 0, 1, 2, 3

user:1 -> shard 1
user:2 -> shard 2
user:3 -> shard 3
user:4 -> shard 0
```

問題: cross-shard query 複雜, JOIN 無法跨 shard。需要在應用層做聚合。

### Vertical Partitioning

把不同的 table 或 column 拆到不同的資料庫。

```text
Before: one DB with all tables
After:
  Users DB    -> user_id, name, email
  Orders DB   -> order_id, user_id, amount
  Products DB -> product_id, name, price
```

和 Foreign Key 的差別: Vertical Partitioning 是物理上把 table 放到不同的 DB instance, 不只是邏輯上的關聯。跨 DB 的 JOIN 變成需要在應用層處理。

### Queue 解耦寫入

高峰流量時, 把寫入請求先放進 Queue, 非同步處理。

```text
User request -> API -> Queue -> Consumer -> DB
```

好處: API 立刻回應 (不等 DB 寫入), 流量峰值被 Queue 吸收。壞處: 資料不是立刻寫入, 用戶可能短暫看不到自己剛才的操作結果。

### Load Shedding

系統超載時, 主動拒絕低優先度的請求, 保護核心功能。

```text
Traffic spike:
  - Priority 1 (payment): always process
  - Priority 2 (read profile): process if capacity > 60%
  - Priority 3 (recommendation): drop if capacity < 40%
```

和 Rate Limiting 的差別: Rate Limiting 是對單一用戶限流, Load Shedding 是系統層級的優先度決策。

### Hierarchical Aggregation

高頻寫入的計數類資料 (例如按讚數、播放次數), 如果每個事件都直接寫入中央資料庫, root 會過載。

```text
Without aggregation:
  Event 1: likes++ -> Central DB
  Event 2: likes++ -> Central DB
  ... (1M events/sec -> Central DB explodes)

With Hierarchical Aggregation:
  Level 1 (edge nodes): buffer locally, aggregate every 1s
  Level 2 (regional nodes): aggregate from L1 every 10s
  Level 3 (central): receive pre-aggregated data every 60s
```

L1 node 每秒彙整一次, 送到 L2 的不是 1000 個事件而是一個「這 1 秒有 1000 個 likes」。L2 再彙整 10 秒的資料送到 central。Central 接收的是已經縮減幾個數量級的流量。

注意: root 收到的是彙整後的數量, 不是每個原始事件。如果業務需求是「知道每個用戶各自按了幾次讚」, 就需要在 edge 層保留更細的資料。Hierarchical Aggregation 適合「總數統計」, 不適合「明細追蹤」。

## References

- [Redis Data Types](https://redis.io/docs/data-types/)
- [Redis GEOSEARCH](https://redis.io/docs/latest/commands/geosearch/)
- [Redis Streams Introduction](https://redis.io/docs/data-types/streams/)
- [Redis Pub/Sub](https://redis.io/docs/interact/pubsub/)
- [Rate Limiting Patterns - Stripe Engineering](https://stripe.com/blog/rate-limiters)
- [Circuit Breaker Pattern - Martin Fowler](https://martinfowler.com/bliki/CircuitBreaker.html)
- [Cache Stampede - Wikipedia](https://en.wikipedia.org/wiki/Cache_stampede)
- [Thundering Herd Problem](https://en.wikipedia.org/wiki/Thundering_herd_problem)
- [Probabilistic Early Expiration - Research Paper](https://cseweb.ucsd.edu/~avattani/papers/cache_stampede.pdf)
- [Cassandra vs PostgreSQL - DataStax](https://www.datastax.com/blog/cassandra-vs-postgresql)
- [Designing Data-Intensive Applications - Martin Kleppmann](https://dataintensive.net/)