分散システムの概要・
アーキテクチャ
分散システム
2015年10月5日
分散システムの定義
• 単一
の（single）
一貫
した（coherent）システム
と
見なせる，独立した
（independent）コン
ピュータの集合
– 自立（autonomous）したコンピュータからなる – 利用者（プログラム）は単一システムと見なせる• 独立したコンピュータの協調が必要
– どのように協調するかが分散システム構築のポ イント – コンピュータの種別（性能，能力）は問わない • スパコンからセンサーまで分散システムの*特徴*
• コンピュータの差，コンピュータ間の通信はユーザ から隠蔽 • 一貫した（consistent）均一な（uniform）なアクセス • 原理的には拡張，スケールが比較的容易 – 独立したコンピュータだから – ただし，実際にどのように構成しているかは隠蔽する必要 がある • いつでも利用可能（continuously available） – 一部が故障した，修理された，追加されたとしても利用者 には気づかせない分散システムのソフトウェア階層の例
• 計算機の非均質性（heterogeneity）とネットワークに対 応するため，アプリケーションとローカルOSの間のミド ルウェアとしてしばしば実装される アプリ1 アプリ2 アプリ3 分散システム（ミドルウェア）OS1 OS2 OS3 OS4
ネットワーク
• 各アプリケーションに同一のインターフェースを提供 • 分散アプリケーションが相互に通信する手段を提供 • ハードウェア，OSの違いを可能な限り隠蔽
4つの目標
• 簡単に利用可能
• 分散していることを十分隠蔽
• オープン
簡単に利用可能に
• 遠隔の資源を簡単に利用できるように – 制御され，効率的に共有 • 資源：プリンタ，コンピュータ，ストレージ，データ， ファイル，Webページ，ネットワーク，… • 資源共有の理由 – それぞれにプリンタを購入し維持するより複数ユーザで 共有した方が経済的 – スパコン，高性能ストレージ，イメージセッタなど高価な機 器の共有資源共有の例
• インターネットプロトコル（IP）により共同作業，情報交換が容 易に – 単純な標準プロトコルにより，ファイル，メール，音楽，ビデオ交換が 容易に – グループウェアにより地理的に離れたグループでの共同編集，テレコ ンなどが可能に – お店に行くことなしにネット購入も可能に • セキュリティが問題に – 通信の盗聴や介入に対する対策が必要 – パスワードなど暗号化されずクリアテキストで送信（http, ftp, telnet 等），サーバに格納されることも – カード保有者である証拠を見せることなくカード番号で購入する – ユーザの好みを知るためなど通信履歴の追跡を許可なく行う – スパムメールなど無用の通信からの対策分散透明性
（Distribution Transparency）
• 目標
– プロセスや資源が複数のコンピュータに分散して いることを隠すこと• 単一のコンピュータのように振る舞う＝
透明
（Transparent）である
透明性の種類
透明性 意味 アクセス データ表現の違い，データアクセス方法の違いを 隠蔽（エンディアンなど） 位置 資源がどこにあるか隠蔽。ネーミングが鍵（位置 が名前に含まれない論理名） 移動 資源が移動したことを隠蔽 再配置 使用中に移動したことを隠蔽 複製 資源の複製があることを隠蔽 並行性 複数ユーザで共有されていることを隠蔽。一貫性 を保つ 障害 障害と復帰を隠蔽 [ISO, 1995]透明性の程度
• 完全な透明性の確保はいいことではない！ • 時差，通信遅延を隠すことはできない – 光速は越えられない • 透明性の程度とシステムの性能はトレードオフの関係 – 最終的に失敗する前に何度もリトライ。そのため反応が遅くなる – 大陸をまたぐ複製。更新を伝えるだけで秒オーダ • 組込やユビキタスシステムでは分散を見せるほうがよい – ノートPCでプリントアウトする場合，国が異なる本部の空いているプ リンタより近くの忙しいプリンタのほうが良い • 分散を見せることにより，より効率的な利用も可能 • 設計では完全な透明性は良い目標だがそのコストは恐ろしく 大きい。性能と分かり易さは重要。Openness
• オープンな分散システム＝標準規格に従いサービスを提供 するシステム – 標準通信プロトコル（フォーマット，内容，メッセージの意味） • 分散システムはインターフェースで定義されることが多い – サービスのインターフェース記述にIDL（Interface Definition Language）を利用 – サービスの名前，引数の型，返値，例外 • オープンシステムの目標 – 相互運用性（Interoperability）＝異なる実装でも仕様に従っていれば お互いに利用可能 – ポータビリティ（Portability）＝システムA用の実装をシステムBで無修 正のまま利用 – 拡張性（Extensibility）＝コンポーネント追加，変更が容易ポリシの分離
• システムの柔軟性のためには，比較的小さく，簡単に変更可 能なコンポーネントで分散システムを構成するのがよい – システム内部のインターフェースの定義と相互作用の記述が必要 • 一つの巨大プログラムで実装されるモノリシックなアプローチ は，コンポーネントの変更が難しく，クローズなシステムとな りやすい（一般論） • 分散システムの変更要求は，しばしばコンポーネントのポリ シの変更 – 内容によるWebキャッシュの例：列車の時刻表は残したいが刻々と 変わる高速道路の現在の交通状況は残したくない • ポリシとメカニズムの分離が必要 – 様々なパラメータ，あるいはポリシの記述を可能にスケーラビリティ
• 最も重要なデザインゴール
• 三つの次元（Clifford Neuman, 1994）
– サイズー利用者や資源の数（信頼性、性能） – 距離ーシステムが分散している距離（信頼性、性 能） – 管理ー独立した組織の数（変更の容易さ、ポリシ の衝突）• 一次元以上スケーラブルなシステムは，ス
ケールアップすると性能に影響することがあ
る
スケーラビリティの問題（１）
• サイズに関するスケーラビリティを考えた場合 – 集中型サービス（多数ユーザに対応できない） – 集中型データ（大規模データに対応できない） – 集中型アルゴリズム（分散データの収集，配布で破綻） は避けなければならない • 非集中型アルゴリズムは以下の点で集中型と異な る – どのノードもシステム全体の情報を知らない – 局所的な情報で決定する – ノードの故障はアルゴリズムに影響しない – 絶対時計（グローバルクロック）は仮定しないスケーラビリティの問題（２）
• 地理的なスケーラビリティの問題
– LANでは同期通信で問題ない（～数百us）が WANでは大問題（～数百ms） – LANは高信頼，マルチキャストも可だがWANは パケットロスがあり，一対一が基本 • サービス発見はLANだとブロードキャストすればよい が，広域だと地球規模，数十億人規模でスケールする 設計が必要 – 集中型のシステムはWANの遅延，低信頼性によ り資源の有効利用ができないスケーラビリティの問題（３）
• 複数の管理ドメインをまたがる分散システム
– 資源の利用法，管理，セキュリティなどポリシの 違いを吸収する必要がある – 通常，組織の管理者は信頼するが，他の組織の 管理者を同様に信頼できるか？ – 他の組織のユーザに対して異なる権限，アクセス 制御が必要？ – 他組織の信頼できないプログラムの実行スケールするための技術
• 通信遅延隠蔽 – 遠隔のサービスの返答を待たない＝非同期通信 – 通信量を減らす • クライアントにサーバ側処理（入力チェックなど）を移動 • 分散 – 要素を分割して分散させる – DNSの例：階層的なドメイン名を重複のないゾーンに分割。それぞれ のゾーンは単一サーバで処理 – WWWの例：文書を分散格納しているからスケールする • 複製 – 可用性の向上，負荷分散，通信遅延隠蔽 – キャッシュ：通常オンデマンドでクライアント主導 – 複製間の一貫性制御：強さは利用形態（Web vs auction）による落とし穴
• 起こしやすい間違った仮定
– ネットワークは高信頼である – ネットワークはセキュアである – ネットワークは均一である – ネットワークトポロジは変化しない – ネットワーク遅延はない – ネットワークバンド幅は無限である – 通信のコストはない – 管理者は一人概要のまとめ
• 分散システムは，複数の
自立
した計算機を
単一
の
一貫
したシステムとして
みせる
– 複数計算機で実行されているアプリケーションを統合 – 設計次第ではネットワークのサイズに応じてスケール 可能 – ソフトウェアの複雑さ，性能の低下，セキュリティの問 題も考慮する必要がある• 分散透明性
の実現は分散システムの目標であ
るが
– 透明性の程度と性能はトレードオフの関係• ネットワークの間違った仮定
分散システムのアーキテクチャ
• ソフトウェアアーキテクチャ
– どのようなソフトウェアコンポーネントで構成され，ど のように相互作用が行われるか – アーキテクチャのスタイル• システムアーキテクチャ
– 集中アーキテクチャ – 分散アーキテクチャ – ハイブリッドアーキテクチャ• 自立的システム（
autonomic systems）
– フィードバック制御用語
• コンポーネント（
component）
– 明確に定義された（well-defined）インターフェー スを持つ交換可能な（ソフトウェアの）構成単位• コネクタ（
connector）
– コンポーネント間の通信，調整，協力を伝えるメカ ニズム – 遠隔手続き呼出し（RPC），メッセージパッシング， データストリーミングなどレイヤアーキテクチャ
（
Layered Architectures）
• 層状アーキテクチャ，階層アーキテクチャ
• レイヤ
iはレイヤi-1
を呼び出せる
• ネットワークの
コンポーネントで
よく利用される
レイヤN レイヤN-1 … レイヤ2 レイヤ1 リクエスト のフロー レスポンス のフローオブジェクトベースアーキテクチャ
（
Object-based Architectures）
• より疎な構成
• オブジェクトがコンポーネント
• 遠隔手続き呼出し
Object Object Object Object Object メソッド 呼出しデータセンタアーキテクチャ
（
Data-centered Architectures）
• 共有レポジトリ
により通信を行う
• 多くのネットワークアプリケーションは，共有
分散ファイルシステムの
ファイル
を利用して
通信を行う
•
Webベースのアプリケーションは，Webベース
の共有データサービスを利用する
イベントベースアーキテクチャ
（
Event-based Architectures）
• イベントの伝搬で通信する
• 発行・購読（
Publish/subscribe）システム
– 購読しているプロセスにイベントを発行する – 疎結合（loosely coupled）型プロセス – 参照分離（Referentially decoupled） • お互いに参照する必要はない パブリッシュ（発行） イベント伝達共有データスペース
（
Shared Data Spaces）
• データセンタアーキテクチャとイベントベース
アーキテクチャの組合せ
• プロセスは時間的にも分離
– 通信中にアクティブでなくてもよい•
SQL，ファイル
データ伝達 パブリッシュ（発行）システムアーキテクチャ
• システムアーキテクチャ
– コンポーネントの相互作用と配置の方法• クライアントサーバモデル
クライアント サーバ 返事待ち リクエスト 返事 サービス実行 時間クライアントサーバモデル
• コネクションレスの通信（例：UDP，user datagram protocol）
– LANなど高信頼な環境では効率的 – クライアントはメッセージ（サービスと引数）をサーバに送信， サーバは返事を送信 – 信頼性のない環境，リクエストorレスポンスが失われる可能性 • リクエストの再送信→サービスを二度実行する可能性 • 「銀行口座から100万円引き出す」などは困る • 「残高照会」などは何度実行してもよい＝idempotentな操作 • 信頼性のあるコネクション指向の通信（例：TCP，
transmission control protocol）
– 広域環境のような低信頼な環境
– コネクションを確立してリクエストを発行 – コネクション（再）接続のコスト
アプリケーションのレイヤリング
• （データベースをアクセスする）クライアント
サーバアプリケーションは三層の階層からな
る
– ユーザインタフェース層（user-interface level） • クライアント（キャラクタ，グラフィックス） – 処理層（processing level） • それぞれのアプリケーション処理 – データ層（data level） • ファイルシステム，データベース • 永続性（persistency）をもつインターネット検索エンジンの例
ユーザインタフェース クエリ生成 Webページのデータベース ランキング アルゴリズム HTML生成 ユーザ インタフェース層 処理層 データ層 キーワード式 データベース クエリ メタ情報付きの Webページのタイトル ランク付リスト リストを含むHTMLのページ二層アーキテクチャ
• 三層レイヤをクライアントとサーバに分ける
ユーザインタフェース アプリケーション データベース 機種依存のUI処理 UI処理全体 ある程度のアプリケーション 処理（編集やフォームチェックなど） アプリケーション処理全体 （共有ファイルシステム利用など） ある程度のデータ処理も （クライアントキャッシュなど） シン クライアント （管理コスト小） ファット クライアント多層アーキテクチャ
ユーザインタフェース アプリケーション データベース Webクライアント （複数） アプリケーション サーバ （複数） データベース サーバ （例）分散アーキテクチャ
• 垂直分散（vertical distribution） – 機能単位を複数マシンで分散 • 水平分散（horizontal distribution） – 同一機能を複数マシンで分散 – 複数マシンで負荷を分散 – Cf. P2P（peer-to-peer）システム • P2Pシステム – （概念的には）P2Pを構成するプロセスは同一 – プロセス間の相互作用は対称的，クライアントでもありサーバ でもある（サーバント，servent） – オーバレイネットワーク（overlay network） • プロセス間のネットワーク。ルーティングしてプロセス間でメッセージ 通信構造化
P2Pアーキテクチャ
• オーバレイネットワークを決定的手続きで構成
• 分散ハッシュ表（
distributed hash table, DHT）を
構成
– ハッシュキーは128ビット（MD5），160ビット（SHA1）な どの広いID空間 – 複数のノードでハッシュ表を分割 • ノードのハッシュ値によりID空間を分割• データを
LOOKUPするとき，そのデータが割当て
られているノードを返す
– データが割当てられているノードにルーティングするChord [Stoica et al., 2003]
0 4 8 12 2 6 10 14 1 3 5 7 9 11 13 15 実際のノード { 0, 1 } { 2, 3, 4 } { 5, 6, 7 } { 8, 9, 10, 11, 12 } {13, 14, 15 } 担当データキー • succ(k)は最小のノードid≥k • LOOKUP(k)でsucc(k)を返す （アルゴリズムは後の講義だ が，O(log N)ステップで検索） • メンバシップ管理 （前後のノードに知らせる）非構造化
P2Pアーキテクチャ
• 乱数アルゴリズムでオーバレイネットワークを
構築
• データもランダムに配置
• 検索はリクエストをフラッディング（ブロード
キャスト）
• ランダムグラフの生成が目標
– それぞれのノードが，生きているノードの内ランダ ムにcノードの情報を知っているスーパピア（
Superpeers）
• 非構造P2Pではデータ検索は基本フラッディングなた め，ピア数の増加に対し問題がある • CDN（コンテンツデリバリネットワーク）等の応用ではコ ンテンツを高速に発見したいという要求がある • インデックスを保持し，ブローカ（仲介）となるノード＝ スーパピアの導入（cf. Sun JXTA） スーパピア 通常のピア スーパピアネットワークハイブリッドアーキテクチャ
• 協力的（
collaborative）分散システム
•
BitTorrentファイル共有システム[Cohen, 2003]
– 協力的なP2Pファイルダウンロード • ファイルのダウンロードは，コンテンツを提供するノー ドだけが可能 – .torrentファイルはトラッカ（tracker）を示す。トラッ カはファイルのチャンクを保有するアクティブな ノードを保持 – アクティブノードは現在ほかのファイルをダウン ロードしているノードアーキテクチャのまとめ
• ソフトウェアアーキテクチャ＝ソフトウェアの論理的な構成 • システムアーキテクチャ＝コンポーネントがどのように異な るマシンに配置されるか • アーキテクチャのスタイル – レイヤ，オブジェクト指向，イベント指向，データスペース指向 アーキテクチャ • クライアントサーバモデル – 集中アーキテクチャとなりやすい • P2Pシステム – プロセスは等しく振る舞う – オーバレイネットワーク＝ほかのピアの局所リストを持つ論理 的なネットワーク – 構造化P2Pと非構造化P2Pサーバ設計における一般的なこと
• サーバ
– クライアントからのリクエストを待ち，実行する• 反復サーバ（
iterative server）
– サーバがリクエストを実行し，レスポンスを返す• 並行サーバ（
concurrent server）
– 別のスレッドorプロセスにリクエストを依頼 – 直ちに次のリクエストを待つ分散システムにおけるスレッド
• プロセスをブロックさせないでブロッキングシ
ステムコールを呼べる
• 複数のコネクションの管理に有用
• マルチスレッドクライアント
– 広域ネットワークの遅延（数百ミリ秒～数秒）隠蔽 – （例）Webブラウザ • ページ内複数ドキュメントの並列受信 • 受信しながら表示マルチスレッドサーバ
• 典型的なマルチスレッドサーバの例
オペレーティングシステム サーバ ディスパッチャ スレッド ワーカ スレッド１ ワーカ スレッド２ ワーカ スレッド３ ネットワーク からの要求 ワーカスレッドに要求をディスパッチ スレッドプールサーバのコンタクト先
• クライアントはサーバのエンドポイント（
end
point）orポート（port）にリクエストを発行
•
TCP，UDPのポート番号
– Internet Assigned Numbers Authority (IANA)が管 理
範囲 種類 備考
0～1023 Well Known Ports 登録なしに利用不可
UNIXではroot権限が必要
1024～49151 Registered Ports 登録なしに利用不可
49152～65535 Dynamic and/or Private
代表的なポート番号
キーワード （サービス）
番号 説明
ftp-data 20/tcp, 20/udp, 20/sctp File Transfer [Default Data]
ftp 21/tcp, 21/udp, 21/sctp File Transfer [Control]
ssh 22/tcp, 22/udp, 22/sctp Secure Shell, RFC 4251, 4960
telnet 23/tcp, 23/udp Telnet
smtp 25/tcp, 25/udp Simple mail transfer
http 80/tcp, 80/udp, 80/sctp World Wide Web HTTP
imap 143/tcp, 143/udp Internet Message Access Protocol
https 443/tcp, 443/udp, 443/sctp http protocol over TLS/SSL
imaps 993/tcp, 993/udp Imap4 protocol over TLS/SSL
http://www.iana.org/assignments/port-numbers http://www.rfc-editor.org/
HTTPサーバへのアクセス例
$ telnet www.tsukuba.ac.jp 80 Trying 130.158.69.246... Connected to www.tsukuba.ac.jp. Escape character is '^]'. GET /index.html HTTP/1.0 HTTP/1.1 200 OKDate: Mon, 14 Dec 2009 22:37:09 GMT Server: Apache/2.2.3 (CentOS)
…
Content-Length: 451 Connection: close
Content-Type: text/html
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> <HTML>
…
</HTML>
Connection closed by foreign host.
HTTPサーバへの リクエスト HTTPサーバからの レスポンス telnetコマンドでwww.tsukuba.ac.jpの port 80/TCPに接続 （リターンを2回） HTTPサーバが接続を切断
