P2P Overlay Network

パーソナル・アーカイブのための
自律分散型データ共有システムの設計
大阪市立大学大学院創造都市研究科
都市情報学専攻情報基盤研究分野
M04UC513 藤田昭人
はじめに
•
研究の目的
パーソナル・アーカイブを実現する上で必要となる共有ストレージを分散
環境において実現する
•
研究のアプローチ
1.
2.
3.
既存のアーカイブ・システムのストレージ構造を調査する
自律分散環境を実現するP2P技術について調査する
上記２項の結果に基づき分散共有システムを設計する
パーソナル・アーカイブ
•
パーソナル・アーカイブとは？
– 個人のビジネスや研究・開発などの作業を支援する私的なアーカイ
ブ
– ネットワーク化することにより専門性が高く網羅的な仮想的なデータ
ベースを実現
•
パーソナル・アーカイブを実現する上での技術的課題
1. 収容するデジタル・コンテンツの分散共有の方法
2. 収容するデジタル・コンテンツの著作権管理の方法
※ 本研究では1.の課題について検討を行った
既存アーカイブ・システムの構造
Statistics
Tools
Web UI
OAI-PMH
Data
Provider
Simple
Importer/
Exporter
Media
Filter
METS
Exporter
Application
Layer
DSpace Public API
Core Tools
Search
(Configuration,
Logging)
(Lucene
Wrapper)
Browse
Tools
History
Recorder
Administration
Toolkit
Content Management
Handle
Manager
Handle Server
Storage Plug-in
E-person/
Group
Manager
Submission
Workflow
Manager
Business
Logic Layer
Authorisation
Storage API
RDBMS Wrapper
Bitstream Storage Manager
JDBC
PostgreSQL
Oracle
File
System
SRB
(Storage
Resource
Broker)
Storage
Layer
パーソナル・アーカイブ化する上での課題
• 既存のアーカイブ・システムの分散共有には次の項目の分
散化が必要
– デジタル・コンテンツ自体を格納するファイル形式のデータ格納機構
– デジタル・コンテンツのメタデータを格納するリレーショナル・データベ
ース
P2P技術
• 分散システムのアーキテクチュア
– 中央集権的な制御実体がない（ディセントライズド）
– 自己組織的
• 参加者は帯域、ストレージ、計算能力などを共有する
• 一般的には信頼性の低い、多種多様な、多数のノードから
構成されるが、信用できないノードが存在する可能性もある
P2P Overlay Network
• Unstructured overlay (Gnutella, Freenet)
– ランダムなグラフによるオーバーレイ・ネットワークを形成
– 信頼性が低く、非効率な検索
– オーバーレイ構築のオーバーヘッドは低い
• Structured overlay (CAN, Chord, Pastry, Tapestry)
– 特定のグラフ構造のオーバーレイ・ネットワークを形成
– 信頼性が高く、効率的な検索
– オーバーレイ構築のオーバーヘッドが幾分高い
分散ハッシュテーブル（DHT）
• Structured P2P overlay を形成するための手段の１つ
• ハッシュ関数と同様に、データから生成されるキーを使って
そのデータが格納されているノードを特定する
• Structured P2P では SHA-1 などのハッシュ関数
(Secure Hash Function)が使用されることが一般的
Chord/DHash
• MITで開発されたP2Pデータ共有の実装
– Chord ー P2Pルーティング・プロトコル
– DHash ーデータ・ブロックの配布、複製、キャッシング
– 両者によりDHTによるP2Pオーバーレイネットワークを形成
• Chord/Dhashを活用したアプリケーション
–
–
–
–
–
ファイル共有 [CFS, Ivy]
Webキャッシュ [Coral]
名前サービス [ChordDNS]
通信プリミティブ [I3]
Webアーカイブ [Herodotus]
Cooperative File System (CFS)
• Chord/DHashを利用した参照専用ファイルシステム
• ソフトウェアなどの配布に活用できる
• Chord/DHashを活用し、負荷分散、対障害性、スケーラビリ
ティの高い分散システムを実現
• ファイルシステムをデータ・ブロックとして管理
– 対象となるファイルシステムをデータ・ブロックに分割し、
Chord/Dhashによって広域分散的に配置
– クライアント側においてデータ・ブロックから
ファイルシステムに再構成する
• ファイルシステムのクライアント・インターフェースと電子署名
はSFS Read-only File System に基づく
Cooperative File System (CFS)
ファイル参照系
User
Program
DHash
chordcd
DHash
Chord
Chord
System Call
NFS 3
Kernel
NFS Client
Chord Ring
DHash
Private key
CFS
sfsrodb
Chord
DHash
Chord
File System
ファイル登録系
DHash
Chord
Ivy: Read/Write P2P Filesystem
• Chord/Dhashを利用した読み出し・書き込み可能なファイルシステム
• 一般的な分散ファイルシステムとして活用できる
• Chord/DHashを活用し、負荷分散、対障害性、スケーラビリティの高い
分散システムを実現
• ログ構造に基づくデータ構造を利用し、ファイルに対するデータ更新時の
競合を回避
• スナップショットを活用してファイルへの高速アクセスを実現
• ファイルシステムのクライアント・インターフェースと電子署名の実装は
SFS File System Toolkit を活用
Ivy: Read/Write P2P Filesystem （２）
User
Program
Ivy Server
(cfsrwcd)
DHash
DHash
Chord
Chord
Ivy agent
Private key
NFS 3
System Call
Chord Ring
Kernel
NFS Client
DHash
Chord
DHash
Chord
DHash
Chord
データ共有システム
• Webアプリケーションとして実装された既存アーカイブ・シス
テムの自律分散化を実現
• 分散ファイルシステムと分散データベースの機能を提供
• 自律分散にはChord/Dhashを活用する
データ共有システム
PC
PC
P2P Overlay Network
PC
PC
PC
Web Server
Archival
System
Web
Browser
Server-Side
Script
Language
Filesystem DBMS
P2P
Data Sharing
System
Chord/DHash
PC
分散ファイルシステムの設計上の要点
• 分散ハッシュテーブルを活用することにより、WAN環境での
アクセス性能の低下は抑制される
• 分散ハッシュテーブルではハッシュ関数の使用頻度が性能
に大きな影響を与える
→ ファイルシステムの内部データ構造は単純なものが望ましい
• ファイルシステム・インターフェースが性能低下の要因になっ
ている可能性がある
→ Webサーバーやサーバー・サイド・スクリプト言語環境から直接ファ
イル参照を行う実装も検討するべき
データベースを分散化する上での課題
• ACID －トランザクション処理における基本的セマンティクス
– データベース管理システム(DBMS)での必須の機能とされる
–
–
–
–
原子性(Atomicity)
一貫性(Consistency)
独立性(Isolation)
永続性(Durability)
トランザクションの全タスクの実行・非実行を保証する
トランザクションの開始時と終了時での整合性を保つ
他の処理から完全に隔離される
成功したトランザクションが取り消されない
• 分散環境でのACIDセマンティックスの完全な実現は難しい
– 特にデータ更新での一貫性の維持（衝突の回避、調停）
Ivy, Coda でのデータ一貫性維持
• Andrew Filesystem (AFS)が起源
• ファイル・セッションに基づくセマンティックス
– サーバーにあるマスターファイルをクライアントにキャッシュする
• OPEN マスターファイルをローカルキャッシュにコピー
• WRITE ローカル・キャッシュに対してデータ更新
• CLOSE ローカルキャッシュの内容をマスターファイルにマージ
• メリット
– データ更新時の衝突の調停を回避できる
• デメリット
– データ・アクセス時に他者の更新を参照できない
– 更新内容のマージがうまくいくとは限らない
参考文献 M. Satyanarayanan, “Scalable, Secure, and Highly Available Distributed File Access”,
IEEE Computer, pp. 9-20, May 1990
分散データベースへの応用
• SQLをベースに考える
• 特定のノードにコンシステント・ハッシュ化されたマスター・データベースが
存在し、任意のノードにあるローカル・データベースの内容と一貫性を
維持するためには・・・
– BEGIN, ROLLBACK
• マスター・データベースの内容をローカル・データベースへ同期
– 更新系コマンド(CREATE, INSERT, DROP・・・)
• ローカル・データベースに対して更新
– COMMIT, END
• ローカル・データベースの更新内容をマスター・データベースへ反映
分散データベース
• データベース・ファイルをページ単位で管理
• 各ページごとコンテント・ハッシュ化して複数ノードに分散配置
• マスターデータベースのノードはページリストを管理
Consistent-Hashed
Master Database
Content-Hashed
Page
Master Database
PC
PC
Content-Hashed
Page
Local Database
PC
P2P Overlay Network
PC
Local Database
Content-Hashed
Page
PC
Content-Hashed
PC
Page
マスターデータベース
Master Database
Page List
(Consistent-Hash)
Page Block
(Content-Hash)
H(Page0)
Page 0
H(Page1)
H(Page2)
H(PageN)
Page 1
Page 2
Page N
マスターからローカルへの同期操作
①
マスターノードよりページリストを取得
②
ページリストを元に古くなったページを探索
③
古くなったページについて各ノードから最新ページを取得
Consistent-Hashed
Master Database
Content-Hashed
Page
③
PC
PC
①
Content-Hashed
Page
②
③
PC
Local Database
③
③
PC
Content-Hashed
Page
PC
Content-Hashed
Page
PC
ローカルからマスターへの同期操作
①
トランザクション内の更新コマンドを一括して転送
②
マスターデータベースを一括更新
③
更新されたページのコンテンツ・ハッシュ化して各ノードに転送
Consistent-Hashed
Master Database
Content-Hashed
Page
②
③
PC
PC
③
①
③
PC
Local Database
③
PC
Content-Hashed
Page
PC
Content-Hashed
Page
Content-Hashed
Page
PC
おわりに
• 本研究ではP2P技術を活用したアーカイブ・システムの分散
データ共有方法を提案する。
• 本研究ではSQLクエリーエンジンが要求するACIDセマンティ
ックスを分散環境で実現するため、SQLトランザクションに基
づく同期手法を提案する。
• 本研究で提案する分散データ共有システムはアーカイブ・シ
ステムだけでなく、その他のWebアプリケーションでも有効に
活用できる可能性が高い。

Download Report