Mercurial > hg > Papers > 2014 > toma-master
annotate paper/chapter3.tex @ 34:345eacdf29e4
add apendix
| author | Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Mon, 03 Feb 2014 16:54:48 +0900 |
| parents | 21f075c483cc |
| children | ec3488a9ddd4 |
| rev | line source |
|---|---|
| 10 | 1 \chapter{Haskellによる並列データベースの実装}\label{ch:impl} |
| 2 | |
| 23 | 3 本章では、並列データベース Jungle の実装について述べる。 |
| 4 まず、実装した非破壊的木構造データベースの利用方法について述べ、次に詳細な設計と実装について述べる。 | |
| 10 | 5 |
| 6 \section{木構造データベース Jungle} | |
| 23 | 7 非破壊的木構造データベース Jungle は、Haskell で実装された並列データベースである。 |
| 10 | 8 非破壊的木構造の方法に則ったAPIを提供する。 |
| 23 | 9 |
| 10 % 本研究では、HTTP サーバ Warp と組み合わせて掲示板システムとして利用しているが、他のシステムに組み込むことも可能である。 | |
| 11 Jungle の基本的な使い方の手順について説明する。 | |
| 12 \begin{enumerate} | |
| 13 \item{木構造を保持する Jungle を作成する（Jungle は複数の木を保持できる）} | |
| 14 \item{Jungle 内に新しい木を名前をつけて作成する} | |
| 15 \item{木の名前を用いて、ルートノードの取得を行い、データを参照する} | |
| 16 \item{もしくは、木の名前を用いて、ルートノードの更新を行う} | |
| 17 \end{enumerate} | |
| 18 | |
| 34 | 19 \subsubsection{Jungle 内部のデータ型} |
| 20 Jungle の内部のデータ型を表\ref{tab:components}に表す。 | |
| 21 木構造の集まりを表現する Jungle、単体の木構造を表現する Tree がある。 | |
| 22 Tree は外部から見えないように実装されている。 | |
| 23 | |
| 24 Jungle は複数の Tree の集まりである。Jungle と木構造の名前を利用して最新のルートノードを取得することができる。 | |
| 25 Node は子と属性を任意の数持てる。 | |
| 26 | |
| 27 \begin{table}[!htbp] | |
| 28 \caption{内部のデータ型} | |
| 29 \label{tab:components} | |
| 30 \begin{center} | |
| 31 \begin{tabular}{|c||c|} \hline | |
| 32 型名 & 概要 \\ \hline | |
| 33 Jungle & 木の作成・取得を担当する。 \\ \hline | |
| 34 Tree & 木の名前とルートノードの情報を保持している。 \\ \hline | |
| 35 Node & 基本的なデータ構造、子と属性を任意の数持てる。 \\ \hline | |
| 36 children & 子となるノードを任意の数持つことができる。 \\ \hline | |
| 37 attributes & Key と Value の組み合わせを任意の数持つことができる。 \\ \hline | |
| 38 \end{tabular} | |
| 39 \end{center} | |
| 40 \end{table} | |
| 41 | |
| 42 \newpage | |
| 43 | |
| 23 | 44 \subsubsection{Jungle と木の作成} |
| 45 Jungle は複数の非破壊的木構造を扱うことができる（図\ref{fig:jungle}）。 | |
| 10 | 46 |
| 23 | 47 \begin{figure}[!htbp] |
| 48 \begin{center} | |
| 49 \includegraphics[scale=0.7]{./images/jungle.pdf} | |
| 50 \end{center} | |
| 51 \caption{複数の木を扱えるJungle} | |
| 52 \label{fig:jungle} | |
| 53 \end{figure} | |
| 10 | 54 |
| 23 | 55 木構造の識別には、名前を利用する。 |
| 56 名前を付けて作成し、名前を用いることで参照を行う。 | |
| 57 | |
| 58 createJungle で、Jungle を作成できる。 | |
| 59 | |
| 10 | 60 木を作成するには、createTree を利用する。 |
| 23 | 61 createTree には、createJungle で作成した Jungle と新しい木の名前を渡す。 |
| 10 | 62 |
| 34 | 63 型の定義と実際のコードを示す。 |
| 64 | |
| 10 | 65 \begin{lstlisting}[caption=データベースと木の作成] |
| 34 | 66 createJungle :: IO Jungle |
| 67 createTree :: Jungle -> String -> IO () | |
| 68 | |
| 10 | 69 jungle <- createJungle |
| 70 createTree jungle "name of new tree here" | |
| 71 \end{lstlisting} | |
| 72 | |
| 73 \subsubsection{ルートノード} | |
| 23 | 74 非破壊的木構造データベース Jungle では、木の最新の状態を更新・参照するのにルートノードを使う。 |
| 75 ルートノードは、最新の木構造の根がどれかの情報を保持している（図\ref{fig:getrootnode}）。 | |
| 76 | |
| 77 \begin{figure}[!htbp] | |
| 78 \begin{center} | |
| 79 \includegraphics[scale=0.7]{./images/get_root_node.pdf} | |
| 80 \end{center} | |
| 81 \caption{ルートノード} | |
| 82 \label{fig:getrootnode} | |
| 83 \end{figure} | |
| 84 | |
| 10 | 85 ルートノードに関する API を説明する。 |
| 86 | |
| 87 getRootNode は、最新のルートノードを取得できる。 | |
| 23 | 88 データベースと木の名前を渡すことで利用できる。 |
| 89 例えば、図\ref{fig:getrootnode}の状態の時は、B というルートノードが取得できる。 | |
| 10 | 90 |
| 91 \begin{lstlisting}[caption=最新のルートノードの取得] | |
| 34 | 92 getRootNode :: Jungle -> String -> IO Node |
| 93 | |
| 10 | 94 node <- getRootNode jungle "your tree name here" |
| 95 \end{lstlisting} | |
| 96 | |
| 97 | |
| 98 木構造を編集する API は全て Node を受け取って Node を返す。 | |
| 23 | 99 その返ってきた Node をルートノードとして登録することで、木構造の最新のルートノードが更新される。 |
| 100 | |
| 10 | 101 updateRootNode は、データベースと木の名前、変更して返ってきた木構造を渡す。 |
| 23 | 102 |
| 103 updateRootNodeをした後は、getRootNodeで取得できるルートノードが更新された状態になっている。 | |
| 10 | 104 |
| 105 \begin{lstlisting}[caption=ルートノードの更新] | |
| 34 | 106 updateRootNode :: Jungle -> String -> Node -> IO () |
| 107 | |
| 10 | 108 updateRootNode jungle "your tree name here" node |
| 109 \end{lstlisting} | |
| 110 | |
| 111 updateRootNodeWithは、ノードを更新する関数とデータベース、木の名前を渡して利用する。 | |
| 112 ノードを更新する関数とは、ノードを受け取ってノードを返す関数である。 | |
| 113 このupdateRootNodeWithを利用することで、getRootNodeをした後、編集しupdateRootNodeを行う一連の操作がatomicallyに行われることが保証される。 | |
| 114 | |
| 115 \begin{lstlisting}[caption=関数を渡してルートノードの更新] | |
| 34 | 116 updateRootNodeWith :: (Node -> Node) -> Jungle -> String -> IO () |
| 117 | |
| 10 | 118 updateRootNodeWith func jungle "your tree name here" |
| 119 \end{lstlisting} | |
| 120 | |
| 121 \subsubsection{木の編集} | |
| 122 木の編集には、Node を使う。 | |
| 123 木の編集に用いる API は全て Node を受け取って Node を返す。 | |
| 124 非破壊的木構造を利用しているため、getRootNode などで取得してきた Node は他のスレッドと干渉することなく自由に参照、編集できる。 | |
| 125 これらの編集のためのAPIは、編集後updateRootNodeするか、ひとつの関数にまとめてupdateRootNodeWithをすることで木構造に反映させることができる。 | |
| 126 | |
| 127 編集対象のノードを指定するには、NodePath を利用する。 | |
| 128 NodePath は、ルートノードからスタートし、ノードの子どもの場所を次々に指定したものである。 | |
| 129 Haskell の基本データ構造であるリストを利用している。 | |
| 130 | |
| 131 | |
| 132 \begin{figure}[!htbp] | |
| 133 \begin{center} | |
| 134 \includegraphics[width=100mm]{./images/nodepath.pdf} | |
| 135 \end{center} | |
| 136 \caption{NodePath} | |
| 137 \label{fig:nodepath} | |
| 138 \end{figure} | |
| 139 | |
| 140 addNewChildAt で、ノードに新しい子を追加できる。 | |
| 141 addNewChildAt には、Node と NodePath を渡す。 | |
| 142 子には Position という場所の情報があるが、インクリメントしながら自動的に指定される。 | |
| 23 | 143 |
| 10 | 144 \begin{lstlisting}[caption=子の追加] |
| 34 | 145 addNewChildAt :: Node -> Path -> Node |
| 146 | |
| 10 | 147 new_node = addNewChildAt node [l,2] |
| 148 \end{lstlisting} | |
| 149 | |
| 150 deleteChildAt で、ノードの子を削除できる。 | |
| 151 deleteChildAt には、Node と NodePath、削除したい子のPositionを指定する。 | |
| 23 | 152 |
| 10 | 153 \begin{lstlisting}[caption=子の削除] |
| 34 | 154 deleteChildAt :: Node -> Path -> Position -> Node |
| 155 | |
| 10 | 156 new_node = deleteChildAt node [1,2] 0 |
| 157 \end{lstlisting} | |
| 158 | |
| 159 putAttribute で、ノードに属性を追加できる。 | |
| 160 putAttribute には、Node と NodePath、Key、Valueを渡す。 | |
| 161 Key は String、 Value は、ByteString である。 | |
| 23 | 162 |
| 10 | 163 \begin{lstlisting}[caption=属性の追加] |
| 34 | 164 putAttribute :: Node -> Path -> String -> ByteString -> Node |
| 165 | |
| 10 | 166 new_node = putAttribute node [1,2] "key" "value" |
| 167 \end{lstlisting} | |
| 168 | |
| 169 deleteAttribute で、ノードの属性を削除できる。 | |
| 170 deleteAttribute には、Node と NodePath、Keyを渡す。 | |
| 23 | 171 |
| 10 | 172 \begin{lstlisting}[caption=属性の削除] |
| 34 | 173 deleteAttribute :: Node -> Path -> String -> Node |
| 174 | |
| 10 | 175 new_node = deleteAttribute node [1,2] "key" |
| 176 \end{lstlisting} | |
| 177 | |
| 178 | |
| 179 \subsubsection{木の参照} | |
| 180 木の参照にも Node を用いる。 | |
| 181 様々な参照の API があるため、ひとつずつ紹介していく。 | |
| 182 | |
| 183 getAttributes は、対象の Path に存在する属性を Key を用いて参照できる。 | |
| 23 | 184 |
| 10 | 185 \begin{lstlisting}[caption=属性の取得] |
| 34 | 186 getAttributes :: Node -> Path -> String -> Maybe ByteString |
| 187 | |
| 10 | 188 bytestring = getAttributes node [1,2] "key" |
| 189 \end{lstlisting} | |
| 2 | 190 |
| 10 | 191 あるNodeに存在する全ての子に対して、参照を行いたい場合に利用する。 |
| 192 getChildren は、対象の Node が持つ全ての子を Node のリストとして返す | |
| 23 | 193 |
| 10 | 194 \begin{lstlisting}[caption=対象のNodeの全ての子を取得] |
| 34 | 195 getChildren :: Node -> Path -> [Node] |
| 196 | |
| 10 | 197 nodelist = getChildren node [1,2] |
| 198 \end{lstlisting} | |
| 199 | |
| 200 あるNodeに存在する全ての子に対して、参照を行いたい場合に利用する。 | |
| 201 getChildren と違い、子のPositionも取得できる。 | |
| 202 assocsChildren は、対象の Node が持つ全ての子を Position とのタプルにし、そのタプルのリストを返す。 | |
| 23 | 203 |
| 10 | 204 \begin{lstlisting}[caption=対象のNodeの全ての子とPositionを取得] |
| 34 | 205 assocsChildren :: Node -> Path -> [(Int, Node)] |
| 206 | |
| 10 | 207 nodelist = assocsChildren node [1,2] |
| 208 \end{lstlisting} | |
| 209 | |
| 210 | |
| 211 あるNodeに存在する全ての属性に対して、参照を行いたい場合に利用する。 | |
| 212 assocsAttribute は、対象の Node が持つ全ての属性を、Key と Value のタプルとし、そのタプルのリストを返す。 | |
| 23 | 213 |
| 10 | 214 \begin{lstlisting}[caption=対象のNodeの全てのAttributeのKeyとValueを取得] |
| 34 | 215 assocsAttribute :: Node -> Path -> [(String, B.ByteString)] |
| 216 | |
| 10 | 217 attrlist = assocsAttribute node [1,2] |
| 218 \end{lstlisting} | |
| 219 | |
| 220 numOfChild では、対象の Node が持つ子どもの数を取得できる。 | |
| 23 | 221 |
| 10 | 222 \begin{lstlisting}[caption=対象のNodeの子どもの数を取得] |
| 34 | 223 numOfChild :: Node -> Path -> Int |
| 224 | |
| 10 | 225 num = numOfChild node [1,2] |
| 226 \end{lstlisting} | |
| 227 | |
| 228 currentChild では、対象の Node が持つ最新の子を取得できる。 | |
| 23 | 229 |
| 10 | 230 \begin{lstlisting}[caption=対象のNodeの最新の子を取得] |
| 34 | 231 currentChild :: Node -> Path -> Maybe Node |
| 232 | |
| 10 | 233 node = currentChild node [1,2] |
| 234 \end{lstlisting} | |
| 235 | |
| 23 | 236 \subsubsection{並列実行} |
| 237 木構造データベース Jungle は、並列に実行することができる。 | |
| 238 アプリケーション側で、データベースを参照や変更する際に各スレッドから呼び出しても問題ない。 | |
| 239 利用方法も、シングルスレッドで実行する場合と同じである。 | |
| 240 | |
| 241 \clearpage | |
| 10 | 242 \section{木構造データベース Jungle の実装} |
| 243 \subsubsection{開発環境} | |
| 244 実装には、Haskell を用いる。 | |
| 23 | 245 コンパイラは、Haskell の並列実行に対応した Glasgow Haskell Compiler (GHC) を用いる。 |
| 25 | 246 GHC は、Haskell で最も広く使われているコンパイラである\cite{ghc}。 |
| 23 | 247 並列実行のためのMonadや、スレッドセーフな参照型を提供している。 |
| 248 | |
| 10 | 249 \subsection{Jungle} |
| 250 Jungle は木構造の集まりを表現する。 | |
| 251 木には名前がついており、ルートノードの情報も一緒に保持している。 | |
| 252 | |
| 253 \subsubsection{木の取り扱い} | |
| 254 Jungle の木の取り扱いには、Haskell の Data.Map を利用している。 | |
| 23 | 255 |
| 10 | 256 Haskell で連想配列を扱いたい場合、平衡木によって実装された Data.Map を一般的に用いる。 |
| 257 Haskell のライブラリには配列や、ハッシュ・テーブルといったものも存在するがあまり使われない。 | |
| 258 配列は参照に適しているが、データを追加する際に配列を再作成するためコストが大きい。 | |
| 259 ハッシュ・テーブルは更新操作に副作用を伴うため、IOモナドの中でしか使うことが出来ず、扱いにくい。 | |
| 260 Data.Mapは、挿入や参照が O(log n) で済む。 | |
| 261 | |
| 262 また、木の取り扱いには Haskell のソフトウェア・トランザクショナル・メモリ (STM) を利用して状態を持たせ、スレッド間で共有できるようにしてある。 | |
| 23 | 263 これは、各スレッドから木構造を新たに作成できるようにするためである。 |
| 10 | 264 STM は、スレッド間でデータを共有するためのツールである。STM を利用することでロック忘れによる競合状態や、デッドロックといった問題から解放される。 |
| 23 | 265 |
| 34 | 266 \begin{lstlisting}[label=src:node, caption=Treeのデータ型の定義] |
| 267 data Jungle = Jungle { getJungleMap :: (TVar (Map String Tree)) } | |
| 268 \end{lstlisting} | |
| 269 | |
| 270 TVar というのは、Transactional variablesの略で、STM で管理する変数に対して利用する。 | |
| 271 | |
| 23 | 272 \subsection{Tree} |
| 273 Jungleが保持する木構造は、内部的には Tree というデータ型で保持している。 | |
| 274 Tree は木の名前と、ルートノードの情報を持っている。 | |
| 275 実際にユーザがJungleを利用する際は、Jungle と木の名前を使ってルートノードを取ってくるため、Tree という構造は見えない。 | |
| 10 | 276 |
| 23 | 277 ルートノードの情報はスレッド間で状態を共有する必要がある。 |
| 278 スレッドセーフに取り扱う必要があるため、この情報も Haskell の ソフトウェア・トランザクショナル・メモリ (STM) を用いて管理している。 | |
| 279 | |
| 280 \begin{lstlisting}[label=src:node, caption=Treeのデータ型の定義] | |
| 281 data Tree = Tree | |
| 282 { rootNode :: (TVar Node) | |
| 283 , treeName :: String } | |
| 284 \end{lstlisting} | |
| 285 | |
| 10 | 286 \subsection{Node} |
| 287 Node は木構造を表現するデータ構造である。 | |
| 288 再帰的に定義されている。 | |
| 289 各ノードは Children としてノードを複数持つことができる（図\ref{fig:node_components}）。 | |
| 290 | |
| 291 \begin{figure}[!htbp] | |
| 292 \begin{center} | |
| 293 \includegraphics[width=110mm]{./images/node_component.pdf} | |
| 294 \end{center} | |
| 295 \caption{Nodeの構成要素} | |
| 296 \label{fig:node_components} | |
| 297 \end{figure} | |
| 298 | |
| 299 Children および Attributes も Data.Map を用いて定義されている（ソースコード \ref{src:node}）。 | |
| 300 | |
| 301 \begin{lstlisting}[label=src:node, caption=Nodeのデータ型の定義] | |
| 302 data Node = Node | |
| 303 { children :: (Map Int Node) | |
| 304 , attributes :: (Map String ByteString) } | |
| 305 \end{lstlisting} | |
| 306 | |
| 307 | |
| 23 | 308 \clearpage |
|
20
ff03e6179f19
describe the design.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
309 \section{Haskellの並列処理} |
|
ff03e6179f19
describe the design.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
310 純粋関数型言語 Haskell は並列処理に向いていると言われる。 |
|
ff03e6179f19
describe the design.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
311 しかしながら、安直にそう言い切ることはできない。 |
|
ff03e6179f19
describe the design.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
312 参照透過性があるため、各々の関数の処理は独立している。 |
|
ff03e6179f19
describe the design.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
313 そのため、並列で走らせても問題ないように思われるが、Haskell は遅延評価を行うため問題が発生する。 |
| 23 | 314 遅延評価では、結果が必要になるまで評価されない。 |
| 315 実装においては、deepseqを用いて即時評価を挟むか、出力など計算が必要となる処理を挟むようにする。 | |
|
20
ff03e6179f19
describe the design.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
316 |
|
ff03e6179f19
describe the design.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
317 Haskellでは、様々な並列化手法が提供されている。 |
| 23 | 318 スレッドを直接操作することも可能である。 |
| 319 | |
|
20
ff03e6179f19
describe the design.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
320 本研究では、抽象度の高い Eval モナドを利用した。 |
| 23 | 321 Eval モナドを利用することで、並列処理のために必要な処理の流れを分かりやすく記述することができた。 |
| 322 しかしながら Eval モナドは実行順序を細かく制御することはできない。 | |
|
20
ff03e6179f19
describe the design.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
323 Par モナドを利用すれば、並列処理の流れを細かく記述できるが、 |
|
ff03e6179f19
describe the design.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
324 Eval モナドのように処理と並列処理の流れを分けて記述し、後からプログラムに並列処理を組み込むというようなことはできない。 |
|
ff03e6179f19
describe the design.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
325 |
|
ff03e6179f19
describe the design.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
326 Haskellで並列処理を実装する場合は、どの並列化手法を採用するかということをよく考察する必要がある。 |
|
ff03e6179f19
describe the design.
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
10
diff
changeset
|
327 |
| 10 | 328 \section{Haskell の生産性} |
| 329 Java を用いた Jungle の実装と比較して、コード行数が約 3000 行から約 300 行へと短くなった。 | |
| 330 | |
| 331 これは Haskell の表現力が高いためである。 | |
| 23 | 332 Haskell では、独自のデータ型を簡単に作成することができる。 |
| 10 | 333 再帰的なデータ構造の定義も容易である。 |
| 334 共通の性質を扱うための型クラスという仕組みが存在し、既存のライブラリを作成したデータ型に利用できる。 | |
| 335 また、Haskellは参照透過性を持つため、コードの再利用が行い易く、関数同士の結合も簡単である。 | |
| 336 | |
| 337 同じような機能を実装する場合でも、Java と比較してコード行数が短くなり生産性が向上する。 |