SkipNet
Kazuyuki Shudo
PIAX を開発している、SkipNet シンパの吉田さんが
JXTA の ML で SkipNet を紹介しているメールを見つけました。
2005年 7月のことでした。
http://groups.yahoo.co.jp/group/ja-jxta/message/659
| Subject: [ja-jxta] SkipNet
| From: Mikio Yoshida <y...@bbr.jp>
| To: ja-...@yahoogroups.jp
| Date: Sat, 23 Jul 2005 19:37:40 +0900
| 最近、SkipNetについて勉強しました。
| ----
| Nicholas J.A. Harvey, et. al,
| SkipNet: A Scalable Overlay Network with Practical Locality Properties.
| Proceedings of the Fourth USENIX Symposium on Internet
| Technologies and Systems (USITS '03), March 2003
|
|
| DHTの問題である情報のローカリティ破壊を解決していること、
| range search を簡単に実現できる点、
| 併せて耐障害性の実現も明快
Kazuyuki Shudo/首藤一幸 私をたばねないで あらせいとうの花のように
20...@shudo.net http://www.shudo.net/
Miko Yoshida
首藤さん、見つけていただいてありがとうございます。
自分も忘れていました。
あっそうか、SkipNet（Skip Graph）の紹介は、ここでは初めてですね。
前振り的な内容を書いてみます。（長くなってしまいました）
> 皆様、首藤です。
>
> PIAX を開発している、SkipNet シンパの吉田さんが
> JXTA の ML で SkipNet を紹介しているメールを見つけました。
> 2005年 7月のことでした。
>
> http://groups.yahoo.co.jp/group/ja-jxta/message/659
>
> | Subject: [ja-jxta] SkipNet
> | From: Mikio Yoshida <y...@bbr.jp>
> | To: ja-...@yahoogroups.jp
> | Date: Sat, 23 Jul 2005 19:37:40 +0900
>
> | 最近、SkipNetについて勉強しました。
> | ----
> | Nicholas J.A. Harvey, et. al,
> | SkipNet: A Scalable Overlay Network with Practical Locality Properties.
> | Proceedings of the Fourth USENIX Symposium on Internet
> | Technologies and Systems (USITS '03), March 2003
> |
> |
> | DHTの問題である情報のローカリティ破壊を解決していること、
> | range search を簡単に実現できる点、
> | 併せて耐障害性の実現も明快
まだ 1年強しか経ってないのですね。
自分にはもっと昔の出来事のように思います。
LL-Netという地理的探索のための structured P2Pの実装で、うまく行かない
部分があって、サーベイのやり直しをやってたときに見つけた論文でした。
DHTのかっこよさ、その中でも、Kademlia のような割り切りのよい実装に感銘
しながらも、私の置かれた現実は「範囲検索」が対象だったので、DHTとは別
の仕掛けを生み出すか、見つけないといけないと考えていました。
で、世の中にはやはり賢い人がいるもので、skip list というデータ構造をベ
ースとした structured P2P を提案した論文がありました。
この場をお借りして、なぜ skip list かというお話を（当時）私が思ってい
たDHTの弱点を交えて説明しようと思います。
まず、skip list ですが、
これについては、Wikipedia を見るのがよいと思います。
http://en.wikipedia.org/wiki/Skip_list
アルゴリズムの研究としては、比較的最近出たもので、バランス木と同様の用
途を持つものだと思ってもらえればいいと思います。
通常のバランス木では、どうしても木の深さに偏りが出るため、バランスさせ
るための再構成処理が必要になるのですが、skip list の場合はこれが不要で
す。おのずと勝手にバランスするというありがたい性質を持っています。
と、ここまで書くと、
あれっ、DHTもよく見ると、それぞれのピアがピアIDにより分布しているバ
ランス木になっているのじゃないの？
ピアIDが一様分布するので、特に特別なデータ構造を持ち込まなくても勝手
にバランスしていると思うけど。
それにID空間は整数の閉空間だけど、順序関係は保持されている。
という疑問が出ると思います。
では、なぜ、DHTの仕組みだと範囲検索ができないのでしょうか？
それは、リソースをDHTの扱うID空間にマッピングする際に、ハッシュ関数を
使うことで順序関係を失っているためです。
逆に言えば、順序関係を保存する形で、ID空間にマッピングできれば、範囲検
索は可能になります。
（そういうアプローチをした論文もあります）
ただ、その場合、ID空間にマッピングした結果、リソースの分布に偏りが出な
いようにする必要があります。そこが難しい点だと思います。
例えば、月平均 1万から2万のヒット数を持つサイトを探したいとします。
ヒット数をうまくDHTのID空間に順序を保存させながらマッピングさせようと
思うと、ヒット数そのものの分布関数が必要になります。
ヒット数ならまだ統計手法に合いますが、地理的情報ならどうでしょう？
分布関数そのものが 1つに定まらないという問題がでます。この場合、分布関
数が途中で変化してしまうと意味がありません。
ここまでの話で、ピアIDの空間は利用できないため、次のシンプルな要件に立
ち戻ることになると思います。
範囲検索を前提とした、structured P2P が持つべき要件：
・ピアが保持する key は、順序関係のみが定義される開空間を構成する。
・ピアは数理的規則に従い、他のピアへのリンク情報を持つ。
このピア間のリンク構造は、P2Pネットワーク全体としてみたときに、
ピア探索のためのデータ構造として機能する。
・各ピアの保持するリンク情報のオーダは、log N である。
・key ∈ [k1,k2] なる key を検索するコストがlog N である。
P2Pネットワークはやはり、keyによって構成しないといけない。
手持ちのアルゴリズムとしては、バランス木を使うしかない。
そうなると、バランスさせるための複雑な処理とコストが問題になる。
うーん。
そんな中での skip list の登場です。
私としては、天から仏さまが舞い降りた気分でした。
SkipNetというより、オリジナルは Skip Graph ですが、
http://cs-www.cs.yale.edu/homes/shah/pubs/soda2003.html
これを考えた先生（Dr. James Aspnes）は偉いと思います。
SkipNetは、Skip Graphを拡張した内容を含む論文で、Skip Graphとは論文の
目的が違うと書いてありますが、基本部分はオリジナルのコピーです。
SkipNet自体は、今、MSから特許申請されていて、防衛特許の意味合いが強く
て気にしないでもよいとは思いますが、実装する人（私のことですが）は注意
が必要です。
> PIAX を開発している、SkipNet シンパの吉田さんが
ということで、*Skip Graph* シンパでお願いします。(^^;;
Aspnes 先生、最近は、Skip B-trees という論文を書いています。
http://www.cs.yale.edu/homes/aspnes/skip-b-trees-abstract.html
http://www.cs.brown.edu/courses/cs275/skip-btree.ppt (PPT)
相変わらず、P2Pへの応用に限定したくないネーミングで、理論派のアルゴリ
ズム屋さんらしいです。
＃だから、みんな SkipNet の方を読むんだな。
中身は、Skip Graphからそう変化していません。
ところで、Skip Graphって何？
と思った人は、主催 西谷さんの関西オフ会にご参加ください（宣伝）。
参照：[overlay-ja:61] Re: 関西オフ会の講師＆会場について
例によって、要点だけ記しておきます。
・structured P2Pの技術の一つ
・skip listをベースにしている。
・range search だけでなく DHTとしても使える。
・join,leaveのコストが log N
（通常のDHTでは、(logN)^2 ）
・固定サイズのルーティングテーブルを必要としない。
テーブルは Nの増加とともに伸長する。
・耐障害性の実現もシンプル
・ALMも素直に実現できる（最近知ったこと）
第２回DHT勉強会
http://toremoro.tea-nifty.com/tomos_hotline/2006/08/dht2dht_f9ea.html
では、「優れた DHTでもある Skip Graph に死角なし」みたいなことを言い、
みなさんの反響（反感？）を招きました。
このDHT勉強会、大変有意義でした。内容については、無印吉澤さんのページ
に詳しく書かれています。
http://muziyoshiz.jp/20061002.html
---
吉田 幹 y...@bbr.jp
Daishi Kato
さて、主に吉田さんにいろいろ聞いてみたいです。
まず、ハッシュを使わずにバランスをさせるというのはよいアイデアで、
今後他のオーバレイでも取り入れられるといいと思います。
#今まではCANとp-gridくらいか。
で、聞いてみたいのは:
・グラフ的には、Chordににている? Level 0がringになるので
・range queryできるのは1次元なのか
・ほんとにChordと同コスト? オーダは同じでも
・細かいところが理解できなかったが実装はできた?
・skip graphのDHTが実装できたなら評価してみたい
加藤
At Fri, 24 Nov 2006 12:16:22 +0900,
Miko Yoshida
In message, Daishi Kato <dai...@cb.jp.nec.com>-san wrote on
Mon, 27 Nov 2006 11:28:16 +0900...
> やっと、skip graphの論文を読みました。後半は頭に入らずとばしました。
おお、すばらしい。
後半というと、耐障害処理の部分ですね。
私も頭に入らなかったところです。(^^;;
> さて、主に吉田さんにいろいろ聞いてみたいです。
ハイ。
本当は、首藤さんのように明快なPPTを作って公開すればよいのですが、ちょ
っと余裕がないのですいません。
質問は大歓迎です。＞ ALL
> まず、ハッシュを使わずにバランスをさせるというのはよいアイデアで、
> 今後他のオーバレイでも取り入れられるといいと思います。
> #今まではCANとp-gridくらいか。
> で、聞いてみたいのは:
> ・グラフ的には、Chordににている? Level 0がringになるので
はい、似てます。
[overlay-ja:66] DHTの定義と比較 で挙げさせてもらった論文で、route
selection の話が出てきて、Ring構造は selection の数が多くて、その分、
耐性も高くなる、という話が出てきますが、
Skip Graphの場合も、そのような性質があるように思います。
Chord と違うところといえば、双方向になっているという点でしょうね。
ところで、厳密な話をすると、前と後ろをつないで ring にしたのは、
SkipNetからで、Skip Graphではそのところの言及はしていないように思いま
す。（まあ、理論系の論文なんで）
＃双方向リストを作ったら、当然頭と尻尾をつなぐでしょうけど。
ということは...
オリジナルでは、ring 構造を生かしたアルゴリズムにはまだなっていないと
いうことですね。（改良の余地あり）
> ・range queryできるのは1次元なのか
そうです。
そのため、地理的範囲のような多次元を扱う場合に、ヒルベルト関数とか使っ
て、1次元にマッピングするということをします。
> ・ほんとにChordと同コスト? オーダは同じでも
下手なコーディングしてないとすればそうです。
> ・細かいところが理解できなかったが実装はできた?
> ・skip graphのDHTが実装できたなら評価してみたい
どっちもできていますよ。
---
吉田 幹 y...@bbr.jp