Mercurial > hg > Papers > 2013 > nobuyasu-jssst

comparison presen/index.html @ 48:5dadfd75cfb0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add presen
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Mon, 09 Sep 2013 09:03:33 +0900
parents
children 56cb62f019e5
comparison
equal deleted inserted replaced
47:533180cea89f 48:5dadfd75cfb0
1 <!DOCTYPE html>
2 <html>
3 <head>
4 <style type="text/css">
5 .center {
6 margin-left: auto;
7 margin-right: auto;
8 text-align: center;
9 }
10 </style>
11
12 <title>Presentation</title>
13
14 <meta charset='utf-8'>
15 <script
16 src='./slides.js'></script>
17 </head>
18
19 <style>
20 /* Your individual styles here, or just use inline styles if that’s
21 what you want. */
22
23
24 </style>
25
26 <body style='display: none'>
27
28 <section class='slides layout-regular template-default'>
29
30 <!-- Your slides (<article>s) go here. Delete or comment out the
31 slides below. -->
32
33
34 <article>
35 <h1><font size=10em>
36 Data Segment の分散データベースへの応用
37 </font>
38 </h1>
39 <p>
40 琉球大学 大城信康
41 <br>
42 11 Sep 2013
43 </p>
44 </article>
45
46 <article>
47 <h3>研究の目的と背景</h3>
48 <ul>
49 <li>当研究室では並列分散フレームワーク Alice を開発している</li>
50 <li>Alice はタスクを Code Segment, データを Data Segment という単位で扱うプログラミングスタイルを提供する</li>
51 <li>また, 当研究室では非破壊的木構造を用いたデータベースである Jungle を開発している</li>
52 <li>非破壊的木構造とは, データの編集の際に一度木構造として保存したデータには触れず, 新しく木構造を作成してデータの編集を行うこと</li>
53 <li>Jungle は分散データベースとして設計されているが, 今のところシングルサーバ上でしか動かない</li>
54 <li><font color="red">本研究では, Jungle に分散データベースとしての実装を行った. また例題を作成し評価を行う.</font></li>
55 </ul>
56 </article>
57
58 <article>
59 <h3>並列分散フレームワーク Alice</h3>
60 <ul>
61 <li>当研究室で開発している</li>
62 <li>Data Segment と Code Segment による並列・分散プログラミングを提供</li>
63 <br>
64 <li>まず Data Segment と Code Segment, それと Alice におけるデータ表現について説明を行う</li>
65 </ul>
66 </article>
67
68 <article>
69 <h3>Data Segment</h3>
70 <ul>
71 <li>計算に必要なデータ</li>
72 <li>Alice は Data Segment を文字列の Key で管理</li>
73 <li>Key 毎にリストが用意され, put された順番で Data Segment は取り出される</li>
74 <li>Data Segment Manager(DSM) により管理される</li>
75 <p class="center">
76 <img src="./pic/put.png">
77 </p>
78 </ul>
79 </article>
80
81 <article>
82 <h3>Code Segment</h3>
83 <ul>
84 <li>Data Segment を受け取り計算を行うコード</li>
85 <li>並列プログラミングにおけるタスクにあたる</li>
86 <li>Code Segment は計算に使う Data Segment の Key を登録してその Key にあたる Data Segment
87 が用意され次第処理が実行される</li>
88 <p class="center">
89 <img src="./pic/dsandcs.png">
90 </p>
91 <li>計算を行った結果を新たな Data Segment として出力する</li>
92 </ul>
93 </article>
94
95 <article>
96 <h3>Alice上でのデータ表現:MessagePack</h3>
97 <ul>
98 <li>Data Segment のデータ表現には MessagePack を利用</li>
99 <li>Messagepack はバイナリをベースにしたシリアライズライブラリー</li>
100 <li>独自のクラスでも @Message アノテーションを付けることでシリアライズ可能<br>
101 (その際にはシリアライズできる型のみのフィールドをもつこと)</l>
102 <li>MessagePack を使用することで Alice 以外のプログラムでの Data Segment を扱うことが可能になる</li>
103 </ul>
104 </article>
105
106 <article>
107 <h3>非破壊的木構造を用いたデータベース Jungle</h3>
108 <ul>
109 <li>Jungle はスケーラビリティのある CMS の開発を目指している</li>
110 <li>一般的なコンテンツマネジメントシステムのウェブサイトの構造は大体が木構造</li>
111 <br>
112 </ul>
113 </article>
114
115
116 <article>
117 <h3>破壊的木構造</h3>
118 <ul>
119 <li>木構造で保持するデータを直接書き換える</li>
120 <li>編集を行う際にロックをかける必要がある</li>
121 <p class="center">
122 <img src="./pic/destructive_tree.png">
123 </p>
124 <li>データを受け取ろうと木を走査するスレッドは編集時には書き換えの終了をまつ必要がある</li>
125 <li><font color=red>スケールしにくい</font></li>
126 </ul>
127 </article>
128
129 <article>
130 <h3>非破壊的木構造</h3>
131 <ul>
132 <li>一度作成したデータの破壊は行わない</li>
133 <li>データの編集は, 編集が行われるノードまでをルートからコピーを行い新しい木構造を作ることで行う</li>
134 <p class="center">
135 <img src="./pic/non_destructive_tree.png">
136 </p>
137 <li>非破壊的木構造ではデータの編集中に走査をすることが可能なためスケールすると考えている</li>
138 </ul>
139 </article>
140
141 <article>
142 <h3>Jungle におけるデータ編集: API</h3>
143 <ul>
144 <li>Jungle ではデータの編集を行う Editor を提供している</li>
145 <li>Editor が提供するデータ編集のメソッドは次のようなものがある</li>
146 <ul>
147 <li>Nodeの追加を行う<br><font color=blue>addNewChildAt(NodePath _path, int _pos)</font></li>
148 <li>Nodeの削除を行う<br><font color=blue>deleteChildAt(NodePath _path, int pos)</font></li>
149 <li>Nodeにattributeを追加する<br><font color=blue>putAttribute(NodePath _path, String _key,<br> ByteBuffer _value)</font></li>
150 <li>Nodeのattributeを削除する<br><font color=blue>deleteAttribute(NodePath _path, String _key)</font></li>
151 </ul>
152 </ul>
153 </article>
154
155 <article>
156 <h3>Jungle におけるデータ編集: NodePath</h3>
157 <ul>
158 <li>NodePath は root から編集を行う Node までの道を示す</li>
159 <li>例えば NodePath が -1,1,2,3 の場合は次の Node を示す</li>
160 <p class="center">
161 <img src="./pic/nodepath.png">
162 </p>
163 <li>Jungle におけるデータ編集はこの NodePath を Editor が提供する API に渡すことで行われる</li>
164 </ul>
165 </article>
166
167 <article>
168 <h3>TreeOperationLog</h3>
169 <ul>
170 <li>Editor による編集の命令はある程度の塊で扱われる</li>
171 <li>この編集の塊を TreeOperatinLog という</li>
172 <li>今回実装した掲示板では, 書き込み時に次のような TreeOperaitonLog が作られる</li>
173 <pre>
174 [APPEND_CHILD:<-1>:pos:1]
175 [PUT_ATTRIBUTE:<-1,1>:key:author,value:oshiro]
176 [PUT_ATTRIBUTE:<-1,1>:key:mes,value:hello]
177 [PUT_ATTRIBUTE:<-1,1>:key:key,value:hoge]
178 [PUT_ATTRIBUTE:<-1,1>:key:timestamp,value:0] </pre>
179 <li>大文字の英字は実行した API を示す</li>
180 <li>&lt;&gt;で囲まれた数字は NodePath を示す</li>
181 <li>key と value は attribute に格納する内容を示す</li>
182 </ul>
183 </article>
184
185 <article>
186 <h3>Alice を用いた Jungle の分散実装</h3>
187 <ul>
188 <li>Alice により TreeOperationLog を Data Segment として扱うことで行う</li>
189 <li>他Nodeがその Data Segment にアクセスを行えるようにする</li>
190 <li>アクセスできるようにするためには次の作業が必要</li>
191 <ul>
192 <li>トポロジーの形成</li>
193 <li>TreeOperationLog を MessagePack によりシリアライズ</li>
194 <li>TreeOperationlog を扱う Data Segment の作成</li>
195 </ul>
196 </ul>
197 </article>
198
199 <article>
200 <h3>トポロジーの形成</h3>
201 <ul>
202 <li>トポロジーの形成は Alice の機能を用いる</li>
203 <li>Alice ではトポロジー設定用ファイルに従いノード同士を接続させる</li>
204 <li>5ノード2分木のノードを組みたいときは次のようなファイルになる</li>
205 <pre style="overflow:scroll; height:300px;">
206 digraph test {
207 node0 -> node1
208 node0 -> node2
209 node1 -> node0
210 node1 -> node3
211 node1 -> node4
212 node2 -> node0
213 [label="child1"]
214 [label="child2"]
215 [label="parent"]
216 [label="child1"]
217 [label="child2"]
218 [label="parent"]
219 node3 -> node1 [label="parent"]
220 node4 -> node1 [label="parent"]
221 }
222 </pre>
223 </ul>
224 </article>
225
226 <article>
227 <h3>トポロジーの形成</h3>
228 <ul>
229 <p>生成されるトポロジー</p>
230 <p class="center">
231 <img src="./pic/tree_topology.png">
232 </p>
233 <li>子供となるノードは parent キーにより親の DSM にアクセスできる</li>
234 <li>親となるノードは child0, child1 キーにより子供のノードの DSM にアクセスできる</li>
235 <li><font color=blue>Alice が提供する機能により楽にトポロジーの形成と他のノードがもつデータへのアクセスができる</font></li>
236 </ul>
237 </article>
238
239 <article>
240 <h3>TreeOperationLog の MessagePack によるシリアライズ</h3>
241 <ul>
242 <li>TreeOperationLog を Data Segment で扱うために MessagePack によるシリアライズ可能にする必要がある</li>
243 <li>MessagePack によりクラスをシリアライズするためには, そのクラスがもつフィールド全てがシリアライズできるものでないといけない</li>
244 <li>TreeOperationLog が保持するフィールドを全てシリアライズして保持する container を用意</li>
245 <li>TreeOperationLog は一度その container で Value 型へと変換されて保持されることで Data Segment として扱えるようにした</li>
246 </ul>
247 </article>
248
249 <article>
250 <h3>ログを扱う Data Segment</h3>
251 <ul>
252 <li>Data Segment にされた TreeOperaiontinLog はAlice上で "log", "childLog" というキーで扱われる</li>
253 <li>"log" にはそのノードが行った木の編集ログが入る</li>
254 <li>子供となるノードは "parent" キーを使うことで親のノードの DSM にアクセスできる</li>
255 <p class="center">
256 <img src="./pic/alice_topology.png">
257 </p>
258 <li>子供となるノードは親の "log" を見張る Code Segment が走らせており, ログが put されると
259 そのデータを受け取り自身の Tree へと反映を行う</li>
260 </ul>
261 </article>
262
263 <article>
264 <h3>ログを扱う Data Segment</h3>
265 <ul>
266 <li>"childLog" には子供となるノードが行った編集のログが入れられる</li>
267 <li>各ノードでは "childLog" を見張る Code Segment が走っており, データが put され次第
268 Tree へのログの反映が行われる</li>
269 <li>親ノードの "log" と自身がもつ "childLog" を Code Segment でみはることでデータの分散を
270 行う</li>
271 <table>
272 <tr style="width:100%;">
273 <td style="width:50%;">
274 <p>
275 <img src="./pic/putLog.png">
276 </p>
277 </td>
278 <td style="width:50%;">
279 <p>
280 <img src="./pic/putChildLog.png">
281 </p>
282 </td>
283 </tr>
284 </table>
285 </ul>
286 </article>
287
288 <article>
289 <h3>Merge algorithm の設計</h3>
290 <ul>
291 <li>Jungle はログの衝突が起きた場合に Merge を行うことで衝突を解決する</li>
292 <li>今回実装した掲示板における Merge algorithm は単純な実装</li>
293 <li>書き込むデータと既に書き込まれたデータのタイムスタンプをみてMergeを行う</li>
294 <br>
295 <li>掲示板においてのMergeはそれで十分だが, ブログやWikiといったCMSを設計するさいには
296 もっと複雑なMergeになる</li>
297 <li>どのようにMerge algorithmを実装していくかはよく考えていかなければならない</li>
298 </ul>
299 </article>
300
301 <article>
302 <h3>Cassandra の実装との比較</h3>
303 <ul>
304 <li>Jungle では非破壊により過去のデータを保持しているためMergeを行うことが可能</li>
305 <li>それにより最新のデータなくてもデータを返すことができる</li>
306 <li><font color=blue>ロックが少なくなりスケーラビリティに繋がると考えている</font></li>
307 </ul>
308 </article>
309
310 <article>
311 <h3>掲示板によるJungleの性能評価</h3>
312 <ul>
313 <li>Jungle の例題のアプリケーションとして掲示板を作成した</li>
314 <li>組み込みウェブサーバである jetty をフロントエンドに実装</li>
315 <li>今回作成した分散バージョンと元のバージョンをシングルサーバ上で動かし, 2つの
316 ベンチマークをとり性能比較を行う</li>
317 <li>ベンチマークは学科の提供するVMのクラスタを用いる</li>
318 </ul>
319 </article>
320
321 <article>
322 <h3>実験方法</h3>
323 <ul>
324 <li>複数のクラスタから並列に5000回アクセス(HTTP Request)を行い, 平均時間をとる</li>
325 <li>クラスタ1台から45台まで順次並列にアクセスを行った結果をグラフ化する</li>
326 </ul>
327 </article>
328
329
330 <article>
331 <h3>実験環境</h3>
332 <table style="font-size: 0.7em;">
333 <tr>
334 <th></th><th>掲示板を動かすサーバのスペック</th>
335 </tr>
336 <tr>
337 <td>CPU</td>
338 <td>Intel(R) Xeon(R) CPU X5650@2.67GHz</td>
339 </tr>
340 <tr>
341 <td>コア数</td>
342 <td>24</td>
343 </tr>
344 <tr>
345 <td>Memory</td>
346 <td>132GB</td>
347 </tr>
348
349 <table style="font-size: 0.7em"/>
350 <tr>
351 <th></th><th>VMWareクラスタ(リクエストをおくるサーバ)</th>
352 </tr>
353 <tr>
354 <td>台数</td><td>45</td>
355 </tr>
356 <tr>
357 <td>CPU</td>
358 <td>Intel(R) Xeon(R) CPU X5650@2.67GHz</td>
359 </tr>
360 <tr>
361 <td>コア数</td>
362 <td>4</td>
363 </tr>
364 <tr>
365 <td>Memory</td>
366 <td>8GB</td>
367 </tr>
368 <tr>
369 <td>OS</td>
370 <td>Fedora 16</td>
371 </tr>
372 <tr>
373 <td>HyperVisor</td>
374 <td>VMWare ESXi</td>
375 </tr>
376 </table>
377
378
379
380 </article>
381
382 <article>
383 <h3>実験結果: 読み込み</h3>
384 <table style="text-align:center; font-size:0.7em;">
385 <tr>
386 <!--
387 <td> <img style="height:300px;" src="./pic/read_result.png"> </td>
388 -->
389 <td> <img style="height:300px;" src="./pic/read_bench_with_cassandra.png"> </td>
390 </tr>
391 <tr>
392 <td>サーバの読み込み実験結果</td>
393 </tr>
394 </table>
395 <ul>
396 <li>今回の実装では読み込みに関する変更の部分はほぼ無い</li>
397 <li>そのため分散サーバ版とシングルサーバ版もに似た結果となっている</li>
398 <li>グラフも両方とも平行にあがっている</li>
399 </ul>
400 </article>
401
402 <article>
403 <h3>実験結果: 書き込み</h3>
404 <table style="text-align:center; font-size:0.7em;">
405 <tr>
406 <!--
407 <td > <img style="height:300px;" src="./pic/write_result.png"> </td>
408 -->
409 <td> <img style="height:300px;" src="./pic/write_bench_with_cassandra.png"> </td>
410 </tr>
411 <tr>
412 <td>サーバの書き込み実験結果</td>
413 </tr>
414 </table>
415 <ul>
416 <li>分散サーバ版がシングルサーバ版よりも遅い</li>
417 <li>これは分散版は書き込まれた内容をData Segment にする作業がはいる為とおもわれる</li>
418 </ul>
419 </article>
420
421 <article>
422 <h3>まとめ</h3>
423 <ul>
424 <li>今回, Alice を用いて Jungle の分散データベースの実装を行った</li>
425 <li>Jungle の編集のログを Data Segment として Alice 上で他ノードへと送ることで実装</li>
426 <li>今回シングル版から分散版への変更は1000行程度のコードの追加で行うことができた</li>
427 <li>これは Alice によりトポロジーの形成部分を書く必要がなかったことがあげられる</li>
428 <li>Alice を用いてると比較的楽に分散プログラムの作成ができることが確認できた</li>
429 </ul>
430 </article>
431
432 <article>
433 <h3>まとめ 2</h3>
434 <ul>
435 <li>また, 実装を行った分散データベースで掲示板の作成を, 元の Jungle との性能比較も行った</li>
436 <li>読み込み速度に差は無いが, 書き込み速度は分散版が遅いことを確認した</li>
437 </ul>
438 </article>
439
440 <article>
441 <h3>今後の課題</h3>
442 <ul>
443 <li>次回は, Cassandra でも同じ分散プログラムを作り, 分散環境における性能比較を行いたい</li>
444 <li>そのためには分散データベースにおけるベンチマークの取り方の検証から行う必要がある</li>
445 <br>
446 <li>また, Alice 内部では java.util.concurrent.Executorを使用している</li>
447 <li>Alice を使用してのプログラムは Alice 自身の Thread Pool との調和も考えていく必要もある</li>
448 <li>Alice の Thread Pool との競合性についての懸賞も行なって行きたい</li>
449 </ul>
450 </article>
451
452
453 <article>
454 <h3>Cassandra の実装との比較</h3>
455 <ul>
456 <li>Cassandra ではデータの書き込みはノードの過半数に行われるのを待つ</l>
457 <li>読み込みに関しても過半数のノードを調べ, 最も新しいタイムスタンプを持つデータを返す</li>
458 <p class="center">
459 <img src="./pic/cassandra.png">
460 </p>
461 </ul>
462 </article>
463
464 <article>
465 <h3>Cassandra の実装との比較: Jungle の場合</h3>
466 <ul>
467 <li>Jungle ではデータはノードが手元に持っているものを返す</li>
468 <li>データの編集が行われた場合は, 他ノードへとログを伝搬していく</li>
469 <li>ログの衝突が起きた場合は衝突を検知したノードがMergeを行い, Mergeを行ったログを伝搬させる</li>
470 <p class="center">
471 <img src="./pic/distribute_jungle.png">
472 </p>
473 </ul>
474 </article>
475
476 </body>
477 </html>