Skip Graphs の解説 - @niftyホームページサービス

ＳｋｉｐＧｒａｐｈｓの仕組
みと
関連研究
大阪大学工学部
電子情報エネルギー工学科
小西
佑治
株式会社 BBR
吉田幹
発表構成
• 前半（小西）
– Skip Graph の仕組みの解説
• 後半（吉田）
– 地理的探索オーバレイ LL-Net の Skip Graph
を使った実装
前半の概要
• 自己紹介
• イントロ
• Skip Graphs について
• 関連研究の紹介
自己紹介
• 大阪大学の４回生です
• ただいま卒業研究の真最中
•
の管理人
– skip graph や SkipNet で検索した人は見たことがある
かも・・・
P2Pネットワーク
• 分散処理システム
• ピアが集まって形成されるネットワーク
• Ｋｅｙによって識別されるリソースを保持
どのようにピアを配置すると効率的か？？
理想的なP2Pネットワークの特
徴
• データの有効性
• 効率的な探索
– 非集中
– 地理的位置の考慮
– スケーラビリティ
– 時間的・空間的なリソー
スの配置
– フォールトトレランス
– 負荷分散
• ネットワークの維持
– 自己安定化
– ピアの動的な追加や削
除
初期のP2Pシステム
• Napster
– インデックスサーバがボトルネック
• Gnutella
– 非効率なフラッディングによる検索
• Freenet
– 検索待ち時間の保証がない
ＤＨＴ（分散ハッシュテーブ
ル）
• Ｓｔｒｕｃｔｕｒｅｄオーバーレイの代表格
• ＣＡＮ、Ｃｈｏｒｄ、Ｐａｓｔｒｙ、Ｔａｐｅ
ｓｔｒｙ、・・・
• リソースのＫｅｙをハッシュして、スケーラビ
リティと負荷分散を実現
ハッシュによりＫｅｙの順序が崩れ、範囲検索
が困難
ＳｋｉｐＧｒａｐｈｓ
論文：
"Skip Graphs" James Aspnes, Gauri Shah
SODA, Jan. 2003, pp.384-393
• 双方向リンクの Skip List をP2Pシステムに適用
• ルーティングテーブルのリンク数：
Οlogn 
• Keyをハッシュしない
• 範囲検索に対応（1次元）
• システム全体のノード数を知る必要がない
Skip List
HEAD
TAIL
33
Level 2
Level 1
13
Level 0
13
21
33
48
33
48
75
99
• ノードは Key 順に並ぶ
数字が Key
• Level 0 は全てのノードが含まれたリスト
• Level (i-1) に現れるノードはある確率 p で Level
i にも現れる
Skip List での検索
HEAD
HEAD から Key “75” を検索
success
failure
33
Level 2
Level 1
13
Level 0
13
21
33
48
33
48
75
99
• 上位レベルから下位レベルに降りてくる
• 平均探索時間：Οlogn 
TAIL
Skip Graph の構成
Level 2
13
21
33
10
01
48
75
99
00
11
11
21
75
99
10
11
11
00
Level 1
13
00
Level 0
33
48
01
00
Membership
vector
Skip List
13
21
33
48
75
99
00
10
01
00
11
11
• N ノードの skip graph のレベル数は
logN 
• Level i では Membership vector の接頭辞が i 桁
一致するもの同士がリンクをはる
検索・ノード追加・ノード削除
• 検索
– 平均時間：Οlogn 
• ノードの追加・削除
– 平均時間：Οlogn 
Skip Graph での検索
Key “33” のノードから Key “75” を検索
Level 2
13
21
33
10
01
48
75
99
00
11
11
21
75
99
10
11
11
00
Level 1
13
00
Level 0
success
33
48
01
00
failure
Skip List
13
21
33
48
75
99
00
10
01
00
11
11
Skip List と同様に検索を行う
一致する Key がない場合は Key が近いノードまで
届く
Skip Graph でのノード追加
Level 2
13
21
33
10
01
48
75
99
00
11
11
21
75
99
10
11
11
00
Level 1
13
00
Level 0
33
48
01
00
introducer
13
21
33
48
75
99
00
10
01
00
11
11
new
40
00
Introducer から Level 0 での新規ノードの位置
を
Skip Graph でのノード追加
Level 2
13
21
33
10
01
40
48
75
99
00
00
11
11
21
75
99
10
11
11
00
Level 1
13
00
Level 0
33
40
48
01
00
00
13
21
33
40
48
75
99
00
10
01
00
00
11
11
Level i-1 （i>0）で接頭辞の i 桁目が同じノードを
探して、 Level i でリンクをつくる
自己安定性
•
Skip Graph のノードの制約条件
•
制約条件が破られる場合
•
修復機構
ノードの制約条件
x の Level i における左右のノードを xLi、xRi とする
xLi ＜ x ＜ xRi
xLi = xLki-1
xLiRi ＝ xRiLi ＝ x
xRi = xRki-1
xRi
key
x
xLi
xRi
invariant 条件：
未配達のメッセージのない全ての
状態で満たされる条件
（ノード故障があっても満たされる）
Level i
x
Level i-1
x
00
01
xR1
00
i-1
xR2i-1
L & R successor 条件：
ノードやリンクの故障で満たされ
なくなる条件
修復機構の対象になる
Successor 制約条件が破られる場
合
1. xRi ＝ xRki-1 だが
∃a ＝ xRk’i-1 、k’ ＜ k 、m(x)i ＝ m(a)i
xRi
Level i
Level i-1
x
x
…00…
a
…00…
Membership vector が
i 桁同じ a が xRi になっ
…00…
ていない
xRk’i-1 xRki-1
2. ∀k に対して xRi ≠ xRki-1
xRi
Level i
x
Level i-1
x
xRi が Level i-1 に
存在しない
修復機構：Case１
Level i
zipperOpB
a
zipperOpF
xRi
x
Level i-1
x
a
…00…
…00…
xRk’i-1
…00…
xRki-1
x と a 、xRi と a に対して、Level i でそれぞ
れ
リンクのつなぎ換えを行う
修復機構：Case2-1
xRi
Level i
x
aLi-1
x
Level i-1
a
zipperOpB
zipperOpF
L
R
xRi より小さく aLi-1 より大き
い
xRi より大きく a より小さ
い
最小の key を持つノード
最大の key を持つノード
aLi-1
Level i-1
x
xRi
L
R
a
Level i-1 において、a と xRi に接続するノード群
は
修復機構：Case2-2
xRi
Level i
x
aRi-1
x
Level i-1
a
zipperOpF
zipperOpB
M
xRiLk’i-1 で a より大きい最小のノード
aRi-1
Level i-1
x
a
M
xRi
修復機構：Case2-3
xRi
Level i
x
a
x
Level i-1
zipperOpB
R
xRiLk’i-1 で a より大きい最小のノード
xRi
Level i-1
x
a
R
フォールトトレランス
• Adversarial failures
• Random failures
Adversarial failures
• Adversarial failures の対象ノードのセット：A
• Aにリンクを張っているノードのセット：δA
• もし A を分離しようとすると、δA のノード全て
を故障させなければならない
expansion ratio = min |δA | / | A | （1 ≦ | A | ≦ n/2）
Ω1/logn

f ノードの故障で
Οf  logn 
のノードが分離する可能性
ノード故障の確率
0.95
0.90
0.85
0.80
0.75
0.70
0.65
0.60
0.55
0.50
0.45
0.40
0.35
0.30
0.25
0.20
0.15
0.10
0.05
0.00
大きさ
Random failures
接続要素の最大サイズ
1.20
1.00
131072 nodes
0.80
0.60
0.40
0.20
0.00
Random failures 時の探索
失敗した探索の割合
131072 nodes
10000 messages
0.20
0.15
0.10
ノード故障の確率
0.6
0.5
0.4
0.3
0.2
0.00
0.1
0.05
0.0
失敗した探索の割合
0.25
負荷分散
s
s から t への検索経路
u
u:s<u<tな
るノード
u
d:u<v<tな
る v の数
u
t
s から t への検索経路上に u が存在する確率 P
P＝（Level k の経路に存在する u の数の期待値）/
（d+1）
＜ 2/(d+1)
実験結果
1.1
1.0
0.9
負荷の期待値
実際の負荷
目的ノード = 76542
ノードの負荷
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0.0
76400
76450
76500
76550
ノードの場所
76600
76650
論文で述べられている課題
•
•
•
•
•
効率的な修復機構を考える
地理的位置の近接性の考慮
実環境での性能の評価
多次元 Skip Graph
ビザンチン障害の影響の研究
関連研究
• SkipNet : A scalable overlay network with practical locality
properties
– Nicholas J. A. Harvey, Michael B. Jones, Stefan Saroiu,
Marvin Theimer, and Alec Wolman.
In Proceedings of USITS, USENIX., 2003
– Skip List の P２P 適用だが、構造はリストではなくリング
関連研究
• The Rainbow Skip Graph : Fault-Tolerant ConstantDegree Distributed Data Structure
– Michael T. Goodrich, Michael J. Nelson, and Jonathan Zheng Sun.
SODA ’06, January 22-26, Miami, FL
– Level 0 のリストを Θ（logn）の Core List に区切り、その Core List を
１つのノード（Super Node）として扱って Skip Graph を構築する
– Core List 内のノードは分担して各レベルを担当する
– 検索などのコストを Skip Graph と変えずに、ポインタの保持数を減ら
している
関連研究
• Skip B-Trees
– Ittai Abraham, James Aspnes, and Jian Yuan.
OPODIS Dec. 2005, pp. 284–295.
– タイトル通り、Skip Graph に B木の考え方を組み合わせたもの。
– Skip Graph の各レベルの各リストはブロックに分けられる
個人的な所感
範囲検索ができるというのは、
ユビキタスとかP2Pとかが流行るにつれて
ますます重要になるのではないか。
範囲検索できる Skip Graph は魅力的。
Key と ID をうまく使い分けしてやると
いろいろな用途に使えそう。
ご清聴ありがとうございました。
次は吉田さんです。

Download Report