# HG changeset patch # User Shinji KONO # Date 1414584828 -32400 # Node ID 0fc8736218d46f83241faa70772692726487af59 # Parent 75e8aac9a4b51c599290010a7f1cbbafd1c2954a fix diff -r 75e8aac9a4b5 -r 0fc8736218d4 midterm.tex --- a/midterm.tex Wed Oct 29 20:05:42 2014 +0900 +++ b/midterm.tex Wed Oct 29 21:13:48 2014 +0900 @@ -20,42 +20,46 @@ \begin{document} \title{Database Jungleに関する研究} -\author{115731 金川竜己 {}{} 指導教員 : 指導教員名} +\author{115731 金川竜己 {}{} 指導教員 : 河野真治} \date{} \maketitle \thispagestyle{fancy} -\section{研究目的} +\section{非破壊木構造データベース} -当研究室ではデータの編集の際に一度木構造として保存したデータには触れず、新しく木構造を作成してデータの編集を行う非破壊的木構造を用いたデータベースであるJungleを開発している。 - +当研究室ではデータの変更の際に過去の木構造を保存しつつ新しく木構造を作成する非破壊的木構造を用いたデータベースであるJungleを開発している。 +Jungle DBの有効性を示すために、 本研究では検索API、Index、過去データの参照の実装を行う。 +Jungleが実用DBとしての性能を持っているかどうかを調べるために、アカウント管理システムmaTrixの実装と評価を行う。 -本研究ではJungleに、検索API、Index、過去データの参照の実装を行う。 -その後、Jungleが実用DBとしての性能を持っているかどうかを調べるために、当研究室と共同研究を行っているSymphonies社が開発した、アカウント管理シ -ステムmaTrixにJungleを組み込む。 +Jugnleの木は、子供を複数持つノードからなる。子供は順序付けられており、任意の位置で作成削除することができる。 +ノードには属性名と属性値の組があり、データベースのレコードとして使うことができる。Index は、このレコードの属性に +対して作成する。任意の木で、属性値に対応する複数のノード、そして必要ならば、そこまでのパスの組を返す。 +ここでパスとは、ルートから木をたどるのに必要な各ノードの子供の番号のリストである。 -\section{maTrix} -maTrixとはSymphonies社が開発した、アカウント管理、許諾判定システムのことである。 - - -maTrixは人、役職、役割、権限と言った木構造の組織、ポリシーファイルの２つのデータを持っており、maTrixが保持している人、役職、役割等のデータはお互いに参照している。 -ポリシーファイルは、組織の中で申請等を行った際に、どの権限によってその申請が許諾されるのかを指定している。 +maTrixは、アカウント管理、許諾判定システムである。 +maTrixは人、役職、役割、権限と言った木構造の組織、許諾のポリシーを決めるXACMLファイルをデータベースとして持つ。 +いつ、誰が、どんな申請をしたか、と言った過去の承認情報を保持する必要がある。 - -組織のデータ、ポリシーファイル共に木構造のデータであるため、Jungleにそのまま格納できる。 +% ので、過去の組織のデータを参照する必要が出てくる。よって過去のデータの参照が出来るJungleと相性が良い。 +% これらは、XMLで記述されており、 +% maTrixが保持している人、役職、役割等のデータはお互いに参照している。 +% ポリシーファイルは、組織の中で申請等を行った際に、どの権限によってその申請が許諾されるのかを指定している。 +% 組織のデータ、ポリシーファイル共に木構造のデータであるため、Jungleにそのまま格納できる。 - -また、maTrixは、いつ、誰が、どんな申請をしたか、と言った過去の承認情報を保持するので、過去の組織のデータを参照する必要が出てくる。よって過去のデータの参照が出来るJungleと相性が良い。 - +\section{maTrixに必要なデータベースの構築} -maTrixはデータをxml形式で出力することが出来る。 -xml形式で出力されたmaTrixのデータをJungleに格納するために、SAXを用いて、Jungle用のxmlReaderを作成した。xmlReaderを作成したことにより、実際にmaTrixから出力されたデータをJungleに取り込み、テストを行うことを可能にした。 +組織構造は木構造なので Jungle の木酵素にそのままマッピングできる。Persons, Organiations, RoleDescription の三つの木を一つのJungleの木として格納する。 +XACMLは、XMLなので木構造を持つ。XACMLは、組織構造中の人や役職を id として参照する。 +具体的な許諾では、 例えば、その人がどの組織に所属して、その役割がどの権限を持っているかを返す検索が必要となる。 +XML形式で出力されたmaTrixのデータをJungleに格納するために、SAXを用いて、Jungle用のXMLReaderを作成した。 -\section{検索APIの実装} -Jungleに対し、Treeに対して検索を行うMethod findを実装した。図1は実際にfindを行っているコードである。Treeを探索し、key:valueの組が、"element":"Person"のデータの組み合わせを持ったNodeと、そのNodeまで>のPathのPairのiteratorを返している。 -図1の引数のQueryはlambda式を用いて実装している。 +\section{検索APIの設計と実装} + +図\ref{query}は 組織構造木から、key:valueの組が、"element":"Person"のデータの組み合わせを持ったNodeと、そのNodeまで>のPathのPairのiteratorを返すQueryのAPIの例を示している。 +\verb+(TreeNode node) -> {}+ は、引数\verb+node+を持つ Java 8 のλ式である。 + {\scriptsize - \begin{itembox}[l]{図1} + \begin{itembox}[l]{Sample Query} \begin{verbatim} Iterator> pairPersonIterator = traverser.find((TreeNode node) -> { @@ -67,35 +71,29 @@ return false; }, "element", "Person"); \end{verbatim} +\label{query1} \end{itembox} }\\ -findは引数にQuery、String key、String valueの3つを取る。 -Queryはinterfaceで、図2にあるようにNodeを引数に取り、そのノードが条件に一致しているかどうかを調べるconditionという関数を定義してある。 - - +\verb+find+は引数に\verb+Query+、\verb+String key+、\verb+String value+の3つを取る。\verb+key+ はIndexの対象となる属性名である。 - - +Queryは図\ref{interface}で定義されたinterfaceである。実行されるQuery は ノードを引数に取り、そのノードが条件に一致しているかどうかを調べるconditionという関数が定義されている必要がある。 {\scriptsize - \begin{itembox}[l]{図2} + \begin{itembox}[l]{Query interface} \begin{verbatim} public interface Query { boolean condition(TreeNode node); } \end{verbatim} + \label{interface} \end{itembox} }\\ -検索APIは、他に特定のNode以下に対して検索を行うfindInSubTree(Query,node,key,value)も実装した。 - \section{Indexの実装} -Jungleの探索はTreeを全探索するので、探索の計算量はO(n)となり効率が悪い。そこで、Indexを使用することで、探索効率の向上を計った。Indexの実装には、functionalJavaのTreeMapを使用したので、Indexを使用した検索の計算量はO(logN)となる\\ -FunctionalJavaのTreeMapはimmutableなので一度作られたTreeに対して更新が行われない。つまり新しい要素を追加する際は、新しくTreeMapを作ることになるが、新しいTreeを作るときに、過去のTreeの一部を再利用するのでメモリの使用量を抑えることが出来る。 - - -Indexは各ユーザーがローカルにIndexを持つon the fly形式で実装する。 - +Jungleの探索はTreeの全探索の計算量はO(n)である。 +Indexの実装には、functionalJavaのTreeMapを使用し、計算量はO(logN)となる。 +これにより、前の版の木のIndexの最大共有するこが可能であり、複数の木の版すべてに対するIndexをサポートすることが可能になる。 +Jungle DB は分散DBなので、 on-th-fly つまり必要になったDBノード毎に作成する。 {\scriptsize \begin{itembox}[l]{図3} @@ -105,47 +103,41 @@ \end{verbatim} \end{itembox} }\\ -図3にはJungleDBにおけるIndexの型を記述した\\ +図3にはJungleDBにおけるIndexの型を記述した Jungleでは、木の編集や、特定のNode下のTreeの探索、Nodeの親をたどるためには全てそのNodeへのPathが必要になる、ため、IndexにもそのNodeまでのPathが必要になる。そのため、IndexのNodePathが大きなボトルネックとなっている。 - - - +JungleでTreeの編集を行う際は、JungleTreeEditorを使用し、子ノードのadd、delete、属性のput、deleteを行う。 +Treeに対して変更を加える時にIndexも更新も行う。 - \section{IndexJungleTreeEditorの実装} - JungleでTreeの編集を行う際は、JungleTreeEditorを使用し、Nodeのadd、delete、値のput、deleteを行う。Treeに対して変更を加えると、それに伴い、Indexも更新する必要が出てくる。そこでJungleTreeEditorの機能を拡張し、IndexJungleTreeEditorを作成した。\\ - IndexJungleTreeEditorでは、Treeの更新と同時にIndexEditorを用いてIndexの更新も行い、Treeに対して両方の更新をCommitする。この時値のPut、deleteは、Indexから対応するKey,valueを持つIndexを更新すれば良い。しかし、Nodeのadd、deleteは、行うとTreeNodeのPathがズレてしまうため、全てのIndexの全ての値を調べ、PathがずれているIndexを全て修正する必要がある。 +Jungleの木の更新(commit)は、CAS(check and set)を用いて atomic に行われる。競合している書き込みにの中で自分の書き込みが成功した場合に関数 \verb+success()+が成功する。IndexはCASの前に作成され +元の木と同時に更新される。Indexの更新は変更で影響を受けるすべてのノードに対して行う必要がある。ノードそのものが変更されなくても、パスが影響を受ける場合には、そのノードも更新する必要がある。 \section{特定のNode下のTreeに対するIndexを用いた検索} - Indexを用いた検索を行う際に問題になったのが、特定のNodeの下のTreeに対して検索を行う際に、Indexが使えない問題が発生した。 - なぜなら、Indexには、Tree全体のデータが入っているので、Indexを使用した検索は必然的にTree全体に対する検索になってしまう。\\ - この問題は、NodePathに、引数に比較対象のNodePathを受け取り、そのPathが自分の下にあるかどうかを調べる関数Compareを実装することで解決した。\\ - compareを使用することにより、特定のNode下の探索を行う際、Indexで取ってきた結果に対し、compareを使い、フィルタリングを行うことで、Indexを用いた特定のNode下の探索を可能にした。\\ -{\scriptsize - \begin{itembox}[l]{図5} - \begin{verbatim} - public boolean compare(NodePath path); - \end{verbatim} - \end{itembox} -}\\ - \section{これから行うべきこと} - 実際にmaTrixとJungleの接続を行い、既存のmaTrixとJunglemaTrixの性能を評価し、本当に早くなったのか確かめる。この時にIndexの性能も評価する。 + +特定のノードの下のTreeに対する検索は、比較対象のパスを使って、自分のパス比較すれば良い。Index を使用して対象を絞ってから比較を行う。 +ノードの下の木が小さいことが予測される場合は、Indexを使用しないほうが良い性能が得られる場合もある。 +\section{これから作業} + +実際にmaTrixとJungleの接続を行い、既存のmaTrixとJunglemaTrixの性能を評価する。 + +Jungleは、過去のversionのTreeを保持しているので、 +過去のversionのuuidを指定して自由に過去のversionを参照できるようにする。 - Jungleは、過去のversionのTreeを保持しているので、 - 過去のversionのuuidを指定して自由に過去のversionを参照できるようにする。 - +JungleはRDBと異なり木構造のデータを自由に格納することができる。それゆえ木構造の設計の自由度は大きい。 +しかし、変更は木が大きいほどルートに集中してしまう。木の分割を行うと、分割した木の間の同期は version +を介して行う間接的なものとなる。なので、JungleDBの設計手法を確立させる必要がある。 - Jungleは比較的自由にデータを格納することができる。なので、Jungleを実際に使用する際に、どこまでを一つの木として扱うか、等をまとめたJungleDBの設計手法を確立させる必要がある。 +本研究は、PCIホールディングス株式会社と株式会社Symphonyとの共同研究である。 - \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}