Mercurial > hg > Papers > 2022 > ikki-master

--- a/Paper/chapter/5-Implementation.tex	Sat Jan 22 23:27:45 2022 +0900
+++ b/Paper/chapter/5-Implementation.tex	Tue Jan 25 22:27:11 2022 +0900
@@ -4,23 +4,23 @@
 複数のプロセスから競合的なアクセスが可能を可能としたい。

 GearsFSは分散フレームワークChristieの仕組みの一部を応用する。
-Christieの仕組みを取り入れることで、ファイルの送受信に関しては、
-ファイル内データをDataGearとして送受信することで実現する。
+Christieの仕組みを取り入れることで、ファイルの送受信に関して、
+ファイル内データをレコード単位で分割し、DataGearとして送受信することで実現する。


 \section{GearsFSのファイル構成}
 GearsOSのファイルは単なるDataGearのListQueueとして実装する。
-また、ファイルのデータを貯蓄する主要なQueueとは別にinputもしくはoutputStreamとなるQueueを持ち合わせている。
+ファイルのデータはレコードとして特定の型へ断続的に分割されたDataGearとして保存される。
+ファイルの読み込みの際にはQueueに対してレコードが無くなるまでTake処理を繰り返し、レコードを参照してファイルの中身を構築することで実現する。

-GearsFSではファイル読み込みもしくは書き込みの際、それぞれinputもしくはoutputの際にストリームのキューに対してアクセスを行う。
-それぞれのキューはkey名としてinput/OutputstreamをもつQueueとして呼び出される。
-それぞれのキューはDataGearに相当し、GearsFSのファイルはChrsitieにおけるDataGearManagerに相当する。
+GearsファイルはDataGearのリストとしてファイルのデータを保持する主要なQueueとは別にinputもしくはoutputStreamとなるQueueを持ち合わせており、
+ファイル読み込みもしくは書き込みの際、それぞれinputもしくはoutputの際にstreamに対してアクセスを行う。
+それぞれのQueueはChristieにおけるkey名を持つDataGearとしてinput/OutputstreamをもつQueueとして呼び出される。
+そのため、GearsFSのファイルはChrsitieにおけるDataGearManagerに相当する。
 GearsOSのファイル構造へのアクセスを図\ref{fig:gearsFile}に示す。
 また、データのリストとなるQueueの構造を図\ref{fig:QueueElement}に示す。

-
-
 \begin{figure}[h]
     \begin{center}
         \includegraphics[width=150mm]{./images/GearsFile.pdf}
@@ -39,10 +39,10 @@
 \end{figure}


-ファイルに対して変更、つまり新しく書き込みを行う際はInputQueueのkeyを指定してput操作を行う。
+ファイルに対して書き込み、つまり従来のwriteにあたる処理を行う場合はInputQueueのkeyを指定してput操作を行う。
 最終的にInputQueueに格納されたデータはInputQueueから取り出され、mainQueueに対して格納される。

-ファイルの読み込みを行う際はOutputQueueに対してTake操作を行えば良い。
+ファイルの読み込み(read)を行う際はOutputQueueに対してTake操作を行えば良い。
 OutputQueueにはmainQueueの要素が複製されており、OutputQueue内の要素を全てTakeで呼び出す。
 ファイルを呼び出す側は取り出したElementのログを順番に読むことでファイルを構築する。

@@ -53,12 +53,26 @@
 SingleLinkedな(単純な)Queueを用いることも考えられる。
 ファイルに対する書き込みやMainQueueは単一プロセスのみからのアクセスとなるためSingleLickedなキューで実装する。

+ファイルのレコードは例題中では単純にファイル内文字列を行ごとに区切り、FileString構造体に書き込んだものとなる。
+\ref{src:FS}にFileString構造体を示す。
+str部分にファイル内文字列を格納し、レコードが全て送信したことを示すEoFフラグが付属している。
+ファイルレコードはGears側のDataGearとして利用も行えるように、ContextにDataGearとして登録された構造体となる。
+
+FileStringはテストに用いられる単純なレコードである。
+実用性のあるレコードを考察した場合、ファイルに変更が加えられた場合Queueに格納するレコードを行順に構成し直す必要性が生じるなど多くの問題が存在する。
+また、GearsFSではファイルの型をOSが区別できることを目指したい。
+レコードの型を最適な形に変更することによって複数のファイルの型に対応したい。
+例として、テキストデータの場合、変更差分をレコードとしてQueueに格納し、QueueのレコードをTopから参照していくことで構築を行う。
+また、画像ファイルなどファイルの中身の変更が行われない形式は、ファイル内のデータをブロック長に区切り扱うといった手段が考えられる。
+
+\lstinputlisting[label=src:FS, caption=例題のレコードとして使われるFileString構造体]{src/FileString.h}


 \section{WordCount例題}
 GearsFSのAPIの構成をWordCount例題を通して行う。
-WordCount例題とは、指定したファイルの中身を読み取り、文字数と行数列、加えて文字列などを出力するという例題である。
+WordCount例題とは、指定したファイルの中身を読み取り、文字数と行数列、加えて文字列を出力するという例題である。
+この例題を通すことでファイルに対するAPIを構築する。
 コード\ref{src:WcImpl}にCbCで記述した、Unixファイルに対してWordCountを行うプログラムの一部を示す。

 ファイルとWordCountはUNIXのシェルのようにプログラムの外で行われる。
@@ -71,6 +85,7 @@
 このように特定の条件を満たすまであるCodeGear間をループ遷移する構成をGearBoxと名付けている。


+
 \lstinputlisting[label=src:WcImpl, caption=Unixファイルに対するWordCount.cbcの一部]{src/WcImpl.cbc}

 \begin{figure}[tb]
@@ -83,10 +98,11 @@


-\section{ChristieAPIによるWordCount}
-ChiristieのDataGearManagerの仕組みを基準としたGearsFSのファイル通信のAPIによるWordCountの設計を行った。
+\section{ChristieAPによるWordCount}
+ChiristieのDataGearManagerの仕組みを基準としたChristieAPIによるWordCountの設計を行った。
 図\ref{fig:ChristieAPI}にChristieAPIによるWordCountを示す。
 ChristieAPIによるファイルデータ通信は2ペアのLocal/RemoteDGMを通して行われる。
+RemoteDGMは接続先のノードが持つLocalDGMのプロキシであり、RemoteDGMに対してput操作を行うことで、相手の持つLocalDGMへのデータの送信が行える。
 NodeA側が任意のファイルを開き、ファイル内の行ごとの文字列をデータとしてNodeB側に対応するRemoteDGMにputする。
 NodeB側は自身のLocalなDGMからデータを得て、WordCountの処理を行ったのちに
 NodeAに対応するRemoteDGMに対してそのデータに対する処理が完了したことを通知するAck(acknowledgement)をputする。
@@ -111,27 +127,40 @@


 \section{Socket付きQueue}
-ChristieにおけるRocalDataGearManagerはプログラム内で使われるDataGearのkeyとデータを全て所持したコレクションにあたる。
+ChristieにおけるLocalDataGearManagerはプログラム内で使われるDataGearのkeyとデータを全て所持したコレクションにあたる。
 keyとデータの組み合わせは、keyの名前がつけられたQueueに対して保存される、
 TakeコマンドではそのkeyのQueueからデータを取り出し、Peekの場合は先頭のデータを取り出さず参照のみを行っている。
 つまりChristieのDGMは詳細には単純なQueueの集合であると言える。
 RemoteDGMとLocalDGMの通信の際にはLocalDGMが持つsocketに対してRemoteDGMが接続を行い、putされたkeyとDataをsocket経由でコマンドとして送信する。

+
 GearsOSのChristieAPIの定義のためにsocketに接続されたQueueによるWordCount例題を作成した。
 ソースコード\ref{src:LDGMQueue}にLocalDGM側にあたる、Socket付きのQueueのCodeGear:getData部分を示す。
 加えてソースコード\ref{src:RDGMQueue}にRemoteDGM側にあたるSocket付きのQueueのCodeGear:sendData部分を示す。
+二つのQueueはmainプログラムによりsocketの接続が行われ、一方が文字列の送信を行い、もう一方がCount処理を行うことによってWordCountが行われる。
+
 socketはC言語のSocketインターフェースを用いており、
 ImplementのコンストラクタにあたるcreateLocalDGMQueueにて呼び出され、
 Implのメンバ変数であるsocketに置かれている。
+ソースコード\ref{src:LDGQh}に受信側となるLocalなQueueのImplementを示す。
+socketはint型での取り扱いが行われる。Impl部分へ保存をすることで、Implを実装したプログラム内ならどのCodeGearからでもsocketの参照が行える。
+
 また、既存のQueueから新たなAPIを追加するためにQueueInterfaceを新しく書き換えたcQueue(Communicate Queue)Interfaceを継承している。
 Local側のgetDataはAPIとしての呼び出しが可能となっている。socketが受け取ったデータを最終的にdataとしてQueueに対してputを行う。
-Remote側のsendDataはAPIとしては呼び出しは行えず、putAPIが呼び出されQueueへのput処理が終了した後に遷移され、putしたDataを接続先のQueueに対して送信する。
-送信データは全てのDataGearのUnionとなるData型で受け取る。
+Remote側のsendDataはAPIとしては呼び出しは行えず、putAPIが呼び出されQueueへのput処理が終了した後に遷移され、
+putしたDataを接続先のQueueに対して送信する。
+
+\lstinputlisting[label=src:LDGQh, caption=LocalDGMQueueのImplement]{src/LocalDGMQueue.h}
+
+現状ではデータの通信に行われるDataGearは全てのDataGearのUnion(共用体)となるData型を用いている。
 送信データのサイズをUnion Data型のサイズにしている理由は、sizeof関数で返される値は共用体に含まれる構造体の中で最も大きなメモリサイズを返すためである。
+これによりputされたDataGearの型がどのようなものであれ、受け取り側がDataGearの型を正しく選択している限りはデータの整合性を守ることができる。
+しかし、受信側が受け取ったデータレコードの正しい型を把握しているとは限らないため、
+将来的にはmessagePackなどによるシリアライズしたデータを送信する形にする。
 Socketの処理中に問題が発生した場合はinputDataGearとして指定した\texttt{\_\_}code whenError()として入力されたCodeGearに対して遷移する。

-GearsOSにおけるファイルはChristieのDGMとして見なすことができる。
-今回作成したQueueはそれぞれInput/OutputStreamに相当する。
+GearsOSにおけるファイルはChristieのDGMとして見なすことができ、今回作成したQueueはそれぞれInput/OutputStreamに相当する。
+

 \lstinputlisting[label=src:LDGMQueue, caption=LocaDGMQueueのgetData]{src/LocalDGMQueue.cbc}
 \lstinputlisting[label=src:RDGMQueue, caption=RemoteDGMQueueのsendData]{src/RemoteDGMQueue.cbc}
@@ -141,26 +170,28 @@
 \section{GearsOSにおけるDataGearManager}
 先で述べたSocket付きのQueueは、DataGearであるQueueとSocketが直接結びついているため、
 一つのDataGearを用いる場合となる最低限の通信しか行えない。
-複数のDataGear(key)を用いての通信を構成するためには複数のQueueを備えることのできるリストを生成し、
+複数のDataGear(key)を用いての通信を構成するためには複数のQueueを蓄えることのできるリストを生成し、
 そのリスト自体がsocketを持つ必要がある。

 GearsOSではDataGearを保持するQueueのリストとして赤黒木を用いる。
 赤黒木は平衡二分木であり、木に対する操作時に行われる操作によりノードの階層が平衡化される
 そのため各操作の最悪時間計算量O(logN)となり、二分木の中でも実用性を備えている。

-DataGearとなるのデータはkeyごとに作られたQueueに保存される、従ってQueueStoreとなる赤黒木にはkeyごとのQueueがノードとして保持される。
-図\ref{fig:GearsDGM}にファイルとなるDataGearManagerに対して任意のkeyに対してput/take操作を行う際の処理を示す。
+DataGearはkeyごとに作られたQueueに保存される、従ってQueueのstoreとなる赤黒木にはkeyごとのQueueがノードとして保持される。
+図\ref{fig:GearsDGM}にファイルとなるDataGearManagerの任意のkeyに対してput/take操作を行う際の処理を示す。
 いずれの場合もStoreとなる赤黒木に対して任意のkeyのQueueのget操作を行い、そのQueueに対してputもしくはtake操作を行う。
 あくまでこのDGMはファイルに相当するものなので、
 赤黒木に含まれているQueueはInput/OutputStreamと実際にファイルデータを保持しておくmainDataQueueの三つとなる。
-しかし、WordCount例題のackや結果出力のようにStreamとなるkey以外を用いるために、ファイルに関連するkey以外にも任意にQueueを追加することもできる。
-任意のQueueを追加したい場合はStoreとなるTreeに対して、
+しかしWordCount例題のackや結果出力の通信など用途を持つ、Streamとなるkey以外を用いるために、
+ファイルに関連するkey以外にも任意にQueueを追加することもできる。
+任意のQueueを追加したい場合はstoreとなるTreeに対して、
 Treeが保持していないkeyへputが行われた場合は新しくそのkeyを持つQueueを生成しTreeに持たせる処理を追加すれば良い。

-図に示した手順のDataアクセスではファイルの呼び出しなどのDataGearの断続的な参照が行われる場合、
+図に示した手順のDataアクセスではファイルの呼び出しなどDataGearの断続的な参照が行われる場合、
 Treeへの探索処理がボトルネックになってしまう可能性が考えられる。
-これは特定のkeyのQueueのアドレスをmain部分で直接行えるように、
-TreeにkeyのQueue自体のアドレスをOutputさせるAPIを記述することで解決が行えると考えられる。
+これは特定のkeyのQueueをmain部分で直接参照できるように、
+TreeにQueue自体のポインタをOutputさせるAPIを記述することで解決が行える。
+


 \begin{figure}[h]
@@ -178,13 +209,14 @@
 \section{ディレクトリシステム}
 本研究と並行する形で又吉雄斗によるGearsFileSystemのディレクトリ構造の構築が行われている。[論文No.]
 GearsFSのディレクトリシステムはUnixOSのディレクトリシステムと同じ仕組みを用いて再現することを試みている。
-通常のUnixのディレクトリシステムと異なる点として、ディレクトリをRedBlackTreeを用いて構成する。
+通常のUnixのディレクトリシステムと異なる点として、ディレクトリを赤黒木(RedBlackTree)を用いて構成する。

 図\ref{fig:GearsDirectory}にGearsFSの構成図を示す。
-一つのディレクトリは赤黒木であり、あるディレクトリの中に位置するファイル(ディレクトリ含む)は赤黒木の中のノードにvalueとして同等に配置される。
-赤黒木にはファイル下に配置された別のディレクトリもしくはファイルが保存される。
+一つのディレクトリは赤黒木を持ち、あるディレクトリの中に位置するファイル(ディレクトリ含む)は親ディレクトリが持つ赤黒木の中にノードとして同等に配置される。
+あるディレクトリに存在するファイルを参照する場合は、ディレクトリの持つTreeに対して探索を行えば良い。
 図の例では/(ルートディレクトリ)からUsersディレクトリ下にあるDadというディレクトリ(もしくはファイル)を参照するには、
 /のTree内のUsersを探索、続いてUsersTreeの内部のDadを探索する形となる。
+また、親ディレクトリを持つ全てのファイルは、親のディレクトリの情報を保持している。

 \begin{figure}[h]
     \begin{center}
@@ -195,10 +227,10 @@
 \end{figure}

 GearsのディレクトリシステムはUnixのinodeの仕様を用いる。
-inodeとはファイルごとのユニークな番号(inode番号)データ領域へのポインタや作成日時、サイズなどのメタデータを保存するための領域である。
+inodeとはファイルごとのユニークな番号(inode番号)。データ領域へのポインタや作成日時、サイズなどのメタデータを保存するための領域である。
 GearsFSの赤黒木を用いたディレクトリシステムに実際に保存されるノードはkeyがFileName、
 valueがinodeのペアを保持している。
-DirectoryTreeで探索し任意のファイルのinode番号を手に入れ、DirectroyTreeとは別に実装されたkeyにinode番号とvalueとして
+DirectoryTreeをファイル名で探索を行い、任意のファイルのinode番号を手に入れ、DirectroyTreeとは別に実装されたkeyにinode番号、ペアとして
 ファイルのポインタを保持させるTreeをinode番号で探索させる形となる。
 この形で実装することにより、ファイル自身が所属するDirectoryをinode番号で保持でき、親Directoryが複数存在していたり、
 親DirectoryのFileNameが変更された場合においてもDirectoryの構造の障害が起きない。
@@ -222,8 +254,8 @@
 特定の時点のファイルとDirectoryの状態を呼び出す際は、レコードの変更日時を確認し、参照するべきTree構造とレコードを呼び出す形となる。

 非破壊的木構造の編集と変更履歴式のデータレコードはディレクトリやファイルの容量が変更が行われるたびに増加していくという問題が存在する。
-この点については任意の期間経過、もしくはユーザの操作により定期的に過去のデータを自動削除することで容量がある程度削減が望める。
-また、近年の電子記録媒体の容量増加に伴い問題の重要性が低下していくことが予想できる。
+この点については任意の期間経過、もしくはユーザの操作により定期的に過去のデータを自動削除もしくは整形することで容量がある程度の削減が望める。
+また、近年の電子記録媒体の容量増加に伴い問題の重要性が低下していくことが期待できる。


 \begin{figure}[h]
@@ -234,6 +266,15 @@
     \label{fig:TreeEdit}
 \end{figure}

-
+\section{GearsFSの分散処理}
+分散フレームワークChristieとGearsOSFileSystemにおける分散処理について考察する。
+GearsFSではファイルはDataGearのリストとして実装される。
+ファイルの読み取り書き込みを含めた通信はDataGearリストにある特定のkeyのDataGearのQueueに対してDataを書き込み、
+もしくは呼び出しを行うことで実現される。
+そのためファイルはDataGearManagerであると言える。

-\section{sokcet付きQueueによるDataGearPool}
+GearsFSのファイルはChristieのDataGearManagerの仕組みを参考にするものであるが、ChristieのDGMとの明確な違いとして、
+GearsFSのDGMはChristieのようにDataGearの差し込みによる通信を構成するだけの用途でなく、ファイルそのものとしての用途を持つという点が存在する。
+そのため、ChristieDGMのように一つのスレッド(CGM)により管理されるものではなく、複数のスレッドから競合的にアクセスが行われるDGMである。
+よってDataGearを保持するQueueは純粋なQueueでなく複数のアクセスが行われても、
+データの整合性が保たれるSynchronizedなQueueを用いる必要が生じる場面がある。
Binary file Paper/master_paper.pdf has changed
--- a/Paper/src/LocalDGMQueue.cbc	Sat Jan 22 23:27:45 2022 +0900
+++ b/Paper/src/LocalDGMQueue.cbc	Tue Jan 25 22:27:11 2022 +0900
@@ -1,15 +1,16 @@
 __code getDataLocalDGMQueue(struct LocalDGMQueue* cQueue, __code next(...), __code whenEOF(...), __code whenError(...)){
     int recv_size, send_size;
-    char recv_buf[BUF_SIZE], send_buf;
+    char send_buf;

     union Data* recv_data;
     recv_size = recv(cQueue->socket, recv_data, sizeof(union Data), 0);
     if (recv_size == -1) {
         printf("recv error\n");
-        goto exit_code();
+        goto whenEOF(...);
     }
     if (recv_size == 0) {
         printf("connection ended\n");
+        goto next(...);
     }