(57)【要約】      （修正有）【課題】データ重複排除技術においてハッシュテーブルのエントリを一定量のみキャッシュメモリに保持し、高速に検索可能で、かつ、キャッシュメモリの容量不足を防止するストレージ装置を提供する。【解決手段】ストレージ装置は、ホストコンピュータに指定されたデータを複数のチャンクに分割し、チャンクの各々のデータに基づいて各々のハッシュ値を生成し、記録媒体に書き込まれているチャンクの識別子とハッシュ値とが対応付けられて記憶されているハッシュテーブルを保持する揮発性メモリを備える。記録媒体にチャンクを書き込むときに、チャンクのデータに基づいて生成されたハッシュ値と一致するハッシュ値が、既にハッシュテーブルに記録されているか否かを探索し、記録されていない場合には書き込み、記録されている場合には書き込みを抑止する。【選択図】図７
2018185760.tif 000002
【特許請求の範囲】
【請求項１】
データを記録するための記録媒体を持つストレージ装置において、
ホストコンピュータからのデータ書き込み要求によって指定されたデータを複数のチャ
ンクに分割するチャンク分割部と、
前記複数のチャンクの各々のデータに基づいて、前記複数のチャンクの各々のハッシュ
値を生成するハッシュ生成部と、
前記記録媒体に書き込まれているチャンクの識別子とそのチャンクのハッシュ値とが対
応付けられて記憶されているハッシュテーブルを保持する揮発性メモリと、
前記記録媒体に第一のチャンクを書き込むときに、前記第一のチャンクのデータに基づ
いて前記ハッシュ生成部で生成されたハッシュ値と一致するハッシュ値が、既に前記ハッ
シュテーブルに記録されているか否かを探索し、一致するハッシュが前記ハッシュテーブ
ルに記録されていない場合には、前記第一のチャンクを前記記録媒体に書き込み、一致す
るハッシュが前記ハッシュテーブルに記録されている場合には、前記第一のチャンクの前
記記録媒体への書き込みを抑止する制御部と、
を備えるストレージ装置。
【請求項２】
前記制御部は、ホストコンピュータからの読み出し要求によって指定されたデータを前
記記録媒体から読み出したときに、
当該データを構成する複数のチャンクについて、各々のチャンクに基づいて生成された
ハッシュ値と一致するハッシュ値が前記ハッシュテーブルに既に登録されているか否かを
探索し、一致するハッシュ値が前記ハッシュテーブルに記録されていない場合には、当該
チャンクの識別子とハッシュ値とを前記ハッシュテーブルに登録する、
請求項１記載のストレージ装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、データの重複を排除するためのストレージ装置に関する。
【背景技術】
【０００２】
近年，情報処理システムで使われるビックデータを格納するためにストレージ装置の大
容量化が進むだけでなく、限られた記憶容量を有効に使用するストレージ装置が求められ
ている。例えば、データを保存する際にデータを一定の大きさに区切り、各々のハッシュ
値を計算し、ハッシュ値を保存しているデータテーブル上に重複する値がある場合は、該
当データを書き込まないという、データ重複排除技術が注目されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特許第５４４４５０６号
【発明の概要】
【発明が解決しようとする課題】
【０００４】
データ重複排除技術は、その動作原理上、ハッシュテーブル内の検索が必要になる。ハ
ッシュテーブルは、保存データ量の増加に伴い大きくなる。データ重複排除処理速度向上
には、ハッシュテーブルの検索時間を短縮することが重要となる。例えば、ハッシュテー
ブルをメモリ上に配置すれば高速に検索可能だが、データ量増加に伴い必要メモリ量が増
大するため、コストが掛かりデータ量によっては容量が足りなくなってしまう。また、仮
想メモリのようにハッシュテーブルの実体をHDDのような二次記憶装置に持てば、コスト
を抑えられデータ量上限は向上させられるが、検索に時間がかかる。
【課題を解決するための手段】
【０００５】
実施形態のストレージ装置は、ホストコンピュータに指定されたデータを複数のチャン
クに分割するチャンク分割部と、前記複数のチャンクの各々のデータに基づいて各々のハ
ッシュ値を生成するハッシュ生成部と、記録媒体に書き込まれているチャンクの識別子と
そのチャンクのハッシュ値とが対応付けられて記憶されているハッシュテーブルを保持す
る揮発性メモリと、前記記録媒体に第一のチャンクを書き込むときに、第一のチャンクの
データに基づいて前記ハッシュ生成部で生成されたハッシュ値と一致するハッシュ値が、
既に前記ハッシュテーブルに記録されているか否かを探索し、一致するハッシュが記録さ
れていない場合には第一のチャンクを書き込み、一致するハッシュが記録されている場合
には書き込みを抑止する制御部と、を備える。
【図面の簡単な説明】
【０００６】
【図１】実施形態に係るストレージシステムのブロック図。
【図２】ディスクアレイ制御装置の機能構成を示すブロック図。
【図３】ホストコンピュータの書き込み要求で指定されたデータとチャンクとの関係の一例を示す図。
【図４】ハッシュテーブルのデータ構造例を示す図。
【図５】メタテーブルのデータ構造例を示す図。
【図６】チャンクテーブルのデータ構造例を示す図。
【図７】ディスクアレイ制御装置がデータ書き込み要求を受信した場合に実行されるデータ書き込み処理の手順を示す図。
【図８】ディスクアレイ制御装置がデータ読み込み要求を受信した場合に実行されるデータ書き込み処理の手順を示す図。
【図９】ハッシュテーブルのエントリをソートするためのエージング周期処理の手順を示す図。
【発明を実施するための形態】
【０００７】
以下、発明を実施するための実施形態について説明する。
【０００８】
図１は、実施形態に係るストレージシステムのブロック図を示す。本実施形態のストレ
ージシステムは、ホストコンピュータ１００（以下、ホスト１００と称する）とストレー
ジ装置２００を備える。ストレージ装置２００は、ネットワーク１１０を介してホスト１
００と接続されている。
【０００９】
ホスト１００は、サーバあるいはクライアントPCのような物理計算機である。ホスト１
００内では、ストレージ装置２００のデータにアクセスするためのアプリケーションプロ
グラムが動作する。ホスト１００は、このアプリケーションプログラムに従い、ストレー
ジ装置２００を外部記憶装置としてネットワーク１１０を介して利用する。ネットワーク
の種類は、SAN（Storage Area Network）、あるいはEthernet（登録商標）等である。
【００１０】
ストレージ装置２００は、ディスクアレイ制御装置２１０およびRAIDディスクアレイ２
３０を備える。
【００１１】
ディスクアレイ制御装置２１０は、RAIDディスクアレイ２３０と、ディスクインタフェ
ースバス２２０を介して接続されている。ディスクインタフェースバス２２０のインタフ
ェース種別は、SCSI、あるいはFC、あるいはSAS（Serial Attached SCSI）、あるいはSAT
A（Serial AT Attachment）等である。
【００１２】
ディスクアレイ制御装置２１０は、ホストインタフェース（ホストＩ／Ｆ）２１１と、
ディスクインタフェース（ディスクＩ／Ｆ）２１２と、キャッシュメモリ２１３と、キャ
ッシュコントローラ２１４と、ＦＲＯＭ２１５と、ローカルメモリ２１６と、ＣＰＵ２１
７と、チップセット２１８と、内部バス２１９とを備える。
【００１３】
ディスクアレイ制御装置２１０は、ストレージ装置２００を外部記憶装置として利用す
るホスト１００と、ネットワーク１１０を経由し、ホストＩ／Ｆ２１１を介して接続され
る。ホストＩ／Ｆ２１１のインタフェース種別はFC（Fibre Channnel）、あるいはiSCSI
（internet SCSI）などである。
【００１４】
ホストＩ／Ｆ２１１は、ホスト１００との間のデータ転送（データ転送プロトコル）を
制御する。
【００１５】
ディスクＩ／Ｆ２１２は、ホスト１００からRAIDディスクアレイ２３０のドライブへの
データライト／リード要求とその応答を送受信するためのインタフェースである。また、
キャッシュコントローラ２１４は、キャッシュメモリ２１３へのデータライト／リード要
求を行う。
【００１６】
キャッシュメモリ２１３は、ホスト１００からのライト／リード要求に対するキャッシ
ュとして用いられる。本実施形態では、主に図２に示すハッシュテーブル２１３aを格納
する。なお、キャッシュメモリ２１３はミラーリング等の冗長化が成されている構成でも
良い。
【００１７】
キャッシュコントローラ２１４は、ＣＰＵ２１７上で動作するディスクアレイ制御プロ
グラムからの命令に従いキャッシュメモリ２１３へのデータのリード／ライト処理を実施
する。ず
【００１８】
ＦＲＯＭ２１５は、ＣＰＵ２１７により実行されるディスクアレイ制御プログラムを格
納するための書き換えが可能な不揮発性メモリである。本実施形態では、ディスク制御装
置が起動されたときの最初の処理でＦＲＯＭ２１５に格納されているディスクアレイ制御
プログラムを、ローカルメモリ２１６にコピーする。
【００１９】
ローカルメモリ２１６は、ＦＲＯＭ２１５からコピーされたディスクアレイ制御プログ
ラムを記憶するのに用いられるほか、ローカルメモリ２１６の一部の領域は、ＣＰＵ２１
７が動作する上で使用するワーク領域として用いられる。
【００２０】
ＣＰＵ２１７は、ローカルメモリ２１６に格納されたディスクアレイ装置制御プログラム
のプログラムコードに従い、ディスクアレイ制御装置２１０内の各部を制御する。また、
ＣＰＵ２１７は、チップセット２１８を介し、ローカルメモリ２１６上に格納されている
ディスクアレイ制御プログラムが動作し、ディスクアレイ制御装置２１０全体の制御を行
う。
【００２１】
チップセット２１８は、ＣＰＵ２１７及びその周辺回路を内部バス２１９に結合するブ
リッジ回路である。
【００２２】
内部バス２１９は汎用バスであり、例えばPCI-expressバスである。ホストＩ／Ｆ２１
１、ディスクＩ／Ｆ２１２、キャッシュコントローラ２１４及びチップセット２１８は、
内部バス２１９により相互接続されている。また、ＦＲＯＭ２１５、ローカルメモリ２１
６、ＣＰＵ２１７は、チップセット２１８を介して内部バス２１９に接続されている。
【００２３】
RAIDディスクアレイ２３０は、複数のハードディスクドライブ（HDD)を用いて構成され
る。RAIDディスクアレイ２３０に代えて、例えば複数のHDDおよび複数のSSD（ソリッドス
テートドライブ）を用いて構成されるRAIDアレイや複数のSSDのみを用いて構成されるRAI
Dアレイを適用しても構わない。また、RAID構成を持たない単なる複数のストレージドラ
イブの集合（ドライブアレイ）を適用しても構わない。また、RAIDディスクアレイ２３０
は、ディスクアレイ制御プログラムによって管理される。以降のRAIDディスクアレイ２３
０を使用した機能についても、ディスクアレイ制御プログラムによって制御する。さらに
本実施形態において、RAIDディスクアレイ２３０は、図２に示すメタテーブル２３０aお
よびチャンクテーブル２３０bを格納する。なお、RAIDディスクアレイ２３０に代えて、
フラッシュメモリ等を用いることも可能である。
【００２４】
本実施形態においてディスクアレイ制御装置２１０は、RAIDディスクアレイ２３０を含
むストレージ装置に備えられている。しかし、ディスクアレイ制御装置２１０が、ストレ
ージ装置２００から独立して備えられていても構わない。この場合、ディスクアレイ制御
装置２１０が、ホスト１００に内蔵されていても構わない。また、ディスクアレイ制御装
置２１０の機能が、ホスト１００の有するオペレーティングシステム（ＯＳ）の機能の一
部を用いて実現されても構わない。
【００２５】
また、ディスクアレイ制御装置２１０が、ホスト１００のカードスロットに装着して用
いられるカードに備えられていても構わない。また、ディスクアレイ制御装置２１０の一
部がホスト１００に内蔵され、当該ディスクアレイ制御装置２１０の残りが前記カードに
備えられていても構わない。
【００２６】
図２は、図１に示されるディスクアレイ制御装置２１０の機能構成を示すブロック図で
ある。ディスクアレイ制御装置２１０は、分割部３００、重複管理部３０１、重複判定部
３０２、ハッシュ生成部３０３、アクセスコントローラ３０４を備えている。分割部３０
０、重複管理部３０１、重複判定部３０２、ハッシュ生成部３０３の機能については後述
する。アクセスコントローラ３０４は、RAIDディスクアレイ２３０に対するデータの読み
出し、書き込みを制御する。これらの機能要素３００ないし３０４は、図１に示されるデ
ィスクアレイ制御装置のＣＰＵ２１７が制御プログラムを実行することにより実現される
ソフトウェアモジュールである。機能要素３００ないし３０４の一部または全部がハード
ウェアモジュールによって実現されても構わない。
【００２７】
ローカルメモリ２１６は、制御プログラム領域２１６ａ、テーブル領域２１６ｂ、ワーク
領域２１６ｃを含む。制御プログラム領域２１６ａは、ＣＰＵ２１７によって実行される
制御プログラムの少なくとも一部を格納するのに用いられる。この制御プログラムは、前
述したようにFROM２１５に予め格納されており、当該制御プログラムの少なくとも一部は
、ディスクアレイ制御装置２１０の起動時に当該FROM２１５からローカルメモリ２１６の
制御プログラム領域２１６ａにロードされる。
【００２８】
テーブル領域２１６ｂは、ディスクアレイ制御装置２１０格納されている各種のテーブ
ルの少なくとも一部を格納するのに用いられる。ワーク領域２１６ｃは、ＣＰＵ２１７が
制御プログラムを実行する際に利用される一時的なデータを格納するのに用いられる。
【００２９】
RAIDディスクアレイ２３０は、メタテーブル２３０a、チャンクテーブルb（詳細は後述
する）を格納する。つまりRAIDディスクアレイ２３０は、メタテーブル２３０a、チャン
クテーブル２３０bがそれぞれ格納される記憶領域を含む。
【００３０】
キャッシュメモリ２１３は、ハッシュテーブル２１３a（詳細は後述する）を格納する
。つまりキャッシュメモリ２１３は、ハッシュテーブル２１３aが格納される記憶領域を
含む。ハッシュテーブル２１３aの記憶容量は固定長であるものとする。
【００３１】
一般的なストレージシステムでは、論理ボリュームに最初に割り当てられた記憶容量（
例えば、最小の単位の記憶容量）で運用が開始される。論理ボリュームとは、ホストによ
って論理的なストレージドライブとして認識される記憶領域を指す。論理ボリュームには
、例えば４Ｋ（キロ）バイト毎にRAIDディスクアレイ２３０の記憶領域（物理領域）が適
宜割り当てられる。この種のストレージシステムは、運用開始後の状況に応じて、論理ボ
リュームの記憶容量をフレキシブルに増加させる機能を有する。本実施形態におけるスト
レージシステムも同様である。
【００３２】
図３は、ホスト１００からの書き込み要求で指定されたデータとチャンクとの関係の例
を示す。分割部３００は、まず、図３に示されるデータを、固定長、例えば４キロバイト
（４Ｋバイト）のデータの塊に分割する。この４Ｋバイト毎のデータの塊をチャンクと呼
ぶ。重複管理部３０１および重複判定部３０２は、チャンク毎に重複の有無を検索し、管
理する。図３の例では、データＦのサイズは４ＮＫバイトである。この場合、データＦは
、Ｎ個のチャンク＃０ないし＃Ｎ−１に分割される。重複管理部３０１は、チャンク＃０
ないし＃Ｎ−１にユニークな識別番号であるチャンク番号を付与する。本実施形態におい
て、チャンク番号は８バイトで表される。
【００３３】
ここで、本実施形態で適用されるデータライト時の重複排除の概要について説明する。
まず、ホスト１００からストレージ装置２００のディスクアレイ制御装置２１０に、チャ
ンクＡを含むデータの書き込みが要求されたことを想定する。また、チャンクＡのハッシ
ュ値がＨ（Ａ）であるものとする。重複判定部３０２は、チャンクＡのハッシュ値Ｈ（Ａ
）をハッシュテーブルに登録されているハッシュ値と順次比較する。この比較の結果に基
づいて、重複判定部３０２は、RAIDディスクアレイ２３０にチャンクＡと同一内容を持つ
チャンク（以下、チャンクＡと称する）が格納されているかを判定する。
【００３４】
まず、図４を用いてキャッシュメモリ２１３に格納されるハッシュテーブル２１３aに
ついて説明する。ハッシュテーブルは、チャンク番号に対応付けられたエントリの集合を
有する。ハッシュテーブルの各エントリは、そのエントリに登録されたチャンク番号が付
与されたチャンクに関するハッシュ値、参照ビット、ヒットカウンタから構成される。
【００３５】
ハッシュ値は、前述した通り、対応付けられたチャンク番号が付与されたチャンクのデ
ータに基づいて、所定のハッシュ関数を用いて計算した値である。参照ビットは、後述す
るエージング周期処理の周期期間内において、対応付けられたチャンク番号が示すチャン
クがアクセスされた際にビット”１”が設定されるもので、対応付けられたチャンクがア
クセスされたことを示すフラグ情報である。参照ビットは、後述するエージング周期処理
が終了した後にビット”０”が設定されてフラグ情報がクリアされる。ヒットカウンタは
、後述するエージング周期処理の際に、ハッシュエントリの優先順位を決定するために用
いられる。ハッシュテーブル２１３aは、RAIDディスクアレイ２３０に書き込まれるべき
チャンクと同一内容を持つチャンクが、既に書き込まれているかを重複判定部３０２が判
定するのに用いられる。
【００３６】
もし、ハッシュテーブル２１３aにハッシュ値Ｈ（Ａ）に一致するハッシュ値（つまり
、ハッシュ値Ｈ（Ａ））が登録されているならば、重複判定部３０２は、RAIDディスクア
レイ２３０にチャンクＡが格納されていると判定する。つまり重複判定部３０２は、チャ
ンクＡが重複すると判定する。一方、ハッシュテーブル２１３aにハッシュ値Ｈ（Ａ）が
登録されていないならば、重複判定部３０２は、チャンクＡが重複しないと判定する。
【００３７】
チャンクＡが重複しないと判定された場合、アクセスコントローラ３０４は、書き込み
要求によって指定された論理アドレスに割り当てられる物理アドレスの示す物理領域に、
チャンクＡを書き込む指示を出す。このとき重複管理部３０１は、ハッシュ値Ｈ（Ａ）と
チャンクＡのチャンク番号との対を含むハッシュ情報を、ハッシュテーブル２１３aに登
録する。
【００３８】
一方、チャンクＡが重複すると判定された場合には、アクセスコントローラ３０４は、
チャンクＡをRAIDディスクアレイ２３０に書き込むのを抑止する。この場合、重複管理部
３０１は、ホスト１００からの書き込み要求によって指定された論理アドレスに、チャン
クＡが既にRAIDディスクアレイ２３０に書き込まれている物理アドレスを割り当てる（つ
まりマッピングする）。
【００３９】
図５は、メタテーブル２３０aのデータ構造例を示す。メタテーブル２３０aは、論理ボ
リュームを４Ｋ（キロ）バイト毎に区切ることにより得られる各領域（４Ｋバイト領域）
に書き込まれているチャンクを管理するのに用いられる。メタテーブル２３０aは、論理
ボリュームのそれぞれの４Ｋバイト領域を指し示す論理アドレスに対応付けられたエント
リの集合である。メタテーブル２３０aの各エントリは、当該エントリに対応付けられた
論理アドレスの示す４Ｋバイト領域に格納されるチャンクのチャンク番号を登録するのに
用いられる。したがって重複管理部３０１は、メタテーブル２３０aを参照することによ
り、目的の論理アドレスで指定される領域に格納されているチャンクとデータが特定でき
る。
【００４０】
図６は、チャンクテーブル２３０ｂのデータ構造例を示す。チャンクテーブル２３０ｂ
は、チャンク番号に対応付けられたエントリの集合を有する。チャンクテーブル２３０ｂ
の各エントリは、当該エントリと対応付けられたチャンク番号を有するチャンクに関する
チャンク情報を登録するのに用いられる。チャンクテーブル２３０ｂの各エントリは、チ
ャンク番号、物理アドレス、重複数から構成される。物理アドレスは、対応付けられたチ
ャンク番号が付与されたチャンクが記録されている物理アドレスである。重複数は、対応
付けられたチャンク番号が付与されたチャンクが幾つの論理アドレスに対応付けられてい
るかを示す。重複数が１の場合には、対応付けられたチャンク番号が付与されたチャンク
が論理ボリューム内の１つの論理アドレスが指し示す４Ｋバイト領域だけに書き込まれて
いることを示す。この場合該当するチャンクが重複していないことを示す。重複数が２の
場合には、重複排除により、実態として１つのチャンクがRAIDディスクアレイ２３０に書
き込まれているものの、当該チャンクが２つの論理アドレスに対応付けられていることを
示す。つまり、ホスト１００から見て、同一内容を持つチャンクが論理ボリューム内の２
つの論理アドレスの指し示す４Kバイト領域に書き込まれていることを示す。
【００４１】
（ライト処理時の動作）
次に、本実施形態における、ストレージ装置２００のディスク
アレイ制御装置２１０がホスト１００からデータ書き込み要求を受信した場合に実行され
るライト処理時の動作について、図７を参照して説明する。
【００４２】
今、ホスト１００からネットワーク１１０を介してストレージ装置２００に、データの
書き込みを指定するデータ書き込み要求が送られたものとする。そして、ストレージ装置
２００のディスクアレイ制御装置２１０が、ホスト１００からのデータ書き込み要求を受
信したものとする。
【００４３】
まず、ディスクアレイ制御装置２１０の分割部３００は、データ書き込み要求で指定さ
れたデータを例えば４Ｋバイト毎に区切る。これにより、分割部３００は、指定されたデ
ータを４Ｋバイトのサイズを有する複数のチャンクに分割する（Ｓ１）。つまり重複管理
部３０１は、指定されたデータから、そのデータを構成する複数のチャンクを取得する。
なお、指定されたデータのサイズが４Ｋバイト以下の場合、分割部３００は、当該データ
自体を１つのチャンクとして取得する。ここで、チャンクのサイズは固定長である必要は
なく、チャンクのサイズは可変長であっても構わない。
【００４４】
重複管理部３０１は、取得されたチャンクの数を変数Ｎに設定する（Ｓ２）。ここで、
取得されたＮ個のチャンクをチャンクＣ＿１ないしＣ＿Ｎと表記する。
【００４５】
すると重複管理部３０１は、ステップＳ１で取得されたＮ個のチャンクの１つを指定す
るのに用いられる変数ｎを初期値１に設定する（Ｓ３）。続いてハッシュ生成部３０３は
、ｎ番目のチャンクＣ＿ｎのハッシュ値Ｈｎ（Ｃ＿ｎ）を計算する（Ｓ４）。つまり初期
値ｎ＝１であるので、１番目のチャンクＣ＿１のハッシュ値Ｈ１（Ｃ＿１）を計算する。
また、ハッシュ値計算は、例えば“ＳＨＡ−２５６”と呼ばれるハッシュ関数を用いて計
算する。さらに、本実施形態では、ハッシュ値Ｈ１（Ｃ＿１）乃至Ｈ１（Ｃ＿Ｎ）は、そ
れぞれ３２バイトで表される。
【００４６】
次に、重複管理部３０１は、ステップＳ４でハッシュ値計算された、ｎ番目のチャンク
Ｃ＿ｎのハッシュ値Ｈｎ（Ｃ＿ｎ）に一致するハッシュ値をハッシュテーブル２１３aか
ら探索するためのハッシュ値探索処理を実行する（Ｓ５）。このハッシュ値探索処理の結
果に基づいて、選択されたチャンクＣ＿ｎのハッシュ値Ｈｎ（Ｃ＿ｎ）に一致するハッシ
ュ値がハッシュテーブル２１３aに存在するかを判定する（Ｓ６）。
【００４７】
重複管理部３０１は、この重複判定部３０２による判定の結果に基づいて、ステップＳ
７またはステップＳ１４に進む。
【００４８】
選択されたチャンクＣ＿ｎのハッシュ値Ｈｎ（Ｃ＿ｎ）に一致するハッシュ値が存在し
ない場合（Ｓ６のＮｏ）を説明する。この場合、重複管理部３０１は、チャンクＣ＿ｎと
同一内容を持つチャンクは格納されていないと判断する。
【００４９】
ステップＳ７おいて重複管理部３０１は、チャンクＣ＿ｎにチャンク番号ＣＮＣ＿ｎを付
与する。次に、アクセスコントローラ３０４は、当該チャンクＣ＿ｎをRAIDディスクアレ
イ２３０内の空いている記憶領域に書き込む（Ｓ８）。
【００５０】
続いて、重複管理部３０１は、選択されたチャンクＣ＿ｎの論理ボリューム内の位置を
示す論理アドレスを取得する。この論理アドレスは、ホスト１００からのデータ書き込み
要求で指定される論理アドレスに４Ｋを加算することにより取得される。重複管理部３０
１は更に、取得された論理アドレスに対応付けられているメタテーブル２３０aのエント
リに、選択されたチャンクＣ＿ｎに付与されたチャンク番号ＣＮＣ＿ｎを登録する（Ｓ９
）。
【００５１】
また、重複管理部３０１は、チャンクＣ＿ｎのチャンク番号ＣＮＣ＿ｎに対応付けられ
たチャンクテーブル２３０ｂのチャンク番号ＣＮＣ＿ｎのエントリに、チャンクＣ＿ｎが
書き込まれたRAIDディスクアレイ２３０内の記憶領域の物理アドレスPＣ＿ｎを登録する
。さらに、重複管理部３０１は、チャンクテーブル２３０ｂにおいて、チャンク番号ＣＮ
Ｃ＿ｎに対応するエントリの重複数に１を設定する（Ｓ１０)。
【００５２】
続いて、重複管理部３０１は、ハッシュテーブル２１３aに、チャンクＣ＿ｎのチャン
ク番号CNC_ｎおよびハッシュ値Ｈｎ（Ｃ−ｎ）を登録する。この時、ハッシュテーブル２
１３aに空きエントリが少ない場合は、ハッシュテーブル２１３a最下段のエントリ（つま
り、ヒットカウンタに格納された値が最小のエントリ）を削除し、チャンクＣ＿ｎのエン
トリを登録する（詳細は後述する）。また重複管理部３０１は、ハッシュテーブル２１３
aにおいて、チャンク番号CNC_ｎに対応するエントリの参照ビットをビット”１”に設定
する（Ｓ１１）。
【００５３】
次に、変数ｎがチャンク数Nを超えているかを判定する。もし、変数ｎがチャンク数Ｎ
を超えていないならば（Ｓ１２のＮｏ）、重複管理部３０１は、ホスト１００からのデー
タ書き込み要求によって指定されたデータに含まれている次のチャンクの書き込みを処理
するために、変数ｎを１インクリメントし（Ｓ１３）、ステップＳ４に戻る。これに対し
て変数ｎがチャンク数Ｎを超えているならば（Ｓ１２のＹｅｓ）、重複管理部３０１は、
ホスト１００からのデータ書き込み要求によって指定されたデータに含まれている全ての
チャンクの書き込みを終了したと判定する。この場合、データ書き込み処理は終了する。
【００５４】
次に、チャンクＣ＿ｎのハッシュ値Ｈｎ（Ｃ＿ｎ）に一致するハッシュ値が存在する場
合、つまり重複判定部３０２がステップＳ６においてＹｅｓと判定した場合の動作を説明
する。重複管理部３０１は、選択されたチャンクＣ＿ｎと同一内容を持つチャンクが既に
RAIDディスクアレイ２３０に格納されていると判定する。ここで、RAIDディスクアレイ２
３０に既に格納されていて、かつチャンクＣ＿ｎと同一内容を持つチャンクをチャンクＣ
＿ｘと表記する。このとき、チャンクＣ＿ｎのチャンク番号としてチャンクＣ＿ｘのチャ
ンク番号CNＣ＿ｘが用いられる。
【００５５】
この場合、同一内容を持つ複数のチャンクが重複してRAIDディスクアレイ２３０に格納
されるのを排除するため、アクセスコントローラ３０４は、選択されたチャンクＣ＿ｎを
RAIDディスクアレイ２３０に書き込む動作を抑止する（Ｓ１４）。
【００５６】
続いて重複管理部３０１は、選択されたチャンクＣ＿ｎのチャンク番号CNＣ＿ｘに対応
付けられたチャンクテーブル２３０ｂのエントリ情報を更新する（Ｓ１５）。具体的には
、エントリの重複数を１増やす。
【００５７】
次に、重複管理部３０１は、メタテーブル２３０aのチャンクＣ＿ｎが書き込まれるべ
き論理アドレスに対応付けられたエントリにチャンクＣ＿ｎと同一内容を持ち既にRAIDデ
ィスクアレイ２３０に書き込まれているチャンクＣ＿ｘのチャンク番号CNＣ＿ｘを登録す
る（S１６）。
【００５８】
続いて、重複管理部３０１は、チャンクＣ＿ｎのチャンク番号CNＣ＿ｘに対応付けられ
たハッシュテーブル２１３aのエントリ情報を更新する（Ｓ１７)。参照ビット欄にビット
”０”が格納されていれば、ビット”１”に更新しフラグを立てる。既に、ビット”１”
が格納されフラグが立っていれば、そのままにする。その後、処理をステップＳ１２へ進
める。
【００５９】
（リード処理時の動作）
次に、本実施形態における、ストレージ装置２００のディスクアレイ制御装置２１０が
ホスト１００からデータ読み込み要求を受信した場合に実行されるリード処理時の動作に
ついて、図８を参照して説明する。
【００６０】
アクセスコントローラ３０４は、ホスト１００から受信したデータの読み出し要求で指
定されたデータの先頭の論理アドレスとデータ長（セクタ数）に基づいて、ディスクアレ
イ２３０からデータを読み出してローカルメモリ２１６のワーク領域２１６ｃに設けたリ
ードバッファに保存する（Ｓ２０）。このデータの読み出しに際して、読み出しデータを
構成する各チャンクが記録されている物理アドレスは次のようにして求めることができる
。即ち、先頭の論理アドレスに順次チャンクを構成するセクタ数（８セクタ＝４ＫＢ）を
加算することで、読み出しデータを構成する各チャンクの論理アドレスを特定する。この
特定された論理アドレスに基づいてメタテーブル２３０aを参照すれば、その論理アドレ
スに記録されているチャンクのチャンク番号が特定できる。さらに、この特定されたチャ
ンク番号に基づいてチャンクテーブル２３０ｂを参照すれば、各チャンクが記録されてい
る物理アドレスが特定できる。
【００６１】
次に、アクセスコントローラ３０４は、ローカルメモリ２１６のリードバッファに保存
したデータを読み出し、ホスト１００へ転送する（Ｓ２１）。
【００６２】
データを転送後、ディスクアレイ制御装置２１０の分割部３００は、転送されたデータ
を複数のチャンクに分割する（Ｓ２２）。重複管理部３０１は、取得されたチャンクの数
を変数Ｎに設定する（Ｓ２３）。
【００６３】
続いて、重複管理部３０１は、ステップＳ２３で取得されたＮ個のチャンクの１つを指
定するのに用いられる変数ｎを初期値１に設定する（Ｓ２４）。次に、ハッシュ生成部３
０３は、チャンクＣ＿ｎのハッシュ値、Ｈｎ（Ｃ＿ｎ）を計算する（Ｓ２５）。つまり初
期値ｎ＝１であるので、１番目のチャンクＣ＿１のハッシュ値Ｈ１（Ｃ＿１）を計算する
。
【００６４】
続いて、重複管理部３０１は、ステップＳ２５でハッシュ値計算されたチャンクＣ＿ｎ
のハッシュ値Ｈｎ（Ｃ＿ｎ）に一致するハッシュ値をハッシュテーブル２１３aから探索
するためのハッシュ値探索処理を実行する（Ｓ２６）。このハッシュ値探索処理の結果に
基づいて、選択されたチャンクＣ＿ｎのハッシュ値Ｈｎ（Ｃ＿ｎ）に一致するハッシュ値
がハッシュテーブル２１３aに存在するかを判定する（Ｓ２７）。
【００６５】
重複管理部３０１は、この重複判定部３０２による判定の結果に基づいて、ステップＳ
２８またはステップＳ２９に進む。
【００６６】
チャンクＣ＿ｎのハッシュ値Ｈｎ（Ｃ＿ｎ）に一致するハッシュ値が存在しない場合（
Ｓ２７のＮｏ）、重複管理部３０１は、チャンクＣ＿ｎに対応するチャンク番号ＣNC＿ｎ
のエントリが、ハッシュテーブル２１３aに保持されていないと判断する。続いて、重複
管理部３０１は、チャンクＣ＿ｎのハッシュ値Ｈｎ（Ｃ＿ｎ）をチャンク番号ＣNC＿ｎに
対応付けてハッシュテーブル２１３aに登録する（Ｓ２８）。この時、ハッシュテーブル
２１３aの空きエントリが少ない場合は、ハッシュテーブル２１３a最下段のエントリ（つ
まり、ヒットカウンタに格納された値が最小のエントリ）を削除し、チャンクＣ＿ｎのエ
ントリを登録する（詳細は後述する）。また、対応するエントリの参照ビットをビット”
１”に設定する。
【００６７】
チャンクＣ＿ｎのハッシュ値Ｈｎ（Ｃ＿ｎ）に一致するハッシュ値が存在し、重複判定
部３０２がステップＳ２７においてＹｅｓと判定した場合、重複管理部３０１は、ハッシ
ュ値がＨｎ（Ｃ＿ｎ）であるハッシュテーブル２１３aのエントリを更新する（Ｓ２９）
。重複管理部３０１は、ハッシュ値がＨｎ（Ｃ＿ｎ）であるハッシュテーブル２１３aの
エントリに参照ビット“１”をセットする。
【００６８】
重複管理部３０１は、変数ｎがステップＳ２３で設定されたチャンク数Ｎを超えている
かを判定する（Ｓ３０）。もし、変数ｎがチャンク数Ｎを超えていないならば（Ｓ３０の
Ｎｏ）、重複管理部３０１は、ホスト１００から指定されたデータに含まれている次のチ
ャンクを処理するために、変数ｎを１インクリメントし（Ｓ３１）、ステップＳ２５に戻
る。これに対して変数ｎがチャンク数Ｎを超えているならば（Ｓ３０のＹｅｓ）、重複管
理部３０１は、全てのチャンクの処理を終了したと判定する。
【００６９】
このように本実施形態において、新規のハッシュテーブルのエントリの登録をライト処
理時だけでなくリード処理完了時にも行う。これにより、ハッシュテーブルの記憶容量が
固定値となっているがために、RAIDディスクアレイ２３０に書き込まれている全てのチャ
ンクに対応するエントリを登録できない場合にも、重複排除をより効率的に実現できる。
【００７０】
即ち、あるチャンクを書き込みする場合に、既にそのチャンクと同一内容のチRAIDディ
スクアレイ２３０に書き込まれているにも関わらず、ハッシュテーブルが固定長であるこ
とに起因して、この既に書き込まれているチャンクに対応するエントリがハッシュテーブ
ルに登録されていないケースが想定される。この場合には、ハッシュテーブルにエントリ
が登録されていないため、重複排除ができない。しかし、リード処理時にもハッシュテー
ブルへのエントリ登録を行うことで、重複排除をすることができる。例えば、ホスト１０
０がRAIDディスクアレイ２３０からデータを読み出す目的として、そのデータに別のデー
タ名を付けてデータをコピーする場合や、その読み出したデータを更新して再度書き込み
する場合が想定される。このような場合にリード処理時にもハッシュテーブルへのエント
リの登録を行うことで、ハッシュテーブルにエントリが登録されていないため発生する重
複排除ができない事態を回避することができる。
【００７１】
（ハッシュエントリの置換）
ハッシュテーブル２１３ａの記憶容量が固定長であるため、空きのエントリがなくなっ
た場合の対策について説明する。空きのエントリがなくなった場合には、ヒットカウンタ
の値が最小のエントリを選択し、そのエントリに記録されているチャンク番号、ハッシュ
値、参照ビット、ビットカウンタの各記録内容を削除し、新たに登録するチャンク番号、
ハッシュ値、参照ビット、ビットカウンタの値を記録することで置換する。この置換処理
を円滑に進めるために、あらかじめ、定期的にハッシュテーブル２１３ａに記録されてい
るエントリをヒットカウンタの値に基づいてソート処理しておく。このように定期的にソ
ート処理することをエージング周期処理と呼び、その詳細を図９を参照して説明する。な
お、周期処理は、例えばOSが提供するタイマー機能等を利用し任意時間周期で行う。
【００７２】
まず、重複管理部３０１は、ハッシュテーブル２１３aの先頭のエントリを選択する（
Ｓ３２）。本実施形態では、例えば一番上にあるエントリから選択する。続いて重複管理
部３０１は、ヒットカウンタを1ビット右シフトする（２で割る）（Ｓ３３）。本実施形
態のヒットカウンタは８ビットで形成されているとし、例えば当該エントリのヒットカウ
ンタに「10000000（１６進数：８０）」が格納されているとする。１ビット右シフトする
ことで、ヒットカウンタの値は「01000000（１６進数：４０）」となる。
【００７３】
次に重複管理部３０１は、当該エントリの参照ビット“１”が立っているか判定する（
Ｓ３４）。例えば、ステップＳ３３の後に、当該エントリのヒットカウンタの値が「0100
0000（１６進数：４０）」である場合を考える。参照ビット“１”が立っている場合、さ
らに最上位ビットを立て（Ｓ３５）、ヒットカウンタの値は「11000000（１６進数：Ｃ０
）」となる。参照ビット“０”の場合、ヒットカウンタの値はそのまま「01000000（１６
進数：４０）」とし、Ｓ３６に進む。このように、ステップＳ３３の処理の後に、ステッ
プＳ３４またはステップＳ３５の処理をすることによって、直近にアクセス（参照）され
たチャンクのヒットカウンタの値が増大されることになる。一方、直近にアクセス（参照
）されていないチャンクのヒットカウンタの値は減少されることになる。このようにヒッ
トカウンタの値を変更することによって、アクセス回数は少ないチャンクでも、直近にア
クセスされているものは、そのヒットカウンタの値が大きく設定されるため、高い優先順
位を持つことになる。
【００７４】
続いて重複管理部３０１は、全てのエントリの処理を行ったか判定する（Ｓ３６）。全
てのエントリの処理を行っていないと判断した場合（Ｓ３６のNo）は、次のエントリを選
択し（Ｓ３７）、ステップＳ３３に戻る。全てのエントリの処理を行っていると判断した
場合（Ｓ３６のNo）は、全エントリをソートし、ヒットカウンタの値が昇順になる位置に
動かし（Ｓ３８）、エージング周期処理は終了となる。
【００７５】
このエージング周期処理が行われることにより、ハッシュテーブル２１３a内のエント
リの優先順位が付けられる。その優先順位に則り、エントリの空き領域がなくなった場合
には、ハッシュテーブル２１３aの一番下のエントリ（つまり、ヒットカウンタの値が最
小のエントリ）を選択し、そのエントリに記録されているチャンク番号、ハッシュ値、参
照ビット、ビットカウンタの各記録内容を削除し、新たに登録するチャンク番号、ハッシ
ュ値、参照ビット、ビットカウンタの値を記録することで置換する。
【００７６】
なお、ハッシュテーブル２１３aはキャッシュメモリ２１３上にのみ存在するため、装
置停止で揮発してしまうが、装置シャットダウン時にはHDDやSSDのような不揮発媒体に退
避し、起動時に復元する。
【００７７】
このように、本実施形態は、ハッシュエントリを一定量のみキャッシュメモリ２１３上
に保持し、アクセス数とアクセス間隔に基づいて重み付けしたヒットカウンタによりハッ
シュエントリを管理する。また、リード処理時にもハッシュエントリを登録する。それに
より、高速で高重複排除率の重複排除機能を実現することができる。
【００７８】
以上、本発明の実施形態を説明したが、これらの実施形態は、例として提示したもので
あり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の
様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略
、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨
に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００７９】
１００…ホスト
１１０…ネットワーク
２００…ストレージ装置
２１０…ディスクアレイ制御装置
２１１…ホストＩ／Ｆ
２１２…ディスクＩ／Ｆ
２１３…キャッシュメモリ
２１３a…ハッシュテーブル
２１４…キャッシュコントローラ
２１５…FROM
２１６…ローカルメモリ
２１６a…制御プログラム領域
２１６b…テーブル領域
２１６c…ワーク領域
２１７…CPU
２１８…チップセット
２２０…ディスクインタフェースバス
２３０…RAIDディスクアレイ
２３０a…メタテーブル
２３０ｂ…チャンクテーブル
３００…分割部
３０１…重複管理部
３０２…重複判定部
３０３…ハッシュ生成部
３０４…アクセスコントローラ
【図１】
2018185760.tif 000003
【図２】
2018185760.tif 000004
【図３】
2018185760.tif 000005
【図４】
2018185760.tif 000006
【図５】
2018185760.tif 000007
【図６】
2018185760.tif 000008
【図７】
2018185760.tif 000009
【図８】
2018185760.tif 000010
【図９】
2018185760.tif 000011