\documentclass[twocolumn,twoside,9.5pt]{jarticle}
\usepackage[dvipdfmx]{graphicx}
\usepackage{ascmac}
\usepackage{fancyhdr}
%\pagestyle{fancy}
\lhead{\parpic{\includegraphics[height=1zw,keepaspectratio,bb=0 0 251 246]{pic/emblem-bitmap.pdf}}琉球大学主催 工学部情報工学科 中間発表予稿}
\rhead{}
\cfoot{}

\setlength{\topmargin}{-1in \addtolength{\topmargin}{15mm}}
\setlength{\headheight}{0mm}
\setlength{\headsep}{5mm}
\setlength{\oddsidemargin}{-1in \addtolength{\oddsidemargin}{11mm}}
\setlength{\evensidemargin}{-1in \addtolength{\evensidemargin}{21mm}}
\setlength{\textwidth}{181mm}
\setlength{\textheight}{261mm}
\setlength{\footskip}{0mm}
\pagestyle{empty}
\input{dummy.tex}
\begin{document}
\title{Database Jungleに関する研究}
\author{135768K 武田和馬 {}{} 指導教員 : 河野真治}
\date{}
\maketitle
\thispagestyle{fancy} 

\section{非破壊木構造データベース}

当研究室ではデータの変更の際に過去の木構造を保存しつつ新しく木構造を作成する非破壊的木構造を用いたデータベースであるJungleを開発している。
本研究ではJungle DBをC\#で再実装を行い、Unity向けに組み込みを行う。

Jugnleの木は、子供を複数持つノードからなる。子供は順序付けられており、任意の位置で作成削除することができる。

Unityは３Dゲームエンジンである。
ゲーム構造はシーングラフを実装しており、ゲームオブジェクトの親子関係からなり、子どもを複数もつノードからなる。
Jungleはこれと同じ構造を持っているため、相性が良い。

% ので、過去の組織のデータを参照する必要が出てくる。よって過去のデータの参照が出来るJungleと相性が良い。
% これらは、XMLで記述されており、
% maTrixが保持している人、役職、役割等のデータはお互いに参照している。
% ポリシーファイルは、組織の中で申請等を行った際に、どの権限によってその申請が許諾されるのかを指定している。
% 組織のデータ、ポリシーファイル共に木構造のデータであるため、Jungleにそのまま格納できる。

\section{Unityでの問題点}

Unityではデータの保存の際にMySQL、SQlite3、PlayerPrefsといった第一正規系、第二正規系のDBがよく使われている。
しかし、図１のように木構造でゲームは構成されているため、RDB向けにノードの関係を変換する必要がある。
つまり、そのまま格納することができればスケールアウトするデータにも対応でき、データベース設計も簡略化できると考え、C\#に書き直すことにした。

PlayerPrefsとは、Unityに特化したバイナリ形式でKey,Valueで保存されるものである。

\section{Jungle-Sharpの実装}

JungleはJavaで書かれているものであったのでUnityで使うにはC\#で実装する必要があった。

\section{AtomicRefefarenceの実装}
% atomic reference問題
JavaにはAtomicRefarenceが標準であったがC\#はなかったため、AtomicReferenceのClassを新たに作った。

{\scriptsize
\begin{itembox}[l]{図1 AtomicReference.cs}
\begin{verbatim}
public class AtomicReference <T> where T : class {
  private T value;

  public AtomicReference(T value) {
    this.value = value;
  }

  public bool CompareAndSet(T newValue, T prevValue) {
    T oldValue = value;
    return (oldValue 
        !=　Interlocked.CompareExchange (ref value, newValue, prevValue));
  }
    
  public T Get() {
    return value;
  }
}
\end{verbatim}
\end{itembox}
}

CompereAndSetメソッドではInterlocked Operationを利用した。
これによりスレッドセーフな値の変更を行うことが可能になる。

\section{Listの実装}

Listを実装する際にIteratorが必要となる。
C\#にはIEnumeratorがあるのでそれを利用した。

{\scriptsize
\begin{itembox}[l]{図2 List.cs}
\begin{verbatim}
public IEnumerator<T> iterator() {
    Node<T> currentNode = head.getNext();
    while (currentNode.getAttribute() != null) {
      yield return (T)currentNode.getAttribute();
      currentNode = currentNode.getNext ();
    }
  }
\end{verbatim}
\end{itembox}
}\\

ListのforeachではIteratorを呼び出すため、一つずつ要素を返す必要がある。
yield returnステートメントを利用することで位置が保持され次に呼ばれた際に続きから値の取り出しが可能になる。

\section{ベンチマーク}

UnityではSqlite3,PlayerPrefsがデータの保存として利用される。
今回の検証はInsertを1000回行い、push(またはSave)を行うまでの時間を測定する。

使用した機材は以下の通りである。
\begin{itemize}
\item OS : Windows 10
\item CPU : Intel Core i7-4700MQ 2.4GHz
\item Unity : Unity 5.4.2f1
\end{itemize}

\begin{figure}[h]
\includegraphics[width=70mm]{pic/benchmark.pdf}
\end{figure}

Sqlite3では100msを超えてしまったため省略してある。
図3の結果よりJungleDBの速度を確認することができた。


\section{これからの作業}

Jungleは分散型のデータベースを目指しているため、MessagePackの実装を行う。
今後はサーバーとの連携も行う。
JungleはRDBと異なりデータを自由に格納することができる。
そこでデータベース設計を確立させる必要がある。

\begin{thebibliography}{9}

\bibitem{1}
玉城将士 非破壊的木構造を用いた分散CMSの設計と実装
\bibitem{2}
大城信康 分散Database Jungleに関する研究
\bibitem{3}
金川竜己 非破壊的木構造データベースJungleとその評価
\end{thebibliography}

\end{document}