Mercurial > hg > Papers > 2013 > nobuyasu-jssst

annotate Paper/jssst.tex @ 29:aec0e1852d85

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
wrote environment
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Fri, 19 Jul 2013 01:52:35 +0900
parents 62114661471d
children 201e1acfdd40
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 % Sample file for the use of compsoft style file.
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
2 %
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 \documentclass[T]{compsoft}
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
4
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
5 % Preamble
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 %
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 % 「コンピュータソフトウェア」誌に掲載される論文の場合，次で
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 % 巻数，号数，開始ページ，終了ページを指定する．
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
9 %\volNoPp{16}{5}{78}{83}
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
10
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
11 % ワークショップによる推薦論文の場合，ワークショップ名を指定する．
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 % \suisen{ワークショップ名}
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
13
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 % 特集の場合，特集のタイトルを与える．
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
15 % \tokushu{特集のタイトル}
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
16
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 % 大会論文の場合，\taikai で開催年を指定する．ここで指定した年から
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 % 大会の回数は計算される．
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
19 \taikai{2013}
24
4e7979f6b571 added bib file
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
20 \pagestyle {empty}
0
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
21
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
22 % ここに，使用するパッケージを列挙する．
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
23 \usepackage[dvipdfmx]{graphicx}
3
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
24 \usepackage{listings,jlisting}
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
25 \usepackage{url}
0
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
26
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
27 % ユーザが定義したマクロなどはここに置く．ただし学会誌のスタイルの
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
28 % 再定義は原則として避けること．
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
29
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
30 \begin{document}
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
31
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
32 % 論文のタイトル
2
fddcd3a2c40a writed intruduction
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
33 \title{Data Segment の分散データベースへの応用}
0
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
34
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
35 % 著者
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
36 % 和文論文の場合，姓と名の間には半角スペースを入れ，
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 % 複数の著者の間は全角スペースで区切る
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
38 %
20
04e41820d930 modified description for DefaultTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
39 \author{大城 信康 \and 杉本 優 \and 河野 真治
0
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
40 %
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
41 % ここにタイトル英訳 (英文の場合は和訳) を書く．
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
42 %
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
43 \ejtitle{}
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
44 %
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
45 % ここに著者英文表記 (英文の場合は和文表記) および
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
46 % 所属 (和文および英文) を書く．
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
47 % 複数著者の所属はまとめてよい．
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
48 %
20
04e41820d930 modified description for DefaultTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
49 \shozoku{Nobuyasu OSHIRO,Yu SUGIMOTO, Shinij KONO }{琉球大学大学院理工学研究科情報工学専攻並列信頼研}%
0
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
50 {Dept.Concurrency Reliance Laboratory, Information Engineering Course, Faculty of Engineering Graduate School of Engineering and Science, University of the Ryukyus}
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
51 %
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
52 % 出典情報は \shutten とすれば出力される．
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
53 %\shutten
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
54 %
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
55 % 受付年月日，記事カテゴリなどは自動的に生成される．
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
56 %\uketsuke{1999}{8}{3}
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
57 %
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
58 % その他，脚注に入れるものがあれば，\note に記述する．
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
59 %\note{脚注に入れる内容}
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
60 }
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
61
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
62 %
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
63 % 和文アブストラクト
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
64 \Jabstract{%
28
62114661471d wrote request data
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
65 当研究室では並列・分散プログラミングスタイルとして Data Segment, Code Segment によるプログラミング手法を提案している.
2
fddcd3a2c40a writed intruduction
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
66 Data Segment のJava上の実装としてAliceを作成してきた。
0
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
67 非破壊的木構造データベースjungleの分散実装を行う際にノード間での通信が必要になる。
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
68 Aliceを用いてデータベースノード間の通信を行う利点と欠点について考察する。
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
69 }
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
70
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
71 %
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
72 % 英文アブストラクト（大会論文には必要なし)
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
73 % \Eabstract{}
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
74 %
24
4e7979f6b571 added bib file
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
75 \maketitle \thispagestyle {empty}
0
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
76
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
77 \section{はじめに}
3
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
78 当研究室では並列・分散プログラムに向いたプログラミングを目指し, データを Data Segment, タスクを Code Segment という単位で扱うプログラミングスタイルの
1
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
79 提案を行なっている.
3
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
80 Data Segment, Code Segment によるプログラミングを提供する実装として, Java による分散ネットワークフレームワーク
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
81 Alice を開発している.
2
fddcd3a2c40a writed intruduction
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
82 Alice はノード間のトポロジー生成を提供しており, Data Segment としてデータの送受信をノード間で行うことができる.
fddcd3a2c40a writed intruduction
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
83
3
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
84 また, 当研究室では非破壊的木構造を用いたデータベースである Jungle の開発も行なっている.
2
fddcd3a2c40a writed intruduction
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
85 Jungle はデータを非破壊で保持することでスケーラビリティのあるデータベースを目指している.
fddcd3a2c40a writed intruduction
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
86 Jungle はデータの編集を TreeOperationLog という単位で行う.
3
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
87 Alice を使いこの TreeOperationLog を各ノード間で送受信することでデータの分散を行うことができる.
2
fddcd3a2c40a writed intruduction
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
88
fddcd3a2c40a writed intruduction
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
89 本研究では, Alice と Jungle を用いて分散データベースの実装を行う.
fddcd3a2c40a writed intruduction
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 1
diff changeset
90 さらに, 例題のアプリケーションとして掲示板を作成し, 評価を行う.
0
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
91
3
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
92 \section{分散ネットワークフレームワーク Alice}
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
93 Alice は当研究室で開発している分散管理フレームワークである.
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
94 Data Segment とCode Segment による並列・分散プログラミングを提供する.
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
95
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
96 まず, Data Segment と Code Segment についての説明を行う.
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
97
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
98 \subsection{Data Segment}
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
99 Data Segment は計算に必要なデータになる.
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
100 Alice は Data Segment を文字列の Key で管理する.
9
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
101 Key 毎にリストが用意され, put された順番で Data Segment は取り出され計算が行われる.
3
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
102 Data Segment は Data Segment Manager(以下DSM) により管理される.
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
103 DSM はノード毎にキーを持つ.
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
104 他のノードの DSM にアクセスする場合は Remote DSM 経由で行う.
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
105 Alice による分散プログラミングはこの Remote DSM の機能を使用する.
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
106
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
107 Data Segment Manager は API を提供しており, この API を通じて Data Segment のやりとりが行われる
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
108 具体的には以下の API が用意されている.
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
109 \begin{itemize}
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
110 \item \verb+void put(String key, Value val)+
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
111 \item \verb+void update(String key, Value val)+
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
112 \item \verb+void peek(Receiver receiver, String key)+
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
113 \item \verb+void take(Receiver receiver, String key)+
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
114 \end{itemize}
9
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
115 put は Data Segment をリストへと追加する API である.
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
116 update はリストに入っている Data Segment を更新する API である.
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
117 peek はリストに入っている Data Segment を取り出す API である.
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
118 peek により取り出された Data Segement はリストより削除されない.
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
119 take はリストに入っている Data Segment を取り出す API である.
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
120 取り出した Data Segment はリストより削除される.
3
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
121
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
122
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
123 \subsection{Code Segment}
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
124 Code Segment は Data Segment を受け取り計算を行うコードのことを示す.
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
125 並列プログラミングにおけるタスクにあたる.
23
335cbec61221 added figure
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
126 Code Segment と Data Segment は対になっている.
3
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
127 Code Segment は計算に使う Data Segment のキーを登録して, そのキー
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
128 にあたる Data Segment が用意され次第処理が実行される.
7
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
129 Code Segment が処理を開始するのに必要な Data Segment を Input Data Segment という.
3
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
130
9
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
131 Code Segment では Data Segment の生成を行い, put や update により新たにリストに登録することができる.
7
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
132 Code Segment 内で作成し登録される Data Segment は Output Data Segment と呼ばれる.
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
133
24
4e7979f6b571 added bib file
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
134 Code Segment は Input Data Segment と Output Data Segment の API を提供する(図\ref{fig:dsnadcs}).
23
335cbec61221 added figure
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
135 \begin{figure}[htpb]
335cbec61221 added figure
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
136 \begin{center}
335cbec61221 added figure
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
137 \includegraphics[scale=0.50]{figures/dsandcs.pdf}
335cbec61221 added figure
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
138 \caption{Data Segment と Code Segment}
335cbec61221 added figure
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
139 \label{fig:dsnadcs}
335cbec61221 added figure
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
140 \end{center}
335cbec61221 added figure
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
141 \end{figure}
335cbec61221 added figure
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
142
4
f3a5eb2c9081 added graffle directory
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 3
diff changeset
143
3
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
144
7
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 4
diff changeset
145 \subsection{MessagePack}
9
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
146 Alice における Data Segment のデータ表現には MessagePack を利用している.
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
147 MessagePack はバイナリをベースにしたシリアライズライブラリーである.
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
148 また, MessagePack のバイナリにシリアライズできる型のみで構成された Value オブジェクト
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
149 が用意されている.
24
4e7979f6b571 added bib file
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
150 MessagePack は Java の基本的な型はシリアライズすることができる.
9
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
151
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
152 Value オブジェクトは自己記述なデータ形式になっている.
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
153 独自のクラスでも @Message アノテーションを付けることで Value 型
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
154 へと変換することができる.
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
155 その時は MessagePack がシリアライズできる型のみをフィールドに入れなければならない.
3
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
156
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
157
9
6212a32c4196 writed MessagePack
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 7
diff changeset
158 \section{非破壊的木構造を用いたデータベース Jungle}
12
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
159 Jungle はスケーラビリティのある CMS の開発を目指して当研究室で開発されている非破壊的木構造データベースである.
10
e4c13f70c552 start write chapter 3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
160 一般的なコンテンツマネジメントシステムではブログツールや Wiki・SNS が多く, これらの
12
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
161 ウェブサイトの構造は大体が木構造であるため, データ構造として木構造を採用している.
1
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
162
14
906c76445554 remove test file
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 13
diff changeset
163 ここではまず破壊的木構造と, 非破壊的木構造の説明をし, Jungle におけるデータ編集の実装について述べる.
10
e4c13f70c552 start write chapter 3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
164
e4c13f70c552 start write chapter 3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
165 \subsection{破壊的木構造}
11
522931416348 added destructive_tree.graffle
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
166 破壊的木構造の編集は, 木構造で保持しているデータを直接書き換えることで行う.
13
f7ace466a7f0 wrote description for non destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
167 図\ref{fig:destractive}は破壊的木構造の編集を表している.
11
522931416348 added destructive_tree.graffle
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
168
522931416348 added destructive_tree.graffle
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
169 \begin{figure}[htpb]
522931416348 added destructive_tree.graffle
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
170 \begin{center}
522931416348 added destructive_tree.graffle
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
171 \includegraphics[scale=0.50]{figures/destructive_tree.pdf}
12
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
172 \caption{破壊的木構造の編集}
11
522931416348 added destructive_tree.graffle
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
173 \label{fig:destractive}
522931416348 added destructive_tree.graffle
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
174 \end{center}
522931416348 added destructive_tree.graffle
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
175 \end{figure}
522931416348 added destructive_tree.graffle
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
176
12
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
177 破壊的木構造は, 編集を行う際に木のロックを掛ける必要がある.
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
178 データを受け取ろうと木を走査するスレッドは書き換えの終了を待つ必要があり, 閲覧者が
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
179 いる場合は木の走査が終わるまで書き換えをまたなければならない.
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
180 これではスケールしないと考えられる.
11
522931416348 added destructive_tree.graffle
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 10
diff changeset
181
12
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
182 \subsection{非破壊的木構造木構造}
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
183 非破壊的木構造は破壊的木構造とは違い一度作成したデータを破壊することはない.
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
184 非破壊的木構造においてデータの編集を行う場合は, root から編集のあったノードまでコピー
15
ac82fd7e1ea1 added makegraph.sh
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 14
diff changeset
185 を行い新しく木構造を作成することで行う.
12
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
186 編集が行われない部分は参照をもたせる.
13
f7ace466a7f0 wrote description for non destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
187 図\ref{fig:nondestractive}は非破壊的木構造の編集を表している.
12
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
188
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
189 \begin{figure}[htpb]
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
190 \begin{center}
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
191 \includegraphics[scale=0.50]{figures/non_destructive_tree.pdf}
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
192 \caption{非破壊的木構造の編集}
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
193 \label{fig:nondestractive}
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
194 \end{center}
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
195 \end{figure}
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
196
13
f7ace466a7f0 wrote description for non destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
197 非破壊的木構造により, 木構造を編集しながら走査することが可能となる.
f7ace466a7f0 wrote description for non destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 12
diff changeset
198
16
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
199
15
ac82fd7e1ea1 added makegraph.sh
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 14
diff changeset
200 \subsection{Jungle におけるデータ編集}
16
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
201 木の編集は, 通常 Node を書き換えるため Node の API として提供されることが多いが, Jungle で
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
202 は JungleTreeEditor を利用して行う.
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
203 JungleTree Editor には編集するためのいくつかのメソッドが用意されており, NodePath と
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
204 呼ばれるルートノードからノードまでのマスを指定することでノードが編集される.
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
205 NodePath は, ルートノードからスタートし, ノードの子供の場所を次々に指定していくことで編集対象
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
206 のノードの場所を表す(図\ref{fig:nodepath}).
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
207
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
208 \begin{figure}[htpb]
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
209 \begin{center}
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
210 \includegraphics[scale=0.50]{figures/nodepath.pdf}
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
211 \caption{NodePath}
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
212 \label{fig:nodepath}
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
213 \end{center}
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
214 \end{figure}
12
fcfd5857d435 wrote description for destructive tree
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 11
diff changeset
215
16
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
216 Tree 編集の API として次の4つが用意されている.
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
217 \begin{itemize}
18
b3bce5bacc04 wrote DefatltTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 17
diff changeset
218 \item \verb+addNewChildAt(NodePath _path,int _pos)+
b3bce5bacc04 wrote DefatltTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 17
diff changeset
219 \item \verb+deleteChildAt(NodePath _path,int _pos)+
16
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
220 \item \verb+putAttribute(NodePath _path,+\\
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
221 \verb+String _key,ByteBuffer _value)+
18
b3bce5bacc04 wrote DefatltTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 17
diff changeset
222 \item \verb+deleteAttribute(NodePath _path,+\\
b3bce5bacc04 wrote DefatltTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 17
diff changeset
223 \verb+String _key)+
16
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
224 \end{itemize}
10
e4c13f70c552 start write chapter 3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
225
16
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
226 \subsubsection{addNewChildAt}
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
227 NodePath で指定された Node に子供となる Node を追加するAPIである.
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
228 pos で指定された番号に子供として追加を行う.
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
229
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
230 \subsubsection{deleteChildAt}
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
231 NodePath と pos により指定される Node を削除する API である.
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
232
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
233 \subsubsection{putAttribute}
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
234 Node に attribute を追加する API である.
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
235 文字列をキーにして ByteBuffer によりデータを保持する.
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
236
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
237 \subsubsection{deleteAttribute}
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
238 NodePath により指定される Node の attribute を削除する API である.
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
239 削除する attribute は文字列のキーで指定する.
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
240
f5028ec67c38 wrote description for editor api
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 15
diff changeset
241 \subsection{TreeOperationLog}
18
b3bce5bacc04 wrote DefatltTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 17
diff changeset
242 上記の API を使用すると Editor 内部では NodeOperation として順次つまれていき, 最終
17
2132391fcb65 wrote TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
243 的に commit されることで編集が行われる.
18
b3bce5bacc04 wrote DefatltTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 17
diff changeset
244 複数の NodeOperation の集まりを TreeOperationLog といい, これが編集の単位となる.
17
2132391fcb65 wrote TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
245 例えば, 後述する掲示板の実装では1つの書き込みに対して1つの Node を作成し, attribute を
2132391fcb65 wrote TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
246 もたせている.
2132391fcb65 wrote TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
247 その時のログは次のようになる.
24
4e7979f6b571 added bib file
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
248
17
2132391fcb65 wrote TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
249 \begin{verbatim}
2132391fcb65 wrote TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
250 [APPEND_CHILD:<-1>:pos:1]
2132391fcb65 wrote TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
251 [PUT_ATTRIBUTE:<-1,1>:key:author,value:oshiro]
2132391fcb65 wrote TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
252 [PUT_ATTRIBUTE:<-1,1>:key:mes,value:hello]
2132391fcb65 wrote TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
253 [PUT_ATTRIBUTE:<-1,1>:key:key,value:hoge]
2132391fcb65 wrote TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
254 [PUT_ATTRIBUTE:<-1,1>:key:timestamp,value:0]
2132391fcb65 wrote TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
255 \end{verbatim}
24
4e7979f6b571 added bib file
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
256
18
b3bce5bacc04 wrote DefatltTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 17
diff changeset
257 大文字の英字は実行した API を表す.
17
2132391fcb65 wrote TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
258 <>により囲まれている数値は NodePath を示す.
18
b3bce5bacc04 wrote DefatltTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 17
diff changeset
259 NodePath の後ろは posision や attribute の情報を表している.
b3bce5bacc04 wrote DefatltTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 17
diff changeset
260 NodeOperation と NodePath の組み合わせを TreeOperation として扱い, それらいくつか集まりが TreeOperationLog となる.
17
2132391fcb65 wrote TreeOperationLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 16
diff changeset
261
18
b3bce5bacc04 wrote DefatltTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 17
diff changeset
262 \section{Alice を用いた Jungle の分散実装}
b3bce5bacc04 wrote DefatltTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 17
diff changeset
263 Alice を用いた Jungle のデータ分散は, 上記の TreeOperationLog を Data Segment として扱うことで行える.
b3bce5bacc04 wrote DefatltTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 17
diff changeset
264 そのために必要なことは以下となる.
b3bce5bacc04 wrote DefatltTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 17
diff changeset
265 \begin{itemize}
b3bce5bacc04 wrote DefatltTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 17
diff changeset
266 \item TreeOperationLog を MessagePack によりシリアライズ
b3bce5bacc04 wrote DefatltTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 17
diff changeset
267 \item TreeOperationLog を扱う Data Segment の作成
19
4afecc3d3331 added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 18
diff changeset
268 %\item Data Segment として受け取った TreeOperationLog の Jungle への適応
18
b3bce5bacc04 wrote DefatltTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 17
diff changeset
269 \end{itemize}
10
e4c13f70c552 start write chapter 3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
270
e4c13f70c552 start write chapter 3
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 9
diff changeset
271
18
b3bce5bacc04 wrote DefatltTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 17
diff changeset
272 \subsection{TreeOperationLog の MessagePack によるシリアライズ}
20
04e41820d930 modified description for DefaultTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
273 TreeOperationLog はそのまま MessagePack でシリアライズすることはできない.
04e41820d930 modified description for DefaultTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
274 TreeOperationLog は TreeOperation をフィールドに List として保持していた.
04e41820d930 modified description for DefaultTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
275 フィールドとして保持しているものは全て MessagePack でシリアライズできるものに
04e41820d930 modified description for DefaultTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
276 しなけれならない.
04e41820d930 modified description for DefaultTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
277 そこで, フィールドで保持しているもの Value 型に変換するための Container クラス
04e41820d930 modified description for DefaultTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
278 作成をそれぞれ行った.
04e41820d930 modified description for DefaultTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
279 ログに関連するクラス全てをシリアライズするクラスを行った後に, それら全てをまとめる
04e41820d930 modified description for DefaultTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
280 DefaultTreeOperationLogContainer クラスの作成を行った.
04e41820d930 modified description for DefaultTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
281 このクラスは TreeOperationLog を Value 型へと変換しフィールド変数で保持する.
04e41820d930 modified description for DefaultTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
282 実際に TreeOperationLog のシリアライズを行うソースを次に示す.
0
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
283
24
4e7979f6b571 added bib file
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
284 %\begin{lstlisting}[label=unconvert, caption=TreeOperationLog のシリアライズ]
4e7979f6b571 added bib file
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
285 \begin{verbatim}
20
04e41820d930 modified description for DefaultTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
286 public void unconvert(Iterable
21
9dcb40e74ab9 added some figres
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
287 <TreeOperation> _log) throws IOExceptio{
20
04e41820d930 modified description for DefaultTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
288 MessagePack msgpack = new MessagePack();
21
9dcb40e74ab9 added some figres
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
289 List<Value> list
9dcb40e74ab9 added some figres
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
290 = new LinkedList<Value>();
20
04e41820d930 modified description for DefaultTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
291 for(TreeOperation op : _log) {
21
9dcb40e74ab9 added some figres
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
292 NodeOperation nOp
9dcb40e74ab9 added some figres
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
293 = op.getNodeOperation();
9dcb40e74ab9 added some figres
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
294 NodePath nPath
9dcb40e74ab9 added some figres
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
295 = op.getNodePath();
20
04e41820d930 modified description for DefaultTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
296 DefaultTreeOperation treeOp
21
9dcb40e74ab9 added some figres
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
297 = new DefaultTreeOperation(nPath, nOp);
20
04e41820d930 modified description for DefaultTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
298 DefaultTreeOperationContainer c
04e41820d930 modified description for DefaultTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
299 = new DefaultTreeOperationContainer();
04e41820d930 modified description for DefaultTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
300 c.unconvert(treeOp);
04e41820d930 modified description for DefaultTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
301 Value v = msgpack.unconvert(c);
04e41820d930 modified description for DefaultTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
302 list.add(v);
04e41820d930 modified description for DefaultTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
303 }
04e41820d930 modified description for DefaultTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
304 Value listValue
04e41820d930 modified description for DefaultTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
305 = msgpack.unconvert(list);
04e41820d930 modified description for DefaultTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
306 logValue = listValue; // field variable
04e41820d930 modified description for DefaultTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
307 }
24
4e7979f6b571 added bib file
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
308 \end{verbatim}
4e7979f6b571 added bib file
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
309 %\end{lstlisting}
20
04e41820d930 modified description for DefaultTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
310
04e41820d930 modified description for DefaultTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
311 List で保持していた TreeOperation を List<Value> へと変換させている.
04e41820d930 modified description for DefaultTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
312 また, TreeOperationLog の保持だけでなく, 編集した木の名前やリビジョン番号, 変更を行ったノードの情報を
04e41820d930 modified description for DefaultTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
313 ノードの名前といった情報も保持するようにした.
04e41820d930 modified description for DefaultTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
314 DefaultTreeOperationLogContainer により, TreeOperationLog を Data Segment へと put することができる.
18
b3bce5bacc04 wrote DefatltTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 17
diff changeset
315
21
9dcb40e74ab9 added some figres
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
316 \subsection{ログを扱う Data Segment}
9dcb40e74ab9 added some figres
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
317 Alice の各ノードは "log", "childLog" というキーでログを扱う(図\ref{fig:topology}).
9dcb40e74ab9 added some figres
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
318
9dcb40e74ab9 added some figres
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
319 \begin{figure}[htpb]
9dcb40e74ab9 added some figres
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
320 \begin{center}
9dcb40e74ab9 added some figres
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
321 \includegraphics[scale=0.50]{figures/alice_topology.pdf}
9dcb40e74ab9 added some figres
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
322 \caption{形成されるトポロジーと Data Segment}
9dcb40e74ab9 added some figres
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
323 \label{fig:topology}
9dcb40e74ab9 added some figres
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
324 \end{center}
9dcb40e74ab9 added some figres
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
325 \end{figure}
19
4afecc3d3331 added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 18
diff changeset
326
4afecc3d3331 added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 18
diff changeset
327 "log" にはそのノードが行った木の編集のログが入る.
22
4cc89b4cf3dd wrote discription for childLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
328 また, 子供となるノードは "parent" というキーを使うことで親ノードの Data Segment Manager にアクセスすることができる.
4cc89b4cf3dd wrote discription for childLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
329 子供となるノードは親の "log" を待ち反映する Code Segment (LogUpdateCodeSegment) を走らせており, ログが put されるとそのデータを受け取り
4cc89b4cf3dd wrote discription for childLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
330 Code Segment の処理が行われる(図\ref{fig:putlog}).
21
9dcb40e74ab9 added some figres
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
331 \begin{figure}[htpb]
9dcb40e74ab9 added some figres
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
332 \begin{center}
9dcb40e74ab9 added some figres
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
333 \includegraphics[scale=0.50]{figures/putLog.pdf}
24
4e7979f6b571 added bib file
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
334 \caption{親ノードの更新を行う Code Segment}
21
9dcb40e74ab9 added some figres
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
335 \label{fig:putlog}
9dcb40e74ab9 added some figres
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
336 \end{center}
9dcb40e74ab9 added some figres
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
337 \end{figure}
9dcb40e74ab9 added some figres
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 20
diff changeset
338
19
4afecc3d3331 added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 18
diff changeset
339 "childLog" には子供となるノードが行った編集のログが入れられる.
22
4cc89b4cf3dd wrote discription for childLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
340 ノードは "childLog" の Data Segment にデータが入るの待っている Code Segment が常に走らせており, 子供が行った木の編集が
4cc89b4cf3dd wrote discription for childLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
341 "childLog" に put されることで親へとデータの伝搬が行われる(図\ref{fig:putchildlog}).
4cc89b4cf3dd wrote discription for childLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
342 \begin{figure}[htpb]
4cc89b4cf3dd wrote discription for childLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
343 \begin{center}
4cc89b4cf3dd wrote discription for childLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
344 \includegraphics[scale=0.50]{figures/putChildLog.pdf}
24
4e7979f6b571 added bib file
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
345 \caption{子供のノードの更新を行う Code Segment}
22
4cc89b4cf3dd wrote discription for childLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
346 \label{fig:putchildlog}
4cc89b4cf3dd wrote discription for childLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
347 \end{center}
4cc89b4cf3dd wrote discription for childLog
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 21
diff changeset
348 \end{figure}
20
04e41820d930 modified description for DefaultTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 19
diff changeset
349
19
4afecc3d3331 added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 18
diff changeset
350
26
0923a2659888 wrote description for merge algorithm
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
351 \subsection{Merge algorithm の設計}
0923a2659888 wrote description for merge algorithm
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
352 Jungle はログの衝突が起きた場合に, Merge を行うことで衝突を解決する.
0923a2659888 wrote description for merge algorithm
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
353 今回実装した掲示板における Merge algorithm は単純な実装である.
0923a2659888 wrote description for merge algorithm
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
354 書き込みのタイムスタンプと既に書き込まれたデータのタイムスタンプを比べ, ソートを行う.
0923a2659888 wrote description for merge algorithm
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
355
0923a2659888 wrote description for merge algorithm
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
356 掲示板においての Merge に関してはそれで十分である.
0923a2659888 wrote description for merge algorithm
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
357 しかし, ブログや Wiki といった CMS を設計するさいにはもっと複雑な Merge になる.
0923a2659888 wrote description for merge algorithm
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
358 どのように Merge algorithm を実装していくかはよく考えて行かなければならない.
19
4afecc3d3331 added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 18
diff changeset
359
23
335cbec61221 added figure
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 22
diff changeset
360
26
0923a2659888 wrote description for merge algorithm
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
361 \section{Cassandra との比較}
0923a2659888 wrote description for merge algorithm
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
362 Cassandra は複数のサーバで動作を想定した分散データベースである.
0923a2659888 wrote description for merge algorithm
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
363 Cassandra は分散 Key-Value ストアデータベースであり, Dynamo\cite{DYNAMO}とBigTable\cite{BIGTABLE}を合わせた
0923a2659888 wrote description for merge algorithm
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
364 特徴を持っている.
0923a2659888 wrote description for merge algorithm
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
365 データの Read と Write に対して Consistency Level を設定することができる.
0923a2659888 wrote description for merge algorithm
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
366 Write に関してはデータの書き込みが全体, 過半数, もしくは1つのノードに書き込まれたかどうかの整合性の設定ができる.
0923a2659888 wrote description for merge algorithm
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
367 Read に関しては最初にデータを持っていたノードか, 全体を検索して最新のタイムスタンプを確認するかといった整合性の設定ができる.
0923a2659888 wrote description for merge algorithm
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
368 Consistency Level にもよるがつまり Cassandra はデータについて複数のノードに問い合わせいることになる.
0923a2659888 wrote description for merge algorithm
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
369
0923a2659888 wrote description for merge algorithm
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
370 \begin{figure}[htpb]
0923a2659888 wrote description for merge algorithm
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
371 \begin{center}
0923a2659888 wrote description for merge algorithm
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
372 \includegraphics[scale=0.50]{figures/cassandra.pdf}
0923a2659888 wrote description for merge algorithm
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
373 \caption{Cassandra におけるデータの更新・読み込み}
0923a2659888 wrote description for merge algorithm
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
374 \label{fig:cassandra}
0923a2659888 wrote description for merge algorithm
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
375 \end{center}
0923a2659888 wrote description for merge algorithm
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
376 \end{figure}
0923a2659888 wrote description for merge algorithm
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
377
0923a2659888 wrote description for merge algorithm
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
378
0923a2659888 wrote description for merge algorithm
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
379 \subsection{Jungle のデータ要求}
0923a2659888 wrote description for merge algorithm
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
380 Jungle ではデータの要求が行われた場合, 手元にあるデータを返す.
27
d2360cf1bfbf added distribute_jungle.graffle
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
381 データの編集が行われた場合は, 他ノードへとログを伝搬していく(図\ref{fig:distribute_jungle}).
d2360cf1bfbf added distribute_jungle.graffle
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
382 \begin{figure}[htpb]
d2360cf1bfbf added distribute_jungle.graffle
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
383 \begin{center}
d2360cf1bfbf added distribute_jungle.graffle
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
384 \includegraphics[scale=0.60]{figures/distribute_jungle.pdf}
d2360cf1bfbf added distribute_jungle.graffle
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
385 \caption{Jungle のデータ伝搬}
d2360cf1bfbf added distribute_jungle.graffle
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
386 \label{fig:distribute_jungle}
d2360cf1bfbf added distribute_jungle.graffle
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
387 \end{center}
d2360cf1bfbf added distribute_jungle.graffle
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
388 \end{figure}
18
b3bce5bacc04 wrote DefatltTreeOperationLogContainer
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 17
diff changeset
389
28
62114661471d wrote request data
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
390 この時, 別のログと衝突が起きた場合は衝突を検知したノードが Merge を行う.
27
d2360cf1bfbf added distribute_jungle.graffle
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 26
diff changeset
391 その後 Merge を行ったログをまた他ノードへと伝搬させていく.
26
0923a2659888 wrote description for merge algorithm
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
392
28
62114661471d wrote request data
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
393 Jungle は非破壊により過去のデータを持っているため Merge を行うことができる.
62114661471d wrote request data
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
394 それにより最新のデータでなくてもデータを返すことができ, それがスケーラビリティ
62114661471d wrote request data
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
395 に繋がると考えている.
26
0923a2659888 wrote description for merge algorithm
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
396
29
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
397 \section{掲示板による Jungle の性能評価}
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
398 Jungle の例題のアプリケーションとして Jetty を用いて実装された掲示板がある.
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
399 今回作成した分散バージョンと2つのベンチマークをとり性能比較を行う.
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
400 ベンチマークは学科が提供する VMWare のクラスタを用いて行う.
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
401
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
402 \subsection{実験方法}
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
403 複数のクラスタから並列に 5000 回アクセスを行い, それぞれのクラスタの
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
404 平均時間をとる.
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
405 クラスタ1台から45台まで順次並列にアクセスを行いグラフ化する.
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
406
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
407 \subsection{実験環境}
26
0923a2659888 wrote description for merge algorithm
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
408
29
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
409 \begin{table}[!htbp]
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
410 \caption{掲示板を動かすサーバーの仕様}
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
411 \label{tab:server_spec_1}
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
412 \begin{center}\small
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
413 \begin{tabular}{|c||c|} \hline
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
414 名前 & 概要 \\ \hline \hline
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
415 CPU &Intel(R) Xeon(R) CPU X5650@2.67GHz*2\\ \hline
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
416 物理コア数 & 12 \\ \hline
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
417 論理コア数 & 24 \\ \hline
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
418 Memory & 132GB \\ \hline
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
419 OS & Fedora 16 \\ \hline
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
420 JavaVM & 1.6.0\_39-b04 \\ \hline
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
421 \end{tabular}
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
422 \end{center}
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
423 \end{table}
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
424
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
425
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
426 \begin{table}[!htbp]
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
427 \caption{検証に利用するVMWareクラスタの仕様}
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
428 \label{tab:cluster_spec_vmware}
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
429 \begin{center}\small
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
430 \begin{tabular}{|c||c|} \hline
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
431 名前 & 概要 \\ \hline \hline
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
432 CPU & Intel(R) Xeon(R) CPU X5650@2.67GHz \\ \hline
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
433 Memory & 8GB \\ \hline
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
434 OS & CentOS 5.8 \\ \hline
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
435 HyperVisor & VMWare ESXi \\ \hline
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
436 \end{tabular}
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
437 \end{center}
aec0e1852d85 wrote environment
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 28
diff changeset
438 \end{table}
26
0923a2659888 wrote description for merge algorithm
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
439
28
62114661471d wrote request data
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 27
diff changeset
440
26
0923a2659888 wrote description for merge algorithm
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 24
diff changeset
441 \subsection{評価}
0
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
442
19
4afecc3d3331 added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 18
diff changeset
443
0
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
444 \section{まとめ}
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
445
19
4afecc3d3331 added some figures
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 18
diff changeset
446
24
4e7979f6b571 added bib file
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
447 \nocite{*}
0
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
448 \bibliographystyle{junsrt}
24
4e7979f6b571 added bib file
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 23
diff changeset
449 \bibliography{jssst}
0
fd15dd05e50f first commit
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
450 \end{document}
3
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
451
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
452
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
453
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
454
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
455
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
456
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
457
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
458
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
459
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
460
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
461
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
462
a16f4ef93295 added sty files
Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
parents: 2
diff changeset
463