\chapter{Haskellによる\\並列データベースの実装}\label{ch:impl}
本章では、並列データベース Jungle の実装について述べる。

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

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

\subsubsection{Jungle が持つデータ型}
Jungle が持つのデータ型を表\ref{tab:components}に表す。
木構造の集まりを表現する Jungle、単体の木構造を表現する Tree がある。
Node は子と属性を任意の数持てる。
データ型として定義することで、データ内部の型の整合性が保たれ、また型検査でエラーがないか検出することができる。
Jungle のデータ型について、ひとつずつ説明する。

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

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

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

Jungle のデータ構造は、Jungle (TVar (Map String Tree)) である。
getJungleMap :: というのは、Haskell のレコード構文である。

レコード構文は、データ構造へのアクセサを提供する。
getJungleMap は関数で、以下のような型を持つ。
これは、Jungleを受け取って、TVar (Map String Tree)を返す関数である。

レコード構文はデータ型を受け取って、:: の右側の型の値を取り出せる関数を作成すると思えば良い。

\begin{lstlisting}[caption=getJungleMap]
getJungleMap :: Jungle -> TVar (Map String Tree)
\end{lstlisting}

Jungle の木の取り扱いには、Haskell の Data.Map を利用している。
型名は、Map である。
Map は、連想配列を扱うことのできるデータ構造である。
平衡木を用いて、挿入や参照が O (log n)で済むように設計されている。
Data.Mapを理解するためにはリストで考えると分かりやすい。

\begin{lstlisting}[caption=getJungleMap]
data Map k a = Map [(k,a)] 

lookup' :: Eq k =>  k -> Map k a -> Maybe a
lookup' k (Map [])          = Nothing
lookup' k (Map ((k',a):xs)) = if k == k'
                                then Just a
                                else lookup k xs


insert :: k -> a -> Map k a -> Map k a
insert k a (Map x) = Map ((k,a):x)

test = Map [("key","value"),("fizz","buzz")]
\end{lstlisting}

Map は、キーと値のペアのリストだと考えることができる。
キーが一致する値を探す場合、lookup'を用いる。
Maybe モナドを用いて、データがなければ Nothing、データがあれば Just に包んで返す。
$=>$ の前にある、Eq kは、型クラスの制約である。
内部で k と k' の同値性をテストしているため、k は同値性をチェックできる型クラス Eq に属している型である必要がある。

新たにキーと値のペアを、Mapに追加するには insertを用いる。
Haskell では、受け取った引数を変更することができないため、ペアを追加した新しい Map を返す。


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

\subsubsection{Jungle と木の作成}
Jungle は、Mapで木を管理しているため、複数の非破壊的木構造を持つことができる（図\ref{fig:jungle}）。

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

木構造の識別、つまり Map の キー にはString を利用する。
String は Haskell の文字列の型で、Char のリスト [Char] の別名である。

Jungle を作成するには、createJungle を用いる。
empty は空のMapを作成する関数である。

\begin{lstlisting}[caption=createJungle]
createJungle :: IO Jungle
createJungle = atomically $ do
    map <- newTVar empty
    return (Jungle map)
\end{lstlisting}

\begin{lstlisting}[caption=STMの関数]
newTVar :: a -> STM (TVar a)
readTVar :: TVar a -> STM a
writeTVar :: TVar a -> a -> STM ()

atomically :: STM a -> IO a
\end{lstlisting}

createJungleは、新たにSTMの変数を作成する newTVar を実行する。
newTVar などの STM の操作は STM モナド内で行う。
最後にatomicallyを行うことで、do 構文内がトランザクションとして実行される。

atomically の隣にある \$ は関数適用演算子である。
\$ 関数は最も低い優先順位を持っており、右結合である。
括弧を減らすのに使う。\$ を使わない場合は以下の様に記述することになる。

\begin{lstlisting}[caption=STMの関数]
createJungle :: IO Jungle
createJungle = atomically (do
    map <- newTVar empty
    return (Jungle map))
\end{lstlisting}

createJungle は、IOを返すため使う際には main に関連付ける必要がある。

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

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

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

新たな非破壊的木構造を作るには、createTree を用いる。
createTree は、createJungleで作成した Jungle と木の名前を String で受け取る。

\begin{lstlisting}[caption=createTree]
createTree :: Jungle -> String -> IO ()
createTree (Jungle tmap) tree_name = atomically $ do
    map <- readTVar tmap
    tree <- emptyTree tree_name
    writeTVar tmap (insert tree_name tree map)

emptyTree :: String -> STM Tree
emptyTree tree_name = do
    node <- newTVar emptyNode
    return (Tree node tree_name)

emptyNode :: Node
emptyNode = Node (empty) (empty)
\end{lstlisting}

createJungleも STM を操作するため IOを返す。
Jungle の持つ、tmapをreadTVarで取得し、複数の木構造を管理するためのMapを取得する。
STM の変数をもった Tree を作成し、Map に insert する。
writeTVar は更新する先の変数と、更新内容の2つを受け取る STM の関数である。

実際にcreateJungleとcreateTreeを使う時は以下のように記述する。

\begin{lstlisting}[caption=データベースと木の作成]
main = do
    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}

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

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

\begin{lstlisting}[caption=最新のルートノードの取得]
getRootNode :: Jungle -> String -> IO Node
getRootNode (Jungle tmap) tree_name = atomically $ do 
    map <- readTVar tmap
    readTVar (root_node map)
    where
      root_node map = case lookup tree_name map of
                        Just x -> rootNode x
\end{lstlisting}

まず、readTVarでJungleが持つmapを参照する。
Haskell の where キーワードは、計算の中間結果に名前をつけるために用いられる。
今回は、root\_node という map を受け取る関数を定義している。
root\_node map では、Jungle が持つ Map をみて取得しようとしている名前の木構造があるかどうか調べている。
木構造があった場合、rootNodeというTreeに定義されているレコード構文のアクセサ関数を使って、(TVar Node)を取得する。
最後に、(TVar Node)に対して、readTVarを行うことで最新のルートノードが取得できる。

木構造を編集する関数は全て Node を受け取って Node を返す。
その返ってきた Node をルートノードとして登録することで、木構造の最新のルートノードが更新される。
updateRootNode は、データベースと木の名前、変更して返ってきた木構造の 3 つを渡す。
updateRootNodeをした後は、getRootNodeで取得できるルートノードが更新された状態になっている。

\begin{lstlisting}[caption=ルートノードの更新]
updateRootNode :: Jungle -> String -> Node -> IO ()
updateRootNode (Jungle tmap) tree_name node = 
  atomically $ do 
    map <- readTVar tmap
    writeTVar (root_node map) node
  where
    root_node map = case lookup tree_name map of
                      Just x -> rootNode x
\end{lstlisting}

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

\begin{lstlisting}[caption=ルートノードの更新]
updateRootNodeWith :: (Node -> Node) -> Jungle -> String -> IO ()
updateRootNodeWith f (Jungle tmap) tree_name = 
  atomically $ do
    map <- readTVar tmap
    n <- readTVar (root_node map)
    writeTVar (root_node map) (f n)
  where
    root_node map = case lookup tree_name map of
                      Just x -> rootNode x
\end{lstlisting}

並列データベース Jungle で他のスレッドと状態を共有する操作は、
createJungle、createTree、getRootNode、updateRootNode、updateRootNodeWith
で全てである。
並列データベース Jungle では、なるべく状態を共有しないようにすることで並列実行時の性能の向上を実現する。
ソフトウェアトランザクショナルメモリは書き込み時に他から変更があった場合にやり直しという操作はあるものの、読み込みに関してはロックなしで高速に読み込める。

\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{木の編集}
木の編集には、Node を使う。
木の編集に用いる関数は全て Node を受け取って Node を返す。
非破壊的木構造を利用しているため、getRootNode などで取得してきた Node は他のスレッドと干渉することなく自由に参照、編集できる。
これらの編集のための関数は、編集後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}

木の編集を行う関数を紹介する。

\begin{lstlisting}[caption=木の編集を行う関数]
addNewChildAt :: Node -> Path -> Node
deleteChildAt :: Node -> Path -> Position -> Node
putAttribute :: Node -> Path -> String -> ByteString -> Node
deleteAttribute :: Node -> Path -> String -> Node
\end{lstlisting}

addNewChildAt で、ノードに新しい子を追加できる。
Node と NodePath を渡す必要がある。
子には Position という場所の情報があるが、インクリメントしながら自動的に指定される。

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

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

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

これらの関数は、ほぼ同一の関数で定義できる。
addNewChildAtを用いて説明する。

\begin{lstlisting}[caption=木の編集を行う関数]
addNewChildAt :: Node -> Path -> Node
addNewChildAt parent []     = addChildAt parent emptyNode
addNewChildAt parent (x:xs) = addChild parent x $ addNewChildAt x_node xs
  where
    map = children parent
    x_node = case lookup x map of
               Just x -> x

addChild :: Node -> Position -> Node -> Node
addChild node pos child = Node new_child attr
  where
    map = children node
    new_child = insert pos child map
    attr = attributes node

addChildAt :: Node -> Node -> Node
addChildAt node child = Node new_child attr
  where
    map = children node
    pos = (size map) + 1
    new_child = insert pos child map
    attr = attributes node
\end{lstlisting}

非破壊的木構造の編集は再帰で定義できる。
左結合となる\$を使い、対象のノードに到達するまで、addChildを繰り返す。
addChildは、引数として子となるノードが必要である。
そのため、下の階層から徐々に上に作られていく。

addNewChildAt、deleteChildAt、putAttribute、deleteAttributeといった、
非破壊的木構造の編集は、対象のノードに対する操作以外は全て同じである。
Pathのリストが空になる、すなわち対象のノードに到達した時の操作だけが異なる。
新しい子を追加するのが addNewChildAt、指定されたポジションの子を削除するのが deleteChildAt、
指定されたキーと値を追加するのが putAttribute、指定されたキーの値を削除するのが deleteAttributeである。


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

\begin{lstlisting}[caption=属性の取得]
getAttributes :: Node -> Path -> String -> Maybe ByteString
getAttributes node path key = lookup key map
  where
    target = getNode node path
    map = attributes target

getChildren :: Node -> Path -> [Node]
getChildren node path = elems map
  where
    target = getNode node path
    map = children target

assocsChildren :: Node -> Path -> [(Int, Node)]
assocsChildren node path = assocs map
  where
    target = getNode node path
    map = children target

assocs :: Node -> Path ->  [(String, ByteString)]
assocs node path = assocs map
  where
    target = getNode node path
    map = attributes target

numOfChild :: Node -> Path -> Int
numOfChild node path = size map
  where
    target = getNode node path
    map = children target

currentChild :: Node -> Path -> Maybe Node
currentChild node path = lookup pos map
  where
    target = getNode node path
    map = children target
    pos = size map
\end{lstlisting}

elems、assocs、sizeなどはData.Mapの関数である。

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

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

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

assocsAttribute は、対象の Node が持つ全ての属性を、キーと値のペアとし、そのペアのリストを返す。
あるNodeに存在する全ての属性に対して、参照を行いたい場合に利用する。

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

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


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

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

Haskell では、独自のデータ型を作成することができる。
再帰的なデータ構造の定義も容易である。
また、Haskellは参照透過性を持つため、コードの再利用が行い易く、関数同士の結合も簡単である。

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