Data Segment の分散データベースへの応用

琉球大学 大城信康
11 Sep 2013

研究の目的と背景

• 当研究室では並列分散フレームワーク Alice を開発している
• Alice はタスクを Code Segment, データを Data Segment という単位で扱うプログラミングスタイルを提供する
• また, 当研究室では非破壊的木構造を用いたデータベースである Jungle を開発している
• 非破壊的木構造とは, データの編集の際に一度木構造として保存したデータには触れず, 新しく木構造を作成してデータの編集を行うこと
• Jungle は分散データベースとして設計されているが, 今のところシングルサーバ上でしか動かない
• 本研究では, Jungle に Alice を用いて分散データベースとしての実装を行った. また例題を作成し評価を行う.

Alice : Code Segment

• Alice : 当研究室で開発している並列分散フレームワーク
• Data Segment と Code Segment による並列・分散プログラミングを提供



• Code Segment : 並列プログラミングにおけるタスク
• Data Segment を受け取り計算を行うコード
• Data Segment の Key を登録することで, 登録された Data Segment が準備されしだい実行される

Data Segment

• 計算に必要なデータ
• Alice は Data Segment を文字列の Key で管理
• Key 毎にリストが用意され, put された順番で Data Segment は取り出される
• Data Segment Manager(DSM) により管理される



• Data Segment のデータ表現にはシリアライズライブラリーの MessagePack が使われている

非破壊的木構造を用いたデータベース Jungle

• 当研究室で開発中のデータベース
• データを木構造かつ、非破壊で保持することが特徴

破壊的木構造

• 木構造で保持するデータを直接書き換える
• 編集を行う際にロックをかける必要がある



• データを受け取ろうと木を走査するスレッドは編集時には書き換えの終了をまつ必要がある

非破壊的木構造

• 一度作成したデータの破壊は行わない
• データの編集は, 編集が行われるノードまでをルートからコピーを行い新しい木構造を作ることで行う



• 非破壊的木構造ではデータの編集中に走査をすることが可能なためスケールしやすいと考えている

Jungle におけるデータ編集: API

• Jungle ではデータの編集を行う Editor を提供している
• Editor が提供するデータ編集のメソッドは次のようなものがある
• Nodeの追加を行う
  addNewChildAt(NodePath _path, int _pos)
• Nodeの削除を行う
  deleteChildAt(NodePath _path, int pos)
• Nodeにattributeを追加する
  putAttribute(NodePath _path, String _key,
  ByteBuffer _value)
• Nodeのattributeを削除する
  deleteAttribute(NodePath _path, String _key)

Jungle におけるデータ編集: NodePath

• NodePath は root から編集を行う Node までの道を示す
• 例えば NodePath が -1,1,2,3 の場合は次の Node を示す



• Jungle におけるデータ編集はこの NodePath を Editor が提供する API に渡すことで行われる

TreeOperationLog

• Editor による編集の命令はある程度のAPIの塊で扱われる
• この編集の塊を TreeOperatinLog という
• 今回実装した掲示板では, 書き込み時に次のような TreeOperaitonLog が作られる

[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]     

• 大文字の英字は実行した API を示す
• <>で囲まれた数字は NodePath を示す
• key と value は attribute に格納する内容を示す

Alice を用いた Jungle の分散実装

• Alice により TreeOperationLog を Data Segment として扱うことで行う
• 他Nodeがその他Nodeの Data Segment にアクセスを行う
• アクセスできるようにするためには次の作業が必要
• トポロジーの形成
• TreeOperationLog を MessagePack によりシリアライズ
• TreeOperationlog を扱う Data Segment の作成

トポロジーの形成

• トポロジーの形成は Alice の機能を用いる
• 子供となるノードは parent キーにより親の DSM にアクセスできる
• 親となるノードは child0, child1 キーにより子供のノードの DSM にアクセスできる
• Alice が提供する機能により楽にトポロジーの形成と他のノードがもつデータへのアクセスができる

TreeOperationLog の MessagePack によるシリアライズ

• TreeOperationLog を Data Segment で扱うために MessagePack によるシリアライズ可能にする必要がある
• MessagePack によりクラスをシリアライズするためには, そのクラスがもつフィールド全てがシリアライズできるものでないといけない
• TreeOperationLog が保持するフィールドを全てシリアライズして保持する container を用意
• TreeOperationLogではFunctional JavaのリストでPathが保持される. MessagePack ではFunctional JavaのListがシリアライズできないため, 普通のListに変換させて Data Segment として保持させた

ログを扱う Data Segment

• Data Segment にされた TreeOperaiontinLog はAlice上で log, childLog というキーで扱われる
• log にはそのノードが行った木の編集ログが入る
• 子供となるノードは parent キーを使うことで親のノードの DSM にアクセスできる



• 子供となるノードは親の log を見張る Code Segment が走らせており, ログが put されると そのデータを受け取り自身の Tree へと反映を行う

ログを扱う Data Segment

• childLog には子供となるノードが行った編集のログが入れられる
• 各ノードでは childLog を見張る Code Segment が走っており, データが put され次第 Tree へのログの反映が行われる
• 親ノードの log と自身がもつ childLog を Code Segment でみはることでデータの分散を 行う

Merge algorithm の設計

• ロックは最新のtreeのrootを取得するときのみでよい
• 変更は新しいrootを作って書き込む
• 作った後に衝突のある変更が来た時にMergeが必要になる
• 書き込むデータと既に書き込まれたデータのタイムスタンプをみてMergeを行う.掲示板においてのMergeはそれで十分だが, ブログやWikiといったCMSを設計するさいには もっと複雑なMergeになる
• Jungle では非破壊により過去のデータを保持しているためMerge中でもreadに応答することが可能

掲示板によるJungleの性能評価

• Jungle の例題のアプリケーションとして掲示板を作成した
• 組み込みウェブサーバである jetty をフロントエンドに実装
• 今回作成した分散バージョンと元のバージョンをシングルサーバ上で動かし, 2つの ベンチマークをとり性能比較を行う
• また, Cassandra でも同様のアプリケーションを作成し性能比較を行う
• ベンチマークは学科の提供するVMのクラスタを用いる

実験方法

• 複数のクライアントから並列に5000回アクセス(HTTP Requestによる read と write)を行い, 平均時間をとる
• クライアント1台から45台まで並列にアクセスを行った結果をグラフ化する

実験環境

実験結果: 読み込み

サーバの読み込み実験結果

• 今回の実装では読み込みに関する変更の部分はほぼ無い
• そのため分散サーバ版とシングルサーバ版もに似た結果となっている
• Jungle はロックが少ないせいか Cassandra よりも早い

実験結果: 書き込み

サーバの書き込み実験結果

• シングルサーバ版JungleとCassandra版では差がない
• 今回実装した分散版 Jungle が一番遅い
• これは分散版は書き込まれた内容をData Segment にする作業がはいる為とおもわれる

まとめ

• 今回, 並列分散フレームワークである Alice を用いて Jungle の分散データベースの実装を行った
• Jungle の編集のログを Data Segment として Alice 上で他ノードへと送ることで実装
• 具体的には, データを Data Segment で扱うための変換と, その Data Segment により Tree へ反映を行う Code Segment を用意することで実装を行った
• トポロジーの形成部分は Alice の提供する機能を使用した
• また, 実装を行った分散データベースで掲示板の作成をし, 元の Jungle との性能比較も行った
• 読み込み速度に差は無いが, 書き込み速度は分散版が遅いことを確認した

今後の課題

• 次回は, 分散環境における性能比較を行いたい
• そのためには分散データベースにおけるベンチマークの取り方の検証から行う必要がある
• 永続性とNodeが落ちた際のリカバリの実装も残っている


• また, Alice 内部 java.util.concurrent.Executorを使用している為, Jungle側のThread Pool に干渉している可能性がある. 調整を行いスピードアップを目指したい

スケーラビリティとは？

スケーラビリティとは, システムの特性で, 利用者の増大やその負荷に応じて柔軟に対応できるような性質.

分散システムの場合, ノードを追加するだけで性能を線形に向上させる事ができる

スケーラビリティを上げる方法は？

• スケールアップ : 高価なサーバーを買う
• スケールアウト : 安価なサーバーを複数用意して利用する

という2種類の方法がある.

Cassandra の実装との比較

• Cassandraとは, スケーラブルな分散KeyValueStoreデータベースである
• Cassandra ではデータの書き込みはノードの過半数に行われるのを待つ
• 読み込みに関しても過半数のノードを調べ, 最も新しいタイムスタンプを持つデータを返す

Cassandra の実装との比較: Jungle の場合

• Jungle ではデータはノードが手元に持っているものを返す
• データの編集が行われた場合は, 他ノードへとログを伝搬していく
• ログの衝突が起きた場合は衝突を検知したノードがMergeを行い, Mergeを行ったログを伝搬させる