Mercurial > hg > Papers > 2013 > toma-jssst
view Paper/jssst.tex @ 2:92fbcd85d3b9
add iintroduction
author | Daichi TOMA <toma@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Wed, 17 Jul 2013 16:42:56 +0900 |
parents | c53cb5bc27cd |
children | 2a4370ed68bc |
line wrap: on
line source
% 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} % ユーザが定義したマクロなどはここに置く.ただし学会誌のスタイルの % 再定義は原則として避けること. \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 を用いる。また、既存のJavaの実装およびCassandraとの性能の比較を行う。 } % % 英文アブストラクト(大会論文には必要なし) % \Eabstract{} % \maketitle \section{はじめに} ブロードバンド環境やモバイル端末の普及により、ウェブサービスの利用者数は急激に伸びている。 リクエスト数の増加を予想することは困難であり、負荷が増大した場合に容易に拡張できるスケーラビリティが求められる。 ここでいうスケーラビリティとは、利用者や負荷の増大に対し、単なるリソースの追加のみでサービスの質を維持することができる性質のことである。 コンテンツマネージメントシステムにおいてスケーラビリティを実現するためには、並列にデータへアクセスできる設計が必要となる。 本研究では、編集元の木構造を破壊することなく編集できる非破壊的木構造を利用する。 非破壊的木構造では、排他制御を行わずに変更を行えるためスケーラビリティを確保できる。 コンテンツマネージメントシステムの実装には、プログラミング言語 Haskell を用いる。 Haskell は 純粋関数型プログラミング言語である。 純粋であるため、非破壊な変数代入は許されていない。 簡易掲示板システムを開発し、既存のJavaの実装およびCassandraとの性能の比較を行った。 \section{Haskell} \subsection{Haskell} \subsection{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} \section{木構造データベース Jungle を用いた CMS の検証} \section{おわりに} \nocite{*} \bibliographystyle{junsrt} \bibliography{jssst} \end{document}