分散式系統理論

為什麼分散式系統很難 基礎 高頻

單機程式的世界是「確定的」：函式呼叫要嘛回傳、要嘛丟例外；記憶體寫入後立刻可讀；所有事件有一個全域的先後順序（CPU 時鐘）。一旦把系統拆到多台機器上，這三個假設全部瓦解。分散式系統的本質難度可以濃縮成一句話：你無法區分「對方很慢」與「對方掛了」，而且你也無法知道「現在」到底是幾點。

分散式運算的八大謬誤（Fallacies of Distributed Computing）

由 Sun 的 L Peter Deutsch 等人整理，是面試時展現「工程直覺」的好素材。每一條都對應到一個實際設計決策：

部分失敗（Partial Failure）

單機系統通常是「全有或全無」：kernel panic 就全部停。分散式系統則常處於部分失敗：一台節點 GC 停頓 5 秒、一條網路連結單向斷線、一顆磁碟變得極慢（gray failure）。最糟的不是「掛掉」，而是「半死不活」——它還會回應 health check，但每個請求要 3 秒。

當你送出一個 RPC 而沒有收到回應，可能的情況有：

1. 請求在網路上遺失，對方根本沒收到。
2. 對方收到了，正在排隊（過載）。
3. 對方處理到一半當機。
4. 對方處理完了，但回應在網路上遺失。
5. 對方處理完了，回應只是很慢（例如對方正在 stop-the-world GC）。

從呼叫端看，這五種情況完全無法區分。這就是為什麼「重試」一定要搭配「冪等」：第 4 種情況下重試會讓操作執行兩次。

不可靠的網路與不可靠的時鐘

非同步網路模型

訊息延遲沒有上界。實務上的網路（乙太網路 + TCP）就是非同步的：佇列壅塞、TCP 重傳都可能讓延遲任意變長。所以「timeout」只是猜測，不是事實。

Network partition

節點群被切成彼此無法通訊的兩群（或多群），但每群內部運作正常。也可能是非對稱的：A 能送給 B，B 送不回 A。

時鐘漂移（clock drift）

每台機器的石英振盪器速度不同，Google 的假設是最多約 200 ppm（每秒偏 200 微秒，約每 30 秒偏 6ms）。NTP 同步後還會發生「時間往回跳」。

Process pause

GC、VM 被 hypervisor 暫停、記憶體 swap、SIGSTOP——行程可能在任意兩行程式碼之間停頓數秒，自己卻毫無察覺。這是分散式鎖最大的敵人（後面會講）。

系統模型通常這樣分類，面試中提到能加分：

CAP 定理的正確理解與 PACELC 進階 高頻

CAP 是面試最常被問、也最常被答錯的題目。Eric Brewer 在 2000 年提出，2002 年由 Gilbert 與 Lynch 形式化證明。

C — Consistency

這裡的 C 指的是 linearizability（線性一致性）：每個讀取都能看到最近一次完成的寫入，整個系統看起來像只有一份資料。注意：和 ACID 的 C（滿足約束條件）完全不同。

A — Availability

每個送到非故障節點的請求，最終都必須得到一個非錯誤的回應（不能回 error、不能無限等待）。這是很強的定義：「99.99% uptime」不等於 CAP 的 A。

P — Partition tolerance

網路分區時（任意數量的訊息遺失），系統仍能繼續運作。

正確理解：P 不是選項

常見的「三選二」說法是誤導。在分散式系統中，網路分區一定會發生——你不能選擇「不容忍分區」，因為分區不是你能決定的。所以 CAP 真正的意思是：

常見誤解

PACELC

Daniel Abadi 在 2010 年提出：if Partition, then Availability or Consistency; Else, Latency or Consistency。也就是「就算沒有分區，強一致性也要付出延遲代價」——因為寫入要等多數副本確認、讀取要跟 leader 確認。

一致性模型光譜 進階 高頻

一致性模型是「系統對讀取結果的承諾」。越強的模型越容易推理，但越貴（延遲高、可用性低）。從強到弱：

Linearizability（線性一致性）

最強的單物件一致性。定義：每個操作看起來在它的「呼叫」與「回應」之間的某個瞬間原子地生效，且這個順序與真實時間（wall-clock）一致。白話說：一旦有任何一個讀取看到了新值，之後所有的讀取都必須看到新值（或更新的值）。

例子：Alice 看到比賽比分更新為 2:1，跟坐在旁邊的 Bob 說，Bob 刷新卻看到 1:1。這違反了 linearizability（Bob 的讀取在 Alice 的讀取之後才開始，卻看到更舊的值）。

需要 linearizability 的場景：leader election（只能有一個 leader）、分散式鎖、唯一性約束（使用者名稱不重複）、帳戶餘額不可為負。實作方式：單 leader 且讀寫都走 leader（且 leader 要確認自己仍是 leader）、共識演算法（Raft/Paxos）。

Sequential Consistency（順序一致性）

所有操作存在一個全域順序，且每個 process 自己的操作在這個順序中保持程式順序；但這個全域順序不需要與真實時間一致。差別在於：Linearizability 要求「如果 A 在 B 開始前完成，A 必須排在 B 之前」；Sequential 只要求每個 client 看到的順序相同且符合各自的程式順序。ZooKeeper 的讀取（不加 sync）提供的就是類似的保證：寫入是 linearizable，但讀取可能讀到 follower 的舊資料。

Causal Consistency（因果一致性）

有因果關係的操作，所有節點都必須以相同順序看到；沒有因果關係（並行）的操作，不同節點可以看到不同順序。

例子：Alice 發文「我丟了戒指」，接著發「找到了！」。Bob 回覆「太好了」。因果一致保證任何人看到 Bob 的回覆時，一定已經看到「找到了！」那篇。但另一個不相關的貼文，不同人可以看到不同順序。

重要性質：Causal consistency 是在不犧牲可用性（網路分區下仍可用）前提下能達到的最強一致性模型之一。實作通常需要 vector clock 或依賴追蹤。

Session 保證（Client-centric）

Eventual Consistency（最終一致性）

如果不再有新的寫入，所有副本最終會收斂到相同的值。這是非常弱的保證：沒說「多久」，也沒說「收斂前會讀到什麼」。實務上要搭配：收斂機制（read repair、anti-entropy）、衝突解決策略（LWW、CRDT），以及監控 replication lag。

DynamoDB 的讀取預設是 eventually consistent，可以指定 ConsistentRead=True 取得強一致讀（花費約兩倍的讀取容量）。

# 實作 read-your-writes：client 帶著自己最後寫入的版本號（例如 MySQL GTID / LSN）
import time

class ReplicaRouter:
    def __init__(self, leader, replicas):
        self.leader = leader
        self.replicas = replicas

    def write(self, session, key, value):
        version = self.leader.put(key, value)   # leader 回傳寫入後的 log position
        session["last_write_version"] = version  # 存在 cookie / session 中
        return version

    def read(self, session, key, wait_ms=50):
        need = session.get("last_write_version", 0)
        for r in self.replicas:
            if r.applied_version() >= need:      # replica 已追上此使用者最後寫入
                return r.get(key)
        # 全部落後：短暫等待一次，仍不行就讀 leader（犧牲一點 leader 負載換正確性）
        time.sleep(wait_ms / 1000)
        for r in self.replicas:
            if r.applied_version() >= need:
                return r.get(key)
        return self.leader.get(key)

複製（Replication）、Quorum 與衝突解決 進階 高頻

複製的目的有三：高可用（一台掛了還有別台）、擴展讀取（讀分散到多台）、降低延遲（資料放在使用者附近）。難點全部來自「資料會變」——如何讓多個副本的變更保持一致。

三種複製架構

同步 vs 非同步複製

• 同步：leader 等 follower 確認才回 client。保證 follower 有最新資料，但任一 follower 慢就全部慢、掛了就寫不進去。
• 非同步：leader 寫完本地就回。最快，但 leader 掛掉時尚未傳出的寫入會遺失（即使 client 已收到成功）。
• 半同步（semi-synchronous）：至少一個 follower 同步確認，其他非同步。MySQL semi-sync replication 就是這樣，是常見的折衷。

Leader failover 的陷阱

1. 判定 leader 死亡：只能靠 timeout。設太短 → 誤判（GC 停頓就換 leader），設太長 → 不可用時間長。
2. 選新 leader：通常選資料最新的 follower；需要共識避免兩邊各自選出 leader。
3. 舊 leader 復活：它還以為自己是 leader 並接受寫入 → 腦裂（split brain）。需要 fencing（epoch/term 號碼）讓舊 leader 的寫入被拒絕。
4. 資料遺失：非同步複製下，新 leader 可能缺少舊 leader 最後幾筆寫入。GitHub 2012 年曾發生 MySQL failover 後新 leader 的 auto-increment 計數落後，重新分配了已被 Redis 引用過的主鍵，造成資料洩漏到錯誤使用者。

Quorum：W + R > N

Leaderless 系統中，每個 key 存在 N 個副本。寫入需 W 個副本確認才算成功，讀取需查詢 R 個副本。如果 W + R > N，則讀取的副本集合與寫入成功的副本集合至少重疊一個，所以讀取一定能拿到至少一個最新值（再用版本號挑出最新的）。

Sloppy Quorum 與 Hinted Handoff

當 key 原本的 N 個「home 節點」有些連不上時，嚴格 quorum 會讓寫入失敗。Sloppy quorum 則允許把寫入暫時寫到 ring 上「下一個健康的節點」，湊滿 W 個確認。該節點會記下 hint（「這筆其實屬於節點 X」），等 X 恢復後把資料轉交回去，這叫 hinted handoff。

效果：寫入可用性大增（AP 取向）；代價：即使 W+R>N，讀取也可能讀不到最新值，因為新值在「替身節點」上。Cassandra 的 hinted handoff 有時間視窗（預設 3 小時），超過就只能靠 repair。

Read Repair 與 Anti-entropy（Merkle Tree）

副本之間的差異靠兩種機制修復：

Merkle tree：葉節點是一段 key range 資料的 hash，父節點是子節點 hash 的 hash。兩個副本先比 root hash，相同就完全一致（一次比對搞定）；不同就往下比子節點，只沿著不同的分支遞迴。差異很少時，比對成本約 O(差異數 × log n)。Cassandra 的 nodetool repair、DynamoDB 的原始 Dynamo 設計、Git、區塊鏈、BitTorrent 都用到 Merkle tree。

import hashlib

def h(b: bytes) -> bytes:
    return hashlib.sha256(b).digest()

def build_merkle(leaves: list[bytes]) -> list[list[bytes]]:
    """回傳每一層的 hash，levels[0] 是葉子，levels[-1] 是 root。"""
    level = [h(x) for x in leaves]
    levels = [level]
    while len(level) > 1:
        if len(level) % 2:                 # 奇數個：複製最後一個
            level = level + [level[-1]]
        level = [h(level[i] + level[i + 1]) for i in range(0, len(level), 2)]
        levels.append(level)
    return levels

def diff_ranges(a, b, depth=None, idx=0):
    """從 root 往下比對，只遞迴進 hash 不同的子樹，回傳不同的葉子索引。"""
    if depth is None:
        depth = len(a) - 1
    if a[depth][idx] == b[depth][idx]:
        return []
    if depth == 0:
        return [idx]
    out = []
    for child in (2 * idx, 2 * idx + 1):
        if child < len(a[depth - 1]):
            out += diff_ranges(a, b, depth - 1, child)
    return out

# 每個葉子代表一個 key range（例如 token range）的資料摘要
r1 = [f"range-{i}:v1".encode() for i in range(8)]
r2 = list(r1); r2[5] = b"range-5:v2"
print(diff_ranges(build_merkle(r1), build_merkle(r2)))   # [5]：只需同步第 5 段

衝突解決：LWW、Vector Clock、CRDT

Multi-leader 與 leaderless 都會遇到「兩個副本對同一個 key 做了並行寫入」。關鍵概念是並行（concurrent）：不是指時間上同時，而是「兩個操作互相不知道對方」，即沒有 happens-before 關係。

Last-Write-Wins（LWW）

每筆寫入帶時間戳，保留時間戳最大的。Cassandra 預設就是 LWW（cell 層級）。簡單，但會靜默丟資料：並行寫入只留一個；而且時鐘偏差可能讓「實際上較晚」的寫入因時間戳較小被丟掉。適用於「key 只寫一次、不可變」或「丟掉並行寫入可接受」的場景（例如快取、最新 GPS 位置）。

Version Vector / Vector Clock

每個副本維護一個向量 {node_id: counter}。比較兩個版本：若 A 的每個分量都 ≤ B，則 A happens-before B（B 可以覆蓋 A）；若互有大小，則並行，兩者都要保留（稱為 siblings），交給應用程式合併。Riak 用的就是這個；原始 Dynamo 論文的購物車範例也是：並行的兩個購物車取聯集（代價是刪除的商品可能「復活」，需要 tombstone）。

CRDT（Conflict-free Replicated Data Type）

設計一種資料結構，讓合併操作滿足交換律、結合律、冪等律（數學上是 join-semilattice）。這樣無論副本以什麼順序、收到幾次重複的狀態，合併結果都相同——自動收斂，不需要協調。

class GCounter:
    """Grow-only counter CRDT：每個節點只遞增自己的分量。"""
    def __init__(self, node_id: str):
        self.node_id = node_id
        self.counts: dict[str, int] = {}

    def incr(self, n: int = 1) -> None:
        assert n >= 0
        self.counts[self.node_id] = self.counts.get(self.node_id, 0) + n

    def value(self) -> int:
        return sum(self.counts.values())

    def merge(self, other: "GCounter") -> None:
        # 逐分量取 max：交換、結合、冪等 → 重複收到同一份狀態也不會重複計算
        for node, c in other.counts.items():
            self.counts[node] = max(self.counts.get(node, 0), c)

tokyo, sg = GCounter("tokyo"), GCounter("sg")
tokyo.incr(100); sg.incr(40)
tokyo.merge(sg); sg.merge(tokyo); tokyo.merge(sg)   # 重複合併無害
assert tokyo.value() == sg.value() == 140

時間與順序：物理時鐘、Lamport、Vector Clock、HLC、TrueTime 深入

「事件 A 比 B 先發生嗎？」在單機上看時間戳即可，在分散式系統中卻是最難的問題之一。

物理時鐘與 NTP

Time-of-day clock（wall clock）

例如 Python 的 time.time()、Linux 的 CLOCK_REALTIME。會被 NTP 調整，可能往回跳；閏秒也可能造成異常。不適合拿來量測時間長度。

Monotonic clock

例如 time.monotonic()、CLOCK_MONOTONIC、Go 的 time.Since（內部用 monotonic）。保證不倒退，適合量測 timeout 與耗時；但不同機器之間的值沒有可比性。

NTP

透過與時間伺服器交換訊息、估算往返延遲來校正。精度受網路延遲影響，公網上通常是數毫秒到數十毫秒；同機房搭配好的時間源可以到次毫秒。NTP 可以 slew（慢慢調整頻率）或 step（直接跳），後者就是時間倒退的來源。AWS 提供 Amazon Time Sync Service，GCP 用 leap smearing 處理閏秒。

Lamport Timestamp

Leslie Lamport 1978 年的經典論文定義了 happens-before（→）關係：同一 process 內先後的事件、送出訊息 → 收到該訊息、以及遞移關係。Lamport clock 規則：

1. 每個節點維護計數器 c，每發生一個本地事件 c += 1。
2. 送訊息時附上 c。
3. 收到訊息時 c = max(c, msg.c) + 1。
4. 用 (c, node_id) 排序，得到一個與因果一致的全序。

性質：若 A → B，則 L(A) < L(B)。但反過來不成立：L(A) < L(B) 不代表 A → B，可能只是並行。所以 Lamport clock 無法偵測並行（無法判斷衝突），只能給出一個一致的排序。

Vector Clock

每個節點維護長度為 N 的向量。本地事件時遞增自己的分量；送訊息附上整個向量；收到時逐分量取 max 後再遞增自己的分量。比較：

• V(A) ≤ V(B)（每個分量都 ≤，且至少一個 <）⇔ A → B
• 兩者互不 ≤ ⇔ A 與 B 並行（concurrent）

這是充分必要條件，所以 vector clock 可以精確偵測並行寫入。代價：大小 O(N)，client 很多時會膨脹（Riak 用 dotted version vector 改善）。

from enum import Enum

class Order(Enum):
    BEFORE = "before"; AFTER = "after"; EQUAL = "equal"; CONCURRENT = "concurrent"

class VectorClock:
    def __init__(self, clock=None):
        self.clock: dict[str, int] = dict(clock or {})

    def tick(self, node: str) -> "VectorClock":
        self.clock[node] = self.clock.get(node, 0) + 1
        return self

    def merge(self, other: "VectorClock", node: str) -> "VectorClock":
        for k, v in other.clock.items():
            self.clock[k] = max(self.clock.get(k, 0), v)
        return self.tick(node)               # 收到訊息也算一個事件

    def compare(self, other: "VectorClock") -> Order:
        keys = self.clock.keys() | other.clock.keys()
        le = all(self.clock.get(k, 0) <= other.clock.get(k, 0) for k in keys)
        ge = all(self.clock.get(k, 0) >= other.clock.get(k, 0) for k in keys)
        if le and ge: return Order.EQUAL
        if le: return Order.BEFORE
        if ge: return Order.AFTER
        return Order.CONCURRENT

a = VectorClock().tick("A")           # {A:1}
b = VectorClock(a.clock).tick("B")    # {A:1, B:1}，B 看過 A 的寫入
c = VectorClock(a.clock).tick("C")    # {A:1, C:1}，C 也看過 A，但不知道 B
print(a.compare(b))   # Order.BEFORE
print(b.compare(c))   # Order.CONCURRENT → 衝突，需保留兩者或合併

Hybrid Logical Clock（HLC）

Lamport clock 跟真實時間無關，不方便做「查詢 5 分鐘前的快照」；物理時鐘又不保證因果。HLC（Kulkarni 等人 2014）結合兩者：時間戳 = (l, c)，l 是「目前看過的最大物理時間」，c 是同一個 l 之下的邏輯計數器。

• 保證因果：A → B 則 HLC(A) < HLC(B)。
• 與物理時間很接近：l 與本地物理時間的差距受時鐘偏差上界所限制。
• 可以放進 64 bits（例如 48 bits 物理時間 + 16 bits 計數器），可直接取代原本的時間戳欄位。

CockroachDB、YugabyteDB、MongoDB（cluster time）都用 HLC 做 MVCC 版本。

import time

class HLC:
    def __init__(self):
        self.l = 0   # 看過的最大物理時間（ms）
        self.c = 0   # 邏輯計數器

    def _pt(self) -> int:
        return int(time.time() * 1000)

    def now(self) -> tuple[int, int]:          # 本地事件 / 送出訊息
        pt = self._pt()
        if pt > self.l:
            self.l, self.c = pt, 0
        else:
            self.c += 1                         # 物理時鐘沒前進（或倒退）就靠計數器
        return (self.l, self.c)

    def update(self, ml: int, mc: int) -> tuple[int, int]:   # 收到訊息
        pt = self._pt()
        new_l = max(self.l, ml, pt)
        if new_l == self.l == ml:
            self.c = max(self.c, mc) + 1
        elif new_l == self.l:
            self.c += 1
        elif new_l == ml:
            self.c = mc + 1
        else:
            self.c = 0
        self.l = new_l
        return (self.l, self.c)

Google TrueTime（Spanner）

Spanner 用 GPS 接收器與原子鐘提供 TrueTime API：TT.now() 回傳一個區間 [earliest, latest]，保證真實時間落在其中，不確定度 ε 通常只有數毫秒。

Commit wait：交易提交時取時間戳 s = TT.now().latest，然後等待直到 TT.now().earliest > s 才釋放鎖並回應 client（約等 2ε）。這保證：任何在此之後開始的交易一定拿到更大的時間戳，於是時間戳順序 = 真實時間順序，達成全球規模的 external consistency（等同 linearizability 在交易上的版本）。核心洞見：把時鐘的不確定性顯式化，用「等待」換正確性。CockroachDB 沒有原子鐘，改用 HLC + 最大時鐘偏差設定 + 讀取時遇到不確定區間就重啟交易。

分區（Partitioning / Sharding）與 Consistent Hashing 進階 高頻

複製解決「可用性與讀取擴展」，分區解決「資料量與寫入量超過單機」。每筆資料屬於一個 partition（MongoDB 叫 chunk、Cassandra 叫 vnode/token range、Kafka 叫 partition），每個 partition 再各自複製。目標：資料與負載平均分散，避免熱點。

Range 分區 vs Hash 分區

折衷：複合鍵。Cassandra 的 primary key = (partition key, clustering columns)：partition key 做 hash 決定位置，同一 partition 內依 clustering column 排序，於是「某使用者在時間範圍內的事件」可以高效查詢。

為什麼不用 hash(key) % N

最直覺的做法是 node = hash(key) % N。問題在於 N 改變時（擴容 10 → 11 台），幾乎所有 key 都要搬家：一個 key 留在原位的機率約只有 1/11。對快取叢集而言，這等於瞬間全部 cache miss，DB 直接被打爆。

Consistent Hashing 原理

Karger 等人 1997 年提出。把 hash 空間想像成一個環（例如 0 到 2³²−1），節點與 key 都 hash 到環上；每個 key 順時針找到的第一個節點就是它的歸屬。新增一個節點時，只有「新節點逆時針到前一個節點之間」的 key 會搬到新節點，平均只搬 K/N 個 key（K 是 key 總數）。

Virtual nodes（虛擬節點）：只有少數實體節點時，它們在環上的位置可能很不平均，某台負責的範圍可能是另一台的好幾倍。解法是每台實體節點在環上放 100–200 個虛擬節點（hash("A#0")、hash("A#1")…），讓負載更平均；也可以依機器規格給不同數量的 vnode（加權）。另一個好處：某台節點下線時，它的負載會分散到很多台，而不是全部壓到順時針的下一台。

import bisect
import hashlib
from collections import Counter

def _hash(s: str) -> int:
    # 不要用 Python 內建 hash()：每個 process 的 str hash 有隨機 salt（PYTHONHASHSEED）
    return int.from_bytes(hashlib.md5(s.encode()).digest()[:8], "big")

class ConsistentHashRing:
    def __init__(self, vnodes: int = 160):
        self.vnodes = vnodes
        self._keys: list[int] = []          # 已排序的 vnode hash
        self._owner: dict[int, str] = {}    # vnode hash -> 實體節點

    def add_node(self, node: str, weight: int = 1) -> None:
        for i in range(self.vnodes * weight):
            hv = _hash(f"{node}#{i}")
            if hv in self._owner:           # 極罕見的碰撞，跳過
                continue
            self._owner[hv] = node
            bisect.insort(self._keys, hv)

    def remove_node(self, node: str) -> None:
        self._keys = [k for k in self._keys if self._owner[k] != node]
        self._owner = {k: v for k, v in self._owner.items() if v != node}

    def get_node(self, key: str) -> str:
        if not self._keys:
            raise RuntimeError("empty ring")
        idx = bisect.bisect_right(self._keys, _hash(key)) % len(self._keys)  # 環狀繞回
        return self._owner[self._keys[idx]]

    def get_nodes(self, key: str, n: int) -> list[str]:
        """取順時針 n 個不同的實體節點，作為複製的 preference list（Dynamo 風格）。"""
        out, idx = [], bisect.bisect_right(self._keys, _hash(key))
        for step in range(len(self._keys)):
            node = self._owner[self._keys[(idx + step) % len(self._keys)]]
            if node not in out:
                out.append(node)
                if len(out) == n:
                    break
        return out

ring = ConsistentHashRing()
for n in ["cache-1", "cache-2", "cache-3", "cache-4"]:
    ring.add_node(n)
keys = [f"user:{i}" for i in range(100_000)]
before = {k: ring.get_node(k) for k in keys}
print(Counter(before.values()))               # 四台大致各 25%
ring.add_node("cache-5")
moved = sum(before[k] != ring.get_node(k) for k in keys)
print(f"moved {moved / len(keys):.1%}")       # 約 20%（= 1/5），而非 mod N 的約 80%

Rendezvous Hashing（HRW, Highest Random Weight）

另一種一致性分配方法：對每個 key，計算它與每個節點的分數 score = hash(key, node)，選分數最高的節點（要 k 個副本就取前 k 名）。

• 優點：不需要維護環與 vnode，實作極簡；天然均勻；節點移除時只有屬於它的 key 移動。
• 缺點：每次查詢 O(N)（N 為節點數）。節點數在數十到數百時完全可接受；非常多時可用 skeleton 分層版本。

def rendezvous(key: str, nodes: list[str], k: int = 1) -> list[str]:
    return sorted(nodes, key=lambda n: _hash(f"{n}|{key}"), reverse=True)[:k]

另外還有 Google 的 Jump Consistent Hash（O(log N)、零記憶體，但只能在尾端增減 bucket）與 Maglev hashing（Google 的 L4 LB 使用，查表 O(1)，分佈極均勻）。

Rebalancing 策略

熱點（Hot Spot / Celebrity Problem）

Hash 分區無法解決「單一 key 本身很熱」：例如某個超大廣告主的 campaign_id、某個名人的 user_id。常見手法：

• Key salting / 分裂：寫入時在熱 key 後加隨機後綴 campaign:42#0..#9，分散到 10 個 partition；讀取時把 10 個合併。代價：讀取放大，需要額外記錄哪些 key 被分裂。
• 本地預聚合：在送出前先在 bidder 本地累加 1 秒，再送一筆彙總，寫入量降 1000 倍。
• 讀取熱點：加一層本地快取（in-process LRU）或 read replica。
• 時間序列 key：避免以純時間戳當 range key，改用 (hash(device_id) % 16, ts) 之類的前綴。

共識（Consensus）：FLP、Paxos、Raft 深入 高頻

共識問題：讓多個節點對「某個值」（或一連串值，即一份 log）達成一致決定，且決定後不可改變。許多問題本質上都等價於共識：leader election、分散式鎖、原子提交、全序廣播（total order broadcast）、唯一性約束。

共識演算法的性質：Agreement（沒有兩個節點決定不同的值）、Integrity（每個節點只決定一次）、Validity（決定的值是某節點提議的）、Termination（沒當機的節點最終都會決定）。前三個是 safety，最後一個是 liveness。

FLP 不可能定理

Fischer、Lynch、Paterson（1985）證明：在完全非同步的系統中，只要可能有一個節點 crash，就不存在一個確定性演算法能保證共識一定會終止。直覺：你永遠無法區分「慢」與「死」，所以總有一種訊息延遲的排程能讓演算法永遠卡在猶豫中。

實務的繞道方法：（1）假設部分同步，用 timeout 做 failure detection；（2）引入隨機性（Raft 的隨機 election timeout）。結果是：Raft/Paxos 永遠保證 safety，但只在網路夠穩定時保證 liveness——這不違反 FLP。

Paxos 概念

Lamport 提出的經典演算法。角色：Proposer、Acceptor、Learner。Basic Paxos 決定單一值，分兩階段：

1. Prepare / Promise：Proposer 選一個提案編號 n，送 Prepare(n) 給多數 Acceptor。Acceptor 若沒看過更大的編號，就承諾不再接受小於 n 的提案，並回報它已接受過的最大編號提案（若有）。
2. Accept / Accepted：Proposer 收到多數 Promise 後，若有人回報已接受的值，必須沿用其中編號最大的那個值（這是 safety 的關鍵），否則用自己的值，送 Accept(n, v)。Acceptor 若沒承諾更大編號就接受。多數接受 → 值被選定。

Multi-Paxos 用一個穩定的 leader 跳過第一階段，連續決定 log 中每個位置的值。Paxos 以難懂著稱、論文留下許多實作細節未定義，這是 Raft 誕生的動機。Google Chubby、Spanner 使用 Paxos 變體；ZooKeeper 用的 ZAB 與 Paxos 相近但不同。

Raft 詳解

Raft（Ongaro & Ousterhout，2014）的設計目標是「可理解性」，把共識拆成三個子問題：leader election、log replication、safety。etcd、Consul、TiKV、CockroachDB、Kafka KRaft 都使用 Raft。

角色與 term

每個節點處於三種狀態之一：Follower、Candidate、Leader。時間被切成 term（任期），以單調遞增的整數表示，每個 term 最多一個 leader。term 扮演邏輯時鐘：任何 RPC 中若發現對方 term 比自己大，立刻更新 term 並退回 follower；收到比自己小的 term 的請求則拒絕。這就是 Raft 內建的 fencing 機制。

Leader Election

1. Follower 在 election timeout（論文建議隨機 150–300ms）內沒收到 leader 的 heartbeat（空的 AppendEntries），就轉為 Candidate。
2. Candidate 將 term + 1、投票給自己，平行送 RequestVote(term, candidateId, lastLogIndex, lastLogTerm) 給其他節點。
3. 每個節點在每個 term 只投一票（先到先得，且要持久化 votedFor），並且只投給 log 至少和自己一樣新的 candidate（先比最後一筆的 term，term 相同再比 index）。這條限制保證新 leader 一定擁有所有已 commit 的 entry。
4. 拿到多數票即成為 leader，立刻送 heartbeat 宣示主權。
5. 若分票（split vote）導致無人過半，各自等待隨機 timeout 後重選；隨機化讓分票很快解除。

Log Replication

• 每筆 entry 有 (index, term, command)。
• 一致性檢查：AppendEntries 帶 prevLogIndex 與 prevLogTerm；follower 在該位置沒有相符的 entry 就拒絕，leader 把 nextIndex 往回退再試，直到找到共同點，然後覆蓋 follower 之後衝突的 entry。這確保 Log Matching Property：兩份 log 若在某 index 的 term 相同，則該 index 之前全部相同。
• entry 被複製到多數節點後，leader 才將其標為 committed、套用到狀態機並回應 client。

Safety 的關鍵細節

Election restriction

只有 log 夠新的節點能當選 → Leader Completeness：已 commit 的 entry 一定出現在所有未來 leader 的 log 中。

只能用當前 term 的 entry 推進 commit

Leader 不能因為「舊 term 的 entry 已在多數節點上」就宣告它 committed（論文 Figure 8 的反例：這樣的 entry 仍可能被之後的 leader 覆蓋）。必須等當前 term 的某個 entry 被多數複製，才連帶 commit 之前的 entry。實作上新 leader 上任時會先寫一筆 no-op entry。

持久化

currentTerm、votedFor、log 必須在回應 RPC 前寫入穩定儲存（fsync），否則重啟後可能在同一 term 投兩次票。

線性一致讀

Leader 直接讀本地狀態不安全（它可能已被罷免而不自知）。做法：ReadIndex（記下 commitIndex，送一輪 heartbeat 確認自己仍是多數認可的 leader，再等狀態機套用到該 index 後讀取），或 lease read（依賴時鐘有界漂移，較快但有風險）。etcd 預設提供線性一致讀，可用 serializable 讀換取速度。

Membership Change 與 Log Compaction

直接把設定從舊集合切到新集合很危險：轉換期間可能同時存在「舊設定的多數」與「新設定的多數」兩個 leader。Raft 提供兩種方法：

• Joint consensus：先進入 C_old,new 過渡設定，任何決定都要同時取得舊集合與新集合各自的多數；確立後再切到 C_new。
• 單節點變更：一次只增或減一個節點，此時新舊多數必定重疊，可以直接切換。etcd 就是一次一個成員，並有 learner（非投票成員）機制讓新節點先追上 log。

Log 不能無限增長，各節點定期把狀態機做 snapshot，丟掉之前的 log；落後太多的 follower 由 leader 用 InstallSnapshot RPC 直接傳快照。

etcd 與 ZooKeeper 的用途

典型用途：服務發現、設定中心、leader election、分散式鎖、叢集成員管理。共同原則：寫入量要小（etcd 預設單一請求上限 1.5MB、建議總資料量在數 GB 以內）。

Leader Election、分散式鎖與 Fencing Token 深入

許多系統需要「同一時間只有一個實例做某件事」：只有一個 scheduler 觸發排程、只有一個 worker 處理某個帳戶的扣款、只有一個 consumer 寫入某個檔案。這需要 leader election 或分散式鎖——兩者本質相同：都是「取得一個有時效的獨占權」。

Lease（租約）

分散式鎖幾乎都必須有過期時間，否則持鎖者當機，鎖就永遠不會被釋放。有過期時間的鎖就是 lease：「你在接下來 10 秒內擁有此資源」，持有者需在到期前續約。

為什麼分散式鎖很難：GC Pause 問題

Martin Kleppmann 的經典反例：

問題的根源：持鎖者無法可靠地知道自己的 lease 是否還有效。檢查「lease 還剩幾秒」和「執行寫入」之間可能發生任意長的停頓（GC、page fault、VM 遷移、網路延遲讓寫入請求在路上多走了 10 秒）。

Fencing Token

解法：鎖服務每次授予鎖時，同時發一個單調遞增的 token（例如 etcd 的 revision、ZooKeeper 的 zxid/czxid、Raft 的 term）。Client 每次寫入儲存時帶上 token，儲存端記住看過的最大 token，拒絕更小的。

• A 拿到 token 33，停頓；B 拿到 token 34 並寫入，儲存端記錄 max=34。
• A 醒來帶 token 33 寫入 → 被拒絕。

關鍵：安全性由資源端保證，而不是持鎖者自律。如果儲存端無法檢查 token（例如第三方 API），可以用條件寫入代替，例如 SQL 的 UPDATE ... WHERE version = ?（樂觀鎖）、S3 的條件寫入、DynamoDB 的 ConditionExpression。

-- 資源端實作 fencing：只接受比上次更大的 token
UPDATE job_state
SET    payload = :payload, fence_token = :token
WHERE  job_id = :job_id
  AND  fence_token < :token;
-- 影響列數為 0 → 代表自己的鎖已過期被別人取代，應中止

Redis 分散式鎖與 Redlock 爭議

單一 Redis 實例的鎖（效率用途）是常見做法：

import uuid
import redis

r = redis.Redis()

RELEASE_LUA = """
if redis.call('get', KEYS[1]) == ARGV[1] then
    return redis.call('del', KEYS[1])
else
    return 0
end
"""
release_script = r.register_script(RELEASE_LUA)

def acquire(name: str, ttl_ms: int = 10_000) -> str | None:
    token = uuid.uuid4().hex                       # 唯一值，用來確認是自己的鎖
    ok = r.set(f"lock:{name}", token, nx=True, px=ttl_ms)   # 原子地「不存在才設定 + 過期」
    return token if ok else None

def release(name: str, token: str) -> bool:
    # 必須用 Lua 原子地「比對再刪除」：否則 GET 後鎖剛好過期被別人拿走，DEL 會刪掉別人的鎖
    return release_script(keys=[f"lock:{name}"], args=[token]) == 1

token = acquire("daily-report")
if token:
    try:
        ...  # 做事；耗時接近 TTL 時需要續約（watchdog）或改用 fencing token
    finally:
        release("daily-report", token)

用 etcd 做 Leader Election

// 使用 go.etcd.io/etcd/client/v3/concurrency
cli, _ := clientv3.New(clientv3.Config{Endpoints: []string{"etcd:2379"}})
sess, _ := concurrency.NewSession(cli, concurrency.WithTTL(10)) // 綁定 lease，process 死掉 10 秒後自動釋放
defer sess.Close()

e := concurrency.NewElection(sess, "/scheduler/leader")
if err := e.Campaign(ctx, hostname); err != nil { // 阻塞直到當選
    log.Fatal(err)
}
// 當選後：e.Rev() 可當 fencing token（建立 key 時的 revision，單調遞增）
fence := e.Rev()
go func() {
    <-sess.Done()       // lease 失效（例如網路斷太久）→ 立刻停止 leader 工作
    os.Exit(1)
}()
runSchedulerLoop(ctx, fence)

分散式交易：2PC、3PC、Saga、TCC、Outbox 深入 高頻

單一資料庫的 ACID 交易很成熟。但當一個業務操作跨越多個資料庫或多個微服務（例如「建立訂單 + 扣庫存 + 扣款」），就需要分散式交易。核心取捨：強一致的原子提交（2PC）會阻塞、降低可用性；最終一致的補償式交易（Saga）可用性高，但要處理中間狀態與補償。

Two-Phase Commit（2PC）

1. Prepare：coordinator 問所有 participant「你能提交嗎？」participant 把交易資料持久化、保留鎖，回 YES 就代表「無論發生什麼，我承諾之後一定能提交」，從此失去單方面中止的權利。
2. Commit / Abort：全部 YES → coordinator 先把 COMMIT 決定寫入自己的 log（不可反悔的點），再通知所有人提交；任一 NO 或逾時 → 通知全部 abort。Participant 必須重試直到收到決定。

阻塞問題：participant 投完 YES 後，若 coordinator 當機，participant 處於 in-doubt（不確定）狀態：不能自行 commit（可能別人投了 NO），也不能 abort（coordinator 可能已決定 commit 並通知了別人）。只能持續持有鎖等待 coordinator 恢復——這期間相關的資料列全部被鎖住，其他交易被卡住。所以 2PC 被稱為「阻塞式原子提交協定」。

其他問題：同步往返多、延遲高；coordinator 是單點；所有參與者都要支援 XA 之類的協定。實例：MySQL XA、PostgreSQL PREPARE TRANSACTION、Java JTA。在資料庫內部的分散式交易（Spanner、CockroachDB）會把 coordinator 狀態也用 Paxos/Raft 複製，解決 coordinator 單點的問題，因此可用。

Three-Phase Commit（3PC）

在 prepare 與 commit 之間加一個 pre-commit 階段，並引入 timeout：參與者在 pre-commit 後若等不到 coordinator，可以安全地自行提交。這讓它在「同步網路 + 有界延遲」假設下是非阻塞的。但在真實的非同步網路中，網路分區會讓兩邊做出不同決定，破壞一致性，因此實務上幾乎不用。面試只需知道：「3PC 試圖解決 2PC 的阻塞，但假設有界延遲，實際上不可靠。」

Saga

1987 年提出的長交易模式：把大交易拆成一串本地交易 T1, T2, …, Tn，每一步各自提交；若第 k 步失敗，就反向執行補償交易 C(k−1), …, C1 來語意上撤銷。

• 沒有全域鎖，可用性與吞吐高。
• 代價：沒有隔離性（isolation），其他交易可能看到中間狀態（已扣庫存但未付款）。需要語意鎖（狀態欄位 PENDING）、交換律設計等對策。
• 補償不一定能完全還原（已寄出的 email 無法收回，只能再寄一封更正信）。
• 每個步驟與補償都必須冪等，因為會被重試。

# 極簡 Saga orchestrator：每步定義 action 與 compensation，失敗時反向補償
from dataclasses import dataclass
from typing import Callable

@dataclass
class Step:
    name: str
    action: Callable[[dict], None]
    compensate: Callable[[dict], None]

def run_saga(steps: list[Step], ctx: dict, log) -> bool:
    done: list[Step] = []
    for step in steps:
        try:
            log.record(ctx["saga_id"], step.name, "START")   # 持久化進度，crash 後可從此恢復
            step.action(ctx)                                  # action 本身必須冪等
            log.record(ctx["saga_id"], step.name, "DONE")
            done.append(step)
        except Exception as e:
            log.record(ctx["saga_id"], step.name, f"FAILED: {e}")
            for s in reversed(done):
                retry_forever(lambda: s.compensate(ctx))      # 補償必須最終成功（冪等 + 重試）
                log.record(ctx["saga_id"], s.name, "COMPENSATED")
            return False
    return True

# steps = [Step("reserve_budget", reserve, release), Step("create_campaign", create, archive),
#          Step("notify_ad_server", push_config, revoke_config)]

TCC（Try-Confirm-Cancel）

可視為「應用層的 2PC」。每個服務提供三個介面：

• Try：檢查並預留資源（凍結 100 元，而不是直接扣）。
• Confirm：真正使用預留的資源（把凍結的 100 元扣掉）。
• Cancel：釋放預留。

比 Saga 隔離性好（預留的資源別人用不到），但侵入性高（每個服務都要實作三套邏輯）。要處理的經典問題：空回滾（Try 沒執行到就收到 Cancel）、懸掛（Cancel 先到、Try 後到，Try 不應再預留）、冪等（Confirm/Cancel 被重試）。通常用一張交易紀錄表記錄每個全域交易 id 在本服務的狀態來解決。

Outbox Pattern：解決 Dual Write

常見錯誤：「先寫 DB，再發訊息到 Kafka」。若寫 DB 成功、發訊息失敗（或 process 在兩者之間當機），下游永遠收不到事件；反過來先發訊息再寫 DB 也有對稱的問題。這叫 dual write problem——兩個系統之間沒有共同的交易。

Outbox：在同一個本地 DB 交易中，同時寫入業務表與 outbox 表；再由獨立的 relay（輪詢 outbox 表，或用 CDC 如 Debezium 讀 binlog）把 outbox 事件送到 MQ，送成功後標記已發送。保證「業務變更與事件」要嘛都發生、要嘛都沒發生；relay 可能重送，所以下游要冪等（at-least-once）。詳細實作見 第 11 章。

BEGIN;
UPDATE campaigns SET status = 'ACTIVE' WHERE id = 42;
INSERT INTO outbox (id, aggregate_id, event_type, payload, created_at)
VALUES ('0192f6c4-...', 42, 'CampaignActivated', '{"campaign_id":42}', NOW());
COMMIT;
-- relay: SELECT ... FROM outbox WHERE sent_at IS NULL ORDER BY created_at LIMIT 100 FOR UPDATE SKIP LOCKED;

分散式 ID 生成 進階 高頻

單機 DB 的 AUTO_INCREMENT 在分庫分表、多區域寫入時不再可用。分散式 ID 的需求通常是：全域唯一、高可用、高效能（本地產生）、大致按時間遞增（對 B+tree 索引友善），有時還要求不可預測（不洩漏業務量）。

UUID v4 與 v7

• UUID v4：122 bits 隨機。無需協調，碰撞機率可忽略。缺點：128 bits 較大；完全隨機，作為 InnoDB 主鍵時插入位置隨機，造成 page split 與 buffer pool 命中率下降，寫入效能明顯變差。
• UUID v7（RFC 9562，2024）：前 48 bits 是 Unix 毫秒時間戳，其後是版本位元與隨機位元（可選用部分作為單調計數器）。時間有序 + 無需協調，是新系統取代 v4 當主鍵的推薦選擇。PostgreSQL 18 起內建 uuidv7()，Python 3.14 起標準庫 uuid 也提供 uuid7()。

Snowflake

Twitter 2010 年提出的 64-bit ID（剛好放進 BIGINT）：

單機理論上限約每秒 409.6 萬個。機器 ID 的分配通常靠 ZooKeeper/etcd 註冊、K8s StatefulSet 序號，或啟動時從 DB 取得。

時鐘回撥（clock moving backwards）是 Snowflake 最大的坑：NTP 把時間往回調，就可能產生與之前重複的 ID。對策：

1. 記錄上次產生 ID 的時間戳 last_ts；若 now < last_ts：回撥很小（例如 ≤ 5ms）就等待追上；回撥大則拒絕服務並告警。
2. 不跟著時鐘走：用 max(now, last_ts)，序號用完就「借用」下一毫秒（百度 UidGenerator 的做法），讓 ID 時間戳與真實時間略微脫鉤。
3. NTP 設定成只 slew 不 step；或預留 1–2 bits 作為「回撥次數」，回撥時遞增以區隔。

import threading
import time

class Snowflake:
    EPOCH = 1_704_067_200_000          # 2024-01-01 UTC，自訂 epoch 延長可用年限
    WORKER_BITS, SEQ_BITS = 10, 12
    MAX_WORKER = (1 << WORKER_BITS) - 1
    MAX_SEQ = (1 << SEQ_BITS) - 1
    MAX_BACKWARD_MS = 5

    def __init__(self, worker_id: int):
        if not 0 <= worker_id <= self.MAX_WORKER:
            raise ValueError("worker_id out of range")
        self.worker_id = worker_id
        self.last_ts = -1
        self.seq = 0
        self.lock = threading.Lock()

    @staticmethod
    def _now() -> int:
        return time.time_ns() // 1_000_000

    def next_id(self) -> int:
        with self.lock:
            ts = self._now()
            if ts < self.last_ts:                         # 時鐘回撥
                back = self.last_ts - ts
                if back > self.MAX_BACKWARD_MS:
                    raise RuntimeError(f"clock moved backwards {back}ms")
                time.sleep(back / 1000)
                ts = self._now()
                if ts < self.last_ts:
                    raise RuntimeError("clock still behind")
            if ts == self.last_ts:
                self.seq = (self.seq + 1) & self.MAX_SEQ
                if self.seq == 0:                         # 本毫秒序號用完 → 等下一毫秒
                    while ts <= self.last_ts:
                        ts = self._now()
            else:
                self.seq = 0
            self.last_ts = ts
            return ((ts - self.EPOCH) << (self.WORKER_BITS + self.SEQ_BITS)) \
                | (self.worker_id << self.SEQ_BITS) | self.seq

    @classmethod
    def parse(cls, id_: int) -> dict:
        return {
            "ts_ms": (id_ >> (cls.WORKER_BITS + cls.SEQ_BITS)) + cls.EPOCH,
            "worker": (id_ >> cls.SEQ_BITS) & cls.MAX_WORKER,
            "seq": id_ & cls.MAX_SEQ,
        }

DB Segment 模式（美團 Leaf-segment）

用 DB 發號，但不是每次取一個，而是一次取一段（segment）：

CREATE TABLE id_alloc (
  biz_tag  VARCHAR(64) PRIMARY KEY,
  max_id   BIGINT NOT NULL,
  step     INT    NOT NULL
);
-- 服務取號段：原子地往前推 step，拿到 (max_id - step, max_id] 這段在記憶體中發放
UPDATE id_alloc SET max_id = max_id + step WHERE biz_tag = 'order';
SELECT max_id, step FROM id_alloc WHERE biz_tag = 'order';

每次 DB 存取可發出 step 個 ID，DB 壓力降 step 倍。雙 buffer：目前號段用到一定比例（如 10%）時，非同步預取下一段，避免號段用完時的等待尖峰。優點：ID 是緊湊的遞增整數、不依賴時鐘；缺點：依賴 DB 可用性（號段可撐一段時間）、多台服務取的號段交錯，所以只是「趨勢遞增」而非嚴格遞增；ID 連續會洩漏業務量。Leaf 同時提供 snowflake 模式（以 ZooKeeper 分配 worker id 並檢查時鐘）。

ULID

128 bits = 48 bits 毫秒時間戳 + 80 bits 隨機，以 Crockford Base32 編碼成 26 字元（如 01ARZ3NDEKTSV4RRFFQ69G5FAV）。字典序 = 時間序，URL 安全、可讀性比 UUID 好；同毫秒內可用 monotonic 模式（隨機部分 +1）保證遞增。概念上和 UUID v7 非常接近，v7 標準化後新專案可直接用 v7（能存進原生 UUID 欄位）。

故障處理、韌性模式與冪等 進階 高頻

分散式系統中故障是常態。韌性（resilience）模式的共同目標：讓局部故障停留在局部，不要擴散成全面癱瘓（cascading failure）。

Timeout

• 一定要設：很多 HTTP client 預設沒有 timeout（Python requests 預設無限等待）。沒有 timeout 的呼叫會讓 thread/connection 被耗盡。
• 依據下游的 p99/p999 延遲設定，而不是平均值；分成 connect timeout 與 read timeout。
• Deadline propagation：上游總預算 100ms，已花 60ms，呼叫下游時只給剩下的 40ms（gRPC 的 deadline 會自動傳遞）。RTB 場景這點至關重要。

Retry、Exponential Backoff 與 Jitter

只重試暫時性錯誤（timeout、503、連線重設），不重試 4xx（除了 429）；只重試冪等操作或帶 idempotency key 的操作。

立刻重試會讓已經過載的下游雪上加霜（retry storm：每層重試 3 次，5 層呼叫鏈最壞放大 3⁵=243 倍）。所以：

• Exponential backoff：等待 base × 2^attempt，設上限 cap。
• Jitter：加入隨機，避免大量 client 同時重試形成同步尖峰（thundering herd）。AWS Architecture Blog 的分析顯示 full jitter（在 0 到 backoff 之間均勻隨機）在總工作量上表現很好。
• Retry budget：重試請求不超過正常請求的某個比例（例如 10%），超過就不重試（gRPC、Envoy、Finagle 都支援）。
• 只在呼叫鏈的一層重試，通常是最靠近使用者的那層或最底層，不要每層都重試。

import random
import time

class RetryableError(Exception): ...

def retry_with_backoff(fn, *, max_attempts=5, base=0.1, cap=5.0, deadline=None):
    """Full jitter: sleep = random(0, min(cap, base * 2**attempt))"""
    start = time.monotonic()                     # 量時間用 monotonic clock
    for attempt in range(max_attempts):
        try:
            return fn()
        except RetryableError:
            if attempt == max_attempts - 1:
                raise
            sleep = random.uniform(0, min(cap, base * (2 ** attempt)))
            if deadline is not None and time.monotonic() - start + sleep > deadline:
                raise                            # 超過整體預算就放棄，不要無止盡重試
            time.sleep(sleep)

Circuit Breaker（斷路器）

當下游持續失敗時，繼續呼叫只是浪費資源並拖慢自己。斷路器在失敗率超過閾值時「跳脫」，直接快速失敗（或回傳 fallback），給下游喘息時間。

import threading
import time
from collections import deque

class CircuitOpenError(Exception): ...

class CircuitBreaker:
    def __init__(self, failure_ratio=0.5, min_calls=20, window_s=10.0, cooldown_s=30.0, half_open_max=3):
        self.failure_ratio, self.min_calls = failure_ratio, min_calls
        self.window_s, self.cooldown_s, self.half_open_max = window_s, cooldown_s, half_open_max
        self.state = "CLOSED"
        self.events: deque[tuple[float, bool]] = deque()   # (時間, 是否成功) 滑動視窗
        self.opened_at = 0.0
        self.half_open_inflight = 0
        self.lock = threading.Lock()

    def _trim(self, now):
        while self.events and now - self.events[0][0] > self.window_s:
            self.events.popleft()

    def call(self, fn, fallback=None):
        with self.lock:
            now = time.monotonic()
            if self.state == "OPEN":
                if now - self.opened_at >= self.cooldown_s:
                    self.state, self.half_open_inflight = "HALF_OPEN", 0
                else:
                    return self._reject(fallback)
            if self.state == "HALF_OPEN":
                if self.half_open_inflight >= self.half_open_max:
                    return self._reject(fallback)
                self.half_open_inflight += 1
        try:
            result = fn()
        except Exception:
            self._record(False)
            raise
        self._record(True)
        return result

    def _record(self, ok: bool):
        with self.lock:
            now = time.monotonic()
            if self.state == "HALF_OPEN":
                self.half_open_inflight -= 1
                if ok:
                    self.state = "CLOSED"; self.events.clear()
                else:
                    self.state, self.opened_at = "OPEN", now
                return
            self.events.append((now, ok)); self._trim(now)
            fails = sum(1 for _, s in self.events if not s)
            if len(self.events) >= self.min_calls and fails / len(self.events) >= self.failure_ratio:
                self.state, self.opened_at = "OPEN", now

    def _reject(self, fallback):
        if fallback is not None:
            return fallback()
        raise CircuitOpenError()

Bulkhead（艙壁隔離）

名稱來自船艙的隔間：一個艙進水不會讓整艘船沉。做法是為不同下游或不同類型的請求分配獨立的資源池（thread pool、connection pool、semaphore、甚至獨立的服務實例/叢集）。例如：呼叫「推薦模型服務」最多用 50 個並行，呼叫「報表服務」最多用 10 個；報表服務卡住時，只會耗盡它自己的 10 個名額，不會拖垮出價主流程。K8s 中用獨立 deployment、resource limit 也是 bulkhead 的實現。

Rate Limiting

import time

class TokenBucket:
    def __init__(self, rate: float, capacity: float):
        self.rate, self.capacity = rate, capacity   # 每秒補 rate 個，最多存 capacity 個
        self.tokens = capacity
        self.ts = time.monotonic()

    def allow(self, cost: float = 1.0) -> bool:
        now = time.monotonic()
        self.tokens = min(self.capacity, self.tokens + (now - self.ts) * self.rate)  # 惰性補充
        self.ts = now
        if self.tokens >= cost:
            self.tokens -= cost
            return True
        return False

分散式限流：多台 API server 共用額度時，常把 token bucket 放在 Redis 並用 Lua 腳本原子化；或每台分配「總額度 / 台數」的本地額度（不精確但零延遲）。

Load Shedding、Backpressure 與 Graceful Degradation

Load shedding（卸載）

伺服器自己判斷過載時（佇列長度、CPU、in-flight 請求數、請求在佇列中已等待過久），主動拒絕部分請求（回 503/429），保住其餘請求的延遲。原則：越早拒絕越便宜；優先丟棄低優先級流量；請求在佇列中等太久（已超過 client deadline）就直接丟掉，因為 client 早已放棄了。

Backpressure（背壓）

下游處理不過來時，把「慢一點」的訊號傳回上游，而不是無限緩衝。例如有界佇列滿了就阻塞生產者、TCP 流量控制（receive window）、Reactive Streams 的 request(n)、Kafka consumer 自然地以自己的速度 poll。無界佇列是隱藏的炸彈：它只是把 OOM 延後，並讓延遲無限增長。

Graceful degradation（優雅降級）

部分功能故障時，提供「較差但可用」的結果。例如：個人化推薦服務掛了，回傳熱門商品；user profile 讀不到，就用 contextual 資訊（地區、裝置）出價或放棄出價；非核心功能（如即時報表）直接關閉。通常搭配 feature flag 與斷路器 fallback。

冪等（Idempotency）與 Exactly-once 的實際含義

重試是韌性的基礎，而重試安全的前提是冪等：同一操作執行一次或多次，系統最終狀態相同。HTTP 語意上 GET/PUT/DELETE 是冪等的，POST 不是。SET balance = 100 冪等，balance += 10 不冪等。

Exactly-once delivery 在一般網路上是不可能的（兩將軍問題：發送方永遠無法確定對方是否收到最後一個確認）。實務上說的 exactly-once 其實是 effectively-once / exactly-once processing：

實作冪等的常見手法：

• Idempotency key：client 為每個邏輯操作產生唯一 key（如 UUID），放在 header（例如 Stripe 的 Idempotency-Key）。伺服器記錄 key → 結果；重複請求直接回傳先前的結果。
• 唯一約束：以業務 ID（event_id、order_id）建 unique index，重複插入會失敗，捕捉錯誤當成功即可（INSERT ... ON DUPLICATE KEY / ON CONFLICT DO NOTHING）。
• 條件更新 / 版本號：UPDATE ... WHERE version = 7，重放的請求因版本不符而無效。
• 把操作轉為絕對值：與其送「+10」，不如送「事件 X 的金額是 10」，接收方以事件 ID 去重後再累加。
• 結果與去重記錄在同一個交易中寫入：否則「處理成功但去重記錄寫入失敗」又會重複處理。

# 以 DB 唯一約束實作 idempotency key（PostgreSQL；psycopg 3）
# CREATE TABLE idempotency (key TEXT PRIMARY KEY, status TEXT, response JSONB, created_at TIMESTAMPTZ DEFAULT now());
import json

def handle_charge(conn, idem_key: str, req: dict) -> dict:
    with conn.transaction():
        cur = conn.execute(
            "INSERT INTO idempotency (key, status) VALUES (%s, 'IN_PROGRESS') "
            "ON CONFLICT (key) DO NOTHING RETURNING key", (idem_key,))
        if cur.fetchone() is None:                       # 已存在：重複請求
            row = conn.execute("SELECT status, response FROM idempotency WHERE key = %s",
                               (idem_key,)).fetchone()
            if row[0] == "DONE":
                return row[1]                            # 回傳第一次的結果
            raise RuntimeError("409 Conflict: request in progress")
        result = do_charge(conn, req)                    # 業務寫入與去重紀錄在同一交易
        conn.execute("UPDATE idempotency SET status = 'DONE', response = %s WHERE key = %s",
                     (json.dumps(result), idem_key))
        return result

服務發現與 Service Mesh

在容器環境中，服務實例的 IP 隨時在變，呼叫端需要動態找到健康的實例。

注意 K8s Service 對長連線（gRPC/HTTP2）的負載平衡是連線層級的：同一條 HTTP/2 連線上的所有請求都會打到同一個 pod，容易不平均。解法是 client-side LB（gRPC 搭配 headless service）或 service mesh。

Service mesh（Istio、Linkerd）：在每個 pod 旁放一個 sidecar proxy（Envoy），所有進出流量都經過它，由 control plane 統一下發設定。把 retry、timeout、circuit breaking、mTLS、流量切分（canary）、分散式追蹤從應用程式碼中抽離到基礎設施層。代價：每跳多一點延遲與 CPU/記憶體、維運複雜度高。新趨勢是 sidecar-less（Istio ambient mode、Cilium 以 eBPF 實作）以降低開銷。

分散式與機率型資料結構 深入 高頻

職缺特別寫到「分散式演算法與資料結構」。在海量資料下，「精確」往往太貴：記住 10 億個 user id 的集合要數十 GB，而用 HyperLogLog 估計 unique 數只要 12KB、誤差約 1%。這些結構的共同特點：用可控的誤差換取數量級的空間與時間節省，而且通常可合併（mergeable）——後者讓它們天生適合分散式：各節點各自計算，最後合併。

Bloom Filter

一個長度 m 的 bit array 與 k 個獨立 hash 函式。加入元素：把 k 個 hash 位置設為 1。查詢：k 個位置全為 1 才回答「可能存在」，任一為 0 則「一定不存在」。

• 插入 n 個元素後偽陽性率 ≈ (1 − e^−kn/m)^k。
• 最佳 k = (m/n)·ln 2；給定目標誤判率 p，所需 m = −n·ln p / (ln 2)²，約每元素 1.44·log₂(1/p) bits：p=1% 約 9.6 bits、k≈7。
• 不能刪除（清掉某 bit 會影響其他元素）。需要刪除用 Counting Bloom filter（每格改成小計數器）或 Cuckoo filter（支援刪除，低誤判率時更省空間）。
• 無法擴容：元素超過設計容量時誤判率急升，可用 Scalable Bloom filter（滿了就疊加新的一層）。

import hashlib
import math

class BloomFilter:
    def __init__(self, capacity: int, error_rate: float = 0.01):
        self.m = math.ceil(-capacity * math.log(error_rate) / (math.log(2) ** 2))
        self.k = max(1, round(self.m / capacity * math.log(2)))
        self.bits = bytearray((self.m + 7) // 8)

    def _positions(self, item: str):
        # Kirsch-Mitzenmacher：用兩個 hash 模擬 k 個 → g_i(x) = h1 + i*h2
        d = hashlib.blake2b(item.encode(), digest_size=16).digest()
        h1 = int.from_bytes(d[:8], "little")
        h2 = int.from_bytes(d[8:], "little") | 1
        return ((h1 + i * h2) % self.m for i in range(self.k))

    def add(self, item: str) -> None:
        for p in self._positions(item):
            self.bits[p >> 3] |= 1 << (p & 7)

    def __contains__(self, item: str) -> bool:
        return all(self.bits[p >> 3] & (1 << (p & 7)) for p in self._positions(item))

bf = BloomFilter(capacity=1_000_000, error_rate=0.01)
print(bf.m // 8 // 1024, "KiB,", bf.k, "hashes")   # 約 1170 KiB, 7 hashes
bf.add("user:42")
print("user:42" in bf, "user:43" in bf)            # True, (極可能) False

Count-Min Sketch

d 列 × w 欄的計數器矩陣，每列一個獨立 hash。加入 x：每列在 h_i(x) % w 的格子 +1。查詢：取 d 個格子的最小值（因為碰撞只會讓計數變大，最小值最接近真值）。

誤差保證：估計值 ≤ 真值 + ε·N 的機率至少 1 − δ（N 是總計數），其中 w = ⌈e/ε⌉、d = ⌈ln(1/δ)⌉。例如 ε=0.001、δ=0.01 → w=2719、d=5，約 1.4 萬個計數器，就能追蹤任意多個 key 的近似頻次。搭配一個小的 min-heap 即可求 Top-K heavy hitters。

import hashlib
import heapq
import math

class CountMinSketch:
    def __init__(self, epsilon=0.001, delta=0.01):
        self.w = math.ceil(math.e / epsilon)
        self.d = math.ceil(math.log(1 / delta))
        self.table = [[0] * self.w for _ in range(self.d)]

    def _idx(self, key: str, row: int) -> int:
        h = hashlib.blake2b(key.encode(), digest_size=8, salt=row.to_bytes(16, "little")).digest()
        return int.from_bytes(h, "little") % self.w

    def add(self, key: str, n: int = 1) -> None:
        for r in range(self.d):
            self.table[r][self._idx(key, r)] += n

    def estimate(self, key: str) -> int:
        return min(self.table[r][self._idx(key, r)] for r in range(self.d))

    def merge(self, other: "CountMinSketch") -> None:      # 尺寸與 hash 相同才能合併
        for r in range(self.d):
            for c in range(self.w):
                self.table[r][c] += other.table[r][c]

def top_k(stream, k=10):
    cms, heap, in_heap = CountMinSketch(), [], {}
    for key in stream:
        cms.add(key)
        est = cms.estimate(key)
        if key in in_heap:
            in_heap[key] = est
        elif len(in_heap) < k:
            in_heap[key] = est
        else:
            heap = [(c, x) for x, c in in_heap.items()]; heapq.heapify(heap)
            if est > heap[0][0]:
                del in_heap[heap[0][1]]; in_heap[key] = est
    return sorted(in_heap.items(), key=lambda kv: -kv[1])

HyperLogLog

直覺：把元素 hash 成均勻隨機的 bit 串。看到「開頭連續 ρ 個 0」的機率是 2^−ρ，所以若觀察到的最大前導零數是 ρ，基數大約是 2^ρ。單一估計變異太大，HLL 用 hash 的前 p bits 把元素分到 m = 2^p 個暫存器（bucket），每個暫存器記錄自己看過的最大 ρ，最後用調和平均合併估計（抑制離群值）：

E = α_m · m² / Σ 2^(−M[j])，並在小基數時改用 linear counting（m · ln(m / 空暫存器數)）修正。

• 相對標準誤差 ≈ 1.04 / √m。Redis 用 p=14（16384 個暫存器、每個 6 bits）= 12KB，誤差 0.81%，可估到 2⁶⁴。
• 可合併：兩個 HLL 逐暫存器取 max = 兩個集合「聯集」的 HLL。所以可以各區、各小時分別計算，再任意組合出「全球、整週」的 unique 數。
• 交集不可直接算：只能用排容原理 |A∩B| = |A| + |B| − |A∪B| 估計，當交集很小時相對誤差極大。需要交集時考慮 MinHash / Theta sketch（Apache DataSketches）。
• Redis 指令：PFADD、PFCOUNT（可多 key，回傳聯集基數）、PFMERGE。BigQuery 的 APPROX_COUNT_DISTINCT、Presto/Trino 的 approx_distinct、Spark 的 approx_count_distinct 都是 HLL 家族（HLL++）。

import hashlib
import math

class HyperLogLog:
    def __init__(self, p: int = 14):
        self.p, self.m = p, 1 << p
        self.reg = bytearray(self.m)
        self.alpha = 0.7213 / (1 + 1.079 / self.m)       # m >= 128 時的修正常數

    def add(self, item: str) -> None:
        x = int.from_bytes(hashlib.blake2b(item.encode(), digest_size=8).digest(), "big")  # 64-bit
        idx = x >> (64 - self.p)                          # 前 p bits 決定暫存器
        w = x & ((1 << (64 - self.p)) - 1)                # 剩下 64-p bits
        rank = (64 - self.p) - w.bit_length() + 1         # 前導零個數 + 1
        if rank > self.reg[idx]:
            self.reg[idx] = rank

    def count(self) -> int:
        z = sum(2.0 ** -r for r in self.reg)
        est = self.alpha * self.m * self.m / z
        zeros = self.reg.count(0)
        if est <= 2.5 * self.m and zeros:                 # 小基數修正：linear counting
            est = self.m * math.log(self.m / zeros)
        return round(est)

    def merge(self, other: "HyperLogLog") -> "HyperLogLog":
        out = HyperLogLog(self.p)
        out.reg = bytearray(max(a, b) for a, b in zip(self.reg, other.reg))
        return out

tokyo, sg = HyperLogLog(), HyperLogLog()
for i in range(600_000): tokyo.add(f"user{i}")
for i in range(400_000, 1_000_000): sg.add(f"user{i}")      # 與東京重疊 20 萬人
print(tokyo.count(), sg.count(), tokyo.merge(sg).count())  # 約 600k、600k、1,000k（誤差約 1%）

Skip List

多層的有序鏈結串列：最底層包含所有元素，每個元素以機率 p（通常 1/2 或 1/4）晉升到上一層。查詢從最高層開始往右走，遇到比目標大的就下降一層，期望時間 O(log n)。

• 為什麼 Redis ZSET 用 skip list 而不是紅黑樹：實作簡單、範圍查詢（ZRANGEBYSCORE）只需找到起點後沿底層走、記憶體與平衡樹相當。Redis 在每個節點加上 span 欄位以 O(log n) 支援 ZRANK。ZSET 實際是 dict（member→score，O(1) 查 score）+ skip list（依 score 排序）。小資料量時用 listpack 節省記憶體。
• 並行友善：插入只影響局部指標，容易做出 lock-free 版本（Java 的 ConcurrentSkipListMap），所以 LevelDB/RocksDB 的 memtable 用 skip list。

Gossip Protocol

又稱 epidemic protocol：每個節點每隔一段時間（例如 1 秒）隨機挑選少數幾個節點交換狀態（membership、心跳計數、metadata 版本）。資訊像傳染病一樣擴散，約 O(log N) 輪後傳遍整個叢集。

• 模式：push（主動告知）、pull（主動詢問）、push-pull（交換，收斂最快）。
• 優點：無中心、容錯（部分節點掛掉不影響傳播）、每節點負載固定、可擴展到數千節點。
• 缺點：最終一致、收斂時間是機率性的、訊息有冗餘。
• 使用者：Cassandra（membership 與 schema 版本）、Consul/Serf（memberlist）、Redis Cluster bus、Amazon Dynamo、Bitcoin 交易廣播。

SWIM 失效偵測

傳統的全對全心跳是 O(N²) 訊息，無法擴展。SWIM（Scalable Weakly-consistent Infection-style process group Membership，2002）把失效偵測與成員資訊傳播分開：

1. 每個週期，節點隨機 ping 一個成員。
2. 逾時未回應，請 k 個其他成員代為 ping（間接探測），避免因 A 與 B 之間單一路徑壅塞而誤判。
3. 仍失敗則標記 suspect（而非直接宣告死亡），給 B 反駁的機會；B 用遞增的 incarnation number 宣告自己 alive。
4. 成員變更資訊附帶（piggyback）在 ping/ack 訊息上傳播，不需額外訊息。

結果：每節點的訊息負載為常數、偵測時間期望為常數、誤判率低。HashiCorp memberlist（Consul、Nomad、Serf）就是 SWIM 加上 Lifeguard 改良。另一種常見的失效偵測器是 Phi Accrual Failure Detector（Cassandra、Akka）：不輸出「死/活」二元結果，而是根據心跳間隔的歷史分佈輸出一個懷疑程度 φ，由應用自行設定閾值。

Appier 情境題：多區 Bidder、預算 Pacing、Unique Reach 深入

以下以廣告平台常見做法為例，把本章概念串起來。這類題目沒有標準答案，重點是講清楚取捨與誤差上界。

全球多區 Bidder 架構

• 讀取路徑全部在地化（PA/EL）：user profile、模型、campaign 設定都複製到各區，出價時不跨區。
• Campaign 設定：在中央以強一致方式寫入（single-leader），透過事件/CDC 非同步推到各區，各區接受秒級延遲。暫停 campaign 這類「停損」操作要特別快：可以用專門的高優先級通道推播。
• 事件流：各區先寫本地 Kafka（低延遲、跨區斷線也不影響出價），再非同步複製（MirrorMaker 2 之類）到中央做報表與計費。
• Profile 更新：多個區域都可能更新同一使用者的特徵 → 屬於 multi-leader，用 LWW（大多數特徵）或 CRDT（計數類特徵）合併。

預算 Pacing 的跨節點計數：近似 vs 精確

問題：一個 campaign 日預算 1000 美元，全球數百個 bidder pod 同時在花這筆錢，每秒上萬次出價。如何不超支、又能平均地花完？

實務常見組合：B + C。中央 controller 依照每小時目標花費曲線（pacing，例如依流量預測平滑分配）計算每個區域、每個 pod 的配額，pod 在本地扣減；花費事件同時回報給中央校正。快接近日預算時縮小配額粒度（例如剩 5% 時配額從 5 美元降為 0.5 美元），把超支上界壓得更低。另外，因為出價時只知道出價，贏標價格（second price 或 first price）要等 win notice 回來才確定，所以計算可用額度時要把「已出價未知結果」的在途金額保守地預扣。

import threading

class LocalBudget:
    """Pod 本地的預算配額：出價路徑只做記憶體操作，背景向中央補貨。"""
    def __init__(self, campaign_id, controller, chunk=5.0, low_watermark=0.3):
        self.campaign_id, self.controller = campaign_id, controller
        self.chunk, self.low_watermark = chunk, low_watermark
        self.available = 0.0          # 已向中央取得、尚未使用的配額
        self.inflight = 0.0           # 已出價、尚未收到 win/loss 結果的金額（保守預扣）
        self.lock = threading.Lock()
        self.refilling = False

    def try_reserve(self, bid_price: float) -> bool:
        with self.lock:
            if self.available - self.inflight < bid_price:
                self._maybe_refill()
                return False          # 配額不足：本次不出價（安全地降級）
            self.inflight += bid_price
            if self.available - self.inflight < self.chunk * self.low_watermark:
                self._maybe_refill()
            return True

    def settle(self, bid_price: float, win_price: float | None) -> None:
        with self.lock:
            self.inflight -= bid_price
            if win_price is not None:
                self.available -= win_price

    def _maybe_refill(self):
        if self.refilling:
            return
        self.refilling = True
        def work():
            granted = self.controller.grant(self.campaign_id, self.chunk)  # 中央原子扣減全域餘額
            with self.lock:
                self.available += granted
                self.refilling = False
        threading.Thread(target=work, daemon=True).start()

用 HyperLogLog 算 Unique Reach

Reach（觸及人數）是廣告主最在意的指標之一：「這個 campaign 本週觸及了多少不重複使用者？」精確計算需要保存所有 user id 的集合：1 億使用者 × 每個 id 約 16 bytes 以上的 set 開銷，單一 campaign 就要數 GB，乘上數萬個 campaign × 各種日期區間組合，完全不可行。

1. Stream processor（Flink/Spark Streaming）消費曝光事件，為每個 (campaign_id, 區域, 小時) 維護一個 HLL（約 12KB）。
2. 每小時把 HLL sketch 以二進位寫入儲存（Redis、或資料倉儲的 BYTES 欄位）。
3. 查詢「某 campaign 過去 7 天全球 reach」時，取出 7×24×區域數個 sketch，逐暫存器取 max 合併後估計——因為合併是聯集，跨天重複的使用者自動去重。
4. 誤差約 1%，報表場景完全可接受；若用於計費（例如按 reach 收費），則以離線批次在資料倉儲精確計算 COUNT(DISTINCT) 作為帳單依據。

import redis
r = redis.Redis()

def on_impression(campaign_id: int, user_id: str, region: str, hour: str):
    r.pfadd(f"reach:{campaign_id}:{region}:{hour}", user_id)

def weekly_reach(campaign_id: int, hours: list[str], regions: list[str]) -> int:
    keys = [f"reach:{campaign_id}:{rg}:{h}" for h in hours for rg in regions]
    return r.pfcount(*keys)        # PFCOUNT 多個 key = 聯集基數，不需先 PFMERGE

延伸：Frequency Capping

「同一使用者一天最多看到這個廣告 3 次」。精確做法是以 (user_id, campaign_id, day) 為 key 的計數器存在低延遲 KV（Redis/Aerospike），出價時讀取、曝光時遞增，並以 user_id 做分區讓同一使用者的計數落在同一節點。跨區時，使用者通常會被路由到最近的區域，所以以本地計數為主、跨區非同步合併（G-Counter 語意）通常足夠；偶爾多投一次的代價遠小於每次出價跨區查詢的延遲。這又是一次 PA/EL 的取捨。

面試自測題