+ time(ms) - + size(byte) - + node depth3 gnuplot_plot_1 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - + diff -r b2869724949d -r 90aaf305aed6 presen/sample.html --- a/presen/sample.html Wed Feb 17 20:35:54 2016 +0900 +++ b/presen/sample.html Thu Feb 18 09:06:13 2016 +0900 @@ -2,10 +2,10 @@ - 分散フレームワークAliceのPC画面配信システムへの応用 + 分散フレームワークAliceのMeta Data Segment - + @@ -67,15 +67,15 @@

分散フレームワークAliceのPC画面配信システムへの応用

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

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

@@ -87,16 +87,16 @@

研究目的(1/3)

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

@@ -105,10 +105,9 @@

研究目的(2/3)

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

@@ -117,9 +116,9 @@

研究目的(3/3)

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

@@ -130,8 +129,8 @@

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

@@ -150,56 +149,16 @@

Data Segment と CodeSegment

AliceはJavaで実装されており、DSはJava-Object、CSはRunnableに相当する
ユーザーが記述する際には CodeSegment.class を継承することでDSを操作するためのAPIを利用して依存関係を記述することができる。
DSはAliceが内部にもつデータベース(DS Manager)により管理されており、CSはDSに対応する一意のkeyを使ってDSを操作する。

- - -

Data Segment Manager

DS の集合体であるデータベースを Alice では DS Manager(DSM) と呼ぶ。
DSM 内の DS には対になる String型のkey が存在し、 DSM 名と key を指定しすることで DS の保存、取得を行う。
keyに対して複数のDSを保存する際はFIFO的に処理される
-

- - -

- -

Data Segment Manager

Local DSM … 各ノード固有のデータベース。
Remote DSM … 他のノードの Local DSM の proxy。接続しているノードの数だけ存在する。
-

- - -

- -

Data Segment API

DS の追加
+
DS の集合体であるデータベースを DS Manager(DSM) と呼ぶ。
- put(String managerKey, String key, Object val)
- update(String managerKey, String key, Object val) ※先頭DSを削除してからput
- Local DSM … 各ノード固有のデータベース。
- Remote DSM … 他のノードの Local DSM の proxy。接続しているノードの数だけ存在する。
DS の取得
-
- take(String managerKey, String key)
- peek(String managerKey, String key) ※DSMから削除されない
-
take/peekは実際にはcreate()とsetKey()によって行われる
create()でDSの受け皿を作っておき、setKey()にkeyをセットすることで Input DS を指定する
DSM 内の DS には対になる String型のkey が存在し、 DSM 名と key を指定しすることで DS の保存、取得を行う。 +

@@ -209,8 +168,8 @@

Computation と Meta Computation

Aliceでは、計算の本質的な処理をComputatin、Computationとは直接関係ないが別のレベルでそれを支える処理をMeta Computationとして分けて考える。
Alice のComputationは、keyによりDSを待ち合わせ、DSが揃ったCSを並列に実行する処理。
分散トポロジーの構成、通信の切断・再接続時の処理やデータの表現形式の選択など、Computationを支えている処理。
分散トポロジーの構成、通信の切断・再接続時の処理などはMeta ComputationとしてAliceが提供
プログラマは目的の処理だけ記述し通信部分などはMeta Computationを指定することでシンプルな記述を実現

@@ -229,32 +188,11 @@

Computation と Meta Computation

分散環境構築などの複雑な処理をAliceがMeta Computationとして提供する
プログラマは目的の処理だけ記述し通信部分などはMeta Computationを指定する

- - -

- -

TreeVNC

TreeVNCへの応用

Aliceを用いて実装する実用的な分散プログラムの例題
当研究室で開発したノードを木構造に配置して負荷分散を行う授業向け画面共有システム
TightVNCがもとになっている
-

- - -

- -

AliceVNC

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

@@ -268,7 +206,7 @@

TreeTopologyの構成・管理（Topology Manager）

ノード間通信の切断時・再接続時の処理（ClosedEventManager）

ノードの接続状態確認（KeepAlive）

子ノードへのデータの転送

子ノードへのデータの転送(flip)

データの圧縮

@@ -276,41 +214,11 @@

Dynamic Topology Manager

Topology Managerを立ちあげ、各ノードはTopology Managerに参加表明をし接続すべきノードの情報を要求する
-

- - -

- -

Dynamic Topology Manager

Topology Managerは参加表明を受け取った順にTree構造になるよう接続情報を送る
-

- - -

- -

Dynamic Topology Manager

各ノードが受け取った情報をもとにRemote DSMを立ちあげ接続し合うことでTree構造が作られる
-

- - -

Meta Computationの追加

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

@@ -318,34 +226,24 @@

転送機能の追加

AliceではInputDSをReceiverに受け取ったあと、Receiverから任意の型で取り出し、操作してOutputDSとして出力する（コピーする）
TreeVNCのように受け取ったデータをそのまま転送したいときには無駄
Input DSをそのままOutput DSとしてコピーせず転送できる flipメソッド を追加。put/updateと同じように扱える。
- flip(String managerKey, String key, Receiver receiver)

- - -

圧縮表現(Meta DS)の追加

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

- -

+
1. 一般的なJavaのオブジェクト -　　　　LocalDSMにputしたときの形式 -2. MessagePackでシリアライズ化されたバイナリオブジェクト -　　　　RemoteDSMにputしたときの形式 -3. 2をさらに圧縮したバイナリオブジェクト -　　　　今回追加した形式 +　LocalDSMにputしたときの形式 + +2. シリアライズ化されたバイナリオブジェクト +　RemoteDSMにputしたときの形式 + +3. 2を圧縮したバイナリオブジェクト +　今回追加した形式	- +	+

@@ -354,18 +252,6 @@

MessagePackとは

Sadayuki Furuhashiが開発したシリアライズのための機能をまとめたオープンソースライブラリ。
シリアライズ/デシリアライズを高速に行うことができ、整数、浮動小数点数、Boolean、文字列、配列、連想配列、nilをバイト列にシリアライズできる。
JSONのようにプログラミング言語に依存しないデータの表現形式として使用できる。
AliceではJavaオブジェクトへの対応のためにJavassistも用いている。

- - -

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

Local と Remote それぞれに圧縮表現を扱う Compressed DSM を追加

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

NodeAでNodeBのcompressed RemoteDSM に対してDSをput
-

- - -

- -

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

DS が圧縮表現を持っていなければCompressed DSM内部で圧縮表現を生成してput -

- - -

- -

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

RemoteDSMがAliceの送信パケットをNodeBのLocalDSMに送る
-

- - -

- -

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

NodeBのLocalDSMでは圧縮表現のみのDSとして保存する
-

- - -

- -

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

setKey()でtake/peekで呼ばれたらReceiverにDSが渡される
-

- - -

- -

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

castメソッドである asClass() が解凍・デシリアライズされた表現を作って渡す
-

- - -

- -

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

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

@@ -467,18 +293,7 @@

性能比較 - 実験内容

木の段数ごとにメッセージの到達にどれぐらい時間がかかっているかを計測
講義内で学生に協力してもらい、最大 17 名の接続があった
-

- - -

- -

性能比較 - 実験結果

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

コード量比較

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

コード複雑度比較

循環的複雑度を用いる
コード内の線形独立な経路の数。if や forが多いほど複雑度が高い。
計測にはIntelliJのプラグイン「MetricsReloaded」を使用

@@ -572,69 +386,28 @@

Meta Computationの評価結果

AliceVNCはコードの修正量・複雑度共に低く抑えながらTreeVNC と同等の性能を持つ分散アプリケーションを記述する能力があった

- - -

- -

Aliceと他言語等との比較(1) - Erlang

まとめ

共通点 -
- タスクをプロセスと呼ばれるメモリを共有しないスレッドに分割
- 共有メモリにアクセスするためのメモリロックの仕組みを必要としない
-
相違点 -
- 複数のデータの待ち合わせ処理はユーザーが書く
- Topologyの構成等はユーザーが書く
-
Alice が実用的なアプリケーションを記述するための Meta Computation として、Meta Data Segmentに複数の表現のデータを同時に持たせることで圧縮機能を実装した。同様の手法を用いれば暗号表現などへの対応もでき自由度の高い通信を行うことが可能になる。
TreeVNCをAlice上で実装し比較を行った結果、変更量の少ないシンプルな記述でTreeVNCの基本機能を実現でき、同等の性能を出すことに成功した。
AliceのMeta Computationが拡張性・信頼性の高い実用的な分散アプリケーションの構築に有用であることが確認された。

Aliceと他言語等との比較(2) - Akka

今後の課題

共通点 -
- tell/ask が Alice の put/take に対応
- 通信部分等を子アクターで分離し階層化
-
相違点 -
- データに名前がついていないので何が来るかわかりづらい
- Actorごとに受け取ったデータの判別処理をユーザーが書く
- Topologyの構成はユーザーが書かないといけない
- 転送などのオーバーヘッドを考慮したメタプロトコル(Meta DS)が存在しない
-
TreeVNCでは拡張が困難であった別ネットワーク間の通信もTopology Manager を用いれば容易に拡張できると考えられる
+

まとめ

Alice が実用的なアプリケーションを記述するための Meta Computation として、データに多態性を持たせる圧縮機能やゼロコピー転送の機能を実装した。
TreeVNCをAlice上で実装し比較を行った結果、シンプルな記述でTreeVNCの基本機能を実現でき、同等の性能を出すことに成功した
AliceのMeta Computationが信頼性の高い実用的な分散アプリケーションの構築に有用であることが確認された

- - -

- -

今後の課題

APIの再設計
- -

- -

今後の課題

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

- - -

- -

Dynamic Topology Manager

- - -

- -

CodeSegment の例

RemoteDSM から DSをtakeし、LocalDSM に put を10回繰り返す　　 -

- - -

- -

CodeSegment の例

RemoteDSM から DSをtakeし、LocalDSM に put を10回繰り返す
CSはInputDSを持たないStartCSからはじまる
-

- - -

- -

StartCodeSegmentの例

public class RemoteStartCodeSegment extends CodeSegment {
-
-    @Override
-    public void run() {
-        RemoteIncrement cs = new RemoteIncrement();//CSを生成
-		ods.put("local", "num", 0);
-    }
-
-}
-

- - -

- -

StartCodeSegmentの例

public class RemoteStartCodeSegment extends CodeSegment {
-
-    @Override
-    public void run() {
-        RemoteIncrement cs = new RemoteIncrement();
-		ods.put("local", "num", 0);//DSをLocalDSMにput
-    }
-
-}
-

- - -

- -

CodeSegment の例

public class RemoteIncrement extends CodeSegment {
-
-    public Receiver num = ids.create(CommandType.TAKE);//DSの受け皿を作る
-
-    public RemoteIncrement(){
-		num.setKey("remote", "num");
-    }
-
-    @Override
-    public void run() {
-        int n = num.asClass(Integer.class);
-        if (n == 10) System.exit(0);
-        RemoteIncrement cs = new RemoteIncrement();
-        ods.put("local", "num", ++n);
-    }
-
-}
-

- - -

- -

CodeSegment の例

public class RemoteIncrement extends CodeSegment {
-
-    public Receiver num = ids.create(CommandType.TAKE);
-
-    public RemoteIncrement(){
-		num.setKey("remote", "num");//CSにInputDSをセット。待ち合わせが発生。
-    }
-
-    @Override
-    public void run() {
-        int n = num.asClass(Integer.class);
-        if (n == 10) System.exit(0);
-        RemoteIncrement cs = new RemoteIncrement();
-        ods.put("local", "num", ++n);
-    }
-
-}
-

- - -

- -

CodeSegment の例

public class RemoteIncrement extends CodeSegment {
-
-    public Receiver num = ids.create(CommandType.TAKE);
-
-    public RemoteIncrement(){
-		num.setKey("remote", "num");
-    }
-
-    @Override
-    public void run() {
-        int n = num.asClass(Integer.class);//InputDSをキャストして取得
-        if (n == 10) System.exit(0);
-        RemoteIncrement cs = new RemoteIncrement();
-        ods.put("local", "num", ++n);
-    }
-
-}
-

- - -

- -

CodeSegment の例

public class RemoteIncrement extends CodeSegment {
-
-    public Receiver num = ids.create(CommandType.TAKE);
-
-    public RemoteIncrement(){
-		num.setKey("remote", "num");
-    }
-
-    @Override
-    public void run() {
-        int n = num.asClass(Integer.class);
-        if (n == 10) System.exit(0);//num=10なら終了
-        RemoteIncrement cs = new RemoteIncrement();
-        ods.put("local", "num", ++n);
-    }
-
-}
-
-

- - -

- -

CodeSegment の例

public class RemoteIncrement extends CodeSegment {
-
-    public Receiver num = ids.create(CommandType.TAKE);
-
-    public RemoteIncrement(){
-		num.setKey("remote", "num");
-    }
-
-    @Override
-    public void run() {
-        int n = num.asClass(Integer.class);
-        if (n == 10) System.exit(0);
-        RemoteIncrement cs = new RemoteIncrement();//次のCSを生成
-        ods.put("local", "num", ++n);
-    }
-
-}
-

- - -

- -

CodeSegment の例

public class RemoteIncrement extends CodeSegment {
-
-    public Receiver num = ids.create(CommandType.TAKE);
-
-    public RemoteIncrement(){
-		num.setKey("remote", "num");
-    }
-
-    @Override
-    public void run() {
-        int n = num.asClass(Integer.class);
-        if (n == 10) System.exit(0);
-        RemoteIncrement cs = new RemoteIncrement();
-        ods.put("local", "num", ++n);//インクリメントしたDSをput
-    }
-
-}
-

分散フレームワークAliceのPC画面配信システムへの応用

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

研究目的(1/3)

研究目的(2/3)

研究目的(3/3)

Data Segment と CodeSegment

Data Segment Manager

Data Segment Manager

Data Segment API

Computation と Meta Computation

Computation と Meta Computation

TreeVNC

TreeVNCへの応用

AliceVNC

Dynamic Topology Manager

Dynamic Topology Manager

Dynamic Topology Manager

Meta Computationの追加

転送機能の追加

圧縮表現(Meta DS)の追加

MessagePackとは

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

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

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

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

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

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

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

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

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

性能比較 - 実験内容

性能比較 - 実験結果

性能比較 - 実験結果

コード量比較

コード量比較

コード複雑度比較

コード複雑度比較

Meta Computationの評価結果

Aliceと他言語等との比較(1) - Erlang

まとめ

Aliceと他言語等との比較(2) - Akka

今後の課題

まとめ

今後の課題

今後の課題

今後の課題

Dynamic Topology Manager

CodeSegment の 例

CodeSegment の 例

StartCodeSegmentの例

StartCodeSegmentの例

CodeSegment の 例

CodeSegment の 例

CodeSegment の 例

CodeSegment の 例

CodeSegment の 例

CodeSegment の 例

CodeSegment の例

CodeSegment の例

CodeSegment の例

CodeSegment の例

CodeSegment の例

CodeSegment の例

CodeSegment の例

CodeSegment の例