コンセンサスアルゴリズム

1）コンセンサスとは何か、なぜ必要なのか

「コンセンサス」（Consensus）-複数のノード間で同じ値/シーケンスの値をネゴシエートし、障害や遅延を発生させます。伝統的に、ステートレプリケーション（State Machine Replication、 SMR）の問題は解決されています。

• コンセンサス（SMR）：コマンド→線形化可能なストレージ/レジストリ、クラスタメタデータ、トランザクションコーディネータの1つの合計順序。
• 総オーダーなしのクォーラム演算（Dynamo-like、 CRDT）：発散とその後の合併を可能にする。グローバルなシリアル化が必要なコンセンサスを置き換えないでください。

2）時間と失敗モデル

2.1タイムモデル

非同期ネットワーク：遅延は無制限です。FLPの定理は、追加の仮定なしに安全と生活の両方を保証することは不可能です。
部分的に同期（しばしば実際には）：未知のTの後、システムは同期的に「振る舞う」-ほとんどのアルゴリズム（Raft、 Paxos）はこれに依存します。
同期：チャンネルの厳密な時間制限（特別なネットワーク/PRTを除いて、ほとんど販売されていません）。

2.2故障モデル

クラッシュフォールトトレラント（CFT）：ノードが落下/ハングすることがありますが、悪意を持って動作しません。
Byzantine-fault tolerant （BFT）：ノードは嘘をつくことができます。f Byzantineへの許容には3f+1ノットが必要です。

3）コンセンサスの性質

安全性：一貫性（2つの正しいノードは異なる値を解決しません）。
Liveness：ネットワークが「健全」であれば、解決策が達成されます。
線形性（直線性）：操作は1つの順序で原子として「見られる」。
耐久性：決定はロールバックされません（ログ/クォーラム保護）。

4）クォーラム、マジョリティ、交差点

CFTの世界では、古典的な：quorum> N/2。レコードとリーダーの選挙はクォーラム交差を使用するため、2つの「有効な」操作は競合しません。
BFTの世界では、3f+1のquorums 2f+1は、少なくともf+1正直なノードの交点を提供します。

Crossing rule：任意の2つのクォーラムには、≥ 1 common fair node （CFT）または≥ f+1 （BFT）が必要です。

5）状態レプリケーション（log+application）

• スナップショット（初期レコードを削除/コンパイルできる状態のスライス）。
• ジャーナル圧縮とログトライアム。
• 確定性チェック（同じコード/設定バージョン）。

6）リーダーシップと非リーダーシップのスキーム

リーダーシップ（Raft、 Multi-Paxos、 ZAB）： 1人のリーダーが記録をシリアライズし、精神的にも操作的にも簡単に、安定したリーダーのレイテンシーを向上させます。
リーダーレス/マルチリーダー（EPaxos、シーザー）：リーダーのためのより多くの並列性と寛容、しかし、より困難な実装と紛争解決；利益はチームの小さな対立で見えます。

7）古典的なCFTアルゴリズム

7.1 Paxos/マルチPaxos（およびプラクティス）

アイデア：2つのフェーズ（準備/提案）、受諾者の約束、大多数のクォーラム。Multi-Paxosは「安定したリーダー」を残し「、ウォームアップ」後にオペレーションを1ラウンド（新規エントリー用）に変えます。

• 適用範囲が広いが、モデルを実装すること困難。
• 特別なエントリ（共同コンセンサス）による再構成。
• 実際には、ライブラリ/エンジン（Chubby/Spanner世代）。

7.2いかだ

学習のために分解：リーダーの選択、ログのレプリケーション、再構成。

選挙：ランダムなタイムアウト、投票期間；任期ごとに1人のリーダー。
AppendEntries：リーダーがレコードをストリームし、プレフィックス（index/term）の一致を監視し、大多数の固定にコミットします。
Read-path：リース読み取り（強力なリーダー付き）またはリニア読み取りのリードインデックス。
Reconfig： 「joint」-ノードは切り替える前に2つのクラスタに投票します。

長所：開発/デバッグが容易で、強いオーダー不変量。短所：リーダーは圧力点です。

7.3 ZAB （ZooKeeper原子放送）/Viewstamped Replication （VRR）

ZAB：リーダーはトランザクション、回復フェーズ、zxid （epoch+index）をブロードキャストします。
VRR： Multi-Paxosと同様に、プライマリ・レプリカントを備えた「ビュー」。

8）非リーダー/マルチリーダーCFT

8.1 EPaxos

永続的なリーダーはありません。どのノードでもコマンドを開始できます。
競合チームは部分的な注文を受け取ります。conflict-free-ローカルで1-2 RTTにコミットします。
コンフリクトが少ないが複雑な依存関係/グラフコードで地理分布を得る。

8.2シーザー、メンシウス

レイテンシ/バランシングとWAN操作を最適化するバリエーション。

9） BFTアルゴリズムとPoSファミリ

9.1 PBFT（実用的なBFT）

3つのフェーズ（事前準備/準備/コミット）は、3f+1ノードが必要です。
ローカルネットワーク、マルチステップロード、O （N ²）メッセージの低遅延。

9.2テンダーミント（BFT-PoSスタイル）

提案と2票のラウンド（防止/事前コミット）。
決定論的バリデータ提案者、タイムアウト、部分的同期性。
数十/数百のバリデータを持つ許可/PoSネットワークに適しています。

9.3 HotStuff（および誘導体）

三相スキームは、クォーラム証明書（QC）で「パッケージ」に統一されています。
コミュニケーションの線形複雑さ、パッケージングと並列パイプラインのサポートは、ブロックチェーン（Diem/Moveエコシステムなど）の実装に便利です。
しきい値署名により、トラフィックが削減されます。

9.4 PoW/累積コンセンサス（要約）

厳密な意味でのBFTではなく、確率的収束（ほとんどの作業を伴うチェーン）。利点：シンプルさ/開放性；デメリット：エネルギー、~秒〜分〜ファイナリティ。

10）読み取り： 線形、シーケンシャル、キャッシュ

線形読み取り：アクティブなリース付きリーダーまたは読み取りインデックス（Raft）→クォーラムによる確認。
Sequential：任意のノードから読み取ることができますが、鮮度の保証はありません。
フォロワーは読む：弱い条件の下で許される；キャッシュの場合-OK。

11）再構成（クラスタ構成の変更）

2つの重複コンフィギュレーション（共同コンセンサス）が必要です：すべてのコミットは両方のコンフィギュレーションのクォーラムを渡します→「穴」なし。
一度に1つずつ追加/削除し、クォーラムサイズを観察します。
リーダーシップ移転は一時停止を軽減します。

12）パフォーマンスとチューニング

12.1遅延

リーダーシップアルゴリズム：1書き込みあたり1 RTT（安定したリーダー付き）+レプリケーション。
地理分布：WAN RTTが支配する→ローカル領域+クロスリージョナルレプリケーションまたはEPaxos/HotStuffアプローチを使用する。

12.2スループット

バッチ（コマンドのグループ化）、並列AppendEntries、ログページキャッシュ、並列アプリケーション（操作が切り替わった場合）。
ディスク：NVMe/別のデバイスでのログ'O_DIRECT '/AIO、 SLA制限付きの大きな'fsync'間隔（耐久性/レイテンシの妥協）。

12.3 p99の尾

ホットノットを避けてください（常にリーダーが1つあります）：フォロワーの定期的な回転または読み取りオフロード。
モニタGCの一時停止（JVM/Go）、 CPUピン、NUMA。

13）地理とトポロジー

1領域、3ゾーン：古典的なCFTクラスタ（N=3/5）。
2つの領域：回避-1-1分割で信頼性の高いクォーラムはありません。
3+リージョン：「中間」またはリーダーレスアルゴリズムのリーダー。非同期ログを持つリージョナルプロキシ/ローカルフロントが可能です。

14）実務上の問題

14.1スナップショットとリカバリ

ジャーナルのサイズ/トランザクション数によるしきい値。
スナップショットを新しいノードに転送する。チェックサムのチェック。

14.2モニタリング

リーダーシップ：リーダーは誰ですか、どのように多くの用語（用語/エポック）が変更されました。
'append_latency'、 'commit_index-applied_index'。

Quorum health： 「大多数は生きている/2f+1ですか？」

ログサイズ/圧縮速度、スナップショットキュー。

BFTの場合： 投票シェア、署名者のダンプ、QC遅延

14.3コードセキュリティ/一貫性

ワイヤ上のプロトコルバージョニング、ログ互換性のある移行。
外部効果に対するフェンシングトークン（「分散ロック」を参照）：CRON/ジョブに転送するリードタイム（用語）。

15）アンチパターン

1つのDBMSまたはquorumがシリアライズなしで読み取る「ファッションのために」で十分なコンセンサスを入れてください。
明確な境界（CAP）→予測不可能なUXのないCPとAPをミックスします。
数十のノード（困難/高価）を持つエンタープライズタスクのPoW/PoSを過大評価します。
コンポジションが変更されたときに再構成と「交差クォーラム」を無視します。
読み取り障壁の欠如（リース/読み取りインデックス）→汚れた読み取り。
2ノードのクラスタを実行します（過半数なし）。
ディスクとfsyncを過小評価：「すべてがメモリに飛ぶ」-最初の再起動まで。

16）選択チェックリスト

1.故障モデル：CFT（クラッシュ）またはBFT（悪意のある）？
2.地理：1つの地域/3つのゾーンまたはWAN？RTTが決める。
3.意味の読み取り：線形読み取りは必要ですか？リース/リードインデックス/フォローアップ。
4.負荷：p50/p99、スループットによる期待；マルチリーダーシップが必要かどうか。
5.操作の複雑さ：ライブラリ/オフザシェルフエンジン（etcd/ZK/Consul/Raft-libs）とネイティブの実装。
6.再構成：頻繁に？共同の合意と移行ツールが必要です。
7.統合：外的な副作用-epoch/termによって囲うことがありますか？
8.セキュリティ：ホスト認証、チャネル暗号化、プロトコルバージョン制御。
9.テストプレイブック：パーティション、GCストップ、キルリーダー、スローディスク、クロックスキュー。
10.観測可能性：Leader/Lags/JournalとAlertの指標が設定されています。

17）ミニガイド： いつ何を取るか

DC内の構成/ロック/調整のためのetcd/Raftクラスタ。
ZooKeeper/ZABはすでにZK（古いスタック、キュー、リーダーシップ）に関連付けられているサービスです。
高度に専門化されたシステムの既製のサービス/ライブラリを介してマルチパクソ。
地理分布と低いコマンド競合のためのEPaxos。
数十から数百のバリデータと最終要件を持つ許可されたネットワーク/PoS層のためのTendermint/HotStuff。
コンセンサスが不要な場合にはDynamo-like/CRDTが必要ですが、その後の合併によるアクセシビリティ/スケールが重要です。

18）インタフェースの例（擬似）

18.1コミットレコード（いかだスタイル）

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線形読書（いかだ）のための読書索引)

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

Q： 2つのノットとタイブレーカーを使用しないのはなぜですか？
A： 3番目のアービターのない2つのノードは、スプリットでクォーラムを与えません。≥ 3 （CFT）または3f+1 （BFT）が必要です。

Q：いかだ「より簡単な」Paxosは何ですか？
A：明確な分解、ログと構成の理解可能な不変；実装し、維持すること容易。

Q：リーダーをロードせずに速く読むにはどうすればよいですか？
A：非クリティカルのフォロワー読み取り（連続）、リニアのリース読み取り/読み取りインデックス；キャッシュ。

Q：何がp99を殺しますか？
A： WAN-RTT、ディスクfsync、 GC停止、過熱リーダー、ラッシュ時に大きなスナップショット。

Q：キャッシュ/カタログはコンセンサスが必要ですか？
A：十分な最終的な一貫性-いいえ。トランザクション不変量が必要な場合は、はい。

20）合計

コンセンサスは、厳密な一貫性と注文のためのツールです。失敗モデルと地理に基づいてアルゴリズムを選択します。クォーラムクロッシング、正しい再構成、リニアリードを提供します。外的効果、スナップショット、雑誌の規律のためのフェンシングを忘れないでください。その後、状態のレプリケーションは予測可能になり、インシデントはまれで理解可能になります。