分散システムの噂

分散システムの噂

[[259783]]

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

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

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

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

[[259785]]

最も簡単な方法

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

[[259785]]

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

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

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

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

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

ゴシップ

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

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

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

[[259785]]

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

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

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

[[259785]]

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

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

[[259785]]

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

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

[[259785]]

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

[[259785]]

全体的なプロセスを示す 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 がデータを更新します。

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

欠点

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

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

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

メッセージは冗長です

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

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

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

<<:  アジア太平洋クラウドコンピューティング市場レポート:テンセントがトップ5にランクイン、市場シェアが初めてグーグルを上回る

>>:  Sangfor クラウド コンピューティングが再開: 同じアーキテクチャのハイパーコンバージド ハイブリッド クラウド

推薦する

justvps: 月額 1.54 ドルから利用可能な英国の VPS、1G メモリ/1 コア/20g NVMe/300M 帯域幅/無制限トラフィック

justvps.pro は、今から 1 月 20 日まで、英国ロンドン データ センターの VPS ...

DevOpsのボトルネックを克服するための4つのステップについてお話ししましょう

挑戦的なビデオ ゲームでレベルアップするために必要な手順は、DevOps の旅でレベルアップするため...

今後O2Oをどのように楽しんでいくのでしょうか?

先週末、私は北京でメディア専門家のグループと座り込み、主要なインターネットの出来事について話し合いま...

マイクロソフトのタブレット戦略は明確:モバイルオフィスがマーケティングのハイライトに

マイクロソフトの創業者ビル・ゲイツが、IT技術の現在の発展と応用の傾向は、伝統的なPCをタブレットコ...

Alibaba ビッグデータ クラウドネイティブプラクティス、EMR Spark on ACK 製品紹介

1. クラウドネイティブの課題とAlibabaの実践ビッグデータ技術開発動向クラウドネイティブの課題...

SEO スタッフ: バックリンクと外部リンクの違いをどのように解釈すればよいでしょうか?

2018年最もホットなプロジェクト:テレマーケティングロボットがあなたの参加を待っていますSEO 初...

SEOキーワードマイニング

ウェブサイトのプロモーションや検索エンジン最適化 (SEO) を行う場合、キーワードの選択は非常に重...

3つの大きな動きがeLong.comに大きな打撃を与え、行き詰まりに近づいている

eLongの2013年度の財務報告は芳しいものではなかった。純損失は1億6800万元で、2009年に...

WeChatがMomentsを再編しています。Momentsでどのようにマーケティングを実施すればよいでしょうか?

今回ついにWeChatが行動を起こしました!そして今回はその激しさがさらに増しています!これまでWe...

#おすすめ# shockhosting: $7.49、大容量ハードディスクVPS、KVM、1Gメモリ、1Tハードディスク、Alipay/WeChat

shockhosting は、大容量ハードドライブ VPS、ハードドライブ RAID10、KVM 仮...

gigsgigscloudはどうですか?シンガポール simplecloud シリーズ VPS クラウド サーバーのレビュー

gigsgigscloud は昨日、まったく新しいシンガポール VPS とシンガポール クラウド サ...

個人ウェブサイトのコンテンツ素材のソース問題を解決する方法

ウェブサイトの最適化にしろ、ウェブサイトの運用にしろ、高品質なコンテンツは欠かせない最優先事項です。...

AWS 対 Azure 対 Google: クラウド コンピューティングの選択肢として最適なのはどれでしょうか?

今日のインターネットは成長と発展を続けており、人々の日常のコミュニケーションをほぼ完全に担っています...

外部リンクがウェブサイトのランキングに与える影響は、量よりも質が重要です。

外部リンクと内部リンクは、ウェブサイトのランキングの 8 割を占めています。外部リンクとコンテンツの...