Raftについて
分散システムを勉強するのであれば、必ず必要となる。これだけ覚えておこう。 Replicate And Fault Tolerant
Raftの目的
Raftアルゴリズムの目的は、分散システムにおける信頼性の高いリーダー選出とログレプリケーションを通じて、一貫性のある状態を維持することです。具体的には、複数のノードが協調して動作し、一つのノードが故障してもシステム全体としての一貫性と可用性を保つことを目指します。
raft demo site
このサイトを見ると、ラフトの動作が詳細までわかることでしょう。
参考文献
目的を達成する手段
Raftアルゴリズムは、以下の手段を用いて目的を達成します：(これはそのまま、ラフトを開発した研究者のプレゼン（youtubeで見られる）で発表されていたものと同じ)
リーダー選出： クラスタ内の一つのノードがリーダーとして選ばれ、他のフォロワーノードに対して命令を発行します。リーダーはクライアントからのリクエストを受け取り、ログにエントリを追加します。 リーダが死んだ際には新たにリーダを選出するようにプロトコルが組まれています
ログレプリケーション： リーダーがクライアントからのリクエストを受け取ると、そのリクエストをログに記録し、そのログエントリをフォロワーノードに複製します。フォロワーはリーダーからの指示に従い、同じログを持つことで一貫性を保ちます。 ここは結構大事だけど、クライアントからデータを受け取るのはリーダだけです
安全性の確保： 特定の条件下でのみリーダーが選出されるようにし、ログのコミットが保証されることで、システムの安全性と一貫性を確保します。 例えば、フォロワーの過半数がログエントリを受け取った場合にのみ、そのエントリをコミットと見なします。 また、最新のログ状態を持っているサーバしかリーダになれないようになっています。
リーダーの失敗処理：リーダーが失敗した場合、残りのノードのうち一つが新しいリーダーとして選出されます。この選出プロセスは、タイムアウトと投票を用いて実現されます。
まとめるとこうです。
- Leader election
- Log replication
- safety
では、ここから詳細に写っていこうと思います。
前提知識
エージェント（各サーバの役割）
サーバは３つの状態のうちのどれか
- follower : completely passive. Does no action. But if he doesn’t get heart beat from leader he gets anxious and try to become a leader. He tries to . They expect to get heart beat from leader.
- candidate: Sends RequestVotes RPCs to get elected as leader.
- leader: Replicate its log to the followers. Heart beats to maintain its leadershop
If candidate or leader discovers higher terms RPC it gets back to follower.
新しい単語が出てきましたね。『Term』です。これもRaftを理解する上では大事な概念です。
Termについて
複数のサーバ間で合意形成を得るためにはobsolateな情報を見分ける必要がある。そのために使われるのがTermであるという話だ。\
e.g.,
前期のリーダの言うことは聞かなくていいぞ
1 Termにつき、一人のリーダしか存在し得ない。各タームはリーダの選出から始まる。そして、各サーバは現在のTermを覚えておくことができる。 これによって、前のタームのリーダからの指示を無視できる。今のタームのリーダからの指示のみを受け取ることができる。 全てのRPCでタームはやり取りされる。これは大事。リクエストにもタームは乗っかるし、レスポンスにもタームが乗っかる。 古いタームのメッセージは全て無視される。これはとても大事な概念です。ここは非常に大事なところ。 逆に、新しいタームのメッセージを受け取ったサーバはその瞬間にfollowerに転生する。
I know nothing I am stupid please teach me every thing... give me instruction oh load...
詳細（リーダの選出）
- リーダからのハートビートが入って時間届かなかった場合は、followerがcandidateに転生します。（各サーバはHPのようなものを持っていて、それは時間と共に減っていく。ハートビートが届くと回復する。0になるとcandidateに転生する）
- この時、自身のTerm をプラス１して、自分自身にリーダ権を投票します。
- さらに、他のサーバたちに投票を促します（RequestVotes RPC）。このRPCにもTermが含まれています。上で書いたように、
If candidate or leader discovers higher terms it gets back to follower. なので、自分持っているTermより高いTermを受け取った時点で皆フォロワーに戻ります。この時点でリーダへの投票が実行されます。 サーバの過半数以上の信任を得たサーバはリーダになります。 過半数の信任を得られないときは得られるまで他のサーバたちに投票を促します。 大事なのは、この間、ハートビートが続いていなときは、HPが減っていくということ。HPが0になると、新しいタームが始まってリーダのセレクションが始まります。 大事なのは、ある時間でcandidateが二人いたとしてもちゃんとリーダがちゃんと決まるということ。 また、candidateはリーダからRPCを受けた瞬間にフォロワーになります。これも大事なところ。
- 過半数の信任を得たcandidateはリーダに転生する。
これを使うことによって、1 Termに一人のサーバのみが選出されることが保障され、さらに必ずいつか誰かが選出されることも保障されている。ss
詳細（ログがレプリケーションされる流れ）
- クライアントがリーダにコマンドを送る（リクエスト）
- リーダが自分のストレージにコマンドをappendする
- リーダがフォロワーにAppendEntries RPCを送信する
- 新しいコマンドがコミットされたら、コミットされたコマンドをリーダが自分のノードで実行する。
- コマンドを実行したことをリーダはfollowerに告知する。AppendEntries RPCを使って
- アペンドが完了しないフォロワーにはしつこく、AppendEntries RPCを送りつけて、更新を促す
ではいつコミットされるのか？？そこが大事だ。コマンドがコミットされるのはいつだ？？
コマンドがコミットされるまで。ここが大事だ
そもそもコミットされるとはどういう状態なのか？ それは、そのコマンドをそのサーバ上で実行しても安全だという状態。 安全なのはどういう状態の時なのか？ それは、同じログポイントにおいて、他のノードが違うコマンドを実行する心配がないという状態。なるほど。 これはそうだ。まじでそうだね。 それはどういう状態なのか？？ 「If the entries has been replicated on majority of the servers by the leader of its term 」 ああ、だから、リーダのログレコード、１１０個あるうちの、例えば１００番目までが過半数のサーバにレプリケートされていると。 そうなると、１００番目まではコミットされている、つまり実行して安全、ということになるのだな。理解。 逆に、１１０まではクライアントからリクエスト来ているわけだけど、実行はできないわけだな？？そういう認識でいいかな？？まじで教えてくれ。
うん、リーダの指示は絶対です。さらに、リーダのログエントリーは必ず正という過程を置いています。なるほど。 最新のコミットまでのログは全部正しいとされる。だから、クラッシュが起きて、古い情報が入ったフォロワーが入ってきても最新のコミットまでは ログが同期される。
最も最新のログを持っているリーダが選ばれるようにするために
実は、リーダセレクションのパートで、一つ大事なことを飛ばしていた。 どのサーバがリーダに選出されるか、どこまでコミットされているかを各マシンは持っているわけです。 んで、candidateが俺に投票しろって入ったとき、ログのコミットインデックスも一緒に送ります。この時、受け取ったフォロワーが、自分のコミットインデックスの方が新しいときは、candidateからの投票リクエストに応じません。こうすることで分散システムは全体として最新の状態をキープし続けられます。というか、
質問
- クライアントからのリクエストはリーダにしか届かないのか？ リーダーがクライアントのリクエストを一元管理することで、システム全体の一貫性を保つためです。リーダーがすべてのリクエストを受け取り処理することで、ログエントリの順序やコミットの管理が一貫して行われます。
仕組み リーダーの選出：クライアントがシステムに接続する際、現在のリーダーを知っている必要があります。通常、クライアントはクラスタ内の任意のノードに問い合わせを行い、現在のリーダーの情報を得ます。 リクエストの送信：クライアントは得られたリーダーの情報を基に、リーダーに直接リクエストを送信します。 リーダーの処理：リーダーはクライアントから受け取ったリクエストをログに記録し、そのエントリを他のフォロワーノードにレプリケートします。過半数のフォロワーがログエントリを受け取った時点で、そのエントリをコミットします。 レスポンスの送信：リーダーはログエントリがコミットされた後、クライアントに対してリクエストの結果を返します。 フォールバックメカニズム リーダーの不在：もしクライアントがリーダーに接続できない場合、クライアントは再度クラスタ内の他のノードに問い合わせを行い、新しいリーダーの情報を取得します。 リーダーの変更：リーダーがクラスタ内で変更された場合、クライアントは新しいリーダーを再度検出し、そのリーダーにリクエストを送信するようにします。 このように、クライアントからのリクエストはリーダーに集中することで、分散システムの一貫性と信頼性を高めることができます。
raftを使った分散データベースでは、読み込み、書き込みはリーダのみに対して実行されるのですか？
分散データベースを使う事によるメリットは結局、なんですか？
1. 耐障害性（Fault Tolerance）
分散データベースは複数のノードにデータをレプリケートするため、一部のノードが故障してもデータ損失を防ぎ、システム全体が継続して動作できます。例えば、Raftアルゴリズムを使用することで、リーダーが故障しても新しいリーダーが選出され、システムの可用性を維持します。
2. 拡張性（Scalability）
分散データベースはノードを追加することで、水平スケーリングが可能です。データ量が増加したり、クライアントからのリクエストが増加した場合でも、新しいノードを追加することで対応できます。これにより、システムのパフォーマンスを維持しながら成長できます。
3. パフォーマンス（Performance）
データが複数のノードに分散されるため、読み込みリクエストを複数のノードに分散させることができます。これにより、読み込みのスループットが向上し、クライアントに対する応答時間が短縮されます。また、書き込みに関しても、適切なシャーディングやパーティショニングを行うことで、個々のノードの負荷を軽減し、全体的な書き込みパフォーマンスを向上させることができます。
4. データの局所性（Data Locality）
分散データベースは、地理的に分散したノードにデータを配置することができます。これにより、ユーザーに近いノードからデータを提供することで、レイテンシを低減し、ユーザー体験を向上させることができます。
5. 高可用性（High Availability）
分散データベースは複数のノードにデータをレプリケートするため、一部のノードがメンテナンス中や障害発生時でも、他のノードがサービスを提供し続けることができます。これにより、システムのダウンタイムを最小限に抑えることができます。
個人的にラフトすごいなって思ったのは、時間という概念が必要ないところかな。これはすごい。
- リーダがコロコロ変わり、クライアントがリーダに対してリクエストを発行する、ということは、クライアントは誰がサーバかを知っている必要がある。 しかしこれはおそらく、リダイレクトとかをすればいいのかな？どうやるんだろう。