(57)【特許請求の範囲】
【請求項１】
複数のデータファイルの中からデータファイルを選択して移動元ノードから移動先ノードへ移動させる移動制御装置であって、
前記データファイルを分割して生成した複数のデータブロックの中から、前記移動先ノードへ移動させる移動データブロックを選択する移動データブロック選択部と、
前記移動データブロック選択部によって選択された前記移動データブロックを備えるデータファイルを移動データファイルとして選択する移動データファイル選択部と、
前記移動データファイル選択部によって選択された前記移動データファイルに備えられる全てのデータブロックを前記移動データブロックに追加する移動データブロック追加部と、
個々の移動データブロックのそれぞれについて、当該移動データブロックを備える全てのデータファイルが、前記移動データファイル選択部によって前記移動データファイルとして選択されると、当該移動データブロックを削除データブロックとして選択する削除データブロック選択部と、
前記移動データブロックを前記移動先ノードに格納させるとともに、前記削除データブロックを前記移動元ノードから削除することにより、前記移動元ノードから前記移動先ノードへ前記データファイルを移動させる移動処理部と
をそなえることを特徴とする、移動制御装置。
【請求項２】
前記移動処理部が、前記削除データブロックの合計データ量が所定の目標削減データ量以上であり、且つ、前記削除データブロックの合計データ量に対する、前記移動データブロックの合計データ量の割合が所定値以下である場合に、前記移動元ノードから前記移動先ノードへ前記データファイルを移動させる
ことを特徴とする、請求項１記載の移動制御装置。
【請求項３】
前記移動データブロック選択部が、前記複数のデータブロックの中から、複数のデータファイルによる重複使用数が、他のデータブロックよりも少ないデータブロックを優先的に前記移動データブロックとして選択する
ことを特徴とする、請求項１又は２記載の移動制御装置。
【請求項４】
データファイルを分割して生成した複数のデータブロックの中から、移動元ノードから移動先ノードへ移動させる移動データブロックを選択し、
選択された前記移動データブロックを備えるデータファイルを移動データファイルとして選択し、
選択された前記移動データファイルに備えられる全てのデータブロックを前記移動データブロックに追加し、
個々の移動データブロックのそれぞれについて、当該移動データブロックを備える全てのデータファイルが、前記移動データファイルとして選択されると、当該移動データブロックを削除データブロックとして選択し、
前記移動データブロックを前記移動先ノードに格納させるとともに、前記削除データブロックを前記移動元ノードから削除することにより、前記移動元ノードから前記移動先ノードへ前記データファイルを移動させる
処理をコンピュータに実行させるプログラム。
【請求項５】
前記削除データブロックの合計データ量が所定の目標削減データ量以上であり、且つ、前記削除データブロックの合計データ量に対する、前記移動データブロックの合計データ量の割合が所定値以下である場合に、前記移動元ノードから前記移動先ノードへ前記データファイルを移動させる
処理をコンピュータに実行させる、請求項４記載のプログラム。
【請求項６】
前記複数のデータブロックの中から、複数のデータファイルによる重複使用数が、他のデータブロックよりも少ないデータブロックを優先的に前記移動データブロックとして選択する、
処理をコンピュータに実行させる、請求項４又は５記載のプログラム。
【請求項７】
データファイルを記憶可能なデータ記憶装置と、
前記データファイルを分割して複数のデータブロックを生成し、生成したデータブロック間で重複除去を行なって前記データ記憶装置に格納する重複除去部と、
前記複数のデータブロックの中から、移動先ノードへ移動させる移動データブロックを選択する移動データブロック選択部と、
前記移動データブロック選択部によって選択された前記移動データブロックを備えるデータファイルを移動データファイルとして選択する移動データファイル選択部と、
前記移動データファイル選択部によって選択された前記移動データファイルに備えられる全てのデータブロックを前記移動データブロックに追加する移動データブロック追加部と、
個々の移動データブロックのそれぞれについて、当該移動データブロックを備える全てのデータファイルが、前記移動データファイル選択部によって前記移動データファイルとして選択されると、当該移動データブロックを削除データブロックとして選択する削除データブロック選択部と、
前記移動データブロックを前記移動先ノードに格納させるとともに、前記削除データブロックを移動元ノードから削除することにより、前記移動元ノードから前記移動先ノードへ前記データファイルを移動させる移動処理部と
をそなえることを特徴とする、ストレージ装置。
【請求項８】
前記移動処理部が、前記削除データブロックの合計データ量が所定の目標削減データ量以上であり、且つ、前記削除データブロックの合計データ量に対する、前記移動データブロックの合計データ量の割合が所定値以下である場合に、前記移動元ノードから前記移動先ノードへ前記データファイルを移動させる
ことを特徴とする、請求項７記載のストレージ装置。
【請求項９】
前記移動データブロック選択部が、前記複数のデータブロックの中から、複数のデータファイルによる重複使用数が、他のデータブロックよりも少ないデータブロックを優先的に前記移動データブロックとして選択することを特徴とする、請求項７又は８記載のストレージ装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本件は、移動制御装置，プログラム及びストレージ装置に関する。
【背景技術】
【０００２】
近年、大量のデータを蓄積するために、複数のサーバノードを備える分散ストレージシステムが実現されている。分散ストレージシステムでは、データの蓄積とともに、ノード毎に蓄積しているデータ量が偏ってくることがある。
このため、各ノードにおいて蓄積したデータをノード間で移動させることにより、ノード間でのデータ量の均等化を図るデータ再配置が行なわれている。
【０００３】
データ再配置を行なうことにより、データの偏りにより生じる、一部のノードのストレージの枯渇や、特定のノードにアクセスが集中することによる性能低下を阻止することができる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１１−２１５７９４号公報
【特許文献２】特開２０１１−１５９２４２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
従来の分散ストレージシステムにおいては、ストレージを効率的に使用できるようにデータの再配置を行ないデータの均一化を行なうことが求められている。
１つの側面では、本件は、ストレージを効率的に使用できるようにすることを目的とする。
なお、前記目的に限らず、後述する発明を実施するための形態に示す各構成により導かれる作用効果であって、従来の技術によっては得られない作用効果を奏することも本発明の他の目的の1つとして位置付けることができる。
【課題を解決するための手段】
【０００６】
このため、この移動制御装置は、複数のデータファイルの中からデータファイルを選択して移動元ノードから移動先ノードへ移動させる移動制御装置であって、前記データファイルを分割して生成した複数のデータブロックの中から、前記移動先ノードへ移動させる移動データブロックを選択する移動データブロック選択部と、前記移動データブロック選択部によって選択された前記移動データブロックを備えるデータファイルを移動データファイルとして選択する移動データファイル選択部と、前記移動データファイル選択部によって選択された前記移動データファイルに備えられる全てのデータブロックを前記移動データブロックに追加する移動データブロック追加部と、個々の移動データブロックのそれぞれについて、当該移動データブロックを備える全てのデータファイルが、前記移動データファイル選択部によって前記移動データファイルとして選択されると、当該移動データブロックを削除データブロックとして選択する削除データブロック選択部と、前記移動データブロックを前記移動先ノードに格納させるとともに、前記削除データブロックを前記移動元ノードから削除することにより、前記移動元ノードから前記移動先ノードへ前記データファイルを移動させる移動処理部とをそなえる。
【０００７】
また、このプログラムは、データファイルを分割して生成した複数のデータブロックの中から、移動元ノードから移動先ノードへ移動させる移動データブロックを選択し、選択された前記移動データブロックを備えるデータファイルを移動データファイルとして選択し、選択された前記移動データファイルに備えられる全てのデータブロックを前記移動データブロックに追加し、個々の移動データブロックのそれぞれについて、当該移動データブロックを備える全てのデータファイルが、前記移動データファイルとして選択されると、当該移動データブロックを削除データブロックとして選択し、前記移動データブロックを前記移動先ノードに格納させるとともに、前記削除データブロックを前記移動元ノードから削除することにより、前記移動元ノードから前記移動先ノードへ前記データファイルを移動させる。
【０００８】
さらに、このストレージ装置は、データファイルを記憶可能なデータ記憶装置と、前記データファイルを分割して複数のデータブロックを生成し、生成したデータブロック間で重複除去を行なって前記データ記憶装置に格納する重複除去部と、前記複数のデータブロックの中から、移動先ノードへ移動させる移動データブロックを選択する移動データブロック選択部と、前記移動データブロック選択部によって選択された前記移動データブロックを備えるデータファイルを移動データファイルとして選択する移動データファイル選択部と、前記移動データファイル選択部によって選択された前記移動データファイルに備えられる全てのデータブロックを前記移動データブロックに追加する移動データブロック追加部と、個々の移動データブロックのそれぞれについて、当該移動データブロックを備える全てのデータファイルが、前記移動データファイル選択部によって前記移動データファイルとして選択されると、当該移動データブロックを削除データブロックとして選択する削除データブロック選択部と、前記移動データブロックを前記移動先ノードに格納させるとともに、前記削除データブロックを移動元ノードから削除することにより、前記移動元ノードから前記移動先ノードへ前記データファイルを移動させる移動処理部とをそなえる。
【発明の効果】
【０００９】
本発明によれば、複数のノード間においてデータ量を均等化することができる。
【図面の簡単な説明】
【００１０】
【図１】実施形態の一例としてのストレージサーバノードをそなえる分散ストレージシステムの機能構成を模式的に示す図である。
【図２】実施形態の一例としてのストレージサーバノードをそなえる分散ストレージシステムの構成を模式的に示す図である。
【図３】実施形態の一例としての分散ストレージシステムにおけるデータファイル構成情報を模式的に例示する図である。
【図４】実施形態の一例としての分散ストレージシステムにおけるインデックステーブルを模式的に例示する図である。
【図５】実施形態の一例としての分散ストレージシステムにおけるデータファイル移動時の全体的な処理を説明するためのフローチャートである。
【図６】実施形態の一例としての分散ストレージシステムにおける再分散データ選択部によるデータファイルの移動処理を説明するためのフローチャートである。
【図７】（ａ），（ｂ）は従来の重複排除手法を説明する図である。
【発明を実施するための形態】
【００１１】
以下、図面を参照して本移動制御装置，プログラム及びストレージ装置に係る実施の形態を説明する。ただし、以下に示す実施形態はあくまでも例示に過ぎず、実施形態で明示しない種々の変形例や技術の適用を排除する意図はない。すなわち、本実施形態を、その趣旨を逸脱しない範囲で種々変形して実施することができる。又、各図は、図中に示す構成要素のみを備えるという趣旨ではなく、他の機能等を含むことができる。
【００１２】
（Ａ）構成
図１は実施形態の一例としてのストレージサーバノードをそなえる分散ストレージシステムの機能構成を模式的に示す図、図２はそのストレージサーバノードをそなえる分散ストレージシステムの構成を模式的に示す図である。
分散ストレージシステム１は、図２に示すように、管理サーバ３０，プロキシサーバ４０，クライアント６０及びストレージサーバノード（ストレージ装置，移動制御装置）１０−１〜１０−６を備える。ただし、図１中においては、便宜上、クライアント６０及びプロキシサーバ４０の図示を省略している。
【００１３】
図２に示す例においては、管理サーバ３０及び各ストレージサーバノード１０−１〜１０−６と各プロキシサーバ４０とは、例えばＬＡＮ（Local Area Network）５０を介して、相互に通信可能に接続されている。又、各プロキシサーバ４０と各クライアント６０とは、公衆回線網等のネットワーク５１を介して、相互に通信可能に接続されている。
分散ストレージシステム１は、複数のストレージサーバノード１０−１〜１０−６がそれぞれ有するディスク領域をまとめて、あたかも一つのストレージのように取り扱うことを可能とする。この分散ストレージシステム１においては、複数のデータファイルを複数のストレージサーバノード１０−１〜１０−６に分散して配置される。
【００１４】
以下、ストレージサーバノードを示す符号としては、複数のストレージサーバノードのうち１つを特定する必要があるときには符号１０−１〜１０−６を用いるが、任意のストレージサーバノードを指すときには符号１０を用いる。
クライアント６０は、例えば、パーソナルコンピュータ等の情報処理装置であり、プロキシサーバ４０を介して、ストレージサーバノード１０に格納されたデータファイル（ファイル）に対するリードやライトの要求（リード／ライト要求）を行なう。図１及び図２に示す例においては、分散ストレージシステム１に２つのクライアント６０が備えられているが、これに限定されるものではなく、１つもしくは３以上のクライアント６０をそなえてもよい。
【００１５】
クライアント６０は、例えば、アクセス対象のファイル名（オブジェクト名）等のデータファイルを特定する情報とともにリード／ライト要求をプロキシサーバ４０に対して送信する。
プロキシサーバ４０は、クライアント６０に代わってストレージサーバノード１０へのデータアクセスを行なう。各プロキシサーバ４０は、サーバ機能を備えたコンピュータ等の情報処理装置であり、互いに同様の構成を備える。図１及び図２に示す例においては、分散ストレージシステム１に２つのプロキシサーバ４０が備えられているが、これに限定されるものではなく、１つもしくは３以上のプロキシサーバ４０をそなえてもよい。
【００１６】
プロキシサーバ４０は、それぞれ分散表４１を備える。分散表４１は、データファイルを特定する情報に対して当該データファイルの格納位置を関連付けて構成される。プロキシサーバ４０は、クライアント６０からデータファイルへのリード／ライト要求を受信すると、受信したファイル名に基づいて分散表４１を参照して、アクセス対象のデータファイルの格納場所を確認する。プロキシサーバ４０は、このデータファイルの格納場所に対応するストレージサーバノード１０に対してリード／ライト要求を送信する。又。プロキシサーバ４０は、ストレージサーバノード１０からリード／ライト要求に対するリプライを受信すると、リード／ライト要求の送信元のクライアント６０に対して、そのリプライを転送する。
【００１７】
なお、プロキシサーバ４０としての機能は、既知の種々の手法で実現され、その詳細な説明は省略する。
管理サーバ３０は、サーバ機能を備えたコンピュータ等の情報処理装置であり、本分散ストレージシステム１における各種設定や制御を行なう。又、管理サーバ３０は、本分散ストレージシステム１における各ストレージサーバノード１０が保持するデータ量を管理するデータ管理機能（データ管理プロセス）をそなえる。本実施形態においては、分散ストレージシステム１に一つの管理サーバ３０を備える例を示すが、これに限定されるものではなく、２以上の管理サーバ３０を備えてもよいし、ストレージサーバノード１０が管理サーバ３０の機能を分担してもよい。
【００１８】
後述する各ストレージサーバノード１０は、それぞれが有する記憶装置１４に保持するデータのデータ量（以下、単にデータ量という）を定期的に管理サーバ３０のデータ量管理プロセスに通知する。
管理サーバ３０（データ量管理プロセス）は、本分散ストレージシステム１に備えられた複数のストレージサーバノード１０間でデータ量の偏りが生じているか否かを判断する。例えば、データ量管理プロセスは各ストレージサーバノード１０からそれぞれ通知されたデータ量の平均値を算出し、この算出した平均値と各ストレージサーバノード１０が保持するデータ量とを比較する。
【００１９】
例えば、保持するデータ量が平均値よりも少なく、且つ、そのデータ量と平均値との差が所定の閾値以上であるストレージサーバノード１０が検出された場合には、データ量管理プロセスは、ストレージサーバノード１０間でデータの偏りが生じたと判断する。又、このデータ量が平均値に対して所定の閾値以上少ないと判断されたストレージサーバノード１０を、データファイルの移動先となるストレージサーバノード１０として決定する。なお、以下、このデータファイルの移動先となるストレージサーバノード１０を移動先ノードという場合がある。
【００２０】
また、管理サーバ３０は、本分散ストレージシステム１に備えられた複数のストレージサーバノード１０間において、例えば、保持するデータ量が最も多いストレージサーバノード１０に対して、前述した移動先ノードに対してデータファイルの移動を指示する。以下、管理サーバ３０によりデータファイルの移動を指示されるストレージサーバノード１０を移動元ノードという場合がある。
【００２１】
また、管理サーバ３０（データ量管理プロセス）は、データの偏りが生じたと判断した場合に、算出した平均値と移動先ノードが保持するデータ量との差（Xbyte）を目標データ移動量（目標削減データサイズ）として決定する。すなわち、この目標データ移動量（Xbyte）が、本分散ストレージシステム１におけるデータの偏りを解消するために、移動元ノードから移動先ノードに移動させるべきデータ量である。
【００２２】
管理サーバ３０は、移動元ノードに対して移動先ノード及び目標データ移動量を通知することにより、移動先ノードへの目標データ移動量に相当するデータファイルの移動を指示する。
ストレージサーバノード１０−１〜１０−６は、それぞれ記憶装置（データ記憶装置）１４をそなえる情報処理装置であり、この記憶装置１４にファイルデータを格納するストレージサーバ機能を備える。各ストレージサーバノード１０−１〜１０−６は互いに同様の構成を備える。なお、図１においては、便宜上、ストレージサーバノード１０−１についてのみハードウェア構成や機能構成を図示し、他のストレージサーバノード１０−２〜１０−６のハードウェア構成や機能構成の図示を省略している。
【００２３】
本実施形態においては、分散ストレージシステム１に６つのストレージサーバノード１０を備える例を示すが、これに限定されるものではなく、５つ以下もしくは７つ以上のストレージサーバノード１０を備えてもよい。
ストレージサーバノード１０は、図１に示すように、ＣＰＵ（Central Processing Unit）１１，ＲＡＭ（Random Access Memory）１２，ＲＯＭ（Read Only Memory）１３及び記憶装置１４をそなえる。
【００２４】
記憶装置１４は種々のデータやプログラムを格納する記憶装置であって、例えば、ＨＤＤ（Hard Disk Drive）やＳＳＤ（Solid State Drive）である。又、記憶装置１４として、例えば、複数の記憶装置によりＲＡＩＤ（Redundant Arrays of Inexpensive Disks）を構成してもよく、種々変形して実施することができる。
この記憶装置１４には、各クライアント６０からリードもしくはライトされるデータファイルが、所定サイズに分割されたデータブロックの状態で格納される。そして、この記憶装置１４においては、同一のデータブロックが重複して格納されることがない。
【００２５】
また、記憶装置１４は、ファイル情報２４０及び重複排除情報２５０を格納する。
ファイル情報２４０は、そのストレージサーバノード１０に格納されるデータファイルを示す情報（例えば、ファイル名）である。後述するデータ再分散部２７によりストレージサーバノード１０間でデータファイルの再配置が行なわれ、データファイルの移動が行われると、このファイル情報２４０が更新される。
【００２６】
重複排除情報２５０は、データファイルを構成するデータブロックに関する情報であって、データを分割して形成されるデータブロックや、そのハッシュキー，データブロック構成等を表す。重複排除情報２５０としては、例えば、ＦＰ情報２５０ａ，データファイル構成情報２５０ｂ及びインデックステーブル２５０ｃをそなえる。
ＦＰ情報２５０ａは、記憶装置１４におけるブロックデータの格納状態（格納実績）を管理する情報であり、データファイルを構成する各データブロックのフィンガープリント（finger print：ＦＰ）が登録される。例えば、後述する記憶装置１４にブロックデータを格納する際に、この記憶装置１４に格納したブロックデータを特定する情報が、そのボリュームを識別する情報に対応させてＦＰ情報２５０ａに登録される。
【００２７】
ＦＰは、データブロックのハッシュ値を求める手法等により作成される。後述する重複除去部２１は、このＦＰを用いることによりデータブロックの一致／不一致を判断し、これによりデータブロックの重複を判断する。このＦＰ情報２５０ａは、既知の種々の手法を用いて実現することができ、その詳細な説明は省略する。
データファイル構成情報２５０ｂは、データファイルを復元するための情報であり、例えば、データファイルを構成するデータブロックのインデックスやその位置を示す（データブロックパターン）。インデックスは、データブロックを一意に特定する識別情報である。
【００２８】
図３は実施形態の一例としての分散ストレージシステム１におけるデータファイル構成情報２５０ｂを模式的に例示する図である。
なお、図３に示す例においては、ファイルを構成する各データブロックの位置をデータブロックの配置順序で表している。すなわち、この図３に示す例においては、例えば、ファイルＡ（データファイル）が、インデックス01,02,03,04,05で表されるデータブロックを備えることを示す。このファイルＡは、インデックス01,02,03,04,05で表されるこれらのデータブロックを、この図３に示す順で配置することにより復元される。同様に、ファイルＢはインデックス05,06,02,03,04で表されるデータブロックを備えるものであり、これらのデータブロックをこの順で配置することにより、ファイルＢが復元される。
【００２９】
このように、このデータファイル構成情報２５０ｂを参照することにより、データブロックを用いてデータの復元ファイルの復元を行なうことが可能となる。なお、データファイル構成情報２５０ｂは、既知の種々の手法を用いて実現することができ、その詳細な説明は省略する。
図４は実施形態の一例としての分散ストレージシステム１におけるインデックステーブル２５０ｃを模式的に例示する図である。
【００３０】
インデックステーブル２５０ｃは、当該ストレージサーバノード１０に格納されるデータファイルの各データブロックに関する情報であり、当該ストレージサーバノード１０における各データブロックの重複関係を示す。インデックステーブル２５０ｃは、図４に示すように、インデックス（index）に対して、カウンタ（counter），リファー（refer）及びポインタ（pointer）を関連付けて構成されている。
【００３１】
カウンタは、そのストレージサーバノード１０において、そのデータブロックを備える（使用する）データファイル（使用元）の数である。すなわち、カウンタの値は、当該データブロックを使用するデータファイルの重複数（重複使用数）を表す。このカウンタの値（カウンタ値）が小さいデータブロックは、当該データブロックを使用（共用）しているデータファイルが少ないことを示す。
【００３２】
リファーは、そのデータブロックが備えられるデータファイルを示し、データファイルを特定する情報が格納される。
例えば、図４に示す例において、インデックス“01”のデータブロックに対して、カウンタ “1”及びリファー“A”が設定されている。これにより、このインデックス“01”のデータブロックは、一つのデータファイルであるファイルＡにのみ備えられることがわかる。又、インデックス“02”のデータブロックに対して、カウンタ “2”及びリファー“A,B”が設定されている。これにより、このインデックス“02”のデータブロックは、ファイルA,Bの２つのデータファイルに備えられることがわかる。ポインタは、そのデータブロックの格納位置（アドレス等）を表す。
【００３３】
なお、上述した重複排除情報２５０は、例えば、後述する重複除去部２１によって設定される。
なお、ストレージサーバノード１０においては、例えば、キーボードやマウス等の入力装置や表示装置をそなえてもよい。
ＲＯＭ１３は種々のデータやプログラムを格納する記憶装置である。ＲＡＭ１２はＣＰＵ１１が演算処理等を行なう際に、データやプログラム等を一時的に格納する記憶装置である。
【００３４】
また、このＲＡＭ１２には、後述する低カウントブロックリスト１２１，移動ブロックリスト１２２，使用元リスト１２３及び削除ブロックリスト１２４が記憶される。なお、上述した重複排除情報２５０やファイル情報２４０をこのＲＡＭ１２に記憶してもよい。
ＣＰＵ１１はＲＯＭ１３や記憶装置１４に格納されたＯＳ（Operating System）や各種プログラムを実行することにより、種々の演算や制御を行なう。ストレージサーバノード１０においては、このＣＰＵ１１が記憶装置１４等に格納されたプログラムを実行することにより、図１に示す、重複除去部２１，再分散データ選択部２２及びデータ再分散部２７として機能する。
【００３５】
なお、これらの重複除去部２１，再分散データ選択部２２及びデータ再分散部２７としての機能を実現するためのプログラムは、例えばフレキシブルディスク，ＣＤ（ＣＤ−ＲＯＭ，ＣＤ−Ｒ，ＣＤ−ＲＷ等），ＤＶＤ（ＤＶＤ−ＲＯＭ，ＤＶＤ−ＲＡＭ，ＤＶＤ−Ｒ，ＤＶＤ＋Ｒ，ＤＶＤ−ＲＷ，ＤＶＤ＋ＲＷ，ＨＤ  ＤＶＤ等），ブルーレイディスク，磁気ディスク，光ディスク，光磁気ディスク等の、コンピュータ読取可能な記録媒体に記録された形態で提供される。そして、コンピュータはその記録媒体からプログラムを読み取って内部記憶装置または外部記憶装置に転送し格納して用いる。又、そのプログラムを、例えば磁気ディスク，光ディスク，光磁気ディスク等の記憶装置（記録媒体）に記録しておき、その記憶装置から通信経路を介してコンピュータに提供するようにしてもよい。
【００３６】
重複除去部２１，再分散データ選択部２２及びデータ再分散部２７としての機能を実現する際には、内部記憶装置（本実施形態ではＲＡＭ１２やＲＯＭ１３）に格納されたプログラムがコンピュータのマイクロプロセッサ（本実施形態ではＣＰＵ）によって実行される。このとき、記録媒体に記録されたプログラムをコンピュータが読み取って実行するようにしてもよい。
【００３７】
なお、本実施形態において、コンピュータとは、ハードウェアとオペレーティングシステムとを含む概念であり、オペレーティングシステムの制御の下で動作するハードウェアを意味している。又、オペレーティングシステムが不要でアプリケーションプログラム単独でハードウェアを動作させるような場合には、そのハードウェア自体がコンピュータに相当する。ハードウェアは、少なくとも、ＣＰＵ等のマイクロプロセッサと、記録媒体に記録されたコンピュータプログラムを読み取るための手段とをそなえており、本実施形態においては、ストレージサーバノード１０がコンピュータとしての機能を有している。
【００３８】
重複除去部２１は、データファイルを複数のデータブロックに分割して重複除去を実行し、重複排除を実行して得られたデータブロックを記憶装置１４に記憶させる。
重複除去部２１は、データファイルを複数のデータブロックに分割するデータ分割部としての機能を備える。例えば、重複除去部２１は、ホストコンピュータ等の図示しない外部装置から受信するバックアップデータ（データファイル）を分割する。
【００３９】
重複除去部２１は、固定長型もしくは可変長型のいずれかの形式でデータファイルの分割を行なう。ここで、固定長型は予め決められたサイズでデータを分割する手法であり、可変長型は特定の区切り方のルールに従って分割する方法である。なお、この重複除去部２１によるデータ分割は、既知の種々の手法により実現することができるものであり、その詳細な説明は省略する。
【００４０】
また、重複除去部２１は、例えば、データブロックのＦＰによりデータブロックの一致／不一致を判断し、これによりデータブロックの重複を判断する重複記憶判定部としての機能をそなえる。本実施形態においては、重複除去部２１は、ＦＰが同一のデータブロックは同一のデータブロックであると判断する。
重複除去部２１は、例えば、データファイルを記憶装置１４に格納する際に、そのデータファイルを構成する個々のデータブロックについて、それぞれ、ＦＰ情報２５０ａを参照する。これにより、各データブロックと同一のデータブロックが記憶装置１４に記憶されているか否かを判定する。
【００４１】
また、重複除去部２１は、例えば、データファイルを記憶装置１４に格納する際に、処理対象のデータブロックと同一のデータブロックが記憶装置１４に格納されていると判断した場合には、その処理対象のデータブロックを廃棄し、その処理対象データブロックの記憶装置１４における重複保存を抑止する。すなわち、重複除去部２１は、同一のＦＰのデータブロックを一の記憶装置１４においては１つしか記憶させない、重複排除（デデュープ：De-dupulication）を実現する。重複除去部２１は、記憶装置１４中には１つだけ記憶させたデータブロックを複数のデータファイルで共用することにより、データファイルの記憶領域を削減する。すなわち、重複除去部２１は、重複排除エンジンとして機能する。
【００４２】
なお、重複排除には、例えば、データをストレージ装置の制御部で比較しながらストレージ装置内に記憶するインライン方式を用いることができる。なお、これに限定されるものではなく、例えば、いわゆるポストプロセス方式やクライアント方式等の他の手法を用いてもよく、適宜変更して実施することができる。
また、重複除去部２１は、データブロック毎に行なったＦＰやデータブロック構成の作成等の結果を、ＦＰ情報２５０ａやインデックステーブル２５０ｃ，データファイル構成情報２５０ｂに保存する。
【００４３】
さらに、重複除去部２１は、記憶装置１４からデータファイルを読み出す際には、その記憶装置１４に記憶されたボリュームについての重複排除情報２５０を読み出す。
重複除去部２１は、データの読み出し時において、データブロックからボリュームを復元する。重複除去部２１は、例えば、データファイル構成情報２５０ｂを参照し、記憶装置１４から読み出したデータブロックを用いてデータファイルの復元を行なう。すなわち、重複排除情報２５０に従って、データブロックの複写等を行なうことによりデータファイルを作成する。なお、データファイルと当該データファイルを分割して生成されるデータブロックとに関して、データブロックを備えるデータファイル、もしくはデータブロックを用いるデータファイルという場合がある。
【００４４】
なお、重複排除情報２５０に基づくデータブロックを用いたデータファイルの復元方法は、既知の種々の手法を用いて実現され、その詳細な説明は省略する。
再分散データ選択部２２は、管理サーバ３０から、移動先ノード及び目標データ移動量を通知されると、当該ストレージサーバノード１０の記憶装置１４に格納されているデータファイルの中から、移動先ノードへ移動（再分散）させるデータファイル（移動データファイル）を選択する。すなわち、再分散データ選択部２２は、複数のストレージサーバノード１０に、データファイルが分散して格納された分散ストレージシステムにおいて、一のストレージサーバノード１０から他のストレージサーバノード１０に移動させる移動データファイルを選択する。
【００４５】
再分散データ選択部２２は、重複除去部２１により重複排除が行なわれているデータファイルに関して、データファイルを構成するデータブロックの重複状況を考慮して、移動元ノードから移動先ノードへ移動させるデータファイル（移動データファイル）を選択する。
再分散データ選択部２２は、インデックステーブル２５０ｃを参照しながら、低カウントブロックリスト１２１，移動ブロックリスト１２２，使用元リスト１２３及び削除ブロックリスト１２４を、順次更新することにより、移動データファイルを決定する。
【００４６】
これらの低カウントブロックリスト１２１，移動ブロックリスト１２２，使用元リスト１２３及び削除ブロックリスト１２４は、例えば、ＲＡＭ１２に記憶される。又、再分散データ選択部２２は、インデックステーブル２５０ｃの更新も行なう。
低カウントブロックリスト１２１は、移動させるデータファイルを選択するに際して、移動先ノードへ優先的に移動させるデータブロック（移動データブロック）の識別情報（例えば、インデックス）の一覧である。再分散データ選択部２２（移動データブロック選択部）は、この低カウントブロックリスト１２１に、優先移動データブロックとして、そのデータブロックを使用するデータファイルの数が少ないデータブロックを優先的に選択する。すなわち、低カウントブロックリスト１２１には、データファイルによる共用数が少ないデータブロックが優先的に登録される。
【００４７】
具体的には、再分散データ選択部２２は、インデックステーブル２５０ｃにおいてカウント値が少ない（例えば、カウント値＝１の）データブロックを抽出して、そのインデックスを、この低カウントブロックリスト１２１に登録する。
移動ブロックリスト１２２は、データファイルの移動に伴い、移動先ノードに記憶されるべきデータブロックの一覧である。使用元リスト１２３は、移動ブロックリスト１２２に登録されているデータブロックを備えるデータファイルの一覧である。削除ブロックリスト１２４は、データファイルの移動に伴い、移動元ノードから削除可能なデータブロックの一覧である。これらの移動ブロックリスト１２２及び削除ブロックリスト１２４にも、データブロックの識別情報（例えば、インデックス）が登録される。以下、これらのリストにデータブロックのインデックスを登録（設定）することを、単にデータブロックを登録すると表現する。
【００４８】
再分散データ選択部２２は、図１に示すように、移動データブロック選択部２３，移動データファイル選択部２４，移動データブロック追加部２５及び削除データブロック選択部２６としての機能をそなえる。
移動データブロック選択部２３は、低カウントブロックリスト１２１に登録された優先移動データブロックを、その先頭から順番に移動データブロックとして選択し、移動ブロックリスト１２２に登録する。
【００４９】
移動データファイル選択部２４は、インデックステーブル２５０ｃのリファーを参照し、選択した優先移動データブロックを備える（使用する）データファイルを移動データファイルとして選択し、この選択した移動データファイルを、使用元リスト１２３に登録する。
移動データブロック追加部２５は、選択した移動データファイルに備えられる全てのデータブロックを移動データブロックとして選択し、移動ブロックリスト１２２に登録する。
【００５０】
削除データブロック選択部２６は、移動ブロックリスト１２２に登録した各移動データブロックについて、その移動データブロックを備える全てのデータファイルが使用元リスト１２３に登録されているか否かを判断する。かかる判断は、例えば、インデックステーブル２５０ｃのリファー等を参照することにより行なう。
削除データブロック選択部２６は、その移動データブロックを備える全てのデータファイルが使用元リスト１２３に登録されたことを確認すると、その移動データブロックを削除データブロックとして選択し、削除ブロックリスト１２４に登録する。
【００５１】
再分散データ選択部２２（移動データファイル選択部２４，移動データブロック追加部２５及び削除データブロック選択部２６）は、移動ブロックリスト１２２に登録されている全ての移動データブロックについて、これらの確認や、各リストの更新を行なう。
そして、削除ブロックリスト１２４に登録された削除データブロックの合計データサイズが以下の条件（ａ）及び条件（ｂ）の２つの条件（データ移動条件）を満たす場合における、使用元リスト１２３に登録されているデータファイルが、移動データファイルとなる。又、その時点において、移動ブロックリスト１２２に登録されているデータブロックが移動先ノードに格納され、削除ブロックリスト１２４に登録されているデータブロックが、移動元ノードから削除される。これにより移動元ノードから移動先ノードへの移動データファイルの移動が実現される。
【００５２】
データ移動条件は以下のとおりである。
条件（ａ）：削除ブロックリスト１２４に登録された削除データブロックの合計データサイズが所定の削除サイズであること。
ここで、削除サイズは、管理サーバ３０から通知された目標データ移動量（Xbyte）に基づいて設定するデータサイズであり、例えば、目標データ移動量に対して所定の許容範囲（±α％）を付加した、ある程度の幅を持たせた値を用いることが望ましい。
【００５３】
この条件（ａ）を満たすことにより、管理サーバ３０からの目標データ移動量に相当するデータファイルの移動指示をほぼ満たすことが可能となる。
条件（ｂ）：削除ブロックリスト１２４に登録された削除データブロックの合計データサイズに対する、移動ブロックリスト１２２に登録された移動データブロックの合計データサイズの割合が所定の閾値（第１閾値：例えば、１．２倍）以下であること。
【００５４】
この条件（ｂ）を満たすことにより、移動元ノードにおいて削除データブロックを削除することにより得られるデータ削除量に対して、移動先ノードにおいて移動データブロックを格納することにより生じるデータ増加量が多すぎる、不均衡な状態となることを阻止することができる。すなわち、移動元ノードと移動先ノードとの間で増減するデータ量のバランスがとれた、効率的なデータ移動を実現することができる。
【００５５】
また、再分散データ選択部２２は、移動データファイルの選択時に、削除ブロックリスト１２４内の削除データブロックの合計サイズが、所定の閾値（第２閾値）以上であるか否かの検知を行なう。
第２閾値は、任意に設定することができ、例えば、目標データ移動量の１．５倍の値を用いる等、適宜設定される。
【００５６】
削除データブロックの合計サイズが第２閾値以上である場合には、移動元ノードから移動先ノードへ使用元リスト１２３のデータファイルを移動させても、データ量の均一化という効果を奏することができないと判断される。再分散データ選択部２２は、低カウントブロックリスト１２１から他の優先移動データブロックを選択しなおして、再度、移動データファイルの選択を行なう。
【００５７】
データ再分散部２７は、再分散データ選択部２２によって選択された移動データファイルを移動元ノードから移動先ノードへ移動させる。データ再分散部２７は、前述した削除ブロックリスト１２４に登録された削除データブロックの合計データサイズが上記（ａ）及び（ｂ）の２つの条件を満たす場合に、使用元リスト１２３に登録されている移動データファイルを、移動元ノードから移動先ノードへ移動させる。
【００５８】
具体的には、移動ブロックリスト１２２に登録された移動データブロックを移動先ノードへ送信して、当該移動先ノードの記憶装置１４に格納させる。又、データ再分散部２７は、移動元ノード、すなわち、当該ストレージサーバノード１０の記憶装置１４から、削除ブロックリスト１２４に登録されている削除データブロックを削除する。
データ再分散部２７は、移動データファイルの構成情報（データファイル構成情報２５０ｂ）やそのデータファイルの存在位置を表す情報等も移動先ノードに格納させる。
【００５９】
（Ｂ）動作
上述の如く構成された実施形態の一例としての分散ストレージシステム１におけるデータファイル移動時の全体的な処理を、図５に示すフローチャート（ステップＡ１０〜Ａ３０）に従って説明する。
本分散ストレージシステム１において、管理サーバ３０は、各ストレージサーバノード１０間からそれぞれ通知されたデータ量に基づき、ストレージサーバノード１０間でデータ量の偏りが生じているか否かを判断する（ステップＡ１０）。
【００６０】
ストレージサーバノード１０間でデータ量の偏りが発生していることを検知すると、管理サーバ３０は、次に、データファイルの移動元ノード及び移動先ノードを決定するとともに、目標データ移動量を決定する（ステップＡ２０）。管理サーバ３０は、移動元ノードに対して、移動先ノード及び目標データ移動量を通知して、データファイルの移動を指示する。
【００６１】
移動元ノードにおいては、移動先ノードへ移動する移動データファイルの選択を行ない、この選択した移動データファイルを移動先ノードに移動させ（ステップＡ３０）、処理を終了する。
次に、実施形態の一例としての分散ストレージシステム１における再分散データ選択部２２によるデータファイルの移動処理を、図６に示すフローチャート（ステップＳ１０〜Ｓ１５０）に従って説明する。なお、以下に示す例においては、変数seed及び変数ｎを用いる。
【００６２】
再分散データ選択部２２（移動データブロック選択部２３）は、ｎに１を設定（ｎ＝１）して初期化を行なった後（ステップＳ１０）、インデックステーブル２５０ｃを参照して、カウンタの値がｎであるデータブロックを抽出し、優先移動データブロックとして低カウントブロックリスト１２１に登録する（ステップＳ２０）。
移動データブロック選択部２３は、低カウントブロックリスト１２１にデータブロックが登録されているか否か、すなわち、低カウントブロックリスト１２１が空であるか否かを確認する（ステップＳ３０）。  
【００６３】
低カウントブロックリスト１２１が空である場合には（ステップＳ３０のＹＥＳルート参照）、ｎをインクリメント（ｎ＝ｎ＋１）した後（ステップＳ１３０）、ｎが所定の閾値（第３閾値）を超えたか否かを確認する（ステップＳ１４０）。
ここで、第３閾値は、予め任意に設定される値である。この第３閾値を設定することにより、使用元のデータファイルの数がこの第３閾値を超えるデータブロックについては、当該データブロックを備えるデータファイルの移動先への移動を抑止する。
【００６４】
本分散ストレージシステム１においては、使用元のデータファイルの数が多いデータブロックを移動先ノードへ移動させる場合には、そのデータブロックを使用する全てのデータファイルを移動先ノードへ移動させる。これらの全てのデータファイルを移動先ノードへ移動させると、ストレージサーバノード１０間で新たなデータの偏りが生じるおそれがあり非効率的である。
【００６５】
そこで、使用元のデータファイルの数がこの第３閾値を超えるデータブロックについては、当該データブロックを備えるデータファイルの移動先への移動を抑止することにより、効率的にデータファイルの移動を行なうことができる。
ｎが第３閾値を超えていない場合には（ステップＳ１４０のＮＯルート参照）、ステップＳ２０に戻る。又、ｎが第３閾値を超えた場合には（ステップＳ１４０のＹＥＳルート参照）、移動させるデータファイルがない（解なし）と判断し（ステップＳ１５０）、処理を終了する。
【００６６】
一方、低カウントブロックリスト１２１が空でない場合には（ステップＳ３０のＮＯルート参照）、変数seedに低カウントブロックリスト１２１の先頭の優先移動データブロックを設定する。又、このseedに設定した優先移動データブロックを低カウントブロックリスト１２１から削除する（ステップＳ４０）。
移動データブロック選択部２３は、移動ブロックリスト１２２にseedに設定されている優先移動データブロックを登録する。又、移動データファイル選択部２４は使用元リスト１２３を、又、削除データブロック選択部２６は削除ブロックリスト１２４をそれぞれ空にして初期化する（ステップＳ５０）。
【００６７】
移動データファイル選択部２４は、移動ブロックリスト１２２の各データブロックに対して、当該データブロックを備えるデータファイルを使用元リスト１２３に登録する（ステップＳ６０）。
再分散データ選択部２２は、使用元リスト１２３に新たなデータファイルが追加されたか否かを確認し（ステップＳ７０）、新たなデータファイルが追加されていない場合には（ステップＳ７０のＮＯルート参照）、ステップＳ３０に戻る。
【００６８】
使用元リスト１２３に新たなデータファイルが追加された場合には（ステップＳ７０のＹＥＳルート参照）、移動データブロック追加部２５は、この使用元リスト１２３に新たに追加されたデータファイルに対して、当該データファイルに備えられるデータブロックであって、移動ブロックリスト１２２に未登録のデータブロックを、移動ブロックリスト１２２に登録する（ステップＳ８０）。
【００６９】
次に、削除データブロック選択部２６は、移動ブロックリスト１２２の各データブロックについて、そのデータブロックを使用する全ての使用元のデータファイルが使用元リスト１２３に登録されたことを確認すると、当該データブロックを削除ブロックリスト１２４に登録する（ステップＳ９０）。使用元リスト１２３の全てのデータファイルを移動先ノードに移動させることにより、移動元ノードにおいては当該データブロックを使用するデータファイルはなくなるので、当該データブロックを移動元ノードから削除することができる。
【００７０】
データ再分散部２７は、削除ブロックリスト１２４に登録された削除データブロックの合計データサイズが、前述した条件（ａ）及び条件（ｂ）の２つのデータ移動条件を満たすか否かを確認する（ステップＳ１００）。すなわち、削除データブロックの合計データサイズが所定の削除サイズであり（条件（ａ））、且つ、削除データブロックの合計データサイズに対する移動データブロックの合計データサイズの割合が第１閾値以下であるか（条件（ｂ））を確認する。
【００７１】
ステップＳ１００のデータ移動条件が満たされる場合には（ステップＳ１００のＹＥＳルート参照）、データ再分散部２７は、使用元リスト１２３に登録されているデータファイルを、移動元ノードから移動先ノードへ移動させる（ステップＳ１１０）。すなわち、移動ブロックリスト１２２の移動データブロックを移動先ノードへ格納させ、又、移動元ノードから削除ブロックリスト１２４の削除データブロックを削除する。その後、処理を終了する。
【００７２】
一方、ステップＳ１００のデータ移動条件が満たされない場合には（ステップＳ１００のＮＯルート参照）、再分散データ選択部２２は、削除ブロックリスト１２４内の削除データブロックの合計サイズが、第２閾値以上であるか否かを確認する（ステップＳ１２０）。
削除ブロックリスト１２４内の削除データブロックの合計サイズが第２閾値未満である場合には（ステップＳ１２０のＮＯルート参照）、ステップＳ６０に戻る。又、削除ブロックリスト１２４内の削除データブロックの合計サイズが第２閾値以上である場合には（ステップＳ１２０のＹＥＳルート参照）、ステップＳ３０に戻る。
【００７３】
削除データブロックの合計サイズが第２閾値以上である場合には、当該優先移動データブロックについては、移動先ノードへの移動を行なう場合に、当該優先移動データブロックに伴って移動させる必要のあるデータブロックが多すぎ、データ量の均等化の効果が得られないと判断される。
（Ｃ）実施例
以下に、図６に示したフローチャートに従って、本分散ストレージシステム１の再分散データ選択部２２による移動させるデータファイルの選択処理過程を例示する。
【００７４】
以下に示す例においては、図３に示すデータファイル（ファイルＡ，ファイルＢ，ファイルＣ）及び図４に示すインデックステーブル２５０ｃをそなえた移動元ノードにおける、移動先ノードへ移動させるデータファイルの選択手法を説明する。
ファイルＡ，ファイルＢ及びファイルＣは、それぞれ重複除去が行なわれ、ファイルＡはインデックス01,02,03,04,05のデータブロックで構成される。又、ファイルＢはインデックス05,06,02,03,04のデータブロックで構成され、ファイルＣはインデックス07,08,09のデータブロックで構成される。又、インデックス01,02,03,04,05のデータブロックの各データサイズは4KBであるものとする。
【００７５】
（Ｃ−１）第１例
先ず、目標データ移動量が20KB（X＝20K）である例について示す。
（１）ｎ＝１（図６のステップＳ１０参照）
（２）移動データブロック選択部２３が、インデックステーブル２５０ｃにおいて、カウンタ値がｎであるデータブロックを抽出し、低カウントブロックリスト１２１を作成する（図６のステップＳ２０参照）。
例：低カウントブロックリスト１２１には、インデックス01,07,08がこの順で登録される。
【００７６】
（３）再分散データ選択部２２は、低カウントブロックリスト１２１の各優先移動データブロック（要素）に対して、以下の処理を行なう。なお、以下に示す例においては、移動ブロックリスト１２２，使用元リスト１２３及び削除ブロックリスト１２４の各エントリを、移動ブロックリスト１２２，使用元リスト１２３及び削除ブロックリスト１２４の順で並べたカッコ“()”内にそれぞれ示す。又、このカッコ中においては、ファイルＡ，ファイルＢ及びファイルＣを、それぞれFileA，FileB及びFileCと表す。
【００７７】
（３−１）移動データファイル選択部２４が、移動ブロックリスト１２２の各データブロックについて、当該データブロックを使用しているデータファイルを使用元リスト１２３に登録する（図６のステップＳ６０参照）。新たに使用元リスト１２３に入るデータファイルがない場合は（図６のステップＳ７０のＮＯルート参照）、低カウントブロックリスト１２１の次の要素に移る。
例：(01)(FileA)()
（３−２） 移動データブロック追加部２５が、使用元リスト１２３に新たに入ったファイルに対して、当該データファイルが備えるデータブロックで、移動ブロックリスト１２２に登録されていないものを移動ブロックリスト１２２に追加する（図６のステップＳ８０参照）。
例：(01,02,03,04,05)(FileA)()
（３−３）削除データブロック選択部２６が、 移動ブロックリスト１２２の各データブロックについて、当該データブロックを使用している全てのデータファイル（使用元）が使用元リスト１２３に登録されたら、そのデータブロックを削除ブロックリスト１２４に登録する（図６のステップＳ９０参照）。
例：(01,02,03,04,05)(FileA)(01)
（３−４） 削除ブロックリスト１２４内のデータブロックの合計サイズが所望の削除サイズであり、移動ブロックリスト１２２の合計サイズ（移動量）が削除ブロックリスト１２４の合計サイズ（削除量）に対する比が第１閾値（例えば1.2倍）以下であるか確認する（図６のステップＳ１００参照）。かかる移動条件を満たす場合に（図６のステップＳ１００のＹＥＳルート参照）、データ再分散部２７が、移動ブロックリスト１２２のデータブロックを移動先ノードに生成するとともに、削除ブロックリスト１２４のデータブロックを移動元ノードから削除する。これにより、使用元リスト１２３のファイルを移動元ノードから移動先ノードに移動させる（図６のステップＳ１１０参照）。
例：移動元ノードでのデータ削除量（削除量）=4KB
移動先ノードでのデータ増加量（移動量）=20KB
本例においては移動条件を満たさない。
【００７８】
（３−５）削除ブロックリスト１２４内のデータブロックの合計サイズが第２閾値（例えば、目標データ移動量の1.5倍）以上であれば、当該優先移動データブロックについての処理を終了する（図６のステップＳ１２０参照）。
例：4＜20×1.5
（３−６）上記（３−５）に示す例においては、削除ブロックリスト１２４内のデータブロックの合計サイズが第２閾値（例えば、目標データ移動量の1.5倍）以上でないので（図６のステップＳ１２０のＮＯルート参照）、上記（３−１）へ戻る。
【００７９】
（３−１′）移動データファイル選択部２４が、移動ブロックリスト１２２の各データブロックについて、当該データブロックを使用しているデータファイルを使用元リスト１２３に登録する（図６のステップＳ６０参照）。
例：(01,02,03,04,05)(FileA, FileB)(01)
（３−２′）上記（３−１′）に示す例においては、使用元リスト１２３に新たにファイルＢが登録されたので、移動データブロック追加部２５が、使用元リスト１２３に新たに入ったファイルに対して、当該データファイルが備えるデータブロックで、移動ブロックリスト１２２に登録されていないものを移動ブロックリスト１２２に追加する（図６のステップＳ８０参照）。
例：(01,02,03,04,05,06)(FileA, FileB)(01)
（３−３′） 移動ブロックリスト１２２の各データブロックについて、当該データブロックを使用している全てのデータファイル（使用元）が使用元リスト１２３に登録されたら、削除データブロック選択部２６が、そのデータブロックを削除ブロックリスト１２４に登録する（図６のステップＳ９０参照）。
例：(01,02,03,04,05,06)(FileA, FileB)(01,02,03,04,05)
（３−４′） 削除ブロックリスト１２４内のデータブロックの合計サイズが所望の削除サイズであり、移動ブロックリスト１２２の合計サイズ（移動量）と削除ブロックリスト１２４の合計サイズ（削除量）との比が第１閾値（例えば1.2倍）以下であるか確認する（図６のステップＳ１００参照）。
例：移動元ノードでのデータ削除量（削除量）=20KB
移動先ノードでのデータ増加量（移動量）=24KB
本例においては、移動量／削除量が移動条件を満たすので（図６のステップＳ１００のＹＥＳルート参照）、データ再分散部２７が、移動ブロックリスト１２２のデータブロック（01,02,03,04,05,06）を移動先ノードに生成するとともに、削除ブロックリスト１２４のデータブロック（01,02,03,04,05）を移動元ノードから削除する。これにより、使用元リスト１２３のファイルＡ及びファイルＢを移動元ノードから移動先ノードに移動させる（図６のステップＳ１１０参照）。その後、処理を終了する。
【００８０】
（Ｃ−２）第２例
次に、目標データ移動量が8KB（X＝8K）である例について示す。又、優先移動データブロックとしてインデックス07を最初に選択する場合について例示する。
本例においても、各データブロックのデータサイズは4KBであるものとする。
（１）ｎ＝１（図６のステップＳ１０参照）
（２）移動データブロック選択部２３が、インデックステーブル２５０ｃにおいて、カウンタ値がｎであるデータブロックを抽出し、低カウントブロックリスト１２１を作成する図６のステップＳ２０参照）。
例：低カウントブロックリスト１２１には、インデックス07,06,08がこの順で登録される。
【００８１】
（３）再分散データ選択部２２は、低カウントブロックリスト１２１の各優先移動データブロック（要素）に対して、以下の処理を行なう。
（３−１）移動データファイル選択部２４が、移動ブロックリスト１２２の各データブ
ロックについて、当該データブロックを使用しているデータファイルを使用元リスト１２３に登録する（図６のステップＳ６０参照）。新たに使用元リスト１２３に入るデータファイルがない場合は（図６のステップＳ７０のＮＯルート参照）、低カウントブロックリスト１２１の次の要素に移る。
例：(07)(FileC)()
（３−２）移動データブロック追加部２５が、 使用元リスト１２３に新たに入ったフ
ァイルに対して、当該データファイルが備えるデータブロックで、移動ブロックリスト１２２に登録されていないものを移動ブロックリスト１２２に追加する（図６のステップＳ８０参照）。
例：(07,06,08)(FileC)()
（３−３）削除データブロック選択部２６が、 移動ブロックリスト１２２の各データ
ブロックについて、当該データブロックを使用している全てのデータファイル（使用元）が使用元リスト１２３に登録されたら、そのデータブロックを削除ブロックリスト１２４に登録する（図６のステップＳ９０参照）。
例：(07,06,08)(FileC)( 07,08)
（３−４） 削除ブロックリスト１２４内のデータブロックの合計サイズが所望の削除
サイズであり、移動ブロックリスト１２２の合計サイズ（移動量）が削除ブロックリスト１２４の合計サイズ（削除量）に対する比が第１閾値（例えば1.2倍）以下であるか確認
する（図６のステップＳ１００参照）。かかる移動条件を満たす場合に（図６のステップＳ１００のＹＥＳルート参照）、データ再分散部２７が、移動ブロックリスト１２２のデータブロックを移動先ノードに生成するとともに、削除ブロックリスト１２４のデータブロックを移動元ノードから削除する。これにより、使用元リスト１２３のファイルを移動元ノードから移動先ノードに移動させる（図６のステップＳ１１０参照）。
例：移動元ノードでのデータ削除量（削除量）=8KB
移動先ノードでのデータ増加量（移動量）=12KB
本例においては移動条件を満たさない。
【００８２】
（３−５）削除ブロックリスト１２４内のデータブロックの合計サイズが第２閾値（例えば、目標データ移動量の1.5倍）以上であるか確認する。
例：8＜12×1.5
（３−６）上記（３−５）に示す例においては、削除ブロックリスト１２４内のデータブロックの合計サイズが第２閾値（例えば、目標データ移動量の1.5倍）以上でないので（図６のステップＳ１２０のＮＯルート参照）、上記（３−１）へ戻る。
【００８３】
（３−１′）移動データファイル選択部２４が、移動ブロックリスト１２２の各データブロックについて、当該データブロックを使用しているデータファイルを使用元リスト１２３に登録する（図６のステップＳ６０参照）。
例：(07,06,08)(FileC,FileB)(07,08)
（３−２′）上記（３−１′）に示す例においては、使用元リスト１２３に新たにファイルＢが登録されたので、移動データブロック追加部２５が、使用元リスト１２３に新たに入ったファイルに対して、当該データファイルが備えるデータブロックで、移動ブロックリスト１２２に登録されていないものを移動ブロックリスト１２２に追加する（図６のステップＳ８０参照）。
例：(07,06,08,05,02,03,04)(FileC, FileB)(07,08) 
（３−３′） 移動ブロックリスト１２２の各データブロックについて、当該データブロックを使用している全てのデータファイル（使用元）が使用元リスト１２３に登録されたら、削除データブロック選択部２６が、そのデータブロックを削除ブロックリスト１２４に登録する（図６のステップＳ９０参照）。
例：(07,06,08,05,02,03,04)(FileC, FileB)(07,08,06)
（３−４′） 削除ブロックリスト１２４内のデータブロックの合計サイズが所望の削除サイズであり、移動ブロックリスト１２２の合計サイズ（移動量）と削除ブロックリスト１２４の合計サイズ（削除量）との比が第１閾値（例えば1.2倍）以下であるか確認する（図６のステップＳ１００参照）。
例：移動元ノードでのデータ削除量（削除量）=12KB
移動先ノードでのデータ増加量（移動量）=28KB
本例においては、移動量／削除量が移動条件を満たさない（図６のステップＳ１００のＮＯルート参照）。
【００８４】
（３−５′）削除ブロックリスト１２４内のデータブロックの合計サイズが第２閾値（例えば、目標データ移動量の1.5倍）以上であるか確認する（図６のステップＳ１２０参照）。本例においては、12＝8×1.5であり、最終的に解を発見できずに処理を終了する。
（Ｄ）効果
本分散ストレージシステム１によれば、各ストレージサーバノード１０において、再分散データ選択部２２が、移動先ノードに移動させるデータファイルを選択し、データ再分散部２７が、選択したデータファイルを構成するデータブロックを移動先ノードに移動させる。特に、移動ブロックリスト１２２の移動データブロックを使用する全データファイルが移動データファイルとして登録されると、移動ブロックリスト１２２の移動データブロックを移動先ノードに格納し、削除ブロックリスト１２４の削除データブロックを移動元ノードから削除する。これにより、複数のストレージサーバノード１０間において、データ量を均等化させることができる。
【００８５】
また、本分散ストレージシステム１においては、各ストレージサーバノード１０において、重複除去部２１が重複排除処理を実現するので、各ストレージサーバノード１０に格納するデータ量を削減し、記憶装置１４の記憶領域を効率的に使用することができる。すなわち、各ストレージサーバノード１０において重複排除を行ないながら、これらのストレージサーバノード１０間でデータ量の均等化を実現することができる。
【００８６】
ここで、従来の分散ストレージシステムに重複除去を適用し、データ再配置を行なう場合について考える。
図７（ａ），（ｂ）は従来の重複排除手法を説明する図であり、（ａ）はファイル構成を例示する図、（ｂ）は（ａ）に示す各データファイルに重複排除を行なった状態を例示する図である。
【００８７】
図７（ａ），（ｂ）に示す例において、ファイルＡはインデックス01,02,03,04,05で表されるデータブロックを備えている。同様に、ファイルＢはインデックス05,06,02,03,04で表されるデータブロックを、又、ファイルＣは、インデックス07,06,08で表されるデータブロックを、それぞれ備えている。各データブロックのデータサイズはそれぞれ4KBであるものとする。
【００８８】
図７（ａ）に示す総データ量52KBのファイルＡ，Ｂ，Ｃを重複除去することにより、図７（ｂ）に示すように、32KBとインデックステーブル（αKB）との合計（32＋α）KB程度までデータサイズを削減することができる。
従来の分散ストレージシステムにおいて、図７（ｂ）に示すような重複除去状態にある各データファイルを再配置の対象として選択して移動先ノードに単純に移動させると、効率的にデータ分散を行なうことができない。
【００８９】
例えば、図７（ｂ）の例において、ファイルＡを移動先ノードに移動させる場合に、移動先ノードにおいては、インデックス01,02,03,04,05で表されるデータブロックが新たに格納されることにより20KBのデータ量が増加する。
一方、移動元ノードにおいては、インデックス02,03,04,05で表されるデータブロックは、他のファイルＢ，Ｃによっても使用されているので、これらのデータブロックを移動元ノードから削除することはできない。従って、移動元ノードにおいては、データファイルＡによってのみ使用されるインデックス01のデータブロックのみを削除することができ、データファイルＡを移動させることにより4KBのデータ量が削減される。
【００９０】
同様に、ファイルＢを移動先ノードに移動させる場合においても、移動先ノードにおいては、インデックス05,06,02,03,04で表されるデータブロックが新たに格納されることにより20KBのデータ量が増加する。その一方で、インデックス05,06,02,03,04で表されるデータブロックは、それぞれファイルＡもしくはファイルＢによっても使用されているので、これらのデータブロックを移動元ノードから削除することはできない。すなわち、移動元ノードにおいては、データファイルＢを移動させることにより削減されるデータ量は0KBとなる。
【００９１】
このように、従来の分散ストレージシステムに重複排除を適用した場合には、データファイルを移動元ノードから移動先ノードへ移動させるデータ再配置を行なっても、移動元ノードでデータ削減を行なうことができず、データ再配置によるデータ量の均一化を実現できない。又、データ再配置を行なうことにより、結果的に、分散ストレージシステム全体でのデータ量が増大し、重複排除による効果を阻害することにもなる。
【００９２】
なお、重複除去のインデックスをストレージサーバノード間で共有して構成する方法も考えられるが、複数のストレージサーバノード間でインデックスを共用／管理することにより処理性能の低下が生じ、分散ストレージとしてのメリットを活かすことができない。
本分散ストレージシステム１においては、各ストレージサーバノード１０において、重複除去部２１による重複除去処理を実現しながら、ストレージサーバノード１０間でデータ量の均等化を実現することができる。
【００９３】
また、本分散ストレージシステム１によれば、低カウントブロックリスト１２１に、優先移動データブロックとしてカウンタ値が少ないデータブロックを優先的に登録し、低カウントブロックリスト１２１に登録されたデータブロックを用いるデータファイルを移動させるデータファイルとして選択する。これにより、データファイルの移動によるデータ量の均等化を効率的に実現することができる。
【００９４】
また、データ再分散部２７は、条件（ａ），（ｂ）からなるデータ移動条件を満たす場合に、使用元リスト１２３のデータファイルを移動元ノードから移動先ノードへ移動させる。
ここで、削除データブロックの合計データサイズが所定の削除サイズであることを規定する条件（ａ）を満たすことにより、管理サーバ３０からの目標データ移動量に相当するデータファイルの移動指示をほぼ満たすことが可能となる。
【００９５】
また、削除データブロックの合計データサイズに対する、移動データブロックの合計データサイズの割合が所定の第１閾値以下であることを規定する条件（ｂ）を満たすことにより、移動元ノードと移動先ノードとの間で増減するデータ量のバランスがとれた、効率的なデータ移動を実現することができる。
（Ｅ）その他
そして、開示の技術は上述した実施形態に限定されるものではなく、本実施形態の趣旨を逸脱しない範囲で種々変形して実施することができる。本実施形態の各構成及び各処理は、必要に応じて取捨選択することができ、あるいは適宜組み合わせてもよい。
【００９６】
例えば、上述した実施形態においては、管理サーバ３０（データ量管理プロセス）が、保持するデータ量が平均値よりも少なく、且つ、保持するデータ量と平均値との差が所定の閾値以上であるストレージサーバノード１０を移動先ノードとして決定している。又、算出した平均値と移動先ノードが保持するデータ量との差（Xbyte）を目標データ移動量として設定している。しかしながら、これに限定されるものではない。
【００９７】
例えば、保持するデータ量が平均値よりも多く、且つ、保持するデータ量と平均値との差が所定の閾値以上であるストレージサーバノード１０を移動元ノードとして決定してもよい。そして、算出した平均値と移動元ノードが保持するデータ量との差（Xbyte）を目標データ移動量として設定してもよい。この場合、例えば、全ストレージサーバノード１０のうち保持するデータ量が最も少ないストレージサーバノード１０を移動先ノードとして決定することが望ましい。
【００９８】
また、例えば、管理サーバ３０が移動先ノードや移動元ノード及び目標データ移動量を決定する代わりに、各ストレージサーバノード１０において、これらの移動先ノードや移動元ノード及び目標データ移動量を決定してもよい。
具体的には、例えば、各ストレージサーバノード１０間において、各自が保持するデータ量を相互に通知し合い、互いに他のストレージサーバノード１０が保持するデータ量を把握する。そして、全ストレージサーバノード１０のデータ量の平均値をそれぞれ算出し、自身の保持するデータ量との差が所定の閾値以上となると、データの偏りを検知してもよい。
【００９９】
この場合において、当該データの偏りを検知したストレージサーバノード１０が保持するデータ量が、全ストレージサーバノード１０の平均値よりも多い場合には、当該ストレージサーバノード１０が移動元ノードとなる。又、当該データの偏りを検知したストレージサーバノード１０が保持するデータ量が、全ストレージサーバノード１０の平均値よりも少ない場合には、当該ストレージサーバノード１０が移動先ノードとなる。又、例えば、算出した平均値と自身が保持するデータ量との差を目標データ移動量として設定することが望ましい。
【０１００】
また、上述した開示により本実施形態を当業者によって実施・製造することが可能である。
【符号の説明】
【０１０１】
１    分散ストレージシステム
１０，１０−１〜１０−６    ストレージサーバノード（ストレージ装置，移動制御装置）
１１    ＣＰＵ
１２    ＲＡＭ
１３    ＲＯＭ
１４    記憶装置
２１    重複除去部
２２    再分散データ選択部
２３    移動ブロック選択部（移動データブロック選択部）
２４    移動ファイル選択部（移動データファイル選択部）
２５    移動ブロック追加部（移動データブロック追加部）
２６    削除ブロック選択部（削除データブロック選択部））
２７    データ再分散部
３０    管理サーバ
４０    プロキシサーバ
５０    ＬＡＮ
５１    ネットワーク
６０    クライアント
１２１    低カウントブロックリスト
１２２    移動ブロックリスト
１２３    使用元リスト
１２４    削除ブロックリスト
２４０    ファイル情報
２５０    重複排除情報
２５０ａ    ＦＰ情報
２５０ｂ    データファイル構成情報
２５０ｃ    インデックステーブル
【図１】
0005867206.tif 000002
【図２】
0005867206.tif 000003
【図３】
0005867206.tif 000004
【図４】
0005867206.tif 000005
【図５】
0005867206.tif 000006
【図６】
0005867206.tif 000007
【図７】
0005867206.tif 000008