プロセス

Transcription

1 分散システムのアーキテクチャ プロセス 分散システム 2014 年 10 月 20 日 建部修見

2 アーキテクチャ ソフトウェアアーキテクチャ どのようなソフトウェアコンポーネントで構成され, どのように相互作用が行われるか アーキテクチャのスタイル システムアーキテクチャ 集中アーキテクチャ 分散アーキテクチャ ハイブリッドアーキテクチャ 自立的システム (autonomic systems) フィードバック制御

3 システムアーキテクチャ システムアーキテクチャ コンポーネントの相互作用と配置の方法 クライアントサーバモデル クライアント 返事待ち リクエスト 返事 サーバ サービス実行 時間

4 クライアントサーバモデル コネクションレスの通信 ( 例 :UDP,user datagram protocol) LAN など高信頼な環境では効率的 クライアントはメッセージ ( サービスと引数 ) をサーバに送信, サーバは返事を送信 信頼性のない環境, リクエスト or レスポンスが失われる可能性 リクエストの再送信 サービスを二度実行する可能性 銀行口座から 100 万円引き出す などは困る 残高照会 などは何度実行してもよい =idempotent な操作 信頼性のあるコネクション指向の通信 ( 例 :TCP, transmission control protocol) 広域環境のような低信頼な環境 コネクションを確立してリクエストを発行 コネクション ( 再 ) 接続のコスト

5 アプリケーションのレイヤリング ( データベースをアクセスする ) クライアントサーバアプリケーションは三層の階層からなる ユーザインタフェース層 (user-interface level) クライアント ( キャラクタ, グラフィックス ) 処理層 (processing level) それぞれのアプリケーション処理 データ層 (data level) ファイルシステム, データベース 永続性 (persistency) をもつ

6 インターネット検索エンジンの例 ユーザインタフェース ユーザインタフェース層 キーワード式 クエリ生成 データベースクエリ リストを含む HTML のページ HTML 生成 ランキングアルゴリズム ランク付リスト 処理層 メタ情報付きの Web ページのタイトル Web ページのデータベース データ層

7 二層アーキテクチャ 三層レイヤをクライアントとサーバに分ける シンクライアント ( 管理コスト小 ) ファットクライアント ユーザインタフェース アプリケーション データベース 機種依存の UI 処理 UI 処理全体 ある程度のアプリケーション処理 ( 編集やフォームチェックなど ) アプリケーション処理全体 ( 共有ファイルシステム利用など ) ある程度のデータ処理も ( クライアントキャッシュなど )

8 多層アーキテクチャ ( 例 ) ユーザインタフェース Web クライアント ( 複数 ) アプリケーション データベース アプリケーションサーバ ( 複数 ) データベースサーバ

9 分散アーキテクチャ 垂直分散 (vertical distribution) 機能単位を複数マシンで分散 水平分散 (horizontal distribution) 同一機能を複数マシンで分散 複数マシンで負荷を分散 Cf. P2P(peer-to-peer) システム P2P システム ( 概念的には )P2P を構成するプロセスは同一 プロセス間の相互作用は対称的, クライアントでもありサーバでもある ( サーバント,servent) オーバレイネットワーク (overlay network) プロセス間のネットワーク ルーティングしてプロセス間でメッセージ通信

10 構造化 P2P アーキテクチャ オーバレイネットワークを決定的手続きで構成 分散ハッシュ表 (distributed hash table, DHT) を構成 ハッシュキーは 128 ビット (MD5),160 ビット (SHA1) などの広い ID 空間 複数のノードでハッシュ表を分割 ノードのハッシュ値により ID 空間を分割 データを LOOKUP するとき, そのデータが割当てられているノードを返す データが割当てられているノードにルーティングする

11 Chord [Stoica et al., 2003] {13, 14, 15 } 1 { 0, 1 } 実際のノード 2 succ(k) は最小のノードid k LOOKUP(k) でsucc(k) を返す 13 3 ( アルゴリズムは後の講義だ 12 { 8, 9, 10, 11, 12 } { 2, 3, 4 } 4 が,O(log N) ステップで検索 ) メンバシップ管理 担当データキー ( 前後のノードに知らせる ) { 5, 6, 7 }

12 非構造化 P2P アーキテクチャ 乱数アルゴリズムでオーバレイネットワークを構築 データもランダムに配置 検索はリクエストをフラッディング ( ブロードキャスト ) ランダムグラフの生成が目標 それぞれのノードが, 生きているノードの内ランダムに c ノードの情報を知っている

13 スーパピア (Superpeers) 非構造 P2P ではデータ検索は基本フラッディングなため, ピア数の増加に対し問題がある CDN( コンテンツデリバリネットワーク ) 等の応用ではコンテンツを高速に発見したいという要求がある インデックスを保持し, ブローカ ( 仲介 ) となるノード = スーパピアの導入 (cf. Sun JXTA) 通常のピア スーパピア スーパピアネットワーク

14 ハイブリッドアーキテクチャ 協力的 (collaborative) 分散システム BitTorrent ファイル共有システム [Cohen, 2003] 協力的な P2P ファイルダウンロード ファイルのダウンロードは, コンテンツを提供するノードだけが可能.torrent ファイルはトラッカ (tracker) を示す トラッカはファイルのチャンクを保有するアクティブなノードを保持 アクティブノードは現在ほかのファイルをダウンロードしているノード

15 アーキテクチャのまとめ ソフトウェアアーキテクチャ = ソフトウェアの論理的な構成 システムアーキテクチャ = コンポーネントがどのように異なるマシンに配置されるか アーキテクチャのスタイル レイヤ, オブジェクト指向, イベント指向, データスペース指向アーキテクチャ クライアントサーバモデル 集中アーキテクチャとなりやすい P2P システム プロセスは等しく振る舞う オーバレイネットワーク = ほかのピアの局所リストを持つ論理的なネットワーク 構造化 P2P と非構造化 P2P

16 演習問題 ソフトウェアアーキテクチャ システムアーキテクチャとは何か? 国際標準化機構 (ISO) が定めた OSI(Open Systems Interconnection) 参照モデルを調べよ 構造化 P2P における DHT は Chord の他にどのようなものが提案されているか? それぞれの特徴をまとめよ

17 プロセス 独立したプログラムの実行 互いに影響を及ぼさない ( 同一 CPU を透明に利用, 並行透明性 ) 独立した論理アドレス空間をもつ プロセステーブル CPU レジスタメモリマップオープンファイルアカウント情報権限 (privileges)

18 プロセス生成とプロセス切替 プロセス生成 論理アドレス空間の生成 メモリセグメントの初期化 ( データセグメントをゼロクリア, テキストセグメントにプログラムをロード, スタック領域の設定 ) プロセス切替 CPU コンテキストの保存 レジスタ, プログラムカウンタ, スタックポインタなど メモリ管理ユニット (MMU) のレジスタの修正と translation lookaside buffer(tlb) の無効化 ( メモリ不足の場合 ) プロセスのスワップイン

19 スレッドとは? プロセス内の * 独立した * プログラム実行 同一プロセス ID プロセスほど高い透明性を持たない 論理メモリ空間を共有 ファイルディスクリプタなどプロセス資源を共有 一般にスレッド生成はプロセス生成より軽い

20 スレッド切替 スレッドコンテキスト CPU コンテキスト レジスタ, プログラムカウンタ, スタックポインタなど スレッド管理情報 ほかの情報は持たない 同一プロセスのスレッド間のデータ保護は開発者に任せられる マルチスレッドプログラムの性能はシングルスレッドに比べ悪くならない 多くの場合で性能向上が見込まれる スレッドは保護されない 適切な設計と KISS(Keep it simple, stupid) が有効

21 プロセス vs スレッド 生成 実行オーバヘッド スレッド 小 プロセス メモリ共有別々 プロセス資源共有別々 データ共有 保護 メモリのポインタ渡し ( コピーは不必要 ) 他スレッドのメモリ 資源を破壊する可能性あり スレッドの実行制御が必要 大 パイプ ソケット ファイルなど 他プロセスのメモリ 資源は保護される

22 非分散システムにおける スレッドの利用 プログラム構造の単純化 表計算における入力処理 ( スレッド 1) と合計値などの値更新 ( スレッド 2) スレッド 1 は入力を処理 スレッド 2 は変更を待ち変更があれば更新 マルチプロセッサでは並列に実行可能 プロセス間通信のオーバヘッド削減 ( 名前付 ) パイプ, メッセージキュー, 共有メモリセグメント カーネル経由のためコンテキスト切替のコスト大

23 main(int argc, char *argv[]) { for (i = 1; i < argc; ++i) { if (i == 1) /* get the first picture */ buf = get_next_pic(argv[i]); else /* wait for the previous process */ pthread_join(tid, &buf); if (i < argc 1) } } /* get the next picture */ pthread_create(&tid, NULL, get_next_pic, argv[i + 1]); display_buf(buf); /* display the picture */ free(buf); if (getchar() == EOF) break; スライドショウのプログラム例 表示している合間に次の画像を読込

24 スレッドの実装 スレッドの生成と解放,mutex ロック, 条件変数 ユーザレベルスレッド 軽い ( カーネル経由ではない ) 入力待ちや無限ループでブロックするとプロセス全体がブロックしてしまう カーネルレベルスレッド スレッドスケジューリングはカーネルが行うため ブロックしても大丈夫 スレッド操作のコスト大 ( システムコール ) ハイブリッド ユーザレベルスレッドとカーネルレベル Lightweight processes(lwp)

25 並列性の制御の必要性 スレッド間でメモリ プロセス資源を共有しているため 破壊してしまう可能性がある 例 : 共有カウンタのインクリメント counter++ 1. counter の値をレジスタにロード 2. レジスタの値をインクリメント 3. レジスタの値を counter にストア スレッド 1 1. counter の値をレジスタにロード 2. レジスタの値をインクリメント 3. レジスタの値をcounterにストア スレッド 2 1. counterの値をレジスタにロード 2. レジスタの値をインクリメント 3. レジスタの値をcounterにストア

26 共有カウンタのインクリメントの例 pthread_mutex_t count_mutex = PTHREAD_MUTEX_INITIALIZER; int count; void increment_count() { pthread_mutex_lock(&count_mutex); count++; データ競合領域 pthread_mutex_unlock(&count_mutex); } int get_count() { int c; pthread_mutex_lock(&count_mutex); c = count; データ競合領域 pthread_mutex_unlock(&count_mutex); return (c); } // ensure atomic increment // guarantee memory is synchronized

27 仮想化 ( 異なるシステムのインターフェースをもち ) 異なるシステムのように振る舞う 既存ソフトウェア (legacy software) の実行 他 OS, アーキテクチャのプログラムの実行 IBM 370[1970] の仮想マシン Cygwin, Wine VMWare,Xen,KVM

28 コンピュータのインターフェース ライブラリ関数 アプリケーション システムコール ライブラリ オペレーティングシステム 特権命令 通常命令 ハードウェア 仮想化は上記のインターフェースを模擬すること

29 仮想マシンのアーキテクチャ アプリケーションアプリケーション アプリケーションアプリケーション ランタイムシステム オペレーティングシステム オペレーティングシステム 仮想マシンモニタ (VMM) ハードウェア ハードウェア プロセス仮想マシン Java VM など 仮想マシンモニタ ( ハイパーバイザ )

30 サーバ設計における一般的なこと サーバ クライアントからのリクエストを待ち, 実行する 反復サーバ (iterative server) サーバがリクエストを実行し, レスポンスを返す 並行サーバ (concurrent server) 別のスレッドorプロセスにリクエストを依頼 直ちに次のリクエストを待つ

31 分散システムにおけるスレッド プロセスをブロックさせないでブロッキングシステムコールを呼べる 複数のコネクションの管理に有用 マルチスレッドクライアント 広域ネットワークの遅延 ( 数百ミリ秒 ~ 数秒 ) 隠蔽 ( 例 )Web ブラウザ ページ内複数ドキュメントの並列受信 受信しながら表示

32 マルチスレッドサーバ 典型的なマルチスレッドサーバの例 ワーカスレッドに要求をディスパッチ スレッドプール サーバ ディスパッチャスレッド ワーカスレッド 1 ワーカスレッド 2 ワーカスレッド 3 オペレーティングシステム ネットワークからの要求

33 サーバのコンタクト先 クライアントはサーバのエンドポイント (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

34 代表的なポート番号 キーワード ( サービス ) 番号 説明 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

35 HTTP サーバへのアクセス例 $ telnet 80 Trying Connected to Escape character is '^]'. GET /index.html HTTP/1.0 ( リターンを2 回 ) HTTP/ OK Date: Mon, 14 Dec :37:09 GMT Server: Apache/2.2.3 (CentOS) Content-Length: 451 Connection: close Content-Type: text/html telnet コマンドで の port 80/TCP に接続 HTTP サーバへのリクエスト HTTP サーバからのレスポンス <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> <HTML> </HTML> Connection closed by foreign host. HTTPサーバが接続を切断

36 その他の事項 割込 例 :FTP サーバへの大きなファイル転送を取り消したい コネクションの切断 Out-of-band(OOB) データの送信 サーバでシグナル割込がかかる 状態 ステートレスサーバ クライアントの状態をサーバ側で保持しない クライアントとは関係なく状態を変更 FTP,HTTP,NFSv2,NFSv3 ステートフルサーバ 状態を持つ クライアントが状態を消去する 性能向上のため 障害時の復旧を考える必要がある NFSv4

37 セッション状態 (session state) 単一ユーザの状態を一定の期間保持 永遠ではない 失われてもまたやり直せばよい Web ブラウザのクッキー (cookie) クライアント側にサーバの状態を保持 消去してもまたやり直せばよい

38 まとめ 特に分散システムでは スレッドは有用 ブロッキング I/O 操作を行いながら CPU を活用 ただし データ競合を起こさないよう並列性の制御が必要 仮想化により既存アプリケーション, 他 OS のアプリケーションが実行可能に VMM では実行環境ごと保存, 移動が可能 サーバ設計に関しての一般的事項

39 演習問題 プロセスとスレッドの違いは何か? Xen と KVM はそれぞれどのように仮想化を実現しているか? telnet で の http ポートにアクセスしてみよ telnet で poplar.cs.tsukuba.ac.jp の smtp ポートにアクセスし,VRFY tatebe,expn c-sotsuken, QUIT を入力してみよ