ファイル置き場日本Cassandraコミュニティ

(1)

谷口雄作 - @yuusaku_tan

Efﬁcient Reconciliation & Flow Control

for Anti-Entropy Protocolsをざっくり紹介

第９回 Cassandra勉強会 2010年７月，東京

http://d.hatena.ne.jp/yuusaku_tan/

(2)

Agenda

•Cassandra におけるGossipの利用

•論文紹介（本題）

•その他関連トピックス

(3)

CassandraにおけるGossipの利用

(4)

主な目的

日々変化する情報（state）をクラスタ内で共有する

state

(5)

Gossipを利用した機能

•ノード管理（membership）

•障害検出

•etc.

※参考文献 Cassandra - A Decentralized Structured Storage System Avinash Lakshman, Prashant Malik LADIS 2009

(6)

Efﬁcient Reconciliation and Flow Control for Anti-Entropy Protocols

Robber van Renesse, Dan Dumitriu, Valient Gough Chris Thomas LADIS 2008

(7)

本論文の概要

•Gossip の基礎

•Anti-Entropy Protocol を対象とした資源節約術

‣ Reconciliation に対する工夫

‣ Flow Control に対する工夫（今日は割愛します）

(8)

Gossipの基礎

論文紹介

(9)

P2P型の情報共有

state

•stateは各ノード内で管理（１カ所で中央管理しない）

•各ノードは他のノードと定期的に情報交換を行い、自分が管理するstateを更新

state

(10)

stateのデータ構造

共有する情報を辞書として表現

•

データが作成されたノード毎に分類

•

他のノードのデータは情報交換を通してのみ更新可能 value 1 version 1 value 2 version 1 key 1

key 2 node A

count up

value 1 version 1 key 1

node B

(11)

Gossipの種類

•Anti-Entropy protocol

‣ _push

‣ _pull

‣ push-pull：本論文の焦点

•Rumor-mongering protocol

(12)

Push-pull 式の情報交換

1. 参加者の中から情報交換の相手を選択

B

C _E

A

(13)

Push-pull 式の情報交換

何か新しい情報持ってたら下さい

node A

^{digest A}

node B

2. 自分が管理しているstateの概要を相手に送信

(14)

Push-pull 式の情報交換

node A

sub-state B & order-sheet A

node B

あなたの持ってる情報私のより新しいので

ついでに下さい

3. 相手から更新情報を受け取って自分のstateを更新

(15)

Push-pull 式の情報交換

node A

sub-state A

node B

4. 相手が必要としている情報を送信

どうぞー

(16)

情報交換に使用するメッセージの基本構造

各更新情報をタプルとして表現

タプルのリストとしてメッセージを構成

node A key 1 value 1 version 1 node A key 2 value 2 version 1 node B key 1 value 1 version 1

...

(17)

Gossipに基づく情報共有の課題

資源の枯渇

•情報交換に利用可能な資源に限りがある

•Gossip経路が渋滞するにつれ、情報の伝搬が遅延

(18)

資源の節約

•情報交換に使用する各メッセージの最大サイズを規定

•各ノードのGossip率を制限

(19)

Reconciliation

論文紹介

(20)

Reconciliation とは

•stateの不一致を解消する操作のこと

•情報交換を行いstateを更新する一連の流れ

state state^new

node B node A

state^sub

node A

=

(21)

更新情報の優先度

•資源節約のため、一度に交換できる更新情報の数が制限される

•各更新情報に対して優先度を付与、メッセージサイズの許す限り優先度の高い情報を選び抜く処理が必要になる

(22)

パフォーマンスに影響する主なポイント

•更新情報の検出方法

•digest のデータ構造

•メッセージに格納する更新情報の優先基準

(23)

本論文で紹介されているメカニズム

•precise（比較対象）

•scuttlebutt（提案手法）

(24)

Precise Reconciliation

論文紹介

(25)

更新情報の検出方法

検証対象各keyのversion番号

node A ^{key 1} ^{version 1} ^{version 4} node A

key 2 version 1 version 1 node B key 1 version 2 version 1

state

m

state

p

new!

(26)

digest のデータ構造

node A key 1 version 1 node A key 2 version 1 node B key 1 version 1

...

送信データノード名・key・version番号

(27)

メッセージに格納する更新情報の優先基準

２種類の基準を紹介

•precise-oldest

•precise-newest

(28)

precise-oldest

更新発生からより時間が経過している情報を優先

旧

新

...

node A key 1 val. 1 ver. 1 node B key 2 val. 2 ver. 1 node A key 2 val. 2 ver. 2

node B key 1 val. 1 ver. 7 node A key 3 val. 3 ver. 9

(29)

precise-newest

更新発生から間もない情報を優先

node A key 1 val. 1 ver. 1 旧

新

...

(30)

Scuttlebutt Reconciliation

論文紹介

(31)

state の管理

version番号が通し番号となるように制約を加える

value 1 version 1 value 2 version 2 key 1

key 2 node A

unique

node B

(32)

更新情報の検出方法

検証対象各ノードの最大version番号

node A version 1 version 4 node B version 2 version 2

state

new!

更新情報の範囲 version 2∼4

(33)

digest のデータ構造

node A version 2 node B version 1

...

送信データノード名・最大version番号

(34)

メッセージに格納する更新情報の優先基準

２種類の基準を提案

•scuttlebutt-breadth

•scuttlebutt-depth

(35)

scuttlebutt-breadth

旧新

多

少

node A node B

node C node D node E

メッセージに格納されるノード数を優先

(36)

scuttlebutt-depth

旧新

多

少

node A node B

node C node D node E

取り残されているノードの更新情報を優先

(37)

評価：Precise vs. Scuttlebutt

論文紹介

(38)

実験の概要

各 reconciliation メカニズムのパフォーマンスを比較

検証環境

•ノード数：128

•各stateで64個のkeyを共有

•各更新イベントで更新するkeyの数：1

•メッセージサイズの制限を検証開始15秒後から実施

(39)

更新イベントの発生率

時間 [秒] 発生率 [イベント数/秒]

0 1 2 3

0 20 40 60 80 100 120 140

25

75

(40)

クラスタ全体におけるkeyの更新率

時間 [秒] 更新率 [key/秒]

0 128 256 384

0 20 40 60 80 100 120 140

25

75

(41)

最大遅延時間の比較

時間 [秒] 最大遅延時間 [秒]

(42)

遅延数の比較

遅延数

時間 [秒]

(43)

まとめ

scuttlebutt-depth

の結果が一番良かった

(44)

その他関連トピックス

(45)

Cassandra 用語集の中で関連しそうな項目

•Merkle Tree

•Φ Accrual Failure Detector

•Snitch

※参考文献 Apache Cassandra Glossary's Japanese Translation

http://mocchira.posterous.com/apache-cassandra-glossarys-japanese-translati

(46)

Merkle Tree

•データ集合を小さな形式に要約した２分木構造

•暗号化や、ファイルや伝送データのベリファイに用いられる

•Cassandraでは、情報交換の際に使用される

‣ Column Family のhash値を計算

(47)

Φ Accrual Failure Detector

•障害が発生したノードを検知するプロセス

•Cassandra では Φ Accrual Failure Detector に更に手を加えたものを使用している

※参考文献 Φ Accrual Failure Detector Naohiro Hayashibara, Xavier Défago, Rami Yared, and Takuya Katayama In RR IS-RR-2004-010, JAIST, 2004

(48)

Snitch

•ノードとネットワークの物理的な位置を結びつける手法

•クラスタ内の相対的なノードの位置決定を支援する

‣ 新ノードの発見と効率的なRequest Routingの実現

(49)

ファイル置き場 日本Cassandraコミュニティ

Efﬁcient Reconciliation & Flow Control

for Anti-Entropy Protocolsをざっくり紹介

Agenda

CassandraにおけるGossipの利用

主な目的

Gossipを利用した機能

本論文の概要

Gossipの基礎

P2P型の情報共有

stateのデータ構造

•

•

Gossipの種類

Push-pull 式の情報交換

Push-pull 式の情報交換

node A

node B

Push-pull 式の情報交換

node A

node B

Push-pull 式の情報交換

node A

node B

情報交換に使用するメッセージの基本構造

...

Gossipに基づく情報共有の課題

資源の節約

Reconciliation

Reconciliation とは

=

更新情報の優先度

パフォーマンスに影響する主なポイント

本論文で紹介されているメカニズム

Precise Reconciliation

更新情報の検出方法

digest のデータ構造

...

メッセージに格納する更新情報の優先基準

precise-oldest

precise-newest

Scuttlebutt Reconciliation

state の管理

更新情報の検出方法

digest のデータ構造

...

メッセージに格納する更新情報の優先基準

scuttlebutt-breadth

scuttlebutt-depth

評価：Precise vs. Scuttlebutt

実験の概要

更新イベントの発生率

クラスタ全体におけるkeyの更新率

最大遅延時間の比較

遅延数の比較

まとめ

scuttlebutt-depth

の結果が一番良かった

その他関連トピックス

Cassandra 用語集の中で関連しそうな項目

Merkle Tree

Φ Accrual Failure Detector

Snitch

Q&A

ファイル置き場日本Cassandraコミュニティ