# HG changeset patch # User Nozomi Teruya # Date 1432492165 -32400 # Node ID a26eacfb49229f1c1d7957440c800dd2345303c5 # Parent 1ac38e2b7572280eca9bb74b8ddfa7314091547c change diff -r 1ac38e2b7572 -r a26eacfb4922 presen/sigOS/sample.markdown --- a/presen/sigOS/sample.markdown Mon May 25 00:09:45 2015 +0900 +++ b/presen/sigOS/sample.markdown Mon May 25 03:29:25 2015 +0900 @@ -2,204 +2,111 @@ author: 照屋のぞみ profile:琉球大学 工学部 情報工学科 4年 -# 研究背景(1/2) -* 信頼性とスケーラビリティに優れた分散プログラムをプログラマが一から記述することは容易ではない。 -* 本研究室ではデータを *Data Segment* 、タスクを *Code Segment* という単位で分割して記述する**並列分散フレームワークAlice**の開発を行っている。 -* Aliceは分散環境の構築のためのAPIが提供されており、スケーラブルな分散プログラムを信頼性高く記述できる環境を実現する。 +# 研究目的 +* 並列分散フレームワークAliceではスケーラブルな分散プログラムを信頼性高く記述できる環境を実現する。 +* Aliceのメタ計算として通信が切断した際の処理やデータを圧縮する処理等を提供することで、プログラマがコードを大きく変更することなくプログラムの振る舞いを変えることを可能にする。 -# 研究背景(1/2) -* 水族館の例題等において、Aliceが分散プログラムを記述する能力を有することは確認された。 -* 実用的な分散プログラムを作成するためには、圧縮形式のデータで通信する機能等が必要だとわかった。 +# Aliceの概要(1) - Data Segment と Code Segment +* Aliceではデータを **Data Segment(DS)** 、タスクを **Code Segment(CS)** という単位に分割してプログラミングを行う。 +* AliceはJavaで実装されており、CS をユーザーが記述する際には CodeSegment.class を継承することで CS で使用する API を利用する事ができる。 +* DSはAliceが内部にもつデータベースにより管理されており、CSはDSに対応する一意のkeyを使ってDSを操作する。 -# 研究目的 -* Aliceに圧縮機能等を追加することにより、Data Segmentの多態性を実現しノード間通信における自由度の向上を図る。 +# Aliceの概要(2) - Data Segment と Code Segment +* CSはInput DS(入力されるDS)とOutput DS(出力されるDS)と呼ぶ。 +* CSはkeyで指定されたDSが揃うと実行されるという性質を持つ。 +![opt](./images/dsandcs.svg) -# Aliceの概要(1) - Data Segment -* 複数の関係のない要素を1つのデータオブジェクトで表現した場合、全ての操作でlockが必要になり、スケラビリティーを低下させる。 -* Alice はデータを細かく分割して記述する。その分割されたデータを **Data Segment(DS)** と呼ぶ。 +# Aliceの概要(3) - CodeSegmentの依存関係 +* データの依存関係にないCSは並列実行される +* データの依存関係がある場合は Input DS が揃うと順に実行される +![opt](./images/dsandcs2.svg) -# Aliceの概要(2) - Data Segment Manager -* DS は queue に保存される。queue には対 になる key し、 key を指定して DS の保存、取得を行う。 -* queue の集合体であるデータベースデータベースを Alice では DS Manager(DSM) と呼ぶ。 +# Aliceの概要(4) - Data Segment +* 整数や文字列などの基本的なデータの集まり +* Aliceの場合はJavaオブジェクトに対応 + +# Aliceの概要(5) - Data Segment Manager +* DS の集合体であるデータベースを Alice では DS Manager(DSM) と呼ぶ。 +* DSM 内の DS には対になる String型のkey が存在し、 key を指定しすることで DS の保存、取得を行う。 ![opt](./pictures/dsm.svg) -# Aliceの概要(2) - Data Segment Manager +# Aliceの概要(6) - Data Segment Manager * Local DSM … 各ノード固有のデータベース。 -* Remote DSM … 他のノードの Local DSM の proxy。接続しているノードの数だけ存在。 +* Remote DSM … 他のノードの Local DSM の proxy。接続しているノードの数だけ存在する。 ![opt](./images/remote_datasegment.svg){:width="450px"} -# Aliceの概要(3) - Data Segment API -DSMに対して以下のコマンドを送り操作できる +# Aliceの概要(7) - Data Segment API +DSM に対して DSM の名前と DS を指し示すkey を指定することで操作を行う +* DS の追加 + put(String managerKey, String key, Object val) +* DS の取得 + take(String managerKey, String key) - - - - - - - - - - - - - - - - - -
putデータを追加する
update データを更新する
peekデータを取得する
takeデータを取得する。取得したデータはDSMから削除される。
+# Aliceの概要(8) - Data Segment の表現 +DSは複数の表現（多態性）を同時に持つ +1. 一般的な Java のクラスオブジェクト +2. MessagePack for Java でシリアライズ化されたバイナリオブジェクト。Remoteとの通信の際に用いる。 +3. 2 を圧縮したバイナリオブジェクト。圧縮機能の一部として今回追加。 + +# MessagePackとは +シリアライズのための機能をまとめたライブラリであり、プログラミング言語に依存しないデータの表現形式として使用できる。 -# Aliceの概要(4) - Data Segment の表現 -* 一般的な Java のクラスオブジェクト - * LocalDSM に put された場合は一般的な Java のクラスオブジェクトとして enQueue される。 -* MessagePack を用いて変換した byte[]で表現されたバイナリオブジェクト - * RemoteDSM に put された場合は通信時に byteArray に変換されたバイナリオブジェクトが enQueue される。 +# Aliceの概要(9) - Code Segment +* setKey()にtakeコマンドをセットすることで Input DS を指定する +* 実際にtakeしたデータを参照するときには、asClass()を用いて任意のJavaのオブジェクトとして扱えるようにする -# Aliceの概要(5) - Code Segment -* Alice上で実行されるタスクの単位を **Code Segment(CS)** と呼ぶ。 -* 複数のDSが入力され、その結果をDSとして出力するfunctionと捉えられる。 -* CS をユーザーが記述する際には CS を継承して記述することにより CS で使用する API を利用する事ができる。 +# Computation と Meta Computation +* Aliceでは、計算の本質的な処理をComputatin、Computationとは直接関係ないが別のレベルでそれを支える処理をMeta Computationとして考える +* これにより通常処理と例外処理を分離できるためシンプルなプログラムが記述可能 -# Aliceの概要(5) - Code Segment -* 入力されるDSをInput DS、出力されるDSをOutput DSと呼ぶ。 -* keyで指定されたDSが揃うと実行されるという性質を持つ。 -![opt](./images/dsandcs.svg) +# Alice の Computation +* keyによりDSを待ち合わせ、DSが揃ったCSを並列に実行する +* VNCの場合、VNCサーバからデータを受け取って表示する処理 -# Aliceの概要(6) - CodeSegmentの依存関係 -* データの依存関係にないCSは並列実行される -* データの依存関係がある場合は依存を解決した順に実行される -* 並列度あげるために、処理を細かく記述し、依存するDSを少なくする -![opt](./images/dsandcs2.svg) +# Alice の Meta Computation +* 通信の切断・再接続時の処理や分散トポロジーの構成、データの表現形式の選択など、Computationを支えている処理。 +* VNCの場合、VNCサーバのデータを各VNCノードにコピーする処理。 +* Aliceの機能を追加するということは Meta Computation を追加すると言い換えられる + # 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ではノード同士を接続させ、木構造を構成することで負荷分散を行う +# TreeVNC +* AliceのMeta Computationを用いて実装する実用的な分散プログラムの例題 +* 本研究室で開発したノードを木構造に配置して負荷分散を行う授業向け画面共有システム +* TightVNCがもとになっており、この部分がComputationと言える ![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として転送機能を実装した。 +# TreeVNCで用いるAliceのMeta Computation +* TreeTopologyの構成 +* ノード間通信の切断時・再接続時の処理 +* データの圧縮 +* 子ノードへのデータの複製 -# 転送機能 -```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の追加 +# TreeVNCでの圧縮 Meta Computation +# データの転送 - DSMとAPIの追加 * Local と Remote それぞれに圧縮表現を扱う Compressed DSM を追加した。 -* Compressed DSM にputする場合 - * DS が圧縮表現を持っていればそれをputする - * 持っていなければその時点で圧縮表現を作ってputする - -# 圧縮機能 - 任意の表現でDSを取得 -* ReceiveData内にあるDSのcastメソッドであるasClass()を用いる -```java - public T asClass(Class clazz) { - if (val != null) { return (T) val; } - - if (zMessagePack != null && messagePack == null) { - messagePack = unzip(zMessagePack, dataSize); - } +* 指定する DSM を Compressed DSM に変えるだけで扱うデータ表現を変更できる + put(String **"compressed"** + managerKey, String key, Object val) + take(String **"compressed"** + managerKey, String key) - 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 はフラグに応じた適切な形式で格納できる。 - -# 圧縮機能 - 通信プロトコルの変更 +# データの転送 - データ表現の自動生成 +* DS が圧縮表現を持っていれはそれをそのまま子ノードにputする +* 持っていなければその時点でCompressed DSM内部で圧縮表現を生成してputする +* DS はオブジェクト表現と圧縮表現を同時にもつため、TreeVNCでは受け取った画面データを伸長をした後、転送のために再圧縮することはない。 -```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; - } -``` - +# データの受け取り - 任意の形式での取得 +* 圧縮表現で画面データ受け取り、Compressed DSM 内に格納。 +* TightVNCが画面表示のためにデータを必要としたときに、 asClass() を用いて任意の形式でデータを取り出す。 +* asClass() は DS のcastメソッドであり、伸長と MessagePack での変換を行う。 -# 圧縮機能 - 通信プロトコルの変更 +# データの受け取り - Aliceの通信パケットの変更 +* 通信ヘッダにデータの状態を表すフラグを追加したことで、受け取ったデータを適切な形式でDSM内に格納できる。 +* 圧縮前と圧縮後のデータサイズを入れたことにより、受け取ったデータの適切な伸長が可能。 - - - - - - - - - - - - - - - - - @@ -208,17 +115,19 @@ + + + + - +
typeCommandType PEEK, PUT などを表す
seq DS の待ち合わせを行っている CS を表す unique number
key どの Key に対して操作を行うか指定する
quickFlag SEDA を挟まず Command を処理を行うかを示す
serialized データ本体のシリアライズ状態を示す
データ本体の圧縮状態を示す
objectDataSize 圧縮前のオブジェクトのデータサイズを表す
dataSize 圧縮前のデータサイズを表す送信するDSのデータサイズを表す
-# 圧縮機能の評価 -RingRelayTest -![opt](./images/topologyring.svg) +# Aliceと他言語等との比較 # まとめ -* Alice が実用的なアプリケーションを記述するための Meta Computation として、データに多態性を持たせ、指定するDSMによってデータ表 現を変える機能を実装した。 +* Alice が実用的なアプリケーションを記述するための Meta Computation として、データに多態性を持たせ、指定するDSMによってデータ表現を変える機能を実装した。 * これによりユーザが記述する Computation 部分を大きく変えずに自由度の高い通信を行うことが可能になった。 * 同様の手法により、暗号形式・JSON 形式など複数のデータ表現を扱えるように拡張できる。 -* 今後の課題としては、圧縮機能を AliceVNC で用 いることで有効性を測る必要がある。 +* 今後の課題としては、圧縮機能を TreeVNC で用 いることで有効性を測る必要がある。