title: ソフトウェア内部で使用するのに適した木構造データベースJungle author: Tatsuki Kanagawa, Kazuma Takeda, Shinji Kono profile: 琉球大学 lang: Japanese code-engine: coderay # はじめに プログラムからデータを分離して扱うデータベースには、 プログラム中のデータ構造とRDBの表構造のずれにより、インピーダンスミスマッチという問題がある。 データベースのレコードをプログラム中のオブジェクトとして使えるOR Mapperや、 データベース自体も、表に特化した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データベース JungleデータベースはJavaで実装されている。 木構造型のデータベースで、プログラム上に直接木構造を構築する。 木は複数のノードの集合でできており、その木の集合によりJungleが構成されている。 ノードは自身の子のリストと属性名と属性値の組でデータを持つ。これはデータベースのレコードに値する。 通常のレコードと異なるのは、ノードに子どもとなる複数のノードがつくところである。 なお、親から子への片方向の参照しか持たない。 データの変更は一度生成した木を上書きせず、ルートから変更を行うノードまでコピーを行い、新しく木構造を構築する。 その際にルートをアトミックに入れ替える。 [](失敗時の具体的な意味Either)
　message
# Jungleの木 Jungleは複数の木を名前を利用して管理しており、名前により作成・編集を行う。 ``` Java // Jungleに新しく木を生成する。木の名前が重複した場合、生成に失敗しnullを返す JungleTree createNewTree(String treeName) // JungleからtreeNameと名前が一致するtreeを取得する。名前が一致するTreeがない場合取得は失敗しnullを返す JungleTree getTreeByName(String treeName) ``` # Jungleの木 Jungleの木の生成するサンプルコードを記載する。 以下のコードは、Jungleの木を"TreeName"で生成し取得する。 ``` Java JungleTree tree = jungle.createNewTree("TreeName"); ``` # TreeNode Jungleが保持している木は、複数のノードの集合で出来ている。 ノードは、自身の子のListと属性名と属性値の組でデータを持つ。 ノードに対するアクセスは、TreeNodeクラスに記述されているAPIを用いて行われる。 ``` Java // ノードの子供を扱うChildrenオブジェクトを返す Children getChildren() // ノードが保持しているデータを扱うAttribteオブジェクトを返す Attribute getAttribute() ``` # ChildrenとAttribute Childrenクラスを利用し、ノードの子どもにアクセスする。 ``` Java // ノードが持っている子どもの個数を返す int size() // ノードが持つ子どもの中から、 変数numで指定された位置にある子ノードを返す at(int num) ``` Attributeクラスを利用し、ノードの保持する値にアクセスする。 ``` Java // ノードが持つ値から、属性名 keyとペアの属性値をByteBuffer型で返す ByteBuffer get(String key) // ノードが持つ値から、属性名 keyとペアの属性値をString型で返す String getString(String key) ``` # Eitherクラス Jungleでは例外を投げる時にEitherクラスを用いて行う。 - 失敗時はA - 成功時はB を包んで返す。 以下に例を記述する。 ``` Java Either 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 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を記述する。 また、ノードを指定して編集を行う際にNodePathクラスを用いる。 # NodePath Jungleでは、木のノードの位置をNodePathクラスを使って表す。 NodePathクラスはルートノードからスタートし、対象のノードまでの経路を、数字を用いて指し示すことで対象のノードの場所を表す。 また、ルートノードは例外として-1と表記される。
　message
# ノードの追加、削除 ``` Java // 変数pathで指定した場所にある、ノードの子供の変数posで指定した位置子ノードを追加 Either addNewChildAt( NodePath path, int pos) // 変数pathで指定した場所にある、ノードの子供の変数posで指定した位置の子ノードを削除 Either deleteChildAt( NodePath path, int pos) ``` # ノードに対してデータの挿入 ``` Java // 変数pathで指定した場所にあるノードに、属性名 変数key 属性値 変数valueのペアで値を挿入 Either putAttribute( NodePath path, String key, ByteBuffer value) // 変数pathで指定した場所にあるノードが持つ、属性名 変数keyとペアで保存されているデータを削除 Either< Error, JungleTreeEditor> deleteAttribute( NodePath path, String key) ``` # 移動、ルートノードの追加、コミット ``` Java // 変数pathで指定した場所にある、ノードの変数numで指定された位置の子供を変数moveの方向に移動 Either moveChild( NodePath path, int num, String move) // ルートノードの上に新しいルートノードを追加。線形の木を作る際に使用することで計算量をO(n)からO(1)にできる Either pushPop() // 木へ行った変更をコミット。自分が編集を行っていた間に、他のJungleTreeEditorクラスによって木が更新されていた場合、コミットは失敗 Either success() ``` # JungleのAPI Jungleの木を編集する例を記載する。 以下のコードは木からEditorを取得し、変数editorNodePathで指定したノードに新しい子ノードを追加したものである。 ``` Java JungleTreeEditor editor = tree.getTreeEditor(); DefaultNodePath editNodePath = new DefaultNodePath(); Either either = editor.addNewChildAt(editNodePath, 0); if (either.isA()) throw new IllegalStateException(); editor = either.b(); editor.success(); ``` # JungleでのIndexの実装 Jungleは、非破壊的木構造というデータ構造上、過去の版の木構造を全て保持しているため、全ての版に独立したIndexが必要となる。 そのため、前の版のIndexを破壊すること無く、Indexを更新する必要があった。 既存のTreeMapでは、一度Indexの複製を行った後更新する必要があったため、Indexの更新オーダーがO(n)となっていた。 よって、非破壊TreeMapを自作し、それを用いてIndexの実装を行った。 このTreeMapは、Jungleと同じようにルートから変更を加えたノードまでの経路の複製を行い、データの更新を行った際、前の版と最大限データを共有した新しいTreeMapを作成する。 # Indexの実装 これにより複数の版全てに対応したIndexをサポートすることが可能になった。 以下にJungleにおけるIndexの型を記述する ``` Java TreeMap node> index> indexMap ``` JungleのIndexはIndexMap内に保持されている。 属性名でIndexMapにgetを行うと、対応したIndexが取得できる。 取得したIndexに属性値でgetを行うと、ノードのリストが返ってくる。 # Indexの実装 Indexから属性名 name 属性値 Kanagawa のデータを持つ、ノードのIteratorを取得するサンプルコードを記述する。 ``` Java Optional>> indexOp = indexMap.get("name"); if (!indexOp.isPresent()) return new NulIterator(); TreeMap> index = indexOp.get(); Optional> nodeListOp = index.get("kanagawa"); if (!nodeListOp.isPresent()) return new NulIterator(); // 持っていた場合OptionalオブジェクトからノードリストのIteratorを返す。 return nodeListOp.get().iterator(); ``` ・属性名"name"でgetを行うと対応したIndexがOptionalに包まれて返ってくる。 ・中身が入っているか確認、入っていた場合Indexを取得する。 ・取得したIndexに、検索で使用する属性値"kanagawa"でgetを行う。属性名"name" 属性値kanagawaの値を持つノードのリストが、Optionalクラスに包まれて返ってくる。 ・中身が入っているか確認、入っていた場合OptionalオブジェクトからノードリストのIteratorを返す。 # 検索APIの実装 属性名key 属性値valueの組で検索を行うAPIの実装を、木の走査を行うTraverserクラス内に、lambda式を用いて行った。 以下に検索を行う関数findの定義を記述する。 ``` Java public Iterator 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 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を開発した。 今回は例題として、日記(ブログ)を選択した。 # 構造 このレンダリングエンジンでは以下の２つの木からなる。 木同士を参照しながら、レンダリングしていく。 - LayoutTree 出力する形式が記述された木 - ContentTree 出力するデータが記述された木 # ContentTree RenderingEngineではContents Treeに以下のように出力するデータを格納した。
　message
- RootNodeはContentのtitle、日時、レンダリングする時に参照するLayoutTreeのNodeNameを持つ。 そして子ノードが日記の本文等のデータを持つ。 # Nodeが持つAttribute NodeAttributeにノードが保持しているContentsの一覧を以下に記述する。
component レンダリングする際に参照するLayoutTreeのNodeName
title 日記のタイトル
date(rootNode) 日記の日時
type そのノードが保持しているContextType。 text(日記本文) or image(画像データ)
body 日記の本文
date(image) 画像の保存日時
fileName 画像の名前
# LayoutTree LayoutTreeには次のようにデータを格納した。
　message
# LayoutTreeの主な要素
NodeName ノードの名前。ノード同士の参照時に用いられる。例外としてルートノードだけはdisplayinformationという名前を持つ
displayComponent 参照するノードの名前
Name この属性名で取得できる値を持つNodeNameを持つノードを参照する
use このノードが、どのContentsに対してのLayoutを持つかを記述するタグ。表\ref{tag}にタグとContentsの対応を記述する
その他 css等と同じ様な記述を行う。 例 属性名font 属性値fontSize
# multiComponent Layoutが複数のComponentを参照する際は以下のような木構造を構築する。
　message
上の例ではdiaryMulti@componentはdiaryText@componentとdiaryImage@componentを参照している。 # レンダリングの流れ ContentTreeとLayoutTreeの２つを使用したレンダリングの流れを記述する。 ・ContentsTreeのルートノードは、属性名 component 属性値 Multi@Componentの組を持つので、LayoutTreeのNode2を参照する。
　message
# レンダリングの流れ ・Node2は自身のNodeNameしか持たないので、子ノードであるNode3,Node4に記述されているデータの参照を行う。
　message
# レンダリングの流れ ・Node3は属性名 displayComponentName、属性名 diaryImageの組を持つため、NodeNameがdiaryText@componentのノードを参照している。
　message
# レンダリングの流れ ・レンダリングエンジンは、参照先のノードに記述されたルールに則ってHTMLを生成する。 ・Node3は、これ以上データを持たないため、次はNode4を参照する。
　message
# レンダリングの流れ ・Node4は属性名 displayComponentName 属性名 dialyText@Componentの組を持つため、NodeNameがdialyText@Componentのノードを参照している。
　message
・レンダリングエンジンは、参照先のノードに記述されているルールに則ってhtmlを生成する。 # 設計 Jungleは凡用の木構造を持つので、データベースを特に設計しなくても、あるがままの形で格納することができる。 しかし、設計を行うことで効率的に木構造を扱うことが可能になる。 同じデータを格納した２つの木の一部を記述する。 # コードとギャップのある格納
　message
このTreeはレンダリングする際に必要な値が複数のノードに分散されて保存されている。そのためすべてのノードを参照し、値を集める処理を行う必要があり、コードの可読性が下がる。さらに余分な処理も増えてしまう。 # コードとギャップのない格納
　message
このTreeは、１つのノードにレンダリングに必要な値が全て格納されている。 そのため、レンダリングを行う際、複数のノードをまたぐ必要が無く、簡潔にコードを書くことができる。 # 性能評価 先ほどのギャップのあるコードの木と、ギャップのないコードの木を使った2つのrenderingEngineの性能測定を行い、木の構造が実行速度にどれだけ影響するかを確かめる。 測定は100000回のレンダリングリクエストを処理するまでの時間の比較で行う。
　message
測定結果より、Jungleデータベースは、設計を行うとプログラム内のデータ構造とギャップがなく、高速に動作するプログラムを簡潔に記述できるようになる。 # まとめ 本研究ではJungleを使った例題アプリケーションとしてRenderingEngineの実装を行った。 その際Jungleのデータ構造でプログラムの処理量、コードの可読性が異なることがわかった。 性能測定では、データ設計を行った木構造を利用したほうが高速に動作した。 これはノードをたどる必要が無いからである。 しかし、単純に1つのノードにデータを記述するとコードの可読性が落ちてしまうこともあるため、可読性と速度を両立できる設計手法を確立する必要があることがわかった。 JungleはRDBと異なり格納するデータの自由度は大きい。 どのようなデータ構造も、設計を行わず格納できる。 しかし、十分なパフォーマンスを出すためには、データを最適化する必要がある。 また、最適な木構造はアプリケーションによって違うため、Jungleの設計手法を確立させる必要がある。 [](プロシン発表時間 セッション4 1/7 8:50 - 10:10)