DEIM Forum 2019 B8-5規模伸縮型分散ストレージにおけるギアシフト中のアクセス可能化と性能向上
中田良祐†

Le Hieu Hanh†

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

近年、情報の蓄積、収集技術の向上により多くのデータが蓄積されている。このような膨大なデータを要求処理能力に応じた電力で処理するためにシステム規模を伸縮させる分散ファイルストレージシステムが研究されている。その１つにワークロードに応じて稼働ノード数を変化させる方法があるがノード数変更に伴うデータ移動時の性能の低下が問題としてあげられる。これに対して更新ブロックの情報を分散インデックスの中に組み込むことで移動の必要なブロックの探索を容易にするとともに、更新ブロックの移行状態の管理を行い移行済みのブロックに対するアクセス要求を移行先のノードに向けることにより伸縮中の性能を向上させる手法を提案し実験、評価する。
キーワード

分散インデックス, ストレージ,HDFS, ギアシフティング

図 1 ワークロードトレース [1]
図 2 性能と電力が比例したサーバのエネルギー効率 [2]1. は じ め に応じてノード数を変化させるギアシフティングと呼ばれる規ビックデータに代表される近年の巨大な情報の利用はますま模伸縮型分散ストレージという仕組みが研究されている。シ

す求められており、それらの処理には Hadoop が代表するようステムの規模を伸縮させる仕組みを持つストレージの例としな分散処理環境が適している。分散処理環境とは、処理対象のて Rabbit [3] や Sierra [4] が研究されている。これらの方法でデータを複数の計算能力をもつノードに分散させ、それらを並はデータを複製して複数のノードに持たせることにより提供性列に動作させることにより処理能力を上げる方法である。

能を変化させることが可能である。ワークロードが大きい時にHadoop 等の分散処理環境は、一部が故障してもその他の部は複数のノードを稼働させ性能を上げ、ワークロードが小さい分は稼働可能である、故障をリカバリすることができ高い信頼時には少ないノード数で稼働し性能を下げることによりワーク性を持つ、スループット向上、スケーラビリティがある等多くロードに適した性能を提供することが可能である。これによりの利点を持つ。しかし複数のノードが常に稼働している状態に余分な性能の提供を抑え消費電力を減らすことが可能だ。

なるため消費電力もそれに比例して増加する。Hadoop などで規模伸縮型分散ストレージはデータを複製するため、処理が処理される実際のワークロードの大きさは図 1 のように一定で行われると処理されたデータの複製との一貫性を保つために必はなく大小の波があり、ここで問題となることはワークロード要なノードには変更のあったデータを移行させる必要がある。

が要求する性能とシステムが提供する性能との差が生じること

この移行はギアアップする際に必要であり時間を要する。このであり、生まれた差のぶんだけ必要以上の性能を提供し余分に移行時間を短縮するために効率的な移行を実現するメタデータ電力を消費しているということである。なので要求する性能に管理法 NDCoupling [5] やデータ配置メソッド Accordion [6] が合わせた性能を提供できるよう求められる。また、サーバーの提案されている。またこれまでギアアップ中の read が行えな省電力化を行うには図 2 のように性能とエネルギーが比例するかったが低ギアのメタデータを保持することで、ギアアップ中ような構成が望ましい [2]。の read を可能にした研究 [7] がある。ギアアップ中の read を

そこで、分散ファイルシステムではワークロードの大きさになっている。ギア２では全てのノードが動作しており、処理能力と消費電力は大きくなっている。このようにギアシフティン
グ方式を使うことにより状況に応じて異なる性能を提供できる。大きな処理能力が必要なワークロード以外ではギア１での処理能力で十分だとすると、常に四つのノードで動いているシステムと比べて消費電力を抑えることができる。

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

ギアシフティング HDFS可能にすると、ギアアップにかかる時間が長くなり、ギアアップ中の read も通常時の read より遅いという問題がある。また、更新ブロックの移行状態を管理し移行済みのブロックに対するアクセス要求を移行先のノードに向けることにより伸縮中の性能を向上させる手法 [8] が提案されているが実装、実験が行われていない。さらに既存研究の課題として、分散したノードで、ギアシフト時の当該ノードの更新適用の完・未完と、さらなるギアシフトのための情報とを同じログのレベルで持っていることが挙げられます、この対処のためにデータ配置の情報が必要になるが既存手法で用いているログにはデータ配置の情報は含まれておらず、管理が複雑になります。本研究では更新ブロックの情報を分散インデックスに組み込むことで移行ブロックの管理を容易にする。また、更新ブロックの移行状態を管理し移行済みのブロックに対するアクセス要求を移行先のノードに向けることにより伸縮中の性能を向上させる手法を実装し実験する。
本論文では、2. 節で、本研究で着目する分散ファイルストレージシステムにおけるギアシフトについて説明し、3. 節で、関連研究を紹介する。4. 節で、ブロックの更新状態の管理と更新ブロックの移行状態管理について説明し、5. 節で実験の環境と内容を説明し最後に 6. 節でまとめを述べる。

2. ギアシフティング方式
2. 1 データの配置とギアシフト
ギアシフティング方式の分散ファイルストレージシステムではデータを複製して複数のノードに持たせワークロードの大きさに合わせて稼働ノード数を変化させることでシステムの規模を伸縮する。ギア１で動作するノードを Group1 のノード、ギア 2 で新しく稼働するノードを Group2 とする。例えば図 3 で示したような四つのノードがあり２段階のギアのシステムを想定した場合、ギア１では Group1 の Node1、Node2、ギア２では Group2 の Node3、Node4 を加えた四つのノードで動作すると言った方式が考えられる。ギア１で動作する際に Group1のノードで全てのデータを処理できなくてはならないので、それらのノード内でデータを分散させる必要がある。Group2 のノードには Group1 のノード内のデータの複製（またはその一部）を持たせる。例では、Group1 のノードのデータの半数をGroup2 のノードに複製することで４並列で処理を行うことができる。
ギア１でシステムが動作している時は Node3 と Node4 は停止しており、処理能力は小さくなっているが消費電力も小さく

低ギアで動作している時にリクエスト処理が行われるとノードのデータに書き込みが発生することがある。この時、書き込みがあったノードのデータと高ギアグループのノードの対応する複製の間にデータの相違が発生する。例えば図 3 で B1 が P 1の複製であったとする。ギア１で動作している時に a に writeが発生して a′ に変わると、a′ =| a になってしまうため、ギアアップした際にデータを最新のものに変更しないと N ode3 のa は最新のデータではないため使うことができない。そこでギアアップの際には a に a′ にあった変更を反映させるためにデータの移行が必要になる。この移行が原因でギアアップ処理に時間がかかり、ギアアップ中にリクエスト応答ができない原因である。このデータの移行をより早く効率よく行うにはシステムのメタデータ管理とデータ配置が重要である。

3. 関 連 研 究
本節では効率的なギアアップ処理の観点から、Hadoop 用ギアシフティングシステムにおいて重要なメタデータ管理とデータ配置についての関連研究について説明する。

3. 1 メタデータ管理
3. 1. 1 NDCoupling
一般的 HDFS は図 4 のようにメタデータを一括管理する

NameNode が一つ存在し、リクエストはまず NameNode にアクセスする。その後、DataNode と呼ばれるデータを分散させているノード群の中から対応するノードに処理を受け渡す。全てのリクエストは一度 NameNode を通るため、リクエスト応答の処理が NameNode に集中する。その他、メタデータの管理やデータ配置、ブロックマッピングなどを一括して NameNodeが受け持つのでギアアップ時には特に大きな負荷がかかることになる。一方 NDCoupling [5] を用いた HDFS では図 5 のように、すべての DataNode に NameNode の仕事を分散させる。
各ノードのメタデータ管理モジュールやブロックマッピングは自分のノードのメタデータとブロックを管理すればよい。リクエストは最初ランダムに選ばれたノードへ行き、その後分散されたメタデータ管理モジュールが Fat-Btree [9] の構造を用いたメタデータ管理を利用して対応するノードへ渡される。処理されたデータは最初にアクセスしたノードを経由しクライアントに返される。この手法によってリクエスト処理が分散せれた。
また、データと対応するメタデータなどをノードごとに管理することができるようになり、ギアアップの際のデータの移行をスムーズに行うことが可能になる。

3. 2 データ配置
3. 2. 1 Rabbit,Sierra
分散ファイルストレージにギアシフティング方式を採用し図 7 3 ギア構成の Sierra データ配置の例
図 4 一般的な HDFS

図 5 NDCoupling+HDFS
図 8 ３ギア構成の Accordion データ配置

3. 2. 2 Accordion
Accordion [6] では、Rabbit,Sierra とは異なるデータ配置メソッドを提案しギアアップの際の効率的なデータ移行などを実現した。続く論文 [10] で NDCoupling と組み合わせたシステムを提案している。このデータ配置メソッドは図 8 のように、全てのノードに primary data を分割して持たせ、ブロック単位で低ギアのノードに複製していく配置方法により、データをブロックで扱えるようになり、ブロックごとに移行やメタデータの管理をすることができる。Accordion は Rabbit に比べて
図 6 3 ギア構成の Rabbit データ配置の例

た研究の先駆けとなったものが Rabbit [3] と Sierra [4] である。Rabbit では主に Read の性能を上げることを目的としてequall-workdata-layout policy という各ノードが同程度の量の仕事を受け持たせることを重視した配置メソッドを提案している。図 6 のように、policy を達成する計算式に基づいてギア1 で動くノード上にある primary data の複製を高ギアで動くノードに持たせている。
後に続く Sierra では Rabbit でギア 1 のノードに集中していた write の処理の負荷を各ノードに分散させる方式などを取り入れ、さらに図 7 のように、同ギアのノードの持つデータのブロックサイズを同じにすることによってノード数の制約を緩和した。
しかし両者ともにデータの移行は考慮されていないため、ギアアップ時のデータ移行量が大きく、データ移行は効率的に行うことができない。

30%スループットが向上し、NDCoupling と Accordion の構成
では HDFS と Accordion の構成と比べても 22%スループットが高い。

3. 3 データ移行中のリクエスト応答
これまでの関連研究ではギアアップ中はリクエストをブロックしてデータの移行を行なっていた。したがって高い性能が欲しい時にギアアップを要請するとしばらくリクエスト応答が停止してしまう。そこでギアアップ中も高ギアで稼働させるための修正が行われる前の低ギアのメタデータを保持する手法が提案された [7]。ギアアップ中も低ギアのメタデータを使いリクエストに応答することで高ギアの一貫性の保障されないノードへのアクセスを防いでいる。

4. 提 案 手 法
本研究では更新情報の管理のためにデータ配置の情報が必要になるが既存手法で用いているログにはデータ配置の情報は含まれていないので管理が複雑になる問題点とギアアップ中の性能低下という問題点があり移行ブロックの管理を容易にするこ

図 10

図 9 更新情報、移行状態を管理しながらのギアアップ処理

ギアアップ中の read 処理とと、ギアアップ中の性能を向上させることを目的に更新情報と移行状態のメタデータ管理を行う。

4. 1 更新情報, 移行状態のメタデータ管理
既存手法ではどのブロックに更新があり、ギアアップの際にはその更新はどこのノードのブロックへ反映させる必要があるのかログファイルに書いていた。既存手法はギアシフト時の当該ノードの更新適用の完・未完と、更なるギアシフトのための情報とを同じログのレベルで持っていることが問題であり、こ図 11 ノードスペックの対応のためにデータ配置の情報が必要になるがログファイルの中にデータ配置は含まれないので管理が複雑になる。検索に使う分散インデックスがブロックのメタデータを管理しており、本提案ではそのメタデータに更新情報も管理させる。メタデー
タはもともとデータ配置を管理しているため移行ブロックの管理は容易に行える。またブロック毎に、メタデータにデータの移行状態を持たせてアクセス先のデータノードを決定させる。
移行状態は移行中と移行済があり、移行済の場合のみ高ギアのノードもすでにデータは最新のものである。この時、メタデータの指す低ギアのノードにアクセスする代わりに高ギアのノードにアクセスさせる。こうすることによってギアアップ中に処理性能が徐々に上がり、より早くリクエスト処理ができるようになる。

4. 1. 1 更新情報、移行状態を管理しながらのギアアップ
提案手法の実現手順について図 9 を使い説明する。Node i はギア g のノード、Node j はギア g+1 のノードとして、ギア gからギア g+1 へのギアアップの手順を以下に示す。
（ 1 ） メタデータを複製して Node j へ移行する。
（ 2 ） 移行の必要なブロックはリーフノードを横にたどり探し移行状態を移行済に変更する。

4. 1. 2 ギアアップ中のリクエスト処理
図 10 を使い移行状態を用いた read の手順は以下のようになる。クライアントから File A が読みたいという reqest があったとする。
（ 1 ） NameNode はインデックスをたどり File A に対応するリーフノードにたどり着く（ 2 ） リーフノードは File A の情報を持つ BlockInfo の Listを持つ。File A がどの Block に分割されているかがわかる。
（ 3 ） BlockInfo が持つ移行状態を得る。
（ 4 ） BlocksMap の中に Block とその Block を持つ DataN-

ode の対応が書かれているので client は次にアクセスすべきDataNode がわかる。ここで移行状態を見て移行済なら高ギアのノードを移行未なら低ギアのノードを選択する。
（ 5 ） File A を含む Block とその Block を持つ Data Nodeの組み合わせを作りクライアントに返す。

5. 実験

索する。データの書き込みがあった場合、ブロックのメタデー
タに変更ありとなっているので、そのブロックを移行キューに挿入する。また、移行状態を移行中、変更状態を変更なしにする。
（ 3 ） データノードは移行キューから移行の必要なブロックを得て移行を行う。
（ 4 ） Node j はブロックを受け取ると NameNode に受け取ったことを報告する。
（ 5 ） NameNode は受け取ったブロックの状態を修正し送信元の NameNode へブロックを受け取ったことを報告する。
（ 6 ） Node j は Node i がブロックを受け取ったことを確認

本論文では 4.1 で提案した手法の変更状態の効果を確認する
実験と 4.1 で提案した手法の移行状態の効果を確認する実験をする。

5. 1 実 験 環 境
ノードのスペックは図 11 のようになっている。実験は Ac-cordion+NDCoupling の構成で、全て 5 回行い平均値を取っています。実験結果のエラーバーは 95%信頼区間を示す。

5. 2 変更状態メタデータ
移行の必要なブロックを探す手法としてメタノードに持たせた変更情報を見て探す方法とあらかじめログファイルに書いておいたものから探す方法を比較した。

図 12 変更状態メタデータ実験のギア構成

図 16

図 13

移行状態管理の実験手順変更状態メタデータ実験手順

図 17移行状態メタデータの実験結果：ギア 1 から 2

図 18移行状態メタデータの実験結果：ギア 2 から 3

図 14 変更状態メタデータの実験結果

図 15 移行状態メタデータ実験のギア構成

5. 2. 1 実 験 手 順
実験を図 12 の構成で図 13 が示す手順で行なった。

アップ開始（ 1 ） ギア 2 で 150 ファイル書き込み（ 6 ） ギアアップ、ファイル読み込み終了（ 2 ） ギア 1 で 150 ファイル書き込み

5. 3. 2 実験結果：ギア 1 から 2（ 3 ） ギア 1 で 300 ファイル読み込みと同時にギアアップ
開始（ 4 ） ギアアップ終了後、ファイル読み込み完了

5. 2. 2 実 験 結 果
実験結果は図 14 のようになった。ログによる管理と変更情報をメタデータに持たせた管理とで大きな差は出なかったことがわかる。よって管理が容易でないログの手法を使うより、柔軟に対応ができるメタデータに変更情報を持たせる手法の方が

図 17 のような実験結果が出た。移行状態の管理をすることによって全てのデータで優れた結果が出た。特にギアアップ時間を 12%削減することができた。

5. 3. 3 実験結果：ギア 2 から 3
図 18 のような結果になった。ギア 1 から 2 ほど大きな差は出なかった。ギアアップにかかる時間が短くなり移行状態の管理による I/O 分散の効果があまり出なかったのだと考えられる。

6. ま と め優れている。

5. 3 移行状態メタデータ
変更状態をもたせた手法と変更状態+移行状態メタデータをもたせた構成とで比較を行った。

5. 3. 1 実 験 手 順
実験を図 16 が示す以下の手順で行った。
（ 1 ） ギア 3 で 50 ファイル書き込み（ 2 ） ギア 2 で 50 ファイル書き込み（ 3 ） ギア 1 で 200 ファイル書き込み（ 4 ） ギア 1 で 300 ファイル読み込みと同時にギア２へギアアップ開始（ 5 ） ギア 2 で 300 ファイル読み込みと同時にギア３へギア

本研究では規模伸縮型ストレージの規模伸縮に伴う移行データの管理を容易にすることと、規模伸縮時の read 性能を向上させることを目的とした。それぞれ、移行するデータの探索を容易にするためにブロックに変更があったかどうかを示す変更状態を保たせる手法と、データ移行時の IO を向上させるためにブロックに移行状態のメタデータをもたせ、移行が済んでいるブロックへのアクセスは移行先のノードに移す手法を提案した。
変更情報を保たせた実験ではギアアップにかかる時間はほとんど既存のログを使った手法と変わらなかった。よってデータの管理を容易に行うことのできる変更情報の方が優れていると言える。
移行状態を保たせた実験ではギアアップの時間が短縮された、

またギアアップ時の移行ブロック数が増加するにつれより高い効果が得られることが確認できた。
今後の課題は、ギアの構成を変えた時の性能を見ていく。また、実際のワークロードに適したギアの構成は何かと、ギアアップのタイミングの検討を行う必要がある。

文

献[1] Zujie Ren, Jian Wan, Weisong Shi, Xianghua Xu, and Min
Zhou, Workload Analysis, Implications, and Optimization
on a Production Hadoop Cluster: A Case Study on Taobao
IEEE TRANSACTIONS ON SERVICES COMPUTING,VOL. 7, NO. 2, APRIL-JUNE 2014
[2] L.A. Barroso and U. H olzle, The Case for Energyproportional Computing, Computer, vol.40, pp. 33-37, 2007
[3] 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.
[4] E.Thereska, A.Donnelly, and D.Narayanan, Sierra: Practical power-proportionality for data center storage, Proc.
6th European Conference on Computer Systems, pp.169182, 2011.
[5] 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.
[6] H.H. Le, S. Hikida,and H. Yokota, Accordion: An Eﬃcient
Gear-Shifting for a Power-Proportional Distributed DataPlacement Method IEICE Trans. inf. & Syst., Vol.E98-D
No.5 pp.1013-1026, 2015.
[7] 中田良祐,Le Hieu hanh , 横田治夫, システム規模を伸縮させる HDFS の QoS 向上 DEIM Forum 2018 H6-3.
[8] 杉山翔一郎, レーヒェウハン, 横田治夫, システム規模を伸縮させる HDFS におけるデータ移行中のリクエスト応答調整
DEIM Forum 2017 H5-1.
[9] 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.
[10] H.H. Le, S. Hikida,and H. Yokota, An Eﬃcient Gear- Shifting Power-Proportional Distributed File System. In- ternational Conference on Database and Expert Systems Applications. Springer International Publishing, 2015.