ゴシッププロトコル - yuuk1's Digital Garden

# ゴシッププロトコル ## 定義ゴシッププロトコル（gossip protocol）は、分散システムにおいてノード間で情報を伝播させるための通信手法であり、各ノードがランダムに選んだ少数の相手と定期的に状態を交換することで、最終的にクラスタ全体に情報が行き渡る。感染症の伝播モデルに着想を得ており、エピデミックプロトコル（epidemic protocol）とも呼ばれる。中央集権的なコーディネータを必要とせず、ノードの参加・離脱に対して自然に耐性を持つ点が特徴である（Source: [[@2010__SIGOPS_OSR__Cassandra - A Decentralized Structured Storage System]]）。 ## 横断的知見 - Cassandra は Scuttlebutt と呼ばれるアンチエントロピー型ゴシップを採用し、メンバーシップ管理だけでなくシステム制御状態の伝播にもゴシップを使用している。Dynamo も同様にゴシップベースのメンバーシップを採用しており、すべてのノードが他の全ノードの情報を保持する。両システムとも、ゴシップを通じてリング上のノード配置とデータ所有権を伝播するが、Cassandra はさらに Φ 累積障害検知器をゴシップ到着間隔に基づいて動作させることで、障害検知をゴシップ層と緊密に統合した点が独自である（Source: [[@2010__SIGOPS_OSR__Cassandra - A Decentralized Structured Storage System]]、[[@2007__SOSP__Dynamo - Amazon's Highly Available Key-value Store]]）。 - [[@2002__DSN__SWIM - Scalable Weakly-consistent Infection-style Process Group Membership Protocol]](DSN 2002)は、Cassandra/Dynamo のようなアンチエントロピー型(全状態を定期的に交換する)ゴシップとは異なる設計を提示する。SWIM は障害検知(ランダム化された間接プロービング: ping / ping-req / ack)とメンバーシップ更新の伝播を明確に分離し、更新情報は独立したゴシップメッセージではなく障害検知プロトコル自身が生成する ping・ack メッセージへの**ピギーバック**でのみ伝播する(感染様式ディセミネーション)。この設計により専用のゴシップメッセージを一切追加で生成せず、メンバーあたりのメッセージ負荷を定数(実測で約 2.0 メッセージ/周期、グループサイズ 8〜56 で不変)に保つ。Cassandra の Scuttlebutt がノード全体のダイジェストを毎ラウンド交換するのに対し、SWIM は「その周期にたまたま選ばれた 1 つの通信相手への応答」に更新を相乗りさせるだけであり、両者は同じ「ゴシップ的伝播」という性質を共有しつつメッセージ生成主体が異なる 2 つの実装系統として区別できる(Source: [[@2002__DSN__SWIM - Scalable Weakly-consistent Infection-style Process Group Membership Protocol]])。 - SWIM の Suspicion サブプロトコル(疑わしいメンバーを即座に failed とせず、まず suspected とマークして猶予期間の間に Alive/Confirm を待つ)は、Cassandra の Φ 累積障害検知器が採用する連続値の疑わしさスコアとは異なる、離散状態遷移(alive → suspected → faulty)による誤検知抑制の設計である。いずれも「即座に 2 値判定しない」という同じ問題意識(ネットワーク損失やスローネスと真の障害を区別する)への異なる解であり、SWIM は仮想 incarnation number によって同一メンバーへの複数回の suspect/alive を一意に順序づける点が Φ 検知器にはない要素である(Source: [[@2002__DSN__SWIM - Scalable Weakly-consistent Infection-style Process Group Membership Protocol]]、[[@2010__SIGOPS_OSR__Cassandra - A Decentralized Structured Storage System]])。 - [[@2021__OReillyJapan__詳説データベース - Chapter 9 障害検出]]は、Cassandra/Dynamo/SWIM の各実装から離れて「ゴシップ方式の障害検出サービス」を一般的なパターンとして記述する [VANRENESSE98]。各メンバーが他メンバーのハートビートカウンタとタイムスタンプのリストを保持し、定期的にランダムな近くのノードへリストを配信・マージするという骨格は、本ページが Cassandra の Scuttlebutt について記録してきた設計と同型だが、Petrov の記述はこれを特定システムの実装詳細としてではなく「単一ノードのビューへの依存を避ける」ための一般的な障害検出戦略として抽象化している点が異なる。すなわち Cassandra 論文がゴシップを「メンバーシップとシステム制御状態の伝播手段」として記述するのに対し、Database Internals はゴシップを「複数ノードの合議によって検出の信頼性を高める手段」として位置づけ直しており、同じ機構を異なる目的の言葉で説明している(Source: [[@2010__SIGOPS_OSR__Cassandra - A Decentralized Structured Storage System]], [[@2021__OReillyJapan__詳説データベース - Chapter 9 障害検出]] §9.3)。 - Database Internals 9 章が説明する「ハートビートのアウトソーシング」(P1 が P2 への ping に無応答のとき、ランダムな P3・P4 に間接確認を依頼する)は、[[@2002__DSN__SWIM - Scalable Weakly-consistent Infection-style Process Group Membership Protocol]] の基本障害検知プロトコル(ping-req による間接プロービング)の平易な言い換えである。両ソースを突き合わせると、Petrov の記述は SWIM の Suspicion サブプロトコルや感染様式ピギーバック伝播には立ち入らず、間接プロービングという中核機構のみを抽出して紹介していることが分かる——教科書的な入門記述と原論文の詳細設計の抽象度の違いが明確になる一例(Source: [[@2021__OReillyJapan__詳説データベース - Chapter 9 障害検出]] §9.1.2, [[@2002__DSN__SWIM - Scalable Weakly-consistent Infection-style Process Group Membership Protocol]] Section 3.1)。 - **同じ書籍の9章と12章は「ゴシップ」という同一機構を、障害検出の道具と情報散布そのものという異なる目的で扱っており、両者を合わせて初めてゴシップの全体像が見える**: [[@2021__OReillyJapan__詳説データベース - Chapter 9 障害検出]]はゴシップを「複数ノードの合議によって検出の信頼性を高める手段」として、ハートビートカウンタの交換という1つの用途に絞って紹介した。一方 [[@2021__OReillyJapan__詳説データベース - Chapter 12 アンチエントロピーと情報散布]]は、ゴシップを「メンバーシップ情報・ノード状態・スキーマ変更などクラスタ全体のメタデータを確実に伝播するための汎用機構」として捉え直し、ファンアウト(f 個のピアとの定期交換)、インフェクティブ/サセプタブル/除去済みという感染モデルの状態遷移、関心の喪失関数による収束制御、log N ラウンドでの配信というスケーラビリティ特性を導入する。9章の障害検出はこの汎用機構の一適用例にすぎず、12章は同じ確率的伝播の仕組みを「何を運ぶか」を特定しない形で抽象化している(Source: [[@2021__OReillyJapan__詳説データベース - Chapter 9 障害検出]] §9.3, [[@2021__OReillyJapan__詳説データベース - Chapter 12 アンチエントロピーと情報散布]] §12.6)。 - **純粋な確率的ゴシップと、Cassandra の Scuttlebutt のようなアンチエントロピー型ゴシップは、12章の分類軸(オーバーレイなし vs オーバーレイあり)で位置づけ直せる**: 本ページが記録してきた Cassandra/Dynamo のゴシップは、全ノードが他の全ノードの状態ダイジェストを毎ラウンド交換する設計であり、これは 12 章がいう「明示的な協調を避け、受信側リストの管理も避ける」古典的なランダムピア選択のゴシップにあたる。12 章はこれをさらに発展させ、ピア間に一時的な固定トポロジ(スパニングツリー)を構築するオーバーレイネットワーク、およびハイブリッドゴシップ(HyParView・Plumtree)という改良系統を導入する。HyParView はアクティブビュー(散布用オーバーレイ)とパッシブビュー(障害時の代替)を分離管理し、Plumtree は平常時にスパニングツリーで完全メッセージを配信し障害時のみ遅延プッシュのゴシップにフォールバックする。これらは Cassandra/Dynamo が採用する「常時オーバーレイなしのランダムゴシップ」と対照的な、冗長性とレイテンシのトレードオフを構造的に作り込んだ改良系統として位置づけられる(Source: [[@2010__SIGOPS_OSR__Cassandra - A Decentralized Structured Storage System]], [[@2021__OReillyJapan__詳説データベース - Chapter 12 アンチエントロピーと情報散布]] §12.6.2〜§12.6.4)。 - **『ウェブオペレーション』15章(2011年)は、Cassandra・Riak双方の「単一障害点を認めない」哲学を支える機構として、ゴシッププロトコルを実装詳細に踏み込まず「ノード情報を相互に取得し、クラスタ全体にすばやく情報を広める」役割だけで簡潔に説明しており、本ページが既存知見として蓄積するCassandra論文(Scuttlebutt・Φ検知器)やSWIM論文の詳細な設計論とは対照的な、2010年代前半の実務者向け抽象度を示す一次資料である**: 15章はCassandraについて「単一障害点を認めないという哲学もある。『コーディネーション』サーバや『選ばれたマスタ』などが存在しないのはそのためだ。ゴシッププロトコルを使って、ノード情報を相互に取得し、クラスタ全体にすばやく情報を広める」と述べ、Riakについても「単一障害点がない。ゴシッププロトコルを使って障害を検知し、リクエストを調整する」と述べるにとどまり、Scuttlebutt・Φ累積障害検知器・SWIMのSuspicionサブプロトコルといった内部実装には一切触れない。これは、本ページが記録する「教科書(Database Internals)は障害検出の道具と情報散布そのものという2つの目的でゴシップを論じ分ける」という抽象度の分岐が、実務書ではさらに一段抽象化され「単一障害点を排除する仕組み」という一言に集約されることを示し、読者層(実務者対データベース内部設計者)によってゴシップという同一機構が要求する説明の粒度が大きく異なることを裏づける。(Source: [[@2011__OReillyJapan__ウェブオペレーション - Chapter 15 非リレーショナルデータベース]] §15.2.1, §15.2.3) ## 未解決の問い - ゴシップの収束時間はクラスタ規模に対して O(log N) と理論的に示されるが、数千〜数万ノード規模での実用上の収束遅延はどの程度か。Cassandra 論文では 100 ノード規模でしか評価されていない。SWIM の実験も 56 メンバーまでに留まり、この問いは依然未解決である。 - Φ 累積障害検知器の指数分布近似は Cassandra のゴシップチャネル特性に合わせたものだが、異なるネットワークトポロジ（データセンタ内対データセンタ間）では分布モデルの切り替えが必要か。 - SWIM のピギーバック方式(専用ゴシップメッセージを生成しない)と Cassandra/Dynamo のアンチエントロピー方式(定期的に独立したダイジェストメッセージを送る)は、総ネットワーク帯域という観点でどちらが有利か。SWIM はメンバーあたりのメッセージ負荷を定数に保つ一方、メンバーシップ変更が高頻度な状況ではピギーバック枠(λ)を使い切り伝播が遅延しうる固有のトレードオフを持つ。両者を定量比較した文献はあるか。 - SWIM の WAN/VPN 拡張(トポロジ情報に基づくプローブ対象の重み付け)は設計思想の言及にとどまり実験がない。Cassandra/Dynamo のデータセンタ間ゴシップ実装と比較したとき、どちらのアプローチが WAN 環境でより実用的か。 - HyParView のアクティブビュー/パッシブビューのサイズはどのような基準で決めるべきか。12 章は定性的な設計原理(小さなアクティブビューで散布コストを抑え、パッシブビューを復旧の仕組みとする)を述べるが、具体的なサイズと収束速度・メッセージ数のトレードオフの定量評価は本章にはない。 - Plumtree の遅延プッシュ枠(メッセージ ID のみ転送する頻度)は SWIM のピギーバック枠(λ)と同種の「専用メッセージを避けて既存トラフィックに相乗りさせる」設計思想を共有するように見える。両者を同一の設計パターンとして定式化できるか、あるいは決定的な違いがあるか。 ## 関連 - ソース: [[@2010__SIGOPS_OSR__Cassandra - A Decentralized Structured Storage System]] / [[@2007__SOSP__Dynamo - Amazon's Highly Available Key-value Store]] / [[@2002__DSN__SWIM - Scalable Weakly-consistent Infection-style Process Group Membership Protocol]] / [[@2021__OReillyJapan__詳説データベース - Chapter 9 障害検出]] / [[@2021__OReillyJapan__詳説データベース - Chapter 12 アンチエントロピーと情報散布]] / [[@2011__OReillyJapan__ウェブオペレーション - Chapter 15 非リレーショナルデータベース]] - 概念: [[結果整合性]] / [[一貫性ハッシュ法]] / [[障害検出器]] / [[アンチエントロピー]] - エンティティ: [[Apache Cassandra]] / [[Riak]] ## 出典 - [[@2010__SIGOPS_OSR__Cassandra - A Decentralized Structured Storage System]]（§5.3 Membership、§5.3.1 Failure Detection——Scuttlebutt ベースゴシップと Φ 累積障害検知器） - [[@2007__SOSP__Dynamo - Amazon's Highly Available Key-value Store]]（ゴシップベースメンバーシップ） - [[@2002__DSN__SWIM - Scalable Weakly-consistent Infection-style Process Group Membership Protocol]](Section 3〜4: 障害検知とディセミネーションの分離、感染様式ピギーバック伝播、Suspicion サブプロトコル) - Alex Petrov, *詳説データベース*, オライリー・ジャパン, 2021, 9 章 §9.1.2「ハートビートのアウトソーシング」・§9.3「ゴシップと障害検出」、12 章 §12.6「ゴシップの散布」〜§12.6.4「部分的なビュー」. - [[@2011__OReillyJapan__ウェブオペレーション - Chapter 15 非リレーショナルデータベース]] §15.2.1, §15.2.3(2011年時点の実務書における抽象度の高いゴシップの説明。Cassandra/Riakの単一障害点排除の哲学)