(57)【特許請求の範囲】
【請求項１】
データ及び当該データに基づいて生成される誤り訂正コード（ＥＣＣ）がセクタを単位に格納されるストレージ装置と、
前記ストレージ装置を利用するホスト計算機とを具備し、
前記ホスト計算機は、
１つ以上のセクタから構成されるチャンク毎に、各チャンクを構成する複数のセクタから取得される複数のＥＣＣを結合し、この結合されたＥＣＣのハッシュ値を求めてＥＣＣ値を取得するＥＣＣ取得部と、
前記ＥＣＣ値を前記チャンクを単位に比較することにより、比較されたＥＣＣ値に対応するチャンクのデータの重複の可能性を判定し、当該判定の結果に基づいて前記対応するチャンクのデータを比較することにより、当該対応するチャンクのデータの重複を検出する重複検出部とを具備する
ストレージシステム。
【請求項２】
データ及び当該データに基づいて生成される誤り訂正コード（ＥＣＣ）がセクタを単位に格納されるストレージ装置を利用するホスト計算機におけるデータ重複検出方法であって、
１つ以上のセクタから構成されるチャンク毎に、各チャンクを構成する複数のセクタから取得される複数のＥＣＣを結合し、この結合されたＥＣＣのハッシュ値を求めてＥＣＣ値を取得し、
前記ＥＣＣ値を前記チャンクを単位に比較することにより、比較されたＥＣＣ値に対応するチャンクのデータの重複の可能性を判定し、
前記判定の結果に基づいて前記対応するチャンクのデータを比較することにより、当該対応するチャンクのデータの重複を検出する
データ重複検出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、ストレージシステム及びデータ重複検出方法に関する。
【背景技術】
【０００２】
近年、ストレージ装置に格納されるべきデータの量は増大の一途をたどっている。このため、ストレージ装置の限られた記憶容量を有効に利用する技術が要求されている。このような技術の１つとして、重複排除技術が注目されている。重複排除技術によれば、同一内容のデータが重複してストレージ装置に格納されるのを防止する。このデータの重複は、例えば、チャンクと呼ばれるデータの塊を単位に判定される。
【０００３】
重複排除技術は、一般に、重複排除処理を実行する時期の違いにより２つに大別される。第１の重複排除技術では、ストレージ装置へのライトアクセスに応じて、重複排除処理が実行される。これに対して第２の重複排除技術では、ストレージ装置へのライトアクセスとは非同期に、重複排除処理が実行される。
【０００４】
第１の重複排除技術では、例えば、ストレージコントローラ（またはストレージ装置を利用するホスト計算機）は、ストレージ装置へのライトアクセスに応じて、ライトデータと同一内容のデータが、ストレージ装置に格納されているかを、チャンクを単位に判定する。この判定のために、ストレージコントローラは、ＳＨＡ１のようなハッシュ関数を用いて、チャンク毎に、対応するデータのハッシュ値を計算する。計算されたハッシュ値は、対応するチャンクに対応付けて、ハッシュテーブルに格納される。
【０００５】
ストレージコントローラは、例えば第１のチャンクのデータの第１のハッシュ値を計算した場合、第１のハッシュ値と同一のハッシュ値がハッシュテーブルに格納されているかに基づいて、第１のチャンクと重複するデータが既にストレージ装置に格納されているかを判定する。コントローラは、第１のチャンクと重複するデータが格納されていない場合だけ、当該第１のチャンクのデータをストレージ装置に書き込む。これにより、ストレージ装置から重複するデータが排除される。
【０００６】
一方、第２の重複排除技術では、ストレージコントローラ（またはホスト計算機）は、ストレージ装置に格納されている全データをチャンク単位にスキャン（リードして）、比較によりデータが重複するチャンクを検出する。ここで、第１及び第２のチャンクが重複チャンクとして検出されたものとする。この場合、ストレージコントローラは、例えばストレージ装置における第２のチャンクのデータを削除（または無効化）し、且つ第２のチャンクへのアクセスが第１のチャンクへのアクセスに切り替えられるように、マッピングを変更する。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特許第５４４４５０６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかし、第１の重複排除技術では、ストレージ装置にデータをライトする場合に、チャンク毎に対応するデータ（ライトデータ）のハッシュ値を計算する必要がある。また、第２の重複排除技術では、ストレージ装置に格納されている全データをチャンク単位にスキャンして比較する処理が必要となる。また、第２の重複排除技術における重複チャンクの検出（つまり、チャンク間のデータの重複の検出）に、ハッシュテーブルに基づくハッシュ値の比較を用いることも可能であるが、第１の重複排除技術と同様にチャンク毎にハッシュ値を計算する必要がある。
【０００９】
本発明が解決しようとする課題は、データの重複の検出に要するコストを低減できるストレージシステム及びデータ重複検出方法を提供することにある。
【課題を解決するための手段】
【００１０】
実施形態によれば、ストレージシステムは、データ及び当該データに基づいて生成される誤り訂正コード（ＥＣＣ）がセクタを単位に格納されるストレージ装置と、前記ストレージ装置を利用するホスト計算機とを具備する。前記ホスト計算機は、ＥＣＣ取得部と重複検出部とを具備する。前記ＥＣＣ取得部は、１つ以上のセクタから構成されるチャンク毎に、各チャンクを構成する複数のセクタから取得される複数のＥＣＣを結合し、この結合されたＥＣＣのハッシュ値を求めてＥＣＣ値を取得する。前記重複検出部は、前記ＥＣＣ値を前記チャンクを単位に比較することにより、比較されたＥＣＣ値に対応するチャンクのデータの重複の可能性を判定する。前記重複検出部は更に、前記判定の結果に基づいて前記対応するチャンクのデータを比較することにより、当該対応するチャンクのデータの重複を検出する。
【図面の簡単な説明】
【００１１】
【図１】実施形態に係るストレージシステムの典型的なハードウェア構成を示すブロック図。
【図２】図１に示されるホストの典型的な機能構成を主として示すブロック図。
【図３】同実施形態におけるチャンクのデータ構造の例を示す図。
【図４】図２に示される重複管理テーブルのデータ構造の例を示す図。
【図５】図２に示されるアドレステーブルのデータ構造例を示す図。
【図６】同実施形態におけるＥＣＣ設定処理の典型的な手順を示すフローチャート。
【図７】図６に示されるＥＣＣ設定処理において実行されるＥＣＣ取得処理の典型的な手順を示すフローチャート。
【図８】同実施形態の変形例におけるＥＣＣ取得処理の典型的な手順を示すフローチャート。
【図９】同実施形態における重複チャンク探索処理の典型的な手順を示すフローチャート。
【図１０】図９に示される重複チャンク探索処理において実行される重複チャンクマージ処理の典型的な手順を示すフローチャート。
【図１１】重複チャンク探索処理に起因する重複管理テーブルの状態の変化の例を示す図。
【図１２】重複チャンク探索処理に起因するアドレステーブルの状態の変化の例を示す図。
【図１３】同実施形態におけるライト処理の典型的な手順を示すフローチャート。
【発明を実施するための形態】
【００１２】
以下、実施の形態につき図面を参照して説明する。  
図１は一つの実施形態に係るストレージシステムの典型的なハードウェア構成を示すブロック図である。ストレージシステムは、ストレージ装置１０と、ホスト計算機（ホスト）２０とを含む。ストレージ装置１０（より、詳細には、ストレージ装置１０のストレージコントローラ１２）は、ファイバチャネル（ＦＣ）、スモールコンピュータシステムインタフェース（ＳＣＳＩ）、シリアルアタッチドＳＣＳＩ（ＳＡＳ）、インターネットＳＣＳＩ（ｉＳＣＳＩ）、イーサネット（登録商標）、或いはシリアルＡＴアタッチメント（ＳＡＴＡ）のような、ホストインタフェースバス３０を介してホスト２０と接続されている。なお、ストレージ装置１０が、ストレージエリアネットワーク（ＳＡＮ）、インターネット或いはイントラネットのようなネットワークを介してホスト２０と接続されていても良い。
【００１３】
ストレージ装置１０は、ストレージ１１と、ストレージコントローラ１２とを含む。ストレージ１１は、ＦＣ、ＳＣＳＩ、ＳＡＳ、ｉＳＣＳＩ、イーサネット、或いはＳＡＴＡのようなストレージインタフェースバス１３を介してストレージコントローラ１２と接続されている。
【００１４】
ストレージ１１は、例えばハードディスクドライブ（ＨＤＤ）である。しかし、ストレージ１１が、複数のＨＤＤから構成されるＲＡＩＤ（Redundant Arrays of Inexpensive Disks、またはRedundant Arrays of Independent Disks）のようなディスクアレイであっても構わない。またストレージ１１が、ＨＤＤとの互換性を有するソリッドステートドライブ（ＳＳＤ）、或いはフラッシュアレイのようなフラッシュストレージであっても構わない。ＳＳＤ及びフラッシュストレージは、一般に、複数のフラッシュメモリを用いて構成される、
ストレージコントローラ１２は、ホスト２０からのアクセス要求（より詳細には、ライトコマンドまたはリードコマンド）に応じて、例えばセクタと呼ばれるデータの塊を単位にストレージ１１にアクセスする。ストレージコントローラ１２はまた、ストレージ１１にデータをライトする場合、セクタ単位にエラー訂正コード（ＥＣＣ）を生成する。ＥＣＣは、当該ＥＣＣの生成に用いられたデータのエラーの検出及び訂正に用いられる。そしてストレージコントローラ１２は、セクタ単位に、データとＥＣＣを含む付加情報との組をストレージ１１にライトする。付加情報が、ＥＣＣに加えて、メタデータ、或いはデータ保護情報を含んでいても構わない。
【００１５】
ホスト２０は、ストレージインタフェース（ＳＩＦ）コントローラ２１と、メモリ２２と、ＨＤＤ２３と、ＣＰＵ２４とを含む。ＳＩＦコントローラ２１は、ＣＰＵ２４とストレージ装置１０のストレージコントローラ１２との間のデータ転送を制御する。ＳＩＦコントローラ２１は、ＣＰＵ２４からのアクセス要求をストレージコントローラ１２に送信し、当該アクセス要求に対するストレージコントローラ１２からの応答を受信する。ＳＩＦコントローラ２１は、ストレージコントローラ１２からの応答を受信すると、当該応答を、ＣＰＵ２４に伝達する。
【００１６】
メモリ２２は、ダイナミックＲＡＭ（ＤＲＡＭ）のような書き換えが可能な揮発性メモリである。メモリ２２の一部の記憶領域は、ＨＤＤ２３からロードされるオペレーティングシステム（ＯＳ）及び種々のプログラムを格納するのに用いられる。メモリ２２の他の一部の記憶領域は、ＣＰＵ２４のためのワーク領域として用いられる。
【００１７】
ＨＤＤ２３には、ＯＳ及び複数のプログラムが格納されている。複数のプログラムは、アプリケーションプログラム（以下、アプリケーションと称する）及びユーティリティプログラムを含む。ＣＰＵ２４は、ホスト機器２０が起動されたときに、ＲＯＭまたはフラッシュＲＯＭ（ＦＲＯＭ）のような不揮発性メモリに格納されているＩＰＬを実行することにより、ＨＤＤ２３に格納されているＯＳをメモリ２２にロードする。またＣＰＵ２４は、ＨＤＤ２３に格納されているプログラムを適宜メモリ２２にロードする。
【００１８】
ＣＰＵ２４は、メモリ２２にロードされたプログラムに従い、アクセス要求部２０３、ＥＣＣ取得部２０４、重複排除コントローラ２０５、及びアクセス部２０６（図２）として機能する。本実施形態では、ＣＰＵ２４は、アプリケーションに従い、アクセス要求部２０３として機能し、特定のユーティリティプログラムに従い、ＥＣＣ取得部２０４及び重複排除コントローラ２０５として機能し、ＯＳに従い、アクセス部２０６として機能する。
【００１９】
図２は、図１に示されるホスト２０の典型的な機能構成を主として示すブロック図である。ホスト２０のメモリ２２の一部の記憶領域は、重複管理テーブル２０１及びアドレステーブル２０２を格納するのに用いられる。ホスト２０は、重複管理テーブル２０１及びアドレステーブル２０２に加えて、前述のアクセス要求部２０３、ＥＣＣ取得部２０４、重複排除コントローラ２０５、及びアクセス部２０６を含む。
【００２０】
アクセス要求部２０３は、例えばアプリケーションからの要求に応じて、アクセス部２０６に対してストレージ装置１０へのアクセスを要求する。本実施形態では、アクセス要求部２０３からのアクセス要求に応じて、ストレージ装置１０へのアクセスが、ブロックと呼ばれる固定長または可変長のデータの塊を単位に実行されるものとする。ブロックのデータは、例えば、チャンクと呼ばれるデータの塊に分割される。チャンクのデータは、ストレージ装置１０においては、例えば、複数のセクタに分散して格納される。
【００２１】
図３は、本実施形態におけるチャンクのデータ構造の例を示す。図３の例では、チャンク３１はｎ個のセクタ３１０＿１乃至３１０＿ｎに分割される。即ちチャンク３１はｎ個のセクタ３１０＿１乃至３１０＿ｎから構成される。本実施形態では、説明の簡略化のために、チャンク３１のデータのサイズ（チャンクサイズ）は４ＫＢ（キロバイト）の固定長であるものとするが、可変長であっても構わない。
【００２２】
チャンク３１のデータは、セクタ３１０＿１乃至３１０＿ｎに均等に分散されて格納される。本実施形態において、セクタ３１０＿１乃至３１０＿ｎのサイズ、つまりセクタ３１０＿１乃至３１０＿ｎのデータ３１１＿１乃至３１１＿ｎのサイズ（セクタサイズ）は、５１２Ｂの固定長である。したがって、チャンク３１のチャンクサイズが本実施形態のように４ＫＢである場合、ｎは８である。これに対してチャンクサイズが可変長である場合、ｎは必ずしも８に一致せず、例えば１の場合もあり得る。
【００２３】
セクタ３１０＿１乃至３１０＿ｎ（より詳細には、セクタ３１０＿１乃至３１０＿ｎのデータ３１１＿１乃至３１１＿ｎ）には、ＥＣＣ３１２＿１乃至３１２＿ｎを含む付加情報が付加されている。ＥＣＣ３１２＿１乃至３１２＿ｎは、データ３１１＿１乃至３１１＿ｎに基づいてストレージコントローラ１２によって生成される。図３では、ＥＣＣ３１２＿１乃至３１２＿ｎ以外の付加情報は省略されている。
【００２４】
データ３１１＿１乃至３１１＿ｎのサイズ（つまり、セクタサイズ）が５１２Ｂの場合、ＥＣＣ３１２＿１乃至３１２＿ｎのサイズ（ＥＣＣサイズ）は一般に数十ビット程度である。しかし、ＥＣＣサイズが、必ずしも数十ビット程度でなくても構わない。
【００２５】
図２においてＥＣＣ取得部２０４は、ストレージ装置１０に格納されたチャンクを単位に、ＥＣＣの群を取得する。ＥＣＣ取得部２０４は、取得されたＥＣＣの群に基づいて、それぞれのＥＣＣの値を重複管理テーブル２０１に格納する。
【００２６】
図４は、図２に示される重複管理テーブル２０１のデータ構造の例を示す。重複管理テーブル２０１の各エントリは、重複管理レコードを格納するのに用いられる。重複管理レコードは、物理アドレス、ＥＣＣ値及び参照カウントを含む。重複管理テーブル２０１の主キーは物理アドレスである。
【００２７】
重複管理レコード中の物理アドレスは、当該重複管理レコード中のＥＣＣ値に対応するＥＣＣ群を含むセクタ群から構成されるチャンクが格納されている、ストレージ装置１０（ストレージ１１）の記憶領域（物理記憶領域）を示す。重複管理レコード中の参照カウントは、当該重複管理レコード中の物理アドレスが、割り当て（対応付け）られている論理アドレスの数を示す。つまり、重複管理レコード中の参照カウントは、当該重複管理レコード中の物理アドレスを論理的に参照する論理アドレスの数を示す。論理アドレスと物理アドレスとの対応は、アドレステーブル２０２によって示される。また、重複管理レコード中の参照カウントは、当該重複管理レコード中の物理アドレスで示されるストレージ装置１０の記憶領域に格納されたチャンクのデータと同一内容のデータを含むチャンクの数（つまり、重複数または重複カウント）をも示す。
【００２８】
図４に示される重複管理テーブル２０１において、例えば、物理アドレスＡＤＲ２を含む重複管理レコードのＥＣＣ値及び参照カウントは、それぞれＥＣＣ２及び３である。この重複管理レコード中の参照カウント＝３は、物理アドレスＡＤＲ２（で指定される記憶領域）に格納されたチャンクのデータと同一内容のデータを含むチャンクが合計３つ存在することを示す。
【００２９】
図５は、図２に示されるアドレステーブル２０２のデータ構造例を示す。アドレステーブル２０２の各エントリは、アドレスレコードを格納するのに用いられる。アドレスレコードは、論理アドレス、及び当該論理アドレスに割り当て（対応付け）られる物理アドレスを含む。本実施形態において、論理アドレスは、ストレージ装置１０の記憶領域（物理記憶領域）が割り当てられる論理ボリューム（論理ディスク）内の記憶領域（論理記憶領域）のアドレス、例えば論理ブロックアドレス（ＬＢＡ）を示す。
【００３０】
図５に示されるアドレステーブル２０２は、論理アドレスＬＢＡ１乃至ＬＢＡ６を含むアドレスレコードの群を有する。論理アドレスＬＢＡ１乃至ＬＢＡ６で指定される論理ボリューム内の記憶領域には、チャンクＣＨＫ１乃至ＣＨＫ６が論理的に格納されているものとする。つまりＬＢＡ１乃至ＬＢＡ６は、チャンクＣＨＫ１乃至ＣＨＫ６の論理アドレスである。
【００３１】
図５の例では、論理アドレスＬＢＡ１，ＬＢＡ４及びＬＢＡ５には、１つの物理アドレスＡＤＲ２が共通に割り当てられている。このことは、チャンクＣＨＫ１，ＣＨＫ４及びＣＨＫ５のデータは同一であり、ストレージ装置１０内では、この同一のデータが、重複排除により、物理アドレスＡＤＲ２で指定されるストレージ装置１０内の記憶領域にまとめて格納されていることを示す。ＡＤＲ２は、チャンクＣＨＫ１，ＣＨＫ４及びＣＨＫ５の物理アドレスである。
【００３２】
図２において、重複排除コントローラ２０５は、重複管理テーブル２０１を参照することにより同一のＥＣＣ値を含む重複管理レコードを探索するための重複チャンク探索処理を実行する。重複排除コントローラ２０５は、同一のＥＣＣ値を含む複数の重複管理レコードを探索できた場合、同一のＥＣＣ値に対応するＥＣＣ群を含む複数のチャンクを探索できたと判定する。
【００３３】
重複排除コントローラ２０５は、探索された複数のチャンクのデータを比較することにより、当該探索された複数のチャンクのデータが同一であるかを判定する。この判定を、重複チャンク判定（または重複判定）と呼ぶ。重複排除コントローラ２０５は、探索された複数のチャンクのデータが同一である場合、当該探索された複数のチャンクのデータがストレージ装置１０において重複して存在すると判定する。この場合、重複排除コントローラ２０５は、この重複を排除するために、探索された複数のチャンクをストレージ装置１０において一つにまとめるための重複チャンクマージ処理を実行する。
【００３４】
重複チャンクマージ処理において重複排除コントローラ２０５は、例えば、第１及び第２のチャンクのデータが同一であるならば、第２のチャンクに対応する重複管理レコード中の参照カウント（第２の参照カウント）を、第１のチャンクに対応する重複管理レコード中の参照カウント（第１の参照カウント）に引き継ぐ。つまり、重複排除コントローラ２０５は、第１の参照カウントを、第２の参照カウントだけインクリメントし、且つ第２の参照カウントを０に設定する。また、重複排除コントローラ２０５は、第１のチャンクの第１の物理アドレスが、第１のチャンクの第１の論理アドレスだけでなく、第２のチャンクの第２の論理アドレスにも割り当てられるように、アドレステーブル２０２（より詳細には、第２の論理アドレスを含むアドレスレコード中の物理アドレス）を更新する、
アクセス部２０６は、アクセス要求部２０３からのアクセス要求に応じて、例えば要求されたファイルに、ブロックを単位にアクセスする。このブロック単位のアクセスは、各ブロックを構成する複数のチャンクへのアクセスを含む。アクセス部２０６は、例えば、チャンクＣＨＫｉにアクセスする場合、チャンクＣＨＫｉの論理アドレスＬＢＡｉに基づいてアドレステーブル２０２を参照する。そしてアクセス部２０６は、論理アドレスＬＢＡｉに対応付けられた物理アドレスＡＤＲｊ（つまりチャンクＣＨＫｉの物理アドレスＡＤＲｊ）を、アクセスされるべき物理記憶領域を示す物理アドレスとして取得して、当該取得された物理アドレスＡＤＲｊに基づいてストレージ装置１０にアクセスする。
【００３５】
次に、本実施形態においてＥＣＣ取得部２０４によってチャンク単位に実行されるＥＣＣ設定処理について、図６を参照して説明する。図６は、ＥＣＣ設定処理の典型的な手順を示すフローチャートである。本実施形態においてＥＣＣ設定処理は、スケジューリングされた時刻が到来した場合（例えば定期的）に、或いはユーザ指定のタイミングで実行される。
【００３６】
ＥＣＣ取得部２０４は、チャンク単位のＥＣＣ設定処理のために、アドレステーブル２０２を先頭エントリから順に参照する。この例では、ＥＣＣ設定処理の先頭で、ＥＣＣ取得部２０４が、アドレステーブル２０２内のｉ番目のエントリを参照したものとする（ステップＳ１０１）。このｉ番目のエントリには、論理アドレスＬＢＡｉと物理アドレスＡＤＲｊとを含むアドレスレコードが格納されているものとする。この場合、ステップＳ１０１においてＥＣＣ取得部２０４は、参照されたｉ番目のエントリから論理アドレスＬＢＡｉに対応付けられた物理アドレスＡＤＲｊを取得する。論理アドレスＬＢＡｉで指定される論理ボリューム内の記憶領域には、チャンクＣＨＫｉのデータが論理（仮想）的に格納されており、物理アドレスＡＤＲｊで指定されるストレージ装置１０（ストレージ１１）内の記憶領域には、チャンクＣＨＫｉのデータが物理的（実際）に格納されているものとする。
【００３７】
次にＥＣＣ取得部２０４は、取得された物理アドレスＡＤＲｊを含む重複管理レコード（ターゲットの重複管理レコード）を、重複管理テーブル２０１から探索する（ステップＳ１０２）。そしてＥＣＣ取得部２０４は、ターゲットの重複管理レコードを探索できたかを判定する（ステップＳ１０３）。
【００３８】
もし、ターゲットの重複管理レコードを探索できなかったならば（ステップＳ１０３のＮｏ）、ＥＣＣ取得部２０４は、チャンクＣＨＫｉに関するＥＣＣ設定処理を終了する。この場合、ＥＣＣ取得部２０４は、次のチャンクに関するＥＣＣ設定処理を開始する。
【００３９】
これに対し、ターゲットの重複管理レコードを探索できたならば（ステップＳ１０３のＹｅｓ）、ＥＣＣ取得部２０４は、探索された重複管理レコード中のＥＣＣ値を参照する（ステップＳ１０４）。そしてＥＣＣ取得部２０４は、参照されたＥＣＣ値が無効であるかを判定する（ステップＳ１０５）。本実施形態では、この判定は、参照されたＥＣＣ値がクリアされているかに基づいて実行される。
【００４０】
もし、参照されたＥＣＣ値が無効でないならば（ステップＳ１０５のＮｏ）、つまり、参照されたＥＣＣ値が有効であるならば、ＥＣＣ取得部２０４は、チャンクＣＨＫｉに関するＥＣＣ値は既に取得されて設定されているとして、ＥＣＣ設定処理を終了する。
【００４１】
これに対して、参照されたＥＣＣ値が無効であるならば（ステップＳ１０５のＹｅｓ）、ＥＣＣ取得部２０４は、チャンクＣＨＫｉに関するＥＣＣ値を取得するためのＥＣＣ取得処理（ステップＳ１０６）を実行する。ＥＣＣ取得部２０４は、このＥＣＣ取得処理（ステップＳ１０６）において、後述のように、チャンクＣＨＫｉを構成する全セクタ中のＥＣＣ（例えば、ｎ個のＥＣＣ）を取得する。
【００４２】
次にＥＣＣ取得部２０４は、取得されたｎ個のＥＣＣを例えば結合し（ステップＳ１０７）、結合されたＥＣＣ（つまり、ＥＣＣ列）をＥＣＣｊとして設定する（ステップＳ１０８）。そしてＥＣＣ取得部２０４は、探索された重複管理レコード中のＥＣＣ値（無効なＥＣＣ値）を、ＥＣＣｊ（有効なＥＣＣ値）に更新する（ステップＳ１０９）。するとＥＣＣ取得部２０４は、チャンクＣＨＫｉに関するＥＣＣ設定処理を終了する。
【００４３】
次に、ＥＣＣ取得処理（ステップＳ１０６）について説明する。ＥＣＣ取得処理は、チャンクＣＨＫｉを構成する全セクタ中のＥＣＣを取得するための処理手順を含む。あるセクタ中のＥＣＣを取得するには、以下の２つの方法のいずれかが適用可能である。１つは、セクタ中のデータと付加情報をまとめてリードし、しかる後に付加情報中のＥＣＣのみを取り出す方法（第１の方法）である。もう１つは、ストレージ装置１０のストレージコントローラ１２が有する、セクタ中のＥＣＣのみをリードする機能を利用する方法（第２の方法）である。このＥＣＣのみのリードをストレージコントローラ１２に要求するためのコマンドは、ＥＣＣリードコマンドと呼ばれる。
【００４４】
ストレージ装置１０とホスト２０との間のインタフェースに例えばＳＣＳＩが適用される場合、当該インタフェースでは、一般に、セクタ中のデータをリードするためのコマンド（通常のリードコマンド）に加えて、セクタ中のデータと付加情報をまとめてリードするためのリードロングと呼ばれるコマンド（リードロングコマンド）が用意されている。第１の方法は、このリードロングコマンドを利用する。
【００４５】
以下、図６に示されるＥＣＣ設定処理において実行されるＥＣＣ取得処理（ステップＳ１０６）の詳細について図７を参照して説明する。図７は、ＥＣＣ取得処理の典型的な手順を示すフローチャートである。本実施形態におけるＥＣＣ取得処理の特徴は、第１の方法を用いて、チャンクＣＨＫｉを構成する全セクタ中のＥＣＣを取得することにある。
【００４６】
まずＥＣＣ取得部２０４は、図６のステップＳ１０１で取得された物理アドレスＡＤＲｊを、ＥＣＣ取得処理で用いられるリードアドレスＡＤＲｒとして設定する（ステップＳ２０１）。次にＥＣＣ取得部２０４は、リードアドレスＡＤＲｒを含むリードロングコマンドを、ストレージ装置１０のストレージコントローラ１２に発行する（ステップＳ２０２）。
【００４７】
ＥＣＣ取得処理の１回目のステップＳ２０２において、ＥＣＣ取得部２０４は、リードアドレスＡＤＲｒを含むリードロングコマンドを用いて、当該リードアドレスＡＤＲｒで指定されるストレージ装置１０のストレージ１１内の物理位置から、チャンクＣＨＫｉに対応するｎ個のセクタ群の先頭セクタのデータ及び付加情報をまとめてリードする。そしてＥＣＣ取得部２０４は、リードされたデータ及び付加情報をメモリ２２に格納する（ステップＳ２０３）。
【００４８】
次にＥＣＣ取得部２０４は、チャンクＣＨＫｉ内の全セクタのリードが完了したかを判定する（ステップＳ２０４）。もし、ステップＳ２０４の判定がＮｏであるならば、ＥＣＣ取得部２０４は、リードアドレスＡＤＲｒがチャンクＣＨＫｉの次のセクタの物理位置を指し示すように、当該リードアドレスＡＤＲｒを更新（例えばインクリメント）する（ステップＳ２０５）。するとＥＣＣ取得部２０４は、ステップＳ２０２に戻り、インクリメントされたリードアドレスＡＤＲｒを含むリードロングコマンドを用いて、チャンクＣＨＫｉの次のセクタのデータ及び付加情報をまとめてリードする。そしてＥＣＣ取得部２０４は、リードされたデータ及び付加情報をメモリ２２に格納する（ステップＳ２０３）。
【００４９】
以下同様に、ＥＣＣ取得部２０４は、Ｓ２０５及びＳ２０２乃至Ｓ２０４を繰り返す。これにより、チャンクＣＨＫｉ内の全セクタのリードが完了したものとする（ステップＳ２０４のＹｅｓ）。このときメモリ２２には、チャンクＣＨＫｉの全セクタ中のデータ及び付加情報が格納されている。そこでＥＣＣ取得部２０４は、チャンクＣＨＫｉの全セクタ中の付加情報からＥＣＣ群を取得する（ステップＳ２０６）。これによりＥＣＣ取得部２０４は、チャンクＣＨＫｉに関するＥＣＣ取得処理（ステップＳ１０６）を終了する。
【００５０】
＜ＥＣＣ取得処理の変形例＞
次に、本実施形態の変形例におけるＥＣＣ取得処理について、図８を参照して説明する。図８は、本実施形態の変形例におけるＥＣＣ取得処理の典型的な手順を示すフローチャートである。本変形例におけるＥＣＣ取得処理の特徴は、第２の方法を用いて、チャンクＣＨＫｉを構成する全セクタ中のＥＣＣを取得することにある。
【００５１】
まずＥＣＣ取得部２０４は、図６のステップＳ１０１で取得された物理アドレスＡＤＲｊを、ＥＣＣ取得処理で用いられるリードアドレスＡＤＲｒとして設定する（ステップＳ２１１）。次にＥＣＣ取得部２０４は、リードアドレスＡＤＲｒを含むＥＣＣリードコマンドを、ストレージ装置１０のストレージコントローラ１２に発行する（ステップＳ２１２）。
【００５２】
ＥＣＣ取得処理の１回目のステップＳ２１２において、ＥＣＣ取得部２０４は、リードアドレスＡＤＲｒを含むＥＣＣリードコマンドを用いて、当該リードアドレスＡＤＲｒで指定されるストレージ装置１０のストレージ１１内の物理位置に格納されているチャンクＣＨＫｉの先頭セクタから、ＥＣＣのみをリードする。そしてＥＣＣ取得部２０４は、リードされたＥＣＣをメモリ２２に格納する（ステップＳ２１３）。
【００５３】
次にＥＣＣ取得部２０４は、チャンクＣＨＫｉ内の全セクタからのＥＣＣのリードが完了したかを判定する（ステップＳ２１４）。もし、ステップＳ２１４の判定がＮｏであるならば、ＥＣＣ取得部２０４は、リードアドレスＡＤＲｒがチャンクＣＨＫｉの次のセクタの物理位置を指し示すように、当該リードアドレスＡＤＲｒを更新（例えばインクリメント）する（ステップＳ２１５）。するとＥＣＣ取得部２０４は、ステップＳ２１２に戻り、インクリメントされたリードアドレスＡＤＲｒを含むＥＣＣリードコマンドを用いて、チャンクＣＨＫｉの次のセクタ中のＥＣＣをリードする。そしてＥＣＣ取得部２０４は、リードされたＥＣＣをメモリ２２に格納する（ステップＳ２１３）。
【００５４】
以下同様に、ＥＣＣ取得部２０４は、Ｓ２１５及びＳ２１２乃至Ｓ２１４を繰り返す。これにより、チャンクＣＨＫｉ内の全セクタからのＥＣＣのリードが完了したものとする（ステップＳ２１４のＹｅｓ）。このときメモリ２２には、チャンクＣＨＫｉの全セクタからリードされたＥＣＣ群が格納されている。そこでＥＣＣ取得部２０４は、メモリ２２からこのＥＣＣ群を取得する（ステップＳ２１６）。これによりＥＣＣ取得部２０４は、チャンクＣＨＫｉに関するＥＣＣ取得処理（ステップＳ１０６）を終了する。
【００５５】
なお、チャンクを単位に、チャンクを構成する全セクタからデータと付加情報をまとめてリードするためのインタフェースを、ストレージコントローラ１２に用意しても構わない。同様に、チャンクを単位に、チャンクを構成する全セクタからＥＣＣのみを取り出すためのインタフェースを、ストレージコントローラ１２に用意しても構わない。
【００５６】
ところで、ストレージ１１が例えばＲＡＩＤ（ディスクアレイ）により構成されている場合、ＥＣＣ取得部２０４は、リードロングコマンドを用いてＥＣＣを含む付加情報を当該ストレージ１１から直接リードすることはできない。このような場合に第１の方法（つまり、セクタ中のデータと付加情報をまとめてリードする方法）を適用するためには、ストレージコントローラ１２（つまり、ＲＡＩＤコントローラとして機能するストレージコントローラ１２）に、リードロングコマンドと同等のインタフェースを用意すれば良い。一方、第２の方法（つまり、セクタ中のＥＣＣのみをリードする方法）を適用するためには、ストレージコントローラ１２に、ストレージ１１からリードされたデータからＥＣＣのみを取り出す機能を用意すれば良い。
【００５７】
上述のＥＣＣ設定処理においてＥＣＣ取得部２０４は、チャンクＣＨＫｉの全セクタから取得したＥＣＣ群を結合し（ステップＳ１０７）、当該結合されたＥＣＣ群を、チャンクＣＨＫｉの物理アドレスＡＤＲｊを含む重複管理レコード中のＥＣＣ値として用いる（ステップＳ１０８及びＳ１０９）。しかし、ＥＣＣ取得部２０４が、ＳＨＡ１のようなハッシュ関数を用いて、結合されたＥＣＣ群のハッシュ値を計算し、このハッシュ値をＥＣＣ値として用いても構わない。
【００５８】
ハッシュ値をＥＣＣ値として用いる場合、たとえ可変長のチャンクサイズが適用されたとしても、ＥＣＣ値のサイズは一定となる。このため重複チャンクの判定（探索）に、チャンクサイズに無関係に同一の方法が適用可能となる。また、セクタサイズに対してＥＣＣのサイズが比較的大きい場合も、ＥＣＣ値のサイズを小さくできるため、重複管理テーブル２０１の格納に必要な記憶容量を小さくできる。
【００５９】
次に、本実施形態において重複排除コントローラ２０５によってチャンク単位に実行される重複チャンク探索処理について、図９を参照して説明する。図９は、重複チャンク探索処理の典型的な手順を示すフローチャートである。重複チャンク探索処理は、例えば、ＥＣＣ設定処理とは非同期に、ホスト２０のＣＰＵ２４の負荷が一定レベルより低い場合、或いはスケジューリングされた時刻が到来した場合に実行されるものとする。しかし重複チャンク探索処理が、全てのチャンクについてＥＣＣ設定処理が実行された場合に実行されても構わない。
【００６０】
重複排除コントローラ２０５は、チャンク単位に実行される重複チャンク探索処理のために、アドレステーブル２０２を先頭エントリから順に参照する。この例では、重複チャンク探索処理の先頭で、重複排除コントローラ２０５が、アドレステーブル２０２内のｉ番目のエントリを参照したものとする（ステップＳ３０１）。このｉ番目のエントリには、チャンクＣＨＫｉの論理アドレスＬＢＡｉを含むアドレスレコードが格納されている。したがって、ステップＳ３０１は、重複排除コントローラ２０５がチャンクＣＨＫｉを選択することと等価である。つまり、ステップＳ３０１において重複排除コントローラ２０５は、重複判定対象としてチャンクＣＨＫｉを選択する。
【００６１】
次に重複排除コントローラ２０５は、アドレステーブル２０２内のｉ番目のエントリから、論理アドレスＬＢＡｉと対応付けられている物理アドレスＡＤＲｊ、つまり選択されたチャンクＣＨＫｉの物理アドレスＡＤＲｊを取得する（ステップＳ３０２）。そして重複排除コントローラ２０５は、物理アドレスＡＤＲｊに基づいて、重複管理テーブル２０１から物理アドレスＡＤＲｊに対応付けられたＥＣＣ値ＥＣＣｊを取得する（ステップＳ３０３）。即ち重複排除コントローラ２０５は、重複管理テーブル２０１に格納されている、物理アドレスＡＤＲｊを含む重複管理レコードから、ＥＣＣ値ＥＣＣｊを取得する。
【００６２】
次に重複排除コントローラ２０５は、ＥＣＣｊと同じＥＣＣ値を持つ他の重複管理レコード（ターゲットの重複管理レコード）を、重複管理テーブル２０１から探索する（ステップＳ３０４）。そしてＥＣＣ取得部２０４は、ターゲットの重複管理レコードを探索できたかを判定する（ステップＳ３０５）。
【００６３】
もし、ターゲットの重複管理レコードを探索できなかったならば（ステップＳ３０５のＮｏ）、重複排除コントローラ２０５は、チャンクＣＨＫｉのデータと同一内容のデータを持つ他のチャンクは存在しないものと判断して、チャンクＣＨＫｉに関する重複チャンク探索処理を終了する。この場合、重複排除コントローラ２０５は、次のチャンクに関する重複チャンク探索処理を開始する。
【００６４】
これに対し、ターゲットの重複管理レコードを探索できたならば（ステップＳ３０５のＹｅｓ）、重複排除コントローラ２０５は、探索された重複管理レコードに対応するチャンク（以下、チャンクＣＨＫｘと称する）は、チャンクＣＨＫｉのデータと同一内容のデータを持つ可能性があると判断する。そこで重複排除コントローラ２０５は、データ重複の有無を確認するために、ステップＳ３０６乃至Ｓ３０９を次のように実行する。
【００６５】
まず重複排除コントローラ２０５は、探索された重複管理レコード中の物理アドレスＡＤＲｙを取得する（ステップＳ３０６）。そして重複排除コントローラ２０５は、物理アドレスＡＤＲｊ及びＡＤＲｙに基づいて、チャンクＣＨＫｉ及びＣＨＫｘのデータを、ストレージ装置１０からリードする（ステップＳ３０７）。即ち重複排除コントローラ２０５は、物理アドレスＡＤＲｊを含むリードコマンドをストレージコントローラ１２に発行することにより、当該物理アドレスＡＤＲｊで指定されるストレージ１１の記憶領域に格納されているチャンクＣＨＫｉのデータをリードする。同様に重複排除コントローラ２０５は、物理アドレスＡＤＲｙを含むリードコマンドをストレージコントローラ１２に発行することにより、当該物理アドレスＡＤＲｙで指定されるストレージ１１の記憶領域に格納されているチャンクＣＨＫｘのデータをリードする。
【００６６】
次に重複排除コントローラ２０５は、リードされたチャンクＣＨＫｉのデータとリードされたチャンクＣＨＫｘのデータとを比較して（ステップＳ３０８）、当該両データが一致するかを判定する（ステップＳ３０９）。もし、両データが一致しないならば（ステップＳ３０９のＮｏ）、重複排除コントローラ２０５は、チャンクＣＨＫｘ及びＣＨＫｉ間でデータが重複していないと判断する。この場合、重複排除コントローラ２０５はステップＳ３０４に戻って、ＥＣＣｊと同じＥＣＣ値を持つ新たな重複管理レコードを、重複管理テーブル２０１から探索する。
【００６７】
これに対し、両データが一致するならば（ステップＳ３０９のＹｅｓ）、チャンクＣＨＫｘ及びＣＨＫｉ間でデータが重複していると判断する。この場合、重複排除コントローラ２０５は、例えばチャンクＣＨＫｘを、チャンクＣＨＫｉにマージするための重複チャンクマージ処理（ステップＳ３１０）を実行する。そして重複排除コントローラ２０５は、ステップＳ３０４に戻って、ＥＣＣｊと同じＥＣＣ値を持つ新たな重複管理レコードを、重複管理テーブル２０１から探索する。
【００６８】
重複排除コントローラ２０５は、このステップＳ３０４から始まる処理を、ＥＣＣｊと同じＥＣＣ値を持つ新たな重複管理レコードが探索できなくなるまで（ステップＳ３０５のＮｏ）、繰り返す。以下の説明では、チャンクＣＨＫｘ及びチャンクＣＨＫｉを、それぞれ、マージ元（またはマージ元チャンク）及びマージ先（またはマージ先チャンク）と称する。なお、マージ元とマージ先は逆であっても構わない。
【００６９】
次に、図９に示される重複チャンク探索処理において実行される重複チャンクマージ処理（ステップＳ３１０）の詳細について図１０を参照して説明する。図１０は、本実施形態における重複チャンクマージ処理の典型的な手順を示すフローチャートである。
【００７０】
まず重複排除コントローラ２０５は、アドレステーブル２０２において、マージ元の物理アドレスＡＤＲｙをマージ先の物理アドレスＡＤＲｊに変更する（ステップＳ４０１）。次に重複排除コントローラ２０５は、重複管理テーブル２０１に格納されている、マージ先の物理アドレスＡＤＲｊを含む重複管理レコード中の参照カウントを、マージ元の物理アドレスＡＤＲｙを含む重複管理レコード中の参照カウントの値だけインクリメントする（ステップＳ４０２）。つまり重複排除コントローラ２０５は、マージ元の物理アドレスＡＤＲｙを含む重複管理レコード中の参照カウントの値を、マージ先の物理アドレスＡＤＲｊを含む重複管理レコード中の参照カウントに引き継がせる。
【００７１】
次に重複排除コントローラ２０５は、重複管理テーブル２０１に格納されている、マージ元の物理アドレスＡＤＲｙを含む重複管理レコード中の参照カウントを０に設定する（ステップＳ４０３）。また、ステップＳ４０３において重複排除コントローラ２０５は、マージ元の物理アドレスＡＤＲｙを含む重複管理レコード中のＥＣＣ値を、例えばクリアすることにより無効化する。
【００７２】
次に重複排除コントローラ２０５は、マージ元の物理アドレスＡＤＲｙで指定される、ストレージ装置１０内のマージ元のチャンクＣＨＫｘのデータ、つまりマージ元チャンクＣＨＫｘを構成するｎ個のセクタのデータを削除する（ステップＳ４０４）。これにより、チャンクＣＨＫｘは、チャンクＣＨＫｉにマージされる。
【００７３】
なお本実施形態では、値が０の参照カウントを含む重複管理レコード中の物理アドレスで指定される記憶領域は、空き記憶領域として管理される。したがって、マージ元の物理アドレスＡＤＲｙで指定される記憶領域も空き記憶領域として管理される。このため重複排除コントローラ２０５は、必ずしもマージ元のチャンクＣＨＫｘのデータを削除する必要はない。
【００７４】
次に、上述の重複チャンクマージ処理を含む重複チャンク探索処理の具体例について、図１１及び図１２を参照して説明する。図１１及び図１２は重複チャンク探索処理に起因する、それぞれ重複管理テーブル２０１及びアドレステーブル２０２の状態の変化の例を示す。
【００７５】
まず、図１１及び図１２において、矢印Ａ１及びＡ２の基端側には、重複チャンク探索処理が開始される前の重複管理テーブル２０１及びアドレステーブル２０２の状態が示されている。この重複管理テーブル２０１及びアドレステーブル２０２の状態は、図４及び図５に示されるそれらの状態と同一である。
【００７６】
この状態では、重複管理テーブル２０１において、物理アドレスＡＤＲ１を含む重複管理レコード中のＥＣＣ値ＥＣＣ１は、物理アドレスＡＤＲ３を含む重複管理レコード中のＥＣＣ値ＥＣＣ３に等しいものとする。また、アドレステーブル２０２において、物理アドレスＡＤＲ１は論理アドレスＬＢＡ３と対応付けられており、物理アドレスＡＤＲ３は論理アドレスＬＢＡ２及びＬＢＡ６と対応付けられている。つまり、物理アドレスＡＤＲ３は、２つの論理アドレスＬＢＡ２及びＬＢＡ６（チャンクＣＨＫ２及びＣＨＫ６）から参照されており、したがって物理アドレスＡＤＲ３を含む重複管理レコード中の参照カウントは２である。
【００７７】
以上のような重複管理テーブル２０１及びアドレステーブル２０２の状態で、アドレステーブル２０２が１回目の重複チャンク探索処理を開始して、チャンクＣＨＫ１を選択したものとする（ステップＳ３０１）。チャンクＣＨＫ１の論理アドレスＬＢＡ１は、アドレステーブル２０２によって物理アドレスＡＤＲ２に対応付けられている。
【００７８】
重複排除コントローラ２０５は、重複管理テーブル２０１から、チャンクＣＨＫ１の物理アドレスＡＤＲ２に対応付けられたＥＣＣ値ＥＣＣ２を取得する（ステップＳ３０２及びＳ３０３）。そして重複排除コントローラ２０５は、ＥＣＣ２と同じＥＣＣ値を持つ他の重複管理レコードを、重複管理テーブル２０１から探索する（ステップＳ３０４）。
【００７９】
本実施形態では、ＥＣＣ２と同じＥＣＣ値を持つ他の重複管理レコードは存在しない（ステップＳ３０５のＮｏ）。この場合、重複排除コントローラ２０５は、２回目の重複チャンク探索処理を開始して、チャンクＣＨＫ２を選択する（ステップＳ３０１）。チャンクＣＨＫ２の論理アドレスＬＢＡ２は、アドレステーブル２０２によって物理アドレスＡＤＲ３に対応付けられている。
【００８０】
重複排除コントローラ２０５は、重複管理テーブル２０１から、チャンクＣＨＫ２の物理アドレスＡＤＲ３に対応付けられたＥＣＣ値ＥＣＣ３を取得する（ステップＳ３０２及びＳ３０３）。そして重複排除コントローラ２０５は、ＥＣＣ３と同じＥＣＣ値を持つ他の重複管理レコードを、重複管理テーブル２０１から探索する（ステップＳ３０４）。
【００８１】
本実施形態では、ＥＣＣ３と同じＥＣＣ値はＥＣＣ１であり、したがってＥＣＣ３と同じＥＣＣ値を持つ他の重複管理レコードは存在する（ステップＳ３０５のＹｅｓ）。この重複管理レコード（つまり、ＥＣＣ１を含む重複管理レコード）は、物理アドレスとしてＡＤＲ１を含む。ＡＤＲ１は、アドレステーブル２０２によって論理アドレスＬＢＡ３に対応付けられており、チャンクＣＨＫ３の物理アドレスを示す。この場合、重複排除コントローラ２０５は、チャンクＣＨＫ２の物理アドレスＡＤＲ３及びチャンクＣＨＫ３の物理アドレスＡＤＲ１に基づいて、チャンクＣＨＫ２及びＣＨＫ３のデータをストレージ装置１０からリードする（ステップＳ３０６及びＳ３０７）。そして重複排除コントローラ２０５は、チャンクＣＨＫ２及びＣＨＫ３のデータを比較する（ステップＳ３０８）。
【００８２】
本実施形態では、チャンクＣＨＫ２及びＣＨＫ３のデータは等しいものとする（ステップＳ３０９のＹｅｓ）。この場合、重複排除コントローラ２０５は、チャンクＣＨＫ３をチャンクＣＨＫ２にマージするための重複チャンクマージ処理（ステップＳ３１０）を実行する。即ち重複排除コントローラ２０５は、アドレステーブル２０２においてチャンクＣＨＫ３の論理アドレスＬＢＡ３に対応付けられた物理アドレスＡＤＲ１（つまりチャンクＣＨＫ３の物理アドレスＡＤＲ１）を、図１２において矢印Ａ２で示されるように、チャンクＣＨＫ２の物理アドレスＡＤＲ３に変更する（ステップＳ４０１）。
【００８３】
また重複排除コントローラ２０５は、重複管理テーブル２０１において物理アドレスＡＤＲ３に対応付けられた参照カウント（＝２）を、重複管理テーブル２０１において物理アドレスＡＤＲ１に対応付けられた参照カウント（＝１）だけインクリメントする（ステップＳ４０２）。これにより物理アドレスＡＤＲ３に対応付けられた参照カウントは、図１１において矢印Ａ１で示されるように、２から３にインクリメントされる。更に重複排除コントローラ２０５は、図１１において矢印Ａ１で示されるように、重複管理テーブル２０１において物理アドレスＡＤＲ１に対応付けられた参照カウントを０に設定し、且つ物理アドレスＡＤＲ１に対応付けられたＥＣＣ値を無効化（クリア）する（ステップＳ４０２）。
【００８４】
上述のように、本実施形態において重複排除コントローラ２０５は、重複管理レコード中のＥＣＣ値、つまりストレージ装置１０に既に格納されている各チャンクを構成する全セクタ中のＥＣＣの列を、重複チャンクの探索（判定）に利用する。このように本実施形態においては、セクタのデータのエラー検出及びエラー訂正のために当該セクタに付されるＥＣＣを、データの重複を検出するための指標として利用する。これに対して、従来技術（第１の重複排除技術）では、各チャンクのデータをストレージ装置にライトする際に、当該データのハッシュ値が計算される。そして、このハッシュ値が重複管理レコード中に設定されて、重複チャンクの探索に利用される。また、別の従来技術（第２の重複排除技術）では、ストレージ装置に格納されている全データがリードされて比較される。
【００８５】
本実施形態においては、ＥＣＣの値をハッシュ値の代替として用い、ＥＣＣの値が等しい場合にのみデータを比較することで、チャンクのデータの重複を検出する。したがって本実施形態によれば、重複チャンクの探索に利用される情報を生成するための計算（ハッシュ計算）、或いは全データの比較を不要にして、チャンクのデータの重複検出に要するコストを低減することができる。
【００８６】
次に、本実施形態においてアクセス部２０６によって実行されるライト処理について、チャンクＣＨＫｓに新たなデータをライトする場合を例に、図１３を参照して説明する。図１３は、ライト処理の典型的な手順を示すフローチャートである。本実施形態においてライト処理は、アクセス要求部２０３からのライトアクセス要求に応じて実行される。
【００８７】
まずアクセス部２０６が、アクセス要求部２０３からのライトアクセス要求に応じて、チャンクＣＨＫｓへのデータライトを開始するものとする。この場合、アクセス部２０６は、チャンクＣＨＫｓの論理アドレスＬＢＡｓに対応付けられた有効な物理アドレスＡＤＲｔを含むアドレスレコード（ターゲットのアドレスレコード）を、アドレステーブル２０２から探索する（ステップＳ５０１）。そしてアクセス部２０６は、ターゲットのアドレスレコードを探索できたかを判定する（ステップＳ５０２）。
【００８８】
もし、ターゲットのアドレスレコードを探索できたならば（ステップＳ５０２のＹｅｓ）、アクセス部２０６は、探索されたアドレスレコードから、物理アドレスＡＤＲｔを取得する（ステップＳ５０３）。そしてアクセス部２０６は、取得された物理アドレスＡＤＲｔに基づいて重複管理テーブル２０１を探索することにより、当該取得された物理アドレスＡＤＲｔを含む重複管理レコード中の参照カウントを取得する（ステップＳ５０４）。次にアクセス部２０６は、取得された参照カウントが１であるかを判定する（ステップＳ５０５）。
【００８９】
もし、取得された参照カウントが１でないならば（ステップＳ５０５のＮｏ）、アクセス部２０６は、現在のチャンクＣＨＫｓのデータは他の１つ以上のチャンクのデータと重複しており、したがって新たなデータを、現在のチャンクＣＨＫｓのデータ（より詳細には、重複データ）に上書きすることはできないと判断する。つまりアクセス部２０６は、新たなデータを、現在のチャンクＣＨＫｓのデータがライトされている記憶領域（より詳細には、物理アドレスＡＤＲｔによって指定される記憶領域）とは別の記憶領域にライトする必要があると判断する。明らかなように、今回のライト処理によりチャンクＣＨＫｓにライトされる新たなデータは、上述の他の１つ以上のチャンクのデータと重複しないものである。そこでアクセス部２０６は、取得された参照カウント（より詳細には、取得された物理アドレスＡＤＲｔを含む重複管理レコード中の参照カウント）を１デクリメントして（ステップＳ５０６）、ステップＳ５０７に進む。一方、ターゲットのアドレスレコードを探索できなかったならば（ステップＳ５０２のＮｏ）、アクセス部２０６は、ステップＳ５０３乃至Ｓ５０６をスキップしてステップＳ５０７に進む。
【００９０】
ステップＳ５０７においてアクセス部２０６は、新たなデータ（つまり、アクセス要求部２０３によって要求されたライトデータ）がチャンクＣＨＫｓのデータとしてライトされるべき、ストレージ装置１０（ストレージ１１）内の空き記憶領域（つまり、空きチャンク領域）を確保する（ステップＳ５０７）。アクセス部２０６は、この空きチャンク領域を次のように確保する。まずアクセス部２０６は、重複管理テーブル２０１から、値が０の参照カウントを含む重複管理レコードを探索する。そしてアクセス部２０６は、探索された重複管理レコード中の物理アドレスＡＤＲｕを、ライト先の空きチャンク領域の物理アドレスとして取得する。これによりアクセス部２０６は、ライト先の空きチャンク領域を確保する。アクセス部２０６は、ステップＳ５０７を実行すると、ステップＳ５０８に進む。
【００９１】
一方、取得された参照カウントが１であるならば（ステップＳ５０５のＹｅｓ）、アクセス部２０６は、現在のチャンクＣＨＫｓのデータは他の１つ以上のチャンクのデータと重複しておらず、したがって新たなデータを、現在のチャンクＣＨＫｓのデータに上書きすることが可能であると判断する。この場合、新たなデータのライト先は、現在のチャンクＣＨＫｓのデータがライトされている記憶領域（チャンク領域）であり、物理アドレスＡＤＲｔによって指定される。ステップＳ５０５の判定がＹｅｓの場合、アクセス部２０６は、ステップＳ５０６及びＳ５０７をスキップしてステップＳ５０８に進む。
【００９２】
ステップＳ５０８においてアクセス部２０６は、ライト先のチャンク領域の物理アドレスを含む重複管理レコード中のＥＣＣ値をクリアし、且つ当該重複管理レコード中の参照カウントを１に設定する。ここで、ライト先のチャンク領域は、ステップＳ５０７を介してステップＳ５０８が実行される場合、当該ステップＳ５０７で確保された空きチャンク領域であり、当該ライト先のチャンク領域の物理アドレスはＡＤＲｕである。これに対し、ステップＳ５０７をスキップしてステップＳ５０８が実行される場合、ライト先のチャンク領域は、現在チャンクＣＨＫｓのデータ（旧データ）が格納されているチャンク領域であり、当該ライト先のチャンク領域の物理アドレスはＡＤＲｔである。
【００９３】
アクセス部２０６は、ステップＳ５０８を実行すると、アクセス要求部２０３によって要求されたライトデータを、チャンクＣＨＫｓの新たなデータとして、ストレージ装置１０（ストレージ１１）におけるライト先のチャンク領域にストレージコントローラ１２によりライトさせる（ステップＳ５０９）。これにより、チャンクＣＨＫｓの新データは、ｎ個のセクタに分散してライトされる。ｎ個のセクタの各々にはＥＣＣを含む付加情報が付されている。ＥＣＣは、ｎ個のセクタに分散してライトされるデータに基づいてストレージコントローラ１２によって生成される。
【００９４】
なお、図２に示される、ＥＣＣ取得部２０４、重複排除コントローラ２０５及びアクセス部２０６がストレージコントローラ１２に設けられても構わない。この場合、重複管理テーブル２０１及びアドレステーブル２０２は、ストレージコントローラ１２が有するメモリに格納されれば良い。
【００９５】
前記実施形態では、ストレージ装置１０は、単一のホスト２０と接続されている。しかし、ストレージ装置１０が、ホスト２０を含む複数のホストと、ホストインタフェースバス３０（またはネットワーク）を介して接続されていても良い。この場合、ホスト２０以外のホストからのストレージ装置１０へのアクセスに関しても、例えば、ホスト２０のみが、重複排除のための前記実施形態と同様の処理を行えば良い。また、ホスト２０を含む複数のホストが、それぞれ、図２に示される構成を有し、当該複数のホストが重複排除のための前記実施形態と同様の処理を行っても構わない。この場合、複数のホストがそれぞれ重複管理テーブル２０１及びアドレステーブル２０２を有し、当該重複管理テーブル２０１及びアドレステーブル２０２を複数のホスト間で同期化しても良い。
【００９６】
以上説明した少なくとも１つの実施形態によれば、データの重複の検出に要するコストを低減することができる。
【００９７】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００９８】
１０…ストレージ装置、１１…ストレージ、１２…ストレージコントローラ、２０…ホスト（ホスト計算機）、２２…メモリ、２４…ＣＰＵ、２０１…重複管理テーブル、２０２…アドレステーブル、２０４…ＥＣＣ取得部、２０５…重複排除コントローラ（重複検出部）、２０６…アクセス部。
【図１】
0006419662.tif 000002
【図２】
0006419662.tif 000003
【図３】
0006419662.tif 000004
【図４】
0006419662.tif 000005
【図５】
0006419662.tif 000006
【図６】
0006419662.tif 000007
【図７】
0006419662.tif 000008
【図８】
0006419662.tif 000009
【図９】
0006419662.tif 000010
【図１０】
0006419662.tif 000011
【図１１】
0006419662.tif 000012
【図１２】
0006419662.tif 000013
【図１３】
0006419662.tif 000014