changeset 31:9eb676914f1d

Writed description of jungle edit
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Mon, 27 Jan 2014 19:53:12 +0900
parents 92bc4faa9a37
children 04af243ddd7c
files paper/chapter1.tex paper/chapter2.tex paper/chapter3.tex paper/figures/alice_topology.xbb paper/figures/cap_theorem.xbb paper/figures/cassandra.xbb paper/figures/cassandra_ring.xbb paper/figures/cluster_benchmark.xbb paper/figures/deos_proccess.xbb paper/figures/destructive_tree.xbb paper/figures/distribute_jungle.xbb paper/figures/distributed_repository.xbb paper/figures/dsandcs.xbb paper/figures/merge1.xbb paper/figures/merge2.xbb paper/figures/merge_imp1.xbb paper/figures/merge_imp2.xbb paper/figures/mongodb_sharding.xbb paper/figures/neo4j_replica.xbb paper/figures/network_topology_ring.xbb paper/figures/network_topology_tree.xbb paper/figures/nodepath.pdf paper/figures/nodepath.xbb paper/figures/non_destructive_edit1.xbb paper/figures/non_destructive_edit2.xbb paper/figures/non_destructive_edit3.xbb paper/figures/non_destructive_edit4.xbb paper/figures/non_destructive_merit.xbb paper/figures/non_destructive_tree.xbb paper/figures/nondestructive_edit1.xbb paper/figures/putChildLog.xbb paper/figures/putLog.xbb paper/figures/read_bench.xbb paper/figures/tree_conflict.xbb paper/figures/tree_conflict2.xbb paper/figures/tree_conflict3.xbb paper/figures/tree_topology.xbb paper/figures/treeoperationlog1.pdf paper/figures/treeoperationlog1.xbb paper/figures/write_bench.xbb paper/graffle/nodepath.graffle paper/graffle/treeoperationlog1.graffle paper/master_paper.pdf
diffstat 43 files changed, 170 insertions(+), 119 deletions(-) [+]
line wrap: on
line diff
--- a/paper/chapter1.tex	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/chapter1.tex	Mon Jan 27 19:53:12 2014 +0900
@@ -1,5 +1,4 @@
 \chapter{既存の分散データベース}
-
 % 分散データベースとはなんなのか。
 % データベースはなんなのかをいれないと。
 % NoSQL の説明も必要。
--- a/paper/chapter2.tex	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/chapter2.tex	Mon Jan 27 19:53:12 2014 +0900
@@ -1,13 +1,10 @@
 \chapter{木構造データベースJungleの分散設計}
-
-
-
-\section{木構造データベースJungle}
 Jungle はスケーラビリティのある CMS の開発を目指して当研究室で開発されている非破壊的木構造データベースである.
 一般的なコンテンツマネジメントシステムではブログツールや Wiki・SNS が多く, これらの
 ウェブサイトの構造は大体が木構造であるため, データ構造として木構造を採用している.
+現在 Java と Haskell によりそれぞれ言語で開発されており本研究で扱うのは Java 版である.
 
-まず破壊的木構造と, 非破壊的木構造の説明をし, Jungle におけるデータ編集の実装について述べる.
+本章ではまず破壊的木構造と, 非破壊的木構造の説明をし, Jungle におけるデータ分散の設計について述べる.
 \subsection{破壊的木構造}
 破壊的木構造の編集は, 木構造で保持しているデータを直接書き換えることで行う.
 図\ref{fig:destractive}は破壊的木構造の編集を表している.
@@ -51,7 +48,7 @@
 \begin{figure}[htpb]
   \begin{center}
     \includegraphics[scale=0.7]{figures/non_destructive_edit1.pdf}
-    \caption{非破壊的木構造の編集1}
+    \caption{非破壊的木構造の編集手順1}
     \label{fig:nondestractive_edit1}
   \end{center}
 \end{figure}
@@ -59,7 +56,7 @@
 \begin{figure}[htpb]
   \begin{center}
     \includegraphics[scale=0.7]{figures/non_destructive_edit2.pdf}
-    \caption{非破壊的木構造の編集2}
+    \caption{非破壊的木構造の編集手順2}
     \label{fig:nondestractive_edit2}
   \end{center}
 \end{figure}
@@ -67,7 +64,7 @@
 \begin{figure}[htpb]
   \begin{center}
     \includegraphics[scale=0.7]{figures/non_destructive_edit3.pdf}
-    \caption{非破壊的木構造の編集3}
+    \caption{非破壊的木構造の編集手順3}
     \label{fig:nondestractive_edit3}
   \end{center}
 \end{figure}
@@ -75,14 +72,18 @@
 \begin{figure}[htpb]
   \begin{center}
     \includegraphics[scale=0.7]{figures/non_destructive_edit4.pdf}
-    \caption{非破壊的木構造の編集4}
+    \caption{非破壊的木構造の編集手順4}
     \label{fig:nondestractive_edit4}
   \end{center}
 \end{figure}
 
 \newpage
 
-非破壊的木構造により, データの読み込みと編集を同時に行うことが可能になる.
+非破壊的木構造においてデータのロックが必要となる部分は, 木のコピーを作終えた後に
+ルートノードを更新するときだけである.
+データ編集を行っている間ロックが必要な破壊的木構造に比べ, 編集中においてもデータの読み込みが
+可能である(図\ref{fig:nondestractive_merit}).
+そのため, 破壊的木構造に比べスケールがしやすくなっている.
 
 \begin{figure}[htpb]
   \begin{center}
@@ -93,12 +94,11 @@
 \end{figure}
 
 
-
-\section{Jungleにおけるデータ編集}
+\section{Jungle におけるデータへのアクセス}
 Jungle ではデータをそれぞれの Node が attribute として保持する.
 attribute は String 型の Key と ByteBuffer の value のペアにより表される.
-Jungle でデータ編集を行う場合, この Node に対して削除や attribute の追加等を行うことを指す.
-どの Node へデータの編集を行うかはパスで示す.
+Jungle でデータへのアクセスは, この Node へのアクセスをさす.
+Node へのアクセスは, 木の名前と Node を指すパスにより行える.
 このパスは NodePath と呼ばれる(図\ref{fig:nodepath}).
 
 \begin{figure}[htpb]
@@ -109,8 +109,14 @@
   \end{center}
 \end{figure}
 
-Node の編集は Node の追加・削除, それと attribute の追加・削除を行うことを指す.
-Node の編集のためには次の4つの API が用意されている.
+
+
+\section{Jungle におけるデータ編集}
+
+\subsection{NodeOperation}
+Jungle による最小のデータ編集は Node の編集を指す.
+Node 編集のために API が用意されており, この API は NodeOperation と呼ばれる.
+NodeOperation には次の4つの API が用意されている.
 \begin{itemize}
 \item \verb|addNewChild(NodePath _path, int _pos)|
 NodePath で指定された Node に子供となる Node を追加する API である.
@@ -125,24 +131,25 @@
 NodePath は Node を示す.
 \end{itemize}
 
-この Node 編集の為の API は NodeOperation と呼ばれる.
+NodeOperation はあくまで最小のデータ編集の単位である.
+アプリケーションレベルの実装にもよるが, Jungle によるデータの編集は NodeOperation が複数集まった単位によって行われる.
+この複数の NodeOperation の集まりを TreeOperationLog という.
+
 \subsection{TreeOperationLog}
-API を使用すると, Jungle 内部では NodeOperation として順次ログに積まれていき, 最終的に
-commit されることで編集が行われる.
-この時ログに積まれる複数の NodeOperation を TreeOperationLog という.
-Jungle ではこの TreeOperationLog 単位でデータの編集が行われる.
+Jungle 内部では NodeOperation は順次ログに積まれていき, 最終的に
+commit されることで編集が完了する.
+この時, ログに積まれた複数の NodeOperation は TreeOperationLog として扱われる.
 以下に TreeOperationLog の具体的な例を示す(\ref{src:treelog}).
 \begin{lstlisting}[frame=lrbt,label=src:treelog,caption=トポロジーマネージャーの利用,numbers=left]
 [APPEND_CHILD:<-1>:pos:0]
-[PUT_ATTRIBUTE:<-1,1>:key:author,value:oshiro]
-[PUT_ATTRIBUTE:<-1,1>:key:mes,value:hello]
-[PUT_ATTRIBUTE:<-1,1>:key:key,value:hoge]
-[PUT_ATTRIBUTE:<-1,1>:key:timestamp,value:0]
+[PUT_ATTRIBUTE:<-1,0>:key:author,value:oshiro]
+[PUT_ATTRIBUTE:<-1,0>:key:mes,value:hello]
+[PUT_ATTRIBUTE:<-1,0>:key:timestamp,value:0]
 \end{lstlisting}
 このログは今回の研究で使用したベンチマーク用掲示板プログラムにおける書き込みにより行われるログである(図\ref{fig:treeoperationlog}).
 
-大文字の英字は実行した NodeOperation を表す.
-<> により囲まれている数字は NodePath を示す.
+大文字の英字は実行した NodeOperation の種類を表す.
+\verb|<>| により囲まれている数字は NodePath を示す.
 NodePath の表記以降は Node の position や attribute の情報を表している.
 \begin{figure}[htpb]
   \begin{center}
@@ -152,7 +159,13 @@
   \end{center}
 \end{figure}
 
+図\ref{fig:treeoperationlog}の説明を行う.
+まず, \verb|APPEND_CHILD| により Root Node の 0 番目の子供となる Node の追加を行う.
+次に, 追加を行った Node に対して \verb|PUT_ATTRIBUTE| により attribute の情報を持たせていく.
+attribute の内容に作者の情報を表す auther, メッセージの内容を表す mes, そしてタイムスタンプ
+を timestamp とそれぞれキーにすることで追加される.
 
+以上が掲示板プログラムにおける1つの書き込みで発生する TreeOperationLog である.
 
 \section{分散バージョン管理システムによるデータの分散}
 Jungle は Git や Mercurial といった分散バージョン管理システムの機能を参考に作られている.
@@ -175,7 +188,6 @@
 \end{figure}
 
 
-
 \subsection{マージによるデータ変更衝突の解決}
 分散管理システムでは, データの更新時において衝突が発生する時がある.
 それは, 分散管理システムを参考にしている Jungle においても起こる問題である.
@@ -219,8 +231,11 @@
 
 \newpage
 
+\section{データ分散の設計}
 
 
+\subsection{}
+
 
 \section{データの永続性}
 
--- a/paper/chapter3.tex	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/chapter3.tex	Mon Jan 27 19:53:12 2014 +0900
@@ -1,4 +1,5 @@
 \chapter{Jungleの分散実装}
+
 \section{TreeOperationLogを用いての分散データベースの実装}
 Jungle でデータ扱うと TreeOperationLog として残ることは述べた.
 この TreeOperationLog を他のサーバへと送り, Jungle の編集を行って
--- a/paper/figures/alice_topology.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/alice_topology.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 386.000000 218.000000
 %%PDFVersion: 1.4
 %%Pages: 1
-%%CreationDate: Mon Jan 27 09:08:07 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
--- a/paper/figures/cap_theorem.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/cap_theorem.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 301.000000 231.000000
 %%PDFVersion: 1.4
 %%Pages: 1
-%%CreationDate: Mon Jan 27 09:08:07 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
--- a/paper/figures/cassandra.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/cassandra.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 336.000000 201.000000
 %%PDFVersion: 1.3
 %%Pages: 1
-%%CreationDate: Mon Jan 27 09:08:07 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
--- a/paper/figures/cassandra_ring.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/cassandra_ring.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 400.000000 290.000000
 %%PDFVersion: 1.4
 %%Pages: 1
-%%CreationDate: Mon Jan 27 09:08:07 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
--- a/paper/figures/cluster_benchmark.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/cluster_benchmark.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 479.000000 293.000000
 %%PDFVersion: 1.4
 %%Pages: 1
-%%CreationDate: Mon Jan 27 09:08:07 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
--- a/paper/figures/deos_proccess.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/deos_proccess.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 900.000000 619.500000
 %%PDFVersion: 1.4
 %%Pages: 1
-%%CreationDate: Mon Jan 27 09:08:08 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
--- a/paper/figures/destructive_tree.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/destructive_tree.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 404.000000 207.000000
 %%PDFVersion: 1.4
 %%Pages: 1
-%%CreationDate: Mon Jan 27 09:08:08 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
--- a/paper/figures/distribute_jungle.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/distribute_jungle.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 245.000000 213.000000
 %%PDFVersion: 1.3
 %%Pages: 1
-%%CreationDate: Mon Jan 27 09:08:08 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
--- a/paper/figures/distributed_repository.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/distributed_repository.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 451.000000 280.000000
 %%PDFVersion: 1.4
 %%Pages: 1
-%%CreationDate: Mon Jan 27 09:08:08 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
--- a/paper/figures/dsandcs.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/dsandcs.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 396.000000 256.000000
 %%PDFVersion: 1.3
 %%Pages: 1
-%%CreationDate: Mon Jan 27 09:08:08 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
--- a/paper/figures/merge1.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/merge1.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 427.000000 430.000000
 %%PDFVersion: 1.4
 %%Pages: 1
-%%CreationDate: Mon Jan 27 09:08:08 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
--- a/paper/figures/merge2.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/merge2.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 427.000000 242.000000
 %%PDFVersion: 1.4
 %%Pages: 1
-%%CreationDate: Mon Jan 27 09:08:08 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
--- a/paper/figures/merge_imp1.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/merge_imp1.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 499.000000 243.000000
 %%PDFVersion: 1.4
 %%Pages: 1
-%%CreationDate: Mon Jan 27 09:08:08 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
--- a/paper/figures/merge_imp2.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/merge_imp2.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 467.000000 256.000000
 %%PDFVersion: 1.4
 %%Pages: 1
-%%CreationDate: Mon Jan 27 09:08:08 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
--- a/paper/figures/mongodb_sharding.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/mongodb_sharding.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 417.000000 317.000000
 %%PDFVersion: 1.4
 %%Pages: 1
-%%CreationDate: Mon Jan 27 09:08:08 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
--- a/paper/figures/neo4j_replica.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/neo4j_replica.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 448.000000 262.000000
 %%PDFVersion: 1.4
 %%Pages: 1
-%%CreationDate: Mon Jan 27 09:08:08 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
--- a/paper/figures/network_topology_ring.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/network_topology_ring.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 271.000000 236.000000
 %%PDFVersion: 1.4
 %%Pages: 1
-%%CreationDate: Mon Jan 27 09:08:08 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
--- a/paper/figures/network_topology_tree.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/network_topology_tree.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 329.000000 237.000000
 %%PDFVersion: 1.4
 %%Pages: 1
-%%CreationDate: Mon Jan 27 09:08:08 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
Binary file paper/figures/nodepath.pdf has changed
--- a/paper/figures/nodepath.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/nodepath.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -1,8 +1,8 @@
 %%Title: ./nodepath.pdf
 %%Creator: extractbb 20130405
-%%BoundingBox: 0 0 315 310
-%%HiResBoundingBox: 0.000000 0.000000 315.000000 310.000000
+%%BoundingBox: 0 0 315 340
+%%HiResBoundingBox: 0.000000 0.000000 315.000000 340.000000
 %%PDFVersion: 1.3
 %%Pages: 1
-%%CreationDate: Mon Jan 27 09:08:08 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
--- a/paper/figures/non_destructive_edit1.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/non_destructive_edit1.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 462.000000 207.000000
 %%PDFVersion: 1.4
 %%Pages: 1
-%%CreationDate: Mon Jan 27 09:08:08 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
--- a/paper/figures/non_destructive_edit2.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/non_destructive_edit2.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 470.000000 240.000000
 %%PDFVersion: 1.4
 %%Pages: 1
-%%CreationDate: Mon Jan 27 09:08:08 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
--- a/paper/figures/non_destructive_edit3.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/non_destructive_edit3.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 511.000000 211.000000
 %%PDFVersion: 1.4
 %%Pages: 1
-%%CreationDate: Mon Jan 27 09:08:08 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
--- a/paper/figures/non_destructive_edit4.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/non_destructive_edit4.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 505.000000 218.000000
 %%PDFVersion: 1.4
 %%Pages: 1
-%%CreationDate: Mon Jan 27 09:08:08 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
--- a/paper/figures/non_destructive_merit.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/non_destructive_merit.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 350.000000 301.000000
 %%PDFVersion: 1.4
 %%Pages: 1
-%%CreationDate: Mon Jan 27 09:08:08 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
--- a/paper/figures/non_destructive_tree.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/non_destructive_tree.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 459.000000 207.000000
 %%PDFVersion: 1.4
 %%Pages: 1
-%%CreationDate: Mon Jan 27 09:08:08 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
--- a/paper/figures/nondestructive_edit1.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/nondestructive_edit1.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 438.000000 207.000000
 %%PDFVersion: 1.4
 %%Pages: 1
-%%CreationDate: Mon Jan 27 09:08:08 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
--- a/paper/figures/putChildLog.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/putChildLog.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 385.000000 149.000000
 %%PDFVersion: 1.4
 %%Pages: 1
-%%CreationDate: Mon Jan 27 09:08:08 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
--- a/paper/figures/putLog.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/putLog.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 385.000000 149.000000
 %%PDFVersion: 1.4
 %%Pages: 1
-%%CreationDate: Mon Jan 27 09:08:08 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
--- a/paper/figures/read_bench.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/read_bench.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 360.000000 252.000000
 %%PDFVersion: 1.4
 %%Pages: 1
-%%CreationDate: Mon Jan 27 13:57:49 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
--- a/paper/figures/tree_conflict.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/tree_conflict.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 456.000000 199.000000
 %%PDFVersion: 1.4
 %%Pages: 1
-%%CreationDate: Mon Jan 27 09:08:08 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
--- a/paper/figures/tree_conflict2.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/tree_conflict2.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 475.000000 242.000000
 %%PDFVersion: 1.4
 %%Pages: 1
-%%CreationDate: Mon Jan 27 09:08:08 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
--- a/paper/figures/tree_conflict3.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/tree_conflict3.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 479.000000 241.000000
 %%PDFVersion: 1.4
 %%Pages: 1
-%%CreationDate: Mon Jan 27 09:08:08 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
--- a/paper/figures/tree_topology.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/tree_topology.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 684.000000 237.000000
 %%PDFVersion: 1.4
 %%Pages: 1
-%%CreationDate: Mon Jan 27 09:08:08 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
Binary file paper/figures/treeoperationlog1.pdf has changed
--- a/paper/figures/treeoperationlog1.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/treeoperationlog1.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 595.000000 258.000000
 %%PDFVersion: 1.3
 %%Pages: 1
-%%CreationDate: Mon Jan 27 09:08:08 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
--- a/paper/figures/write_bench.xbb	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/figures/write_bench.xbb	Mon Jan 27 19:53:12 2014 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 360.000000 252.000000
 %%PDFVersion: 1.4
 %%Pages: 1
-%%CreationDate: Mon Jan 27 13:57:49 2014
+%%CreationDate: Mon Jan 27 18:08:43 2014
 
--- a/paper/graffle/nodepath.graffle	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/graffle/nodepath.graffle	Mon Jan 27 19:53:12 2014 +0900
@@ -53,7 +53,45 @@
 	<array>
 		<dict>
 			<key>Bounds</key>
-			<string>{{26, 273}, {208, 28}}</string>
+			<string>{{92, 83}, {163.00000000000006, 18}}</string>
+			<key>Class</key>
+			<string>ShapedGraphic</string>
+			<key>ID</key>
+			<integer>60</integer>
+			<key>Shape</key>
+			<string>Rectangle</string>
+			<key>Style</key>
+			<dict>
+				<key>fill</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>shadow</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>stroke</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+			</dict>
+			<key>Text</key>
+			<dict>
+				<key>Text</key>
+				<string>{\rtf1\ansi\ansicpg1252\cocoartf1265
+\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
+{\colortbl;\red255\green255\blue255;}
+\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
+
+\f0\fs36 \cf0 tree_name}</string>
+			</dict>
+		</dict>
+		<dict>
+			<key>Bounds</key>
+			<string>{{60, 375}, {208, 28}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>FitText</key>
@@ -108,7 +146,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{253, 246}, {48, 18}}</string>
+			<string>{{287, 348}, {48, 18}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>FitText</key>
@@ -161,8 +199,8 @@
 			<integer>56</integer>
 			<key>Points</key>
 			<array>
-				<string>{169.05305440841548, 183}</string>
-				<string>{227.71823047933887, 224.12554931220842}</string>
+				<string>{203.05305440841548, 285}</string>
+				<string>{261.71823047933884, 326.12554931220842}</string>
 			</array>
 			<key>Style</key>
 			<dict>
@@ -202,8 +240,8 @@
 			<integer>55</integer>
 			<key>Points</key>
 			<array>
-				<string>{160.8745931692697, 189.63399464199267}</string>
-				<string>{176.09901765531245, 218.36477549283194}</string>
+				<string>{194.8745931692697, 291.63399464199267}</string>
+				<string>{210.09901765531245, 320.36477549283194}</string>
 			</array>
 			<key>Style</key>
 			<dict>
@@ -230,8 +268,8 @@
 			<integer>54</integer>
 			<key>Points</key>
 			<array>
-				<string>{142.81004419374304, 190.73205310302325}</string>
-				<string>{133.10630674740696, 217.22579082378741}</string>
+				<string>{176.81004419374304, 292.73205310302325}</string>
+				<string>{167.10630674740696, 319.22579082378741}</string>
 			</array>
 			<key>Style</key>
 			<dict>
@@ -258,8 +296,8 @@
 			<integer>53</integer>
 			<key>Points</key>
 			<array>
-				<string>{132.76672715531757, 184.00476228664814}</string>
-				<string>{82.226868755021428, 223.97383281319256}</string>
+				<string>{166.76672715531757, 286.00476228664814}</string>
+				<string>{116.22686875502143, 325.97383281319253}</string>
 			</array>
 			<key>Style</key>
 			<dict>
@@ -276,7 +314,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{225, 216.49299491436881}, {45, 43}}</string>
+			<string>{{259, 318.49299491436881}, {45, 43}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>ID</key>
@@ -322,7 +360,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{164, 216.49299491436881}, {45, 43}}</string>
+			<string>{{198, 318.49299491436881}, {45, 43}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>ID</key>
@@ -357,7 +395,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{103, 216.49299491436881}, {45, 43}}</string>
+			<string>{{137, 318.49299491436881}, {45, 43}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>ID</key>
@@ -387,7 +425,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{42, 216.49299491436881}, {45, 43}}</string>
+			<string>{{76, 318.49299491436881}, {45, 43}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>ID</key>
@@ -427,8 +465,8 @@
 			<integer>48</integer>
 			<key>Points</key>
 			<array>
-				<string>{133.05305440841548, 115.01401017126238}</string>
-				<string>{192.94648863248722, 157.00059484769366}</string>
+				<string>{167.05305440841548, 217.01401017126238}</string>
+				<string>{226.94648863248719, 259.00059484769366}</string>
 			</array>
 			<key>Style</key>
 			<dict>
@@ -455,8 +493,8 @@
 			<integer>47</integer>
 			<key>Points</key>
 			<array>
-				<string>{124.8745931692697, 121.64800481325506}</string>
-				<string>{139.39668124540665, 149.05337113068666}</string>
+				<string>{158.8745931692697, 223.64800481325506}</string>
+				<string>{173.39668124540665, 251.05337113068666}</string>
 			</array>
 			<key>Style</key>
 			<dict>
@@ -496,8 +534,8 @@
 			<integer>46</integer>
 			<key>Points</key>
 			<array>
-				<string>{106.81004419374304, 122.74606327428563}</string>
-				<string>{97.106306747406961, 149.23980099504979}</string>
+				<string>{140.81004419374304, 224.74606327428563}</string>
+				<string>{131.10630674740696, 251.23980099504976}</string>
 			</array>
 			<key>Style</key>
 			<dict>
@@ -524,8 +562,8 @@
 			<integer>45</integer>
 			<key>Points</key>
 			<array>
-				<string>{96.766727155317568, 116.01877245791053}</string>
-				<string>{46.226868755021385, 155.98784298445494}</string>
+				<string>{130.76672715531757, 218.01877245791053}</string>
+				<string>{80.226868755021428, 257.98784298445491}</string>
 			</array>
 			<key>Style</key>
 			<dict>
@@ -542,7 +580,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{189, 148.50700508563119}, {45, 43}}</string>
+			<string>{{223, 250.50700508563119}, {45, 43}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>ID</key>
@@ -572,7 +610,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{128, 148.50700508563119}, {45, 43}}</string>
+			<string>{{162, 250.50700508563119}, {45, 43}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>ID</key>
@@ -623,7 +661,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{67, 148.50700508563119}, {45, 43}}</string>
+			<string>{{101, 250.50700508563119}, {45, 43}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>ID</key>
@@ -653,7 +691,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{6, 148.50700508563119}, {45, 43}}</string>
+			<string>{{40, 250.50700508563119}, {45, 43}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>ID</key>
@@ -693,8 +731,8 @@
 			<integer>37</integer>
 			<key>Points</key>
 			<array>
-				<string>{159.28167672951264, 47.367567191823298}</string>
-				<string>{217.94657602116644, 88.493475973601221}</string>
+				<string>{193.28167672951264, 149.3675671918233}</string>
+				<string>{251.94657602116641, 190.49347597360119}</string>
 			</array>
 			<key>Style</key>
 			<dict>
@@ -726,8 +764,8 @@
 			<integer>36</integer>
 			<key>Points</key>
 			<array>
-				<string>{150.59519702941319, 54.457594388891593}</string>
-				<string>{165.34057841889111, 82.309981457905437}</string>
+				<string>{184.59519702941319, 156.45759438889158}</string>
+				<string>{199.34057841889111, 184.30998145790542}</string>
 			</array>
 			<key>Style</key>
 			<dict>
@@ -759,8 +797,8 @@
 			<integer>35</integer>
 			<key>Points</key>
 			<array>
-				<string>{131.35054684019144, 55.666512594679247}</string>
-				<string>{122.64945315980854, 79.333487405320739}</string>
+				<string>{165.35054684019144, 157.66651259467926}</string>
+				<string>{156.64945315980856, 181.33348740532071}</string>
 			</array>
 			<key>Style</key>
 			<dict>
@@ -805,8 +843,8 @@
 			<integer>34</integer>
 			<key>Points</key>
 			<array>
-				<string>{120.5951873510197, 48.44799139686814}</string>
-				<string>{71.228189182546799, 87.482362041707177}</string>
+				<string>{154.59518735101969, 150.44799139686816}</string>
+				<string>{105.22818918254683, 189.48236204170718}</string>
 			</array>
 			<key>Style</key>
 			<dict>
@@ -828,7 +866,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{214, 80}, {45, 43}}</string>
+			<string>{{248, 182}, {45, 43}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>ID</key>
@@ -858,7 +896,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{153, 80}, {45, 43}}</string>
+			<string>{{187, 182}, {45, 43}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>ID</key>
@@ -898,7 +936,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{92, 80}, {45, 43}}</string>
+			<string>{{126, 182}, {45, 43}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>ID</key>
@@ -944,7 +982,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{31, 80}, {45, 43}}</string>
+			<string>{{65, 182}, {45, 43}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>ID</key>
@@ -974,7 +1012,7 @@
 		</dict>
 		<dict>
 			<key>Bounds</key>
-			<string>{{117, 12}, {45, 43}}</string>
+			<string>{{151, 114}, {45, 43}}</string>
 			<key>Class</key>
 			<string>ShapedGraphic</string>
 			<key>ID</key>
@@ -1067,7 +1105,7 @@
 	<key>MasterSheets</key>
 	<array/>
 	<key>ModificationDate</key>
-	<string>2014-01-15 16:25:55 +0000</string>
+	<string>2014-01-27 09:04:36 +0000</string>
 	<key>Modifier</key>
 	<string>Oshiro Nobuyasu</string>
 	<key>NotesVisible</key>
--- a/paper/graffle/treeoperationlog1.graffle	Mon Jan 27 14:54:34 2014 +0900
+++ b/paper/graffle/treeoperationlog1.graffle	Mon Jan 27 19:53:12 2014 +0900
@@ -46,7 +46,7 @@
 	<key>Creator</key>
 	<string>Oshiro Nobuyasu</string>
 	<key>DisplayScale</key>
-	<string>1 0/72 in = 1 0/72 in</string>
+	<string>1 0/72 in = 1.0000 in</string>
 	<key>GraphDocumentVersion</key>
 	<integer>8</integer>
 	<key>GraphicsList</key>
@@ -135,7 +135,6 @@
 
 \f0\fs24 \cf0 "author" =&gt; "oshiro"\
 "mes" =&gt; "hello"\
-"key" =&gt; "hogs"\
 "timestamp" =&gt; 0}</string>
 			</dict>
 			<key>TextRelativeArea</key>
@@ -153,8 +152,8 @@
 			<integer>102</integer>
 			<key>Points</key>
 			<array>
-				<string>{429.51898193359375, 348.20509865086063}</string>
-				<string>{470.93732646990804, 346.18814124975404}</string>
+				<string>{429.51898193359375, 348.25642635770362}</string>
+				<string>{471.14537279580793, 346.27022187747195}</string>
 			</array>
 			<key>Style</key>
 			<dict>
@@ -371,10 +370,9 @@
 \deftab720
 \pard\pardeftab720
 
-\f0\fs24 \cf0 [PUT_ATTRIBUTE:&lt;-1,1&gt;:key:author,value:oshiro]\'a0\
-[PUT_ATTRIBUTE:&lt;-1,1&gt;:key:mes,value:hello]\
-[PUT_ATTRIBUTE:&lt;-1,1&gt;:key:key,value:hoge]\
-[PUT_ATTRIBUTE:&lt;-1,1&gt;:key:timestamp,value:0] \'a0\
+\f0\fs24 \cf0 [PUT_ATTRIBUTE:&lt;-1,0&gt;:key:author,value:oshiro]\'a0\
+[PUT_ATTRIBUTE:&lt;-1,0&gt;:key:mes,value:hello]\
+[PUT_ATTRIBUTE:&lt;-1,0&gt;:key:timestamp,value:0] \'a0\
 }</string>
 			</dict>
 		</dict>
@@ -417,8 +415,8 @@
 			<integer>93</integer>
 			<key>Points</key>
 			<array>
-				<string>{206.84700655474452, 337}</string>
-				<string>{237.02444604865124, 322.96983599246488}</string>
+				<string>{206.96426294884969, 337.00000000000006}</string>
+				<string>{237.06908365705308, 323.05887097019672}</string>
 			</array>
 			<key>Style</key>
 			<dict>
@@ -689,10 +687,10 @@
 				<key>Text</key>
 				<string>{\rtf1\ansi\ansicpg1252\cocoartf1265
 \cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
-{\colortbl;\red255\green255\blue255;\red0\green0\blue0;}
+{\colortbl;\red255\green255\blue255;}
 \pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
 
-\f0\fs24 \cf2 0}</string>
+\f0\fs24 \cf0 0}</string>
 				<key>VerticalPad</key>
 				<integer>0</integer>
 			</dict>
@@ -745,7 +743,7 @@
 	<key>MasterSheets</key>
 	<array/>
 	<key>ModificationDate</key>
-	<string>2014-01-15 18:23:07 +0000</string>
+	<string>2014-01-27 10:01:07 +0000</string>
 	<key>Modifier</key>
 	<string>Oshiro Nobuyasu</string>
 	<key>NotesVisible</key>
Binary file paper/master_paper.pdf has changed