\chapter{Haskellによる並列データベースの設計}\label{ch:design}

\section{マルチプロセッサで十分な性能を得るためには}
現在、CPU はマルチコア化が進んでいる。
マルチコアプロセッサで線形に性能向上をするためには、処理全体で高い並列度を保たなければならない\cite{amdahl}。
% ウェブサービスでは、ニーズの変化に柔軟に対応できる能力が求められる。
% 利用者や負荷の増大に対し、CPU のコア数に応じてパフォーマンスを線形に向上できる能力、すなわちスケーラビリティが必要となる。
% スケーラビリティが線形的であれば、リソースの追加に比例したパフォーマンスを得ることが可能である。
% 一方、スケーラビリティが線形的でないと、いくらリソースを追加しても必要なパフォーマンスが得られないというケースもありえる。

CPU コア数に応じて、データベースを線形に性能向上させたい場合、別々の CPU コアから同時にデータベースへアクセスできればよい。
通常は、同一のデータへアクセスする場合、競合が発生してしまい処理性能に限界が生じる。

本研究では、非破壊的木構造という手法を用いて競合が発生する問題を解決する。
競合を発生させないためには、既にあるデータを変更しなければよい。
非破壊的木構造は、変更元となる木構造を変更しない。
そのため、別々の CPU コアから並列にアクセスが可能であり、スケーラビリティを実現できる。

\newpage
\section{非破壊的木構造}
非破壊的木構造は、木構造を書き換えることなく編集を行う手法である。
既にあるデータを変更しないため、データの競合状態が発生せず、並列に読み書きが行える。

また、元の木構造は破壊されることがないため、自由にコピーを行うことができる。
コピーを複数作成することでアクセスを分散させることも可能である。

図\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{変更したいノードまでのパスを求める(図\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
この編集方法を用いた場合、閲覧者が木構造を参照してる間に、木の変更を行っても問題がない。
閲覧者は木が変更されたとしても、保持しているルートノードから整合性を崩さずに参照が可能である。
排他制御をせずに並列に読み書きが可能であるため、スケーラブルなシステムに有用である。
元の木構造は破壊されることがないため、自由にコピーを作成しても構わない。したがってアクセスの負荷の分散も可能である。

\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{ルートノード}
非破壊的木構造では、ルートノードの管理が重要である。
ルートノードは、木の最新の状態を更新・参照するのに使う。
ルートノードの情報は、全てのスレッドで共有する必要があり、スレッドセーフに取り扱う必要がある。
一度ルートノードの情報を取得すれば、その後は排他制御なしに木構造へアクセスできる（図\ref{fig:rootnode}）。

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[scale=0.6]{./images/rootnode.pdf}
 \end{center}
 \caption{排他制御なしの非破壊的木構造のアクセス}
 \label{fig:rootnode}
\end{figure}

ルートノードはスレッド間で共有する状態を持つため、Haskell では IO モナドを用いる必要がある。
これには、Haskell のソフトウェア・トランザクショナル・メモリ（STM）を利用する。
STM は排他制御を行わず、スレッドセーフに状態を扱うことができる。
STM を利用することでロック忘れによる競合状態や、デッドロックといった問題から解放される。
STM は、STM モナドという特殊なモナドの中でのみ変更できる。
STM モナドの中で変更したアクションのブロックを atomically コンビネータを使ってトランザクションとして実行する（atomically コンビネータを用いることで IO モナドとして返される）。
いったんブロック内に入るとそこから出るまでは、そのブロック内の変更は他のスレッドから見ることはできない。
こちら側のスレッドからも他のスレッドによる変更はみることはできず、実行は完全に孤立して行われる。
トランザクションから出る時に、以下のことが１つだけ起こる。
\begin{itemize}
 \item 同じデータを平行して変更したスレッドが他になければ、加えた変更が他のスレッドから見えるようになる。
 \item そうでなければ、変更を実際に実行せずに破棄し、アクションのブロックを再度実行する。
\end{itemize}

STM は排他制御を行わないため、簡単に扱うことができる。
ルートノードの情報の取得だけならば、並列に取得できる。
ルートノードの情報の更新の場合は、他から変更があれば再度やり直すということが自動的に行われる。

以前の実装では、ルートノードだけではなく非破壊的木構造全体をSTMで管理していた\cite{toma:2013}。
しかしながら、非破壊的木構造全体をSTMで管理すると並列実行時に性能が出ないため、ルートノードのみの管理に変更を行った。