|
0
|
1 %%
|
|
|
2 %% 研究報告用スイッチ
|
|
|
3 %% [techrep]
|
|
|
4 %%
|
|
|
5 %% 欧文表記無しのスイッチ(etitle,eabstractは任意)
|
|
|
6 %% [noauthor]
|
|
|
7 %%
|
|
|
8
|
|
|
9 %\documentclass[submit,techrep]{ipsj}
|
|
|
10 \documentclass[submit,techrep,noauthor]{ipsj}
|
|
|
11
|
|
|
12
|
|
|
13
|
|
|
14 \usepackage[dvips, dvipdfmx]{graphicx}
|
|
|
15 \usepackage{latexsym}
|
|
|
16 \usepackage{listings}
|
|
|
17 \lstset{
|
|
|
18 language=C,
|
|
|
19 tabsize=2,
|
|
|
20 frame=single,
|
|
|
21 basicstyle={\tt\footnotesize}, %
|
|
|
22 identifierstyle={\footnotesize}, %
|
|
|
23 commentstyle={\footnotesize\itshape}, %
|
|
|
24 keywordstyle={\footnotesize\ttfamily}, %
|
|
|
25 ndkeywordstyle={\footnotesize\ttfamily}, %
|
|
|
26 stringstyle={\footnotesize\ttfamily},
|
|
|
27 breaklines=true,
|
|
|
28 captionpos=t,
|
|
|
29 columns=[l]{fullflexible}, %
|
|
|
30 xrightmargin=0zw, %
|
|
|
31 xleftmargin=1zw, %
|
|
|
32 aboveskip=1zw,
|
|
|
33 numberstyle={\scriptsize}, %
|
|
|
34 stepnumber=1,
|
|
|
35 numbersep=0.5zw, %
|
|
|
36 lineskip=-0.5ex
|
|
|
37 }
|
|
|
38 \usepackage{caption}
|
|
|
39
|
|
|
40
|
|
|
41 \def\Underline{\setbox0\hbox\bgroup\let\\\endUnderline}
|
|
|
42 \def\endUnderline{\vphantom{y}\egroup\smash{\underline{\box0}}\\}
|
|
|
43 \def\|{\verb|}
|
|
|
44 %
|
|
|
45
|
|
|
46 %\setcounter{巻数}{59}%vol59=2018
|
|
|
47 %\setcounter{号数}{10}
|
|
|
48 %\setcounter{page}{1}
|
|
|
49 \renewcommand{\lstlistingname}{Code}
|
|
|
50
|
|
|
51 \begin{document}
|
|
|
52
|
|
|
53
|
|
|
54 \title{Gears OSのファイルシステムとDB}
|
|
|
55
|
|
|
56 \affiliate{IPSJ}{情報処理学会\\
|
|
|
57 IPSJ, Chiyoda, Tokyo 101--0062, Japan}
|
|
|
58
|
|
|
59
|
|
|
60 \paffiliate{JU}{琉球大学大学院理工学研究科工学専攻知能情報プログラム\\
|
|
|
61 University of the Ryukyus, Graduate School of Engineering and Science}
|
|
|
62
|
|
|
63 \author{又吉 雄斗}{Matayoshi Yuto}{KIE}[matac@cr.ie.u-ryukyu.ac.jp]
|
|
|
64 \author{佐野 巧曜}{Sano Yoshiaki}{KIE}[yoshisaur@cr.ie.u-ryukyu.ac.jp]
|
|
|
65 \author{河野 真治}{Kono Shinzi}{IE}[kono@ie.u-ryukyu.ac.jp]
|
|
|
66
|
|
|
67 \begin{abstract}
|
|
|
68 当研究室では，Continuation based C（CbC）を用い，定理証明やモデル検査などで信頼性を保証することを目的としたGearsOSを開発している．
|
|
|
69 OSにおいてファイルシステムは重要な機能の一つであるため実装する必要がある．
|
|
|
70 現在，一般的なアプリケーションはファイルシステムとデータベースを併用する形で構成される．
|
|
|
71 DBはSQLによってデータの挿入や変更が可能だがスキーマを事前に定義したり，insert時にそれらのschemaを指定したりする必要がある．
|
|
|
72 GearsOSのファイルシステムではSQLの機能に相当するgrepやfindなどのインターフェースを実装し，
|
|
|
73 アプリケーションのデータベースとしてファイルシステムを使用する構成が取れるようにしたい．
|
|
|
74 ファイルシステムとデータベースの違いについて考え，データベースとしても利用可能なファイルシステムを構築したい．
|
|
|
75 本研究では，ファイルシステムとデータベースの違いについて考察し，Gears OSのファイルシステムの設計について述べる．
|
|
|
76 \end{abstract}
|
|
|
77
|
|
|
78
|
|
|
79 %
|
|
|
80 %\begin{jkeyword}
|
|
|
81 %情報処理学会論文誌ジャーナル，\LaTeX，スタイルファイル，べからず集
|
|
|
82 %\end{jkeyword}
|
|
|
83 %
|
|
|
84 %\begin{eabstract}
|
|
|
85 %This document is a guide to prepare a draft for submitting to IPSJ
|
|
|
86 %Journal, and the final camera-ready manuscript of a paper to appear in
|
|
|
87 %IPSJ Journal, using {\LaTeX} and special style files. Since this
|
|
|
88 %document itself is produced with the style files, it will help you to
|
|
|
89 %refer its source file which is distributed with the style files.
|
|
|
90 %\end{eabstract}
|
|
|
91 %
|
|
|
92 %\begin{ekeyword}
|
|
|
93 %IPSJ Journal, \LaTeX, style files, ``Dos and Dont's'' list
|
|
|
94 %\end{ekeyword}
|
|
|
95
|
|
|
96 \maketitle
|
|
|
97
|
|
|
98 %1
|
|
|
99 \section{GearsOSにおけるファイルシステム}
|
|
|
100
|
|
|
101 アプリケーションの信頼性を保証することは
|
|
|
102 情報システムやコンピュータを用いる業務の信頼性の保障につながる重要な課題である．
|
|
|
103 したがって，アプリケーションの信頼性を保証するために，基盤となるOSの信頼性を高める必要がある．
|
|
|
104
|
|
|
105 当研究室では，信頼性の保証を目的としたGearsOSを開発している．
|
|
|
106 GearsOSは，OSの信頼性を定理証明やモデル検査を行うことで保証することを目指している\cite{modelcheck}．
|
|
|
107 同じく，当研究室で開発しているプログラム言語であるCbC（Continuation based C）で記述されており，
|
|
|
108 ノーマルレベルとメタレベルを簡単に切り分けることを可能としている．
|
|
|
109 そのようにして，CbCでメタレベルの処理を切り出したものに対して，定理証明やモデル検査を行うことで信頼性を保証する．
|
|
|
110
|
|
|
111 GearsOSは現在OSとして重要な機能がいくつか未実装であり，その一つとしてファイルシステムが挙げられる．
|
|
|
112 ファイルシステムはファイルやディレクトリといった構造を持ち，データの保存，整理を行う．
|
|
|
113 また，OSが管理するデータの操作を人間が行いやすいようにインターフェースを提供する．
|
|
|
114 OSの機能の中でも特に重要な機能であるため，GearsOSにも実装を行う必要がある．
|
|
|
115
|
|
5
|
116 今回GearsOSへファイルシステムを実装するにあたり，
|
|
0
|
117
|
|
|
118 \section{Continuation based C}
|
|
|
119
|
|
|
120 Continuation based C（CbC）\cite{cbcllvm,cbc}は，当研究室で開発しているCの下位言語である．
|
|
|
121 CbCでは関数の代わりにCodeGearという単位でプログラミングを行う．
|
|
|
122 CodeGearは\emph{\_\_code}という記述で宣言することができる．
|
|
|
123 また，データの単位にはDataGearと呼ばれる変数データを用いる．
|
|
|
124 図\ref{fig:dgcg}はCodeGearと入出力の関係を表している．
|
|
|
125 CodeGearはDataGearを入力として受け取り，別のDataGearに書き込み出力することができる．
|
|
|
126 特に，入力のDataGearをInput DataGear，出力のDataGearをOutput DataGearと呼ぶ．
|
|
|
127 gotoで次のCodeGearに遷移することができ，その際，Output DataGearを次のCodeGearのInput DataGearとして渡すことができる．
|
|
|
128
|
|
|
129 \begin{figure}[ht]
|
|
|
130 \begin{center}
|
|
|
131 \includegraphics[width=80mm]{figs/cgdg.pdf}
|
|
|
132 \end{center}
|
|
|
133 \caption{CodeGearと入出力の関係図}
|
|
|
134 \label{fig:dgcg}
|
|
|
135 \end{figure}
|
|
|
136
|
|
|
137 CodeGearから次のCodeGearに遷移していく一連の動作を継続と呼ぶ．
|
|
|
138 通常の関数の場合，関数から次の関数へ遷移する時にfunction callが行われる．
|
|
|
139 function callは前の関数へ戻る場合があり，そのためにcall stackを保存する．
|
|
|
140 他方，CbCの継続はfunction callをせずにgotoによるjmpで行われる．
|
|
|
141 jmpはfunction callと異なり，call stackのような環境を保存しない．
|
|
|
142 よって，CbCのgotoによる継続はfunction callによる継続と比較して軽量であるといえる．
|
|
|
143 そのことから，CbCにおける継続をfunction callによる継続と区別して，軽量継続と呼ぶ．
|
|
|
144 これらの仕組みにより，ノーマルレベルとメタレベルの処理を容易に切り分けることが可能となる．
|
|
|
145
|
|
|
146 CbCのプログラム例をソースコード\ref{src:cbc}に示す．
|
|
|
147 まずmain関数においてadd1 CodeGearへgotoを行う．
|
|
|
148 その際add1へInput DataGearとしてnを渡す．
|
|
|
149 Cのgotoが\emph{goto label;}という記法で，ラベリングした箇所へjmpを行うのに対し，
|
|
|
150 CbCのgotoは\emph{goto add1(n);}という記法で，add1 CodeGearへn DataGearを渡してjmpを行う．
|
|
|
151 add1は処理の最後にadd2 CodeGearへgotoを行う．
|
|
|
152 その際Output DataGear out\_nをadd2のInput DataGearとして渡す．
|
|
|
153 このようにCbCではCodeGearのOutput DataGearを次のCodeGearのInput DataGearとして渡すことを繰り返すことで処理を進める．
|
|
|
154
|
|
|
155 \lstinputlisting[caption=CbCのプログラム例,label=src:cbc]{src/hello.cbc}
|
|
|
156
|
|
1
|
157 \section{信頼性の保証を目的としたGearsOS}
|
|
0
|
158
|
|
|
159 GearsOS\cite{gears,gearsos,cr}は当研究室で開発している，信頼性と拡張性の両立を目的としたOSである．
|
|
|
160 GearsOSにはGearという概念があり，実行の単位をCodeGear，データの単位をDataGearと呼ぶ．
|
|
|
161 軽量継続を基本とし，stackを持たない代わりに全てをContext経由で実行する．
|
|
|
162 同様にGearの概念を持つContinuation based C（CbC）で記述されており，ノーマルレベルとメタレベルの処理を切り分けることが容易である．
|
|
|
163 また，GearsOSは現在開発途上であり，OSとして動作するために今後実装しなければならない機能がいくつか残っている．
|
|
|
164
|
|
9
|
165 GearsOSには現在3つの種類がある．
|
|
|
166 1つ目が型式手法による信頼性の向上を目的とした，GearsAgdaと呼ばれるGearsOSである．
|
|
10
|
167 これは，Agdaによって実装されている．
|
|
|
168 2つ目がユーザーレベルタスクマネジメントの実装を目的としたGearsOSがある．
|
|
|
169 これは，CbCによって実装されている．
|
|
|
170 3つ目はスタンドアロンOSの開発を目的とした，CbC\_xv6と呼ばれるGearsOSがある．
|
|
|
171 これは，教育用に開発されたx.v6 OSをCbCで書き換える形で実装している．
|
|
|
172 今回，ファイルシステムを実装する対象は3つ目のCbC\_xv6である．
|
|
9
|
173
|
|
0
|
174 ContextはGearsOS上全てのCodeGear，DataGearの参照を持ち，CodeGearとDataGearの接続に用いられる．
|
|
|
175 OS上の処理の実行単位で，従来のOSにおけるプロセスに相当する機能であるといえる．
|
|
|
176 また，CodeGearをDataGearの一種であると考えると，ContextはGearの概念ではMetaDataGearに当たる．
|
|
|
177 Contextはノーマルレベルから直接参照されず，必ずMetaDataGearとしてMetaCodeGearから参照される．
|
|
|
178 それは，ノーマルレベルのCodeGearがContextを直接参照してしまうと，
|
|
|
179 メタレベルを切り分けた意味がなくなってしまうためである．
|
|
|
180
|
|
|
181 図\ref{fig:context}はContextを参照する流れを表したものである．
|
|
|
182 まずCodeGearがOutputDataGearへデータをoutputする．
|
|
|
183 stubCodeGearはInputDataGear（前のCodeGearのOutputDataGear）とOutputDataGearをContextから参照し，次のCodeGearへgotoを行う．
|
|
|
184 CodeGearでの処理後，OutputDataGearへデータをoutputする．
|
|
|
185
|
|
|
186 Contextはいくつかの種類に分けることができる．
|
|
|
187 OS全体のContextを管理するKernel Contextやユーザープログラムごとに存在するUser Context，
|
|
|
188 CPUやGPUごとに存在するCPU Contextがある．
|
|
|
189 \begin{figure}[ht]
|
|
|
190 \begin{center}
|
|
|
191 \includegraphics[width=80mm]{figs/context.pdf}
|
|
|
192 \end{center}
|
|
|
193 \caption{Contextを参照する流れ}
|
|
|
194 \label{fig:context}
|
|
|
195 \end{figure}
|
|
|
196
|
|
|
197 図\ref{fig:meta-cgdg}はCodeGearの遷移とMetaCodeGearの関係を表している．
|
|
|
198 OSのプログラムはユーザーが実際に行いたい処理を表現するノーマルレベルと，
|
|
|
199 カーネルが行う処理を表現するメタレベルが存在する．
|
|
|
200 ノーマルレベルで見るとCodeGearがDataGearを受け取り，
|
|
|
201 処理後にDataGearを次のCodeGearに渡すという動作をしているように見える．
|
|
|
202 しかしながら，実際にはデータの整合性の確認や資源管理などのメタレベルの処理が存在し，
|
|
|
203 それらの計算はMetaCodeGearで行われる．
|
|
|
204 その際，MetaCodeGearに渡されるDataGearのことは特にMetaDataGearと呼ばれる．
|
|
|
205 また，CodeGearの前に実行されるMetaCodeGearは特にstubCodeGearと呼ばれ，
|
|
|
206 メタレベルを含めるとstubCodeGearとCodeGearを交互に実行する形で遷移していく．
|
|
|
207 \begin{figure}[ht]
|
|
|
208 \begin{center}
|
|
|
209 \includegraphics[width=80mm]{figs/meta-cg-dg.pdf}
|
|
|
210 \end{center}
|
|
|
211 \caption{CodeGearとMetaCodeGearの関係}
|
|
|
212 \label{fig:meta-cgdg}
|
|
|
213 \end{figure}
|
|
|
214
|
|
1
|
215 \section{RedBlackTreeよるファイルシステムの構成}
|
|
0
|
216
|
|
1
|
217 ファイルシステムは全てRedBlackTreeで構成する．
|
|
|
218 それにより，プログラムの証明がより簡単になるからである．
|
|
|
219 また，ファイルシステムとDBはデータを保管するという本質的な役割は同じである．
|
|
|
220 よって，それらをまとめてRedBlackTreeで構成する．
|
|
0
|
221
|
|
1
|
222 ファイルシステムとDBの違いとして，スキーマが挙げられる．
|
|
|
223 DBは事前にスキーマを定義し，それに沿ってデータを挿入したり参照したりする．
|
|
|
224 対して，ファイルシステムにはスキーマに当たるものがなく，
|
|
|
225 データはファイルパスによって管理される．
|
|
2
|
226 スキーマを定義することによってデータは構造化され，
|
|
|
227 構造化されたデータは非構造化データと比較して，
|
|
|
228 インデックスを作成することが容易であり，データの検索性が向上する利点がある．
|
|
1
|
229 しかしながら，スキーマはDBの運用中に変更されることがあり，
|
|
|
230 スキーマを変更した以前へロールバックができない問題がある．
|
|
0
|
231
|
|
1
|
232 ロールバックがスキーマの変更によって出来なくなることは信頼性に問題があると考えると，
|
|
|
233 スキーマを定義する必要のないスキーマレスなDBが必要になる．
|
|
|
234 ファイルシステムはスキーマレスなDBといえるので，ファイルシステムを構築しつつ
|
|
|
235 DBがスキーマによって実現していた機能を付け加えることを試みる．
|
|
0
|
236
|
|
1
|
237 RedBlackTreeは実装によって，操作が破壊的なものとそうでないものがある．
|
|
|
238 今回用いるのは，非破壊的な実装のRedBlackTreeである．
|
|
3
|
239 図\ref{fig:TreeEdit}は非破壊的編集を行うRedBlackTreeを表している．
|
|
|
240 編集前の木構造の6のノードをAにアップデートすることを考える．
|
|
|
241 まず，ルートノードからアップデートしたいノード6までをコピーする．
|
|
|
242 その後，コピーしたもののノード6をAにアップデートする．
|
|
|
243 これにより，アップデート前のノード6を破壊することなくAにアップデートが可能である．
|
|
|
244 参照する時は，黒のルートノードから辿れば古い6が，赤のルートノードから辿れば新しいAが見える．
|
|
|
245 この仕組みは，データのバックアップやDBのロールバックに用いることが可能だと考える．
|
|
|
246
|
|
|
247 \begin{figure}[ht]
|
|
|
248 \begin{center}
|
|
|
249 \includegraphics[width=80mm]{figs/nonDestroyTreeEdit.pdf}
|
|
|
250 \end{center}
|
|
|
251 \caption{非破壊的なTree編集}
|
|
|
252 \label{fig:TreeEdit}
|
|
|
253 \end{figure}
|
|
|
254
|
|
0
|
255
|
|
1
|
256 \section{ディスク上とメモリ上のデータ構造}
|
|
0
|
257
|
|
1
|
258 ディスク上とメモリ上でデータの構造は，RedBlackTreeに統一する．
|
|
|
259 一般的に，ディスク上のデータ構造としてB-Treeが用いられることが多い．
|
|
|
260 なぜならば，HDDを用いる場合はブロックへのアクセス回数を減らしデータアクセスの時間を短くするために，
|
|
|
261 B-Treeのようなノードを複数持つことができる構造が効果的だからである．
|
|
|
262 その点ではRedBlackTreeはB-Treeに劣る．
|
|
|
263 しかしながら，SSDはランダムアクセスによってデータにアクセスするため，
|
|
|
264 RedBlackTreeでなくB-Treeを用いる利点は少ないと考える．
|
|
|
265 よって，ディスク上とメモリ上のデータ構造をRedBlackTreeに統一することが考えられる．
|
|
|
266 そうすることによって，ディスク上とメモリ上のデータのやりとりは単純なコピーで実装できる．
|
|
0
|
267
|
|
4
|
268 % メモリからディスクに書き戻すタイミングの話をしたい
|
|
|
269
|
|
|
270 \section{データのロールバックとバックアップ}
|
|
|
271
|
|
|
272 DBの重要な機能の一つにロールバックがある．
|
|
|
273 RDBのロールバックは，
|
|
|
274 コミットするまではトランザクションの開始時点に戻ることができる機能である．
|
|
|
275 コミットが完了するとそれ以前の状態に戻すことはできないが，
|
|
|
276 データのバックアップをとっておくことで復元を行う．
|
|
|
277 このような，ロールバックとバックアップの仕組みをファイルシステムに実装したい．
|
|
|
278
|
|
|
279 今回は，RedBlackTreeのルートノードがデータのバージョンの役割を果たしていることを利用し，
|
|
|
280 データの復元が行える仕組みを構築することを考える．
|
|
|
281 非破壊的なTree編集はアップデートのたびに，ルートノードを増やす．
|
|
|
282 つまり，ルートノードはアップデートのログと言えその時点のデータのバージョンを表していると考えることができる．
|
|
|
283 よって，ロールバックを行いたい場合は参照を過去のルートノードに切り替える．
|
|
2
|
284
|
|
4
|
285 ルートノードはデータのアップデート時に増えるため，
|
|
|
286 データが際限なく増加していく問題がある．
|
|
|
287 この問題はCopyingGCを行うことによって解決する．
|
|
|
288 まず，RedBlackTreeを丸ごとコピーして最新のルートを残して他のルートは削除する．
|
|
|
289 その後，コピーしたものはバックアップとしてディスクに書き込む．
|
|
|
290 そうすることで，データの増加によるリソースの枯渇を防ぎ，
|
|
|
291 かつデータのバックアップを作成することで信頼性の向上が期待できる．
|
|
|
292
|
|
|
293
|
|
11
|
294 \section{RedBlackTreeのトランザクション}
|
|
|
295
|
|
|
296 トランザクションはDBの重要な機能の一つである．
|
|
|
297 データの競合を防ぎ信頼性を向上させ，DBとしても扱えるよう
|
|
|
298 トランザクションの仕組みを考える必要がある．
|
|
|
299 今回，ファイルシステムは全てRedBlackTreeで実装するため，
|
|
|
300 RedBlackTreeのノードに対するトランザクションを考える．
|
|
6
|
301
|
|
11
|
302 トランザクションをwriteとreadに分けて考える．
|
|
|
303 writeする場合，トランザクションはRedBlackTreeのルートの置き換えと対応する．
|
|
|
304 writeするために，まずルートを生やし書き込みが終わった後ルートを置き換える．
|
|
|
305 そのため，書き込みの並列度はルートの数と一致する．
|
|
|
306 しかしながら，ルートの置き換えは競合的なので，
|
|
|
307 複数書き込みを行っても1つしか成功しない．
|
|
|
308 よって，単一のRedBlackTreeに複数の書き込みポイントを作り，
|
|
|
309 並行実行可能にする必要がある．
|
|
4
|
310
|
|
11
|
311 RedBlackTreeに複数の書き込みポイントを作るために，
|
|
|
312 キーごとのルートを作成する．
|
|
|
313 ノードはそれぞれがキーとRedBlackTreeを持つ状態になる．
|
|
|
314 writeする際は，そのキーのルートを置き換える．
|
|
|
315 それによって，RedBlackTreeは複数の書き込みポイントを持つことができ，
|
|
|
316 writeを並行実行することが可能となる．
|
|
|
317
|
|
|
318 readはデータに変更を加えないため，複数同時に同じノードを読み込むことが可能である．
|
|
|
319 しかし，常に最新の情報を読み込めるとは限らない．
|
|
|
320 最新の情報が欲しい場合は書き込みを一旦止めるような処理が必要になる．
|
|
|
321
|
|
6
|
322
|
|
|
323 \section{スキーマレスな実装}
|
|
4
|
324
|
|
6
|
325 従来のSQLのようなスキーマの定義が存在すると，
|
|
|
326 個別にバックアップなどを取らない限り
|
|
|
327 スキーマの変更以前にロールバックすることができない．
|
|
|
328 しかしながら，実際運用する上でスキーマを変更することは多々ある．
|
|
7
|
329 これは，データの信頼性を低下させると考える．
|
|
6
|
330 また，DB上のデータ構造とプログラム上で扱うデータ構造に差が生まれる
|
|
|
331 インピーダンスミスマッチが発生し，DBのデータをプログラムが扱う際に
|
|
|
332 その差を埋めるような変換を必要とする場合が生まれる．
|
|
8
|
333 一方で，スキーマがあることによってデータに対して高度な操作を行なったり，
|
|
|
334 インデックスを容易に作成することができたりするといったメリットがある．
|
|
|
335 よって，スキーマフルなDBとスキーマレスなDBはそれぞれメリットデメリットがあり，
|
|
|
336 状況によって使い分けるのが良いと考えるが，
|
|
|
337 非構造化データ内であれば構造化データを扱うことが可能であることと，
|
|
|
338 信頼性を保証したいという点から今回は，
|
|
|
339 スキーマレスなDBとしてのファイルシステムを実装することを考える．
|
|
6
|
340
|
|
|
341
|
|
7
|
342
|
|
3
|
343 \section{インデックス}
|
|
|
344 \section{今後の課題}
|
|
|
345 \section{まとめ}
|
|
2
|
346
|
|
0
|
347 \nocite{*}
|
|
|
348 \bibliographystyle{ipsjunsrt}
|
|
|
349 \bibliography{matac-bib}
|
|
|
350
|
|
|
351 \end{document}
|
