Mercurial > hg > Papers > 2011 > shoshi-jssst
comparison shoshi-paper.tex @ 5:bb4327f3c4c4
format fix
author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
---|---|
date | Mon, 08 Aug 2011 18:03:18 +0900 |
parents | d779b8753c55 |
children | bd7d39a4e57f |
comparison
equal
deleted
inserted
replaced
4:8a18a18d055d | 5:bb4327f3c4c4 |
---|---|
2 % | 2 % |
3 \documentclass[T]{compsoft} | 3 \documentclass[T]{compsoft} |
4 | 4 |
5 % Preamble | 5 % Preamble |
6 % | 6 % |
7 % 「コンピュータソフトウェア」誌に掲載される論文の場合,次で | 7 % 「コンピュータソフトウェア」誌に掲載される論文の場合, 次で |
8 % 巻数,号数,開始ページ,終了ページを指定する. | 8 % 巻数, 号数, 開始ページ, 終了ページを指定する. |
9 %\volNoPp{16}{5}{78}{83} | 9 %\volNoPp{16}{5}{78}{83} |
10 | 10 |
11 % ワークショップによる推薦論文の場合,ワークショップ名を指定する. | 11 % ワークショップによる推薦論文の場合, ワークショップ名を指定する. |
12 % \suisen{ワークショップ名} | 12 % \suisen{ワークショップ名} |
13 | 13 |
14 % 特集の場合,特集のタイトルを与える. | 14 % 特集の場合, 特集のタイトルを与える. |
15 % \tokushu{特集のタイトル} | 15 % \tokushu{特集のタイトル} |
16 | 16 |
17 % 大会論文の場合,\taikai で開催年を指定する.ここで指定した年から | 17 % 大会論文の場合, \taikai で開催年を指定する. ここで指定した年から |
18 % 大会の回数は計算される. | 18 % 大会の回数は計算される. |
19 \taikai{2011} | 19 \taikai{2011} |
20 | 20 |
21 % ここに,使用するパッケージを列挙する. | 21 % ここに, 使用するパッケージを列挙する. |
22 \usepackage[dvipdfm]{graphicx} | 22 \usepackage[dvipdfm]{graphicx} |
23 \usepackage{mediabb} | 23 \usepackage{mediabb} |
24 \usepackage{url} | 24 \usepackage{url} |
25 | 25 |
26 % ユーザが定義したマクロなどはここに置く.ただし学会誌のスタイルの | 26 % ユーザが定義したマクロなどはここに置く. ただし学会誌のスタイルの |
27 % 再定義は原則として避けること. | 27 % 再定義は原則として避けること. |
28 | 28 |
29 \begin{document} | 29 \begin{document} |
30 | 30 |
31 % 論文のタイトル | 31 % 論文のタイトル |
32 \title{Cassandraと非破壊的構造を用いたCMSのスケーラビリティ検証環境の構築} | 32 \title{Cassandraと非破壊的構造を用いたCMSのスケーラビリティ検証環境の構築} |
33 | 33 |
34 % 著者 | 34 % 著者 |
35 % 和文論文の場合,姓と名の間には半角スペースを入れ, | 35 % 和文論文の場合, 姓と名の間には半角スペースを入れ, |
36 % 複数の著者の間は全角スペースで区切る | 36 % 複数の著者の間は全角スペースで区切る |
37 % | 37 % |
38 \author{玉城 将士 \and 河野 真治 | 38 \author{玉城 将士 \and 河野 真治 |
39 % | 39 % |
40 % ここにタイトル英訳 (英文の場合は和訳) を書く. | 40 % ここにタイトル英訳 (英文の場合は和訳) を書く. |
41 % | 41 % |
42 \ejtitle{Constructing Scalability Evaluation Environment for CMS using Monotonic-Tree Operation and Cassandra} | 42 \ejtitle{Constructing Scalability Evaluation Environment for CMS using Monotonic-Tree Operation and Cassandra} |
43 % | 43 % |
44 % ここに著者英文表記 (英文の場合は和文表記) および | 44 % ここに著者英文表記 (英文の場合は和文表記) および |
45 % 所属 (和文および英文) を書く. | 45 % 所属 (和文および英文) を書く. |
46 % 複数著者の所属はまとめてよい. | 46 % 複数著者の所属はまとめてよい. |
47 % | 47 % |
48 \shozoku{Shoshi TAMAKI, Shinji KONO}{琉球大学理工学研究科情報工学専攻} | 48 \shozoku{Shoshi TAMAKI, Shinji KONO}{琉球大学理工学研究科情報工学専攻} |
49 {Dept. \ of Information Engineering, Ryukyu University} | 49 {Dept. \ of Information Engineering, Ryukyu University} |
50 % | 50 % |
51 % 出典情報は \shutten とすれば出力される. | 51 % 出典情報は \shutten とすれば出力される. |
52 %\shutten | 52 %\shutten |
53 % | 53 % |
54 % 受付年月日,記事カテゴリなどは自動的に生成される. | 54 % 受付年月日, 記事カテゴリなどは自動的に生成される. |
55 %\uketsuke{1999}{8}{3} | 55 %\uketsuke{1999}{8}{3} |
56 % | 56 % |
57 % その他,脚注に入れるものがあれば,\note に記述する. | 57 % その他, 脚注に入れるものがあれば, \note に記述する. |
58 %\note{脚注に入れる内容} | 58 %\note{脚注に入れる内容} |
59 } | 59 } |
60 | 60 |
61 % 全角,全角. を使わない.,<sp> .<sp> を使う. | |
62 % テ゛になっているのがある. | |
63 % 行頭の間隔は使わない | |
64 % 段落は1行空ける | |
61 % | 65 % |
62 % 和文アブストラクト | 66 % 和文アブストラクト |
63 \Jabstract{% | 67 \Jabstract{% |
64 本研究では,スケーラビリティのあるCMSを開発するために,PCクラスタを利用したスケーラビリティの検証環境を構築し,ロックフリーな木構造である非破壊的木構造・多段キャッシュ・Cassandraを用いた設計と実装を行って来た.今回は,実装したシステムのスケーラビリティを検証するため,構築したスケーラビリティの検証環境を用いてベンチマークを取り,スケーラビリティがあるか確認するために,環境構築を行った.また,非破壊的木構造をバランス木に応用し,バランス木の性能であるO(log N)を保ちつつ並列に読み・書き込みが可能である辞書アルゴリズムの提案をする. | 68 本研究では, スケーラビリティのあるCMSを開発するために, PCクラスタを利用したスケーラビリティの検証環境を構築し, ロックフリーな木構造である非破壊的木構造・多段キャッシュ・Cassandraを用いた設計と実装を行って来た. 今回は, 実装したシステムのスケーラビリティを検証するため, 構築したスケーラビリティの検証環境を用いてベンチマークを取り, スケーラビリティがあるか確認するために, 環境構築を行った. また, 非破壊的木構造をバランス木に応用し, バランス木の性能であるO(log N)を保ちつつ並列に読み・書き込みが可能である辞書アルゴリズムの提案をする. |
65 } | 69 } |
66 % | 70 % |
67 % 英文アブストラクト(大会論文には必要なし) | 71 % 英文アブストラクト(大会論文には必要なし) |
68 % \Eabstract{} | 72 % \Eabstract{} |
69 % | 73 % |
70 \maketitle | 74 \maketitle |
71 | 75 |
72 \section{はじめに} | 76 \section{はじめに} |
73 Cassandraは複数のサーバーで動作を想定した分散データベースである.本研究は,Cassandraの検証と非破壊的木構造を用いたスケーラビリティのあるCMSの設計と開発を行った. | 77 Cassandraは複数のサーバーで動作を想定した分散デデータベースある. 本研究は, Cassandraの検証と非破壊的木構造を用いたスケーラビリティのあるCMSの設計と開発を行った. |
74 非破壊的木構造を用いたCMSのとは,木構造で表すことの出来るコンテンツを編集する際に,編集元の木構造を破壊することなく編集するアルゴリズムである.これを利用してCassandra上に非破壊的木構造を構築しCMSを実装することができた.\\ | 78 非破壊的木構造を用いたCMSのとは, 木構造で表すことの出来るコンテンツを編集する際に, 編集元の木構造を破壊することなく編集するアルゴリズムである. これを利用してCassandra上に非破壊的木構造を構築しCMSを実装することができた. |
75 本研究では,開発したCMSのスケーラビリティの検証を行うため,仮想環境を用いた検証環境の構築と管理ソフトウェアを開発した. | 79 |
80 本研究では, 開発したCMSのスケーラビリティの検証を行うため, 仮想環境を用いた検証環境の構築と管理ソフトウェアを開発した. | |
76 \section{分散データベースCassandra} | 81 \section{分散データベースCassandra} |
77 Cassandraは, FaceBookが自社のために開発した分散Key-Valueストアデータベースであり,Dynamo\cite{DYNAMO}とBigTable\cite{BIGTABLE}を合わせた特徴を持っている. 2008年にオープンソースとして公開され, 2009年にApache Incubatorのプロジェクトとなった. | 82 Cassandraは, FaceBookが自社のために開発した分散Key-Valueストアデータベースであり, Dynamo\cite{DYNAMO}とBigTable\cite{BIGTABLE}を合わせた特徴を持っている. 2008年にオープンソースとして公開され, 2009年にApache Incubatorのプロジェクトとなった. |
78 2010年にはApacheのトップレベルプロジェクトとなり, 現在でも頻繁にバージョンアップが行われている. \\ | 83 2010年にはApacheのトップレベルプロジェクトとなり, 現在でも頻繁にバージョンアップが行われている. |
84 | |
79 \section{非破壊的木構造} | 85 \section{非破壊的木構造} |
80 非破壊的木構造とは,木構造を編集する際に編集元の木構造を破壊することなく,新しく木構造を構築する.新しい木構造のルートノードを置き換えることにより編集する方法である.\\ | 86 非破壊的木構造とは, 木構造を編集する際に編集元の木構造を破壊することなく, 新しく木構造を構築する. 新しい木構造のルートノードを置き換えることにより編集する方法である. |
81 非破壊的に変更することで,編集元の破壊することなく編集することが出来るため,木構造の整合性を保ちつつ変更することが可能になる. | 87 非破壊的に変更することで, 編集元の破壊することなく編集することが出来るため, 木構造の整合性を保ちつつ変更することが可能になる. |
82 \subsection{木構造の破壊的変更} | 88 \subsection{木構造の破壊的変更} |
83 従来の破壊的木構造は,存在する木構造を書き換えて編集する.以下の様な操作を行う.\\ | 89 従来の破壊的木構造は, 存在する木構造を書き換えて編集する. 以下の様な操作を行う. |
84 \begin{figure}[!htbp] | 90 \begin{figure}[!htbp] |
85 \begin{center} | 91 \begin{center} |
86 \includegraphics[scale=0.5]{dest-tree1.pdf} | 92 \includegraphics[scale=0.5]{dest-tree1.pdf} |
87 \end{center} | 93 \end{center} |
88 \caption{木構造の破壊的変更例} | 94 \caption{木構造の破壊的変更例} |
89 \label{fig:dest-tree1} | 95 \label{fig:dest-tree1} |
90 \end{figure} | 96 \end{figure} |
91 図\ref{fig:dest-tree1}の操作では,ノード$F$の内容をノード$G$に書き換える操作を行った.破壊的変更では,単純に編集したいノードを書き換えることにより行われる.この操作では,編集時に木を参照している処理がある場合,参照されている木構造を破壊するため,参照を開始した自転での木構造の整合性が破壊されるという問題が起きる.\\ | 97 |
98 図\ref{fig:dest-tree1}の操作では, ノード$F$の内容をノード$G$に書き換える操作を行った. 破壊的変更では, 単純に編集したいノードを書き換えることにより行われる. この操作では, 編集時に木を参照している処理がある場合, 参照されている木構造を破壊するため, 参照を開始した自転での木構造の整合性が破壊されるという問題が起きる. | |
92 \begin{figure}[!htbp] | 99 \begin{figure}[!htbp] |
93 \begin{center} | 100 \begin{center} |
94 \includegraphics[scale=0.4]{dest-tree2.pdf} | 101 \includegraphics[scale=0.4]{dest-tree2.pdf} |
95 \end{center} | 102 \end{center} |
96 \caption{破壊的変更の問題点} | 103 \caption{破壊的変更の問題点} |
97 \label{fig:dest-tree2} | 104 \label{fig:dest-tree2} |
98 \end{figure} | 105 \end{figure} |
99 この問題を解決するためには,木構造の操作に排他制御を取り入れてロックする必要がある.しかし,その方法ではスケーラビリティを確保できるとは考えられないため,非破壊的な変更を方法を用いて木構造を編集する. | 106 この問題を解決するためには, 木構造の操作に排他制御を取り入れてロックする必要がある. しかし, その方法ではスケーラビリティを確保できるとは考えられないため, 非破壊的な変更を方法を用いて木構造を編集する. |
100 \subsection{木構造の非破壊的変更} | 107 \subsection{木構造の非破壊的変更} |
101 木構造の非破壊的な変更は,編集元の木構造を破壊せずに編集を行う,編集の様子を図\ref{fig:mono-tree1}に示す.図\ref{fig:mono-tree1}では図\ref{fig:dest-tree1}と同様にノード$F$の内容をノード$G$に書き換える処理を行っている.\\ | 108 木構造の非破壊的な変更は, 編集元の木構造を破壊せずに編集を行う, 編集の様子を図\ref{fig:mono-tree1}に示す. 図\ref{fig:mono-tree1}では図\ref{fig:dest-tree1}と同様にノード$F$の内容をノード$G$に書き換える処理を行っている. |
109 | |
102 \begin{figure}[!htbp] | 110 \begin{figure}[!htbp] |
103 \begin{center} | 111 \begin{center} |
104 \includegraphics[scale=0.4]{mono-tree1.pdf} | 112 \includegraphics[scale=0.4]{mono-tree1.pdf} |
105 \end{center} | 113 \end{center} |
106 \caption{木構造の非破壊的変更例} | 114 \caption{木構造の非破壊的変更例} |
107 \label{fig:mono-tree1} | 115 \label{fig:mono-tree1} |
108 \end{figure} | 116 \end{figure} |
109 この方法での編集は以下の手順を用いて行われる. | 117 |
118 この方法での編集は以下の手順を用いて行われる. | |
110 \begin{enumerate} | 119 \begin{enumerate} |
111 \item{ルートノードであるノード$A$から編集対象であるノード$F$までのパスをコピーする.(ノード$A,C,F$をコピーする)} | 120 \item{ルートノードであるノード$A$から編集対象であるノード$F$までのパスをコピーする. (ノード$A,C,F$をコピーする)} |
112 \item{パスに含まれないノードは編集元のノードと共有する.(コピーノード$A$からノード$B$へリンクを作成する)} | 121 \item{パスに含まれないノードは編集元のノードと共有する. (コピーノード$A$からノード$B$へリンクを作成する)} |
113 \item{編集対象であるノード$F$は編集せず,コピーしたノード$F$をノード$G$へと編集する.} | 122 \item{編集対象であるノード$F$は編集せず, コピーしたノード$F$をノード$G$へと編集する. } |
114 \item{木構造のルートノードをノード$A$からコピーしたノード$A$へと置き換える.} | 123 \item{木構造のルートノードをノード$A$からコピーしたノード$A$へと置き換える. } |
115 \end{enumerate} | 124 \end{enumerate} |
116 この手順では,元の木構造は破壊されることは無い,そのため木の閲覧者が存在していても閲覧している木構造の整合性が破壊されることはない. | 125 この手順では, 元の木構造は破壊されることは無い, そのため木の閲覧者が存在していても閲覧している木構造の整合性が破壊されることはない. |
117 よって,並列に読み書きを行うことが出来る. | 126 よって, 並列に読み書きを行うことが出来る. |
118 | 127 |
119 \subsection{応用例:非破壊的木構造を用いた二分木辞書} | 128 \subsection{応用例:非破壊的木構造を用いた二分木辞書} |
120 この方法の応用例として非破壊的木構造とバランス木を用いた二分木辞書を考えることが出来る.二分木辞書とは二分探索を用いたO(lg n)を保証する辞書アルゴリズムである.二分木辞書では,バランスのとれた木構造を維持するためにバランス木のアルゴリズムを利用する. | 129 |
121 これらのアルゴリズムと非破壊的木構造を組み合わせることにより,並列に読み書きを行うことが出来る辞書を作成することが出来る. | 130 この方法の応用例として非破壊的木構造とバランス木を用いた二分木辞書を考えることが出来る. 二分木辞書とは二分探索を用いたO(lg n)を保証する辞書アルゴリズムである. 二分木辞書では, バランスのとれた木構造を維持するためにバランス木のアルゴリズムを利用する. |
122 また,この辞書アルゴリズムの利点として辞書全体のコピーにかかる計算量がO(1)で済むことも利点の一つである. | 131 これらのアルゴリズムと非破壊的木構造を組み合わせることにより, 並列に読み書きを行うことが出来る辞書を作成することが出来る. |
132 また, この辞書アルゴリズムの利点として辞書全体のコピーにかかる計算量がO(1)で済むことも利点の一つである. | |
123 \subsubsection{AVL-Treeを用いた非破壊的二分木辞書} | 133 \subsubsection{AVL-Treeを用いた非破壊的二分木辞書} |
124 実装例として,AVL-Treeを用いた非破壊的二分木辞書を紹介する.この辞書は読み書きがO(lg n)かつ辞書の複製のコストがO(1)で有ることを保証する. | 134 |
135 実装例として, AVL-Treeを用いた非破壊的二分木辞書を紹介する. この辞書は読み書きがO(lg n)かつ辞書の複製のコストがO(1)で有ることを保証する. | |
125 \begin{enumerate} | 136 \begin{enumerate} |
126 \item{辞書の読み込み}\\ | 137 \item{辞書の読み込み} |
127 非破壊二分木辞書の読み込みは通常の二分木と同様で,ルートノードよりキーの大小関係を比較し値を検索する.そのため,省略する. | 138 |
128 キーを検索する際に,二分木辞書で使われている木構造は破壊されることがないため,並列に行うことが出来き,スレッドセーフである. | 139 非破壊二分木辞書の読み込みは通常の二分木と同様で, ルートノードよりキーの大小関係を比較し値を検索する. そのため, 省略する. |
129 \item{辞書の書き込み}\\ | 140 キーを検索する際に, 二分木辞書で使われている木構造は破壊されることがないため, 並列に行うことが出来き, スレッドセーフである. |
130 非破壊辞書の書き込みは以下の手順で行われる. | 141 \item{辞書の書き込み} |
142 | |
143 非破壊辞書の書き込みは以下の手順で行われる. | |
131 \begin{enumerate} | 144 \begin{enumerate} |
132 \item{二分木探索より,書きこむ場所を特定する.この時,同時に通過したノードのコピーを行う.} | 145 \item{二分木探索より, 書きこむ場所を特定する. この時, 同時に通過したノードのコピーを行う. } |
133 \begin{figure}[!htbp] | 146 \begin{figure}[!htbp] |
134 \begin{center} | 147 \begin{center} |
135 \includegraphics[scale=0.4]{mono-dic1.pdf} | 148 \includegraphics[scale=0.4]{mono-dic1.pdf} |
136 \end{center} | 149 \end{center} |
137 \caption{手順1:ノードのコピーと書き込み} | 150 \caption{手順1:ノードのコピーと書き込み} |
138 \label{fig:mono-dic1} | 151 \label{fig:mono-dic1} |
139 \end{figure} | 152 \end{figure} |
140 \\ この例では,木構造に新しくノード$7$を追加する.そのため,編集元の二分木より$50,25,15$のノードをコピーする.他の影響のない$100,35$は共有する. | 153 |
141 \item{ローカルにコピーしたノードを編集し,書き込みむ} | 154 この例では, 木構造に新しくノード$7$を追加する. そのため, 編集元の二分木より$50,25,15$のノードをコピーする. 他の影響のない$100,35$は共有する. |
142 \\ 次に,コピーした木構造を編集し書き込みを行う.図\ref{fig:mono-dic1}の例ではノード$15$の右部分に新しくノード$7$を追加する. | 155 \item{ローカルにコピーしたノードを編集し, 書き込みむ} |
143 \item{コピーし編集したノードよりルートノードまでを走査し,木の回転が必要な場合は回転させる.} | 156 |
157 次に, コピーした木構造を編集し書き込みを行う. 図\ref{fig:mono-dic1}の例ではノード$15$の右部分に新しくノード$7$を追加する. | |
158 \item{コピーし編集したノードよりルートノードまでを走査し, 木の回転が必要な場合は回転させる. } | |
144 \begin{figure}[!htbp] | 159 \begin{figure}[!htbp] |
145 \begin{center} | 160 \begin{center} |
146 \includegraphics[scale=0.4]{mono-dic2.pdf} | 161 \includegraphics[scale=0.4]{mono-dic2.pdf} |
147 \end{center} | 162 \end{center} |
148 \caption{手順2:コピーした木構造のバランス} | 163 \caption{手順2:コピーした木構造のバランス} |
149 \label{fig:mono-dic2} | 164 \label{fig:mono-dic2} |
150 \end{figure} | 165 \end{figure} |
151 \\ 新しく構築した二分木のバランスさせるために木構造を追加したノードよりルートノードまで辿りバランスを確認する.図\ref{fig:mono-dic2}ではノードを$7-15-25-50$とルートへとバランスを確認し,回転が必要であるノード$50$の位置で木の回転を行う. | 166 |
152 \item{CASを用いて,ルートノードへの参照を入れ替える.} | 167 新しく構築した二分木のバランスさせるために木構造を追加したノードよりルートノードまで辿りバランスを確認する. 図\ref{fig:mono-dic2}ではノードを$7-15-25-50$とルートへとバランスを確認し, 回転が必要であるノード$50$の位置で木の回転を行う. |
153 最後に,二分木辞書がルートノードとして保持している編集元の木構造を,新しい木構造へと置き換える.この時CASを使用することによりアトミックに置き換える.他のスレッドがこの木構造を編集し置き換えていた場合,この処理は失敗する.その場合,再度,非破壊的に編集を行う. | 168 \item{CASを用いて, ルートノードへの参照を入れ替える. } |
169 最後に, 二分木辞書がルートノードとして保持している編集元の木構造を, 新しい木構造へと置き換える. この時CASを使用することによりアトミックに置き換える. 他のスレッドがこの木構造を編集し置き換えていた場合, この処理は失敗する. その場合, 再度, 非破壊的に編集を行う. | |
154 \begin{figure}[!htbp] | 170 \begin{figure}[!htbp] |
155 \begin{center} | 171 \begin{center} |
156 \includegraphics[scale=0.4]{mono-dic3.pdf} | 172 \includegraphics[scale=0.4]{mono-dic3.pdf} |
157 \end{center} | 173 \end{center} |
158 \caption{手順3:非破壊的に編集した木構造の適用} | 174 \caption{手順3:非破壊的に編集した木構造の適用} |
159 \label{fig:mono-dic2} | 175 \label{fig:mono-dic2} |
160 \end{figure} | 176 \end{figure} |
161 \end{enumerate} | 177 \end{enumerate} |
162 \item{辞書のコピー}\\ | 178 \item{辞書のコピー} |
163 非破壊辞書のコピーは,単にルートノードを共有するだけで行うことが出来る.木構造は破壊されないため,元の木構造は不変である.共有した木構造を元にローカル新しい木構造を作成していくため,問題は起きない.\\よって,この場合の計算量は定数でありO(1)である. | 179 |
180 非破壊辞書のコピーは, 単にルートノードを共有するだけで行うことが出来る. 木構造は破壊されないため, 元の木構造は不変である. 共有した木構造を元にローカル新しい木構造を作成していくため, 問題は起きない. よって, この場合の計算量は定数でありO(1)である. | |
164 \end{enumerate} | 181 \end{enumerate} |
165 この二分木辞書は主に,辞書をコピーするときに効果を発揮する. | 182 この二分木辞書は主に, 辞書をコピーするときに効果を発揮する. |
166 | 183 |
167 \section{非破壊的木構造を用いたCMS} | 184 \section{非破壊的木構造を用いたCMS} |
168 本研究では,非破壊木構造を用いてスケーラビリティのあるCMSの設計と実装を行った.\cite{SHOSHI2}本システムではコンテンツを木構造で表現する.Cassandra上に木構造を構築し,それを非破壊的に編集する.図\ref{fig:tree-cms1}に概略図を示す. | 185 |
186 本研究では, 非破壊木構造を用いてスケーラビリティのあるCMSの設計と実装を行った. \cite{SHOSHI2}本システムではコンテンツを木構造で表現する. Cassandra上に木構造を構築し, それを非破壊的に編集する. 図\ref{fig:tree-cms1}に概略図を示す. | |
169 \begin{figure}[!htbp] | 187 \begin{figure}[!htbp] |
170 \begin{center} | 188 \begin{center} |
171 \includegraphics[scale=0.2]{tree-cms1.pdf} | 189 \includegraphics[scale=0.2]{tree-cms1.pdf} |
172 \end{center} | 190 \end{center} |
173 \caption{システムのアーキテクチャ} | 191 \caption{システムのアーキテクチャ} |
174 \label{fig:tree-cms1} | 192 \label{fig:tree-cms1} |
175 \end{figure} | 193 \end{figure} |
176 \\本システムでは,Cassandra上に木構造を構築するサーバー(API Server)を設ける,サーバーの提供するAPIを用いてコンテンツを非破壊的に操作することができる. | 194 本システムでは, Cassandra上に木構造を構築するサーバー(API Server)を設ける, サーバーの提供するAPIを用いてコンテンツを非破壊的に操作することができる. |
177 WebServerはAPI Serverを利用してコンテンツを操作しコンテンツの配置を記述したレイアウトを用いてレンダリングを行い,木構造を編集する際には専用のエディタを提供する.(図\ref{fig:tree-cms2}) | 195 WebServerはAPI Serverを利用してコンテンツを操作しコンテンツの配置を記述したレイアウトを用いてレンダリングを行い, 木構造を編集する際には専用のエディタを提供する. (図\ref{fig:tree-cms2}) |
178 \begin{figure}[!htbp] | 196 \begin{figure}[!htbp] |
179 \begin{center} | 197 \begin{center} |
180 \includegraphics[scale=0.35]{tree-cms2.pdf} | 198 \includegraphics[scale=0.35]{tree-cms2.pdf} |
181 \end{center} | 199 \end{center} |
182 \caption{木構造のレンダリングと編集} | 200 \caption{木構造のレンダリングと編集} |
183 \label{fig:tree-cms2} | 201 \label{fig:tree-cms2} |
184 \end{figure} | 202 \end{figure} |
185 \\また,各段階(API Server , WebServer , Browser)で木構造のキャッシュを保持している.各段階のキャッシュは,親の木構造に対してコミット,マージ処理を行うことができ,分散レポジトリと同様の機能を提供している.こうすることでスケーラビリティを確保することが出来ると考えられる. | 203 また, 各段階(API Server , WebServer , Browser)で木構造のキャッシュを保持している. 各段階のキャッシュは, 親の木構造に対してコミット, マージ処理を行うことができ, 分散レポジトリと同様の機能を提供している. こうすることでスケーラビリティを確保することが出来ると考えられる. |
186 (図\ref{fig:tree-cms3}) | 204 (図\ref{fig:tree-cms3}) |
187 \begin{figure}[!htbp] | 205 \begin{figure}[!htbp] |
188 \begin{center} | 206 \begin{center} |
189 \includegraphics[scale=0.35]{tree-cms3.pdf} | 207 \includegraphics[scale=0.35]{tree-cms3.pdf} |
190 \end{center} | 208 \end{center} |
191 \caption{多段キャッシュとマージ処理} | 209 \caption{多段キャッシュとマージ処理} |
192 \label{fig:tree-cms3} | 210 \label{fig:tree-cms3} |
193 \end{figure} | 211 \end{figure} |
194 \section{検証環境の構築} | 212 \section{検証環境の構築} |
195 検証では,前回用いたPCクラスタがシステム更新のために使用不可になってしまったため,新しく導入されたブレードサーバーによる仮想環境において検証環境を構築する.\cite{SHOSHI1} | 213 検証では, 前回用いたPCクラスタがシステム更新のために使用不可になってしまったため, 新しく導入されたブレードサーバーによる仮想環境において検証環境を構築する. \cite{SHOSHI1} |
196 仮想環境のホストとして利用するサーバーを表\ref{tab:bldsv-info}に示す. | 214 仮想環境のホストとして利用するサーバーを表\ref{tab:bldsv-info}に示す. |
197 \begin{table}[!htbp] | 215 \begin{table}[!htbp] |
198 \caption{検証環境に用意したサーバー} | 216 \caption{検証環境に用意したサーバー} |
199 \label{tab:bldsv-info} | 217 \label{tab:bldsv-info} |
200 \begin{center} | 218 \begin{center} |
201 \begin{tabular}{|c|c|c|c|} \hline | 219 \begin{tabular}{|c|c|c|c|} \hline |
206 server04 & Xeon X5650 x2 & 130GB & KVM \\ \hline | 224 server04 & Xeon X5650 x2 & 130GB & KVM \\ \hline |
207 \end{tabular} | 225 \end{tabular} |
208 \end{center} | 226 \end{center} |
209 \end{table} | 227 \end{table} |
210 \subsection{仮想環境} | 228 \subsection{仮想環境} |
211 仮想化とは1つの物理マシン上にて複数のオペレーティングシステムを動作させる技術である.物理マシンにハイパーバイザと呼ばれる物理マシンのリソースを仮想化するレイヤを追加する.\\ | 229 仮想化とは1つの物理マシン上にて複数のオペレーティングシステムを動作させる技術である. 物理マシンにハイパーバイザと呼ばれる物理マシンのリソースを仮想化するレイヤを追加する. |
212 ハイパーバイザは仮想マシンを作成し仮想化したリソースを仮想マシンに提供する.その上でオペレーティングシステムを動作させることで,複数のオペレーティングシステムの稼働を可能にする.\\ | 230 ハイパーバイザは仮想マシンを作成し仮想化したリソースを仮想マシンに提供する. その上でオペレーティングシステムを動作させることで, 複数のオペレーティングシステムの稼働を可能にする. |
213 ハイパーバイザは複数ありVMWare,KVM,Xen,Hyper-Vなどがあげられる.本検証では,KVMとVMWareを用いた検証を行う予定である. | 231 ハイパーバイザは複数ありVMWare,KVM,Xen,Hyper-Vなどがあげられる. 本検証では, KVMとVMWareを用いた検証を行う予定である. |
214 \subsection{仮想環境を用いた検証方法の検討} | 232 \subsection{仮想環境を用いた検証方法の検討} |
215 仮想環境を用いた検証方法は基本的に前回のPCクラスタを用いたスケーラビリティ検証と同様の方法を採用する.(図\ref{fig:bench-method1}) | 233 仮想環境を用いた検証方法は基本的に前回のPCクラスタを用いたスケーラビリティ検証と同様の方法を採用する. (図\ref{fig:bench-method1}) |
216 つまり,並列アクセス用のクライアントクラスタとサーバー用のクラスタを用意する.今回は,server01-03をクライアントクラスタ用の仮想環境に,server04をサーバークラスタ用の仮想環境として用いる. | 234 つまり, 並列アクセス用のクライアントクラスタとサーバー用のクラスタを用意する. 今回は, server01-03をクライアントクラスタ用の仮想環境に, server04をサーバークラスタ用の仮想環境として用いる. |
217 \begin{figure}[!htbp] | 235 \begin{figure}[!htbp] |
218 \begin{center} | 236 \begin{center} |
219 \includegraphics[scale=0.35]{bench-method1.pdf} | 237 \includegraphics[scale=0.35]{bench-method1.pdf} |
220 \end{center} | 238 \end{center} |
221 \caption{PCクラスタを用いたベンチマーク方法} | 239 \caption{PCクラスタを用いたベンチマーク方法} |
222 \label{fig:bench-method1} | 240 \label{fig:bench-method1} |
223 \end{figure} | 241 \end{figure} |
224 \\今回の検証では,PCクラスタを用いるのではなく仮想環境利用する.仮想環境において複数の仮想マシンで物理マシンのリソースを共有することになるため,仮想マシン同士が物理マシンのリソースを奪い合う可能性が出てくる.リソースの奪い合いによる,仮想マシンの性能低下を防ぐため,仮想マシンのリソースを予約・制限する必要がある.(図\ref{fig:bench-method2}) | 242 今回の検証では, PCクラスタを用いるのではなく仮想環境利用する. 仮想環境において複数の仮想マシンで物理マシンのリソースを共有することになるため, 仮想マシン同士が物理マシンのリソースを奪い合う可能性が出てくる. リソースの奪い合いによる, 仮想マシンの性能低下を防ぐため, 仮想マシンのリソースを予約・制限する必要がある. (図\ref{fig:bench-method2}) |
225 仮想マシンのリソースを予約・制限すると,制限以上の性能は出なくなる.それを応用し,物理マシンのリソースの範囲内で同様の仮想マシンを構築することにより台数効果も検証できるのではないかと思われる. | 243 仮想マシンのリソースを予約・制限すると, 制限以上の性能は出なくなる. それを応用し, 物理マシンのリソースの範囲内で同様の仮想マシンを構築することにより台数効果も検証できるのではないかと思われる. |
226 \begin{figure}[!htbp] | 244 \begin{figure}[!htbp] |
227 \begin{center} | 245 \begin{center} |
228 \includegraphics[scale=0.4]{bench-method2.pdf} | 246 \includegraphics[scale=0.4]{bench-method2.pdf} |
229 \end{center} | 247 \end{center} |
230 \caption{仮想環境を用いたクラスタ環境の構築} | 248 \caption{仮想環境を用いたクラスタ環境の構築} |
231 \label{fig:bench-method2} | 249 \label{fig:bench-method2} |
232 \end{figure} | 250 \end{figure} |
233 \\以上のように仮想環境を構築し仮想環境において検証を行う.仮想環境の構築において,複数の仮想マシンを操作することが必要となる. | 251 以上のように仮想環境を構築し仮想環境において検証を行う. 仮想環境の構築において, 複数の仮想マシンを操作することが必要となる. |
234 通常,物理マシンのコンソールより個々の仮想マシンを操作する作業は効率が悪いため,管理ツールの開発を行う. | 252 通常, 物理マシンのコンソールより個々の仮想マシンを操作する作業は効率が悪いため, 管理ツールの開発を行う. |
235 \subsection{仮想化管理ツールの実装} | 253 \subsection{仮想化管理ツールの実装} |
236 仮想環境で複数の仮想マシンを操作する場合,仮想マシン個々の設定を物理マシンのコンソールより操作するのは大変困難な作業であり,仮想化管理ツールの利用が必須であると考えられる.\\ | 254 仮想環境で複数の仮想マシンを操作する場合, 仮想マシン個々の設定を物理マシンのコンソールより操作するのは大変困難な作業であり, 仮想化管理ツールの利用が必須であると考えられる. |
237 そこで,本研究では初めに仮想環境を管理するツールを開発し,検証環境の構築に利用する. | 255 そこで, 本研究では初めに仮想環境を管理するツールを開発し, 検証環境の構築に利用する. |
238 \subsubsection{libvirt} | 256 \subsubsection{libvirt} |
239 libvirtとは,複数ある仮想環境においてノードをリモートより共通で十分に安全な安定した管理方法を提供するライブラリである.この場合のノードは1台の物理的なマシンであり,ドメインは仮想マシンを指す. | 257 libvirtとは, 複数ある仮想環境においてノードをリモートより共通で十分に安全な安定した管理方法を提供するライブラリである. この場合のノードは1台の物理的なマシンであり, ドメインは仮想マシンを指す. |
240 様々な言語とハイパーバイザ,ユーザーの認証方法に対応している. | 258 様々な言語とハイパーバイザ, ユーザーの認証方法に対応している. |
241 \begin{enumerate} | 259 \begin{enumerate} |
242 \item{ハイパーバイザ}\\ | 260 \item{ハイパーバイザ} |
243 KVM,Xen,VirtualBox,VMWare,etc.. | 261 KVM,Xen,VirtualBox,VMWare,etc.. |
244 \item{プログラミング言語}\\ | 262 \item{プログラミング言語} |
245 C,Python,C\#,Java,Perl,Ruby,PHP,etc.. | 263 C,Python,C\#,Java,Perl,Ruby,PHP,etc.. |
246 \end{enumerate} | 264 \end{enumerate} |
247 libvirtを用いた仮想化管理ツールは複数存在している,以下にその一例を示す. | 265 libvirtを用いた仮想化管理ツールは複数存在している, 以下にその一例を示す. |
248 \begin{table}[!htbp] | 266 \begin{table}[!htbp] |
249 \caption{libvirtを用いた管理ツール} | 267 \caption{libvirtを用いた管理ツール} |
250 \begin{center} | 268 \begin{center} |
251 \begin{tabular}{|c|c|} \hline | 269 \begin{tabular}{|c|c|} \hline |
252 virsh & CUI \\ \hline | 270 virsh & CUI \\ \hline |
253 virt-manager & GUI \\ \hline | 271 virt-manager & GUI \\ \hline |
254 oVirt & Web \\ \hline | 272 oVirt & Web \\ \hline |
255 \end{tabular} | 273 \end{tabular} |
256 \end{center} | 274 \end{center} |
257 \end{table} | 275 \end{table} |
258 \\libvirtを用いた管理ツールは複数存在するが,インストールが複雑であり,必要のない機能を実装してることが多い.そこで,導入が用意であり,かつ十分な機能を提供するウェブ上の管理ツールを実装する. | 276 {\tt libvirt}を用いた管理ツールは複数存在するが, インストールが複雑であり, 必要のない機能を実装してることが多い. そこで, 導入が用意であり, かつ十分な機能を提供するウェブ上の管理ツールを実装する. |
259 \subsubsection{webvirt} | 277 \subsubsection{webvirt} |
260 webvirtとは,本研究室で開発した仮想環境のウェブ管理ツールである.ウェブアプリケーションフレームワークであるCakePHPとlibvirt-phpを用いて開発した.\\ | 278 {\tt webvirt}とは, 本研究室で開発した仮想環境のウェブ管理ツールである. ウェブアプリケーションフレームワークであるCakePHPとlibvirt-phpを用いて開発した. |
261 webvirtは,シンプルで十分なシングルノード上でのウェブ仮想化管理ツールを目指して開発した.インストールに必要なのはPHPが動作可能なウェブサーバー・PHP・libvirt-phpのみであり,主な機能として,以下の機能を提供する. | 279 webvirtは, シンプルで十分なシングルノード上でのウェブ仮想化管理ツールを目指して開発した. インストールに必要なのはPHPが動作可能なウェブサーバー・PHP・libvirt-phpのみであり, 主な機能として, 以下の機能を提供する. |
262 \begin{itemize} | 280 \begin{itemize} |
263 \item{VNCViewer(TightVNCViewer2)} | 281 \item{VNCViewer(TightVNCViewer2)} |
264 \item{仮想マシンのシャットダウン} | 282 \item{仮想マシンのシャットダウン} |
265 \item{仮想マシンの起動} | 283 \item{仮想マシンの起動} |
266 \item{仮想マシンの定義・変更} | 284 \item{仮想マシンの定義・変更} |
267 \item{ストレージプールの管理} | 285 \item{ストレージプールの管理} |
268 \item{ネットワークの管理} | 286 \item{ネットワークの管理} |
269 \end{itemize} | 287 \end{itemize} |
270 また,シングルノードのみを管理する目的で開発されているため,ライブマイグレーションなどの機能は実装していない. | 288 また, シングルノードのみを管理する目的で開発されているため, ライブマイグレーションなどの機能は実装していない. |
271 \section{まとめ} | 289 \section{まとめ} |
272 本研究では,構築した非破壊的構造を用いたCMSのスケーラビリティ検証環境を構築するために,ウェブ上の管理ツールであるwebvirtの実装を行った.また,非破壊的構造の応用例として並列に読み書きを行うことの出来るバランス木を用いた二分木辞書の実装例を示した. | 290 本研究では, 構築した非破壊的構造を用いたCMSのスケーラビリティ検証環境を構築するために, ウェブ上の管理ツールであるwebvirtの実装を行った. また, 非破壊的構造の応用例として並列に読み書きを行うことの出来るバランス木を用いた二分木辞書の実装例を示した. |
273 次回は,構築した仮想環境によるスケーラビリティの検証を行う予定である. | 291 次回は, 構築した仮想環境によるスケーラビリティの検証を行う予定である. |
274 | 292 |
275 \begin{adjustvboxheight} % needed only when Appendix follows | 293 \begin{adjustvboxheight} % needed only when Appendix follows |
276 \begin{thebibliography}{99} | 294 \begin{thebibliography}{99} |
277 \bibitem{BIGTABLE}{Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach | 295 \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 | 296 Mike Burrows, Tushar Chandra, Andrew Fikes, Robert E. Gruber}: Bigtable : A Distributed Storege System for Structured Data |