# HG changeset patch # User Shoshi TAMAKI # Date 1312763878 -32400 # Node ID d779b8753c551d0b628a2bdc64ed84faad9f2402 # Parent d9e526a0e9ff263216a34fbd1fd465917ba19e66 added conclusions and modified desc of treecms , benchmark method diff -r d9e526a0e9ff -r d779b8753c55 shoshi-paper.aux --- a/shoshi-paper.aux Sun Aug 07 22:51:40 2011 +0900 +++ b/shoshi-paper.aux Mon Aug 08 09:37:58 2011 +0900 @@ -11,17 +11,26 @@ \newlabel{fig:mono-tree1}{{3}{2}} \@writefile{toc}{\contentsline {subsection}{\numberline {3.\,3}応用例：非破壊的木構造を用いた二分木辞書}{2}} \@writefile{toc}{\contentsline {subsubsection}{\numberline {3.\,3.\,1}AVL-Treeを用いた非破壊的二分木辞書}{2}} +\citation{SHOSHI2} \newlabel{fig:mono-dic1}{{4}{3}} \newlabel{fig:mono-dic2}{{5}{3}} \newlabel{fig:mono-dic2}{{6}{3}} \@writefile{toc}{\contentsline {section}{\numberline {4}非破壊的木構造を用いたCMS}{3}} +\citation{SHOSHI1} \newlabel{fig:tree-cms1}{{7}{4}} \newlabel{fig:tree-cms2}{{8}{4}} \newlabel{fig:tree-cms3}{{9}{4}} \@writefile{toc}{\contentsline {section}{\numberline {5}検証環境の構築}{4}} \newlabel{tab:bldsv-info}{{1}{4}} \@writefile{toc}{\contentsline {subsection}{\numberline {5.\,1}仮想環境}{4}} -\@writefile{toc}{\contentsline {subsection}{\numberline {5.\,2}仮想化管理ツールの実装}{4}} -\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.\,2.\,1}libvirt}{4}} -\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.\,2.\,2}webvirt}{5}} -\@writefile{toc}{\contentsline {section}{\numberline {6}まとめ}{5}} +\@writefile{toc}{\contentsline {subsection}{\numberline {5.\,2}仮想環境を用いた検証方法の検討}{4}} +\newlabel{fig:bench-method1}{{10}{5}} +\newlabel{fig:bench-method2}{{11}{5}} +\@writefile{toc}{\contentsline {subsection}{\numberline {5.\,3}仮想化管理ツールの実装}{5}} +\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.\,3.\,1}libvirt}{5}} +\@writefile{toc}{\contentsline {subsubsection}{\numberline {5.\,3.\,2}webvirt}{5}} +\bibcite{BIGTABLE}{1} +\bibcite{DYNAMO}{2} +\bibcite{SHOSHI1}{3} +\bibcite{SHOSHI2}{4} +\@writefile{toc}{\contentsline {section}{\numberline {6}まとめ}{6}} diff -r d9e526a0e9ff -r d779b8753c55 shoshi-paper.dvi Binary file shoshi-paper.dvi has changed diff -r d9e526a0e9ff -r d779b8753c55 shoshi-paper.log --- a/shoshi-paper.log Sun Aug 07 22:51:40 2011 +0900 +++ b/shoshi-paper.log Mon Aug 08 09:37:58 2011 +0900 @@ -1,4 +1,4 @@ -This is pTeXk, Version 3.1415926-p3.1.11 (utf8.euc) (TeX Live 2010) (format=platex 2011.5.15) 7 AUG 2011 22:50 +This is pTeXk, Version 3.1415926-p3.1.11 (utf8.euc) (TeX Live 2010) (format=platex 2011.5.15) 8 AUG 2011 09:31 restricted \write18 enabled. %&-line parsing enabled. **shoshi-paper.tex @@ -135,19 +135,12 @@ (Font) Font shape `JT1/gt/m/n' tried instead on input line 72. LaTeX Font Info: Font shape `JY1/gt/bx/n' in size <10> not available (Font) Font shape `JY1/gt/m/n' tried instead on input line 72. - - -LaTeX Warning: Citation `DYNAMO' on page 1 undefined on input line 77. - - -LaTeX Warning: Citation `BIGTABLE' on page 1 undefined on input line 77. - LaTeX Font Info: Font shape `JT1/gt/bx/n' in size <9> not available (Font) Font shape `JT1/gt/m/n' tried instead on input line 82. LaTeX Font Info: Font shape `JY1/gt/bx/n' in size <9> not available (Font) Font shape `JY1/gt/m/n' tried instead on input line 82. File: dest-tree1.pdf Graphic file (type pdf) - + LaTeX Font Info: External font `cmex10' loaded for size (Font) <9> on input line 91. File: dest-tree2.pdf Graphic file (type pdf) @@ -158,10 +151,10 @@ File: mono-tree1.pdf Graphic file (type pdf) File: mono-dic1.pdf Graphic file (type pdf) - [2] + +[2] File: mono-dic2.pdf Graphic file (type pdf) - - + File: mono-dic3.pdf Graphic file (type pdf) Overfull \hbox (28.76392pt too wide) in paragraph at lines 156--157 @@ -170,30 +163,39 @@ File: tree-cms1.pdf Graphic file (type pdf) -LaTeX Font Info: Font shape `JT1/mc/bx/n' in size <9> not available -(Font) Font shape `JT1/gt/m/n' tried instead on input line 178. -LaTeX Font Info: Font shape `JY1/mc/bx/n' in size <9> not available -(Font) Font shape `JY1/gt/m/n' tried instead on input line 178. +File: tree-cms2.pdf Graphic file (type pdf) + +File: tree-cms3.pdf Graphic file (type pdf) + [3] +Overfull \hbox (32.05156pt too wide) in paragraph at lines 201--208 + [] + [] -LaTeX Warning: Reference `tree-cms3' on page 3 undefined on input line 178. +Overfull \hbox (6.56854pt too wide) in paragraph at lines 211--214 +[]\JY1/mc/m/n/9 ハイパ ーバイザは複数あり \OT1/cmr/m/n/9 VMWare,KVM,Xen,Hyper- + [] -File: tree-cms2.pdf Graphic file (type pdf) - -File: tree-cms3.pdf Graphic file (type pdf) - [3] [4] [5] (./shoshi-paper.aux) +File: bench-method1.pdf Graphic file (type pdf) + +Overfull \hbox (21.56952pt too wide) in paragraph at lines 219--220 + [] + [] + +File: bench-method2.pdf Graphic file (type pdf) + [4] [5] [6] (./shoshi-paper.aux) LaTeX Warning: Label(s) may have changed. Rerun to get cross-references right o -n input line 246. +n input line 290. ) Here is how much of TeX's memory you used: - 893 strings out of 494462 - 10482 string characters out of 3171224 - 71541 words of memory out of 3000000 - 4271 multiletter control sequences out of 15000+200000 + 898 strings out of 494462 + 10569 string characters out of 3171224 + 73541 words of memory out of 3000000 + 4274 multiletter control sequences out of 15000+200000 19246 words of font info for 74 fonts, out of 3000000 for 9000 678 hyphenation exceptions out of 8191 25i,9n,34p,1550b,843s stack positions out of 5000i,500n,10000p,200000b,50000s -Output written on shoshi-paper.dvi (5 pages, 27152 bytes). +Output written on shoshi-paper.dvi (6 pages, 33840 bytes). diff -r d9e526a0e9ff -r d779b8753c55 shoshi-paper.pdf Binary file shoshi-paper.pdf has changed diff -r d9e526a0e9ff -r d779b8753c55 shoshi-paper.tex --- a/shoshi-paper.tex Sun Aug 07 22:51:40 2011 +0900 +++ b/shoshi-paper.tex Mon Aug 08 09:37:58 2011 +0900 @@ -70,17 +70,17 @@ \maketitle \section{はじめに} -　Cassandraは複数のサーバーで動作を想定した分散データベースである．本研究は，Cassandraの検証と非破壊的木構造を用いたスケーラビリティのあるCMSの設計と開発を行った． +Cassandraは複数のサーバーで動作を想定した分散データベースである．本研究は，Cassandraの検証と非破壊的木構造を用いたスケーラビリティのあるCMSの設計と開発を行った． 非破壊的木構造を用いたCMSのとは，木構造で表すことの出来るコンテンツを編集する際に，編集元の木構造を破壊することなく編集するアルゴリズムである．これを利用してCassandra上に非破壊的木構造を構築しCMSを実装することができた．\\ -　本研究では，開発したCMSのスケーラビリティの検証を行うため，仮想環境を用いた検証環境の構築と管理ソフトウェアを開発した． +本研究では，開発したCMSのスケーラビリティの検証を行うため，仮想環境を用いた検証環境の構築と管理ソフトウェアを開発した． \section{分散データベースCassandra} - Cassandraは, FaceBookが自社のために開発した分散Key-Valueストアデータベースであり，Dynamo\cite{DYNAMO}とBigTable\cite{BIGTABLE}を合わせた特徴を持っている. 2008年にオープンソースとして公開され, 2009年にApache Incubatorのプロジェクトとなった. +Cassandraは, FaceBookが自社のために開発した分散Key-Valueストアデータベースであり，Dynamo\cite{DYNAMO}とBigTable\cite{BIGTABLE}を合わせた特徴を持っている. 2008年にオープンソースとして公開され, 2009年にApache Incubatorのプロジェクトとなった. 2010年にはApacheのトップレベルプロジェクトとなり, 現在でも頻繁にバージョンアップが行われている. \\ \section{非破壊的木構造} -　非破壊的木構造とは，木構造を編集する際に編集元の木構造を破壊することなく，新しく木構造を構築する．新しい木構造のルートノードを置き換えることにより編集する方法である．\\ +非破壊的木構造とは，木構造を編集する際に編集元の木構造を破壊することなく，新しく木構造を構築する．新しい木構造のルートノードを置き換えることにより編集する方法である．\\ 非破壊的に変更することで，編集元の破壊することなく編集することが出来るため，木構造の整合性を保ちつつ変更することが可能になる． \subsection{木構造の破壊的変更} -　従来の破壊的木構造は，存在する木構造を書き換えて編集する．以下の様な操作を行う．\\ +従来の破壊的木構造は，存在する木構造を書き換えて編集する．以下の様な操作を行う．\\ \begin{figure}[!htbp] \begin{center} \includegraphics[scale=0.5]{dest-tree1.pdf} @@ -88,7 +88,7 @@ \caption{木構造の破壊的変更例} \label{fig:dest-tree1} \end{figure} -　図\ref{fig:dest-tree1}の操作では，ノード$F$の内容をノード$G$に書き換える操作を行った．破壊的変更では，単純に編集したいノードを書き換えることにより行われる．この操作では，編集時に木を参照している処理がある場合，参照されている木構造を破壊するため，参照を開始した自転での木構造の整合性が破壊されるという問題が起きる．\\ +図\ref{fig:dest-tree1}の操作では，ノード$F$の内容をノード$G$に書き換える操作を行った．破壊的変更では，単純に編集したいノードを書き換えることにより行われる．この操作では，編集時に木を参照している処理がある場合，参照されている木構造を破壊するため，参照を開始した自転での木構造の整合性が破壊されるという問題が起きる．\\ \begin{figure}[!htbp] \begin{center} \includegraphics[scale=0.4]{dest-tree2.pdf} @@ -165,7 +165,7 @@ この二分木辞書は主に，辞書をコピーするときに効果を発揮する． \section{非破壊的木構造を用いたCMS} -　本研究では，非破壊木構造を用いてスケーラビリティのあるCMSの設計と実装を行った．本システムではコンテンツを木構造で表現する．Cassandra上に木構造を構築し，それを非破壊的に編集する．図\ref{fig:tree-cms1}に概略図を示す． +　本研究では，非破壊木構造を用いてスケーラビリティのあるCMSの設計と実装を行った．\cite{SHOSHI2}本システムではコンテンツを木構造で表現する．Cassandra上に木構造を構築し，それを非破壊的に編集する．図\ref{fig:tree-cms1}に概略図を示す． \begin{figure}[!htbp] \begin{center} \includegraphics[scale=0.2]{tree-cms1.pdf} @@ -175,7 +175,6 @@ \end{figure} \\本システムでは，Cassandra上に木構造を構築するサーバー(API Server)を設ける，サーバーの提供するAPIを用いてコンテンツを非破壊的に操作することができる． WebServerはAPI Serverを利用してコンテンツを操作しコンテンツの配置を記述したレイアウトを用いてレンダリングを行い，木構造を編集する際には専用のエディタを提供する．(図\ref{fig:tree-cms2}) -また，各段階(API Server , WebServer , Browser)で木構造のキャッシュを保持し，必要になったときのみキャッシュを同期・マージさせる．(図\ref{tree-cms3})こうすることでスケーラビリティを確保することが出来ると考えられる． \begin{figure}[!htbp] \begin{center} \includegraphics[scale=0.35]{tree-cms2.pdf} @@ -183,6 +182,8 @@ \caption{木構造のレンダリングと編集} \label{fig:tree-cms2} \end{figure} +\\また，各段階(API Server , WebServer , Browser)で木構造のキャッシュを保持している．各段階のキャッシュは，親の木構造に対してコミット，マージ処理を行うことができ，分散レポジトリと同様の機能を提供している．こうすることでスケーラビリティを確保することが出来ると考えられる． +(図\ref{fig:tree-cms3}) \begin{figure}[!htbp] \begin{center} \includegraphics[scale=0.35]{tree-cms3.pdf} @@ -191,20 +192,46 @@ \label{fig:tree-cms3} \end{figure} \section{検証環境の構築} -検証では，前回用いたPCクラスタがシステム更新のために使用不可になってしまったため，新しく導入されたブレードサーバーによる仮想環境において検証環境を構築する． +検証では，前回用いたPCクラスタがシステム更新のために使用不可になってしまったため，新しく導入されたブレードサーバーによる仮想環境において検証環境を構築する．\cite{SHOSHI1} 仮想環境のホストとして利用するサーバーを表\ref{tab:bldsv-info}に示す． \begin{table}[!htbp] -\caption{検証環境に用いたサーバー} +\caption{検証環境に用意したサーバー} \label{tab:bldsv-info} \begin{center} \begin{tabular}{|c|c|c|c|} \hline サーバー名 & CPU & メモリ & 仮想化 \\ \hline \hline -server01 & Xeon x2 & 139GB & KVM \\ \hline +server01 & Xeon X5650 x2 & 130GB & VMware ESX \\ \hline +server02 & Xeon X5650 x2 & 130GB & VMware ESX \\ \hline +server03 & Xeon X5650 x2 & 130GB & VMware ESX \\ \hline +server04 & Xeon X5650 x2 & 130GB & KVM \\ \hline \end{tabular} \end{center} \end{table} \subsection{仮想環境} -説明する必要あり？ +仮想化とは１つの物理マシン上にて複数のオペレーティングシステムを動作させる技術である．物理マシンにハイパーバイザと呼ばれる物理マシンのリソースを仮想化するレイヤを追加する．\\ +ハイパーバイザは仮想マシンを作成し仮想化したリソースを仮想マシンに提供する．その上でオペレーティングシステムを動作させることで，複数のオペレーティングシステムの稼働を可能にする．\\ +ハイパーバイザは複数ありVMWare,KVM,Xen,Hyper-Vなどがあげられる．本検証では，KVMとVMWareを用いた検証を行う予定である． +\subsection{仮想環境を用いた検証方法の検討} +仮想環境を用いた検証方法は基本的に前回のPCクラスタを用いたスケーラビリティ検証と同様の方法を採用する．(図\ref{fig:bench-method1}) +つまり，並列アクセス用のクライアントクラスタとサーバー用のクラスタを用意する．今回は，server01-03をクライアントクラスタ用の仮想環境に，server04をサーバークラスタ用の仮想環境として用いる． +\begin{figure}[!htbp] +\begin{center} + \includegraphics[scale=0.35]{bench-method1.pdf} +\end{center} +\caption{PCクラスタを用いたベンチマーク方法} +\label{fig:bench-method1} +\end{figure} +\\今回の検証では，PCクラスタを用いるのではなく仮想環境利用する．仮想環境において複数の仮想マシンで物理マシンのリソースを共有することになるため，仮想マシン同士が物理マシンのリソースを奪い合う可能性が出てくる．リソースの奪い合いによる，仮想マシンの性能低下を防ぐため，仮想マシンのリソースを予約・制限する必要がある．(図\ref{fig:bench-method2}) +仮想マシンのリソースを予約・制限すると，制限以上の性能は出なくなる．それを応用し，物理マシンのリソースの範囲内で同様の仮想マシンを構築することにより台数効果も検証できるのではないかと思われる． +\begin{figure}[!htbp] +\begin{center} + \includegraphics[scale=0.4]{bench-method2.pdf} +\end{center} +\caption{仮想環境を用いたクラスタ環境の構築} +\label{fig:bench-method2} +\end{figure} +\\以上のように仮想環境を構築し仮想環境において検証を行う．仮想環境の構築において，複数の仮想マシンを操作することが必要となる． +通常，物理マシンのコンソールより個々の仮想マシンを操作する作業は効率が悪いため，管理ツールの開発を行う． \subsection{仮想化管理ツールの実装} 仮想環境で複数の仮想マシンを操作する場合，仮想マシン個々の設定を物理マシンのコンソールより操作するのは大変困難な作業であり，仮想化管理ツールの利用が必須であると考えられる．\\ そこで，本研究では初めに仮想環境を管理するツールを開発し，検証環境の構築に利用する． @@ -242,5 +269,22 @@ \end{itemize} また，シングルノードのみを管理する目的で開発されているため，ライブマイグレーションなどの機能は実装していない． \section{まとめ} +本研究では，構築した非破壊的構造を用いたCMSのスケーラビリティ検証環境を構築するために，ウェブ上の管理ツールであるwebvirtの実装を行った．また，非破壊的構造の応用例として並列に読み書きを行うことの出来るバランス木を用いた二分木辞書の実装例を示した． +次回は，構築した仮想環境によるスケーラビリティの検証を行う予定である． + +\begin{adjustvboxheight} % needed only when Appendix follows +\begin{thebibliography}{99} +\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 +\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{SHOSHI1} +{Shoshi TAMAKI,Shinji KONO}:Cassandraを用いたCMSのPCクラスタを用いたスケーラビリティの検証,ソフトウェア科学会 (2010) +\bibitem{SHOSHI2} +{Shoshi TAMAKI,Shinji KONO,Yu TANINARI}: +Cassandraを使ったスケーラビリティのあるCMSの設計,情報処理学会システムソフトウェアとオペレーティング・システム研究会(OS) + +\end{thebibliography} +\end{adjustvboxheight} % needed only when Appendix follows \end{document} diff -r d9e526a0e9ff -r d779b8753c55 tree-cms2.graffle Binary file tree-cms2.graffle has changed diff -r d9e526a0e9ff -r d779b8753c55 tree-cms2.pdf Binary file tree-cms2.pdf has changed