skiplist&overlay-111030
- 1. 2011/10/29-30 5th sensor & overlay workshop Skip List Revisited! （再訪） 吉田 幹 BBR, PIAX Inc. ～探索アルゴリズムと構造化オーバーレイ、 両者の接点について考える～
- 3. なぜ、Skip listか （私は）構造化オーバーレイをこう捉えている “探索アルゴリズム” の適用領域が、1台のコンピュータ の内側から広域に拡がるネットワーキングの世界に展開 した形 特に、Pastry, Tapestry (Plaxtonのアルゴリズム), Kademlia を見るとそう感じる 起点ノードから見ると、木構造の探索 共通する原理は、対象空間をstepwiseに絞り込むため の構造化で、分割統治法（divide and conquer algorithm） ※ けれど、Chordは異なった構造を持っていて、2つの見方が存在するのは確 かです。（今回は前者） 既存研究の延長で構造化オーバーレイを捉える 構造化オーバーレイに既存研究にない要素を見出す 6
- 4. なぜ、Skip listか 構造化オーバーレイ Skip graphの登場 通常のkey検索、範囲検索をシンプルな形で実現 “探索アルゴリズム”のニューファイスであるskip listを巧 みに使っている ニューフェイス Skip list 新しい発想のバランス木新しい発想のバランス木 1970年代にKnuth博士によってまとめ上げられ、ほぼ仕事として 終わったと思われていた研究領域 バランシングのために“確率”を活用 そこに、分散システムを考える何かヒントがあるかも 7
- 5. Skip list 論文 W. Pugh, “Skip Lists: A Probabilistic Alternative to Balanced Trees,” Communications of the ACM 33, 6 (June 1990) ちなみに、WADS ’89（workshop, Aug 1989）での発表が最初 特徴 勝手にバランスするバランス木 木といっても実際には多段なリスト構造 これまでの厳格なバランシング処理とは違い、確率を使って緩や かなバランスを実現 データ構造とアルゴリズムの両面においてシンプル ノードの挿入?削除を簡単に行える 既存のバランス木と比べ高速 Lock-freeな実装が存在する 8
- 6. Skip list の構造 ノードはkey順に並ぶ レベル0のリストには全てのノードが含まれる レベルi-1に現れるノードはある確率pでレベルiに現れる（こ こでは簡単のため、p=1/2とします） 通常のバランス木と違い、ノードの挿入?削除の際にバラン シング処理が不要 HEAD TAIL 9 HEAD TAIL Level 2 Level 1 Level 0 13 21 33 48 75 99
- 7. Skip list を使った探索 上位レベルから下位レベルに降りる形で処理が進む 平均探索時間は、ノード数をNとして、O(log N) 全順序関係が定義できるデータならすべて key として使うこ とができる（数値、文字列など）。片寄りがあってもよい HEAD TAIL HEAD から Key “75” を探索 10 HEAD TAIL Level 2 Level 1 Level 0 13 21 33 48 75 99
- 9. バランス木（平衡木、balanced tree） 探索効率維持のため木を平衡状態にする必要がある 2分木（binary tree） …平衡2分探索木（self-balancing binary search tree） AVL tree Red-black tree N分木（N-ary tree） 2-3 tree 6 2-3 tree B-tree 12 1 2 3 4 5 ワーストケース O(N) の探索コスト 1 2 3 4 5 6 平衡状態の2分木 O(log N) の探索コスト
- 11. 2-3 tree ノードが2または3の子供を持つ 上限3をorder値と呼び拡張したのが、B-tree （1972年） key追加の時に、ノードの分割 削除の時に、ノードの併合を行う 14 http://ja.wikipedia.org/ より ノードの分割ノードの分割ノードの分割ノードの分割 2-3木の例木の例木の例木の例
- 13. 2-3-4 tree と Red-black tree B-tree（2-3-4木はその一種）と赤黒木の共通性 2-3-4木と等価なデータ構造を持つ赤黒木が存在する 2-3-4木における挿入、削除の操作は、赤黒木における 色のつけかえおよび回転の各操作と等価である 16 http://en.wikipedia.org/wiki/ より 2-3-4木を等価変換した赤黒木木を等価変換した赤黒木木を等価変換した赤黒木木を等価変換した赤黒木
- 14. Skip list vs. 既存のバランス木 AVL tree, 2-3 tree との性能比較 Skip listの論文より Java、TreeMapと ConcurrentSkipListMapの比較 17 Java、TreeMapと ConcurrentSkipListMapの比較 Java 6のスレッドセーフなskip list実装 TreeMap ConcurrentSkipListMap get,put,removeのコスト O(log N) O(log N) バランシング処理 要 不要 スレッドセーフ NG さらに、lock-free メモリ消費のオーバヘッド 3*N+α 6*N+α
- 15. Skip list についての素朴な疑問 p<1/2 の場合はどうなる? 確率（ばらつき）の影響は大丈夫? 探索木と同等に扱えるのか?? lock-free が可能な理由 18
- 16. p<1/2 の場合はどうなる? Skip listの高さは低くなるが、横方向にたどる回数が増える 論文によると、1/2～1/4はほぼ同じ計算コスト。分かりやす さから p=1/2 が用いられる 1 2 3 4 5 6 7 8 9 10head 高さ 19 1 2 3 4 5 6 7 8 9 10head 横方向
- 18. Skip listは探索木と同等に扱えるのか? 下図のようにマッピングできる 木の左リンク は で代用される リンク数が足りない場合、 を使って兄弟をたどる 3分木にした場合、 の代わりに青リンクを使う 21 1 2 3 4 5 6 7 8 9 10head 1 2 3 4 7 8 9 105 6
- 19. Skip listがlock-free可能な理由 ノードの挿入?削除の際に、バランシング処理を行う 必要がないため 単方向リストにおけるノードの挿入?削除（lock-free可能） の組み合わせで済む 一方、バランシング処理は一方、バランシング処理は 次のようなトランザクションを形成する 1. ノード挿入箇所の探索 2. バランシングの要不要判定 3. バランシング処理（色のつけかけ、回転など） 4. （必要に応じて）根の方向に、3を再帰処理 同時処理ができないことと、根方向に影響範囲が及ぶこ とが、lock-free化を困難にしている 22
- 20. Lock-free Skip List M. Fomitchev , E. Ruppert, “Lock-free linked lists and skip lists,” Proc of the 23th annual ACM symp, July 2004 23
- 21. ConcurrentSkipListMap lock-free実装 （ソースを見ると書いてある） * Head nodes Index nodes * +-+ right +-+ +-+ * |2|---------------->| |--------------------->| |->null * +-+ +-+ +-+ * | down | | * v v v * +-+ +-+ +-+ +-+ +-+ +-+ * |1|----------->| |->| |------>| |----------->| |------>| |->null * +-+ +-+ +-+ +-+ +-+ +-+ * v | | | | | 24 * v | | | | | * Nodes next v v v v v * +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ * | |->|A|->|B|->|C|->|D|->|E|->|F|->|G|->|H|->|I|->|J|->|K|->null * +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+ * * The base lists use a variant of the HM linked ordered set * algorithm. See Tim Harris, "A pragmatic implementation of * non-blocking linked lists" * http://www.cl.cam.ac.uk/~tlh20/publications.html and Maged * Michael "High Performance Dynamic Lock-Free Hash Tables and * List-Based Sets" * http://www.research.ibm.com/people/m/michael/pubs.htm. The * basic idea in these lists is to mark the "next" pointers of * deleted nodes when deleting to avoid conflicts with concurrent * insertions, and when traversing to keep track of triples * (predecessor, node, successor) in order to detect when and how * to unlink these deleted nodes.
- 22. “DHT=構造化オーバーレイ” ではない DHTは2層のモジュール構造になる DHTサービス層では、hash(key)をルーティング層に渡す ルーティング層では、受け取った値（=hash(key)）の近傍 値を探索key（skey）として持つノードへ要求を転送する put(key, value) pub(objId) join(grId), leave(grId) 25 Routing Layer Service Layer DHT DOLR ALM ??? route(skey, msg) deliver(skey, msg) ※ case of KBR put(key, value) value=get(key) pub(objId) unpub(objId) send(msg, objId) join(grId), leave(grId) multicast(msg, grId) anycast(msg, grId)
- 23. “DHT=構造化オーバーレイ” ではない 分散KVSもこの枠組みに属する Consistent hashingは右（左）最近傍探索 この場合、ルーティング層は通常フルメッシュ “構造化オーバーレイ” をシンプルにルーティング層 を指す用語と捉えたい オーバーレイネットワークの元々の意味からもオーバーレイネットワークの元々の意味からも 大半のDHT研究において、核となる部分はルーティング 層に関するものだし… Skip graphのように、ルーティング層のみを対象とした研 究もある DHTサービス層を前提とすることで制限付きのルーティ ング機能となっているという現状も 26
- 25. ルーティング層の独立性 探索木と同じ検索方式をルーティング層が持つこと ができたなら、 全順序関係が定義できる任意の型のkeyを扱える 範囲検索も可能 DHTのルーティング層は上位のサービス層に依存 しているしている 例えば、DOLR（Decentralized Object Location and Routing） ルーティング層で任意の型を扱えるなら、objIdを直接挿 入し、検索対象とすればよい しかしながら、objIdをセットできないため、DHTを対応表 として、間接的にobjIdを探すということをしている 28
- 26. ある日のつぶやき 29
- 27. ある日のつぶやき 30
- 28. まとめると 確率を使って、探索木を勝手にバランスさせる手法 Skip listの持つ革新的原理 分散化への効果 マルチコアシステムにおける lock-free ネットワークシステムにおける skip graph DHTが前提とするルーティングDHTが前提とするルーティング 対象とするドメイン key（ID）が一様に分布する固定整数空間 既存の探索アルゴリズムでは 順序関係のみが定義されておればよい全順序集合 後者を実現する構造化オーバーレイはまだ少ない Skip graph, Chord# … 31
- 29. 見えてくる研究の方向性 探索アルゴリズムの知見を構造化オーバーレイに 多次元範囲検索や区間検索 Kd-tree, R-tree, interval tree など log_2 N --> log_k N に 2分木からN分木へ 鍵は、確率によるバランシング 32
- 30. 集中 分散 B-treeB-tree plaxtonplaxton XORXOR Chord#Chord# ChordChord FRTFRT AVL treeAVL tree quadtreequadtree trietrie octreeoctree 33 探索アルゴリズムの研究探索アルゴリズムの研究探索アルゴリズムの研究探索アルゴリズムの研究 DHTアルゴリズムアルゴリズムアルゴリズムアルゴリズム の研究の研究の研究の研究 構造化オーバーレイの研究構造化オーバーレイの研究構造化オーバーレイの研究構造化オーバーレイの研究 skip listskip list interval treeinterval tree kd-treekd-tree R-treeR-tree skip graphskip graph RKSGRKSG 確率確率確率確率
- 31. いろいろ Skip graphを分解すると Skip list 確率によるバランシング membership vector 分散化の手法 バランシングと分散化について、別の手法を編み出バランシングと分散化について、別の手法を編み出 すと、skip graph以外のものが作れるかも Plaxtonに応用できれば、普通に使えるオーバーレ イが作れるかも 確率の持つデメリットの回避方法も考えれる 近傍のノードをチェックするなど 残る課題、並行joinや修復処理は次のDDLLで 34