分散システムの概要・アーキテクチャ

分散システムの概要・
アーキテクチャ
分散システム
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）をもつ
インターネット検索エンジンの例
ユーザ
インタフェース層
ユーザインタフェース
リストを含むHTMLのページ
キーワード式
HTML生成
ランク付リスト処理層
クエリ生成
データベース
クエリ
ランキング
アルゴリズム
メタ情報付きの
Webページのタイトル
Webページのデータベース
データ層
二層アーキテクチャ
• 三層レイヤをクライアントとサーバに分ける
ユーザインタフェース
シン
クライアント
（管理コスト小）
機種依存の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]
15
14
0
{13, 14, 15 }
実際のノード
1
{ 0, 1 }
• succ(k)は最小のノードid≥k
2
13
• LOOKUP(k)でsucc(k)を返す
（アルゴリズムは後の講義だ
3
が，O(log N)ステップで検索）
{ 8, 9, 10, 11, 12 }
12
4
{ 2, 3, 4 }
担当データキー
（前後のノードに知らせる）
11
5
10
{ 5, 6, 7 }
9
• メンバシップ管理
8
7
6
非構造化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
Ports
代表的なポート番号
キーワード
（サービス）
番号
説明
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/portnumbers http://www.rfc-editor.org/
HTTPサーバへのアクセス例
$ telnet www.tsukuba.ac.jp 80
telnetコマンドでwww.tsukuba.ac.jpの
Trying 130.158.69.246...
port 80/TCPに接続
Connected to www.tsukuba.ac.jp.
Escape character is '^]'.
HTTPサーバへの
GET /index.html HTTP/1.0 （リターンを2回）
リクエスト
HTTP/1.1 200 OK
HTTPサーバからの
Date: 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サーバが接続を切断
その他の事項
• 割込
– 例：FTPサーバへの大きなファイル転送を取り消したい
– コネクションの切断
– Out-of-band（OOB）データの送信
• サーバでシグナル割込がかかる
• 状態
– ステートレスサーバ
• クライアントの状態をサーバ側で保持しない。クライアントとは関係な
く状態を変更
• FTP，HTTP，NFSv2，NFSv3
– ステートフルサーバ
• 状態を持つ。クライアントが状態を消去する
• 性能向上のため。障害時の復旧を考える必要がある
• NFSv4
セッション状態（session state）
• 単一ユーザの状態を一定の期間保持
– 永遠ではない
– 失われてもまたやり直せばよい
• Webブラウザのクッキー（cookie）
– クライアント側にサーバの状態を保持
– 消去してもまたやり直せばよい
サーバ設計に関するまとめ
• マルチスレッドクライアント、マルチスレッド
サーバ
– ブロッキングI/O操作を行いながらCPUを活用
– ただし、データ競合を起こさないよう並列性の制
御が必要
• 反復サーバと並行サーバ
• コンタクト先
• 割込、状態

Download Report