並行分散ソフトウェア／並列分散ソフトウェア
電子・情報工学系
新城 靖
<yas@is.tsukuba.ac.jp>
このページは、次の URL にあります。
http://www.cs.tsukuba.ac.jp/~yas/sie/pdsoft-2005/2006-01-13
あるいは、次のページから手繰っていくこともできます。
http://www.cs.tsukuba.ac.jp/~yas/sie/
http://www.cs.tsukuba.ac.jp/~yas/
読み書きロックでも、読み込みだけ行うスレッドも読み込みで advisory ロックを行う必要がある。 ロックを行わないでアクセスしてはいけない。
例：銀行口座が円とドルで２種類あった時に、合計の残高を知りたい。
クライアント・サーバ型の通信。
資料： 谷口 秀夫 (編), 谷口 秀夫, 佐藤一朗, 佐藤 文明, 柴田 義孝, 新城 靖, 横山 和俊 (著): "情報処理学会編集 IT Text 分散処理", オーム社 (2005年9月). ISBN: 4274201333.
第２章 基盤技術 (新城)
ネットワークで接続された複数のコンピュータ上で複数のプロセスを動作させ る。プロセスは、全体として１つの仕事を成し遂げる。
ノード：プロセス、あるいは、コンピュータ
メッセージ：ノード間で交換されるデータ
分散システムでは、次のような集中システムでは普通に使える共有資源が使えない。
信頼性性があるかないか。専門用語では、程度問題（高い低い）ではなく、有 るか無いか。
信頼性がある通信プリミティブを利用した場合、あるプロセスが送信したメッ セージは、途中で失われることはなく、有限時間以内に通信相手のプロセスに 送り届けられる。
分散システムでは、メッセージは、失われることがある。
図? 同期型sendと非同期型send
ほとんどの通信プリミティブは、間接。
直接の例：
問題：直接アドレス指定では、receiveする前にsendされると、どのプロセス にメッセージを送っていいのかわからない。
解決
send,receive それぞれ２種類ある。
非同期の方が、並列性が高い。しかし、、、
2. は、転送完了割り込みで解決可能。プログラミングが難しい。 割り込みよりは、マルチスレッドがよい。
プログラミングの選択
時間切れ(timeout)。同期で使われる。
同期、非同期とは直行しているとも言えるが、普通は同期の場合にはバッファ リングを省略してコピーを減らす。
メールボックスには、しばしば有限のバッファがもうけられる。
バッファがいっぱいだった時にどうするか。 いっぱいの時にだけ送信側をブロックさせる、という方法でいいのか。
通信の分類
グループ通信は、いろいろな分散アルゴリズムでよく使われる。
普通の固定電話の場合、64k bps の帯域保証がなされている。電話を掛ける人 が増えてきたとしても、それが 32k bps に減らされるようなことはない。そ の代りに、電話を掛けようとすると「通話中」というエラーが返り、通信その ものが行えなくなる。
| TCP | IP | UDP | イーサネット | 電話 | 郵便 | |
| send | 非同期 | 非同期 | 非同期 | 非同期 | 非同期 | 非同期 |
| receive | 同期 | (非同期)* | 同期 | (非同期)* | 同期 | 非同期 |
| 信頼性 | あり | なし | なし | なし | あり | なし |
| アドレス指定 | 間接 | 間接 | 間接 | 間接 | 間接 | 直接 |
| 結合 | あり | なし | なし | なし | あり | なし |
| 方向 | 双方向 | 単方向 | 単方向 | 単方向 | 双方向 | 単方向 |
| マルチキャスト | 不可 | 可能 | 可能 | 可能 | 可能 | 不可 |
| 帯域保証 | なし | なし | なし | なし | あり | なし |
図? marshalingとunmarshaling
４個の要素からなる構造体を整列化して送信している。ネットワーク上を流れている時には、整列化された データの先頭にはネットワークのヘッダが付加されている。
SunRPC で使われているデータ形式。バイナリ文化。rpcgen というスタブ・コンパイラがある。 データ構造を与えると、marshaling の手続きを自動生成する。
SunRPC を使わなくて、XDR だけを使う方法もある。
Ｃ言語で扱える整数
2バイト、または、4バイトの整数をメモリに保存する方法 : メモリの下位番地に上位バイトを置くか下位バイトを置くか
図? バイト・オーダー
| 名前 | 方向 | ビット数 |
| htonl() | ホストからネットワークへ変換 | 32ビット |
| htons() | ホストからネットワークへ変換 | 16ビット |
| ntohl() | ネットワークからホストへ変換 | 32ビット |
| ntohs() | ネットワークからホストへ変換 | 16ビット |
long int hostlong, netlong; hostlong = 0x12345678 ; netlong = htonl( hostlong ); send(conn, &netlong, sizeof(netlong), 0);
思ったほど遅くはない。
注意：sscanf() は、整数をデコードするために使う分には問題ないが、 文字列を受け取るために使うとバッファ・オーバーフローが生じる可能性があるので、 使わない方がよい。
今後 TCP/IP 以外にも様々な通信プロトコルが開発され、Unix で利用できる ように設計されている。TCP/IP で使う時には、煩雑である。
| ドメイン | 型 | プロトコル |
| PF_INET | SOCK_STREAM | TCP(IPv4) |
| PF_INET | SOCK_DGRAM | UDP(IPv4) |
| PF_INET6 | SOCK_STREAM | TCP(IPv6) |
| PF_INET6 | SOCK_DGRAM | UDP(IPv6) |
| PF_UNIX | SOCK_STREAM | 同一ホスト内(UNIXドメイン)のストリーム |
| PF_UNIX | SOCK_DGRAM | 同一ホスト内(UNIXドメイン)のデータグラム |
| PF_NS | SOCK_STREAM | XNS のストリーム(SPP) |
| PF_NS | SOCK_SEQPACKET | XNS の順序付きパケット(IDP) |
| PF_NS | SOCK_RDM | XNSの信頼性のあるデータグラム(SPP) |
| 名前 | 説明 |
| socket() | 通信プロトコルに対応したソケット・オブジェクトを作成する |
| connect() | 結合(conection)を確立させる。サーバのアドレスを固定する。 |
| listen() | サーバ側で接続要求の待ち受けを開始する。 |
| accept() | サーバ側で接続されたソケットを得る。 |
| bind() | ソケットにアドレス(名前)を付ける。 |
| getpeername() | 通信相手のアドレス(名前)を得る。 |
| getsockname() | 自分のアドレス(名前)を得る。 |
| send(), sendto(), sendmsg() | メッセージを送信する。 |
| recv(), recvfrom(), recvmsg() | メッセージを受信する。 |
| shutdown() | 双方向の結合を部分的に切断する。 |
| getsockopt() | オプションの現在の値を取得する。 |
| setsockopt() | オプションを設定する。 |
| select(), poll() | 複数の入出力(通信を含む)を多重化する。 |
| write() | メッセージを送信する。 |
| read() | メッセージを受信する。 |
| close() | ファイル記述子を閉じる。他に参照しているファイル記述子がなければ、ソケット・オブジェクトを削除する。 |
| 名前 | 説明 |
| gethostbyname() | ホスト名から IP アドレスを調べる。 |
| getaddrinfo() | ホスト名から IP アドレスを調べる。IPv6対応。 |
| gethostbyaddr() | IPアドレスからホスト名を調べる。 |
| getnameinfo() | IPアドレスからホスト名を調べる。IPv6対応。 |
| freeaddrinfo() | getaddrinfo(), getnameinfo() で得られた構造体を解放する。 |
TCP/IP では、クラ イアント側とサーバ側でソケット・オブジェクトの作成するクラスが違ってい る。
| クラス名 | 説明 |
|---|---|
| Socket | TCP/IP のクライアント側のソケット |
| ServerSocket | TCP/IP のサーバ側のソケット |
| DatagramSocket | UDP/IP のソケット |
以後、ネットワークか ら文字列を入力するには、InputStreamReader や BufferedReader のオブジェ クトを生成して利用する。
出力側では、Socket クラスのオブジェクトに対して getOutputStream() して、 OutputStream クラスのオブジェクトを得て、 PrintStream オブジェクトを生成して利用できる。
通信を構造化。send()/receive() を直接使うのは、goto (jump) でプログラ ムを書くようなもの。call/if/while で書きたい。
プロセスを２種類に分類する。通信は、次のパタンを繰り返す。
図? 通信のパタンからみたクライアントとサーバの定義
構造化プログラミング：分かりにくいgoto文をつかわないで、わかりやすい goto文だけ使う。
図? サービスの授受によるクライアントとサーバの定義
図? 複数のクライアントによるサーバの共有
以上のように、クライアントとサーバは、いろいろな意味で使われる。これら の意味は、多くの場合、一致しているが、一致していないこともある。
通信を開始するパタンで、コンピュータ、プログラム、人間は、次の２つに分 類される。
図? 能動的なクライアントと受動的なサーバ
例：ＷＷＷサーバは、ＷＷＷクライアントから何か要求が来ない限り、ずっと 黙っている。
コンピュータを使う時には、人間が能動的になり、コンピュータが受動的にな る。
テレビを見ている時には、人間が受動的になり、テレビが能動的になる。
講義形式の授業では、サービスの授受では、教官がサーバで、学生がクライア ントになる。通信の開始の方法では、教官が能動的になり、学生が受動的にな る。
大学以上では、学生は、能動的になることが求められている。
混沌とした通信を 構造化 してわかりやすくしたものが、クライアント・サーバ・モデルである。
サーバあるシステムでは、サーバが落ちるとシステム全体が動作しなくなる。 このように複数の要素から構成されているシステムで、ある要素が故障した時 に、全体が動作しなくなるような場所を、単一障害個所(single point of failure) という。
コンピュータサイエンスでは、古くから、単一障害個所を避けるための研究が 行われてきている。もっとも成功している方法は、サーバを複数用意する方法 である。
サーバがないシステムでは、下手に作るとどの要素が故障してもシステム全体 が止まってしまうことになる。
サーバがないシステムで成功している例はある。
peer は、「対等の仲間」の意味。「通信相手」という意味もある。
検索は、サーバで索引を集めた方が速い。Web 上の検索エンジンなど。
サーバがない方法の利点(特徴)
クライアントが何かサーバにして欲しい時には、do_operation() で、サーバ に要求メッセージを送る。そして、サーバからの応答メッセージを待つ。
サーバは、要求メッセージを受けとると、何か仕事をして、send_reply() で、 クライアントに応答メッセージを返す。そして、再び次の要求メッセージ を待つ。
１つのサーバに複数のクライアントがアクセスすることがある。１つのクライ アントも、複数のサーバに同時にアクセスすることもできる。
図? クライアント・サーバ・モデルに基づく通信で使う３つの命令
例２：３種類（回数）
（＜−＞文化的には、TCP/IP上のテキストベースのプロトコルとは対照。）
RPCでは、別のアドレス空間の間でデータがやり取りされるので、基本的に 「ポインタ」を受け渡しすることはできない。しかし、SunRPC では、ポイン タの先を再帰的に「コピー」する機能がある。
このRPCの３つの命令は、システムコール、または、ライブラリで実現される。 SunRPCには、get_request() に相当する命令が定義されていない。
スタブ(stub) は、プロセス間通信を普通の手続き呼出しと全く同じ形式で行なうことができ るようにするためのプログラム。 もともとは木の切株の意味。
スタブの分類
図? rpcgenによるRPCプログラム開発で利用するファイル
name.x
name_client.c
name_server.c
% rpcgen name.x次の４つのファイルが生成される。![[←]](../icons/screen-return.gif)
name.h
name_clnt.c
name_xdr.c
name_svc.c
ハッシュ表
typedef string key_t<256>;
struct keyvalue_t {
key_t key;
int value ;
};
typedef key_t keyarray_t<>;
program HASHTABLE_PROG {
version HASHTABLE_VERSION {
int PUT(keyvalue_t) = 11 ;
int GETVALUE(key_t) = 12 ;
keyarray_t GETKEYS(void) = 13 ;
} = 1 ;
} = 0x20051001 ;
遠隔手続き呼出しでは、送受信できるデータは基本的には値だけであり、
ポインタを送ることはできない。
SunRPC では、ポインタの先の１要素だけコピーして送る機能がある。SunRPC では、ポインタによる単純なリストや木構造を送ることができる。
双方向リストなど、内部にループを含むものは SunRPC では送ることができな い。また、ポインタで実現された有向非循環グラフを送ると木構造に展開され てしまう。
ローカルの手続き呼出しでは、リンク時に固定される。
クライアントとサーバは１対１ではない。
binding のための命令
/etc/rpc
というファイルに含まれている。
TCP/IPまたはUDP/IPでデータを送るにはポート番号が必要になる。 サーバが動作しているホストには、 portmapper とよばれる特殊な RPC のサーバが動作している。 サーバは起動時に自分の＜プログラム番号, バージョン, プロトコル, ポート番号＞をPortmapper に登録する (pmap_set())。
クライアントは、実際にサーバに接続する前に、Portmapper に＜プ ログラム番号, バージョン, プロトコル＞を送り、 TCP/IPまたはUDP/IPのポート番号を得る(pmap_getport())。最終的には, この ポート番号を使ってメッセージを送る。
Portmapper 自身のポート番号は、111 に固定されている。
図? SunRPC での binding (portmapper)
例: 銀行預金転送。
対策:
ＲＰＣのセマンティクス
親（クライアント）がいない計算を孤児という。
対応方法
孤児が、ロックを持っていたら、孤児を消しただけでは話を終わらない。
例：
無状態サーバ(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 システムコール |
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 では、 TCP/IP というコネクションが作られる通信サービスが使われいるが、 １ページ１ページを転送する度にコネクションを切っているので、 複数ページ のアクセスの時にはコネクションが作られない通信サービスを使っているのと 論理的に同じ。
途中経過を保存したい時：
4. EXAMPLES
4.1 Example 1
Most detail of request and response headers has been omitted. Assume
the user agent has no stored cookies.
1. User Agent -> Server
POST /acme/login HTTP/1.1
[form data]
User identifies self via a form.
2. Server -> User Agent
HTTP/1.1 200 OK
Set-Cookie2: Customer="WILE_E_COYOTE"; Version="1"; Path="/acme"
Cookie reflects user's identity.
3. User Agent -> Server
POST /acme/pickitem HTTP/1.1
Cookie: $Version="1"; Customer="WILE_E_COYOTE"; $Path="/acme"
[form data]
User selects an item for "shopping basket".
4. Server -> User Agent
HTTP/1.1 200 OK
Set-Cookie2: Part_Number="Rocket_Launcher_0001"; Version="1";
Path="/acme"
Shopping basket contains an item.
5. User Agent -> Server
POST /acme/shipping HTTP/1.1
Cookie: $Version="1";
Customer="WILE_E_COYOTE"; $Path="/acme";
Part_Number="Rocket_Launcher_0001"; $Path="/acme"
[form data]
User selects shipping method from form.
6. Server -> User Agent
HTTP/1.1 200 OK
Set-Cookie2: Shipping="FedEx"; Version="1"; Path="/acme"
New cookie reflects shipping method.
7. User Agent -> Server
POST /acme/process HTTP/1.1
Cookie: $Version="1";
Customer="WILE_E_COYOTE"; $Path="/acme";
Part_Number="Rocket_Launcher_0001"; $Path="/acme";
Shipping="FedEx"; $Path="/acme"
[form data]
User chooses to process order.
8. Server -> User Agent
HTTP/1.1 200 OK
Transaction is complete.
The user agent makes a series of requests on the origin server, after
each of which it receives a new cookie. All the cookies have the
same Path attribute and (default) domain. Because the request-URIs
all path-match /acme, the Path attribute of each cookie, each request
contains all the cookies received so far.
普通のＷＷＷサーバでは、要求を送ってきたコンピュータのＩＰアドレスを記 録しているので、コンピュータ単位でのアクセス状況を記録することはできる が、個人を特定することはできない。
クッキーを利用することにより、コンピュータではなくどの個人がアクセスし てきたかを記録することができる。
クッキーから電子メールのアドレスや氏名まで調べることはできない。 しかし、インターネットをサーフしている間にどこかでそれを打ち込んだが最 後、クッキーと電子メール・アドレスや氏名との対応が記録されてしまう危険 性がある。
参考
RFC2965 HTTP State Management Mechanism
Netscape社によるＷＷＷにおけるクッキー実現の案
http://wp.netscape.com/newsref/std/cookie_spec.html
HTTP でも、クライアントの状態をサーバ側で保存するためにクッキーが使わ れることがある。
グループ通信で何が難しいか
対等だと、クラッシュに強い（single point of failure がない）が、何をす るにもすぐ投票が必要になる。
グループサーバを持つか持たないか。
難しいのは、メンバのプロセスがクラッシュした時。 何も言わずにグループから抜ける。
total ordering は、グループ通信では実現が難しすぎる。弱いものが実現さ れる。
プロセスが複数のグループに属していると、１つのメッセージについての順序 だけ考えていてはすまなくなる。
下手をすると、メッセージが増幅しながいつまでもぐるぐる回る。
最初の実現：２相コミットによる ABCAST 。重すぎる。
メンバの数：ｎ
各プロセスは、グループごとに、長さｎのベクトルＶを持つ。 ｉ番目の要素は、プロセスｉから正しい順序で受信したメッセージの最後の番号。 ０に初期化される。
図? ISISでのCBCASTの実現。