Papers/2014/toma-master: paper/chapter2.tex annotate

annotate paper/chapter2.tex @ 40:bd30d93097da

describe Jungle and Tree

author	Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
date	Tue, 04 Feb 2014 04:41:52 +0900
parents	ec3488a9ddd4
children	e32c9a53310c

rev	line source
40 bd30d93097da describe Jungle and Tree Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 35 diff changeset	1 \chapter{Haskellによる\\並列データベースの設計}\label{ch:design}
2 d8b94e828d79 add tex files Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	2
35 ec3488a9ddd4 fix Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 34 diff changeset	3 \section{マルチコアプロセッサで十分な性能を得るためには}
34 345eacdf29e4 add apendix Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	4 現在、CPU はマルチコア化が進んでいる。
40 bd30d93097da describe Jungle and Tree Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 35 diff changeset	5 マルチコアプロセッサで線形に性能向上をするためには、処理全体で高い並列度を保つ必要がある。
bd30d93097da describe Jungle and Tree Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 35 diff changeset	6 アムダールの法則\cite{amdahl}によると、並列度が80 \% の場合、どんなにコア数を増やしても性能向上率は5倍にしかならない。
bd30d93097da describe Jungle and Tree Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 35 diff changeset	7
34 345eacdf29e4 add apendix Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	8 % ウェブサービスでは、ニーズの変化に柔軟に対応できる能力が求められる。
345eacdf29e4 add apendix Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	9 % 利用者や負荷の増大に対し、CPU のコア数に応じてパフォーマンスを線形に向上できる能力、すなわちスケーラビリティが必要となる。
345eacdf29e4 add apendix Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	10 % スケーラビリティが線形的であれば、リソースの追加に比例したパフォーマンスを得ることが可能である。
345eacdf29e4 add apendix Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	11 % 一方、スケーラビリティが線形的でないと、いくらリソースを追加しても必要なパフォーマンスが得られないというケースもありえる。
20 ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	12
40 bd30d93097da describe Jungle and Tree Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 35 diff changeset	13 CPU コア数に応じて、データベースを線形に性能向上させたい場合、別々の CPU コアから同時にデータベースへアクセスできるようにし、並列度を高める必要がある。
20 ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	14 通常は、同一のデータへアクセスする場合、競合が発生してしまい処理性能に限界が生じる。
9 70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	15
20 ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	16 本研究では、非破壊的木構造という手法を用いて競合が発生する問題を解決する。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	17 競合を発生させないためには、既にあるデータを変更しなければよい。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	18 非破壊的木構造は、変更元となる木構造を変更しない。
34 345eacdf29e4 add apendix Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	19 そのため、別々の CPU コアから並列にアクセスが可能であり、スケーラビリティを実現できる。
9 70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	20
20 ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	21 \newpage
34 345eacdf29e4 add apendix Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	22 \section{非破壊的木構造}
9 70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	23 非破壊的木構造は、木構造を書き換えることなく編集を行う手法である。
20 ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	24 既にあるデータを変更しないため、データの競合状態が発生せず、並列に読み書きが行える。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	25
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	26 また、元の木構造は破壊されることがないため、自由にコピーを行うことができる。
9 70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	27 コピーを複数作成することでアクセスを分散させることも可能である。
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	28
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	29 図\ref{fig:nondestructive_tree_modification}では、ノード 6 をノード A へ書き換える処理を行なっている。
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	30
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	31 \begin{figure}[!htbp]
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	32 \begin{center}
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	33 \includegraphics[width=120mm]{./images/nondestructive_tree_modification.pdf}
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	34 \end{center}
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	35 \caption{木構造の非破壊的編集}
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	36 \label{fig:nondestructive_tree_modification}
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	37 \end{figure}
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	38
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	39 この編集方法を用いた場合、閲覧者が木構造を参照してる間に、木の変更を行っても問題がない。
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	40 閲覧者は木が変更されたとしても、保持しているルートノードから整合性を崩さずに参照が可能である。
20 ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	41 排他制御をせずに並列に読み書きが可能であるため、スケーラブルなシステムに有用である。
9 70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	42 元の木構造は破壊されることがないため、自由にコピーを作成しても構わない。したがってアクセスの負荷の分散も可能である。
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	43
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	44 \begin{figure}[!htbp]
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	45 \begin{center}
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	46 \includegraphics[width=140mm]{./images/nondestructive_tree_modification_in_lace.pdf}
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	47 \end{center}
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	48 \caption{並列に読み書きが可能な非破壊的木構造}
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	49 \label{fig:nondestructive_tree_modification_in_lace}
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	50 \end{figure}
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	51
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	52
70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	53 \newpage
20 ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	54 \section{ルートノード}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	55 非破壊的木構造では、ルートノードの管理が重要である。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	56 ルートノードは、木の最新の状態を更新・参照するのに使う。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	57 ルートノードの情報は、全てのスレッドで共有する必要があり、スレッドセーフに取り扱う必要がある。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	58 一度ルートノードの情報を取得すれば、その後は排他制御なしに木構造へアクセスできる（図\ref{fig:rootnode}）。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	59
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	60 \begin{figure}[!htbp]
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	61 \begin{center}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	62 \includegraphics[scale=0.6]{./images/rootnode.pdf}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	63 \end{center}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	64 \caption{排他制御なしの非破壊的木構造のアクセス}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	65 \label{fig:rootnode}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	66 \end{figure}
9 70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	67
20 ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	68 ルートノードはスレッド間で共有する状態を持つため、Haskell では IO モナドを用いる必要がある。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	69 これには、Haskell のソフトウェア・トランザクショナル・メモリ（STM）を利用する。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	70 STM は排他制御を行わず、スレッドセーフに状態を扱うことができる。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	71 STM を利用することでロック忘れによる競合状態や、デッドロックといった問題から解放される。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	72 STM は、STM モナドという特殊なモナドの中でのみ変更できる。
40 bd30d93097da describe Jungle and Tree Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 35 diff changeset	73 STM モナドの中で変更したアクションのブロックを atomically コンビネータを使ってトランザクションとして実行する。（atomically コンビネータを用いることで IO モナドとして返される）。
20 ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	74 いったんブロック内に入るとそこから出るまでは、そのブロック内の変更は他のスレッドから見ることはできない。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	75 こちら側のスレッドからも他のスレッドによる変更はみることはできず、実行は完全に孤立して行われる。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	76 トランザクションから出る時に、以下のことが１つだけ起こる。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	77 \begin{itemize}
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	78 \item 同じデータを平行して変更したスレッドが他になければ、加えた変更が他のスレッドから見えるようになる。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	79 \item そうでなければ、変更を実際に実行せずに破棄し、アクションのブロックを再度実行する。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	80 \end{itemize}
9 70bda541eb1d add pdf Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 6 diff changeset	81
20 ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	82 STM は排他制御を行わないため、簡単に扱うことができる。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	83 ルートノードの情報の取得だけならば、並列に取得できる。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	84 ルートノードの情報の更新の場合は、他から変更があれば再度やり直すということが自動的に行われる。
ff03e6179f19 describe the design. Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	85
34 345eacdf29e4 add apendix Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	86 以前の実装では、ルートノードだけではなく非破壊的木構造全体をSTMで管理していた\cite{toma:2013}。
345eacdf29e4 add apendix Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	87 しかしながら、非破壊的木構造全体をSTMで管理すると並列実行時に性能が出ないため、ルートノードのみの管理に変更を行った。

Mercurial > hg > Papers > 2014 > toma-master

annotate paper/chapter2.tex @ 40:bd30d93097da