# HG changeset patch # User Daichi TOMA # Date 1391414088 -32400 # Node ID 345eacdf29e462616e645b5750ce584fc4e8bf34 # Parent 705c29dd2f6d8b3a79b01f03eb9038f8ce3f1520 add apendix diff -r 705c29dd2f6d -r 345eacdf29e4 paper/abstract.tex --- a/paper/abstract.tex Mon Feb 03 12:00:46 2014 +0900 +++ b/paper/abstract.tex Mon Feb 03 16:54:48 2014 +0900 @@ -9,8 +9,8 @@ 並列にデータへアクセスする手法として、元となる木構造を変更することなく編集できる非破壊的木構造を用いる。 非破壊的木構造は、破壊的代入が存在しない Haskell と相性がよい。 -実装した並列データベースの読み込みと書き込みについて性能を計測し、読み込みに関して 98.96 \% という高い並列度が確認できた。 -また、簡単な掲示板ウェブアプリケーションを開発し、既存の Java の非破壊的木構造データベースとの比較をおこない、Java のおよそ 2倍の性能を確認することができた。 +実装した並列データベースの読み込みと書き込みについて性能を計測し、読み込みに関して 98.96 \% という高い並列化率が確認でき、マルチコアプロセッサの性能を引き出すことができた。 +また、掲示板ウェブアプリケーションを開発し、既存の Java の非破壊的木構造データベースとの比較をおこない、Java のおよそ 2倍の性能を確認することができた。 \end{abstract} diff -r 705c29dd2f6d -r 345eacdf29e4 paper/chapter1.tex --- a/paper/chapter1.tex Mon Feb 03 12:00:46 2014 +0900 +++ b/paper/chapter1.tex Mon Feb 03 16:54:48 2014 +0900 @@ -9,6 +9,7 @@ 例えば、Haskell でフィボナッチ数列を定義するにはソースコード\ref{src:fib}のように記述する。 \begin{lstlisting}[label=src:fib, caption=フィボナッチ数列] +fib :: Int -> Int fib 0 = 0 fib 1 = 1 fib n = fib (n-2) + fib (n-1) @@ -61,6 +62,9 @@ True :: Bool \end{lstlisting} +Haskell は静的型検査によりエラーを広範囲に検出することができる。 +データ構造を独自の型で表現することができ、その定義したデータ構造も型検査でエラーがないか調べることができる。 + \subsubsection{基本的な型} Haskell は多くの基本型を提供している。 Haskell の基本型を表\ref{tab:type}に示す。 @@ -103,23 +107,23 @@ リストのリストを作ることもできる。 -\subsubsection{タプル型} -タプルは固定サイズの要素の組である。各要素の型は異なってもよい。 -各要素をコンマで区切って、全体を括弧で包む。 - -タプルの例をソースコード\ref{src:tuple}に示す。 - -\begin{lstlisting}[label=src:tuple, caption=Haskellのタプル] -ghci> :type (False, True) -(False, True) :: (Bool, Bool) - -ghci> :type ('a', True, False) -('a', True, False) :: (Char, Bool, Bool) - -ghci> :type ([True, False], 'a', 'b') -([True, False], 'a', 'b') :: ([Bool], Char, Char) -\end{lstlisting} - +%\subsubsection{タプル型} +%タプルは固定サイズの要素の組である。各要素の型は異なってもよい。 +%各要素をコンマで区切って、全体を括弧で包む。 +% +%タプルの例をソースコード\ref{src:tuple}に示す。 +% +%\begin{lstlisting}[label=src:tuple, caption=Haskellのタプル] +%ghci> :type (False, True) +%(False, True) :: (Bool, Bool) +% +%ghci> :type ('a', True, False) +%('a', True, False) :: (Char, Bool, Bool) +% +%ghci> :type ([True, False], 'a', 'b') +%([True, False], 'a', 'b') :: ([Bool], Char, Char) +%\end{lstlisting} +% \subsubsection{型の安全性} Haskell では、評価の際に型に起因するエラーが起きないことを保証している。 @@ -152,39 +156,6 @@ 型推論では、適用可能な最も広い型が選択されてしまうため、制限するには明示的に型宣言を行う。 明示的な型宣言は可読性の向上や問題の発見に役に立つため、トップレベルの関数には型を明記することが一般的である。 -\subsubsection{多相型} -Haskell の型は多相的である。 -型変数を使い、型を抽象化できる。 -型変数は、型安全を保ちながら、関数を複数の型に対して動作するようにできる。 -Haskell の型の名前は全て大文字から始まるが、型変数は小文字から始まる。 -任意の型のリストを引数に取り、その型の先頭要素を返すという関数 head の型はソースコード\ref{type_variable}のように定義される。 - -\begin{lstlisting}[label=type_variable, caption=型変数] -head :: [a] -> a -\end{lstlisting} - -\subsubsection{多重定義型} -Haskell の (+) は、整数や浮動小数点数のどちらにも使える。 -これは型にクラス制約を含めることで実現している。 - -\begin{lstlisting}[label=type_class, caption=クラス制約] -ghci> :t (+) -(+) :: Num a => a -> a -> a -\end{lstlisting} - -=$>$ というシンボルの前にあるものがクラス制約である。 -これは、a が Num 型クラスのインスタンスでなければいけないということを意味する。 -Num 型クラスのインスタンスとなる型は数値型である。 - -型クラスは型の振る舞いを定義するものである。 -ある型クラスのインスタンスである型は、その型クラスに属する関数の集まりを実装する。 -これは、それらの関数がその型ではどのような意味になるのか定義するということである。 - -例えば、Eq 型クラスのインスタンスとなる型は等値性をテストできる。 -この型クラスに属させるためには、(==)と、(/=)の 2 つの関数を実装する。 - -Haskell の型クラスは、動的型付けの利点を安全で使いやすい形で実現するものである。 - \subsubsection{型の定義} Haskell で新しい型を宣言する一番簡単な方法は、type キーワードを使って既存の型に別名を付けることである。 @@ -229,6 +200,39 @@ この型宣言は、「Tree a 型は、空の木、もしくは何らかの値 a と 2 つの木を含む要素である」ということを表している。 +\subsubsection{多相型} +Haskell の型は多相的である。 +型変数を使い、型を抽象化できる。 +型変数は、型安全を保ちながら、関数を複数の型に対して動作するようにできる。 +Haskell の型の名前は全て大文字から始まるが、型変数は小文字から始まる。 +任意の型のリストを引数に取り、その型の先頭要素を返すという関数 head の型はソースコード\ref{type_variable}のように定義される。 + +\begin{lstlisting}[label=type_variable, caption=型変数] +head :: [a] -> a +\end{lstlisting} + +\subsubsection{多重定義型} +Haskell の (+) は、整数や浮動小数点数のどちらにも使える。 +これは型にクラス制約を含めることで実現している。 + +\begin{lstlisting}[label=type_class, caption=クラス制約] +ghci> :t (+) +(+) :: Num a => a -> a -> a +\end{lstlisting} + +=$>$ というシンボルの前にあるものがクラス制約である。 +これは、a が Num 型クラスのインスタンスでなければいけないということを意味する。 +Num 型クラスのインスタンスとなる型は数値型である。 + +型クラスは型の振る舞いを定義するものである。 +ある型クラスのインスタンスである型は、その型クラスに属する関数の集まりを実装する。 +これは、それらの関数がその型ではどのような意味になるのか定義するということである。 + +例えば、Eq 型クラスのインスタンスとなる型は等値性をテストできる。 +この型クラスに属させるためには、(==)と、(/=)の 2 つの関数を実装する。 + +Haskell の型クラスは、動的型付けの利点を安全で使いやすい形で実現するものである。 + 自作のデータ型を作成する際は、型クラスを利用することで、既存の Haskell ライブラリを利用できる。 特定の型クラスは自動導出することも可能である。自動導出には deriving キーワードを使う。 ソースコード\ref{deriving}は、Showのインスタンスを自動導出している。 diff -r 705c29dd2f6d -r 345eacdf29e4 paper/chapter2.tex --- a/paper/chapter2.tex Mon Feb 03 12:00:46 2014 +0900 +++ b/paper/chapter2.tex Mon Feb 03 16:54:48 2014 +0900 @@ -1,63 +1,29 @@ \chapter{Haskellによる並列データベースの設計}\label{ch:design} -\section{スケーラビリティのあるデータベースを実現するには} -ウェブサービスでは、ニーズの変化に柔軟に対応できる能力が求められる。 -利用者や負荷の増大に対し、CPU のコア数に応じてパフォーマンスを線形に向上できる能力、すなわちスケーラビリティが必要となる。 -スケーラビリティが線形的であれば、リソースの追加に比例したパフォーマンスを得ることが可能である。 -一方、スケーラビリティが線形的でないと、いくらリソースを追加しても必要なパフォーマンスが得られないというケースもありえる。 +\section{マルチプロセッサで十分な性能を得るためには} +現在、CPU はマルチコア化が進んでいる。 +マルチコアプロセッサで線形に性能向上をするためには、処理全体で高い並列度を保たなければならない\cite{amdahl}。 +% ウェブサービスでは、ニーズの変化に柔軟に対応できる能力が求められる。 +% 利用者や負荷の増大に対し、CPU のコア数に応じてパフォーマンスを線形に向上できる能力、すなわちスケーラビリティが必要となる。 +% スケーラビリティが線形的であれば、リソースの追加に比例したパフォーマンスを得ることが可能である。 +% 一方、スケーラビリティが線形的でないと、いくらリソースを追加しても必要なパフォーマンスが得られないというケースもありえる。 -ウェブサービスにおいてデータベースは切り離すことのできない要素である。 -スケーラビリティの実現をするには、データベースの並列度が重要になる。 -CPU のコア数に応じてパフォーマンスを向上させる場合、別々の CPU コアから同時にデータベースへアクセスできればよい。 +CPU コア数に応じて、データベースを線形に性能向上させたい場合、別々の CPU コアから同時にデータベースへアクセスできればよい。 通常は、同一のデータへアクセスする場合、競合が発生してしまい処理性能に限界が生じる。 本研究では、非破壊的木構造という手法を用いて競合が発生する問題を解決する。 競合を発生させないためには、既にあるデータを変更しなければよい。 非破壊的木構造は、変更元となる木構造を変更しない。 -そのため、並列にアクセスが可能であり、スケーラビリティを実現できる。 +そのため、別々の CPU コアから並列にアクセスが可能であり、スケーラビリティを実現できる。 \newpage -\section{破壊的木構造と非破壊的木構造} +\section{非破壊的木構造} 非破壊的木構造は、木構造を書き換えることなく編集を行う手法である。 既にあるデータを変更しないため、データの競合状態が発生せず、並列に読み書きが行える。 また、元の木構造は破壊されることがないため、自由にコピーを行うことができる。 コピーを複数作成することでアクセスを分散させることも可能である。 -通常の破壊的木構造との違いを説明する。 - -\subsection{破壊的木構造} -破壊的木構造は、木構造を編集する際に木構造を書き換えることにより編集を実現する。 -図\ref{fig:destructive_tree_modification}では、ノード 6 をノード A に書き換える処理を行っている。 - - -\begin{figure}[!htbp] - \begin{center} - \includegraphics[width=100mm]{./images/destructive_tree_modification.pdf} - \end{center} - \caption{木構造の破壊的編集} - \label{fig:destructive_tree_modification} -\end{figure} - -破壊的に編集する方法では、並列環境において問題が発生する。 -閲覧者が木構造を参照している間に編集者が木構造を書き換えると、閲覧者が参照を開始した時点での木構造ではなくなり整合性が崩れてしまう。 -整合性が崩れた状態では、正しい状態のコンテンツを参照することは出来ない（図\ref{fig:destructive_tree_modification_in_lace}） - -\begin{figure}[!htbp] - \begin{center} - \includegraphics[width=120mm]{./images/destructive_tree_modification_in_lace.pdf} - \end{center} - \caption{競合状態に陥る木構造の破壊的編集} - \label{fig:destructive_tree_modification_in_lace} -\end{figure} - -この状態を回避するためには、木構造にアクセスする際に排他制御を行う。 -その場合、木構造に１つのスレッドしかアクセスできないため並列度が下がりスケーラビリティを損なってしまう。 -破壊的木構造では、スケーラビリティのあるデータベースの開発はできない。 - -\newpage -\subsection{非破壊的木構造} -非破壊的木構造は、木構造を書き換えることなく編集を行うため、読み書きを並列に行うことが可能である。 図\ref{fig:nondestructive_tree_modification}では、ノード 6 をノード A へ書き換える処理を行なっている。 \begin{figure}[!htbp] @@ -109,7 +75,7 @@ \label{fig:nondestructive_tree_modification_step4} \end{figure} -\clearpage +\newpage この編集方法を用いた場合、閲覧者が木構造を参照してる間に、木の変更を行っても問題がない。 閲覧者は木が変更されたとしても、保持しているルートノードから整合性を崩さずに参照が可能である。 排他制御をせずに並列に読み書きが可能であるため、スケーラブルなシステムに有用である。 @@ -157,3 +123,5 @@ ルートノードの情報の取得だけならば、並列に取得できる。 ルートノードの情報の更新の場合は、他から変更があれば再度やり直すということが自動的に行われる。 +以前の実装では、ルートノードだけではなく非破壊的木構造全体をSTMで管理していた\cite{toma:2013}。 +しかしながら、非破壊的木構造全体をSTMで管理すると並列実行時に性能が出ないため、ルートノードのみの管理に変更を行った。 diff -r 705c29dd2f6d -r 345eacdf29e4 paper/chapter3.tex --- a/paper/chapter3.tex Mon Feb 03 12:00:46 2014 +0900 +++ b/paper/chapter3.tex Mon Feb 03 16:54:48 2014 +0900 @@ -16,6 +16,31 @@ \item{もしくは、木の名前を用いて、ルートノードの更新を行う} \end{enumerate} +\subsubsection{Jungle 内部のデータ型} +Jungle の内部のデータ型を表\ref{tab:components}に表す。 +木構造の集まりを表現する Jungle、単体の木構造を表現する Tree がある。 +Tree は外部から見えないように実装されている。 + +Jungle は複数の Tree の集まりである。Jungle と木構造の名前を利用して最新のルートノードを取得することができる。 +Node は子と属性を任意の数持てる。 + +\begin{table}[!htbp] +\caption{内部のデータ型} +\label{tab:components} +\begin{center} +\begin{tabular}{|c||c|} \hline +型名 & 概要 \\ \hline +Jungle & 木の作成・取得を担当する。 \\ \hline +Tree & 木の名前とルートノードの情報を保持している。 \\ \hline +Node & 基本的なデータ構造、子と属性を任意の数持てる。 \\ \hline +children & 子となるノードを任意の数持つことができる。 \\ \hline +attributes & Key と Value の組み合わせを任意の数持つことができる。 \\ \hline +\end{tabular} +\end{center} +\end{table} + +\newpage + \subsubsection{Jungle と木の作成} Jungle は複数の非破壊的木構造を扱うことができる（図\ref{fig:jungle}）。 @@ -35,7 +60,12 @@ 木を作成するには、createTree を利用する。 createTree には、createJungle で作成した Jungle と新しい木の名前を渡す。 +型の定義と実際のコードを示す。 + \begin{lstlisting}[caption=データベースと木の作成] +createJungle :: IO Jungle +createTree :: Jungle -> String -> IO () + jungle <- createJungle createTree jungle "name of new tree here" \end{lstlisting} @@ -59,6 +89,8 @@ 例えば、図\ref{fig:getrootnode}の状態の時は、B というルートノードが取得できる。 \begin{lstlisting}[caption=最新のルートノードの取得] +getRootNode :: Jungle -> String -> IO Node + node <- getRootNode jungle "your tree name here" \end{lstlisting} @@ -71,6 +103,8 @@ updateRootNodeをした後は、getRootNodeで取得できるルートノードが更新された状態になっている。 \begin{lstlisting}[caption=ルートノードの更新] +updateRootNode :: Jungle -> String -> Node -> IO () + updateRootNode jungle "your tree name here" node \end{lstlisting} @@ -79,6 +113,8 @@ このupdateRootNodeWithを利用することで、getRootNodeをした後、編集しupdateRootNodeを行う一連の操作がatomicallyに行われることが保証される。 \begin{lstlisting}[caption=関数を渡してルートノードの更新] +updateRootNodeWith :: (Node -> Node) -> Jungle -> String -> IO () + updateRootNodeWith func jungle "your tree name here" \end{lstlisting} @@ -106,6 +142,8 @@ 子には Position という場所の情報があるが、インクリメントしながら自動的に指定される。 \begin{lstlisting}[caption=子の追加] +addNewChildAt :: Node -> Path -> Node + new_node = addNewChildAt node [l,2] \end{lstlisting} @@ -113,6 +151,8 @@ deleteChildAt には、Node と NodePath、削除したい子のPositionを指定する。 \begin{lstlisting}[caption=子の削除] +deleteChildAt :: Node -> Path -> Position -> Node + new_node = deleteChildAt node [1,2] 0 \end{lstlisting} @@ -121,6 +161,8 @@ Key は String、 Value は、ByteString である。 \begin{lstlisting}[caption=属性の追加] +putAttribute :: Node -> Path -> String -> ByteString -> Node + new_node = putAttribute node [1,2] "key" "value" \end{lstlisting} @@ -128,6 +170,8 @@ deleteAttribute には、Node と NodePath、Keyを渡す。 \begin{lstlisting}[caption=属性の削除] +deleteAttribute :: Node -> Path -> String -> Node + new_node = deleteAttribute node [1,2] "key" \end{lstlisting} @@ -139,6 +183,8 @@ getAttributes は、対象の Path に存在する属性を Key を用いて参照できる。 \begin{lstlisting}[caption=属性の取得] +getAttributes :: Node -> Path -> String -> Maybe ByteString + bytestring = getAttributes node [1,2] "key" \end{lstlisting} @@ -146,6 +192,8 @@ getChildren は、対象の Node が持つ全ての子を Node のリストとして返す \begin{lstlisting}[caption=対象のNodeの全ての子を取得] +getChildren :: Node -> Path -> [Node] + nodelist = getChildren node [1,2] \end{lstlisting} @@ -154,6 +202,8 @@ assocsChildren は、対象の Node が持つ全ての子を Position とのタプルにし、そのタプルのリストを返す。 \begin{lstlisting}[caption=対象のNodeの全ての子とPositionを取得] +assocsChildren :: Node -> Path -> [(Int, Node)] + nodelist = assocsChildren node [1,2] \end{lstlisting} @@ -162,18 +212,24 @@ assocsAttribute は、対象の Node が持つ全ての属性を、Key と Value のタプルとし、そのタプルのリストを返す。 \begin{lstlisting}[caption=対象のNodeの全てのAttributeのKeyとValueを取得] +assocsAttribute :: Node -> Path -> [(String, B.ByteString)] + attrlist = assocsAttribute node [1,2] \end{lstlisting} numOfChild では、対象の Node が持つ子どもの数を取得できる。 \begin{lstlisting}[caption=対象のNodeの子どもの数を取得] +numOfChild :: Node -> Path -> Int + num = numOfChild node [1,2] \end{lstlisting} currentChild では、対象の Node が持つ最新の子を取得できる。 \begin{lstlisting}[caption=対象のNodeの最新の子を取得] +currentChild :: Node -> Path -> Maybe Node + node = currentChild node [1,2] \end{lstlisting} @@ -190,29 +246,6 @@ GHC は、Haskell で最も広く使われているコンパイラである\cite{ghc}。 並列実行のためのMonadや、スレッドセーフな参照型を提供している。 -\subsubsection{全体の構造} -木構造の集まりを表現する Jungle、単体の木構造を表現する Tree から構成される。 -Tree は外部から見えないように実装されている。 - -Jungle は複数の Tree の集まりである。Jungle と木構造の名前を利用して最新のルートノードを取得することができる。 -Node は子と属性を任意の数持てる。 - -\begin{table}[!htbp] -\caption{全体の構造} -\label{tab:components} -\begin{center} -\begin{tabular}{|c||c|} \hline -名前 & 概要 \\ \hline -Jungle & 木の作成・取得を担当する。 \\ \hline -Tree & 木の名前とルートノードの情報を保持している。 \\ \hline -Node & 基本的なデータ構造、子と属性を任意の数持てる。 \\ \hline -RootNode & 木構造のルートを表す。Jungle から最新のルートノードを取得できる。 \\ \hline -children & 子となるノードを任意の数持つことができる。 \\ \hline -attributes & Key と Value の組み合わせを任意の数持つことができる。 \\ \hline -\end{tabular} -\end{center} -\end{table} - \subsection{Jungle} Jungle は木構造の集まりを表現する。 木には名前がついており、ルートノードの情報も一緒に保持している。 @@ -230,6 +263,12 @@ これは、各スレッドから木構造を新たに作成できるようにするためである。 STM は、スレッド間でデータを共有するためのツールである。STM を利用することでロック忘れによる競合状態や、デッドロックといった問題から解放される。 +\begin{lstlisting}[label=src:node, caption=Treeのデータ型の定義] +data Jungle = Jungle { getJungleMap :: (TVar (Map String Tree)) } +\end{lstlisting} + +TVar というのは、Transactional variablesの略で、STM で管理する変数に対して利用する。 + \subsection{Tree} Jungleが保持する木構造は、内部的には Tree というデータ型で保持している。 Tree は木の名前と、ルートノードの情報を持っている。 @@ -237,7 +276,6 @@ ルートノードの情報はスレッド間で状態を共有する必要がある。 スレッドセーフに取り扱う必要があるため、この情報も Haskell の ソフトウェア・トランザクショナル・メモリ (STM) を用いて管理している。 -TVar というのは、Transactional variablesの略で、STM で管理する変数に対して利用する。 \begin{lstlisting}[label=src:node, caption=Treeのデータ型の定義] data Tree = Tree @@ -245,7 +283,6 @@ , treeName :: String } \end{lstlisting} -\newpage \subsection{Node} Node は木構造を表現するデータ構造である。 再帰的に定義されている。 diff -r 705c29dd2f6d -r 345eacdf29e4 paper/chapter4.tex --- a/paper/chapter4.tex Mon Feb 03 12:00:46 2014 +0900 +++ b/paper/chapter4.tex Mon Feb 03 16:54:48 2014 +0900 @@ -1,9 +1,11 @@ -\chapter{ベンチマーク}\label{ch:bench} -本章では、非破壊的木構造データベース Jungle の読み込みと書き込みの性能の計測を行う。 -また、簡単な掲示板ウェブアプリケーションを作成し、Java を用いた非破壊的木構造データベースとの性能比較を行う。 +\chapter{性能評価}\label{ch:bench} +本章では、非破壊的木構造データベース Jungle がマルチコアプロセッサで性能向上を果たせるのか確認する。 +まずはじめに、並列読み込みと並列書き込みの性能の計測を行う。 +また、掲示板ウェブアプリケーションを作成し、Java を用いた非破壊的木構造データベースとの性能比較を行う。 -\section{計測環境の構築} -学科が提供するブレードサーバを用いて、計測環境を構築する。 +\section{計測環境} +マルチコアプロセッサでの性能を確認するためコア数の多いサーバを用いる。 +本研究では、学科が提供するブレードサーバを用いて、計測環境を構築する。 ブレードサーバの仕様を表\ref{tab:server_spec}に示す。 \begin{table}[!htbp] @@ -21,8 +23,8 @@ \end{center} \end{table} -非破壊的木構造データベース Jungle の読み込みと書き込みの性能の計測には１台、 -簡単な掲示板ウェブアプリケーションを用いた Java との性能比較には２台のブレードサーバを利用する。 +非破壊的木構造データベース Jungle の並列読み込みと並列書き込みの性能の計測には１台、 +掲示板ウェブアプリケーションを用いた Java との性能比較には２台のブレードサーバを利用する。 ２台使用するのは、サーバと負荷をかけるクライアントを別々に実行するためである。 \subsubsection{Haskell および Java のバージョン} @@ -44,109 +46,11 @@ \end{center} \end{table} -\subsubsection{サーバのチューニング} -ウェブアプリケーションのベンチマークを行う際、サーバの設定に注意を払う必要がある。 -適切に設定を行わないと、サーバがボトルネックとなってしまい正しい結果が得られない。 -ウェブアプリケーションのベンチマークを行う際の注意点について述べる。 - -データを受信したり送信したりするのは OS カーネルである。 -多くの TCP パケットを要求し、各パケットのサイズが1500バイトといった大きなファイルを提供する場合、 -ウェブアプリケーションというよりOSカーネルのテストになってしまう。 - -接続には、HTTP Keep-Alivesを利用する。 -新しい TCP 接続を確立するのはとても遅く、OS カーネルによって行われる。 -毎秒多くの新しい接続を作成するようなベンチマークを行うと、OSカーネルのテストとなってしまう。 - -アプリケーションやOSカーネルが完全にハードウェアを使用できるようにするためにいくつか調整を行う必要がある。 -最初の問題は、ファイル記述子の欠如である。 -デフォルトはプロセスあたり、1,024 files で非常に貧弱な結果しか得られない。 -ファイル記述子の現在のリミットは以下のコマンドで取得できる。 +計測環境の構築方法については付録に記載する。 -\begin{lstlisting}[caption=ファイル記述子のリミットの取得] -$ ulimit -aH -\end{lstlisting} - -リミットを変更するには、以下のコマンドを実行する。 - -\begin{lstlisting}[caption=ファイル記述子のリミットの設定] -$ sudo sh -c ulimit -HSn 200000 -\end{lstlisting} - -再起動後も有効にするためには、システムファイルの編集を行う。\\ -/etc/security/limits.conf へ以下の記述を追加する。 - -\begin{lstlisting}[caption=リミットの設定の追加] - * soft nofile 200000 - * hard nofile 200000 -\end{lstlisting} - -次に問題となるのは listenキューの制限である。 -listen キューとは、保留中のコネクションが繋がれるキューのことである。 -このキューの長さの制限が小さいと、同時にたくさんのコネクション要求がきた場合、制限を超えた要求を拒否する。 -listen キューや、その他の設定も含めてベンチマーク用にサーバの設定を変更する。\\ -/etc/sysctl.conf に以下の記述を追加する。 -\begin{lstlisting}[caption=システム設定の変更] -fs.file-max = 5000000 -net.core.netdev_max_backlog = 400000 -net.core.optmem_max = 10000000 -net.core.rmem_default = 10000000 -net.core.rmem_max = 10000000 -net.core.somaxconn = 100000 -net.core.wmem_default = 10000000 -net.core.wmem_max = 10000000 -net.ipv4.conf.all.rp_filter = 1 -net.ipv4.conf.default.rp_filter = 1 -net.ipv4.ip_local_port_range = 1024 65535 -net.ipv4.tcp_congestion_control = bic -net.ipv4.tcp_ecn = 0 -net.ipv4.tcp_max_syn_backlog = 12000 -net.ipv4.tcp_max_tw_buckets = 2000000 -net.ipv4.tcp_mem = 30000000 30000000 30000000 -net.ipv4.tcp_rmem = 30000000 30000000 30000000 -net.ipv4.tcp_sack = 1 -net.ipv4.tcp_syncookies = 0 -net.ipv4.tcp_timestamps = 1 -net.ipv4.tcp_wmem = 30000000 30000000 30000000 -net.ipv4.tcp_tw_reuse = 1 -net.ipv4.tcp_tw_recycle = 1 -\end{lstlisting} - -ファイルを保存後、設定を反映させるには以下のコマンドを実行する。 - -\begin{lstlisting}[caption=設定の反映] -$ sudo sysctl -p /etc/sysctl.conf -\end{lstlisting} - -ベンチマークを行う際、小さなテストでは妥当性が低くなってしまうので注意する。 -TCP/IPのスタックは保守的な方法で動作し、ダウンロード速度に合わせて徐々に速度を増大させるためである。 - -また、テストするサーバより遅いベンチマーククライアントを用いると正しい結果は得られない。 -シングルスレッドで稼働したり、Ruby や Python といった低速なベンチマークツールでテストを行うと、 -すべてのテストする対象が同じようなパフォーマンスを持っているように見えてしまう。 - -\subsubsection{weighttp} -ウェブアプリケーションの性能測定には、weighttpを用いる。 -weighttpはWebサーバの性能測定ツールで、マルチコアCPUを使ってテストできる\cite{weighttp}。 -また、livev を使うことで、モダンなポール・システムコールを利用し、測定性能を向上できるといった特徴を持つ。 -同様の性能測定ツールには、Apache Benchやhttprefが存在するが非力であり、ボトルネックとなってしまうため使用しない。 - -weighttp を起動するには、以下の様にコマンドを入力する。 -\begin{lstlisting}[caption=weighttpの起動] -$ weighttp -n 1000000 -c 1000 -t 10 -k "http://bldsv12.cr.ie.u-ryukyu.ac.jp:3000" -\end{lstlisting} - -起動時には対象のサーバの URL を記述する他に、いくつかのオプションを指定できる。 -\begin{itemize} - \item n ... HTTP リクエストの総数 - \item c ... 同時に接続するコネクションの数 - \item t ... 作製するネイティブスレッドの数 - \item k ... HTTP Keep-Alives を有効にする -\end{itemize} - -\clearpage \section{読み込みの性能計測} -非破壊的木構造データベース Jungle の読み込みの性能計測を行う。 +非破壊的木構造データベース Jungle を用いて、マルチコアプロセッサ上で並列に読み込みを行い、線形に性能向上ができるか調査する。 \subsubsection{計測方法} ブレードサーバ上で、Jungle で作成した木構造を並列に読み込んで性能計測を行う。 @@ -201,7 +105,7 @@ \clearpage \section{書き込みの性能計測} -非破壊的木構造データベース Jungle の書き込みの性能計測を行う。 +非破壊的木構造データベース Jungle を用いて、マルチコアプロセッサ上で並列に書き込みを行い、線形に性能向上ができるか調査する。 \subsubsection{計測方法} ブレードサーバ上で、Jungle に木構造を並列に書き込んで性能計測を行う。 @@ -254,72 +158,24 @@ GHC の IO マネージャーは、マルチスレッドでうまくスケールしないという問題があり、並列度が下がってしまう。 GHCの次期バージョンではIO マネージャーが改善され、スケールするようになる見込みである\cite{iomanager}。 -非破壊的木構造データベース Jungle は、書き込みは並列化率が低くなってしまい並列実行に向いていない。 +非破壊的木構造データベース Jungle は、書き込みは並列化率が低くなってしまっている。 読み込みが高速なため、書き込みより読み込みが多用されるシステムに向いているといえる。 \clearpage \section{ウェブアプリケーションに組み込んでの性能評価} - -\subsection{簡単な掲示板ウェブアプリケーションの実装} -木構造データベース Jungle と Haskell の HTTP サーバ Warp を用いて簡易掲示板システムを作成する。 - -\subsubsection{Warp を用いたウェブアプリケーションの構築} -Warp は、軽量・高速な HTTP サーバである\cite{warp}。 -Haskell の軽量スレッドを活かして書かれている。 -Haskell のウェブフレームワークである Yesod のバックエンドとして用いられており、現在も開発が続けられている。 -Warp のバージョンは 2.0.2 を用いる。 - -Warp を用いてウェブアプリケーションを構築する方法について説明する。 - -% Source Codeは実行可能な状態でsrcに置いてある -% firstline, lastlineで、どの範囲を表示するか指定できる -\lstinputlisting[label=warp_sample, caption=Warpを用いたウェブアプリケーションの例, firstline=9]{src/warp.hs} - -ソースコード \ref{warp_sample}は、URLによって出力する結果を変更するウェブアプリケーションである。 -/hello/worldへアクセスがあった場合は、インクリメントされる counter が表示される。 - -\paragraph*{main} -HTTP サーバを起動するには、Warp の run 関数を利用する。 -run 関数は、利用する Port 番号と、application というリクエストを受けて何かしらのレスポンスを返す関数の2つを引数として受け取る。 - -関数型言語では、関数を第一級オブジェクトとして扱える。 -また、今回は Haskell のカリー化された関数の特性を利用し、main 内で作成した IORef 型の counter を部分適用させている。 +実用的なウェブアプリケーションに組み込んで、妥当な性能が出ているか調査を行う。 -IORef を用いることで、Haskell で更新可能な変数を扱うことができる。 -参照透過性を失うようにみえるが、Haskell は IO モナドを利用することで純粋性を保っている。 -IORef 自体が入出力を行うわけではなく、単なる入出力操作の指示にすぎない。 -IO モナドとして糊付けされた単一のアクションに main という名前を付けて実行することで処理系が入出力処理を行う。 - -\paragraph*{application 及び routes , findRoute} -application の実装では、routes という関数を独自に定義して、URL によって出力を変更している。 -application に渡されるリクエストはデータ型で様々な情報が含まれている。 -その中のひとつに pathInfo という、URL から hostname/port と、クエリを取り除いたリストがある。 -この情報を routes という関数に渡すことで、routeSetting というリストから一致する URL がないか調べる。 -routeSetting は、URL のリストとレスポンスを返す関数のタプルのリストである。 - -\paragraph*{notFound 及び hello} -レスポンスを返す関数は、いくつか定義されている。 -その中で利用されている responseLBS は文字列からレスポンスを構築するためのコンストラクタである。 - -\paragraph*{world 及び incCount} -world は、インクリメントされる counter を表示するための関数である。 -IORef 内のデータは直接触ることができないため、incCount 内で atomicModifyIORef を利用してデータの更新を行なっている。 -atomicModifyIORef は、データの更新をスレッドセーフに行うことができる。 -また、responseLBSで構築したレスポンスは、Resource Tというリーソスの解放を安全に行うために使われるモナドに包まれている。 -lift 関数を用いて、incCountの型を持ち上げ調整している。\\ - - -実際にプログラムを例にして説明したが、Warp は容易にプログラムに組み込むことができる。 -非破壊的木構造データベース Jungle と Warp を組み合わせて、簡単な掲示板ウェブアプリケーションを開発する。 -掲示板としての機能を関数として実装し、routeSetting に登録することでリクエストによって関数を実行する。 +\subsection{掲示板ウェブアプリケーションの実装} +木構造データベース Jungle と Haskell の HTTP サーバ Warp を用いて掲示板ウェブアプリケーションを開発する。 +Warp を用いたウェブアプリケーションの構築法については付録に記載する。 掲示板におけるデータベースへの書き込みは、板の作成と、板への書き込みがある。 Jungle において、板の作成は新しい木構造の作成、板への書き込みは木構造へのノードの追加で表現する。 掲示板へ実装した機能を表\ref{tab:bbs_func}に示す。 \begin{table}[!htbp] -\caption{簡単な掲示板ウェブアプリケーションへ実装した機能一覧} +\caption{掲示板ウェブアプリケーションへ実装した機能一覧} \label{tab:bbs_func} \begin{center} \begin{tabular}{|c||c|} \hline @@ -336,13 +192,9 @@ \subsection{読み込み} \subsubsection{計測方法} 掲示板に対して読み込みを行い、負荷をかける。 -掲示板を立ち上げるサーバと、weighttpを用いて負荷をかけるサーバの 2 台ブレードサーバを用いて測定を行った。 +掲示板を立ち上げるサーバと、性能測定ツール weighttp\cite{weighttp} を用いて負荷をかけるサーバの 2 台ブレードサーバを用いて測定を行った。 -weighttpの起動時のオプションは以下の通りである。 -リクエストの総数は 100 万、同時に接続するコネクションの数は 1,000、実行時のスレッド数は10、HTTP Keep-Alivesを有効とする。 -\begin{lstlisting}[caption=weighttpの起動時のオプション] -weighttp -n 1000000 -c 1000 -t 10 -k "http://bldsv12.cr.ie.u-ryukyu.ac.jp:3000/showBoardMessage?bname=hello" -\end{lstlisting} +weighttpの設定は、リクエストの総数 100 万、同時に接続するコネクションの数 1,000、実行時のスレッド数 10、HTTP Keep-Alivesを有効とする。 HTTP サーバ Warp は、ハイパースレッディングの効果がなくハイパースレッディング利用時に遅くなるため、12 スレッドまでの計測とする。 @@ -424,11 +276,11 @@ \subsection{Javaを用いた非破壊的木構造データベースとの比較} 非破壊的木構造データベースは、Haskell 版と Java 版の2つ存在する。 -簡単な掲示板ウェブアプリケーションを両方の言語で実装し、比較を行う。 +掲示板ウェブアプリケーションを両方の言語で実装し、比較を行う。 Haskell ではフロントエンドとして Warp を利用したが、Java では Jetty を利用する。 Jetty のバージョンは 6.1.26 を用いる。 -Haskell 版と Java 版の簡単な掲示板ウェブアプリケーションをブレードサーバ上で実行し、 +Haskell 版と Java 版の掲示板ウェブアプリケーションをブレードサーバ上で実行し、 weightttpで負荷をかけ100万リクエストを処理するのにかかる時間を計測する。 Haskell と Java の測定結果を表\ref{tab:compare}に示す。 diff -r 705c29dd2f6d -r 345eacdf29e4 paper/conclusion.tex --- a/paper/conclusion.tex Mon Feb 03 12:00:46 2014 +0900 +++ b/paper/conclusion.tex Mon Feb 03 16:54:48 2014 +0900 @@ -1,19 +1,20 @@ -\chapter{結論} \label{ch:conclusion} +\chapter{まとめと今後の課題} \label{ch:conclusion} \section{まとめ} +% 並列環境で動くことを示せた 本研究では、関数型言語 Haskell を用いて並列データベースの実装をおこなった。 Haskell は、型推論と型安全により簡潔で信頼性の高いプログラムを書くことができる。 実装において、Haskellの表現力とコンパイル時に多くのエラーを捕まえるという特徴は、開発期間およびコード行数の短縮に繋がった。 -また、型安全により実行時に不正にプログラムが終了するといったことがない。 +また、型安全により実行時に型エラーによってプログラムが終了するといったことがない。 -実装した並列データベースの読み込みと書き込みについて性能を計測し、読み込みに関して 98.96 \%という高い並列度が確認できた。 -また、簡単な掲示板ウェブアプリケーションを開発し、既存の Java の非破壊的木構造データベースとの比較をおこない、Java のおよそ 2 倍の性能を確認することができた。 +実装した並列データベースの読み込みと書き込みについて性能を計測し、読み込みに関して 98.96 \%という高い並列化率が確認できた。 +また、掲示板ウェブアプリケーションを開発し、既存の Java の非破壊的木構造データベースとの比較をおこない、Java のおよそ 2 倍の性能を確認することができた。 \section{今後の課題} 非破壊的木構造データベース Jungle の今後の課題について述べる。 -\subsection{書き込み処理の並列度の上昇} +\subsubsection{書き込み処理の並列度の上昇} データベースへの書き込み処理において 80.8 \%の並列度しか出ていない。 はじめに、プログラムの変更をせずに、GHC の IO マネージャーの改善によりどの程度並列度が向上するのかを調査する必要がある。 GHC の IO マネージャーの影響度を計測した後、変更処理の改善方法に調査する。 @@ -21,12 +22,12 @@ Haskell では、様々なスレッドセーフな参照型が用意されている。 ロックが制限的だが、高速なIORef、ロックの使えるMVarなどである。 -\subsection{分散データベースとしての実装} +\subsubsection{分散データベースとしての実装} 並列環境で実行できるが、今後は分散データベースとして実行できるようにしたい。 トポロジーの形成機能や、サーバ間でのデータアクセスの仕組みを実装する必要がある。 サーバ間で木構造の変更を共有するには、木構造を何らかの情報に基づいて、マージする仕組みを導入する必要がある。 -\subsection{永続性の実装} +\subsubsection{永続性の実装} 非破壊的木構造データベース Jungle は、オンメモリ上で動作するデータベースである。 並列性を損なわない形で、ディスクへの書き出しを実現したい。 簡単な実装としては、書き出しを担当するスレッドを作成するといったことが考えられる。 diff -r 705c29dd2f6d -r 345eacdf29e4 paper/introduciton.tex --- a/paper/introduciton.tex Mon Feb 03 12:00:46 2014 +0900 +++ b/paper/introduciton.tex Mon Feb 03 16:54:48 2014 +0900 @@ -1,7 +1,6 @@ -\chapter{序論} \label{ch:introduction} +\chapter{研究背景と目的} \label{ch:introduction} \pagenumbering{arabic} -\section{研究背景と目的} ブロードバンド環境やモバイル端末の普及により、ウェブサービスの利用者数は急激に伸びている。 リクエスト数の増加を予想することは困難であり、負荷が増大した場合に容易に拡張できるスケーラビリティが求められる。 ここでいうスケーラビリティとは、利用者や負荷の増大に対し、単なるリソースの追加のみでサービスの質を維持することのできる性質のことである。 @@ -10,22 +9,13 @@ 本研究の目的は、スケーラビリティを実現するデータベースの実装である。 ウェブサービスにおけるスケーラビリティを実現するためには、並列にデータにアクセスできる設計が必要となる。 本研究では並列にデータへアクセスする手法として、非破壊的木構造を利用する。 -非破壊的木構造では、排他制御をせずにデータへアクセスすることが可能でありスケーラビリティを確保できる。 +非破壊的木構造では、排他制御をせずにデータへアクセスすることが可能でありスケーラビリティを確保できる\cite{shoshi:2010a}\cite{shoshi:2011a}\cite{shoshi:2011b}。 データベースの実装には、純粋関数型言語 Haskell を用いる。 Haskell は、モダンな型システムを持ち、型推論と型安全により簡潔で信頼性の高いプログラムを書くことが可能である\cite{types}。 +データベースのやり取りするデータにも型が付くため、セキュリティホールを突くような攻撃の多くが無害化される。 また、Haskellは純粋であるため、関数は引数が同じならば必ず同じ値を返すことが保証されている。 これは、並列処理において並列化に適した部分が分かりやすくなるというメリットがあり、また状態に依存したバグから解放されることも意味する。 -本論文では、Haskellを用いて非破壊的木構造データベースを実装し、スケーラビリティを実現できることを明らかにする。 -\newpage - -\section{本論文の構成} - -本論文では、データベースの実装によって得られた知見について述べる。 - -第\ref{ch:haskell}章では、純粋関数型言語 Haskell の特徴及び Haskell を用いた並列プログラミングについて述べる。 -第\ref{ch:design}章では、非破壊的木構造を用いたスケーラビリティ確保の方法について考察し、Haskellを用いたデータベースの設計について述べる。 -第\ref{ch:impl}章では、Haskellを用いた非破壊的木構造データベースの実装と、その利用方法について述べる。 -第\ref{ch:bench}章では、実装したデータベースの性能評価を行う。 -実装したデータベースを用いて、簡単な掲示板ウェブアプリケーションを開発し、Java による非破壊的木構造データベースとの比較を行う。 +本論文では、Haskellを用いて非破壊的木構造データベースを実装し、読み込みに関して高い並列化率を達成することができ、マルチコアプロセッサの性能を引き出すことができた。 +また、掲示板ウェブアプリケーションを開発し、既存の Java の非破壊的木構造データベースとの比較をおこない、Java のおよそ 2倍の性能を確認することができた。 diff -r 705c29dd2f6d -r 345eacdf29e4 paper/master_paper.bib --- a/paper/master_paper.bib Mon Feb 03 12:00:46 2014 +0900 +++ b/paper/master_paper.bib Mon Feb 03 16:54:48 2014 +0900 @@ -1,17 +1,19 @@ @article{iomanager, author = "Andreas Voellmy and Junchang Wang and Paul Hudak and Kazuhiko Yamamoto", - title = "Mio: A High-Performance Multicore IO Manager for GHC", + title = "Mio: A High-Performance Multicore {IO} Manager for {GHC}", journal = "Haskell Symposium", year = "2013", month = "September" } -@article{cap, - author = "Nancy Lynch and Seth Gilbert", - title = "Brewer's conjecture and the feasibility of consistent, available, partition-tolerant web services", - journal = "ACM SIGACT News", - year = "2002" -} +@inproceedings{amdahl, + author = {Amdahl, Gene M.}, + title = {Validity of the Single Processor Approach to Achieving Large Scale Computing Capabilities}, + booktitle = {Proceedings of the April 18-20, 1967, Spring Joint Computer Conference}, + series = {AFIPS '67 (Spring)}, + year = {1967}, + pages = {483--485}, +} @misc{warp, title = {The warp package}, @@ -39,14 +41,14 @@ } @misc{deos, - title = {DEOS}, + title = {{DEOS}}, howpublished = "\url{http://www.dependable-os.net/osddeos/data.html}", note = "[Online; accessed 29-Jan-2014]" } @article{shoshi:2010a, author = "玉城 将士 and 河野 真治", - title = "Cassandraを使ったCMSのPCクラスタを使ったスケーラビリティの検証", + title = "Cassandraを使った{CMS}の{PC}クラスタを使ったスケーラビリティの検証", journal = "日本ソフトウェア科学会", month = "August", year = 2010 @@ -54,7 +56,7 @@ @article{shoshi:2011a, author = "玉城 将士 and 河野 真治", - title = "Cassandraを使ったスケーラビリティのあるCMSの設計", + title = "Cassandraを使ったスケーラビリティのある{CMS}の設計", journal = "情報処理学会", month = "March", year = 2011 @@ -62,7 +64,7 @@ @article{shoshi:2011b, author = "玉城 将士 and 河野 真治", - title = "Cassandraと非破壊的構造を用いたCMSのスケーラビリティ検証環境の構築", + title = "Cassandraと非破壊的構造を用いた{CMS}のスケーラビリティ検証環境の構築", journal = "日本ソフトウェア科学会", month = "August", year = 2011 @@ -70,7 +72,7 @@ @article{toma:2013, author = "當眞 大千 and 河野 真治 and 永山 辰巳", - title = "Haskell による非破壊的木構造を用いた CMS の実装", + title = "Haskell による非破壊的木構造を用いた {CMS} の実装", journal = "日本ソフトウェア科学会", month = "September", year = 2013 diff -r 705c29dd2f6d -r 345eacdf29e4 paper/master_paper.pdf Binary file paper/master_paper.pdf has changed diff -r 705c29dd2f6d -r 345eacdf29e4 paper/master_paper.tex --- a/paper/master_paper.tex Mon Feb 03 12:00:46 2014 +0900 +++ b/paper/master_paper.tex Mon Feb 03 16:54:48 2014 +0900 @@ -19,7 +19,6 @@ breaklines=true, captionpos=b, columns=[l]{fullflexible},% - numbers=left,% xrightmargin=0zw,% xleftmargin=1zw,% aboveskip=1zw, @@ -31,7 +30,7 @@ \input{font.sty} -\jtitle{関数型言語 Haskell による並列データベースの実装} +\jtitle{関数型言語 Haskell による\\並列データベースの実装} \etitle{} \year{平成26年度} \affiliation{\center% @@ -83,6 +82,7 @@ \input{chapter3.tex} \input{chapter4.tex} \input{conclusion.tex} +\input{appendix1.tex} %謝辞 \input{thanx.tex} diff -r 705c29dd2f6d -r 345eacdf29e4 paper/thanx.tex --- a/paper/thanx.tex Mon Feb 03 12:00:46 2014 +0900 +++ b/paper/thanx.tex Mon Feb 03 16:54:48 2014 +0900 @@ -3,7 +3,7 @@ 本研究を行うにあたり、日頃より多くの助言、ご指導いただきました河野真治助教授に心より感謝申し上げます。 -本研究は、JST/CREST 研究領域「実用化を目指した組み込みシステム用ディペンダブル・ オペレーティングシステム」D-ADD 研究チームとして実施しました。 +本研究は、JST/CREST 研究領域「実用化を目指した組み込みシステム用ディペンダブル・ オペレーティングシステム」\cite{deos} D-ADD 研究チームとして実施しました。 研究の機会を与えてくださった、株式会社 Symphony の永山辰巳さんに感謝します。 また、データベースの実装にあたり、多くの議論にお付き合い頂いた大城信康さん、並列信頼研究室の全てのメンバーに感謝いたします.