(57)【特許請求の範囲】
【請求項１】
重複排除方法であって、
記憶デバイスによって、第1のデータストリームを受信するステップと、
前記記憶デバイスによって、前記第1のデータストリームを分割して、n個のデータブロックを取得するステップであって、前記n個のデータブロックの論理アドレスは連続し、前記n個のデータブロックは第1のデータブロックを含み、前記第1のデータブロックの論理アドレスは、前記n個のデータブロックに対応する前記論理アドレス内の先頭アドレスであり、nは2以上の整数である、ステップと、
前記記憶デバイスによって、前記n個のデータブロックを計算して、前記n個のデータブロックのフィンガープリントを取得するステップと、
前記n個のデータブロックの前記フィンガープリントが前記記憶デバイスにおけるフィンガープリント内で見つからない場合、前記記憶デバイスによって、前記n個のデータブロックの前記論理アドレスのシーケンスで、第1の記憶領域に、前記n個のデータブロックを連続して記憶するステップであって、前記第1の記憶領域に記憶された前記第1のデータブロックの物理アドレスは第1の物理アドレスである、ステップと、
前記記憶デバイスによって、前記n個のデータブロックの前記論理アドレスの前記シーケンスで、第2の記憶領域に、前記n個のデータブロックの前記フィンガープリントのメタデータを連続して記憶するステップであって、前記n個のデータブロックの前記フィンガープリントにおける各フィンガープリントのメタデータは、前記n個のデータブロックの前記フィンガープリントにおけるそれぞれのフィンガープリントと、前記第1の記憶領域に記憶されている、前記フィンガープリントに対応するそれぞれのデータブロックの物理アドレスとを含む、ステップと、
前記記憶デバイスによって、前記n個のデータブロックの前記フィンガープリントにおける各フィンガープリントの前記メタデータのアドレス識別子と、前記n個のデータブロックの前記フィンガープリントにおける前記それぞれのフィンガープリントの前記メタデータとの間のマッピングを確立するステップと、
前記記憶デバイスによって、前記第1のデータブロックの前記論理アドレスと集約アドレスとの間のマッピングを確立するステップであって、前記集約アドレスは、集約データブロックの物理アドレスと、集約フィンガープリントのメタデータのアドレス識別子とを含み、前記集約データブロックの前記物理アドレスは、前記第1の物理アドレスと、前記第1の記憶領域に記憶されている前記n個のデータブロックの物理アドレス長とを含み、前記集約フィンガープリントの前記メタデータの前記アドレス識別子は、前記第1のデータブロックのフィンガープリントのメタデータのアドレス識別子と、前記n個のデータブロックの前記フィンガープリントのメタデータのアドレス識別子の数とを含む、ステップとを含む方法。
【請求項２】
前記記憶デバイスによって、前記第1のデータブロックの前記論理アドレスと集約アドレスとの間のマッピングを確立する前記ステップは、具体的には、
前記記憶デバイスによって、前記第1のデータブロックの前記論理アドレスと、前記集約データブロックの前記物理アドレスおよび前記集約フィンガープリントの前記メタデータの前記アドレス識別子の両方との間のマッピングを確立するステップを含む、請求項1に記載の方法。
【請求項３】
前記記憶デバイスによって、前記第1のデータブロックの前記論理アドレスと集約アドレスとの間のマッピングを確立する前記ステップは、具体的には、
前記記憶デバイスによって、前記第1のデータブロックの前記論理アドレスと、前記集約フィンガープリントの前記メタデータの前記アドレス識別子との間のマッピングおよび前記集約フィンガープリントの前記メタデータの前記アドレス識別子と、前記集約データブロックの前記物理アドレスとの間のマッピングを確立するステップを含む、請求項1に記載の方法。
【請求項４】
前記記憶デバイスによって、前記第1のデータブロックの前記論理アドレスと集約アドレスとの間のマッピングを確立する前記ステップは、具体的には、
前記記憶デバイスによって、前記第1のデータブロックの前記論理アドレスと、前記集約データブロックの前記物理アドレスとの間のマッピングおよび前記集約データブロックの前記物理アドレスと、前記集約フィンガープリントの前記メタデータの前記アドレス識別子との間のマッピングを確立するステップを含む、請求項1に記載の方法。
【請求項５】
前記方法は、
前記記憶デバイスによって、前記第1のデータブロックの前記論理アドレスと集約アドレスとの間のマッピングを確立する前記ステップの前に、前記記憶デバイスによって、前記第1の記憶領域に記憶されている前記n個のデータブロックの前記物理アドレス長が前記記憶デバイスの圧縮ウィンドウを超過するかどうかを判定するステップをさらに含み、前記圧縮ウィンドウは、一度に圧縮されることができるデータブロックの長さを指す、請求項1乃至4のいずれか1項に記載の方法。
【請求項６】
前記方法は、前記記憶デバイスによって、前記圧縮ウィンドウに従って、前記第1の記憶領域に記憶されている前記n個のデータブロックを圧縮するステップをさらに含む、請求項5に記載の方法。
【請求項７】
前記記憶デバイスによって、第2のデータストリームを受信するステップと、
前記記憶デバイスによって、前記第2のデータストリームを分割して、n個のデータブロックを取得するステップであって、前記第2のデータストリームにおける前記n個のデータブロックの論理アドレスは連続し、前記第2のデータストリームにおける前記n個のデータブロックは第2のデータブロックを含み、前記第2のデータブロックの論理アドレスは、前記第2のデータストリームにおける前記n個のデータブロックに対応する前記論理アドレス内の先頭アドレスである、ステップと、
前記記憶デバイスによって、前記第2のデータストリームにおける前記n個のデータブロックを計算して、前記第2のデータストリームにおける前記n個のデータブロックのフィンガープリントを取得するステップと、
前記記憶デバイスが、前記第1のデータストリームにおける前記n個のデータブロックの前記フィンガープリントの前記メタデータを問い合わせることによって、前記第2のデータストリームにおける前記n個のデータブロックの各々の前記フィンガープリントが前記第1のデータストリーム内の前記n個のデータブロックの各々のフィンガープリントと同じであると決定した場合、前記記憶デバイスによって、前記第2のデータブロックの前記論理アドレスと前記集約アドレスとの間のマッピングを確立するステップであって、前記第2のデータストリームにおける前記n個のデータブロックのデータブロックシーケンス位置は、前記第1のデータストリーム内の前記n個のデータブロックのデータブロックシーケンス位置と同じであり、前記データブロックシーケンス位置は、前記第1のデータストリームまたは前記第2のデータストリームのいずれかにおける前記n個のデータブロック内の各データブロックの相対位置を指す、ステップとをさらに含む、請求項1乃至4のいずれか1項に記載の方法。
【請求項８】
前記方法は、
前記記憶デバイスによって、前記第1のデータストリームにおける前記n個のデータブロックの前記フィンガープリント内の第1のフィンガープリントの索引を確立するステップであって、前記第1のフィンガープリントの前記索引は、前記第1のフィンガープリントと、前記第1のフィンガープリントのメタデータのアドレス識別子との間のマッピングを含む、ステップをさらに含む、請求項1に記載の方法。
【請求項９】
記憶デバイスであって、
第1のデータストリームを受信するように構成される受信ユニットと、
前記第1のデータストリームを分割して、n個のデータブロックを取得するように構成される分割ユニットであって、前記n個のデータブロックの論理アドレスは連続し、前記n個のデータブロックは第1のデータブロックを含み、前記第1のデータブロックの論理アドレスは、前記n個のデータブロックに対応する前記論理アドレス内の先頭アドレスであり、nは2以上の整数である、分割ユニットと、
前記n個のデータブロックを計算して、前記n個のデータブロックのフィンガープリントを取得するように構成される計算ユニットと、
前記n個のデータブロックの前記フィンガープリントが前記記憶デバイスにおけるフィンガープリント内で見つからない場合、前記n個のデータブロックの前記論理アドレスのシーケンスで、第1の記憶領域に、前記n個のデータブロックを連続して記憶し、前記n個のデータブロックの前記論理アドレスの前記シーケンスで、第2の記憶領域に、前記n個のデータブロックの前記フィンガープリントのメタデータを連続して記憶するように構成される記憶ユニットであって、前記第1の記憶領域に記憶された前記第1のデータブロックの物理アドレスは第1の物理アドレスであり、前記n個のデータブロックの前記フィンガープリントにおける各フィンガープリントのメタデータは、前記n個のデータブロックの前記フィンガープリントにおけるそれぞれのフィンガープリントと、前記第1の記憶領域に記憶されている、前記フィンガープリントに対応するそれぞれのデータブロックの物理アドレスとを含む、記憶ユニットと、
前記n個のデータブロックの前記フィンガープリントにおける各フィンガープリントの前記メタデータのアドレス識別子と、前記n個のデータブロックの前記フィンガープリントにおける前記それぞれのフィンガープリントの前記メタデータとの間のマッピングを確立し、前記第1のデータブロックの前記論理アドレスと集約アドレスとの間のマッピングを確立するように構成される確立ユニットであって、前記集約アドレスは、集約データブロックの物理アドレスと、集約フィンガープリントのメタデータのアドレス識別子とを含み、前記集約データブロックの前記物理アドレスは、前記第1の物理アドレスと、前記第1の記憶領域に記憶されている前記n個のデータブロックの物理アドレス長とを含み、前記集約フィンガープリントの前記メタデータの前記アドレス識別子は、前記第1のデータブロックのフィンガープリントのメタデータのアドレス識別子と、前記n個のデータブロックの前記フィンガープリントの前記メタデータのアドレス識別子の数とを含む、確立ユニットとを含む記憶デバイス。
【請求項１０】
前記確立ユニットは、具体的には、前記第1のデータブロックの前記論理アドレスと、前記集約データブロックの前記物理アドレスおよび前記集約フィンガープリントの前記メタデータの前記アドレス識別子の両方との間のマッピングを確立するように構成される、請求項9に記載の記憶デバイス。
【請求項１１】
前記確立ユニットは、具体的には、前記第1のデータブロックの前記論理アドレスと、前記集約フィンガープリントの前記メタデータの前記アドレス識別子との間のマッピングおよび前記集約フィンガープリントの前記メタデータの前記アドレス識別子と、前記集約データブロックの前記物理アドレスとの間のマッピングを確立するように構成される、請求項9に記載の記憶デバイス。
【請求項１２】
前記確立ユニットは、具体的には、前記第1のデータブロックの前記論理アドレスと、前記集約データブロックの前記物理アドレスとの間のマッピングおよび前記集約データブロックの前記物理アドレスと、前記集約フィンガープリントの前記メタデータの前記アドレス識別子との間のマッピングを確立するように構成される、請求項9に記載の記憶デバイス。
【請求項１３】
前記記憶デバイスは決定ユニットをさらに含み、前記決定ユニットは、前記第1のデータブロックの前記論理アドレスと前記集約アドレスとの間の前記マッピングが確立される前に、前記第1の記憶領域に記憶されている前記n個のデータブロックの前記物理アドレス長が前記記憶デバイスの圧縮ウィンドウを超過するかどうかを判定するように構成され、前記圧縮ウィンドウは、一度に圧縮されることができるデータブロックの長さを指す、請求項9乃至12のいずれか1項に記載の記憶デバイス。
【請求項１４】
前記記憶デバイスは圧縮ユニットをさらに含み、前記圧縮ユニットは、前記圧縮ウィンドウに従って、前記第1の記憶領域に記憶されている前記n個のデータブロックを圧縮するように構成される、請求項13に記載の記憶デバイス。
【請求項１５】
前記受信ユニットは、第2のデータストリームを受信するようにさらに構成され、
前記分割ユニットは、前記第2のデータストリームを分割して、n個のデータブロックを取得するようにさらに構成され、前記第2のデータストリームにおける前記n個のデータブロックの論理アドレスは連続し、前記第2のデータストリームにおける前記n個のデータブロックは第2のデータブロックを含み、前記第2のデータブロックの論理アドレスは、前記第2のデータストリームにおける前記n個のデータブロックに対応する前記論理アドレス内の先頭アドレスであり、
前記計算ユニットは、前記第2のデータストリームにおける前記n個のデータブロックを計算して、前記第2のデータストリームにおける前記n個のデータブロックのフィンガープリントを取得するようにさらに構成され、
前記確立ユニットは、前記記憶デバイスが、前記第1のデータストリームにおける前記n個のデータブロックの前記フィンガープリントの前記メタデータを問い合わせることによって、前記第2のデータストリームにおける前記n個のデータブロックの各々の前記フィンガープリントが前記第1のデータストリーム内の前記n個のデータブロックの各々のフィンガープリントと同じであると決定した場合、前記第2のデータブロックの前記論理アドレスと前記集約アドレスとの間のマッピングを確立するようにさらに構成され、前記第2のデータストリームにおける前記n個のデータブロックのデータブロックシーケンス位置は、前記第1のデータストリーム内の前記n個のデータブロックのデータブロックシーケンス位置と同じであり、前記データブロックシーケンス位置は、前記第1のデータストリームまたは前記第2のデータストリームのいずれかにおける前記n個のデータブロック内の各データブロックの相対位置を指す、請求項9乃至12のいずれか1項に記載の記憶デバイス。
【請求項１６】
前記確立ユニットは、前記第1のデータストリームにおける前記n個のデータブロックの前記フィンガープリント内の第1のフィンガープリントの索引を確立するようにさらに構成され、前記第1のフィンガープリントの前記索引は、前記第1のフィンガープリントと、前記第1のフィンガープリントのメタデータのアドレス識別子との間のマッピングを含む、請求項9に記載の記憶デバイス。
【請求項１７】
インタフェースおよびプロセッサを含む記憶デバイスであって、前記インタフェースは前記プロセッサと通信し、
前記インタフェースは、第1のデータストリームを受信するように構成され、
前記プロセッサは、
前記第1のデータストリームを分割して、n個のデータブロックを取得し
前記n個のデータブロックを計算して、前記n個のデータブロックのフィンガープリントを取得し、
前記n個のデータブロックの前記フィンガープリントが前記記憶デバイスにおけるフィンガープリント内で見つからない場合、前記n個のデータブロックの論理アドレスのシーケンスで、第1の記憶領域に、前記n個のデータブロックを連続して記憶し、
前記n個のデータブロックの前記論理アドレスの前記シーケンスで、第2の記憶領域に、前記n個のデータブロックの前記フィンガープリントのメタデータを連続して記憶し、
前記n個のデータブロックの前記フィンガープリントにおける各フィンガープリントの前記メタデータのアドレス識別子と、前記n個のデータブロックの前記フィンガープリントにおけるそれぞれのフィンガープリントの前記メタデータとの間のマッピングを確立し、
第1のデータブロックの前記論理アドレスと集約アドレスとの間のマッピングを確立するように構成され、
前記n個のデータブロックの前記論理アドレスは連続し、前記n個のデータブロックは前記第1のデータブロックを含み、前記第1のデータブロックの論理アドレスは、前記n個のデータブロックに対応する前記論理アドレス内の先頭アドレスであり、nは2以上の整数であり、
前記第1の記憶領域に記憶された前記第1のデータブロックの物理アドレスは第1の物理アドレスであり、
前記n個のデータブロックの前記フィンガープリントにおける各フィンガープリントのメタデータは、前記n個のデータブロックの前記フィンガープリントにおける前記それぞれのフィンガープリントと、前記第1の記憶領域に記憶されている、前記フィンガープリントに対応するそれぞれのデータブロックの物理アドレスとを含み、
前記集約アドレスは、集約データブロックの物理アドレスと、集約フィンガープリントのメタデータのアドレス識別子とを含み、前記集約データブロックの前記物理アドレスは、前記第1の物理アドレスと、前記第1の記憶領域に記憶されている前記n個のデータブロックの物理アドレス長とを含み、前記集約フィンガープリントの前記メタデータの前記アドレス識別子は、前記第1のデータブロックのフィンガープリントのメタデータのアドレス識別子と、前記n個のデータブロックの前記フィンガープリントのメタデータのアドレス識別子の数とを含む、記憶デバイス。
【請求項１８】
前記プロセッサは、具体的には、前記第1のデータブロックの前記論理アドレスと、前記集約データブロックの前記物理アドレスおよび前記集約フィンガープリントの前記メタデータの前記アドレス識別子の両方との間のマッピングを確立するように構成される、請求項17に記載の記憶デバイス。
【請求項１９】
前記プロセッサは、具体的には、前記第1のデータブロックの前記論理アドレスと、前記集約フィンガープリントの前記メタデータの前記アドレス識別子との間のマッピングおよび前記集約フィンガープリントの前記メタデータの前記アドレス識別子と、前記集約データブロックの前記物理アドレスとの間のマッピングを確立するように構成される、請求項17に記載の記憶デバイス。
【請求項２０】
前記プロセッサは、具体的には、前記第1のデータブロックの前記論理アドレスと、前記集約データブロックの前記物理アドレスとの間のマッピングおよび前記集約データブロックの前記物理アドレスと、前記集約フィンガープリントの前記メタデータの前記アドレス識別子との間のマッピングを確立するように構成される、請求項17に記載の記憶デバイス。
【請求項２１】
前記プロセッサは、前記第1のデータブロックの前記論理アドレスと前記集約アドレスとの間の前記マッピングが確立される前に、前記第1の記憶領域に記憶されている前記n個のデータブロックの前記物理アドレス長が前記記憶デバイスの圧縮ウィンドウを超過するかどうかを判定するようにさらに構成され、前記圧縮ウィンドウは、一度に圧縮されることができるデータブロックの長さを指す、請求項17乃至20のいずれか1項に記載の記憶デバイス。
【請求項２２】
前記プロセッサは、前記圧縮ウィンドウに従って、前記第1の記憶領域に記憶されている前記n個のデータブロックを圧縮するようにさらに構成される、請求項21に記載の記憶デバイス。
【請求項２３】
前記インタフェースは、第2のデータストリームを受信するようにさらに構成され、
前記プロセッサは、
前記第2のデータストリームを分割して、n個のデータブロックを取得し、
前記第2のデータストリームにおける前記n個のデータブロックを計算して、前記第2のデータストリームにおける前記n個のデータブロックのフィンガープリントを取得し、
前記記憶デバイスが、前記第1のデータストリームにおける前記n個のデータブロックの前記フィンガープリントの前記メタデータを問い合わせることによって、前記第2のデータストリームにおける前記n個のデータブロックの各々の前記フィンガープリントが前記第1のデータストリーム内の前記n個のデータブロックの各々のフィンガープリントと同じであると決定した場合、第2のデータブロックの前記論理アドレスと前記集約アドレスとの間のマッピングを確立するようにさらに構成され、
前記第2のデータストリームにおける前記n個のデータブロックの論理アドレスは連続し、前記第2のデータストリームにおける前記n個のデータブロックは前記第2のデータブロックを含み、前記第2のデータブロックの論理アドレスは、前記第2のデータストリームにおける前記n個のデータブロックに対応する前記論理アドレス内の先頭アドレスであり、
前記第2のデータストリームにおける前記n個のデータブロックのデータブロックシーケンス位置は、前記第1のデータストリーム内の前記n個のデータブロックのデータブロックシーケンス位置と同じであり、前記データブロックシーケンス位置は、前記第1のデータストリームまたは前記第2のデータストリームのいずれかにおける前記n個のデータブロック内の各データブロックの相対位置を指す、請求項17乃至20のいずれか1項に記載の記憶デバイス。
【請求項２４】
前記プロセッサは、前記第1のデータストリームにおける前記n個のデータブロックの前記フィンガープリント内の第1のフィンガープリントの索引を確立するようにさらに構成され、前記第1のフィンガープリントの前記索引は、前記第1のフィンガープリントと、前記第1のフィンガープリントのメタデータのアドレス識別子との間のマッピングを含む、請求項17に記載の記憶デバイス。
【請求項２５】
プログラムコードを記憶するコンピュータ可読記憶媒体であって、前記プログラムコードに含まれる命令は、記憶デバイス内のCPUに、請求項1乃至8のいずれか1項に記載の前記方法を実行させるために使用される、コンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報技術の分野に関し、詳細には、重複排除方法および記憶デバイスに関する。
【背景技術】
【０００２】
情報技術の発展に伴い、記憶される必要があるデータ量は急速に増加する。無限に増加するデータ量と比較的限られた記憶空間との間の矛盾を緩和するために、重複排除技術が導入される。
【０００３】
具体的な実施において、重複排除技術は主に以下のステップを含む：
【０００４】
ステップ1: 記憶デバイスは、具体的には、固定長チャンキングアルゴリズムまたは可変長チャンキングアルゴリズムを使用して、1つのデータストリームをデータブロックに分割する。
【０００５】
ステップ2: 記憶デバイスは、データブロックの各々のフィンガープリントを計算し、ここで、フィンガープリントは、特性値とも呼ばれる。
【０００６】
ステップ3: 記憶デバイスは、データブロックの各々のフィンガープリントを記憶デバイスに記憶されている一意のデータブロック（非重複データブロックとも呼ばれる）のフィンガープリントと比較し、データブロックの1つのデータブロックのフィンガープリントが記憶デバイスに記憶されている一意のデータブロックのフィンガープリントと同じである場合、ステップ4を実行し、データブロックのそのデータブロックのフィンガープリントが記憶デバイスに記憶されている一意のデータブロックのフィンガープリントと異なる場合、ステップ5を実行する。
【０００７】
ステップ4: 記憶デバイスは、データブロックをもはや記憶せず、記憶デバイスに記憶されているとともにそのデータブロックのフィンガープリントと同じフィンガープリントを有する一意のデータブロックの参照カウントを1増やす。
【０００８】
ステップ5: 記憶デバイスは、データブロックの論理アドレス（logical address, LA）の順序で、記憶デバイスのデータコンテナ（container）の物理アドレス（physical address, PA）に、データブロックを一意のデータブロックとして順次記憶し、データブロックの論理アドレスの順序で、記憶デバイスのフィンガープリントコンテナの物理アドレスに、データブロックのフィンガープリントのメタデータを順次記憶し、フィンガープリントのメタデータのアドレス識別子を生成し、フィンガープリントのメタデータのアドレス識別子と、フィンガープリントのメタデータとの間のマッピングを確立し、ステップ6を実行する。データブロックのフィンガープリントのメタデータは、データブロックのフィンガープリントと、データブロックが記憶されている物理アドレスとを含む。フィンガープリントのメタデータのアドレス識別子は、フィンガープリントのメタデータが記憶されている物理アドレスであってよい。別の実施方式では、フィンガープリントのメタデータのアドレス識別子は、フィンガープリントのメタデータを一意に識別する論理識別子であってよい。具体的には、記憶デバイスは、グローバル一意識別子を、一意のデータブロックに対応するフィンガープリントのメタデータに割り当ててよく、その論理アドレスが連続している複数の一意のデータブロックのフィンガープリントのメタデータのアドレス識別子は線形的に増加する。フィンガープリントのメタデータのアドレス識別子と、フィンガープリントのメタデータとの間のマッピングは確立され、その結果、フィンガープリントのメタデータは、その後の重複排除操作におけるフィンガープリントの問合せのためにロードされることができる。
【０００９】
ステップ6: 記憶デバイスは、データブロックの論理アドレスとフィンガープリントとの間のマッピングを確立し、フィンガープリントと、一意のデータブロックが記憶されている物理アドレスとの間のマッピングを確立する。記憶デバイスが重複排除機能を有するために、記憶デバイスに記憶されている一意のデータブロックは、論理アドレスを使用することによってアクセスされることができることは保証される必要があり、記憶されている一意のデータブロックが削除された後に、一意のデータブロックに対応するフィンガープリントは削除されることもまた保証される必要がある。従って、重複排除機能を有する記憶デバイスにおいては、データブロックの論理アドレスの各々、データブロックのフィンガープリント、および一意のデータブロックのものであるとともにフィンガープリントに対応している物理アドレスは、マッピングにおいて不可欠である。
【００１０】
しかしながら、記憶デバイスによって記憶されたデータに対して行われる断続的重複排除は、記憶デバイスの物理空間を節約するが、ステップ6において記憶デバイスによって確立される大量のマッピング関係は、記憶デバイスのメモリ空間を多く占有する。
【発明の概要】
【課題を解決するための手段】
【００１１】
第1の態様によると、本発明は重複排除方法を提供し、方法は、
記憶デバイスによって、第1のデータストリームを受信するステップと、
記憶デバイスによって、第1のデータストリームを分割して、n個のデータブロックを取得するステップであって、ここで、n個のデータブロックの論理アドレスは連続し、n個のデータブロックは第1のデータブロックを含み、第1のデータブロックの論理アドレスは、n個のデータブロックに対応する論理アドレス内の先頭アドレスであり、nは2以上の整数である、ステップと、
記憶デバイスによって、n個のデータブロックを計算して、n個のデータブロックのフィンガープリントを取得するステップと、
n個のデータブロックのフィンガープリントが記憶デバイスにおけるフィンガープリント内で見つからない場合、記憶デバイスによって、n個のデータブロックの論理アドレスのシーケンスで、第1の記憶領域に、n個のデータブロックを連続して記憶するステップであって、ここで、第1の記憶領域に記憶された第1のデータブロックの物理アドレスは第1の物理アドレスである、ステップと、
記憶デバイスによって、n個のデータブロックの論理アドレスのシーケンスで、第2の記憶領域に、n個のデータブロックのフィンガープリントのメタデータを連続して記憶するステップであって、ここで、n個のデータブロックのフィンガープリントにおける各フィンガープリントのメタデータは、n個のデータブロックのフィンガープリントにおけるそれぞれのフィンガープリントと、それぞれのフィンガープリントのものであるとともに、第2の記憶領域に記憶されている物理アドレスとを含む、ステップと、
記憶デバイスによって、n個のデータブロックのフィンガープリントにおける各フィンガープリントのメタデータのアドレス識別子と、n個のデータブロックのフィンガープリントにおけるそれぞれのフィンガープリントのメタデータとの間のマッピングを確立するステップと、
記憶デバイスによって、第1のデータブロックの論理アドレスと集約アドレスとの間のマッピングを確立するステップであって、ここで、集約アドレスは、集約データブロックの物理アドレスと、集約フィンガープリントのメタデータのアドレス識別子とを含み、集約データブロックの物理アドレスは、第1の物理アドレスと、第1の記憶領域に記憶されているn個のデータブロックの物理アドレス長とを含み、集約フィンガープリントのメタデータのアドレス識別子は、第1のデータブロックのフィンガープリントのメタデータのアドレス識別子と、n個のデータブロックのフィンガープリントのメタデータのアドレス識別子の数とを含む、ステップとを含む。本発明の実施形態では、記憶デバイスにおけるマッピングエントリの数は低減され、その結果、記憶デバイスのメモリ空間は節約され、加えて、フィンガープリントのメタデータが削除される必要があるかどうかは、マッピング関係に従って決定されることができる。任意で、第1の記憶領域および第2の記憶領域はコンテナである。さらに、第1の記憶領域および第2の記憶領域は同じ記憶領域であり得る。
【００１２】
第1の態様を参照すると、第1の可能な実施方式では、記憶デバイスによって、第1のデータブロックの論理アドレスと集約アドレスとの間のマッピングを確立するステップは、具体的には、
記憶デバイスによって、第1のデータブロックの論理アドレスと、集約データブロックの物理アドレスおよび集約フィンガープリントのメタデータのアドレス識別子の両方との間のマッピングを確立するステップを含む。
【００１３】
第1の態様を参照すると、第2の可能な実施方式では、記憶デバイスによって、第1のデータブロックの論理アドレスと集約アドレスとの間のマッピングを確立するステップは、具体的には、
記憶デバイスによって、第1のデータブロックの論理アドレスと、集約フィンガープリントのメタデータのアドレス識別子との間のマッピングおよび集約フィンガープリントのメタデータのアドレス識別子と、集約データブロックの物理アドレスとの間のマッピングを確立するステップを含む。
【００１４】
第1の態様を参照すると、第3の可能な実施方式では、記憶デバイスによって、第1のデータブロックの論理アドレスと集約アドレスとの間のマッピングを確立するステップは、具体的には、
記憶デバイスによって、第1のデータブロックの論理アドレスと、集約データブロックの物理アドレスとの間のマッピングおよび集約データブロックの物理アドレスと、集約フィンガープリントのメタデータのアドレス識別子との間のマッピングを確立するステップを含む。
【００１５】
第1の態様、または第1の態様の第1乃至第3の可能な実施方式のいずれか1つを参照すると、第4の可能な実施方式では、
方法は、
記憶デバイスによって、第1のデータブロックの論理アドレスと集約アドレスとの間のマッピングを確立するステップの前に、記憶デバイスによって、第1の記憶領域に記憶されているn個のデータブロックの物理アドレス長が記憶デバイスの圧縮ウィンドウを超過しないと決定するステップをさらに含む。
【００１６】
第1の態様の第4の可能な実施方式を参照すると、第5の可能な実施方式では、方法は、記憶デバイスによって、圧縮ウィンドウに従って、第1の記憶領域に記憶されているn個のデータブロックを圧縮するステップをさらに含む。
【００１７】
第1の態様、または第1の態様の第1乃至第3の可能な実施方式のいずれか1つを参照すると、第6の可能な実施方式では、方法は、
記憶デバイスによって、第2のデータストリームを受信するステップと、
記憶デバイスによって、第2のデータストリームを分割して、n個のデータブロックを取得するステップであって、ここで、第2のデータストリームにおけるn個のデータブロックの論理アドレスは連続し、第2のデータストリームにおけるn個のデータブロックは第2のデータブロックを含み、第2のデータブロックの論理アドレスは、第2のデータストリームにおけるn個のデータブロックに対応する論理アドレス内の先頭アドレスである、ステップと、
記憶デバイスによって、第2のデータストリームにおけるn個のデータブロックを計算して、第2のデータストリームにおけるn個のデータブロックのフィンガープリントを取得するステップと、
記憶デバイスが、第1のデータストリームにおけるn個のデータブロックのフィンガープリントのメタデータを問い合わせることによって、第2のデータストリームにおけるn個のデータブロックのフィンガープリントがそれぞれ第1のデータストリーム内のn個のデータブロックのフィンガープリントと同じであると決定した場合、記憶デバイスによって、第2のデータブロックの論理アドレスと集約アドレスとの間のマッピングを確立するステップであって、ここで、第2のデータストリームにおけるn個のデータブロックのデータブロックシーケンス位置は、第1のデータストリーム内のn個のデータブロックのデータブロックシーケンス位置と同じであり、データブロックシーケンス位置は、第1のデータストリームまたは第2のデータストリームのいずれかにおけるn個のデータブロック内の各データブロックの相対位置を指す、ステップとをさらに含む。
【００１８】
第1の態様を参照すると、第7の可能な実施方式では、方法は、
記憶デバイスによって、第1のデータストリームにおけるn個のデータブロックのフィンガープリント内の第1のフィンガープリントの索引を確立するステップであって、ここで、第1のフィンガープリントの索引は、第1のフィンガープリントと、第1のフィンガープリントのメタデータのアドレス識別子との間のマッピングを含む、ステップをさらに含む。任意で、第1のフィンガープリントのメタデータにおける第1のフィンガープリントを特定の整数で割ることによって得られる余りは特定の値を満たす。任意で、第1のフィンガープリントのメタデータにおける第1のフィンガープリントは、第2の記憶領域に記憶されているフィンガープリントのメタデータからランダムに、または一定間隔で抽出される。
【００１９】
第1の態様の様々な可能な実施方式では、第1のデータブロックの論理アドレスは、第1のデータストリームにおけるn個のデータブロックに対応する論理アドレス内の末尾アドレスであり、第2のデータブロックの論理アドレスは、第2のデータストリームにおけるn個のデータブロックに対応する論理アドレス内の末尾アドレスである。任意で、第1のデータブロックの論理アドレスと集約アドレスとの間のマッピングおよび第2のデータブロックの論理アドレスと集約アドレスとの間のマッピングの両方が、マッピングアドレス方向識別子を含む。
【００２０】
第2の態様によると、本発明の実施形態は重複排除方法を提供し、方法は、
記憶デバイスによって、第1のデータストリームを受信するステップと、
記憶デバイスによって、第1のデータストリームを分割して、n個のデータブロックを取得するステップであって、ここで、n個のデータブロックの論理アドレスは連続し、n個のデータブロックは第1のデータブロックを含み、第1のデータブロックの論理アドレスは、n個のデータブロックに対応する論理アドレス内の先頭アドレスであり、nは2以上の整数である、ステップと、
記憶デバイスによって、n個のデータブロックを計算して、n個のデータブロックのフィンガープリントを取得するステップと、
n個のデータブロックのフィンガープリントが記憶デバイスにおけるフィンガープリント内で見つからない場合、記憶デバイスによって、n個のデータブロックの論理アドレスのシーケンスで、第1の記憶領域に、n個のデータブロックを連続して記憶するステップであって、ここで、第1の記憶領域に記憶された第1のデータブロックの物理アドレスは第1の物理アドレスである、ステップと、
記憶デバイスによって、n個のデータブロックの論理アドレスのシーケンスで、第2の記憶領域に、n個のデータブロックのフィンガープリントのメタデータを連続して記憶するステップであって、ここで、n個のデータブロックのフィンガープリントにおける各フィンガープリントのメタデータは、n個のデータブロックのフィンガープリントにおけるそれぞれのフィンガープリントと、それぞれのフィンガープリントのものであるとともに、第2の記憶領域に記憶されている物理アドレスとを含む、ステップと、
記憶デバイスによって、n個のデータブロックのフィンガープリントにおける各フィンガープリントのメタデータのアドレス識別子と、n個のデータブロックのフィンガープリントにおけるそれぞれのフィンガープリントのメタデータとの間のマッピングを確立するステップと、
記憶デバイスによって、第2のデータストリームを受信するステップと、
記憶デバイスによって、第2のデータストリームを分割して、n個のデータブロックを取得するステップであって、ここで、第2のデータストリームにおけるn個のデータブロックの論理アドレスは連続し、第2のデータストリームにおけるn個のデータブロックは第2のデータブロックを含み、第2のデータブロックの論理アドレスは、第2のデータストリームにおけるn個のデータブロックに対応する論理アドレス内の先頭アドレスである、ステップと、
記憶デバイスによって、第2のデータストリームにおけるn個のデータブロックを計算して、第2のデータストリームにおけるn個のデータブロックのフィンガープリントを取得するステップと、
記憶デバイスが、第1のデータストリームにおけるn個のデータブロックのフィンガープリントのメタデータを問い合わせることによって、第2のデータストリームにおけるn個のデータブロックのフィンガープリントがそれぞれ第1のデータストリーム内のn個のデータブロックのフィンガープリントと同じであると決定した場合、記憶デバイスによって、第2のデータブロックの論理アドレスと集約アドレスとの間のマッピングを確立するステップであって、ここで、第2のデータストリームにおけるn個のデータブロックのデータブロックシーケンス位置は、第1のデータストリーム内のn個のデータブロックのデータブロックシーケンス位置と同じであり、データブロックシーケンス位置は、第1のデータストリームまたは第2のデータストリームのいずれかにおけるn個のデータブロック内の各データブロックの相対位置を指し、集約アドレスは、集約データブロックの物理アドレスと、集約フィンガープリントのメタデータのアドレス識別子とを含み、集約データブロックの物理アドレスは、第1の物理アドレスと、第1の記憶領域に記憶されているn個のデータブロックの物理アドレス長とを含み、集約フィンガープリントのメタデータのアドレス識別子は、第1のデータブロックのフィンガープリントのメタデータのアドレス識別子と、n個のデータブロックのフィンガープリントのメタデータのアドレス識別子の数とを含む、ステップとを含む。任意で、第1の記憶領域および第2の記憶領域はコンテナである。さらに、第1の記憶領域および第2の記憶領域は同じ記憶領域であり得る。
【００２１】
第2の態様を参照すると、第1の可能な実施方式では、記憶デバイスによって、第2のデータブロックの論理アドレスと集約アドレスとの間のマッピングを確立するステップは、具体的には、
記憶デバイスによって、第2のデータブロックの論理アドレスと、集約データブロックの物理アドレスおよび集約フィンガープリントのメタデータのアドレス識別子の両方との間のマッピングを確立するステップを含む。
【００２２】
第2の態様を参照すると、第2の可能な実施方式では、記憶デバイスによって、第2のデータブロックの論理アドレスと集約アドレスとの間のマッピングを確立するステップは、具体的には、
記憶デバイスによって、第2のデータブロックの論理アドレスと、集約フィンガープリントのメタデータのアドレス識別子との間のマッピングおよび集約フィンガープリントのメタデータのアドレス識別子と、集約データブロックの物理アドレスとの間のマッピングを確立するステップを含む。
【００２３】
第2の態様を参照すると、第3の可能な実施方式では、記憶デバイスによって、第2のデータブロックの論理アドレスと集約アドレスとの間のマッピングを確立するステップは、具体的には、
記憶デバイスによって、第2のデータブロックの論理アドレスと、集約データブロックの物理アドレスとの間のマッピングおよび集約データブロックの物理アドレスと、集約フィンガープリントのメタデータのアドレス識別子との間のマッピングを確立するステップを含む。
【００２４】
第2の態様、または第2の態様の第1乃至第3の可能な実施方式のいずれか1つを参照すると、第4の可能な実施方式では、
方法は、
記憶デバイスによって、第2のデータブロックの論理アドレスと集約アドレスとの間のマッピングを確立するステップの前に、
記憶デバイスによって、第1の記憶領域に記憶されているn個のデータブロックの物理アドレス長が記憶デバイスの圧縮ウィンドウを超過しないと決定するステップをさらに含む。
【００２５】
第2の態様の第4の可能な実施方式を参照すると、第5の可能な実施方式では、方法は、記憶デバイスによって、圧縮ウィンドウに従って、第1の記憶領域に記憶されているn個のデータブロックを圧縮するステップをさらに含む。
【００２６】
第2の態様を参照すると、第6の可能な実施方式では、方法は、
記憶デバイスによって、第1のデータストリームにおけるn個のデータブロックのフィンガープリント内の第1のフィンガープリントの索引を確立するステップであって、ここで、第1のフィンガープリントの索引は、第1のフィンガープリントと、第1のフィンガープリントのメタデータのアドレス識別子との間のマッピングを含む、ステップをさらに含む。任意で、第1のフィンガープリントのメタデータにおける第1のフィンガープリントを特定の整数で割ることによって得られる余りは特定の値を満たす。任意で、第1のフィンガープリントのメタデータにおける第1のフィンガープリントは、第2の記憶領域に記憶されているフィンガープリントのメタデータからランダムに、または一定間隔で抽出される。
【００２７】
第2の態様の様々な可能な実施方式では、第1のデータブロックの論理アドレスは、第1のデータストリームにおけるn個のデータブロックに対応する論理アドレス内の末尾アドレスであり、第2のデータブロックの論理アドレスは、第2のデータストリームにおけるn個のデータブロックに対応する論理アドレス内の末尾アドレスである。任意で、第2のデータブロックの論理アドレスと集約アドレスとの間のマッピングは、マッピングアドレス方向識別子を含む。
【００２８】
対応して、本発明は、第1の態様および第2の態様における様々な可能な実施の解決手段を別々に実行するために、第1の態様および第1の態様の様々な可能な実施方式および第2の態様および第2の態様の様々な可能な実施方式における記憶デバイスとしてそれぞれ使用される記憶デバイスをさらに提供する。記憶デバイスは、第1の態様および第2の態様における様々な可能な実施の解決手段を実施する構造ユニットを含み、または、記憶デバイスは、第1の態様および第2の態様における様々な可能な実施の解決手段をそれぞれ実行するインタフェースおよびプロセッサを含む。
【００２９】
対応して、本発明は、不揮発性コンピュータ可読記憶媒体およびコンピュータプログラム製品をさらに提供する。不揮発性コンピュータ可読記憶媒体およびコンピュータプログラム製品に含まれるコンピュータ命令が、本発明で提供される記憶デバイスのメモリにロードされ、記憶デバイスにおける中央処理装置（Central Processing Unit, CPU）が、コンピュータ命令を実行するとき、記憶デバイスは、第1および第2の態様における様々な可能な実施の解決手段を別々に実行する。
【図面の簡単な説明】
【００３０】
【図１】図1は、本発明の実施形態に係る、記憶デバイスの概略構成図である。
【図２Ａ】図2Aは、本発明の実施形態に係る、非重複データおよびフィンガープリントのメタデータを記憶する概略図である。
【図２Ｂ】図2Bは、本発明の実施形態に係る、非重複データおよびフィンガープリントのメタデータを記憶する概略図である。
【図２Ｃ】図2Cは、本発明の実施形態に係る、非重複データおよびフィンガープリントのメタデータを記憶する概略図である。
【図３】図3は、本発明の実施形態に係る、フィンガープリントの索引の概略図である。
【図４Ａ】図4Aは、本発明の実施形態に係る、非重複データおよびフィンガープリントのメタデータを記憶する概略図である。
【図４Ｂ】図4Bは、本発明の実施形態に係る、非重複データおよびフィンガープリントのメタデータを記憶する概略図である。
【図４Ｃ】図4Cは、本発明の実施形態に係る、非重複データおよびフィンガープリントのメタデータを記憶する概略図である。
【図５】図5は、本発明の実施形態に係る、フィンガープリントの索引の概略図である。
【図６】図6は、本発明の実施形態に係る、記憶デバイスの概略構成図である。
【発明を実施するための形態】
【００３１】
図1に示されるように、重複排除機能を有する記憶デバイスは、中央処理装置（Central Processing Unit, CPU）101およびメモリ102を含む。CPU 101は、メモリ102内のコンピュータ命令を実行して、本発明の実施形態で説明される重複排除操作を実施する。加えて、CPUの計算リソースを節約するために、本発明の実施形態で説明される重複排除操作を実施するために、フィールドプログラマブルゲートアレイ（Field Programmable Gate Array, FPGA）または他のハードウェアが、本発明の実施形態における重複排除における全ての操作を実行し、または、FPGAまたは他のハードウェアおよびCPUが、本発明の実施形態における重複排除における操作の一部を別々に実行する。説明を容易にするために、本発明の実施形態では、記憶デバイスのプロセッサが、本発明の実施形態における重複排除操作を実施するように構成される。記憶デバイスは、データストリームを受信するように構成されるインタフェースをさらに含み、インタフェースはプロセッサと通信する。本発明の実施形態における記憶デバイスは、重複排除後に得られる一意のデータブロック、フィンガープリントのメタデータ等を記憶するように構成される永続記憶媒体をさらに含む。
【００３２】
記憶デバイスによるデータ記憶の間、一般に、重複データブロックは異なるデータストリーム内で繰り返し現れる。1つのデータストリームは1つのデータソース、例えば、1つのファイルまたは1つのアプリケーションを示す。実際のシナリオでは、記憶デバイスは、重複排除操作を実行するとき、1 Mのファイルを複数のデータブロックに分割してよい。ファイルが部分的に変更されている場合、変更されたファイルのほとんどのデータは、変更前に存在するファイルのデータと同じであり、わずかなデータのみが変更前に存在するファイルのデータと異なる。加えて、変更前後に存在するファイル内の重複データブロックは、データブロックシーケンスにおいて基本的に同じ位置を有する。この属性は、本発明の実施形態ではデータブロック重複局所性と呼ばれる。従って、記憶デバイスが、データストリームにおけるデータブロックが重複データブロックであると決定したとき、そのデータブロックに隣接するデータブロックもまた重複データブロックである可能性は高い。従って、記憶デバイスはデータストリームを受信し、データストリームをデータブロックに分割し、データブロックのフィンガープリントを計算し、データブロックのフィンガープリント内の任意のフィンガープリントと同じフィンガープリントが記憶デバイスに記憶されているかどうかを問い合わせる。同一のフィンガープリントが記憶されていない場合、データブロックは非重複データブロックであると示し、記憶デバイスは、記憶されている一意のデータブロックと同じでないデータストリームにおけるデータブロックの論理アドレスのシーケンスで、記憶デバイスの特定の領域の物理アドレスにデータブロックを連続して記憶する。本発明の実施形態では、記憶デバイスの特定の領域は、論理アドレスのシーケンスで、データストリーム内の非重複データブロックを、物理アドレス内に連続して記憶するために使用されるコンテナであってよい。加えて、記憶デバイスは、記憶デバイスの特定の領域の物理アドレス内に、非重複データブロックの論理アドレスのシーケンスで、データストリームにおける非重複データブロックのフィンガープリントのメタデータを連続して記憶する。このようなフィンガープリントメタデータ記憶方式では、その論理アドレスが連続している非重複データブロックのフィンガープリントのメタデータは、データブロック重複局所性に従ってメモリにロードされ、その結果、重複排除プロセスにおけるフィンガープリントの問合せのヒット率が向上する。フィンガープリントのメタデータの記憶領域は、データストリームにおける非重複データブロックを記憶するコンテナの一部であってよく、または、独立したコンテナであってよい。本発明の実施形態では、データブロックの論理アドレスが連続することは、1つのデータブロックの論理アドレスの終了位置が別のデータブロックの論理アドレスの開始位置であることを意味する。同様に、本発明の実施形態では、物理アドレスが連続していることは、1つのデータブロックが記憶されている物理アドレスの終了位置が、別のデータブロックが記憶されている物理アドレスの開始位置であることを意味する。記憶デバイスに記憶されている一意のデータブロックと同一でないデータストリームにおけるデータブロックが、データブロックの論理アドレスのシーケンスで、記憶デバイスの特定の領域における物理アドレス内に連続して記憶されている場合、データブロックが記憶されている物理アドレスは連続している。
【００３３】
本発明の実施形態では、データブロックの論理アドレスのシーケンスで、記憶領域にデータブロックを連続して記憶すること、データブロックの論理アドレスのシーケンスで、記憶領域にデータブロックを順次記憶すること、およびデータブロックの論理アドレスのシーケンスで、記憶領域の物理アドレスにデータブロックを連続して記憶することは同じ意味を有する。その論理アドレスが連続しているデータブロックはまた、記憶領域の物理アドレスにおいて連続している。
【００３４】
図2Aに示されるように、記憶デバイスはデータストリーム1およびデータストリーム2を受信する。例えば、記憶デバイスは、データストリーム1およびデータストリーム2の各々を、固定長チャンキングアルゴリズムを使用することによって、固定長のデータブロックに分割する。説明を容易にするために、本発明の本実施形態では、例えば、データストリーム1およびデータストリーム2内の全てのデータは最初に書き込まれたデータであり、すなわち、データストリーム1およびデータストリーム2を分割することによって得られた固定長の全てのデータブロックは、記憶デバイスにおける一意のブロックである。
【００３５】
データストリーム1は、その論理アドレスが連続しているデータブロック、すなわち、その論理アドレスがLA 1からLA 16であるデータブロックを含み、その論理アドレスがLA 1からLA 16であるデータブロックに対応するフィンガープリントはそれぞれFP 1からFP 16である。データストリーム2は、その論理アドレスが連続しているデータブロック、すなわち、その論理アドレスがLA 30からLA 45であるデータブロックを含み、その論理アドレスがLA 30からLA 45であるデータブロックに対応するフィンガープリントはそれぞれFP 30からFP 45である。
【００３６】
記憶デバイスは、論理アドレスのシーケンスで、1つのデータストリームにおけるデータブロックを同じコンテナに連続して記憶する。記憶デバイスは、論理アドレス：LA 1からLA 16のシーケンスで、データストリーム1におけるデータブロックをコンテナ1の物理アドレスに連続して記憶する。例えば、記憶デバイスは、データストリーム1におけるデータブロックの論理アドレス、LA 1からLA 16のシーケンスで、コンテナ1の物理アドレス、PA 1からPA 16（コンテナ1の開始物理アドレスは、例えばPA 1である）にデータストリーム1におけるデータブロックをそれぞれ記憶し、すなわち、その論理アドレスがLA 1からLA 16であるデータブロックをPA 1からPA 16に順次記憶する。記憶デバイスは、データストリーム1におけるデータブロックの論理アドレスのシーケンスで、データストリーム1におけるデータブロックのフィンガープリントのメタデータ（データブロックのフィンガープリントおよびデータブロックが記憶される物理アドレス）を、コンテナ3の物理アドレスに連続して記憶し、すなわち、FP 1およびPA 1をPA 201に記憶し、FP 2およびPA 2をPA 202に記憶し、FP 3およびPA 3をPA 203に記憶し、FP 4およびPA 4をPA 204に記憶し、FP 5およびPA 5をPA 205に記憶し、FP 6およびPA 6をPA 206に記憶し、FP 7およびPA 7をPA 207に記憶し、FP 8およびPA 8をPA 208に記憶し、FP 9およびPA 9をPA 209に記憶し、FP 10およびPA 10をPA 210に記憶し、FP 11およびPA 11をPA 211に記憶し、FP 12およびPA 12をPA 212に記憶し、FP 13およびPA 13をPA 213に記憶し、FP 14およびPA 14をPA 214に記憶し、FP 15およびPA 15をPA 215に記憶し、FP 16およびPA 16をPA 216に記憶する。
【００３７】
記憶デバイスは、フィンガープリントのメタデータのアドレス識別子からフィンガープリントのメタデータへのマッピングを確立し、すなわち、PA 201からFP 1およびPA 1へのマッピングを確立し、PA 202からFP 2およびPA 2へのマッピングを確立し、PA 203からFP 3およびPA 3へのマッピングを確立し、PA 204からFP 4およびPA 4へのマッピングを確立し、PA 205からFP 5およびPA 5へのマッピングを確立し、PA 206からFP 6およびPA 6へのマッピングを確立し、PA 207からFP 7およびPA 7へのマッピングを確立し、PA 208からFP 8およびPA 8へのマッピングを確立し、PA 209からFP 9およびPA 9へのマッピングを確立し、PA 210からFP 10およびPA 10へのマッピングを確立し、PA 211からFP 11およびPA 11へのマッピングを確立し、PA 212からFP 12およびPA 12へのマッピングを確立し、PA 213からFP 13およびPA 13へのマッピングを確立し、PA 214からFP 14およびPA 14へのマッピングを確立し、PA 215からFP 15およびPA 15へのマッピングを確立し、PA 216からFP 16およびPA 16へのマッピングを確立する。
【００３８】
その論理アドレスがLA 1からLA 16である非重複データブロックは物理アドレスに連続して記憶され、すなわち、非重複データブロックはPA 1からPA 16にそれぞれ記憶され、且つ、その論理アドレスがLA 1からLA 16である非重複データブロックのフィンガープリントのメタデータもまた連続的に記憶され、すなわち、メタデータは、PA 201からPA 216にそれぞれ記憶されているため、LA 1と集約アドレスとの間のマッピングが確立される。集約アドレスは、集約データブロックの物理アドレスおよび集約フィンガープリントのメタデータのアドレス識別子を含む。集約フィンガープリントのメタデータのアドレス識別子は、その論理アドレスがLA 1であるデータブロックに対応するフィンガープリントのメタデータのアドレス識別子およびLA 1からLA 16に対応するデータブロックのフィンガープリントのメタデータのアドレス識別子の数16を含む。集約データブロックの物理アドレスは、その論理アドレスがLA 1であるデータブロックが記憶されている物理アドレスPA 1およびコンテナ1のものであるとともに、その論理アドレスがLA 1からLA 16であるデータブロックが記憶されている物理アドレスの長さを含む。本発明の本実施形態では、その論理アドレスがLA 1からLA 16であるデータブロックはまた、集約データブロックとも呼ばれる。任意で、コンテナ1のものであるとともに、その論理アドレスがLA 1からLA 16であるデータブロックが記憶されている物理アドレスの長さは、実際の物理的な長さを使用することによって示されてよい。任意で、コンテナ1のものであるとともに、その論理アドレスがLA 1からLA 16であるデータブロックのものである物理アドレスの長さは、物理ブロックの数を使用することによって示されてよい。例えば、集約データブロックの物理アドレスは、PA 1+16として表されてよく、これは、その論理アドレスがLA 1からLA 16であるデータブロックが記憶されている物理アドレスはPA 1であり、16個の物理ブロックの合計が物理アドレスに記憶されていることを示す。集約フィンガープリントのメタデータのアドレス識別子は、PA 201+16として表され、これは、その論理アドレスがLA 1であるデータブロックに対応するフィンガープリントのメタデータのアドレス識別子がPA 201であり、LA 1からLA 16に対応するデータブロックのフィンガープリントのメタデータのアドレス識別子の合計数は16であることを示す。実施方式では、記憶デバイスがLA 1と集約アドレスとの間のマッピングを確立することは、具体的には、記憶デバイスが、LA 1とPA 1+16およびPA 201+16の両方との間のマッピングを確立することを含む。マッピングは、LA 1->PA 1+16およびPA 201+16として表される。PA 1+16およびPA 201+16は同じフィールドに記憶される。具体的には、キー（key）-値（value）形式が使用されてよく、すなわち、keyはLA 1であるとともにvalueはPA 1+16およびPA 201+16である。従来技術に記載される方式では、データストリーム1におけるデータブロックのために32個のマッピング、すなわち、LA 1からFP 1へのマッピング、FP 1からPA 1へのマッピング,…,LA 16からFP 16へのマッピングおよびFP 16からPA 16へのマッピングが確立される必要がある。本発明の本実施形態では、1つのマッピングのみ確立される必要がある。従って、記憶デバイスにおけるマッピングエントリの数は低減され、そ��結果、記憶デバイスのメモリ空間は節約され、加えて、フィンガープリントのメタデータが削除される必要があるかどうかは、マッピング関係に従って、決定されることができる。任意で、本発明の本実施形態では、記憶デバイスは、LA 1から集約アドレス1へのマッピングを確立し、ここで、集約アドレス1は、PA 1+8およびPA 201+8を含む。記憶デバイスは、LA 9から集約アドレス2へのマッピングを確立し、ここで、集約アドレス2は、PA 9+8およびPA 209+8を含む。これはまた、記憶デバイスにおけるマッピングエントリの数を低減することができ、加えて、フィンガープリントのメタデータが削除される必要があるかどうかは、マッピング関係に従って決定されることができる。集約データブロックの具体的な物理アドレス長は、具体的な実施に従って指定されてよい。このことは、本発明では限定されない。
【００３９】
別の実施方式では、記憶デバイスがLA 1と集約アドレスとの間のマッピングを確立することは、具体的には、記憶デバイスが、LA 1と集約フィンガープリントのメタデータのアドレス識別子との間のマッピングを確立し、集約フィンガープリントのメタデータのアドレス識別子と集約データブロックの物理アドレスとの間のマッピングを確立することを含む。集約フィンガープリントのメタデータのアドレス識別子は、その論理アドレスがLA 1であるデータブロックに対応するフィンガープリントのメタデータのアドレス識別子と、LA 1からLA 16に対応するデータブロックのフィンガープリントのメタデータのアドレス識別子の数16を含む。集約データブロックの物理アドレスは、その論理アドレスがLA 1であるデータブロックが記憶されている物理アドレスPA 1およびコンテナ1のものであるとともに、その論理アドレスがLA 1からLA 16であるデータブロックが記憶されている物理アドレスの長さを含む。表現方式では、LA 1からPA 201+16へのマッピングおよびPA 201+16からPA 1+16へのマッピングは、LA 1-> PA 201+16およびPA 201+16->PA 1+16として表されてよく、すなわち、keyはLA 1であるとともに、対応して、valueはPA 201+16であり、且つ、keyはPA 201+16であるとともに、対応して、valueはPA 1+16である。任意で、記憶デバイスは、LA 1と、集約フィンガープリントのメタデータのアドレス識別子3との間のマッピングを確立し、集約フィンガープリントのメタデータのアドレス識別子3と、集約データブロックの物理アドレス3との間のマッピングを確立する。集約フィンガープリントのメタデータのアドレス識別子3はPA 201+8を含み、集約データブロックの物理アドレス3はPA 1+8を含む。記憶デバイスは、LA 9と、集約フィンガープリントのメタデータのアドレス識別子4との間のマッピングおよび、集約フィンガープリントのメタデータのアドレス識別子4と、集約データブロックの物理アドレス4との間のマッピングを確立する。集約フィンガープリントのメタデータのアドレス識別子4はPA 209+8を含み、集約データブロックの物理アドレス4はPA 9+8を含む。
【００４０】
別の実施方式では、記憶デバイスがLA 1と集約アドレスとの間のマッピングを確立することは、具体的には、記憶デバイスが、LA 1と、集約データブロックの物理アドレスとの間のマッピングを確立し、集約データブロックの物理アドレスと、集約フィンガープリントのメタデータのアドレス識別子との間のマッピングを確立することを含む。詳細はここでは説明されない。2つのマッピングは、LA 1->PA 1+16およびPA 1+16-> PA 201+16として表されてよい。すなわち、keyはLA 1であるとともに、対応して、valueはPA 1+16であり、且つ、keyはPA 1+16であるとともに、対応して、valueはPA 201+16である。
【００４１】
記憶デバイスは、論理アドレス：LA 30からLA 45のシーケンスで、データストリーム2におけるデータブロックをコンテナ2の物理アドレスに連続して記憶する。例えば、データストリーム2におけるデータブロックは、データストリーム2におけるデータブロックの論理アドレス、LA 30からLA 45のシーケンスで、コンテナ2の物理アドレス、PA 101からPA 116（コンテナ2の開始物理アドレスは、例えばPA 101である）にそれぞれ記憶される。
【００４２】
記憶デバイスは、データストリーム2におけるデータブロックの論理アドレス、LA 30からLA 45のシーケンスで、データストリーム2におけるデータブロックのフィンガープリントのメタデータを、コンテナ4の物理アドレスに連続して記憶する。すなわち、記憶デバイスは、FP 30およびPA 101をPA 301に記憶し、FP 31およびPA 102をPA 302に記憶し、FP 32およびPA 103をPA 303に記憶し、FP 33およびPA 104をPA 304に記憶し、FP 34およびPA 105をPA 305に記憶し、FP 35およびPA 106をPA 306に記憶し、FP 36およびPA 107をPA 307に記憶し、FP 37およびPA 108をPA 308に記憶し、FP 38およびPA 109をPA 309に記憶し、FP 39およびPA 110をPA 310に記憶し、FP 40およびPA 111をPA 311に記憶し、FP 41およびPA 112をPA 312に記憶し、FP 42およびPA 113をPA 313に記憶し、FP 43およびPA 114をPA 314に記憶し、FP 44およびPA 115をPA 315に記憶し、FP 45およびPA 116をPA 316に記憶する。記憶デバイスは、フィンガープリントのメタデータのアドレス識別子からフィンガープリントのメタデータへのマッピングを確立し、すなわち、PA 301からFP 30およびPA 101へのマッピングを確立し、PA 302からFP 31およびPA 102へのマッピングを確立し、PA 303からFP 32およびPA 103へのマッピングを確立し、PA 304からFP 33およびPA 104へのマッピングを確立し、PA 305からFP 34およびPA 105へのマッピングを確立し、PA 306からFP 35およびPA 106へのマッピングを確立し、PA 307からFP 36およびPA 107へのマッピングを確立し、PA 308からFP 37およびPA 108へのマッピングを確立し、PA 309からFP 38およびPA 109へのマッピングを確立し、PA 310からFP 39およびPA 110へのマッピングを確立し、PA 311からFP 40およびPA 111へのマッピングを確立し、PA 312からFP 41およびPA 112へのマッピングを確立し、PA 313からFP 42およびPA 113へのマッピングを確立し、PA 314からFP 43およびPA 114へのマッピングを確立し、PA 315からFP 44およびPA 115へのマッピングを確立し、PA 316からFP 45およびPA 116へのマッピングを確立する。
【００４３】
その論理アドレスがLA 30からLA 45である非重複データブロックは物理アドレスに連続して記憶され、すなわち、非重複データブロックはPA 101からPA 116にそれぞれ記憶され、且つ、その論理アドレスがLA 30からLA 45である非重複データブロックのフィンガープリントのメタデータもまた連続的に記憶され、すなわち、メタデータは、PA 301からPA 316にそれぞれ記憶されているため、記憶デバイスは、LA 30と集約アドレスとの間のマッピングを確立する。集約アドレスは、集約データブロックの物理アドレスおよび集約フィンガープリントのメタデータのアドレス識別子を含む。集約フィンガープリントのメタデータのアドレス識別子は、その論理アドレスがLA 30であるデータブロックに対応するフィンガープリントのメタデータのアドレス識別子およびLA 30からLA 45に対応するデータブロックのフィンガープリントのメタデータのアドレス識別子の数を含む。集約データブロックの物理アドレスは、その論理アドレスがLA 30であるデータブロックが記憶されている物理アドレスPA 101およびコンテナ2のものであるとともに、その論理アドレスがLA 30からLA 45であるデータブロックが記憶されている物理アドレスの長さを含む。本発明の本実施形態では、その論理アドレスがLA 30からLA 45であるデータブロックはまた、集約データブロックとも呼ばれる。任意で、PA 101からPA 116の長さは、実際の物理的な長さを使用することによって示されてよい。任意で、PA 101からPA 116の長さは、物理ブロックの数16を使用することによって示されてよい。例えば、集約データブロックの物理アドレスは、PA 101+16として表されてよく、集約フィンガープリントのメタデータのアドレス識別子は、PA 301+16として表される。実施方式では、記憶デバイスがLA 30と集約アドレスとの間のマッピングを確立することは、具体的には、記憶デバイスが、LA 30とPA 101+16およびPA 301+16の両方との間のマッピングを確立することを含む。マッピングは、LA 30->PA 101+16およびPA 301+16として表される。具体的な表現については、上で説明された実施を参照されたい。従来技術に記載される方式では、記憶デバイスは、データストリーム2におけるデータブロックのために32個のマッピング、すなわち、LA 30からFP 30へのマッピング、FP 30からPA 301へのマッピング,…,LA 45からFP 45へのマッピングおよびFP 45からPA 316へのマッピングを確立する必要がある。本発明の本実施形態では、1つのマッピングのみ確立される必要がある。従って、記憶デバイスにおけるマッピングエントリの数は低減され、その結果、記憶デバイスのメモリ空間は節約され、加えて、フィンガープリントのメタデータが削除される必要があるかどうかは、マッピング関係に従って、決定されることができる。任意で、本発明の本実施形態では、記憶デバイスは、LA 30から集約アドレス5へのマッピングを確立し、ここで、集約アドレス5は、PA 101+8およびPA 301+8を含む。記憶デバイスは、LA 38から集約アドレス6へのマッピングを確立し、ここで、集約アドレス6は、PA 109+8およびPA 309+8を含む。これはまた、記憶デバイスにおけるマッピングエントリの数を低減することができる。集約データブロックの具体的な物理アドレス長は、具体的な実施に従って指定されてよい。このことは、本発明では限定されない。
【００４４】
別の実施方式では、記憶デバイスがLA 30と集約アドレスとの間のマッピングを確立することは、具体的には、記憶デバイスが、LA 30と集約フィンガープリントのメタデータのアドレス識別子との間のマッピングを確立し、集約フィンガープリントのメタデータのアドレス識別子と集約データブロックの物理アドレスとの間のマッピングを確立することを含む。集約フィンガープリントのメタデータのアドレス識別子は、その論理アドレスがLA 30であるデータブロックに対応するフィンガープリントのメタデータのアドレス識別子と、LA 30からLA 45に対応するデータブロックのフィンガープリントのメタデータのアドレス識別子の数を含む。集約データブロックの物理アドレスは、その論理アドレスがLA 30であるデータブロックが記憶されている物理アドレスPA 101およびコンテナ2のものであるとともに、その論理アドレスがLA 30からLA 45であるデータブロックが記憶されている物理アドレスの長さを含む。表現方式では、LA 30からPA 301+16へのマッピングおよびPA 301+16からPA 101+16へのマッピングは、LA 30-> PA 301+16およびPA 301+16->PA 101+16として表される。具体的な実施については、上で説明される実施を参照されたい。任意で、記憶デバイスは、LA 30と、集約フィンガープリントのメタデータのアドレス識別子7との間のマッピングおよび集約フィンガープリントのメタデータのアドレス識別子7と、集約データブロックの物理アドレス7との間のマッピングを確立する。集約フィンガープリントのメタデータのアドレス識別子7はPA 301+8を含み、集約データブロックの物理アドレス7はPA 30+8を含む。記憶デバイスは、LA 38と、集約フィンガープリントのメタデータのアドレス識別子8との間のマッピングおよび、集約フィンガープリントのメタデータのアドレス識別子8と、集約データブロックの物理アドレス8との間のマッピングを確立する。集約フィンガープリントのメタデータのアドレス識別子8はPA 309+8を含み、集約データブロックの物理アドレス8はPA 38+8を含む。このことはまた、記憶デバイスにおけるマッピングエントリの数を低減することができる。具体的な集約アドレス長は、具体的な実施に従って指定されてよい。このことは、本発明では限定されない。
【００４５】
別の実施方式では、記憶デバイスがLA 30と集約アドレスとの間のマッピングを確立することは、具体的には、記憶デバイスが、LA 30と、集約データブロックの物理アドレスとの間のマッピングを確立し、集約データブロックの物理アドレスと、集約フィンガープリントのメタデータのアドレス識別子との間のマッピングを確立することを含む。2つのマッピングは、LA 30->PA 101+16およびPA 101+16-> PA 301+16として表される。具体的な指示については、上で説明される実施を参照されたく、詳細はここでは再び説明されない。
【００４６】
さらに、記憶デバイスは、その後の重複排除操作におけるフィンガープリントの問合せを容易にするために、フィンガープリントの索引を確立し、記憶デバイスにキャッシュされるフィンガープリントのメタデータ量を低減する。具体的には、データストリーム1およびデータストリーム2におけるデータブロックのフィンガープリントのメタデータにおけるフィンガープリントは、代表フィンガープリント（サンプルフィンガープリントとも呼ばれる）として使用されてよく、ここで、フィンガープリントを特定の整数で割って得られる余りは、特定の値を満たす。例えば、フィンガープリントを10で割って得られる余りは3であり、このフィンガープリントはサンプルフィンガープリントとして使用される。フィンガープリントと、フィンガープリントのメタデータのアドレス識別子との間のマッピングが確立される。別の実施では、フィンガープリントのメタデータ内の、コンテナ3およびコンテナ4に記憶されているフィンガープリントのメタデータから、ランダムに、または一定間隔で抽出されるフィンガープリントは、サンプルフィンガープリントとして使用されてよい。本発明の本実施形態では、コンテナ3およびコンテナ4に記憶されているフィンガープリントのメタデータから一定間隔で抽出されるフィンガープリントのメタデータにおけるフィンガープリントは、図3に示されるフィンガープリントの索引を取得するために、サンプルフィンガープリントとして使用される。
【００４７】
記憶デバイスは、重複排除操作におけるフィンガープリントの問合せを実行するために、図3に示されるフィンガープリントの索引をロードする。
【００４８】
さらに、図4Aに示されるように、記憶デバイスは、データストリーム3を受信し、データストリーム3をデータブロックに分割し、データブロックのフィンガープリントを計算する。その論理アドレスがLA 61であるデータブロックは、その論理アドレスがLA 1であるデータブロックと同じであり、その論理アドレスがLA 62であるデータブロックは、その論理アドレスがLA 2であるデータブロックと同じであり、その論理アドレスがLA 63であるデータブロックは、その論理アドレスがLA 3であるデータブロックと同じであり、その論理アドレスがLA 64であるデータブロックは、その論理アドレスがLA 4であるデータブロックと同じであり、その論理アドレスがLA 65であるデータブロックは、その論理アドレスがLA 5であるデータブロックと同じであり、その論理アドレスがLA 66であるデータブロックは、その論理アドレスがLA 6であるデータブロックと同じであり、その論理アドレスがLA 67であるデータブロックは、その論理アドレスがLA 7であるデータブロックと同じであり、その論理アドレスがLA 68であるデータブロックは、その論理アドレスがLA 8であるデータブロックと同じであり、その論理アドレスがLA 69であるデータブロックは、その論理アドレスがLA 9であるデータブロックと同じであり、その論理アドレスがLA 70であるデータブロックは、その論理アドレスがLA 10であるデータブロックと同じであり、その論理アドレスがLA 71であるデータブロックは、その論理アドレスがLA 11であるデータブロックと同じである。その論理アドレスがLA 1からLA 11であるデータブロックおよびその論理アドレスがLA 61からLA 71であるデータブロックでは、その論理アドレスがLA 1であるデータブロックのデータブロックシーケンス位置は、その論理アドレスがLA 61であるデータブロックのものと同じであり、その論理アドレスがLA 2であるデータブロックのデータブロックシーケンス位置は、その論理アドレスがLA 62であるデータブロックのものと同じであり、・・・、その論理アドレスがLA 11であるデータブロックのデータブロックシーケンス位置は、その論理アドレスがLA 71であるデータブロックのものと同じである。その論理アドレスがLA 61からLA 71であるデータブロックのフィンガープリントは、順次FP 1からFP 11である。
【００４９】
記憶デバイスは、図3に示されるフィンガープリントの索引をロードし、フィンガープリントの索引を検索して、データストリーム3におけるデータブロックのものと同じフィンガープリントがあるかどうかを見つけ出す。本発明の本実施形態では、フィンガープリントのインデックスは、フィンガープリント：FP 1、FP 5、FP 9、FP 13、FP 30、FP 34、FP 38およびFP 42を含む。記憶デバイスは、フィンガープリントの索引におけるものであるとともに、データストリーム3におけるデータブロックのフィンガープリントと同じであるフィンガープリントは、FP 1、FP 5、FP 9およびFP 13であると決定する。データブロック繰返し局所性によると、フィンガープリントの索引における、FP 1、FP 5、FP 9およびFP 13に対応しているフィンガープリントのメタデータ、FP 1およびPA 1、FP 5およびPA 9、FP 9およびPA 9およびFP 13およびPA 13がフィンガープリントのメタデータのアドレス識別子に従ってロードされているときと同時に、FP 2およびPA 2、FP 3およびPA 3、FP 4およびPA 4、FP 6およびPA 6、FP 7およびPA 7、FP 8およびPA 8、FP 10およびPA 10、FP 11およびPA 11、FP 12およびPA 12、FP 14およびPA 14、FP 15およびPA 15、FP 16およびPA 16がロードされる。
【００５０】
記憶デバイスは、フィンガープリントのメタデータを検索し、その論理アドレスがLA 61からLA 71であるデータブロックが重複データブロックであると決定し、従って、その論理アドレスがLA 61からLA 71であるデータブロックはそれ以上記憶されない。記憶デバイスでは、一意のデータブロックのものであるとともに、その論理アドレスがLA 61からLA 71であるデータブロックに対応している物理アドレスは、順次PA 1からPA 11であり、LA 61と集約アドレスとの間のマッピングが確立される。具体的な実施については、本実施形態における前述の説明を参照されたい。実施方式では、記憶デバイスが、LA 61と集約アドレスとの間のマッピングを確立することは、具体的には、記憶デバイスが、LA 61とPA 1+11およびPA 201+11の両方との間のマッピングを確立することを含む。マッピングは、LA 61->PA 1+11およびPA 201+11として表される。具体的な表現方式については、上述の実施を参照されたい。別の実施方式では、記憶デバイスが、LA 61と集約アドレスとの間のマッピングを確立することは、具体的には、記憶デバイスが、LA 61と、集約フィンガープリントのメタデータのアドレス識別子との間のマッピングを確立し、集約フィンガープリントのメタデータのアドレス識別子と、集約データブロックの物理アドレスとの間のマッピングを確立することを含む。2つのマッピングは、具体的には、LA 61からPA 201+11へのマッピングおよびPA 201+11からPA 1+11へのマッピングであり、LA 61->PA 201+11およびPA 201+11->PA 1+11として表される。具体的な表現方式については、上述の実施を参照されたい。別の実施方式では、記憶デバイスが、LA 61と集約アドレスとの間のマッピングを確立することは、具体的には、記憶デバイスが、LA 61と、集約データブロックの物理アドレスとの間のマッピングを確立し、集約データブロックの物理アドレスと、集約フィンガープリントのメタデータのアドレス識別子との間のマッピングを確立することを含む。2つのマッピングは、LA 61->PA 1+11およびPA 1+11->PA 201+11として表される。具体的な表現方式については、上述の実施を参照されたく、詳細はここでは再び説明されない。
【００５１】
その論理アドレスがLA 72からLA 76であるデータブロックは、非重複データブロックである。上述の実施方式によると、データブロック重複局所性を維持するために、データブロックは、論理アドレス：LA 72からLA 76のシーケンスで、物理アドレスPA 401からPA 405としてそれぞれマークされる（本発明の本実施形態では、コンテナ5の開始物理アドレスはPA 401である）、コンテナ5の連続する物理アドレスに記憶される。その論理アドレスがLA 72からLA 76であるデータブロックのフィンガープリントのメタデータは、論理アドレス：LA 72からLA 76のシーケンスで、PA 501からPA 504としてそれぞれマークされる（本発明の本実施形態では、コンテナ6の第1の物理アドレスはPA 501である）、コンテナ6の物理アドレスに連続して記憶される。すなわち、FP 72およびPA 401はPA 501に記憶され、FP 73およびPA 402はPA 502に記憶され、FP 74およびPA 403はPA 503に記憶され、FP 75およびPA 404はPA 504に記憶され、FP 76およびPA 405はPA 505に記憶される。記憶デバイスは、フィンガープリントのメタデータのアドレス識別子からフィンガープリントのメタデータへのマッピングを確立し、すなわち、PA 501からFP 72およびPA 401へのマッピングを確立し、PA 502からFP 73およびPA 402へのマッピングを確立し、PA 503からFP 74およびPA 403へのマッピングを確立し、PA 504からFP 75およびPA 404へのマッピングを確立し、PA 505からFP 76およびPA 405へのマッピングを確立する。その論理アドレスがLA 72からLA76である非重複データブロックは、物理アドレスにおいて連続して記憶されているため、すなわち、非重複データブロックは、PA 401からPA 405に順次記憶され、その論理アドレスがLA 72からLA 76である非重複データブロックのフィンガープリントのメタデータはまた、コンテナ6の物理アドレスにまた連続して記憶されているため、LA 72と集約アドレスとの間のマッピングが確立される。本発明の本実施形態における上述の方法によると、実施方式では、記憶デバイス
が、LA 72と集約アドレスとの間のマッピングを確立することは、具体的には、LA 72とPA 501+5およびPA 601+5との間のマッピングを確立することを含む。マッピングは、LA 72->PA 501+5およびPA 601+5として表される。具体的な表現方式については、上述の実施を参照されたい。別の実施方式では、記憶デバイスが、LA 72と集約アドレスとの間のマッピングを確立することは、具体的には、記憶デバイスが、LA 72と、集約フィンガープリントのメタデータのアドレス識別子との間のマッピングを確立し、集約フィンガープリントのメタデータのアドレス識別子と、集約データブロックの物理アドレスとの間のマッピングを確立することを含む。2つのマッピングは、具体的には、LA 72とPA 601+5との間のマッピングおよびPA 601+5からPA 501+5へのマッピングであるとともに、LA 72->PA 601+5およびPA 601+5->PA 501+5として表される。具体的な表現方式については、上述の実施を参照されたい。別の実施方式では、記憶デバイスが、LA 72と集約アドレスとの間のマッピングを確立することは、具体的には、記憶デバイスが、LA 72と、集約データブロックの物理アドレスとの間のマッピングを確立し、集約データブロックの物理アドレスと、集約フィンガープリントのメタデータのアドレス識別子との間のマッピングを確立することを含む。2つのマッピングは、LA 72->PA 501+5およびPA 501+5->PA 601+5として表される。具体的な表現方式については、上述の実施を参照されたく、詳細はここでは再び説明されない。
【００５２】
記憶デバイスは、その論理アドレスがLA 64からLA 68である非重複データブロックのフィンガープリントに対してサンプリングを実行し、フィンガープリントの索引を確立する。本発明の本実施形態では、フィンガープリントのメタデータにおけるものであり、コンテナ6に記憶されているフィンガープリントのメタデータから一定間隔で抽出されるフィンガープリントは、図3におけるものと比較して、図5に示される新しいフィンガープリントの索引を取得するために、サンプルフィンガープリントとして使用される。
【００５３】
本発明の本実施形態では、例えば、記憶デバイスは、LA 1->PA 1+16およびPA 201+16のマッピングを確立する。記憶デバイスがデータ読出し要求を受信するとき、ここで、データ読出し要求で搬送される論理アドレスはLA 2であるが、記憶デバイスは、LA 1->PA 1+16およびPA 201+16のマッピングを問い合わせ、LA 2とLA 1との間に1つの論理アドレスの差があると決定し、従って、記憶デバイスは、論理アドレスに対応する物理アドレスからデータを読み出し、ここで、論理アドレスとLA 1との間に1つの論理アドレスの差がある。
【００５４】
実際の実施では、記憶デバイスは、圧縮アルゴリズムを使用することによって、記憶された一意のデータブロックを圧縮する。記憶デバイスは、一意のデータブロックを圧縮するために圧縮ウィンドウを設定する。圧縮ウィンドウは、一度に圧縮されることができるデータブロックの長さを指す。従って、本発明の本実施形態では、集約データブロックの物理アドレス長は、圧縮ウィンドウを超過しない。任意で、論理アドレスから集約アドレスへのマッピングを確立する前に、記憶デバイスは、記憶デバイスの圧縮ウィンドウを問い合わせ、集約データブロックの物理アドレス長が圧縮ウィンドウを超過しないと決定する。例えば、本発明の本実施形態では、その論理アドレスがLA 1からLA 16であるデータブロックについて、LA 1->PA 1+16およびPA 201+16のマッピングが確立されてよい。しかしながら、集約データブロックの物理アドレス長が圧縮ウィンドウを超過する場合、複数のマッピング、例えば、LA 1->PA 1+8およびPA 201+8のマッピングおよび、LA 9->PA 9+8およびPA 209+8のマッピングが確立され得る。記憶デバイスは、圧縮ウィンドウに従って、記憶された非重複データを圧縮する。
【００５５】
本発明の本実施形態では、コンテナ5に記憶された非重複データおよびコンテナ6に記憶されているフィンガープリントのメタデータは、コンテナ5等の同じコンテナに記憶されてよい。このことは、本発明の本実施形態では限定されない。
【００５６】
本発明の本実施形態では、例えば、その論理アドレスがLA 1からLA 16であるデータブロックについて、LA 1->PA 1+16およびPA 201+16のマッピングが確立されてよい。マッピングは、LA 1から開始することによって、論理アドレスの昇順でアドレッシングが実行されることを示すために使用されるマッピングアドレス方向識別子を含む。任意で、マッピングアドレス方向識別子は、集約データブロックの物理アドレスおよび集約フィンガープリントのメタデータのアドレス識別子を使用することによって表されてよい。例えば、集約データブロックの物理アドレスはPA 1から上がり、且つ、集約フィンガープリントのメタデータのアドレス識別子はPA 201から上がる。対応して、別の実施方式では、LA 16->PA 16-16およびPA 216-16のマッピングが確立されてよい。これはまた、マッピングエントリの数を低減し、記憶デバイスのメモリ空間を節約することができる。マッピングは、LA 16から開始することによって、論理アドレスの降順でアドレッシングが実行されることを示すために使用されるマッピングアドレス方向識別子を含む。任意で、マッピングアドレス方向識別子は、集約データブロックの物理アドレスおよび集約フィンガープリントのメタデータのアドレス識別子を使用することによって表されてよい。例えば、集約データブロックの物理アドレスはPA 16から下がり、且つ、集約フィンガープリントのメタデータのアドレス識別子はPA 216から下がる。詳細は、本発明の本実施形態では説明されない。
【００５７】
本発明の本実施形態では、データストリームをデータブロックに分割するために、固定長チャンキングアルゴリズムが例として使用される。別のシナリオでは、コンテンツ定義チャンキング（Content-Defined Chunking, CDC）アルゴリズム等の可変長チャンキングアルゴリズムが、データストリームをデータブロックに分割するために使用されてよい。本発明の本実施形態における記憶デバイスは、ネットワーク接続システム（Network Attached System, NAS）等のファイルシステムにおいて重複排除操作を実施してよく、対応して、本発明の本実施形態における論理アドレスは、ファイル識別子にオフセットアドレスを加えたものである。本発明の本実施形態における記憶デバイスはまた、ネットワーク、例えば、ストレージエリアネットワーク（Storage Area Network, SAN）においてデータブロックに対して重複排除操作を実施してよく、対応して、本発明の本実施形態における論理アドレスは、論理ブロックアドレス（logical block address, LBA）である。
【００５８】
本発明の本実施形態では、フィンガープリントのメタデータのアドレス識別子は、フィンガープリントのメタデータを一意に識別する論理識別子であってよい。記憶デバイスは、グローバル一意識別子を、一意のデータブロックに対応するフィンガープリントのメタデータに割り当ててよい。その論理アドレスが連続している複数の一意のデータブロックのフィンガープリントのメタデータのアドレス識別子は線形に増加する。例えば、その論理アドレスがLA 1からLA 16であるデータブロックのフィンガープリントのメタデータのアドレス識別子は、順次チャンク識別子（Chunk Identifier, 略してChunk ID）1からChunk ID 16であってよい。具体的な実施では、記憶デバイスは、データストリームに対して重複排除操作を実行して、データストリームにおけるものであるとともにその論理アドレスが連続している一意のデータブロックを決定する。記憶デバイスは、一意のデータブロックの論理アドレスのシーケンスで、コンテナの物理アドレスに、データストリームにおけるものであるとともにその論理アドレスが連続している一意のデータブロックのフィンガープリントのメタデータを順次記憶する。記憶デバイスは、一意のデータブロックの論理アドレスのシーケンスで、これらの一意のデータブロックのフィンガープリントのメタデータについて、グローバル一意Chunk IDを生成する。これらのChunk IDは、これらの一意のデータブロックの論理アドレスのシーケンスで線形に増加する。
【００５９】
本発明の本実施形態では、同じデータストリームにおける一意のデータブロックおよび一意のデータブロックのフィンガープリントのメタデータは、異なるコンテナに別々に記憶される。他の実施では、同じデータストリームにおける一意のデータブロックおよび一意のデータブロックのフィンガープリントのメタデータは、同じコンテナの異なる記憶領域に記憶されてよい。
【００６０】
本発明の本実施形態では、コンテナは、一意のデータブロックおよびフィンガープリントのメタデータを記憶するために使用される。別の実施では、一意のデータブロックおよびフィンガープリントのメタデータを記憶するためにツリー構造が使用されてよい。具体的な実施においては、一意のデータブロックおよびフィンガープリントのメタデータを記憶するために、ツリーの葉ノードが使用されてよい。
【００６１】
任意で、本発明の本実施形態では、本発明の本実施形態における論理アドレスから集約アドレスへのマッピングは、その論理アドレスが連続している重複データブロックに対してのみ確立されてよい。その論理アドレスが連続している非重複データブロックについては、既存の実施に従って、1対1マッピングが確立される。
【００６２】
図6に示されるように、本発明の実施形態は、受信ユニット601、分割ユニット602、計算ユニット603、記憶ユニット604および確立ユニット605を含む、記憶デバイス600を提供する。受信ユニット601は、第1のデータストリームを受信するように構成される。分割ユニット602は、第1のデータストリームを分割して、n個のデータブロックを取得するように構成され、ここで、n個のデータブロックの論理アドレスは連続し、n個のデータブロックは第1のデータブロックを含み、第1のデータブロックの論理アドレスは、n個のデータブロックに対応する論理アドレス内の先頭アドレスであり、nは2以上の整数である。計算ユニット603は、n個のデータブロックを計算して、n個のデータブロックのフィンガープリントを取得するように構成される。記憶ユニット604は、n個のデータブロックのフィンガープリントが記憶デバイス600におけるフィンガープリント内で見つからない場合、n個のデータブロックの論理アドレスのシーケンスで、第1の記憶領域に、n個のデータブロックを連続して記憶し、n個のデータブロックの論理アドレスのシーケンスで、第2の記憶領域に、n個のデータブロックのフィンガープリントのメタデータを連続して記憶するように構成され、ここで、第1の記憶領域に記憶された第1のデータブロックの物理アドレスは第1の物理アドレスであり、n個のデータブロックのフィンガープリントにおける各フィンガープリントのメタデータは、n個のデータブロックのフィンガープリントにおけるそれぞれのフィンガープリントと、それぞれのフィンガープリントのものであるとともに、第2の記憶領域に記憶されている物理アドレスとを含む。確立ユニット605は、n個のデータブロックのフィンガープリントにおける各フィンガープリントのメタデータのアドレス識別子と、n個のデータブロックのフィンガープリントにおけるそれぞれのフィンガープリントのメタデータとの間のマッピングを確立し、第1のデータブロックの論理アドレスと集約アドレスとの間のマッピングを確立するように構成され、ここで、集約アドレスは、集約データブロックの物理アドレスと、集約フィンガープリントのメタデータのアドレス識別子とを含み、集約データブロックの物理アドレスは、第1の物理アドレスと、第1の記憶領域に記憶されているn個のデータブロックの物理アドレス長とを含み、集約フィンガープリントのメタデータのアドレス識別子は、第1のデータブロックのフィンガープリントのメタデータのアドレス識別子と、n個のデータブロックのフィンガープリントのメタデータのアドレス識別子の数とを含む。
【００６３】
本発明の実施形態では、記憶デバイスにおけるマッピングエントリの数は低減され、その結果、記憶デバイスのメモリ空間は節約され、加えて、フィンガープリントのメタデータが削除される必要があるかどうかは、マッピング関係に従って決定されることができる。
【００６４】
任意で、記憶デバイス600における第1の記憶領域および第2の記憶領域はコンテナである。さらに、第1の記憶領域および第2の記憶領域は同じ記憶領域であり得る。
【００６５】
任意で、確立ユニット605は、具体的には、第1のデータブロックの論理アドレスと、集約データブロックの物理アドレスおよび集約フィンガープリントのメタデータのアドレス識別子の両方との間のマッピングを確立するように構成される。
【００６６】
任意で、確立ユニット605は、具体的には、第1のデータブロックの論理アドレスと、集約フィンガープリントのメタデータのアドレス識別子との間のマッピングおよび集約フィンガープリントのメタデータのアドレス識別子と、集約データブロックの物理アドレスとの間のマッピングを確立するように構成される。
【００６７】
任意で、確立ユニット605は、具体的には、第1のデータブロックの論理アドレスと、集約データブロックの物理アドレスとの間のマッピングおよび集約データブロックの物理アドレスと、集約フィンガープリントのメタデータのアドレス識別子との間のマッピングを確立するように構成される。
【００６８】
任意で、記憶デバイス600は決定ユニットをさらに含み、ここで、決定ユニットは、第1のデータブロックの論理アドレスと集約アドレスとの間のマッピングが確立される前に、第1の記憶領域に記憶されているn個のデータブロックの物理アドレス長が記憶デバイスの圧縮ウィンドウを超過しないと決定するように構成される。任意で、記憶デバイス600は圧縮ユニットをさらに含み、ここで、圧縮ユニットは、圧縮ウィンドウに従って、第1の記憶領域に記憶されているn個のデータブロックを圧縮するように構成される。
【００６９】
任意で、受信ユニット601は、第2のデータストリームを受信するようにさらに構成される。分割ユニット602は、第2のデータストリームを分割して、n個のデータブロックを取得するようにさらに構成され、ここで、第2のデータストリームにおけるn個のデータブロックの論理アドレスは連続し、第2のデータストリームにおけるn個のデータブロックは第2のデータブロックを含み、第2のデータブロックの論理アドレスは、第2のデータストリームにおけるn個のデータブロックに対応する論理アドレス内の先頭アドレスである。計算ユニット603は、第2のデータストリームにおけるn個のデータブロックを計算して、第2のデータストリームにおけるn個のデータブロックのフィンガープリントを取得するようにさらに構成される。確立ユニット605は、記憶デバイス600が、第1のデータストリームにおけるn個のデータブロックのフィンガープリントのメタデータを問い合わせることによって、第2のデータストリームにおけるn個のデータブロックのフィンガープリントがそれぞれ第1のデータストリーム内のn個のデータブロックのフィンガープリントと同じであると決定した場合、第2のデータブロックの論理アドレスと集約アドレスとの間のマッピングを確立するようにさらに構成され、ここで、第2のデータストリームにおけるn個のデータブロックのデータブロックシーケンス位置は、第1のデータストリーム内のn個のデータブロックのデータブロックシーケンス位置と同じであり、データブロックシーケンス位置は、第1のデータストリームまたは第2のデータストリームのいずれかにおけるn個のデータブロック内の各データブロックの相対位置を指す。
【００７０】
任意で、確立ユニット605は、第1のデータストリームにおけるn個のデータブロックのフィンガープリント内の第1のフィンガープリントの索引を確立するようにさらに構成され、ここで、第1のフィンガープリントの索引は、第1のフィンガープリントと、第1のフィンガープリントのメタデータのアドレス識別子との間のマッピングを含む。
【００７１】
本発明の本実施形態で提供される記憶デバイス600の具体的な機能および具体的な実施については、前述の実施形態で説明される方法およびステップを参照されたく、詳細はここでは再び説明されない。
【００７２】
図6に示される記憶デバイス600については、実施方式では、前述のユニットは記憶デバイス600上にインストールされ、前述のユニットは記憶デバイス600のメモリにロードされてよく、記憶デバイス600内のCPUは、本発明の対応する実施形態における機能を実施するためにメモリ内の命令を実行する。別の実施においては、記憶デバイス600に含まれるユニットは、ハードウェアを使用することによって、または、ハードウェアおよびCPUがメモリ内の命令を実行する方式で、実施されてよい。前述のユニットはまた、構造ユニットとも呼ばれる。
【００７３】
本発明の実施形態は、不揮発性コンピュータ可読記憶媒体およびコンピュータプログラム製品をさらに提供する。不揮発性コンピュータ可読記憶媒体に含まれるコンピュータ命令およびコンピュータプログラム製品が、図6に示される記憶デバイス600内のCPUのメモリにロードされるとき、CPUは、本発明の実施形態の全てにおける対応する機能を実施するために、メモリにロードされたコンピュータ命令を実行する。
【００７４】
本発明で提供される実施形態では、開示される装置および方法が他の方式で実施されてよいことは理解されるべきである。例えば、説明される装置の実施形態におけるユニット分割は、単なる論理的な機能分割であり、実際の実施においては別の分割であってよい。例えば、複数のユニットまたは構成要素は、別のシステムに結合または統合されてよく、または、いくつかの特徴は無視されるか実行されなくてよい。加えて、表示されるまたは議論される相互結合または直接結合または通信接続は、いくつかのインタフェースを使用することによって実施されてよい。装置またはユニット間の間接結合または通信接続は、電気的、機械的または他の形態で実施されてよい。
【００７５】
分離した部分として記載されるユニットは物理的に分離していてもしていなくてもよく、ユニットとして表示される部分は、物理的なユニットであってもなくてもよく、1つの位置に配置されてよく、または、複数のネットワークユニットに分配されてよい。ユニットの一部または全ては、実施形態の解決手段の目的を達成するための実際のニーズに従って選択されてよい。
【００７６】
加えて、本発明の実施形態における機能ユニットは、1つの処理ユニットに統合されてよく、または、ユニットの各々は物理的に孤立して存在してよく、または、2つ以上のユニットは1つのユニットに統合されてよい。
【符号の説明】
【００７７】
102  メモリ
601  受信ユニット
602  分割ユニット
603  計算ユニット
604  記憶ユニット
605  確立ユニット
【図１】
0006537214.tif 000002
【図２Ａ】
0006537214.tif 000003
【図２Ｂ】
0006537214.tif 000004
【図２Ｃ】
0006537214.tif 000005
【図３】
0006537214.tif 000006
【図４Ａ】
0006537214.tif 000007
【図４Ｂ】
0006537214.tif 000008
【図４Ｃ】
0006537214.tif 000009
【図５】
0006537214.tif 000010
【図６】
0006537214.tif 000011