知的構造を格納するためのデータベース
-知的構造を格納するためのデータベース
-そこで、当研究室では非破壊木構造データベースJungleの開発を行っている
+我々が扱っている知識は木構造であることが多い。
+RDBに格納するためには煩雑なデータ設計を行わなければならない
+データ設計等を行うこと無く木構造を格納できるデータベースが望ましい
+そこで当研究室では、非破壊的木構造データベースJungleの開発をおこなっている
Jungleの表現力、機能の十分性検証、及び性能実証実験を行いたい
そのために、Jungle上に組織の許認可管理アプリケーションmaTrixを実装した
@@ -118,36 +115,44 @@組織の中の許認可管理アプリケーションmaTrix
-組織の中の許認可管理アプリケーションmaTrix
-maTrixとは、株式会社Symphonyが開発しているアカウント管理、許諾判定システムである
-人、組織、役割等の木構造データとポリシーファイルを持つ
-データ同士が参照を行うことで組織構造を表現しており、組織構造は版管理されている
+人、組織、役割等の木構造データを保持しており
+木構造のデータはIdでお互いに参照を行っている
+許認可の判断はアクセスルールが記述されたポリシーファイルにそって行われる
ポリシーファイルは主に、誰が (Target)、何を (Redource)、どうできるか(Action) の3つの要素で記述されている
-maTrixはアクセス要求に応じたポリシーファイルを参照することで許認可の判断を行う
非破壊的木構造データベースJungle
-非破壊的木構造データベースJungle
Jungleは、複数の木の集合からなり、木はノードの集合で出来ている
ノードは、自身の子供のリストと、属性名(Key)と属性値(Value)のデータの組を持つ
Jungleは、非破壊的木構造であるため、一度作成した木を破壊することはない
-そのため、書き込みと読み込みを同時に行うことができる
-木の編集は、ルートから編集を行うノードまでコピーし、新しい木構造を作成することで行う
-その際、変更がないノードは共有する
+ +Jungleのデータの編集
+ +新しい木構造を作成することでデータの編集を行う
+変更がないノードは共有する
木の更新は、ルートノードをCASを用いて入れ替えることで行う
+データの上書きが無いため、読み込み中にロックをかける必要がない
Jungle上でのmaTrixのデータ構造の表現
-Jungle上でのmaTrixのデータ構造の表現
Jugnleは木構造のデータをそのまま格納できるため、maTrixのデータを一部を除きそのまま格納できる
maTrixの人物TreeをJungleに格納した図の一部を以下に示す
@@ -158,57 +163,52 @@Jungleで表現出来ないmaTrixのデータ構造
-Jungleのノードは１つの属性名に対し、１つの属性値しか持つことが出来ない
-しかしmaTrixには、１つの属性名に対し、複数の属性名がペアになることがある
-例として、人が所属している組織のIdなどである
-なので、Jungleに格納できる形式に変換を行う必要がある
-データの変換は、データを複数個のノードに分割して格納することで行う
-以下にデータ変換の例を示す
- - -Jungle上での組織構造の表現
-maTrixでは、複数の木構造がお互いに参照を行うことで組織構造を表現している
-人や組織はそれぞれ異なるIdを保持している(p:1など)
-参照はIdを用いて行う
-→ノードIDの検索機能が必要となる
- +Jungle上でのIdを使った木の相互参照
+組織構造は複数の木構造を持ち、お互いのノード参照し合っている
+ex. 人物と組織は、idを用いてお互いのノードを参照する
+
JungleのIndex
-Jungle上でのIdを使った木の相互参照
-組織構造は複数の木構造を持ち、お互いのノード参照し合っている
-ex. 人物は、そのロールの木の中のノードを参照する
-
-ロールの木のノードにID属性を用意し、異なるID値を割りふる
-ノードIDにより参照を可能にする
-→ノードIDの検索機能が必要となる
+Jungleは過去のTreeを全て保持しているため、Treeのversion毎にIndexを持っている必要がある
+version毎にIndexを作るとメモリを多量使用してしまう
+過去のIndexとデータを共有するIndexを実装した
+複数のversionのIndexがあっても、データの差分しかメモリは使用されない
+ +非破壊TreeMapの実装
+ +当初は、FunctionalJavaのTreeMapを使用してIndexの実装を行った
+FunctionalJavaにはバグがあり、性能が出なかった
+新しく非破壊TreeMapを実装した
+TreeMapのアルゴリズムには赤黒木を採用した
+その結果Jungleの性能は劇的に向上した
木構造の親を取得するIndex
-maTrixでの許認可管理
-maTrixを用いた許認可は、組織構造だけでは判断されない
-アクセス可能な時間等のルールは組織構造では表現できないからである
-そこでアクセスルールを記述したポリシーファイルを用いて許認可管理を行う
+Jungleは子から親への参照は存在しないため、自身の親を返すParentIndexの実装を行った
+ +許認可Queryの実装
+ +maTrixを用いた許認可は、ポリシーファイルを参照し行われる
ポリシーファイルには、subject(誰が)、Resource(何に対して)、Action(何が出来るか)を記述する
- -以下に許認可管理の流れを示す
--
-
- Aさん(Subject)が、学科のノートPC(Resource)の借りる(Action)ために、maTrixに貸出許可を求める -
- maTrixはリポジトリから、貸出許可を与えるかを判断するためのポリシーを取得する -
- ポリシーファイルを元に、組織構造にアクセスを行い許可を与えるかどうかを判断する -
maTrixにおける許認可判断において、データに対するアクセスは、subject部分でデータアクセス関数を用いて行う
+maTrixには、データアクセス関数が実装されている
+Jungle上にmaTrixを実装するにあって、データアクセス関数の実装を行った
Treeの検索
-Jungleの木をたどる Traverserを使用する
+データアクセス関数を実装するため、Traverserに検索関数findを実装する
TraverserはTreeのNodeを走破する機能を持ったクラスです
TreeからgetTraverserで取得可能
-第一引数で 検索を行う際にIndexを使用するかどうかを選択できる
+引数で検索を行う際にIndexを使用するかどうかを選択できる
+ +Treeの検索
findは以下のように定義されており、引数に
+探索の条件を記述する関数boolean condition(TreeNode)を定義したQuery
+Indexを使う検索に使用するString 属性名、String 属性値のペア
+の3つを取る
+条件に一致したNodeのIteratorを返す
+Iteratorは、複数の値から１つずつ順番に取得するためのinterfaceである
++ boolean condition(TreeNode _node);
+ } +
findの使用例
+ ++Iterator<TreeNode> personIdpairIterator = personTraverser.find((TreeNode node) -> {
+ String personId = node.getAttributes().getString("Person-id");
+ if (personId.equals("p:4"))
+ return true;
+ return false;
+ }, "Person-id", "p:4");
+
+if (personIdpairIterator.hasNext())
+ TreeNode node = personIdpairIterator.next();
第一引数には、探索の条件を記述する関数boolean condition(TreeNode)を定義したQueryを受け取る
-第二、第三引数の、String key、String valueはIndexの取得に使用する
-条件に一致したNodeのIteratorを返す
+-
+
- Treeから木の探索を行うInterfaceTraverserを取得する +
- findを実行する。引数には、検索条件が記述されたQuery、Person-Id、p:4を与える。(以下Queryの中の解説) +
- nodeから属性名Person-idとペアになっている属性値を取得する +
- 返り値がp:4と一致するかどうかを調べる +
- 一致した場合trueを一致しなかった場合falseを返す +
- 帰ってきたIteratorからNodeを取得する +
maTrix上での許認可判断例(1)
+ +情報工学科の学生にのみ貸し出されるPCをAさんが借りようとした場合の許認可判断
+-
+
- Aさん(Subject)が、学科のノートPC(Resource)の借りる(Action)ために、maTrixに貸出許可を求める +
- maTrixは、PCの貸出許可を与えるかを判断するためのポリシーファイルを参照する +
- データにアクセスしAさんの役割を取得する +
- Aさんが情報工学科の役割を持っていた場合貸出許可を与える +
maTrixは、3番目の処理で役割を取得する関数roleIdsを使用している
+ +役割を取得する関数
+ +roleIdsは、人、組織の役割を取得する関数
- boolean condition(TreeNode _node);
-} +public Iterator<String> searchPersonRoleIds(String version, String id, LinkedList<String> filterIds) +
roleIdsは引数に
+の3つをとります
+ +roleIdsのフィルター
+ +人や組織は、複数の組織に所属することが可能
+組織に所属する際に役割が与えられる
+例. 人が大学に所属していると、「学生」や「教授」という役割が与えられる
+フィルターを使うと組織が与える役割で結果を絞り込める
roleIdsのコード
-JungleのIndex
-indexを実装することで探索計算量がO(logN)となる
-Jungleは過去のTreeを全て保持しているため、Treeのversion毎にIndexを持っている必要がある
-version毎にIndexを作るとメモリを多量消費してしまう
-FunctionalJavaのTreeMapを使用してIndexの実装を行った
-データの更新が行われた際に、一度作られたIndexに対して更新を行わず、新しいIndexを構築します
-その際、過去のIndexとデータを共有している
-複数のversionのIndexがあっても、データの差分しかメモリは消費されない
-メモリの使用量を抑えつつ複数のversionでIndexを保持できる
++
maTrixは組織構造を版管理している
+getTree(String Version, String TreeName)は、VersionとTreeNameで指定された木を返す
+今回はroleIdsの引数で指定されたversionの人物Treeを取得している
+ +roleIdsのコード
+ ++ Iterator<TreeNode> personNodeIterator = traverser.find((TreeNode node) -> {
+ String nodeId = node.getAttributes().getString("Person-id");
+ if (nodeId.equals(id))
+ return true;
+ return false;
+ }, "Person-id", id);
+
getTreeで取得したTreeから、getTraverserで木を探索する機能を持ったTraverserを取得する
+取得したTraverser.findで、属性名 Person-id、属性値 引数で指定されたidのペアを持つノードのIteratorを検索する
+ +roleIdsのコード
+ ++TreeNode parentOrganizationsNode = PersonNode.getChildren().at(5).b();
+Iterator<TreeNode> OrganizationMappedByRoleIterator = parentOrganizationsNode.getChildren().iterator();
+
findで取得したノードから、その人が持っている役割を持つノードのIteratorを取得する
+idを持っているノードの5番目の子供の下に役割のデータが格納されている
+なので、PersonNode.getChildren().at(5).b();で5番目の子供を取得
+その下に役割のデータが入ったノードがあるので、子供のiteratorを取得している
+ +roleIdsのコード
+ ++ TreeNode OrganizationMappedByRole = OrganizationMappedByRoleIterator.next();
+ TreeNode organizationRefIdNode = OrganizationMappedByRole.getChildren().at(0).b();
+ String organizationRefId = organizationRefIdNode.getAttributes().getString("text-organizationRefId");
+ if (!filterIds.contains(organizationRefId) && !filterIds.isEmpty())
+ continue;
+ + TreeNode roleRefIdNode = OrganizationMappedByRole.getChildren().at(1).b();
+ return roleRefIdNode.getAttributes().getString("text-roleRefId");
+}
+
役割のデータが入ったノードのiteratorをfor文で回して役割を取得する
+iteratorで取得できるノードの0番目の子供には役割を与える組織名が
+1番目のノードには与えられる役割名を保持している
+0番目の子供から組織名を取得し検索結果の絞込を行う
+その後1番目のノードから役割名を返す
+このfor文はroleIdsの返り値のiteratorで呼ばれます
木構造の親を辿るQuery
-maTrixで許認可を判断する際に、木構造の親を辿る検索を行う必要がある
+maTrixで許認可を判断する際に、木構造の親を辿る検索が必要になる場合がある
以下に親を辿る検索を行う例を記す
- Aさんが、maTrixに工学部の学生にのみ貸出を行っている書籍の貸出許可を求める
- Aさんの所属している組織の情報を取得する(情報工学科)
- 情報工学科の親の情報を取得する(工学部) -
- Aさんは工学部に所属しているため本の貸出を許可する +
- maTrixは、Aさんに工学部に所属しているため本の貸出を許可する
TreeNodeでgetを行うと、親Nodeを返すParentIndexを実装した
-3番目の処理でParentIndexを使用する
+3番目の処理で親Nodeを返すParentIndexを使用する
+ +親を辿るQueryのコード
+ +以下に親の取得を行う部分のコードを記述する
+idには工学部のidが、orgNodeにはAさんが所属している組織のidを持ったノードが入っている
++ String orgId = orgNode.getAttributes().getString("Organization-id");
+ if (id.equals(orgId))
+ return true;
+ parentOrgNodeOptional = parentIndex.get(orgNode);
+ if (parentOrgNodeOptional.isPresent())
+ orgNode = parentOrgNodeOptional.get();
+ else
+ return false;
+}while(true);
+
-
+
- orgNodeから組織のidを取得する +
- idと取得した組織のidを比較する +
- 一致した場合はtrueを、しなかった場合はorgNodeの親を取得する +
以上の処理を取得できる親ノードが無くなるまで行う
+ +ベンチマーク
+ +Jungle上にmaTrixの実装を行ったので、性能測定を行った
+測定はmongoDBとの比較とマルチプロセッサー上でのJungleの読み書き性能の2つを行った
+木構造をそのまま格納できること、属性名を指定することで属性値が取得できるなど、Jungleと似た特徴を持っているmongoDBを比較対象に選択した
+ +測定環境
+ +今回の測定は以下の環境で行った
+mongoDBとの比較
-maTrixのポリシーファイルのInterpreter
-Jungle上での許認可判断は、組織構造とポリシーファイルを参照して行う
-引数にポリシーファイルと、誰が(subject)、何に(Resource)、どうするか(Action)を取る
-返り値は、許可(Permit) or 拒否(Deny)がある
-実際にJungleの上で許認可判断が行えるようになった
+1万人のデータをmongoDBとJungleに格納し、データの読み込みにかかる時間の測定を行った
+各DBに挿入するデータは以下のような構造を持つ
++
mongoDBとの比較
+ +mongoDBでのデータの読み込みは以下のように行った
++ var roleId = personData.roleId
+
dbからpersonIdがp:9のuserを取得する
+取得したuserのroleIdを取得する
+ +mongoDBとの比較
+ +Jungleのデータの読み込みは以下のように行った
++ String nodeId = node.getAttributes().getString("Person-id");
+ if (nodeId.equals("p:9"))
+ return true;
+ return false;
+ }, "Person-id", "r:9");
+if (it.hasNext()) {
+ TreeNode targetNode = it.next();
+ String targetRoleId = targetNode.getAttributes().getString("roleId");
+}
+
+
TreeからpersonIdがp:9のノードを取得する
+取得したノードからroleIdを取得する
mongoDBとの比較
+ -maTrixのポリシーファイルのInterpreter
-Jungle上での許認可判断は、組織構造とポリシーファイルを参照して行う
-引数にポリシーファイルと、誰が(subject)、何に(Resource)、どうするか(Action)を取る
-返り値は、許可(Permit) or 拒否(Deny)がある
-実際にJungleの上で許認可判断が行えるようになった
++
Jungleの方がmongoDBより高速で動いた理由として、
通信の有無が大きい
mongoDBはMongoShellからデータベースにアクセスする際に
通信を行っている
それに対しJungleは、通信を行わないため高速に動作する
+また、データへのアクセスもmongoDBは
ディスクにあるデータに対しmmapを用いて行う
Jungleは初めからメモリにあるデータにアクセスする
+その部分も差が出た理由の１つである
+その結果JungleはmongoDBの約500倍の性能が出ている
マルチプロセッサー上でのJungleの読み書き性能
-今後の課題
--
今は、maTrixのデータ構造をそのまま格納しているため、Jungleに合ったデータ構造を設計する
+Jungleがマルチプロセッサ上で性能が出るか測定を行った
+複数スレッドからJungleに読み込みだけを行った場合と、1スレッドだけ書き込みを行い続け、残りのスレッドで読み込み行った場合で測定を行った。
+ ++
Jungleでは、書き込みと読み込みを同時に行っても
性能低下はおこらなかった
ハイパースレッディングに引っかかるまでは
リニアに性能が出ている
書き込みと読み込みを同時に行った場合、
読み込みのCPUCOUNTが2の時だけ性能が出ていない
これは、書き込みを連続で行っているため
読み込みと書き込みで競合が起きている
しかし読み込みのスレッドが増えると
読み込みが優先されるので性能が出るようになっている
読み込みと書き込み同時に行っている方が
CPUCOUNT11で性能上昇が止まっているのは
書き込みに1スレッド使用しているからである
考察
+ +性能評価では、JungleのほうがMongoDBより高速に動いたが、全てのアプリケーションにおいてJungleの方が早いわけではない
+Jungleは、木構造の形と使われ方がアルゴリズム的に一致している場合に性能が出る
+ +Jungleに向いているアプリケーション
+ +Jungleは、書き込み時の処理が木の大きさで変わる
+そのため、比較的小さな木にデータがたくさんあり、木の深い部分に対し変更があまり行われないアプリケーションが得意
+また、書き込みより読み込みを重視したDBであるため、読み込みが多いアプリケーションが性能が出る
+そのため、Jungleの上に構築するアプリケーション例としてBBSやWEBページなどがある
+ +Jungleに不向きなアプリケーション
+ +逆に、１つの大きな木に対し変更が頻繁に行われるようなアプリケーションは向いていない
+そういった場合、木を分割して複数の小さな木にすることで性能を上げることは可能である
+しかし、木を分割するための設計手法がまだ無いので、設計手法の確立は今後の課題である
今後の課題
-まとめ
-Jungle上で実用アプリケーションを構築できた
-その際に必要だった機能をJungleに追加した
-実際にポリシーファイルを読み込み許認可を行えた
+1. RDBとの比較
+もともとmaTrixはRDB上で動いているアプリケーションなので、RDB版maTrixとの性能測定を行いたい
+2.データの書き出し部分の改良
+Jungleはデータをディスクに書き出すことが可能である
+書きだしたデータを読み込む機能もあるのでトラブルが発生し、Jungleが強制終了されても元の状態に復旧できる
+しかし、今の実装は、データの書き出しはcommit時に毎回行っているため書き出しが非効率的である
+できれば複数回分の変更をバッファリングしておいて一気に書き出しを行いたい
+また、ある値を行ったり来たりするような、書き出す必要が無いデータもあるため、書き出す部分の最適化を行う必要がある
+ +今後の課題
+ +3.過去のデータの掃除
+Jungleは非破壊でデータを保持し続けるため、非常に多くのメモリを消費する
+ある程度のタイミングで過去のデータをメモリから掃除する必要がある
+しかし、データを掃除するタイミングは、Jungle上に実装するアプリケーションによって変わるため、自明ではない
+そこを含め、データを掃除するAPIの設計を行う必要がある
+4.分散環境でのmaTrixの構築
+Jungleはもともと分散データベースである
+分散版Jungle上にmaTrixを構築し、性能測定を行いたい
今後の課題
+ +5.設計手法の確立
+Jungleは木構造のデータをそのまま格納できる
+木のサイズが大きいと、データ更新の負荷が大きくなるため分割を行う必要がある
+分割を行った木同士の参照はIdを用いた間接的なものになる
+このようにJungleはRDBと異なり格納するデータの自由度が大きい
+なのでJungleの設計手法を確立させる必要がある
+ +まとめ
+ +当研究室で開発している非破壊的木構造データベースJungle上に許認可管理アプリケーションmaTrixを実装した
+その際必要になった検索APIやIndexの実装を行った
+またFunctionalJavaは性能が出なかったので、非破壊TreeMapを自作した
+その結果Jungleの性能は劇的に上昇した
+性能測定ではmongoDBより高速に動き、マルチプロセッサ上でも並列に動作した
+ +