Reading: Epidemic Broadcast Trees

1. Introduction

tree-based and gossip based primitives. メッセージの伝送に unreliable IP multicast を使う。欠点として IP-multicast に依存していること、2 つの異なる protocol が必要で複雑であること。

この論文で説明するのは、tree-based で gossip な protocol で、かつ、メッセージングの複雑さが低く、高信頼性な手法である。この手法は gossip-based なオーバーレイに埋め込まれた broadcast tree を使う。broadcast は木のブランチ上で push gossip をすることで実現する。gossip-based なオーバーレイの(push gossip でカバーされない)残りのリンクでは、 lazy-push アプローチでメッセージを伝播させる。push-lazy-push multicast tree から Plumtree と呼ぶ。Plumtree は gossip-based なランダムオーバーレイだけで操作が完結するので、IP-baased multicast などに依存しない。システム全体の80%が故障していても迅速に復旧できる。

(以下一般的な gossip protocol の説明なので省略)

2. Gossip Protocols

2.2 Gossip Strategy

  • Eager push approach

    • 初めて受けとったペイロードをランダムな peer にすぐに送信する。

  • Pull approach

    • 定期的に peer から情報を取得する。unreliable broadcast を組み合わせると最も良く機能する。

  • Lazy push approach

    • ノードがあるメッセージを初めて受けとったときに、メッセージ識別子のみをランダムに選んだ peer に送る。peer はまだそのメッセージを受け取っていなかったら、明示的に pull をする。

2.3 Metrics

  • Reliability

    • gossip broadcast を伝送するアクティブなノードのパーセンテージで定義される。

  • Relative Message Redundancy

    • gossip protocol のメッセージオーバーヘッド。(m / (n - 1)) - 1 で定義される。

    • m: broadcast 手続き中に交換されるメッセージのペイロード数

    • n: broadcast を受け取るノード数

    • ただし、制御メッセージはこのメトリクスには含まれない。

  • Last Delivery Hop

    • すべての recipients にメッセージを broadcast するのに必要なホップ数。

    • メッセージを初めて gossip する時にカウントを1にセットして、リレーされるたびに increment される。

3. Epidemic Broadcast Trees

3.1 Architecture

  • Random Overlay Network

    • システムの partial view を管理するコンポーネント。

    • Peer Sampling Service によって実現される。

  • Plumtree Protocol

    • この論文で説明している gossip スキームを実体化するコンポーネントで以下の 2 つの機能を持つ。

      • Tree construction

      • Tree repair

  • Tree construction

    • eager push strategy でメッセージのペイロードを転送するためにランダムオーバーレイネットワーク内のどのリンクを選択するかについて責務を持つ。

  • Tree repair

    • 障害が発生した際のツリーの修復について責務を持つ。

    • spanning tree ですべてのノードが覆われることを担保する。

  • GetPeers() 関数

    • peer sampling service が提供する関数。あるノードの neighbors の内メッセージを送信すべきノード(群)情報を返す。

  • NeighborUp(), NeighborDown()

    • partial view に変化があったときに gossip protocol を通知するために利用する。

3.2 Overview

Plumtree の設計方針について。

  • protocol は純粋な gossip protocol として実行される。

    • gossip には eager push と lazy push の組み合わせを使う。

    • eager push は fanout の subset に対して、lazy push はそれ以外のノードに対して使われる。

  • 障害が発生しない限り、各 gossip ステップで peer の集合は変化しない。

3.3 Peer Sampling Service and Initialization

random overlay network は以下の特性を持たなければならない。

  • connectivity

    • 障害があってもつながり続けなければならない。

  • scalable

    • 大規模な分散アルゴリズム向けに設計されている。

  • reactive membership

    • peer sampling service は steady-state において動作する時は partial views 内で 同一メンバーを管理するような reactive な戦略を採用しなければならない。(!メンバーが固定される)

最初は f 個のランダムな peer を持つ。それらのピアは peer sampling service から得られる。

最初は空。

つまり、このプロトコルでは最初は純粋な push gossip protocol を実行する。

オーバーレイがすべてのノードの eagerPushPeers で定義され、すべてのノードを覆うように fanout f の値は選ばれなければならない。HyParView を peer sampling service として使うとこのタスクは簡単になる。

3.4 Gossip and Tree Construction

eagerPushPeers の初期化が終わると、ノード集合は eagerPushPeers を lazyPushPeers に移しながら spanning tree を構築する。

  • ノードは送信元から初めてメッセージを受け取った時に、送信元を eagerPushPeers に追加する。

  • 同じメッセージを受け取った時は送信元は lazyPushPeers に移される。

    • PRUNE 応答を送信元に投げる。PRUNE を受け取ったノードは送信元を lazyPushPeers に移す。

  • lazyPushPeers にノードが追加されるやいなや、eagerPushPeers と lazyPushPeers に情報を伝播する。

    • lazy push は IHAVE メッセージを送ることで実装される。

    • IHAVE メッセージはただちに送信される必要性はない。

3.5 Fault Tolerance and Tree Repair

障害が発生すると少なくとも1つのブランチが影響を受けるので、eager push ではメッセージの到達保証には十分ではない。失なわれた(かもしれない)メッセージの復元、multicast tree の迅速な復元 のために lazy push でメッセージを伝播させる。

ノードは IHAVE メッセージを受け取ると単にその IHAVE メッセージに対応するメッセージを missing 状態としてマークする。タイマーを開始し、時間内に eager push から失われた(かもしれない)メッセージを受け取るのを待つ。

タイムアウトした場合、タイムアウトした IHAVE メッセージから最初のメッセージを選び、IHAVE メッセージの送信元へ GRAFT メッセージを送る。GRAFT メッセージは2つの目的を持つ。1つ目は失われた(かもしれない)メッセージのペイロードの伝送をトリガーすること、2つ目は broadcast tree を復元しつつ、その復元に対応するノード間のリンクを tree に追加すること。

3.6 Dynamic Membership

gossip overlay の変化は NeighborDown, NeighborUp メッセージで通知される。neighbor の離脱を検知したら、eagerPushPeers と lazyPushPeers から取り除き、missing メッセージの履歴から、離脱したノードからのメッセージをすべて取り除く。neighbor が追加を検知したら、単純に eagerPushPeers に追加する。

3.7 Sender-Based vs Shared Trees

Plumtree で作られる木は特定の sender に最適化されている。その sender とは、ノードを eagaerPushPeers 集合から lazyPushPeers 集合へ移すのに利用される最初の broadcast の送信元。

レイテンシの最適化のために、異なる送信元毎に異なる Plumtree を使う。メモリとシグナリングのオーバーヘッドがともなう。

木を構築する時の original broadcast を送信したノード以外にとっては最適以下の効率になる。

3.8 最適化

  • 上記アルゴリズムで生成した spanning tree は最初の broadcast メッセージで主に決まるので、構成の変化時に最適とはならない。

  • さらに、repair のプロセスは IHAVE メッセージのスケジューリングポリシーに影響を受ける。

上記の制限を乗り越えるために、hop count がある閾値を越えていたら GRAFT メッセージと PRUNE メッセージを投げる最適化ができる。閾値が低いほど tree は最適化しやすくなる。

4. Evaluation

以下実験結果なので省略。

Comments

comments powered by Disqus