\chapter{Haskellによる並列データベースの実装}\label{ch:impl}

本章では、並列データベース Jungle の実装について述べる。
まず、実装した非破壊的木構造データベースの利用方法について述べ、次に詳細な設計と実装について述べる。

\section{木構造データベース Jungle}
非破壊的木構造データベース Jungle は、Haskell で実装された並列データベースである。
非破壊的木構造の方法に則ったAPIを提供する。

% 本研究では、HTTP サーバ Warp と組み合わせて掲示板システムとして利用しているが、他のシステムに組み込むことも可能である。
Jungle の基本的な使い方の手順について説明する。
\begin{enumerate}
  \item{木構造を保持する Jungle を作成する（Jungle は複数の木を保持できる）}
  \item{Jungle 内に新しい木を名前をつけて作成する}
  \item{木の名前を用いて、ルートノードの取得を行い、データを参照する}
  \item{もしくは、木の名前を用いて、ルートノードの更新を行う}
\end{enumerate}

\subsubsection{Jungle 内部のデータ型}
Jungle の内部のデータ型を表\ref{tab:components}に表す。
木構造の集まりを表現する Jungle、単体の木構造を表現する Tree がある。
Tree は外部から見えないように実装されている。

Jungle は複数の Tree の集まりである。Jungle と木構造の名前を利用して最新のルートノードを取得することができる。
Node は子と属性を任意の数持てる。

\begin{table}[!htbp]
\caption{内部のデータ型}
\label{tab:components}
\begin{center}
\begin{tabular}{|c||c|} \hline
型名 & 概要 \\ \hline
Jungle & 木の作成・取得を担当する。 \\ \hline
Tree & 木の名前とルートノードの情報を保持している。 \\ \hline
Node & 基本的なデータ構造、子と属性を任意の数持てる。 \\ \hline
children & 子となるノードを任意の数持つことができる。 \\ \hline
attributes & Key と Value の組み合わせを任意の数持つことができる。 \\ \hline
\end{tabular}
\end{center}
\end{table}

\newpage

\subsubsection{Jungle と木の作成}
Jungle は複数の非破壊的木構造を扱うことができる（図\ref{fig:jungle}）。

\begin{figure}[!htbp]
\begin{center}
\includegraphics[scale=0.7]{./images/jungle.pdf}
\end{center}
\caption{複数の木を扱えるJungle}
\label{fig:jungle}
\end{figure}

木構造の識別には、名前を利用する。
名前を付けて作成し、名前を用いることで参照を行う。

createJungle で、Jungle を作成できる。

木を作成するには、createTree を利用する。
createTree には、createJungle で作成した Jungle と新しい木の名前を渡す。

型の定義と実際のコードを示す。

\begin{lstlisting}[caption=データベースと木の作成]
createJungle :: IO Jungle
createTree :: Jungle -> String -> IO ()

jungle <- createJungle
createTree jungle "name of new tree here"
\end{lstlisting}

\subsubsection{ルートノード}
非破壊的木構造データベース Jungle では、木の最新の状態を更新・参照するのにルートノードを使う。
ルートノードは、最新の木構造の根がどれかの情報を保持している（図\ref{fig:getrootnode}）。

\begin{figure}[!htbp]
\begin{center}
\includegraphics[scale=0.7]{./images/get_root_node.pdf}
\end{center}
\caption{ルートノード}
\label{fig:getrootnode}
\end{figure}

ルートノードに関する API を説明する。

getRootNode は、最新のルートノードを取得できる。
データベースと木の名前を渡すことで利用できる。
例えば、図\ref{fig:getrootnode}の状態の時は、B というルートノードが取得できる。

\begin{lstlisting}[caption=最新のルートノードの取得]
getRootNode :: Jungle -> String -> IO Node

node <- getRootNode jungle "your tree name here"
\end{lstlisting}


木構造を編集する API は全て Node を受け取って Node を返す。
その返ってきた Node をルートノードとして登録することで、木構造の最新のルートノードが更新される。

updateRootNode は、データベースと木の名前、変更して返ってきた木構造を渡す。

updateRootNodeをした後は、getRootNodeで取得できるルートノードが更新された状態になっている。

\begin{lstlisting}[caption=ルートノードの更新]
updateRootNode :: Jungle -> String -> Node -> IO ()

updateRootNode jungle "your tree name here" node
\end{lstlisting}

updateRootNodeWithは、ノードを更新する関数とデータベース、木の名前を渡して利用する。
ノードを更新する関数とは、ノードを受け取ってノードを返す関数である。
このupdateRootNodeWithを利用することで、getRootNodeをした後、編集しupdateRootNodeを行う一連の操作がatomicallyに行われることが保証される。

\begin{lstlisting}[caption=関数を渡してルートノードの更新]
updateRootNodeWith :: (Node -> Node) -> Jungle -> String -> IO ()

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=子の追加]
addNewChildAt :: Node -> Path -> Node

new_node = addNewChildAt node [l,2]
\end{lstlisting}

deleteChildAt で、ノードの子を削除できる。
deleteChildAt には、Node と NodePath、削除したい子のPositionを指定する。

\begin{lstlisting}[caption=子の削除]
deleteChildAt :: Node -> Path -> Position -> Node

new_node = deleteChildAt node [1,2] 0
\end{lstlisting}

putAttribute で、ノードに属性を追加できる。
putAttribute には、Node と NodePath、Key、Valueを渡す。
Key は String、 Value は、ByteString である。

\begin{lstlisting}[caption=属性の追加]
putAttribute :: Node -> Path -> String -> ByteString -> Node

new_node = putAttribute node [1,2] "key" "value"
\end{lstlisting}

deleteAttribute で、ノードの属性を削除できる。
deleteAttribute には、Node と NodePath、Keyを渡す。

\begin{lstlisting}[caption=属性の削除]
deleteAttribute :: Node -> Path -> String -> Node

new_node = deleteAttribute node [1,2] "key"
\end{lstlisting}


\subsubsection{木の参照}
木の参照にも Node を用いる。
様々な参照の API があるため、ひとつずつ紹介していく。

getAttributes は、対象の Path に存在する属性を Key を用いて参照できる。

\begin{lstlisting}[caption=属性の取得]
getAttributes :: Node -> Path -> String -> Maybe ByteString

bytestring = getAttributes node [1,2] "key"
\end{lstlisting}

あるNodeに存在する全ての子に対して、参照を行いたい場合に利用する。
getChildren は、対象の Node が持つ全ての子を Node のリストとして返す

\begin{lstlisting}[caption=対象のNodeの全ての子を取得]
getChildren :: Node -> Path -> [Node]

nodelist = getChildren node [1,2]
\end{lstlisting}

あるNodeに存在する全ての子に対して、参照を行いたい場合に利用する。
getChildren と違い、子のPositionも取得できる。
assocsChildren は、対象の Node が持つ全ての子を Position とのタプルにし、そのタプルのリストを返す。

\begin{lstlisting}[caption=対象のNodeの全ての子とPositionを取得]
assocsChildren :: Node -> Path -> [(Int, Node)]

nodelist = assocsChildren node [1,2]
\end{lstlisting}


あるNodeに存在する全ての属性に対して、参照を行いたい場合に利用する。
assocsAttribute は、対象の Node が持つ全ての属性を、Key と Value のタプルとし、そのタプルのリストを返す。

\begin{lstlisting}[caption=対象のNodeの全てのAttributeのKeyとValueを取得]
assocsAttribute :: Node -> Path ->  [(String, B.ByteString)]

attrlist = assocsAttribute node [1,2]
\end{lstlisting}

numOfChild では、対象の Node が持つ子どもの数を取得できる。

\begin{lstlisting}[caption=対象のNodeの子どもの数を取得]
numOfChild :: Node -> Path -> Int

num = numOfChild node [1,2]
\end{lstlisting}

currentChild では、対象の Node が持つ最新の子を取得できる。

\begin{lstlisting}[caption=対象のNodeの最新の子を取得]
currentChild :: Node -> Path -> Maybe Node

node = currentChild node [1,2]
\end{lstlisting}

\subsubsection{並列実行}
木構造データベース Jungle は、並列に実行することができる。
アプリケーション側で、データベースを参照や変更する際に各スレッドから呼び出しても問題ない。
利用方法も、シングルスレッドで実行する場合と同じである。

\clearpage
\section{木構造データベース Jungle の実装}
\subsubsection{開発環境}
実装には、Haskell を用いる。
コンパイラは、Haskell の並列実行に対応した Glasgow Haskell Compiler (GHC) を用いる。
GHC は、Haskell で最も広く使われているコンパイラである\cite{ghc}。
並列実行のためのMonadや、スレッドセーフな参照型を提供している。

\subsection{Jungle}
Jungle は木構造の集まりを表現する。
木には名前がついており、ルートノードの情報も一緒に保持している。

\subsubsection{木の取り扱い}
Jungle の木の取り扱いには、Haskell の Data.Map を利用している。

Haskell で連想配列を扱いたい場合、平衡木によって実装された Data.Map を一般的に用いる。
Haskell のライブラリには配列や、ハッシュ・テーブルといったものも存在するがあまり使われない。
配列は参照に適しているが、データを追加する際に配列を再作成するためコストが大きい。
ハッシュ・テーブルは更新操作に副作用を伴うため、IOモナドの中でしか使うことが出来ず、扱いにくい。
Data.Mapは、挿入や参照が O(log n) で済む。

また、木の取り扱いには Haskell のソフトウェア・トランザクショナル・メモリ (STM) を利用して状態を持たせ、スレッド間で共有できるようにしてある。
これは、各スレッドから木構造を新たに作成できるようにするためである。
STM は、スレッド間でデータを共有するためのツールである。STM を利用することでロック忘れによる競合状態や、デッドロックといった問題から解放される。

\begin{lstlisting}[label=src:node, caption=Treeのデータ型の定義]
data Jungle = Jungle { getJungleMap :: (TVar (Map String Tree)) } 
\end{lstlisting}

TVar というのは、Transactional variablesの略で、STM で管理する変数に対して利用する。

\subsection{Tree}
Jungleが保持する木構造は、内部的には Tree というデータ型で保持している。
Tree は木の名前と、ルートノードの情報を持っている。
実際にユーザがJungleを利用する際は、Jungle と木の名前を使ってルートノードを取ってくるため、Tree という構造は見えない。

ルートノードの情報はスレッド間で状態を共有する必要がある。
スレッドセーフに取り扱う必要があるため、この情報も Haskell の ソフトウェア・トランザクショナル・メモリ (STM) を用いて管理している。

\begin{lstlisting}[label=src:node, caption=Treeのデータ型の定義]
data Tree = Tree
          { rootNode :: (TVar Node)
          , treeName :: String }
\end{lstlisting}

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


\clearpage
\section{Haskellの並列処理}
純粋関数型言語 Haskell は並列処理に向いていると言われる。
しかしながら、安直にそう言い切ることはできない。
参照透過性があるため、各々の関数の処理は独立している。
そのため、並列で走らせても問題ないように思われるが、Haskell は遅延評価を行うため問題が発生する。
遅延評価では、結果が必要になるまで評価されない。
実装においては、deepseqを用いて即時評価を挟むか、出力など計算が必要となる処理を挟むようにする。

Haskellでは、様々な並列化手法が提供されている。
スレッドを直接操作することも可能である。

本研究では、抽象度の高い Eval モナドを利用した。
Eval モナドを利用することで、並列処理のために必要な処理の流れを分かりやすく記述することができた。
しかしながら Eval モナドは実行順序を細かく制御することはできない。
Par モナドを利用すれば、並列処理の流れを細かく記述できるが、
Eval モナドのように処理と並列処理の流れを分けて記述し、後からプログラムに並列処理を組み込むというようなことはできない。

Haskellで並列処理を実装する場合は、どの並列化手法を採用するかということをよく考察する必要がある。

\section{Haskell の生産性}
Java を用いた Jungle の実装と比較して、コード行数が約 3000 行から約 300 行へと短くなった。

これは Haskell の表現力が高いためである。
Haskell では、独自のデータ型を簡単に作成することができる。
再帰的なデータ構造の定義も容易である。
共通の性質を扱うための型クラスという仕組みが存在し、既存のライブラリを作成したデータ型に利用できる。
また、Haskellは参照透過性を持つため、コードの再利用が行い易く、関数同士の結合も簡単である。

同じような機能を実装する場合でも、Java と比較してコード行数が短くなり生産性が向上する。