Mercurial > hg > Papers > 2013 > nobuyasu-jssst
view presen/index.html @ 55:307c87617e62 default tip
add slide
| author | Nobuyasu Oshiro <dimolto@cr.ie.u-ryukyu.ac.jp> |
|---|---|
| date | Wed, 11 Sep 2013 10:21:42 +0900 |
| parents | edc3972b949c |
| children |
line wrap: on
line source
<!DOCTYPE html> <html> <head> <style type="text/css"> .center { margin-left: auto; margin-right: auto; text-align: center; } </style> <title>Presentation</title> <meta charset='utf-8'> <script src='./slides.js'></script> </head> <style> /* Your individual styles here, or just use inline styles if that’s what you want. */ </style> <body style='display: none'> <section class='slides layout-regular template-default'> <!-- Your slides (<article>s) go here. Delete or comment out the slides below. --> <article> <h1><font size=10em> Data Segment の分散データベースへの応用 </font> </h1> <p> 琉球大学 大城信康 <br> 11 Sep 2013 </p> </article> <article> <h3>研究の目的と背景</h3> <ul> <li>当研究室では並列分散フレームワーク Alice を開発している</li> <li>Alice はタスクを Code Segment, データを Data Segment という単位で扱うプログラミングスタイルを提供する</li> <li>また, 当研究室では非破壊的木構造を用いたデータベースである Jungle を開発している</li> <li>非破壊的木構造とは, データの編集の際に一度木構造として保存したデータには触れず, 新しく木構造を作成してデータの編集を行うこと</li> <li>Jungle は分散データベースとして設計されているが, 今のところシングルサーバ上でしか動かない</li> <li><font color="red">本研究では, Jungle に Alice を用いて分散データベースとしての実装を行った. また例題を作成し評価を行う.</font></li> </ul> </article> <article> <h3>Alice : Code Segment </h3> <ul> <li>Alice : 当研究室で開発している並列分散フレームワーク</li> <li>Data Segment と Code Segment による並列・分散プログラミングを提供</li> <p class="center"> <img src="./pic/dsandcs.png"> </p> <li>Code Segment : 並列プログラミングにおけるタスク</li> <li>Data Segment を受け取り計算を行うコード</li> <li>Data Segment の Key を登録することで, 登録された Data Segment が準備されしだい実行される</li> </ul> </article> <article> <h3>Data Segment</h3> <ul> <li>計算に必要なデータ</li> <li>Alice は Data Segment を文字列の Key で管理</li> <li>Key 毎にリストが用意され, put された順番で Data Segment は取り出される</li> <li>Data Segment Manager(DSM) により管理される</li> <p class="center"> <img src="./pic/put.png"> <li>Data Segment のデータ表現にはシリアライズライブラリーの MessagePack が使われている</li> </p> </ul> </article> <!-- <article> <h3>Code Segment</h3> <ul> <li>並列プログラミングにおけるタスク</li> <li>Data Segment を受け取り計算を行うコード</li> <li>Code Segment は計算に使う Data Segment の Key を登録してその Key にあたる Data Segment が用意され次第処理が実行される</li> <p class="center"> <img src="./pic/dsandcs.png"> </p> <li>計算を行った結果を新たな Data Segment として出力する</li> </ul> </article> --> <!-- <article> <h3>Alice上でのデータ表現:MessagePack</h3> <ul> <li>Data Segment のデータ表現には MessagePack を利用</li> <li>Messagepack はバイナリをベースにしたシリアライズライブラリー</li> <li>独自のクラスでも @Message アノテーションを付けることでシリアライズ可能<br> (その際にはシリアライズできる型のみのフィールドをもつこと)</l> <li>MessagePack を使用することで Alice 以外のプログラムでの Data Segment を扱うことが可能になる</li> </ul> </article> --> <article> <h3>非破壊的木構造を用いたデータベース Jungle</h3> <ul> <li>当研究室で開発中のデータベース</li> <li>データを木構造かつ、非破壊で保持することが特徴</li> </ul> </article> <article> <h3>破壊的木構造</h3> <ul> <li>木構造で保持するデータを直接書き換える</li> <li>編集を行う際にロックをかける必要がある</li> <p class="center"> <img src="./pic/destructive_tree.png"> </p> <li>データを受け取ろうと木を走査するスレッドは編集時には書き換えの終了をまつ必要がある</li> <!-- <li><font color=red>ロックが多いためスケールしにくい</font></li> --> </ul> </article> <article> <h3>非破壊的木構造</h3> <ul> <li>一度作成したデータの破壊は行わない</li> <li>データの編集は, 編集が行われるノードまでをルートからコピーを行い新しい木構造を作ることで行う</li> <p class="center"> <img src="./pic/non_destructive_tree.png"> </p> <li>非破壊的木構造ではデータの編集中に走査をすることが可能なためスケールしやすいと考えている</li> </ul> </article> <article> <h3>Jungle におけるデータ編集: API</h3> <ul> <li>Jungle ではデータの編集を行う Editor を提供している</li> <li>Editor が提供するデータ編集のメソッドは次のようなものがある</li> <ul> <li>Nodeの追加を行う<br><font color=blue>addNewChildAt(NodePath _path, int _pos)</font></li> <li>Nodeの削除を行う<br><font color=blue>deleteChildAt(NodePath _path, int pos)</font></li> <li>Nodeにattributeを追加する<br><font color=blue>putAttribute(NodePath _path, String _key,<br> ByteBuffer _value)</font></li> <li>Nodeのattributeを削除する<br><font color=blue>deleteAttribute(NodePath _path, String _key)</font></li> </ul> </ul> </article> <article> <h3>Jungle におけるデータ編集: NodePath</h3> <ul> <li>NodePath は root から編集を行う Node までの道を示す</li> <li>例えば NodePath が -1,1,2,3 の場合は次の Node を示す</li> <p class="center"> <img src="./pic/nodepath.png"> </p> <li>Jungle におけるデータ編集はこの NodePath を Editor が提供する API に渡すことで行われる</li> </ul> </article> <article> <h3>TreeOperationLog</h3> <ul> <li>Editor による編集の命令はある程度のAPIの塊で扱われる</li> <li>この編集の塊を TreeOperatinLog という</li> <li>今回実装した掲示板では, 書き込み時に次のような TreeOperaitonLog が作られる</li> <pre> [APPEND_CHILD:<-1>:pos:1] [PUT_ATTRIBUTE:<-1,1>:key:author,value:oshiro] [PUT_ATTRIBUTE:<-1,1>:key:mes,value:hello] [PUT_ATTRIBUTE:<-1,1>:key:key,value:hoge] [PUT_ATTRIBUTE:<-1,1>:key:timestamp,value:1378758973] </pre> <li>大文字の英字は実行した API を示す</li> <li><>で囲まれた数字は NodePath を示す</li> <li>key と value は attribute に格納する内容を示す</li> </ul> </article> <article> <h3>Alice を用いた Jungle の分散実装</h3> <ul> <li>Alice により TreeOperationLog を Data Segment として扱うことで行う</li> <li>他Nodeがその他Nodeの Data Segment にアクセスを行う</li> <li>アクセスできるようにするためには次の作業が必要</li> <ul> <li>トポロジーの形成</li> <li>TreeOperationLog を MessagePack によりシリアライズ</li> <li>TreeOperationlog を扱う Data Segment の作成</li> </ul> </ul> </article> <!-- <article> <h3>トポロジーの形成</h3> <ul> <li>Alice ではトポロジー設定用ファイルに従いノード同士を接続させる</li> <li>5ノード2分木のノードを組みたいときは次のようなファイルになる</li> <pre style="overflow:scroll; height:300px;"> digraph test { node0 -> node1 node0 -> node2 node1 -> node0 node1 -> node3 node1 -> node4 node2 -> node0 [label="child1"] [label="child2"] [label="parent"] [label="child1"] [label="child2"] [label="parent"] node3 -> node1 [label="parent"] node4 -> node1 [label="parent"] } </pre> </ul> </article> --> <article> <h3>トポロジーの形成</h3> <ul> <p class="center"> <img src="./pic/tree_topology.png"> </p> <li>トポロジーの形成は Alice の機能を用いる</li> <li>子供となるノードは parent キーにより親の DSM にアクセスできる</li> <li>親となるノードは child0, child1 キーにより子供のノードの DSM にアクセスできる</li> <li><font color=blue>Alice が提供する機能により楽にトポロジーの形成と他のノードがもつデータへのアクセスができる</font></li> </ul> </article> <article> <h3>TreeOperationLog の MessagePack によるシリアライズ</h3> <ul> <li>TreeOperationLog を Data Segment で扱うために MessagePack によるシリアライズ可能にする必要がある</li> <li>MessagePack によりクラスをシリアライズするためには, そのクラスがもつフィールド全てがシリアライズできるものでないといけない</li> <li>TreeOperationLog が保持するフィールドを全てシリアライズして保持する container を用意</li> <li>TreeOperationLogではFunctional JavaのリストでPathが保持される. MessagePack ではFunctional JavaのListがシリアライズできないため, 普通のListに変換させて Data Segment として保持させた</li> <!-- <li>TreeOperationLog は一度その container で Value 型へと変換されて保持されることで Data Segment として扱えるようにした</li> --> </ul> </article> <article> <h3>ログを扱う Data Segment</h3> <ul> <li>Data Segment にされた TreeOperaiontinLog はAlice上で log, childLog というキーで扱われる</li> <li>log にはそのノードが行った木の編集ログが入る</li> <li>子供となるノードは parent キーを使うことで親のノードの DSM にアクセスできる</li> <p class="center"> <img src="./pic/alice_topology.png"> </p> <li>子供となるノードは親の log を見張る Code Segment が走らせており, ログが put されると そのデータを受け取り自身の Tree へと反映を行う</li> </ul> </article> <article> <h3>ログを扱う Data Segment</h3> <ul> <li>childLog には子供となるノードが行った編集のログが入れられる</li> <li>各ノードでは childLog を見張る Code Segment が走っており, データが put され次第 Tree へのログの反映が行われる</li> <li>親ノードの log と自身がもつ childLog を Code Segment でみはることでデータの分散を 行う</li> <table> <tr style="width:100%;"> <td style="width:50%;"> <p> <img src="./pic/putLog.png"> </p> </td> <td style="width:50%;"> <p> <img src="./pic/putChildLog.png"> </p> </td> </tr> </table> </ul> </article> <article> <h3>Merge algorithm の設計</h3> <ul> <li>ロックは最新のtreeのrootを取得するときのみでよい</li> <li>変更は新しいrootを作って書き込む</li> <li>作った後に衝突のある変更が来た時にMergeが必要になる</li> <li>書き込むデータと既に書き込まれたデータのタイムスタンプをみてMergeを行う.掲示板においてのMergeはそれで十分だが, ブログやWikiといったCMSを設計するさいには もっと複雑なMergeになる</li> <li>Jungle では非破壊により過去のデータを保持しているためMerge中でもreadに応答することが可能</li> </ul> </article> <article> <h3>掲示板によるJungleの性能評価</h3> <ul> <li>Jungle の例題のアプリケーションとして掲示板を作成した</li> <li>組み込みウェブサーバである jetty をフロントエンドに実装</li> <li>今回作成した分散バージョンと元のバージョンをシングルサーバ上で動かし, 2つの ベンチマークをとり性能比較を行う</li> <li>また, Cassandra でも同様のアプリケーションを作成し性能比較を行う</li> <li>ベンチマークは学科の提供するVMのクラスタを用いる</li> </ul> </article> <article> <h3>実験方法</h3> <ul> <li>複数のクライアントから並列に5000回アクセス(HTTP Requestによる read と write)を行い, 平均時間をとる</li> <li>クライアント1台から45台まで並列にアクセスを行った結果をグラフ化する</li> </ul> </article> <article> <h3>実験環境</h3> <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> <table style="font-size: 0.7em"/> <tr> <th></th><th>VMWareクラスタ(リクエストを送るクライアント)</th> </tr> <tr> <td>台数</td><td>45</td> </tr> <tr> <td>CPU</td> <td>Intel(R) Xeon(R) CPU X5650@2.67GHz</td> </tr> <tr> <td>コア数</td> <td>4</td> </tr> <tr> <td>Memory</td> <td>8GB</td> </tr> <tr> <td>OS</td> <td>Fedora 16</td> </tr> <tr> <td>HyperVisor</td> <td>VMWare ESXi</td> </tr> </table> </article> <article> <h3>実験結果: 読み込み</h3> <table style="text-align:center; font-size:0.7em;"> <tr> <!-- <td> <img style="height:300px;" src="./pic/read_result.png"> </td> --> <td> <img style="height:300px;" src="./pic/read_bench_with_cassandra.png"> </td> </tr> <tr> <td>サーバの読み込み実験結果</td> </tr> </table> <ul> <li>今回の実装では読み込みに関する変更の部分はほぼ無い</li> <li>そのため分散サーバ版とシングルサーバ版もに似た結果となっている</li> <li>Jungle はロックが少ないせいか Cassandra よりも早い</li> </ul> </article> <article> <h3>実験結果: 書き込み</h3> <table style="text-align:center; font-size:0.7em;"> <tr> <!-- <td > <img style="height:300px;" src="./pic/write_result.png"> </td> --> <td> <img style="height:300px;" src="./pic/write_bench_with_cassandra.png"> </td> </tr> <tr> <td>サーバの書き込み実験結果</td> </tr> </table> <ul> <li>シングルサーバ版JungleとCassandra版では差がない</li> <li>今回実装した分散版 Jungle が一番遅い</li> <li>これは分散版は書き込まれた内容をData Segment にする作業がはいる為とおもわれる</li> </ul> </article> <article> <h3>まとめ</h3> <ul> <li>今回, 並列分散フレームワークである Alice を用いて Jungle の分散データベースの実装を行った</li> <li>Jungle の編集のログを Data Segment として Alice 上で他ノードへと送ることで実装</li> <li>具体的には, データを Data Segment で扱うための変換と, その Data Segment により Tree へ反映を行う Code Segment を用意することで実装を行った</li> <li>トポロジーの形成部分は Alice の提供する機能を使用した</li> <li>また, 実装を行った分散データベースで掲示板の作成をし, 元の Jungle との性能比較も行った</li> <li>読み込み速度に差は無いが, 書き込み速度は分散版が遅いことを確認した</li> <!-- <li>今回シングル版から分散版への変更は1000行程度のコードの追加で行うことができた</li> <li>これは Alice によりトポロジーの形成部分を書く必要がなかったことがあげられる</li> <li>Alice を用いて少ない変更で分散プログラムの作成ができることが確認できた</li> --> </ul> </article> <article> <h3>今後の課題</h3> <ul> <li>次回は, 分散環境における性能比較を行いたい</li> <li>そのためには分散データベースにおけるベンチマークの取り方の検証から行う必要がある</li> <li>永続性とNodeが落ちた際のリカバリの実装も残っている</li> <br> <li>また, Alice 内部 java.util.concurrent.Executorを使用している為, Jungle側のThread Pool に干渉している可能性がある. 調整を行いスピードアップを目指したい</li> </ul> </article> <article> <h3>スケーラビリティとは？</h3> <p>スケーラビリティとは, システムの特性で, 利用者の増大やその負荷に応じて柔軟に対応できるような性質.</p> <p>分散システムの場合, ノードを追加するだけで性能を線形に向上させる事ができる</p> <br/> <p>スケーラビリティを上げる方法は？</p> <ul style="color:red;text-weight:bold;"> <li>スケールアップ : 高価なサーバーを買う</li> <li>スケールアウト : 安価なサーバーを複数用意して利用する</li> </ul> <p>という2種類の方法がある.</p> </article> <article> <h3>Cassandra の実装との比較</h3> <ul> <li>Cassandraとは, スケーラブルな分散KeyValueStoreデータベースである</li> <li>Cassandra ではデータの書き込みはノードの過半数に行われるのを待つ</l> <li>読み込みに関しても過半数のノードを調べ, 最も新しいタイムスタンプを持つデータを返す</li> <p class="center"> <img src="./pic/cassandra.png"> </p> </ul> </article> <article> <h3>Cassandra の実装との比較: Jungle の場合</h3> <ul> <li>Jungle ではデータはノードが手元に持っているものを返す</li> <li>データの編集が行われた場合は, 他ノードへとログを伝搬していく</li> <li>ログの衝突が起きた場合は衝突を検知したノードがMergeを行い, Mergeを行ったログを伝搬させる</li> <p class="center"> <img src="./pic/distribute_jungle.png"> </p> </ul> </article> </body> </html>