P2P 技術と Cloud コンピューティングへの応用

大学院の輪講でやったはなし

Transcript

1. P2P技術とCloudコンピューティングへの応用 折原 レオナルド賢 The application to cloud computing and peer-to-peer network. Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan. Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications. SIGCOMM ’01, pp.149-160. (2001). [1]
2. ▪ Cloudコンピューティングが普及 ❏ 複数のコンピュータを用いてサービスを運用 2 近年のオンラインシステム 抽象化されたCloudの中身は複数マシンが接続
3. ▪ Dropboxのようなデータを共有・同期するシステムが普及 ❏ Cloudと抽象化されたコンピュータ集合にデータを預ける 3 データ共有サービス
4. ▪ ユーザがアップロードするファイルの75%～90%は重複[2] ❏ Cloud上のディスクスペースを逼迫 4 データの重複 Anthony D. Joseph. A Survey, Cloud File Sharing, and Object Augmentation. Pervasive Computing, IEEE, Vol.11, Issue.2, p.96, (2012). [2] 75%～90% 75%～90% P2P技術を用いての同期・分散を行うシステム LifeStuffについて紹介 この問題を解決するサービス
5. ▪ P2Pネットワーク ❏ 複数のコンピュータが互いに直接接続 5 Peer-to-Peerネットワーク サーバーを必要とせず、クライアント同士で通信が可能 本発表ではChordアルゴリズムを紹介
6. ▪ P2Pネットワークではデータの分散配置が可能 ❏ 1つの同じデータを5人のユーザがアップロードした場合 6 P2Pにおけるデータの分散配置１ 1つのファイルで5倍のディスクスペースを使用 ディスクスペース逼迫する要因 Cloudコンピューティングでは
7. ▪ P2Pネットワークを用いてデータを共有 ❏ 1つのデータを5人のユーザで共有した場合 7 P2Pにおけるデータの分散配置２ 7 14 6 0 8 12 4 11 10 1 7 14 6 0 8 12 4 11 10 1 2 3 4 5 5人が１つのデータの断片を所持している ➡1つのデータを5分割してそれぞれ所持 個人のディスクスペース消費は1/5で済む 一般的なデータであるほど、消費量は減る 1
8. ▪ 分散ハッシュテーブル ❏ そもそも、マシン群へデータを保存・取得するとは？ 8 P2Pの基本的なアルゴリズム データの実態はマシン群のどこかのマシンに存在する データを保存 データを取得
9. ▪ 各々のマシンはマシンIDを持っている ❏ ハッシュ関数を用いてデータの保存場所を決定 9 データの所在 データの実態はマシン群のどこかのマシンに存在する ：担当範囲 192.168.0.1 192.168.1.1 192.168.2.1 192.168.3.1 マシン IPアドレス マシンID 担当範囲 A 192.168.0.1 0x0001 0x0001～0x0010 B 192.168.1.1 0x0011 0x0011～0x0020 C 192.168.2.1 0x0021 0x0021～0x0030 D 192.168.3.1 0x0031 0x0031～0x0040 Hash = 保存場所 あるデータが与えられた時、 そのデータを代表する数値を得る関数 0x0001 0x0011 0x0021 0x0031
10. ▪ ハッシュ関数とは ❏ データを元に別の空間に射影する関数 10 ハッシュ関数 mod 素数2 素数1 MD5 SHA-1 etc.. 8c7dd922ad47494f c02c388e12c00eac 971c419dd609331343d ee105fffd0f4608dc0bf2 45682183 射影 ハッシュ関数 ハッシュ関数
11. ▪ 各々のマシンはマシンIDを持っている ❏ ハッシュ関数を用いてデータの保存場所を決定 マシン IPアドレス マシンID 担当範囲 A 192.168.0.1 0x0001 0x0001～0x0010 B 192.168.1.1 0x0011 0x0011～0x0020 C 192.168.2.1 0x0021 0x0021～0x0030 D 192.168.3.1 0x0031 0x0031～0x0040 11 データの所在 データの実態はマシン群のどこかのマシンに存在する 192.168.0.1 192.168.1.1 192.168.2.1 192.168.3.1 Hash = 0x0036 0x0001 0x0011 0x0021 0x0031 ：担当範囲
12. マシン IPアドレス マシンID 担当範囲 A 192.168.0.1 0x0001 0x0001～0x0010 B 192.168.1.1 0x0011 0x0011～0x0020 C 192.168.2.1 0x0021 0x0021～0x0030 D 192.168.3.1 0x0031 0x0031～0x0040 ▪ 各々のマシンはマシンIDを持っている ❏ ハッシュ関数を用いてデータの保存場所を決定 Hash = 0x0036 12 データの所在 データの実態はマシン群のどこかのマシンに存在する 192.168.0.1 192.168.1.1 192.168.2.1 192.168.3.1 0x0001 0x0011 0x0021 0x0031 ：担当範囲
13. ▪ Chordではリング状にID空間を形成 ❏ IPアドレスとハッシュ関数を用いてマシンIDを設定 Chordでは 0～2 -1までの整数値を取る m 13 ChordのID空間 Chordネットワークは時計回りに移動 15 7 14 6 13 5 0 8 12 4 11 3 10 2 9 1 15 7 14 6 13 5 0 8 12 4 11 3 10 2 9 1 m=4のとき ID空間が密や疎になることがない
14. ▪ Chordの担当領域も時計回りで決定 ❏ 以下のようなChordネットワークを仮定 ノード8が保存 14 Chordネットワークのルーティング 13 0 8 3 13 0 8 3 1 2 6 時計回りで最初にぶつかったノードが担当 ノード3の担当領域は1, 2, 3 Hash = 6 Successorと呼ぶ 3は0のSuccessor 8は3のSuccessor
15. ▪ 経路表内のSuccessorを用いてデータをルーティング 15 経路表の構築 13 0 8 3 13 0 8 3 種別 IPアドレス マシンID Successor 192.168.8.1 8 種別 IPアドレス マシンID Successor 192.168.3.1 3 種別 IPアドレス マシンID Successor 192.168.13.1 13 ・・・ ・・・ 切断 1つでもノードが切断されると到達性が確保されない
16. ▪ SuccessorListを保持して到達性を向上 16 Successorの冗長化 13 0 8 3 13 0 8 3 種別 IPアドレス マシンID ステータス Successor 192.168.8.1 8 SuccessorList1 192.168.13.1 13 SuccessorList2 192.168.0.1 0 切断 SuccessorList全てにファイルを持たせ、冗長化 ➡ レプリケーション 到達性は向上した ➡ ノードが50万、100万接続あるとコストが高い
17. ▪ 経路表にFingerTableを追加 17 経路の短絡 7 14 0 8 12 4 11 10 1 7 14 0 8 12 4 11 10 1 種別 IPアドレス マシンID Successor 192.168.10.1 10 SuccessorList1 192.168.11.1 11 SuccessorList2 192.168.12.1 12 FingerTable1 192.168.0.1 0 FingerTable2 192.168.12.1 12 FingerTable3 192.168.10.1 10 FingerTable m 192.168.m.1 m … … … FingerTable1 FingerTable2 FingerTable3 最大で向かいのノードまでジャンプ可能 ➡ FingerTableを用いた経路長は O(logN)
18. ▪ P2Pネットワークではノードが追加・切断されることは頻繁 ❏ JoinとStabilizeを用いてネットワークを維持 マシンID6のノードが追加 ➡ 6を担当するノードを時計回りに検索 18 ノードの新規追加 7 14 0 8 12 4 11 10 1 7 14 0 8 12 4 11 10 1 種別 IPアドレス マシンID Successor 192.168.7.1 7 … … … Join Hash = 6 6 新規ノード
19. ▪ 単にJoinされただけでは、正しいルーティングが行われない ❏ Predecessorを用いて修正する 19 経路表の修正 Stabilize（Successor用） 7 14 6 0 8 12 4 11 10 1 7 14 6 0 8 12 4 11 10 1 Predecessor ➡ １つ前のノードへの経路 種別 IPアドレス マシンID Successor 192.168.7.1 7 Predecessor 192.168.1.1 1 ノード4のSuccessorが7のまま
20. ▪ 自ノードのSuccessorにPredecessorがどのノードが聞く 20 Successor用 Stabilizeの動作 7 14 6 0 8 12 4 11 10 1 7 14 6 0 8 12 4 11 10 1 Successor 192.168.7.1 7 Predecessor 192.168.1.1 1 Successor 192.168.7.1 7 Predecessor 192.168.?.1 ? Successor 192.168.8.1 8 Predecessor 192.168.4.1 4 ノード4のSccssrは7 ノード7Prdcssrのは4 1 修正は行われない
21. ▪ 自ノードのSuccessorにPredecessorがどのノードが聞く 21 Successor用 Stabilizeの動作 7 14 6 0 8 12 4 11 10 1 7 14 6 0 8 12 4 11 10 1 Successor 192.168.7.1 7 Predecessor 192.168.1.1 1 Successor 192.168.7.1 7 Predecessor 192.168.?.1 ? Successor 192.168.8.1 8 Predecessor 192.168.6.1 4 ノード6のSccssrは7 ノード7Prdcssrのは4 2 間違いを修正 6
22. ▪ 自ノードのSuccessorにPredecessorがどのノードが聞く 22 Successor用 Stabilizeの動作 7 14 6 0 8 12 4 11 10 1 7 14 6 0 8 12 4 11 10 1 Successor 192.168.7.1 7 Predecessor 192.168.1.1 1 Successor 192.168.7.1 7 Predecessor 192.168.?.1 ? Successor 192.168.8.1 8 Predecessor 192.168.6.1 6 ノード4のSccssrは7 ノード7Prdcssrのは6 3 6にアクセス 一周まわって 6の存在を検知
23. ▪ 自ノードのSuccessorにPredecessorがどのノードが聞く 23 Successor用 Stabilizeの動作 7 14 6 0 8 12 4 11 10 1 7 14 6 0 8 12 4 11 10 1 Successor 192.168.6.1 7 Predecessor 192.168.1.1 1 Successor 192.168.7.1 7 Predecessor 192.168.4.1 ? Successor 192.168.8.1 8 Predecessor 192.168.6.1 6 ノード6にアクセス 6のPrdcssrは ”?” 4 ノード6のPrdcssr、 ノード4のSccssrを修正 4 6
24. ▪ 自ノードのSuccessorにPredecessorがどのノードが聞く 24 Successor用 Stabilizeの動作 7 14 6 0 8 12 4 11 10 1 7 14 6 0 8 12 4 11 10 1 Successor 192.168.6.1 6 Predecessor 192.168.1.1 1 Successor 192.168.7.1 7 Predecessor 192.168.4.1 4 Successor 192.168.8.1 8 Predecessor 192.168.6.1 6 ネットワークが修正 Stabilize処理は 定期的に行われる
25. ▪ FingerTable用のStabilizeを実行 ❏ FingerTableは元々m個と決まっている 25 FingerTableの修正 7 14 6 0 8 12 4 11 10 1 7 14 6 0 8 12 4 11 10 1 FingerTable1 192.168.?.1 ? FingerTable2 192.168.?.1 ? FingerTable3 192.168.?.1 ? FingerTable m 192.168.?.1 ? … … … FingerTableのすべての座標にアクセス ➡ 宛先が変わっていたら修正
26. ▪ FingerTable用のStabilizeを実行 ❏ FingerTableは元々m個と決まっている FingerTable用のStabilizeも定期的に行われる 26 FingerTableの修正 7 14 6 0 8 12 4 11 10 1 7 14 6 0 8 12 4 11 10 1 FingerTable1 192.168.14.1 14 FingerTable2 192.168.10.1 10 FingerTable3 192.168.8.1 8 FingerTable m 192.168.m.1 m … … … ネットワークが修正
27. ▪ ネットワークが維持されているとデータの共有・分散が可能 ❏ このようにP2Pネットワーク上で処理が行える 27 データの共有・分散 7 14 6 0 8 12 4 11 10 1 7 14 6 0 8 12 4 11 10 1 複数コンピュータ間での サーバーを除いた通信が容易に可能
28. ▪ P2Pネットワーク上で、Dropboxのようなシステムを運用 28 LifeStuff P2Pなので、管理者であっても データを閲覧することができない ネットワーク上のデータの重複を回避
29. ▪ ネットワーク上のノード4がデータを要求 ❏ 5分割されたデータのコピーをノード4へルーティング → 結合 29 P2Pにおけるデータの分散配置 7 14 6 0 8 12 4 11 10 1 7 14 6 0 8 12 4 11 10 1 1 2 3 4 5 7 14 6 0 8 12 4 11 10 1 7 14 6 0 8 12 4 11 10 1 1 2 3 4 5 1 2 3 4 必要なときのみ 結合・復元
30. ▪ サービスを使っている不特定多数が共有しては問題 ❏ データを持っているユーザのみ復号化を許可 30 データ共有・同期サービスにおいて 7 14 6 0 8 12 4 11 10 1 7 14 6 0 8 12 4 11 10 1 1 2 3 4 5 Self-Encryption データそのものを鍵として暗号化 Hash = 秘密鍵 暗号化 = , 秘密鍵 データを所持している人のみ復号化可能
31. 31 Self-Encryption 7 14 6 0 8 12 4 11 10 1 7 14 6 0 8 12 4 11 10 1 1 2 3 4 5 秘密鍵 秘密鍵 秘密鍵 秘密鍵 秘密鍵 データを所持しているユーザなら 秘密鍵を生成できる 必要なときに復号化
32. ▪ P2Pネットワーク技術の基礎としてChordを取り扱った ❏ Cloud技術への応用として、LifeStuffの概要を紹介 ❏ P2P技術の基本は比較的容易で応用しやすい ➡ 分散ハッシュテーブルやSelf-Encryptionはオープンソース 32 まとめ （GitHub） システム開発や研究を行う上で役に立てていただければ。