Mercurial > hg > Papers > 2015 > nozomi-sigos

comparison presen/sigOS/sample.markdown @ 17:a26eacfb4922

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
change
author Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
date Mon, 25 May 2015 03:29:25 +0900
parents 1ac38e2b7572
children 20c9082b212d
comparison
equal deleted inserted replaced
16:1ac38e2b7572 17:a26eacfb4922
1 title: 分散フレームワークAliceの圧縮機能 1 title: 分散フレームワークAliceの圧縮機能
2 author: 照屋のぞみ 2 author: 照屋のぞみ
3 profile:琉球大学 工学部 情報工学科 4年 3 profile:琉球大学 工学部 情報工学科 4年
4 4
5 # 研究背景(1/2) 5 # 研究目的
6 * 信頼性とスケーラビリティに優れた分散プログラムをプログラマが一から記述することは容易ではない。 6 * 並列分散フレームワークAliceではスケーラブルな分散プログラムを信頼性高く記述できる環境を実現する。
7 * 本研究室ではデータを *Data Segment* 、タスクを *Code Segment* という単位で分割して記述する**並列分散フレームワークAlice**の開発を行っている。 7 * Aliceのメタ計算として通信が切断した際の処理やデータを圧縮する処理等を提供することで、プログラマがコードを大きく変更することなくプログラムの振る舞いを変えることを可能にする。
8 * Aliceは分散環境の構築のためのAPIが提供されており、スケーラブルな分散プログラムを信頼性高く記述できる環境を実現する。
9 8
10 # 研究背景(1/2) 9 # Aliceの概要(1) - Data Segment と Code Segment
11 * 水族館の例題等において、Aliceが分散プログラムを記述する能力を有することは確認された。 10 * Aliceではデータを **Data Segment(DS)** 、タスクを **Code Segment(CS)** という単位に分割してプログラミングを行う。
12 * 実用的な分散プログラムを作成するためには、圧縮形式のデータで通信する機能等が必要だとわかった。 11 * AliceはJavaで実装されており、CS をユーザーが記述する際には CodeSegment.class を継承することで CS で使用する API を利用する事ができる。
12 * DSはAliceが内部にもつデータベースにより管理されており、CSはDSに対応する一意のkeyを使ってDSを操作する。
13 13
14 # 研究目的 14 # Aliceの概要(2) - Data Segment と Code Segment
15 * Aliceに圧縮機能等を追加することにより、Data Segmentの多態性を実現しノード間通信における自由度の向上を図る。 15 * CSはInput DS(入力されるDS)とOutput DS(出力されるDS)と呼ぶ。
16 * CSはkeyで指定されたDSが揃うと実行されるという性質を持つ。
17 ![opt](./images/dsandcs.svg)
16 18
17 # Aliceの概要(1) - Data Segment 19 # Aliceの概要(3) - CodeSegmentの依存関係
18 * 複数の関係のない要素を1つのデータオブジェクトで表現した場合、全ての操作でlockが必要になり、スケラビリティーを低下させる。 20 * データの依存関係にないCSは並列実行される
19 * Alice はデータを細かく分割して記述する。その分割されたデータを **Data Segment(DS)** と呼ぶ。 21 * データの依存関係がある場合は Input DS が揃うと順に実行される
22 ![opt](./images/dsandcs2.svg)
20 23
21 # Aliceの概要(2) - Data Segment Manager 24 # Aliceの概要(4) - Data Segment
22 * DS は queue に保存される。queue には対 になる key し、 key を指定して DS の保存、取得を行う。 25 * 整数や文字列などの基本的なデータの集まり
23 * queue の集合体であるデータベースデータベースを Alice では DS Manager(DSM) と呼ぶ。 26 * Aliceの場合はJavaオブジェクトに対応
27
28 # Aliceの概要(5) - Data Segment Manager
29 * DS の集合体であるデータベースを Alice では DS Manager(DSM) と呼ぶ。
30 * DSM 内の DS には対になる String型のkey が存在し、 key を指定しすることで DS の保存、取得を行う。
24 ![opt](./pictures/dsm.svg) 31 ![opt](./pictures/dsm.svg)
25 32
26 # Aliceの概要(2) - Data Segment Manager 33 # Aliceの概要(6) - Data Segment Manager
27 * Local DSM … 各ノード固有のデータベース。 34 * Local DSM … 各ノード固有のデータベース。
28 * Remote DSM … 他のノードの Local DSM の proxy。接続しているノードの数だけ存在。 35 * Remote DSM … 他のノードの Local DSM の proxy。接続しているノードの数だけ存在する。
29 ![opt](./images/remote_datasegment.svg){:width="450px"} 36 ![opt](./images/remote_datasegment.svg){:width="450px"}
30 37
31 # Aliceの概要(3) - Data Segment API 38 # Aliceの概要(7) - Data Segment API
32 DSMに対して以下のコマンドを送り操作できる 39 DSM に対して DSM の名前と DS を指し示すkey を指定することで操作を行う
40 * DS の追加
41 put(String managerKey, String key, Object val)
42 * DS の取得
43 take(String managerKey, String key)
33 44
34 <table style="border-collapse: collapse;border:1px solid #000000;"> 45 # Aliceの概要(8) - Data Segment の表現
35 <tr> 46 DSは複数の表現（多態性）を同時に持つ
36 <td style="border:1px solid #000000;"> put</td> 47 1. 一般的な Java のクラスオブジェクト
37 <td style="border:1px solid #000000;">データを追加する</td> 48 2. MessagePack for Java でシリアライズ化されたバイナリオブジェクト。Remoteとの通信の際に用いる。
38 </tr> 49 3. 2 を圧縮したバイナリオブジェクト。圧縮機能の一部として今回追加。
39 <tr>
40 <td style="border:1px solid #000000;"> update </td>
41 <td style="border:1px solid #000000;">データを更新する</td>
42 </tr>
43 <tr>
44 <td style="border:1px solid #000000;"> peek</td>
45 <td style="border:1px solid #000000;">データを取得する</td>
46 </tr>
47 <tr>
48 <td style="border:1px solid #000000;"> take</td>
49 <td style="border:1px solid #000000;">データを取得する。取得したデータはDSMから削除される。</td>
50 </tr>
51 </table>
52 50
53 # Aliceの概要(4) - Data Segment の表現 51 # MessagePackとは
54 * 一般的な Java のクラスオブジェクト 52 シリアライズのための機能をまとめたライブラリであり、プログラミング言語に依存しないデータの表現形式として使用できる。
55 * LocalDSM に put された場合は一般的な Java のクラスオブジェクトとして enQueue される。
56 * MessagePack を用いて変換した byte[]で表現されたバイナリオブジェクト
57 * RemoteDSM に put された場合は通信時に byteArray に変換されたバイナリオブジェクトが enQueue される。
58 53
59 # Aliceの概要(5) - Code Segment 54 # Aliceの概要(9) - Code Segment
60 * Alice上で実行されるタスクの単位を **Code Segment(CS)** と呼ぶ。 55 * setKey()にtakeコマンドをセットすることで Input DS を指定する
61 * 複数のDSが入力され、その結果をDSとして出力するfunctionと捉えられる。 56 * 実際にtakeしたデータを参照するときには、asClass()を用いて任意のJavaのオブジェクトとして扱えるようにする
62 * CS をユーザーが記述する際には CS を継承して記述することにより CS で使用する API を利用する事ができる。
63 57
64 # Aliceの概要(5) - Code Segment 58 # Computation と Meta Computation
65 * 入力されるDSをInput DS、出力されるDSをOutput DSと呼ぶ。 59 * Aliceでは、計算の本質的な処理をComputatin、Computationとは直接関係ないが別のレベルでそれを支える処理をMeta Computationとして考える
66 * keyで指定されたDSが揃うと実行されるという性質を持つ。 60 * これにより通常処理と例外処理を分離できるためシンプルなプログラムが記述可能
67 ![opt](./images/dsandcs.svg)
68 61
69 # Aliceの概要(6) - CodeSegmentの依存関係 62 # Alice の Computation
70 * データの依存関係にないCSは並列実行される 63 * keyによりDSを待ち合わせ、DSが揃ったCSを並列に実行する
71 * データの依存関係がある場合は依存を解決した順に実行される 64 * VNCの場合、VNCサーバからデータを受け取って表示する処理
72 * 並列度あげるために、処理を細かく記述し、依存するDSを少なくする 65
73 ![opt](./images/dsandcs2.svg) 66 # Alice の Meta Computation
67 * 通信の切断・再接続時の処理や分散トポロジーの構成、データの表現形式の選択など、Computationを支えている処理。
68 * VNCの場合、VNCサーバのデータを各VNCノードにコピーする処理。
69 * Aliceの機能を追加するということは Meta Computation を追加すると言い換えられる
70
74 71
75 # AliceのMeta Computation(1/2) 72 # AliceのMeta Computation(1/2)
76 * 並列指向プログラミング言語 Erlang では、分散環境の構築等の処理は全てプログラマが記述しなければいけない。
77 * Aliceではプログラマが記述する部分を *Computation*、Aliceが提供するComputationを支える部分を *Meta Computation* として分けて捉えている。 73 * Aliceではプログラマが記述する部分を *Computation*、Aliceが提供するComputationを支える部分を *Meta Computation* として分けて捉えている。
78 * 分散環境の構築等の処理等は全てMeta Computationが行うためプログラマがシンプルに分散プログラムを記述できる環境を提供している。 74 * 分散環境の構築等の処理等は全てMeta Computationが行うためプログラマがシンプルに分散プログラムを記述できる環境を提供している。
79 75
80 # AliceのMeta Computation(2/2) 76 # TreeVNC
81 * AliceのComputation 77 * AliceのMeta Computationを用いて実装する実用的な分散プログラムの例題
82 * keyによりData Segmentを待ち合わせてCode Segmentを実行する 78 * 本研究室で開発したノードを木構造に配置して負荷分散を行う授業向け画面共有システム
83 79 * TightVNCがもとになっており、この部分がComputationと言える
84 * AliceのMeta Computation
85 * Javaで記述したAliceの実装システム
86
87 * Aliceの機能を追加するということは Meta Computation を追加すると言い換えられる
88 * Meta Computation も CS と DS により表現される。
89
90 # AliceVNC
91 * 研究室では授業向け画面共有システムTreeVNCではノード同士を接続させ、木構造を構成することで負荷分散を行う
92 ![opt](./images/treeVNC.svg) 80 ![opt](./images/treeVNC.svg)
93 81
94 # Alice の新機能 82 # TreeVNCで用いるAliceのMeta Computation
95 * Alice が実用的なアプリケーションを記述する能力をもつことを確認するため、TreeVNC を Alice を用いて実装した AliceVNC の作成を行った。 83 * TreeTopologyの構成
96 * AliceVNCの実装で必要となった以下の機能をMeta Computation として実装した。 84 * ノード間通信の切断時・再接続時の処理
97 * 転送機能　… Input DS を Output DS として転送する 85 * データの圧縮
98 * 圧縮機能　… DS Manager の指定によってDSの表現を切り替える 86 * 子ノードへのデータの複製
99 87
100 # 転送機能
101 * 通常、Input DSに変更を加えOutput DSとして出力する場合DSのコピーが行われる。
102 * AliceVNCのようにInput DS をそのまま子ノードに Output DS として出力する場合、コピーを行なうのは無駄。
103 * Input DSをコピーせずそのままOutput DSに渡すMeta Computationとして転送機能を実装した。
104 88
105 # 転送機能 89 # TreeVNCでの圧縮 Meta Computation
106 ```java 90 # データの転送 - DSMとAPIの追加
107 public void flip(Receiver receiver) { 91 * Local と Remote それぞれに圧縮表現を扱う Compressed DSM を追加した。
108 DataSegment.getLocal().put(receiver.key, receiver.getReceiveData(), null); 92 * 指定する DSM を Compressed DSM に変えるだけで扱うデータ表現を変更できる
109 } 93 put(String **"compressed"** + managerKey, String key, Object val)
110 ``` 94 take(String **"compressed"** + managerKey, String key)
111 95
112 # 圧縮機能 96 # データの転送 - データ表現の自動生成
113 * AliceVNCは、ノードは受け取った画面データを描画すると同時に、子ノードの Remote DSM に送信する。 97 * DS が圧縮表現を持っていれはそれをそのまま子ノードにputする
114 * ノードは DS を受信するとそれを一度解凍して画面を表示し、再圧縮して子ノードに送信する。 98 * 持っていなければその時点でCompressed DSM内部で圧縮表現を生成してputする
115 * 圧縮状態のまま子ノードに送信ができれば、解凍・再圧縮するオーバーヘッドを無くすことができる。 99 * DS はオブジェクト表現と圧縮表現を同時にもつため、TreeVNCでは受け取った画面データを伸長をした後、転送のために再圧縮することはない。
116 100
117 # 圧縮機能 - Data Segmentの表現の変更 101 # データの受け取り - 任意の形式での取得
118 1つの Data Segment に対し以下の3種類の表現を同時に持たせ、必要に応じた形式で DS を扱う。 102 * 圧縮表現で画面データ受け取り、Compressed DSM 内に格納。
119 1. 一般的な Java のクラスオブジェクト 103 * TightVNCが画面表示のためにデータを必要としたときに、 asClass() を用いて任意の形式でデータを取り出す。
120 2. MessagePack for Java でシリアライズ化され たバイナリオブジェクト 104 * asClass() は DS のcastメソッドであり、伸長と MessagePack での変換を行う。
121 3. 2 を圧縮したバイナリオブジェクト
122 105
123 # 圧縮機能 - Data Segmentの表現の変更 106 # データの受け取り - Aliceの通信パケットの変更
124 ```java 107 * 通信ヘッダにデータの状態を表すフラグを追加したことで、受け取ったデータを適切な形式でDSM内に格納できる。
125 public class ReceiveData { 108 * 圧縮前と圧縮後のデータサイズを入れたことにより、受け取ったデータの適切な伸長が可能。
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 # 圧縮機能 - 通信プロトコルの変更
162 * Remote から put されたデータは必ずシリアライズ化されており byteArray で表現される。
163 * 圧縮した byteArray の追加により、Remote から put された byteArray が圧縮されているのか判断する必要がある。
164
165 # 圧縮機能 - 通信プロトコルの変更
166 * Alice の通信におけるヘッダにあたる CommandMessage.classに **シリアライズ状態表すフラグ**と、**圧縮状態を表すフラク** を追加
167 * これにより put された DSM はフラグに応じた適切な形式で格納できる。
168
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;"> 109 <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> 110 <td style="border:1px solid #000000;"> serialized </td>
204 <td style="border:1px solid #000000;">データ本体のシリアライズ状態を示す</td> 111 <td style="border:1px solid #000000;">データ本体のシリアライズ状態を示す</td>
205 </tr> 112 </tr>
206 <tr> 113 <tr>
207 <td style="border:1px solid #000000;"> compressed </td> 114 <td style="border:1px solid #000000;"> compressed </td>
208 <td style="border:1px solid #000000;">データ本体の圧縮状態を示す</td> 115 <td style="border:1px solid #000000;">データ本体の圧縮状態を示す</td>
209 </tr> 116 </tr>
210 <tr> 117 <tr>
118 <td style="border:1px solid #000000;"> objectDataSize </td>
119 <td style="border:1px solid #000000;">圧縮前のオブジェクトのデータサイズを表す</td>
120 </tr>
121 <tr>
211 <td style="border:1px solid #000000;"> dataSize </td> 122 <td style="border:1px solid #000000;"> dataSize </td>
212 <td style="border:1px solid #000000;">圧縮前のデータサイズを表す</td> 123 <td style="border:1px solid #000000;">送信するDSのデータサイズを表す</td>
213 </tr> 124 </tr>
214 </table> 125 </table>
215 126
216 # 圧縮機能の評価 127 # Aliceと他言語等との比較
217 RingRelayTest
218 ![opt](./images/topologyring.svg)
219 128
220 # まとめ 129 # まとめ
221 * Alice が実用的なアプリケーションを記述するための Meta Computation として、データに多態性を持たせ、指定するDSMによってデータ表 現を変える機能を実装した。 130 * Alice が実用的なアプリケーションを記述するための Meta Computation として、データに多態性を持たせ、指定するDSMによってデータ表現を変える機能を実装した。
222 * これによりユーザが記述する Computation 部分を大きく変えずに自由度の高い通信を行うことが可能になった。 131 * これによりユーザが記述する Computation 部分を大きく変えずに自由度の高い通信を行うことが可能になった。
223 * 同様の手法により、暗号形式・JSON 形式など複数のデータ表現を扱えるように拡張できる。 132 * 同様の手法により、暗号形式・JSON 形式など複数のデータ表現を扱えるように拡張できる。
224 * 今後の課題としては、圧縮機能を AliceVNC で用 いることで有効性を測る必要がある。 133 * 今後の課題としては、圧縮機能を TreeVNC で用 いることで有効性を測る必要がある。