Mercurial > hg > Papers > 2022 > ikki-master
annotate Paper/chapter/5-Implementation.tex @ 11:a3cda2aa18aa
add par goto??
| author | ichikitakahiro <e165713@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Thu, 27 Jan 2022 22:49:44 +0900 |
| parents | cc4cb64f9af9 |
| children | 2c54886cebef |
| rev | line source |
|---|---|
|
5
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1 \chapter{GearsFileSystem Implementation} |
|
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2 本章ではGearsOSのFileSystem(以下GearsFS)の実装について解説する。 |
|
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
3 GearsOSのファイルは分散ファイルシステム的に大域的な資源として、 |
|
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
4 複数のプロセスから競合的なアクセスが可能を可能としたい。 |
|
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
5 |
|
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
6 GearsFSは分散フレームワークChristieの仕組みの一部を応用する。 |
| 9 | 7 Christieの仕組みを取り入れることで、ファイルの送受信に関して、 |
| 8 ファイル内データをレコード単位で分割し、DataGearとして送受信することで実現する。 | |
|
5
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
9 |
|
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
10 |
|
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
11 |
|
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
12 \section{GearsFSのファイル構成} |
| 11 | 13 GearsOSにおけるファイルのデータは任意の型を持ったレコード(構造体)に断続的に分割されて構成され、 |
| 14 それを保持するファイルは単なるDataGearのListQueueとして実装される。 | |
| 15 ファイルの読み込みの際はQueueに対して順次データレコードのTake操作を繰り返し、連続したレコードからファイルの中身を構築することで実現する。 | |
| 16 つまり、一見としてChristieのファイルはQueueとその要素(Element)として構成される。 | |
| 17 データのリストとなるQueueの構造を図\ref{fig:QueueElement}に示す。 | |
|
5
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
18 |
|
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
19 |
|
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
20 \begin{figure}[h] |
|
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
21 \begin{center} |
|
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
22 \includegraphics[width=150mm]{./images/QueueElement.pdf} |
|
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
23 \end{center} |
| 11 | 24 \caption{FileData Stacking Queue} |
|
5
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
25 \label{fig:QueueElement} |
|
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
26 \end{figure} |
|
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
27 |
|
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
28 |
| 11 | 29 しかし、単純に一つのQueueをファイルとして直接読み書きを行うと、複数のノードからのアクセスされた際の整合性や、セキュリティの面で問題が発生する。 |
| 30 そのため、GearsFSのファイルは主体となるデータを保持する主要なQueueとは別にinputもしくはoutputStreamとなるQueueを持ち合わせている。 | |
| 31 そのためGearsFSファイルは複数の役割を持ったDataGearを持つリストとして実装される。 | |
| 32 GearsOSのファイル構造へのアクセスを図\ref{fig:gearsFile}に示す。 | |
| 33 ファイル読み込みもしくは書き込みの際にはそれぞれinputもしくはoutputの際にstreamに対してアクセスを行う形でファイルに対する読み書きが行われ、 | |
| 34 それぞれのQueueはリスト内で固有のkeynameを保持している。 | |
| 35 つまり、ファイルに対する読み書きを行う際は、Queueリストに対してinputもしくはoutputのstreamQueueのkeyに対してput操作、もしくはtake操作を行えば良い。 | |
| 36 これは、ChrsitieにおけるDataGearのkeyとその要素に相当し、それらをリストとして持ち合わせているファイルはDataGearManagerに相当する。 | |
| 37 | |
| 38 \begin{figure}[h] | |
| 39 \begin{center} | |
| 40 \includegraphics[width=150mm]{./images/GearsFile.pdf} | |
| 41 \end{center} | |
| 42 \caption{GearsFSのread/writeAPI} | |
| 43 \label{fig:gearsFile} | |
| 44 \end{figure} | |
| 45 | |
| 46 | |
| 9 | 47 ファイルに対して書き込み、つまり従来のwriteにあたる処理を行う場合はInputQueueのkeyを指定してput操作を行う。 |
|
5
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
48 最終的にInputQueueに格納されたデータはInputQueueから取り出され、mainQueueに対して格納される。 |
|
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
49 |
| 9 | 50 ファイルの読み込み(read)を行う際はOutputQueueに対してTake操作を行えば良い。 |
| 11 | 51 OutputQueueにはmainQueueの要素が複製されており、OutputQueue内の要素を全てTakeのループにより呼び出す。 |
| 52 ファイルを呼び出す側は取り出したレコードを順番に読むことでファイルを構築する。 | |
|
5
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
53 |
|
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
54 GearsOSのファイルは大域的な資源として同時に複数のプロセスから参照が可能になる作りにしたい。 |
| 11 | 55 OutputQueueは複数のプロセスからファイルreadが行われた際に、データの整合性が失われてしまう危険性がある。 |
|
5
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
56 そのため、OutputQueueはCAS(Compare And Swap)を実装したSynchronizedQueueを用いる。 |
| 11 | 57 しかしファイルのアクセス権限の設定などにより、データアクセスが単一のプロセスからしか許さないもしくは想定されない環境では読み込みの高速化とメモリの軽量化のため、 |
|
5
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
58 SingleLinkedな(単純な)Queueを用いることも考えられる。 |
|
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
59 ファイルに対する書き込みやMainQueueは単一プロセスのみからのアクセスとなるためSingleLickedなキューで実装する。 |
|
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
60 |
| 9 | 61 ファイルのレコードは例題中では単純にファイル内文字列を行ごとに区切り、FileString構造体に書き込んだものとなる。 |
| 62 \ref{src:FS}にFileString構造体を示す。 | |
| 63 str部分にファイル内文字列を格納し、レコードが全て送信したことを示すEoFフラグが付属している。 | |
| 11 | 64 ファイルレコードはGears側のDataGearとして利用も行えるように、ContextにDataGearとして登録された構造体である。 |
| 9 | 65 |
| 66 FileStringはテストに用いられる単純なレコードである。 | |
| 67 実用性のあるレコードを考察した場合、ファイルに変更が加えられた場合Queueに格納するレコードを行順に構成し直す必要性が生じるなど多くの問題が存在する。 | |
| 68 また、GearsFSではファイルの型をOSが区別できることを目指したい。 | |
| 69 レコードの型を最適な形に変更することによって複数のファイルの型に対応したい。 | |
| 70 例として、テキストデータの場合、変更差分をレコードとしてQueueに格納し、QueueのレコードをTopから参照していくことで構築を行う。 | |
| 11 | 71 また、画像ファイルなどファイルの中身の変更が行われない形式は、ファイル内のデータをブロック長に区切り扱うといった手段が考えられるなど、 |
| 72 ファイルの型に応じてレコードの構造体を任意に構成することができる。 | |
| 9 | 73 |
| 74 \lstinputlisting[label=src:FS, caption=例題のレコードとして使われるFileString構造体]{src/FileString.h} | |
| 7 | 75 |
| 76 | |
| 8 | 77 |
| 78 \section{WordCount例題} | |
| 79 GearsFSのAPIの構成をWordCount例題を通して行う。 | |
| 9 | 80 WordCount例題とは、指定したファイルの中身を読み取り、文字数と行数列、加えて文字列を出力するという例題である。 |
| 11 | 81 この例題により連続したレコードをQueueから順次読みだすreadAPIを構築した。 |
| 8 | 82 コード\ref{src:WcImpl}にCbCで記述した、Unixファイルに対してWordCountを行うプログラムの一部を示す。 |
| 83 | |
| 11 | 84 ファイルとWordCountの接続はUNIXのシェルのようにプログラムの外で行われる。 |
| 85 ファイルは事前にC言語のFILE型構造体を用いて開かれ、行列であるwc\texttt{->}strTableへ内部文字列を行区切りで保存されている。 | |
| 8 | 86 MainからファイルのOpenが完了した後、CodeGear:putStrinに遷移し、strTableから文字列を行ごと呼び出しCountUpへ入力し遷移する。 |
| 87 CodeGear:CountUpにて文字列の出力と文字数を読み取り記録、そしてputStringへ遷移する。 | |
| 88 ファイルの文字列がある間はputStringとCountUpをループし続け、 | |
| 89 putStringはstrTableの中身がなくなった(EOF)ならshowResultへ遷移する形となる。 | |
| 90 図\ref{fig:WordCount}にCGの遷移図を示す。 | |
| 91 このように特定の条件を満たすまであるCodeGear間をループ遷移する構成をGearBoxと名付けている。 | |
| 92 | |
| 93 \lstinputlisting[label=src:WcImpl, caption=Unixファイルに対するWordCount.cbcの一部]{src/WcImpl.cbc} | |
| 94 | |
| 11 | 95 \begin{figure}[h] |
| 8 | 96 \begin{center} |
| 97 \includegraphics[width=150mm]{./images/UnixWC.pdf} | |
| 98 \end{center} | |
| 99 \caption{Unixファイルに対するWordCountのCG遷移} | |
| 100 \label{fig:WordCount} | |
| 101 \end{figure} | |
| 102 | |
| 11 | 103 \section{ChristieAPIによるWordCount} |
| 104 GearsFSはChristieのLocalDataGearManagerとRemoteDataGearManagerによる通信の仕組みを用いてファイルデータの送受信を構成する。これをChristieAPIと呼ぶ。 | |
| 105 ChrstieAPIではファイルをDataGearManagerと見なすことができ、 | |
| 106 Local上にRemote先のファイルのploxyとなるRemoteDGMを作成し、 | |
| 107 これに対しLocalのファイルへの書き込みと同様に操作を行うことで自動的に通信を行ってくれる。 | |
| 8 | 108 |
| 9 | 109 ChiristieのDataGearManagerの仕組みを基準としたChristieAPIによるWordCountの設計を行った。 |
| 8 | 110 図\ref{fig:ChristieAPI}にChristieAPIによるWordCountを示す。 |
| 111 ChristieAPIによるファイルデータ通信は2ペアのLocal/RemoteDGMを通して行われる。 | |
| 9 | 112 RemoteDGMは接続先のノードが持つLocalDGMのプロキシであり、RemoteDGMに対してput操作を行うことで、相手の持つLocalDGMへのデータの送信が行える。 |
| 8 | 113 NodeA側が任意のファイルを開き、ファイル内の行ごとの文字列をデータとしてNodeB側に対応するRemoteDGMにputする。 |
| 11 | 114 NodeB側は自身のLocalDGMからデータを得て、WordCountの処理を行ったのちに |
| 8 | 115 NodeAに対応するRemoteDGMに対してそのデータに対する処理が完了したことを通知するAck(acknowledgement)をputする。 |
| 116 Ackを受け取ったOpen側のノードBは再び続きのファイル内文字列をデータとして送信する。 | |
| 117 ここまでの処理が繰り返され、ファイル内の文字列が全て処理されたら、Open側はEoF(End of File)をCount側に対して通知、 | |
| 118 NodeBは最後にWordCountの結果をRemoteDGMに対してputしOpen側に送信する。 | |
| 119 そして、双方のRemoteDGMを閉じることにより通信を終了させる。 | |
| 120 | |
| 121 図中ではRemoteDGMを複数作成することにより通信のやりとりを行っているが、 | |
| 122 WordCountでない純粋なファイルの送信などの場合、DGMのSocketが持つAckのみでも通信を構成することが可能である。 | |
| 123 そのためデータの一方的な送受信のみならDGMのペアは一つだけでも通信が行うことができる。 | |
| 124 | |
| 125 | |
| 126 | |
| 127 \begin{figure}[h] | |
| 128 \begin{center} | |
| 129 \includegraphics[width=150mm]{./images/wordCountDGM.jpg} | |
| 130 \end{center} | |
| 131 \caption{ChristieAPIによるWordCount} | |
| 132 \label{fig:ChristieAPI} | |
| 133 \end{figure} | |
| 134 | |
| 135 | |
| 136 \section{Socket付きQueue} | |
| 11 | 137 RemoteDGMとLocalDGMの接続の際にはLocalDGMが持つsocketに対してRemoteDGMが接続を行い、Dataの書き込み先のkeyを指定してsocket経由でコマンドとして送信する。 |
| 8 | 138 |
| 11 | 139 socketを所有したQueueによるWordCount例題の記述を行うことでGearsOSにおけるsocketの取り扱いと実用性を検証した。 |
| 140 接続元と接続先のsocketは、Queueの作成時に行われ、 | |
| 141 socketへのアクセスはQueueにCodeGearとして実装を行った。 | |
| 8 | 142 ソースコード\ref{src:LDGMQueue}にLocalDGM側にあたる、Socket付きのQueueのCodeGear:getData部分を示す。 |
| 143 加えてソースコード\ref{src:RDGMQueue}にRemoteDGM側にあたるSocket付きのQueueのCodeGear:sendData部分を示す。 | |
| 11 | 144 CodeGear:getDataではsocketなどによるError発生時やEoFフラグがあるデータを受信した場合の遷移先を指定する必要ある。 |
| 9 | 145 |
| 11 | 146 二つのQueueはmainプログラムによりsocketの接続が行われ、一方が文字列の送信を行い、もう一方がCount処理を行うことによってWordCountが行われる。 |
| 8 | 147 socketはC言語のSocketインターフェースを用いており、 |
| 11 | 148 socketのImplementのコンストラクタにあたるcreateLocalDGMQueueにて呼び出され、 |
| 8 | 149 Implのメンバ変数であるsocketに置かれている。 |
| 9 | 150 ソースコード\ref{src:LDGQh}に受信側となるLocalなQueueのImplementを示す。 |
| 11 | 151 socketはint型で宣言されている。Implで宣言したsocket変数へsocketを保存をすることで、 |
| 152 Implの実装となるプログラム内ならどのCodeGearからでもsocketの参照が行える。 | |
| 9 | 153 |
| 8 | 154 また、既存のQueueから新たなAPIを追加するためにQueueInterfaceを新しく書き換えたcQueue(Communicate Queue)Interfaceを継承している。 |
| 155 Local側のgetDataはAPIとしての呼び出しが可能となっている。socketが受け取ったデータを最終的にdataとしてQueueに対してputを行う。 | |
| 9 | 156 Remote側のsendDataはAPIとしては呼び出しは行えず、putAPIが呼び出されQueueへのput処理が終了した後に遷移され、 |
| 157 putしたDataを接続先のQueueに対して送信する。 | |
| 158 | |
| 159 \lstinputlisting[label=src:LDGQh, caption=LocalDGMQueueのImplement]{src/LocalDGMQueue.h} | |
| 160 | |
| 161 現状ではデータの通信に行われるDataGearは全てのDataGearのUnion(共用体)となるData型を用いている。 | |
| 8 | 162 送信データのサイズをUnion Data型のサイズにしている理由は、sizeof関数で返される値は共用体に含まれる構造体の中で最も大きなメモリサイズを返すためである。 |
| 9 | 163 これによりputされたDataGearの型がどのようなものであれ、受け取り側がDataGearの型を正しく選択している限りはデータの整合性を守ることができる。 |
| 164 しかし、受信側が受け取ったデータレコードの正しい型を把握しているとは限らないため、 | |
| 165 将来的にはmessagePackなどによるシリアライズしたデータを送信する形にする。 | |
| 8 | 166 Socketの処理中に問題が発生した場合はinputDataGearとして指定した\texttt{\_\_}code whenError()として入力されたCodeGearに対して遷移する。 |
| 167 | |
| 168 | |
| 169 \lstinputlisting[label=src:LDGMQueue, caption=LocaDGMQueueのgetData]{src/LocalDGMQueue.cbc} | |
| 170 \lstinputlisting[label=src:RDGMQueue, caption=RemoteDGMQueueのsendData]{src/RemoteDGMQueue.cbc} | |
| 171 | |
| 172 | |
| 173 | |
| 174 \section{GearsOSにおけるDataGearManager} | |
| 175 先で述べたSocket付きのQueueは、DataGearであるQueueとSocketが直接結びついているため、 | |
| 176 一つのDataGearを用いる場合となる最低限の通信しか行えない。 | |
| 9 | 177 複数のDataGear(key)を用いての通信を構成するためには複数のQueueを蓄えることのできるリストを生成し、 |
| 8 | 178 そのリスト自体がsocketを持つ必要がある。 |
| 179 | |
| 180 GearsOSではDataGearを保持するQueueのリストとして赤黒木を用いる。 | |
| 181 赤黒木は平衡二分木であり、木に対する操作時に行われる操作によりノードの階層が平衡化される | |
| 182 そのため各操作の最悪時間計算量O(logN)となり、二分木の中でも実用性を備えている。 | |
| 183 | |
| 11 | 184 DataGearはkeyごとに作られたQueueに保存される、従ってQueueのリストとなる赤黒木にはkeyごとのQueueがノードとして保持される。 |
| 9 | 185 図\ref{fig:GearsDGM}にファイルとなるDataGearManagerの任意のkeyに対してput/take操作を行う際の処理を示す。 |
| 11 | 186 いずれの場合もリストとなる赤黒木に対して任意のkeyのQueueのget操作を行い、そのQueueに対してputもしくはtake操作を行う。 |
| 8 | 187 あくまでこのDGMはファイルに相当するものなので、 |
| 188 赤黒木に含まれているQueueはInput/OutputStreamと実際にファイルデータを保持しておくmainDataQueueの三つとなる。 | |
| 11 | 189 しかしWordCount例題のackや結果出力の通信など用途に用いるDataGearが必要な場合、Streamとなるkey以外を用いるために、 |
| 9 | 190 ファイルに関連するkey以外にも任意にQueueを追加することもできる。 |
| 191 任意のQueueを追加したい場合はstoreとなるTreeに対して、 | |
| 8 | 192 Treeが保持していないkeyへputが行われた場合は新しくそのkeyを持つQueueを生成しTreeに持たせる処理を追加すれば良い。 |
| 193 | |
| 9 | 194 図に示した手順のDataアクセスではファイルの呼び出しなどDataGearの断続的な参照が行われる場合、 |
| 8 | 195 Treeへの探索処理がボトルネックになってしまう可能性が考えられる。 |
| 9 | 196 これは特定のkeyのQueueをmain部分で直接参照できるように、 |
| 11 | 197 TreeにQueue自体のポインタをOutputさせるAPIを実装することで解決が行える。 |
| 8 | 198 |
| 199 \begin{figure}[h] | |
| 200 \begin{center} | |
| 201 \includegraphics[width=180mm]{./images/GearsDGM.pdf} | |
| 202 \end{center} | |
| 203 \caption{GearsOSにおけるファイル(DGM)} | |
| 204 \label{fig:GearsDGM} | |
| 205 \end{figure} | |
| 206 | |
| 207 | |
| 208 | |
| 209 | |
| 210 | |
|
5
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
211 \section{ディレクトリシステム} |
|
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
212 本研究と並行する形で又吉雄斗によるGearsFileSystemのディレクトリ構造の構築が行われている。[論文No.] |
| 11 | 213 GearsFSのディレクトリシステムはUnixOSのディレクトリシステムのinodeの仕組みを用いて再現することを試みている。 |
| 9 | 214 通常のUnixのディレクトリシステムと異なる点として、ディレクトリを赤黒木(RedBlackTree)を用いて構成する。 |
|
5
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
215 |
|
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
216 図\ref{fig:GearsDirectory}にGearsFSの構成図を示す。 |
| 9 | 217 一つのディレクトリは赤黒木を持ち、あるディレクトリの中に位置するファイル(ディレクトリ含む)は親ディレクトリが持つ赤黒木の中にノードとして同等に配置される。 |
| 218 あるディレクトリに存在するファイルを参照する場合は、ディレクトリの持つTreeに対して探索を行えば良い。 | |
|
5
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
219 図の例では/(ルートディレクトリ)からUsersディレクトリ下にあるDadというディレクトリ(もしくはファイル)を参照するには、 |
|
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
220 /のTree内のUsersを探索、続いてUsersTreeの内部のDadを探索する形となる。 |
| 9 | 221 また、親ディレクトリを持つ全てのファイルは、親のディレクトリの情報を保持している。 |
|
5
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
222 |
|
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
223 \begin{figure}[h] |
|
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
224 \begin{center} |
|
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
225 \includegraphics[width=80mm]{./images/GearsDirectory.pdf} |
|
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
226 \end{center} |
|
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
227 \caption{GearsDirectory} |
|
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
228 \label{fig:GearsDirectory} |
|
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
229 \end{figure} |
|
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
230 |
| 7 | 231 GearsのディレクトリシステムはUnixのinodeの仕様を用いる。 |
| 9 | 232 inodeとはファイルごとのユニークな番号(inode番号)。データ領域へのポインタや作成日時、サイズなどのメタデータを保存するための領域である。 |
| 7 | 233 GearsFSの赤黒木を用いたディレクトリシステムに実際に保存されるノードはkeyがFileName、 |
| 234 valueがinodeのペアを保持している。 | |
| 9 | 235 DirectoryTreeをファイル名で探索を行い、任意のファイルのinode番号を手に入れ、DirectroyTreeとは別に実装されたkeyにinode番号、ペアとして |
| 7 | 236 ファイルのポインタを保持させるTreeをinode番号で探索させる形となる。 |
| 237 この形で実装することにより、ファイル自身が所属するDirectoryをinode番号で保持でき、親Directoryが複数存在していたり、 | |
| 238 親DirectoryのFileNameが変更された場合においてもDirectoryの構造の障害が起きない。 | |
| 239 | |
| 240 | |
|
5
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
241 |
|
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
242 \section{GearsFSのバックアップ} |
|
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
243 GearsOSは将来的にOS自体がバックアップの機能を保持する構成を目指している。 |
| 7 | 244 GearsFSのDirectoryのバックアップは木構造の構築を非破壊的に行うことにより過去のデータを保持する。 |
| 245 図\ref{fig:TreeEdit}に非破壊的な木構造の編集を図に示す。 | |
| 246 非破壊的木構造の編集とは編集元のノードのデータや接続を直接書き換えることなく、 | |
| 247 根(ルートノード)から必要なノードは新しく生成し一部のノードは過去のものを使い回すことで更新することを指す。 | |
| 248 図中の右側の編集後の木構造の赤く記されたノードは新規に作成、もしくはコピーされたノードとなる。 | |
| 249 変更されたノードと根から変更ノードまでの道筋のノードは、編集元のノードとは別に新しく作成される。 | |
| 250 それ以外のTreeに属していたノードは編集元のTreeのノードをポインタで接続することで使い回す。 | |
| 251 つまり、図中の黒いノード1から探索を行えば過去のデータのノードが参照でき、 | |
| 252 赤いノード1から探索を行えば編集後の木構造を参照することができる。 | |
|
5
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
253 |
| 7 | 254 ファイル構造体のバックアップについては、ファイルのDataレコードをファイルの変更差分を履歴として保持させる形にすることに加え、 |
| 255 変更日時を保持させることで可能となると考えられる。 | |
| 256 特定の時点のファイルとDirectoryの状態を呼び出す際は、レコードの変更日時を確認し、参照するべきTree構造とレコードを呼び出す形となる。 | |
| 257 | |
| 11 | 258 変更ログデータを定期的に任意または一定期間ごとに別のストレージに保存することでバックアップを実現する。 |
| 259 また、非破壊的木構造の編集と変更履歴式のデータレコードは変更が行われるたびに、ディレクトリTreeやファイルの容量増加していくという問題が存在する。 | |
| 9 | 260 この点については任意の期間経過、もしくはユーザの操作により定期的に過去のデータを自動削除もしくは整形することで容量がある程度の削減が望める。 |
| 261 また、近年の電子記録媒体の容量増加に伴い問題の重要性が低下していくことが期待できる。 | |
| 7 | 262 |
| 263 \begin{figure}[h] | |
| 264 \begin{center} | |
| 265 \includegraphics[width=150mm]{./images/nonDestroyTreeEdit.pdf} | |
| 266 \end{center} | |
| 267 \caption{非破壊的なTree編集} | |
| 268 \label{fig:TreeEdit} | |
| 269 \end{figure} | |
|
5
d8f93db60366
add GearsFile & Directory
ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
270 |
| 11 | 271 |
| 9 | 272 \section{GearsFSの分散処理} |
| 273 分散フレームワークChristieとGearsOSFileSystemにおける分散処理について考察する。 | |
| 274 GearsFSではファイルはDataGearのリストとして実装される。 | |
| 275 ファイルの読み取り書き込みを含めた通信はDataGearリストにある特定のkeyのDataGearのQueueに対してDataを書き込み、 | |
| 276 もしくは呼び出しを行うことで実現される。 | |
| 277 そのためファイルはDataGearManagerであると言える。 | |
| 8 | 278 |
| 9 | 279 GearsFSのファイルはChristieのDataGearManagerの仕組みを参考にするものであるが、ChristieのDGMとの明確な違いとして、 |
| 280 GearsFSのDGMはChristieのようにDataGearの差し込みによる通信を構成するだけの用途でなく、ファイルそのものとしての用途を持つという点が存在する。 | |
| 281 そのため、ChristieDGMのように一つのスレッド(CGM)により管理されるものではなく、複数のスレッドから競合的にアクセスが行われるDGMである。 | |
| 282 よってDataGearを保持するQueueは純粋なQueueでなく複数のアクセスが行われても、 | |
| 283 データの整合性が保たれるSynchronizedなQueueを用いる必要が生じる場面がある。 | |
| 11 | 284 |
| 285 Christieのでは分散されたTask(CodeGear)はCodeGearManagerにより実行が行われる。 | |
| 286 GearsFSでは分散処理をCodeGearManagerを用いた実装に代わり、GearsOSに搭載されたpar gotoを利用するという手段が考えられる。 | |
| 287 par gotoとはGearsOSにおける並列処理構文である。 | |
| 288 par gotoによる並列処理ではTaskをContextで表現し、TaskのInputDataGearが揃ったTaskをWorkerで処理を行う。 | |
| 289 図\ref{fig:WorkerRun}にpar goto構文による並列処理を示す。 | |
| 290 GearsFSではファイル送受信自体をTaskの一つとして実装する他に、 | |
| 291 socketに対してファイルデータの確認と取り出しを行う待ち合わせの処理を一つのTaskとする必要がある。 | |
| 292 | |
| 293 | |
| 294 | |
| 295 \begin{figure}[h] | |
| 296 \begin{center} | |
| 297 \includegraphics[width=170mm]{./images/WorkerRun.pdf} | |
| 298 \end{center} | |
| 299 \caption{par gotoによる並列処理} | |
| 300 \label{fig:WorkerRun} | |
| 301 \end{figure} | |
| 302 | |
| 303 | |
| 304 \section{GearsOSの持続性} |