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

琉球大学大城信康
11 Sep 2013

研究の目的と背景

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

並列分散フレームワーク Alice

当研究室で開発している
Data Segment と Code Segment による並列・分散プログラミングを提供

まず Data Segment と Code Segment, それと Alice におけるデータ表現について説明を行う

Data Segment

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

Code Segment

Data Segment を受け取り計算を行うコード
並列プログラミングにおけるタスクにあたる
Code Segment は計算に使う Data Segment の Key を登録してその Key にあたる Data Segment が用意され次第処理が実行される

計算を行った結果を新たな Data Segment として出力する

Alice上でのデータ表現:MessagePack

Data Segment のデータ表現には MessagePack を利用
Messagepack はバイナリをベースにしたシリアライズライブラリー
独自のクラスでも @Message アノテーションを付けることでシリアライズ可能
(その際にはシリアライズできる型のみのフィールドをもつこと)
MessagePack を使用することで Alice 以外のプログラムでの Data Segment を扱うことが可能になる

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

Jungle はスケーラビリティのある CMS の開発を目指している
一般的なコンテンツマネジメントシステムのウェブサイトの構造は大体が木構造

破壊的木構造

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

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

非破壊的木構造

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

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

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 による編集の命令はある程度の塊で扱われる
この編集の塊を 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:0]

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

Alice を用いた Jungle の分散実装

Alice により TreeOperationLog を Data Segment として扱うことで行う
他Nodeがその Data Segment にアクセスを行えるようにする
アクセスできるようにするためには次の作業が必要

トポロジーの形成
TreeOperationLog を MessagePack によりシリアライズ
TreeOperationlog を扱う Data Segment の作成

トポロジーの形成

トポロジーの形成は Alice の機能を用いる
Alice ではトポロジー設定用ファイルに従いノード同士を接続させる
5ノード2分木のノードを組みたいときは次のようなファイルになる

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"]
}

トポロジーの形成

生成されるトポロジー

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

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

TreeOperationLog を Data Segment で扱うために MessagePack によるシリアライズ可能にする必要がある
MessagePack によりクラスをシリアライズするためには, そのクラスがもつフィールド全てがシリアライズできるものでないといけない
TreeOperationLog が保持するフィールドを全てシリアライズして保持する container を用意
TreeOperationLog は一度その container で Value 型へと変換されて保持されることで Data Segment として扱えるようにした