More Related Content
Similar to 区間をキーとして保持する分散KVSの効率的な実現法 (9)
区間をキーとして保持する分散KVSの効率的な実現法
- 3. 分散 KVS(Key-Value Store) とは Google, Amazon, Facebook など 分散 KVS get( 156 ) -> A Key は 単一 の値 417 -> B 871 -> Y 156 -> A 324 -> R Key -> Value 膨大なデータを扱う 大規模分散システム
- 4. 1 時 4 時 2 時 7 時 5 時 8 時 4 時 5 時 区間を持ったデータを扱うことは難しい ! 分散 KVS 上で 例:セッションログ管理 ← C さん ← B さん ← A さん ← D さん
- 5. 1 時 4 時 2 時 7 時 5 時 8 時 4 時 5 時 区間を持ったデータを扱うことは難しい ! 分散 KVS 上で 例:セッションログ管理 分散KVSのキーは 単一の値 だから ... ← C さん ← B さん ← A さん ← D さん
- 6. 1 時 2 時 5 時 4 時 5 時 区間を持ったデータを扱うことは難しい ! 分散 KVS 上で 例:セッションログ管理 Key ← C さん ← B さん ← A さん ← D さん
- 7. 1 時 2 時 5 時 4 時 5 時 区間を持ったデータを扱うことは難しい ! 分散 KVS 上で 例:セッションログ管理 3 時~ 6 時に ログインしていた人を検索したい ← C さん ← B さん ← A さん ← D さん
- 8. 1 時 2 時 5 時 4 時 5 時 区間を持ったデータを扱うことは難しい ! 分散 KVS 上で 例:セッションログ管理 検索されない 3 時~ 6 時に ログインしていた人を検索したい ← C さん ← B さん ← A さん ← D さん
- 11. Range Key Skip Graph + 区間をキーとして扱える 構造化オーバーレイネットワーク Range Key 包含キー L0 L1 L2 L3 Skip Graph がベース
- 12. 1 時 4 時 2 時 7 時 5 時 8 時 4 時 5 時 Range Key Skip Graph 包含キーをたどって検索 Range Key 3 時~ 6 時に ログインしていた人を検索したい 包含キー
- 13. Range Key Skip Graph (2)データの冗長性について考慮されていない (1)領域計算量や挿入・削除のコストが最悪 O(n) n: Range Key の数 ※最悪の場合の例 問題点
- 15. 提案手法の流れ (アイディア) ・区間を 2 次元平面上の 1 点で表現 区間に対する範囲検索を 2 次元平面上の範囲検索に置き換える ・多数の区間 ( 点 ) を分散管理するために Znet を用いる 研究の目的 「区間をキーとして扱える 効率的な分散 KVS の構成法を提案すること」
- 16. 1 時 4 時 2 時 7 時 5 時 8 時 4 時 5 時 (1) 区間を 2 次元平面上の 1 点で表現 例:セッションログ管理 ← C さん ← B さん ← A さん ← D さん 例えば,Aさんの場合
- 17. (1) 区間を 2 次元平面上の 1 点で表現 y x 下限値をXとする 上限値をYとする A(4, 5 ) 4 5 A さんが ログインしていた区間 [4 , 5]
- 18. (1) 区間を 2 次元平面上の 1 点で表現 y x D(1, 4 ) 下限値をXとする 上限値をYとする ← A さん ← B さん ← C さん A(4, 5 ) C(2, 7 ) B(5, 8 ) ← D さん
- 19. (1) 区間を 2 次元平面上の 1 点で表現 y x D(1, 4 ) 下限値をXとする 上限値をYとする A(4, 5 ) C(2, 7 ) B(5, 8 ) y ≧ x
- 20. 1 時 4 時 2 時 7 時 5 時 8 時 4 時 5 時 ( 2 ) 区間に対する範囲検索 3 時~ 6 時に ログインしていた人を検索したい ← C さん ← B さん ← A さん ← D さん
- 21. 1 時 4 時 2 時 7 時 5 時 8 時 4 時 5 時 ( 2 ) 区間に対する範囲検索 3 時~ 6 時に ログインしていた人を検索したい ← C さん ← B さん ← A さん ← D さん ① 指定した検索範囲に 真に含まれる区間 ( 点 ) を検索する場合
- 22. 1 時 4 時 2 時 7 時 5 時 8 時 4 時 5 時 ( 2 ) 区間に対する範囲検索 3 時~ 6 時に ログインしていた人を検索したい ← C さん ← B さん ← A さん ← D さん ② 指定した検索範囲と 重なりがある区間 ( 点 ) を検索する場合
- 23. ① 指定した検索範囲に 真に含まれる区間 ( 点 ) を検索 y x D(1, 4 ) A(4, 5 ) C(2, 7 ) B(5, 8 ) 3 時 ~ 6 時 ← A さん ← B さん ← C さん ← D さん
- 24. ① 指定した検索範囲に 真に含まれる区間 ( 点 ) を検索 y x D(1, 4 ) A(4, 5 ) C(2, 7 ) B(5, 8 ) 3 時 ~ 6 時 ← A さん ← B さん ← C さん ← D さん 3
- 25. ① 指定した検索範囲に 真に含まれる区間 ( 点 ) を検索 y x D(1, 4 ) A(4, 5 ) C(2, 7 ) B(5, 8 ) 3 時 ~ 6 時 ← A さん ← B さん ← C さん ← D さん 3 6
- 26. ① 指定した検索範囲に 真に含まれる区間 ( 点 ) を検索 y x D(1, 4 ) A(4, 5 ) C(2, 7 ) B(5, 8 ) 3 時 ~ 6 時 ← A さん ← B さん ← C さん ← D さん 3 6
- 27. ① 指定した検索範囲に 真に含まれる区間 ( 点 ) を検索 y x D(1, 4 ) A(4, 5 ) C(2, 7 ) B(5, 8 ) 3 時 ~ 6 時 ← A さん ← B さん ← C さん ← D さん 3 6 検索領域
- 28. ① 指定した検索範囲に 真に含まれる区間 ( 点 ) を検索 y x D(1, 4 ) A(4, 5 ) C(2, 7 ) B(5, 8 ) 3 時 ~ 6 時 ← A さん ← B さん ← C さん ← D さん 3 6 この 2 次元平面上を 検索すると ...
- 29. ① 指定した検索範囲に 真に含まれる区間 ( 点 ) を検索 y x D(1, 4 ) A(4, 5 ) C(2, 7 ) B(5, 8 ) 3 時 ~ 6 時 ← A さん ← B さん ← C さん ← D さん 3 6
- 30. ① 指定した検索範囲に 真に含まれる区間 ( 点 ) を検索 y x D(1, 4 ) A(4, 5 ) C(2, 7 ) B(5, 8 ) 3 時 ~ 6 時 ← A さん ← B さん ← C さん ← D さん 3 6 区間に対する範囲検索 ↓ 2 次元平面上の 範囲検索に置き換え可能
- 31. ② 指定した検索範囲に 重なりがある区間 ( 点 ) を検索 y x D(1, 4 ) A(4, 5 ) C(2, 7 ) B(5, 8 ) 3 時 ~ 6 時 ← A さん ← B さん ← C さん ← D さん 3 6
- 32. 提案手法の流れ (アイディア) ・区間を 2 次元平面上の 1 点で表現 区間に対する範囲検索を 2 次元平面上の範囲検索に置き換える ・多数の区間 ( 点 ) を分散管理するために Znet を用いる ここまで説明終了 研究の目的 「区間をキーとして扱える 効率的な分散 KVS の構成法を提案すること」
- 33. ・検索ホップ数: O(log m) m:Znet に参加している物理ノード数 多数の区間 ( 点 ) の分散管理方法 ・複数のノードにデータを冗長配置 ・空間充填曲線( Z 曲線) Skip Graph + Znet: 多次元データを効率よく分散管理するための 構造化オーバーレイネットワーク y x L0 L1 L2 L3
- 34. 空間充填曲線( Z 曲線) 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 ・ ・ ・ ・ ・ ・ y x Z 曲線は 2 次元空間を埋め尽くす 2 次元情報を 1 次元上で管理する
- 35. [Znet] 負荷分散処理 y x ノード挿入時 高負荷なノードの 担当領域を分割,担当する 負荷の平準化 物理ノード A B C D E F G
- 36. Z 曲線 + Skip Graph y x
- 37. Z 曲線 + Skip Graph y x 検索範囲
- 38. Z 曲線 + Skip Graph y x L0 L1 L2 L3 検索範囲 Skip Graph
- 40. 提案手法と Range Key Skip Graph との比較 ※ 登録するデータ数を n , 物理ノード数を m とする . 比較項目 RKSG 提案手法 挿入・削除の メッセージ数 最悪 O(n) O(log m) 1レコードあたりの 領域計算量 最悪 O(n) O(1) 冗長性 なし あり
- 42. 本研究では、 ・区間をキーとして扱える 効率的な分散 KVS の構成法を提案した . ・ 区間を 2 次元平面上の 1 点で表現した . 区間に対する範囲検索を 2 次元平面上の範囲検索に置き換えた . ・ 多数の区間 ( 点 ) を分散管理するために Znet を用いた . ・今後の課題 ・提案手法の実装および定量的な評価 ・関連研究との性能比較を行う