Mercurial > hg > Papers > 2018 > nozomi-master

title: 分散フレームワークChristieの設計
author: 照屋のぞみ

# 研究目的（1/2）
* スケーラブルで信頼性の高い分散プログラムを書くのは容易ではない
    * 並列で動く分散した資源を意識するのは難しい
    * 分散したノードの洗濯方法が明確ではない􏱾􏱿􏰮􏳠􏲒􏰌􏰍􏰞􏰫􏷑􏷒􏱃􏱱􏲭􏰞􏰡􏰨􏰢􏱯􏱰􏰻􏰼􏰔􏰠􏳍􏳎􏰮􏰠􏰡􏲒􏰭􏲣 􏰫􏰭􏰘􏰔􏱑􏰥􏰹􏰌􏰍􏰞􏰫
* 当研究室が開発している並列分散フレームワークAliceではスケーラブルな分散プログラムを信頼性高く記述できる環境を実現する。
* ここで言う信頼性とは定められた環境下で安定して仕様に従った動作を行うことを指す。
    * 仕様の記述のしやすさ、可読性、拡張時に仕様変更を抑えられるかも含む
* スケーラビリティとはサービス利用者が増加したとき単純にノードを追加するだけで線形に性能を向上させる能力

# 研究目的（2/2）
* 本研究では、Aliceの通信の信頼性を高めるためにNAT越えの機能設計を提案する
* そしてその実現にはAliceの再設計が必要であることを示す
* Aliceの問題点を整理し、得られた知見をもとに分散フレームワークChristieの設計を行う


# 目次
* Aliceの概要
	* Code Segment / Data Segment
	* Data Segment Manager
    * API
	* Computation / Meta Computation
	* Topology Manager
    * 圧縮
* Topology Managerの拡張設計
	* 別トポロジー間の接続のための設計
	* 別ネットワーク間の接続のための設計
* Aliceの問題点
    * LocalDSMの複数立ち上げができない
    * 記述の煩雑さ
* Christieの設計
    * 基本設計
    * 記述性の改善
* 他フレームワークとの比較
    * Akka, Hazelcast
    * 設計思想の違い
    * 記述性の違い
    * 提供する機能
* まとめ
* 今後の課題


# Data Segment と Code Segment
* Aliceではデータを **Data Segment(DS)** 、タスクを **Code Segment(CS)** という単位に分割して依存関係を記述することでプログラミングを行う。
* CSはInput DS(入力されるDS)とOutput DS(出力されるDS)を持つ。
* CSはkeyで指定されたDSが揃うと実行されるという性質を持つ。
![opt](./images/dsandcs.svg){:width="50%"}

# CodeSegmentの依存関係
* データの依存関係にないCSは並列実行される
* データの依存関係がある場合は Input DS が揃うと順に実行される
* DSはCSに専有されるためロックの記述を必要としない
![opt](./images/dsandcs2.svg){:width="60%"}

# Data Segment と CodeSegment
* AliceはJavaで実装されており、DSはJava-Object、CSはRunnableに相当する
* ユーザーが記述する際には CodeSegment.class を継承することでDSを操作するためのAPIを利用して依存関係を記述することができる。

# Data Segment Manager
* DS の集合体であるデータベースを Alice では **DS Manager(DSM)** と呼ぶ。
* DSM 内の DS には対応する一意の String型のkey が存在し、 DSM 名と key を指定しすることで DS の保存、取得を行う。
![opt](./pictures/key.svg){:width="50%"}

# Data Segment Manager
* Local DSM … 各ノード固有のデータベース
* Remote DSM … 他のノードのLocal DSMのproxy。接続しているノードの数だけ存在する。
* Remote DSMに書き込むと対応するノードのLocalDSMに書き込まれる
* Remote DSMにはString型のDSM keyを指定してアクセスする
![opt](./pictures/newDSM.svg){:width="50%"}

# Data Segment API
* DSの取得
    * `void take(String managerKey, String key)`
    * `void peek(String managerKey, String key)`
* DSの追加
    * `void put(String managerKey, String key, Object val)`
    * `void update(String managerKey, String key, Object val)`
    * `void flip(String managerKey, String key, Receiver val)`

# Code Segmentの記述例
* take/peekをするにはcreate/setKeyメソッドを使わなければならない
* *create* でインプットDGのRecieverを作り、*setKey* でReceiverにインプットとなるkeyを指定
* データをReceiverから取り出す際は *asClass()* で型を指定
* 処理をループさせたい場合はCSをnewする
```java
public class TestCodeSegment extends CodeSegment {
    private Receiver input = ids.create(CommandType.TAKE);

    public TestCodeSegment() {
        input.setKey("count");
    }

    @Override
    public void run() {
        int count = input.asClass(Integer.class);
        System.out.println("data = " + count);

        new TestCodeSegment();

        ods.put("count", count);
    }
}
```

# Computation と Meta Computation
* Aliceでは、計算の本質的な処理をComputatin、Computationとは別のレベルでそれを支える処理をMeta Computationとして分けて考える。
* Alice のComputationは、keyによりDSを待ち合わせ、DSが揃ったCSを並列に実行する処理
* Meta Computationはそれを実現している処理
	* DSの待ち合わせ
	* 分散トポロジーの構成
	* 通信の切断・再接続時の処理
	* データの表現形式の選択

# Computation と Meta Computation
* 分散環境構築などの複雑な処理をAliceがMeta Computationとして提供する
* プログラマは目的の処理だけ記述し通信部分などはMeta Computationを指定する
* シンプルで見通しの良いコードを保つ

# AliceのMeta Computation - Topology Manager/Topology Node
* Topology Manager
	* ノード間の接続管理やトポロジーの構成管理行うMeta Computation
	* Static Topology ManagerとDynamic Topology Managerがある
* Topology Node
	* 各ノード側でTopology Managerとの通信を行うMeta Computation
	* ノードアプリケーションを記述する際にTopology Nodeをnewしておけば以降のTopology Managerとの通信やノード間の接続を行う
* Topology Manager/NodeもCS/DSを用いて実装されている。

# AliceのMeta Computation - Static Topology Manager
* プログラマがdot形式のトポロジーファイルを用意し、Topology Managerに読み込ませる
* トポロジーファイルにはノードの接続関係と接続する際に指定するRemote DSM名を記す
* Graphvizを用いればトポロジーを描くだけでトポロジーファイルが自動出力されるため構成が容易

```dot
digraph test{
	node0 −> node1[label=”right”]
	node0 −> node2[label=”left”]
	node1 −> node2[label=”right”]
	node1 −> node0[label=”left”]
	node2 −> node0[label=”right”]
	node2 −> node1[label=”left”]
}
```

# AliceのMeta Computation - Static Topology Manager
* ファイルを読み込んだTopology Managerを立ち上げる
* 各Topology NodeはTopology Managerに参加表明をし接続すべきノードの情報を要求する
![opt](./pictures/tree1.svg){:width="60%"}

# AliceのMeta Computation - Static Topology Manager
* 参加表明があった順に各ノードにnodeNameを割り当て、接続するべきノードのIPアドレス/ポート番号を送る
![opt](./pictures/tree2.svg){:width="60%"}

# AliceのMeta Computation - Static Topology Manager
* Topology Nodeが受け取った情報をもとにRemote DSMを立ちあげ接続し合うことでオーバーレイネットワークが作られる
* Topology Managerは接続情報を管理し、実際の接続はTopology Nodeが行う
![opt](./pictures/tree3.svg){:width="60%"}

# AliceのMeta Computation - Dynamic Topology Manager
* 参加するノード数があらかじめ決まっているとは限らない
* Dynamic Topology Managerがノードを参加表明順にトポロジーに組み込む
* 現在はTree Topologyに対応

# AliceのMeta Computation - 圧縮
* DSは内部に圧縮・非圧縮の複数の形式を複数もつことができる
* 圧縮したデータの伸長と圧縮したままの転送が同時に可能
![opt](./pictures/compress.svg){:width="80%"}

# AliceのMeta Computation - 圧縮
* 圧縮の指定には宛先DGM keyに"compressed"とつけるだけでよい
`put("compressedRemoteDGM", "key", data)`
* 伸長も *asClass()* した際に自動でされる
* コードの変更が抑えて圧縮・非圧縮が切り替えられる


# Aliceに求められるMeta Computation - アプリケーションの接続
* 別のトポロジーをもった既存のアプリケーション同士をコードの変更を抑えつつ接続させたい
* AliceVNC
	* Alice上に実装したツリートポロジーの画面配信システム
* AliceChat
	* Alice上に実装したスタートポロジーのチャット
* 連携することで実現したい機能
	* VNC画面のスナップショットをチャットに載せる
	* チャットの内容をVNC画面にコメントとして流す

# Aliceに求められるMeta Computation - アプリケーションの接続
* それぞれのアプリケーションのトポロジーを構成するTopologyManagerを連携させることで可能
![opt](./pictures/vncandchat.svg){:width="70%"}

# Aliceに求められるMeta Computation - NATを越えた接続
* NATを越えたノード間通信は分散処理の課題である
* Aliceではトポロジー管理がアプリケーションから分離しているため、コードを大きく変更しなくともTopology Managerを増やすことでトポロジーの拡張が可能

# Aliceに求められるMeta Computation - NATを越えた接続
* 各プライベートネットワーク内を管理するPrivate Topology Manager
* グローバルIPアドレスを持ったGlobal Topology Managerを１つ立てる
* TopologyNodeが複数対応できるためPrivate/Global Topology Managerに接続
![opt](./pictures/overNAT.svg){:width="70%"}


# 複数のTopology Managerへの対応
* 別トポロジーのアプリケーションの連携やNAT越えはノードが複数のTopologyManagerに接続することで可能になる
* この機能を実現するにはTopology Nodeが各Topology Managerに対応する複数のnodeNameを持つようにする必要がある
* Topology Nodeは割り当てられたnodeNameをDSとして保持してTopology Managerと通信を行うため、nodeNameの衝突を避けなければならない

![opt](./pictures/somehostname.svg){:width="50%"}

# Local DSMの切り替えによる対応
* 通常のLocal DSMとは別にTopology ManagerごとのLocal DSMを作成しnodeNameを管理
* Tpology Manager/Nodeの働きはそのままに、指定するLocal DSMを変えるだけでTopology Managerの複数対応が可能
![opt](./pictures/somehostname2.svg){:width="50%"}


# Aliceの問題点 - LocalDSMを複数立ち上げられない
* AliceではDSMを管理するクラスがstaticで書かれていたためLocal DSMを複数立ち上げることができない
* このstaticを抜くにはAliceのコード全体を大きく変更しなければならない
* アプリケーション接続やNAT越えのMeta Computationの追加が困難
* 複数インスタンスを立ち上げての分散プログラムのテストが書けない

# Aliceの問題点 - APIシンタックスの分離
* setKeyは記述場所が決まっておらず、CSの外からも呼べる
    * CSの再利用を可能にするが、どのkeyを待っているのか不明なCSが生まれてしまう
* setKeyではkeyを動的に指定することができる
    * どんな処理を行っているかわかりづらい
    * 対応するput箇所も修正しなければならない
    * モデル検査しづらくなる

# Aliceの問題点 - APIシンタックスの分離
* setKeyは全てのcreateが終わった最後に呼ばなければならない
    * Input DGの待ち合わせを行うカウンタはcreateの総数を持っている
    * カウントが0になると入力が揃ったと判断しrunに入る
    * countとsetKeyを交互に書くと入力が揃わないまま実行されNullPointExceptionになる
```java
class ShowData extends CodeSegment{
    private Receiver[] info;

    public ShowData(int cnt) {
        info = new Receiver[cnt];
        for (int i= 0;i < cnt; i++) {
            info[i] = ids.create(CommandType.TAKE);
            info[i].setKey(SetInfo.array[i]);
        }
    }

    @Override
    public void run() {
        int size = 0;
        for (Receiver anInfo : info) {
            DataList dlist = anInfo.asClass(DataList.class);
            dlist.showData();
        }
    }
}
```

# Aliceの問題点 - 型が推測できない
* Input DSをReceiver型でcreateするため、どの型のデータを待っているのかわからない
* しかしReceiverからデータを取り出すにはasClass()で型を指定する必要がある
* 型をDSをputした箇所までコードをたどる必要がある
    * flipでの転送もあるため、それを発見するのは容易ではない

# Aliceの問題点 - まとめ
* 以下の問題がAliceの信頼性・拡張性を下げている
    * Local DSMを複数立ち上げられないため、Topology Managerの拡張やテストが困難
    * インプットAPIが分離しているためCSでどんな処理が行われているかわかりづらい
    * setKyeの記述順序や型を気にしてプログラミングをしなくてはならない

# 分散フレームワークChristieへの必要要件
* Aliceの問題点を踏まえ、フレームワークをChristieを設計する
    * staticなLocalDSMをなくし複数インスタンスを立ち上げられるようにすることでスケーラビリティを高める
    * 煩雑なAPIをシンプルにし、記述性を高める
    * 型の整合性をとれるようにし、信頼性を向上させる

# Christie - 基本設計
* Javaで実装される
* 将来的に当研究室で開発しているGearsOSに統合したい
    * GearsOSに倣い、Code Gear(CG)/ Data Gear(DG) という名称を用いる
* CG/DGの依存関係や、DG Manager（DGM）の構造、Remote DGMへの接続方法はAliceと同様である

# Christie - 基本設計
* DGMはLocalもRemoteも全てCode Gear Manager(CGM)が管理する
* 1つのCGMは1つのLocalDGMを持つ
* CGM同士はThreadPoolとCGMのリストを共有している
    * メタ計算で全てのCGMにアクセス可能
![opt](./pictures/ChristieClass.svg){:width="60%"}

# Christie - 基本設計
* CG を記述する際は Alice同様CodeGear.classを継承
* CGは　*void run(CodeGearManager cgm)* を持ち、run メソッド内に処理を記述
    * このようにCGMを持ち運ぶ書き方はGearsOSに合わせてた書き方
* CGを作るためのAPIにはCGM経由で呼び出す

# Christie - DGMの複数立ち上げ
* ChristieではCGMを2つ生成すればLocalDGMも2つ作られる
* 複数のLocalDGM同士のやりとりは、Remoteへの接続と同じようにRemoteDGMを介してアクセスする
* 分散プログラムのローカルでのテストが可能になる
![opt](./pictures/DGM.svg){:width="50%"}

# Christie - CGの生成方法
1. StartCodeGear.classを継承しCGMを生成する
2. CGをnewしたあと*setup*を用いる
    * newが終わらないとアノテーションから待ち合わせを行う処理ができないため
    * このときCGMがCGに渡されるため、プログラマが引数にCGMを渡す必要はない

```java
public class StartTest extends StartCodeGear{//StartCG

    public StartTest(CodeGearManager cgm) {
        super(cgm);
    }

    public static void main(String args[]){
        StartTest start = new StartTest(createCGM(10000));//CGMを生成
    }

    @Override
    protected void run(CodeGearManager cgm) {
        cgm.setup(new TestCodeGear());//CGの待ち合わせを開始
        getLocalDGM().put("count", 1);
    }
}
```

# Christie - アノテーションを用いたインプット記述
* keyの指定にはJavaのアノテーションを用いる
    * 先頭を@で始める注釈
    * 独自アノテーションを定義できる
* アノテーションから待ち合わせを行う処理にはJavaのreflectionAPIを使用

# Christie - アノテーションを用いたインプット記述
* InputのためのDGを宣言し、その上にアノテーションでkeyを指定
* Takeの例
```java
@Take(”count”)
public DataGear<Integer> count = new DataGear<>();
```
* RemoteTakeの例
```java
@RemoteTake(dgmName="remote", key=”count”)
public DataGear<Integer> count = new DataGear<>();
```

# Christie - アノテーションを用いたインプット記述
* アノテーションは必ずフィールドに付けなければならない
    * InputDGの生成とkeyの指定を一箇所に書ける
* アノテーションの内容はコンパイル時に決定される
    * 動的なkey指定を防ぐ

# Christie - 型を指定しないデータ取り出し
* InputDGを宣言する際には必ず型の指定が必要となるため、CG内で型を把握できる
* DataGearはJavaの総称型を用いて<>内に指定した型を受け取る
```java
@Take(”count”)
public DataGear<Integer> count = new DataGear<>();
```

# Christie - 型を指定しないデータ取り出し
* 宣言された型は内部で保存され、ノード間通信でも保たれる
* AliceのasClass()と違い、getData()で型を指定せずにデータを取り出すことができる
```java
public class GetData extends CodeGear{ @Take(”name”)
    public DataGear<String> name = new DataGear<>();

    @Override
    protected void run(CodeGearManager cgm) {
        System.out.println(”this name is : ” + name.getData());
    }
}
```
* 取得したDGが待ち合わせに指定した型と違う場合はエラーになる

# Christie - 設計の効果
* CodeGearManagerというDGMの管理機構を作ったことでLocalDGM複数立ち上げが可能になった
    * テストや機能拡張がしやすくなった
* アノテーションを用いたことでDG生成とkey指定の分離問題を解決し、処理の見通しを良くした
* 型の整合性を保証することで信頼性が向上した

# Christieと他フレームワークの比較
* Christieの特徴を述べるために他の分散フレームワークとしてAkka、Hazelcastと比較を行う

# Christieと他フレームワークの比較 - Akka
* アクターモデル
    * アクターと呼ばれるオブジェクト同士が並列で非同期メッセージを送受信するモデル
* アクターは固有のアドレス持つ
    * ローカルアクターにもリモートアクターにもアドレス指定でメッセージを送受信
* アクターはメールボックスというキューを持つ
    * 受け取ったメッセージをパターンマッチで順次処理
    * パターンマッチにはScalaのcase classを用いられる。

# Christieと他フレームワークの比較 - Hazelcast
* キーと値の1対1でデータを管理するインメモリ・データグリッド
    * 複数のノードに分散させたデータを、仮想的な1つのメモリ空間に見せるモデル
    * プログラマがサーバを意識せずに共有のタプルスペースに対してデータをget/put
* 共有のタプルスペースに書き込むとマルチキャストで全サーバにデータが贈られる

# Christieと他フレームワークの比較 - 設計思想
* AkkaやHazelcastはロケーション透過性が高く、分散プログラムの煩雑な処理を抽象度を高めることで隠している
* 分散性を明示的に意識しながら細かな処理を記述できる
* 通常計算とメタ計算に分けているため複雑さをセパレートしている

# Christieと他フレームワークの比較 - 記述性
* AkkaはFIFO的にメッセージを処理する複数インプットのときの待ち合わせ処理をプログラマが書かなければならない
* アノテーションを使ったインプットの指定はAkkaやHazelcastにはなく、複数インプットが書きやすいため

# Christieと他フレームワークの比較  - 提供する機能
* NAT
* 圧縮

# まとめ
* AliceのプロトコルやMeta Computationを説明し、TopologyManagerを用いたNAT越えの手法を示した
* Aliceの問題点を整理し、再設計の必要性を述べた
* LocalDGMの複数立ち上げを可能にし、テストや機能拡張がしやすい環境を整えた
* Christieではアノテーションを用いたAPIで信頼性の高い記述を実現した
* Christieを他のフレームワークと比較し、分散性を意識して記述できる特徴があることを述べた

# 今後の課題
* DataGearのメタレイヤーへの移行
* TopologyManagerの実装
* 実用性の検証
* Jungleとの統合
* GearsOSへの移行

<style type="text/css">
<!--
*{
	font:nomal 100% 'PT Sans';
}

ul > li{
	list-style-type:disc;
}

.slide h1{
	text-align:left;
	color:#777777;
	font:bold 40px/1.13 'PT Sans', sans-serif;
	margin-bottom: 50px;
}

div#slide1 h1{
	text-align:left;
	color:#777777;
	font:bold 60px 'PT Sans', sans-serif;
	margin-bottom: 50px;
}

pre > code{
	font-family:'Droid Sans Mono', 'Courier New', monospace;
}

img[alt="opt"]{
	display: block;
	margin-left: auto;
	margin-right: auto;
}

img[alt="right"]{
	margin-right: 0;
}

table {
	margin-left: auto;
	margin-right: auto;
}

th {
    font-size: 120%;
}
-->
</style>
author	Nozomi Teruya <e125769@ie.u-ryukyu.ac.jp>
date	Tue, 06 Feb 2018 11:14:10 +0900
parents	055266d62d84
children	074eb76a9184