view paper/chapter2.tex @ 20:ff03e6179f19

describe the design.
author Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
date Sun, 02 Feb 2014 07:10:55 +0900
parents a349b2c01cfe
children 345eacdf29e4
line wrap: on
line source

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

\section{スケーラビリティのあるデータベースを実現するには}
ウェブサービスでは、ニーズの変化に柔軟に対応できる能力が求められる。
利用者や負荷の増大に対し、CPU のコア数に応じてパフォーマンスを線形に向上できる能力、すなわちスケーラビリティが必要となる。
スケーラビリティが線形的であれば、リソースの追加に比例したパフォーマンスを得ることが可能である。
一方、スケーラビリティが線形的でないと、いくらリソースを追加しても必要なパフォーマンスが得られないというケースもありえる。

ウェブサービスにおいてデータベースは切り離すことのできない要素である。
スケーラビリティの実現をするには、データベースの並列度が重要になる。
CPU のコア数に応じてパフォーマンスを向上させる場合、別々の CPU コアから同時にデータベースへアクセスできればよい。
通常は、同一のデータへアクセスする場合、競合が発生してしまい処理性能に限界が生じる。

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

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

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

通常の破壊的木構造との違いを説明する。

\subsection{破壊的木構造}
破壊的木構造は、木構造を編集する際に木構造を書き換えることにより編集を実現する。
図\ref{fig:destructive_tree_modification}では、ノード 6 をノード 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}

この状態を回避するためには、木構造にアクセスする際に排他制御を行う。
その場合、木構造に1つのスレッドしかアクセスできないため並列度が下がりスケーラビリティを損なってしまう。
破壊的木構造では、スケーラビリティのあるデータベースの開発はできない。

\newpage
\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{変更したいノードまでのパスを求める(図\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}

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

\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 モナドとして返される)。
いったんブロック内に入るとそこから出るまでは、そのブロック内の変更は他のスレッドから見ることはできない。
こちら側のスレッドからも他のスレッドによる変更はみることはできず、実行は完全に孤立して行われる。
トランザクションから出る時に、以下のことが1つだけ起こる。
\begin{itemize}
 \item 同じデータを平行して変更したスレッドが他になければ、加えた変更が他のスレッドから見えるようになる。
 \item そうでなければ、変更を実際に実行せずに破棄し、アクションのブロックを再度実行する。
\end{itemize}

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