通信ソフトウェア

並列分散ソフトウェア

                                       電子・情報工学系
                                       新城 靖
                                       <yas@is.tsukuba.ac.jp>

このページは、次の URL にあります。
http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2001/2002-01-10
あるいは、次のページから手繰っていくこともできます。
http://www.hlla.is.tsukuba.ac.jp/~yas/sie/
http://www.is.tsukuba.ac.jp/~yas/index-j.html
http://www.hlla.is.tsukuba.ac.jp/~yas/index-j.html

■復習

■今日の重要な話

通信プリミティブの分類

クライアント・サーバ型の通信。

グループ通信（マルチキャスト）の実現

資料：

Ａ．Ｓ．タネンバウム著、水野忠則、鈴木健二、西宮洋太郎、佐藤文明訳、分 散オペレーティングシステム、プレンティスホール (1996)
第２章 分散システムにおける通信

■プロセス間通信

２つの重要なパタン プロセス間通信の構造化。send, receive は、goto 相当。

■通信プリミティブ

◆marshaling/unmarshaling

プログラム中のデータ項目とネットワーク上を流れるメッセージに対応づける。
marshaling
メモリ中からデータ項目を集めて、ネットワークでメッセージとして 転送するのに適した形式にまとめる。
unmarshaling
逆。
英語の綴りは、l が１つのものと２つのものがある。教科書によって違う。

◆XDR

SunRPC で使われているデータ形式。バイナリ文化。

rpcgen というスタブ・コンパイラがある。 marshaling 部分の自動生成。

SunRPC を使わなくて、XDR だけを使う方法もある。

xdrmem_create(XDR *, const caddr_t, const uint_t, const enum xdr_op)
メモリの指定されたの番地に保存／回復／メモリの解放。
void xdrstdio_create(XDR *, FILE *, const enum xdr_op)
FILE * を通じて、構造体の読み書き。

xdr_int.c、 Sun RPC examples

◆sprintf()/sscanf()

文字列に直して送る方法もある。文字列文化。インターネットのアプリケーショ ンでよく使われる。

思ったほど遅くはない。

◆sendとreceive

通信の基本命令

◆通信プリミティブの分類

◆同期型／非同期

図

send,receive それぞれ２種類ある。

非同期の方が、並列性が高い。しかし、、、

  1. 転送完了までメッセージ・バッファを書き換えられない
  2. 送信側は、転送が終了したかわからない
1. は、バッファリングで解決可能。しかし、無駄なコピー、フロー制御の問 題がある。

2. は、転送完了割り込みで解決可能。プログラミングが難しい。 割り込みよりは、マルチスレッドがよい。

プログラミングの選択

時間切れ(timeout)。同期で使われる。

◆バッファリング

コピーするかしないか。

同期、非同期とは直行しているとも言えるが、普通は同期の場合にはバッファ リングを省略してコピーを減らす。

メールボックスには、しばしば有限のバッファがもうけられる。

バッファがいっぱいだった時にどうするか。 いっぱいの時にだけ送信側をブロックさせる、という方法でいいのか。

◆アドレス指定

直接アドレス指定では、receiveする前にsendされると、どのプロセスにメッ セージを送っていいのかわからない。

解決

◆信頼性の有無

分散システムでは、メッセージは、失われることがある。

■TCP/IP

◆IP

IPデータグラム（datagram）転送サービス

◆TCP

ストリーム転送サービス データの区切りが保存されると、sequenced packet と呼ばれる。

TCP層の技術1:再転送付き肯定確認応答

IP層は、転送サービスとして信頼性のないデータグラムを提供する。TCP 層の仕事は、それを使って、双方向のストリーム転送サービス提供することで ある。そのために、「再転送付き肯定確認応答(positive acknowledgement with retransmission)」という、一般的によく用いられている技術が使われ ている。この技術では、データの受け手は、データを受け取る度に、送り手に 確認応答(acknowledgement, しばしば ack と省略される)を返す。データの 送り手は、確認応答を受け付けると、次のデータを送る。ある時間がたっても 確認応答が来なかった場合、データの送り手は、再転送(retransmit)する。

TCP層の技術2:スライディング・ウィンドウ

ストリームを実現する技術として、TCPは、スライディング・ウィンドウ (sliding window)と呼ばれる技術を用いている。この技術では、ウィンドウと 呼ばれる範囲を設定して、確認応答が来る前に、次々とウィンドウ内のパケッ トを送出す。確認応答を受け取ると、ウィンドウを「スライド」させ、次のパ ケットを送り出す。

フロー制御

受け手のバッファ（メモリ）は、有限である。送り手は、受け手消費する速度 に合わせてパケットを送出さなければならない。このような制御をフロー制御 という。TCPでは、スライディング・ウィンドウを用いてフロー制御を行って いる。

■クライアント・サーバ通信

手続き呼出しの形に見えたら RPC (Remote Procedure Call)。

通信を構造化。send()/receive() を直接使うのは、goto (jump) でプログラ ムを書くようなもの。call/if/while で書きたい。

プロセスを２種類に分類する。通信は、次のパタンを繰り返す。

クライアント
先にメッセージ(要求)を送る、後でメッセージ(応答)を受け取る
サーバ
先にメッセージ(要求)を受け取る、後でメッセージ(応答)を返す

図? 通信のパタンからみたクライアントとサーバの定義

図? 通信のパタンからみたクライアントとサーバの定義

◆３つの基本命令

  1. get_request(port_t serviceport,message_t request/*in*/): サーバ・プロセスにより使われる。クライアント・プロ セスから送られてくる要求メッセージを待つ。
  2. send_reply(port_t client,message_t reply): サーバ・プロセスにより使われる。クライアント・プロ セスに対して応答メッセージを送る。
  3. do_operation(port_t server,message_t request/*out*/, message_t reply/*in*/): クライアント・プロセスにより使われる。サーバへ要 求を送り、サーバからの応答が返ってくるまで待つ。
サーバは、普通、get_request() で、クライアントから何か要求メッセージが 届くのを待っている。

クライアントが何かサーバにして欲しい時には、do_operation() で、サーバ に要求メッセージを送る。そして、サーバからの応答メッセージを待つ。

サーバは、要求メッセージを受けとると、何か仕事をして、send_reply() で、 クライアントに応答メッセージを返す。そして、再び次の要求メッセージ を待つ。

１つのサーバに複数のクライアントがアクセスすることがある。１つのクライ アントも、複数のサーバに同時にアクセスすることもできる。

図? クライアント・サーバ・モデルに基づく通信で使う３つの命令

図? クライアント・サーバ・モデルに基づく通信で使う３つの命令

◆実現例

例１：７種類のメッセージを使う方法 図

例２：３種類（回数）

◆RPC

RPC (Remote Procedure Call) ( 遠隔手続き呼び出し ) は、分散システムを構築する時に広く使われている「プロセス間通信」の方法。 NFS (Network File System) を始めとする分散ファイル・システムの構築や、 や NIS (Network Information Service) (パスワード・ファイルなどの共有) で使われている。

（＜−＞文化的には、TCP/IP上のテキストベースのプロトコルとは対照。）

◆RPCの特徴

TCP/IP で提供されているストリームや UDP/IP で提供されているデー タグラムと比較して、RPC には次のような特徴がある。

孤児が、ロックを持っていたら、孤児を消しただけでは話を終わらない。

◆idempotent冪等

冪等(idempotent)な操作とは、 その操作を何回繰り返しても、1回だけ実行した時と同じ結果になるもの。

例：

idempotentではない操作

◆stateless server

無状態サーバ(stateless server) とは、サーバ内部に状態を保持しないようなサーバ。

状態の例

RPCで冪等な操作や無状態サーバを実現すると、クラッシュに強いシステムを 作れる。クライアントは、サーバから応答がない場合、何度要求を再送信して もよい。

例：NFS Version 2

サーバは、ファイルに対する書き込み要求を受け付けると、ディスクへ の書き込みを完了してから応答を返す。 応答が返ってきた要求は、 ディスクへの書き込みが完了したことが保証されている。 この段階でサーバがクラッシュしたとしても、なにも失われない。

しかし、、、重たい。NFS Version 3 では、状態付きのサーバになった。

表? NFSで使われているRPCの手続き

 
--------------------------------------------------------------------------------
手続き名	意味			関連するコマンド、 システムコール
--------------------------------------------------------------------------------
null()    	何もしない		rpcinfo -u hostname nfs コマンド 
getattr() 	属性の読み出し 		ls -l コマンド, stat システムコール , open システムコール
setattr() 	属性の設定 		chmod , chown コマンド
lookup()  	ファイルの検索	 	open システムコール
readlink() 	シンボリックリンクの読み出し
			 		ls -l コマンド, readlink システムコール
read() 		ファイルの読み出し	read システムコール
write() 	ファイルの書き込み 	write システムコール
create() 	ファイルの作成	 	creat システムコール, open システムコール
remove() 	ハードリンクの削除 	rm コマンド, unlink システムコール
rename() 	ファイル名前の変更 	mv コマンド, rename システムコール
link()		ハードリンクの作成 	ln コマンド, link システムコール
symlink() 	シンボリックリンクの作成
				 	ln -s コマンド, symlink システムコール
mkdir() 	ディレクトリの作成	mkdir コマンド
rmdir() 	ディレクトリの削除 	rmdir コマンド
readdir() 	ディレクトリの読み出し 	ls コマンド
statfs() 	ファイルシステムの利用状況
				 	df コマンド, statfs システムコール
commit()*	ディスクへの書き込み	fsync システムコール
access()*	アクセス権のチェック	access システムコール
--------------------------------------------------------------------------------
 は、NFS Version 3 の新しい手続き。

◆cookie

RPC のようにコネクションが作られない 通信サービスを使う時に 冪等や無状態といった性質を実現する時に必要になる技術。

例：NFSでのディレクトリの読み込み手続き nfsproc_readdir() で、１回の RPC で全部のデータを返せないことが起きる。 ディレクトリのどの位置まで読み込んだかを 示す中間状態を クッキー(cookie) という形でクライアントに返す。

クライアントは、次の RPC の呼び出しで、 前回受けとった応答の中のクッキーを、サーバへの要求に含めて送す。 

/usr/include/rpcsvc/nfs_prot.x:

const NFS_COOKIESIZE	= 4;
typedef opaque nfscookie[NFS_COOKIESIZE];

/*
 * Arguments to readdir
 */
struct readdirargs {
	nfs_fh dir;		/* directory handle */
	nfscookie cookie;
	unsigned count;		/* number of directory bytes to read */
};

struct entry {
	unsigned fileid;
	filename name;
	nfscookie cookie;
	entry *nextentry;
};

struct dirlist {
	entry *entries;
	bool eof;
};

union readdirres switch (nfsstat status) {
case NFS_OK:
	dirlist reply;
default:
	void;
};

nfsproc_readdir() で、１回目と２回目の RPC の間にディレクトリの内容が 更新された場合、どのような結果になるのか不明。

◆HTTP での cookie

HTTP では、 TCP/IP というコネクションが作られる通信サービスが使われいるが、 １ページ１ページを転送する度にコネクションを切っているので、 複数ページ のアクセスの時にはコネクションが作られない通信サービスを使っているのと 論理的に同じ。

HTTP でも、クライアントの状態をサーバ側で保存するためにクッキーが使わ れることがある。

問題点

◆高速化

◆プログラミング・スタイル

RPC向きのものと向いていないもの。

◆SunRPC

■グループ通信

通信の分類

放送は、特定の（物理的な）ネットワークに属するプロセス「全部」に送る。

何に使えるか

グループ通信で何が難しいか

◆設計の論点

並列処理では、クローズが多い。 IP MBone のように、オープンでないとどうしようもないものもある。

対等だと、クラッシュに強い（single point of failure がない）が、何をす るにもすぐ投票が必要になる。

◆メンバシップの管理

グループサーバを持つか持たないか。

難しいのは、メンバのプロセスがクラッシュした時。 何も言わずにグループから抜ける。

◆アドレス指定

◆通信プリミティブ

one-to-oneの通信と同じにしたい。しかし、 障害がなければ、簡単。

◆atomic broadcastの簡単なアルゴリズム

◆メッセージの到着順

one-to-one でも問題があるのに、group 通信だとさらに複雑。

total ordering は、グループ通信では実現が難しすぎる。弱いものが実現さ れる。

プロセスが複数のグループに属していると、１つのメッセージについての順序 だけ考えていてはすまなくなる。

◆スケーラビリテイ

数が増えた時に動くか。

◆冗長性

ネットワークのダウンに対応するには、ネットワークを冗長に しないといけない。冗長性があると、メッセージの重複を うまく扱う必要がでてくる。

下手をすると、メッセージが増幅しながいつまでもぐるぐる回る。

◆例 ISIS システム

分散アプリケーションのためのツールキット。 コーネル大学。

◆ISISの同期性(synchrony)

同期システム(synchronous system)
イベント(マルチキャスト)の順序が厳密に逐次的に発生する。オーバーラップしない。 イベント（マルチキャストを含む）は、完了までの時間は、０。 実現不可能。
緩やかな同期システム(loosly synchronous system)
イベントは有限。
仮想的な同期システム(virtually synchronous system)
因果関係が成り立つようにがんばる。（並行なものは、手抜き。）

◆ISISの通信プリミティブ

ABCAST
緩やかな同期
CBCAST
仮想的な同期
GBCAST
仮想的な同期(グループのメンバシップ用)

最初の実現：２相コミットによる ABCAST 。重すぎる。

  1. 送信者は、タイムスタンプを含むメッセージを全てのメンバに送る。
  2. 各メンバは、送信、または、受信したメッセージで最大のものを最初の送信者に送る。
  3. 送信者は、全ての返事を受け取ると、最大のものを選び、メンバにコミット・メッセージを送る。コミット・メッセージは、タイムスタンプの順に届けられる。
CBCASTの実現

メンバの数：ｎ

各プロセスは、グループごとに、長さｎのベクトルＶを持つ。 ｉ番目の要素は、プロセスｉから正しい順序で受信したメッセージの最後の番号。 ０に初期化される。

  1. プロセスは、送信すべきメッセージがあると、 ベクトルの自分のスロットを増加させ、メッセージの一部として送信する。
  2. メッセージのベクトルをＶ、メモリ中のベクトルをＬとする。 メッセージがｊから送られてきたものとすると、次の条件の時に受け取る。 そうでないものは、この条件が満たされるまでバッファリングされる。

◆ニュースシステム

マルチキャストの実装。
↑[もどる] ←[12月20日] ・[1月10日] →[12月13日]
Last updated: 2002/01/09 23:43:45
Yasushi Shinjo / <yas@is.tsukuba.ac.jp>