Mercurial > hg > Papers > 2016 > tatsuki-prosym
view Slide/prosym.md @ 61:86c066e69a2f
fix description.
| author | Kazuma Takeda |
|---|---|
| date | Sun, 25 Dec 2016 17:40:41 +0900 |
| parents | 6eb64c475d57 |
| children | d5ec56df0230 |
line wrap: on
line source
title: ソフトウェア内部で使用するのに適した木構造データベースJungle author: Tatsuki Kanagawa, Kazuma Takeda, Shinji Kono profile: 琉球大学 lang: Japanese code-engine: coderay # はじめに プログラムからデータを分離して扱うデータベースには、 プログラム中のデータ構造とRDBの表構造のずれにより、<u>インピーダンスミスマッチ</u>という問題がある。 データベースのレコードをプログラム中のオブジェクトとして使える<u>OR Mapper</u>や、 データベース自体も、表に特化したKey Value Storeや、Jsonなどの不定形のデータ構造を格納するように機能拡張されてきている。 しかし、プログラム中のデータは複雑な構造をメモリ上に構築しており、これらの方法でもまだギャップがある。 # インピーダンス・ミスマッチ プログラム中のデータ構造とRDBの表構造には大きなギャップがある。これはインピーダンスミスマッチと呼ばれている。 例えばRPGゲーム中のユーザが持つアイテムという単純なものでも、RDBではユーザとアイテムの組をキーとする巨大な表として管理することになる。 プログラム中では、ユーザが持つアイテムリストという簡単な構造を持つが、データのネスト構造を許さない第一正規形を要求するRDBとは相容れない。 # O/R Mapper データベースのレコードをプログラム中のオブジェクトとして使える。 オブジェクトに対する操作を行うとORMapperがSQLを発行し、処理を行ってくれる。 PythonのpeeweeやRubyのActiveRecordなどスクリプト言語にもある。 しかし、レコードをプログラム中のオブジェクトに対応させるOR Mapperという技術では、インピーダンスミスマッチを本質的には解決することはできない。 # 問題点 MySQLやPosgreSQLなどは、Jsonなどの不定形のデータ構造を格納するように機能拡張されるようになってきた。 しかし、不定形の構造の変更をトランザクションとして、どのように処理するかはJsonの一括変更という形で処理されてしまっており、 並列処理が中心となってきている今のアプリケーションには向いていない。 つまり、この拡張はRDBよりの拡張であり、 並列処理を含むプログラミングからの要請とのミスマッチが残っている。 データベース自体も、表に特化したKey Value Storeや、Jsonなどの不定形のデータ構造を格納するように機能拡張されてきている。 その例としてCassandraや、mongoDBが挙げられる。 しかし、プログラム中のデータは複雑な構造をメモリ上に構築しており、これらの方法でもまだギャップがある。 # 提案 当研究室ではこれらの問題を解決した煩雑なデータ設計が必要のないJungleデータベースを提案している。 トランザクションは木のルートをアトミックに入れ替えることで実現する。 また、木構造のデータの変更を非破壊的、つまり元の木を保存しつつ、新しい木を構築する方法を採る。 プログラムは、この木を内部のデータ構造として直接取り扱うことができるので、読み出し時にデータベースに問い合わせる必要がない。 また汎用の木構造を持つので、データベースを特に設計しなくても、あるがままの形で格納することが可能になっている。Jungleは分散構成も可能である。 まずはJungleの仕様部分から説明する。 # Jungleデータベース JungleデータベースはJavaで実装されている。 木構造型のデータベースで、プログラム上に直接木構造を構築する。 木は複数のノードの集合でできており、その木の集合によりJungleが構成されている。 ノードは自身の子のリストと属性名と属性値の組でデータを持つ。これはデータベースのレコードに値する。 通常のレコードと異なるのは、ノードに子どもとなる複数のノードがつくところである。 なお、親から子への片方向の参照しか持たない。 データの変更は一度生成した木を上書きせず、ルートから変更を行うノードまでコピーを行い、新しく木構造を構築する。 その際にルートをアトミックに入れ替える。 [](失敗時の具体的な意味Either) <div style="text-align: center;"> <img src="./images/nonDestractTreeEdit.pdf" alt="message" width="600"> </div> # Jungleの木 Jungleは複数の木を名前を利用して管理しており、名前により作成・編集・削除を行う。 ``` Java // Jungleに新しく木を生成する。木の名前が重複した場合、生成に失敗しnullを返す JungleTree createNewTree(String treeName) // JungleからtreeNameと名前が一致するtreeを取得する。名前が一致するTreeがない場合取得は失敗しnullを返す JungleTree getTreeByName(String treeName) ``` # Jungleの木 Jungleの例を記載する。 以下のコードは、Jungleの木を"TreeName"で生成し取得する。 ``` Java jungle.createNewTree("TreeName"); JungleTree tree = jungle.getTreeByName("TreeName"); ``` # TreeNode Jungleが保持している木は、複数のノードの集合で出来ている。 ノードは、自身の子のListと属性名と属性値の組でデータを持つ。 ノードに対するアクセスは、TreeNodeクラスに記述されているAPIを用いて行われる。 ``` Java // ノードの子供を扱うChildrenオブジェクトを返す Children getChildren() // ノードが保持しているデータを扱うAttribteオブジェクトを返す Attribute getAttribute() ``` # Eitherクラス Jungleでは例外を投げる時にEitherクラスを用いて行う。 - 失敗時はA - 成功時はB を包んで返す。 以下に例を記述する。 ``` Java Either<Error,TreeNode> either = children.at(2); if (either.isA()) throw new IOException(); TreeNode child = either.b(); ``` # JungleのAPI Jungleの例を記載する。 以下のコードは、ルートノードの2番目の子どもから、属性名"name"とペアになっている属性値を取得する。 ``` Java JungleTree tree = jungle.getTreeByName("TreeName"); TreeNode root = tree.getRootNode(); Children children = root.getChildren(); Either<Error,TreeNode> either = children.at(2); if (either.isA()) throw new IOException(); TreeNode child = either.b(); Attribute attribute = child.getAttribute(); String value = attribute.getString("name"); ``` # Jungleの木の編集 Jungleの木の編集はJungleTreeEditorクラスを用いて行われる。 JungleTreeEditorクラスには編集を行うために、定義されているAPIを記述する。 また、ノードを指定して編集を行う際に<u>NodePathクラス</u>を用いる。 # NodePath Jungleでは、木のノードの位置をNodePathクラスを使って表す。 NodePathクラスはルートノードからスタートし、対象のノードまでの経路を、数字を用いて指し示すことで対象のノードの場所を表す。 また、ルートノードは例外として-1と表記される。 <div style="text-align: center;"> <img src="./images/NodePath.pdf" alt="message" width="400"> </div> # ノードの追加、削除 ``` Java // 変数pathで指定した場所にある、ノードの子供の変数posで指定した位置子ノードを追加 Either<Error, JungleTreeEditor> addNewChildAt( NodePath path, int pos) // 変数pathで指定した場所にある、ノードの子供の変数posで指定した位置の子ノードを削除 Either<Error, JungleTreeEditor> deleteChildAt( NodePath path, int pos) ``` # ノードに対してデータの挿入 ``` Java // 変数pathで指定した場所にあるノードに、属性名 変数key 属性値 変数valueのペアで値を挿入 Either<Error, JungleTreeEditor> putAttribute( NodePath path, String key, ByteBuffer value) // 変数pathで指定した場所にあるノードが持つ、属性名 変数keyとペアで保存されているデータを削除 Either< Error, JungleTreeEditor> deleteAttribute( NodePath path, String key) ``` # 移動、ルートノードの追加、コミット ``` Java // 変数pathで指定した場所にある、ノードの変数numで指定された位置の子供を変数moveの方向に移動 Either<Error, JungleTreeEditor> moveChild( NodePath path, int num, String move) // ルートノードの上に新しいルートノードを追加。線形の木を作る際に使用することで計算量をO(n)からO(1)にできる Either<Error, JungleTreeEditor> pushPop() // 木へ行った変更をコミット。自分が編集を行っていた間に、他のJungleTreeEditorクラスによって木が更新されていた場合、コミットは失敗 Either<Error, JungleTreeEditor> success() ``` # JungleのAPI Jungleの木を編集する例を記載する。 以下のコードは木からEditorを取得し、変数editorNodePathで指定したノードに新しい子ノードを追加したものである。 ``` Java JungleTreeEditor editor = tree.getTreeEditor(); DefaultNodePath editNodePath = new DefaultNodePath(); Either<Error, JungleTreeEditor> either = editor.addNewChildAt(editNodePath, 0); if (either.isA()) throw new IllegalStateException(); editor = either.b(); editor.success(); ``` # Jungle を用いたアプリケーション Jungleの特性を生かし、アプリケーションを構築した。 - maTrix - Rendering Engine # maTrix 実際に企業で運用されている許認可管理アプリケーション。 人物、役職、役割、権限、組織の木構造のデータとポリシーファイルを持つ。 maTrixのデータ構造は以下のようになっている。 <div style="text-align: center;"> <img src="./images/TreePersonJungle.pdf" alt="message" width="400"> </div> # ポリシーファイル データに対するアクセス要求が許可されるか否認されるかを判断するためのルール、 - 誰が(Target) - 何を(Resource) - どうできるか(Action) の３つの要素を持っている。 maTrixはアクセス要求に応じたポリシーファイルを参照することで許認可の判断を行う。 ポリシーファイルは組織構造中の人や役職をidを用いて参照し表現している。 - 許認可を下すためには、その人がどこの組織に所属して、その役割がどの権限を持っているかを返す検索が必要。 # maTrixでは - 組織構造は、それぞれの木構造がidを用いた参照を行う - 過去のアクセス要求を全て保存する [](なんでアクセス要求を保存する必要があるのか) - ポリシーファイルを用いた場合の人物検索 [](ポリシーファイルが必要な部分) # Indexの実装 [](indexがなんで必要かを入れる必要がある。) Jungleは、非破壊的木構造というデータ構造上、過去の版の木構造を全て保持しているため、全ての版に独立したIndexが必要となる。 そのため、前の版のIndexを破壊すること無く、Indexを更新する必要があった。 既存のTreeMapでは、一度Indexの複製を行った後更新する必要があったため、Indexの更新オーダーがO(n)となっていた。 よって、非破壊TreeMapを自作し、それを用いてIndexの実装を行った。 このTreeMapは、Jungleと同じようにルートから変更を加えたノードまでの経路の複製を行い、データの更新を行った際、前の版と最大限データを共有した新しいTreeMapを作成する。 Jungleとの違いは、木の回転処理が入ることである。 # Indexの実装 これにより複数の版全てに対応したIndexをサポートすることが可能になった。 以下にJungleにおけるIndexの型を記述する ``` Java TreeMap<String key,TreeMap<String attribute, List<TreeNode> node> index> indexMap ``` JungleのIndexはIndexMap内に保持されている。 属性名でIndexMapにgetを行うと、対応したIndexが取得できる。 取得したIndexに属性値でgetを行うと、ノードのリストが返ってくる。 # Indexの実装 Indexから属性名 name 属性値 Kanagawa のデータを持つ、ノードのIteratorを取得するサンプルコードを記述する。 ``` Java Optional<TreeMap<String, List<TreeNode>>> indexOp = indexMap.get("name"); if (!indexOp.isPresent()) return new NulIterator<TreeNode>(); TreeMap<String, List<TreeNode>> index = indexOp.get(); Optional<List<TreeNode>> nodeListOp = index.get("kanagawa"); if (!nodeListOp.isPresent()) return new NulIterator<TreeNode>(); // 持っていた場合OptionalオブジェクトからノードリストのIteratorを返す。 return nodeListOp.get().iterator(); ``` ・属性名"name"でgetを行うと対応したIndexがOptionalに包まれて返ってくる。 ・中身が入っているか確認、入っていた場合Indexを取得する。 ・取得したIndexに、検索で使用する属性値"kanagawa"でgetを行う。属性名"name" 属性値kanagawaの値を持つノードのリストが、Optionalクラスに包まれて返ってくる。 ・中身が入っているか確認、入っていた場合OptionalオブジェクトからノードリストのIteratorを返す。 # 検索APIの実装 Indexを実装したことにより、Idを用いた組織構造の表現は可能になった。 しかし、組織構造に問い合わせを行う検索APIが実装されていなかったため、属性名key 属性値valueの組で検索を行うAPIの実装を、木の走査を行うTraverserクラス内に、lambda式を用いて行った。 以下に検索を行う関数findの定義を記述する。 ``` Java public Iterator<TreeNode> find(Query query, String key, String searchValue); ``` 関数findは引数に、Query query、String key、String valueの3つの引数を取り、条件に一致したノードのIteratorインタフェースを返す。 第1引数には、探索の条件を記述する関数boolean comdition(TreeNode)を定義したInterface Queryを、第2、第3引数の、String key、String ValueはIndexを用いた絞込みに使用する。 # 関数findを用いた検索APIのサンプルコード ``` Java InterfaceTraverser traverser = tree.getTraverser(true); Iterator<TreeNode> resultNodeIterator = traverser.find((TreeNode node) -> { String personId = node.getAttributes().getString("Personid"); if (personId == null) return false; return personId.equals("p:2"); }, "element", "Person"); ``` ・Traverserクラスは木の走査を行う。まずは木から取得してくる。 ・Indexからfindの第２、第３引数である、属性名"element" 属性値"Person"の組のノードを取得し、Queryに渡す。 ・引数のノードから関数getAttributes().getString("Personid")で属性名Personidとペアになっている属性値を取得する。 ・属性値がnullだった場合、このノードには属性名がPersonidの組のデータは存在しないので、falseを返し次のノードの評価を行う。 ・属性値がnullでなかった場合、p:2と一致するかどうかを調べ結果を返す。 # HTML Rendering Engine Jungleの特性を生かしたRendering Engineを開発した。 今回は例題として、日記(ブログ)を選択した。 # 構造 このレンダリングエンジンでは以下の２つの木からなる。 木同士を参照しながら、レンダリングしていく。 - <u>LayoutTree</u> 出力する形式が記述された木 - <u>ContentTree</u> 出力するデータが記述された木 # ContentTree RenderingEngineではContents Treeに以下のように出力するデータを格納した。 <div style="text-align: center;"> <img src="./images/contentTree.pdf" alt="message" width="400"> </div> - RootNodeはContentのtitle、日時、レンダリングする時に参照するLayoutTreeのNodeNameを持つ。 そして子ノードが日記の本文等のデータを持つ。 # Nodeが持つAttribute NodeAttributeにノードが保持しているContentsの一覧を以下に記述する。 <table border="1"> <tr> <td>component</td> <td>レンダリングする際に参照するLayoutTreeのNodeName</td> </tr> <tr> <td>title</td> <td>日記のタイトル</td> </tr> <tr> <td>date(rootNode)</td> <td>日記の日時</td> </tr> <tr> <td>type</td> <td>そのノードが保持しているContextType。 text(日記本文) or image(画像データ)</td> </tr> <tr> <td>body</td> <td>日記の本文</td> </tr> <tr> <td>date(image)</td> <td>画像の保存日時</td> </tr> <tr> <td>fileName</td> <td>画像の名前</td> </tr> </table> # LayoutTree LayoutTreeには次のようにデータを格納した。 <div style="text-align: center;"> <img src="./images/layoutTree.pdf" alt="message" width="400"> </div> # LayoutTreeの主な要素 <table border="1"> <tr> <td>NodeName</td> <td>ノードの名前。ノード同士の参照時に用いられる。例外としてルートノードだけはdisplayinformationという名前を持つ</td> </tr> <tr> <td>displayComponent</td> <td>参照するノードの名前</td> </tr> <tr> <td>Name</td> <td>この属性名で取得できる値を持つNodeNameを持つノードを参照する</td> </tr> <tr> <td>use</td> <td>このノードが、どのContentsに対してのLayoutを持つかを記述するタグ。表\ref{tag}にタグとContentsの対応を記述する</td> </tr> <tr> <td>その他</td> <td>css等と同じ様な記述を行う。 例 属性名font 属性値fontSize</td> </tr> </table> # multiComponent Layoutが複数のComponentを参照する際は以下のような木構造を構築する。 <div style="text-align: center;"> <img src="./images/multiComponent.pdf" alt="message" width="300"> </div> 上の例ではdiaryMulti@componentはdiaryText@componentとdiaryImage@componentを参照している。 # レンダリングの流れ ContentTreeとLayoutTreeの２つを使用したレンダリングの流れを記述する。 ・ContentsTreeのルートノードは、属性名 component 属性値 Multi@Componentの組を持つので、LayoutTreeのNode2を参照する。 <div style="text-align: center;"> <img src="./images/multiComponent01.pdf" alt="message" width="400"> </div> # レンダリングの流れ ・Node2は自身のNodeNameしか持たないので、子ノードであるNode3,Node4に記述されているデータの参照を行う。 <div style="text-align: center;"> <img src="./images/multiComponent02.pdf" alt="message" width="400"> </div> # レンダリングの流れ ・Node3は属性名 displayComponentName、属性名 diaryImageの組を持つため、NodeNameがdiaryText@componentのノードを参照している。 <div style="text-align: center;"> <img src="./images/multiComponent04.pdf" alt="message" width="400"> </div> # レンダリングの流れ ・レンダリングエンジンは、参照先のノードに記述されたルールに則ってHTMLを生成する。 ・Node3は、これ以上データを持たないため、次はNode4を参照する。 # レンダリングの流れ ・Node4は属性名 displayComponentName 属性名 dialyText@Componentの組を持つため、NodeNameがdialyText@Componentのノードを参照している。 <div style="text-align: center;"> <img src="./images/multiComponent05.pdf" alt="message" width="400"> </div> ・レンダリングエンジンは、参照先のノードに記述されているルールに則ってhtmlを生成する。 # 設計 Jungleは凡用の木構造を持つので、データベースを特に設計しなくても、あるがままの形で格納することができる。 しかし、設計を行うことで効率的に木構造を扱うことが可能になる。 同じデータを格納した２つの木の一部を記述する。 # コードとギャップのある格納 <div style="text-align: center;"> <img src="./images/badLayoutTree.pdf" alt="message" width="400"> </div> このTreeはレンダリングする際に必要な値が複数のノードに分散されて保存されている。そのためすべてのノードを参照し、値を集める処理を行う必要があり、コードの可読性が下がる。さらに余分な処理も増えてしまう。 # コードとギャップのない格納 <div style="text-align: center;"> <img src="./images/goodLayoutTree.pdf" alt="message" width="400"> </div> このTreeは、１つのノードにレンダリングに必要な値が全て格納されている。 そのため、レンダリングを行う際、複数のノードをまたぐ必要が無く、簡潔にコードを書くことができる。 # 性能評価 先ほどのギャップのあるコードの木と、ギャップのないコードの木を使った2つのrenderingEngineの性能測定を行い、木の構造が実行速度にどれだけ影響するかを確かめる。 測定は100000回のレンダリングリクエストを処理するまでの時間の比較で行う。 <div style="text-align: center;"> <img src="./images/benchMark.pdf" alt="message" width="400"> </div> 測定結果より、Jungleデータベースは、設計を行うとプログラム内のデータ構造とギャップがなく、高速に動作するプログラムを簡潔に記述できるようになる。 # まとめ 本研究では非破壊データベースJungleに許認可管理アプリケーションmaTrix、HtmlRenderingEngineの2つを実装した。 許認可管理アプリケーションmaTrixの実装を通して、Jungleに実用データベースとしての表現力、機能の十分性、実用的な性能があるか実証実験を行った。 maTrixは複数の木がお互いにIdを用いた参照を行い組織構造を表現していたが、JungleではIndexを用いた参照で表現した。 また、測定の結果mongoDBの約500倍高速に動作した。 これはJungleがon memoryなのに対し、MongoDBはmmapを用いてデータにアクセスしているからである。 maTrixの実装により、Jungleは、実用アプリケーションを実装できるほどの表現力、機能、性能があることを証明できた。 最後に、Jungleを使った例題アプリケーションとしてRenderingEngineの実装を行った。 その際Jungleのデータ構造でプログラムの処理量、コードの可読性が異なることがわかった。 性能測定では、データ設計を行った木構造を利用したほうが高速に動作した。 これはノードをたどる必要が無いからである。 しかし、単純に1つのノードにデータを記述するとコードの可読性が落ちてしまうこともあるため、可読性と速度を両立できる設計手法を確立する必要があることがわかった。 JungleはRDBと異なり格納するデータの自由度は大きい。 どのようなデータ構造も、設計を行わず格納できる。 しかし、十分なパフォーマンスを出すためには、データを最適化する必要がある。 また、最適な木構造はアプリケーションによって違うため、Jungleの設計手法を確立させる必要がある。 [](プロシン発表時間 セッション4 1/7 8:50 - 10:10)