\chapter{Federated Linda の実装により得られた知見}

\section{Federated Linda}
本研究室では、自然に分散プログラミングが書けるようなプログラミングモデルとして、グローバルな ID を持たない連邦型タプルスペース(以下 Federated Linda \cite{linda, globalid, dinamicrouting, dinamicrouting2, dinamicrouting_compact, akamine:2009a, akamine:2010a, akamine:2011a} と記す)を提案してきた。

\subsection{Linda}
Linda は、タプルという ID で番号づけられたデータの集合を、以下の API (表\ref{tb:lindaApi}) を用いて共有されたタプルスペースに出し入れすることにより、外部との通信を行うプログラミングモデルである。(図\ref{fig:lindaServer})

\begin{table}[htbp]
\caption{Linda API}
\label{tb:lindaApi}
\begin{center}
\begin{tabular} {|l|l|}
  \hline
  {\bf API}&{\bf 概要}\\
  \hline
  in(id)&タプルスペースからタプルを取り出す。\\&タプルスペースにタプルは残らない。\\
  \hline
  read(id)&タプルスペースからタプルを取り出す。\\&タプルスペースにタプルが残る。\\
  \hline
  out(id,data)&タプルスペースへタプルを書きこむ。\\
  \hline
\end{tabular}
\end{center}
\end{table}

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=50mm]{images/linda_server.pdf}
  \end{center}
  \caption{Linda Server とそれを API を用いて操作するクライアント}
  \label{fig:lindaServer}
\end{figure}

\subsection{Federated Linda}

Federated Linda は、複数のタプルスペース (Linda Server) を相互に接続することにより分散プログラミングを実現する。一つのタプルスペースには少数の接続があることが期待されており、多数のタプルスペースが接続することにより分散アプリケーションを実現する(図\ref{fig:connectionOfTspace})。 smtp/nntp デーモンが行単位でプロトコルを作るのと似た形で、タプルスペースへの in/out でプロトコルを作ることになる。

通信モデルは、タプルの出し入れによるリレー転送のようになる。インターネットのパケット転送のように、タプルスペースからタプルスペースへとタプルを転送していく。

クライアントのアクセス数が増えても、タプルスペース等の数を増やし、ネットワーク処理を分散することにより、スケーラビリティを保つ。

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=100mm]{images/connection_of_tspace.pdf}
  \end{center}
  \caption{タプルスペースの相互接続}
  \label{fig:connectionOfTspace}
\end{figure}

\section{Federated Linda の分散プログラミング}
Federated Linda の分散プログラムには "Tuple Space", "Protocol Engine", "Link Configuration" の3つの要素がある。
Federated Linda は、この3つの要素に基づいてプログラミングモデルを提供する。

\subsection{Tuple Space}
プロトコルへのアクセスは Linda の API を用いる。
つまり、タプルスペースへの "in", "read", "out" 等である。
これらのコマンドは単純で、理解しやすいものである。
タプルの出し入れというモデルで通信を行うことができる。

また、 Protocol Engine との通信は非同期に行われる。

\subsection{Protocol Engine}
プロトコルを規定する Protocol Engine は、分散アルゴリズムを内包し、他のプロトコルへのアクセスもタプルスペース経由で行う。通信はタプルをタプルスペースからタプルスペースへと伝搬させるように転送する。クライアントはタプルスペースを介した通信を行うので、クライアントからはプロトコルの細かい挙動は見えない。しかし、クライアントプログラムのプロトコルへの依存を低く抑えることが可能である。

タプルスペースとのタプルのやり取りは非同期で行われるが、これらのライブラリはシングルスレッドで実装されている。
そのため、"in", "read" を実行した際にリクエストは送信されず、また返ってくるであろうタプルのレスポンスは返ってこない。
"sync" を行った時にキューに入っているリクエストを Linda Server へ送信する。
この時、サーバー側からクライアントへのレスポンスが準備できていればそれらを受け取る。

サーバー側からレスポンスデータを受信した際、ユーザーはそれらを確認する以下の2つの方法がある。
\subsubsection{poll 方式}
poll 方式とは、 "sync" を行った後に、その "in", "read" のレスポンスが ready 状態になっているか確認する方法である。
この方式を用いた場合、レスポンスが ready 状態かどうかをユーザーが好きなタイミングで記述するため、行いたい処理を順次書くだけでよくなるため、ソースコードの可読性が上がる。

しかし、レスポンスが返って来ない間、ループを行い、状態チェックを行う等の処理を書かなくてはいけなくなるため、処理効率は悪化する。(図\ref{fig:pollBased})

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=70mm]{images/poll_based.pdf}
  \end{center}
  \caption{poll 方式の例}
  \label{fig:pollBased}
\end{figure}

\subsubsection{callback function 方式}
callback function 方式とは、 "in", "read" を行う際に、そのレスポンスがサーバー側から返ってきた時の処理を予め記述しておく方法である。

レスポンスがサーバー側から返って来た時に指定したコールバック関数が自動で実行されるため、ユーザーは受信したかどうかチェックする処理を書かなくてもよい。
また、それらの処理がまるごと消えるため、処理効率は向上する。(図\ref{fig:callbackFunctionBased})

しかし、実行されるタイミングをユーザーが把握することが難しくなる。
そのため、ソースコードの難読化につながる。
コールバック関数間のデータの共有も難しくなる。

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=70mm]{images/callback_function_based.pdf}
  \end{center}
  \caption{callback function 方式の例}
  \label{fig:callbackFunctionBased}
\end{figure}

\subsection{Link Configuration}
タプルスペースや Protocol Engine の接続を規定する。接続の状態を XML として表し、各ノードがそれにしたがってIPの上位レイヤーでオーバーレイネットワークを構築する。オーバーレイネットワークを構築するために、接続等を扱うモジュールを提供する。


\section{Federated Linda の改良}
Federated Linda はいくつかの段階を経て実装されてきた。
それは、プロトタイプをプログラミングすることによって、設計を詳細なものへと落としこんでいく必要があったからである。

\subsection{Meta Protocol Engine}
従来の Protocol Engine は、タプルスペース (Linda Server) とは独立したプロセスであった。(図\ref{fig:flindaType2})
それでは、その2つのプロセスがローカルの同じマシン上にあっても、タプルをやり取りするためにソケット通信を行う必要があった。

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=110mm]{./images/flinda_type2.pdf}
  \end{center}
  \caption{タプルスペースと Protocol Engine が別プロセス}
  \label{fig:flindaType2}
\end{figure}

そこで、 Linda Server と一体型の Protocol Engine として、 Meta Protocol Engine を提案し、実装した。(図\ref{fig:flindaType3})
Protocol Engine のプロセスがタプルスペースと同じであるため、ローカルのタプルスペースへアクセスする際にメモリ空間に直接アクセスすることができるようになった。

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=110mm]{./images/flinda_type3.pdf}
  \end{center}
  \caption{タプルスペースと Protocol Engine が同じプロセス}
  \label{fig:flindaType3}
\end{figure}

\subsection{update API の追加}
Federated Linda の例題を書いているときに、 "in" の直後に "out" を実行することが多いことに気がついた。これは即ち、タプルを消して、新しいタプルを書き込むということである。そこで、新しく "update" API を追加することにした。(表\ref{tb:additionalLindaApi})

\begin{table}[htbp]
\caption{追加 Linda API}
\label{tb:additionalLindaApi}
\begin{center}
\begin{tabular} {|l|l|}
  \hline
  {\bf API}&{\bf 概要}\\
  \hline
  update(id,data)&タプルスペースからタプルを取り除く。\\&タプルスペースへデータを書き込む。\\
  \hline
\end{tabular}
\end{center}
\end{table}


\section{Federated Linda の問題点}
Federated Linda の設計と実装、それらを使った例題の作成を通して、 Federated Linda の抱える問題点が浮き彫りとなった。これらの問題点を整理し、次章に記す新しい分散アプリケーションフレームワークの設計に活かすことができた。
その問題点を以下に記す。

\subsection{シングルスレッドを用いた設計}
Federated Linda の設計上の問題点としてシングルスレッドで設計されていることが挙げられる。
シングルスレッドで設計された理由として、 Federated Linda の実装を行った当時は、シングルコア CPU が主流であったことが挙げられる。
さらに、Java 2 SE, v1.4 がリリースされ、 java.nio がノンブロッキング I/O をサポートたことも理由として挙げられる。
java.nio.channels.Selector を使用し、シングルスレッドで複数の入出力を取り扱うという方法が当時のサーバーの主流であった。

この方法では、大きな容量のデータを送受信した際に、 CPU がそのデータの送受信にかかりっきりになってしまい、その処理が終わるまで他の小さな処理が全て待ち状態になってしまうといった問題が発生していた。

しかし、近年では、シングルコア CPU の性能向上が発熱量等の問題により頭打ちとなり、マルチコアのマシンが主流となっている。将来的にはメニーコアのマシンが主流になっていくと考えられる。そのような背景を踏まえて、 Apache の Cassandra プロジェクト\cite{cassandra}ではデーモンの実装に SEDA アーキテクチャ \cite{seda} を採用している。これは、マルチスレッドを用いて大量の接続を管理し、受け取ったデータを、処理ごとに分けられたステージと呼ばれるスレッドに投げ、処理が終わると次のステージにデータを伝搬させる。これを用いることによってマルチコア性能を生かし、パイプライン的に効率よく処理することが可能となっている。

分散アプリケーションを作成する上で、マルチスレッドをどのように活用するかといったことが、重要な課題となっている。

\subsection{タプルの表現方法}
次の問題点として、タプルの表現方法が挙げられる。
Federated Linda におけるタプルはバイトの配列として表現されている。
例えば、 Java を用いた実装では、 ByteBuffer を利用している。
バイトの配列を用いることによる問題点としては、データを送受信する際に、ユーザーが Protocol Engine で利用しているデータをバイトの配列へ変換、またはその逆を行う必要があるということが挙げられる。

また、異なるアーキテクチャ間におけるデータフォーマットの取り扱いも問題となる。
異なるアーキテクチャとは、CPU の違い(バイトオーダー、ビット数等)、使用するプログラミング言語の違い、 OS の違い等である。
例えば、 PlayStation 3 (Cell) 上の Linux で動作するアプリケーションと、 Mac OS X (Intel) 上で動作するアプリケーション間である。そのアプリケーション間で、とある共通の構造体のデータをやり取りするといった事案でデータフォーマットに関する問題が発生する。
通信するたびに、 XDR (External Data Representation) などのデータフォーマットを用いて、ユーザーがデータを変換する必要がある。

\subsection{タプルの ID}
更なる問題点として、タプルの ID が整数値であることが挙げられる。
これは、整数値であるため、送受信する際や、タプルスペースのデータを探すときには効率がよいというメリットがある。
一方で、ユーザーが整数 ID を管理するためには、 enum やハッシュ、即ち文字列から整数値への射影を管理する必要が出てくるのである。
新しいタプルをタプルスペースで使用する際に新しい整数 ID と文字列の対応をユーザーが管理する手間がかかる。
この問題はデバッグ時に顕著となる。それら無数の整数値をユーザーがログを見ながらどのデータか把握しなければならないからである。

Cassandra 等の KVS (Key-Value Store) では、キーに直接文字列を使用しているため、キーの管理が行いやすくなっている。

\subsection{Protocol Engine の記述方法}
次に Protocol Engine の記述方法である。

Protocol Engine は処理効率の観点から基本的に callback function 方式 (図\ref{fig:callbackFunctionBased}) を用いて行うが、これらの取り扱いが問題となる。

"in" や "read" を行う時にコールバック関数を準備し、タプルに設定する。
更に、そのコールバック関数内で、新しいコールバック関数を準備し、 "in" や "read" を行ってタプルに設定する。このように、コールバック関数が "in" や "read" を介してツリー状に接続されているという構図が生まれる。(図\ref{fig:callbackTree}) このように、ユーザーはタプルの ID を元にコールバック関数の繋がりを把握する必要がある。
分散アプリケーションであるため、ローカルマシンのタプル ID だけでなく、リモートマシン上のコールバック関数の影響も受ける。
そのため、スタック上に関数を呼び出して読んでいくことが難しい。

これらのタプルの接続をユーザーが "in" や "read" を直接用いて表現するのではなく、フレームワーク側で接続関係をサポートする必要がある。

\begin{figure}[htbp]
  \begin{center}
    \includegraphics[width=70mm]{./images/callback_tree.pdf}
  \end{center}
  \caption{コールバック関数間のタプルを介した接続(ツリー状)}
  \label{fig:callbackTree}
\end{figure}

\subsection{接続しているタプルスペースリソースの管理}
Federated Linda にはタプルスペースへのコネクションを管理する機構がないため、ユーザーがそれらのコネクションを管理する必要があった。
分散アプリケーションにおいて、どのようなグラフ構造でマシンが接続されているかという情報は重要である。
接続時に、コネクションに把握しやすい名前をつけることで、ユーザーは接続を管理しやすくなる。
例えば、リングトポロジーの場合、1つのマシンに着目してみると、右への接続を"right"、左への接続を"left"といったキーで呼び出すことができると嬉しい。

また、受け取ったデータがどこから来たか、受け取るときに把握できると望ましい。
なぜならば、ルーティングを行うときに役立つからである。ツリートポロジーの場合、親から来たデータを子に伝搬するといった処理を記述することがよくある。その時に、どこからデータが来たかという情報は重要である。

これらの問題点を踏まえて設計した、新しい分散アプリケーションフレームワークの設計を次章では示す。