Mercurial > hg > Papers > 2011 > shoshi-jssst

comparison shoshi-paper.tex @ 3:d779b8753c55

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
added conclusions and modified desc of treecms , benchmark method
author Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
date Mon, 08 Aug 2011 09:37:58 +0900
parents d9e526a0e9ff
children bb4327f3c4c4
comparison
equal deleted inserted replaced
2:d9e526a0e9ff 3:d779b8753c55
68 % \Eabstract{} 68 % \Eabstract{}
69 % 69 %
70 \maketitle 70 \maketitle
71 71
72 \section{はじめに} 72 \section{はじめに}
73 　Cassandraは複数のサーバーで動作を想定した分散データベースである．本研究は，Cassandraの検証と非破壊的木構造を用いたスケーラビリティのあるCMSの設計と開発を行った． 73 Cassandraは複数のサーバーで動作を想定した分散データベースである．本研究は，Cassandraの検証と非破壊的木構造を用いたスケーラビリティのあるCMSの設計と開発を行った．
74 非破壊的木構造を用いたCMSのとは，木構造で表すことの出来るコンテンツを編集する際に，編集元の木構造を破壊することなく編集するアルゴリズムである．これを利用してCassandra上に非破壊的木構造を構築しCMSを実装することができた．\\ 74 非破壊的木構造を用いたCMSのとは，木構造で表すことの出来るコンテンツを編集する際に，編集元の木構造を破壊することなく編集するアルゴリズムである．これを利用してCassandra上に非破壊的木構造を構築しCMSを実装することができた．\\
75 　本研究では，開発したCMSのスケーラビリティの検証を行うため，仮想環境を用いた検証環境の構築と管理ソフトウェアを開発した． 75 本研究では，開発したCMSのスケーラビリティの検証を行うため，仮想環境を用いた検証環境の構築と管理ソフトウェアを開発した．
76 \section{分散データベースCassandra} 76 \section{分散データベースCassandra}
77 Cassandraは, FaceBookが自社のために開発した分散Key-Valueストアデータベースであり，Dynamo\cite{DYNAMO}とBigTable\cite{BIGTABLE}を合わせた特徴を持っている. 2008年にオープンソースとして公開され, 2009年にApache Incubatorのプロジェクトとなった. 77 Cassandraは, FaceBookが自社のために開発した分散Key-Valueストアデータベースであり，Dynamo\cite{DYNAMO}とBigTable\cite{BIGTABLE}を合わせた特徴を持っている. 2008年にオープンソースとして公開され, 2009年にApache Incubatorのプロジェクトとなった.
78 2010年にはApacheのトップレベルプロジェクトとなり, 現在でも頻繁にバージョンアップが行われている. \\ 78 2010年にはApacheのトップレベルプロジェクトとなり, 現在でも頻繁にバージョンアップが行われている. \\
79 \section{非破壊的木構造} 79 \section{非破壊的木構造}
80 　非破壊的木構造とは，木構造を編集する際に編集元の木構造を破壊することなく，新しく木構造を構築する．新しい木構造のルートノードを置き換えることにより編集する方法である．\\ 80 非破壊的木構造とは，木構造を編集する際に編集元の木構造を破壊することなく，新しく木構造を構築する．新しい木構造のルートノードを置き換えることにより編集する方法である．\\
81 非破壊的に変更することで，編集元の破壊することなく編集することが出来るため，木構造の整合性を保ちつつ変更することが可能になる． 81 非破壊的に変更することで，編集元の破壊することなく編集することが出来るため，木構造の整合性を保ちつつ変更することが可能になる．
82 \subsection{木構造の破壊的変更} 82 \subsection{木構造の破壊的変更}
83 　従来の破壊的木構造は，存在する木構造を書き換えて編集する．以下の様な操作を行う．\\ 83 従来の破壊的木構造は，存在する木構造を書き換えて編集する．以下の様な操作を行う．\\
84 \begin{figure}[!htbp] 84 \begin{figure}[!htbp]
85 \begin{center} 85 \begin{center}
86 \includegraphics[scale=0.5]{dest-tree1.pdf} 86 \includegraphics[scale=0.5]{dest-tree1.pdf}
87 \end{center} 87 \end{center}
88 \caption{木構造の破壊的変更例} 88 \caption{木構造の破壊的変更例}
89 \label{fig:dest-tree1} 89 \label{fig:dest-tree1}
90 \end{figure} 90 \end{figure}
91 　図\ref{fig:dest-tree1}の操作では，ノード$F$の内容をノード$G$に書き換える操作を行った．破壊的変更では，単純に編集したいノードを書き換えることにより行われる．この操作では，編集時に木を参照している処理がある場合，参照されている木構造を破壊するため，参照を開始した自転での木構造の整合性が破壊されるという問題が起きる．\\ 91 図\ref{fig:dest-tree1}の操作では，ノード$F$の内容をノード$G$に書き換える操作を行った．破壊的変更では，単純に編集したいノードを書き換えることにより行われる．この操作では，編集時に木を参照している処理がある場合，参照されている木構造を破壊するため，参照を開始した自転での木構造の整合性が破壊されるという問題が起きる．\\
92 \begin{figure}[!htbp] 92 \begin{figure}[!htbp]
93 \begin{center} 93 \begin{center}
94 \includegraphics[scale=0.4]{dest-tree2.pdf} 94 \includegraphics[scale=0.4]{dest-tree2.pdf}
95 \end{center} 95 \end{center}
96 \caption{破壊的変更の問題点} 96 \caption{破壊的変更の問題点}
163 　非破壊辞書のコピーは，単にルートノードを共有するだけで行うことが出来る．木構造は破壊されないため，元の木構造は不変である．共有した木構造を元にローカル新しい木構造を作成していくため，問題は起きない．\\よって，この場合の計算量は定数でありO(1)である． 163 　非破壊辞書のコピーは，単にルートノードを共有するだけで行うことが出来る．木構造は破壊されないため，元の木構造は不変である．共有した木構造を元にローカル新しい木構造を作成していくため，問題は起きない．\\よって，この場合の計算量は定数でありO(1)である．
164 \end{enumerate} 164 \end{enumerate}
165 この二分木辞書は主に，辞書をコピーするときに効果を発揮する． 165 この二分木辞書は主に，辞書をコピーするときに効果を発揮する．
166 166
167 \section{非破壊的木構造を用いたCMS} 167 \section{非破壊的木構造を用いたCMS}
168 　本研究では，非破壊木構造を用いてスケーラビリティのあるCMSの設計と実装を行った．本システムではコンテンツを木構造で表現する．Cassandra上に木構造を構築し，それを非破壊的に編集する．図\ref{fig:tree-cms1}に概略図を示す． 168 　本研究では，非破壊木構造を用いてスケーラビリティのあるCMSの設計と実装を行った．\cite{SHOSHI2}本システムではコンテンツを木構造で表現する．Cassandra上に木構造を構築し，それを非破壊的に編集する．図\ref{fig:tree-cms1}に概略図を示す．
169 \begin{figure}[!htbp] 169 \begin{figure}[!htbp]
170 \begin{center} 170 \begin{center}
171 \includegraphics[scale=0.2]{tree-cms1.pdf} 171 \includegraphics[scale=0.2]{tree-cms1.pdf}
172 \end{center} 172 \end{center}
173 \caption{システムのアーキテクチャ} 173 \caption{システムのアーキテクチャ}
174 \label{fig:tree-cms1} 174 \label{fig:tree-cms1}
175 \end{figure} 175 \end{figure}
176 \\本システムでは，Cassandra上に木構造を構築するサーバー(API Server)を設ける，サーバーの提供するAPIを用いてコンテンツを非破壊的に操作することができる． 176 \\本システムでは，Cassandra上に木構造を構築するサーバー(API Server)を設ける，サーバーの提供するAPIを用いてコンテンツを非破壊的に操作することができる．
177 WebServerはAPI Serverを利用してコンテンツを操作しコンテンツの配置を記述したレイアウトを用いてレンダリングを行い，木構造を編集する際には専用のエディタを提供する．(図\ref{fig:tree-cms2}) 177 WebServerはAPI Serverを利用してコンテンツを操作しコンテンツの配置を記述したレイアウトを用いてレンダリングを行い，木構造を編集する際には専用のエディタを提供する．(図\ref{fig:tree-cms2})
178 また，各段階(API Server , WebServer , Browser)で木構造のキャッシュを保持し，必要になったときのみキャッシュを同期・マージさせる．(図\ref{tree-cms3})こうすることでスケーラビリティを確保することが出来ると考えられる．
179 \begin{figure}[!htbp] 178 \begin{figure}[!htbp]
180 \begin{center} 179 \begin{center}
181 \includegraphics[scale=0.35]{tree-cms2.pdf} 180 \includegraphics[scale=0.35]{tree-cms2.pdf}
182 \end{center} 181 \end{center}
183 \caption{木構造のレンダリングと編集} 182 \caption{木構造のレンダリングと編集}
184 \label{fig:tree-cms2} 183 \label{fig:tree-cms2}
185 \end{figure} 184 \end{figure}
185 \\また，各段階(API Server , WebServer , Browser)で木構造のキャッシュを保持している．各段階のキャッシュは，親の木構造に対してコミット，マージ処理を行うことができ，分散レポジトリと同様の機能を提供している．こうすることでスケーラビリティを確保することが出来ると考えられる．
186 (図\ref{fig:tree-cms3})
186 \begin{figure}[!htbp] 187 \begin{figure}[!htbp]
187 \begin{center} 188 \begin{center}
188 \includegraphics[scale=0.35]{tree-cms3.pdf} 189 \includegraphics[scale=0.35]{tree-cms3.pdf}
189 \end{center} 190 \end{center}
190 \caption{多段キャッシュとマージ処理} 191 \caption{多段キャッシュとマージ処理}
191 \label{fig:tree-cms3} 192 \label{fig:tree-cms3}
192 \end{figure} 193 \end{figure}
193 \section{検証環境の構築} 194 \section{検証環境の構築}
194 検証では，前回用いたPCクラスタがシステム更新のために使用不可になってしまったため，新しく導入されたブレードサーバーによる仮想環境において検証環境を構築する． 195 検証では，前回用いたPCクラスタがシステム更新のために使用不可になってしまったため，新しく導入されたブレードサーバーによる仮想環境において検証環境を構築する．\cite{SHOSHI1}
195 仮想環境のホストとして利用するサーバーを表\ref{tab:bldsv-info}に示す． 196 仮想環境のホストとして利用するサーバーを表\ref{tab:bldsv-info}に示す．
196 \begin{table}[!htbp] 197 \begin{table}[!htbp]
197 \caption{検証環境に用いたサーバー} 198 \caption{検証環境に用意したサーバー}
198 \label{tab:bldsv-info} 199 \label{tab:bldsv-info}
199 \begin{center} 200 \begin{center}
200 \begin{tabular}{|c|c|c|c|} \hline 201 \begin{tabular}{|c|c|c|c|} \hline
201 サーバー名 & CPU & メモリ & 仮想化 \\ \hline \hline 202 サーバー名 & CPU & メモリ & 仮想化 \\ \hline \hline
202 server01 & Xeon x2 & 139GB & KVM \\ \hline 203 server01 & Xeon X5650 x2 & 130GB & VMware ESX \\ \hline
204 server02 & Xeon X5650 x2 & 130GB & VMware ESX \\ \hline
205 server03 & Xeon X5650 x2 & 130GB & VMware ESX \\ \hline
206 server04 & Xeon X5650 x2 & 130GB & KVM \\ \hline
203 \end{tabular} 207 \end{tabular}
204 \end{center} 208 \end{center}
205 \end{table} 209 \end{table}
206 \subsection{仮想環境} 210 \subsection{仮想環境}
207 説明する必要あり？ 211 仮想化とは１つの物理マシン上にて複数のオペレーティングシステムを動作させる技術である．物理マシンにハイパーバイザと呼ばれる物理マシンのリソースを仮想化するレイヤを追加する．\\
212 ハイパーバイザは仮想マシンを作成し仮想化したリソースを仮想マシンに提供する．その上でオペレーティングシステムを動作させることで，複数のオペレーティングシステムの稼働を可能にする．\\
213 ハイパーバイザは複数ありVMWare,KVM,Xen,Hyper-Vなどがあげられる．本検証では，KVMとVMWareを用いた検証を行う予定である．
214 \subsection{仮想環境を用いた検証方法の検討}
215 仮想環境を用いた検証方法は基本的に前回のPCクラスタを用いたスケーラビリティ検証と同様の方法を採用する．(図\ref{fig:bench-method1})
216 つまり，並列アクセス用のクライアントクラスタとサーバー用のクラスタを用意する．今回は，server01-03をクライアントクラスタ用の仮想環境に，server04をサーバークラスタ用の仮想環境として用いる．
217 \begin{figure}[!htbp]
218 \begin{center}
219 \includegraphics[scale=0.35]{bench-method1.pdf}
220 \end{center}
221 \caption{PCクラスタを用いたベンチマーク方法}
222 \label{fig:bench-method1}
223 \end{figure}
224 \\今回の検証では，PCクラスタを用いるのではなく仮想環境利用する．仮想環境において複数の仮想マシンで物理マシンのリソースを共有することになるため，仮想マシン同士が物理マシンのリソースを奪い合う可能性が出てくる．リソースの奪い合いによる，仮想マシンの性能低下を防ぐため，仮想マシンのリソースを予約・制限する必要がある．(図\ref{fig:bench-method2})
225 仮想マシンのリソースを予約・制限すると，制限以上の性能は出なくなる．それを応用し，物理マシンのリソースの範囲内で同様の仮想マシンを構築することにより台数効果も検証できるのではないかと思われる．
226 \begin{figure}[!htbp]
227 \begin{center}
228 \includegraphics[scale=0.4]{bench-method2.pdf}
229 \end{center}
230 \caption{仮想環境を用いたクラスタ環境の構築}
231 \label{fig:bench-method2}
232 \end{figure}
233 \\以上のように仮想環境を構築し仮想環境において検証を行う．仮想環境の構築において，複数の仮想マシンを操作することが必要となる．
234 通常，物理マシンのコンソールより個々の仮想マシンを操作する作業は効率が悪いため，管理ツールの開発を行う．
208 \subsection{仮想化管理ツールの実装} 235 \subsection{仮想化管理ツールの実装}
209 仮想環境で複数の仮想マシンを操作する場合，仮想マシン個々の設定を物理マシンのコンソールより操作するのは大変困難な作業であり，仮想化管理ツールの利用が必須であると考えられる．\\ 236 仮想環境で複数の仮想マシンを操作する場合，仮想マシン個々の設定を物理マシンのコンソールより操作するのは大変困難な作業であり，仮想化管理ツールの利用が必須であると考えられる．\\
210 そこで，本研究では初めに仮想環境を管理するツールを開発し，検証環境の構築に利用する． 237 そこで，本研究では初めに仮想環境を管理するツールを開発し，検証環境の構築に利用する．
211 \subsubsection{libvirt} 238 \subsubsection{libvirt}
212 libvirtとは，複数ある仮想環境においてノードをリモートより共通で十分に安全な安定した管理方法を提供するライブラリである．この場合のノードは１台の物理的なマシンであり，ドメインは仮想マシンを指す． 239 libvirtとは，複数ある仮想環境においてノードをリモートより共通で十分に安全な安定した管理方法を提供するライブラリである．この場合のノードは１台の物理的なマシンであり，ドメインは仮想マシンを指す．
240 \item{ストレージプールの管理} 267 \item{ストレージプールの管理}
241 \item{ネットワークの管理} 268 \item{ネットワークの管理}
242 \end{itemize} 269 \end{itemize}
243 また，シングルノードのみを管理する目的で開発されているため，ライブマイグレーションなどの機能は実装していない． 270 また，シングルノードのみを管理する目的で開発されているため，ライブマイグレーションなどの機能は実装していない．
244 \section{まとめ} 271 \section{まとめ}
272 本研究では，構築した非破壊的構造を用いたCMSのスケーラビリティ検証環境を構築するために，ウェブ上の管理ツールであるwebvirtの実装を行った．また，非破壊的構造の応用例として並列に読み書きを行うことの出来るバランス木を用いた二分木辞書の実装例を示した．
273 次回は，構築した仮想環境によるスケーラビリティの検証を行う予定である．
274
275 \begin{adjustvboxheight} % needed only when Appendix follows
276 \begin{thebibliography}{99}
277 \bibitem{BIGTABLE}{Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach
278 Mike Burrows, Tushar Chandra, Andrew Fikes, Robert E. Gruber}: Bigtable : A Distributed Storege System for Structured Data
279 \bibitem{DYNAMO} {Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati , Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall , Werner Vogels}:
280 Dynamo: Amazon's Highly Avaliable Key-value Store , SOSP (2007)
281 \bibitem{SHOSHI1}
282 {Shoshi TAMAKI,Shinji KONO}:Cassandraを用いたCMSのPCクラスタを用いたスケーラビリティの検証,ソフトウェア科学会 (2010)
283 \bibitem{SHOSHI2}
284 {Shoshi TAMAKI,Shinji KONO,Yu TANINARI}:
285 Cassandraを使ったスケーラビリティのあるCMSの設計,情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS)
286
287 \end{thebibliography}
288 \end{adjustvboxheight} % needed only when Appendix follows
245 289
246 \end{document} 290 \end{document}