(57)【特許請求の範囲】
【請求項１】
高速小容量の記憶装置を用いた１次ストレージと、低速大容量の記憶装置を用いた２次ストレージで構成され、前記１次ストレージを前記２次ストレージのキャッシュ装置として使用し、前記１次ストレージと前記２次ストレージ間でアクセス頻度や必要性に応じてデータの再配置を行う階層記憶部と、
前記１次ストレージにデータブロックを書き込んだ際に、タイムスタンプを格納したブロック情報テーブルを揮発メモリ上に生成して管理すると共に前記揮発メモリ上のブロック情報テーブルを所定タイミング毎に前記１次ストレージに書き込んで保存するブロック情報テーブル管理部と、
前記ブロック情報テーブルを生成した際に、タイムスタンプ順となる位置に前記ブロック情報テーブルを挿入してポインタにより繋げたリンクを前記揮発メモリ上に生成すると共に、前記ポインタを格納したリンクテーブルを生成して前記揮発メモリ上で管理するリンク管理部と、
上位装置からデータブロックの入出力要求を受けた際に、マッピングチェックに基づいて前記階層記憶部の入出力処理を実行する入出力処理部と、
を備えた階層ストレージシステムに於いて、
電源再投入時に、前記１次ストレージから前記揮発メモリに前記ブロック情報テーブルをリストアするリストア処理部と、
リストアした前記ブロック情報テーブルを、複数の時間帯に分けたグループ別リンクに分類し前記揮発性メモリにリストアされているブロック情報テーブルをアドレス順に繋ぎ、このグループ分け終了後に、各グループ別リンクを時間順に繋げてグループ分類リンクを構成する第１ソート部と、
前記グループ分類リンクのブロック情報テーブルを最古のタイムスタンプ側から順番に取り出してタイムスタンプの昇順に並ぶ位置に挿入して前記リンクを再構築する第２ソート処理部と、
を備えたことを特徴とする階層ストレージシステム。
【請求項２】
請求項１記載の階層ストレージシステムに於いて、
前記第１ソート処理部は、
リストアした前記ブロック情報テーブルから検索した最古のタイムスタンプから最新のタイムスタンプまでの時間を所定数の時間帯に分割して複数のグループ別リンクを生成し、
前記ブロック情報テーブルをアドレス順に取出してタイムスタンプの属する時間帯のグループ別リンクに挿入してアドレス順に繋ぎ、
グループ分け終了後に、各グループ別リンクを時間順に繋げてグループ分類リンクを構成することを特徴とする階層ストレージシステム。
【請求項３】
請求項２記載の階層ストレージシステムに於いて、
前記グループ別リンクは、
最新のタイムスタンプから最古のタイムスタンプを減算した結果をグループ数で除算してグループ間差分値を求め、最新のタイムスタンプから前記グループ間差分値を減算した第１のグループ基準値を求め、該第１のグループ基準値から最新のタイムスタンプ方向にグループ間差分値分の範囲を第１のグループ範囲として定め、
前記第１のグループ基準値から前記グループ間差分値を減算した第２のグループ基準値を求め、該第２のグループ基準値から最新のタイムスタンプ方向にグループ間差分値の範囲を第２のグループ基準値として求め、
これらの処理をグループ数分だけ順次行うことを特徴とする階層ストレージシステム。
【請求項４】
請求項１記載の階層ストレージシステムに於いて、
前記第２ソート処理部は、
前記リンクのＬＲＵ側を前方とし、ＭＲＵ側を後方として処理対象テーブルを整列済みリンクのタイムスタンプ順となる位置に挿入する繋ぎ替え処理として、
挿入位置前テーブル（Ａ）が存在する否かの第１条件、
処理対象テーブル（Ｙ）の対象位置後テーブル（Ｚ）が存在するか否かの第２条件、更に
挿入位置後テーブル（Ｂ）と処理対象テーブル（Ｙ）が隣接しているか否かの第３条件、
の３条件の組合せに基づく８つの繋ぎ替え処理ケースを予め設定し、
処理対象テーブルを取出すごとに前記３条件を判定して該当する繋ぎ替え処理ケースを選択して繋ぎ替え処理を実行することを特徴とする階層ストレージシステム。
【請求項５】
高速小容量の記憶装置を用いた１次ストレージと、低速大容量の記憶装置を用いた２次ストレージで構成され、ディスクアレイ装置が前記１次ストレージを前記２次ストレージのキャッシュ装置として使用し、前記１次ストレージと前記２次ストレージ間でアクセス頻度や必要性に応じてデータの再配置を行う階層記憶部と、
前記１次ストレージにデータブロックを書き込んだ際に、タイムスタンプを格納したブロック情報テーブルを揮発メモリ上に生成して管理すると共に前記揮発メモリ上のブロック情報テーブル群を所定タイミング毎に前記１次ストレージに書き込んで保存するようにディスクアレイ装置の構成管理部に設けたブロック情報テーブル管理部と、
前記ブロック情報テーブルを生成した際に、タイムスタンプ順となる位置に前記ブロック情報テーブルを挿入してポインタにより繋げたリンクを前記揮発メモリ上に生成すると共に、前記ポインタを格納したリンクテーブルを生成して前記揮発メモリ上で管理するディスクアレイ装置の構成管理部に設けたリンク管理部と、
上位装置からデータブロックの入出力要求を受けた際に、マッピングチェックに基づいて前記階層記憶部の入出力処理を実行する仮想ディスク処理部に設けた入出力処理部と、
を備えた階層ストレージシステムの制御方法に於いて、
ディスクアレイ装置の構成管理部に設けたリストア部が電源再投入時に、前記１次ストレージから前記揮発メモリに前記ブロック情報テーブルをリストアするリストア処理ステップと、
ディスクアレイ装置の構成管理部に設けた第１ソート処理部がリストアした前記ブロック情報テーブルを、複数の時間帯に分けたグループ別リンクに分類し前記揮発性メモリにリストアされているブロック情報テーブルをアドレス順に繋ぎ、このグループ分け終了後に、各グループ別リンクを時間順に繋げてグループ分類リンクを構成する第１ソート処理ステップと、
ディスクアレイ装置の構成管理部に設けた第２ソート処理部が前記グループ分類リンクのブロック情報テーブルを最古のタイムスタンプ側から順番に取り出してタイムスタンプの昇順に並ぶ位置に挿入して前記リンクを再構築する第２ソート処理ステップと、
を備えたことを特徴とする階層ストレージシステムの制御方法。
【請求項６】
高速小容量の記憶装置を用いた１次ストレージと、低速大容量の記憶装置を用いた２次ストレージで構成され、前記１次ストレージを前記２次ストレージのキャッシュ装置として使用し、前記１次ストレージと前記２次ストレージ間でアクセス頻度や必要性に応じてデータの再配置を行う階層記憶部と、
前記１次ストレージにデータブロックを書き込んだ際に、タイムスタンプを格納したブロック情報テーブルを揮発メモリ上に生成して管理すると共に前記揮発メモリ上のブロック情報テーブル群を所定タイミング毎に前記１次ストレージに書き込んで保存するブロック情報テーブル管理部と、
前記ブロック情報テーブルを生成した際に、タイムスタンプ順となる位置に前記ブロック情報テーブルを挿入してポインタにより繋げたリンクを前記揮発メモリ上に生成すると共に、前記ポインタを格納したリンクテーブルを生成して前記揮発メモリ上で管理するリンク管理部と、
上位装置からデータブロックの入出力要求を受けた際に、マッピングチェックに基づいて前記階層記憶部の入出力処理を実行する入出力処理部と、
を備えた階層ストレージシステムのコンピュータに、
電源再投入時に、前記１次ストレージから前記揮発メモリに前記ブロック情報テーブルをリストアするリストア処理ステップと、
リストアした前記ブロック情報テーブルを、複数の時間帯に分けたグループ別リンクに分類し前記揮発性メモリにリストアされているブロック情報テーブルをアドレス順に繋ぎ、このグループ分け終了後に、各グループ別リンクを時間順に繋げてグループ分類リンクを構成する第１ソート処理ステップと、
前記グループ分類リンクのブロック情報テーブルを最古のタイムスタンプ側から順番に取り出してタイムスタンプの昇順に並ぶ位置に挿入して前記リンクを再構築する第２ソート処理ステップと、
を実行させることを特徴とする階層ストレージ制御プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ディスク装置等の１次ストレージと磁気テープ装置等の２次ストレージによる階層記憶構造を備えた階層ストレージシステム、制御方法及びプログラムに関し、特に、１次ストレージを２次ストレージのキャッシュ記憶装置のように利用し、また１次ストレージと２次ストレージ間で自律型データ再配置運用を可能とするために使用するリンクを電源再投入時にタイムスタンプ順にソートして再構築する階層ストレージシステム、制御方法及びプログラムに関する。
【背景技術】
【０００２】
従来、ペタバイトサイズとなる大容量のストレージシステムとして、１次ストレージに磁気ディスク装置等の高速記憶デバイスを使用し、２次ストレージに磁気テープ装置等の低速記憶デバイスを使用したデータ階層構造をもつ階層ストレージシステムが構築されている。
【０００３】
大容量階層ストレージシステムは、１次ストレージを２次ストレージのキャッシュ装置として扱うことで、アクセス頻度の高いデータをホストから近い１次ストレージに配置し、アクセス頻度の低いデータをホストから遠い２次ストレージに配置してアクセス性能を高めるようにしている。
【０００４】
１次ストレージを２次ストレージのキャッシュ装置として使用する階層ストレージの入出力処理にあっては、１次ストレージ及び２次ストレージにおけるデータ入出力単位であるデータブロックごとにブロック情報テーブルを作成して管理している。このブロック情報テーブルは、上位装置から１次ストレージにブロックデータを書き込んだ際にメモリ上に生成され、書込み時刻を示すタイムスタンプや階層記憶におけるステータス等が格納されている。またブロック情報テーブルと同時にリンクテーブルがメモリ上に作成され、ブロック情報テーブルをタイムスタンプ順にポインタで繋いだリンクを構築する。
【０００５】
ブロック情報テーブルをタイムスタンプ順にポインタで繋いだリンクとしては、ダーティリンク、ヒットリンク、ＬＲＵリンク等がある。ヒットリンクは１次ストレージと２次ストレージの両方に存在する同期がとられたデータブロックのブロック情報テーブルをタイムスタンプ順に繋げている。
【０００６】
ダーティリンクは、１次ストレージに存在するが、２次ストレージに存在しないか又は存在するが同期がとられていないデータブロックのブロック情報テーブルをタイムスタンプ順に繋げている。更に、ＬＲＵリンクは１次ストレージに存在する全てのデータブロックのブロック情報テーブルをタイムスタンプ順に繋げている。
【０００７】
更にメモリ上のブロック情報テーブルは所定のタイミング毎に１次ストレージのシステム領域に書き込まれることでバックアップされている。
【特許文献１】特開平９−２９７６９９号公報
【特許文献２】特開昭６０−１７９８５７号公報
【特許文献３】特開平０２−１２３４３８号公報
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、このような従来の階層ストレージシステムにあっては、メモリ上で管理しているブロック情報テーブル及びリンクテーブルを１次ストレージのシステムボリュームに保存し、電源遮断で消失してもバックアップできるようにする必要があるが、１次ボリュームにおけるバックアップ領域の制約からブロック情報テーブルのみをバックアップし、リンクテーブルはバックアップしていない問題がある。
【０００９】
これは２次ストレージのキャッシュ装置として機能する１次ストレージに格納可能なデータブロックは、例えば１次ストレージの容量を３２テラバイト（ＴＢ）とし、ブロックサイズを２５６メガバイト（ＭＢ）とした場合、約１５万ブロックとかなりの数となり、これに対応した数のブロック情報テーブルがメモリ上に生成されており、１次ストレージのシステムボリュームには、１５万ブロック分のブロック情報テーブルをバックアップのために保存する領域を確保する必要がある。
【００１０】
これに加えて１５万ブロック分のブロック情報テーブルをタイムスタンプ順につなげたダーティリンクやヒットリンクのポインタを格納したリンクテーブルの保存領域をシステムボリュームに確保することは、１次ストレージのシステムボリューム割当領域が増加してユーザー領域が制約されるため、更には、電源遮断時における全面バックアップ時間を短縮するために、リンクテーブルについては２次ストレージに保存するバックアップを行っていない。
【００１１】
また、電源遮断時にリンクテーブルをバックアップし、電源再投入時にリンクを再構築する手法では、複数枚あるメモリの一部が電源投入時にデグレードし、切離されると、「ブロック情報テーブルの前後関係をポインタで繋いでいる」というリンクの性格から、リンクがこわれてしまうことからも、リンクテーブルについては２次ストレージへのバックアップは行っていない。
【００１２】
このため階層ストレージシステムの運用中に、電源を遮断して再投入した場合、電源の遮断によりメモリ上のダーティリンク、ヒットリンク及びＬＲＵリンクを構築しているリンクテーブルが消えてしまう。そこで、電源を再投入した後の初期化処理中に、１次ストレージに保存しているブロック情報テーブルをメモリにリストアし、ブロック情報テーブルをステータスによりヒット、ダーティに分け、それぞれタイムスタンプ順に繋げたヒットリンク、ダーティリンク、ＬＲＵリンクを再構築する必要がある。
【００１３】
しかし、リンクを再構築する際には、まずメモリ上にリストアしたブロック情報テーブルをアドレス順に検索してポインタにより繋げて初期リンクを構築するが、この初期リンクはタイムスタンプ順に繋がっていない。このため初期リンクについて、リンクの先頭からブロック情報テーブルのタイムスタンプを調べ、タイムスタンプの古い順に並び替えるソート処理が必要になる。
【００１４】
しかしながら、再構成したテーブルリンクは、最長で１次ストレージのブロックサイズに対応した例えば１５万個にも及ぶリンク長をもっており、このような長大なリンクをタイムスタンプ順に並び替えるソート処理には相当な時間がかかる。特に、電源再投入から初期化処理が済んで入出力処理が可能となるまでには、長くても数分程度の時間しか許されておらず、この初期化中に再構成したリンクのソート処理を終えることができない。
【００１５】
そこで従来システムでは、再構成したリンクについては、タイムスタンプ順に並べ替えるソート処理は行わず、アドレス順のままとし、電源再投入後にホストからのライトコマンドで書き込まれたデータブロックのブロック情報テーブルについて、リンク上でのタイムスタンプ順の整列を保証している。
【００１６】
このため電源の再投入前に生成したブロック情報テーブルのリンク部分については、タイムスタンプ順に並べられておらず、例えば１次ストレージに空き領域を確保するためヒットリンクの古いほう（ＬＲＵ側）のテーブルを追い出す場合、タイムスタンプの新しいデータブロックが追い出され、タイムスタンプの古いデータブロックが残ってしまい、１次ストレージに対する入出力要求がヒットせずに２次ストレージにアクセスする頻度が高まり、システムの入出力性能が低下する問題がある。
【００１７】
本発明は、電源を再投入した際にタイムスタンプ順に並んだテーブルリンクの再構成を高速且つ短時間で実現可能とする階層ストレージシステム、制御方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１８】
この目的を達成するため本発明は次のように構成する。図１は本発明の原理説明図である。
【００１９】
（システム）
本発明は、階層ストレージシステムを提供する。本発明が対象とする階層ストレージシステムは、
高速小容量の記憶装置を用いた１次ストレージ６８と、低速大容量の記憶装置を用いた２次ストレージ７０で構成され、１次ストレージ６８を２次ストレージ７０のキャッシュ装置として使用する階層記憶部と、
１次ストレージ６８にデータブロックを書き込んだ際に、タイムスタンプを格納したブロック情報テーブルを揮発メモリ上に生成して管理すると共に揮発メモリ上のブロック情報テーブル群を所定タイミング毎に１次ストレージ６８に書き込んで保存するブロック情報テーブル管理部８８と、
ブロック情報テーブルを生成した際に、タイムスタンプ順となる位置にブロック情報テーブルを挿入してポインタにより繋げたリンクを揮発メモリ上に生成すると共に、ポインタを格納したリンクテーブルを生成して揮発メモリ上で管理するリンク管理部９０と、
上位装置からデータブロックの入出力要求を受けた際に、マッピングチェックに基づいて階層記憶部の入出力処理を実行する入出力処理部８２と、
を備える。
【００２０】
このような階層ストレージシステムについて本発明は、
電源再投入時に、１次ストレージ６８から揮発メモリにブロック情報テーブルをリストアするリストア処理部９２と、
リストアしたブロック情報テーブルを、複数の時間帯に分けたグループ別リンクに分類した後に、各グループ別リンクを時間順に繋げてグループ分類リンクを構成する第１ソート処理部９４と
グループ分類リンクのブロック情報テーブルを最古のタイムスタンプ側から順番に取り出してタイムスタンプの昇順に並ぶ位置に挿入してリンクを再構築する第２ソート処理部９６と、
を設けたことを特徴とする。
【００２１】
ここで、リンク管理部は、リストア処理部により揮発メモリにブロック情報テーブルをリストアした際に、各ブロック情報テーブルに対応してリンクテーブルを生成し、第１ソート処理部及び第２ソート処理部でリンクを構成する際に、リンクを繋ぐポインタをリンクテーブルに格納する。
【００２２】
第１ソート処理部は、
リストアしたブロック情報テーブルから検索した最古のタイムスタンプから最新のタイムスタンプまでの時間を所定数の時間帯に分割して複数のグループ別リンクを生成し、
ブロック情報テーブルをアドレス順に取出してタイムスタンプの属する時間帯のグループ別リンクに挿入してアドレス順に繋ぎ、
グループ分け終了後に、各グループ別リンクを時間順に繋げてグループ分類リンクを構成する。
【００２３】
第２ソート処理部は、
リンクのＬＲＵ側を前方とし、ＭＲＵ側を後方として処理対象テーブルを整列済みリンクのタイムスタンプ順となる位置に挿入する繋ぎ替え処理ケースとして、
（１）挿入位置前テーブル（Ａ）が存在する否かの第１条件、
（２）処理対象テーブル（Ｙ）の後の対象位置後テーブル（Ｚ）が存在するか否かの第２条件、更に
（３）挿入位置後テーブル（Ｂ）と処理対象テーブル（Ｙ）が隣接しているか否かの第３条件、
の３条件の組合せに基づく８つの繋ぎ替え処理ケースを予め設定し、処理対象テーブルを取出すごとに３条件を判定して該当する繋ぎ替え処理ケースを選択して繋ぎ替え処理を実行する。
【００２４】
（第１ケース）
第２ソート処理部は、前記３条件として、挿入位置前テーブル（Ａ）が存在し、処理対象テーブル（Ｙ）の対象位置後テーブル（Ｚ）が存在し、更に挿入位置後テーブル（Ｂ）と処理対象テーブル（Ｙ）が隣接していない場合の第１ケースとして、
挿入位置前テーブル（Ａ）の後ポインタを処理対象テーブル（Ｙ）に変更し、
挿入位置後テーブル（Ｂ）の前ポインタを処理対象テーブル（Ｙ）に変更し、
処理対象位置前テーブル（Ｘ）の後ポインタを対象位置後テーブル（Ｚ）に変更し、更に、
処理対象テーブル（Ｙ）の前ポインタを挿入位置前テーブル（Ａ）に変更すると共に後ポインタを挿入位置後テーブル（Ｂ）に変更する。
【００２５】
（第２ケース）
第２ソート処理部は、３条件として、挿入位置前テーブル（Ａ）が存在し、処理対象テーブル（Ｙ）の対象位置後テーブル（Ｚ）が存在し、更に挿入位置後テーブル（Ｂ）と処理対象テーブル（Ｙ）が隣接している場合の第２ケースとして、
挿入位置前テーブル（Ａ）の後ポインタを処理対象テーブル（Ｙ）に変更し、
挿入位置後テーブル（Ｂ）の前ポインタを処理対象テーブル（Ｙ）に変更すると共に後ポインタを対象位置後テーブル（Ｚ）に変更し、
処理対象テーブル（Ｙ）の前ポインタを挿入位置前テーブル（Ａ）に変更すると共に後ポインタを挿入位置後テーブル（Ｂ）に変更し、更に、
対象位置後テーブル（Ｚ）の後ポインタを挿入位置後テーブル（Ｂ）に変更する。
【００２６】
（第３ケース）
第２ソート処理部は、３条件として、挿入位置前テーブル（Ａ）が存在し、処理対象テーブル（Ｙ）の対象位置後テーブル（Ｚ）が存在せず、更に挿入位置後テーブル（Ｂ）と処理対象テーブル（Ｙ）が隣接していない場合の第３ケースとして、
挿入位置前テーブル（Ａ）の後ポインタを処理対象テーブル（Ｙ）に変更し、
挿入位置後テーブル（Ｂ）の前ポインタを処理対象テーブル（Ｙ）に変更し、
対象位置前テーブル（Ｘ）の後ポインタをリンク後端（ＮＵＬＬ）に変更し、更に、
処理対象テーブル（Ｙ）の前ポインタを挿入位置前テーブル（Ａ）に変更すると共に後ポインタを挿入位置後テーブル（Ｂ）に変更する。
【００２７】
（第４ケース）
第２ソート処理部は、３条件として、挿入位置前テーブル（Ａ）が存在し、処理対象テーブル（Ｙ）の対象位置後テーブル（Ｚ）が存在せず、更に挿入位置後テーブル（Ｂ）と処理対象テーブル（Ｙ）が隣接している場合の第４ケースとして、
挿入位置前テーブル（Ａ）の後ポインタを処理対象テーブル（Ｙ）に変更し、
挿入位置後テーブル（Ｂ）の前ポインタを処理対象テーブル（Ｙ）に変更すると共に後ポインタをリンク後端（ＮＵＬＬ）に変更し、更に、
処理対象テーブル（Ｙ）の前ポインタを挿入位置前テーブル（Ａ）に変更すると共に後ポインタを挿入位置後テーブル（Ｂ）に変更する。
【００２８】
（第５ケース）
第２ソート処理部は、３条件として、挿入位置前テーブル（Ａ）が存在せず、処理対象テーブル（Ｙ）の対象位置後テーブル（Ｚ）が存在し、更に挿入位置後テーブル（Ｂ）と処理対象テーブル（Ｙ）が隣接していない場合の第５ケースとして、
挿入位置後テーブル（Ｂ）の前ポインタを処理対象テーブル（Ｙ）に変更し、
対象位置前テーブル（Ｘ）の後ポインタを対象位置後テーブル（Ｚ）に変更し、
処理対象テーブル（Ｙ）の前ポインタをリンク先端（ＮＵＬＬ）に変更すると共に後ポインタを挿入位置後テーブル（Ｂ）に変更し、更に
対象位置後テーブル（Ｚ）の前ポインタを対象位置前テーブル（Ｘ）に変更する。
【００２９】
（第６ケース）
第２ソート処理部は、３条件として、挿入位置前テーブル（Ａ）が存在せず、処理対象テーブル（Ｙ）の対象位置後テーブル（Ｚ）が存在し、更に挿入位置後テーブル（Ｂ）と処理対象テーブル（Ｙ）が隣接している場合の第６ケースとして、
挿入位置後テーブル（Ｂ）の前ポインタを処理対象テーブル（Ｙ）に変更すると共に後ポインタを対象位置後テーブル（Ｚ）に変更し、
処理対象テーブル（Ｙ）の前ポインタをリンク先端（ＮＵＬＬ）に変更すると共に後ポインタを挿入位置後テーブル（Ｂ）に変更し、更に
対象位置後テーブル（Ｚ）の前ポインタを挿入位置後テーブル（Ｂ）に変更する。
【００３０】
（第７ケース）
第２ソート処理部は、３条件として、挿入位置前テーブル（Ａ）が存在せず、処理対象テーブル（Ｙ）の対象位置後テーブル（Ｚ）が存在せず、更に挿入位置後テーブル（Ｂ）と処理対象テーブル（Ｙ）が隣接していない場合の第７ケースとして、
挿入位置後テーブル（Ｂ）の前ポインタを処理対象テーブル（Ｙ）に変更し、
挿入位置前テーブル（Ｘ）の後ポインタをリンク後端（ＮＵＬＬ）に変更し、更に、
処理対象テーブル（Ｙ）の前ポインタをリンク先端（ＮＵＬＬ）に変更すると共に後ポインタを挿入位置後テーブル（Ｂ）に変更する。
【００３１】
（第８ケース）
第２ソート処理部は、３条件として、挿入位置前テーブル（Ａ）が存在せず、処理対象テーブル（Ｙ）の対象位置後テーブル（Ｚ）が存在せず、更に挿入位置後テーブル（Ｂ）と処理対象テーブル（Ｙ）が隣接している場合の第８ケースとして、
挿入位置後テーブル（Ｂ）の前ポインタを処理対象テーブル（Ｙ）に変更すると共に後ポインタをリンク後端（ＮＵＬＬ）に変更し、更に、
処理対象テーブル（Ｙ）の前ポインタをリンク先端（ＮＵＬＬ）に変更すると共に後ポインタを挿入位置後テーブル（Ｂ）に変更する。
【００３２】
本発明の階層ストレージシステムは、電源再投入から入出力処理が開始されるまでの間の初期化処理中に、リストア処理部、第１ソート処理部及び第２ソート処理部の処理を順次実行する。
【００３３】
第２ソート処理部は、入出力処理が開始されるまでにリンクの再構築が終了しなかった場合、入出力処理の開始時にソート処理を中断し、入出力開始後は一定時間ごとにソート処理を再開して一定時間後に中断する処理を繰り返す。
【００３４】
リンク管理部により生成管理するリンクは、
１次ストレージと２次ストレージの両方に存在する同期したデータブロックのブロック情報テーブルをタイムスタンプ順に繋げたヒットリンク、
１次ストレージに存在するが２次ストレージに存在しないか又は存在するが同期していないデータブロックのブロック情報テーブルをタイムスタンプ順に繋げたダーティリンク、又は、
１次ストレージに存在する全てのデータブロックのブロック情報テーブルをタイムスタンプ順に繋げたＬＲＵリンクである。
【００３５】
本発明の別の形態にあってはリンクソート装置を提供する。本発明のリンクソート装置は、
メモリ上にランダムに記憶されたタイムスタンプを有する複数の情報テーブルを、複数の時間帯に分けたグループ別リンクに分類した後に各グループ別リンクをタイムスタンプ順に繋げてグループ分類リンクを構成する第１ソート処理部と
グループ分類リンクの情報テーブルを最古のタイムスタンプ側から順番に取り出してタイムスタンプの昇順に並ぶ位置に挿入してリンクを構築する第２ソート処理部と、
を備えたことを特徴とする。
【００３６】
ここでリンクソート装置の第１ソート処理部は、
リストアした前記情報テーブルから検索した最古のタイムスタンプから最新のタイムスタンプまでの時間を所定数の時間帯に分割して複数のグループ別リンクを生成し、
情報テーブルをアドレス順に取出してタイムスタンプの属する時間帯のグループ別リンクに挿入してアドレス順に繋ぎ、
グループ分け終了後に、各グループ別リンクを時間順に繋げてグループ分類リンクを構成する。
【００３７】
（方法）
本発明は階層ストレージの制御方法を提供する。本発明が対象とする階層ストレージ装置は、
高速小容量の記憶装置を用いた１次ストレージと、低速大容量の記憶装置を用いた２次ストレージで構成され、１次ストレージを２次ストレージのキャッシュ装置として使用する階層記憶部と、
１次ストレージにデータブロックを書き込んだ際に、タイムスタンプを格納したブロック情報テーブルを揮発メモリ上に生成して管理すると共に揮発メモリ上のブロック情報テーブル群を所定タイミング毎に１次ストレージに書き込んで保存するブロック情報テーブル管理部と、
ブロック情報テーブルを生成した際に、タイムスタンプ順となる位置にブロック情報テーブルを挿入してポインタにより繋げたリンクを揮発メモリ上に生成すると共に、ポインタを格納したリンクテーブルを生成して揮発メモリ上で管理するリンク管理部と、
上位装置からデータブロックの入出力要求を受けた際に、マッピングチェックに基づいて階層記憶部の入出力処理を実行する入出力処理部と、
を備える。
【００３８】
このような階層ストレージシステムの制御方法として本発明は、
電源再投入時に、１次ストレージから揮発メモリにブロック情報テーブルをリストアするリストア処理ステップと、
リストアしたブロック情報テーブルを、複数の時間帯に分けたグループ別リンクに分類した後に各グループ別リンクを時間順に繋げてグループ分類リンクを構成する第１ソート処理ステップと、
グループ分類リンクのブロック情報テーブルを最古のタイムスタンプ側から順番に取り出してタイムスタンプの昇順に並ぶ位置に挿入してリンクを再構築する第２ソート処理ステップと、
を備えたことを特徴とする。
【００３９】
本発明の別の形態にあっては、リンクソート方法を提供する。本発明のリンクソート方法は、
メモリ上にランダムに記憶されたタイムスタンプを有する複数の情報テーブルを、複数の時間帯に分けたグループ別リンクに分類した後に各グループ別リンクをタイムスタンプ順に繋げてグループ分類リンクを構成する第１ソート処理ステップと、
グループ分類リンクの情報テーブルを最古のタイムスタンプ側から順番に取り出してタイムスタンプの昇順に並ぶ位置に挿入してリンクを構築する第２ソート処理ステップと、
を備えたことを特徴とする。
【００４０】
（プログラム）
本発明は、階層ストレージシステムのコンピュータにより実行される制御プログラムを提供する。
本発明のプログラムを実行するコンピュータを備えた階層ストレージシステムは、
高速小容量の記憶装置を用いた１次ストレージと、低速大容量の記憶装置を用いた２次ストレージで構成され、１次ストレージを２次ストレージのキャッシュ装置として使用する階層記憶部と、
１次ストレージにデータブロックを書き込んだ際に、タイムスタンプを格納したブロック情報テーブルを揮発メモリ上に生成して管理すると共に揮発メモリ上のブロック情報テーブル群を所定タイミング毎に１次ストレージに書き込んで保存するブロック情報テーブル管理部と、
ブロック情報テーブルを生成した際に、タイムスタンプ順となる位置にブロック情報テーブルを挿入してポインタにより繋げたリンクを揮発メモリ上に生成すると共に、ポインタを格納したリンクテーブルを生成して揮発メモリ上で管理するリンク管理部と、
上位装置からデータブロックの入出力要求を受けた際に、マッピングチェックに基づいて階層記憶部の入出力処理を実行する入出力処理部と、
を備える。
【００４１】
本発明の制御プログラムは、このような階層ストレージシステムのコンピュータに、
電源再投入時に、１次ストレージから前記揮発メモリにブロック情報テーブルをリストアするリストア処理ステップと、
リストアしたブロック情報テーブルを複数の時間帯に分けたグループ毎に分類した後に各グループをタイムスタンプ順に繋げてグループ分類リンクを構成する第１ソート処理ステップと
グループ分類リンクのブロック情報テーブルを最古のタイムスタンプ側から順番に取り出してタイムスタンプの昇順に並ぶ位置に挿入してリンクを再構築する第２ソート処理ステップと、
を実行させることを特徴とする。
【００４２】
本発明の別の形態にあっては、リンクソートプログラムを提供する。本発明のリンクソートプログラムは、コンピュータに、
メモリ上にランダムに記憶されたタイムスタンプを有する複数の情報テーブルを、複数の時間帯に分けたグループ別リンクに分類した後に各グループ別リンクをタイムスタンプ順に繋げてグループ分類リンクを構成する第１ソート処理ステップと
グループ分類リンクの情報テーブルを最古のタイムスタンプ側から順番に取り出してタイムスタンプの昇順に並ぶ位置に挿入してリンクを構築する第２ソート処理ステップと、
を実行させることを特徴とする。
【００４３】
なお、本発明による方法及びプログラムの詳細は、本発明によるシステム及び装置の場合と基本的に同じである。
【発明の効果】
【００４４】
本発明によれば、電源再投入時に、１次ストレージからメモリ上にリストアしたバックアップ保存しているデータブロック分のブロック情報テーブルを対象に、グループ分類リンクを生成する第１ソート処理と、クループ分類リンクについてタイムスタンプ順に整列する第２ソート処理との２段階のソート処理を行うことで、リンクに配置するブロック情報テーブルの数が例えば十数万というように多くとも、電源再投入から入出力処理が開始されるまでの数分程度といった短い時間しかない初期化処理中に、タイムスタンプ順に整列されたリンクをメモリ上に再構築することができる。
【００４５】
即ち、第１段階となる第１ソート処理では、メモリにリストしたブロック情報テーブルを対象に、最古（ＬＲＵ）と最新（ＭＲＵ）のタイムスタンプで決まる時間を複数分割した時間範囲のグループ別リンクを形成し、各グループの時間範囲に属するブロック情報テーブルをグループ別リンクに挿入してアドレス順に繋げるているため、タイムスタンプ順に整列させる第２段階目の挿入ソートでは、グループ別リンクの範囲内で挿入ソート処理を実行すれば良く、挿入ソートの際にタイムスタンプの大小関係を比較判別する整列済リンクの検索範囲が最大でもグループ別リンク長に抑えられ、整列済リンクの検索に要する時間が短縮されることで、リンク再構築の処理時間を初期化処理中に完了できる実用的な時間に短縮できる。
【００４６】
このためシステム電源遮断で揮発メモリ上で生成していたリンクが失われても、電源再投入時に、バックアップ保存していたブロック情報テーブルをリストアしてタイムスタンプ順に整列された正しいリンクを再構築することができ、再構築したリンクを用いた入出力処理により、電源遮断前と同等な入出力性能を電源再投入直後から発揮することができる。
【００４７】
またグループ分類リンクを対象とした第２段階目の第２ソート処理として、ポインタの繋ぎ替えが異なるリンク状態として３条件を特定して８ケースの挿入ソート処理のアルゴリズムを予め設定しておくことで、処理対象とその挿入位置が特定されると、３条件が確定してケースが決まることで挿入ソートが実行され、これによって挿入ソート処理の実行効率を大幅に高め、リンク再構築に要する処理時間を短縮できる。
【発明を実施するための最良の形態】
【００４８】
図２は本発明が適用されるペタバイト階層ストレージシステムの説明図である。図２において、ペタバイト階層ストレージシステム１０は、１次ストレージと２次ストレージのデータ階層構造により、ペタバイト（＝１０３テラバイト）クラスの容量を持つストレージシステムを構築している。
【００４９】
ペタバイト階層ストレージシステム１０に対しては、ホスト側の上位装置としてファイバーチャネルスイッチ１４−１，１４−２を介して、この例では実験データ管理サーバ１２−１、文書データ管理サーバ１２−２及び画像データ管理サーバ１２−３が設けられており、各サーバの入出力処理を実行することになる。
【００５０】
ペタバイト階層ストレージシステム１０には１次ストレージとしてディスクアレイ装置１６が設けられ、また２次ストレージとしてテープライブラリ１８−１，１８−２と光ディスクライブラリ２０−１，２０−２が設けられている。１次ストレージとしてのディスクアレイ装置１６の記憶容量は例えば２テラバイトであり、残りの容量が２次ストレージとしてのテープライブラリ１８−１，１８−２と光ディスクライブラリ２０−１，２０−２で構築されている。
【００５１】
１次ストレージとしてのディスクアレイ装置１６と２次ストレージとしてのテープライブラリ１８−１，１８−２及び光ディスクライブラリ２０−１，２０−２の間には階層間のデータ転送を行う階層制御サーバ２４−１，２４−２が配置されており、ディスクアレイ装置１６に対してはファイバーチャネルスイッチ２２−１，２２−２を介して接続され、テープライブラリ１８−１，１８−２及び光ディスクライブラリ２０−１，２０−２に対してはファイバーチャネルスイッチ２５−１，２５−２を介して接続されている。更に、ペタバイト階層ストレージシステム１０のメンテナンス処理のため、保守端末２６がＬＡＮにより接続される。
【００５２】
図３は図２の１次ストレージとして配置したディスクアレイ装置１６のハードウェア構成のブロック図である。図３において、ディスクアレイ装置１６には、２系統に分けてチャネルアダプタ２８−１１，２８−１２とチャネルアダプタ２８−２１，２８−２２が設けられており、ここに図２に示したように各種サーバを接続している。
【００５３】
またディスクアレイ装置１６には二重化された制御モジュール３０−１，３０−２が設けられている。制御モジュール３０−１，３０−２に対してはディスクエンクロージャ３２−１，３２−２が設けられ、それぞれ磁気ディスク装置を用いた１５台のディスク装置を設けている。ただし、図３ではその内の５台の磁気ディスク装置３４−１１〜３４−１５及び磁気ディスク装置３４−２１〜３４−２５を示している。
【００５４】
ディスクエンクロージャ３２−１，３２−２の５台の磁気ディスク装置３４−１１〜３４−１５，磁気ディスク装置３４−２１〜３４−２５は、所定のＲＡＩＤレベル例えばＲＡＩＤ１あるいはＲＡＩＤ５といったＲＡＩＤ構成によるディスクアレイを構成している。
【００５５】
制御モジュール３０−１，３０−２には、ＣＰＵ３６−１，３６−２、ＤＭＡコントローラ３５−１，３５−２、メモリ３８−１，３８−２、デバイスインタフェース４０−１１，４０−１２，４０−２１，４０−２２が設けられている。
【００５６】
図４は図２のペタバイト階層ストレージシステム１０におけるソフトウェア構成の説明図である。図４において、ホスト１２には、アプリケーション４２、ファイルシステム４４及びディスクドライバ４６が設けられ、所定のＯＳ上で動作している。
【００５７】
ペタバイト階層ストレージシステム１０のディスクアレイ装置１６には仮想ディスク処理部４８と構成管理部５０が設けられ、仮想ディスク処理部４８はチャネルアダプタ２８を介してホスト１２に接続され、またデバイスアダプタ４０を介して磁気ディスク処理部５２を備えたディスクアレイ３２に接続されている。
【００５８】
ディスクアレイ装置１６の仮想ディスク処理部４８及び構成管理部５０は、図３に示したディスクアレイ装置１６に設けているマスタ側の例えば制御モジュール３０−１のＣＰＵ３６−１によるプログラムの実行により実現される機能である。
【００５９】
また、ペタバイト階層ストレージシステム１０に設けられた階層間制御サーバ２４には、階層間データ転送制御部５４と磁気テープ処理部５６が設けられている。磁気テープ処理部５６に対してはライブラリ機構部５８が設けられ、ライブラリ機構部５８にはロボット６０、テープドライブ６２及びカートリッジテープ６４が設けられている。
【００６０】
ロボット６０は階層間データ転送制御部５４からのムーブコマンドを受けて動作し、カートリッジテープ６４を収納庫からテープドライブ６２に搬送して投入し、また処理の済んだカートリッジテープをテープドライブ６２から取り出して収納棚に戻すテープ搬送処理を行っている。
【００６１】
ディスクアレイ装置１６の仮想ディスク処理部４８は、階層間制御サーバ２４の階層間データ転送制御部５４を介して磁気テープ制御部５６に接続されており、階層間データ転送制御部５４が、１次ストレージとしてのディスクアレイ装置１６と２次ストレージとしてのテープライブラリ５８との間のホスト１２からの入出力処理に伴うデータ転送を行っている。また、保守端末２６はＬＡＮを介してペタバイト階層ストレージシステム１０に接続されている。
【００６２】
図５は本発明が適用される階層ストレージシステムにおけるデータ階層構造の説明図である。図５において、本発明により構築しているデータ階層構造は最上位にホスト１２が位置し、ホスト１２には例えばファイルシステム４４がＯＳとして配置されている。このホスト１２の下側に１次ストレージ６８と２次ストレージ７０を備えた階層ストレージ１５が配置される。
【００６３】
階層ストレージ１５は、ホスト１２がアクセスするデータの頻度には高いものと低いものがあるという特性に基づき、アクセス頻度の高いデータをホスト１２に近い高価格で高性能の例えば磁気ディスク装置などを用いた１次ストレージ６８に配置し、アクセス頻度の低いデータについてはホスト１２から遠い低価格で低性能な例えば磁気テープ装置などを用いた２次ストレージ７０に配置する構造である。
【００６４】
本発明の階層ストレージシステムにあっては、ユーザデータを１次ストレージ６８と２次ストレージ７０に階層的に配置し、構成管理部５０によるデータ階層管理機構及び仮想ディスク機構により、ホスト１２における通常のディスクアクセス用インタフェースによって、２次ストレージ７０の容量と同等のディスク空間を提供している。
【００６５】
また、このような階層ストレージシステムはホスト１２から見ると、１次ストレージ６８は２次ストレージ７０のキャッシュ装置として機能している。したがって１次ストレージ６８へのマッピングテーブルを生成して管理することで、ホスト１２からの入出力要求に対するヒット判定を行い、その結果に応じた入出力処理を実行する。
【００６６】
この入出力処理はライト処理とリード処理に分けることができる。ライト処理にあっては、ホスト１２からのアクセスに対するヒットがあれば１次ストレージ６８に対するデータの書込みを行う。ミスヒットの場合には、１次ストレージ６８に書き込んだ後、必要に応じて２次ストレージ７０との同期をとることになる。
【００６７】
一方、リード処理については、ヒットした場合には１次ストレージ６８からデータを読み出して応答し、ミスヒットの場合には２次ストレージ７０からデータを１次ストレージ６８にステージングした後にヒット状態としてリード応答することになる。
【００６８】
ここで１次ストレージ６８と２次ストレージ７０の間のデータのやり取りについては、２次ストレージ７０から１次ストレージ６８にデータをステージングしてヒット状態とすることをリコールという。また１次ストレージ６８上で更新されたデータを２次ストレージ７０に書き込み、１次ストレージ６８と２次ストレージ７０のデータの内容を同期化することをシンク（Ｓｙｎｃ）といい、通常のキャッシュ装置におけるライトバックに相当する。また、１次ストレージ６８と、２次ストレージ７０のデータの内容を同期化するシンク（Ｓｙｎｃ）後、更に１次ストレージ６８上にあるデータの内容を削除することをマイグレーションという。
【００６９】
また本発明の階層ストレージシステムにおける仮想ディスク機構は、２次ストレージ７０の持つ大容量の記憶領域を仮想的にディスク空間としてホスト１２に見せることで、１次ストレージ６８の持つ物理ディスク容量以上のディスク空間をホスト１２に提供している。この場合、ホストが２次ストレージ７０に直接、接続されることはない。このような仮想ディスク構造により、ホスト１２に見せる論理ディスク（論理ボリューム）をＶＬＵ（バーチャルロジカルユニット）と呼ぶ。この階層ストレージシステムで定義できる論理ディスクの総容量は、１次ストレージ６８の物理容量を超えて定義することはできるが、２次ストレージ７０の容量を超えて定義することはできない。
【００７０】
図６は本発明の階層ストレージシステムにおけるデータ転送の説明図である。図６において、１次ストレージ６８と２次ストレージ７０の間で行われるリコールまたはシンク／マイグレーションのデータ転送は、予め定めたデータブロック単位で行う。このため、１次ストレージ６８の仮想論理ユニット７２即ち論理ボリュームは、１または複数のデータブロックで構成されている。２次ストレージ７０については、１つのカートリッジテープの中が複数のデータブロックに分割されていることになる。
【００７１】
ホスト１２からのリード要求に対し、１次ストレージ６８でミスヒットであった場合には、２次ストレージ７０から対応するデータブロックを仮想論理ユニット７２にステージングしてヒット状態とした後に、リード応答をホスト１２に対し行う。
【００７２】
ホスト１２からのライトコマンドについては、１次ストレージ６８の仮想論理ユニット７２でヒットすると、１次ストレージ６８上でデータブロックの新規書込みもしくは更新を行い、その後、所望のタイミングで２次ストレージ７０に転送して同期化するシンクもしくはマイグレーションを行うことになる。
【００７３】
図７は本発明による階層ストレージシステムの機能構成の説明図である。図７において、データ階層構造に対する仮想ディスク装置の制御機能は、ディスクアレイ装置１６の仮想ディスク処理部４８及び構成管理部５０で実現されている。
【００７４】
仮想ディスク処理部４８に対しては、データ階層構造によりユーザボリューム７６として、実ボリュームで構成される１次ストレージ６８と、仮想ボリュームで構成される２次ストレージ７０が配置されている。また仮想ディスク処理部４８に対してはシステムボリューム７４が、仮想ディスク制御に必要な各種の制御情報を格納するために設けられている。
【００７５】
仮想ディスク処理部４８には入出力処理部８２が設けられ、入出力処理部８２にはコマンドキュー８４、ライト処理部８５及びリード処理部８６が設けられている。また構成管理部５０には、情報テーブル管理部８８、リンク管理部９０が設けられる。これに加えて本発明にあっては、システムの電源を遮断して再投入した際に、テーブルリンクを再構築するために使用するリストア部９２、第１ソート処理部９４及び第２ソート処理部９６を設けている。
【００７６】
揮発性のメモリ３８には、仮想ディスク処理部４８の入出力処理に対応して、ブロック情報テーブル領域９８、リンクテーブル領域１００、ＬＲＵリンク領域１０２、ダーティリンク領域１０４及びヒットリンク領域１０６が設けられている。
【００７７】
構成管理部５０に設けた情報テーブル管理部８８は、データブロック毎にブロック情報テーブルとリンクテーブルを生成してメモリ３８上で管理する。ブロック情報テーブルはデータブロックのステータス、対応するＶＬＵ（仮想論理ユニット）情報、ディスクの位置情報、タイムスタンプ情報などを保持する。リンクテーブルは、各種リンク情報とホスト入出力制御のための情報を保持する。
【００７８】
情報テーブル管理部８８は、１次ストレージ６８にライト処理部８５の処理によりデータブロックを書き込んだ際に、その書込時刻に対応した値を持つタイムスタンプを格納したブロック情報テーブルを作成して、メモリ３８のブロック情報テーブル領域９８に格納する。このような情報テーブル管理部８８によるブロック情報テーブルの作成保存により、メモリ３８のブロック情報テーブル領域９８には、１次ストレージ６８に配置しているユーザデータのデータブロック数分のブロック情報テーブルが格納されることになる。
【００７９】
メモリ３８は揮発性のメモリであり、電源を遮断すると記憶内容が消えてしまう。そこで本発明にあっては、メモリ３８のブロック情報テーブル領域９８については、システムボリューム７４のブロック情報テーブル格納領域７５に所定のタイミングで定期的に格納するバックアップ処理を行っている。このブロック情報テーブル領域９８のバックアップタイミングは、例えば
（１）新規マッピング時
（２）データブロック状態の変更時
（３）アンマップ時
に行われることになる。
【００８０】
構成管理部５０に設けたリンク管理部９０は、メモリ３８のブロック情報テーブル領域９８にブロック情報テーブルを生成した際に、そのステータスに対応したリンクのタイムスタンプ順となる位置にブロック情報テーブルを挿入してポインタにより繋げたリンクをメモリ３８上に生成し、同時にリンクにテーブルを繋げるためのポインタを格納したリンクテーブルを生成してリンクテーブル領域１００に格納している。
【００８１】
この実施形態で仮想ディスク処理部４８が使用するリンクとしては
（１）ＬＲＵリンク
（２）ダーティリンク
（３）ヒットリンク
の３つであり、それぞれに対応してメモリ３８には、ＬＲＵリンク領域１０２、ダーティリンク領域１０４及びヒットリンク領域１０６が設けられている。
【００８２】
ここでヒットリンクは、１次ストレージ６８と２次ストレージ７０の両方に存在する同期したデータブロックのブロック情報テーブルをタイムスタンプ順に繋げたリンクである。またダーティリンクは、１次ストレージ６８に存在するが、２次ストレージ７０に存在しないかまたは存在するが同期していないブロックのブロック情報テーブルをタイムスタンプ順に繋げたリンクである。更にＬＲＵリンクは、１次ストレージ７０に存在する全てのデータブロックのブロック情報テーブルをタイムスタンプ順に繋げたリンクである。
【００８３】
一次ストレージ６８と二次ストレージ７０間で、データのアクセス頻度や必要性に応じて自律型データ再配置運用を可能にするために、ヒットリンク、ダーティリンク、ＬＲＵリンクはそれぞれ利用される。
【００８４】
ヒットリンクは、１次ストレージ６８におけるデータブロックのフリー領域の確保に利用される。フリー領域が残り少なくなってきた場合およびフリー領域がない状態で新規マッピングが発生した場合に、ヒットリンクのタイムスタンプの古い側、即ちＬＲＵ側から、必要なテーブルを取り出し、これに対応するデータブロックを１次ストレージ６８から削除することでフリー領域の確保を行なう。
【００８５】
削除されたデータブロックのブロック情報テーブルのステータスはミス状態（マッピングされていない状態）となり、したがって、その情報テーブルをヒットリンクから外す処理を行なう。
【００８６】
一方、ダーティリンクは、１次ストレージ６８におけるデータブロックのダーティ率、即ち２次ストレージ７０との同期化が済んでいない割合が多くなった場合に、ダーティ率を下げてヒット割合を高める同期化のための処理、即ちシンク（Ｓｙｎｃ）に利用される。
【００８７】
具体的には、１次ストレージ（実ボリューム）６８におけるダーティ率を監視し、ダーティ率が所定値を超えた場合に、ダーティリンクのタイムスタンプの古い側、即ちＬＲＵ側から、予め定めた数のテーブルを取り出し、これに対応するデータブロックを１次ストレージ６８から２次ストレージ７０にデータ転送して書き込むことで同期化を行う。
【００８８】
同期化の済んだデータブロックのブロック情報テーブルのステータスはヒット状態となり、したがって、その情報テーブルをダーティリンクから外してヒットリンクに繋ぎ直す処理を行う。
【００８９】
ＬＲＵリンクについては、例えばオペレータなどによる設定で、例えば１次ストレージで６８から２次ストレージ７０に移す時間的な設定、例えば「３年前のデータは全て移す」といった設定を行うと、これに対応するタイムスタンプを持つブロック情報テーブルのデータブロックが１次ストレージで６８から２次ストレージ７０に移され、１次ストレージ６８におけるデータブロック、ブロック情報テーブル及びリンクテーブルは消去することになる。
【００９０】
本発明の階層ストレージシステムの運用状態において、メモリ３８に配置されているＬＲＵリンク、ダーティリンク及びヒットリンクのそれぞれは、全てＬＲＵ側を最も古い位置とし、ＭＲＵ側を最新の位置として、タイムスタンプ順にブロック情報テーブルをリンクテーブルのポインタにより繋げたリンク配置をとっている。
【００９１】
構成管理部５０に設けているリストア部９２、第１ソート処理部９４及び第２ソート処理部９６は、本発明の階層ストレージシステムの電源を遮断して再投入し、システムの入出力処理が開始される初期化処理中に、電源遮断でメモリ３８から消えたＬＲＵリンク、ダーティリンク及びヒットリンクのそれぞれを、システムボリューム７４のブロック情報テーブル格納領域７５に、バックアップ処理により保存しているブロック情報テーブルをメモリ３８にリストアして再構築する処理を実行する。
【００９２】
リストア部９２は、システムの電源再投入時に、システムボリューム７４のブロック情報テーブル格納領域７５にバックアップ保存している電源遮断前のブロック情報テーブルを、メモリ３８のブロック情報テーブル領域９８にリストアする。
【００９３】
第１ソート処理部９４は、メモリ３８にリストアしたブロック情報テーブルから検索した最古（ＬＲＵ）のタイムスタンプから最新（ＭＲＵ）のタイムスタンプまでの時間を例えば１６で割った時間帯に分割した１６個のグループ別リンクを生成し、メモリ３８にリストアしているブロック情報テーブルをアドレス順に取り出して、そのタイムスタンプの属する時間帯のグループ別リンクに挿入してアドレス順に繋ぎ、このグループ分け終了後に各グループ別リンクを時間順に繋げてグループ分類リンクを構成する。
【００９４】
第２ソート処理部９６は、第１ソート処理部９４で生成したグループ分類リンクにおけるブロック情報テーブルをＬＲＵ側から順番に取り出して、タイムスタンプの昇順に並ぶ位置に挿入して、リンクを再構築する。
【００９５】
このリストア部９２、第１ソート処理部９４及び第２ソート処理部９６によるＬＲＵリンク、ダーティリンク及びヒットリンクの再構築は、システムの電源再投入から入出力処理部８２による処理が開始される初期化処理中に終了することを前提としているが、終了しなかった場合には、第２ソート処理部９６の処理として入出力処理が開始された段階でソート処理を中断し、入出力処理が行われている運用中に一定の時間間隔でタイマ割込みを行って、タイマ割込みによる一定時間の間、第２ソート処理部９６の処理を繰り返し、システムが運用に入った初期の段階でリンクの再構築処理を完了するようにしている。
【００９６】
図８は本発明におけるＬＲＵリンクの説明図である。図８において、ＬＲＵリンク１０８は、ＬＲＵリンクターミナル１１０に対しＬＲＵ側（最古側）からＭＲＵ側（最新側）の間に、複数のブロック情報テーブル１１２−１〜１１２−（ｍ＋ｎ）を、タイムスタンプＴ１，Ｔ２，Ｔ３，・・・Ｔｍ＋ｎのように、タイムスタンプ順に並べている。ＬＲＵリンク１０８を構成しているブロック情報テーブル１１２−１〜１１２−（ｍ＋ｎ）は、リンクを構成するためのポインタとして、ＬＲＵ側となる前方に矢印で示す前ポインタを設定し、ＭＲＵ側となる後方に後ポインタを設定し、それぞれ両側に位置するブロック情報テーブルのアドレスを指定している。
【００９７】
更に、ＬＲＵリンク１０８を構成するブロック情報テーブル１１２−１〜１１２−（ｍ＋ｎ）をタイムスタンプ順に繋げているポインタ、即ち前ポインタと後ポインタの値は、ブロック情報テーブル１１２−１〜１１２−（ｍ＋ｎ）に対応して生成されたリンクテーブル１１４−１〜１１４−（ｍ＋ｎ）に格納されている。
【００９８】
図９は本発明におけるダーティリンク１１６の説明図である。図９においてダーティリンク１１６は、ダーティリンクターミナル１１８と、そのＬＲＵ側とＭＲＵ側との間にタイムスタンプ順に並べられたブロック情報テーブル１１２−１〜１１２−ｎで構成されている。ブロック情報テーブル１１２−１〜１１２−ｎのそれぞれは、リンクを構成する矢印で示す前ポインタと後ポインタで繋げられており、これらのポインタは図８に示したリンクテーブル１１４−１〜１１４−ｎに格納されている。
【００９９】
図１０は本発明におけるヒットリンク１２０の説明図であり、ヒットリンク１２０は、ヒットリンクターミナル１１２とそのＬＲＵとＭＲＵの間にタイムスタンプ順に配置されたブロック情報テーブル１１２−（ｍ＋１）〜１１２−（ｍ＋ｎ）で構成されている。このヒットリンク１１２におけるリンクを構成する前ポインタ、後ポインタについても、図８に示したリンクテーブル１１４−（ｍ＋１）〜１１４−（ｍ＋ｎ）に格納されている。
【０１００】
図１１は本発明におけるブロック情報テーブルの説明図である。図１１において、ブロック情報テーブル１１２は例えば６４バイトサイズのテーブルであり、次の（１）〜（１５）に示す情報が格納されている。
【０１０１】
（１）ブロック情報テーブルのインデックス番号である。
（２）有効／無効フラグであり、有効は０ｘ０１、０ｘ００である。
（３）ボリュームテーブルコンテンツ（ＶＴＯＣ）情報フラグであり、ＶＴＯＣがブロック情報テーブルであるかそうでないかを示している。
（４）データブロックのステータスを指定する。
０ｘ００はディスク上にマッピングされていない状態、
０ｘ０１はマッピングはされているがデータがステージングされていない状態、
０ｘ０２は１次ストレージと２次ストレージのデータ内容が等しいヒット状態、
０ｘ０４は１次ストレージと２次ストレージのデータ内容が異なるダーティ状態
０ｘ１０はＬＲＵリンク閉鎖時に除去したデータ情報ブロックがダーティ状態
０ｘ２０は同期処理に失敗した場合
（５）バインド状態を保持するフラグであり、バインド状態の有効または無効を示す。
（６）データブロックの単位サイズを示す。
（７）実ディスク上のデータブロック割当先頭アドレスを示す。
（８）実ディスク番号を示す。
（９）仮想論理ユニット番号を示す。
（１０）仮想論理ユニット上のデータブロック番号を示す。
（１１）割当制御モジュール番号を示す。
（１２）担当制御モジュール番号を示す。
（１３）タイムスタンプ情報を示す。
（１４）同期制御フラグを示す。
（１５）リザーブである。
【０１０２】
このようなブロック情報テーブル１１２のうち、本発明の電源再投入時のリンクの再構成に必要な情報は、前記（４）のデータブロックステータス１２４と前記（１３）のタイムスタンプ情報１２６が主なものである。
【０１０３】
図１２は本発明におけるリンクテーブルの説明図である。図１２において、リンクテーブル１１４は例えば９６バイトのテーブルサイズを持っている。リンクテーブル１１４の内容は次の（１）〜（２３）の内容となる。
【０１０４】
（１）リンクテーブルのインデックス番号を示す。
（２）上位管理テーブルのポインタを示す。
（３）ブロック情報テーブルへのポインタを示す。
（４）実ディスク管理バッファへのポインタを示す。
（５）ヒットリンク／ダーティリンクの先行／後続情報（前ポインタ／後ポインタ）を示す。
（６）ＬＲＵリンクの先行／後続情報（前ポインタ／後ポインタ）を示す。
（７）仮想論理ユニットリンクの先行／後続情報を示す。
（８）実論理ユニットリンクの先行／後続情報（前ポインタ／後ポインタ）を示す。
（９）入出力待ちキューへのヘッダ／テール情報を示す。
（１０）フリーリンクの先行／後続情報を示す。
（１１）ブロック排他フラグを示す。
（１２）タイムスタンプ情報同期フラグであり、制御モジュール間でのテーブル同期の必要性の有無をセットしている。
（１３）削除予約フラグを示す。
（１４）イベントフラグを示す。
（１５）リザーブである。
（１６）未使用である。
（１７）実行中のライトコマンド数を示す。
（１８）実行中のリードコマンド数を示す。
（１９）待ち合わせ中のライトコマンド数を示す。
（２０）待ち合わせ中のリードコマンド数を示す。
（２１）デバック情報を示す。
（２２）デバック情報を示す。
（２３）リザーブである。
【０１０５】
図１３は本発明における階層ストレージシステムの制御処理のフローチャートであり、図７の機能構成を参照して説明すると次のようになる。
【０１０６】
図１３において、システムの電源を投入するとステップＳ１で初期化処理が行われる。この初期化処理はスレッドの初期化及びオンラインのセット処理を行う。続いてステップＳ２でシステムボリューム７４のブロック情報テーブル格納領域７５からデータ情報ブロックをメモリ３８に対するリストアを行う。続いてステップＳ３でリンク生成処理を行う。
【０１０７】
ここで、システムの運用を最初に開始した際にはシステムボリューム７４にブロック情報テーブルは格納されていないことから、ステップＳ２のデータ情報テーブルのリストア及びステップＳ３の生成処理は行われない。これに対しシステム運用中に電源を遮断して再投入した際にはステップＳ２でリストア部９２によりシステムボリューム７４にバックアップ保存していたブロック情報テーブルのメモリ３８に対するリストアが行われ、ステップＳ３で第１ソート処理部９４及び第２ソート処理部９６によるリストアされたブロック情報テーブルからＬＲＵリンク及びダーティリンク、ヒットリンクを再構築するリンク生成処理が実行される。
【０１０８】
続いてステップＳ４で入出力処理部８２による入出力処理が開始されたか否かチェックしており、開始されるとステップＳ５に進み、ホスト１２からのコマンド受領をチェックする。ホストからコマンドを受領するとステップＳ６でコマンドキュー８４に格納した後、ステップＳ７でキューからコマンドを出力して入出力処理を実行する。この入出力処理はライトコマンドについてはライト処理部８５による処理、リードコマンドについてはリード処理部８６による処理となる。
【０１０９】
続いてステップＳ８でＬＲＵ管理処理を行う。本発明の実施形態にあっては運用状態におけるＬＲＵ管理は特に行っておらず、運用中にオペレータが例えば１次ストレージ６８から排除する年数などの設定をＬＲＵ管理に対して行うと、設定した年数以前のスタンプを持つデータブロックが１次ストレージ６８から２次ストレージ７０に転送され、１次ストレージ６８のデータブロックが破棄され、これに伴いブロック情報テーブル及びリンク情報テーブルも破棄される。
【０１１０】
続いてステップＳ９でダーティリンク管理処理を行う。ダーティリンク管理処理は１次ストレージ６８に存在するデータブロックのステータスからダーティとなっているデータブロックの割合であるダーティ率を算出し、ダーティ率が予め設定した所定値を超えた場合には、ダーティリンクのＬＲＵ側から所定ブロックテーブル分のデータブロックを２次ストレージ７０に転送して同期化し、ヒットステータスとなるデータブロックの数を増やすことでダーティ率を下げる。
【０１１１】
ステータスがこのダーティリンク管理処理でヒットに変更されたブロックについては、ヒットリンクのタイムスタンプ順に従った位置に挿入する処理を行う。
【０１１２】
続いてステップＳ１０でメモリ３８のブロック情報テーブル領域９８に格納しているブロック情報テーブルを予め設定したタイミング、即ちデータブロックの新規マッピング時、データブロック状態の変更時またはアンマッピング時のいずれかであれば、システムボリューム７４に転送してブロック情報テーブル格納領域７５に対し保存するバックアップ処理を行う。このようなステップＳ５〜Ｓ１０の処理をステップＳ１１でシステム停止指示があるまで繰り返している。
【０１１３】
図１４は図１３のステップＳ７の入出力処理に含まれる本発明におけるライト処理のフローチャートである。図１４において、ライト処理はコマンドキュー８４からライトコマンドを取り出すことで実行され、ステップＳ１でマッピングチェック（１次ストレージ６８への割り当てがされているか）を実施し、ステップＳ２でマッピングされているか否かを判定する。
【０１１４】
マッピングされていた、即ち１次ストレージ６８上にデータブロックが存在する場合にはステップＳ３に進み、ブロック情報テーブルのステータスチェックを行なう。ここでブロック情報テーブルのステータスがヒットであった場合は、ステップＳ４で１次ストレージすなわちディスク上に存在するデータブロックに対し書き込みを行う。
【０１１５】
続いてステップＳ５で書き込みを行ったデータブロックに対応するブロック情報テーブルのタイムスタンプを更新する。続いてステップＳ６で１次ストレージ６８上でデータブロックが更新されて２次ストレージ７０のデータブロックと同期しなくなったことから、図１１のブロック情報テーブル１１２に示したようにデータブロックステータス１２４をそれまでのヒットからダーティに変更し、更にダーティに変更されたブロック情報テーブルをヒットリンクから外し、ステップＳ９でダーティリンクＭＲＵ側（最新値）に移動する。
【０１１６】
このヒットリンクからダーティリンクへのブロック情報テーブルの付け替えに伴い、図１２に示したリンクテーブル１１４におけるポインタ情報１２８はそれまでのヒットリンクの先行／後続情報（前ポインタ／後ポインタ）からダーティリンクの先行／後続情報（前ポインタ／後ポインタ）に変更する。
【０１１７】
一方、ステップＳ３でブロック情報テーブルのステータスがダーティであった場合には、ステップＳ７で１次ストレージ６８となる実働値にデータブロックを書き込み、すでに確認されているデータブロックを更新する。
【０１１８】
続いてステップＳ８で確認されて更新されたデータブロックに対応したブロック情報テーブルのタイムスタンプを更新する。続いてステップＳ９でブロック管理テーブルをダーティリンクのＭＲＵ（最新側）に移動してリンクの付け替えを行う。
【０１１９】
更にステップＳ２でブロック情報テーブルがマッピングされていなかった場合には、ステップＳ１０で１次ストレージにフリー領域があるかどうかをチェックする。フリー領域がなかった場合には、ステップＳ１１に進み、ヒットリンクの最もＬＲＵ（最古値）にあるデータブロックを必要な分だけ１次ストレージから削除することで追い出し、フリー領域を確保する。
【０１２０】
フリー領域が確保されると、またはステップＳ１０においてもともとフリー領域が確保されていた場合には、ステップＳ１２で確保されているフリー領域に対して新規マッピング処理を行なう。新規マッピング完了後は、確保されている領域に対しステップＳ１３で１次ストレージ６８にデータブロックを書き込み後、ステップＳ１４でブロック情報テーブルとブロックリンクテーブルを生成し、ステップＳ１５でダーティリンクのＭＲＵに新規のブロック情報テーブルを追加する。
【０１２１】
図１５は本発明におけるリード処理のフローチャートである。リード処理はコマンドキュー８４からリードコマンドをリード処理部８６で取り出すことで実行される。まずステップＳ１でマッピングチェックを実施し、ステップＳ２でマッピングされていた場合にはステップＳ３で１次ストレージから対応するデータブロックを読み出してホスト１２に応答する。
【０１２２】
ステップＳ２でマッピングされていなかった場合にはＳ４で２次ストレージ７０を検索し、ステップＳ５で２次ストレージ７０上にデータブロックがあることが判定されるとステップＳ６で１次ストレージ６８にフリー領域があるかどうかをチェックする。フリー領域がなかった場合には、ステップＳ７に進み、ヒットリンクの最もＬＲＵ（最古値）にあるデータブロックを必要な分だけ１次ストレージから削除することで追い出し、フリー領域を確保する。
【０１２３】
フリー領域が確保されると、またはステップＳ６においてもともとフリー領域が確保されていた場合には、ステップＳ８で確保されているフリー領域に対して新規マッピング処理を行なう。新規マッピング完了後は、確保されている領域に対しステップＳ９で２次ストレージ７０から１次ストレージ６８にデータブロックを転送するステージング（リコール）を行った後、ステップＳ１０でブロック情報テーブルとリンクテーブルを作成し、ブロック情報テーブルをヒットリンクのＭＲＵに追加する。ステップＳ５でステージングの検索によりミスヒットなった場合にはステップＳ１１でエラー応答を行う。
【０１２４】
図１６及び図１７は本発明における電源再投入時にリンクを再構築するための図７の構成管理部５０に設けている第１ソート処理部９４による処理手順の説明図である。
【０１２５】
図１６において、システムの電源が再投入されると、図７のリストア部９２によりシステムボリューム７４のブロック情報テーブル格納領域７５からメモリ３８のブロック情報テーブル領域９８にバックアップ保存していたブロック情報テーブルのリストア処理１３２が行われる。
【０１２６】
このリストア処理１３２によりメモリ３８上にブロック情報テーブル１１２−１〜１１２−１７が展開される。ブロック情報テーブル１１２−１〜１１２−１７の数字はそれぞれが保有しているタイムスタンプの値である。このタイムスタンプはシステム運用中におけるデータブロックの書き込み時に更新されているため、メモリに展開した状態でのアドレスとは無関係にランダムにスタンプが並んでいる。
【０１２７】
続いてリストア処理１３２を行ったメモリに展開されているブロック情報テーブル１１２−１〜１１２−１７の中から最新のタイムスタンプと最古のタイムスタンプを抽出するタイムスタンプ抽出処理を行う。この場合、最新タイムスタンプは「１６１」であり、最古タイムスタンプは「１」となっている。
【０１２８】
続いてグループ間差分算出処理１３６を実行する。グループ間差分算出処理１３６はグループ間差分値ΔＴを予め設定したグループ数である「１６」により最新と最古のタイムスタンプの差分（１６１−１）を割る（１６１−１）／１６を行うことにより算出され、ΔＴ＝１０が求められる。
【０１２９】
続いてグループ範囲算出処理１３８が行われる。グループ範囲算出処理１３８は図示のリストに示す内容が求められる。このリストはグループ番号Ｇ１５〜Ｇ００の１６グループを持ち、各グループごとにグループ基準値とグループ範囲が求められる。
【０１３０】
例えばグループＧ１５を例にとると、グループ基準値は最新のタイムスタンプ「１６１」からグループ間差分値Ｄ＝１０を減算した「１５１」であり、グループ基準値が求まればグループ範囲として「１５１〜１６１」が求まる。以下、グループ番号Ｇ１４〜Ｇ００につき同様にしてグループ基準値を順次計算することでグループ範囲が算出される。
【０１３１】
続いて図１７に進んでグループ別リンク生成処理１４０を実行する。グループ別リンク生成処理１４０は、１６グループに対応したグループターミナル１４０−１〜１４０−１６に対し、それぞれの時間範囲の最古の時間をＬＲＵ、最新の時間をＭＲＵとし、この時間範囲に属するタイムスタンプを持つブロック情報テーブルを抽出して挿入し、アドレス順に配置している。
【０１３２】
例えば図１７のグループ別リンク生成処理にあってはグループ番号Ｇ２〜Ｇ４のグループターミナル１４０−２〜１４０―４の部分を示しており、グループ番号Ｇ２のグループターミナル１４０−２を例にとると、図１６のグループ範囲からＬＲＵ＝２１で、ＭＲＵ＝３０であり、この時間範囲をグループ範囲「２１〜３０」とし、これに属するブロック情報テーブルを図１６のリストア処理１３２でメモリ上に展開されたブロック情報テーブル１１２−１〜１１２−１７の中からアドレス順に抽出する。
【０１３３】
この場合、タイムスタンプ「２２」を持つブロック情報テーブル１１２−１０、タイムスタンプ「２９」を持つブロック情報テーブル１１２−１４及びタイムスタンプ「２７」を持つブロック情報テーブル１１２−１５の３つが抽出され、グループ番号Ｇ２、グループターミナル１４０−２、アドレス順に挿入され、前ポインタ及び後ポインタによりリンクが生成される。
【０１３４】
このようにグループ別リンク生成処理で形成されたグループ別リンクにあっては、グループ間ではタイムスタンプが時間順に並んでいるが、グループ内ではタイムスタンプ順ではなくアドレス順に並んでいることがわかる。
【０１３５】
続いてグループ分類リンク生成処理１４４を実行する。グループ分類リンク生成処理１４４は、グループ別リンク生成処理１４０で生成されたグループ別リンクを時間順に並べてひとつのリンクとしたグループ分類リンク１４８を生成する。
【０１３６】
グループ分類リンク１４８はグループ単位で比較するとタイムスタンプは時間順に並んでいるが、グループ内にあってはタイムスタンプ順ではなくアドレス順に並んでおり、タイムスタンプ順に並んだ本来のリンクではなく中間的なリンクを形成している。
【０１３７】
図１８は図１６及び図１７に示した第１ソート処理に続いて行われる第２ソート処理の説明図である。第２ソート処理は第１ソート処理で生成されたグループ分類リンク１４８につき最古側となるＬＲＵが即ち前方側からブロック情報テーブルをひとつずつ取り出し、前方に位置するブロック情報テーブルのタイムスタンプと自己のタイムスタンプを比較し、タイムスタンプ順となる位置に挿入して並び替える挿入ソート処理を実行する。
【０１３８】
図１８において、整列済リンク１５０に続いて処理対象テーブルＹの挿入ソートを行う場合を例にとると、処理対象テーブルＹのタイムスタンプをその前方に位置する整列済リンク１５０の最後からＬＲＵとなる前方側に順次取り出してタイムスタンプを比較し、例えばテーブルＡとテーブルＢの間を挿入位置として判定する。
【０１３９】
このようにして処理対象テーブルＹの挿入位置が判定されたならば、処理対象テーブルＹを挿入位置となるテーブルＡとテーブルＢの間に入れ替えることになるが、このテーブルの入れ替えは、具体的には各テーブルが持つ矢印で示す前方側を示した前ポインタと後方側を示した後ポインタの付け替えによって実現される。
【０１４０】
ここで挿入ソートの対象となるポインタ付け替えを必要とするテーブルは、処理対象テーブルＹ、挿入位置の前テーブルＡと後テーブルＢ、さらに処理対象位置テーブルＹの前テーブルＸと後テーブルＺの５つとなる。
【０１４１】
このような挿入ソートについて対象となるテーブルＡ，Ｂ，Ｙ，Ｘ，Ｚを次のように
呼ぶこととする。
（１）テーブルＹは処理対象テーブルという
（２）テーブルＸは対象位置前テーブルという。
（３）テーブルＺは対象位置後テーブルという。
（４）テーブルＡは挿入位置前テーブルという。
（５）テーブルＢは挿入位置後テーブルという。
【０１４２】
図１８の場合には、処理対象テーブルＹをテーブルＡ，Ｂの間に挿入することから、挿入位置前テーブルＡについては後ポインタを挿入前の「Ｂ」から「Ｙ」に付け替える必要がある。挿入位置後テーブルＢについては前ポインタを挿入前の「Ａ」から「Ｙ」に付け替える必要がある。処理対象テーブルＹについては前ポインタを挿入前の「Ｘ」から「Ａ」に付け替えると共に、後ポインタを挿入前の「Ｚ」から「Ｂ」に付け替える必要がある。
【０１４３】
また対象位置前テーブルＸについては後ポインタを挿入前の「Ｙ」から「Ｚ」に付け替える必要がある。更に対象位置後テーブルＺについては前ポインタを挿入前の「Ｙ」から「Ｘ」に付け替える必要がある。このようにグループ分類リンク１４８に対しタイムスタンプ上に整列させる挿入ソート処理にあっては、挿入処理によりポインタの付け替え処理を実行するアルゴリズムとして実現される。
【０１４４】
本発明の第２ソート処理にあっては挿入ソート処理におけるアルゴリズムを、処理対象となるリンク状態に応じてケース分けし、処理対象となっているリンク状態から一義的に対応するアルゴリズムケースを選択してポインタ付け替えによるリンク付け替え処理を実行できるようにしている。
【０１４５】
図１９は本発明の第２ソート処理の処理対象としているリンク状態を判別する３条件を判定ビット率ｂ２，ｂ１，ｂ０により示し、これに対応した挿入ソート処理のアルゴリズムをケース１〜ケース８の８ケースに対応させた対応表である。この対応表１５２における判定ビット率ｂ２，ｂ１，ｂ０を与える３条件は次のようになる。
（１）挿入位置前テーブルＡが存在するか否かの第１条件。
（２）処理対象テーブルＹの対象位置後テーブルＺが存在するか否かの第２条件。
（３）挿入位置後テーブルＢと処理対象テーブルＹが隣接しているか否かの第３条件。
【０１４６】
ここで３条件（１）〜（３）につき判定ビットｂ２，ｂ１，ｂ０が割り当てられ、条件が「存在する」であればビット１をセットし、「否」であればビット０をセットする。
【０１４７】
なお、第１条件における「挿入位置前テーブルＡが存在するか否か」は、「挿入位置がＬＲＵ端でないか否か」と同じことである。また第２条件の「処理対象テーブルＹの対象位置後テーブルＺが存在するか否か」は、「処理対象テーブルＹがＭＲＵ端にないか否か」と同じことである。
【０１４８】
図２０〜図２７は図１９における対応表１５２における判定ビット率ｂ２，ｂ１，ｂ０の３条件の組合せによるアルゴリズムケースであるケース１〜ケース８についてそれぞれ挿入前のテーブルのポインタと挿入後のテーブルのポインタ及びリンクにおける挿入とポインタの付け替えとした説明図である。
【０１４９】
図２０は判定ビット率ｂ２，ｂ１，ｂ０＝１１１となるケース１の説明図である。このケース１におけるリンク状態の３条件は
（１）挿入位置前テーブルＡが存在し、
（２）処理対象テーブルＹの対象位置後テーブルＺが存在し、
（３）挿入位置後テーブルＢと処理対象テーブルＹが隣接していない、
場合である。
【０１５０】
この場合には図２０（Ａ）に示すケース１のポインタ付け替えのアルゴリズムが実行される。即ち処理対象テーブルとして挿入位置前テーブルＡ、挿入位置後テーブルＢ、対象位置前テーブルＸ、処理対象テーブルＹ及び対象位置後テーブルＺが検出され、それぞれ変更されるポインタ名が前ポインタか後ポインタか両方かがセットされ、挿入前のポインタが指し示しているテーブル名が挿入後のポインタが指し示しているテーブル名となるようにそれぞれのブロック情報テーブルのポインタ内容を変更するアルゴリズムが実行される。
【０１５１】
図２１は判定ビット率ｂ２，ｂ１，ｂ０＝１１０となるケース２の場合であり、この場合には図２１（Ｂ）に示すように
（１）挿入位置前テーブルＡが存在し、
（２）処理対象テーブルＹの対象位置後テーブルＺが存在し、
（３）挿入位置後テーブルＢと処理対象テーブルＹが隣接している
場合である。この場合には図２１（Ａ）に示すテーブルＡ，Ｂ，Ｙ，Ｚにつき挿入前のポインタが挿入後のポインタに変更される。尚、ケース２にあっては対象位置前テーブルＸは存在していない。
【０１５２】
図２２は判定ビット率ｂ２，ｂ１，ｂ０＝１０１によるケース３の場合である。ケース３の場合には図２２（Ｂ）のように３条件として
（１）挿入位置前テーブルＡが存在し、
（２）処理対象テーブルＹの対象位置後テーブルＺが存在せず、
（３）挿入位置後テーブルＢと処理対象テーブルＹが隣接していない
場合である。
【０１５３】
ここで条件（２）における処理対象テーブルＹの対象位置後テーブルＺが存在しない場合である処理対象テーブルＹがリンクの最新側となるＭＲＵに位置しており、その後ろが空きを示す「ＮＵＬＬ」となっている場合である。
【０１５４】
このケース３にあっては図２２（Ａ）のようにテーブルＡ，Ｂ，Ｘ，Ｙを処理対象として挿入前のポインタの内容が挿入後のポインタに変更されており、処理対象テーブルＹが整列済リンク１５０の中に挿入されたことで対象位置前テーブルＸの後ろポインタがＬＲＵ側を示す「ＮＵＬＬ」に変更されている。
【０１５５】
図２３は判定ビット率ｂ２，ｂ１，ｂ０＝１００となるケース４の場合である。ケース４における３条件は図２３（Ｂ）に示すように
（１）挿入位置前テーブルＡが存在し、
（２）処理対象テーブルＹの対象位置後テーブルＺが存在する
（３）挿入位置後テーブルＢと処理対象テーブルＹが隣接している
場合である。この場合には図２３（Ａ）に示すようにテーブルＡ，Ｂ，Ｙが処理対象となり挿入前のポインタの値が挿入後のポインタの値に変更されている。
【０１５６】
図２４は判定ビット率ｂ２，ｂ１，ｂ０＝０１１となるケース５の場合である。このケース５における３条件は図２４（Ｂ）のように
（１）挿入位置前テーブルＡが存在せず
（２）処理対象テーブルＹの対象位置後テーブルＺが存在し、
（３）挿入位置後テーブルＢと処理対象テーブルＹが隣接していない
場合である。このケース５の場合には図２４（Ｂ）に示すようにテーブルＢ，Ｘ，Ｙ，Ｚが処理対象となり、挿入前のポインタの内容が挿入後のポインタの内容に変更される。
【０１５７】
図２５は判定ビット率ｂ２，ｂ１，ｂ０＝０１０となるケース６の場合である。ケース６においての３条件は図２５（Ｂ）に示すように
（１）挿入位置前テーブルＡが存在せず
（２）処理対象テーブルＹの対象位置後テーブルＺが存在し
（３）挿入位置後テーブルＢと処理対象テーブルＹが隣接している
場合である。このケース６については図２５（Ｂ）のようにテーブルＢ，Ｘ，Ｙ，Ｚが処理対象となり、挿入前のポインタの内容が挿入後のポインタの内容に変更される。
【０１５８】
図２６は判定ビット率ｂ２，ｂ１，ｂ０＝００１となるケース７の場合である。ケース７においての３条件は図２６（Ｂ）に示すように
（１）挿入位置前テーブルＡが存在せず
（２）処理対象テーブルＹの対象位置後テーブルＺが存在せず
（３）挿入位置後テーブルＢと処理対象テーブルＹが隣接していない
場合である。このケース７については図２６（Ａ）のようにテーブルＢ，Ｘ，Ｙが処理対象となり、挿入前のポインタの内容が挿入後のポインタの内容に変更される。
【０１５９】
図２７は判定ビット率ｂ２，ｂ１，ｂ０＝０００となるケース８の場合である。ケース８においての３条件は図２７（Ｂ）に示すように
（１）挿入位置前テーブルＡが存在せず
（２）処理対象テーブルＹの対象位置後テーブルＺが存在せず
（３）挿入位置後テーブルＢと処理対象テーブルＹが隣接している
場合である。このケース８については図２７（Ａ）のようにテーブルＢ，Ｘ，Ｙが処理対象となり、挿入前のポインタの内容が挿入後のポインタの内容に変更される。
【０１６０】
図２８は図１３のステップＳ３における本発明における電源再投入時のリンク生成処理の詳細のフローチャートである。図２８において、図７の機能構成を参照して説明すると次のようになる。
【０１６１】
まずステップＳ１でシステムボリューム７４にバックアップしているブロック情報テーブルをメモリ３８に読み込む。次にステップＳ２でリンクの種別を設定する。例えばリンクの種別はＬＲＵリンク、ダーティリンク、ヒットリンクの順に設定する。続いてステップＳ３でリンクのステータスを持つブロック情報テーブルを抽出する。
【０１６２】
この例では最初にＬＲＵリンクを設定していることから、１次ストレージ６８に存在するデータブロックに対応したリストアした全ブロック情報テーブルを抽出することになる。続いてステップＳ４でブロック情報テーブルに対応したリンクテーブルを生成する。この段階でリンクテーブルのポインタ情報は空きとなっておりリンクは形成されていない。
【０１６３】
次にステップＳ５で図１６及び図１７で示したように、第１ソート処理によりタイムスタンプ順にグループ化したグループ分類リンクを構築する。続いてステップＳ６でリンク種別を全て設定したか否か判定し、未設定であればステップＳ２に戻り、次のダーティリンクを設定して同様の処理を繰り返し、更にヒットリンクを設定して同様の処理を繰り返す。
【０１６４】
ステップＳ６でリンク種別の全ての設定が判別されると、ステップＳ７に進み、図１８〜図２７に示した第２ソート処理部９６によるタイムスタンプ順にリンクを並び替える第２ソート処理を実行する。
【０１６５】
続いてステップＳ８でソート終了の有無をチェックしており、未終了であればステップＳ９で入出力処理開始をチェックしている。入出力処理開始を判別する前にステップＳ８でソート終了が判別されると、一連のリンク生成処理を終了する。この場合のソート終了はシステムの初期化中にソート処理を完了して新たにリンクを再構築できた場合である。
【０１６６】
一方、ソート終了を判別する前にステップＳ９で入出力処理開始が判別されると、ソートを中断しステップＳ１０でタイマー割り込みの有無をチェックする。タイマー割り込みがあるとステップＳ１１で中断した第２ソート処理を所定時間にわたり実行する。
【０１６７】
そしてステップＳ１２でソート終了をチェックしており、ソート終了が判別するまでステップＳ１０，Ｓ１２の処理をタイマー割り込みに伴う挿入ソート処理、すなわち第２ソート処理を繰り返している。ステップＳ１２で入出力処理中におけるソート処理が完了すると一連のリンク生成処理を終了し、この場合にもシステムの電源再投入を行った後の早い段階でタイムスタンプ順に並んだリンクの再構築が完了することになる。
【０１６８】
図２９は図２８のステップＳ５における第１ソート処理のフローチャートである。図２９において、第１ソート処理は、ステップＳ１で図１６のタイムスタンプ抽出処理１３４に示したように、メモリ３８にリストアしたブロック情報テーブルから最古と最新のタイムスタンプを検索し、ステップＳ２で図１６のグループ間差分算出処理１３６に示したように最古と最新のタイムスタンプの差分を算出し、ステップＳ３でグループ間差分値ΔＴ値をグループ数である例えば１６で割って算出する。
【０１６９】
次にステップＳ４で最新のタイムスタンプからグループ間差分値ΔＴを順次差し引いた値から各グループの基準値とグループ範囲を図１６のグループ範囲算出処理１３８のリストに示すように算出する。
【０１７０】
続いてステップＳ５でメモリにリストアしたブロック情報テーブルをアドレス順に取出し、ステップＳ６で上から順にグループ範囲を選択して比較する。この比較結果につきステップＳ７でタイムスタンプがグループ範囲内であればステップＳ８でそのグループにテーブルを挿入する。このステップＳ５〜Ｓ８は図１７のグループ別リンク生成処理１４０の処理内容となる。
【０１７１】
ステップＳ９で全てのブロック情報テーブルの処理が終了すると、ステップＳ１０に進み、図１７のグループ分類リンク生成処理１４４に示したように、全グループのテーブルを時間順に繋げてひとつのリンクなるグループ分類リンク１４８を生成する。
【０１７２】
図３０は図２８のステップＳ７における第２ソート処理のフローチャートである。第２ソート処理は，ステップＳ１で第１ソート処理で生成されたグループ別リンクを対象にＬＲＵ側からブロック情報テーブルを処理対象として順次取り出し、ステップＳ２で整列済のリンクの前方検索によりタイムスタンプの対象資格により挿入位置を判定する。
【０１７３】
続いてステップＳ３で挿入位置の前方と処理対象位置の後方のリンク状態、すなわちリンク状態の３条件に応じて判定ビット率ｂ２，ｂ１，ｂ０で選択されるアルゴリズムケースの内のケース１〜ケース８のいずれかに分類した後に、ステップＳ４で分類したケースに応じたポインタの付け替え処理を実行する。このステップＳ１〜Ｓ４の処理をステップＳ５で全ブロックの情報テーブルの処理がすむまで繰り返す。
【０１７４】
図３１は図３０のステップＳ３におけるケース分類処理のフローチャートである。図３１においてケース分類処理は、ステップＳ１で挿入位置前テーブルＡが存在するか否か判別し、存在すればステップＳ２で判定ビットｂ２＝１にセットし、存在しなければ、即ちＬＲＵ端でＮＵＬＬであれば、ステップＳ３で判定ビットｂ２＝０にセットする。続いてステップＳ４で対象位置後テーブルＺが存在するか否か判別する。存在すればステップＳ５で判定ビットｂ１＝１とし、存在しなければ、即ちＭＲＵ端でＮＵＬＬであれば、ステップＳ６で判定ビットｂ１＝０とする。
【０１７５】
続いてステップＳ７で挿入位置と対象位置のテーブルが隣接していないか否かチェックし、隣接していなければステップＳ８で判定ビットｂ０＝１とし、隣接していればステップＳ９で判定ビットｂ０＝０とする。続いてステップＳ１０で判定ビット率ｂ２，ｂ１，ｂ０によりケース番号を指定し、ステップＳ１１で指定したケース番号の繋がり開始処理を選択して実行する。
【０１７６】
このような処理対象となるリンク状態に応じた３条件の判定結果によりケース１〜ケース８のいずれかのケースを一時的に選択し、予め選択した各ケースごとのリンク挿入ソートに伴うポインタの付け替え処理を実行することで、挿入ソート処理が判定条件による関数コール処理として高速に実行することができ、第１ソート処理におけるグループ分けリンクによる第１段階のソート処理に続く第２ソート処理の高速化に伴い、電源再投入時のリンク再構築の処理時間を初期化処理中に原則的に完了できる短い時間に短縮することができる。
【０１７７】
また本発明は図２のペタバイト階層ストレージシステム１０のコンピュータ、具体的には図３に示したディスクアレイ装置１６におけるマスタ側の専用モジュール３０−１に設けているＣＰＵ３６−１を備えたコンピュータのハードウェア環境で実行されるソート処理プログラムを提供するものであり、このソート処理プログラムの内容は図２８、図２９、図３０に示したフローチャートの内容を持つ。
【０１７８】
また本発明のソートプログラムはＣＤ−ＲＯＭ、フロッピーディスク（Ｒ）、ＤＶＤディスク、光ディスク、ＩＣカードなどの記憶媒体のほか回線を介してプログラムを保持するデータベース、他のコンピュータシステム並びそのデータベースや更には回線上の伝送媒体を含むものである。
【０１７９】
また上記の実施形態は階層ストレージシステムでの電源再投入に伴うリンクの再構築を例にとるものであったが、複数のデータテーブルをポインタ情報により繋げたリンクをメモリ上に展開して使用するシステムまたは装置について、リンクのポインタを格納したリンクテーブルはバックアップせず、データテーブルのみをバックアップ保存し、電源切断に伴いリンクがきれ、電源再投入時にバックアップしているデータテーブルのリストアによりそこからタイムスタンプ順に並んだリンクを再構築するシステムまたは装置であれば、適宜のシステムまたは装置により本発明のリンクソートを適用することができる。
【０１８０】
また本発明はその目的を利点を損なうことのない適宜の変形を含み、さらに上記の実施形態に示した数値による限定は受けない。
【０１８１】
ここで本発明の特徴をまとめて列挙すると次の付記のようになる。
（付記）
（付記１）
高速小容量の記憶装置を用いた１次ストレージと、低速大容量の記憶装置を用いた２次ストレージで構成され、前記１次ストレージを前記２次ストレージのキャッシュ装置として使用する階層記憶部と、
前記１次ストレージにデータブロックを書き込んだ際に、タイムスタンプを格納したブロック情報テーブルを揮発メモリ上に生成して管理すると共に前記揮発メモリ上のブロック情報テーブルを所定タイミング毎に前記１次ストレージに書き込んで保存するブロック情報テーブル管理部と、
前記ブロック情報テーブルを生成した際に、タイムスタンプ順となる位置に前記ブロック情報テーブルを挿入してポインタにより繋げたリンクを前記揮発メモリ上に生成すると共に、前記ポインタを格納したリンクテーブルを生成して前記揮発メモリ上で管理するリンク管理部と、
上位装置からデータブロックの入出力要求を受けた際に、マッピングチェックに基づいて前記階層記憶部の入出力処理を実行する入出力処理部と、
を備えた階層ストレージシステムに於いて、
電源再投入時に、前記１次ストレージから前記揮発メモリに前記ブロック情報テーブルをリストアするリストア処理部と、
リストアした前記ブロック情報テーブルを、複数の時間帯に分けたグループ別リンクに分類した後に、各グループ別リンクを時間順に繋げてグループ分類リンクを構成する第１ソート処理部と、
前記グループ分類リンクのブロック情報テーブルを最古のタイムスタンプ側から順番に取り出してタイムスタンプの昇順に並ぶ位置に挿入して前記リンクを再構築する第２ソート処理部と、
を備えたことを特徴とする階層ストレージシステム。（１）
【０１８２】
（付記２）
付記１記載の階層ストレージシステムに於いて、前記リンク管理部は、
前記リストア処理部により前記揮発メモリに前記ブロック情報テーブルをリストアした際に、各ブロック情報テーブルに対応してリンクテーブルを生成し、
前記第１ソート処理部及び第２ソート処理部でリンクを構成する際に、リンクを繋ぐポインタを前記リンクテーブルに格納することを特徴とする階層ストレージシステム。
【０１８３】
（付記３）
付記１記載の階層ストレージシステムに於いて、
前記第１ソート処理部は、
リストアした前記ブロック情報テーブルから検索した最古のタイムスタンプから最新のタイムスタンプまでの時間を所定数の時間帯に分割して複数のグループ別リンクを生成し、
前記ブロック情報テーブルをアドレス順に取出してタイムスタンプの属する時間帯のグループ別リンクに挿入してアドレス順に繋ぎ、
グループ分け終了後に、各グループ別リンクを時間順に繋げてグループ分類リンクを構成することを特徴とする階層ストレージシステム。（２）
【０１８４】
（付記４）
付記１記載の階層ストレージシステムに於いて、
前記第２ソート処理部は、
前記リンクのＬＲＵ側を前方とし、ＭＲＵ側を後方として処理対象テーブルを整列済みリンクのタイムスタンプ順となる位置に挿入する繋ぎ替え処理として、
挿入位置前テーブル（Ａ）が存在する否かの第１条件、
処理対象テーブル（Ｙ）の対象位置後テーブル（Ｚ）が存在するか否かの第２条件、更に
挿入位置後テーブル（Ｂ）と処理対象テーブル（Ｙ）が隣接しているか否かの第３条件、
の３条件の組合せに基づく８つの繋ぎ替え処理ケースを予め設定し、
処理対象テーブルを取出すごとに前記３条件を判定して該当する繋ぎ替え処理ケースを選択して繋ぎ替え処理を実行することを特徴とする階層ストレージシステム。（３）
【０１８５】
（付記５）（第１ケース）
付記４記載の階層ストレージシステムに於いて、
前記第２ソート処理部は、前記３条件として、挿入位置前テーブル（Ａ）が存在し、処理対象テーブル（Ｙ）の対象位置後テーブル（Ｚ）が存在し、更に挿入位置後テーブル（Ｂ）と処理対象テーブル（Ｙ）が隣接していない場合の第１ケースとして、
挿入位置前テーブル（Ａ）の後ポインタを処理対象テーブル（Ｙ）に変更し、
挿入位置後テーブル（Ｂ）の前ポインタを処理対象テーブル（Ｙ）に変更し、
処理対象位置前テーブル（Ｘ）の後ポインタを対象位置後テーブル（Ｚ）に変更し、更に、
処理対象テーブル（Ｙ）の前ポインタを挿入位置前テーブル（Ａ）に変更すると共に後ポインタを挿入位置後テーブル（Ｂ）に変更する、
ことを特徴とする階層ストレージシステム。
【０１８６】
（付記６）（第２ケース）
付記４記載の階層ストレージシステムに於いて、
前記第２ソート処理部は、前記３条件として、挿入位置前テーブル（Ａ）が存在し、処理対象テーブル（Ｙ）の対象位置後テーブル（Ｚ）が存在し、更に挿入位置後テーブル（Ｂ）と処理対象テーブル（Ｙ）が隣接している場合の第２ケースとして、
挿入位置前テーブル（Ａ）の後ポインタを処理対象テーブル（Ｙ）に変更し、
挿入位置後テーブル（Ｂ）の前ポインタを処理対象テーブル（Ｙ）に変更すると共に後ポインタを対象位置後テーブル（Ｚ）に変更し、
処理対象テーブル（Ｙ）の前ポインタを挿入位置前テーブル（Ａ）に変更すると共に後ポインタを挿入位置後テーブル（Ｂ）に変更し、更に、
対象位置後テーブル（Ｚ）の後ポインタを挿入位置後テーブル（Ｂ）に変更する、
ことを特徴とする階層ストレージシステム。
【０１８７】
（付記７）（第３ケース）
付記４記載の階層ストレージシステムに於いて、
前記第２ソート処理部は、前記３条件として、挿入位置前テーブル（Ａ）が存在し、処理対象テーブル（Ｙ）の対象位置後テーブル（Ｚ）が存在せず、更に挿入位置後テーブル（Ｂ）と処理対象テーブル（Ｙ）が隣接していない場合の第３ケースとして、
挿入位置前テーブル（Ａ）の後ポインタを処理対象テーブル（Ｙ）に変更し、
挿入位置後テーブル（Ｂ）の前ポインタを処理対象テーブル（Ｙ）に変更し、
対象位置前テーブル（Ｘ）の後ポインタをリンク後端（ＮＵＬＬ）に変更し、更に、
処理対象テーブル（Ｙ）の前ポインタを挿入位置前テーブル（Ａ）に変更すると共に後ポインタを挿入位置後テーブル（Ｂ）に変更する、
ことを特徴とする階層ストレージシステム。
【０１８８】
（付記８）（第４ケース）
付記４記載の階層ストレージシステムに於いて、
前記第２ソート処理部は、前記３条件として、挿入位置前テーブル（Ａ）が存在し、処理対象テーブル（Ｙ）の対象位置後テーブル（Ｚ）が存在せず、更に挿入位置後テーブル（Ｂ）と処理対象テーブル（Ｙ）が隣接している場合の第４ケースとして、
挿入位置前テーブル（Ａ）の後ポインタを処理対象テーブル（Ｙ）に変更し、
挿入位置後テーブル（Ｂ）の前ポインタを処理対象テーブル（Ｙ）に変更すると共に後ポインタをリンク後端（ＮＵＬＬ）に変更し、更に、
処理対象テーブル（Ｙ）の前ポインタを挿入位置前テーブル（Ａ）に変更すると共に後ポインタを挿入位置後テーブル（Ｂ）に変更する、
ことを特徴とする階層ストレージシステム。
【０１８９】
（付記９）（第５ケース）
付記４記載の階層ストレージシステムに於いて、
前記第２ソート処理部は、前記３条件として、挿入位置前テーブル（Ａ）が存在せず、処理対象テーブル（Ｙ）の対象位置後テーブル（Ｚ）が存在し、更に挿入位置後テーブル（Ｂ）と処理対象テーブル（Ｙ）が隣接していない場合の第５ケースとして、
挿入位置後テーブル（Ｂ）の後ポインタを処理対象テーブル（Ｙ）に変更し、
対象位置前テーブル（Ｘ）の前ポインタを対象位置後テーブル（Ｚ）に変更し、
処理対象テーブル（Ｙ）の前ポインタをリンク先端（ＮＵＬＬ）に変更すると共に後ポインタを挿入位置後テーブル（Ｂ）に変更し、更に
対象位置後テーブル（Ｚ）の前ポインタを対象位置前テーブル（Ｘ）に変更する、
ことを特徴とする階層ストレージシステム。
【０１９０】
（付記１０）（第６ケース）
付記４記載の階層ストレージシステムに於いて、
前記第２ソート処理部は、前記３条件として、挿入位置前テーブル（Ａ）が存在せず、処理対象テーブル（Ｙ）の対象位置後テーブル（Ｚ）が存在し、更に挿入位置後テーブル（Ｂ）と処理対象テーブル（Ｙ）が隣接している場合の第６ケースとして、
挿入位置後テーブル（Ｂ）の前ポインタを処理対象テーブル（Ｙ）に変更すると共に後ポインタを対象位置後テーブル（Ｚ）に変更し、
処理対象テーブル（Ｙ）の前ポインタをリンク先端（ＮＵＬＬ）に変更すると共に後ポインタを挿入位置後テーブル（Ｂ）に変更し、更に
対象位置後テーブル（Ｚ）の前ポインタを挿入位置後テーブル（Ｂ）に変更する、
ことを特徴とする階層ストレージシステム。
【０１９１】
（付記１１）（第７ケース）
付記４記載の階層ストレージシステムに於いて、
前記第２ソート処理部は、前記３条件として、挿入位置前テーブル（Ａ）が存在せず、処理対象テーブル（Ｙ）の対象位置後テーブル（Ｚ）が存在せず、更に挿入位置後テーブル（Ｂ）と処理対象テーブル（Ｙ）が隣接していない場合の第７ケースとして、
挿入位置後テーブル（Ｂ）の前ポインタを処理対象テーブル（Ｙ）に変更し、
対象位置前テーブル（Ｘ）の後ポインタをリンク後端（ＮＵＬＬ）に変更し、更に、
処理対象テーブル（Ｙ）の前ポインタをリンク先端（ＮＵＬＬ）に変更すると共に後ポインタを挿入位置後テーブル（Ｂ）に変更する、ことを特徴とする階層ストレージシステム。
【０１９２】
（付記１２）（第８ケース）
付記４記載の階層ストレージシステムに於いて、
前記第２ソート処理部は、前記３条件として、挿入位置前テーブル（Ａ）が存在せず、処理対象テーブル（Ｙ）の対象位置後テーブル（Ｚ）が存在せず、更に挿入位置後テーブル（Ｂ）と処理対象テーブル（Ｙ）が隣接している場合の第８ケースとして、
挿入位置後テーブル（Ｂ）の前ポインタを処理対象テーブル（Ｙ）に変更すると共に後ポインタをリンク後端に変更し、更に、
処理対象テーブル（Ｙ）の前ポインタをリンク先端（ＮＵＬＬ）に変更すると共に後ポインタを挿入位置後テーブル（Ｂ）に変更する、
ことを特徴とする階層ストレージシステム。
【０１９３】
（付記１３）
付記１記載の階層ストレージシステムに於いて、電源再投入から入出力処理が開始されるまでの間の初期化処理中に前記リストア処理部、第１ソート処理部及び第２ソート処理部の処理を順次実行することを特徴とする階層ストレージシステム。
【０１９４】
（付記１４）（入出力処理開始後のソート）
付記１記載の階層ストレージシステムに於いて、前記第２ソート処理部は、入出力処理が開始されるまでに前記リンクの再構築が終了しなかった場合、入出力処理の開始時にソート処理を中断し、入出力開始後は一定時間ごとにソート処理を再開して一定時間後に中断する処理を繰り返すことを特徴とする階層ストレージシステム。
【０１９５】
（付記１５）
付記１記載の階層ストレージシステムに於いて、前記リンク管理部により生成管理するリンクは、
前記１次ストレージと前記２次ストレージの両方に存在する同期したデータブロックのブロック情報テーブルをタイムスタンプ順に繋げたヒットリンク、
前記１次ストレージに存在するが前記２次ストレージに存在しないか又は存在するが同期していないデータブロックのブロック情報テーブルをタイムスタンプ順に繋げたダーティリンク又は、
前記１次ストレージに存在する全てのデータブロックのブロック情報テーブルをタイムスタンプ順に繋げたＬＲＵリンクである、
ことを特徴とする階層ストレージシステム。
【０１９６】
（付記１６）
メモリ上にランダムに記憶されたタイムスタンプを有する複数の情報テーブルを、複数の時間帯に分けたグループ別リンクに分類した後に各グループ別リンクをタイムスタンプ順に繋げてグループ分類リンクを構成する第１ソート処理部と
前記グループ分類リンクの情報テーブルを最古のタイムスタンプ側から順番に取り出してタイムスタンプの昇順に並ぶ位置に挿入してリンクを構築する第２ソート処理部と、
を備えたことを特徴とするリンクソート装置。
【０１９７】
（付記１７）
付記１６記載のリンクソート装置に於いて、
前記第１ソート処理部は、
リストアした前記情報テーブルから検索した最古のタイムスタンプから最新のタイムスタンプまでの時間を所定数の時間帯に分割して複数のグループ別リンクを生成し、
前記情報テーブルをアドレス順に取出してタイムスタンプの属する時間帯のグループ別リンクに挿入してアドレス順に繋ぎ、
グループ分け終了後に、各グループ別リンクを時間順に繋げてグループ分類リンクを構成することを特徴とするリンクソート装置。
【０１９８】
（付記１８）
高速小容量の記憶装置を用いた１次ストレージと、低速大容量の記憶装置を用いた２次ストレージで構成され、前記１次ストレージを前記２次ストレージのキャッシュ装置として使用する階層記憶部と、
前記１次ストレージにデータブロックを書き込んだ際に、タイムスタンプを格納したブロック情報テーブルを揮発メモリ上に生成して管理すると共に前記揮発メモリ上のブロック情報テーブル群を所定タイミング毎に前記１次ストレージに書き込んで保存するブロック情報テーブル管理部と、
前記ブロック情報テーブルを生成した際に、タイムスタンプ順となる位置に前記ブロック情報テーブルを挿入してポインタにより繋げたリンクを前記揮発メモリ上に生成すると共に、前記ポインタを格納したリンクテーブルを生成して前記揮発メモリ上で管理するリンク管理部と、
上位装置からデータブロックの入出力要求を受けた際に、マッピングチェックに基づいて前記階層記憶部の入出力処理を実行する入出力処理部と、
を備えた階層ストレージシステムの制御方法に於いて、
電源再投入時に、前記１次ストレージから前記揮発メモリに前記ブロック情報テーブルをリストアするリストア処理ステップと、
リストアした前記ブロック情報テーブルを、複数の時間帯に分けたグループ別リンクに分類した後に各グループ別リンクを時間順に繋げてグループ分類リンクを構成する第１ソート処理ステップと
前記グループ分類リンクのブロック情報テーブルを最古のタイムスタンプ側から順番に取り出してタイムスタンプの昇順に並ぶ位置に挿入して前記リンクを再構築する第２ソート処理ステップと、
を備えたことを特徴とする階層ストレージシステムの制御方法。（４）
【０１９９】
（付記１９）
付記１８記載の階層ストレージシステムの制御方法に於いて、
前記第１ソート処理ステップは、
リストアした前記ブロック情報テーブルから検索した最古のタイムスタンプから最新のタイムスタンプまでの時間を所定数の時間帯に分割して複数のグループ別リンクを生成し、
前記ブロック情報テーブルをアドレス順に取出してタイムスタンプの属する時間帯のグループ別リンクに挿入してアドレス順に繋ぎ、
グループ分け終了後に、各グループ別リンクを時間順に繋げてグループ分類リンクを構成することを特徴とする階層ストレージシステムの制御方法。
【０２００】
（付記２０）
メモリ上にランダムに記憶されたタイムスタンプを有する複数の情報テーブルを、複数の時間帯に分けたグループ別リンクに分類した後に各グループ別リンクをタイムスタンプ順に繋げてグループ分類リンクを構成する第１ソート処理ステップと
前記グループ分類リンクの情報テーブルを最古のタイムスタンプ側から順番に取り出してタイムスタンプの昇順に並ぶ位置に挿入してリンクを構築する第２ソート処理ステップと、
を備えたことを特徴とするリンクソート方法。
【０２０１】
（付記２１）
付記２０記載のリンクソート方法に於いて、
前記第１ソート処理ステップは、
リストアした前記情報テーブルから検索した最古のタイムスタンプから最新のタイムスタンプまでの時間を所定数の時間帯に分割して複数のグループ別リンクを生成し、
前記情報テーブルをアドレス順に取出してタイムスタンプの属する時間帯のグループ別リンクに挿入してアドレス順に繋ぎ、
グループ分け終了後に、各グループ別リンクを時間順に繋げてグループ分類リンクを構成することを特徴とするリンクソート方法。
【０２０２】
（付記２２）
高速小容量の記憶装置を用いた１次ストレージと、低速大容量の記憶装置を用いた２次ストレージで構成され、前記１次ストレージを前記２次ストレージのキャッシュ装置として使用する階層記憶部と、
前記１次ストレージにデータブロックを書き込んだ際に、タイムスタンプを格納したブロック情報テーブルを揮発メモリ上に生成して管理すると共に前記揮発メモリ上のブロック情報テーブル群を所定タイミング毎に前記１次ストレージに書き込んで保存するブロック情報テーブル管理部と、
前記ブロック情報テーブルを生成した際に、タイムスタンプ順となる位置に前記ブロック情報テーブルを挿入してポインタにより繋げたリンクを前記揮発メモリ上に生成すると共に、前記ポインタを格納したリンクテーブルを生成して前記揮発メモリ上で管理するリンク管理部と、
上位装置からデータブロックの入出力要求を受けた際に、マッピングチェックに基づいて前記階層記憶部の入出力処理を実行する入出力処理部と、
を備えた階層ストレージシステムのコンピュータに、
電源再投入時に、前記１次ストレージから前記揮発メモリに前記ブロック情報テーブルをリストアするリストア処理ステップと、
リストアした前記ブロック情報テーブルを複数の時間帯に分けたグループ毎に分類した後に各グループをタイムスタンプ順に繋げてグループ分類リンクを構成する第１ソート処理ステップと、
前記グループ分類リンクのブロック情報テーブルを最古のタイムスタンプ側から順番に取り出してタイムスタンプの昇順に並ぶ位置に挿入して前記リンクを再構築する第２ソート処理ステップと、
を実行させることを特徴とする階層ストレージ制御プログラム。（５）
【０２０３】
（付記２３）
付記２２記載の階層ストレージ制御プログラムに於いて、
前記第１ソート処理ステップは、
リストアした前記ブロック情報テーブルから検索した最古のタイムスタンプから最新のタイムスタンプまでの時間を所定数の時間帯に分割して複数のグループ別リンクを生成し、
前記ブロック情報テーブルをアドレス順に取出してタイムスタンプの属する時間帯のグループ別リンクに挿入してアドレス順に繋ぎ、
グループ分け終了後に、各グループ別リンクを時間順に繋げてグループ分類リンクを構成することを特徴とする階層ストレージ制御プログラム。
【０２０４】
（付記２４）
コンピュータに、
メモリ上にランダムに記憶されたタイムスタンプを有する複数の情報テーブルを、複数の時間帯に分けたグループ別リンクに分類した後に各グループ別リンクをタイムスタンプ順に繋げてグループ分類リンクを構成する第１ソート処理ステップと
前記グループ分類リンクの情報テーブルを最古のタイムスタンプ側から順番に取り出してタイムスタンプの昇順に並ぶ位置に挿入してリンクを構築する第２ソート処理ステップと、
を実行させることを特徴とするプログラム。
【０２０５】
（付記２５）
付記２４記載のプログラムに於いて、
前記第１ソート処理ステップは、
リストアした前記情報テーブルから検索した最古のタイムスタンプから最新のタイムスタンプまでの時間を所定数の時間帯に分割して複数のグループ別リンクを生成し、
前記情報テーブルをアドレス順に取出してタイムスタンプの属する時間帯のグループ別リンクに挿入してアドレス順に繋ぎ、
グループ分け終了後に、各グループ別リンクを時間順に繋げてグループ分類リンクを構成することを特徴とするプログラム。
【図面の簡単な説明】
【０２０６】
【図１】本発明の原理説明図
【図２】本発明が適用されるペタバイト階層ストレージシステムの説明図
【図３】図２のディスクアレイ装置のハードウェア構成のブロック図
【図４】図２のペタバイト階層ストレージシステムにおけるソフトウェア構成の説明図
【図５】階層ストレージシステムの説明図
【図６】階層ストレージシステムにおけるデータ転送処理の説明図
【図７】本発明による機能構成の説明図
【図８】本発明におけるＬＲＵリンクの説明図
【図９】本発明におけるダーティリンクの説明図
【図１０】本発明におけるヒットリンクの説明図
【図１１】本発明におけるブロック情報テーブルの説明図
【図１２】本発明におけるリンクテーブルの説明図
【図１３】本発明の階層ストレージシステムの制御処理のフローチャート
【図１４】本発明におけるライト処理のフローチャート
【図１５】本発明におけるリード処理のフローチャート
【図１６】本発明による電源再投入時にリンクを再構成するための第１ソート処理の説明図
【図１７】図１６に続く第１ソート処理の説明図
【図１８】第１ソート処理に続いて行われる第２ソート処理の説明図
【図１９】第２ソート処理における３条件の組合せに対応した挿入ソート処理の８ケースのアルゴリズムの説明図
【図２０】第１ケースによる挿入ソート処理の説明図
【図２１】第２ケースによる挿入ソート処理の説明図
【図２２】第３ケースによる挿入ソート処理の説明図
【図２３】第４ケースによる挿入ソート処理の説明図
【図２４】第５ケースによる挿入ソート処理の説明図
【図２５】第６ケースによる挿入ソート処理の説明図
【図２６】第７ケースによる挿入ソート処理の説明図
【図２７】第８ケースによる挿入ソート処理の説明図
【図２８】本発明による電源再投入時のリンク生成処理のフローチャート
【図２９】図２８におけるステップＳ５の第１ソート処理のフローチャート
【図３０】図２８におけるステップＳ７の第２ソート処理のフローチャート
【図３１】図３０のステップＳ３によるケース分類処理のフローチャート
【符号の説明】
【０２０７】
１０：ペタバイト階層ストレージシステム
１２：ホスト
１２−１：実験データ管理サーバ
１２−２：文書データ管理サーバ
１２−３：画像データ管理サーバ
１４−１，１４−２，２２−１，２２−２，２５−１，２５−２：ファイバーチャネルスイッチ
１５：階層ストレージ
１６：ディスクアレイ装置
１８−１，１８−２：テープライブラリ
２０−１，２０−２：光ディスクライブラリ
２４，２４−１，２４−２：階層間制御サーバ
２６：保守端末
２８，２８−１１，２８−１２，２８−２１，２８−２２：チャネルアダプタ
３０−１，３０−２：制御モジュール
３２：ディスクアレイ
３２−１，３２−２：ディスクエンクロージャ
３４−１１〜３４−２５：磁気ディスク装置
３５−１，３５−２：ＤＭＡコントローラ
３６−１，３６−２：ＣＰＵ
３８，３８−１，３８−２：メモリ（揮発性）
４０：ディスクアダプタ
４０−１１，４０−１２，４０−２１，４０−２２：デバイスインタフェース
４２：アプリケーション
４４：ファイルシステム
４６：ディスクドライバ
４８：仮想ディスク処理部
５０：構成管理部
５２：磁気ディスク処理部
５４：階層間データ転送制御部
５６：磁気テープ処理部
５８：テープライブラリ
６０：ロボット
６２：テープドライブ
６４：カートリッジテープ
６８：１次ストレージ
７０：２次ストレージ
７２：仮想論理ユニット
７４：システムボリューム
７５：ブロック情報テーブル格納領域
７６：ユーザボリューム
８２：入出力処理部
８４：コマンドキュー
８５：ライト処理部
８６：リード処理部
８８：情報テーブル管理部
９０：リンク管理部
９２：リストア部
９４：第１ソート処理部
９６：第２ソート処理部
９８：ブロック情報テーブル領域
１００：リンクテーブル領域
１０２：ＬＲＵリンク領域
１０４：ダーティリンク領域
１０６：ヒットリンク領域
１０８：ＬＲＵリンク
１１０：ＬＲＵリンクターミナル
１１２，１１２−２〜１１２−（ｍ＋ｎ）：ブロック情報テーブル
１１４，１１４−１〜１１４−（ｍ＋ｎ）：リンクテーブル
１１６：ダーティリンク
１１８：ダーティリンクターミナル
１２０：ヒットリンク
１２２：ヒットリンクターミナル
１２４：データブロックステータス
１２６：タイムスタンプ情報
１２８：ヒットリンク／ダーティリンクの前ポインタ／後ポインタ
１３０：ＬＲＵリンクの前ポインタ／後ポインタ
１３２：リストア処理
１３４：タイムスタンプ抽出処理
１３６：グループ間差分算出処理
１３８：グループ範囲算出処理
１４０：グループ別リンク生成処理
１４０−２〜１４０−４：グループターミナル
１４２−１〜１４２−３：グループ別リンク
１４４：グループ分類リンク生成処理
１４６：リンクターミナル
１４８：グループ分類リンク
１５０：整列済リンク
１５２：対応表
【図１】
0004420351.tif 000002
【図２】
0004420351.tif 000003
【図３】
0004420351.tif 000004
【図４】
0004420351.tif 000005
【図５】
0004420351.tif 000006
【図６】
0004420351.tif 000007
【図７】
0004420351.tif 000008
【図８】
0004420351.tif 000009
【図９】
0004420351.tif 000010
【図１０】
0004420351.tif 000011
【図１１】
0004420351.tif 000012
【図１２】
0004420351.tif 000013
【図１３】
0004420351.tif 000014
【図１４】
0004420351.tif 000015
【図１５】
0004420351.tif 000016
【図１６】
0004420351.tif 000017
【図１７】
0004420351.tif 000018
【図１８】
0004420351.tif 000019
【図１９】
0004420351.tif 000020
【図２０】
0004420351.tif 000021
【図２１】
0004420351.tif 000022
【図２２】
0004420351.tif 000023
【図２３】
0004420351.tif 000024
【図２４】
0004420351.tif 000025
【図２５】
0004420351.tif 000026
【図２６】
0004420351.tif 000027
【図２７】
0004420351.tif 000028
【図２８】
0004420351.tif 000029
【図２９】
0004420351.tif 000030
【図３０】
0004420351.tif 000031
【図３１】
0004420351.tif 000032