\documentclass{ipsjpapers}
\usepackage[dvipdfm]{graphicx}
\usepackage{mediabb}
\usepackage{url}

%\input{dummy.tex} %% Font 

% 巻数，号数などの設定
\setcounter{volume}{51}
\setcounter{number}{10}
\setcounter{volpageoffset}{1234}
\received{22}{7}{17}
\accepted{22}{9}{17}

%\checklines	% 行送りを確認する時に使用
\begin{document}%{
% 和文表題
\title{Cassandraを使ったスケーラビリティのあるCMSの設計}
%%\title[{\protect\LaTeX} による論文作成のガイド]%{{\protect\LATEX} による論文作成のガイド（第7.1版）}
% 英文表題
\etitle{Design of Scalable CMS using Cassandra}

% 所属ラベルの定義
\affilabel{1}{琉球大学理工学研究科情報工学専攻 \\Interdisciplinary Infomation Engineering, Graduate School of Engineering and Science, University of the Ryukyus.}
\affilabel{2}{琉球大学工学部情報工学科\\Infomation Engineering, University of the Ryukyus.}
\affilabel{3}{琉球大学工学部情報工学科\\Infomation Engineering, University of the Ryukyus.}

% 和文著者名
\author{
  玉城 将士\affiref{1}\and
  谷成 雄\affiref{2}\and
  河野 真治\affiref{3}
}
	
% 英文著者名
\eauthor{
  Shoshi TAMAKI\affiref{1}\and
  Yu TANINARI\affiref{2}\and
  Shinji KONO\affiref{3}
}

% 和文概要
\begin{abstract}
本研究では，スケーラビリティのあるCMSを開発するために，100台のPCクラスタを使いCassandra
のスケーラビリティの検証を行った．その結果Cassandraの特徴やスケールする条件の検証，スケ
ーラビリティの検証環境を構築することが出来た．\\
今回は，その検証結果を元にスケーラビリティを確保する方法を検討した．その方法に則りCMSを設計し，データ構造として用いる非破壊的木
構造の実装を行った．

\end{abstract}
\begin{eabstract}
To develop scalable CMS , We built scalability verification environment with 100 PC Clusters to
verify scalabilty of Cassandra. As a result , We confirm a scalability verification method , 
feature and scale condition in Cassandra. \\
In this time , We considered how to secure scalabilty confroming to the verification.
According as the method , We designed CMS and implemented Monotonic Tree-Modification for the CMS's data structure

% 英文概要
\end{eabstract}


% 表題などの出力
\maketitle

%}{

% 本文はここから始まる
\section{研究の目的}
　Cassandraは複数のサーバーで動作を想定した分散データベースである．
前回は，実際に分散させることによって高価なサーバーを超えることが出来る性能を出すことが出来るのか，
また，どの様にCassandra上で動くソフトウェアを開発することによって性能を発揮することが出来るのかを，90台のPCクラスタ上でベンチマークを取り検証した．
結果として，Cassandraの特徴やスケールする条件の検証，スケーラビリティの検証環境を構築することが出来た．\\
　本研究では，前回構築したスケーラビリティの検証環境とCassandraの検証結果を用いて，多段キャッシュと非破壊的木構造をデータ構造に用いたCMSの設計・開発を行った．\\

\section{Cassandra}
Cassandraは, FaceBookが自社のために開発した分散Key-Valueストアデータベースであり，Dynamo\cite{DYNAMO}とBigTable\cite{BIGTABLE}を合わせた特徴を持っている. 2008年にオープンソースとして公開され, 2009年にApache Incubatorのプロジェクトとなった.
2010年にはApacheのトップレベルプロジェクトとなり, 現在でも頻繁にバージョンアップが行われている. \\

\subsection{ConsistencyLevel}
Cassandraには, ConsistencyLevelが用意されている. これは, 整合性と応答速度どちらを取るか選ぶためのパラメータであり, リクエストごとに設定することが出来る. \\
また, ReadとWriteでConsistencyLevelの意味は異なる. 
このConsistencyLevelを適用するノードの台数をReplicationFactorといい, Cassandraの設定ファイル，またはクライアントより設定することが出来る. \\

\subsection{SEDA}
SEDA(Staged Event-Driven Architecture)は, Cassandraで使用されているアーキテクチャである\cite{SEDA1}\cite{SEDA2}. 処理を複数のステージに分解しタスクキューとスレッドプールを用意し処理を行う. 処理の様子を図\ref{fig:SEDA}に示す. \\
タスクが各ステージのタスクキューに入ると, スレッドプールにどれかのスレッドがタスクキューの中からタスクを取り出し処理を行う. 処理が終わるとそのタスクを次のステージのタスクキューに入れる.同様にして次のステージのスレッドプールがタスクキューからタスクを受け取り処理を行う．\\
このアーキテクチャは数多くのスレッドを生成するためマルチコアなPCと多数のタスクがある状況で性能を発揮することができる. \\
実際，Cassandraには20以上のスレッドが動作している．しかし, あまりにもスレッドプールやタスクが多すぎると, コンテキストに切り替えに時間がかかり性能は低下する. \\

\begin{figure}[!htbp]
\begin{center}
	\includegraphics[scale=1.1]{fig/SEDA.pdf}
\end{center}
\caption{SEDA}
\label{fig:SEDA}
\end{figure}

\subsection{PCクラスタを用いたCassandraの検証結果}
前回の研究\cite{SHOSHI1}で，PCクラスタを用いたCassandraの検証で行ったMySQLとCassandraの比較から得られた特徴について簡単にまとめる．\\
クラスタ管理ツールのTorqueを使用し, 使用するノード数を指定してクラスタにジョブを投げてPHPスクリプトを実行させる. このPHPスクリプトは対象のサーバーにリクエストを10000回送信するスクリプトである．実験の概要図を図\ref{fig:benchmark}に示す．\\

\begin{figure}[!htbp]
\begin{center}
	\includegraphics[scale=0.4]{./fig/benchmark.pdf}
\end{center}
\caption{PCクラスタを用いたCassandraの検証環境}
\label{fig:benchmark}
\end{figure}

この実験では，徐々に負荷をかけるクラスタの台数を増加させ，並列度を上げていく．クラスタすべてが処理を完了するまでの平均をグラフにプロットし，比較した．\\
\subsubsection{2Coreを搭載したコア数の少ないサーバーを用いた検証}
ReadはCassandra/MySQLともに，似たような性能低下の推移をしていたがCassandraの方が遅い. しかし, WriteはCassandraの方が断然速く動作している. この実験では, Cassandraの動作を基準に考えたため書き込みのコマンドにREPLACEを使用した. REPLACEは置き換えるようなコマンドである. \\
そのため, INSERTに比べて多少遅くなる.  SEDAは複数のスレッドで動作しているためコア数が少ないサーバーでは性能が出にくいことがわかる. \\
\subsubsection{4Core8Threadsを搭載したコア数の多いサーバーを用いた検証}
Read/Write共にMySQLの性能を超えることに成功した. Readにおいてはコア数が少ない場合に超えることが出来なかったが, 並列度が70度付近でMySQLを上回る性能がでていた.
Cassandraの平均時間は並列度が増加しても, MySQLよりは平均時間の上昇は少ない. これは, SEDAの特徴である多くのタスクを並列に実行すると性能を発揮することを確認することが出来た. \\
また, SEDAはマルチスレッド前提であるため, コア数が少ないサーバーでは性能が出ず, コア数の多いサーバーで性能が発揮できるということが分かる．\\
\subsubsection{クラスタ化したCassandraを用いた検証}
Read/Writeともに, 今回の場合は分散を行わなかったほうが性能を引き出せてることが分かった. これは, 実験に使用したデータがRead/Write共に1つだけで, 結局は同じノードにリクエストが転送されている. そのため, リクエストは1台のノードに集中する. よって, 性能が出ないのではないかと考えられる. Cassandraをただ増やすだけでは性能は得ることが出来ず, データも分散させて実験を行わなければならない.\\
\subsubsection{まとめ}
以上の実験より，Cassandraはコア数の多いサーバーかつREAD/WRITEを並列に行い，なおかつ使用するデータ構造も工夫が必要であるということが分かった．

\section{スケーラビリティのあるCMSの設計}
Cassandraの検証で得られた結果に基づき，スケーラビリティのあるCMSの設計を行う．
スケーラビリティがあるということは以下のような特徴がある．
\begin{enumerate}
\item{大きな負荷がかかっても性能が低下しない}
\item{ノードの台数を増やすだけで性能を維持することが出来る}
\end{enumerate}
これらの特徴を実現する為に，２つの方法が挙げられる．
\begin{enumerate}
\item{データのコピーを複数用意する方法}\\
　データのコピーを複数用意することにより，データのアクセスが集中することを防ぐ．
\item{データの更新通知を行わずポーリングを行う方法}\\
　複数コピーされたデータを同期するためには更新を通知する必要があるが，実際には全ての更新結果をコピー先が把握する必要はなく，コピー先が必要になったときのみ同期を行えば良い．
\end{enumerate}
この２つの方法に則り設計を行った．\\

\subsection{提案するシステムのアーキテクチャ}
提案するシステムのアーキテクチャを図\ref{fig:arch}に示す．
\begin{figure}[!htbp]
\begin{center}
	\includegraphics[scale=0.3]{./fig/arch.pdf}
\end{center}
\caption{提案するシステムの概要}
\label{fig:arch}
\end{figure}
\\
　Cassandraをバックエンドにその上にCMSのAPIを提供するサーバーを構築し，WebサーバーがAPIサーバーを呼び出す形をとる．
こうすることで，APIサーバー自体のスケーラビリティをbotなどを用いて計測することが出来るためである．また，クライアントを
Webと限定せず，デスクトップクライアントなど多様なクライアントに対応することが出来る．\\
　提案するシステムでは各ステージ(Cassandra/APIサーバー/Webサーバー)で方法１に則りキャッシュを用意し，アクセスが集中するのを防ぐ．
また，方法２に則り，各ステージのキャッシュは必要なとき自分より上のステージよりポーリングし更新の有無を確認する．\\
この方法を用いることでスケーラビリティのあるCMSが構築できるのではないかと考えられる．\\


\subsection{スレッドセーフな木構造の開発}
CMSのデータ構造としは，木構造を採用することが出来る．しかし，スケーラビリティのあるシステムで使用するデータ構造はスケールする必要があるため，
スケールする木構造を開発する必要がある．そこで，スレッドセーフな木構造である非破壊的木構造について説明する．\\

\subsubsection{破壊的木構造}
一般的に使用されている木構造はメモリ上の木構造を書き換えて編集する破壊的木構造である．この木構造は編集する際に木にロックを掛ける必要があり，
編集時には木を走査しようとしているスレッドは書き換えの終了を待つ必要，閲覧者がいる場合は木の操作を終了するのを待つ必要があり，スケールしないと考えられる．\\

\begin{figure}[!htbp]
\begin{center}
	\includegraphics[scale=0.3]{./fig/desttree.pdf}
\end{center}
\caption{破壊的木構造}
\label{fig:destree}
\end{figure}

\newpage

\subsubsection{非破壊的木構造}
今回設計したCMSではデータ構造として非破壊的木構造を用いる．非破壊的木構造とは，編集時にルートノードから編集する対象となるノードまでのパスをコピーし
，変更のないノードは古い木構造と共有する．そしてコピーしたルートノードを編集された木とする．
こうすることで，編集前の木構造は破壊されず，木構造を走査していながら編集することが可能になる．\\

\begin{figure}[!htbp]
\begin{center}
	\includegraphics[scale=0.3]{./fig/monotree.pdf}
\end{center}
\caption{非破壊的木構造}
\label{fig:destree}
\end{figure}

\section{実装}
本研究では，実装にJavaを使用した．以下に実装した非破壊的木構造について説明する．\\
\subsection{オンメモリな非破壊的木構造の実装}
分散リポジトリの考え方を参考にし，非破壊的木構造を実装する上で以下のようなクラスを考えた．
\begin{itemize}
\item{Node : データを保持するクラス}
\item{NodeID : Nodeを識別するID，UUID+Version番号で構成される．}
\item{Forest : すべてのNodeを含んだマップ}
\item{Tree : あるNodeをルートとする破壊的な木}
\item{TreeEditor : 木構造を非破壊的に編集するエディタ}
\end{itemize}
それぞれのクラスの役割に付いて説明する．\\

\subsubsection{Node/NodeID}
Nodeはデータを保持するクラスである．NodeのインスタンスはユニークなNodeIDを持ちUUIDとVersion番号で構成されている．
NodeID.UUIDが一致するNode同士は木構造上同じ位置に存在するNodeであり，木の特定のNodeを編集する際には木を捜査し同一のUUIDを持つNodeを検索するために使用される．\\

\begin{figure}[!htbp]
\begin{center}
	\includegraphics[scale=0.3]{./fig/node_nodeid.pdf}
\end{center}
\caption{NodeとNodeIDの関係}
\label{fig:node_nodeid}
\end{figure}

\subsubsection{Forest}
Forestは全Nodeのマップで管理しており，NodeIDをkeyとしてNodeを返す．また，NodeIDのUUIDをkeyとして同じUUIDを持つNodeの中で最新のNodeを返す．
CMSのコンテンツ全体のTreeとNodeの作成，削除，取得はすべてこのクラスが管理している．\\
あるデータ構造を用いて非破壊的木構造を実装する場合，このForestが中心となる．よって，他のクラスはある程度使い回すことができ，基本的にForestの実装だけを行えば良い．\\

\subsubsection{Tree}
あるNodeをルートとする木構造，Forestには全体を表すTreeを持っているが，それとは別に任意のNodeをTreeとすることが出来る．こうすることで全体の木を編集しなくても，部分的に木を編集することが出来るようになる．\\

\subsubsection{TreeEditor}
TreeEditorはTreeをメンバーとして保持し，木構造を非破壊的に編集する．メソッドにcommit/check/updateを持ち，１回または複数回の編集が完了すると自身のルートをTreeに反映する．\\
もし，メンバーのTreeがすでに他のTreeEditorにより編集されていた場合commitは失敗しmerge処理を行う．

\begin{figure}[!htbp]
\begin{center}
	\includegraphics[scale=0.3]{./fig/forest.pdf}
\end{center}
\caption{実装した非破壊的木構造の概要}
\label{fig:forest.pdf}
\end{figure}

\subsection{Cassandraを使った非破壊的木構造の実装}
非破壊的木構造を実装するため，Cassandraに以下のようなKeySpaceを定義した．\\

\begin{figure}[!htbp]
\begin{center}
	\includegraphics[scale=0.3]{./fig/keyspace.pdf}
\end{center}
\caption{KeySpaceの定義}
\label{fig:defKS}
\end{figure}

Node ColumnFamilyはNodeIDをkeyとしてColumnはNodeの保持するデータを格納する．NodeID ColumnFamilyはNodeのUUIDをkeyとしてNodeの最新版のVersionを格納する．Partitionerにはkeyの分散を考慮してRandomPartitionerを使用している．\\

\subsubsection{CassandraForest}
CassandraForestは初めにCassandraから最新版のノードの情報をすべて取得しメモリ上にキャッシュする．この処理のリクエスト回数は木構造の大きさによらず，iNodeID ColumnFamilyからの最新版NodeIDの全取得，Node ColumnFamilyからの最新版Nodeの取得の２回である．\\
オンメモリ上の実装と同様に，作成，削除，取得を管理する．そのため，内部にはCassandraClientを保持している．Cassandraの検証より並列に負荷をかけることで，性能を発揮するという結果が得られた．よって，Javaのスレッドプールフレームワーク(java.concurrentパッケージ)を用いてコネクションプールを用意し，Cassandraへの操作を並列に行う．\\
　Cassandraへのリクエストに対する返り値はすべてFutureでやり取りされ，リクエストの結果は必要となったときにのみ同期され展開される．この様に実装することにより高い並列度が期待できる．\\

\begin{figure}[!htbp]
\begin{center}
	\includegraphics[scale=0.4]{./fig/concurrent_client.pdf}
\end{center}
\caption{ConnectionPool}
\label{ref:ConPool}
\end{figure}

\subsubsection{CassandraTreeEditor}
TreeEditorでは，編集する際にNodeをそれぞれコピーするため，Cassandraへのリクエストが複数発生する．しかし，実際にはコピーが終わったあとにまとめてコピーを行えば良い．Cassandraには\verb+batch_mutate+という機能があり，複数のColumnFamilyと複数のColumnに１度で変更を加えることができる．\\
CassandraTreeEditorでは，NodeID ColumnFamilyとNode ColumnFamilyへの操作をまとめてリクエストするため，Cassandraへ発生するリクエストの回数は非破壊的に編集した場合でも１回である．

\section{まとめと今後の課題}
本研究では，スケーラビリティのあるCMSを開発するため，前回行ったCassandraの検証と検証環境を構築を元に設計を行った．
スケーラビリティのあるCMSの特徴として，「負荷がかかっても性能が低下しない・ノードの台数を増やすだけで性能を維持できる」と考え，
実現方法として「データの複製を用意する・更新通知にはポーリングを利用する」を提案した．\\
この２つの方法を実現したものとして非破壊的木構造に分散リポジトリの要素を組み合わせたデータ構造を開発出来た．\\
今後は，開発したデータ構造の性能評価と改良を行う．

\section{謝辞}
この研究はSymphony社との共同研究「分散化されたテキスト管理システムに関する研究」によって行われました．
Symphony社の社員を始め，指導教官である河野真治先生には様々な助言や協力をして頂きました．ありがとうございました．

\bibliographystyle{ipsjunsrt}
\begin{thebibliography}{99}
\bibitem{SHOSHI1}
{Shoshi TAMAKI,Shinji KONO}:Cassandraを用いたCMSのPCクラスタを用いたスケーラビリティの検証,ソフトウェア科学会 (2010)
\bibitem{DYNAMO} {Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati , Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall , Werner Vogels}:
Dynamo: Amazon's Highly Avaliable Key-value Store , SOSP (2007)
\bibitem{SEDA1}{Matt Welsh}: The Staged Event-Driven Architecture for Highly-Concurrent Server Applications
\bibitem{SEDA2}{Matt Welsh, David Culler, Eric Brewer}: SEDA : An Architecture for Well-Conditioned , Scalable Internet Services , SOSP (2001)
\bibitem{BIGTABLE}{Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach
Mike Burrows, Tushar Chandra, Andrew Fikes, Robert E. Gruber}: Bigtable : A Distributed Storege System for Structured Data
\end{thebibliography}

\end{document}