構造化オーバーレイネットワークに適した 分散双方向連結リストDDLL 安倍 広多 (大阪市立大学) 吉田 幹 (BBR) 2010.09.17 DPS144

分散双方向連結リストとは ネットワークで接続された複数のノードが 双方向連結リストを構成 各ノードは右ノードと左ノードへのポインタ (IPアドレスなど)を保持 各ノードが保持するキーによってソートされている 循環リストを想定 2010.09.17 DPS144

分散双方向連結リストの応用例 自律分散的に動作する分散双方向連結リストが必要 構造化オーバーレイ(P2P)ネットワークでよく用いられる Chord, Chord#, Symphony, Skip graph, SkipNet, etc. 自律分散的に動作する分散双方向連結リストが必要 Skip Graph James Aspnes and Gauri Shah "Skip Graphs", ACM Trans. on Algorithm, 2007 2010.09.17 DPS144

分散双方向連結リストの難しいところ ノードは勝手なタイミングで挿入・削除 ノードは削除手続きを実行せずに（勝手に）離脱・故障 複数ノードが並行して挿入・削除するかも ノードは削除手続きを実行せずに（勝手に）離脱・故障 これらを考慮したアルゴリズムが必要 ノード挿入 ノード削除 リンク修復 2010.09.17 DPS144

従来の手法 楽観的アプローチ (Chordなど) 排他制御アプローチ 周囲のノードを気にせずに挿入・削除 連結リストを理想的な状態に戻すために定期的に修復 利点: リンク修復が容易 欠点: （理想的な状態ではない間）到達できないノードが存在 排他制御アプローチ 分散排他制御を用いて厳密に挿入・削除 利点: 挿入されているノードに必ず到達できる 欠点: 障害からの回復が困難（ノードが故障した場合，ロックされたままに） 挿入されているノードに必ず到達可能で，かつ 障害からの回復が容易なアルゴリズムが欲しい 2010.09.17 DPS144

DDLLアルゴリズム （障害を考慮しないバージョン） 2010.09.17 DPS144

前提 ノードの実行速度は任意 ノード間の通信路： 全てのキーはユニーク（重複しない） 送信したメッセージはいずれ到着 伝送時間の上限はない FIFOでなくてもよい 全てのキーはユニーク（重複しない） キーの後ろに十分なビット数の乱数を 付け加えれば良い 2010.09.17 DPS144

DDLLでの挿入・削除の基本的な流れ 挿入・削除のどちらの場合でも まず，左ノードの右リンクを書き換える（右リンク更新処理） 次に，右ノードの左リンクを書き換える（左リンク更新処理） 挿入 削除 SetRメッセージ 右リンク更新要求 SetRAckメッセージ 確認応答 SetLメッセージ 左リンク更新要求 2010.09.17 DPS144

右リンク更新処理 | 提案手法 分散排他制御を用いずに安全に右リンクを更新 a-b間にノードuを挿入する場合: uは左リンクをaに，右リンクをbに張る uはSetRメッセージで新リンク先(u)とaの現在の右リンク先(b)をaに送信 aは，aが削除中ではなく，かつ右リンク先が等しい場合に限り 右リンクを更新し，SetRAckを返す 複数ノードが同時にa-b間に挿入しようとしても，SetRに成功するのは1つ → 分散排他制御不要 aの右リンクがuになったとき，uの右リンクはbになっている → 右リンクは途切れない（一瞬たりとも） 2010.09.17 DPS144

右リンク更新処理 | 例 複数ノードが同時にa-b間に挿入しようとしても，SetRに成功するのは1つ → 分散排他制御不要 aの右リンクがuになったとき，uの右リンクはbになっている → 右リンクは途切れない（一瞬たりとも） 2010.09.17 DPS144

? 左リンク更新処理 | 問題1 右リンクの更新に成功したら左リンクを更新 SetLメッセージの到着順序はSetRの順番通りとは限らない! → SetRAckを受け取ったらSetLメッセージを送信 SetLメッセージの到着順序はSetRの順番通りとは限らない! ? 2010.09.17 DPS144

左リンク更新処理 | 問題1の解決法 SetLメッセージにシーケンス番号を付与 各ノードに右リンク番号と左リンク番号を割り当てる SetLメッセージを送信する時点で同一ノードを宛先とする SetLメッセージのシーケンス番号を決定できる → SetLメッセージを受信順序に関係なく処理可能 各ノードに右リンク番号と左リンク番号を割り当てる 左リンク番号: 今までに受信したSetLメッセージの最大シーケンス番号 挿入直後は 0 右リンク番号: 右ノードの左リンク番号 基本的に左右のリンク番号は等しい（過渡的な状態を除けば） 2010.09.17 DPS144

左リンク更新処理 | リンク番号の更新方法 ノードが受信するSetLメッセージに， 送信時点でシーケンス番号を付与できる 挿入 削除 2010.09.17 DPS144

SetLの到着順序が入れ替わっても問題ない！ 左リンク更新処理 | 同時挿入の例 Dの右リンク 番号=6 Bの右リンク 番号=4 Cの右リンク 番号=5 SetLの到着順序が入れ替わっても問題ない！ 2010.09.17 DPS144

左リンク更新処理 | 問題2 左リンクを常に使えるようにするために... このままだと左リンクが削除済みノードを指す場合がある 2010.09.17 DPS144

左リンク更新処理 | 問題2の解決法 参照カウンタ(ref)の導入 左リンクによって参照されている数をカウント SetRメッセージを受信 → 1加算 UnrefLメッセージを受信 → 1減算 SetLを受信したノードは変更前の左ノードにUnrefLメッセージを送信し，参照されなくなったことを通知 ノードは ref = 0 になれば停止可能 2010.09.17 DPS144

検索処理 DDLLでは これを考慮してリストをトラバースする 必要がある 右リンクは常に正しいノードを指す 左リンクは常に正しいとは限らない 左リンクを使うときは注意が必要 詳細は省略 2010.09.17 DPS144

DDLLアルゴリズム （障害を考慮するバージョン） 2010.09.17 DPS144

リンク修復 故障したノードをバイパスして連結リストを修復 各ノードは左側のリンクを修復 前提: 修復して接続するノードは求められる 左リンク番号を単調に増加させるため 各ノードは，定期的に左ノードをチェック 前提: 修復して接続するノードは求められる 左側のk個のノードを保持しておくなど 2010.09.17 DPS144

修復時のリンク番号の問題 単純に左リンク番号を+1すると困る例 Bの故障直前にXが挿入したが，Cはそのことを知らずに修復開始 Cを右リンクとするノードが2つ存在し(A, X)，右リンク番号も同一! X-C間に新たなノードYが挿入されると，Cの左リンクはYを指してしまう 2010.09.17 DPS144

解決策(リンク番号の拡張) リンク番号を(g, s)形式に拡張 gが大きい方が優先 リンク修復前の状態には戻らない 2010.09.17 DPS144

各ノードが保持する変数 ノードの状態 キー 右リンク（右ノードへのポインタとキー） 左リンク（左ノードへのポインタとキー） 右リンク番号 out リストから外れている ins 挿入するために左ノードにSetR送信中 inswait insでSetRNakを受信し，リトライ待ち in 少なくとも右方向は挿入済み del 削除するために左ノードにSetR送信中 delwait delでSetRNakを受信し，リトライ待ち grace 削除時に，refが0になるのを待機中 キー 右リンク（右ノードへのポインタとキー） 左リンク（左ノードへのポインタとキー） 右リンク番号 左リンク番号 参照カウンタ (ref) 2010.09.17 DPS144

詳細な アルゴリズム 2010.09.17 DPS144

本発表で割愛した点 検索アルゴリズム 修復時の参照カウンタの取り扱い ノード故障誤検出からの修復 挿入・削除時のノード故障の取り扱い 生きているノードを(誤って)故障していると判断した場合でも回復できる 挿入・削除時のノード故障の取り扱い ノードの再挿入の取り扱い 2010.09.17 DPS144

まとめ 分散双方向連結リストを構築・維持する自律分散アルゴリズムDDLLを提案 DDLLの特徴 複数のノードが並行して挿入・削除する場合でも， 連結リストの構造は常に維持 挿入されたノードには必ず到達できる（ネットワーク分断が発生しない限り） 分散排他制御を用いない ⇒ ノード故障時に容易に修復可能 アルゴリズムは単純で容易に実装可能 構造化オーバーレイネットワークにDDLLを適用した場合， 信頼性の向上 リンク修復処理の簡略化 今後の課題 DDLLを用いた構造化オーバーレイネットワークの実装と評価 2010.09.17 DPS144

2010.09.17 DPS144

予備スライド 2010.09.17 DPS144

検索アルゴリズム 前提: 挿入しようとするノードuは何らかの方法で挿入済みのノードqを知っている n:=qとする．q < uならば p:=q.l，そうでなければ p:=q.r ord(n, u, n.r) = true ∧ n.s ≠ grace → n と n.r がそれぞれ u の左ノード，右ノードの候補 ord(n,u,p) = true ∧ n.s ≠ grace → p := n; n := n.r とし，2に戻る p := n; n := n.l とし，2 に戻る 2010.09.17 DPS144

楽観的アプローチの例 | Chord A-D間にBとCを並行挿入した場合 定期的にスタビライズ処理を行って正常にする 到達できないノードが存在! u.join() left = nil; right = b; u.stabilize() x = right.left; if (x ∈ (u, right)) right = x; right.notify(u); u.notify(n') if (left = nil or n' ∈ (left, u)) left = n' 2010.09.17 DPS144

排他制御アプローチとその問題点 例: a-b間にuを挿入する場合，aで排他制御するパターン 問題点1: 障害に弱い 問題点2: 性能上の問題 aはロックされていなければロックし，uにロック完了通知を送信 応答を受信したuはaの右リンクとbの左リンクを変更 uはaにロック解放要求を送信 問題点1: 障害に弱い step 4の前にuが故障したらロックが解放されない タイムアウトでロック解放する方法は危険 問題点2: 性能上の問題 ロックしている間，aの右側に他のノードは挿入できない ロックしている間，bは削除できない 2010.09.17 DPS144

SetLの到着順序が入れ替わっても問題ない BとCが同時にAとDの間に挿入 同時挿入の例 右リンク ミスマッチ SetLの到着順序が入れ替わっても問題ない 2010.09.17 DPS144

リンク不整合から の回復 EがCを故障していると誤って判定した場合からの回復 2010.09.17 DPS144