Mercurial > hg > Papers > 2013 > nobuyasu-jssst

comparison meeting20130802/index.html @ 46:0c6ef18bf2e8

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