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

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

Daichi TOMA
@@ -48,141 +46,69 @@

- 研究概要 -

- Haskell を用いて並列データベースを実装した -

- 読み込みに関して 12 コアで実行した場合、10.37 倍という性能向上率が確認できた -

- また、Web 掲示板サービスを開発し、Java と比較して読み込みで 3.25 倍、書き込みで 3.78 倍の性能差が確認できた -

- 研究背景 -

- Web サービスの脆弱性を悪用されると多大な被害がでる -

- Haskell は型検査でバッファオーバーフローや、クロスサイトスクリプティング、SQL インジェクションを防げる -

- Haskell を用いることで信頼性の高いデータベースとWebサービスを開発できる -

研究概要

Haskell を用いて信頼性の高い並列データベースを実装した

Haskell は rseq により並列実行を指示し、STMにより共有データを実現する

Haskellの並列処理は、最新のコンパイラで性能がでることがわかった

読み込みに関して 12 コアで実行した場合、10.37 倍という性能向上率が確認できた

Web 掲示板サービスを開発し、Java と比較して読み込みで 3.25 倍、書き込みで 3.78 倍の性能差が確認できた

Network および IO の並列性能はあまり出てないことがわかった

- 型による区別 -

- Haskellは、全てに型がある -

- 文字列やHTMLを型として定義し、別の型として扱うことができる -

- 入力として受け取った文字列が、HTML型に自動変換されたりしない
- - > クロスサイトスクリプティングが防げる -

Haskellによる信頼性の高いサービスの構築

Web サービスの脆弱性を悪用されると多大な被害がでる

脆弱性の大半はBuffer Overflowや、Cross site scripting、SQL injection

これらは型エラー。Haskell は、これらをコンパイル時にチェック

入力として受け取った文字列が、HTML型に実行時に自動変換されたりしない
+ ⇒ クロスサイトスクリプティングが防げる

- 実行時型エラーがない -

- Haskellは、実行時に型に起因するエラーが起きない -

- [1,2,3]のリストに文字'a'を追加することや、['a','b','c']のリストに 1 を追加することはできない -

- コンパイル時にエラーになる -

Haskellの型検査の例(list)

+ : + / \ + 1 []

-abc = 'a' : [1,2,3] -- error
-cde =  1  : ['a','b','c'] -- error
+let a = 0 : [1,2,3] -- [0,1,2,3]
+let b = 'a' : [1,2,3] -- error
+let c =  1  : ['a','b','c'] -- error

- Haskell 自体が型の不整合を防ぐ -

- 型推論 -

- 型エラーを検出するために全ての式や関数に型を書いていくのは大変 -

- Haskell は型を推論してくれる -

- 型推論 -

- 前提として関数に以下のような型が定義されている -

型推論

前提として関数に以下のような型が定義されているとする

 getNode :: Node -> Path -> Node
 elems :: Map k a -> [a]
 children :: Node -> Map Int Node

- 新しくgetChildrenという関数を定義するとき型を自動で導出できる -

新しくgetChildrenという関数を定義する

 getChildren node path = elems (children (getNode node path))

- Haskell が推論した型を確認する -

型をHaskellが自動で導出する

 *Jungle> :type getChildren
 getChildren :: Node -> Path -> [Node]

- 実用的なデータベースの開発 -

- 現在、CPU はマルチコア化がすすんでいる -

- 実用的なデータベースとするためにはマルチコアに対応させる必要性がある -

- 並列に処理できればマルチコアで性能が出る -

実用的なデータベースには並列実行が必須

現在、CPU はマルチコア化がすすんでいる

実用的なデータベースとするためにはマルチコアに対応させる必要性がある

並列に処理できればマルチコアで性能が出る

Haskell は Eval モナド(rpar)といったモナドで並列実行の機能を提供

モナドは、Haskellでメタ計算を提供する構文あるいはAPI

システムコールのようなものと考えてよい

モナドの例:IOモナド、エラーモナド、STMモナド

- Haskell での並列実行 -

- Eval モナドといったモナドで並列実行の機能を提供 -

- Haskell では様々な目的にモナドを使う
- I/O 処理を行うための IO モナドはよく使われる -

- + Haskell の並列処理 +rparの例

Haskell の遅延評価 @@ -248,57 +174,19 @@

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

- 非破壊的木構造の並列実行のネックとなるものがルートノード -

- ルートノードは、どの木構造が最新なのかを表す情報 -

- スレッド間で共有する状態を持つため、並列度を高めるにはルートノードの設計が重要 -

Haskell でのRoot Node の管理

- Haskell でのルートノードの管理 -

- ソフトウェア・トランザクショナル・メモリ (STM) を使う -

- STM は、ノンブロッキングで共有データを扱える -

- 共有データの変更は以下の様に行われる -

Root Node は最新のNode → 状態を持つ

共有された状態を作るには Software Transactional Memory (STM) を使う

STM は、ノンブロッキングで共有データを扱える

共有データの変更は以下の様に行われる

他から変更がなければそのまま適用
変更している間に、他から変更されれば変更処理をやり直し

- STM のメリット -

- 共有データにアクセスする時に待ちがない -

- 読み込みは他の変更を気にせず並列に行える -

- 高速に読み込める -

@@ -339,22 +227,6 @@

- Jungle に新しい木を作成 -

-data Tree = Tree (TVar Node) String
-

- Tree は最新のルートノードの情報と木の名前を持っている -

-
-
-

@@ -371,42 +243,26 @@

- ノード -

- Jungle で最も基本的な構成要素 -

- Jungle の参照や変更の関数は全てノードに対して行う -

-data Node = Node (Map Int Node) (Map String ByteString)
-

ノード

Node はChildren(Node)とattributesを持つ

Jungle の参照や変更の関数は全てノードに対して行う

- ノードを編集し、木の最新のルートノードを更新する -

- updateRootNodeやupdateRootNodeWithで更新できる -

ノードを編集し、木の最新のルートノードを更新する

updateRootNodeやupdateRootNodeWithで更新できる

内部でSTMを使っているのでIOモナドを返す

 updateRootNode :: Jungle -> String -> Node -> IO ()
 updateRootNodeWith :: (Node -> Node) -> Jungle -> String -> IO ()

- updateRootNodeには編集したNodeを渡すことで木の最新のルートノードを更新できる -

- updateRootNodeWithにはNodeを編集する関数を渡すことで木の最新のルートノードを更新できる -

updateRootNodeには編集したNodeを渡すことで木の最新のルートノードを更新できる

updateRootNodeWithにはNodeを編集する関数を渡すことで木の最新のルートノードを更新できる

@@ -456,13 +312,13 @@ 現在の GHC の安定版 7.6.3 は並列時にIOマネージャーがスケールしないという問題がある

- リリース候補版である 7.8 を用いる + リリース候補版である 7.8 を用いることにより、よりよい性能を得ることができた

- 親和性機能を利用する + 親和性機能(affinity)を利用する

親和性機能とは OS スレッドをCPUコアに固定する機能