(57)【要約】【課題】ストレージ装置においてデータの重複排除を行う。【解決手段】  本実施形態において、ストレージ装置は、データの第１の探索位置に含まれる第１の部分データの第１のハッシュ値と既存データの既存ハッシュ値とが一致するか否か判断する第１の判断部と、第１の判断部によって第１のハッシュ値と既存ハッシュ値とが一致すると判断された場合に、第１の部分データと既存データとが一致するか否か判断する第２の判断部と、第２の判断部によって第１の部分データと既存データとが一致すると判断された場合、第１の部分データと既存データとに対する重複排除を行い、重複排除されたデータをメモリ装置へ格納する重複排除部と、第１の判断部によって第１のハッシュ値と既存ハッシュ値とが一致しないと判断された場合に、第１のハッシュ値と既存ハッシュ値との差に基づいて第２の探索位置を決定する決定部と、を具備する。【選択図】      図１
2018045305.tif 000002
【特許請求の範囲】
【請求項１】
データの第１の探索位置に含まれる第１の部分データの第１のハッシュ値と既存データの既存ハッシュ値とが一致するか否か判断する第１の判断部と、
前記第１の判断部によって前記第１のハッシュ値と前記既存ハッシュ値とが一致すると判断された場合に、前記第１の部分データと前記既存データとが一致するか否か判断する第２の判断部と、
前記第２の判断部によって前記第１の部分データと前記既存データとが一致すると判断された場合、前記第１の部分データと前記既存データとに対する重複排除を行い、重複排除されたデータをメモリ装置へ格納する重複排除部と、
前記第１の判断部によって前記第１のハッシュ値と前記既存ハッシュ値とが一致しないと判断された場合に、前記第１のハッシュ値と前記既存ハッシュ値との差に基づいて第２の探索位置を決定する決定部と、
を具備するストレージ装置。
【請求項２】
前記決定部によって前記第２の探索位置が決定された場合に、前記第１の判断部、前記第２の判断部、前記重複排除部は、前記第１の部分データ及び前記第１のハッシュ値に代えて、前記第２の探索位置に含まれる前記第２の部分データ及び前記第２の部分データの第２のハッシュ値を用いて処理を実行する、
請求項１に記載のストレージ装置。
【請求項３】
前記決定部は、
前記第２の判断部によって前記第１の部分データと前記既存データとが一致しないと判断された場合、前記第１の探索位置を所定の１単位進め、
前記第２の判断部によって前記第１の部分データと前記既存データとが一致すると判断された場合、前記第１の探索位置を前記第１の分割データのサイズの分進める、
請求項１又は請求項２に記載のストレージ装置。
【請求項４】
先の部分データのハッシュ値に基づいて、前記先の部分データのハッシュ値に所定サイズのデータを付加し前記所定サイズのデータを削除した次の部分データのハッシュ値を計算可能であり、２つの部分データが似ているほど前記２つの部分データのハッシュ値が近くなるハッシュ関数を用いて、前記第１及び前記第２のハッシュ値と、前記既存ハッシュ値とを算出するハッシュ算出部、をさらに具備する、
請求項１乃至請求項３のいずれか１項に記載のストレージ装置。
【請求項５】
前記決定部は、前記第１の判断部によって前記第１のハッシュ値と前記既存ハッシュ値とが一致しないと判断された場合に、前記第１のハッシュ値と前記第２のハッシュ値との差を前記所定の１単位に相当する値で除算して算出された区間を前記第１の探索位置に加えることにより前記第２の探索位置を決定する、
請求項４に記載のストレージ装置。
【請求項６】
前記第１の判断部、前記決定部は、前記メモリ装置に格納済の複数の格納済データごとに全体ハッシュ値を算出し、前記データの全体ハッシュ値と値の近い全体ハッシュ値を有する格納済データを選出し、前記選出された格納済データを、前記既存データとして処理を実行する、
請求項４又は請求項５に記載のストレージ装置。
【請求項７】
前記第１の判断部、前記第２の判断部、前記重複排除部は、前記メモリ装置に格納済の複数の格納済データごとに全体ハッシュ値を算出し、前記算出された全体ハッシュ値のうち値の近い１組のハッシュ値を選出し、前記第１の部分データ及び前記第１のハッシュ値に代えて、前記１組のハッシュ値に対応し前記メモリ装置に格納されている１組の格納済データに含まれる第３の部分データ及び前記第３の部分データの第３のハッシュ値を用い、さらに前記既存データ及び前記既存ハッシュ値に代えて、前記１組の格納済データに含まれる第４の部分データ及び前記第４の部分データの第４のハッシュ値を用いて処理を実行する、
請求項４又は請求項５に記載のストレージ装置。
【請求項８】
前記第１の部分データのサイズは、オペレーティング・システムのメモリ管理サイズと同等である、
請求項１乃至請求項７のいずれか１項に記載のストレージ装置。
【請求項９】
コンピュータを、
データの第１の探索位置に含まれる第１の部分データの第１のハッシュ値と既存データの既存ハッシュ値とが一致するか否か判断する第１の判断部と、
前記第１の判断部によって前記第１のハッシュ値と前記既存ハッシュ値とが一致すると判断された場合に、前記第１の部分データと前記既存データとが一致するか否か判断する第２の判断部と、
前記第２の判断部によって前記第１の部分データと前記既存データとが一致すると判断された場合、前記第１の部分データと前記既存データとに対する重複排除を行い、重複排除されたデータをメモリ装置へ格納する重複排除部と、
前記第１の判断部によって前記第１のハッシュ値と前記既存ハッシュ値とが一致しないと判断された場合に、前記第１のハッシュ値と前記既存ハッシュ値との差に基づいて第２の探索位置を決定する決定部と、
して機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本実施形態は、ストレージ装置、及びプログラムに関する。
【背景技術】
【０００２】
ストレージ装置にデータを格納する際に重複排除技術が用いられる場合がある。重複排除技術では、重複したデータを１か所にまとめて保存することでストレージ装置の記憶量効率を高める。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】米国特許第８７５１４６２号明細書
【特許文献２】特願２０１３−５１７５０４号公報
【特許文献３】特表２０１４−５０７８４１号公報
【特許文献４】米国特許第５９９０８１０号明細書
【非特許文献】
【０００４】
【非特許文献１】A Berman, Y.Birk and A.Mendelson, “Accelerating duplicate data chunk recognition using NN trained by locality sensitive hash”,  (IEEEI) 2014 IEEE 28th Convention of, 2014年12月3日, p.1-5.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本実施形態は、データの重複排除を行うストレージ装置、及びプログラムを提供する。
【課題を解決するための手段】
【０００６】
本実施形態において、ストレージ装置は、データの第１の探索位置に含まれる第１の部分データの第１のハッシュ値と既存データの既存ハッシュ値とが一致するか否か判断する第１の判断部と、第１の判断部によって第１のハッシュ値と既存ハッシュ値とが一致すると判断された場合に、第１の部分データと既存データとが一致するか否か判断する第２の判断部と、第２の判断部によって第１の部分データと既存データとが一致すると判断された場合、第１の部分データと既存データとに対する重複排除を行い、重複排除されたデータをメモリ装置へ格納する重複排除部と、第１の判断部によって第１のハッシュ値と既存ハッシュ値とが一致しないと判断された場合に、第１のハッシュ値と既存ハッシュ値との差に基づいて第２の探索位置を決定する決定部と、を具備する。
【図面の簡単な説明】
【０００７】
【図１】第１の実施形態に係るストレージ装置の構成を例示するブロック図。
【図２】ローリングハッシュ関数によるハッシュ値の計算を例示する概念図。
【図３】第１の実施形態に係る重複探索処理を例示するフローチャート。
【図４】第１の実施形態に係る重複探索対象となるファイルの絞り込み処理を例示するフローチャート。
【図５】第１の実施形態に係る探索位置のスキップ処理を例示するフローチャート。
【図６】第１の実施形態に係る探索位置のスキップ処理を例示する概念図。
【図７】第１の実施形態に係る重複探索処理を例示する図。
【図８】第１の実施形態に係るポストプロセスにおける重複探索処理の手順を例示するフローチャート。
【図９】第１の実施形態に係る重複探索処理と他の重複探索処理との対比結果を例示する図。
【発明を実施するための形態】
【０００８】
以下、図面を参照しながら本発明の実施の形態について説明する。なお、以下の説明において、略又は実質的に同一の機能及び構成要素については、同一符号を付し、必要に応じて説明を行う。
【０００９】
［第１の実施形態］
重複排除処理は、重複したデータを１か所にまとめて保存することでストレージ装置の記憶量効率を高める技術である。
【００１０】
重複排除処理では、データの重複判定にハッシュが用いられる場合がある。例えば、可変長の重複排除処理では、ローリングハッシュ（Rolling Hash）を用いて特定のパターンを検出することで区切り位置を決める。
【００１１】
本実施形態に係るストレージ装置は、重複排除処理を行う際、重複データの探索処理（以下、重複探索処理とする）及び重複の判定に局所性鋭敏型ハッシュ（Locality Sensitive Hash）とローリングハッシュの性質を併せ持つハッシュ関数を用いる。
【００１２】
本実施形態において、局所性鋭敏型ハッシュとは、例えば、データが類似しているほど値が近くなる性質を持つハッシュである。局所性鋭敏型ハッシュは、例えば、データクラスタリング、最近傍探索、類似画像検索などに用いられる。
【００１３】
本実施形態において、ローリングハッシュとは、例えば、あるデータの一部分に対するハッシュ値が既知である場合、その位置から任意の長さ分ずらした位置のハッシュ値を高速に算出できる性質を持つハッシュである。ローリングハッシュは、例えば、部分文字列探索などに用いられる。
【００１４】
本実施形態においては、上述の局所性鋭敏型ハッシュとローリングハッシュの両方の性質を持つハッシュ関数の一例として、移動平均（Moving Average）を用いたハッシュ関数を用いる。当該移動平均を用いたハッシュ関数により算出されるハッシュ値は１次元の整数であり、類似したデータのハッシュ値は近い値となる。しかしながら、他のハッシュ関数が用いられてもよい。例えば、データの中でビットが１である数がハッシュ値として用いられてもよい。また、特徴ベクトルなど、多次元の数値がハッシュ値として用いられてもよい。
【００１５】
本実施形態において、チャンクとは、例えば、ひとまとまりのデータを意味する。より具体的には、例えば、チャンクは、重複排除処理が行われる前のデータでもよく、重複排除処理が行われたことにより分割されたデータでもよい。
【００１６】
本実施形態に係る重複探索処理において、重複探索部は、まず、データ全体のハッシュ値を比較することで、重複探索処理及び重複排除処理の対象となるデータを絞り込む。次に、重複探索部は、ハッシュ値の差分に応じて重複部分の探索をスキップする。これにより、重複探索処理を効率化可能である。さらに、重複探索部は、ハッシュ値の比較に加えてデータの比較も行うことでデータの一致判定を行うため、ハッシュ値として使用されるデータの長さであるハッシュ長は短くてよい。このため、ハッシュ値の記憶量を削減可能である。
【００１７】
また、本実施形態に係る重複探索処理においては、データの重複部分に基づいて、データをチャンクに分割する分割位置が決められるため、重複排除率が向上する。また、データの重複が検出された後に、データがチャンクに分割されるため、分割数は最小限となる。
【００１８】
図１は、本実施形態に係るストレージ装置の構成を例示するブロック図である。
【００１９】
ストレージ装置１は、情報処理装置６と、データ、コマンド、信号、要求、情報などを送信及び受信可能に接続されている。情報処理装置６は、例えばコンピュータであり、プロセッサ６ａ、プログラムＰを格納するメモリ６ｂ、通信部６ｃを含む。プロセッサ６ａは、メモリ６ｂに記録されているプログラムＰを実行することで、通信部６ｃ経由でストレージ装置１とデータを通信可能である。プログラムＰは、例えばオペレーティング・システム（Operating System）でもよく、アプリケーション・プログラムでもよい。情報処理装置６は、例えば、ストレージ装置１のホスト装置でもよい。
【００２０】
ストレージ装置１は、重複排除処理部２、メモリ装置（ストレージ）３、チャンクテーブル４を記憶する第１の記憶部７、ファイルテーブル５を記憶する第２の記憶部８を備える。
【００２１】
重複排除処理部２は、Ｉ／Ｏ処理部２１、重複探索部２２、ハッシュ算出部２３、マッピング管理部２４、データ比較部２５を含む。重複排除処理部２は、例えば、プログラムを実行するプロセッサ、又は、コントローラによって実現されてもよい。
【００２２】
Ｉ／Ｏ処理部２１は、プログラムＰよりＩ／Ｏ要求Ｃ１を受信し、重複探索部２２へ重複排除要求Ｃ４を送信する。Ｉ／Ｏ要求Ｃ１は、例えばファイル書き込み要求である。また、Ｉ／Ｏ処理部２１は、メモリ装置３に対してデータの読み出し又は書き込み要求Ｃ３を送信する。Ｉ／Ｏ処理部２１は、マッピング管理部２４に対し、マッピング取得要求Ｃ２を送信する。
【００２３】
重複探索部２２は、Ｉ／Ｏ処理部２１より重複排除要求Ｃ４を受信した場合、重複排除処理を実行する。
【００２４】
重複探索部２２は、ハッシュ算出部２３へハッシュ値算出要求Ｃ５を送信する。重複探索部２２は、チャンクテーブル４を記憶する第１の記憶部７、及び、ファイルテーブル５を記憶する第２の記憶部８へチャンク情報の読み出し要求Ｃ６、及び、ファイル情報の読み出し要求Ｃ７を送信し、記録されているハッシュ値を探索する。重複探索部２２は、データ比較部２５へデータ比較要求Ｃ８を送信する。重複探索部２２は、マッピング管理部２４へマッピング更新要求Ｃ１０を送信する。
【００２５】
ハッシュ算出部２３は、重複探索部２２よりハッシュ値を取得したいデータ、及び、ハッシュ値算出要求Ｃ５を受信すると、受信したデータのハッシュ値を計算して重複探索部２２へ送信する。
【００２６】
マッピング管理部２４は、チャンクテーブル４に含まれるそれぞれのチャンク情報４０、及び、ファイルテーブル５に含まれるそれぞれのファイル情報５０を管理する。マッピング管理部２４は、例えば、ファイル情報５０のチャンクリスト５４から当該ファイルを構成するチャンクの一覧を取得し、チャンク情報４０を参照してメモリ装置３上に記録されたチャンクの格納位置を取得することで、当該ファイルとメモリ装置３上のデータとを関連づける。以下、マッピング管理部２４で管理されているファイルとメモリ装置３上のデータとの関連づけをマッピングと呼ぶ。
【００２７】
マッピング管理部２４は、Ｉ／Ｏ処理部２１からのマッピング取得要求Ｃ２に対してマッピングを送信する。マッピング管理部２４は、チャンクテーブル４を記憶する第１の記憶部７に対し、チャンク情報４０の読み出し又は書き込み要求Ｃ１１、及び、ファイルテーブル５を記憶する第２の記憶部８に対し、ファイル情報５０の読み出し又は書き込み要求Ｃ１２を送信する。マッピング管理部２４は、重複探索部２２よりマッピング更新要求Ｃ１０を受信すると、チャンクテーブル４及びファイルテーブル５に含まれているマッピングを更新する。
【００２８】
データ比較部２５は、重複探索部２２よりデータ比較要求Ｃ８を受信した場合、重複探索部２２により指定された２つのデータを比較し、比較結果を重複探索部２２へ送信する。データ比較部２５は、データ比較処理を実行する際に、メモリ装置３に格納されているデータ（チャンク）を読み出す必要がある場合は、メモリ装置３へ該当するデータの読み出し要求Ｃ９を送信し、メモリ装置３より該当するデータを受信する。
【００２９】
メモリ装置３は、重複排除処理において分割されたチャンクを格納する。
【００３０】
メモリ装置３は、Ｉ／Ｏ処理部２１、又は、データ比較部２５よりデータの読み出し要求Ｃ３，Ｃ９を受信した場合、Ｉ／Ｏ処理部２１又はデータ比較部２５に対して、メモリ装置３に格納されているデータを読み出して送信する。
【００３１】
本実施形態において、メモリ装置３、第１の記憶部７、第２の記憶部８は、例えば、ハード・ディスク（Hard Disk）、ソリッド・ステート・ドライブ（Solid State Drive）、又は、不揮発性メモリである。メモリ装置３、第１の記憶部７、第２の記憶部８は、ハード・ディスクとソリッド・ステート・ドライブとの双方を備えるハイブリッド型のメモリ装置でもよい。不揮発性メモリは、例えば、ＮＡＮＤ型フラッシュメモリ、ＮＯＲ型フラッシュメモリ、ＭＲＡＭ（Magnetoresistive Random Access Memory：磁気抵抗メモリ）、ＰＲＡＭ（Phase change Random Access Memory：相変化メモリ）、ＲｅＲＡＭ（Resistive Random Access Memory：抵抗変化型メモリ）、ＦｅＲＡＭ（Ferroelectric Random Access Memory）などの不揮発性の半導体メモリでもよい。例えば、不揮発性メモリは、他の不揮発性メモリ、磁気メモリなどでもよい。例えば、不揮発性メモリは、３次元構造のフラッシュメモリでもよい。例えば、不揮発性メモリは、ディスク（例えばｄｉｓｃ又はｄｉｓｋ）でもよい。
【００３２】
以下、重複排除処理の概要について述べる。
【００３３】
重複探索部２２は、さらに、第１の判断部２２ａ、決定部２２ｂ、重複排除部２２ｃを含む。また、データ比較部２５は、さらに、第２の判断部２５ａを含む。
【００３４】
第１の判断部２２ａは、データの第１の探索位置に含まれる第１の部分データの第１のハッシュ値と既存データの既存ハッシュ値とが一致するか否か判断する。
【００３５】
データ比較部２５の第２の判断部２５ａは、重複探索部２２の第１の判断部２２ａによって第１のハッシュ値と既存ハッシュ値とが一致すると判断された場合に、第１の部分データと既存データとが一致するか否か判断する。
【００３６】
重複排除部２２ｃは、データ比較部２５の第２の判断部２５ａによって第１の部分データと既存データとが一致すると判断された場合、第１の部分データと既存データとに対する重複排除を行い、マッピング管理部２４にマッピング情報の更新要求を送信し、重複排除されたデータをメモリ装置３へ格納する。
【００３７】
決定部２２ｂは、第１の判断部２２ａによって第１のハッシュ値と既存ハッシュ値とが一致しないと判断された場合に、第１のハッシュ値と既存ハッシュ値との差に基づいて第２の探索位置を決定する。この場合、重複探索部２２は、第１の部分データ及び第１のハッシュ値に代えて、第２の探索位置に含まれる第２の部分データ及び第２の部分データの第２のハッシュ値を用いて処理を実行する。
【００３８】
また、決定部２２ｂは、データ比較部２５の第２の判断部２５ａによって第１の部分データと既存データとが一致しないと判断された場合、第１の探索位置を所定の１単位進め、第１の部分データと既存データとが一致すると判断された場合、第１の探索位置を第１の分割データのサイズの分進める。重複排除処理の詳細については、図３以降で説明する。
【００３９】
チャンクテーブル４は、メモリ装置３に格納されたチャンクごとにチャンク情報４０を含む。
【００４０】
チャンク情報４０は、チャンクＩＤ ４１、チャンクサイズ４２、ハッシュ値４３、参照数４４を含む。
【００４１】
チャンクＩＤ ４１は、複数のチャンクを識別するための識別情報である。チャンクＩＤ ４１は、例えば、チャンクが生成された順に割り振られる番号でもよく、メモリ装置３上でのチャンクの論理アドレス（Logical Block Addressing（ＬＢＡ））などでもよい。
【００４２】
チャンクサイズ４２は、チャンクのサイズを表す。チャンクのサイズが小さい場合、重複排除処理後に管理されるチャンクの数が多くなり重複排除効率が低下するため、重複排除処理に用いるチャンクサイズ４２は、一定以上のサイズであることが望ましい。また、チャンクサイズ４２は、オペレーティング・システム上でメモリが管理される単位（例えば、ページ）のサイズと対応づけられてもよい。
【００４３】
本実施形態においては、例えば、重複排除処理に用いるチャンクサイズ４２は、４キロバイト（ｋＢ）以上の可変長とする。また、重複排除処理により生成される４ｋＢ未満のサイズのチャンクは、重複排除処理に用いられないものとする。
【００４４】
ハッシュ値４３は、チャンクのハッシュ値を表す。ハッシュ値４３は、重複排除処理における重複判定の際に他のチャンク又はデータと比較されるため、チャンクサイズ４２のうち一定のサイズに対して算出されることが望ましい。本実施形態においては、例えば、チャンクのハッシュ値算出には先頭４ｋＢのデータを用いる。また、重複排除処理により生成される４ｋＢ未満のサイズのチャンクのハッシュ値４３は記憶しない。
【００４５】
参照数４４は、重複排除処理が行われた後、該当するチャンクが重複して参照される回数を表す。例えば、ファイルα及びファイルβについて重複排除処理が行われ、共通する部分がチャンクγとして抽出された場合、チャンクγはファイルα及びファイルβの双方から参照されるため、チャンクγの参照数４４は２となる。
【００４６】
ファイルテーブル５は、メモリ装置３に格納されたファイルごとにファイル情報５０を含む。
【００４７】
ファイル情報５０は、ファイルＩＤ ５１、ファイルサイズ５２、ハッシュ値５３、チャンクリスト５４を含む。
【００４８】
ファイルＩＤ ５１は、複数のファイルを識別するための識別情報である。ファイルＩＤ ５１は、例えば、ｉノード番号などであってもよい。ｉノード番号は、ファイルシステム上でファイル又はディレクトリに対して固有に割り振られる番号である。
【００４９】
ファイルサイズ５２は、ファイルのサイズを表す。
【００５０】
ハッシュ値５３は、ファイルのハッシュ値を表す。本実施形態においては、ハッシュ値５３は、ファイル全体のデータを用いて算出される。なお、ファイルのハッシュ値５３の計算に用いるハッシュ関数は、ローリングハッシュの性質を備えていなくてもよい。すなわち、ファイルのハッシュ値５３の計算に用いるハッシュ関数として、チャンクのハッシュ値４３の計算に用いられるハッシュ関数（本実施形態では、移動平均を用いたハッシュ関数）とは異なるハッシュ関数が用いられてもよい。
【００５１】
チャンクリスト５４は、重複排除処理が行われた後、ファイルが参照するチャンクのリストを表す。
【００５２】
図２は、ローリングハッシュ関数によるハッシュ値の計算を例示する概念図である。
【００５３】
以下では、通常のハッシュ関数をｆとし、ローリングハッシュ関数をｈとする。
【００５４】
ローリングハッシュ関数ｈを用いることにより、通常のハッシュ関数ｆと比べて、ハッシュ値を算出するための計算量を低減することができる。
【００５５】
重複排除処理におけるハッシュ計算では、重複排除を行う文字列に対し、例えば１バイト（１文字）ずつずらしながら探索を行う。通常のハッシュ関数ｆを用いる場合、１回あたりのハッシュ計算に用いる文字列の長さをｎとすると、１回あたりのハッシュ計算の計算量はＯ（ｎ）となる。したがって、文字列長ｎの全ての位置で通常のハッシュ関数ｆによりハッシュ値の計算を行うと、計算量はＯ（ｎ2）となる。
【００５６】
これに対し、ローリングハッシュ関数ｈは、ある長さｌの第１のチャンクのハッシュ値ｈ（Ｘ）から、このチャンクＸに１バイトのデータを付加し１バイトのデータを削除した第２のチャンクのハッシュ値ｈ（Ｙ）を計算することができる関数である。このローリングハッシュ関数ｈを用いることにより、最初のデータのハッシュ値の計算より後の１回あたりのハッシュ値の計算量をＯ（１）に低減することができる。
【００５７】
例えば、図２に示すように、文字列からなるチャンクＸと、チャンクＸから文字Ａを削除し、文字Ｂを付加して得られるチャンクＹのハッシュ値を計算する場合について説明する。通常のハッシュ関数ｆを用いる場合、ハッシュ値は、チャンクＸについてはｆ（Ｘ）、チャンクＹについてはｆ（Ｙ）によりそれぞれ独立に算出され、いずれも計算量はＯ（ｎ）となる。これに対して、ローリングハッシュ関数ｈを用いる場合、チャンクＸのハッシュ値は、ｈ（Ｘ）（＝ｆ（Ｘ））により算出され、計算量はＯ（ｎ）となる。しかしながら、チャンクＹのハッシュ値は、既に算出されたｈ（Ｘ）の値を用いてｈ（Ｙ）＝ｈ（ｈ（Ｘ），−Ａ＋Ｂ）により計算量Ｏ（１）で算出される。
【００５８】
以下では、移動平均を用いたハッシュ関数Ｈを説明する。
【００５９】
移動平均を用いたハッシュ関数Ｈは、ｓをハッシュ値計算に用いる文字列、Ｃiをｉ番目のバイトの値、ｎを文字列長（チャンクサイズ４２）、ｍを整数、ｌを文字列ｓの文字列長とする場合、式（１）により表される。
【数１】
2018045305.tif 000003
【００６０】
ここで、ｍｏｄ（ａ，ｂ）関数は、数値ａを数値ｂで除算した場合の余りを計算する関数である。
【００６１】
ｎ、ｍおよびｌをすべて２のべき乗の値とした場合、移動平均を用いたハッシュ関数Ｈにより算出されるハッシュ値は、データの各バイトの値を合計し、上位ビットと下位ビットを取り除いた値となる。
【００６２】
なお、ｓはバイナリであってもよく、又は文字列であってもよい。Ｃiは１バイトでなくてもよく、１バイトより小さい又は大きい値であってもよい。ｎは可変長でもよく、この場合はｍをｎに比例させた値とする。
【００６３】
また、ｍ及びｌはハッシュ値の精度に影響する。ｌが大きいほどハッシュ長は大きくなり、ハッシュ値が衝突する可能性が小さくなるため、ハッシュ値の精度は高くなる。一方で、チャンクテーブルに記録するハッシュ値の記憶量が多くなる。また、ｍが小さいと類似しないデータ同士のハッシュ値が衝突しやすくなり、ｍが大きいと類似するデータ同士のハッシュ値が衝突しやすくなる。本実施形態では、例えば、Ｃiは１バイト、ｍは１、ｌは２の２０乗とすると、ハッシュ長は２０ビットとなる。
【００６４】
図３は、本実施形態に係る重複探索処理を例示するフローチャートである。
【００６５】
本実施形態に係る重複探索処理は、例えばファイルがメモリ装置３に保存される際に、当該ファイルに対して行われるものとする。しかしながら、重複探索処理は、当該ファイルがメモリ装置３に保存された後に行われてもよい。
【００６６】
ステップＳ１において、プログラムＰは、ストレージ装置１に対してファイルの書き込み要求（Ｉ／Ｏ要求Ｃ１）を送信する。
【００６７】
ステップＳ２において、ストレージ装置１のＩ／Ｏ処理部２１は、書き込むファイルを受信し、重複探索部２２へ重複排除要求Ｃ４を送信する。
【００６８】
ステップＳ３において、重複探索部２２は、重複探索処理を開始する。まず、重複探索部２２は、重複探索の対象となるファイルを絞り込む処理を行う。ファイルを絞り込む処理の詳細については、図４で後述する。なお、ファイルを絞り込む処理は行わなくてもよい。
【００６９】
ステップＳ４において、重複探索部２２は、ハッシュ算出部２３を用いて、ステップＳ２において受信したファイルの先頭４ｋＢのハッシュ値を算出する。より具体的には、重複探索部２２は、ハッシュ算出部２３に対し、ハッシュ値算出要求Ｃ５を送信する。ハッシュ算出部２３は、ハッシュ値の算出指令を受信すると、当該ハッシュ値を算出し、算出したハッシュ値を重複探索部２２へ送信する。
【００７０】
ステップＳ５において、重複探索部２２は、ステップＳ３で選出した重複探索の対象となるファイルのファイル情報５０のチャンクリスト５４に記されたチャンクについて、チャンクテーブル４を格納している第１の記憶部７に対し、チャンク情報の読み出し要求Ｃ６を送信する。重複探索部２２は、それぞれのチャンクのチャンク情報４０に含まれているハッシュ値４３を受信し、受信したハッシュ値４３の中からステップＳ４において算出されたファイルの先頭４ｋＢのハッシュ値と最も近いハッシュ値を探索する。
【００７１】
ステップＳ６において、重複探索部２２は、ステップＳ５において探索されたハッシュ値４３が、ステップＳ４において算出されたファイルの先頭４ｋＢのハッシュ値と等しいか否かを確認する。
【００７２】
双方のハッシュ値が異なる場合、重複探索部２２は、ステップＳ７において、ハッシュ値の差に応じて新たな探索位置を決定する（スキップする）。ここで、移動平均を用いたハッシュ関数Ｈにより求められる２つのデータのハッシュ値の差は、当該２つのデータの距離を表す。本実施形態では、このハッシュ値の差を用いて探索位置のスキップを行う。探索位置のスキップ処理については、図５及び図６を用いて後述する。双方のハッシュ値が等しい場合、ステップＳ８に進む。
【００７３】
ステップＳ８において、重複探索部２２は、データ比較部２５を用いて、ステップＳ４において算出されたハッシュ値に対応するデータ（ファイルの先頭４ｋＢのデータ）と、ステップＳ５において探索されたハッシュ値が等しいチャンクのデータを比較する。より具体的には、重複探索部２２は、データ比較部２５へ該当するデータのデータ比較要求Ｃ８を送信する。データ比較部２５は、メモリ装置３に対して該当するデータの読み出し要求Ｃ９を送信することにより、比較対象のデータを取得して比較し、比較結果を重複探索部２２へ送信する。
【００７４】
ステップＳ９において、ステップＳ８において得られた比較結果が完全一致である場合は、処理はステップＳ１２に進む。比較結果が完全一致でない場合、ステップＳ１０において、重複探索部２２は、一致する部分でデータを分割した場合に分割後に生成されるチャンクのうち、少なくとも１つ以上のチャンクのチャンクサイズ４２が４ｋＢ以上となるか否かを確認する。この条件を満たす場合は、処理はステップＳ１２に進む。当該条件を満たさない場合は、処理はステップＳ１１に進む。なお、ステップＳ１０の判定の閾値に用いられるチャンクのサイズは４ｋＢでなくてもよい。また、分割後に生成されるチャンクのサイズに関わらず、ファイルの分割を行うとしてもよい（すなわち、ステップＳ１０の判定はなくてもよい）。
【００７５】
ステップＳ１１において、重複探索部２２は、探索位置を１バイト進め、その後処理はステップＳ１４に進む。
【００７６】
ステップＳ１２において、重複探索部２２は、ファイルをステップＳ８の比較結果により一致する部分でチャンク（以下、新しいチャンクとする）に分割して重複排除を行う。新しいチャンクは、メモリ装置３に格納される。当該新しいチャンクのチャンク情報４０は、チャンクテーブル４に格納される。なお、ステップＳ８における比較結果が完全一致でない場合は、ステップＳ５において探索された既存のチャンク（以下、既存チャンクとする）も分割する。この場合、既存チャンクの参照数４４が１以上である場合（すなわち、既存チャンクが他の重複排除処理により生成された場合）は、既存チャンクを分割しなくてもよい。
【００７７】
ステップＳ１３において、重複探索部２２は、ステップＳ１２で重複排除を行ったチャンクのチャンクサイズ４２分だけ探索位置を進める。
【００７８】
ステップＳ１４において、重複探索部２２は、ステップＳ２において受信したファイルの新しい探索位置からのサイズが４ｋＢ以上であるか否かを確認する。新しい探索位置からのサイズが４ｋＢ以上の場合は、処理はステップＳ１５へ進む。新しい探索位置からのサイズが４ｋＢ以下である場合は、処理を終了する。
【００７９】
ステップＳ１５において、重複探索部２２は、ステップＳ２において受信したファイルの新しい探索位置から４ｋＢのハッシュ値を計算する。そして、重複探索部２２は、ステップＳ５に戻り、ファイルの先頭４ｋＢに対して実行した上述の重複探索処理を、新しい探索位置から４ｋＢの部分に対しても同様に実行する。
【００８０】
なお、重複探索処理の結果、重複するチャンクが見つからなかった場合は、重複探索部２２は、ファイルをチャンクに分割せずにメモリ装置３に格納する。この場合は、当該ファイル全体が１つのチャンクとしてファイル情報５０に記録される。
【００８１】
なお、上述では、新しくストレージ装置１に入力されるファイルと既存チャンクとの重複探索処理について説明したが、さらに当該ファイル内に含まれる複数のチャンクの中からハッシュ値が等しいチャンクを探索することにより重複排除処理を行ってもよい。
【００８２】
図４は、重複探索対象となるファイルの絞り込み処理を例示するフローチャートである。図４の処理は、上述の図３のステップＳ３の処理に相当する。
【００８３】
ステップＴ１において、重複探索部２２は、ハッシュ算出部２３を用いて、プログラムＰより受信したファイル全体のハッシュ値を算出する。より具体的には、重複探索部２２は、ハッシュ算出部２３に対し、当該ファイルのハッシュ値算出要求Ｃ５を送信する。ハッシュ算出部２３は、当該ファイルのハッシュ値を算出し、算出したハッシュ値を重複探索部２２へ送信する。重複探索部２２は、当該ハッシュ値がファイルテーブル５のファイル情報５０に含まれるように、ファイルテーブル５を更新する。
【００８４】
ステップＴ２において、重複探索部２２は、ファイルテーブル５に格納されている他のファイル情報５０のハッシュ値５３のうち、ステップＴ１において算出したハッシュ値と値が近い（例えば、両者のハッシュ値の差が１０２４以内である等）と判断したハッシュ値５３を持つファイルを選出し、重複探索処理の対象とする。なお、重複探索処理の対象とするファイル数には上限が設けられていてもよい。
【００８５】
図５は、本実施形態に係る探索位置のスキップ処理を例示するフローチャートである。
【００８６】
図６は、本実施形態に係る探索位置のスキップ処理を例示する概念図である。
【００８７】
図５及び図６の処理は、上述の図３のステップＳ４乃至ステップＳ７の処理に相当する。図６中の符号は、図５中の符号と対応する。
【００８８】
ステップＵ１において、重複探索部２２は、あるデータＤＴに対し、所定長（例えば４ｋＢ）のチャンクＸのハッシュ値Ｈ（Ｘ）を求める。ステップＵ１の処理は、図３のステップＳ４の処理と同等である。
【００８９】
ステップＵ２において、重複探索部２２は、チャンクテーブル４に格納されているチャンクのハッシュ値４３の中から、ハッシュ値Ｈ（Ｘ）に最も近いハッシュ値Ｈ（Ｙ）を探索する。ステップＵ２の処理は、図３のステップＳ５の処理と同等である。
【００９０】
ステップＵ３において、重複探索部２２は、ステップＵ１及びステップＵ２において得られたハッシュ値Ｈ（Ｘ）及びハッシュ値Ｈ（Ｙ）を用いて、スキップ長Ｄを算出する。ステップＵ３及びステップＵ４の処理は、図３のステップＳ７の処理に相当する。
【００９１】
本実施形態において、例えば、スキップ長Ｄは、スキップ長Ｄの単位をバイトとすると、ハッシュ値Ｈ（Ｘ）とハッシュ値Ｈ（Ｙ）の差（｜Ｈ（Ｘ）−Ｈ（Ｙ）｜）を１バイト（８ビット）分に相当する値（＝２8−１＝２５５）で除算することにより求められる。すなわち、スキップ長Ｄは、データＸとデータＹがＤバイト以上異なることを示す。より具体的には、例えば、｜Ｈ（Ｘ）−Ｈ（Ｙ）｜＝２５００である場合、スキップ長Ｄはｃｅｉｌ（２５００／２５５）＝１０となり、データＸとデータＹは１０バイト以上異なるため、重複探索部２２は、探索位置を１０バイト分スキップ可能である。ここで、ｃｅｉｌ（ａ）関数は、数値ａの小数点以下を切り上げする関数である。
【００９２】
ステップＵ４において、重複探索部２２は、探索位置をＤバイト分スキップする。
【００９３】
図７は、本実施形態に係る重複探索処理を例示する図である。
【００９４】
図７は、図３で説明した重複探索処理をより具体的に例示したものである。図７では、重複探索処理に用いるチャンクサイズを４バイト（４文字）として説明する。
【００９５】
状態Ｒ１は、図３のステップＳ１乃至ステップＳ３に相当する。なお、当該既存チャンクを含むファイルは、図３のステップ３において重複探索対象ファイルとして選出されたものとする。
【００９６】
状態Ｒ１において、８バイトの文字列「ＨＡＢＳＣＥＩＪ」からなる新しいファイルと、７バイトの文字列「ＡＢＣＤＥＦＧ」からなる既存チャンクとの重複探索処理が開始される。
【００９７】
状態Ｒ２は、図３のステップＳ４乃至ステップＳ７に相当する。
【００９８】
状態Ｒ２において、既存チャンクの先頭４文字のハッシュ値Ｈ（ＡＢＣＤ）と、新しいファイルの先頭４文字のハッシュ値Ｈ（ＨＡＢＣ）とが比較される。両者のハッシュ値は一致しないため、ステップＳ７の探索位置のスキップ処理が実行される。ハッシュ値Ｈ（ＡＢＣＤ）とハッシュ値Ｈ（ＨＡＢＣ）とは、１バイト（１文字）異なる。新しいファイルの探索位置はスキップ長の演算によって得られた１バイト分スキップされ、新しいハッシュ値Ｈ（ＡＢＣＤ）が算出される。ここで、当該新しいハッシュ値と既存チャンクのハッシュ値Ｈ（ＡＢＣＤ）とは一致するため、状態Ｒ３においてデータ比較が行われる。
【００９９】
状態Ｒ３は、図３のステップＳ８乃至ステップＳ１０に相当する。
【０１００】
状態Ｒ３においては、既存チャンク及び新しいファイルについて、両者のハッシュ値が一致した位置から両者のデータ（文字列）の比較が行われる。文字列を比較した結果、文字列「ＡＢＣＤＥ」が両者の一致部分として抽出されるため、状態Ｒ４において既存チャンク及び新しいファイルの分割が行われる。
【０１０１】
状態Ｒ４は、図３のステップＳ１２に相当する。
【０１０２】
状態Ｒ４において、既存チャンクの文字列「ＡＢＣＤＥＦＧ」は、状態Ｒ３でのデータ比較結果により、「ＡＢＣＤＥ」及び「ＦＧ」に分割され、分割後の結果に基づいてチャンクテーブル４が更新される。また、新しいファイルの文字列「ＨＡＢＣＤＥＩＪ」は、新しいチャンク「Ｈ」，「ＡＢＣＤＥ」及び「ＩＪ」に分割され、分割後の結果に基づいてチャンクテーブル４が更新される。さらに、新しいファイルのファイル情報５０のチャンクリスト５４には、分割された上述の３つの新しいチャンクがこの新しいファイルに含まれることを示す情報が記録される。
【０１０３】
上述のように重複排除処理が行われた結果、メモリ装置３には、「ＡＢＣＤＥ」，「ＦＧ」，「Ｈ」，「ＩＪ」の合計１０バイトの４つのチャンクが格納される。すなわち、重複排除処理の結果は、既存チャンクと新しいファイルを重複排除せずに格納した場合の合計１５バイトより、５バイト削減される。
【０１０４】
図８は、本実施形態に係るポストプロセスにおける重複探索処理の手順を例示するフローチャートである。
【０１０５】
上述の図３では、重複探索処理が新しくストレージ装置１に入力されるファイルに対して行われる場合について説明した。一方、図８では、複数のファイルをメモリ装置３に格納した後に、当該複数のファイル間で重複探索処理を行う際の手順（ポストプロセス）について説明する。当該手順により、例えば、重複排除処理が行われない既存のメモリ装置に対しても、後から重複排除処理部２、チャンクテーブル４、及びファイルテーブル５を実装して重複排除処理が実行可能となる。なお、図３と同じ手順の説明は省略する。
【０１０６】
ステップＶ１において、重複探索部２２は、メモリ装置３に格納されている全てのファイルについて、それぞれファイル全体のハッシュ値を算出し、算出したハッシュ値をファイルテーブル５に含める。より具体的には、重複探索部２２は、Ｉ／Ｏ処理部２１を経由してメモリ装置３に対してデータの読み出し要求Ｃ３を送信し、読み出したデータのハッシュ値を、ハッシュ算出部２３により算出する。重複探索部２２は、当該ハッシュ値をファイルテーブル５のファイル情報５０に含める。
【０１０７】
ステップＶ２において、重複探索部２２は、ファイルテーブル５に含まれている全てのファイル情報５０のハッシュ値５３のうち、値が近い（例えば、両者のハッシュ値の差が１０２４である等）と判断したハッシュ値５３を持つ複数のファイルを選出し、重複探索処理の対象とする。なお、両者のハッシュ値が近いか否かの判断基準は、上述のものに限られない。また、重複探索処理の対象とするファイル数には上限が設けられていてもよい。
【０１０８】
ステップＶ３において、重複探索部２２は、ステップＶ２で選出した全てのファイルに対し、先頭４ｋＢから１バイトずつずらした全てのチャンクのハッシュ値を算出する。なお、ステップＶ３で得られたチャンク及びハッシュ値は、重複探索処理のために用いる一時的な値であるため、チャンクテーブル４に含まれなくてもよい。
【０１０９】
ステップＶ４において、重複探索部２２は、ステップＶ３で得られたハッシュ値をそれぞれ比較し、ハッシュ値が一致したチャンクが存在する場合に、データを比較して重複排除処理を行う（すなわち、図３のステップＳ８乃至ステップＳ１５の処理を実行する）。
【０１１０】
図９は、本実施形態に係る重複探索処理と他の重複探索処理との対比結果を例示する図である。
【０１１１】
より具体的には、図９では、固定長による重複探索処理Ｍ１、ファイル単位の重複探索処理Ｍ２、可変長の重複探索処理Ｍ３、全探索の重複探索処理Ｍ４、及び本実施形態に係る重複探索処理Ｍ５を比較する。比較する項目は、探索時及び比較時の計算量、マッピング単位及びハッシュ値の記憶量、重複排除効率である。図中の“◎”，“○” ，“△” ，“×”は、それぞれの重複探索処理がそれぞれ比較項目ごとにどの程度優れているか否かのレベルを表す。
【０１１２】
固定長による重複探索処理Ｍ１、ファイル単位の重複探索処理Ｍ２、可変長の重複探索処理Ｍ３は、重複探索時にハッシュ値のみを比較するため、比較時の計算量は少ないが、重複探索の精度を高めるためにハッシュ値の記憶量は多くなる（例えば、１６０ビット）。
【０１１３】
一方、全探索の重複探索処理Ｍ４、及び本実施形態に係る重複探索処理Ｍ５は、重複探索時にハッシュ値及びデータを比較するため、計算量は大きいが、データ比較により重複探索の精度が高まるため、ハッシュ値の記憶量は少なくなる（例えば、３２ビット）。
【０１１４】
固定長による重複探索処理Ｍ１は、ファイル等を先頭から固定長のチャンクに区切り、チャンクごとにハッシュ値を計算し、ハッシュ値が一致するチャンクが存在した場合に、ハッシュ値が一致するチャンクの記録先を１つにまとめ、１つにまとめたチャンクを複数の参照元から参照させる処理である。固定長による重複探索処理Ｍ１では、区切り位置の探索が不要であり、チャンクの区切り位置の計算及び記憶が必要ないため、実装が容易である。しかしながら、同一内容のデータが存在しても、記録位置のオフセットがずれていると重複排除されない（すなわち、挿入に弱い）ため、重複排除効率が低い。
【０１１５】
ファイル単位の重複探索処理Ｍ２は、ファイルごとのハッシュ値を計算し、ストレージ装置内でハッシュ値が同一なファイルが存在した場合に、ハッシュ値が同一なファイルの記録先を１つにまとめ、１つにまとめたファイルを複数の参照元から参照させる処理である。ファイル単位の重複探索処理Ｍ２では、探索及びチャンクの分割が不要であるため、実装が容易である。しかしながら、完全に同一なファイルのみが重複排除の対象となるため、重複排除率が低い。
【０１１６】
可変長の重複探索処理Ｍ３は、ファイル等に含まれる特定パターン（例えば、特定の文字又は文字列）を探索し、特定パターンを区切り位置として可変長のチャンクに区切り、同一内容のチャンクが存在した場合に、同一内容のチャンクの記録先を１つにまとめ、１つにまとめたチャンクを複数のファイル等から参照させる処理である。可変長の重複探索処理Ｍ３では、記録位置のオフセットがずれたデータに対応できるため、重複排除率が高い。しかしながら、チャンクの区切り位置となる特定パターンの探索が必要である。また、特定パターンで区切られたチャンクの内容が一致しない場合（すなわち、区切り位置が適切でない場合）、同一データでも重複排除されない。さらに、特定パターンが出現した場合は重複していなくてもチャンクが分割されるため、分割数が多くなる。
【０１１７】
全探索の重複探索処理Ｍ４は、メモリ装置内のデータを全探索して部分一致している箇所を検出し、部分一致した範囲をチャンクに区切り、部分一致したチャンクの記録先を１つにまとめ、部分一致したチャンクを複数の参照元から参照させる処理である。全探索の重複探索処理Ｍ４は、全てのデータを探索して重複を検出するため、重複排除率は最大（理論上限）となる。しかしながら、すべてのファイルに対して先頭から１バイトずつずらしながらハッシュ値を計算し、部分一致を探索するため、計算量が膨大となる。
【０１１８】
本実施形態に係る重複探索処理Ｍ５は、図１乃至図８を用いて説明した処理を実行する。本実施形態に係る重複探索処理Ｍ５は、全探索の重複探索処理Ｍ４に比べ、探索対象となるファイルを絞り込むこと、及びハッシュ値の比較により探索時にスキップ処理を行うことにより、探索時の計算量を低減している。また、絞り込んだ探索対象となるファイル間では、全探索の重複探索処理Ｍ４と同じく重複排除効率は最大となる。
【０１１９】
以下では、文字列Ｊ「I_control_myself」及び文字列Ｋ「I_lose_my_self-control」に対し、可変長の重複探索処理Ｍ３を用いた場合と本実施形態に係る重複探索処理Ｍ５を用いた場合との差異について説明する。
【０１２０】
可変長の重複探索処理Ｍ３を用いた場合、例えば、「_」を特定パターンとして文字列Ｊ及び文字列Ｋを分割した場合は、文字列「control」は重複排除されない。また、「_」及び「-」を特定パターンとして文字列Ｊ及び文字列Ｋを分割した場合は、文字列「control」は重複排除されるが、文字列「my」と文字列「self」は重複排除されない。
【０１２１】
これに対し、本実施形態に係る重複探索処理Ｍ５を用いて例えば３文字単位で探索する場合、まず文字列Ｊを先頭の３文字より１バイトずつずらした３文字ずつの文字列（例えば、文字列「I_c」、文字列「_co」、文字列「con」）に対してハッシュ値が算出される。次に、文字列Ｋについて先頭の３文字の文字列「I_l」から順にハッシュ値が算出され、上述のハッシュ値と比較される。ハッシュ値が一致する場合は、ハッシュ値が一致する位置からデータの比較が行われ、データが一致する部分について重複排除される。例えば、文字列Ｊに含まれる３文字の文字列「ol_」と文字列Ｋに含まれる３文字の文字列「_lo」とはハッシュ値が一致するが、データを比較すると異なるため、重複排除されない。最終的に、文字列Ｊ及び文字列Ｋのうち、文字列「_my」、文字列「self」、文字列「control」の３つが重複排除される。
【０１２２】
以上説明した本実施形態において、重複探索部２２は、重複探索処理において、特定パターンによる区切りを用いず、データのうちの一致する部分の先頭及び末尾でデータをチャンクに区切ることができ、重複排除効率を向上させる。また、本実施形態においては、データの比較とハッシュ値の比較を併用することで、ハッシュ値の記憶量を抑えつつ、重複探索の精度を向上する。
【０１２３】
本実施形態において、重複探索部２２は、局所性鋭敏型ハッシュの性質を持つハッシュ関数を用いてファイル全体のハッシュ値を計算し、算出されたハッシュ値をファイル間で比較することで、類似するファイルを抽出する。これにより、重複探索処理を行う対象が絞り込まれ、計算量が削減される。より具体的には、算出されたハッシュ値が大きく異なる場合、重複の可能性は低いとして探索を省略できる。例えば、メモリ装置３に格納されている１００万ファイルの中から、重複排除の対象となるファイルを１００ファイルに絞る場合、計算量は１万分の１に削減される。
【０１２４】
本実施形態において、重複探索部２２は、局所性鋭敏型ハッシュの性質及びローリングハッシュの性質を併せて持つハッシュ関数を用いる。重複探索部２２は、局所性鋭敏型ハッシュの性質を利用して、重複探索処理時にハッシュ値の差分に応じて重複探索をスキップすることにより、ハッシュ値及びデータの比較回数を削減可能である。また、ローリングハッシュの性質により、ハッシュ算出部２３はハッシュ値算出の計算量を低減可能である。
【０１２５】
さらに、本実施形態においては、重複判定に局所性鋭敏型ハッシュの性質を持たないローリングハッシュが併用されることで、異なったデータに対してハッシュ値が同じとなることを避けることができる。これにより、重複探索の効率をより高めることが可能となる。
【０１２６】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０１２７】
１…ストレージ装置、２…重複排除処理部、３…メモリ装置、４…チャンクテーブル、５…ファイルテーブル、７…第１の記憶部、８…第２の記憶部、２１…Ｉ／Ｏ処理部、２２…重複探索部、２２ａ…第１の判断部、２２ｂ…決定部、２２ｃ…重複排除部、２３…ハッシュ算出部、２４…マッピング管理部、２５…データ比較部、２５ａ…第２の判断部、４０…チャンク情報、４１…チャンクＩＤ、４２…チャンクサイズ、４３…ハッシュ値、４４…参照数、５０…ファイル情報、５１…ファイルＩＤ、５２…ファイルサイズ、５３…ハッシュ値、５４…チャンクリスト、Ｃ１…Ｉ／Ｏ要求、Ｃ２…マッピング取得要求、Ｃ３，Ｃ１１，Ｃ１２…読み出し又は書き込み要求、Ｃ４…重複排除要求、Ｃ５…ハッシュ値算出要求、Ｃ６…チャンク情報の読み出し要求、Ｃ７…ファイル情報の読み出し要求、Ｃ８…データ比較要求、Ｃ９…読み出し要求、Ｃ１０…マッピング更新要求。
【図１】
2018045305.tif 000004
【図２】
2018045305.tif 000005
【図３】
2018045305.tif 000006
【図４】
2018045305.tif 000007
【図５】
2018045305.tif 000008
【図６】
2018045305.tif 000009
【図７】
2018045305.tif 000010
【図８】
2018045305.tif 000011
【図９】
2018045305.tif 000012