(57)【要約】【課題】記憶消費容量の節約を図る。【解決手段】データ処理装置１は、記憶部１ａと制御部１ｂを備える。記憶部１ａは、データの識別情報を格納する複数の記憶領域を有する。制御部１ｂは、識別情報の参照頻度にもとづいて識別情報を異なる縮約度で縮約し、複数の記憶領域のうち、対応する記憶領域に縮約後の識別情報を格納する。この場合、制御部１ｂは、識別情報の参照頻度にもとづいて識別情報を縮約し、参照頻度に応じて記憶部１ａの記憶領域を複数に分割して分割領域を生成し、識別情報を構成する全データビットまたは縮約後のデータビットを分割領域に格納する。また、制御部１ｂは、参照頻度にランクを設けて複数の分割領域に対応づけ、ランクが下がるほど識別情報のデータビットの縮約度が増える縮約データをランク毎の分割領域に格納する。【選択図】図１
2020057305.tif 000002
【特許請求の範囲】
【請求項１】
データの識別情報を格納する複数の記憶領域を有する記憶部と、
前記識別情報の参照頻度にもとづいて前記識別情報を異なる縮約度で縮約し、前記複数の記憶領域のうち、対応する記憶領域に縮約後の識別情報を格納する制御部と、
を有するデータ処理装置。
【請求項２】
前記識別情報を、参照頻度別、縮約度別、もしくは前記識別情報のインデックス別のいずれかの条件でグループ化し、
前記制御部は、前記複数の記憶領域のうち、前記識別情報が属するグループに対応付けられた記憶領域に、前記縮約後の識別情報を格納する、
請求項１記載のデータ処理装置。
【請求項３】
前記複数の記憶領域は、
非縮約の前記識別情報の全データビットを非縮約データとして格納する第１の記憶領域と、
前記識別情報の全データビットのうちｎビットを削減した縮約データを格納する第２の記憶領域を含み、
前記制御部は、
処理対象の対象識別情報が前記非縮約データおよび前記縮約データに対して不一致となる場合、前記第１の記憶領域に格納されている前記非縮約データのうち第１のデータを抽出し、抽出した前記第１のデータのｎビットを削除して第２のデータを生成し、前記第２のデータを前記縮約データとして前記第２の記憶領域に格納し、
前記対象識別情報の全データビットを前記非縮約データとして前記第１の記憶領域に格納する、
請求項１記載のデータ処理装置。
【請求項４】
前記複数の記憶領域は、
非縮約の前記識別情報の全データビットを非縮約データとして格納する第１の記憶領域と、
前記識別情報の全データビットのうちｎビットを削減した縮約データを格納する第２の記憶領域と、を含み、
前記制御部は、
処理対象の対象識別情報のうちの所定データビットが前記縮約データに一致する場合、前記第１の記憶領域に格納される前記非縮約データのうち第１のデータを抽出し、抽出した前記第１のデータのｎビットを削除して第２のデータを生成し、前記第２のデータを前記縮約データとして前記第２の記憶領域に格納し、
前記所定データビットに一致した前記縮約データに対してｎビットの拡張を行って拡張データを生成し、前記拡張データを前記非縮約データとして前記第１の記憶領域に格納する、
請求項１記載のデータ処理装置。
【請求項５】
前記複数の記憶領域は、
前記識別情報のデータビットのうちｎビットを削減した第１の縮約データを第１の記憶領域と、
前記識別情報のデータビットのうちｍ（＞ｎ）ビットを削減した第２の縮約データを第２の記憶領域と、を含み、
前記制御部は、
処理対象の対象識別情報のうちの所定データビットが前記第２の縮約データに一致する場合、前記第１の記憶領域に格納されている前記第１の縮約データのうち第１のデータを抽出し、抽出した前記第１のデータのｍビットを削除して第２のデータを生成し、前記第２のデータを前記第２の縮約データとして前記第２の記憶領域に格納し、
前記所定データビットに一致した前記第２の縮約データに対してｍビットの拡張を行って拡張データを生成し、前記拡張データを前記第１の縮約データとして前記第１の記憶領域に格納する、
請求項１記載のデータ処理装置。
【請求項６】
前記制御部は、外部記憶装置に格納されている前記識別情報の全データビットにもとづいて、縮約データのビット拡張を行う請求項４または５に記載のデータ処理装置。
【請求項７】
データの識別情報の参照頻度にもとづいて前記識別情報を異なる縮約度で縮約し、
前記識別情報を格納する複数の記憶領域のうち、対応する記憶領域に縮約後の識別情報を格納する、
処理をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理装置およびプログラムに関する。
【背景技術】
【０００２】
ストレージシステムは、ＨＤＤ（Hard Disk Drive）やＳＳＤ（Solid State Drive）等の記憶装置と、記憶装置を制御するためのコントローラとを有して、情報処理で扱う大量のデータを記録管理する。
【０００３】
また、ストレージシステムには、バックアップ等を行う際に、重複データを検出して排除する重複排除（De-duplication）機能が備えられている。
重複排除機能は、データをブロックに分割し、ブロックそれぞれにフィンガープリント（Fingerprint）と呼ばれる識別情報を割り当てる。フィンガープリントが一致すれば、ブロックは同一のものと見なして重複データブロックは排除され、フィンガープリントが不一致となる一意のデータブロックのみが記憶装置に格納される。このような機能によりデータの冗長性を解消することができる。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２０１５−２０１０５０号公報
【特許文献２】特開昭６２−１０８３４２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ストレージに蓄積されるデータの増加に伴って、生成されるフィンガープリントも増加する。しかし、フィンガープリントの生成数が多くなるほど、フィンガープリントを格納しておくメモリ容量が増加し、メモリ資源が圧迫されてしまう。
【０００６】
１つの側面では、本発明は、フィンガープリントの格納時におけるメモリの効率的な活用を行ってメモリ消費容量の節約を可能にしたデータ処理装置およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００７】
上記課題を解決するために、データ処理装置が提供される。データ処理装置は、データの識別情報を格納する複数の記憶領域を有する記憶部と、識別情報の参照頻度にもとづいて識別情報を異なる縮約度で縮約し、複数の記憶領域のうち、対応する記憶領域に縮約後の識別情報を格納する制御部とを有する。
【０００８】
また、上記課題を解決するために、コンピュータに上記データ処理装置と同様の制御を実行させるプログラムが提供される。
【発明の効果】
【０００９】
１側面によれば、記憶消費容量の節約が可能になる。
【図面の簡単な説明】
【００１０】
【図１】データ処理装置の一例を説明するための図である。
【図２】ストレージシステムの構成の一例を示す図である。
【図３】ＣＭのハードウェア構成の一例を示す図である。
【図４】制御部の機能ブロックの一例を示す図である。
【図５】重複排除の動作の一例を説明するための図である。
【図６】フィンガープリントの管理の一例を示す図である。
【図７】フィンガープリントの管理の一例を示す図である。
【図８】フィンガープリントの検索の一例を示すフローチャートである。
【図９】フィンガープリント管理リストの一例を示す図である。
【図１０】キャッシュ領域の分割の一例を示す図である。
【図１１】フィンガープリントの管理制御の一例を示すフローチャートである。
【図１２】フィンガープリントの検索処理の一例を示すフローチャートである。
【図１３】新規フィンガープリントの格納処理の一例を示すフローチャートである。
【図１４】フィンガープリントのランク更新処理の一例を示す図である。
【図１５】新規フィンガープリントの格納処理の一例を示す図である。
【図１６】フィンガープリントのランク更新処理の一例を示す図である。
【図１７】フィンガープリントのランク更新処理の一例を示す図である。
【図１８】キャッシュ容量の決定手順の一例を示すフローチャートである。
【発明を実施するための形態】
【００１１】
以下、本実施の形態について図面を参照して説明する。
［第１の実施の形態］
第１の実施の形態について図１を用いて説明する。図１はデータ処理装置の一例を説明するための図である。データ処理装置１は、記憶部１ａと制御部１ｂを備える。
【００１２】
記憶部１ａは、データの識別情報を格納する複数の記憶領域を有する。制御部１ｂは、識別情報の参照頻度にもとづいて識別情報の参照頻度にもとづいて識別情報を異なる縮約度で縮約し、複数の記憶領域のうち、対応する記憶領域に縮約後の識別情報を格納する。
【００１３】
例えば、制御部１ｂは、識別情報の参照頻度にもとづいて識別情報を縮約し、参照頻度に応じて記憶部１ａの記憶領域を複数に分割して分割領域を生成する。そして、制御部１ｂは、識別情報を構成する全データビットまたは縮約後のデータビットを分割領域に格納する。
【００１４】
この場合、制御部１ｂは、参照頻度にランクを設けて複数の分割領域に対応づけ、ランクが下がるほど識別情報のデータビットの縮約度が増える縮約データをランク毎の分割領域に格納する。
【００１５】
図１に示す例を用いて動作について説明する。
〔ステップＳ１〕制御部１ｂは、データａ０を受信すると、データａ０を識別するための識別情報ａ１を生成する。例えば、データ処理装置１がデータａ０の重複排除判定を行う場合、識別情報ａ１はフィンガープリントに該当する。
【００１６】
〔ステップＳ２〕制御部１ｂは、識別情報ａ１の参照頻度を複数のランク＃１、・・・、＃ｎに分ける。例えば、ランク＃１は識別情報ａ１の参照頻度が最も高く、ランク＃ｎは識別情報ａ１の参照頻度が最も低いとする。
【００１７】
〔ステップＳ３〕制御部１ｂは、ランクが下がるほど識別情報ａ１のデータビットの縮約度が増える縮約データを生成する。この場合、制御部１ｂは、参照頻度が最も高いランク＃１に対しては、識別情報ａ１のデータビットの縮約は行わない。
【００１８】
また、制御部１ｂは、ランク＃２に対しては、識別情報ａ１のデータビットの縮約を行って縮約データａ２を生成し、ランク＃３に対しては、識別情報ａ１のデータビットにランク＃２よりも縮約度の高い縮約を行って縮約データａ３を生成する。
【００１９】
同様にして、制御部１ｂは、ランク＃ｎの場合、識別情報ａ１のデータビットにランク＃（ｎ−１）よりも縮約度の高い縮約を行って縮約データａｎを生成する。
〔ステップＳ４〕制御部１ｂは、記憶部１ａの記憶領域を分割し、分割領域ｒ１、・・・、ｒｎにランク＃１、・・・、＃ｎを対応づける。
【００２０】
〔ステップＳ５〕制御部１ｂは、ステップＳ３で処理した識別情報を分割領域ｒ１、・・・、ｒｎに格納する。すなわち、分割領域ｒ１には識別情報ａ１が格納され、分割領域ｒ２には識別情報ａ１の縮約データａ２が格納される。同様に、分割領域ｒｎには、識別情報ａ１の縮約データａｎが格納される。
【００２１】
このように、データ処理装置１では、データの識別情報を記憶する記憶部において、識別情報のデータビットを参照頻度のランクにもとづいて縮約し、縮約した識別情報をランク毎に分割した分割領域に格納して識別情報の管理を行う。このような管理制御により、データ処理装置１は、識別情報の生成数が増加しても、参照頻度に応じた縮約を行って記憶部に格納するため、記憶部の消費容量の節約を図ることが可能になる。
【００２２】
［第２の実施の形態］
次に第２の実施の形態について説明する。第２の実施の形態は、データ処理装置１の機能をストレージシステムに適用したものである。
【００２３】
図２はストレージシステムの構成の一例を示す図である。ストレージシステム１−１は、ストレージ装置１０ａとホスト３を備える。ストレージ装置１０ａは、２台以上の冗長化されたＣＭ（Controller Module）１０−１、・・・、１０−ｎ（総称する場合はＣＭ１０）と、ＤＥ（Disc Enclosure）２を備える。ストレージシステム１−１は、例えば、記憶装置を多重化したＲＡＩＤ（Redundant Array of Inexpensive Disks）システムである。
【００２４】
ＣＭ１０は、制御部１１、メモリ１２、ＣＡ（Channel Adapter）１３ａ、１３ｂおよびＤＩ（Disk Interface）１４ａ、１４ｂを含む。ＤＥ２は、記憶装置２０−１、・・・、２０−ｎ（総称する場合は記憶装置２０）を含む。制御部１１は、図１の制御部１ｂに対応し、メモリ１２は、図１の記憶部１ａに対応する。なお、以降ではメモリ１２の領域をキャッシュ、記憶装置２０の領域をディスクと呼ぶ場合がある。
【００２５】
制御部１１は、例えば、ＣＰＵ（Central Processing Unit）であり、ホスト３からのデータ読み出し（Read IO）およびデータ書き込み（Write IO）の要求にもとづいて、記憶装置２０−１、・・・、２０−ｎに対してＩ／Ｏ制御を行う。
【００２６】
メモリ１２は、記憶装置２０−１、・・・、２０−ｎを制御するためのデータを制御部１１と授受するためのキャッシュメモリであって、例えば、ＤＲＡＭ（Dynamic Random Access Memory）等の揮発性の記憶デバイスが使用される。メモリ１２には、フィンガープリントや制御情報等も格納される。
【００２７】
ＣＡ１３ａ、１３ｂは、ホスト３に対するインタフェース制御を行う。ＤＩ１４ａ、１４ｂは、記憶装置２０−１、・・・、２０−ｎに対するインタフェース制御を行う。
記憶装置２０−１、・・・、２０−ｎは、例えば、ＨＤＤまたはＳＳＤであり、ディスクアレイ化されて、ＣＭ１０からＩ／Ｏ制御が行われるデータや制御情報およびフィンガープリント等を格納する。
【００２８】
＜ハードウェア＞
図３はＣＭのハードウェア構成の一例を示す図である。ＣＭ１０は、プロセッサ（コンピュータ）１００によって装置全体が制御されている。プロセッサ１００は、図２に示した、制御部１１の機能を実現する。
【００２９】
プロセッサ１００には、バス１０３を介して、メモリ１０１および複数の周辺機器が接続されている。プロセッサ１００は、マルチプロセッサであってもよい。プロセッサ１００は、例えば、ＣＰＵ、ＭＰＵ（Micro Processing Unit）、ＤＳＰ（Digital Signal Processor）、ＡＳＩＣ（Application Specific Integrated Circuit）、またはＰＬＤ（Programmable Logic Device）である。またプロセッサ１００は、ＣＰＵ、ＭＰＵ、ＤＳＰ、ＡＳＩＣ、ＰＬＤのうちの２以上の要素の組み合わせであってもよい。
【００３０】
メモリ１０１は、ＣＭ１０の主記憶装置として使用される。メモリ１０１には、プロセッサ１００に実行させるＯＳのプログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。また、メモリ１０１には、プロセッサ１００による処理に要する各種データが格納される。
【００３１】
また、メモリ１０１は、ＣＭ１０の補助記憶装置としても使用され、ＯＳのプログラム、アプリケーションプログラム、および各種データが格納される。メモリ１０１は、補助記憶装置として、フラッシュメモリやＳＳＤ等の半導体記憶装置やＨＤＤ等の磁気記録媒体を含んでもよい。なお、メモリ１０１は、図２に示した、メモリ１２の機能を実現する。
【００３２】
バス１０３に接続されている周辺機器としては、入出力インタフェース１０２、ネットワークインタフェース１０４およびストレージインタフェース１０５がある。入出力インタフェース１０２は、プロセッサ１００からの命令にしたがってＣＭ１０の状態を表示する表示装置として機能するモニタ（例えば、ＬＥＤ（Light Emitting Diode）やＬＣＤ（Liquid Crystal Display）等）が接続されている。
【００３３】
また、入出力インタフェース１０２は、キーボードやマウス等の情報入力装置を接続可能であって、情報入力装置から送られてくる信号をプロセッサ１００に送信する。
さらに、入出力インタフェース１０２は、周辺機器を接続するための通信インタフェースとしても機能する。例えば、入出力インタフェース１０２は、レーザ光等を利用して、光ディスクに記録されたデータの読み取りを行う光学ドライブ装置を接続することができる。光ディスクには、Ｂｌｕ−ｒａｙＤｉｓｃ（登録商標）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（Rewritable）等がある。
【００３４】
また、入出力インタフェース１０２は、メモリ装置やメモリリーダライタを接続することができる。メモリ装置は、入出力インタフェース１０２との通信機能を搭載した記録媒体である。メモリリーダライタは、メモリカードへのデータの書き込み、またはメモリカードからのデータの読み出しを行う装置である。メモリカードは、カード型の記録媒体である。
【００３５】
ネットワークインタフェース１０４は、図２に示したＣＡ１３ａ、１３ｂの機能を実現し、ホスト３に接続される。また、ネットワークインタフェース１０４は、他の外部ネットワークとのインタフェース制御が可能であり、例えば、ＮＩＣ（Network Interface Card）、無線ＬＡＮ（Local Area Network）カード等を使用することもできる。ネットワークインタフェース１０４で受信されたデータは、メモリ１０１やプロセッサ１００に出力される。
【００３６】
ストレージインタフェース１０５は、図２に示したＤＩ１４ａ、１４ｂの機能を実現し、ＣＭ１０とＤＥ２との接続を行う拡張デバイスとして、ＤＥ２とのインタフェース制御を行う。
【００３７】
以上のようなハードウェア構成によって、ＣＭ１０の処理機能を実現することができる。例えば、ＣＭ１０は、プロセッサ１００がそれぞれ所定のプログラムを実行することで本発明の制御を行うことができる。
【００３８】
ＣＭ１０は、例えば、コンピュータで読み取り可能な記録媒体に記録されたプログラムを実行することにより、本発明の処理機能を実現する。ＣＭ１０に実行させる処理内容を記述したプログラムは、様々な記録媒体に記録しておくことができる。
【００３９】
例えば、ＣＭ１０に実行させるプログラムを補助記憶装置に格納しておくことができる。プロセッサ１００は、補助記憶装置内のプログラムの少なくとも一部を主記憶装置にロードし、プログラムを実行する。
【００４０】
また、光ディスク、メモリ装置、メモリカード等の可搬型記録媒体に記録しておくこともできる。可搬型記録媒体に格納されたプログラムは、例えば、プロセッサ１００からの制御により、補助記憶装置にインストールされた後、実行可能となる。またプロセッサ１００が、可搬型記録媒体から直接プログラムを読み出して実行することもできる。
【００４１】
＜機能ブロック＞
図４は制御部の機能ブロックの一例を示す図である。ＣＭ１０の制御部１１は、フィンガープリント管理部１１ａおよび重複排除処理部１１ｂを含む。フィンガープリント管理部１１ａは、フィンガープリント生成部１１ａ１、ランク分け処理部１１ａ２、縮約処理部１１ａ３、格納処理部１１ａ４を含む。重複排除処理部１１ｂは、判定部１１ｂ１およびランク更新処理部１１ｂ２を含む。
【００４２】
フィンガープリント生成部１１ａ１は、受信した書き込みデータのフィンガープリントを生成する。フィンガープリントは、データから算出されるハッシュ値である。ランク分け処理部１１ａ２は、フィンガープリントの参照頻度にもとづいて、フィンガープリントのランク分けを行う。
【００４３】
縮約処理部１１ａ３は、ランクにもとづいて、フィンガープリントの縮約を行う。例えば、フィンガープリントのデータビットから所定ビットを削減するなどして縮約を行う。格納処理部１１ａ４は、非縮約のフィンガープリントおよび縮約後のフィンガープリントを、メモリ１２内のランク毎の分割領域に格納する。
【００４４】
また、格納処理部１１ａ４は、フィンガープリントをグループ単位で分けた際のグループ毎のフィンガープリント管理リスト（後述）を作成して、メモリ１２に該リストの構造を持つデータを格納し、リスト内の属性情報の更新を行う。
【００４５】
判定部１１ｂ１は、重複排除の検索対象のフィンガープリントである対象フィンガープリントと、分割領域に格納されるフィンガープリントとが一致するか否かの判定を行う。判定部１１ｂ１は、すべての分割領域に格納されるフィンガープリントに一致しない場合、対象フィンガープリントに対応するデータを記憶装置２０に書き込む。フィンガープリントに一致するデータは、重複排除される。
【００４６】
ランク更新処理部１１ｂ２は、対象フィンガープリントの重複排除の判定結果にもとづいて、すでに分割領域に格納されているフィンガープリントのビット拡張またはビット削減を行ってランク更新（ランクアップ／ランクダウン）処理を行う（ランク更新については後述）。
【００４７】
メモリ１２は、Ｉ／Ｏデータ、ストレージ制御に関する制御情報およびフィンガープリント管理リストの構造を持つデータ等を格納する。また、メモリ１２は、所定領域がランクに対応付けて分割された分割領域を有し、各分割領域には、フィンガープリントの全データビットまたは縮約後のデータビットが格納される。
【００４８】
＜重複排除＞
図５は重複排除の動作の一例を説明するための図である。
〔ステップＳ１１〕制御部１１は、ホスト３から送信された、記憶装置２０への書き込み対象となるデータ（Ｉ／Ｏデータ）ｄ０を受信すると、データｄ０を所定サイズに分割して、データｄ１、・・・、ｄ６を生成する。
【００４９】
〔ステップＳ１２〕制御部１１は、データｄ１、・・・、ｄ６から各データを識別するためのフィンガープリントを生成し、生成したフィンガープリントをフィンガープリントキャッシュ１２ａに格納する。
【００５０】
分割されたデータのうち、データｄ１からフィンガープリントｆ１が生成され、データｄ２からフィンガープリントｆ２が生成される。
また例えば、データｄ３、ｄ５が同一データであり、データｄ４、ｄ６が同一データとする。この場合、同一データのフィンガープリントは一致するから、データｄ３、ｄ５からフィンガープリントｆ３が生成され、データｄ４、ｄ６からフィンガープリントｆ４が生成される。生成されたフィンガープリントｆ１、ｆ２、ｆ３、ｆ４は、フィンガープリントキャッシュ１２ａに保持される。
【００５１】
〔ステップＳ１３〕制御部１１は、フィンガープリントｆ１、・・・、ｆ４に対応するデータを、重複排除プール２０ａ内のデータＤＢ（データベース）２０ａ１へ書き込む。データＤＢ２０ａ１には、重複排除後のデータ（De-duplicated I/O data）として、データｄ１、ｄ２、ｄ３、ｄ４が書き込まれる（データｄ５、ｄ６は重複データなので排除される）。
【００５２】
〔ステップＳ１４〕制御部１１は、フィンガープリントキャッシュ１２ａの領域が枯渇した場合、重複排除プール２０ａ内のフィンガープリントＤＢ２０ａ２にフィンガープリントを退避させて空き領域を作成する。また、制御部１１は、枯渇が解消した場合、フィンガープリントＤＢ２０ａ２からフィンガープリントを読み出し、フィンガープリントキャッシュ１２ａに格納する。
【００５３】
なお、フィンガープリントキャッシュ１２ａは、メモリ１２の所定領域が使用され、データＤＢ２０ａ１およびフィンガープリントＤＢ２０ａ２は、記憶装置２０の所定領域が使用される。
【００５４】
＜フィンガープリント格納時のメモリ資源の圧迫＞
次にフィンガープリントを格納する際にメモリ資源が圧迫される状況について、図６を用いて説明する。図６はフィンガープリントの管理の一例を示す図である。フィンガープリント制御部１１０は、フィンガープリントからインデックス値を算出し、インデックス値を用いて、フィンガープリントをグループ分けする。なお、フィンガープリント制御部１１０は、参考例のＣＭの制御機構部とする。
【００５５】
フィンガープリント制御部１１０は、グループ毎のフィンガープリント格納場所を一意に定めてフィンガープリントを管理する。例えば、フィンガープリントｆ１、・・・、ｆ１１がある場合、フィンガープリント制御部１１０は、フィンガープリントｆ１、・・・、ｆ１１からインデックス値を算出し、インデックス値にもとづいて、フィンガープリントｆ１、・・・、ｆ１１を４つのグループｇ１、・・・、ｇ４に分ける。
【００５６】
そして、フィンガープリント制御部１１０は、キャッシュ領域ｒ１１、ｒ１２、ｒ１３、ｒ１４それぞれをグループｇ１、ｇ２、ｇ３、ｇ４のフィンガープリントの格納領域とする。さらにフィンガープリント制御部１１０は、ディスク領域Ｒ１１、Ｒ１２、Ｒ１３、Ｒ１４それぞれをグループｇ１、ｇ２、ｇ３、ｇ４のフィンガープリントの格納領域とする。
【００５７】
図６の例では、フィンガープリントｆ１、ｆ２、ｆ９は、グループｇ１に分類されている。そして、キャッシュ領域ｒ１１にフィンガープリントｆ１、ｆ２が格納され、ディスク領域Ｒ１１にフィンガープリントｆ９が格納されている。
【００５８】
フィンガープリントｆ３、ｆ４、ｆ１０は、グループｇ２に分類されている。そして、キャッシュ領域ｒ１２にフィンガープリントｆ３、ｆ４が格納され、ディスク領域Ｒ１２にフィンガープリントｆ１０が格納されている。
【００５９】
フィンガープリントｆ５、ｆ６は、グループｇ３に分類されている。キャッシュ領域ｒ１３にフィンガープリントｆ５、ｆ６が格納され、ディスク領域Ｒ１３は空きになっている。
【００６０】
フィンガープリントｆ７、ｆ８、ｆ１１は、グループｇ４に分類されている。キャッシュ領域ｒ１４にフィンガープリントｆ７、ｆ８が格納され、ディスク領域Ｒ１４にフィンガープリントｆ１１が格納されている。
【００６１】
なお、ディスク領域は、例えば、メモリ領域に格納できなかったフィンガープリントを格納する場合に使用される。また、ディスク領域に存在するフィンガープリントを参照する場合、フィンガープリント制御部１１０は、該当フィンガープリントのインデックス値に該当するグループのすべてのフィンガープリントを読み出す。
【００６２】
ここで、上記のフィンガープリント制御部１１０では、データから生成したフィンガープリントを縮約等せずにキャッシュに格納しているため、フィンガープリントの増加に伴ってキャッシュ容量が増加し、キャッシュ容量の枯渇が発生しやすい。
【００６３】
また、キャッシュに格納できなかったフィンガープリントはディスクに格納されるが、フィンガープリント制御部１１０は、フィンガープリントがディスク上のどこに存在するかの仕組みを有しておらず、存在箇所を特定できない。
【００６４】
このため、フィンガープリントの検索時、ディスクに格納されているすべてのフィンガープリントを読み出してキャッシュに展開する処理が行われており、性能が大幅に劣化してしまう。さらに、ディスクから読み出したすべてのフィンガープリントを展開するための領域を、キャッシュ上に確保しておかなければならない。
【００６５】
本発明はこのような点に鑑みてなされたものであり、フィンガープリントの格納時におけるメモリの効率的な活用を行ってメモリ消費容量の節約を可能にするものである。
＜フィンガープリントの管理＞
以降、第２の実施の形態について詳しく説明する。図７はフィンガープリントの管理の一例を示す図である。制御部１１は、フィンガープリントからインデックス値を算出し、インデックス値を用いて、フィンガープリントをグループ分けする。そして、制御部１１は、グループ毎のフィンガープリント格納場所を一意に定めてフィンガープリントを管理する。
【００６６】
例えば、フィンガープリントｆ１、・・・、ｆ１１がある場合、制御部１１は、フィンガープリントｆ１、・・・、ｆ１１からインデックス値を算出し、インデックス値にもとづいて、フィンガープリントｆ１、・・・、ｆ１１を４つのグループｇ１、・・・、ｇ４に分ける。
【００６７】
そして、制御部１１は、キャッシュ１２内のキャッシュ領域ｒ１、ｒ２、ｒ３、ｒ４それぞれをグループｇ１、ｇ２、ｇ３、ｇ４のフィンガープリントの格納領域とする。さらに制御部１１は、ディスク２０内のディスク領域Ｒ１、Ｒ２、Ｒ３、Ｒ４それぞれをグループｇ１、ｇ２、ｇ３、ｇ４のフィンガープリントの格納領域とする。
【００６８】
ここで、制御部１１は、所定のフィンガープリントに対しては、サイズ削減による縮小化を行ってキャッシュ１２に格納する。例えば、制御部１１は、キャッシュヒット率（参照頻度）が所定値より小さなフィンガープリントに対しては、該フィンガープリントのサイズを削減してキャッシュ１２に格納する。
【００６９】
また、制御部１１は、キャッシュヒット率が所定値より大きなフィンガープリントは、該フィンガープリントのサイズはそのままで（サイズ削減無しで）キャッシュ１２に格納する。さらに、制御部１１は、ディスク２０にフィンガープリントを格納する場合、フィンガープリントのサイズ削減は行わずに、オリジナル（原本）のフィンガープリントで、その全データビットを複製して格納する。
【００７０】
図７の例のフィンガープリントの格納状態について示すと、フィンガープリントｆ１、ｆ２、ｆ９は、グループｇ１に分類されている。キャッシュ領域ｒ１には、フィンガープリントｆ１（サイズ削減有り）、フィンガープリントｆ２（サイズ削減無し）、フィンガープリントｆ９（サイズ削減有り）が格納される。また、ディスク領域Ｒ１には、サイズ削減のないフィンガープリントｆ１、ｆ２、ｆ９が格納される。
【００７１】
フィンガープリントｆ３、ｆ４、ｆ１０は、グループｇ２に分類されている。キャッシュ領域ｒ２には、フィンガープリントｆ３（サイズ削減無し）、フィンガープリントｆ４（サイズ削減有り）、フィンガープリントｆ１０（サイズ削減有り）が格納される。また、ディスク領域Ｒ２には、サイズ削減のないフィンガープリントｆ３、ｆ４、ｆ１０が格納される。
【００７２】
フィンガープリントｆ５、ｆ６は、グループｇ３に分類されている。キャッシュ領域ｒ３には、フィンガープリントｆ５（サイズ削減無し）、フィンガープリントｆ６（サイズ削減無し）が格納される。また、ディスク領域Ｒ３には、サイズ削減のないフィンガープリントｆ５、ｆ６が格納される。
【００７３】
フィンガープリントｆ７、ｆ８、ｆ１１は、グループｇ４に分類されている。キャッシュ領域ｒ４には、フィンガープリントｆ７（サイズ削減有り）、フィンガープリントｆ８（サイズ削減無し）、フィンガープリントｆ１１（サイズ削減有り）が格納される。また、ディスク領域Ｒ４には、サイズ削減のないフィンガープリントｆ７、ｆ８、ｆ１１が格納される。
【００７４】
図６の格納状態と比較すると、図７ではフィンガープリントｆ１、ｆ４、ｆ７のサイズ削減を行ってキャッシュ領域に格納することにより、キャッシュ領域に対してフィンガープリントｆ９、ｆ１０、ｆ１１の格納が可能になっている。
【００７５】
なお、フィンガープリントをディスク２０に管理する場合、キャッシュ１２にオリジナルのフィンガープリントが格納された後から、フィンガープリントのサイズ削減処理が行われるまでの間に、該オリジナルのフィンガープリントをディスク２０上に複製して管理する。契機としては、例えば、制御部１１は、ＣＰＵ処理が低負荷状態において、ディスク２０にオリジナルのフィンガープリントを複製して格納する。
【００７６】
また、ＣＰＵ処理の低負荷状態において、ディスク２０へのフィンガープリントの複製ができなかった場合、制御部１１は、フィンガープリントの一部をキャッシュ１２から削除する直前の期間にオリジナルのフィンガープリントの複製を行う。
【００７７】
＜フィンガープリントの検索＞
図８はフィンガープリントの検索の一例を示すフローチャートである。
〔ステップＳ２１〕制御部１１は、重複排除を行う際の検索対象となる対象フィンガープリントからインデックス値を算出する。
【００７８】
〔ステップＳ２２〕制御部１１は、算出したインデックス値に対応するグループを求める。
〔ステップＳ２３〕制御部１１は、対象フィンガープリントと、求めたグループのキャッシュ領域に格納されるフィンガープリントとを順に比較する。一致の場合（ＨＩＴの場合）、ステップＳ２４へ処理が進み、不一致の場合（ＭＩＳＳの場合）、ステップＳ２５へ処理が進む。
【００７９】
〔ステップＳ２４〕制御部１１は、対象フィンガープリントが生成されたデータは、重複有りと判定して排除する。
〔ステップＳ２５〕制御部１１は、求めたグループのディスク領域に格納されるフィンガープリントを読み込んでキャッシュ領域に格納する。
【００８０】
〔ステップＳ２６〕制御部１１は、対象フィンガープリントと、読み込んだフィンガープリントとを順に比較する。一致の場合、ステップＳ２４へ処理が進み、不一致の場合、ステップＳ２７へ処理が進む。
【００８１】
〔ステップＳ２７〕制御部１１は、対象フィンガープリントが生成されたデータは、重複無しと判定して、図５に示したデータＤＢ２０ａ１に格納する。
＜フィンガープリント管理リスト＞
図９はフィンガープリント管理リストの一例を示す図である。フィンガープリント管理リスト４は、グループ毎に生成され、各グループのキャッシュ領域に格納されるフィンガープリントを管理するためのデータが登録されるリストである。
【００８２】
フィンガープリント管理リスト４は、属性として、フィンガープリント番号、参照頻度番号および付加情報を有する。フィンガープリント番号は、フィンガープリントの識別番号である。
【００８３】
参照頻度番号は、キャッシュヒット率を示すもので、キャッシュヒット率が高い順に若い数字が付される。図９の例では、参照頻度番号＝１のフィンガープリントｆ３は、参照頻度が最も高いことを表している。また、参照頻度番号＝１１のフィンガープリントｆ５は、参照頻度が最も低いことを表している。
【００８４】
付加情報は、フィンガープリントに付随して設けられる情報であり、例えば、インデックス値やフィンガープリントがキャッシュ領域およびディスク領域に格納されるときのアドレス情報、またはグループの識別番号等が該当する。
【００８５】
なお、ディスク領域に格納されるときのアドレス情報がフィンガープリント毎に対応付けて管理されるため、ディスク領域のどの領域にフィンガープリントが格納されているかを特定可能である。
【００８６】
＜キャッシュ領域の分割＞
図１０はキャッシュ領域の分割の一例を示す図である。キャッシュ１２の所定領域は、フィンガープリントのキャッシュヒット率に応じたランクに対応して分割される。図１０の例では、ランク＃１、＃２、＃３が設定され、キャッシュ１２の所定領域を３つに分割したキャッシュ領域（以下、キャッシュ分割領域と呼ぶ）Ｈ１、Ｈ２、Ｈ３を示している。キャッシュ分割領域Ｈ１、Ｈ２、Ｈ３の順にランクが高い（キャッシュヒット率が高い）ものとする。
【００８７】
また、フィンガープリントの全ビットをｈビットとした場合、制御部１１は、キャッシュ分割領域Ｈ１には、ｈビットのフィンガープリント（フィンガープリントの全データビット）を格納する。
【００８８】
さらに、制御部１１は、キャッシュ分割領域Ｈ２には、上位ｈ／２ビットのフィンガープリントを格納し、キャッシュ分割領域Ｈ３には、上位ｈ／４ビットのフィンガープリントを格納する。
【００８９】
＜フローチャート＞
次に動作について、図１１から図１４のフローチャートを用いて説明する。
図１１はフィンガープリントの管理制御の一例を示すフローチャートである。
【００９０】
〔ステップＳ３１〕制御部１１は、ホスト３から送信された書き込みＩ／Ｏデータを受信する。
〔ステップＳ３２〕制御部１１は、受信したＩ／Ｏデータから対象フィンガープリントを生成する。
【００９１】
〔ステップＳ３３〕制御部１１は、対象フィンガープリントの検索を行い（図１２で後述）、検索処理の結果、３つの処理へ分岐する。
対象フィンガープリントがキャッシュ１２にない場合、ステップＳ３４へ処理が進む。すなわち、対象フィンガープリントがキャッシュ分割領域Ｈ１、Ｈ２、Ｈ３に格納されるフィンガープリントのいずれにも一致しない場合は、ステップＳ３４へ処理が進む。
【００９２】
対象フィンガープリントの一部の所定データビットがキャッシュ１２にある場合、ステップＳ３５へ処理が進む。すなわち、対象フィンガープリントの上位の所定データビットがキャッシュ分割領域Ｈ２、Ｈ３のいずれかに格納されるフィンガープリントに一致する場合は、ステップＳ３５へ処理が進む。
【００９３】
対象フィンガープリントの全データビットがキャッシュ１２にある場合、ステップＳ３６へ処理が進む。すなわち、対象フィンガープリントがキャッシュ分割領域Ｈ１に格納されるフィンガープリントに一致する場合は、ステップＳ３６へ処理が進む。
【００９４】
〔ステップＳ３４〕制御部１１は、新規フィンガープリントの格納処理を行う（図１３で後述）。
〔ステップＳ３５〕制御部１１は、フィンガープリントのランク更新処理を行う（図１４で後述）。
【００９５】
〔ステップＳ３６〕制御部１１は、対象フィンガープリントに対し、フィンガープリント管理リスト４上で参照頻度番号＝１を付して更新する（参照頻度が最も高いフィンガープリントとしてリスト登録する）。
【００９６】
〔ステップＳ３７〕制御部１１は、対象フィンガープリントに対し、フィンガープリント管理リスト４上の付加情報を更新する。
図１２はフィンガープリントの検索処理の一例を示すフローチャートである。
【００９７】
〔ステップＳ３３ａ〕制御部１１は、対象フィンガープリントがキャッシュ１２に格納されているか否かを判定する。対象フィンガープリントがキャッシュ１２に格納されていない場合、図１１のステップＳ３４へ処理が進む。
【００９８】
すなわち、対象フィンガープリントの全ｈビットがキャッシュ分割領域Ｈ１に格納されるフィンガープリントと不一致であること。また、該フィンガープリントの上位ｈ／２ビットがキャッシュ分割領域Ｈ２に格納されるフィンガープリントと不一致であること。さらに、該フィンガープリントの上位ｈ／４ビットがキャッシュ分割領域Ｈ３に格納されるフィンガープリントと不一致であること。これらすべてにおいて不一致が満たされる場合、ステップＳ３４へ処理が進む。
【００９９】
一方、制御部１１は、対象フィンガープリントがキャッシュ１２に格納されている場合、ステップＳ３３ｂへ処理が進む。すなわち、制御部１１は、対象フィンガープリントの全ｈビット、上位ｈ／２ビット、上位ｈ／４ビットの少なくとも１つがキャッシュ分割領域Ｈ１、Ｈ２、Ｈ３のいずれかに格納されるフィンガープリントに一致する場合、ステップＳ３３ｂへ処理が進む。
【０１００】
〔ステップＳ３３ｂ〕制御部１１は、対象フィンガープリントに該当するデータをディスク２０から読み出す。
〔ステップＳ３３ｃ〕制御部１１は、対象フィンガープリントの全ｈビットは、キャッシュ分割領域Ｈ１に格納されるフィンガープリントと一致するか否かを判定する。一致する場合はステップＳ３３ｆへ処理が進み、不一致の場合はステップＳ３３ｄへ処理が進む。
【０１０１】
〔ステップＳ３３ｄ〕制御部１１は、ディスク２０からフィンガープリントを読み出す。
〔ステップＳ３３ｅ〕制御部１１は、ディスク２０から読み出したフィンガープリントと、対象フィンガープリントが一致するか否かを判定する。一致する場合はステップＳ３３ｆへ処理が進み、不一致の場合は図１１のステップＳ３５へ処理が進む。
【０１０２】
〔ステップＳ３３ｆ〕制御部１１は、ステップＳ３３ｂで読み出したデータと、書き込み要求を受けたデータとの合致確認を行い、合致確認後に図１１のステップＳ３６へ処理が進む。
【０１０３】
図１３は新規フィンガープリントの格納処理の一例を示すフローチャートである。
〔ステップＳ３４ａ〕制御部１１は、フィンガープリント管理リスト４にもとづいて、キャッシュ分割領域Ｈ１に格納されるフィンガープリントのうち、参照頻度が２つの低いフィンガープリントを抽出する。
【０１０４】
〔ステップＳ３４ｂ〕制御部１１は、抽出したフィンガープリントそれぞれから下位ｈ／２のビットを削除する。
〔ステップＳ３４ｃ〕制御部１１は、キャッシュ分割領域Ｈ２の現在の格納量は、所定量以上か否かを判定する。所定量未満の場合、ステップＳ３４ｄへ処理が進み、所定量以上の場合、ステップＳ３４ｆへ処理が進む。
【０１０５】
〔ステップＳ３４ｄ〕制御部１１は、下位ｈ／２ビットを削除したフィンガープリントをキャッシュ分割領域Ｈ２に格納する。
〔ステップＳ３４ｅ〕制御部１１は、対象フィンガープリント（の全ｈビット）をキャッシュ分割領域Ｈ１に格納する。図１１のステップＳ３７へ処理が進む。
【０１０６】
〔ステップＳ３４ｆ〕制御部１１は、フィンガープリント管理リスト４にもとづいて、キャッシュ分割領域Ｈ２に格納されるフィンガープリントのうち、参照頻度が低い４つのフィンガープリントを抽出する。
【０１０７】
〔ステップＳ３４ｇ〕制御部１１は、抽出したフィンガープリントそれぞれから下位ｈ／４のビットを削除する。
〔ステップＳ３４ｈ〕制御部１１は、キャッシュ分割領域Ｈ３の現在の格納量は、所定量以上か否かを判定する。所定量未満の場合、ステップＳ３４ｉへ処理が進み、所定量以上の場合、ステップＳ３４ｊへ処理が進む。
【０１０８】
〔ステップＳ３４ｉ〕制御部１１は、下位ｈ／４ビットを削除したフィンガープリントをキャッシュ分割領域Ｈ３に格納する。ステップＳ３４ｄへ処理が進む。
〔ステップＳ３４ｊ〕制御部１１は、フィンガープリント管理リスト４にもとづいて、キャッシュ分割領域Ｈ３から参照頻度が低い４つのフィンガープリントを削除する。ステップＳ３４ｄへ処理が進む。
【０１０９】
図１４はフィンガープリントのランク更新処理の一例を示すフローチャートである。
〔ステップＳ３５ａ〕制御部１１は、対象フィンガープリントの上位ｈ／２が一致したのか、上位ｈ／４が一致したのかを判定する。
【０１１０】
対象フィンガープリントの上位ｈ／２がキャッシュ分割領域Ｈ２に格納されるフィンガープリントに一致する場合はステップＳ３５ｂ１へ処理が進む。また、対象フィンガープリントの上位ｈ／４がキャッシュ分割領域Ｈ３に格納されるフィンガープリントに一致する場合はステップＳ３５ｃ１へ処理が進む。
【０１１１】
〔ステップＳ３５ｂ１〕制御部１１は、フィンガープリント管理リスト４にもとづいて、キャッシュ分割領域Ｈ１から参照頻度が低い１つのフィンガープリントを抽出する。
〔ステップＳ３５ｂ２〕制御部１１は、抽出したフィンガープリントの下位ｈ／２ビットを削除する。
【０１１２】
〔ステップＳ３５ｂ３〕制御部１１は、下位ｈ／２ビットを削除したフィンガープリントをキャッシュ分割領域Ｈ２に格納する。
〔ステップＳ３５ｂ４〕制御部１１は、対象フィンガープリントの上位ｈ／２ビットに一致したキャッシュ分割領域Ｈ２に格納されるフィンガープリントを、ディスク２０に格納されるフィンガープリントにもとづいてビット拡張を行う。
【０１１３】
〔ステップＳ３５ｂ５〕制御部１１は、ビット拡張したフィンガープリントをキャッシュ分割領域Ｈ１に格納する。図１１のステップＳ３７へ処理が進む。
〔ステップＳ３５ｃ１〕制御部１１は、フィンガープリント管理リスト４にもとづいて、キャッシュ分割領域Ｈ２から参照頻度が低い１つのフィンガープリントを抽出する。
【０１１４】
〔ステップＳ３５ｃ２〕制御部１１は、抽出したフィンガープリントの下位ｈ／４ビットを削除する。
〔ステップＳ３５ｃ３〕制御部１１は、下位ｈ／４ビットを削除したフィンガープリントをキャッシュ分割領域Ｈ３に格納する。
【０１１５】
〔ステップＳ３５ｃ４〕制御部１１は、対象フィンガープリントの上位ｈ／４ビットに一致したキャッシュ分割領域Ｈ３に格納されるフィンガープリントを、ディスク２０に格納されるフィンガープリントにもとづいてビット拡張を行う。
【０１１６】
〔ステップＳ３５ｃ５〕制御部１１は、ビット拡張したフィンガープリントをキャッシュ分割領域Ｈ２に格納する。図１１のステップＳ３７へ処理が進む。
＜新規フィンガープリントの格納処理＞
図１５は新規フィンガープリントの格納処理の一例を示す図である。図１３に示すステップＳ３４ａからステップＳ３４ｅのフローを模式的に説明する図である。なお、以降の説明では、フィンガープリントの全データビットは８（＝ｈ）ビットとする。
【０１１７】
〔ステップＳ４１〕制御部１１は、対象フィンガープリントがキャッシュ１２に存在しないことを検出した場合、キャッシュ分割領域Ｈ１から参照頻度が最も低いフィンガープリントｆ２１と、参照頻度が２番目に低いフィンガープリントｆ２２とを抽出する。
【０１１８】
〔ステップＳ４２〕制御部１１は、抽出したフィンガープリントｆ２１、ｆ２２の下位４ビットを削除してフィンガープリントｆ２１ａ、ｆ２２ａを生成する。
〔ステップＳ４３〕制御部１１は、１ランク下のキャッシュ分割領域Ｈ２へ、フィンガープリントｆ２１ａ、ｆ２２ａを格納する。なお、キャッシュ分割領域Ｈ１に格納されるフィンガープリントｆ２１ａ、ｆ２２ａは、複製完了後に任意のタイミングでキャッシュ分割領域Ｈ１から削除される。
【０１１９】
〔ステップＳ４４〕制御部１１は、対象フィンガープリントをキャッシュ分割領域Ｈ１へ格納する。
＜フィンガープリントのランク更新処理＞
次に図１６、図１７を用いてフィンガープリントのランク更新処理について説明する。図１６はフィンガープリントのランク更新処理の一例を示す図である。図１４に示すステップＳ３５ｂ１からステップＳ３５ｂ５のフローを模式的に説明する図である。
【０１２０】
〔ステップＳ５１〕制御部１１は、対象フィンガープリントの上位４ビットがキャッシュ分割領域Ｈ２に存在することを検出した場合、キャッシュ分割領域Ｈ１から参照頻度が最も低いフィンガープリントｆ３１を抽出する。
【０１２１】
〔ステップＳ５２〕制御部１１は、抽出したフィンガープリントｆ３１の下位４ビットを削除してフィンガープリントｆ３１ａを生成する。
〔ステップＳ５３〕制御部１１は、１ランク下のキャッシュ分割領域Ｈ２へ、フィンガープリントｆ３１ａを格納する（ランクダウン処理）。
【０１２２】
〔ステップＳ５４〕制御部１１は、対象フィンガープリントの上位４ビットに一致したキャッシュ分割領域Ｈ２に存在するフィンガープリントに対して、ディスク２０に格納されているフィンガープリントを利用してビット拡張を行い（４ビットの拡張）、フィンガープリントｆ３２を生成する。
【０１２３】
〔ステップＳ５５〕制御部１１は、ビット拡張後のフィンガープリントｆ３２を１ランク上のキャッシュ分割領域Ｈ１に格納する（ランクアップ処理）。
図１７はフィンガープリントのランク更新処理の一例を示す図である。図１４に示すステップＳ３５ｃ１からステップＳ３５ｃ５のフローを模式的に説明する図である。
【０１２４】
〔ステップＳ６１〕制御部１１は、対象フィンガープリントの上位２ビットがキャッシュ分割領域Ｈ３に存在することを検出した場合、キャッシュ分割領域Ｈ２から参照頻度が最も低いフィンガープリントｆ４１を抽出する。
【０１２５】
〔ステップＳ６２〕制御部１１は、抽出したフィンガープリントｆ４１の下位２ビットを削除してフィンガープリントｆ４１ａを生成する。
〔ステップＳ６３〕制御部１１は、１ランク下のキャッシュ分割領域Ｈ３へ、フィンガープリントｆ４１ａを格納する（ランクダウン処理）。
【０１２６】
〔ステップＳ６４〕制御部１１は、対象フィンガープリントの上位２ビットに一致したキャッシュ分割領域Ｈ３に存在するフィンガープリントに対して、ディスク２０に格納されているフィンガープリントを利用してビット拡張（２ビットの拡張）を行い、フィンガープリントｆ４２を生成する。
【０１２７】
〔ステップＳ６５〕制御部１１は、ビット拡張後のフィンガープリントｆ４２を１ランク上のキャッシュ分割領域Ｈ２に格納する（ランクアップ処理）。
このようなキャッシュ分割領域に格納すべきフィンガープリントのランク更新処理が行われることで、参照頻度にもとづくデータビット縮約を行ったフィンガープリントの格納管理が可能になり、キャッシュの効率的な活用が可能になる。
【０１２８】
＜キャッシュ容量の決定＞
図１８はキャッシュ容量の決定手順の一例を示すフローチャートである。
〔ステップＳ７１〕制御部１１は、ディスクの搭載容量Ｍ［ｂｙｔｅ］からフィンガープリントの格納容量Ｈｍｅｍ［ｂｙｔｅ］を求める。
【０１２９】
〔ステップＳ７２〕制御部１１は、フィンガープリント格納容量Ｈｍｅｍからフィンガープリントの全データビットを格納できる最小数Ｈｍｉｍを求める。
〔ステップＳ７３〕制御部１１は、フィンガープリント格納容量Ｈｍｅｍからフィンガープリントのデータビットを部分的に格納できる最大数Ｈｍａｘを求める。
【０１３０】
〔ステップＳ７４〕制御部１１は、最小数Ｈｍｉｍから最大性能を引き出せる重複排除容量Ｘ［ｂｙｔｅ］を求める。
〔ステップＳ７５〕制御部１１は、最大数Ｈｍａｘからサポートできる重複排除容量Ｙ［ｂｙｔｅ］を求める。
【０１３１】
〔ステップＳ７６〕制御部１１は、重複排除容量Ｘ，Ｙにもとづいて、キャッシュ容量を決定する。
ここで、Ｈをフィンガープリントの最大サイズ、ａをフィンガープリントの最大分割回数、Ｄを重複排除を行うデータサイズ、Ｌをフィンガープリントに付加される付加情報とする。このとき以下の式が成り立つ。
【０１３２】
Ｈｍｅｍ＜Ｍ・・・（１）
Ｈｍｉｎ＝Ｈｍｅｍ／ｈ・・・（２）
Ｈｍａｘ＝Ｈｍｅｍ／（ｈ／２ａ）・・・（３）
Ｘ＝Ｈｍｉｎ×Ｄ  Ｙ＝Ｈｍａｘ×Ｄ・・・（４）
Ｈｍｅｍ＝（ｈ＋Ｌ）×Ｈ１＋（ｈ／２＋Ｌ）×Ｈ２＋・・・＋（ｈ／２ａ＋Ｌ）×Ｈａ・・・（５）
なお、Ｈ１、・・・、Ｈａは、作成したいプール毎に必要な重複排除可能容量に応じて１種類以上を割り振ることができる。
【０１３３】
以上説明したように、ストレージシステム１−１のＣＭ１０によれば、データから生成したフィンガープリントを縮約してキャッシュに格納するため、フィンガープリントが増加してもキャッシュ容量の枯渇を抑制する。また、フィンガープリントを格納する分割領域のランク更新を行うことでメモリの効率活用が可能になる。
【０１３４】
さらに、ディスクに格納するフィンガープリントのアドレスを管理するため、フィンガープリントのディスク上の格納箇所を容易に特定することができる。このため、ディスクに格納されているフィンガープリントをすべて読み出す処理が不要となり、システム性能の低下を抑止することができる。
【０１３５】
上記で説明した本発明のデータ処理装置１およびＣＭ１０の処理機能は、コンピュータによって実現することができる。この場合、データ処理装置１およびＣＭ１０が有すべき機能の処理内容を記述したプログラムが提供される。そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１３６】
処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、磁気記憶装置、光ディスク、光磁気記録媒体、半導体メモリ等がある。磁気記憶装置には、ハードディスク装置（ＨＤＤ）、フレキシブルディスク（ＦＤ）、磁気テープ等がある。光ディスクには、ＣＤ−ＲＯＭ／ＲＷ等がある。光磁気記録媒体には、ＭＯ（Magneto Optical disk）等がある。
【０１３７】
プログラムを流通させる場合、例えば、そのプログラムが記録されたＣＤ−ＲＯＭ等の可搬型記録媒体が販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。
【０１３８】
プログラムを実行するコンピュータは、例えば、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。
【０１３９】
また、コンピュータは、ネットワークを介して接続されたサーバコンピュータからプログラムが転送される毎に、逐次、受け取ったプログラムに従った処理を実行することもできる。また、上記の処理機能の少なくとも一部を、ＤＳＰ、ＡＳＩＣ、ＰＬＤ等の電子回路で実現することもできる。
【０１４０】
以上、実施の形態を例示したが、実施の形態で示した各部の構成は同様の機能を有する他のものに置換することができる。また、他の任意の構成物や工程が付加されてもよい。さらに、前述した実施の形態のうちの任意の２以上の構成（特徴）を組み合わせたものであってもよい。
【符号の説明】
【０１４１】
１  データ処理装置
１ａ  記憶部
１ｂ  制御部
ａ０  データ
ａ１  識別情報
ａ２、・・・、ａｎ  縮約された識別情報
＃１、・・・、＃ｎ  ランク
ｒ１、・・・、ｒｎ  分割領域
【図１】
2020057305.tif 000003
【図２】
2020057305.tif 000004
【図３】
2020057305.tif 000005
【図４】
2020057305.tif 000006
【図５】
2020057305.tif 000007
【図６】
2020057305.tif 000008
【図７】
2020057305.tif 000009
【図８】
2020057305.tif 000010
【図９】
2020057305.tif 000011
【図１０】
2020057305.tif 000012
【図１１】
2020057305.tif 000013
【図１２】
2020057305.tif 000014
【図１３】
2020057305.tif 000015
【図１４】
2020057305.tif 000016
【図１５】
2020057305.tif 000017
【図１６】
2020057305.tif 000018
【図１７】
2020057305.tif 000019
【図１８】
2020057305.tif 000020