Mercurial > hg > Papers > 2012 > kazz-master

annotate paper/chapter1.tex @ 8:0b01b77d33b4

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
write about Federated Linda
author kazz <kazz@cr.ie.u-ryukyu.ac.jp>
date Mon, 06 Feb 2012 03:19:53 +0900
parents 70f19a2daea6
children 7a2a26770f62
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
1
d50fdef3ebd5 add title
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
1 \chapter{Federated Linda の実装により得られた知見}
d50fdef3ebd5 add title
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
2
d50fdef3ebd5 add title
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
3 \section{Federated Linda}
d50fdef3ebd5 add title
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
4 本研究室では、自然に分散プログラミングが書けるようなプログラミングモデルとして、グローバルな ID を持たない連邦型タプルスペース(以下 Federated Linda と記す)を提案してきた。
d50fdef3ebd5 add title
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
5
d50fdef3ebd5 add title
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
6 \subsection{Linda}
5
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
7 Linda は、タプルという ID で番号づけられたデータの集合を、以下の API (表\ref{tb:lindaApi}) を用いて共有されたタプルスペースに出し入れすることにより、外部との通信を行うプログラミングモデルである。(図\ref{fig:lindaServer})
0
70623c622232 first commit
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
8
5
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
9 \begin{table}[htbp]
1
d50fdef3ebd5 add title
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
10 \caption{Linda API}
d50fdef3ebd5 add title
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
11 \label{tb:lindaApi}
d50fdef3ebd5 add title
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
12 \begin{center}
d50fdef3ebd5 add title
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
13 \begin{tabular} {|l|l|}
d50fdef3ebd5 add title
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
14 \hline
d50fdef3ebd5 add title
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
15 {\bf API}&{\bf 概要}\\
d50fdef3ebd5 add title
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
16 \hline
d50fdef3ebd5 add title
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
17 in(id)&タプルスペースからタプルを取り出す。\\&タプルスペースにタプルは残らない。\\
d50fdef3ebd5 add title
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
18 \hline
d50fdef3ebd5 add title
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
19 read(id)&タプルスペースからタプルを取り出す。\\&タプルスペースにタプルが残る。\\
d50fdef3ebd5 add title
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
20 \hline
d50fdef3ebd5 add title
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
21 out(id,data)&タプルスペースへタプルを書きこむ。\\
d50fdef3ebd5 add title
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
22 \hline
d50fdef3ebd5 add title
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
23 \end{tabular}
d50fdef3ebd5 add title
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
24 \end{center}
d50fdef3ebd5 add title
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
25 \end{table}
d50fdef3ebd5 add title
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
26
5
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
27 \begin{figure}[htbp]
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
28 \begin{center}
7
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
29 \includegraphics[width=50mm]{images/linda_server.pdf}
5
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
30 \end{center}
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
31 \caption{Linda Server とそれを API を用いて操作するクライアント}
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
32 \label{fig:lindaServer}
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
33 \end{figure}
2
bc5a55ce5e8d add linda server graffle
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
34
1
d50fdef3ebd5 add title
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
35 \subsection{Federated Linda}
d50fdef3ebd5 add title
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
36
7
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
37 Federated Linda は、複数のタプルスペース (Linda Server) を相互に接続することにより分散プログラミングを実現する。一つのタプルスペースには少数の接続があることが期待されており、多数のタプルスペースが接続することにより分散アプリケーションを実現する(図\ref{fig:connectionOfTspace})。 smtp/nntp デーモンが行単位でプロトコルを作るのと似た形で、タプルスペースへの in/out でプロトコルを作ることになる。
5
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
38
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
39 通信モデルは、タプルの出し入れによるリレー転送のようになる。インターネットのパケット転送のように、タプルスペースからタプルスペースへとタプルを転送していく。
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
40
7
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
41 クライアントのアクセス数が増えても、タプルスペース等の数を増やし、ネットワーク処理を分散することにより、スケーラビリティを保つ。
5
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
42
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
43 \begin{figure}[htbp]
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
44 \begin{center}
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
45 \includegraphics[width=100mm]{images/connection_of_tspace.pdf}
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
46 \end{center}
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
47 \caption{タプルスペースの相互接続}
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
48 \label{fig:connectionOfTspace}
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
49 \end{figure}
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
50
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
51 \section{Federated Linda の分散プログラミング}
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
52 Federated Linda の分散プログラムには "Tuple Space", "Protocol Engine", "Link Configuration" の3つの要素がある。
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
53 Federated Linda は、この3つの要素に基づいてプログラミングモデルを提供する。
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
54
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
55 \subsection{Tuple Space}
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
56 プロトコルへのアクセスは Linda の API を用いる。
7
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
57 つまり、タプルスペースへの "in", "read", "out" 等である。
5
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
58 これらのコマンドは単純で、理解しやすいものである。
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
59 タプルの出し入れというモデルで通信を行うことができる。
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
60
7
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
61 また、 Protocol Engine との通信は非同期に行われる。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
62
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
63 \subsection{Protocol Engine}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
64 プロトコルを規定する Protocol Engine は、分散アルゴリズムを内包し、他のプロトコルへのアクセスもタプルスペース経由で行う。通信はタプルをタプルスペースからタプルスペースへと伝搬させるように転送する。クライアントはタプルスペースを介した通信を行うので、クライアントからはプロトコルの細かい挙動は見えない。しかし、クライアントプログラムのプロトコルへの依存を低く抑えることが可能である。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
65
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
66 タプルスペースとのタプルのやり取りは非同期で行われるuが、これらのライブラリはシングルスレッドで実装されている。
5
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
67 そのため、"in", "read" を実行した際にリクエストは送信されず、また返ってくるであろうタプルのレスポンスは返ってこない。
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
68 "sync" を行った時にキューに入っているリクエストを Linda Server へ送信する。
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
69 この時、サーバー側からクライアントへのレスポンスが準備できていればそれらを受け取る。
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
70
7
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
71 サーバー側からレスポンスデータを受信した際、ユーザーはそれらを確認する以下の2つの方法がある。
5
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
72 \subsubsection{poll 方式}
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
73 poll 方式とは、 "sync" を行った後に、その "in", "out" のレスポンスが ready 状態になっているか確認する方法である。
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
74 この方式を用いた場合、レスポンスが ready 状態かどうかをユーザーが好きなタイミングで記述するため、行いたい処理を順次書くだけでよくなるため、ソースコードの可読性が上がる。
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
75
7
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
76 しかし、レスポンスが返って来ない間、ループを行い、状態チェックを行う等の処理を書かなくてはいけなくなるため、処理効率は悪化する。(図\ref{fig:pollBased})
6
4b95f939ca56 add poll based fig
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
77
4b95f939ca56 add poll based fig
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
78 \begin{figure}[htbp]
4b95f939ca56 add poll based fig
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
79 \begin{center}
7
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
80 \includegraphics[width=70mm]{images/poll_based.pdf}
6
4b95f939ca56 add poll based fig
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
81 \end{center}
4b95f939ca56 add poll based fig
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
82 \caption{poll 方式の例}
4b95f939ca56 add poll based fig
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
83 \label{fig:pollBased}
4b95f939ca56 add poll based fig
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 5
diff changeset
84 \end{figure}
5
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
85
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
86 \subsubsection{callback function 方式}
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
87 callback function 方式とは、 "in", "out" を行う際に、そのレスポンスがサーバー側から返ってきた時の処理を予め記述しておく方法である。
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
88
7
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
89 レスポンスがサーバー側から返って来た時に指定したコールバック関数が自動で実行されるため、ユーザーは受信したかどうかチェックする処理を書かなくてもよい。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
90 また、それらの処理がまるごと消えるため、処理効率は向上する。(図\ref{fig:callbackFunctionBased})
5
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
91
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
92 しかし、実行されるタイミングをユーザーが把握することが難しくなる。
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
93 そのため、ソースコードの難読化につながる。
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
94 コールバック関数間のデータの共有も難しくなる。
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
95
7
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
96 \begin{figure}[htbp]
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
97 \begin{center}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
98 \includegraphics[width=70mm]{images/callback_function_based.pdf}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
99 \end{center}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
100 \caption{callback function 方式の例}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
101 \label{fig:callbackFunctionBased}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
102 \end{figure}
5
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
103
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
104 \subsection{Link Configuration}
7
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
105 タプルスペースや Protocol Engine の接続を規定する。接続の状態を XML として表し、各ノードがそれにしたがってIPの上位レイヤーでオーバーレイネットワークを構築する。オーバーレイネットワークを構築するために、接続等を扱うモジュールを提供する。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
106
5
0d56d00f89fc description of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
107
2
bc5a55ce5e8d add linda server graffle
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
108 \section{Federated Linda の改良}
7
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
109 Federated Linda はいくつかの段階を経て実装されてきた。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
110 それは、プロトタイプをプログラミングすることによって、設計を詳細なものへと落としこんでいく必要があったからである。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
111
2
bc5a55ce5e8d add linda server graffle
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
112 \subsection{Meta Protocol Engine}
7
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
113 従来の Protocol Engine は、タプルスペース (Linda Server) とは独立したプロセスであった。(図\ref{fig:flindaType2})
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
114 それでは、その2つのプロセスがローカルの同じマシン上にあっても、タプルをやり取りするためにソケット通信を行う必要があった。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
115
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
116 \begin{figure}[htbp]
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
117 \begin{center}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
118 \includegraphics[width=110mm]{./images/flinda_type2.pdf}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
119 \end{center}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
120 \caption{タプルスペースと Protocol Engine が別プロセス}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
121 \label{fig:flindaType2}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
122 \end{figure}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
123
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
124 そこで、 Linda Server と一体型の Protocol Engine として、 Meta Protocol Engine を提案し、実装した。(図\ref{fig:flindaType3})
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
125 Protocol Engine のプロセスがタプルスペースと同じであるため、ローカルのタプルスペースへアクセスする際にメモリ空間に直接アクセスすることができるようになった。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
126
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
127 \begin{figure}[htbp]
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
128 \begin{center}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
129 \includegraphics[width=110mm]{./images/flinda_type3.pdf}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
130 \end{center}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
131 \caption{タプルスペースと Protocol Engine が同じプロセス}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
132 \label{fig:flindaType3}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
133 \end{figure}
2
bc5a55ce5e8d add linda server graffle
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
134
bc5a55ce5e8d add linda server graffle
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
135 \subsection{update API の追加}
8
0b01b77d33b4 write about Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
136 Federated Linda の例題を書いているときに、 "in" の直後に "out" を実行することが多いことに気がついた。これは即ち、タプルを消して、新しいタプルを書き込むということである。そこで、新しく "update" API を追加することにした。(表\ref{tb:additionalLindaApi})
7
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
137
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
138 \begin{table}[htbp]
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
139 \caption{追加 Linda API}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
140 \label{tb:additionalLindaApi}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
141 \begin{center}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
142 \begin{tabular} {|l|l|}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
143 \hline
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
144 {\bf API}&{\bf 概要}\\
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
145 \hline
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
146 update(id,data)&タプルスペースからタプルを取り除く。\\&タプルスペースへデータを書き込む。\\
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
147 \hline
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
148 \end{tabular}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
149 \end{center}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
150 \end{table}
1
d50fdef3ebd5 add title
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
151
d50fdef3ebd5 add title
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
152
7
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
153 \section{Federated Linda の問題点}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
154 Federated Linda の設計と実装、それらを使った例題の作成を通して、 Federated Linda の抱える問題点が浮き彫りとなった。これらの問題点を整理し、次章に記す新しい分散アプリケーションフレームワークの設計に活かすことができた。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
155 その問題点を以下に記す。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
156
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
157 \subsection{シングルスレッドを用いた設計}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
158 Federated Linda の設計上の問題点としてシングルスレッドで設計されていることが挙げられる。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
159 シングルスレッドで設計された理由として、 Federated Linda の実装を行った当時は、シングルコア CPU が主流であったことが挙げられる。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
160 さらに、Java 2 SE, v1.4 がリリースされ、 java.nio がノンブロッキング I/O をサポートたことも理由として挙げられる。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
161 java.nio.channels.Selector を使用し、シングルスレッドで複数の入出力を取り扱うという方法が当時のサーバーの主流であった。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
162
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
163 この方法では、大きな容量のデータを送受信した際に、 CPU がそのデータの送受信にかかりっきりになってしまい、その処理が終わるまで他の小さな処理が全て待ち状態になってしまうといった問題が発生していた。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
164
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
165 しかし、近年では、シングルコア CPU の性能向上が発熱量等の問題により頭打ちとなり、マルチコアのマシンが主流となっている。将来的にはメニーコアのマシンが主流になっていくと考えられる。そのような背景を踏まえて、 Apache の Cassandra プロジェクトではデーモンの実装に SEDA アーキテクチャを採用している。これは、マルチスレッドを用いて大量の接続を管理し、受け取ったデータを、処理ごとに分けられたステージと呼ばれるスレッドに投げ、処理が終わると次のステージにデータを伝搬させる。これを用いることによってマルチコア性能を生かし、パイプライン的に効率よく処理することが可能となっている。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
166
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
167 分散アプリケーションを作成する上で、マルチスレッドをどのように活用するかといったことが、重要な課題となっている。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
168
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
169 \subsection{タプルの表現方法}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
170 次の問題点として、タプルの表現方法が挙げられる。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
171 Federated Linda におけるタプルはバイトの配列として表現されている。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
172 例えば、 Java を用いた実装では、 ByteBuffer を利用している。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
173 バイトの配列を用いることによる問題点としては、データを送受信する際に、ユーザーが Protocol Engine で利用しているデータをバイトの配列へ変換、またはその逆を行う必要があるということが挙げられる。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
174
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
175 また、異なるアーキテクチャ間におけるデータフォーマットの取り扱いも問題となる。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
176 異なるアーキテクチャとは、CPU の違い(バイトオーダー、ビット数等)、使用するプログラミング言語の違い、 OS の違い等である。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
177 例えば、 PlayStation 3 (Cell) 上の Linux で動作するアプリケーションと、 Mac OS X (Intel) 上で動作するアプリケーション間である。そのアプリケーション間で、とある共通の構造体のデータをやり取りするといった事案でデータフォーマットに関する問題が発生する。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
178 通信するたびに、 XDR (External Data Representation) などのデータフォーマットを用いて、ユーザーがデータを変換する必要がある。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
179
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
180 \subsection{タプルの ID が整数値であること}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
181 更なる問題点として、タプルの ID が整数値であることが挙げられる。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
182 これは、整数値であるため、送受信する際や、タプルスペースのデータを探すときには効率がよいというメリットがある。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
183 一方で、ユーザーが整数 ID を管理するためには、 enum やハッシュ、即ち文字列から整数値への射影を管理する必要が出てくるのである。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
184 新しいタプルをタプルスペースで使用する際に新しい整数 ID と文字列の対応をユーザーが管理する手間がかかる。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
185 この問題はデバッグ時に顕著となる。それら無数の整数値をユーザーがログを見ながらどのデータか把握しなければならないからである。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
186
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
187 Cassandra 等の KVS (Key-Value Store) では、キーに直接文字列を使用しているため、キーの管理が行いやすくなっている。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
188
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
189 \subsection{Protocol Engine の記述方法}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
190 次に Protocol Engine の記述方法である。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
191
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
192 Protocol Engine は処理効率の観点から基本的に callback function 方式 (図\ref{fig:callbackFunctionBased}) を用いて行うが、これらの取り扱いが問題となる。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
193
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
194 "in" や "read" を行う時にコールバック関数を準備し、タプルに設定する。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
195 更に、そのコールバック関数内で、新しいコールバック関数を準備し、 "in" や "read" を行ってタプルに設定する。このように、コールバック関数が "in" や "read" を介してツリー状に接続されているという構図が生まれる。(図\ref{fig:callbackTree}) このように、ユーザーはタプルの ID を元にコールバック関数の繋がりを把握する必要がある。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
196 分散アプリケーションであるため、ローカルマシンのタプル ID だけでなく、リモートマシン上のコールバック関数の影響も受ける。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
197 そのため、スタック上に関数を呼び出して読んでいくことが難しい。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
198
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
199 これらのタプルの接続をユーザーが "in" や "read" を直接用いて表現するのではなく、フレームワーク側で接続関係をサポートする必要がある。
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
200
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
201 \begin{figure}[htbp]
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
202 \begin{center}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
203 \includegraphics[width=70mm]{./images/callback_tree.pdf}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
204 \end{center}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
205 \caption{コールバック関数同士がタプルを介してツリー状に接続されている}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
206 \label{fig:callbackTree}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
207 \end{figure}
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
208
70f19a2daea6 add the problem of Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 6
diff changeset
209 \subsection{接続しているタプルスペースリソースの管理}
8
0b01b77d33b4 write about Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
210 Federated Linda にはタプルスペースへのコネクションを管理する機構がないため、ユーザーがそれらのコネクションを管理する必要があった。
0b01b77d33b4 write about Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
211 分散アプリケーションにおいて、どのようなグラフ構造でマシンが接続されているかという情報は重要である。
0b01b77d33b4 write about Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
212 接続時に、コネクションに把握しやすい名前をつけることで、ユーザーは接続を管理しやすくなる。
0b01b77d33b4 write about Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
213 例えば、リングトポロジーの場合、1つのマシンに着目してみると、右への接続を"right"、左への接続を"left"といったキーで呼び出すことができると嬉しい。
2
bc5a55ce5e8d add linda server graffle
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
214
8
0b01b77d33b4 write about Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
215 また、受け取ったデータがどこから来たか、受け取るときに把握できると望ましい。
0b01b77d33b4 write about Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
216 なぜならば、ルーティングを行うときに役立つからである。ツリートポロジーの場合、親から来たデータを子に伝搬するといった処理を記述することがよくある。その時に、どこからデータが来たかという情報は重要である。
2
bc5a55ce5e8d add linda server graffle
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
217
8
0b01b77d33b4 write about Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
218 これらの問題点を踏まえて設計した、新しい分散アプリケーションフレームワークの設計を次章では示す。
0b01b77d33b4 write about Federated Linda
kazz <kazz@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
219