DEIM Forum 2017 H5-1

システム規模を伸縮させる HDFS におけるデータ移行中のリクエスト応答調整杉山翔一郎†

レーヒェウハン†横田 治夫†† 東京工業大学 〒 152-8550 東京都目黒区大岡山 2-12-1
E-mail: †{sugiyama,hanhlh}@de.cs.titech.ac.jp, ††yokota@cs.titech.ac.jp
あらまし

近年情報の蓄積・収集技術の発展により多くの情報がデータとして蓄積され、利用されている。膨大なデータを高速かつ省電力に処理するための方法の一つとして複数のノードにデータを複製して持たせ、稼働ノード数をワークロードに応じて変化させる分散ファイルストレージが研究されている。データの一貫性の為に、システムの伸縮の際には停止していたノードのデータを最新のものにするためのデータの移行が必要であり、現在提案されている方法ではこの間に当該ノードへのリクエストが待ち状態になってしまうという問題がある。そこで本研究では、この分野で広く使われている HDFS に着目し、メタデータにデータの状態を表す情報を持たせ、その情報をもとに移行中も最新のデータをもつノードへアクセスするように制御する仕組みと、移行完了までの時間とリクエスト応答のバランスを調整する方法を提案し、メタデータ管理コストを見積もり考察する。
キーワード ストレージ, HDFS, 分散インデックス, ギアシフティング

1. は じ め にビックデータに代表される近年の巨大な情報の利用はますます求められており、それらの処理には Hadoop のような分散処理環境が適している。分散処理環境とは、処理対象のデータを複数の計算能力をもつノードに分散させ、それらを並列に動作させることにより処理能力を上げる方法である。

Hadoop 等の分散処理環境によりスループット向上や応答時間短縮を望めるが、複数ノードが常に稼働している状態になるため当然消費電力も大きくなる。実際に Hadoop などで処理されるワークロードの大きさは図 1 のように一定ではなく、ここで

図 1 Facebook のワークロードトレース [1]必要な性能を 1 分毎にトレースしたもの問題となることはワークロードが小さいときでもシステムが必要以上の性能を提供し余分に電力を消費することである。

Accordion 上でギアアップ要求からデータの移行が終わりギア

そこで、分散ファイルシステムとしてワークロードの大きさにアップが完了するまでの間もリクエスト応答できるような仕組応じてギアシフティングと呼ばれるシステムの規模を伸縮させみを提案し、ギアアップ時間とリクエスト応答の調整を行う。

る仕組みを持つストレージが研究されている [2] [3]。それら方本論文では、2. 章で、本研究で着目する分散ファイルストレー法では異なるギアのデータノードにデータの複製を持たせ、必ジシステムにおけるギアシフティングについて説明する。3. 章

要なとき、つまりワークロードが大きいときには高ギアのノーでは、ギアシフトにとって重要な要素であるメタデータ管理とドを稼働させ並列度をあげ、ワークロードが小さい時には高ギデータ配置の研究についての研究を紹介する。続く 4. 章では、アのノードは停止させることによって消費電力を抑える事がで関連研究での課題を提示して研究の動機を説明し、5. 章で提案

きる (図 2)。

手法を述べる。6. 章では、提案手法で新たに発生するメタデーデータを複製するため、処理が行われると処理されたデータタ管理コストの見積もりを行い考察を行う。最後に 7. 章でまとの複製との一貫性を保つために必要なノードには変更のあっためと今後の課題を述べる。

データを移行をさせる必要がある。この移行はギアアップする際に必要であり時間を要する。この移行時間を短縮するために

2. ギアシフティング方式

効率的な移行を実現するメタデータ管理法 NDCoupling [4] や

2. 1 データの配置とギアシフト

データ配置メソッド Accordion [5] が提案されているが、これ

ギアシフティング方式の分散ファイルストレージではデータまで提案されている方式ではデータ移行中のリクエスト応答をを複製して複数のノードに持たせ、ワークロードの大きさに応停止させている。

じて稼働ノード数を変化させることによりシステムの規模を伸そこで本研究では、データ移行中のリクエスト応答を考慮し、縮する。ギア 1 で動作するノードを Group1 のノード、ギア n

図2

ギアシフティング方式

図 4 HDFS アーキテクチャとデータフロー

3. 関 連 研 究
本章では効率的なギアアップ処理の観点から、Hadoop 用ギ
図 3 ギアシフティング HDFS

アシフティングシステムにおいて重要なメタデータ管理とデータ配置についての関連研究について説明する。

で新たに動作するノードを Groupn とする。例えば、図 3 で

3. 1 メタデータ管理示したような四つのノードがあり 2 段階のギアのシステムを

3. 1. 1 NDCoupling

想定した場合、ギア 1 では Group1 のノード二つ、ギア 2 で一般的な HDFS は図 4 のように NameNode と呼ばれるノー

は Group1 + Group2 の四つのノードが動作するといった方式

ドが一つ存在し、リクエストはまず NameNode にアクセスすが考えられる。ギア 1 で動作する際に Group1 のノードですべる。その後、DataNode と呼ばれるデータを分散させているてのデータを処理できなくてはならないので、それらのノードノード群の中から対応するノードに処理を受け渡す。その他、内でデータを分散させる必要がある。Group2 移行のノードにメタデータの管理やデータ配置、ブロックマッピングなどを一は Group1 のノード内のデータの複製 (またはその一部) を持括して NameNode が受け持つのでギアアップ時は特に大きなたせる。例では、Group1 のノードのデータの半数を Group2負荷がかかる。のノードに複製することで 4 並列で処理を行うことができる。

一方 NDCoupling [4] という手法を用いた HDFS では図 5 のよ

ギア 1 でシステムが動作しているときは Node3 と Node4 は停

うに、すべての DataNode に NameNode の仕事を分散させる。

止しており、処理能力は小さくなっているが消費電力も小さく各ノードのメタデータ管理モジュールやブロックマッピングはなっている。大きな処理能力が必要なワークロード以外ではギ自分のノードのメタデータとブロックを管理すればよい。リク

ア 1 での処理能力で十分だとすると、常に四つのノードで動いエストは最初ランダムに選ばれたノードへ行き、その後分散さているシステムと比べて消費電力を抑えることができる。

れたメタデータ管理モジュールが Fat-Btree [6] の構造を用いた

2. 2 ギアアップ処理に要する時間

メタデータ管理を利用して対応するノードへ渡される。処理さ低ギアで動作しているときにリクエスト処理が行われるとれたデータは最初にアクセスしたノードを経由しクライアントノードのデータに書き込みが発生することがある。この時、書に返される。この手法によってデータと対応するメタデータなき込みがあったノードのデータと停止している高グループのどをノードごとに管理することができるようになり、ギアアッノードの対応する複製の間にデータの相違が発生する。例えばプの際のデータの移行をスムーズに行うことが可能になった。

図 3 で B1 が P1 の複製であったとする。この時ギア 1 で動作

3. 2 データ配置している P1 に write が発生して P1’ に変わると、P1’ ≠ B1 に3. 2. 1 Rabbit,Sierraなってしまうため、ギアアップした際に Node3 の B1 は最新の分散ファイルストレージにギアシフティング方式を採用したデータではないため使うことができない。そこでギアアップの研究の先駆けとなったものが Rabbit [2] と Sierra [3] である。両際には B1 に P1 にあった変更を反映させるためのデータの移者とも NameNode 一つの一般的な HDFS で実装されている。

行が必要になる。この移行がギアアップ処理にかかる時間に起Rabbit では主に Read の性能を上げることを目的として equall-因する。データの移行のためにはシステムのメタデータ管理とwork data-layout policy という各ノードが同程度の量の仕事をデータ配置が重要である。

受け持たせることを考慮した配置メソッドを提案している。図6 のように、policy を達成する計算式に基づいてギア 1 で動くノード上にある primary data の複製を高ギアで動くノードに持たせる。

図 5 NDCouplingHDFS アーキテクチャとデータフロー

図 8 3 ギア構成の Accordion データ配置の例

ブロック単位で低ギアのノードに複製していく配置方法により、データをブロックで扱えるようになり、ブロックごとに移行やメタデータの管理をすることができる。結果としてギアアップ時のデータ移行量が小さくなり、効率的なデータ移行を実現する。
図 6 3 ギア構成の Rabbit データ配置の例

4. 研 究 動 機関連研究ではギアアップ中のリクエストをブロックして、データの移行を行っている。つまり性能を上げたい状況でギアアップ要請を出したのにも関わらず、しばらくの間はリクエスト応答が止まってしまう。リクエストを停止させずにギアアップを行うには、アクセス分散の方法やメタデータ管理コストの抑制、ギアアップ時間とリクエスト応答性能のバランス調整などの課題がある。

5. 提 案 手 法
図 7 3 ギア構成の Sierra データ配置の例

後に続く Sierra では Rabbit でギア 1 のノードに集中していたwrite の処理の負荷を各ノードに分散させる方式などを取り入れ、さらに図 7 のように、同ギアのノードの持つデータのブロックサイズを同じにすることによってノード数の制約を緩和した。
両者ともデータの移行を考慮したデータ配置メソッドではないため、ギアアップ時のデータ移行量が大きく、データ移行は効率的に行うことができない。

3. 2. 2 Accordion
Accordion [5] では、Rabbit や Sierra とは異なる新たなデータ配置メソッドを提案しギアアップの際の効率的なデータ移行などを実現した。続く論文 [7] で NDCoupling と組み合わせたシステムを提案している。このデータ配置メソッドは図 8 のよ
うに、全てのノードに primary data を分割して持たせ、分割

本研究では、以下の二つを目標とする。

•

ギアアップ中のリクエスト応答を可能とする方法の提案•

ギアアップ中のリクエスト応答の課題の解決

5. 1 提案手法のアプローチ
5. 1. 1 ギアアップ中のアクセス先ノードの選択
2. 2 節で述べたことが原因で、システムがギアアップ要請後に求められる性能を発揮するのには時間がかかる。データの移行が完了するまでは止まっていたノードにあるデータが最新のものである保証がないため、アクセスすることは認められない。
しかしながら、Accordion の分散されたメタデータを管理する構造を利用して、データごとにデータが最新かどうかわかるようなステータスを持たせることでギアアップが完了する前に可能なデータから逐次高ギアのノードへアクセスできるような制御が可能である。
ギアアップの際、データの移行前や移行途中のデータの状態に5. 1. 2 データ移行の必要な量に応じて packing する量を制御

3. 2. 2 節で述べたように、Accordion ではデータの移行の際に packing というバッチ処理を行っている。packing を行うとデータ移行が高速になるが、packing 移行中の当該ノードのリクエスト応答はできない。
ギアアップ処理にかかる時間が多少増えても、ギアアップの要請から逐次性能を上げていくべきか、それとも少しの間リクエスト応答が止まってもギアアップ処理時間を最短にすべきかは検証すべき問題である。

5. 1. 1 節の手法を適用した際に当該ノードのリクエスト応答は
図 10 のようになると考えられる。ある packing サイズごとに分割した packing をすることによって、段階的にデータの移行を完了させることができ、リクエスト処理を徐々改善しつつ、
図 9 ギアアップ中のアクセス先ノードの制御

すべて packing せずに移行するよりもギアアップにかかる時間を減らすことができると考える。本研究ではデータの移行の量などに応じて最適な packing サイズを検証し、選択することでシステムの利用者にとって使いやすいように調整する。

5. 2 提案手法の実装方法
提案手法の実現方法の手順について図 11 を用いて説明する。

Step 1：更新のあるメタデータの移行
データの書き込みがあったときには各ノードのログファイルに記録される。ギアアップの際はまず、稼働しているノード（Node i）がログファイルをチェックし、各ノードのメタデータマネジメントモジュールが変更のあったメタデータのみ移行する。例では a’ に対応するメタデータ m a’ が Node j に移行される。

Step 2：データブロック移行のコマンド発行
次に、ログファイルからメタデータマネジメントモジュールが書き込みのあったブロックを検索する。その後、各ノードの
図 10 packing の効果のイメージ

ストレージマネジメントモジュールのキューにデータブロックと移行先ノードの組が挿入されるという形で移行のコマンドよりアクセスすべきノードが異なる。図 9 のデータ a の様にが発行される。ストレージマネジメントモジュールは設定され書き込みによるデータの変更があり、移行がまだ済んでいない

た heartbeat-interval でキューからコマンドを受け取る。コマ

データは Groupg+1 の Node j にはまだ最新のデータがないのンドの発行には、上述のファイルの検索とコマンドの発行をで移行元である Groupg のノード Node i にアクセスしなけれそれぞれの移行ブロックについて繰り返す sequential issuanceばならない。一方データ b の様に書き込みがあったとしてもmethod と、書き込みのあったブロックと移行先ノードの検索移行が済んでいるとわかれば、Node i にも Node j にも最新のを先にすべて行い、まとめてキューに入れる batch issuance

データがあることがわかるのでどちらにもアクセス可能である

method の二つの方法があるが、本研究では両者の間でバッチが、並列度を上げるために高ギアグループのノード Node j にサイズを変えながら移行中もリクエストを停止させず受け付け、アクセスするのが望ましい。また、書き込みのないデータ c にリクエスト応答の調整を行う。

関してもデータ b 同様の事が言える。このように、••書き込みによる変更があったかどうか書き込みによる変更があった場合、移行が済んでいるかどうかという状態がわかれば、上記のようなアクセス先の選択が可能である。本研究では分散されたメタデータにこれらの状態を記録し、参照することでこれを実現する。

Step 3：対応するメタデータに移行ステータスを付与
移行するデータブロックの対応するメタデータに移行が未完了であることを示すステータスを付与する。

Step 4：書き込みにあったブロックの移行
ストレージマネジメントモジュールがコマンドを受け取ると、データブロックを指定されたノードに送る。

Step 5；移行が済んだブロックのメタデータ更新
データブロックの移行が完了したら Step3 で付与したステータスを移行未完了から移行完了に更新する。

提案手法を実現した場合、ギアアップの際にデータの移行が完了したデータのメタデータを書き換えるコストが発生する。
ここではそのコストを見積もる。Rabbit にはノード設定に制約があるため、Sierra を比較に用いる。リクエストの伝達コストについては、メタデータを参照し対応するノードへ伝達がいくという仕組み自体は従来手法と変わらないため、提案手法により新たに発生しないと推測する。
比較はノード構成を変更した場合とギアを変更した場合で行い、メタデータ管理法とデータ配置の効果を確認する。
まず前提を以下の通りに設定する。
（ 1 ） 1 ブロックは 1 ファイルに対応し、対応するメタデータを一つ持つ（ 2 ） 書き込みリクエストにより変更されるのは内容のみでファイル名は不変（ 3 ） 書き込みは全アクティブノードに平均的にまたがって発生する（ 4 ） Sierra にはリクエストに関して、リクエストのあったデータブロックの最新の値を持つ最高ギアのノードを NameN-

ode により一括管理されたメタデータより特定し、リクエストが送られるという形で提案手法を適用する。
図 11 NDCouplingHDFS のデータ移行処理

変数は以下の通り•
Step 6：更新されたデータに関するメタデータの反映
データの移行によるデータの更新に伴い移行先のノードのメタデータも必要であれば更新する。

CU A ：ギア g →g + 1 の時の Accordion のメタデータ

アップデートコスト•CU S ：ギア g →g + 1 の時の Sierra のメタデータアップ

デートコストStep 7：ギアアップ完了後追加したステータスをリセット•

B ：全ブロック数

ギアアップ完了後は追加したステータスを用いない従来の方•

BU ：アップデートブロック数•N ：全ノード数法でアクセス分散を行うため、ステータスをリセットする。

•Ng ：ギア g − 1 →g で増えるノード数

メタデータに新たに追加された上述のステータスを用いて•G：システムのギア数

5. 1. 1 節のようにアクセス先のノードを決定することにより実•H ：一つのギアでの稼働時間 (h)•CT ：メタデータ更新コスト現する。
提案手法によりギアアップ中にリクエストを停止させないこ

このとき Sierra でのメタデータアップデートコストは、全てとのメリットとして、ギアアップ中のリクエスト応答が可能にのブロックを複製する必要があり、一つの NameNode がすべなり性能を徐々に上げることができるという点がある。一方デてのメタデータを管理するので、メリットとして、上述で付与したメタデータ管理コストが発生するということが挙げられる。HDFS におけるギアアップ時

CU S = BU × CT(1)の NameNode の負荷は、リクエストを停止する場合は移行処である。一方、分散した NameNode でメタデータを管理して理だけだが、停止しない場合はそれにメタデータ管理が加わる

いる NDCouplingHDFS では、仮定より書き込みは平均的に全ためこのコストを見積もる必要がある。次章で一般的な HDFSアクティブノードに分散しているため、各 NameNode でメタと Rabbit や Sierra のデータ配置で実現する場合のコストとデータの更新を分割できる。さらに Accordion のデータ配置

NDCouplingHDFS と Accordion のデータ配置で実現する場合

により、書き換えの必要なメタデータも Sierra よりも少ない。のコストを見積もり、メタデータ管理とデータ配置の効果を比よって g から g+1 にギアアップするとき以下のようになると較する。実際の実装や実験は現在進行中である。

見積もることができる。

6. コストの見積もり
本章では 5. 1. 1 節のステータス管理のコストを見積もり、NDCoupling を用いた HDFS+Accordion で実現した場合と、一般的な HDFS+Rabbit や Sierra で実現した場合で比較する。

CU A =BU
N×∑Gg+1Ng

Ng× CT(2)

リクエスト応答により、1 時間で 1%のデータが書き換えられると仮定すると、H 時間で更新が必要になるブロック数はBU = B × (1 − (99 H) )100(3)

N G ノード構成

N G ノード構成

62 N1 = 2, N2 = 41818

2 N1 = 2, N2 = 16100

2 N1 = 2, N2 = 98

5 N1 = 2, N2 = 4, N3 = 4, N4 = 4,N5 = 4
表 2 全ノード数 18、5 ギアの構成

表 1 全ノード数の異なる 2 ギアの構成

図 15 一日稼働した表 6. 2 のシステムにおけるギアアップ
図 12 一日稼働した表 6. 1 のシステムにおけるギアアップ

図 16 一週間稼働した表 6. 2 のシステムにおけるギアアップ
図 13 一週間稼働した表 6. 1 のシステムにおけるギアアップ

図 14 N=6 と N=100 の場合の Accordion データ配置
図 17 Accordion における各ギアアップでのデータ移行量となる。以下の見積もりでは B = 1000 と仮定する。

6. 1 ノード構成を変更した場合の見積もり

ギアアップでのコストを比較する。

ギア数を 2 で、全ノード数を表 6. 1 に示す設定の構成でのコ結果が図 15,16 のようになったのは Accordion による効果が大ストを比較する。

きいと考えられる。Accordion のデータ配置により、特に高ギ結果が図 12,13 のようになったのは NDCoupling による効果

アでのギアアップでデータ移行量の削減がされコストを削減しが大きいと考えられる。ノード数が増えると Accordion でも図ている。図 17 のように、ギアが上がるにつれてデータ移行の14 のようにデータ移行量は大きくなる。しかしながら NDCou-量が減っていくため、メタデータ管理の量も減っていく。

pling の分散メタデータ管理によって、少なくとも N1g までコ6. 3 考ストを削減することを保証する。

図 12-13、15-16 を見ると、Accordion のデータ配置メソッド

察

6. 2 ギアを変更した場合の見積もりによるデータ移行量の削減と、NDCoupling によるメタデータ

表 6. 2 で示した 5 ギア構成のシステムにおける各ギアからの管理の分散化によって Sierra に比べてすべての場合でメタデータ更新コストが小さくなることがわかる。見積もり 6. 1 のよう実的なワークロードで見積もった packing サイズに動的に変化なギア 1 でのギアアップを想定する場合には、メタデータ更新させながら実験を行い、ギアアップ中のスループットや応答時を分散するノード数が常に二つなので、コストは Sierra に比間、ギアアップ時間の測定を行う必要がある。

べてノード数 6 の場合の 67%削減でき、全ノード数が多くなっても少なくとも 50%削減を保証する。見積もり 6. 2 では、特に Accordion によるデータ移行量の削減の効果が見られ、ギア4 でのギアアップで 94.4%のコスト削減を見積もることができ謝

辞本研究の一部は, 日本学術振興会科学研究費補助金基盤研究(A)(#25240014) の助成により行われた. ここに謝意を表す.

た。このことからより大きなシステムの高ギアでのギアアップで提案手法がさらに効果を発揮することが期待できる。

7. お わ り に
7. 1 ま と め
本研究ではギアシフティングする HDFS における、ギアアップ中のリクエスト応答を可能にする手法として，データの移行状態をメタデータとして管理し、その状態によってデータのアクセス先のノードを選択する方法を提案し、新たに発生するメタデータ管理コストを見積もった。
見積もりによって、Accordion の NDCoupling を用いた HDFSで実装した場合と Sierra の一般的な HDFS で実装した場合に、NDCoupling によるメタデータ管理の負荷分散と、Accordionによるデータ移行量の削減によって設定した構成で Accordion
が Sierra に比べ最大 94.4%のコスト削減が可能であると見積もることができた。

7. 2 今後の課題
7. 2. 1 packing サイズの調整
Accordion では、データ移行の際に移行時間を短縮するため、移行の必要なデータを packing してまとめて移行する方法をとっていた。この方法では移行中のリクエスト応答は止まってしまうというトレードオフがある。上述の手法でデータをpacking せずリクエスト処理しながら移行を行う方法を提案したが、packing をする場合と比べてデータ移行にかかる時間は増える。
そこで、提案手法を実装したシステムでデータの移行を packingサイズを変えて行うことにより、データ移行時間と移行中のリクエスト応答を提案手法と従来手法の間で調整することを提案した。これについ実際に検証する必要がある。

7. 2. 2 提案手法の実装の完成
現在提案手法を Accordion 上に実装中である。6. 章の見積
もりでは、システムの規模が大きくなるにつれコストの差で大きな効果が期待できると推測したが、実際に測定する必要がある。また、ギアアップ中のスループットや応答時間、ギアアップ時間などを測定し、5. 1. 1 節や 5. 1. 2 節の手法の効果を検証する必要がある。

7. 2. 3 提案手法の実験
提案手法について実験を行い、効果を検証する必要がある。

5. 1. 2 節で述べた手法で、データ移行量などに応じて動的にpacking サイズを切り替えて最適なデータ移行を可能にするため、packing サイズを変えながら実験でデータの移行量などに応じた最適な packing サイズを見積もり、時間的に変化する現文

献[1] L. Xu, J. Cipar, E. Krevat, A. Tumanov, N. Gupta, M.
A. Kozuch and G. R. Ganger, Slide of ”SpringFS: Bridging
Agility and Performance in Elastic Distributed Storage”,
Proc. of the 12th USENIX FAST,2014, pp. 243-255.
[2] A.Hrishikesh, C.Hames, G.Varun, G.R.Ganger, .Michael A.,and S.Karsten, Robust and flexible power-pproportional
storage..
Proc, 1st Symposium on Cloud Computing,pp.217-228, 2010.
[3] E.Thereska, A.Donnelly, and D.Narayanan, ”Sierra: Practical oiwer-proportionality for data center storage,” Proc.
6th European Conference on Computer Systems, pp.169182, 2011.
[4] H.H. Le, S. Hikida, H Yokota,”NDCouplingHDFS: A Coupling Architecture for a Power-Proportional Hadoop Distributed File System,” IEICE Trans. Inf. & Syst., vol.E97D, no.2, pp.213-222, Feb. 2014.
[5] H.H. Le, S. Hikida,and H. Yokota, Accordion: ”An Eﬃcient
Gear-Shifting for a Power-Proportional Distributed DataPlacement Method” IEICE TRANSACTIONS on Information and Systems Vol.E98-D No.5 pp.1013-1026, 2015.
[6] H. Yokota, Y. Kanemasa, and J. Miyazaki, ”Fat-Btree: An
update-conscious parallel directory structure,” Proc. of the
15th ICDE, pp.448-457, March 1999.
[7] H.H. Le, S. Hikida,and H. Yokota, ”An Eﬃcient GearShifting Power-Proportional Distributed File System.” International Conference on Database and Expert SystemsApplications. Springer International Publishing, 2015.