title: 分散フレームワークAliceの圧縮機能
author: 照屋のぞみ
profile:琉球大学 工学部 情報工学科 4年

# 研究目的
* 当研究室が開発している並列分散フレームワークAliceではスケーラブルな分散プログラムを信頼性高く記述できる環境を実現する。
* Aliceのメタ計算として、通信が切断した際の処理やデータを圧縮する処理等を提供することで、プログラマがコードを大きく変更することなくプログラムの振る舞いを変えることを可能にする。

# Data Segment と Code Segment
* Aliceではデータを **Data Segment(DS)** 、タスクを **Code Segment(CS)** という単位に分割してプログラミングを行う。
* AliceはJavaで実装されており、CS をユーザーが記述する際には CodeSegment.class を継承することで CS で使用する API を利用する事ができる。
* DSはAliceが内部にもつデータベースにより管理されており、CSはDSに対応する一意のkeyを使ってDSを操作する。

# Data Segment と Code Segment
* CSはInput DS(入力されるDS)とOutput DS(出力されるDS)を持つ。
* CSはkeyで指定されたDSが揃うと実行されるという性質を持つ。
![opt](./images/dsandcs.svg)

# CodeSegmentの依存関係
* データの依存関係にないCSは並列実行される
* データの依存関係がある場合は Input DS が揃うと順に実行される
![opt](./images/dsandcs2.svg)

# Data Segment
* 整数や文字列などの基本的なデータの集まり
* Aliceの場合はJavaオブジェクトに対応

# Data Segment Manager
* DS の集合体であるデータベースを Alice では DS Manager(DSM) と呼ぶ。  
* DSM 内の DS には対になる String型のkey が存在し、 DSM 名と key を指定しすることで DS の保存、取得を行う。
* DS の追加  
		put(String managerKey, String key, Object val)  
* DS の取得  
		take(String managerKey, String key)  

<!--![opt](./images/dsm.svg)-->

# Data Segment Manager
* Local DSM … 各ノード固有のデータベース。
* Remote DSM … 他のノードの Local DSM の proxy。接続しているノードの数だけ存在する。  
		![opt](./images/remote_datasegment.svg){:width="450px"}


# Data Segment の表現
* DSは複数の表現を同時に持っており、現在は3種類の表現がある。
	1. 一般的な Java のクラスオブジェクト
	2. MessagePack for Java でシリアライズ化されたバイナリオブジェクト。Remoteとの通信の際に用いる。
	3. 2 を圧縮したバイナリオブジェクト。圧縮機能の一部として今回追加。  

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

# CS と Input DS の対応付け
* setKey()にtakeコマンドをセットすることで Input DS を指定する
* 実際にtakeしたデータを参照するときには、asClass()を用いて任意のJavaのオブジェクトとして扱えるようにする  

# CS の 例
RemoteDSM から DSをtakeし、LocalDSM に put を10回繰り返す
```java
public class RemoteIncrement extends CodeSegment {

    public Receiver num = ids.create(CommandType.TAKE);

    @Override
    public void run() {
        int num = this.num.asClass(Integer.class);
        if (num == 10) System.exit(0);

        RemoteIncrement cs = new RemoteIncrement();
        cs.num.setKey("remote", "num");

        ods.put("local", "num", num);
    }

}
```

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

# Computation
* Aliceでは、計算の本質的な処理をComputatin、Computationとは直接関係ないが別のレベルでそれを支える処理をMeta Computationとして分けて考える。
* Alice の Computationは、keyによりDSを待ち合わせ、DSが揃ったCSを並列に実行する処理。
* TreeVNC の Computationは、VNCサーバからデータを受け取って表示する処理。

# Meta Computation
* 通信の切断・再接続時の処理や分散トポロジーの構成、データの表現形式の選択など、Computationを支えている処理。
* TreeVNCの場合、VNCサーバのデータを各VNCノードにコピーする処理。
* Aliceの機能を追加するということは Meta Computation を追加すると言い換えられる

# TreeVNCで用いるAliceのMeta Computation
* TreeTopologyの構成
* ノード間通信の切断時・再接続時の処理
* データの圧縮
* 子ノードへのデータの複製


# データの転送 - DSMとAPIの追加
* Local と Remote それぞれに圧縮表現を扱う Compressed DSM を追加。
* 指定する DSM を Compressed DSM に変えるだけで扱うデータ表現を変更できる  
		put(String **"compressed"** + managerKey, String key, Object val)  
		take(String **"compressed"** + managerKey, String key)  

# データの転送 - データ表現の自動生成
* DS が圧縮表現を持っていれはそれをそのまま子ノードにputする
* 持っていなければその時点でCompressed DSM内部で圧縮表現を生成してputする
* DS はオブジェクト表現と圧縮表現を同時にもつため、TreeVNCでは受け取った画面データを伸長をした後、転送のために再圧縮することはない。

# データの受け取り - 任意の形式での取得
* 圧縮表現で画面データ受け取り、Compressed DSM 内に格納。
* TightVNCが画面表示のためにデータを必要としたときに、 asClass() を用いて任意の形式でデータを取り出す。
* asClass() は DS のcastメソッドであり、内部で伸長と MessagePack での変換を行う。

# データの受け取り - Aliceの通信パケット変更
* 通信ヘッダにデータの状態を表すフラグを追加したことで、受け取ったデータを適切な形式でDSM内に格納できる。
* 圧縮前と圧縮後のデータサイズを入れたことにより、受け取ったデータの適切な伸長が可能。

<table style="border-collapse: collapse;border:1px solid #000000;">
	<td style="border:1px solid #000000;"> serialized </td>
	<td style="border:1px solid #000000;">データ本体のシリアライズ状態を示す</td>
	</tr>
	<tr>
	<td style="border:1px solid #000000;"> compressed </td>
	<td style="border:1px solid #000000;">データ本体の圧縮状態を示す</td>
	</tr>
	<tr>
	<td style="border:1px solid #000000;"> objectDataSize </td>
	<td style="border:1px solid #000000;">圧縮前のオブジェクトのデータサイズを表す</td>
	</tr>
	<tr>
	<td style="border:1px solid #000000;"> dataSize </td>
	<td style="border:1px solid #000000;">送信するDSのデータサイズを表す</td>
	</tr>
</table>

# Aliceと他言語等との比較(1) - Erlang
* ネットワークに依存しない通信が可能

* Topologyは自分で管理

# Aliceと他言語等との比較(1) - Linda
* keyでタプルというデータの集合を管理している
* in/outでAliceのput/takeに対応する操作を行う

* タスクはinで単一のタプルを待つ
* MetaComputationがない

# Aliceと他言語等との比較(1) - Corba
* オブジェクト間のRPC

* DSがない。keyという概念がない。
* データの待ち合わせがない

# Aliceと他言語等との比較(1) - HTTP
* get/putで通信を行う
* URLがデータベースのkeyとなる

* MIME形式で送信。複数の表現を持つMeta Computationがない。  
* セッション管理はクライアント自身がやる  
* 並列処理できない  
* get/putをRPC的に扱わない


# TreeVNCとAliceを用いたTreeVNCの比較
* TreeVNC  
	通信プロトコルを定義や圧縮を自前で行う  
	通信スレッドを複数作成  
	様々な部分で通信APIを呼び出す  

* Aliceを用いたTreeVNC  
	Aliceと接続する最小限の変更  
	木の構成部分や圧縮形式での通信はMeta Computation  

# TreeVNCとAliceを用いたTreeVNCの比較
* TightVNCからのコードの増加量
* Aliceを用いれば通常の TreeVNC の 20% の行数で記述できる。

<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;"> TreeVNC </td>
	<td style="border:1px solid #000000;padding:5px 15px 5px 15px;">5049</td>
	<td style="border:1px solid #000000;padding:5px 15px 5px 15px;">14191</td>
	</tr>
	<tr>
	<td style="border:1px solid #000000;padding:5px 15px 5px 15px;"> Aliceを用いたTreeVNC </td>
	<td style="border:1px solid #000000;padding:5px 15px 5px 15px;">989</td>
	<td style="border:1px solid #000000;padding:5px 15px 5px 15px;">2355</td>
	</tr>
</table>

# まとめ
* Alice が実用的なアプリケーションを記述するための Meta Computation として、データに多態性を持たせ、指定するDSMによってデータ表現を変える機能を実装した。
* これによりユーザが記述する Computation 部分を大きく変えずに自由度の高い通信を行うことが可能になった。
* 同様の手法により、暗号形式・JSON 形式など複数のデータ表現を扱えるように拡張できる。
* 今後の課題としては、圧縮機能を TreeVNC で用 いることで有効性を測る必要がある。