Papers/2014/nobuyasu-master: paper/chapter3.tex annotate

annotate paper/chapter3.tex @ 39:63eca978482f

Writed description of experiment

author	Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date	Wed, 29 Jan 2014 02:53:18 +0900
parents	559589aec976
children	585196deaace

rev	line source
38 559589aec976 Writed how to use alice topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 34 diff changeset	1 \chapter{Jungle の分散実装}
559589aec976 Writed how to use alice topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 34 diff changeset	2 本章では Jungle に行った分散実装について述べる.
559589aec976 Writed how to use alice topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 34 diff changeset	3 前章では Jungle のアーキテクチャと分散設計について説明した.
559589aec976 Writed how to use alice topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 34 diff changeset	4 トポロジーの形成と他サーバノードのデータのアクセス方法には Alice を使用する.
559589aec976 Writed how to use alice topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 34 diff changeset	5 また, Jungle ではデータ編集のログとして TreeOperationLog がある.
559589aec976 Writed how to use alice topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 34 diff changeset	6 この TreeOperationLog を Alice により他サーバノードへ送ることでデータの分散を行う.
16 e16dad3b80fc Writed topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 15 diff changeset	7
20 a7fbd5db80fb chapter3 Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 19 diff changeset	8 \section{Alice のトポロジーマネージャーの利用}
38 559589aec976 Writed how to use alice topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 34 diff changeset	9
559589aec976 Writed how to use alice topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 34 diff changeset	10 \subsection{トポロジーマネージャーの起動}
559589aec976 Writed how to use alice topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 34 diff changeset	11 Alice を用いてサーバノードでトポロジーの形成を行う方法を述べる.
559589aec976 Writed how to use alice topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 34 diff changeset	12 Alice のトポロジーマネージャーの起動は\ref{src:alice_dot}の様に行う.
20 a7fbd5db80fb chapter3 Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 19 diff changeset	13 (\ref{src:alice_ntm_run}).
a7fbd5db80fb chapter3 Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 19 diff changeset	14 \begin{lstlisting}[frame=lrbt,label=src:alice_ntm_run,caption=Alice によるネットワークトポロジーマネージャーの起動,numbers=left]
a7fbd5db80fb chapter3 Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 19 diff changeset	15 % java -cp Alice.jar alice.topology.manager.TopologyManager -p 10000 -conf ./topology/tree5.dot
a7fbd5db80fb chapter3 Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 19 diff changeset	16 \end{lstlisting}
38 559589aec976 Writed how to use alice topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 34 diff changeset	17 -p オプションはトポロジーマネージャーが開くポートの番号, -conf オプションには dot ファイルのパスを渡す.
20 a7fbd5db80fb chapter3 Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 19 diff changeset	18
a7fbd5db80fb chapter3 Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 19 diff changeset	19 ポート番号は Alice により記述された並列分散プログラムの起動時に渡す必要がある.
a7fbd5db80fb chapter3 Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 19 diff changeset	20 dot ファイルには, トポロジーをどのように形成するかが書かれている.
a7fbd5db80fb chapter3 Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 19 diff changeset	21 以下に, サーバノード数5で, 2分木ツリー構造を形成する dot ファイルの例を示す(\ref{src:alice_dot}).
18 fc14b1876141 Modified description of topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 17 diff changeset	22 \begin{lstlisting}[frame=lrbt,label=src:alice_dot,caption=ネットワークトポロジー設定用 dot ファイル,numbers=left]
fc14b1876141 Modified description of topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 17 diff changeset	23 % cat tree5.dot
16 e16dad3b80fc Writed topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 15 diff changeset	24 digraph test {
e16dad3b80fc Writed topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 15 diff changeset	25 node0 -> node1 [label="child1"]
e16dad3b80fc Writed topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 15 diff changeset	26 node0 -> node2 [label="child2"]
e16dad3b80fc Writed topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 15 diff changeset	27 node1 -> node0 [label="parent"]
e16dad3b80fc Writed topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 15 diff changeset	28 node1 -> node3 [label="child1"]
e16dad3b80fc Writed topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 15 diff changeset	29 node1 -> node4 [label="child2"]
e16dad3b80fc Writed topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 15 diff changeset	30 node2 -> node0 [label="parent"]
e16dad3b80fc Writed topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 15 diff changeset	31 node3 -> node1 [label="parent"]
e16dad3b80fc Writed topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 15 diff changeset	32 node4 -> node1 [label="parent"]
e16dad3b80fc Writed topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 15 diff changeset	33 }
18 fc14b1876141 Modified description of topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 17 diff changeset	34 \end{lstlisting}
fc14b1876141 Modified description of topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 17 diff changeset	35
20 a7fbd5db80fb chapter3 Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 19 diff changeset	36 node0 や node1 はサーバノードの名前を示す.
a7fbd5db80fb chapter3 Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 19 diff changeset	37 サーバノードの間にはラベルがあり, Alice 上ではこのラベル
a7fbd5db80fb chapter3 Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 19 diff changeset	38 に指定される文字列(キー)を使うことで他のサーバノードのデータへアクセスすることができる.
a7fbd5db80fb chapter3 Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 19 diff changeset	39 node0 -> node1 はサーバノード同士の繋がりを示している.
a7fbd5db80fb chapter3 Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 19 diff changeset	40 次に続く label="child1" は, node0 が node1 のデータに"child1"という文字列を使うことでアクセス
a7fbd5db80fb chapter3 Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 19 diff changeset	41 できることを示す.
18 fc14b1876141 Modified description of topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 17 diff changeset	42
21 a4dfb70496ee Added figure Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	43 dot ファイルを読み込んだ Alice のトポロジーマネージャーに対して, サーバノードは
20 a7fbd5db80fb chapter3 Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 19 diff changeset	44 誰に接続を行えばよいかを訪ねる.
a7fbd5db80fb chapter3 Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 19 diff changeset	45 トポロジーマネージャーは訪ねてきたサーバノードに対してノード番号を割り振り, dot ファイル
a7fbd5db80fb chapter3 Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 19 diff changeset	46 に記述している通りにサーバノード同士が接続を行うよう指示をだす.
18 fc14b1876141 Modified description of topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 17 diff changeset	47
20 a7fbd5db80fb chapter3 Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 19 diff changeset	48 トポロジーマネージャーは接続要求先を聞いてくるサーバノードに対して名前を割り振り, 接続相手を伝える.
a7fbd5db80fb chapter3 Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 19 diff changeset	49 dot ファイル\ref{src:alice_dot}により形成されるトポロジーを図\ref{fig:tree_topology}に示す.
16 e16dad3b80fc Writed topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 15 diff changeset	50
e16dad3b80fc Writed topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 15 diff changeset	51
e16dad3b80fc Writed topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 15 diff changeset	52 \begin{figure}[htpb]
e16dad3b80fc Writed topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 15 diff changeset	53 \begin{center}
e16dad3b80fc Writed topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 15 diff changeset	54 \includegraphics[scale=0.70]{figures/tree_topology.pdf}
e16dad3b80fc Writed topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 15 diff changeset	55 \caption{Alice によるネットワークトポロジー形成}
e16dad3b80fc Writed topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 15 diff changeset	56 \label{fig:tree_topology}
e16dad3b80fc Writed topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 15 diff changeset	57 \end{center}
e16dad3b80fc Writed topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 15 diff changeset	58 \end{figure}
e16dad3b80fc Writed topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 15 diff changeset	59
17 dfa2fd4658b2 Modified abstract Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 16 diff changeset	60 矢印に書かれている文字列は, 相手のデータにアクセスするキーを示す.
dfa2fd4658b2 Modified abstract Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 16 diff changeset	61 "child1", "child2", "parent" というキーを使うことで別のサーバノードにあるデータを取得することができる.
dfa2fd4658b2 Modified abstract Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 16 diff changeset	62 %子共となるノードは "parent" キーにより親の DSM (Remote DSM) にアクセスすることができる.
dfa2fd4658b2 Modified abstract Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 16 diff changeset	63 %また, 親も子供となるノードの DSM に対して "child1" や "child2" キーによりアクセスすることが可能となる.
38 559589aec976 Writed how to use alice topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 34 diff changeset	64 これでトポロジーマネージャーが起動される.
16 e16dad3b80fc Writed topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 15 diff changeset	65
38 559589aec976 Writed how to use alice topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 34 diff changeset	66 \subsection{アプリケーション側の記述}
559589aec976 Writed how to use alice topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 34 diff changeset	67 次は Jungle 側のプログラムが最初に Alice のトポロジーノードと通信を行うようにする.
559589aec976 Writed how to use alice topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 34 diff changeset	68 そのためには Alice の TopologyNode クラスに必要な情報を渡してインスタンスを生成する(\ref{src:app_start}).
559589aec976 Writed how to use alice topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 34 diff changeset	69 \begin{lstlisting}[frame=lrbt,label=src:app_start,caption=アプリケーションの起動,numbers=left]
20 a7fbd5db80fb chapter3 Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 19 diff changeset	70 public static void main( String[] args ) throws Exception
a7fbd5db80fb chapter3 Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 19 diff changeset	71 {
a7fbd5db80fb chapter3 Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 19 diff changeset	72 RemoteConfig conf = new RemoteConfig(args);
38 559589aec976 Writed how to use alice topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 34 diff changeset	73 new TopologyNode(conf, new StartJungleCodeSegment(args, conf.bbsPort));
20 a7fbd5db80fb chapter3 Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 19 diff changeset	74 }
a7fbd5db80fb chapter3 Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 19 diff changeset	75 \end{lstlisting}
38 559589aec976 Writed how to use alice topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 34 diff changeset	76 TopologyNode クラスは第2引数として CodeSegment を受け取る.
559589aec976 Writed how to use alice topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 34 diff changeset	77 TopologyNode のインスタンスはまず初めにトポロジーマネージャーへ接続を行う.
559589aec976 Writed how to use alice topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 34 diff changeset	78 次にトポロジーマネージャーから受け取った情報を元に別のサーバノードとトポロジーの形成を行う.
559589aec976 Writed how to use alice topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 34 diff changeset	79 その後, 第2引数で渡された StartJungleCodeSegment の実行を行う.
559589aec976 Writed how to use alice topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 34 diff changeset	80 StartJungleCodeSegment には通常のアプリケーションの処理が書かれる.
20 a7fbd5db80fb chapter3 Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 19 diff changeset	81
38 559589aec976 Writed how to use alice topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 34 diff changeset	82 アプリケーションの起動時にはコンフィグの情報として, トポロジーマネージャーが動いているサーバのドメインとポート番号を
559589aec976 Writed how to use alice topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 34 diff changeset	83 渡す必要がある.
21 a4dfb70496ee Added figure Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	84 例えば, mass00.cs.ie.u-ryukyu.ac.jp というサーバ上でポート番号10000を指定してトポロジーマネージャーを
a4dfb70496ee Added figure Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	85 起動した場合は次のようになる(\ref{src:run_program}).
a4dfb70496ee Added figure Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	86 \begin{lstlisting}[frame=lrbt,label=src:run_program,caption=トポロジーマネージャーの利用,numbers=left]
a4dfb70496ee Added figure Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	87 % java Program -host mass00.cs.ie.u-ryukyu.ac.jp -port 10000
a4dfb70496ee Added figure Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	88 \end{lstlisting}
17 dfa2fd4658b2 Modified abstract Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 16 diff changeset	89
39 63eca978482f Writed description of experiment Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 38 diff changeset	90 \section{Alice を用いての分散実装}
21 a4dfb70496ee Added figure Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	91 形成されたトポロジー上でのデータの送受信を行う部分について述べる.
10 02c7fc1cda10 Writed description of TreeOperationLog Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 4 diff changeset	92
11 b87deec129df Added images Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 10 diff changeset	93
25 67880a2ca650 Modfied chapter1.tex Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 24 diff changeset	94
67880a2ca650 Modfied chapter1.tex Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 24 diff changeset	95
4 d42d2acf5d1d Added some tex files Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: diff changeset	96 \section{ログのシリアライズ}
21 a4dfb70496ee Added figure Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	97 ここでログのシリアライズについて述べる.
17 dfa2fd4658b2 Modified abstract Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 16 diff changeset	98
16 e16dad3b80fc Writed topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 15 diff changeset	99 シリアライズとは, データをネットワーク上に流しても良い形式に変換することである.
e16dad3b80fc Writed topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 15 diff changeset	100
e16dad3b80fc Writed topology manager Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 15 diff changeset	101
21 a4dfb70496ee Added figure Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	102
a4dfb70496ee Added figure Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	103
22 56753cfbeeab Added merge_imp.pdf Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 21 diff changeset	104 \section{掲示板プログラムにおけるマージの実装}
56753cfbeeab Added merge_imp.pdf Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 21 diff changeset	105 Jungle に分散実装を行った後の問題としてデータ衝突がある.
56753cfbeeab Added merge_imp.pdf Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 21 diff changeset	106 他のサーバノードから送られてくるデータが既に手元で変更を加えた木構造を対象とした
56753cfbeeab Added merge_imp.pdf Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 21 diff changeset	107 場合に発生する問題である.
56753cfbeeab Added merge_imp.pdf Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 21 diff changeset	108 Jungle ではこれをアプリケーション毎にマージを実装することで解決させる.
21 a4dfb70496ee Added figure Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	109
22 56753cfbeeab Added merge_imp.pdf Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 21 diff changeset	110 今回分散実装を行い, 例題として掲示板プログラムを用意した.
56753cfbeeab Added merge_imp.pdf Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 21 diff changeset	111 掲示板プログラムに実装を行ったマージについて述べる.
56753cfbeeab Added merge_imp.pdf Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 21 diff changeset	112 まず Jungle を用いた掲示板プログラムのデータ保持方法を図\ref{fig:merge2}に示す.
21 a4dfb70496ee Added figure Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	113 \begin{figure}[htpb]
a4dfb70496ee Added figure Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	114 \begin{center}
22 56753cfbeeab Added merge_imp.pdf Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 21 diff changeset	115 \includegraphics[scale=0.70]{figures/merge2.pdf}
21 a4dfb70496ee Added figure Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	116 \caption{Jungle による掲示板プログラムのデータ保持方法}
22 56753cfbeeab Added merge_imp.pdf Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 21 diff changeset	117 \label{fig:merge2}
21 a4dfb70496ee Added figure Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	118 \end{center}
a4dfb70496ee Added figure Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	119 \end{figure}
a4dfb70496ee Added figure Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	120
a4dfb70496ee Added figure Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	121 掲示板プログラムでは各掲示板毎に1つの木構造が作成される.
22 56753cfbeeab Added merge_imp.pdf Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 21 diff changeset	122 掲示板への1つの書き込みは子ノードを1つ追加することに相当する.
56753cfbeeab Added merge_imp.pdf Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 21 diff changeset	123 また, 各子ノードは attributes として書き込みの内容である message と書き込まれた時間を表す timestamp を保持している.
56753cfbeeab Added merge_imp.pdf Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 21 diff changeset	124 先に追加された順で子ノードには若い番号が割り振られる.
56753cfbeeab Added merge_imp.pdf Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 21 diff changeset	125
23 21e1a110f258 Writed description of merge Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 22 diff changeset	126 他サーバノードからの書き込みをそのまま子ノードの後ろに追加してしまうと, データの整合性が崩れてしまう.
22 56753cfbeeab Added merge_imp.pdf Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 21 diff changeset	127 この時の状態を表しているのが図\ref{fig:merge_imp1}と\ref{fig:merge_imp2}になる.
56753cfbeeab Added merge_imp.pdf Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 21 diff changeset	128 \begin{figure}[htpb]
56753cfbeeab Added merge_imp.pdf Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 21 diff changeset	129 \begin{center}
56753cfbeeab Added merge_imp.pdf Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 21 diff changeset	130 \includegraphics[scale=0.70]{figures/merge_imp1.pdf}
23 21e1a110f258 Writed description of merge Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 22 diff changeset	131 \caption{他サーバノードの編集データ反映による整合性の崩れ1}
22 56753cfbeeab Added merge_imp.pdf Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 21 diff changeset	132 \label{fig:merge_imp1}
56753cfbeeab Added merge_imp.pdf Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 21 diff changeset	133 \end{center}
56753cfbeeab Added merge_imp.pdf Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 21 diff changeset	134 \end{figure}
56753cfbeeab Added merge_imp.pdf Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 21 diff changeset	135
56753cfbeeab Added merge_imp.pdf Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 21 diff changeset	136 \begin{figure}[htpb]
56753cfbeeab Added merge_imp.pdf Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 21 diff changeset	137 \begin{center}
56753cfbeeab Added merge_imp.pdf Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 21 diff changeset	138 \includegraphics[scale=0.70]{figures/merge_imp2.pdf}
23 21e1a110f258 Writed description of merge Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 22 diff changeset	139 \caption{他サーバノードの編集データ反映による整合性の崩れ2}
22 56753cfbeeab Added merge_imp.pdf Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 21 diff changeset	140 \label{fig:merge_imp2}
56753cfbeeab Added merge_imp.pdf Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 21 diff changeset	141 \end{center}
56753cfbeeab Added merge_imp.pdf Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 21 diff changeset	142 \end{figure}
21 a4dfb70496ee Added figure Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	143
23 21e1a110f258 Writed description of merge Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 22 diff changeset	144 \newpage
21e1a110f258 Writed description of merge Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 22 diff changeset	145
21e1a110f258 Writed description of merge Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 22 diff changeset	146 図\ref{fig:merge_imp2}の server node0 の木の状態にするのが理想である.
21e1a110f258 Writed description of merge Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 22 diff changeset	147 掲示板のへの書き込みの表示は, 書き込みされた時間が早い順に表示されるようにしたい.
21e1a110f258 Writed description of merge Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 22 diff changeset	148 これを timestamp を利用することで行う.
21e1a110f258 Writed description of merge Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 22 diff changeset	149 他サーバノードから来たデータに関しては, timestamp を参照し, 次に自分の保持している
21e1a110f258 Writed description of merge Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 22 diff changeset	150 木の子ノードの timestamp と比べていくことでデータの追加する場所を決める.
21e1a110f258 Writed description of merge Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 22 diff changeset	151 これが今回実装を行った掲示板システムにおけるマージになる.
21e1a110f258 Writed description of merge Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 22 diff changeset	152
21e1a110f258 Writed description of merge Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 22 diff changeset	153 %単一サーバで動いている時の Jungle はただ子ノードとして後ろに追加するだけだが, 分散
21e1a110f258 Writed description of merge Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 22 diff changeset	154 %環境下においては timestamp に従い子ノードを追加する位置を決めるようにする.
21 a4dfb70496ee Added figure Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	155
a4dfb70496ee Added figure Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 20 diff changeset	156
22 56753cfbeeab Added merge_imp.pdf Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 21 diff changeset	157
56753cfbeeab Added merge_imp.pdf Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> parents: 21 diff changeset	158

Mercurial > hg > Papers > 2014 > nobuyasu-master

annotate paper/chapter3.tex @ 39:63eca978482f