(57)【要約】データ管理及びデータ処理のシステム及び方法が提供される。例えば、種々の実施形態は、同等以上の実行選択結果（例えば、高いデータ冗長性除去及び／又は平均チャンクサイズ）で選択された比較的大きなデータのグループに関するシステム及び方法を含んでもよい。種々の実施形態において、システム及び方法は、例えばデータグループ、ブロック又はチャンク結合技法、及び／又はデータグループ、ブロック又はチャンク分割技法を含んでもよい。種々の実施形態は、第１の標準的又は典型的なデータグループ化、ブロック化又はチャンク化技法、及び／又はデータグループ、ブロック又はチャンク結合技法、及び／又はデータグループ、ブロック又はチャンク分割技法を含んでもよい。例示的システム及び方法は、データハッシュ化及び／又はデータ除去に関連してもよい。実施形態は先読みバッファを含み、基礎となるデータの特性及び／又は本発明の特定の用途（例えばバックアップ）に基づいて、小さなチャンク又は大きなチャンクを放出すべきかどうかを判定することができる。
2010515114.tif 000002
【特許請求の範囲】
【請求項１】
第１のデータ分割手順と第２のデータ分割手順との組み合わせを用いて、データストリームを複数のデータグループに分解することを有し、前記第１のデータ分割手順及び第２のデータ分割手順でのデータグループの期待される平均の大きさが異なる、データ管理の方法。
【請求項２】
前記第２のデータ分割手順は１つ以上の代替のデータ分割手順を含む、請求項１に記載の方法。
【請求項３】
前記第２のデータ分割手順は、前記データストリーム中のデータにおいて先読みすることによって判定されるような、前記データストリーム中のデータに関連するある所定の基準が満たされる場合にのみ適用される、請求項１に記載の方法。
【請求項４】
前記第１の分割手順のデータグループの平均の大きさは前記第２の分割手順のデータグループの平均の大きさよりも小さい、請求項１に記載の方法。
【請求項５】
前記第２のデータ分割手順は、２つ以上の小さなデータグループを一緒に結合して、より大きな平均大きさを有する、より大きなデータグループを生成する、請求項４に記載の方法。
【請求項６】
前記２つ以上の小さなデータグループが、前記データストリームにおいて以前に発生したとは判定されていない新しいデータである場合に、前記第２のデータ分割手順は、前記２つ以上の小さなデータグループを結合してより大きなデータグループとする、請求項５に記載の方法。
【請求項７】
前記データストリームの最大の所定長が達成されまたは処理されたときに、新しいデータの１つ以上の小さなデータグループが、より大きなデータグループになるように結合される、請求項６に記載の方法。
【請求項８】
前記第２のデータ分割手順は、前記２つ以上の小さなデータグループが前記データストリームで以前に発生したと判定されていない新しいデータであり、かつ、該小さなデータグループが、データグループが以前に発生したと判定された後に順次発生している場合には、常に、前記２つ以上の小さなデータグループをより大きなデータグループに結合するステップをスキップする、請求項５に記載の方法。
【請求項９】
前記第２のデータ分割手順は、前記２つ以上の小さなデータグループが前記データストリームで以前に発生したと判定されなかった新しいデータであり、かつ、該小さなデータグループが、以前に発生したと判定されたデータグループの前に順次発生している場合には、前記２つ以上の小さなデータグループをより大きなデータグループに結合するステップをスキップする、請求項５に記載の方法。
【請求項１０】
前記第２のデータ分割手順は、前記２つ以上の小さなデータグループが前記データストリームで以前に発生したと判定されなかった新しいデータであり、かつ、該小さなデータグループは、以前に発生したと判定されたデータグループの前または後のいずれかで順次発生している場合には、前記２つ以上の小さなデータグループをより大きなデータグループに結合するステップをスキップする、請求項５に記載の方法。
【請求項１１】
小さなデータグループの最大数がすでに結合されてしまった場合に、新しいデータの１つ以上の小さなデータグループがより大きなデータグループに結合される、請求項１に記載の方法。
【請求項１２】
１つ以上の小さなデータグループまたは１つ以上のより大きなデータグループを放出するステップをさらに含む、請求項１１に記載の方法。
【請求項１３】
再同期ポイントが横切られない場合、より大きなデータグループが放出されるのみである、請求項１２に記載の方法。
【請求項１４】
以前に放出された、または以前に放出された大きなデータグループの一部として以前に放出されたと判定された、小さなデータグループに重複ステータスが割り当てられ、前記複数のデータグループは連続するデータの順次ストリームである、請求項１３に記載の方法。
【請求項１５】
前記第１のデータ分割手順は、前記データストリームのデータからブレイクポイント及びデータグループ化を独立して決定し、その情報を前記第２のデータ分割手順に入力する、コンテンツ定義のチャンク化またはブロック化手順であり、前記第２のデータ分割手順は、修正されたコンテンツ定義のチャンク化またはブロック化手順、または２つ以上のより小さなデータグループをの１つ以上のより大きなデータグループに結合する手順である、請求項１４に記載の方法。
【請求項１６】
データ記憶システムの重複データ除去を行うのに用いられる、請求項１５に記載の方法。
【請求項１７】
前記第２のデータ分割手順がいつ適用されるかを先読みバッファを用いて決定する、請求項１に記載の方法。
【請求項１８】
前記第２のデータ分割手順は、重複領域、または重複した大きなデータグループ、ブロックまたはチャンクが検出された前または後のいずれかで、重複していない大きなデータグループ、ブロックまたはチャンクをさらに分解する、請求項１に記載の方法。
【請求項１９】
前記第１の分割手順のデータグループの平均の大きさは前記第２の分割手順よりも大きい、請求項１８に記載の方法。
【請求項２０】
少なくとも一つのより小さなデータグループで終わる、より大きなデータグループが重複と考えられない場合、すぐ次に続く多くのデータグループが所定の種類であるか、すぐ次に続く量のデータが重複データであると考えられる場合に、前記第２のデータ分割手順は、前記少なくとも１つのより小さなデータグループには適用されない、請求項１に記載の方法。
【請求項２１】
前記第１の分割手順及び前記第２のデータ分割手順の両方を用いた結果が改善され期待した結果を達成しない場合、前記第１の分割手順及び前記第２のデータ分割手順よりむしろ単一の代替のデータ分割手順が用いられる、請求項１に記載の方法。
【請求項２２】
前記第２のデータ分割手順を適用する機会が複数回あり、結果として生じた少なくとも１つのより大きなデータグループが重複であると評価される場合には、常に、前記第２のデータ分割手順は少なくとも１つのそのようなより大きなデータグループに適用される、請求項１に記載の方法。
【請求項２３】
１つ以上のより小さなデータグループまたは１つ以上のより大きなデータグループを放出するステップをさらに含む、請求項１に記載の方法。
【請求項２４】
第１のコンテンツ定義のデータチャンク化手順を適用して１つ以上の初期チャンク化ポイントを得ることと、
該初期チャンク化ポイントを異なるチャンク化ポイントに変更するように、事前に設定された基準の組に基づいて第２のコンテンツ定義のデータチャンク化手順を適用し、それによってデータチャンクの平均サイズ及び識別された重複データの平均量を増加させることと、
を含む、データ管理の方法。
【請求項２５】
前記第２のコンテンツ定義のデータチャンク化手順は、前記初期チャンク化ポイントによって定義されたデータチャンクを融合するチャンク結合手順を含む、請求項２４に記載の方法。
【請求項２６】
前記第２のコンテンツ定義のデータチャンク化手順は、前記初期チャンク化ポイントによって定義されたデータチャンクを分割するチャンク分割手順を含む、請求項２４に記載の方法。
【請求項２７】
非重複データと判定されたデータの長い広がり内の大きなチャンクに小さなチャンクを融合することと、
エッジ近傍で見つかった複数の小さなチャンクを融合しないことにより、重複データと判定されたデータ領域に隣接した、非重複データ領域と判定されたデータの長い広がり内のエッジを、小さなチャンクで境界をつけることと、
重複データであることが分かった大きなチャンクを再放出することと、
を含む、コンテンツ定義のチャンク化の方法。
【請求項２８】
データ識別システムと、
データ操作システムと、
を有し、前記データ操作システムは、データグループの平均サイズを増加させるように、事前に設定された基準の組に基づいて、１つ以上の初期のデータブレイクポイントを選択的に変更する、データ管理のシステム。
【請求項２９】
前記データ操作システムは、データグループの平均サイズを増加させる代わりに、識別された重複データの平均量を増加させるように、１つ以上の初期のブレイクポイントを選択的に変更する、請求項２８に記載のシステム。
【請求項３０】
前記データ操作システムは、既存のデータブロックを融合するデータブロック結合手順を適用することによって、前記初期のブレイクポイントを変更する、請求項２８に記載のシステム。
【請求項３１】
前記データ操作システムは、既存のデータブロックを分割するデータブロック分割手順を適用することによって、前記初期のブレイクポイントを変更する、請求項２８に記載のシステム。
【請求項３２】
データ識別を行う手段と、
データを操作する手段と、
を有し、前記データを操作する手段は、データグループの平均サイズを増加させるように、事前に設定された基準の組に基づいて、１つ以上の初期のデータブレイクポイントを選択的に変更する、データ管理のシステム。
【請求項３３】
前記データを操作する手段は、データグループの平均サイズを増加させる代わりに、識別された重複データの平均量を増加させるように、１つ以上の初期のブレイクポイントを選択的に変更する、請求項３２に記載のシステム。
【請求項３４】
前記データを操作する手段は、既存のデータブロックを融合するデータブロック結合手順を適用することによって、前記初期のブレイクポイントを変更する、請求項３２に記載のシステム。
【請求項３５】
前記データを操作する手段は、既存のデータブロックを分割するデータブロック分割手順を適用することによって、前記初期のブレイクポイントを変更する、請求項３４に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理(data processing)及びデータ管理(daga management)の分野に関し、より具体的には、データハッシュ化及び／またはデータ冗長性除去のような用途のための、効率的な処理に関する方法及びシステムに関する。
【背景技術】
【０００２】
毎日ますます多くの情報が世界中の至る所で作られ、保持され送信される情報の量は驚くべき速さで増え続けており、データ処理及びデータ管理に関する深刻な懸念を引き起こしている。これらの情報の大半は、電子的に生成され、処理され、保持され、送信され、記憶される。これらのデータ及びそれに関連したデータストリーム、及びそれらの記憶をすべて管理しようとする規模だけでも膨大なものになる。その結果、できるだけ多くの重複データを除去することにより、データをより効率的に処理し、より少ないデータを記憶し送信する多数のシステム及び方法が開発されている。例えば、コンピュータのような種々の電子機器、コンピュータネットワーク（例えばＬＡＮ、イントラネット、インターネットなど）、電話のようなモバイル機器、ＰＤＡ、ディスクドライブ、メモリチップなどにおいて、重複データを保存したり送信したりなどする必要性を低減することを支援する種々のシステム及び方法が開発されている。このような技術は、データ圧縮、データ暗号化、及び／またはデータ記憶のためであってもよく、またはそれらを含んでいてもよい。さらに、例えばデータ送信中は特に、暗号化技術を用いてデータを暗号化する必要がある。例えば、強い（すなわち、暗号）ハッシュ化(hashing)を提供するシステム及び方法が開発されており、このような方法は、セキュアでない通信チャネル上でのデータの冗長性の除去を達成するためにデータのハッシュ化を用いる用途に、ごく自然に組み込むことができる。セキュアなシステム上においても、データハッシュ化及び／またはデータ冗長性除去を提供するシステム及び方法が開発されている。アーカイブストリ−ムにおける重複データの識別及びデータ冗長性の除去は、記憶スペースを節約する１つの技法である。種々の電子データ管理方法及びシステムにおいて、データをハッシュ化するために、及び／または、例えば、データ保存（例えば、電子メールまたはホームディレクトリのバックアップデータの長期保管（アーカイブ））及びデータ送信から冗長なデータを除去するために、多くの方法が開発されてきた。これらの技術には、種々のデータ圧縮（例えば、ｚｉｐ技法）、データハッシュ化、及び、暗号化法が含まれる。
【０００３】
ハッシュ化のいくつかの特定の形態として、全ファイルハッシュ化、固定サイズチャンク化（ブロック化）、及びコンテンツ定義型のチャンク化(chunking)を含んでいてもよいコンテンツチャンク化が挙げられる。データストリーム管理及びデータ処理のいくつかの典型的な技術が、種々の論文に開示されている。それらの論文には、C. Policroniades and I. Pratt, "Alternatives for Detecting Redundancy in Storage Systems Data," in USENIX_04: Proceedings of the USENIX Annual Technical Conference, (2004), pp. 1-14（非特許文献１）；R. Jain, "A Comparison of Hashing Schemes for Address Lookup in Computer Networks," IEEE Transactions on Communications, 40, 1570(1992), pp. 1-5（非特許文献２）；N. Jain, M. Dahlin, and R. Tewari, "TAPER: Tiered Approach for Eliminating Redundancy in Replica Synchronization, Tech. Rep.," Technical Report TR-05-42, Dept. of Comp. Sc., Univ. of Texas at Austin, (2005), pp. 1-14（非特許文献３）；A. Chowdhury, O. Frieder, D. Grossman, and M. C. McCabe, "Collection Statistics for Fast Duplicate Document Detection," ACM Trans. Inf. Syst., 20, (2002), ISSN 1046-8188, pp. 171-191（非特許文献４）；F. Douglis and A. Iyengar, "Application-Specific Delta-encoding via resemblance Detection," Proceedings of the USENIX Annual Technical Conference (2003), pp. 1-23（非特許文献５）；P. Kulkarni, F. Douglis, J. LaVoie, and J. Tracey, "Redundancy Elimination Within Large Collections of Files," Proceedings of the USENIX Annual Technical Conference (2004), pp. 1-14（非特許文献６）；J. Barreto and P. Ferreira, "A Replicated File System for Resource Constrained Mobile Devices," Proceedings of IADIS International Conference on Applied Computing, (2004), pp. 1-9（非特許文献７）；T. Denehy and W. Hsu, "Duplicate Management for Reference Data," Technical report RJ 10305, IBM Research (2003), pp. 1-14（非特許文献８）；G. Forman, K. Eshghi, and S. Chiocchetti, "Finding Similar Files in Large Document Repositories," KDD '05: Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, ACM Press, New York, NY, USA, (2005), pp. 394-400（非特許文献９）；L. You, K. T. Pollack, and D. D. E. Long, "Deep Store: An Archival Storage System Architecture," ICDE '05: Proceedings of the 21st International Conference on Data Engineering, IEEE Computer Society, Washington, DC, USA, (2005), pp. 1-12（非特許文献１０）；K. Eshghi and H. K. Tang, "A Framework for Analyzing and Improving Content-Based Chunking Algorithms," Technical report HPL-2005-30R1, HP Laboratories (2005), pp. 1-10（非特許文献１１）；P. L'Ecuyer, "Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure," in Math. Comput., 68, 249(1999), ISSN 0025-5718, pp. 249-260（非特許文献１２）；A. Tridgell and P. MacKerras, "Technical report TRCS-96-05 - The Rsync Algorithm," Australian National University, Department of Computer Science, FEIT, ANU(1996), pp. 1-6（非特許文献１３）；及びL. You and C. Karamanolis, "Evaluation of Efficient Archival Storage Techniques," in Proceedings of 21st IEEE/NASA Goddard MSS (2004), pp. 1-6（非特許文献４）が含まれる。米国特許公開2006/0112264（特許文献１）、同2006/0047855（特許文献２）、同2005/0131939（特許文献３）、米国特許第6,658,423号（特許文献４）及び同第6,810,398号（特許文献５）を含む、関連する種々の典型的な技術を開示した多くの米国特許明細書及び米国特許公開公報もある。これらの参考文献には、より効率的なデータ処理及びデータ管理に関する種々の典型的な技術が示されている。
【０００４】
上述した種々の参考文献では、ｇｚｉｐ（ジージップ）、差分符号化(delta-encoding)、固定サイズブロック化(fixed-size blocking)、可変サイズチャンク化(variable-size chunking)、チャンク化と差分符号化との比較（差分符号化は、頻繁な小さな変化によって特徴付けられるログファイル及び電子メールのようなものに対して適した技術であろう）、及び、実データの固定サイズと可変サイズでのチャンク化の比較のようなオプションを紹介している。
【０００５】
しかしながら、これらの既知の技術にはある有用な能力が欠けている。通常、非常に用途の広いデータ圧縮またはハッシュ技法は、他の用途よりも特定の用途に対して（例えば、データ記憶及びバックアップよりもむしろ圧縮）、異なるデータ処理速度において、処理されるべきデータのサイズに対する異なるスケーリング特性によって、他のデータタイプよりもあるデータタイプに関して（例えば、短いデータブロック対長いデータブロック）、良好に機能する傾向がある。さらに、種々のハードウェア及びアプリケーションソフトウェアは、データ処理またはデータ管理技術がいかに良く機能できるかに対して影響を与える。例えば、以下に述べるように、データの短いブロック（例えば、３２ｋサイズのブロック）、またはおそらく中間サイズのデータブロックについては非常に良く機能するが、大規模データブロック（例えば、Ｇｂ（ギガバイト）サイズのブロック）についてはうまく機能しないデータ圧縮または冗長性除去技法もいくつかある。
【０００６】
残念ながら既知の技術は、通常は、特定の用途、アプリケーションまたはハードウェアに対するデータパターンを適切には考慮しないだけでなく、データセットまたはデータストリーム中の実際の高いデータ冗長度を識別しながら、処理中のデータセグメントのサイズを効率的に管理することもしない。重複除去の既知の手法には、達成される重複除去の程度、それに要した時間、及び／またはその手法のスケーラビリティ(scalability)に深刻な影響を与えることなく記憶または送信されるデータセグメントの平均サイズを増加させることにおいて、困難性がある。
【０００７】
したがって、高い冗長性除去を実現しつつ、妥当な性能を備えており、アーカイブデータ、バックアップデータ、及び／または大きなブロックまたはチャンク(chunk)でより効率的に送信または記憶されるデータにおいて使用された場合に特に効率的な、データ処理及び管理技術に対する必要性が存在する。重複除去に対する性能目標は、速度、大きな平均チャンクサイズと多量の重複除去との組み合わせ、及び／または超大規模データセットに対するスケーラビリティを含むであろう。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】米国特許公開第２００６／０１１２２６４号公報
【特許文献２】米国特許公開第２００６／００４７８５５号公報
【特許文献３】米国特許公開第２００５／０１３１９３９号公報
【特許文献４】米国特許第６，６５８，４２３号明細書
【特許文献５】米国特許第６，８１０，３９８号明細書
【非特許文献】
【０００９】
【非特許文献１】C. Policroniades and I. Pratt, "Alternatives for Detecting Redundancy in Storage Systems Data," in USENIX_04: Proceedings of the USENIX Annual Technical Conference, (2004), pp. 1-14
【非特許文献２】R. Jain, "A Comparison of Hashing Schemes for Address Lookup in Computer Networks," IEEE Transactions on Communications, 40, 1570(1992), pp. 1-5
【非特許文献３】N. Jain, M. Dahlin, and R. Tewari, "TAPER: Tiered Approach for Eliminating Redundancy in Replica Synchronization, Tech. Rep.," Technical Report TR-05-42, Dept. of Comp. Sc., Univ. of Texas at Austin, (2005), pp. 1-14
【非特許文献４】A. Chowdhury, O. Frieder, D. Grossman, and M. C. McCabe, "Collection Statistics for Fast Duplicate Document Detection," ACM Trans. Inf. Syst., 20, (2002), ISSN 1046-8188, pp. 171-191
【非特許文献５】F. Douglis and A. Iyengar, "Application-Specific Delta-encoding via resemblance Detection," Proceedings of the USENIX Annual Technical Conference (2003), pp. 1-23
【非特許文献６】P. Kulkarni, F. Douglis, J. LaVoie, and J. Tracey, "Redundancy Elimination Within Large Collections of Files," Proceedings of the USENIX Annual Technical Conference (2004), pp. 1-14
【非特許文献７】J. Barreto and P. Ferreira, "A Replicated File System for Resource Constrained Mobile Devices," Proceedings of IADIS International Conference on Applied Computing, (2004), pp. 1-9
【非特許文献８】T. Denehy and W. Hsu, "Duplicate Management for Reference Data," Technical report RJ 10305, IBM Research (2003), pp. 1-14
【非特許文献９】G. Forman, K. Eshghi, and S. Chiocchetti, "Finding Similar Files in Large Document Repositories," KDD '05: Proceeding of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, ACM Press, New York, NY, USA, (2005), pp. 394-400
【非特許文献１０】L. You, K. T. Pollack, and D. D. E. Long, "Deep Store: An Archival Storage System Architecture," ICDE '05: Proceedings of the 21st International Conference on Data Engineering, IEEE Computer Society, Washington, DC, USA, (2005), pp. 1-12
【非特許文献１１】K. Eshghi and H. K. Tang, "A Framework for Analyzing and Improving Content-Based Chunking Algorithms," Technical report HPL-2005-30R1, HP Laboratories (2005), pp. 1-10
【非特許文献１２】P. L'Ecuyer, "Tables of Linear Congruential Generators of Different Sizes and Good Lattice Structure," in Math. Comput., 68, 249(1999), ISSN 0025-5718, pp. 249-260
【非特許文献１３】A. Tridgell and P. MacKerras, "Technical report TRCS-96-05 - The Rsync Algorithm," Australian National University, Department of Computer Science, FEIT, ANU(1996), pp. 1-6
【非特許文献１４】L. You and C. Karamanolis, "Evaluation of Efficient Archival Storage Techniques," in Proceedings of 21st IEEE/NASA Goddard MSS (2004), pp. 1-6
【発明の概要】
【課題を解決するための手段】
【００１０】
本発明は、一般に、データ管理及びデータ処理のシステム及び方法を提供することを目的としている。例えば、種々の実施形態は、同等またはよりよい実行選択結果(performing selection results)（例えば高いデータ冗長性除去）によって選択された比較的大きなデータのグループ（群）に関連するシステム及び方法を含んでいてもよい。種々の実施形態において、システム及び方法は、例えばデータグループ、ブロックまたはチャンクを結合する技法、または／及びデータグループ、ブロックまたはチャンクを分割する技法を含んでいてもよい。種々の実施形態は、第１の標準的または典型的なデータグループ化、ブロック化またはチャンク化技法、及び／またはデータグループ、ブロックまたはチャンクの結合技法、または／及びデータグループ、ブロックまたはチャンクの分割技法を含んでいてもよい。実施形態は、先読みバッファ(look-ahead buffer)を含んでいてもよく、基礎となるデータの特性及び／または本発明の特定の用途（例えばバックアップ用）に基づいて、小さなチャンクを放出(emit)するか大きなチャンクを放出するかを判定することができる。さらに、例示的なシステム及び方法は、データセットまたはデータの列についてのデータハッシュ化、及び／または冗長性識別及び除去技法に関するものであってもよい。本発明は、データ処理結果の品質を著しく低下させることなく、データ処理を効率的に改善するソフトウェア及びハードウェアを含んだ、コンピュータに実装される発明であってもよい。
【００１１】
少なくとも１つの実施形態において、コンテンツ定義のチャンク化技法、関数または方法を最適化する種々の手段が、データストリームまたはデータセットのアーカイブまたはバックアップ用に提供されてもよい。種々の実施形態は、（上で言及した関連特許出願において記載されているような）複数の選択基準を用いて、チャンク化プロセスを促進する手段を含んでいてもよい。種々の実施形態は、出力データグループ、ブロックまたはチャンクの許容可能な最小及び最大の長さが与えられると、バックアップのカットポイント(cut point)、ブロックポイント(block point)またはチャンクポイント(chunk point)、及びカッティングレベル、ブレイクレベルまたはチャンクレベルを用いて、再現可能なカットポイント、ブロックポイントまたはチャンクポイントを生成する可能性を最大限にするやり方を含むこともできる。種々の実施形態は、いくつかの種類のアーカイブまたはバックアップデータにおける重複パターンの直観的なモデルに基づいていてもよい。種々の実施形態は、１つ以上のデータグループ、１つ以上のブロックまたは１つ以上のチャンクを再分配して、異なるパラメータ及び／または長さにしたがって改善されたカットポイント、ブロックポイントまたはチャンクポイントを決定するように、１つ以上のデータグループ、１つ以上のブロックまたは１つ以上のチャンクを融合すること(amalgamation)を含んでいてもよい。そのような実施形態は、重複除去率（ＤＥＲ；duplicate elimination ratio）を向上させ、賢明なヒューリスティクスによって平均チャンクサイズが著しくは低下しないようにできる可能性がある。種々の実施形態において、重複除去率（ＤＥＲ）を著しく低下させることなく、平均チャンクサイズを大きくできる可能性のあるリアルタイムシステム及び方法を提供することができる。
【００１２】
これらのシステム及び方法は、データグループを分割(splitting)または分解(breaking apart)することを含んでいてもよく、大きな平均チャンクサイズで「新しい」データの長いシーケンスを楽観的にチャンク化すること、及び、重複データである可能性のあるものに十分に近い「新しい」データに対し、より小さなチャンクを使用することを含んでいてもよい。このようなやり方で、いくつかの種類のバックアップデータを、より簡単に、局所的な変更に対応する角括弧挿入(bracket insertions)または削除領域(deletion regions)とすることができる。これを行うには、非常に限定された先読み(look-ahead)、先読みバッファの使用、及び／または、予想されるチャンクが以前に放出されていたかどうかを判定する、単位入力当たりの有限の数の問い合わせ（クエリ）を必要とするであろう。この問い合わせは、バックエンドの記憶装置に対して、及び／または、例えばブルーム(Bloom)フィルタのような実メモリまたは仮想メモリに保持されている有限サイズの局所履歴(local history)に対して、正確にまたは直接に行ってもよい。
【００１３】
本発明の種々の実施形態は、データグループ、ブロックまたはチャンクの平均サイズを大きくし、重複除去率を向上させる能力を実証している。さらに、種々の実施形態は、以前に取得可能であったデータグループ、データブロックまたはデータチャンクのほぼ２から４倍大きなデータグループ、データブロックまたはデータチャンクを用いて、ほぼ同等の重複除去率を達成することができた。これらのより大きなデータグループ、ブロックまたはチャンクは、データを保存するメタデータコスト(metadata cost)の低減を提供でき、その結果、他の装置、例えばバックアップ機器（例えば、ディスクまたはネットワーク記憶システム）にデータを送信し、及び／または、読み出しまたは書き込む際のスループット（処理能力）を向上させることができる。
【００１４】
当業者には、種々の実施形態に含まれるさらなる様相が、以下の開示の検討及びそれに添付された図面に基づいて、明白になるであろう。
【図面の簡単な説明】
【００１５】
【図１】少なくとも一実施形態における、入力ストリームの情報を識別し、出力を生成する前に時にはその情報を変更できる、データ管理システムの例示的な全体図である。
【図２】少なくとも一実施形態における、第１の選択関数を利用し、次に、ある既存のチャンクを融合及び／または分解できるコンテンツ定義のチャンク化ポリシーからなる第２の修正選択関数を利用する、データ識別プロセスの例示的な全体図である。
【図３ａ】少なくとも一実施形態における、非重複データの長い広がり(stretch)内の大きなチャンクに、複数の小さなチャンクを加え合わせまたは融合し、及び／または、その非重複データのエッジの小さなチャンクを融合しないで、そのような遷移領域内の潜在的な重複をよりよく識別することができる、例示的なコンテンツ定義のチャンク化技法またはポリシーを示すデータストリームである。
【図３ｂ】少なくとも一実施形態における、非重複データの長い広がり内の大きなチャンクに、複数の小さなチャンクを加え合わせまたは融合し、及び／または、その非重複データのエッジの小さなチャンクを融合しないで、そのような遷移領域内の潜在的な重複をよりよく識別することができる、例示的なコンテンツ定義のチャンク化技法またはポリシーを示すデータストリームである。
【図４ａ】少なくとも一実施形態における、より大きなチャンクを非重複データのエッジのより小さなチャンクに分解または分割し、そのような領域内の潜在的な重複をよりよく識別できる、例示的なコンテンツ定義のチャンク化技法またはポリシーを示すデータストリームである。
【図４ｂ】少なくとも一実施形態における、より大きなチャンクを非重複データのエッジのより小さなチャンクに分解または分割し、そのような領域内の潜在的な重複をよりよく識別できる、例示的なコンテンツ定義のチャンク化技法またはポリシーを示すデータストリームである。
【図５ａ】少なくとも一実施形態における、小さなチャンクを大きなチャンクに融合でき、及び／または、小さなチャンクによって非重複データのエッジに境界をつけることができ、及び／または、小さなチャンクを非重複データの短い領域内に残すことができる、例示的なコンテンツ定義のチャンク化技法またはポリシーのフローチャートである。
【図５ｂ】少なくとも一実施形態における、小さなチャンクを大きなチャンクに融合でき、及び／または、小さなチャンクによって非重複データのエッジに境界をつけることができ、及び／または、小さなチャンクを非重複データの短い領域内に残すことができる、例示的なコンテンツ定義のチャンク化技法またはポリシーのフローチャートである。
【図６ａ】少なくとも一実施形態における、データセットまたはデータ入力ストリームに対するコンテンツ定義のチャンク化融合技法またはポリシーの例示的な応用のタイミング図である。
【図６ｂ】少なくとも一実施形態における、データセットまたはデータ入力ストリームに対するコンテンツ定義のチャンク化融合技法またはポリシーの例示的な応用のタイミング図である。
【図６ｃ】少なくとも一実施形態における、データセットまたはデータ入力ストリームに対するコンテンツ定義のチャンク化融合技法またはポリシーの例示的な応用のタイミング図である。
【図７ａ】少なくとも一実施形態における、小さなチャンクの大きなチャンクへの融合を有する再同期を含んでいてもよい、例示的なコンテンツ定義のチャンク化技法またはポリシーのフローチャートである。
【図７ｂ】少なくとも一実施形態における、小さなチャンクの大きなチャンクへの融合を有する再同期を含んでいてもよい、例示的なコンテンツ定義のチャンク化技法またはポリシーのフローチャートである。
【図８】少なくとも一実施形態における、大きなチャンクを小さなチャンクに分割できる、例示的なコンテンツ定義のチャンク化技法またはポリシーのフローチャートである。
【図９ａ】少なくとも一実施形態における、データセットまたはデータ入力ストリームに対するコンテンツ定義のチャンク化分割技法またはポリシーの例示的な応用のタイミング図である。
【図９ｂ】少なくとも一実施形態における、データセットまたはデータ入力ストリームに対するコンテンツ定義のチャンク化分割技法またはポリシーの例示的な応用のタイミング図である。
【図９ｃ】少なくとも一実施形態における、データセットまたはデータ入力ストリームに対するコンテンツ定義のチャンク化分割技法またはポリシーの例示的な応用のタイミング図である。
【図１０】少なくとも一実施形態における、データ融合及び／またはデータ分割技法またはポリシーを適用できる、バックアップシステムの例示的な応用である。
【図１１】少なくとも一実施形態における、種々のチャンク化技法の圧縮因子対チャンクサイズの実験結果を示している。
【図１２】少なくとも一実施形態における、種々のチャンク化技法の圧縮因子対チャンクサイズの実験結果を示している。
【図１３】少なくとも一実施形態における、種々のチャンク化技法の分解による重複排除比対チャンクサイズの実験結果を示している。
【図１４】少なくとも一実施形態における、理論的なチャンクサイズ限界に対するＤＥＲ対チャンクサイズの実験結果を示している。
【図１５】少なくとも一実施形態における、コンピュータ装置の例示的な機能ブロック図である。
【図１６】少なくとも一実施形態における、ネットワークを示した例示的な機能ブロック図である。
【発明を実施するための形態】
【００１６】
本発明の有用性、目的、特徴及び利点は、添付の図面とともに考慮するとき、以下の本発明の実施形態の詳細な説明を検討することから、当業者に容易に認識、理解されよう。
【００１７】
改良されたデータ管理及びデータ処理のためのシステム及び方法をここで説明する。例えば本発明の種々の実施形態は、条件に合った(acceptable)、同等及び／またはより優れた実行選択、及び／または、冗長性除去の結果（例えば、高いデータ冗長性除去）によって選択された比較的大きなグループのデータに関連したシステム及び方法を含んでいてもよい。種々の実施形態において、システム及び方法は、例えば、データグループ、ブロックまたはチャンクの結合技法、または／及びデータグループ、ブロックまたはチャンクの分割技法を含んでいてもよい。本発明は、種々の形態のデータ処理、データ送信、及び／またはデータ記憶に適用することができ、本発明の特に有用な用途として、ファイル同期、バックアップデータ記憶（ストレージ）等のみならず、例えば、いくつかの形態のネットワークファイルシステム、収集した参考ファイルの集合の空間最適化アーカイブも挙げることができる。以下の種々の実施形態は、１つの特に例示的な用途として、バックアップデータ記憶を本発明の使用例としている。本発明は、データ処理及びデータ保守をより効率的に向上させるソフトウェアとハードウェアとを含んだ、コンピュータに実装される発明であってもよく、データ処理結果の性能を著しく低下させない。以下により詳細に説明するように、コンピュータによる実装は、種々の電子装置（例えば、ＰＤＡ、携帯電話、ＧＰＳ等）、コンピュータ（例えば、ＰＣ）、記憶装置またはシステム、及び／またはコンピュータネットワーク（ＬＡＮ、イントラネット、インターネット等）を含んでいてもよい。
【００１８】
通常、圧縮アルゴリズムは、データの短いブロックの特性に適合している。例えば、文脈自由文法は、バイト(byte)または英単語として見た場合、通常、長いシーケンスを含んだ生成がますます少なくなることが理解することができる。合理的な圧縮は、ローカルデータモデルまたは辞書ベースのルックアップ(lookup)技法を含む機構によって達成することができる。例えば、ｇｚｉｐは、短いブロック（例えば、３２ｋ）上で動作して、繰り返し文字列を書式のポインタ（距離，長さ）と置き換える。この場合、ｇｚｉｐは、局所スコープにおいて冗長性除去を行うが、長さを極めて短くできる冗長な文字列を使用してこれを行う。
【００１９】
アーカイブデータでは、状況は全く異なる。実ファイルシステムにおいては、大半のファイルアクセスが読み取り専用であり、ファイルはほぼ読み取り専用(read-mostly)またはほぼ書き込み専用(write-mostly)のいずれかである傾向があり、小さなファイル群が大半のブロック上書きを発生する。全ファイルが重複していてもよく、変更された場合にも、その変更は、比較的小さな編集領域に局在化することができる。ここで、圧縮方式（圧縮スキーム）は、長い繰り返しのデータセグメントをより効果的に処理する必要がある。さらに制約することに、データが再発生する「将来(future)」は、数ギガバイト先に（すなわち、次のバックアップ実行時）にあるであろう。この場合、はるかに広い入力データ領域を超えた、大域スコープでの重複識別及び冗長性除去が目標にされてもよい。これらの冗長な文字列の「位置」の保存に関連付けられた付加的なオーバーヘッドがあるので、興味の対象であるチャンクは、例えば、ｇｚｉｐのようなデータ圧縮技術によって目標とされるチャンクよりもはるかに大きい。
【００２０】
アーカイブデータに対する基本的な仮定は非常に異なっているので、辞書ベースの圧縮技術は、重複除去（ＤＥ；duplicate elimination）と呼ばれる手順を用いてもよい。重複除去では、入力データストリームを単順に再生可能に分解し、次に、以前に放出されたチャンクと重複するいかなるチャンクのただ１つのコピーのみを保存する（または送信する）。
【００２１】
重複除去は、相当な付加の作業を行って圧縮率を改善する、より積極的（アグレッシブ）な技術とは区別することができる。より積極的な圧縮方式においてよく用いられる技術は、類似検出及びある形態の差分符号化を起動することである。残念なことに、大きな（ギガバイト）の集合の中で、最大限に長い重複を見つけること、または類似の（または同一の）ファイルを見つけることは、通常の場合には、特殊なアルゴリズムを含んだ非常に複雑で非自明なタスクである（例えば米国特許第６，６５８，４２３号明細書を参照）。
【００２２】
種々の実施形態は、データグループ化、ブロック化またはチャンク化の技法、及び／またはデータグループ、ブロックまたはチャンクの結合技法、または／及びデータグループ、ブロックまたはチャンクの分割技法を含んでいてもよい。種々の実施形態において、データグループ化、ブロック化またはチャンク化技法は、標準的または典型的なデータグループ化、ブロック化またはチャンク化の手法を利用してもよい。実施形態は、先読みバッファを含み、基礎となるデータの特性及び／または本発明の特定の用途（例えばバックアップ用）に基づいて、小さなチャンクを放出すべきかまたは大きなチャンクを放出すべきかを判定することができる。さらに、例示的なシステム及び方法は、データセットまたはデータの列についてのデータハッシュ化、及び／または冗長性識別及び除去技法に関するものであってもよい。いくつかの例示的な実施形態において、本発明を、データアーカイブ及び／またはデータバックアップに適用されるものとして説明し、その用途において特に良好に機能するように構成する。
【００２３】
少なくとも１つの実施形態において、コンテンツ定義のチャンク化技法、関数または方法を最適化する種々の手段が、データストリームまたはデータセットのアーカイブまたはバックアップ用に提供されてもよい。種々の実施形態は、（例えば上で言及した関連特許出願において記載されているような）複数の選択基準を用いて、チャンク化プロセスを促進する手段を含んでいてもよい。種々の実施形態は、出力データグループ、ブロックまたはチャンクの許容可能な最小及び最大の長さが与えられると、バックアップのカットポイント、ブレイクポイントまたはチャンクポイント、及びカッティングレベル、ブレイクレベルまたはチャンクレベルを用いて、再現可能なカットポイント、ブロックポイントまたはチャンクポイントを生成する可能性を最大限にするやり方を含むこともできる。このようなカットポイント、ブレイクポイントまたはチャンクポイントは、優れた重複検出能力を有すると期待される形態で生成されてもよい。種々の実施形態は、何らかの形態のアーカイブまたはバックアップデータで発生する可能性のある重複パターンの、直観的な、測定された及び／または動的なモデルに基づくものであってもよい。
【００２４】
種々の実施形態において、重複除去率（ＤＥＲ）を著しく低下させることなく平均チャンクサイズを大きくできる可能性を有する、リアルタイムのデータ処理及び／またはデータ管理システム及び方法を提供することができる。アーカイブまたはバックアップデータに本発明を適用することを考えた場合、新鮮なすなわち新しいデータに対する１つの仮定は、それが将来のバックアップ実行時に再発生する高い可能性を有しているということであろう。その場合、大きなデータグループ、ブロックまたはチャンクの使用は非常に効率的であることが分かる。したがって、本発明のシステム及び方法は、大きな平均を有するチャンクによって、新鮮なすなわち「新しい」データの長いシーケンスを楽観的にチャンク化することを含んでいてもよい。これは、重複データの可能性のあるものに十分に近い「新しい」データに対し、より小さなチャンクを使用することと組み合わされてもよい。このようにして、いくつかの種類のバックアップデータを、より簡単に、局所的な変更に対応する角括弧挿入または削除領域とすることができる。これを行うには、非常に限定された先読み、先読みバッファの使用、及び、予想されるチャンクが以前に放出されていたかどうか判定する、単位入力当たりの有限の数の問い合わせを必要とするであろう。この問い合わせは、バックエンドの記憶装置に対して、または例えばブルームフィルタのような実メモリまたは仮想メモリに保持されている有限サイズの局所履歴に対して、正確にまたは直接に行ってもよい。本発明の種々の実施形態は、データグループ、ブロックまたはチャンクの平均サイズを大きくし、条件に合った（または、改善さえされた）重複除去率を維持する能力を実証している。さらに、種々の実施形態は、以前に取得可能であったデータグループ、データブロックまたはデータチャンクのほぼ２から４倍大きなデータグループ、データブロックまたはデータチャンクを用いて、ほぼ同等の重複除去率を達成することができた。これらのより大きなデータグループ、ブロック、またはチャンクは、データを保存するメタデータコストの低減をもたらすことができ、その結果、他の装置、例えばバックアップ機器（例えば、ディスク記憶システム）にデータを送信、及び／または読み出し、または書き込む際のスループットを向上させることができる。
【００２５】
本発明は、データ処理結果の質を著しく低減することなくデータ処理効率を改善する、ソフトウェアとハードウェアとを有するコンピュータで実装される発明であってもよい。少なくとも一実施形態において、ここで与えられているシステム及び方法は、コンピュータ装置を使用して実現することができ、ネットワーク内の１つ以上のコンピュータ上で動作可能であってよい。例示的なコンピュータ装置及びネットワークの詳細を、図１９及び図２０を参照して本明細書において後で詳細に説明する。それらの例に対する先立つ参照は、本発明の種々の詳細に対するより良い理解を深めるのに有用であることが理解されるであろう。
【００２６】
いずれにしても、理解を容易にするために、ハッシュ関数(hashing function)、及び／またはデータ冗長性識別、及び／またはデータ重複除去ともに使用することについて、本発明をより詳細に説明する。しかしながら、処理または保存すべきデータ列を有するコンピュータ、送信すべきデータを有する無線通信、インターネット及びイントラネットでの応用、データの暗号化技術等を含む、他のデータ管理及び処理システム及び方法に本発明を適用可能であることを、当業者は理解するであろう。特に、本発明を説明するためにここで使用する例示的な実施形態は、主として、データハッシュ化及びデータ重複除去に関連している。
【００２７】
ファイル全体のハッシュ化の場合、ハッシュ化は、ファイル全体のすべてのデータにハッシュ関数を適用することにより行うことができる。例えば、ＳＨＡ−１ハッシュ関数をデータファイル全体に使用及び適用することができる。ＳＨＡ−１ハッシュ関数は、計算量的に複雑であって、他のいくつかのハッシュ関数と比較すると低速である。とにかく、この場合、重複を識別して除去するために、最小の量のデータ重複が見つけられて除去される。というのは、たった１ビットのデータでもファイル中で変化した場合、結果として生じるハッシュ値は以前に保存されたハッシュ値と異なった値になり、改訂されたファイルに関連付けられたデータの全量が送信または保存される必要があるからである（例えば、テキストファイル中の１つの文字が変更されると、テキストファイルの全データ表現及びそのハッシュ値は、それらは同じテキストファイルの前バージョンと重複しないように変化する）。一方、ハッシュ関数はデータファイルの全体について一回だけ動作すればよいので、ハッシュ化は迅速である。
【００２８】
固定サイズのデータブロックハッシュ関数は、ファイル全体で見出される全データの一部分またはブロックについてハッシュ化を行うことができ（例えば、単一のテキストファイルは、１０ｋビットの同一サイズの１０個のデータブロックに分解されてもよい）、データブロックは、重なり合わない固定サイズに設定されてもよい。種々の目的のために、ブロック化またはチャンク化の速度は興味の対象である。最も簡単で最も高速の手法は、固定サイズのチャンクに入力ストリームを分解することである。この手法は、いくつかのｒｓｙｎｃファイルの同期化技法に取り入れることができる。しかしながら、固定サイズのチャンク化を用いる場合、潜在的な再同期化問題がある。すなわち、挿入または除去の編集がファイルの先頭付近で行われた場合に何が起こるか考えてみると、単一のチャンクが変更された後、それに引き続くチャンク化の全体が変更される。ファイルの新しいバージョンには、おそらく重複チャンクがほとんどないであろう。再び、固定サイズのブロックについて、ＳＨＡ−１ハッシュ関数は、ファイル全体（例えば１００ｋビット）を構成する固定サイズ（例えば、１０ｋビット）のブロック群の各々に適用されるであろう。この場合、各回でハッシュ化されるデータのブロックがより小さくなるので、より多くの重複が見つけられ可能性があるが、ファイル全体のどこかでおきる単一ビットの変化は、ファイル全体を構成する複数のブロックのうちの１つにおける変化になるだけである（例えば、１０個の１０ｋビットのブロックのうちの９個は重複しているであろう）。ブロックが小さくなればなるほど、冗長性検出はより良くなるが、ハッシュ関数、例えばＳＨＡ−１が、データファイル全体で見出される同じ量のデータに対し、より多くの回数実行されなければならないので、結果的にわずかに遅いプロセスとなる。
【００２９】
再同期化問題を回避する１つの方法は、ローカルウィンドウ（例えば、長さ１２〜４８バイト）を使用して、データストリームを可変サイズのチャンクに再生可能な方法で分離できる、コンテンツ定義のチャンク化（ＣＤＣ；content-defined chunking）技術を使用することである。このようなチャンク化は、ランダムデータの入力が与えられたとして、平均出力チャンクサイズすなわちチャンク生成の平均速度を制御するという意味で、確率的である。ＣＤＣは、局所化された編集からの変化を限られた数のチャンクにより良く抑制できる可変サイズのチャンクを生成する。ＣＤＣの用途として、いくつかの形態のネットワークファイルシステム、収集された参照ファイルの集合の空間最適化アーカイブ、及びファイル同期を挙げることができる。低帯域幅ファイルシステム（ＬＢＦＳ；Low-Bandwidth File System）は、広く使用される技術としてＣＤＣを確立することに影響を与えるものであった。一般に、基本的なチャンク化アルゴリズムは、典型的には、最小及び最大チャンクサイズについての制限によって拡張されるだけである。いくつかの事例では、最大チャンクサイズに到達すると、または補助的な特別なデータのシーケンスが入力データストリーム内で見つかると、より複雑な決定を下すことができる。
【００３０】
コンテンツ定義のデータチャンクハッシュ化は、極めて低速ではあるが多少優れた性能（例えば、より正確で識別力のある）計算を適用して、それらのコンテンツで定義される種々のデータチャンクの識別、生成することによって、行うことができる。このようなハッシュ関数の１つは、ラビン(Rabin)のフィンガープリント法(fingerprinting)とＳＨＡ−１ハッシュ関数との組み合わせを含んでいてもよい。データファイル中のデータの重なりあうデータウィンドウ（例えば、スライディングウィンドウ）に対してラビンのフィンガープリント法を複数回適用して、データファイルのどこにチャンク境界を設定するべきかを、所定の境界点基準（例えば、０であるフィンガープリントの所定のビット集合）に基づいて決定し、その後、決定したデータブロックの各々（そのサイズは、基礎となるデータのうちの解析されるものに応じて変化する）に対してＳＨＡ−１ハッシュ関数を適用してもよい。また、前述したように、入力の各バイトをあるＳＨＡ−１ハッシュ計算に入れてもよい。しかしながら、ラビンのフィンガープリント法は、固定サイズのチャンク化と比較した場合、追加の計算負担（例えば、処理時間）を提起する。この手法は、さらに多くのデータ冗長性を識別するのに極めて優れているが、上記の関数はともに多大な計算時間を要し、両者を組み合わせた場合、ハッシュ化及び／またはデータ冗長性識別及び除去は、多大な計算時間を要するものになる。事実、ラビンのフィンガープリント関数は、冗長性データ識別及び／またはデータ除去を最適化しようとする際に、特に、各種のデータブロックのカットポイントまたはハッシュポイントがどこにあるべきかを識別するのに特別に計算時間を要する。
【００３１】
データのアーカイブまたはバックアップに関する種々の実施形態において、基本的なチャンク化技法を用いることで最大のブロックまたはチャンクサイズに到達する場合、バックアップのカットポイント、チャンクポイントまたはブレイクポイントについての優先順位が付けられた階層を使用することもできる。この技法は、局所化された編集を含んだ入力ストリームを再同期化できる可能性の増加を望むことよって、動機付けられてもよい。この技法は、チャンクの結合または融合技法、またはのチャンク分割または分解技法によって拡張することができる。このような手法は、ランダムデータ入力をチャンク化する統計量を考慮することにより、従来のシステム及び方法を著しく改善して、効果的に使用できることをここで説明する。基本的なチャンク化技法は、最小及び最大のチャンク長によりパラメータ化された、コンテンツ定義のチャンク化スキームを用いて動作することができ、おそらくバックアップのカットポイント、チャンクポイントまたはブレイクポイントの概念を含んでいてもよく、ここで「ベースライン」重複除去技法または関数と呼ばれている。
【００３２】
重複除去（ＤＥ）の１つの利点は、多くのファイルシステムのような入力について、再生成されたコンテンツの大半を認識できる点にある。ある圧縮関連という意味において最適な、重複領域を能動的に探索することと比較した場合、重複除去の非効率性は、主として、新しいデータと古いデータとの間の境界にまたがるデータグループ、ブロックまたはチャンクで生じる。そのため、データグループ、ブロックまたはチャンクのサイズが小さくなるにつれて、一般に、重複除去の効率は向上する。しかしながら、この結果、（より多くのメタデータ、より長い検索及び再アセンブリ時間など、）チャンク（グループまたはブロック）当たりの記憶（ストレージ）コストが増加する可能性がある。
【００３３】
重複除去率（ＤＥＲ）は、入力されたバイト／記憶されたバイト（すなわち、データの単位としてバイトを使用した、入力されたデータ／記憶されたデータ）の比率として定義することができる。データアーカイブの用途を考えた場合、現行のデータアーカイブシステムは約５から２０のＤＥＲを得ることができる。１つの考察は、ＤＥのために、チャンク当たりのメタデータが、所望のデータグループ、ブロックまたはチャンクサイズにどのような影響を及ぼすだろうかということである。例えば、データグループ、ブロックまたはチャンク当たり１００バイトのオーバーヘッドがあり、そのデータグループ、ブロックまたはチャンクがどこに及びどのように保存されるであろうかを示しているものとする。そのようなシステムが、例えば５０の最大ＤＥＲをサポートすべき場合、平均データグループ、ブロックまたはチャンクサイズは、少なくとも５０×１００＝５０００バイトとなるべきである（このデータグループ、ブロックまたはチャンクサイズにおいて、１つの重複を追加は、さらに１００バイトのコストを必要とする）。
【００３４】
チャンク当たりのコストが高い場合、より大きなデータグループ、ブロックまたはチャンクサイズを生成することの誘因となるかもしれない。このため、典型的な重複除去手法は、例えば、２ｋ〜１６ｋの範囲にあるデータグループ、ブロックまたはチャンクサイズを使用し、短い文字列レベルでの冗長性を明確には除去しようとしない。個々のチャンクに高速の「局所」圧縮スキームを使用することにより、限られた程度にまでこのような冗長性を除去することができる。より大きな平均的サイズのデータグループ、ブロックまたはチャンクを用いることができる場合には、チャンク（グループまたはブロック）当たりの圧縮効率は再度向上させることができるであろう。しかしながら留意に値することは、この特別な利点が、重複除去によって節約されたデータ記憶空間量と比較してそれほど重要でないことである。というのは、重複除去による利益は、チャンクが発生するたびに発生する（典型的なデータに対して５〜２０回）が、上記の利点は保存されたチャンク当たり１回しか発生しないからである。
【００３５】
本発明の１つの目的は、従来の（「ベースライン」）重複除去手法に比較して、ＤＥＲを向上させ、及び／または平均のデータグループ、ブロックまたはチャンクサイズを大きくすることができる、改善された重複除去方式を見い出すことである。本発明の種々の用途には、その用途のデータセットまたはデータストリームに独特な態様または特性に応じて、本発明の特定の関数の開発が必要である。例えば、次の２つの主要な原理をアーカイブまたはバックアップデータのストリームの処理及び管理を改善することに適用することができる：
原理１：新しいすなわちまだ見たことがない長い一続きのデータは、後で（例えば、次のバックアップの実行時に）現われる良い候補であると推定できる；
原理２：重複データと新しい（まだ見たことがない）データとの間の境界にまたがる「変化領域(change regions)」周辺に発生する非効率性は、より短いチャンクによって最小化できる。
【００３６】
この場合、原理１は、アーカイブまたはバックアップデータのＤＥＲが、「典型的な」アーカイブまたはバックアップデータ（例えば、ホームディレクトリ、電子メール等）に対して、５〜２０の範囲内にあることが多いという事実により正当化できる。一方、原理１は、高いロールオーバー(rollover)のコンテンツを有するシステム、または頻出する非重複のマーカが挿入されたコンテンツデータストリームに対しては、実際には正当化できないかもしれない。原理１は、特に、新しいすなわちまだ見たことがないデータの拡張領域中にある場合に、平均サイズが大きなデータグループ、ブロックまたはチャンクを生成できるデータグループ化、ブロック化またはチャンク化技法または手順の使用をサポートする。
【００３７】
ベースライン技術または手順の多くの変形が原理２から生じてもよい。すなわちその変形は、変化領域がどのように識別されるか、及び変化領域内の新しいすなわちまだ見たことがないデータのどのくらいが、より細かい粒度でグループ化、ブロック化またはチャンク化されるか、という点において主として異なっている。１つの手法は、平均して大量のデータを含んだデータグループ、ブロックまたはチャンクにまず全てをグループ化、ブロック化またはチャンク化することができる初期の技術から始めるものであってもよい。次に、重複データ及び非重複データを含んだブロックが識別され、これらのブロックのサブセットが選択されてもよい。次に、この選択されたサブセットは分解または分割技術を用いて、より細かいレベルで、識別されたデータの領域に再チャンク化できる。この手法の１つの利点は、重複チャンクに対する問い合わせがほとんど必要ないことであろう。しかしながらこのような手法では、小さな挿入／変更が大きなチャンク全体を無効にする可能性がある。重複除去率（ＤＥＲ）の性能が問い合わせ数を最小化することよりも重要な場合、次のパラグラフで説明する融合手順がより優れた選択肢となろう。大きなチャンクを配置できる場所について、より高い柔軟性を与えることにより、いくぶん良好なＤＥＲが取得可能になる。
【００３８】
多少はより柔軟な手法であるものにおいては、初期に細かいレベルでチャンク化することができ、小さなチャンクを結合して大きなチャンクにすることができるデータの構築(building-up)または融合の技法または手順が好ましいであろう。このような手法は、どのように大きなチャンクを形成するかの可能性の数を増やすことをできるようにすることにより、さらに柔軟になるであろう。構築または融合によるグループ化、ブロック化またはチャンク化の技法は、単一の挿入された／変更されたチャンクをより細かくひとまとめにすることができ、後で再利用することができる。しかしながら上述したように、大きなデータグループ、ブロックまたはチャンクをどのように構築するかについて、より多くの変形または可能性を与えることは、異なる期待された大きなサイズのグループ、ブロックまたはチャンクが重複であるかどうかを判定する問い合わせの数が増加するというコストを伴うであろう。いくつかの変形は、データのグループ化、ブロック化またはチャンク化の決定をする前に必要な問い合わせの数を制限することにより、異なっていてもよい。
【００３９】
一般に、より大きなデータグループ、ブロックまたはチャンク（例えば、データグループ、ブロックまたはチャンク当たりのより大量のデータ）を作成すること、及び変化領域をひとまとめにすることに対して利用可能な柔軟性が大きなほど、技術または手順の性能は、ＤＥＲを向上させると同時にデータグループ、ブロックまたはチャンクサイズを大きくする点において、より良好になる。例えばデータアーカイブ設定におけるこれらの技法の正確な挙動は、頻度の分布、重複領域の長さ、及び１つのバックアップシーケンスまたはセッションから次のバックアップシーケンスまたはセッションへの挿入または変更「編集」の平均サイズに依存する。
【００４０】
本発明の種々の実施形態は、特に、記憶されるべきデータ量またはファイル数を伴う実施形態に関して、高速かつスケーラブルである。これらの要件が緩和されると、本発明の種々のデータブロック化技法をより複雑な手法と組み合わせることができる。例えば、種々の実施形態は、大きなチャンクがどの特定のサブチャンクを含んでいるかについての情報を保存すること、データストリームを保存し再構成するためのより複雑な圧縮スタイルのレシピを生み出すこと、を含むこともできる。さらに、本発明のデータグループ化、ブロック化及びチャンク化の技法または関数は、類似検出及び差分圧縮のようなより壮大な技法と組み合わすこともできる。しかしながら、「類似の(similar)」ファイルまたはチャンクを能動的に見つけ出すことに基づいた種々の手法は、保存されたチャンクの数とともに線型的あるいはそれより悪く規模が大きくなる傾向にあるので、それほど汎用的ではない。より優れた手法は、上述の簡単な原理１及び原理２によって主に支配される、一定の時間で動作可能な多少「受動的な(passive)」技法を用いることであろう。というのは、それらの技法は、最終的なデータグループ化、ブロック化またはチャンク化の決定をするために、限られた数のデータグループ、ブロックまたはチャンクの存在問い合わせしか必要としないからである。データアーカイブ及びバックアップ用途の使用について、本発明は、例えば３２ｋの平均データグループ、ブロックまたはチャンクサイズの目標値を使用してもよい。この目標値は、読み出し／書き込みの速度要件とメタデータ記憶コストとの組み合わせの望ましいレベルを得るのに有用である（より大きなチャンクはこれらの目標の達成を助ける）。しかしながら、平均４ｋ〜８ｋしかないチャンクサイズを典型的に使用する既存の重複除去スキームと同等のＤＥレベルを達成することも望ましい。
【００４１】
本発明は、ローリングウィンドウのカットポイント、ブレイクポイントまたはチャンクポイントの選択のための複数の選択基準技法を含んでいてもよい。一般に、コンテンツ定義のチャンク化は、所定の位置群を選択して入力ストリームを分解することによって動作する。チャンク化の決定（カットポイントの決定）がローカルウィンドウ内に含まれるデータに基づいている場合、そのチャンク化はコンテンツ定義である。典型的な目標は、カットポイントを生成するウィンドウ群が十分にランダムな場合、チャンクサイズ分布が、実データ入力に対して、なおランダム入力の統計的期待値に類似していることである。（本件と同日に出願され、参照することによってここで援用される"METHODS AND SYSTEMS FOR DATA MANAGEMENT USING MULTIPLE SELECTION CRITERIA"と題するCezary Dubnicki, Erik Kruus, Cristian Ungureanu, and Krzysztof Lichotaによる関連特許出願に記載されているように）高速なカットポイント決定とカットポイントの合理的で優れた実行との両方を達成するために、第１の高速選択関数(fast selection function)、例えばボックスカー和(boxcar sum)、及び第２のより遅い選択処理、例えばＣＲＣ３２ｃまたはＳＨＡ−１を用いて、初期のカットポイント群を決定してもよい。
【００４２】
２段階のカットポイント、ブレイクポイントまたはブロックポイントの選択処理を選択して、ボックスカー和の速度を引き上げることもできる。まず、かなり寛大な選択は、高速のボックスカー和を用いて潜在的なカットポイント、ブレイクテポイントまたはブロックポイントの群を生成することによって行うことができる。この群から、第２の（より遅い）ハッシュ関数を用いて、最終的なカットポイント、ブレイクポイントまたはブロックポイントを選択してもよい。これらの「組み合わせ(combined)」チャンク関数は、ほとんどの入力ウィンドウに対して、（典型的にはメモリのバンド幅が限定された）ボックスカーハッシュの速度で動作し、より遅いハッシュ関数によって時々評価される必要があるのみである。第２のハッシュ関数はロールされる必要はないので、速度にほとんど影響を与えずに、任意のハッシュ関数を使用することができる。種々の実施形態において、初期の選択に対するより高速のボックスカー関数（例えばハッシュ関数）と、それに引き続き、最終的な選択に対するより遅いＣＲＣ３２ｃまたはＳＨＡ−１関数（例えばハッシュ関数）を組み合わせることは有益であろう。可能性のあるチャンク化のカットポイント、ブロックポイント、ハッシュポイントまたはブレイクポイントは、ハッシュ値の最下位（桁）のゼロビットの数を調べることにより決定することができる。このゼロビットの数がｌであった場合、このウィンドウはレベルｌでカットポイントを生成すると言える。種々の例示的なカットポイント、ブロックポイント、ハッシュポイント、ブロックポイントの関数の表が、シミュレーション中に達成された種々の速度を示した表１で説明されている。
【００４３】
【表１】
2010515114.tif 000003
いくつかの簡単なハッシュ関数を上記の表１に示している。ハッシュ(hash)には一定の初期値が割り当てられる。ウィンドウ中の各バイトに対し、ハッシュは次のバイト値ｂをく加えることにより変更される。ここで挙げたハッシュ関数には、高速のローリング(rolling)バージョンがある。ここで、ＡとＮはハッシュ固有の定数であり、ＲＯＬは左回転演算である。ｘアドラーハッシュ(xAdler hash)は、アドラー（／フレッチャー）(Adler(/Fletcher))ハッシュの簡略版である。速度値は、最大量のコンパイル時間定数を有する適正に最適化されたコードの代表値であり、ハッシュ関数の速度の合理的な表示を与える。速度試験は、ハッシュをロールして、数百メガバイトのメモリ内(in-memory)ランダムデータの末端のゼロビットをチェックして測定する。
【００４４】
種々の実施形態において、このシステム及び方法は、複数のバックアップのカットポイント、ブロックポイント、ハッシュポイントまたはブレイクポイントを生成し維持することを含んでいてもよい。任意のローリングハッシュアルゴリズムに対して共通に設定されるパラメータは、最小チャンクサイズｍ、最大チャンクサイズＭ、チャンク化「レベル」ｌ及びバックアップのカットポイントの数ｂである。ランダム入力データについては、レベルｌで切断(cut)する任意のウィンドウチェックサムが、
【００４５】
【数１】
2010515114.tif 000004
の平均チャンクサイズを生成するべきである。期待される平均のデータチャンクサイズは、ランダム入力データを含む入力ストリームで表した場合、チャンク化の境界を選択する統計的な期待率である。チャンクサイズｓに対する統計的期待値は、平均値
【００４６】
【数２】
2010515114.tif 000005
を有する指数分布に従うべきである。
【００４７】
【数３】
2010515114.tif 000006
Ｓバイトの入力バイトの任意のシーケンスにおいて、ちょうどｋ個のカットポイントを見る確率はポアソン分布に従うべきである。
【００４８】
【数４】
2010515114.tif 000007
領域Ｓ内にちょうど１個のカットポイント（ｋ＝１）を有する確率は、
【００４９】
【数５】
2010515114.tif 000008
のときに最大になる。最小チャンクサイズｍに対して、平均チャンクサイズは約
【００５０】
【数６】
2010515114.tif 000009
であるべきである。最大チャンクサイズＭに対して、普通のレベルｌのチャンカーは、確率
【００５１】
【数７】
2010515114.tif 000010
で最大に達する。指数分布はかなり長い裾を引いた部分を有している。関数が、
【００５２】
【数８】
2010515114.tif 000011
という型で演算している場合、その関数は、ｅ-1〜３７％までの最大サイズのチャンクを生成することができる。これはかなり大きな割合のチャンクであり、この場合、代替のカットポイントを選択することができるであろう。容易に維持可能な代替は、レベルｌ−１（等）で発生する可能性のある任意のカットポイントである。この第１のバックアップレベルにおいて、平均チャンクサイズ
【００５３】
【数９】
2010515114.tif 000012
により、０個のカットポイントを持つ可能性は少ない（≒１０％）。このレベルにカットポイントがある場合、それは明らかに、Ｍ番目のデータバイトでの任意の切断よりも、例えば２つの入力ストリームを再同期化するより良い機会を与える。カットポイントに対する少しのバックアップレベルを維持することにより、一意的なカットポイントを持たない確率を下げることができる。しばしば、３つのバックアップのカットポイントがここで説明した種々の実験で使用され、これらは実際的な選択であろう。いくつかのバックアップのカットポイント、ブロックポイント、ハッシュポイント、ブレイクポイントを１つのレベルで持つことは、最も早いまたは最も遅いそのようなポイントで切断する選択を可能にする。重複除去のためには、典型的には、最も早いカットポイントでの切断が最良の再同期化を与えることができる。後のカットポイントでの切断は、スラックを増加させるという犠牲を払って、チャンクサイズを最大限に大きくする（例えば、米国特許公開第２００６／００４７８５５号を参照）。ここで提示した種々の実験データにおいて、バックアップの切断、ブロックまたはハッシュポイントを選択して、最長で最大のブロックまたはチャンクを生じさせることができる。ここで図面を参照して、本発明の種々の実施形態のより詳細な説明を与える。
【００５４】
図１は、本発明の少なくとも一実施形態による、入力ストリームの情報を識別でき、出力を生成する前にその情報を時には変更できる、データ管理システム１００の例示的な概略図を示している。入力データストリーム１１０が与えられる。入力データストリーム１１０は、データストリームまたはデータセットであってもよく、例えばデータの１または２以上の電子ビット及び／またはバイトで構成されていてもよい。データストリーム１１０は、任意の数のまたは任意の種類の装置またはソース（例えば、ＰＣ上で動作するコンピュータプログラム、ＬＡＮ、インターネット、記憶ディスク、携帯型無線装置、マイクロプロセッサ出力、メモリチップ、メモリスティック、受信された送信等）の１つ以上からもたらされることができる。データ識別システム１２０は、電子情報の種々のビット及び／またはバイトを識別することができ、使用のために、（１つ以上の電子装置に含まれていてもよい）種々のメモリ、バッファ等にそれらのビット及び／またはバイトを保存することができる。データ識別システムは、種々のブレイクポイント、ブロックポイント、チャンクポイントまたはハッシュポイントを決定する関数も含むことができる。このデータ及び情報はデータ操作システム１３０によって使用されてもよい。種々の実施形態において、データ操作システム１３０は、データハッシュ関数、重複除去関数、ハッシュテーブル、圧縮関数等を含んでいてもよく、電子及び／またはコンピュータシステムまたはネットワークに含まれていてもよい。しかしながら、データストリーム１１０からのデータは、データの形態及び特性とデータ操作システム１３０の目的または用途に基づいて、時々操作されても操作されなくてもよい。いずれの場合においても、いったんデータがデータ識別システム１２０及びデータ操作システム１３０を通過すると、そのデータの一部またはすべてを出力データストリーム１４０として出力することができる。この出力データストリームは、次に、通常の場合に電子データが遭遇する任意の形態で、さらに処理、送信、記憶等をすることができる。本発明の種々の実施形態において、出力データストリームは、バックアップデータとして、多くの記憶媒体のいずれかにアーカイブあるいは格納されてもよい。
【００５５】
ここで図２を参照すると、データ識別処理２００の例示的な全体図が与えられている。
データ識別処理２００は、例えば、第１の選択関数２２０（上述の高速／低速の複数の選択基準を含んでいてもよい）を利用し、次に、ある既存のチャンクを融合し（２３０）及び／または分解する（２４０）、コンテンツ定義のチャンク化方式からなる第２の修正選択関数を利用してもよい。この処理はステップ２１０において開始でき、このステップでは、入力データストリームはデータ識別システム（例えばシステム１２０）に入力される。次にステップ２２０において、コンテンツ定義のチャンク化手順（関数、アルゴリズム等）をデータストリームに適用して、データについての提案されるカットポイント、ブロックポイント、ブレイクポイントまたはチャンクポイントを得ることができる。コンテンツ定義のチャンク化手順は、（例えば、前述の関連特許出願において開示されている技法に対し）第１の高速ハッシュ及び第２の低速ハッシュの関数または手順を含んでいてもよい。次に、ステップ２３０またはステップ２４０の一方または両方が行われてもよい。提案されたデータのカットポイント、ブロックポイント、ブレイクポイントまたはチャンクポイントは、ステップ２３０において、以下でより詳細に説明する特定の規則に基づいて、ブロックまたはチャンク結合手順を適用して既存のチャンクを融合することにより、変更することができる。ステップ２４０において、提案されたデータのカットポイント、ブロックポイント、ブレイクポイントまたはチャンクポイントは、以下でより詳細に説明する特定の規則に基づいて、ブロックまたはチャンクの分割または分解手順を適用して既存のチャンクをより小さなチャンクに分割することにより、変更することができる。ステップ２４０において、これらの手順からの出力データは、データ操作システム１３０に送られるべきカットポイント、ブロックポイント、ブレイクポイントまたはチャンクポイントまたは放出されるチャンクを決定することができる。
【００５６】
図３ａ及び図３ｂは、例えば、図２のステップ２３０において使用できる例示的なコンテンツ定義のチャンク化ポリシーのデータストリームである。この例示のポリシーは、(i)長い一続きの非重複データ内で小さなチャンクを融合して大きなチャンクにするが、その一方で、(ii)小さなチャンクを融合しないことによってその小さなチャンクを伴う重複データの近傍にある非重複データ領域のエッジに境界をつけ、及び／または(iii)重複であることが分かった大きなチャンクを再放出することができる。この例示的な例では、例えばアーカイブデータまたはバックアップデータが処理された場合、特に、データストリームの大きな文字列が時間とともに重複されやすい状況では、原理１及び２を適用して、データのカットポイント、ブレイクポイント、ブロックポイントまたはチャンクポイントを設定してもよい。図３ａ及び図３ｂにおいて、データストリーム３００，３５０は、それぞれ、それらのデータストリームに対して提案されたチャンク化を変更または修正する処理を含んでいてもよいデータチャンク化手順を示している。図３ａにおいて、最初の早いチャンク化時間での、例えば最初の週での、最初の提案されたデータストリームのカットポイント、ブレイクポイント、ブロックポイントまたはチャンクポイントは、３３０としてここに示したデータストリームの抜粋(excerpt)を含んでいてもよい。この場合、例えば、重複データが見つからない、コンテンツ定義のチャンク化手順（例えば、図２の２２０）によって生成された３０個のデータグループ、ブロックまたはチャンクの長いシーケンスが存在してもよい。非重複ステータスの指定は記号表示“ｎ”によって示されている。図に示したように、データチャンク化手順３００は、５つの連続するチャンクのすべての融合３０１〜３２６が重複していないと判定するとともに、３０個の個々のチャンクの各々が重複していないと判定する。この場合、手順３００に示したチャンク融合ポリシー２３０は、５つの小さなチャンクの連続するグループを融合することにより大きなチャンクを形成することを選ぶことができ、その結果、例えば６個の大きなチャンク３４１〜３４６からなる出力ストリーム３４０が得られることになる。
【００５７】
例えば第２の後の時間に対応するかもしれない図３ｂにおいて、入力ストリーム３５１の抜粋の提案されたチャンク化は、再び３０個のチャンクを含んでいる。図示のように、データストリーム３５１は、複数の重複データブロックまたはチャンク、例えば一緒と考えられる最初の５つのチャンク３５２を含んでいてもよく、一緒と考えられる最後の５つのチャンク３５７は重複であってもよい（“ｄ”として示し、大きな重複と呼ばれる）。重複した大きなチャンクを保持することは都合がよいので、３５２と３５７とからなる小さなチャンクが選ばれて、出力ストリーム３８０内で融合され、大きなチャンク３９０，３９１を生成する。重複した２つのグループ３５２，３５７は、例えば非重複ステータスに指定された２０個のデータブロックの列すなわちチャンク３５３〜３５６と境界を接する。ブロック３５３〜３５６内で“ｎ”は、個々のチャンクとしても、５つの連続するチャンクからなる任意のグループとしても、重複が見つからなかったことを示している。原理１は、チャンクポイント３６０とチャンクポイント３７０との間のこの大量の非重複データを、チャンクの結合または融合手順を用いてグループ化することができることを示唆している。しかしながら、（重複と考えられるデータと非重複データとの間の境界にまたがるかまたはこの境界の十分近くに存在する、大きなチャンクを生成しない、という）原理２に基づいて、小さなチャンクの最初及び最終のバッファゾーンを含むように、非重複領域３６０〜３７０を区分するのが最善であろう。変化領域３６０〜３７０が十分に小さい（例えば、少数の連続するデータグループまたは非重複データの「穿孔(short hole)」）場合、手順は、融合を全く行うことなく、連続するチャンクの全領域を放出することを選んでもよい。もう１つの選択肢として、例示的な出力ストリーム３８０で示されるように、結合または融合手順は、２つのより小さなチャンク３８１，３８２に先行されかつ３つのより小さなチャンク３８３，３８４，３８５が後続する３つの大きなチャンク３９５，３９６，３９７として、３６０〜３７０から領域を放出することを選んでもよい。それゆえ、出力ストリーム３８０は、重複していると考えられる領域から重複していないと考えられる領域までの遷移の後に、及び／または、重複してない領域から重複している領域までの遷移の前に、融合されていない小さなチャンクの遷移領域を含んでいてもよい。出力ストリーム３２０，３８０によって示された効果を生み出す手順３００，３５０を組み込んだ処理は、重複検出についての条件に合った量を維持することにより、及び／または、格納されまたは送信されるデータセグメントの平均的サイズを大きくすることにより、例えば、アーカイブの用途、インターネット通信等に典型的なデータストリームの性能を改善することができる。
【００５８】
図４ａ及び図４ｂを参照すると、重複データによって境界をつけられた、連続する非重複データの開始及び終了近傍にあるより大きなチャンクを、そのような領域内の潜在的な重複をより良く識別するように、分解または分割できる、本発明の少なくとも一実施形態による例示的なコンテンツ定義のチャンク化ポリシーを示すデータストリーム４００，４５０が示される。データストリーム４００，４５０は、例示的な出力４２０，４８０を生成するように、提案されたチャンク化４１０，４６０を変更または修正する処理（例えば、図２のステップ２４０に対応している）を含んでいてもよい、データチャンク化手順を説明している。
【００５９】
図４ａにおいて、最初の早い時間、例えば最初の週での手順２２０の出力は、４１０としてここに示したデータストリームの抜粋を含んでいてもよい。この場合、（“ｎ”によって示された）非重複として分類されたデータグループ、ブロックまたはチャンクのシーケンスが再び存在していてもよい。上記のような６つのチャンクを４１０に表示している。チャンク変更ポリシーは、原理１に基づき、これらの大きなブロックは後で再発生する高い可能性を有することを期待して、その出力ストリーム４２０に、これらと同一のチャンクを提示することを選んでもよい。図４ｂにおいて、第２の後の日付での、例えば第２の週での図２の手順２２０の出力は、今回、いくつかのデータグループ、ブロックまたはチャンクが重複であると判定された（“ｄ”で示された４６１，４６６）が、一方で他の４６２〜４６５は重複ではないと判定された（“ｎ”として示されている）、データストリーム４６０の抜粋を含んでいてもよい。一般に、大きな重複出力チャンクが望ましいので、チャンク変更ポリシーは、出力ストリームに未変更の重複チャンク４６１，４６６を渡すことを決定してもよい。この場合、カットポイント、ブレイクポイント、ブロックポイントまたはチャンクポイント４７０，４７５間の領域は、完全に非重複として識別されたグループ、ブロックまたはチャンクからなる。ポイント４７０が非重複領域の始まりであると判定したチャンク化変更ポリシーは、より短い平均チャンク長を生成する代替手順を用いて、内部の非重複チャンクの領域を変更しないで、１つの初期チャンク４６２を分割することを選んでもよい。ポイント４７５は非重複領域に続く重複領域の開始であると判定したこの同じポリシーは、例えば、より短い平均チャンク長を生成する代替手順を用いて、１つ前のチャンク４６５を分割することも決定することもできる。図示のように、最初の非重複データブロック４６２が、複数のより小さなブロックまたはチャンク４８１〜４８５を生成し、その一方で、最後の非重複データブロックが出力ストリームにおいて４つのブロック４９１〜４９４を生成してもよい。このように、このポリシーは元のデータストリーム４６０内の変化領域の開始及び終了をよりよく区別できるので、より小さなチャンクの方が、より多くの重複データブロックを捉えるという点ではより優れている。例えば、図４ｂに示すように、事実、出力ストリームは、重複ブロック４８１，４８２，４９４を重複することができる。
【００６０】
当業者には、重複及び／または非重複の領域が具体的にどのように定義されるのか、小さなチャンクのバッファゾーンの長さがどのように選ばれるのか、小さなチャンクのサイズなのかあるいは大きなチャンクのサイズなのか、等の詳細において、データストリーム３００，３５０，４００，４５０に関する手順の特定の実現形態は変化してもよいことが認識されるであろう。小さな（またはより小さな）チャンクは、約２〜１８ｋの典型的なサイズであってよく、ランダムデータについては、入力は指数分布に類似したチャンクサイズ分布を示してもよい。単純な融合の実施形態における大きなあるいはより大きなチャンクは、例えば、それに対応した広い範囲のチャンクサイズを有する、ちょうど８個の連続する小さなチャンクによって常に構成されてもよく、約１６ｋ〜１４４ｋ（例えば８倍大きい）のサイズに平均化してもよく、ランダム入力データで示された場合の指数関数よりも狭い、より狭いチャンクサイズ分布を示してもよい。
【００６１】
種々の実現の形態において、第１のセグメント化手順の後に第２のセグメント化手順が続いてもよく、第１のデータセグメント化手順及び第２のセグメント化手順の期待されるデータグループの平均サイズが異なっていてもよい。期待される平均データグループサイズは、ランダム入力データを含んだ入力ストリームで示された場合、チャンク化の境界を選択する統計的な期待率である。期待されるデータグループのサイズは、Cezary Dubnicki, Erik Kruus, Cristian Ungureanu, and Krzysztof Lichotaによる関連特許出願"METHODS AND SYSTEMS FOR DATA MANAGEMENT USING MULTIPLE SELECTION CRITERIA"において説明されるように、選択基準に関連していてもよく、または式(1)で示唆したように、上に示したような（最小または最大チャンクサイズの制限がない）チャンクサイズｓに対する理論的期待値に関連していてもよい。いくつかの実現の形態は、図３に示したように計算の単位として「チャンク」を使用するよりも、むしろ、融合の制限を支配する基礎となるデータストリームの実際の長さまたは量、重複または非重複ステータスの指定に関連する種々の制限、または、どれだけ多くのデータを融合しなければならないのかに関連する制限、を利用することが好ましい。他の実現の形態は、小さなチャンクを融合できるいくつかの方法またはその度合いを含んでいてもよい。いくつかの実現の形態は、付加的にまたは他の選択肢として、入力ストリームのさらなる（かつ、実際には本質的に異なる）特性を用いることを選び、小さなチャンクと大きなチャンクとの間での決定プロセスを導くことができる。例えば、実現の形態は、以前のデータ入力の統計モデルから生じたチャンク化ポリシー２３０及び／または２４０を導く入力、及び／または異なる期待される出力チャンク長のチャンク化手順間の遷移を導く出力を含んでいてもよい。このようなポリシーに対する他の有用な入力は、例えば、以前の履歴または高速エントロピ推定法（例えば、レーニイ・エントロピ(Renyi entropy)）に基づいた圧縮推定値を含んでいてもよい。
【００６２】
いくつかの実現の形態は、現在の重複除去の目標値に関連した結果の現在のステータスに基づいて、チャンク化サイズを設定または動的に変更できる可能性も含んでいてもよい。例えば、手順が重複除去の目標を達成している場合、その手順は、より大きな平均チャンクサイズを有する、新しい非重複データをチャンク化するように切り替えることができ、メタデータを低減することもできる。あるいは、重複除去の目標が満たされていない場合、その手順は、少しだけ小さい大きなチャンクサイズに切り替えてもよい。いくつかの実現の形態は、平均データグループサイズの目標値に関連した結果の現在のステータスに基づいて、チャンク化サイズを設定または動的に変更できる可能性も含んでいてもよい。手順の出力ストリームの平均チャンクサイズが目標を越えている場合、例えば、手順は、（ある最大数までの）可変数である個数の連続する小さなチャンクに対する重複の問い合わせを後で適切に処理できる場合には、全く新しいデータの領域にある、より少数のチャンクを融合することができる。いくつかの実現の形態は、小さい及び／またはより大きなデータグループについての推定されたまたは実際の圧縮率に関する現在のステータス、または重複除去特性についての理論的または実験的モデルに基づいて、チャンク化サイズを設定または動的に変更できる可能性も含んでいてもよい。例えば、以前における性能の評価が、小さなチャンクレベルで、例えば非重複領域に入ることが、最初の３つは特に重複の可能性があるが一方で次の８つ以上が特に非重複である可能性がある小さなチャンクの初期のシーケンスを含む可能性が大いにあることを示す場合、手順は、例えば、境界領域にある小さなチャンクの数を（例えば、４つまたは２つではなく）３つの小さなチャンクに調整できるであろう。いくつかの実現の形態は、最終的なチャンクサイズ及び／またはＤＥＲをさらに改善するように、第２のデータセグメント化手順を複数回適用できる可能性も含んでいてもよい。例えば、手順は分割のために変更されてもよい。すなわち、初期の小さなチャンク化が重複ステータスを有する領域のより細かい粒度の拡張から始まると仮定すると、第１の非重複領域をさらに細かいスケールで考えられる限り分割して、重複の領域をより綿密に終端させることができる。非常に小さなチャンクの増加した個数に関連付けられたメタデータコストがＤＥＲの利点を上回る場合には（所定のまたは動的に変化する目標に基づくものであってもよいので）、このような処理は終了してもよい。
【００６３】
なお、図３ａ、図３ｂ、図４ａ及び図４ｂの入力データストリームは、元のデータストリームの同一の抜粋に対応していてもよいことに留意されたい。この場合、重複／非重複ステータスを指定するために必要な付加の処理労力の主要な源について、考慮、比較することが有益であろう。図３ａ及び図３ｂにおいて、重複ステータスの問い合わせの数は、小さなチャンク当たり２つの問い合わせを上限としてもよい（最大で、１つのチャンク重複に対して１つの問い合わせ、及び５つの連続するチャンクの重複に対して１つの問い合わせ）。それで、同一の２つの入力ストリーム３３０，４１０の場合、問い合わせ労力は、図３ａの場合で３０×２＝６０、図４の場合で６に制限される。融合処理の他の実現の形態は、多くの連続するチャンクを、ある所定の最大値までまたは基礎となるデータのある所定の最大量まで融合できる、可変サイズの大きなチャンクを認容してもよい。これはやはり入力単位当たり一定量の問い合わせ労力を生じさせるが、その一定量はより大きくなる。これらの考察は、システム設計に対して実際的な影響を及ぼすであろう。事実、多くの手順は、非重複ステータスに指定されたデータの連続領域が示されると、出力ストリーム３８０，４８０に類似した出力を生成できるが、有用な経験則は、さらなる「柔軟性(flexibility)」（すなわち、融合されたチャンクに対する多数の位置及び／または長さを可能にする）を有する手順が、より高い重複除去量を達成できるということである。この性能上の利点は、追加の問い合わせのコストに対して釣り合いが取れている必要がある。なお、類似検出及び差分圧縮をアーカイブシステムに含んだ技法の中には、保存されたデータ量に対して線型的に（またはより悪く）規模が大きくなるものがあるが、この追加の問い合わせコストは、以前に記憶されたデータの規模にかかわらずほぼ一定であることに留意されたい。提案されたシステム及び方法の少ない追加コスト及び優れたスケーラビリティは、これらの手法を、データアーカイブ及びデータ通信システム等のための重複除去及びデータ処理速度を改善する他の利用可能なシステム及び方法よりも好ましいものにすることができる。
【００６４】
前述の手順の各々は、比較的簡単な処理、ソフトウェアまたはアルゴリズムを使用して実行できるので、重複データ認識を向上させＤＥＲを改善する可能性を備えるわずかな処理時間を必要とするのみであろう。さらに、各手順は、種々の実施形態において、短いまたは小さな先読みバッファを使用して実装することができる。この先読みバッファは、少量のデータが重複データの大きなストリーム内に挿入された場合に、再同期化を支援するのにも有用であろう。その場合、先読みバッファは、前のデータストリームから現在のデータストリームへのシフトを識別しないので、大きな再同期化が必要である。この再同期化は、処理されるデータストリーム中の特定の形態のデータに基づいて、事前に決定することができる。種々の実施形態は、再同期化を支援する１つ以上のバックアップのカットポイント、ブレイクポイント、ブロックポイントまたはチャンクポイントも含んでいてもよい。ともかく、ここで複数のより詳細なフローチャート及び例を与えて、本発明のいくつかの実施形態をさらに説明する。なお、図３ａ、図３ｂ、図４ａ、図４ｂに示す例では、種々の大きなシャンク及び小さなチャンクを等しい長さで描いているが、個々のチャンクは、種々のバイト数の基礎となるデータストリームを含むことができ、小さいチャンク及び大きいチャンクと呼ばれているものに関連付けられたデータストリームの実際の長さは、１つの小さな／大きなチャンクから次のそのようなチャンクまで変化できることに留意されたい。例えば、基礎となる非融合チャンクのいずれのもののデータコンテンツよりも完全に大きなデータコンテンツを有する大きなチャンクのいくつかは、入力データストリームの他の領域で生成された個々の小さなチャンクよりも小さい可能性がある。このように、チャンクは、実際には、可変サイズ(variable-sized)であり、図面が示唆するような固定サイズ(fixed-size)でなくてもよい。
【００６５】
最初により小さなチャンクを生成し、次にチャンクを融合して大きなチャンクにするという手順を実行することによって、可変サイズのチャンクの生成にかなり高い柔軟性を与えることができる。融合の決定を下すことのできる方法は多数あるが、１つの重要な違いは、チャンク化決定を行うのに必要とされる、小さなチャンク当たりの問い合わせの数である。例えば簡単な手法は、連続する小さなチャンクを一定または所与の数Ｎだけ連結することによって、大きなあるいは巨大なチャンクを生成することであろう。この手法では、大きなチャンクの存在の問い合わせの数を、例えば小さなチャンク当たり１つに制限することができる。他の可能性は、必要な問い合わせ数に対するより高い制限を用いて、大きなチャンクが２，…，Ｎ個の連続する小さなチャンクからなることを可能にすることであろう。何らかの形で保存される必要のある大量の小さなチャンクの「メタデータ」がある可能性があるので、非放出の小さなチャンク（すなわち、ある大きなチャンクの一部だったために放出されなかった小さなチャンク）に関する情報の使用は、あまり望ましくない。
【００６６】
簡単で例示的なチャンク融合手順またはアルゴリズムとして、例えば次のようなものがある。
【００６７】
【表２】
2010515114.tif 000013
このような手順は、構成要素のステップが正確に定義された種々の合理的な方法を受け入れることによって柔軟性を認めている。ここで、「ｂｕｆ」は、例えば２ｋ−１個までのチャンクを含んだ先読みバッファを指している。「ｉｓＤｕｐＢｉｇ（ｂｕｆ［０］）」は、最初の小さなチャンクが、以前に放出された融合チャンクの一部であるかどうかをチェックすることができる。種々の実施形態において、このことは、例えばｂｕｆ［０］からｂｕｆ［ｋ−１］までを含む単一の大きなチャンクが重複であるかどうかをチェックすることを必要とするであろう。重複の場合、ｂｕｆ［０．．ｋ−１］は大きなチャンクとしてもう１回、再放出される（「ｅｍｉｔ  ｂｉｇ  ＠  ｂｕｆ［０  ｔｏ  ｋ−１］」）。他の実施形態において、ｉｓＤｕｐＢｉｇ（ｂｕｆ［０］）は、ｋ−１から２までのあるＮに対して任意の融合ｂｕｆ［０．．Ｎ］が以前に放出されたかどうかを問い合わせることにより、重複ステータスをチェックすることができる。以前に放出されている場合には、ｂｕｆ［０］からｂｕｆ［Ｎ］を含む融合された（大きな）チャンクを放出することができる。「ｆｉｎｄＤｕｐＢｉｇＳｔａｒｔｉｎｇ」は、先読みバッファｂｕｆ内での増加したオフセットから始めてｉｓＤｕｐＢｉｇを順次呼び出すことを除き、「ｉｓＤｕｐＢｉｇ（ｂｕｆ［０］）」に類似した手順を呼び出すことができる。このような前向きの最長で最初の融合されたチャンクが以前に放出されていることが分かった場合、行４において、小さなチャンクがｂｕｆ［０］から開始して放出され、行３によって見つかった最初の融合されたチャンクがこれに続く。「ｉｓＰｒｅｖＤｕｐ」は、ｂｕｆ［０］の直前に放出されたチャンクの重複ステータスの状態変数を問い合わせる。これは、以前の放出の指定された重複ステータスを反映する状態変数として実装でき、及び／または、以前の放出が２つ以上の小さなチャンクからなる融合されたチャンクであった場合に、真(true)を保存することによって実装できる。他の実施形態では、代わりに、「真の(true)」重複ステータスを任意の重複の以前の放出（１つ以上の小さなチャンク）に割り当てもよい。さらに、大きなチャンクの形成基準は、大きなチャンクの基礎となるデータストリームのサイズについての所定のしきい値を超えるチャンクに大きなチャンクを制約することを含んでいてもよい。理解を容易にするために、融合手順中の小さなチャンクのカウントによってのみ判定された大きなチャンクについて、以下に説明する。固定サイズの大きなチャンクについて、処理は小さなチャンク当たりせいぜい１つの問い合わせしか行わない。一方、可変サイズの大きなチャンクについては、処理は、小さなチャンク当たりｋ−１個まで問い合わせを行うことができる。他の変形は、単一の小さなチャンクが（論理的な）重複／非重複遷移を発生するのに十分なものであると考えられるかどうかという概念を修正することを含んでいる。このようなアルゴリズムが先読みバッファなしで書かれている場合、ｆｉｎｄＤｕｐＢｉｇＳｔａｒｔｉｎｇ（）の述語は利用不可能である。そのような場合、２つの重複入力ストリームが無限に非ｓｙｎｃｈ状態(out-of-synch)に留まることがあり得る。これは再同期カットポイントの導入により避けることができる。すなわち、小さなチャンクのカットポイントレベルがあるしきい値を超える場合は常に、その小さなチャンクによって大きなチャンクを終了させることができるが、大きなチャンク内部のどこか他の場所に発生することはできない。このようなやり方で、再同期化を自発的に行うだけの十分なルックアヘッドを持たないアルゴリズムでは、２つの重複入力ストリームを再同期カットポイントの後に強制的に再同期化することができる。
【００６８】
ここで図５ａ及び図５ｂを参照すると、小さなチャンクを有する非重複データのエッジに境界をつけて非重複データの短い領域内に小さなチャンクを残しつつ、小さなチャンクを融合または結合して長い一続きの新しい非重複データ内の大きなチャンクにする、固定サイズの先読みバッファを利用したコンテンツ定義のチャンク化ポリシーの例示的なフローチャート５００が与えられている。まず５０３において、入力バッファまたは先読みバッファは、多くのより小さなチャンクを含んでいる。次に決定ステップ５０６において、データのより大きなチャンクを放出するのに十分なだけの小さなチャンクがバッファにあるかどうかが判定される。それだけの小さなチャンクがない場合、ステップ５０９において、１つの小さなチャンクがバッファから放出され、ステップ５２４において、バッファは、最後に放出されたチャンクの後の次のチャンクで補充される(refilled)ことができる。大きなチャンクを放出するのに十分なだけの小さなチャンクがバッファにある場合、次に決定ステップ５１２において、バッファが以前に放出された大きなチャンクから始まるかどうかが判定される。もしそうである場合、ステップ５１５において、その大きなチャンクを放出することができ、その後、補充(refill)バッファステップ５２４が続く。もしそうでない場合、ステップ５１８において、決定ステップは、バッファが、大きなチャンクの放出を防止するのに十分なほどバッファの始まりに近い、以前に放出された大きなチャンクを有するかどうかを判定する。もしそうである場合、ステップ５２１において、処理は、バッファの始まりと大きなチャンクとの間の小さなチャンクを放出し、その大きなチャンクを放出し、その後、補充バッファステップ５２４が続くであろう。しかしながら、バッファが、大きなチャンクの放出を防止するのに十分なほどバッファの始まりに近い、以前に放出された大きなチャンクを持っていない場合、処理は決定ステップ５５６に進む。決定ステップ５５６において、次の大きなチャンクを構築することを許容するために、大きなチャンク（バッファの始まりプラス大きなチャンクの長さ）の放出を防止するのに十分なほどバッファの始まりに近いような以前に放出された大きなチャンクが存在し得ないような点に引き続く、十分なほどの小さなチャンクをバッファが有しているかどうかが判定される。有していない場合、ステップ５６８において、処理は、放出された最後のチャンクは以前に放出された大きなチャンクであったかどうかを判定する。そのチャンクが以前に放出された大きなチャンクである場合、ステップ５７１において、処理は、１つの小さなチャンクを放出でき、その後、補充バッファステップ５２４が続く。ステップ５６８に対する答えが「いいえ」の場合、ステップ５６５において、新しい大きなチャンクが放出される。次の大きなチャンクを構築できるとステップ５５６で判定した場合、決定ステップ５５９が実行される。決定ステップ５５９において、ステップ５２４での放出された最後のチャンクが、以前に放出されたチャンクだったかどうかが、または次の大きなチャンクが以前に放出されたかどうかが判定される。決定ステップ５５９に対する答えが「いいえ」の場合、ステップ５６５において、新しい大きなチャンクが放出される。決定ステップ５５９に対する答えが「はい」の場合、次の可能性のある大きなチャンクが決定される前に、ステップ５６２において、小さなチャンクがすべて放出される。いずれの場合も、後に補充バッファステップ５２４が続く。
【００６９】
図６ａ、図６ｂ及び図６ｃを参照すると、少なくとも一実施形態による、データ入力ストリームに対するコンテンツ定義のチャンク化融合ポリシーの適用の例示的な説明図６００が示されている。まず入力データストリーム６０５は、例示的な一連の小さなチャンクのハッシュ値からなることが示されており、ここで、各例示的なハッシュ値は個々の文字により表されている。例示的な入力データストリーム６０５は、第１の標準コンテンツ定義のチャンク化アルゴリズムの適用の結果であろう。図５ａ及び図５ｂによるコンテンツ定義のチャンク融合関数からなる第２の修正選択関数は、先読みバッファ６１０を用いて入力データストリーム６０５を反復して調べることにより、その例示的な入力データストリーム６０５に適用される。先読みバッファ６１０は、８つの小さなチャンクの例示的な容量を持っている。この例では、示されるチャンク化ポリシーは、予測される大きなチャンクをちょうど４つの小さなチャンクからなるように制限する。まず最初には、先読みバッファ６１０は、複数の小さなチャンク、より具体的には、入力データストリーム６０５の初めにあるそれらの小さいチャンクのハッシュ値“ａｂｃｄｅｆｇｈ”によって満たされている。融合された小さなチャンクまたは融合されていない小さなチャンクのいずれを放出するかの各決定の後、先読みバッファ６１０は、最後に放出されたチャンクの後のチャンクから始まって容量まで満たされる。例えば、先読みバッファ６１０が、入力データストリーム６０５の始まりで、８個の小さなチャンク“ａｂｃｄｅｆｇｈ”を最初に含んでいる場合、小さなチャンク“ａ”，“ｂ”，“ｃ”，“ｄ”は、新しい大きなチャンク“ａｂｃｄ”６１５に融合され、そのような大きなチャンクとして放出される。というのは、これらの最初の小さなチャンクも、次の可能性のある大きなチャンク“ｅｆｇｈ”６２０も、いずれも以前に確認されていないからである。最も最近に放出されたチャンク“ａｂｃｄ”６１５の後の次のチャンク“ｅ”から始まって先読みバッファ６１０が補充された後、小さなチャンク“ｅ”，“ｆ”，“ｇ”，“ｈ”も新しい大きなチャンク“ｅｆｇｈ”６２０に融合され、そのような大きなチャンクとして放出される。というのは、最後に放出されたチャンク“ａｂｅｄ”６１５も、次の可能性のある大きなチャンク“ｉｊｋｌ”６２５も、いずれも重複した大きなチャンクではないからである。最も最近に放出されたチャンク“ｅｆｇｈ”６２０の後の次のチャンク“ｉ”から始まって先読みバッファ６１０が補充された後、小さなチャンク“ｉ”，“ｊ”，“ｋ”，“ｌ”も新しい大きなチャンク“ｉｊｋｌ”６２５に融合され、そのような大きなチャンクとして放出される。というのは、最後に放出されたチャンク“ｅｆｇｈ”６２０も、次の可能性のある大きなチャンク“ｍｎｏｐ”も、いずれも重複した大きなチャンクではないからである。最も最近に放出されたチャンク“ｉｊｋｌ”６２５の後の次のチャンク“ｍ”から始まって先読みバッファ６１０が補充された後、小さなチャンク“ｍ”，“ｎ”，“ｏ”，“ｐ”は、新しい大きなチャンクに融合されないで、小さなチャンク“ｍ”，“ｎ”，“ｏ”，“ｐ”６３０としてすべて放出される。というのは、最後に放出されたチャンク“ｉｊｋｌ”６２５は非重複の大きなチャンクであるが、次の可能性のある大きなチャンク“ｅｆｇｈ”６４０はステップ６２０において以前に確認されているからである。
【００７０】
図６ｂのこの例示的な概念的説明図６００の続きをここで参照すると、最も最近に放出されたチャンク“ｐ”６３０の後の次のチャンク“ｅ”から始まって先読みバッファ６１０が補充された後、小さなチャンク“ｅ”，“ｆ”，“ｇ”，“ｈ”は、新しい大きなチャンク“ｅｆｇｈ”６４０に融合され、大きなチャンクとしてそのように放出される。というのは、これらのチャンクは、先読みバッファ６１０の始まりとして、ステップ６２０で以前に確認されたように、以前に放出された大きなチャンクを構成するからである。最も最近に放出されたチャンク“ｅｆｇｈ”６４０の後の次のチャンク“ｉ”から始まって先読みバッファ６１０が補充された後、小さなチャンク“ｉ”，“ｊ”，“ｋ”，“ｌ”は、新しい大きなチャンク“ｉｊｋｌ”６４５に融合され、大きなチャンクとしてそのように放出される。というのは、これらのチャンクは、先読みバッファ６１０の始まりとして、ステップ６２５で以前に確認されたように、以前に放出された大きなチャンクを構成するからである。最も最近に放出されたチャンク“ｉｊｋｌ”６４５の後の次のチャンク“ａ”から始まって先読みバッファ６１０が補充された後、小さなチャンク“ａ”，“ａ”，“ａ”，“ｂ”は、新しい大きなチャンクに融合されないで、そのような小さなチャンク“ａ”，“ａ”，“ａ”，“ｂ”６５０としてすべて放出される。というのは、次の可能性のある大きなチャンク“ｂｂｃｄ”はそれまでには確認されていないが、放出された最後のチャンク“ｉｊｋｌ”６４５は、ステップ６２５で以前に確認された大きなチャンクだったからである。最も最近に放出されたチャンク“ｂ”６５０の後の次のチャンク“ｂ”から始まって先読みバッファ６１０が補充された後、小さなチャンク“ｂ”，“ｂ”は新しい大きなチャンクに融合されないで、そのような小さなチャンク“ｂ”，“ｂ”６５５として放出されるが一方、小さなチャンク“ａ”，“ｂ”，“ｃ”，“ｄ”は新しい大きなチャンク“ａｂｃｄ”６５５に融合され、大きなチャンクとしてそのように放出される。というのは、以前に放出された大きなチャンク“ａｂｃｄ”６５５は、潜在的な大きなチャンク“ｂｂａｂ”の放出を防止するために先読みバッファ６１０の始まりの十分近くにあったからである。
【００７１】
図６ｃのこの例示的な概念的説明図６００の続きをここで参照すると、最も最近に放出されたチャンク“ａｂｃｄ”６５５の後の次のチャンク“ｋ”から始まって先読みバッファ６１０が補充された後、小さなチャンク“ｋ”，“ｌ”，“ｍ”，“ｎ”は、新しい大きなチャンクに融合されないで、小さなチャンク“ｋ”，“ｌ”，“ｍ”，“ｎ”６６５としてすべて放出される。というのは、次の可能性のある大きなチャンク“ｏｐｉｊ”はそれまでに確認されていないが、放出された最後のチャンク“ａｂｃｄ”６５５はステップ６１５で以前に確認された大きなチャンクだったからである。最も最近に放出されたチャンク“ｎ”６６５の後の次のチャンク“ｏ”から始まって先読みバッファ６１０が補充された後、小さなチャンク“ｏ”，“ｐ”は新しい大きなチャンクに融合されないで、小さなチャンク“ｏ”，“ｐ”６７０として放出される。しかし一方で、小さなチャンク“ｉ”，“ｊ”，“ｋ”，“ｌ”は、新しい大きなチャンク“ｉｊｋｌ”６７０に融合され、大きなチャンクとしてそのように放出される。というのは、以前に放出された大きなチャンク“ｉｊｋｌ”６７０は、潜在的な大きなチャンク“ｏｐｉｊ”の放出を防止するために、先読みバッファ６１０の始まりのすぐ近くにあったからである。最も最近に放出されたチャンク“ｉｊｋｌ”６７０の後の次のチャンク“ｘ”から始まって先読みバッファ６１０が補充された後、小さなチャンク“ｘ”，“ｘ”，“ｙ”，“ｙ”は、新しい大きなチャンクに融合されず、小さなチャンク“ｘ”，“ｘ”，“ｙ”，“ｙ”６７５としてすべて放出される。というのは、次の可能性のある大きなチャンク“ｚｚａｃ”はそれまでには確認されていないが、放出された最後のチャンク“ｉｊｋｌ”６７０はステップ６２５で以前に確認された大きなチャンクだったからである。最も最近に放出されたチャンク“ｙ”６７５の後の次のチャンク“ｚ”から始まって先読みバッファ６１０が補充された後、小さなチャンク“ｚ”，“ｚ”，“ａ”，“ｃ”は、新しい大きなチャンク“ｚｚａｃ”６８０に融合され、大きなチャンクとしてそのように放出される。というのは、（先読みバッファ６１０が、潜在的な大きなチャンク“ｚｚａｃ”の後の“ａ”から始まった場合に、他の大きなチャンクを次の反復で放出できないように）先読みバッファ６１０はデータが不足し始め、また、放出された最後のチャンク“ｙ”６７５は以前に放出された大きなチャンクではなかったからである。最後に、先読みバッファ６１０が、放出された最後のチャンク“ｚｚａｃ”６８０の後の残っている小さなチャンク“ａ”で補充された後、小さなチャンク“ａ”に融合するチャンクがないので、小さなチャンク“ａ”を大きなチャンクに融合することはできず、小さなチャンク“ａ”６８５として放出される。したがって、（図５ａ及び図５ｂによるコンテンツ定義のチャンク融合関数からなる）第２の修正選択関数を入力データストリーム６０５に適用することは、第１の標準チャンク化アルゴリズムから与えられるチャンクを、非重複データの長い領域内で大きく、非重複データの長い領域の境界で小さく、非重複データの短い領域内で小さくなるように変更する結果となる。
【００７２】
病的(pathological)事例において再同期化の可能性を考えることは、大きなチャンクがなんらかの高レベルのカットポイント、ブロックポイント、ブレイクポイントまたはチャンクポイントにまたがることを決して可能にしないという選択肢につながる。大きなチャンクは常にオフセット形態で常に選ばれただけなので、この選択肢は、再同期化しなければ理論的に長期間にわたって同期化されないままであったであろう重複ストリームを、最終的に強制的に再同期化することができる。図７ａ及び図７ｂは、バックアップ（例えば再同期）チャンクポイントだけでなく固定サイズの先読みバッファも利用して、大きなチャンクが再同期ポイントにまたがらない限り長い一続きの非重複データ内で小さなチャンクを大きなチャンクに融合し、同時に小さなチャンクによって非重複データのエッジに境界をつけ、非重複データの短い領域内に小さなチャンクを残す、少なくとも一実施形態による、コンテンツ定義のチャンク化方式の例示的なフローチャート７００を与えている。まず、ステップ７０３において、入力バッファまたは先読みバッファは、多くのより小さなチャンクを含んでいる。次に、決定ステップ７０９において、データのより大きなチャンクを放出するのに十分なだけの小さなチャンクがバッファ内にあるかどうかが判定される。もしない場合には、ステップ７１２において１つの小さなチャンクがバッファから放出され、ステップ７０６においてそのバッファは、最後の放出されたチャンクの後の次のチャンクで補充されることができる。大きなチャンクを放出するのに十分なだけの小さなチャンクがバッファ内にある場合、決定ステップ７１５において、大きなチャンクが放出された場合に再同期ポイントが横切られるかどうかが判定される。横切られない場合には、処理はステップ７１８に進み、バッファが以前に放出された大きなチャンクから始まるかどうかを判定する。再同期ポイントが横切られる場合、処理はステップ７１２に進み、１つの小さなチャンクが放出され、その後、補充バッファステップ７０６が続くことができる。「はい」の場合、ステップ５１５においてその大きなチャンクは放出され、その後、補充バッファステップ７０６が続くことができる。ステップ７１８でバッファが以前に放出された大きなチャンクから始まると判定された場合、処理はステップ７２１に進んでその大きなチャンクを放出し、その後補充バッファステップ７０６が続く。「始まらない」場合、ステップ７２４において、決定ステップは、再同期ポイントを横切らず、大きなチャンクの放出を防止するのに十分なほどバッファの始まりに近い、以前に放出された大きなチャンクをバッファが持っているかどうかを判定する。「持っている」場合、ステップ７２７において、処理は、バッファの始まりとその大きなチャンクとの間の小さなチャンクを放出し、その大きなチャンクを放出するだろう。その後、補充バッファステップ７０６が続く。しかしながら、バッファが、大きなチャンクの放出を防止するのに十分なほどバッファの始まりに近い、このような以前に放出された大きなチャンクを持っていない場合、処理は、決定ステップ７６０に進む。決定ステップ７６０において、再同期ポイントを横切らない次���大きなチャンクを構築するために、大きなチャンク（バッファの始まりプラス大きなチャンクの長さ）の放出を防止するのに十分なほどバッファの始まりに近いような以前に放出された大きなチャンクが存在し得ないような点に引き続く、十分なほどの小さな小さなチャンクをバッファが有しているかどうかが判定される。有していない場合、ステップ７８０において、処理は、ステップ７０６中に放出された最後のチャンクが以前に放出された大きなチャンクだったかどうかを判定する。そのチャンクが以前に放出された大きなチャンクだった場合、ステップ７８５において、処理は、１つの小さなチャンクを放出でき、その後、補充バッファステップ７０６が続く。ステップ７８０に対する答えが「いいえ」の場合、ステップ７７５において、新しい大きなチャンクが放出される。再同期ポイントを横切らない次の大きなチャンクを構築できるとステップ７６０で判定した場合、決定ステップ７６５が実行される。決定ステップ７６５において、放出された最後のチャンクが以前に放出されたチャンクだったかどうか、または大きなチャンクの放出を考える場合に、次の大きなチャンクが以前に放出された大きなチャンクであったかどうかが判定される。決定ステップ７６５に対する答えが「いいえ」の場合、ステップ７７５において、新しい大きなチャンクが放出される。決定ステップ７６５に対する答えが「はい」の場合、次の大きなチャンクが決定される前に、ステップ７７０において、小さなチャンクがすべて放出される。いずれの場合においても、補充バッファステップ７０６が後に続く。
【００７３】
重複した大きなチャンクが検出される前または後のいずれかに、重複していない大きなチャンクを再チャンク化する、簡単なチャンク分割手順またはアルゴリズムの例を以下に示す。
【００７４】
【表３】
2010515114.tif 000014
ここで、データに対する一次パス(primary pass)が、大きな平均チャンクサイズによって行われてもよく、重複した大きなチャンクの後または前の単一の非重複データチャンクが、より小さな平均ブロックサイズで再チャンク化されてもよい。処理は、このようなアルゴリズムを変更して、重複／非重複遷移のより複雑な定義を検出するようにすることができる、例えば、Ｎ個の非重複がＤ個の重複に隣接している場合、より小さな平均サイズを用いてＲ個の大きなチャンクを再チャンク化する。あるいは処理は、チャンクの実際の長さと連携し、重複／非重複の遷移点を決定し処理することができるだろう。
【００７５】
図８を参照すると、固定サイズの先読みバッファを利用して、大きなチャンクを短い一続きの非重複データ内の小さなチャンクに分割し、同時に長い一続きの非重複データ内の大きなチャンクを残し、大きなチャンクを長い一続きの非重複データの境界に沿った小さなチャンクに分割する、コンテンツ定義のチャンク化ポリシー８００の例示的なフローチャートが与えられている。ステップ８０５において、入力バッファは複数の大きなチャンクを含んでいてもよい。その後、決定ステップ８１５において、処理は、バッファが以前に放出された大きなチャンクから始まるかどうかを判定する。「はい」の場合、ステップ８２０においてその大きなチャンクが放出され、次に、ステップ８１０において、放出された最後のチャンクの後の次のチャンクから始めてバッファが補充される。「いいえ」の場合、処理は決定ステップ８２５に進む。ステップ８２５において、処理は、放出された最後のチャンクが以前に放出された大きなチャンクであったかどうか、または次のチャンクが以前に放出された大きなチャンクであるのかを判定する。これらのいずれかが真の場合、処理はステップ８３０に進むことができ、大きな新しいチャンクが、複数のより小さなチャンクとして分割あるいは再チャンク化され、それらはバッファの始まりと次の大きなチャンクとの間で放出される。このステップの後にバッファ補充ステップ８１０が続く。しかしながら、ステップ８２５での質問に対する答えが「いいえ」の場合、ステップ８３５においてチャンクは大きなチャンクとして放出され、その後、バッファ補充ステップ８１０が続く。
【００７６】
図９ａ、図９ｂ及び図９ｃを参照すると、本発明の少なくとも一実施形態による、図８に基づくコンテンツ定義のチャンク化分割関数からなり、本発明の第２の修正選択関数の入力データストリームへの適用の例示的な説明図９００が与えられている。概念的な説明図９００，９３５，９６０を表す図９ａ、図９ｂ及び図９ｃをここで参照すると、入力データストリーム９０５は、カンマ区切りで示された例示的な一連の大きなチャンクのハッシュ値からなるように示されており、ここでは、各例示的な小さなチャンクのハッシュ値は個別の文字で表され、大きなチャンクは連結された文字で表されている。大きなチャンクのほとんどは、それが４個の小さなチャンクを含んでいるものとして示されているが、実際には、各大きなチャンク内の小さなチャンクの数は一定ではない。例示的な入力データストリーム９０５は、大きな平均チャンクサイズでチャンク化するように考案された、第１の標準コンテンツ定義のチャンク化アルゴリズム（例えば、図２の２２０）を適用した結果になるだろう。図８による、コンテンツ定義のチャンク化分割関数（例えば、図２の２４０）からなる第２の修正選択関数は、先読みバッファ９１０を用いて入力データストリーム９０５を反復して調べることにより、例示的な入力データストリーム９０５に適用される。先読みバッファ９１０は、２個の大きなチャンクに相当する例示的な容量を有している。最初に先読みバッファ９１０は、大きなチャンク、より具体的には、入力データストリーム９０５の初めにある、それらのチャンクのハッシュ値“ａｂｃｄ”，“ｅｆｇｈ”によって満たされている。分割された小さなチャンクまたは大きなチャンクのいずれかを放出する各決定の後、先読みバッファ９１０は、最後に放出されたチャンクの後のチャンクから始まって、その容量まで満たされる。例えば、先読みバッファ９１０が、最初に、入力データストリーム９０５の始まりの２つの大きなチャンク“ａｂｃｄ”，“ｅｆｇｈ”を含んでいる場合、小さなチャンク“ａ”，“ｂ”，“ｃ”，“ｄ”は、大きなチャンク“ａｂｅｄ”９１５として留まり、そのように大きなチャンクとして放出される。というのは、この最初の大きなチャンクと次の大きなチャンク“ｅｆｇｈ”９２０のいずれもそれまでに確認されていないからである。最も最近に放出されたチャンク“ａｂｅｄ”９１５の後の次の大きなチャンク“ｅｆｇｈ”から始まって先読みバッファ９１０が補充された後、小さなチャンク“ｅ”，“ｆ”，“ｇ”，“ｈ”も大きなチャンク“ｅｆｇｈ”９２０として留まり、そのように大きなチャンクとして放出される。というのは、放出された最後のチャンク“ａｂｃｄ”９１５も、次の大きなチャンク“ｉｊｋｌ”９２５も、いずれもそれまでに確認されていないからである。最も最近に放出されたチャンク“ｅｆｇｈ”９２０の後の次のチャンク“ｉｊｋｌ”から始まって先読みバッファ９１０が補充された後、小さなチャンク“ｉ”，“ｊ”，“ｋ”“ｌ”も大きなチャンク“ｉｊｋｌ”９２５として留まり、そのように大きなチャンクとして放出される。放出された最後のチャンク“ｅｆｇｈ”９２０も、次の大きなチャンク“ｍｎｏｐ”も、いずれもそれまでに確認されていないからである。最も最近に放出されたチャンク“ｉｊｋｌ”９２５の後の次のチャンク“ｍｎｏｐ”から始まって先読みバッファ９１０が補充された後、小さなチャンク“ｍ”，“ｎ”，“ｏ”，“ｐ”が大きなチャンク“ｍｎｏｐ”である状態から分割され、小さなチャンク“ｍ”，“ｎ”，“ｏ”，“ｐ”９３０としてすべて放出される。というのは、放出された最後のチャンク“ｉｊｋｌ”９２５はそれまでに確認されていなかったが、次の大きなチャンク“ｅｆｇｈ”はステップ９２０で以前に確認されているからである。
【００７７】
図９ｂのこの例示的な説明図９００の続きをここで参照すると、最も最近に放出されたチャンク“ｐ”９３０の後の次のチャンク“ｅｆｇｈ”から始まって先読みバッファ９１０が補充された後、小さなチャンク“ｅ”，“ｆ”，“ｇ”，“ｈ”は、大きなチャンク“ｅｆｇｈ”９４０として留まり、そのように大きなチャンクとして放出される。というのは、これらのチャンクは、ステップ９２０で以前に確認されたように、以前に放出された大きなチャンクを構成するからである。最も最近に放出されたチャンク“ｅｆｇｈ”９４０の後の次のチャンク“ｉｊｋｌ”から始まって先読みバッファ９１０が補充された後、小さなチャンク“ｉ”，“ｊ”，“ｋ”，“ｌ”は、大きなチャンク“ｉｊｋｌ”９４５として留まり、そのように大きなチャンクとして放出される。というのは、これらのチャンクは、先読みバッファ９１０の始まりとして、ステップ９２５で以前に確認されたように、以前に放出された大きなチャンクを構成するからである。最も最近に放出されたチャンク“ｉｊｋｌ”９４５の後の次のチャンク“ａａａｂ”から始まって先読みバッファ９１０が補充された後、小さなチャンク“ａ”，“ａ”，“ａ”，“ｂ”が大きなチャンク“ａａａｂ”である状態から分割され、小さなチャンク“ａ”，“ａ”，“ａ”，“ｂ”９５０としてすべて放出される。というのは、次の可能性のある大きなチャンク“ｂｂａｂ”はそれまでに確認されていないが、放出された最後のチャンク“ｉｊｋｌ”９４５は大きく、ステップ９２５で以前に確認されていたからである。最も最近に放出されたチャンク“ｂ”９５０の後の次のチャンク“ｂｂａｂ”から始まって先読みバッファ９１０が補充された後、小さなチャンク“ｂ”，“ｂ”，“ａ”，“ｂ”は大きなチャンク“ｂｂａｂ”９５５として留まり、そのように大きなチャンクとして放出される。というのは、放出された最後のチャンク“ｂ”９５０も、次の大きなチャンク“ｃｄｋｌ”９６５も、いずれも以前に確認された大きなチャンクではないからである。チャンク分割アルゴリズムが、大きなチャンク“ｂｂａｂ”９５５の途中から始まる大きな重複チャンク“ａｂｃｄ”を検出し再放出することに頼らないことが認識されるであろう。このことは、重複した大きなチャンクに対する問い合わせを行う量を増加させるチャンク融合アルゴリズムでは可能だったかもしれない。
【００７８】
図９ｃのこの例示的な概念的説明図９００の続きをここで参照すると、最も最近に放出されたチャンク“ｂｂａｂ”９５５の後の次のチャンク“ｃｄｋｌ”から始まって先読みバッファ９１０が補充された後、小さなチャンク“ｃ”，“ｄ”，“ｋ”，“ｌ”は、大きなチャンク“ｃｄｋｌ”９６５として留まり、そのように大きなチャンクとして放出される。というのは、放出された最後のチャンク“ｂｂａｂ”９５５は以前に確認されておらず、次の大きなチャンク“ｍｎｏｐ”は大きなチャンクとしては以前に放出されていないからである。最も最近に放出されたチャンク“ｃｄｋｌ”９６５の後の次のチャンク“ｍｎｏｐ”から始まって先読みバッファ９１０が補充された後、小さなチャンク“ｍ”，“ｎ”，“ｏ”，“ｐ”が大きなチャンク“ｍｎｏｐ”である状態から分割され、小さなチャンク“ｍ”，“ｎ”，“ｏ”，“ｐ”９７０としてすべて放出される。というのは、以前に放出されたチャンク“ｃｄｋｌ”９６５はそれまでに確認されていなかったが、次のチャンク“ｉｊｋｌ”はステップ９４５で以前に確認されているからである。最も最近に放出されたチャンク“ｐ”９７０の後の次のチャンク“ｉｊｋｌ”から始まって先読みバッファ９１０が補充された後、小さなチャンク“ｉ”，“ｊ”，“ｋ”，“ｌ”は、大きなチャンク“ｉｊｋｌ”９７５として留まり、そのように大きなチャンクとして放出される。というのは、これらのチャンクは、先読みバッファ９１０の始まりとして、ステップ９４５で以前に確認されたように、以前に放出された大きなチャンク“ｉｊｋｌ”を構成するからである。最も最近に放出されたチャンク“ｉｊｋｌ”９７５の後の次のチャンク“ｘｘｙｙ”から始まって先読みバッファ９１０が補充された後、小さなチャンク“ｘ”，“ｘ”，“ｙ”，“ｙ”が大きなチャンク“ｘｘｙｙ”である状態から分割され、小さなチャンク“ｘ”，“ｘ”，“ｙ”，“ｙ”９８０としてすべて放出される。というのは、次のチャンク“ｚｚａｃ”はそれまでには確認されていないが、以前に放出されたチャンク“ｉｊｋｌ”がステップ９７５で前に確認されているからである。最も最後に放出されたチャンク“ｙ”９８０の後の次のチャンク“ｚｚａｃ”から始まって先読みバッファ９１０が補充された後、小さなチャンク“ｚ”，“ｚ”，“ａ”，“ｃ”は、大きなチャンク“ｚｚａｃ”９８５として留まり、そのように大きなチャンクとして放出される。というのは、次の大きなチャンク“ａ”は以前に確認されておらず、以前に放出されたチャンク“ｙ”９８０は重複しているが重複した大きなチャンクではなかったからである。最後に、先読みバッファ９１０が、放出された最後のチャンク“ｚｚａｃ”９８５の後の残っている小さなチャンク“ａ”で補充された後、小さなチャンク“ａ”はそのように小さなチャンクとして簡単に放出される。図８によるコンテンツ定義のチャンク分割関数からなる本発明の第２の修正選択関数を入力データストリーム９０５に適用することは、第１の標準チャンク化アルゴリズムから与えられるチャンクを、非重複データの長い領域内で大きく、非重複データの長い領域の境界で小さく、非重複データの短い領域内で小さくなるように変更することになる。
【００７９】
図１０は、本発明の少なくとも一実施形態による、コンテンツ定義のチャンク融合ポリシーのアーカイブまたはバックアップシステム１０００への例示的な適用である。本発明のこの例示的な適用例において、例えばコンピュータシステム内にソースファイルシステム１０１０が与えられ、ソースファイルシステム１０１０はデータセットまたはデータストリームを含んでいてもよい。このソースファイルシステム１０１０はバックアッププログラム１０２０に接続されてもよい。本発明は、ソースファイルシステム１０１０及び／またはバックアッププログラムに組み込まれていてもよく、より優れたデータチャンク化及びより優れた重複除去を与えるように動作することができる。次にバックアッププログラム１０２０は、変更されたデータを、対象の記憶装置１０３０、例えば、テープ、ディスク、遠隔（リモート）ディスク記憶システム等に入力することができる。１つの典型的な記憶システムは、例えばSaturn（サターン）フルバックアップシステムであってもよい。本発明の種々の例示的な実施形態のいくつかの実験データ結果をここに与える。
【００８０】
ここで、本発明の実験結果及び解析についての説明に移る。ここでのシステム及び方法と種々のシミュレーション装置（例えば、ツール）により、非放出の小さなチャンク（すなわち、ある大きなチャンクの一部だったために放出されなかった小さなチャンク）に関する情報を用いて、技法、手順またはアルゴリズムのクラスを調べることができるようになった。何らかの形で保存される必要のある大量の小さなチャンクの「メタデータ」があるので、上記のような情報に基づいたポリシーはあまり望ましくない。
【００８１】
テストコードでは、理論的に興味のあるいくつかの非実用的なアルゴリズムも用いることができる。多くの異なる種類のチャンク放出、すなわち小さなチャンク及び大きなチャンクであってそれら両方の放出されたチャンクと放出されなかったチャンクに対するブルームフィルタを別々に保持した。（例えば）１つの利点は、「重複」データ領域の概念が、以前に放出された小さなチャンクと放出されていない（以前のある大きなチャンク放出の一部としては放出された）小さなチャンクとの両方を含むことができる点にある。放出されていない小さなチャンクを問い合わせるように変更されたアルゴリズムは、より細かい粒度のレベルで重複データを検出することができる。存在についての問い合わせに近似的に答えることの影響を測定するために、コードは偽陽性(false positive)をチャンク存在の返答に導入することもできるだろう。
【００８２】
何百ものユーザディレクトリの約１．１６テラバイトのフルバックアップからなるテスト用のデータセットを４か月にわたって使用した。ファイルの種類の分布がどのようであったかは確かではないが、そのデータセットが実データの大きな集合であって、実際に目にするであろうかなり典型的なものであったことは確かである。
【００８３】
非常に大きな入力データセットの解析が可能なように、種々の技法及び／またはアルゴリズムのオンラインシミュレーションを容易化するツールが多数開発された。その重要な発想は、入力データの２進表現(binary)「サマリー(summary)」を生成することだった。（理論上、チャンク当たり平均５１２バイト）のレベル９で生成されたすべての小さなチャンクについて、チャンクサイズ及び実際の１つまたは複数のカットポイントレベルだけでなく、チャンクのＳＨＡ−１ハッシュも保存された。このチャンクデータは、全くチャンクポイントを生成しない非常に非ランダムなデータセットを除いて、ほとんどの入力データセットを再チャンク化するのに十分なものであった。発明者等のユーティリティの後のバージョンは、ＬＺＯ圧縮アルゴリズムによって各固定サイズ（４ｋ，８ｋ，１６ｋ，３２ｋ）のチャンク化を実行し、元のチャンクサイズの百分率を有する単一バイトを保存することによって生成された、局所圧縮率推定値も保存した。現在のストリームのオフセット及びチャンクサイズが与えられると、ストリームの任意点で圧縮率を推定することができるだろう。こんなやり方で、１．１テラバイトの入力データを、よりポータブルな６０Ｇｂのサマリー情報として解析することができるだろう。（主としてディスクからの読み出しの減少により、このような再解析は、時間単位の時間を必要としたのみで日数単位の時間は必要としなかった。）レベル９チャンクが別個のファイルに対して発生した場合の、すべてのレベル９チャンクの重複／非重複ステータスも保存することもできた。
【００８４】
所与のアルゴリズム内には、最小及び最大チャンクサイズや、異なる挙動を生成できるトリガーレベルなどのいくるかのパラメータがある。分解と融合のアルゴリズムには、ｋ（大きなチャンク中の小さなチャンクの数）、可変サイズの大きなチャンクが許容されるかどうか等のような他のパラメータもある。アルゴリズムが全体で１．１テラバイトのデータセットまたはその圧縮されたサマリーに対して実行された場合、通常は保存され圧縮されたチャンク内のバイトに対する入力バイトの比率として、ＤＥＲを測定する。発明者等のデータセット上で異なるアルゴリズムの性能が測定された。
【００８５】
図１１は、少なくとも一実施形態による、種々のチャンク化技法での圧縮因子対チャンクサイズの実験結果を示している。図１１は、３つのアルゴリズムについて、ＤＥＲ対チャンクサイズ測定値のサンプリングを与えている。各アルゴリズムについて、実線は保存されたチャンクの平均サイズであり、対をなしている点線は同じチャンクの平均圧縮サイズである。平均チャンクサイズが大きくなるほどより良好に圧縮される。ベースライン(baseline)アルゴリズム１１２０，１１２５は、平均チャンクサイズだけでなく、最小チャンクサイズ及び最大チャンクサイズも変化させる。一般に、最小チャンクサイズと最大チャンクサイズとの間のほぼ中間に平均チャンク長を生成するように設定されたチャンク化レベルを保持し、カットポイントの３つのバックアップレベルを使用した。固定サイズの大きなチャンクにより実行する単純な融合チャンカー(chunker)が、「単純(Simple)」と記された線１１３０，１１３５に示されている。「装飾的(Fancy)」アルゴリズム１１４０，１１４５は最良の性能を有しているが、これは、以前に発生したが、以前の大きなチャンクの一部としてしか放出されなかったチャンクに対して、ブルームフィルタの問い合わせを使用した。
【００８６】
図１２を参照すると、少なくとも一実施形態による、種々のチャンク化技法の圧縮因子対チャンクサイズの実験結果が示されている。図１２は、平均チャンクサイズが図１１のそれより大きな範囲にわたり、同じ３つのアルゴリズム、すなわち単純アルゴリズム１２２０，１２２５、実用的(practical)アルゴリズム１２４５，１２５０、及び最良のアルゴリズム１２３５，１２４０のより多くの測定値を示している。偽陽性率が０，１，２，５，１０，２０及び４０％に設定された場合のチャンク存在についての問い合わせに対する偽陽性返答の影響も示している。水平線は、同じ入力データ（ＤＥＲ＝５．６７）に対する市販の(DataDomain)バックアップ機器の重複排除性能である。この測定では、平均チャンクサイズは未知であるが、４〜１０ｋバイトの間のいずれかである可能性がある。「実用的(Practical)」及び「最良の(Best)」という印をつけた線は、図１１と同じアルゴリズムであるが、より広範囲のパラメータにわたるものである。傾向は、対数スケール上で、１ｋから８０ｋまでのチャンクサイズの範囲にわたって、線形に見える。しかしながら、挙動には制限が存在しなければならないので、これは一般的な規則ではない。チャンクサイズが非常に大きく（図面の下部）なると、ベースラインアルゴリズムを修正することによる利点はほとんどなかった。競争力があるためには、約５．７のＤＥＲを生じさせる、約８ｋのＬＢＦＳスタイルのチャンクサイズを有するシステムと競争したい。２０ｋと３０ｋとの間に、記憶されたチャンクの平均サイズがある、同等のＤＥＲを達成することができる。ローカルブルームフィルタからの概略の問い合わせが実用的でスケーラブルなアーカイブ機構の基礎を形成できるかどうかを調べることは、魅力的なことである。巨大な（例えば、Ｐｂ（ペタバイト））データセットによってこのことが可能になるように、誤って識別された重複に対するいくつかのアルゴリズムの感度を調べた。すべての事例において、チャンク存在の問い合わせに対する１％の偽陽性の誤判定によってさえ、ＤＥＲ及びチャンクサイズが極めて急速に低下することが判明した。これらの誤って生成された重複／非重複の遷移が小さなチャンクを誤って生成するということが起こる。せいぜい、そのような「ローカルな」ブルームフィルタを、ある制限された過去における存在の高品質な問い合わせに限定すべきであり、そうすれば偽陽性は生じない。しかしながら、項目がローカルブルームフィルタに見つからない場合、やはりバックエンドの記憶機構から決定的な答えを得るべきである。ネットワーク送信については、ローカルブルームフィルタの手法は非常に適切であろう。
【００８７】
大きなチャンクにおける等価な選択肢が生じた場合、そのような等価な選択肢に優先順位をつけるために何を行うことができるかについてより能力を発揮しようとする、いくつかのより複雑なアルゴリズムを調べたが、これらのアルゴリズムはあまりより良くは機能しなかった。例えば、１つの変形は、再同期ポイントで開始または終了する大きなチャンクを優先させるかなり複雑な論理を使用して、等価な優先権を持つ最長の大きなチャンクを使用するテストを行う。それは著しい改善を示さなかった。事実、いくつかのこのような試みは、実データ上で実行されると、かなり微妙な理由でうまくいかないことが多い。
【００８８】
図１３を参照すると、少なくとも一実施形態による、種々のチャンク化技法の分解による重複排除率対チャンクサイズの実験結果が示されている。図１３では、ベースラインアルゴリズム１３２０と比較した、分解アルゴリズムを用いた結果が与えられている。シリーズ(Series)１  １３２５、シリーズ２  １３３０、シリーズ３  １３３５及び接合最小問い合わせ(joining minimal querying)１３４０は、ベースライン１３２０に対して、ほんのわずかな改善しか有しない。これらの実行に対して変化させられたパラメータは、再チャンク化が生成する、小さなチャンクの期待される個数ｋであった。しかしながら、優れた性能を達成するために、分解アルゴリズムのパラメータは注意深く設定されなければならない。分解アルゴリズムは、４０〜５０ｋの平均チャンクサイズで特にうまく機能するように思われる。残念なことに、この制度には非競合ＤＥＲが多少ある。「単純な」融合アルゴリズムのデータのいくつかに対する非圧縮のＤＥＲも示している。分解アルゴリズムは、融合アルゴリズムの最も単純な実装とほぼ同じくらいよくなり得ることが分かる。
【００８９】
チャンクポイントの選択（表１を参照）が、ラビン、大きな素数による乗算、ボックスカー＋ＣＲＣ３２ｃの組み合わされた手法に基づくハッシュ、及びＭＬＣＧと複合ＣＲＣ３２ｃのハッシュを使用した場合に、ベースラインアルゴリズムを用いて上述のデータセットのＤＥＲを比較した。ほぼ同じ重複除去値及び平均チャンクサイズであることが分かった。このことは、典型的なデータに関し、単純なボックスカー和ですらそれを用いてチャンク化ポイントを選択することで、適切にほぼランダムなチャンクサイズ分布が生成されたというThakerの観察を裏付けるものである。Thakerは、このことを入力データそのものに十分なビットレベルのランダム性があったことを示すものとして説明した。そのため、高品質にランダム化されたハッシュは、彼のデータには必要ではなかった。
【００９０】
ここで、例えば、最適な「常に一緒の(always together)」チャンクのデータ特性について説明する。上述の１．１テラバイトのデータセットについて、小さなチャンクの最良の可能な配置はどのようなものかを考えることも面白い。Ａ＝５１２のチャンクサマリーのレベルで、約３億６０００万個の異なるチャンクしか含まれていないことが判明した。整数識別子に対する別個のメッセージダイジェストを注意して翻訳すると、「将来の知識(future kowledge)」を使用したいくつかの単純なチャンク融合を決定する他のツールを書いて、チャンク化性能に対するいくつかの理論的な制限を決定することは可能であった。
【００９１】
最適化ムーブの単純な組は、常に一緒に生じる２つのチャンクを常に融合することである。これはＤＥＲには全く影響を及ぼさないが、平均チャンクサイズを大きくする。これを反復するは、常に同時に発生するチャンクの最長の可能な文字列を生成する。このような融合は、ＤＥＲを、影響を受けない状態にしておくが、平均チャンクサイズを大きくする。
【００９２】
実際、チャンクを頻繁に一緒(often-together)に、または常に一緒(always-together)に融合することは、記憶の最適化に対する有用なバックグラウンドタスクであろう。しかしながら、アーカイブのバックエンドは削除を支援せず、次のチャンク情報を提供しないだろう。そのため、このやり方には従わなかった。その代わりに、この実験は、重複／非重複の遷移領域に基づいて本発明の単純なアルゴリズムがどの程度うまく機能していたかを判定する方法を与える。生(raw)の「レベル９」サマリーストリームについてのこの手順は、平均的な非圧縮保存チャンクの平均サイズを５７６から５８５５バイトまで増やす（すなわち、常に同時に発生する小さなチャンクの平均の数はこのデータセットについては約１０個である）ことが分かった。この６ｋのサイズは、低帯域幅ネットワークファイルシステム（ＬＢＦＳ）スタイルのチャンク化で典型的に使用されるチャンクサイズと同じようなものである（例えば、A. Muthitacharoen, B. Chen and D. Mazieres, "A Low-bandwidth Network File System", (2001), pp. 174-187を参照）。
【００９３】
発明者らは、約８ｋの平均チャンクサイズを有する、より大きな元のチャンク化も解析した。常に一緒のチャンクを各対ごとにすべて融合することにより、保存されたチャンクの平均サイズは７５３９７バイトになった。再び、この手順は、約１０を乗数として、保存チャンクの平均サイズを大きくした。
【００９４】
ここで図１４を参照すると、グラフ１４００がベースラインチャンク化アルゴリズム１４３０の観点において上に述べた「理論的な」制限を設け、多くの他の可変サイズの融合が（前の図面で提示したものとは異なる群だが、ほぼ同一の挙動を有する）１４４０，１４５０を実行し、種々の理論的なチャンクサイズが１４６０，１４７０を制限する。この場合、目標は、ＤＥＲとチャンクサイズの両方を大きくすることである。図示のようにグラフ１４００は、上述の１．１テラバイトのデータセットで常に同時に発生するチャンクのすべての組を融合することにより決定される、理論的なチャンクサイズの限界を示している。この手順は、（メタデータコストを無視して）重複除去率（ＤＥＲ）は影響を受けないが、保存チャンクの平均サイズを大きくするだろう。グラフ１４００は、可変サイズの大きなチャンク、例えば１４４０を有する本発明の融合アルゴリズムを、上述の１．１テラバイトのデータセットに対するこの特定の理論的チャンク化制限のほぼ中間に置く。
【００９５】
簡単な原理Ｐ１及びＰ２の考察に基づいて当初は定式化されたが、本実施形態における実際のテストデータ入力がそのような単純化したデータモデルからどの程度かけ離れているかを判定することは重要である。したがって、これらのテストデータセットにおける実際の特性及び変化の解析を考慮した。実際の入力テストデータは、Ｐ１及びＰ２に忠実な「理想的な(ideal)」データセットから極めて大幅にずれていることが分かった。Ｐ１に忠実な、最も単純で可能性のあるデータセットは、第１のバックアップセッション中に長いシーケンスの連続する非重複データを有し、その後、引き続く実行中に長い一続きの重複データが続くことが期待される。
【００９６】
チャンクの「現在の(current)」重複ステータスのビットストリームサマリーを用いて、５１２バイトレベルでチャンク化されたサマリーストリームを問い合わせることにより、本実施形態のテストデータセットの評価を始めた。連続する非重複チャンクの個数対連続する重複の後続チャンクの個数（及び逆もまた同様）の実際のヒストグラムは、単一の重複チャンクを後に従える単一の非重複チャンクを有することについて、圧倒的かつ円滑に変化する優先傾向を示した。このことは、本発明の動機づけに含まれるヒューリスティックスを生成するのに使用される簡単な原理が与えられたとして、驚くべきことであろう。（１４のフルバックアップセッションの後の）重複／非重複チャンクの最終的な連続する数についてのヒストグラムをグラフ化した（不図示）。これまた驚くべきことに、第１の「フル(full)」バックアップ後のヒストグラムの特徴も上記のものに類似していた。しかしながら、チャンクの重複回数が計数されなかったので、このようなヒストグラムは、異なるポリシーの重複除去率を推定するのに十分でないことは注目すべきである。常に一緒のチャンクの平均のサイズは約６ｋであったという本発明者らの測定値とあわせて、この評価は、テストデータセットの統計的挙動のより深い理解は、特に、非重複チャンクが多くちりばめられている重複を含んだ入力データセットに対して、ここで発明された手順よりもさらに性能が優れ得る、他のヒューリスティックスにつながる可能性があることを示唆している。それでもやはり、この１．１テラバイトのテストデータを用いて発見された改善は、本発明が、同様の非理想的な統計的挙動を有する多くの他の現実のデータセットに対してもロバスト性能を達成できることを示唆している。
【００９７】
上述のごとく、種々の実施形態において、本発明はデータ識別及び重複データ除去に使用することができる。それゆえ、好ましいハッシュポイント、カットポイント、バウンダリ（境界：boundary）ポイント、チャンクポイントまたはブレイクポイントの決定に引き続いて、データの決定されたチャンクに対するハッシュ値を生成し、以前に保存されたハッシュ値と比較することができる。種々の実施形態において、本発明はデータ重複除去に特に適用可能である。さらに上述のごとく、本発明は、無線ネットワーク、インターネット、イントラネット、処理され、記憶され、及び／または送信されるデータ列を有するコンピュータシステム及びネットワークを含む、種々の電子システムに等しく適用可能であり、ハッシュ化の使用が有用であることが分かる。本発明が動作できる種々のシステムのいくつかについての説明を以下に与える。
【００９８】
上述のごとく、種々の実施形態において、ここで示されたシステム及び方法は、ここで説明したような動作を実行するようにコンピュータを構成する一連の命令を実行するようにプログラムされた、例えば、パーソナルコンピュータ、サーバ、ミニメインフレームコンピュータ、及び／またはメインフレームコンピュータ等のコンピュータ装置を使用して実現することができる。種々の実施形態において、コンピュータ装置は、例えば、例えばWindows（登録商標）XP（商標）及びＬｉｎｕｘオペレーティングシステムを実行し、標準的な周辺機器群（例えば、キーボード、マウス、表示装置、プリンタ）を備えた、米国テキサス州AustinのDell Computer社などのような、任意の数の民間製造業者から入手可能なパーソナルコンピュータであってもよい。
【００９９】
図１５は、ここで説明したシステム及び方法を実現するソフトウェアアプリケーションプログラムをホストするのに有用であろうコンピュータ装置１５００の一実施形態の機能ブロック図である。ここで図１５を参照すると、コンピュータ装置１５００は、処理装置１５０５、通信インタフェース１５１０、記憶装置１５１５、ユーザインターフェース１５２０、オペレーティングシステム命令１５３５、アプリケーション実行可能命令／ＡＰＩ１５４０を含んでいてもよく、これらはすべて機能的通信において提供され、例えば、データバス１５５０を使用してもよい。コンピュータ装置１５００は、システムメモリ１５５５、データ及びデータ実行可能コード１５６５、ソフトウェアモジュール１５６０、及びインタフェースポートを含んでいてもよい。インタフェースポート１５７０は、プリンタ、スキャナ、一体型のプリンタ／スキャナ／ファクシミリ装置のような、１つ以上の入出力装置１５７５に接続されてもよい。処理装置１５０５は、ここで説明した関数を実現するソフトウェア命令を実行するように構成された、１つ以上のマイクロプロセッサまたはマイクロコントローラであってもよい。アプリケーション実行可能命令／ＡＰＩ１５４０及びオペレーティングシステム命令１５３５は、コンピュータ装置１５００を使用して、記憶装置１５１５、及び／または揮発性メモリ及び不揮発性メモリを含むことができるシステムメモリ１５５５上で記憶されてもよい。アプリケーション実行可能命令／ＡＰＩ１５４０は、本発明のシステム及び方法を実装するソフトウェアアプリケーションプログラムを含んでいてもよい。オペレーティングシステム命令１５３５は、プロセッサ１５０５の基本動作及び制御を制御するのに動作可能なソフトウェア命令を含んでいてもよい。一実施形態において、オペレーティングシステム命令１５３５は、例えば、米国ワシントン州RedmondのMicrosoft Corporationから入手可能なXP（商標）オペレーティングシステムを含んでいてもよい。
【０１００】
命令は、記憶装置のような他のコンピュータ可読媒体からメインメモリに読み込まれてもよい。ここで使用する用語「コンピュータ可読媒体」とは、実行のために処理装置１５０５に対して命令を供給することに係わる任意の媒体を指すことができる。そのような媒体は、不揮発性媒体、揮発性媒体及び伝送媒体を含む多くの形態を取ることができるが、これらに限定されるものではない。不揮発性媒体は、例えば、光ディスクまたは磁気ディスク、サムドライブ(thumb drive)またはジャンプドライブ(jump drive)、及び記憶装置を含んでいてもよい。揮発性媒体は、メインメモリまたはキャッシュメモリのようなダイナミックメモリを含んでいてもよい。伝送媒体は、バス１５５０を有する接続を含む、同軸ケーブル、銅線及び光ファイバを含んでいてもよい。伝送媒体は、無線周波数（ＲＦ）及び赤外線（ＩＲ）データ通信中に生成されるもののような、音波または光波の形態を取ることもできる。コンピュータ可読媒体の一般的な形態として、以下に説明するような、例えば、フロッピーディスク（登録商標）、フレキシブルディスク、ハードディスク、磁気テープ、任意の他の磁気媒体、ユニバーサルシリアルバス（ＵＳＢ；Universal Serial Bus）メモリスティック（登録商標）、ＣＤ−ＲＯＭ、ＤＶＤ、任意の他の光学媒体、ＲＡＭ、ＲＯＭ、ＰＲＯＭ、ＥＰＲＯＭ、フラッシュＥＰＲＯＭ、任意の他のメモリチップまたはカートリッジ、搬送波、コンピュータが読み出すことができる任意の他の媒体が挙げられる。
【０１０１】
コンピュータ可読媒体の種々の形態は、処理装置１５０５に１つ以上の実行命令の１つ以上のシーケンスを運ぶことに関係してもよい。例えば、命令は、最初、リモートコンピュータ１５８５（例えば、サーバ、ＰＣ、メインフレーム等）の磁気ディスク上にあってもよい。リモートコンピュータ１５８５は、そのダイナミックメモリ内に命令をロードし、１つ以上のネットワークインタフェース１５８０を介して、例えば、アナログ、デジタル、ＤＳＬまたはケーブルモデムであってよいモデムに接続された電話回線を使用して、その命令を送ってもよい。ネットワークは、例えば、インターネット及びイントラネット、ピアツーピアネットワーク等であってもよい。コンピュータ装置１５００は、通信インタフェース１５１０を介して接続可能なネットワークインタフェース１５８０を経て、他のコンピュータのネットワークを通して、メッセージを送信し、プログラムコードを含んだデータを受信することができる。サーバは、アプリケーションプログラムの要求されたコードを、ダウンロードされたアプリケーション用に、インターネットを通して送信することができる。受信されたコードは、それが受信されると処理装置１５０５によって実行されることができ、及び／または、後での実行のために記憶装置１５１５または他の不揮発性記憶装置１５５５に保存されることができる。このように、コンピュータ装置１５００は、搬送波の形態でアプリケーションコードを取得することができる。
【０１０２】
本発明のシステム及び方法は、単一のコンピュータ装置またはプラットフォーム１５００、または複数のコンピュータ装置１５００に常駐していてもよく、または異なるアプリケーションが別個のコンピュータ装置１５００に常駐していてもよい。アプリケーション実行可能命令／ＡＰＩ１５４０及びオペレーティングシステム命令１５３５は、ランタイム実行用に、コンピュータ装置１５００の揮発性メモリの１つ以上の割り当てられたコードセグメントにロードされてもよい。一実施形態において、コンピュータ装置１５００は、５１２ＭＢの揮発性メモリ及び８０ＧＢの不揮発性メモリ記憶装置のようなシステムメモリ１５５５を含んでいてもよい。少なくとも一実施形態において、本発明のシステム及び方法のソフトウェア部分は、例えば、Ｃプログラミング言語ソースコード命令を使用して実装されてもよい。他の実施形態も可能である。
【０１０３】
アプリケーション実行可能命令／ＡＰＩ１５４０は、１つ以上のアプリケーションプログラムインターフェース（ＡＰＩ）を含むことができる。本発明のシステム及び方法は、プロセス間通信にＡＰＩ１５４０を使用して、アプリケーション間関数呼び出しを要求し、その呼び出しから戻ることができる。例えば、スクリプトに指定された命令に従って特定データの記憶または検索動作をデータベースに行わせるのに有用な例えばＳＱＬスクリプトの開発を容易にするために、ＡＰＩは、データベース１５６５と関連して提供されてもよい。一般に、ここで説明した関数のいくつかを遂行するようにプログラムされたアプリケーションプログラムの開発を容易にするのに、ＡＰＩを使用することができる。
【０１０４】
通信インタフェース１５１０は、電子メール、ＨＴＭＬまたはＸＭＬのページを含み、これらに限られるものではない、インターネット上の情報を送受信する能力と、ファイル転送能力とをコンピュータ装置１５００に与える。この目的を達成するために、通信インタフェース１５１０は、Microsoft Corporationによって提供されるMicrosoft Internet Explorer（登録商標）等であってこれらに限定されるものではない、ウェブブラウザをさらに含むことができる。ユーザインターフェース１５２０は、コンピュータ端末表示装置、キーボード、及びマウス装置を含んでいてもよい。対話型のＨＴＭＬまたはＸＭＬページに含まれるデータの表示及び操作に備えた、１つ以上のグラフィカルユーザインタフェース（ＧＵＩ；Graphical User Interface）も含むことができる。
【０１０５】
ここで図１６を参照すると、システム及び方法が動作できるネットワーク１６００が示されている。上述したように、本特許出願のシステム及び方法は、１つ以上のコンピュータで動作可能である。ネットワーク１６００は、１つ以上のクライアントデータ記憶部１６１０に接続された１つ以上のクライアント１６０５を含むことができる。１つ以上のクライアントは、通信ネットワーク（例えば、光ファイバ、電話回線、無線等）を介して通信フレームワーク１６３０に接続することができる。通信フレームワーク１６３０は、例えば、インターネット及びイントラネット、ピアツーピアネットワーク、ＬＡＮ、アドホックのコンピュータ間ネットワーク等であってもよい。ネットワーク１６００は、通信フレームワーク１６３０に接続され、サーバデータ記憶部１６２０に接続された１つ以上のサーバ１６１５も含むことができる。本発明のシステム及び方法は、完全な機能システム及び方法として動作するように、ネットワーク１６００の１つ以上のコンポーネント上で機能する部分を備えていてもよい。
【０１０６】
本発明の実施形態を上で説明したが、当業者には多くの代替、変更及び変形が明らかなことは明白である。一般に実施形態は、データの分析が行われるこれら及び他のビジネスプロセスの自動化に関するものであってもよい。したがって、本発明の実施形態は、上で説明したように、例示となるように意図したものであり、本発明の範囲の制限として解釈されるべきではない。種々の変更を、本発明の精神及び範囲から逸脱することなく行うことができる。したがって、本発明の範囲は、上に示した実施形態ではなく、ここで添付した請求項及びそれらの法的な等価物によって決定されるべきである。
【０１０７】
出版物、特許、及びここで引用した特許出願はすべて、あらゆる目的のためにそれらの全体が参照することによりここで援用される。
【０１０８】
［関連する出願の相互参照］
本特許出願は、２００６年１２月１日に申請され、Cezary Dubnicki，Erik Kruus，Cristian Ungureanu及びKrzysztof Lichotaに付与された、「METHODS AND SYSTEMS FOR DATA MANAGEMENT USING MULTIPLE SELECTION CRITERIA」と題する、米国特許出願番号第（ＴＢＤ）号に関し、そしてそれは、すべての目的のために参照することによりここで援用される。
【０１０９】
本開示は、著作権保護の対象となる情報、例えば本明細書に挙げた種々の擬似コード、コード、または１つ以上のコンピュータプログラムを含んでいてもよい。著作権者は、米国特許商標局のファイルまたは記録にある限り、何人が本特許開示内容または本特許をファクシミリ複製しようと異議を唱えないが、それ以外の全著作権を留保する。
【図１】
2010515114.tif 000015
【図２】
2010515114.tif 000016
【図３ａ】
2010515114.tif 000017
【図３ｂ】
2010515114.tif 000018
【図４ａ】
2010515114.tif 000019
【図４ｂ】
2010515114.tif 000020
【図５ａ】
2010515114.tif 000021
【図５ｂ】
2010515114.tif 000022
【図６ａ】
2010515114.tif 000023
【図６ｂ】
2010515114.tif 000024
【図６ｃ】
2010515114.tif 000025
【図７ａ】
2010515114.tif 000026
【図７ｂ】
2010515114.tif 000027
【図８】
2010515114.tif 000028
【図９ａ】
2010515114.tif 000029
【図９ｂ】
2010515114.tif 000030
【図９ｃ】
2010515114.tif 000031
【図１０】
2010515114.tif 000032
【図１１】
2010515114.tif 000033
【図１２】
2010515114.tif 000034
【図１３】
2010515114.tif 000035
【図１４】
2010515114.tif 000036
【図１５】
2010515114.tif 000037
【図１６】
2010515114.tif 000038
【国際調査報告】
2010515114.tif 000039
2010515114.tif 000040