|
10
|
1 \chapter{Haskellによる並列データベースの設計}\label{ch:design}
|
|
2
|
2
|
|
9
|
3 \section{スケーラビリティのあるデータベース}
|
|
|
4 本研究の目標はマルチスレッド環境でのスケーラビリティのあるデータベースの開発である。
|
|
|
5 データベースは、ウェブサービスでの利用を前提とする。
|
|
|
6 Twitter や Facebook などのタイムラインは多少遅延しても問題のないサービスである。
|
|
|
7 これはデータの整合性を犠牲にできることを意味し、結果的に整合性が保たれればよいという考え方であり結果整合性と呼ばれる。
|
|
|
8 本研究で開発するデータベースは結果整合性の特性を持つ。
|
|
|
9
|
|
|
10 開発するデータベースはデータに並列にアクセスできる。
|
|
|
11 マルチスレッド間でデータを共有する方法はいくつかある。
|
|
|
12 最も一般的なのは、共有変数に対して排他制御を行う方法である。
|
|
|
13 データにアクセスしてよいスレッドを１つに制限することで、そのデータが常に正しいことが保証される。
|
|
|
14 しかしながら、１つのスレッドしかアクセスできないため、大量にデータにアクセスする場合ボトルネックとなってしまい並列度がでない。
|
|
|
15 本研究では非破壊的木構造を採用する。
|
|
|
16 非破壊的木構造は、最新の木構造はどれかという情報を取り扱う部分にのみ排他制御が必要で、並列に編集可能なデータ構造として扱うことができる。
|
|
|
17 そのためマルチスレッド環境でのスケーラビリティのあるデータベースと相性がよい。
|
|
|
18 また、ウェブサービスのデータ構造は木構造で表現することができる。
|
|
|
19
|
|
|
20 \section{非破壊的木構造}
|
|
|
21 非破壊的木構造は、木構造を書き換えることなく編集を行う手法である。
|
|
|
22 排他制御を行わず、並列に読み書きを行うことが可能である。
|
|
|
23 元の木構造は破壊されることがないため、自由にコピーを行うことができる。
|
|
|
24 コピーを複数作成することでアクセスを分散させることも可能である。
|
|
|
25
|
|
|
26 通常の破壊的木構造との違いを説明する。
|
|
|
27
|
|
|
28 \subsection{破壊的木構造}
|
|
|
29 破壊的木構造は、木構造を編集する際に木構造を書き換えることにより編集を実現する。
|
|
|
30 図\ref{fig:destructive_tree_modification}では、ノード６をノード A に書き換える処理を行っている。
|
|
|
31
|
|
|
32
|
|
|
33 \begin{figure}[!htbp]
|
|
|
34 \begin{center}
|
|
|
35 \includegraphics[width=100mm]{./images/destructive_tree_modification.pdf}
|
|
|
36 \end{center}
|
|
|
37 \caption{木構造の破壊的編集}
|
|
|
38 \label{fig:destructive_tree_modification}
|
|
|
39 \end{figure}
|
|
|
40
|
|
|
41 破壊的に編集する方法では、並列環境において問題が発生する。
|
|
|
42 閲覧者が木構造を参照している間に編集者が木構造を書き換えると、閲覧者が参照を開始した時点での木構造ではなくなり整合性が崩れてしまう。
|
|
|
43 整合性が崩れた状態では、正しい状態のコンテンツを参照することは出来ない（図\ref{fig:destructive_tree_modification_in_lace}）
|
|
|
44
|
|
|
45 \begin{figure}[!htbp]
|
|
|
46 \begin{center}
|
|
|
47 \includegraphics[width=120mm]{./images/destructive_tree_modification_in_lace.pdf}
|
|
|
48 \end{center}
|
|
|
49 \caption{競合状態に陥る木構造の破壊的編集}
|
|
|
50 \label{fig:destructive_tree_modification_in_lace}
|
|
|
51 \end{figure}
|
|
|
52
|
|
|
53 この状態を回避するためには、木構造にアクセスする際に排他制御を行う。
|
|
|
54 その場合、木構造に１つのスレッドしかアクセスできないため並列度が下がりスケーラビリティを損なってしまう。
|
|
|
55 破壊的木構造では、スケーラビリティのあるデータベースの開発はできない。
|
|
|
56
|
|
|
57 \subsection{非破壊的木構造}
|
|
|
58 非破壊的木構造は、木構造を書き換えることなく編集を行うため、読み書きを並列に行うことが可能である。
|
|
|
59 図\ref{fig:nondestructive_tree_modification}では、ノード 6 をノード A へ書き換える処理を行なっている。
|
|
|
60
|
|
|
61 \begin{figure}[!htbp]
|
|
|
62 \begin{center}
|
|
|
63 \includegraphics[width=120mm]{./images/nondestructive_tree_modification.pdf}
|
|
|
64 \end{center}
|
|
|
65 \caption{木構造の非破壊的編集}
|
|
|
66 \label{fig:nondestructive_tree_modification}
|
|
|
67 \end{figure}
|
|
|
68
|
|
|
69 非破壊的木構造の基本的な戦略は、変更したいノードへのルートノードからのパスを全てコピーする。
|
|
|
70 そして、パス上に存在しない (編集に関係のない) ノードはコピー元の木構造と共有することである。
|
|
|
71
|
|
|
72 編集は以下の手順で行われる。
|
|
|
73
|
|
|
74 \begin{enumerate}
|
|
|
75 \item{変更したいノードまでのパスを求める。}
|
|
|
76 \item{変更したいノードをコピーし、コピーしたノードの内容を変更する。}
|
|
|
77 \item{求めたパス上に存在するノードをルートノードに向かって、コピーする。 コピーしたノードに一つ前にコピーしたノードを子供として追加する。}
|
|
|
78 \item{影響のないノードをコピー元の木構造と共有する。}
|
|
|
79 \end{enumerate}
|
|
|
80
|
|
|
81 この編集方法を用いた場合、閲覧者が木構造を参照してる間に、木の変更を行っても問題がない。
|
|
|
82 閲覧者は木が変更されたとしても、保持しているルートノードから整合性を崩さずに参照が可能である。
|
|
|
83 ロックをせずに並列に読み書きが可能であるため、スケーラブルなシステムに有用であると考えられる。
|
|
|
84 元の木構造は破壊されることがないため、自由にコピーを作成しても構わない。したがってアクセスの負荷の分散も可能である。
|
|
|
85
|
|
|
86 \begin{figure}[!htbp]
|
|
|
87 \begin{center}
|
|
|
88 \includegraphics[width=140mm]{./images/nondestructive_tree_modification_in_lace.pdf}
|
|
|
89 \end{center}
|
|
|
90 \caption{並列に読み書きが可能な非破壊的木構造}
|
|
|
91 \label{fig:nondestructive_tree_modification_in_lace}
|
|
|
92 \end{figure}
|
|
|
93
|
|
|
94
|
|
|
95 \newpage
|
|
|
96 \section{Haskellの並列処理}
|
|
|
97 純粋関数型言語 Haskell は並列処理に向いていると言われる。
|
|
|
98 しかしながら、安直にそう言い切ることはできない。
|
|
|
99 参照透過性があるため、各々の関数の処理は独立している。
|
|
|
100 そのため、並列で走らせても問題ないように思われるが、Haskell は遅延評価を行うため問題が発生する。
|
|
|
101 遅延評価では、結果が必要になるまで評価せず、同じ呼び出しがあった場合メモ化を行うことで最適化を行う。
|
|
|
102 並列で実行する際は、遅延評価を行っていては並列度を高めることができない。
|
|
|
103 また、メモ化は結果をキャッシュするため各スレッド間で同期するコストが発生する。
|
|
|
104 Haskell においても並列化によるコストが実際の処理とは別に発生するため、並列化箇所をよく見極める必要がある。
|
|
|
105
|
|
|
106 Haskellでは、様々な並列化手法が提供されている。
|
|
|
107 もちろんスレッドを直接操作することも可能である。
|
|
|
108 本研究では、抽象度の高い Eval モナドを利用した。
|
|
|
109 Eval モナドを利用することで、並列処理のために必要な処理の流れを分かりやすく記述することができる。
|
|
|
110 しかしながら実行順序を細かく制御することはできない。
|
|
|
111 Par モナドを利用すれば、並列処理の流れを細かく記述できるが、
|
|
|
112 Eval モナドのように処理と並列処理の流れを分けて記述し、後からプログラムに並列処理を組み込むというようなことはできない。
|
|
|
113
|
|
|
114 Haskellで並列処理を実装する場合は、どの並列化手法を採用するかということをよく考察する必要がある。
|
