分散システムの噂

[[259783]]

Redis、Cassandra、Amazon S3、BitTorrent などの有名なソフトウェアを使用したことがあるかもしれませんが、それらのすべてが基盤となる通信に Gossip と呼ばれるプロトコルを使用していることはご存じないかもしれません。

私はずっとゴシップについて書きたいと思っていましたが、適切な方法が見つかりませんでした。今日、このゴシップシミュレーター（クリックすると元のテキストが読めます）を見たとき、これを書く必要はないと分かったので、そのままコピーして皆さんに送りました。

始める前に、まず問題について話すのが私の習慣です。この問題により、このテクノロジーがどのような問題を解決しようとしているのかがわかります。

数千台のサーバーを持つクラスターがあるとします。ここで、クライアントがサーバー A 上のデータに変更を加えます。この変更をクラスター内のすべてのサーバーに迅速に伝播させたいとします。つまり、これらのサーバー上のデータの一貫性を保つ必要があります。あなたならどうしますか？

最も簡単な方法

顧客のデータ変更を安定したサーバー X に保存し、他のサーバー A、B、C、D などがサーバー X から定期的にデータを取得するのは問題ないのではないでしょうか。

しかし、分散型の場合には、少なくとも 2 つの問題があります。

1. サーバー X は非常に安定していますが、それでもクラッシュする可能性があります。一度クラッシュすると、システム全体が台無しになります。

サーバー X をバックアップし、そのデータをサーバー X1、X2、X3 などに同期することもできます。この方法では、サーバー X がクラッシュすることを心配する必要がありません。しかし、再び疑問が生じます。これらのサーバー X、X1、X2、X3 間でデータの一貫性を保つにはどうすればよいのでしょうか?

2. ネットワーク上の理由により (これは非常によくあることです)、サーバー H がサーバー X に接続できない場合、サーバー H が他のサーバーに接続できたとしても、データを取得することはできません。

これは分散システムにおける典型的な一貫性の問題です。科学者たちは、Paxos や Raft など、多くのアルゴリズムを開発してきました。今日はそのうちの 1 つ、ゴシッププロトコル (ゴシッププロトコルとも呼ばれる) を紹介します。このプロトコルは、ソーシャルネットワークでのゴシップの拡散に似ています。ネットワーク全体に急速に広がります。

ゴシップ

ゴシッププロトコルはどのように機能しますか?この写真を見てみましょう:

画像には 40 個のカラフルな円があり、これらは 40 個のノードを表しており、これらをサーバーと見なします。 [[259785]]

次に、データの変更が発生したノードを選択しました。

次に、図の緑の線で示されているように、このノードが認識している「隣接ノード」を表示できます。

太い線が 4 本ある場合、このノードは 4 つの隣接ノードをランダムに選択してメッセージを送信することを意味します。

4番はファンアウトと呼ばれる

次に、メッセージを送信できます。メッセージが送信された後、4 つのノードも赤に変わることに注意してください。これは、データの更新を受信したことを意味します。

ウイルス拡散の観点から見ると、4 つのノードが感染しました。

次に、すべての赤いノード (更新されたデータを持つ「感染した」ノード) は開始ノードの戦略に従い、データの変更を伝播するために、既知のノードから 4 つのノードをランダムに選択します。

その結果、より多くのノードが「感染」し、赤色に変わりました。

このサイクルが継続され、感染したノードは「ウイルス」（データの変更）をランダムに拡散し続け、すべてのノードが感染して一貫した状態に達します。

全体的なプロセスを示す GIF を以下に示します。ご興味がございましたら、クリックして原文を読んだり、ウェブサイトにアクセスして遊んでみたりしてください。とても興味深いですね。

ここで示されているのは 40 個のノードの状況です。 3 ラウンド後には、すべてのノードが感染し、データは一貫性を保っていることがわかります。

アドバンテージ

1. スケーラビリティ

ここに示した例は 40 ノードの場合です。 80 ノードの場合はどうなりますか?合意に達するまでに何回の伝達が必要でしょうか?

自分でプレイすることもできます。実際には、4 ラウンドしかかかりません。

理論的には、ゴシッププロトコルの複雑さは O(logN) です。毎回 4 つのノードが Fanout としてランダムに選択される場合:

40ノード: 2.66ラウンド

80ノード: 3.16ラウンド

120ノード: 3.45ラウンド

....

ゴシッププロトコルはノードの増加に対処するのに非常に効果的であることがわかります。

2. フォールトトレランス

ノードAとノードBの間に接続があり、AはBにメッセージを送信できると仮定します。A-> B

ある日突然、ネットワークの問題により、A は B に接続できなくなり、メッセージを送信できなくなりました。どうすればいいですか？

心配しないでください。C->Bなど、別のパスから送信する別のノードが常に存在します。

これは次のアニメーション図でより明確にわかります。 2 つのメッセージ送信パスを削除しましたが、対応するノードは他のチャネルを介してメッセージを受信しました。

3. 収束の一貫性

ゴシッププロトコルでは、1 人が 10 人に伝え、10 人が 100 人に伝えるというように、指数関数的に速く情報が拡散します。メッセージが到着すると、ネットワーク全体に急速に広まります。システムステータスの不一致は、非常に短い時間で収束する可能性があります。メッセージの伝播速度はlog(N)です。

4. 極端な分散化

Gossip プロトコルでは、中央のキーノードは必要ありません。すべてのノードはピアツーピアにすることができます。どのノードもネットワーク全体の状態を知る必要はありません。ネットワークが接続されている限り、どのノードもメッセージをネットワーク全体に広めることができます。

その他の通信モード

このシミュレーターは、1 つの通信モード（プッシュ）のみを表示します。これは、1 つのノードがデータを他のノードにプッシュすることを意味します。

プル方式もあります。ノード A が他のノードにローカルデータのバージョンを伝え、他のノードが A よりも新しいデータをノード A に送信し、A がデータを更新します。

もちろん、プッシュプルの組み合わせも可能です。

欠点

タダ飯というものは存在せず、ゴシッププロトコルには弱点があります。

メッセージが遅れています

ゴシッププロトコルは急速に広がりますが、ネットワーク全体のすべてのノードに到達するには、数回の伝播が必要であり、リアルタイム要件が高いシナリオには適していません。言い換えれば、ゴシッププロトコルは結果整合性のみを実現できます。

メッセージは冗長です

アニメーションから、特に後のラウンドでほとんどのノードがメッセージを受信しているものの、送信するノードを継続的に選択している場合、メッセージの送信が冗長であることが明確にわかります。メッセージ数は圧巻と言えるでしょう。