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

琉球大学大城信康
30 July 2013

研究の目的と背景

当研究室では並列・分散プログラムに向いたプログラミングを目指し, タスクを Code Segment, データを Data Segment によるプログラミング手法の提案を行なっている
Code Segment, Data Segment によるプログラミングの提供をする実装として分散ネットワークフレームワーク Alice を開発をしている

研究の目的と背景

また, 当研究室では非破壊的木構造を用いたデータベースである Jungle の開発も行なっている
Jungle はデータの編集を TreeOperationLog という単位で行う
Alice を使いこの TreeOperationLog を各ノード間で送受信することでデータの分散を行うことができる.
本研究では, Alice と Jungle を用いて分散データベースの実装を行う
さらに, 例題アプリケーションとして掲示板を作成し, 評価を行う

分散ネットワークフレームワーク Alice

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

Data Segment と Code Segment についての説明を行う

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 が用意され次第処理が実行される

MessagePack

Data Segment のデータ表現には MessagePack を利用
Messagepack はバイナリをベースにしたシリアライズライブラリー
独自のクラスでも @Message アノテーションを付けることでシリアライズ可能

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

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

まず破壊的木構造と, 非破壊的木構造の説明をおこなう

破壊的木構造

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

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

非破壊的木構造

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

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

Jungle におけるデータ編集

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 は 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 として扱えるようにした