\chapter{分散コンテンツマネージメントシステムの設計}

\section{はじめに}
本章では, スケーラブルなコンテンツマネージメントシステムの設計を行う.
まずはじめに, スケーラブルにする方法について考察する. 次に, 本研究で我々が提案する幾つかの方法を紹介する. 
それを用いた, 本システムの基本的なアーキテクチャについて述べる. 

\subsection{スケーラブルにするためには}
分散システムでは, 次の3つの性質は同時には成り立たない.

\begin{itemize}
\item{Consistency}
データの整合性
\item{Availability}
データの可用性
\item{Pertition-tolerance}
データの分割耐性
\end{itemize}

これはCAP定理と呼ばれる定理である. この定理を踏まえて考察する. \\ \\
スケーラブルにするのは簡単ではなくいくつか弊害がある. 例えば, データベースなどデータを取り扱うシステムに取っては, データの整合性が大事になる.
あるデータをリクエストしたとして, 異なるノードが同じデータをレスポンスすることが望ましい. しかし, そのためには, 全ノードのデータの整合性がとれている必要がある. \\
実現するためには, 以下の方法があげられる.

\begin{enumerate}
\item{データの更新を受けたノードが, 他の全ノードに通知する.（図\ref{fig:consistency_level_write_heavy}）}
\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[width=140mm]{./images/consistency_level_write_heavy.pdf}
 \end{center}
 \caption{データを他の全ノードに通知する}
 \label{fig:consistency_level_write_heavy}
\end{figure}

\item{あるデータのリクエストをノードが受けた時, 他の全ノードに最新のデータを確認する.（図\ref{fig:consistency_level_read_heavy}）}

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[width=140mm]{./images/consistency_level_read_heavy.pdf}
 \end{center}
 \caption{他の全ノードに最新のデータを確認する}
 \label{fig:consistency_level_read_heavy}
\end{figure}

\item{データの更新を受けたノードが, 過半数以上のノードに通知する. また, データのリクエストを受けたノードは, 全ノードにリクエストを送信し過半数以上の回答が得られた時点で最新と判断する}

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[width=140mm]{./images/consistency_level_read_heavy.pdf}
 \end{center}
 \caption{過半数のノードに通知, 過半数のノードの答えを採用する}
 \label{fig:consistency_level_quoram}
\end{figure}

\end{enumerate}

最初は書き込み時に負荷をかける方法で, ノードの数に応じて書き込み時の負荷は増えるが, 読み込みは全サーバーが最新のデータを保持しているためスケールする. 
二番目の方法は最初の方法と逆で, 読み込みに負荷をかける方法で, ノード数に応じて書き込みの負荷は増えるが, 書き込みはスケールする.
三番目の方法は書き込みと読み込みに半々の負荷をかけて分散する方法である. どちらにせよ, これらの分散かつ整合性を取るにはスケーラブルに出来ない部分が存在することがわかる. 
銀行などのシステムはお金が関係するため, 整合性は欠かすことが出来ない性質である. \\
\\
整合性が必須であるシステムがある中, 大して整合性が必要のないシステムについて考える. TwitterやFacebookなどはタイムラインが数分程度遅延しても全く問題の無いサービスである.
これらのSNSは, 遅延はあるものの最終的に整合性のとれたデータがタイムラインに現れる. これを, 結果整合性という.
結果整合性は, 負荷が少ない時や細かい更新をまとめて行うなど細かい工夫を入れることで実現でき負荷を軽減することも可能である.
つまり, CAP定理のConsistentcyは無視して, 以下の組み合わせをとることが出来る. 

\begin{itemize}
\item{Avaliability + Pertition-tolerance + Eventual Consistency}
\end{itemize}

この組み合わせが現在のシステムで多く利用されている方法の1つである. 
そして, 前述した三種類の方法を結果整合性になるように変更すると以下のようになると考える.

\begin{itemize}
\item{データの更新を受けたノードが一定時間ごとに, 他のノードに通知する. 最新データは自分のみに書き込む.}
\item{ノードは一定時間ごとに他のノードから更新が無いかチェックし, リクエストを受けたときは自分が保持するデータを利用する.}
\end{itemize}

\section{木構造を用いたデータ表現}
我々のシステムでは, データ構造として木構造を採用する. 一般的なコンテンツマネージメントシステムはブログツールやWiki・SNSが多い.
これらのウェブサイトの構造は大体が木構造である. \\
ウェブログはトップページとカテゴリが存在し, カテゴリの中にサブカテゴリが存在しエントリーに到達する.
このように, ウェブサイトは木構造でうまく表現できると考える, また, 木構造は並列に編集可能なデータ構造としても実装できるため, 前章で述べたマルチコア環境でのスケーラブルなアーキテクチャと相性が良い.

\newpage

\section{提案手法}
\subsection{非破壊的木構造}
非破壊的木構造は, 一度構築した木構造を破壊することなく新しい木構造を構成することで, 木構造を編集する方法である.\\
破壊的木構造と異なりロックフリーであるため, 並列に読むことが出来きるため自由にコピーを作成することが可能である.\\
よって, コピーを複数作成しアクセスを分散させることで性能を維持することが出来ると考えられる.\\
\\
通常の破壊的木構造との違いを説明する.

\subsubsection{破壊的木構造}
破壊的木構造は, 木構造を編集する際に木構造を書き換えることにより編集を実現する. 図\ref{fig:destructive_tree_modification}では, ノード6をノードAへ書き換える処理を行なっている.

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[width=100mm]{./images/destructive_tree_modification.pdf}
 \end{center}
 \caption{木構造の破壊的編集}
 \label{fig:destructive_tree_modification}
\end{figure}

この方法では, 並列環境において問題が発生する. ある時点の木構造を参照している閲覧者と編集する編集者を考える.
閲覧者が木構造を参照中に編集者が木構造を書き換えると, 閲覧者が参照を開始した時点での木構造ではく整合性は崩れている.
整合性が崩れた状態では正しい状態のコンテンツを参照することは出来なくなってしまう. (図\ref{fig:destructive_tree_modification_in_lace}) \\ \\
この状態を回避するためには, 木構造にアクセスする際は木構造をロックする. しかし, ロックすることは排他処理を行い, 木構造を利用している処理が1つであることを保証するものであるため, 並列度を下げることになる. 結果, スケーラビリティを損なってしまい本システムには破壊的木構造は向かないことが分かる.

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[width=100mm]{./images/destructive_tree_modification_in_lace.pdf}
 \end{center}
 \caption{競合状態に陥る木構造の破壊的編集}
 \label{fig:destructive_tree_modification_in_lace}
\end{figure}
 

\subsubsection{非破壊的木構造}
一方, 非破壊的木構造は, 木構造を書き換えることなく編集を行うため, 読み書きを並列に行うことが可能である. 図\ref{fig:nondestructive_tree_modification}では, 図\ref{fig:destructive_tree_modification}同様に, ノード6をノードAへ書き換える処理を行なっている.

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[width=100mm]{./images/nondestructive_tree_modification.pdf}
 \end{center}
 \caption{木構造の非破壊的編集}
 \label{fig:nondestructive_tree_modification}
\end{figure}

赤色で示したノードが新しく追加されたノードである. 非破壊的木構造の基本的な戦略は, 変更したいノードへのルートノードからのパスを全てコピーする. そして, パス上に存在しない（編集に関係のない）ノードはコピー元の木構造と共有することである. 以下にその方法を示す.

\begin{enumerate}
\item{変更したいノードまでのパスを求める. (図\ref{fig:nondestructive_tree_modification_step1})}
\item{変更したいノードをコピーし, コピーしたノードの内容を変更する.(図\ref{fig:nondestructive_tree_modification_step1}}
\item{求めたパス上に存在するノードをルートノードに向かって, コピーする. コピーしたノードに一つ前にコピーしたノードを子供として追加する.(図\ref{fig:nondestructive_tree_modification_step1}}
\item{影響のないノードをコピー元の木構造と共有する.(図\ref{fig:nondestructive_tree_modification_step1})}
\end{enumerate}

以下に図示して説明する.

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[width=95mm]{./images/nondestructive_tree_modification_step1.pdf}
 \end{center}
 \caption{ステップ1:変更したいノードまでのパスを求める.}
 \label{fig:nondestructive_tree_modification_step1}
 \begin{center}
  \includegraphics[width=95mm]{./images/nondestructive_tree_modification_step2.pdf}
 \end{center}
 \caption{ステップ2:変更したいノードをコピーし, コピーしたノードの内容を変更する.}
 \label{fig:nondestructive_tree_modification_step2}
 \begin{center}
  \includegraphics[width=95mm]{./images/nondestructive_tree_modification_step3.pdf}
 \end{center}
 \caption{ステップ3:求めたパス上に存在するノードをルートノードまでコピーする.}
 \label{fig:nondestructive_tree_modification_step3}
 \begin{center}
  \includegraphics[width=95mm]{./images/nondestructive_tree_modification_step4.pdf}
 \end{center}
 \caption{ステップ4:影響のないノードは共有する.}
 \label{fig:nondestructive_tree_modification_step4}
\end{figure}

この編集方法で破壊的木構造の場合と同様に, ある時点の木構造を参照している閲覧者と編集する編集者を考える.
閲覧者が木構造を参照している中, 編集者が非破壊的な編集を行う. しかし, 破壊的方法とは異なり, 元の木構造は破壊されることはないため編集後も整合性は崩れることはない.
(図\ref{fig:nondestructive_tree_modification_in_lace})
よって, ロックが必要なく並列に読み書きが可能であるため, スケーラブルなシステムに有用であると考えられる.
また, 元の木構造は破壊されることがないため, 自由にコピーを作成しても構わない. すなわち, アクセスの負荷も分散させることが出来るはずである.

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[width=120mm]{./images/nondestructive_tree_modification_in_lace.pdf}
 \end{center}
 \caption{並列に読み書きが可能な非破壊的木構造}
 \label{fig:nondestructive_tree_modification_in_lace}
\end{figure}


我々のシステムでは, 非破壊的木構造を採用してシステムを設計する.
\subsection{分散バージョン管理システム}
分散バージョン管理システムとは, GitやMercurialに代表される分散版管理システムである. バージョン管理システムとは, 多人数のソフトウェア開発などで利用され, 開発の変更履歴を管理するために用いる.
更新履歴を管理する対象のまとまりをレポジトリと呼ぶ.
従来の, バージョン管理システムは集中型システムであり, レポジトリを保存するサーバーが存在しローカルにチェックアウトすることで変更を加える.
変更を加えたレポジトリはチェックアウト元にコミット・マージされサーバーに更新が伝わる. 他のユーザーは, それを自身のローカルにアップデートし変更が伝搬する仕組みである. \\
一方, 分散型はローカルにクローンすることでクローン先自体が新たなレポジトリとして独立で存在できる.
よって, 同じレポジトリからクローンされた複数の新レポジトリはお互いにマージすることができる. この仕組みより, 前述した結果整合性を用いたシステムが構築できると考える.
(図\ref{fig:distributed_and_normal_repository})

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[width=170mm]{./images/distributed_and_normal_repository.pdf}
 \end{center}
 \caption{分散バージョン管理システムと集中型バージョン管理システム}
 \label{fig:distributed_and_normal_repository}
\end{figure}

\subsubsection{Push/Pull方式}
Push/Pull方式とは, 分散レポジトリで利用されているレポジトリの結合方法の1つである.
分散バージョン管理システムでのレポジトリはお互いにPush/Pullを用いて自身の更新を通知・受信することができる.\\
Pushとは, あるレポジトリが異なるレポジトリに自分の持つ更新を通知することで, Pullは, その逆の更新を他のレポジトリより受信することである.
また, 異なる履歴を持つレポジトリ同士がPush/Pullを行う時お互いの更新がしょうとする可能性が考えられる, これらの問題はマージを用いることで解決する.\\
これを我々が提案した方法に当てはめると以下のようになる.

\begin{itemize}
\item{データの更新を受けたノードが一定時間ごとに, 他のノードに結果をPushする. 最新データは自分のみに書き込む.}
\item{ノードは一定時間ごとに他のノードから更新をPullし, リクエストを受けたときは自信が保持するデータを利用する.}
\end{itemize}
この方式は, 他のノードが故障またはネットワークが分断されてもノード自身は独立して動作するためAvailabilityとPartition-toleranceがあるのではないかと考えられる.

\subsubsection{マージ}
Push/Pullする際に更新が衝突しない場合は良いが衝突する場合もある. 木構造を例に以下の状態を考える.

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[width=95mm]{./images/merge_sample_success.pdf}
 \end{center}
 \caption{変更が衝突しない場合}
 \label{fig:merge_sample_success}
\end{figure}

この状態は衝突が発生していない, なぜならPull元が編集されていないためである. 次に図\ref{fig:merge_sample_success}について考える.\\
この場合, お互いの異なる履歴をもつ木構造がマージされる場合で変更が衝突している. しかし, 一方の木構造に対する変更が, もう一方の木構造の編集と衝突していない.\\
よってこの場合は自然にマージすることが可能である.

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[width=95mm]{./images/merge_sample_success.pdf}
 \end{center}
 \caption{変更が衝突したが, 自然に解決できる場合}
 \label{fig:merge_sample_success}
\end{figure}

次の図\ref{fig:merge_sample_fail}は, 自然にマージできない場合である. 一方の変更箇所がもう一方と衝突している.

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[width=95mm]{./images/merge_sample_fail.pdf}
 \end{center}
 \caption{変更が衝突したが, 自然に解決できない場合}
 \label{fig:merge_sample_fail}
\end{figure}

衝突する場合は, マージ処理が必要である.マージ処理はお互いの変更点を検出し, 更新を自身の木構造に衝突を取り除いた状態で取り込むことである.\\
分散レポジトリでは, お互いの更新点を検出する際に変更履歴を利用することで効率よくマージを実行することが出来ると考えられため, 我々のシステムでもマージの際に木構造に対しての更新履歴を参照できるようにする.\\
マージには衝突を回避する他に, スケーラブルにするために工夫を加えることが出来る. なぜならば, 管理するコンテンツにおいて厳密なマージ処理が必要なコンテンツとそうでないコンテンツが存在するからである.\\
そのため, 我々のシステムでは単純なマージアルゴリズムのほか, プログラマがマージアルゴリズムを記述できるようにできる仕組みを導入する. 

\subsection{グラフデータベース}
グラフデータベースとはリレーショナルデータベースと異なり, グラフ構造を保存するデータベースである. 主な実装にNeo4j,OrientDB,InfiniteGraphがあるほか, TinkerPopという様々なグラフデータベースの実装の差異を吸収するためのプロジェクトも存在する.\\
グラフデータベースはプロパティグラフと呼ばれる種類のグラフを保持することが出来る. 主にソーシャルネットワークの人物関係を表すソーシャルグラフを表現するのに利用されるほか, ページランクのアルゴリズムにも利用される.

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[width=100mm]{./images/property_graph.pdf}
 \end{center}
 \caption{プロパティグラフの例}
 \label{fig:property_graph}
\end{figure}

\subsubsection{トラバース}
グラフデータベースでのデータの検索方法はトラバースと呼ばれ, グラフ上を渡り歩く方法を示すことで目的のデータを取得する.\\
トラバースは, 並列に効率よく行うことが可能であるためスケーラビリティに貢献できると考えられる. 以下にTinkerPopでのトラバース方法を示す.

\begin{lstlisting}[frame=lrbt,label=src:property_graph_traverse_tinkerpop,caption=トラバースの例,numbers=left]
graph.v(1).out('knows').out('father);
\end{lstlisting}

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[width=100mm]{./images/property_graph_traverse.pdf}
 \end{center}
 \caption{プロパティグラフのトラバース例}
\end{figure}

我々のシステムでは, トラバースを木構造の検索方法として採用する. 
木構造はグラフ構造の1つであるため効率よく検索を行うことができると考えられるからである.
なぜならば, 複数の結果が得られるようなトラバース例を考える. このとき, 

\subsection{ブラウザサイドの実装}
近年のウェブブラウザはJavaScriptでかなり複雑な処理が可能になっている. その上, HTML5の制定によりウェブストレージやウェブソケットなどのIOまでサポートされるようになる.
以下に, HTML5で実装される主なIO関連の機能を示す.

\begin{table}[!htbp]
 \caption{HTML5で実装される新機能}
 \label{tab:HTML5_functions}
 \begin{center}
  \begin{tabular}{|c||p{25zw}|} \hline
   名称 & 説明 \\ \hline \hline
   WebSocket & ウェブサーバーとウェブブラウザが相互通信するための機能. \\ \hline
   Indexed Database API & 値とオブジェクトをローカルデータベースに保存できる.  \\ \hline
   WebStorage & 値とオブジェクトの組みを保存できる, sessionStorageとlocalStorageの2種類が存在する. \\ \hline
   App Cache & キャッシュマニフェストでブラウザのキャッシュを操作できるようになる. \\ \hline
  \end{tabular}
 \end{center}
\end{table}

通常, システムの負荷はクライアントの数に応じて増加する. 我々のシステムにおいてはクライアントはウェブブラウザに相当するため, ウェブブラウザをスケーラビリティに貢献できるようにすることでかなりの効果を期待できると考えられる.

\section{全体の設計}
提案手法を用いたシステム全体の概略図を以下に示す.

\begin{figure}[!htbp]
 \begin{center}
  \includegraphics[width=150mm]{./images/basic_architecture.pdf}
 \end{center}
 \caption{システム全体の概要図}
 \label{fig:basic_architecture}
\end{figure}

本システムでは, データ構造として木構造を採用する. 各サーバー・クライアントはそれぞれ木構造が保存されており, サーバーはサーバー同士で木構造のpush/pullを行い, クライアントはサーバーと木構造のpush/pullを行う.
前述した, スケーラブルにする方法,