Mercurial > hg > Papers > 2014 > nobuyasu-master

comparison slides/index.html_back @ 85:07aec327a7bc

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Added slides.htlm
author Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp>
date Mon, 03 Feb 2014 13:06:41 +0900
parents bd73f0e1cdd4
children
comparison
equal deleted inserted replaced
81:e36cbf39a949 85:07aec327a7bc
1 <!DOCTYPE html> 1 <!DOCTYPE html>
2 <html> 2 <html>
3 <head> 3 <head>
4 <meta charset='utf-8'> 4 <meta charset='utf-8'>
5 <title>分散データベースJungle</title> 5 <title>分散 Database Jungle に関する研究</title>
6 6 <script src='slides.js'></script>
7 <!-- 7 <style media='screen,projection'>
8 Notes on CSS media types used: 8 /****
9 9 * Add your styles here.
10 1) projection -> slideshow mode (display one slide at-a-time; hide all others) 10 */
11 2) screen -> outline mode (display all slides-at-once on screen) 11
12 3) print -> print (and print preview) 12 body { font-size: 175%; }
13
14 .step { color: silver; } /* or hide next steps e.g. .step { visibility: hidden; } */
15
16 .slide {
17 font-family: 'Open Sans', Arial, sans-serif;
18
19 color: rgb(102, 102, 102);
20 text-shadow: 0 1px 1px rgba(0, 0, 0, .1);
21 }
13 22
14 Note: toggle between projection/screen (that is, slideshow/outline) mode using t-key 23 .slide h1, .slide h2, .slide h3 {
15 24 color: rgb(51, 51, 51);
16 Questions, comments? 25 }
17 - send them along to the mailinglist/forum online @ http://groups.google.com/group/webslideshow 26
27 .slide pre {
28 font-family: 'Droid Sans Mono', 'Courier New', monospace;
29 font-size: 80%;
30
31 padding: 5px 10px;
32
33 margin-top: 40px;
34 margin-bottom: 40px;
35
36 color: black;
37 background: rgb(240, 240, 240);
38 border: 1px solid rgb(224, 224, 224);
39 box-shadow: inset 0 2px 6px rgba(0, 0, 0, .1);
40 overflow: hidden;
41 }
42
43 .slide code {
44 font-family: 'Droid Sans Mono', 'Courier New', monospace;
45 color: black;
46 }
47
48 .slide h3 {
49 margin-top:-15px;
50 }
51
52 </style>
53 </head>
54 <body>
55
56 <section class='slides'>
57 <!-- Add your slides here. Delete or comment out the slides below. -->
58
59 <article class='cover'>
60 <h1>
61 分散 Database Jungle に関する研究
62 <br>
63
64 </h1>
65 <p>
66 大城 信康
67 <br>
68 Feb 3, 2013
69 </p>
70 </article>
71
72 <article>
73 <h3>
74 概要
75 </h3>
76 <p>非破壊的木構造データベースJungleに分散実装を行い掲示板システムに特化したデーターベースを作成し、その評価を行った。</p>
77 <p>分散データベースCassandraより2倍以上速く、分散環境下においては10倍以上速い結果も確認された。</p>
78 <br/>
79 </article>
80
81 <article>
82 <h3>
83 研究の目的と背景
84 </h3>
85 <p>ウェブサービスにとってデータベースは必須であり、ウェブサービスの規模に比例してデータベースへの負荷も高まる。</p>
86 <p>データベースの処理能力の高さはそのままウェブサービスの質に繋がるため、データベースのスケーラビリティの確保は重要である。</p>
87 <p>スケーラビリティ確保の方法としてデータ分散があるが、分散する方法により性能も変わってくる。</p>
88 <p>スケーラビリティのある分散データベースとしてJungleの実装を行う。</p>
89 </article>
90
91
92 <article>
93 <h3>
94 ウェブサービスにおけるデータベースの重要性
95 </h3>
96 <p>ウェブサービスへの負荷が高まることは、データベースへの負荷が高まることでもある。</p>
97 <p>データベースの性能が低ければ負荷に耐え切れずサービスはダウンする</p>
98 <p style="text-align:center;">
99 <img src="./images/service_down.png">
100 </p>
101 <p>そのため、データベースにはスケーラビリティが必要</p>
102 </article>
103
104 <article>
105 <h3>
106 スケーラビリティとは
107 </h3>
108 <p>システムが負荷の増大に対して柔軟に拡張して対応できる性質</p>
109 <p>主に次の2つの方法によりシステムはスケールされる</p>
110 <ul>
111 <li><font color="blue">スケールアップ</font>：<br/>高価な単一マシンによる性能アップ</li>
112 <br/>
113 <li><font color="red">スケールアウト</font>：<br/>汎用的なマシンを複数台用意することで性能アップ</li>
114 </ul>
115 <p>分散システムにおいては<font color="red">スケールアウト</font>によりスケーラビリティを高める</p>
116 </article>
117
118 <article>
119 <h3>
120 データベースのスケーラビリティ
121 </h3>
122 <p>データベースのスケーラビリティを考えるとき、どういう用途で使用するかを考えるのが重要。</p>
123 <li>例えば、掲示板システムにおいては、書き込みと読み込みが速いことが求められる。</li>
124 <br/>
125 <p>ウェブサービスは、サービスの内容によってスケーラビリティの確保の仕方も変わってくる。</p>
126 <p>本研究で開発しているデータベースはコンテンツマネジメントシステム（CMS）を対象としている。</p>
127 <p style="text-align:center;">
128 <img style="" src="./images/scalability.png">
129 </p>
130
131 </article>
132
133 <article>
134 <h3>
135 コンテンツマネジメントシステム(CMS)
136 </h3>
137 <p>Webコンテンツを構成するテキストや画像などのデジタルコンテンツを管理し配信するシステム。</p>
138 <li>例：ブログツール、Wiki</li>
139 <p>分散コンテンツマネジメントシステムに求められること。</p>
140 <li>Webコンテンツを分散して管理</li>
141 <li>スケールアウトするシステム</li>
142 <p>データ全体の整合性に遅延がある、結果整合性でもよい。書き込みや読み込みを優先としたデータベースが必要。</p>
143 <p>そこで、非破壊的木構造データベースJungleの提案を行った。</p>
144 </article>
145
146 <article>
147 <h3>非破壊的木構造データベースJungle</h3>
148 <p>JungleはスケーラビリティのあるCMSの設計を目指して当研究室で開発されているデータベース。</p>
149 <p>データを木構造で、さらに非破壊で保持する。</p>
150 <br/>
151 </article>
152
153 <article>
154 <h3>破壊的木構造</h3>
155 <p>木構造の通常のデータ表現</p>
156 <p>破壊的木構造は、木構造により保持しているデータの編集をデータを直接書き換えることで行う</p>
157 <p style="text-align:center;">
158 <img style="height:300px;" src="./images/destructive_tree_slide.png">
159 </p>
160 </article>
161
162 <article>
163 <h3>破壊的木構造</h3>
164 <p>破壊的木構造ではデータの編集中にそのデータを読むことができない</p>
165 <p>編集が完了するまでまたなければならない</p>
166 <p style="text-align:center;">
167 <img style="width:500px;" src="./images/destructive_tree_demerit.png">
168 </p>
169 </article>
170
171 <article>
172 <h3>
173 非破壊的木構造
174 </h3>
175 <p>非破壊的木構造は一度作成したデータは変更しない</p>
176 <p>新しい木構造を作成することでデータの編集を行う</p>
177 <p style="text-align:center;">
178 <img style="height:300px;" src="./images/non_destructive_tree_slide.png">
179 </p>
180 <p></p>
181 </article>
182
183 <article>
184 <h3>
185 非破壊的木構造におけるデータ編集
186 </h3>
187 <p>目的とするノード5ををコピーして内容を編集する。ノード100となる</p>
188 <p>ルートノードから目的のノード5までに続くルートノードとノード2のコピーとりノード100と繋げる</p>
189
190 <p style="text-align:center;">
191 <img style="width:700px;" src="./images/non_destructive_tree_edit.png">
192 </p>
193 </article>
194
195 <article>
196 <h3>
197 非破壊的木構造におけるデータ編集と読み込み
198 </h3>
199 <p>新しく作成したルートノードに変更を加えていないノードへの参照を持たせる。新しい木構造のデータができる</p>
200 <p>最新のルートノードの登録を新しく作成した側のルートノードへと登録する</p>
201 <p style="text-align:center;">
202 <img style="width:700px;" src="./images/non_destructive_tree_edit2.png">
203 </p>
204 </article>
205
206 <article>
207 <h3>
208 非破壊的木構造の利点
209 </h3>
210 <p>非破壊的木構造は通常の木構造である破壊的木構造に比べ、以下のような利点を持つ</p>
211 <ul>
212 <li>一度作成したデータは変更されない</li>
213 <li>データが変更されないため自由にコピーを作ることができる(いつでも読み込みが可能)</li>
214 <li>ロックがすくない。ロックが必要なのは最新のルートノードを登録するときだけ</li>
215 </ul>
216 <p>ロックが少なく、いつでもコピーが可能なことから、非破壊的木構造はスケーラブルなシステムに有用となる</p>
217 </article>
218
219 <article>
220 <h3>
221 Jungleの分散設計
222 </h3>
223 <p>ここまでJungleに実装されている非破壊的木構造の利点について述べた。</p>
224 <p>次に、Jungleにおける分散設計について述べる。</p>
225 <p>データ分散を行うにあたり、まず考えることはトポロジーの形成と他のノードからデータの伝搬の仕方である。</p>
226 <p>Jungleはこの問題に対し、ツリートポロジーを形成し、データ編集の際に発生するcommit logを他のノードに流すことで解決する。</p>
227 </article>
228
229 <article>
230 <h3>
231 Jungleの分散設計：トポロジー形成とログによるデータ分散
232 </h3>
233 <small>
234 <table>
235 <tr>
236 <th>ツリートポロジーを形成</th>
237 <th>commit log伝搬によるデータ分散</th>
238 </tr>
239 <tr>
240 <td>
241 <img src="./images/tree_topology.png">
242 </td>
243 <td>
244 <img src="./images/distributed_jungle.png">
245 </td>
246 </tr>
247 </table>
248 <p>サーバノード同士でツリートポロジーを形成する。データ編集をどのように行ったのかを示すログ commit log を伝搬させデータの分散を行う。</p>
249 </small>
250 </article>
251
252 <article>
253 <h3>
254 非破壊的木構造の利点を活かした分散設計
255 </h3>
256 <p>Jungleで扱うつもりのデータは結果整合性でもよいCMSを想定していることを始めに説明した。</p>
257 <p>そこでJungleはMergeを使うことでデータの整合性をとることにした。</p>
258 <p>Mergeとは、2つ以上の変更を1つの変更にまとめることである。</p>
259 <p>分散システムにおいては、2つ以上のデータの更新が同じデータに対して行われていた場合、
260 更新を受け取って新しいデータを作ることを指す。</p>
261 <p>Mergeは自動で解決出来る場合とそうでない場合がある。</p>
262 </article>
263
264
265 <article>
266 <h3>
267 Mergeによる更新の衝突を自然に解決
268 </h3>
269 <small>
270 <table style="font-size: 0.7em; width:100%;" >
271 <tr>
272 <td><p style="margin-top:-5px; margin-bottom:-5px; text-align:center;"><img src="./images/tree_conflict.png"></p></td>
273 </tr>
274 <tr>
275 <td><p style="margin-top:-5px; margin-bottom:-5px; text-align:center;"><img src="./images/tree_conflict3.png"></p></td>
276 </tr>
277 </table>
278 <p style="margin-top:0px;">上の図は通常のデータ更新を示す</p>
279 <p style="margin-top:-20px;">下の図は、同じ木に対して2つのデータの更新があったが編集を無事終えるケースを示す</p>
280 </small>
281 </article>
282
283
284
285 <article>
286 <h3>
287 Mergeによる更新の衝突が自然に解決できない場合
288 </h3>
289 <table style="font-size: 0.7em; width:100%;" >
290 <tr>
291 <td><p style="margin-top:-5px; margin-bottom:-5px; text-align:center;"><img src="./images/tree_conflict2.png"></p></td>
292 </tr>
293 </table>
294 <p>木の同じノードに対してデータの編集が行われた場合、どのような編集結果にすればよいかわからない。</p>
295 <p>どのような木が組まれ、どのようにデータを保存するかはアプリケーション毎に変わってくる。そのため、アプリケーション毎に
296 Mergeアルゴリズムは考えなくてはならない。</p>
297
298 </article>
299
300 <article>
301 <h3>
302 JungleとMergeの相性
303 </h3>
304 <p>Jungleは非破壊で過去のデータも保持しているため、更新時に過去のデータを参照して自然なMergeを行うことが可能。</p>
305 <p>自然にMergeできない場合においても、アプリケーション毎にMergeアルゴリズムを設計することで対応する。</p>
306 <p>Mergeが自動で行われるようになれば、Jungleで扱う木構造データは編集を自由に行うことができる。</p>
307 <p>木構造データが自由に行えるようになれば、Jungleはデータのリクエストに対して手元のデータを返すことができる。</p>
308 <p>古いデータを編集されたものが更新されても、いずれはMergeにより最新のデータと合わせられるから。</p>
309 <p></p>
310 </article>
311
312
313 <article>
314 <h3>
315 Jungleの分散実装
316 </h3>
317 <p>以上がJungleにおける分散設計になる。</p>
318 <br/>
319 <p>この分散設計を元にJungleのサーバノード同士でツリトポロジーを構成し、ログによるデータ分散を実装した。</p>
320 <p>また、Mergeの例として掲示板プログラムにおけるMergeの実装も行った。</p>
321 </article>
322
323
324
325 <article>
326 <h3>
327 Jungleの分散実装:掲示板システムにおけるMerge
328 </h3>
329 <p>Jungleではアプリケーション毎にMergeアルゴリズムを設計</p>
330 <p>後述する性能比較に用いた掲示板システムにおけるMergeの実装を考える</p>
331 <p>掲示板システムにおけるデータ構造を以下に示す</p>
332 <p style="text-align:center;">
333 <img src="./images/bulletinboard.png">
334 </p>
335 </article>
336
337 <article>
338 <h3>
339 Jungleの分散実装:掲示板システムにおけるMerge
340 </h3>
341 <small>
342 <table style="font-size: 0.7em; width:100%;" >
343 <tr>
344 <td><p>1</p></td>
345 <td><p style="margin-top:-5px; margin-bottom:-5px; text-align:center;"><img src="./images/merge_impl1.png"></p></td>
346 </tr>
347 <tr>
348 <td>2</td>
349 <td><p style="margin-top:-5px; margin-bottom:-5px; text-align:center;"><img src="./images/merge_impl2.png"></p></td>
350 </tr>
351 <tr>
352 <td>3</td>
353 <td><p style="margin-top:-5px; margin-bottom:-5px; text-align:center;"><img src="./images/merge_impl3.png"></p></td>
354 </tr>
355 </table>
356 </small>
357 </article>
358
359 <article>
360 <h3>
361 分散データベースJungleの評価
362 </h3>
363 <p>分散データベースとしてJungleの性能を評価する。</p>
364 <p>分散Key-ValueデーターべースCassandraと比較を行う。</p>
365 <p>比較方法は、Jungle, Cassandra をそれぞれバックエンドとした簡易掲示板を作成する。</p>
366 <p>掲示板に対してHTTP Requestで並列に読み込みと書き込みの負荷をかけ計測する。</p>
367 <p>レスポンスが返る平均時間と標準偏差を求めグラフ化する</p>
368 </article>
369
370
371 <article>
372 <h3>
373 JungleとCassandraの比較方法
374 </h3>
375 <p>実験は以下の2つを行う</p>
376 <small>
377 <table style="font-size: 0.7em; width:100%;">
378 <tr>
379 <th>実験1:サーバ単体への負荷</th><th>実験2:複数台のサーバに対する負荷</th>
380 </tr>
381 <tr>
382 <td><img style="width:400px;" src="./images/cluster_request_server.png"></td>
383 <td><img style="width:400px;" src="./images/clients_request_servers.png"></td>
384 </tr>
385 <tr>
386 <td><p>複数のクライアントから単体のサーバへ負荷をかける</p></td>
387 <td><p>複数のクライアントから複数のサーバへ負荷をかける</p></td>
388 </tr>
389 </table>
390 <p>サーバ単体の性能と, 分散環境下における性能の2つを調べる。</p>
391 <p>分散環境下におけるノードは全て繋がっている</p>
392 </small>
393 </article>
394
395 <article>
396 <h3>
397 実験に使用するサーバの仕様
398 </h3>
399 <!--
400 <p>実験1:単体サーバへの負荷で使用するサーバ側</p>
18 --> 401 -->
19 402 <table style="font-size: 0.7em;">
20 <!-- style sheet links --> 403 <tr>
21 <link rel="stylesheet/less" href="themes/blank/projection.css.less" media="screen,projection"> 404 <th></th><th>ブレードサーバ</th>
22 <link rel="stylesheet/less" href="themes/blank/screen.css.less" media="screen"> 405 </tr>
23 <link rel="stylesheet/less" href="themes/blank/print.css.less" media="print"> 406 <tr>
24 407 <td>CPU</td>
25 <link rel="stylesheet/less" href="blank.css.less" media="screen,projection"> 408 <td>Intel(R) Xeon(R) CPU X5650@2.67GHz</td>
26 409 </tr>
27 <!-- Notes about less css support 410 <tr>
28 - all less stylesheets (*.css.less) need to get listed/loaded first (before the less.js script) 411 <td>コア数</td>
29 - find more info about less.js online @ http://lesscss.org 412 <td>24</td>
30 413 </tr>
31 ***** NOTE: 414 <tr>
32 less.js browser script currently won’t work if you’re using Google Chrome 415 <td>Memory</td>
33 and the path to your page starts with "file:///" due to a known Chrome issue. 416 <td>132GB</td>
34 (In the developer/js console you will see: 417 </tr>
35 XMLHttpRequest cannot load file:///../s6/shared/projection.css.less. 418 <tr>
36 Cross origin requests are only supported for HTTP.) 419 <td>OS</td>
37 --> 420 <td>Fedora 16</td>
38 421 </tr>
39 <!-- add js libs (less, jquery) --> 422 <tr>
40 <script src="js/less-1.1.4.min.js"></script> 423 <td>HyperVisor</td>
41 <script src="js/jquery-1.7.min.js"></script> 424 <td>なし（物理マシン）</td>
42 425 </tr>
43 <!-- S6 JS --> 426 </table>
44 <script src="js/jquery.slideshow.js"></script> 427 <small>
45 <script src="js/jquery.slideshow.counter.js"></script> 428 <p style="">並列環境</p>
46 <script src="js/jquery.slideshow.controls.js"></script> 429 </small>
47 <script src="js/jquery.slideshow.footer.js"></script> 430 <table style="font-size: 0.7em; margin-top:-20px; ">
48 <script src="js/jquery.slideshow.autoplay.js"></script> 431 <tr>
49 <script> 432 <th></th><th>VMWareクラスタ</th><th>KVMクラスタ</th>
50 $(document).ready( function() { 433 </tr>
51 Slideshow.init(); 434 <tr>
52 435 <td>台数</td><td>48</td><td>12</td>
53 // Example 2: Start Off in Outline Mode 436 </tr>
54 // Slideshow.init( { mode: 'outline' } ); 437 <tr>
55 438 <td>CPU</td>
56 // Example 3: Use Custom Transition 439 <td>Intel(R) Xeon(R) CPU X5650@2.67GHz</td>
57 // Slideshow.transition = transitionScrollUp; 440 <td>Intel(R) Xeon(R) CPU X5650@2.67GHz</td>
58 // Slideshow.init(); 441 </tr>
59 442 <tr>
60 // Example 4: Start Off in Autoplay Mode with Custom Transition 443 <td>コア数</td>
61 // Slideshow.transition = transitionScrollUp; 444 <td>4</td>
62 // Slideshow.init( { mode: 'autoplay' } ); 445 <td>4</td>
63 } ); 446 </tr>
64 </script> 447 <tr>
65 448 <td>Memory</td>
66 <!-- Better Browser Banner for Microsoft Internet Explorer (IE) --> 449 <td>8GB</td>
67 <!--[if IE]> 450 <td>8GB</td>
68 <script src="js/jquery.microsoft.js"></script> 451 </tr>
69 <![endif]--> 452 <tr>
70 453 <td>OS</td>
71 </head> 454 <td>Fedora 16</td>
72 <body> 455 <td>Fedora 16</td>
73 456 </tr>
74 <div class="layout"> 457 <tr>
75 <div id="header"></div> 458 <td>HyperVisor</td>
76 <div id="footer"> 459 <td>VMWare ESXi</td>
77 <h1>分散データベースJungleの実装</h1> 460 <td>KVM (Linux Fedora 16)</td>
78 <h2>琉球大学大学院　情報工学専攻 修士2年次　大城信康</h2> 461 </tr>
79 </div> 462 </table>
80 </div> 463
81 464 </article>
82 <div class="presentation"> 465
83 466
84 <!-- add slides here; example --> 467 <article>
85 468 <h3>
86 <div class='slide cover'> 469 実験1:単体サーバへの負荷
87 <h1>分散データベースJungleに関する研究</h1> 470 </h3>
88 <ul> 471 <p style="text-align:center;">
89 <p>琉球大学　大城信康 472 <img style="width:80%;" src="./images/cluster_request_server.png">
90 <br> 473 </p>
91 14 Jan 2013 474 </article>
92 </p> 475
93 </ul> 476 <article>
94 </div> 477 <h3>
95 478 実験1：単体サーバへの負荷（読み込み）
96 <div class='slide'> 479 </h3>
97 <h1>研究の背景と目的</h1> 480 <small>
98 <ul> 481 <p>ブレードサーバ一台に対して複数のクライアントからの負荷</p>
99 <li>スマートフォンやタブレット端末の普及により、大量のデータを扱うウェブサービスが現れてきている。</li> 482 <table style="text-align:center;font-size:0.7em;">
100 <li>しかしそれに伴い、サーバサイド側への負荷も増大しウェブサービスがダウンする事態が出てきている。</li> 483 <tr>
101 <li>そのため、スケーラビリティはウェブサービスにおいて重要な性質の1つとなっている。</lii> 484 <td><img style="height:350px;" src="./images/bldsv12_read_bench.png"/></td>
102 <li>スケーラビリティとは、ある複数のノードから構成される分散ソフトウェアがあるとき、その分散ソフトウェアに対して単純にノード 485 </tr>
103 を追加するだけで性能を線形に上昇させることができる性質である</li> 486 <tr>
104 <li>スケーラビリティのあるプログラムについてアーキテクチャの設計から行った</li> 487 <th style="text-align:center;">読み込みの実験結果</th>
105 </ul> 488 </tr>
106 </div> 489 </table>
107 490 <p style="margin-top:0px;">JungleがCassandraより良い結果を示している</p>
108 <div class='slide'> 491 <p style="margin-top:-20px;">クライアントが55台のときのJungleの最速とCassandraの最遅は3倍近く離れている</p>
109 <h1>研究の背景と目的</h1> 492 </small>
110 493 </article>
111 <ul> 494
112 <li>当研究室では非破壊的木構造を用いたデータベースである Jungle を開発している</li> 495 <article>
113 <li>非破壊的木構造とは、データの編集の際に一度木構造として保存したデータには触れず、新しく木構造を作成してデータの編集を行うこと</li> 496 <h3>
114 <li>Jungle は分散データベースとして設計・実装されているが、分断耐性や永続性といった部分の実装がまだ 497 実験1：単体サーバへの負荷（書き込み）
115 行われていない</li> 498 </h3>
116 <li>本研究では、Jungle を用いてスケーラビリティをもつアーキテクチャの追求を行う</li> 499 <small>
117 </ul> 500 <p>ブレードサーバ一台に対して複数のクライアントからの負荷</p>
118 </div> 501 <table style="text-align:center;font-size:0.7em;">
119 502 <tr>
120 <div class='slide'> 503 <td><img style="height:350px;" src="./images/bldsv12_write_bench.png"/></td>
121 <h1>今週の作業</h1> 504 </tr>
122 <ul> 505 <tr>
123 <li>論文の執筆</li> 506 <th style="text-align:center;">書き込みの実験結果</th>
124 <li>ベンチマーク測定環境の構築</li> 507 </tr>
125 </ul> 508 </table>
126 </div> 509 <p>読み込み同様Jungleのほうが良い結果を示している</p>
127 510 <p>読み込みよりJungleとCassandraの結果が重なる部分が減っている</p>
128 <div class='slide'> 511 </small>
129 <h1>ベンチマーク測定環境の構築</h1> 512 </article>
130 <ul> 513
131 <li>csクラスタ(VM)上で掲示板プログラムを走らせ、ベンチマークをとる</li> 514 <article>
132 <li>Jungle と Cassandra 両方を走らせる環境の構築を行った</li> 515 <h3>
133 <h2>問題が発生</h2> 516 実験1の考察
134 <li>Cassandra でConsistencyLevelをいじってもデータを伝搬してくれない</li> 517 </h3>
135 <li>Jungle の分散結果が良くならない。圧倒的に遅い。Cassandra の結果の2倍3倍遅くなる</li> 518 <p>読み込み、書き込みともにJungleの性能がよく。平均だけみても2倍以上早い部分もある。</p>
136 </ul> 519 <p>特に書き込みに関してはクライアントの数が増えるにつれ差が開いている。</p>
137 </div> 520 <!--
138 521 <p>要因の1つとしてCassandraはディスクへ書き込みを行うが、Jungleは全てのデータをオンメモリで扱っていることもある</p>
139 <div class='slide'> 522 <p>これはある意味当然だが、もう1つ要因をあげられる</p>
140 <h1>問題解決</h1> 523 -->
141 <ul> 524 <p>これはJungleが全体的にロックが少ないことが要因としてあげられる。</li>
142 <li>Cassandra はConsistencyLevelとは別にReplication factorというレプリケーション(複製)をとるノードの数を指定する項目がある</li> 525 <p>Jungleは非破壊でデータの保持をするため、読み込みは自由に行える。書き込み時には木のコピーをとりルートノードを入れ替える
143 <li>Cassandra のConsistencyLevelはこのReplication factorの数に対して行われる</li> 526 ときのみロックが発生する。</p>
144 <ul> 527 </article>
145 <li>Replication factorをNとした場合、ConsistencyLevelをALLにするとこのNの数だけノードに書き込まれるのをまつ</li> 528
146 <li>Replication factorをノードの全体の数に合わせてあげるとよい</li> 529 <article>
147 <li>Replication factorの設定はv1.1くらいまでは設定ファイルでできるが、v1.2からはキースペース生成時に設定するか 530 <h3>
148 ./bin/cassandra-cli を使ってCassandraのデータにアクセスして変更する必要がある</li> 531 実験2:分散環境下における負荷
149 </ul> 532 </h3>
150 <br> 533 <p style="text-align:center;">
151 <li>Jungle の結果が悪い原因</li> 534 <img style="width:80%;" src="./images/clients_request_servers.png">
152 <ul> 535 </p>
153 <li>Javaのメモリの量を増やす設定をいれることで解決</li> 536 </article>
154 </ul> 537
155 </ul> 538 <article>
156 </div> 539 <h3>
157 540 実験2：分散環境下における読み込み
158 <div class='slide'> 541 </h3>
159 <h1>単体・複数ノードへの負荷</h1> 542 <small>
160 <ul> 543 <table style="text-align:center;font-size:0.7em;">
161 <li>クライアント数最大12台。各クライアント5000回のリクエストを出す</li> 544 <tr>
162 </ul> 545 <td><img style="height:350px;" src="./images/distributed_read_bench.png">
163 <img src="./images/write_bench.png"> 546 </tr>
164 </div> 547 <tr>
165 548 <th style="text-align:center;">読み込みの実験結果</th>
166 <div class='slide'> 549 </tr>
167 <h1>ベンチマーク改良</h1> 550 </table>
168 <ul> 551 <p>CassandraはConsistency Level ONE(赤)とQUORUM(緑)両方を測定</p>
169 <li>Jungleの結果をbldsvで起動した時に近い結果になることが確認できた</li> 552 <p>Jungleは1秒から5秒をキープ</p>
170 <li>Cassandra も Jungle のグラフも横ばいになっている。クライアント側からの負荷が足りない。</li> 553 </small>
171 <li>Cassandra の ConsystencyLevel をいじっても結果が変わらないのも負荷が足りないから？</li> 554 </article>
172 <h2>次の課題</h2> 555
173 <li>クライアント側はKVMで動かしていて現在12台しか無い</li> 556 <article>
174 <li>負荷をかけるプログラムをforkすることでプロセスを増やして負荷を増やすよう改良する必要がある</li> 557 <h3>
175 <br> 558 実験2：分散環境下における書き込み
176 <li>論文書こう</li> 559 </h3>
177 </ul> 560 <small>
178 </div> 561 <table style="text-align:center;font-size:0.7em;">
179 562 <tr>
180 <div class='slide'> 563 <td><img style="height:350px;" src="./images/distributed_write_bench.png">
181 <h1>今後の作業</h1> 564 </tr>
182 <ul> 565 <tr>
183 <li>修論作成</li> 566 <th style="text-align:center;">書き込みの実験結果</th>
184 <li>ベンチマークプログラム作成</li> 567 </tr>
185 </ul> 568 </table>
186 </div> 569 <p>CassandraはConsistency Level ONE(赤)とQUORUM(緑)両方を測定</p>
187 </div> <!-- presentation --> 570 <p>Jungleは5.5秒から7.3秒をキープ</p>
188 </body> 571 </small>
572 </article>
573
574
575 <article>
576 <h3>
577 実験2の考察
578 </h3>
579 <p>こちらもJungleがCassadraより良い結果を示した。実験1よりも差がでている。</p>
580 <p>Jungleのグラフが横ばいになっていることに注目したい。</p>
581 <!--
582 <p>Cassandraはノードの数が増えるに従いデータを取りにいくノードも増えることでレスポンスが遅くなっている。</p>
583 -->
584 <p>Jungleはリクエストに対し手元にあるデータを返す。そのためノードの数が増えてもレスポンスの早さを維持できる。</p>
585 <p>Cassandraはデータを持っている数台のノードに読み込みに行くという作業が入るためJungleより遅くなってしまう</p>
586 <p>Jungleは同期を取らないためデータ全体の整合性は落ちるが、分散管理システムを参考にした設計の有用性を示すことができた。</p>
587 </article>
588
589
590 <article>
591 <h3>
592 まとめ
593 </h3>
594 <p>本研究では非破壊的木構造Jungleに分散データベースの実装を行った</p>
595 <p>非破壊的木構造における利点を述べ、スケーラビリティの高い分散版管理システムとの類似性を述べた</p>
596 <p>Mergeアルゴリズムの1つとして掲示板プログラムにおけるMergeについて設計・実装を行った</p>
597 <p>性能比較の実験のためJungle、Cassandraで利用できる簡易掲示板の作成を行った</p>
598 <p>実験は単体サーバと分散環境下において行い、どちらともCassandraよりよい結果をえることができた</p>
599 </article>
600
601 <!--
602 <article>
603 <h3>
604 今後の課題
605 </h3>
606 <p>push/pull方式による分断耐性の実装</p>
607 <ul>
608 <li>現実装ではJungleはデータ編集が行われた際に発生するログを非同期で他サーバノードへと送信している</li>
609 <li>だがこの方法では接続が切れた際に再接続を行ったノードが全てのデータをとることができない</li>
610 <li>そこで非同期とは別に同期をとり他ノードとに差分となるデータを送るということを行いたい</li>
611 <li>これは分散管理システムにおけるpush/pull APIにあたる</li>
612 </ul>
613 </article>
614 -->
615 <article>
616 <h3>
617 今後の課題
618 </h3>
619 <p>データ分割の実装</p>
620 <ul>
621 <li>現在の実装は全てのノードで全てのデータを持たせている</li>
622 <li>この方法ではメモリの使用量が高いこととネットワーク帯域への負荷が懸念される</li>
623 <li>ノード単位で保持するデータを分ける実装が必要</li>
624 <li>その場合、木構造単位でノード毎にデータを分ける</li>
625 <li>持っていないデータの要求が来た場合は、データを持っているノードに取りに行くようにする</li>
626 </ul>
627 </article>
628
629 <article>
630 <h3>
631 今後の課題
632 </h3>
633 <p>Mergeアルゴリズムの設計</p>
634 <ul>
635 <li>JungleはMergeを使うことで更新データ衝突の問題を解決する。</li>
636 <li>今回実装した掲示板プログラムにおけるMergeは単純なもの。</li>
637 <li>他のアプリケーションではどのようにMergeを行うのか考察が必要。</li>
638 </ul>
639 </article>
640
641
642 <article>
643 <h3>
644 今後の課題
645 </h3>
646 <p>過去のデータの掃除について</p>
647 <ul>
648 <li>Jungleは非破壊でデータを保持するため過去のメモリの使用量が大きい</li>
649 <li>ある程度の単位で過去のデータの掃除を行いたい</li>
650 <li>そのためにはどのノードがどのデータを持っているかという情報を扱うことが必要</li>
651 <li>どれくらいデータが古くなると掃除を行うか判断が必要</li>
652 </ul>
653 </article>
654
655 <article>
656 <h3>
657 </h3>
658 <p></p>
659 <ul>
660 </ul>
661 </article>
662
663 <article>
664 <h3>
665 Mergeは必ずできるのか
666 </h3>
667 <p>Mergeを必ず行うことは難しい</p>
668 <p>例えば、更新するデータが画像だった場合、2つの画像のデータから新しい画像を作るわけにはいかない。</p>
669 <p>後に更新したものを優先するといった方法をとるか、ユーザの選択に委ねるしかない。</p>
670 </article>
671
672
673 <article>
674 <h3>
675 分散Key-ValueストアCassandraの特徴
676 </h3>
677 <small style="line-height:30px;">
678 <p>ring型トポロジーを形成。ring上にはHash値があり、書き込むデータのキーのハッシュ値により書き込むノードを決定</p>
679 <p>1つのデータの複製を最大何とるかというReplication factorの設定がある。</p>
680 <p>Consistency Levelというデータの読み書きの際に何台のノードから読み書きするかを決定できる</p>
681 <p>Consistency LevelにはONE,QUORUM,ALLがある。QUORUMはReplication factorの数/2+1 のノードに読み書きする。</p>
682 </small>
683 <p>
684 <img style="margin-top:-30px;" src="./images/consistency_quorum.png">
685 </p>
686 </article>
687
688
689 <article>
690 <h3>
691 Jungleの分散設計:分散版管理システム
692 </h3>
693 <p>Jungleは分散設計を行うにあたってGitやMercurialといった分散版管理システムを意識している</p>
694 <p style="margin-top:-10px;">分散版管理システムとは多人数によるソフトウェア開発において変更履歴を管理するシステム</p>
695 <p style="margin-top:-10px;">分散版管理システムは次の特徴とAPIを持つ</p>
696 <ul>
697 <li>開発者それぞれがリポジトリのクローンしてローカルに持ち、開発はローカルのリポジトリを通すことで行われる</li>
698 <li>ローカルのリポジトリは独立に存在し、サーバ上にある他人のリポジトリから変更履歴をとることができる。また自身の変更履歴を伝えることもできる</li>
699 <li>データ更新時に先に別の更新が入っていた(衝突)場合はMergeによりデータの整合性をとる</li>
700 </ul>
701 </article>
702
703 <article>
704 <h3>
705 Jungleの分散設計:分散版管理システム
706 </h3>
707 <p>分散版管理システムAPI</p>
708 <ul style="margin-top:-20px;">
709 <li>commit:データに変更を加えたことをリポジトリに登録</li>
710 <li>push:ローカルのリポジトリで行った変更履歴を他のリポジトリへまとめて送る</li>
711 <li>pull:他のリポジトリからの変更履歴をまとめて受け取る</li>
712 </ul>
713 <p style="text-align:center;">
714 <img style="height:200px;" src="./images/distributed_repository.png">
715 </p>
716 <small>
717 <p>分版版管理システムはリポジトリが壊れても別のリポジトリよりデータを復旧できることと、push/pullそれとMergeによる整合性
718 の確保で、高いスケーラビリティを持っている</p>
719 </small>
720 </article>
721
722 <article>
723 <h3>
724 Jungleの分散設計:分散版管理システム
725 </h3>
726 <p>Jungleと分散版管理システムには似通った点がある</p>
727 <li>どちらもデータのコピーが自由</li>
728 <li>データ更新しても過去のデータに影響を与えない</li>
729 <br/>
730 <p><font color="red">同じAPIを実装することで、分散版管理システムと同じく高いスケーラビリティが期待できる</font></p>
731 <p>具体的には</p>
732 <ul>
733 <li>pushやpullによる定期的なデータの更新</li>
734 <li>Mergeによる更新データ衝突の解決</li>
735 </ul>
736 </article>
737
738
739 </section>
740
741 </body>
189 </html> 742 </html>