# HG changeset patch
# User Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
# Date 1391456512 -32400
# Node ID bd30d93097da00d1a85f5d7372fe6ef3aad7efcf
# Parent  a7981a22f12e2456f463c7ffbbd560caa270d0a2
describe Jungle and Tree

diff -r a7981a22f12e -r bd30d93097da paper/chapter2.tex
--- a/paper/chapter2.tex	Tue Feb 04 02:26:58 2014 +0900
+++ b/paper/chapter2.tex	Tue Feb 04 04:41:52 2014 +0900
@@ -1,14 +1,16 @@
-\chapter{Haskellによる並列データベースの設計}\label{ch:design}
+\chapter{Haskellによる\\並列データベースの設計}\label{ch:design}
 
 \section{マルチコアプロセッサで十分な性能を得るためには}
 現在、CPU はマルチコア化が進んでいる。
-マルチコアプロセッサで線形に性能向上をするためには、処理全体で高い並列度を保たなければならない\cite{amdahl}。
+マルチコアプロセッサで線形に性能向上をするためには、処理全体で高い並列度を保つ必要がある。
+アムダールの法則\cite{amdahl}によると、並列度が80 \% の場合、どんなにコア数を増やしても性能向上率は5倍にしかならない。
+
 % ウェブサービスでは、ニーズの変化に柔軟に対応できる能力が求められる。
 % 利用者や負荷の増大に対し、CPU のコア数に応じてパフォーマンスを線形に向上できる能力、すなわちスケーラビリティが必要となる。
 % スケーラビリティが線形的であれば、リソースの追加に比例したパフォーマンスを得ることが可能である。
 % 一方、スケーラビリティが線形的でないと、いくらリソースを追加しても必要なパフォーマンスが得られないというケースもありえる。
 
-CPU コア数に応じて、データベースを線形に性能向上させたい場合、別々の CPU コアから同時にデータベースへアクセスできればよい。
+CPU コア数に応じて、データベースを線形に性能向上させたい場合、別々の CPU コアから同時にデータベースへアクセスできるようにし、並列度を高める必要がある。
 通常は、同一のデータへアクセスする場合、競合が発生してしまい処理性能に限界が生じる。
 
 本研究では、非破壊的木構造という手法を用いて競合が発生する問題を解決する。
@@ -34,48 +36,6 @@
  \label{fig:nondestructive_tree_modification}
 \end{figure}
 
-非破壊的木構造の基本的な戦略は、変更したいノードへのルートノードからのパスを全てコピーする。
-そして、パス上に存在しない (編集に関係のない) ノードはコピー元の木構造と共有することである。
-
-編集は以下の手順で行われる。
-
-\begin{enumerate}
-  \item{変更したいノードまでのパスを求める(図\ref{fig:nondestructive_tree_modification_step1})。}
-  \item{変更したいノードをコピーし、コピーしたノードの内容を変更した新しいノードを作成する(図\ref{fig:nondestructive_tree_modification_step2})。}
-  \item{求めたパス上に存在するノードをルートノードに向かってコピーする。 コピーしたノードに一つ前にコピーしたノードを子供として追加した新しいノードを作成する(図\ref{fig:nondestructive_tree_modification_step3})。}
-  \item{影響のないノードをコピー元の木構造と共有する(図\ref{fig:nondestructive_tree_modification_step4})。}
-\end{enumerate}
-
-\begin{figure}[!htbp]
- \begin{center}
-  \includegraphics[scale=0.6]{./images/nondestructive_tree_modification_step1.pdf}
- \end{center}
- \caption{ステップ1 : 変更したいノードまでのパスを求める}
- \label{fig:nondestructive_tree_modification_step1}
-\end{figure}
-\begin{figure}[!htbp]
- \begin{center}
-  \includegraphics[scale=0.6]{./images/nondestructive_tree_modification_step2.pdf}
- \end{center}
- \caption{ステップ2 : 変更したいノードをコピーし、コピーしたノードの内容を変更した新しいノードを作成する}
- \label{fig:nondestructive_tree_modification_step2}
-\end{figure}
-\begin{figure}[!htbp]
- \begin{center}
-  \includegraphics[scale=0.6]{./images/nondestructive_tree_modification_step3.pdf}
- \end{center}
- \caption{ステップ3 : 求めたパス上に存在するノードをルートノードまでコピーする}
- \label{fig:nondestructive_tree_modification_step3}
-\end{figure}
-\begin{figure}[!htbp]
- \begin{center}
-  \includegraphics[scale=0.6]{./images/nondestructive_tree_modification_step4.pdf}
- \end{center}
- \caption{ステップ4 : 影響のないノードは共有する}
- \label{fig:nondestructive_tree_modification_step4}
-\end{figure}
-
-\newpage
 この編集方法を用いた場合、閲覧者が木構造を参照してる間に、木の変更を行っても問題がない。
 閲覧者は木が変更されたとしても、保持しているルートノードから整合性を崩さずに参照が可能である。
 排他制御をせずに並列に読み書きが可能であるため、スケーラブルなシステムに有用である。
@@ -110,7 +70,7 @@
 STM は排他制御を行わず、スレッドセーフに状態を扱うことができる。
 STM を利用することでロック忘れによる競合状態や、デッドロックといった問題から解放される。
 STM は、STM モナドという特殊なモナドの中でのみ変更できる。
-STM モナドの中で変更したアクションのブロックを atomically コンビネータを使ってトランザクションとして実行する（atomically コンビネータを用いることで IO モナドとして返される）。
+STM モナドの中で変更したアクションのブロックを atomically コンビネータを使ってトランザクションとして実行する。（atomically コンビネータを用いることで IO モナドとして返される）。
 いったんブロック内に入るとそこから出るまでは、そのブロック内の変更は他のスレッドから見ることはできない。
 こちら側のスレッドからも他のスレッドによる変更はみることはできず、実行は完全に孤立して行われる。
 トランザクションから出る時に、以下のことが１つだけ起こる。
diff -r a7981a22f12e -r bd30d93097da paper/chapter3.tex
--- a/paper/chapter3.tex	Tue Feb 04 02:26:58 2014 +0900
+++ b/paper/chapter3.tex	Tue Feb 04 04:41:52 2014 +0900
@@ -1,7 +1,5 @@
 \chapter{Haskellによる並列データベースの実装}\label{ch:impl}
-
 本章では、並列データベース Jungle の実装について述べる。
-まず、実装した非破壊的木構造データベースの利用方法について述べ、次に詳細な設計と実装について述べる。
 
 \section{木構造データベース Jungle}
 非破壊的木構造データベース Jungle は、Haskell で実装された並列データベースである。
@@ -10,24 +8,20 @@
 % 本研究では、HTTP サーバ Warp と組み合わせて掲示板システムとして利用しているが、他のシステムに組み込むことも可能である。
 Jungle の基本的な使い方の手順について説明する。
 \begin{enumerate}
-  \item{木構造を保持する Jungle を作成する（Jungle は複数の木を保持できる）}
+  \item{木構造を保持する Jungle を作成する}
   \item{Jungle 内に新しい木を名前をつけて作成する}
   \item{木の名前を用いて、ルートノードの取得を行い、データを参照する}
   \item{もしくは、木の名前を用いて、ルートノードの更新を行う}
 \end{enumerate}
 
-\subsubsection{Jungle 内部のデータ型}
-Jungle の内部のデータ型を表\ref{tab:components}に表す。
+\subsubsection{Jungle が持つデータ型}
+Jungle が持つのデータ型を表\ref{tab:components}に表す。
 木構造の集まりを表現する Jungle、単体の木構造を表現する Tree がある。
-Tree は外部から見えないように実装されている。
-
-Jungle は複数の Tree の集まりである。Jungle と木構造の名前を利用して最新のルートノードを取得することができる。
 Node は子と属性を任意の数持てる。
-
-データ型として定義することで、データ内部の整合性が保たれ、また型検査でエラーがないか検出することができる。
+データ型として定義することで、データ内部の型の整合性が保たれ、また型検査でエラーがないか検出することができる。
+Jungle のデータ型について、ひとつずつ説明する。
 
 \begin{table}[!htbp]
-\caption{内部のデータ型}
 \label{tab:components}
 \begin{center}
 \begin{tabular}{|c||c|} \hline
@@ -35,17 +29,71 @@
 Jungle & 木の作成・取得を担当する。 \\ \hline
 Tree & 木の名前とルートノードの情報を保持している。 \\ \hline
 Node & 基本的なデータ構造、子と属性を任意の数持てる。 \\ \hline
-children & 子となるノードを任意の数持つことができる。 \\ \hline
-attributes & Key と Value の組み合わせを任意の数持つことができる。 \\ \hline
 \end{tabular}
 \end{center}
+\caption{Jungle が持つデータ型}
 \end{table}
 
+\subsection{Jungle}
+Jungle は木構造の集まりを表現する。
+木には名前がついており、Tree の情報と一緒に保持している。
 
-\newpage
+\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 は複数の非破壊的木構造を扱うことができる（図\ref{fig:jungle}）。
+Jungle は、Mapで木を管理しているため、複数の非破壊的木構造を持つことができる（図\ref{fig:jungle}）。
 
 \begin{figure}[!htbp]
 \begin{center}
@@ -55,25 +103,91 @@
 \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 ()
 
-createJungle で、Jungle を作成できる。
+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 に関連付ける必要がある。
 
-木を作成するには、createTree を利用する。
-createTree には、createJungle で作成した Jungle と新しい木の名前を渡す。
+\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=データベースと木の作成]
-createJungle :: IO Jungle
-createTree :: Jungle -> String -> IO ()
-
-jungle <- createJungle
-createTree jungle "name of new tree here"
+main = do
+    jungle <- createJungle
+    createTree jungle "name of new tree here"
 \end{lstlisting}
 
-\newpage
+
 \subsubsection{ルートノード}
 非破壊的木構造データベース Jungle では、木の最新の状態を更新・参照するのにルートノードを使う。
 ルートノードは、最新の木構造の根がどれかの情報を保持している（図\ref{fig:getrootnode}）。
@@ -94,34 +208,84 @@
 
 \begin{lstlisting}[caption=最新のルートノードの取得]
 getRootNode :: Jungle -> String -> IO Node
-
-node <- getRootNode jungle "your tree name here"
+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を行うことで最新のルートノードが取得できる。
 
 木構造を編集する API は全て Node を受け取って Node を返す。
 その返ってきた Node をルートノードとして登録することで、木構造の最新のルートノードが更新される。
-
-updateRootNode は、データベースと木の名前、変更して返ってきた木構造を渡す。
-
+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 M.lookup tree_name map of
+                      Just x -> rootNode x
+\end{lstlisting}
 
-updateRootNode jungle "your tree name here" node
+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 M.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}
 
 \newpage
-updateRootNodeWithは、ノードを更新する関数とデータベース、木の名前を渡して利用する。
-ノードを更新する関数とは、ノードを受け取ってノードを返す関数である。
-このupdateRootNodeWithを利用することで、getRootNodeをした後、編集しupdateRootNodeを行う一連の操作がatomicallyに行われることが保証される。
+
 
-\begin{lstlisting}[caption=関数を渡してルートノードの更新]
-updateRootNodeWith :: (Node -> Node) -> Jungle -> String -> IO ()
-
-updateRootNodeWith func jungle "your tree name here"
-\end{lstlisting}
+\newpage
 
 \subsubsection{木の編集}
 木の編集には、Node を使う。
@@ -243,70 +407,6 @@
 利用方法も、シングルスレッドで実行する場合と同じである。
 
 \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
diff -r a7981a22f12e -r bd30d93097da paper/master_paper.pdf
Binary file paper/master_paper.pdf has changed