分散型 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 関数にあります。ノードの選挙タイムアウトが到来したかどうかを判断する必要があります。もしそうなら、選挙を開始する必要があります。

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