Mercurial > hg > Papers > 2014 > toma-master
annotate paper/chapter3.tex @ 10:a349b2c01cfe
add graffle
| author | Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Tue, 28 Jan 2014 06:40:52 +0900 |
| parents | 37efb7dc0bda |
| children | ff03e6179f19 |
| rev | line source |
|---|---|
| 10 | 1 \chapter{Haskellによる並列データベースの実装}\label{ch:impl} |
| 2 | |
| 3 本章では、並列データベースの実装について述べる。 | |
| 4 まず、実装した木構造データベースの利用方法について述べ、次に詳細な設計と実装について述べる。 | |
| 5 | |
| 6 \section{木構造データベース Jungle} | |
| 7 木構造データベース Jungle は、Haskell で実装された並列データベースである。 | |
| 8 非破壊的木構造の方法に則ったAPIを提供する。 | |
| 9 本研究では、HTTP サーバ Warp と組み合わせて掲示板システムとして利用しているが、他のシステムに組み込むことも可能である。 | |
| 10 | |
| 11 \subsubsection{木の作成} | |
| 12 Jungle は複数の木構造を保持する事ができる。 | |
| 13 木構造は、名前を付けて管理する。 | |
| 14 名前を利用することで他の木構造と識別し、作成・編集を行う。 | |
| 15 | |
| 16 createJungle で、データベースを作成できる。 | |
| 17 木を作成するには、createTree を利用する。 | |
| 18 createTree には、createJungle で作成したデータベースと新しい木の名前を渡す。\\ | |
| 19 | |
| 20 \begin{lstlisting}[caption=データベースと木の作成] | |
| 21 jungle <- createJungle | |
| 22 createTree jungle "name of new tree here" | |
| 23 \end{lstlisting} | |
| 24 | |
| 25 \subsubsection{ルートノード} | |
| 26 Jungle は参照および編集に木構造のルートノードを活用する。 | |
| 27 ルートノードに関する API を説明する。 | |
| 28 | |
| 29 getRootNode は、最新のルートノードを取得できる。 | |
| 30 データベースと木の名前を渡すことで利用する。\\ | |
| 31 | |
| 32 \begin{lstlisting}[caption=最新のルートノードの取得] | |
| 33 node <- getRootNode jungle "your tree name here" | |
| 34 \end{lstlisting} | |
| 35 | |
| 36 | |
| 37 木構造を編集する API は全て Node を受け取って Node を返す。 | |
| 38 その返ってきた Node をルートノードとして新たに登録することで木構造が更新される。 | |
| 39 updateRootNode は、データベースと木の名前、変更して返ってきた木構造を渡す。 | |
| 40 updateRootNodeをした後は、getRootNodeで取得できるルートノードが更新された状態になっている。\\ | |
| 41 | |
| 42 \begin{lstlisting}[caption=ルートノードの更新] | |
| 43 updateRootNode jungle "your tree name here" node | |
| 44 \end{lstlisting} | |
| 45 | |
| 46 updateRootNodeWithは、ノードを更新する関数とデータベース、木の名前を渡して利用する。 | |
| 47 ノードを更新する関数とは、ノードを受け取ってノードを返す関数である。 | |
| 48 このupdateRootNodeWithを利用することで、getRootNodeをした後、編集しupdateRootNodeを行う一連の操作がatomicallyに行われることが保証される。 | |
| 49 \\ | |
| 50 | |
| 51 \begin{lstlisting}[caption=関数を渡してルートノードの更新] | |
| 52 updateRootNodeWith func jungle "your tree name here" | |
| 53 \end{lstlisting} | |
| 54 | |
| 55 \subsubsection{木の編集} | |
| 56 木の編集には、Node を使う。 | |
| 57 木の編集に用いる API は全て Node を受け取って Node を返す。 | |
| 58 非破壊的木構造を利用しているため、getRootNode などで取得してきた Node は他のスレッドと干渉することなく自由に参照、編集できる。 | |
| 59 これらの編集のためのAPIは、編集後updateRootNodeするか、ひとつの関数にまとめてupdateRootNodeWithをすることで木構造に反映させることができる。 | |
| 60 | |
| 61 編集対象のノードを指定するには、NodePath を利用する。 | |
| 62 NodePath は、ルートノードからスタートし、ノードの子どもの場所を次々に指定したものである。 | |
| 63 Haskell の基本データ構造であるリストを利用している。 | |
| 64 | |
| 65 | |
| 66 \begin{figure}[!htbp] | |
| 67 \begin{center} | |
| 68 \includegraphics[width=100mm]{./images/nodepath.pdf} | |
| 69 \end{center} | |
| 70 \caption{NodePath} | |
| 71 \label{fig:nodepath} | |
| 72 \end{figure} | |
| 73 | |
| 74 addNewChildAt で、ノードに新しい子を追加できる。 | |
| 75 addNewChildAt には、Node と NodePath を渡す。 | |
| 76 子には Position という場所の情報があるが、インクリメントしながら自動的に指定される。 | |
| 77 \\ | |
| 78 \begin{lstlisting}[caption=子の追加] | |
| 79 new_node = addNewChildAt node [l,2] | |
| 80 \end{lstlisting} | |
| 81 | |
| 82 deleteChildAt で、ノードの子を削除できる。 | |
| 83 deleteChildAt には、Node と NodePath、削除したい子のPositionを指定する。 | |
| 84 \\ | |
| 85 \begin{lstlisting}[caption=子の削除] | |
| 86 new_node = deleteChildAt node [1,2] 0 | |
| 87 \end{lstlisting} | |
| 88 | |
| 89 putAttribute で、ノードに属性を追加できる。 | |
| 90 putAttribute には、Node と NodePath、Key、Valueを渡す。 | |
| 91 Key は String、 Value は、ByteString である。 | |
| 92 \\ | |
| 93 \begin{lstlisting}[caption=属性の追加] | |
| 94 new_node = putAttribute node [1,2] "key" "value" | |
| 95 \end{lstlisting} | |
| 96 | |
| 97 deleteAttribute で、ノードの属性を削除できる。 | |
| 98 deleteAttribute には、Node と NodePath、Keyを渡す。 | |
| 99 \\ | |
| 100 \begin{lstlisting}[caption=属性の削除] | |
| 101 new_node = deleteAttribute node [1,2] "key" | |
| 102 \end{lstlisting} | |
| 103 | |
| 104 | |
| 105 \subsubsection{木の参照} | |
| 106 木の参照にも Node を用いる。 | |
| 107 様々な参照の API があるため、ひとつずつ紹介していく。 | |
| 108 | |
| 109 getAttributes は、対象の Path に存在する属性を Key を用いて参照できる。 | |
| 110 \\ | |
| 111 \begin{lstlisting}[caption=属性の取得] | |
| 112 bytestring = getAttributes node [1,2] "key" | |
| 113 \end{lstlisting} | |
| 2 | 114 |
| 10 | 115 あるNodeに存在する全ての子に対して、参照を行いたい場合に利用する。 |
| 116 getChildren は、対象の Node が持つ全ての子を Node のリストとして返す | |
| 117 \\ | |
| 118 \begin{lstlisting}[caption=対象のNodeの全ての子を取得] | |
| 119 nodelist = getChildren node [1,2] | |
| 120 \end{lstlisting} | |
| 121 | |
| 122 あるNodeに存在する全ての子に対して、参照を行いたい場合に利用する。 | |
| 123 getChildren と違い、子のPositionも取得できる。 | |
| 124 assocsChildren は、対象の Node が持つ全ての子を Position とのタプルにし、そのタプルのリストを返す。 | |
| 125 \\ | |
| 126 \begin{lstlisting}[caption=対象のNodeの全ての子とPositionを取得] | |
| 127 nodelist = assocsChildren node [1,2] | |
| 128 \end{lstlisting} | |
| 129 | |
| 130 | |
| 131 あるNodeに存在する全ての属性に対して、参照を行いたい場合に利用する。 | |
| 132 assocsAttribute は、対象の Node が持つ全ての属性を、Key と Value のタプルとし、そのタプルのリストを返す。 | |
| 133 \\ | |
| 134 \begin{lstlisting}[caption=対象のNodeの全てのAttributeのKeyとValueを取得] | |
| 135 attrlist = assocsAttribute node [1,2] | |
| 136 \end{lstlisting} | |
| 137 | |
| 138 numOfChild では、対象の Node が持つ子どもの数を取得できる。 | |
| 139 \\ | |
| 140 \begin{lstlisting}[caption=対象のNodeの子どもの数を取得] | |
| 141 num = numOfChild node [1,2] | |
| 142 \end{lstlisting} | |
| 143 | |
| 144 currentChild では、対象の Node が持つ最新の子を取得できる。 | |
| 145 \\ | |
| 146 \begin{lstlisting}[caption=対象のNodeの最新の子を取得] | |
| 147 node = currentChild node [1,2] | |
| 148 \end{lstlisting} | |
| 149 | |
| 150 \section{木構造データベース Jungle の実装} | |
| 151 \subsubsection{開発環境} | |
| 152 実装には、Haskell を用いる。 | |
| 153 \subsubsection{全体の構造} | |
| 154 木構造の集まりを表現する Jungle、単体の木構造を表現する Node から構成される。 | |
| 155 Jungle は複数の Node の集まりである。Jungle を利用して最新のルートノードを取得することができる。 | |
| 156 Node は子と属性を任意の数持てる。 | |
| 157 | |
| 158 \begin{table}[!htbp] | |
| 159 \caption{全体の構造} | |
| 160 \label{tab:components} | |
| 161 \begin{center} | |
| 162 \begin{tabular}{|c||c|} \hline | |
| 163 名前 & 概要 \\ \hline | |
| 164 Jungle & 木の作成・取得を担当する。 \\ \hline | |
| 165 Node & 基本的なデータ構造、子と属性を任意の数持てる。 \\ \hline | |
| 166 RootNode & 木構造のルートを表す。Jungle から最新のルートノードを取得できる。 \\ \hline | |
| 167 children & 子となるノードを任意の数持つことができる。 \\ \hline | |
| 168 attributes & Key と Value の組み合わせを任意の数持つことができる。 \\ \hline | |
| 169 \end{tabular} | |
| 170 \end{center} | |
| 171 \end{table} | |
| 172 | |
| 173 \subsection{Jungle} | |
| 174 Jungle は木構造の集まりを表現する。 | |
| 175 木には名前がついており、ルートノードの情報も一緒に保持している。 | |
| 176 | |
| 177 \subsubsection{木の取り扱い} | |
| 178 Jungle の木の取り扱いには、Haskell の Data.Map を利用している。 | |
| 179 Haskell で連想配列を扱いたい場合、平衡木によって実装された Data.Map を一般的に用いる。 | |
| 180 Haskell のライブラリには配列や、ハッシュ・テーブルといったものも存在するがあまり使われない。 | |
| 181 配列は参照に適しているが、データを追加する際に配列を再作成するためコストが大きい。 | |
| 182 ハッシュ・テーブルは更新操作に副作用を伴うため、IOモナドの中でしか使うことが出来ず、扱いにくい。 | |
| 183 Data.Mapは、挿入や参照が O(log n) で済む。 | |
| 184 | |
| 185 また、木の取り扱いには Haskell のソフトウェア・トランザクショナル・メモリ (STM) を利用して状態を持たせ、スレッド間で共有できるようにしてある。 | |
| 186 これは、木構造の各スレッドから作成できるようにするためである。 | |
| 187 STM は、スレッド間でデータを共有するためのツールである。STM を利用することでロック忘れによる競合状態や、デッドロックといった問題から解放される。 | |
| 188 STM は、アクションのブロックを atomically コンビネータを使ってトランザクションとして実行する。 | |
| 189 いったんブロック内に入るとそこから出るまでは、そのブロック内の変更は他のスレッドから見ることはできない。 | |
| 190 こちら側のスレッドからも他のスレッドによる変更はみることはできず、実行は完全に孤立して行われる。 | |
| 191 トランザクションから出る時に、以下のことが１つだけ起こる。 | |
| 192 \begin{itemize} | |
| 193 \item 同じデータを平行して変更したスレッドが他になければ、加えた変更が他のスレッドから見えるようになる。 | |
| 194 \item そうでなければ、変更を実際に実行せずに破棄し、アクションのブロックを再度実行する。 | |
| 195 \end{itemize} | |
| 196 STM は簡単に使え、また同時に安全である。 | |
| 197 | |
| 198 \subsection{Node} | |
| 199 Node は木構造を表現するデータ構造である。 | |
| 200 再帰的に定義されている。 | |
| 201 各ノードは Children としてノードを複数持つことができる（図\ref{fig:node_components}）。 | |
| 202 | |
| 203 \begin{figure}[!htbp] | |
| 204 \begin{center} | |
| 205 \includegraphics[width=110mm]{./images/node_component.pdf} | |
| 206 \end{center} | |
| 207 \caption{Nodeの構成要素} | |
| 208 \label{fig:node_components} | |
| 209 \end{figure} | |
| 210 | |
| 211 Children および Attributes も Data.Map を用いて定義されている（ソースコード \ref{src:node}）。 | |
| 212 | |
| 213 \begin{lstlisting}[label=src:node, caption=Nodeのデータ型の定義] | |
| 214 data Node = Node | |
| 215 { children :: (Map Int Node) | |
| 216 , attributes :: (Map String ByteString) } | |
| 217 \end{lstlisting} | |
| 218 | |
| 219 \subsubsection{ルートノード} | |
| 220 非破壊的木構造ではノードは破壊されない。 | |
| 221 そのため、どのノードが最新のルートノードなのかという情報が必要である。 | |
| 222 この情報もスレッドセーフに取り扱う必要があるため、Haskell の ソフトウェア・トランザクショナル・メモリ (STM) を用いて管理している。 | |
| 223 | |
|
5
658281be77ec
describe the abstract
Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp>
parents:
2
diff
changeset
|
224 \section{並列実行} |
| 10 | 225 木構造データベース Jungle は、並列に実行することができる。 |
| 226 アプリケーション側で、データベースを参照や変更する際に各スレッドから呼び出しても問題ない。 | |
| 227 利用方法も、シングルスレッドで実行する場合と同じである。 | |
| 2 | 228 |
| 10 | 229 \section{Haskell の生産性} |
| 230 Java を用いた Jungle の実装と比較して、コード行数が約 3000 行から約 300 行へと短くなった。 | |
| 231 | |
| 232 これは Haskell の表現力が高いためである。 | |
| 233 Haskell では、データ型を簡単に作成することができる。 | |
| 234 再帰的なデータ構造の定義も容易である。 | |
| 235 共通の性質を扱うための型クラスという仕組みが存在し、既存のライブラリを作成したデータ型に利用できる。 | |
| 236 また、Haskellは参照透過性を持つため、コードの再利用が行い易く、関数同士の結合も簡単である。 | |
| 237 | |
| 238 同じような機能を実装する場合でも、Java と比較してコード行数が短くなり生産性が向上する。 |