Push-Lazy-Push Multicast Tree.
高いスケーラビリティ、信頼性 (Reliability) 、回復力 (Resiliency) を達成するため、 流行性のブロードキャスト (Epidemic Broadcast) と、 決定論的なツリーに基づくブロードキャスト (Deterministic Tree-Based Broadcast) を統合する。
純粋な Gossip Protocol と異なり、ブロードキャスト用のツリーを構築するフェーズで、冗長な転送経路が取り除かれるので、重複するメッセージが大量に転送されることはない。
Peer Sampling Service: HyParView
メンバーシップの維持と隣接ノードの情報を取得するためのコンポーネント。
Plumtree Protocol コンポーネントに対して NeighborUp / NeighborDown を通知する。
- all nodes should have in their partial views, at least, another correct node.
- all nodes should be in the partial view of, at least, a correct node.
- the peer sampling service should be able to operate correctly in such large systems (e.g. with more than 10.000 nodes).
Example:
- ブロードキャスト用のツリー。
- 受け取ったメッセージを Eager Push Approach で直ぐに転送するのに使う。
- 最初は Peer Sampling Service コンポーネントから取得 (
GetPeers) する。 - 最初はランダムに選ばれた幾つか (riak_core の場合は
round(math:log(length(Members)) + 1)) のノードを含む。
3 = round(math:log(10) + 1).
6 = round(math:log(100) + 1).
8 = round(math:log(1000) + 1).
10 = round(math:log(10000) + 1).
- フォールトトレラント用のスパニングツリー。
- 定期的に Lazy Push Approach でツリーを修復するのに使う。
- 最初は空。
Gossip Protocol により、ツリーの構築と修復を実現するためのコンポーネント。
Example:
eagerPushPeers から lazyPushPeers へ隣接ノードを移動することで、スパニングツリーを構築する。
- あるメッセージを初めて受け取ったら、それを送信したノードを
eagerPushPeersに追加する。 - 再度、同じメッセージを受け取ったら、それを送信したノードを
lazyPushPeersに移動する。 - ノードを
lazyPushPeersに移動したら、そのノードにPRUNEメッセージを送信する。 PRUNEメッセージを受信したら、それを送信したノードをlazyPushPeersに移動する。
Example:
- basho/riak_core: riak_core_util:build_tree/3
- basho/riak_core: riak_core_broadcast:init_peers/1
- basho/riak_core: riak_core_broadcast:handle_broadcast/8
- basho/riak_core: riak_core_broadcast:add_lazy/3
- helium/plumtree: plumtree_util:build_tree/3
- helium/plumtree: plumtree_broadcast:init_peers/1
- helium/plumtree: plumtree_broadcast:handle_broadcast/8
- helium/plumtree: plumtree_broadcast:add_lazy/3
%% 隣接ノードのリスト.
Members = [1,
11, 12,
111, 112, 121, 122,
1111, 1112, 1121, 1122, 1211, 1212, 1221, 1222],
%% 各ノードが K (= 4) 個の子ノードを持つ木.
Tree = [{ 1, [ 11, 12, 111, 112]},
{ 11, [ 121, 122, 1111, 1112]},
{ 12, [1121, 1122, 1211, 1212]},
{ 111, [1221, 1222, 1, 11]},
{ 112, [ 12, 111, 112, 121]},
{ 121, [ 122, 1111, 1112, 1121]},
{ 122, [1122, 1211, 1212, 1221]},
{1111, [1222, 1, 11, 12]},
{1112, [ 111, 112, 121, 122]},
{1121, [1111, 1112, 1121, 1122]},
{1122, [1211, 1212, 1221, 1222]},
{1211, [ 1, 11, 12, 111]},
{1212, [ 112, 121, 122, 1111]},
{1221, [1112, 1121, 1122, 1211]},
{1222, [1212, 1221, 1222, 1]}],
%% 隣接ノードのリストから各ノードが K 個の子ノードを持つ木を構築する.
Tree = riak_core_util:build_tree(round(math:log(length(Members)) + 1), Members, [cycles]).
lazyPushPeers に追加されたノードと定期的にメッセージを交換することで、ツリーの故障を検知して修復する。
- ブロードキャストされたメッセージの識別子を、定期的 (riak_core の場合は 1 秒ごと) に
IHAVEメッセージでlazyPushPeersに追加されたノードに送信する。 IHAVEメッセージを受信したら、一定時間eagerPushPeersからブロードキャストされたメッセージが転送されて来るのを待つ。- 一定時間以内にブロードキャストされたメッセージが転送されて来なければ、
IHAVEメッセージを送信して来たノードをeagerPushPeersに移動する。 - ノードを
eagerPushPeersに移動したら、そのノードにGRAFTメッセージを送信する。 GRAFTメッセージを受信したら、それを送信したノードをeagerPushPeersに移動する。- ノードを
eagerPushPeersに移動したら、そのノードにブロードキャストされたメッセージのペイロードを送信する。
重複したメッセージを受信すると PRUNE メッセージによって、冗長な転送経路が取り除かれるので、eagerPushPeers が増え続けることはない。
Example:
- basho/riak_core: riak_core_broadcast:schedule_lazy_tick/0
- basho/riak_core: riak_core_broadcast:send_lazy/1
- basho/riak_core: riak_core_broadcast:handle_ihave/7
- basho/riak_core: riak_core_broadcast:handle_graft/7
- basho/riak_core: riak_core_broadcast:add_eager/3
- helium/plumtree: plumtree_broadcast:schedule_lazy_tick/0
- helium/plumtree: plumtree_broadcast:send_lazy/1
- helium/plumtree: plumtree_broadcast:handle_ihave/7
- helium/plumtree: plumtree_broadcast:handle_graft/7
- helium/plumtree: plumtree_broadcast:add_eager/3
ノードごとに異なるブロードキャスト用のツリーを使う。
転送のホップ数を最適化できる。
riak_core はこのモード。
すべてのノードが単一の共有されたブロードキャスト用のツリーを使う。
ホップ数が閾値を超えた eagerPushPeers のノードを lazyPushPeers のノードと入れ替えることで最適化できる。