何十億ものコンピューターが毎日互いに通信している中で、それらはどのようにして何かを決定しているのでしょうか? データベースまたはサーバーの配置であっても、データベースを構成するさまざまなコンピューターは、コミットされた値をどのように判断するのでしょうか? 彼らは今何時にどのように同意しますか? 彼らはどのようにしてコンセンサスに達するのでしょうか?
しかし、最初に、コンピューターのコンテキストにおけるコンセンサスの概念は何ですか? 要するに、関係するすべてのエージェントが単一の値に同意することです。 ただし、プロトコルには、異議を唱えるエージェント、不正確なエージェント、または過失を犯すエージェントの許容範囲が設計されています。 すべての正しいエージェントは答える必要があり、すべての正しいエージェントは同じ答えを持つ必要があります。 これは、データセンターやメッシュ ネットワークでは特に重要です。 ネットワークが分断されたり、一部のノードがオフラインになったり、ソフトウェアが奇妙にクラッシュして奇妙なデータが送信されたりするとどうなりますか? 最も一般的なコンセンサス アルゴリズムの XNUMX つは Raft です。
Raft
Secret Lives Of Data には、 エージェント間の Raft アルゴリズム内でデータがどのように流れるかを示す素晴らしいアニメーション デモンストレーション. Raft GitHub ページも 役立つ図があります. Raft には、選出されたリーダーによるフォールト トレランスを提供する証明可能な保証があります。 重要なことに、この選出されたリーダーは、ビザンチンの失敗の弱点につながりますが、それについては後で説明します. Cockroach DB、Splunk、MongoDB などのデータベースでは Raft がよく使用されます。Raft は、データベースへのトランザクションなど、エージェントが一連の状態遷移に同意できるように特に調整されています。 Raft アルゴリズムを要約すると、リーダーの選出とログの複製という XNUMX つの部分があります。
相互に通信する一連のサーバーと、メッセージを生成するクライアントを想像してください。 これらのメッセージは、「レジスタ Y を 6 に設定」や「id = 1230231 の行を削除」など、何でもかまいません。 サーバーが最初に起動したとき、サーバーはフォロワー状態にあり、ハートビートを介してリーダーからの連絡を待ちます。 150 ～ 300 ミリ秒以内にハートビートを受信しない場合、候補者になろうとします。 その後、サーバーは候補者に投票し、投票が分かれた場合は選挙期間が終了し、サイクルが再び開始されます。 タイムアウトはランダム化され、投票の分割を防止しようとします。
クライアントが現在のリーダーにメッセージを送信すると、リーダーはそのメッセージをすべてのフォロワーに複製します。 フォロワーの大多数から返信があると、メッセージはコミットされたと見なされます。 メッセージはログに追加され、すべてのサーバーで一貫性が保たれます。 リーダーに障害が発生した場合、新しく選出されたリーダーのログが使用され、矛盾したエントリは削除されます。 フォロワーは、最新のコミットされたログを持っている必要があるため、過半数にコミットされたデータが失われることはありません。
ビザンチンの失敗
前述のように、Raft/Paxos はサーバー障害から保護しますが、 ビザンチンの失敗. この名前は、一部の将軍が信頼できないという有名なビザンチン将軍問題に由来しています。 彼らはあることを言いますが、別のことをします。 Raft は、システムがクラッシュすると失敗して再起動すると想定しています。 これはハードウェアの意味では当てはまりません。デバイスが一貫性のないデータを生成し続けたり、誤った動作をしたり、敵対的なエンティティに乗っ取られたりする可能性があるからです。
それにもかかわらず、飛行機や宇宙船などの多くのリアルタイム システムでは、ビザンチン障害を念頭に置いておく必要があります。 コンポーネントは誤ったデータを生成する可能性があり、残りのシステムはそれを回避する必要があります。 これは、他のサーバーのアクションを検証するための追加のメッセージ、データへの署名、さらには取得によって行うことができます。 リーダーの考えを完全に取り除く.
ロックステップ プロトコル
リアルタイム ストラテジー ゲームをプレイしたことがある場合は、接続が非常に遅い数十人のプレイヤー間でゲームがどのように一貫しているのか疑問に思うかもしれません。 残念ながら、Age of Empires のネットワークは、1996 モデムが比較的標準的だった 28.8 年に開発されました。 では、ネットワーク レイテンシの変動が激しく、毎秒数ビットの余裕がある場合、画面上のすべてのオブジェクトの位置と更新をシリアル化するにはどうすればよいでしょうか? 答えは、そうではないということです。
素晴らしいがあります 1500 人の射手をリアルタイムで実行することに関する記事 エイジ オブ エンパイア (とりわけ) に取り組んだ [ポール ベトナー] から。 答えは、ゲーム内の各オブジェクトの状態ではなく、プレイヤーのアクションのみを送信することです。 各ゲームはまったく同じシミュレーションを実行し、各プレーヤーのコマンドはすべてのプレーヤーのコンピューターでシミュレートされます。 多くの点で、これは Raft プロトコルと同じです。メッセージは読み取り専用のログに渡されて追加され、ログは常にすべてのコンピューターで一貫している必要があります。 しかし、Raft とは異なり、リーダーはなく、すべてのサーバーはクライアントでもあります。 ホストはいますが、ゲームの状態に関する真の権威はありません。
すべてのクライアントで一貫した単調なターン数があります。 各コマンドは XNUMX ターンで実行されるようにスケジュールされています。 これにより、ゲームのシミュレーション中にコマンドを送信、確認、および処理できます。 これは、シミュレーションが最も遅いマシンと同じ速度でしか実行できないことを意味し、ゲームをプレイ可能に保つためにターンの長さを変更するスピードコントローラーがあります. レンダリング時間をターン時間から分離することで、ターン レートが比較的低くても、プレイヤーにとってゲームプレイは非常にスムーズに保たれます。
各クライアントが同じシミュレーションを実行するため、ごまかすのは困難です (再びビザンチン問題)。 紛らわしいメッセージや無意味なメッセージを送信するクライアントは、非同期化され、ゲームから追い出されました。 ただし、お考えかもしれませんが、ランダム性と確率を備えたシミュレーションを、プロセッサが異なり、場合によってはアーキテクチャが異なる可能性のある数十台のマシン間で一貫させることは、控えめに言っても困難です。
暗号資産
ここハッカデーでは、私たちは集中する傾向があります ビットコインの実際の採掘側、しかし、ネットワークはどのようにして次のハッシュに同意するのでしょうか? それがプルーフ・オブ・ワークの真の力です。 これは、大規模な分散型コンセンサス アルゴリズムであり、悪意のある人物の大部分に対応できます。 詳細については触れません (別の機会に記事を書くかもしれません)。 結局のところ、それがブロックチェーンの唯一の力であり、それに付随するすべての誇大宣伝です。 これは、分散化された方法で全員が同意できるエントリのログにすぎません。 チアは別の暗号通貨です これは同様の原則に基づいて機能しますが、プルーフ オブ ワークの代わりにプルーフ オブ ステークを使用しますが、コアには同じ概念があります。
コンセンサスはどこにでもあります
コンセンサスは、飛行機から Web サービス、仮想通貨に至るまで、いたるところにあります。 その結果、何百ものコンセンサス アルゴリズムがあり、それぞれに異なるトレードオフとパフォーマンス プロファイルがあります。 次回、共通の価値観に同意する必要がある多くのノードを含むメッシュ スケールの IOT プロジェクトを実装する場合は、ここでいくつかのアイデアを得ることができます。
- コインスマート。 ヨーロッパで最高のビットコインと暗号通貨取引所。ここをクリック
- Platoblockchain。 Web3メタバースインテリジェンス。 知識の増幅。 こちらからアクセスしてください。
- 情報源： https://hackaday.com/2022/11/30/building-your-own-consensus/
