# HG changeset patch
# User Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
# Date 1390532119 -32400
# Node ID 70bda541eb1d24c13fb99465bbeec48aebbd4c5b
# Parent  a145ceb871d3ea87ed1555692c1a3c9e3655a5fe
add pdf

diff -r a145ceb871d3 -r 70bda541eb1d .hgignore
--- a/.hgignore	Sun Jan 19 23:30:12 2014 +0900
+++ b/.hgignore	Fri Jan 24 11:55:19 2014 +0900
@@ -8,4 +8,3 @@
 *.lof
 *.lot
 *.toc
-master_paper.pdf
diff -r a145ceb871d3 -r 70bda541eb1d paper/chapter1.tex
--- a/paper/chapter1.tex	Sun Jan 19 23:30:12 2014 +0900
+++ b/paper/chapter1.tex	Fri Jan 24 11:55:19 2014 +0900
@@ -141,9 +141,10 @@
 
 \begin{lstlisting}[label=rpar/rseq/rseq, caption=rpar/rseq/rseq]
 runEval $ do
-   a <- rpar (f x)
-   b <- rpar (f y)
-   return (a,b)
+    a <- rpar (f x)
+    b <- rseq (f y)
+    rseq a
+    return (a,b)
 \end{lstlisting}
 
 rpar/rseq/rseq パターンは、f x および f y の結果を待ってから return する。
diff -r a145ceb871d3 -r 70bda541eb1d paper/chapter2.tex
--- a/paper/chapter2.tex	Sun Jan 19 23:30:12 2014 +0900
+++ b/paper/chapter2.tex	Fri Jan 24 11:55:19 2014 +0900
@@ -1,4 +1,114 @@
 \chapter{Haskellによるデータベースの設計}\label{ch:design}
 
-\section{目標}
-\section{Haskellで実装するメリット}
+\section{スケーラビリティのあるデータベース}
+本研究の目標はマルチスレッド環境でのスケーラビリティのあるデータベースの開発である。
+データベースは、ウェブサービスでの利用を前提とする。
+Twitter や Facebook などのタイムラインは多少遅延しても問題のないサービスである。
+これはデータの整合性を犠牲にできることを意味し、結果的に整合性が保たれればよいという考え方であり結果整合性と呼ばれる。
+本研究で開発するデータベースは結果整合性の特性を持つ。
+
+開発するデータベースはデータに並列にアクセスできる。
+マルチスレッド間でデータを共有する方法はいくつかある。
+最も一般的なのは、共有変数に対して排他制御を行う方法である。
+データにアクセスしてよいスレッドを１つに制限することで、そのデータが常に正しいことが保証される。
+しかしながら、１つのスレッドしかアクセスできないため、大量にデータにアクセスする場合ボトルネックとなってしまい並列度がでない。
+本研究では非破壊的木構造を採用する。
+非破壊的木構造は、最新の木構造はどれかという情報を取り扱う部分にのみ排他制御が必要で、並列に編集可能なデータ構造として扱うことができる。
+そのためマルチスレッド環境でのスケーラビリティのあるデータベースと相性がよい。
+また、ウェブサービスのデータ構造は木構造で表現することができる。
+
+\section{非破壊的木構造}
+非破壊的木構造は、木構造を書き換えることなく編集を行う手法である。
+排他制御を行わず、並列に読み書きを行うことが可能である。
+元の木構造は破壊されることがないため、自由にコピーを行うことができる。
+コピーを複数作成することでアクセスを分散させることも可能である。
+
+通常の破壊的木構造との違いを説明する。
+
+\subsection{破壊的木構造}
+破壊的木構造は、木構造を編集する際に木構造を書き換えることにより編集を実現する。
+図\ref{fig:destructive_tree_modification}では、ノード６をノード A に書き換える処理を行っている。
+
+
+\begin{figure}[!htbp]
+ \begin{center}
+  \includegraphics[width=100mm]{./images/destructive_tree_modification.pdf}
+ \end{center}
+ \caption{木構造の破壊的編集}
+ \label{fig:destructive_tree_modification}
+\end{figure}
+
+破壊的に編集する方法では、並列環境において問題が発生する。
+閲覧者が木構造を参照している間に編集者が木構造を書き換えると、閲覧者が参照を開始した時点での木構造ではなくなり整合性が崩れてしまう。
+整合性が崩れた状態では、正しい状態のコンテンツを参照することは出来ない（図\ref{fig:destructive_tree_modification_in_lace}）
+
+\begin{figure}[!htbp]
+ \begin{center}
+  \includegraphics[width=120mm]{./images/destructive_tree_modification_in_lace.pdf}
+ \end{center}
+ \caption{競合状態に陥る木構造の破壊的編集}
+ \label{fig:destructive_tree_modification_in_lace}
+\end{figure}
+
+この状態を回避するためには、木構造にアクセスする際に排他制御を行う。
+その場合、木構造に１つのスレッドしかアクセスできないため並列度が下がりスケーラビリティを損なってしまう。
+破壊的木構造では、スケーラビリティのあるデータベースの開発はできない。
+
+\subsection{非破壊的木構造}
+非破壊的木構造は、木構造を書き換えることなく編集を行うため、読み書きを並列に行うことが可能である。
+図\ref{fig:nondestructive_tree_modification}では、ノード 6 をノード A へ書き換える処理を行なっている。
+
+\begin{figure}[!htbp]
+ \begin{center}
+  \includegraphics[width=120mm]{./images/nondestructive_tree_modification.pdf}
+ \end{center}
+ \caption{木構造の非破壊的編集}
+ \label{fig:nondestructive_tree_modification}
+\end{figure}
+
+非破壊的木構造の基本的な戦略は、変更したいノードへのルートノードからのパスを全てコピーする。
+そして、パス上に存在しない (編集に関係のない) ノードはコピー元の木構造と共有することである。
+
+編集は以下の手順で行われる。
+
+\begin{enumerate}
+\item{変更したいノードまでのパスを求める。}
+\item{変更したいノードをコピーし、コピーしたノードの内容を変更する。}
+\item{求めたパス上に存在するノードをルートノードに向かって、コピーする。 コピーしたノードに一つ前にコピーしたノードを子供として追加する。}
+\item{影響のないノードをコピー元の木構造と共有する。}
+\end{enumerate}
+
+この編集方法を用いた場合、閲覧者が木構造を参照してる間に、木の変更を行っても問題がない。
+閲覧者は木が変更されたとしても、保持しているルートノードから整合性を崩さずに参照が可能である。
+ロックをせずに並列に読み書きが可能であるため、スケーラブルなシステムに有用であると考えられる。
+元の木構造は破壊されることがないため、自由にコピーを作成しても構わない。したがってアクセスの負荷の分散も可能である。
+
+\begin{figure}[!htbp]
+ \begin{center}
+  \includegraphics[width=140mm]{./images/nondestructive_tree_modification_in_lace.pdf}
+ \end{center}
+ \caption{並列に読み書きが可能な非破壊的木構造}
+ \label{fig:nondestructive_tree_modification_in_lace}
+\end{figure}
+
+
+\newpage
+\section{Haskellの並列処理}
+純粋関数型言語 Haskell は並列処理に向いていると言われる。
+しかしながら、安直にそう言い切ることはできない。
+参照透過性があるため、各々の関数の処理は独立している。
+そのため、並列で走らせても問題ないように思われるが、Haskell は遅延評価を行うため問題が発生する。
+遅延評価では、結果が必要になるまで評価せず、同じ呼び出しがあった場合メモ化を行うことで最適化を行う。
+並列で実行する際は、遅延評価を行っていては並列度を高めることができない。
+また、メモ化は結果をキャッシュするため各スレッド間で同期するコストが発生する。
+Haskell においても並列化によるコストが実際の処理とは別に発生するため、並列化箇所をよく見極める必要がある。
+
+Haskellでは、様々な並列化手法が提供されている。
+もちろんスレッドを直接操作することも可能である。
+本研究では、抽象度の高い Eval モナドを利用した。
+Eval モナドを利用することで、並列処理のために必要な処理の流れを分かりやすく記述することができる。
+しかしながら実行順序を細かく制御することはできない。
+Par モナドを利用すれば、並列処理の流れを細かく記述できるが、
+Eval モナドのように処理と並列処理の流れを分けて記述し、後からプログラムに並列処理を組み込むというようなことはできない。
+
+Haskellで並列処理を実装する場合は、どの並列化手法を採用するかということをよく考察する必要がある。
diff -r a145ceb871d3 -r 70bda541eb1d paper/introduciton.tex
--- a/paper/introduciton.tex	Sun Jan 19 23:30:12 2014 +0900
+++ b/paper/introduciton.tex	Fri Jan 24 11:55:19 2014 +0900
@@ -9,13 +9,13 @@
 ウェブサービスにおけるスケーラビリティを実現するための難点の一つとして、データベースが挙げられる。
 本研究の目的は、スケーラビリティを実現するデータベースの実装である。
 ウェブサービスにおけるスケーラビリティを実現するためには、並列にデータにアクセスできる設計が必要となる。
-本研究では、並列にデータへアクセスする手法として、非破壊的木構造を利用する。
-非破壊的木構造では、排他制御をせずにデータを読むことが可能でありスケーラビリティを確保できる。
+本研究では並列にデータへアクセスする手法として、非破壊的木構造を利用する。
+非破壊的木構造では、排他制御をせずにデータへアクセスすることが可能でありスケーラビリティを確保できる。
 
 データベースの実装には、純粋関数型言語 Haskell を用いる。
 Haskell を用いることで、表現力や純粋性のメリットを享受することができる。
 Haskell では、高度な型を一からつくり上げることができ、型情報を利用してコンパイル時に多くのエラーを捕捉できる。
-また、並列処理において副作用に依存する問題から解放され処理が簡潔になるといったメリットがあった。
+また、並列処理において副作用に依存する問題から解放され処理が簡潔になるといったメリットがある。
 
 本研究で実装したデータベースを用いて、簡易掲示板システムを開発し、既存の Java による非破壊的木構造データベースと性能比較を行う。
 
diff -r a145ceb871d3 -r 70bda541eb1d paper/master_paper.pdf
Binary file paper/master_paper.pdf has changed