# HG changeset patch # User kono # Date 1486807470 -32400 # Node ID 8d1f5ab7b420e47f205e85c5bc74b84197aeea62 # Parent cbc652b58d991784c99f8befc2c753f9b64b9e44 fix diff -r cbc652b58d99 -r 8d1f5ab7b420 abstract.tex --- a/abstract.tex Sat Feb 11 01:13:24 2017 +0900 +++ b/abstract.tex Sat Feb 11 19:04:30 2017 +0900 @@ -1,26 +1,36 @@ \begin{abstract} プログラムからデータを分離して扱うデータベースには、 -プログラム中のデータ構造と Relational DataBase(RDB) の表構造のインピーダンスミスマッチという問題がある。 +プログラム中のデータ構造と表構造とのインピーダンスミスマッチという問題がある。 データベースのレコードをプログラム中のオブジェクトとして使えるOR Mapperや、 データベース自体も、表に特化したKey Value Store、Jsonなどの不定形のデータ構造を格納するように機能拡張されてきている。 しかし、プログラム中のデータは複雑な構造をメモリ上に構築しており、これらの方法でもまだギャップがある。 -そこで当研究室では、これらの問題を解決した、煩雑な設計を行わずプログラム内部に木構造を格納できるデータベース Jungle を提案している。 -Jungleは、木構造の変更を非破壊的、つまり、元の木を保存しつつ、新しい木を構築する方法を取り、 -木のルートをアトミックに入れ替えることでトランザクションを実現する。 -プログラムは、この木を内部のデータ構造として直接取り扱うことができるので、読み出し時にデータベースに問い合わせる必要がない。 -Jungleは、全体の整合性ではなく、木ごとに閉じた局所的な整合性を保証している。 -また、整合性のある木同士をマージすることで新しい整合性のある木を作り出すことも可能であるため、データの伝搬も容易である。 - +そこで当研究室では、これらの問題を解決するためにプログラム内部に木構造を格納できるデータベース Jungle を提案している。 +Jungleは、木構造の変更を非破壊的に行う。 Jungleは、読み込みは高速に行える反面、書き込みの手間は木の形・大きさに依存しており、最悪の場合O(n)となってしまう。 また、Indexの構築も大幅なネックとなっていた。 -そこで、本研究では、Jungleの木の構築・編集機能の改善を行う。 -その後、実際にJungleを使用したアプリケーションを開発・運用する。 +そこで、本研究ではJungleの木とIndexの編集機能の改善を行う。 +また、実際にJungleを使用した複数のアプリケーションを作成し、 +PostgreSQLとMongoDBとの比較を行った。 -改善後行った性能測定では、木の編集機能の高速化を確認できた。 -また、PostgreSQL・MongoDBと読み込み速度の比較を行った。 -結果、これらのDB以上の性能を確認できた。 - -残された課題として木の設計手法の確立、 メモリ内にある木構造の破棄についての課題が確認された. \end{abstract} + +\chapter*{Abstract} + +Database which handles data from programs separately has an impedance mismatch problem. +Sevaral technologies are introduced such as OR Mapper which uses records as objects in a program, +Key Value Store(KVS) which is a specialized databases for tables, +storing Json tree structures in conventional Relational Databases. +Despite of these technologies, +it is not suffient to handle complex data strucutures in the program memories. + +In this paper, +Tree structured database Jungle is intruduced. +Jungle stores tree structures in the program and it modifies trees non-destructively, +which is suitable for parallel processings. +Jungle is very good at reading tree structures, +but updating tree structures may requires O(n) in worst case depending on configurations of the trees. +Updating indexies on the trees are also having computional complexity difficulities, +Sevaral improvements a presented and comparisons are shown to PostgreSQL and MongoDB +in Jungle applications. diff -r cbc652b58d99 -r 8d1f5ab7b420 databases.tex --- a/databases.tex Sat Feb 11 01:13:24 2017 +0900 +++ b/databases.tex Sat Feb 11 19:04:30 2017 +0900 @@ -1,17 +1,16 @@ %もう少し詳しく書く \chapter{既存のデータベース} -本章では、既存のデータベースの例として、PostgreSql・MongoDB・Cassandra・当研究室で開発しているJungle について記述する。 +本章では、既存のデータベースの例として、PostgreSQL・MongoDB・Cassandra・当研究室で開発しているJungle について記述する。 -\section{PostgreSql} -PostgreSqlは、列と行からなる2次元のテーブルにより実装されるデータベースである。 +\section{PostgreSQL} +PostgreSQLは、列と行からなる2次元のテーブルにより実装されるデータベースである。 厳密な型を持つデータベースであり、きちんと設計を行えば、柔軟なクエリを用いてどんな検索にも対応できる力を持つ。 データベースへのアクセスは、SQLを用いて行う。 データの格納を行う際は、まずテーブルのデータの型と・制約を定義する。 テーブルの定義は、 -{\tt -\vspace{0.1in} +\begin{vervatime} CREATE TABLE table名 ( \\ \ \ 値の名前 型 制約 , …… \\ ) \\ @@ -47,23 +46,19 @@ の構文で行う。 またテーブル名の後ろに表示する値の絞込や、データの並び替えなどのオプションをつけることも可能である。 -PostgreSqlでは、Json形式をJson・JsonBという型を用いて格納する。 +PostgreSQLでは、Json形式をJson・JsonBという型を用いて格納する。 Json型は、Jsonデータを文字列で格納し、JsonBはバイナリで格納する。 -Json型で格納した場合、データにアクセスするたびにパースするため、非常に処理が重い。 -Index を張ることである程度は改善するが、基本的にJsonBで格納したほうが良い。 +Json型で格納した場合、データにアクセスするたびにパースする必要がある。 +JsonのIndex を張ることが可能になっている。 +%JsonのIndexの貼る例題 +% Jsonデータのアップデートは、Jsonの大きさnに対してO(n)になってしまう。 -このようにPostgreSqlは、厳密な型に守られたDBである。 -検索時に使用できるオプションも豊富で、欲しいデータを的確に抽出する力がある。 -その一方で、データの分割が難しいため、複数のマシンでデータを分割して保持する事が苦手で、 -また、格納するデータが複雑な構造だった場合、テーブル設計が煩雑になってしまう問題もある。 - \section{MongoDB} -MongoDB は2009年に公開された NoSQL のデータベースである。 -JSON フォーマットのドキュメントデータベースであり、スキーマが無い -リレーショナルテーブルに例えられる。 +MongoDB\cite{mongo} は2009年に公開された NoSQL のデータベースである。 +JSON フォーマットのドキュメントデータベースであり、スキーマレスト呼ばれる。 MongoDBでは、テーブルの代わりにコレクションにデータを保持する。 スキーマが無いため、事前にデータの定義を行う必要がなく、同じコレクションであっても、他のドキュメントが持っていないフィルドやデータ型をドキュメントに含めることができる。 @@ -94,6 +89,9 @@ findで使用するクエリもJavaScriptで記述できる。 +MongoDBは実装にmmapを使用しているため、トランザクションを安全に行うことが難しい。 +そのためデータの喪失などが発生することが知られている。 + このようにMongoDBは、非常に柔軟なデータモデルを扱え、 JavaScript を用いることで複雑な検索も可能である。 一方でデータの設計を行わないと、そのパフォーマンスを活かすことはできない。 @@ -101,13 +99,9 @@ \section{Cassandra} -Cassandraは2008年7月にFacebookによってオープンソースとして公開された Key-Value なデータベースである。 -データは4次元か、5次元の連想配列のようになっている。 -4次元の場合、{\tt [KeySpace][ColumnFamily][Key][Column]}・\\ -5次元の場合{\tt [KeySpace][ColumnFamily][Key][SuperColumn][Column]} の形で保持している。 -しかし、SuperColumn はパフォーマンスが悪く、公式でも使用を推奨していない。 -なので、4次元でデータを持つのが主流である。 -本論文でも4次元のデータモデルについて記述する。 +Cassandraは2008年7月にFacebookによって開発された Key-Value なデータベースである。 +データは4次元の連想配列のようになっている。 +{\tt [KeySpace][ColumnFamily][Key][Column]}\\ データを格納する場合初めに、KeySpaceを構築する。 KeySpaceは、 @@ -122,7 +116,7 @@ 障害時に、複製したデータを持つサーバにリクエストを行うことで、データの取得を行える。 データベースに対する負荷が高まった際に、複製を行ったノードに分散を行えるなどのメリットがある。 -KeySpaceは、PostgreSqlでいうところのデータベースに近い働きをする。 +KeySpaceは、PostgreSQLでいうところのデータベースに近い働きをする。 作成した KeySpace に対してColumnFamily を構築する。 @@ -135,7 +129,7 @@ の構文で行う。 また、テーブルの定義で最低１つは Key にオプションで PRIMARY KEY を指定する必要がある。 -ColumnFamily は、PostgreSql でいうところのテーブルに近い働きをする。 +ColumnFamily は、PostgreSQL でいうところのテーブルに近い働きをする。 作成したColumnFamily への値の挿入は、 diff -r cbc652b58d99 -r 8d1f5ab7b420 introduciton.tex --- a/introduciton.tex Sat Feb 11 01:13:24 2017 +0900 +++ b/introduciton.tex Sat Feb 11 19:04:30 2017 +0900 @@ -1,43 +1,39 @@ \chapter{ソフトウェア内部で使用するのに適した 木構造データベース Jungle} \pagenumbering{arabic} -\section{研究目的} プログラムからデータを分離して扱うデータベースには、 -プログラム中のデータ構造と Relational DataBase(RDB) の表構造のインピーダンスミスマッチという問題がある。 -データベースのレコードをプログラム中のオブジェクトとして使えるOR Mapperや、 -データベース自体も、表に特化したKey Value Store、Jsonなどの不定形のデータ構造を格納するように機能拡張されてきている。 -しかし、プログラム中のデータは複雑な構造をメモリ上に構築しており、これらの方法でもまだギャップがある。 +プログラム中のデータ構造と Relational DataBase(RDB) の表構造のミスマッチという問題がある。 +例えばRPGゲーム中のユーザが持つアイテムという単純なものでも、RDBではユーザとアイテムの組をキーとする巨大な表として管理することになる。 +プログラム中では、ユーザが持つアイテムリストという簡単な構造を持つが、データのネスト構造を許さない第一正規形を要求するRDBとは相容れない。 +レコードをプログラム中のオブジェクトに対応させるOR Mapperという技術、 +データベース自体を表に特化したKey Value Store技術、PostgreSQLやMySQLにJsonなどの不定形のデータ構造を格納技術 +が開発されてきたが、これを本質的には解決することはできていない。 +この問題はデータベースのインピーダンスミスマッチと呼ばれている。 +不定形の構造の変更をトランザクションとしてJsonの一括変更という形で処理するのは +並列処理が中心となってきている今のアプリケーションには向いているとは言えない。 +そこで当研究室では、これらの問題を解決するためにプログラム内部に木構造を格納できるデータベース Jungle を提案している。 +Jungleは、木構造の変更を非破壊的、つまり、元の木を保存しつつ、新しい木を構築する方法を取り、 +木のルートをアトミックに入れ替えることでトランザクションを実現する。 +プログラムは、この木を内部のデータ構造として直接取り扱うことができる。 +Jungleは、全体の整合性ではなく、木ごとに閉じた局所的な整合性を保証している。 +また、整合性のある木同士をマージすることで新しい整合性のある木を作り出すことも可能であるため、データの伝搬も容易である。 -そこで当研究室では、これらの問題を解決した、煩雑な設計を行わずプログラム内部に木構造を格納できるデータベース Jungle を提案している。 -Jungleは、木構造の変更を非破壊的、つまり、元の木を保存しつつ、新しい木を構築する方法を取り、 -木のルートをアトミックに入れ替えることでトランザクションを実現する。 -プログラムは、この木を内部のデータ構造として直接取り扱うことができるので、読み出し時にデータベースに問い合わせる必要がない。 -Jungleは、全体の整合性ではなく、木ごとに閉じた局所的な整合性を保証している。 -また、整合性のある木同士をマージすることで新しい整合性のある木を作り出すことも可能であるため、データの伝搬も容易である。 +\section{本論文の構成} Jungleは、読み込みは高速に行える反面、書き込みの手間は木の形・大きさに依存しており、最悪の場合O(n)となってしまう。 また、Indexの構築も大幅なネックとなっていた。 -そこで、本研究では、Jungleの木の構築・編集機能の改善を行う。 -その後、実際にJungleを使用したアプリケーションを開発・運用する。 +そこで、本研究では、Jungleの木とIndexの編集機能の改善を行う。 +また、実際にJungleを使用した複数のアプリケーション作成し評価を行う。 -\section{インピータンスミスマッチ} -インピータンスミスマッチとは、プログラム中のデータ構造とRDBの表構造の間に生まれるギャップのことである。 -例えばRPGゲーム中のユーザが持つアイテムという単純なものでも、RDBではユーザとアイテムの組をキーとする巨大な表として管理することになる。 -プログラム中では、ユーザが持つアイテムリストという簡単な構造を持つが、データのネスト構造を許さない第一正規形を要求するRDBとは相容れない。 -レコードをプログラム中のオブジェクトに対応させるOR Mapperという技術では、これを本質的には解決することはできない。 -そこで、 MySQLやPosgreSQLなどは、Jsonなどの不定形のデータ構造を格納するように機能拡張されるようになってきた。 -しかし、不定形の構造の変更をトランザクションとして、どのように処理するかはJsonの一括変更という形で処理されてしまっており、 -並列処理が中心となってきている今のアプリケーションには向いているとは言えない。つまり、この拡張はRDBよりの拡張であり、 -並列処理を含むプログラミングからの要請とのミスマッチが残っている - - -\section{本論文の構成} -本論文では、初めに既存のデータベースについて記述する。 -第 3 章では、Jungleの基本的な機能・APIについて記述する。 -第 4 章では、Jungleに新しく加えた構成要素について述べる。 -第 5 章では、改良後のIndexの実装に使用する非破壊 TreeMap の実装について記述する。 -第 6 章では、Indexの差分 Update の実装について記述する。 -第 7 章では、線形の木を、正順でO(1)で構築することが可能な、Differential Jungle Tree の実装について記述する。 -第 8 章では、自身が Index としての機能を持つ、 Red Black Jungle Treeの実装について記述する。 -第 9 章では、実際に Jungle を使用した、例題アプリケーションの実装について記述する。 -第 10 章では、今回実装した機能の測定について記述する。 +本論文の構成は以下のようになっている。 +\begin{itemize} +\item 第2章で既存のデータベース +\item 第3章ではJungleの基本的な機能・API +\item 第4章ではJungleに新しく加えた構成要素 +\item 第5章では改良後のIndexの実装に使用する非破壊 TreeMap の実装 +\item 第6章ではIndexの差分 Update の実装 +\item 第7章では線形の木を、正順でO(1)で構築することが可能な、Differential Jungle Tree の実装 +\item 第8章では自身が Index としての機能を持つ、 Red Black Jungle Treeの実装 +\item 第9章では実際に Jungle を使用した、例題アプリケーションの実装 +\item 第10章では今回実装した機能の測定 +\end{itemize} diff -r cbc652b58d99 -r 8d1f5ab7b420 jungle.tex --- a/jungle.tex Sat Feb 11 01:13:24 2017 +0900 +++ b/jungle.tex Sat Feb 11 19:04:30 2017 +0900 @@ -1,38 +1,31 @@ -\chapter{非破壊的木構造データベースJungle} -本章では、Jungleの基本的な解説を行う。 -初めに Jungle の特徴である非破壊的木構造の説明をし、その後提供しているAPIについて述べる。 +\chapter{非破壊的木構造データベースの利点} +本章では、非破壊的木構造を選択した理由について述べる。 +従来の破壊的木構造は親から子へのポインタと子供から親へのポインタを持つ二重リンク構造を持っていた。 +これによりノードの挿入削除をO(1)で行うことができる。 +しかし、変更前の木を保存することとは両立せず、変更中に前の版の木を使用することはできない。 +そこで、子供から親へのポインタを無くし、木を共有しながら変更部分を付け加える非破壊的木構造を提案する。 +これにより、木の変更はO(n)になるが、並列実行向けの複数の版が存在できるデータベースを実現することができる。 -\section{破壊的木構造と非破壊的木構造} -Jungle は、非破壊的木構造という特殊な木構造を持つ。 -本節では、破壊的木構造と非破壊的木構造の編集・メリットデメリットについて記述する。 - -\vspace{0.3in} -{\Large 破壊的木構造の編集} - -\vspace{0.1in} -破壊的木構造の編集は, 木構造で保持しているデータを直接書き換えることで行う。 -図\ref{fig:destractive}は破壊的木構造におけるデータ編集を表している。 - -\begin{figure}[htpb] - \begin{center} - \includegraphics[scale=0.7]{figures/destructive_tree.pdf} - \caption{破壊的木構造の編集} - \label{fig:destractive} - \end{center} -\end{figure} - -破壊的木構造は、編集を行う際に木のロックを掛ける必要がある。 -この時、データを受け取ろうと木を走査するスレッドは書き換えの終了を待つ必要があり、 -閲覧者がいる場合は木の走査が終わるまで書き換えを待たなければならない。 +\section{破壊的木構造} +破壊的木構造は親から子までのポインタとともに、子から親へのポインタを持つ。 +ノードの属性値を書き換える場合は、そのまま上書きすることが可能である。 +ノードの追加を行うときには、行う位置の親と子供の両方のポインタを変更する。 +この複数の変更を一つのトランザクションとして行う必要がある。 +変更中は親と子をロックする必要がある。 +平行度を上げるために、前の版の木にアクセスするためには複製を作る必要がある。 +一つの方法は、常に二つの木を用意し交互に変更を行うものである。 +変更自体はO(1)だが、平行実行下では複雑な工夫が必要になる。 -\vspace{0.3in} -{\Large 非破壊的木構造の編集} +\section{非破壊的木構造} -\vspace{0.1in} -データの編集を一度生成した木を上書きせず、ルートから編集を行うノードまでコピーを行い新しく木構造を構築し、そのルートをアトミックに入れ替えることで行う(図\ref{fig:nondestractive})。 -その際、編集に関係ないノードは参照を行い、複製元の木と共有する(図\ref{fig:nondestractive}の例ではノード1・3・4は編集に関係ないため新しいルートノードから参照を行い、過去の木と共有を行っている)。 +データの編集を一度生成した木を上書きせず、ルートから編集を行う位置までノードをコピーする{図\ref{fig:nondestractive})。 +この時に、子供からの親へのポインタは持たないとする。 +木のルートをAtomicに置き換えることで、木のアップデートを行う。 +変更前の木が残っているので、そのまま使用できる。 +変更されないノードは変更前と変更後のルートから共有されることになる。 + \begin{figure}[htpb] \begin{center} @@ -42,11 +35,20 @@ \end{center} \end{figure} -非破壊的木構造においてデータのロックが必要となる部分は、木のコピーを作り終えた後に -ルートノードを更新するときだけである。 -データ編集を行っている間ロックが必要な破壊的木構造に比べ、編集中においてもデータの読み込みが可能であるが、 -書き込み時の手間は大きくなる。 +破壊的変更に比べて、ノードの作成量は増えるが複数の版が同時に存在できる(\ref{fig:nondestractive_merit})。 +したがって、現在および過去の木を分散ノードまたはディスクに安全に格納することができる。 +実際には、木自体ではなく木の変更Logを分散ノードまたはディスクに書き出すのが妥当である。 +変更の計算量は最悪O(n)になるので、大量の挿入を行うときには工夫が必要になる。 +木のルートの上に新しくノードを付け加える場合はO(1)となる。 +この場合は木は追加順と逆順の構成を持つことになる。 +木の末端に追加する場所を覚えておき、そこにAtomicにノードを追加するとO(1)で正順で追加することができる。 +この場合は木が破壊的に変更されているように見えるが、前の版の末端部分を超えてアクセスすることがなければ複数の版を同時に使用することができる。 +これをDifferential Treeと呼ぶ。 + +木構造自体をバランス木、例えば赤黒木とすることもできる。 +これにより、O(log n)で木の変更を行うことができる。 +しかし、この場合木構造自体を自由に構成することはできないが、赤黒木のKeyを用いて任意のノードにO(Log n)でアクセスすることができる。 \begin{figure}[htpb] @@ -60,6 +62,18 @@ また、過去の木を保持する場合、破壊的木構造は、木の複製後編集を行う必要がある。 一方、非破壊的木構造は過去の木を上書きしないため、過去の木のルートノードを保持するだけで良い。 + +\chapter{Jungleの構成要素} +本章では、Jungleの構成要素について説明する。 +Jungleは名前を用いて木の生成と木の取得を行う。 +木の中の特定のノードにアクセスするには、木の中のノードの位置を表すNodePathを用いる。 +木の変更は非破壊的に行われ、木のルートを変更後の木に置き換えるAtomicOperationがトランザクションとなる。 +木の変更はLogとして記録され、分散ノードあるいはディスクに格納される。 +JungleのAPIは、Eitherを返すようになっており、Eitherの型をチェックすることにより成功と失敗がわかるようになっている。 +今回効率的な木の非破壊アップデートを可能にするために追加した機能である、 +Jungleの中で使用する非破壊赤黒木、Indexの差分アップデート、Differential Jungle Tree、Red Black Jungle Treeについて説明する。 + + \section{NodePath} Jungleでは、木のノードの位置を{\tt NodePath}クラスを使って表す。 {\tt NodePath}クラスはルートノードからスタートし、対象のノードまでの経路を数字を用いて指し示す。また、ルートノードは例外として-1と表記される。