Mercurial > hg > Papers > 2016 > nozomi-sigos

title: 分散システム向けのTopology Managerの改良
author: 照屋のぞみ  河野真治
profile:琉球大学 工学部 情報工学科

# 研究目的(1/3)
* 当研究室が開発している並列分散フレームワークAliceではスケーラブルな分散プログラムを信頼性高く記述できる環境を実現する。
* ここで言う信頼性とは定められた環境下で安定して仕様に従った動作を行うことを指す。
* スケーラビリティと信頼性の向上のため、Aliceでは当研究室が提案しているデータを Data Segment、タスクを Code Segment という単位で分割して記述するプログラミング手法を採用している。

# 研究目的(2/3)
* さらに処理をComputationとMetaComputationに階層化し、コアな仕様とそれを支える複雑な例外処理に分離する。
* 分散環境構築などの複雑な処理をAliceがMeta Computationとして提供するため、仕様の変更を抑えた拡張が可能となる。
* 例えば、分散アプリケーションでNATを越えて通信するように拡張したい場合、コアな処理は変えずMeta Computationに指定する分散トポロジーを変更するだけで良い。
* 拡張する際にメインのコードを破壊しないため変更前の信頼性を保つことができる。

# 研究目的(3/3)
* 分散アプリケーションの例題の１つとして画面配信システムTreeVNCをAlice上で実装する中で、NATを介した別ネットワークや別トポロジー上のノードとの接続が必要であることがわかった
* 本研究では、分散トポロジーの管理を行うMeta ComputationであるTopology Managerに対し、別ネットワーク・別トポロジーでのノード間接続を実現するための拡張設計を行う

# 目次
* Aliceの概要
	* Code Segment / Data Segment
	* Data Segment Manager
	* Computation / Meta Computation
	* Topology Manager / Topology Node
* Alice上にTreeVNCを実装する際の課題
	* VNCとChatを連携させる課題
	* TreeVNCにおけるNATを越えた接続の課題
* Topology Managerの拡張設計
	* 別トポロジー間の接続のための設計
		* Topology Nodeの複数対応
	* 別ネットワーク間の接続のための設計
* 他言語等との比較
* まとめ

# 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に書き込まれる
![opt](./pictures/newDSM.svg){:width="50%"}

# 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を指定する
* シンプルで見通しの良いコードを保つ

# 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を用いて実装されている。

# 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”]
}
```

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

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

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

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

# 障害発生時の対応
* KeepAliveというMeta Computationがノードの生存確認を行う
* Closed Event ManagerというMeta Computationは切断・再接続時に指定されたCSを実行する
* これらのMeta ComputationはTopology Manager内でも使用されるため、Meta Meta Computationとも言える

# Alice上にTreeVNCを実装する際の課題
* TreeVNC
	* 当研究室で開発したノードを木構造に配置して負荷分散を行う授業向け画面共有システム
	* TightVNCを拡張して作られている

* AliceVNC
	* Alice上に実装したTreeVNC
	* Dinamic Topology ManagerでTree Topologyを構成

![opt](./images/treeVNC.svg){:width="40%"}

# 課題1 - AliceVNCとAliceChatの接続
* AliceChat
	* Alice上に実装したチャット
	* Dinamic Topology ManagerでStar Topologyを構成
* 既存のAliceVNCとAliceChatをコードの変更を抑えつつ連携させたい
	* VNC画面のスナップショットをチャットに載せる
	* チャットの内容をVNC画面にコメントとして流す
* 別トポロジーのアプリケーションへの接続をサポートする機能が必要

# 課題2 - NATを越えた接続
* TreeVNCでは学外からも画面共有ができるよう拡張したいNAT越えの要求がある
* ソースコードが複雜で他のコードも大きく修正しならなかったため、NAT越えの実装には至らなかった
* グローバルIPを持っていることを前提としたノードに直接IPを指定して直下の子になるDirect Connectionを実装し受信のみを可能にしている

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

# 課題2 - TreeVNCのNAT越えの欠点
* 複数の別ネットワークからの接続があるとルートノードにネットワーク数分の負荷がかかる
* どちらもプライベートネットワークだった場合に通信できない(中継サーバのプログラムを用意しなければならない)
* 分散アプリケーションにおけるNATを越えた通信は重要だがプログラマが実装するのは容易ではない
* 別ネットワークのアプリケーションへの接続をサポートする機能が必要

# Topology Managerの拡張設計 -  別トポロジーへの接続
以降の機能をMeta Meta Computationとして実装
1. 接続を要求する側のいずれかの Node が接続先 Topology Manager(A)のIPアドレスを自身を管理するTopology Manager(B)に保存。
![opt](./pictures/private1.svg){:width="70%"}

# Topology Managerの拡張設計 -  別トポロジーへの接続
2. Topology Manager(B)はRootNode(B)にTopology Manager(A) への接続をするよう要求
![opt](./pictures/private2.svg){:width="70%"}

# Topology Managerの拡張設計 -  別トポロジーへの接続
3. RootNode(B) が Topology Manager(A) と接続し、接続すべきRootNode(A)の情報を取得
![opt](./pictures/private3.svg){:width="70%"}

# Topology Managerの拡張設計 -  別トポロジーへの接続
4. 取得した情報をもとに RootNode(A) に接続
*※①でTopology Managerに保存することでRootNodeが落ちてもトポロジーの再構成時にまた接続要求が出せる*
![opt](./pictures/private4.svg){:width="70%"}

# 複数のTopology Managerへの対応
* この機能を実現するには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%"}

# Keyの切り替えによる対応
* DSMを管理するclassがstaticのためLocal DSMが１つしか生成できない
* staticを抜くにはAliceのコードを大幅に変更しなければならない
* nodeNameのDSを管理するkeyにManagerごとの番号を付け加えKeyによって切り替えている
![opt](./pictures/somehostname3.svg){:width="50%"}

# Topology Managerの拡張設計 -  別ネットワークへの接続
* Aliceではトポロジー管理がアプリケーションから分離しているため、Topology Managerを増やすことでトポロジーの拡張が可能
* 各プライベートネットワーク内を管理するPrivate Topology Manager
* グローバルIPアドレスを持ったGlobal Topology Managerを１つ立てる
* TopologyNodeが複数対応できるためPrivate/Global Topology Managerに接続
![opt](./pictures/overNAT.svg){:width="50%"}

# Topology Managerの拡張設計 -  別ネットワークへの接続
* Private Topology Managerがプライベートネットワーク内で木構造を構成
* 各RootNodeをGlobal Topology Managerが木構造に接続（森構造）
* 1つのノードへの接続数は最大４
* Topology Managerの「参加表明のあったノードで木を構成」仕様は変わらない
![opt](./pictures/3Dtree.svg){:width="50%"}

# Topology Managerの拡張設計 -  別ネットワークへの接続
以降の機能をMeta Meta Computationとして実装
1. 接続を要求する側のいずれかのノードがGlobal Topology ManagerのIPアドレスを自身を管理するTopology ManagerのDSMに保存
![opt](./pictures/global1.svg){:width="70%"}

# Topology Managerの拡張設計 -  別ネットワークへの接続
2. Topology ManagerはRootNodeにGlobal Topology Managerへの接続をするよう要求
![opt](./pictures/global2.svg){:width="70%"}

# Topology Managerの拡張設計 -  別ネットワークへの接続
3. RootNodeがGrobal Topology Managerと接続し、自身のIPアドレスを送る。Global Topology Manager が受け取ったIPアドレスがプライベートアドレスであれば、ノードに対してNATの外側IPアドレス/ポート番号を要求される。RootNode はそれに返答。
![opt](./pictures/global3.svg){:width="70%"}

# Topology Managerの拡張設計 -  別ネットワークへの接続
4. UDP hole punching 行われ、Network1のRootNodeとNetwork2のRootNodeが接続される
![opt](./pictures/global4.svg){:width="70%"}

# Topology Managerの拡張設計 -  別ネットワークへの接続
5. もし接続が確立されなければ、Global Topology Manager がデータ中継用の CSを用意しデータを中継する
![opt](./pictures/global5.svg){:width="70%"}


# Aliceと他言語等との比較(1) - Erlang
Ericssonが開発した並列指向関数型プログラミング言語

* 共通点
	* タスクをプロセスと呼ばれるメモリを共有しないスレッドに分割
	* 共有メモリにアクセスするためのメモリロックの仕組みを必要としない

* 相違点
	* Topologyの構成等はユーザーが書く
	* NAT越えをサポートするライブラリがありプログラマはそれを組み合わせてNAT越えを行う


# Aliceと他言語等との比較(2) - Akka
アクターモデルのScalaおよびJava向けの並列および分散処理フレームワーク

* 共通点
	* 通信部分等を子アクターで分離し階層化

* 相違点
	* Topologyの構成等はユーザーが書く
	* 外側IPアドレス/ポート番号を指定できるが、ポートマッピングはユーザーが記述しなければならない


# まとめ
* 別トポロジー・別ネットワークのアプリケーションとの接続を可能にするため、分散トポロジーの構成・管理をするMeta ComputationであるTopology Manager/Nodeの拡張設計を行った。
* DSM の切り替えにより Topology Node を複数の Topology Manager に対応させ、Meta Meta Computation として NAT 越えの機能を追加することで、Topology Manager/Node のコードを大きく変えず自由度の高い通信が可能になると期待される。
* しかし、それを実現するにはAliceのDSMを管理するclassのstaticを取り除かなければならず、それは容易ではなかったためAlice自体の再設計を行ったうえで実装を行いたい。


<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	Mon, 30 May 2016 23:16:41 +0900
parents	ceb02999f1a5
children