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

ファイルシステムはOSにおいて重要な機能であるためGearsOSにおいても実装をする必要があると考えられ，
当研究室では分散ファイルシステムやi-nodeを用いたファイルシステムの設計がされてきた\cite{cfile, directory}．
しかしながら，データの多重度や一貫性を確保するための機能がないため実装したい．
本研究では，データのレプリケーションやガベージコレクションの仕組みに必要である，
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{全ての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{モジュール化の仕組みInterface}

Gears OSにはモジュール化の仕組みであるInterfaceという概念が存在する．
モジュール化とはJavaのクラスのように複数のメソッドや属性を1つの機能として
まとめて記述することである．
GearsOSではInterfaceによって，DataGearやCodeGearを複数まとめてモジュール化する．
Interfaceは仕様と実装を分けて記述する．
例としてQueue Interfaceの仕様記述部分をソースコード\ref{src:Queue.h}に示す．

\lstinputlisting[label=src:Queue.h, caption=Queueのインターフェース]{src/Queue.h}

Interfaceの仕様はC言語の構造体定義の形で記述する．
2，3行目はDataGearを記述しており，DataGearは\texttt{union Data*}型で表現する．
ここにはInterfaceにおいて，CodeGearが使用するDataGearを列挙する．
5行目から10行目まではCodeGearの引数型を記述しており，\texttt{\_\_code}型で表現する．
ここに列挙したCodeGearはInterfaceのAPIとして機能する．
InterfaceのAPIの呼び出し例をソースコード\ref{exinterface}に示す．

\begin{lstlisting}[label=exinterface,frame=lrbt,caption={Interfaceの呼び出し}]
  __code odgCommitCPUWorker3(struct CPUWorker* worker, struct Context* task) {
    int i = worker->loopCounter;
    struct Queue* queue = GET_WAIT_LIST(task->data[task->odg+i]);
    goto queue->take(odgCommitCPUWorker4);
  }
\end{lstlisting}

4行目でgotoによってqueue Interfaceのtake CodeGearに継続するよう記述している．
takeのinputDataGearにはodgCommitCPUWorker4 CodeGearを指定している．
ソースコード\ref{src:Queue.h}の仕様記述ではtakeにはqueue，nextがinputDataGearの型として指定されている．
しかし，実際に呼び出す際にはnextに当たるodgCommitCPUWorker4のみを渡している．
仕様記述の際に全てのCodeGearの第1引数(inputDataGear)に渡している\texttt{Impl* queue}は，
仕様から実装のCodeGearにgotoするために必要な記述である．
軽量継続において，CodeGearを跨いで状態を保持することはできない．
よって仕様から実装に遷移するためには，実装のCodeGearをinput DataGearとして渡す必要がある．
このImplの第1引数はstubCodeGearで自動挿入されるため，
実際にAPIを使用する際は渡す必要がない．
inputDataGearのnextはCodeGearの処理が終わった際に次にgotoするCodeGearを指定する．
よって，take CodeGearの処理が全て終了すると，次にodgCommitCPUWorker4へgotoする．
nextは\texttt{next(...)}と引数に\texttt{...}が渡される．
これは仕様を記述する時点では不定である次に遷移するCodeGearのinputDataGearを表現している．
GearsOSでgotoする際は実際にはContextから必要な値を取り出す．
よって，\texttt{...}は必要な値をContextから取り出すことを意味している．

次にInterfaceの実装について説明する．
Queue Interfaceの実装の1つであるSingleLinkedQueueをソースコード\ref{src:SingleLinkedQueue.cbc}に示す．

\lstinputlisting[label=src:SingleLinkedQueue.cbc, caption=Queueのインターフェース]{src/SingleLinkedQueue.cbc}

3行目の\texttt{\#impl as}はInterfaceの実装を記述する際に指定する．
implの直後に実装したいInterfaceの仕様を指定し，
asの後ろには実装の型名を記述する．
であるから，\texttt{\#impl "Queue.h" as "SingleLinkedQueue.h"}は仕様Queueの実装を
SingleLinkedQueueとして定義することになる．
7行目の\texttt{createSingleLinkedQueue}はSingleLinkedQueueのコンストラクタを定義しており，
DataGearのアロケートやCodeGearを保持するメソッドの初期化を行っている．
8，9行目ではnewでアロケートを行っている．
アロケートのようなメタレベルの処理はノーマルレベルには記述されない．
そのためこのnewはC言語のnewとは違うGearsOS独自の記述であり，
実際にはメタレベルにアロケートを行う処理を挿入している．
10〜16行目ではSingleLinkedQueueで使用するCodeGearとDataGearを
queueのメソッドとして初期化している．
CodeGearはQueueの仕様で記述したCodeGearと一致している．
\texttt{C\_}で始まる記述にはenum CodeにおけるCodeGearの整数を格納している．
CodeGearはenum Codeで整数と対応付けられており，
この整数を元にCodeGearが参照される．
20行目以降では\texttt{putSingleLinkedQueue}や\texttt{takeSingleLinkedQueue}
のように，仕様で記述されたCodeGearを実装している．
15，16行目では実装の型定義で定義されたその実装独自のDataGearを初期化している．
実装の型定義はソースコード\ref{src:SingleLinkedQueue.h}の通りである．

\lstinputlisting[label=src:SingleLinkedQueue.h, caption=SingleLinkedQueueの型定義]{src/SingleLinkedQueue.h}

3行目にあるように，実装の型定義ではimplキーワードで実装した型名を指定する．
4，5行目でSingleLinkedQueueが独自にもつtop，lastのDataGearを記述している．

\section{GearsOSのRedBlackTree}

Red-black tree(赤黒木)は二分探索木の一種で，
ノードに赤か黒の色を付けて色に関するいくつかの条件をもつデータ構造である．
木に対する探索，挿入，削除操作における最悪計算量がO(log n)であるため，
赤黒木は大規模なデータを扱う際に効率的なデータ構造となる．

GearsOSのRedBlackTreeはGearsFileSystemで用いられる重要な構造の1つであり，
ディレクトリ構造を表現するために使用されている．
GearsOSにおけるTreeの仕様記述をソースコード\ref{src:Tree.h}に示す．

\lstinputlisting[label=src:Tree.h, caption=Treeの仕様]{src/Tree.h}

ソースコード\ref{src:Tree.h}より，Treeはtree DataGearと
put，get，remove，nextの4つのCodeGearをAPIとして持っていることがわかる．
他にも探索や木のローテートを行うCodeGearが実装されているが，
RedBlackTreeのAPIとして提供しているのはput，get，removeの3つであり，
RedBlackTree Interfaceの使用者は木に対してこの3つの操作ができる．
それぞれノードの挿入，取得，削除を行うCodeGearである．
取得は，指定したnodeと一致するノードを木から探し，
存在すればそのまま返す．

次に，RedBlackTreeの実装の記述の一部をソースコード\ref{src:RedBlackTreeImpl.cbc}に示す．

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

ソースコード\ref{src:RedBlackTreeImpl.cbc}の4行目から，
RedBlackTreeはTreeの実装の　であることがわかり，
13〜16行目で仕様に対応するCodeGearを初期化している．

次に，RedBlackTreeの実装の型定義をソースコード\ref{src:RedBlackTree.h}に示す．

\lstinputlisting[label=src:RedBlackTree.h, caption=RedBlackTreeの実装の型定義]{src/RedBlackTree.h}

\begin{figure}[ht]
  \begin{center}
      \includegraphics[width=160mm]{fig/rbtree_def.png}
  \end{center}
  \caption{RedBlackTreeのノードの種類}
  \label{fig:rbtree-def}
\end{figure}

2〜7行目はRedBlackTreeが持つノードを表しており，
それぞれのノードの役割は図\ref{fig:rbtree-def}のように示される．
rootはRedBlackTreeの全てのノードを参照できる親ツリーのルートノードを指す．
読み込み中のノードはcurrentで指されており，currentの親ノードをprevious，
追加するノードをnewNodeで表している．
また，RedBlackTreeは挿入，更新，削除の際に木の回転操作を行う．
その際，起点のノードに対して親のノードをparent，祖父母のノードをgrandparentで指す．
8行目のnodeStackは木の操作をする際に使用するスタックである．
9行目のfindNodeNextはfindNode CodeGearを実行後，次に実行するCodeGearを保持する．
10行目のresultはノードを探索する際のノードの比較結果を保持する．

\chapter{GearsFileSystem}

ファイルシステムはOSにおいてユーザーやアプリケーションが使用するファイルや
プロセスの管理に用いられる重要なシステムである．
そのため，GearsOSにおいてもi-nodeを用いたディレクトリシステムや，
DataGearManagerによる分散ファイルシステムの仕組みをもつ，
GearsFileSystemの取り組みがいくつかされてきた．

\section{i-nodeを用いたディレクトリシステム}

GearsFileSystemにはi-nodeを用いたディレクトリの仕組みが存在する\cite{directory}．
i-nodeは主にUnix系のファイルシステムで用いられる，
ファイルの属性情報が書かれたデータである．
inodeにおけるファイルの属性情報は表\ref{table:inode}のようなものがある．
またinodeは識別番号としてinode numberを持つ．
inode numberは一つのファイルシステム内で一意の番号であり，\emph{ls -i}コマンドで確認可能である．
inodeはファイルシステム始動時にinode領域をディスク上に確保する．
そのためinode numberには上限があり，それに伴いファイルシステム上で扱えるファイル数の上限も決まる．
inode numberの最大値は\emph{df -i}コマンドで確認可能である．

\begin{table}[htpb]
  \begin{center}
    \small
    \begin{tabular}[htpb]{|c||c|}
      \hline
      File Types & directoryやregular fileなど，ファイルの種類 \\
      \hline
      Permissions & read write executeの実行可否\\
      \hline
      UID & ファイル所有者のID \\
      \hline
      GID & ファイル所有グループのID \\
      \hline
      File Size & ファイルのサイズ \\
      \hline
      Time Stamps & ファイル作成，編集日時 \\
      \hline
      Number of link & ハードリンクの数 \\
      \hline
      Location on hard disk & データのアドレス\\
      \hline
    \end{tabular}
    \caption{inodeでのファイル属性情報}
    \label{table:inode}
  \end{center}
\end{table}

GearsFileSystemではi-nodeをi-node numberがkey，
i-nodeでのファイル属性情報をvalueであるノードを持つinode treeをRedBlackTreeで表現している．
また，ファイル名からi-node numberを検索するためのindex treeも同じRedBlackTreeで表現している．
データ構造にRedBlackTreeのみを用いているのは，
ls，cd，mkdirといった，ディレクトリ操作を行うためのUnix Likeなユーザーインターフェースをもつ．
図\ref{fig:GearsDir}にGears Directoryの処理の例を示す．

\begin{figure}[ht]
  \begin{center}
      \includegraphics[width=160mm]{fig/gears_dir.png}
  \end{center}
  \caption{i-nodeを用いたディレクトリシステムの処理の流れ}
  \label{fig:GearsDir}
\end{figure}

lsコマンドはディレクトリ内のファイルやファイル自体の情報を出力するコマンドである．
\texttt{ls hoge.txt}を実行すると\textcircled{\scriptsize 1}index treeを参照し，
ファイル名hoge.txtからi-node numberの2を取得する．
次に，\textcircled{\scriptsize 2}i-node treeを参照し，
i-node numberを元にファイルの属性を取得し，lsコマンドの場合はそれを出力する．

\section{DataGearManagerによる分散ファイルシステム}
\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を基本的なアルゴリズムとする．
他のGC手法と比較して参照できるオブジェクトをコピーするだけであるため，
実装が簡単で，より高いスループットが期待できる．
Mark \& Sweep GCやReference counting GCの場合は，
GCを複数フェーズで実装したり，カウンターの扱いについて考える必要がある．
また，同様の構造をコピーするのみで実装することによって，
データの透過性の確保がしやすい．
ファイルやディレクトリを表現するRedBlackTreeは全てのデータの参照を持つ．
そのため，オブジェクトルートからオブジェクトを辿ってコピーを行うCopying GCとの相性が良い．

一般的なCopying GCではFrom領域上のオブジェクトをTo領域にコピーする形で実装される．
一方，GearsFileSystemではファイルやディレクトリの基本構造であるRedBlackTreeをコピーする．
ファイルやディレクトリの操作を行うFromのRedBlackTreeから，
ルートから辿れるノードのみをToのRedBlackTreeとしてコピーする．
それにより，辿れなかったノード，つまり参照されていないノードはコピーされず，
不要なオブジェクトが回収された状態となる．

\begin{figure}[ht]
  \begin{center}
      \includegraphics[width=160mm]{fig/rbtree_gc.png}
  \end{center}
  \caption{RedBlackTReeのCopyによるGC}
  \label{fig:TreeCopyGC}
\end{figure}

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

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

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


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

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

\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{証明のしやすさについて}



% 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}