分散フレームワークAliceのMeta Data Segment

照屋のぞみ琉球大学工学部情報工学科河野研

研究目的(1/3)

当研究室が開発している並列分散フレームワークAliceではスケーラブルな分散プログラムを信頼性高く記述できる環境を実現する
ここで言う信頼性とは定められた環境下で安定して仕様に従った動作を行うことを指す
Aliceでは当研究室が提案しているデータを Data Segment、タスクを Code Segment という単位で分割して記述するプログラミング手法を採用している

研究目的(2/3)

Aliceでは、ComputationとMetaComputationに階層化し、コアな仕様と複雑な例外処理に分離する。
分散環境構築などの複雑な処理はAliceがMeta Computationとして提供する
コードの変更を抑え、変更前の信頼性を保ったまま拡張可能にする

研究目的(3/3)

本研究では、Alice上に実用的な分散アプリケーションが制作できることを示すために画面配信システムTreeVNCを構築する
構築するにあたり必要となった圧縮機能をAliceのMeta Computationとして実装した
もとのTreeVNCとの比較を行うことでMeta Computationの役割と有効性を示す

Data Segment と Code Segment

Aliceではデータを Data Segment(DS) 、タスクを Code Segment(CS) という単位に分割して依存関係を記述することでプログラミングを行う。
CSはInput DS(入力されるDS)とOutput DS(出力されるDS)を持つ。
CSはkeyで指定されたDSが全て揃うと実行されるという性質を持つ。

CodeSegmentの依存関係

データの依存関係にないCSは並列実行される
データの依存関係がある場合は Input DS が揃うと順に実行される
DSはCSに専有されるためロックの記述を必要としない

Data Segment Manager

DS の集合体であるデータベースを DS Manager(DSM) と呼ぶ。
- Local DSM … 各ノード固有のデータベース。
- Remote DSM … 他のノードの Local DSM の proxy。接続しているノードの数だけ存在する。
DSM 内の DS には対になる String型のkey が存在し、 DSM 名と key を指定しすることで DS の保存、取得を行う。

Computation と Meta Computation

Aliceでは、計算の本質的な処理をComputatin、Computationとは直接関係ないが別のレベルでそれを支える処理をMeta Computationとして分けて考える。
分散トポロジーの構成、通信の切断・再接続時の処理などはMeta ComputationとしてAliceが提供
プログラマは目的の処理だけ記述し通信部分などはMeta Computationを指定することでシンプルな記述を実現

Computation と Meta Computation

DS/CSの接続の間にMeta Computationが実行されている
AliceのMeta ComputationもCS/DSにより実現される
Meta ComputationはCS の処理を支えるMeta CSとMeta CSに管理されるMeta DSに分けられる

TreeVNCへの応用

AliceのMeta Computationの有効性を示すため実用的な例題であるTreeVNCを実装する
TightVNCをもとにした木構造画面配信システム
画面処理や分散処理が混在する複雑なTreeVNCも、Aliceを用いればTightVNCからの変更が少ない見通しの良い記述で構成可能

TreeVNCで必要な機能

TreeVNCのComputation（VNCサーバからデータを受け取り表示）を支える機能をMeta Computationとして実装する

TreeTopologyの構成・管理（Topology Manager）
ノード間通信の切断時・再接続時の処理（ClosedEventManager）
ノードの接続状態確認（KeepAlive）
子ノードへのデータの転送(flip)
データの圧縮

Meta Computationの追加

TreeVNCの数MByteの画面差分データを配信し続けるためデータを圧縮している
画面データを圧縮して送る → 解凍して画面表示 → 再圧縮して子ノードへ転送
圧縮状態のまま子ノードに送信ができれば、解凍・再圧縮するオーバーヘッドを無くすことができる
圧縮のMeta Computationと転送のMeta Computationを追加した

圧縮表現(Meta DS)の追加

DSを複数作るのではなく、１つのDSに対しMeta DSとして以下の表現を同時に持たせる

1. 一般的なJavaのオブジェクト
　LocalDSMにputしたときの形式

2. シリアライズ化されたバイナリオブジェクト
　RemoteDSMにputしたときの形式

3. 2を圧縮したバイナリオブジェクト
　今回追加した形式

圧縮表現を扱うDSMとAPIの追加

Local と Remote それぞれに圧縮表現を扱う Compressed DSM を追加
DSを圧縮したい場合は指定する DSM を Compressed DSM に変える
圧縮するコードとしないコードで変更が少ない

	put("Remote", "Key", val);  
	put("compressedRemote", "Key", val);

圧縮表現がオンデマンドに作られる

DS はオブジェクト表現と圧縮表現を同時にもつため、TreeVNCでは受け取った画面データを解凍した後、転送のためにコピーや再圧縮をすることはない。
複数表現は必要最低限にしか作られない。
一つのKeyに対し様々な表現のDSが対応するが、キャストメソッドであるasClass()によってユーザーは送られてくるDSの表現を気にせず任意の型で取り出せる。

Meta Computationの評価

TreeVNCとAliceVNCを比較した

性能比較
各ノードへのメッセージの伝達速度を比較
同等の性能が実現できたか
コード比較
コード量・コード複雑度を比較
シンプルな記述で仕様の変更が抑えられているか

性能比較 - 実験結果

3段目の計測結果
同じ傾向から同等の処理性能があることがわかった


TreeVNC	AliceVNC

コード量比較

TightVNCを含む全体の行数・単語数はAliceVNCのほうが少ない
コードの増加量ではTreeVNCに比べ75%仕様の変更が抑えられている

	行数	単語数	TightVNCからの変更行数
TreeVNC	19502	73646	7351
AliceVNC	14647	59217	1129
減少率 (%)	25	20	75

コード複雑度比較

循環的複雑度を用いる
コード内の線形独立な経路の数。if や forが多いほど複雑度が高い。

	平均値	最高値
TightVNC	13.63	97
TreeVNC	15.33	141
AliceVNC	10.95	99

AliceVNCのほうがTreeVNCに比べ複雑度が低い
TreeVNC で最も複雑度が高いTreeRFBProto.classはデータの待ち合わせ処理や通信処理が入り組んだ複雑なコード
AliceVNCで最も複雑度が高いSwingViewerWindow.classは、TightVNCから変更がほとんどないため、AliceVNCの持っている複雑度はTightVNCが元来持っていた複雑度

まとめ

Alice が実用的なアプリケーションを記述するための Meta Computation として、Meta Data Segmentに複数の表現のデータを同時に持たせることで圧縮機能を実装した。同様の手法を用いれば暗号表現などへの対応もでき自由度の高い通信を行うことが可能になる。
TreeVNCをAlice上で実装し比較を行った結果、変更量の少ないシンプルな記述でTreeVNCの基本機能を実現でき、同等の性能を出すことに成功した。
AliceのMeta Computationが拡張性・信頼性の高い実用的な分散アプリケーションの構築に有用であることが確認された。

今後の課題

TreeVNCでは拡張が困難であった別ネットワーク間の通信もTopology Manager を用いれば容易に拡張できると考えられる

今後の課題

APIの再設計
- put/updateに対しtake/peekがcreate()・setKey()の操作はわかりにくい
DSの型情報のマネジメント
- 型情報がないのでpeek/takeする際にわかりにくい
セキュリティをサポートしていない
- 圧縮と同様の手法で暗号形式のデータ表現を扱えるように拡張可能