(57)【要約】【課題】データ構造におけるノード分割を改善したノード分割方法を提供する。【解決手段】ノードへのエントリのハッシュの少なくとも一部に基づいてノードの分割ポイントを決定し、決定した分割ポイントに基づいてノードを分割するものである。【選択図】図３
2010079888.tif 000002
【特許請求の範囲】
【請求項１】
コンテンツ定義のノード分割方法であって、
ノードへのエントリのハッシュの少なくとも一部に基づいて該ノードの分割ポイントを決定し、
決定した分割ポイントに基づいて前記ノードを分割する、ノード分割方法。
【請求項２】
前記分割ポイントを求めて前記ノードの少なくとも一部を検索することをさらに含む請求項１に記載のノード分割方法。
【請求項３】
前記分割ポイントを求めて前記ノードの少なくとも一部を検索することは、一意の分割ポイントを求めて事前に定められた検索領域を検索することを含み、前記ノードへのエントリのハッシュの少なくとも一部に基づいて該ノードの分割ポイントを決定することは、前記決定した分割ポイントとして前記一意の分割ポイントを設定することをさらに含む、請求項２に記載のノード分割方法。
【請求項４】
前記一意の分割ポイントを求めて事前に定められた検索領域を検索することは、最初に遭遇する分割ポイントを求めて該所定の領域を検索することを含む請求項３に記載のノード分割方法。
【請求項５】
前記ノードへのエントリのハッシュの少なくとも一部に基づいて該ノードの分割ポイントを決定することは、所定の条件を満足させる、前記ノードへのエントリのハッシュの所定のビットマスクを求めて該ノードの少なくとも一部を検索することを含む請求項１に記載のノード分割方法。
【請求項６】
ビットの設定された前記ノードの検索された部分の２を底とする対数の大きさを有するビットマスクとして、前記所定のビットマスクを設定することをさらに含む請求項５に記載のノード分割方法。
【請求項７】
前記所定の条件は、０となるビットを示すエントリのハッシュの所定のビットマスクを有する、請求項５に記載のノード分割方法。
【請求項８】
機械読み取り可能な媒体に保存された、プロセッサにより実行可能なプログラム命令を有する機械読み取り可能な媒体であって、該命令が、
ノードへのエントリのハッシュの少なくとも一部に基づいて該ノードの分割ポイントを決定するステップと、
決定した分割ポイントに基づいて前記ノードを分割するステップと、
を規定する、機械読み取り可能な媒体。
【請求項９】
前記命令は、
前記分割ポイントを求めて前記ノードの少なくとも一部を検索する命令をさらに規定する、請求項８に記載の機械読み取り可能な媒体。
【請求項１０】
前記分割ポイントを求めて前記ノードの少なくとも一部を検索する前記命令は、最初に遭遇する分割ポイントを求めて事前に定められた検索領域を検索する命令を含み、
前記ノードへのエントリのハッシュの少なくとも一部に基づいて前記ノードの分割ポイントを決定する前記命令は、前記決定した分割ポイントとして前記最初に遭遇する分割ポイントを設定する命令をさらに含む、請求項９に記載の機械読み取り可能な媒体。
【請求項１１】
前記命令は、
所定の選択基準を満足させる、前記ノードへのエントリのハッシュの所定のビットマスクを求めて該ノードの少なくとも一部を検索するステップをさらに有する、請求項８に記載の機械読み取り可能な媒体。
【請求項１２】
前記命令は、
２ビットを底とする前記ノードの検索された部分の大きさの対数を有するビットマスクとして、前記所定のビットマスクを設定するステップをさらに有する、請求項１１に記載の機械読み取り可能な媒体。
【請求項１３】
前記命令は、
ノードエントリのハッシュの所定のビットマスクを該ノードエントリの算出されたハッシュと比較して０となるビットを決定するステップをさらに規定する、請求項１１に記載の機械読み取り可能な媒体。
【請求項１４】
コンテンツ定義のノードを分割する装置であって、
ノードへのエントリのハッシュの少なくとも一部に基づいて該ノードの分割ポイントを決定する手段と、
決定した分割ポイントに基づいてノードを分割する手段と、
を有する装置。
【請求項１５】
前記分割ポイントを求めて前記ノードの少なくとも一部を検索する手段をさらに有する請求項１４に記載の装置。
【請求項１６】
前記分割ポイントを求めて前記ノードの少なくとも一部を検索する前記手段は、最初に遭遇する分割ポイントを求めて所定の検索領域を検索する手段を有し、前記ノードへのエントリのハッシュの少なくとも一部に基づいて該ノードの分割ポイントを決定する前記手段は、前記決定した分割ポイントとして前記最初に遭遇する分割ポイントを設定する手段をさらに有する請求項１５に記載の装置。
【請求項１７】
前記ノードへのエントリのハッシュの少なくとも一部に基づいて該ノードの分割ポイントを決定する前記手段は、
所定の選択基準を満足させる、前記ノードのチャンクのハッシュの所定のビットマスクを求めて該ノードの少なくとも一部を検索する手段を有する、請求項１４に記載の装置。
【請求項１８】
２ビットを底とする前記ノードの検索された部分の大きさの対数を有するビットマスクとして、前記所定のビットマスクを設定する手段をさらに有する請求項１７に記載の装置。
【請求項１９】
ノードエントリのハッシュの前記所定のビットマスクを選択して０となるビットを決定する手段をさらに有する請求項１７に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般にデータ構造におけるノード分割に関し、特にデータ構造におけるコンテンツ定義のノード分割に関する。
【背景技術】
【０００２】
従来のバックアップシステムでは、大量（例えば、テラバイト）の入力データがインデックスを付けられて保存される必要がある。データ（例えば、ディレクトリ、ファイル、データシーケンス、データチャンク等）に関するメタデータ（例えば、基礎となるデータのインデックス、ノード等）を保存するのにツリー構造のようなデータ構造が用いられる。大きなファイルシステムのバックアップシステムでは、これらのデータ構造は、ファイルデータの固定サイズまたは可変サイズのチャンクを順序付けられた配列で配置している。すなわち、基礎となるファイルデータは、関連付けられた複数のファイルオフセットを伴った入力ストリームからのチャンクのバイトの配列であり、メタデータツリーは、順序付けられた配列にチャンクのアドレスを配置している。このような方法で、基礎となるデータの位置ならびに同様に予備のファイルおよびディレクトリに関する情報の位置が常に保存され、適切な順序で検索を行うことを可能にしている。
【０００３】
多くの用途（例えば、バックアップまたはアーカイブ）では、同一またはほぼ類似したコンテンツに対応するメタデータ構造が生成され、保存されていなければならない。例えば、同一のファイルシステムを保存のために２度送信してもよいが、コンテンツの挿入順序は、（例えば、データ伝送における可変遅延によって）異なってもよい。あるいは、わずかに変更のある大きなファイルシステムを後でバックアップしてもよい。同一または非常に類似した、基礎となるデータに対応する２つのメタデータツリーを保存すること、および同一でない多数のノードを持つメタデータ構造を保存することは、保存コストを増加させる。相応して大きな度合いの同一のノードを持つメタデータ構造を実現することは、これが時間または保存装置の資源の面で非常に高価になる可能性があるので、データ構造のノードのリバランシングが必要となる。
【０００４】
一般に、コンテンツ定義のデータチャンク化システムは、標準のデータ構造を用いてチャンクハッシュ情報（例えば、メタデータ）の配列を保存する。メタデータの配列は、基礎となる、保存されたコンテンツに関する順序を誘導するメタデータノードの大きなデータ構造（例えば、シーケンス、リスト、ツリー、Ｂ＋ツリー等）として維持されている。データアーカイブシステムでは、これらのデータ構造は、絶え間なく保存され、オンライン「ストリーミング」環境で動作する必要がある。これらのデータ構造の詰め込みすぎを防止するために、ノード分割方式が起動され、ノードエントリの最大数を制限しながら合理的な平均的ノード詰め込みを実現する。
【０００５】
例えば、従来のＢ＋ツリーは中間点分割のノード分割方式を用いることができる。データ構造が昇順の挿入順序で２つのオケージョンに成長し、２つのオケージョンのうち第２のオケージョンに追加データ項目がある場合、追加データ項目の後側のすべての分割ポイントを、第１のオケージョンに用いられた分割ポイントに対して、１つ分の位置だけ移動させることが可能となる。したがって、異なる分割ポイントで生成されたノードは同一のエントリを含まず、それらは２つのデータ構造において厳密には重複にならない。
【０００６】
同一コンテンツの挿入順序を変化させる代表的な他の例では、単一のデータ項目がデータ構造の元のリーフノードから取り除かれて後方ポイントに挿入される場合、異なって分割されたノードを結果的に生じさせることがある。元のリーフノードがその最終的形態で生成された後に遅延挿入が発生しても、新しいツリーが元のツリーと比較されるときに、除去ポイントから挿入ポイントまでのすべてのノードが異なっていてもよい。従来の分割方式を用いたツリーノードのコンテンツは挿入順序に依存している。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
典型的なノード分割方式では、複数の、順序誘導データ構造が保存されるとき、基礎となるデータまたは挿入順序の小さな変化が多数の非重複ノードを発生させる結果となり得る。したがって、データ構造におけるノード分割を改善したシステムおよび方法が必要とされる。
【０００８】
本発明は、データ構造におけるノード分割を改善したノード分割方法および装置を提供するものである。
【課題を解決するための手段】
【０００９】
本発明のノード分割方法、装置、および機械読み取り可能な媒体は、ノード領域を検索してコンテンツ定義の分割ポイントが決定されるものである。ノードの分割ポイントが、そのノードへのエントリ（例えば、チャンク、サブノード等）のハッシュの少なくとも一部に基づいて決定され、そのノードは、決定した分割ポイントに基づいて分割される。
【００１０】
また、ノードの検索領域は、一意の（例えば、最初の）遭遇分割ポイントを求めて検索されてもよい。そのノードはその分割ポイントに基づいて分割される。さらに、その分割ポイントは、通常、ノードへのエントリのハッシュの所定のビットマスクを所定の値（例えば、０）と比較することに基づいて決定されてもよい。
【００１１】
本発明のこれらおよびその他の利点は、以下の詳細な説明および添付の図面を参照することにより当業者に明白になるであろう。
【発明の効果】
【００１２】
本発明によれば、非重複ノードを低減でき、保存コストを下げることができる。
【図面の簡単な説明】
【００１３】
【図１】保存システムのダイアグラムの一例を示す図である。
【図２】本発明の実施形態によるファイルシステムの一例を示す図である。
【図３】保存されたコンテンツ中の小さな差異を示したコンテンツ定義のノード分割と従来のノード分割とを比較したダイアグラムである。
【図４】同一であるが異なる挿入順序を持つコンテンツを保存する効果を示した、コンテンツ定義のノード分割と従来のノード分割とを比較したダイアグラムである。
【図５】本発明の実施形態によるコンテンツ定義のノード分割方法のフローチャートである。
【図６】本発明の実施形態による典型的なコンテンツ定義のノード分割方式を示す。
【発明を実施するための形態】
【００１４】
コンテンツアドレス可能保存（Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｓｔｏｒａｇｅ：ＣＡＳ）システムは、位置の代わりにコンテンツに基づいて検索可能な情報を保存する。図１は保存システム１００のダイアグラムである。本発明の少なくとも１つの実施形態では、ここで説明するノード分割方法は、保存システム１００のような保存システムで実行される。そのような保存システムの実施は、２００８年３月５日に出願された、「コンテンツアドレス可能な保存のシステムおよび方法（Ｓｙｓｔｅｍ  ａｎｄ  Ｍｅｔｈｏｄ  ｆｏｒ  Ｃｏｎｔｅｎｔ  Ａｄｄｒｅｓｓａｂｌｅ  Ｓｔｏｒａｇｅ）」と題する米国特許出願番号第１２／０４２，７７７号に関してさらに詳細に記載されており、この出願明細書に記載された内容は参照により本明細書に組み込まれている。
【００１５】
保存システム１００は、データ操作（例えば、ファイル書き込み、ファイル読み取り等）およびメタデータ操作（例えば、ファイル削除等）を受け取り、受け取ったデータを、ブロック保存装置１０４へ保存されるデータブロックにチャンクするファイルサーバ１０２を有している。ブロック保存装置１０４は、データおよびメタデータのブロックを保存しており、図２から図５についてさらに詳細に後述するように、そのブロックのいくつかは他のブロックを指していてもよく、ファイルシステム１０６を記述するように体系付けられていてもよい。
【００１６】
本説明のコンテキストでは、メタデータはファイルコンテンツでない、あらゆるデータである。例えば、メタデータは、ファイルまたはディレクトリ名、ファイル生成時間、ファイルサイズ、ファイルパーミッション等のような、クライアントによって見ることが可能な１つまたは２つ以上のファイルに関する情報であってもよく、および／または、インデクシング構造、ファイルオフセット等のような、クライアントによって見ることのない１つまたは２つ以上のファイルおよび／またはファイルシステムに関する情報であってもよい。当然、他の適切なメタデータ（例えば、データに関する情報、１つまたは２つ以上のファイル、１つまたは２つ以上のデータブロック、１つまたは２つ以上のデータ構造、１つまたは２つ以上のファイルシステム、ビットマップ等）を用いることも可能である。
【００１７】
ファイルサーバ１０２は、データ（例えば、情報、ドキュメント、ファイル等）の保存位置を提供するように構成され、かつ、クライアントに接続された、任意のコンピュータまたは他の装置であってもよい。したがって、ファイルサーバ１０２は保存装置および／または記憶装置を備えていてもよい。さらに、ファイルサーバ１０２はデータをデータブロックにチャンクする（例えば、データブロックを生成する）。すなわち、ファイルサーバ１０２は、ＣＡＳにおける保存可能な方法で、クライアントデータおよび／またはそうでなければグループデータとメタデータとからデータブロック（例えば、チャンク）を生成し、これらのデータおよびメタデータブロックをブロック保存装置１０４に書き込む。
【００１８】
ブロック保存装置１０４は、ファイルサーバ１０２に対して、データブロックを以前に見た（例えば、知られた、保存された等）データブロックと認識してそのコンテンツアドレスを返してもよく、または、データブロックを新しいブロックと認識してそれ用のコンテンツアドレスを生成し、コンテンツアドレスを返してもよい。書き込みが完了したという確認と共に受け取られるコンテンツアドレスは、データブロックを再フェッチする際に使用することが可能である。
【００１９】
ブロック保存装置１０４は、ＣＡＳシステムまたは他の適切な記憶システムまたは保存システムであってもよい。少なくとも一実施形態では、ブロック保存装置１０４は、２００８年１月３１日に出願された米国特許出願番号第１２／０２３，１３３号、および２００８年１月３１日に出願された米国特許出願番号第１２／０２３，１４１号に記載されているような、クラスターベースのコンテンツアドレス可能なブロック保存システムであり、それらの出願明細書に記載された内容は参照により本明細書に組み込まれている。当然、他のアドレスベースの保存システムを利用することも可能である。ブロック保存装置１０４は、ファイルシステム１０６として体系付けられることが可能なデータブロックを含んでいる。図２から図５についてさらに詳細に後述するように、ファイルシステム１０６はツリー構造として表すことができるデータ構造である。
【００２０】
保存システム１００は、この保存システム１００の全体的な動作を規定したコンピュータプログラム命令を実行することによって、その動作を制御するプロセッサ（図示せず）を持っていてもよい。同一または代替の実施形態では、ファイルサーバ１０２および／またはブロック保存装置１０４のそれぞれは、保存システム１００の少なくとも一部の動作を規定したコンピュータプログラム命令を実行することによって、その動作を制御する、制御装置、プロセッサ、または他のデバイスを持っていてもよい。コンピュータプログラム命令は、保存装置（例えば、磁気ディスク、データベース等）に保存され、および／または、コンピュータプログラム命令の実行が望まれるときにメモリにロードされることが可能である。したがって、方法５００における、データ保存、ノード分割等のような、ここで説明される保存システム１００の方法のステップおよび関連する機能を実行するためのアプリケーションは、メモリに保存されたコンピュータプログラム命令によって規定され、コンピュータプログラム命令を実行するプロセッサによって制御される。保存システム１００は、１つまたは２つ以上の中央処理装置、読み取り専用記憶（ＲＯＭ）装置、および／またはランダムアクセス記憶（ＲＡＭ）装置を含んでいてもよい。実際のコンテンツアドレス可能な保存システムの実施は他の構成要素を含むことを可能とし、また、図１の保存システム１００が例示を目的としたそのような保存システムのいくつかの構成要素のハイレベルの表現であることは、当業者には認識されるであろう。
【００２１】
本発明のいくつかの実施形態によれば、プログラム（例えば、制御装置ソフトウェア）の命令は、ＲＯＭ装置からＲＡＭ装置へ、またはＬＡＮアダプタからＲＡＭ装置へのように、ファイルサーバ１０２および／またはブロック保存装置１０４に読み込まれてもよい。プログラム中の命令シーケンスの実行は、方法５００について後述する方法のステップのように、ここで説明した１つまたは２つ以上の方法のステップを、保存システム１００に実行させてもよい。他の実施形態として、本発明のプロセスを実行するために、ハードウェアに組み込まれた回路または集積回路をソフトウェア命令の代わりに、またはソフトウェア命令と組み合わせて用いることが可能である。したがって、本発明の実施形態は、ハードウェア、ファームウェア、および／またはソフトウェアの任意の特定の組み合わせに限定されるものではない。ブロック保存装置１０４は、ソフトウェアプログラムを実行することによって本発明にしたがって動作する、特に、後で詳細に説明する方法にしたがって動作するように適合された、保存システム１００用のソフトウェアを保存してもよい。しかしながら、ここで説明しているような本発明が汎用のハードウェアサブシステムまたは専用の制御装置だけでなく多種多様のプログラミング技法を用いて、多くの異なる方法で実施できるであろうことは当業者には理解されるであろう。
【００２２】
それらのプログラムは、圧縮、非コンパイル、および／または暗号化フォーマットで保存されてもよい。それらのプログラムは、制御装置がコンピュータ周辺機器および他の装置／構成要素と接続することを可能にする、オペレーティングシステム、データベース管理システム、およびデバイスドライバのような、一般に有用なプログラム要素をさらに含んでいてもよい。適切な汎用のプログラム要素は当業者に知られているので、それについてここで詳細に説明する必要はないであろう。
【００２３】
コンテンツ定義のノード分割方法は、基礎となるデータコンテンツに基づいて擬似乱数的にノード分割ポイントを選択する。一般に、コンテンツ定義のノード分割ポイントに必要な所与の基準を満足させる一意の要素は、所与の検索領域で選択される。したがって、可能性のある分割ポイントとして、任意の所与の要素が選択される確率は低い。
【００２４】
単一のデータ項目の挿入が分割ポイントの決定に影響を及ぼす可能性は低い。したがって、２つのツリー成長間の差異は、おそらく単一のリーフノードおよびルートへの関連するパス内に含まれるであろう。たとえ単一のデータ項目の挿入がノード分割ポイントの決定に影響を及ぼしたとしても、２つのツリーはおそらく次の成長で再度同期する。
【００２５】
同様に、単一のデータ項目の挿入順序がコンテンツ定義のノード分割中に変更された場合、その項目がコンテンツ定義のノード分割ポイントになる可能性は低い。ノード分割決定の前に発生する、挿入時間の差がほとんどない場合、同一の２つのツリーが結果として生じることになる。しかしながら、２つのデータ項目の挿入時間が十分に離れている場合、コンテンツ定義のノード分割を用いて成長するツリーは、影響を受けない中間ノードを持つ確率が高く、局所的なノード変更を示す確率が高い。
【００２６】
図２は本発明の実施形態によるファイルシステム２００を示している。ファイルシステム２００は、ここで説明したような、データ構造、データツリー、データリストまたは他のデータ、メタデータ、チャンク、ブロック、および／またはハッシュ保存装置であってもよい。
【００２７】
一般に、ファイルシステム２００は、高ファンアウトのＢ＋ツリーのようなデータ構造に配置された、一連のノード２０２を含んでいる。したがって、保存構造の当業者には理解されるように、ノード２０２は最終的にルート（ｒｏｏｔ）２０４に接続される。次に、ファイルシステム２００は、任意の適正な数のノード２０２を持つことが可能である。すなわち、ファイルシステム２００が成長するにつれて、適正な数のノード２０２が追加および／または満たされる。各ノード２０２は、多くのエントリ（例えば、スロット、ブロック、チャンク等）２０６を含んでいる。データ構造において知られているように、任意の数の、ノード２０２および／またはエントリ２０６のレイヤーがあってもよい。
【００２８】
少なくとも一実施形態では、エントリ２０６は、他のエントリ２０６、ノード２０２、および／またはデータを記述する、データおよび／またはメタデータのハッシュである。以下では、そのような順序誘導データ構造で用いられるノード内のエントリはチャンクと呼ばれ、異なるコンテキストでは、チャンクは異なる論理的な構成要素（例えば、他のデータ構造のノード、ディレクトリ、ファイル、ファイルコンテンツ、ｉノード、ファイル属性等）を表すことができると理解する。
【００２９】
図３および図４において、ノード分割方式をデータ構造へのデータの挿入に適用するものとして説明する。なぜなら、この状況がＣＡＳを用いたバックアップアプリケーションに対して最も重要だからである。しかしながら、２つの（または３つ以上の）連続するノードの合併されたノードエントリにノード分割操作を適用する（できる限り繰り返して）ことによって、ノードがアンダフロー状態中、動作が削除中に、これらの方式を適用し、所望の範囲内に多くのエントリを含んだ置換ノードを生成することも可能である。
【００３０】
図３は、コンテンツ定義のノード分割とその比較として従来のノード分割の例であり、それぞれダイアグラム３００Ａおよび３００Ｂを示している。ダイアグラム３００Ａは、理想的にソートされた挿入配列３０２Ａに関して、従来のノード分割とコンテンツ定義のノード分割との比較を示している。ダイアグラム３００Ｂは、追加のチャンク３２４がソートされた挿入配列３０２Ｂ内に理想的に存在する、コンテンツ定義のノード分割と、従来のノード分割の比較を示している。ノード分割のプロセスについては、方法５００および図５についてさらに詳細に後で説明する。
【００３１】
列３０６は、チャンクの特定の挿入順序を示している。列３０８は、特定の従来のノード分割方法を適用した結果を示している。列３１６は、本発明の一実施形態による特定のコンテンツ定義のノード分割方法を適用した結果を示している。
【００３２】
ダイアグラム３００Ａにおいて、挿入配列３０２Ａは複数のメタデータチャンク３０４ａから３０４ｈを含んでいる。ダイアグラム３００Ａでは、挿入配列３０２Ａが８つのチャンク（例えば、チャンク３０４ａから３０４ｈ）を持つように示されているが、挿入配列は任意の数のチャンクを持っていてもよい。
【００３３】
挿入配列３０２Ａは、図２のノード２０２および／またはエントリ２０６のような、ノードに保存されるデータおよび／またはメタデータの挿入順序を表している。同様に、チャンク３０４ａから３０４ｈは、ノード２０２／３０２Ａに保存されたハッシュを表している。
【００３４】
列３０６の第１行は、図示のように正しい順序で挿入されてノードを形成する、任意の分割以前の挿入配列３０２Ａのチャンク３０４ａから３０４ｈを示している。図５に関してさらに詳細に後で説明するコンテンツ定義の基準によれば、チャンク３０４ｃおよび３０４ｇ（塗りつぶされたブロックとして示されている）は、適格なコンテンツ定義の分割ポイントである。すなわち、挿入配列３０２Ａは、次のチャンクが新しいノードに移動されるように、チャンク３０４ｃおよび３０４ｇのそれぞれの後で分割され得る。
【００３５】
列３０８の第１行は、従来のノード分割基準を用いてノード３１０、３１２、および３１４に分割された挿入配列３０２Ａを示している。この例では、挿入配列３０２Ａは３番目毎のチャンクの後で分割される。それゆえ、ノード３１０はチャンク３０４ａから３０４ｃを含み、ノード３１２はチャンク３０４ｄから３０４ｆを含み、ノード３１４はチャンク３０４ｇおよび３０４ｈを含んでいる。
【００３６】
列３１６の第１行は、図５に関して後で説明するコンテンツ定義のノード分割方法５００を用いて、ノード３１８、３２０、および３２２に分割された挿入配列３０２Ａを示している。この例では、挿入配列３０２Ａは各適格なコンテンツ定義の分割ポイントの後で分割される。すなわち、挿入配列３０２Ａは、チャンク３０４ａから３０４ｃがノード３１８を形成し、チャンク３０４ｄから３０４ｇがノード３２０を形成し、チャンク３０４ｈだけでなく次の適格なコンテンツ定義の分割ポイントまでのチャンクも含んだノード３２２を形成するように、チャンク３０４ｃおよび３０４ｇのそれぞれの後で分割される。
【００３７】
ダイアグラム３００Ｂでは、挿入配列３０２Ｂは、図示の順序で挿入されてデータ構造にノードを形成する、複数のメタデータチャンク３０４ａから３０４ｈを含んでいる。さらに、新しいチャンク３２４が、その適切な（例えば、理想的な、ソートされた）順序で配置されて、挿入配列３０２Ｂに存在している。典型的な例を説明するために、ダイアグラム３００Ｂでは、チャンク３２４がチャンク３０４ｂと３０４ｃとの間にあるように示されているが、当業者であれば、操作の最中は、追加のチャンクはノードの任意のポイントにあってもよいことが認識されるであろう。ダイアグラム３００Ｂでは、挿入配列３０２Ｂが９つのチャンク（例えば、チャンク３０４ａから３０４ｈ、および３２４）を持つように示されているが、挿入配列は任意の数のチャンクを持っていてもよく、２つ以上のチャンクが追加および／または削除されてもよい。
【００３８】
挿入配列３０２Ｂは、図２のノード２０２および／またはエントリ２０６のようなノードに保存される、データ、サブノード、および／またはメタデータを表している。挿入配列３０２Ｂは、挿入配列３０２Ｂがチャンク３２４（×印されたボックスとして示されている）を含んでいるという点を除いて、挿入配列３０２Ａと等価である。同様に、チャンク３０４ａから３０４ｈ、および３２４は、図２のノード２０２に保存されたハッシュを表している。
【００３９】
列３０６の第２行は、任意の分割以前の挿入配列３０２Ｂのチャンク３０４ａから３０４ｈを示している。図５に関してさらに詳細に後で説明するコンテンツ定義の基準によれば、チャンク３０４ｃおよび３０４ｇ（塗りつぶされたブロックとして示されている）は、適格なコンテンツ定義の分割ポイントである。すなわち、挿入配列３０２Ｂは、チャンク３０４ｃおよび３０４ｇのそれぞれの後で分割されてもよく、そのような分割の後で、次のチャンクが新しいノードに移動されてもよい。
【００４０】
列３０８の第２行は、従来のノード分割基準を用いてノード３２６、３２８、および３３０に分割された挿入配列３０２Ｂを示している。この例では、挿入配列３０２Ｂは、チャンク３０４ａから３０４ｈの３番目毎のチャンクおよび新しく挿入されたチャンク３２４の後で分割される。そのため、ノード３２６はチャンク３０４ａ、３０４ｂ、および３２４を含み、ノード３２８はチャンク３０４ｃから３０４ｅを含み、ノード３３０はチャンク３０４ｆから３０４ｈを含んでいる。なお、ノード３１０、３１２、３１４のどれもノード３２６、３２８、および３３０と一致しないことに注意されたい。
【００４１】
列３１６の第２行は、図５に関して後で説明するコンテンツ定義のノード分割方法５００を用いて、ノード３３２、３３４、および３３６に分割された挿入配列３０２Ｂを示している。この例では、挿入配列３０２Ｂは各適格なコンテンツ定義の分割ポイントの後で分割される。すなわち、チャンク３０４ａから３０４ｃおよびチャンク３２４がノード３３２を形成し、チャンク３０４ｄから３０４ｇがノード３３４を形成し、チャンク３０４ｈだけでなく次の適格なコンテンツ定義の分割ポイントまでのチャンクも含んだノード３３６を形成するように、挿入配列３０２Ｂは、チャンク３０４ｃおよび３０４ｇのそれぞれの後で分割される。なお、ノード３１８、３２０、および３２２をノード３３２、３３４、および３３６と比較すると、挿入されたチャンク３２４を含んだノード３３２のみが変更されていることに注意されたい。
【００４２】
図４は、コンテンツ定義のノード分割とその比較としての従来のノード分割の例であり、それぞれダイアグラム４００Ａおよび４００Ｂを示している。ダイアグラム４００Ａは、挿入配列４０２Ａに示すようにソートされた順序で、追加のチャンク４０６が理想的に配置された、従来のノード分割とコンテンツ定義のノード分割との比較を示している。ダイアグラム４００Ｂは、挿入配列４０２Ｂに示すように、従来のノード分割と、同じ追加のチャンク４０６が配列の外に配置された、コンテンツ定義のノード分割との比較を示している。ノード分割のプロセスについては、方法５００および図５に関してさらに詳細に後で説明する。
【００４３】
列４０８は、チャンクの特定の挿入順序を示している。列４１０は、特定の従来のノード分割方法を適用した結果を示している。列４１８は、本発明の一実施形態による特定のコンテンツ定義のノード分割方法を適用した結果を示している。
【００４４】
ダイアグラム４００Ａおよび４００Ｂにおいて、挿入配列４０２Ａおよび４０２Ｂのそれぞれは複数のメタデータチャンク４０４ａから４０４ｈを含んでいる。さらに、新しいチャンク４０６（×印されたボックスとして示されている）は、その適切な位置で挿入配列４０２Ａに置かれているが、４０２Ｂでは順序が間違って遅延位置に置かれている。典型的な例を説明するために、ダイアグラム４０２Ａでは、チャンク４０６はチャンク４０４ｂと４０４ｃ間にあるように示されているが、当業者であれば、操作の最中は、そのようなチャンクは、最初に挿入配列の任意のポイントにあってもよいことが認識されるであろう。ダイアグラム４００Ａでは、挿入配列４０２Ａが９つのチャンク（例えばチャンク４０４ａから４０４ｈ、および４０６）を持つように示されているが、挿入配列は任意の数のチャンクを持っていてもよく、２つ以上のチャンクが追加されてもよく、および配列４０２Ｂの次のポイントまで遅延された挿入を持っていてもよい。
【００４５】
列４０８の第１行は、挿入配列４０２Ａのチャンク４０４ａから４０４ｈ、およびチャンク４０６の挿入順序を示している。この挿入順序はチャンクの最終順序付けと等価である。図５に関してさらに詳細に後で説明するコンテンツ定義の基準によれば、チャンク４０４ｃおよび４０４ｇ（塗りつぶされたブロックとして示されている）は、適格なコンテンツ定義の分割ポイントである。すなわち、挿入配列４０２Ａは、すべての次のチャンクが新しいノードに移動されるように、チャンク４０４ｃおよび４０４ｇのそれぞれの後で分割され得る。
【００４６】
列４１０の第１行は、従来のノード分割基準を用いてノード４１２、４１４、および４１６に分割された挿入配列４０２Ａを示している。この例では、挿入配列４０２Ａは、チャンク４０４ａから４０４ｈの３番目毎のチャンクおよび新しく挿入されたチャンク４０６の後で分割される。そのため、ノード４１２はチャンク４０４ａ、４０４ｂ、および４０６を含み、ノード４１４はチャンク４０４ｃから４０４ｅを含み、ノード４１６はチャンク４０４ｆから４０４ｈを含んでいる。
【００４７】
列４１８の第１行は、図５に関して後で説明するコンテンツ定義のノード分割方法５００を用いて、ノード４２０、４２２、および４２４に分割された挿入配列４０２Ａを示している。この例では、挿入配列４０２Ａは各適格なコンテンツ定義の分割ポイントの後で分割される。すなわち、チャンク４０４ａから４０４ｃおよびチャンク４０６がノード４２０を形成し、チャンク４０４ｄから４０４ｇがノード４２２を形成し、チャンク４０４ｈだけでなく次の適格なコンテンツ定義の分割ポイントまでのチャンクを含んだノード４２４を形成するように、挿入配列４０２Ａは、チャンク４０４ｃおよび４０４ｇのそれぞれの後で分割される。
【００４８】
ダイアグラム４００Ｂにおいて、挿入配列４０２Ｂは、適切な順序で複数のチャンク４０４ａから４０４ｈを含んでいる。しかしながら、追加のチャンク４０６は、順序が間違って挿入配列４０２Ｂに置かれている。典型的な例を説明するために、ダイアグラム４００Ｂでは、チャンク４０４ｈの後にチャンク４０６が示されているが、当業者であれば、操作の最中は、そのようなチャンクは挿入配列の任意のポイントにあってもよいことが認識されるであろう。ダイアグラム４００Ｂでは、挿入配列４０２Ｂが９つの挿入（例えばチャンク４０４ａから４０４ｈ、および４０６）の配列を持つように示されているが、挿入配列は任意の数のチャンクを持っていてもよく、２つ以上のチャンクが、順序が間違って置かれていてもよい。
【００４９】
挿入配列４０２Ｂは、図２のノード２０２および／またはエントリ２０６のようなノードに保存される、データおよび／またはメタデータを表している。挿入配列４０２Ｂは、その挿入配列４０２Ｂが配列から外れて（例えば、挿入配列４０２Ａのような理想的にソートされた順序ではではない）置かれたチャンク４０６（×印されたボックスとして示されている）を持っているという点を除いて、挿入配列４０２Ａと等価である。同様に、４０２Ｂのチャンク４０４ａから４０４ｈ、および４０６は、ノード２０２に保存されるコンテンツのハッシュを表している。
【００５０】
列４０８の第２行は、挿入配列４０２Ｂのチャンク４０４ａから４０４ｈ、およびチャンク４０６を示している。図５に関してさらに詳細に後で説明するコンテンツ定義の基準によれば、チャンク４０４ｃおよび４０４ｇ（塗りつぶされたブロックとして示されている）は、適格なコンテンツ定義の分割ポイントである。すなわち、挿入配列４０２Ｂは、次のチャンクが新しいノードに移動されるように、各々のチャンク４０４ｃおよび４０４ｇのそれぞれの後で分割され得る。
【００５１】
列４１０の第２行は、従来のノード分割基準を用いてノード４２８、４３０、および４３２に分割された挿入配列４０２Ｂを示している。この例では、挿入配列４０２Ｂは、元のチャンク４０４ａから４０４ｈの３番目毎のチャンクおよびチャンク４０６の後で分割される。従来のノード分割方式では、ノードが分割される場合、配列から外れた位置にあるチャンク（例えば、チャンク４０６）は、適切な順序（例えば、ダイアグラム４００Ａの挿入配列４０２Ａのように、チャンク４０４ｂと４０４ｃとの間）に置かれる。そのため、ノード４２８はチャンク４０４ａから４０４ｃおよび４０６を含み、ノード４３０はチャンク４０４ｄから４０４ｆを含み、ノード４３２はチャンク４０４ｇおよび４０４ｈ含んでいる。なお、ノード４１２、４１４、４１６のどれもノード４２８、４３０、および４３２と一致しないことに注意されたい。
【００５２】
列４１８の第２行は、図５に関して後で説明するコンテンツ定義のノード分割方法５００を用いて、ノード４３４、４３６、および４３８に分割された挿入配列４０２Ｂを示している。この例では、挿入配列４０２Ｂは各適格なコンテンツ定義の分割ポイントの後で分割される。すなわち、挿入配列４０２Ｂはチャンク４０４ｃおよび４０４８のそれぞれの後で分割される。図５に関して後で説明するコンテンツ定義のノード分割方法では、ノードが分割される場合、以前に配列から外れた位置にあったチャンク（例えば、チャンク４０６）は、適切な順序（例えば、ダイアグラム４００Ａの挿入配列４０２Ａのように、チャンク４０４ｂと４０４ｃとの間）に置かれる。このように、チャンク４０４ａから４０４ｃおよびチャンク４０６はノード４３４を形成し、チャンク４０４ｄから４０４ｇはノード４３６を形成し、チャンク４０４ｈだけでなく次の適格なコンテンツ定義の分割ポイントまでのチャンクを含んだノード４３８を形成する。なお、順序が間違った挿入配列４０２Ｂの構築されたノード４３４、４３６、４３８は、順番通りの挿入配列４０２Ａの構築されたノード４２０および４２２、４２４と同一であることに注意されたい。
【００５３】
図３および図４の説明で理解されるように、従来のノード分割方法が用いられる場合、データチャンクの挿入または削除を含む、基礎となるチャンク（例えば、バイト等）に対する局所的な変更は、通常多くのノードを変化させる。データ挿入の時間に大きな違いがある場合、それに比例した多くのリーフノードも影響を受ける。そのため、従来のノード分割方法は多くの非重複ノードを発生させる。
【００５４】
対照的に、コンテンツ定義のノード分割では、データ構造は挿入順序変更にそれほど敏感ではない。同様に、保存されたチャンクの数における局所的な変化は、メタデータ保存構造に局所的効果を与え、多くの重複ノードを発生させる。ノード重複はそれが保存コストを下げるという点で都合がよい。用途によっては、ノード重複は、データ伝送コストを下げ、および／または、動作速度を向上させることができる。
【００５５】
図５は、本発明の一実施形態による、コンテンツ定義のノード分割方法５００のフローチャートである。この方法５００は、上述のプロセッサまたは他の類似した構成要素のような、保存システム１００の種々の構成要素によって実行することが可能である。この方法は、通常、ノードがある所定の（例えば、最大の）エントリ数に達したときに、ステップ５０２で開始する。
【００５６】
ステップ５０４で、ノード領域がコンテンツ定義の分割ポイントを求めて検索される。少なくとも一実施形態では、ローリングウィンドウを用いて分割ポイントの疑似乱数選択を行う。検索領域は事前に定められて（例えば、規定されて）いてもよい。すなわち、その検索領域はユーザ定義であってもよく、および／または、グローバルパラメータを用いて設定されていてもよい。検索領域は、前方および／または後方へ検索されてもよい。多くの場合、ノードエントリは、１つのローリングウィンドウの長さが適切になる（例えば、保存されている、基礎となるデータが、基礎となるコンテンツのハッシュまたはコンテンツアドレスであるとき）ように、それ自体十分に任意抽出される。
【００５７】
コンテンツ定義の分割ポイントは、ノードエントリのコンテンツのハッシュ関数に基づいている。すなわち、ノードのチャンクのハッシュ関数を用いて分割ポイントを決定する。分割ポイントを確定するハッシュ関数のパラメータは事前に定義されていてもよく、ユーザによってまたはシステムによって定義されてもよく、およびチャンクの種類（例えば、データ、メタデータ、ノード等）によって異なっていてもよい。検索は、ノードのチャンクのハッシュのビットの特定の配列を検索することによって、事前に定められた検索領域内で行われてもよい。例えば、ビットマスクがノードへのエントリのハッシュに適用されてもよく、選択されたビットが所定の条件をいつ満たすかを見つけるために検索が実行される。
【００５８】
例えば、ビットマスクによって選択されたビットが０に等しいかどうか、またはある固定値を越えているかどうかを比較できるであろうし、または、最大または最小の遭遇値を用いて、その選択が選択され得るであろう。コンテンツ定義のチャンク化技術の当業者によく知られている他の技法を用いて選択を行うことが可能である。一方、コンテンツアドレスまたは基礎となるデータのハッシュ関連の表現をリーフノードに保存することも望ましいが、これは提案された実施形態のみである。実施形態によっては、リーフノードのみがコンテンツ定義の分割ポイントを求めて検索される。代替の実施形態では、ファイルシステム（例えば、図１のファイルシステム１０６）のツリーノードはすべて、コンテンツ定義の分割ポイントを求めて検索される。
【００５９】
ステップ５０６では、分割ポイントが見つけられたかどうかについての決定がなされる。少なくとも一実施形態では、最初のコンテンツ定義の分割ポイントが見つかるまで、ステップ５０４の検索が実行される。コンテンツ定義の分割ポイントが見つかる場合、この方法ではステップ５０８に進み、コンテンツ定義の分割ポイントが指定される。コンテンツ定義の分割ポイントが見つからない場合、この方法ではステップ５１０に進み、分割ポイントが選択される。
【００６０】
ステップ５０８では、適切な（例えば、事前に定義された）条件が満たされた（例えば、満足させられた）場合に、関連するチャンクがコンテンツ定義の分割ポイントとして指定される。図３および図４に関して上述したように、コンテンツ定義の分割ポイントは特定のチャンクと関連付けられており、ファイルシステム１０６は既知の手法でそのチャンクを含んだノードを分割することができる。例えば、ファイルシステム１０６は、指定の分割ポイントの前またはそのポイントの後で分割することができる。次に、本実施形態の方法では、ステップ５１２に進む。
【００６１】
ステップ５１０では、分割ポイントが選ばれる。少なくとも一実施形態では、コンテンツ定義の分割ポイントがステップ５０４で見つからない場合、検索領域の中間が分割ポイントとして指定される。他の実施形態では、元のビットマスクのそれほど制限的でない変形を用いること、または、さらにコンテンツ定義である、代替の分割ポイントを選択する他の方法を用いることが好ましい。
【００６２】
ステップ５１２では、ノードは指定の分割ポイントにしたがって分割される。この方法はステップ５１４で終わる。
【００６３】
図６は本発明の実施形態によるコンテンツ定義のノード分割方法を明示している。図６は、方法５００を制御するアルゴリズムパラメータの一例である、コンテンツ定義のノード分割方式６００を示している。すなわち、コンテンツ定義のノード分割方式６００は、ファイルシステム１００に関して上述したような、プロセッサ等上で、方法５００の処理を指揮する。
【００６４】
２行目の方式６００（「ｃｏｎｄｅｎｔｄｅｆｉｎｅｄｎｏｄｅｓｐｌｉｔ」）は、コンテンツ定義の分割化が用いられることを示している。３行目および４行目は、リーフおよび内部ノードに対する最大許容ファンアウトが３２０であることを示している。ノード（例えば、挿入配列３０２Ａ、３０２Ｂ、４０２Ａ、４０２Ｂ等中の）が、最大ファンアウトを越える場合は常に、方法５００のステップ５０４のように、コンテンツ定義の分割ポイントを見つけるための検索が実行される。ｓｐｌｉｔｌｏの値とｓｐｌｉｔｈｉの値との間の範囲（例えば、事前に定められた検索領域）のノードが検索される。この例では、ｓｐｌｉｔｌｏは検索範囲の下限（例えば、０．２５×３２０＝８０）を指定し、ｓｐｌｉｔｈｉは検索範囲の上限（例えば、０．７５×３２０＝２４０）を指定している。当然、任意のユーザ定義の検索領域、または、事前に定められた検索領域が用いられてもよい。
【００６５】
方式６００の７行目に示されるように、検索領域は、ハッシュのｓｐｌｉｔｍａｓｋビットに０を持つコンテンツを求めて検索される。動作中、ｓｐｌｉｔｍａｓｋのセットビット数はほぼｌｏｇ2（検索領域の大きさ）である。検索領域の大きさは検索範囲内のエントリ数である。この例では、検索領域の大きさは１６０である。これは、検索領域内に１つのコンテンツ定義の分割ポイントを持つ確率を最大にする。当然、任意の適切なビットマスク（例えば、ｓｐｌｉｔｍａｓｋ）が用いられてもよい。コンテンツ定義の分割化の他の変形をｓｐｌｉｔａｌｇ（２行目）によって選択することもできる。例えば、いくつかの変形は、分割ポイントが検索領域のエントリを通して第１のパス中に見つからない場合に分割ポイントを選択するのに用いることができる、バックアップ分割ポイント選択方法を指定することができる。例えば、それほど制限的でないビットマスクが用いられてもよく、またはフォールバック固定分割ポイント（例えば、中間点分割）をそのような場合に用いることも可能であろう。実施形態によっては、上述の変形はステップ５０４において分割ポイントを検索するのに用いられてもよく、および／または、上記の図５のステップ５１０において分割ポイントを選択するのに用いられてもよい。
【００６６】
実施形態によっては、メタデータ「データ（ｄａｔａ）」は対応するコンテンツアドレスから分離される。次に、メタデータ「データ（ｄａｔａ）」およびコンテンツアドレスは異なるブロックに保存される。したがって、チャンクがファイルシステム（例えば、ファイルシステム２００等）に移動させられた場合、次に成長したデータ構造におけるメタデータ「データ（ｄａｔａ）」は異なるであろうが、重複したコンテンツアドレスブロックを削除することが可能である。
【００６７】
先の「発明を実施するための詳細な説明」は、あらゆる点で具体例および典型的な例であって限定するものではないと理解されるべきであり、本明細書に開示された本発明の範囲は、「発明を実施するための詳細な説明」からではなく、むしろ特許法によって認められた十分な範囲によって解釈されるような請求項から判断されるべきである。本明細書に示され記載された実施形態は本発明の原理の例示にすぎず、種々の変更が本発明の範囲および精神から逸脱することなく、当業者により実行されてもよいことを理解されたい。当業者は、本発明の範囲および精神から逸脱することなく、種々の他の特徴の組み合わせを実現することができるであろう。
【符号の説明】
【００６８】
１００    保存システム
１０２    ファイルサーバ
１０４    ブロック保存装置
１０６    ファイルシステム
【図１】
2010079888.tif 000003
【図２】
2010079888.tif 000004
【図３】
2010079888.tif 000005
【図４】
2010079888.tif 000006
【図５】
2010079888.tif 000007
【図６】
2010079888.tif 000008