共識算法

1）什麼是共識，為什麼需要共識

共識-在發生故障和延遲時,在多個節點之間協商相同的值/值序列。傳統上，狀態復制任務（State Machine Replication，SMR）是解決方案：存在確定性狀態機器和總體操作順序。

• 共識（SMR）：統一的總命令順序→線性存儲/註冊表，群集元數據，事務協調員。
• 沒有完全順序的法定操作（類似Dynamo，CRDT）：允許差異和隨後的合並；在需要全球序列化的地方不能取代共識。

2）時間與故障模型

2.1時間模型

異步網絡：延遲是無限的；如果沒有額外的假設，FLP定理⇒無法保證安全性和生活性。
部分同步（通常在實踐中）：在未知的T之後，系統「表現」同步-大多數算法（Raft，Paxos）都依賴它。
同步：對通道的嚴格超時限制（除專用網絡/PTP外，很少銷售）。

2.2故障模型

Crash-fault tolerant （CFT）：節點可能會掉落/掛起,但不表現惡意。
Byzantine-fault tolerant （BFT）：節點可以說謊/偽造消息。需要3f+1節來耐受f拜占庭語。

3）共識屬性

安全（安全）：一致性（兩個正確的節點不會解決不同的值）。
Liveness（活著）：如果網絡「健康」,解決方案就會實現。
可線性化（線性）：操作「可見」為單一順序的原子。
耐用性：所作出的決定不會退回（日誌保護/法定人數）。

4）法定人數，多數和交叉點

在CFT世界中，經典：法定人數>N/2。領導者的記錄和選舉使用法定人數的交集，因此兩個「有效」操作不會發生沖突。
在BFT世界中：3f+1中的2f+1的法定值提供了至少f+1誠實節點的交叉點。

交叉規則：任何兩個法定人數必須具有≥1通用誠實節點（CFT）或≥f+1（BFT）。

5）狀態復制（日誌+應用）

• Snapshots（可以刪除/編譯早期記錄的狀態切片）。
• 雜誌匯編和日誌三重奏。
• 確定性檢查（密碼/密碼的相同版本）。

6）領導和非領導力計劃

領導者（Raft，Multi-Paxos，ZAB）：一位領導者將記錄序列化→在精神和操作上更簡單，在穩定的領導者上更好。
無標記/多標記（EPaxos，Caesar）：對領導者的更多並發性和寬容，但實現和沖突解決更為困難；在小團隊沖突中可見利潤。

7）經典CFT算法

7.1 Paxos/Multi-Paxos（和實踐）

想法：兩個階段（prepare/propose），接受者的承諾，多數法定人數。Multi-Paxos留下「穩定的領導者」，並在「預熱」後將操作轉換為單運行（用於新記錄）。

• 靈活但難以實現的模型。
• 通過特殊記錄（joint consensus）重新配置。
• 實際上，是庫/引擎（Chubby/Spanner世代）。

7.2 Raft

可培訓性的解密：領導者選擇、日誌復制、重新配置。

選擇：隨機定時，熱量投票；一個領導一個任期。
AppendEntries：領導者流記錄,跟隨前綴匹配（索引/term）,通過多數提交進行通信。
讀取路徑：用於線性讀取的lease-reads（具有強大的領導者）或讀取索引。
Reconfig：「協作配置」（joint）-節點在轉換前在兩個群集中進行投票。

優點：更容易開發/debag,強階不變量。缺點：領導者是壓力點。

7.3 ZAB (ZooKeeper Atomic Broadcast) / Viewstamped Replication (VRR)

ZAB：領導者廣播事務，恢復階段，zxid（時代+索引）。
VRR：具有主要復制的「視圖」（視圖）在精神上類似於Multi-Paxos。

8）非裏德/多用戶CFT

8.1 EPaxos

沒有永久領導者：任何節點都可以啟動命令。
沖突團隊獲得部分順序；無沖突-在本地被命令進入1-2 RTT。
在低沖突但復雜的依存關系/圖代碼下贏得地理分布。

8.2 Caesar, Mencius

在WAN中優化延遲/平衡和操作的變化。

9） BFT算法和PoS系列

9.1 PBFT (Practical BFT)

三個階段（pre-prepare/prepare/commit）,需要3f+1節點。
局域網、多通道道路和O （N ²）消息的低潛伏率。

9.2 Tendermint（BFT-PoS風格）

Proposal和兩個投票（prevote/precommit）的回合。
確定性建議驗證器，超時，部分同步。
適用於具有數十個/數百個驗證器的永久性/PoS網絡。

9.3 HotStuff（和衍生產品）

將三相方案統一為具有法定證書（QC）的「包」。
線性通信復雜性，對批處理和並行管道化的支持對於區塊鏈實現（例如Diem/Move生態系統）非常方便。
使用閾值簽名（threshold signatures）可減少流量。

9.4 PoW/累積共識（簡述）

不是嚴格意義上的BFT，而是概率收斂性（工作最多的鏈）。優點：簡單/開放；缺點：能量，~秒鐘到最後一分鐘。

10）讀數： 線性、串行和緩存

線性讀取：帶有活動優惠或通過read-index （Raft）的領導者通過法定人數→確認。
連續：您可以從任何節點讀取,但不保證新鮮度。
Follower reads：寬松要求允許使用；對於緩存-ok。

11）重新配置（群集組成變更）

需要兩種重疊的配置（joint consensus）：任何commites都通過兩種配置的法定人數→沒有「孔」。
每次添加/刪除一個,遵守法定人數的大小。
領導力轉移（領導力轉移）減少了停頓。

12）性能和調音

12.1個延誤

領導算法：每條記錄1個RTT（具有穩定的領導者）+復制。
地理分配：RTT WAN占主導地位→使用本地區域+跨區域重鋪或EPaxos/HotStuff方法。

12.2個吞吐量

與AppendEntries平行的Batching（命令分組），paig-kesh日誌，並行應用（當操作切換時）。
驅動器：NVMe/日誌在單獨的設備上，「O_DIRECT」/AIO，帶有SLA約束的大型「fsync」 Intervel（可執行性/延遲權衡）。

12.3尾巴p99

避免熱節點（領導者始終是其中之一）：定期輪換或閱讀到追隨者。
控制GC暫停（JVM/Go）、CPU Pins、NUMA。

13）地理和拓撲

1個區域，3個區域：經典的CFT集群（N=3/5）。
2個區域：避免-分隔1-1時無法獲得可靠的法定人數。
3+區域：「中間」或無限制算法的領導者；具有異步日誌的區域代理/本地前沿是可能的。

14）實際操作問題

14.1 Snapshots和恢復

日誌大小/操作數閾值。
將狙擊手轉移到新節點；驗證基準金額。

14.2監視

領導：誰是領導者，改變了多少時間表（term/epoch）。

Лаги: `append_latency`, `commit_index - applied_index`.

定額健康： 「多數/2f+1活著嗎？」

日誌大小/堆疊速度，快門隊列。
對於BFT：選票份額，取消簽名者，QC延遲。

14.3安全性/代碼一致性

協議在線上的忠誠度，遷移與日誌兼容性。
外部效果上的折射令牌（請參閱「分布式鎖定」）：領導期限（term）傳遞給CRON/jobs。

15）反模式

將「為了時尚」的共識放在一個沒有序列化的DBMS或法定閱讀中。
混合CP和AP無界限（CAP） →不可預測的UX。
重新評估具有數十個節點的企業任務的PoW/PoS（復雜/昂貴）。
更改組成時忽略重新配置和「相交的法定人數」。
缺少read-barrier（lease/read-sindex）→「臟」讀取。
運行2節點群集（沒有多數）。
低估磁盤和fsync：「在內存中一切都在飛行」-直到第一次重新啟動。

16）選擇支票清單

1.故障模型： CFT（汙垢）或BFT（惡意）?

2.地理：一個區域/三個區域或WAN?RTT決定。
3.閱讀語義：需要線性閱讀嗎？Lease/read-index/follover rids。
4.負載：p50/p99，throughput的期望；是否需要多領導能力。
5.操作復雜性：庫/完成引擎（etcd/ZK/Consul/Raft-libs）與自己的實現。
6.重新配置：頻繁嗎？需要聯合咨詢和遷移工具。
7.整合：外部副作用-是否有epoch/term fencing？
8.安全性：節點身份驗證，鏈路加密，協議版本控制。
9.測試花花公子：分區，GC停止，殺手，慢盤，clock skew。
10.可觀察性：已配置領導者/拉格/日誌和差分度量。

17）迷你手冊： 什麼時候拿什麼

etcd/Raft群集，用於DC內部的配置/鎖定/協調。
ZooKeeper/ZAB用於已經綁定到ZK（舊堆棧，隊列，領導力）的服務。
通過高度專業化的系統中的現成服務/庫來實現多功能。
EPaxos在地理分布和低命令沖突中。
Tendermint/HotStuff 用於永久性網絡/PoS layer，具有數十到數百個驗證器和最終要求。
當不需要共識時，類似於Dynamo/CRDT的可用性/規模很重要，然後合並。

18）接口示例（偽）

18.1 Commit錄音（Raft風格）

pseudo client -> leader: Propose(cmd)
leader. appendLog(cmd)
leader. replicateToQuorum()
if quorum_acked:
leader. commit(index)
leader. apply(index)
leader. reply(client, ok)

18.2線性讀取索引（Raft）

pseudo client -> any: LinearizableRead node -> leader: ReadIndex?
leader -> quorum: Heartbeat (barrier)
leader -> node: ReadIndex=commit_index node. wait_until(applied_index >= ReadIndex)
node. reply(client, state_at(ReadIndex))

18.3聯合配置

pseudo old_conf + new_conf # quorums must intersect commit (entries under joint)
switch_to(new_conf)

18.4 BFT（HotStuff接近）

pseudo propose(block)
collect votes -> QC lock on highest QC commit when have consecutive QCs across phases

19) FAQ

問：為什麼不使用兩個節點和決勝局？
答：沒有第三個仲裁員的兩個節點在分手時不會產生法定人數。需要≥3（CFT）或3f+1（BFT）。

Q： Raft對Paxos「簡單」有什麼好處?

答：清晰的解構，可理解的邏輯和配置不變性；更容易實施和陪伴。

Q： 如何在不加載領導的情況下快速閱讀?

A：非臨界的follower-reads（串行），線性的lease-reads/read-sindex；緩存。

問：p99殺死什麼？
A： WAN-RTT、fsync磁盤、GC腳、過熱的領頭羊、「高峰時段」的大狙擊手。

Q： 是否需要對緩存/目錄達成共識?

A：如果有足夠的事件一致性-沒有。如果需要事務不變量-是的。

20）結果

共識是嚴格一致和精簡的工具。根據故障模型和地理位置選擇算法；提供法定相交、正確的re配置、關鍵位置的線性讀取和可觀察性。不要忘記對外部效果、快照和雜誌紀律的思考。然後狀態復制將是可預測的，並且事件是罕見且易於理解的。