日本ソフトウェア科学会第 30 回大会 (2013 年度) 講演論文集

Data Segment の分散データベースへの応用
大城 信康

杉本 優

河野 真治

永山 辰巳

当研究室では並列・分散プログラミングスタイルとして Data Segment, Code Segment によるプログラミング手法を提案している. Data Segment, Code Segment の Java 上の実装として Alice を作成してきた。Alice は分散管理フレームワークであり, Alice を用いることで分散プログラムが比較的楽に行える. そこで, 当研究室で開発している非破壊的木構造データベース Jungle の分散実装を Alice を用いて行った. 本研究では, Alice に Jungle の分散実装を通じて, データベースノード間の通信を行う利点と欠点について考察する。

送受信することでデータの分散を行うことができる.

1 研究の目的と背景
当研究室では並列・分散プログラムに向いたプログ
ラミングを目指し, データを Data Segment, タスクを本研究では, Alice の応用として Jungle を用いた分散データベースの実装を行う. さらに, 例題のアプリケーションとして掲示板を作成し, 評価を行う.

Code Segment という単位で扱うプログラミングス
タイルの提案を行なっている. そこで Data Segment,2 分散ネットワークフレームワーク Alice

Code Segment によるプログラミングを提供する実Alice は当研究室で開発している分散管理フレーム装として, Java による分散ネットワークフレームワーワークである. Data Segment と Code Segment にク Alice を開発している. Alice はノード間のトポロよる並列・分散プログラミングを提供する.

ジー生成を提供しており, Data Segment としてデータの送受信をノード間で行うことができる.

まず, Data Segment と Code Segment についての説明を行う.

また, 当研究室では非破壊的木構造を用いたデータベースである Jungle の開発も行なっている. Jungle

2. 1 Data Segmentはデータを非破壊で保持することでスケーラビリティ

Data Segment は計算に必要なデータになる. Aliceのあるデータベースを目指している. Jungle はデー

は Data Segment を文字列の Key で管理する. Keyタの編集を TreeOperationLog という単位で行う.

毎にリストが用意され, put された順番で Data Seg-Alice を使いこの TreeOperationLog を各ノード間でment は取り出され計算が行われる. Data Segment
は Data Segment Manager(以下 DSM) により管理

Distribution Database Application of Data Segment
Nobuyasu OSHIRO,Yu SUGIMOTO, Shinij KONO ,琉球大学大学院理工学研究科情報工学専攻並列信頼研, Dept.Concurrency Reliance Laboratory, Information Engineering Course, Faculty of Engineering
Graduate School of Engineering and Science, University of the Ryukyus, .
Tatsumi NAGAYAMA, 株 式 会 社 Symphony, Symphony Co., LTD.

される. DSM はノード毎にキーを持つ. 他のノードの DSM にアクセスする場合は Remote DSM 経由で行う. Alice による分散プログラミングはこの

Remote DSM の機能を使用する.
Data Segment Manager は API を提供しており,この API を通じて Data Segment のやりとりが行われる具体的には以下の API が用意されている.

• void put(String key, Value val)

InputDataSegment

put は Data Segment をリストへと追加する API である.

Data
Segment

OutputDataSegment• void update(String key, Value val)
update はリストに入っている Data Segment を更新

DataSegment
DataSegment

する API である.

• void peek(Receiver receiver, String key)
peek はリストに入っている Data Segment を取り

CodeSegment
DataSegment

DataSegment

出す API である. peek により取り出された Data

Segement はリストより削除されない.
• void take(Receiver receiver, String key)

図1

Data Segment と Code Segment

take はリストに入っている Data Segment を取り出ている. 独自のクラスでも @Message アノテーショ

す API である. 取り出した Data Segment はリストンを付けることで Value 型へと変換することができより削除される.

る. その時は MessagePack がシリアライズできる型のみをフィールドに入れなければならない.

2. 2 Code Segment
Code Segment は Data Segment を受け取り計算を行うコードのことを示す. 並列プログラミング

3 非破壊的木構造を用いたデータベース Jungleにおけるタスクにあたる. Code Segment と Data

Jungle はスケーラビリティのある CMS の開発をSegment は対になっている. Code Segment は計算目指して当研究室で開発されている非破壊的木構造に使う Data Segment のキーを登録して, そのキーデータベースである. 一般的なコンテンツマネジメンにあたる Data Segment が用意され次第処理が実行

トシステムではブログツールや Wiki・SNS が多く,される. Code Segment が処理を開始するのに必要な

これらのウェブサイトの構造は大体が木構造であるた

Data Segment を Input Data Segment という.

め, データ構造として木構造を採用している.

Code Segment では Data Segment の生成を行い,ここではまず破壊的木構造と, 非破壊的木構造の説

put や update により新たにリストに登録することが明をし, Jungle におけるデータ編集の実装についてできる. Code Segment 内で作成し登録される Data述べる.

Segment は Output Data Segment と呼ばれる.
Code Segment は Input Data Segment と Output
Data Segment の API を提供する (図 1).

3. 1 破壊的木構造
破壊的木構造の編集は, 木構造で保持しているデータを直接書き換えることで行う. 図 2 は破壊的木構造

2. 3 MessagePackの編集を表している.

Alice における Data Segment のデータ表現には破壊的木構造は, 編集を行う際に木のロックを掛けMessagePack を利用している. MessagePack はバイる必要がある. この時, データを受け取ろうと木を走ナリをベースにしたシリアライズライブラリーであ査するスレッドは書き換えの終了を待つ必要があり,る [1]. また, MessagePack のバイナリにシリアライ閲覧者がいる場合は木の走査が終わるまで書き換えズできる型のみで構成された Value オブジェクトがをまたなければならない. これではスケールしにくい用意されている. MessagePack は Java の基本的なと考えられる.

型はシリアライズすることができる.

Value オブジェクトは自己記述なデータ形式になっノードの子供の場所を次々に指定していくことで編集
ノード5をノード100へ直接書き換える

root

132415

図2

対象のノードの場所を表す (図 4).

root

3

root-124

100010

破壊的木構造の編集

3. 2 非破壊的木構造木構造

...

10n2

1

323

非破壊的木構造は破壊的木構造とは違い一度作成

編集対象

NodePath<-1,1,2,3>したデータを破壊することはない. 非破壊的木構造においてデータの編集を行う場合は, root から編集の図4あったノードまでコピーを行い新しく木構造を作成す

NodePath

ることで行う. 編集が行われない部分は参照をもたせTree 編集の API として次の 4 つが用意されている.

る. 図 3 は非破壊的木構造の編集を表している.

• addNewChildAt(NodePath _path,int _pos)root から変更のあったノードまでコピーを行う

root1NodePath で指定された Node に子供となる Node2rootrootを追加する API である. pos で指定された番号に子供として追加を行う.

1• deleteChildAt(NodePath _path,int _pos)

22

NodePath と pos により指定される Node を削除す
345

345100る API である.

• putAttribute(NodePath _path,String _key,ByteBuffer _value)
図3

非破壊的木構造の編集

Node に attribute を追加する API である. 文字列をキーにして ByteBuﬀer によりデータを保持する.

非破壊的木構造により, 木構造を編集しながら走査することが可能となる. よって, 破壊的木構造よりスケールすると考えている.

• deleteAttribute(NodePath _path,String _key)
NodePath により指定される Node の attribute を削除する API である. 削除する attribute は文字列

3. 3 Jungle におけるデータ編集のキーで指定する.

木の編集は, 通常 Node を書き換えるため Nodeの API として提供されることが多いが, Jungle で3. 4 TreeOperationLog

は JungleTreeEditor を利用して行う. JungleTree

上記の API を使用すると Editor 内部では Node-Editor には編集するためのいくつかのメソッドが用Operation として順次つまれていき, 最終的に commit意されており, NodePath と呼ばれるルートノードかされることで編集が行われる. 複数の NodeOperation

らノードまでのパスを指定することでノードが編集の集まりを TreeOperationLog といい, これが編集のされる. NodePath は, ルートノードからスタートし,単位となる. 例えば, 後述する掲示板の実装では 1 つ

の書き込みに対して 1 つの Node を作成し, attributenode3 -> node1 [label="parent"]

をもたせている. その時のログは次のようになる.

node4 -> node1 [label="parent"][APPEND_CHILD:<-1>:pos:1]}[PUT_ATTRIBUTE:<-1,1>:key:author,value:oshiro]

これにより形成されるトポロジーを図 5 に示す.

[PUT_ATTRIBUTE:<-1,1>:key:mes,value:hello][PUT_ATTRIBUTE:<-1,1>:key:key,value:hoge]
node0[PUT_ATTRIBUTE:<-1,1>:key:timestamp,value:0]

parentparent

大文字の英字は実行した API を表す. <>によりchild1

node2

parentの後ろは posision や attribute の情報を表している. NodeOperation と NodePath の組み合わせを

child2

node1囲まれている数値は NodePath を示す. NodePathparentchild1child2

node3

node4

TreeOperation として扱い, それらいくつか集まりがTreeOperationLog となる.
図54 Alice を用いた Jungle の分散実装
Alice を用いた Jungle のデータ分散は, 上記の子共となるノードは ”parent” キーにより親の DSM

TreeOperationLog を Data Segment として扱い他(Remote DSM) にアクセスすることができる. また,ノードがその Data Segment にアクセスできるよう親も子供となるノードの DSM に対して ”child1” やにすることで行える. そのために必要なことは以下と”child2” キーによりアクセスすることが可能となる.

なる.

Alice ではスクリプトが用意されており, ノードの

• トポロジーの形成数と子供の数を指定するだけで dot ファイルの作成• TreeOperationLog を MessagePack によりシリが行える. このように, Alice では比較的楽にトポロ

アライズ

ジーの形成が行える.

• TreeOperationLog を 扱 う Data Segment の作成

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

4. 1 トポロジーの形成

TreeOperationLog は MessagePack でシリアライ

Alice はトポロジーの形成を行う機能を提供していズできないものを List のフィールド変数に保持しる. トポロジー設定用ファイルに従い, ノード同士をている. そのため, TreeOperationLog はそのまま接続させる.

では MessagePack でシリアライズすることはでき

トポロジー設定用ファイルは DOT Language で記ない. フィールドとして保持しているものは全て述される. 例えば, 5 ノード 2 分木のノードを組みた

MessagePack でシリアライズできるものにする必要いときは次のようなファイルになる.

がある. そこで, フィールドで保持しているものをdigraph test {Value 型に変換するための Container クラス作成を

node0 -> node1 [label="child1"]

それぞれ行った. ログに関連するクラス全てをシリ

node0 -> node2 [label="child2"]

アライズするクラスを行った後に, それら全てをまとnode1 -> node0 [label="parent"]

める DefaultTreeOperationLogContainer クラスのnode1 -> node3 [label="child1"]作成を行った. このクラスは TreeOperationLog を

node1 -> node4 [label="child2"]

Value 型へと変換しフィールド変数で保持する. 実際

node2 -> node0 [label="parent"]に TreeOperationLog のシリアライズを行うソース

を次に示す.

container.setUpdaterName(_updaterName);public void unconvert(Iterable

container.setRevision(nextRevision);<TreeOperation> _log) throws IOExceptio{

container.setPosition(pos);

MessagePack msgpackcontainer.unconvert(_log);= SingletonMessage.getInstance();container.setTimeStamp(timestamp);

List<Value> list

HashLogUpdateCodeSegment cs= new LinkedList<Value>();= new HashLogUpdateCodeSegment(container.getHashLogString());

for(TreeOperation op : _log) {NodeOperation nOp

cs.ods.put("log", container);= op.getNodeOperation();cs.ods.put により Data Segment のリスト ”log” に

NodePath nPath

対してログの put を行う.

= op.getNodePath();DefaultTreeOperation treeOp

4. 3 ログを扱う Data Segment= new DefaultTreeOperation(nPath, nOp);

Alice の各ノードは ”log”, ”childLog” というキー

DefaultTreeOperationContainer c

でログを扱う (図 6).

= new DefaultTreeOperationContainer();c.unconvert(treeOp);

log
node0

Value v = msgpack.unconvert(c);parentlist.add(v);node1}
Value listValueparent= msgpack.unconvert(list);

node3

childLog
parentlog
childLog

node2

log
childLog

log
childLog

logValue = listValue; // field variable}
上 記 の ソ ー ス で は 主 に MessagePack に よ り

図6

形成されるトポロジーと Data SegmentList<TreeOperation> で 保 持 し て い た TreeOperation を List<Value> へと変換させている. Single-”log” にはそのノードが行った木の編集のログが入TonMessage は使用する MessagePack を Singleton

る. また, 子供となるノードは ”parent” というキーで使用するためのクラスである. これにより何度もを使うことで親ノードの Data Segment Manager にMessagePack を new することを防いでいる.

アクセスすることができる. 子供となるノードは親のまた, Data Segment にするにあたり, TreeOper-”log” を待ち反映する Code Segment (LogUpdate-ationLog の保持だけでなく, 編集した木の名前やリ

CodeSegment) を走らせており, ログが put される

ビジョン番号, 変更を行ったノードの情報をノードのとそのデータを受け取り Code Segment の処理が行名前といった情報も保持させる. DefaultTreeOpera-

われる (図 7).

tionLogContainer の生成から Data Segment へ put”childLog” には子供となるノードが行った編集のを行なっているソースを次に示す.

ログが入れられる. ノードは ”childLog” の Data

DefaultTreeOperationLogContainer container

Segment にデータが入るの待っている Code Seg-

= new DefaultTreeOperationLogContainer();ment が常に走らせており, 子供が行った木の編集がcontainer.setTreeName(_treeName);”childLog” に put されることで親へとデータの伝搬

container.setUUID(_uuid);が行われる (図 8).

るがつまり Cassandra はデータについて複数のノードに問い合わせていることになる.

"parent", "log"1

LogUpdate
CodeSegment

log

同じ最新のデータを持っているput過半数のノードに問い合わせる

図7

親ノードの更新を行う Code Segment

require"local", "childLog"
1log

ChildLogCheckUpdate
CodeSegment

図9

Cassandra におけるデータの更新・読み込みput
図8

子供のノードの更新を行う Code Segment

5. 1 Jungle のデータ要求
Jungle ではデータの要求が行われた場合, 手元に

4. 4 Merge algorithm の設計あるデータを返す. データの編集が行われた場合は,Jungle はログの衝突が起きた場合に, Merge を行他ノードへとログを伝搬していく (図 10).

うことで衝突を解決する. 今回実装した掲示板における Merge algorithm は単純な実装である. 書き込み

Masterのタイムスタンプと既に書き込まれたデータのタイ67

ムスタンプを比べ, ソートを行うだけである.

2

掲示板においての Merge はそれで十分である. し534

かし, ブログや Wiki といった CMS を設計するさいにはもっと複雑な Merge になる. どのように Merge

81algorithm を実装していくかはよく考えて行わなければならに.

5 Cassandra との比較

require図 10

Jungle のデータ伝搬

Cassandra は複数のサーバで動作を想定した分散データベースである. Cassandra は分散 Key-Value

この時, 別のログと衝突が起きた場合は衝突を検知ストアデータベースであり, Dynamo [2] と BigTableしたノードが Merge を行う. その後 Merge を行った

[3] を合わせた特徴を持っている. データの Read とログをまた他ノードへと伝搬させていく.

Write に対して Consistency Level を設定すること

Jungle は非破壊により過去のデータを持っているができるのが特徴である. Write に関してはデータのため Merge を行うことができる. それにより最新の書き込みが全体, 過半数, もしくは 1 つのノードに書データでなくてもデータを返すことができ, それがスき込まれたかどうかの整合性の設定ができる. Read

ケーラビリティに繋がると考えている.

に関しては最初にデータを持っていたノードか, 全体を検索して最新のタイムスタンプを確認するかといった整合性の設定ができる. Consistency Level にもよ35

Distribution Server version
Single Server version

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

Jungle の例題のアプリケーションとして掲示板を25

る Jetty をフロントエンドにしたウェブアプリケーションである. 今回作成した分散バージョンと元のバージョンをシングルサーバ上で動かし, 2 つのベンavarage time(sec)作成した. この掲示板は組み込みウェブサーバーであ201510

チマークをとり性能比較を行う. ベンチマークは学科5が提供する VMWare のクラスタを用いて行う.

00510156. 1 実験方法
複数のクラスタから並列に 5000 回アクセス (HTTP

図 112025
nuber of nodes

30354045

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

Reauest) を行い, それぞれのクラスタの平均時間をとる. クラスタ 1 台から 45 台まで順次並列にアクセ50スを行いグラフ化する.

Distribution Server version
Single Server version

4540

6. 2 実験環境
掲示板を動かすサーバーの環境を図 1 に示す.
表1

掲示板を動かすサーバーの仕様

avarage time(sec)35302520

名前概要

CPU
物理コア数
論理コア数
MemoryOSJavaVM

RRIntel⃝Xeon⃝CPUX5650@2.67GHz*2
1224132GB
Fedora 16
1.6.0 39-b04

151050510

図 12152025
nuber of nodes

303540

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

6. 4 実験結果の考察
サーバにアクセスを行うクラスタの使用を図 2 に示す.

今回の行った実装では読み込み時に関しては特に手を加えていない. そのため, 読み込み速度に差は出ないというのが予想であった. 結果 (11) としても 2 つ

表2

検証に利用する VMWare クラスタの仕様

名前概要CPUMemoryOS
HyperVisor

RRIntel⃝Xeon⃝CPU
X5650@2.67GHz
8GB
CentOS 5.8
VMWare ESXiの結果にあまり差はでず, グラフもほぼ平行している.
書き込みの実装に対しては, ログを Data Segmentに put するという作業が入る. そのため分散版はシングル版に比べて遅くなることが予想できた. 結果(12) としても若干遅くなっていることが確認できた.

7 おわりに
7. 1 本研究のまとめ
6. 3 実験結果
実験結果を図 11, 12 に示す.

今回, Alice を用いて Jungle の分散データベースの実装を行った. Jungle の編集のログを Data Segment45

として Alice 上で他ノードへと送ることで実装する一環として行われた.

ことができた. Alice を使用すると, Jungle をシングルサーバーから分散サーバへと変更するコードの行参 考 文 献数は 1000 行程であった. これは, Alice によりトポロ[ 1 ] http://msgpack.org/. Messagepack.
[ 2 ] Giuseppe DeCandia, Deniz Hastorun, MadanJampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall, and Werner Vogels. Dynamo:
Amazon’s highly avaliable key-value store.
[ 3 ] Fay Changand Jeﬀrey Dean, Sanjay Ghemawat,
Wilson C. Hsieh, Deborah A. Wallach, Mike
Burrows, Tushar Chandra, Andrew Fikes, andRobert E. Gruber. Bigtable : A distributed storege
system for structured data.
[ 4 ] http://www.dependable os.net/osddeos/data.html.
研究チームフォーカスエリア技術報告書.
[ 5 ] 杉本優. 分散フレームワーク alice の datasegmentの更新に関する改良. 情報処理学会, April 2013.
[ 6 ] 玉城将士, 河野真治. Cassandra を使った cms の pc
クラスタを使ったスケーラビリティの検証. 日本ソフト
ウェア科学会, August 2010.
[ 7 ] 玉城将士, 河野真治. Cassandra を使ったスケーラビ
リティのある cms の設計. 情報処理学会, March 2011.
[ 8 ] 玉城将士, 河野真治. Cassandra と非破壊的構造を用いた cms のスケーラビリティ検証環境の構築. 日本
ソフトウェア科学会, August 2011.
[ 9 ] Avinash Lakshman and Prashant Malik. Cassandra - a decentralized structured storage system.
LADIS, March 2003.
[10] Brian Goetz, Tim Peierls, Joshua Bloch, Joseph
Bowbeer, David Holmes, and Doug Lea. Java Concurrency in Prac-tice. Addison-Wesley Professional,2005.
[11] DEOS 研究開発センター. DEOS プロジェクト「実用化を目指した組み込みシステム用ディペンダブル・オ
ペレーティングシステム」, 2012.

ジーの形成部分を書く必要がなかったことが理由としてあげられる. Alice を用いると比較的楽に分散プログラムの作成ができることを確認できた.
また, 実装を行った分散データベースで掲示板の作成をし, 元の Jungle との性能比較も行った. 読み込
み速度に差は無いが, 書き込み速度は分散版が遅いことが確認できた.

7. 2 今後の課題
次回は, Cassandra でも同じ分散プログラムを作り, 分散環境における性能比較を行いたい. それには分散データーベースにおけるベンチマークの取り方の検証から行わなければならない.
それと, Alice 内部では java.util.concurrent.Executorを使用している. そのため, Alice を使用しての分散プログラムは Alice 自身の Thread Pool との調和も考えて行く必要もある. Alice の Thread Pool との競合性についての検証も行っていきたい.

8 謝辞
本研究は高信頼性を目指す DEOS プロジェクトの