PCクラスタ間ファイル複製スケジューリング

情報処理学会論文誌
コンピューティングシステム
Vol. 3
No. 3
113–125 (Sep. 2010)
files are distributed very unevenly amongst the nodes.
PC クラスタ間ファイル複製スケジューリング
鈴 木 克 典†1
建
部
修
見†1
1. は じ め に
ネットワークの広帯域化にともない，広域環境下で大規模なデータを共有するデータグ
ネットワークの広帯域化にともない遠隔 PC クラスタ間での大規模データ共有の
要求が高まってきた．一方，効率的な大規模データ処理のために PC クラスタのロー
カルディスクが積極的に用いられるようになってきた．その結果，PC クラスタ間に
おける多数のローカルディスク間の効率的な並列ファイル転送が必要となってきた．
本論文ではクラスタ間広域ファイル複製作成をグラフにより定式化し，その問題を解
決するためのファイル複製選択問題・転送順序スケジューリングを線形計画法，貪欲
法，リストスケジューリングにより求めるアルゴリズムを提案する．また，転送処理
実行時に複製を作成することでより効率的なファイル転送を行うための複製作成スケ
ジューリングアルゴリズムを提案する．これらをシミュレーションにより評価した結
果，ファイルが特定のノードに偏って配置されていた場合で複製数が多い場合では線
形計画法によるスケジューリングが良い性能を示していた．
リッドの試みが多数なされている1),2),6) ．このような広域環境でのデータ共有では大規模
データファイルの複製作成が重要であり，そのために現在まで高遅延・広帯域ネットワーク
での単一ファイルの効率的なファイル転送に関する研究がなされている．
一方，近年では科学技術計算など大規模計算において，PC クラスタによる並列計算が一
般的に用いられている．PC クラスタで大規模データ処理を行う場合，各計算ノードのロー
カルディスクを積極的に利用することで高速かつ拡張性のあるデータ I/O を実現すること
ができる．この工夫は Google File System 7) ，HDFS 5) ，Gfarm 11),13) などの分散ファイ
ルシステムにも応用されており，さらにこれらではクラスタ内でファイル複製を作成するこ
とで可用性，信頼性の向上も図っている．
以上で述べたように高遅延・広帯域な広域環境において，複数ディスクに分散したファイ
Replication Scheduling for a Set of Files between
PC Clusters
れた PC クラスタ間で多ノード対多ノードのファイル転送を効率的に行うためのスケジュー
Katsunori Suzuki†1 and Osamu Tatebe†1
のノードが保持するファイルを表す．そして Site A のすべてのファイル Fj を Site B に転
ル群の複製を作成する要求がある．そこで我々は図 1 のように広帯域ネットワークで接続さ
リング手法を提案する．図 1 中の Ni は PC クラスタの各計算ノードを表し，隣の Fj はそ
送しファイル複製を作成することを表している．このとき提案手法では適切なファイル転送
Thanks to increases in wide-area network bandwidth, it is now possible to
efficiently share data on a large scale. While network bandwidth has become
wider, network data access is still significantly slower than using local disks
because of enormous latency. Therefore in order to improve I/O performance
each compute node should read data from its local disk as much as possible.
In order to achieve this goal, we will need efficient and parallel file transfer
mechanisms between compute nodes. Using graph theory to model wide-area
file replication on PC clusters, we have developed new algorithms that improve
I/O performance on PC clusters. In order to determine our file transfer strategy we developed two file replica selection algorithms; one based on a linear
programming approach the other based on a greedy algorithm. We are also
proposing a dynamic replica creation algorithm that increases throughput by
more equally distributing work among the source cluster nodes. Our simulation results show the linear programming based replicate selection algorithm
produces much better scheduling results than the greedy algorithm when the
113
順序スケジューリングを行ったうえで，各計算ノードが並列転送を行う．これは過剰なノー
ドが同時に転送を行うことで輻輳が発生し転送速度が低下することや，同時に 1 つのディ
スクに対し複数ファイルを読み書きすることで，シークが頻発しディスク I/O スループッ
トが低下することを防ぐためである．
転送ファイルの複製がすでに存在する場合には，適切なファイル複製の選択を行うことで
より効率的な転送を行う．さらに，よりファイル転送時間を短縮するために，ファイル転送
実行時に送信元クラスタ内において動的に複製を作成し，後に複数ノードで並列にファイル
†1 筑波大学大学院システム情報工学研究科
Graduate School of Systems and Information Engineering, University of Tsukuba
c 2010 Information Processing Society of Japan
114
PC クラスタ間ファイル複製スケジューリング
を提案している3) ．これは高性能な並列ファイルシステムの利用を仮定しているが，本研究
では特別な並列ファイルシステムを仮定せず，クラスタ内の各計算ノードのローカルディス
クに分散したファイル群の転送を扱っていることが大きな違いといえる．
また，Weigle らは N ノード対 M ノードのデータ転送について “Composite Endpoint
Protocol: CEP” を提案している12) ．CEP は全体として最も効率の良い各ノードへの転送
ファイル複製の選択割当てと各ノードの転送順序スケジューリングを求めるもので本研究と
の類似点が多数ある．しかしながら，輻輳の発生やディスクのシーク頻発による速度低下な
どは考慮していない．また，本研究が高遅延・広帯域な環境を前提としていることも違いと
いえる．
3. クラスタ間広域ファイル複製作成
3.1 環 境 設 定
図 1 クラスタ間広域ファイル複製作成
Fig. 1 File replication on PC clusters.
本研究では図 1 で示しているように，ある PC クラスタ Site A の各計算ノードのローカ
ルディスクにファイル群が格納されていることを想定し，これらのファイル群を遠隔の PC
クラスタ Site B の各計算ノードのローカルディスクへと複製を作成することを想定する．
想定するファイル複製作成では基本的に各計算ノードが転送先 PC クラスタの計算ノードと
転送を行う．
本論文では，まず 2 章において関連する既存の研究について議論し，その問題点について
1 対 1 で通信し，複数計算ノードが並列にファイル転送を行う．転送ファイルは PC クラス
述べた後，3 章において提案する PC クラスタ間広域ファイル複製作成について考察し，解
タ内の複数のノード上に複製が存在する可能性があると仮定する．ここでの複製とは完全な
決すべき問題点についてまとめる．次に 4 章で 3 章でまとめた問題点について定式的に表
形でのファイル複製を意味し，一部分のみの複製は想定しないものとする．この仮定の下，
現し，さらに 5 章において定式化をもとに線形計画法，貪欲法，リストスケジューリングに
適切なファイル複製を選択し他 PC クラスタへ転送する．このとき，送信元 PC クラスタ
よるスケジューリングアルゴリズムについて提案する．6 章ではアルゴリズムのシミュレー
内でのファイル複製の数や配置は受信先 PC クラスタでは保存されないとする．
タによる評価について議論し，7 章でまとめとする．
また，2 つの PC クラスタ間は広帯域なネットワークで接続されているが，地理的に離れ
ており高遅延であるとする．このとき，各ノードが無計画なバースト転送を行った場合で
2. 関 連 研 究
はスイッチにおいてパケットロスを頻発させる可能性があり，本来のネットワーク性能を実
これまで，広域環境で用いられるような広帯域，高遅延での複製作成には GridFTP
10)
現することは難しい．この問題を解決する方法にそれぞれの通信ストリームをトラフィック
がよく用いられてきた．これは単一ファイルを効率的に転送するためのものである．しか
制御して転送する方法が有効であることが知られており14) ，本研究では広域通信に関して
し，本研究で想定するように複数ディスクに転送ファイル群が分散する場合においては各
トラフィック制御を行うことを仮定する．そして，トラフィック制御を行った通信ストリー
ノードからの効率的転送と全体としての調整が必要となり，これら単一ファイル転送技術の
ムの本数を制御することにより，広域環境における広帯域ネットワークを効率的に利用す
みでは不十分である．
る．一方，クラスタ内のノード間通信では所定のネットワーク性能を利用できることが多
多ノード対多ノードを想定した関連する研究としては以下のものがあげられる．Allcock
らは並列ファイルシステム間で単一ファイルをストライピングし GridFTP で転送する機構
情報処理学会論文誌
コンピューティングシステム
Vol. 3
No. 3
113–125 (Sep. 2010)
い．このことから一般的に 2 ノード間の通信においては遠隔地のノードと通信する場合よ
りもクラスタ内のノードと通信する場合の方が高バンド幅であると考えられる．たとえば，
c 2010 Information Processing Society of Japan
115
PC クラスタ間ファイル複製スケジューリング
図 2 ではクラスタ内では 900 Mbps で転送可能であるもののクラスタ間の広域通信ではパ
3.2.3 実行時複製作成処理
ケットロスを防ぐために 600 Mbps にトラフィック制御を行っている．このとき，Site A か
3.1 節で述べたように 2 ノード間では PC クラスタ内での通信の方が広域通信よりも広帯
ら Site B へトラフィック制御を行ったうえで，16 ノードが並列に転送することで 10 Gbps
域であると仮定できる．このとき，図 1 においてノード N3 からノード N4 へコピーを作
のクラスタ間ネットワーク帯域を十分に利用することができる．
成しているように，直接に外部へとデータ転送を行うのではなく，クラスタ内においてファ
3.2 広域ファイル複製作成にともなう問題点
イル複製を作成してから並列転送を行うことで，より高速なデータ転送が可能となる．
前節で想定する PC クラスタ環境において複数のディスクに分散したファイル群を効率的
に転送するために解決すべき問題点についてまとめる．
3.2.1 ファイル転送順序スケジューリング
4. モデル化と定式化
前章でまとめた問題点を解決するスケジューリングアルゴリズムを設計するために問題点
1 つのディスクに対し複数のファイルを同時に読み書きした場合，シークが頻発しスルー
のモデル化を行う．ここで，本論文では転送先，転送元 PC クラスタの各計算ノードのロー
プットが極端に低下する可能性がある．また，各ノードが無計画に転送を行った場合，輻輳
カルディスクの容量に関して制限はないものとし，また他ジョブによる CPU 使用，ディス
が発生しスループットが低下すると考えられる．そこで各ノードからのファイルの転送順序
ク使用はないという仮定をおく．以下，ファイル集合を F ，転送元 PC クラスタの計算ノー
と転送トラフィック量をスケジューリングにより制御する必要がある．
ド集合を N ，ファイル数を n，転送元 PC クラスタの計算ノード数を m としファイル名を
{Fi ∈ F |1 ≤ i ≤ n}，転送元 PC クラスタの計算ノード名を {Nj ∈ N |1 ≤ j ≤ m} と表す．
3.2.2 転送するファイル複製の選択・決定
3.2.1 項で述べた転送順序スケジューリングを行うためには，どのファイル複製を転送す
るかという，ファイル複製の選択をあらかじめ行っておかなければならない．ここで，適切
ここで，転送元 PC クラスタで解決すべき問題を，それぞれのファイルについて適切な
ノード上の複製を選択し，それらを転送する順序スケジューリング問題として定式化する．
なファイル複製を選択することにより特定のノードに転送ファイルが集中することを回避
図 3 はファイル集合 F とノード集合 N の関係を表したグラフであり，ファイル Fi から
し，全体としての転送時間を短縮化することが可能であると考えられる．本研究では簡単化
ノード Nj への枝が存在することはファイル複製 Fi がそのノード Nj に存在することを示
のためにファイルの分割割当てを許し，各ファイルは部分ごとに複数のノードへ割り当てら
している．まず，各ファイルについての適切な転送ファイル複製選択問題を図 3 の 2 部グ
れる可能性があるとする．
図 2 広域環境下の通信例
Fig. 2 Example of wide-area and inter-cluster communication.
情報処理学会論文誌
コンピューティングシステム
Vol. 3
No. 3
113–125 (Sep. 2010)
図 3 ファイル複製選択問題のグラフによる表現
Fig. 3 A graph of replica selection problem.
c 2010 Information Processing Society of Japan
116
PC クラスタ間ファイル複製スケジューリング
ラフにおける各ファイルと各ノードとの間のファイル割当て問題として表現する．そして各
ノードへの適切な転送ファイル複製選択割当てを行った後，ノードごとに順序スケジューリ
ングを行うことで効率的なスケジューリングを表現する．
また，受信側 PC クラスタでは，本論文ではディスク容量の制限や他ジョブの影響がない
という仮定を利用し，単純にそれぞれのコネクションを通して送られたファイルがそれぞれ
の計算ノードのローカルディスクに対し衝突なく格納されるとする．本論文では，以降送信
元 PC クラスタにおける問題について考察する．
4.1 ネットワーク通信性能低下の回避
広域環境ではあえて通信帯域を抑えることで，パケットロスを抑制し安定的な通信を行う
ことができる．そこで，各ノードからの転送バンド幅を b と固定し，複数ノードがバンド
図 4 ファイル複製選択と転送順序スケジューリングの概要
Fig. 4 Overview of selecting replicas and file transfer scheduling.
幅 b で並列転送を行うことで PC クラスタ間広帯域ネットワークを有効に利用する．以下，
固定バンド幅 b の転送ストリームをコネクションと表す．さらに，PC クラスタ間のネット
ワークバンド幅を B としたとき，コネクション数 l を
合 N のコネクション集合 C への順序スケジューリングは独立タスクスケジューリングとす
b×l ≤B
ることができる．
が成り立つように定めることでネットワークに対し過剰なトラフィックを発生することを防
ぎ，同時にファイル転送を行うノード数を制御することができる．
4.3 モデル化のまとめ
前節までのモデル化をまとめると解くべき問題は以下のようになる．
前段落においてバンド幅 b でトラフィック制御された計算ノード間の転送ストリームをコ
(1)
ファイル集合 F とノード集合 N のファイル複製選択割当て問題
ネクションとして抽象化し，コネクションをノード集合へ割り当てることで各ノードからの
(2)
ノード集合 N のコネクション集合 C への独立順序スケジューリング
トラフィック制御や同時転送ノード数の制限を表現できることを考えてきた．一方，逆にコ
このスケジューリング（図 4）は並列ファイル転送の順序や転送ファイル複製を適切に選
ネクション集合に対してノード上のファイルを割り当てていくことでトラフィックの制御を
択にすることにより全体としての転送時間を短縮することを目的としている．ノード Nj に
行ったうえでの効率の良いファイル転送順序を表現することができるといえる．
割り当てられる各ファイル Fi の割合 xi,j を 0 ≤ xi,j ≤ 1（
m
j=1
xi,j = 1）とおく．また，
4.2 単一ディスクへのアクセス集中による性能低下の回避
あるノード Nj がコネクション Ck に割り当てられているかどうかを yj,k = {1, 0} で表す．
前節でファイル集合 F のコネクション集合 C に対する順序スケジューリングを求めるこ
このとき，各コネクション Ck によるファイル転送の転送時間 Tk はバンド幅 b を用いて以
とで解くべき問題を表現できることを述べた．しかし，このままでは同一ディスク上の複数
下に示す式 (1) で計算される．
のファイルが同時に複数のコネクションに割り当てられる可能性がある．
そこでファイル集合 F をコネクション集合 C へスケジューリングするのではなく，ノー
ド上のファイルをまとめノード単位にコネクション集合 C へスケジューリングする．ファ
イル集合 F からノード集合 N へのファイル割当ては，図 3 の 2 部グラフとしてモデル化
することができ，このグラフを用いて各ノードへ各ファイルのどの部分が割り当てられるか
を決定する．
j=1
コンピューティングシステム
Vol. 3
No. 3
113–125 (Sep. 2010)
1 yj,k × ×
(sizeof (Fi ) × xi,j )
b
n
(1)
i=1
さらに ( 2 ) の目的関数は式 (2) で示すように，すべてのコネクション Ck に対して最大の
ファイル転送時間 Tmax を最少とすることである．
M inimize
各ノードからのファイル転送は互いに影響を与えず，順序依存がないことから，ノード集
情報処理学会論文誌
Tk =
m
max (Tk )
k=1,···,l
(2)
c 2010 Information Processing Society of Japan
117
PC クラスタ間ファイル複製スケジューリング
5. アルゴリズム
に割り当て，リストスケジューリングにより各ノードをコネクションに割り当てた後，コネ
前章までに行った定式化に基づきアルゴリズムを設計する．提案アルゴリズムは全体とし
により転送ファイル複製の選択を実現する．
クション全体を見ながら総転送時間が短縮するよう転送ファイル複製の再割当てを行うこと
てのファイル転送時間が短くなるように適切な転送ファイルを選択する「転送ファイル複製
5.1.1 線形計画法による複製選択
選択アルゴリズム」，ノード集合 N からコネクション集合 C へのスケジューリングを求め
転送するファイル複製の選択問題を図 3 で示すグラフとしてモデル化する．図 3 におい
る「転送順序スケジューリングアルゴリズム」とそれらの結果からさらに実行時のファイル
て，各ファイルサイズを入力フローとし，すべてのノードへの割当てファイルサイズが平均
複製作成をスケジューリングする「実行時ファイル複製作成アルゴリズム」の 3 フェーズか
的になるよう，各枝に流れるフローサイズを線形計画法を用いて計算することで，各ノード
らなる．
へのファイル割当てを求める．
「転送ファイル複製選択アルゴリズム」と「転送順序スケジューリング」の概要を図 4 に
はじめにパラメータとしてファイル複製 Fi がノード Nj に存在するとき 1 となる
示す．図 4 中，Ni が PC クラスタの計算ノードを表し，Fj が各計算ノードが保持するファ
ei,j ∈ {0, 1} と入力フローとしてファイルサイズ fi （i ∈ F ）を与える．また，変数と
イル複製，Ck がコネクションを表している．
「転送ファイル複製選択アルゴリズム」により
してファイル集合 F からノード集合 N へのフロー f lowi,j （i ∈ F ，j ∈ N ）と最も割当て
各ノードが保持する既存のファイル複製 Fj のノード Ni への選択割当てを行い，その後「転
ファイルサイズの大きいノードのファイルサイズ max，最も割当てファイルサイズの小さ
送順序スケジューリング」によりノード Ni をコネクション Ck へスケジューリングする．
いノードのファイルサイズ min を用いる．目的関数と制約条件は次のようになる．
図 4 で示すように「転送ファイル複製選択アルゴリズム」と「転送順序スケジューリン
グ」により，既存の複数のファイル複製のうち転送するファイル複製が選択され，それらが
コネクションへ割当てスケジューリングされる形で転送順序が決定される．しかしながら，
Minimize
max − min
(3)
Subject to
特定のノードへ各ファイルの複製が偏って存在している場合など特定のコネクションからの
max ≥ 0
(4)
転送時間が偏って大きくなる可能性がある．これを解消するために「実行時ファイル複製作
min ≥ 0
(5)
成アルゴリズム」により，転送開始前にファイル複製の偏って配置されているノードからの
∀i ∈ F, j ∈ N. f lowi,j ≥ 0
(6)
送信元 PC クラスタ内計算ノードへファイルの一部または全部の複製作成をスケジューリン
∀i ∈ F.
(7)
グする．そして，ファイル転送実行時にこのスケジューリングに従い動的にファイル複製を
作成しながら外部へのファイル転送を行うことで負荷の分散を行い，全体として効率的な
(f lowi,j × ei,j ) = fi
j∈N
∀j ∈ N.
ファイル転送を実現する．
(f lowi,j × ei,j ) ≤ max
(8)
(f lowi,j × ei,j ) ≥ min
(9)
i∈F
∀j ∈ N.
5.1 ファイル複製選択アルゴリズム
5.2 節の転送順序スケジューリングを行う前に各ノードに割り当てる複製を選択・決定し
ておかなければならない．そこで線形計画法と貪欲法を用いた転送ファイル複製の選択アル
i∈F
目的関数式 (3) は割当てファイルサイズ最大のノードと最少のノードの割当てファイルサ
イズの差を最小とすることですべてのノードへ平均的にファイルを割り当てることを表して
ゴリズムについて述べる．
後述するリストスケジューリングでは特定ノードのみにほとんどのファイルが偏っている
いる．式 (4)，(5)，(6) はそれぞれ割当てファイルサイズの最大値，最小値と各枝のフロー
場合を除いて良い近似解が得られる．そこで線形計画法を用いるアルゴリズムでは各ノード
の下界として 0 を設定することでそれぞれを有効な値とするためのものである．式 (7) は流
に対し平均的に転送ファイル複製が割り当てられるように線形計画問題を解くことで解を求
量保存則であり，すべてのファイルがノード集合に割り当てられることを保証する．式 (8)，
める．一方，貪欲法によるアルゴリズムでは 1 度仮に初期状態として各ファイルを各ノード
(9) は各ノードの総割当てファイルサイズが最大で max，最少で min となることを示して
情報処理学会論文誌
コンピューティングシステム
Vol. 3
No. 3
113–125 (Sep. 2010)
c 2010 Information Processing Society of Japan
118
PC クラスタ間ファイル複製スケジューリング
いる．
以上の問題を解くことにより，ファイル集合 F からノード集合 N へのフロー f lowi,j と
して各ノードへの適切なファイル割当てを求めることができる．
5.1.2 貪欲法による複製選択
はじめにファイル複製のノード割当て初期状態を求める．これはファイル複製の出現状態
を記憶しながら，すべてのノードを探索し，あるファイル複製 Fi がノード Nj において初
めて出現したならばファイル Fi をノード Nj に割り当てることで実現する．このとき，当
然ながら特定のノードにファイル複製が偏って割り当てられている可能性がある．
図 5 ファイル複製アルゴリズムの基本モデル
Fig. 5 Basic model for replica creation algorithm.
次に初期状態において 5.2 節で述べるリストスケジューリングにより次のステップであ
る転送順序スケジューリングを行い，各ノードをコネクションへ割り当てる．この状態では
特定のファイルの偏るノードの影響で，ある一部のコネクションのみに負荷が偏っていると
らに転送時間を短縮するために転送ファイルが偏っているノードから，割当ての少ないノー
考えられる．以降，この負荷の偏るコネクション群からの転送時間を減らすために，これら
ドへのファイル複製作成をスケジューリングし，外部へのファイル転送中に送信元 PC クラ
に割り当てられているノード群からそれ以外のノード群へ複製の再割当てを全体として収
スタ内で転送ファイルの一部または全部のファイル複製を作成する．その後，作成した一部
束するまで行っていく．このとき，複製の再選択を Greedy に決定していくことで高速に，
または全部のファイル複製を元の転送ファイルと並列に転送することにより効率的なファイ
ある程度の近似解を得ることができる16) ．
ル転送を実現する．
5.2 転送順序スケジューリング
このとき，動的に作成した一部または全部の複製については基本的に転送処理実行時にお
コネクションに対し転送ノードをスケジューリングすることで転送順序スケジューリング
ける一時的なものとし，この実行時複製作成により作成されたファイルの一部分複製につい
を表現する．このとき，ファイル転送自体は互いに独立なことから，ノード集合からコネク
ては転送処理実行後には破棄されるものとする．完全な形でのファイル複製を転送処理実
ション集合への割当ては独立タスクスケジューリング問題
4)
とすることができ，これはリ
ストスケジューリング15) で効率的に解くことができる．
行後，転送ファイルの複製の 1 つとして扱うかについては本論文の範囲を超えるため割愛
する．
リストスケジューリングはタスク列 {ti |1 ≤ i ≤ q} とそれを処理するマシン集合
{Mj |1 ≤ j ≤ p} が与えられたとき，全タスクの処理時間が最短となるスケジューリン
5.3.1 複製作成アルゴリズムの基本モデル
基本的なモデルとして図 5 を示す．図 5 中，Ns ，Nd は PC クラスタの計算ノードを表
グを求めるアルゴリズムである．本研究ではタスク列がノード列，マシン集合がコネクショ
し，ノード Ns には転送ファイル複製が偏って割り当てられ，Nd は Ns ほど転送ファイル複
ン集合にあたる．手順としては，割当てファイルサイズの大きい順にソートされたノード列
製が割り当てられていないノードであるとする．このとき，Ns から Nd へファイルを複製
の先頭から順にノードを取り出し，その時点で予想転送終了時刻が最も早いコネクションへ
することを考える．簡単のために Ns へ割り当てられている転送ファイル群のファイルサイ
割当てを行っていく．タスクスケジューリング問題は NP 困難であるが，リストスケジュー
ズの和を Fs ，Nd へ割り当てられているファイル群のファイルサイズの和を Fd とする．ま
リングは計算量 O(q log q + q log p) で最適解から誤差
る8) ．
4
3
−
1
3p
の範囲の解を得ることができ
ラスタ間の通信のコネクションのバンドを幅 b とし，送信元クラスタ内のバンド幅を h × b
（h ≥ 1）とする．ここで，Fs (B)（= Fs − Fs (A)）の大きさだけ Ns から Nd へ複製を作
5.3 実行時複製作成アルゴリズム
前節までのアルゴリズムにより，ファイル転送時間を最短とするファイル複製の選択と
ノード集合のコネクション集合への割当ての近似解を得ることができる．これを利用し，さ
情報処理学会論文誌
た，クラスタ間の通信よりもクラスタ内の通信の方が高バンド幅であるという仮定から，ク
コンピューティングシステム
Vol. 3
No. 3
113–125 (Sep. 2010)
Fs (B)
と求められる．これを用いて複製作
h×b
Tcopy + Fsb(A) となる．また，Nd からの転送
成する場合，複製の作成に必要な時間は Tcopy =
成後の Ns からの転送時間を計算すると Ts =
c 2010 Information Processing Society of Japan
119
PC クラスタ間ファイル複製スケジューリング
1: if コネクションが一つしかない then
2:
return
3: end if
4:
5: loop
コピー元コネクション ← 最も転送時間のかかっているコネクション
コピー元候補ノード群 ← コピー元コネクションへ割り当てられているすべてのノード
8:
コピー先候補ノード群 ← すべてのコネクションから今までにコピー元にもコピー先にもなっ
ていないノードをすべて取り出す
9:
コピー先候補コネクション群 ← 8 の処理を行った後の状態でノード割り当てがないコネク
ション
10:
コピー元・コピー先ノード数 ← min(コピー元候補ノード群数 , コピー先候補ノード数 −
コピー先候補コネクション数 + 1)
6:
7:
図 6 実行時ファイル複製作成スケジューリング概要
Fig. 6 Scheduling overview of replica creation.
時間は Td = Tcopy +
Fs (B)+Fd
b
となる．
このとき，転送元クラスタ内での転送の方が外部への転送よりも高バンド幅なため，Ns
から直接外部へ転送するよりも，1 度 Nd へファイルをコピーしてから Ns ，Nd が並列に転
11:
送した方が効率的である．つまり，Ns から Nd へファイル複製を作成し，ちょうど Ns と
12:
Nd の割当てファイルサイズが等しいとき転送時間が最短となる（Ts = Td ）．また，このと
きの複製作成サイズは Fs (B) =
Fs −Fd
2
13:
14:
15:
となる．
コピー元ノード群 ← コピー元候補ノード群からコピー元・コピー先ノード数だけ選びだす
コピー先ノード群 ← コピー先候補ノード群からコピー元・コピー先ノード数だけ選びだす
コピー元・コピー先ノード群の間で基本モデルにより複製作成
16:
5.3.2 提案複製作成アルゴリズム
アルゴリズムの基本的な流れを図 6 に示す．図 6 中の Ck がコネクションを表し，Nj
が各コネクションへ割り当てられている PC クラスタの計算ノードを表している．5.2 節，
5.1 節のアルゴリズムの結果，コネクションには図 6（左）のような状態で割り当てられて
おり，特定のノードにファイルが偏ることから特定のコネクションからのファイル転送時間
が大きい．そこで複製作成アルゴリズムではすべてのコネクションに対し，コネクションに
割り当てられている各ノードからの複製を前節のモデルに従い順々に計算する．たとえば
図 6 において初めに図 6（左）の状態から最もファイル転送時間が大きいコネクション C1
17:
18:
コピー先コネクション ← コピー先候補コネクション群から一つ選択
コピー先ノード群をコピー先コネクションへ割り当てる
19:
20:
残りのノードをリストスケジューリング
21:
if すべてのコネクションへコピー先・コピー元となったノードが割り当てられている then
return
24:
end if
25: end loop
22:
23:
26:
に割り当てられているノード N1 から，ノード N3 へ基本モデルに従い複製を作成し，N3
図 7 複製作成のアルゴリズム
Fig. 7 Algorithm of replica creation.
を C3 へ割り当てることで図 6（中）の状態へ移行する．同様に N2 から N4 へ複製を作成
することにより図 6（右）の状態へ移行する．このように前項の基本モデルに基づき複製作
成を行っていくことにより順次転送時間を短縮していく．具体的なアルゴリズムは図 7 の
ノードが割り当てられている．このとき，すべてのノードに対して複製の転送を受け取るこ
ようになる．
とはたかだか 1 回となることが保証され，複製作成回数はたかだかノード個数分で済む．
このアルゴリズムが最後まで動作するために，アルゴリズムの開始時と終了時において各
コネクションには割当てファイルサイズ 0 のノードを含めつねに最低 1 個のノードが割り
6. 評
価
当てられているものとする．つまり，図 7 の行番号 5 のループ内処理開始時（行番号 6）と
6.1 評価モデル
ループ内処理終了時（行番号 23 または 25）の時点ですべてのコネクションには最低 1 個の
図 1 で示すように Site A の PC クラスタの各ノードに分散して配置されたファイル群を
情報処理学会論文誌
コンピューティングシステム
Vol. 3
No. 3
113–125 (Sep. 2010)
c 2010 Information Processing Society of Japan
120
PC クラスタ間ファイル複製スケジューリング
すべて Site B の PC クラスタの各ノードへ転送する場面を想定し，すべてのファイルの複
製を作成するのに要するファイル転送時間とスケジューリングの計算時間をシミュレーショ
ンにより評価する．このとき，Site A と Site B は高遅延，広帯域なネットワークで接続さ
れているとする．
線形計画法と貪欲法による複製選択と実行時複製作成アルゴリズムおよびシミュレータ
は C++言語で実装し，線形計画問題のソルバとしては GLPK（GNU Linear Program-
表 1 ファイルサイズとネットワークバンド幅設定
Table 1 Settings of file size and network bandwidth.
最大ファイルサイズ
平均ファイルサイズ
送信元クラスタ内バンド幅
PC クラスタ間バンド幅
トラフィックシェーピング後のバンド幅
基準となる送信元ディスク I/O
12.5 GB
6.25 GB
1 Gbps
10 Gbps
200 Mbps
400 Mbps
ming Kit）を用いた9) ．作成したシミュレータは以下のパラメータをとり，一様ランダムに
各ファイルサイズ，ノードに対するファイル配置を決定する．
Number of Files ファイルの数．
Number of Nodes 割り当てられるノードの数．
Number of Connections コネクションの数．
Max File Size ファイルサイズの最大値．
Repl ファイル複製の存在しやすさ．パラメータ 0 ≤ Repl ≤ 0.99 により，転送するファ
イル数が M 個のとき，あるファイルが N （> 1）個のノード上に存在する確率を
(1 − Repl)ReplN −1
(10)
として定義する．
Bias ファイルのノードに対する偏りやすさ．パラメータ 0 ≤ Bias ≤ 0.99 により，N 個
のノード中 n 番目のノードにファイルが存在する確率を
Bias(1 − Bias)n−1
1 − (1 − Bias)N
として定義する．また，Bias = 0 の場合一様ランダムに決定する．
(11)
図 8 各複製数あたりのファイル数
Fig. 8 Histogram of number of replications versus number of files.
ファイルの存在しやすさ Repl について，ReplN は N 個以上のノードにファイル複製が
外のパラメータについて表 1 のように設定し，Repl についてはファイル複製が少ない場合
存在する確率を示している．また，式 (10) は公比 Repl の等比数列を表している．これは
（Repl = 0.01）と複製が多い場合（Repl = 0.7），Bias についてはファイル配置の偏りが
複製を N ノード上に持つファイルの数は複製数 N に対して指数的に減少することを表して
小さい場合（Bias = 0.01）と偏りが大きい場合（Bias = 0.99）のパターンについて調べ
おり，Repl を小さくすればほとんどのファイルが複製を持たないことを，Repl を大きくす
た．ファイル複製数，ファイル配置はそれぞれ図 8，図 10 のようになっている．
れば複製を多く持つファイルが多くなることを表す．また，ファイルのノードに対する偏り
やすさ Bias について，式 (11) は初項
Bias
1−(1−Bias)M
，公比 (1 − Bias) の等比数列であり，
Repl と Bias の設定値についてはファイル配置が特定のノードに極度に偏っている場合
とすべてのノードに平滑化されている場合，または複製がほとんど存在しない場合と多く存
図 10 に示すように Bias を小さく設定することで初項が小さく，かつ公比が 1 に近くなる
在する場合のそれぞれについて極端なパターンの組合せ 4 パターンについて調査すること
ことからすべてのノードに対して均一なファイル配置となり，逆に大きく設定することで特
で，複製数とファイル配置の偏りがそれぞれ及ぼす影響の傾向をつかむことを目的としてい
定のノードに偏ったファイル配置となる．
る．Bias の設定については図 10 より十分に特定のノードへの偏っている場合とすべての
上記パラメータを変化させファイル転送所要時間に与える影響を調べる．ここで，それ以
情報処理学会論文誌
コンピューティングシステム
Vol. 3
No. 3
113–125 (Sep. 2010)
ノードへ平滑化されている場合が表せていると考えられる．
c 2010 Information Processing Society of Japan
121
PC クラスタ間ファイル複製スケジューリング
Fig. 9
図 9 Repl = 0.99 と Repl = 0.7 の複製数比較
Histogram of number of replication on Repl = 0.99 and Repl = 0.7.
図 10 各ノードへのファイル割当てとファイルの偏りの一例，複製数の関係．100 ノードに対し 1,000 個のファイ
ルをシミュレータにより割り当てる．すべての複製を含むためファイルの総和は 1,000 を超える
Fig. 10 Number of files which are allocated to each node. We allocated a set of 1,000 files to 100
nodes. However amount of all allocated files are over 1,000 because of file replications.
また，Repl については Repl = 0.01 とすることで各ファイルについてほぼ複製がない状
態を表現できていることが図 8 より分かる．しかし，Repl を大きすぎる値とした場合，た
とえば図 9 のように Repl = 0.99 とすると各ファイルについて複製が過剰に存在すること
になり，どの複製を選択しても簡単に近似解を作ることが可能となり，複製選択の最適化問
題として簡単に解くことができる問題となりすぎてしまうと考えられる．このことから，あ
表 2 マシンスペック
Table 2 Specification of evaluating machine.
CPU
memory
OS
Intel(R) Xeon(R) CPU 3060 2.40 GHz
6 GB
Linux 2.6.18-128.2.1.el5
えて複製が多いパターンについては複製数が多くなりすぎない半面，十分な複製数がある
Repl = 0.7 としている．
図 11，図 12，図 13，図 14 はそれぞれ，ファイルが特定のノードに偏って配置される
また，測定した計算機の性能は表 2 である．比較対象として，貪欲法により複製選択
場合と平均的に配置される場合，複製数が多い場合と少ない場合の組合せ 4 パターンの予想
を行う Greedy と線形計画法による LP に関して実行時複製作成を行う “Greedy repl” と
転送時間を示している．図 11，図 12，図 13，図 14 では直観的な分かりやすさのためファ
“LP repl”，実行時複製作成を行わない “Greedy” と “LP” を評価する．また，“Ideal” は
イル数から転送データ量を計算しこれを横軸としている．転送データ量についてはファイル
すべてのバンド幅を使いきれている理想的な状態を示す．
サイズの最大値を 12.5 GB とし，各ファイルのサイズを一様ランダムに決定することから，
6.2 ファイル数を変化させた場合
1 つのファイルのサイズの期待値が 6.25 GB と求まることによる．
表 1 の設定の下で，送信元 PC クラスタの計算ノード数を 100，コネクション数 50 とし
図 11 では貪欲法よりも線形計画法を用いた場合の方が良い結果を示している．これは貪
てファイル数を変化させ，予想される転送時間と計算時間を求めた．また，受信先 PC クラ
欲法を用いた場合，選択肢となるファイル複製が多いため，局所解に陥る可能性が高いため
スタの計算ノードは 4 章で設定したモデルを利用し，各コネクションと 1 対 1 で対応する
である．しかしながら，そのほかの場合では貪欲法，線形計画法どちらの場合も同程度の性
ために十分な数があることを仮定する．
能であった．特に，ファイル配置の偏りが少なく，まんべんなくファイルが配置されている
情報処理学会論文誌
コンピューティングシステム
Vol. 3
No. 3
113–125 (Sep. 2010)
c 2010 Information Processing Society of Japan
122
PC クラスタ間ファイル複製スケジューリング
図 11 ファイル偏りが大きく，複製数が多いときの転送データ量変化にともなう予想転送時間変化
Fig. 11 Amount of transfer data versus expected transfer time, in a case that the files which have
many replications are concentrated in a few nodes.
図 13 ファイル偏りが小さく，複製数が多いときの転送データ量変化にともなう予想転送時間変化
Fig. 13 Amount of transfer data versus expected transfer time, in a case that the files which have
many replications are distributed evenly amongst all nodes.
図 12 ファイル偏りが大きく，複製数が少ないときの転送データ量変化にともなう予想転送時間変化
Fig. 12 Amount of transfer data versus expected transfer time, in a case that the files which have
few replications are concentrated in a few nodes.
図 14 ファイル偏りが小さく，複製数が少ないときの転送データ量変化にともなう予想転送時間変化
Fig. 14 Amount of transfer data versus expected transfer time, in a case that the files which have
few replications are distributed evenly amongst all nodes.
情報処理学会論文誌
コンピューティングシステム
Vol. 3
No. 3
113–125 (Sep. 2010)
c 2010 Information Processing Society of Japan
123
PC クラスタ間ファイル複製スケジューリング
図 15 ファイル偏りが大きく，複製数が多いときのファイル数変化にともなう計算時間変化
Fig. 15 Number of files versus scheduling time, in a case that the files which have many
replications are concentrated in a few nodes.
図 16 ファイル偏りが大きく，複製数が多いときのノード数変化にともなう予想転送時間変化
Fig. 16 Number of nodes versus expected transfer time, in a case that the files which have many
replications are concentrated in a few nodes.
場合では貪欲法，線形計画法と Ideal の差がほとんどなく理想に近い結果であった．また，
せ予想転送時間を求めた．また，受信 PC クラスタの計算ノード数は 6.2 節と同様にコネ
図 11，図 12 のファイル配置の偏りがある場合では実行時複製作成作成により約 2 倍程度
クション数と同数以上を仮定している．図 16，図 17 はそれぞれファイル複製が多数あり，
転送時間が短縮されている．
ファイルが特定のノードに偏って配置されている場合と偏っていない場合である．複製が少
これは，表 1 で設定からクラスタ内ネットワークバンド幅が 1 Gbps あるもののディスク
I/O 速度が 400 Mbps であり，ディスクからディスクへのデータコピー速度は 400 Mbps で
ない場合は図 16，図 17 と同様の傾向であり割愛する．
まず，図 16 よりファイル配置の偏りが大きい場合，ファイル数を変化させた場合と同様，
抑えられる一方，クラスタ間通信ではトラフィック制御されたネットワーク速度 200 Mbps
貪欲法よりも線形計画法の方が良い性能であった．これは貪欲法では局所解に陥っているた
で抑えられていることによる速度差が原因である．これよりクラスタ間とクラスタ内での転
めである．次に図 17 よりファイル配置の偏りが小さい場合，ほぼ理想に近い性能を得てい
送速度の約 2 倍の差を利用し，複製を作成することでより効率的な転送が実現できている
る．どちらの場合でも，ノード数 50 までは転送時間が指数的に減少しているが，50 を境
といえる．
に一定になる．これはコネクションバンド幅を 200 Mbps 固定としているため 50 ノードか
また，図 15 はファイルが特定のノードに偏り，複製数が多い場合の計算時間を示してい
ら並列に転送した場合にクラスタ間のネットワーク 10 Gbps を使いきることができるため
る．計算時間に関してはすべてのパターンで貪欲法よりも線形計画法の方が計算時間が大き
であり，50 ノードまでは全ノードで並列転送可能だが，それ以上では同時転送ノード数 50
かった．しかし，データ転送時間が大きい場合においてはよりよく転送時間を短縮するスケ
で制限されるためである．特に図 17 の LP でノード数 60，110 で一時的に転送時間が増加
ジューリングを行う可能性がある線形計画法を用いても，計算時間に対して十分な効果が得
するのは，同時転送ノード数が 50 とされているためである．たとえば，50 ノードの場合
られる．
全ノードが並列に転送することができるが，60 ノードでは先に 50 ノードの転送が終了し
6.3 ノード数を変化させた場合
てから残りの 10 ノードの転送が行われるため，この 10 ノードがネックとなる．LP でこ
6.2 節と同様にファイル数を 1,000 として送信元 PC クラスタの計算ノード数を変化さ
の現象が起きるのは LP ではすべてのノードを平均的にするよう複製選択が行われる一方，
情報処理学会論文誌
コンピューティングシステム
Vol. 3
No. 3
113–125 (Sep. 2010)
c 2010 Information Processing Society of Japan
124
PC クラスタ間ファイル複製スケジューリング
築のための研究開発「e-サイエンス実現のためのシステム統合・連携ソフトウェアの研究開
発」，研究コミュニティ形成のための資源連携技術に関する研究（データ共有技術に関する
研究）による．
参
図 17 ファイル偏りが小さく，複製数が多いときのノード数変化にともなう予想転送時間変化
Fig. 17 Number of nodes versus expected transfer time, in a case that the files which have many
replications are distributed evenly amongst all nodes.
Greedy では全体を見ながら複製再割当てが行われるためである．
7. お わ り に
本論文では，広域環境において PC クラスタ間で複数ファイルの複製を効率的に作成する
手法について考察し，アルゴリズムの提案と評価を行った．効率的に PC クラスタ間広域並
列ファイル複製作成を行うためには，転送するファイル複製の選択と転送順序スケジューリ
ングを行う必要がある．このスケジューリングについて線形計画法または貪欲法とリストス
ケジューリングを用いる方法を提案した．また，クラスタ内外のネットワークバンド幅差が
あることを利用し転送処理実行時に複製を作成するアルゴリズムを提案した．
シミュレータによる評価の結果，ファイル複製の選択アルゴリズムは線形計画法，貪欲法
どちらの場合においても同等の転送時間短縮が行われており，特定の場合ではほぼ理想状態
に近い結果であった．しかし，線形計画法の計算時間の問題，貪欲法が苦手とするファイル
複製配置パターンなどの問題が明らかとなった．今後これらの改善を行っていく．また，実
行時に複製を作成することで効果的に転送時間を短縮することが可能であることが分かった．
謝辞 本研究の一部は，情報爆発時代に向けた新しい IT 基盤技術の研究，文部科学省科
考
文
献
1) Avian flu grid. http://avianflugrid.pragma-grid.net/
2) ILDG. http://ildg.sasr.edu.au/Plone
3) Allcock, W., Bresnahan, J., Kettimuthu, R. and Link, M.: The Globus Striped
GridFTP Framework and Server, Proc. SC ’05, pp.54–64 (2005).
4) Belkhale, K.P. and Banerjee, P.: An Approximate Algorithm for the Partitionable
Independent Task Scheduling Problem, Proc. ICPP, Vol.1, pp.72–75 (1990).
5) Borthakur, D.: HDFS Architecture. http://hadoop.apache.org/common/docs/
current/hdfs design.pdf
6) Donno, F. and Litmaath, M.: Data management in WLCG and EGEE, Worldwide
LHC Computing Grid, Technical Report CERN-IT-Note-2008-002, CERN, Geneva
(Feb. 2008).
7) Ghemawat, S., Gobioff, H. and Leung, S.: The Google file system, SIGOPS Oper.
Syst. Rev., Vol.37, No.5, pp.29–43 (2003).
8) Graham, R.L. and Grahamt, R.L.: Bounds on Multiprocessing Timing Anomalies,
SIAM Journal on Applied Mathematics, Vol.17, Issue 2, pp.416–429 (1969).
9) Makhorin, A.: GLPK (GNU linear programming kit). http://www.gnu.org/
software/glpk/glpk.html
10) Mandrichenko, I., Allcock, W. and Perelmutov, T.: GridFTP v2 protocol description.
11) Tatebe, O., Hiraga, K. and Soda, N.: Gfarm grid file system, New Generation
Computing, Ohmsha, Ltd. and Springer, Vol.28 (2010). (to appear)
12) Weigle, E. and Chien, A.A.: The Composite Endpoint Protocol (CEP): Scalable
endpoints for terabit flows, Proc. CCGRID’05, pp.1126–1134 (2005).
13) 建部修見，曽田哲之：広域分散ファイルシステム Gfarm v2 の実装と評価，情報処理
学会研究報告，2007-HPC-113, pp.7–12 (2007).
14) 高野了成，工藤知宏，児玉祐悦：精密な帯域共有とトラフィック隔離を実現するパケッ
トスケジューリング方式，情報処理学会研究報告，2009-HPC-119(9), pp.67–72 (2009).
15) 須田礼仁：ヘテロ並列計算環境のためのタスクスケジューリング手法のサーベイ，情
報処理学会論文誌コンピューティングシステム，Vol.47, No.18, pp.92–114 (2006).
16) 鈴木克典，建部修見：クラスタ間高速ファイル転送方式の提案と評価，情報処理学会
研究報告，2009-HPC-121(31), pp.1–8 (2009).
学研究費補助金「特定領域研究」
（課題番号 21013005）および文部科学省次世代 IT 基盤構
情報処理学会論文誌
コンピューティングシステム
Vol. 3
No. 3
113–125 (Sep. 2010)
c 2010 Information Processing Society of Japan
125
PC クラスタ間ファイル複製スケジューリング
(平成 22 年 1 月 26 日受付)
建部 修見（正会員）
(平成 22 年 6 月 11 日採録)
昭和 44 年生．平成 4 年東京大学理学部情報科学科卒業．平成 9 年同大
学大学院理学系研究科情報科学専攻博士課程修了．同年電子技術総合研究
鈴木 克典（学生会員）
所入所．平成 17 年独立行政法人産業技術総合研究所主任研究員．平成 18
昭和 61 年生．平成 21 年筑波大学第三学群情報学類卒業．現在，筑波
年筑波大学大学院システム情報工学研究科准教授．博士（理学）（東京大
大学大学院システム情報工学研究科コンピュータサイエンス専攻在学中．
学）．超高速計算システム，グリッドコンピューティング，並列分散シス
広域環境における大規模データ共有技術に関する研究に従事．
情報処理学会論文誌
コンピューティングシステム
Vol. 3
No. 3
113–125 (Sep. 2010)
テムソフトウェアの研究に従事．日本応用数理学会，ACM 各会員．
c 2010 Information Processing Society of Japan