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

# 研究背景(1/2)
* 信頼性とスケーラビリティに優れた分散プログラムをプログラマが一から記述することは容易ではない。
* 本研究室ではデータを *Data Segment* 、タスクを *Code Segment* という単位で分割して記述する**並列分散フレームワークAlice**の開発を行っている。
* Aliceは分散環境の構築のためのAPIが提供されており、スケーラブルな分散プログラムを信頼性高く記述できる環境を実現する。  

# 研究背景(1/2)
* 水族館の例題等において、Aliceが分散プログラムを記述する能力を有することは確認された。
* 実用的な分散プログラムを作成するためには、圧縮形式のデータで通信する機能等が必要だとわかった。

# 研究目的
* Aliceに圧縮機能等を追加することにより、Data Segmentの多態性を実現しノード間通信における自由度の向上を図る。  

# Aliceの概要(1) - Data Segment
* 複数の関係のない要素を1つのデータオブジェクトで表現した場合、全ての操作でlockが必要になり、スケラビリティーを低下させる。
* Alice はデータを細かく分割して記述する。その分割されたデータを **Data Segment(DS)** と呼ぶ。

# Aliceの概要(2) - Data Segment Manager
* DS は queue に保存される。queue には対 になる key し、 key を指定して DS の保存、取得を行う。
* queue の集合体であるデータベースデータベースを Alice では DS Manager(DSM) と呼ぶ。  
![opt](./pictures/dsm.svg)

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

# Aliceの概要(3) - Data Segment API
DSMに対して以下のコマンドを送り操作できる  

<table style="border-collapse: collapse;border:1px solid #000000;">
  <tr>
    <td style="border:1px solid #000000;"> put</td>
    <td style="border:1px solid #000000;">データを追加する</td>
  </tr>
  <tr>
    <td style="border:1px solid #000000;"> update </td>
    <td style="border:1px solid #000000;">データを更新する</td>
  </tr>
	<tr>
		<td style="border:1px solid #000000;"> peek</td>
		<td style="border:1px solid #000000;">データを取得する</td>
	</tr>
	<tr>
	<td style="border:1px solid #000000;"> take</td>
	<td style="border:1px solid #000000;">データを取得する。取得したデータはDSMから削除される。</td>
	</tr>
</table>

# Aliceの概要(4) - Data Segment の表現
* 一般的な Java のクラスオブジェクト
	* LocalDSM に put された場合は一般的な Java のクラスオブジェクトとして enQueue される。
* MessagePack を用いて変換した byte[]で表現されたバイナリオブジェクト
	* RemoteDSM に put された場合は通信時に byteArray に変換されたバイナリオブジェクトが enQueue される。

# Aliceの概要(5) - Code Segment  
* Alice上で実行されるタスクの単位を **Code Segment(CS)** と呼ぶ。
* 複数のDSが入力され、その結果をDSとして出力するfunctionと捉えられる。
* CS をユーザーが記述する際には CS を継承して記述することにより CS で使用する API を利用する事ができる。

# Aliceの概要(5) - Code Segment  
* 入力されるDSをInput DS、出力されるDSをOutput DSと呼ぶ。
* keyで指定されたDSが揃うと実行されるという性質を持つ。
![opt](./images/dsandcs.svg)

# Aliceの概要(6) - CodeSegmentの依存関係
* データの依存関係にないCSは並列実行される
* データの依存関係がある場合は依存を解決した順に実行される
* 並列度あげるために、処理を細かく記述し、依存するDSを少なくする
![opt](./images/dsandcs2.svg)

# AliceのMeta Computation(1/2)
* 並列指向プログラミング言語 Erlang では、分散環境の構築等の処理は全てプログラマが記述しなければいけない。
* Aliceではプログラマが記述する部分を *Computation*、Aliceが提供するComputationを支える部分を *Meta Computation* として分けて捉えている。
* 分散環境の構築等の処理等は全てMeta Computationが行うためプログラマがシンプルに分散プログラムを記述できる環境を提供している。

# AliceのMeta Computation(2/2)
* AliceのComputation
	* keyによりData Segmentを待ち合わせてCode Segmentを実行する

* AliceのMeta Computation
	* Javaで記述したAliceの実装システム

* Aliceの機能を追加するということは Meta Computation を追加すると言い換えられる
* Meta Computation も CS と DS により表現される。

# AliceVNC
* 研究室では授業向け画面共有システムTreeVNCではノード同士を接続させ、木構造を構成することで負荷分散を行う
![opt](./images/treeVNC.svg)

# Alice の新機能
* Alice が実用的なアプリケーションを記述する能力をもつことを確認するため、TreeVNC を Alice を用いて実装した AliceVNC の作成を行った。
* AliceVNCの実装で必要となった以下の機能をMeta Computation として実装した。  
	* 転送機能　… Input DS を Output DS として転送する
	* 圧縮機能　… DS Manager の指定によってDSの表現を切り替える

# 転送機能
* 通常、Input DSに変更を加えOutput DSとして出力する場合DSのコピーが行われる。
* AliceVNCのようにInput DS をそのまま子ノードに Output DS として出力する場合、コピーを行なうのは無駄。
* Input DSをコピーせずそのままOutput DSに渡すMeta Computationとして転送機能を実装した。

# 転送機能
```java
	public void flip(Receiver receiver) {
		 DataSegment.getLocal().put(receiver.key, receiver.getReceiveData(), null);
	}
```

# 圧縮機能
* AliceVNCは、ノードは受け取った画面データを描画すると同時に、子ノードの Remote DSM に送信する。
* ノードは DS を受信するとそれを一度解凍して画面を表示し、再圧縮して子ノードに送信する。
* 圧縮状態のまま子ノードに送信ができれば、解凍・再圧縮するオーバーヘッドを無くすことができる。

# 圧縮機能 - Data Segmentの表現の変更
1つの Data Segment に対し以下の3種類の表現を同時に持たせ、必要に応じた形式で DS を扱う。
	1. 一般的な Java のクラスオブジェクト
	2. MessagePack for Java でシリアライズ化され たバイナリオブジェクト
	3. 2 を圧縮したバイナリオブジェクト

# 圧縮機能 - Data Segmentの表現の変更
```java
	public class ReceiveData {
		private Object val = null;
		private byte[] messagePack = null;
		private byte[] zMessagePack = null;
	}
```

# 圧縮機能 - DSMの追加
* Local と Remote それぞれに圧縮表現を扱う Compressed DSM を追加した。
* Compressed DSM にputする場合
	* DS が圧縮表現を持っていればそれをputする
	* 持っていなければその時点で圧縮表現を作ってputする

# 圧縮機能 - 任意の表現でDSを取得
* ReceiveData内にあるDSのcastメソッドであるasClass()を用いる
```java
	public <T> T asClass(Class<T> clazz) {
		if (val != null) { return (T) val; }

		if (zMessagePack != null && messagePack == null) {
			messagePack = unzip(zMessagePack, dataSize);
		}

		return packer.read(messagePack, clazz);
	}
```

# 圧縮機能 - API設計  
通常のデータを扱う場合  
* put(String managerKey, String key, Object val)  
* take(String managerKey, String key)

圧縮表現のデータを扱う場合  
* put(String **"compressed"** + managerKey, String key, Object val)  
* take(String **"compressed"** + managerKey, String key)

# 圧縮機能 - 通信プロトコルの変更
* Remote から put されたデータは必ずシリアライズ化されており byteArray で表現される。
* 圧縮した byteArray の追加により、Remote から put された byteArray が圧縮されているのか判断する必要がある。

# 圧縮機能 - 通信プロトコルの変更
* Alice の通信におけるヘッダにあたる CommandMessage.classに **シリアライズ状態表すフラグ**と、**圧縮状態を表すフラク** を追加
* これにより put された DSM はフラグに応じた適切な形式で格納できる。

# 圧縮機能 - 通信プロトコルの変更

```java  
	public class CommandMessage {
		public int type;
		public int seq;
		public String key;
		public boolean quickFlag = false;
		public boolean serialized = false;
		public boolean compressed = false;
		public int dataSize = 0;
	}
```


# 圧縮機能 - 通信プロトコルの変更
<table style="border-collapse: collapse;border:1px solid #000000;">
  <tr>
    <td style="border:1px solid #000000;"> type</td>
    <td style="border:1px solid #000000;">CommandType PEEK, PUT などを表す</td>
  </tr>
  <tr>
    <td style="border:1px solid #000000;"> seq </td>
    <td style="border:1px solid #000000;">DS の待ち合わせを行っている CS を表す unique number</td>
  </tr>
	<tr>
		<td style="border:1px solid #000000;"> key </td>
		<td style="border:1px solid #000000;">どの Key に対して操作を行うか指定する</td>
	</tr>
	<tr>
	<td style="border:1px solid #000000;"> quickFlag </td>
	<td style="border:1px solid #000000;">SEDA を挟まず Command を処理を行うかを示す</td>
	</tr>
	<tr>
	<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;"> dataSize </td>
	<td style="border:1px solid #000000;">圧縮前のデータサイズを表す</td>
	</tr>
</table>

# 圧縮機能の評価
RingRelayTest  
![opt](./images/topologyring.svg)

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