(57)【要約】【課題】内部記憶システムからリムーバブル記憶システムへの重複排除データの移動／コピーを最適化するための機構を提供する。【解決手段】データ・オブジェクトの組の数に基づいて、内部記憶システムに保存されるデータ・オブジェクトの組に対して生成されるべきクラスタの予備数が定められる。データ・オブジェクトの組間の最短距離に基づいて、予備数のクラスタが生成され、各クラスタはデータ・オブジェクトの１つまたはそれ以上の組を含み、データ・オブジェクトの各組はデータの１つまたはそれ以上のチャンクを含む。できる限り少ないデータ・オブジェクトの組の中に最大数の共通チャンクを有するクラスタを識別することによって、クラスタの組の中から選択されたクラスタが識別される。選択されたクラスタのエクスポート・サイズがリムーバブル記憶システムの利用可能な記憶容量を超えていないことに応答して、選択されたクラスタがリムーバブル記憶システムにエクスポートされる。【選択図】図２
2015505997.tif 000002
【特許請求の範囲】
【請求項１】
データ処理システムにおいて、内部記憶システムからリムーバブル記憶システムへの重複排除データの移動／コピーを最適化するための方法であって、前記方法は、
データ・オブジェクトの組の数に基づいて、前記内部記憶システムに保存される前記データ・オブジェクトの組に対して生成されるべきクラスタの予備数を定めるステップと、
前記データ・オブジェクトの組間の最短距離に基づいて前記予備数のクラスタを生成するステップであって、各クラスタはデータ・オブジェクトの１つまたはそれ以上の組を含み、データ・オブジェクトの各組はデータの１つまたはそれ以上のチャンクを含む、ステップと、
できる限り少ないデータ・オブジェクトの組の中に最大数の共通チャンクを有するクラスタを識別することによって、クラスタの組の中から選択されたクラスタを識別するステップと、
前記選択されたクラスタのエクスポート・サイズが、前記リムーバブル記憶システムの利用可能な記憶容量を超えているかどうかを判定するステップと、
前記選択されたクラスタの前記エクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な記憶容量を超えていないことに応答して、前記選択されたクラスタを前記リムーバブル記憶システムにエクスポートするステップと
を含む、方法。
【請求項２】
前記選択されたクラスタにおけるデータ・オブジェクトの１つの組のデータの少なくとも１つのチャンクは、前記選択されたクラスタにおけるデータ・オブジェクトの別の組のデータの少なくとも１つのチャンクを参照する、請求項１に記載の方法。
【請求項３】
前記選択されたクラスタが前記リムーバブル記憶媒体にエクスポートされた後に、前記選択されたクラスタに関連する前記データ・オブジェクトの組を、移動のためのさらなる検討から除去するステップ
をさらに含む、請求項１に記載の方法。
【請求項４】
前記選択されたクラスタに関連する前記データ・オブジェクトの組を移動のためのさらなる検討から除去した後に、前記リムーバブル記憶システムにおける前記データ・オブジェクトの組の位置に対する参照を前記内部記憶システムに挿入するステップと、
前記選択されたクラスタに関連するすべてのデータを前記内部記憶システムから削除するステップと
をさらに含む、請求項３に記載の方法。
【請求項５】
前記選択されたクラスタを前記リムーバブル記憶システムにエクスポートする前に、前記選択されたクラスタ内の、前記選択されたクラスタの部分ではないチャンク・データ参照を修正して、データのそれらのチャンクを参照しないようにするステップ
をさらに含む、請求項１に記載の方法。
【請求項６】
前記データ・オブジェクトの組の数に基づいて、前記内部記憶システムに保存されるデータ・オブジェクトの組に対して生成されるべきクラスタの前記予備数を定めるステップは、
前記内部記憶システムに保存されるデータ・オブジェクトの組に集約されたすべての複数参照チャンクを含むチャンク参照テーブルを生成するステップと、
データ・オブジェクトの各組に対して、そのデータ・オブジェクトの組によって参照される複数参照チャンクを示すチャンク・マトリックス・テーブルを生成するステップと、
前記チャンク・マトリックス・テーブルを用いて、データ・オブジェクトの各組に対する前記チャンク・マトリックス・テーブル内の点のｎ次元表現を生成するステップと、
前記データ・オブジェクトの組のｎ次元空間における点としての前記表現を用いて、前記データ・オブジェクトの組の各々の間の距離を示す、前記データ・オブジェクトの組の各々の間のメトリック値を算出するステップと、
結果として得られる前記メトリック値をメトリック・マトリックスに挿入するステップと
を含む、請求項１に記載の方法。
【請求項７】
前記選択されたクラスタの前記エクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な記憶容量を超えていることに応答して、前記クラスタの配置を禁止クラスタのリストに加えるステップと、
前記選択されたクラスタがデータ・オブジェクトの３つ以上の組を有するかどうかを判定するステップと、
前記選択されたクラスタがデータ・オブジェクトの３つ以上の組を有することに応答して、最後に加えられたデータ・オブジェクトの組を前記クラスタから除去するステップと、
前記選択されたクラスタの新たなエクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な記憶容量を超えているかどうかを判定するステップと、
前記選択されたクラスタの前記新たなエクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な記憶容量を超えていないことに応答して、前記最良のクラスタを前記リムーバブル記憶システムにエクスポートするステップと
をさらに含む、請求項１に記載の方法。
【請求項８】
前記選択されたクラスタの前記エクスポート・サイズが、前記リムーバブル記憶システムの前記利用可能な容量から予め定義された安全マージンを引いたものを超えているかどうかを判定するステップと、
前記選択されたクラスタの前記エクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な容量から前記予め定義された安全マージンを引いたものを超えていることに応答して、前記選択されたクラスタを前記リムーバブル記憶システムにエクスポートするステップと
をさらに含む、請求項１に記載の方法。
【請求項９】
前記選択されたクラスタの前記エクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な容量から前記予め定義された安全マージンを引いたものを超えていないことに応答して、なおも移動／コピーすべきデータ・オブジェクトの追加の組があるかどうかを判定するステップと、
なおも移動／コピーすべき前記データ・オブジェクトの追加の組の存在に応答して、すでに前記クラスタ内にある前記データ・オブジェクトの組に対する次の最短距離を有するデータ・オブジェクトの次の組を前記選択されたクラスタに加えるステップと、
前記選択されたクラスタの前記エクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な記憶容量を超えているかどうかを判定するステップと、
前記選択されたクラスタの前記エクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な記憶容量を超えていないことに応答して、前記選択されたクラスタを前記リムーバブル記憶システムにエクスポートするステップと
をさらに含む、請求項８に記載の方法。
【請求項１０】
前記データ・オブジェクトの組の間の距離は、差の二乗和の平方根を含むユークリッド距離、前記平方根が取られない前記ユークリッド距離の変形、差の絶対値の和、または１つのチャンクから別のチャンクへのアクセスの合計時間のうちの少なくとも１つに基づいて定められる、請求項１に記載の方法。
【請求項１１】
コンピュータ読取り可能プログラムが中に保存されたコンピュータ読取り可能記憶媒体を含むコンピュータ・プログラム製品であって、前記コンピュータ読取り可能プログラムは、コンピュータ・デバイス上で実行されるときに、
データ・オブジェクトの組の数に基づいて、内部記憶システムに保存される前記データ・オブジェクトの組に対して生成されるべきクラスタの予備数を定めるステップと、
前記データ・オブジェクトの組間の最短距離に基づいて前記予備数のクラスタを生成するステップであって、各クラスタはデータ・オブジェクトの１つまたはそれ以上の組を含み、データ・オブジェクトの各組はデータの１つまたはそれ以上のチャンクを含む、ステップと、
できる限り少ないデータ・オブジェクトの組の中に最大数の共通チャンクを有するクラスタを識別することによって、クラスタの組の中から選択されたクラスタを識別するステップと、
前記選択されたクラスタのエクスポート・サイズが、リムーバブル記憶システムの利用可能な記憶容量を超えているかどうかを判定するステップと、
前記選択されたクラスタの前記エクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な記憶容量を超えていないことに応答して、前記選択されたクラスタを前記リムーバブル記憶システムにエクスポートするステップと
を前記コンピュータ・デバイスに行わせる、コンピュータ・プログラム製品。
【請求項１２】
前記選択されたクラスタにおけるデータ・オブジェクトの１つの組のデータの少なくとも１つのチャンクは、前記選択されたクラスタにおけるデータ・オブジェクトの別の組のデータの少なくとも１つのチャンクを参照する、請求項１１に記載のコンピュータ・プログラム製品。
【請求項１３】
前記コンピュータ読取り可能プログラムはさらに、
前記選択されたクラスタを前記リムーバブル記憶システムにエクスポートする前に、前記選択されたクラスタ内の、前記選択されたクラスタの部分ではないチャンク・データ参照を修正して、データのそれらのチャンクを参照しないようにするステップ
を前記コンピュータ・デバイスに行わせる、請求項１１に記載のコンピュータ・プログラム製品。
【請求項１４】
前記データ・オブジェクトの組の数に基づいて、前記内部記憶システムに保存されるデータ・オブジェクトの組に対して生成されるべきクラスタの前記予備数を定めるための前記コンピュータ読取り可能プログラムはさらに、
前記内部記憶システムに保存されるデータ・オブジェクトの組に集約されたすべての複数参照チャンクを含むチャンク参照テーブルを生成するステップと、
データ・オブジェクトの各組に対して、そのデータ・オブジェクトの組によって参照される複数参照チャンクを示すチャンク・マトリックス・テーブルを生成するステップと、
前記チャンク・マトリックス・テーブルを用いて、データ・オブジェクトの各組に対する前記チャンク・マトリックス・テーブル内の点のｎ次元表現を生成するステップと、
前記データ・オブジェクトの組のｎ次元空間における点としての前記表現を用いて、前記データ・オブジェクトの組の各々の間の距離を示す、前記データ・オブジェクトの組の各々の間のメトリック値を算出するステップと、
結果として得られる前記メトリック値をメトリック・マトリックスに挿入するステップと
を前記コンピュータ・デバイスに行わせる、請求項１１に記載のコンピュータ・プログラム製品。
【請求項１５】
前記コンピュータ読取り可能プログラムはさらに、
前記選択されたクラスタの前記エクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な記憶容量を超えていることに応答して、前記クラスタの配置を禁止クラスタのリストに加えるステップと、
前記選択されたクラスタがデータ・オブジェクトの３つ以上の組を有するかどうかを判定するステップと、
前記選択されたクラスタがデータ・オブジェクトの３つ以上の組を有することに応答して、最後に加えられたデータ・オブジェクトの組を前記クラスタから除去するステップと、
前記選択されたクラスタの新たなエクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な記憶容量を超えているかどうかを判定するステップと、
前記選択されたクラスタの前記新たなエクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な記憶容量を超えていないことに応答して、前記最良のクラスタを前記リムーバブル記憶システムにエクスポートするステップと
を前記コンピュータ・デバイスに行わせる、請求項１１に記載のコンピュータ・プログラム製品。
【請求項１６】
前記コンピュータ読取り可能プログラムはさらに、
前記選択されたクラスタの前記エクスポート・サイズが、前記リムーバブル記憶システムの前記利用可能な容量から予め定義された安全マージンを引いたものを超えているかどうかを判定するステップと、
前記選択されたクラスタの前記エクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な容量から前記予め定義された安全マージンを引いたものを超えていることに応答して、前記選択されたクラスタを前記リムーバブル記憶システムにエクスポートするステップと
を前記コンピュータ・デバイスに行わせる、請求項１１に記載のコンピュータ・プログラム製品。
【請求項１７】
前記コンピュータ読取り可能プログラムはさらに、
前記選択されたクラスタの前記エクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な容量から前記予め定義された安全マージンを引いたものを超えていないことに応答して、なおも移動／コピーすべきデータ・オブジェクトの追加の組があるかどうかを判定するステップと、
なおも移動／コピーすべき前記データ・オブジェクトの追加の組の存在に応答して、すでに前記クラスタ内にある前記データ・オブジェクトの組に対する次の最短距離を有するデータ・オブジェクトの次の組を前記選択されたクラスタに加えるステップと、
前記選択されたクラスタの前記エクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な記憶容量を超えているかどうかを判定するステップと、
前記選択されたクラスタの前記エクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な記憶容量を超えていないことに応答して、前記選択されたクラスタを前記リムーバブル記憶システムにエクスポートするステップと
を前記コンピュータ・デバイスに行わせる、請求項１６に記載のコンピュータ・プログラム製品。
【請求項１８】
装置であって、
プロセッサと、
前記プロセッサに結合されたメモリとを含み、前記メモリは命令を含み、前記命令は前記プロセッサによって実行されるときに、
データ・オブジェクトの組の数に基づいて、内部記憶システムに保存される前記データ・オブジェクトの組に対して生成されるべきクラスタの予備数を定めるステップと、
前記データ・オブジェクトの組間の最短距離に基づいて前記予備数のクラスタを生成するステップであって、各クラスタはデータ・オブジェクトの１つまたはそれ以上の組を含み、データ・オブジェクトの各組はデータの１つまたはそれ以上のチャンクを含む、ステップと、
できる限り少ないデータ・オブジェクトの組の中に最大数の共通チャンクを有するクラスタを識別することによって、クラスタの組の中から選択されたクラスタを識別するステップと、
前記選択されたクラスタのエクスポート・サイズが、リムーバブル記憶システムの利用可能な記憶容量を超えているかどうかを判定するステップと、
前記選択されたクラスタの前記エクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な記憶容量を超えていないことに応答して、前記選択されたクラスタを前記リムーバブル記憶システムにエクスポートするステップと
を前記プロセッサに行わせる、装置。
【請求項１９】
前記選択されたクラスタにおけるデータ・オブジェクトの１つの組のデータの少なくとも１つのチャンクは、前記選択されたクラスタにおけるデータ・オブジェクトの別の組のデータの少なくとも１つのチャンクを参照する、請求項１８に記載の装置。
【請求項２０】
前記命令はさらに、
前記選択されたクラスタを前記リムーバブル記憶システムにエクスポートする前に、前記選択されたクラスタ内の、前記選択されたクラスタの部分ではないチャンク・データ参照を修正して、データのそれらのチャンクを参照しないようにするステップ
を前記プロセッサに行わせる、請求項１８に記載の装置。
【請求項２１】
前記データ・オブジェクトの組の数に基づいて、前記内部記憶システムに保存されるデータ・オブジェクトの組に対して生成されるべきクラスタの前記予備数を定めるための前記命令はさらに、
前記内部記憶システムに保存されるデータ・オブジェクトの組に集約されたすべての複数参照チャンクを含むチャンク参照テーブルを生成するステップと、
データ・オブジェクトの各組に対して、そのデータ・オブジェクトの組によって参照される複数参照チャンクを示すチャンク・マトリックス・テーブルを生成するステップと、
前記チャンク・マトリックス・テーブルを用いて、データ・オブジェクトの各組に対する前記チャンク・マトリックス・テーブル内の点のｎ次元表現を生成するステップと、
前記データ・オブジェクトの組のｎ次元空間における点としての前記表現を用いて、前記データ・オブジェクトの組の各々の間の距離を示す、前記データ・オブジェクトの組の各々の間のメトリック値を算出するステップと、
結果として得られる前記メトリック値をメトリック・マトリックスに挿入するステップと
を前記プロセッサに行わせる、請求項１８に記載の装置。
【請求項２２】
前記命令はさらに、
前記選択されたクラスタの前記エクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な記憶容量を超えていることに応答して、前記クラスタの配置を禁止クラスタのリストに加えるステップと、
前記選択されたクラスタがデータ・オブジェクトの３つ以上の組を有するかどうかを判定するステップと、
前記選択されたクラスタがデータ・オブジェクトの３つ以上の組を有することに応答して、最後に加えられたデータ・オブジェクトの組を前記クラスタから除去するステップと、
前記選択されたクラスタの新たなエクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な記憶容量を超えているかどうかを判定するステップと、
前記選択されたクラスタの前記新たなエクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な記憶容量を超えていないことに応答して、前記最良のクラスタを前記リムーバブル記憶システムにエクスポートするステップと
を前記プロセッサに行わせる、請求項１８に記載の装置。
【請求項２３】
前記命令はさらに、
前記選択されたクラスタの前記エクスポート・サイズが、前記リムーバブル記憶システムの前記利用可能な容量から予め定義された安全マージンを引いたものを超えているかどうかを判定するステップと、
前記選択されたクラスタの前記エクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な容量から前記予め定義された安全マージンを引いたものを超えていることに応答して、前記選択されたクラスタを前記リムーバブル記憶システムにエクスポートするステップと
を前記プロセッサに行わせる、請求項１８に記載の装置。
【請求項２４】
前記命令はさらに、
前記選択されたクラスタの前記エクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な容量から前記予め定義された安全マージンを引いたものを超えていないことに応答して、なおも移動／コピーすべきデータ・オブジェクトの追加の組があるかどうかを判定するステップと、
なおも移動／コピーすべき前記データ・オブジェクトの追加の組の存在に応答して、すでに前記クラスタ内にある前記データ・オブジェクトの組に対する次の最短距離を有するデータ・オブジェクトの次の組を前記選択されたクラスタに加えるステップと、
前記選択されたクラスタの前記エクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な記憶容量を超えているかどうかを判定するステップと、
前記選択されたクラスタの前記エクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な記憶容量を超えていないことに応答して、前記選択されたクラスタを前記リムーバブル記憶システムにエクスポートするステップと
を前記プロセッサに行わせる、請求項２３に記載の装置。
【請求項２５】
前記コンピュータ読取り可能プログラムはさらに、
前記選択されたクラスタが前記リムーバブル記憶媒体にエクスポートされた後に、前記選択されたクラスタに関連する前記データ・オブジェクトの組を、移動のためのさらなる検討から除去するステップ
を前記コンピュータ・デバイスに行わせる、請求項１１に記載のコンピュータ・プログラム製品。
【請求項２６】
前記コンピュータ読取り可能プログラムはさらに、
前記選択されたクラスタに関連する前記データ・オブジェクトの組を移動のためのさらなる検討から除去した後に、前記リムーバブル記憶システムにおける前記データ・オブジェクトの組の位置に対する参照を前記内部記憶システムに挿入するステップと、
前記選択されたクラスタに関連するすべてのデータを前記内部記憶システムから削除するステップと
を前記コンピュータ・デバイスに行わせる、請求項２５に記載のコンピュータ・プログラム製品。
【請求項２７】
前記データ・オブジェクトの組の間の距離は、差の二乗和の平方根を含むユークリッド距離、前記平方根が取られない前記ユークリッド距離の変形、差の絶対値の和、または１つのチャンクから別のチャンクへのアクセスの合計時間のうちの少なくとも１つに基づいて定められる、請求項１１に記載のコンピュータ・プログラム製品。
【請求項２８】
前記命令はさらに、
前記選択されたクラスタが前記リムーバブル記憶媒体にエクスポートされた後に、前記選択されたクラスタに関連する前記データ・オブジェクトの組を、移動のためのさらなる検討から除去するステップ
を前記プロセッサに行わせる、請求項１８に記載の装置。
【請求項２９】
前記命令はさらに、
前記選択されたクラスタに関連する前記データ・オブジェクトの組を移動のためのさらなる検討から除去した後に、前記リムーバブル記憶システムにおける前記データ・オブジェクトの組の位置に対する参照を前記内部記憶システムに挿入するステップと、
前記選択されたクラスタに関連するすべてのデータを前記内部記憶システムから削除するステップと
を前記プロセッサに行わせる、請求項２８に記載の装置。
【請求項３０】
前記データ・オブジェクトの組の間の距離は、差の二乗和の平方根を含むユークリッド距離、前記平方根が取られない前記ユークリッド距離の変形、差の絶対値の和、または１つのチャンクから別のチャンクへのアクセスの合計時間のうちの少なくとも１つに基づいて定められる、請求項１８に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は一般的に、改善されたデータ処理装置および方法に関し、より特定的には、重複排除（ｄｅ−ｄｕｐｌｉｃａｔｅｄ）データの移動／コピーを最適化するための機構に関する。
【背景技術】
【０００２】
本明細書の発明者らが認識したところでは、記憶環境にデータを保存するときに費用効率は重要な局面である。費用効率を達成するためのやり方の１つは、データ重複排除によるものである。データ重複排除とはデータの同一部分を選別して、データの一意のインスタンスのみを記憶サブシステムに保存することである。よって、一意に保存されたインスタンスと同一であるデータの他のインスタンスは、保存されたインスタンスを参照するだけになる。データの一意のインスタンスのみが保存され、他のインスタンスはこの１つのインスタンスを参照するため、重複排除を用いたデータ保存は記憶容量を小さくする。
【０００３】
データ重複排除は、重複排除データ・オブジェクトの組またはチャンクを作成し、チャンクの同一性を比較し、同一のチャンクを１度だけ保存することによって記憶容量を小さくし得るが、その後バックアップもしくは回復またはその両方の目的のために重複排除データ・オブジェクト（すなわちチャンク）をリムーバブル記憶媒体に移動させることは、現在のところ常駐記憶サブシステムにおいて用いられる重複排除からの利益を得ていない。すなわち、さまざまな現行の方法は、チャンクからデータ・オブジェクトを再構築し、各データ・オブジェクトを完全なデータ・オブジェクトとして保存することによって、重複排除データをリムーバブル記憶媒体に移動させている。よって、データが元の様式で保存されるため、重複排除データの移動によって重複排除の費用効率が失われる。
【０００４】
他の現行の方法は、リムーバブル記憶媒体にチャンクを直接保存することによって、重複排除データをリムーバブル記憶媒体に移動させている。しかしながら、チャンクを移動させることによって、実際のチャンクが１つのリムーバブル記憶媒体にあるのに対し、そのチャンクに対する参照が別のリムーバブル記憶媒体に存在するということが起こり得る。したがって、データ・オブジェクトの復元動作は極度に時間のかかるものとなる。なぜなら、多数のリムーバブル記憶媒体を装着して読取る必要が生じるおそれがあるために、復元のために受容できないほどの時間がかかり得るからである。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
よって例示的実施形態は、すべてのチャンクまたはチャンクに対する参照を有するデータ・オブジェクトのエンティティを同じリムーバブル媒体上に保ちながら、リムーバブル記憶システムに重複排除データを移動／コピーするための機構を提供する。
【課題を解決するための手段】
【０００６】
例示的実施形態の１つにおいては、データ処理システムにおいて、内部記憶システムからリムーバブル記憶システムへの重複排除データの移動／コピーを最適化するための方法が提供される。この例示的実施形態は、データ・オブジェクトの組の数に基づいて、内部記憶システムに保存されるデータ・オブジェクトの組に対して生成されるべきクラスタの予備数を定める。この例示的実施形態は、データ・オブジェクトの組間の最短距離に基づいて、予備数のクラスタを生成する。この例示的実施形態において、各クラスタはデータ・オブジェクトの１つまたはそれ以上の組を含み、データ・オブジェクトの各組はデータの１つまたはそれ以上のチャンクを含む。この例示的実施形態は、できる限り少ないデータ・オブジェクトの組の中に最大数の共通チャンクを有するクラスタを識別することによって、クラスタの組の中から選択されたクラスタを識別する。この例示的実施形態は、選択されたクラスタのエクスポート・サイズが、リムーバブル記憶システムの利用可能な記憶容量を超えているかどうかを判定する。この例示的実施形態は、選択されたクラスタのエクスポート・サイズがリムーバブル記憶システムの利用可能な記憶容量を超えていないことに応答して、選択されたクラスタをリムーバブル記憶システムにエクスポートする。
【０００７】
他の例示的実施形態においては、コンピュータ読取り可能プログラムを有するコンピュータ使用可能または読取り可能媒体を含むコンピュータ・プログラム製品が提供される。このコンピュータ読取り可能プログラムは、コンピュータ・デバイス上で実行されるときに、方法の例示的実施形態に関して上記に概説されたさまざまな動作の１つおよびその組み合わせをそのコンピュータ・デバイスに行わせる。
【０００８】
さらに別の例示的実施形態においては、システム／装置が提供される。このシステム／装置は、１つまたはそれ以上のプロセッサと、その１つまたはそれ以上のプロセッサに結合されたメモリとを含んでもよい。このメモリは、１つまたはそれ以上のプロセッサによって実行されるときに、方法の例示的実施形態に関して上記に概説されたさまざまな動作の１つおよびその組み合わせをその１つまたはそれ以上のプロセッサに行わせる命令を含んでもよい。
【０００９】
本発明のこれらおよびその他の特徴および利点は、本発明の例示的実施形態の以下の詳細な説明に記載されるか、またはそれを鑑みて当該技術分野の通常の当業者に明らかになるであろう。
【００１０】
本発明、ならびにその使用の好ましいモードならびにさらなる目的および利点は、添付の図面とともに読まれたときに、例示的実施形態の以下の詳細な説明を参照することによって最もよく理解されるであろう。
【図面の簡単な説明】
【００１１】
【図１】例示的実施形態の局面が実現され得るデータ処理システムの例を示すブロック図である。
【図２】例示的実施形態に従ってリムーバブル記憶システムに重複排除データを移動／コピーするための機構を示す機能ブロック図である。
【図３】例示的実施形態に従って内部記憶システムからリムーバブル記憶システムへの重複排除データの移動／コピーを最適化するステップにおいて、重複排除移動／コピー論理によって行われる動作を示す流れ図である。
【図４】例示的実施形態に従って内部記憶システムからリムーバブル記憶システムへの重複排除データの移動／コピーを最適化するステップにおいて、重複排除移動／コピー論理によって行われる動作を示す流れ図である。
【図５】例示的実施形態に従って内部記憶システムからリムーバブル記憶システムへの重複排除データの移動／コピーを最適化するステップにおいて、重複排除移動／コピー論理によって行われる動作を示す流れ図である。
【図６】例示的実施形態に従って内部記憶システムからリムーバブル記憶システムへの重複排除データの移動／コピーを最適化するステップにおいて、重複排除移動／コピー論理によって行われる動作を示す流れ図である。
【図７】例示的実施形態に従って内部記憶システムからリムーバブル記憶システムへの重複排除データの移動／コピーを編成するステップにおいて、重複排除移動／コピー論理によって行われる動作を示す流れ図である。
【発明を実施するための形態】
【００１２】
例示的実施形態は、すべてのチャンクまたはチャンクに対する参照を有するデータ・オブジェクトのエンティティを同じリムーバブル媒体上に保ちながら、リムーバブル記憶システムに重複排除データを移動／コピーするための機構を提供する。重複排除エンジンは、１つのリムーバブル記憶システムに適切に保存され得るデータ・オブジェクトの組に関係する一意のチャンクの組を選択する重複排除プロセスを行う。すなわち、例示的実施形態の機構は、データ・オブジェクトに関連するチャンクを追跡する重複排除テーブルから、リムーバブル記憶システムに移動／コピーされるべきすべてのデータ・オブジェクトに対する一意のチャンクを識別する。リムーバブル記憶システムに適切に保存され得る類似チャンク・クラスタの組が識別されるとき、そのクラスタの組がリムーバブル記憶システムに移動／コピーされる。
【００１３】
よって、この例示的実施形態は多くの異なるタイプのデータ処理環境において用いられてもよい。例示的実施形態の特定の構成要素および機能の説明に対する状況を提供するために、例示的実施形態の局面が実現され得る環境の例として以下に図１が提供される。図１は単なる例であって、本発明の局面または実施形態が実現され得る環境に関する何らかの制限を主張または暗示することは意図されていないことが認識されるべきである。本発明の趣旨および範囲から逸脱することなく、図示される環境に多くの修正が加えられてもよい。
【００１４】
図１は、例示的実施形態の局面が実現され得るデータ処理システムの例のブロック図である。データ処理システム１００は、本発明の例示的実施形態に対するプロセスを実現するコンピュータ使用可能コードまたは命令が中に位置していてもよいコンピュータの例である。
【００１５】
図示される例において、データ処理システム１００は、ノース・ブリッジおよびメモリ・コントローラ・ハブ（ｎｏｒｔｈ  ｂｒｉｄｇｅ  ａｎｄ  ｍｅｍｏｒｙ  ｃｏｎｔｒｏｌｌｅｒ  ｈｕｂ：ＮＢ／ＭＣＨ）１０２と、サウス・ブリッジおよび入出力（ｉｎｐｕｔ／ｏｕｔｐｕｔ：Ｉ／Ｏ）コントローラ・ハブ（ｓｏｕｔｈ  ｂｒｉｄｇｅ  ａｎｄ  ｉｎｐｕｔ／ｏｕｔｐｕｔ（Ｉ／Ｏ）ｃｏｎｔｒｏｌｌｅｒ  ｈｕｂ：ＳＢ／ＩＣＨ）１０４とを含むハブ・アーキテクチャを用いる。処理ユニット１０６、メイン・メモリ１０８およびグラフィックス・プロセッサ１１０はＮＢ／ＭＣＨ１０２に接続される。グラフィックス・プロセッサ１１０は、アクセラレイティッド・グラフィックス・ポート（ａｃｃｅｌｅｒａｔｅｄ  ｇｒａｐｈｉｃｓ  ｐｏｒｔ：ＡＧＰ）を通じてＮＢ／ＭＣＨ１０２に接続されてもよい。
【００１６】
図示される例においては、ローカル・エリア・ネットワーク（ｌｏｃａｌ  ａｒｅａ  ｎｅｔｗｏｒｋ：ＬＡＮ）アダプタ１１２がＳＢ／ＩＣＨ１０４に接続している。音声アダプタ１１６、キーボードおよびマウス・アダプタ１２０、モデム１２２、リード・オンリ・メモリ（ｒｅａｄ  ｏｎｌｙ  ｍｅｍｏｒｙ：ＲＯＭ）１２４、ハード・ディスク・ドライブ（ｈａｒｄ  ｄｉｓｋ  ｄｒｉｖｅ：ＨＤＤ）１２６、ＣＤ−ＲＯＭドライブ１３０、ユニバーサル・シリアル・バス（ｕｎｉｖｅｒｓａｌ  ｓｅｒｉａｌ  ｂｕｓ：ＵＳＢ）ポートおよびその他の通信ポート１３２、ならびにＰＣＩ／ＰＣＩｅデバイス１３４は、バス１３８およびバス１４０を通じてＳＢ／ＩＣＨ１０４に接続している。ＰＣＩ／ＰＣＩｅデバイスは、たとえばイーサネット（Ｒ）アダプタ、アドイン・カード、およびノート型コンピュータに対するＰＣカードなどを含んでもよい。ＰＣＩはカード・バス・コントローラを用いるのに対し、ＰＣＩｅは用いない。ＲＯＭ１２４は、たとえばフラッシュ基本入出力システム（ｂａｓｉｃ  ｉｎｐｕｔ／ｏｕｔｐｕｔ  ｓｙｓｔｅｍ：ＢＩＯＳ）などであってもよい。
【００１７】
ＨＤＤ１２６およびＣＤ−ＲＯＭドライブ１３０は、バス１４０を通じてＳＢ／ＩＣＨ１０４に接続している。ＨＤＤ１２６およびＣＤ−ＲＯＭドライブ１３０は、たとえばインテグレーテッド・ドライブ・エレクトロニクス（ｉｎｔｅｇｒａｔｅｄ  ｄｒｉｖｅ  ｅｌｅｃｔｒｏｎｉｃｓ：ＩＤＥ）またはシリアル・アドバンスド・テクノロジ・アタッチメント（ｓｅｒｉａｌ  ａｄｖａｎｃｅｄ  ｔｅｃｈｎｏｌｏｇｙ  ａｔｔａｃｈｍｅｎｔ：ＳＡＴＡ）インタフェースなどを用いてもよい。スーパＩ／Ｏ（Ｓｕｐｅｒ  Ｉ／Ｏ：ＳＩＯ）デバイス１３６がＳＢ／ＩＣＨ１０４に接続されてもよい。一実施形態において、ＨＤＤ１２６はソリッド・ステート・ドライブ（ｓｏｌｉｄ  ｓｔａｔｅ  ｄｒｉｖｅ：ＳＤＤ）である。さらに別の実施形態において、ディスク・ドライブ１３０はデジタル多用途ディスク（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｋ：ＤＶＤ）ドライブまたはＢｌｕ−Ｒａｙ  Ｄｉｓｃ（ＢＤ）（Ｒ）ドライブである。
【００１８】
処理ユニット１０６においてオペレーティング・システムが実行される。オペレーティング・システムは、図１におけるデータ処理システム１００内のさまざまな構成要素を協調させ、かつそれらの制御を提供する。クライアントとして、オペレーティング・システムは、たとえばＭｉｃｒｏｓｏｆｔ（Ｒ）Ｗｉｎｄｏｗｓ（Ｒ）７（ＭｉｃｒｏｓｏｆｔおよびＷｉｎｄｏｗｓは、米国、その他の国、またはその両方におけるＭｉｃｒｏｓｏｆｔ社の登録商標である）などの商業的に入手可能なオペレーティング・システムであってもよい。たとえばＪａｖａ（Ｒ）プログラミング・システムなどのオブジェクト指向プログラミング・システムがオペレーティング・システムとともに実行されてもよく、Ｊａｖａ（Ｒ）プログラムまたはデータ処理システム１００において実行中のアプリケーションからオペレーティング・システムへの呼出しを提供してもよい（Ｊａｖａは、オラクルもしくはその関連会社またはその両方の登録商標である）。
【００１９】
サーバとして、データ処理システム１００は、たとえばアドバンスト・インタラクティブ・エグゼクティブ（Ａｄｖａｎｃｅｄ  Ｉｎｔｅｒａｃｔｉｖｅ  Ｅｘｅｃｕｔｉｖｅ：ＡＩＸ（ＩＢＭ社の登録商標））オペレーティング・システムまたはＬＩＮＵＸ（Ｒ）オペレーティング・システムを実行するＩＢＭ（ＩＢＭ社の登録商標）ｅＳｅｒｖｅｒ（ＩＢＭ社の登録商標）Ｓｙｓｔｅｍ  ｐ（ＩＢＭ社の登録商標）コンピュータ・システムなどであってもよい（ＩＢＭ、ｅＳｅｒｖｅｒ、Ｓｙｓｔｅｍ  ｐおよびＡＩＸは、米国、その他の国、またはその両方におけるインターナショナル・ビジネス・マシーンズ社（Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｂｕｓｉｎｅｓｓ  Ｍａｃｈｉｎｅｓ  Ｃｏｒｐｏｒａｔｉｏｎ）の登録商標であり、ＬＩＮＵＸは、米国、その他の国、またはその両方におけるＬｉｎｕｓ  Ｔｏｒｖａｌｄｓの登録商標である）。ＬＩＮＵＸ（Ｒ）オペレーティング・システムの種類は、Ｒｅｄ  Ｈａｔ  Ｅｎｔｅｒｐｒｉｓｅ  Ｌｉｎｕｘ（Ｒ）（ＲＨＥＬ）およびＤｅｂｉａｎ  Ｌｉｎｕｘ（Ｒ）を含むがそれに限定されない。データ処理システム１００は、処理ユニット１０６内に複数のプロセッサを含む対称型マルチプロセッサ（ｓｙｍｍｅｔｒｉｃ  ｍｕｌｔｉｐｒｏｃｅｓｓｏｒ：ＳＭＰ）システムであってもよい。代替的に、単一プロセッサ・システムが用いられてもよい。
【００２０】
オペレーティング・システム、オブジェクト指向プログラミング・システム、およびアプリケーションまたはプログラムに対する命令は、たとえばＨＤＤ１２６などの記憶装置に位置しており、処理ユニット１０６によって実行のためにメイン・メモリ１０８にロードされてもよい。本発明の例示的実施形態のためのプロセスは、コンピュータ使用可能プログラム・コードを用いて処理ユニット１０６によって行われてもよく、そのコンピュータ使用可能プログラム・コードは、たとえばメイン・メモリ１０８、ＲＯＭ１２４などのメモリに位置していてもよいし、たとえば１つまたはそれ以上の周辺デバイス１２６および１３０などに位置していてもよい。
【００２１】
たとえば図１に示されるバス１３８またはバス１４０などのバス・システムは、１つまたはそれ以上のバスで構成されてもよい。むろんバス・システムは、その機構またはアーキテクチャに取付けられた異なる構成要素またはデバイス間のデータ移送を提供するようなあらゆるタイプの通信機構またはアーキテクチャを用いて実現されてもよい。たとえば図１のモデム１２２またはネットワーク・アダプタ１１２などの通信ユニットは、データを送信および受信するために用いられる１つまたはそれ以上のデバイスを含んでもよい。メモリは、たとえばメイン・メモリ１０８、ＲＯＭ１２４、または図１のＮＢ／ＭＣＨ１０２にみられるものなどのキャッシュなどであってもよい。
【００２２】
図１のハードウェアは、実施によって変化し得ることを通常の当業者は認識するだろう。図１に示されるハードウェアに加えて、またはそれに代えて、たとえばフラッシュ・メモリ、等価の不揮発性メモリ、または光学ディスク・ドライブ（コンパクト・ディスク、デジタル多用途ディスクおよびＢｌｕ−Ｒａｙ  Ｄｉｓｃ（Ｒ）ディスクを含む）など、その他の内部ハードウェアまたは周辺デバイスが用いられてもよい。加えて、本発明の趣旨および範囲から逸脱することなく、例示的実施形態のプロセスが前述したＳＭＰシステム以外のマルチプロセッサ・データ処理システムに適用されてもよい。
【００２３】
さらに、データ処理システム１００は、クライアント・コンピュータ・デバイス、サーバ・コンピュータ・デバイス、タブレット・コンピュータ、ラップトップ・コンピュータ、電話またはその他の通信デバイス、パーソナル・デジタル・アシスタント（ｐｅｒｓｏｎａｌ  ｄｉｇｉｔａｌ  ａｓｓｉｓｔａｎｔ：ＰＤＡ）などを含むいくつかの異なるデータ処理システムのいずれかの形を取ってもよい。いくつかの例示的な例において、データ処理システム１００は、たとえばオペレーティング・システム・ファイルもしくはユーザ生成データまたはその両方を保存するための不揮発性メモリを提供するためのフラッシュ・メモリとともに構成されたポータブル・コンピュータ・デバイスなどであってもよい。本質的に、データ処理システム１００はアーキテクチャの制限なく、あらゆる公知のデータ処理システムまたは後に開発されるデータ処理システムであってもよい。
【００２４】
再び、例示的実施形態の機構は、データ・オブジェクトのエンティティを同じリムーバブル記憶システム上に一緒に保ちながら、たとえば図１のハード・ディスク・ドライブ（ＨＤＤ）１２６などの非リムーバブル記憶システムに保存された重複排除データを、たとえば図１のＣＤ−ＲＯＭ１３０、またはリニア・テープ・ファイル・システム（Ｌｉｎｅａｒ  Ｔａｐｅ  Ｆｉｌｅ  Ｓｙｓｔｅｍ：ＬＴＦＳ）などのリムーバブル記憶システムに移動／コピーすることを提供する。この機構は、データ・オブジェクトに関連するチャンクを追跡する重複排除テーブルから、リムーバブル記憶システムに移動／コピーされるべきデータ・オブジェクトの組からの一意のチャンクを識別する。この機構は、第１の記憶媒体に保存される各々の一意のチャンクに対する参照の数をリストにしたチャンク参照テーブルを得る。この機構は、２未満の参照を有するチャンクを削除することによってチャンク参照テーブルを低減し、残りのチャンクに対して、チャンクをデータ・オブジェクトに対してマップしたチャンク・マトリックス［Ｃ］を作成する。この機構は、チャンク・マトリックス［Ｃ］に基づいてｎ次元範囲で表される各データ・オブジェクトに対するベクトルを作成し、たとえばベクトル間のユークリッド距離などの「メトリック（ｍｅｔｒｉｃ）」を算出し、そのユークリッド距離をメトリック・マトリックス［Ｍ］に挿入する。ユークリッド距離は２点間の距離である。この機構はメトリック・マトリックス［Ｍ］から、最も多くの共通チャンクを有することによって最短距離を有するデータ・オブジェクトのクラスタを識別する。同じ距離を有する複数のクラスタが見出されたときは、この機構は好ましいクラスタをランダムに定める。この好ましいクラスタの決定に基づき、この機構はクラスタに必要とされる記憶空間（エクスポート・サイズ）を定め、その必要とされる記憶サイズとリムーバブル記憶システムの容量とを比較する。もしエクスポート・サイズがリムーバブル記憶システムの容量よりも大きければ、この機構はそのクラスタを禁止とマーク付けし、次に好ましいクラスタを定める。もしエクスポート・サイズがリムーバブル記憶システムの容量から任意の予め定義された安全マージンを引いたものよりも小さければ、この機構は新たなクラスタ点を算出し、次いでその新たなクラスタ点と他のデータ・オブジェクトとの間のユークリッド距離を算出する。その際に、エクスポートが所望のサイズに達するまで、クラスタにさらなるデータ・オブジェクトが加えられる。もしエクスポート・サイズがリムーバブル記憶システムの容量よりも小さく、かつリムーバブル記憶システムの容量から任意の予め定義された安全マージンを引いたものよりも大きければ、この機構は次いで移動／コピー・プロセスを呼び出す。
【００２５】
図２は、例示的実施形態に従ってリムーバブル記憶システムに重複排除データを移動／コピーするための機構を示す機能ブロック図である。データ処理システム２００は、重複排除論理２０２および重複排除移動／コピー論理２０４を含む。重複排除論理２０２はデータ２０６を受け取り、データ２０６の一意部分を選別し、リムーバブル記憶システムではない内部記憶システム２０８にデータの一意のインスタンスのみを保存する。データ２０６は、たとえばデータ・ストリーム、データ・ファイル、または仮想テープなど、データ重複排除の対象であるデータ・オブジェクトであってもよい。この例示的実施形態では、重複排除されるデータ・オブジェクトを示すために仮想テープ（Ｖｉｒｔｕａｌ−ｔａｐｅ：Ｖｔａｐｅ）という例示的用語を用いる。データ処理システム２００において、重複排除論理２０２は以下に示されるとおりの重複排除テーブルを維持する。
【００２６】
【表１】
2015505997.tif 000003
【００２７】
Ｖｔａｐｅによって表されるデータ・オブジェクトを保存するために、重複排除論理２０２はＶｔａｐｅをチャンクに分けて、重複排除テーブルの「Ｖｔａｐｅ−チャンク−ＩＤ」列における各チャンクを追跡する。重複排除論理２０２はチャンクを類似の長さに保つことが好ましいが、重複排除論理２０２は可変長のチャンクを保存してもよい。重複排除論理２０２は各チャンクの識別特徴を算出し、それはたとえばハッシュ「メッセージ・ダイジェスト」または単に「ダイジェスト」などであってもよく、これはたとえばメッセージ・ダイジェスト５（Ｍｅｓｓａｇｅ  Ｄｉｇｅｓｔ  ５：ＭＤ−５）またはセキュア・ハッシュ・アルゴリズム（Ｓｅｃｕｒｅ  Ｈａｓｈ  Ａｌｇｏｒｉｔｈｍ）（ＳＨＡ−１、ＳＨＡ−２５６、ＳＨＡ−５１２）などの暗号ハッシュ関数の英数字出力である。このダイジェストは所与のハッシュ関数に対する固定長のものであり、どのハッシュ関数が用いられているかによって長さが変わる。たとえば、ＭＤ−５に対するダイジェストは１６０ビットの長さであり、ＳＨＡ−１に対するダイジェストは１２８ビットの長さである。ハッシュ関数に対する入力は、重複排除されるべきチャンクである。暗号ハッシュ関数は典型的に重複排除に用いられるが、これは暗号ハッシュ関数が「アバランシェ」機能であるためであり、これはデータの２つのチャンクの間にただ１ビットの相違があることによって、それぞれのダイジェストに顕著な変化がもたらされることを意味する。重複排除論理２０２は、重複排除テーブルの「チャンク・ハッシュ・ダイジェスト」列に識別特徴を保存する。重複排除テーブルにあらゆるチャンクを保存する前に、重複排除論理２０２は、たとえばさまざまなチャンクに対する暗号ハッシュのダイジェストを比較することなどによって、現行チャンクとまったく等しいデータのチャンクが重複排除テーブル内にすでに存在するかどうかを判定する。もし既存チャンクのダイジェストとまったく等しいダイジェストを有することによって、あるチャンクがすでに存在すれば、重複排除論理２０２はその現行チャンクを保存して貴重な記憶空間を無駄にする代わりに、重複排除テーブルの「記憶位置」列における既存チャンクの記憶位置に対してそのチャンクを参照する。もしチャンクが存在しなければ、重複排除論理２０２はそのチャンクを保存し、重複排除テーブルの「チャンク・ハッシュ・ダイジェスト」列にその新たなチャンクのダイジェストを入れ、「記憶位置」列にその新たなチャンクの記憶位置を入れる。記憶位置は内部記憶システム２０８における１つまたはそれ以上のブロック・アドレスであってもよいし、次の段落で説明されるとおり、ＶｔａｐｅのＩＤとＶｔａｐｅ上のチャンクの番号との組み合わせであってもよい。
【００２８】
したがって、各チャンクは一意のＩＤを有するか、または一意のＩＤをポイントしており、重複排除論理２０２は以下の意味（ｓｅｍａｎｔｉｃ）を用いてチャンク情報を保存する。すなわちＸｚｚ（Ｙ）、ここで接頭辞「Ｘ」はＶｔａｐｅのＩＤであり、「ｚｚ」はその特定のＶｔａｐｅにおけるチャンクの番号である。Ｙ接尾辞が存在するとき、そのＹの存在はこれが所与のチャンクに対するポインタであることを示す。したがって重複排除テーブルを参照すると、重複排除論理はＶｔａｐｅ１を４つのチャンクに分離しており（「Ｖｔａｐｅ−チャンク−ＩＤ」列、２〜５行）、さらに重複排除論理はＶｔａｐｅ２を３つのチャンクに分離している（「Ｖｔａｐｅ−チャンク−ＩＤ」列、６〜８行）。Ｖｔａｐｅ２のチャンク１（「Ｖｔａｐｅ−チャンク−ＩＤ」列、６行）はＶｔａｐｅ１のチャンク１（「Ｖｔａｐｅ−チャンク−ＩＤ」列、２行）と同じハッシュ・ダイジェストを有するため、重複排除論理はＶｔａｐｅ２のチャンク１を同じ位置に保存する。よって、Ｖｔａｐｅ２のチャンク１のＩＤはＶｔａｐｅ１のチャンク１をポイントするように変更される。
【００２９】
重複排除移動／コピー論理２０４は、データ処理システム２００のユーザに対して、データ・オブジェクト・チャンクおよびそのそれぞれのデータ・オブジェクト・チャンク参照をともに保ちながら、内部記憶システム２０８に保存されている重複排除データをリムーバブル記憶システム２１０に移動／コピーするための機構を提供する。移動／コピーを行うために、重複排除移動／コピー論理２０４は多数の変数を用いて、固定された容量のリムーバブル記憶システム２１０に保存されるべきデータ・オブジェクトの最適な組み合わせを算出し、それらの変数は以下のとおりである。
【００３０】
［チャンク−サイズ］：１つのデータ・チャンクのサイズ、たとえば１ＭＢなど。
［ｒｓｍ−サイズ］：リムーバブル記憶システムのサイズ、たとえば４０ＭＢなど。
［自身のＶｔａｐｅのチャンクに対するポインタ］：それぞれのＶｔａｐｅにおけるチャンクに対するポインタ。
［別のＶｔａｐｅのチャンクに対するポインタ］：別のＶｔａｐｅのチャンクに対するポインタ。
［固有−Ｖｔａｐｅ−サイズ］：重複排除データを有さないＶｔａｐｅの元のサイズ。
［重複排除（ｄｅｄｕｐ）−Ｖｔａｐｅ−サイズ］：各チャンクのただ１つのコピーおよびチャンクに対するポインタを含むＶｔａｐｅのサイズ。実際上は、重複排除された固有Ｖｔａｐｅ（＝［固有−Ｖｔａｐｅ−サイズ］−［自身のＶｔａｐｅのチャンクに対するポインタ］）。
［複数参照−チャンク］：以下に太字で示された、他のテープにも参照されるチャンクの数。
［重複排除−クラスタ−サイズ］：各チャンクのただ１つのコピーおよびチャンクに対するポインタを含むＶｔａｐｅの集合したクラスタのサイズ。実際上は、移動／コピーされる必要のあるすべてのデータの合計。
【００３１】
上記の重複排除はＶｔａｐｅ１およびＶｔａｐｅ２からのチャンクの保存を示しているが、内部記憶システム２０８には多くの仮想テープ（Ｖｔａｐｅ）が保存されてもよいこと、および各Ｖｔａｐｅは上に示される重複排除テーブルに例示されるものとは異なる数のチャンクを含んでもよいことを通常の当業者は認識するだろう。一例として、重複排除論理２０２によって処理されたそれぞれのチャンクを有する６つのＶｔａｐｅの表現を以下に示す。
【００３２】
【表２】
2015505997.tif 000004
【００３３】
これらの例において、Ｖｔａｐｅ１はＩＤ  Ａ０１〜Ａ１５を有する１５個の一意のチャンクを含む。例示されるとおり、チャンクＡ０１、Ａ０４およびＡ０５はＶｔａｐｅ２、Ｖｔａｐｅ３、Ｖｔａｐｅ４、およびＶｔａｐｅ５にも参照されている。Ｖｔａｐｅ２は２７個のチャンクを含み、そのうち１１個が一意のチャンクである。Ｖｔａｐｅ２は他のＶｔａｐｅにも参照されるチャンクを３つ含んでおり、それらはＢ０２、Ｂ０３およびＢ０６である。加えてＶｔａｐｅ２は、別のＶｔａｐｅすなわちＶｔａｐｅ１のチャンクに対する、チャンクをポイントするポインタを２つ含む（Ａ０１ｐおよびＡ０５ｐ）。
【００３４】
このＶｔａｐｅの表現から、重複排除移動／コピー論理２０４は、各Ｖｔａｐｅがどれだけの固有容量を有するか、重複排除後に各Ｖｔａｐｅがどれだけの容量を有するか、および複数参照チャンクの数を示す別の表現を得てもよく、それは以下の、内部記憶システムに保存される仮想テープ・テーブルによって示される。
【００３５】
【表３】
2015505997.tif 000005
【００３６】
例示されるとおり、重複排除論理２０２は内部記憶システム２０８に６つのＶｔａｐｅを保存している。Ｖｔａｐｅ１は１５ＭＢの固有サイズを有し、これはこのテープのデータが重複排除されていない（同一チャンクがない）ことを示す。Ｖｔａｐｅ２の重複排除サイズは１３ＭＢであり、これはＶｔａｐｅ２が一意チャンクを１３個しか有さず、チャンクに対するポインタを１４個有するためである。加えて、Ｖｔａｐｅ１は他のテープに参照されるチャンクを３つ有する。
【００３７】
重複排除移動／コピー論理２０４が内部記憶システム２０８からリムーバブル記憶システム２１０への重複排除データの移動／コピーを行うために、重複排除移動／コピー論理２０４は、上記の内部記憶システムに保存される仮想テープ・テーブルおよびＶｔａｐｅの表現に集約されるすべての複数参照チャンクを含むチャンク参照テーブルを生成する。
【００３８】
【表４】
2015505997.tif 000006
【００３９】
チャンク参照テーブルによると、チャンクＡ０１は他のテープに３回参照され、チャンクＡ０４は１回参照され、チャンクＡ０５は５回参照され、チャンクＢ０２は２回参照され、チャンクＢ０３は３回参照され、チャンクＢ０６は２回参照される。
【００４０】
チャンク参照テーブルを用いて、重複排除移動／コピー論理２０４は、各Ｖｔａｐｅに対してどのチャンクが参照されるかを示すチャンク・マトリックス・テーブルを生成する。１という値はそのチャンクがＶｔａｐｅによって少なくとも１回参照されるかどうかを示し、０という値はＶｔａｐｅがその特定のチャンクを参照しないかどうかを示す。
【００４１】
【表５】
2015505997.tif 000007
【００４２】
チャンク・マトリックス・テーブルを用いて、重複排除移動／コピー論理２０４は、以下に示されるとおり、各Ｖｔａｐｅに対するチャンク・マトリックス・テーブル内の点のｎ次元表現を生成する。
【００４３】
Ｖｔａｐｅ１＝（１／１／１／０／０／０）
Ｖｔａｐｅ２＝（１／０／１／１／１／１）
Ｖｔａｐｅ３＝（０／０／１／０／１／１）
Ｖｔａｐｅ４＝（１／０／１／０／１／１）
Ｖｔａｐｅ５＝（１／１／１／１／１／０）
Ｖｔａｐｅ６＝（０／０／０／１／０／０）
【００４４】
ｎ次元空間における点としてのＶｔａｐｅの表現によって、重複排除移動／コピー論理２０４は前述のメトリックを算出する。一実施形態において、重複排除移動／コピー論理２０４は、以下に示される距離の差の二乗和の平方根アルゴリズムを用いて各２つのＶｔａｐｅすなわちｘおよびｙの間のユークリッド距離を算出することによって、メトリックを算出してもよい。
【００４５】
【数１】
2015505997.tif 000008
【００４６】
ここでは２つの点ｘ（ｘ１，．．．，ｘｎ）およびｙ（ｙ１，．．．，ｙｎ）に対してユークリッド距離が算出される。トポロジの言語において、ユークリッド距離はルベーグ空間Ｌ２メトリックである。別の実施形態においては、上記のそれぞれの距離の差の二乗和アルゴリズムにおいて平方根が取られないことによって、さらに離れたクラスタにより多くの重みを与える非ユークリッド・メトリックを提供する。さらに別の代替的実施形態において、そのメトリックは、ルベーグ空間Ｌ１メトリックとして、すなわちそれぞれの距離の差の絶対値の和として算出された非ユークリッド距離である。
【００４７】
【数２】
2015505997.tif 000009
【００４８】
さらに別の実施形態においては、「距離」の代わりに「合計時間」がメトリックとして用いられる。この合計時間は、たとえば、（ａ）ロボット・ピッカーがリムーバブル媒体を含む記憶装置スロットに移動するための時間、（ｂ）リムーバブル媒体をその記憶装置スロットから掴み出すための時間、（ｃ）ロボット・ピッカーが媒体ドライブに移動するための時間、（ｄ）リムーバブル媒体を媒体ドライブにロードするための時間、および（ｅ）１つまたはそれ以上の所望のチャンクをシークするための時間に対する個々の時間の合計などである。これら４つのアルゴリズムは異なるが、これらはすべてトポロジ的にメトリックを定めるものである。
【００４９】
以下のとおり、重複排除移動／コピー論理２０４は、結果として得られる例示的なユークリッド距離値をメトリック・マトリックス［Ｍ］に挿入する。
【００５０】
【表６】
2015505997.tif 000010
【００５１】
次いで重複排除移動／コピー論理２０４は、Ｖｔａｐｅの数の平方根（√Ｖｔａｐｅ＿ｃｏｕｎｔ）を取ることによって、生成されるべきクラスタの予備数を定める。たとえば、
√６＝２．４４９≒２などである。
したがって重複排除移動／コピー論理２０４は、移動／コピー・プロセスが最初に２つの予備クラスタで始まるべきであることを定める。
【００５２】
重複排除移動／コピー論理２０４は、メトリック・マトリックス［Ｍ］からＶｔａｐｅ間の２つの最短距離を検索し、２つのクラスタを生成する。この場合の２つのクラスタは次のとおりになる。
クラスタ２４（Ｖｔａｐｅ２＆Ｖｔａｐｅ４）＝１，０００
クラスタ３４（Ｖｔａｐｅ３＆Ｖｔａｐｅ４）＝１，０００
ここに示されるとおり、同じＶｔａｐｅを含む２つのクラスタが存在する場合がある。こうした場合には、重複排除移動／コピー論理２０４は両方のクラスタを分析するが、後のステップにおいて、共通のＶｔａｐｅはより効率的なクラスタにのみ排他的に加えられる。
【００５３】
定められたクラスタに従って、重複排除移動／コピー論理２０４は以下のとおりに、先行するクラスタ−チャンク参照部分によってチャンク−マトリックス・テーブルを増加させる。
【００５４】
【表７】
2015505997.tif 000011
【００５５】
重複排除移動／コピー論理２０４は、どのクラスタができる限り少ないＶｔａｐｅ内に最も多くの共通チャンクを有するかを判定することによって、最良のクラスタを選択する。
クラスタ２４：２つのＶｔａｐｅを用いて５つの共通チャンク→５／２＝２．５
クラスタ３４：２つのＶｔａｐｅを用いて４つの共通チャンク→４／２＝２．０
重複排除移動／コピー論理２０４は、クラスタ２４がクラスタ３４よりも良い因子を有すると判定する。２つのクラスタの因子が同じであると重複排除移動／コピー論理２０４が判定するときには、重複排除移動／コピー論理２０４はクラスタの一方をランダムに選択する。
【００５６】
最良クラスタが選択されると、重複排除移動／コピー論理２０４は、選択されたクラスタの［エクスポート−サイズ］とリムーバブル記憶システムの利用可能な容量［ｒｓｍ−サイズ］とに基づいて、選択されたクラスタがリムーバブル記憶システム２１０に保存され得るかどうかを判定する。選択されたクラスタの［エクスポート−サイズ］を定めるために、重複排除移動／コピー論理２０４は次の式を用いる。
（（クラスタの各Ｖｔａｐｅに対して：（［重複排除−Ｖｔａｐｅ−サイズ］−クラスタ内の他のテープへの参照［ＶｔａｐｅＸをポイントする複数参照−チャンク］−そのクラスタの部分でないＶｔａｐｅへの共通参照））−そのクラスタの部分でないＶｔａｐｅへの共通参照）。
クラスタ２４に対して、
Ｖｔａｐｅ２：［重複排除−Ｖｔａｐｅ−サイズ］−［Ｖｔａｐｅ４をポイントする複数参照−チャンク］−［他のＶｔａｐｅへの共通参照］、これは次のとおりになる。
Ｖｔａｐｅ２：１３−０−２（Ａ０１ｐ，Ａ０５ｐ）＝１１チャンク
Ｖｔａｐｅ４：［重複排除−Ｖｔａｐｅ−サイズ］−［Ｖｔａｐｅ２をポイントする複数参照−チャンク］−［他のＶｔａｐｅへの共通参照］
Ｖｔａｐｅ４：１２−２（Ｂ０３ｐ，Ｂ０６ｐ）−２（Ａ０１ｐ，Ａ０５ｐ）＝８チャンク
他のチャンクへの共通参照＝２チャンク（Ａ０１ｐ，Ａ０５ｐ）
よって、選択されたクラスタのサイズ［重複排除−クラスタ−サイズ］は、１１＋８＋２＝２１チャンクとなり、これは２１ＭＢの［エクスポート−サイズ］と等価になる。
【００５７】
次いで重複排除移動／コピー論理２０４は、［エクスポート−サイズ］がリムーバブル記憶システムの利用可能な容量［ｒｓｍ−サイズ］よりも大きいかどうかを判定する。［エクスポート−サイズ］が［ｒｓｍ−サイズ］よりも大きいと重複排除移動／コピー論理２０４が判定するとき、重複排除移動／コピー論理２０４はそのクラスタ配置を禁止クラスタのリストに加える。例示されていないが、もし選択されたクラスタが３つ以上のＶｔａｐｅを含んでいれば、重複排除移動／コピー論理２０４は最後に加えられたクラスタ構成要素をクラスタから除去して、修正されたクラスタの新しい［エクスポート−サイズ］がリムーバブル記憶システムの利用可能な容量［ｒｓｍ−サイズ］よりも大きいかどうかを判定する。クラスタの［エクスポート−サイズ］がリムーバブル記憶システム２１０に適切に保存されるために十分なサイズだけ低減されないときは、重複排除移動／コピー論理２０４はその低減されたクラスタを禁止クラスタのリストに加え、ただ２つのＶｔａｐｅが残るまで、再び最後に加えられたクラスタ構成要素をクラスタから除去する。Ｖｔａｐｅが２つしか残っておらず、よってＶｔａｐｅを１つ除去することによってクラスタがなくなるとき、重複排除移動／コピー論理２０４はその低減されたクラスタ配置を禁止クラスタのリストに加え、新たな最良クラスタを選択する。
【００５８】
クラスタの［エクスポート−サイズ］がリムーバブル記憶システムの利用可能な容量［ｒｓｍ−サイズ］よりも小さいと重複排除移動／コピー論理２０４が判定するとき、次いで重複排除移動／コピー論理２０４は、［エクスポート−サイズ］がリムーバブル記憶システムの容量から任意の予め定義された安全マージンを引いたもの［ｒｓｍ−閾値］を超えているかどうかを判定する。任意の予め定義された安全マージンの閾値は［ｒｓｍ−サイズ］の８５％であってもよく、よってたとえば０．８５＊４０ＭＢ＝３４ＭＢなどであってもよい。もし［エクスポート−サイズ］が［ｒｓｍ−閾値］よりも大きければ、重複排除移動／コピー論理２０４は選択されたクラスタ配置におけるクラスタの部分ではない参照を修正して、それらのクラスタを参照しないようにする。次いで重複排除移動／コピー論理２０４はそのクラスタをリムーバブル記憶システム２１０にエクスポートする。Ｖｔａｐｅクラスタがエクスポートされた後、重複排除移動／コピー論理２０４は、そのクラスタのＶｔａｐｅに関連するすべてのエントリを、Ｖｔａｐｅ−Ｖｔａｐｅ−マトリックスおよびその他すべてのクラスタから削除する。
【００５９】
付加的に、重複排除移動／コピー論理２０４がそのクラスタのＶｔａｐｅに関連するすべてのエントリを、Ｖｔａｐｅ−Ｖｔａｐｅ−マトリックスおよびその他すべてのクラスタから削除してから、重複排除移動／コピー論理２０４はエクスポートされたクラスタに関連するすべてのデータを内部記憶システム２０８から削除してもよい。つまり、重複排除移動／コピー論理２０４は移動／コピー・プロセスを、たとえばバックアップ、回復、または内部記憶システム２０８における空間管理などの多数の理由から行ってもよい。空間管理に関して、内部記憶システム２０８の空間は典型的に、性能およびコストの両方に関して価値が高い。よって、コストを低減して性能を改善するために、内部記憶システム２０８からリムーバブル記憶システム２１０にデータが移動／コピーされる。重複排除移動／コピー論理２０４がエクスポートされたクラスタに関連するデータを内部記憶システム２０８から削除するとき、重複排除移動／コピー論理２０４はそれぞれのリムーバブル記憶システム２１０に対する削除されたデータの参照を挿入してもよい。その参照は、内部記憶システム２０８からエクスポートされたクラスタをリムーバブル記憶システム２１０に対してマップした参照テーブルであってもよく、それはボリューム識別子、スタブ・ファイルまたはブロック、空ファイルまたはブロックなどを含んでもよく、それはエクスポートされたクラスタに関連するデータがエクスポートされたそれぞれのリムーバブル記憶システム２１０を参照するものである。重複排除移動／コピー論理２０４は、なおも異なるリムーバブル記憶システム２１０に移動／コピーすべき追加のＶｔａｐｅがあるかどうかを判定する。なおも移動／コピーすべき追加のＶｔａｐｅがあるとき、次いで重複排除移動／コピー論理２０４は残りのＶｔａｐｅに対して重複排除移動／コピー・プロセスを再適用する。もし追加のＶｔａｐｅがなければ、次いで重複排除移動／コピー論理２０４は移動／コピー・プロセスを終了する。
【００６０】
もし［エクスポート−サイズ］が［ｒｓｍ−閾値］以下であれば、重複排除移動／コピー論理２０４は、なおも移動／コピーすべき追加のＶｔａｐｅがあるかどうかを判定する。もうＶｔａｐｅが残されていないとき、次いで重複排除移動／コピー論理２０４は、まだ［ｒｓｍ−閾値］に達していないために移動／コピー・プロセスを続けるべきかどうかについてユーザに確認し、そのＶｔａｐｅクラスタをエクスポートすることを無効にしてもよい。もしユーザが移動／コピー・プロセスを進めることを示せば、重複排除移動／コピー論理２０４は選択されたクラスタ配置におけるクラスタの部分ではない参照を修正して、それらのクラスタを参照しないようにする。重複排除移動／コピー論理２０４はクラスタをそのままリムーバブル記憶システム２１０にエクスポートする。Ｖｔａｐｅクラスタがエクスポートされた後、重複排除移動／コピー論理２０４は、そのクラスタのＶｔａｐｅに関連するすべてのエントリを、Ｖｔａｐｅ−Ｖｔａｐｅ−マトリックスおよびその他すべてのクラスタから削除する。ここでも、移動／コピー・プロセスが行われる目的によって、重複排除移動／コピー論理２０４はエクスポートされたクラスタに関連するすべてのデータを内部記憶システム２０８から削除してもよい。重複排除移動／コピー論理２０４は再び、なおも異なるリムーバブル記憶システム２１０に移動／コピーすべき追加のＶｔａｐｅがあるかどうかを判定する。しかしながら、重複排除移動／コピー論理２０４はすでに追加のＶｔａｐｅがないことを判定しているので、重複排除移動／コピー論理２０４は移動／コピー・プロセスを終了する。
【００６１】
もし移動／コピーすべき追加のＶｔａｐｅがあれば、重複排除移動／コピー論理２０４は以下に示されるとおり、増加チャンク・マトリックス・テーブル内の選択された最良クラスタのｎ次元表現を生成する。
クラスタ２４＝（１／０／１／１／１／１）
【００６２】
重複排除移動／コピー論理２０４は、選択された最良クラスタ点に対するすべてのＶｔａｐｅ点のユークリッド距離を算出する。以下のとおり、重複排除移動／コピー論理２０４は、結果として得られる例示的なユークリッド距離値をＶｔａｐｅ−クラスタ・マトリックスに挿入する。
【００６３】
【表８】
2015505997.tif 000012
【００６４】
次いで重複排除移動／コピー論理２０４は、もしそのクラスタ配置が禁止クラスタ・リストになければ、選択された最良クラスタに、選択された最良クラスタ点への最短ユークリッド距離を有するＶｔａｐｅを加える。２つまたはそれ以上のＶｔａｐｅが選択された最良クラスタに対する同じ最短ユークリッド距離を有するとき、重複排除移動／コピー論理２０４は次のとおりにクラスタを生成する。
クラスタ２４＋Ｖｔａｐｅ３＝クラスタ２４３
クラスタ２４＋Ｖｔａｐｅ５＝クラスタ２４５
【００６５】
よってこの例においては、以下のクラスタが重複排除移動／コピー論理２０４によって生成されている。
クラスタ２４３
クラスタ２４５
クラスタ３４（以前の生成による）
【００６６】
このステップの後に、重複排除移動／コピー論理２０４によって２つの一致するクラスタが生成されていることがあることに留意すべきである。もし２つの一致するクラスタが存在すれば、重複排除移動／コピー論理２０４は一致するインスタンスの一方を削除する。この例においては一致するクラスタがないため、重複排除移動／コピー論理２０４はクラスタがエクスポートされるまでこのプロセスを繰り返す。すなわち重複排除移動／コピー論理２０４は、次のとおりに２つの新たなクラスタによってチャンク−マトリックス・テーブルを増加させる。
【００６７】
【表９】
2015505997.tif 000013
【００６８】
重複排除移動／コピー論理２０４は、どのクラスタができる限り少ないＶｔａｐｅ内に最も多くの共通チャンクを有するかを判定することによって、最良のクラスタを選択する。
クラスタ２４３：３つのＶｔａｐｅを用いて５つの共通チャンク→５／３＝１．６６６
クラスタ２４５：３つのＶｔａｐｅを用いて６つの共通チャンク→６／３＝２．０
クラスタ３４：２つのＶｔａｐｅを用いて４つの共通チャンク→４／２＝２．０
クラスタ２４５およびクラスタ３４のように２つのクラスタ因子が一致するときには、重複排除移動／コピー論理２０４は１つのクラスタをランダムに選択する。
【００６９】
たとえば、重複排除移動／コピー論理２０４がクラスタ３４を選択するとき、重複排除移動／コピー論理２０４は、選択されたクラスタの［エクスポート−サイズ］とリムーバブル記憶システムの利用可能な容量［ｒｓｍ−サイズ］とに基づいて、選択されたクラスタがリムーバブル記憶システム２１０に保存され得るかどうかを判定する。
クラスタ３４に対して、
Ｖｔａｐｅ３：［重複排除−Ｖｔａｐｅ−サイズ］−［Ｖｔａｐｅ４をポイントする複数参照−チャンク］−［他のＶｔａｐｅへの共通参照］、これは次のとおりになる。
Ｖｔａｐｅ３：１７−０−３（Ａ０５ｐ，Ｂ０３ｐ，Ｂ０６ｐ）＝１４チャンク
Ｖｔａｐｅ４：［重複排除−Ｖｔａｐｅ−サイズ］−［Ｖｔａｐｅ３をポイントする複数参照−チャンク］−［他のＶｔａｐｅへの共通参照］、これは次のとおりになる。
Ｖｔａｐｅ４：１２−０−３（Ａ０５ｐ，Ｂ０３ｐ，Ｂ０６ｐ）＝９チャンク
他のチャンクへの共通参照＝３チャンク（Ａ０５ｐ，Ｂ０３ｐ，Ｂ０６ｐ）
よって、選択されたクラスタのサイズ［重複排除−クラスタ−サイズ］は、１４＋９＋３＝２６チャンクとなり、これは２６ＭＢの［エクスポート−サイズ］と等価になる。
【００７０】
定められた２６ＭＢは［ｒｓｍ−サイズ］よりも小さく、かつ［ｒｓｍ−閾値］よりも小さいため、重複排除移動／コピー論理２０４はなおも移動／コピーすべき追加のＶｔａｐｅがあるかどうかを判定する。移動すべき追加のＶｔａｐｅがあるため、重複排除移動／コピー論理２０４は以下に示されるとおり、増加チャンク・マトリックス・テーブル内の選択された最良クラスタのｎ次元表現を生成する。
クラスタ３４（１／０／１／０／１／１）
【００７１】
重複排除移動／コピー論理２０４は、選択された最良クラスタ点に対するすべてのＶｔａｐｅ点のユークリッド距離を算出する。以下のとおり、重複排除移動／コピー論理２０４は、結果として得られる例示的なユークリッド距離値をＶｔａｐｅ−クラスタ・マトリックスに挿入する。
【００７２】
【表１０】
2015505997.tif 000014
【００７３】
Ｖｔａｐｅ−クラスタ・マトリックスによると、Ｖｔａｐｅ２はクラスタ３４に対する最短距離を有するものである。したがって、次いで重複排除移動／コピー論理２０４は、選択された最良クラスタに、選択された最良クラスタ点への最短ユークリッド距離を有するＶｔａｐｅを加えて、クラスタ３４２を作成する。
【００７４】
よってこの例においては、以下のクラスタが重複排除移動／コピー論理２０４によって生成されている。
クラスタ２４３
クラスタ２４５
クラスタ３４２
【００７５】
クラスタ２４３とクラスタ３４２とは同じであるため、重複排除移動／コピー論理２０４は一方のインスタンスを削除する。したがってクラスタ２４３およびクラスタ２４５のみが残される。重複排除移動／コピー論理２０４は再び、先行するクラスタ−チャンク参照部分によってチャンク−マトリックス・テーブルを増加し、どのクラスタができる限り少ないＶｔａｐｅ内に最も多くの共通チャンクを有するかを判定することによって、最良のクラスタを選択する。
クラスタ２４３：３つのＶｔａｐｅを用いて５つの共通チャンク→５／３＝１．６６６
クラスタ２４５：３つのＶｔａｐｅを用いて６つの共通チャンク→６／３＝２．０
【００７６】
重複排除移動／コピー論理２０４は、クラスタ２４３がクラスタ２４５よりも良い因子を有すると判定する。重複排除移動／コピー論理２０４は、選択されたクラスタの［エクスポート−サイズ］とリムーバブル記憶システムの利用可能な容量［ｒｓｍ−サイズ］とに基づいて、選択されたクラスタがリムーバブル記憶システム２１０に保存され得るかどうかを判定する。
クラスタ２４３に対して、
Ｖｔａｐｅ２：［重複排除−Ｖｔａｐｅ−サイズ］−［Ｖｔａｐｅ４をポイントする複数参照−チャンク］−［Ｖｔａｐｅ３をポイントする複数参照−チャンク］−［他のＶｔａｐｅへの共通参照］、これは次のとおりになる。
Ｖｔａｐｅ２：１３−０−０−２（Ａ０１ｐ，Ａ０５ｐ）＝１１チャンク
Ｖｔａｐｅ４：［重複排除−Ｖｔａｐｅ−サイズ］−［Ｖｔａｐｅ２をポイントする複数参照−チャンク］−［Ｖｔａｐｅ３をポイントする複数参照−チャンク］−［他のＶｔａｐｅへの共通参照］
Ｖｔａｐｅ４：１２−２（Ｂ０３ｐ，Ｂ０６ｐ）−０−２（Ａ０１ｐ，Ａ０５ｐ）＝８チャンク
Ｖｔａｐｅ３：［重複排除−Ｖｔａｐｅ−サイズ］−［Ｖｔａｐｅ２をポイントする複数参照−チャンク］−［Ｖｔａｐｅ４をポイントする複数参照−チャンク］−［他のＶｔａｐｅへの共通参照］
Ｖｔａｐｅ３：１７−２（Ｂ０３ｐ，Ｂ０６ｐ）−０−１（Ａ０５ｐ）＝１４チャンク
他のチャンクへの共通参照＝２チャンク（Ａ０１ｐ，Ａ０５ｐ）
よって、選択されたクラスタのサイズ［重複排除−クラスタ−サイズ］は、１１＋８＋１４＋２＝３５チャンクとなり、これは３５ＭＢの［エクスポート−サイズ］と等価になる。
【００７７】
クラスタ２４３は［ｒｓｍ−サイズ］よりも小さく、かつ［ｒｓｍ−閾値］よりも大きいため、重複排除移動／コピー論理２０４は選択されたクラスタ配置におけるクラスタの部分ではない参照を修正して、それらのクラスタを参照しないようにする。たとえば、Ｖｔａｐｅ２におけるＡ０１ｐが修正されて一意のチャンクになる。次いで、重複排除移動／コピー論理２０４はクラスタ２３４をエクスポートする。重複排除移動／コピー論理２０４はＶｔａｐｅ２、Ｖｔａｐｅ３またはＶｔａｐｅ４を含むすべてのクラスタを削除し、それらのＶｔａｐｅに対するすべてのエントリをＶｔａｐｅ−Ｖｔａｐｅ−マトリックスから除去し、以下のものを残す。
【００７８】
【表１１】
2015505997.tif 000015
【００７９】
次いで重複排除移動／コピー論理２０４は、すべてのＶｔａｐｅが移動／コピーされるまでこのプロセスを繰り返す。
【００８０】
重複排除移動／コピー論理２０４がエクスポートされるべきクラスタを識別するとき、重複排除移動／コピー論理２０４は、たとえば、リムーバブル記憶システム２１０がテープ記憶媒体であるときにはテープの一定の前方／後方への巻取りを回避し、リムーバブル記憶システム２１０が外部ハード・ディスク・ドライブであるときにはディスク・ヘッドの移動を回避し、リムーバブル記憶システム２１０が光学ディスク記憶媒体であるときにはレーザ・ヘッドの移動を回避するなどの態様で、クラスタ内のＶｔａｐｅに関連するデータの編成を進める。
【００８１】
前に定めたとおり、クラスタ２４３に対して、
Ｖｔａｐｅ２：［重複排除−Ｖｔａｐｅ−サイズ］−［Ｖｔａｐｅ４をポイントする複数参照−チャンク］−［Ｖｔａｐｅ３をポイントする複数参照−チャンク］−［他のＶｔａｐｅへの共通参照］、これは次のとおりになる。
Ｖｔａｐｅ２：１３−０−０−２（Ａ０１ｐ，Ａ０５ｐ）＝１１チャンク
Ｖｔａｐｅ４：［重複排除−Ｖｔａｐｅ−サイズ］−［Ｖｔａｐｅ２をポイントする複数参照−チャンク］−［Ｖｔａｐｅ３をポイントする複数参照−チャンク］−［他のＶｔａｐｅへの共通参照］
Ｖｔａｐｅ４：１２−２（Ｂ０３ｐ，Ｂ０６ｐ）−０−２（Ａ０１ｐ，Ａ０５ｐ）＝８チャンク
Ｖｔａｐｅ３：［重複排除−Ｖｔａｐｅ−サイズ］−［Ｖｔａｐｅ２をポイントする複数参照−チャンク］−［Ｖｔａｐｅ４をポイントする複数参照−チャンク］−［他のＶｔａｐｅへの共通参照］
Ｖｔａｐｅ３：１７−２（Ｂ０３ｐ，Ｂ０６ｐ）−０−１（Ａ０５ｐ）＝１４チャンク
他のチャンクへの共通参照＝２チャンク（Ａ０１ｐ，Ａ０５ｐ）
よって、選択されたクラスタのサイズ［重複排除−クラスタ−サイズ］は、１１＋８＋１４＋２＝３５チャンク、すなわち３５ＭＢの［エクスポート−サイズ］となる。上に考察されるとおり、リムーバブル記憶システム２１０の例示的容量［ｒｓｍ−サイズ］は４０ＭＢである。
【００８２】
クラスタ２３４のチャンク・レイアウトは次のとおりである。
【００８３】
【表１２】
2015505997.tif 000016
【００８４】
Ｖｔａｐｅは互いの類似性に従って分類される。したがって重複排除移動／コピー論理２０４は次のとおりに、メトリック・マトリックス［Ｍ］を生成することによって各Ｖｔａｐｅに対する「最短近隣（ｎｅａｒｅｓｔ  ｎｅｉｇｈｂｏｒ）」を定める。
【００８５】
【表１３】
2015505997.tif 000017
【００８６】
このメトリック・マトリックス［Ｍ］に基づき、重複排除移動／コピー論理２０４は最初の表示として最短ユークリッド距離を有する２つのＶｔａｐｅを選択する。それはこの例においてはＶｔａｐｅ２およびＶｔａｐｅ４である。なぜならＶｔａｐｅ２およびＶｔａｐｅ４は最も多くの共通チャンクを有するからである。次いで重複排除移動／コピー論理２０４は、Ｖｔａｐｅ２およびＶｔａｐｅ４を分類順序の端縁としてマーク付けする。重複排除移動／コピー論理２０４は、Ｖｔａｐｅ２またはＶｔａｐｅ４のいずれかに対する次の最短距離を有する次のＶｔａｐｅを探す。それはこの場合はＶｔａｐｅ３であり、Ｖｔａｐｅ３はＶｔａｐｅ２よりもＶｔａｐｅ４の方に近い。したがって重複排除移動／コピー論理２０４はＶｔａｐｅ３を順序に加え、Ｖｔａｐｅの順序をＶｔａｐｅ２、Ｖｔａｐｅ４およびＶｔａｐｅ３として示し、Ｖｔａｐｅ２およびＶｔａｐｅ３を新たなＶｔａｐｅ端縁とする。Ｖｔａｐｅが残っている限り、重複排除移動／コピー論理２０４はこのＶｔａｐｅ順序を増していく。ここには３つのＶｔａｐｅしかないため、Ｖｔａｐｅの表現は以下のとおりになる。
【００８７】
【表１４】
2015505997.tif 000018
【００８８】
上記のグループ化に従って、重複排除移動／コピー論理２０４は以下の順序でリムーバブル記憶システム２１０にＶｔａｐｅを書込む（番号１〜７０は、リムーバブル記憶システム２１０上の位置である）。
【００８９】
【表１５】
2015505997.tif 000019
【００９０】
さらなる実施形態においては、チャンクの最初のインスタンスのみを書込むのではなく、重複排除移動／コピー論理２０４はチャンクの最後のインスタンスのみを書込んでもよく、その結果としてＶｔａｐｅは以下の順序でリムーバブル記憶システム２１０に書込まれる。
【００９１】
【表１６】
2015505997.tif 000020
【００９２】
チャンクをリムーバブル記憶システム２１０に書込む前に、重複排除移動／コピー論理２０４がチャンクの最初のインスタンスまたはチャンクの最後のインスタンスのいずれを書込むかを決めるとき、重複排除移動／コピー論理２０４はリムーバブル記憶システム２１０に残る容量の量を定めてもよい。たとえば、一意のデータ・チャンクのサイズは１ＭＢであってもよく、ポインタのサイズは１ｋＢであってもよい。上記の例においては、６７個のチャンク位置があり、そのうち３２個がポインタで３５個が一意のチャンクである。よってリムーバブル記憶システム２１０に書込まれるデータの量は、実際上次のとおりになる。３５＊１ＭＢデータ＋３２＊１ｋＢポインタ＝３５．０３２ＭＢ。リムーバブル記憶システム２１０の初期利用可能容量が４０ＭＢであるとき、重複排除移動／コピー論理２０４がリムーバブル記憶システム２１０にデータを書込んだ後に残る空間は次のとおりになる。４０ＭＢ−３５．０３２ＭＢ＝４．９６８ＭＢ。
【００９３】
リムーバブル記憶システム２１０に空き空間があるとき、この残りの空間を無駄にする代わりに、重複排除移動／コピー論理２０４はこの空間を用いてチャンクを２回書込むことによって、リムーバブル記憶システム２１０がテープ記憶媒体であるときにはテープの一定の前方／後方への巻取りを回避し、リムーバブル記憶システム２１０が外部ハード・ディスク・ドライブであるときにはディスク・ヘッドの移動を回避し、リムーバブル記憶システム２１０が光学ディスク記憶媒体であるときにはレーザ・ヘッドの移動を回避するなどしてもよい。どのチャンクを２回書込むべきかを決めるために、重複排除移動／コピー論理２０４はさまざまなポリシーを実施してもよい。たとえば、実施されるポリシーに基づいて、重複排除移動／コピー論理２０４は、最も多く参照されるチャンクを複数回書込むか、最初の出現と最後の出現との間の距離が最大であるチャンクを２回書込むか、または元のチャンクと元のチャンクに対するポインタとの間の距離が最長であると判定されたチャンクを再書込することによって、参照距離を減少させるなどしてもよい。空き空間が追加のチャンクで満たされても満たされなくても、リムーバブル記憶システム２１０の利用可能な空間をどのように割り当てるべきかを重複排除移動／コピー論理２０４が定めた後に、重複排除移動／コピー論理２０４は定められた構成のデータをリムーバブル記憶システム２１０に書込む。
【００９４】
さらなる実施形態において、重複排除移動／コピー論理２０４は、最も多く参照されるチャンクをリムーバブル記憶システム２１０の始めに特殊なパターンで書込むことによって、マイクロコードが駆動されてこれらの最も多く参照されるチャンクを不揮発性ランダム・アクセス・メモリ（ｎｏｎ−ｖｏｌａｔｉｌｅ  ｒａｎｄｏｍ  ａｃｃｅｓｓ  ｍｅｍｏｒｙ：ＮＶＲＡＭ）にフェッチし、読取りの際にこれらのチャンクを逆参照するようにしてもよい。
【００９５】
通常の当業者に容易に認識され得るとおり、内部記憶システム２０８およびリムーバブル記憶システム２１０は両方とも、さまざまな時点でデータ処理システム２００内のバックアップ・アプリケーションによってアクセス可能であってもよい。よってバックアップ・アプリケーションは、内部記憶システム２０８から、またはデータがすでに移動／コピーされているときにはリムーバブル記憶システム２１０から読取りを行う必要があり得る。したがって重複排除移動／コピー論理２０４は、Ｖｔａｐｅがリムーバブル記憶システム２１０に移動／コピーされたときにこうしたバックアップ・アプリケーションに通知する必要があり得る。すなわち、バックアップ・アプリケーションは下記を用いてＶｔａｐｅの位置を追跡してもよい。
【００９６】
【表１７】
2015505997.tif 000021
【００９７】
リムーバブル記憶システム２１０からの通知を受け取ると、バックアップ・アプリケーションはＶｔａｐｅの位置を次のとおりに更新してもよい。
【００９８】
【表１８】
2015505997.tif 000022
【００９９】
当業者に認識されるとおり、本発明はシステム、方法またはコンピュータ・プログラム製品として具現化されてもよい。したがって本発明の局面は、完全にハードウェアの実施形態、完全にソフトウェアの実施形態（ファームウェア、常駐ソフトウェア、マイクロコードなどを含む）、またはソフトウェアおよびハードウェアの局面を組み合わせた実施形態の形を取ってもよく、本明細書においてこれらはすべて一般的に「回路」、「モジュール」または「システム」と呼ばれることがある。さらに、本発明の局面は、コンピュータ使用可能プログラム・コードが具現化されているあらゆる１つまたはそれ以上のコンピュータ読取り可能媒体（単数または複数）において具現化されるコンピュータ・プログラム製品の形を取ってもよい。
【０１００】
１つまたはそれ以上のコンピュータ読取り可能媒体（単数または複数）のあらゆる組み合わせが用いられてもよい。コンピュータ読取り可能媒体は、コンピュータ読取り可能信号媒体またはコンピュータ読取り可能記憶媒体であってもよい。コンピュータ読取り可能記憶媒体は、たとえば電子、磁気、光学、電磁気、赤外、または半導体のシステム、装置、デバイス、または前述のもののあらゆる好適な組み合わせなどであってもよいがそれに限定されない。コンピュータ読取り可能記憶媒体のより特定的な例（非網羅的なリスト）は以下を含む。すなわち、１つまたはそれ以上のワイヤを有する電気的接続、ポータブル・コンピュータ・ディスケット、ハード・ディスク、ランダム・アクセス・メモリ（ｒａｎｄｏｍ  ａｃｃｅｓｓ  ｍｅｍｏｒｙ：ＲＡＭ）、リード・オンリ・メモリ（ＲＯＭ）、消去可能プログラマブル・リード・オンリ・メモリ（ｅｒａｓａｂｌｅ  ｐｒｏｇｒａｍｍａｂｌｅ  ｒｅａｄ−ｏｎｌｙ  ｍｅｍｏｒｙ）（ＥＰＲＯＭまたはフラッシュ・メモリ）、光ファイバ、ポータブル・コンパクト・ディスク・リード・オンリ・メモリ（ｃｏｍｐａｃｔ  ｄｉｓｃ  ｒｅａｄ−ｏｎｌｙ  ｍｅｍｏｒｙ：ＣＤＲＯＭ）、光学記憶装置、磁気記憶装置、または前述のもののあらゆる好適な組み合わせである。本文書の状況において、コンピュータ読取り可能記憶媒体は、命令実行システム、装置またはデバイスによる使用、またはそれに関連する使用のためのプログラムを含有または保存し得るあらゆる有形の媒体であってもよい。
【０１０１】
コンピュータ読取り可能信号媒体は、たとえばベースバンド内で、または搬送波の部分などとして媒体内で具現化されるコンピュータ読取り可能プログラム・コードを有する伝播データ信号を含んでもよい。こうした伝播信号は、電磁気信号、光学信号、またはそのあらゆる好適な組み合わせを含むがそれに限定されないさまざまな形のいずれかを取ってもよい。コンピュータ読取り可能信号媒体は、コンピュータ読取り可能記憶媒体ではなく、かつ命令実行システム、装置またはデバイスによる使用、またはそれに関連する使用のためのプログラムを通信、伝播または移送できるあらゆるコンピュータ読取り可能媒体であってもよい。
【０１０２】
コンピュータ読取り可能媒体において具現化されるコンピュータ・コードは、ワイヤレス、ワイヤライン、光ファイバ・ケーブル、無線周波数（ｒａｄｉｏ  ｆｒｅｑｕｅｎｃｙ：ＲＦ）など、またはそのあらゆる好適な組み合わせを含むがそれに限定されないあらゆる適切な媒体を用いて送信されてもよい。
【０１０３】
本発明の局面のための動作を行うためのコンピュータ・プログラム・コードは、オブジェクト指向プログラミング言語、たとえばＪａｖａ（商標）、Ｓｍａｌｌｔａｌｋ（商標）、Ｃ＋＋など、および従来の手続き型プログラミング言語、たとえば「Ｃ」プログラミング言語または類似のプログラミング言語などを含む、１つまたはそれ以上のプログラミング言語のあらゆる組み合わせで書かれていてもよい。プログラム・コードは、すべてがユーザのコンピュータで実行されてもよいし、スタンド・アロン・ソフトウェア・パッケージとして部分的にユーザのコンピュータで実行されてもよいし、一部がユーザのコンピュータで、一部がリモート・コンピュータで実行されてもよいし、すべてがリモート・コンピュータまたはサーバで実行されてもよい。後者のシナリオにおいて、リモート・コンピュータは、ローカル・エリア・ネットワーク（ＬＡＮ）または広域ネットワーク（ｗｉｄｅ  ａｒｅａ  ｎｅｔｗｏｒｋ：ＷＡＮ）を含むあらゆるタイプのネットワークを通じてユーザのコンピュータに接続されてもよいし、（たとえば、インターネット・サービス・プロバイダを用いてインターネットを通じて）外部コンピュータへの接続が行われてもよい。
【０１０４】
本発明の例示的実施形態に従う方法、装置（システム）およびコンピュータ・プログラム製品の流れ図もしくはブロック図またはその両方を参照して、本発明の局面を以下に説明する。流れ図もしくはブロック図またはその両方の各ブロック、および流れ図もしくはブロック図またはその両方におけるブロックの組み合わせは、コンピュータ・プログラム命令によって実現され得ることが理解されるだろう。これらのコンピュータ・プログラム命令が、汎用コンピュータもしくは特定目的のコンピュータのプロセッサ、またはマシンを生成するためのその他のプログラマブル・データ処理装置に与えられることによって、そのコンピュータのプロセッサまたはその他のプログラマブル・データ処理装置を介して実行された命令が、流れ図もしくはブロック図またはその両方の単数または複数のブロックにおいて指定された機能／動作を実現するための手段を作成するようにしてもよい。
【０１０５】
これらのコンピュータ・プログラム命令は、コンピュータ、その他のプログラマブル・データ処理装置またはその他のデバイスに特定の態様で機能するよう指示できるコンピュータ読取り可能媒体の中に保存されることによって、コンピュータ読取り可能媒体に保存された命令が、流れ図もしくはブロック図またはその両方の単数または複数のブロックにおいて指定された機能／動作を実現する命令を含む製造品を生成するようにしてもよい。
【０１０６】
さらに、コンピュータ・プログラム命令は、コンピュータ、その他のプログラマブル・データ処理装置またはその他のデバイスにロードされて、そのコンピュータ、その他のプログラマブル装置またはその他のデバイスにおいて一連の動作ステップを行わせることにより、コンピュータまたはその他のプログラマブル装置において実行された命令が、流れ図もしくはブロック図またはその両方の単数または複数のブロックにおいて指定された機能／動作を実現するためのプロセスを提供するような、コンピュータに実現されるプロセスを生成してもよい。
【０１０７】
図３〜図６は、例示的実施形態に従って内部記憶システムからリムーバブル記憶システムへの重複排除データの移動／コピーを最適化するステップにおいて、重複排除移動／コピー論理によって行われる動作を示す流れ図である。この動作が始まる際に、重複排除移動／コピー論理は、内部記憶システムに保存される仮想テープ内に集約されたすべての複数参照チャンクを含むチャンク参照テーブルを生成する（ステップ３０２）。このチャンク参照テーブルを用いて、重複排除移動／コピー論理は、各Ｖｔａｐｅに対してどのチャンクが参照されるかを示すチャンク・マトリックス・テーブルを生成する（ステップ３０４）。このチャンク・マトリックス・テーブルを用いて、重複排除移動／コピー論理は、各Ｖｔａｐｅに対するチャンク・マトリックス・テーブル内の点のｎ次元表現を生成する（ステップ３０６）。
【０１０８】
ｎ次元空間における点としてのＶｔａｐｅの表現によって、重複排除移動／コピー論理は各２つのＶｔａｐｅ間のメトリックを算出する（ステップ３０８）。重複排除移動／コピー論理は、結果として得られるメトリック値をメトリック・マトリックス［Ｍ］に挿入する（ステップ３１０）。重複排除移動／コピー論理は、生成されるべきクラスタの予備数を定める（ステップ３１２）。重複排除移動／コピー論理は、メトリック・マトリックス［Ｍ］からＶｔａｐｅ間の最短距離を検索し（ステップ３１４）、先行するクラスタ−チャンク参照部分によって増加されたチャンク−マトリックス・テーブル内に識別された数のクラスタを生成する（ステップ３１６）。重複排除移動／コピー論理は、どのクラスタができる限り少ないＶｔａｐｅ内に最も多くの共通チャンクを有するかを判定することによって、最良のクラスタを選択する（ステップ３１８）。
【０１０９】
最良クラスタが選択されると、重複排除移動／コピー論理は、選択されたクラスタの［エクスポート−サイズ］とリムーバブル記憶システムの利用可能な容量［ｒｓｍ−サイズ］とに基づき、［エクスポート−サイズ］がリムーバブル記憶システムの利用可能な容量［ｒｓｍ−サイズ］よりも大きいかどうかを判定することによって、選択されたクラスタがリムーバブル記憶システムに保存され得るかどうかを判定する（ステップ３２０）。ステップ３２０において、［エクスポート−サイズ］が［ｒｓｍ−サイズ］よりも大きいと重複排除移動／コピー論理が判定するとき、重複排除移動／コピー論理はそのクラスタ配置を禁止クラスタのリストに加える（ステップ３２２）。重複排除移動／コピー論理は、選択されたクラスタが３つ以上のＶｔａｐｅを有するかどうかを判定する（ステップ３２４）。ステップ３２４において、選択されたクラスタが３つ以上のＶｔａｐｅを含むとき、重複排除移動／コピー論理は最後に加えられたクラスタ構成要素をクラスタから除去し（ステップ３２６）、その後プロセスはステップ３２０に戻る。ステップ３２４において、Ｖｔａｐｅが２つしか残っておらず、よってＶｔａｐｅを１つ除去することによってクラスタがなくなるとき、重複排除移動／コピー論理はその低減されたクラスタ配置を禁止クラスタのリストに加え（ステップ３２８）、その後動作はステップ３１８に戻る。
【０１１０】
ステップ３２０において、クラスタの［エクスポート−サイズ］がリムーバブル記憶システムの利用可能な容量［ｒｓｍ−サイズ］よりも小さいと重複排除移動／コピー論理が判定するとき、重複排除移動／コピー論理は、［エクスポート−サイズ］がリムーバブル記憶システムの容量から任意の予め定義された安全マージンを引いたもの［ｒｓｍ−閾値］を超えているかどうかを判定する（ステップ３３０）。ステップ３３０において［エクスポート−サイズ］が［ｒｓｍ−閾値］よりも大きいとき、重複排除移動／コピー論理は選択されたクラスタ配置におけるクラスタの部分ではない参照を修正して、それらのクラスタを参照しないようにする（ステップ３３２）。次いで、重複排除移動／コピー論理はそのクラスタをリムーバブル記憶システムにエクスポートする（ステップ３３４）。Ｖｔａｐｅクラスタがエクスポートされた後、重複排除移動／コピー論理は、そのクラスタのＶｔａｐｅに関連するすべてのエントリを、メトリック・マトリックス［Ｍ］およびその他すべてのクラスタから削除する（ステップ３３６）。この時点で、移動／コピー・プロセスの目的に依存して、重複排除移動／コピー論理はエクスポートされたクラスタに関連するすべてのデータを内部記憶システムから削除してもよい（ステップ３３７）。重複排除移動／コピー論理は、なおも異なるリムーバブル記憶システムに移動／コピーすべき追加のＶｔａｐｅがあるかどうかを判定する（ステップ３３８）。ステップ３３８において、なおも移動／コピーすべき追加のＶｔａｐｅがあるとき、動作はステップ３１４に戻る。ステップ３３８において追加のＶｔａｐｅがないとき、動作は終了する。
【０１１１】
ステップ３３０において、［エクスポート−サイズ］が［ｒｓｍ−閾値］以下であるとき、重複排除移動／コピー論理は、なおも移動／コピーすべき追加のＶｔａｐｅがあるかどうかを判定する（ステップ３４０）。ステップ３４０においてＶｔａｐｅが残されていないとき、重複排除移動／コピー論理は、移動／コピー・プロセスを続けるべきかどうかについてユーザに確認する（ステップ３４２）。ステップ３４２において、移動／コピー・プロセスを進めることをユーザが示すとき、動作はステップ３３２に進む。ステップ３４２において、移動／コピーを進めないことをユーザが示すとき、動作は終了する。
【０１１２】
ステップ３４０において、移動／コピーすべき追加のＶｔａｐｅがあるとき、重複排除移動／コピー論理は、増加チャンク・マトリックス・テーブル内の選択された最良クラスタのｎ次元表現を生成する（ステップ３４４）。重複排除移動／コピー論理は、選択された最良クラスタ点に対するすべてのＶｔａｐｅ点のユークリッド距離を算出し（ステップ３４６）、結果として得られる例示的なユークリッド距離値をＶｔａｐｅ−クラスタ・マトリックスに挿入する（ステップ３４８）。次いで重複排除移動／コピー論理は、もしそのクラスタ配置が禁止＿クラスタ・リストになければ、選択された最良クラスタに、選択された最良クラスタ点への最短ユークリッド距離を有するＶｔａｐｅを加え（ステップ３５０）、その後動作はステップ３１６に進む。
【０１１３】
図７は、例示的実施形態に従って内部記憶システムからリムーバブル記憶システムへの重複排除データの移動／コピーを編成するステップにおいて、重複排除移動／コピー論理によって行われる動作を示す流れ図である。この動作が始まる際に、重複排除移動／コピー論理は、メトリック・マトリックス［Ｍ］を生成することによって各々の識別されたＶｔａｐｅに対する「最短近隣」を定める（ステップ４０２）。このメトリック・マトリックス［Ｍ］に基づき、重複排除移動／コピー論理は最初の表示として最短メトリックを有する２つのＶｔａｐｅを選択する（ステップ４０４）。重複排除移動／コピー論理はその２つのＶｔａｐｅを分類順序の端縁としてマーク付けする（ステップ４０６）。重複排除移動／コピー論理は、識別されたＶｔａｐｅのいずれかに対する次の最短距離を有する次のＶｔａｐｅを探す（ステップ４０８）。重複排除移動／コピー論理は、この次のＶｔａｐｅを順序に加え、この次のＶｔａｐｅを新たなＶｔａｐｅ端縁として示す（ステップ４１０）。次いで重複排除移動／コピー論理は、編成すべき追加のＶｔａｐｅがあるかどうかを判定する（ステップ４１２）。ステップ４１２においてＶｔａｐｅが残されているとき、重複排除移動／コピー論理は動作をステップ４０６に戻すことによってＶｔａｐｅの順序を増やす。
【０１１４】
ステップ４１２においてすべてのＶｔａｐｅが編成されているとき、重複排除移動／コピー論理は、リムーバブル記憶システムに残る容量の量を定める（ステップ４１４）。ステップ４１４においてリムーバブル記憶システムに空き空間があるとき、重複排除移動／コピー論理は、識別されるポリシーに基づいて空き空間に書込みを行う（ステップ４１６）。ステップ４１６の後、またはステップ４１４においてリムーバブル記憶システムに空き空間がないとき、重複排除移動／コピー論理は定められた構成のデータをリムーバブル記憶システムに書込み（ステップ４１８）、その後動作は終了する。
【０１１５】
図面中の流れ図およびブロック図は、本発明のさまざまな実施形態に従うシステム、方法およびコンピュータ・プログラム製品の実現可能なアーキテクチャ、機能および動作を例示するものである。これに関して、流れ図またはブロック図における各ブロックは、指定された論理関数（単数または複数）を実現するための１つまたはそれ以上の実行可能な命令を含むモジュール、セグメント、またはコードの部分を表していてもよい。さらに、いくつかの代替的な実現においては、ブロック中に示される機能が図面に示される以外の順序で起こってもよいことに留意すべきである。たとえば、連続して示される２つのブロックは、伴われる機能に依存して、実際には実質的に同時に実行されてもよいし、それらのブロックがときには逆の順序で実行されてもよい。さらに、ブロック図もしくは流れ図またはその両方の各ブロック、およびブロック図もしくは流れ図またはその両方のブロックの組み合わせは、指定された機能もしくは動作を行う特定目的のハードウェアに基づくシステム、または特定目的のハードウェアとコンピュータ命令との組み合わせによって実現され得ることを注記する。
【０１１６】
よって例示的実施形態は、データ・オブジェクト・チャンクおよびデータ・オブジェクト・チャンクに対するすべての参照を同じリムーバブル媒体上に一緒に保ちながら、リムーバブル記憶システムに重複排除データを移動／コピーするための機構を提供する。重複排除エンジンは、１つのリムーバブル記憶システムに適切に保存され得るデータ・オブジェクトの組に関係する一意のチャンクの組を選択する重複排除プロセスを行う。すなわち、例示的実施形態の機構は、データ・オブジェクトに関連するチャンクを追跡する重複排除テーブルから、リムーバブル記憶システムに移動／コピーされるべきすべてのデータ・オブジェクトに対する一意のチャンクを識別する。リムーバブル記憶システムに適切に保存され得る類似チャンク・クラスタの組が識別されるとき、そのクラスタの組がリムーバブル記憶システムに移動／コピーされる。
【０１１７】
上に言及したとおり、例示的実施形態は完全にハードウェアの実施形態、完全にソフトウェアの実施形態、またはハードウェアおよびソフトウェアの両方の構成要素を含む実施形態の形を取ってもよいことが認識されるべきである。例示的実施形態の１つにおいて、例示的実施形態の機構はソフトウェアまたはプログラム・コードにおいて実現され、それはファームウェア、常駐ソフトウェア、マイクロコードなどを含むがそれに限定されない。
【０１１８】
プログラム・コードの保存もしくは実行またはその両方を行うために好適なデータ処理システムは、システム・バスを通じて直接的または間接的にメモリ構成要素に結合された少なくとも１つのプロセッサを含む。メモリ構成要素は、プログラム・コードの実際の実行の際に用いられるローカル・メモリ、バルク記憶装置、および実行中にバルク記憶装置からコードを検索しなければならない回数を減らすために少なくとも何らかのプログラム・コードの一時的記憶を提供するキャッシュ・メモリを含み得る。
【０１１９】
入出力すなわちＩ／Ｏデバイス（キーボード、ディスプレイ、ポインティング・デバイスなどを含むがそれに限定されない）は、システムに直接結合されてもよいし、介在するＩ／Ｏコントローラを通じて結合されてもよい。さらに、介在する私用ネットワークまたは公共ネットワークを通じてデータ処理システムが他のデータ処理システムまたはリモート・プリンタもしくは記憶装置に結合され得るようにするために、システムにネットワーク・アダプタが結合されてもよい。モデム、ケーブル・モデムおよびイーサネット（Ｒ）カードは、現在利用可能なネットワーク・アダプタの種類のほんの一部である。
【０１２０】
本発明の説明は例示および説明の目的のために提供されたものであり、網羅的になったり、開示される形に本発明を制限したりすることは意図されない。たとえばコンパクト・ディスク（ＣＤ）、デジタル多用途ディスク（ＤＶＤ）、およびＢｌｕ−Ｒａｙ  Ｄｉｓｃ（ＢＤ）（Ｒ）などの光学ディスクもリムーバブル媒体であるため、たとえばＶｔａｐｅの代替的実施形態として仮想光学ディスク（ｖｉｒｔｕａｌ  ｏｐｔｉｃａｌ  ｄｉｓｋｓ）に対するＶｄｉｓｋを用いることなど、多くの修正および変更が通常の当業者に明らかになるだろう。実施形態は、本発明の原理および実際の適用を最も良く説明し、かつ他の通常の当業者が、予期される特定の使用に好適であるようなさまざまな修正を伴うさまざまな実施形態に対して本発明を理解できるようにするために選択されて記載されたものである。
【図１】
2015505997.tif 000023
【図２】
2015505997.tif 000024
【図３】
2015505997.tif 000025
【図４】
2015505997.tif 000026
【図５】
2015505997.tif 000027
【図６】
2015505997.tif 000028
【図７】
2015505997.tif 000029
【手続補正書】
【提出日】平成26年6月20日(2014.6.20)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
データ処理システムにおいて、内部記憶システムからリムーバブル記憶システムへの重複排除データの移動／コピーを最適化するための方法であって、
データ・オブジェクトの組の数に基づいて、前記内部記憶システムに保存される前記データ・オブジェクトの組に対して生成されるべきクラスタの予備数を定めるステップと、
前記データ・オブジェクトの組間の最短距離に基づいて前記予備数のクラスタを生成するステップであって、各クラスタはデータ・オブジェクトの１つまたはそれ以上の組を含み、データ・オブジェクトの各組はデータの１つまたはそれ以上のチャンクを含む、ステップと、
できる限り少ないデータ・オブジェクトの組の中に最大数の共通チャンクを有するクラスタを識別することによって、クラスタの組の中から選択されたクラスタを識別するステップと、
前記選択されたクラスタのエクスポート・サイズが、前記リムーバブル記憶システムの利用可能な記憶容量を超えているかどうかを判定するステップと、
前記選択されたクラスタの前記エクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な記憶容量を超えていないことに応答して、選択された前記クラスタを前記リムーバブル記憶システムにエクスポートするステップと
を含む、方法。
【請求項２】
前記選択されたクラスタにおけるデータ・オブジェクトの１つの組のデータの少なくとも１つのチャンクは、前記選択されたクラスタにおけるデータ・オブジェクトの別の組のデータの少なくとも１つのチャンクを参照する、請求項１に記載の方法。
【請求項３】
前記選択されたクラスタが前記リムーバブル記憶システムにエクスポートされた後に、前記選択されたクラスタに関連する前記データ・オブジェクトの組を、移動のためのさらなる検討から除去するステップ
をさらに含む、請求項１に記載の方法。
【請求項４】
前記選択されたクラスタに関連する前記データ・オブジェクトの組を移動のためのさらなる検討から除去した後に、前記リムーバブル記憶システムにおける前記データ・オブジェクトの組の位置に対する参照を前記内部記憶システムに挿入するステップと、
前記選択されたクラスタに関連するすべてのデータを前記内部記憶システムから削除するステップと
をさらに含む、請求項３に記載の方法。
【請求項５】
前記選択されたクラスタを前記リムーバブル記憶システムにエクスポートする前に、前記選択されたクラスタ内の、前記選択されたクラスタの部分ではないチャンク・データ参照を修正して、データのそれらのチャンクを参照しないようにするステップ
をさらに含む、請求項１に記載の方法。
【請求項６】
前記データ・オブジェクトの組の数に基づいて、前記内部記憶システムに保存されるデータ・オブジェクトの組に対して生成されるべきクラスタの前記予備数を定めるステップは、
前記内部記憶システムに保存されるデータ・オブジェクトの組に集約されたすべての複数参照チャンクを含むチャンク参照テーブルを生成するステップと、
データ・オブジェクトの各組に対して、そのデータ・オブジェクトの組によって参照される複数参照チャンクを示すチャンク・マトリックス・テーブルを生成するステップと、
前記チャンク・マトリックス・テーブルを用いて、データ・オブジェクトの各組に対する前記チャンク・マトリックス・テーブル内の点のｎ次元表現を生成するステップと、
前記データ・オブジェクトの組のｎ次元空間における点としての前記表現を用いて、前記データ・オブジェクトの組の各々の間の距離を示す、前記データ・オブジェクトの組の各々の間のメトリック値を算出するステップと、
結果として得られる前記メトリック値をメトリック・マトリックスに挿入するステップと
を含む、請求項１に記載の方法。
【請求項７】
前記選択されたクラスタの前記エクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な記憶容量を超えていることに応答して、前記クラスタの配置を禁止クラスタのリストに加えるステップと、
前記選択されたクラスタがデータ・オブジェクトの３つ以上の組を有するかどうかを判定するステップと、
前記選択されたクラスタがデータ・オブジェクトの３つ以上の組を有することに応答して、最後に加えられたデータ・オブジェクトの組を前記クラスタから除去するステップと、
前記選択されたクラスタの新たなエクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な記憶容量を超えているかどうかを判定するステップと、
前記選択されたクラスタの前記新たなエクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な記憶容量を超えていないことに応答して、最良の前記クラスタを前記リムーバブル記憶システムにエクスポートするステップと
をさらに含む、請求項１に記載の方法。
【請求項８】
前記選択されたクラスタの前記エクスポート・サイズが、前記リムーバブル記憶システムの前記利用可能な容量から予め定義された安全マージンを引いたものを超えているかどうかを判定するステップと、
前記選択されたクラスタの前記エクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な容量から前記予め定義された安全マージンを引いたものを超えていることに応答して、前記選択されたクラスタを前記リムーバブル記憶システムにエクスポートするステップと
をさらに含む、請求項１に記載の方法。
【請求項９】
前記選択されたクラスタの前記エクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な容量から前記予め定義された安全マージンを引いたものを超えていないことに応答して、なおも移動／コピーすべきデータ・オブジェクトの追加の組があるかどうかを判定するステップと、
なおも移動／コピーすべき前記データ・オブジェクトの追加の組の存在に応答して、すでに前記クラスタ内にある前記データ・オブジェクトの組に対する次の最短距離を有するデータ・オブジェクトの次の組を前記選択されたクラスタに加えるステップと、
前記選択されたクラスタの前記エクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な記憶容量を超えているかどうかを判定するステップと、
前記選択されたクラスタの前記エクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な記憶容量を超えていないことに応答して、前記選択されたクラスタを前記リムーバブル記憶システムにエクスポートするステップと
をさらに含む、請求項８に記載の方法。
【請求項１０】
前記データ・オブジェクトの組の間の距離は、差の二乗和の平方根を含むユークリッド距離、前記平方根が取られない前記ユークリッド距離の変形、差の絶対値の和、または１つのチャンクから別のチャンクへのアクセスの合計時間のうちの少なくとも１つに基づいて定められる、請求項１に記載の方法。
【請求項１１】
データ処理システムにおいて、内部記憶システムからリムーバブル記憶システムへの重複排除データの移動／コピーを最適化するためのプログラムであって、
データ・オブジェクトの組の数に基づいて、内部記憶システムに保存される前記データ・オブジェクトの組に対して生成されるべきクラスタの予備数を定めるステップと、
前記データ・オブジェクトの組間の最短距離に基づいて前記予備数のクラスタを生成するステップであって、各クラスタはデータ・オブジェクトの１つまたはそれ以上の組を含み、データ・オブジェクトの各組はデータの１つまたはそれ以上のチャンクを含む、ステップと、
できる限り少ないデータ・オブジェクトの組の中に最大数の共通チャンクを有するクラスタを識別することによって、クラスタの組の中から選択されたクラスタを識別するステップと、
前記選択されたクラスタのエクスポート・サイズが、リムーバブル記憶システムの利用可能な記憶容量を超えているかどうかを判定するステップと、
前記選択されたクラスタの前記エクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な記憶容量を超えていないことに応答して、前記選択されたクラスタを前記リムーバブル記憶システムにエクスポートするステップと
を前記データ処理システムに実行せる、プログラム。
【請求項１２】
内部記憶システムからリムーバブル記憶システムへの重複排除データの移動／コピーを最適化するためのデータ処理システムであって、
プロセッサと、
前記プロセッサに結合されたメモリとを含み、前記メモリは命令を含み、前記命令は前記プロセッサによって実行されるときに、
データ・オブジェクトの組の数に基づいて、内部記憶システムに保存される前記データ・オブジェクトの組に対して生成されるべきクラスタの予備数を定めるステップと、
前記データ・オブジェクトの組間の最短距離に基づいて前記予備数のクラスタを生成するステップであって、各クラスタはデータ・オブジェクトの１つまたはそれ以上の組を含み、データ・オブジェクトの各組はデータの１つまたはそれ以上のチャンクを含む、ステップと、
できる限り少ないデータ・オブジェクトの組の中に最大数の共通チャンクを有するクラスタを識別することによって、クラスタの組の中から選択されたクラスタを識別するステップと、
前記選択されたクラスタのエクスポート・サイズが、リムーバブル記憶システムの利用可能な記憶容量を超えているかどうかを判定するステップと、
前記選択されたクラスタの前記エクスポート・サイズが前記リムーバブル記憶システムの前記利用可能な記憶容量を超えていないことに応答して、前記選択されたクラスタを前記リムーバブル記憶システムにエクスポートするステップと
を前記プロセッサに行わせる、データ処理システム。
【国際調査報告】
2015505997.tif 000030
2015505997.tif 000031