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