アンチエントロピーとGossipプロトコル

アンチエントロピーという発想

大規模クラスタでは、全ノードを束ねる中央コーディネータを置くと、そこが単一障害点とスケール限界になります。Gossipプロトコル（gossip protocol、epidemic protocol とも） は、中央を一切置かずに、各ノードが 定期的にランダムなピアを選んで状態を交換する という単純な規則だけで、クラスタ全体に情報を伝播させます。Amazon Dynamo、Cassandra、Consul、Serf、Akka Cluster などがメンバーシップ管理や障害検出に採用しています。

理論的な背骨が アンチエントロピー（anti-entropy） です。レプリカ同士は放っておくと差分（エントロピー＝乱雑さ）が増えていきます。そこで定期的にペアで状態を突き合わせ、差分を解消して エントロピーを減らし続ける ことで、更新が止まればいつか全レプリカが揃う。これは 整合性モデル でいう 結果整合性 を支える代表的な実装手法です。

なぜ log N ラウンドで収束するのか

gossip の収束の速さは、感染症の流行モデル（epidemic model）と同型です。1つの更新を持つノードを「感染者」、まだ持たないノードを「未感染」とみなします。総数を N、ラウンド t での感染者数を I(t) とすると、各感染者が毎ラウンド1台へ伝えるため、感染者が少ない序盤は 指数的に増加 します。

# push（感染者がランダムな1台へ送る）の概形
I(t+1) ≒ I(t) + I(t) * (未感染の割合)
       = I(t) * (2 - I(t)/N)     # 序盤 I << N では約 2*I(t)

序盤は1ラウンドごとにほぼ倍増するので、I が N/2 に達するまで約 log2 N ラウンド。問題は 終盤 で、残り少数の未感染者にランダムな送信が当たる確率が下がり、push だけでは収束の最後が遅れます（後述）。それでも全体は O(log N) ラウンド で揃う、というのが epidemic 拡散の核心です。N が100万でも log2 N は約20。台数が桁で増えてもラウンド数は対数でしか増えない という、極めて優れたスケール特性です。

push / pull / push-pull の収束速度

ペアで状態交換するとき、どちら向きに送るかで収束特性が変わります。

直感は感染者と未感染者のどちらが「探しに行く」かにあります。push は感染者が送る側なので、未感染が残り少なくなると「未感染に当たる確率」が下がり終盤が伸びます。pull は未感染が自分から取りに行くので、感染者が多数派になった終盤ほど「感染者に当たる確率」が高く、速い。残り未感染割合を x とすると、pull では x が毎ラウンドおよそ二乗のオーダーで縮む（x が x^2 程度に減る）ため、二重指数的（doubly exponential） に収束します。

push-pull は1回の交換で双方が相手の差分を取り込むため、push の序盤の速さと pull の終盤の速さを併せ持ち、最も少ないラウンドで全体が揃います。実装では Cassandra のように push-pull（三段ハンドシェイク：SYN/ACK/ACK2 で互いの差分だけ交換）を採るのが一般的です。

Merkle木による差分検出

anti-entropy で2ノードが「どこが食い違うか」を調べるとき、全データを送って比較するのは帯域の無駄です。ここで Merkle木（ハッシュツリー） を使います。

• 葉：各データ範囲（キー区間）のハッシュ。
• 内部ノード：子ハッシュを連結して再ハッシュした値。
• 根：木全体を1個に要約したハッシュ。

2ノードはまず 根のハッシュだけ を交換します。一致すれば、その配下のデータは完全に同一なので 転送ゼロ で同期完了。違えば子へ降りて比較し、食い違う枝だけ をたどります。差分が d 箇所、葉が n 個なら、比較・転送コストは全データの O(n) ではなく O(d * log n) に圧縮されます。差分がごく一部のときに劇的に効くのがポイントです。

# 根が違えば子へ。一致する枝（=*）はそこで打ち切り
        root(異)
       /        \
   hashL(同*)   hashR(異)      # 左は一致 → 左の全データはスキップ
                /      \
            leaf(同*)  leaf(異)  # この葉の範囲だけ実データを突き合わせ

SWIM障害検出の原理

メンバーシップ管理には「誰が生きていて誰が落ちたか」の合意が要ります。素朴に 全員が全員を ping する と通信量は O(N^2) に膨らみ、N が増えると破綻します。SWIM（Scalable Weakly-consistent Infection-style process group Membership） は、検出と伝播を分離してこれを O(N)（各ノードあたり一定負荷）に抑えます。

検出の核は 間接 ping です。

1. ノード A は周期ごとに ランダムな1台 B へ ping を送る。
2. B から ack が来れば生存確認、終わり。
3. タイムアウトしたら、A は 別のランダムな k 台 に「B を代わりに ping して」と依頼する（間接 ping）。
4. k 台のいずれかが B から ack を取れれば、B は生存（A↔B 間の一時的な経路障害だっただけ）。
5. 直接も間接も全滅なら、A は B を suspect（疑い） と印を付ける。

ポイントは、各ノードが毎ラウンド 1台＋疑わしければ k 台 しか触らないため、監視負荷がクラスタ規模に依存しない ことです。間接 ping は、A と B の間だけが詰まっている偽陽性（false positive）を打ち消す役割を持ちます。

Suspicion機構で誤検知を減らす

即座に「死亡（dead）」と断ずると、GC ストールや一瞬の輻輳で生きたノードを誤殺してしまいます。SWIM は suspect → （一定時間内に反証がなければ）→ dead という二段階を踏みます。疑われたノード B 自身も gossip で「自分は生きている（refute）」を流せるため、誤判定を覆せます。これは FLP不可能性 が示す「非同期系では『遅い』と『死んだ』を確実に区別できない」という限界への、確率的・実用的な折り合いです。

判定結果をgossipに相乗りさせる

SWIM のもう一つの肝は、メンバーシップの変化（join / leave / suspect / dead）を 専用の伝播経路で配らない ことです。これらのイベントを ping/ack メッセージの空き領域に ピギーバック（相乗り） させて運びます。つまり障害検出のトラフィックそのものが gossip の伝播路を兼ね、追加メッセージなしで情報が epidemic 拡散します。各イベントには インカネーション番号（世代カウンタ） を付け、古い「suspect」を新しい「alive」が上書きできるようにして、状態の整合を取ります。これは 論理時計 と同じく、物理時刻に頼らず どちらの情報が新しいか を単調増加カウンタで決める発想です。

まとめ

• Gossip は中央調整なしに「ランダムなピアと周期的に状態交換する」だけで全体へ情報を広げ、O(log N) ラウンド という対数スケールで収束する。
• アンチエントロピー はレプリカ間の差分を周期的に解消し続ける発想で、結果整合性の底支えになる。速報は rumor、底支えは anti-entropy と併用する。
• 拡散方式は push / pull / push-pull。push は終盤が遅く、pull は終盤が速く、push-pull が二重指数で最速のため既定値になる。
• 差分検出は Merkle木 で全比較 O(n) を O(d * log n) に圧縮し、一致する枝を転送ゼロでスキップする。
• SWIM は間接 ping で負荷を O(N) に抑え、suspect → dead の二段判定で誤検知を減らし、判定結果を ping にピギーバックして gossip で配る。誤殺の本質は FLP不可能性 に根ざす。