詳細な説明
以下の説明は、当業者が本発明を行って用いることができるように提示されており、特定の用途およびその要件の文脈において提供されている。開示される実施形態に対するさまざまな変更が当業者に容易に明らかとなり、本明細書に定義される一般原理は本発明の精神および範囲から逸脱することなく他の実施形態および用途にも適用され得る。ゆえに、本発明は示される実施形態に限定されず、本明細書に開示される原理および特徴と一致した最も広範な範囲が与えられる。本開示において、ある語句が「および/または」という語を一組のエンティティとともに用いる場合、当該語句は特に記載のない限りその一組のエンティティのすべての可能性のある組合せを包含する。たとえば、「X、Y、および/またはZ」という語句は、「Xのみ」、「Yのみ」、「Zのみ」、「Zを含まないXおよびY」、「Yを含まないXおよびZ」、「Xを含まないYおよびZ」、ならびに「X、Y、およびZ」の7個の組合せを包含する。
コンテンツ連想シーブを用いたデータの効率的な無損失削減
本明細書に記載のいくつかの実施形態では、データセット全体にわたってグローバルに冗長を効率的に発見して利用するようにデータが組織化されて記憶される。入力データストリームはエレメントと称される構成片またはチャンクに分割され、エレメント同士間の冗長がエレメント自体よりも細かく検出され利用されることによって、記憶データのフットプリント全体が削減される。基本データエレメントと称される一組のエレメントが識別されてデータセットのための共通および共有のビルディングブロックとして用いられ、基本データストアまたはシーブと称される構造に記憶される。基本データエレメントは単に、一定サイズのビット、バイト、または桁のシーケンスである。基本データエレメントは、実現例に依存して固定サイズであってもよく、または可変サイズであってもよい。入力データの他の構成要素が基本データエレメントから導出されて導出エレメント(Derivative Element)と称される。ゆえに、入力データは基本データエレメントおよび導出エレメントに因子分解される。
基本データストアは、基本データストアをコンテンツ連想的に検索してアクセスできるように、基本データエレメントを順序付けて組織化する。何らかの入力コンテンツを前提として、いくつかの制限を伴い、基本データストアに問合わせて、そのコンテンツを含む基本データエレメントを取出すことができる。入力エレメントを前提として、当該エレメントの値、または当該エレメント内の一定のフィールドの値を用いて基本データストアを検索して、1つのまたは小さい一組の基本データエレメントを迅速に提供することができ、そこから、導出を指定するのに必要な最小ストレージで入力エレメントを導出することができる。いくつかの実施形態では、基本データストア内のエレメントはツリー形態に組織化される。基本データエレメントに対して変換を実行することによって基本データエレメントから導出エレメントが導出され、そのような変換は、1つ以上の基本データエレメントから導出エレメントをどのように生成するかを記述する再構成プログラム内に指定されている。距離閾値が、導出エレメントの記憶フットプリントのサイズに対する制限を指定する。この閾値は、基本データエレメントからの導出エレメントの最大許容距離を指定し、また、導出エレメントを生成するために用いられ得る再構成プログラムのサイズに制限を課す。
導出データの取出しは、導出によって指定される1つ以上の基本データエレメントに対して再構成プログラムを実行することによって達成される。
本開示では、上記の汎用無損失データ削減技術はData Distillation(商標)プロセスと称され得る。これは、化学の蒸留と同様の、混合物をその構成要素に分離する機能を果たす。基本データストアは、シーブまたはData Distillation(商標)シーブとも称される。
このスキームでは、入力データストリームはエレメントのシーケンスに因子分解され、各エレメントは、基本データエレメント、または1つ以上の基本データエレメントから導出される導出エレメントである。各エレメントは無損失削減表現に変換され、これは、基本データエレメントの場合は基本データエレメントの参照を含み、導出エレメントの場合は、導出に伴う1つ以上の基本データエレメントの参照と、再構成プログラムの記述とを含む。ゆえに、入力データストリームは、無損失削減表現内にあるエレメントのシーケンスに因子分解される。この(無損失削減表現内に現われる)エレメントのシーケンスは、蒸留データストリームまたは蒸留データと称される。蒸留データ内のエレメントのシーケンスは、入力データ内のエレメントのシーケンスと1対1の対応関係を有しており、すなわち、蒸留データ内のエレメントのシーケンス内のn番目のエレメントは、入力データ内のエレメントのシーケンス内のn番目のエレメントに対応する。
本開示に記載の汎用無損失データ削減技術は、入力データストリームを受信し、蒸留データストリームおよび基本データストアのフットプリントの合計が入力データストリームのフットプリントよりも通常は小さいように、入力データストリームを蒸留データストリームと基本データストアとの組合せにコンバートする。本開示では、蒸留データストリームおよび基本データストアは無損失削減データと総称され、同じ意味で「削減データストリーム」または「削減データ」とも称される。同様に、本開示に記載の無損失データ削減技術によって生成され、かつ無損失削減フォーマットで現われるエレメントのシーケンスについて、「削減出力データストリーム」、「削減出力データ」、「蒸留データストリーム」、および「蒸留データ」という語は同じ意味で用いられる。
図1Aは、本明細書に記載のいくつかの実施形態に従う、入力データをエレメントに因子分解し、これらを基本データストア内に存在している基本データエレメントから導出するデータ削減のための方法および装置を示す。この図はデータ削減またはData Distillation(商標)方法および装置の全体ブロック図を示しており、機能コンポーネント、構造、および演算の概要を提供している。図1Aに示すコンポーネントおよび/または演算はソフトウェア、ハードウェア、またはそれらの組合せを用いて実現され得る。
バイトのシーケンスが入力データストリームから受信され、Data Distillation(商標)装置とも称されるデータ削減装置103に入力データ102として提示される。パーサおよび因子分解部104が受信データをパースし、当該データをチャンクまたは候補エレメントに分割する。因子分解部は、入力ストリーム内のどこにブレークを挿入してストリームを候補エレメントにスライスアップするかを決定する。データ内の連続する2つのブレークが識別されると、候補エレメント105がパーサおよび因子分解部によって作成され、Data Distillation(商標)シーブとも称される基本データストア106に提示される。
Data Distillation(商標)シーブまたは基本データストア106は、(図1AにおいてPDEとラベル付けされている)すべての基本データエレメントを含んでおり、それらの値またはコンテンツに基づいてそれらを順序付けて組織化する。シーブは2種類のアクセスのサポートを提供する。第1に、基本データエレメントの各々には、基本データエレメントがシーブ内に存在する場所の参照によって、直接アクセス可能である。第2に、エレメントには、ソフトウェア、ハードウェア、またはそれらの組合せで実現され得るコンテンツ連想マッパー121を用いることによって、コンテンツ連想的にアクセス可能である。シーブへのこの第2のアクセス形態は、候補エレメント105と完全に一致する基本データエレメントを識別するために、または、候補エレメントをそこから導出可能な基本データエレメントを識別するために、開示される実施形態によって用いられる重要な特徴である。具体的には、たとえば候補エレメント105などの候補エレメントを前提として、基本データストア106を(候補エレメント105の値に基づいて、または候補エレメント105内の一定のフィールドの値に基づいて)検索して、1つのまたは小さい一組の基本データエレメント107を迅速に提供することができ、そこから、導出を指定するのに必要な最小ストレージで候補エレメントを導出することができる。
シーブまたは基本データストア106は、その値がデータ空間にわたって分散している一組の基本データエレメントで初期化され得る。あるいは、シーブは空で開始してもよく、図1A〜図1Cおよび図2を参照して本明細書に記載されるData Distillation(商標)プロセスに従って、データが取込まれるにつれて基本データエレメントがシーブに動的に追加されてもよい。
導出部110は、候補エレメント105と、(基本データストア106からコンテンツ連想的に取出されるコンテンツである)導出に好適な取出された基本データエレメント107とを受信し、候補エレメント105がこれらの基本データエレメントの1つ以上から導出可能であるか否かを判断し、削減されたデータコンポーネント115(関連の基本データエレメントの参照および再構成プログラムで構成される)を生成し、基本データストアに更新114を提供する。候補エレメントが、取出された基本データエレメントの重複である場合、導出部は、基本データストア内にある基本データエレメントの参照(またはポインタ)と、これが基本データエレメントであるというインジケータとを、蒸留データ108に入れる。重複が見つからない場合、導出部は、候補エレメントを、1つ以上の取出された基本データエレメントに対して実行された1つ以上の変換の結果として表現し、この一連の変換は、たとえば再構成プログラム119Aなどの再構成プログラムと総称される。各導出では、その固有のプログラムを導出部によって構築する必要があり得る。再構成プログラムは、基本データエレメントに適用可能な挿入、削除、置換、連結、算術、および論理演算といった変換を指定する。導出エレメントのフットプリント(再構成プログラムのサイズに、必要な基本データエレメントの参照のサイズを加えたものとして計算される)が(データ削減を可能にするための)候補エレメントに関して一定の指定された距離閾値内にあるという条件で、候補エレメントは導出エレメントとして再公式化され、再構成プログラムと1つの(または複数の)関連の基本データエレメントの参照との組合せで置換され、この場合、これらは削減されたデータコンポーネント115を形成する。閾値を超えた場合、または基本データストアから好適な基本データエレメントが取出されなかった場合、基本データストアは候補を新規な基本データエレメントとしてインストールするように指示され得る。この場合、導出部は、新たに追加された基本データエレメントの参照と、さらに、これが基本データエレメントであるというインジケータとを蒸留データに入れる。
データの取出し要求(たとえば取出し要求109)は、基本データエレメントを含む基本データストア内の場所の参照の形態、または、導出物(Derivative)の場合には、基本データエレメントのそのような参照と、関連付けられた再構成プログラムとの組合せ(または複数の基本データエレメントに基づく導出物の場合は、複数の基本データエレメントの参照と、関連付けられた再構成プログラムとの組合せ)の形態であり得る。基本データストア内の基本データエレメントの1つ以上の参照を用いて、取出部111は基本データストアにアクセスして1つ以上の基本データエレメントをフェッチし、1つ以上の基本データエレメントおよび再構成プログラムを再構成部112に与えることができ、再構成部112は、(再構成プログラム内に指定されている)変換を1つ以上の基本データエレメントに対して実行して再構成データ116(要求されたデータ)を生成し、それをデータ取出し要求に応答して取出されたデータ出力113に供給する。
本実施形態の変形では、基本データエレメントは、(ハフマン符号化およびLempel Ziv法を含む先行技術において公知の技術を用いて)圧縮形態でシーブに記憶され、必要に応じて復元されてもよい。これには、基本データストアのフットプリント全体を削減するという利点がある。唯一の制約は、コンテンツ連想マッパー121が、前と同様に基本データエレメントへのコンテンツ連想アクセスを提供し続けなければならないことである。
図1Bおよび図1Cは、本明細書に記載のいくつかの実施形態に従う、図1Aに示す方法および装置の変形を示す。図1Bでは、再構成プログラムは基本データストアに記憶されて基本データエレメントと同様に取扱われ得る。再構成プログラム119A自体を提供する代わりに、再構成プログラムの参照またはポインタ119Bが蒸留データ108内に提供される。再構成プログラムが他の導出物によって共有される場合、および、再構成プログラムの参照またはポインタ(さらに、再構成プログラムと再構成プログラムの参照とを区別するために必要な任意のメタデータを加えたもの)のストレージスペースが再構成プログラム自体よりも小さくて済む場合、さらなるデータ削減が達成される。
図1Bでは、再構成プログラムは基本データエレメントと同様に取扱われてアクセスされ、基本データエレメントとして基本データストアに記憶されることによって、基本データストアからの再構成プログラムのコンテンツ連想検索および取出しが可能になり得る。導出エレメントを作成する導出プロセスの際、導出部110が導出に必要な再構成プログラムを決定すると、導出部110は次いで、この候補再構成プログラムが基本データストア内に既に存在しているか否か、またはこの候補再構成プログラムが基本データストア内に既に存在している別のエントリから導出可能であるか否かを判断し得る。候補再構成プログラムが基本データストア内に既に存在している場合は、導出部110は既存のエントリの参照を決定し、当該参照を蒸留データ108に含めることができる。候補再構成プログラムが基本データストア内に既に存在している既存のエントリから導出可能である場合、導出部は候補再構成プログラムの導出物または再公式化を蒸留データに供給し得、すなわち、導出部は、基本データストア内に予め存在しているエントリの参照を、この予め存在しているエントリから候補再構成プログラムを導出する増分的な再構成プログラムとともに、蒸留データに入れる。候補再構成プログラムが基本データストア内に存在しておらず、基本データストアへのエントリからも導出不可能である場合は、導出部110は再構成プログラムを基本データストアに追加し(再構成プログラムをストアに追加する演算は、新たに追加されたエントリの参照を戻し得る)、再構成プログラムの参照を蒸留データ108に含めることができる。
図1Cは、本明細書に記載のいくつかの実施形態に従う、図1Bに示す方法および装置の変形を提示する。具体的には、再構成プログラムを記憶して再構成プログラムに問合せるために用いられる図1Cのメカニズムは、基本データエレメントを記憶して基本データエレメントに問合せるために用いられるメカニズムと同様であるが、再構成プログラムは、基本データエレメントを含む構造とは別の構造内に維持される。そのような構造へのエントリは、基本再構成プログラム(図1CにおいてPRPとラベル付けされている)と称される。基本データストア106は、迅速なコンテンツ連想ルックアップ操作をサポートするコンテンツ連想マッパー121を含んでいることを思い起こされたい。図1Cに示す実施形態は、コンテンツ連想マッパー121と同様のコンテンツ連想マッパー122を含む。図1Cでは、コンテンツ連想マッパー122およびコンテンツ連想マッパー121は基本データストアまたはシーブ106の一部であるとして示されている。他の実施形態では、コンテンツ連想マッパー122および再構成プログラムは、基本データストアまたはシーブ106とは別に記憶されてもよい。
本実施形態の変形では、基本データエレメントは、(ハフマン符号化およびLempel Ziv法を含む先行技術において公知の技術を用いて)圧縮形態でシーブに記憶され、必要に応じて復元されてもよい。同様に、基本再構成プログラムは、(ハフマン符号化およびLempel Ziv法を含む先行技術において公知の技術を用いて)圧縮形態で基本再構成プログラムシーブに記憶され、必要に応じて復元されてもよい。これには、基本データシーブおよび基本再構成プログラムシーブのフットプリント全体を削減するという利点がある。唯一の制約は、コンテンツ連想マッパー121および122が、前と同様に基本データエレメントおよび基本再構成プログラムへのコンテンツ連想アクセスを提供し続けなければならないことである。
図1Dは、本明細書に記載のいくつかの実施形態に従う、図1Aに示す方法および装置の変形を提示する。具体的には、図1Dに記載の実施形態では、基本データエレメントは蒸留データ内にインラインに記憶されている。基本データシーブまたは基本データストア106は基本データエレメントへのコンテンツ連想アクセスを提供し続け、基本データエレメントを論理的に包含し続ける。それは、蒸留データ内にインラインに配置されている基本データエレメントの参照またはリンクを維持する。たとえば、図1Dでは、基本データエレメント130は蒸留データ108内にインラインに配置されている。基本データシーブまたは基本データストア106は基本データエレメント130の参照131を維持する。ここでも、このセットアップにおいて、導出エレメントの無損失削減表現は、必要な基本データエレメントの参照を含む。データ取出し時、取出部111は、必要な基本データエレメントをその配置場所からフェッチする。
図1Eは、本明細書に記載のいくつかの実施形態に従う、図1Dに示す方法および装置の変形を提示する。具体的には、図1Eに記載の実施形態では、図1Bに示すセットアップと同様に、再構成プログラムが他の基本再構成プログラムから導出され、増分再構成プログラムに基本再構成プログラムの参照を加えたものとして指定され得る。そのような基本再構成プログラムは基本データエレメントと同様に取扱われ、基本データシーブに論理的にインストールされる。さらに、このセットアップでは、基本データエレメントおよび基本再構成プログラムの両方が蒸留データ内にインラインに記憶される。基本データシーブまたは基本データストア106は、基本データエレメントおよび基本再構成プログラムへのコンテンツ連想アクセスを提供し続け、これら基本データエレメントおよび基本再構成プログラムを、それらが蒸留データ内にインラインに配置されている場所の参照またはリンクを維持しつつ、論理的に包含し続ける。たとえば、図1Eでは、基本データエレメント130は蒸留データ108内にインラインに配置されている。また図1Eでは、基本再構成プログラム132は蒸留データ内にインラインに配置されている。基本データシーブまたは基本データストア106は、基本データエレメント130(PDE_i)の参照131(Reference_to_PDE_i)、および基本再構成プログラム132(Prime_Recon_Program_l)の参照133(Reference_to_PDE_k)を維持する。ここでも、このセットアップにおいて、導出エレメントの無損失削減表現は、必要な基本データエレメントおよび必要な基本再構成プログラムの参照を含む。データ取出しの際、取出部111は、必要なコンポーネントを、対応する蒸留データ内のそれらの配置場所からフェッチする。
図1Fは、本明細書に記載のいくつかの実施形態に従う、図1Eに示す方法および装置の変形を提示する。具体的には、図1Fに記載の実施形態では、図1Cに示すセットアップと同様に、基本データシーブ108は別個のマッパー、すなわち、基本データエレメントのためのコンテンツ連想マッパー121、および基本再構成プログラムのためのコンテンツ連想マッパー122を含む。
図1Gは、図1Aから図1Fに示す方法および装置のより一般化した変形を提示する。具体的には、図1Gに記載の実施形態では、基本データエレメントは基本データシーブ内に、または蒸留データ内にインラインに配置され得る。いくつかの基本データエレメントは基本データシーブ内に配置され得、他の基本データエレメントは蒸留データ内にインラインに配置される。同様に、基本再構成プログラムは基本データシーブ内に、または蒸留データ内にインラインに配置され得る。いくつかの基本再構成プログラムは基本データシーブ内に配置され得、他の基本再構成プログラムは蒸留データ内にインラインに配置される。基本データシーブは、すべての基本データエレメントおよび基本再構成プログラムを論理的に包含しており、基本データエレメントまたは基本再構成プログラムが蒸留データ内にインラインに配置されている場合は、基本データシーブはその場所の参照を供給する。
入力データをエレメントに因子分解し、これらを基本データストア内に存在している基本データエレメントから導出するデータ削減のための方法および装置の上記の説明は、例示および説明目的で提示されているに過ぎない。それらは網羅的であること、または本発明を開示された形態に限定することを意図していない。したがって、多くの変更および変形が当業者に明らかになるであろう。
図1Hは、本明細書に記載のいくつかの実施形態に従う、Data Distillation(商標)プロセスのための方法および装置の図1Aの蒸留データ119Aの構造を記述するフォーマットおよび仕様の例を提示する。Data Distillation(商標)プロセスは入力データを基本データエレメントおよび導出エレメントに因子分解するので、データの無損失削減表現のためのフォーマットはこれらエレメントを識別し、蒸留データ内のこれらのエレメントのさまざまなコンポーネントを記述する。自己記述フォーマットは蒸留データ内の各レコードを識別し、それが基本データエレメントであるか導出エレメントであるかを指示し、さまざまなコンポーネント、すなわち、シーブにインストールされる1つ以上の基本データエレメントの参照、基本データストアにインストールされる再構成プログラムの参照(図1Bの119Bのように)、または再構成プログラム(RP)ストアに記憶される再構成プログラムの参照(図1Cの119Cのように)、およびインラインの再構成プログラム(RP)を記述する。再構成プログラム(RP)ストアは、同じ意味で基本再構成プログラム(PRP)ストアとも称される。図1Hのフォーマットは、複数の基本データエレメントに対して再構成プログラムを実行することによって導出を指定する規定を有し、導出エレメントおよび基本データエレメントの各々のサイズは独立して指定可能である。図1Hのフォーマットはさらに、基本データストア内に配置されるのではなく蒸留データ内にインラインに配置されている基本データエレメントを指定する規定を有する。これは、エレメントのタイプが、蒸留データ内にインラインに配置されている基本データエレメントであることを指定するオペコード符号化7によって指定される。蒸留データは、このフォーマットを用いてデータストレージシステムに記憶される。このフォーマットのデータは、当該データのさまざまなコンポーネントがフェッチされた後に再構成され得るように、データ取出部111によって消費される。
図1Iから図1Pは、図1Aから図1Gに示すデータ削減のための方法および装置の変形についての入力データの無損失削減形態への概念的な変換を示す。図1Iは、どのように入力データのストリームが候補エレメントに因子分解され、続いて、候補エレメントが基本データエレメントまたは導出エレメントと見なされるかを示す。最後に、データは無損失削減形態に変換される。図1Iから図1Nは、さまざま実施形態についての無損失削減形態の変形を示す。
図1Iおよび図1Jは、図1Aに示す方法および装置によって生成されるデータの無損失削減形態の例を示す。図1Iの無損失削減形態はコンテンツ連想マッパーを含んでおり、データの連続的なさらなる取込み、および既存の基本データエレメントに対するこのデータの削減を可能にする形態である。一方、図1Jの無損失削減形態はコンテンツ連想マッパーをもはや保持しておらず、より小さいフットプリントのデータがもたらされる。図1Kおよび図1Lは、図1Cに示す方法および装置によって生成されるデータの無損失削減形態の例を示す。図1Kの無損失削減形態はコンテンツ連想マッパーを含んでおり、データの連続的なさらなる取込み、ならびに既存の基本データエレメントおよび基本再構成プログラムに対するこのデータの削減を可能にする形態である。一方、図1Lの無損失削減形態はコンテンツ連想マッパーをもはや保持しておらず、より小さいフットプリントのデータがもたらされる。
図1Mおよび図1Nは、図1Fに示す方法および装置によって生成されるデータの無損失削減形態の例を示しており、基本データエレメントおよび基本再構成プログラムは蒸留データ内にインラインに配置されている。図1Mの無損失削減形態はコンテンツ連想マッパーを含んでおり、データの連続的なさらなる取込み、ならびに既存の基本データエレメントおよび基本再構成プログラムに対するこのデータの削減を可能にする形態である。一方、図1Nの無損失削減形態はコンテンツ連想マッパーをもはや保持しておらず、より小さいフットプリントのデータがもたらされる。図1Oおよび図1Pは、図1Gに示す方法および装置によって生成されるデータの無損失削減形態の例を示しており、基本データエレメントおよび基本再構成プログラムは蒸留データ内にインラインに、または基本データシーブ内に配置され得る。図1Oの無損失削減形態はコンテンツ連想マッパーを含んでおり、データの連続的なさらなる取込み、ならびに既存の基本データエレメントおよび基本再構成プログラムに対するこのデータの削減を可能にする形態である。一方、図1Pの無損失削減形態はコンテンツ連想マッパーをもはや保持しておらず、より小さいフットプリントのデータがもたらされる。
図1Aから図1Pに示す実施形態の変形では、削減データのさまざまなコンポーネントは、(ハフマン符号化およびLempel Ziv法といった)先行技術において公知の技術を用いてさらに削減または圧縮され、この圧縮形態で記憶されてもよい。これらのコンポーネントは続いて、それらがデータ蒸留装置での使用に必要となったときに圧縮され得る。これには、データのフットプリント全体をさらに削減するという利点がある。
図2は、本明細書に記載のいくつかの実施形態に従う、入力データをエレメントに因子分解し、これらエレメントを基本データストア内に存在する基本データエレメントから導出することによるデータ削減のためのプロセスを示す。入力データが到着すると、当該データはパースされ、一連の候補エレメントに因子分解されるか分割され得る(オペレーション202)。次の候補エレメントが入力から消費され(オペレーション204)、基本データストアのコンテンツ連想ルックアップが候補エレメントのコンテンツに基づいて実行されて、候補エレメントをそこから導出可能ないずれかの好適なエレメントがあるか否かが調べられる(オペレーション206)。基本データストアがそのようなエレメントを全く見つけなかった場合(オペレーション208の「No」のブランチ)、候補エレメントが割当てられて新たな基本データエレメントとしてシーブに入力され、候補エレメントのために作成された蒸留データへのエントリが、新たに作成された基本データエレメントの参照となる(オペレーション216)。基本データストアのコンテンツ連想ルックアップが、候補がそこから導出される可能性がある1つ以上の好適なエレメントをもたらす場合(オペレーション208の「Yes」のブランチ)、取出された基本データエレメントに対して分析および計算が行われて、当該エレメントから候補エレメントが導出される。なお、いくつかの実施形態では、まず好適な基本データエレメントのためのメタデータのみがフェッチされてこのメタデータに対して分析が行われ、この好適な基本データエレメントは有用であると見なされた場合にのみ続いてフェッチされる(これらの実施形態では、基本データエレメントのためのメタデータが基本データエレメントのコンテンツについての何らかの情報を提供することによって、システムがメタデータに基づいて迅速に一致を排除するか導出可能性を評価することができる)。他の実施形態では、基本データストアは基本データエレメントを直接(すなわち、基本データエレメントを取出す前にまずメタデータを取出してメタデータを分析することなく)取出すので、分析および計算は取出された基本データエレメントに対して行なわれる。
候補がこれらエレメントのうちのいずれかの重複であるか否かを調べるための第1の確認が行なわれる(オペレーション210)。この確認は任意の好適なハッシング技術を用いて迅速化され得る。候補が基本データストアから取出された基本データエレメントと同一である場合(オペレーション210の「Yes」のブランチ)、候補エレメントのために作成された蒸留データへのエントリは、この基本データエレメントの参照と、このエントリが基本データエレメントであるという指示とに置換される(オペレーション220)。重複が見つからない場合(オペレーション210の「No」のブランチ)、候補エレメントに基づいて基本データストアから取出されたエントリが、候補エレメントをそこから導出できる可能性があるエントリと見なされる。以下は、基本データストアの重要な、新規な、非自明な特徴である:基本データストア内に重複が見つからない場合、基本データストアは基本データエレメントを戻すことができ、基本データエレメントは、候補エレメントと同一ではないが、1つ以上の変換を基本データエレメントに適用することによって候補エレメントがそこから導出される可能性があるエレメントである。プロセスは次に分析および計算を行って、最適な基本データエレメントまたは一組の好適な基本データエレメントから候補エレメントを導出し得る(オペレーション212)。いくつかの実施形態では、導出は、候補エレメントを、1つ以上の基本データエレメントに対して実行した変換の結果として表現し、そのような変換は再構成プログラムと総称される。各導出では、その固有のプログラムを構築する必要があり得る。再構成プログラムを構築するのに加えて、プロセスはさらに、候補エレメントの再公式化を記憶するために、かつ再公式化から候補エレメントを再構成するために必要なストレージリソースおよび/または計算リソースのレベルを一般的に示す距離メトリックを計算し得る。いくつかの実施形態では、導出エレメントのフットプリントは、基本データエレメントからの候補の距離の測定として用いられ、具体的には、距離メトリックは、再構成プログラムのサイズに、導出に伴う1つ以上の基本データエレメントの参照のサイズのを加えた合計と定義され得る。最小距離を有する導出が選択され得る。この導出のための距離は距離閾値と比較され(オペレーション214)、距離が距離閾値を超えない場合、導出が受付けられる(オペレーション214の「Yes」のブランチ)。データ削減をもたらすために、距離閾値は常に候補エレメントのサイズ未満でなければならない。たとえば、距離閾値は候補エレメントのサイズの50%に設定されてもよく、これによって、導出物は、そのフットプリントが候補エレメントのフットプリントの半分以下である場合にのみ受付けられることになり、これによって、好適な導出が存在する候補エレメント毎に2倍以上の削減が確実となる。距離閾値は、ユーザが指定した入力に基づく、またはシステムによって選択される、予め定められた割合または分率であってもよい。距離閾値は、システムの静的または動的パラメータに基づいてシステムによって決定されてもよい。導出が受付けられると、候補エレメントが再公式化され、再構成プログラムと1つ以上の基本データエレメントの参照との組合せで置換される。候補エレメントのために作成された蒸留データへのエントリは導出で置換され、すなわち、それは、再構成プログラムに、導出に伴う1つ以上の基本データエレメントの参照を加えたものとともに、これは導出エレメントであるという指示に置換される(オペレーション218)。一方、最良導出のための距離が距離閾値を超えた場合(オペレーション214の「No」のブランチ)、可能性のある導出物はいずれも受付けられない。その場合、候補エレメントが割当てられて新たな基本データエレメントとしてシーブに入力され得、候補エレメントのために作成された蒸留データへのエントリは、これが基本データエレメントであるという指示とともに、新たに作成された基本データエレメントの参照となる(オペレーション216)。
最後に、プロセスは追加の候補エレメントがあるか否かを確認し(オペレーション222)、追加の候補エレメントがある場合(オペレーション222の「Yes」のブランチ)はオペレーション204に戻り、追加の候補エレメントがない場合(オペレーション222の「No」のブランチ)はプロセスを終了し得る。
図2のオペレーション202を実行するために、すなわち受信データをパースしてそれを候補エレメントに分割するために、さまざまな方法が利用され得る。因子分解アルゴリズムは、バイトストリーム内のどこにブレークを挿入してストリームを候補エレメントにスライスアップするかを決定する必要がある。可能性のある技術として、ストリームを固定サイズのブロック(4096バイトのページなど)に分割すること、または、フィンガープリンティングの方法(ランダムな素数多項式を入力ストリームの部分文字列に適用する技術など)を適用して、エレメントの境界となる好適なフィンガープリントのデータストリーム内の位置を特定すること(この技術によって可変サイズのエレメントを得ることができる)、または、入力をパースしてヘッダもしくは何らかの予め宣言された構造を検出し、この構造に基づいてエレメントの輪郭を描くことがある(がこれらに限定されない)。入力はパースされて、スキーマによって宣言される一定の構造が検出され得る。入力はパースされて、データ内の予め宣言されたパターン、文法、または正規表現の存在が検出され得る。データ内の連続する2つのブレークが識別されると、候補エレメントが作成され(候補エレメントは連続する2つのブレーク同士の間にあるデータである)、コンテンツ連想ルックアップのために基本データストアに提示される。可変サイズのエレメントが作成されると、候補エレメントの長さを指定し、候補エレメントとともにメタデータとして伝送する必要がある。
基本データストアの1つの重要な機能は、基本データストアに提示される候補エレメントに基づいてコンテンツ連想ルックアップを提供すること、および、導出を指定するのに必要な最小ストレージで候補エレメントをそこから導出可能な1つのまたは小さい一組の基本データエレメントを迅速に提供することである。これは、大型データセットを前提とすると困難な問題である。テラバイトのデータを前提として、キロバイトサイズのエレメントであっても、検索して選択する何十億ものエレメントが存在する。この問題はデータセットが大きくなるとより深刻になる。好適な技術を用いてエレメントを組織化して順序付けした後、エレメントのその組織内の類似および導出可能性を検出して、小さい一組の好適な基本データエレメントを迅速に提供可能であることが重要になる。
シーブへのエントリは各エレメント(すなわち基本データエレメント)の値に基づいて順序付けられ得るので、すべてのエントリは値によって昇順または降順に配置され得る。あるいは、エントリは、エレメント内の一定のフィールドの値に基づく主軸に沿って、次にエレメントの残りのコンテンツを用いる副軸に沿って順序付けられてもよい。この文脈において、フィールドは、エレメントのコンテンツからの一組の隣接バイトである。フィールドは、フィンガープリントの場所がフィールドの位置を特定するようにエレメントのコンテンツにフィンガープリンティングの方法を適用することによって、位置が特定され得る。あるいは、エレメントのコンテンツ内部の一定の固定オフセットを選択してフィールドの位置を特定してもよい。他の方法を用いてフィールドの位置を特定してもよく、当該方法として、エレメントをパースして一定の宣言された構造を検出し、その構造内のフィールドの位置を特定することがあるが、これに限定されない。
さらに別の形態の組織では、エレメント内の一定のフィールドまたはフィールド同士の組合せを次元と見なすことができるので、これらの次元の連結、およびそれに続く各エレメントの残りのコンテンツを用いてデータエレメントを順序付けて組織化してもよい。一般的に、フィールドおよび次元同士の間の対応関係またはマッピングは任意に複雑であり得る。たとえば、いくつかの実施形態では、1つのフィールドのみが1つの次元のみにマップし得る。他の実施形態では、たとえばF1、F2、およびF3などの複数のフィールドの組合せが1つの次元にマップし得る。フィールドの組合せは、2つのフィールド同士を連結することによって、またはそれらにその他の好適な関数を適用することによって達成され得る。重要な要件は、フィールドの配置、次元、およびエレメントを組織化するために用いられるエレメントの残りのコンテンツが、すべての基本データエレメントをそれらのコンテンツによって固有に識別してシーブ内に順序付けることが可能でなければならないことである。
いくつかの実施形態では、エレメントのコンテンツは以下のような表現:エレメント = Head .* sig1 .* sig2 .* … sigI .*… sigN .* Tailとして表わすことができ、式中、「Head」はエレメントの先頭バイトを含むバイトのシーケンスであり、「Tail」はエレメントの終了バイトを含むバイトのシーケンスであり、「sig1」、「sig2」、「sigI」、および「sigN」は、エレメントを特徴付けるエレメントのコンテンツの本体内の一定長さのさまざまな署名またはパターンまたは正規表現またはバイトのシーケンスである。さまざまな署名同士の間の「.*」という表現はワイルドカード表現であり、すなわち、これは、「.*」という表現に続く署名以外の任意の値の任意の数の中間バイトを許可する正規表現の表記法である。いくつかの実施形態では、Nタプル(sig1, sig2, … sigI,…sigN)がエレメントの骨格データ構造またはスケルトンと称され、エレメントの減少した本質的なサブセットまたは本質と見なすことができる。他の実施形態では、(N+2)タプル(Head, sig1, sig2, … sigI,… sigN, Tail)がエレメントの骨格データ構造またはスケルトンと称される。あるいは、HeadまたはTailを残りの署名とともに含むN+1タプルを使用してもよい。
フィンガープリンティングの方法がエレメントのコンテンツに適用されて、エレメントのコンテンツ内の骨格データ構造のさまざまなコンポーネント(または署名)の場所が判定され得る。あるいは、エレメントのコンテンツ内部の一定の固定オフセットを選択してコンポーネントの位置を特定してもよい。他の方法を用いて骨格データ構造のコンポーネントの位置を特定してもよく、当該方法として、エレメントをパースして一定の宣言された構造を検出し、その構造内のコンポーネントの位置を特定することがあるが、これに限定されない。基本データエレメントは、それらの骨格データ構造に基づいてシーブ内に順序付けられ得る。言い換えると、エレメントの骨格データ構造のさまざまなコンポーネントを次元と見なすことができるため、これらの次元同士の連結、およびそれに続く各エレメントの残りのコンテンツを用いて、基本データエレメントをシーブ内に順序付けて組織化してもよい。
いくつかの実施形態では入力データが候補エレメントに因子分解され、各候補エレメントのサイズは、グローバルデータセット内のすべてのそのようなエレメントにアクセスするのに必要な参照のサイズより実質的に大きい。そのようなデータチャンクに分割される(かつコンテンツ連想的にアクセスされる)データに関する1つの観察は、実際のデータは、データチャンクが指定可能なすべての可能性のある値に対して非常に疎らであることである。たとえば、1ゼタバイトのデータセットを考えてみる。このデータセット内の全バイトをアドレス指定するには約70ビットが必要である。128バイト(1024ビット)のチャンクサイズでは、1ゼタバイトのデータセット内に約263個のチャンクが存在するので、これらすべてのチャンクをアドレス指定するには63ビット(8バイト未満)が必要である。なお、1024ビットのエレメントまたはチャンクは21024個の可能性のある値のうちの1つを有し得るが、データセット内の所与のチャンクの実際値の数はせいぜい263個(すべてのチャンクが別個である場合)である。これは、実際のデータは、エレメントのコンテンツが達し得るまたは名付け得る値の数に対して非常に疎らであることを示す。これによって、効率的なコンテンツベースのルックアップを可能にし、新たなエレメントをツリー構造に効率的に追加することを可能にし、かつ、ツリー構造自体に必要な増分ストレージの面でコスト効率の高い態様で非常に疎らなデータを組織化するのに適しているツリー構造の使用が可能になる。1ゼタバイトのデータセット内には別個のチャンクが263個しかないため、それら同士を区別するのに63個の区別ビットの情報しか必要でないが、関連の区別ビットはエレメントの1024ビットにわたって分散し、エレメント毎に異なる場所で起こり得る。したがって、すべてのエレメント同士を完全に区別するためには、コンテンツから固定の63ビットを調べるのみでは不十分であり、むしろ、エレメントのコンテンツ全体が、エレメントをソートするのに、特に、データセット内のすべてのエレメントへの真のコンテンツ連想アクセスを提供するソリューションに関与する必要がある。Data Distillation(商標)フレームワークでは、データを順序付けて組織化するために用いられるフレームワーク内の導出可能性を検出可能であることが望ましい。上記のすべてを念頭に置いて、コンテンツに基づくツリー構造(より多くのコンテンツが調べられるにつれてデータを漸進的に区別する)は、因子分解されたデータセット内のすべてのエレメントを順序付けて区別するのに好適な組織である。そのような構造は、導出可能エレメントのグループ分け、または導出可能性の同様のプロパティを有するエレメントのグループ分けとして取扱われ得るサブツリーの多数の中間レベルを提供する。そのような構造は、各サブツリーを特徴付けるメタデータで、またはデータの各エレメントを特徴付けるメタデータで階層的に拡張され得る。そのような構造は、データ内の実際値の密度、近接、および分布を含む、当該構造が含むデータ全体の構成を効果的に通信し得る。
いくつかの実施形態では、基本データエレメントがツリー形態でシーブ内に組織化される。各基本データエレメントは、当該基本データエレメントのコンテンツ全体から構築される別個の「名前」を有する。この名前は、基本データエレメントを固有に識別するのに、かつそれをツリー内のすべての他のエレメントに対して区別するのに十分であるように設計される。基本データエレメントのコンテンツから名前を構築可能な方法はいくつかある。名前は単に基本データエレメントの全バイトで構成されてもよく、これらのバイトは、それらが基本データエレメント内に存在しているのと同じ順序で名前内に現われる。別の実施形態では、次元と称される一定のフィールドまたはフィールド同士の組合せ(フィールドおよび次元は上記の通り)を用いて名前の先頭バイトが形成され、基本データエレメントの残りのコンテンツは残りの名前を形成しているので、基本データエレメントのコンテンツ全体がエレメントの完全な固有の名前を作成するのに関与している。さらに別の実施形態では、エレメントの骨格データ構造のフィールドが次元として選択され(フィールドおよび次元は上記の通り)、当該フィールドを用いて名前の先頭バイトが形成され、基本データエレメントの残りのコンテンツは残りの名前を形成しているので、基本データエレメントのコンテンツ全体がエレメントの完全な固有の名前を作成するのに関与している。
各基本データエレメントの名前を用いて、基本データエレメントが順序付られてツリーに組織化される。ほとんどの実用的なデータセット、さらにはサイズが非常に大きい(たとえば、4KBサイズの258個のエレメントで構成される1ゼタバイトのデータセットなど)データセットについては、名前のバイトの小さいサブセットが基本データエレメントの大半をソートしてツリー内に順序付ける役割を果たすことが多いと予想される。
図3A、図3B、図3C、図3Dおよび図3Eは、本明細書に記載のいくつかの実施形態に従う、基本データエレメントをそれらの名前に基づいて組織化するために用いられ得るさまざまなデータ組織システムを示す。
図3Aは、基本データエレメントが各基本データエレメントの名前からの連続バイトの値に基づいて漸進的に小さくなるグループに組織化されるトライデータ構造を示す。図3Aに示す例では、各基本データエレメントは、当該基本データエレメントのコンテンツ全体から構築される別個の名前を有しており、この名前は単に基本データエレメントの全バイトで構成されており、これらのバイトは、それらが基本データエレメント内に存在しているのと同じ順序で名前内に現われる。トライのルートノードはすべての基本データエレメントを表わす。トライの他のノードは基本データエレメントのサブセットまたはグループを表わす。トライのルートノードまたは第1レベル(図3Aにおいてルート302とラベル付けされている)で始まり、基本データエレメントはそれらの名前の最大有効バイト(図3AにおいてN1とラベル付けされている)の値に基づいてサブツリーにグループ分けされる。それらの名前の最大有効バイトにおいて同じ値を有するすべての基本データエレメントが共通のサブツリーに互いにグループ分けされ、その値が示すリンクが、ルートノードからそのサブツリーを表わすノードに存在する。たとえば、図3Aでは、ノード303は、各自の名前のそれらの最大有効バイトN1内に同じ値2を各々が有する基本データエレメントのサブツリーまたはグループを表わす。図3Aでは、このグループは基本データエレメント305,306および307を含む。
トライの第2レベルにおいて、各基本データエレメントの名前の2番目の最大有効バイトを用いて、基本データエレメントの各グループがより小さいサブグループにさらに分割される。たとえば、図3Aでは、ノード303によって表わされる基本データエレメントのグループが、2番目の最大有効バイトN2を用いてサブグループにさらに細分割される。ノード304は、それらの最大有効バイトN1内に値2を有し、かつ各自の名前のそれらの2番目の最大有効バイトN2内に値1を有する基本データエレメントのサブグループを表わす。このサブグループは基本データエレメント305および306を含む。
細分割のプロセスは、親ノードから各子ノードのリンクを作成するトライの各レベルで継続し、子ノードは親ノードによって表わされる基本データエレメントのサブセットを表わす。このプロセスは、トライのリーフに個別の基本データエレメントしか存在しなくなるまで継続する。リーフノードはリーフのグループを表わす。図3Aでは、ノード304がリーフノードである。ノード304によって表わされる基本データエレメントのグループは、基本データエレメント305および306を含む。図3Aでは、このグループは、個別の基本データエレメント305および306に、それらの名前の3番目の最大有効バイトを用いてさらに細分割される。N3=3の値は基本データエレメント305に至り、値N3=5は基本データエレメント306に至る。この例では、それらの完全な名前のうち、基本データエレメント305および306を完全に識別するのに3つの有効バイトのみで十分である。同様に、基本データエレメント307を識別するのに名前からの2つの有効バイトのみで十分である。
この例は、基本データエレメントの所与の混合において、名前のバイトのサブセットのみがツリー内の基本データエレメントを識別する役割を果たし、固有の基本データエレメントに到達するのに名前全体は不要であることを示す。また、基本データエレメントまたは基本データエレメントのグループは各々が、それらを固有に識別できるようにするために異なる数の有効バイトを必要とし得る。ゆえに、ルートノードから基本データエレメントまでのトライの深さは基本データエレメント毎に異なり得る。さらに、トライにおいて、各ノードは下位のサブツリーに下降する異なる数のリンクを有し得る。
そのようなトライでは、各ノードは、このノードにどのように到達するかを指定するバイトのシーケンスで構成される名前を有する。たとえば、ノード304についての名前は「21」である。また、ツリー内のエレメントの現在の分布におけるエレメントを固有に識別するエレメントの名前からのバイトのサブセットは、ルートノードからこの基本データエレメントまでの「パス」である。たとえば、図3Aでは、値213を有するパス301が基本データエレメント305を識別する。
ここに記載するトライ構造は、ツリー内のエレメントの名前のすべての区別バイトが1レベルの深さをトライに追加するため、深いツリー(すなわち多くのレベルを有するツリー)を作成し得る。
なお、図3A〜図3Eのツリーデータ構造は左から右に描かれている。したがって、図の左側から図の右側に移動するにつれて、ツリーの高レベルからツリーの低レベルに移動する。所与のノードの下位に(すなわち図3A〜図3Eの所与のノードの右側に向かって)、名前からの区別バイトの一定値によって選択される任意の子について、その子の下位のサブツリーに存在しているすべてのエレメントは、当該エレメントの名前内のその対応するバイト内に同じ値を有する。
次に、入力候補エレメントを前提として、トライ構造のコンテンツ連想ルックアップのための方法を説明する。この方法は、候補エレメントの名前を用いるトライ構造のナビゲーションを伴い、その後、分析およびスクリーニングが続いて行なわれて、コンテンツ連想ルックアップ全体の結果として何を戻すべきかが決定される。言い換えると、トライナビゲーションプロセスは第1の結果を戻し、次に、その結果に対して分析およびスクリーニングが行われて、コンテンツ連想ルックアップ全体の結果が判定される。
トライナビゲーションプロセスを開始するために、候補エレメントの名前から最大有効バイトの値を用いて、ルートノードから、それらの名前の最大有効バイト内にその同じ値を有する基本データエレメントのサブツリーを表わす後続ノードまでのリンク(その値によって示される)が選択される。このノードから進んで、候補エレメントの名前からの第2のバイトを調べ、その値が示すリンクを選択することによって、1レベル深く(または低く)トライの中へと進み、それらの名前からの少なくとも2つの有効バイトにおいて候補エレメントと共有するようになった基本データエレメントのより小さいサブグループが選択される。このプロセスは、1つの基本データエレメントに到達するまで、または候補エレメントの名前からの対応するバイトの値と一致するリンクがなくなるまで継続される。これらの条件のいずれか一方の下で、ツリーナビゲーションプロセスが終了する。1つの基本データエレメントに到達すると、それはトライナビゲーションプロセスの結果として戻され得る。そうでない場合、1つの代替案は「欠落」を報告することである。別の代替案は、ナビゲーションが終了したノードをルートとするサブツリー内にある複数の基本データエレメントを戻すことである。
トライナビゲーションプロセスが終了すると、他の基準および要件を用いてトライナビゲーションプロセスの結果が分析されスクリーニングされて、コンテンツ連想ルックアップの結果として何を戻すべきかが決定され得る。たとえば、1つの基本データエレメントまたは複数の基本データエレメントがトライナビゲーションプロセスによって戻された場合は、それらは、コンテンツ連想ルックアップの結果として戻される資格を得る前に、候補エレメントの名前と一定の最小数のバイトを共有しているという付加的な要件があり得る(そうでない場合、コンテンツ連想ルックアップは欠落を戻す)。スクリーニング要件の別の例は、トライナビゲーションプロセスが、複数の基本データエレメント(トライナビゲーションが終了したノードをルートとする)がトライナビゲーションプロセスの結果として戻されるように、1つの基本データエレメントに到達することなく終了した場合は、これら複数の基本データエレメントは、これらエレメントの数が一定の指定された制限未満である場合にのみ、コンテンツ連想ルックアップ全体の結果として戻される資格を得るようなものであってもよい(そうでない場合、コンテンツ連想ルックアップは欠落を戻す)。複数の要件同士の組合せを使用して、コンテンツ連想ルックアップの結果を判定してもよい。このように、ルックアッププロセスは、「欠落」を報告するかもしくは1つの基本データエレメントを戻し、または1つの基本データエレメントでない場合は、候補エレメントを導出するための良好な開始点である可能性が高い一組の基本データエレメントを戻す。
以下に記載する図3B〜図3Eは、図3Aに示すツリーデータ構造の変形および変更に関する。これらの変形は、図3Aに示すトライデータ構造に対する向上および利点を提供するが、データ構造をナビゲートするためのプロセスは図3Aを参照して上記したプロセスと同様である。すなわち、図3B〜図3Eに示すツリーデータ構造のためのツリーナビゲーションが終了した後、続いて分析およびスクリーニングが行われてコンテンツ連想ルックアップ全体の結果が判定され、プロセス全体は、欠落、1つの基本データエレメント、または候補エレメントを導出するための良好な開始点である可能性が高い一組の基本データエレメントを戻す。
図3Bは、基本データエレメントをそれらの名前に基づいて組織化するために用いられ得る別のデータ組織システムを示す。図3Bに示す例では、各基本データエレメントは、当該基本データエレメントのコンテンツ全体から構築される別個の名前を有しており、この名前は単に当該基本データエレメントの全バイトで構成されており、これらのバイトは、それらが基本データエレメント内に存在しているのと同じ順序で名前内に現われる。図3Bは、1つのリンクが下位のサブツリー内の基本データエレメントの名前から(図3Aのトライに用いられる単一のバイトではなく)複数のバイトを使用して再分割または次のレベルのグループ分けを作成する、よりコンパクトな構造を示す。親ノードから子ノードへのリンクは、ここでは複数のバイトによって示されている。さらに、任意の所与の親ノードから、各リンクは、そのリンクと関連付けられているサブツリーを区別して識別するために異なる数のバイトを使用し得る。たとえば、図3Bでは、ルートノードからノード308のリンクは名前から4バイト(N1N2N3N4=9845)を用いることによって区別されているが、ルートノードからノード309へのリンクは名前から3バイト(N1N2N3=347)を用いることによって区別されている。
なお、(所与の候補エレメントからのコンテンツを用いる)ツリーナビゲーションの際、ツリー内のいずれかの親ノードに到着すると、ツリーナビゲーションプロセスは、候補エレメントの名前から十分なバイトを調べてどのリンクを選択すべきかを明確に決定することを保証する必要がある。所与のリンクを選択するために、候補の名前からのバイトは、その特定のリンクへの移行を示す全バイトと一致しなければならない。ここでも、そのようなツリーにおいて、ツリーの各ノードは、このノードにどのように到達すべきかを指定するバイトのシーケンスで構成される名前を有する。たとえば、ノード309の名前は、これが基本データエレメント(たとえばエレメント311および312)のグループを表わしており、それらの名前の先頭の3バイトが「347」であるため、「347」であり得る。名前の先頭の3バイトが347である候補エレメントを用いてツリーをルックアップすると、このデータパターンによって、ツリーナビゲーションプロセスは図3Bに示すようにノード309に到達する。ここでも、ツリー内のエレメントの現在の混合内のエレメントを固有に識別するエレメントの名前からのバイトのサブセットは、ルートノードからこの基本データエレメントへの「パス」である。たとえば、図3Bでは、バイトのシーケンス3475は基本データエレメント312に至り、その例に示す基本データエレメントの混合内の基本データエレメント312を固有に識別する。
多様で疎らなデータについて、図3Bのツリー構造は、図3Aのトライ構造よりも柔軟でコンパクトであることが判明している。
図3Cは、基本データエレメントをそれらの名前に基づいて組織化するために用いられ得る別のデータ組織システムを示す。図3Cに示す例では、各基本データエレメントは、当該基本データエレメントのコンテンツ全体から構築される別個の名前を有しており、この名前は単に当該基本データエレメントの全バイトで構成されており、これらのバイトは、それらが基本データエレメント内に存在しているのと同じ順序で名前内に現われる。図3Cは、(必要および/または有用であれば)正規表現を使用してさまざまなリンクに至る基本データエレメントの名前からの値を指定することによってツリーおよびグループエレメントをサブツリー内にさらにコンパクト化する(図3Bに記載の組織に対する)別の変形を示す。正規表現の使用によって、同じサブツリー下の対応するバイト上の同一表現を共有するエレメントの効率的なグループ分けが可能になり、これに続いて、当該サブツリー内の別個の基本データエレメントのより局所的な曖昧性除去を行なうことができる。また、正規表現の使用によって、エレメントを下位の任意のサブツリーにマップするために必要なバイトの値を記述する、よりコンパクトな方法が可能になる。これによって、ツリーを指定するのに必要なバイトの数がさらに減少する。たとえば、正規表現318は28個の連続した「F」のパターンを指定しており、ツリーナビゲーション時にこのリンクをたどると、エレメント314に到達することができ、これは正規表現318に従って28個の連続した「F」を有するパターン320を含む。同様に、エレメント316に到達するパスは、16個の連続した「0」を有するパターンを指定する正規表現を使用するリンクまたはブランチを有する。そのようなツリーについては、ツリーナビゲーションプロセスは、どのリンクを選択すべきかを決定するためにそのような正規表現を検出して実行する必要がある。
図3Dは、基本データエレメントをそれらの名前に基づいて組織化するために用いられ得る別のデータ組織システムを示す。図3Dに示す例では、各基本データエレメントは、当該基本データエレメントのコンテンツ全体から構築される別個の名前を有する。フィンガープリンティングの方法が各エレメントに適用されて、選択されたフィンガープリントを評価するコンテンツを含むフィールドの場所が識別される。エレメント内に見つかった第1のフィンガープリントの場所におけるフィールドは次元として取扱われ、このフィールドからの一定数のバイト(たとえばxバイトであり、ここでxはエレメント内のバイトの数より実質的に小さい)が抽出されてエレメントの名前の先頭バイトとして用いられ、名前の残りのバイトは、基本データエレメントの残りのバイトで構成され、それらが基本データエレメント内に存在しているのと同じ周期的順序で現われる。この名前を用いて基本データエレメントがツリーに組織化される。この例では、エレメント内にフィンガープリントが検出されない場合、名前は、単にエレメントの全バイトをそれらがエレメント内に存在している順序で用いることによって公式化される。別個のサブツリー(フィンガープリントが見つからなかったという指示によって示される)が、すべてのそのようなエレメントをそれらの名前に基づいて保持して組織化する。
たとえば、図3Dに示すように、フィンガープリンティング技術がエレメント338(tバイトのデータ、すなわちB1B2B3…Btを含む)に適用されて、「次元1」として選択されるフィールドを識別するバイトBi+1におけるフィンガープリント場所「フィンガープリント1」が得られ得る。次に、「フィンガープリント1」によって識別された場所からのxバイトを抽出して「次元1」が形成され得、これらxバイトは図3Dの各エレメントの名前の先頭バイトN1N2…Nxとして用いられ得る。続いて、エレメント338からの残りのt−xバイト(Bi+x+1で始まり、後でB1B2B3…Biにラップアラウンドす
る)が連結され、名前の残りのバイトNx+1Nx+2…Ntとして用いられる。エレメント内
にフィンガープリントが見つからない場合、名前N1N2……Ntは単にエレメント338
からのB1B2B3…Btである。基本データエレメントは、それらの名前を用いてソートされてツリーに組織化される。たとえば、基本データエレメント(PDE)330は、パス13654…06を用いてツリーの2つのレベルをトラバースした後に識別されて到達され、バイト13654…0は次元1からのバイトであるN1N2……Nxである。(フィンガープリントが見つからなかったという指示によって示される)リンク334に沿ったルートから到達されるノード335における別個のサブツリーが、選択されたフィンガープリントを評価しなかったコンテンツを有するすべての基本データエレメントを保持して組織化する。ゆえに、この組織では、たとえばリンク336などのいくつかのリンクは、エレメント内に現われるのと同じ順序で現われるエレメントのバイトで構成される名前を用いてエレメントを組織化し得るが、たとえばリンク340などの他のリンクは、フィンガープリントを用いて公式化される名前を用いてエレメントを組織化し得る。
候補エレメントを受信すると、プロセスは上記と同一の技術を適用して候補エレメントの名前を判定し、この名前を用いてコンテンツ連想ルックアップのためにツリーをナビゲートする。ゆえに、同一の一貫した処理が基本データエレメントに(それらがツリーにインストールされると)、および候補エレメントに(それらをパーサおよび因子分解部から受信すると)適用されてそれらの名前が作成される。ツリーナビゲーションプロセスは、候補エレメントの名前を用いてツリーをナビゲートする。本実施形態では、候補エレメント内にフィンガープリントが見つからない場合、ツリーナビゲーションプロセスは、フィンガープリントを評価しなかったコンテンツを有する基本データエレメントを組織化して含んでいるサブツリーをたどってナビゲートする。
図3Eは、基本データエレメントをそれらの名前に基づいて組織化するために用いられ得る別のデータ組織システムを示す。図3Eに示す例では、各基本データエレメントは、当該基本データエレメントのコンテンツ全体から構築される別個の名前を有する。フィンガープリンティングの方法が各エレメントに適用されて、2つのフィンガープリントのいずれか一方を評価するコンテンツを含むフィールドの場所が識別される。エレメント内の第1のフィンガープリント(図3Eのフィンガープリント1)の第1の発生の場所にあるフィールドは第1の次元(次元1)として取扱われ、第2のフィンガープリント(図3Eのフィンガープリント2)の第1の発生の場所にあるフィールドは第2の次元(次元2)として取扱われる。フィンガープリンティングを用いてエレメント上の2つの別個のフィンガープリントを探すと、4つの可能なシナリオにつながる:(1)両フィンガープリントがエレメント内に見つかる、(2)フィンガープリント1は見つかるがフィンガープリント2は見つからない、(3)フィンガープリント2は見つかるがフィンガープリント1は見つからない、および(4)フィンガープリントがまったく見つからない。基本データエレメントは、上記シナリオの各々に対応する4つのサブツリーにグループ分けされ得る。図3Eでは、「FP1」はフィンガープリント1の存在を示し、「FP2」はフィンガープリント2の存在を示し、「〜FP1」はフィンガープリント1の欠如を示し、「〜FP2」はフィンガープリント2の欠如を示す。
4つのシナリオの各々について、エレメントの名前は以下のように作成される:(1)両フィンガープリントが見つかる場合、「フィンガープリント1」によって識別される場所からのxバイトが抽出されて「次元1」が形成され得、「フィンガープリント2」によって識別される場所からのyバイトが抽出されて「次元2」が形成され得、これらx+yバイトが、図3Eにおけるそのような各エレメントの名前の先頭バイトN1N2…Nx+yとして用いられ得る。続いて、エレメント348からの残りのt−(x+y)バイトが周期的に(第1の次元からのバイトの後に開始して)抽出され、連結されて名前の残りのバイトNx+y+1Nx+y+2…Ntとして用いられる。(2)フィンガープリント1は見つかるがフィンガープリント2は見つからない場合、「フィンガープリント1」によって識別される場所からのxバイトが抽出されて先頭次元が形成され得、これらxバイトはそのような各エレメントの名前の先頭バイトN1N2…Nxとして用いられ得る。続いて、エレメント348からの残りのt−xバイト(Bi+x+1から開始し、後でB1B2B3…Biにラップアラウンドする)が連結され、名前の残りのバイトNx+1Nx+2…Ntとして用いられる。(3)フィンガープリント2は見つかるがフィンガープリント1は見つからない場合、「フィンガープリント2」によって識別される場所からのyバイトが抽出されて先頭次元が形成され得、これらyバイトは、そのような各エレメントの名前の先頭バイトN1N2…Nyとして用いられ得る。続いて、エレメント348からの残りのt−yバイト(Bj+y+1から開始し、後でB1B2B3…Bjにラップアラウンドする)が連結され、名前の残りのバイトNy+1Ny+2…Ntとして用いられる。(4)エレメント内にフィンガープリントがまったく見つからない場合、名前N1N2……Ntは単にエレメント348からのB1B2B3…Btである。ゆえに、これら4つのシナリオ毎に別個のサブツリーが存在する。エレメント348のための名前(N1N2N3…Nt)を抽出するためのプロセスは、以下のように4つのシナリオについて要約することができる:
(1) フィンガープリント1およびフィンガープリント2の両方が見つかる:
N1−Nx←Bi+1−Bi+x=次元1からのxバイト
Nx+1−Nx+y←Bj+1−Bj+y=次元2からのyバイト
Nx+y+1…Nt=(tバイトのサイズの候補エレメントからの)残りのバイト=Bi+x+1Bi+x+2Bi+x+3…BjBj+y+1Bj+y+2Bj+y+3…BtB1B2B3…Bi
(2) フィンガープリント1は見つかり、フィンガープリント2は見つからない:
N1−Nx←Bi+1−Bi+x=次元1からのxバイト
Nx+1…Nt=(tバイトのサイズの候補エレメントからの)残りのバイト=Bi+x+1Bi+x+2Bi+x+3…BtB1B2B3…Bi
(3) フィンガープリント2は見つかり、フィンガープリント1は見つからない:
N1−Ny←Bj+1−Bj+y=次元2からのyバイト
Ny+1…Nt=(tバイトのサイズの候補エレメントからの)残りのバイト=Bj+y+1Bj+y+2Bj+y+3…BtB1B2B3…Bj
(4) フィンガープリントがまったく見つからない:
N1−Nx←B1−Bt
候補エレメントを受信すると、プロセスは上記と同一の技術を適用して候補エレメントの名前を判定する。本実施形態では、(フィンガープリント1およびフィンガープリント2が見つかるか否かに依存して)上記の名前構築の4つの方法が、基本データエレメントがシーブに入力される際の基本データエレメントに対するのと同様に、候補エレメントに適用される。ゆえに、同一の一貫した処理が基本データエレメントに(それらがツリーにインストールされると)、および候補エレメントに(それらをパーサおよび因子分解部から受信すると)適用されてそれらの名前が作成される。ツリーナビゲーションプロセスは、候補エレメントの名前を用いてコンテンツ連想ルックアップのためにツリーをナビゲートする。
コンテンツ連想ルックアップが成功すると、候補エレメントと同一のパターンを特定次元の場所に有する基本データエレメントがもたらされる。たとえば、両フィンガープリントが候補エレメント内に見つかると、ツリーナビゲーションプロセスは、ルートノードから開始して、それをツリーのリンク354にダウンさせる。候補エレメントが「次元1」としてパターン「99…3」を有し、「次元2」としてパターン「7…5」を有する場合、ツリーナビゲーションプロセスはノード334に到着する。これは、導出のターゲットの可能性が高い、2つの基本データエレメント(PDE352およびPDE353)を含むサブツリーに到達する。付加的な分析およびスクリーニングが(最初にメタデータを調べることによって、かつ必要であれば、続いて実際の基本データエレメントをフェッチして調べることによって)行われて、どの基本データエレメントが導出に最適であるかが判断される。ゆえに、本明細書に記載の実施形態は、シーブ内に用いられ得るさまざまなツリー構造を識別する。そのような構造の組合せまたはそれらの変形を使用して基本データエレメントが組織化され得る。いくつかの実施形態では基本データエレメントはツリー形態に組織化され、エレメントのコンテンツ全体がエレメントの名前として用いられる。しかし、バイトがエレメントの名前内に現われる順番は、必ずしも当該バイトがエレメント内に現われる順番とは限らない。エレメントの一定のフィールドが次元として抽出されて名前の先頭バイトを形成するために用いられ、エレメントの残りのバイトは残りの名前を構成する。これらの名前を用いて、エレメントはシーブ内にツリー形態で順序付けられる。名前の先頭桁を用いてツリーのより高位のブランチ(またはリンク)同士が区別され、残りの桁を用いてツリーのすべてのブランチ(またはリンク)が漸進的に区別される。ツリーの各ノードは、そのノードから発生する異なる数のリンクを有し得る。また、ノードからの各リンクは異なる数のバイトによって区別され示され得、これらのバイトの記述は、それらの仕様を表現する正規表現および他の強力な方法を用いて達成され得る。これら特徴はすべて、コンパクトなツリー構造をもたらす。ツリーのリーフノードには、個々の基本データエレメントの参照が存在している。
一実施形態では、フィンガープリンティングの方法が基本データエレメントを含むバイトに適用され得る。フィンガープリントによって識別される場所に存在するバイトの数を用いて、名前のエレメントのコンポーネントが作成され得る。1つ以上のコンポーネントが組合されて次元が提供され得る。複数のフィンガープリントを用いて複数の次元が識別され得る。これら次元は連結され、エレメントの名前の先頭バイトとして用いられ、エレメントの残りのバイトはエレメントの残りの名前を含む。次元はフィンガープリントによって識別される位置にあるため、これによって、名前が各エレメントからの一貫したコンテンツから形成されている可能性が高くなる。フィンガープリントによって位置を特定されたフィールドにおけるコンテンツの同一の値を有するエレメントは、ツリーの同一のレッグに沿って互いにグループ分けされる。このように、同様のエレメントはツリーデータ構造内に互いにグループ分けされる。内部にフィンガープリントが見つからないエレメントは、それらの名前の代替の公式化を用いて、別個のサブツリー内に互いにグループ分けされ得る。
一実施形態では、フィンガープリンティングの方法がエレメントのコンテンツに適用されて、エレメントのコンテンツ内の(上記の)骨格データ構造のさまざまなコンポーネント(または署名)の場所が判定され得る。あるいは、エレメントのコンテンツ内部の一定の固定オフセットを選択してコンポーネントの位置を特定してもよい。他の方法を用いてエレメントの骨格データ構造のコンポーネントの位置を特定してもよく、当該方法として、エレメントをパースして一定の宣言された構造を検出し、その構造内のコンポーネントの位置を特定することがあるが、これに限定されない。エレメントの骨格データ構造のさまざまなコンポーネントを次元と見なすことができるため、これらの次元同士の連結、およびそれに続く各エレメントの残りのコンテンツを用いて、各エレメントの名前が作成される。名前を用いて基本データエレメントが順序付けられてツリーに組織化される。
別の実施形態では、エレメントの一定の構造を検出するためにエレメントがパースされる。この構造内の一定のフィールドは次元として識別される。複数のそのような次元は連結されて名前の先頭バイトとして用いられ、エレメントの残りのバイトはエレメントの残りの名前を含む。次元はエレメントをパースしてその構造を検出することによって識別される位置にあるため、これによって、名前が各エレメントからの一貫したコンテンツから形成されている可能性が高くなる。パースすることによって位置を特定されたフィールドにおけるコンテンツの同一の値を有するエレメントは、ツリーの同一のレッグに沿って互いにグループ分けされる。このように、ここでも、同様のエレメントはツリーデータ構造内に互いにグループ分けされる。
いくつかの実施形態では、ツリーデータ構造内の各ノードは自己記述仕様を含む。ツリーノードは1つ以上の子を有する。各子エントリは、当該子へのリンク上の区別バイトについての情報、および当該子ノードの参照を含む。子ノードはツリーノードまたはリーフノードであり得る。図3Fは、本明細書に記載のいくつかの実施形態に従う、自己記述ツリーノードデータ構造を提示する。図3Fに示すツリーノードデータ構造は、(A)ルートノードからこのツリーノードへのパスに関連する情報であって、以下のコンポーネントのすべてまたはサブセットを含む:名前からこのツリーノードに到達するためのバイトの実際のシーケンス、ルートノードからこのノードに到達するために消費する名前のバイトの数、この消費するバイトの数が何らかの予め指定された閾値よりも大きいか否かの指示、ならびに、このノードへのパスを記述し、ツリーのコンテンツ連想検索に、およびツリーの構築に関連する決定に有用な他のメタデータ、(B)ノードが有する子の数を指定し、(C)各子(各子はツリーの1つのブランチに対応する)について、(1)子ID、(2)ツリーのこのリンクを下位に移行させるために名前の後続バイトから必要とされる区別バイトの数、(3)それをこのリンクにダウンさせる名前からのバイトの実際値についての仕様、および(4)子ノードの参照を指定する。
図3Gは、本明細書に記載のいくつかの実施形態に従う、自己記述リーフノードデータ構造を提示する。リーフノードは1つ以上の子を有する。各子は基本データエレメントへのリンクである。各子エントリは、基本データエレメントへのリンク上の区別バイトについての情報、基本データエレメントの参照、重複および導出物のカウント、ならびに基本データエレメントについての他のメタデータを含む。図3Gに示すリーフノードデータ構造は、(A)ルートノードからこのリーフノードへのパスに関連する情報であって、以下のコンポーネントのすべてまたはサブセットを含む:名前からこのリーフノードに到達するためのバイトの実際のシーケンス、ルートノードからこのノードに到達するために消費する名前のバイトの数、この消費するバイトの数が何らかの予め指定された閾値よりも大きいか否かの指示、ならびに、このノードへのパスを記述し、ツリーのコンテンツ連想検索に、およびツリーの構築に関連する決定に有用な他のメタデータ、(B)ノードが有する子の数を指定し、(C)各子(各子はリーフノード下の1つの基本データエレメントに対応する)について、(1)子ID、(2)基本データエレメントへのツリーのこのリンクを下位に移行させるために名前の後続バイトから必要とされる区別バイトの数、(3)それをこのレッグにダウンさせる名前からのバイトの実際値についての仕様、(4)ツリーのこのパス上のツリーを終了させる基本データエレメントの参照、(5)いくつの重複および導出物がこの基本データエレメントを指しているかのカウント(これは、ストレージシステム内のデータが削除されるとシーブからエントリを削除可能であるか否かを確かめるために用いられる)、ならびに(6)基本データエレメントのサイズを含む基本データエレメントについての他のメタデータ等を指定する。
新規な基本データエレメントがツリーにインストールされる効率を増加させるために、いくつかの実施形態では、ツリーのリーフノードで維持される基本データエレメント毎に付加的なフィールドがリーフノードデータ構造に組込まれる。なお、新規なエレメントをツリーに挿入する必要がある場合、サブツリー内のどこに新規なエレメントを挿入すべきかを決定するために、またはサブツリーのさらなるパーティション分割をトリガするか否かを決定するために、対象のサブツリー内の基本データエレメントの各々の名前またはコンテンツのさらなるバイトが必要であり得る。これら付加的なバイトが必要であるので、新規なエレメントに対してこれらのエレメント毎に関連の区別バイトを抽出するために、対象の基本データエレメントのうちのいくつかをフェッチすることが必要であり得る。このタスクに必要なIOの数を減らして最適化する(かつ、ほとんどの場合は完全になくす)ために、リーフノード内のデータ構造は、そのリーフノード下の各基本データエレメントの名前からの一定数の付加的なバイトを含む。これら付加的なバイトはナビゲーションルックアヘッドバイトと称され、新規な受信エレメントに対して基本データエレメントをソートするのに役立つ。所与の基本データエレメントについてのナビゲーションルックアヘッドバイトは、基本データエレメントがシーブにインストールされると、リーフノード構造にインストールされる。この目的で保持すべきバイトの数は、関与するサブツリーの深さ、およびそのサブツリー内の基本データエレメントの密度を含むさまざまな基準を用いて静的にまたは動的に選択され得る。たとえば、ツリーの浅いレベルにインストールされている基本データエレメントについては、このソリューションは、非常に深いツリー内に存在する基本データエレメントに対してよりも長いナビゲーションルックアヘッドフィールドを追加し得る。また、新規なエレメントがシーブにインストールされており、かつ既存のターゲットサブツリー内に多くの基本データエレメントが既にある(差し迫った再パーティション分割の可能性が高い)場合は、付加的なナビゲーションルックアヘッドバイトは、新規な基本データエレメントがサブツリーにインストールされている間、その新規な基本データエレメントのために保持され得る。
図3Hは、ナビゲーションルックアヘッドフィールドを含むリーフノードについてのリーフノードデータ構造を提示する。このデータ構造は、(A)ルートノードからこのリーフノードへのパスに関連する情報であって、以下のコンポーネントのすべてまたはサブセットを含む:名前からこのリーフノードに到達するためのバイトの実際のシーケンス、ルートノードからこのノードに到達するために消費する名前のバイトの数、この消費するバイトの数が何らかの予め指定された閾値よりも大きいか否かの指示、ならびに、このノードへのパスを記述し、ツリーのコンテンツ連想検索に、およびツリーの構築に関連する決定に有用な他のメタデータ、(B)ノードが有する子の数を指定し、(C)各子(各子はリーフノード下の1つの基本データエレメントに対応する)について、(1)子ID、(2)基本データエレメントへのツリーのこのリンクを下位に移行させるために名前の後続バイトから必要とされる区別バイトの数、(3)それをこのレッグにダウンさせるバイトの実際値についての仕様、(4)ツリーのこのパス上のツリーを終了させる基本データエレメントの参照、(5)何バイトのナビゲーションルックアヘッドが基本データエレメントのために保持されているか、およびそれらのバイトの実際値を指定するナビゲーションルックアヘッドフィールド、(6)いくつの重複および導出物がこの基本データエレメントを指しているかのカウント(これは、ストレージシステム内のデータが削除されるとシーブからエントリを削除可能であるか否かを確かめるために用いられる)、ならびに(7)基本データエレメントのサイズを含む基本データエレメントについての他のメタデータ等を指定する。
いくつかの実施形態では、ツリーのさまざまなブランチを用いて、子サブツリーに至るリンクに沿った区別バイトを範囲デリミタと解釈することによって形成されるグループまたは範囲にさまざまなデータエレメントがマップされる。その子サブツリー内のすべてのエレメントは、エレメント内の対応するバイトの値が、特定の子サブツリーへのリンクに指定される区別バイトの値以下となるようなものである。ゆえに、各サブツリーはこうして、特定の範囲内に収まる値を有するエレメントのグループを表わすことになる。所与のサブツリーの内部で、ツリーの各後続レベルはエレメントのセットをより小さい範囲に漸進的に分割する。本実施形態は、図3Fに示す自己記述ツリーノード構造のコンポーネントに異なる解釈を提供する。図3FのN個の子は、ツリーノードデータ構造内でそれらの区別バイトの値によって順序付けられ、非重複範囲の順序付けられたシーケンスを表わす。N個のノードに対して、N+1個の範囲が存在し、最低のまたは1番目の範囲は最小エントリ以下の値を含み、N+1番目の範囲はN番目のエントリよりも大きい値を含む。N+1番目の範囲は範囲外として取扱われるので、N個のリンクは下位のN個のサブツリーまたは範囲に至る。
たとえば、図3Fでは、子1は最低範囲を規定しており、その範囲を区別するために(abef12d6743aの値の)6バイトを使用しており、子1の範囲は00000000からabef12d6743aである。候補エレメントの対応する6バイトは、終了値を含むこの範囲内に収まり、この子についてのリンクが選択される。候補エレメントの対応する先頭6バイトが範囲デリミタabef12d6743aよりも大きい場合、子1は選択されない。候補が子2の範囲内に収まるか否かを調べるためには、2つの条件を満たす必要があり、第1に、候補は直前の子(この例では子1)の範囲外にある必要があり、第2に、その名前の中の対応するバイトは子2の範囲デリミタ以下である必要がある。この例では、子2の範囲デリミタはdcfaの値の2バイトで記述されている。ゆえに、候補エレメントについての対応する2バイトはdcfa以下である必要がある。この方法を用いて、ツリーノード内の候補エレメントおよびすべての子を調べて、N+1個の範囲のうちのどれに候補エレメントが収まるかを確認することができる。図3Fに示す例では、候補エレメントの名前の対応する4バイトが、f3231929である子Nへのリンクについての区別バイトの値よりも大きい場合、欠落状態が検出される。
ツリーナビゲーションプロセスは、この新たな範囲ノードを収容するように修正され得る。範囲ノードに到着すると、そのノードから発生する所与のリンクを選択するために、候補の名前からのバイトは、その特定のリンクについて規定された範囲内に収まる必要がある。候補の名前からのバイトの値が、すべてのリンク内の対応するバイトの値よりも大きく、候補エレメントが下位のサブツリーが跨っているすべての範囲外にある場合−この場合(「範囲外状態」と称する)、欠落状態が検出され、ツリーナビゲーションプロセスは終了する。候補エレメントの名前の先頭バイトが、子サブツリーに至るリンクに沿った対応する区別バイトによって決定される範囲内に収まる場合、ツリーナビゲーションは下位のそのサブツリーに継続する。「範囲外状態」のために終了しない限り、ツリーナビゲーションは、リーフノードデータ構造に到達するまでツリーの下方へとより深く漸進的に継続し得る。
この種類の範囲ノードは、図3A〜図3Eに記載のトライノードとともにツリー構造において使用され得る。いくつかの実施形態では、ツリー構造の一定数のレベルの上位ノードがトライノードであり得、ツリーのトラバースは、候補エレメントの名前の先頭バイトと、ツリーのリンクに沿った対応するバイトとの正確な一致に基づいている。後続のノードは範囲ノードであり得、ツリーのトラバースは、候補エレメントの名前の対応するバイトが収まる範囲によって決まる。ツリーナビゲーションプロセスが終了すると、本文書で上述したように、さまざまな基準を用いて、コンテンツ連想ルックアップ全体の結果として何を戻すべきかが決定され得る。
ツリーノードおよびリーフノードを表現および使用するための方法および装置の上記の説明は、例示および説明目的で提示されているに過ぎない。それらは網羅的であること、または本発明を開示された形態に限定することを意図していない。したがって、多くの変更および変形が当業者に明らかになるであろう。
候補エレメントが入力として提示されると、上記のツリーノードおよびリーフノード構造をトラバースすることができ、ツリーのコンテンツ連想ルックアップを候補エレメントのコンテンツに基づいて実行することができる。候補エレメントの名前は、基本データエレメントがシーブにインストールされたときに基本データエレメントの名前が基本データエレメントのコンテンツから構築されたのと同様に、候補エレメントのバイトから構築される。入力候補エレメントを前提として、ツリーのコンテンツ連想ルックアップのための方法は、候補エレメントの名前を用いるツリー構造のナビゲーションを伴い、その後、分析およびスクリーニングが続いて行われて、コンテンツ連想ルックアップ全体の結果として何を戻すべきかが決定される。言い換えると、ツリーナビゲーションプロセスは第1の結果を戻し、次に、その結果に対して分析およびスクリーニングが行なわれて、コンテンツ連想ルックアップ全体の結果が判定される。
候補と同じ名前の先頭バイト(またはそれらが同じ範囲に収まるようなバイト)を有する基本データエレメントがある場合、ツリーは、リンクによって示されるエレメントのサブツリーの形態の基本データエレメントのそのサブセットを識別する。一般的に、各ツリーノードまたはリーフノードは、ツリーナビゲーションプロセスが、存在する場合はどの送信リンクを選択すべきかを判断して、入力エレメントの名前の対応するバイトと、選択されたリンクに沿ってツリーがナビゲートされると到達するノードのアイデンティティとに基づいてツリー内の次の下位レベルにナビゲートすることを可能にする情報を記憶し得る。各ノードがこの情報を含んでいる場合は、ツリーナビゲーションプロセスは、一致が見つからなくなるまで(この点で、ツリーナビゲーションプロセスは、現在のノードをルートとするサブツリー内に存在する一組の基本データエレメントを戻すことができる)、または基本データエレメントに到達するまで(この点で、ツリーナビゲーションプロセスは、基本データエレメントおよび任意の関連のメタデータを戻すことができる)、ツリー内の各レベルに再帰的にナビゲートダウンし得る。
ツリーナビゲーションプロセスが終了すると、他の基準および要件を用いてツリーナビゲーションプロセスの結果が分析されスクリーニングされて、コンテンツ連想ルックアップ全体の結果として何を戻すべきかが決定され得る。まず、候補と共通の名前から最多数の先頭バイトを有する基本データエレメントを選ぶことができる。次に、1つの基本データエレメントまたは複数の基本データエレメントがツリーナビゲーションプロセスによって戻された場合は、それらは、コンテンツ連想ルックアップの結果として戻される資格を得る前に、候補エレメントの名前と一定の最小数のバイトを共有しているという付加的な要件があり得る(そうでない場合、コンテンツ連想ルックアップは欠落を戻す)。スクリーニング要件の別の例は、ツリーナビゲーションプロセスが、複数の基本データエレメント(ツリーナビゲーションが終了したノードをルートとする)がツリーナビゲーションプロセスの結果として戻されるように、1つも基本データエレメントに到達することなく終了した場合は、これら複数の基本データエレメントは、これらエレメントの数が4〜16個のエレメントといった一定の指定された制限未満である場合にのみ、コンテンツ連想ルックアップ全体の結果として戻される資格を得るようなものであってもよい(そうでない場合、コンテンツ連想ルックアップは欠落を戻す)。複数の要件同士の組合せを使用して、コンテンツ連想ルックアップの結果を判定してもよい。複数の候補がまだ残っている場合は、ナビゲーションルックアヘッドバイトおよび関連のメタデータを調べて、どの基本データエレメントが最適であるかを決定してもよい。選択を1つの基本データエレメントにまだ狭めることができない場合は、複数の基本データエレメントを導出機能に供給してもよい。このように、ルックアッププロセスは、「欠落」を報告するかもしくは1つの基本データエレメントを戻し、または1つの基本データエレメントでない場合は、候補エレメントを導出するための良好な開始点である可能性が高い一組の基本データエレメントを戻す。
ツリーは、効率的なコンテンツ連想アクセスのために設計される必要がある。バランスの取れたツリーは、データの大部分について同程度のアクセス深度を提供する。ツリーのいくつかの上位レベルはプロセッサキャッシュ内に、次のいくつかのレベルは高速メモリ内に、その後続レベルはフラッシュストレージに存在していることが多いと予想される。超大型データセットについては、1つ以上のレベルがフラッシュストレージ内に、またはさらにはディスク内に存在しなければならない可能性もある。
図4は、本明細書に記載のいくつかの実施形態に従う、256TBの基本データがどのようにツリー形態に組織化され得るかの例を示し、当該ツリーがどのようにメモリおよびストレージ内にレイアウトされ得るかを提示する。ノード毎に64(26)個の子の平均ファンアウトを仮定して、基本データエレメントの参照は、(平均して)ツリーの第6レベル(すなわち5個のリンクトラバースまたはホップの後)に存在している(たとえば図3Hに示すような)リーフノードデータ構造に到達することによってアクセスされ得る。したがって、5個のホップ後のツリーの第6レベルにおけるそのような構造は、さらに230個のそのようなノードに沿って存在し、各々が平均64個の子(これらの子は基本データエレメントの参照である)を有するので、約640億個の基本データエレメントを収容している。4KBのエレメントサイズでは、これによって256TBの基本データエレメントが収容される。
ツリーは、以下のようにツリーの6レベルをトラバースすることができるようにレイアウトされ得る:オンチップキャッシュ内に存在する3レベル(約256K個のノードへのリンクのための移行を指定する約4000個の「上位レベル」ツリーノードデータ構造を含む)、メモリ内の2レベル(約10億個のリーフノードへのリンクのための移行を指定する1600万個の「中位レベル」ツリーノードデータ構造を含む)、およびフラッシュストレージ内の第6レベル(10億個のリーフノードデータ構造を収容する)。フラッシュストレージ内のツリーのこの第6レベルに存在している10億個のリーフノードデータ構造は、640億個の基本データエレメントの参照(リーフノード毎に平均で64個のエレメント)を供給する。
図4に示す例では、第4および第5レベルにおいて、各ノードは平均で16バイト/エレメント(子IDに1バイト、たとえばPDEの6バイト参照、およびさらに、バイトカウントに1バイト、およびさらに、実際の移行バイトを指定するために平均で8バイト、および何らかのメタデータ)を費やす。第6レベルにおいて、各リーフノードは平均で48バイト/エレメント(子IDに1バイト、バイトカウントに1バイト、実際の移行バイトを指定するために8バイト、基本データエレメントの6バイト参照、この基本データエレメントからの導出物のカウントのために1バイト、ナビゲーションルックアヘッドの16バイト、基本データエレメントのサイズに2バイト、および13バイトの他のメタデータ)を費やし、したがって、ツリーに必要なフラッシュストレージ内の全容量(基本データエレメントの参照を含み、いずれかのメタデータを含む)は約3テラバイトである。ツリーの上位ノードに必要な全容量はこのサイズのほんの一部である(ノードが少なく、子ノードのより緊密な参照を指定するのに必要なバイトが少なくて済み、ノード毎に必要なメタデータが少なくて済むため)。この例では、上位ツリーノードは平均で8バイト/エレメント(子IDに1バイト、バイトカウントに1バイト、およびさらに、実際の移行バイトを指定するために平均で3〜4バイト、および子ノードの2〜3バイト参照)を費やす。全体として、この例では、256TBの基本データを有する合成データセットが、3TB(または256TBの1.17%)の付加的な装置を用いて10億個のグループにソートされる。
256TBの基本データの各々が4KBの640億個の基本データエレメントを含む図4に示す例では、640億個の基本データエレメント同士を完全に区別するために5バイト(または36ビット)未満のアドレスが必要である。コンテンツ連想の観点から、データの混合が、平均4バイトの漸進的な名前が最初の3レベルの各々で消費され、8バイトが次の3レベルの各々で消費されるようなものである場合、(平均で)合計36バイト(288ビット)の名前が640億個の基本データエレメントのすべてを区別することになる。これら36バイトは、各エレメントを構成する4KBの1%未満である。4KBの基本データエレメントがそのバイトの1%(またはさらには5〜10%)によって識別可能である場合は、(バイトの大半を構成する)残りのバイトはゆらぎに耐えることができ、そのようなゆらぎを有する候補でもこの基本データエレメントに到達することができ、そこからの導出のために考慮され得る。
なお、(下位のさまざまな下位のサブツリー同士を区別するための)任意の所与のリンク上に必要なバイトの数は、データセットを含むエレメントの混合内の実際のデータによって支配される。同様に、所与のノードから出るリンクの数もデータによって異なる。自己記述ツリーノードおよびリーフノードデータ構造は、リンク毎に必要なバイトの実際の数および値、ならびに任意のノードから発生するリンクの数を宣言する。
ツリーのさまざまなレベルで費やされるキャッシュ、メモリ、およびストレージの量を制限するようにさらに制御して、入力を、増分ストレージの割当てられたバジェット内で可能な限り多くの区別されたグループにソートすることができる。エレメント同士を完全に区別するために非常に深いサブツリーを必要とするデータの密度およびポケットが存在する状況に対処するために、そのような密度は、大きい一組の関連のエレメントをツリーの一定の深さ(たとえば第6レベル)におけるフラットなグループにグループ分けし、これらに対して合理化された検索および導出を行なうことによって(まずナビゲーションルックアヘッドおよびメタデータを調べて最良の基本データエレメントを判定するか、または(フォールバックとして)残りのデータについて当該方法によって与えられる全導出ではなく重複のみを探すことによって)効率的に対処され得る。これによって非常に深いツリーの作成が回避される。別の代替案は、これらのレベルが利用可能なメモリに収まる限り、(多くのレベルを有する)深いツリーを許可することである。より深いレベルがフラッシュまたはディスクにスピルアウトした瞬間に、ツリーをそのレベルから前方にフラット化して、待ち時間を最小化するための工程を取ることができ、そうしなければ、フラッシュまたはディスクに記憶されたツリーノードのより深いレベルへの複数の連続アクセスによって待ち時間が発生する。
多くの場合、各基本データエレメントを識別するのに、エレメントの名前からの全バイトの比較的小さい一部で十分であると予想される。本明細書に記載の実施形態を用いてさまざまな実世界データセットに対して行なった研究では、基本データエレメントのバイトの小さいサブセットがエレメントの大半を順序付けてソリューションを可能にする役割を果たすことが確認されている。ゆえに、そのようなソリューションは、そのオペレーションのために必要なストレージの量の観点で効率的である。
図4の例に必要なアクセスの観点から、4KBのチャンクの入力(または候補エレメント)を受信するごとに、スキームはツリー構造に問合せてリーフノードに到達するために以下のアクセスを必要とする:3つのキャッシュ参照、2つのメモリ参照(または場合によっては複数のメモリ参照)、およびさらに、リーフノードデータ構造にアクセスするためのフラッシュストレージからの1回のIO。ストレージからのこの1回のIOは4KBのページをフェッチし、これは、対象の基本データエレメントに費やされる48バイトを含む、約64個のエレメントのグループについてのリーフノードデータ構造の情報を保持する。これら48バイトは、対象の基本データエレメントについてのメタデータを含む。これによってツリールックアッププロセスが終了する。続いて、必要なIOの回数は、候補エレメントが重複であるか、導出物であるか、またはシーブにインストールすべき新規な基本データエレメントであるかに依存する。
基本データエレメントの重複である候補エレメントは、基本データエレメントをフェッチして当該重複を検証するために1回のIOを必要とする。重複が検証されると、ツリー内のメタデータを更新するためにもう1回IOがある。したがって、重複エレメントの取込みにはツリールックアップの後に2回のIOが必要であり、全部で3回のIOが必要である。
ツリールックアップに失敗し、重複でも導出物でもない候補エレメントは、当該エレメントを新たな基本データエレメントとしてシーブに記憶するためにもう1回のIO、およびツリー内のメタデータを更新するためにさらにもう1回のIOを必要とする。ゆえに、ツリールックアップに失敗する候補エレメントの取込みにはツリールックアップ後に2回のIOが必要であり、全部で3回のIOが必要である。しかし、ツリールックアッププロセスがストレージIOを必要とせずに終了する候補エレメントについては、そのような候補エレメントを取込むためには全部で2回のIOで済む。
導出物である(しかし重複ではない)候補エレメントはまず、導出を計算するために必要な基本データエレメントをフェッチするために1回のIOを必要とする。ほとんどの場合、導出は(複数ではなく)1つの基本データエレメントからのものであると予想されるので、基本データエレメントをフェッチするには1回のIOのみで済むと予想される。導出の完了が成功したのに続いて、再構成プログラムおよび導出詳細を記憶されるエレメントについて作成されたエントリに記憶するためにもう1回のIOが、かつ新たな導出物を反映するようにツリー内のメタデータ(カウントなど)を更新するためにさらにもう1回のIOが必要となる。したがって、導出物となる候補エレメントの取込みには第1のツリールックアップの後にさらに3回のIOが必要であり、全部で4回のIOが必要である。
要約すると、(超大型データセット全体にわたってグローバルに冗長を利用しつつ)候補エレメントを取込み、当該候補エレメントにData Distillation(商標)法を適用するためには、約3回から4回のIOが必要である。旧来のデータ重複排除技術が必要とするものと比較して、これは典型的に候補エレメント毎にIOが1回増えただけであり、その見返りに、エレメント自体よりも細かくデータセット全体にわたってグローバルに冗長を利用することができる。
250,000回のランダムIOアクセス/秒(4KBのページへの1GB/秒のランダムアクセスの帯域幅を意味する)を提供するストレージシステムは、約62,500個の入力チャンク/秒(各々が4KBの平均サイズの入力チャンク毎に4回のIOで分割される250,000個)に対してData Distillation(商標)法を取込んで実行することができる。これによって、ストレージシステムの全帯域幅を使い果たしつつ250MB/秒の取込速度が可能になる。ストレージシステムの帯域幅の半分のみが用いられる(したがって残りの半分は記憶データのアクセスに利用可能である)場合も、そのようなData Distillation(商標)システムはやはり125MB/秒の取込速度を提供可能である。ゆえに、十分な処理能力を前提として、Data Distillation(商標)システムは、無駄のないIOで(エレメント自体よりも細かく)データセット全体にわたってグローバルに冗長を利用することができ、現在のストレージシステムに対して数百メガバイト/秒の取込速度でデータ削減を提供することができる。
ゆえに、試験結果によって確認されたように、本明細書に記載の実施形態は、無駄のないIOアクセスで、装置に必要な最小の増分ストレージで、莫大なデータストアからエレメントがあるかを検索する(導出を指定するのに必要な最小ストレージで、そこから入力エレメントが導出され得る)複雑なタスクを達成する。このように構築されたこのフレームワークによって、エレメントの全バイトのより小さい割合を用いて導出に好適なエレメントを見つけることが実行可能になり、バイトの大部分がゆらぎおよび導出に利用可能になる。このスキームがほとんどのデータに対して効果的に働く理由を説明する重要な洞察は、ツリーが、シーブ内のエレメントを特定する区別バイトおよび識別バイトの位置を特定することができる使いやすい細かい構造を提供することであり、これらのバイトは各々がデータ内の異なる深さおよび位置にあるが、それらをツリー構造内で効率的に分離して記憶できることである。
図5A〜図5Cは、本明細書に記載の実施形態を用いてデータがどのように組織化され得るかの実際の例を示す。図5Aは、512バイトの入力データ、および因子分解の結果(たとえば図2のオペレーション202を実行した結果)を示す。この例では、フィンガープリンティングが適用されてデータ内のブレークが求められるので、連続するブレークが候補エレメントを識別する。交互に現われる候補エレメントは太字および通常フォントを用いて示されている。たとえば、第1の候補エレメントは「b8ac83d9dc7caf18f2f2e3f783a0ec69774bb50bbe1d3ef1ef8a82436ec43283 bc1c0f6a82e19c224b22f9b2」であり、次の候補エレメントは「ac83d9619ae5571ad2bbcc15d3e493eef62054b0 5b2dbccce933483a6d3daab3cb19567dedbe33e952a966c49f3297191cf22aa3 1b98b9dcd0fb54a7f761415e」である、などである。図5Aの入力は、示されるように12個の可変サイズの候補エレメントに因子分解される。各チャンクの先頭バイトを用いてエレメントがシーブ内に順序付けられて組織化される。図5Bは、図5Aに示す12個の候補エレメントが、それらの名前を用いて、かつ図3Bに記載のツリー構造を用いて、どのようにツリー形態でシーブ内に基本データエレメントとして組織化され得るかを示す。各エレメントは、当該エレメントのコンテンツ全体から構築される別個の名前を有する。この例では、フィンガープリンティングが適用されて12個の候補エレメント同士の間のブレークが求められるので、各候補エレメントの先頭バイトは既にアンカーフィンガープリントと整列していることになる。したがって、各名前の先頭バイトは、このフィンガープリントをアンカーとするコンテンツの第1の次元からすでに構築されていることになる。名前の先頭バイトはさまざまなエレメントを組織化する。たとえば、エレメントの名前の最初のバイトが「0x22」と等しい場合は、トップリンクを取って基本データエレメント♯1を選択する。なお、図5Bのさまざまなリンクは、図3Bに示すツリーデータ構造を参照して説明したようにさまざまな数のバイトを用いて区別される。
図5Cは、図5Aに示す12個の候補エレメントが、図3Dを参照して説明したツリーデータ構造を用いてどのように組織化され得るかを示す。フィンガープリンティングが各エレメントのコンテンツにさらに適用されて、エレメントのコンテンツ内の2次フィンガープリントが識別される。第1のフィンガープリント(各エレメントの境界に既に存在している)および第2のフィンガープリントの場所から抽出されたコンテンツのバイトが連結されて名前の先頭バイトが形成され、これを用いてエレメントが組織化される。言い換えると、名前のエレメントは以下のように構築される:2つの次元またはフィールド(それぞれアンカーフィンガープリントおよび2次フィンガープリントによって位置を特定される)からのデータのバイトが連結されて名前の先頭バイトが形成され、残りのバイトがそれに続く。この名前の構築の選択の結果として、バイトのさまざまなシーケンスによってさまざまな基本データエレメントが(図5Bに対して)図5Cにおいてもたらされる。たとえば、基本データエレメント♯4に到達するために、ツリーナビゲーションプロセスはまず、第1の次元(すなわち第1のフィンガープリント)におけるフィールドの先頭バイトである「46093f9d」に対応するリンクを取り、次に、第2の次元(すなわち第2のフィンガープリント)に位置するフィールドの先頭バイトである「c4」に対応するリンクを取る。
図6A〜図6Cは、本明細書に記載のいくつかの実施形態に従う、それぞれ図1A〜図1Cを参照して説明したコンテンツ連想マッパー121および122にどのようにツリーデータ構造が使用され得るかを示す。
好適な基本データエレメント(そこから候補エレメントを導出することを試みる)を見つけるという困難な問題が解決すると、問題は、基本データエレメントの1つまたは小さいサブセットを調べること、および、導出を指定するのに必要な最小ストレージでそれらから候補エレメントを最適に導出することに絞り込まれる。他の目的として、ストレージシステムへのアクセス数を最小限に維持すること、ならびに導出時間および再構成時間を許容可能に維持することがある。
導出部は、1つ以上の基本データエレメントに対して行った変換の結果として候補エレメントを表現する必要があり、これらの変換を、データが取出されると導出物を再生成するために用いられる再構成プログラムとして指定する必要がある。各導出では、その固有のプログラムを構築する必要があり得る。導出部の機能は、これらの変換を識別し、再構成プログラムを最小フットプリントで作成することである。1つ以上の基本データエレメントに対して、または各エレメントの特定のフィールドに対して実行される算術、代数、または論理演算を含む、さまざまな変換が使用され得る。また、1つ以上の基本データエレメントにおけるバイトの連結、挿入、置換、および削除といった、バイト操作変換を用いてもよい。
図7Aは、本明細書に記載のいくつかの実施形態に従う、再構成プログラム内に指定され得る変換の例を提供する。この例で指定される変換の語彙は、エレメント内の特定長さのフィールドに対する算術演算、ならびに、基本データエレメント内の指定されたオフセットにおける宣言された長さのバイトの挿入、削除、付加、および置換を含む。さまざまな技術および演算が導出部によって使用されて、候補エレメントと1つ以上の基本データエレメントとの間の類似および相違が検出され、再構成プログラムが構築され得る。導出部は、根本的なハードウェアにおいて利用可能な語彙を利用してその機能を実行し得る。この作業の最終結果は、再構成プログラムについて指定される語彙で変換を指定すること、および、最小量の増分ストレージを用いて、高速データ取出しをも可能にする態様でそれを行なうことである。
導出部は、根本的なマシンの処理能力を利用し、自身に割当てられた処理予算内で作業して、システムのコストパフォーマンス制約内で可能な最良の分析を提供し得る。マイクロプロセッサコアがより容易に利用可能であると仮定して、かつストレージへのIOアクセスが高価であると仮定して、Data Distillation(商標)ソリューションは、現在のマイクロプロセッサの処理能力を利用して、数個の基本データエレメントから候補エレメントのコンテンツの局所的な分析および導出を効率的に行なうように設計されている。(超大型データに対する)Data Distillation(商標)ソリューションのパフォーマンスは、計算処理によってではなく典型的なストレージシステムのIO帯域幅によって速度が制限される。たとえば、250,000回のIO/秒をサポートする典型的なフラッシュベースのストレージシステムに対して数百メガバイト/秒の取込速度をサポートするために必要な計算および分析を行なうのに、2、3個のマイクロプロセッサコアで十分であると予想される。なお、インテルXeonプロセッサE5−2687W(10コア、3.1GHz、25MBキャッシュ)といった現在のマイクロプロセッサからの2つのそのようなマイクロプロセッサコアは、プロセッサから利用可能な全計算能力のごく一部(10分の2)である。
図7Bは、本明細書に記載のいくつかの実施形態に従う、基本データエレメントから導出されている候補エレメントの結果の例を示す。具体的には、データパターン「Elem」は基本データストアに記憶されている基本データエレメントであり、データパターン「Cand」は基本データエレメントから導出すべき候補エレメントである。「Cand」と「Elem」との間の18個の共通バイトがハイライト表示されている。再構成プログラム702は、データパターン「Cand」がデータパターン「Elem」からどのように導出され得るかを指定する。図7Bに示すように、再構成プログラム702は、1バイトの置換、6バイトの挿入、3バイトの削除、7バイトのバルク置換を用いることによって「Elem」から「Cand」をどのように導出するかを示す。導出物を指定するコストは20バイト+3バイト参照=23バイトであり、これは元のサイズの65.71%である。なお、示される再構成プログラム702は人間が読取り可能なプログラムの表現であり、プログラムが本明細書の記載の実施形態によってどのように実際に記憶されるかではない場合がある。同様に、乗算および加算などの算術演算に基づく他の再構成プログラムも図7Bに示されている。たとえば、「Elem」がbc1c0f6a790c82e19c224b22f900ac83d9619ae5571ad2bbec152054ffffff83であり、「Cand」がbc1c0f6a790c82e19c224b22f91c4da1aa0369a0461ad2bbec152054ffffff83である場合は、乗算(00ac83d9619ae557)*2a = [00]1c4da1aa0369a046を用いて示されるように8バイトの差が導出され得る。導出物を指定するコストは4バイト+3バイト参照=7バイトであり、これは元のサイズの20.00%である。あるいは、「Elem」がbc1c0f6a790c82e19c224b22f9b2ac83ffffffffffffffffffffffffffffb283であり、「Cand」がbc1c0f6a790c82e19c224b22f9b2ac8300000000000000000000000000002426である場合は、加算を用いて、たとえば、オフセット16で始まる16バイト領域に0x71a3を加算して繰り上げを切り捨てることによって、示されるように16バイトの差が導出され得る。導出物を指定するコストは5バイト+3バイト参照=8バイトであり、これは元のサイズの22.85%である。なお、図7Aのサンプル符号化は例示目的で選択されているに過ぎない。図7Bの例は32バイトのデータサイズを有しており、したがって、エレメント内の長さおよびオフセットフィールドには5ビットで十分である。大きいエレメント(たとえば4KBのエレメント)については、これらのフィールドのサイズを12ビットに増加させる必要がある。同様に、サンプル符号化は3バイトまたは24ビットの参照サイズを収容する。これによって、1600万個の基本データエレメントを参照することが可能になるべきである。参照が、たとえば256TBのデータ内のいずれかの場所をアドレス指定できる必要がある場合、参照は6バイトのサイズである必要がある。そのようなデータセットを4KBのエレメントに因子分解すると、参照を指定するのに必要な6バイトは4KBのエレメントのサイズのほんの一部である。
(1つ以上の基本データエレメントから導出される)導出エレメントを指定するのに必要な情報のサイズは、再構成プログラムのサイズと、必要な(1つ以上の)基本データエレメントを指定するのに必要な参照のサイズとの合計である。候補エレメントを導出エレメントとして指定するのに必要な情報のサイズは、基本データエレメントからの候補の距離と称される。候補が複数のセットの基本データエレメントのうちのいずれか1セットから実行可能に導出され得る場合、最短距離を有する基本データエレメントのセットがターゲットとして選択される。
2つ以上の基本データエレメントから(これらの各々から導出した抽出をアセンブルすることによって)候補エレメントを導出する必要がある場合、導出部は、ストレージシステムへの付加的なアクセスのコストを考慮に入れ、それを、より小さい再構成プログラムおよびより小さい距離の利点と比較検討する必要がある。候補についての最適な再構成プログラムが作成されると、その距離が距離閾値と比較され、距離が閾値を超えない場合は導出が受付けられる。導出が受付けられると、候補エレメントは導出エレメントとして再公式化され、基本データエレメントと再構成プログラムとの組合せで置換される。候補エレメントについて作成された蒸留データへのエントリは、再構成プログラムと、関連の基本データエレメントの1つ以上の参照とで置換される。最良の導出についての距離が距離閾値を超える場合は、導出物は受付けられない。
データ削減をもたらすために、距離閾値は常に候補エレメントのサイズ未満でなければならない。たとえば、距離閾値は候補エレメントのサイズの50%に設定されてもよく、これによって、導出物は、そのフットプリントが候補エレメントのフットプリントの半分以下である場合にのみ受付けられることになり、これによって、好適な導出が存在する候補エレメント毎に2倍以上の削減が確実になる。距離閾値は、ユーザが指定した入力に基づく、またはシステムによって選択される、予め定められた割合または分数であってもよい。距離閾値は、システムの静的または動的パラメータに基づいてシステムによって決定されてもよい。
図8A〜8Eは、本明細書に記載のいくつかの実施形態に従う、入力データを固定サイズのエレメントに因子分解し、当該エレメントを図3Dおよび図3Eを参照して説明したツリーデータ構造に組織化することによってどのようにデータ削減が実行され得るかを示す。図8Aは、どのように入力データが32バイトのチャンクに単純に因子分解され得るかを示す。具体的には、図8Aは最初の10個のチャンクを、そしてたとえば4200万個のチャンクの後に現われるさらにいくつかのチャンクを示す。図8Bは、名前の先頭バイトが(アンカーフィンガープリント、2次フィンガープリントおよび3次フィンガープリントの場所に対応する)エレメントのコンテンツ内の3つの次元からのコンテンツで構成されるように構築された名前を用いる、シーブ内の基本データエレメントの組織を示す。具体的には、図8Bでは、各32バイトのチャンクが32バイトの候補エレメント(固定サイズのブロック)になる。フィンガープリンティングの方法がエレメントのコンテンツに適用される。各エレメントは、以下のように構築される名前を有する:エレメントの3つの次元またはフィールド(それぞれアンカーフィンガープリント、2次フィンガープリント、および3次フィンガープリントによって位置が特定される)からのデータのバイトが連結されて名前の先頭バイトが形成され、エレメントの残りのバイトがそれに続く。名前を用いてエレメントがシーブ内に組織化される。図8Bに示すように、最初の10個のチャンクは重複または導出物を含んでおらず、エレメントとしてシーブに順次インストールされる。図8Bは、10番目のチャンクが消費された後のシーブを示す。図8Cは、さらに数百万個のデータ入力のエレメントを消費した後の、たとえば次の4200万個のチャンクが提示された後の、その後の時点におけるシーブのコンテンツを示す。シーブは重複または導出物があるか否か調べられる。エレメントから導出不可能なチャンクはシーブにインストールされる。図8Cは、4200万個のチャンクが消費された後のシーブを示しており、たとえば16,000,010個のエレメント(3バイトの参照アドレスで論理的にアドレス指定可能)を含んでおり、残りの26,000,000個のチャンクは導出物になる。図8Dは、続いてシーブに提示されてシーブへの(エレメント番号24,789として示される)エントリの重複として識別される、新規な入力の例を示す。この例では、シーブは、エレメント24,789(チャンク9)をチャンク42,000,011について最適なエレメントとして識別する。導出機能は、新たなチャンクが正確な重複であると判断し、それをエレメント24,789の参照で置換する。導出物を表わすコストは元の35Bに対して3バイト参照であり、これは元のサイズの8.57%である。図8Dは、シーブ内の(エレメント番号187,126として示される)エントリの導出物にコンバートされる入力の第2の例(チャンク42,000,012)を示す。この例では、シーブは正確な一致がないと判断する。シーブは、エレメント187,125および187,126(チャンク8および1)を最適なエレメントとして識別する。新たなエレメントは最適なエレメントから導出される。エレメント187,125に対する導出およびエレメント187,126に対する導出が図8Dに示されている。エレメント187,125に対する導出を表わすコストは39バイト+3バイト参照=42バイトであり、これは元のサイズの120.00%である。エレメント187,126に対する導出を表わすコストは12バイト+3バイト参照=15バイトであり、これは元のサイズの42.85%である。(エレメント187,126に対する)最良の導出が選択される。再構成サイズは閾値と比較される。たとえば、閾値が50%である場合、この導出物(42.85%)は受付けられる。図8Eは、基本データエレメントから導出されるデータチャンクの2つの付加的な例を提供しており、導出物が2つの基本データエレメントからの導出によって実際に作成される一例を含む。第1の例では、チャンク42,000,013が提示される。シーブは、エレメント9,299,998(チャンク10)を最適なエレメントとして識別する。エレメント9,299,998に対する導出が図8Eに示されている。導出物を表わすコストは4バイト+3バイト参照=7バイトであり、これは元のサイズの20.00%である。再構成サイズは閾値と比較される。たとえば、閾値が50%である場合、この導出物(20.00%)は受付けられる。第2の例では、チャンク42,000,014が提示される。この例では、チャンク42,000,014は、チャンクの半分がエレメント9,299,997から最良に導出され得、チャンクの残りの半分がエレメント9,299,998から最良に導出され得るようなものである。したがって、マルチ導出エレメントが作成されてさらなるデータ削減がもたらされる。マルチエレメント導出は図8Eに示されている。このマルチ導出エレメントを表わすコストは3バイト参照+3バイト+3バイト参照=9バイトであり、これは元のサイズの25.71%である。再構成サイズは閾値と比較され、たとえば閾値が50%である場合、この導出物(25.71%)は受付けられる。なお、単一の導出エレメントからの最良の結果は45.71%であったはずである。
図8A〜8Eは、Data Distillation(商標)システムが固定サイズのブロックを消費して生成しつつデータ削減を行うのに効果的であり得るという、Data Distillation(商標)システムの重要な利点を示す。なお、固定サイズのブロックは高パフォーマンスストレージシステムにおいて非常に望ましい。Data Distillation(商標)装置を用いて、多数の固定サイズのブロックで構成される大きい受信入力ファイルが、すべての基本データエレメントが固定サイズであるように、多数の固定サイズのエレメントに因子分解され得る。導出エレメント毎の潜在的に可変サイズの再構成プログラムは互いにパックされて蒸留データファイル内にインラインに維持され得、これは続いて固定サイズのブロックにチャンク分けされ得る。ゆえに、すべての実用的な目的で、ストレージシステム内で固定サイズのブロックを消費して作成しつつ、強力なデータ削減を実行することができる。
図9A〜図9Cは、最初に図1Cに示したData Distillation(商標)スキームの例を示す。このスキームは、コンテンツ連想的にアクセスされ得る別個の基本再構成プログラムストアを使用する。そのような構造によって、基本再構成プログラムストア内に既に存在している再構成プログラムを構築する導出物の検出が可能になる。そのような導出物は、既存の再構成プログラムを参照するように再公式化され得る。これによって、再構成プログラム同士の間の冗長の検出が可能になる。図9Aでは、入力データが取込まれる。フィンガープリンティングの方法が当該データに適用され、フィンガープリント位置にチャンク境界が設定される。入力は、示されるように8個の候補エレメント(図9Aにおいて太字および通常のフォントで示される交互に現われるチャンク)に因子分解される。図9Bでは、8個の候補エレメントがシーブ内に組織化されて示されている。各エレメントは、当該エレメントのコンテンツ全体から構築される別個の名前を有する。この例では、名前のエレメントは以下のように構築される:2つの次元またはフィールド(それぞれアンカーフィンガープリントおよび2次フィンガープリントによって位置を特定される)からのデータのバイトが連結されて名前の先頭バイトが形成され、残りのバイトがそれに続く。この名前を用いてシーブ内にエレメントが順序付けられ、また、ツリー構造を介してシーブへのコンテンツ連想アクセスが提供される。図9Bはさらに、基本再構成プログラムを含む第2のコンテンツ連想構造を示す。図9Cは重複再構成を示す。いずれの基本データエレメントの重複でもない55バイトの候補エレメント(図9Cに示す)が到着すると仮定する。エレメント3が最適なエレメントとして選択され、最初の2つの次元はPDE2および3について同一であるが、88a7で始まる残りのバイトはエレメント3と一致する。新たな入力は、12バイト再構成プログラム(RP)を用いてエレメント3から導出される。符号化は図7Aに示すようなものである。なお、この例については、最大エレメントサイズは64ビットであり、すべてのオフセットおよび長さは、図7Aに示す5ビットの長さおよびオフセットとは対照的に、6ビット値として符号化される。RPストアが検索され、この新たなRPは見つけられない。このRPは基本RPストアに挿入され、その値に基づいて順序付けられる。新たなエレメントは、RPストア内の基本データエレメント3の参照、および参照4における新たに作成された基本再構成プログラムの参照として再公式化される。この導出エレメントについての全ストレージサイズは、3バイトのPDE参照、3バイトのRP参照、12バイトのRP=18バイトであり、これは、それをPDEとして記憶することに対して、サイズの31.0%である。その後、55バイトの候補エレメントのコピーが到着すると仮定する。前と同様に、エレメント3に基づいて12バイトのRPが作成される。RPストアが検索され、基本RP ID=3、RP参照=4を有するRPが見つけられる。この候補エレメントは、基本データエレメント3の参照および再構成プログラム4の参照としてシステム内に表わされる。この導出エレメントについて追加される全ストレージサイズは、3バイトのPDE参照、3バイトのRP参照=6バイトとなり、これは、それをPDEとして記憶することに対して、サイズの10.3%である。
図10Aは、本明細書に記載のいくつかの実施形態に従う、再構成プログラム内に指定された変換がどのように基本データエレメントに適用されて導出エレメントをもたらすかの例を提供する。この例は、187,126と番号付けられた基本データエレメント(この基本データエレメントは図8Cのシーブ内にも示されている)に、示される再構成プログラムによって指定されるような4つの変換(挿入、置換、削除、および付加)を適用することによって当該基本データエレメントから生成されるように指定された導出エレメントを示す。図10Aに示すように、エレメント187,126がシーブからロードされ、再構成プログラムが実行されてエレメント187,126からチャンク42,000,012が導出される。図10B〜図10Cは、本明細書に記載のいくつかの実施形態に従うデータ取出しプロセスを示す。各データ取出し要求は本質的に蒸留データ内のエレメントの形態を取り、無損失削減フォーマットで取出しエンジンに提示される。エレメント毎の無損失削減フォーマットは、関連付けられた基本データエレメントおよび再構成プログラムの参照を含む。Data Distillation(商標)装置の取出部は基本データエレメントおよび再構成プログラムをフェッチし、これらを再構成のために再構成部に供給する。蒸留データのエレメントについての関連の基本データエレメントおよび再構成プログラムがフェッチされた後、再構成部は再構成プログラムを実行して、エレメントをその本来の未削減形態で生成する。再構成を実行するためにデータ取出しプロセスが必要とする労力は、再構成プログラムのサイズおよび基本データエレメントのサイズに対して直線的である。したがって、当該システムによって高いデータ取出率を達成することができる。
蒸留データ内の無損失削減形態からその本来の未削減形態にエレメントを再構成するためには、基本データエレメントおよび当該エレメントについて指定された再構成プログラムのみをフェッチするだけでよいことが明白である。ゆえに、所与のエレメントを再構成するために、他のエレメントにアクセスするかまたは他のエレメントを再構成することは不要である。このため、Data Distillation(商標)装置は、再構成および取出しの要求のランダムなシーケンスをサービスする場合にも効率的である。なお、Lempel Ziv法といった旧来の圧縮法は、所望のブロックを含むデータのウインドウ全体をフェッチして復元する必要がある。たとえば、ストレージシステムがLempel-Ziv法を利用して32KBのウインドウを用いて4KBのデータのブロックを圧縮し、次に所与の4KBのブロックをフェッチして復元する場合、32KBのウインドウ全体をフェッチして復元する必要がある。これは、所望のデータを提供するためにより大きい帯域幅を消費し、より大量のデータを復元する必要があるため、パフォーマンスペナルティを課す。Data Distillation(商標)装置はそのようなペナルティを受けない。
Data Distillation(商標)装置は、システム内のデータ全体にわたってグローバルに冗長を効率的に発見して利用する態様でデータを組織化して記憶するようにさまざまな方法でコンピュータシステムに統合され得る。図11A〜図11Gは、本明細書に記載のいくつかの実施形態に従う、Data Distillation(商標)メカニズム(ソフトウェア、ハードウェア、またはそれらの組合せを用いて実現され得る)を含むシステムを示す。図11Aは、プロセッサ、メモリおよびデータストレージコンポーネントで構成されるハードウェアプラットフォーム上で実行されるシステムソフトウェア上で動作するソフトウェアアプリケーションを有する汎用計算プラットフォームを提示する。図11Bは、プラットフォームのアプリケーション層に統合されたData Distillation(商標)装置を示しており、各特定のアプリケーションは当該装置を用いてそのアプリケーションのためのデータセット内で冗長を利用する。図11Cは、データ仮想化層またはサービスの上位で動作するすべてのアプリケーションについて当該データ仮想化層またはサービスを提供するように使用されるData Distillation(商標)装置を示す。図11Dおよび図11Eは、サンプル計算プラットフォームのオペレーティングシステム、ファイルシステムおよびデータ管理サービスを有するData Distillation(商標)装置の2つの異なる統合形態を示す。他の統合方法として、図11Fに示すようなフラッシュベースのデータストレージサブシステムにおいて使用されるようなハードウェアプラットフォームにおける埋込計算スタックとの統合があるが、これに限定されない。
図11Gは、図11Dに示すサンプル計算プラットフォームを有するData Distillation(商標)装置の統合のさらなる詳細を提示する。図11Gは、汎用プロセッサ上のソフトウェアとして実行されるパーサおよび因子分解部、導出部、取出部、ならびに再構成部、ならびにストレージ階層のいくつかのレベルにわたって存在しているコンテンツ連想マッピング構造を有する、Data Distillation(商標)装置のコンポーネントを示す。基本データストアは、(フラッシュベースのストレージドライブといった)記憶媒体内に存在し得る。
図11Hは、Data Distillation(商標)装置がどのようにサンプル汎用計算プラットフォームとインターフェイスし得るかを示す。
ファイルシステムは、ファイル(たとえばテキスト文書、スプレッドシート、実行可能ファイル、マルチメディアファイル等)を識別子(たとえばファイル名、ファイルハンドル等)と関連付け、ファイルと関連付けられた識別子を用いることによってファイル上で操作(たとえば読出、書込、挿入、付加、削除等)を実行できるようにする。ファイルシステムによって実現されるネームスペースはフラットであってもよく、または階層状であってもよい。また、ネームスペースは多層化されてもよく、たとえば、最上層識別子が完全に分解されるまで、最上層識別子が、順次下層において1つ以上の識別子に分解されてもよい。このように、ファイルシステムは、ファイルのコンテンツを物理的に記憶する物理データストレージデバイスおよび/または記憶媒体(たとえばコンピュータメモリ、フラッシュドライブ、ディスクドライブ、ネットワークストレージデバイス、CD−ROM、DVD等)の抽象化を提供する。
情報をファイルシステムに記憶するために用いられる物理ストレージデバイスおよび/または記憶媒体は1つまたは複数のストレージ技術を用いてもよく、同一のネットワーク場所に存在してもよいし、または異なるネットワーク場所にわたって分散していてもよい。ファイルおよび当該ファイル上で実行されるように要求される1つ以上の操作と関連付けられた識別子を前提として、ファイルシステムは(1)1つ以上の物理ストレージデバイスおよび/または記憶媒体を識別することができ、(2)当該ファイルシステムによって識別された物理ストレージデバイスおよび/または記憶媒体に、当該識別子と関連付けられたファイル上で実行されるように要求された操作を実行させることができる。
システム内で読出または書込操作が実行されるたびに、異なるソフトウェアおよび/またはハードウェアコンポーネントが関与し得る。「リーダ」という用語は、所与の読出操作がシステム内で実行される際に関与するシステム内のソフトウェアおよび/またはハードウェアコンポーネントの集まりを指し得、「ライタ」という用語は、所与の書込操作がシステム内で実行される際に関与するシステム内のソフトウェアおよび/またはハードウェアコンポーネントの集まりを指し得る。本明細書に記載のデータ削減のための方法および装置のいくつか実施形態は、所与の読出または書込操作が実行される際に関与するシステムの1つ以上のソフトウェアおよび/またはハードウェアコンポーネントによって利用され得るか、またはそれに組込まれ得る。異なるリーダおよびライタは異なるデータ削減実現例を利用するかまたは組込み得る。しかし、特定のデータ削減実現例を利用するかまたは組込む各ライタは、これも同一のデータ削減実現例を利用するかまたは組込むリーダに対応する。なお、当該システムにおいて実行される読出および書込操作の中には、データ削減装置を利用しないかまたは組込まない操作もある。たとえば、Data Distillation(商標)装置またはデータ削減装置103が基本データエレメントを取出すか、または新たな基本データエレメントを基本データストアに追加すると、当該装置はデータ削減なしで読出および書込操作を直接実行することができる。
具体的には、図11Hにおいて、ライタ150Wは一般的に、所与の書込操作が実行される際に関与するシステムのソフトウェアおよび/またはハードウェアコンポーネントを指し得、リーダ150Rは一般的に、所与の読出操作が実行される際に関与するシステムのソフトウェアおよび/またはハードウェアコンポーネントを指し得る。図11Hに示すように、ライタ150Wは入力データをData Distillation(商標)装置またはデータ削減装置103に与え、Data Distillation(商標)装置またはデータ削減装置103から蒸留データ108を受信する。リーダ150Rは取出し要求109をData Distillation(商標)装置またはデータ削減装置103に与え、取出されたデータ出力113をData Distillation(商標)装置またはデータ削減装置103から受信する。
図11Hについての実現例として、Data Distillation(商標)装置またはデータ削減装置103をアプリケーション、オペレーティングシステムカーネル、ファイルシステム、データ管理モジュール、デバイスドライバ、またはフラッシュもしくはディスクドライブのファームウェアに組込むかまたは利用することがあるが、これらに限定されない。これは、図11B〜図11Fに記載のさまざまな構成および使用方法に及ぶ。
図11Iは、Data Distillation(商標)装置がブロック処理ストレージシステムにおけるデータ削減にどのように用いられ得るかを示す。そのようなブロック処理システムでは、データはブロックで記憶され、各ブロックはロジカルブロックアドレスすなわちLBAによって識別される。ブロックは、特定のLBAによって識別されるブロックに新規なデータが上書きされ得るように、絶えず変更されて上書きされている。システム内の各ブロックは候補エレメントとして取扱われ、Data Distillation(商標)装置を用いて、候補エレメントが、(特定の基本データエレメントブロックに記憶される)基本データエレメントの参照と、導出エレメントの場合は(特定の再構成プログラムブロックに記憶される)再構成プログラムの参照とを含む無損失削減形態に削減され得る。図11Iは、LBAによって識別されるブロックのコンテンツを無損失削減形態の対応するエレメントにマップするデータ構造1151を導入する。各LBAに対して、関連付けられたエレメントの仕様が存在することになる。固定サイズのブロックを用いるシステムにとっては、受信ブロック、基本データエレメントブロック1152、および再構成プログラムブロック1153がすべて固定サイズであることが便利である。このシステムでは、各基本データエレメントは個別のブロックとして記憶され得る。複数の再構成プログラムが、これも同一の固定サイズである再構成プログラムブロック内にパックされてもよい。データ構造は、基本データエレメントおよび再構成プログラムごとに、カウントフィールドの参照と、リーフノードデータ構造に存在している関連付けられたメタデータとをさらに含むため、ブロックが新規なデータで上書きされると、LBAに存在している以前のデータを有効に管理することができる。すなわち、(上書きされている)既存の基本データエレメントおよび再構成プログラムのカウントフィールドをデクリメントしなければならず、同様に、LBA内への受信データによって参照される基本データエレメントのカウントをインクリメントしなければならない。このデータ構造1151内のカウントフィールドの参照を維持することによって、上書きを迅速に管理することができるため、Data Distillation(商標)装置が提供するデータ削減を最大限に活用する高パフォーマンスのブロック処理ストレージシステムが可能になる。
図12Aは、本明細書に記載のいくつかの実施形態に従う、帯域幅が制約された通信媒体全体にわたるデータの通信のためのData Distillation(商標)装置の使用を示す。示されるセットアップでは、通信ノードAは、通信ノードBに送信すべき一組のファイルを作成する。ノードAは、Data Distillation(商標)装置を用いて、入力ファイルを、基本データストアにインストールされる基本データエレメントおよび導出エレメントのための再構成プログラムの参照とを含む蒸留データまたは蒸留ファイルに変換する。ノードAは次に、蒸留ファイルを基本データストアとともにノードBに送信する(基本データストアは、蒸留ファイルを送信する前に、送信するのと同時に、または送信した後に送信され得、さらに、基本データストアは、同一の通信チャネル上で、または蒸留ファイルを送信するために用いられる通信ファイルとは異なる通信チャネル上で送信され得る)。ノードBは基本データストアをその端における対応の構造にインストールし、続いてノードBのData Distillation(商標)装置内に存在している取出部および再構成部を介して蒸留ファイルを送り、ノードAが作成した元の一組のファイルをもたらす。ゆえに、Data Distillation(商標)装置を媒体の両端で使用して削減データのみを送信することによって、帯域幅が制約された通信媒体がより効率的に使用される。なお、Data Distillation(商標)を使用することによって、(Lempel-Zivといった従来の技術を用いて実行可能である範囲を超えて)より大きい範囲にわたって冗長を利用することができるので、さらに大型のファイルまたはファイルのグループを効率的に送信することができる。
次に、複数のノードにわたって分散しているデータをワークグループが共同して共有する広域ネットワークインストールにおけるData Distillation(商標)装置の使用を説明する。データがまず作成されると、当該データは図12Aに示すように削減されて通信され得る。広域ネットワークはデータのコピーを各サイトに維持して、当該データへの迅速なローカルアクセスを可能にする。Data Distillation(商標)装置の使用によって各サイトのフットプリントを削減することができる。さらに、続いていずれかのサイトで新規データを取込むと、新規データと既存の基本データストアのコンテンツとの間のいずれかの冗長を利用して新規データを削減することができる。
そのようなインストールでは、任意の所与のサイトにおけるデータのいずれの修正も、各サイトの基本データストアが一貫して保持されるように、すべての他のサイトに通信する必要がある。したがって、図12Bに示すように、基本データエレメントのインストールおよび削減などの更新、ならびにメタデータ更新は、本明細書に記載のいくつかの実施形態に従って各サイトの基本データストアに通信され得る。たとえば、所与のサイトのシーブに新規な基本データエレメントがインストールされると、基本データエレメントをすべての他のサイトに通信する必要がある。各サイトは、基本データエレメントの値を用いてコンテンツ連想的にシーブにアクセスし、シーブ内のどこに新たなエントリを追加する必要があるかを判断することができる。同様に、所与のサイトのシーブから基本データエレメントが削除されると、この削除を反映するようにすべての他のサイトを更新する必要がある。これが達成され得る1つの方法は、各サイトが基本データエレメントを用いてコンテンツ連想的にシーブにアクセスしてリーフノードへのどのエントリを削除する必要があるかを判断できるように、すべてのサイトに基本データエレメントを、ツリー内の関連リンクへの必要な更新およびストアからのその基本データエレメントの削除とともに通信することによってである。別の方法は、基本データエレメントが存在しているリーフノード内の基本データエレメントについてのエントリの参照をすべてのサイトに通信することである。
ゆえに、Data Distillation(商標)装置を用いて、広域ネットワークのさまざまなサイトにわたって記憶されているデータのフットプリントを削減し、ネットワークの通信リンクを効率的に使用することができる。
図12C〜図12Kは、本明細書に記載のいくつかの実施形態に従う、さまざまな使用モデルについてData Distillation(商標)装置によって生成される削減データのさまざまなコンポーネントを示す。
図12Cは、Data Distillation(商標)装置1203がどのように一組の入力ファイル1201を取込み、蒸留プロセスの完了後に一組の蒸留ファイル1205および基本データシーブまたは基本データストア1206を生成するかを示す。図12Cの基本データシーブまたは基本データストア1206自体は2つのコンポーネント、すなわち、図12Dに示すようなマッパー1207および基本データエレメント(またはPDE)1208で構成されている。
マッパー1207自体は内部に2つのコンポーネント、すなわち、ツリー全体を規定する一組のツリーノードデータ構造および一組のリーフノードデータ構造を有する。一組のツリーノードデータ構造は1つ以上のファイルに入れられ得る。同様に、一組のリーフノードデータ構造は1つ以上のファイルに入れられ得る。いくつかの実施形態では、ツリーノードファイルと称される1つのファイルが、所与のデータセット(入力ファイル1201)のために基本データエレメントについて作成されたツリーのための一組のツリーノードデータ構造全体を保持し、リーフノードファイルと称される別の1つのファイルが、そのデータセットのための基本データエレメントについて作成されたツリーのための一組のリーフノードデータ構造全体を保持する。
図12Dでは、基本データエレメント1208は、所与のデータセット(入力ファイル1201)のために作成された一組の基本データエレメントを含む。一組の基本データエレメントは1つ以上のファイルに入れられ得る。いくつかの実施形態では、PDEファイルと称される1つのファイルが、所与のデータセットのために作成された一組の基本データエレメント全体を保持する。
ツリーノードファイル内のツリーノードは、ツリーノードファイル内の他のツリーノードの参照を含む。ツリーノードファイル内のツリーノードの最深層(または最低レベル)は、リーフノードファイル内のリーフノードデータ構造へのエントリの参照を含む。リーフノードファイル内のリーフノードデータ構造へのエントリは、PDEファイル内の基本データエレメントの参照を含む。
ツリーノードファイル、リーフノードファイル、およびPDEファイルは、装置によって作成されるすべてのコンポーネントの詳細を示す図12Eに示されている。図12Eは、ファイル1、ファイル2、ファイル3、…ファイルNと名付けられたN個のファイルを含む一組の入力ファイル1201を示しており、当該ファイルはData Distillation(商標)装置によって削減されて、一組の蒸留ファイル1205および基本データシーブのさまざまなコンポーネント、すなわち、ツリーノードファイル1209、リーフノードファイル1210、およびPDEファイル1211を生成する。蒸留ファイル1205は、file1.dist, file2.dist, file3.dist…fileN.distと名付けられたN個のファイルを含む。Data Distillation(商標)装置は入力データをその構成要素に因子分解し、2つのカテゴリのデータエレメント、すなわち基本データエレメントおよび導出エレメントを作成する。蒸留ファイルは無損失削減フォーマットのデータエレメントの記述を含み、PDEファイル内の基本データエレメントの参照を含む。入力ファイル1201内の各ファイルは、蒸留ファイル1205内の対応する蒸留ファイルを有する。たとえば、入力ファイル1201内のファイル1 1212は、蒸留ファイル1205内のfile1.distと名付けられた蒸留ファイル1213に対応する。
なお、図12Eは、図1Aに従う蒸留データおよび基本データストアの組織に基づいてデータ蒸留装置によって作成されたさまざまなコンポーネントを示しており、再構成プログラムは蒸留ファイル内のエレメントの無損失削減表現に入れられている。なお、(図1Bに従う)いくつかの実施形態では、再構成プログラムを基本データストアに入れて、それらを基本データエレメントと同様に取扱うことができる。蒸留ファイル内のエレメントの無損失削減表現は、(再構成プログラム自体を含むのではなく)基本データストア内の再構成プログラムの参照を含む。これらの実施形態では、再構成プログラムは基本データエレメントと同様に取扱われてPDEファイル1211内に生成される。さらに別の実施形態では、図1Cに従って、再構成プログラムは、基本データエレメントとは別個に、再構成プログラムストアと称される構造に記憶される。そのような実施形態では、蒸留ファイル内のエレメントの無損失削減表現は、再構成プログラムストア内の再構成プログラムの参照を含む。そのような実施形態では、図12Fに示すように、基本データエレメントのツリー組織のためのツリーノードファイル1209、リーフノードファイル1210およびPDEファイル1211を生成することに加えて、装置は、再構成ツリーノードファイル1219および再構成リーフノードファイル1220と称される第2の一組のツリーおよびリーフノードファイルを、RPファイル1221と称されるすべての再構成プログラムを含むファイルとともに生成する。
図12Eに示すData Distillation(商標)装置はさらに、ツリーノードファイル1209、リーフノードファイル1210、PDEファイル1211および蒸留ファイル1205の1つ以上における演算を支配する構成および制御情報を記憶する。あるいは、この情報を含む第5のコンポーネントが生成されてもよい。図12Fに示す装置と同様に、構成および制御情報は図12Fに示すさまざまなコンポーネントの1つ以上に記憶されてもよく、またはそれは、この目的で生成された別のコンポーネントに記憶されてもよい。
図12GはData Distillation(商標)装置の使用の概要を示しており、所与のデータセット(入力データセット1221)がData Distillation(商標)装置1203に送られ処理されて、無損失削減データセット(無損失削減データセット1224)が生成される。入力データセット1221は、ファイル、オブジェクト、ブロック、チャンク、またはデータストリームからの抽出の集まりで構成され得る。なお、図12Eは、データセットがファイルで構成される例を示す。図12Gの入力データセット1221は図12Eの入力ファイル1201に対応し、図12Gの無損失削減データセット1224は図12Eに示す4つのコンポーネント、すなわち、図12Eの蒸留ファイル1205、ツリーノードファイル1209、リーフノードファイル1210、およびPDEファイル1211を含む。図12Gでは、Data Distillation(商標)装置は、当該装置に提示される入力データセットの範囲全体にわたるデータエレメント同士の間の冗長を利用する。
Data Distillation(商標)装置は、入力データセットのサブセット全体にわたって冗長を利用し、当該装置に提示されるデータのサブセット毎に無損失削減を提供するように構成され得る。たとえば、図12Hに示すように、入力データセット1221は多数のより小さいデータの集まりにパーティション分割され得、各集まりは本開示において「ロット」または「データのロット」または「データロット」と称される。図12Hは、入力データロット1224を取込んで無損失削減データロット1225を生成するように構成されたData Distillation(商標)装置を示す。図12Hは、データロット1、…データロットi、…データロットnである多数のデータの集まりで構成される入力データセット1221を示す。このデータは一度に1データロットずつData Distillation(商標)装置に提示され、各データロットの範囲全体にわたって冗長が利用されて無損失削減データロットが生成される。たとえば、入力データセット1221からのデータロットi1226が装置に送られ、無損失削減データロットi1228が無損失削減データセット1227に供給される。入力データセット1221からの各データロットは装置に送られ、対応する無損失削減データロットが無損失削減データセット1227に供給される。データロット1、…データロットi…データロットnのすべてを消費して削減すると、入力データセット1221は無損失削減データセット1227に削減される。
Data Distillation(商標)装置は、設計によって、データのグローバルスコープ全体にわたって冗長を利用するのに既に効率的であるが、上記の技術を用いてデータ削減プロセスをさらに迅速化させ、その効率をさらに向上させてもよい。データ削減プロセスのスループットは、データロットのサイズをシステムの利用可能なメモリに収まることができるように制限することによって増加し得る。たとえば、サイズが多くのテラバイト、またはさらにはペタバイトである入力データセットを、各々のサイズがたとえば256GBである多数のデータロットに分割することができ、各データロットを迅速に削減することができる。256GBのメモリを有するシングルプロセッサコア(インテルXeon E5−1650 V3、Haswell 3.5Ghzプロセッサ)を用いて、256GBの範囲全体にわたって冗長を利用するそのようなソリューションが我々の研究所で実現され、さまざまなデータセットに対して2〜3倍の削減レベルを提供しつつ数百メガバイト/秒のデータの取込速度がもたらされた。なお、256GBの範囲は、Lempel Ziv法が現代のプロセッサに対して10MB/秒から200MB/秒の取込みパフォーマンスを提供するウインドウのサイズである32KBより何百万倍も大きい。ゆえに、冗長の範囲を適切に制限することによって、データ蒸留プロセスの速度の向上が、いくらかの削減を潜在的に犠牲にして達成され得る。
図12Iは図12Hのセットアップの変形を示しており、入力データセットのデータ削減(およびデータ再構成/取出し)のスループットを大きく高める複数のプロセッサ上で動作する複数のデータ蒸留プロセスを示す。図12Iは、x個のデータロットにパーティション分割された入力データセット1201を示しており、x個の独立したデータロットは、独立したプロセッサコア上で動作するj個の独立したプロセスに送り込まれ(各プロセスには、それに送り込まれるいずれかのデータロットを収容するのに十分なメモリが割当てられている)、並列に実行され、データ削減および再構成/取出しの両方について約j倍の迅速化をもたらす。図12Jは、使用モデルについてData Distillation(商標)装置によって生成される削減データのさまざまなコンポーネントを示しており、ここでは入力データセットの削減の後にマッパーをもはや保持しなくてもよい。そのような使用モデルの例として、ある種のデータバックアップおよびデータアーカイビングアプリケーションがある。そのような使用モデルでは、削減データの唯一のその後の使用は、削減データセットからの入力データセットの再構成および取出しである。そのようなシナリオでは、データ削減が完了した後にマッパーを記憶しないことによって、削減データのフットプリントをさらに削減することができる。図12Jは装置に送られる入力ファイル1201を示しており、当該装置は蒸留ファイル1205およびPDEファイル1211を生成し、これらコンポーネントはこのシナリオでは削減データを含む。なお、入力ファイル1201は、蒸留ファイル1205およびPDEファイル1211のみを用いて、完全に再生成および回復され得る。蒸留ファイル内のエレメント毎の無損失削減表現は、必要な場合は再構成プログラム、およびPDEファイル内の基本データエレメントの参照を含むことを思い起こされたい。PDEファイルと結合されると、これは再構成を実行するのに必要なすべての情報である。
なお、図12Jは、図1Aに従う蒸留データおよび基本データストアの組織に基づいてデータ蒸留装置によって作成されるさまざまなコンポーネントを示しており、再構成プログラムは蒸留ファイル内のエレメントの無損失削減表現に入れられる。なお、(図1Bに従う)いくつかの実施形態では、再構成プログラムを基本データストアに入れて、それらを基本データエレメントと同様に取扱うことができる。蒸留ファイル内のエレメントの無損失削減表現は、(再構成プログラム自体を含むのではなく)基本データストア内の再構成プログラムの参照を含む。これらの実施形態では、再構成プログラムは基本データエレメントと同様に取扱われてPDEファイル1211内に生成される。さらに別の実施形態では、図1Cに従って、再構成プログラムは、基本データエレメントとは別個に、再構成プログラムストアと称される構造に記憶される。そのような実施形態では、蒸留ファイル内のエレメントの無損失削減表現は、再構成プログラムストア内の再構成プログラムの参照を含む。そのような実施形態では、基本データエレメントのためのPDEファイルを生成することに加えて、装置は、RPファイルと称されるすべての再構成プログラムを含むファイルをさらに生成する。これは、使用モデルについての削減データのコンポーネントを示す図12Kに示されており、ここではマッパーをもはや保持しなくてもよい。図12Kは、蒸留ファイル1205、PDEファイル1211、およびRPファイル1221を含む削減されたデータコンポーネントを示す。
図12L〜図12Pは、本明細書に記載のいくつかの実施形態に従う、蒸留プロセスが超大型データセットを超高速の取込速度で収容できるようにどのように分散システム上にデプロイおよび実行され得るかを示す。
分散コンピューティングパラダイムは、複数のコンピュータ上で動作するプログラムによる大型データセットの分散処理を伴う。図12Lは、分散コンピューティングクラスタと称される組織内に互いにネットワーク化された多数のコンピュータを示す。図12Lはコンピュータ間のポイントツーポイントリンクを示しているが、図12Lに示すトポロジの代わりに、たとえばハブアンドスポークトポロジまたはメッシュトポロジなどの任意の通信トポロジを用いてもよいことが理解されるであろう。所与のクラスタにおいて、1つのノードが、タスクをスレーブノードに分散させてそれらの全体動作を制御および調整するマスターノードとして指名される。スレーブノードはマスターノードによって指示される通りにタスクを実行する。
データ蒸留プロセスは、分散コンピューティングクラスタの複数のノードにわたって分散して実行されて、クラスタ内の多数のコンピュータの全体的な計算、メモリ、および記憶容量を利用し得る。このセットアップでは、マスターノード上のマスター蒸留モジュールがスレーブノード上で動作するスレーブ蒸留モジュールと対話して、分散したデータ蒸留を達成する。この分散を容易にするために、装置の基本データシーブは、スレーブノード上で動作する複数のスレーブモジュールにわたって分散され得る複数の独立したサブセットまたはサブツリーにパーティション分割され得る。データ蒸留装置においては、基本データエレメントはそれらの名前に基づいてツリー形態に組織化されており、それらの名前はそれらのコンテンツから導出されることを思い起こされたい。基本データシーブは、基本データシーブ内のエレメントの名前の先頭バイトに基づいて複数の独立したサブセットまたは子シーブにパーティション分割され得る。ネームスペースを複数のサブツリーにわたってパーティション分割する複数の方法があり得る。たとえば、エレメントの名前の先頭バイトの値が多数の部分範囲にパーティション分割され、各部分範囲が子シーブに割当てられてもよい。クラスタ内のスレーブモジュールと同数のサブセットまたはパーティションが作成され得るため、独立した各パーティションは特定のスレーブモジュール上にデプロイされる。デプロイされた子シーブを用いて、各スレーブモジュールは自身が受信する候補エレメントに対してデータ蒸留プロセスを実行するように設計される。
図12Mは、4つのノード上で動作する4つのスレーブモジュール上にデプロイされることになるPDS_1,PDS_2,PDS_3およびPDS_4とラベル付けされた4つの基本データシーブまたは子シーブへの基本データシーブのサンプルパーティション分割を示す。パーティション分割は基本データエレメントの名前の先頭バイトに基づいている。示される例では、PDS_1内のすべてのエレメントの名前の先頭バイトはAからIの範囲内にあり、シーブPDS_1はそれに向かう値の範囲によってマーク付けされる名前A_Iを有する。同様に、PDS_2内のすべてのエレメントの名前の先頭バイトはJからOの範囲内にあり、子シーブPDS_2はそれに向かう値の範囲によってマーク付けされる名前J_Oを有する。同様に、PDS_3内のすべてのエレメントの名前の先頭バイトはPからSの範囲内にあり、子シーブPDS_3はそれに向かう値の範囲によってマーク付けされる名前P_Sを有する。最後に、PDS_4内のすべてのエレメントの名前の先頭バイトはTからZの範囲内にあり、子シーブPDS_4はそれに向かう値の範囲によってマーク付けされる名前T_Zを有する。
このセットアップでは、マスターノード上で動作するマスターモジュールは入力ファイルを受信し、入力ファイルの軽量パースおよび因子分解を行なって入力ファイルを候補エレメントのシーケンスに分割し、その後、各候補エレメントをさらなる処理のために好適なスレーブモジュールに導く。軽量パースは、スキーマに対して各候補エレメントをパースすることを含んでいてもよく、または候補エレメントに対してフィンガープリンティングを適用して、候補エレメントの名前の先頭バイトを構成する次元を求めることを含んでいてもよい。マスターにおけるパースは、どのスレーブモジュールが候補エレメントを受信すべきかを決定するのに必要な数のバイトのみを識別するように制限される。候補エレメントの名前の先頭バイト内の値に基づいて、候補は、この特定値に対応する子シーブを保持するスレーブノードにおけるスレーブモジュールに転送される。
データがシーブ内に蓄積するにつれて、パーティションは断続的に再検討および再バランシングされ得る。パーティション分割および再バランシング機能はマスターモジュールによって実行され得る。
候補エレメントを受信すると、各スレーブモジュールは、候補エレメントの完全なパースおよび調査によって候補エレメントの名前を作成することから始めて、データ蒸留プロセスを実行する。この名前を用いて、スレーブモジュールは子シーブのコンテンツ連想ルックアップを行ない、蒸留プロセスを実行して、候補エレメントをその子シーブに対する無損失削減表現のエレメントにコンバートする。蒸留ファイル内のエレメントの無損失削減表現は、スレーブモジュールと、それに対してエレメントが削減された対応する子シーブとを識別するためのSlaveNumberと称されるフィールドを用いて高められる。エレメントの無損失削減表現はマスターモジュールに送り返される。候補エレメントが子シーブ内に見つからない場合、または子シーブ内の基本データエレメントから導出できない場合、新規な基本データエレメントが子シーブ内に割当てられるように識別される。
マスターモジュールは入力ファイルからのすべての候補エレメントを適切なスレーブモジュールに導き続け、入力ファイルのためのすべてのエレメントを受信するまで、受信するエレメント記述を(無損失削減表現で)蓄積する。すべてのエレメントを受信した点で、グローバルコミット通信がすべてのスレーブモジュールに発行されて、それぞれの子シーブがそれらの個別の蒸留プロセスの結果で更新され得る。入力のための蒸留ファイルはマスターモジュールにおいて記憶される。
いくつかの実施形態では、任意のスレーブがその子シーブを新規な基本データエレメントまたはメタデータで更新できる前に蒸留ファイル全体が準備されるのを待つのではなく、子シーブの更新は候補エレメントがスレーブモジュールにおいて処理されると完了されてもよい。
いくつかの実施形態では、各子シーブは、図1Bおよび図1Cについての記述に従う基本データエレメントおよび再構成プログラムを含む。そのような実施形態では、再構成プログラムは子シーブに記憶され、無損失削減表現は、基本データエレメントおよび子シーブ内の再構成プログラム(必要な場合)の両方の参照を含む。これによって、エレメントのサイズ、およびしたがってマスターモジュールにおいて記憶される必要がある蒸留ファイルのサイズがさらに減少する。全体的な方法は、各ファイル内の各チャンクまたは候補エレメントのコンテンツに基づいて、すべてのスレーブノードの組合された記憶容量を活用してファイルをすべてのノードに分散させる。
データ取出しも同様にマスターモジュールによって調整される。マスターモジュールは蒸留ファイルを受信し、蒸留ファイル内のエレメント毎に無損失削減仕様を調べる。マスターモジュールは、どのスレーブモジュールがエレメントを再構成することになるかを示すフィールド「SlaveNumber」を抽出する。エレメントは次に再構成のために適切なスレーブモジュールに送られる。再構成エレメントは次にマスターモジュールに送り返される。マスターモジュールはすべてのスレーブからの再構成エレメントをアセンブルし、ファイルを要求している消費者に再構成ファイルを転送する。
図12Nは、データ蒸留装置がどのように分散システムにおいてデプロイおよび実行され得るかを示す。入力ファイル1251がマスターモジュールに送られ、マスターモジュールがファイル内の各候補エレメントの名前の先頭バイトをパースして識別する。マスターモジュールは候補エレメントを4つのスレーブモジュールの1つに導く。PDS_1を保持するスレーブノード1におけるスレーブモジュール1、またはAからIの範囲内の値を有する名前の先頭バイトを有する基本データエレメントを含む名前A_Iを有する子シーブは、名前A_Iを有する子シーブ内に既に存在しているエレメントの重複であると判断される名前BCD…を有する候補エレメント1252を受信する。スレーブモジュール1は、エレメントが基本であり、アドレスrefPDE1においてスレーブ1内に存在しているというインジケータを含む無損失削減表現1253を戻す。マスターは図12Nに示すようにすべての候補エレメントを関連のスレーブモジュールに送信し、蒸留ファイルをアセンブルして収集して最後に記憶する。
図12Oは図12Nに示すスキームの変形を示す。この変形では、蒸留ファイル内の各エレメントの無損失削減表現において、それに対してエレメントが削減された特定のChild_Sieveを識別するフィールドは、そのChild_Sieveが存在しているモジュールまたはノードの番号の代わりに、そのChild_Sieveの名前を含む。したがって、フィールドSlaveNumberはフィールドChild_Sieve_Nameで置換される。これには、関連のChild_Sieveを、Child_Sieveが存在しているモジュールまたは物理ノードの番号ではなくその仮想アドレスによって参照するという利点がある。ゆえに、図12Oに見ることができるように、PDS_1を保持するスレーブノード1におけるスレーブモジュール1、またはAからIの範囲内の値を有する名前の先頭バイトを有する基本データエレメントを含む名前A_Iを有する子シーブは、名前A_Iを有する子シーブ内に既に存在しているエレメントの重複であると判断される名前BCD…を有する候補エレメント1252を受信する。スレーブモジュール1は、エレメントが基本であり、アドレスrefPDE1において名前A_Iを有するChild_Sieve内に存在しているというインジケータを含む無損失削減表現1254を戻す。
なお、図12Lから図12Oに記載の構成を使用することによって、データ蒸留プロセスの全体的なスループット率を増加させることができる。マスターにおけるスループットはこうして、軽量パースおよびマスターモジュールからの候補エレメントのディスパッチによって制限されることになる。多数の候補エレメントについての蒸留は、それらのコンテンツがそれらを別個のスレーブモジュールに導く限り、並列に実行される。
全体的なスループットをさらに高めるために、軽量パース、およびどのChild_Sieveが候補エレメントを受信すべきかを識別するための入力ストリームの因子分解のタスクを並列化することができる。このタスクは、マスターモジュールによって、複数のスレーブノード上で動作するスレーブモジュールによって並列に実行される複数の同時タスクにパーティション分割され得る。これは、データストリーム内をルックアヘッドし、データストリームを複数の一部重複するセグメントにスライスすることによって達成され得る。これらのセグメントはマスターによってスレーブモジュールの各々に送信され、スレーブモジュールは軽量パースおよび因子分解を並列に行い、因子分解の結果をマスターに送り返す。マスターは、セグメントの各々の境界にわたる因子分解を解いた後、候補エレメントを適切なスレーブモジュールにルーティングする。
図12Lから図12Oは、データ蒸留装置がマスターノード上で動作する1つのマスター蒸留モジュールおよびスレーブノード上で動作する複数のスレーブ蒸留モジュールを用いて分散して動作する構成を説明した。マスターモジュールは、さまざまな子シーブにわたって基本データエレメントのパーティション分割を行なう役割を担っていた。示される構成では、取込むべきすべての入力ファイルがマスターモジュールによって取込まれ、無損失削減された蒸留ファイルがマスターモジュールに保持されていると同時に、すべての基本データエレメント(および任意の基本再構成プログラム)はさまざまなスレーブにおける子シーブ内に存在していた。ファイルのデータ取出し要求もマスターによって処理され、対応する蒸留ファイルの再構成はマスターによって調整されていた。図12Pは、入力ファイルがスレーブ蒸留モジュールのいずれか(およびそれらのモジュールに保持されている対応する蒸留ファイル)によって取込まれ得、データ取出し要求がスレーブ蒸留モジュールのいずれかによって処理され得る変形を示す。マスターモジュールは同じ態様で子シーブにわたって基本データエレメントのパーティション分割を行ない続けるので、子シーブにわたる基本データエレメントの分散は図12Lから図12Oに示す構成における分散と同じである。しかし、図12Pに示す新たな構成では、各スレーブモジュールはデータの取込みおよび取出しの両方が可能であるため、各スレーブモジュールはパーティション分割を認識している。さらに、すべてのモジュールは、それらのモジュールによってデータを取込んだ際にモジュールの各々において作成および記憶される蒸留ファイルの存在および場所を認識している。これによって、いずれかのスレーブモジュールは、システム全体に記憶されているファイルのいずれかのデータ取出し要求を満たすことができる。
図12Pに示すように、スレーブモジュールの各々は分散ストレージシステムからデータを取込んで取出すことができる。たとえば、スレーブ蒸留モジュール1 1270は入力ファイルI1271を取込み、軽量パースを行なって入力ファイルIを因子分解し、入力ファイルIからの各候補エレメントの名前に対応する子シーブを含むモジュールに候補エレメントをルーティングする。たとえば、入力ファイルIからの候補エレメント1275はスレーブ蒸留モジュール2 1279に送信される。同様に、スレーブ蒸留モジュール2 1279は入力ファイルIIを取込み、軽量パースを行なって入力ファイルIIを因子分解し、入力ファイルIIからの各候補エレメントの名前に対応する子シーブを含むモジュールに候補エレメントをルーティングする。たとえば、入力ファイルIIからの候補エレメント1277はスレーブ蒸留モジュール1 1270に送信される。スレーブ蒸留モジュールの各々は自身が受信する候補エレメントを処理し、それらの子シーブに対する蒸留プロセスを完了し、候補エレメントの無損失削減表現を、データを取込んだ開始モジュールに戻す。たとえば、スレーブ蒸留モジュール1 1270からの入力ファイルIから候補エレメント1275を受信したことに応答して、スレーブ蒸留モジュール2 1279は無損失削減エレメント1276をスレーブ蒸留モジュール1 1270に戻す。同様に、スレーブ蒸留モジュール2 1279からの入力ファイルIIから候補エレメント1277を受信したことに応答して、スレーブ蒸留モジュール1 1270は無損失削減エレメント1278をスレーブ蒸留モジュール2 1279に戻す。
この構成では、データの取出しは任意のスレーブモジュールにおいて満たされ得る。取出し要求を受信するモジュールは、まずその要求ファイルについての蒸留ファイルがどこに存在するかを判断し、対応するスレーブモジュールから蒸留ファイルをフェッチする必要がある。続いて、開始スレーブモジュールは、その蒸留ファイル内のさまざまなエレメントの分散再構成を調整して元のファイルをもたらし、要求しているアプリケーションにそれを供給する必要がある。
このように、データ蒸留プロセスは分散システムの複数のノードにわたって分散して実行されて、クラスタ内の多数のコンピュータの全体的な計算、メモリ、および記憶容量をより効果的に利用し得る。システム内のすべてのノードを利用してデータが取込まれて取出され得る。これによって、システム内のノードの組合された全記憶容量を最大限に活用しつつ超高速なデータ取込みおよび取出しが可能となるはずである。また、これによって、システム内の任意のノード上で動作するアプリケーションが、システム内のどこかに記憶されている任意のデータについてローカルノードにおいて問合せることができ、その問合せの答えを効率的にかつシームレスに得ることができる。
図12Mから図12Pに記載の構成では、システムのさまざまなノード内に存在している子シーブにわたるデータのパーティション分割は、入力ファイルを因子分解することによってエレメントが抽出される、グローバルに可視的なネームスペース内のエレメントの名前に基づいていた。代替の構成では、データロット、または一定のメタデータを共有するファイルのグループ全体が特定のノード上に割当てられて記憶され得る。ゆえに、全体のデータの一次パーティション分割はデータロットに基づいており、マスターによって行なわれて管理される。すべてのスレーブモジュールはデータロットのモジュールへの割当を認識し続けている。データロットは所与のスレーブノード上に完全に存在する。そのスレーブノード上で動作する蒸留スレーブモジュール上の子シーブは、このデータロットに属するすべての基本データエレメントを含む。換言すれば、所与のデータロットについてのすべての基本データエレメントのツリー全体が、1つのスレーブ蒸留モジュール内の1つの子シーブ上に完全に存在する。所与のデータロットについてのすべての蒸留ファイルも同じスレーブ蒸留モジュール上に存在する。この構成を用いて、入力ファイルを依然としてスレーブ蒸留モジュールのいずれかによって取込むことができ、データ取出し要求を依然としてスレーブ蒸留モジュールのいずれによって処理することができる。しかし、所与のデータロットについてのデータ蒸留プロセス全体が、そのデータロットを含むモジュール上で完全に実行される。データ取込みおよびデータ取出しの要求は、開始モジュールから、特定のデータロットを保持するように指定されている特定のスレーブモジュールにルーティングされる。このソリューションには、データロットを因子分解して蒸留する際に分散環境における通信オーバーヘッドが減少するという利点がある。冗長はグローバルデータフットプリント全体にわたって利用されなくなり、局所的にデータロット内で非常に効率的に利用される。このソリューションは依然として分散システムの組合された記憶容量を用いており、システムの任意のノードからの任意のデータに問合せ、当該データを取込み、当該データを取出すシームレスな能力を提供する。
ゆえに、上述の多数の技術を使用して、分散システムにおいてリソースを効率的に用いて、超大型データセットに対して超高速でデータ蒸留が行なわれる。
本明細書に記載の実施形態を用いてさまざまな実世界データベースに対してデータ削減を行い、これら実施形態の有効性を判定した。検討した実世界データベースとして、企業電子メールのエンロンコーパス、さまざまな米国政府記録および文書、MongoDB NOSQLデータベースに入力された米国運輸省記録、ならびに公衆が利用可能な企業のパワーポイントプレゼンテーションがある。本明細書に記載の実施形態を用いて、入力データを平均で4KBの可変サイズのエレメント(フィンガープリンティングによって境界が決まる)に因子分解すると、これらデータベース全体にわたって3.23倍の平均データ削減が達成された。3.23倍の削減は、削減データのサイズが3.23倍で割った元のデータのサイズと等しいことを意味しており、これによって31%の圧縮率の削減フットプリントがもたらされる。旧来のデータ重複排除技術は、同等のパラメータを用いてこれらデータセットに対して1.487倍のデータ削減を提供することがわかった。本明細書に記載の実施形態を用いて、入力データを4KBの固定サイズのエレメントに因子分解すると、これらデータセット全体にわたって1.86倍の平均データ削減が達成された。旧来のデータ重複排除技術は、同等のパラメータを用いてこれらデータセットに対して1.08倍のデータ削減を提供することがわかった。したがって、Data Distillation(商標)ソリューションは、旧来のデータ重複排除ソリューションよりもはるかに良好なデータ削減を提供することがわかった。
また、テストランでは、基本データエレメントのバイトの小さいサブセットがシーブ内のエレメントの大半を順序付けることによって、その演算のための最小の増分ストレージで済むソリューションを可能にすることが確認された。
これらの結果によって、Data Distillation(商標)装置は、エレメント自体よりも細かく、データセット全体にわたってグローバルにデータエレメント同士の間の冗長を利用することを効率的に可能にすることが確認された。この方法によって提供される無損失データ削減は、無駄のないデータアクセスおよびIOで、それら自体が最小の増分ストレージで済むデータ構造を使用して、かつ、現代のマルチコアマイクロプロセッサ上で利用可能な全計算処理能力のごく一部を用いて達成される。前節に記載の実施形態は、高速のデータ取込みおよびデータ取出しを提供しつつ、大型および超大型データセットに対する無損失データ削減を実行する、かつ従来の技術の欠点および制限を受けないシステムおよび技術を特徴とする。
コンテンツ連想シーブ内に存在している基本データエレメントからデータを導出することによる無損失削減されたデータに対するコンテンツ連想検索および取出しの実行
上記本文に記載されて図1Aから図12Lに示されたデータ蒸留装置は、無損失削減フォーマットで記憶されているデータからの情報に対する検索、および当該情報のコンテンツ連想的な取出しを効率的に行なうために一定の特徴を用いて改良され得る。そのような多次元検索およびデータ取出しは、アナリティクスまたはデータウェアハウジングアプリケーションの重要なビルディングブロックである。次にこれらの改良を説明する。
図13は、図3Hに示した構造と同様のリーフノードデータ構造を示す。しかし、図13では、基本データエレメント毎のリーフノードデータ構造内のエントリが、その特定の基本データエレメントの参照を含む蒸留データ内のすべてのエレメントの参照(逆方向参照または逆方向リンクとも称される)を含むように改良されている。データ蒸留スキームは入力ファイルからのデータをエレメントのシーケンスに因子分解して、これらが図1Hに記載のような仕様を用いて削減フォーマットで蒸留ファイルに入れられることを思い起こされたい。蒸留ファイル内には、基本データエレメントおよび導出エレメントの2種類のエレメントがある。蒸留ファイル内のこれらのエレメントの各々の仕様は、基本データストア内に存在している基本データエレメントの参照を含む。これらの参照(蒸留ファイル内のエレメントから基本データストア内の基本データエレメントまで)の各々について、リーフノードデータ構造にインストールされた対応する逆方向リンクまたは逆方向参照(リーフノードデータ構造内の基本データエレメントについてのエントリから蒸留ファイル内のエレメントまで)が存在することになる。逆方向参照は、エレメントの無損失削減表現の開始をマーク付けする蒸留ファイル内のオフセットを判断する。いくつかの実施形態では、逆方向参照は、蒸留ファイルの名前と、エレメントの開始の位置を特定するそのファイル内のオフセットとを含む。図13に示すように、蒸留ファイル内の各エレメントの逆方向参照とともに、リーフノードデータ構造はさらに、蒸留ファイル内の参照されているエレメントが基本データエレメント(prime)であるか否か、またはそれが導出エレメント(deriv)であるか否かを識別するインジケータを維持する。蒸留プロセス時、エレメントが蒸留ファイル内に入れられた場合は、逆方向リンクがリーフノードデータ構造にインストールされる。
逆方向参照または逆方向リンクは、基本データシーブを共有するすべての蒸留ファイル内のすべてのエレメントに到達可能なユニバーサルハンドルとして設計される。
データエレメントサイズは、各参照がデータエレメントのサイズのごく一部であるように選択されると予想されるため、逆方向参照を追加しても、達成されるデータ削減には大きく影響しないと予想される。たとえば、(マルチ導出エレメントが許可されないように)導出エレメントの各々が1つ以下の基本データエレメントから導出されるように制約されるシステムを考えてみる。すべてのリーフノードデータ構造にわたる逆方向参照の総数は、すべての蒸留ファイルにわたるエレメントの総数と等しくなる。32GBのサイズのサンプル入力データセットが8GBの無損失削減データに削減され、1KBの平均エレメントサイズを使用し、4倍の削減率をもたらすと仮定してみる。入力データ内には32M個のエレメントが存在する。各逆方向参照のサイズが8Bである場合、逆方向参照が占める全空間は256MB、または0.25GBである。これは、8GBのフットプリントの削減データに対して小さい増加である。新たなフットプリントは8.25GBとなり、達成される効果的な削減は3.88倍となり、これは3%の削減の損失を表わす。これは、削減データに対する強力なコンテンツ連想データ取出しの利点のために支払わなくてはならない小さな代償である。
本文書において先に述べたように、蒸留装置は、候補エレメントのコンテンツ内の骨格データ構造のさまざまなコンポーネントの場所を判定するさまざまな方法を使用することができる。エレメントの骨格データ構造のさまざまなコンポーネントを次元と見なすことができるため、これらの次元同士の連結、およびそれに続く各エレメントの残りのコンテンツを用いて、各エレメントの名前が作成される。名前を用いて基本データエレメントが順序付けられてツリーに組織化される。
入力データの構造がわかっている使用モデルでは、スキーマがさまざまなフィールドまたは次元を規定する。そのようなスキーマは、このコンテンツ連想データ取出し装置を使用しているアナリティクスアプリケーションによって供給され、アプリケーションへのインターフェイスを介して装置に提供される。スキーマ内の宣言に基づいて、蒸留装置のパーサは候補エレメントのコンテンツをパースしてさまざまな次元を検出して位置を特定し、候補エレメントの名前を作成することができる。上述のように、次元に対応するフィールド内に同じコンテンツを有するエレメントは、ツリーの同一のレッグに沿って互いにグループ分けされる。シーブにインストールされた基本データエレメント毎に、次元についての情報がメタデータとして、リーフノードデータ構造内のその基本データエレメントについてのエントリに記憶され得る。この情報は、宣言された次元の各々におけるコンテンツの場所、サイズ、および値を含み得、図13において「基本データエレメントについての他のメタデータ」と称されるフィールドに記憶され得る。
図14Aは、本明細書に記載のいくつかの実施形態に従う、入力データセットの構造の記述、ならびに入力データセットの構造と次元との対応関係の記述を提供するサンプルスキーマを示す。構造記述1402は、入力データの完全な構造を記述するより完全なスキーマの抜粋または一部である。構造記述1402はキーワードのリスティング(たとえば「PROD_ID」、「MFG」、「MONTH」、「CUS_LOC」、「CATEGORY」、および「PRICE」)を含み、キーワードに対応する値のタイプがその後に続く。コロン記号「:」はキーワードを値のタイプと分けるデリミタとして用いられ、セミコロン記号「;」は別個の対のキーワードを対応する値のタイプと分けるデリミタとして用いられる。なお、(構造1402がその一部である)完全なスキーマは、各入力の開始および終了を識別する付加的なフィールドと、場合によってはさらに次元の外部の他のフィールドとを指定し得る。次元マッピング記述1404は、基本データエレメントを組織化するために用いられる次元が構造化入力データセット内のキーワード値にどのようにマップするかを記述している。たとえば、次元マッピング記述1404内の一行目は、入力データセット内のキーワード「MFG」に対応する値の最初の4バイト(一行目はテキスト「prefix=4」で終わるため)を用いて次元1が作成されることを指定している。次元マッピング記述1404内の残りの行は、構造化入力データに基づいて他の3つの次元をどのように作成するかを記述している。この次元へのキーワードのマッピングにおいて、入力内に現われるキーワードの順序は次元の順序と必ずしも一致しない。提供されるスキーマ記述を用いて、パーサは入力データ内のこれらの次元を認識して候補エレメントの名前を作成することができる。たとえば図14Aでは、次元マッピング記述1404を用いて、候補エレメントの名前は以下のように作成される。(1)名前の最初の4バイトは、次元1と宣言されるキーワード「MFG」に対応する値からの最初の4バイトであり、(2)名前の次の4バイトは、次元2と宣言されるキーワード「CATEGORY」に対応する値からの最初の4バイトであり、(3)名前の次の3バイトは、次元3と宣言されるキーワード「CUS_LOC」に対応する値からの最初の3バイトであり、(4)名前の次の3バイトは、次元4と宣言されるキーワード「MONTH」に対応する値からの最初の3バイトであり、(5)名前の次のバイトセットは次元からの残りのバイトの連結で構成され、(6)最後に、次元のすべてのバイトを使い果たした後、名前の残りのバイトは候補エレメントの残りのバイトの連結から作成される。
この装置を駆動するアプリケーションによって供給されるスキーマは、第1の次元の数および第2の次元の数を指定し得る。これら第1および第2の次元のすべてについての情報は、リーフノードデータ構造内のメタデータ内に保持され得る。第1の次元を用いて主軸が形成され、これに沿ってエレメントがシーブ内にソートされて組織化される。第1の次元が使い果たされ、大きいメンバーシップを有するサブツリーが依然として残っている場合は、ツリーのさらに深部で第2の次元も用いて、エレメントがより小さいグループに細分割され得る。第2の次元についての情報はメタデータとして保持され、リーフノード内のエレメント同士を区別するための二次基準としても用いられ得る。コンテンツ連想的な多次元検索および取出しを提供するいくつかの実施形態では、すべての受信データはスキーマが宣言する次元毎にキーワードおよび有効値を含んでいなければならないという要件が課され得る。これによって、システムには、有効データのみがシーブ内の所望のサブツリーに入ることを保証する方法が与えられる。次元と指定されたすべてのフィールドを含んでいない、または次元についてのフィールドに対応する値内に無効値を含んでいる候補エレメントは、先に図3Eに示したように異なるサブツリーの下方に送られる。
データ蒸留装置は、次元内のコンテンツに基づくデータのコンテンツ連想検索および取出しを包括的にサポートするために、1つの付加的な方法で制約される。導出エレメントが基本データエレメントから作成されると、導出部は、基本データエレメントおよび導出物の両方が、対応する次元の各々についての値内に全く同じコンテンツを有することを保証するように制約される。ゆえに、導出物が作成されている間、再構成プログラムは、導出エレメントを構築するために、基本データエレメントの次元のいずれかに対応するフィールド内のコンテンツにゆらぎを起こさせることまたはコンテンツを変更することが許可されない。候補エレメントを前提として、シーブのルックアップ時、候補エレメントがターゲット基本データエレメントの対応する次元と比べていずれかの次元に異なるコンテンツを有する場合、導出物を受付ける代わりに新規な基本データエレメントをインストールする必要がある。たとえば、候補エレメントがリーフノードに到着して、第1の次元のサブセット内に同じコンテンツを有するが、残りの第1の次元または第2の次元内に異なるコンテンツを有する基本データエレメントを見つけるように、この第1の次元のサブセットがツリー内の別個のグループにエレメントを十分にソートした場合は、導出物を作成する代わりに、新規な基本データエレメントをインストールする必要がある。この特徴によって、単に基本データストアに問合せるだけで、次元を用いてすべてのデータを検索できることが保証される。
上述の制限は、ほとんどの使用モデルについてデータ削減の程度を大幅に妨げないと予想される。たとえば、入力データが、各々が1000バイトのサイズのデータウェアハウストランザクションである一組のエレメントで構成されている場合、かつ、一組の6個の第1の次元および14個の第2の次元が、各々がたとえば次元毎に8バイトのデータを有するスキーマによって指定されている場合、次元においてコンテンツが占める全バイトは160バイトである。導出物を作成する際にこれら160バイトに対するゆらぎは許可されない。これによって、残りの840バイトの候補エレメントデータが依然として導出物を作成するためのゆらぎに利用可能であり続けるため、冗長を利用するのに十分な機会が残されており、同時に、データウェアハウスからのデータを次元を用いてコンテンツ連想的に検索して取出すことができる。
次元内のフィールドについての特定値を含むデータの検索クエリを実行するために、装置はツリーをトラバースして、指定された次元と一致するツリー内のノードに到達することができ、そのノードよりも下方のすべてのリーフノードデータ構造はルックアップの結果として戻され得る。リーフノードに存在している基本データエレメントの参照を用いて、必要であれば所望の基本データエレメントをフェッチすることができる。逆方向リンクによって、所望であれば、蒸留ファイルからの(無損失削減フォーマットの)入力エレメントの取出しが可能になる。その後、エレメントが再構成されて元の入力データがもたらされ得る。ゆえに、改良された装置によって、(全データの小さいサブセットである)基本データストア内のデータに対してすべての検索を行なうことができ、なおかつ、必要に応じてすべての導出エレメントに到達してそれらを取出すことができる。
改良された装置を用いて、強力な検索のための検索およびルックアップクエリ、ならびにクエリによって指定された次元内のコンテンツに基づく関連のデータのサブセットの取出しを実行することができる。コンテンツ連想データ取出しクエリは、「フェッチ(次元1、次元1の値;次元2、次元2の値;…)の形態を有する。クエリは、検索に伴う次元と、コンテンツ連想検索およびルックアップのための指定次元の各々に用いられる値とを指定する。クエリはすべての次元を指定してもよく、または次元のサブセットのみを指定してもよい。クエリは、複数の次元に基づく複合条件を検索および取出しの基準として指定してもよい。指定次元の指定値を有するシーブ内のすべてのデータが取出される。
さまざまなフェッチクエリがサポートされ、このコンテンツ連想データ取出し装置を使用しているアナリティクスアプリケーションが当該クエリを利用することができる。そのようなクエリは、インターフェイスを介してアプリケーションから装置に供給される。インターフェイスはアプリケーションから装置にクエリを与え、装置からアプリケーションにクエリの結果を戻す。まず、クエリFetchRefsを用いて、当該クエリと一致する基本データエレメント毎に図13のリーフノードデータ構造の参照またはハンドルが(エントリの子IDまたは索引とともに)フェッチされ得る。第2の形態のクエリFetchMetaDataを用いて、当該クエリと一致する基本データエレメント毎に図13のリーフノードデータ構造内のエントリからメタデータ(骨格データ構造、次元についての情報、および基本データエレメントの参照を含む)がフェッチされ得る。第3の形態のクエリFetchPDEsは、検索基準と一致するすべての基本データエレメントをフェッチする。別の形態のクエリFetchDistilledElementsは、検索基準と一致する蒸留ファイル内のすべてのエレメントをフェッチする。さらに別の形態のクエリFetchElementsは、検索基準と一致する入力データ内のすべてのエレメントをフェッチする。なお、FetchElementsクエリについては、装置はまず蒸留エレメントをフェッチし、次に関連の蒸留エレメントを入力データからのエレメントに再構成してこれらをクエリの結果として戻す。
そのような多次元コンテンツ連想フェッチプリミティブに加えて、インターフェイスはさらに、(基本データエレメントの参照を用いて)基本データエレメントに、かつ(エレメントの逆方向参照を用いて)蒸留ファイル内のエレメントに直接アクセスする能力をアプリケーションに提供し得る。さらに、インターフェイスは、(蒸留エレメントの参照を与えられて)蒸留ファイル内の蒸留エレメントを再構成して当該エレメントを入力データ内に存在していたように供給する能力をアプリケーションに提供し得る。
これらのクエリの適切な組合せがアナリティクスアプリケーションによって用いられて、検索が行なわれ、関連の和集合および共通集合が求められ、重要な洞察が収集され得る。
以下に説明する図14Bは、構造記述1402内に記述された構造を有する入力データセットの例を示す。この例では、ファイル1405に含まれている入力データはeコマーストランザクションを含む。入力データは、図14Aのスキーマおよび次元宣言を用いて、データ蒸留装置内のパーサによって一連の候補エレメント1406にコンバートされる。なお、各候補エレメントの名前の先頭バイトは次元からのコンテンツで構成されている。たとえば、候補エレメント1についての名前1407の先頭バイトはPRINRACQNYCFEBである。これらの名前を用いて候補エレメントがツリー形態に組織化される。データ削減の完了後、蒸留データは蒸留ファイル1408に入れられる。
以下に説明する図14Cは、どのように次元マッピング記述1404を用いて構造記述1402に従って図14Aに示す入力データセットをパースし、次元マッピング記述1404に従って次元を求め、求めた次元に基づいて基本データエレメントをツリーに組織化することがきるかを示す。図14Cでは、基本データエレメントは4つの次元から取られた合計14文字を用いてマスターツリーに組織化されている。マスターツリー内には、さまざまな基本データエレメントについてのリーフノードデータ構造の一部が示されている。なお、見やすくするために、図13の完全なリーフノードデータ構造は示されていない。しかし、図14Cは、リーフノードデータ構造内の各エントリのパス情報または名前と、子IDと、蒸留ファイル内のエレメントが「prime」(Pで示す)であるか「deriv」(Dで示す)であるかのインジケータとともに、基本データエレメントから蒸留ファイル内のエレメントまでのすべての逆方向参照または逆方向リンクと、さらに基本データエレメントの参照とを示す。図14Cは、マスターツリー内の5個の基本データエレメントにマップされる蒸留ファイル内の7個のエレメントを示す。図14Cでは、名前PRINRACQNYCFEBを有する基本データエレメントについての逆方向リンクAは蒸留ファイル内のエレメント1を再び参照する。一方、名前NIKESHOELAHJUNを有する基本データエレメントはエレメント2、エレメント3、およびエレメント58への逆方向リンクB,CおよびEをそれぞれ有する。なお、エレメント3およびエレメント58はエレメント2の導出物である。
図14Dは、検索の効率を向上させるために次元から作成される補助索引または補助ツリーを示す。この例では、作成される補助マッピングツリーは(CATEGORYである)次元2に基づいている。この補助ツリーを直接トラバースすることによって、入力データ内の所与のCATEGORYのすべてのエレメントを、別の方法では引起される可能性があるマスターツリーのより高額なトラバースなしで見つけることができる。たとえば、「SHOE」で示されているレッグの下方へのトラバースによって、ADIDSHOESJCSEPおよびNIKESHOELAHJUNであるshoesについての2つの基本データエレメントが直接得られる。
あるいは、そのような補助ツリーは第2の次元に基づいており、当該次元を用いる検索の迅速な集束に役立つように用いられてもよい。
次に、図14Dに示す装置上で実行されるクエリの例を提供する。クエリFetchPDEs(次元1、NIKE;)は、NIKESHOELAHJUNおよびNIKEJERSLAHOCTと名付けられた2つの基本データエレメントを戻す。クエリFetchDistilledElements(次元1、NIKE;)は、無損失削減フォーマットの蒸留エレメントとなるエレメント2、エレメント3、エレメント58およびエレメント59を戻す。クエリFetchElements(次元1、NIKE;次元2、SHOE)は、入力データファイル1405からトランザクション2、トランザクション3およびトランザクション58を戻す。クエリFetchMetaData(次元2、SHOES)は、ADIDSHOESJCSEPおよびNIKESHOELAHJUNと名付けられた2つの基本データエレメントの各々についてリーフノードデータ構造エントリに記憶されたメタデータを戻す。
ここまで説明した装置を用いて、次元と称されるフィールド内に指定されているコンテンツに基づく検索をサポートすることができる。また、当該装置を用いて、次元のリスティングに含まれていないキーワードのリスティングに基づく検索をサポートすることができる。そのようなキーワードは、装置を駆動している検索エンジンなどのアプリケーションによって装置に提供され得る。キーワードはスキーマ宣言によって装置に指定されてもよく、またはすべてのキーワードを含むキーワードリストを介して渡されてもよく、各キーワードは宣言分離記号(スペース、またはコンマ、または改行など)によって分離されている。あるいは、スキーマおよびキーワードリストの両方を用いてすべてのキーワードを包括的に指定してもよい。非常に多くのキーワードを指定してもよく、装置はキーワードの数に制限を課さない。これらの検索キーワードをキーワードと称する。装置は、これらのキーワードを用いて検索の逆索引を維持し得る。逆索引は、キーワード毎に、このキーワードを含む蒸留ファイル内のエレメントの逆方向参照のリスティングを含む。
スキーマ内のキーワード宣言またはキーワードリストに基づいて、蒸留装置のパーサは候補エレメントのコンテンツをパースして、受信する候補エレメント内のさまざまなキーワードを(見つけた場合は、見つけた場所に)検出して位置を特定することができる。その後、候補エレメントはデータ蒸留装置によって基本データエレメントまたは導出エレメントにコンバートされ、エレメントとして蒸留ファイルに入れられる。このエレメント内に見つかったキーワードについての逆索引は、蒸留ファイル内のこのエレメントの逆方向参照で更新され得る。エレメント内に見つかったキーワード毎に、逆索引は蒸留ファイル内にこのエレメントの逆方向参照を含むように更新される。蒸留ファイル内のエレメントは無損失削減表現であることを思い起こされたい。
キーワードを用いてデータの検索クエリを実行すると、逆索引を調べて、このキーワードを含む蒸留ファイル内のエレメントの逆方向参照を見つけて抽出する。そのようなエレメントの逆方向参照を用いて、エレメントの無損失削減表現を取出すことができ、エレメントを再構成することができる。そして、再構成エレメントを検索クエリの結果として提供することができる。
逆索引は、再構成エレメント内のキーワードのオフセットの位置を特定する情報を含むように改良され得る。なお、候補エレメント内に検出された各キーワードのオフセットまたは場所はパーサによって求められ得るため、この情報も、蒸留ファイル内のエレメントの逆方向参照が逆索引に入れられると逆索引内に記録され得る。検索クエリを実行すると、逆索引を調べて関連のキーワードを含む蒸留ファイル内のエレメントの逆方向参照が取出された後、かつエレメントが再構成された後、(元の入力候補エレメントと同じ)再構成エレメント内のキーワードの記録されたオフセットまたは場所を用いて、キーワードが存在している入力データ内の正確な位置を特定することができる。
図15は、キーワードに基づく検索を容易にする逆索引を示す。キーワード毎に、逆索引は値の対を含み、第1はキーワードを含む蒸留ファイル内の無損失削減エレメントの逆参照であり、第2の値は再構成エレメント内のキーワードのオフセットである。
次元とキーワードとの相違を指摘しておくことが重要である。なお、次元は主軸として用いられ、これに沿って基本データエレメントをシーブ内に組織化する。次元は、データ内の各エレメントの骨格データ構造を形成する。次元は、受信データの構造の知識に基づいて宣言される。導出部は、作成される任意の導出エレメントが、対応する次元の各々についてのフィールドの値内に基本データエレメントと全く同じコンテンツを有さなければならないように制約される。キーワードについては、これらの特性は成り立たない。そもそもキーワードがデータ内に存在するという先験的要件がなく、基本データストアはキーワードに基づいて組織化されなくてもよく、導出部はキーワードを含むコンテンツを伴う導出に関して制約もされない。導出部は、必要であればキーワードの値を変更することによって基本データエレメントから導出物を自由に作成することができる。キーワードは単純に入力データのスキャン時に見つかった場所に記録され、逆索引が更新されるので、キーワードは、キーワードに基づくコンテンツ連想検索を実行すると位置が特定され得る。
当該装置は、キーワードのリスティングの更新を可能にし得る。キーワードは、無損失削減形態で記憶されているデータを全く変更せずに追加され得る。新たなキーワードが追加されると、新規な受信データが、更新されたキーワードリストに対してパースされ得、受信データで更新された逆索引はその後無損失削減形態で記憶される。既存のデータ(無損失削減形態で既に記憶されている)を新たなキーワードに対して索引付けする必要がある場合、装置は蒸留ファイル内(一度に1つ以上の蒸留ファイル、または一度に1つの無損失削減データロット)を漸進的に読込み、元のファイルを再構成し(しかし無損失削減された記憶データを乱すことなく)、再構成ファイルをパースして逆索引を更新し得る。この間ずっと、データレポジトリ全体が無損失削減形態で記憶され続け得る。
図16Aは、図14Aに示したスキーマの変形であるスキーマ宣言を示す。図16Aのスキーマは、第2の次元1609の宣言およびキーワードのリスティング1610を含む。図16Bは、宣言された第1の次元に基づく名前を有する一組の候補エレメントにパースされてコンバートされる構造記述1602内に記述された構造を有する入力データセット1611の例を示す。候補エレメントは蒸留ファイル1613内のエレメントにコンバートされる。第2の次元「PROD_ID」の宣言は、候補エレメント58が基本データエレメント「NIKESHOELAHJUN with PROD_ID=348」から導出され得ず、したがって、1つの付加的な基本データエレメント「NIKESHOELAHJUN with PROD_ID=349」が基本データストア内に作成されるように、導出部に対して制約を課す。入力データセットは図14Bに示したものと同一であるが、蒸留の結果は7個の蒸留エレメント、しかし6個の基本データエレメントをもたらすものである。図16Cは、蒸留プロセスの結果として作成された蒸留ファイル、マスターツリー、および基本データエレメントを示す。
図16Dは、第2の次元「PROD_ID」について作成された補助ツリーを示す。特定のPROD_ID値を有するこのツリーをトラバースすると、その特定のPROD_IDを有する基本データエレメントが得られる。たとえば、PROD_ID=251を有する基本データエレメントを求めるクエリFetchPDEs(次元5,251)、またはあるいはクエリFetchPDEs(PROD_ID,251)は、基本データエレメントWILSBALLLAHNOVをもたらす。
図16Eは、図16Aの構造1610内に宣言された3つのキーワードについて作成された逆索引(キーワードについての逆索引1631とラベル付けされている)を示す。これらのキーワードはFEDERER、LAVERおよびSHARAPOVAである。逆索引は、入力データセット1611をパースして消費した後に更新される。クエリFetchDistilledElements(キーワードFederer)は(マスターツリーまたは補助ツリーではなく)逆索引を利用してエレメント2、エレメント3およびエレメント58を戻す。
図17は、コンテンツ連想データ取出しのために改良された全体的な装置のブロック図を示す。コンテンツ連想データ取出しエンジン1701は、データ蒸留装置にスキーマ1704、またはデータの次元を含む構造定義を与える。エンジン1701はさらに、装置にキーワードリスト1705を与える。エンジン1701は、蒸留装置からのデータの検索および取出しのためのクエリ1702を発行し、クエリの結果を結果1703として受信する。導出部110は、導出物を作成する際に次元の宣言を認識して次元の場所におけるコンテンツの変更を禁止するように改良されている。なお、リーフノードデータ構造内のエントリから蒸留ファイル内のエレメントまでの逆方向参照は基本データシーブ106内のリーフノードデータ構造に記憶される。同様に、補助索引も基本データシーブ106に記憶される。エレメントが蒸留データに書込まれている間に導出部110によって逆方向参照1709で更新される逆索引1707も示されている。このコンテンツ連想データ取出しエンジンは他のアプリケーション(アナリティクス、データウェアハウジング、およびデータ分析アプリケーションなど)と対話して、実行したクエリの結果をそれらに提供する。
要約すると、改良されたデータ蒸留装置によって、無損失削減形態で記憶されているデータに対する強力な多次元コンテンツ連想検索および取出しが可能となる。
Data Distillation(商標)装置を音声および映像データを無損失削減するために使用することができる。本方法によって達成されるデータ削減は、コンテンツ連想シーブ内に存在している基本データエレメントから音声および映像データのコンポーネントを導出することによって達成される。そのような目的のための本方法の適用を次に説明する。
図18A〜図18Bは、MPEG1、Layer3規格(MP3とも称される)に従って音声データを圧縮および復号するためのエンコーダおよびデコーダのブロック図を示す。MP3は、有損失および無損失データ削減技術の組合せを用いて入力音声を圧縮するデジタル音声用の音声符号化フォーマットである。MP3は、コンパクトディスク(CD)音声を1.4Mbpsから128Kbpsに圧縮する。MP3は人間の耳の限界を利用して、大抵の人の耳には聞こえない音声のコンポーネントを抑制する。これを達成するために、知覚符号化技術と総称される一連の技術が用いられる。当該技術は、音声データのスニペットのサイズを損失はあるが知覚不可能なように減少させる。知覚符号化技術は有損失であり、これらのステップ時に失われた情報を取戻すことはできない。これらの知覚符号化技術は、本文書において先に説明した無損失データ削減技術であるハフマン符号化によって補足される。
MP3では、入力音声ストリームがいくつかの小さいデータフレームのシーケンスに圧縮され、各データフレームがフレームヘッダおよび圧縮音声データを含んでいる。元の音声ストリームは周期的にサンプリングされて、音声のスニペットのシーケンスを生成する。これが次に知覚符号化およびハフマン符号化を用いて圧縮されて、MP3データフレームのシーケンスを生成する。知覚符号化技術およびハフマン符号化技術の双方が、音声データの各スニペット内で局所的に適用される。ハフマン符号化技術は、冗長を音声のスニペット内で局所的に利用するが、音声ストリームにわたって全体的には利用しない。ゆえに、MP3技術は、冗長を全体的には、すなわち単一の音声ストリームにわたっても、複数の音声ストリーム同士の間でも、利用しない。これは、MP3が達成可能なレベルを超えるさらなるデータ削減の機会を提供する。
各MP3データフレームは26msの音声スニペットを表わす。各フレームは1152個のサンプルを記憶しており、各々が576個のサンプルを含む2つのグラニュールに細分される。図18Aのエンコーダブロック図に見ることができるように、デジタル音声信号の符号化の際、フィルタリングの処理を通じて、かつ修正離散コサイン変換(MDCT)の適用によって、時間領域サンプルが取られて576個の周波数領域サンプルに変換される。知覚符号化技術を適用して、サンプルに含まれている情報の量を減少させる。知覚符号化の出力は、周波数ラインごとに減少した情報を含む、非一様量子化グラニュール1810である。次にハフマン符号化を用いてグラニュールのサイズをさらに減少させる。各グラニュールの576本の周波数ラインは、それらの符号化のために複数のハフマンテーブルを用い得る。ハフマン符号化の出力は、スケールファクタ、ハフマン符号化ビット、および補助データを含むフレームの主要なデータコンポーネントである。サイド情報(さまざまなフィールドを特徴付けて位置を特定するために用いられる)がMP3ヘッダに入れられる。符号化の出力は、MP3符号化音声信号である。128Kbpsのビットレートでは、MP3フレームのサイズは417または418バイトである。
図18Cは、図1Aに最初に示したデータ蒸留装置がどのように改良されてMP3データに対してデータ削減を実行し得るかを示す。図18Cに示す方法は、MP3データを候補エレメントに因子分解し、エレメント間の冗長をエレメント自体よりも細かい粒度で利用する。MP3データについては、グラニュールがエレメントとして選択される。一実施形態では、(図18Aに示すような)非一様量子化グラニュール1810はエレメントとして取扱われ得る。別の実施形態では、エレメントは、量子化周波数ライン1854とスケールファクタ1855との連結で構成され得る。
図18Cでは、MP3符号化データのストリーム1862がデータ蒸留装置1863によって受信されて蒸留MP3データのストリーム1868に削減されて、無損失削減形態で記憶される。MP3符号化データの入力ストリーム1862は、MP3ヘッダおよびMP3データの対のシーケンスで構成される。MP3データは、CRC、サイド情報、主データおよび補助データを含む。装置によって作成された出力する蒸留MP3データは、同様の対のシーケンス(各対は蒸留MP3ヘッダであり、その後に無損失削減形態のエレメント仕様が続く)で構成される。蒸留MP3ヘッダは主データ以外の元のフレームのすべてのコンポーネントを含み、すなわち、MP3ヘッダ、CRC、サイド情報、および補助データを含む。この蒸留MP3データ内のエレメントフィールドは、無損失削減形態で指定されるグラニュールを含む。パーサ/因子分解部1864が、入力するMP3符号化ストリームの第1の復号化を実行して(ハフマン復号化の実行を含む)、(図18Bに示す)量子化周波数ライン1851およびスケールファクタ1852を抽出し、かつ音声グラニュール1865を候補エレメントとして生成する。パーサ/因子分解部が実行する第1の復号化ステップは、図18Bの同期化およびエラーチェック1851、ハフマン復号化1852、およびスケールファクタ復号化1853のステップと同一である。これらのステップは任意の標準的なMP3デコーダにおいて実行され、既存の技術において周知である。基本データシーブ1866は、グラニュールを、コンテンツ連想的にアクセスされるように組織化される基本データエレメントとして含む。グラニュールを基本データシーブにインストールする際、グラニュールのコンテンツを用いて、シーブのどこにグラニュールをインストールすべきかを確認し、シーブの適切なリーフノード内の骨格データ構造およびメタデータを更新する。その後、グラニュールは、MP3データ内に存在していた時に占めていたフットプリントと同程度のフットプリントでシーブに記憶され得るように、ハフマン符号化されて圧縮される。シーブ内のグラニュールが導出部によって基本データエレメントとして必要とされるたびに、グラニュールは復元されてから導出部に供給される。このデータ蒸留装置を用いて、入力音声グラニュールは、シーブ内に存在している基本データエレメント(音声グラニュールでもある)から導出部1870によって導出され、グラニュールの無損失削減表現または蒸留表現が作成されて蒸留MP3データ1868に入れられる。このグラニュールの蒸留表現は、MP3フレームの主データフィールドに本来存在していたハフマン符号化情報を置換するエレメントフィールドに入れられる。各エレメントまたはグラニュールの蒸留表現は図1Hに示すフォーマットを用いて符号化される。蒸留データ内の各エレメントは、基本データエレメント(シーブ内の基本データエレメントまたは基本グラニュールの参照が添付されている)、または導出エレメント(シーブ内の基本データエレメントまたは基本グラニュールの参照に加えて、参照されている基本データエレメントから導出エレメントを生成する再構成プログラムが添付されている)のいずれか一方である。導出ステップの際、導出を受付けるための閾値は、削減されているフレームの主データフィールド内に存在していた元のハフマン符号化情報のサイズの一部であるように設定され得る。ゆえに、再構成プログラムと基本データエレメントの参照との合計が、(ハフマン符号化データを含んでいた)MP3符号化フレームの対応する主データフィールドのサイズのこの一部未満でない限り、導出は受付けられない。再構成プログラムと基本データエレメントの参照との合計が、(ハフマン符号化データを含んでいた)符号化MP3フレームの既存の主データフィールドのサイズのこの一部未満である場合は、導出を受付ける決定がなされ得る。
上述の方法によって、装置に記憶された複数の音声グラニュール全体にわたって、グローバルスコープで冗長を利用することができる。MP3符号化データファイルは蒸留MP3データに変換されて無損失削減形態で記憶され得る。取出される必要がある場合は、(取出部1871および再構成部1872を使用する)データ取出し処理を呼出してMP3符号化データ1873を再構成することができる。図18Cに示す装置では、再構成部は、再構成プログラムを実行して所望のグラニュールを生成する役割を果たす。再構成部はさらに、MP3符号化データを生成するのに必要なハフマン符号化ステップ(図18Aではハフマン符号化1811として示される)を実行するように改良されている。次にこのデータを標準的なMP3デコーダに供給して音声を再生することができる。
このように、データ蒸留装置は、MP3音声ファイルのサイズをさらに減少させるように適合されて使用され得る。
説明したスキームの別の変形では、MP3符号化ストリームを受信すると、パーサ/因子分解部は、主データフィールド全体を、導出のための候補エレメントとして、または基本データシーブにインストールするための基本データエレメントとして取得する。この変形では、すべてのエレメントがハフマン符号化され続けることになり、再構成プログラムはすでにハフマン符号化されているエレメントに作用することになる。このデータ蒸留装置の変形を用いてMP3音声ファイルのサイズをさらに減少させてもよい。
上記の説明は、当業者が実施形態を行って用いることができるように提示されている。開示される実施形態に対するさまざまな変更が当業者に容易に明らかとなり、本明細書に定義される一般原理は本開示の精神および範囲から逸脱することなく他の実施形態および用途にも適用され得る。ゆえに、本発明は示される実施形態に限定されず、本明細書に開示される原理および特徴と一致した最も広範な範囲が与えられる。
本開示に記載のデータ構造およびコードは、コンピュータ読取可能記憶媒体および/またはハードウェアモジュールおよび/またはハードウェア装置上に部分的または完全に格納され得る。コンピュータ読取可能記憶媒体として、揮発性メモリ、不揮発性メモリ、ディスクドライブ、磁気テープ、CD(コンパクトディスク)、DVD(デジタル汎用ディスクもしくはデジタルビデオディスク)といった磁気および光学記憶装置、または現在公知のもしくは将来開発される、コードおよび/もしくはデータを格納可能な他の媒体があるがこれらに限定されない。本開示に記載のハードウェアモジュールまたは装置として、特定用途向け集積回路(ASIC)、フィールドプログラマブルゲートアレイ(FPGA)、専用もしくは共有プロセッサ、および/または現在公知のもしくは将来開発される他のハードウェアモジュールもしくは装置があるがこれらに限定されない。
本開示に記載の方法およびプロセスは、コンピュータ読取可能記憶媒体または装置に格納されるコードおよび/またはデータとして部分的にまたは完全に具体化され得るので、コンピュータシステムが当該コードおよび/またはデータを読出して実行すると、コンピュータシステムは関連付けられた方法およびプロセスを実行する。当該方法およびプロセスはハードウェアモジュールまたは装置においても部分的にまたは完全に具体化され得るので、ハードウェアモジュールまたは装置は、起動されると、関連付けられた方法およびプロセスを実行する。なお、当該方法およびプロセスは、コード、データ、およびハードウェアモジュールまたは装置の組合せを用いて具体化されてもよい。
本発明の実施形態の上記の説明は、例示および説明目的で提示されているに過ぎない。それらは網羅的であること、または本発明を開示された形態に限定することを意図していない。したがって、多くの変更および変形が当業者に明らかになるであろう。また、上記の開示は本発明を制限することを意図していない。