ソフトウェア界面発表 数理計算科学専攻 松岡研究室 06M37059 梅田典宏

今回の紹介論文 Sujoy Basu, Sujata Banerjee, Puneet Sharma, Sung-Ju Lee, “NodeWiz: Peer-to-peer Resource Discovery for Grids”, In Proceedings of Cluster Computing and Grid 2005(CCGrid 2005), Javier Celaya, Unai Arronategui,“YA: Fast and Scalable Discovery of Idle CPUs in a P2P Network”, In Proceedings of the 7th IEEE/ACM International Conference on Grid Computing (GRID 2006), 2006

背景 ジョブ実行に適した計算資源を高速に発 見することが大規模な Grid 環境では重要 初期のシステムでは集中管理型や静的な 構成をとっていた  スケーラビリティや構成が動的に変わる環境に は不向き

一つの解 :Distributed Hash Table (DHT) 情報に対しハッシュ値を与え、それを元 に情報格納担当のピアを決定し、情報を 複数のマシンで管理する  ピア数・情報数に対してスケーラブル  ノードの動的な構成に対応  完全一致検索に適している Sword[1] のように Range Search をサポートするもの もある 一様分布を取らず偏りがある情報の場合負 荷が集中する

NodeWiz Grid での高速な資源探索を目的とする 分散環境で複数のパラメタの Range Search を実現する  CPU 使用率  搭載・空きメモリ量  搭載・空きディスク量 負荷に応じて動的に負荷分散 レプリカを分散配置  ネットワークの近隣度を考慮に入れている

データ格納 各パラメタを次元とした 空間を各ノードで分割し て管理する 計算資源は、自らの状態 に当てはまるピアに自分 を登録 状態の登録および資源の 探索メッセージは、次に 述べる各ピアが持つ経路 表に基づいてルーティン グされることで行われる。 D 0<x<x1 0<y<y1 A 0<x<x2 y1<y<y2 B x2<x<x3 y1<y<y2 C x3<x<x4 0<y<y2 E x1<x<x3 0<y<y1 x1x2x3 x4x4 y1 y2 0 計算資源

情報の担当範囲 左に示した各ノードの担当範囲は右の 2 分木によって表現され る。 D 0<x<x1 0<y<y1 A 0<x<x2 y1<y<y2 B x2<x<x3 y1<y<y2 C x3<x<x4 0<y<y2 E x1<x<x3 0<y<y1 x1x2x3 x4 y1 Y 0 x3<X<x4 C X<x3 0<Y<y1y1<Y<y2 0<X<x1x1<X<x30<X<x2x2<X<x3 B,C D,B A,B D,E DEAB X y2

経路表 A の経路表 x3<X<x4 C X<x3 0<Y<y1y1<Y<y2 0<X<x1x1<X<x30<X<x2x2<X<x3 B,C D,B A,B D,E DEAB LevelAttrMinMaxNode 0Xx3x4C 1Y0y1D 2Xx2x3B E の経路表 LevelAttrMinMaxNode 0Xx3x4C 1Yy1y2B 2X0x1D

経路表とルーティング LevelAttrMinMaxNode 0Xx3x4C 1Y0y1D 2Xx2x3B A の経路表 例 1: X=v1 (0<v1<x2) かつ Y<v2 (y1<v2<y1) を担当するノードを探索するクエリの ルーティング 1.Level 0 では上の条件を満たさないので C は探索範囲外 2.Level 1 は条件を満たすので D にクエリを 転送する。また、 Level 2 以降も条件を 満たす可能性がある。 3.Level 2 は条件を満たさないので B には転 送しない 4.1 はクエリの条件を満たすので、自らの 保持する情報をクエリの発信元に返す A の担当範囲 0<x<x2 y1<y<y2

負荷分散 :Top-K algorithm 新規参加ノードがどの領域を担当するかに用いる 各ノードは自らの負荷を示す値 workload を持つ  資源の登録・探索クエリを受信するたびに値を 1 増や す  定期的に workload を 2 で割ることで直近のアクセスに 重みをつける  自らの workload を定期的に上流ノードに流す  下流からやってきたノードの workload のうち、負荷 の高い上位 K 個のピアをさらに上流に流す  Tree のルートで得られた上位 K 個のピアを下流の全ピ アに広報する

ノードの参加・脱退 ( 領域分割・合併 ) 負荷の高いノードの担当範囲を分割する際 に、出来るだけ負荷が均等になるように分 割する  各パラメタについて資源登録と探索クエリのヒス トグラムを作り、 K 平均法というクラスタリング アルゴリズムでその中心点を求め、その点で分割 することで均等な負荷になるようにする ノードが脱退する際には、経路表の一番下 にあるノードに自分の担当する範囲を渡す

高速化手法 レプリケーション  既存ノードの負荷が小さいときには、近隣ノードの経路 表に含まれるノードのレプリカとなる レプリカを近い場所につくることで探索を高速化する  レプリカノードと元ノードの一貫性をどの程度確保する かが課題 本論文では評価の対象外としている 経路のキャッシュ  以前自分が投げたクエリの範囲とその結果となるノード をキャッシュし、自分の経路表に加える 次回その範囲のクエリがやってきたときにそのホップ数を 減少させる効果

シミュレーションによる評価 パラメタは 6 次元  過去 1 分 /5 分 /15 分間の平均負荷  ディスク / メモリ / スワップの空き容量 計算資源の状態変化のデータセット  PlanetLab[2] 参加ノードの観測データ 台数不足分は生成したデータ  パレート分布に従って生成したデータ データセンターでよく見られるパターンに近い

評価 : ノード数とホップ数 6 つのパラメタを指定し た広告・クエリを投げた ときの平均ホップ数 クエリ・広告共にノード 数 n に対し、目的の情報を 持つノードに到達する平 均ホップ数は O(logN) に抑 えられている

評価 : 経路表のサイズ PlanetLab, Synthesis とも に各ノードが持つ経路表の 平均サイズ・最大サイズを 測定 ノード数 N に対し、経路表 のサイズは O(logN) の増加に とどまる

評価 : 各ノード負荷の負荷分散 負荷の分散度合いを各ノードの 負荷の標準偏差で評価を行った。 k 平均法を用いた範囲分割手法を Clustering とし, 比較のために、 単純に範囲を半々に分割したも のを K-d Tree とする。 本論文で提案した手法において、 標準偏差が小さくなっているこ とから、負荷がより適切に分散 されていることが示されている。

評価 : 資源登録・探索メッセージに含まれ るパラメタの数とホップ数 資源の登録と探索に用いるパ ラメタの数を変えたときの メッセージのホップ数を測定 した パラメタ数を減らすことで担 当に当てはまるノード数が増 加することで、ホップ数が増 えトラヒックが増加する 登録より探索のほうが範囲が 広いために同じパラメタ数で もホップ数が増加している。

評価 : 経路のキャッシュ 過去のクエリとそれに 対応するノードを各 ノードの経路表に キャッシュすることで、 トラフィックが大きく 減少できている

YA より実行に適した計算資源を高速に探索  良い計算資源とは？ 処理速度が高速 ネットワーク的に近い ( ホップ数の小さい ) 場所にある 資源数と投入ジョブ数の増加にスケーラブ ルであることが望ましい

B-Tree ベースのネットワーク IP アドレスを各ノードの値としている  ネットワーク的に近いノードが相互につながることがね らい 親ノードは子ノードおよび自分の値の範囲を もっている 近隣ノードや隣の木のノードとの接続を持つ  親ノードの障害への対処

ノードの新規参加・脱退 基本的には B-Tree のノード追加・削除と 同じ  すべてのノードは m から 2m 個の子を持つ ルートノードだけは 2 から 2m 個の子を持つ  もし子が 2m 個を越えた時は、  もし子が m 個未満になった時は、親とマージす る 常に木の高さが最小になるようにツリーを 動的に変更することでホップ数を小さく する

Free Node の管理 各ノードは、子に含まれる遊休ノードの台数・最 高性能・最小ホップ数を定期的に収集する 収集した情報を親ノードに転送するのは、次の条 件を満たしたときのみ  前回収集時に比べ より性能の良いノード よりホップ数の小さいノード 遊休ノード数が大きく変化したとき これによって、ツリー上位のトラヒックが混雑する ことを防ぐ

Free Node の探索 探索開始ノードの枝にぶら下がっている 遊休ノードの中から、より高性能でホッ プ数の小さい資源を選び、それにジョブ を割り当てる もし足りない場合は、親ノードに探索ク エリを転送して探索を続ける 最悪ホップ数は葉のノードから別の葉の ノードで O(2log m N) であり、スケーラブル といえる

YA の評価 ネットワークシミュレータ OMNeT++[3] によ るシミュレーション ノード数 ノード間のバンド幅 1Mbps ノード間通信遅延 200ms ノードの性能 2000MIPS B-Tree のパラメタ m6 ～ 10

評価 : 資源にジョブを割り当てるまでの時 間 探索に必要な最悪ホップ数は O(log m N) であるため、 m が大きくなるほど木が低くなりホップ数が小さく なり、遊休ノードをより早く見つけることが出来る N が大きくなるにつれ、探索に必要な時間は O(logN) で増加する

評価 : ノード負荷とトラヒック m を大きくすることで メッセージ受信量が増 え、負荷とトラフィッ クが大きくなっている ノードの負荷と探索時間は m によって左右さ れ、トレードオフの関係にある

NodeWiz と YA の比較 スケーラビリティ  NodeWiz はノードの負荷によって動的に担当範 囲を分割・合併することで負荷分散を行う  YA はネットワーク的に近いノードをより優先 的に発見 探索性能  YA は一つのパラメタしか扱えない  NodeWiz は複数のパラメタを扱える

参考文献 [1]Sword D. Oppenheimer, J. Albrecht, D. Patterson, and A. Vahdat, “Distributed resource discovery on planetlab with SWORD”, First Workshop on Real, Large Distributed Systems (WORLDS 2004), [2]PlanetLab [3]OMNeT++

評価 : ノード負荷とトラヒック 通常時 高負荷時

YA のまとめ ネットワーク的に近いノード ツリー上位に遊休ノードの情報を集約す る

既存のシステム 中央のリポジトリに各計算資源が自らの 情報を登録する  Condor  Globus の MDS スケーラビリティに難