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

Topology Managerをもっとかっこよくアピール
前半もっとクリーンナップ

# 目次


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

# 研究目的(2/3)
* Aliceでは、処理をComputationとMetaComputationに階層化し、コアな仕様と複雑な例外処理に分離する。//コアな仕様の例
* 分散環境構築などの複雑な処理はAliceがMeta Computationとして提供する
* 仕様を大きく変更することなくプログラムの挙動が変えられる//分散処理とかの拡張なら指定だけで良い
* 変更前の信頼性を保ったまま拡張可能にする

# 研究目的(3/3)
* Aliceでは分散トポロジー管理の Meta Computation である Topology Manager
* 本研究では、 Topology Managerに NAT越えを実現するための設計を行う
* そしてその設計が Alice アプリケーション同士の接続も可能にすることを示す
↑逆？
Topologyの課題をかく

# 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="50%"}

# 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](./images/KeyDS.svg){:width="50%"}//変更

# Data Segment Manager
* Local DSM … 各ノード固有のデータベース。
* Remote DSM … 他のノードの Local DSM の proxy。接続しているノードの数だけ存在する。  
* Remote DSMに書き込むと対応するノードのLocalDSMに書き込まれる
![opt](./images/remote_datasegment.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="70%"}

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

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

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

# 障害発生時の対応
* KeepAliveというMeta Computationがノードの生存確認を行う
* 一定時間内にノードから応答がない場合、そのノードとの接続を切断し、再接続すべきノードの情報をTopologyManagerに要求する

# 障害発生時の対応
* Closed Event ManagerというMeta Computationは切断・再接続時に指定されたCSを実行する
* 再接続時に特定の処理を行いたい場合はCSを書いてClosed Event Managerに登録する
* これらのMeta ComputationはTopology Manager内でも使用されるため、Meta Meta Computationとも言える

# TreeVNC
* 当研究室で開発したノードを木構造に配置して負荷分散を行う授業向け画面共有システム
* TightVNCを拡張して作られている
![right](./images/treeVNC.svg){:width="40%"}

# AliceVNCとAliceChatの接続
* AliceVNC：Alice上に実装したTreeVNC（Tree Topology）
* AliceChat：Alice上に実装したチャット（Star Topology）
* 既存のAliceVNCとAliceChatをコードの変更を抑えつつ連携させたい
	* 画面のスナップショットをチャットに載せる
	* チャットの内容を画面にコメントとして流す

# TreeVNCのNAT越え
* TreeVNCを学外からも画面共有ができるよう拡張したい
* ソースコードが膨大で複雜であったためNAT越えの実装には至らなかった
* グローバルIPを持っていることを前提としたノードに直接IPを指定して直下の子になるDirect Connectionを実装
![right](./images/directConnection.svg){:width="40%"}

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


# Aliceの課題まとめ
* 別トポロジー、別ネットワークのアプリケーションに接続したい
* コード変更を抑えつつトポロジーの拡張をサポートする機能がTopology Managerに必要

# Topology Managerの拡張設計 -  別トポロジーへの接続
1. 接続を要求する側のいずれかの Node が接続先 Topology Manager(A)のIPアドレスを自身を管理するTopology Manager(B)のDSMに保存。  
*ここでTopology Managerに保存することでRootNodeが落ちてもトポロジーの再構成時にまた接続要求が出せる*  
![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) と接 続し、自身の接続先ノードの情報を取得
![opt](./pictures/private3.svg){:width="70%"}//変更

# Topology Managerの拡張設計 -  別トポロジーへの接続
4. 取得した情報をもとに RootNode(A) に接続  
![opt](./pictures/private4.svg){:width="70%"}//変更

# 複数のTopology Managerへの対応
* Topology Managerは各ノードにnodeNameを割り当て管理
* Topology Nodeは割り当てられたnodeNameをDSとして保持しTopology Managerと通信
* Topology Nodeが各Topology Managerに対応する複数のnodeNameを持つようにする  
![opt](./pictures/somehostname.svg){:width="40%"}//変更

# Local DSMの切り替えによる対応
* 通常のLocal DSMとは別にTopology ManagerごとのLocal DSMを作成しnodeNameを管理
* Tpology Manager/Nodeのコードを大きく変えずにTopology Managerの複数対応が可能  
![right](./pictures/somehostname2.svg){:width="40%"}

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

# Topology Managerの拡張設計 -  別ネットワークへの接続
* 各プライベートネットワーク内を管理するPrivate Topology Manager
* グローバルIPアドレスを持ったGlobal Topology Managerを１つ立てる
* TopologyNodeが複数対応できるためPrivate/Global Topology Managerに接続  
![opt](./pictures/overNAT.svg){:width="40%"}

# Topology Managerの拡張設計 -  別ネットワークへの接続
* 各プライベートネットワークのRootNodeをGlobal Topology Managerが木構造に接続
* Global Topology Manager foresutoに木を構成
* 1つのノードへの接続数は最大４
![right](./pictures/3Dtree.svg){:width="40%"}//変更

# Topology Managerの拡張設計 -  別ネットワークへの接続
* Topology Managerの「参加表明のあったノードで木を構成」仕様は変わらない
* NAT越えはTopology ManagerのMeta Meta Computationと言える  

# Topology Managerの拡張設計 -  別ネットワークへの接続
1. 接続を要求する側のいずれかのノードがGlobal Topology ManagerのIPアドレスを自身を管理するTopology ManagerのDSMに保存
![opt](./pictures/global1.svg){:width="40%"}

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

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

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

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


# Aliceと他言語等との比較(1) - Erlang
* 共通点
	* タスクをプロセスと呼ばれるメモリを共有しないスレッドに分割
	* 共有メモリにアクセスするためのメモリロックの仕組みを必要としない

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


# Aliceと他言語等との比較(2) - Akka
* 共通点
	* 通信部分等を子アクターで分離し階層化

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


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

# 今後の課題
* DSMのレイヤー分け
	* staticのないコードで再設計し、Local DSMをメタレイヤー、トポロジーごとのレイヤーなどに分ける
* APIの再設計
	* put/updateに対しtake/peekがcreate()・setKey()の操作はわかりにくい
* DSの型情報のマネジメント
	* 型情報がないのでpeek/takeする際にわかりにくい



<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>