13
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1 title: 分散フレームワークAliceの圧縮機能
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2 author: 照屋のぞみ
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
3 profile:琉球大学 工学部 情報工学科 4年
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
4
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
5 # 研究背景(1/2)
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
6 * 信頼性とスケーラビリティに優れた分散プログラムをプログラマが一から記述することは容易ではない。
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
7 * 本研究室ではデータを *Data Segment* 、タスクを *Code Segment* という単位で分割して記述する**並列分散フレームワークAlice**の開発を行っている。
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
8 * Aliceは分散環境の構築のためのAPIが提供されており、スケーラブルな分散プログラムを信頼性高く記述できる環境を実現する。
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
9
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
10 # 研究背景(1/2)
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
11 * 水族館の例題等において、Aliceが分散プログラムを記述する能力を有することは確認された。
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
12 * 実用的な分散プログラムを作成するためには、圧縮形式のデータで通信する機能等が必要だとわかった。
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
13
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
14 # 研究目的
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
15 * Aliceに圧縮機能等を追加することにより、Data Segmentの多態性を実現しノード間通信における自由度の向上を図る。
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
16
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
17 # Aliceの概要(1) - Data Segment
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
18 * 複数の関係のない要素を1つのデータオブジェクトで表現した場合、全ての操作でlockが必要になり、スケラビリティーを低下させる。
|
|
15
|
19 * Alice はデータを細かく分割して記述する。その分割されたデータを **Data Segment(DS)** と呼ぶ。
|
13
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
20
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
21 # Aliceの概要(2) - Data Segment Manager
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
22 * DS は queue に保存される。queue には対 になる key し、 key を指定して DS の保存、取得を行う。
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
23 * queue の集合体であるデータベースデータベースを Alice では DS Manager(DSM) と呼ぶ。
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
24 
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
25
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
26 # Aliceの概要(2) - Data Segment Manager
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
27 * Local DSM … 各ノード固有のデータベース。
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
28 * Remote DSM … 他のノードの Local DSM の proxy。接続しているノードの数だけ存在。
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
29 {:width="450px"}
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
30
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
31 # Aliceの概要(3) - Data Segment API
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
32 DSMに対して以下のコマンドを送り操作できる
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
33
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
34 <table style="border-collapse: collapse;border:1px solid #000000;">
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
35 <tr>
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
36 <td style="border:1px solid #000000;"> put</td>
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
37 <td style="border:1px solid #000000;">データを追加する</td>
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
38 </tr>
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
39 <tr>
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
40 <td style="border:1px solid #000000;"> update </td>
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
41 <td style="border:1px solid #000000;">データを更新する</td>
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
42 </tr>
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
43 <tr>
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
44 <td style="border:1px solid #000000;"> peek</td>
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
45 <td style="border:1px solid #000000;">データを取得する</td>
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
46 </tr>
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
47 <tr>
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
48 <td style="border:1px solid #000000;"> take</td>
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
49 <td style="border:1px solid #000000;">データを取得する。取得したデータはDSMから削除される。</td>
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
50 </tr>
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
51 </table>
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
52
|
|
14
|
53 # Aliceの概要(4) - Data Segment の表現
|
|
|
54 * 一般的な Java のクラスオブジェクト
|
|
|
55 * LocalDSM に put された場合は一般的な Java のクラスオブジェクトとして enQueue される。
|
|
|
56 * MessagePack を用いて変換した byte[]で表現されたバイナリオブジェクト
|
|
|
57 * RemoteDSM に put された場合は通信時に byteArray に変換されたバイナリオブジェクトが enQueue される。
|
13
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
58
|
|
14
|
59 # Aliceの概要(5) - Code Segment
|
|
15
|
60 * Alice上で実行されるタスクの単位を **Code Segment(CS)** と呼ぶ。
|
13
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
61 * 複数のDSが入力され、その結果をDSとして出力するfunctionと捉えられる。
|
|
14
|
62 * CS をユーザーが記述する際には CS を継承して記述することにより CS で使用する API を利用する事ができる。
|
|
|
63
|
|
|
64 # Aliceの概要(5) - Code Segment
|
13
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
65 * 入力されるDSをInput DS、出力されるDSをOutput DSと呼ぶ。
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
66 * keyで指定されたDSが揃うと実行されるという性質を持つ。
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
67 
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
68
|
|
14
|
69 # Aliceの概要(6) - CodeSegmentの依存関係
|
13
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
70 * データの依存関係にないCSは並列実行される
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
71 * データの依存関係がある場合は依存を解決した順に実行される
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
72 * 並列度あげるために、処理を細かく記述し、依存するDSを少なくする
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
73 
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
74
|
|
14
|
75 # AliceのMeta Computation(1/2)
|
13
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
76 * 並列指向プログラミング言語 Erlang では、分散環境の構築等の処理は全てプログラマが記述しなければいけない。
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
77 * Aliceではプログラマが記述する部分を *Computation*、Aliceが提供するComputationを支える部分を *Meta Computation* として分けて捉えている。
|
|
14
|
78 * 分散環境の構築等の処理等は全てMeta Computationが行うためプログラマがシンプルに分散プログラムを記述できる環境を提供している。
|
13
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
79
|
|
14
|
80 # AliceのMeta Computation(2/2)
|
13
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
81 * AliceのComputation
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
82 * keyによりData Segmentを待ち合わせてCode Segmentを実行する
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
83
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
84 * AliceのMeta Computation
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
85 * Javaで記述したAliceの実装システム
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
86
|
|
14
|
87 * Aliceの機能を追加するということは Meta Computation を追加すると言い換えられる
|
|
16
|
88 * Meta Computation も CS と DS により表現される。
|
|
14
|
89
|
|
|
90 # AliceVNC
|
|
15
|
91 * 研究室では授業向け画面共有システムTreeVNCではノード同士を接続させ、木構造を構成することで負荷分散を行う
|
|
14
|
92 
|
13
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
93
|
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
94 # Alice の新機能
|
|
15
|
95 * Alice が実用的なアプリケーションを記述する能力をもつことを確認するため、TreeVNC を Alice を用いて実装した AliceVNC の作成を行った。
|
|
14
|
96 * AliceVNCの実装で必要となった以下の機能をMeta Computation として実装した。
|
|
15
|
97 * 転送機能 … Input DS を Output DS として転送する
|
|
14
|
98 * 圧縮機能 … DS Manager の指定によってDSの表現を切り替える
|
13
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
99
|
|
15
|
100 # 転送機能
|
|
|
101 * 通常、Input DSに変更を加えOutput DSとして出力する場合DSのコピーが行われる。
|
|
|
102 * AliceVNCのようにInput DS をそのまま子ノードに Output DS として出力する場合、コピーを行なうのは無駄。
|
|
|
103 * Input DSをコピーせずそのままOutput DSに渡すMeta Computationとして転送機能を実装した。
|
13
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
104
|
|
16
|
105 # 転送機能
|
|
|
106 ```java
|
|
|
107 public void flip(Receiver receiver) {
|
|
|
108 DataSegment.getLocal().put(receiver.key, receiver.getReceiveData(), null);
|
|
|
109 }
|
|
|
110 ```
|
|
|
111
|
13
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
112 # 圧縮機能
|
|
14
|
113 * AliceVNCは、ノードは受け取った画面データを描画すると同時に、子ノードの Remote DSM に送信する。
|
|
|
114 * ノードは DS を受信するとそれを一度解凍して画面を表示し、再圧縮して子ノードに送信する。
|
|
|
115 * 圧縮状態のまま子ノードに送信ができれば、解凍・再圧縮するオーバーヘッドを無くすことができる。
|
13
Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
116
|
|
14
|
117 # 圧縮機能 - Data Segmentの表現の変更
|
|
|
118 1つの Data Segment に対し以下の3種類の表現を同時に持たせ、必要に応じた形式で DS を扱う。
|
|
|
119 1. 一般的な Java のクラスオブジェクト
|
|
|
120 2. MessagePack for Java でシリアライズ化され たバイナリオブジェクト
|
|
|
121 3. 2 を圧縮したバイナリオブジェクト
|
|
|
122
|
|
|
123 # 圧縮機能 - Data Segmentの表現の変更
|
|
|
124 ```java
|
|
|
125 public class ReceiveData {
|
|
|
126 private Object val = null;
|
|
|
127 private byte[] messagePack = null;
|
|
|
128 private byte[] zMessagePack = null;
|
|
|
129 }
|
|
|
130 ```
|
|
|
131
|
|
|
132 # 圧縮機能 - DSMの追加
|
|
|
133 * Local と Remote それぞれに圧縮表現を扱う Compressed DSM を追加した。
|
|
|
134 * Compressed DSM にputする場合
|
|
|
135 * DS が圧縮表現を持っていればそれをputする
|
|
|
136 * 持っていなければその時点で圧縮表現を作ってputする
|
|
|
137
|
|
|
138 # 圧縮機能 - 任意の表現でDSを取得
|
|
|
139 * ReceiveData内にあるDSのcastメソッドであるasClass()を用いる
|
|
|
140 ```java
|
|
|
141 public <T> T asClass(Class<T> clazz) {
|
|
|
142 if (val != null) { return (T) val; }
|
|
|
143
|
|
|
144 if (zMessagePack != null && messagePack == null) {
|
|
|
145 messagePack = unzip(zMessagePack, dataSize);
|
|
|
146 }
|
|
|
147
|
|
|
148 return packer.read(messagePack, clazz);
|
|
|
149 }
|
|
|
150 ```
|
|
|
151
|
|
|
152 # 圧縮機能 - API設計
|
|
|
153 通常のデータを扱う場合
|
|
|
154 * put(String managerKey, String key, Object val)
|
|
|
155 * take(String managerKey, String key)
|
|
|
156
|
|
|
157 圧縮表現のデータを扱う場合
|
|
|
158 * put(String **"compressed"** + managerKey, String key, Object val)
|
|
|
159 * take(String **"compressed"** + managerKey, String key)
|
|
|
160
|
|
|
161 # 圧縮機能 - 通信プロトコルの変更
|
|
15
|
162 * Remote から put されたデータは必ずシリアライズ化されており byteArray で表現される。
|
|
|
163 * 圧縮した byteArray の追加により、Remote から put された byteArray が圧縮されているのか判断する必要がある。
|
|
|
164
|
|
|
165 # 圧縮機能 - 通信プロトコルの変更
|
|
|
166 * Alice の通信におけるヘッダにあたる CommandMessage.classに **シリアライズ状態表すフラグ**と、**圧縮状態を表すフラク** を追加
|
|
|
167 * これにより put された DSM はフラグに応じた適切な形式で格納できる。
|
|
14
|
168
|
|
16
|
169 # 圧縮機能 - 通信プロトコルの変更
|
|
|
170
|
|
|
171 ```java
|
|
|
172 public class CommandMessage {
|
|
|
173 public int type;
|
|
|
174 public int seq;
|
|
|
175 public String key;
|
|
|
176 public boolean quickFlag = false;
|
|
|
177 public boolean serialized = false;
|
|
|
178 public boolean compressed = false;
|
|
|
179 public int dataSize = 0;
|
|
|
180 }
|
|
|
181 ```
|
|
|
182 
|
|
|
183
|
|
|
184 # 圧縮機能 - 通信プロトコルの変更
|
|
|
185 <table style="border-collapse: collapse;border:1px solid #000000;">
|
|
|
186 <tr>
|
|
|
187 <td style="border:1px solid #000000;"> type</td>
|
|
|
188 <td style="border:1px solid #000000;">CommandType PEEK, PUT などを表す</td>
|
|
|
189 </tr>
|
|
|
190 <tr>
|
|
|
191 <td style="border:1px solid #000000;"> seq </td>
|
|
|
192 <td style="border:1px solid #000000;">DS の待ち合わせを行っている CS を表す unique number</td>
|
|
|
193 </tr>
|
|
|
194 <tr>
|
|
|
195 <td style="border:1px solid #000000;"> key </td>
|
|
|
196 <td style="border:1px solid #000000;">どの Key に対して操作を行うか指定する</td>
|
|
|
197 </tr>
|
|
|
198 <tr>
|
|
|
199 <td style="border:1px solid #000000;"> quickFlag </td>
|
|
|
200 <td style="border:1px solid #000000;">SEDA を挟まず Command を処理を行うかを示す</td>
|
|
|
201 </tr>
|
|
|
202 <tr>
|
|
|
203 <td style="border:1px solid #000000;"> serialized </td>
|
|
|
204 <td style="border:1px solid #000000;">データ本体のシリアライズ状態を示す</td>
|
|
|
205 </tr>
|
|
|
206 <tr>
|
|
|
207 <td style="border:1px solid #000000;"> compressed </td>
|
|
|
208 <td style="border:1px solid #000000;">データ本体の圧縮状態を示す</td>
|
|
|
209 </tr>
|
|
|
210 <tr>
|
|
|
211 <td style="border:1px solid #000000;"> dataSize </td>
|
|
|
212 <td style="border:1px solid #000000;">圧縮前のデータサイズを表す</td>
|
|
|
213 </tr>
|
|
|
214 </table>
|
|
|
215
|
|
14
|
216 # 圧縮機能の評価
|
|
16
|
217 RingRelayTest
|
|
15
|
218 
|
|
14
|
219
|
|
|
220 # まとめ
|
|
|
221 * Alice が実用的なアプリケーションを記述するための Meta Computation として、データに多態性を持たせ、指定するDSMによってデータ表 現を変える機能を実装した。
|
|
|
222 * これによりユーザが記述する Computation 部分を大きく変えずに自由度の高い通信を行うことが可能になった。
|
|
|
223 * 同様の手法により、暗号形式・JSON 形式など複数のデータ表現を扱えるように拡張できる。
|
|
|
224 * 今後の課題としては、圧縮機能を AliceVNC で用 いることで有効性を測る必要がある。
|
