Mercurial > hg > Papers > 2016 > tatsuki-prosym
view introduction.tex @ 15:b3350fe86bb7
intorduction
author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
---|---|
date | Thu, 10 Nov 2016 19:49:52 +0900 |
parents | 05ab591d3a24 |
children | 27f92e7af1fc |
line wrap: on
line source
\section{Jungle DBによるインピーダンスミスマッチの解決} プログラム中のデータ構造とRDBの表構造には大きなギャップがある。これはインピーダンスミスマッチと呼ばれている。 例えばRPGゲーム中のユーザが持つアイテムという単純なものでもRDBではユーザとアイテムの組をキーとする巨大な表として管理することになる。 プログラム中ではユーザが持つアイテムリストという簡単な構造を持つが、データのネスト構造を許さない第一正規形を要求するRDBとは相容れない。 レコードをプログラム中のオブジェクトに対応させるOR Mapという技術では、これを本質的には解決することはできない。 そこで、 MySQLやPosgreSQLなどはJsonなどの不定形のデータ構造を格納するように機能拡張されるようになってきた。 しかし、不定形の構造の変更をトランザクションとして、どのように処理するかはJsonの一括変更という形で処理されてしまっており、 並列処理が中心となってきている今のアプリケーションには向いているとは言えない。つまり、この拡張はRDBよりの拡張であり、 並列処理を含むプログラミングからの要請とのミスマッチが残っている。 \subsection{非破壊的木構造データベースJungle} 当研究室では、これらの問題を解決した煩雑なデータ設計が必要のない Jungle データベースを提案している。 Jungleはプログラム内部に直接木構造を構築し、そのルートをアトミックに入れ替えることでトランザクションを実現する。 また木構造の表現に単一リンクを用い、変更を非破壊的つまり、元の木を保存しつつ、新しい木を構築する方法を取る。 これにより複数のスレッドからでも木構造を安全に扱うことができる。 プログラムは、この木を内部のデータ構造として直接取り扱うことができるので、読み出し時にいちいちデータベースに問い合わせる必要がない。また汎用の木構造を持つので、データベースを特に設計しなくても、あるがままの形で格納することが可能になっている。 本研究では実際にJungle上に実際に複数のアプリケーションを実装し、Jungleの表現力、機能の十分性、実用的な性能があるか、実証実験を行った。その時に明らかになった木構造データベースの問題点についても考察する。 Jungleは複数の木の集合からなり、木は複数のノードの集合で出来ている。 ノードは自身の子のListと属性名と属性値の組を持ち、データベースのレコードに相当する。 通常のレコードと異なるのは、ノードに子供となる複数のノードが付くところである。 Jungleは データの編集は一度生成した木を上書きせず、ルートから編集を行うノードまでコピーを行い新しく木構造を構築することで行う。 これを非破壊的木構造と呼ぶ。非破壊木構造は新しい木を構築している時にも、現在の木を安定して読み出せるという特徴がある。 しかし、書き込み時の手間は大きくなる。 通常のRDBと異なり、Jungleは木構造をそのまま読み込むことができる。例えば、XMLやJasonで記述された構造をデータベースを設計することなく読み込むことが可能であり、実際、そういう機能が実装されている。この木をそのままデータベースとしてしようすることも可能である。しかし、木の変更の手間は木の構造に依存する。 特に非破壊木構造を採用しているJungleでは木構造の変更にo(1)からo(n)の様々な選択肢がある。つまり、アプリケーションに合わせて木を設計しない限り、 十分な性能を出すことはできない。逆に言えば、正しい木の設計を行えば高速な処理が可能である。 Jungleは基本的にon memoryで使用することを考えており、一度、木のルートを握れば、その上で木構造として自由にアクセスして良い。 Jungleは分散データベースを構成するように設計されており、分散ノード間の通信は木の変更のログを交換することによって行われる。 持続性のある分散のードを用いることでJungleの持続性を保証することができる。本論文では分散実装部分ではなく on memory DBの 部分について考察する。 本論文では、 実際に、Jungleを用いたアプリケーションをいくつか構築し、どのような木構造がアプリケーションに向いているかを調べる。 その際の設計指針はRDBとは異なり複雑である。これはプログラムのデータ構造そのものの設計に相当する。 Jungleは、その意味でプログラミングの視点から見たデータベースになっている。