# HG changeset patch # User Kazuma # Date 1476865999 -32400 # Node ID 93d15a2b6745ac836aeca676d7296bbfacde1d2d # Parent 7008af359a96f5101947198cac5d6d7c65825cc0 add section 'Jungle-Sharp implementation' and c# code. diff -r 7008af359a96 -r 93d15a2b6745 midterm.tex --- a/midterm.tex Wed Oct 19 15:12:16 2016 +0900 +++ b/midterm.tex Wed Oct 19 17:33:19 2016 +0900 @@ -29,132 +29,89 @@ \section{非破壊木構造データベース} 当研究室ではデータの変更の際に過去の木構造を保存しつつ新しく木構造を作成する非破壊的木構造を用いたデータベースであるJungleを開発している。 -Jungle DBの有効性を示すために、 本研究では検索API、Index、過去データの参照の実装を行う。 -Jungleが実用DBとしての性能を持っているかどうかを調べるために、アカウント管理システムmaTrixへ組み込み、評価を行う。 +本研究ではJungle DBをC#で再実装を行い、Unity向けに組み込みを行う。 + +Jugnleの木は、子供を複数持つノードからなる。子供は順序付けられており、任意の位置で作成削除することができる。 -Jugnleの木は、子供を複数持つノード(*図1)からなる。子供は順序付けられており、任意の位置で作成削除することができる。 -ノードには属性名と属性値の組があり、データベースのレコードとして使うことができる。Index は、このレコードの属性に -対して作成する。任意の木で、属性値に対応する複数のノード、そして必要ならば、そこまでのパスの組を返す。 -ここでパスとは、ルートから木をたどるのに必要な各ノードの子供の番号のリストである。 -\\ -\\ -\\ -\\ -\begin{figure}[h] -\includegraphics[width=2cm, bb=0 0 172 200]{node.pdf} -\end{figure} -\\\\\\ -Unityはゲーム +Unityは３Dゲームエンジンである。 +ゲーム構造はシーングラフを実装しており、ゲームオブジェクトの親子関係からなり、子共を複数もつノードからなる。 +Jungleはこれと同じ構造を持っているため、相性が良い。 + % ので、過去の組織のデータを参照する必要が出てくる。よって過去のデータの参照が出来るJungleと相性が良い。 % これらは、XMLで記述されており、 % maTrixが保持している人、役職、役割等のデータはお互いに参照している。 % ポリシーファイルは、組織の中で申請等を行った際に、どの権限によってその申請が許諾されるのかを指定している。 % 組織のデータ、ポリシーファイル共に木構造のデータであるため、Jungleにそのまま格納できる。 -\section{maTrixに必要なデータベースの構築} +\section{Jungle-Sharpの実装} + +JungleはJavaで書かれているものであったのでUnityで使うにはC#で実装する必要があった。 -組織構造は木構造なので Jungle の木構造にそのままマッピングできる。Persons, Organiations, RoleDescription の三つの木を一つのJungleの木として格納する。 -XACMLは、XMLなので木構造を持つ。XACMLは、組織構造中の人や役職を id として参照する。 -具体的な許諾では、 例えば、その人がどの組織に所属して、その役割がどの権限を持っているかを返す検索が必要となる。 -XML形式で出力されたmaTrixのデータをJungleに格納するために、SAXを用いて、Jungle用のXMLReaderを作成した。 - -\section{検索APIの設計と実装} - -図2は組織構造木から、key:valueの組が、"element":"Person"のデータの組み合わせを持ったNodeと、そのNodeまでのPathのPairのiteratorを返すQueryのAPIの例を示している。 -\verb+(TreeNode node) -> {}+ は、引数\verb+node+を持つ Java 8 のλ式である。 +\section{AtomicRefefarenceの実装} +% atomic reference問題 +JavaにはAtomicRefarenceが標準であったがC#はなかったため、AtomicReferenceのClassを新たに作った。 {\scriptsize - \begin{itembox}[l]{図2 Sample Query} +\begin{itembox}[l]{図1 AtomicReference.cs} \begin{verbatim} -Iterator> pairPersonIterator = - traverser.find((TreeNode node) -> { - String element = node.getAttributes().getString("element"); - if (element == null) - return false; - if (element.equals("Person")) - return true; - return false; -}, "element", "Person"); +public class AtomicReference 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} }\\ -\verb+find+は引数に\verb+Query+、\verb+String key+、\verb+String value+の3つを取る。\verb+key+ はIndexの対象となる属性名である。 +CompereAndSetメソッドではInterlocked Operationを利用した。 +これによりスレッドセーフな値の変更を行うことが可能になる。 -Queryは図3で定義されたinterfaceである。実行されるQuery は ノードを引数に取り、そのノードが条件に一致しているかどうかを調べるconditionという関数が定義されている必要がある。 +\section{Listの実装} + +Listを実装する際にIteratorが必要となる。 +C#にはIEnumeratorがあるのでそれを利用した。 + {\scriptsize - \begin{itembox}[l]{図3 Query interface} - \begin{verbatim} - public interface Query { - boolean condition(TreeNode node); +\begin{itembox}[l]{図2 List.cs} +\begin{verbatim} +public IEnumerator iterator() { + Node currentNode = head.getNext(); + while (currentNode.getAttribute() != null) { + yield return (T)currentNode.getAttribute(); + currentNode = currentNode.getNext (); + } } - \end{verbatim} - \label{interface} - \end{itembox} +\end{verbatim} +\end{itembox} }\\ -\section{Indexの実装} -Jungleの探索はTreeの全探索の計算量はO(n)である。 -Indexの実装には、functionalJavaのTreeMapを使用し、計算量はO(logN)となる。 -これにより、前の版の木のIndexの最大共有するこが可能であり、複数の木の版すべてに対するIndexをサポートすることが可能になる。 -Jungle DB は分散DBなので、 on-th-fly つまり必要になったDBノード毎に作成する。 +ListのforeachではIteratorを呼び出すため、一つずつ要素を返す必要がある。 +yield returnステートメントを利用することで位置が保持され次に呼ばれた際に続きから実行が可能になる。 \newpage -{\scriptsize - \begin{itembox}[l]{図4 Indexの型} - \begin{verbatim} -TreeMap>>> index; -\end{verbatim} - \end{itembox} -}\\ -図4にはJungleDBにおけるIndexの型を記述した -Jungleでは、木の編集や、特定のNode下のTreeの探索、Nodeの親をたどるためには全てそのNodeへのPathが必要になる、ため、IndexにもそのNodeまでのPathが必要になる。そのため、IndexのNodePathが大きなボトルネックとなっている。 - -JungleでTreeの編集を行う際は、JungleTreeEditorを使用し、子ノードのadd、delete、属性のput、deleteを行う。 -Treeに対して変更を加える時にIndexも更新も行う。 +\section{ベンチマーク} -Jungleの木の更新(commit)は、CAS(check and set*図5)を用いて atomic に行われる。競合している書き込みにの中で自分の書き込みが成功した場合に関数 \verb+success()+が成功する。IndexはCASの前に作成され -元の木と同時に更新される。 -\\ -\\ -\\ -\\ -\\ -\\ -\begin{figure}[h] -\includegraphics[width=2cm, bb=0 0 172 200]{cas.pdf} -\end{figure} - -Indexの更新は変更で影響を受けるすべてのノードに対して行う必要がある。ノードそのものが変更されなくても、パスが影響を受ける場合には、そのノードも更新する必要がある。(*図6) -\\ -\\ -\\ -\\ -\begin{figure}[h] -\includegraphics[width=2cm, bb=0 0 160 200]{path.pdf} -\end{figure} - - - -\newpage -\section{特定のNode下のTreeに対するIndexを用いた検索} - -特定のノードの下のTreeに対する検索は、比較対象のパスを使って、自分のパス比較すれば良い。Index を使用して対象を絞ってから比較を行う。 -ノードの下の木が小さいことが予測される場合は、Indexを使用しないほうが良い性能が得られる場合もある。 +UnityではSqlite3,PlayerPrefsがデータの保存として利用される。 +今回の検証はInsertを10000回行ったのち、push(またはSave)を行い時間、メモリ使用量を測定する。 \section{これからの作業} -実際にmaTrixとJungleの接続を行い、既存のmaTrixとJunglemaTrixの性能を評価する。 - -Jungleは、過去のversionのTreeを保持しているので、 -過去のversionのuuidを指定して自由に過去のversionを参照できるようにする。 - -JungleはRDBと異なり木構造のデータを自由に格納することができる。それゆえ木構造の設計の自由度は大きい。 -しかし、変更は木が大きいほどルートに集中してしまう。木の分割を行うと、分割した木の間の同期は version -を介して行う間接的なものとなる。なので、JungleDBの設計手法を確立させる必要がある。 - -本研究は、PCIホールディングス株式会社と株式会社Symphonyとの共同研究である。 +Jungleは分散型のデータベースを目指している。 +そこに必要なMessagePackの実装を行う。 +JungleはRDBと異なりデータを自由に格納することができる。 +そこでデータベース設計を確立させる必要がある。 \begin{thebibliography}{9} @@ -162,6 +119,8 @@ 玉城将士 非破壊的木構造を用いた分散CMSの設計と実装 \bibitem{2} 大城信康 分散Database Jungleに関する研究 +\bibitem{3} +金川竜己 非破壊的木構造データベースJungleとその評価 \end{thebibliography} \end{document}