\documentclass[12pt,a4paper,platex]{jreport} 
\usepackage{master_paper}
\usepackage{ascmac}
\usepackage[dvipdfmx]{graphicx}
\usepackage{here}
\usepackage{listings}
\usepackage{comment}
\usepackage{url}
\usepackage[deluxe, multi]{otf}



%\input{dummy.tex} %% font


\jtitle{GearsOSのファイルシステムにおけるGCとレプリケーション}
\etitle{GC and Replication in the File System of GearsOS}
\year{2024年 3月}
\eyear{March 2024}
\author{又吉 雄斗}
\eauthor{Matayoshi Yuto}
\chife{指導教員：教授 和田 知久}
\echife{Supervisor: Prof. Wada Tomohisa}

\marklefthead{% 左上に挿入
  \begin{minipage}[b]{.4\textwidth}
    琉球大学大学院学位論文(修士)
\end{minipage}}

% \markleftfoot{% 左下に挿入
%  \begin{minipage}{.8\textwidth}
%    Gears OS の Paging
% \end{minipage}}

\newcommand\figref[1]{図 \ref{fig:#1}}
\newcommand\coderef[1]{ソースコード \ref{code:#1}}

\lstset{
  frame=single,
  keepspaces=true,
  stringstyle={\ttfamily},
  commentstyle={\ttfamily},
  identifierstyle={\ttfamily},
  keywordstyle={\ttfamily},
  basicstyle={\ttfamily},
  breaklines=true,
  xleftmargin=0zw,
  xrightmargin=0zw,
  framerule=.2pt,
  columns=[l]{fullflexible},
  numbers=left,
  stepnumber=1,
  numberstyle={\scriptsize},
  numbersep=1em,
  language={},
  tabsize=4,
  lineskip=-0.5zw,
  escapechar={@},
}
\def\lstlistingname{ソースコード}
\def\lstlistlistingname{ソースコード目次}

%%% 索引のために以下の2行を追加
\usepackage{makeidx,multicol}
\makeindex
\begin{document}
%rome
\maketitle

\pagenumbering{roman}
\setcounter{page}{0}
\newpage
\makecommission
%\input{chapter/signature.tex}

\newpage

%要旨
\input{chapter/abstract.tex}

\mainmatter
%目次
\tableofcontents

%図目次
\listoffigures



%リスト目次
% \lstlistoflistings

%chapters

\chapter{GearsOSにおけるファイルシステムとDB}



情報システムの信頼性を確保することは重要な課題である．
2023年には銀行システムや航空機の旅客システム，
電子決済システムなどで障害が発生した\cite{zengin,ana,glory}．
信頼性の高いシステムを構築することは，
これらのような社会的影響のあるシステムの重大な障害発生防止につながり，
サービス提供者や受容者の機会的，経済的損失を防ぐことにつながる．
情報システムはアプリケーション，OS，DB，メモリやSSDなどのハードウェア，
分散ノードやネットワークなどさまざまな要素で構成される．
それらのうちどれか1つでも信頼性を損なうと，
システム全体の信頼性の低下につながる．
情報システム全体の信頼性を確保するためには，
これらの要素それぞれにおいて，信頼性を保証する必要がある．

当研究室では，信頼性の保証を目的としたGearsOSを開発している．
GearsOSは，定理証明やモデル検査などの形式手法を用いて信頼性を保証できることを目標としている．\cite{modelcheck}．
一般的に信頼性を保証する手法としてテストコードを用いることが挙げられる．
しかしながら，OSなどの大規模なソフトウェアにおいて人力で記述するテストコードのみでは
カバレッジが不十分であり，検証漏れが発生する可能性がある．
GearsOSではテストコードに加え，形式手法を用いることでより高い信頼性の保証を目指している．
GearsOSは当研究室で開発しているプログラム言語であるContinuation based C(CbC)で記述されており，
ノーマルレベルとメタレベルを容易に切り分けることを可能とする拡張性を有す．
CbCによって本来行いたい処理をノーマルレベルで記述し，
信頼性を保証するための処理をメタレベルで記述するといった書き分け，
拡張を比較的容易に可能とする．

OSの重要な機能の1つとしてファイルシステムが挙げられる．
ファイルシステムはOSのプロセスやユーザーデータの管理などに必要不可欠であるため，
GearsOSにおいても実装をする必要があると考えられ，
当研究室では分散ファイルシステムやi-nodeを用いたファイルシステムの設計がされてきた\cite{cfile, directory}．

ファイルシステムには可変長の文字列を格納するファイルと，
そのファイルにアクセスするための名前管理の機能がある．
ファイルの名前の一貫性は名前管理によって保証される．
しかし，ファイルに同時に書き込まれた際の一貫性を保証する機能を
ファイルシステムとしては持っておらず，
ファイルの書き込みを制御するロック機構をアプリケーションが持つことによって，
ファイルの一貫性を保証している．ファイルシステムによく似たものとしてDBが挙げられる．
DBは入力の属性名と型の組み合わせを複数持つレコードと，
特定の属性をキーとしたテーブルがある．
また，レコードのinsert，delete，updateの直列化可能性を保証する機能を持つ．
ファイルシステムとDBは格納するものの形式やそれにアクセスする方法，
直列化可能性を保証する手法が異なるが，
データをある形式で保持する仕組みであるという本質的な部分において違いはない．
よって，ファイルシステムとDBを同一のシステムとして実装することが可能であると考える．

データのレプリケーションやガベージコレクションの仕組みに必要である，
RedBlackTreeのCopyの仕組みを実装した．




\chapter{軽量継続を基本とする言語CbC}

Continuation based C(CbC)\cite{cbcllvm,cbc}はC言語の下位言語であり，
関数呼び出しを行わない軽量な継続を基本とするプログラミング言語である．
CbCは処理の単位のCodeGear，データの単位のDataGearといったGearの概念をもつ．
CodeGearはC言語などにおける関数と違い，gotoによるjmp命令が用いられ，
プログラムの継続においてコールスタックを持たない．
これを通常の関数による継続と区別して，軽量継続と呼ぶ．
軽量継続によってリフレクションのような処理の挿入や切り分けを容易にしている．

\section{Gearの概念}

CbCには処理の単位のCodeGearとデータの単位であるDataGearという概念が存在する．
CodeGearは\emph{\_\_code}という記述で宣言することができる．
CbCはC言語の下位言語であるため，通常の関数も使用することは可能だが，
基本的にCodeGearの単位でプログラミングを行う．
DataGearはCodeGearで入出力される変数データである．
図\ref{fig:dgcg}はCodeGearとDataGearの入出力の関係を表している．
CodeGearはDataGearを複数入力として受け取ることができ，
別のDataGearに複数書き込み出力することができる．
特に，入力のDataGearをInput DataGear，出力のDataGearをOutput DataGearと呼ぶ．
gotoで次のCodeGearに遷移する際，Output DataGearを次のCodeGearのInput DataGearとして渡すことができる．

\begin{figure}[ht]
  \begin{center}
      \includegraphics[width=100mm]{fig/cgdg.pdf}
  \end{center}
  \caption{CodeGearと入出力の関係図}
  \label{fig:dgcg}
\end{figure}

\section{gotoによる軽量継続}

CodeGearから次のCodeGearに遷移していく一連の動作を継続と呼ぶ．
通常の関数の場合，関数から次の関数へ遷移する時にfunction callが行われる．
function callは前の関数へ戻る場合があり，そのためにcall stackを保存する．
他方，CbCの継続はfunction callをせずにgotoによるjmpで行われる．
jmpはfunction callと異なり，call stackによる変数などの環境を保存しない．
よって，CbCのgotoによる継続はfunction callによる継続と比較して軽量であるといえる．
そのことから，CbCにおける継続をfunction callによる継続と区別して，軽量継続と呼ぶ．
軽量継続の利点としてリフレクションのような処理をより柔軟に行える点が挙げられる．
リフレクションはプログラム自身のメタデータを分析し，
それによってプログラムを実行時に書き換える一種のメタプログラミング手法である．
一般的にクラスやメソッド，関数の単位で書き換えが行われる．
手法の例としてJavaにおけるAspectJライブラリを用いたプログラミングが挙げられる．
軽量継続の場合，CodeGear遷移のどの地点においてもメタな処理を挿入することが可能であるため，
より柔軟なリフレクションが可能と考える。


\section{CodeGearの記述例}

CbCのプログラム例をソースコード\ref{src:cbc}に示す．
まずmain関数においてadd1 CodeGearへgotoを行う．
その際add1へInput DataGearとしてnを渡す．
Cのgotoが\emph{goto label;}という記法で，ラベリングした箇所へjmpを行うのに対し，
CbCのgotoは\emph{goto add1(n);}という記法で，add1 CodeGearへn DataGearを渡してjmpを行う．
add1は処理の最後にadd2 CodeGearへgotoを行う．
その際Output DataGear out\_nをadd2のInput DataGearとして渡す．
このようにCbCではCodeGearのOutput DataGearを次のCodeGearのInput DataGearとして渡すことを繰り返すことで処理を進める．

\lstinputlisting[caption=CbCのプログラム例,label=src:cbc]{src/hello.cbc}

\chapter{信頼性の保証を目的としたGearsOS}

GearsOS\cite{gears,gearsos,cr}は当研究室で開発している，信頼性と拡張性の両立を目的としたOSである．
GearsOSにはGearという概念があり，実行の単位をCodeGear，データの単位をDataGearと呼ぶ．
軽量継続を基本とし，stackを持たない代わりに全てをContext経由で実行する．
同様にGearの概念を持つContinuation based C（CbC）で記述されており，ノーマルレベルとメタレベルの処理を切り分けることが容易である．
また，GearsOSは現在開発途上であり，OSとして動作するために今後実装しなければならない機能がいくつか残っている．

\section{3種類のGearsOS}

GearsOSには現在3つの種類がある．
1つ目が形式手法による信頼性の向上を目的とした，GearsAgdaと呼ばれるGearsOSである\cite{gearsagda}．
これは，Agdaによって実装されており，
森 逸汰によるGearsAgdaによるRed Black Treeの検証などの取り組みがされている\cite{garbtree}．
2つ目はスタンドアロンOSの開発を目的とした，CbC\_xv6と呼ばれるGearsOSがある\cite{cbcxv6}．
これは，教育用に開発されたx.v6\cite{xv6}をCbCで書き換える形で実装している．
CbC\_xv6では仲吉 菜々子によるGears OSのCodeGear Managementの取り組みがされている\cite{gearscodemngment}．
3つ目はユーザーレベルタスクマネジメントの実装を目的としたGearsOSがある．
これは，CbCによって実装されており，
分散ファイルシステムの設計やRedBlackTreeでのディレクトリシステムの構築などの取り組みがされている\cite{cfile, directory}．

本研究では，CbCによって実装されたユーザーレベルタスクマネジメント実装のGearsOSを対象に
ファイルシステムのレプリケーションやGC機能の実装を考える．
以下，GearsOSはユーザーレベルタスクマネジメント実装のGearsOSを指す．

\section{メタ処理を記述するmetaGear}

図\ref{fig:meta-cgdg}はCodeGearの遷移とMetaCodeGearの関係を表している．
OSのプログラムはユーザーが実際に行いたい処理を表現するノーマルレベルと，
カーネルが行う処理を表現するメタレベルが存在する．
ノーマルレベルで見るとCodeGearがDataGearを受け取り，
処理後にDataGearを次のCodeGearに渡すという動作をしているように見える．
しかしながら，実際にはデータの整合性の確認や資源管理などのメタレベルの処理が存在し，
それらの計算はMetaCodeGearで行われる．
その際，MetaCodeGearに渡されるDataGearのことは特にMetaDataGearと呼ばれる．
また，CodeGearの前に実行されるMetaCodeGearは特にstubCodeGearと呼ばれ，
メタレベルを含めるとstubCodeGearとCodeGearを交互に実行する形で遷移していく．

\begin{figure}[ht]
  \begin{center}
      \includegraphics[width=160mm]{fig/meta-cg-dg.pdf}
  \end{center}
  \caption{CodeGearとMetaCodeGearの関係}
  \label{fig:meta-cgdg}
\end{figure}

\section{CodeGearの遷移}


\section{全てのGearを参照するContext}

ContextはGearsOS上全てのCodeGear，DataGearの参照を持ち，CodeGearとDataGearの接続に用いられる．
OS上の処理の実行単位で，従来のOSにおけるプロセスに相当する機能であるといえる．
また，CodeGearをDataGearの一種であると考えると，ContextはGearの概念ではMetaDataGearに当たる．
Contextはノーマルレベルから直接参照されず，必ずMetaDataGearとしてMetaCodeGearから参照される．
それは，ノーマルレベルのCodeGearがContextを直接参照してしまうと，
メタレベルを切り分けた意味がなくなってしまうためである．

図\ref{fig:context}はContextを参照する流れを表したものである．
まずCodeGearがOutputDataGearへデータをoutputする．
stubCodeGearはInputDataGear（前のCodeGearのOutputDataGear）とOutputDataGearをContextから参照し，次のCodeGearへgotoを行う．
CodeGearでの処理後，OutputDataGearへデータをoutputする．

Contextはいくつかの種類に分けることができる．
OS全体のContextを管理するKernel Contextやユーザープログラムごとに存在するUser Context，
CPUやGPUごとに存在するCPU Contextがある．

\begin{figure}[ht]
  \begin{center}
      \includegraphics[width=150mm]{fig/context.pdf}
  \end{center}
  \caption{Contextを参照する流れ}
  \label{fig:context}
\end{figure}

\section{GearsOSの記述例}
\section{GearsOSの現状}

\chapter{GearsOSのファイルシステム}
\section{DataGearManagerによる分散ファイルシステム}
\section{i-nodeを用いたファイルシステム}
\section{非破壊RedBlackTreeによる構成}

ディスク上とメモリ上でデータの構造は，RedBlackTreeに統一する．
一般的に，ディスク上のデータ構造としてB-Treeが用いられることが多い．
なぜならば，HDDを用いる場合はブロックへのアクセス回数を減らしデータアクセスの時間を短くするために，
B-Treeのようなノードを複数持つことができる構造が効果的だからである．
その点ではRedBlackTreeはB-Treeに劣る．
しかしながら，SSDはランダムアクセスによってデータにアクセスするため，
RedBlackTreeでなくB-Treeを用いる利点は少ないと考える．
よって，ディスク上とメモリ上のデータ構造をRedBlackTreeに統一することが考えられる．
そうすることによって，ディスク上とメモリ上のデータのやりとりは単純なコピーで実装できる．

\section{RedBlackTreeのトランザクション}

トランザクションはDBの重要な機能の一つである．
データの競合を防ぎ信頼性を向上させ，DBとしても扱えるよう
トランザクションの仕組みを考える必要がある．
今回，ファイルシステムは全てRedBlackTreeで実装するため，
RedBlackTreeのノードに対するトランザクションを考える．

トランザクションをwriteとreadに分けて考える．
writeする場合，トランザクションはRedBlackTreeのルートの置き換えと対応する．
writeするために，まずルートを生やし書き込みが終わった後ルートを置き換える．
そのため，書き込みの並列度はルートの数と一致する．
しかしながら，ルートの置き換えは競合的なので，
複数プロセスから同時に書き込みを行っても1つしか成功しない．
よって，単一のRedBlackTreeに複数の書き込みポイントを作り，
並行実行可能にする必要がある．

% TODO: writeトランザクションの図を入れたい

RedBlackTreeに複数の書き込みポイントを作るために，
キーごとのルートを作成する．
ノードはそれぞれがキーとRedBlackTreeを持つ状態になる．
writeする際は，そのキーのルートを置き換える．
それによって，RedBlackTreeは複数の書き込みポイントを持つことができ，
writeを並行実行することが可能となる．

図\ref{fig:Transaction}にトランザクショナルなwrite操作を表す．
Aの木はファイルシステム全体を表すRedBlackTreeである．
ノードNのデータに対して書き込みすることを考えると，
キーがaであるBの木のルートからロックしCの木を作成して，
Bの木からCの木のルートに入れ替えることで書き込みを行う．
この書き込みを行っている際，
Aの木のノードはロックしないのでAの木のどのノードに対しても並行して書き込み可能となる．

\begin{figure}[ht]
  \begin{center}
      \includegraphics[width=100mm]{fig/transaction.drawio.pdf}
  \end{center}
  \caption{トランザクショナルなwrite操作}
  \label{fig:Transaction}
\end{figure}

% TODO: read時常に最新の情報が取れないことを説明する図を入れたい

readはデータに変更を加えないため，複数同時に同じノードを読み込むことが可能である．
しかし，常に最新の情報を読み込めるとは限らない．
最新の情報が欲しい場合は書き込みを一旦止めるような処理が必要になる．

\section{ディスク上とメモリ上のデータ構造}


ファイルシステムは全てRedBlackTreeで構成する．
それにより，プログラムの証明がより簡単になるからである．
また，ファイルシステムとDBはデータを保管するという本質的な役割は同じである．
よって，それらはまとめてRedBlackTreeで構成する．

ファイルシステムとDBの違いとして，スキーマが挙げられる．
DBは事前にスキーマを定義し，それに沿ってデータを挿入，参照する．
対して，ファイルシステムにはスキーマに当たるものがなく，
データはファイルパスによって管理される．
スキーマを定義することによってデータは構造化され，
構造化されたデータは非構造化データと比較して，
インデックスを作成することが容易であり，データの検索性が向上する利点がある．
しかしながら，スキーマはDBの運用中に変更されることがあり，
スキーマを変更した以前へロールバックができない問題がある．

ロールバックがスキーマの変更によって出来なくなることは信頼性に問題があると考えると，
スキーマを定義する必要のないスキーマレスなDBが必要になる．
ファイルシステムはスキーマレスなDBといえるので，ファイルシステムを構築しつつ
DBがスキーマによって実現していた機能を付け加えることを試みる．

RedBlackTreeは実装によって，操作が破壊的なものとそうでないものがある．
今回用いるのは，非破壊的な実装のRedBlackTreeである．
図\ref{fig:TreeEdit}は非破壊的編集を行うRedBlackTreeを表している．
編集前の木構造の6のノードをAにアップデートすることを考える．
まず，ルートノードからアップデートしたいノード6までをコピーする．
その後，コピーしたもののノード6をAにアップデートする．
これにより，アップデート前のノード6を破壊することなくAにアップデートが可能である．
参照する時は，黒のルートノードから辿れば古い6が，赤のルートノードから辿れば新しいAが見える．
この仕組みは，データのバックアップやDBのロールバックに用いることが可能だと考える．

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


\chapter{GearsFileSystemにおけるGCとレプリケーション}
\section{ファイルシステムの信頼性に関する機能}

ファイルシステムはデータを保持することを基本的な機能としている．
信頼性に関する機能など，その他の機能は追加機能として実装する．
ファイルシステムやDBにおける信頼性に関する追加機能として，
システムの電源断時にデータが残るpersistency，
データを書き込めたかどうかを判定するatomic write，
1つのノードが失われた際にデータを保護する多重性，
複数のコピーを調停するコミット機構などが挙げられる．

現状のGearsOSには分散ファイルシステムの通信機能やUnix Likeな
インターフェースを持つi-nodeファイルシステムの基本機能は存在するものの，
多重性やメモリ管理などの信頼性を確保するための機能が存在しない．
データの多重度を確保するための一般的な手法として，
データのバックアップやシステム自体のレプリケーションをすることが挙げられる．
メモリ管理の機能としてはガーベージコレクションが挙げられる．
ガベージコレクションは通常プログラム言語のレイヤで行われる．
これらの機能を実装することでファイルシステムの信頼性を高めたい．

\section{メモリの管理手法}

GCのアルゴリズムは大きく分けてMark \& Sweep GC，Reference counting GC，
Copying GCの3つの種類が存在する．
Mark \& Sweep GCはマークフェーズとスイープフェーズからなる。
マークフェーズはヒープ上でルートから参照することができるオブジェクト全てにマークをし，
その後、スイープフェーズでマークされていないオブジェクトを
使用されていないオブジェクトのリストであるフリーリストに接続することでGCを行う．
Reference counting GCはオブジェクトの被参照数を表すReference counterを用いるGCである．
新たに参照される度にReference counterをインクリメントし，
参照が外れる度にデクリメントする．
そのようにして，カウンターが0になった時点でフリーリストに接続することでGCを行う．
CopyingGCはメモリ上のヒープ領域をFrom領域とTo領域に分割し，
ルートから参照できるオブジェクトをFrom領域からTo領域にコピーする．
From領域を参照していたポインタはTo領域のオブジェクトを参照するように置き換える．
その後，From領域とTo領域を入れ替えることでGCを行う．

一般的にこれらのGC手法は複数を組み合わせて用いられる．
世代別GCではオブジェクトの生存期間によって適用するGCアルゴリズムを使い分ける．
アロケートされてすぐのオブジェクトを新世代オブジェクト，
任意の回数のGCを生き残ったオブジェクトを旧世代オブジェクトとし，
それぞれの特性に合ったGCアルゴリズムを適用する．
すぐに回収されることが多い新世代オブジェクトはCopying GCで網羅的にGCをし，
長く生き残る旧世代オブジェクトはMark \& Sweep GCで適宜回収するなどが例として挙げられる．
このように複数のGCアルゴリズムを組み合わせることで，
それぞれのアルゴリズムの利点を享受できる．

また，メモリ管理手法としてRust言語の所有権がある．
所有権ではメモリを所有する変数がスコープを抜ける時に，
同時にメモリも解放する．
そのためRustではGCの仕組みを必要とせず，
より高速にメモリの管理を行うことができる．

\section{GearsFileSystemのGC}

GearsFileSystemのGCはCopying GCを基本的なアルゴリズムとする．

GearsFileSystemにおけるデータは全てRedBlackTreeに格納する．
また，ディスク上とメモリ上のデータ構造は同一である．
よって，RedBlackTreeの単なるコピーによってGCを行うことによって，
データの透過性が確保され，単純なプログラムで実装することが可能と考える．


\section{GearsFileSystemのレプリケーション}

\chapter{CopyRedBlackTreeの実装}

データのバックアップやレプリケーション，GCの機能を実装するためには，
データのコピーをする必要がある．
GearsOSのファイルシステムにおいて，データは全てRedBlackTreeに格納される．
しかしながら，現状のRedBlackTreeには木をコピーする機能が無い．
よって，RedBlackTreeに木のコピー機能を実装する必要がある．

\lstinputlisting[label=src:CopyRedBlackTree.cbc, caption=CopyRedBlackTreeの実装]{src/CopyRedBlackTree.cbc}

\section{コピーのアルゴリズム}

\lstinputlisting[label=src:CopyRedBlackTree.cbc, caption=CopyRedBlackTreeのアルゴリズム]{src/copyAlgorithm.cbc}

\begin{figure}[ht]
  \begin{center}
      \includegraphics[width=160mm]{fig/copy_algo.png}
  \end{center}
  \caption{Copyのアルゴリズム}
  \label{fig:CopyAlgo}
\end{figure}

\section{Stackの使用に関して}
\section{証明のしやすさについて}


DBの重要な機能の一つにロールバックがある．
RDBのロールバックは，
コミットするまではトランザクションの開始時点に戻ることができる機能を持つ．
コミットが完了するとそれ以前の状態に戻すことはできないが，
データのバックアップをとっておくことで復元を行う．
このような，ロールバックとバックアップの仕組みをファイルシステムに実装したい．

今回は，RedBlackTreeのルートノードがデータのバージョンの役割を果たしていることを利用し，
データの復元が行える仕組みを構築することを考える．
非破壊的なTree編集はアップデートのたびに，ルートノードを増やす．
つまり，ルートノードはアップデートのログと言えその時点のデータのバージョンを表していると考えることができる．
よって，ロールバックを行いたい場合は参照を過去のルートノードに切り替える．

ルートノードはデータのアップデート時に増えるため，
データが際限なく増加していく問題がある．
この問題はCopyingGCを行うことによって解決する．
まず，RedBlackTreeを丸ごとコピーして最新のルートを残して他のルートは削除する．
その後，コピーしたものはバックアップないしログとしてディスクに書き込む．
そうすることで，データの増加によるリソースの枯渇を防ぎ，
かつデータのログ付きバックアップを作成することで信頼性の向上が期待できる．

% TODO: バックアップのフローを図にしたい


\chapter{まとめと今後の課題}

本論文ではGearsOSのファイルシステムとDBの設計について説明した．
今後，実装を行いながら設計と動作の確認，計測を行い，
設計の意図が反映されていることやプログラムの検証ができることを確認する必要がある．

また，今後の課題や議題として次のようなものが挙げられる．

\section{ファイルシステムにおけるスキーマ}

従来のRDBのようなスキーマが存在すると，
個別にバックアップなどを取らない限り
スキーマの変更以前にロールバックすることができない．
しかしながら，実際運用する上でスキーマを変更することは多々ある．
これは，データの信頼性を低下させると考える．
また，DB上のデータ構造とプログラム上で扱うデータ構造に差が生まれる
インピーダンスミスマッチが発生し，DBのデータをプログラムが扱う際に
その差を埋めるような変換を必要とする場合が生まれる．
一方で，スキーマがあることによってデータに対して高度な操作を行うことができ，
また，インデックスを容易に作成することができるといったメリットがある．
よって，スキーマフルなDBとスキーマレスなDBはそれぞれメリットデメリットがあり，
状況によって使い分けるのが良いと考える．

今回は，非構造化データ内であれば構造化データを扱うことが可能であることと，
信頼性を保証したいという点から，
スキーマレスなDBとしてのファイルシステムを考える．
しかしながら，トランザクションの仕組みを作る上でRedBlackTreeに対し，
キーを設定することから完全なスキーマレスとは言えない構成となる．

GearsOSのデータは全てDataGearで表される．
よって，GearsOSにおけるファイルシステムはDataGearの集合となる．
スキーマレスとはキーがない状態のことといえるが，
DataGearはキーが設定されていないため，その集合自体にスキーマは無い．
そのことから，GearsOSにおけるスキーマとはDataGear上のキーの構成であることがわかる．
なお，今回のRedBlackTreeによる構成の場合，キーはRedBlackTreeを指す．
DataGearはKernelのContextからプロセスのContextを経由して全て繋がっている．
よって，KernelのContext上にキーを用いたDataGearの参照を書き込む．

\section{RedBlackTreeによる権限の表現}

ファイルの権限はファイルシステムの重要な機能の一つであるため実装する必要がある．
今回のRedBlackTreeによる構成の場合，木のルートの所持者を設定することが
ファイルに対して権限を設定することにあたる．
ルートに対してアクセスする権限がなければ，
読み書きができないといった実装になると考える．
\section{データクエリ言語}

ユーザーやアプリケーションがDBのデータにアクセスするための言語設計を
する必要がある．
RedBlackTreeのキーを用いたインデックスに対応し，
従来のSQLと比較してより柔軟なクエリを実行できることを目指したい．

\section{ログなどの時系列データの保存}

時系列データは通常のデータと違った保存の方法を考えることができる．
時系列に並んでいることを生かしたデータの保存方式や，
時間経過に伴うデータの重要性の変化を考慮に入れたデータ圧縮の方法をとることで，
より効率的な保存が可能だと考える．

\section{スタンドアロンなDB}

MySQLやPostgreSQLなどはOSの機能としてではなく，
それ自体が一つのアプリケーションとして自立的に動作している．
自立的に動作するのは，データのポータビリティを向上させるためである．
スタンドアロンなDBの形にするか，
その他の方法でポータビリティを向上させる手法を考えたい．



% %謝辞
\input{chapter/thanks.tex}


%参考文献
\nocite{*}
\bibliography{reference}
\bibliographystyle{junsrt}


%発表履歴
\input{chapter/history.tex}
\addcontentsline{toc}{chapter}{研究関連論文業績}

%付録
\addcontentsline{toc}{chapter}{付録}
\appendix
\input{chapter/appendix.tex}
\end{document}