DEIM Forum2014 D1-4

大規模環境における HDFS の
効率的なレプリカ再配置制御に向けた評価
日開 朝美†

竹房あつ子††

中田 秀基††

小口正人†† お茶の水女子大学 〒 112-8610 東京都文京区大塚 2-1-1†† 産業技術総合研究所 〒 305-8568 茨城県つくば市梅園 1-1-1
E-mail: †asami@ogl.is.ocha.ac.jp, ††{atsuko.takefusa,hide-nakada}@aist.go.jp, †††oguchi@computer.org
あらまし 大規模データに対応した処理システムとして，汎用なハードウェアを用いて高度な集約処理を行う分散ファ
イルシステムに注目が集まっている．分散ファイルシステムでは従来よりも大規模なシステムが構成されるようになり，複数のレプリカを分散配置することで可用性や耐故障性を維持している．ノードが故障すると，そのノードが管理していたレプリカが一時的に不足し，そのデータを保持している他のノードへのアクセス負荷が増加してシステム
全体の性能が低下するため，不足レプリカの再配置の高速化が重要である．しかしながら，一般に広く利用されている Hadoop Distributed File System(HDFS) のレプリカ再配置では，データ移動に偏りが生じており，効率良く処理されていない．この問題を解消するために，我々はリング構造に基づく一方向のデータ転送を行い負荷分散を行う制御手法を提案した．本稿では，この制御手法を 0-1 整数計画問題として定式化した最適化手法を提案し，7 台からなる
実クラスタを用いた小規模環境での評価とシミュレーションによる大規模環境での評価を行った．評価実験より，いずれの環境においても提案手法が有効であり，小規模実環境ではスループットが最大で 45%向上することを確認した．
キーワード 分散ファイルシステム，HDFS，レプリカ再配置，ノード削除

A Evaluation of Eﬀective Replica Reconstruction Schemes on a
Large-scale HDFS Environment
Asami HIGAI† , Atsuko TAKEFUSA†† , Hidemoto NAKADA†† , and Masato OGUCHI†† Ochanomizu University
2-1-1 Otsuka, Bunkyouku Tokyo 112-8610 JAPAN†† National Institute of Advanced Industrial Science and Technology (AIST) 1-1-1 Umezono, Tsukuba,
Ibaraki, 305-8568, Japan
E-mail: †asami@ogl.is.ocha.ac.jp, ††{atsuko.takefusa,hide-nakada}@aist.go.jp, †††oguchi@computer.org

1. は じ め に
近年，センサネットワークやソーシャルメディアなどから大負荷が増加して，システム全体の性能が低下する．そのため不足レプリカの再配置を高速に行い，データ処理システム全体の性能低下を防ぐことが重要である．

量のデータが生み出されるようになり，高エネルギー物理学，

オ ー プ ン ソ ー ス の 分 散 ファイ ル シ ス テ ム で は ，Apache

生命情報工学などの科学技術分野や商業分野において，大規模

Hadoop [2](以下 Hadoop) プロジェクトの Hadoop Distributed

データを効率良く管理，処理することが求められている．このFile System [3](以下 HDFS) が広く用いられている．しかしなような大規模データに対応した処理システムとして，汎用的ながら，HDFS のレプリカ再配置では，レプリカの生成元と生成

ハードウェアを用いて高度な集約処理を可能にする分散ファイ

先がランダムに選ばれるため，データ移動に偏りが生じて，効ルシステムが広く利用されている．分散ファイルシステムは，率良く処理が行われていない [1]．我々はこの問題を解消するた

データに対して複数のレプリカを生成し，大量のノードを用い

めに，リング構造に基づく一方向のデータ転送によって負荷分て分散管理することで可用性や耐故障性を維持している．ノー散を行うレプリカ再配置のスケジューリング制御手法を提案し，ドが故障すると，そのノードが管理していたレプリカが一時的

その有用性を示した [1]．

に不足し，そのデータを保持している他のノードへのアクセス

本稿では，これまで提案してきたレプリカ再配置のスケジュー—1—

リング制御を，0-1 整数計画問題として定式化した最適化手法を提案し，マシン 7 台からなる実クラスタを用いた小規模環境と，シミュレーションによる大規模環境における提案手法の有効性を評価する．評価実験より，小規模実環境において提案手法により最大で 45%スループットが向上することと，ヒューリ
スティック手法が最適化手法と同程度の性能を得られることを

x

x

star

n-ary spanning treex示す．また大規模シミュレーション環境においてノード数が増加した場合にも提案手法が有効であることを示す．

mul!-drop-chain: source

2. 関 連 研 究

x : switch

図 1 各ネットワークトポロジ

2. 1 レプリケーション手法

表 1 レプリカ再配置処理に関する変数のデフォルト値

分散ファイルシステムにおいて，データのレプリカをどのよ

変数
N work
N stream

うに管理するかというレプリケーション手法が数多く提案され

説明
NameNode の指示ブロック数の一変数
DataNode の同時転送ブロック数

デフォルト値
2
2ている．一般にデータを複製して，複数のレプリカを複数の異なるマシン上に保存することで，高いシステム性能や耐故障性，

3. 1 レプリカ再配置処理

信頼性を提供しているが，この時，レプリカ数とレプリカの配クラスタから DataNode が離脱すると，その DataNode で置場所が重要になってくる．

管理されていたデータの不足分を補うレプリカ再配置処理が行

ファイルクラスタリングに基づいて，アクセス時間やスト

われる．NameNode がレプリカ生成元と生成先の DataNode

レージ容量などの性能要件を満たし，レプリカの複製時間がを決定し，ブロック単位で処理される．NameNode が定期的最小になるようにレプリカの配置を決定する手法 [4] [5] [6] や，にレプリカ再配置の指示を生成元の DataNode に送信し，各ファイルの人気度に基づいて，レプリカ配置場所と複製数を決

DataNode は受け取った指示をもとに，生成先の DataNode へ定する手法 [7] など，アクセス時間やストレージ容量，複製時ブロックの転送を行う．生成先の DataNode はデータの複製が間を考慮したレプリカ配置手法は数多く提案されているものの，完了すると，生成元の DataNode に ACK を返し，さらにその複製処理自体が各ノードに与える負荷についてはあまり考慮さ

生成元の DataNode は NameNode に複製が完了したことを伝れていない．

える．不足したブロックの全てが複製されるまで，このフェー

2. 2 ネットワークトポロジ

ズが繰り返される．

Felix [8] らは大規模クラスタにおいて OS イメージを全てのこ の 時 NameNode が 生 成 元 の DataNode に 指 示 す る ブ

マシンに高速に分配する方法として，star 型，n-ary spanning

ロック 数 は ，ク ラ ス タ に 接 続 さ れ て い る DataNode 数 とtree 型，multi-drop-chain 型の 3 つの論理ネットワークトポロ

REPLICATION WORK MULTIPLIER PER ITERATION(N work とす

ジ (図 1) を取り上げ，調査している．評価実験から，star 型はる) の積で定義される．この値を超えてレプリカ再配置のスケノード数が増加すると，スイッチ部分で輻輳が発生してしまう．

ジューリングすることは出来ず，スケジューリングとデータ転n-ary spanning tree 型はネットワーク帯域の限界により複数の送が並行して行われる．DataNode が生成完了の ACK を受けストリームを効率良く処理できない．一方で multi-drop-chain

取らない状態のまま，レプリカ生成先の DataNode へ転送でき型は，他のトポロジと比較するとノード数やネットワーク帯

るブロック数は dfs.max-repl-stream(N stream とする) で域に大きく影響されることなく，データの転送が可能であり，定義される．REPLICATION WORK MULTIPLIER PER ITERATION

データの分配に適した方式であることが述べられている．

は，FSNamesystem.java の ReplicationMonitor クラスで定義

我々は，レプリカ再配置において multi-drop-chain 型と同様されている変数であり，dfs.max-repl-stream はプロパティの転送処理が行われるように，一方向のリング構造をベースとで変更可能な変数である．各変数のデフォルト値は表 1 のようしたスケジューリングを行う．

になっている．

3. HDFS におけるレプリカ再配置

4. レプリカ再配置の制御手法の提案

HDFS は Google の分散ファイルシステム GFS [9] に基づい

レプリカ再配置処理を効率良く行うには，適切にレプリカのて設計された分散ファイルシステムである．HDFS はマスタ・生成元と生成先を選択して各 DataNode の送受信処理を均衡

ワーカの構成をしており，ファイルのメタデータやクラスタ内

化することが必要である．そこで我々は，生成元が決定するとのノード管理を行う一台の NameNode と，実際にデータを格

生成先も一意に決定する一方向のリング構造に基づいてデータ納し処理を行う複数台の DataNode からなる．ファイルを最小転送を行いながら，各 DataNode の転送データ量を均衡化す単位であるブロックに分割し DataNode 間で各ブロックのレプるようなレプリカ再配置のスケジューリング方針を提案していリカを複数個分散して保存することで可用性や耐故障性を維持

る [1]．この方針をもとに，0-1 整数計画問題として定式化してしている．

最適化ソルバで求めた最適解を用いる手法 (以下，最適化手法)を提案する．

—2—

表 2 マシンスペック

4. 1 提案するスケジューリング方針の概要
提案するレプリカ再配置のスケジューリング方針を以下に述べる．全ノードが同一ラック上に存在するものとする．

OS
CPU
Main Memory
HDD
RAID Controller
Network

Linux 2.6.32-5-amd64 Debian GNU/Linux 6.0.4
Quad-Core Intel(R) Xeon(R) CPU@1.60GHz
2GB
73GB SAS×2(RAID0)
SAS5/iR
Gigabit Ethernet

1) DataNode を論理的にリング状に配置し，そのリング
表 3 実験に用いた各パラメータ構造に従って一方向にデータを転送する．

2) 各 DataNode が送信するデータ量を等しくするために，生成元に選出される回数を等しくする．

4. 2 最適化手法

レプリカ数

3

HDFS のデータ量 50GB×3(レプリカ数)
ブロックサイズ16,32,64,128,256MB

DataNode 数

6 台から 1 台削除

前述で提案したスケジューリング方針を 0-1 整数計画問題として定式化し，その解をレプリカ再配置のスケジューリングに用いる．定義する 0-1 整数計画問題では，レプリカ再配置に要する時間を短縮するために，各 DataNode の送信ブロック数の差を最小化することを目指す．
まず，記号の定義を与える．DataNode i の集合を D，レプ
リカ再配置が必要なブロック j の集合を B とする．DataN-

ode の総数を Ndn ，レプリカ再配置が必要なブロックの総数
を Nb ，レプリカ数を Nreplica (>=2) とすると，DataNode あ
たりの平均転送ブロック数 Navg は，Navg =Nb /Ndn となる．
現在のブロックの配置を行列 Currenti,j (i∈D, j∈B) とする．

Currenti,j の値は，DataNode i にブロック j が存在する場合
は 1，存在しない場合は 0 とする．また DataNode の隣接関係を行列 Adjf rom,to (f rom, to∈D) とする．Adjf rom,to の値はDataNode f rom から DataNode to への転送が可能な場合は
1，そうでない場合は 0 とする．レプリカ再配置のスケジュー
リング結果を格納する変数を Xf rom,to,j で表す．Xf rom,to,j の値は，DataNode f rom から DataNode to へブロック j の転送をする場合は 1，ない場合は 0 とする．各 DataNode i の転送ブロック数の差を最小化するために利用する変数を zi とする．この時，レプリカ再配置のスケジューリングは以下のように定式化される．
zi

(1)

i∈D

Alli,j = Currenti,j +X∀i ∈ D, ∀j ∈ BAlli,j <= 1, ∀i ∈ D, ∀j ∈ B
XAlli,j = Nreplica , ∀j ∈ B

(3)
(4)

Xf rom,to,j ∈ {0, 1}, ∀f rom, ∀to ∈ D, ∀j ∈ B
XXi,to,j >= 0, ∀i ∈ D, ∀j ∈ B
Currenti,j −ることを表す．式 (7) は，DataNode f rom と DataNode to が転送リングにおける生成元 DataNode と生成先 DataNode の関係にあることを表す．隣接関係がない DataNode 間の転送ブ
ロック数は 0 で，ある場合は正の値となる．M はある程度大きい値であり，ブロック総数を超えることはないので，ここでは M = Nb とする．式 (8)(9) は，各 DataNode が転送するブロック数とその平均値 Navg の差の下界と上界を表す．式 (10)は，zi は 0 以上の値をとることを表す．

5. 実クラスタを用いた小規模環境における評価
最適化手法を HDFS のレプリカ再配置モジュールに実装した．最適化ソルバには無償で提供されている GLPK [10] を用
いる．デフォルトの手法と最適化手法，そして [1] で既に提案している制御手法 (以下，ヒューリスティック手法) を用いて，ノード削除時のレプリカ再配置処理の性能を比較する．評価では，以下を調査する．

∀f rom, ∀to ∈ D

ローカルクラスタ上で Hadoop-1.0.3 をインストールしたマ
シン 7 台からなるクラスタを用いた．その内 1 台を NameNodeとし，残りの 6 台を DataNode とする．マシンのスペックは全て同一で表 2 に示す．全ノードが Gigabit Ethernet で接続された単一のラックからなる．

Xf rom,to,j <= M · Adjf rom,to∀f rom, ∀to ∈ D

5. 1 実 験 概 要

(6)

j∈B

Xf rom,to,j − Navg >= −zi ,

(2) 各 DataNode の転送ブロック数

(5)

to∈D

実験に用いたパラメータを表 3 に示す．レプリカ数を 3 とし，
(7)
(8)

j∈B

X

ブロックの生成元となる DataNode がそのブロックを持ってい

信処理の偏りを評価する．
(2)

i∈D

X

(5) は，Xf rom,to,j は 0 か 1 の値をとることを表す．式 (6) は，(2) の各 DataNode が転送するブロック数の調査では，送受Xf rom,i,j

f rom∈D

X

各ブロックのレプリカの総数が Nreplica になることを表す．式(1) 再配置のスループット
X

M inimize

Subject toに同じブロックが 2 つ以上配置されないことを表す．式 (4) は，各試行毎に HDFS に約 10GB のファイルを 5 つ put した．レプリカを含めた全データ量は約 150GB となっており，これはXf rom,to,j − Navg <= zi ,∀f rom, ∀to ∈ D

(9)

j∈B

zi >
= 0, ∀i ∈ D(10)

クラスタ全体の容量の約 25%に相当する．ファイルを put した後に，バランサーを起動し，各 DataNode が保持するデータ量を均一にした．そのため試行毎にデータ配置は異なるが，各上記を満たす，Xf rom,to,j を求めレプリカ再配置のスケジュー
リングに用いる．式 (1) は，各 DataNode の転送ブロック数の差を最小化するための目的関数を表す．式 (2) は，転送後の配置をAlli,j で表す．式 (3) は，転送後の配置において同じ DataNode

DataNode が保持するデータ量は同程度である．
各手法を用いて，ブロックサイズを 16〜256MB(デフォルト64MB) まで変化させ，1 台の DataNode 削除時のレプリカ再配置処理の性能を調査する．

—3—

200

180

180

160

160

throughput [MB/sec]

throughput [MB/sec]

200

140
120
100
80
60
40
20

140
120
100
80
60
40
20

0

0
16MB

32MB

64MB

128MB

256MB

16MB_2

block size
Default scheme
shcemeHeuris!c scheme

16MB_832MB_2

32MB_4block size and N_stream
Op!miza!on scheme

図 2 各手法におけるノード削除時のスループット

schemeDefault shceme

Heuris!c scheme

Op!miza!on scheme

図 3 N stream を 変 化 さ せ た 時 の ノ ー ド 削 除 時 の ス ル ー プット(16MB,32MB)
表 4 16MB,32MB に対する N stream の値

8

32MB

4

5. 2 実 験 結 果
5. 2. 1 再配置のスループット

500

500

各手法を用いて，ノード削除を行った時のスループットを図

throughput [MB/sec]

N stream

16MB

throughput [MB/sec]

ブロックサイズ

400
300
200
100

ブロックサイズである．図 2 より，ブロックサイズが 64MB 以

DataNode1

で 44%，最適化手法では最大で 45%向上していた．ヒューリス

200
100
0

0

フォルトの手法と比較するとヒューリスティック手法では最大30002 に示す．縦軸は再配置のスループット [MB/sec] で，横軸は上の場合は提案手法によりスループットが向上しており，デ

400

50

100

150

200

0

50

!me [sec]

図4

DataNode2

DataNode3

DataNode4100!me (sec)

150

200

DataNode5

各 DataNode(計 5 台) のディスク I/O のスループット (積み上げグラフ)

(左：デフォルト手法，右：ヒューリスティック手法)

ティック手法と最適化手法の再配置のスループットはほぼ等し
く，本実験環境においてヒューリスティック手法が十分有効であることが確認できた．
ブロックサイズ 16MB，32MB と小さい場合は，制御前後でスループットに変化がない．これは，ディスク帯域を全て使い切っておらず，処理に余力があるためである．3. 1 で述べたよ
うに，各 DataNode が ACK を受け取らない状態のまま転送出来るブロック数がデータ量ではなくブロック数 N stream で指定されているために，ブロックサイズが小さいと処理するデー
タ量も少なくなる．よって，DataNode では NameNode から指示されたレプリカ再配置処理が完了して，定期的に送られてくるレプリカ再配置の指示を待っている状態がデフォルト手法
時から既に生じていたからと考えられる．そこでブロックサイズ 16MB，32MB に対して，処理の負荷が大きい場合には提案手法が有効であるかを確認するために N stream の値を表4 に示す値に変化させて，ノード削除の実験を行った際の再配
置のスループットを図 3 に示す．縦軸は再配置のスループット[MB/sec] で，横軸はブロックサイズと N stream の値である．
図 3 より，N stream の値が大きい場合にはブロックサイズが小さくても制御手法によりスループットが向上することが確認できた．
またデフォルト手法とヒューリスティック手法を用いた際のディスク I/O のスループットの時系列データ (ブロックサイズ

64MB) を図 4 に示す．図 4 は縦軸がディスク I/O のスループッ

ト [MB/sec] で，横軸が時間 [sec] である．図 4 より，デフォル
ト手法では，ディスク I/O のスループットが不安定であるのに対し，ヒューリスティック手法では，比較的安定した高い値が
全 DataNode で維持されている

5. 2. 2 各 DataNode の転送ブロック数
デフォルト手法とヒューリスティック手法を用いた際のディ
スク I/O のスループットと受信ブロック数の時系列データ (ブロックサイズ 64MB) を図 5 に示す．図 5 は縦軸が受信ブロッ
ク数で，横軸が時間 [sec] である．図 5 より，デフォルト手法
では各 DataNode が受信しているブロック数には大きく差があるのに対し，ヒューリスティック手法では各 DataNode の受信
ブロック数が安定している．
また各手法を用いて，ノード削除を行った時の各 DataNodeが受信したブロック数とその偏差を表 5 に示す．ここではブロックサイズ 64MB のある 1 回の試行を取り上げている．デー
タ配置が試行毎に異なるため，受信ブロック数や偏差の値は各試行で若干異なり，各試行の偏差を平均すると表 6 になる．提案手法により各 DataNode が受信するブロック数が均衡化され，送受信処理の偏りが解消されていることが分かる．ヒュー
リスティック手法と最適化手法の受信ブロック数の結果はほぼ同じで，送受信処理の偏りという点からも，ヒューリスティッ
ク手法が有効であることが分かる．

—4—

4

2

6

4

2

0

0
0

50

100

150

50

100

150

200

!me (sec)!me [sec]
DataNode1

DataNode2

DataNode3

6

DataNode4

DataNode5

5
4
3
2
1
0

5
0

200

45
40
35
30
25
20
15
10
5
0

execuon me [sec]6

execuon me [sec]8
the number of blocks

the number of blocks

8

10

15

20

25

800

the number of nodes

1600

2400

3200

4000

the number of blocks

図 6 左：最適解の求解時間 (ブロック数固定，ノード数変化)
図 7 右：最適解の求解時間 (ブロック数変化，ノード数固定)

図 5 各 DataNode の受信ブロック数(左：デフォルト手法，右：ヒューリスティック手法)

6. 1. 2 実 験 結 果
表 5 ある 1 回の試行における各 DataNode の受信ブロック数とその偏差
ヒューリス
デフォルト手法 ティック手法 最適化手法

最適解の求解に要した時間を図 6，7 に示す．図 6 はブロック数固定でノード数を変化させた時の結果で，図 7 はノード数固定でブロック数を変化させた時の結果である．図 6，7 より，

DataNode1

78

78

78

求解時間はノード数の増加に伴い指数的に，そしてブロック数

DataNode2

79

79

79

の増加に伴い線形に増加していることが分かる．ノード数を d，DataNode3

84

78

79

DataNode4

85

79

79

ブロック数を b とすると，最適化手法の計算量は，O(d2 × b)

DataNode5

67

79

78

偏差

7.162

0.548

0.548

である．一方デフォルト手法とヒューリスティック手法の計算量は，O(b) である．最適化手法がスケールしない一方，ヒュー
リスティック手法は O(b) の計算量で最適化手法と同等の再配

表 6 各試行における各 DataNode の受信ブロック数の偏差の平均
ヒューリス
デフォルト手法 ティック手法 最適化手法
平均偏差

8.337

0.697

0.481

置スループットを達成することが可能であり，大規模環境においても非常に有効であることが示唆された．

6. 2 レプリカ再配置の実行時間
ヒューリスティック手法が最適化手法と同程度の性能を示す

表 7 ノード数とブロック数のパラメータ

ことと，大規模環境において最適化手法を用いることが非実

ノード数

ブロック数

用的であることから，大規模環境の評価では，提案手法として

ブロック数：固定
ノード数：変化

5〜25

800

ヒューリスティック手法を用いる．デフォルト手法とヒューリ

ブロック数：変化
ノード数：固定10800〜4000

スティック手法に対して大規模環境におけるレプリカ再配置の基本性能を把握するために，単一ラックにおいてノード数を変化させた場合のレプリカ再配置の実行時間をシミュレーションを用いて評価する．

6. シミュレーションによる大規模環境における評価
HDFS の実際の運用では，数十〜数千ノードを用いてラック

6. 2. 1 実 験 概 要
DataNode 数を 5〜30 台まで変化させて，レプリカ再配置の実行時間をシミュレーション環境を用いて評価する．評価にを構成して運用される．そこで大規模環境における提案手法のは，分散システムのシミュレータ SimGrid [11] を用いた．また有効性を検証するために，シミュレーションにより以下を調査

基本性能を把握するために単一のラック構成とする．評価に用する．

いるパラメータを表 8 に示す．DataNode 数はノード削除後の(1) 最適化手法の実用性

DataNode 数を示す．ブロック数は，5 節の実験においてレプ(2) レプリカ再配置の実行時間

リカ再配置時に各 DataNode が転送したデータ量に近い値とし6. 1 最適化手法の実用性て，DataNode 数に比例する値とした．ブロック一つあたりの一般に最適解の求解には時間がかかり実システムでは非実用

再配置にかかる時間は実環境の実験結果から 1.5sec とし，複数的であると言われているため，ノード数やブロック数を変化さの複製処理が共存する場合には CPU リソースは等しく割り当

せて最適化手法の実用性を評価する．

てられるものとする．

6. 1. 1 実 験 概 要

6. 2. 2 実 験 結 果

ノード数とブロック数を変化させて，最適解の求解にかかる

デフォルト手法とヒューリスティック手法を用いて，ノード数

時間をシミュレーションを用いて評価する．実験に用いたパラを変化させた際のレプリカ再配置の実行時間を図 8 に示す．図メータを表 7 に示す．ブロック数 800 個は，ブロックサイズを

8 は縦軸が実行時間 [sec] で，横軸が DataNode 数である．ひ

64MB とした時の表 3 のデータ量に相当する．

げは 95%信頼区間を表している．図 8 より，DataNode 数が増—5—

表 8 シミュレーションの各種パラメータ

DataNode 数

5, 10, 15, 20, 25, 30 台

ネットワーク帯域幅

1Gbps

ネットワーク遅延0.05msec

CPU 性能4.2GFLOPS

ブロックサイズ

64MB

ブロック数

80×DataNode 数

ᵏᵗᵎ

H[HFWLRQWLP H>VHF@

ᵏᵖᵓ
ᵏᵖᵎ
ᵏᵕᵓ
ᵏᵕᵎ
ᵏᵔᵓ
ᵏᵔᵎ
ᵏᵓᵓ
ᵏᵓᵎ
ᵓӨ

ᵏᵎӨ

ᵏᵓӨ

ἙἧỻἽἚ৖ඥ

図8

ᵐᵎӨ

ᵐᵓӨ

ᵑᵎӨ

ἤἷὊἼἋἘỵἕἁ৖ඥ

レプリカ再配置の実行時間

加した場合にも提案手法の方が再配置に要する時間が短く，有効であることが分かる．DataNode 数に関わらず実行時間はほぼ一定で，両手法ともスケールしていることが分かる．また信[2] Tom White, Hadoop: The deﬁnitive guide, trans. Ryuji
Tamagawa. O’Reilly JAPAN, 2010.
[3] Dhruba Borthakur. ”HDFS Architecture,” 2008 The
Apache Software Foundation.
[4] Rashedur M.Rahman, Ken Barker, Reda Alhajj, ”Studyof Diﬀerent Replica Placement and Maintenance Strategies
in Data Grid,” In Proceedings of the Seventh IEEE International Symposium on Cluster Computing and the Grid,
pp.171-178, 2007.
[5] Y. Wang and D. Kaeli, ”Load balancing using grid-based
peer-to-peer parallel I/O,” In Proceedings of IEEE International Conference on Cluster Computing, pp.1-10, 2005.
[6] Hitoshi Sato, Satoshi Matsuoka, and Toshio Endo, ”FileClustering Based Replication Algorithm in a Grid Environment,” In Proceedings of the 9th IEEE International Symposium on Computing and the Grid (CCGrid2009), pp.204211, Shanghai, China, May 2009.
[7] K. Sashi, Antony Selvadoss Thanamani, ”A New Replica
Creation and Placement Algorithm for Data Grid Environment,” International Conference on Data Storage and Data
Engineering, pp. 265-269, 2010.
[8] Felix Rauch, Christian Kurmann, Tomas M.Stricker, ”Partition Cast ― Modelling and Optimizing the Distributionof Large Data Sets in PC Clusters,” Euro-Par 2000, LNCS
1900, pp.1118-1131, 2000.
[9] Sanjay Ghemawat, Howard Gobioﬀ, and Shun-Tak Leung(October 2003), ”The Google File System,” 19th Symposium on Operating Systems Principles (conference), Lake
George, NY: The Association for Computing Machinery,
CiteSeerX: 10.1.1.125.789, retrieved 2012-07-12.
[10] GLPK. http://www.gnu.org/software/glpk/[11] SimGrid. http://simgrid.gforge.inria.fr/

頼区間に関して，デフォルト手法では若干の幅があるのに対して，ヒューリスティック手法では非常に小さいことから，デー
タ配置に関わらず安定して効率良く処理することができると考えられる．以上より単一ラックにおいては，DataNode 数の増加に関わらず，ヒューリスティック手法が有効であることが分かった．

7. ま と め
HDFS において効率良くレプリカ再配置を行うために，リング構造に基づく一方向のデータ転送を行い，各ノードの負荷を均衡化するスケジューリング方針をもとにした最適化手法を実装し，ヒューリスティック手法とともに単一ラック環境において評価した．評価実験から実クラスタを用いた小規模環境においては，提案手法により各 DataNode の負荷が均衡化し，スループットが最大で 45%向上することと，ヒューリスティッ
ク手法が最適化手法と同程度の性能が得られることを示した．
シミュレーションによる大規模環境においては，最適化手法はDataNode 数が増加すると非実用的であるが，ヒューリスティッ
ク手法は DataNode 数やデータ配置に関わらず有効であることが分かった．
今後の課題は，複数のラックが存在する場合において，各手法の基本性能や有効性を検証することである．
文

献[1] 日 開 朝 美 ，竹 房 あ つ 子 ，中 田 秀 基 ，小 口 正 人 ，”Hadoopの ノ ー ド 削 除 時 の レ プ リ カ 生 成 の 高 速 化 手 法 の 提 案”
Multime-dia, Distributed, Cooperative, and Mobile Symposium(DICOMO2013), 7H-2, July 2013.

—6—