Papers/2011/shoshi-jssst: shoshi-paper.tex comparison

comparison shoshi-paper.tex @ 6:bd7d39a4e57f

correct spellmiss,wordiness,etc...

author	Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
date	Mon, 08 Aug 2011 21:58:05 +0900
parents	bb4327f3c4c4
children

comparison

equal deleted inserted replaced

-:bb4327f3c4c4
+:bd7d39a4e57f
 % 行頭の間隔は使わない
 % 段落は1行空ける
 %
 % 和文アブストラクト
 \Jabstract{%
-本研究では, スケーラビリティのあるCMSを開発するために, PCクラスタを利用したスケーラビリティの検証環境を構築し, ロックフリーな木構造である非破壊的木構造・多段キャッシュ・Cassandraを用いた設計と実装を行って来た. 今回は, 実装したシステムのスケーラビリティを検証するため, 構築したスケーラビリティの検証環境を用いてベンチマークを取り, スケーラビリティがあるか確認するために, 環境構築を行った. また, 非破壊的木構造をバランス木に応用し, バランス木の性能であるO(log N)を保ちつつ並列に読み・書き込みが可能である辞書アルゴリズムの提案をする.
+本研究では, スケーラビリティのあるCMSを開発するために, PCクラスタを利用したスケーラビリティの検証環境を構築し, ロックフリーな木構造である非破壊的木構造・多段キャッシュ・Cassandraを用いた設計と実装を行って来た.
+今回は, 実装したシステムのスケーラビリティを検証するため, 構築した検証環境を用いてベンチマークを取り, スケーラビリティがあるか確認するために, 環境構築を行った.
+また, 非破壊的木構造をバランス木に応用し, バランス木の性能であるO(log N)を保ちつつ並列に読み・書き込みが可能である辞書アルゴリズムの提案をする.
 }
 %
 % 英文アブストラクト（大会論文には必要なし)
 % \Eabstract{}
 %
 \maketitle
 \section{はじめに}
-Cassandraは複数のサーバーで動作を想定した分散デデータベースある. 本研究は, Cassandraの検証と非破壊的木構造を用いたスケーラビリティのあるCMSの設計と開発を行った.
+Cassandraは複数のサーバーで動作を想定した分散デデータベースある. Cassandraは, FaceBookが自社のために開発した分散Key-Valueストアデータベースであり, Dynamo\cite{DYNAMO}とBigTable\cite{BIGTABLE}を合わせた特徴を持っている.
+2008年にオープンソースとして公開され, 2009年にApache Incubatorのプロジェクトとなり，現在でも頻繁にバージョンアップが行われている. 本研究は, Cassandraの検証と非破壊的木構造を用いたスケーラビリティのあるCMSの設計と開発を行った.
 非破壊的木構造を用いたCMSのとは, 木構造で表すことの出来るコンテンツを編集する際に, 編集元の木構造を破壊することなく編集するアルゴリズムである. これを利用してCassandra上に非破壊的木構造を構築しCMSを実装することができた.
 本研究では, 開発したCMSのスケーラビリティの検証を行うため, 仮想環境を用いた検証環境の構築と管理ソフトウェアを開発した.
-\section{分散データベースCassandra}
-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}
 \end{center}
 \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}
 \end{center}
 \caption{破壊的変更の問題点}
 \label{fig:dest-tree2}
 \end{figure}
-この問題を解決するためには, 木構造の操作に排他制御を取り入れてロックする必要がある. しかし, その方法ではスケーラビリティを確保できるとは考えられないため, 非破壊的な変更を方法を用いて木構造を編集する.
+この問題を解決するためには, 木構造の操作に排他制御を取り入れてロックする必要がある. しかし, その方法ではスケーラビリティを確保できるとは考えられないため, 非破壊的な変更を用いて木構造を編集する. \\
-\subsection{木構造の非破壊的変更}
 木構造の非破壊的な変更は, 編集元の木構造を破壊せずに編集を行う, 編集の様子を図\ref{fig:mono-tree1}に示す. 図\ref{fig:mono-tree1}では図\ref{fig:dest-tree1}と同様にノード$F$の内容をノード$G$に書き換える処理を行っている.
 \begin{figure}[!htbp]
 \begin{center}
 	\includegraphics[scale=0.4]{mono-tree1.pdf}
 	\item{ルートノードであるノード$A$から編集対象であるノード$F$までのパスをコピーする. （ノード$A,C,F$をコピーする）}
 	\item{パスに含まれないノードは編集元のノードと共有する. （コピーノード$A$からノード$B$へリンクを作成する）}
 	\item{編集対象であるノード$F$は編集せず, コピーしたノード$F$をノード$G$へと編集する. }
 	\item{木構造のルートノードをノード$A$からコピーしたノード$A$へと置き換える. }
 \end{enumerate}
-この手順では, 元の木構造は破壊されることは無い, そのため木の閲覧者が存在していても閲覧している木構造の整合性が破壊されることはない.
+この手順では, 元の木構造は破壊されることは無く, 木の閲覧者が存在していても閲覧している木構造の整合性が破壊されることはない.
 よって, 並列に読み書きを行うことが出来る.
-\subsection{応用例：非破壊的木構造を用いた二分木辞書}
+\section{非破壊的木構造を用いた二分木辞書}
 この方法の応用例として非破壊的木構造とバランス木を用いた二分木辞書を考えることが出来る. 二分木辞書とは二分探索を用いたO(lg n)を保証する辞書アルゴリズムである. 二分木辞書では, バランスのとれた木構造を維持するためにバランス木のアルゴリズムを利用する.
 これらのアルゴリズムと非破壊的木構造を組み合わせることにより, 並列に読み書きを行うことが出来る辞書を作成することが出来る.
 また, この辞書アルゴリズムの利点として辞書全体のコピーにかかる計算量がO(1)で済むことも利点の一つである.
-\subsubsection{AVL-Treeを用いた非破壊的二分木辞書}
+\subsection{AVL-Treeを用いた非破壊的二分木辞書}
 実装例として, AVL-Treeを用いた非破壊的二分木辞書を紹介する. この辞書は読み書きがO(lg n)かつ辞書の複製のコストがO(1)で有ることを保証する.
 \begin{enumerate}
 \item{辞書の読み込み}
-非破壊二分木辞書の読み込みは通常の二分木と同様で, ルートノードよりキーの大小関係を比較し値を検索する. そのため, 省略する.
+非破壊二分木辞書の読み込みは通常の二分木と同様で, ルートノードよりキーの大小関係を比較し値を検索する.
 キーを検索する際に, 二分木辞書で使われている木構造は破壊されることがないため, 並列に行うことが出来き, スレッドセーフである.
 \item{辞書の書き込み}
 非破壊辞書の書き込みは以下の手順で行われる.
 \begin{enumerate}
 \end{center}
 \caption{手順1:ノードのコピーと書き込み}
 \label{fig:mono-dic1}
 \end{figure}
-この例では, 木構造に新しくノード$7$を追加する. そのため, 編集元の二分木より$50,25,15$のノードをコピーする. 他の影響のない$100,35$は共有する.
+図\ref{fig:mono-dic1}では, 木構造に新しくノード$7$を追加する. そのため, 編集元の二分木より$50,25,15$のノードをコピーする. 他の影響のない$100,35$は共有する.
 \item{ローカルにコピーしたノードを編集し, 書き込みむ}
 次に, コピーした木構造を編集し書き込みを行う. 図\ref{fig:mono-dic1}の例ではノード$15$の右部分に新しくノード$7$を追加する.
 \item{コピーし編集したノードよりルートノードまでを走査し, 木の回転が必要な場合は回転させる. }
 \begin{figure}[!htbp]
 \end{enumerate}
 \item{辞書のコピー}
 非破壊辞書のコピーは, 単にルートノードを共有するだけで行うことが出来る. 木構造は破壊されないため, 元の木構造は不変である. 共有した木構造を元にローカル新しい木構造を作成していくため, 問題は起きない. よって, この場合の計算量は定数でありO(1)である.
 \end{enumerate}
-この二分木辞書は主に, 辞書をコピーするときに効果を発揮する.
+この二分木辞書は主に, 辞書をコピーするときに効果を発揮する. 本研究で開発した非破壊的構造を用いたCMSでは, 木構造を編集する際に, ノードの持つ属性を同時にコピーする．
+本来は単純な辞書のコピーで合ったが, これを非破壊的二分木辞書を利用することで改善することが出来るのではないかと考えられる.
 \section{非破壊的木構造を用いたCMS}
 本研究では, 非破壊木構造を用いてスケーラビリティのあるCMSの設計と実装を行った. \cite{SHOSHI2}本システムではコンテンツを木構造で表現する. Cassandra上に木構造を構築し, それを非破壊的に編集する. 図\ref{fig:tree-cms1}に概略図を示す.
 \begin{figure}[!htbp]
 \end{center}
 \caption{多段キャッシュとマージ処理}
 \label{fig:tree-cms3}
 \end{figure}
 \section{検証環境の構築}
-検証では, 前回用いたPCクラスタがシステム更新のために使用不可になってしまったため, 新しく導入されたブレードサーバーによる仮想環境において検証環境を構築する. \cite{SHOSHI1}
+検証では, 新しく導入されたブレードサーバーによる仮想環境において検証環境を構築する. \cite{SHOSHI1}
 仮想環境のホストとして利用するサーバーを表\ref{tab:bldsv-info}に示す.
 \begin{table}[!htbp]
 \caption{検証環境に用意したサーバー}
 \label{tab:bldsv-info}
 \begin{center}
 \subsection{仮想環境}
 仮想化とは１つの物理マシン上にて複数のオペレーティングシステムを動作させる技術である. 物理マシンにハイパーバイザと呼ばれる物理マシンのリソースを仮想化するレイヤを追加する.
 ハイパーバイザは仮想マシンを作成し仮想化したリソースを仮想マシンに提供する. その上でオペレーティングシステムを動作させることで, 複数のオペレーティングシステムの稼働を可能にする.
 ハイパーバイザは複数ありVMWare,KVM,Xen,Hyper-Vなどがあげられる. 本検証では, KVMとVMWareを用いた検証を行う予定である.
 \subsection{仮想環境を用いた検証方法の検討}
-仮想環境を用いた検証方法は基本的に前回のPCクラスタを用いたスケーラビリティ検証と同様の方法を採用する. (図\ref{fig:bench-method1})
+仮想環境を用いた検証方法は基本的に前回\cite{SHOSHI1}のPCクラスタを用いたスケーラビリティ検証と同様の方法を採用する. (図\ref{fig:bench-method1})
 つまり, 並列アクセス用のクライアントクラスタとサーバー用のクラスタを用意する. 今回は, server01-03をクライアントクラスタ用の仮想環境に, server04をサーバークラスタ用の仮想環境として用いる.
 \begin{figure}[!htbp]
 \begin{center}
 	\includegraphics[scale=0.35]{bench-method1.pdf}
 \end{center}
 そこで, 本研究では初めに仮想環境を管理するツールを開発し, 検証環境の構築に利用する.
 \subsubsection{libvirt}
 libvirtとは, 複数ある仮想環境においてノードをリモートより共通で十分に安全な安定した管理方法を提供するライブラリである. この場合のノードは１台の物理的なマシンであり, ドメインは仮想マシンを指す.
 様々な言語とハイパーバイザ, ユーザーの認証方法に対応している.
 \begin{enumerate}
-\item{ハイパーバイザ}
+\item{ハイパーバイザ}\\
 KVM,Xen,VirtualBox,VMWare,etc..
-\item{プログラミング言語}
+\item{プログラミング言語}\\
 C,Python,C\#,Java,Perl,Ruby,PHP,etc..
 \end{enumerate}
 libvirtを用いた仮想化管理ツールは複数存在している, 以下にその一例を示す.
 \begin{table}[!htbp]
 \caption{libvirtを用いた管理ツール}
 \begin{center}
 \begin{tabular}{|c|c|} \hline
 virsh & CUI  \\ \hline
 virt-manager & GUI \\ \hline
-oVirt & Web \\ \hline
+oVirt,AbiCloud,etc... & Web \\ \hline
 \end{tabular}
 \end{center}
 \end{table}
 {\tt libvirt}を用いた管理ツールは複数存在するが, インストールが複雑であり, 必要のない機能を実装してることが多い. そこで, 導入が用意であり, かつ十分な機能を提供するウェブ上の管理ツールを実装する.
 \subsubsection{webvirt}
 \item{ストレージプールの管理}
 \item{ネットワークの管理}
 \end{itemize}
 また, シングルノードのみを管理する目的で開発されているため, ライブマイグレーションなどの機能は実装していない.
 \section{まとめ}
-本研究では, 構築した非破壊的構造を用いたCMSのスケーラビリティ検証環境を構築するために, ウェブ上の管理ツールであるwebvirtの実装を行った. また, 非破壊的構造の応用例として並列に読み書きを行うことの出来るバランス木を用いた二分木辞書の実装例を示した.
+本研究では, 開発した非破壊的構造を用いたCMSのスケーラビリティ検証を行うため, 仮想環境における検証環境の構築方法について検討した．
-次回は, 構築した仮想環境によるスケーラビリティの検証を行う予定である.
+基本的な方法は前回\cite{SHOSHI1}と同様に行い, クライアントクラスタとサーバークラスタの仮想環境を構築する必要がある.
+仮想環境下では, 仮想マシンによる物理リソースの取り合いを防ぐため, 仮想マシンのリソースを予約・制限しつつ構築する必要があることが分かった. 仮想マシンは複数存在するため管理が困難だと考えられ，ウェブ上の管理用ツールを開発した．
+また, 非破壊的構造の応用例として並列に読み書きを行うことの出来るバランス木を用いた二分木辞書の実装例を示した. 次回は, 構築した仮想環境によるスケーラビリティの検証を行う予定である.
 \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

Mercurial > hg > Papers > 2011 > shoshi-jssst

comparison shoshi-paper.tex @ 6:bd7d39a4e57f