+ 関数型言語 Haskell による並列データベースの実装 +

+ Daichi TOMA +
+ Feb 4, 2014 +

+ 研究概要 +

+ Haskellは純粋関数型プログラミング言語である。 + モダンな型システムを持ち、型推論と型安全により簡潔で信頼性の高いプログラムを書くことが可能である。 + また、Haskellは純粋であるため、関数は引数が同じならば必ず同じ値を返すことが保証されている。 + これは、並列処理において並列化に適した部分が分かりやすくなるというメリットがあり、また状態に依存したバグから解放されることも意味する。 +

+ 本研究では、Haskell を用いて並列に読み書き可能なデータベースの実装を行う。 + 並列にデータへアクセスする手法として、元となる木構造を変更することなく編集できる非破壊的木構造を用いる。 + 非破壊的木構造は、破壊的代入が存在しない Haskell と相性がよい。 +

+ + 実装した並列データベースの読み込みと書き込みについて性能を計測し、読み込みに関して 98.96 % という高い並列度が確認できた。 + また、簡単な掲示板ウェブアプリケーションを開発し、既存の Java の非破壊的木構造データベースとの比較をおこない、Java のおよそ 2倍の性能を確認することができた。 +

+ Haskell とは +

+ Haskellは純粋関数型プログラミング言語である。 + 関数とは、一つの引数を取り一つの結果を返す変換器のことである。 + 関数型プログラミング言語では、関数を引数に適用させていくことで計算を行う。 +

+ 既存の手続き型言語と異なり、手順を記述するのではなく、この関数が何であるかということを記述する。 + 例えば、Haskell でフィボナッチ数列を定義するには以下の様に記述する。 +

+ +

+fib 0 = 0
+fib 1 = 1
+fib n = fib (n-2) + fib (n-1)
+

+ Haskell の特徴 +

+ Haskellの他の言語との大きな違いは、純粋性を持つことと現代的な型システムを備えていることである。 +

+ 純粋性を持つとは、引数が同じならば関数は必ず同じ値を返すということを保証しているという意味である。 + 関数が引数のみに依存する場合、関数はどのタイミングで実行してもよいため並列化が行いやすい。 +

+ Haskell の型システム +

+ Haskell では、すべての式、すべての関数に型がある。 + Haskell の型システムはプログラマにいくつかの恩恵をもたらす。 +

エラーの検出 +
抽象化 +
安全性 +
ドキュメント化 +

+ ひとつずつ説明していく +

+ Haskell の型システム - エラーの検出 +

+ Haskell は静的型検査によりエラーを広範囲に検出することができる。 + プログラムが型検査器（コンパイラ）を通れば「ちゃんと動く」傾向にある。 +

+ Haskell では、データ構造を独自の型で表現することができる。 + 独自に定義した型も、コンパイラの援助を得ることができる。 +

+ また型検査器は保守のためのツールにもなりうる。 + 独自に定義したデータ型を変更した場合、修正が必要な箇所は型の不整合が起こるので、修正が容易である。 +

+ Haskell の型システム - 抽象化 +

+ 型システムは、プログラムに抽象をもたらす。 + 抽象を導入することで、低水準の詳細を気にせずプログラミングが可能になる。 + 例えば、値の型が文字列ならば、どのように実装されているかという細かいことは気にせず、 + その文字列が他の文字列と同じように振る舞うとみなすことができる。 +

+ また、Haskell では型クラスを用いて、型の振る舞いを定義できる。 + 言語の基本的な機能である、同値性の検査や数値演算を抽象化することもできる。 +

+ Haskell の型システム - 安全性 +

+ Haskell の型システムは、自らがもたらす抽象の整合性を保証する。 + 型は不変の条件であり、異なる型として認識されることはない。 +

+ 定義したデータ型は期待通りに動くことが保証される。 + 他のデータ構造の境界を超えてきたデータが書き込まれたりするようなことは起きない。 +

+ Haskell の型システム - ドキュメント化 +

+ Haskell の型はプログラムを読む際にも有用である。 + 関数の型は、その関数の振る舞いを理解するヒントになる。 +

+ 例えばリストの先頭要素を取ってくる head という関数がある。 + この型宣言を見れば、この関数はリストの要素のどれか１つをそのまま返すだけの関数ということが分かる。 +

+head :: [a] -> a
+

+ 型はコンパイルが実行されるたびに検査されるので、コメントに埋め込まれた記述と違って古くなることがない。 +

+ Haskell による並列データベース +

+ 現在、CPU はマルチコア化が進んでいる。 + マルチコアプロセッサで線形に性能向上をするためには、処理全体で高い並列度を保たなければならない（アムダール則）。 +

+ CPU コア数に応じて、データベースを線形に性能向上させたい場合、別々の CPU コアから同時にデータベースへアクセスできればよい。 + 通常は、同一のデータへアクセスする場合、競合が発生してしまい処理性能に限界が生じる。 +

+ 本研究では、非破壊的木構造という手法を用いて競合が発生する問題を解決する。 + 競合を発生させないためには、既にあるデータを変更しなければよい。 + 非破壊的木構造は、変更元となる木構造を変更しない。 + そのため、別々の CPU コアから同時にアクセスが可能である。 +

+ 非破壊的木構造 +

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

+ +

+ 非破壊的木構造 - ルートノード +

+ 非破壊的木構造では、どの木構造が最新かを表す情報が重要である。 + 最新の木構造を表すノードをルートノードと呼ぶ。 +

+ +

+ 非破壊的木構造 - ルートノードの管理 +

+ ルートノードの情報はスレッド間で共有する必要がある。 + ソフトウェア・トランザクショナル・メモリ (STM) を用いて実現する。 + STM は、排他制御を行わずに共有データを扱うことができる。 +

+ STM は、他のスレッドによる変更を考慮せずに共有データに対して変更を行う。 + 変更をトランザクションとしてコミットする時に以下のことがひとつだけ起こる。 +

同じデータを平行して変更したスレッドが他になければ、加えた変更が他のスレッドから見えるようになる +
そうでなければ、変更を実際に実行せずに破棄し、変更の処理を再度実行する。 +

+ 非破壊的木構造データベース Jungle +

+ Jungle は、複数の非破壊的木構造を扱うことのできるデータベースである。 +

+ 木構造の識別には、名前を利用する。 + 名前を付けて作成し、名前を用いることで参照を行う。 +

+
+
+

+ Jungle - データの取得と更新 +

+ Jungle では、データの取得や更新のためにルートノードを扱う API がある。 + ルートノード関連の API は IO 処理となる。 +

+-- ルートノードの取得
+node <- getRootNode jungle "your_tree_name_here"
+
+-- ルートノードの更新
+updateRootNode jungle "your_tree_name_here" node
+
+-- ノードを編集する関数を渡して、ルートノードの取得から更新までを一貫して行う
+updateRootNodeWith func jungle "your_tree_name_here"
+

+ Jungle 内部のデータ型 +

+ Jungle 内部で用いているデータ型を示す。 + これらの型は、Jungle 内部の関数で使われている。 +

+ データ型として定義することで、データ内部の整合性が保たれ、また型検査でエラーがないか検出することができる。 +

+ + + + + + + + + + + + + + + + + +

型の名前	概要
Jungle	複数の木と名前を結びつける辞書
Tree	木の名前とルートノードの情報
Node	子と属性の2つの辞書