Mercurial > hg > Papers > 2017 > tatsuki-master
changeset 14:e4da23b04260
commit
| author | tatsuki |
|---|---|
| date | Wed, 08 Feb 2017 17:26:22 +0900 |
| parents | 7acd7d5afeb6 |
| children | 33d8077a5d45 |
| files | abstract.tex databases.tex introduciton.tex jungle.tex jungleUpdatePoint.tex master_paper.pdf master_paper.tex |
| diffstat | 7 files changed, 200 insertions(+), 75 deletions(-) [+] |
line wrap: on
line diff
--- a/abstract.tex Tue Feb 07 18:50:35 2017 +0900 +++ b/abstract.tex Wed Feb 08 17:26:22 2017 +0900 @@ -1,12 +1,19 @@ \begin{abstract} -Jungleは、本研究室で開発している、プログラム内部に木構造を構築するデータベースである。 -木の変更は、変更を加えたノードから、ルートまでの経路の複製を行い、新しいルートをアトミックに入れ替えることでトランザクションを実現する。 -この方法により、木構造の変更を非破壊的、つまり、元の木を保存しつつ、新しい木を構築する。 -プログラムは、この木を内部のデータ構造として直接取り扱うことができる。 -また、汎用の木構造を持つので、データベースを特に設計しなくてもあるがままの形で格納することが可能になっている。 -%しかし、木構造の形によっては、木の変更の手間が大きくなる・Indexの更新処理が極めて重いという面があった。 +プログラムからデータを分離して扱うデータベースには、 +プログラム中のデータ構造と Relational DataBase(RDB) の表構造のインピーダンスミスマッチという問題がある。 +データベースのレコードをプログラム中のオブジェクトとして使えるOR Mapperや、 +データベース自体も、表に特化したKey Value Store、Jsonなどの不定形のデータ構造を格納するように機能拡張されてきている。 +しかし、プログラム中のデータは複雑な構造をメモリ上に構築しており、これらの方法でもまだギャップがある。 -本研究では、Jungleデータベースの改善を行い、既存のJungleとくらべて大幅な処理の高速化に成功した。 -また、Jungleを使用した例題アプリケーションを作成し、性能測定を行ったところ、木構造の形によって処理速度に差が出ることがわかった。 +そこで当研究室では、煩雑な設計を行わず、プログラム内部に木構造を格納できるデータベースJungleを提案している。 +また、Jungleは、木構造の変更を非破壊的、つまり、元の木を保存しつつ、新しい木を構築する方法を取り、 +木のルートをアトミックに入れ替えることでトランザクションを実現する。 +プログラムは、この木を内部のデータ構造として直接取り扱うことができるので、読み出し時にデータベースに問い合わせる必要がない。 +Jungleは分散構成も可能である。 + +Jungleは、読み込みは高速に行える反面、書き込みは木の形に依存しており、最悪の場合O(n)となってしまう。 +また、Indexの構築も大幅なネックとなっていた。 +そこで、本研究では、Jungleの木の構築・編集機能の改善を行う。 +その後、実際にJungleを使用したアプリケーションを開発・運用する。 \end{abstract}
--- a/databases.tex Tue Feb 07 18:50:35 2017 +0900 +++ b/databases.tex Wed Feb 08 17:26:22 2017 +0900 @@ -1,49 +1,143 @@ %もう少し詳しく書く \chapter{既存のデータベース} -本章では, まずデータベースの種類であるRelational DatabaseとNoSQL について記述する。 -次に、データベースに値を格納する際に、発生する問題であるインピータンスミスマッチについて触れ、 -最後に既存のデータベースの例として、PostgreSql・MongoDB・Cassandraについて記述する。 +本章では、既存のデータベースの例として、PostgreSql・MongoDB・Cassandraについて記述する。 + +\section{PostgreSql} +PostgreSqlは、列と行からなる2次元のテーブルにより実装されるデータベースである。 +厳密な型を持つデータベースであり、きちんと設計を行えば、柔軟なクエリを用いてどんな検索にも対応できる力を持つ。 -\section{Relational Database} -Relational Database(RDB)は、列と行からなる2次元のテーブルにより実装されるデータベースである。 -RDBが保持しているデータへのアクセスは、SQLを用いて行われる。 -テーブルに格納されるデータ型として、文字列・数値・日付・BOOL型があり、システムによりデータに型が強制される。 -RDBはスキーマの決まったデータを扱うことに長けている。 -また、既存のテーブルを結合することで、１つのテーブルとして扱うことが可能である。 -RDBの例として、MySQL・PostgreSQLなどがある。 +データベースへのアクセスは、SQLを用いて行う。 +データの格納を行う際は、まずテーブルのデータの型と・制約を定義する。 +テーブルの定義は、 -\section{NoSQL} -NoSQLはNot Only SQLの略で、SQLを使わないデータベースのことを指す。 -NoSQLデータベースはRDBとは違いスキーマがない。 -そのため、扱おうとしているデータの形が決まっていなくても気軽に使うことができる。 -NoSQLの例として、MongoDB・Cassandra・当研究室で開発を行っているJungleなどがある。 +\vspace{0.1in} +CREATE TABLE table名 ( \\ +\ \ 値の名前 型 制約 , …… \\ +) \\ + +の構文で行う。 +制約というのは、値の重複を許さない行を特定する際に用いる{\tt PRIMARY KEY}などがある。 +また、テーブル同士は{\tt PRIMARY KEY}を用いて参照を行うことが可能である。 -\section{インピータンスミスマッチ} -インピータンスミスマッチとは、プログラム中のデータ構造とRDBの表構造の間に生まれるギャップのことである。 -例えばRPGゲーム中のユーザが持つアイテムという単純なものでも、RDBではユーザとアイテムの組をキーとする巨大な表として管理することになる。 -プログラム中では、ユーザが持つアイテムリストという簡単な構造を持つが、データのネスト構造を許さない第一正規形を要求するRDBとは相容れない。 -レコードをプログラム中のオブジェクトに対応させるOR Mapperという技術では、これを本質的には解決することはできない。 -そこで、 MySQLやPosgreSQLなどは、Jsonなどの不定形のデータ構造を格納するように機能拡張されるようになってきた。 -しかし、不定形の構造の変更をトランザクションとして、どのように処理するかはJsonの一括変更という形で処理されてしまっており、 -並列処理が中心となってきている今のアプリケーションには向いているとは言えない。つまり、この拡張はRDBよりの拡張であり、 -並列処理を含むプログラミングからの要請とのミスマッチが残っている。 +テーブルへのデータの格納は、 + +\vspace{0.1in} +INSERT INTO テーブル名 VALUES( \\ +\ \ 格納するデータ \\ +); \\ + +の構文で行う。 +テーブルにデータを格納する際にはスキーマの定義に沿ってなければならない。 +もし、スキーマに反するデータを格納した場合 +エラーが発生しデータの格納に失敗する。 +このようにPostgreSqlは、厳密な型に守られている。 + + +作成したテーブルからのデータの取得は、 + +\vspace{0.1in} +Select 表示する値 FROM テーブル名;\\ + + +の構文で行う。 +またテーブル名の後ろに表示する値の絞込や、データの並び替えなどのオプションをつけることも可能である。 + +PostgreSqlでは、Json形式をJson・JsonBという型を用いて格納する。 +Json型は、Jsonデータを文字列で格納し、JsonBはバイナリで格納する。 +Json型で格納した場合、データにアクセスするたびにパースするため、非常に処理が重い。 +Index を張ることである程度は改善するが、基本的にJsonBで格納したほうが良い。 + + +このようにPostgreSqlは、厳密な型に守られたDBである。 +検索時に使用できるオプションも豊富で、欲しいデータを的確に抽出する力がある。 +その一方で、データの分割が難しいため、複数のマシンでデータを分割して保持する事が苦手で、 +また、格納するデータが複雑な構造だった場合、テーブル設計が煩雑になってしまう問題もある。 + \section{MongoDB} MongoDB は2009年に公開された NoSQL のデータベースである。 JSON フォーマットのドキュメントデータベースであり、スキーマが無い リレーショナルテーブルに例えられる。 + +MongoDBでは、テーブルの代わりにコレクションにデータを保持する。 スキーマが無いため、事前にデータの定義を行う必要がなく、同じコレクションであっても、他のドキュメントが持っていないフィルドやデータ型をドキュメントに含めることができる。 そのためリレーショナルデータベースに比べてデータの追加・削除が行いやすい。 +コレクションへのデータの格納は、 + +\vspace{0.1in} +db.コレクション名.insert({Jsonフォーマットで記述されたデータ});\\ + +の構文で行う。 +Json形式のデータは任意の深さまでネストすることが可能である。 + + +作成したコレクションからのデータの取得は、 + +\vspace{0.1in} +db.コレクション名.find(検索条件,表示する値の絞込);\\ + +の構文で行う。 +引数を渡さなかった場合、コレクションの中身が全て表示される。 + +MongDBは、あらゆる箇所でJavaScriptを用いており、前述した{\tt insert()}・{\tt find()}といった関数もJavaScriptで実装されている。 +dbですらJavaScriptのオブジェクトである。 +findで使用するクエリもJavaScriptで記述できる。 + + +このようにMongoDBは、非常に柔軟なデータモデルを扱える。 +一方でデータの設計を行わないと、そのパフォーマンスを活かすことはできない。 + + \section{Cassandra} Cassandraは2008年7月にFacebookによってオープンソースとして公開された Key-Value なデータベースである。 データは4次元か、5次元の連想配列のようになっている。 4次元の場合、{\tt [KeySpace][ColumnFamily][Key][Column]}・\\ -5次元の場合{\tt [KeySpace][ColumnFamily][Key][SuperColumn][Column]} の形で値にアクセスする。 -例えば、SuperColumnに対して特定のKeyでアクセスを行うと、KeyとペアのColumnが返ってくる。 -このように、Cassandraはネストしているデータに対して、Keyを使ってアクセスを行う。 -また、Column等は、予めデータの型を定義する必要がないため、柔軟にデータを格納できる。 -Cassandraは、スキーマレスな NoSQL データベースである。 +5次元の場合{\tt [KeySpace][ColumnFamily][Key][SuperColumn][Column]} の形で保持している。 +しかし、SuperColumn はパフォーマンスが悪く、公式でも使用を推奨していない。 +なので、4次元でデータを持つのが主流である。 +本論文でも4次元のデータモデルについて記述する。 + +データを格納する場合初めに、KeySpaceを構築する。 +KeySpaceは、 + +\vspace{0.1in} +create keyspace KeySpace名 with replication = {レプリケーションの設定};\\ + +の構文で行う。 +レプリケーションとは、データベースを別のノードに複製し、データの編集時に同期を取ることである。 +障害時に、複製したデータを持つサーバにリクエストを行うことで、データの取得を行える。 +データベースに対する負荷が高まった際に、複製を行ったノードに分散を行えるなどのメリットがある。 + +KeySpaceは、PostgreSqlでいうところのデータベースに近い働きをする。 + + +作成した KeySpace に対してColumnFamily を構築する。 +ColumnSpace は、 + +\vspace{0.1in} +create table テーブル名 (Key Column PRIMARY KEY, Key Column); \\ + +の構文で行う。 +また、テーブルの定義で最低１つは Key にオプションで PRIMARY KEY を指定する必要がある。 +ColumnFamily は、PostgreSql でいうところのテーブルに近い働きをする。 + +作成したColumnFamily への値の挿入は、 + +\vspace{0.1in} +INSERT INTO テーブル名 (key1,key2) VALUES (column1, column2);\\ + +の構文で行う。 +また、Cassandra は、PRIMARY KEY で指定した Key で、Column を管理しているため、重複した PRIMARY KEY で 値を挿入すると、データの更新扱いになり上書きされる。 + +作成した ColumnFamily からのデータの取得は、 + +\vspace{0.1in} +SELECT 表示する値 FROM テーブル名 オプション;\\ + +で行う。 +またテーブル名の後ろに表示する値の絞込や、データの並び替えなどのオプションをつけることも可能である。 +
--- a/introduciton.tex Tue Feb 07 18:50:35 2017 +0900 +++ b/introduciton.tex Wed Feb 08 17:26:22 2017 +0900 @@ -1,5 +1,6 @@ -\chapter{研究目的} +\chapter{ソフトウェア内部で使用するのに適した 木構造データベース Jungle} \pagenumbering{arabic} +\section{研究目的} プログラムからデータを分離して扱うデータベースには、 プログラム中のデータ構造と Relational DataBase(RDB) の表構造のインピーダンスミスマッチという問題がある。 データベースのレコードをプログラム中のオブジェクトとして使えるOR Mapperや、 @@ -19,9 +20,19 @@ その後、実際にJungleを使用したアプリケーションを開発・運用する。 +\section{インピータンスミスマッチ} +インピータンスミスマッチとは、プログラム中のデータ構造とRDBの表構造の間に生まれるギャップのことである。 +例えばRPGゲーム中のユーザが持つアイテムという単純なものでも、RDBではユーザとアイテムの組をキーとする巨大な表として管理することになる。 +プログラム中では、ユーザが持つアイテムリストという簡単な構造を持つが、データのネスト構造を許さない第一正規形を要求するRDBとは相容れない。 +レコードをプログラム中のオブジェクトに対応させるOR Mapperという技術では、これを本質的には解決することはできない。 +そこで、 MySQLやPosgreSQLなどは、Jsonなどの不定形のデータ構造を格納するように機能拡張されるようになってきた。 +しかし、不定形の構造の変更をトランザクションとして、どのように処理するかはJsonの一括変更という形で処理されてしまっており、 +並列処理が中心となってきている今のアプリケーションには向いているとは言えない。つまり、この拡張はRDBよりの拡張であり、 +並列処理を含むプログラミングからの要請とのミスマッチが残っている + \section{本論文の構成} -本論文では、初めに既存のデータベースとインピータンスミスマッチについて記述する。 +本論文では、初めに既存のデータベースについて記述する。 第 3 章では、Jungleの基本的な機能・APIについて記述する。 第 4 章では、改良後のIndexの実装に使用する非破壊 TreeMap の実装について記述する。 第 5 章では、Indexの差分 Update の実装について記述する。
--- a/jungle.tex Tue Feb 07 18:50:35 2017 +0900 +++ b/jungle.tex Wed Feb 08 17:26:22 2017 +0900 @@ -1,4 +1,7 @@ \chapter{非破壊的木構造データベースJungle} +本章では、当研究室で開発を行っているデータベース Jungle について記述する。 + +\section{概要} Jungleは、当研究室で開発を行っているデータベースで、Javaを用いて実装されている。 Jungleは名前付きの複数の木の集合からなり、木は複数のノードの集合で出来ている。 ノードは自身の子のリストと属性名と属性値の組でデータを持ち、データベースのレコードに相当する。 @@ -17,7 +20,16 @@ 部分について考察する。 本章ではまず破壊的木構造と、非破壊的木構造の説明をし、その後Jungleの提供しているAPIについて述べる。 -\section{破壊的木構造} +\newpage + +\section{非破壊的木構造} +Jungle は、非破壊的木構造という特殊な木構造を持つ。 +本節では、初めに破壊的木構造と非破壊的木構造の編集・メリットデメリットについて記述する。 + +\vspace{0.3in} +{\Large 破壊的木構造の編集} + +\vspace{0.1in} 破壊的木構造の編集は, 木構造で保持しているデータを直接書き換えることで行う。 図\ref{fig:destractive}は破壊的木構造におけるデータ編集を表している。 @@ -33,7 +45,11 @@ この時、データを受け取ろうと木を走査するスレッドは書き換えの終了を待つ必要があり、 閲覧者がいる場合は木の走査が終わるまで書き換えを待たなければならない。 -\section{非破壊的木構造} + +\vspace{0.3in} +{\Large 非破壊的木構造の編集} + +\vspace{0.1in} データの編集を一度生成した木を上書きせず、ルートから編集を行うノードまでコピーを行い新しく木構造を構築し、そのルートをアトミックに入れ替えることで行う(図\ref{fig:nondestractive})。 その際、編集に関係ないノードは参照を行い、複製元の木と共有する(図\ref{fig:nondestractive}の例ではノード1・3・4は編集に関係ないため新しいルートノードから参照を行い、過去の木と共有を行っている)。 @@ -45,11 +61,14 @@ \end{center} \end{figure} +\newpage 非破壊的木構造においてデータのロックが必要となる部分は、木のコピーを作り終えた後に ルートノードを更新するときだけである。 データ編集を行っている間ロックが必要な破壊的木構造に比べ、編集中においてもデータの読み込みが可能であるが、 書き込み時の手間は大きくなる。 + + \begin{figure}[htpb] \begin{center} \includegraphics[scale=0.7]{figures/non_destructive_merit.pdf} @@ -58,6 +77,9 @@ \end{center} \end{figure} +また、過去の木を保持する場合、非破壊的木構造は、木の複製後編集を行う必要がある。 +一方、非破壊的木構造は過去の木を上書きしないため、過去の木のルートノードを保持するだけで良い。 + \section{NodePath} Jungleでは、木のノードの位置を{\tt NodePath}クラスを使って表す。 {\tt NodePath}クラスはルートノードからスタートし、対象のノードまでの経路を数字を用いて指し示す。また、ルートノードは例外として-1と表記される。 @@ -176,7 +198,7 @@ \end{table} \newpage -以下にルートノードの2番目の子供から、属性名 {\tt name}とペアになっている属性値を取得するサンプルコードを記述する。 +以下にルートノードの2番目の子供から、属性名 {\tt name}とペアになっている属性値を取得するサンプルコード\ref{getAttributeCode}を記述する。 \begin{lstlisting}[frame=lrbt,numbers=left,label=getAttributeCode] JungleTree tree = jungle.getTreeByName("TreeName"); TreeNode root = tree.getRootNode(); @@ -189,45 +211,36 @@ String value = attribute.getString("name"); \end{lstlisting} -\begin{enumerate} - \item Jungleから名前が{\tt "TreeName"}の木を取得する。 - \item 取得した木のルートノードを取得する。 - \item 木のルートノードから{\tt Children}を取得する。 - \item 3で取得した{\tt Children}から2番目の子供を取得する。 - \item 関数{\tt Either.isA()}を用いて、2番目の子供が取得できたかを調べる。 - \item 取得できていなかった場合{\tt Either.a()}でErrorを返す。 - \item 取得に成功していた場合、{\tt Either.b()}で子ノードを取得する。 - \item 取得した子ノードから{\tt Attribute}クラスを取得する。 - \item 取得した{\tt attribute}から属性名 {\tt name}とペアの属性値を取得する。 -\end{enumerate} +ソースコード\ref{getAttributeCode}の説明を行う。 +1行目から2行目で \section{木の編集API} Jungleの木の編集は{\tt Default Jungle Tree Editor}クラスを用いて行われる。 {\tt Default Jungle Tree Editor}クラスは、木に対する編集を行うAPIが定義されているJungle Tree Editorインターフェースを実装している。 Default Jungle Tree Editorは、Jungle Tree から、{\tt getTreeEditor()}を用いて取得する。 表\ref{editor}にJungle Tree Editorインターフェースに定義されているAPIを記述する。 - +また、表\ref{editor}に記述しているAPIは全て、{\tt Either<Error,JungleTreeEditor>} を返す。 \newpage \begin{table}[htb] \begin{center} \caption{Editorに実装されているAPI} - \begin{tabular}{|p{15em}|p{24em}|} \hline - {\tt Either<Error, JungleTreeEditor> addNewChildAt( NodePath path, int pos)} & - 変数{\tt path}で指定した場所にあるノードの、変数{\tt pos}で指定した位置に子ノードを追加する。\\ \hline - {\tt Either<Error, JungleTreeEditor> deleteChildAt( NodePath path,int pos)} & - 変数{\tt path}で指定した場所にあるノードの、変数{\tt pos}で指定した位置の子ノードを削除する。 \\ \hline - {\tt Either<Error, JungleTreeEditor> putAttribute( NodePath path,String key,ByteBuffer value)} & - 変数{\tt path}で指定した場所にあるノードに、属性名 変数{\tt key} 属性値 変数{\tt value} のペアで値を挿入する。 \\ \hline - {\tt Either< Error, JungleTreeEditor> deleteAttribute( NodePath path,String key)}& - 変数{\tt path}で指定した場所にあるノードが持つ、属性名 変数{\tt key}とペアで保存されている属性値を削除する。\\ \hline - {\tt Either<Error, JungleTreeEditor> moveChild( NodePath path,int num,String move)} & - 変数{\tt path}で指定した場所にあるノードの、変数{\tt num}で指定された位置の子供を変数{\tt move}の方向に移動させる。 \\ \hline - {\tt Either<Error, JungleTreeEditor> pushPop()} & + \begin{tabular*}{\textwidth}{|p{15em}|p{22em}|} \hline + {\small\tt addNewChildAt( NodePath path, int pos)} & + {\tt path}で指定したノードの{\tt pos}番目の子の後にノードを追加する。\\ \hline + {\small\tt deleteChildAt( NodePath path,int pos)} & + {\tt path}で指定したノードの{\tt pos}番目の子ノードを削除する。 \\ \hline + {\small\tt putAttribute( NodePath path,String key,ByteBuffer value)} & + {\tt path}で指定したノードに属性名 {\tt key} 属性値 {\tt value} のペアで値を挿入する。 \\ \hline + {\small\tt deleteAttribute( NodePath path,String key)}& + {\tt path}で指定したノードが持つ、属性名 {\tt key}とペアで保存されている属性値を削除する。\\ \hline + {\small\tt moveChild( NodePath path,int num,String move)} & + {\tt path}で指定したノードの{\tt num}番目の子供を{\tt move}の方向に移動させる。 \\ \hline %あとで直す + {\small\tt pushPop()} & ルートノードの上に新しいルートノードを追加する。線形の木を作る際に使用することで木の変更の手間をO(n)からO(1)にできる。\\ \hline - {\tt Either<Error, JungleTreeEditor> success()} & + {\small\tt success()} & 木へ行った変更をコミットする。自分が編集を行っていた間に、他のJungleTreeEditorクラスによって木が更新されていた場合、コミットは失敗する。 \\ \hline - \end{tabular} + \end{tabular*} \label{editor} \end{center} \end{table} @@ -288,7 +301,7 @@ -\section{検索APIの実装} +\section{検索API} これまでに紹介したAPIにより、Jungleは木構造を構築できるようになった。 しかし、木に問い合わせを行う検索APIが実装されていなかったため、木の走査を行う{\tt Traverser}クラス内に、lambda式を用いて実装した。 以下に検索を行う関数{\tt find}の定義を記述する。 @@ -328,7 +341,7 @@ 検索の際に使用する Index の実装については次節に記述する。 -\section{Indexの実装} +\section{Index} Jungleは、非破壊的木構造というデータ構造上、過去の版の木構造を全て保持している。 よって、全ての版に独立したIndexが必要となるため、前の版のIndexを破壊すること無く、Indexを更新する必要がある。 既存のTreeMapでは、一度Indexの複製を行ない、その後更新する必要があったため、Indexの更新オーダーがO(n)となっていた。 @@ -360,7 +373,7 @@ \begin{enumerate} -\item {\tt indexMap}に、今回検索で使用する属性名 {\tt name}を使用して{\tt get("name")}を行う。すると属性名 {\tt name}に対応したIndexが、{\tt Optional}クラスで包まれて返ってくる。 +\item {\tt indexMap}に、今回検索で使用する属性名 {\tt name}を使用して{\tt get("name")}を行う。すると属性名 {\tt "name"}に対応したIndexが、{\tt Optional}クラスで包まれて返ってくる。 \item {\tt Optional}オブジェクトに対して、中身を保持しているか(属性名 {\tt name}に対応したIndexを木が持っているか)を調べる。 @@ -368,9 +381,9 @@ \item 持っていた場合、{\tt Optional}オブジェクトからIndexを取得する。 -\item 取得したIndexに、検索で使用する属性値{\tt kanagawa}で{\tt get()}を行う。すると、属性名 {\tt name} 属性値{\tt kanagawa}の値を持つノードのリストが、{\tt Optional}クラスに包まれて返ってくる。 +\item 取得したIndexに、検索で使用する属性値{\tt "kanagawa"}で{\tt get()}を行う。すると、属性名 {\tt "name"} 属性値{\tt "kanagawa"}の値を持つノードのリストが、{\tt Optional}クラスに包まれて返ってくる。 -\item {\tt Optional}オブジェクトに対して中身を保持しているか(属性名 {\tt name} 属性値 {\tt kanagawa}を持つノードを木が持っているか)を調べる。 +\item {\tt Optional}オブジェクトに対して中身を保持しているか(属性名 {\tt "name"} 属性値 {\tt "kanagawa"}を持つノードを木が持っているか)を調べる。 \item 持っていなかった場合、空の{\tt Iterator}オブジェクトを返す。