無主複製 (Leaderless / Quorum)

★★★★Reviewed

FromDDIADatabase Internals

📚 From the Books

無主複製 (Leaderless / Quorum)Replication

沒有 leader,客戶端(或協調節點)直接同時寫多個副本,靠 quorum(多數派)來保證讀寫重疊。它用「讀寫各自湊夠票數」換掉了 failover 的複雜性,但也讓「一致性」變成一個機率與運維問題。

🧠 Intuition

TIP

把它想成「投票」:寫的時候請 w 個副本簽收,讀的時候問 r 個副本。只要 w + r > n,讀的集合與寫的集合必定有交集——你至少會問到一個「看過最新寫入」的副本,再靠版本號挑出最新值。

⚖️ Tradeoffs

Quorum 條件 w + r > n — 旋鈕怎麼調
  • 典型 n=3、w=2、r=2:能容忍 1 個副本掛掉仍可讀可寫。
  • 讀多寫少:調 w=n、r=1,寫慢但讀快(適合讀密集)。
  • 寫多讀少:調 w=1、r=n,反之。
  • 只要 w + r > n 就保證讀寫集合相交;但 w、r 變小(如 w+r ≤ n)能換更高可用/低延遲,代價是可能讀到舊值。
讀修復 (Read repair) 與 反熵 (Anti-entropy) — 副本怎麼追上
  • 讀修復:讀取時若發現某副本回了舊值,客戶端/協調節點順手把新值寫回去。被動、只修「有人讀到」的資料——冷資料可能長期不一致。
  • 反熵程序 (Anti-entropy):背景程序持續比對副本差異並補齊(常用 Merkle tree 加速比對)。主動、覆蓋冷資料。
  • 兩者通常並用:讀修復顧熱資料的即時性,反熵顧全量的最終收斂。
Sloppy Quorum 與 Hinted Handoff — 可用性的延伸
  • 網路分區時,「應該負責」的 n 個節點可能湊不到 w 個。Sloppy quorum:暫時把寫入交給其他可達節點(不在原本的 home 節點集合內),先收下保可用。
  • Hinted handoff:這些臨時節點記著「這筆其實該給某某節點」,等對方恢復再轉交回去。
  • 代價:sloppy quorum 下,w + r > n 的相交保證不再成立——因為寫入可能落在原集合之外。它提高的是寫入持久性/可用性,不是讀一致性。
為何 Quorum ≠ 線性一致 (Linearizability)
  • 並行寫的時序模糊:兩個並行寫沒有全域定序,quorum 不保證大家對「誰先誰後」達成一致——只能靠 LWW 或版本向量事後調和(仍可能丟寫)。
  • 讀修復非原子:修復進行到一半,不同讀者可能看到新舊夾雜。
  • Sloppy quorum 破壞相交:如上,寫可能落在讀問不到的節點。
  • 結論:quorum 給的是「可調的最終一致性」,不是線性一致。要線性一致得加共識(如 Paxos/Raft)或讀寫同步阻塞,那就回到了協調的成本。

🔑 Takeaways

✍️ My Notes

2026-07-01

  • Q: 都已經 w + r > n 保證讀寫集合相交了,為什麼還不算強一致?
  • A: 相交只保證「讀的集合裡至少有一個副本看過最新寫入」——它解決的是「讀得到最新值」,沒解決「認得出哪個是最新值、以及並行寫該如何定序」。具體三個漏洞:(1) 兩個並行寫沒有全域順序,quorum 不裁決先後,最後得靠 LWW/版本向量,仍可能靜默丟寫;(2) 讀修復不是原子操作,修一半時讀者看到的是新舊混合;(3) 一旦啟用 sloppy quorum,寫入可能落到原節點集合之外,相交保證直接失效。所以 quorum 給的是「可調的最終一致性」,要真正線性一致就得引入共識協定,付出協調延遲。

📖 Further Reading

🔗 Dive Deeper