![?
協調モデルの分類学 [Cabri et al., 2000]
? 時間面と関係面の２つの次元でモデルを分類
時間面
結び付きあり
結び付きなし
結び付きあり
直接協調
メールボックス
結び付きなし
会議指向
発生通信
関係面](https://image.slidesharecdn.com/13-140218024809-phpapp01/85/13-4-320.jpg)
![? 各サーバはルータがルーティングフィルタを構成できるように、
購読を放送する。上流側のルータではフィルタを集約するこ
とができる。
Interface
Filter
ノード3へ
ノード4へ
a∈[2, 5]
ルータR1へ
Interface
a∈[0, 3]
（指定なし）
Filter
ルータR2へ
a∈[0, 5]
ノード1へ
（略）
ノード2へ
（略）
ノード5へ
（指定なし）
a∈[0, 3] を購読
a∈[2, 5] を購読](https://image.slidesharecdn.com/13-140218024809-phpapp01/85/13-21-320.jpg)
![?
?
?
?
出版されたデータ項目はｎ（属性，値）の組の関連ベクトル
で、プロセスはこれらの属性値の条件を指定することで購
読できると仮定してきた。
データ項目には関連している（属性，値）の一組しかない
場合、イベント（event）と呼ばれる。
イベントの購読、特に合成しているイベントのサポートは、
名前付けの問題に関係している。
複合イベントには２つの課題がある。
? 複合を記述すること
? イベントを集めて、どう購読とマッチングするか
※ [Pietzuch et el., 2003] が一般的な枠組みを示した](https://image.slidesharecdn.com/13-140218024809-phpapp01/85/13-23-320.jpg)
分散システム読書会 13章-分散協調ベースシステム
- 2. ? 前提 ? システムのコンポーネントは分散している ? その活動を調整するには現実の問題がある ? その上で ? 新しい世代の分散システムを考える ? コンポーネント間での活動の協調が重要である
- 4. ? 協調モデルの分類学 [Cabri et al., 2000] ? 時間面と関係面の２つの次元でモデルを分類 時間面 結び付きあり 結び付きなし 結び付きあり 直接協調 メールボックス 結び付きなし 会議指向 発生通信 関係面
- 5. ? 直接協調 (direct coordination) ? 相手の名前か識別子で通信し、プロセスは同時に実行する ? メールボックス協調 (mailbox coordination) ? メールボックスを通信に使えば同時に実行している必要はない ? 会議指向協調 (meeting-oriented coordination) ★ ? プロセスは互いを明示的には知らない（直接関係できない） ? 時間面にグループ化された会議→出版?購読システム ? 発生通信 (generative coordination) ★★ ? 独立したプロセス集合が共有されたタプルのデータ空間を利用する ? タプルはタグ付けされた型付きフィールドからなるデータレコードである ? プロセスは関心を持つフィールドの値を指定して、共有データ空間からタ プルを抽出する（連想検索）。合致するタプルがあるまでブロックもできる
- 7. ? 配送と通知 ? 購読がデータ項目のマッチングに成功するとき ? 出版されたデータ自体を購読者のプロセスに転送する（配 送）：データストレージは無くてもよい＝参照は分離される が、時間的には分離されない ? 出版されたデータ項目を読み出せるように「通知」を購読者 のプロセスに転送する： ミドルウェアにはデータ項目の格納 やリース期限管理などが必要になる
- 8. ? イベント ? ここまでデータ項目の記述にはｎ個の属性を用い、出版され たデータ項目は「（属性，値）の組」を持っている、としたが多く のシステムでは単一の指定された属性＝「イベント」だけが出 版される ? イベントは購読の処理を複雑にする（出版する側の処理を分 散させやすくはなる？）。イベント合成は難しいことが判明し ている ? 協調ベースのシステムでは、「データ項目への購読の効率的 でスケーラブルなマッチングの実装」が問題となる
- 9. ? 簡単な解決策 ? データ項目のマッチングの簡単な解決策は、クライアント／ サーバ構造を持つことである ? JiniとJava Space ? 発生通信のための協調モデル ? JiniはJava Spaceと呼ばれるLindaのような協調システムを 買って、プロセスの時間面?関係面で結びつかないようにして いる ? Java SpaceはJavaオブジェクトへのリファレンスの型付き集 合を表現するタプルを格納する共有データ空間 ? （詳細は省略）
- 10. ? JiniとJava Space （続き） ? 格納されているデータ項目上の大規模な検索を必要とする かもしれない。しかし効率的な検索の実現は容易ではなく、 高度なマッチング規則がサポートされているときは集中的な 実装が多い ? 集中的＝同期プリミティブの実現が簡単。非集中システムで の同期は本来難しい（６章）
- 11. ? TIB/Rendezvous ? 集中型サーバを使用する代わりに、マルチキャストで出版す ることでデータ構造を適切な購読者に同時に伝える ? データ項目はその内容を記述した news.comp.os.books などのような複合キーワードがタグ付けされたメッセージであ る ? 購読者はキーワード（の一部）あるいは news.comp.*.books などの受信したいメッセージを与える。 これらのキーワードはメッセージの「サブジェクト」と呼ばれる
- 12. ? TIB/Rendezvous （続き） ? 可能であれば効率的な通信を使用する： LANであればブロード キャスト、購読者の場所が特定できていればP2Pを用いる ? 各ホストは「ランデブーデーモン」を走らせて、メッセージが送られる とサブジェクトに関する配送があることを監視する。メッセージを出 版するときはランデブーデーモンを走らせる各ホストにマルチキャ ストされる ? デーモンはローカルの購読者に関する（プロセス，サブジェクト）の エントリを持つ表を作り、届いたメッセージをそれに照らして配送ま たは廃棄する ? メッセージがあらゆるノードに転送されるので、出版データの複雑 なマッチングも（余分な通信無しに）すべてローカルで処理できる
- 14. ? 例：ゴシップベースの出版?購読システム ? 各ノードの購読が範囲で記述されるとき、その範囲集合を 重なりのないサブセットに分割することで、出版されたデー タ項目に興味あるノードにすぐに通知される
- 15. ? 出版?購読にいかにノードの移動性を組合せるか ? 仮定：移動ノードのアクセスポイントは固定 ? 問題：アクセスポイントを切り替える購読者に、出版されたメッ セージを2回以上送られないようにするには？ ? 実際的な解決策：購読者にすでに受信したメッセージを管理 させて、重複したものを捨てさせる ? より複雑な代替案：メッセージをどの購読者に送ったかを ルータに管理させる
- 16. ? 例： Lime ? 発生通信ではノードが移動可能である共有データ空間を走査する ための解決策→例：Lime ? 各プロセスは自身に関係するデータ空間を持つ ? プロセスが接続されているように、互いに接近している（同じネット ワーク、同じ物理ホスト上など）ときは、そのデータ空間は共有され る ? 接続されたプロセス間ではタプル交換を可能とする一時的な共有 データ空間を形成する（writeとtakeが透過的） ? 誰に対するタプルのwriteか、どのプロセスからのタプルの read/takeかを指定することも可能 ? テンプレートに合うタプルがローカルで見つかったときに実行する 動作を指定する「反応」も指定できる
- 18. ? 出版?購読システムの通信は比較的簡単 ? すべての通信が遠隔メソッド呼び出し ? 広域システムに拡張するときの問題点は、「出版されたデー タが関連購読者だけに到達」するようにすること ? ピアツーピアシステムの自動クラスタ化 ? コンテンツベースのルーティング
- 19. ? 仮定 ? メッセージが明示的にノード間をルーティングされるP2Pネット ワーク上に構築される ? ルータがメッセージの内容を考えることによってルーティング を決定する。そのために各メッセージがその内容の説明記述 を運んでいることを仮定する ? アプリケーションはあらかじめ興味を持っているデータの種類 の記述をサーバに提供しておくと仮定する
- 20. ? 前提 ? 各メッセージは特有の（複合でない）キーワードでタグ付けさ れている ? 解決策１ ? 出版されたメッセージがすべてのサーバに送られる方法。各 クライアントが購読しているかをサーバがチェックする。 ? 解決策２ ? すべてのサーバにその購読を他のすべてのサーバに放送す る方法。
- 21. ? 各サーバはルータがルーティングフィルタを構成できるように、 購読を放送する。上流側のルータではフィルタを集約するこ とができる。 Interface Filter ノード3へ ノード4へ a∈[2, 5] ルータR1へ Interface a∈[0, 3] （指定なし） Filter ルータR2へ a∈[0, 5] ノード1へ （略） ノード2へ （略） ノード5へ （指定なし） a∈[0, 3] を購読 a∈[2, 5] を購読
- 23. ? ? ? ? 出版されたデータ項目はｎ（属性，値）の組の関連ベクトル で、プロセスはこれらの属性値の条件を指定することで購 読できると仮定してきた。 データ項目には関連している（属性，値）の一組しかない 場合、イベント（event）と呼ばれる。 イベントの購読、特に合成しているイベントのサポートは、 名前付けの問題に関係している。 複合イベントには２つの課題がある。 ? 複合を記述すること ? イベントを集めて、どう購読とマッチングするか ※ [Pietzuch et el., 2003] が一般的な枠組みを示した
- 24. ? だんだんと複雑になる合成イベントの例 例 説明 S1 S2 R4.20室が不在であり、ドアに鍵が掛かっていないときに通知する S3 R4.20室のドアに鍵が掛かっていないのに10秒間不在になったとき通知する S4 R4.20室が30分に一度以上温度が上がったときに通知する S5 ? R4.20室が不在になったら通知する R4.20室の平均温度が過去30分において20度以上であるときに通知する イベント複合言語（event-composition language） ? 有限状態機械(FSM)の拡張版に対する言語を提供 ? 状態における滞在時間、新しいイベントの生成が可能 ? 重要なことは、購読をFSMに変換できるということ
- 28. ? 複製は、発生通信のスケーラビリティに重要な役割を 持つ。ここでは以下を述べる ? JavaSpaces など多くのシステムで用いられてきた標準のア プローチ ? アクセスパターンに基づいてタプルの動的で自動的な配置を 可能とする最近の結果
- 29. ? ? 発生通信をサポートするシステムの分散実装では、 特有の注意が必要となる ここでは JavaSpaces サーバを実現できる分散実装 に焦点をあてる ? タプルインスタンスの集まりが数台のマシンにまたがって分 散されるかもしれない実装
- 30. ? JavaSpaces の効率的な分散実装には、２つの問題 を解決しなければならない ? 大規模な検索なしで連想アドレス付けをどうシミュレートする か ? どのようにマシンにタプルインスタンスを分散して、後でどうそ れらの場所を見つけるか ? 両方の問題のキー ? 各タプルが型付けされたデータ構造であることを観測するこ と（？）にある。タプルスペースをいくつかのサブスペースに分 けて、各タプルは同じもの（型？）としたとき、プログラミング は簡単化され最適化も可能となる。
- 31. ? 高信頼ブロードキャストが利用可能な場合 ? すべてのマシンにすべてのサブスペースを複製することができる ? タプルはwriteでブロードキャストされ(a)、takeでは削除がブロードキャストされる(b) ※ 设计は简単だがスケーラビリティがなく、広域ネットワークでは非常に高価になる
- 34. ? これまでの実装の問題 ? タプルをタプルスペースに挿入、あるいは削除するときに、マ ルチキャストが必要なことに起因する ? タプルスペースの広域実装は存在しておらず、せいぜいいく つかのタプルスペースが１つのサーバあるいはLANに実装さ れている程度である ? タプルスペースの効率的な広域実装をどのように開発するか は未解決の問題である
- 35. ? GSpaceの概要 ? read/write/takeインターフェースの呼び出しは、従うべきポ リシーを探索するために、ローカルの起動ハンドラに取り上 げられる ? 複製はポリシーにしたがって行われる。マスター／スレーブ ポリシーであれば、readはローカルのデータ空間から読み込 まれ、writeは更新をマスターノードに送るようになる。 ? 実行時にポリシー記述子を加えたり、分散マネージャを変え ることができる。この設定により、タプルの分散と複製の細粒 度を調整できる。
- 36. ? 適応型複製 ? 開発者にどのポリシーの組合せが最良か指摘させるより、システ ムにアクセスパターンと動作をモニタさせて、必要に応じてポリシー を採用させるようがよい ? 絶え間なく消費ネットワーク帯域、レイテンシ、メモリ使用量などを 測定し、タプルをどのノードに配置し、複製の一貫性を管理する最 適な方法はなにかを選択する。 ? 与えられたタプルに対して、どのポリシーが最良であるかの評価は、 中央コーディネータによって行われる。 ? その時々で複製ポリシーを別のものに切り替える必要があり、その ような遷移を行なうことができるいくつかの方式がある。 ? デフォルトでは、一時的に特定のタイプのタプルに対するすべての オペレーションを停止し、すべての複製を削除し、共有データ空間 にタプルを再投入し、新たな複製ポリシーに従う
- 37. ? 協調ベースのシステムでは、データ配送の効率性と 信頼性の保証が注目される ? 高信頼通信 ? 高信頼ストレージ ※ むしろこの２点しか注目が集まっていない
- 39. ? TIB/Rendezvousにおけるフォールトトレント性 ? 通信装置は本来信用できないと仮定 ? メッセージの出版時は、60秒はメッセージを保持して、再送 に備える（メッセージに順序番号を付与してその喪失を検出 する） ? それでもメッセージが失われた場合にはアプリケーションに 通信エラーが通知される ? TIB/Rendezvousでは、実際的な汎用マルチキャスト (Pragmatic General Multicast: PGM) と呼ばれる高信頼 マルチキャストを提供する
- 40. ? PGMの概要 ? マルチキャストメッセージが各受信者に最終的には渡される という厳密な保証はしない ? 受信者が失ったメッセージを検出して再送要求 (NACK) を送 信者に向けて、マルチキャスト木の逆向きのパス沿ってに送 る ? 中間ノードは同一の再送要求を送り主に転送しないことで、 フィードバック爆発を防ぐ ? NACK の通過パスを記憶しておき、再送メッセージを要求し た受信者だけに送ることで、無駄な転送を防ぐ
- 41. ? PGMの原理
- 42. ? 公認されたメッセージ配送 (certified message delivery) ? メッセージの送受信に特別なトランスポート層を使用する ? 公認メッセージの受信者は自分自身を送信者とともに「台帳 (ledger)」に登録することで、プロセス障害があるときでも高 信頼なメッセージ配送を可能とする ? 受信プロセスのクラッシュでは回復するまでのすべてのメッ セージは送り主の台帳に記録される。回復時は台帳にメッ セージの再送を要求する。
- 43. ? プロセスのフォールトトレラント性 ? プロセス障害の隠蔽のため、自動的にプロセスを活性化／非活性 化する方法を提供する ? プロセスはグループ化されるが、その中では一意なランクを持つ。 各グループは活性化しているプロセス数の目標値（通常は１）を持 つ ? アクティブなプロセスは定期的にハートビートをグループメンバに送 信する。それが欠けたとき、ミドルウェアはアクティブでない最も高 いランクのプロセスを動かす ? アクティブ化はメンバが実装する active オペレーションのコール バックによって行われる ? クラッシュしたプロセスが回復して再びアクティブ化すると、現在ア クティブな最も低いランクのプロレスが非アクティブ化される
- 44. ? 発生通信を扱うときはより複雑である ? 共有データ空間にフォールトトレラント性を組み込む必要が 出てくると、その解決策はとても効率が悪くなるため、集中実 装のみが実現可能である ? 代替手段 ? 様々なマシンにデータ項目のコピーを置き、より積極的に複 製を配備する ? 各ノードはその可用性を計算し、それは、単一のデータ項目 としての可用性の計算に用いられる
- 45. ? 可用性の計算 ? ノードは定期的に永続的ストレージにタイムスタンプを書き込むことで、 それを元に可用性を計算できる ???? ノードの可用性 = ???? + ???? ????? ? 実際のクラッシュは ? ? より遅く、復旧は ? ???? より早いので、計算 上の可用性は実際より悲観的となる
- 46. ? 協調ベースシステムのセキュリティ問題 ? プロセスが参照的に分離されるべき ? データの完全性と機密性を確実にする ? 通常はセキュアなチャネルで実現される ? しかし、送信者と受信者が互いに認証できる必要があり、参 照の分離に違反する ? アプローチ ? データ処理と購読を扱うブローカのネットワークを確立するこ と。この場合、クライアントはブローカを信頼する必要はある。
- 47. ? 情報機密性 ? 協調ベースシステムでは、ミドルウェアが出版されたデータの内容 を点検する必要がある ? 出版されたデータのミドルウェアによる点検を禁止したい場合に、 情報機密性問題を引き起こすが、これはエンドツーエンド暗号化で 回避できる。 ? 出版されるデータ項目が複数のフィールドを持つように構造化して いる場合、あるフィールドだけ暗号化することができる ? 平文がミドルウェアで点検できない場合、コンテンツベースルーティ ングが暗号化されたデータで行われる。 ? 部分的なマッチングが可能となるような方法で、フィールドの購読 が符号化される必要があるだろうが、達成するのはほとんど不可 能である。 ※ 暗号化データの場合、フィールドの完全一致は判定できても、そ れ以外の判定は不可能ということ？
- 48. ? 購読秘密性 ? 購読がミドルウェアに対しても明かされないこと 【解決策】 フィールドごとの暗号化を使用して、厳密なフィー ルドごとのマッチングを適用する。複合キーワードの場合は、 成分が暗号化された集合のように表現される ? 出版機密性 ? あるプロセスはある（出版）メッセージを見ることさえできない こと 【解決策】 出版者は購読者のグループを制限したくな るが、多くの場合、このコントロールは出版と購読アプ リケーションのレベルの範囲外でなされる
- 50. ? AS での鍵管理とメッセージの変換 ? 出版者が登録するとき、その登録情報はASに転送されて、 暗号鍵（公開鍵）が生成?署名されて出版者に渡される（秘密 鍵はASが保持する） ? 購読者が登録するとき、ASに暗号鍵（公開鍵）を提供する ? メッセージがブローカに到着したとき、ASに対して「そのメッ セージを復号して購読者から提供された暗号鍵で暗号化」 （変換）するよう要求する。 ※出版者の秘密鍵で復号、購読者の公開鍵で再暗号化する ? この方法ではブローカは秘密にされるべき内容を知ることも、 出版者と購読者が鍵情報を共有する必要もない ? もちろんAS自体がスケーラビリティを持つことが重要
- 51. ? 共有データ空間をセキュアにするための研究はほと んど行われていない ? 一般的なアプローチは、フィールドの暗号化と、復号化に成 功して内容が購読に合致する場合だけマッチングが行われ るという方式 ? このアプローチの問題点 ? 出版者と購読者の間で鍵が共有される必要がある ? 出版者の復号化鍵が認可された購読者に知られている ? ほとんどの実装が単一のサーバを利用すると考える場合、 認証と認可のメカニズムをそのサーバに拡張することは実際 的に採用されているアプローチである
- 52. ? プロセスの独立 ? 協調ベースは、通信による互いの関係面?時間面での独立を提供 ? 出版?購読パラダイム ? メッセージは受信者アドレスを持たず、受け取りたいプロセスがサブジェクトを 購読する。属性に関する条件を定式化できれば、コンテンツベースルーティン グが可能になる。また効率的な転送のためにはルータでフィルタする。 ? 共有されたタプルによるデータ空間 ? タプルは型付けされたデータ構造である ? テンプレートタプルを提示して読み込みを要求し、見つかるまでブロックする ? ? 通信は匿名でよく、拡張や変更に対する柔軟性 分散システムの原則は協調ベースにも同様に適用される ? キャッシュと複製は際立った役割を果たしていない ? 名前付けは属性ベースの検索に強く関係している ? 問題はセキュリティのサポート（出版者と購読者の分離違反）