Mercurial > hg > Papers > 2017 > suruga-sigos
changeset 21:5be85f2a6d07
fix
| author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Sat, 21 Apr 2018 19:07:47 +0900 |
| parents | 9e9af63c241d |
| children | f55662d3643f |
| files | paper/sigos.tex |
| diffstat | 1 files changed, 62 insertions(+), 169 deletions(-) [+] |
line wrap: on
line diff
--- a/paper/sigos.tex Tue Apr 25 20:12:39 2017 +0900 +++ b/paper/sigos.tex Sat Apr 21 19:07:47 2018 +0900 @@ -36,38 +36,29 @@ \begin{document} % 和文表題 -\title{非破壊木構造データベース Jungle のサービス利用法にそった改良} +\title{分散フレームワークChristieと分散木構造データベースJungle} % 英文表題 \etitle{} % 所属ラベルの定義 -\affilabel{1}{琉球大学大学院理工学研究科情報工学専攻 \\Interdisciplinary Information Engineering, Graduate School of Engineering and Science, University of the Ryukyus.} \affilabel{2}{琉球大学工学部情報工学科\\Information Engineering, University of the Ryukyus.} % 和文著者名 \author{ - 仲松 栞\affiref{2} - \and - 照屋 のぞみ \affiref{1} - \and 河野 真治\affiref{1} } % 英文著者名 \eauthor{ - Nakamatsu Shiori\affiref{2} - \and - Teruya Nozomi\affiref{1} - \and Shinji KONO\affiref{1} } % 連絡先（投稿時に必要．製版用では無視される．） -\contact{仲松 栞\\ +\contact{河野真治\\ 〒903-0213 沖縄県西原町千原1番地\\ 琉球大学工学部情報工学科\\ TEL: (098)895-2221\qquad FAX: (098)895-8727\\ - email: suruga@cr.ie.u-ryukyu.ac.jp} + email: kono@ie.u-ryukyu.ac.jp} % 和文概要 \begin{abstract} @@ -97,36 +88,57 @@ % 本文はここから始まる % Introduce -\section{サービス利用に適したデータベース} -データのネスト構造を許さない第一正規系を要求するRDBの表構造は、Jsonなどの不定形のデータ構造とミスマッチを起こしてしまうという問題がある。 -この問題はデータベースのインピーダンスミスマッチと呼ばれている。 -不定形の構造の変更をトランザクションとしてJsonの一括変更という形で処理する方法が考えられるが、並列処理が中心となってきている今のアプリケーションには向いているとは言えない。 -これらの問題を解決するため、当研究室では、分散処理環境で動くことができるデータベースを目指して非破壊的木構造データベースJungleを開発している。 +\section{分散アプリケーションとフレームワーク} +現代のサービスはInternetと切り離せない形で提供されている。それらは比較的ad-hocに開発発展してきたHTTP上に構築されている。 +一方で、分散データベースや分散プログラムをサポートするフレームワークの研究も古くから行われてきている。例えば、 +MySQLやPostgressなどのオープンソースデータベースでもリプリケーションなどの分散技術を採用するようになってきている。 +HTTPもセキュリティを重視したHTTPSや、HTTP上のファイル変更プロトコルであるWebDAVなどが導入されてきている。 +残念ながら、いまだに定番の分散フレームワークは存在せず、分散データベースも広く使われるようにはなっていない。 +古くに提案された分散フレームワークCORBAや、KVSとして導入されたCassandraあるいはHDFSなども企業内ネットワークで +使われるに留まっている。 + +現代のOSには階層型ファイルシステムが必須なものとして備わっており、ファイルシステムの分散版が使われるようになると期待された +時期もあった。Andrew File System などが設計されたが、広く使われるにはいたらなかった。 +本論文では、当研究室で開発してきた分散フレームワークAliceと、それを用いて実装された分散木構造データベースJungleを +見直すことにより、幅広く使われる分散サービスを構築するためのフレームワークのあるべき姿について考察する。 + + +\section{分散フレームワークAlice} +ネットワーク上のサービスには、利用者数の爆発的な増加を受け入れるスケールアウト(サーバの数を増やすことによりサービスの質を維持する手法) +が必須である。 +安定したネットワークサービスを提供するためには、分散プログラムに信頼性とスケーラビリティが要求される。 +ここでいう信頼性とは、定められた環境下で安定して仕様に従った動作を行うことを指す。 + +分散プログラムには以下の３つの要素がある\cite{Framework}。 +\begin{itemize} +\item {ノード内の計算} +\item {ノード間通信} +\item {地理的に分散したノード} +\end{itemize} + +本研究室で開発された分散フレームワーク +Aliceは、タスクをCode Segment、データをData Segmentという単位で記述し、Code SegmentはインプットとなるData Segmentが全て揃うと並列に実行される。 +Data Segmentは対になるkeyが存在し、Data Segment Managerというノードごとに存在する独自のデータベースによって管理されている。 +通信する各ノードに対応するラベル付きのプロキシであるRemote Data Segment Managerを立て、ラベルとkeyを指定してデータをtake/putする。 +Linda のTuple spaceをノード毎に用意したような構造になっている。Linda と異なり、Tuple space が全世界で一つということはない。 + +AliceではTopologyManagerという機構が分散ノードを管理しており、静的・動的なトポロジーを自動構成する。静的トポロジーではプログラマがトポロジーを図として記述できるため +、より分かりやすく詳細な設定ができる。 +TopologyManager内にはKeepAliveという機能があり、常にノードが生きているかHeartbeatを送信して監視しており、どこかのノードに障害が起こればトポロジーを再構成す +るといった対応ができる。 + +\section{木構造分散データベースJungle} + +Web上の情報は複雑な木構造を持っていて、それを相互に参照する形式を持っている。Web上の相互参照はURIによるものだが、URIの存在は保証されているわけではなく、 +リンク切れなどが存在する。広く使われるようになったRDBは、基本的にはネスト構造を持たない表の集まりであり、Web上の情報には直接は対応しない。 +そこで、本研究室では木構造を直接扱うデータベースJungle を提案している。Jungle では、 木構造を扱えることによって、従来のRDBとは異なり、XMLやJsonで記述された構造を、データベースを設計することなく読み込むことが可能である。 -また、その木をそのままデータベースとして使用することも可能である。 -非破壊的木構造とは、データの元の木を直接書き換えずに保存し、新しく構築した木のデータ構造を編集する方法である。 - これにより、データの書き込み中であっても、元のデータは変更されない為、読み込みも同時に行うことができる。 - Jungleは、読み込みは高速に行える反面、書き込みの手間は木の形・大きさに依存しており、最悪の場合O(n)となってしまう。 - また、Index の構築も大幅なネックとなっていた。 - そこで、本研究ではJungleの木と Index の編集機能の改善を行う。 - また、分散環境におけるJungleの書き出し速度の測定方法の提案をする。 -\section{非破壊的木構造データベースJungle} -Jungleは、当研究室で開発を行っている非破壊的木構造データベースで、Javaを用いて実装されている。非破壊的木構造とは、データの編集を一度生成した木を上書きせず、ルートから編集を行う位置までのノードをコピーする特徴を持つ（図\ref{fig:non_destructive_tree} ）。これにより、読み込み中にデータが変更されないことが保証されているため、書き込みと読み込みを同時に行うことできる。 - \begin{figure}[ht] - \begin{center} - \includegraphics[width=70mm]{./pic/non_destructive_tree.pdf} - \end{center} - \caption{非破壊的木構造の編集} - \label{fig:non_destructive_tree} -\end{figure} -Jungleは名前付きの複数の木の集合からなり、木は複数のノードの集合でできている。ノードは自身の子のリストと属性名、属性値を持ち、データベースのレコードに相応する。通常のレコードと異なるのは、ノードに子供となる複数のノードが付くところである。また、親と子相互で参照しあうことができる破壊的木構造データベースとは違い、非破壊的木構造であるJungleは、親から子への片方向の参照しかできない。通常のRDBと異なり、Jungleは木構造をそのまま読み込むことができる。例えば、XMLやJsonで記述された構造を、データベースを設計することなく読み込むことが可能である。また、この木を、そのままデータベースとして使用することも可能である。しかし、木の変更の手間は木の構造に依存する。特に非破壊木構造を採用しているJungleでは、木構造の変更の手間はO(1)からO(n)となりえる。つまり、アプリケーションに合わせて木を設計しない限り、十分な性能を出すことはできない。逆に、正しい木の設計を行えば高速な処理が可能である。Jungleは基本的にon memoryで使用することを考えており、一度、木のルートを取得すれば、その上で木構造として自由にアクセスして良い。Jungleは分散データベースを構成するように設計されており、分散ノード間の通信は木の変更のログを交換することによって行われる。持続性のある分散ノードを用いることでJungleの持続性を保証することができる。 +Jungle では非破壊的木構造を採用している。データの元の木を直接書き換えずに保存し、新しく構築した木のデータ構造を編集する方法である。 +木構造は、そのルートをAtomic に書き換えることにより、その変更の整合性を維持する。ルート複数存在しURIに相当するラベルを持っている。 +木に対する変更をlogとして記録し、それをAliceによって通信し、分散データベースを構成している。 -\section{Jungleの構成要素} - -\subsection*{[NodePath]} Jungle では、木のノードの位置を NodePath クラスを使って表す。 NodePath クラスはルートノードからスタートし、対象のノードまでの経路を数字を用いて指し示す。また、ルートノードは例外として-1と表記される。 NodePath クラスを用いて \textless -1,0,2,3 \textgreater を表している際の例を(図\ref{fig:nodepath})に示す。 - - \begin{figure}[htpb] +\begin{figure}[htpb] \begin{center} \includegraphics[width=60mm]{./pic/nodepath.pdf} \end{center} @@ -134,141 +146,22 @@ \label{fig:nodepath} \end{figure} -\subsection*{[Index]} -Jungleは、非破壊的木構造というデータ構造上、過去の版の木構造を全て保持している。よって、すべての版に独立したIndexが必要となるため、前の版のIndexを破壊すること無く、Indexを更新する必要がある。既存の TreeMap では、一度 Index の複製を行い、その後更新する必要があったため、Indexの更新オーダーがO(n)となっていた。その問題を解決するため、Java 上で関数型プログラミングを行えるライブラリである、 Functional Java の TreeMap を使用し、それを用いてIndexは実装されている。この TreeMap は、 Jungle と同じようにルートから変更を加えたノードまでの経路の複製を行い、データの更新を行なった際、前の版と最大限データを共有した新しい TreeMap を作成する。JungleでIndexを実装した場合と違いは、木の回転処理が入るという点である。これにより複数の版すべてに対応した Index をサポートすることが可能になった。 -\subsection*{[非破壊TreeMap]} -Jungle の Index は、Functional Java の非破壊 TreeMap を用いて実装を行なっている。しかし、Functional Java の TreeMap は、木の変更の手間が大きい、並列実行処理速度が落ちるなど、実用的な性能を持っていなかった。そのため、Jungleの性能も、TreeMap 部分がネックとなっていた。その問題を解決するため、 Jungle で使用する非破壊 TreeMap を作成した。TreeMap は、Red Black Tree のアルゴリズムを用いている。RedBlackTreeとは二分木探索の一つで、以下の条件を満たした木のことである。 -\begin{itemize} - \item 各ノードは赤か黒の色を持つ。 - \item ルートノードは黒色である。 - \item 全ての葉は黒色である。 - \item 赤いノードの子は黒色である。 - \item 全ての葉からルートノードまでのパスには、同じ個数の黒いノードがある。 -\end{itemize} - -\section{Indexの差分Updateの実装} -Jungleは木の編集を行う際に、編集を行うノードと、経路にあるノードの複製を行い新しい木構造を構築するため、 Index の中には、編集後の木には存在しない複製前のノードが残ってしまう。なので、 Index の差分 Update を行う際には、それらのノードを Index から削除して、新しく複製されたノードを Index に登録する必要がある。そのためには、編集を行なったノードを覚えておく必要がある。そこで、 Jungle Tree Editor 内に、編集を加えたノードを覚えておくためのリストを定義した。 Editor は木に編集を加えた際、リストに編集前のノードを保存する。そして、Commit 時にリストにあるノードを使って Index の中に残っている、編集後の木に存在しないノードを削除する。その後、新しく作られたノードを Index に登録して Update は終了する。 - +木のノードを他の木から参照することが必要な場合には、ノードにIndexを張ることができる。 +Jungleは、非破壊的木構造というデータ構造上、過去の版の木構造を全て保持している。よって、すべての版に独立したIndexが必要となるため、前の版のIndexを破壊すること無く、Indexを更新する必要がある。 +そのために非破壊なRed Black Tree をJava上に開発した。 -\paragraph* {編集前ののノードの削除} -ndex のUpdate を行う際、初めに、編集後の木に存在しないノードを Index から削除する。削 -除の対象は、変更を加えたノードと、ルートから変更を加えたノードまでの経路にあるノード -である。ノードの削除は、以下の手順で行われる。 - \begin{itemize} - \item 編集を行なったノードのリストからノードを取得する。 - \item 取得したノードが、保持している値をIndex から削除する。 - \item 自身と子供のペアを Parent Index から削除する。 - \item ParentIndex から親を取得する。 - \item 2 - 4 をルートノードにたどり着くか、 ParentIndex から親を取得できなkなるまで続ける。 - \item 1 - 5 をリストからノードが無くなるまで続ける。 -\end{itemize} -Parent Index に現在のノードが登録されていない場合は、現在のノードからルートまでの経路にあるノードはIndexから削除されているため、削除を終えて、リストに入っている次のノードの削除処理を行なっても構わない。 - -\paragraph* {Indexへのノードの挿入} -Index から不要なノードを削除した後は、木の編集時新しく作られたノードを Index に挿入する。ノードの挿入は、以下の手順で行われる。 - \begin{itemize} - \item 木からルートノードを取得する - \item 取得したノードがIndex に登録されているかを調べる。 - \item 登録されている場合、そのノード以下の Sub treeは、全てIndexに登録されているので、次のノードに移動する。 - \item 登録されていなかった場合、自身が保持している値をIndex に登録する。 - \item 自身と子ノードを Parent Index に登録する。 - \item 自身の子ノードを取得したノードとして２に戻る。 - \item 全てのノードを登録したら終了する。 -\end{itemize} - -\section{Differential Jungle Treeの実装} -Jungleは木の編集時、ルートから編集を行う位置までのノードの複製を行う。そのため、木の編集の手間は、木構造の形によって異なる。特に線形の木は、全てのノードの複製を行うため、変更の手間がO(n)になってしまう。そこで、Jungleは、線形の木をO(1)で変更するPushPop の機能を持つ。PushPop とは、ルートノードの上に新しいルートノードを付け加える API である(図\ref{fig:PushPopDemerit} )。すると、木の複製を行う必要が無いため、木の変更の手間がO(1)でノードの追加を行える。 - \begin{figure}[ht] - \begin{center} - \includegraphics[width=70mm]{./pic/PushPopDemerit.pdf} - \end{center} - \caption{PushPop} - \label{fig:PushPopDemerit} -\end{figure} -しかし、PushPopはルートノードを追加していくため、(図\ref{fig:PushPopDemerit} )のようにノードの並びが逆順になってしまう。Logなどの正順の木でなければデータを表現できない場合、木の編集時PushPop を使用できない。そこで、木の編集の手間を O(1) で、正順の木を構築できるDifferential Jungle Tree の実装を行なった。 Differential Jungle Tree は。木のバージョンごとに、自身の木の最後尾を表す末尾ノードを保持する。木の編集は、別途構築したSub Tree に対して破壊的に更新を行い、Commit 時に末尾のノードに Sub Tree を Append することで行う。この場合は木が破壊的に変更されているように見えるが、前の版の末端部分を超えてアクセスすることがなければ複数の版を同時に使用することができる。 - -\paragraph* {Differential Tree Context} -Jungleの木はTreeContext というオブジェクトに自身の木の情報を保持している。Differential Jungle Tree では、現在の版の木構造の末尾ノードを保持することが可能な Differential Tree Context を作成した。 - - \paragraph* {Differential Jungle Tree の作成} - Differential Jungle Tree を作成するためにJungle に、新しいAPIを実装した(表\ref{table:Differential API})。 +Jungleは、読み込みは高速に行える反面、書き込みの手間は木の形・大きさに依存している。 +通常の変更ではルートから編集を行う位置までのノードの複製を行う。そのため、木の編集の手間は、木構造の形によって異なる。特に線形の木は、全てのノードの複製を行うため、変更の手間がO(n)になってしまう。 +それに対処するために、木の変更アルゴリズムを三種提供している。 -\begin{table}[htb] - \begin{center} - \caption{Jungleに新しく実装したAPI} - \begin{tabular}{|p{3cm}|p{4cm}|} \hline - \hline \shortstack{ createNewDifferenceTree\\ (StringtreeName)}& Jungleに新しくDifferential Jungle Treeを生成する。木の名前が重複した場合、生成に失敗し null を返す。\\ - \hline - \end{tabular} - \label{table:Diffetential API} - \end{center} -\end{table} - - -\paragraph* {末尾ノードを使用した木の編集} -Differential Jungle Tree の木の編集は、Differential Jungle Tree Editor を使用して行う。 Differential Jungle Tree Editor は、Default Jungle Tree Editor と違い、生成時に新しい木構造(Sub Tree)を自身の中に構築する。そして、木の編集は、Editor が保持している木構造に対して行う。編集後、Commit を行う際に構築した木構造を、 Differential Jungle Tree の末尾ノードにAppend する。その際木の複製は行わない。 - また、Differential Tree は自身が保持している木構造に対する変更しか行えないため、一度Commit した木に対して変更は行えない(図\ref{fig:EditDifferencialTree})。 - -\begin{figure}[ht] - \begin{center} - \includegraphics[width=80mm]{./pic/EditDifferencialTree.pdf} - \end{center} - \caption{末尾ノードを使用した木の編集} - \label{fig:EditDifferencialTree} -\end{figure} - -\begin{itemize} - \item 木からgetJungleTreeEditor で Editor を取得する。（このとき Editor は新しい木構造(Sub Tree)を持つ）。 - \item Editorが保持している木構造に対して addNewChild( \textless-1.0\textgreater)を実行し、ノードの追加を行う。 - \item Commit を行い、Treeの末尾ノードにEditorが保持している木構造を Append する。 -\end{itemize} -Editor が保持している木構造に最後に追加したノードが、新しい木の末尾ノードとなる。また、Differential Jungle Tree は、木の編集時複製を行わないため、 Index のアップデートは、 Editor が保持している木構造のデータを Index に追加するだけで良い。 - - \paragraph* {Differential Jungle Tree の検索} - Differential Jungle Tree は、末尾ノードを使って、現在の木構造を表現している。なので、過去の木に対して全探索を行なった場合、その版には無いはずのノードが取得できてしまう。例として、編集前の木である Tree ver1 と編集後の木である Tree ver2 があるとする(図\ref{fig:Differential_Interface_Traverser})。ここで、Tree ver1 に対して、全探索を行なった場合、本来Tree ver1 に存在しないノード3・４も検索対象に含まれてしまう。そこで、その版の木が持つ末尾ノード以下のSub Tree を検索対象から除外する、Differential Interface Traverser を実装した。Differential Interface Traverserを用いて木の全探索を行なった場合、Tree ver1 に存在しないノード３・４は検索対象から省かれる。 +線形の木をO(1)で変更するPushPop は、ルートノードの上に新しいルートノードを付け加える API である、木の複製を行う必要が無いため、木の変更の手間がO(1)でノードの追加を行える。 -\begin{figure}[ht] - \begin{center} - \includegraphics[width=60mm]{./pic/Differential_Interface_Traverser.pdf} - \end{center} - \caption{複数の版の木の表現} - \label{fig:Differential_Interface_Traverser} -\end{figure} - Index を使用した検索を行う場合、各版の木に対応した Index があるため、Default Tree と検索のアルゴリズムは変わらない。これらの実装により Differential Jungle Tree は木構造の構築・検索を行う。 - -\paragraph* {Differential Jungle Tree の検索} - Differential Jungle Tree への Commit は、編集後の木のデータを持つ TreeContext を作り、編集前の木が持つ TreeContext と Atomic に入れ替えることで行われる。しかし、Differential Jungle Tree のCommit は、Default Jungle Tree の Commit と異なり、TreeContext の入れ替えと、 Editor が保持している木構造の末尾ノードへの Append の２つのプロセスからなる。 TreeContext の入れ替えに関しては、 Default Jungle Tree と同じように行い、末尾ノードへの Editor が持っている木構造の Append は、TreeContect の入れ替えが成功した後に行う。そうすることで、別Thread で行われている Commit と競合した際に、 TreeContext を入れ替えた Thread と別 Thread がAppend を行い、木の整合性が崩れることを回避している。また、過去の版の木に対して、編集を加えCommit を行なった場合、木の整合性が崩れてしまう問題もある。(図\ref{fig:Differential_Interface_Traverser})(図\ref{fig:Tree_ver2})を例に解説する。（図\ref{fig:Differential_Interface_Traverser}）の過去の版の木 Tree ver1 に新しいノード５を追加・Commit を行うと、新しい木 Tree ver'2 が構築される。ここで、Tree ver'2 に対して全検索を行う。differential Jungle Tree に対する全検索は、末尾ノードよ上にあるノードを検索対象にする。しかしノード３・４という、本来存在しないはずのノードが検索対象に含まれてしまう。これは、過去の版の木である、 tree ver1 の末尾ノードが２つの子ノードを持っているせいで発生する。この問題を解決するために、Differential Jungle Tree では、過去の木に対する変更を禁止している。具体的には。末尾ノードは子を１つしか持つことができないようにした。そうすることで木の整合性を保証している。 - - -\begin{figure}[ht] - \begin{center} - \includegraphics[width=50mm]{./pic/Tree_ver2.pdf} - \end{center} - \caption{木の整合性が崩れる例} - \label{fig:Tree_ver2} -\end{figure} +しかし、PushPopはルートノードを追加していくため、ノードの並びが逆順になってしまう。Logなどの正順を要求する場合に対処するために、 +Differential Jungle Tree の実装を行なった。 Differential Jungle Tree は。木のバージョンごとに、自身の木の最後尾を表す末尾ノードを保持する。木の編集は、別途構築したSub Tree に対して破壊的に更新を行い、Commit 時に末尾のノードに Sub Tree を Append することで行う。この場合は木が破壊的に変更されているように見えるが、前の版の末端部分を超えてアクセスすることがなければ複数の版を同時に使用することができる。 -\section{Red Black Jungle Tree の実装} -Jungle は木に編集を加えた際、ルートから編集を行う位置までのノードをコピーする。その為、木の編集の手間は木の大きさにも依存している。バランスの取れた木構造を構築することで、編集の手間をO(log n)にすることは可能だが、Default Jungle Tree の場合、ユーザーがPath を用いて、バランスを取りながら木を構築する必要がある。しかし、ユーザーが全ての木構造の形を把握し、バランスの取れた木を構築するのは困難である。そこで、自動で木のバランスを取り、最適な形の木構造を構築する機能を持つ Red Black Jungle Tree を実装した。バランスは、木の生成時に特定の Balance Key を決定し、それを使って行う。木のバランスを取るアルゴリズムは、前述した非破壊 TreeMap と同じものを使用する。しかし、木の編集を加えた際、木がどのようにバランスを取るか予想するのは困難であるため、木構造自体がデータを表現していない場合に限る。また、自身の木構造が、Balance Key を使った Index と同じ働きを持つため、木のCommit 時に別途 Index を構築する必要が無い、といったメリットもある。 - -\paragraph* {Red Black Jungle Tree の作成} - Red Black Jungle Tree を作成するため、Jungle に新しいAPIを実装した。(表\ref{table:Diffetential API}) +完全にランダムな変更が巨大な木に対して必要な場合には、Jungleの木そのものをRed Black Tree として構築する手法を使うことができる。この場合は木の構造を固定することはできないが、 +O(log n)での木の変更が可能になる。これは表構造そのものになる。これにより、Jungle をRDBして使うことも可能になった。Reb Black Jungle Tree 用には専用のNode Pathが提供される。 -\begin{table}[htb] - \begin{center} - \caption{Jungleに新しく実装したAPI} - \begin{tabular}{|p{3cm}|p{4cm}|} \hline - \hline \shortstack{ createNewRedBlackTree\\ (StringtreeName, \\String balanceKey)}& Jungleに新しくRed Black Jungle Treeを生成する。第一引数に木の名前、第２引数に木のバランスを取る時に使用する Balance Key を受け取る。木の名前が重複した場合、生成に失敗し null を返す。\\ - \hline - \end{tabular} - \label{table:Diffetential API} - \end{center} -\end{table} - -\paragraph* { NodePath の拡張} -Red Black Jungle Tree は、ノードを追加・削除するたびに木のバランスが行われ、各ノードの Path が変わってしまう。その為、数 -字を使った NodePath では、編集を加える際、編集対象のノードの Pathを毎回調べる必要がある。その問題を解決するためにNodePath を拡張した Red Black Tree Node Path を作成し、属性名 BalanceKey 属性値 value のペアでノードを指定できるようにした。 Red Black Jungle Node Path は、引数に String 型の BalanceKey と ByteBuffer 型の value を取る。 -Red Black Tree Node Path で指定できる属性名は、木の生成時に宣言した属性名しか使用できない。これは、Red Black Jungle Tree が木の生成時に宣言した属性名でソートされているからである。 \section{分散環境でのJungleDBの書き出し実験方法の提案} Jungleは分散環境で動くデータベースを目指して開発している。 Jungleには大量の様々な木が存在し、その大きさも様々である。