Mercurial > hg > Papers > 2013 > toma-jssst
diff Paper/jssst.tex @ 1:c53cb5bc27cd
add description for nondestructive tree structure
author | Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Wed, 17 Jul 2013 11:50:29 +0900 |
parents | 09f44076bd1e |
children | 92fbcd85d3b9 |
line wrap: on
line diff
--- a/Paper/jssst.tex Tue Jul 09 21:20:16 2013 +0900 +++ b/Paper/jssst.tex Wed Jul 17 11:50:29 2013 +0900 @@ -37,13 +37,13 @@ % % ここにタイトル英訳 (英文の場合は和訳) を書く. % -\ejtitle{Design of DataSegment API in Cerium} +\ejtitle{Implementation of the CMS using Nondestructive tree structure with Haskell} % % ここに著者英文表記 (英文の場合は和文表記) および % 所属 (和文および英文) を書く. % 複数著者の所属はまとめてよい. % -\shozoku{Daichi TOMA, Shinij KONO}{琉球大学大学院理工学研究科情報工学専攻並列信頼研}% +\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 とすれば出力される. @@ -60,11 +60,16 @@ % 和文アブストラクト \Jabstract{% ウェブサービスではユーザの増加に対応し、容易に拡張できるスケーラビリティが求められる。 -分散CMSにおいてスケーラビリティを実現するためには、並列にデータへアクセスできる設計が必要となる。 -本研究では、編集元の木構造を破壊することなく編集できる非破壊木構造を用いる。 -非破壊木構造では、排他制御を行わずに変更を行えるためスケーラビリティを確保できる。 +CMSにおいてスケーラビリティを実現するためには、並列にデータへアクセスできる設計が必要となる。 +本研究では、編集元の木構造を破壊することなく編集できる非破壊的木構造を利用する。 +非破壊的木構造では、排他制御を行わずに変更を行えるためスケーラビリティを確保できる。 Haskellによる非破壊木構造を用いたCMSの実装を行う。 また、既存のJavaの実装およびCassandraとの性能の比較を行う。 } +% スケーラビリティが必要 +% 非破壊的木構造でスケーラビリティが確保できる +% Haskellについての説明 +% - Haskellはもともと破壊的代入を許さないので非破壊と相性がいいはず +% 簡易掲示板システムを実装し、既存のJavaとCassandraと性能比較 % % 英文アブストラクト(大会論文には必要なし) @@ -74,17 +79,95 @@ \section{はじめに} -\section{その1} +\section{関数型言語 Haskell} +\subsection{Haskell} +\subsection{Warp} + +\section{コンテンツマネージメントシステムの設計} +本研究では、スケーラビリティのある CMS の実現のために非破壊的木構造\cite{shoshi:2011a}を用いる。 +非破壊的木構造とは、編集元の木構造を破壊することなく新しい木構造を構成することで木構造を編集する方法である。 + +破壊的木構造と異なりロックせずに並列に読むことができるため、自由にコピーを作成することが可能である。 +コピーを複数作成し、アクセスを分散させることで性能を維持することができると考えられる。 + +通常の破壊的木構造との違いを説明する。 + +\subsection{破壊的木構造} +破壊的木構造は、木構造を編集する際に木構造を置き換えることにより編集を実現する。 +図\ref{fig:destructive_tree_modification}では, ノード6をノードAへ書き換える処理を行なっている. -\section{その2} +\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})。 -\section{その3} +\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 へ書き換える処理を行なっている。 -\section{その4} +\begin{figure}[!htbp] + \begin{center} + \includegraphics[width=70mm]{./images/nondestructive_tree_modification.pdf} + \end{center} + \caption{木構造の非破壊的編集} + \label{fig:nondestructive_tree_modification} +\end{figure} -\section{まとめ} +非破壊的木構造の基本的な戦略は、変更したいノードへのルートノードからのパスを全てコピーする。 +そして、パス上に存在しない (編集に関係のない) ノードはコピー元の木構造と共有することである。 + +編集は以下の手順で行われる。 + +\begin{enumerate} +\item{変更したいノードまでのパスを求める。} +\item{変更したいノードをコピーし、コピーしたノードの内容を変更する。} +\item{求めたパス上に存在するノードをルートノードに向かって、コピーする。 コピーしたノードに一つ前にコピーしたノードを子供として追加する。} +\item{影響のないノードをコピー元の木構造と共有する。} +\end{enumerate} -\nocite{fix200609} +この編集方法で破壊的木構造の場合と同様に、ある時点の木構造を参照する閲覧者と編集する編集者を考える。 +閲覧者が木構造を参照している中、編集者が非破壊的な編集を行う。 +しかし、破壊的な方法とは異なり、元の木構造は破壊されることはないため編集後も整合性は崩れることはない(図\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} + +\section{木構造データベース Jungle を用いた CMS の検証} + +\section{おわりに} + +\nocite{*} \bibliographystyle{junsrt} -\bibliography{reference} +\bibliography{jssst} \end{document}