プログラムからデータを分離して扱うデータベースには、プログラム中のデータ構造と表構造とのミスマッチという問題がある。
-データベースのレコードをプログラム中のオブジェクトとして使えるOR Mapperや、データベース自体も、表に特化したKey Value Storeや、Jsonなどの不定形のデータ構造を格納するように機能拡張されてきている。
-しかし、プログラム中のデータは複雑な構造をメモリ上に構築しており、これらの方法でもまだギャップがある。
+プログラム中のデータ構造には、構造体、オブジェクトなどがある。それらが、ポインタで結合されリストや木やグラフを構成する。一部はHashMapなどに格納される。
+一方でデータベースでは、平たんな表構造を持ち、KEY属性を用いて参照する。
+例えばゲーム中のアイテムのリストは、データ構造として容易に表現されるがRDBでは、関係を表すテーブルを用いて表現する必要がある。
+データ構造の変更は、並列に行われても整合性を維持するトランザクションである必要があるが、標準的なものは提供されていない。
+このようにプログラム中のデータ構造とデータベースの間にはギャップがある。これをインピータンスピスマッチいうことがある。
MySQLやPosgreSQLなどは、Jsonなどの不定形のデータ構造を格納するように機能拡張されるようになってきた。
+これまでに開発されてきたものには、 +
しかし、不定形の構造の変更をトランザクションとして、どのように処理するかはJsonの一括変更という形で処理されてしまっており、 並列処理が中心となってきている今のアプリケーションには向いていない。
-この拡張はRDBよりの拡張であり、 -並列処理を含むプログラミングからの要請とのミスマッチが残っている。
+特に木構造自体が大きくなる場合に問題がある。
データベース自体も、表に特化したKey Value Storeや、Jsonなどの不定形のデータ構造を格納するように機能拡張されてきている。
-その例としてCassandraや、mongoDBが挙げられる。
-しかし、プログラム中のデータは複雑な構造をメモリ上に構築しており、これらの方法でもまだギャップがある。
- -当研究室ではこれらの問題を解決するために木構造Jungleデータベースを提案している。
-Jungleは様々な構造のデータ(例えばXML/JSON/LIST)を木構造としてそのまま格納することが可能である。
-Jungleではデータの変更を非破壊的、つまり元の木を保存しつつ、新しい木を構築する方法をとる。
-これにより木を参照しながら処理するタスクと木を変更するタスクを並列に処理することができる。
-プログラムは、この木を変更されないデータ構造として直接取り扱うことができる。
-名前付きの複数の木をatomicに入れ替えるのがJungleの transactionとなる。
+プログラム中のデータ構造のうち木構造やリスト構造に着目する。
+データベースJungleはこれらを直接データベースとして取り扱い、マルチスレッドからの読み書きをトランザクションとして提供する。
+Jungleの木は、外部のノードあるいはディスクに複製され、持続性を提供する。
+複数の木の間の参照などの複雑な構造はノードのKey属性のIndexを使って実現する。
+Jungleでは、データ構造の並行処理が可能なように、データの変更を非破壊的に行う。
+木が変更されている間も、その前の版を安全に読み出すことができる。
Jungleはゲームなどのアイテムのリストをそのまま木構造に格納することができ、トランザクションと持続性を提供する。
+Jungleは様々な構造のデータ(例えばXML/JSON/LIST)を木構造としてそのまま格納することが可能である。
+決まった版の木は変更されないので、いちいち木を検索することなく木構造をそのままプログラムのデータ構造として用いることができる。
+以下では、Jungleの構成要素と木へのアクセス方法を説明する。
+木は複数のノードの集合でできており、その木の集合によりJungleが構成されている。
@@ -206,6 +219,19 @@Jungleでは木のノードの位置をNodePathを使って表す。
+ルートから対象のノードまでの経路を数字で指し示す。
+ルートノードは例外として-1と表記される。
+NodePathクラスを用いて[-1,1,2,3]を表している例を以下に貼る。
+ + +Jungleでは木のノードの位置をNodePathを使って表す。
-ルートから対象のノードまでの経路を数字で指し示す。
-ルートノードは例外として-1と表記される。
-NodePathクラスを用いて[-1,1,2,3]を表している例を以下に貼る。
- - -これまでに記述したAPIにより、Jungleはデータの書き込み、読み込みを行える。
-しかし、性能はあまり良いものではなかった。
-特にIndexを用いた検索が明らかに遅く、検索の手間がO(n^2)となっていた。
-本来ならIndexを使った場合の検索の手間はO(Log n)であるべきである。
+Jungle では、今まで Java 上で関数型プログラミングが行えるライブラリ、Functional Java の TreeMap を使用して、Index を実装していた。
-しかし、Functional Java の TreeMap は、採用しているアルゴリズムが悪かった。
-またコードの量も膨大であり、修正も困難だった。
-そこで、自分で、同じ機能を持つ 非破壊 TreeMap を実装することにした。
-TreeMap アルゴリズムは赤黒木を採用した。
- -Jungleは過去の版の木を全て保持している。
過去の木に対する検索もサポートしている。
-木の版毎にIndexを持っている必要がある
-破壊的TreeMapでは、木に更新が入るたびに新しいIndexを作り直す必要がある。
-Indexの更新の手間がO(n)になってしまう。
-非破壊TreeMapの場合、一度作られたTreeMapに対して編集を行うと、編集後のTreeMapを返す。
-その際、編集前のTreeMapのデータは破壊されることはない。
-また、過去のIndexとデータを共有している
-複数のversionのIndexがあっても、データの差分しかメモリは消費されない
-メモリの使用量を抑えつつ複数のversionでIndexを保持できる
+木の版毎にIndexを持っている必要がある。
+従来は破壊的TreeMapでIndexを実現しており、木に更新が入るたびに新しいIndexをO(n)で作り直す必要があった。
+実装した非破壊TreeMapでIndexを実装することにより、更新をO(log n)で行うことができるようになった。 +また、変更されない部分は過去の版と共有されるので、メモリ効率も改良された。
非破壊のTreeMapを実装したことにより、読み込みは極めて高速に行えるようになった。
-しかし、書き込みに関してはまだ十分な速度が出ていない。
-Jungleの木の編集時に特に問題になっているのは、主に次の三点である。
-以降これらの問題について述べていく。
+Jungleは木の編集時、ルートから編集を行う位置までのノードの複製を行う。
+そのため、木の編集の手間は木構造の形によって異なる。
+特に線形の木の場合、全てのノードの複製を行うため変更の手間がO(n)となってしまう。
+線形の木をO(1)で変更するPush/Pop操作とDifferential Jungle Tree操作の実装した。
JungleではIndexの更新を行う際、毎回新しいIndexを構築していた。
-その為、毎回O(n)のIndexの更新が入っていた。
-Indexの差分アップデートを実装することで、Indexの更新の手間をO(Log n)とする。
- -Jungleは木の編集を行う際、編集を行うノードからルートまでの経路のノードの複製を行う。
-そのため、編集後の木には存在しない、複製前のノードがIndexに残ってしまう。
-それらのノードをIndexから削除し、複製後のノードを登録する必要がある。
- -この図だと、Indexの更新時にroot、2、5をIndexから削除する必要がある。
-その後新しく作られたノードを登録することでIndexの更新は完了する
- -複製前のノードをIndexから削除するためには、編集を行ったノードを覚えておく必要がある。
-Editorの中に編集を加えたノードを格納するリストを定義した。
-Indexのアップデート時にリストを使用する。
+線形リストのルートの上にルートを付け加える操作(Push)はO(1)である。
+逆にルートを取り除き、その子供をルートにする操作(Pop)もO(1)である。
+これらにより、線形木を高速に操作することができる。
+Pushを連続で行うと、リストは逆順に構築される。
+複製前のノードは以下の手順で行われる。
-ノードD、Eを編集した後の、複製前のノードをIndexから削除する例を記述する。
-黒のノードは編集後の木に存在しないノード。
-赤のノードはIndexから削除が終了したノード。
-その他のノードは緑とする。
-編集前ノードのDelete前
- - -ノードDについての削除後
- - -ノードEについての削除後
- -このようにIndexからのノードの削除は行われる
- -Indexへのノードは以下の手順で行われる。
-ノードの登録は深さ優先探索と同じ順序で行っていく。
- -ノードD、Eを編集した後の、複製前のノードをIndexから削除する例を記述する。
-赤のノードはIndexに存在しないノード。
-緑のノードはIndexに追加されているノード。
-以下の図の場合、A、B，D、Eの順に登録され、Cで終了する。
- - - -Jungleは木の編集時、ルートから編集を行う位置までのノードの複製を行う。
-そのため、木の編集の手間は木構造の形によって異なる。
-特に線形の木の場合、全てのノードの複製を行うため変更の手間がO(n)となってしまう。
-Jungleは線形の木をO(1)で変更するPushPopの機能を持つ。
- -PushPopはルートノードの上に新しいルートを追加するAPIである。
-しかし、PushPopで構築した木は逆順になってしまう。
-そのため、正順の木を構築する際は使用できない。
- - -正順の木をO(1)で構築するために実装した。
-Differential Jungle Treeは木のバージョン毎に自身の木の最後尾のノードを持つ。
+木のノードの追加順の線形リストが必要な場合もある。例えばLogなどである。
+Differential Jungle Treeは木の最後尾のノードへのポインタを持つ。
+最後尾に新しいノードをAtomicに書き込む。ルートは、版ごとに最後尾のノードを保持しており、 +木自体は変更されるが、その版の木の長さの範囲では変更されていない。
+版ごとの最後尾を越えないようにアクセスすることで、線形木の非破壊性を維持することができる。
@@ -481,27 +367,17 @@Differential Jungle Treeを作成するためにJungleに新しいAPIを実装した。
+Differential Jungle Treeは、特別なAPIで作成する必要がある。
JungleTree createNewDifferenceTree(String treeName);
上記のAPIは、treeNameで指定した名前のDifferential Jungle Treeを構築する。
+差分木への追加を複数回行うと、複数回のトランザクション処理を行う必要がある。 +複数の追加をSub Treeに対して破壊的に行って、そのSub Treeを差分木へ追加することにより、トランザクションを一回で済ませることができるようにしている。
Differential Jungle Treeの木の編集は、Differential Jungle Tree Editorを用いて行う。
-既存のDefault Jungle Treeは、木の複製を作った後編集を行う。
-Differential Jungle Tree Editorは、自身がSub Treeを持っている。
-Sub Tree に対して編集を行う。
-Commit時に自身が保持している末尾ノードにSub TreeをAppendすることで木の編集を終了する。
-また、Diffirential Jungle Treeの編集は、Editorが持つSub Treeへの編集しか行えないため、一度Commitした木に対して変更を加えることはできない。
- -Differential Jungle Treeは末尾ノードを使って現在の木構造を表現している。
-過去の木に対してIndexを使わないで全探索を行った場合、既存の検索ではその版に存在しないはずのノードが取得できてしまう。
- - -以下の図の場合Tree Ver1を全探索すると、存在しないはずのノード３、４が取得できてしまう。
- - -この問題を解決するためにDifferential Interface Traverserを実装した。
-これは、末尾ノード以下を検索対象から取り除く検索を持つ。
-Indexを使った検索の場合、各版ごとに独立したIndexを持つため、Default Jungle Treeと同じ検索でも問題ない。
- -Differential Jungle Treeでは、過去の版の木に対して変更を加えた際に木の整合性が崩れてしまう問題もある。
-図の中の、過去の木であるTree ver1に対してノード5を追加してCommitした場合、新しい木Tree ver`2が生成される。
- - +Jungleは木の編集時、ルートから編集を行う位置までのノードの複製を行う。
+そのため、木の編集の手間は木構造の大きさにも依存している。
+バランスの取れた木構造を構築することで、編集の手間をO(log n)にすることは可能ではある。
+しかし、ユーザーが木の構造を把握しバランスを取るのは難しい。
+そこで、自動で木のバランスを取り、最適な木構造を構築する機能を持つRed Black Jungle Treeを実装した。
+Red Black Jungle Treeは、木構造を指定した作成を行うことはできないが、Key属性を用いて任意のノードにアクセスすることができる。
Tree ver`2に対してIndexを使わないで検索を行った場合、本来存在しないはずのノード3、４が検索対象に入ってしまう。
-これは、Tree ver1の末尾ノードが2つ子を持っているせいで発生する。
-この問題を解決するために、過去の木に対する変更は禁止した。
- - -Jungleは木の編集時、ルートから編集を行う位置までのノードの複製を行う。
-そのため、木の編集の手間は木構造の大きさにも依存している。
-バランスの取れた木構造を構築することで、編集の手間をO(Log n)にすることは可能ではある。
-しかし、ユーザーが木の構造を把握しバランスを取るのは難しい。
-そこで、自動で木のバランスを取り、最適な木構造を構築する機能を持つRed Black Jungle Treeを実装した。
-Red Black Jungle Treeは、自動でバランスを取ってしまうため、木構造の形でデータを表現することはできない。
- -Red Black Jungle Treeを作成するためにJungleに新しいAPIを実装した。
+Red Black Jungle Treeは、特別なAPIで作成する必要がある。
JungleTree createNewRedBlackTree(String treeName,String balanceKey);
上記のAPIは、treeNameで指定した名前のRed Black Jungle Treeを構築する。
また、第二引数のbalanceKeyを用いて木のバランスを取る。
-第二引数のbalanceKeyを使用して、検索することでO(Log n)で検索を行うことができる。
-なので、別途Indexを構築する必要はない。
Red Black Jungle TreeはIndexを持たないため既存の検索は使用できない。
-木の生成時に指定したbalanceKeyを使用して、O(Log n)で探索を行う検索を実装した。
-また、balanceKeyを使用しない場合は、既存のDefault Jungle Treeと同じで全探索を行うのでO(n)となる。
- -