\chapter{GearsFileSystemの設計と実装}
本章ではGearsOSのFileSystem(以下GearsFS)の実装について解説する。
GearsOSのファイルは分散ファイルシステム的に大域的な資源として、
複数のプロセスから競合的なアクセスを可能としたい。

GearsFSは分散フレームワークChristieの仕組みの一部を応用する。
ファイルはChristieにおけるDataGearManager的に実装を行い、ファイルの送受信は、
ファイル内データを構造体の単位で分割し、DataGearとして送受信することで実現する。

Christieは自律分散システムを目指した分散フレームワークである。
Christieの仕組みにより、GearsFSは通信の中枢となるサーバーノードが必要なくなるような、自律分散なファイルシステムを目指す。


\section{GearsFSのファイル構成}
GearsOSにおけるファイルのデータは任意の型を持った構造体に断続的に分割されて構成され、
それを保持するファイルは単なるDataGearのListQueueとして実装される。
ファイルの最小単位をDataGearとすることでファイルデータの扱いをCodeGearで記述できる。
GearsFSにおけるファイルの読み書きは従来の分散ファイルシステムのようなプロトコルを用いず、データベースアクセス的な処理で構成される。
プロトコルを用いず、最低限なデータアクセスによる通信を構成することで、分散通信技術の見通しをよくする狙いがある。
また、CodeGearはTransactionと言えるのでkeyの書き込みはTransactionに閉じられ、動作が明確になる。

ファイルの読み込みの際はQueueに対して順次DataGearのTake操作を繰り返し、連続したDataGearからファイルの中身を構築することで実現する。
つまり、一見としてChristieのファイルはQueueとその要素(Element)として構成される。
データのリストとなるQueueの構造を図\ref{fig:QueueElement}に示す。


\begin{figure}[h]
    \begin{center}
        \includegraphics[width=150mm]{./images/QueueElement.pdf}
    \end{center}
    \caption{FileData Stacking Queue}
    \label{fig:QueueElement}
\end{figure}


しかし、単純に一つのQueueに対しファイルとして直接読み書きを行うと、複数のノードからのアクセスされた際の整合性や、セキュリティの面で問題が発生する。
そのため、GearsFSのファイルは主体となるデータを保持する主要なQueueとは別にinputもしくはoutputStreamとなるQueueを持ち合わせている。
そのためGearsFSファイルは複数の役割を持ったDataGearを持つリストとして実装される。
GearsOSのファイル構造へのアクセスを図\ref{fig:gearsFile}に示す。
ファイル読み込みもしくは書き込みの際にはそれぞれinputもしくはoutputの際にstreamに対してアクセスを行う形でファイルに対する読み書きが行われ、
それぞれのQueueはリスト内で固有のkeynameを保持している。
つまり、ファイルに対する読み書きを行う際は、Queueリストに対してinputもしくはoutputのstreamQueueのkeyに対してput操作、もしくはtake操作を行えば良い。
これは、ChrsitieにおけるDataGearのkeyとその要素に相当し、それらをリストとして持ち合わせているファイルはDataGearManagerに相当する。

\begin{figure}[h]
    \begin{center}
        \includegraphics[width=150mm]{./images/GearsFile.pdf}
    \end{center}
    \caption{GearsFSの呼び出し/書き込み}
    \label{fig:gearsFile}
\end{figure}


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

ファイルの読み込み(既存のファイルシステムでのread)を行う際はOutputQueueに対してTake操作を行えば良い。
OutputQueueにはmainQueueの要素が複製されており、OutputQueue内の要素を全てTakeのループにより呼び出す。
ファイルを呼び出す側は取り出したDataGearを順番に読むことでファイルを構築する。

GearsOSのファイルは大域的な資源として同時に複数のプロセスから参照が可能になる作りにしたい。
OutputQueueは複数のプロセスからファイル読み込みが行われた際に、データの整合性が失われてしまう危険性がある。
そのため、OutputQueueはCAS(Compare And Swap)を実装したSynchronizedQueueを用いる。
しかしファイルのアクセス権限の設定などにより、データアクセスが単一のプロセスからしか許さないもしくは想定されない環境では
読み込みの高速化とメモリの軽量化のため、
SingleLinkedな(単純な)Queueを用いることも考えられる。
ファイルに対する書き込みやMainQueueは単一プロセスのみからのアクセスとなるためSingleLinkedなキューで実装する。

ファイルデータとなるDataGearは例題中では単純にファイル内文字列を行ごとに区切り、FileString構造体に書き込んだものとなる。
\ref{src:FS}にFileString構造体を示す。
str部分にファイル内文字列を格納し、DataGearが全て送信したことを示すEoFフラグが付属している。
ファイルデータDataGearはGears側のDataGearとして利用も行えるように、ContextにDataGearとして登録された構造体である。

FileStringはテストに用いられる単純な構造体である。
実用性のあるファイルデータ構造体を考察した場合、ファイルに変更が加えられた場合Queueに格納するDataGearを行順に構成し直す必要性が生じるなど多くの問題が存在する。
また、GearsFSではファイルの型をOSが区別できることを目指しており、
DataGearの型を最適な形に変更することによって複数のファイルの型に対応したい。
例として、テキストデータの場合、gitやMercurialなどのバージョン管理システムのように、
変更差分をファイルデータとしてQueueに格納し、QueueのDataGearをTopから参照していくことで構築を行う。
また、画像ファイルなどファイルの中身の変更が行われない形式は、ファイル内のデータをブロック長に区切り扱うといった手段が考えられるなど、
ファイルの型に応じてDataGearの構造体を任意に構成することができる。

\lstinputlisting[label=src:FS, caption=例題のファイルDataGearとして使われるFileString構造体]{src/FileString.h}



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

ファイルとWordCountの接続はUNIXのシェルのようにプログラムの外で行われる。
ファイルは事前にC言語のFILE型構造体を用いて開かれ、行列であるwc\texttt{->}strTableへ内部文字列を行区切りで保存されている。
MainからファイルのOpenが完了した後、CodeGear:putStringに遷移し、strTableから文字列を行ごと呼び出しCountUpへ入力し遷移する。
CodeGear:CountUpにて文字列の出力と文字数を読み取り記録、そしてputStringへ遷移する。
ファイルの文字列がある間はputStringとCountUpをループし続け、
putStringはstrTableの中身がなくなった(EOF)ならshowResultへ遷移する形となる。
図\ref{fig:WordCount}にCGの遷移図を示す。

WordCountのFileOpenとWordCount処理を別ノード上で行うことで、ファイルの読み込みとファイルの送信の構成が行える。

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

\begin{figure}[h]
    \begin{center}
        \includegraphics[width=150mm]{./images/UnixWC.pdf}
    \end{center}
    \caption{Unixファイルに対するWordCountのCG遷移}
    \label{fig:WordCount}
\end{figure}

\section{GearsFile APIによるWordCount}
GearsFSはChristieのLocalDataGearManagerとRemoteDataGearManagerによる通信の仕組みを用いてファイルデータの送受信を構成する。これをGearsFile APIと呼ぶ。
ChrstieAPIではファイルをDataGearManagerと見なすことができ、
Local上にRemote先のファイルのproxyとなるRemoteDGMを作成し、
これに対しLocalのファイルへの書き込みと同様に操作を行うことで自動的に通信を行ってくれる。

ChristieのDataGearManagerの仕組みを基準としたGearsFile APIによるWordCountの設計を行った。
図\ref{fig:GearsFile API}にGearsFile APIによるWordCountを示す。
GearsFile APIによるファイルデータ通信は2ペアのLocal/RemoteDGMを通して行われる。
RemoteDGMは接続先のノードが持つLocalDGMのプロキシであり、RemoteDGMに対してput操作を行うことで、相手の持つLocalDGMへのデータの送信が行える。
NodeA側が任意のファイルを開き、ファイル内の行ごとの文字列をデータとしてNodeB側に対応するRemoteDGMにputする。
NodeB側は自身のLocalDGMからデータを得て、WordCountの処理を行ったのちに
NodeAに対応するRemoteDGMに対してそのデータに対する処理が完了したことを通知するAck(acknowledgement)をputする。
Ackを受け取ったOpen側のノードBは再び続きのファイル内文字列をデータとして送信する。
ここまでの処理が繰り返され、ファイル内の文字列が全て処理されたら、Open側はEoF(End of File)をCount側に対して通知、
NodeBは最後にWordCountの結果をRemoteDGMに対してputしOpen側に送信する。
そして、双方のRemoteDGMを閉じることにより通信を終了させる。


\begin{figure}[h]
    \begin{center}
        \includegraphics[width=150mm]{./images/wordCountDGM.jpg}
    \end{center}
    \caption{GearsFile APIによるWordCount}
    \label{fig:GearsFile API}
\end{figure}



\section{GearsOS上のSocket通信}
RemoteDGMとLocalDGMの接続の際にはLocalDGMが持つsocketに対してRemoteDGMが接続を行い、
Dataの書き込み先のkeyを指定してsocket経由でコマンドとして送信する。

socketを所有したQueueによるWordCount例題の記述を行うことでGearsOSにおけるsocket通信の実装を行った。
接続元と接続先のsocketは、Queueの作成時に行われ、
socketへのアクセスはQueueのAPIであるPut/Take/Peekの際に行われる。
ソースコード\ref{src:LDGMQueue}にLocalDGM側にあたる、Socket付きのQueueのCodeGear:getData部分を示す。
加えてソースコード\ref{src:RDGMQueue}にRemoteDGM側にあたるSocket付きのQueueのCodeGear:sendData部分を示す。
CodeGear:getDataではsocketなどによるError発生時やEoFフラグがあるデータを受信した場合の遷移先を指定する必要ある。

二つのQueueはmainプログラムによりsocketの接続が行われ、一方が文字列の送信を行い、もう一方がCount処理を行うことによってWordCountが行われる。
socketはC言語のSocketインターフェースを用いており、
socketのImplementのコンストラクタにあたるcreateLocalDGMQueueにて呼び出され、
Implのメンバ変数であるsocketに置かれている。
ソースコード\ref{src:LDGQh}に受信側となるLocalなQueueのImplementに使われるデータ構造を示す。
socketはint型で宣言されている。Implementファイルで宣言したsocket変数へsocketを保存をすることで、
Implの実装となるプログラム内ならどのCodeGearからでもsocketの参照が行える。

CodeGearであるgetData/sendDataはそれぞれTake/PutAPIを呼び出した際に遷移が行われる。
getDataはQueueの実際のTake処理の直前に、sendDataはPut処理の直後に遷移されsocketを通じてデータの出し入れを行う。
sosketへのデータのやりとりはwrite/read関数で行われる。
send/readでない理由はファイルのデータ通信の相手は他のノードにあるファイルのsocketのみでなく、
記録デバイスへの書き込みも同様な記述で行うためである。

\lstinputlisting[label=src:LDGQh, caption=LocalDGMQueueで使われるデータ構造体]{src/LocalDGMQueue.h}

現状ではデータの通信に行われるDataGearは全てのDataGearのUnion(共用体)となるData型を用いている。
送信データのサイズをUnion Data型のサイズにしている理由は、sizeof関数で返される値は共用体に含まれる構造体の中で最も大きなメモリサイズを返すためである。
これによりputされたDataGearの型がどのようなものであれ、受け取り側がDataGearの型を正しく選択している限りはデータの整合性を守ることができる。
しかし、受信側が受け取ったデータDataGearの正しい型を把握しているとは限らないため、
将来的にはJavaにおけるMessagePackに相当する機能になどによるシリアライズしたデータを送信する形にする。
Socketの処理中に問題が発生した場合はinputDataGearとして指定した\texttt{\_\_}code whenError()として入力されたCodeGearに対して遷移する。

\newpage{}
\lstinputlisting[label=src:LDGMQueue, caption=LocaDGMQueueのgetData]{src/LocalDGMQueue.cbc}
\newpage{}
\lstinputlisting[label=src:RDGMQueue, caption=RemoteDGMQueueのsendData]{src/RemoteDGMQueue.cbc}

Queueによる通信で実装されたWordCount例題を記述した。
ソースコード\ref{src:WCbyGears}にファイル送信側のmain部分を示す。
Remote側は行ごとに分割した文字列が無くなるまでDataGearを送信し、なくなったらEoFデータを送る。
ソースコード\ref{src:WCget}にファイル受信側のmain部分を示す。
Local側では受け取ったデータのEoFフラグが1になるまでTake処理をループし、EoFが送られてきた場合は結果を出力する。

ソースコード\ref{src:wcResult}は Count側で表示される受け取った文字列とWordCountの結果出力である。



\lstinputlisting[label=src:WCbyGears, caption=Queueの通信による送信側WordCountのMain]{src/WordCOunt_Remote.cbc}

\lstinputlisting[label=src:WCget, caption=Queueの通信による受信側WordCountの]{src/Local_test.cbc}

\lstinputlisting[label=src:wcResult, caption=単一Queueによる簡易なWordCountの出力結果]{src/wcResult.txt}

\section{GearsOSにおけるDataGearManager}
先で述べたSocket付きのQueueは、GearsOS上でのsocket通信を構成するために記述を行った一例である。
これはDataGearであるQueueとSocketが直接結びついているため、
一つのDataGearを用いる場合となる最低限の通信しか行えない。
複数のDataGear(key)を用いての通信を構成するためには複数のQueueを蓄えることのできるリストを生成し、
そのリスト自体がsocketを持つ必要がある。

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

Queueを所持するリストはTreeでなくとも単純な単方向あるいは双方向リストなどでも実現は可能であるが、
GearsOSにおけるファイルは複数のプロセスからのアクセスが行われ、アクセスが増えるほどDataGearのkeyの数が増加するため赤黒木での実装を行う。

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

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



\begin{figure}[h]
    \begin{center}
        \includegraphics[width=150mm]{./images/newGearsFile.pdf}
    \end{center}
    \caption{GearsOSにおけるファイル(DGM)}
    \label{fig:GearsDGM}
\end{figure}




\section{ディレクトリシステム}
本研究と並行する形で又吉雄斗によるGearsFileSystemのディレクトリ構造の構築が行われている\cite{mata-thesis}。
GearsFSのディレクトリシステムはUnixOSのディレクトリシステムのi-nodeの仕組みを用いて再現することを試みている。
通常のUnixのディレクトリシステムと異なる点として、ディレクトリを赤黒木(RedBlackTree)を用いて構成する。

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

\begin{figure}[h]
    \begin{center}
        \includegraphics[width=80mm]{./images/GearsDirectory.pdf}
    \end{center}
    \caption{GearsDirectory}
    \label{fig:GearsDirectory}
\end{figure}

GearsのディレクトリシステムはUnixのi-nodeの仕様を用いる。
i-nodeとはファイルごとのユニークな番号(i-node番号)をもち、データ領域へのポインタや作成日時、サイズなどのメタデータを保存するための領域である。
GearsFSの赤黒木を用いたディレクトリシステムに実際に保存されるノードはkeyがFileName、
valueがi-nodeのペアを保持している。
DirectoryTreeをファイル名で探索を行うことで任意のファイルのi-node番号を手に入れ、DirectroyTreeとは別に実装されたkeyにi-node番号とペアとして
ファイルのディスクアドレスを保持させるTreeをi-node番号で探索させる形となる。
この形で実装することにより、ファイル自身が所属するDirectoryをi-nodeが保持でき、
ファイルの複数のアカウントでの共有などによる親Directoryが複数存在する場合や、
親DirectoryのFileNameが変更された場合においてもDirectoryの構造の障害の発生を防げぐことができる。



\section{GearsFSのバックアップ}
GearsOSは将来的にOS自体がバックアップの機能を保持する構成を目指している。
GearsFSのDirectoryのバックアップは木構造の構築を非破壊的に行うことにより過去のデータを保持する。
図\ref{fig:TreeEdit}に非破壊的な木構造の編集を図に示す。
非破壊的木構造の編集とは編集元のノードのデータや接続を直接書き換えることなく、
根(ルートノード)から必要なノードは新しく生成し一部のノードは過去のものを使い回すことで更新することを指す。
図中の右側の編集後の木構造の赤く記されたノードは新規に作成、もしくはコピーされたノードとなる。
変更されたノードと根から変更ノードまでの道筋のノードは、編集元のノードとは別に新しく作成される。
それ以外のTreeに属していたノードは編集元のTreeのノードをポインタで接続することで使い回す。
つまり、図中の黒いノード1から探索を行えば過去のデータのノードが参照でき、
赤いノード1から探索を行えば編集後の木構造を参照することができる。

ファイル構造体の変更履歴については、ファイルのDataGearをファイルの変更差分を履歴として保持させる形にすることに加え、
変更日時を記録させることで実現したい。
diffコマンドようなファイル差分をDataGearにすることにより、gitやMercurialのようなバージョン管理を行う。
特定の時点のファイルとDirectoryの状態を呼び出す際は、DataGearの変更日時を確認し、参照するべきTree構造とDataGearの時点まで参照する形となる。


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

\begin{figure}[h]
    \begin{center}
        \includegraphics[width=150mm]{./images/nonDestroyTreeEdit.pdf}
    \end{center}
    \caption{非破壊的なTree編集}
    \label{fig:TreeEdit}
\end{figure}


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

GearsFSのファイルはChristieのDataGearManagerの仕組みを参考にするものであるが、ChristieのDGMとの明確な違いとして、
GearsFSのDGMはChristieのようにDataGearの差し込みによる通信を構成するだけの用途でなく、ファイルそのものとしての用途を持つという点が存在する。
そのため、ChristieDGMのように一つのノード(CGM)により管理されるものではなく、複数のプロセスから競合的にアクセスが行われるDGMである。
よってDataGearを保持するQueueは純粋なQueueでなく複数のアクセスが行われても、
データの整合性が保たれるSynchronizedなQueueを用いる必要が生じる場面がある。

ChristieではTask(CodeGear)はCodeGearManagerにより実行が行われる。
GearsFSでは並列処理をCodeGearManagerを用いた実装に代わり、GearsOSに搭載されたpar gotoを利用するという手段が考えられる。
par gotoとはGearsOSにおける並列処理構文である。
par gotoによる並列処理ではTaskをContextで表現し、TaskのInputDataGearが揃ったTaskをWorkerで処理を行う。
図\ref{fig:WorkerRun}にpar goto構文による並列処理を示す。
GearsFSではstreamに対する書き込みや取り出しとqueueに蓄えられたファイルDataGearの送受信を並列に実行する。
当然複数のファイルが同時に通信される場合はそれらも並行に処理が行われる。

現状、GearsOSのpar gotoは実装にいくつか問題点があり、処理速度が比較的遅いことに加え、
トランスコンパイラによる書き出しが多くバグが発生しやすい。
そのため、par gotoによる並列処理の構成をより軽量なものに改良する、
もしくはファイル通信用の並列処理を独自に開発してしまうという案も考えられる。

\begin{figure}[h]
    \begin{center}
        \includegraphics[width=170mm]{./images/WorkerRun.pdf}
    \end{center}
    \caption{par gotoによる並列処理}
    \label{fig:WorkerRun}
\end{figure}


\section{GearsFSの持続性}
GearsFileSystemにおいてファイルは分割されたDataGearを保持するQueueを持つリストになることを論じた。
メモリ空間上に展開され、変更が行われたデータをSSDなどの持続性を持つデバイスへ保存する場合、
リスト(DataGearManager)の中のQueueである、ファイルデータそのものを保持しているmainDataQueueを格納すれば良い。
持続性デバイスは単なるメモリとして扱ってよく、メモリ上のデータ構造と同様に構築する。
逆にメモリ上へファイルを展開する場合、デバイス上に保存されているQueueを呼び出し、メモリ上でLocalDataGearManagerとして構築すれば良い。
図\ref{fig:fp}にデバイス上に保存されたDGMをLocalDGMとして呼び出す際の遷移図を示す。
ストレージ上のブロックのアドレスはunixファイルシステム同様に、ファイルが保持しているi-nodeが認知していればよい。


\begin{figure}[h]
    \begin{center}
        \includegraphics[width=120mm]{./images/filePersistency.pdf}
    \end{center}
    \caption{file Persistency}
    \label{fig:fp}
\end{figure}