Mercurial > hg > Papers > 2011 > shoshi-jssst

comparison shoshi-paper.tex @ 0:50a9279c19eb

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
hg init and added section of Monotonic-Tree Modification
author Shoshi TAMAKI <shoshi@cr.ie.u-ryukyu.ac.jp>
date Sun, 07 Aug 2011 01:55:35 +0900
parents
children 600b5de23cc6
comparison
equal deleted inserted replaced
-1:000000000000 0:50a9279c19eb
1 % Sample file for the use of compsoft style file.
2 %
3 \documentclass[T]{compsoft}
4
5 % Preamble
6 %
7 % 「コンピュータソフトウェア」誌に掲載される論文の場合，次で
8 % 巻数，号数，開始ページ，終了ページを指定する．
9 %\volNoPp{16}{5}{78}{83}
10
11 % ワークショップによる推薦論文の場合，ワークショップ名を指定する．
12 % \suisen{ワークショップ名}
13
14 % 特集の場合，特集のタイトルを与える．
15 % \tokushu{特集のタイトル}
16
17 % 大会論文の場合，\taikai で開催年を指定する．ここで指定した年から
18 % 大会の回数は計算される．
19 \taikai{2011}
20
21 % ここに，使用するパッケージを列挙する．
22 \usepackage[dvipdfm]{graphicx}
23 \usepackage{mediabb}
24 \usepackage{url}
25
26 % ユーザが定義したマクロなどはここに置く．ただし学会誌のスタイルの
27 % 再定義は原則として避けること．
28
29 \begin{document}
30
31 % 論文のタイトル
32 \title{Cassandraと非破壊的構造を用いたCMSのスケーラビリティ検証環境の構築}
33
34 % 著者
35 % 和文論文の場合，姓と名の間には半角スペースを入れ，
36 % 複数の著者の間は全角スペースで区切る
37 %
38 \author{玉城 将士 \and 河野 真治
39 %
40 % ここにタイトル英訳 (英文の場合は和訳) を書く．
41 %
42 \ejtitle{Constructing Scalability Evaluation Environment for CMS using Monotonic-Tree Operation and Cassandra}
43 %
44 % ここに著者英文表記 (英文の場合は和文表記) および
45 % 所属 (和文および英文) を書く．
46 % 複数著者の所属はまとめてよい．
47 %
48 \shozoku{Shoshi TAMAKI, Shinji KONO}{琉球大学理工学研究科情報工学専攻}
49 {Dept. \ of Information Engineering, Ryukyu University}
50 %
51 % 出典情報は \shutten とすれば出力される．
52 %\shutten
53 %
54 % 受付年月日，記事カテゴリなどは自動的に生成される．
55 %\uketsuke{1999}{8}{3}
56 %
57 % その他，脚注に入れるものがあれば，\note に記述する．
58 %\note{脚注に入れる内容}
59 }
60
61 %
62 % 和文アブストラクト
63 \Jabstract{%
64 本研究では，スケーラビリティのあるCMSを開発するために，PCクラスタを利用したスケーラビリティの検証環境を構築し，ロックフリーな木構造である非破壊的木構造・多段キャッシュ・Cassandraを用いた設計と実装を行って来た．今回は，実装したシステムのスケーラビリティを検証するため，構築したスケーラビリティの検証環境を用いてベンチマークを取り，スケーラビリティがあるか確認するために，環境構築を行った．また，非破壊的木構造をバランス木に応用し，バランス木の性能であるO(log N)を保ちつつ並列に読み・書き込みが可能である辞書アルゴリズムの提案をする．
65 }
66 %
67 % 英文アブストラクト（大会論文には必要なし)
68 % \Eabstract{}
69 %
70 \maketitle
71
72 \section{はじめに}
73 　Cassandraは複数のサーバーで動作を想定した分散データベースである．本研究は，Cassandraの検証と非破壊的木構造を用いたスケーラビリティのあるCMSの設計と開発を行った．
74 非破壊的木構造を用いたCMSのとは，木構造で表すことの出来るコンテンツを編集する際に，編集元の木構造を破壊することなく編集するアルゴリズムである．これを利用してCassandra上に非破壊的木構造を構築しCMSを実装することができた．\\
75 　本研究では，開発したCMSのスケーラビリティの検証を行うため，仮想環境を用いた検証環境の構築と管理ソフトウェアを開発した．
76 \section{分散データベースCassandra}
77 Cassandraは, FaceBookが自社のために開発した分散Key-Valueストアデータベースであり，Dynamo\cite{DYNAMO}とBigTable\cite{BIGTABLE}を合わせた特徴を持っている. 2008年にオープンソースとして公開され, 2009年にApache Incubatorのプロジェクトとなった.
78 2010年にはApacheのトップレベルプロジェクトとなり, 現在でも頻繁にバージョンアップが行われている. \\
79 \section{非破壊的木構造}
80 　非破壊的木構造とは，木構造を編集する際に編集元の木構造を破壊することなく，新しく木構造を構築する．新しい木構造のルートノードを置き換えることにより編集する方法である．\\
81 非破壊的に変更することで，編集元の破壊することなく編集することが出来るため，木構造の整合性を保ちつつ変更することが可能になる．
82 \subsection{木構造の破壊的変更}
83 　従来の破壊的木構造は，存在する木構造を書き換えて編集する．以下の様な操作を行う．\\
84 \begin{figure}[!htbp]
85 \begin{center}
86 \includegraphics[scale=0.5]{dest-tree1.pdf}
87 \end{center}
88 \caption{木構造の破壊的変更例}
89 \label{fig:dest-tree1}
90 \end{figure}
91 　図\ref{fig:dest-tree1}の操作では，ノード$F$の内容をノード$G$に書き換える操作を行った．破壊的変更では，単純に編集したいノードを書き換えることにより行われる．この操作では，編集時に木を参照している処理がある場合，参照されている木構造を破壊するため，参照を開始した自転での木構造の整合性が破壊されるという問題が起きる．\\
92 \begin{figure}[!htbp]
93 \begin{center}
94 \includegraphics[scale=0.4]{dest-tree2.pdf}
95 \end{center}
96 \caption{破壊的変更の問題点}
97 \label{fig:dest-tree2}
98 \end{figure}
99 この問題を解決するためには，木構造の操作に排他制御を取り入れてロックする必要がある．しかし，その方法ではスケーラビリティを確保できるとは考えられないため，非破壊的な変更を方法を用いて木構造を編集する．
100 \subsection{木構造の非破壊的変更}
101 木構造の非破壊的な変更は，編集元の木構造を破壊せずに編集を行う，編集の様子を図\ref{fig:mono-tree1}に示す．図\ref{fig:mono-tree1}では図\ref{fig:dest-tree1}と同様にノード$F$の内容をノード$G$に書き換える処理を行っている．\\
102 \begin{figure}[!htbp]
103 \begin{center}
104 \includegraphics[scale=0.4]{mono-tree1.pdf}
105 \end{center}
106 \caption{木構造の非破壊的変更例}
107 \label{fig:mono-tree1}
108 \end{figure}
109 　この方法での編集は以下の手順を用いて行われる．
110 \begin{enumerate}
111 \item{ルートノードであるノード$A$から編集対象であるノード$F$までのパスをコピーする．（ノード$A,C,F$をコピーする）}
112 \item{パスに含まれないノードは編集元のノードと共有する．（コピーノード$A$からノード$B$へリンクを作成する）}
113 \item{編集対象であるノード$F$は編集せず，コピーしたノード$F$をノード$G$へと編集する．}
114 \item{木構造のルートノードをノード$A$からコピーしたノード$A$へと置き換える．}
115 \end{enumerate}
116 この手順では，元の木構造は破壊されることは無い，そのため木の閲覧者が存在していても閲覧している木構造の整合性が破壊されることはない．
117 よって，並列に読み書きを行うことが出来る．
118
119 \subsection{応用例：非破壊的木構造を用いた二分木辞書}
120 　この方法の応用例として非破壊的木構造とバランス木を用いた二分木辞書を考えることが出来る．二分木辞書とは二分探索を用いたO(lg n)を保証する辞書アルゴリズムである．二分木辞書では，バランスのとれた木構造を維持するためにバランス木のアルゴリズムを利用する．
121 これらのアルゴリズムと非破壊的木構造を組み合わせることにより，並列に読み書きを行うことが出来る辞書を作成することが出来る．
122 また，この辞書アルゴリズムの利点として辞書全体のコピーにかかる計算量がO(1)で済むことも利点の一つである．
123 \subsubsection{AVL-Treeを用いた非破壊的二分木辞書}
124 　実装例として，AVL-Treeを用いた非破壊的二分木辞書を紹介する．この辞書は読み書きがO(lg n)かつ辞書の複製のコストがO(1)で有ることを保証する．
125 \begin{enumerate}
126 \item{辞書の読み込み}\\
127 　非破壊二分木辞書の読み込みは通常の二分木と同様で，ルートノードよりキーの大小関係を比較し値を検索する．そのため，省略する．
128 キーを検索する際に，二分木辞書で使われている木構造は破壊されることがないため，並列に行うことが出来き，スレッドセーフである．
129 \item{辞書の書き込み}\\
130 　非破壊辞書の書き込みは以下の手順で行われる．
131 \begin{enumerate}
132 \item{二分木探索より，書きこむ場所を特定する．この時，同時に通過したノードのコピーを行う．}
133 \begin{figure}[!htbp]
134 \begin{center}
135 \includegraphics[scale=0.4]{mono-dic1.pdf}
136 \end{center}
137 \caption{手順1:ノードのコピーと書き込み}
138 \label{fig:mono-dic1}
139 \end{figure}
140 \\　この例では，木構造に新しくノード$7$を追加する．そのため，編集元の二分木より$50,25,15$のノードをコピーする．他の影響のない$100,35$は共有する．
141 \item{ローカルにコピーしたノードを編集し，書き込みむ}
142 \\　次に，コピーした木構造を編集し書き込みを行う．図\ref{fig:mono-dic1}の例ではノード$15$の右部分に新しくノード$7$を追加する．
143 \item{コピーし編集したノードよりルートノードまでを走査し，木の回転が必要な場合は回転させる．}
144 \begin{figure}[!htbp]
145 \begin{center}
146 \includegraphics[scale=0.4]{mono-dic2.pdf}
147 \end{center}
148 \caption{手順2:コピーした木構造のバランス}
149 \label{fig:mono-dic2}
150 \end{figure}
151 \\　新しく構築した二分木のバランスさせるために木構造を追加したノードよりルートノードまで辿りバランスを確認する．図\ref{fig:mono-dic2}ではノードを$7-15-25-50$とルートへとバランスを確認し，回転が必要であるノード$50$の位置で木の回転を行う．
152 \item{CASを用いて，ルートノードへの参照を入れ替える．}
153 最後に，二分木辞書がルートノードとして保持している編集元の木構造を，新しい木構造へと置き換える．この時CASを使用することによりアトミックに置き換える．他のスレッドがこの木構造を編集し置き換えていた場合，この処理は失敗する．その場合，再度，非破壊的に編集を行う．
154 \begin{figure}[!htbp]
155 \begin{center}
156 \includegraphics[scale=0.4]{mono-dic3.pdf}
157 \end{center}
158 \caption{手順3:非破壊的に編集した木構造の適用}
159 \label{fig:mono-dic2}
160 \end{figure}
161 \end{enumerate}
162 \item{辞書のコピー}\\
163 　非破壊辞書のコピーは，単にルートノードを共有するだけで行うことが出来る．木構造は破壊されないため，元の木構造は不変である．共有した木構造を元にローカル新しい木構造を作成していくため，問題は起きない．\\よって，この場合の計算量は定数でありO(1)である．
164 \end{enumerate}
165 この二分木辞書は主に，辞書をコピーするときに効果を発揮する．
166
167 \section{非破壊的木構造を用いたCMS}
168 \section{検証環境の構築}
169 本検証では，前回行ったPCクラスタによるスケーラビリティの検証環境とは異なり，ブレードサーバー上に検証環境構築する．ブレードサーバーとは
170 \subsection{仮想環境}
171 \subsection{仮想化管理ツールの実装}
172 \section{まとめ}
173
174 \end{document}