--- a/paper/sigos.tex	Fri Apr 21 19:02:00 2017 +0900
+++ b/paper/sigos.tex	Fri Apr 21 20:14:17 2017 +0900
@@ -71,8 +71,24 @@
 
 % 和文概要
 \begin{abstract}
-コンピュータの性能が向上するにつれ、ソフトウェアやアプリケーションを高速に動作させる需要が求められてきた。しかし、RDB
-では、同時書き込みの際に起こる競合を防ぐため、編集中にロックがかけられ、編集に時間がかかってしまう。また、不定形のデータ構造と表構造がミスマッチを起こしてしまう、インピーダンスミスマッチという問題がある。そこで当研究では、非破壊的木構造データベースJungleを開発している。非破壊的木構造により、読み込みと書き込みを同時に実行することができる。また、データベースの再設計を行わずに不定形のデータ構造を扱うことが可能である。本研究ではJungleの木と Index の編集機能の改善を行う。また、分散環境におけるJungleの書き出し速度の測定方法の提案をする。
+現代のインターネットやアプリケーションで使われるデータは、複雑な構造を持っており、RDBの第一正規系には納まらないようになってきている。
+また、RDBでは、編集中にロックがかけられ、複雑な構造に対する変更に向いていない。
+これらの問題は、不定形のデータ構造とRDBの表構造のミスマッチである。
+これをDBのインピーダンスミスマッチと言うことがある。
+そこで当研究室では、非破壊的木構造データベースJungleを開発している。
+Jungleでは、不定形のデータ構造を、直接木構造として格納することができる。
+木構造の変更は、過去の版を保存する非破壊で行われ、木のルートをAtomicに入れ替える操作がトランザクションになる。
+これにより、複雑な構造をDBとして素直に取り扱うことができる。
+木構造の変更は、木の形に依存している。
+サービスやアプリケーションに適した木の形があり、それに対応した木の変更方法を採用する必要がある。
+本研究ではJungleの木と Index の編集機能の改善を行う。
+直線的なリスト構造に適したPush/Popと差分リストを提案し、実装と評価を行なった。
+巨大な木が必要な場合は、木を特定のKeyを用いてbalanceさせることにより、変更をO(log n)にすることができる。
+Jungleは分散構造を取ることもできる。
+複数の木を複数の分散したJungleノード間で通信することにより、Jungleをスケールさせる。
+Jungleの木の変更Logを当研究室で開発した分散フレームワークAliceを用いて通信する。
+それぞれの木は、ルートノードに集約され、集約の過程で、競合する変更のMergeを行う。
+分散Jungleの性能を測定する手法について述べる。
 \end{abstract}
 
 % 表題などの出力
@@ -82,8 +98,18 @@
 
 % Introduce
 \section{サービス利用に適したデータベース}
-CPUのマルチコア化により、コンピュータのCPU性能が格段に上がった。マルチコアCPUの普及により、一般的なコンピュータの性
-能も向上してきた。コンピュータの性能が向上するにつれ、分散に適したデータベースや分散データベースの速度を向上させる需要が求められてきた。しかし、RDBでは、１一人のユーザーがデータを書き込んでいるとき、他のユーザーが書き込みをしてくることで起こるデータの競合を防ぐために、書き込みが終わるまでロックをかける必要がある。これにより、データの編集に時間がかかってしまうという問題がある。また、データのネスト構造を許さない第一正規系を要求するRDBの表構造は、Jsonなどの不定形のデータ構造とミスマッチを起こしてしまうという問題がある。この問題はデータベースのインピーダンスミスマッチと呼ばれている。不定形の構造の変更をトランザクションとしてJsonの一括変更という形で処理する方法が考えられるが、並列処理が中心となってきている今のアプリケーションには向いているとは言えない。これらの問題を解決するため、当研究室では、分散処理環境で動くことができるデータベースを目指して非破壊的木構造データベースJungleを開発している。木構造を扱えることによって、従来のRDBとは異なり、XMLやJsonで記述された構造を、データベースを設計することなく読み込むことが可能である。また、その木をそのままデータベースとして使用することも可能である。非破壊的木構造とは、データの元の木を直接書き換えずに保存し、新しく構築した木のデータ構造を編集する方法である。 これにより、データの書き込み中であっても、元のデータは変更されない為、読み込みも同時に行うことができる。Jungleは、読み込みは高速に行える反面、書き込みの手間は木の形・大きさに依存しており、最悪の場合O(n)となってしまう。また、Index の構築も大幅なネックとなっていた。そこで、本研究ではJungleの木と Index の編集機能の改善を行う。また、分散環境におけるJungleの書き出し速度の測定方法の提案をする。
+データのネスト構造を許さない第一正規系を要求するRDBの表構造は、Jsonなどの不定形のデータ構造とミスマッチを起こしてしまうという問題がある。
+この問題はデータベースのインピーダンスミスマッチと呼ばれている。
+不定形の構造の変更をトランザクションとしてJsonの一括変更という形で処理する方法が考えられるが、並列処理が中心となってきている今のアプリケーションには向いているとは言えない。
+これらの問題を解決するため、当研究室では、分散処理環境で動くことができるデータベースを目指して非破壊的木構造データベースJungleを開発している。
+木構造を扱えることによって、従来のRDBとは異なり、XMLやJsonで記述された構造を、データベースを設計することなく読み込むことが可能である。
+また、その木をそのままデータベースとして使用することも可能である。
+非破壊的木構造とは、データの元の木を直接書き換えずに保存し、新しく構築した木のデータ構造を編集する方法である。
+ これにより、データの書き込み中であっても、元のデータは変更されない為、読み込みも同時に行うことができる。
+ Jungleは、読み込みは高速に行える反面、書き込みの手間は木の形・大きさに依存しており、最悪の場合O(n)となってしまう。
+ また、Index の構築も大幅なネックとなっていた。
+ そこで、本研究ではJungleの木と Index の編集機能の改善を行う。
+ また、分散環境におけるJungleの書き出し速度の測定方法の提案をする。
 \section{非破壊的木構造データベースJungle}
 Jungleは、当研究室で開発を行っている非破壊的木構造データベースで、Javaを用いて実装されている。非破壊的木構造とは、データの編集を一度生成した木を上書きせず、ルートから編集を行う位置までのノードをコピーする特徴を持つ（図\ref{fig:non_destructive_tree} ）。これにより、読み込み中にデータが変更されないことが保証されているため、書き込みと読み込みを同時に行うことできる。
   %木のルートをAtomicに置き換えることで、木のアップデートを行う。変更前の木が残っているので、そのまま使用できる。変更されないノードは変更前と変更後のルートから共有されることになる。
@@ -256,11 +282,43 @@
 
 
 \section{分散環境でのJungleDBの書き出し実験方法の提案}
-Jungleは分散環境で動くデータベースを目指して開発している。そこで、Jungleの実用性を示すために、分散環境での通信速度の測定を行う必要がある。今回、実験で分散構造としてJungleの動くノード16台を木構造に接続する。この木のルートノードをルートjungleと呼び、末端ノードをリーフjungleと呼ぶ。
-<図>
-まず、末端のJungleにUserが書き込みをし、Jungleからuserにレスポンスが返ってくるまでの時間を測定する。次に、Jungleの変更がルートのJungleにコピーされるまでの時間の測定方法を提案するJungle同士の接続には、当研究室で開発している分散フレームワークであるAliceを用いる。
+Jungleは分散環境で動くデータベースを目指して開発している。
+Jungleには大量の様々な木が存在し、その大きさも様々である。
+それぞれの木を異なるJungleノードに格納することにより、木が大量になる場合にも一定した性能が出るようにしたい。
+一つの木が極端に大きくなる場合もあるが、それを分散して格納するのは難しい。
+ここでは、一つの木は一つのノードに納まる大きさだと仮定する。
+Jungleの木は信頼性向上とアクセス速度の向上のために、複数のノードに格納される。
+木の変更は複数のノードを伝搬し、特定のJungleの木のルートノードに到達する。
+そこで、木の状態が確定する。
+一つのルートノードではなく、複数のノードに対して、多数決などの方法を用いることも考えられるが、
+今回は単一のルートノードを用いる。
+この方法は、読み込みに対して書き込みが少ない場合、あるいは書き込みが単一ノードのみからくる場合に有効であると考えられる。
+
+従来のJungleDBの分散機能の測定はJetty Webサーバー込みで行なっており、DBに対する負荷は直接的には大きくなかった。
+JungleDBに対して十分な負荷をかけるhttpリクエストを生成するのは困難であった。
+そこで、Jungleの分散性能そのものを調べるために、Webサーバー抜きで測定したい。
+
+JungleDBの通信は、研究室で開発した分散フレームワークAliceによって行われる。
+Aliceはノードの木構造接続を自動的に行うTopologyManagerを持っている。
+ここでは、Jungleの木それぞれに対してノードの木構造を別々に構成する必要がある。
+これは、TopologyManagerを改良することによって行う。
+Aliceはまた、通信を圧縮して行う機能も持っており、それによる高速化も期待できる。
+通信されるのは、Jungleの木に対する変更Logであり、これをまとめて転送することにより、圧縮がうまく働くと期待される。
+複数のノードの変更は、互いに競合することがあり、ノード間をルートに向かって通信していく間に競合を解消する必要がある。
+これをMergeをいう。
+従来のDBのような変更では、Mergeが失敗することがある。
+失敗した場合は、複数の木構造がまとめて失敗してしまう。
+JungleではMergeが失敗しないような場合、例えば、SNSへのコメントの追加などではうまく働く。
+従来のDBとしてJungleを使う場合には、単一ノードで使用するか、多数決Commitを使うことになるが、ここではそれは測定しない。
+
+今回、実験で分散構造としてJungleの動くノード16台を木構造に接続する。
+この木のルートノードをルートjungleと呼び、末端ノードをリーフjungleと呼ぶ。
+（図）
+まず、末端のJungleにUserが書き込みをし、Jungleからuserにレスポンスが返ってくるまでの時間を測定する。
+次に、Jungleの変更がルートのJungleにコピーされるまでの時間の測定方法を提案するJungle同士の接続には、当研究室で開発している分散フレームワークであるAliceを用いる。
 \section{まとめ}
 本研究では、始めに破壊的木構造データベースであるJungleについて説明を行い、次にJungleの性能を上げるために実装した点を挙げ、最後に分散環境での Jungle の書き出し実験の手法について述べた。実装した点は、まず Jungle の Index の Update を高速化させるために、前の版の Index と値を共有しながら Update を行う、差分 Update の実装を行なった。次に、線形の木を正順で構築する際、木の変更の手間が O(n) になる問題を解決するために、 Differential Jungle Tree の実装をした。 Differential Jungle Tree は、自身の末尾のノードの情報を保持している。この末尾ノードを使用して、木の編集や検索を行う。次に、自動的に木のバランスを行い、最適な形の木構造を構築する Red Black Jungle Tree を実装した。 Red Black Jungle Tree は、自身が Index を構築する Default Jungle Tree により、編集できる。また、ノードは、木のバランスによって Path が編集ごとに変わってしまうため、属性名と属性値のペアでノードを指定できる、 Red Black Jungle Tree Editor の実装を行なった。
+また、Jungleの分散機能に対する測定手法を提案した。
 今後の課題として、Jungleは非破壊でデータを保持し続けるため、非常に多くのメモリを使用してしまう。ある程度の単位で過去のデータの掃除を行いたい。Jungleは、過去の木に対するアクセスをサポートしているため、データの掃除を行うタイミングが明確ではない。なので、メモリから追い出すタイミングを定義する必要がある。