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

\section{マルチコアプロセッサで十分な性能を得るためには}
現在, CPU はマルチコア化が進んでいる. 
マルチコアプロセッサで線形に性能向上をするためには, 処理全体で高い並列度を保つ必要がある. 
アムダールの法則\cite{amdahl}によると, 並列度が80 \% の場合, どんなにコア数を増やしても性能向上率は5倍にしかならない. 

% ウェブサービスでは, ニーズの変化に柔軟に対応できる能力が求められる. 
% 利用者や負荷の増大に対し, 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}

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

\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で管理すると並列実行時に性能が出ないため, ルートノードのみの管理に変更を行った.