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

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

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

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

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

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

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

\begin{document}

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

% 著者
% 和文論文の場合，姓と名の間には半角スペースを入れ，
% 複数の著者の間は全角スペースで区切る
%
\author{當眞 大千 \and 河野 真治
%
% ここにタイトル英訳 (英文の場合は和訳) を書く．
%
\ejtitle{Implementation of the CMS using Nondestructive tree structure with 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の実装およびCassandraとの性能の比較を行う。
}

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

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

コンテンツマネージメントシステムの実装には、プログラミング言語 Haskell を用いる。
Haskell は 純粋関数型プログラミング言語である。
純粋であるため、非破壊な変数代入は許されていない。

Haskellで書かれたHTTPサーバ Warp を用いて簡易掲示板システムを開発し、既存のJavaの実装およびCassandraとの性能の比較を行う。

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

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

\subsection{Warp を用いたウェブサービスの構築}
Warp を用いてウェブサービスを構築する方法について考察する。
% Source Codeは実行可能な状態でsrcに置いてある 
% firstline, lastlineで、どの範囲を表示するか指定できる
\lstinputlisting[label=src1, caption=Warpを用いたウェブサービスの例, firstline=9]{src/warp.hs}

ソースコード \ref{src1}は、URLによって出力する結果を変更するウェブサービスである。
/hello/worldへアクセスがあった場合は、インクリメントされる counter が表示される。

HTTP サーバを起動するには、Warp の run 関数を利用する。
run 関数は、利用する Port 番号 と、application というリクエストを受けて何かしらのレスポンスを返す関数の2つを引数として受け取る。

関数型言語では、関数を第一級オブジェクトとして扱える。
また、今回は Haskell のカリー化された関数の特性を利用し、main 内で作成した IORef 型の counter を部分適用させている。

IORef を用いることで、Haskell で更新可能な変数を扱うことができる。
参照透過性を失うようにみえるが、Haskell は IO モナドを利用することで純粋性を保っている。
IORef 自体が入出力を行うわけではなく、単なる入出力操作の指示にすぎない。
IO モナドとして糊付けされた単一のアクションに main という名前を付けて実行することで処理系が入出力処理を行う。

application の実装では、routes という関数を独自に定義して、URL によって出力を変更している。
application に渡されるリクエストはデータ型で様々な情報が含まれている。
その中のひとつに pathInfo という、URL から hostname/port と、クエリを取り除いたリストがある。
この情報を routes という関数に渡すことで、routeSetting というリストから一致する URL がないか調べる。
routeSetting は、URL のリストとレスポンスを返す関数のタプルのリストである。

レスポンスを返す関数は、いくつか定義されている。
その中で利用されている responseLBS は文字列からレスポンスを構築するためのコンストラクタである。

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{コンテンツマネージメントシステムの実装}
木構造データベースについて述べる。
\subsection{木構造データベース Jungle}
Haskellによって実装された木構造データベースである。
\subsubsection{利用方法}
\subsubsection{実装の詳細}

\section{木構造データベース Jungle を用いた CMS の検証}
複数のクラスタを利用して、サーバに対して並列にアクセスを行う。
クラスタの実行平均時間を計測

簡易掲示板システムについて

実験環境

読み込みの実験結果

書き込みの実験結果

遅延評価の問題

並列の問題
\section{おわりに}
実装を行った

検証した

\subsection{今後の課題}
データ永続化

分散環境でMergeを行う仕組みの実装

遅延評価

並列で速度
\nocite{*}
\bibliographystyle{junsrt}
\bibliography{jssst}
\end{document}