Mercurial > hg > Papers > 2016 > tatsuki-prosym
view Slide/prosym.md @ 53:bc2f679ff4d8
fix purpose of resaerch.
author | Kazuma Takeda |
---|---|
date | Fri, 23 Dec 2016 00:28:06 +0900 |
parents | b37ab31d5f12 |
children | 51a2d20e57bf |
line wrap: on
line source
title: ソフトウェア内部で使用するのに適した木構造データベースJungle author: Tatsuki Kanagawa author: Kazuma Takeda author: Shinji Kono profile: 琉球大学 lang: Japanese code-engine: coderay # データベースの歴史 コンピュータでは常に簡略化が行われてきた。 その中でデータベースとして採用されてきたのが # 階層型データベース データの関係性をツリー構造で定義し、プログラム内部ではその定義を利用してデータへのアクセスする。 しかし、新しい木構造を作るたびにデータ重複が発生し、冗長化が問題となった。 そこで採用されたのが # ネットワーク型データベース CODASYL型データモデルを準拠に作られたデータベース。 階層型データベースのデータ冗長化を排除したもの。 データをノード単位で整理し、データ間の関係性を定義する。 しかし、データの関係性が複雑になっているため、データのネットワーク構造を安易に変更できないと言った問題がある。 そこで開発されたのが # リレーショナルデータベース 階層型データベースやネットワーク型データベースの持つ問題点を解決し、データとプログラムの独立性を高めたデータベース。 しかし、プログラムからデータを分離して扱うデータベースにはデータ構造とRDBの表構造のインピーダンス・ミスマッチという問題がある。 # インピーダンス・ミスマッチ もともとは電気工学の言葉。 抵抗の異なる素材の間に電磁波を流すと、境界面で反射が起こって効率よく伝達できないことを意味する。 つまり、データベースの世界ではオブジェクト指向プログラミングとリレーショナルデータベースの間の不一致で起こることをいう。 (例があった方がいいかな?) # 近年 NoSQLと呼ばれるデータベースが開発、利用されている。 ## Key-Value Store データをKeyとValueのHash形式でもつ。 完全一致検索しかできないが高速で動作する。 その例としてCassandraがある。 ## ドキュメント指向データベース スキーマが必要ななく使用できる。 複雑な検索条件でデータを取得できる。 その例としてMongoDBがある。 # Mongo Database ドキュメント指向型のデータベースである。 NoSQLのパフォーマンス、スケーラビリティに優れている。 なお、パフォーマンスを向上させるため、トランザクション、リレーショナルと言った機能は実装されていない。 Key-Value Storeでは完全一致検索しかできないが、 RDBのような検索クエリの機能を持たせることで複雑な検索が可能になっている。 # 現在の課題 コンピュータのCPU性能は格段によくなった。しかし、これ以上CPUの性能が大幅に向上するとは思えない。 一方、データは膨大化している。 CPUを物理的に増やすことで、解決はできるが、有限な物であるため一時的な解決方法にしかならない。 そこで並列処理という手法が考えられる。 トランザクションの機能を排除した、MongoDBでは並列で動くアプリケーションには向いていない。 # 提案 今回トランザクションの機能を備え、スケーラビリティにも優れた木構造データベースJungleを提案する。 トランザクションは木のルートをアトミックに入れ替えることで実現する。 また、木構造のデータの変更を非破壊的、つまり元の木を保存しつつ、新しい木を構築する方法を採る。 # この発表では - Jungleデータベースの構造 - WebServer(BBS) - maTrix - RenderingEngine - まとめ Jungleデータベースの構造とこれを用いたアプリケーション、実装時に発生した問題と解決方法について解説する。 # Jungleデータベース JungleデータベースはJavaで実装されている。 木構造型のデータベースで、プログラム上に直接木構造を構築する。 木は複数のノードの集合でできており、その木の集合によりJungleが構成されている。 ノードは自身の子のリストと属性名と属性値の組でデータを持つ。これはデータベースのレコードに値する。 通常のレコードと異なるのは、ノードに子どもとなる複数のノードがつくところである。 なお、親から子への片方向の参照しか持たない。 []( 理由はノードをコピーするときにその参照までもコピーしないといけないし、特定のノードから探って行くので子は誰が知る必要はない) []( ノードの図入れた方が良い?) データの変更は一度生成した木を上書きせず、ルートから変更を行うノードまでコピーを行い、新しく木構造を構築する。 その際にルートをアトミックに入れ替える。 [](失敗時の具体的な意味Either) <div style="text-align: center;"> <img src="./images/nonDestractTreeEdit.pdf" alt="message" width="600"> </div> 以降はJungleの構造をAPIとともに紹介。 # 木の生成 Jungleは複数の木を名前を利用して管理しており、名前により作成・編集・削除を行う。 Jungleクラスの木の生成、管理を提供するAPIは以下のようになっている。 ``` Java /* If the name of the tree duplicates, it fails and returns null */ JungleTree createNewTree(String treeName); /* If there is no matching Tree name, it fails and returns null */ JungleTree getTreeByName(String treeName); ``` # 木のノード Jungleの木は、複数のノードの集合でできている。 ノードは、自身の子のListと属性名と属性値の組でデータをもつ。 ノードへTreeNodeクラスにより提供しているAPIでアクセスする。 ``` Java Children getChildren(); Attribute getAttribute(); ``` # ノードのChildren Childrenクラスで提供されているAPIでTreeNodeにアクセスできる。 ``` Java // Children.java int size(); Either<Error, TreeNode> at(int num); ``` ## Eitherクラス TreeNodeを取ってくる場合Eitherで比較する。 ``` Java Either<Error, JungleTreeEditor> either = tree.getRootNode ().getChildren ().at (0); if(either.isA()) { // throw Exception } TreeNode node = either.b(); ``` # ノードのAttribute Attributeクラスで提供されているAPIでノードの値にアクセスできる。 ``` Java // Attribute.java ByteBuffer get(String key); String getString(String key); ``` # Jungle を用いたアプリケーション - maTrix - BBS - Rendering Engine - Unity # maTrix 実際に企業で運用されている許認可管理アプリケーション。 人物、役職、役割、権限、組織の木構造のデータとポリシーファイルを持つ。 maTrixのデータ構造は以下のようになっている。 <div style="text-align: center;"> <img src="./images/TreePersonJungle.pdf" alt="message" width="600"> </div> ## ポリシーファイル データに対するアクセス要求が許可されるか否認されるかを判断するためのルール、 - 誰が(Target) - 何を(Resource) - どうできるか(Action) の3つの要素を持っている。 maTrixはアクセス要求に応じたポリシーファイルを参照することで許認可の判断を行う。 ポリシーファイルは組織構造中の人や役職をidを用いて参照している。 - 許認可を下すためには、その人がどこの組織に所属して、その役割がどの権限を持っているかを返す検索が必要。 # maTrixでは - 組織構造は、それぞれの木構造がidを用いた参照を行う - 過去のアクセス要求を全て保存する - ファイルポリシーを用いた場合の人物検索 ## maTrixでのJungleの問題点 - JungleではIndexを持っていない - 検索部分がない # 改良 Indexをつけて、検索部分も実装した。 子から親への参照が必要になったのでParentIndexを実装した ## ParentIndex ノードを投げるとその親がReturnされる。 # 性能評価 mongoDBとの性能を比較した。 # BBS JungleTreeEditorは手動での変更には向いていない。 ブラウザ上で変更できるようにした。 仕様は以下の通りである。 - WebサーバJettyを利用し、 ServletによりViewを生成 - JungleDBをJettyに組み込む ## 木構造の表示 NodePathを除けば、通常のデータベースのレコードと同じである。 NodePathはURLのGetパラメータとして指定する。 ``` HTML http://localhost/showBoardMessage?bname=Layout&path=-1,0,2 ``` [](イメージしやすい図があれば良さそう) ## 木構造の編集 変更したいページに移動し、木を取得し、 データをPostすることでCreateもしくは、Updateを行う。 # HTML Rendering Engine Jungleの特性を生かしたRendering Engineを開発した。 今回は例題として、日記(ブログ)を選択した。 # 構造 - LayoutTree 出力する形式が記述された木 - ContentTree 出力するデータが記述された木 これら2つを参照しながらレンダリングを行う。 # Unity ゲームエンジンUnity上で動くデータベースとしてJungleをC#に書き換え、実装を行なった。 # まとめ 今回は... [](プロシン発表時間 セッション4 1/7 8:50 - 10:10)