% Sample file for the use of compsoft style file.
%
\documentclass[T]{compsoft}

% Preamble
%
% 「コンピュータソフトウェア」誌に掲載される論文の場合，次で
% 巻数，号数，開始ページ，終了ページを指定する．
%\volNoPp{16}{5}{78}{83}

% ワークショップによる推薦論文の場合，ワークショップ名を指定する．
% \suisen{ワークショップ名}

% 特集の場合，特集のタイトルを与える．
% \tokushu{特集のタイトル}

% 大会論文の場合，\taikai で開催年を指定する．ここで指定した年から
% 大会の回数は計算される．
\taikai{2013}

\pagestyle {empty}

% ここに，使用するパッケージを列挙する．
\usepackage[dvipdfmx]{graphicx}
\usepackage{url}
\usepackage{listings,jlisting}

\lstset{
    language=Haskell,%プログラミング言語によって変える。
    basicstyle={\ttfamily\footnotesize},
    tabsize=2,
    frame=single,
    breaklines=true,%折り返し
    captionpos=b
}
% ユーザが定義したマクロなどはここに置く．ただし学会誌のスタイルの
% 再定義は原則として避けること．

\begin{document}

% 論文のタイトル
\title{Haskellによる非破壊的木構造を用いたCMSの実装}

% 著者
% 和文論文の場合，姓と名の間には半角スペースを入れ，
% 複数の著者の間は全角スペースで区切る
%
\author{當眞 大千 \and 河野 真治
%
% ここにタイトル英訳 (英文の場合は和訳) を書く．
%
\ejtitle{Implementation of the CMS using Nondestructive Tree Structure and Haskell}
%
% ここに著者英文表記 (英文の場合は和文表記) および
% 所属 (和文および英文) を書く．
% 複数著者の所属はまとめてよい．
%
\shozoku{Daichi TOMA, Shinij KONO}{琉球大学大学院理工学研究科情報工学専攻並列信頼研究室}%
{Dept.Concurrency Reliance Laboratory, Information Engineering Course, Faculty of Engineering Graduate School of Engineering and Science, University of the Ryukyus}
%
% 出典情報は \shutten とすれば出力される．
%\shutten
%
% 受付年月日，記事カテゴリなどは自動的に生成される．
%\uketsuke{1999}{8}{3}
%
% その他，脚注に入れるものがあれば，\note に記述する．
%\note{脚注に入れる内容}
}

%
% 和文アブストラクト
\Jabstract{%
ウェブサービスではユーザの増加に対応し、容易に拡張できるスケーラビリティが求められる。 
コンテンツマネージメントシステムにおいてスケーラビリティを実現するためには、並列にデータへアクセスできる設計が必要となる。 
本研究では、編集元の木構造を破壊することなく編集できる非破壊的木構造を利用する。
非破壊的木構造では、少ない排他制御で変更を行えるためスケーラビリティを確保できる。 
コンテンツマネージメントシステムの実装にはプログラミング言語 Haskell を用いた。
Haskell で書かれた HTTP サーバ Warp を用いて簡易掲示板システムを開発し、既存の Java の実装と比較して短い開発期間やコード行数で、同程度の性能を達成できた。
}

%
% 英文アブストラクト（大会論文には必要なし)
% \Eabstract{}
%
\maketitle
\thispagestyle {empty}

\section{はじめに}
ブロードバンド環境やモバイル端末の普及により、ウェブサービスの利用者数は急激に伸びている。
リクエスト数の増加を予想することは困難であり、負荷が増大した場合に容易に拡張できるスケーラビリティが求められる。
ここでいうスケーラビリティとは、利用者や負荷の増大に対し、単なるリソースの追加のみでサービスの質を維持することができる性質のことである。
コンテンツマネージメントシステムにおいてスケーラビリティを実現するためには、並列にデータへアクセスできる設計が必要となる。
本研究では、編集元の木構造を破壊することなく編集できる非破壊的木構造を利用する。
非破壊的木構造では、排他制御を行わずに変更を行えるためスケーラビリティを確保できる。 

コンテンツマネージメントシステムの実装には、プログラミング言語 Haskell を用いた。
Haskell は 純粋関数型プログラミング言語である。
純粋であるため、一度定義した変数の書き換えは許されていない。
また、生産性が高いことも特徴で、本システムの実装においても開発期間およびコード行数は非常に短くなった。

Haskellで書かれたHTTPサーバ Warp を用いて簡易掲示板システムを開発し、既存のJavaの実装と同程度の性能を達成できた。

\section{Haskell}
Haskell は、純粋関数型プログラミング言語である。
関数型プログラミング言語では、引数に関数を作用させていくことで計算を行う。
変数への代入は一度のみで、書き換えることはできない。
遅延評価や、強い静的型付けも Haskell の特徴である。

\section{Warp}
Warp\cite{warp} は、軽量、高速な HTTP サーバである。
Haskell の軽量スレッドを活かして書かれている。
Haskell の ウェブフレームワーク である Yesod のバックエンドとして用いられており、現在も開発が続けられている。

\subsection{Warp を用いたウェブアプリケーションの構築}
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 関数}
world は、インクリメントされる counter を表示するための関数である。
IORef 内のデータは直接触ることができないため、atomicModifyIORef を利用してデータの更新を行なっている。
atomicModifyIORef は、データの更新をスレッドセーフに行うことができる。

実際にプログラムを例にして説明したが、Warp は容易にプログラムに組み込むことができる。
我々のシステムでは Warp を用いて開発を行う。

\section{コンテンツマネージメントシステムの設計}
コンテンツマネージメントシステムのデータ構造としては木構造を用いる。
また、スケーラビリティのある CMS の実現のために非破壊的木構造\cite{shoshi:2011a}を採用する。
非破壊的木構造とは、編集元の木構造を破壊することなく新しい木構造を構成することで木構造を編集する方法である。

破壊的木構造と異なりロックせずに並列に読むことができるため、自由にコピーを作成することが可能である。
コピーを複数作成し、アクセスを分散させることで性能を維持することができる。

通常の破壊的木構造との違いを説明する。

\subsection{破壊的木構造}
破壊的木構造は、木構造を編集する際に木構造を置き換えることにより編集を実現する。
図\ref{fig:destructive_tree_modification}では, ノード6をノードAへ書き換える処理を行なっている.

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[width=70mm]{./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=70mm]{./images/destructive_tree_modification_in_lace.pdf}
 \end{center}
 \caption{競合状態に陥る木構造の破壊的編集}
 \label{fig:destructive_tree_modification_in_lace}
\end{figure}

この状態を回避するためには、木構造にアクセスする際は木構造をロックする。
しかし、ロックするということは排他処理を行い、木構造を利用している処理がひとつであることを保証するものであるため、並列度を下げることになる。
結果、スケーラビリティを損なってしまうため、本システムに破壊的木構造は向かないことが分かる。

\subsection{非破壊的木構造}
非破壊的木構造は、木構造を書き換えることなく編集を行うため、読み書きを並列に行うことが可能である。
図\ref{fig:nondestructive_tree_modification}では、図\ref{fig:destructive_tree_modification}同様に、ノード 6 をノード A へ書き換える処理を行なっている。

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[width=70mm]{./images/nondestructive_tree_modification.pdf}
 \end{center}
 \caption{木構造の非破壊的編集}
 \label{fig:nondestructive_tree_modification}
\end{figure}

非破壊的木構造の基本的な戦略は、変更したいノードへのルートノードからのパスを全てコピーする。
そして、パス上に存在しない (編集に関係のない) ノードはコピー元の木構造と共有することである。

編集は以下の手順で行われる。

\begin{enumerate}
\item{変更したいノードまでのパスを求める。}
\item{変更したいノードをコピーし、コピーしたノードの内容を変更する。}
\item{求めたパス上に存在するノードをルートノードに向かって、コピーする。 コピーしたノードに一つ前にコピーしたノードを子供として追加する。}
\item{影響のないノードをコピー元の木構造と共有する。}
\end{enumerate}

この編集方法で破壊的木構造の場合と同様に、ある時点の木構造を参照する閲覧者と編集する編集者を考える。
閲覧者が木構造を参照している中、編集者が非破壊的な編集を行う。
しかし、破壊的な方法とは異なり、元の木構造は破壊されることはないため編集後も整合性は崩れることはない(図\ref{fig:nondestructive_tree_modification_in_lace})。
ロックをせずに並列に読み書きが可能であるため、スケーラブルなシステムに有用であると考えられる。
元の木構造は破壊されることがないため、自由にコピーを作成しても構わない。したがってアクセスの負荷の分散も可能である。

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[width=70mm]{./images/nondestructive_tree_modification_in_lace.pdf}
 \end{center}
 \caption{並列に読み書きが可能な非破壊的木構造}
 \label{fig:nondestructive_tree_modification_in_lace}
\end{figure}

非破壊的木構造を用いて、コンテンツマネージメントシステムの開発を行う。

\section{コンテンツマネージメントシステムの実装}
コンテンツマネージメントシステムのデータ構造としては木構造を用いると述べた。
我々が開発している木構造データベース Jungle \cite{shoshi:2011b} について説明する。

Jungle は、非破壊的木構造を扱う木構造データベースで、既に Java による実装が存在する。
本研究では、Haskell を用いて実装を行った。
コンテンツマネージメントシステムに組み込んで利用しているが、他のシステムに組み込むことも可能である。

\subsection{利用方法}
\paragraph*{木の作成}
はじめに、データベースオブジェクトと木の作成方法について述べる。
Jungle は複数の木を保持することができる。
木には名前がついており、名前を利用して作成・編集・削除を行うことができる。\\

\begin{lstlisting}[label=new_jung, caption=データベースオブジェクトと木の作成]
jungle = createJungle
new_jung = createTree jungle "new_tree"
\end{lstlisting}

createTree 関数を利用して木構造を作成する。

\paragraph*{木と木を構成するノード}

データベースオブジェクトを作成し、木構造とルートノードを取得するためには以下のように記述する。

\begin{lstlisting}[label=get_tree, caption=木とノードの取得]
tree = getTreeByName new_jung "new_tree"
node = getRootNode tree
\end{lstlisting}

getTreeByName 関数で名前を指定することで木構造を取得できる。
getRootNode 関数でルートノードを取得できる。

\paragraph*{木の編集}

addNewChildAt 関数で、ノードに新しい子を追加することができる。
また、putAttribute 関数で、ノードが持つ連想リストを編集できる。
どのノードを編集するかという情報は、ルートノードからのパスを渡すことで解決する。
木を編集したあと、updateTree 関数を用いて既存のJungleに変更を加え新しいJungleを作成する。

\begin{lstlisting}[label=get_tree, caption=木の編集]
new_tree  = addNewChildAt tree [0,1] 0
new_tree2 = putAttribute new_tree [0,1,0] "key" "value"
new_jungle = updateTree jungle new_tree2
\end{lstlisting}

毎回、新しい変数に代入することで記述が少々煩雑になりやすい。
State モナドを用いて記述を簡易にしたものもあるが、利用者にどのようなAPIを提供するかは検討中である。

\subsection{実装の詳細}
\paragraph*{Treeの取り扱い}
Jungle の Tree の取り扱いには、Haskell の Map を用いている。
Mapは、平衡木を使った Haskell の連想リストである。
連想リストを用いて、木の名前と Tree 自体を結びつけている。

\paragraph*{データ構造}
木のデータ構造は、データ型で定義されている。

\begin{lstlisting}[label=node, caption=データ構造]
data Node = Empty
          | Node
          { children   :: Children
          , attributes :: Attributes
          } deriving (Show)
\end{lstlisting}

各ノードは、Childrenとしてノードを複数持つことができる。
ChildrenおよびAttributesも、Map を用いて定義されている。

\paragraph*{ルートノードの取り扱い}
非破壊的木構造であっても、どのノードが最新のルートノードなのかという情報が必要である。
スレッドセーフに取り扱う必要があるため、Haskell のソフトウェア・トランザクショナル・メモリを用いて管理している。

\section{木構造データベース Jungle を用いた CMS の検証}
木構造データベース Jungle 及び Warp を用いて簡単な掲示板ウェブアプリケーションを作成した。
同様のウェブアプリケーションを、Java による Jungle 実装 及び Cassandra\cite{cassandra} 上でも動かし性能比較を行う。
Cassandra は、Facebook が自社のために開発した分散 Key-Value ストアデータベースであり、Dynamo\cite{dynamo}とBigTable\cite{bigtable}を合わせた特徴を持っている。
Java 版では、組み込みウェブサーバである Jetty を利用する。

\subsection{実験方法}
複数のクラスタを利用して、サーバに対して並列にアクセスを 5000 回行い、それぞれクラスタの実行平均時間をとる。
クラスタ台数を増やすことにより並列度を上昇させ、並列度の実行時間の平均をグラフ化する。
測定するのは書き込みと読み込みであり、掲示板のメッセージの取得と掲示板のメッセージの編集を行う。

\subsection{実験環境}
負荷をかける対象であるサーバは、マルチコア環境が生かされているか確認するためにコア数の多いマシンを用いる。
サーバの仕様を表\ref{tab:server_spec}に示す。

\begin{table}[!htbp]
\caption{検証に使用するサーバーの仕様}
\label{tab:server_spec}
\begin{center}\small
\begin{tabular}{|c||c|} \hline
名前 & 概要 \\ \hline \hline
CPU &  Intel\textregistered Xeon\textregistered X5650 @2.67GHz * 2 \\ \hline
物理コア数 & 12 \\ \hline
論理コア数 & 24 \\ \hline
Memory & 132GB \\ \hline
OS & Fedora 16 \\ \hline
JavaVM & 1.6.0\_39-b04 \\ \hline
GHC & 7.6.3 \\ \hline
\end{tabular}
\end{center}
\end{table}

Warp 及び Cassandra, Jetty は表\ref{tab:bulletinboard_components}のバージョンを利用した。

\begin{table}[!htbp]
\caption{Warp と Cassandra, Jetty のバージョン}
\label{tab:bulletinboard_components}
\begin{center}
\begin{tabular}{|c||c|} \hline
名前 & バージョン \\ \hline \hline
Warp & 1.3.9 \\ \hline
Cassandra & 1.2.6 \\ \hline
Jetty & 6.1.26 \\ \hline
\end{tabular}
\end{center}
\end{table}

サーバに並列に負荷をかけるクラスタの仕様を表\ref{tab:cluster_spec_vmware}に示す。
クラスタは最大で45台使用する。

\begin{table}[!htbp]
\caption{検証に利用するクラスタの仕様}
\label{tab:cluster_spec_vmware}
\begin{center}\small
\begin{tabular}{|c||c|} \hline
名前 & 概要 \\ \hline \hline
CPU &  Intel\textregistered Xeon\textregistered X5650 @2.67GHz \\ \hline
Memory & 8GB \\ \hline
OS & CentOS 5.6 \\ \hline
HyperVisor & VMWare ESXi \\ \hline
\end{tabular}
\end{center}
\end{table}

\subsection{実験結果}
読み込みの実験結果を図\ref{fig:read}、書き込みの実験結果を図\ref{fig:write}に示す。

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[width=70mm]{./images/read.pdf}
 \end{center}
 \caption{読み込みの実験結果}
 \label{fig:read}
\end{figure}

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[width=70mm]{./images/write.pdf}
 \end{center}
 \caption{書き込みの実験結果}
 \label{fig:write}
\end{figure}

Haskell版およびJava版のJungleは、ほぼ同程度の速度が出ていることが分かる。
また、Cassandraと比較して、僅かながらJungleが速く処理を終えている。

\subsection{遅延評価}

Haskell は遅延評価を行うが、書き込みの際に問題が生じる。
何かしらの結果を表示するまで、簡約可能な式の状態で積まれたままとなる。
その際メモリを消費し、効率のよい領域に入りきらないサイズになると非常に実行結果が遅くなる。
図\ref{fig:write}の結果では、オプションで推奨されるヒープ領域のサイズを変更してある。
推奨されるヒープ領域のサイズを変更しない場合の実験結果を図\ref{fig:delay}に示す。

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[width=70mm]{./images/delay.pdf}
 \end{center}
 \caption{推奨されるヒープ領域のサイズを変更しない場合の実験結果}
 \label{fig:delay}
\end{figure}

急に実行時間が下がっている点が3箇所あるが、手動で掲示板の表示を挟んだ箇所である。
数万回以上の書き込みを処理するため、書き込みが積まれている状態ではじめて掲示板を表示する際は数秒かかる。
書き込みは、インクリメントしている値を書き込んでいるが順序などは正しく処理されている。

この問題を解決するために、全て遅延評価するのではなく正格評価を挟むことで領域効率を向上する必要がある。

\subsection{並列処理}

Haskell 版 Jungle では、並列実行に問題を抱えている。
並列に動かすことは可能だが、シングルコアで実行した場合と比較して実行結果が遅くなる。
図\ref{fig:read}や図\ref{fig:write}の結果では、Haskell版はシングルコアで実行している。

並列に動かした場合の実験結果を図\ref{fig:para}に示す。

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[width=70mm]{./images/para.pdf}
 \end{center}
 \caption{並列に動かした場合の実験結果}
 \label{fig:para}
\end{figure}

本研究のウェブアプリケーションとは別に、簡単な例題を並列で動かした場合でも実行速度の向上を確認することはできなかった。
並列処理で速度向上をはかることは、今後の課題である。

\section{おわりに}
\subsection{本研究のまとめ}
本研究では、Haskell による非破壊的木構造を用いた CMS の実装を行った。
Haskellは生産性が高く、本システムの実装においても開発期間およびコード行数は非常に短くなった。

木構造データベース Jungle と HTTP サーバ Warp を用いて簡易掲示板システムを開発し、既存のJavaの実装と同程度の性能を達成できた。

\subsection{今後の課題}
書き込みの際に、遅延評価のためにメモリを多く使用する問題がある。
いくつかの式の評価を正格に切り替え、領域効率を向上しなければならない。

また、並列処理を行った際に実行速度が向上するよう再設計を行う必要がある。

現在の Jungle には木構造を永続化する仕組みが備わっていない。
設計を行い、実装する必要がある。

分散環境で Jungle を効率よく利用するために、木構造をマージする仕組みを実装する必要がある。
マージにはお互いの木の情報が必要になる。
どのようにマージすべきなのかは、ユーザが知っていると考えられるが、データベース間で過度の情報をやり取りを行うと負荷が上昇するおそれがある。
どの程度の情報が必要であるのか検討しなければならない。
\nocite{*}

\bibliographystyle{junsrt}
\bibliography{jssst}
\end{document}