Mercurial > hg > Papers > 2014 > tatsuki-midterm
view midterm.tex @ 5:0fc8736218d4
fix
author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
---|---|
date | Wed, 29 Oct 2014 21:13:48 +0900 |
parents | 75e8aac9a4b5 |
children | 9cff89bddcc7 |
line wrap: on
line source
\documentclass[twocolumn,twoside,9.5pt]{jarticle} \usepackage[dvips]{graphicx} \usepackage[dvipdfm]{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} \begin{document} \title{Database Jungleに関する研究} \author{115731 金川竜己 {}{} 指導教員 : 河野真治} \date{} \maketitle \thispagestyle{fancy} \section{非破壊木構造データベース} 当研究室ではデータの変更の際に過去の木構造を保存しつつ新しく木構造を作成する非破壊的木構造を用いたデータベースであるJungleを開発している。 Jungle DBの有効性を示すために、 本研究では検索API、Index、過去データの参照の実装を行う。 Jungleが実用DBとしての性能を持っているかどうかを調べるために、アカウント管理システムmaTrixの実装と評価を行う。 Jugnleの木は、子供を複数持つノードからなる。子供は順序付けられており、任意の位置で作成削除することができる。 ノードには属性名と属性値の組があり、データベースのレコードとして使うことができる。Index は、このレコードの属性に 対して作成する。任意の木で、属性値に対応する複数のノード、そして必要ならば、そこまでのパスの組を返す。 ここでパスとは、ルートから木をたどるのに必要な各ノードの子供の番号のリストである。 maTrixは、アカウント管理、許諾判定システムである。 maTrixは人、役職、役割、権限と言った木構造の組織、許諾のポリシーを決めるXACMLファイルをデータベースとして持つ。 いつ、誰が、どんな申請をしたか、と言った過去の承認情報を保持する必要がある。 % ので、過去の組織のデータを参照する必要が出てくる。よって過去のデータの参照が出来るJungleと相性が良い。 % これらは、XMLで記述されており、 % maTrixが保持している人、役職、役割等のデータはお互いに参照している。 % ポリシーファイルは、組織の中で申請等を行った際に、どの権限によってその申請が許諾されるのかを指定している。 % 組織のデータ、ポリシーファイル共に木構造のデータであるため、Jungleにそのまま格納できる。 \section{maTrixに必要なデータベースの構築} 組織構造は木構造なので Jungle の木酵素にそのままマッピングできる。Persons, Organiations, RoleDescription の三つの木を一つのJungleの木として格納する。 XACMLは、XMLなので木構造を持つ。XACMLは、組織構造中の人や役職を id として参照する。 具体的な許諾では、 例えば、その人がどの組織に所属して、その役割がどの権限を持っているかを返す検索が必要となる。 XML形式で出力されたmaTrixのデータをJungleに格納するために、SAXを用いて、Jungle用のXMLReaderを作成した。 \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]{Sample Query} \begin{verbatim} Iterator<Pair<TreeNode, NodePath>> 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} \label{query1} \end{itembox} }\\ \verb+find+は引数に\verb+Query+、\verb+String key+、\verb+String value+の3つを取る。\verb+key+ はIndexの対象となる属性名である。 Queryは図\ref{interface}で定義されたinterfaceである。実行されるQuery は ノードを引数に取り、そのノードが条件に一致しているかどうかを調べるconditionという関数が定義されている必要がある。 {\scriptsize \begin{itembox}[l]{Query interface} \begin{verbatim} public interface Query { boolean condition(TreeNode node); } \end{verbatim} \label{interface} \end{itembox} }\\ \section{Indexの実装} Jungleの探索はTreeの全探索の計算量はO(n)である。 Indexの実装には、functionalJavaのTreeMapを使用し、計算量はO(logN)となる。 これにより、前の版の木のIndexの最大共有するこが可能であり、複数の木の版すべてに対するIndexをサポートすることが可能になる。 Jungle DB は分散DBなので、 on-th-fly つまり必要になったDBノード毎に作成する。 {\scriptsize \begin{itembox}[l]{図3} \begin{verbatim} TreeMap<String, TreeMap <String, List<Pair<TreeNode, NodePath>>>> index; \end{verbatim} \end{itembox} }\\ 図3にはJungleDBにおけるIndexの型を記述した Jungleでは、木の編集や、特定のNode下のTreeの探索、Nodeの親をたどるためには全てそのNodeへのPathが必要になる、ため、IndexにもそのNodeまでのPathが必要になる。そのため、IndexのNodePathが大きなボトルネックとなっている。 JungleでTreeの編集を行う際は、JungleTreeEditorを使用し、子ノードのadd、delete、属性のput、deleteを行う。 Treeに対して変更を加える時にIndexも更新も行う。 Jungleの木の更新(commit)は、CAS(check and set)を用いて atomic に行われる。競合している書き込みにの中で自分の書き込みが成功した場合に関数 \verb+success()+が成功する。IndexはCASの前に作成され 元の木と同時に更新される。Indexの更新は変更で影響を受けるすべてのノードに対して行う必要がある。ノードそのものが変更されなくても、パスが影響を受ける場合には、そのノードも更新する必要がある。 \section{特定のNode下のTreeに対するIndexを用いた検索} 特定のノードの下のTreeに対する検索は、比較対象のパスを使って、自分のパス比較すれば良い。Index を使用して対象を絞ってから比較を行う。 ノードの下の木が小さいことが予測される場合は、Indexを使用しないほうが良い性能が得られる場合もある。 \section{これから作業} 実際にmaTrixとJungleの接続を行い、既存のmaTrixとJunglemaTrixの性能を評価する。 Jungleは、過去のversionのTreeを保持しているので、 過去のversionのuuidを指定して自由に過去のversionを参照できるようにする。 JungleはRDBと異なり木構造のデータを自由に格納することができる。それゆえ木構造の設計の自由度は大きい。 しかし、変更は木が大きいほどルートに集中してしまう。木の分割を行うと、分割した木の間の同期は version を介して行う間接的なものとなる。なので、JungleDBの設計手法を確立させる必要がある。 本研究は、PCIホールディングス株式会社と株式会社Symphonyとの共同研究である。 \begin{thebibliography}{9} \bibitem{1} 玉城将士 非破壊的木構造を用いた分散CMSの設計と実装 \bibitem{2} 大城信康 分散Database Jungleに関する研究 \bibitem{3} Eric Redmond and Jim R. Wilson 7つのデータベース7つの世界 \end{thebibliography} \end{document}