Binary file Paper/images/delay_memory.pdf has changed

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/Paper/images/delay_memory.xbb	Fri Jul 19 19:46:44 2013 +0900
@@ -0,0 +1,8 @@
+%%Title: ./delay_memory.pdf
+%%Creator: extractbb 20120420
+%%BoundingBox: 0 0 792 612
+%%HiResBoundingBox: 0.000000 0.000000 792.000000 612.000000
+%%PDFVersion: 1.3
+%%Pages: 1
+%%CreationDate: Fri Jul 19 19:43:04 2013
+

--- a/Paper/jssst.bib	Fri Jul 19 18:35:51 2013 +0900
+++ b/Paper/jssst.bib	Fri Jul 19 19:46:44 2013 +0900
@@ -54,7 +54,7 @@
 }
 
 @misc{deos,
-  title = {DEOS 技術報告書},
+  title = {DEOS},
   howpublished = "\url{http://www.dependable-os.net/osddeos/data.html}",
   note = "[Online; accessed 19-July-2013]"
 }

--- a/Paper/jssst.tex	Fri Jul 19 18:35:51 2013 +0900
+++ b/Paper/jssst.tex	Fri Jul 19 19:46:44 2013 +0900
@@ -91,23 +91,18 @@
 ブロードバンド環境やモバイル端末の普及により、ウェブサービスの利用者数は急激に伸びている。
 リクエスト数の増加を予想することは困難であり、負荷が増大した場合に容易に拡張できるスケーラビリティが求められる。
 ここでいうスケーラビリティとは、利用者や負荷の増大に対し、単なるリソースの追加のみでサービスの質を維持することができる性質のことである。
-マルチコア環境におけるコンテンツマネージメントシステムにおいてスケーラビリティを実現するためには、並列にデータへアクセスできる設計が必要となる。
-並列にデータにアクセスできない場合、排他制御が必要となり、パフォーマンスが低下する。
-本研究では、編集元の木構造を破壊することなく編集できる非破壊的木構造を利用する。
+コンテンツマネージメントシステムにおいてスケーラビリティを実現するためには、並列にデータへアクセスできる設計が必要となる。
+
+本研究では、並列にデータへアクセスする手法として、非破壊的木構造を利用する。
 非破壊的木構造では、少ない排他制御で変更を行えるためスケーラビリティを確保できる。 
 
-コンテンツマネージメントシステムの実装には、プログラミング言語 Haskell を用いた。
-Haskell は 純粋関数型プログラミング言語である。
-純粋であるため、一度定義した変数の書き換えは許されていない。
-また、生産性が高いことも特徴で、本システムの実装においても開発期間およびコード行数は非常に短くなった。
+非破壊的木構造を用いたデータベースとして、本研究室による Java による実装が既に存在する。
+しかしながら、Functional Java を多用しており、それならば Pure Functional な Haskell のほうが相性がいいのではないかと考え、本研究では Haskell による実装を行った。
 
-Haskellで書かれたHTTPサーバ Warp を用いて簡易掲示板システムを開発し、既存のJavaの実装と同程度の性能を達成できた。
+Haskell による実装では、Java と比較して開発期間およびコード行数が非常に短くなるといったメリットがあった。
 
-\section{DEOSプロジェクト}
-2006 年に独立行政法人科学技術機構の CREST プログラムの 1 つとして始まったプロジェクトである。
-DEOS プロジェクトは、変化しつづける目的や環境の中でシステムを適切に対応させ、継続的にユーザが求めるサービスを提供することができるシステムの構築法を開発することを目標としている。
-DEOS プロセスにおいて、D-ADD (DEOS Agreement Description Database)\cite{deos}と呼ばれるデータベースがある。
-本論文で説明する 木構造データベース Jungle は、D-ADD への応用も目指して研究を続けている。
+また、性能比較のために Haskell で書かれたHTTPサーバ Warp を用いて簡易掲示板システムを開発し、既存のJavaの実装と同程度の性能を達成できた。
+
 \section{Haskell}
 Haskell は、純粋関数型プログラミング言語である。
 関数型プログラミング言語では、引数に関数を作用させていくことで計算を行う。
@@ -163,45 +158,15 @@
 
 \section{コンテンツマネージメントシステムの設計}
 コンテンツマネージメントシステムのデータ構造としては木構造を用いる。
-我々は、スケーラビリティのある CMS の実現のために非破壊的木構造\cite{shoshi:2011a}を提案する。
+スケーラビリティのある 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 へ書き換える処理を行なっている。
+図\ref{fig:nondestructive_tree_modification}では、ノード 6 をノード A へ書き換える処理を行なっている。
 
 \begin{figure}[!htbp]
  \begin{center}
@@ -223,9 +188,8 @@
 \item{影響のないノードをコピー元の木構造と共有する。}
 \end{enumerate}
 
-この編集方法で破壊的木構造の場合と同様に、ある時点の木構造を参照する閲覧者と編集する編集者を考える。
-閲覧者が木構造を参照している中、編集者が非破壊的な編集を行う。
-しかし、破壊的な方法とは異なり、元の木構造は破壊されることはないため編集後も整合性は崩れることはない(図\ref{fig:nondestructive_tree_modification_in_lace})。
+この編集方法を用いた場合、閲覧者が木構造を参照してる間に、木の変更を行っても問題がない。
+閲覧者は木が変更されたとしても、保持しているルートノードから整合性を崩さずに参照が可能である。
 ロックをせずに並列に読み書きが可能であるため、スケーラブルなシステムに有用であると考えられる。
 元の木構造は破壊されることがないため、自由にコピーを作成しても構わない。したがってアクセスの負荷の分散も可能である。
 
@@ -247,11 +211,11 @@
 本研究では、Haskell を用いて実装を行った。
 コンテンツマネージメントシステムに組み込んで利用しているが、他のシステムに組み込むことも可能である。
 
-\subsection{利用方法}
+\subsection{データベースオブジェクトと木の作成}
 \paragraph*{木の作成}
-はじめに、データベースオブジェクトと木の作成方法について述べる。
 Jungle は複数の木を保持することができる。
-木には名前がついており、名前を利用して作成・編集・削除を行うことができる。
+木には名前がついており、名前を利用して判別を行う。
+また、作成・編集・削除を行うことができる。
 
 \begin{lstlisting}[label=new_jung, caption=データベースオブジェクトと木の作成]
 jungle = createJungle
@@ -285,16 +249,12 @@
 new_jungle = updateTree jungle new_tree2
 \end{lstlisting}
 
-毎回、新しい変数に代入することで記述が少々煩雑になりやすい。
-State モナドを用いて記述を簡易にしたものもあるが、利用者にどのようなAPIを提供するかは検討中である。
-
-\subsection{実装の詳細}
-\paragraph*{木の取り扱い}
+\subsection{木の取り扱い}
 Jungle の 木 の取り扱いには、Haskell の Map を用いている。
 Mapは、平衡木を使った Haskell の連想リストである。
 連想リストを用いて、名前と木を結びつけている。
 
-\paragraph*{データ構造}
+\subsection{データ構造}
 木のデータ構造は、データ型で定義されている。
 
 \begin{lstlisting}[label=node, caption=データ構造]
@@ -308,15 +268,14 @@
 各ノードは、Childrenとしてノードを複数持つことができる。
 ChildrenおよびAttributesも、Map を用いて定義されている。
 
-\paragraph*{ルートノードの取り扱い}
+\subsection{ルートノードの取り扱い}
 非破壊的木構造であっても、どのノードが最新のルートノードなのかという情報が必要である。
 スレッドセーフに取り扱う必要があるため、Haskell のソフトウェア・トランザクショナル・メモリを用いて管理している。
 
-\subsection{開発期間}
-関数型プログラミングでは、コードは短く簡潔になり、生産性が向上する。
-
+\subsection{開発期間の短縮}
 Java 版の Jungle の実装と比較すると、コード行数は約3000行から約150行へ短くなった。
 また開発期間はJava版の実装で、3 ヶ月程度かかったが、Haskell 版の実装は 2 週間程度であった。
+これにより、関数型プログラミングではコードは短くなり、生産性が向上することが分かった。
 
 \section{木構造データベース Jungle を用いた CMS の検証}
 木構造データベース Jungle 及び Warp を用いて簡単な掲示板ウェブアプリケーションを作成した。
@@ -409,6 +368,20 @@
 Haskell は遅延評価を行うが、書き込みの際に問題が生じる。
 何かしらの結果を表示するまで、簡約可能な式の状態で積まれたままとなる。
 その際メモリを消費し、効率のよい領域に入りきらないサイズになると非常に実行結果が遅くなる。
+
+図 \ref{fig:delay} では、メモリ消費量を表している。
+実行中メモリ消費量は増えていくが、木の表示を行う22秒前後まで簡約化は行われない。
+表示を行った際に簡約化され、メモリ消費量が急激に下がっている。
+
+\begin{figure}[!htbp]
+ \begin{center}
+  \includegraphics[width=80mm]{./images/delay_memory.pdf}
+ \end{center}
+ \caption{遅延評価のメモリ消費}
+ \label{fig:delay_memory}
+\end{figure}
+
+
 図\ref{fig:write}の結果では、オプションで推奨されるヒープ領域のサイズを変更してある。
 推奨されるヒープ領域のサイズを変更しない場合の実験結果を図\ref{fig:delay}に示す。
 
@@ -426,7 +399,7 @@
 読み込みの際には、数万回以上の書き込みを処理するため数秒から数十秒かかる。
 書き込みは、インクリメントしている値を書き込んでいるが順序などは正しく処理できている。
 
-この問題を解決するために、全て遅延評価するのではなく適切な箇所で正格評価を行うことで領域効率を改善する必要がある。
+この問題を解決するために、全て遅延評価するのではなく適切な箇所で即時評価を行うことで領域効率を改善する必要がある。
 
 \subsection{並列処理}
 
@@ -466,6 +439,13 @@
 マージにはお互いの木の情報が必要になる。
 どのようにマージすべきなのかは、ユーザが知っていると考えられるが、データベース間で過度の情報をやり取りを行うと負荷が上昇するおそれがある。
 どの程度の情報が必要であるのか検討しなければならない。
+
+\subsection{DEOSプロジェクト}
+2006 年に独立行政法人科学技術機構の CREST プログラムの 1 つとして始まったプロジェクトである。
+DEOS プロジェクトは、変化しつづける目的や環境の中でシステムを適切に対応させ、継続的にユーザが求めるサービスを提供することができるシステムの構築法を開発することを目標としている。
+DEOS プロセスにおいて、D-ADD (DEOS Agreement Description Database)\cite{deos}と呼ばれるデータベースがある。
+本論文で説明する 木構造データベース Jungle は、D-ADD への応用を目指しており、DEOS プロジェクトの一環として行なっている。
+
 \nocite{*}
 
 \bibliographystyle{junsrt}