Mercurial > hg > Papers > 2016 > kazuma-midterm

comparison midterm.tex @ 13:03e97e769bb0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix
author Kazuma
date Fri, 21 Oct 2016 22:32:20 +0900
parents 202092f0f309
children 87907fc91f62
comparison
equal deleted inserted replaced
12:202092f0f309 13:03e97e769bb0
26 \maketitle 26 \maketitle
27 \thispagestyle{fancy} 27 \thispagestyle{fancy}
28 28
29 \section{非破壊木構造データベース} 29 \section{非破壊木構造データベース}
30 30
31 当研究室ではデータの変更の際に過去の木構造を保存しつつ新しく木構造を作成する非破壊的木構造を用いたデータベースであるJungleを開発している\cite{1}。 31 当研究室ではデータの変更の際に過去の木構造を保存する非破壊木構造データベースであるJungleを開発している\cite{1}。
32 32
33 本研究ではJungleの実用例として、ゲームのバックエンドとして利用出来るデータベースとしてJungle DBをC\#で再実装を行い、Unity向けに組み込みを行う。 33 本研究ではJungleをUnityを用いたネットワークゲームで使用する方法を提案する。
34 データベースとしてJungle DBをC\#で再実装を行い、Unity向けに組み込みを行う。
34 35
35 Jugnleの木は、子供を複数持つノードからなる。子供は順序付けられており、任意の位置で作成削除することができる。 36 Jugnleの木は、子供を複数持つノードからなる。子供は順序付けられており、任意の位置で作成削除することができる。
37 ノードは属性名と属性値の組からなる表を持つ。
36 38
37 Unityは３Dゲームエンジンである。 39 \section{UnityでのDBの取り扱い}
38 ゲーム構造はシーングラフに類似している。
39 ゲームシーンに子ノードのゲーム要素(GameObject)があり、その要素自身も親子関係になっている。
40 Jungleはこれと同じ構造を持っているため、相性が良い。
41 40
42 % ので、過去の組織のデータを参照する必要が出てくる。よって過去のデータの参照が出来るJungleと相性が良い。 41 Unityは3Dゲームエンジンで、ゲームを構成する要素(Object)をC\#で制御する。
43 % これらは、XMLで記述されており、 42 Objectは一つのゲームのシーン(一画面の状況)の中で木構造を持つ。
44 % maTrixが保持している人、役職、役割等のデータはお互いに参照している。 43 これをシーングラフと言う。
45 % ポリシーファイルは、組織の中で申請等を行った際に、どの権限によってその申請が許諾されるのかを指定している。 44 シーングラフをそのままJungleに格納するという手法が考えられる。
46 % 組織のデータ、ポリシーファイル共に木構造のデータであるため、Jungleにそのまま格納できる。
47 45
48 \section{Unityでの問題点} 46 JungleはJavaで書かれていたので、Unityで使うにはJungleをC\#で実装する必要がある。
47 クライアント側はC\#、サーバー側はJavaで動作するJungleを用いる。
48 Jungleの分散機構を用いてネットワークゲームに必要な通信を行う。
49 通信はMessagePackを基本に実装されている。
50 従って、C\#側でもMessagePackを用いてデータのやり取りを行いたい。
49 51
50 Unityではデータの保存の際にMySQL、SQlite3、PlayerPrefsといったDBがよく使われている。 52 Unityではデータの保存の際にSQlite3、PlayerPrefsといったDBがよく使われている。
51 しかし、木構造でゲームは構成されているため、ゲーム構造を保存するにはRDB向けにノードの関係を変換する必要がある。
52 つまり、そのまま格納することができればスケールアウトするデータにも対応でき、データベース設計も簡略化できると考え、C\#に書き直すことにした。
53
54 PlayerPrefsとは、Unityに特化したバイナリ形式でKey,Valueのみで保存されるものである。 53 PlayerPrefsとは、Unityに特化したバイナリ形式でKey,Valueのみで保存されるものである。
54 これらのDBにはObjectを直接格納することはできない。
55 また、セーブ機能に特化していてメモリ上にDBを展開するものではない。
55 56
56 \section{Jungle-Sharpの実装} 57 \section{Jungle-Sharpの実装}
57 58
58 JungleはJavaで書かれているものであったのでUnityで使うにはC\#で実装する必要があった。 59 %スムーズにできた部分を書く
59 なお、将来的にはクライアント側はC\#、サーバー側はJavaで動作させMessagePackを用いてデータのやり取りを行う。 60 %Jungleがプログラミング言語に依存しないものだというのをかくほうがいい
61 JavaとC\#はよく似た言語であり、移行はそれほど難しくはない。
62 実際Jungleの中心部分である木構造とIndexを構成する赤黒木\cite{}のコードはほぼ変更なく移行できた。
63 C\#ではインナークラスが使えないので明示的なクラスに変換する必要があった。
60 64
61 \section{AtomicRefefarenceの実装} 65 異なる部分は一つは木を変更した後、木のルートをAtomicに置き部分である。
66 もう一つは木をたどる時に使うItertorである。
67
68 %\section{AtomicRefefarenceの実装}
62 % atomic reference問題 69 % atomic reference問題
63 Jungleの木の更新(commit)は、CAS(check and set*図1)を用いて atomic に行われる。競合している書き込みにの中で自分の書き込みが成功した場合に関数 \verb+success()+が成功する。 70 Jungleの木の更新(commit)は、CAS(check and set*図1)を用いて atomic に行われる。競合している書き込みにの中で自分の書き込みが成功した場合に関数 \verb+success()+が成功する。
64 JavaにはAtomicRefarenceが標準であるがC\#はなかったため、AtomicReferenceのClassを新たに作った。 71 JavaにはAtomicRefarenceが標準であるがC\#はなかったため、AtomicReferenceのClassを新たに作った。
65 72
66 \begin{figure}[htbp] 73 \begin{itembox}[l]{AtomicReplace}
67 \includegraphics[width=8cm]{pic/cas.pdf}
68 \label{fig:cas}
69 \caption{Check and Set}
70 \end{figure}
71
72
73 \begin{itembox}[l]{ソースコード1 AtomicReference.cs}
74 \begin{verbatim} 74 \begin{verbatim}
75 public class AtomicReference <T> where T : class { 75 // C#
76 private T value; 76 public bool CompareAndSet(T newValue, T prevValue) {
77
78 public AtomicReference(T value) {
79 this.value = value;
80 }
81
82 public bool CompareAndSet(T newValue, T prevValue) {
83 T oldValue = value; 77 T oldValue = value;
84 return (oldValue 78 return (oldValue
85 != Interlocked.CompareExchange (ref value, newValue, prevValue)); 79 != Interlocked.CompareExchange (ref value, newValue, prevValue));
86 }
87
88 public T Get() {
89 return value;
90 }
91 } 80 }
81
82 // Java
83
92 \end{verbatim} 84 \end{verbatim}
93 \end{itembox} 85 \end{itembox}
94 86
95 CompereAndSetメソッドではInterlocked Operationを利用した。 87 %\section{Listの実装}
96 これによりスレッドセーフな値の変更を行うことが可能になる。 88 木やリストをたどる時にJavaではIteratorを用いる。
89 Iteratorは次の値があるかを返すboolean hasNext()と、Tという型の次の値を取ってくるT next()を持つObjectである。
90 C\#では木やリストをたどりながらyeildで次の値を返す。
97 91
98 \section{Listの実装}
99 Jungleでは、木の編集や、特定のNode下のTreeの探索、Nodeの親をたどるためには全てそのNodeへのPathが必要になる。
100 その管理をListで行っている。
101 Listを実装する際にIteratorが必要となる。
102 JavaではインナークラスでIteratorを返すが
103 \begin{itembox}[l]{ソースコード2 List.java} 92 \begin{itembox}[l]{ソースコード2 List.java}
104 \begin{verbatim} 93 \begin{verbatim}
105 public Iterator<T> iterator() { 94 public Iterator<T> iterator() {
106 return new Iterator<T>() { 95 return new Iterator<T>() {
107 Node<T> currentNode = head.getNext(); 96 Node<T> currentNode = head.getNext();
166 Sqlite3 & 100 \\ 155 Sqlite3 & 100 \\
167 PlayerPrefs & 100 \\ 156 PlayerPrefs & 100 \\
168 \end{tabular} 157 \end{tabular}
169 \end{table} 158 \end{table}
170 159
171 図3の結果よりJungleDBの速度を確認することができた。
172 160
173 \section{これからの作業} 161 \section{これからの作業}
174 162
175 Jungleは分散型のデータベースを目指しているため、MessagePackの実装を行う。 163 Jungleは分散型のデータベースを目指しているため、MessagePackの実装を行う。
176 今後はサーバーとの連携も行う。 164 今後はサーバーとの連携も行う。