Mercurial > hg > Members > nobuyasu > master-presen > presen20140114
view index.html @ 5:3020e4fb1793
Writed description non destructive tree
author | Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Sun, 02 Feb 2014 17:06:42 +0900 |
parents | 916cd38dd037 |
children | 10306206458f |
line wrap: on
line source
<!DOCTYPE html> <html> <head> <meta charset='utf-8'> <title>分散データベース Jungle に関する研究</title> <script src='slides.js'></script> <style media='screen,projection'> /**** * Add your styles here. */ body { font-size: 175%; } .step { color: silver; } /* or hide next steps e.g. .step { visibility: hidden; } */ .slide { font-family: 'Open Sans', Arial, sans-serif; color: rgb(102, 102, 102); text-shadow: 0 1px 1px rgba(0, 0, 0, .1); } .slide h1, .slide h2, .slide h3 { color: rgb(51, 51, 51); } .slide pre { font-family: 'Droid Sans Mono', 'Courier New', monospace; font-size: 80%; padding: 5px 10px; margin-top: 40px; margin-bottom: 40px; color: black; background: rgb(240, 240, 240); border: 1px solid rgb(224, 224, 224); box-shadow: inset 0 2px 6px rgba(0, 0, 0, .1); overflow: hidden; } .slide code { font-family: 'Droid Sans Mono', 'Courier New', monospace; color: black; } .slide h3 { margin-top:-15px; } </style> </head> <body> <section class='slides'> <!-- Add your slides here. Delete or comment out the slides below. --> <article class='cover'> <h1> 分散データベース Jungle に関する研究 <br> </h1> <p> 大城 信康 <br> Feb 3, 2013 </p> </article> <article> <h3> 概要 </h3> <small> <p>ウェブサービスにとってデータベースは必須であり、ウェブサービスの規模に比例してデータベースへの負荷も高まる。</p> <p>データベースの処理能力の高さはそのままウェブサービスの質に繋がるため、データベースのスケーラビリティの確保は重要である。</p> <p>スケーラビリティ確保の方法としてデータ分散があるが、分散する方法により性能も変わってくる。</p> <p>我々は、非破壊的構造を用いてデータを表現するデータベースJungleの開発を行った。</p> <p>非破壊的木構造データベースJungleに分散実装を行い、その評価を行い、分散データベースCassandraよりよい性能を得ることができた。</p> </small> </article> <article> <h3> ウェブサービスにおけるデータベースの重要性 </h3> <p>ウェブサービスへの負荷が高まることは、データベースへの負荷が高まることでもある。</p> <p>データベースの性能が低ければ負荷に耐え切れずサービスはダウンする</p> <p style="text-align:center;"> <img src="./images/service_down.png"> </p> <p>そのため、データベースにはスケーラビリティが必要</p> </article> <article> <h3> スケーラビリティとは </h3> <p>システムが負荷の増大に対して柔軟に拡張して対応できる性質</p> <p>主に次の2つの方法によりシステムはスケールされる</p> <ul> <li><font color="blue">スケールアップ</font>:<br/>高価な単一マシンによる性能アップ</li> <br/> <li><font color="red">スケールアウト</font>:<br/>汎用的なマシンを複数台用意することで性能アップ</li> </ul> <p>分散システムにおいては<font color="red">スケールアウト</font>によりスケーラビリティを高める</p> </article> <article> <h3> コンテンツマネジメントシステム(CMS) </h3> <p></p> <p></p> <p></p> </article> <article> <h3> </h3> <p></p> <p></p> </article> <article> <h3>非破壊的木構造データベースJungle</h3> <p>JungleはスケーラビリティのあるCMSの設計を目指して当研究室で開発されているデータベース</p> <p>データを木構造で、さらに非破壊で保持する</p> <br/> <p>まず、破壊的木構造と非破壊的木構造について説明する</p> </article> <article> <h3>破壊的木構造</h3> <p>木構造の通常のデータ表現</p> <p>破壊的木構造は、木構造により保持しているデータの編集をデータを直接書き換えることで行う</p> <p style="text-align:center;"> <img style="height:300px;" src="./images/destructive_tree_slide.png"> </p> </article> <article> <h3>破壊的木構造</h3> <p>破壊的木構造ではデータの編集中にそのデータを読むことができない</p> <p>編集が完了するまでまたなければならない</p> <p style="text-align:center;"> <img style="width:500px;" src="./images/destructive_tree_demerit.png"> </p> </article> <article> <h3> 非破壊的木構造 </h3> <p>非破壊的木構造は一度作成したデータは変更しない</p> <p>新しい木構造を作成することでデータの編集を行う</p> <p style="text-align:center;"> <img style="height:300px;" src="./images/non_destructive_tree_slide.png"> </p> <p></p> </article> <article> <h3> 非破壊的木構造におけるデータ編集 </h3> <p>目的とするノード5ををコピーして内容を編集する。ノード100となる</p> <p>ルートノードから目的のノード5までに続くルートノードとノード2のコピーとりノード100と繋げる</p> <p style="text-align:center;"> <img style="width:700px;" src="./images/non_destructive_tree_edit.png"> </p> </article> <article> <h3> 非破壊的木構造におけるデータ編集と読み込み </h3> <p>新しく作成したルートノードに変更を加えていないノードへの参照を持たせる。新しい木構造のデータができる</p> <p>最新のルートノードの登録を新しく作成した側のルートノードへと登録する</p> <p style="text-align:center;"> <img style="width:700px;" src="./images/non_destructive_tree_edit2.png"> </p> </article> <article> <h3> 非破壊的木構造の利点 </h3> <p>非破壊的木構造は通常の木構造である破壊的木構造に比べ、以下のような利点を持つ</p> <ul> <li>一度作成したデータは変更されない</li> <li>データが変更されないため自由にコピーを作ることができる(いつでも読み込みが可能)</li> <li>ロックがすくない。ロックが必要なのは最新のルートノードを登録するときだけ</li> </ul> <p>ロックが少なく、いつでもコピーが可能なことから、非破壊的木構造はスケーラブルなシステムに有用となる</p> </article> <article> <h3> </h3> <p></p> <p></p> </article> <article> <h3> 非破壊的木構造データベースJungleの評価 </h3> <p>分散データベースとしてJungleの性能を評価する。</p> <p>分散Key-ValueデーターべースCassandraと比較を行う。</p> <p>比較方法は、Jungle, Cassandra をそれぞれバックエンドとした簡易掲示板を作成する。</p> <p>掲示板に対してHTTP Requestで並列に読み込みと書き込みの負荷をかけ計測する。</p> </article> <article> <h3> 比較方法 </h3> <p>実験は以下の2つを行う</p> <small> <table style="font-size: 0.7em; width:100%;"> <tr> <th>実験1:サーバ単体への負荷</th><th>実験2:複数台のサーバに対する負荷</th> </tr> <tr> <td><img style="width:400px;" src="./images/cluster_request_server.png"></td> <td><img style="width:400px;" src="./images/clients_request_servers.png"></td> </tr> <tr> <td><p>複数のクライアントから単体のサーバへ負荷をかける</p></td> <td><p>複数のクライアントから複数のサーバへ負荷をかける</p></td> </tr> </table> <p>サーバ単体の性能と, 分散環境下における性能の2つを調べる。</p> </small> </article> <article> <h3> 実験に使用するブレードサーバの仕様 </h3> <p>実験1:単体サーバへの負荷で使用するサーバ側</p> <table style="font-size: 0.7em;"> <tr> <th></th><th>ブレードサーバ</th> </tr> <tr> <td>CPU</td> <td>Intel(R) Xeon(R) CPU X5650@2.67GHz</td> </tr> <tr> <td>コア数</td> <td>24</td> </tr> <tr> <td>Memory</td> <td>132GB</td> </tr> <tr> <td>OS</td> <td>Fedora 16</td> </tr> <tr> <td>HyperVisor</td> <td>なし(物理マシン)</td> </tr> </table> </article> <article> <h3> 実験に使用する並列環境の仕様 </h3> <small> <p>台数を増やすため学科の提供するVM48台とは別にKVMより12台用意し合計60台用意した。</p> <p>KVMはクライアントとしてだけ使用する。</p> <p>並列環境は実験1ではクライアントとして利用し、実験2ではクライアントとサーバ両方で利用する。</p> </small> <table style="font-size: 0.7em"/> <tr> <th></th><th>VMWareクラスタ</th><th>KVMクラスタ</th> </tr> <tr> <td>台数</td><td>48</td><td>12</td> </tr> <tr> <td>CPU</td> <td>Intel(R) Xeon(R) CPU X5650@2.67GHz</td> <td>Intel(R) Xeon(R) CPU X5650@2.67GHz</td> </tr> <tr> <td>コア数</td> <td>4</td> <td>4</td> </tr> <tr> <td>Memory</td> <td>8GB</td> <td>8GB</td> </tr> <tr> <td>OS</td> <td>Fedora 16</td> <td>Fedora 16</td> </tr> <tr> <td>HyperVisor</td> <td>VMWare ESXi</td> <td>KVM (Linux Fedora 16)</td> </tr> </table> </article> </article> <article> <h3> 実験1:単体サーバへの負荷 </h3> <p style="text-align:center;"> <img style="width:80%;" src="./images/cluster_request_server.png"> </p> </article> <article> <h3> 実験1:単体サーバへの読み込み </h3> <small> <p>ブレードサーバ一台に対して複数のクライアントからの負荷</p> <table style="text-align:center;font-size:0.7em;"> <tr> <td><img style="height:350px;" src="./images/bldsv12_read_bench.png"/></td> </tr> <tr> <th style="text-align:center;">読み込みの実験結果</th> </tr> </table> </small> </article> <article> <h3> 実験1:単体サーバへの書き込み </h3> <small> <p>ブレードサーバ一台に対して複数のクライアントからの負荷</p> <table style="text-align:center;font-size:0.7em;"> <tr> <td><img style="height:350px;" src="./images/bldsv12_write_bench.png"/></td> </tr> <tr> <th style="text-align:center;">書き込みの実験結果</th> </tr> </table> </small> </article> <article> <h3> 実験1の考察 </h3> <p>読み込み、書き込みともにJungleの性能がよく。最大2倍以上早い部分もある.</p> <p>特に書き込みに関してはクライアントの数が増えるにつれ差が開いている.</p> <!-- <p>要因の1つとしてCassandraはディスクへ書き込みを行うが、Jungleは全てのデータをオンメモリで扱っていることもある</p> <p>これはある意味当然だが、もう1つ要因をあげられる</p> --> <p>これはJungleが全体的にロックが少ないことが要因としてあげられる</li> <p>Jungleは非破壊でデータの保持をするため、読み込みは自由に行える。書き込み時には木のコピーをとりルートノードを入れ替える ときのみロックが発生する。</p> </article> <article> <h3> 実験2:複数台のサーバに対する負荷 </h3> <p style="text-align:center;"> <img style="width:80%;" src="./images/clients_request_servers.png"> </p> </article> <article> <h3> 実験2:分散環境下における読み込み </h3> <small> <table style="text-align:center;font-size:0.7em;"> <tr> <td><img style="height:350px;" src="./images/distributed_read_bench.png"> </tr> <tr> <th style="text-align:center;">読み込みの実験結果</th> </tr> </table> <p>CassandraはConsistency Level ONE(赤)とQUORUM(緑)両方を測定</p> <p>Jungleは1秒から5秒をキープ</p> </small> </article> <article> <h3> 実験2:分散環境下における書き込み </h3> <small> <table style="text-align:center;font-size:0.7em;"> <tr> <td><img style="height:350px;" src="./images/distributed_write_bench.png"> </tr> <tr> <th style="text-align:center;">書き込みの実験結果</th> </tr> </table> <p>CassandraはConsistency Level ONE(赤)とQUORUM(緑)両方を測定</p> <p>Jungleは5.5秒から7.3秒をキープ</p> </small> </article> <article> <h3> 実験2の考察 </h3> <p>こちらもJungleがCassadraのより良い結果を示した。実験1よりも差がでている。</p> <p>Jungleのグラフが横ばいになっていることに注目したい。</p> <p>Cassandraはノードの数が増えるに従いデータを取りにいくノードも増えることでレスポンスが遅くなっている。</p> <p>Jungleはリクエストに対し手元にあるデータを返す。そのためノードの数が増えてもレスポンスの早さを維持できる。</p> <p>Jungleは同期を取らないためデータ全体の整合性は落ちるが、分散管理システムを参考にした設計の有用性を示すことができた。</p> </article> <article> <h3> まとめ </h3> <p>本研究では非破壊的木構造Jungleに分散データベースの実装を行った</p> <p>非破壊的木構造における利点を述べ、</p> <p>性能比較の実験のためJungle、Cassandraで利用できる簡易掲示板の作成を行った</p> <p>実験は単体サーバと分散環境下において行い、どちらともCassandraよりよい結果をえることができた</p> <p>特に分散環境下においての実験ではConsistency Level QUORUMのCassandraに倍以上の</p> </article> <article> <h3> 今後の課題 </h3> <p>push/pull方式による分断耐性の実装</p> <ul> <li>現実装ではJungleはデータ編集が行われた際に発生するログを非同期で他サーバノードへと送信している</li> <li>だがこの方法では接続が切れた際に再接続を行ったノードが全てのデータをとることができない</li> <li>そこで非同期とは別に同期をとり他ノードとに差分となるデータを送るということを行いたい</li> <li>これは分散管理システムにおけるpush/pull APIにあたる</li> </ul> </article> <article> <h3> 今後の課題 </h3> <p>データ分割の実装</p> <ul> <li>現在の実装は全てのノードで全てのデータを持たせている</li> <li>この方法ではメモリの使用量が高いこととネットワーク帯域への負荷が懸念される</li> <li>ノード単位で保持するデータを分ける実装が必要</li> <li>その場合、木構造単位でノード毎にデータを分ける</li> <li>持っていないデータの要求が来た場合は、データを持っているノードに取りに行くようにする</li> </ul> </article> <article> <h3> 今後の課題 </h3> <p>Mergeアルゴリズムの設計</p> <ul> <li>JungleはMergeを使うことで更新データ衝突の問題を解決する</li> <li>今回実装した掲示板プログラムにおけるMergeは単純なもの</li> <li>他のアプリケーションではどのようにMergeを行うのか</li> </ul> </article> <article> <h3> 今後の課題 </h3> <p>過去のデータの掃除について</p> <ul> <li>Jungleは非破壊でデータを保持するため過去のメモリの使用量が大きい</li> <li>ある程度の単位で過去のデータの掃除を行いたい</li> <li>そのためにはどのノードがどのデータを持っているかという情報を扱うことが必要</li> <li>どれくらいデータが古くなると掃除を行うか判断が必要</li> </ul> </article> <article> <h3> </h3> <p></p> <ul> <li></li> <li></li> <li></li> </ul> </article> </section> </body> </html>