kibayos_ov_090922
- 1. 2009/5/8-9 3rd sensor overlay workshop (original) 2009/9/22 改訂（詳細アルゴリズムを削除、unbreakableを追加） 考察: 构造化オーバレイの一贯性保証 考察 構造化オ バレイの 貫性保証 ～Skip Graph を例に～ 吉田 幹 BBR / PIAX Inc. 大阪大学
- 2. Agenda Skip Graph再訪 基本アルゴリズムのおさらい 整合性維持の困難さ 构造化オーバレイの一贯性保証について考察して 構造化オ バレイの一貫性保証について考察して みる 技術トピック 技術トピ ク ロック不要の排他制御 Windows Azure 再考（クラウド事例） 考 ド事 クリプキ構造を使ったシステム検証 壊れても蘇る構造化オーバレイ 2
- 3. Skip Graph再訪 Ski G h再訪 基本アルゴリズムのおさらい 整合性維持の困難さ
- 4. Skip List ノードはkey順に並ぶ レベル0のリストには全てのノードが含まれる レベルi-1に現れるノードはある確率pでレベルiに現れる（こ こでは簡単のため、p=1/2とします） 通常のバランス木と違い、ノードの追加?削除の際にバラン 通常のバランス木と違い ノ ドの追加 削除の際にバラン ス化の処理が不要 HEAD TAIL Level 2 L l 33 Level 1 L l 13 33 48 Level 0 L l 13 21 33 48 75 99 4
- 5. Skip List を使った探索 上位レベルから下位レベルに降りる形で処理が進む 平均探索時間は、ノード数をNとして、O(log N) 平均探索時間は、 ド数を して、 ( g ) 全順序関係が定義できるデータならすべて key として使うこ とができる（数値、文字列など）。片寄りがあってもよい HEAD から Key “75” を探索 75 HEAD TAIL Level 2 L l 33 Level 1 L l 13 33 48 Level 0 L l 13 21 33 48 75 99 5
- 6. Skip Graph の構成 レベルi では membership vectorのプレフィックスの i桁が 一致するノード同士リンクをはる membership vector “レベルi-1に現れるノードは確率1/2でレベルiに現れる”性質を実現 するための2進整数（ランダムに分布） DHTでいうノードIDに相当 DHTでいうノ ドIDに相当 Key 21 33 Level 2 13 48 75 99 21 75 99 Level 1 13 33 48 Skip List Level 0 L l 13 21 33 48 75 99 Membership vector 000 100 010 001 110 111 6
- 7. Skip Graphでのkey探索 個々のノードから見ると、Skip List と同じ構造（アミ掛け部 分） Skip List と同じ探索アルゴリズムを実行 範囲探索も同様にできる key “33”のノードから key “75” を探索 Key 21 33 Level 2 13 48 75 99 21 75 99 Level 1 13 33 48 Skip List Level 0 L l 13 21 33 48 75 99 Membership vector 000 100 010 001 110 111 7
- 8. Skip Graphでのノード追加 (1) introducer（ここでは99）から挿入位置を探索 ? key “48” を見つける レベル0のリンクに新規ノードを挿入 21 33 Level 2 introducer 13 48 75 99 21 75 99 Level 1 13 33 48 Level 0 13 21 33 48 75 99 40 011 000 100 010 001 110 111 8
- 9. Skip Graphでのノード追加 (2) レベル1から上位レベルへ順番に、プレフィックスの一致す るノードから成るリンクに新規ノードを挿入 21 33 40 Level 2 13 48 75 99 21 75 99 Level 1 13 33 40 48 Level 0 13 21 33 40 48 75 99 000 100 010 011 001 110 111 9
- 10. Coffee Break: Skip List Java 6 から skip list が使えるようになっています java.util.concurrent.ConcurrentSkipListMap うれしいことにスレッドセーフ さらに、SortedMap より強力な NavigableMap が登場し、今 までできなかった次の処理ができるようになりました ま きなか た次 処理が きるよう なりま た 指定したkey以上の大きさを持つ最小のkeyを取得 等 TreeMap ConcurrentSkipListMap は次のように使い分け T M とC tSki Li tM ましょう TreeMap ConcurrentSkipListMap get,put,removeのコスト log N log N バランス処理 要 不要 スレッドセーフ NG OK メモリ消費のオーバヘッド 3*N+α 6*N+α 10
- 11. 整合性維持の困難さ Skip Graphは、Skip Listと違い、探索に用いるグラフ構造が ネットワーク全体に分散されている 探索アルゴリズムを正しく機能させるためには、分散配置された構 造の維持が必要 これは、構造化オーバレイ全般の特徴 これは 構造化オ バレイ全般の特徴 構造の変更を起こす処理（join/leave等）については、なんら かの同期（synchronization）処理が必要 同時に起こりうるjoin/leaveへの対応 構造が緻密であるほど大変 ノードの障害、予期できないダウンについては、構造の修復 処理が必要 Skip Graphの場合は、Kademlia, Pastry等と違い、経路の 冗長性が小さいため、困難さが増している 11
- 12. Skip Graph 論文の記載では... 2003年の最初の論文では、 同時に起こりうるjoin/leaveの処理では、なんらかの排他処理を行う 必要があると記載 経路表の不整合を検知するための必要十分条件が提示され、修復 のための縫合（zipper）アルゴリズムについて記載 2007年に、Skip Graphの改訂論文（journal版）が出る J. Aspnes and G. Shah, “Skip Graphs,” ACM Transactions on p , p p , Algorithms, 3(4):37, Nov 2007. この論文で、2003年のやり方だと最悪 O(N) になることがあ ると否定 ると 定 縫合アルゴリズムの記載がなくなる !! 同時j i /l 同時join/leaveについては、排他処理を避ける一手法として については 排他処理を避ける 手法として “unbreakable” なアプローチ（本資料最後に紹介）が紹介さ れる 12
- 13. 构造化オーバレイの一贯性保証 を考察してみる
- 14. 构造化オーバレイの一贯性保証とは? 次のように分類 1. 構造を能動的に変化させるとき（挿入、削除）に保つべき一貫性 2. 障害修復が対象とする一貫性 3. 不整合を許容する仕組み ? システム全体の 貫性に いては総合的に捉える必要がある システム全体の一貫性については総合的に捉える必要がある アプローチはいろいろ Skip Graphの場合 1.は、双方向リンクドリスト構造における挿入、削除 2003年論文では、これは一貫性を持ったアトミック（分散排他制御を推 奨）。2007年論文では、soft stateで保証 Chordの場合 1.は、単方向リンクドリスト構造における挿入、削除 1 は 単方向リンクドリスト構造における挿入 削除 逆方向リンクは補助的なので アトミックではない。join時に完結しない 14
- 15. Skip Graph（2003年）の方法を再考 挿入、削除時の一貫性 論理的にパ フェクトにできそうでできない? 論理的にパーフェクトにできそうでできない? 通信の失敗を正確に観察するすべがない 高負荷（渋滞）による通信エラーも起こりうる、等 よって、2.の障害修復でカバーする必要がある 障害修復の困難さ ノードの予期せぬ一時停止や再開、突然死について、外 部から同定はできない 事象について、ケースを細かく分類しても仕方ない おかしいと観察されたリンクは壊れた（実は休止してて壊れてな いかもしれないが）として、修復するしかない 休止したノードが再開した場合、修復行為が不整合を発生させ ることも起こる、等 ることも起こる 等 15
- 16. なぜ難しいか 神さまはいない 障害修復処理自体が構造を変化させ、それがまた障害 障害修復処理自体が構造を変化させ それがまた障害 修復処理の対象となる 分散システムのパラダイムシフト 見ようとしても見えない ハンゼンベルクの不確定性原理（量子論） 同期は取れない 時間および状態観測における相対性理論（ニュートン-->アイン シュタイン） 16
- 17. ほしい指標 安定化条件 「不整合の検出 >修復」の繰り返しによって特定の時間 「不整合の検出-->修復」の繰り返しによって特定の時間 内に整合状態に到達することの保証 アルゴリズムの性質として最低限必要 故障率が高いと成り立たないため、このための条件も必 要 例えば、unbreakableでは、 「Bootstrap nodes が弱連結（weakly connected）であること」 不整合の許容度 不整合を含んだ状態での探索処理の成功率等 迂回経路は許容度を高めるが、もちろんパーフェクトで 迂回経路は許容度を高めるが もちろんパ ク はない 17
- 18. 技術トピック 技術トピ ク ロック不要の排他制御 Windows Azure 再考（クラウド事例） クリプキ構造を使ったシステム検証 壊れても蘇る構造化オーバレイ
- 19. ロック不要の排他制御
- 20. Lock Free Synchronization (1) 今日は紹介だけ 情報は入手しやすいので、是非キャッチアップを Wikipedia: Non-blocking synchronization など http://en.wikipedia.org/wiki/Lock-free_and_wait-free_algorithms 従来（pessimistic）に対し optimisticなアプローチ 従来（pessimistic）に対し、optimisticなアプローチ 「前提条件を完全に揃えてから、目的の処理を行う」 のでなく、「前提条件を揃えないで、目的の処理を行う」 途中不整合があれば検知して、retryし、結果的に一貫性を出す CAS（Compare and Swap）などの atomic命令を組み合わ せて実現する non-blocking な 期 取り方 実現する bl k な同期の取り方 単方向リンクドリスト、queue など、基本データ構造を対象と した実装例が多くある SMP上で動作するOSのカーネル実装（Massalin and Pu, 1992）など 意外と古い 20
- 21. Lock Free Synchronization (2) 1マシン内の処理といえども、分散を前提にしないといけな い昨今 マルチCoreなCPU, out-of-order な命令実行 ?まるでネットワーク メモリバリアという手段があるけど、これは使わないお約束 wait f と う概念もあ たり freeという概念もあったり、software transactional f l memory との関連も深かったり、これから楽しい研究分野 wait free lock freeの上位条件。決められた有限時間（処理ステップ）内に処理が 完了する software transactional memory 元はハードウェアを対象に生まれたoptimisticアプローチ。ソフトウェア での有用性も認められて、こう呼ばれるようになった 、 21
- 22. 単方向リンクドリストの場合 ノードの挿入、削除、traverseが同時に起こる。 その状態で、すべて（挿入、削除、traverse）がうまく処理で きないといけない 道路工事を車の行き来に支障なく行うようなもの 同時に挿入と削除が起こると普通はおかしくなる 時 挿 と削除が起 ると普通はおか くなる 例：1->2->4 に対し、3の挿入と、2の削除を同時に行う 同時に起こる挿入と削除によって、挿入が無効化 時 起 挿 除 、挿 効 22
- 23. 単方向リンクドリストのLock-Freeな例1 補助（Auxiliary）ノードを使う J.D. Valois, “Lock-Free Linked Lists Using Compare-and Swap,” Proc of the 14th Symposium on Principles of Distributed Computing, 1995. 2の削除と3の挿入を同時に行う 1 2 4 Auxiliary node 3 1 2 4 3 23
- 24. 単方向リンクドリストのLock-Freeな例2 削除マークを使う T. L. Harris, “A pragmatic implementation of non-blocking linked-lists,” Proc of the 15th International Symposium on Distributed Computing, 2001. 2段階のノード削除 24
- 25. Lock-free Skip List M. Fomitchev , E. Ruppert, “Lock-free linked lists and skip lists,” Proc of the 23th annual ACM symp, July 2004 25
- 26. ConcurrentSkipListMap 実は、Lock-free （ソースを見ると書いてある） * Head nodes Index nodes * +-+ right +-+ +-+ * |2|---------------->| |--------------------->| |->null * +-+ +-+ +-+ * | down | | * v v v * +-+ +-+ +-+ +-+ +-+ +-+ * |1|----------->| |->| |------>| |----------->| |------>| |->null * +-+ +-+ +-+ +-+ +-+ +-+ * 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. 26
- 27. 双方向リンクドリストの実装も Hakan Sundell et al., “Lock-free deques and doubly linked lists,” Journal of Parallel and Distributed Computing, July 2008. 単方向リンクドリストと比べると、doubly はやはり複雑 ネットワーク環境だと、 マルチプロセッサ環境で現れないエラー（通信エラー）を想 定しないといけない 構造化オーバレイ（Skip Graph） の適用にはまだ距離が 構造化オ バレイ（Ski G h） への適用にはまだ距離が ありそう 27
- 28. Windows Azure 再考
- 29. Windows Azure 様々なサービスを24時間、365日稼働させるための Cloud向けOS機能の提供（SDK） Key-value Store の機構にDHTを採用 …. … Service 1 Service 2 Service 3 Service N ※MS: Windows Azure 資料より 29
- 30. ※MS: Windows Azure 資料より 200 180 210 Routing Table at Node 64: 174 218 Successor = 76 151 Predecessor = 50 225 Neighborhood N i hb h d = (83, 76, 50, 46) (83 76 50 Routing nodes = (200, 2, 30, 46, 50, r7 250 64, 64, 64, 64, 64, 135 83, 98, 135, 200) r6 r-6 2 120 r5 r-5 17 103 Routing is the basis 98 r4 30 for building distributed r-4 90 4 40 hash t bl (DHT ) h h tables (DHTs) 83 76 46 64 50
- 31. ※MS: Windows Azure 資料より Time = tt00 Time = 83 83 46 76 76 50 64 Time = t1 Node failed 83 46 76 50 64 61 New Node arrived Time = t2 Ring reconfigured 83 46 Failures Detected 50 61
- 32. どうでしょう? 両方向Chordって、感じ なぜ、双方向リンクドリストを選んだんだろう? なぜ 双方向リンクドリストを選んだんだろう? クラウド環境だと一貫性保証はできる話なのかもし れない 32
- 33. クリプキ構造を使ったシステム検証 分散システムのテストは困難 時相論理（クリプキ構造）を使った検証の自動化が研究されている ※Top SE 分散システムのモデルリングと検証より（2008.8） 33
- 34. クリプキ構造 状態を分散する各プログラムのプログラムカウンタ（時間の 代用）と共通変数の組により表す 状態遷移を計算することで以下を検証 到達可能性：初期状態から特定の状態へ到達できる 安全性：望ましくない状態へ陥らない 活性：望ましい状態へ必ず到達できる 状態遷移図 ※Top SE 分散システムのモデルリングと検証より（2008.8） 34
- 36. Unbreakable 構造化オーバレイ ※命名（“unbreakable” のところ）は首藤さんww 従来は、 参加?離脱?安定化の各処理において、常に、トポロジ が理想的もしくはそれに近い状態が前提 安定化は、トポロジに生じた不整合を修復するという前提 トポロジが理想状態にない場合、安定化は機能障害に 陥る 頻繁な参加?離脱によって、トポロジが分断される危険 性がある トポロジが分断されると、部分トポロジが理想的な状態にあっても回復 はほぼ不可能 これに対し、どんな状態からでも（再）構成できる 維持プロトコルのみからなる。参加 離脱に特別の処理 維持プロトコルのみからなる。参加?離脱に特別の処理 は要らない 36
- 37. Unbreakable の一歩（Chordの改良） 論文 D. Liben-Nowell, H. Balakrishnan, and D. R. Karger, “Analysis of the evolution of peer-to-peer systems,” I P l i f ” In Proc of the 21 Annual f h 21st A l Symposium on PODC, 2002. 成果 half-life（Nノードの倍増?半減時間）というmetricを導入 Chord を維持するための安定化（idealization）の起動頻度を推定 安定化処理を強化し、任意のconnected な状態からChordを再構成できる ことを示した A weakly ideal loopy network Network with appendages state 37
- 38. Unbreakable の（たぶん）最初の成果 論文 Shaker, A. and Reeves, D. S., “Self-stabilizing structured ring topology P2P systems,” In Fifth IEEE International Conference on systems Peer-to-Peer Computing (P2P 2005), Sep. 2005. 成果 RN（Ring Network）プロトコルを提示 Chordと同様のトポロジを持つ構造化オーバレイを維持する 任意の状態から正しいトポロジを再構成できることを示した Bootstrap nodes が弱連結（weakly connected）であることが前提 安定化に要するメッセージ数 探索失敗率 と ホップ数 38
- 39. ご清聴ありがとうございました