通信プリミティブ

並列分散ソフトウェア

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

このページは、次の URL にあります。
http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2003/2003-12-18
あるいは、次のページから手繰っていくこともできます。
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

■連絡

来週、学生証のコピーを持ってくること。学術情報処理センターの並列計算機 のアカウントを作成するために必要。

■復習

■今日の重要な話

通信プリミティブの分類

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

グループ通信(マルチキャスト)の実現

資料:

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

■プロセス間通信

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

■通信プリミティブ

◆marshaling/unmarshaling

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

◆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.cSun RPC examples

◆snprintf()/sscanf()

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

思ったほど遅くはない。

◆sendとreceive

通信の基本命令

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

◆同期型/非同期

send() したプロセスはreceive()されるのを待たずにすぐ再開する。 send() したプロセスがreceive()されるまで止まる。

図? 同期型sendと非同期型send

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

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

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

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

プログラミングの選択

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

◆バッファリング

コピーするかしないか。

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

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

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

◆アドレス指定

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

解決

◆信頼性の有無(reliable or non-reliable)

信頼性性があるかないか。専門用語では、程度問題(高い低い)ではなく、有 るか無いか。

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

■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 で書きたい。

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

クライアント
先にメッセージ(要求)を send() 1回、後でメッセージ(応答)を receive() 1回
サーバ
先にメッセージ(要求)を receive() 1回、後でメッセージ(応答)を send() 1回
send() の回数と receive() の回数は同じ。相互に繰り返す。

図? send(),receive()と繰り返すクライアントと receive(),send() と繰り返すサーバ

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

◆3つの基本命令

  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() で、 クライアントに応答メッセージを返す。そして、再び次の要求メッセージ を待つ。

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

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

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

◆実現例

例1:7種類のメッセージを使う方法

例2:3種類(回数)

◆RPC

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

(<−>文化的には、TCP/IP上のテキストベースのプロトコルとは対照。)

◆RPCの特徴

TCP/IP で提供されているストリームや UDP/IP で提供されているデー タグラムと比較して、RPC には次のような特徴がある。 RPCで「遠隔(remote)」というのは、もともとはネットワークに接続された別 のコンピュータという意味であったが、最近では、同じコンピュータの内部で もRPCが使われる。「遠隔(remote)」とは、「別のコンピュータ」という意味 ではなく、「別のアドレス空間」という意味もある。

RPCでは、別のアドレス空間の間でデータがやり取りされるので、基本的に 「ポインタ」を受け渡しすることはできない。しかし、SunRPC では、ポイン タの先を再帰的に「コピー」する機能がある。

◆RPCを実現する基本命令

下位層では、上であげた3つの基本命令が使われている。

このRPCの3つの命令は、システムコール、または、ライブラリで実現される。 SunRPCには、get_request() に相当する命令が定義されていない。

◆スタブとスタブ生成器

RPCでプログラムを作成するときには、3つの基本命令を利用することは、ほ とんどない。 スタブ生成器(stub generator) を使えば、インタフェースの定義から3つの基本命令を呼び出すようなプログ ラムが自動生成される(lex、yacc )。

スタブ(stub) は、プロセス間通信を普通の手続き呼出しと全く同じ形式で行なうことができ るようにするためのプログラム。 もともとは木の切株の意味。

スタブの分類

クライアント側スタブ
手続き呼出しの形で呼び出される。do_operation() 命令を実行する。
サーバ側スタブ
無限ループを持つプログラム。 get_request() でクライアントからのメッ セージを受け取り、対応する手続きを呼び出し、結果をsend_reply() により 返す。
スタブでは、パラメタ(引数と結果)の 整列化(marshalling) ( パック ) と 非整列化(unmarshalling) ( アンパック ) も行なわれる。SunRPC では、 XDR (eXternal Data Representation) と呼ばれている方法を使っている。

◆Binding

クライアントとサーバを結び付ける。 RPC では、動的(dynamic)になる。

ローカルの手続き呼出しでは、リンク時に固定される。

クライアントとサーバは1対1ではない。

binding のための命令

◆SunRPC での Binding

SunRPCでは、多くの場合、TCP/IPやUDP/IPを使ってメッセージを送る。この場 合、手続きをを次の5つの番号で区別する。 広く使われるUST2_Var(プログラム番号)は、 UST2_Computer( /etc/rpc ) というファイルに含まれている。

TCP/IPまたはUDP/IPでデータを送るにはポート番号が必要になる。 サーバが動作しているホストには、 portmapper とよばれる特殊な RPC のサーバが動作している。 サーバは起動時に自分の<UST2_Var(プログラム番号), UST2_Var(バージョン), UST2_Var(プロトコル), UST2_Var(ポート番号)>をPortmapper に登録する (pmap_set())。

クライアントは、実際にサーバに接続する前に、Portmapper に<UST2_Var(プ ログラム番号), UST2_Var(バージョン), UST2_Var(プロトコル)>を送り、 TCP/IPまたはUDP/IPのポート番号を得る(pmap_getport())。最終的には, この ポート番号を使ってメッセージを送る。

Portmapper 自身のポート番号は、111 に固定されている。

portmapper が binding

図? SunRPC での binding (portmapper)

◆クライアント・サーバ型通信を実現する上での解決すべき問題

(RPCを実現する上での問題)

◆障害

◆クライアントがサーバを見つけられない

◆要求メッセージが紛失

時間切れ再要求。簡単。

◆応答メッセージが紛失

難しい。単純な時間切れだとまずい。

例: 銀行預金転送。

対策:

◆要求受信後、サーバがクラッシュ

番号では対応できない。要求実行前と実行後を区別できない。

図。

RPCのセマンティクス

集中だと、クライアントもサーバもいっしょに死ぬので、問題はない。

◆要求送信後、クライアントがクラッシュ

孤児問題(orphan problem)。

親(クライアント)がいない計算を孤児という。

対応方法

根絶(extermination)。
RPC 前にログに書く。クラッシュしたらログを見て根絶する。重たい。 孫の孤児(grandorphan)問題がある。
再生(reincarnation)
リブートすると、タイムスタンプをサーバに投げる。サーバは、 全孤児を消去する。
穏和な再生(gentle reincarnation)
タイムスタンプを受信すると、サーバは親を探し、見つからない時だけ孤児を消去する。
期限切れ(expiration)
RPC に標準時間Tを与え、その時間内に終了しないものを消去する。 それ以上かかる時には、明示的に要求する。クラッシュ後、サーバがTだけ待てば 孤児は消える。

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

◆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() で、1回の 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() で、1回目と2回目の RPC の間にディレクトリの内容が 更新された場合、どのような結果になるのか不明。

◆HTTP での cookie

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

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

問題点

◆高速化

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

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

◆SunRPC

■グループ通信

通信の分類

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

グループ通信は、いろいろな分散アルゴリズムでよく使われる。

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

◆設計の論点

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

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

◆メンバシップの管理

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

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

◆アドレス指定

◆通信プリミティブ

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

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

◆メッセージの到着順

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

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

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

◆スケーラビリテイ

数が増えた時に動くか。

◆冗長性

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

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

◆例 ISIS システム

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

◆ISISの同期性(synchrony)

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

◆ISISの通信プリミティブ

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

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

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

メンバの数:n

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

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

◆ニュースシステム

マルチキャストの実装。
↑[もどる] ←[12月11日] ・[12月18日] →[12月25日]
Last updated: 2003/12/19 18:11:59
Yasushi Shinjo / <yas@is.tsukuba.ac.jp>