分散合意アルゴリズム Raft を理解する
https://qiita.com/torao@github/items/5e2c0b7b0ea59b475cce
ぼんやりと理解してたけど、もう少しちゃんと理解する
Raft は安全な ステートマシンレプリケーション (SMR; State Machine Replication) を実装するための分散合意アルゴリズム。分散システムにおいて一貫性 (分散トランザクション) と可用性 (障害耐性) を実装するための基本的な部品として使用することができる。
分散システムにおける合意 (Consensus) とは、参加しているすべてのノードが最終的に同じ値を採用すること (≒ 同じ状態になること) を意味します。このため、合意アルゴリズムは一貫性のあるレプリケーションを実現するために利用されます。
元々、Hyperledger Fabric というプライベートブロックチェーンが Raft で合意形成するという話を聞いて「Raft って Byzantine 障害耐性はないよね?」と論文を読み始めたことがきっかけなのでブロックチェーンの視点を交えています
なんかcrdtへの問題にすごく近しいコメントな気がするんだけどYudai.icon
State Machine Replication
https://scrapbox.io/files/6894d4a50cef156afffa87d1.png
Raft は強い一貫性を持つ SMR に基づくアーキテクチャ
マルチキャストされるコマンドのことをログと読ぶ
https://scrapbox.io/files/6894d4a50cef156afffa87d1.png
どのようにログの適用順序を正しく決める？
https://scrapbox.io/files/6894d4f826880b3fa518d0bd.png
リーダー と呼ばれる 1 つの FSM に送信され、そのリーダーがログの順序を決定します。
なんかリーダーノードやブロックプロデューサーとかってここから来てる？
死活監視
https://scrapbox.io/files/6894d5da59ac9a5357bc02ec.png
死活監視はリーダー役が機能していることを確認する動作です。合意クラスタ内のフォロワーはリーダーが機能していないことを検知すると速やかにリーダー選挙を開始します。
リーダー選挙
https://scrapbox.io/files/6894d62486b187d81bd324b5.png
Raft には選挙が行われるたびに単純増加するタームと呼ばれる数値があります。ある時点のタームを担当するリーダーは 1 つないしは 0 (選挙失敗時) であり、2 つ以上のリーダーが同一のタームに発生することはありません。
さて、合意クラスタ内のリーダー不在を検知したフォロワーはリーダーに立候補し候補者となります。候補者は自分の認識しているタームを一つ進め、自分に投票し、クラスタ内の他のサーバの RequestVote RPC (投票要求) を呼び出します。
Monasでもそうえば提案ノードの提案とノードの割り当ての処理についてを思い出した
結局排他的論理和距離によって選出するようにしたけど、確かにRaftだと、選出方法難しいね
ただここで得られることは、毎回リーダーの選出はコストが高いのでは？ってことなんよね