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

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

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

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

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

%pdf ここに, 使用するパッケージを列挙する. 
\usepackage{mediabb}
\usepackage{graphicx}
%\usepackage[dvips]{graphics}

% ユーザが定義したマクロなどはここに置く. ただし学会誌のスタイルの
% 再定義は原則として避けること. 

\begin{document}
% 論文のタイトル
\title{Cassandraを使ったCMSのPCクラスタを使ったスケーラビリティの検証}

% 著者
% 和文論文の場合, 姓と名の間には半角スペースを入れ, 
% 複数の著者の間は全角スペースで区切る
%
\author{玉城 将士 \and 河野 真治
\shozoku{Shoshi TAMAKI, Shinji KONO}{琉球大学工学部情報工学学科}
{Dept. \ of Information Engineering, Ryukyu University}
}


%
% 和文アブストラクト
\Jabstract{
数ある分散Key-Valueストアの中でもCassandraが注目を集めている. 
CassandraはConsitency levelの変更が可能であり、スケーラビリテイを
高めるための使い方には工夫が必要である. 
本研究では, Cassandra上で動作するCMSを実装し学科のクラスタ上で動作させ
る. 
特に, CoreDuo などの安価だが非力なマシンの振舞を調べることを行なった. 
そしてその環境上でスケーラビリティを確認する実験手法に関して考察する. 
}
%
% 英文アブストラクト(大会論文には必要なし)
% \Eabstract{}

\maketitle

%

\section{はじめに}
インターネットやスマートフォンなどの普及に伴い，インターネット上のサービスを使用するユーザーが急速に増え続けている．サービスを利用するユーザーが増えると，いままでのシステムでは膨大なアクセスに対応できなくなり，サービスの品質を維持することができなくなる．
%品質を維持するためには，使用するサーバー性能の向上を測ればよい．しかし，性能の良いサーバーを揃えるには膨大なコストを必要とし，これをスケールアップと呼ぶ．
そこで，安価なサーバーを複数用意し，連携させることによって性能を向上させる方法があり，これをスケールアウトと呼ぶ．この方法では，従来使用してきたソフトウェアを複数のサーバーに移動するだけではうまく動作しない．
複数のサーバーを強調させるのは難しく，データの整合性や通信速度，負荷分散など様々な考慮をしなければならないためである．
Cassandraは複数のサーバーで動作を想定した分散データベースである．
本研究では，実際に分散させることによって高価なサーバーを超えることが出来る性能を出すことが出来るのか，また，どの様にCassandra上で動くソフトウェアを開発することによって性能を発揮することが出来るのかを，９０台のPCクラスタ上でベンチマークを取り検証した，その結果，コア数の多いサーバー上で高い性能を得ることが出来た．
\section{先行研究}
\subsection{Yahoo! Cloud Serving Benchmark}
数のデータベース（Sherpa,BitTable,Azure）などがあるが, 実際にはどのデータベースを使用すればよいか確かではない. この研究では, 異なるデータベースの性能を比較する共通なフレームワークを開発する．\cite{YCSB}
\section{分散データベース Cassandra}
Cassandraは, FaceBookが自社のために開発した分散Key-Valueストアデータベースであり，DynamoとBigTable\cite{BIGTABLE}を合わせた特徴を持っている. 2008年にオープンソースとして公開され, 2009年にApache Incubatorのプロジェクトとなった.
2010年にはApacheのトップレベルプロジェクトとなり, 現在でも頻繁にバージョンアップが行われている. 
\subsection{ConsictencyLevel}
Cassandraには, ConsistencyLevelが用意されている. これは, 整合性と応答速度どちらを取るか選ぶためのパラメータであり, リクエストごとに設定することが出来る. 
また, ReadとWriteでConsistencyLevelの意味は異なる. 
このConsistencyLevelを適用するノードの台数をReplicationFactorといい, Cassandraの設定ファイルで設定することが出来る. 
{\gt Read}
\begin{enumerate}
\item{ConsistencyLevel::ZERO}\\
サポートされていない. 
\item{ConsistencyLevel::ANY}\\
サポートされていない. 
\item{ConsistencyLevel::ONE}\\
一番最初に返答したノードの値を返すが値が最新のものであるかは保証できない. 整合性の調査は常に非同期で行われており, 再度読み出しを行うときに結果が変わっている可能性がある. 
\item{ConsistencyLevel::QUORUM}\\
すべてのノードにリクエストを送信し, 取得した値のタイムスタンプを比較し, 最も多数のノードが返した値のうちで最新のタイムスタンプを持つ値を返す. 
\item{ConsistencyLevel::ALL}\\
すべてのノードにリクエストを送信し, もっともタイムスタンプの新しいノードの値を返す. 
\end{enumerate}
{\gt Write}
\begin{enumerate}
\item{ConsistencyLevel::ZERO}\\
何も保証しない, 書き込みは非同期的に行われる. 
\item{ConsistencyLevel::ANY}\\
別のどこか他のノードに書き込まれることを保証する. 
\item{ConsistencyLevel::ONE}\\
最低1つのノードのログとメモリテーブルに書き込まれていることを保証する. 
\item{ConsistencyLevel::QUORUM}\\
(ReplicationFactor/2) + 1のノードに書き込むことに書き込みを終えてからクライアントにレスポンスを返す. 
\item{ConsistencyLevel::ALL}\\
ReplicationFactorのノード数に書き込みを終えてからレスポンスを返す. 
\end{enumerate}
\subsection{コンシステント・ハッシュ}
Cassandraは複数のノードにデータを分散して格納する. その為に使用されているのがコンシステント・ハッシュである. 普通, n台で構成されたノードにデータを分散する場合, hash(key) mod nで分散させる. この場合だと, ノードが追加・削除された場合すべてのデータの位置を再計算する必要があり面倒である. 

そこで, 図\ref{fig:chash}のようなものを考える. 図\ref{fig:chash}はハッシュ関数が取りうる値を範囲としたリングである. このリング上に構成するノードを配置していく. この図の場合, アルファベットがノードで数字がデータ, 矢印が担当するノードである. 
次に, ハッシュ関数により計算された値をリングの上に配置する. このとき, リングを右回りに周り一番最初にあたったノードがデータを担当するノードとする. 
こうすると, ノードが追加・削除された場合に, 全体を再計算する必要はなく, 担当するノードがいなくなったデータのみを再計算し, 次の担当するノードに移せばよい. 
Cassandraでは, 右回りに回ったとき担当するノード数を複数にする場合, ReplicationFactorで調整することが出来る. 
\begin{figure}[h]
\begin{center}
\includegraphics{./fig/ConsistentHash.pdf}
\end{center}
\caption{コンシステントハッシュ}
\label{fig:chash}
\end{figure}
\subsection{SEDA}
SEDA(Staged Event-Driven Architecture)は, Cassandraで使用されているアーキテクチャである\cite{SEDA1}\cite{SEDA2}. 処理を複数のステージに分解しタスクキューとスレッドプールを用意し処理を行う. 処理の様子を図\ref{fig:seda}に示す. 
タスクが各ステージのタスクキューに入ると, スレッドプールにどれかのスレッドがタスクキューの中からタスクを取り出し処理を行う. 処理が終わるとそのタスクを次のステージのタスクキューに入れる. 
このアーキテクチャはマルチスレッドベースなためマルチコアなPCと多数のタスクがある状況で性能を発揮することができる. しかし, あまりにもスレッドプールやタスクが多すぎると, コンテキストに切り替えに時間がかかり性能は低下する. 
\begin{figure}[h]
\begin{center}
\includegraphics{./fig/SEDA.pdf}
\end{center}
\caption{SEDA}
\label{fig:seda}
\end{figure}
\subsection{Cassandra上でのステージの構成}
Cassandraは主に以下のステージにより構成されており, concurrent::StageManagerを参照すると見つけることが出来る. 
\begin{itemize}
\item{READ STAGE}
\item{MUTATION STAGE}
\item{STREAM STAGE}
\item{GOSSIP STAGE}
\item{RESPONSE STAGE}
\item{AE SERVICE STAGE}
\item{LOADBALANCE STAGE}
\item{MIGRATION STAGE}\\
\end{itemize}
実際にはもっと多数のステージが存在し, この他にもクライアントの接続を待つスレッドプールやMemTableのFlushを行うスレッドプールがあり, 全部で40個程度のスレッドが動作している. 
\subsection{YukiWiki on Cassandra}
今回の検証のため, CMSのであるWikiクローンのYukiWikiをCassandra上で動作するように改造した．YukiWikiは文書の管理にTIEHASHを使用しており，Cassandra用のTIEHASHを作成することで簡単に実装することが出来る．\\
Cassandra上で動作するため，このWikiで複数のサーバー上でデータを共有することが出来るようになった．\\
ソースコードは以下のURLで参照することが出来る．
\section{実験}
本研究では, Cassandraのスケーラビリティの検証の為にベンチマークテストを行う. 実験環境は以下のとおりである. 
\subsection{実験環境}
\begin{enumerate}
\item{クラスタ(クライアント)}
\begin{itemize}
\item{CPU : Core Duo}
\item{Mem : 1GB}
\item{O S : CentOS 5}
\end{itemize}
\item{MacMini}
\begin{itemize}
\item{CPU : Core2 Duo}
\item{Mem : 4GB}
\item{O S : OSX SnowLeopard}
\end{itemize}
\item{Core i7}
\begin{itemize}
\item{CPU : Core i7 950 @3.0GHz}
\item{Mem : 16GB}
\item{O S : CentOS 5}
\end{itemize}
\end{enumerate}
\subsection{実験方法}
\begin{enumerate}
\item{クライアント}
クラスタ管理ツールのTorqueを使用し, 使用するノード数を指定してクラスタにジョブを投げてPHPスクリプトを実行させる. このPHPスクリプトはCassandraとMySQLに10000回リクエストを送信するスクリプトである. 
\item{Cassandra}
Cassandra 0.6.3を使用した. 
\item{MySQL}
MySQL 5.5を使用した. Cassandraと似たデータ構造を持たせるために表\ref{tab:mysql_tbl_def}のような構造でテーブルを作成した. 
\begin{table}[h]
\caption{テーブルの定義}
\label{tab:mysql_tbl_def}
\begin{center}
\begin{tabular}{|c|c|c|} \hline
フィールド名 & データタイプ & 備考 \\ \hline
NAME & VARCHAR(100) & UNIQUE \\ \hline
VALUE & VARCHAR(100) & - \\ \hline
TIMEUUID & LONG & - \\ \hline
\end{tabular}
\end{center}
\end{table}
\end{enumerate}
\newpage
\section{実験結果と考察}
\subsection{単純なベンチマーク}
はじめに, 単純なベンチマークを行った. 単体のクライアントとサーバーを用意し, CassandraとMySQLの実行時間の比較を行った. 結果を表\ref{tab:bench1}に示す. この時のCassandraのConsistencyLevelはONEである. 

結果を見てみると, MySQLよりCassandraのほうが高速に動作していることが分かる. MyySQLはC++で記述されているがCassandraはJavaであるため, 動作が遅い. よって, 単純な使用方法ではCassandraよりMySQLの方が優れていると言える, 普通の方法ではCassandraの性能を引き出すことは出来ない. 
\begin{table}[h]
\caption{単純なベンチマークの結果(Read)}
\begin{center}
\begin{tabular}{|c|c|c|}  \hline
& Cassandra & MySQL \\ \hline
MacMini& 13.72s & 5.94s \\ \hline
Core i7& 12.56s & 3.99s \\ \hline
\end{tabular}
\end{center}
\vspace{5mm}
\caption{単純なベンチマークの結果(Write)}
\begin{center}
\begin{tabular}{|c|c|c|} \hline
& Cassandra & MySQL \\ \hline
MacMini& 11.75s & 5.7s \\ \hline
Core i7& 9.62s & 5.3s \\ \hline
\end{tabular}
\end{center}
\end{table}
\subsection{コア数の少ないサーバー上でのベンチマーク}
次に, クライアントを並列化しての実験を行う. ここでは, コア数の少ないMacMiniを用いる. クライアントの並列化はスクリプトを指定した時間に同時起動するようにして実装した. 
実験結果を図\ref{fig:bench2-R}と図\ref{fig:bench2-W}に示す. 

Readは両方とも, 同じような推移の仕方をしているが, Cassandraの方が遅い. しかし, WriteはCassandraの方が断然速く動作している. この実験では, Cassandraの動作を基準に考えたため書き込みのコマンドにREPLACEを使用した. REPLACEは置き換えるようなコマンドである. そのため, INSERTに比べて多少遅くなる. それがこのグラフに出ているのではないかと考えられる. SEDAは複数のスレッドで動作しているためコア数が少ないサーバーでは性能が出にくいことがわかる. 
\begin{figure}[h]
\begin{center}
	\scalebox{0.33}{\includegraphics{./fig/serv1_read.pdf}}
\end{center}
\caption{MacMini上でのベンチマーク(Read)}
\label{fig:bench2-R}
\end{figure}
\begin{figure}[h]
\begin{center}
	\scalebox{0.33}{\includegraphics{./fig/serv1_write.pdf}}
\end{center}
\caption{MacMini上でのベンチマーク(Write)}
\label{fig:bench2-W}
\end{figure}
\subsection{コア数の多いサーバー上でのベンチマーク}
クライアントを並列化した状態で, コア数の多いCore i7を用いたベンチマークを行う. 実験結果を図\ref{fig:bench3-R}と図\ref{fig:bench3-W}に示す. 

Read/Write共にMySQLの性能を超えることに成功した. Readにおいてはコア数が少ない場合に超えることが出来なかったが, 並列度が70度付近でMySQLを上回る正農がでている.
Cassandraの平均時間は並列度が増加しても, MySQLよりは平均時間の上昇は少ない. これは, SEDAの特徴である, 多くのタスクを並列に実行すると性能を発揮することを確認することが出来た. 
また, SEDAはマルチスレッド前提であるため, コア数が少ないMacMiniでは性能が出ず, コア数の多いCore i7で性能が発揮できるということが分かる．

つまり, Cassandraは負荷が高いときにMySQLを超える性能を出すことが出来る. 負荷がかかっても性能の劣化が少ないことを考えると考えると遅延をあまり考慮しなくても済むのではないだろうか. 
\begin{figure}[h]
\begin{center}
	\scalebox{0.33}{\includegraphics{./fig/serv2_read.pdf}}
\end{center}
\caption{Core i7上でのベンチマーク(Read)}
\label{fig:bench3-R}
\end{figure}
\begin{figure}[h]
\begin{center}
	\scalebox{0.33}{\includegraphics{./fig/serv2_write.pdf}}
\end{center}
\caption{Core i7上でのベンチマーク(Write)}
\label{fig:bench3-W}
\end{figure}
\subsection{複数ノードで構成したCassadraのベンチマーク}
最後に分散しなかったCassandraと複数ノードで構成したCassandraの比較を行う. サーバーはMacMiniを5台使用して行った. 実験結果を図\ref{fig:bench4-R}と図\ref{fig:bench4-W}に示す. 
Read/Writeともに, 今回の場合は分散を行わなかったほうが性能を引き出せてることが分る. これは, 実験に使用したデータがRead/Write共に1つだけで, 結局は同じノードにリクエストが転送されている. そのため, リクエストは1台のノードに集中する. よって, 性能が出ないのではないかと考えられる. Cassandraをただ増やすだけでは性能は得ることが出来ず, データも分散させて実験を行わなければならない.
\begin{figure}[h]
\begin{center}
	\scalebox{0.33}{\includegraphics{./fig/cluster_read.pdf}}
\end{center}
\caption{MacMiniを複数ノードにしたベンチマーク(Read)}
\label{fig:bench4-R}
\end{figure}
\begin{figure}[h]
\begin{center}
	\scalebox{0.33}{\includegraphics{./fig/cluster_write.pdf}}
\end{center}
\caption{MacMiniを複数ノードにしたベンチマーク(Write)}
\label{fig:bench4-W}
\end{figure}
\newpage
\section{まとめ}
Cassandraは従来の使用方法では性能を発揮することが出来ずコア数が多いサーバーでクライアントの並列度が高い場合に性能を発揮する. 
これは，ベンチマークの結果を考察すると，コア数が少ない場合ReadはMySQLより遅いがほぼ同し推移の仕方をする. 
Writeは，コア数が少なくてもクライアントの並列度を高く設定すればMySQLより性能が出る．
コア数が多い場合，Read・Write共に，初めはやはりMySQLの方が動作が早いが，グラフの傾きはMySQLの方が大きくCassandraは緩やかである．
特にCassandraのWhiteの性能は高く, MySQLを大きく上回っている．
また, 単純にCassandraのノード数を増やしても性能は高くならない. これは, データも綺麗に分散させてあげないとデータを読み込む際に一定のノードに集中してしまい，他のノードにアクセスを分散しても結局は保持しているノードに聞きに行かないといけないことになるからである． 
データもある程度分散させなければならないため，汎用的なhash関数では性能が発揮できなく, そのアプリケーション専用の関数が必要だと思われる. 
格納されるデータを決めるのにStrategyというものがあり, それを利用することで実装できると思われる．
\section{今後の課題}
今後は, Strategyを拡張し複数のデータをノードに分散させた環境下でベンチマークを行い, その結果をCassandra単体でのベンチマーク結果と比較したいと考えている.

% 本文で引用しない限り、参考文献には挙げないものなんだよ

\begin{adjustvboxheight} % needed only when Appendix follows
\begin{thebibliography}{99}
\bibitem{YCSB} Benchmarking Cloud Serving Systems with YCSB
\bibitem{SEDA1} The Staged Event-Driven Architecture for Highly-Concurrent Server Applications
\bibitem{SEDA2} SEDA : An Architecture for Well-Conditioned , Scalable Internet Services
\bibitem{BIGTABLE} Bigtable : A Distributed Storege System for Structured Data
\end{thebibliography}
\end{adjustvboxheight} % needed only when Appendix follows
\end{document}