分散型 Kv-2 ラフトリーダー選出の実装

分散型 Kv-2 ラフトリーダー選出の実装

[[441163]]

この記事から、raft をベースに分散 KV を構築していきます。

Raft は、分散システム内の各ノードのデータの一貫性を主に保証する分散一貫性アルゴリズムです。ラフト アルゴリズムは、それが解決する分散一貫性問題が本質的に難しい問題であるため、比較的複雑です。ラフト アルゴリズムの実装は、次の 3 つの部分に分けられます。

  • リーダー選挙
  • ログのレプリケーション
  • 安全

ラフト アルゴリズムに詳しくない場合は、次の Web サイトでアニメーションを視聴できます。

http://thesecretlivesofdata.com/raft

ラフト アルゴリズムが直面する問題と、ラフト アルゴリズムが問題を解決する基本的なプロセスを鮮明に示します。

もちろん、ラフトアルゴリズムに関する論文も参照する価値があります。

https://github.com/maemual/raft-zh_cn

また、インターネット上でラフト アルゴリズムに関する優れた一連の記事も見つけました。

https://www.codedump.info/post/20180921-raft

https://blog.betacat.io/post/raft-implementation-in-etcd

これらの資料を読んだ後、ラフト アルゴリズムの概要を理解し、それを具体的に実装する方法がわかるようになります。

この記事では、TinyKV のプロジェクト 2aa に対応する最初のリーダー選出問題のみを紹介します。

ラフト クラスターでは、ノードはフォロワー、候補、リーダーの 3 つの状態に分かれています。ノードの初期状態はフォロワーです。

フォロワー ノードは、自身のステータスを維持するために、リーダーのハートビート情報を定期的に取得する必要があります。 Follower ノードにはタイムアウト (ElectionTimeout) があります。この期間中にリーダーからハートビート メッセージを受信しない場合、クラスター内にリーダーが存在しないものと見なし、選出を開始します。

選挙の具体的な手順:

上図に示すように、ノード A の選挙タイムアウトが最初に到来するため、ノード A はステータスを候補に変更し、任期数を 1 増やします (図の初期任期数は 0 で、追加後は 1 になります)。その後、ノード A 自身に投票し、ノード B と C に投票要求メッセージを送信します。

ノード B と C は、自分の用語数が A より小さいことに気付くため、A に承認票を投じます。応答を受信した後、ノード A は投票数がノード数の半分を超えているかどうかを計算します。そうであれば、それがリーダーになります。

上記はリーダー選挙の最も理想的な状況を説明しています。厳密に言えば、候補ノードが選挙を開始した後、次のいずれかの状況が発生するまでステータスを維持する必要があります。

  • 選挙自体に勝利した
  • 他のノードが選挙に勝利した
  • 選挙のタイムアウトが到来し、どのノードもリーダーになれない

最初のケースは、上で説明した選挙プロセスです。自ら選挙を開始し、半数以上のノードの投票を獲得すると、リーダーになります。

2 番目のケースでは、選挙プロセス中に別のノードが候補になり選挙に勝利した場合、そのノードは新しいリーダーから AppendEntry RPC メッセージを受信し、新しいリーダーの任期数が自身の任期数より大きい場合、そのリーダーを有効と見なし、自身をフォロワーに変更します。

3 番目のケースは、選挙で負けることも勝つこともないノードに対応します。これは、クラスター ノードの数が偶数で、2 つのノードが同時に選出を開始した場合に発生する可能性があり、その場合、選出は無効になります。選挙のタイムアウトが再び到来し、まだ新しいリーダーがいない場合は、候補者が新たな選挙ラウンドを開始します。

具体的なコード実装については、まず、初期ロジックは外側のレイヤーによって呼び出される tick 関数にあります。ノードの選挙タイムアウトが到来したかどうかを判断する必要があります。もしそうなら、選挙を開始する必要があります。

  1. // tick は内部論理クロック1 ティック進めます。
  2. func (r *Raft) tick() {
  3. // ここにコードを記述します (2A)。
  4. スイッチr.State{
  5. ケースStateLeader:
  6. // ...
  7. StateFollower、StateCandidateの場合:
  8. r.electionElapsed++ 選挙経過日数
  9. r.electionElapsed >= r.electionTimeout の場合 {
  10. // 新しい選挙を開始する
  11. r.startElection()
  12. }
  13. }
  14. }

選挙を開始し、自分自身を候補者(任期番号 + 1)に変更し、自分自身に投票します。次に、他のノードに MsgRequestVote メッセージを送信する必要があります。

MsgRequestVote メッセージには、現在のノードの最後のログのインデックスと用語を含める必要があります。これにより、フォロワーはノードのログが最新であるかどうかを判断できます。

MsgRequestVote メッセージを受信すると、他の Follower ノードが処理を開始します。処理時に注意すべき点がいくつかあります。

  • メッセージの期間数が自身の期間より小さい場合は、メッセージを直接拒否します。
  • メッセージの期間が自分の期間よりも長い場合は、フォロワーに変更して(フォロワーでない場合)、期間を更新する必要があります。
  • メッセージの用語番号とインデックス番号をチェックする必要があります。メッセージのログが最新でない場合は、メッセージを拒否します。

すべてのチェックに合格すると、フォロワー ノードは賛成票を投じ、候補ノードに MsgRequestVoteResponse メッセージを送信します。

MsgRequestVoteResponse メッセージを受信した後、候補者ノードは投票結果を記録し、投票が次の条件を満たすかどうかを計算する必要があります。

  • 拒否票の数がノード数の 1/2 を超えると、選出は失敗し、候補ノードはフォロワー状態に変わります。
  • 賛成票数がノード数の半分を超えると、選挙は成功します。

選出が成功した場合、自身のステータスをリーダーに変更し、他のノードが引き続き選出を開始するのを防ぐために、空のデータ エントリを含む MsgAppend メッセージを他のノードに送信する必要があります。

追伸具体的なコード実装については、etcd の raft を参照し、それに基づいて TinyKV に手動でコードを実装してください。

<<:  「チャイナクラウド」は世界一?もっと深く掘り下げてください!

>>:  クラウドコスト管理だけではクラウド支出の問題を解決できない理由

推薦する

Debian/Ubuntu で MySQL のルート パスワードをリセットする

MySQL パスワードをバックアップして記録するのも面倒な人が時々います。そんな人はいるのでしょうか...

Ku6の収益成長は弱く、同社は打開策を見つけるために二流のビデオネットワークへの転換を試みている。

最近、百度の子会社であるiQiyiがPPSを買収するという噂が出回っている。実際、YoukuとTud...

ローカル人材ウェブサイトのコア競争力の欠如という現象を打破する方法

地元の人材ウェブサイトは、雇用や採用を促進するための優れた基盤を築いてきましたが、雇用圧力が高まるに...

Baiduはネットワーク全体の外部リンク検索ツールを立ち上げる予定

少し前に、Baidu Webmaster Platform が外部リンク検索機能を開始しました!現在...

海外インフルエンサーマーケティングが越境電子商取引に与える影響を段階的に分析

海外セレブのマーケティングが過去2年間で急成長していることは特筆に値します。越境EC企業はジレンマに...

買収当初、Vancl はどのようにして大規模 e コマースの夢を実現すべきでしょうか?

かつては多額の資金を浪費していたヴァンクルは、IPOの失敗、資金繰りの悪化、市場の過小評価など一連の...

JD.com の 3 段階分類ページの SEO、ユーザー エクスペリエンス、マーケティング手法の簡単な分析 (パート 1)

今日は、「家電」ページを例に、JD.com の 3 階層のカテゴリ ページを見てみましょう。まず頭を...

低価格がなければ、Viya と Li Jiaqi はどうやってユーザーを維持するのでしょうか?

Eコマースのライブストリーミングに新たな「ルーチン」が誕生しました。ライブストリーミングルームが依然...

クラウドコンピューティングの主なセキュリティリスク

クラウド コンピューティングは新しいものではありません。スケーラビリティ、アクセス性、信頼性などの明...

あなたの性格はSEOに適していますか?

今日は、Yiyun がパーソナリティと SEO の関係についてお話しします。 SEOマーケティングの...

ニュース: Ramnode が 128M メモリ搭載の VPS の販売を停止

Ramnode からの最新の公式ニュース: IPv4 リソースが枯渇しつつあることを考慮して、Ram...

成功を達成するには、タオバオストアを開設する戦略的認識が明確でなければなりません

タオバオに店を開くことは、今でも多くの若者がオンラインで自分のビジネスを始めるために選ぶ方法です。『...

ハイブリッドクラウドデータバックアップ

バックアップにハイブリッド クラウドを使用すると、組織はオンプレミス展開の制御を損なうことなく、クラ...

BudgetVMのVPS製品価格表の全範囲、budgetvmはAlipayをサポート

ENZU は 2007 年に設立され、4 つのデータ センターを構築し、有名な格安 VPS ブランド...

ソフト記事マーケティングのスキルと計画

ソフトコンテンツマーケティングは、最も一般的で効果的なマーケティング手法です。このマーケティング モ...