クラウド ネイティブ Etcd シリーズ: クォーラムと投票

[[438630]]

この記事はWeChatの公開アカウント「Qiya Cloud Storage」から転載したもので、著者はQiyaです。この記事を転載する場合は、Qiya Cloud Storage 公式アカウントまでご連絡ください。

クォーラムの2つの側面

前回の記事では、さまざまなフレームワークやデザインのアイデアについてお話ししました。今日はちょっとしたポイントを共有したいと思います。etcd のクォーラムはどのように実装されているのでしょうか?

クォーラム メカニズムの本質は多数決にあり、これには 2 つの側面があります。

• 選挙プロセス: ノード投票の過半数を獲得したノードが勝利し、リーダーになります。
• 実行中のプロセス: 大多数のノードによってコミットされたログの場所は、クラスターによって確実に記録される場所です。クラスターによってコミットされたログのみを適用できます。

そこで、考えるべき 2 つの小さな質問があります。

選挙ですので、選挙結果はどのように発表されるのでしょうか？

実行中のプロセスなので、クラスター内のこれらのノードはクラスターのコミット位置をどのように確認するのでしょうか?

選挙があるところには投票がある

投票を数えることは選挙プロセスにおけるステップです。クラスのリーダーを選ぶとき、黒板に「正」という言葉を書き、最も多くの票を獲得した人が選ばれることを今でも覚えています。

etcd にはリーダー選挙と呼ばれる選挙もあります。リーダーが勝利するための基準は、その投票が過半数を満たすこと、つまり定足数メカニズムを満たすことです。

今日は、etcd の投票カウントの仕組みを見てみましょう。

それは非常にシンプルなアイデアです。私たちは選挙に参加するすべての友人の投票を数えます。投票の半分以上を獲得した人が勝者となります。

たとえば、A、B、C、D、E の 5 人が選挙に立候補した場合、3 票を獲得した人が勝利します。

etcdの投票数を見てみましょう

選挙はクォーラム メカニズムに属し、コードは etcd/raft/quorum/ にあります。クォーラムのコア実装は MajorityConfig 構造にあり、これは実際にはマップのカプセル化です。

タイプ MajorityConfig map[uint64]struct{}

このマップのキーは、クラスターのノードを含むノード ID です。マップの値は重要ではなく、struct{} 型が使用されます。

質問させてください。値は気にしないのであれば、なぜスライス構造を使用しないのですか?

実際のところ、それは単に検索の必要性のためです。マップの検索は一定レベルで行われ、値は struct{} を使用するため、スペースを占有せず、一石二鳥です。

 // etcd/raft/quorum/majority.go
 func (c MajorityConfig) VoteResult(votes map[uint64]bool) VoteResult {
    // 長さ2の配列を作成する
    ny := [2] int {}
    // クラスターノードを走査する
id := 範囲 c {
        v、ok := 投票[id]
        !okの場合{
            // まだ投票はありません
            不足++
続く 
        }
        もしv{
            // 賛成票を投じた
            ny[1]++
        }それ以外{
            //拒否に投票
            ny[0]++
        }
    }
    q := len(c)/2 + 1
    ny[1] >= qの場合{
        // 選挙成功: 投票の半数以上、たとえば、投票 => [はい、はい、はい]
戻るVoteWon
    }
    ny[1]+欠損値 >= q {
        // 不明な状況: 成功か失敗か不明
投票保留中を返す
    }
    // 選挙に失敗しました
戻るVoteLost
 }

投票集計の実装は非常に簡単で、次の手順に従ってください。

• クラスター ノードをトラバースします。
• 誰が賛成したか、誰が反対したか、まだ投票していないかを数えます。
• 投票集計の結果には、成功、失敗、保留の 3 種類があります。
• 投票の半分以上（len(c)/2+1）が同意した場合、候補者が勝利します。

この実装は非常にシンプルです。投票結果を横断して「肯定的」という単語を書き込むだけです。 「ポジティブ」という単語が半分を超えたら勝ちです。

クラスター ノードはクラスターのコミット場所をどのように確認しますか?

クラスター内の大多数のノードによってコミットされた場所が、クラスターのコミット ポイントです。つまり、これも定足数を満たす必要があります。これは面白いですね。

重要な手順: 並べ替えてから、中央の位置を取ります。

中央の位置は、クォーラムを満たすコミットです。

 // etcd/raft/quorum/majority.go
 func (c MajorityConfig) CommittedIndex(l AckedIndexer)インデックス{
    // クラスターノードを走査し、各ノードのコミットを取得します 
 id := 範囲 c {
        idxの場合、ok:=l.AckedIndex(id);わかりました {
            srt[i] = uint64(idx)
            私  -  
        }
    }
    // 並べ替え
    挿入ソート(srt) 
 
    // 最も多くのコミットが行われ、クラスターのコンセンサスとなっている中間の位置を取る
    正数 := n - (n/2 + 1)
戻る インデックス(srt[pos])
 }

この実装は非常に興味深いです。各ノードの現在のコミット位置を取り出し、配列を形成し、配列をソートして中央の位置を取得します。この場所はクラスターのコミット場所であり、適用場所でもあります。

まず、次のようにして、クラスター内の各ノードのコミット位置を取得します。

その後、順序は次のようになり、ブラック ノードのコミット位置はクラスターのコミット位置になります。

要約する

クォーラム メカニズムは、分散システムの非常に重要な理論的な部分です。それは多数派に関する仕組みです。 etcd には多数決に関して、リーダー選出とラフト ログ操作という 2 つの側面があります。

etcd の投票の実装は非常にシンプルです。それは単なるカウントの実装です。マップはクラスター内のノードを記録するために使用されます。過半数の票を獲得したノードが勝利します。

etcd は、まず各ノードのコミット位置を配列に入れて並べ替え、次に中央の位置、つまりクラスターのコミット位置を取得することで、クラスターのコミット位置を確認します。

ほとんどのノードによってコミットされたログはクラスターコミットの場所であり、クラスターによってコミットされたログのみを適用できます。これを覚えておいてください。

クラスターのコミット位置は、ハートビートまたはログレプリケーションメッセージを通じてリーダーから他のノードに通知されます。