研究概要

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

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

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

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

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

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

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

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

@@ -62,23 +59,26 @@

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

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

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

+ ⇒ Cross site scripting が防げる

Haskellの型検査の例(list)

- : - / \ - 1 [] +

Haskellの型検査の例(list)

: はlistに要素を追加するための演算子

1 : 2 : 3 : [] == [1,2,3]

+
+

-let a = 0 : [1,2,3] -- [0,1,2,3]
+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 の並列処理

- 並列実行は遅延評価が問題になる -

- haskell では値が必要となるまで式の評価が行われない -

- 並列に実行するように指示しても、評価が行われなければ並列に動かない + rparの例

- Haskell の遅延評価 -

- sprintは評価を行わずに値を表示するコマンド -

- _ は未評価の式を表し、thunk と呼ばれる -

Haskell の遅延評価

並列実行は遅延評価が問題になる

haskell では値が必要となるまで式の評価が行われない

並列に実行するように指示しても、評価が行われなければ並列に動かない

Haskell の遅延評価

sprintは評価を行わずに値を表示するコマンド

_ は未評価の式を表し、thunk と呼ばれる

 ghci> let y = map (+1) [1,2,3] :: [Int]
 ghci> :sprint y
@@ -148,26 +140,15 @@
 ghci> :sprint y
 y = [2,_,_]

- 並列実行時には出力などを挟んで強制的に即時評価されるようにする -

並列実行時には出力などを挟んで強制的に即時評価されるようにする

- データベースの設計 - 非破壊的木構造 -

- マルチコア上で、データベースの性能向上をさせるためには、各コアからデータに同時にアクセスできるようにする -

- 非破壊的木構造という手法を用いる。 - - 非破壊的木構造は、元となる木構造を書き換えずに編集できる。 -

- 既にあるデータを変更しないので、データの競合状態が発生しない。並列に読み書きできる -

データベースの設計 - 非破壊的木構造

マルチコア上で、データベースの性能向上をさせるためには、各コアからデータに同時にアクセスできるようにする

非破壊的木構造という手法を用いる。

非破壊的木構造は、元となる木構造を書き換えずに編集できる。

既にあるデータを変更しないので、データの競合状態が発生しない。並列に読み書きできる

@@ -175,11 +156,11 @@

Haskell でのRoot Node の管理

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

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

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

STM は、Non-Blockingで共有データを扱える

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

他から変更がなければそのまま適用 @@ -187,96 +168,63 @@

- -

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

- 非破壊的木構造を扱うデータベース Jungle を開発した -

- Jungle の基本的な使い方 -

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

非破壊的木構造を扱うデータベース Jungle を開発した

Jungle の基本的な使い方

木構造を保持する Jungle を作成
Jungle に新しい木を作成 -
木から最新のルートノードを取ってきて、データを参照する -
もしくは、ノードを編集し、木の最新のルートノードを更新する +
木からRoot Nodeを取ってきて、データを参照 +
もしくは、Node を編集し、木のRoot Nodeを更新

- 木構造を保持する Jungle の作成 -

-data Jungle = Jungle (TVar (Map String Tree))
-

- TVarがついているのはSTMを使っている変数 -

- 各スレッドから新しく木を作ったりできるように木構造の保持にSTMを使っている -

- Jungle は複数の Tree を名前で管理する -

木構造を保持する Jungle の作成

各スレッドから新しく木を作ったりできるように木構造の保持にSTMを使っている

Jungle は複数の Tree を名前で管理する

- +

- 木から最新のルートノードを取ってくる -

- 木から最新のルートノードを取ってくるにはgetRootNodeという関数を使う -

木からRoot Nodeを取ってくる

木からRoot Nodeを取ってくるにはgetRootNodeという関数を使う

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

 getRootNode :: Jungle -> String -> IO Node

- Jungleと木の名前を渡すと最新のルートノードが返ってくる -

Jungleと木の名前を渡すと最新の Node が返ってくる

ノード

Node

Node はChildren(Node)とattributesを持つ

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

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

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

Node を編集し、木の Root Node を更新する

updateRootNodeやupdateRootNodeWithで更新できる

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

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

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

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

updateRootNodeには編集したNodeを渡すことで木の Root Node を更新できる

updateRootNodeWithにはNodeを編集する関数を渡すことで木の Root Node を更新できる

- 性能計測 -

- Jungle がマルチコアプロセッサで性能が出るのか、実用的なWebサービスが提供できるのか確認する -

- 性能の計測に用いるサーバの仕様 -

- ハイパースレッディングで24コアまで使える
- ハイパースレッディングはおよそ20％程度クロックあたりの性能が向上する -

性能計測

Jungle がマルチコアプロセッサで性能が出るのか、実用的なWebサービスが提供できるのか確認する

性能の計測に用いるサーバの仕様

ハイパースレッディングで24コアまで使える
ハイパースレッディングはおよそ20％程度クロックあたりの性能が向上する

@@ -299,411 +247,148 @@

名前	Fedora 19

- Haskell コンパイラ -

- Haskell のコンパイラには The Glasgow Haskell Compiler (GHC) を利用する -

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

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

- -

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

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

- 並列実行時の性能が向上するため性能計測で利用する -

- Haskell は実行時に -qa オプションを使うこと親和性機能を使うように指示できる -

Haskell コンパイラ

Haskell のコンパイラには The Glasgow Haskell Compiler (GHC) を利用する

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

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

- 読み込みの性能計測 -

- 木構造の読み込みにかかる時間を計測する -

- 12 スレッドで親和性機能を使って実行した場合 10.37 倍の性能向上 -

- 親和性機能を使って24スレッドで実行すると実行時間が大幅に伸びる。 - スレッドが CPU に固定されるため、性能計測以外のプログラムがうまくスケジューリングされないためだと考えられる -

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

CPU数	親和性機能なし	親和性機能あり
1	60.95 s	61.00 s
2	30.83 s	33.95 s
4	15.49 s	16.10 s
8	10.31 s	8.79 s
12	8.49 s	5.88 s
16	5.82 s	5.81 s
20	6.54 s	5.48 s
24	8.21 s	125.09 s

- -

- 読み込みの性能計測 -

- 親和性機能を使った場合、実コアの12スレッドまでほぼ線形にスケールする -

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

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

並列実行時の性能が向上するため性能計測で利用する

Haskell は実行時に -qa オプションを使うこと親和性機能を使うように指示できる

- 書き込みの性能計測 -

- 木構造の書き込みにかかる時間を計測する -

- 12 スレッドで親和性機能を使って実行した場合 3.82 倍の性能向上 -

- 読み込みと同様に親和性機能を使って24スレッドで実行すると実行時間が大幅に伸びる -

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

CPU数	親和性機能なし	親和性機能あり
1	49.70 s	49.61 s
2	27.77 s	30.76 s
4	18.06 s	18.05 s
8	16.66 s	12.50 s
12	15.62 s	12.96 s
16	14.91 s	13.11 s
20	15.31 s	13.84 s
24	18.11 s	71.66 s

- -

- 書き込みの性能計測 -

- 4 倍程度で性能向上が頭打ちになっている -

- 同時に書き込みがあった場合、STMが処理をやり直すため並列度が下がる -

読み込みの性能計測

木構造の読み込みにかかる時間を計測する

12 スレッドで親和性機能を使って実行した場合 10.37 倍の性能向上
+ →ほぼ線形にスケールする

親和性機能を使った時 24スレッドで実行すると実行時間が大幅に伸びる

書き込みの性能計測

木構造の書き込みにかかる時間を計測する

12 スレッドで親和性機能を使って実行した場合 3.82 倍の性能向上
+ → 同時に書き込みがあった場合、STMが処理をやり直すため並列度がでない

読み込みと同様に親和性機能を使って24スレッドで実行すると実行時間が大幅に伸びる

+ +

読み込みと書き込みの考察

読み込みが高速

書き込みは、同時に書き込まれた場合 STMが処理のやり直しをするため、並列度がでない

親和性機能を使った場合 24 スレッドでは遅くなる
+ ⇒ 全てのCPUコアにスレッドを固定することになりスケジューリングがうまくいかないためだと考えられる +

書き込みより読み込みが多用されるシステムに向いている

+ +

Webサービスに組み込んでの性能計測

Haskell の HTTP サーバ Warp と組み合わせて Web掲示板サービスを開発する

測定ツール weighttp を用いて掲示板に読み込みと書き込みで負荷をかける。

Warp は、ハイパースレッディングで明らかに遅くなるので使わない

+ +

ネットワークのボトルネック

ネットワークのボトルネックが大きい

並列環境でどのようにスケールするか計測したいため、ネットワークを介さずに性能計測を行う

+
+

+ + +

Webサービスに組み込んでの性能計測

読み込みと書き込みの実験結果

1秒間あたりどれだけリクエストを捌けるかという指標で比較
+ ⇒大きければ大きいほど性能が良い

8 スレッドで実行時、読み込みは 6.18 倍、書き込みは3.93倍の性能向上

Jungle 単体での実験結果と同じで、読み込みのほうがスケールする

+ +

Java との比較

HaskellとJavaで同様のWeb掲示板サービスを用意する

実環境を想定して、ブレードサーバ2台用意し、ネットワークを介して負荷をかける

100 万リクエストを処理するのにかかる時間を計測

+ + + + + + + + +

測定 +	Haskell +	Java +
読み込み +	16.31 s +	53.13 s +
書き込み +	20.17 s +	76.4 s +

+ +

読み込みで 3.25 倍、書き込みで 3.78 倍の性能差
+ ⇒ Haskell は実用的なWebサービスを開発できる

+ +

Java との生産性の比較

Haskell 版 Jungle は 284 行、Java 版 Jungle は 3,390 行

実装が 1/12 程度のサイズとなっている

再帰的なデータ型の定義ができることや、関数の再利用が行いやすいことが要因

同じ機能を実装する場合でも、Haskell は Java と比較してコード行数が短くなる

+ +

まとめ

純粋関数型言語 Haskell を用いて並列データベースの実装をおこなった

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

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

+ +

今後の課題

書き込み処理の性能向上

分散データベースとしての実装

永続性の実装

+ +

- 考察 -

- 読み込みが高速 -

- 書き込みより読み込みが多用されるシステムに向いている -

- -

- Webサービスに組み込んでの性能計測 + ネットワークボトルネックの計測

- Haskell の HTTP サーバ Warp と組み合わせて Web掲示板サービスを開発する -

- 測定ツール weighttp を用いて掲示板に読み込みと書き込みで負荷をかける。 -

- Warp は、ハイパースレッディングで明らかに遅くなるので使わない + ネットワークを介す場合と介さない場合のWarpのベンチマーク

- -

- ネットワークのボトルネック -

- ネットワークのボトルネックが大きい -

- 並列環境でどのようにスケールするか計測したいため、ネットワークを介さずに性能計測を行う -

- -

- 実験環境 -

- 3 コアを測定ツール weighttp に使い、 - 8 コアを Web 掲示板サービスに使う -

-
-

- -

- Webサービスに組み込んでの性能計測 -

- 読み込みと書き込みの実験結果 -

- 1秒間あたりどれだけリクエストを捌けるかという指標で比較 - 大きければ大きいほど性能が良い -

- 8 スレッドで実行時、読み込みは 6.18 倍、書き込みは3.93倍の性能向上 -

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

CPU数	読み込み	書き込み
1	22,624 req/s	28,552 req/s
2	43,083 req/s	53,765 req/s
4	92,548 req/s	98,691 req/s
6	119,310 req/s	99,009 req/s
8	139,965 req/s	112,212 req/s

- -

- Webサービスに組み込んでの性能計測 -

- Jungle 単体での実験結果と同じで、読み込みのほうがスケールする -

- Java との比較 -

- HaskellとJavaで同様のWeb掲示板サービスを用意する -

- 実環境を想定して、ブレードサーバ2台用意し、ネットワークを介して負荷をかける -

- 100 万リクエストを処理するのにかかる時間を計測 -

- - - - - - - - - - - - - - - - - -

測定	Haskell	Java
読み込み	16.31 s	53.13 s
書き込み	20.17 s	76.4 s

- 読み込みで 3.25 倍、書き込みで 3.78 倍の性能差 -

- Haskell は実用的なWebサービスを開発できる -

- -

- Java との比較 - 生産性 -

- 生産性の面からも Java との比較を行う -

- Haskell 版 Jungle は 284 行、 - Java 版 Jungle は 3,390 行 -

- 実装が 1/12 程度のサイズとなっている -

- 再帰的なデータ型の定義ができることや、関数の再利用が行いやすいことが要因 -

- 同じ機能を実装する場合でも、Haskell は Java と比較してコード行数が短くなる -

- -

- まとめ -

- 純粋関数型言語 Haskell を用いて並列データベースの実装をおこなった -

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

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

- -

- 今後の課題 -

- 書き込み処理の性能向上 -

- 分散データベースとしての実装 -

- 永続性の実装 -

- -

- GHC 7.6.3 の IO マネージャーの問題 -

- GHC 7.6.3 には並列実行時に IO マネージャーがスケールしないという問題がある -

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

研究概要

Haskellの型検査の例(list)

Haskellの型検査の例(list)

型推論

型推論

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

- Haskell の遅延評価 + Haskell の並列処理

- Haskell の遅延評価 -

Haskell の遅延評価

Haskell の遅延評価

- データベースの設計 - 非破壊的木構造 -

データベースの設計 - 非破壊的木構造

Haskell でのRoot Node の管理

Haskell でのRoot Node の管理

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

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

- 木構造を保持する Jungle の作成 -

木構造を保持する Jungle の作成

- 木から最新のルートノードを取ってくる -

木からRoot Nodeを取ってくる

ノード

Node

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

Node を編集し、木の Root Node を更新する

- 性能計測 -

性能計測

- Haskell コンパイラ -

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

Haskell コンパイラ

- 読み込みの性能計測 -

- 読み込みの性能計測 -

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

- 書き込みの性能計測 -

- 書き込みの性能計測 -

読み込みの性能計測

書き込みの性能計測

読み込みと書き込みの考察

Webサービスに組み込んでの性能計測

ネットワークのボトルネック

Webサービスに組み込んでの性能計測

Java との比較

Java との生産性の比較

まとめ

今後の課題

- 考察 -

- Webサービスに組み込んでの性能計測 + ネットワークボトルネックの計測

- ネットワークのボトルネック -

- 実験環境 -

- Webサービスに組み込んでの性能計測 -

- Webサービスに組み込んでの性能計測 -

- Java との比較 -

- Java との比較 - 生産性 -

- まとめ -

- 今後の課題 -

- GHC 7.6.3 の IO マネージャーの問題 -