(57)【特許請求の範囲】
【請求項１】
上位記憶階層の記憶領域と下位記憶階層の記憶領域とからなる階層記憶において、前記下位記憶階層から同一データ列を持つ領域を抽出する同一データ列抽出手段と、
前記同一データ列抽出手段で抽出された情報に基づいて、前記下位記憶階層の複数の記憶領域に対して、前記上位記憶階層の一つの領域を対応付けて、前記下位記憶階層から当該同一データ列を読出して当該一つの領域に格納する階層記憶制御手段と
を有することを特徴とする階層記憶制御装置。
【請求項２】
前記同一データ列を持つ領域の情報を記憶する同一データ列情報記憶手段を含み、
前記同一データ列抽出手段は、抽出した同一データ列を持つ領域の情報を前記同一データ列情報記憶手段に書込み、
前記階層記憶制御手段は、前記同一データ列情報記憶手段に記憶された情報を読出し、その読出した情報を基に対応付けを行うことを特徴とする請求項１記載の階層記憶制御装置。
【請求項３】
前記上位記憶階層の記憶領域と前記下位記憶階層の記憶領域とを対応付けるための情報を記憶する階層記憶管理情報記憶手段を含み、
前記階層記憶制御手段は、対応付けた領域の情報を前記階層記憶管理情報記憶手段に書込むことを特徴とする請求項１または請求項２に記載の階層記憶制御装置。
【請求項４】
前記階層記憶制御手段は、前記上位記憶階層の一つの領域に対応付けた下位記憶階層の複数の記憶領域のうちの一つの領域に対する書込み命令を受信すると、それらの領域に対する対応付けを解除することを特徴とする請求項１から請求項３のいずれかに記載の階層記憶制御装置。
【請求項５】
前記上位記憶階層がキャッシュメモリであり、前記下位記憶階層がハードディスクドライブであることを特徴とする請求項１から請求項４のいずれかに記載の階層記憶制御装置。
【請求項６】
請求項１から請求項４のいずれかに記載の階層記憶制御装置と、前記上位記憶階層と、前記下位記憶階層とを備えることを特徴とするストレージ装置。
【請求項７】
請求項５に記載の階層記憶制御装置と、前記キャッシュメモリと、前記ハードディスクドライブとを備えることを特徴とするストレージ装置。
【請求項８】
請求項１から請求項４のいずれかに記載の階層記憶制御装置と、前記上位記憶階層と、前記下位記憶階層とからなることを特徴とする階層記憶制御システム。
【請求項９】
請求項５に記載の階層記憶制御装置と、前記キャッシュメモリと、前記ハードディスクドライブとからなることを特徴とする階層記憶制御システム。
【請求項１０】
上位記憶階層の記憶領域と下位記憶階層の記憶領域とからなる階層記憶を制御する階層記憶制御方法であって、
前記下位記憶階層から同一データ列を持つ領域を抽出し、その抽出された情報に基づいて、前記下位記憶階層の複数の記憶領域に対して、前記上位記憶階層の一つの領域を対応付けて、前記下位記憶階層から当該同一データ列を読出して当該一つの領域に格納することを特徴とする階層記憶制御方法。
【請求項１１】
前記下位記憶階層の複数の領域のうち一つの領域に対する書込み命令を受信した時にそれらの領域に対する対応付けを解除することを特徴とする請求項１０記載の階層記憶制御方法。
【請求項１２】
前記上位記憶階層がキャッシュメモリであり、前記下位記憶階層がハードディスクドライブであることを特徴とする請求項１０または請求項１１に記載の階層記憶制御方法。
【請求項１３】
コンピュータに実行させるためのプログラムであって、
上位記憶階層の記憶領域と下位記憶階層の記憶領域とからなる階層記憶において、前記下位記憶階層から同一データ列を持つ領域を抽出して同一データ列情報として記憶する処理と、
前記同一データ列情報に基づいて、前記下位記憶階層の複数の記憶領域に対して、前記上位記憶階層の一つの領域を対応付けて、前記下位記憶階層から当該同一データ列を読出して当該一つの領域に格納する処理とを含むことを特徴とするプログラム。
【請求項１４】
前記コンピュータに、前記下位記憶階層の複数の領域のうち一つの領域に対する書込み命令を受信した時にそれらの領域に対する対応付けを解除させることを特徴とする請求項１３記載のプログラム。
【請求項１５】
前記上位記憶階層がキャッシュメモリであり、前記下位記憶階層がハードディスクドライブであることを特徴とする請求項１３または請求項１４に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は階層記憶制御装置、階層記憶制御システム及びそれらに用いる階層記憶制御方法及びそのプログラムに関し、特にコンピュータシステムにおける階層記憶の制御方法に関する。
【背景技術】
【０００２】
コンピュータシステムにおいては、階層記憶が利用されている。この階層記憶は、上位記憶階層として高速で小容量な記憶装置を、下位記憶階層として低速で大容量な記憶装置を使い、アクセスの空間的局所性や時間的局所性を利用することによって、比較的低いコストでアクセス性能と記憶容量とを両立させるものである。
【０００３】
例えば、ストレージ装置においては、上位記憶階層としてキャッシュ、下位記憶階層としてハードディスクドライブ（以下、ＨＤＤとする）を用いた階層記憶が利用される。キャッシュとしては、ＨＤＤと比較して高速なアクセスが可能なメモリ素子が用いられるため、上位記憶階層にキャッシュを用いることによって、下位記憶階層であるＨＤＤのアクセスの遅さを隠蔽する効果がある。
【０００４】
キャッシュを搭載したストレージ装置においては、ホストからデータの書込み要求を受けた場合、書込まれたデータを一時的にキャッシュに格納してホストに書込み応答を返し、ＨＤＤには後でキャッシュのデータを書込む。また、ホストからデータ読出し要求があった場合には、要求されたデータがキャッシュにある場合、そのデータをＨＤＤからリードせずにキャッシュのデータをホストに返す。この動作によって、ＨＤＤのアクセスの遅さが隠蔽されて、ストレージ装置のアクセス性能を向上させることができる。
【０００５】
一般的に、キャッシュに使われるメモリ素子は、ＨＤＤよりも容量単価が高額であるため、キャッシュの利用効率は高いことが望ましい。キャッシュの利用効率を高める方法としては、複数の区画に分割したキャッシュにおいて、重複キャッシュを避ける方法が提案されている（例えば、特許文献１参照）。
【０００６】
ところで、ストレージ装置が有するＨＤＤの記憶領域は複数の区画に分けられ、それぞれ独立したアドレス空間を持つ記憶領域として使用されることがある。これらの区画は、例えばＳＣＳＩ（Ｓｍａｌｌ  Ｃｏｍｐｕｔｅｒ  Ｓｙｓｔｅｍ  Ｉｎｔｅｒｆａｃｅ）規格においては区画に割当られた識別番号であるＬＵＮ（Ｌｏｇｉｃａｌ  Ｕｎｉｔ  Ｎｕｍｂｅｒ）によって識別される。
【０００７】
ストレージ内部に複数のＬＵＮがある場合には、ＬＵＮ間で部分的に同一のデータ列を持つ場合がある。例えば、同じオペレーティングシステムによって動作する２つのホストがそれぞれのシステムイメージを、同一のストレージ装置の異なるＬＵＮに格納している場合、オペレーティングシステムに関するデータ列の大部分は同じデータ列となる。
【０００８】
また、同じＬＵＮ内でも、同一のデータ列を重複して持つ場合がある。例えば、１つのＬＵＮ上に構成したファイルシステムにおいて、別のディレクトリに同じ内容のファイルが存在する場合等である。
【０００９】
このように、同じデータ列がある場合、ＨＤＤにはデータ列を一つしか記憶しないことによって、ＨＤＤの記憶領域の利用効率を高める技術として、デデュープリケーションと呼ばれる技術が知られている（例えば、非特許文献１参照）。
【００１０】
デデュープリケーションは、データを記憶する際に、異なるアドレスに同一のデータ列が無いかどうかを探し、同一のデータ列が有った場合、実際にＨＤＤにはデータ列を一つしか記憶しない。
【００１１】
但し、デデュープリケーションでは、異なるアドレスに対する同一のデータ列を、実際にはＨＤＤに一つしか持たないため、ＨＤＤに障害があった場合、失われるデータの影響が大きくなる。また、重複データを管理する情報が失われた場合には、復旧が非常に困難である。このため、データの可用性の観点からは、デデュープリケーションを行わずに、重複するデータもそれぞれ記憶する方が望ましい。
【００１２】
さらに、デデュープリケーションでは、データの書込みを行う度に、すでに記憶されたデータの中に同一のデータ列がないかを調べるため、書込み速度が遅くなる。このため、可用性やアクセス速度が重視されるシステムにおいては、デデュープリケーションを使うのは望ましくない場合がある。
【００１３】
【特許文献１】特開２００７−４１９０４号公報
【非特許文献１】「月刊［コンピュータワールド］２００７年１０月号」、ＩＤＧジャパン、２００７年１０月１日、ｐｐ．９８−１０３
【発明の開示】
【発明が解決しようとする課題】
【００１４】
しかし、本発明に関連するストレージ装置では、デデュープリケーションを使わない場合、ＨＤＤ内に同一のデータ列が複数ある時に、キャッシュ利用効率の低下を招き、ひいては性能低下につながることがある。その理由は、キャッシュの一つの領域は、ＨＤＤ内の一つの領域のみに対応付けられるため、キャッシュに同一のデータ列が複数存在する状態が起り得るためである。
【００１５】
これは、ストレージ装置に限らず、階層記憶を用いるシステム一般に共通する課題である。すなわち、階層記憶において、一つの上位記憶階層の領域は、一つの下位記憶階層の領域のみに対応付けられるため、下位記憶階層に同一のデータ列が複数ある時には、上位記憶階層に同一のデータ列が複数存在する状態が起こり得るため、上位記憶階層の利用効率の低下を招き、ひいては性能低下につながることがある。
【００１６】
そこで、本発明の目的は上記の問題点を解消し、階層記憶において、下位記憶階層に同一データ列が複数存在する時に、上位記憶階層に同一データ列が複数存在する状態を減らして、上位記憶階層の利用効率を上げることができる階層記憶制御装置、階層記憶制御システム及びそれらに用いる階層記憶制御方法及びそのプログラムを提供することにある。
【課題を解決するための手段】
【００１７】
本発明による階層記憶制御装置は、上位記憶階層の記憶領域と下位記憶階層の記憶領域とからなる階層記憶において、前記下位記憶階層から同一データ列を持つ領域を抽出する同一データ列抽出手段と、
前記同一データ列抽出手段で抽出された情報に基づいて、前記下位記憶階層の複数の記憶領域に対して、前記上位記憶階層の一つの領域を対応付けて、前記下位記憶階層から当該同一データ列を読出して当該一つの領域に格納する階層記憶制御手段と備えている。
【００１８】
本発明によるストレージ装置は、階層記憶制御装置と、前記上位記憶階層と、前記下位記憶階層とを備えてることを特徴とする。
【００１９】
本発明による階層記憶制御システムは、階層記憶制御装置と、前記上位記憶階層と、前記下位記憶階層とからなることを特徴とする。
【００２０】
本発明による階層記憶制御方法は、上位記憶階層の記憶領域と下位記憶階層の記憶領域とからなる階層記憶を制御する階層記憶制御方法であって、
前記下位記憶階層から同一データ列を持つ領域を抽出し、その抽出された情報に基づいて、前記下位記憶階層の複数の記憶領域に対して、前記上位記憶階層の一つの領域を対応付けて、前記下位記憶階層から当該同一データ列を読出して当該一つの領域に格納している。
【００２１】
本発明によるプログラムは、コンピュータに実行させるためのプログラムであって、
上位記憶階層の記憶領域と下位記憶階層の記憶領域とからなる階層記憶において、前記下位記憶階層から同一データ列を持つ領域を抽出して同一データ列情報として記憶する処理と、
前記同一データ列情報に基づいて、前記下位記憶階層の複数の記憶領域に対して、前記上位記憶階層の一つの領域を対応付けて、前記下位記憶階層から当該同一データ列を読出して当該一つの領域に格納する処理とを含むことを特徴とする。
【発明の効果】
【００２２】
本発明は、上記のような構成及び動作とすることで、階層記憶において、下位記憶階層に同一データ列が複数存在する時に、上位記憶階層に同一データ列が複数存在する状態を減らして、上位記憶階層の利用効率を上げることができるという効果が得られる。
【発明を実施するための最良の形態】
【００２３】
次に、本発明の実施の形態について図面を参照して説明する。図１は本発明の第１の実施の形態による階層記憶制御システムの構成例を示すブロック図である。図１において、本発明の第１の実施の形態による階層記憶制御システムは、ストレージ装置１と、ホスト２−１〜２−３とから構成されている。
【００２４】
ストレージ装置１は、ホストインタフェース部１０と、キャッシュ制御部１１と、キャッシュ１２と、ディスク制御部１３と、記憶部１４と、同一データ列抽出部１５と、ＨＤＤ（ハードディスクドライブ）１６−１〜１６−４とから構成されている。尚、ホストインタフェース部１０、キャッシュ制御部１１、ディスク制御部１３、記憶部１４、同一データ列抽出部１５は、本実施の形態による階層記憶制御装置に対応する構成要素である。
【００２５】
ホストインタフェース部１０は、ホスト２−１〜２−３との間でコマンドやデータの送受信を行う。キャッシュ制御部１１は、ホストインタフェース部１０を介してホスト２−１〜２−３から受けたコマンドの内容に応じて、ホスト２−１〜２−３から受け取ったデータをキャッシュ１２に格納する処理及びキャッシュ１２のデータを読出してホストに送る処理を行う。
【００２６】
キャッシュ１２は、データ記憶機能を有するデバイスである。キャッシュ１２の記憶空間は、ページと呼ぶ固定長の領域として管理する。ディスク制御部１３は、ＨＤＤ１６−１〜１６−４へのデータの書込みと、ＨＤＤ１６−１〜１６−４からのデータの読出しを行う。記憶部１４は、キャッシュ管理情報記憶部１４０と、同一データ列情報記憶部１４１とを含む。
【００２７】
キャッシュ管理情報記憶部１４０は、キャッシュ１２のページとＨＤＤ１６−１〜１６−４の領域を対応付けるためのデータを記憶する。キャッシュ管理情報記憶部１４０のデータ構造については後述する。
【００２８】
同一データ列情報記憶部１４１は、同一データ列を持つＨＤＤ１６−１〜１６−４の異なる領域を対応付けるためのデータを記憶する。同一データ列情報記憶部１４１のデータ構造についても後述する。
【００２９】
同一データ列抽出部１５は、同一データ列を持つＨＤＤ１６−１〜１６−４の異なる領域を抽出し、抽出した情報を同一データ列情報記憶部１４１に格納する。ＨＤＤ１６−１〜１６−４は、データ記憶機能を有するデバイスである。図１には、４台のＨＤＤ１６−１〜１６−４を図示しているが、１台、２台、３台、あるいは５台以上であってもよい。
【００３０】
ＨＤＤ１６−１〜１６−４の記憶領域のアドレス空間は、複数の区画に分割することが可能であり、区画はＬＵＮ（Ｌｏｇｉｃａｌ  Ｕｎｉｔ  Ｎｕｍｂｅｒ）によって識別され、同一ＬＵＮの中の位置はＬＢＡ（Ｌｏｃｉｃａｌ  Ｂｌｏｃｋ  Ａｄｄｒｅｓｓ）によって識別されるものとする。すなわち、アドレスとしてホストＬＵＮとＬＢＡとを指定することによって、ＨＤＤ１６−１〜１６−４の特定の位置に一意にアクセスすることが可能である。
【００３１】
尚、ＨＤＤ１６−１〜１６−４は、ＲＡＩＤ（Ｒｅｄｕｎｄａｎｔ  Ａｒｒａｙｓ  ｏｆ  Ｉｎｄｅｐｅｎｄｅｎｔ  Ｄｉｓｋｓ）構成で利用されていてもよい。この場合、ディスク制御部１３はＲＡＩＤコントローラとして動作することとなる。
【００３２】
本実施の形態では、ＬＢＡあたり、５１２Ｂｙｔｅのデータを格納するものとする。また、キャッシュ１２におけるページの大きさは３２ＫＢｙｔｅとする。すなわち、１つのページは、連続した６４のＬＢＡに対応するものとする。１つのページに対応するＨＤＤの記憶領域のアドレスは、ＬＵＮ及び先頭のＬＢＡによって識別するものとする。
【００３３】
図５に、キャッシュ１２の記憶空間とＨＤＤの記憶空間との対応例を示す。図５は本発明の第１の実施の形態における記憶空間を概念的に示す図である。図５においては、キャッシュ１２の記憶空間（Ｘ１）とＨＤＤの記憶空間（Ｘ２）とを図示している。
【００３４】
キャッシュ１２の記憶空間Ｘ１は０から（ｍ−１）のページ番号がついた、ｍ個のページを持つ。ＨＤＤの記憶空間Ｘ２はＬＵＮ＝０とＬＵＮ＝１との２つの区画に分けられており、ＬＵＮ＝０はＬＢＡが０〜｛（ｎ０×Ｐ）−１｝の記憶空間を持ち、ＬＵＮ＝１はＬＢＡが０〜｛（ｎ１×Ｐ）−１｝の記憶空間を持つ。ここで、Ｐはキャッシュ記憶空間における１ページに対応するＬＢＡの数である。すなわち、本実施の形態では、ＬＢＡの数Ｐ＝６４である。また、ｎ０とｎ１はそれぞれ自然数であり、ＬＢＡ＝０の記憶空間とＬＢＡ＝１の記憶空間とをページ数に換算した値である。
【００３５】
図５において、キャッシュ記憶空間Ｘ１のページ番号＝１のページには、ＨＤＤ記憶空間Ｘ２のＬＵＮ＝０、ＬＢＡ＝Ｐ〜（２Ｐ−１）が対応している。また、キャッシュ記憶空間Ｘ１のページ番号＝３のページには、ＬＵＮ＝０、ＬＢＡ＝５Ｐ〜（６Ｐ−１）とＬＵＮ＝１、ＬＢＡ＝Ｐ〜（２Ｐ−１）とが対応している。さらに、キャッシュ記憶空間Ｘ１のページ番号＝（ｍ−２）のページには、ＬＵＮ＝１、ＬＢＡ＝４Ｐ〜（５Ｐ−１）が対応している。ここで、キャッシュ記憶空間Ｘ１の１つのページに対して、ＨＤＤ記憶空間Ｘ２の複数のＬＵＮとＬＢＡとが対応し得ることが本発明の特徴である。
【００３６】
ホスト２−１〜２−３は、それぞれストレージ装置１に対してデータの書込み要求と読出し要求とを行う。図１には、ストレージ装置１に３台のホスト２−１〜２−３が接続されているが、１台、２台、あるいは４台以上であってもよい。
【００３７】
また、図１では、ストレージ装置１とホスト２−１〜２−３とが直接接続されているが、これらはＦＣ（Ｆｉｂｒｅ  Ｃｈａｎｎｅｌ）等のプロトコルを用いるＳＡＮ（Ｓｔｏｒａｇｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）を介して接続されていてもよい。
【００３８】
次に、キャッシュ管理情報記憶部１４０のデータ構造を図２と図３とを用いて説明する。図２は本発明の第１の実施の形態におけるキャッシュ管理情報記憶部１４０のデータ構造の一部を示す図であり、図３は本発明の第１の実施の形態におけるキャッシュ管理情報記憶部１４０のデータ構造の一部を示す図である。
【００３９】
これらの図において、キャッシュ管理情報記憶部１４０は、キャッシュ管理テーブル１４００と、アドレスレコード１４０１と、ページポインタ１４０２と、未使用ポインタヘッド１４０３とからなる。
【００４０】
キャッシュ管理テーブル１４００は、目的のアドレスに対応するアドレスレコード１４０１を探索するために利用するテーブルである。キャッシュ管理テーブル１４００は、複数の列を持ち、各列は識別番号と、アドレスレコード１４０１へのポインタとを持つ。本実施の形態では、キャッシュ管理テーブル１４００が、それぞれ０から７までの識別番号を持つ８つの列を持つものとする。
【００４１】
アドレスレコード１４０１は、アドレス情報としてＬＵＮ番号とＬＢＡとを持ち、さらに、別のアドレスレコード１４０１へのポインタと、ページポインタ１４０２へのポインタとを持つ。アドレスレコード１４０１が持つアドレス情報は、ページに対応するＨＤＤの記憶空間の先頭アドレスである。
【００４２】
ページポインタ１４０２は、キャッシュ１２の１つのページへのポインタ及びアドレスレコード１４０１へのポインタ、別のページポインタ１４０２へのポインタを持つ。ページポインタ１４０２の数は、キャッシュ１２の記憶空間のページ数と同じ数とする。アドレスレコード１４０１へのポインタは、複数持つことが可能である。未使用ページポインタヘッド１４０３は、ページポインタ１４０２へのポインタを持つ。
【００４３】
アドレスレコード１４０１は、キャッシュ管理テーブル１４００の列をヘッドとした一方向の連結リスト構造をとる。アドレスレコード１４０１は、アドレスレコード１４０１が持つアドレス情報から算出されるハッシュ値と同じ識別番号を持つキャッシュ管理テーブル１４００の列をヘッドとするリストに接続される。
【００４４】
本実施の形態では、アドレス情報のＬＢＡを上記の１ページに対応するＬＢＡの数Ｐで割った値について８の剰余を算出したものをハッシュ値とする。例えば、アドレス情報としてＬＵＮ＝０、ＬＢＡ＝１８Ｐを持つアドレスレコード１４０１のハッシュ値は、（１８Ｐ）／Ｐ＝１８について８の剰余を算出した２であるので、キャッシュ管理テーブル１４００のうち２の識別子を持つ列に接続される。
【００４５】
また、アドレスレコード１４０１と、ページポインタ１４０２とは多対１の双方向リンクによって関連付けられる。すなわち、１つのアドレスレコード１４０１からは１つのページポインタ１４０２のみにリンクされるが、１つのページポインタ１４０２は複数のアドレスレコード１４０１からリンクされ得る。
【００４６】
さらに、１つのページポインタ１４０２からは複数のアドレスレコード１４０１にリンクされうるが、１つのアドレスレコード１４０１は、１つのページポインタ１４０２からのみリンクされる。アドレスレコード１４０１からリンクされたページポインタ１４０２について、別のページポインタ１４０２へのポインタは未使用である。
【００４７】
アドレスレコード１４０１とのリンクを持たないページポインタ１４０２は、未使用ページポインタヘッド１４０３をヘッドとする一方向の連結リスト構造をとる。未使用ページポインタヘッド１４０３をヘッドとするリストに接続されているページポインタ１４０２については、アドレスレコード１４０１へのポインタは未使用である。
【００４８】
次に、同一データ列情報記憶部１４１のデータ構造を図４を用いて説明する。図４は本発明の第１の実施の形態における同一データ列情報記憶部１４１のデータ構造を示す図である。
【００４９】
図４において、同一データ列情報記憶部１４１は、同一データ列管理テーブル１４１０と、同一管理レコード１４１１とからなる。同一データ列管理テーブル１４１０は、目的のアドレスに対応する同一管理レコード１４１１を探索するために利用するテーブルである。
【００５０】
同一データ列管理テーブル１４１０は、複数の列を持ち、各列は、識別番号と、同一管理レコード１４１１へのポインタとを持つ。本実施の形態では、同一データ列管理テーブル１４１０が、それぞれ０から７までの識別番号を持つ８つの列を持つものとする。
【００５１】
同一管理レコード１４１１は、アドレス情報としてＬＵＮとＬＢＡとを持ち、さらに、別の同一管理レコード１４１１へのポインタを持つ。別の同一管理レコード１４１１へのポインタは複数持つことが可能である。同一管理レコード１４１１は、同一データ列管理テーブル１４１０の１つの列をヘッドとした一方向の連結リスト構造をとる。
【００５２】
また、同一管理レコード１４１１は、１つ以上の別の同一管理レコード１４１１と双方向リンクによって関連付けられる。同一管理レコード１４１１は、同一管理レコード１４１１が持つアドレス情報から算出されるハッシュ値と同じ識別番号を持つ同一データ列管理テーブル１４１０の列をヘッドとするリストに接続される。
【００５３】
本実施の形態では、アドレス情報のＬＢＡを上記の１ページに対応するＬＢＡの数Ｐで割った値について８の剰余を算出したものをハッシュ値とする。例えば、アドレス情報としてＬＵＮ＝０、ＬＢＡ＝１８Ｐを持つ同一管理レコード１４１１のハッシュ値は、（１８Ｐ）／Ｐ＝１８について８の剰余を算出した２であるので、同一データ列管理テーブル１４１０のうち２の識別子を持つ列に接続される。
【００５４】
図６及び図７は本発明の第１の実施の形態における同一データ列抽出処理の動作を示すフローチャートであり、図８及び図９は本発明の第１の実施の形態における同一データ列情報登録処理の動作を示すフローチャートである。図１０は本発明の第１の実施の形態におけるリード処理の動作を示すフローチャートであり、図１１は本発明の第１の実施の形態におけるアドレスレコードサーチの動作を示すフローチャートである。
【００５５】
図１２は本発明の第１の実施の形態における未使用ページポインタ取得処理の動作を示すフローチャートであり、図１３は本発明の第１の実施の形態における同一管理レコードサーチの動作を示すフローチャートである。図１４は本発明の第１の実施の形態における同一管理レコードリンク処理の動作を示すフローチャートであり、図１５は本発明の第１の実施の形態におけるライト処理の動作を示すフローチャートである。これら図１〜図１５を参照して本発明の第１の実施の形態による階層記憶制御システムの動作について説明する。
【００５６】
尚、本実施の形態の動作の説明では、説明の複雑さを避けるため、読出し要求（リードコマンド）や書込み要求（ライトコマンド）によって指定されるＬＢＡはページの割当対象の先頭となるＬＢＡの値のみとし、１回の要求での読出しや書込みのデータ長は１ページ分とする。但し、本発明は、この場合に限定されるものではなく、一般的な条件に拡張する事は容易である。さらに、図６〜図１５に示す処理動作は、ストレージ装置１内のコンピュータ［例えば、ＣＰＵ（中央処理装置）等］（図示せず）に、プログラムを実行させることで実現可能である。
【００５７】
まず、ストレージ装置１がホスト２−１〜２−３（以下、これらを総称してホスト２とする）からリードコマンドもライトコマンドも受けていない場合の動作について説明する。この時、同一データ列抽出部１５はＨＤＤ１６−１〜１６−４（以下、これらを総称してＨＤＤ１６とする）から同一データ列を探索して同一データ列情報記憶部１４１に登録する処理を行う。この処理について図６〜図９を参照して説明する。
【００５８】
同一データ列抽出部１５は、処理を行うための変数としてＬＵＮ１とＬＢＡ１とＬＵＮ２とＬＢＡ２とを持つ。ＬＵＮ１とＬＵＮ２とにはＬＵＮの値が代入され、ＬＢＡ１とＬＢＡ２とにはＬＢＡの値が代入される。本実施の形態では、ＬＵＮは１つ以上が定義され、ＬＵＮの番号は０から連続した値が割り振られるものとする。また、それぞれのＬＵＮは１ページに相当する以上のＬＢＡを持つものとする。
【００５９】
同一データ列抽出部１５は、まず、ＬＵＮ１、ＬＢＡ１、ＬＵＮ２、ＬＢＡ２すべて０を代入する（図６ステップＡ１）。次に、同一データ列抽出部１５は、ＬＵＮ１＝ＬＵＮ２かつＬＢＡ１＝ＬＢＡ２であるかどうかを判定する（図６ステップＡ２）。同一データ列抽出部１５は、ＬＵＮ１＝ＬＵＮ２かつＬＢＡ１＝ＬＢＡ２である場合、後述のステップＡ６の処理を行う。
【００６０】
同一データ列抽出部１５は、ＬＵＮ１≒ＬＵＮ２もしくはＬＢＡ１≒ＬＢＡ２の場合、ＬＵＮ１のＬＢＡ１からＬＢＡ１＋Ｐ−１に格納されたデータ列とＬＵＮ２のＬＢＡ２からＬＢＡ２＋Ｐ−１に格納されたデータ列との内容を比較する（図６ステップＡ３）。同一データ列抽出部１５は、データ列が完全に同じであった場合（図６ステップＡ４）、同一データ列情報登録を行う（図６ステップＡ５）。この同一データ列情報登録についての詳細は、後述する。
【００６１】
同一データ列抽出部１５は、ＬＵＮ１＝ＬＵＮ２かつＬＢＡ１＝ＬＢＡ２である場合（図６ステップＡ２）、及びステップＡ５で同一データ列情報登録を行った後、ＬＢＡ２にＬＢＡ２＋Ｐの値を代入し（図６ステップＡ６）、ＬＵＮ＝ＬＵＮ２かつＬＢＡ＝ＬＢＡ２が存在するかどうかを調べる（図６ステップＡ７）。
【００６２】
ＬＵＮ＝ＬＵＮ２かつＬＢＡ＝ＬＢＡ２が存在する場合、同一データ列抽出部１５は、ステップＡ２に戻って、それ以降の処理を行う。ＬＵＮ＝ＬＵＮ２かつＬＢＡ＝ＬＢＡ２が存在しない場合、同一データ列抽出部１５は、ＬＢＡ２＝０とし（図６ステップＡ８）、ＬＵＮ２にＬＵＮ２＋１を代入する（図６ステップＡ９）。
【００６３】
次に、同一データ列抽出部１５は、ＬＵＮ＝ＬＵＮ２が存在するかどうかを調べ（図７ステップＡ１０）、ＬＵＮ＝ＬＵＮ２が存在する場合、ステップＡ２に戻ってそれ以降の処理を行う。同一データ列抽出部１５は、ＬＵＮ＝ＬＵＮ２が存在しない場合、ＬＵＮ２＝０とし（図７ステップＡ１１）、ＬＢＡ１にＬＢＡ１＋Ｐを代入する（図７ステップＡ１２）。
【００６４】
その後、同一データ列抽出部１５は、ＬＵＮ＝ＬＵＮ１かつＬＢＡ１＝ＬＢＡ１が存在するかどうかを調べ（図７ステップＡ１３）、ＬＵＮ＝ＬＵＮ１かつＬＢＡ１＝ＬＢＡ１が存在する場合、ステップＡ２に戻ってそれ以降の処理を行う。同一データ列抽出部１５は、ＬＵＮ＝ＬＵＮ１かつＬＢＡ１＝ＬＢＡ１が存在しない場合、ＬＢＡ１＝０を代入し（図７ステップＡ１４）、ＬＵＮ１にＬＵＮ１＋１を代入する（図７ステップＡ１５）。
【００６５】
さらに、同一データ列抽出部１５は、ＬＵＮ＝ＬＵＮ１が存在するかどうかを調べ（図７ステップＡ１６）、ＬＵＮ＝ＬＵＮ１が存在した場合、ステップＡ２に戻ってそれ以降の処理を行う。同一データ列抽出部１５は、ＬＵＮ＝ＬＵＮ１が存在しない場合、ＬＵＮ１＝０として（図７ステップＡ１７）、ステップＡ２に戻ってそれ以降の処理を行う。
【００６６】
次に、上記のステップＡ５の同一データ列情報登録の詳細について、図８及び図９を参照して説明する。
【００６７】
まず、同一データ列抽出部１５は、ＬＢＡ１のハッシュ値を算出し（図８ステップＢ１）、同一データ列情報記憶部１４１の同一データ列管理テーブル１４１０のハッシュ値を持つ列からリンクをたどり、ＬＵＮ１，ＬＢＡ１に対応する同一管理レコード１４１１を探索する（図８ステップＢ２）。
【００６８】
同一データ列抽出部１５は、ＬＵＮ１，ＬＢＡ１に対応する同一管理レコード１４１１が登録済みでなかった場合、ＬＵＮ１，ＬＢＡ１に対応する同一管理レコード１４１１を作成して、同一データ列管理テーブル１４１０のハッシュ値を持つ列をヘッドとするリストの最後尾に挿入する（図８ステップＢ３）。
【００６９】
同一データ列抽出部１５は、このステップＢ３の後、及びステップＢ２でＬＵＮ１，ＬＢＡ１に対応する同一管理レコード１４１１が登録済みであった場合、ＬＢＡ２のハッシュ値を計算し（図８ステップＢ４）、同一データ列情報記憶部１４１の同一データ列管理テーブル１４１０のハッシュ値を持つ列からリンクをたどり、ＬＵＮ２，ＬＢＡ２に対応する同一管理レコード１４１１を探索する（図８ステップＢ５）。
【００７０】
同一データ列抽出部１５は、ＬＵＮ２，ＬＢＡ２に対応する同一管理レコード１４１１が登録済みでなかった場合、ＬＵＮ２，ＬＢＡ２に対応する同一管理レコード１４１１を作成して、同一データ列管理テーブル１４１０のハッシュ値を持つ列をヘッドとするリストの最後尾に挿入する（図８ステップＢ６）。
【００７１】
同一データ列抽出部１５は、このステップＢ６の後、及びステップＢ５でＬＵＮ２，ＬＢＡ２に対応する同一管理レコード１４１１が登録済みであった場合、ＬＵＮ１，ＬＢＡ１に対応する同一管理レコード１４１１とＬＵＮ２，ＬＢＡ２に対応する同一管理レコード１４１１とが相互リンク済みか否かを調べる（図８ステップＢ７）。
【００７２】
同一データ列抽出部１５は、相互リンク済みでなかった場合、ＬＵＮ１，ＬＢＡ１に対応する同一管理レコード１４１１とＬＵＮ２，ＬＢＡ２に対応する同一管理レコード１４１１とを相互リンクする（図８ステップＢ８）。
【００７３】
同一データ列抽出部１５は、このステップＢ８の後、及びステップＢ７で、ＬＵＮ１，ＬＢＡ１に対応する同一管理レコード１４１１とＬＵＮ２，ＬＢＡ２に対応する同一管理レコード１４１１とが相互リンク済みであった場合、ＬＵＮ１，ＬＢＡ１に対応する同一管理レコード１４１１にＬＵＮ２，ＬＵＮ２に対応する同一管理レコード１４１１以外の同一管理レコード１４１１以外へのリンクがあれば、ＬＵＮ２，ＬＵＮ２に対応する同一管理レコード１４１１と、ＬＵＮ１，ＬＢＡ１に対応する同一管理レコード１４１１のＬＵＮ２，ＬＵＮ２に対応する同一管理レコード１４１１以外の全てのリンク先の同一管理レコード１４１１との相互リンクを行う（図９ステップＢ９）。
【００７４】
次に、同一データ列抽出部１５は、ＬＵＮ２，ＬＢＡ２に対応する同一管理レコード１４１１にＬＵＮ１，ＬＵＮ１に対応する同一管理レコード１４１１以外のリンクがあれば、ＬＵＮ１，ＬＵＮ１に対応する同一管理レコード１４１１と、ＬＵＮ２，ＬＢＡ２に対応する同一管理レコード１４１１のＬＵＮ１，ＬＵＮ１に対応する同一管理レコード１４１１以外の全てのリンク先の同一管理レコード１４１１との相互リンクを行う（図９ステップＢ１０）。
【００７５】
本実施の形態では、上記のステップＢ９の処理とステップＢ１０の処理とを行うことによって、同一データ列を持つアドレスが３つ以上ある場合でも、同一データ列であることを認識することができる。
【００７６】
本実施の形態では、上述したステップＡ１〜ステップＡ１７の処理、ステップＢ１〜ステップＢ１０の処理を繰り返すことによって、同一のデータ列を持つアドレス情報の組み合わせが、同一データ列情報記憶部１４１に蓄積されていく。尚、本実施の形態では、同一データ列を抽出する方法として、単純にデータの内容の一致を順次比較する方法について説明したが、本発明は同一データ列を抽出する手段には依存しない。この同一データ列を抽出する方法については、例えば、予め各データ列のハッシュ値を計算しておき、ハッシュ値を比較することによって、データ列の比較対象を絞り込む方法を取ってもよい。
【００７７】
また、同一データ列の抽出は順次行われていくため、必ずしも同一データ列を持った全てのアドレス情報の組み合わせが同一データ列情報記憶部１４１に登録されているわけではない。登録されている情報が多い程、本発明の効果は顕著であるが、登録されている情報が少ない場合でも以降で説明する動作には影響しない。
【００７８】
尚、リードコマンドもしくはライトコマンドを受けた場合、ステップＡ１〜ステップＡ１７の処理と、ステップＢ１〜ステップＢ１０の処理とを一度中断し、ライトコマンドの処理もしくはライトコマンドの処理が終了してから再開する。但し、ステップＡ３〜ステップＡ５を実行中にライトコマンドを受けた場合には、同一データ列の関係性が崩れることを避けるため、ステップＡ４でデータ列が同じでないと判断した後か、ステップＡ５まで実行した後に、コマンドに対応した動作に移行する。
【００７９】
次に、図１０〜図１４を参照して本実施の形態におけるリード処理動作について説明する。まず、図１０を参照して処理動作全体の流れについて説明する。
【００８０】
ホスト２からリードコマンドを受けると、キャッシュ制御部１１は、リードコマンドに含まれるＬＵＮとＬＢＡとに対応するアドレスレコードサーチ処理を行う（図１０ステップＣ１）。このアドレスレコードサーチ処理の詳細については後述する。
【００８１】
キャッシュ制御部１１は、対応するアドレスレコード１４０１があった場合（図１０ステップＣ２）、対応アドレスレコード１４０１からリンクされたページポインタ１４０２のページを、対応ページとして（図１０ステップＣ３）、キャッシュ１２の対応ページに格納されているデータを読出してホスト２に送信する（図１０ステップＣ９）。
【００８２】
キャッシュ制御部１１は、対応するアドレスレコード１４０１がなかった場合（図１０ステップＣ２）、未使用ページポインタ取得処理を行い（図１０ステップＣ４）、ページポインタ１４０２を取得する。
【００８３】
次に、キャッシュ制御部１１は、同一管理レコードサーチ処理を行い（図１０ステップＣ５）、対応する同一管理レコード１４１１があるかを調べる。これら未使用ページポインタ取得処理及び同一管理レコードサーチ処理の詳細については後述する。
【００８４】
キャッシュ制御部１１は、同一管理レコードサーチ処理において、対応する同一管理レコード１４１１があった場合（図１０ステップＣ６）、同一管理レコードリンク処理を行う（図１０ステップＣ７）。キャッシュ制御部１１は、同一管理レコードリンク処理を行った後、及び図１０ステップＣ６において対応する同一管理レコード１４１１がなかった場合、ＨＤＤ１６からデータを読出して、ステップＣ４において取得したページポインタ１４０２に対応するページに格納し（図１０ステップＣ８）、キャッシュ１２の対応ページに格納されているデータを読出してホスト２に送信する（図１０ステップＣ９）。
【００８５】
次に、アドレスレコードサーチ処理（ステップＣ１）の詳細について図１１を参照して説明する。まず、キャッシュ制御部１１は、コマンドに含まれるＬＢＡのハッシュ値を算出する（図１１ステップＤ１）。
【００８６】
次に、キャッシュ制御部１１は、キャッシュ管理テーブル１４００の列の、上記のハッシュ値を持つ列からリンクをたどり、リードコマンドに含まれるＬＵＮとＬＢＡとに対応するアドレスレコード１４０１を探索する（図１１ステップＤ２）。リンクの最後尾まで見つからなかった場合には、対応するアドレスレコード１４０１がないものとする。
【００８７】
次に、未使用ページポインタ取得処理（ステップＣ４）の詳細について図１２を参照して説明する。
【００８８】
まず、キャッシュ制御部１１は、未使用ページポインタヘッド１４０３からリンクされているページポインタ１４０２があるかを調べる（図１２ステップＥ１）。
【００８９】
キャッシュ制御部１１は、ページポインタ１４０２がない場合、ページ開放処理を行う（図１２ステップＥ２）。ページ開放処理では、まずＬＲＵ（Ｌｅａｓｔ  Ｒｅｃｅｎｔ  Ｕｓｅｄ）アルゴリズムに基づいて開放するページポインタ１４０２を決定する。
【００９０】
次に、ページ開放処理では、開放するページポインタ１４０２がクリーン（ホスト２からキャッシュ１２のページポインタ１４０２に対応するページに書込まれたデータのうち、まだＨＤＤ１６に書込んでいないデータがない状態）であった場合、開放するページポインタ１４０２からリンクされたアドレスレコード１４０１をキャッシュ管理テーブル１４００の列をヘッドとするリンクから除去し、ページポインタ１４０２のポインタを全て削除し、ページポインタ１４０２を未使用ページポインタヘッド１４０３をヘッドとするリンクの最後尾に接続する。
【００９１】
ページ開放処理では、開放するページポインタ１４０２がダーティ（ホスト２からキャッシュ１２のページポインタ１４０２に対応するページに書込まれたデータのうち、まだＨＤＤ１６に書込んでいないデータがある状態）であった場合、ページポインタ１４０２に対応するページのデータを、ＨＤＤ１６の、ページポインタ１４０２からリンクされたアドレスレコード１４０１が持つＬＵＮ，ＬＢＡに書出した後、開放するページポインタ１４０２からリンクされたアドレスレコード１４０１をキャッシュ管理テーブル１４００の列をヘッドとするリンクから除去し、ページポインタ１４０２のポインタを全て削除し、ページポインタ１４０２を未使用ページポインタヘッド１４０３をヘッドとするリンクの最後尾に接続する。上記のページ開放処理は、１つ以上のページポインタ１４０２に対して行う。
【００９２】
キャッシュ制御部１１は、ページ開放処理の終了後、及び図１２ステップＥ１において未使用ページポインタヘッド１４０３からリンクされているページポインタ１４０２があった場合、未使用ページポインタヘッド１４０３をヘッドとしたリンクの先頭からページポインタ１４０２を取得する（図１２ステップＥ３）。
【００９３】
続いて、同一管理レコードサーチ処理（ステップＣ５）の詳細について図１３を参照して説明する。
【００９４】
まず、キャッシュ制御部１１は、コマンドに含まれるＬＵＮとＬＢＡとに対応するアドレスレコード１４０１を作成して、ＬＢＡから算出されるハッシュ値を持つキャッシュ管理テーブル１４００の列をヘッドとしたリンクの最後尾に挿入する（図１３ステップＦ１）。
【００９５】
次に、キャッシュ制御部１１は、アドレスレコード１４０１と、未使用ページポインタ取得処理（ステップＣ４）で取得したページポインタ１４０２との相互リンクを行う（図１３ステップＦ２）。
【００９６】
続いて、キャッシュ制御部１１は、上記のハッシュ値を持つ同一データ列管理テーブル１４１０の列からリンクをたどり、コマンドのＬＵＮとＬＢＡとに対応する同一管理レコード１４１１があるかを探す。キャッシュ制御部１１は、リンクの最後まで対応する同一管理レコード１４１１がない場合、対応する同一管理レコードはないものとする（図１３ステップＦ３）。
【００９７】
さらに、同一管理レコードリンク処理（ステップＣ７）の詳細について図１４を参照して説明する。
【００９８】
まず、キャッシュ制御部１１は、同一管理レコードサーチ処理（ステップＣ６）において、サーチした同一管理レコード１４１１からリンクされている全ての同一管理レコード１４１１のＬＵＮ，ＬＢＡについてアドレスレコード１４０１を生成して、それぞれのＬＢＡから計算されるハッシュ値を持つキャッシュ管理テーブル１４００の列をヘッドとするリストの最後尾に挿入する（図１３ステップＧ１）。
【００９９】
但し、すでにリンク上に該当するＬＵＮ，ＬＢＡを持つアドレスレコード１４０１がある場合、キャッシュ制御部１１は、アドレスレコード１４０１からリンクされたページポインタ１４０２のページについてページ開放処理を行った後に、生成したアドレスレコード１４０１を挿入する。
【０１００】
この後に、キャッシュ制御部１１は、ステップＧ１で挿入した全てのアドレスレコード１４０１と、ステップＣ４で取得したページポインタ１４０２とを相互リンクする（図１３ステップＧ２）。
【０１０１】
さらにまた、図１５と図１１と図１２とを参照して本実施の形態におけるライト処理動作について説明する。
【０１０２】
ホスト２からライトコマンドを受けると、キャッシュ制御部１１は、ライトコマンドに含まれるＬＵＮとＬＢＡとに対応するアドレスレコードサーチ処理を行う（図１５ステップＨ１）。このアドレスレコードサーチ処理は、図１０におけるアドレスレコードサーチ処理（ステップＣ１）と同じ処理である。
【０１０３】
キャッシュ制御部１１は、対応するアドレスレコード１４０１があった場合（図１５ステップＨ２）、対応アドレスレコード１４０１からリンクされたページポインタ１４０２のページを、対応ページとする（図１５ステップＨ３）。
【０１０４】
続いて、キャッシュ制御部１１は、ページポインタ１４０２からアドレスレコード１４０１へのリンク数が２以上の場合（図１５ステップＨ４）、これらのアドレスレコード１４０１のうち、ライトがあったアドレス以外のアドレスレコード１４０１を削除する（図１５ステップＨ５）。
【０１０５】
キャッシュ制御部１１は、ライトがあったアドレス以外のアドレスレコード１４０１を削除した後、及び図１５ステップＨ４においてページポインタ１４０２からアドレスレコード１４０１へのリンク数が２以上ではない場合、ライトコマンドのＬＢＡから算出されるハッシュ値を持つ同一データ列管理テーブル１４１０の列のリンクをたどり、ライトコマンドのＬＵＮ，ＬＢＡに対応する同一管理レコード１４１１を探す（図１５ステップＨ６）。
【０１０６】
キャッシュ制御部１１は、ライトコマンドのアドレスに対応する同一管理レコード１４１１があった場合、同一管理レコード１４１１及び同一管理レコード１４１１とリンクされた全ての同一管理レコード１４１１を削除する（図１５ステップＨ８）。
【０１０７】
上記のステップＨ５〜ステップＨ８の処理は、これまで同一データ列だった領域が、一つの領域のみにライトが行われて同一データ列ではなくなることを反映させる処理である。
【０１０８】
キャッシュ制御部１１は、同一管理レコード１４１１を削除した後、及び図１５ステップＨ７において同一管理レコード１４１１がなかった場合、ホスト２からライトデータを受信し、キャッシュ１２のページポインタ１４０２に対応するページに格納する（図１５ステップＨ９）。
【０１０９】
一方、キャッシュ制御部１１は、ステップＨ２で、対応するアドレスレコード１４０１がなかった場合、未使用ページポインタ取得処理を行う（図１５ステップＨ１０）。この未使用ページポインタ取得処理は、図１０の未使用ページポインタ取得処理（ステップＣ４）と同じ処理である。
【０１１０】
次に、キャッシュ制御部１１は、ライトコマンドに含まれるＬＵＮとＬＢＡとに対応するアドレスレコード１４０１を作成して、ＬＢＡから算出されるハッシュ値を持つキャッシュ管理テーブル１４００の列をヘッドとしたリンクの最後尾に挿入する（図１５ステップＨ１１）。
【０１１１】
キャッシュ制御部１１は、アドレスレコード１４０１と、未使用ページポインタ取得処理（ステップＨ１０）で取得したページポインタ１４０２との相互リンクを行い（図１５ステップＨ１２）、上記のステップＨ６以降の処理を行う。
【０１１２】
このように、本実施の形態では、同一のデータ列を持つＨＤＤ１６の記憶領域が、キャッシュ１２の同じページを使うため、キャッシュ１２のページを一つのＨＤＤ１６の記憶領域のみと対応付ける技術に比べて、キャッシュ１２の使用効率を向上させることができる。
【０１１３】
また、本実施の形態では、ＨＤＤ１６の記憶領域では同一のデータ列を複数記憶するため、ＨＤＤ１６の記憶領域で同一データ列を一つしか記憶しないデデュープリケーション技術と比べて、ＨＤＤ１６の一部に障害が発生した時のデータロスへの影響が小さいという効果がある。
【０１１４】
さらに、本実施の形態では、同一データ列を探索する処理がコマンドの処理と独立に行われ、ライトコマンドが発生する度にデータ列の比較を実行する必要がないため、コマンドの応答時間への影響が小さいという効果がある。
【０１１５】
次に、本発明の第２の実施の形態について図面を参照して説明する。本発明の第２の実施の形態は、上述した本発明の第１の実施の形態と、ライトコマンドに対する処理動作において異なり、他の処理動作及び構成は、上記の図１〜図１４に示す本発明の第１の実施の形態と同様である。
【０１１６】
図１６及び図１７は本発明の第２の実施の形態におけるライト処理の動作を示すフローチャートである。これら図１６及び図１７と図１１と図１２とを参照して本実施の形態におけるライト処理動作について説明する。尚、図１６及び図１７に示す処理動作は、ストレージ装置１内のコンピュータ［例えば、ＣＰＵ（中央処理装置）等］（図示せず）に、プログラムを実行させることで実現可能である。
【０１１７】
ホスト２からライトコマンドを受けると、キャッシュ制御部１１は、ライトコマンドに含まれるＬＵＮとＬＢＡとに対応するアドレスレコードサーチ処理を行う（図１６ステップＨ２１）。このアドレスレコードサーチ処理は、図１０におけるアドレスレコードサーチ処理（ステップＣ１）と同じ処理である。
【０１１８】
キャッシュ制御部１１は、対応するアドレスレコード１４０１があった場合（図１６ステップＨ２２）、対応するアドレスレコード１４０１からリンクされたページポインタ１４０２からの、アドレスレコード１４０１へのリンク数が２以上であるかどうかを調べる（図１６ステップＨ２４）。
【０１１９】
キャッシュ制御部１１は、アドレスレコード１４０１へのリンク数が２以上であった場合、ライトコマンドのＬＵＮ，ＬＢＡに対応したアドレスレコード１４０１とページポインタ１４０２との相互リンクを解除する（図１６ステップＨ２５）。
【０１２０】
一方、キャッシュ制御部１１は、ステップＨ２２で対応するアドレスレコード１４０１がなかった場合、対応するアドレスレコード１４０１を作成してライトコマンドのＬＢＡから算出されるハッシュ値を持つキャッシュ管理テーブル１４００の列のリンクの最後尾に接続する（図１６ステップＨ２３）。
【０１２１】
キャッシュ制御部１１は、図１６ステップＨ２５においてアドレスレコード１４０１とページポインタ１４０２との相互リンクを解除した後、及び図１６ステップＨ２４において対応するアドレスレコード１４０１へのリンク数が１であった場合、及び図１６ステップＨ２３においてアドレスレコード１４０１を作成した後、ライトコマンドのＬＢＡから算出されれるハッシュ値を持つ同一データ列管理テーブル１４１０の列のリンクをたどり、ライトのアドレスに対応する同一管理レコード１４１１を探す（図１６ステップＨ２６）。
【０１２２】
キャッシュ制御部１１は、対応する同一管理レコード１４１１があった場合（図１６ステップＨ２７）、対応する同一管理レコード１４１１からのリンク数は１であるかを調べる（図１６ステップＨ２８）。キャッシュ制御部１１は、リンク数が１だった場合、ライトコマンドのアドレスに対応する同一管理レコード１４１１のリンク先の同一管理レコードを削除する（図１６ステップＨ２９）。
【０１２３】
また、キャッシュ制御部１１は、リンク数が１ではなかった（すなわち、２以上）であった場合、ライトコマンドのアドレスに対応する同一管理レコード１４１１とリンク先の同一管理レコード１４１１との間のリンクを解除する（図１６ステップＨ３０）。
【０１２４】
キャッシュ制御部１１は、図１６ステップＨ２９において同一管理レコード１４１１のリンク先の同一管理レコードを削除した後、及び図１６ステップＨ３０において同一管理レコード１４１１とリンク先の同一管理レコード１４１１との間のリンクを解除した後、ライトコマンドに対応するアドレスの同一管理レコード１４１１を削除する（図１７ステップＨ３１）。
【０１２５】
キャッシュ制御部１１は、図１６ステップＨ２７において対応する同一管理レコード１４１１がなかった場合、及び図１７ステップＨ３１においてライトコマンドに対応するアドレスの同一管理レコード１４１１を削除した後、未使用ポインタ取得処理を行う（図１７ステップＨ３２）。この未使用ポインタ取得処理は、図１０の未使用ページポインタ取得処理（ステップＣ４）と同じ処理である。
【０１２６】
次に、キャッシュ制御部１１は、ライトコマンドのアドレスに対応するアドレスレコード１４０１と、ステップＨ３２で取得したページポインタ１４０２とを相互リンクとし（図１７ステップＨ３３）、ホスト２からデータを受信してキャッシュ１２のページポインタ１４０２に対応するページに格納する（図１７ステップＨ３４）。
【０１２７】
このように、本実施の形態では、上述した本発明の第１の実施の形態における効果に加えて、複数のアドレスに対応したキャッシュのページがある時、対応する１つのアドレスにライトがあった場合でも、ライトがあったアドレス以外のキャッシュ１２のデータもキャッシュ１２に残るため、ライトがあったアドレス以外へのアクセスがあった場合でも、新たにキャッシュページを確保したり、ＨＤＤ１６からキャッシュ１２に読込む必要がなくなるという効果がある。
【実施例１】
【０１２８】
次に、具体的な実施例を用いて本発明を実施するための最良の形態の動作について説明する。本実施例は、本発明の第１の実施の形態に対応するものである。尚、以降、ＬＢＡの値を表記する際に、値の後ろにｈを付した場合には十六進数での表記であることを意味するものとする。
【０１２９】
図１８（ａ），（ｂ）及び図１９（ａ），（ｂ）は本発明の第１の実施例におけるキャッシュ１２とＨＤＤ１６との記憶空間を概念的に表す図である。図２０（ａ）〜（ｄ）及び図２１（ａ）〜（ｃ）は本発明の第１の実施例におけるキャッシュ管理情報記憶部１４０の状態を表す図である。
【０１３０】
図２０（ｂ）〜（ｄ）のアドレスレコード１４０１には、各々のアドレスレコード１４０１に対応するＬＵＮとＬＢＡとを（ＬＵＮ，ＬＢＡ）の形式で記している。また、図２０（ｂ）〜（ｄ）及び図１７（ａ）〜（ｃ）のページポインタ１４０２には、各々のページポインタ１４０２に対応するページの番号を（ページ番号）の形式で記している。
【０１３１】
図２２（ａ）〜（ｄ）は本発明の第１の実施例における同一データ列情報記憶部１４１の状態を表す図である。図２２（ｂ）〜（ｄ）の同一管理レコード１４１１には、各々の同一管理レコード１４１１に対応するＬＵＮとＬＢＡとを（ＬＵＮ，ＬＢＡ）の形式で記している。
【０１３２】
本実施例では、キャッシュ１２が、ページ番号が０〜７である、８つのページを持つものとする。また、ＨＤＤ１６の記憶空間には、ＬＵＮ＝０とＬＵＮ＝１との２つのＬＵＮが割当てられており、ＬＵＮ＝０はＬＢＡ＝０ｈ〜３ＦＦＦｈのアドレス空間を持ち、ＬＵＮ＝１はＬＢＡ＝０ｈ〜４ＦＦＦｈのアドレス空間を持つものとする。
【０１３３】
まず、ＬＵＮ＝０のＬＢＡ＝８０ｈ〜ＢＦｈ及びＬＵＮ＝１のＬＢＡ＝８０ｈ〜ＢＦｈと、ＬＵＮ＝０のＬＢＡ＝１３４０ｈ〜１３７Ｆｈ及びＬＵＮ＝１のＬＢＡ＝２ＢＣ０ｈ〜２ＢＦＦｈとが、それぞれ同じデータ列を記憶している状態を考える。この時のキャッシュ１２の記憶空間Ｘ１とＨＤＤ１６の記憶空間Ｘ２との概念図を図１８（ａ）に示す。
【０１３４】
また、キャッシュ管理テーブル１４００にはアドレスレコード１４０１が１つもリンクされていない状態であるものとする。この時の、キャッシュ管理情報記憶部１４０の状態を図２０（ａ）及び図２１（ａ）に示す。
【０１３５】
さらに、同一データ列管理テーブル１４１０には、同一管理レコード１４１１が１つもリンクされていない状態であるものとする。この時の、同一データ列情報記憶部１４１の状態を図２２（ａ）に示す。
【０１３６】
この状態で、ホスト２からコマンドがない場合、図６及び図７の各ステップが繰り返し実行され、まず、ＬＵＮ＝０のＬＢＡ＝８０ｈ〜ＢＦｈとＬＵＮ＝１のＬＢＡ＝８０ｈ〜ＢＦｈとのデータ列が同じであることが検出され（図６ステップＡ３，Ａ４）、同一データ列情報登録（図６ステップＡ５）が実行されて、同一データ列管理テーブル１４１０は図２２（ｂ）の状態となる。
【０１３７】
次に、ＬＵＮ＝０のＬＢＡ＝１３４０ｈ〜１３７ＦｈとＬＵＮ＝１のＬＢＡ＝２ＢＣ０ｈ〜２ＢＦＦｈとのデータ列が同じであることが検出され（図６ステップＡ３，Ａ４）、同一データ列情報登録（図６ステップＡ５）が実行されて、同一データ列管理テーブル１４１０は図２２（ｃ）の状態となる。
【０１３８】
続いて、ホスト２から、ＬＵＮ＝０，ＬＢＡ＝１３４０ｈに対して３２ＫＢのリードコマンドを受けた場合を考える。この時、図１０の各ステップが実行され、キャッシュ管理情報記憶部１４０は図２０（ｂ）及び図２１（ｂ）の状態となる。また、この時のキャッシュ１２の記憶空間Ｘ１とＨＤＤ１６の記憶空間Ｘ２との対応関係の概念図を図１８（ｂ）に示す。尚、同一データ列管理テーブル１４１０は図２２（ｃ）のままである。
【０１３９】
さらに、キャッシュ１２のページ番号＝０のページには、ＬＵＮ＝０，ＬＢＡ＝１３４０ｈ〜１３７Ｆｈのデータ列が読込まれた状態となる。尚、このデータ列は、ＬＵＮ＝１，ＬＢＡ＝２ＢＣ０ｈ〜２ＢＦＦｈのデータ列と同じである。
【０１４０】
次に、ホスト２から、ＬＵＮ＝１，ＬＢＡ＝８０ｈに対して３２ＫＢのリードコマンドを受けた場合を考える。この時、図１０の各ステップが実行され、キャッシュ管理情報記憶部１４０は、図２０（ｃ）及び図２１（ｃ）の状態となる。また、この時のキャッシュ１２の記憶空間Ｘ１とＨＤＤ１６の記憶空間Ｘ２との対応関係の概念図を図１９（ａ）に示す。
【０１４１】
尚、同一データ列管理テーブル１４１０は、図２２（ｃ）のままである。さらに、キャッシュ１２のページ番号＝４のページには、ＬＵＮ＝１，ＬＢＡ＝８０ｈ〜ＢＦｈのデータ列が読込まれた状態となる。この場合、読込まれたデータ列は、ＬＵＮ＝０，ＬＢＡ＝８０ｈ〜ＢＦｈのデータ列と同じである。
【０１４２】
続いて、ホスト２から、ＬＵＮ＝１，ＬＢＡ＝２ＢＣ０ｈに対して３２ＫＢのリードコマンドを受けた場合を考える。この時、図１０の各ステップが実行されるが、キャッシュ管理情報記憶部１４０は、図２０（ｃ）及び図２１（ｃ）の状態のままである。また、この時のキャッシュ１２の記憶空間Ｘ１とＨＤＤ１６の記憶空間Ｘ２との対応関係の概念図は、図１９（ａ）のままである。すなわち、キャッシュ１２では、新たなページが使用されない。尚、同一データ列管理テーブル１４１０は、図２２（ｃ）のままである。
【０１４３】
さらに、ホスト２から、ＬＵＮ＝０，ＬＢＡ＝８０ｈに対して３２ＫＢのリードコマンドを受けた場合を考える。この時、図１０の各ステップが実行されるが、キャッシュ管理情報記憶部１４０は、図２０（ｃ）及び図２１（ｃ）の状態のままである。
【０１４４】
また、この時のキャッシュ１２の記憶空間Ｘ１とＨＤＤ１６の記憶空間Ｘ２との対応関係の概念図は、図１９（ａ）のままである。すなわち、キャッシュ１２では、新たなページが使用されない。尚、同一データ列管理テーブル１４１０は、図２２（ｃ）のままである。
【０１４５】
次に、ホスト２から、ＬＵＮ＝１，ＬＢＡ＝８０ｈに対して３２ＫＢのライトコマンドを受けた場合を考える。この時、図１５の各ステップが実行され、キャッシュ管理情報記憶部１４０は、図２０（ｄ）及び図２１（ｃ）の状態となる。また、この時のキャッシュ１２の記憶空間Ｘ１とＨＤＤ１６の記憶空間Ｘ２との対応関係の概念図を図１９（ｂ）に示す。
【０１４６】
また、同一データ列管理テーブル１４１０は、図２２（ｄ）の状態となる。尚、この時点では、ＬＵＮ＝１，ＬＢＡ＝８０ｈに対してライトされたデータはキャッシュ１２のページ番号＝４のページに格納されているだけであり、実際にＨＤＤ１６のＬＵＮ＝１，ＬＢＡ＝８０ｈにデータが格納されるのは、以降でキャッシュ１２のページ番号＝４のページに対してページ開放処理が行われる時である。
【０１４７】
本実施例では、ＬＵＮ＝０のＬＢＡ＝８０ｈ〜ＢＦｈ、ＬＵＮ＝０のＬＢＡ＝１３４０ｈ〜１３７Ｆｈ、ＬＵＮ＝１のＬＢＡ＝８０ｈ〜ＢＦｈ、ＬＵＮ＝１のＬＢＡ＝２ＢＣ０ｈ〜２ＢＦＦｈの４つの領域に対してアクセスが行われたにもかかわらず、使用されたキャッシュ１２のページ数は２のみである。キャッシュ１２の１ページをＨＤＤ１６の１つの領域のみに対応付ける技術では、ページ数４が使用されるため、本発明によってキャッシュ利用効率が向上していることがわかる。
【実施例２】
【０１４８】
次に、本発明の第２の実施例について説明する。本実施例は、本発明の第２の実施の形態に対応するものである。本発明の第１の実施の形態と本発明の第２の実施の形態との違いを説明するため、本実施例では上記の本発明の第１の実施例と同じ構成で、同じコマンド列をホスト２から受ける場合について考える。
【０１４９】
すなわち、まず、
ＬＵＮ＝０，ＬＢＡ＝１３４０ｈに対して３２ＫＢのリードコマンド
ＬＵＮ＝１，ＬＢＡ＝８０ｈに対して３２ＫＢのリードコマンド
ＬＵＮ＝１，ＬＢＡ＝２ＢＣ０ｈに対して３２ＫＢのリードコマンド
ＬＵＮ＝０，ＬＢＡ＝８０ｈに対して３２ＫＢのリードコマンド
というコマンドを順に受けるものとする。
【０１５０】
ここまでの動作は、上記の本発明の第１の実施例と同じであり、この時、キャッシュ管理情報記憶部１４０は、図２０（ｃ）及び図２１（ｃ）の状態となる。また、この時のキャッシュ１２の記憶空間Ｘ１とＨＤＤの記憶空間Ｘ２との対応関係の概念図は、図１９（ａ）に示す状態となる。さらに、同一データ列管理テーブル１４１０は、図２２（ｃ）の状態である。
【０１５１】
次に、ホスト２から、ＬＵＮ＝１，ＬＢＡ＝８０ｈに対して３２ＫＢのライトコマンドを受けた場合を考える。この時、図１６及び図１７の各ステップが実行され、キャッシュ管理情報記憶部１４０は、図２４及び図２５の状態となる。また、この時のキャッシュ１２の記憶空間Ｘ１とＨＤＤ１６の記憶空間Ｘ２との対応関係の概念図を図２３に示す。
【０１５２】
さらに、同一データ列管理テーブル１４１０は、図２２（ｄ）の状態となる。尚、この時点では、ＬＵＮ＝１，ＬＢＡ＝８０ｈに対してライトされたデータがキャッシュ１２のページ番号＝２のページに格納されているだけであり、実際にＨＤＤ１６のＬＵＮ＝１，ＬＢＡ＝８０ｈにデータが格納されるのは、以降でキャッシュ１２のページ番号＝２のページに対してページ開放処理が行われる時である。
【０１５３】
本発明の第１の実施例における図１９（ｂ）と、本発明の第２の実施例における図２３とを比較すると、本発明の第１の実施例では、ＬＵＮ＝０，ＬＢＡ＝８０ｈのデータがキャッシュ１２上からなくなったのに対し、本発明の第２の実施例では、ＬＵＮ＝０，ＬＢＡ＝８０ｈのデータがキャッシュ１２上のページに残っている。このため、以降にＬＵＮ＝０，ＬＢＡ＝８０ｈへのアクセスがあった場合でも、改めてキャッシュ１２のページを確保したり、ＨＤＤ１６からデータをリードする必要がない。
【０１５４】
上記のように、本発明は、同一データ列抽出部１５と、階層記憶制御部（キャッシュ制御部１１）と、同一データ列記憶部１４１と、階層記憶管理情報記憶部（キャッシュ管理情報記憶部１４０）とを備えている。同一データ列抽出部１５は、下位記憶階層から同一データ列を持つ領域を抽出して、領域の情報を同一データ列記憶部１４１に蓄積する。階層記憶制御部（キャッシュ制御部１１）は、同一データ列記憶部１４１の情報に基づいて、下位記憶階層の複数の記憶領域を上位記憶階層の一つの領域に対応付けて、階層記憶管理情報記憶部（キャッシュ管理情報記憶部１４０）に対応情報を記憶する。
【０１５５】
本発明は、上記のような構成を採用し、上位記憶階層の一つの領域に対して、同一データを有する下位記憶階層の複数の領域を対応付けることによって、階層記憶において、上位記憶階層に同一データ列が複数存在する状態を減らして上位記憶階層利用効率を上げることができる。これは、同一データ列を持つ下位記憶階層の領域に対して、一つの上位記憶階層の領域を対応付けるためである。
【産業上の利用可能性】
【０１５６】
本発明によれば、キャッシュを搭載したストレージ装置といった用途に適用できる。また、階層記憶を利用する計算機システムや、ネットワーク上のキャッシュサーバといった用途にも適用可能である。
【図面の簡単な説明】
【０１５７】
【図１】本発明の第１及び第２の実施の形態による階層記憶制御システムの構成例を示すブロック図である。
【図２】本発明の第１及び第２の実施の形態におけるキャッシュ管理情報記憶部のデータ構造の一部を示す図である。
【図３】本発明の第１及び第２の実施の形態におけるキャッシュ管理情報記憶部のデータ構造の一部を示す図である。
【図４】本発明の第１及び第２の実施の形態における同一データ列情報記憶部のデータ構造を示す図である。
【図５】本発明の第１及び第２の実施の形態における記憶空間を概念的に示す図である。
【図６】本発明の第１及び第２の実施の形態における同一データ列抽出処理の動作を示すフローチャートである。
【図７】本発明の第１及び第２の実施の形態における同一データ列抽出処理の動作を示すフローチャートである。
【図８】本発明の第１及び第２の実施の形態における同一データ列情報登録処理の動作を示すフローチャートである。
【図９】本発明の第１及び第２の実施の形態における同一データ列情報登録処理の動作を示すフローチャートである。
【図１０】本発明の第１及び第２の実施の形態におけるリード処理の動作を示すフローチャートである。
【図１１】本発明の第１及び第２の実施の形態におけるアドレスレコードサーチ処理の動作を示すフローチャートである。
【図１２】本発明の第１及び第２の実施の形態における未使用ページポインタ取得処理の動作を示すフローチャートである。
【図１３】本発明の第１及び第２の実施の形態における同一管理レコードサーチの動作を示すフローチャートである。
【図１４】本発明の第１及び第２の実施の形態における同一管理レコードリンク処理の動作を示すフローチャートである。
【図１５】本発明の第１の実施の形態におけるライト処理の動作を示すフローチャートである。
【図１６】本発明の第２の実施の形態におけるライト処理の動作を示すフローチャートである。
【図１７】本発明の第２の実施の形態におけるライト処理の動作を示すフローチャートである。
【図１８】（ａ），（ｂ）は本発明の第１及び第２の実施例における記憶空間を概念的に示す図である。
【図１９】（ａ），（ｂ）は本発明の第１及び第２の実施例における記憶空間を概念的に示す図である。
【図２０】（ａ）〜（ｄ）は本発明の第１及び第２の実施例におけるキャッシュ管理情報記憶部のデータ構造の一部を示す図である。
【図２１】（ａ）〜（ｃ）は本発明の第１及び第２の実施例におけるキャッシュ管理情報記憶部のデータ構造の一部を示す図である。
【図２２】（ａ）〜（ｄ）は本発明の第１及び第２の実施例における同一データ列情報記憶部のデータ構造を示す図である。
【図２３】本発明の第２の実施例における記憶空間を概念的に示す図である。
【図２４】本発明の第２の実施例におけるキャッシュ管理情報記憶部のデータ構造の一部を示す図である。
【図２５】本発明の第２の実施例におけるキャッシュ管理情報記憶部のデータ構造の一部を示す図である。
【符号の説明】
【０１５８】
１  ストレージ装置
２−１〜２−３  ホスト
１０  ホストインタフェース部
１１  キャッシュ制御部
１２  キャッシュ
１３  ディスク制御部
１４  記憶部
１５  同一データ列抽出部
１６−１〜１６−４  ＨＤＤ
１４０  キャッシュ管理情報記憶部
１４１  同一データ列情報記憶部
１４０１，
１４０１ａ〜１４０１ｄ  アドレスレコード
１４０２，
１４０２ａ〜１４０２ｈ  ページポインタ
１４０３  未使用ページポインタヘッド
１４１０  同一データ列管理テーブル
１４１１，
１４１１ａ〜１４１１ｄ  同一管理レコード
Ｘ１  キャッシュ記憶空間
Ｘ２  ＨＤＤ記憶空間
【図１】
0005141234.tif 000002
【図２】
0005141234.tif 000003
【図３】
0005141234.tif 000004
【図４】
0005141234.tif 000005
【図５】
0005141234.tif 000006
【図６】
0005141234.tif 000007
【図７】
0005141234.tif 000008
【図８】
0005141234.tif 000009
【図９】
0005141234.tif 000010
【図１０】
0005141234.tif 000011
【図１１】
0005141234.tif 000012
【図１２】
0005141234.tif 000013
【図１３】
0005141234.tif 000014
【図１４】
0005141234.tif 000015
【図１５】
0005141234.tif 000016
【図１６】
0005141234.tif 000017
【図１７】
0005141234.tif 000018
【図１８】
0005141234.tif 000019
【図１９】
0005141234.tif 000020
【図２０】
0005141234.tif 000021
【図２１】
0005141234.tif 000022
【図２２】
0005141234.tif 000023
【図２３】
0005141234.tif 000024
【図２４】
0005141234.tif 000025
【図２５】
0005141234.tif 000026