% Sample file for the use of compsoft style file.
%
\documentclass[T]{compsoft}

% Preamble
%
% 「コンピュータソフトウェア」誌に掲載される論文の場合，次で
% 巻数，号数，開始ページ，終了ページを指定する．
%\volNoPp{16}{5}{78}{83}

% ワークショップによる推薦論文の場合，ワークショップ名を指定する．
% \suisen{ワークショップ名}

% 特集の場合，特集のタイトルを与える．
% \tokushu{特集のタイトル}

% 大会論文の場合，\taikai で開催年を指定する．ここで指定した年から
% 大会の回数は計算される．
\taikai{2013}
\pagestyle {empty}

% ここに，使用するパッケージを列挙する．
\usepackage[dvipdfmx]{graphicx}
\usepackage{listings,jlisting}
\usepackage{url}

% ユーザが定義したマクロなどはここに置く．ただし学会誌のスタイルの
% 再定義は原則として避けること．

\begin{document}

% 論文のタイトル
\title{Data Segment の分散データベースへの応用}

% 著者
% 和文論文の場合，姓と名の間には半角スペースを入れ，
% 複数の著者の間は全角スペースで区切る
%
\author{大城 信康 \and 杉本 優 \and 河野 真治
%
% ここにタイトル英訳 (英文の場合は和訳) を書く．
%
\ejtitle{}
%
% ここに著者英文表記 (英文の場合は和文表記) および
% 所属 (和文および英文) を書く．
% 複数著者の所属はまとめてよい．
%
\shozoku{Nobuyasu OSHIRO,Yu SUGIMOTO, Shinij KONO }{琉球大学大学院理工学研究科情報工学専攻並列信頼研}%
{Dept.Concurrency Reliance Laboratory, Information Engineering Course, Faculty of Engineering Graduate School of Engineering and Science, University of the Ryukyus}
%
% 出典情報は \shutten とすれば出力される．
%\shutten
%
% 受付年月日，記事カテゴリなどは自動的に生成される．
%\uketsuke{1999}{8}{3}
%
% その他，脚注に入れるものがあれば，\note に記述する．
%\note{脚注に入れる内容}
}

%
% 和文アブストラクト
\Jabstract{%
当研究室では並列・分散プログラミングスタイルとして Data Segment, Code Segment によるプログラミング手法を提案している.
Data Segment のJava上の実装としてAliceを作成してきた。
非破壊的木構造データベースjungleの分散実装を行う際にノード間での通信が必要になる。
Aliceを用いてデータベースノード間の通信を行う利点と欠点について考察する。
}

%
% 英文アブストラクト（大会論文には必要なし)
% \Eabstract{}
%
\maketitle \thispagestyle {empty}

\section{はじめに}
当研究室では並列・分散プログラムに向いたプログラミングを目指し, データを Data Segment, タスクを Code Segment という単位で扱うプログラミングスタイルの
提案を行なっている.
Data Segment, Code Segment によるプログラミングを提供する実装として, Java による分散ネットワークフレームワーク
Alice を開発している.
Alice はノード間のトポロジー生成を提供しており, Data Segment としてデータの送受信をノード間で行うことができる.

また, 当研究室では非破壊的木構造を用いたデータベースである Jungle の開発も行なっている.
Jungle はデータを非破壊で保持することでスケーラビリティのあるデータベースを目指している.
Jungle はデータの編集を TreeOperationLog という単位で行う.
Alice を使いこの TreeOperationLog を各ノード間で送受信することでデータの分散を行うことができる.

本研究では, Alice と Jungle を用いて分散データベースの実装を行う.
さらに, 例題のアプリケーションとして掲示板を作成し, 評価を行う.

\section{分散ネットワークフレームワーク Alice}
Alice は当研究室で開発している分散管理フレームワークである.
Data Segment とCode Segment による並列・分散プログラミングを提供する.

まず, Data Segment と Code Segment についての説明を行う.

\subsection{Data Segment}
Data Segment は計算に必要なデータになる.
Alice は Data Segment を文字列の Key で管理する.
Key 毎にリストが用意され, put された順番で Data Segment は取り出され計算が行われる.
Data Segment は Data Segment Manager(以下DSM) により管理される.
DSM はノード毎にキーを持つ.
他のノードの DSM にアクセスする場合は Remote DSM 経由で行う.
Alice による分散プログラミングはこの Remote DSM の機能を使用する.

Data Segment Manager は API を提供しており, この API を通じて Data Segment のやりとりが行われる
具体的には以下の API が用意されている.
\begin{itemize}
\item \verb+void put(String key, Value val)+
\item \verb+void update(String key, Value val)+
\item \verb+void peek(Receiver receiver, String key)+
\item \verb+void take(Receiver receiver, String key)+
\end{itemize}
put は Data Segment をリストへと追加する API である.
update はリストに入っている Data Segment を更新する API である.
peek はリストに入っている Data Segment を取り出す API である.
peek により取り出された Data Segement はリストより削除されない.
take はリストに入っている Data Segment を取り出す API である.
取り出した Data Segment はリストより削除される.


\subsection{Code Segment}
Code Segment は Data Segment を受け取り計算を行うコードのことを示す.
並列プログラミングにおけるタスクにあたる.
Code Segment と Data Segment は対になっている.
Code Segment は計算に使う Data Segment のキーを登録して,  そのキー
にあたる Data Segment が用意され次第処理が実行される.
Code Segment が処理を開始するのに必要な Data Segment を Input Data Segment という.

Code Segment では Data Segment の生成を行い, put や update により新たにリストに登録することができる.
Code Segment 内で作成し登録される Data Segment は Output Data Segment と呼ばれる.

Code Segment は Input Data Segment と Output Data Segment の API を提供する(図\ref{fig:dsnadcs}).
\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.50]{figures/dsandcs.pdf}
    \caption{Data Segment と Code Segment}
    \label{fig:dsnadcs}
  \end{center}
\end{figure}



\subsection{MessagePack}
Alice における Data Segment のデータ表現には MessagePack を利用している.
MessagePack はバイナリをベースにしたシリアライズライブラリーである.
また, MessagePack のバイナリにシリアライズできる型のみで構成された Value オブジェクト
が用意されている.
MessagePack は Java の基本的な型はシリアライズすることができる.

Value オブジェクトは自己記述なデータ形式になっている.
独自のクラスでも @Message アノテーションを付けることで Value 型
へと変換することができる.
その時は MessagePack がシリアライズできる型のみをフィールドに入れなければならない.


\section{非破壊的木構造を用いたデータベース Jungle}
Jungle はスケーラビリティのある CMS の開発を目指して当研究室で開発されている非破壊的木構造データベースである.
一般的なコンテンツマネジメントシステムではブログツールや Wiki・SNS が多く, これらの
ウェブサイトの構造は大体が木構造であるため, データ構造として木構造を採用している.

ここではまず破壊的木構造と, 非破壊的木構造の説明をし, Jungle におけるデータ編集の実装について述べる.

\subsection{破壊的木構造}
破壊的木構造の編集は, 木構造で保持しているデータを直接書き換えることで行う.
図\ref{fig:destractive}は破壊的木構造の編集を表している.

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.50]{figures/destructive_tree.pdf}
    \caption{破壊的木構造の編集}
    \label{fig:destractive}
  \end{center}
\end{figure}

破壊的木構造は, 編集を行う際に木のロックを掛ける必要がある.
データを受け取ろうと木を走査するスレッドは書き換えの終了を待つ必要があり, 閲覧者が
いる場合は木の走査が終わるまで書き換えをまたなければならない.
これではスケールしないと考えられる.

\subsection{非破壊的木構造木構造}
非破壊的木構造は破壊的木構造とは違い一度作成したデータを破壊することはない.
非破壊的木構造においてデータの編集を行う場合は, root から編集のあったノードまでコピー
を行い新しく木構造を作成することで行う.
編集が行われない部分は参照をもたせる.
図\ref{fig:nondestractive}は非破壊的木構造の編集を表している.

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.50]{figures/non_destructive_tree.pdf}
    \caption{非破壊的木構造の編集}
    \label{fig:nondestractive}
  \end{center}
\end{figure}

非破壊的木構造により, 木構造を編集しながら走査することが可能となる.


\subsection{Jungle におけるデータ編集}
木の編集は, 通常 Node を書き換えるため Node の API として提供されることが多いが, Jungle で
は JungleTreeEditor を利用して行う. 
JungleTree Editor には編集するためのいくつかのメソッドが用意されており, NodePath と
呼ばれるルートノードからノードまでのマスを指定することでノードが編集される.
NodePath は, ルートノードからスタートし, ノードの子供の場所を次々に指定していくことで編集対象
のノードの場所を表す(図\ref{fig:nodepath}).

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.50]{figures/nodepath.pdf}
    \caption{NodePath}
    \label{fig:nodepath}
  \end{center}
\end{figure}

Tree 編集の API として次の4つが用意されている.
\begin{itemize}
\item \verb+addNewChildAt(NodePath _path,int _pos)+
\item \verb+deleteChildAt(NodePath _path,int _pos)+
\item \verb+putAttribute(NodePath _path,+\\
\verb+String _key,ByteBuffer _value)+
\item \verb+deleteAttribute(NodePath _path,+\\
\verb+String _key)+
\end{itemize}

\subsubsection{addNewChildAt}
NodePath で指定された Node に子供となる Node を追加するAPIである.
pos で指定された番号に子供として追加を行う.

\subsubsection{deleteChildAt}
NodePath と pos により指定される Node を削除する API である.

\subsubsection{putAttribute}
Node に attribute を追加する API である.
文字列をキーにして ByteBuffer によりデータを保持する.

\subsubsection{deleteAttribute}
NodePath により指定される Node の attribute を削除する API である.
削除する attribute は文字列のキーで指定する.

\subsection{TreeOperationLog}
上記の API を使用すると Editor 内部では NodeOperation として順次つまれていき, 最終
的に commit されることで編集が行われる.
複数の NodeOperation の集まりを TreeOperationLog といい, これが編集の単位となる.
例えば, 後述する掲示板の実装では1つの書き込みに対して1つの Node を作成し, attribute を
もたせている.
その時のログは次のようになる.

\begin{verbatim}
[APPEND_CHILD:<-1>:pos:1]
[PUT_ATTRIBUTE:<-1,1>:key:author,value:oshiro]
[PUT_ATTRIBUTE:<-1,1>:key:mes,value:hello]
[PUT_ATTRIBUTE:<-1,1>:key:key,value:hoge]
[PUT_ATTRIBUTE:<-1,1>:key:timestamp,value:0]
\end{verbatim}

大文字の英字は実行した API を表す.
<>により囲まれている数値は NodePath を示す.
NodePath の後ろは posision や attribute の情報を表している.
NodeOperation と NodePath の組み合わせを TreeOperation として扱い, それらいくつか集まりが TreeOperationLog となる.

\section{Alice を用いた Jungle の分散実装}
Alice を用いた Jungle のデータ分散は, 上記の TreeOperationLog を Data Segment として扱うことで行える.
そのために必要なことは以下となる.
\begin{itemize}
\item TreeOperationLog を MessagePack によりシリアライズ
\item TreeOperationLog を扱う Data Segment の作成
%\item Data Segment として受け取った TreeOperationLog の Jungle への適応
\end{itemize}


\subsection{TreeOperationLog の MessagePack によるシリアライズ}
TreeOperationLog はそのまま MessagePack でシリアライズすることはできない.
TreeOperationLog は TreeOperation をフィールドに List として保持していた.
フィールドとして保持しているものは全て MessagePack でシリアライズできるものに
しなけれならない.
そこで, フィールドで保持しているもの Value 型に変換するための Container クラス
作成をそれぞれ行った.
ログに関連するクラス全てをシリアライズするクラスを行った後に, それら全てをまとめる 
DefaultTreeOperationLogContainer クラスの作成を行った.
このクラスは TreeOperationLog を Value 型へと変換しフィールド変数で保持する.
実際に TreeOperationLog のシリアライズを行うソースを次に示す.

%\begin{lstlisting}[label=unconvert, caption=TreeOperationLog のシリアライズ]
\begin{verbatim}
public void unconvert(Iterable
  <TreeOperation> _log) throws IOExceptio{
 MessagePack msgpack = new MessagePack();
 List<Value> list 
  = new LinkedList<Value>();
 for(TreeOperation op : _log) {
   NodeOperation nOp 
    = op.getNodeOperation();
   NodePath nPath 
    = op.getNodePath();
   DefaultTreeOperation treeOp 
  = new DefaultTreeOperation(nPath, nOp);
   DefaultTreeOperationContainer c
   = new DefaultTreeOperationContainer();
   c.unconvert(treeOp);
   Value v = msgpack.unconvert(c);
   list.add(v);
 }
 Value listValue 
 = msgpack.unconvert(list);
 logValue = listValue; // field variable
}
\end{verbatim}
%\end{lstlisting}

List で保持していた TreeOperation を List<Value> へと変換させている.
また, TreeOperationLog の保持だけでなく, 編集した木の名前やリビジョン番号, 変更を行ったノードの情報を
ノードの名前といった情報も保持するようにした.
DefaultTreeOperationLogContainer により, TreeOperationLog を Data Segment へと put することができる.

\subsection{ログを扱う Data Segment}
Alice の各ノードは "log", "childLog" というキーでログを扱う(図\ref{fig:topology}).

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.50]{figures/alice_topology.pdf}
    \caption{形成されるトポロジーと Data Segment}
    \label{fig:topology}
  \end{center}
\end{figure}

"log" にはそのノードが行った木の編集のログが入る.
また, 子供となるノードは "parent" というキーを使うことで親ノードの Data Segment Manager にアクセスすることができる.
子供となるノードは親の "log" を待ち反映する Code Segment (LogUpdateCodeSegment) を走らせており, ログが put されるとそのデータを受け取り
Code Segment の処理が行われる(図\ref{fig:putlog}).
\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.50]{figures/putLog.pdf}
    \caption{親ノードの更新を行う Code Segment}
    \label{fig:putlog}
  \end{center}
\end{figure}

"childLog" には子供となるノードが行った編集のログが入れられる.
ノードは "childLog" の Data Segment にデータが入るの待っている Code Segment が常に走らせており, 子供が行った木の編集が
"childLog" に put されることで親へとデータの伝搬が行われる(図\ref{fig:putchildlog}).
\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.50]{figures/putChildLog.pdf}
    \caption{子供のノードの更新を行う Code Segment}
    \label{fig:putchildlog}
  \end{center}
\end{figure}


\subsection{Merge algorithm の設計}
Jungle はログの衝突が起きた場合に, Merge を行うことで衝突を解決する.
今回実装した掲示板における Merge algorithm は単純な実装である.
書き込みのタイムスタンプと既に書き込まれたデータのタイムスタンプを比べ, ソートを行う.

掲示板においての Merge に関してはそれで十分である.
しかし, ブログや Wiki といった CMS を設計するさいにはもっと複雑な Merge になる.
どのように Merge algorithm を実装していくかはよく考えて行かなければならない.


\section{Cassandra との比較}
Cassandra は複数のサーバで動作を想定した分散データベースである.
Cassandra は分散 Key-Value ストアデータベースであり, Dynamo\cite{DYNAMO}とBigTable\cite{BIGTABLE}を合わせた
特徴を持っている.
データの Read と Write に対して Consistency Level を設定することができる.
Write に関してはデータの書き込みが全体, 過半数, もしくは1つのノードに書き込まれたかどうかの整合性の設定ができる.
Read に関しては最初にデータを持っていたノードか, 全体を検索して最新のタイムスタンプを確認するかといった整合性の設定ができる.
Consistency Level にもよるがつまり Cassandra はデータについて複数のノードに問い合わせいることになる.

\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.50]{figures/cassandra.pdf}
    \caption{Cassandra におけるデータの更新・読み込み}
    \label{fig:cassandra}
  \end{center}
\end{figure}


\subsection{Jungle のデータ要求}
Jungle ではデータの要求が行われた場合, 手元にあるデータを返す.
データの編集が行われた場合は, 他ノードへとログを伝搬していく(図\ref{fig:distribute_jungle}).
\begin{figure}[htpb]
  \begin{center}
    \includegraphics[scale=0.60]{figures/distribute_jungle.pdf}
    \caption{Jungle のデータ伝搬}
    \label{fig:distribute_jungle}
  \end{center}
\end{figure}

この時, 別のログと衝突が起きた場合は衝突を検知したノードが Merge を行う.
その後 Merge を行ったログをまた他ノードへと伝搬させていく.

Jungle は非破壊により過去のデータを持っているため Merge を行うことができる.
それにより最新のデータでなくてもデータを返すことができ, それがスケーラビリティ
に繋がると考えている.

\section{掲示板の作成}



\subsection{評価}


\section{まとめ}


\nocite{*}
\bibliographystyle{junsrt}
\bibliography{jssst}
\end{document}