Mercurial > hg > Papers > 2016 > nozomi-thesis

title: 分散フレームワークAliceのPC画面配信システムへの応用
author: 照屋のぞみ  河野真治
profile:琉球大学 工学部 情報工学科

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

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

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


# Data Segment と Code Segment
* Aliceではデータを **Data Segment(DS)** 、タスクを **Code Segment(CS)** という単位に分割して依存関係を記述することでプログラミングを行う。
* CSはInput DS(入力されるDS)とOutput DS(出力されるDS)を持つ。
* CSはkeyで指定されたDSが揃うと実行されるという性質を持つ。
![opt](./images/dsandcs.svg){:width="60%"}

# CodeSegmentの依存関係
* データの依存関係にないCSは並列実行される
* データの依存関係がある場合は Input DS が揃うと順に実行される
* DSはCSに専有されるためロックの記述を必要としない
![opt](./images/dsandcs2.svg){:width="60%"}

# 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的に処理される
![opt](./images/KeyDS.svg){:width="50%"}

# Data Segment Manager
* Local DSM … 各ノード固有のデータベース。
* Remote DSM … 他のノードの Local DSM の proxy。接続しているノードの数だけ存在する。
![opt](./images/remote_datasegment.svg){:width="50%"}

# Data Segment API
* DS の追加
	* put(String managerKey, String key, Object val)
	* update(String managerKey, String key, Object val)  ※先頭DSを削除してからput
* DS の取得
	* take(String managerKey, String key)
	* peek(String managerKey, String key)  ※DSMから削除されない

* take/peekは実際にはcreate()とsetKey()によって行われる
* create()でDSの受け皿を作っておき、setKey()にkeyをセットすることで Input DS を指定する

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

# Computation と Meta Computation
* DS/CSの接続の間にMeta Computationが実行されている
* AliceのMeta ComputationもCS/DSにより実現される
* Meta ComputationはCS の処理を支えるMeta CSとMeta CSに管理されるMeta DSに分けられる
![opt](./pictures/MetaCSDS.svg){:width="70%"}

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

# TreeVNC
* Aliceを用いて実装する実用的な分散プログラムの例題
* 当研究室で開発したノードを木構造に配置して負荷分散を行う授業向け画面共有システム
* TightVNCがもとになっている
![opt](./images/treeVNC.svg){:width="40%"}

# AliceVNC
* 画面処理や分散処理が混在する複雑なTreeVNCも、Aliceを用いればTightVNCからの変更が少ない見通しの良い記述で構成可能
![opt](./images/AliceVNC.svg){:width="50%"}

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

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

# Dynamic Topology Manager
* Topology Managerを立ちあげ、各ノードはTopology Managerに参加表明をし接続すべきノードの情報を要求する
![opt](./pictures/tree1.svg){:width="60%"}

# Dynamic Topology Manager
* Topology Managerは参加表明を受け取った順にTree構造になるよう接続情報を送る
![opt](./pictures/tree2.svg){:width="60%"}

# Dynamic Topology Manager
* 各ノードが受け取った情報をもとにRemote DSMを立ちあげ接続し合うことでTree構造が作られる
![opt](./pictures/tree3.svg){:width="60%"}

# Meta Computationの追加
* TreeVNCの数MByteの画面差分データを配信し続けるためデータを圧縮している
* 画面データを圧縮して送る → 解凍して画面表示 → 再圧縮して子ノードへ転送
* 再圧縮オーバーヘッドなしにゼロコピー転送する機能が必要
* 圧縮のMeta Computationと転送のMeta Computationを追加した

# 転送機能の追加
* 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として以下の表現を同時に持たせる

<table style="border:none;">
<tr><td>
1. 一般的なJavaのオブジェクト<br>
　　　　LocalDSMにputしたときの形式 <br>
2. MessagePackでシリアライズ化されたバイナリオブジェクト  <br>
　　　　RemoteDSMにputしたときの形式  <br>
3. 2をさらに圧縮したバイナリオブジェクト  <br>
　　　　今回追加した形式  <br>
</td>
<td>
<img src="./pictures/compressDS.svg" width="90%">
</td>
</tr>
</table>


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

# 圧縮表現を扱うDSMとAPIの追加
* Local と Remote それぞれに圧縮表現を扱う Compressed DSM を追加
* DSを圧縮したい場合は指定する DSM を Compressed DSM に変える
* 圧縮するコードとしないコードで変更が少ない
```java
	put("Remote", "Key", val);
	put("compressedRemote", "Key", val);
```

# 圧縮表現がオンデマンドに作られる
* NodeAでNodeBのcompressed RemoteDSM に対してDSをput
![opt](./pictures/flow1.svg){:width="80%"}

# 圧縮表現がオンデマンドに作られる
* DS が圧縮表現を持っていなければCompressed DSM内部で圧縮表現を生成してput
![opt](./pictures/flow2.svg){:width="80%"}

# 圧縮表現がオンデマンドに作られる
* RemoteDSMがAliceの送信パケットをNodeBのLocalDSMに送る
![opt](./pictures/flow3.svg){:width="80%"}

# 圧縮表現がオンデマンドに作られる
* NodeBのLocalDSMでは圧縮表現のみのDSとして保存する
![opt](./pictures/flow4.svg){:width="80%"}

# 圧縮表現がオンデマンドに作られる
* setKey()でtake/peekで呼ばれたらReceiverにDSが渡される
![opt](./pictures/flow5.svg){:width="80%"}

# 圧縮表現がオンデマンドに作られる
* castメソッドである **asClass()** が解凍・デシリアライズされた表現を作って渡す
![opt](./pictures/flow6.svg){:width="80%"}

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

# Meta Computationの評価
TreeVNCとAliceVNCを比較した

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

# 性能比較 - 実験内容
* 木の段数ごとにメッセージの到達にどれぐらい時間がかかっているかを計測
* 講義内で学生に協力してもらい、最大 17 名の接続があった
![](./pictures/delay.svg){:width="50%"}![](./pictures/delay2.svg){:width="50%"}

# 性能比較 - 実験結果
* 3段目の計測結果
* 同じ傾向から同等の処理性能があることがわかった

<table style="border:none;">
	<tr>
	<td><img src="./pictures/TreeVNC_depth3.svg" width="80%"></td>
	<td><img src="./pictures/AliceVNC_compress_depth3.svg" width="80%"></td>
	</tr>
	<tr>
	<td align="center">TreeVNC</td>
	<td align="center">AliceVNC</td>
	</tr>
</table>


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

<table style="border-collapse: collapse;border:1px solid #000000;">
	<th style="border:1px solid #000000;padding:5px 15px 5px 15px;"></th>
	<th style="border:1px solid #000000;padding:5px 15px 5px 15px;"> 行数 </th>
	<th style="border:1px solid #000000;padding:5px 15px 5px 15px;">単語数</th>
	<th style="border:1px solid #000000;padding:5px 15px 5px 15px;">TightVNCからの変更行数</th>
	<tr>
	<td style="border:1px solid #000000;padding:5px 15px 5px 15px;"> TreeVNC </td>
	<td style="border:1px solid #000000;padding:5px 15px 5px 15px;">19502</td>
	<td style="border:1px solid #000000;padding:5px 15px 5px 15px;">73646</td>
	<td style="border:1px solid #000000;padding:5px 15px 5px 15px;">7351</td>
	</tr>
	<tr>
	<td style="border:1px solid #000000;padding:5px 15px 5px 15px;"> AliceVNC </td>
	<td style="border:1px solid #000000;padding:5px 15px 5px 15px;">14647</td>
	<td style="border:1px solid #000000;padding:5px 15px 5px 15px;">59217</td>
	<td style="border:1px solid #000000;padding:5px 15px 5px 15px;">1129</td>
	</tr>
	<tr>
	<td style="border:1px solid #000000;padding:5px 15px 5px 15px;"> 減少率 (%)</td>
	<td style="border:1px solid #000000;padding:5px 15px 5px 15px;">25</td>
	<td style="border:1px solid #000000;padding:5px 15px 5px 15px;">20</td>
	<td style="border:1px solid #000000;padding:5px 15px 5px 15px;">75</td>
	</tr>
</table>

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

<table style="border-collapse: collapse;border:1px solid #000000;">
	<th style="border:1px solid #000000;padding:5px 15px 5px 15px;"></th>
	<th style="border:1px solid #000000;padding:5px 15px 5px 15px;"> 平均値 </th>
	<th style="border:1px solid #000000;padding:5px 15px 5px 15px;">最高値</th>
	<tr>
	<td style="border:1px solid #000000;padding:5px 15px 5px 15px;"> TightVNC </td>
	<td style="border:1px solid #000000;padding:5px 15px 5px 15px;">13.63</td>
	<td style="border:1px solid #000000;padding:5px 15px 5px 15px;">97</td>
	</tr>
	<tr>
	<td style="border:1px solid #000000;padding:5px 15px 5px 15px;"> TreeVNC </td>
	<td style="border:1px solid #000000;padding:5px 15px 5px 15px;">15.33</td>
	<td style="border:1px solid #000000;padding:5px 15px 5px 15px;">141</td>
	</tr>
	<tr>
	<td style="border:1px solid #000000;padding:5px 15px 5px 15px;"> AliceVNC</td>
	<td style="border:1px solid #000000;padding:5px 15px 5px 15px;">10.95</td>
	<td style="border:1px solid #000000;padding:5px 15px 5px 15px;">99</td>
	</tr>
</table>


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


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

# Aliceと他言語等との比較(1) - Erlang
* 共通点
	* タスクをプロセスと呼ばれるメモリを共有しないスレッドに分割
	* 共有メモリにアクセスするためのメモリロックの仕組みを必要としない

* 相違点
	* 複数のデータの待ち合わせ処理はユーザーが書く
	* Topologyの構成等はユーザーが書く

# Aliceと他言語等との比較(2) - Akka
* 共通点
	* tell/ask が Alice の put/take に対応
	* 通信部分等を子アクターで分離し階層化

* 相違点
	* データに名前がついていないので何が来るかわかりづらい
	* Actorごとに受け取ったデータの判別処理をユーザーが書く
	* Topologyの構成はユーザーが書かないといけない
	* 転送などのオーバーヘッドを考慮したメタプロトコル(Meta DS)が存在しない

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

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

# 今後の課題
* TreeVNCでは拡張が困難であった別ネットワーク間の通信もTopology Manager を用いれば容易に拡張できると考えられる
![opt](./pictures/overNAT.svg){:width="60%"}

# Dynamic Topology Manager
![](./pictures/tree1.svg){:width="33%"}![](./pictures/tree2.svg){:width="33%"}![](./pictures/tree3.svg){:width="33%"}


# CodeSegment の 例
* RemoteDSM から DSをtakeし、LocalDSM に put を10回繰り返す
![opt](./pictures/remoteTest.svg){:width="70%"}

# CodeSegment の 例
* RemoteDSM から DSをtakeし、LocalDSM に put を10回繰り返す
* CSはInputDSを持たないStartCSからはじまる
![opt](./pictures/remoteTest2.svg){:width="70%"}

# StartCodeSegmentの例
```java
public class RemoteStartCodeSegment extends CodeSegment {

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

}
```

# StartCodeSegmentの例
```java
public class RemoteStartCodeSegment extends CodeSegment {

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

}
```

# CodeSegment の 例
```java
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 の 例
```java
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 の 例
```java
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 の 例
```java
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 の 例
```java
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 の 例
```java
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
    }

}
```


<style type="text/css">
<!--
*{
	font:nomal 100% 'PT Sans';
}

ul > li{
	list-style-type:disc;
}

.slide h1{
	text-align:left;
	color:#777777;
	font:bold 40px/1.13 'PT Sans', sans-serif;
	margin-bottom: 50px;
}

div#slide1 h1{
	text-align:left;
	color:#777777;
	font:bold 60px 'PT Sans', sans-serif;
	margin-bottom: 50px;
}

pre > code{
	font-family:'Droid Sans Mono', 'Courier New', monospace;
}

img[alt="opt"]{
	display: block;
	margin-left: auto;
	margin-right: auto;
}

img[alt="right"]{
	margin-right: 0;
}

table {
	margin-left: auto;
	margin-right: auto;
}

th {
    font-size: 120%;
}
-->
</style>
author	Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
date	Wed, 17 Feb 2016 11:25:52 +0900
parents
children	ef17e4dc6216