# HG changeset patch # User tatsuki # Date 1414552981 -32400 # Node ID 9b65d79399ff9d264ae3b8d20b89fe2aa462e87a # Parent 4299a784ab4fa73e821865800333b4241c0e0ea8 add ver1.0 diff -r 4299a784ab4f -r 9b65d79399ff midterm.pdf Binary file midterm.pdf has changed diff -r 4299a784ab4f -r 9b65d79399ff midterm.tex --- a/midterm.tex Wed Oct 29 05:15:31 2014 +0900 +++ b/midterm.tex Wed Oct 29 12:23:01 2014 +0900 @@ -1,7 +1,7 @@ \documentclass[twocolumn,twoside,9.5pt]{jarticle} \usepackage[dvips]{graphicx} \usepackage[dvipdfm]{graphicx} -\usepackage{picins} +\usepackage{ascmac} \usepackage{fancyhdr} %\pagestyle{fancy} \lhead{\parpic{\includegraphics[height=1zw,keepaspectratio,bb=0 0 251 246]{pic/emblem-bitmap.pdf}}琉球大学主催 工学部情報工学科 中間発表予稿} @@ -26,130 +26,123 @@ \thispagestyle{fancy} \section{研究目的} -実際の業務システム等で、アカウントアカウント管理を行う際に既存のDatabaseでは、過去のversionのデータを参照するAPIが無かったり、木構造のデータ型を入れる際に面倒だったり、問題がある。\\ +実際の業務システム等で、アカウント管理を行う際に既存のDatabaseでは、過去のversionのデータを参照を行えなかったり、木構造のデータ型を入れる際に面倒だったり、問題がある。\\ そこで、当研究室ではデータの編集の際に一度木構造として保存したデータには触れず、新しく木構造を作成してデータの編集を行う非破壊的木構造を用いたデータベースであるJungleを開発している。\\ -Jungleは非破壊で過去のデータを変更しないので、過去のデータを簡単に参照できるはずである(まだ未実装)\\ -また、Jungle自体木構造データベースなので木構造をそのまま格納出来るなど様々な利点がある。\\ -その後、当研究室と共同研究を行っているSymphoniesが開発しているアカウント認証システムmaTrixにJungleを組み込む +Jungleは非破壊で過去のデータを変更しないので、過去のデータを簡単に参照できたり、Jungle自体が木構造データベースなので、木構造のデータをそのまま格納出来る。\\ +本研究ではJungleに、検索API、Index、過去データの参照の実装を行い、 +その後、当研究室と共同研究を行っているSymphonies社が開発しているアカウント管理システムmaTrixにJungleを組み込む。 -\section{非破壊的木構造} -非破壊的木構造は一度構築した木構造を破壊すること無く、新しい木構造を構成することで木構造を編集する方法である。\\ -ここでは通常の破壊的木構造との違いを説明する +\section{maTrix} +maTrixとはSymphonies社が開発しているアカウント管理、許諾判定システムのことである。\\ +matrixは人、役職、役割、権限と言った木構造の組織、ポリシーファイルの２つのデータを持っている。maTrixが保持している人、役職、役割等のデータはお互いに参照している。 +ポリシーファイルは、組織の中で申請等を行った際に、どの権限によってその申請が許諾されるのかを指定している。\\ +組織のデータ、ポリシーファイル共に木構造のデータであるため、木構造のデータベースであるJungleには、そのまま格納できる。\\ +また、maTrixは、いつ、誰が、どんな申請をしたか、と言った過去の承認情報を保持するので、過去の組織のデータを参照する必要が出てくる。よって過去のデータの参照が出来るJungleと相性が良い。\\ +maTrixはデータをxml形式で出力することが可能なので、xml形式で出力されたmaTrixの人、組織等のデータをJungleに格納するために、SAXを用いて、Jungle用のxmlReaderを作成した。xmlReaderを作成したことにより、実際にmaTrixから出力されたデータをJungleに取り込み、本格的なテストが行えるようになった。 + +\section{検索APIの実装} +Jungleは、データを格納するAPIは実装されていたが、データの検索を行うAPIの実装は行われていなかった。\\ +本研究ではJava8の新機能であるlambda式を用いてデータの検索を行うfind関数の実装を行った。\\ +以下にfind関数の使い方を示したソースコードを記述する。\\ -\subsection{破壊的木構造} -破壊的木構造は、木構造を編集する際に、木構造を書き換えることにより編集を行う\\ -しかし破壊的構造では、並列環境において問題が発生し、閲覧者が読み込みを行っている際に編集者が木構造を書き換えると、閲覧者が参照を開始した時点での木構造ではなく整合性が崩れてしまう。\\ -この状態を回避するためには、木構造にアクセスする際には、木構造をロックする。\\ -しかしロックすることは、排他処理を行い、木構造を利用している処理が１つであることを保証するものであるため、並列度を下げることになってしまい、破壊的木構造は並列処理に向かないことがわかる -\newline -\newline -\newline -\newline -\newline -\newline -\begin{figure}[!htbp] - \includegraphics[scale=0.3]{jungle.pdf} - \caption{木構造の破壊的変更例} - \label{fig:dest-tree1} - \end{figure} +{\scriptsize + \begin{itembox}[l]{JungleのQuery部分のソースコード} +\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"); +\end{verbatim} +\end{itembox} +}\\ +find関数は引数にQuery、String key、String valueの3つの引数を取り、条件に一致したNodeと、そのNodeまでのPathを１つにまとめたPairのIteratorを返す。\\ +第一引数には、探索の条件を記述する関数boolean comdition(TreeNode)を定義したInterface　Queryを。 +第二、第三引数の、String key、String valueは後述するIndexを使うために使用する。\\ +{\scriptsize +\begin{itembox}[l]{Interface Queryの定義} +\begin{verbatim} +public interface Query { + boolean condition(TreeNode node); +} +\end{verbatim} +\end{itembox} +}\\ +find関数の処理の流れは、まず初めに、Indexがあるかどうかを調べる、indexがある場合はIndexを使用し探索を行う。Indexがない場合は、Indexを作成しながらTreeを全探索する。\\ +上記のJungleのQuery部分のソースコードは、"Person"というデータを持ったNodeと、そのNodeまでのPathのPairのiteratorを返す。\ +検索APIは、他に特定のNode以下に対して検索を行うfindInSubTree(Query,node,key,value)も実装した。 +\section{Indexの実装} +Jungleの探索はTreeを全探索するので、探索の計算量はO(n)となり、非常に効率が悪い。しかし、Indexを使用することで効率よく探索を行えるようになる。Indexの実装には、functionalJavaのTreeMapを使用した。\\ +TreeMapは、KeyとValueのペアを用いて赤黒木を構築する。赤黒木の長所として、ソート済み二分木の探索なので計算量がO(logN)であること、データ編集時の最悪計算量がデータ構造のうちで最善のものの１つであるので、安定した速度でデータの編集が行える。また、TreeMapはimmutableなので一度作られたTreeに対して更新が行われない、つまり新しい要素を追加した際は、新しくTreeMapを作る。なのでTreeは、各versionごとに固定のIndexを持つことが出来る、また、新しくTreeを作る際に、過去のTreeの一部を再利用するのでメモリの使用量を抑えることが出来る、ということがあげられる。\\ +Indexは各ユーザーがローカルにIndexを持つon the fly形式で実装する。\\ -\subsection{非破壊的木構造} -その一方で非破壊的木構造は、木構造を書き換えること無く編集を行うため読み書きを並列に行うことが可能である\\ -非破壊的木構造の基本的な、木の編集手順は以下の様に行われる -\begin{enumerate} - \item 変更したいノードまでのパスを求める - \item 変更したいノードを複製し、複製したノードの内容を変更する - \item 1で求めた、パス上に存在するノードをルートノードに向かってコピーする。コピーしたノードの子をコピー後のノードの子として追加する - \item 影響の無いノードは共有する -\end{enumerate} -この編集方法で、破壊的木構造の場合と同様にある時点の木構造を参照している閲覧者と、編集している編集者を考える\\ -閲覧者が木構造を参照している中、編集者が非破壊的な編集を行う、破壊的方法とは異なり、元の木構造は破壊されることは無いため編集後も整合性は崩れることはない\\ -よってロックを行う必要が無いため並列に読み書きが可能である。\\ -また、元の木構造は破壊されることが無いため、自由にコピーを作成しても構わない。すなわち、アクセスの負荷も分散させることが可能である\\ - -\newpage -\newline -\newline -\newline -\begin{figure}[!htbp] -\begin{flushleft} - \includegraphics[scale=0.28]{jungle2.pdf} -\end{flushleft} - \caption{木構造の非破壊的変更例} - \label{fig:dest-tree1} - \end{figure} -\section{functionalJava} -JungleではJava上で関数型プログラミングを行うためのFunctionalJavaを使用している。\\ -関数言語の特徴として、副作用(変数等の書き換え)がないことがあげられる\\ -ここでは後述するIndexの実装で使用したFunctionalJavaのTreeMapについて説明する\\ - -\subsection{TreeMap} -TreeMapは、FunctionalJavaに実装されているClassで、KeyとValueを用いて赤黒木を構築する\\ -赤黒木の長所として、ソート済みの二分木の探索なので計算量がO(logN)であること、最悪計算量がデータ構造のうちで最善のものの１つであるので、安定した速度でデータの編集が行えることの２つがあげられる\\ -また新しくTreeを構築する際、過去のTreeの一部を再利用するのでメモリの使用効率が良い\\ - -\section{Indexの実装} -%\subsection{Node} -%Nodeは、木構造を表現するためのコンポーネントであり、子供と辞書を保持している\\ -%辞書はTreeMapを用いて$<$String key,ByteBuffer Value$>$の組み合わせで管理されている\\ -%\newline -%\newline -%\begin{figure}[!htbp] -%\begin{flushleft} -% \includegraphics[scale=0.28]{node.pdf} -% \end{flushleft} -% \caption{木構造の非破壊的変更例} -% \label{fig:dest-tree1} -% \end{figure} -\subsection{Indexの型} -Indexのデータの型は\\TreeMap$<$String key,TreeMap\\$<$String value,List$<$Pair$<$TreeNode,NodePath$>>>>$\\となっている\\ -最初のTreeMap$<$String ,TreeMap$>$はIndexを格納するTreeMapである。\\ -このTreeMapに対しkeyでgetを行うと、対応するIndexが登録されている場合Indexを取得できる\\ -取得したIndexに対しValueでgetを行うと、valueの値を持つNodeとそのNodeまでのPathの２つをPairにまとめたものが返ってくる。\\ -Indexを使う利点として、探索の計算量が全探索のO(N)からO(logN)になることが挙げられる - -\subsection{Indexの作成} -IndexはTreeに対して、探索を行う際に作成される。\\ -Treeにおける探索の流れを以下に示す -\begin{enumerate} - \item まずindexのリストに対して探索する文字列のkeyでgetを行い、対応するIndexが登録されているかどうかを調べる - \item keyに対応するIndexが登録されている場合は、そのIndexに対しvalueでgetを行いその結果を返す。 - \item 対応するIndexが登録されていなかった場合、TreeをIndexを作りながら全探索を行い、探索結果を返す。 -\end{enumerate} - -\subsection{Indexの編集} -JungleではTreeの編集にはJungleTreeEditorを使用し、Nodeの追加、削除、値のput、deleteを行える\\ -そこでJungleTreeEditorの機能を拡張し、Treeへの変更をIndexに反映するIndexJungleTreeEditorを作成した\\ -IndexJungleTreeEditorを使えば、Treeに加えた変更をIndexに反映することが出来る。 - -\subsection{Indexの削除} -まだ未実装\\ -これから実装を行う + \begin{itembox}[l]{Indexのデータの型} + {\scriptsize\begin{verbatim} TreeMap>>>\end{verbatim}}\\\\ + \end{itembox} + 最初のTreeMap$<$String key,TreeMap$>$はIndexを格納するTreeMapである。 + このTreeMapに対しkeyでgetを行うと、keyに対応するIndexが登録されている場合、Indexを取得できる。 + 取得したIndexに対しvalueでgetを行うと、valueの値を持つNodeと、そのNodeまでのPathの２つをPairにまとめたListが返ってくる。\\ + \\ + IndexのUpdate\\ + Indexの更新はIndexEditorを用いて行う。\\ + JungleでTreeの編集を行う際は、JungleTreeEditorを使用し、Nodeのadd、delete、値のput、deleteを行う。Treeに対して変更を加えると、それに伴い、Indexも更新する必要が出てくる。そこでJungleTreeEditorの機能を拡張し、IndexJungleTreeEditorを作成した。\\ + IndexJungleTreeEditorでは、Treeの更新と同時にIndexEditorを用いてIndexの更新も行い、Treeに対して両方の更新をCommitする。 + \begin{itembox}[l]{IndexEditorの定義} +{\scriptsize\begin{verbatim} +public interface IndexEditor { + Either + edit(TreeNode root,TransactionManager txManager, + TreeEditor editor,TreeOperationLog log, + TreeMap>>> index); +} + \end{verbatim}}\\\\ + \end{itembox} + \\ -\section{過去のversionの参照} -まだ未実装\\ -Jungleは非破壊なので、過去のversionのTreeを保持している\\ -なので簡単に参照できるはずである\\ -これから実装を行う\\ + \section{maTrixに必要なQueryの作成} + maTrixは、許諾判定を行う際に、組織構造に対してQueryを行う。 + maTrixとJungleの接続を行うにあたり、組織構造に対するQueryは必要不可欠である。\\ + 当研究ではmaTrixにJungleを接続するのに必要なQuery15個を完成させた。maTrixのQueryを実装するにあたって、問題となったのが、特定のNodeの子供に対してのindexを使った検索である。 + Indexには、Tree全体のデータが入っているのでIndexを使用した検索は必然的にTree全体に対する検索になる。\\ + この問題は、NodePathに、関数compare()を実装し解決した。 + 関数compareは引数に比較対象のNodePathを受け取り、そのPathが自分の下にあるかどうかを調べる関数である。\\ + compareを使用することにより、特定のNode下の探索を行う際、特定のNodeのPathとIndexで取ってきた結果に対し、compareを使い、フィルタリングを行うことで、Indexを用いた特定のNode下の探索を可能にした\\ +{\scriptsize + \begin{itembox}[l]{今回追加実装したcompareの定義} + \begin{verbatim} + public boolean compare(NodePath path); + \end{verbatim} + \end{itembox} +}\\ + \section{これから行うべきこと} + 性能評価\\ + IndexとmaTrixのQueryの実装が終わり、maTrixに接続する準備が整ったので、実際にmaTrixとJungleの接続を行い、既存のmaTrixとjunglemaTrixの性能を評価し、本当に早くなったのか確かめる。この時にIndexの性能も評価する。\\ + \\ + 過去のversionの参照APIの実装\\ + Jungleは、過去のversionのTreeを保持しているので、簡単に参照できるはずである。 + 過去のversionのuuidを指定して自由に過去のversionを参照できるようにする。 +\\ +\\ +Jungleの設計手法の確立\\ +Jungleは比較的自由にデータを格納することができるので、Jungleを実際に使用する際に、どこまでを一つの木として扱うか、等をまとめたJungleDBの設計手法を確立させる必要がある。\\ -\section{これから行うべきこと} -\begin{enumerate} - \item Indexの削除APIの実装 - \item 過去のversionの参照APIの実装 - \item Indexを使用した場合の性能評価 - \item Jungleのソースが大分汚くなってきたのでリファクタリング -\end{enumerate} -\begin{thebibliography}{9} + \begin{thebibliography}{9} - \bibitem{1} - 玉城将士 非破壊的木構造を用いた分散CMSの設計と実装 - \bibitem{2} - 大城信康 分散Database Jungleに関する研究 - \bibitem{3} - Eric Redmond and Jim R. Wilson 7つのデータベース7つの世界 - \end{thebibliography} + \bibitem{1} + 玉城将士 非破壊的木構造を用いた分散CMSの設計と実装 + \bibitem{2} + 大城信康 分散Database Jungleに関する研究 + \bibitem{3} + Eric Redmond and Jim R. Wilson 7つのデータベース7つの世界 + \end{thebibliography} - \end{document} + \end{document}