(57)【要約】データ管理システムは、データブロックの開始位置から所定サイズ分までの所定範囲について、ウインドウを所定量ずつ移動させながら第１ハッシュ値をそれぞれ算出する。システムは、各第１ハッシュ値のうち特徴値に該当する第１ハッシュ値を抽出し、その第１ハッシュ値に対応する位置で、データブロックを第１チャンクデータに分割する。システムは、第１チャンクデータと、記憶済の第２チャンクデータとの同一性を判定し、重複したデータが二重に保存されるのを防止する。【選択図】図１
2014514618.tif 000002
【特許請求の範囲】
【請求項１】
データブロックを可変長で分割して管理するデータ管理方法であって、
（ａ１）前記データブロックの所定の開始位置から所定サイズ分までの所定範囲について、ハッシュ値を算出するための算出用領域を所定量ずつ移動させながら、前記算出用領域内のデータと所定の第１ハッシュ関数とに基づいて、前記算出用領域内のデータ毎に第１ハッシュ値をそれぞれ算出し、
（ａ２）前記所定範囲内で得られる前記各第１ハッシュ値のうち、所定の基準に基づいて相対的に決定される特徴値に該当する第１ハッシュ値を抽出し、
（ａ３）前記特徴値に該当する前記第１ハッシュ値に対応する位置で前記データブロックを分割することにより、第１チャンクデータを取得し、
（ａ４）分割後の前記データブロックについて、前記ａ１，ａ２，ａ３の処理を繰り返し実行することにより、元の前記データブロック全体を複数の前記第１チャンクデータに分割して管理する、
データの管理方法。
【請求項２】
前記特徴値は、前記所定範囲内で得られる前記各第１ハッシュ値の中での、最小値または最大値のいずれかである、
請求項１に記載のデータの管理方法。
【請求項３】
前記算出用領域内のデータに基づいて得られる前記第１ハッシュ値が、前記特徴値の理論的限界値として予め設定される値に一致する場合は、その理論的限界値に一致する前記第１ハッシュ値に対応する位置で前記データブロックを分割することにより、第１チャンクデータを生成する、
請求項２に記載のデータの管理方法。
【請求項４】
前記所定の開始位置は、前記データブロックの先頭位置に所定の下限値を加えた値として設定される、
請求項３に記載のデータの管理方法。
【請求項５】
前記データブロックの全体サイズが所定の上限値に満たない場合、前記データブロックの全体を前記第１チャンクデータとする、
請求項４に記載のデータの管理方法。
【請求項６】
さらに、
（ｂ１）前記各第１チャンクデータと所定の第２ハッシュ関数とに基づいて、前記各第１チャンクデータ毎に第２ハッシュ値をそれぞれ算出し、
（ｂ２）記憶部に記憶されている複数の第２チャンクデータの第２ハッシュ値と前記各第１チャンクデータの前記第２ハッシュ値とを比較することにより、前記第１チャンクデータの前記第２ハッシュ値と一致する第２ハッシュ値が前記記憶部に記憶されているか否かを判定する、
請求項５に記載のデータの管理方法。
【請求項７】
さらに、
（ｃ１）前記各第１チャンクデータのうち、当該第１チャンクデータついて算出される前記第２ハッシュ値が前記各第２チャンクデータの前記第２ハッシュ値のいずれとも一致しない新規の第１チャンクデータは、前記新規の第１チャンクデータの格納先と当該新規の第１チャンクデータの前記データブロックにおける元の位置とを対応付けて、前記記憶部に前記第２チャンクデータとして記憶させ、
（ｃ２）前記各第１チャンクデータのうち、当該第１チャンクデータについて算出される前記第２ハッシュ値が前記各第２チャンクデータの前記第２ハッシュ値のいずれかと一致する、記憶済の第１チャンクデータは、前記記憶済の第１チャンクデータに一致する前記第２チャンクデータの格納先と前記記憶済の第１チャンクデータの前記データブロックにおける元の位置とを対応付けて、前記記憶部に記憶させ、
（ｃ３）前記各第２チャンクデータの格納先と前記各第２チャンクデータについて算出される前記第２ハッシュ値とを対応付けて、前記記憶部に記憶させる、
請求項６に記載のデータの管理方法。
【請求項８】
前記データブロックは、データブロックを記憶するためのデータブロック記憶部にいったん蓄積された後で、所定の指示に基づいて、前記各第１チャンクデータに分割される、請求項７に記載のデータの管理方法
【請求項９】
前記データブロックを受信しながら、前記データブロックを前記各第１チャンクデータに分割する、
請求項７に記載のデータの管理方法。
【請求項１０】
コンピュータがデータブロックを可変長で分割して管理するデータ管理方法であって、
前記コンピュータは、所定のコンピュータプログラムを記憶するメモリと、前記所定のコンピュータプログラムを実行するマイクロプロセッサとを備え、
前記マイクロプロセッサは、前記所定のコンピュータプログラムに基づいて、
（Ａ）前記データブロックを、前記複数の第１チャンクデータに可変長で分割する分割処理と、
（Ｂ）前記各第１チャンクデータと、記憶部に記憶されている複数の第２チャンクデータとを比較し、前記各第１チャンクデータが前記各第２チャンクデータのうちのいずれかに一致するか否かを判定し、
（Ｃ）前記各第１チャンクデータのうち前記各第２チャンクデータのいずれとも一致しない新規の第１チャンクデータは、前記新規の第１チャンクデータの格納先と当該新規の第１チャンクデータの前記データブロックにおける元の位置とを対応付けて、前記記憶部に記憶させ、前記各第１チャンクデータのうち前記各第２チャンクデータのいずれかと一致する記憶済の第１チャンクデータは、前記記憶済の第１チャンクデータに一致する前記第２チャンクデータの格納先と前記記憶済の第１チャンクデータの前記データブロックにおける元の位置とを対応付けて、前記記憶部に記憶させる、データ管理処理と、
を実行し、
前記分割処理は、
（ａ１）前記データブロックの前記所定の開始位置から前記所定サイズ分までの前記所定範囲について、前記算出用領域を所定量ずつ移動させながら、前記算出用領域内のデータと前記所定の第１ハッシュ関数とに基づいて、前記算出用領域内のデータ毎に前記第１ハッシュ値をそれぞれ算出し、
（ａ２）前記所定範囲内で得られる前記各第１ハッシュ値の中から、最小値または最大値のうちいずれか一方に予め指定される特徴値に該当する第１ハッシュ値を抽出し、
（ａ３）前記特徴値に該当する前記第１ハッシュ値に対応する位置で前記データブロックを分割することにより、前記第１チャンクデータを取得し、
（ａ４）分割後の前記データブロックについて前記ａ１，ａ２，ａ３の処理を繰り返し実行することにより、元の前記データブロック全体を複数の前記第１チャンクデータに分割し、
前記重複検出処理は、
（ｂ１）前記各第１チャンクデータと所定の第２ハッシュ関数とに基づいて、前記各第１チャンクデータ毎に第２ハッシュ値をそれぞれ算出し、
（ｂ２）前記記憶部に記憶されている前記各第２チャンクデータの第２ハッシュ値と前記各第１チャンクデータの前記第２ハッシュ値とを比較することにより、前記第１チャンクデータの前記第２ハッシュ値と一致する第２ハッシュ値が前記記憶部に記憶されているか否かを判定し、
前記データ管理処理は、
（ｃ１）前記各第１チャンクデータのうち、当該第１チャンクデータついて算出される前記第２ハッシュ値が前記各第２チャンクデータの前記第２ハッシュ値のいずれとも一致しない前記新規の第１チャンクデータは、前記新規の第１チャンクデータの格納先と当該新規の第１チャンクデータの前記データブロックにおける元の位置とを対応付けて、前記記憶部に前記第２チャンクデータとして記憶させ、
（ｃ２）前記各第１チャンクデータのうち、当該第１チャンクデータについて算出される前記第２ハッシュ値が前記各第２チャンクデータの前記第２ハッシュ値のいずれかと一致する、前記記憶済の第１チャンクデータは、前記記憶済の第１チャンクデータに一致する前記第２チャンクデータの格納先と前記記憶済の第１チャンクデータの前記データブロックにおける元の位置とを対応付けて、前記記憶部に記憶させ、
（ｃ３）前記各第２チャンクデータの格納先と前記各第２チャンクデータについて算出される前記第２ハッシュ値とを対応付けて、前記記憶部に記憶させる、
請求項１に記載のデータの管理方法。
【請求項１１】
データブロックを可変長で分割して管理するデータ管理システムであって、
（Ａ）前記データブロックを、複数の第１チャンクデータに可変長で分割する分割処理部と、
（Ｂ）前記各第１チャンクデータと、記憶部に記憶されている複数の第２チャンクデータとを比較し、前記各第１チャンクデータが前記各第２チャンクデータのうちのいずれかに一致するか否かを判定し、
（Ｃ）前記各第１チャンクデータのうち前記各第２チャンクデータのいずれとも一致しない新規の第１チャンクデータは、前記新規の第１チャンクデータの格納先と当該新規の第１チャンクデータの前記データブロックにおける元の位置とを対応付けて、前記記憶部に前記第２チャンクデータとして記憶させ、前記各第１チャンクデータのうち前記各第２チャンクデータのいずれかと一致する記憶済の第１チャンクデータは、前記記憶済の第１チャンクデータに一致する前記第２チャンクデータの格納先と前記記憶済の第１チャンクデータの前記データブロックにおける元の位置とを対応付けて、前記記憶部に記憶させる、データ管理処理部と、
を備え、
前記分割処理部は、
（ａ１）前記データブロックの所定の開始位置から所定サイズ分までの所定範囲について、ハッシュ値を算出するための算出用領域を所定量ずつ移動させながら、前記算出用領域内のデータと所定の第１ハッシュ関数とに基づいて、前記算出用領域内のデータ毎に第１ハッシュ値をそれぞれ算出し、
（ａ２）前記所定範囲内で得られる前記各第１ハッシュ値のうち、所定の基準に基づいて相対的に決定される特徴値に該当する第１ハッシュ値を抽出し、
（ａ３）前記特徴値に該当する前記第１ハッシュ値に対応する位置で前記データブロックを分割することにより、第１チャンクデータを取得し、
（ａ４）分割後の前記データブロックについて、前記ａ１，ａ２，ａ３の処理を繰り返し実行することにより、元の前記データブロック全体を複数の前記第１チャンクデータに分割して管理する、
データ管理システム。
【請求項１２】
前記各第１チャンクデータに分割される前のデータブロックを記憶するためのデータブロック記憶部は、前記記憶部とは別に存在する、
請求項１１に記載のデータ管理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ管理方法及びデータ管理システムに関する。
【背景技術】
【０００２】
企業等で管理される多数のファイルは、他のいずれかのファイルと、完全にまたは部分的に一致することがある。例えば、ファイルのバックアップを何度も繰り返すと、同一ファイルが多数作成される。さらに、既存ファイルの一部を更新して新規ファイルを作成する場合、新規ファイルのうちの多くの部分は、既存ファイルに一致する。このようなファイルの重複が多数生じると、記憶資源が無駄に消費される。
【０００３】
そこで、ファイルの重複を検出して排除する技術が提案されている。従来技術では、ファイルを可変長で分割し、分割されたデータ毎にハッシュ値を算出して、データの重複を検出する（特許文献１）。
【０００４】
その従来技術では、ファイルの先頭から所定サイズ毎にハッシュ値を算出し、そのハッシュ値が予め設定される固定値と一致するか否かを判定する。ハッシュ値が固定値に一致すると、その部分でファイルを分割する。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】米国特許第５９９０８１０号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００６】
従来技術では、ファイルを可変長で分割することにより、データの重複を排除するようになっている。ファイルを固定長で分割する場合に比べて、ファイルを可変長で分割する方が、一般的に、データの重複を排除する効率が高い。
【０００７】
しかし、従来技術では、ハッシュ値と固定値が適切なサイズで一致する保証はない。ハッシュ値が固定値になかなか一致しない場合、ファイルの分割サイズが大きくなる。分割サイズが大きくなるほど、記憶済のデータと一致する可能性が低くなるため、重複を排除する効率が低下する。
【０００８】
本発明は上記の問題に鑑みてなされたもので、その目的は、データを比較的適切なサイズで分割して管理することのできるデータ管理方法及びデータ管理システムを提供することにある。本発明の他の目的は、データを所定サイズに近いサイズに分割し、重複データを効率的に排除して、データを管理できるデータ管理方法及びデータ管理システムを提供することにある。
【課題を解決するための手段】
【０００９】
本発明に従うデータ管理方法は、データブロックを可変長で分割して管理するデータ管理方法であって、（ａ１）データブロックの所定の開始位置から所定サイズ分までの所定範囲について、ハッシュ値を算出するための算出用領域を所定量ずつ移動させながら、算出用領域内のデータと所定の第１ハッシュ関数とに基づいて、算出用領域内のデータ毎に第１ハッシュ値をそれぞれ算出し、（ａ２）所定範囲内で得られる各第１ハッシュ値のうち、所定の基準に基づいて相対的に決定される特徴値に該当する第１ハッシュ値を抽出し、（ａ３）特徴値に該当する第１ハッシュ値に対応する位置でデータブロックを分割することにより、第１チャンクデータを取得し、（ａ４）分割後のデータブロックについて、ａ１，ａ２，ａ３の処理を繰り返し実行することにより、元のデータブロック全体を複数の第１チャンクデータに分割して管理する。
【００１０】
特徴値は、所定範囲内で得られる各第１ハッシュ値の中での、最小値または最大値のいずれかであってもよい。
【００１１】
算出用領域内のデータに基づいて得られる第１ハッシュ値が、特徴値の理論的限界値として予め設定される値に一致する場合は、その理論的限界値に一致する第１ハッシュ値に対応する位置でデータブロックを分割することにより、第１チャンクデータを生成してもよい。
【００１２】
所定の開始位置は、データブロックの先頭位置に所定の下限値を加えた値として設定されてもよい。
【００１３】
データブロックの全体サイズが所定の上限値に満たない場合、データブロックの全体を第１チャンクデータとしてもよい。
【００１４】
本発明は、データを管理するプログラムとして把握してもよい。そのコンピュータプログラムは、通信媒体または記録媒体を介して流通させることができる。
【図面の簡単な説明】
【００１５】
【図１】図１は、本実施形態の全体概要を示す説明図。
【図２】図２は、データ管理システムの構成図。
【図３】図３は、チャンクデータからファイルを復元するために使用するファイル格納情報の構成例。
【図４】図４は、チャンクデータを管理するインデックス情報の構成例。
【図５】図５は、全体の流れを示すフローチャート。
【図６】図６は、ハッシュ値に基づいてデータブロックとしてのファイルデータを分割する様子を模式的に示す説明図。
【図７】図７は、ウインドウの設定位置の他の例を示す説明図。
【図８】図８は、ファイルを分割する処理を示すフローチャート。
【図９】図９は、重複データを検出して排除する処理を示すフローチャート。
【図１０】図１０は、第２実施例に係り、ファイルを分割する処理を示すフローチャート。
【図１１】図１１は、第３実施例に係り、データ管理システムの全体を示す構成図。
【図１２】図１２は、全体の流れを示すフローチャート。
【発明を実施するための形態】
【００１６】
以下、図面に基づいて、本発明の実施形態を説明する。本実施形態では、以下のように、データブロックの一例としてのファイルデータの分割位置を検出するための複数の第１ハッシュ値の中から、その中に少なくとも一つ以上必ず存在する特徴値に該当する、第１ハッシュ値を検出する。特徴値としては、最小値または最大値のいずれかを用いることができる。複数の第１ハッシュ値の群には、その中で最も小さい値の第１ハッシュ値（最小値）と、その中で最も大きい値の第２ハッシュ値（最大値）とが、一つ以上含まれる。最小値または最大値が複数存在する場合、例えば、いずれか早く検出された方を採用することができる。
【００１７】
図１は、本実施形態の全体概要を示す。図１には、データ分割処理Ｓ１と、重複検出処理Ｓ２と、データ管理処理Ｓ３とが示されている。データ分割処理Ｓ１は、ファイルデータを分割する処理である。重複検出処理Ｓ２は、分割されたファイルデータから重複するデータを検出する処理である。データ管理処理Ｓ３は、ファイルデータを分割して管理する処理である。
【００１８】
データ分割処理Ｓ１を説明する。データ分割処理Ｓ１は、例えば、開始位置決定処理Ｓ１０と、第１ハッシュ値算出処理Ｓ１１と、ウインドウ移動処理Ｓ１２と、特徴値検出処理Ｓ１３と、分割位置決定処理Ｓ１４とを含む。
【００１９】
開始位置決定処理Ｓ１０は、第１ハッシュ値を算出する処理を開始する位置ＨＳを決定する。点線で示すウインドウＷは、第１ハッシュ値を算出するための「算出用領域」に該当する。ウインドウサイズＷＬは、例えば、４８バイト程度に設定してもよい。
【００２０】
Ｓ１０は、ファイルデータの先頭（ＳｏＦ）から下限値ＬＳだけ後ろの位置を、開始位置ＨＳとして決定する。下限値ＬＳは、例えば、４キロバイト程度に設定してもよい。
【００２１】
第１ハッシュ値算出処理Ｓ１１は、ウインドウ内に含まれるデータ（例えば、４８バイのデータ）を第１ハッシュ関数ｆ（ｘ）に入力して、第１ハッシュ値を算出する。
【００２２】
ウインドウ移動処理Ｓ１２は、第１ハッシュ値の算出された後で、ウインドウを所定量だけファイルデータの後側に向けて移動させる。ウインドウ移動処理Ｓ１２は、開始位置ＨＳから所定サイズＰＬだけ離れた終了位置ＨＥまでの所定範囲を、ウインドウを所定量ずつ移動させる。ウインドウは、例えば、１バイトずつ移動する。所定サイズＰＬは、例えば、８キロバイト程度に設定してもよい。
【００２３】
ウインドウが移動するたびに、第１ハッシュ値算出処理Ｓ１１は、ウインドウ内のデータについての第１ハッシュ値を算出する。従って、開始位置ＨＳから終了位置ＨＥまでの所定範囲のデータについて、複数の第１ハッシュ値が算出されて保持される。
【００２４】
特徴値検出処理Ｓ１３は、保持された複数の第１ハッシュ値の中から、所定の基準に基づいて相対的に決定される特徴値に該当する第１ハッシュ値を検出する。
【００２５】
所定の基準とは、例えば、複数の第１ハッシュ値の中から最も小さい値を選ぶこと、または、最も大きい値を選ぶことである。相対的に決定されるとは、予め設定される固定値ではなく、複数の第１ハッシュ値の中から相対的に選ばれる値であること、である。
【００２６】
例えば、特徴値として最小値を例に挙げると、”１，２，３，４”という第１ハッシュ値の群では、”１”が最小値になる。さらに、”７，８，９，７”という他の第１ハッシュ値の群では、”７”が最小値となる。このように、特徴値は、複数の第１ハッシュ値の中に少なくとも一つ以上必ず存在する。特徴値が最大値である場合も同様である。
【００２７】
分割位置決定処理Ｓ１４は、特徴値に該当する第１ハッシュ値に対応する位置を分割位置ＤＰとする。ファイルデータは、分割位置ＤＰで分割されることにより、第１チャンクデータとなる。
【００２８】
分割後の残されたファイルデータの開始位置に、再びウインドウが設定される。そして、再び、最終位置ＨＥまで所定量ずつウインドウをずらしながら、ウインドウ内のデータについて第１ハッシュ値を算出する。各第１ハッシュ値の中から特徴値に該当する位置が分割位置ＤＰとして設定される。
【００２９】
以上の処理を繰り返すことにより、ファイルデータは、複数の第１チャンクデータに分割される。
【００３０】
なお、ウインドウサイズＷＬは４８バイト、下限値を４キロバイト、所定サイズＰＬを８キロバイトとして述べたが、これらの数値は例示である。他の数値を採用することもできる。さらに、図１では、説明の便宜のために、ウインドウサイズを２バイト、所定サイズを４バイトとして、示している。ウインドウは、１バイトずつ移動する。図１中のｆ０，ｆ１，ｆ２，ｆ３等の値は、第１ハッシュ関数ｆ（ｘ）から得られた第１ハッシュ値であることを示す。
【００３１】
データ分割処理Ｓ１では、下限値ＬＳ未満の第１チャンクデータは、生成されない。第１チャンクデータのサイズは、下限値ＬＳから下限値ＬＳに所定サイズＰＬを加えた値までの範囲の値となる（ＬＳ≦チャンクサイズ≦ＬＳ＋ＰＬ）。従って、本実施形態では、ファイルデータが下限値ＬＳ未満の小さいサイズで分割されたり、（ＬＳ＋ＰＬ）よりも大きいサイズで分割されたりするのを防止できる。つまり、第１チャンクデータのサイズを一定範囲に収めることができる。この結果、ファイルデータのうち重複しているデータを効率的に検出して、少ない記憶資源で効率的に管理することができる。
【００３２】
重複検出処理Ｓ２を説明する。重複検出処理Ｓ２では、各第１チャンクデータ毎に第２ハッシュ値を算出する。即ち、第１チャンクデータを第２ハッシュ関数ｇ（ｘ）に入力することにより、第２ハッシュ値を得る。
【００３３】
重複検出処理Ｓ２は、各第１チャンクデータの第２ハッシュ値と、記憶部に記憶されている各第２チャンクデータの第２ハッシュ値とが一致するか否かを判定する。
【００３４】
図１では、第１チャンクデータに符号Ｃａを付し、第２チャンクデータに符号Ｃｂを付している。ｄ１，ｄ２，ｄ３，ｄ４等は、１バイト毎のデータを示す。図示の例では、例えば、３番目の第１チャンクデータＣａ３のデータｄ３とｄ５から、第２ハッシュ値ｇ３が算出されている。
【００３５】
対象のファイルデータＤａの各第１チャンクデータＣａについての第２ハッシュ値と、システムに既に記憶されている第２チャンクデータＣｂについての第２ハッシュ値とを比較すれば、重複しているチャンクデータが判明する。
【００３６】
例えば、第１チャンクデータＣａ１，Ｃａ３，Ｃａ４，Ｃａ５，Ｃａ６は、第２チャンクデータＣｂ１，Ｃｂ３，Ｃｂ４，Ｃｂ５，Ｃｂ６と同一である。互いの第２ハッシュ値が一致するためである。
【００３７】
これに対し、２番目の第１チャンクデータＣａ２の第２ハッシュ値（ｇ２）と、２番目の第２チャンクデータＣｂ２の第２ハッシュ値（ｇ７）とは一致しない。従って、第１チャンクデータＣａ２と第２チャンクデータＣｂ２とは、異なる。
【００３８】
第２ハッシュ値が異なる理由は、対象のファイルデータＤａの第１チャンクデータＣａ２では、更新前の古いファイルデータＤｂの第２チャンクデータＣｂ２に比べて、太線で囲むデータ（ｄ４）を備えていないためである。
【００３９】
このように本実施形態では、データが追加または変更または削除された部分（チャンク）を検出することができる。データ管理処理Ｓ３の詳細は後述する。
【実施例１】
【００４０】
図２〜図９を参照して第１実施例を説明する。図２は、データ管理システムの一例としてのファイルデータ管理システム１０の全体構成を示す。ファイルデータ管理システム１０は、例えば、ＮＡＳ（Network Attached Storage）サーバ２０と、第１ストレージ装置３０と、第２ストレージ装置４０とを備えることができる。
【００４１】
ＮＡＳサーバ２０は、例えば、マイクロプロセッサ２１と、メモリ２２と、通信インターフェース（図示せず）とを備える。メモリ２２には、重複排除プログラムＰ２０と、マイグレーションプログラムＰ２１とが記憶されている。
【００４２】
重複排除プログラムＰ２０は、ファイルデータの重複を検出して排除し、ファイルデータをチャンクデータに分割して管理するためのコンピュータプログラムである。その詳細は後述する。
【００４３】
マイグレーションプログラムＰ２１は、第２ストレージ装置４０に記憶されたファイルデータを、重複排除プログラムＰ２１に引き渡すコンピュータプログラムである。
【００４４】
第１ストレージ装置３０は、例えば、チャンクデータ３１０と、チャンクインデックス情報３２０と、ファイル格納情報３３０とを記憶する。チャンクインデックス情報３２０及びファイル格納情報３３０については、後述する。
【００４５】
第２ストレージ装置４０は、管理対象のファイルデータ４１０を記憶する。なお、第１ストレージ装置３０と第２ストレージ装置４０とは、同一であってもよい。
【００４６】
ストレージ装置としては、例えば、ハードディスクドライブ、光ディスクドライブ、フラッシュメモリデバイス等の種々の装置を用いることができる。さらに、他のＮＡＳをストレージ装置として使用する構成でもよい。
【００４７】
クライアントコンピュータ５０は、ＮＡＳサーバ２０に接続されている。クライアントコンピュータ５０は、ストレージ装置６０に記憶されたファイルデータ４１０を、ＮＡＳサーバ２０に送信して、管理を依頼する。ＮＡＳサーバ２０は、クライアントコンピュータ５０から受領したファイルデータ４１０を、第２ストレージ装置４０に格納する。
【００４８】
図３は、ファイル格納情報３３０の例を示す。ファイル格納情報３３０は、各ファイルデータ４１０毎にそれぞれ用意される。ファイル格納情報３３０は、ファイルデータ４１０の各部分に対応するチャンクデータが、管理システム１０内のどこに記憶されているのかを管理するための管理情報である。
【００４９】
ファイル格納情報３３０は、例えば、オフセット３３１と、チャンク格納場所３３２とを各チャンクデータ毎に対応付けて管理する。オフセット３３１は、チャンクデータのファイルデータにおける位置（元々の位置）を示す情報である。オフセット３３１は、ファイルデータの先頭アドレスからのオフセット値を示す。
【００５０】
チャンク格納場所３３２は、チャンクデータの格納場所を示す情報である。チャンク格納場所は、格納先アドレスでもよいし、格納先アドレスに対応付けられるポインタのような情報でもよい。
【００５１】
図４は、チャンクインデックス情報３２０の例を示す。チャンクインデックス情報３２０は、ファイルデータ管理システム１０内に一つ設けられる。チャンクインデックス情報３２０は、ハッシュ値３２１と、チャンク格納場所３２２とを対応付けて管理する。
【００５２】
ハッシュ値３２１は、チャンクデータ３１０について算出される第２ハッシュ値であり、チャンクデータ間の同一性を判断するために使用される。チャンク格納場所３２２は、図３で述べたチャンク格納場所３３２と同一である。
【００５３】
図５は、ファイルデータ管理システム１０の全体動作を示すフローチャートである。以下、ステップを「Ｓ」と略記する。本処理を含む以下の各処理は、マイクロプロセッサ２１がメモリ２２に記憶されたコンピュータプログラムＰ２０を実行することにより、実現される。従って、以下の各処理の主語は、プログラムであってもよいし、マイクロプロセッサであってもよい。あるいは、以下の各処理の主語を、管理システム１０またはＮＡＳサーバ２０としてもよい。
【００５４】
管理システム１０は、クライアントコンピュータ５０から送信されるファイルデータ４１０を受信し、第２ストレージ装置４０に保存する（Ｓ１００）。
【００５５】
管理システム１０は、データの重複排除を指示されたか否か判定する（Ｓ２００）。重複排除の指示方法には、複数ある。例えば、クライアントコンピュータ５０は、ファイルデータ４１０を管理システム１０に送信した後で、重複排除を指示するためのコマンドを管理システム１０に送信することができる。あるいは、管理システム１０は、図外の他のコンピュータから、重複排除の指示を受領することもできる。さらに、管理システム１０は、負荷の少ない時間帯を選んで、重複排除を自ら指示することもできる。
【００５６】
重複排除が指示されると（Ｓ２００：ＹＥＳ）、管理システム１０は、マイグレーションプログラムＰ２１により、第２ストレージ装置４０に記憶されたファイルデータ４１０を、重複排除プログラムＰ２０に引き渡させる。
【００５７】
重複排除プログラムＰ２０は、入力されたファイルデータ４１０について、ファイル分割処理（Ｓ３００）を実行し、その後で重複排除処理（Ｓ４００）を実行する。ファイル分割処理及び重複排除処理については、図８，図９で後述する。
【００５８】
図６は、ファイルデータ４１０を分割する方法を模式的に示す。図１でも述べたように、ファイルデータ４１０の先頭（ＳｏＦ）から下限値ＬＳだけ後ろの開始位置ＨＳに、ウインドウＷを設定する。
【００５９】
ウインドウを１バイトずつ一定方向（ファイルの終端側）に移動させながら、ウインドウ内のデータを第１ハッシュ関数ｆ（ｘ）に入力して、第１ハッシュ値を算出する。管理システム１０は、ウインドウを開始位置ＨＳから終了位置ＨＥまでの所定範囲（所定サイズＰＬ分のファイルデータ）だけ移動させる。
【００６０】
これにより、図６の下側に白丸で示すように、複数の第１ハッシュ値が得られる。管理システム１０は、図中黒丸で示すように、それら第１ハッシュ値のうち、特徴値（最小値または最大値のいずれか一つ）に該当する第１ハッシュ値に対応する位置を、分割位置ＤＰとして選択する。
【００６１】
なお、図６では、ウインドウの右端を基準として、開始位置ＨＳ及び終了位置ＨＥに一致させる。これに代えて、図７のように、ウインドウの左端を基準にしてもよい。
【００６２】
図８を参照してファイル分割処理Ｓ３００の詳細を説明する。以下、説明の便宜上、重複排除プログラムＰ２０をプログラムＰ２０と略記する場合がある。
【００６３】
プログラムＰ２０は、対象とするファイルデータのサイズが、下限値ＬＳと所定サイズＰＬとの合計値以上であるか否かを判定する（Ｓ３０１）。
【００６４】
下限値ＬＳは、チャンクデータの下限サイズを規定する値である。所定サイズＰＬは、ウインドウの最大移動範囲を規定する値である。従って、下限値ＬＳと所定サイズＰＬの合計値は、チャンクデータの上限サイズを示す。
【００６５】
ファイルデータのサイズが下限値ＬＳと所定サイズＰＬの合計値以上である場合（Ｓ３０１：ＹＥＳ）、対象ファイルデータを複数のチャンクデータに分割可能である。従って、プログラムＰ２０は、ウインドウの位置を開始位置ＨＳに設定する（Ｓ３０２）。ウインドウの基準を右端にする場合、開始位置ＨＳは、図６に示すように、ファイルデータの先頭から（ＬＳ−ＷＬ）だけ後ろの位置である。
【００６６】
プログラムＰ２０は、ウインドウ内のデータを第１ハッシュ関数ｆ（ｘ）に入力して、第１ハッシュ値を算出する（Ｓ３０３）。プログラムＰ２０は、ウインドウを１バイト右側にシフトさせる（Ｓ３０４）。プログラムＰ２０は、シフト後のウインドウ位置が終了位置ＨＥに到達したか否かを判定する（Ｓ３０５）。終了位置ＨＥは、図６に示すように、開始位置ＨＳから所定サイズＰＬだけ後ろの位置である。
【００６７】
ウインドウ位置が終了位置ＨＥに到達していない場合（Ｓ３０５：ＮＯ）、プログラムＰ２０は、Ｓ３０３に戻り、ウインドウ内のデータから第１ハッシュ値を算出し、さらに、ウインドウを１バイトだけ右にシフトさせる（Ｓ３０４）。このように、プログラムＰ２０は、ウインドウ位置が終了位置ＨＥに到達するまで、Ｓ３０２〜Ｓ３０４を繰り返し実行する。
【００６８】
ウインドウ位置が終了位置ＨＥに到達すると（Ｓ３０５：ＹＥＳ）、プログラムＰ２０は、Ｓ３０３で取得された複数の第１ハッシュ値の中から、特徴値に該当する第１ハッシュ値を検索する。プログラムＰ２０は、特徴値に該当する第１ハッシュ値に対応するデータ位置を、分割位置ＤＰとして設定する（Ｓ３０６）。
【００６９】
プログラムＰ２０は、分割位置ＤＰでファイルデータを分割する（Ｓ３０７）。分割位置ＤＰを境として左右に分割されたファイルデータのうち、左側のデータ（前側のデータ）をチャンクデータとする。
【００７０】
プログラムＰ２０は、ファイルデータからチャンクデータを一つ切り出した後（Ｓ３０７）、Ｓ３０１に戻る。プログラムＰ２０は、Ｓ３０１〜Ｓ３０７を繰り返し実行することにより、ファイルデータを複数のチャンクデータに分割していく。
【００７１】
そして、ファイルデータのサイズが下限値ＬＳと所定サイズＰＬの合計値未満になると（Ｓ３０１：ＮＯ）、プログラムＰ２０は、その残ったファイルデータの全体を一つのチャンクデータとする（Ｓ３０８）。これにより、第１ハッシュ値が無駄に算出されるのを防止できる。
【００７２】
図９を参照して重複排除処理Ｓ４００の詳細を説明する。重複排除プログラムＰ２０は、一つのファイルデータから分割された複数のチャンクデータ（第１チャンクデータ）の全てについて、以下に述べるＳ４０２〜Ｓ４０７をそれぞれ実行する（Ｓ４０１）。
【００７３】
プログラムＰ２０は、対象のチャンクデータを第２ハッシュ関数ｇ（ｘ）に入力することにより、第２ハッシュ値を算出する（Ｓ４０２）。第２ハッシュ関数ｇ（ｘ）は、第１ハッシュ関数ｆ（ｘ）と同一でもよいし、異なっていてもよい。
【００７４】
プログラムＰ２０は、第２ハッシュ値を検索キーとして、チャックインデックス情報３２０を検索する（Ｓ４０３）。プログラムＰ２０は、Ｓ４０２で算出された第２ハッシュ値と同一の第２ハッシュ値がチャンクインデックス情報３２０に存在するかを判定する（Ｓ４０４）。
【００７５】
算出された第２ハッシュ値と同一の第２ハッシュ値がチャンクインデックス情報３２０に登録されていない場合（Ｓ４０４：ＮＯ）、プログラムＰ２０は、未登録の第２ハッシュ値を有するチャンクデータを、第１ストレージ装置３０に格納する（Ｓ４０５）。
【００７６】
プログラムＰ２０は、チャンクインデックス情報３２０に、チャンクデータの格納場所とその第２ハッシュ値とを登録する（Ｓ４０６）。プログラムＰ２０は、対象ファイルデータに対応するファイル格納情報３３０に、ファイルデータにおけるチャンクデータの位置を示すオフセットと、チャンクデータの格納場所とを登録する（Ｓ４０７）。
【００７７】
対象のチャンクデータについて算出された第２ハッシュ値が、チャンクインデックス情報３２０に登録されている場合（Ｓ４０４：ＹＥＳ）を説明する。この場合、プログラムＰ２０は、その登録済の第２ハッシュ値に対応するチャンクデータの格納場所を、チャンクインデックス情報３２０から取得する（Ｓ４０８）。
【００７８】
プログラムＰ２０は、対象ファイルデータに対応するファイル格納情報３３０に、ファイルデータにおけるチャンクデータの位置を示すオフセットと、既に記憶されているチャンクデータの格納場所とを登録する（Ｓ４０７）。
【００７９】
つまり、プログラムＰ２０は、対象チャンクデータが既に管理システム１０に記憶されているか否かを、第２ハッシュ値に基づいて判定する。プログラムＰ２０は、そのチャンクデータが既に記憶されている場合、ファイル格納情報３３０に、記憶済のチャンクデータの格納場所を登録する。対象チャンクデータは管理システム１０に格納されない。記憶済のチャンクデータと重複するためである。
【００８０】
このように構成される本実施例では、開始位置ＨＳ（＝ファイル先頭位置＋ＬＳ）から終了位置ＨＥ（＝ＨＳ＋ＰＬ）までの所定範囲で、第１ハッシュ値を算出する。さらに、本実施例では、複数の第１ハッシュ値の中に必ず一つ以上含まれる特徴値を用いて、ファイルデータをチャンクデータに分割する。
【００８１】
従って、本実施例では、チャンクデータのサイズを、下限値ＬＳから上限値（＝ＬＳ＋ＰＬ）までの予定した範囲に収めることができる。このため、下限値ＬＳ未満の短すぎるチャンクデータが生じたり、上限値を超えた長すぎるチャンクデータが生じたりするのを防止できる。従って、本実施例では、重複データの検出精度を高めて、重複データを効率的に排除でき、同一データが二重に保存されるのを抑制できる。
【００８２】
ウインドウサイズＷＬ、下限値ＬＳ及び所定サイズＰＬ等の各数値は、例えば、ファイルデータの性質（構造化データか非構造化データか等）、ストレージの空き容量などの観点に基づいて、適宜設定することができる。本実施例のファイルデータ管理システム１０は、種々の製品に組み込んで使用することができる。
【実施例２】
【００８３】
図１０を参照して、第２実施例を説明する。本実施例を含む以下の各実施例は、第１実施例の変形例である。従って、以下、第１実施例との相違を中心に説明する。
【００８４】
図１０は、ファイル分割処理（Ｓ３００Ａ）を示すフローチャートである。本フローチャートは、図８に示すＳ３０１〜Ｓ３０８を全て備える。さらに、本フローチャートは、ウインドウ内のデータから第１ハッシュ値を算出する処理（Ｓ３０３）の後に、新規な処理（Ｓ３１０，Ｓ３１１）が追加されている。
【００８５】
プログラムＰ２０は、第１ハッシュ値を算出すると（Ｓ３０３）、その第１ハッシュ値が予め設定されている限界値に一致するか否かを判定する（Ｓ３１０）。
【００８６】
限界値とは、特徴値の理論的限界を示す値である。特徴値がハッシュ値の最小値である場合、その限界値は”００００”である。特徴値がハッシュ値の最大値の場合、その限界値は、ハッシュ関数の仕様で定まる値（例えば”ＦＦＦＦ”）である。
【００８７】
従って、特徴値に最小値が設定されている場合において、ウインドウ内のデータから算出された第１ハッシュ値が”０”であるときは、その時点で、特徴値が検出されたと判断しても差し支えない。第１ハッシュ値が特徴値の限界値に一致しており、その第１ハッシュ値は必ず特徴値に該当するためである。
【００８８】
その後に、特徴値に該当する他の第１ハッシュ値が出現する可能性はある。従って、複数の特徴値が検出される場合、先に出現した特徴値を選択する構成とする。プログラムＰ２０は、特徴値の限界値に一致する第１ハッシュ値が検出された時点で、第１ハッシュ値の算出を打ち切ることができる（Ｓ３１０：ＹＥＳ）。プログラムＰ２０は、限界値に一致する第１ハッシュ値に対応する位置を分割位置に設定し（Ｓ３１１）、ファイルデータを分割位置で分割する（Ｓ３０７）。
【００８９】
算出された第１ハッシュ値が限界値に一致しない場合（Ｓ３１０：ＮＯ）、プログラムＰ２０はウインドウを１バイトだけ右にシフトさせ（Ｓ３０４）、他のデータについての第１ハッシュ値を算出する（Ｓ３０３）。
【００９０】
このように構成される本実施例も第１実施例と同様の効果を奏する。さらに、本実施例では、算出された第１ハッシュ値が特徴値の理論的限界である限界値に一致する場合、その第１ハッシュ値を特徴値として選択する。所定範囲ＰＬの全体について第１ハッシュ値の算出が終了していない場合でも、第１ハッシュ値の算出は中止される。
【００９１】
従って、本実施例では、第１実施例よりも高速に、ファイルデータを適切なサイズに分割することができる。このため、ファイルデータの重複を検出して排除する処理をより高速に行うことができ、使い勝手が向上する。
【実施例３】
【００９２】
図１１，図１２を参照して第３実施例を説明する。本実施例では、受信した対象ファイルデータを逐次処理する。
【００９３】
図１１は、本実施例のファイルデータ管理システム１０Ａの全体構成を示す。図２に示す構成との第１の相違は、クライアントコンピュータ５０から受領するファイルデータを保存するための第２ストレージ装置４０が存在しないことである。第２の相違は、マイグレーションプログラムＰ２１が存在しないことである。
【００９４】
図１２は、全体動作を示すフローチャートである。管理システム１０Ａは、クライアントコンピュータ５０から対象ファイルデータを受信すると（Ｓ１００Ａ）、ただちにファイル分割処理（Ｓ３００）及び重複排除処理（Ｓ４００）を実行する。
【００９５】
つまり、本実施例では、クライアントコンピュータ５０から受領したファイルデータを、受領とほぼ同時に処理する。本実施例では、ＮＡＳサーバ２０内のバッファメモリまたはキャッシュメモリにファイルデータが一時的に記憶されることはある。しかし、それは、ファイル分割処理及び重複排除処理の開始契機を待つための記憶ではない。
【００９６】
このように構成される本実施例も第１実施例と同様の効果を奏する。さらに、本実施例では、ほぼリアルタイムにファイルデータを分割して管理することができる。
、本発明は、上述した実施形態に限定されない。当業者であれば、本発明の範囲内で、種々の追加や変更等を行うことができる。例えば、第２実施例と第３実施例とを組合せることもできる。
【符号の説明】
【００９７】
１０，１０Ａ：データ管理システム、Ｐ２０：重複排除プログラム
【図１】
2014514618.tif 000003
【図２】
2014514618.tif 000004
【図３】
2014514618.tif 000005
【図４】
2014514618.tif 000006
【図５】
2014514618.tif 000007
【図６】
2014514618.tif 000008
【図７】
2014514618.tif 000009
【図８】
2014514618.tif 000010
【図９】
2014514618.tif 000011
【図１０】
2014514618.tif 000012
【図１１】
2014514618.tif 000013
【図１２】
2014514618.tif 000014
【国際調査報告】
2014514618.tif 000015
2014514618.tif 000016