(57)【特許請求の範囲】
【請求項１】
互いに隣接し部分的に重複するトラック群を含むバンドを書き込み単位とする瓦記録装置と、
前記バンドのバンド識別情報と、前記バンドに格納されたデータが参照されなくなる可能性を示す特性情報と、前記バンドに前記データが格納された場合の前記データのデータ識別情報と、を互いに関連付ける管理情報、を管理する管理部と、
前記瓦記録装置に対して前記データの格納が要求された場合に、前記データの有効期限と、前記特性情報と、前記瓦記録装置の空きバンドの残り容量と所定期間における書き込み量から求められる前記空きバンドがなくなると予測されるタイミングとに基づいて、前記データの前記有効期限が前記タイミングよりも前か否かで格納先を分けることにより、前記データを格納する前記バンドを選択する選択部と、
前記データを、前記選択されたバンドに格納する実行部と、
を具備する、
ストレージ装置。
【請求項２】
前記バンドに格納された前記データの前記有効期限が経過した場合に、前記データを削除する削除部をさらに具備する、
請求項１のストレージ装置。
【請求項３】
前記選択部は、前記タイミングを経過した場合に、新たなデータに対して前記バンドを選択し、
前記実行部は、前記新たなデータを、前記選択されたバンドに格納する、
請求項１のストレージ装置。
【請求項４】
前記特性情報は、増設瓦記録装置が増設された場合に移動されることを示す情報を含み、
前記増設瓦記録装置が増設された場合に、前記特性情報に基づいて、前記バンドに格納されている前記データを前記瓦記録装置から読み出し、前記増設瓦記録装置に格納する増設格納部と、
前記増設格納部によって前記データが読み出された後に、前記データを前記バンドから削除する増設削除部と、
をさらに具備する請求項１のストレージ装置。
【請求項５】
前記選択部は、前記増設瓦記録装置が増設された場合に、前記データの前記有効期限と、前記増設瓦記録装置のバンドの特性情報と、前記増設瓦記録装置の空きバンドの残り容量と前記増設瓦記録装置の所定期間における書き込み量から求められる前記増設瓦記録装置の空きバンドがなくなると予測される前記増設瓦記録装置に関するタイミングとに基づいて、前記データの前記有効期限が前記増設瓦記録装置に関するタイミングよりも前か否かで前記増設瓦記録装置の格納先を分けることにより、前記データを格納する前記増設瓦記録装置のバンドを選択し、
前記増設格納部は、前記増設瓦記録装置の前記選択されたバンドに、前記データを格納する、
請求項４のストレージ装置。
【請求項６】
前記管理情報は、前記データの更新履歴を含み、
前記特性情報は、前記バンドへの格納を許可する条件として、更新履歴ありが設定されていることを示す情報を含み、
前記選択部は、前記更新履歴と前記特性情報とに基づいて、前記データが更新されている場合に、前記バンドを選択する、
請求項１のストレージ装置。
【請求項７】
前記特性情報は、前記バンドへの格納を許可する条件が所定のデータサイズ以下であることを示す情報を含み、
前記選択部は、前記データのサイズと前記特性情報とに基づいて、前記データのサイズが前記所定のデータサイズ以下の場合に、前記バンドを選択する、
請求項１のストレージ装置。
【請求項８】
前記データが格納される場合に、前記データを複数のデータ断片と冗長情報とに分割する分割部と、
前記複数のデータ断片が読み出され、前記複数のデータ断片のいずれかに異常がある場合に、前記冗長情報に基づいて、前記複数のデータ断片を復元する復元部と、
前記復元部から受けた前記複数のデータ断片を結合する結合部と、
をさらに具備し、
前記管理情報の前記データ識別情報は、データ断片識別情報であり、
前記特性情報は、前記バンドに格納されたデータ断片が参照されなくなる可能性を示す、
請求項１のストレージ装置。
【請求項９】
前記データが格納される場合に、前記データを複数のデータ断片に分割する分割部と、
前記複数のデータ断片が前記瓦記録装置から読み出された場合に、前記複数のデータ断片を結合する結合部と、
をさらに具備し、
前記管理情報の前記データ識別情報は、データ断片識別情報であり、
前記管理情報は、前記データ断片に基づいて算出される値と前記バンド識別情報とをさらに関連付けており、
前記特性情報は、前記バンドに格納されたデータ断片が参照されなくなる可能性を示し、
前記選択部は、前記管理情報に基づいて、前記データ断片を格納する前記バンドを選択する、
請求項１のストレージ装置。
【請求項１０】
コンピュータを、
互いに隣接し部分的に重複するトラック群を含むバンドを書き込み単位とする瓦記録装置を管理するための情報であり、前記バンドのバンド識別情報と、前記バンドに格納されたデータが参照されなくなる可能性を示す特性情報と、前記バンドに前記データが格納された場合の前記データのデータ識別情報と、を互いに関連付ける管理情報、を管理する管理部と、
前記瓦記録装置に対して前記データの格納が要求された場合に、前記データの有効期限と、前記特性情報と、前記瓦記録装置の空きバンドの残り容量と所定期間における書き込み量から求められる前記空きバンドがなくなると予測されるタイミングとに基づいて、前記データの前記有効期限が前記タイミングよりも前か否かで格納先を分けることにより、前記データを格納する前記バンドを選択する選択部と、
前記データを、前記選択されたバンドに格納する実行部と、
して機能させるためのストレージ装置の制御プログラム。
【請求項１１】
コントローラが、互いに隣接し部分的に重複するトラック群を含むバンドを書き込み単位とする瓦記録装置を管理するための情報であり、前記バンドのバンド識別情報と、前記バンドに格納されたデータが参照されなくなる可能性を示す特性情報と、前記バンドに前記データが格納された場合の前記データのデータ識別情報と、を互いに関連付ける管理情報、を管理すること、
前記コントローラが、前記瓦記録装置に対して前記データの格納が要求された場合に、前記データの有効期限と、前記特性情報と、前記瓦記録装置の空きバンドの残り容量と所定期間における書き込み量から求められる前記空きバンドがなくなると予測されるタイミングとに基づいて、前記データの前記有効期限が前記タイミングよりも前か否かで格納先を分けることにより、前記データを格納する前記バンドを選択すること、
前記コントローラが、前記データを、前記選択されたバンドに格納すること、
を具備するストレージ装置の制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本実施形態は、ストレージ装置、ストレージ装置の制御プログラム、及び、ストレージ装置の制御方法に関する。
【背景技術】
【０００２】
ハードディスクドライブ（以下、ＨＤＤと称する）の大容量化及び記録密度の向上のために、磁気ディスクのトラック幅を短縮し、トラック密度を増す技術がある。
【０００３】
さらに、磁気ディスクのトラック密度を向上させるために、隣接トラックが部分的に重ね書きされる程度までトラック幅を狭くする技術が提案されている。この技術は、瓦記録技術又はシングル記録技術と称される。当該瓦記録技術を用いた場合には、部分的に重ね書きされた隣接トラックのデータが、書き込み時に消失される。このため、複数のトラックをまとめたトラック群（以下、バンドと称する）単位で書き込みを行う必要がある。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特許第４８８６８７７号公報
【非特許文献】
【０００５】
【非特許文献１】Dennis Colarelli, Dirk Grunwald, “Massive Arrays of Idle Disks For Storage Archives”, pp.47, ACM/IEEE SC2002, Conference (SC 2002), 2002
【発明の概要】
【発明が解決しようとする課題】
【０００６】
瓦記録装置では、データの書き込みをバンド単位で行う必要があり、データ単位で書き込みを行う通常のＨＤＤよりも書き込み時間が増加する場合がある。また、瓦記録装置では、データが削除又は上書きなどで更新される場合に、更新されるデータを含むバンド単位で更新を行う必要があり、更新にかかる時間が増加する場合がある。
【０００７】
本実施形態は、以上のような実情に鑑みてなされたもので、瓦記憶装置に対する書き込み時間を抑制することを目的とする。
【課題を解決するための手段】
【０００８】
本実施形態によれば、ストレージ装置は、瓦記録装置、管理部、選択部、実行部を含む。瓦記録装置は、互いに隣接し部分的に重複するトラック群を含むバンドを書き込み単位とする。管理部は、バンドのバンド識別情報と、バンドに格納されたデータが参照されなくなる可能性を示す特性情報と、バンドにデータが格納された場合のデータのデータ識別情報と、を互いに関連付ける管理情報を管理する。選択部は、瓦記録装置に対してデータの格納が要求された場合に、データの有効期限と、特性情報と、瓦記録装置の空きバンドの残り容量と所定期間における書き込み量から求められる空きバンドがなくなると予測されるタイミングとに基づいて、データの有効期限がタイミングよりも前か否かで格納先を分けることにより、データを格納するバンドを選択する。実行部は、データを選択されたバンドに格納する。
【図面の簡単な説明】
【０００９】
【図１】第１の実施形態に係るストレージ装置の第１の例を示すブロック図。
【図２】第１の実施形態に係るストレージ装置の第２の例を示すブロック図。
【図３】第２の実施形態に係るストレージシステムの一例を示すブロック図。
【図４】コーディネータの構成の一例を示すブロック図。
【図５】ハッシュ値範囲テーブルの一例を示すデータ構造図。
【図６】要求処理部の処理の一例を示すフローチャート。
【図７】データノード決定処理の一例を示すフローチャート。
【図８】データノードに備えられるコントローラの構成の一例を示すブロック図。
【図９】キャッシュ記録装置に格納されているキャッシュ情報の一例を示すデータ構造図。
【図１０】キャッシュ処理部の処理の一例を示すフローチャート。
【図１１】瓦記録装置の一例を示す図。
【図１２】データバンドテーブルの一例を示すデータ構造図。
【図１３】ハッシュ値テーブルの一例を示すデータ構造図。
【図１４】要求実行部の処理の一例を示すフローチャート。
【図１５】選択された瓦記録装置に対してキャッシュされている全ての要求を実行する処理の一例を示すフローチャート。
【図１６】瓦記録装置に対する要求の実行処理の一例を示すフローチャート。
【図１７】瓦記録装置に対するＧＥＴの実行処理の一例を示すフローチャート。
【図１８】瓦記録装置に対するＤＥＬＥＴＥの実行処理の一例を示すフローチャート。
【図１９】瓦記録装置に対するＰＵＴ又はＰＯＳＴの実行処理の一例を示すフローチャート。
【図２０】データの情報を満たすバンドの選択処理の一例を示すフローチャート。
【図２１】有効期限処理の一例を示すフローチャート。
【図２２】空きバンド確保処理の一例を示すフローチャート。
【図２３】既存データ詰め込み処理の一例を示すフローチャート。
【図２４】データ特性に基づいてバンドが選択される状態の一例を示す図。
【図２５】データ特性に基づくバンドの選択処理の一例を示すフローチャート。
【図２６】データが近い将来に削除される可能性があるか否かの判断により格納先のバンドを選択する処理の一例を示すフローチャート。
【図２７】有効期限に応じて保存先のデータバンドを分けた状態の一例を示す図。
【図２８】データが瓦記録装置増設時に移動される可能性があるか否かの判断により格納先のバンクを選択する処理の一例を示すフローチャート。
【図２９】瓦記録装置増設時に移動する可能性に応じてデータの格納先のバンドを分けた状態の一例を示す図。
【図３０】データが削除又は上書きされる可能性があるか否かの判断により保存先のデータバンドを選択する処理の一例を示すフローチャート。
【図３１】過去に削除又は上書きされたデータと、他のデータとでバンドを分けた状態の一例を示す図。
【図３２】データサイズの大小により格納先のバンドを選択する処理の一例を示すフローチャート。
【図３３】サイズの小さいデータと他のデータとでバンドを分けた状態の一例を示す図。
【図３４】増設管理部の処理の一例を示すフローチャート。
【図３５】増設後のハッシュ値範囲テーブルの一例を示すデータ構造図。
【図３６】増設処理部の処理の一例を示すフローチャート。
【図３７】移動されるデータＩＤのハッシュ値範囲内のデータを、増設された瓦記録装置を担当するコントローラに送る処理の一例を示すフローチャート。
【図３８】増設された瓦記録装置を担当するコントローラの処理の一例を示すフローチャート。
【図３９】比較例の瓦記録装置のバンドの格納状態の一例を示す図。
【図４０】比較例の瓦記録装置において書き込みが一巡する前と後の書き込み時間の変化の一例を示すグラフ。
【図４１】第３の実施形態に係る、瓦記録装置の増設時に移動される可能性があるか否かの判断により格納先のバンクを選択する処理の一例を示すフローチャート。
【図４２】増設処理部の処理の一例を示すフローチャート。
【図４３】ハッシュ値テーブルのデータ特性の変更処理の一例を示すフローチャート。
【図４４】選択された瓦記録装置に対してキャッシュされている全ての要求を実行する処理と、再分類に関連するデータの書き直し処理との関係の一例を示すフローチャート。
【図４５】再分類に関連するデータの書き直し処理の一例を示すフローチャート。
【図４６】再分類に関連付けられているデータＩＤの全データを再分類する処理の一例を示すフローチャート。
【図４７】次回増設時に移動されるデータ、次々回増設時に移動されるデータ、データ特性が再分類されるデータの関係の一例を示す図。
【図４８】第４の実施形態に係る、消失訂正符号が適用された場合のデータノードの決定及び要求の発行処理の一例を示すフローチャート。
【図４９】Ｄ＝４、Ｐ＝２の場合のハッシュ値範囲テーブルの一例を示すデータ構造図。
【図５０】データから４個のデータ断片と２個の冗長情報とを生成する処理の一例を示すブロック図。
【図５１】４個のデータ断片と２個の冗長情報とから元のデータを復元する処理の一例を示すブロック図。
【図５２】第５の実施形態に係る、コーディネータの要求処理部の処理の一例を示すフローチャート。
【図５３】データＩＤテーブルの一例を示すデータ構造図。
【図５４】データＩＤテーブルに基づいて処理先のデータノードを決定し、決定されたデータノードへ要求を送る処理の一例を示すフローチャート。
【図５５】データハッシュ値リストの生成及び格納処理の一例を示すフローチャート。
【図５６】データを重複排除に適したサイズで分割する処理の一例を示すフローチャート。
【図５７】データの分割の具体例を示す図。
【図５８】データハッシュ値リストの生成の一例を示すブロック図。
【図５９】データハッシュ値範囲テーブルの一例を示すデータ構造図。
【図６０】データハッシュ値リストのデータハッシュ値によって決定されるデータノードに、要求を送る処理の一例を示すフローチャート。
【図６１】クライアントに対する結果を生成する処理の一例を示すフローチャート。
【図６２】データＩＤテーブルを検索し、古いデータを削除する処理の一例を示すフローチャート。
【図６３】キャッシュ記録装置に格納されているキャッシュ情報の一例を示すデータ構造図。
【図６４】キャッシュ処理部の処理の一例を示すフローチャート。
【図６５】データバンドテーブルの一例を示すデータ構造図。
【図６６】ハッシュ値テーブルの一例を示すデータ構造図。
【図６７】データハッシュ値テーブルの一例を示すデータ構造図。
【図６８】瓦記録装置に対するＧＥＴの実行処理の一例を示すフローチャート。
【図６９】瓦記録装置に対するＤＥＬＥＴＥの実行処理の一例を示すフローチャート。
【図７０】瓦記録装置に対するＰＵＴ又はＰＯＳＴの実行処理の一例を示すフローチャート。
【図７１】既存データ詰め込み処理の一例を示すフローチャート。
【図７２】データが瓦記録装置増設時に移動される可能性があるか否かの判断により格納先のバンクを選択する処理の一例を示すフローチャート。
【図７３】瓦記録装置増設時に移動する可能性に応じてデータの格納先のバンドを分けた状態の一例を示す図。
【図７４】増設管理部の処理の一例を示すフローチャート。
【図７５】増設後のデータハッシュ値範囲テーブルの一例を示すデータ構造図。
【図７６】増設処理部の処理の一例を示すフローチャート。
【図７７】移動されるデータＩＤのハッシュ値の範囲内のデータを、増設された瓦記録装置を担当するコントローラに送る処理の一例を示すフローチャート。
【図７８】増設された瓦記録装置を担当するコントローラの処理の一例を示すフローチャート。
【発明を実施するための形態】
【００１０】
以下、図面を参照しながら本実施形態について説明する。なお、以下の各図において同一又はほぼ同一の要素には同一の符号を付して説明を省略するか又は簡単に説明し、異なる部分についてのみ詳しく説明する。
【００１１】
［第１の実施形態］
本実施形態に係るストレージ装置は、主に書き込むことが目的であり、書き込みの回数に対して読み出しの回数が少ないコールドストレージ装置の場合を例として説明する。
【００１２】
図１は、本実施形態に係るストレージ装置の第１の例を示すブロック図である。
【００１３】
ストレージ装置１０１は、コントローラ１０２と、瓦記録装置１０３と、記録装置１０４とを含む。ストレージ装置１０１は、２以上の瓦記録装置を備えるとしてもよい。ストレージ装置１０１は、瓦記録装置１０３に対するデータの格納が開始された後に瓦記録装置１０５を増設可能である。
【００１４】
コントローラ１０２は、選択部１０６、実行部１０７、管理部１０８、期限削除部１０９、増設格納部１１０、増設削除部１１１、再分類設定部１１２、再分類部１１３を含む。コントローラ１０２の各機能は、例えば記録媒体２０１に格納されているプログラム２０２がコンピュータによって読み出され、読み出されたプログラムがコンピュータによって実行されることで実現されてもよい。
【００１５】
記録装置１０４は、バンド管理情報１１４とデータ管理情報１１５とを含む。バンド管理情報１１４とデータ管理情報１１５とは、例えばテーブル形式で管理される。しかしながら、バンド管理情報１１４とデータ管理情報１１５とは、リスト形式などの他のデータ形式で管理されてもよい。また、バンド管理情報１１４とデータ管理情報１１５とは、１つの情報に統合されてもよく、３以上に分割されてもよい。
【００１６】
バンド管理情報１１４とデータ管理情報１１５とは、例えば、瓦記録装置１０３に格納されてもよい。この場合、記録装置１０４は削除されてもよい。
【００１７】
バンド管理情報１１４は、ストレージ装置１０１に備えられる瓦記録装置を識別するための記録装置ＩＤ（例えば識別子などのような識別情報）、瓦記録装置のバンドを識別するためのバンドＩＤ、バンド内に格納されるデータの書き込み位置（例えば、データの格納容量及びデータの書き込み先頭位置）、バンド内にデータが格納された場合のデータを識別するためのデータＩＤ、バンドに格納されたデータが参照されなくなる可能性を示すデータ特性、を互いに関連付けている。ここで、「データが参照されなくなる可能性」とは、後述される「ホスト装置又はユーザによって指定された有効期間の経過により参照されなくなる場合」、「瓦記録装置の増設時の移動により参照されなくなる場合」、「データが上書きにより古くなったデータが参照されなくなる場合」などのように、ホスト装置又はユーザからの問い合わせに対してバンドに格納されたデータが参照されることがなくなる可能性を表す。換言すると、データ特性は、バンドに格納されたデータが無効状態となる可能性を表す。
【００１８】
データ特性は、例えば、バンドにデータが格納された後においてこのバンドが空き状態になる可能性を示す。データ特性は、例えば、バンドに格納可能なデータの特徴とシステムの状態とのうちの少なくとも一方に基づいて設定される。例えば、コントローラ１０１がデータ特性を設定する機能を含むとしてもよい。
【００１９】
データ管理情報１１５は、記録装置ＩＤ、データＩＤ、データＩＤの示すデータを格納するアドレス、データのサイズ、データが更新（削除又は上書き）されたか否かを示す更新履歴、データの有効期限、を互いに関連付けている。
【００２０】
選択部１０６は、データの格納（作成、上書き、更新を含む）、瓦記録装置１０５の増設による移動、などが要求された場合に、このデータとバンド管理情報１１４のデータ特性とに基づいて、データを格納するバンドを選択する。
【００２１】
例えば、バンド管理情報１１４のデータ特性は、瓦記録装置１０３の空き状態のバンドがなくなる時点で対応するバンドのデータ有効期限が切れることを示す。
【００２２】
例えば、データ特性は、瓦記録装置１０５の増設時に移動対象とすることを示す。
【００２３】
例えば、データ特性は、瓦記録装置の次回増設時に移動対象とすること、次々回増設時に移動対象とすること、再分類すること、又は、他の情報のいずれかを示す。
【００２４】
例えば、データ特性は、格納可能なデータのサイズを示す。
【００２５】
例えば、データ特性は、バンドへの格納を許可する条件が更新されていることであることを示す。
【００２６】
実行部１０７は、データの格納が要求された場合に、選択されたバンドに対して、データを格納する。
【００２７】
実行部１０７は、データの削除が要求された場合に、データ管理情報１１５に基づいて、データを削除する。
【００２８】
管理部１０８は、バンド管理情報１１４とデータ管理情報１１５とを管理する。例えば、管理部１０８は、実行部１０７によるデータの格納又は削除、期限削除部１０９によるデータの削除、増設格納部１１０によるデータの格納、増設削除部１１１によるデータの削除、再分類部１１３によるデータの格納又は削除、に基づいて、バンド管理情報１１４とデータ管理情報１１５とを更新する。例えば、管理部１０８は、データ管理情報１１５の更新履歴の管理をさらに行う。
【００２９】
管理部１０８は、ストレージ装置１０１に備えられている瓦記録装置１０３に対するバンド管理情報１１４とデータ管理情報１１５とを管理し、瓦記録装置１０５の増設後には、瓦記録装置１０３，１０５に対するバンド管理情報１１４とデータ管理情報１１５とを管理する。
【００３０】
期限削除部１０９は、バンド管理情報１１４とデータ管理情報１１５とに基づいて、バンドに格納されたデータの有効期限が経過した場合に、このデータを瓦記録装置１０３，１０５から削除する。
【００３１】
増設格納部１１０は、瓦記録装置１０５の増設時に、バンド管理情報１１４のデータ特性が次回増設時に移動対象とすることを示す瓦記録装置１０３のバンドから、データを読み出す。そして、増設格納部１１０は、バンド管理情報１１４とデータ管理情報１１５とに基づいて、読み出されたデータを、選択部１０６によって選択された瓦記録装置１０５のバンドに格納する。
【００３２】
増設削除部１１１は、瓦記録装置１０５の増設時に、増設格納部１１０によって読み出され、増設された瓦記録装置１０５に移動されたデータを、移動前の瓦記録装置１０３のバンドから削除する。
【００３３】
再分類設定部１１２は、瓦記録装置１０３から瓦記録装置１０５にデータが移動された場合に、瓦記録装置１０３のバンドに対するデータ特性を変更する。例えば、再分類設定部１１２は、増設格納部１１０によって移動されるデータが読み出された後に、データ特性が次回増設時の移動を示す場合に当該データ特性を初期化（クリア）し、データ特性が次々回増設時の移動を示す場合に当該データ特性を次回増設時の移動とし、データ特性が他の情報の場合に特性情報を再分類とする。
【００３４】
再分類部１１３は、バンド管理情報１１４でデータ特性に再分類が設定されているバンドのデータを読み出し、読み出されたデータとバンド管理情報１１４のデータ特性とに基づいて、読み出されたデータが新たに格納されるバンドを選択し、読み出されたデータを選択されたバンドに格納する。
【００３５】
図２は、本実施形態に係るストレージ装置の構成の第２の例を示すブロック図である。
【００３６】
ストレージ装置１０１Ａのコントローラ１０２Ａは、データを複数のデータ断片に分割し、データ断片単位で瓦記録装置１０３，１０５への格納、読み出しを行う。コントローラ１０２Ａの各構成要素１０６Ａ〜１１３Ａは、データを複数に分割したデータ断片を扱う点で、上記図１のコントローラ１０２の各構成要素１０６〜１１３と異なるが、概ね各構成要素１０６〜１１３と同様の処理を行う。
【００３７】
コントローラ１０２Ａは、さらに、分割部１１６と、復元部１１７、結合部１１８、を備える。
【００３８】
分割部１１６は、データを複数のデータ断片に分割し、複数のデータ断片を元のデータに戻す場合に用いられる結合情報と、データ断片に異常が発生した場合の復元に用いられる冗長情報とを生成する。例えば、冗長情報もデータ断片として瓦記録装置１０３，１０５に格納されてもよい。例えば、冗長情報は、瓦記録装置１０３，１０５ではない他の記録装置に格納されてもよい。例えば、結合情報としては、分割前のデータ中のデータ断片の位置を示す断片位置が用いられる。例えば、結合情報は、バンド管理情報１１４とデータ管理情報１１５とのうちの少なくとも１つに含められて、管理される。
【００３９】
復元部１１７は、瓦記録装置１０３，１０５からデータ断片が読み出され、読み出された複数のデータ断片のうちのいずれかに異常がある場合に、正常なデータ断片と冗長情報とに基づいて、異常の発生したデータ断片を復元する。
【００４０】
結合部１１８は、復元部１１７から正常な複数のデータ断片を受けた場合に、複数のデータ断片と結合情報とに基づいて、分割前の元のデータを生成する。
【００４１】
バンド管理情報１１４Ａ及びデータ管理情報１１５Ａは、データ断片を示すデータＩＤ、結合情報である断片位置、データ断片に基づいて算出される値をさらに含む。
【００４２】
コントローラ１０２Ａは、データ断片に基づいて計算される値により、バンド管理情報１１４Ａ及びデータ管理情報１１５Ａを管理し、瓦記録装置１０３，１０５におけるバンドの選択を行う。例えば、コントローラ１０２Ａは、データ断片のハッシュ値の計算結果であるデータハッシュ値により、格納されるバンドの選択を行う。
【００４３】
複数のデータ断片の値が同じ場合には、同じデータハッシュ値が計算される。したがって、データハッシュ値に基づいてバンドを選択することにより、同じ値のデータ断片が複数のバンドに重複して格納されることを抑えることができ、瓦記録装置１０３，１０５の容量効率を向上させることができる。
【００４４】
以上説明した本実施形態に係るストレージ装置１０１，１０１Ａにおいては、書き込み時に必要な読み出しを削減することができ、瓦記憶装置１０３，１０５に対する書き込み時間を抑制することができ、記録密度を高くすることができ、コストを下げることができ、処理速度を速くし、省電力化することができる。
【００４５】
本実施形態においては、一旦データが格納されたバンドを再利用する場合に、バンドに格納されている有効期限の経過したデータをまとめて空き状態とみなし、再利用されるバンドをそのまま空きバンドとして使用可能であり、オーバーヘッドを抑えることができる。
【００４６】
本実施形態においては、瓦記録装置１０５が増設された場合に、既存の瓦記録装置１０３のバンドのデータが増設された瓦記録装置１０５に移動され、瓦記録装置１０３のバンドを空きバンドとして使用することができる。したがって、瓦記録装置１０５の増設時のオーバーヘッドを抑えることができる。
【００４７】
本実施形態においては、既存の瓦記録装置１０３から増設された瓦記録装置１０５にデータが移動された後に、将来有効期限の経過する可能性の高いデータを瓦記録装置１０５の同じバンドにまとめることができる。したがって、増設された瓦記録装置１０５のバンドが再利用される場合に、バンド内のデータをまとめて空き状態とみなし、瓦記録装置１０５の再利用されるバンドをそのまま空きバンドとして使用可能であり、オーバーヘッドを抑えることができる。
【００４８】
本実施形態においては、データの更新履歴が管理されており、削除又は上書きされる可能性の高いデータを、同じバンドにまとめることができる。既にデータが格納されたバンドが再利用される場合、多くのデータが削除又は上書きされているバンドを選ぶことができる。更新されているバンドでは、データの削除又は上書きにより空き状態となっている領域が多い。したがって、削除又は上書きされたデータを多く格納しているバンドを再利用することで、データの格納時に読み出すデータ量を少なくすることができ、多くのデータを格納することができ、オーバーヘッドを抑えることができる。
【００４９】
本実施形態においては、データサイズが管理されており、データサイズに応じて、データを格納するバンドを選択することができる。小さいサイズのデータは管理のためのデータであり、削除又は上書きされる可能性が高い。既にデータを格納したバンドを再利用する場合、データサイズの小さいデータをまとめたバンドでは、多くのデータが削除又は上書きされて空き状態になっている。したがって、バンドを再利用する場合に、データサイズの小さいデータをまとめたバンドを再利用することにより、読み出すデータ量を少なくすることができ、多くのデータを格納することができ、オーバーヘッドを抑えることができる。
【００５０】
本実施形態においては、瓦記録装置の増設が繰り返された場合であっても、既に設置されていた瓦記録装置から増設された瓦記録装置へデータを移動し、既に設置されていた瓦記録装置に空き状態のバンドを生成することができる。
【００５１】
本実施形態に係るストレージ装置１０１Ａにおいては、冗長情報に基づいてデータが復元されるため、同じデータをバックアップ用に重複して格納することを抑えることができ、必要な記録容量を抑えることができる。本実施形態では、消失訂正符号（Erasure coding）による訂正処理を実行することができ、容量効率を向上させることができる。
【００５２】
本実施形態に係るストレージ装置１０１Ａにおいては、データ断片のハッシュ値であるデータハッシュ値に基づいて瓦記録装置１０３，１０５のバンドが選択される。したがって、瓦記録装置１０３，１０５に同じデータが重複して格納されることを抑えることができ、容量効率を向上させることができる。
【００５３】
［第２の実施形態］
本実施形態は、上記第１の実施形態に係るストレージ装置をより具体的に説明する。本実施形態では、ストレージシステムについて説明する。
【００５４】
図３は、本実施形態に係るストレージシステムの一例を示すブロック図である。
【００５５】
ストレージシステム１は、コーディネータ２−１，２−２、データノード３−１〜３−Ｎを備える。例えば、ストレージシステム１は、バックアップ、アーカイブ、大量のデータの管理などの各種の目的で用いられる。図３では、２つのコーディネータと、Ｎ（Ｎは２以上の整数）個のデータノードとを備えるストレージシステム１を例示している。しかしながら、コーディネータの数は１つ、又は、３つ以上でもよく、データノードの数は１つでもよい。すなわち、コーディネータ及びデータノードの数は、１以上の任意の整数とすることができる。
【００５６】
コーディネータ２−１，２−２、データノード３−１〜３−Ｎ、クライアント４は、ネットワーク５に接続されており、互いに要求、データ、結果を送信及び受信可能である。ストレージシステム１に接続される。ネットワーク５に接続されている各装置は遠隔に設置されてもよい。クライアント４は、ユーザ側の装置である。
【００５７】
データノード３−１〜３−Ｎは、コントローラ６−１〜６−Ｎと、キャッシュ記録装置７−１〜７−Ｎと、瓦記録装置８−１−１〜８−Ｎ−９と、を備える。図３では、データノード３−１〜３−Ｎに備えられる瓦記録装置の数が９つの場合を図示しているが、１以上であればよい。
【００５８】
コントローラ６−１〜６−Ｎは、データノード３−１〜３−Ｎに備えられている各種の構成要素を制御する。
【００５９】
キャッシュ記録装置７−１〜７−Ｎは、データノード３−１〜３−Ｎに対して発行された要求と要求に関連する情報をキャッシュする。
【００６０】
瓦記録装置８−１−１〜８−Ｎ−９は、書き込み対象の各種のデータを格納する。瓦記録装置８−１−１〜８−Ｎ−９に格納されるデータとしては、例えば、ユーザによって格納を要求されたユーザデータなどがある。
【００６１】
データノード３−１〜３−Ｎは、コントローラ６−１〜６−Ｎと、キャッシュ記録装置７−１〜７−Ｎと、瓦記録装置８−１−１〜８−１−９，…，８−Ｎ−１〜８−Ｎ−９とを備える。
【００６２】
コーディネータ２−１〜２−２の機能は、コントローラ６−１〜６−Ｎに備えられてもよく、この場合、コーディネータ２−１〜２−２は省略されてもよい。
【００６３】
クライアント４は、ストレージシステム１に対して、アプリケーションプログラムインタフェース（ＡＰＩ）にしたがって、要求を発行する。ＡＰＩは、例えば、ＨＴＴＰ（HyperText Transfer Protocol）などの通信プロトコルを用いるインタフェースである。
【００６４】
本実施形態においては、コーディネータ２−１，２−２、データノード３−１〜３−Ｎ、キャッシュ記録装置７−１〜７−Ｎ、瓦記録装置８−１−１〜８−Ｎ−９のうち、コーディネータ２−１、データノード３−１、キャッシュ記録装置７−１、瓦記録装置８−１−１を典型例として説明するが、他のコーディネータ２−２及びデータノード３−２〜３−Ｎ、キャッシュ記録装置７−２、瓦記録装置８−１−２〜８−Ｎ−９も同様の特徴を持つ。
【００６５】
要求としては、例えば、ＰＯＳＴ、ＧＥＴ、ＰＵＴ、ＤＥＬＥＴＥがある。
【００６６】
ＰＯＳＴは、ストレージシステム１にデータを生成するための要求である。例えば、ＰＯＳＴには、ホストを識別するためのストレージシステムＩＤ、データＩＤ、格納されるデータ、データのサイズが付される。
【００６７】
ＧＥＴは、ストレージシステム１からデータを取得するための要求である。例えば、ＧＥＴには、ストレージシステムＩＤ、データＩＤが付される。
【００６８】
ＰＵＴは、ストレージシステム１のデータを更新するための要求である。例えば、ＰＵＴには、ストレージシステムＩＤ、データＩＤ、格納されるデータ、データのサイズが付される。
【００６９】
ＤＥＬＥＴＥは、ストレージシステム１のデータを除去するための要求である。ＤＥＬＥＴＥには、ストレージシステムＩＤ、データＩＤが付される。
【００７０】
図４は、コーディネータ２−１の構成の一例を示すブロック図である。
【００７１】
コーディネータ２−１は、要求処理部９、増設管理部１０、ハッシュ値範囲テーブル１１を備える。
【００７２】
ここでは、ハッシュ値範囲テーブル１１及び要求処理部９について説明し、増設管理部１０の説明は、後述する。
【００７３】
図５は、ハッシュ値範囲テーブル１１の一例を示すデータ構造図である。このハッシュ値範囲テーブル１１において、ハッシュ値の範囲は、１から１００００００としている。しかしながら、ハッシュ値の範囲は、適宜変更可能である。
【００７４】
ハッシュ値範囲テーブル１１は、各種のハッシュ値範囲に対して、瓦記録装置８−１−１〜８−Ｎ−９を示す記録装置ＩＤを関連付けている。
【００７５】
ハッシュ値範囲テーブル１１を使用することにより、データＩＤのハッシュ値に基づいてこのデータＩＤに対応する記録装置ＩＤを決定することができる。さらに、記録装置ＩＤに基づいて、その記録装置ＩＤを備えるデータノードを示すデータノードＩＤを決定することができる。例えば、記録装置ＩＤには、その記録装置ＩＤの示す瓦記録装置を備えるデータノードのデータノードＩＤが含まれているとする。
【００７６】
要求処理部９は、クライアント４から発行された要求を受けた場合に、要求とハッシュ値範囲テーブル１１とに基づいて、要求を処理するデータノードを決定し、決定されたデータノードに要求を送る。
【００７７】
図６は、要求処理部９の処理の一例を示すフローチャートである。
【００７８】
ステップＳ６０１において、要求処理部９は、クライアント４から、要求対象のデータＩＤ、要求を受ける。要求処理部９は、要求の種別（例えば、ＰＯＳＴ又はＰＵＴ）によっては、クライアント４からデータ、データサイズを受ける。
【００７９】
ステップＳ６０２において、要求処理部９は、データＩＤに基づいて、要求を処理する担当データノードを決定し、担当データノードへ、要求対象のデータＩＤ、要求を送る。要求処理部９は、要求の種別によっては、担当データノードへデータ、データサイズを送る。
【００８０】
ステップＳ６０３において、要求処理部９は、クライアントに結果を返す。
【００８１】
図７は、ステップＳ６０２におけるデータノード決定処理の一例を示すフローチャートである。
【００８２】
ステップＳ７０１において、要求処理部９は、要求に付されているデータＩＤに基づいてハッシュ値を計算する。
【００８３】
ステップＳ７０２において、要求処理部９は、計算されたハッシュ値とハッシュ値範囲テーブル１１とに基づいて、計算されたハッシュ値に対応する瓦記録装置（複数）を決定する。
【００８４】
ステップＳ７０３において、要求処理部９は、決定された瓦記録装置のうちの１つを含む担当データノードに、要求、データＩＤ、決定された瓦記録装置を示す記録装置ＩＤを送る。要求処理部９は、要求の種別によっては、担当データノードへデータ、データサイズを送る。
【００８５】
ステップＳ７０４において、要求処理部９は、決定された複数の瓦記録装置の全てに対して要求などを送ったか判断する。
【００８６】
決定された複数の瓦記録装置の全てに対して要求が送られていない場合には、要求処理部９は、ステップＳ７０３を繰り返す。
【００８７】
決定された複数の瓦記録装置の全てに対して要求が送られた場合には、ステップＳ７０５において、要求処理部９は、担当データノードからの完了通知を待つ。ここで、要求がＰＯＳＴ、ＰＵＴ、ＤＥＬＥＴＥの場合には、要求処理部９は、全ての担当データノードからの完了通知を待つ。要求がＧＥＴの場合には、要求処理部９は、担当データノードのうちの１つのデータノードからの完了通知を待つ。
【００８８】
図８は、データノード３−１に備えられるコントローラ６−１の構成の一例を示すブロック図である。
【００８９】
コントローラ６−１は、キャッシュ処理部１２、要求実行部１３、増設処理部１４を含む。なお、増設処理部１４の説明は、後述する。
【００９０】
キャッシュ処理部１２は、コーディネータ２−１から、要求、データＩＤ、瓦記録装置を示す記録装置ＩＤを受ける。キャッシュ処理部１２は、要求の種別によっては、データ、データサイズを受ける。そして、キャッシュ処理部１２は、記録装置ＩＤに対して要求とデータＩＤなどの情報を関連付けて、キャッシュ記録装置７−１に格納する（キャッシュする）。
【００９１】
図９は、キャッシュ記録装置７−１に格納されているキャッシュ情報の一例を示すデータ構造図である。図９では、キャッシュ情報を論理的に図示している。
【００９２】
キャッシュ記録装置７−１のキャッシュ情報１５は、記録装置ＩＤとその記録装置ＩＤに対する要求などとを関連付けている。要求種別がＰＯＳＴ又はＰＵＴの場合、要求には、データＩＤ、データが付される。要求種別がＧＥＴ又はＤＥＬＥＴＥの場合、要求にはデータＩＤが付される。
【００９３】
キャッシュ記録装置７−１は、データベースとして実装されてもよく、記録装置に対応するファイルに、要求、データＩＤ、データを格納する方式で、キャッシュ情報１５を管理してもよい。
【００９４】
図１０は、キャッシュ処理部１２の処理の一例を示すフローチャートである。
【００９５】
ステップＳ１００１において、キャッシュ処理部１２は、コーディネータ２−１から、要求、データＩＤ、記録装置ＩＤを受ける。キャッシュ処理部１２は、要求の種別によっては、データ、データサイズを受ける。
【００９６】
ステップＳ１００２において、キャッシュ処理部１２は、要求がＧＥＴか否か判断する。
【００９７】
要求がＧＥＴの場合、処理はステップＳ１００５に進む。
【００９８】
要求がＧＥＴでない場合、ステップＳ１００３において、キャッシュ処理部１２は、記録装置ＩＤごとに、要求、データＩＤなどの情報を分類した状態でキャッシュ記録装置７−１にキャッシュする。
【００９９】
ステップＳ１００４において、キャッシュ処理部１２は、要求がＰＯＳＴ、ＤＥＬＥＴＥ、又は、ＰＵＴの場合に、コーディネータ２−１に返し、処理は終了する。
【０１００】
上記のステップＳ１００２において要求がＧＥＴと判断された場合、ステップＳ１００５において、キャッシュ処理部９は、キャッシュ記録装置７−１に対して、要求に付されている記録装置ＩＤ、データＩＤに対応するデータを検索する。
【０１０１】
ステップＳ１００６において、キャッシュ処理部９は、キャッシュ記録装置７−１から、対応するデータが読み出されたか否か、換言すれば、コーディネータ２−１，２−２から受けた要求及び情報に対応するデータがキャッシュ記録装置７−１にキャッシュされているか、判断する。
【０１０２】
対応するデータがキャッシュされていない場合、処理はステップＳ１００３に進む。
【０１０３】
対応するデータがキャッシュされている場合、ステップＳ１００７において、キャッシュ処理部９は、キャッシュ記録装置７−１から読み出され、コーディネータ２−１から受けた要求及び情報と関連するデータ（キャッシュされていたデータ）を、コーディネータ２−１に返し、処理は終了する。
【０１０４】
図１１は、瓦記録装置８−１−１の一例を示す図である。
【０１０５】
瓦記録装置８−１−１は、管理バンド１６と、データバンド１７とを含む。管理バンド１６及びデータバンド１７は、バンド区切りによって区切られる。
【０１０６】
管理バンド１６は、管理情報を格納する。管理情報は、例えば、データバンドテーブル１８、ハッシュ値テーブル１９を含む。管理情報は、キャッシュ記録装置７−１に格納されてもよい。この場合、キャッシュ記録装置７−１の全バンドは、データバンド１７とすることができる。
【０１０７】
データバンド１７は、例えば、ユーザデータ、クライアントデータなどの各種のデータを格納する。
【０１０８】
図１２は、データバンドテーブル１８の一例を示すデータ構造図である。
【０１０９】
管理バンド１６に格納されるデータバンドテーブル１８は、バンドＩＤ、格納容量、書き込み先頭位置、格納されたデータのデータＩＤ、データ有効期限を表すデータ特性（例えば、将来削除されるか、増設移動可能か、など）を、互いに関連付けて格納する。
【０１１０】
図１３は、ハッシュ値テーブル１９の一例を示すデータ構造図である。
【０１１１】
ハッシュ値テーブル１９は、ハッシュ値、データＩＤ、更新履歴、アドレス、サイズ、有効期限を、互いに関連付けて格納する。アドレスは、例えば、バンドＩＤとセクタＩＤとを含む。
【０１１２】
ＤＥＬＥＴＥが実行された場合には、削除されたデータに対応するアドレス、サイズ、有効期限は初期化される。
【０１１３】
図１４は、要求実行部１３の処理の一例を示すフローチャートである。
【０１１４】
ステップＳ１４０１において、要求実行部１３は、接続されている瓦記録装置の中から、要求を実行する瓦記録装置を選択する。
【０１１５】
ステップＳ１４０２において、要求実行部１３は、選択された瓦記録装置の電源をＯＮとし、選択された瓦記録装置に対してアクセス可能になるまで待機する。
【０１１６】
ステップＳ１４０３において、要求実行部１３は、選択された瓦記録装置に対してキャッシュされている全ての要求を実行する。
【０１１７】
ステップＳ１４０４において、要求実行部１３は、選択された瓦記録装置の電源をＯＦＦにする。
【０１１８】
ステップＳ１４０５において、要求実行部１３は、接続されている全ての瓦記録装置に対してキャッシュされている要求を実行したか否か判断する。
【０１１９】
全ての瓦記録装置に対してキャッシュされている要求を実行していない場合、処理はステップ１４０１に戻る。
【０１２０】
全ての瓦記録装置に対してキャッシュされている要求を実行した場合、要求実行部１３は処理を終了する。
【０１２１】
図１５は、選択された瓦記録装置に対してキャッシュされている全ての要求を実行する処理（上記図１４のステップＳ１４０３）の一例を示すフローチャートである。
【０１２２】
ステップＳ１５０１において、要求実行部１３は、選択された瓦記録装置から、データバンドテーブル１８とハッシュ値テーブル１９とを読み出す。
【０１２３】
ステップ１５０２において、要求実行部１３は、キャッシュ記録装置７−１から、選択された瓦記録装置に対してキャッシュされている要求とその要求に付されている情報を、順次読み出す。
【０１２４】
ステップＳ１５０３において、要求実行部１３は、選択された瓦記録措置に対して、読み出された要求を実行する。
【０１２５】
ステップＳ１５０４において、要求実行部１３は、選択された瓦記録措置に対して、キャッシュされている全ての要求を実行したか否か判断する。
【０１２６】
キャッシュされている全ての要求が実行されていない場合には、処理はステップＳ１５０２に戻る。
【０１２７】
キャッシュされている全ての要求が実行された場合には、処理は終了する。
【０１２８】
図１６は、選択された瓦記録装置に対する要求の実行処理（上記図１５のステップＳ１５０３）の一例を示すフローチャートである。
【０１２９】
ステップＳ１６０１において、要求実行部１３は、要求の種別を判断する。
【０１３０】
要求の種別がＧＥＴの場合、ステップＳ１６０２Ａにおいて、要求実行部１３は、選択された瓦記録装置に対するＧＥＴを実行する。
【０１３１】
要求の種別がＤＥＬＥＴＥの場合、ステップＳ１６０２Ｂにおいて、要求実行部１３は、選択された瓦記録装置に対するＤＥＬＥＴＥを実行する。
【０１３２】
要求の種別がＰＯＳＴ又はＰＵＴの場合、ステップＳ１６０２Ｃにおいて、要求実行部１３は、選択された瓦記録装置に対するＰＯＳＴ又はＰＵＴを実行する。
【０１３３】
図１７は、瓦記録装置に対するＧＥＴの実行処理（上記図１６のステップＳ１６０２Ａ）の一例を示すフローチャートである。
【０１３４】
ステップＳ１７０１において、要求実行部１３は、要求に付されているデータＩＤに基づいてハッシュ値を計算する。
【０１３５】
ステップＳ１７０２において、要求実行部１３は、ハッシュ値に基づいてハッシュ値テーブル１９を検索する。
【０１３６】
ステップＳ１７０３において、要求実行部１３は、ハッシュ値テーブル１９にハッシュ値に対応するエントリがあり、かつ、ハッシュ値に対応するサイズが正の値か、判断する。サイズが正の値の場合には、対応するバンドにデータが格納されていることを示す。サイズがゼロの場合には、対応するバンドにデータが格納されていないことを示す。
【０１３７】
ハッシュ値テーブル１９にハッシュ値に対応するエントリがない場合、又は、ハッシュ値に対応するサイズが正の値ではない場合、ステップＳ１７０４において、要求実行部１３は、コーディネータ２−１に、ＧＥＴ対象のデータがないことを示す結果を返し、処理は終了する。
【０１３８】
ハッシュ値テーブル１９にハッシュ値に対応するエントリがあり、かつ、ハッシュ値に対応するサイズが正の値の場合、ステップＳ１７０５において、要求実行部１３は、ハッシュ値テーブル１９から、ハッシュ値に対応するアドレスとサイズとを読み出す。
【０１３９】
ステップＳ１７０６において、要求実行部１３は、読み出されたアドレスとサイズとに基づいて、ＧＥＴ対象のデータを、選択された瓦記録装置のバンドから読み出す。
【０１４０】
ステップＳ１７０７において、要求実行部１３は、コーディネータ２−１に、読み出されたデータを結果として返す。
【０１４１】
図１８は、瓦記録装置に対するＤＥＬＥＴＥの実行処理（上記図１６のステップＳ１６０２Ｂ）の一例を示すフローチャートである。
【０１４２】
ステップＳ１８０１において、要求実行部１３は、要求に付されているデータＩＤに基づいてハッシュ値を計算する。
【０１４３】
ステップＳ１８０２において、要求実行部１３は、ハッシュ値に基づいてハッシュ値テーブル１９を検索する。
【０１４４】
ステップＳ１８０３において、要求実行部１３は、ハッシュ値テーブル１９にハッシュ値に対応するエントリがあり、かつ、ハッシュ値に対応するサイズが正の値か、判断する。
【０１４５】
ハッシュ値テーブル１９にハッシュ値に対応するエントリがない場合、又は、ハッシュ値に対応するサイズが正の値ではない場合、処理は終了する。
【０１４６】
ハッシュ値テーブル１９にハッシュ値に対応するエントリがあり、かつ、ハッシュ値に対応するサイズが正の値の場合、ステップＳ１８０４において、要求実行部１３は、ハッシュ値テーブル１９のハッシュ値に対応するアドレスからＤＥＬＥＴＥ対象のバンドＩＤを決定し、ハッシュ値に対応するサイズを読み出す。
【０１４７】
ステップＳ１８０５において、要求実行部１３は、データバンドテーブル１８に対して、決定されたバンドＩＤに対応する格納容量を、ハッシュ値に対応するサイズの分減らす。また、要求実行部１３は、データバンドテーブル１８に対して、決定されたバンドＩＤに対応するＤＥＬＥＴＥ対象のデータＩＤを削除する。
【０１４８】
ステップＳ１８０６において、要求実行部１３は、データバンドテーブル１８に対して、決定されたバンドＩＤに対応する格納容量がゼロになった場合には、決定されたバンドＩＤに対応する書き込み先頭位置をゼロにし、データＩＤとデータ特性とを初期化し、「なし」とする。
【０１４９】
ステップＳ１８０７において、要求実行部１３は、ハッシュ値テーブル１９に対して、ハッシュ値に対応するアドレスを初期化し、サイズをゼロとし、有効期限をなしとし、更新履歴をありとする。そして、処理は終了する。
【０１５０】
図１９は、瓦記録装置に対するＰＵＴ又はＰＯＳＴの実行処理（上記図１６のステップＳ１６０２Ｃ）の一例を示すフローチャートである。
【０１５１】
ステップＳ１９０１において、要求実行部１３は、要求に付されているデータＩＤに基づいてハッシュ値を計算する。
【０１５２】
ステップＳ１９０２において、要求実行部１３は、ハッシュ値に基づいてハッシュ値テーブル１９を検索する。
【０１５３】
ステップＳ１９０３において、要求実行部１３は、ハッシュ値テーブル１９にハッシュ値に対応するエントリがあり、かつ、ハッシュ値に対応するサイズが正の値か、判断する。
【０１５４】
ハッシュ値テーブル１９にハッシュ値に対応するエントリがない場合、又は、ハッシュ値に対応するサイズが正の値ではない場合、処理はステップＳ１９０５に進む。
【０１５５】
ハッシュ値テーブル１９にハッシュ値に対応するエントリがあり、かつ、ハッシュ値に対応するサイズが正の値の場合、ステップＳ１９０４において、要求実行部１３は、データＩＤに対応するデータをＤＥＬＥＴＥ対象のデータとみなし、ＤＥＬＥＴＥを実行する。
【０１５６】
ステップＳ１９０５において、要求実行部１３は、ＰＵＴ又はＰＯＳＴ対象のデータ及びシステム状態に基づいて、データの情報を生成する。
【０１５７】
ステップＳ１９０６において、要求実行部１３は、データバンドテーブル１８を参照し、データの情報がデータバンドテーブル１８のデータ特性を満たすバンドを選択する。要求実行部１３は、データの情報を満たすデータ特性がデータバンドテーブル１８に設定されていない場合には、空きバンドを選択し、この選択された空きバンドに対応するデータ特性に、データの情報を格納する。
【０１５８】
ステップＳ１９０７において、要求実行部１３は、選択されたバンドに対して、書き込み先頭位置からデータを格納する。
【０１５９】
ステップＳ１９０８において、要求実行部１３は、データバンドテーブル１８に対して、選択されたバンドＩＤに対する格納容量、書き込み先頭位置を、格納されたデータのサイズ分増やす。要求実行部１３は、データバンドテーブル１８に対して、選択されたバンドＩＤに、データＩＤを関連付けて格納する。要求実行部１３は、データバンドテーブル１８に対して、選択されたバンドに空き領域がなくなった場合に、選択されたバンドＩＤに対応する書き込み先頭位置に、空き領域のない状態を示す情報「−１」を設定する。
【０１６０】
ステップＳ１９０９において、要求実行部１３は、ハッシュ値テーブル１９にエントリを確保し、ハッシュ値、データＩＤ、更新履歴、アドレス、サイズ、有効期限を格納する。そして、処理は終了する。
【０１６１】
図２０は、データの情報を満たすバンドの選択処理（上記図１９のステップＳ１９０６）の一例を示すフローチャートである。
【０１６２】
ステップＳ２００１において、要求実行部１３は、データバンドテーブル１８に対して、データの情報がデータ特性を満たし、書き込み先頭位置が空き領域のない状態を示す「−１」ではないバンドＩＤを検索する。
【０１６３】
ステップＳ２００２において、要求実行部１３は、データバンドテーブル１８からバンドＩＤが検索されたか否か判断する。
【０１６４】
検索されたバンドＩＤがある場合、ステップＳ２００３において、要求実行部１３は、検索されたバンドＩＤを選択する。そして、処理は終了する。
【０１６５】
検索されたバンドＩＤがない場合、要求実行部１３は、ステップＳ２００４において有効期限処理を実行し、ステップＳ２００５において空きバンド確保処理を実行する。
【０１６６】
ステップＳ２００６において、要求実行部１３は、確保された空きバンドのバンドＩＤを選択し、データバンドテーブル１８に対して、確保された空きバンドに対応するエントリに、データの情報に対応するデータ特性を格納する。そして、処理は終了する。
【０１６７】
図２１は、有効期限処理（上記図２０のステップＳ２００４）の一例を示すフローチャートである。
【０１６８】
ステップＳ２１０１において、要求実行部１３は、データバンドテーブル１８に対して、データ特性に有効期限があることを示す「有効期限」が設定されており、格納容量がゼロではないバンドのバンドＩＤを検索する。
【０１６９】
ステップＳ２１０２において、要求実行部１３は、バンドＩＤが検索されたか否か判断する。
【０１７０】
バンドＩＤが検索されなかった場合、処理は終了する。
【０１７１】
バンドＩＤが検索された場合、ステップＳ２１０３において、要求実行部１３は、ハッシュ値テーブル１９に基づいて、検索されたバンドＩＤの示すバンドに格納されたデータを順次読み出す。
【０１７２】
ステップＳ２１０４において、要求実行部１３は、ハッシュ値テーブル１９に基づいて、読み出されたデータの有効期限を確認する。
【０１７３】
ステップＳ２１０５において、要求実行部１３は、読み出されたデータの有効期限が切れているか否か判断する。
【０１７４】
読み出されたデータの有効期限が切れていない場合、処理はステップＳ２１０７に進む。
【０１７５】
読み出されたデータの有効期限が切れている場合、ステップＳ２１０６において、要求実行部１３は、有効期限が切れているデータに対するＤＥＬＥＴＥを実行する。
【０１７６】
ステップＳ２１０７において、要求実行部１３は、検索されたバンドＩＤの示すバンドに格納された全データを処理したか否か判断する。
【０１７７】
検索されたバンドＩＤの示すバンドに格納された全データが処理されていない場合には、処理はステップＳ２１０３に戻る。
【０１７８】
選択されたデータバンドの全データが処理された場合には、処理は終了する。
【０１７９】
図２２は、空きバンド確保処理（上記図２０のステップＳ２００５）の一例を示すフローチャートである。
【０１８０】
ステップＳ２２０１において、要求実行部１３は、データバンドテーブル１８に対して、格納容量がゼロのバンドＩＤを検索する。
【０１８１】
ステップＳ２２０２において、要求実行部１３は、格納容量がゼロのバンドＩＤが検索されたか否か判断する。
【０１８２】
バンドＩＤが検索された場合、処理は終了する。
【０１８３】
バンドＩＤが検索されていない場合、ステップＳ２２０３において、要求実行部１３は、データバンドテーブル１８に対して、例えば、格納容量が最も少ない、又は、格納容量がしきい値以下、などのように、格納容量が少ないバンドのバンドＩＤを検索する。
【０１８４】
ステップＳ２２０４において、要求実行部１３は、格納容量が少ないために検索されたバンドに対する既存データ詰め込み処理を実行する。そして、処理は終了する。
【０１８５】
図２３は、既存データ詰め込み処理（図２２のステップＳ２２０４）の一例を示すフローチャートである。
【０１８６】
ステップＳ２３０１において、要求実行部１３は、データバンドテーブル１８に基づいて、バンドの既存データを読み出す。
【０１８７】
ステップＳ２３０２において、要求実行部１３は、バンドから全ての既存データが読み出されたか否か判断する。
【０１８８】
全ての既存データが読み出されていない場合、処理はステップＳ２３０１を繰り返す。
【０１８９】
全ての既存データが読み出された場合、ステップＳ２３０３において、要求実行部１３は、読み出されたデータを元のバンドに詰めた状態で格納する。
【０１９０】
ステップＳ２３０４において、要求実行部１３は、ハッシュ値テーブル１９に対して、バンドに詰めた状態で格納されたデータに対するアドレスを更新する。
【０１９１】
ステップＳ２３０５において、要求実行部１３は、全ての読み出されたデータをバンドに格納したか否か判断する。
【０１９２】
全ての読み出されたデータがバンドに格納されていない場合、処理はステップ２３０３に戻る。
【０１９３】
全ての読み出されたデータがバンドに格納された場合、処理は終了する。
【０１９４】
以下で、本実施形態に係るストレージシステム１の特徴を具体的に説明する。
【０１９５】
本実施形態においては、上記図１９のステップＳ１９０６で説明したように、ＰＯＳＴ又はＰＵＴが実行される場合にデータの情報がデータバンドテーブル１８に設定されているデータ特性を満たすバンドを選択する。
【０１９６】
図２４は、データ特性に基づいてバンドが選択される状態の一例を示す図である。
【０１９７】
ＰＯＳＴ又はＰＵＴを実行する場合、特徴Ｃ１を持つデータは、特徴Ｃ１のデータ特性に対応するバンドに格納される。特徴Ｃ２を持つデータは、特徴Ｃ２のデータ特性に対応するバンドに格納される。
【０１９８】
図２５は、データ特性に基づくバンドの選択処理の一例を示すフローチャートである。
【０１９９】
ステップＳ２５０１において、要求実行部１３は、データが近い将来に削除される可能性があるか否かの判断により格納先のバンドを選択する。
【０２００】
ステップＳ２５０２において、要求実行部１３は、データが瓦記録装置増設時に移動される可能性があるか否かの判断により格納先のバンドを選択する。
【０２０１】
ステップＳ２５０３において、要求実行部１３は、更新履歴を用いた、データが削除又は上書き（更新）される可能性があるか否かの判断により格納先のバンドを選択する。
【０２０２】
ステップＳ２５０４において、要求実行部１３は、データサイズの大小により、格納先のバンドを選択する。
【０２０３】
（データが近い将来に削除される可能性があるか否かの判断により格納先のバンドを選択する処理）
本実施形態において、ＰＯＳＴ又はＰＵＴの要求は、データの有効期限を指定可能であるとする。
【０２０４】
クライアント４は、ＰＯＳＴ又はＰＵＴの要求、データ、データの有効期限を、コーディネータ２−１経由で、データノード３−１のコントローラ６−１に送る。コントローラ６−１は、有効期限を、ハッシュ値テーブル１９に格納する。
【０２０５】
要求実行部１３は、有効期限と各バンドのデータ特性とに基づいて、データを格納するバンドを選択する。
【０２０６】
図２６は、データが近い将来に削除される可能性があるか否かの判断により格納先のバンドを選択する処理（図２５のステップＳ２５０１）の一例を示すフローチャートである。
【０２０７】
ステップＳ２６０１において、要求実行部１３は、データの有効期限に基づいて、データが近い将来に削除される可能性があるか否か判断する。
【０２０８】
データが近い将来に削除される可能性がない場合、処理は終了する。
【０２０９】
データが近い将来に削除される可能性がある場合、ステップＳ２６０２において、要求実行部１３は、データの格納先として、データバンドテーブル１８のデータ特性で将来削除が設定されているバンドを選択する。
【０２１０】
以上説明した本実施形態において、要求実行部１３は、有効期限の付されているデータが、例えば空きバンドの残り容量と所定の期間における書き込み量とに基づいて、近い将来に削除される可能性があるか否かを判断し、データが格納されるバンドを選択する。例えば、近い将来としては、空きバンドがなくなると予測されるタイミングがよい。例えば、空きバンドが１００００バンドあり、１日に５０バンド分のデータがＰＯＳＴ又はＰＵＴされるとする。この場合、要求実行部１３は、有効期限が２００日より前のデータを、近い将来に削除される可能性があると判断し、有効期限が２００日以上のデータを、近い将来に削除される可能性がないと判断し、格納先のバンドを分ける。
【０２１１】
近い将来削除される可能性の有無で、格納先のバンドが分けられることにより、有効期限が過ぎて削除可能なデータを格納するバンドが発生する。この削除可能なデータを格納するバンドは、新たなデータの格納に再利用可能である。
【０２１２】
図２７は、有効期限に応じて格納先のバンドを分けた状態の一例を示す図である。
【０２１３】
本実施形態においては、データの有効期限がメタデータとして管理される。空きバンドがなくなるまでに有効期限が切れるデータと、他のデータとで格納されるバンドが分けられる。本実施形態では、複数のバンドに、近い将来削除される可能性があるデータがまとめて格納されることで、有効期限が来た後に、複数のバンドが空きバンドとなる。空バンドに対しては、データを上書きすることができるため、書き込み時間を抑えることができる。
【０２１４】
（データが瓦記録装置増設時に移動される可能性があるか否かの判断により格納先のバンドを選択する処理）
コールドストレージシステムには、第１及び第２の制約がある。
【０２１５】
第１の制約では、データ数の増加に対してスケールアウト（例えば、瓦記録装置の増設、データノードの増設など）で対応できる仕組みを必要とする。このため、コールドストレージシステムは、データＩＤのハッシュ値から格納先の瓦記録装置を決定する仕組みを備える。
【０２１６】
第２の制約では、コスト面から、最初から最大容量の瓦記録装置を用意するのではなく、空き容量が少なくなった時点で、瓦記録装置を増設できる仕組みを必要とする。
【０２１７】
本実施形態に係るストレージシステム１は、上記の第１及び第２の制約を満たす。ストレージシステム１において、瓦記録装置の記録容量が上限となったら、新規の瓦記録装置が増設され、既存の瓦記録装置から増設された瓦記録装置へデータが移動される。
【０２１８】
図２８は、データが瓦記録装置増設時に移動される可能性があるか否かの判断により格納先のバンクを選択する処理（図２５のステップＳ２５０２）の一例を示すフローチャートである。この図２８の処理では、要求実行部１３は、瓦記録装置増設時にデータが移動される可能性があるか否かを判断し、データを格納するバンドを選択する。
【０２１９】
ステップＳ２８０１において、要求実行部１３は、データＩＤのハッシュ値に基づいて、データに対して次回の瓦記録装置増設時の移動の可能性を判断する。
【０２２０】
移動の可能性がない場合、処理は終了する。
【０２２１】
移動の可能性がある場合、ステップＳ２８０２において、要求実行部１３は、データの格納先として、データバンドテーブル１８のデータ特性で増設移動が設定されているバンドを選択する。
【０２２２】
図２９は、瓦記録装置増設時に移動する可能性に応じてデータの格納先のバンドを分けた状態の一例を示す図である。
【０２２３】
ある瓦記録装置に格納されるデータは、データＩＤのハッシュ値が１０００１〜２００００のデータである。この瓦記録装置において、ハッシュ値１０００１〜１５０００のデータは瓦記録装置が増設されても移動しないが、ハッシュ値１５００１〜２００００のデータは瓦記録装置の増設時に移動する。そこで、要求実行部１３は、データＩＤのハッシュ値が１５００１〜２００００であるか否か判断し、判断結果に応じてバンドを選択する。
【０２２４】
本実施形態においては、瓦記録装置が増設され、データＩＤのハッシュ値が１５００１〜２００００のデータが増設された瓦記録装置へ移動され、移動されたデータが元の瓦記録装置から削除される。これにより、元の瓦記録装置にまとまった空きバンドが多数生成される。これらの空きバンドへのデータを格納する場合には、データをそのまま上書きすればよく、書き込み時間を抑えることができる。
【０２２５】
（データが削除又は上書きされる可能性があるか否かの判断により格納先のバンドを選択する処理）
コールドストレージシステムでは、ＤＥＬＥＴＥ又はＰＵＴを実行することにより、指定されたデータＩＤのデータが削除又は上書きされる。過去に削除又は上書きされたデータは、再び削除又は上書きされる可能性が高い。
【０２２６】
そこで、本実施形態に係るストレージシステム１では、ハッシュ値テーブル１９の更新履歴に、削除又は上書きがあったか否かを示す情報が設定される。
【０２２７】
ストレージシステム１は、ハッシュ値テーブル１９の更新履歴に基づいて、データが削除又は上書きされる可能性があるか否か判断し、データが格納されるバンドを選択する。
【０２２８】
図３０は、データが削除又は上書きされる可能性があるか否かの判断により格納先のバンドを選択する処理（図２５のステップＳ２５０３）の一例を示すフローチャートである。
【０２２９】
ステップＳ３００１において、要求実行部１３は、ハッシュ値テーブル１９における更新履歴に基づいて、データが削除又は上書きされる可能性があるか判断する。
【０２３０】
データが削除又は上書きされる可能性がない場合、処理は終了する。
【０２３１】
データが削除又は上書きされる可能性がある場合、ステップＳ２７０２において、要求実行部１３は、データの格納先として、データバンドテーブル１８のデータ特性で更新履歴ありが設定されているバンドを選択する。
【０２３２】
この処理により、削除又は上書きされたことのあるデータが同じバンドにまとめられる。
【０２３３】
図３１は、過去に削除又は上書きされたデータと、他のデータとでバンドを分けた状態の一例を示す図である。
【０２３４】
削除又は上書きされたデータを格納するバンドでは、空きバンドの検索時に、多くのデータが削除又は上書きされ、無効になっている可能性が高い。したがって、削除又は上書きされたデータをまとめて格納するバンドでは、既存データの詰め込み時に、読み出すデータの数を少なくすることができる。このため、ストレージシステム１では、既存データの詰め込み時などにおいて、書き込み時間を抑えることができる。
【０２３５】
（データサイズの大小により格納先のバンドを選択する処理）
コールドストレージシステムにおいて、サイズの小さいデータは、管理のためのデータの可能性が高く、削除又は更新される可能性が高い。
【０２３６】
そこで、本実施形態に係るストレージシステム１は、データのサイズの大小により格納先のバンドを選択する。例えば、データのサイズがしきい値以下か、しきい値を越えるかに応じて格納先のバンドが分けられる。
【０２３７】
図３２は、データサイズの大小により格納先のバンドを選択する処理（図２５のステップＳ２５０４）の一例を示すフローチャートである。
【０２３８】
ステップＳ３２０１において、要求実行部１３は、データが所定サイズ以下か否か判断する。
【０２３９】
データが所定サイズ以下の場合、ステップＳ３２０２Ａにおいて、要求実行部１３は、データの格納先として、データバンドテーブル１８のデータ特性で小データが設定されているバンドを選択する。
【０２４０】
データが所定サイズ以下ではない場合、ステップＳ３２０２Ｂにおいて、要求実行部１３は、データの格納先として、データバンドテーブル１８のデータ特性でその他の情報が設定されているバンドを選択する。
【０２４１】
この処理により、サイズの小さいデータが同じバンドにまとめられる。
【０２４２】
図３３は、サイズの小さいデータと他のデータとでバンドを分けた状態の一例を示す図である。
【０２４３】
サイズの小さいデータは管理のためのデータである場合が多いため、上書き又は削除される可能性が高い。したがって、サイズの小さいデータをまとめたバンドでは、空きバンドの検索時に、多くのデータが削除又は上書きされ、無効になっている可能性が高い。本実施形態では、小さいデータを格納するバンドにおいては、既存データの詰め込み時に、読み出されるデータの数が少なくなる。したがって、ストレージシステム１では、既存データの詰め込み時などにおいて、書き込み時間を抑えることができる。
【０２４４】
（瓦記録装置の増設）
コーディネータ２−１に備えられる増設管理部１０及びコントローラ６−１に備えられる増設処理部１４のそれぞれで実行される処理を説明する。
【０２４５】
瓦記録装置の増設の要否の判断は、コントローラ６−１で実行される。データＩＤのハッシュ値範囲の決定、ハッシュ値範囲に対応する瓦記録装置の決定は、コーディネータ２−１で実行される。
【０２４６】
図３４は、増設管理部１０の処理の一例を示すフローチャートである。増設管理部１０は、増設要求の発行元のコントローラ６−１から増設処理の完了通知を受けた段階で、ハッシュ値範囲テーブル１１を変更する。
【０２４７】
ステップＳ３４０１において、増設管理部１０は、コントローラ６−１からの増設要求を受ける。
【０２４８】
ステップＳ３４０２において、増設管理部１０は、増設された瓦記録装置の記録装置ＩＤを決定する。
【０２４９】
ステップＳ３４０３において、増設管理部１０は、分割されるデータＩＤのハッシュ値範囲を決定する。
【０２５０】
ステップＳ３４０４において、増設管理部１０は、増設要求を発行したコントローラ６−１に、増設された瓦記録装置の記録装置ＩＤ、移動されるハッシュ値範囲を通知し、移動完了通知を待つ。
【０２５１】
ステップＳ３４０５において、増設管理部１０は、ハッシュ値範囲テーブル１１を変更する。
【０２５２】
ステップＳ３４０６において、増設管理部１０は、他のコーディネータ２−２へ、ハッシュ値範囲テーブル１１の変更を通知する。
【０２５３】
図３５は、増設後のハッシュ値範囲テーブル１１の一例を示すデータ構造図である。
【０２５４】
増設前の１０００１〜２００００のハッシュ値範囲が、増設により、１０００１〜１５０００のハッシュ値範囲と、１５００１〜２００００のハッシュ値範囲とに分割されている。増設された瓦記録装置８−１−９，８−２−９，８−３−９は、１５００１〜２００００のハッシュ値範囲に割り当てられている。より具体的に説明すると、増設前は、１０００１〜２００００のハッシュ値範囲が、瓦記録装置８−４−１，８−５−１，８−６−１で担当されていた。瓦記録装置８−４−１，８−５−１，８−６−１が増設されると、１０００１〜１５０００のハッシュ値範囲は、瓦記録装置８−４−１，８−５−１，８−６−１で担当され、１５００１〜２００００のハッシュ値範囲は、瓦記録装置８−１−９，８−２−９，８−３−９で担当される。増設後のハッシュ値範囲テーブル１１は、全てのコーディネータに通知される。これにより、コーディネータ２−１，２−２は、増設された瓦記録装置８−１−９，８−２−９，８−３−９をアクセス可能になる。
【０２５５】
図３６は、増設処理部１４の処理の一例を示すフローチャートである。
【０２５６】
ステップＳ３６０１において、増設処理部１４は、データバンドテーブル１８に対して、格納容量が第１の所定値以下のバンド数を計算する。
【０２５７】
ステップＳ３６０２において、増設処理部１４は、計算されたバンド数が第２の所定値以上か否か判断する。
【０２５８】
バンド数が第２の所定値以上の場合、処理は終了する。
【０２５９】
バンド数が第２の所定値未満の場合、ステップＳ３６０３において、増設処理部１４は、コーディネータ２−１に、瓦記録装置の増設要求を送る。
【０２６０】
ステップＳ３６０４において、増設処理部１４は、コーディネータ２−１から、増設された瓦記録装置の記録装置ＩＤ、移動されるデータＩＤのハッシュ値範囲を受ける。
【０２６１】
ステップＳ３６０５において、増設処理部１４は、増設された瓦記録装置を担当するコントローラに、増設された瓦記録装置の記録装置ＩＤ、移動されるデータＩＤのハッシュ値範囲を送る。
【０２６２】
ステップＳ３６０６において、増設処理部１４は、移動されるデータＩＤのハッシュ値範囲内のデータを、増設された瓦記録装置を担当するコントローラに送る。
【０２６３】
ステップＳ３７０７において、増設処理部１４は、コーディネータ２−１に、増設完了通知を送り、移動された全データの情報を、データバンドテーブル１８、ハッシュ値テーブル１９から削除する。そして、処理は終了する。
【０２６４】
図３７は、移動されるデータＩＤのハッシュ値範囲内のデータを、増設された瓦記録装置を担当するコントローラに送る処理（図３６のステップＳ３６０６）の一例を示すフローチャートである。
【０２６５】
ステップＳ３７０１において、増設処理部１４は、ハッシュ値テーブル１９のデータＩＤを順次読み出す。
【０２６６】
ステップＳ３７０２において、増設処理部１４は、読み出されたデータＩＤのハッシュ値が、移動されるデータＩＤのハッシュ値範囲か否か判断する。
【０２６７】
データＩＤのハッシュ値が、移動されるデータＩＤのハッシュ値範囲でない場合、処理はステップＳ３７０５に進む。
【０２６８】
データＩＤのハッシュ値が、移動されるデータＩＤのハッシュ値範囲の場合、ステップＳ３７０３において、増設処理部１４は、ハッシュ値テーブル１９から、データＩＤに対応するアドレスのデータを、バンドから読み出す。
【０２６９】
ステップＳ３７０４において、増設処理部１４は、読み出されたデータと、ハッシュ値テーブル１９のデータＩＤ、更新履歴、有効期限を、増設された瓦記録装置を担当するコントローラに送る。
【０２７０】
ステップＳ３７０５において、増設処理部１４は、ハッシュ値テーブル１９の全データＩＤを処理したか否か判断する。
【０２７１】
ハッシュ値テーブル１９の全データＩＤを処理していない場合、処理はステップＳ３７０１に戻る。
【０２７２】
ハッシュ値テーブル１９の全データＩＤを処理した場合、増設処理部１４は、増設された瓦記録装置を担当するコントローラに終了通知を送り、処理は終了する。
【０２７３】
図３８は、増設された瓦記録装置を担当するコントローラの処理の一例を示すフローチャートである。
【０２７４】
ステップＳ３８０１において、増設処理部１４は、増設要求の発行元のコントローラ（例えば、記憶容量が上限となった瓦記録装置を担当するコントローラ）から、増設された瓦記録装置の記録装置ＩＤ、移動されるデータＩＤのハッシュ値範囲を受ける。
【０２７５】
ステップＳ３８０２において、増設処理部１４は、移動されるデータＩＤのハッシュ値範囲に基づいて、データバンドテーブル１８、ハッシュ値テーブル１９を初期化する。
【０２７６】
ステップＳ３８０３において、増設処理部１４は、増設要求の発行元のコントローラから、データ、データＩＤ、更新履歴、有効期限を受ける。
【０２７７】
ステップＳ３８０４において、増設処理部１４は、増設要求の発行元のコントローラから受けたデータを新規に格納されるデータとみなしてＰＯＳＴ又はＰＵＴを実行する。
【０２７８】
ステップＳ３８０５において、増設処理部１４は、増設要求の発行元のコントローラから、終了通知を受けたか否か判断する。
【０２７９】
終了通知を受けていない場合、処理はステップＳ３８０３に戻る。
【０２８０】
終了通知を受けた場合、処理は終了する。
【０２８１】
以上説明したように、瓦記録装置増設時のデータ移動において、増設要求の発行元のコントローラは、増設される瓦記録装置を担当するコントローラがバンドを選択するために必要な情報（具体的には、近い将来削除される可能性の判断、瓦記録装置増設時に移動される可能性の判断、更新履歴による削除又は上書きされる可能性の判断、データサイズの大小の判断、で用いられる情報）を、データとともに、増設された瓦記録装置を担当するコントローラに送る。
【０２８２】
増設された瓦記録装置を担当するコントローラは、増設要求の発行元のコントローラから受けた情報に基づいて、データを格納するバンドを選択し、選択されたバンドにデータを格納する。
【０２８３】
したがって、本実施形態においては、増設された瓦記録装置に移動されたデータのうち、近い将来に削除、移動、上書きされるデータをまとめて、増設された瓦記録装置における選択されたバンドに格納することができる。増設された瓦記録装置では、ある程度使用された後に、この選択されたバンドを空きバンドとして新たに書き込みを行うことができる。これにより書き込み時間を抑えることができる。
【０２８４】
（本実施形態の有効性）
本実施形態に係るストレージシステム１の有効性を、比較例の瓦記録装置と対比して説明する。
【０２８５】
図３９は、比較例の瓦記録装置のバンドの格納状態の一例を示す図である。
【０２８６】
図４０は、比較例の瓦記録装置において書き込みが一巡する前と後の書き込み時間の変化の一例を示すグラフである。
【０２８７】
比較例の瓦記録装置では、バンド単位で書き込みを行う必要があるため、１バンド以内の書き込みであれば、例えば５１２バイトなどの少ないデータ量の書き込みであっても、１バンドの記憶容量（約２００メガバイト）に相当するデータ量の書き込みであっても、同じ時間が必要になる。通常のＨＤＤと同様の書き込みを、比較例の瓦記憶装置に適用した場合、比較例の瓦記憶装置に対するデータ書き込みの一巡後に、空きバンドがなくなる。その後、比較例の瓦記録装置に対して書き込みデータの追加、更新、削除、移動が発生すると、データの書き換え位置はまだら状態に散在する。書き換え位置が散在するバンドに、１バンド分のデータを格納する場合には、２バンドの読み出しと２バンドの書き込みが必要になる。したがって、比較例の瓦記録装置は、通常のＨＤＤと比べて、４倍の書き込み時間（２バンド読み出し、２バンド書き込み）が必要になる。通常のＨＤＤでは、書き換える場所が増えても、ランダムで書き換えられるため、多少書き込み時間が延びるだけですむ。これに対して、比較例の瓦記録装置では、バンド単位の更新に時間がかかり、更新されるバンド数も増えるため、更新に必要な時間が増加する。
【０２８８】
これに対して、本実施形態に係るストレージシステム１においては、データ特性に応じてデータを格納するバンドを分けることで、瓦記録装置におけるバンド単位での読み出し回数、書き込み回数を抑制することができ、使用電力を抑制することができる。
【０２８９】
本実施形態に係るストレージシステム１においては、瓦記録装置を用いることで、安いコストで大量のデータを格納することができる。
【０２９０】
［第３の実施形態］
本実施形態においては、上記の第２の実施形態に係るストレージシステム１の変形例について説明する。本実施形態では、上記の第２の実施形態と異なる部分を主に説明する。
【０２９１】
上記の第２の実施形態では、瓦記録装置の増設時に移動される可能性があるか否かの判断によるバンドの選択は、１回の増設に用いられる。したがって、増設が繰り返される状況では、増設要求の発行元のデータノードで空きバンドが少なくなる場合がある。
【０２９２】
これに対して、本実施形態では、増設要求の発行を複数回繰り返すことが可能なストレージシステム１について説明する。
【０２９３】
本実施形態においては、次回の瓦記録装置の増設に加えて、次々回の瓦記録装置の増設におけるデータの移動も考慮し、データの格納先のバンドを選択する。
【０２９４】
図４１は、本実施形態に係る瓦記録装置の増設時に移動される可能性があるか否かの判断により格納先のバンクを選択する処理の一例を示すフローチャートである。
【０２９５】
ステップＳ４１０１において、要求実行部１３は、データＩＤのハッシュ値に基づいて、データに対する次回及び次々回の瓦記録装置増設時の移動の可能性を判断する。
【０２９６】
移動の可能性がない場合には、処理は終了する。
【０２９７】
次回の瓦記録装置増設時に移動の可能性がある場合、ステップＳ４１０２Ａにおいて、要求実行部１３は、データの格納先として、データバンドテーブル１８のデータ特性で次回増設移動が設定されているバンドを選択する。
【０２９８】
次々回の瓦記録装置増設時に移動の可能性がある場合、ステップＳ４１０２Ｂにおいて、要求実行部１３は、データの格納先として、データバンドテーブル１８のデータ特性で次々回増設移動が設定されているバンドを選択する。
【０２９９】
図４２は、本実施形態に係る増設処理部１４の処理の一例を示すフローチャートである。この図４２のステップＳ４２０１〜Ｓ４２０７までは、上記図３６のステップＳ３６０１〜Ｓ３６０７と同様である。図４２の処理は、ハッシュ値テーブル１９のデータ特性の変更処理が実行されるステップＳ４２０８を含む特徴を持つ。
【０３００】
図４３は、ハッシュ値テーブル１９のデータ特性の変更処理（図４２のステップＳ４２０８）の一例を示すフローチャートである。
【０３０１】
ステップＳ４３０１において、増設要求の発行元の増設処理部１４は、データバンドテーブル１８のデータ特性を順次読み出す。
【０３０２】
ステップＳ４３０２において、増設処理部１４は、データ特性を判断する。
【０３０３】
データ特性に次回増設移動が設定されている場合、ステップＳ４３０３Ａにおいて、増設処理部１４は、データ特性を初期化（情報の削除）する。
【０３０４】
データ特性に次々回増設移動が設定されている場合、ステップＳ４３０３Ｂにおいて、増設処理部１４は、データ特性に、次回増設移動を設定する。
【０３０５】
データ特性に、更新履歴、小データなど、他の情報が設定されている場合に、ステップＳ４３０３Ｃにおいて、増設処理部１４は、データ特性に、再分類を設定する。
【０３０６】
ステップＳ４３０４において、増設処理部１４は、データバンドテーブル１８の全エントリのデータ特性が処理されたか判断する。
【０３０７】
全エントリが処理されていない場合、処理はステップＳ４３０１に戻る。
【０３０８】
全エントリが処理された場合、処理は終了する。
【０３０９】
この結果、増設要求の発行元のデータバンドテーブル１８では、瓦記録装置の増設後に、データ特性の次回増設移動は初期化され、データ特性の次々回増設移動は次回増設移動に変更され、他のデータ特性は再分類に変更される。
【０３１０】
図４４は、選択された瓦記録装置に対してキャッシュされている全ての要求を実行する処理（上記図１５の処理）と、再分類に関連するデータの書き直し処理との関係の一例を示すフローチャートである。
【０３１１】
この図４４では、ステップＳ１５０１からステップＳ１５０４で全ての要求が実行された後に、ステップＳ４４０１において、要求実行部１３が、再分類に関連するデータの書き直し処理を実行する。
【０３１２】
図４５は、再分類に関連するデータの書き直し処理（図４４のステップＳ４４０１）の一例を示すフローチャートである。
【０３１３】
ステップ４５０１において、要求実行部１３は、データバンドテーブル１８からデータ特性を順次読み出す。例えば、要求実行部１３は、前回の再分類処理で読み出されたデータ特性の続きから、データ特性を読み出すとしてもよい。
【０３１４】
ステップＳ４５０２において、要求実行部１３は、データ特性が再分類か否か判断する。
【０３１５】
データ特性が再分類ではない場合、処理はステップＳ４５０４に進む。
【０３１６】
データ特性が再分類の場合、ステップＳ４５０３において、要求実行部１３は、再分類に関連付けられているデータＩＤの全データを再分類する処理を実行する。
【０３１７】
ステップＳ４５０４において、要求実行部１３は、所定数のエントリに対して処理を実行したか否か判断する。
【０３１８】
所定数のエントリに対して処理が実行されていない場合、処理はステップＳ４５０１に戻る。
【０３１９】
所定数のエントリに対して処理が実行された場合、処理は終了する。
【０３２０】
図４６は、再分類に関連付けられているデータＩＤの全データを再分類する処理（図４５のステップＳ４５０３）の一例を示すフローチャートである。
【０３２１】
ステップＳ４６０１において、要求実行部１３は、データバンドテーブル１８で再分類に関連付けられているデータＩＤを読み出し、読み出されたデータＩＤに対応するデータを順次読み出す。
【０３２２】
ステップＳ４６０２において、要求実行部１３は、読み出されたデータＩＤに対応するハッシュ値テーブル１９のサイズにゼロを設定する。
【０３２３】
ステップＳ４６０３において、要求実行部１３は、読み出されたデータに対応するハッシュ値テーブル１９のデータＩＤ、更新履歴、有効期限を使用して、ＰＯＳＴ又はＰＵＴを実行する。
【０３２４】
ステップＳ４６０４において、要求実行部１３は、再分類に関連付けられているデータＩＤの全データに対して処理が実行されたか否か判断する。
【０３２５】
再分類に関連付けられているデータＩＤの全データに対して処理が実行されていない場合、処理はステップＳ４６０１に戻る。
【０３２６】
再分類に関連付けられているデータＩＤの全データに対して処理が実行された場合、処理は終了する。
【０３２７】
以上説明したように、本実施形態においては、ある瓦記録装置に格納されているデータを、瓦記録装置が増設された場合に複数回移動させることができる。
【０３２８】
図４７は、次回増設時に移動されるデータ、次々回増設時に移動されるデータ、データ特性が再分類されるデータの関係の一例を示す図である。
【０３２９】
この図４７の例では、データＩＤのハッシュ値が１５００１〜２００００のデータが次回移動、データＩＤのハッシュ値が１２５０１〜１５０００のデータが次々回移動として、別々のバンドに格納される。
【０３３０】
増設された瓦記録装置へデータが移動された場合、データＩＤのハッシュ値が１２５０１〜１５０００のデータが次回移動、データＩＤのハッシュ値が１０００１〜１２５００のデータが再分類として、データ特性が変更される。
【０３３１】
再分類のバンドに格納されたデータは、キャッシュされた要求が処理される場合に、少しずつ（所定数ずつ）再分類される。この再分類により、再分類のバンドに格納されたデータは、次々回移動と他の情報とに分けられて、別々のバンドに格納される。これにより、瓦記録装置の増設とデータ移動が繰り返されても、空きバンドを生成することができる。
【０３３２】
なお、本実施形態においては、再分類を行うために、再分類バンドの読み出しと書き込みとが必要になるが、再分類バンドの量は全体のおよそ１／４であり、書き込み時間が通常のＨＤＤよりおよそ２倍に延びる程度である。上記の比較例の瓦記録装置では通常のＨＤＤの４倍の読み出しと書き込みの時間を必要とする。したがって、本実施形態に係るストレージシステム１では、比較例の瓦記録装置により、書き込み時間を短縮することができる。
【０３３３】
［第４の実施形態］
本実施形態においては、上記第２及び第３の実施形態の変形例について説明する。
【０３３４】
例えば、上記第２の実施形態では、バックアップデータを格納するために、３台の瓦記録装置に同じデータが格納されてもよい。この場合、容量のオーバーヘッドが大きくなる。そこで、本実施形態においては、コーディネータ２−１で消失訂正符号（Erasure coding）による訂正処理を実行可能とし、瓦記録装置に、データ断片及び冗長情報を格納する。
【０３３５】
図４８は、消失訂正符号が適用された場合のデータノードの決定及び要求の発行処理の一例を示すフローチャートである。この図４８において、データノードは、データＩＤに基づいて決定される。
【０３３６】
ステップＳ４８０１において、コーディネータ２−１の要求処理部９は、データＩＤに基づいてハッシュ値を計算する。例えば、ハッシュ値は、１〜１００００００の範囲とする。
【０３３７】
ステップＳ４８０２において、要求処理部９は、計算されたハッシュ値に基づいて、ハッシュ値範囲テーブル１１を検索し、計算されたハッシュ値に対応するデータを格納するＤ＋Ｐ台の瓦記録装置を決定する。ここで、Ｄ及びＰは整数とする。
【０３３８】
ステップＳ４８０３において、要求処理部９は、データをＤ個に分割し、冗長情報をＰ個に分割し、Ｄ個のデータ断片とＰ個の冗長情報を生成する。
【０３３９】
ステップＳ４８０４において、要求処理部９は、決定された瓦記録装置のうちの１つを含むデータノードに、要求、決定された瓦記録装置の記録装置ＩＤ、データ断片又は冗長情報、を送る。
【０３４０】
ステップＳ４８０５において、要求処理部９は、決定された瓦記録装置の全てに対して、要求を送ったか判断する。
【０３４１】
決定された瓦記録装置の全てに対して要求を送っていない場合には、要求処理部９は、ステップＳ４８０４を繰り返す。
【０３４２】
決定された瓦記録装置の全てに対して要求が送られた場合には、ステップＳ４８０６において、要求処理部９は、要求を送ったデータノードから完了通知を待つ。ここで、要求がＰＯＳＴ、ＰＵＴ、ＤＥＬＥＴＥの場合には、要求処理部９は、要求を送った全てのデータノードからの完了通知を待つ。要求がＧＥＴの場合には、要求処理部９は、要求を送ったデータノードのうちのＤ＋Ｐ個のデータノードからの完了通知を待つ。
【０３４３】
ステップＳ４８０７において、要求処理部９は、要求がＧＥＴの場合に、Ｄ個のデータ断片及びＰ個の冗長情報から元のデータを復元する。
【０３４４】
上記の図４８のフローチャートは、データからＤ個のデータ断片とＰ個の冗長情報とを生成する処理と、Ｄ個のデータ断片とＰ個の冗長情報とから元のデータを復元する処理を含む点で、上記第２の実施形態の図７と相違しているが、他の部分ではほぼ同じである。
【０３４５】
図４９は、Ｄ＝４、Ｐ＝２の場合のハッシュ値範囲テーブル１１の一例を示すデータ構造図である。なお、Ｄは２以上の整数のいずれの値でもよく、Ｐは１以上の整数のいずれの値でもよい。
【０３４６】
本実施形態に係るストレージシステム１では、ハッシュ値範囲テーブル１１のハッシュ範囲ごとに、Ｄ＋Ｐ個の瓦記録装置が登録されている。
【０３４７】
図５０は、データから４個のデータ断片と２個の冗長情報とを生成する処理の一例を示すブロック図である。
【０３４８】
第１に、データｄは、Ｄ＝４個のデータ断片ｄ１〜ｄ４に分割される。
【０３４９】
第２に、４個の分割されたデータｄ１〜ｄ４が同じサイズになるよう、データ断片ｄ４に対するパッドデータｄｐの追加が行われる。
【０３５０】
第３に、４個の分割されたデータｄ１〜ｄ４に対する２個の冗長情報ｐ，ｑが生成される。
【０３５１】
図５１は、４個のデータ断片ｄ１〜ｄ４と冗長情報ｐとから元のデータｄを復元する処理の一例を示すブロック図である。
【０３５２】
第１に、データ断片ｄ１〜ｄ４のうちの１つのデータ断片ｄ３にエラーが発生し、このデータ断片ｄ３が欠落している場合、冗長情報ｐに基づいて不足しているデータ断片ｄ３が復元される。
【０３５３】
第２に、データ断片ｄ４からパッドデータｐｄが削除される。
【０３５４】
第３に、４個のデータ断片ｄ１〜ｄ４が連結され、データｄが復元される。
【０３５５】
以上説明した本実施形態においては、データｄに基づいてデータ断片ｄ１〜ｄ４と冗長情報ｐ，ｑとが生成され、データノードに格納される。これにより、同じデータを複数個格納する必要がなく、ストレージシステム１の容量効率を向上させることができる。
【０３５６】
［第５の実施の形態］
本実施形態においては、上記第２乃至第４の実施形態の変形例について説明する。
【０３５７】
上記第２の実施形態では、データＩＤから計算されるハッシュ値によりデータを格納する瓦記録装置が決定される。この場合、データＩＤが異なるがデータの値が同じ複数のデータが別々に保存される場合がある。
【０３５８】
これに対して、本実施形態においては、値の同じデータを同じ瓦記録装置に格納することにより、容量効率を向上させる。
【０３５９】
図５２は、本実施形態に係るコーディネータ２−１の要求処理部９の処理の一例を示すフローチャートである。
【０３６０】
ステップＳ５２０１において、要求処理部９は、クライアント４から、要求、データＩＤ、データを受ける。
【０３６１】
ステップＳ５２０２において、要求処理部９は、データのハッシュ値であるデータハッシュ値に対応する担当のデータノードを決定し、決定されたデータノードに、要求、データＩＤ、データを送る。
【０３６２】
ステップＳ５２０３において、要求処理部９は、クライアント４に結果を返す。
【０３６３】
この図５２のフローチャートは、データハッシュ値に対応するデータノードを決定し、決定されたデータノードへ要求を送る処理が、上記第２の実施形態の図６と相違しているが、他の部分はほぼ同じである。
【０３６４】
図５３は、本実施形態に係るデータＩＤテーブルの一例を示すデータ構造図である。
【０３６５】
データＩＤテーブル２０は、データＩＤと、データＩＤに対応するデータを分割したデータ断片のデータハッシュ値を含むデータハッシュ値リストと、データＩＤに対する更新履歴とを、互いに関連付けた状態で格納する。
【０３６６】
本実施形態において、データの格納及びデータの読み出しに、データハッシュ値リストが使用される。
【０３６７】
図５４は、データハッシュ値に対応するデータノードに要求を送る処理の一例を示すフローチャートである。
【０３６８】
ステップＳ５４０１において、要求処理部９は、要求の種別を判断する。
【０３６９】
要求がＤＥＬＥＴＥの場合、処理はステップＳ５４０２に進む。
【０３７０】
要求がＧＥＴの場合、処理はステップＳ５４０３に進む。
【０３７１】
要求がＰＯＳＴ又はＰＵＴの場合、処理はステップＳ５４０６に進む。
【０３７２】
ステップＳ５４０２において、要求処理部９は、データＩＤテーブル２０に対して、データＩＤに対応する更新履歴を「あり」に設定する。その後、処理はステップＳ５４０３に進む。
【０３７３】
ステップＳ５４０３において、要求処理部９は、データＩＤテーブル２０に対して、データＩＤに対応するデータハッシュ値リストを検索する。
【０３７４】
ステップＳ５４０４において、要求処理部９は、データＩＤに対応するデータハッシュ値リストがあるか否か判断する。
【０３７５】
データハッシュ値のリストがある場合、処理はステップＳ５４０８に移動する。
【０３７６】
データハッシュ値リストがない場合、ステップＳ５４０９において、要求処理部９は、「要求データなし」を示す結果を生成する。そして、処理は終了する。
【０３７７】
上記のステップＳ５４０１において要求がＰＯＳＴ又はＰＵＴと判断された場合には、ステップＳ５４０６が実行される。ステップＳ５４０６において、要求処理部９は、データＩＤテーブル２０を検索し、古いデータがあれば、古いデータを削除する。
【０３７８】
ステップＳ５４０７において、要求処理部９は、データからデータハッシュ値を計算し、データハッシュ値リストをデータＩＤテーブル２０に格納する。
【０３７９】
上記のステップＳ５４０４においてデータハッシュ値リストがあった場合、又は、上記ステップＳ５４０７の後、ステップＳ５４０８において、要求処理部９は、データハッシュ値リストに含まれるデータハッシュ値で決定されるデータノードに、要求を送る。
【０３８０】
ステップＳ５４０９において、要求処理部９は、決定された全てのデータノードから完了通知を受けた後に、クライアント４に対する結果を生成する。そして、処理は終了する。
【０３８１】
図５５は、データハッシュ値リストの生成及び格納処理（図５４のステップＳ５４０７）の一例を示すフローチャートである。
【０３８２】
ステップＳ５５０１において、要求処理部９は、データを重複排除に適したサイズで分割する。
【０３８３】
ステップＳ５５０２において、要求処理部９は、分割されたデータ断片ごとに、データハッシュ値を計算する。
【０３８４】
ステップＳ５５０３において、要求処理部９は、計算されたデータハッシュ値に基づいてデータハッシュ値のリストを生成する。
【０３８５】
ステップＳ５５０４において、要求処理部９は、データＩＤテーブルに対して、生成されたデータハッシュ値のリストとデータＩＤとを関連付けて格納する。
【０３８６】
図５６は、データを重複排除に適したサイズで分割する処理（図５５のステップＳ５５０１）の一例を示すフローチャートである。
【０３８７】
ステップＳ５６０１において、要求処理部９は、データの先頭を分割候補点に設定する。
【０３８８】
ステップＳ５６０２において、要求処理部９は、分割候補点からｍバイトのハッシュ値を計算する。
【０３８９】
ステップＳ５６０３において、要求処理部９は、ハッシュ値の下位ｂビットが規定値ｈに一致するか否か判断する。
【０３９０】
規定値ｈに一致しない場合、処理はステップＳ５６０６に進む。
【０３９１】
規定値ｈに一致する場合、ステップＳ５６０４において、要求処理部９は、データ断片が例えば１キロバイトなどの所定サイズ以上になるか否か判断する。
【０３９２】
データ断片が所定サイズ以上にならない場合、処理はステップＳ５６０６に進む。
【０３９３】
データ断片が所定サイズ以上になる場合、ステップＳ５６０５において、要求処理部９は、分割候補点でデータを分割し、データ断片を生成する。そして、処理はステップＳ５６０６に進む。
【０３９４】
ステップＳ５６０６において、要求処理部９は、分割候補点を１バイト後に進める。
【０３９５】
ステップＳ５６０７において、要求処理部９は、データ全体を調べたか否か判断する。
【０３９６】
データ全体が調べられていない場合、処理はステップＳ５６０２に戻る。
【０３９７】
データ全体が調べられた場合、処理は終了する。
【０３９８】
図５７は、データの分割の具体例を示す図である。
【０３９９】
この図５７は、上記図５６のフローチャートを、ｍ＝３、ｂ＝１２、ｈ＝０で実行した場合のデータの分割状態を示している。この例では、データがｒｓｔで始まる部分で分割される。
【０４００】
重複するオフセットの位置がずれており、部分的に重複する部分を持つデータであっても、図５６及び図５７の分割方法を適用することにより、重複する部分に下位１２ビットがゼロになる部分が含まれていれば、その先は分割位置が同じになり、分割されたデータ断片も一致する確率が高くなる。したがって、重複する部分が多くなるようにデータを分割することができる。
【０４０１】
図５８は、本実施形態に係るデータハッシュ値リストの生成の一例を示すブロック図である。
【０４０２】
第１に、データｄは重複排除に適したサイズに分割され、データ断片ｄ１〜ｄ７が生成される。
【０４０３】
第２に、データ断片ｄ１〜ｄ７のデータハッシュ値が計算され、データハッシュ値リストが生成される。
【０４０４】
データハッシュ値リストを使用して、データ断片ｄ１〜ｄ７を処理するデータノードが決定され、決定されたデータノードへ要求が送られる。
【０４０５】
図５９は、本実施形態に係るデータハッシュ値範囲テーブルの一例を示すデータ構造図である。
【０４０６】
本実施形態では、データハッシュ値からデータ断片を担当するデータノードを決定するために、このデータハッシュ値範囲テーブル２１が用いられる。このデータハッシュ値範囲テーブル２１の役割は、第２の実施形態に係るハッシュ値範囲テーブル１１に相当する。
【０４０７】
データハッシュ値範囲テーブル２１では、データハッシュ値範囲に対して記憶装置ＩＤが関連付けられている。
【０４０８】
本実施形態に係る要求処理部９は、データハッシュ値範囲テーブル２１に基づいて、全てのデータ断片を、データハッシュ値範囲のデータノードに送り、処理を依頼する。そして、要求処理部９は、全てのデータ断片に対するデータノードからの完了通知を待つ。
【０４０９】
図６０は、データハッシュ値リストのデータハッシュ値によって決定されるデータノードに、要求を送る処理（上記図５４のステップＳ５４０８）の一例を示すフローチャートである。
【０４１０】
ステップＳ６００１において、要求処理部９は、生成されるデータ断片がデータのどの位置かを示す断片位置をゼロに設定する。
【０４１１】
ステップＳ６００２において、要求処理部９は、データハッシュ値リスト内の断片位置に対応するデータハッシュ値を読み出す。
【０４１２】
ステップＳ６００３において、要求処理部９は、データハッシュ値範囲テーブル２１を検索し、読み出されたデータハッシュ値に対応するデータ断片を格納する瓦記録装置（複数でもよい）を決定する。
【０４１３】
ステップＳ６００４において、要求処理部９は、決定された複数の瓦記録装置のうちの１つを含むデータノードに、要求、データＩＤ，断片位置、更新履歴、決定された瓦記録装置の記録装置ＩＤを送る。要求処理部９は、要求がＰＯＳＴ又はＰＵＴの場合に、さらに、対応するデータ断片とデータ断片のサイズを、決定された複数の瓦記録装置のうちの１つを含むデータノードに送る。
【０４１４】
ステップＳ６００５において、要求処理部９は、決定された瓦記録装置の全てに対して、要求を送ったか判断する。
【０４１５】
決定された瓦記録装置の全てに対して、要求を送っていない場合には、要求処理部９は、ステップＳ６００４を繰り返す。
【０４１６】
決定された瓦記録装置の全てに対して、要求を送った場合には、ステップＳ６００６において、要求処理部９は、断片位置を１増加する。
【０４１７】
ステップＳ６００７において、要求処理部９は、データハッシュ値リストに含まれている全てのデータハッシュ値が読み出されたか否か判断する。
【０４１８】
データハッシュ値リストに含まれている全てのデータハッシュ値が読み出されていない場合、処理はステップＳ６００２に戻る。
【０４１９】
データハッシュ値リストに含まれている全てのデータハッシュ値が読み出された場合、ステップＳ６００８において、要求処理部９は、要求を送ったデータノードから要求に対する完了通知を待つ。
【０４２０】
ステップＳ６００９において、要求処理部９は、全ての要求に対する完了通知を受けたか否か判断する。
【０４２１】
全ての要求に対する完了通知を受けていない場合、処理はステップＳ６００８を繰り返す。
【０４２２】
全ての要求に対する完了通知を受けた場合、処理は終了する。
【０４２３】
要求処理部９は、このように、決定された瓦記録装置を含む全てのデータノードから完了通知を受けた後に、クライアント４に対する結果を生成する。
【０４２４】
図６１は、クライアント４に対する結果を生成する処理（上記図５４のステップＳ５４０９）の一例を示すフローチャートである。
【０４２５】
ステップＳ６１０１において、要求処理部９は、要求の種別を判断する。
【０４２６】
要求がＧＥＴの場合、ステップＳ６１０２において、要求処理部９は、全てのＧＥＴが成功か否か判断する。
【０４２７】
全てのＧＥＴが成功の場合、ステップＳ６１０３において、要求処理部９は、受けたデータ断片と断片位置から元のデータを復元する。
【０４２８】
ステップＳ６１０４において、復元されたデータと成功情報とを含む結果を生成する。
【０４２９】
全てのＧＥＴの要求が成功でない場合、ステップＳ６１０５において、要求処理部９は、エラーを示す結果を生成する。
【０４３０】
上記ステップＳ６１０１において要求がＰＯＳＴ、ＰＵＴ、又は、ＤＥＬＥＴＥと判断された場合、ステップＳ６１０６において、要求処理部９は、全てのＰＯＳＴ、ＰＵＴ、又は、ＤＥＬＥＴＥの要求が成功か否か判断する。
【０４３１】
全てのＰＯＳＴ、ＰＵＴ、又は、ＤＥＬＥＴＥの要求が成功の場合、ステップＳ６１０７において、要求処理部９は、成功情報を含む結果を生成する。
【０４３２】
全てのＰＯＳＴ、ＰＵＴ、又は、ＤＥＬＥＴＥの要求が成功ではない場合、上記のステップＳ６１０５において、要求処理部９は、エラーを示す結果を生成する。
【０４３３】
本実施形態において、ＰＯＳＴ又はＰＵＴによってデータの上書きが実行された場合、古いデータ断片を格納するデータノードと、新しいデータ断片を格納するデータノードとは相違する場合がある。そこで、本実施形態では、コーディネータ２−１が古いデータ断片の削除を指示する。
【０４３４】
図６２は、データＩＤテーブルを検索し、古いデータを削除する処理（上記図５４のステップＳ５４０６）の一例を示すフローチャートである。
【０４３５】
ステップＳ６２０１において、要求処理部９は、データＩＤテーブル２０に基づいて、データＩＤに対応するデータハッシュ値リストを検索する。
【０４３６】
ステップＳ６２０２において、要求処理部９は、データＩＤに対応するデータハッシュ値リストがない場合に、処理は終了する。
【０４３７】
データＩＤに対応するデータハッシュ値リストがある場合に、ステップＳ６２０３において、要求処理部９は、データハッシュ値リストのデータハッシュ値に基づいて決定されるデータノードでＤＥＬＥＴＥを実行する。
【０４３８】
ステップＳ６２０４において、要求処理部９は、データＩＤテーブル２０に対して、データＩＤに対応する更新履歴に「あり」を設定し、データハッシュ値リストを初期化（クリア）する。そして処理は終了する。
【０４３９】
本実施形態において、要求処理部９は、データの削除又は上書きが実行されたか否かを示す行進履歴をデータＩＤテーブル２０で管理し、データノード３−１〜３−Ｎへ要求を送る場合に、要求に対応する更新履歴をデータノード３−１〜３−Ｎへ送る。
【０４４０】
次に、データノード３−１〜３−Ｎ側の処理を説明する。本実施形態に係るデータノード３−１〜３−Ｎの処理は、以下の第１乃至第６の相違点で、上記第２の実施形態と異なる。
【０４４１】
第１の相違点は、データを識別するための情報が、データＩＤからデータＩＤ及び断片位置に変更され、データがデータ断片に変更される点である。
【０４４２】
第２の相違点は、後述のデータハッシュ値テーブルに基づいて重複データが管理される点である。
【０４４３】
第３の相違点は、ＰＵＴが実行される場合に、データノードが同じデータを既に保存している場合には、バンドへの書き込みが行われない点である。
【０４４４】
第４の相違点は、ＤＥＬＥＴＥが実行される場合に、バンドのデータがまだ他のデータで参照されていればこのバンドのデータは削除されない点である。
【０４４５】
第５の相違点は、瓦記録装置の増設時の移動の判断が、データＩＤのハッシュ値ではなくデータ断片をハッシュ計算したデータハッシュ値で行われる点である。
【０４４６】
第６の相違点は、瓦記録装置の増設時のデータ移動が、データＩＤのハッシュ値ではなく、データ断片のデータハッシュ値によって行われる点である。
【０４４７】
上記の相違点に基づいて、本実施形態においては、キャッシュ記録装置７−１〜７−Ｎのデータ構造と、キャッシュ処理部１２の処理とが、変更される。
【０４４８】
図６３は、本実施形態に係るキャッシュ記録装置７−１に格納されているキャッシュ情報の一例を示すデータ構造図である。図６３では、キャッシュ情報２２を論理的に図示している。
【０４４９】
キャッシュ記録装置７−１のキャッシュ情報２２は、記録装置ＩＤとその記録装置ＩＤに対する要求などとを関連付けている。要求種別がＰＯＳＴ又はＰＵＴの場合、要求には、データＩＤ、断片位置、データ断片が付される。要求種別がＧＥＴ又はＤＥＬＥＴＥの場合、要求にはデータＩＤ、断片位置が付される。
【０４５０】
図６４は、キャッシュ処理部１２の処理の一例を示すフローチャートである。
【０４５１】
ステップＳ６４０１において、キャッシュ処理部１２は、コーディネータ２−１から、要求、データＩＤ、断片位置、記録装置ＩＤを受ける。要求がＰＯＳＴ又はＰＵＴの場合には、キャッシュ処理部１２は、コーディネータ２−１から、要求、データＩＤ、断片位置、記録装置ＩＤ、データ断片とデータ断片のサイズを受ける。
【０４５２】
ステップＳ６４０２において、キャッシュ処理部１２は、要求がＧＥＴか否か判断する。
【０４５３】
要求がＧＥＴの場合、処理はステップＳ６４０５に進む。
【０４５４】
要求がＧＥＴでない場合、ステップＳ６４０３において、キャッシュ処理部１２は、記録装置ＩＤごとに、要求、データＩＤ、断片位置を、キャッシュ記録装置７−１にキャッシュする。要求がＰＵＳＴ又はＰＵＴの場合には、キャッシュ処理部１２は、記録装置ＩＤごとに、要求、データＩＤ、断片位置、データ断片及びサイズを、キャッシュ記録装置にキャッシュする。
【０４５５】
ステップＳ６４０４において、キャッシュ処理部１２は、要求がＰＯＳＴ、ＤＥＬＥＴＥ、又は、ＰＵＴの場合に、キャッシュの結果をコーディネータ２−１に返す。そして、処理は終了する。
【０４５６】
上記のステップＳ６４０２において要求がＧＥＴの場合、ステップＳ６４０５において、キャッシュ処理部１２は、コーディネータ２−１から受けた要求、記録装置ＩＤ、データＩＤ、断片位置に対応するデータ断片を検索する。
【０４５７】
ステップＳ６４０６において、キャッシュ処理部１２は、キャッシュ記録装置７−１から、コーディネータ２−１から受けた要求及び情報に対応するデータ断片がキャッシュされているか否か判断する。
【０４５８】
対応するデータ断片がキャッシュされていない場合、処理はステップＳ６４０３に進む。
【０４５９】
対応するデータ断片がキャッシュされている場合、ステップＳ６４０７において、キャッシュ処理部１２は、キャッシュ記録装置７−１から読み出され、コーディネータ２−１から受けた要求及び情報と関連するデータ断片を、コーディネータ２−１に返す。そして、処理は終了する。
【０４６０】
図６５は、データバンドテーブルの一例を示すデータ構造図である。
【０４６１】
データバンドテーブル２３は、バンドＩＤ、格納容量、書き込み先頭位置、格納されるデータ断片のデータＩＤ及び断片位置、データ特性（例えば、将来削除されるか、増設移動されるか、など）を、互いに関連付けて格納する。
【０４６２】
図６６は、ハッシュ値テーブルの一例を示すデータ構造図である。
【０４６３】
ハッシュ値テーブル２４は、ハッシュ値、データＩＤ及び断片位置、更新履歴、アドレス、サイズ、有効期限、データハッシュ値、を、互いに関連付けて格納する。
【０４６４】
図６７は、データハッシュ値テーブルの一例を示すデータ構造図である。
【０４６５】
データハッシュ値テーブル２５は、データ断片に基づいて計算されたデータハッシュ値と、データＩＤ及び断片位置とを関連付けて格納する。データハッシュ値テーブル２５において、データハッシュ値が同じデータ断片のデータＩＤ及び断片位置は、同じデータハッシュ値に関連付けられて、同じエントリに格納される。
【０４６６】
図６８は、瓦記録装置に対するＧＥＴの実行処理の一例を示すフローチャートである。
【０４６７】
ステップＳ６８０１において、要求実行部１３は、データＩＤ及び断片位置に基づいてハッシュ値を計算する。
【０４６８】
ステップＳ６８０２において、要求実行部１３は、ハッシュ値に基づいてハッシュ値テーブル２４を検索する。
【０４６９】
ステップＳ６８０３において、要求実行部１３は、ハッシュ値テーブル２４にハッシュ値に対応するエントリがあり（ハッシュ値に対応するデータＩＤ及び断片位置があり）、かつ、ハッシュ値に対応するサイズが正の値か、判断する。
【０４７０】
ハッシュ値に対応するデータＩＤ及び断片位置がない場合、又は、ハッシュ値に対応するサイズが正の値でない場合、ステップＳ６８０４において、要求実行部１３は、コーディネータ２−１に、ＧＥＴ対象のデータ断片がないことを示す結果を返し、処理は終了する。
【０４７１】
ハッシュ値に対応するデータＩＤ及び断片位置があり、ハッシュ値に対応するサイズが正の値の場合、ステップＳ６８０５において、要求実行部１３は、ハッシュ値テーブル２４から、ハッシュ値に対応するアドレスとサイズとを読み出す。
【０４７２】
ステップＳ６８０６において、要求実行部１３は、読み出されたアドレスとサイズとに基づいて、ＧＥＴ対象のデータ断片を、バンドから読み出す。
【０４７３】
ステップＳ６８０７において、要求実行部１３は、コーディネータ２−１に、読み出されたデータ断片を結果として返す。
【０４７４】
図６９は、瓦記録装置に対するＤＥＬＥＴＥの実行処理の一例を示すフローチャートである。
【０４７５】
ステップＳ６９０１において、要求実行部１３は、データＩＤ及び断片位置に基づいてハッシュ値を計算する。
【０４７６】
ステップＳ６９０２において、要求実行部１３は、ハッシュ値によりハッシュ値テーブル２４を検索する。
【０４７７】
ステップＳ６９０３において、要求実行部１３は、ハッシュ値テーブル２４にハッシュ値に対応するデータＩＤ及び断片位置があり、かつ、ハッシュ値に対応するサイズが正の値か、判断する。
【０４７８】
ハッシュ値に対応するデータＩＤ及び断片位置がない場合、又は、ハッシュ値に対応するサイズが正の値でない場合、処理は終了する。
【０４７９】
ハッシュ値に対応するデータＩＤ及び断片位置があり、かつ、ハッシュ値に対応するサイズが正の値の場合、ステップＳ６９０４において、要求実行部１３は、データハッシュ値テーブル２５に基づいて、他の重複するデータＩＤ及び断片位置があるか否か判断する。
【０４８０】
重複データがある場合には、ステップＳ６９０５において、要求実行部１３は、データハッシュ値テーブル２５とデータバンドテーブル２３とから、ハッシュ値に対応するデータＩＤ及び断片位置を削除する。その後、処理は、ステップＳ６９０９に進む。
【０４８１】
重複データがない場合には、処理はステップＳ６９０６に進む。
【０４８２】
ステップＳ６９０６において、要求実行部１３は、ハッシュ値テーブル２４のハッシュ値に対応するアドレスからＤＥＬＥＴＥ対象のバンドＩＤを決定し、ハッシュ値に対応するサイズを読み出す。
【０４８３】
ステップＳ６９０７において、要求実行部１３は、データバンドテーブル２３に対して、決定されたバンドＩＤに対応する格納容量を、ハッシュ値に対応するサイズの分減らす。また、要求実行部１３は、データバンドテーブル２３に対して、決定されたバンドＩＤに対応するＤＥＬＥＴＥ対象のデータＩＤ及び断片位置を削除する。
【０４８４】
ステップＳ６９０８において、要求実行部１３は、データバンドテーブル２３に対して、決定されたバンドＩＤに対応する格納容量がゼロになった場合には、決定されたバンドＩＤに対応する書き込み先頭位置をゼロにし、データＩＤ及び断片位置とデータ特性とを初期化し、「なし」とする。
【０４８５】
ステップＳ６９０９において、要求実行部１３は、ハッシュ値テーブル２４に対して、ハッシュ値に対応するアドレスを初期化し、サイズをゼロとし、有効期限をなしとし、更新履歴をありとする。そして、処理は、終了する。
【０４８６】
図７０は、瓦記録装置に対するＰＵＴ又はＰＯＳＴの実行処理の一例を示すフローチャートである。
【０４８７】
ステップＳ７００１において、要求実行部１３は、データ断片に基づいてデータハッシュ値を計算する。
【０４８８】
ステップＳ７００２において、要求実行部１３は、データハッシュ値に基づいてデータハッシュ値テーブル２５を検索する。
【０４８９】
ステップＳ７００３において、要求実行部１３は、データハッシュ値が重複するデータＩＤ及び断片位置が既にあるか否か判断する。
【０４９０】
重複するデータＩＤ及び断片位置がある場合、ステップＳ７００４において、要求実行部１３は、ハッシュ値テーブル２４から、重複するデータＩＤ及び断片位置に対応するアドレスとサイズとを読み出す。要求実行部１３は、データハッシュ値テーブル２５とデータバンドテーブル２３とに、ＰＵＴ又はＰＯＳＴ対象のデータＩＤ及び断片位置を格納する。その後処理は、ステップＳ７００９に進む。
【０４９１】
重複するデータＩＤ及び断片位置がない場合、ステップＳ７００５において、要求実行部１３は、ＰＵＴ又はＰＯＳＴ対象のデータ及びシステム状態に基づいて、データの情報を生成する。
【０４９２】
ステップＳ７００６において、要求実行部１３は、データバンドテーブル２３を参照し、データの情報がデータバンドテーブル２３のデータ特性を満たすバンドを選択する。
【０４９３】
ステップＳ７００７において、要求実行部１３は、選択されたバンドに対して、書き込み先頭位置からデータ断片を格納する。
【０４９４】
ステップＳ７００８において、要求実行部１３は、データバンドテーブル２３に対して、選択されたバンドＩＤに対する格納容量、書き込み先頭位置を、格納されたデータ断片のサイズ分増やす。要求実行部１３は、データバンドテーブル２３に対して、選択されたバンドＩＤに、データＩＤ及び断片位置を関連付けて格納する。要求実行部１３は、データバンドテーブル２３に対して、選択されたバンドに空き領域がなくなった場合に、選択されたバンドＩＤに対応する書き込み先頭位置に、空き領域のない状態を示す情報「−１」を設定する。
【０４９５】
ステップＳ７００９において、要求実行部１３は、ハッシュ値テーブル２４にエントリを確保し、ハッシュ値、データＩＤ及び断片位置、更新履歴、アドレス、サイズ、有効期限、データハッシュ値を格納する。そして、処理は終了する。
【０４９６】
図７１は、既存データ詰め込み処理の一例を示すフローチャートである。
【０４９７】
ステップＳ７１０１において、要求実行部１３は、データバンドテーブル２３を参照し、バンドに格納されているデータＩＤ及び断片位置に基づいて、バンドの既存データを１回読み出す。
【０４９８】
ステップＳ７１０２において、要求実行部１３は、バンドから全ての既存データが読み出されたか否か判断する。
【０４９９】
全ての既存データが読み出されていない場合には、処理はステップＳ７１０１を繰り返す。
【０５００】
全ての既存データが読み出された場合、ステップＳ７１０３において、要求実行部１３は、読み出されたデータを元のバンドに詰めた状態で格納する。
【０５０１】
ステップＳ７１０４において、要求実行部１３は、ハッシュ値テーブル２４に対して、バンドに詰めた状態で格納されたデータに対するアドレスを更新する。
【０５０２】
ステップＳ７１０５において、要求実行部１３は、全ての読み出されたデータをバンドに格納したか否か判断する。
【０５０３】
全ての読み出されたデータがバンドに格納されていない場合、処理はステップ７１０３に戻る。
【０５０４】
全ての読み出されたデータがバンドに格納された場合、処理は終了する。
【０５０５】
図７２は、データが瓦記録装置増設時に移動される可能性があるか否かの判断により格納先のバンクを選択する処理の一例を示すフローチャートである。
【０５０６】
ステップＳ７２０１において、要求実行部１３は、データハッシュ値に基づいて、データに対して次回の瓦記録装置増設時の移動の可能性を判断する。
【０５０７】
移動の可能性がない場合、処理は終了する。
【０５０８】
移動の可能性がある場合、ステップＳ７２０２において、要求実行部１３は、データの格納先として、データバンドテーブル２３のデータ特性で増設移動が設定されているバンドを選択する。
【０５０９】
図７３は、瓦記録装置増設時に移動する可能性に応じてデータの格納先のバンドを分けた状態の一例を示す図である。
【０５１０】
ある瓦記録装置に格納されるデータは、データハッシュ値が１０００１〜２００００のデータである。この瓦記録装置において、データハッシュ値１０００１〜１５０００のデータは瓦記録装置が増設されても移動しないが、データハッシュ値１５００１〜２００００のデータは移動する。そこで、要求実行部１３は、データハッシュ値が１５００１〜２００００であるか否か判断し、判断結果に応じてバンドを選択する。
【０５１１】
これにより、瓦記録装置が増設され、データハッシュ値が１５００１〜２００００のデータを増設された瓦記録装置へ移動させ、移動されたデータが元の瓦記録装置から削除されると、まとまった空きバンドを多数生成することができる。これらの空きバンドへの格納は、そのまま上書きすることができ、書き込み時間が延びることを防止することができる。
【０５１２】
図７４は、増設管理部１０の処理の一例を示すフローチャートである。増設管理部１０は、増設要求の発行元のコントローラ６−１から増設処理が完了通知を受けた段階で、データハッシュ値範囲テーブル２１を変更する。
【０５１３】
ステップＳ７４０１において、増設管理部１０は、コントローラ６−１からの増設要求を受ける。
【０５１４】
ステップＳ７４０２において、増設管理部１０は、増設された瓦記録装置の記録装置ＩＤを決定する。
【０５１５】
ステップＳ７４０３において、増設管理部１０は、分割されるデータハッシュ値の範囲を決定する。
【０５１６】
ステップＳ７４０４において、増設管理部１０は、増設要求を発行したコントローラ６−１に、増設された瓦記録装置の記録装置ＩＤ、移動されるデータハッシュ値の範囲を通知し、移動完了の通知を待つ。
【０５１７】
ステップＳ７４０５において、増設管理部１０は、データハッシュ値範囲テーブル２１を変更する。
【０５１８】
ステップＳ７４０６において、増設管理部１０は、他のコーディネータへ、データハッシュ値範囲テーブル２１の変更を通知する。
【０５１９】
図７５は、増設後のデータハッシュ値範囲テーブル２１の一例を示すデータ構造図である。
【０５２０】
増設前の１０００１〜２００００のデータハッシュ値範囲が、増設により、１０００１〜１５０００のデータハッシュ値範囲と、１５００１〜２００００のデータハッシュ値範囲とに分割されている。増設された瓦記録装置８−１−９，８−２−９，８−３−９は、１５００１〜２００００のデータハッシュ値範囲に割り当てられている。より具体的に説明すると、増設前は、１０００１〜２００００のデータハッシュ値範囲が、瓦記録装置８−４−１，８−５−１，８−６−１で担当されていた。瓦記録装置８−１−９，８−２−９，８−３−９が増設されると、１０００１〜１５０００のデータハッシュ値範囲は、瓦記録装置８−４−１，８−５−１，８−６−１で担当され、１５００１〜２００００のデータハッシュ値範囲は、瓦記録装置８−１−９，８−２−９，８−３−９で担当される。増設後のデータハッシュ値範囲テーブル２１は、全てのコーディネータに通知される。これにより、コーディネータ２−１，２−２は、増設された瓦記録装置８−１−９，８−２−９，８−３−９をアクセス可能になる。
【０５２１】
図７６は、増設処理部１４の処理の一例を示すフローチャートである。
【０５２２】
ステップＳ７６０１において、増設処理部１４は、データバンドテーブル２３に対して、格納容量が第１の所定値以下のバンド数を計算する。
【０５２３】
ステップＳ７６０２において、増設処理部１４は、計算されたバンド数が第２の所定値以上か否か判断する。
【０５２４】
バンド数が第２の所定値以上の場合、処理は終了する。
【０５２５】
バンド数が第２の所定値未満の場合、ステップＳ７６０３において、増設処理部１４は、コーディネータ２−１に、瓦記録装置の増設要求を送る。
【０５２６】
ステップＳ７６０４において、増設処理部１４は、コーディネータ２−１から、増設された瓦記録装置の記録装置ＩＤ、移動されるデータハッシュ値範囲を受ける。
【０５２７】
ステップＳ７６０５において、増設処理部１４は、増設された瓦記録装置を担当するコントローラに、増設された瓦記録装置の記録装置ＩＤ、移動されるデータハッシュ値範囲を送る。
【０５２８】
ステップＳ７６０６において、増設処理部１４は、移動されるデータハッシュ値範囲内のデータを、増設された瓦記録装置を担当するコントローラに送る。
【０５２９】
ステップＳ７６０７において、増設処理部１４は、コーディネータ２−１に、増設完了通知を送り、移動された全データの情報を、データバンドテーブル２３、データハッシュ値テーブル２５から削除する。そして、処理は終了する。
【０５３０】
図７７は、移動されるデータハッシュ値範囲内のデータを、増設された瓦記録装置を担当するコントローラに送る処理（図７６のステップＳ７６０６）の一例を示すフローチャートである。
【０５３１】
ステップＳ７７０１において、増設処理部１４は、データハッシュ値テーブル２５のデータＩＤ及び断片位置を順次読み出す。
【０５３２】
ステップＳ７７０２において、増設処理部１４は、読み出されたデータＩＤ及び断片位置で示されるデータ断片のデータハッシュ値が、移動されるデータハッシュ値範囲か否か判断する。
【０５３３】
データハッシュ値が、移動されるデータハッシュ値範囲でない場合、処理はステップＳ７７０５に進む。
【０５３４】
データハッシュ値が、移動されるデータハッシュ値範囲の場合、ステップＳ７７０３において、増設処理部１４は、ハッシュ値テーブル２４から、データＩＤ及び断片位置に対応するアドレスのデータ断片を、バンドから読み出す。
【０５３５】
ステップＳ７７０４において、増設処理部１４は、読み出されたデータ断片と、ハッシュ値テーブル２４のデータＩＤ及び断片位置、更新履歴、有効期限を、増設された瓦記録装置を担当するコントローラに送る。
【０５３６】
ステップＳ７７０５において、増設処理部１４は、ハッシュ値テーブル２４の全てのデータＩＤ及び断片位置を処理したか否か判断する。
【０５３７】
ハッシュ値テーブル２４の全てのデータＩＤ及び断片位置を処理していない場合、処理はステップＳ７７０１に戻る。
【０５３８】
ハッシュ値テーブル２４の全てのデータＩＤ及び断片位置を処理した場合、増設処理部１４は、増設された瓦記録装置を担当するコントローラに終了通知を送り、処理は終了する。
【０５３９】
図７８は、増設された瓦記録装置を担当するコントローラの処理の一例を示すフローチャートである。
【０５４０】
ステップＳ７８０１において、増設処理部１４は、増設要求の発行元のコントローラから、増設された瓦記録装置の記録装置ＩＤ、移動されるデータハッシュ値範囲を受ける。
【０５４１】
ステップＳ７８０２において、増設処理部１４は、移動されるデータハッシュ値範囲に基づいて、データバンドテーブル２３、ハッシュ値テーブル２４、データハッシュ値テーブル２５を初期化する。
【０５４２】
ステップＳ７８０３において、増設処理部１４は、増設要求の発行元のコントローラから、データ断片、データＩＤ及び断片位置、更新履歴、有効期限を受ける。
【０５４３】
ステップＳ７８０４において、増設処理部１４は、増設要求の発行元のコントローラから受けたデータ断片を新規に格納されるデータとみなしてＰＯＳＴ又はＰＵＴを実行する。
【０５４４】
ステップＳ７８０５において、増設処理部１４は、増設要求の発行元のコントローラから、終了通知を受けたか否か判断する。
【０５４５】
終了通知を受けていない場合、処理はステップＳ７８０３に戻る。
【０５４６】
終了通知を受けた場合、処理は終了する。
【０５４７】
以上説明した本実施形態においては、格納されるデータの重複を防止してストレージシステム１の容量効率を向上させることができ、瓦記録装置が増設された場合の処理を効率化することができ、書き込み時間を抑えることができる。
【０５４８】
上記の各実施形態で説明した各種の構成要素は、適宜組み合わせてもよく、分割してもよい。例えば、管理部１０８と再分類設定部１１２とは組み合わせてもよい。実行部１０７、期限削除部１０９、増設格納部１１０、増設削除部１１１は、組み合わせてもよい。再分類部１１３のうちのバンドを選択する機能は選択部１０６で実現してもよく、データを格納する機能は実行部１０７で実現してもよい。バンド管理情報１１４とデータ管理情報１１５とは、組み合わせてもよい。
【０５４９】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる
【符号の説明】
【０５５０】
１０１，１０１Ａ…ストレージ装置、１０２，１０２Ａ…コントローラ、１０３，１０５…瓦記録装置、１０４…記録装置、１０６，１０６Ａ…選択部、１０７，１０７Ａ…実行部、１０８，１０８Ａ…管理部、１０９，１０９Ａ…期限削除部、１１０，１１０Ａ…増設格納部、１１１，１１１Ａ…増設削除部、１１２，１１２Ａ…再分類設定部、１１３，１１３Ａ…再分類部、１１４，１１４Ａ…バンド管理情報、１１５，１１５Ａ…データ管理情報、１１６…分割部、１１７…復元部、１１８…結合部、１…ストレージシステム、２−１，２−２…コーディネータ、３−１〜３−Ｎ…データノード、４…クライアント、５…ネットワーク、６−１〜６−Ｎ…コントローラ、７−１〜７−Ｎ…キャッシュ記録装置、８−１−１〜８−Ｎ−９…瓦記録装置、９…要求処理部、１０…増設管理部、１１…ハッシュ値範囲テーブル、１２…キャッシュ処理部、１３…要求実行部、１４…増設処理部、１５，２２…キャッシュ情報、１６…管理バンド、１７…データバンド、１８，２３…データバンドテーブル、１９，２４…ハッシュ値テーブル、２０…データＩＤテーブル、２１…データハッシュ値範囲テーブル、２５…データハッシュ値テーブル
【図１】
0006396161.tif 000002
【図２】
0006396161.tif 000003
【図３】
0006396161.tif 000004
【図４】
0006396161.tif 000005
【図５】
0006396161.tif 000006
【図６】
0006396161.tif 000007
【図７】
0006396161.tif 000008
【図８】
0006396161.tif 000009
【図９】
0006396161.tif 000010
【図１０】
0006396161.tif 000011
【図１１】
0006396161.tif 000012
【図１２】
0006396161.tif 000013
【図１３】
0006396161.tif 000014
【図１４】
0006396161.tif 000015
【図１５】
0006396161.tif 000016
【図１６】
0006396161.tif 000017
【図１７】
0006396161.tif 000018
【図１８】
0006396161.tif 000019
【図１９】
0006396161.tif 000020
【図２０】
0006396161.tif 000021
【図２１】
0006396161.tif 000022
【図２２】
0006396161.tif 000023
【図２３】
0006396161.tif 000024
【図２４】
0006396161.tif 000025
【図２５】
0006396161.tif 000026
【図２６】
0006396161.tif 000027
【図２７】
0006396161.tif 000028
【図２８】
0006396161.tif 000029
【図２９】
0006396161.tif 000030
【図３０】
0006396161.tif 000031
【図３１】
0006396161.tif 000032
【図３２】
0006396161.tif 000033
【図３３】
0006396161.tif 000034
【図３４】
0006396161.tif 000035
【図３５】
0006396161.tif 000036
【図３６】
0006396161.tif 000037
【図３７】
0006396161.tif 000038
【図３８】
0006396161.tif 000039
【図３９】
0006396161.tif 000040
【図４０】
0006396161.tif 000041
【図４１】
0006396161.tif 000042
【図４２】
0006396161.tif 000043
【図４３】
0006396161.tif 000044
【図４４】
0006396161.tif 000045
【図４５】
0006396161.tif 000046
【図４６】
0006396161.tif 000047
【図４７】
0006396161.tif 000048
【図４８】
0006396161.tif 000049
【図４９】
0006396161.tif 000050
【図５０】
0006396161.tif 000051
【図５１】
0006396161.tif 000052
【図５２】
0006396161.tif 000053
【図５３】
0006396161.tif 000054
【図５４】
0006396161.tif 000055
【図５５】
0006396161.tif 000056
【図５６】
0006396161.tif 000057
【図５７】
0006396161.tif 000058
【図５８】
0006396161.tif 000059
【図５９】
0006396161.tif 000060
【図６０】
0006396161.tif 000061
【図６１】
0006396161.tif 000062
【図６２】
0006396161.tif 000063
【図６３】
0006396161.tif 000064
【図６４】
0006396161.tif 000065
【図６５】
0006396161.tif 000066
【図６６】
0006396161.tif 000067
【図６７】
0006396161.tif 000068
【図６８】
0006396161.tif 000069
【図６９】
0006396161.tif 000070
【図７０】
0006396161.tif 000071
【図７１】
0006396161.tif 000072
【図７２】
0006396161.tif 000073
【図７３】
0006396161.tif 000074
【図７４】
0006396161.tif 000075
【図７５】
0006396161.tif 000076
【図７６】
0006396161.tif 000077
【図７７】
0006396161.tif 000078
【図７８】
0006396161.tif 000079