# HG changeset patch # User Nozomi Teruya # Date 1517751072 -32400 # Node ID d09fb22608f15d5af20910a3bd3e744c7dcd1faa # Parent b9222de888895747349aba1cf32da834739a1a3c change chapter1 diff -r b9222de88889 -r d09fb22608f1 paper/images/nat.pdf Binary file paper/images/nat.pdf has changed diff -r b9222de88889 -r d09fb22608f1 paper/nozomi-master.pdf Binary file paper/nozomi-master.pdf has changed diff -r b9222de88889 -r d09fb22608f1 paper/nozomi-master.tex --- a/paper/nozomi-master.tex Sun Feb 04 17:27:53 2018 +0900 +++ b/paper/nozomi-master.tex Sun Feb 04 22:31:12 2018 +0900 @@ -59,8 +59,8 @@ captionpos=b,%キャプションの位置 } -\def\lstlistingname{リスト} -\def\lstlistlistingname{リスト目次} +\def\lstlistingname{ソースコード} +\def\lstlistlistingname{ソースコード目次} %%% 索引のために以下の2行を追加 @@ -99,62 +99,117 @@ \chapter{分散フレームワークへの要求事項} スマートフォンやタブレット端末の普及率が増加している。 -それに伴いインターネット利用者数も増加しており、ネットワーク上のサービスには、信頼性とスケーラビリティーが要求される。 +それに伴いインターネット利用者数も増加しており、ネットワークサービスにはそれに対する処理能力が求められる。 +サーバの処理能力を増強するアプローチとして、スケールアップとスケールアウトがある。 +スケールアップはサーバそのものを増強することで処理能力を向上させる手法であり、スケールアウトは複数のサーバを接続することで処理能力を上げる手法である。 +スケールアウトは安価なサーバで実現でき、サーバが故障しても別のサーバでカバーできるため、システムを安定運用させやすく、現代のネットワークサービスの要求に合っていると言える。 + +スケールアウトのように複数のサーバで処理をまたぐ場合、サーバには分散プログラムが必要になる。 +分散プログラムとは、プログラムの個々の部分が複数のノード上で並列に実行され、各ノードがネットワークを介して互いに通信を行いながら全体の処理を進行する計算手法のことである。 +安定したネットワークサービスを提供するためには、分散プログラムに信頼性とスケーラビリティが要求される。 ここでいう信頼性とは、定められた環境下で安定して仕様に従った動作を行うことを指す。 これには仕様を記述しやすさも含まれ、可読性が高いほどバグを抑えた信頼性が高いと言える。 - またスケーラビリティーとは、分散ソフトウェアに対して単純にノードを追加するだけで性能を線形的に上昇させることができる性質である。 -分散フレームワークには分散トポロジーの構成などの分散アルゴリズムが求められる。 しかし、これらをもつ分散プログラムをユーザーが一から記述することは容易ではない。 なぜなら、並列で動く分散した資源を意識しながら記述するのは容易ではなく、また、どのように分散したノードの選択を行えば良いのか明確ではないからである。 -本章では、分散フレームワークであるAkka\cite{Akka}、Hazelcast\cite{Hazelcast}と当研究室で開発したAlice\cite{Alice1}\cite{Alice2}の記述モデル・分散処理を支える機能を比較しながら、本論文で設計するChristieの設計目標を述べる。 + +分散プログラムには以下の３つの要素がある。 +\begin{itemize} +\item {ノード内の計算} +\end{itemize} + +\begin{itemize} +\item {ノード間通信} +\end{itemize} -\section{記述モデル} -Akkaではアクターモデルという、アクターと呼ばれるオブジェクト同士が並列で非同期メッセージを送受信するモデルを採用している。 -アクターはそれぞれメッセージボックスを持っており、受け取ったメッセージをcase文を使って順次処理していく。 -アクター同士は固有のアドレスで指定してメッセージを送り合う。 +\begin{itemize} +\item {地理的に分散したノード} +\end{itemize} + +ノード内の計算には通信プロトコルやデータベースが含まれる。 +またノード間通信には、トポロジーの構成や通信の信頼性や速度、データの転送やデータの圧縮などの要素がある。 + +これらの要素をサポートするのが分散フレームワークである。 +すなわち分散フレームワークには、プロトコルの定義、それによってアクセスされるデータベース、トポロジーの決定いった分散アルゴリズムや、信頼性と拡張性の高い通信の提供が求められる。 + +本章では、これらの項目別に分けて、分散フレームワークであるAkka\cite{Akka}、Hazelcast\cite{Hazelcast}と当研究室で開発したAlice\cite{Alice1}\cite{Alice2}を比較し、本論文で設計するChristieの設計目標を述べる。 -また、Hazelcastはキーと値の1対1でデータを管理するインメモリ・データグリッドであり、複数のサーバが同じメモリかのように扱う。 -プログラマはサーバを意識せずに共有のMapに対してデータをget/putできる。 +AkkaはScalaおよびJava向けのオープンソースの並列分散処理フレームワークであり、HazelcastはHazelcast社が開発したJava向けのオープンソースインメモリデータグリッドである。 + +\section{プロトコルとデータベース} +Akkaではアクターモデルという、アクターと呼ばれるオブジェクト同士が並列で非同期メッセージを送受信するモデルを採用している。 +アクターは固有のアドレス持っており、ローカルのアクターにもリモートのアクターにも同じようにアドレスを指定することでメッセージを送りあえるというプロトコルになっている。 +アクターはそれぞれメールボックスというキューを持っており、メールボックスに受け取ったメッセージをパターンマッチで順次処理していく。 +このパターンマッチにはScalaのcase classを用いられる。 +case classとは、データ構造とデータを同時に持つことができ、その両方を一括してパターンマッチさせることができるクラスである。 +メッセージをcase classで記述することにより、スムーズなメッセージの処理を可能にしている。 -AliceはタスクをCode Segment、データをData Segmentという単位で記述し、Code SegmentはインプットとなるData Segmentが全て揃うと並列に実行される。 -Data SegmentはData Segment Managerというノードごとに存在するデータベースによって管理される。 -各ノードにはラベル付きのプロキシであるRemote Data Segment Managerを立て、ラベルを指定してアクセスする。 +Hazelcastは、キーと値の1対1でデータを管理するインメモリ・データグリッドである。 +インメモリ・データグリッドとは、複数のノードに分散させたデータを、アプリケーション側からは仮想的な1つのメモリ空間に置かれているように見せるモデルである。 +そのため、プログラマがサーバを意識せずに共有のタプルスペースに対してデータをget/putできるプロトコルとなっている。 +共有のタプルスペースに書き込むとそれに接続しているノードにデータを行き渡らせる、マルチキャストベースの通信を採用している。 -Akkaでは、メッセージが集中した場合にそれを処理するcase文が増えてしまう問題や、複数のインプットを待ち合わせたい場合に記述が煩雑になる問題があった。 +Aliceは、タスクをCode Segment、データをData Segmentという単位で記述し、Code SegmentはインプットとなるData Segmentが全て揃うと並列に実行される。 +Data Segmentは対になるkeyが存在し、Data Segment Managerというノードごとに存在する独自のデータベースによって管理されている。 +各ノードにはラベル付きのプロキシであるRemote Data Segment Managerを立て、ラベルとkeyを指定してデータをtake/putするプロトコルとなっている。 + + +記述の面において、Akkaではメッセージが集中した場合にそれを処理するパターンマッチが増えてしまう問題や、複数のインプットを待ち合わせる際に記述が煩雑になる問題があった。 しかしAliceはインプットを明確に記述でき、複数のインプットを持てるため、そのような煩雑さがない。 -また、Hazelcastではロケーション透過性が高く、データはマルチキャストで通信するため、プログラマがトポロジーを把握しにくかった。 -Akkaでは送り先をドメインで指定するためどのような処理をするアクターにメッセージを渡しているのか分かりづらかった。 -一方でAliceでは他のノードにラベルでアクセスするため、分散計算の見通しが良い。 +プロトコルの設計方針において、AkkaやHazelcastは分散通信の複雜さを抽象度を高めることで隠す方針であるため、ロケーション透過性が高く、プログラマからは処理の流れを把握しにくくなっていた。 +一方でAliceはそのような抽象度は持たせず、処理の流れを明確に見通せたほうが、処理途中で細かな計算が必要になった場合にチューニングがしやすいと考えている。 +そのため、ラベルを用いてリモートノードを意識的に選択する。 +Aliceでは明示的に分散性を意識する代わりに、Aliceは計算を通常計算とそれを支えるメタ計算として分離することで記述の複雑さを回避している。 +また、Akkaでは送り先をドメインで指定するためどのような処理をするアクターにメッセージを渡しているのか分かりづらかったが、Aliceでは他のノードにラベルでアクセスできるため処理の見通しを良いと言える。 -しかしAliceのAPIシンタックスは直感的でなく、プログラマが処理の順番やデータの型を考慮して書く必要があった。 +このように、Aliceのプロトコルの特徴は分散処理の見通しの良さといえる。 +しかし、現状のAliceのAPIシンタックスは直感的でなく、プログラマが処理の順番やデータの型を考慮して書く必要があった。 これではバグを引き起こす可能性が高いため、信頼性を上げるにはよりユーザーフレンドリーなシンタックスで再設計すべきだと考えた。 -\section{分散処理を支える機能} -ここではスケーラビリティの指標として特にトポロジーの構成、フォールト・トレランス性、圧縮通信、NAT越えについて比較する。 +\section{トポロジーの構成} AkkaではAkka Streamという機能で処理の流れが記述できる。 N入力1出力、1入力N出力、出力のみ、などが用意されたJunctionsと呼ばれる要素をつなぎ合わせることでトポロジーを記述する。 -また、Akkaではアクターで親子関係を構成でき、親アクターは子アクターを監視し障害が起こった際に再起動や終了といった処理を指定できる。 HazelcastにはMapやQueueといったメモリ空間内のデータ構造は指定できるが、具体的なノード間トポロジーを記述する機構がない。 -１つのサーバで障害が起きても他のサーバがデータを共有しているため、データを失うことなく素早く復旧ができる。 + +AliceではTopologyManagerという機構が分散ノードを管理しており、静的・動的なトポロジーを自動構成する。静的トポロジーではプログラマがトポロジーを図として記述できるため、より分かりやすく詳細な設定ができる。 + + +\section{信頼性・拡張性の高い通信の提供} +ここでは信頼性・拡張性の高い通信の指標として、障害耐性、圧縮・転送通信、NAT越えについてを比較する。 -一方、AliceではTopologyManagerという機構が分散ノードを管理しており、静的・動的なトポロジーを自動構成する。静的トポロジーではプログラマがトポロジーを図として記述できるため、より分かりやすく詳細な設定ができる。 -また、TopologyManagerのKeepAlive機能がノードを監視しており、どこかのノードに障害が起こればトポロジーを再構成するといった対応ができる。 +\subsection*{障害耐性} +分散プログラムでは、１つのノードがダウンしてもシステム全体は動き続けなければならないため、フォールト・トレラントであることが重要である。 + +Akkaでは親子関係を構成でき、親アクターは子アクターを監視し障害が起こった際に再起動や終了といった処理を指定できる。 -\newpage +また、Hazelcastは、１つのサーバで障害が起きても他のサーバがデータを共有しているため、データを失うことなく素早く復旧ができる。 + +Aliceでは、TopologyManager内にKeepAliveという機能があり、常にノードが生きているかHeartbeatを送信して監視しており、どこかのノードに障害が起こればトポロジーを再構成するといった対応ができる。 + -また、通信するデータの圧縮を指定したい場合、Akka・Hazelcastはシリアライザが用意されているため、そのメソッドを呼び出すことでzip/unzipを行う。 -一方でAliceは圧縮したままの転送を想定した圧縮・転送機能を持っている。 +\subsection*{圧縮・転送通信} +ノード間通信でより速い通信をするためには、送信するデータを圧縮する機能や、受け取ったデータをそのままほかノードへ転送する機能が求められる。 + +データの圧縮を指定したい場合、Akka・Hazelcastはシリアライザが用意されているため、そのメソッドを呼び出すことでzip/unzipを行う。 +また、転送を指定したい場合、Akkaにはforwardメソッドがあるためそれを呼び出すことで受け取ったデータの転送が可能だが、Hazelcastは一つのMapへのアクセスに見立てているため、転送にもputを用いる。 + +一方でAliceは圧縮の展開と転送を同時に行うことを想定した圧縮・転送機能を持っている。 Data Segment内に圧縮と非圧縮の両形式を同時に持てるため、受け取った圧縮データを展開をしながら圧縮したまま別ノードに転送することができる。 -また、圧縮するには送信する宛先ラベルに"compressed"とつけるだけでよく、データ取得時に自動で展開もされるため、プログラマがコードを追加する必要がなく圧縮・非圧縮を簡単に切り替えられる。 +また、圧縮するには送信する宛先ラベルに"compressed"とつけるだけでよく、データ取得時に自動で展開もされるため、プログラマがメソッドの呼び出しを追加する必要がなく圧縮・非圧縮を簡単に切り替えられる。 -HazelcastではNAT越えをサポートする機能はなく、プログラマが自前で書かなければならない。 +\subsection*{NAT越え} +ネットワーク間通信の大きな問題の一つに、NATがある。 +NATとは、WANとLANの間にあるIPアドレスの変換機構である。 +NATを隔てたプライベートネットワーク内では、LAN内だけでユニークなプライベートIPアドレスを持っており、WAN側からはそのIPアドレスを直接指定してアクセスできないためアドレス変換を行う必要がある。 +そのためNATを越えたノード間通信は容易ではなく、分散フレームワークでそれをサポートできることが望ましい。 + +しかしHazelcastではNAT越えをサポートする機能がなく、プログラマが自前で書かなければならない。 Akkaではノードの設定にグローバルアドレスとプライベートアドレスを両方登録することでNATを越えた通信を可能にする。 AliceにNAT越えの機能はないが、TopologyManagerが各ノードのData Segment Managerと通信してトポロジー管理をしており、TopologyManager/Data Segment Managerを複数立ち上げることによりプライベートトポロジーとグローバルトポロジーの同時構成が可能だと考えた。 しかし、Aliceが複数のData Segment Managerを持てない実装だったため、AliceのままでNAT越えを実装することは困難であると判明した。