分散型コンセンサスアルゴリズム: 想像以上に複雑

1. 分散システムの難しさ

張大鵬は難しい問題に遭遇した。

彼らの会社には貴重なデータを保存するサーバーがあります。クラッシュを防ぐために、リーダーのビルはチャン・ダパンにデータをバックアップする方法を見つけるように依頼します。

Zhang Dapang 氏は抽象的能力を駆使して、頭の中に次のようなイメージを描きました。このユニークなマシンはノードになることができます。

可用性を向上させるには、複数のマシンを追加し、それらをローカル エリア ネットワーク経由で接続して分散システムを形成できます。

データのコピーを各ノードに保存すればもっと安全ではないでしょうか?

しかし、張大鵬はすぐにこれが簡単な仕事ではないことに気づきました。たとえば、各ノードには残高が 100 元のアカウントが保存されます。今、誰かがノード A を通じてアカウントに 20 元を追加し、別の誰かがノード B を通じてアカウントから 30 元を減額しました。

現在の残高はいくらですか？

一貫性を維持するために、ノード A は「残高プラス 20」などのメッセージを B と C に送信し、ノード B は「残高マイナス 30」などのメッセージを A と C に送信する必要があります。ネットワークに問題がある場合、メッセージが他のノードに送信されない場合、またはノードが単に壊れている場合、データの一貫性が失われる可能性が非常に高くなります。

ユーザーがこの一貫性のないシステムで操作を続けると、すぐに混乱に陥ることになります。

2. 誰がボスになるでしょうか?

張大鵬は長い間考えた末、このような無秩序な行動はできないと感じた。彼は、これら 3 つのノードの「ボス」を見つける必要がありました。

すべての操作は「ボス」を通じて実行され、ボスは各「弟」にメッセージを送信します。

しかし、誰がボスになるのでしょうか? また、このボスが死んだらどうなるのでしょうか?

手動で調整できます。たとえば、ノード A に障害が発生した場合、手動でノード B を「ボス」にし、ノード C を「弟」にすることができます。

しかし、これはちょっと面倒です。自動的に実行できますか?

この質問はとても興味深いものでした。張大鵬はこれに魅了され、深く考え続けました。選挙の仕組みを作り、彼らにその地位を競わせよう。

最初は、各ノードが候補者であり、他のノードに投票招待状を送信して全員が投票できるようにします。過半数の票を獲得すれば「ボス」になれる。

全員が同時に投票招待を開始するのを避けるために、各ノードにランダムな「選挙タイムアウト」を割り当てることができます。平たく言えば、それは待ち時間です。この期間中、ノードは辛抱強く待機する必要があります。この期間が経過して初めて、その地位を競い合い、ボスになることができます。

各ノードには 0 から始まるタイマーがあります。待機時間が終了したノードが選挙の開始を主導し、他のノードに呼びかけて自分がボスになるための投票を依頼します。

たとえば、ノード A は 170 ミリ秒待機し、ノード B は 200 ミリ秒待機し、ノード C は 250 ミリ秒待機します。

ノード A の待機時間が最も短いため、最初にそこに到達します。まず、初期値が 0 の整数である自身の項 (Term) を増やします。次に、自身に投票し、ノード B とノード C を呼び出して、自身に投票するよう依頼します。

ノード B とノード C は投票要求を受信します。選挙を開始していない場合（待機時間が経過していない場合）、ノード A がリーダーになることに同意する必要があります。同時に、各自のタイマーをリセットし、再び 0 からカウントを開始する必要があります。つまり、新たな待機ラウンドが開始されることになります。

ノード A は、他の 2 つのノードが同意し、投票数が半分を超える 3 になったことを学習し、リーダーになれることを認識します。

ノード A がリーダーになると、ノード B と C に定期的にメッセージを送信し始めます。メッセージを受信した後、B と C はハートビートを維持するために応答する必要があります。

B と C はハートビート メッセージを受信するたびに、自身のタイマーをリセットし、再び 0 からカウントを開始する必要があります。

このとき、ノード B とノード C は「弟」になります。

残念ながらノード A が切断し、ノード B とノード C が待機時間内にハートビート メッセージを受信できない場合、2 つのノードは再び位置を競うことになります。

上の図では、ノード C が主導権を握り、最初に選挙投票を開始しました。

ノード B は一歩遅れて、しぶしぶノード C をサポートすることに同意しました。ノード C はサポートの半分以上を獲得して「ボス」となり、ノード B は「弟」となりました。

(ノード B とノード C が同時に選挙投票を開始し、各ノードの投票数は 1 で、半分を超えることはできません。どうすればよいでしょうか? 非常に簡単です。別の選挙投票ラウンドを開始するだけです。もちろん、B と C が同時に選挙投票を開始してループに陥るのを防ぐために、ランダムな待機時間をリセットする必要があります。)

多数決は重要であり、この方法でのみ「ボス」ノードの一意性が保証されると張大鵬氏は考えています。

各ノードの処理フローは実際には非常にシンプルです。

3. データの複製

多大な努力の末、張大鵬氏はついに分散システムで「ボス」ノードを自動的に選択する方法を解明しました。

次のステップは、「ボス」に送信されたデータを「弟」のノードにコピーする方法を見つけることです。何をするか？

分散されているため、ほとんどのノードが正常に保存された場合にのみ、データが正常に保存されます。

したがって、「ボス」ノードが調整の責任を負う必要があります。

Zhang Dapang は、ログを複製する方法を考え出しました。各ノードにはログ キューがあります。

実際のデータを送信する前に、データをログ キューに追加し、それを「弟分」にコピーします。

1. クライアントはノード A (「ボス」) にデータを送信します。

ノード A は最初にデータをログに記録します。これは、この時点では「コミットされていない状態」であることを意味します。

2. 次のハートビート メッセージでは、データが各「弟」に送信されます。

3. 各「弟」もログにデータを記録し（これもコミットされていない状態で）、ログを記録したことを「ボス」に報告します。

4. ノード A が応答の半分以上を受信した場合、ノード A はデータを送信し、データが正常に保存されたことをクライアントに通知します。

5. ノード A は、次のハートビート メッセージでデータが送信されたことを各「弟」に通知します。それぞれの「弟」も自分のデータを提出しました。

不幸にして「弟」が死んでしまった場合、「兄」は連絡を取ろうとし続けます。再び動作を開始すると、「ビッグ ブラザー」との一貫性を保つために、「ビッグ ブラザー」からデータをコピーする必要があります。

4.ラフト

張大鵬はこの予備設計に非常に満足したので、リーダーのビルに検討を依頼しました。

ビルはそれを読んだ後、笑ってこう言いました。「君は実は一貫性アルゴリズムに取り組んでいるんだ。簡単に言えば、マシンのグループが全体として動作し、一部が故障しても動作し続けることを可能にするものだ。」

「その通り、リーダーの要約は非常に正確です。」太っちょ張は喜んだ。

「しかし」とビルは話題を変えました。「あなたが設計したログ レプリケーションにはまだ多くの抜け穴があります。設計には合計 5 つのステップがあることがわかりました。この 5 つのステップ中に「ボス」ノード A がクラッシュしたらどうなるでしょうか。データの一貫性が失われるでしょうか。」

「これは…」張太っちょは、本当によく考えていませんでした。彼は、カートを引くことに集中するあまり、道路を見上げることを忘れ、分散環境の複雑な問題を無視してしまったことを密かに後悔していた。

「しかし、君はよくやったよ」とリーダーはすぐに励ましました。 「あなたが設計したシステムは、実はRAFTアルゴリズムと非常によく似ています。」

"ラフト？"

「はい、RAFT は分散コンセンサス アルゴリズムです。複雑で理解しにくい Paxos と比較すると、RAFT は理解しやすさと実現可能性の点で大きな改善が図られています。ここでの「ボス」は RAFT アルゴリズムのリーダーと呼ばれ、「弟」はフォロワーと呼ばれます。ただし、ログのレプリケーションとデータの一貫性を確保する方法については、非常に詳細な規定があります。」

張大鵬氏は、既成のアルゴリズムがあると聞いて、すぐに喜びました。「素晴らしい！配布問題は他の人によって解決されています。私も実装します。」

【この記事は51CTOコラムニスト「Liu Xin」によるオリジナル記事です。転載する場合は著者のWeChat公開アカウントcoderisingを通じて許可を得てください]

この著者の他の記事を読むにはここをクリックしてください