\chapter{ベンチマーク}\label{ch:bench}
本章では、非破壊的木構造データベース Jungle の読み込みと書き込みの性能の計測を行う。
また、簡単な掲示板ウェブアプリケーションを作成し、Java を用いた非破壊的木構造データベースとの性能比較を行う。

\section{計測環境の構築}
学科が提供するブレードサーバを用いて、計測環境を構築する。
ブレードサーバの仕様を表\ref{tab:server_spec}に示す。

\begin{table}[!htbp]
\caption{学科が提供するブレードサーバの仕様}
\label{tab:server_spec}
\begin{center}
\begin{tabular}{|c||c|} \hline
名前 & 概要 \\ \hline \hline
CPU & Intel(R) Xeon(R) CPU X5650@2.67GHz * 2\\ \hline
物理コア数 & 12 \\ \hline
論理コア数 & 24 \\ \hline
Memory & 126GB \\ \hline
OS & Fedora 14 \\ \hline
\end{tabular}
\end{center}
\end{table}

非破壊的木構造データベース Jungle の読み込みと書き込みの性能の計測には１台、
簡単な掲示板ウェブアプリケーションを用いた Java との性能比較には２台のブレードサーバを利用する。
２台使用するのは、サーバと負荷をかけるクライアントを別々に実行するためである。

\subsubsection{Haskell および Java のバージョン}
Haskell のコンパイラには The Glasgow Haskell Compiler（GHC）を使用する。
GHC は、Haskell で最も広く使われているコンパイラである。
ソフトウェア・トランザクショナル・メモリをサポートするなど、並列プログラミングのためのHaskellの拡張が行われている。

Haskell および Java のバージョンを表\ref{tab:compiler}に示す。

\begin{table}[!htbp]
\caption{ベンチマークで利用したHaskellとJavaのバージョン}
\label{tab:compiler}
\begin{center}
\begin{tabular}{|c||c|} \hline
言語 & バージョン \\ \hline \hline
Haskell & Glasgow Haskell Compiler, Version 7.6.3 \\ \hline
Java & Java(TM) SE Runtime Environment (build 1.7.0\_51-b13) \\ \hline
\end{tabular}
\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 の読み込みの性能計測を行う。

\subsubsection{計測方法}
ブレードサーバ上で、Jungle で作成した木構造を並列に読み込んで性能計測を行う。
まず、Jungle を利用して木構造を作成する。
並列に実行する際に、読み込みに負荷がかかるように木構造はある程度の大きさとする。
今回は木の深さが 8、ノードの数が約 80 万の大きさの木構造を使用する。

木構造を読み込み、ノードの数を数えるタスクを 1,000 個作成し並列実行する。
非破壊的木構造は、木構造に変更を加えても他の読み込みのタスクに影響を与えない。
そのことを確認するために、木構造は各タスクに渡す前に無作為にノードを追加する。

\subsubsection{計測結果}
非破壊的木構造データベース Jungle の読み込みの計測結果を表\ref{tab:par_read}に示す。

CPUコア数を増やしていくと、実行時間が短くなっていることが分かる。
シングルスレッドで実行した場合と比較して、2 スレッドで 1.79 倍、12 スレッドで 10.77 倍の性能向上が見られる。
13 スレッド以上は、Intel のハイパースレッディング機能を利用して計測した。
ハイパースレッディングは、１つのプロセッサをあたかも２つのプロセッサであるかのように扱う技術である。
同時に演算器などを利用することはできないため性能が２倍になるわけではないが、概ね20 \%程度クロックあたりの性能が向上すると言われている。
実際の計測では、13 スレッド以上は、12スレッドより速くなることもあるが、遅くなる場合もあるなど安定しない結果となっている。


\begin{table}[!htbp]
\caption{読み込みの計測結果}
\label{tab:par_read}
\begin{center}
\begin{tabular}{|c||r|} \hline
CPU数 & 実行時間 \\ \hline
1 & 59.77 s\\ \hline
2 & 33.36 s\\ \hline
4 & 15.63 s\\ \hline
8 & 8.10 s\\ \hline
12 & 5.55 s\\ \hline
16 & 5.65 s\\ \hline
20 & 5.23 s\\ \hline
24 & 5.77 s\\ \hline
\end{tabular}
\end{center}
\end{table}

性能向上率のグラフを図\ref{fig:benchmark_read}に示す。
線形に近い形で性能が向上していることが分かる。
12 スレッドで実行した場合の並列化率は 98.96 \%で、非破壊的木構造データベース Jungle は読み込みにおいてスケールするデータベースであることが分かる。

\begin{figure}[!htbp]
 \caption{読み込みの性能向上率}
 \begin{center}
  \includegraphics[width=90mm]{./images/read.pdf}
 \end{center}
 \label{fig:benchmark_read}
\end{figure}

\clearpage
\section{書き込みの性能計測}
非破壊的木構造データベース Jungle の書き込みの性能計測を行う。

\subsubsection{計測方法}
ブレードサーバ上で、Jungle に木構造を並列に書き込んで性能計測を行う。
木の深さが 6、ノードの数が約 1 万の大きさの木構造を作成しJungle に登録するタスクを 1,000 個作成し、並列に実行する。
書き込んだ木構造はノードの数が整合しているかどうか確認する。その後正確に書き込まれてるタスクの数を出力する。
Haskell は遅延評価のため、出力などを挟むことで評価が行われるようにしなければならない。

\subsubsection{計測結果}
非破壊的木構造データベース Jungle の書き込みの計測結果を表\ref{tab:par_write}に示す。

CPUコア数を増やしていくと、実行時間が短くなっていることが分かる。
シングルスレッドで実行した場合と比較して、2 スレッドで 1.55 倍、12 スレッドで 3.86 倍の性能向上が見られる。
読み込みと比べ、書き込みはJungleへの登録作業があるため並列化率が下がり、性能向上率が低いことが分かる。

ハイパースレッディングは効果がなく、13 スレッド以上では実行時間が遅くなっている。


\begin{table}[!htbp]
\caption{書き込みの計測結果}
\label{tab:par_write}
\begin{center}
\begin{tabular}{|c||r|} \hline
CPU数 & 実行時間 \\ \hline
1 & 52.68 s\\ \hline
2 & 33.92 s\\ \hline
4 & 20.11 s\\ \hline
8 & 15.31 s\\ \hline
12 & 13.62 s\\ \hline
16 & 14.92 s\\ \hline
20 & 18.62 s\\ \hline
24 & 16.63 s\\ \hline
\end{tabular}
\end{center}
\end{table}

性能向上率のグラフを図\ref{fig:benchmark_write}に示す。
書き込みは並列化率が低く、性能向上が 4 倍程度で止まっている。
12 スレッドで実行した場合の並列化率は 80.8 \%である。

\newpage
\begin{figure}[!htbp]
 \caption{書き込みの性能向上率}
 \begin{center}
  \includegraphics[width=90mm]{./images/write.pdf}
 \end{center}
 \label{fig:benchmark_write}
\end{figure}

Jungle へ登録する際に他のスレッドから登録があった場合に、ソフトウェア・トランザクショナル・メモリが処理をやり直すため、並列度が下がっていると思われるが、GHCの問題も考えられる。
GHC の IO マネージャーは、マルチスレッドでうまくスケールしないという問題があり、並列度が下がってしまう。
GHCの次期バージョンではIO マネージャーが改善され、スケールするようになる見込みである。\cite{iomanager}

非破壊的木構造データベース 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 に登録することでリクエストによって関数を実行する。

掲示板におけるデータベースへの書き込みは、板の作成と、板への書き込みがある。
Jungle において、板の作成は新しい木構造の作成、板への書き込みは木構造へのノードの追加で表現する。
掲示板へ実装した機能を表\ref{tab:bbs_func}に示す。

\begin{table}[!htbp]
\caption{簡単な掲示板ウェブアプリケーションへ実装した機能一覧}
\label{tab:bbs_func}
\begin{center}
\begin{tabular}{|c||c|} \hline
  関数名 & 概要 \\ \hline \hline
  showBoard & 板の一覧を表示 \\ \hline
  createBoard & 板の作成 \\ \hline
  showBoardMessage & 板への書き込みの一覧を表示 \\ \hline
  createBoardMessage & 板への書き込み \\ \hline
  editMessage & 板への書き込みの編集 \\ \hline
\end{tabular}
\end{center}
\end{table}

\subsection{読み込み}
\subsubsection{計測方法}
掲示板に対して読み込みを行い、負荷をかける。
掲示板を立ち上げるサーバと、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}

HTTP サーバ Warp は、ハイパースレッディングの効果がなくハイパースレッディング利用時に遅くなるため、12 スレッドまでの計測とする。

\subsubsection{計測結果}

掲示板の読み込みの計測結果を表\ref{tab:bbs_read}に示す。

並列で実行した場合、実行時間が短くなっているが性能向上率が低いことが分かる。
これは HTTP サーバ Warp がボトルネックとなってしまっているためだと考えられる。

Warp を用いてアクセスした際に、"hello, world"と返すだけのプログラムを作成し測定する。
結果を表\ref{tab:warp}に示す。
1 スレッドで実行した場合は、Jungle と組み合わせた掲示板より速い。
しかしながら、スレッド数が増えていくと掲示板の読み込みとあまり結果が変わらなくなってしまう。
Warpは、HTTP サーバのため IO 処理を多用する。この問題は、GHC の IO マネージャーの改良で改善される可能性が高い。

\begin{table}[!htbp]
\caption{掲示板を利用した読み込みの計測結果}
\label{tab:bbs_read}
\begin{center}
\begin{tabular}{|c||r|} \hline
CPU数 & 実行時間 \\ \hline
1 & 60.72 s\\ \hline
2 & 37.74 s\\ \hline
4 & 28.97 s\\ \hline
8 & 27.73 s\\ \hline
12 & 28.33 s\\ \hline
\end{tabular}
\end{center}
\end{table}

\begin{table}[!htbp]
\caption{Warpの計測結果}
\label{tab:warp}
\begin{center}
\begin{tabular}{|c||r|} \hline
CPU数 & 実行時間 \\ \hline
1 & 49.28 s\\ \hline
2 & 35.45 s\\ \hline
4 & 25.70 s\\ \hline
8 & 27.90 s\\ \hline
12 & 29.23 s\\ \hline
\end{tabular}
\end{center}
\end{table}

ウェブアプリケーションを用いて実験する場合、データベースだけがボトルネックとなるように負荷をかけるのは難しい。
ただ単にデータを大きくするだけでは、文字列をHTMLに変換するコストが大きくなってしまうためである。

\subsection{書き込み}
\subsubsection{計測方法}
掲示板に対して書き込みを行い、負荷をかける。
掲示板を立ち上げるサーバと、weighttpを用いて負荷をかけるサーバの 2 台ブレードサーバを用いて測定を行った。

weighttpでは、GET しかできないためURLのクエリ文字列でデータを書き込めるように掲示板ウェブアプリケーションを変更した。
weightttp起動時のオプションは、読み込みと同じである。
\subsubsection{計測結果}

掲示板の書き込みの計測結果を表\ref{tab:bbs_write}に示す。
並列で実行した場合、実行時間が短くなっているが性能向上率が低いことが分かる。
これも HTTP サーバ Warp がボトルネックとなってしまっているためだと考えられる。

\newpage
\begin{table}[!htbp]
\caption{掲示板を利用した書き込みの計測結果}
\label{tab:bbs_write}
\begin{center}
\begin{tabular}{|c||r|} \hline
CPU数 & 実行時間 \\ \hline
1 & 54.16 s\\ \hline
2 & 36.71 s\\ \hline
4 & 31.74 s\\ \hline
8 & 31.58 s\\ \hline
10 & 32.64 s\\ \hline
12 & 32.68 s\\ \hline
\end{tabular}
\end{center}
\end{table}

\subsection{Javaを用いた非破壊的木構造データベースとの比較}
非破壊的木構造データベースは、Haskell 版と Java 版の2つ存在する。
簡単な掲示板ウェブアプリケーションを両方の言語で実装し、比較を行う。
Haskell ではフロントエンドとして Warp を利用したが、Java では Jetty を利用する。
Jetty のバージョンは 6.1.26 を用いる。

Haskell 版と Java 版の簡単な掲示板ウェブアプリケーションをブレードサーバ上で実行し、
weightttpで負荷をかけ100万リクエストを処理するのにかかる時間を計測する。
Haskell と Java の測定結果を表\ref{tab:compare}に示す。

\begin{table}[!htbp]
\caption{HaskellとJavaの比較}
\label{tab:compare}
\begin{center}
\begin{tabular}{|c||r|r|} \hline
  測定 & Haskell & Java \\ \hline \hline
  読み込み & 28.33 s & 53.13 s \\ \hline
  書き込み & 32.68 s & 76.4 s \\ \hline
\end{tabular}
\end{center}
\end{table}

Haskell 版は、Java 版と比較して読み込みで 1.87 倍、書き込みで 2.3 倍の性能が出ている。

書き込みが読み込みより性能差が出ている理由として遅延評価が考えられる。
Haskell では書き込みを行う際、完全に評価せず thunk として積み上げていく。
thunkとは、未評価の式を追跡するのに使われるものである。
遅延評価は、グラフ簡約があるため先行評価より簡約ステップ数が増えることはない。
また、不要な計算が省かれるので簡約ステップ数が少なくなることもある。
しかしながら、計算の所用領域が増えてしまうのが難点で、
ハードウェアが効率的に利用できるメモリの範囲内に収まらなければ即時評価より実行時間が遅くなってしまうことがあるので注意が必要である。
本実験では、潤沢にメモリを割り当てているためそういった問題は起きない。