--- a/paper/chapter3.tex	Fri Jan 24 11:55:19 2014 +0900
+++ b/paper/chapter3.tex	Tue Jan 28 06:40:52 2014 +0900
@@ -1,7 +1,238 @@
-\chapter{Haskellによるデータベースの実装}\label{ch:impl}
+\chapter{Haskellによる並列データベースの実装}\label{ch:impl}
+
+本章では、並列データベースの実装について述べる。
+まず、実装した木構造データベースの利用方法について述べ、次に詳細な設計と実装について述べる。
+
+\section{木構造データベース Jungle}
+木構造データベース Jungle は、Haskell で実装された並列データベースである。
+非破壊的木構造の方法に則ったAPIを提供する。
+本研究では、HTTP サーバ Warp と組み合わせて掲示板システムとして利用しているが、他のシステムに組み込むことも可能である。
+
+\subsubsection{木の作成}
+Jungle は複数の木構造を保持する事ができる。
+木構造は、名前を付けて管理する。
+名前を利用することで他の木構造と識別し、作成・編集を行う。
+
+createJungle で、データベースを作成できる。
+木を作成するには、createTree を利用する。
+createTree には、createJungle で作成したデータベースと新しい木の名前を渡す。\\
+
+\begin{lstlisting}[caption=データベースと木の作成]
+jungle <- createJungle
+createTree jungle "name of new tree here"
+\end{lstlisting}
+
+\subsubsection{ルートノード}
+Jungle は参照および編集に木構造のルートノードを活用する。
+ルートノードに関する API を説明する。
+
+getRootNode は、最新のルートノードを取得できる。
+データベースと木の名前を渡すことで利用する。\\
+
+\begin{lstlisting}[caption=最新のルートノードの取得]
+node <- getRootNode jungle "your tree name here"
+\end{lstlisting}
+
+
+木構造を編集する API は全て Node を受け取って Node を返す。
+その返ってきた Node をルートノードとして新たに登録することで木構造が更新される。
+updateRootNode は、データベースと木の名前、変更して返ってきた木構造を渡す。
+updateRootNodeをした後は、getRootNodeで取得できるルートノードが更新された状態になっている。\\ 
+
+\begin{lstlisting}[caption=ルートノードの更新]
+updateRootNode jungle "your tree name here" node
+\end{lstlisting}
+
+updateRootNodeWithは、ノードを更新する関数とデータベース、木の名前を渡して利用する。
+ノードを更新する関数とは、ノードを受け取ってノードを返す関数である。
+このupdateRootNodeWithを利用することで、getRootNodeをした後、編集しupdateRootNodeを行う一連の操作がatomicallyに行われることが保証される。
+\\
+
+\begin{lstlisting}[caption=関数を渡してルートノードの更新]
+updateRootNodeWith func jungle "your tree name here"
+\end{lstlisting}
+
+\subsubsection{木の編集}
+木の編集には、Node を使う。
+木の編集に用いる API は全て Node を受け取って Node を返す。
+非破壊的木構造を利用しているため、getRootNode などで取得してきた Node は他のスレッドと干渉することなく自由に参照、編集できる。
+これらの編集のためのAPIは、編集後updateRootNodeするか、ひとつの関数にまとめてupdateRootNodeWithをすることで木構造に反映させることができる。
+
+編集対象のノードを指定するには、NodePath を利用する。
+NodePath は、ルートノードからスタートし、ノードの子どもの場所を次々に指定したものである。
+Haskell の基本データ構造であるリストを利用している。
+
+
+\begin{figure}[!htbp]
+\begin{center}
+\includegraphics[width=100mm]{./images/nodepath.pdf}
+\end{center}
+\caption{NodePath}
+\label{fig:nodepath}
+\end{figure}
+
+addNewChildAt で、ノードに新しい子を追加できる。
+addNewChildAt には、Node と NodePath を渡す。
+子には Position という場所の情報があるが、インクリメントしながら自動的に指定される。
+\\
+\begin{lstlisting}[caption=子の追加]
+new_node = addNewChildAt node [l,2]
+\end{lstlisting}
+
+deleteChildAt で、ノードの子を削除できる。
+deleteChildAt には、Node と NodePath、削除したい子のPositionを指定する。
+\\
+\begin{lstlisting}[caption=子の削除]
+new_node = deleteChildAt node [1,2] 0
+\end{lstlisting}
+
+putAttribute で、ノードに属性を追加できる。
+putAttribute には、Node と NodePath、Key、Valueを渡す。
+Key は String、 Value は、ByteString である。
+\\
+\begin{lstlisting}[caption=属性の追加]
+new_node = putAttribute node [1,2] "key" "value"
+\end{lstlisting}
+
+deleteAttribute で、ノードの属性を削除できる。
+deleteAttribute には、Node と NodePath、Keyを渡す。
+\\
+\begin{lstlisting}[caption=属性の削除]
+new_node = deleteAttribute node [1,2] "key"
+\end{lstlisting}
+
+
+\subsubsection{木の参照}
+木の参照にも Node を用いる。
+様々な参照の API があるため、ひとつずつ紹介していく。
+
+getAttributes は、対象の Path に存在する属性を Key を用いて参照できる。
+\\
+\begin{lstlisting}[caption=属性の取得]
+bytestring = getAttributes node [1,2] "key"
+\end{lstlisting}
 
-\section{Node}
-\section{Treeの取り扱い}
-\section{ルートノード}
+あるNodeに存在する全ての子に対して、参照を行いたい場合に利用する。
+getChildren は、対象の Node が持つ全ての子を Node のリストとして返す
+\\
+\begin{lstlisting}[caption=対象のNodeの全ての子を取得]
+nodelist = getChildren node [1,2]
+\end{lstlisting}
+
+あるNodeに存在する全ての子に対して、参照を行いたい場合に利用する。
+getChildren と違い、子のPositionも取得できる。
+assocsChildren は、対象の Node が持つ全ての子を Position とのタプルにし、そのタプルのリストを返す。
+\\
+\begin{lstlisting}[caption=対象のNodeの全ての子とPositionを取得]
+nodelist = assocsChildren node [1,2]
+\end{lstlisting}
+
+
+あるNodeに存在する全ての属性に対して、参照を行いたい場合に利用する。
+assocsAttribute は、対象の Node が持つ全ての属性を、Key と Value のタプルとし、そのタプルのリストを返す。
+\\
+\begin{lstlisting}[caption=対象のNodeの全てのAttributeのKeyとValueを取得]
+attrlist = assocsAttribute node [1,2]
+\end{lstlisting}
+
+numOfChild では、対象の Node が持つ子どもの数を取得できる。
+\\
+\begin{lstlisting}[caption=対象のNodeの子どもの数を取得]
+num = numOfChild node [1,2]
+\end{lstlisting}
+
+currentChild では、対象の Node が持つ最新の子を取得できる。
+\\
+\begin{lstlisting}[caption=対象のNodeの最新の子を取得]
+node = currentChild node [1,2]
+\end{lstlisting}
+
+\section{木構造データベース Jungle の実装}
+\subsubsection{開発環境}
+実装には、Haskell を用いる。
+\subsubsection{全体の構造}
+木構造の集まりを表現する Jungle、単体の木構造を表現する Node から構成される。
+Jungle は複数の Node の集まりである。Jungle を利用して最新のルートノードを取得することができる。
+Node は子と属性を任意の数持てる。
+
+\begin{table}[!htbp]
+\caption{全体の構造}
+\label{tab:components}
+\begin{center}
+\begin{tabular}{|c||c|} \hline
+名前 & 概要 \\ \hline
+Jungle & 木の作成・取得を担当する。 \\ \hline
+Node & 基本的なデータ構造、子と属性を任意の数持てる。 \\ \hline
+RootNode & 木構造のルートを表す。Jungle から最新のルートノードを取得できる。 \\ \hline
+children & 子となるノードを任意の数持つことができる。 \\ \hline
+attributes & Key と Value の組み合わせを任意の数持つことができる。 \\ \hline
+\end{tabular}
+\end{center}
+\end{table}
+
+\subsection{Jungle}
+Jungle は木構造の集まりを表現する。
+木には名前がついており、ルートノードの情報も一緒に保持している。
+
+\subsubsection{木の取り扱い}
+Jungle の木の取り扱いには、Haskell の Data.Map を利用している。
+Haskell で連想配列を扱いたい場合、平衡木によって実装された Data.Map を一般的に用いる。
+Haskell のライブラリには配列や、ハッシュ・テーブルといったものも存在するがあまり使われない。
+配列は参照に適しているが、データを追加する際に配列を再作成するためコストが大きい。
+ハッシュ・テーブルは更新操作に副作用を伴うため、IOモナドの中でしか使うことが出来ず、扱いにくい。
+Data.Mapは、挿入や参照が O(log n) で済む。
+
+また、木の取り扱いには Haskell のソフトウェア・トランザクショナル・メモリ (STM) を利用して状態を持たせ、スレッド間で共有できるようにしてある。
+これは、木構造の各スレッドから作成できるようにするためである。
+STM は、スレッド間でデータを共有するためのツールである。STM を利用することでロック忘れによる競合状態や、デッドロックといった問題から解放される。
+STM は、アクションのブロックを atomically コンビネータを使ってトランザクションとして実行する。
+いったんブロック内に入るとそこから出るまでは、そのブロック内の変更は他のスレッドから見ることはできない。
+こちら側のスレッドからも他のスレッドによる変更はみることはできず、実行は完全に孤立して行われる。
+トランザクションから出る時に、以下のことが１つだけ起こる。
+\begin{itemize}
+ \item 同じデータを平行して変更したスレッドが他になければ、加えた変更が他のスレッドから見えるようになる。
+ \item そうでなければ、変更を実際に実行せずに破棄し、アクションのブロックを再度実行する。
+\end{itemize}
+STM は簡単に使え、また同時に安全である。
+
+\subsection{Node}
+Node は木構造を表現するデータ構造である。
+再帰的に定義されている。
+各ノードは Children としてノードを複数持つことができる（図\ref{fig:node_components}）。
+
+\begin{figure}[!htbp]
+\begin{center}
+\includegraphics[width=110mm]{./images/node_component.pdf}
+\end{center}
+\caption{Nodeの構成要素}
+\label{fig:node_components}
+\end{figure}
+
+Children および Attributes も Data.Map を用いて定義されている（ソースコード \ref{src:node}）。
+
+\begin{lstlisting}[label=src:node, caption=Nodeのデータ型の定義]
+data Node = Node
+          { children   :: (Map Int Node)
+          , attributes :: (Map String ByteString) }
+\end{lstlisting}
+
+\subsubsection{ルートノード}
+非破壊的木構造ではノードは破壊されない。
+そのため、どのノードが最新のルートノードなのかという情報が必要である。
+この情報もスレッドセーフに取り扱う必要があるため、Haskell の ソフトウェア・トランザクショナル・メモリ (STM) を用いて管理している。
+
 \section{並列実行}
+木構造データベース Jungle は、並列に実行することができる。
+アプリケーション側で、データベースを参照や変更する際に各スレッドから呼び出しても問題ない。
+利用方法も、シングルスレッドで実行する場合と同じである。
 
+\section{Haskell の生産性}
+Java を用いた Jungle の実装と比較して、コード行数が約 3000 行から約 300 行へと短くなった。
+
+これは Haskell の表現力が高いためである。
+Haskell では、データ型を簡単に作成することができる。
+再帰的なデータ構造の定義も容易である。
+共通の性質を扱うための型クラスという仕組みが存在し、既存のライブラリを作成したデータ型に利用できる。
+また、Haskellは参照透過性を持つため、コードの再利用が行い易く、関数同士の結合も簡単である。
+
+同じような機能を実装する場合でも、Java と比較してコード行数が短くなり生産性が向上する。