\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}に表す. 
また, データ型内部のデータ構造を表\ref{tab:components2}に表す.

木構造の集まりを表現する Jungle, 単体の木構造を表現する Tree がある. 
Node は子と属性を任意の数持てる. 
データ型として定義することで, 内部の型の整合性が保たれる.
例えば, Node の1つ目の型は (Map Int Node) となり他の型は許されない.
非破壊的木構造データベース Jungle のデータ型について, ひとつずつ説明する. 

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

\newpage
\begin{table}[htbp]
\begin{center}
\begin{tabular}{|c||c|} \hline
  型名 & データ構造 \\ \hline
  Jungle & Jungle (TVar (Map String Tree)) \\ \hline
  Tree & Tree (TVar Node) String \\ \hline
  Node & Node (Map Int Node) (Map String ByteString) \\ \hline
\end{tabular}
\end{center}
\label{tab:components2}
\caption{データ型のデータ構造}
\end{table}

\clearpage
\section{Jungle}
Jungle は木構造の集まりを表現する. 
木には名前がついており, Tree の情報と一緒に保持している（ソースコード\ref{src:jungle}）. 

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

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

レコード構文は, データ構造へのアクセサを提供する. 
getJungleMap は関数で, ソースコード\ref{src:getjunglemap}の型を持つ. 
これは, Jungleを受け取って, TVar (Map String Tree)を返す関数である. 

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

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

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

\begin{lstlisting}[label=src:map_list, caption=リストで定義した場合のMap]
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}）. 
Tree には名前がついており, 複数のバージョンの Tree のノードのどれが最新かという情報を持っている.

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

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

Jungle を作成するには, createJungle を用いる（ソースコード\ref{src:createJungle}）. 
empty は空のMapを作成する関数である. 

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


createJungleは, 新たにSTMの変数を作成する newTVar を実行する. 
newTVar などの STM の操作は STM モナド内で行う. 
最後にatomicallyを行うことで, do 構文内がトランザクションとして実行される. 
STMの関数が持つ型をソースコード\ref{src:stm}に示す.

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

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

ソースコード\ref{src:createJungle}の atomically の隣にある \$ は関数適用演算子である. 
\$ 関数は最も低い優先順位を持っており, 右結合である. 
括弧を減らすのに使う. \$ を使わない場合はソースコード\ref{src:dollar}の様に記述することになる. 

\begin{lstlisting}[label=src:dollar, caption=関数適用演算子を使わない場合]
createJungle :: IO Jungle
createJungle = atomically (do
    map <- newTVar empty
    return (Jungle map))
\end{lstlisting}

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

\clearpage
\section{Tree}
Jungleが保持する木の情報は, 内部的には Tree というデータ型で保持している. 
Tree は木の名前と, ルートノードの情報を持っている（ソースコード\ref{src:tree}）. 
実際にユーザがJungleを利用する際は, Jungle と木の名前を使ってルートノードを取ってくるため, Tree という構造は見えない. 

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

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

新たな非破壊的木構造を作るには, createTree を用いる（ソースコード\ref{src:createTree}）. 
createTree は, createJungleで作成した Jungle と木の名前を String で受け取る. 

\begin{lstlisting}[label=src:createTree, 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 の持つ, 複数の木構造と名前を関連付けた Map をreadTVarで取得する.
ルートノードの管理のための STM の変数をもった Tree を作成し, Jungle の Map に insert する. 
そして最後に writeTVar を用いて STM を更新する.
writeTVar は更新する先の変数と, 更新内容の2つを受け取る STM の関数である. 

実際にcreateJungleとcreateTreeを利用する時はソースコード\ref{src:createdatabase}のように記述する. 

\begin{lstlisting}[label=src:createdatabase,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 というルートノードが取得できる. 


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

\begin{lstlisting}[label=src:getrootnode, 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}

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

updateRootNode 関数の定義を示す（ソースコード\ref{src:updaterootnode}）.
getRootNodeと同じように, Treeの(TVar Node)を取得し, 最後にwriteTVarを用いて更新している.

\begin{lstlisting}[label=src:updaterootnode, 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を行う一連の操作が分断されずに行われることが保証される. 

updateRootNodeWith 関数の定義を示す（ソースコード\ref{src:updaterootnodewith}）.
updateRootNodeWithでは, 一連の操作を分断せずに行うためにreadTVarからwriteTVarまで同じ STM モナド内で行っている. 
atomicallyに関数にdo構文で繋げたSTMモナドを渡すことで, このブロックがトランザクションとして実行される.

\begin{lstlisting}[label=src:updaterootnodewith, 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 では, なるべく状態を共有しないようにすることで並列実行時の性能の向上を実現する. 
ソフトウェアトランザクショナルメモリは書き込み時に他から変更があった場合にやり直しという操作はあるものの, 読み込みに関してはノンブロッキングで高速に読み込める. 

\clearpage
\section{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 を利用する（図\ref{fig:nodepath}）. 
NodePath は, ルートノードからスタートし, ノードの子どもの場所を次々に指定したものである. 
Haskell の基本データ構造であるリストを利用している. 

\begin{figure}[!htbp]
\begin{center}
\includegraphics[width=100mm]{./images/nodepath.pdf}
\end{center}
\caption{NodePath}
\label{fig:nodepath}
\end{figure}

木の編集を行う関数を紹介する. 
木の編集を行う関数の型の定義をソースコード\ref{src:editfunc_type}に示す.

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

\paragraph*{addNewChildAt}
ノードに新しい子を追加できる. 
更新対象となる木構造の Node と, どこに追加するかの情報である NodePath を渡す必要がある. 
子の場所は, インクリメントしながら自動的に指定される. 

\paragraph*{deleteChildAt}
ノードの子を削除できる. 
更新対象となる木構造の Node と, どこのノードの子を削除するかという情報である NodePath, 削除したい子の場所を指定する Position を渡す必要がある. 

\paragraph*{putAttribute}
ノードに属性を追加できる. 
更新対象となる木構造の Node と, どこに属性を追加するかの情報である NodePath を渡す必要がある. 
属性はキーと値があり, キーは String, 値は ByteString である. 

\paragraph*{deleteAttribute}
ノードの属性を削除できる. 
更新対象となる木構造の Node と, どこの属性を削除するかの情報である NodePath, 削除したい属性のキーである String  を渡す必要がある. 

これらの関数は, ほぼ同一の関数で定義できる. 
addNewChildAtを用いて説明する（ソースコード\ref{src:addNewChildAt}）. 

\newpage
\begin{lstlisting}[label=src:addNewChildAt, 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は, 指定したノードのPositionに子を追加する. 引数として子となるノードが必要である. 
addChildを繰り返すことで, 下の階層から徐々に上に作られていく. 

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

\subsubsection{木の参照}
木の参照にも参照対象となる木構造の Node を用いる. 
参照関数の定義をソースコード\ref{src:reffunc}に示す.

\begin{lstlisting}[label=src:reffunc, caption=参照関数]
getNode :: Node -> Path -> Node
getNode node []     = node
getNode node (x:xs) = getNode child xs
  where
    map = children node
    child = case M.lookup x map of
              Just x -> x
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}

参照関数の基本的な流れは, getNode関数を使って参照したいPathのノードを取ってくることである.
そのノードにはwhereキーワードを利用して, targetという名前をつけている.
targetに対して, 子のMapや属性のMapを取得した後, lookup関数などを適用する.
elems, assocs, sizeなどはData.Mapの参照関数で, Jungle ではその関数をそのまま利用している.

参照関数の基本的な機能をまとめて説明する.

\paragraph*{getAttributes}
対象の Path に存在する属性を Key を用いて参照できる. 

\paragraph*{getChildren}
対象の Node が持つ全ての子を Node のリストとして返す. 
あるNodeに存在する全ての子に対して, 参照を行いたい場合に利用する. 

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

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

\paragraph*{numOfChild}
対象の Node が持つ子どもの数を取得できる. 

\paragraph*{currentChild}
対象の Node が持つ最新の子を取得できる.