Mercurial > hg > Papers > 2015 > tatsuki-sigos
changeset 4:84bbcfe22656 default tip
change slide
| author | tatsuki |
|---|---|
| date | Sat, 12 Sep 2015 17:30:58 +0900 |
| parents | 082148d6bf7f |
| children | |
| files | OSSIGOS.xmind slide/.DS_Store slide/slide.html |
| diffstat | 3 files changed, 104 insertions(+), 81 deletions(-) [+] |
line wrap: on
line diff
--- a/slide/slide.html Tue May 26 13:54:37 2015 +0900 +++ b/slide/slide.html Sat Sep 12 17:30:58 2015 +0900 @@ -96,6 +96,8 @@ <font size=5> <h1>非破壊的木構造データベースJungleとその評価</h1> <br><br> +</font> +<font size=6> <p>琉球大学情報工学科並列信頼研</p> <p>金川竜己</p></font> @@ -105,9 +107,11 @@ <h1>知的構造を格納するためのデータベース</h1> <font size=5> <p>我々が扱っている知識は木構造であることが多い。</p> -<p>RDBに格納するためには煩雑なデータ設計を行わなければならない</p> -<p>データ設計等を行うこと無く木構造を格納できるデータベースが望ましい</p> -<p>そこで当研究室では、非破壊的木構造データベースJungleの開発をおこなっている</p> +<p>RDBに木構造を格納する際は表に変換を行う必要があり、スキーマが煩雑になる</p> +<p>木構造をそのまま格納できるデータベースが欲しい</p> +<p>データ構造をリトライ可能な形で変更したい</p> +<p>いろいろ試しながらアプリケーションに合ったデータ設計を行える</p> +<p>当研究室では、非破壊的木構造データベースJungleの開発をおこなっている</p> <p>Jungleの表現力、機能の十分性検証、及び性能実証実験を行いたい</p> <p>そのために、Jungle上に組織の許認可管理アプリケーションmaTrixを実装した</p> </font> @@ -117,8 +121,9 @@ <div> <h1>組織の中の許認可管理アプリケーションmaTrix</h1> <font size=5> -<p>人、組織、役割等の木構造データを保持しており</p> -<p>木構造のデータはIdでお互いに参照を行っている</p> +<p>人、組織、役割等の複数の木構造データを組織構造として保持している</p> +<p>組織構造は版管理されている</p> +<p>木構造のデータはお互いに参照を行っている</p> <p>許認可の判断はアクセスルールが記述されたポリシーファイルにそって行われる</p> <p>ポリシーファイルは主に、誰が (Target)、何を (Redource)、どうできるか(Action) の3つの要素で記述されている</p> </font> @@ -130,30 +135,38 @@ <font size=5> <p>Jungleは、複数の木の集合からなり、木はノードの集合で出来ている</p> <p>ノードは、自身の子供のリストと、属性名(Key)と属性値(Value)のデータの組を持つ</p> -<p>Jungleは、非破壊的木構造であるため、一度作成した木を破壊することはない</p> +<p>Jungleは、木の編集を行う際に一度作成した木を上書きしない</p> +<p>新しい木構造を構築することでデータの編集を行う</p> +<p>変更がないノードは共有する</p> +<p>木が変更されていることが保証されているため、読み込み時にロックをかける必要がない</p> +<p>Jungleは過去のversionへの木の参照を持つ</p> +<p>過去の木に対してアクセスが可能</p> </font> </div> - +<!-- <div> <h1>Jungleのデータの編集</h1> <font size=5> -<p>新しい木構造を作成することでデータの編集を行う</p> +<p>Jungleは、木の編集を行う際に一度作成した木を上書きしない</p> +<p>新しい木構造を構築することでデータの編集を行う</p> <p>変更がないノードは共有する</p> -<img src="./images/non_destructive_tree_edit2.png"> +<iframe src="images/non_destructive_tree_edit2.html" width="1000" height="400"></iframe> <p>木の更新は、ルートノードをCASを用いて入れ替えることで行う</p> <p>データの上書きが無いため、読み込み中にロックをかける必要がない</p> +<p>木は過去のversionの木への参照を持つ</p> </font> </div> - +--> <div> <h1>Jungle上でのmaTrixのデータ構造の表現</h1> <font size=5> -<p>Jugnleは木構造のデータをそのまま格納できるため、maTrixのデータを一部を除きそのまま格納できる</p> +<p>Jugnleは木構造のデータをそのまま格納できる</p> +<p>maTrixが書きだしたxml形式データをそのまま格納できる</p> <p>maTrixの人物TreeをJungleに格納した図の一部を以下に示す</p> <iframe src="images/TreePersonJungle.html" width="1000" height="1000"></iframe> <p></p> @@ -164,8 +177,8 @@ <div> <font size=5> <h1>Jungle上でのIdを使った木の相互参照</h1> -<p>組織構造は複数の木構造を持ち、お互いのノード参照し合っている</p> -<p>ex. 人物と役割は、idを用いてお互いのノードを参照する</p> +<p>組織構造は複数の木構造を持ち、お互いのノード参照している</p> +<p>ノードの参照はidとindexを用いて表現する</p> <iframe src="images/ref.html" width="2000" height="1000"></iframe> </font> </div> @@ -174,9 +187,10 @@ <div> <h1>JungleのIndex</h1> <font size=5> -<p>Jungleは過去のTreeを全て保持しているため、Treeのversion毎にIndexを持っている必要がある</p> -<p>version毎にIndexを作るとメモリを多量使用してしまう</p> -<p>過去のIndexとデータを共有するIndexを実装した</p> +<p>Jungleは過去の木を全て保持している</p> +<p>version毎にIndexを持っている必要がある</p> +<p>全てに新しくIndexを作るとメモリを多量使用してしまう</p> +<p>前の版のIndexから変更が行われていないデータを共有するIndexを実装した</p> <p>複数のversionのIndexがあっても、データの差分しかメモリは使用されない</p> </font> </div> @@ -184,10 +198,10 @@ <div> <h1>非破壊TreeMapの実装</h1> <font size=5> -<p>当初は、FunctionalJavaのTreeMapを使用してIndexの実装を行った</p> -<p>FunctionalJavaにはバグがあり、性能が出なかった</p> +<p>FunctionalJavaというjava上で関数型プログラミングが行えるライブラリがある</p> +<p>当初はFunctionalJavaのTreeMapを使用してIndexの実装を行った</p> +<p>FunctionalJavaにはTreeMapにはgetが致命的に遅いバグがあった</p> <p>新しく非破壊TreeMapを実装した</p> -<p>TreeMapのアルゴリズムには赤黒木を採用した</p> <p>その結果Jungleの性能は劇的に向上した</p> </font> </div> @@ -195,9 +209,10 @@ <div> -<h1>木構造の親を取得するIndex</h1> +<h1>ノードの親を取得するIndex</h1> <font size=5> -<p>Jungleは子から親への参照は存在しないため、自身の親を返すParentIndexの実装を行った</p> +<p>Jungleは子から親への参照は存在しない</p> +<p>子ノードを渡すと親をノードを返すParentIndexの実装を行った</p> </font> </div> @@ -213,35 +228,30 @@ <div> +<h1>Treeの検索</h1> <font size=5> -<h1>Treeの検索</h1> -<p>データアクセス関数を実装するため、Traverserに検索関数findを実装する</p> +<p>検索関数はTraverserに実装する</p> <div style="padding: 10px; margin-bottom: 10px; border: 1px solid #333333;"> InterfaceTraverser traverser = tree.getTraverser(boolean useIndex); </div> -<p>TraverserはTreeのNodeを走破する機能を持ったクラスです</p> +<p>Traverserは木のノードを走破する機能を持ったクラスです</p> <p>TreeからgetTraverserで取得可能</p> <p>引数で検索を行う際にIndexを使用するかどうかを選択できる</p> </font> </div> <div> +<h1>Treeの検索</h1> <font size=5> -<h1>Treeの検索</h1> <div style="padding: 10px; margin-bottom: 10px; border: 1px solid #333333;"> public Iterator<TreeNode> find(Query query,String key, String searchValue); </div> -<p>findは以下のように定義されており、引数に</p> - <p>探索の条件を記述する関数boolean condition(TreeNode)を定義したQuery</p> +<p>findは上のように定義されており、引数に</p> + <p>検索の条件を記述する関数boolean condition(TreeNode)を定義したQuery</p> <p>Indexを使う検索に使用するString 属性名、String 属性値のペア</p> <p>の3つを取る</p> <p>条件に一致したNodeのIteratorを返す</p> <p>Iteratorは、複数の値から１つずつ順番に取得するためのinterfaceである</p> - <div style="padding: 10px; margin-bottom: 10px; border: 1px solid #333333;"> - public interface Query {<br> -   boolean condition(TreeNode _node);<br> - } - </div> </font> </div> @@ -250,15 +260,15 @@ <font size=5> <div style="padding: 10px; margin-bottom: 10px; border: 1px solid #333333;"> InterfaceTraverser personTraverser = personTree.getTraverser(true);<br> -Iterator<TreeNode> personIdpairIterator = personTraverser.find((TreeNode node) -> { <br> +Iterator<TreeNode> iterator = personTraverser.find((TreeNode node) -> { <br> String personId = node.getAttributes().getString("Person-id");<br> if (personId.equals("p:4"))<br> return true;<br> return false;<br> }, "Person-id", "p:4");<br> <br> -if (personIdpairIterator.hasNext())<br> - TreeNode node = personIdpairIterator.next(); +if (iterator.hasNext())<br> + TreeNode node = iterator.next(); </div> <ol> <li>Treeから木の探索を行うInterfaceTraverserを取得する</li> @@ -279,9 +289,9 @@ <li>Aさん(Subject)が、学科のノートPC(Resource)の借りる(Action)ために、maTrixに貸出許可を求める</li> <li>maTrixは、PCの貸出許可を与えるかを判断するためのポリシーファイルを参照する</li> <li>maTrixはAさんの役割を取得する</li> -<li>Aさんが情報工学科の役割を持っていた場合貸出許可を与える</li> +<li>Aさんが情報工学科学生の役割を持っていた場合貸出許可を与える</li> </ol> -<p>maTrixは、3番目の処理で役割を取得する関数roleIdsを使用している</p> +<p>maTrixは、3番目の処理で役割を取得する検索関数roleIdsを使用している</p> </font> </div> @@ -306,11 +316,11 @@ <p>人や組織は、複数の組織に所属することが可能</p> <p>組織に所属する際に役割が与えられる</p> <p>例. 人が大学に所属していると、「学生」や「教授」という役割が与えられる</p> -<p>フィルターを使うと組織が与える役割で結果を絞り込める</p> +<p>フィルターを使うと役割を与える組織、で結果を絞り込める</p> </font> </div> - +<!-- <div> <h1>roleIdsのコード</h1> <font size=5> @@ -336,7 +346,7 @@ }, "Person-id", id);<br> </div> <p>getTreeで取得した木から、getTraverserで木を探索する機能を持ったTraverserを取得する</p> -<p>取得したTraverser.findで、属性名 Person-id、属性値 引数で指定されたidのペアを持つノードのIteratorを検索する</p> +<p>取得したTraverser.findで、属性名 Person-id、属性値 引数で指定されたidのペアを持つノードを検索する</p> </font> </div> @@ -346,9 +356,9 @@ <font size=5> <div style="padding: 10px; margin-bottom: 10px; border: 1px solid #333333;"> TreeNode PersonNode = personNodeIterator.next();<br> -TreeNode parentOrganizationsNode = PersonNode.getChildren().at(5).b();<br> -Iterator<TreeNode> OrganizationMappedByRoleIterator = parentOrganizationsNode.getChildren().iterator();<br> -return new Iteratorr<String>() {<br> +TreeNode rolesNode = PersonNode.getChildren().at(5);<br> +Iterator<TreeNode> roleIterator = rolesNode.getChildren().iterator();<br> +return new Iterator<String>() {<br> ………<BR> }; </div> @@ -366,21 +376,21 @@ <p>定義したiteratorのhasNext</p> <div style="padding: 10px; margin-bottom: 10px; border: 1px solid #333333;"> public boolean hasNext() {<br> - if (OrganizationMappedByRoleIterator.hasNext())<br> - roleRefId = search();<br> + if (roleIterator.hasNext())<br> + roleId = search();<br> else<br> - roleRefId = null;<br> - if (roleRefId != null)<br> + roleId = null;<br> + if (roleId != null)<br> return true;<br> return false;<br> }<br> </div> <p>取得した役割のIteratorの中身がある場合はsearch()を実行する</p> <p>search()は条件にあった役割を返す</p> -<p>中身がない場合はroleRefId = nullを行う</p> -<p>roleRefIdがnullの場合、条件にあった役割は無いのでfalseを返し</p> -<p>roleRefIdに値がある場合はtrueを返す</p> -<p>next()では、roleRefIdの値を返せば良い</p> +<p>中身がない場合はroleId = nullを行う</p> +<p>roleIdがnullの場合、条件にあった役割は無いのでfalseを返し</p> +<p>roleIdに値がある場合はtrueを返す</p> +<p>next()では、roleIdの値を返せば良い</p> </font> </div> @@ -390,14 +400,14 @@ <h1>roleIdsのコード</h1> <font size=5> <div style="padding: 10px; margin-bottom: 10px; border: 1px solid #333333;"> -for (; OrganizationMappedByRoleIterator.hasNext(); ) {<br> - TreeNode OrganizationMappedByRole = OrganizationMappedByRoleIterator.next();<br> - TreeNode organizationRefIdNode = OrganizationMappedByRole.getChildren().at(0).b();<br> - String organizationRefId = organizationRefIdNode.getAttributes().getString("text-organizationRefId");<br> - if (!filterIds.contains(organizationRefId) && !filterIds.isEmpty())<br> +for (; roleIterator.hasNext(); ) {<br> + TreeNode roleNode = roleIterator.next();<br> + TreeNode organizationNode = roleNode.getChildren().at(0).b();<br> + String organizationId = organizationNode.getAttributes().getString("text-organizationRefId");<br> + if (!filterIds.contains(organizationId) && !filterIds.isEmpty())<br> continue;<br> - TreeNode roleRefIdNode = OrganizationMappedByRole.getChildren().at(1).b();<br> - return roleRefIdNode.getAttributes().getString("text-roleRefId");<br> + TreeNode roleIdNode = roleNode.getChildren().at(1).b();<br> + return roleIdNode.getAttributes().getString("text-roleRefId");<br> }<br> return null; </div> @@ -409,7 +419,7 @@ <p>役割のノードのiteratorが空になったら、nullを返す</p> </font> </div> - +--> <div> <font size=5> @@ -418,11 +428,12 @@ <p>以下に親を辿る検索を行う例を記す</p> <ol> <li>Aさんが、maTrixに工学部の学生にのみ貸出を行っている書籍の貸出許可を求める</li> +<li>maTrixは、書籍の貸出許可を与えるかを判断するためのポリシーファイルを参照する</li> <li>Aさんの所属している組織の情報を取得する(情報工学科)</li> <li>情報工学科の親の情報を取得する(工学部)</li> -<li>maTrixは、Aさんに工学部に所属しているため本の貸出を許可する</li> +<li>maTrixは、Aさんは工学部に所属しているため本の貸出を許可する</li> </ol> -<p>3番目の処理で親Nodeを返すParentIndexを使用する</p> +<p>4番目の処理で親ノードを辿る処理を行っています</p> </font> </div> @@ -433,16 +444,16 @@ <p>以下に親の取得を行う部分のコードを記述する</p> <p>idには工学部のidが、orgNodeにはAさんが所属している組織のidを持ったノードが入っている</p> <div style="padding: 10px; margin-bottom: 10px; border: 1px solid #333333;"> -do {<br> +while(true) {<br> String orgId = orgNode.getAttributes().getString("Organization-id");<br> if (id.equals(orgId))<br> return true;<br> - parentOrgNodeOptional = parentIndex.get(orgNode);<br> + Optional<TreeNode> parentOrgNodeOptional = parentIndex.get(orgNode);<br> if (parentOrgNodeOptional.isPresent())<br> orgNode = parentOrgNodeOptional.get();<br> else<br> return false;<br> -}while(true);<br> +}<br> </div> <ol> <li>orgNodeから組織のidを取得する</li> @@ -454,10 +465,21 @@ </div> <div> +<h1>ポリシーファイルのインタプリタ</h1> +<font size=5> +<p>maTrixのポリシーファイルを読み込んで許認可を判断するインタプリタの実装を行った</p> +<p>引数にポリシーファイルと、誰が(subject)、何に(Resource)、どうするか(Action)を取る</p> +<p>返り値は、許可(Permit) or 拒否(Deny)がある</p> +<p>実際にJungleの上で許認可判断が行えるようになった</p> +</font> +</div> + + +<div> <h1>ベンチマーク</h1> <font size=5> <p>Jungle上にmaTrixの実装を行ったので、性能測定を行った</p> -<p>測定はmongoDBとの比較とマルチプロセッサー上でのJungleの読み書き性能の2つを行った</p> +<p>測定はmongoDBとの比較とマルチプロセッサー上での性能評価の2つを行った</p> <p>木構造をそのまま格納できること、属性名を指定することで属性値が取得できるなど、Jungleと似た特徴を持っているmongoDBを比較対象に選択した</p> </font> </div> @@ -479,10 +501,10 @@ <div> <h1>mongoDBとの比較</h1> <font size=5> -<p>1万人のデータをmongoDBとJungleに格納し、データの検索にかかる時間の測定を行った</p> +<p>1万個のデータをmongoDBとJungleに格納し、データの検索にかかる時間の測定を行った</p> <p>各DBに挿入するデータは以下のような構造を持つ</p> <div style="padding: 10px; margin-bottom: 10px; border: 1px solid #333333;"> -{PersonId: 固有のPersonId ,roleRefIds:ランダムな役割Id}<br> +{PersonId: 固有のPersonId ,roleId:ランダムな役割Id}<br> </div> </font> </div> @@ -505,13 +527,13 @@ <font size=5> <p>Jungleのデータの読み込みは以下のように行った</p> <div style="padding: 10px; margin-bottom: 10px; border: 1px solid #333333;"> -InterfaceTraverser traverser = tree.getTraverser(true); +InterfaceTraverser traverser = tree.getTraverser(true);<br> Iterator<TreeNode> it = traverser.find((TreeNode node) -> {<br> String nodeId = node.getAttributes().getString("Person-id");<br> if (nodeId.equals("p:9"))<br> return true;<br> return false;<br> - }, "Person-id", "r:9");<br> + }, "Person-id", "p:9");<br> if (it.hasNext()) {<br> TreeNode targetNode = it.next();<br> String targetRoleId = targetNode.getAttributes().getString("roleId");<br> @@ -541,7 +563,8 @@ <h1>マルチプロセッサー上でのJungleの読み書き性能</h1> <font size=5> <p>Jungleがマルチプロセッサ上で性能が出るか測定を行った</p> -<p>複数スレッドからJungleに読み込みだけを行った場合と、1スレッドだけ書き込みを行い続け、<br>残りのスレッドで読み込み行った場合で測定を行った。</p> +<p>複数スレッドからJungleに読み込みだけを行った場合と、1スレッドだけ書き込みを行い続け、<br>残りのスレッドで読み込み行った場合で測定を行った</p> +<p>Jungleに格納したデータはmaTrixで実際に使われているユーザーデータ400人分</p> <p>読み込みではmaTrixで実際に使われている検索関数isActive(personId , version)を用いた</p> <p>この関数引数で与えた人が、maTrixにアカウントを持っているか調べる関数である</p> </font> @@ -552,7 +575,7 @@ <font size=5> <embed src="images/transactionPersecond.svg" width="700" height="700"align="left"/> <br> -<p>Jungleでは、書き込みと読み込みを同時に行っても<br>性能低下はおこらなかった</p> +<p>Jungleでは、書き込みと読み込みを同時に行っても<br>ほぼ性能低下はおこらなかった</p> <p>ハイパースレッディングに引っかかるまでは<br>リニアに性能が出ている</p> <p>書き込みと読み込みを同時に行った場合、<br>読み込みのCPUCOUNTが2の時だけ性能が出ていない</p> <p>これは、書き込みを連続で行っているため<br>読み込みと書き込みで競合が起きている</p> @@ -564,7 +587,8 @@ <div> <h1>考察</h1> <font size=5> -<p>性能評価では、JungleのほうがMongoDBより高速に動いたが、全てのアプリケーションでJungleの方が早いわけではない</p> +<p>マルチプロセッサ上でもJungleは並列に動作する</p> +<p>性能比較では、JungleのほうがMongoDBより高速に動いたが、全てのアプリケーションでJungleの方が早いわけではない</p> <p>Jungleは、木構造の形と使われ方がアルゴリズム的に一致している場合に性能が出る</p> </font> </div> @@ -573,7 +597,7 @@ <h1>Jungleに向いているアプリケーション</h1> <font size=5> <p>Jungleは、書き込み時の処理が木の大きさで変わる</p> -<p>そのため、比較的小さな木にデータがたくさんあり、木の深い部分に対し変更があまり行われないアプリケーションが得意</p> +<p>そのため、比較的小さな木がたくさんあり、木の深い部分に対し変更があまり行われないアプリケーションが得意</p> <p>また、書き込みより読み込みを重視したDBであるため、読み込みが多いアプリケーションが性能が出る</p> <p>そのため、Jungleの上に構築するアプリケーション例としてBBSやWEBページなどがある</p> </font> @@ -597,7 +621,7 @@ <p>2.データの書き出し部分の改良</p> <p> Jungleはデータをディスクに書き出すことが可能である</p> <p> 書きだしたデータを読み込む機能もあるのでトラブルが発生し、Jungleが強制終了されても元の状態に復旧できる</p> -<p> 今の実装は、データの書き出しはcommit時に毎回行っているため書き出しが非効率的である</p> +<p> 今の実装は、データの書き出しは、変更が加わる度に行われるので、非効率的である</p> <p> できれば複数回分の変更をバッファリングしておいて一気に書き出しを行いたい</p> <p> ある値を行ったり来たりするような、書き出す必要が無いデータもあるため、書き出す部分の最適化を行う必要がある</p> </font> @@ -606,11 +630,11 @@ <div> <h1>今後の課題</h1> <font size=5> -<p>3.過去のデータの掃除</p> +<p>3.メモリの効率的な利用</p> <p> Jungleは非破壊でデータを保持し続けるため、非常に多くのメモリを消費する</p> -<p> ある程度のタイミングで過去のデータをメモリから掃除する必要がある</p> -<p> しかし、データを掃除するタイミングは、Jungle上に実装するアプリケーションによって変わる</p> -<p> そこを含め、データを掃除するAPIの設計を行う必要がある</p> +<p> ある程度のタイミングで過去のデータをメモリから解放する必要がある</p> +<p> しかし、データを解放するタイミングは、Jungle上に実装するアプリケーションによって変わる</p> +<p> そこを含め、データを解放するAPIの設計を行う必要がある</p> <p>4.分散環境でのmaTrixの構築</p> <p> Jungleはもともと分散データベースである</p> <p> 分散版Jungle上にmaTrixを構築し、性能測定を行いたい</p> @@ -626,7 +650,7 @@ <p> 木のサイズが大きいと、データ更新の負荷が大きくなるため分割を行う必要がある</p> <p> 分割を行った木同士の参照はIdを用いた間接的なものになる</p> <p> このようにJungleはRDBと異なり格納するデータの自由度が大きい</p> -<p> なのでJungleの設計手法を確立させる必要がある</p> +<p> Jungleの設計手法を確立させる必要がある</p> </font> </div> @@ -635,8 +659,7 @@ <font size=5> <p>当研究室で開発している非破壊的木構造データベースJungle上に許認可管理アプリケーションmaTrixを実装した</p> <p>その際必要になった検索APIやIndexの実装を行った</p> -<p>またFunctionalJavaは性能が出なかったので、非破壊TreeMapを自作した</p> -<p>その結果Jungleの性能は劇的に上昇した</p> +<p>またFunctionalJavaのTreeMapでは性能が出なかったので、非破壊TreeMapを自作した</p> <p>性能測定ではmongoDBより高速に動き、マルチプロセッサ上でも並列に動作した</p> </font> </div>