(57)【要約】      （修正有）【課題】データブロックのアドレスを保持する別の記憶空間の使用を必要としないＣＡＳシステムを提供する。【解決手段】連想データを構築するシステムは、ユーザー定義の検索キーおよびデータブロックのコンテンツの両方を用いてアドレス指定される、データ内容の有向非巡回グラフ（ＤＡＧ）を有していてもよい。ＤＡＧの保持元の内部キーはユーザー定義の検索キーから導き出されてもよいが一方、残りのブロックはコンテンツアドレスされてもよい。データ内容を保持するＤＡＧを検索、削除する場合、ユーザーはコンテンツアドレスを用いないで検索キーを提供することができる。さらに、該内部キーは、ハッシュ関数を適用するおよび分散ハッシュテーブルを用いるような内部連想記憶操作を用いて実現することができる。【選択図】図１
2010157204.tif 000002
【特許請求の範囲】
【請求項１】
記憶媒体に記憶された連想データを構築するシステムであって、
不変の規則的なブロック群と、
不変の検索可能なブロック群とを有し、
前記不変の規則的なブロック群の各規則的なブロックは、システムによってそれぞれの規則的なブロックのデータ内容から導き出されたコンテンツアドレスで参照することができ、
前記不変の検索可能なブロック群の各検索可能なブロックは、それぞれの検索可能なブロックのユーザー定義の検索キーで参照することができ、ＤＡＧノードとして前記規則的なブロックの少なくとも部分集合を含む有向非巡回グラフ（ＤＡＧ）の根源であるシステム。
【請求項２】
前記規則的なブロックおよび前記検索可能なブロックの各々は、ＤＡＧポインタとして働く露出したコンテンツアドレス、またはバイトのバイナリデータの少なくとも１つを含む請求項１に記載のシステム。
【請求項３】
前記コンテンツアドレスの各々は、それぞれの規則的なブロックのデータ内容にハッシュ関数を適用することによって導き出され、前記検索可能なブロックの各々は、それぞれの検索可能なブロックの対応するユーザー定義の検索キーに前記ハッシュ関数を適用することによって得られる内部保持キーで場所を特定することができる請求項１に記載のシステム。
【請求項４】
前記規則的なブロック群および検索可能なブロック群は、前記コンテンツアドレスおよび前記内部保持キーを対応する規則的なブロックおよび検索可能なブロックにそれぞれマッピングする分散ハッシュテーブルに記憶される請求項３に記載のシステム。
【請求項５】
前記検索可能なブロックの少なくとも部分集合が検索可能なブロックのバージョン化されたシーケンスを構成し、前記シーケンスの各検索可能なブロックは異なるバージョン番号によって特定され、対応するユーザー定義の検索キーで検索可能である請求項１に記載のシステム。
【請求項６】
少なくとも１つの削除元をさらに有し、
各削除元は、１つの前記検索可能なブロックのユーザー定義の検索キーから導き出された内部削除キーで書き込まれ、前記検索可能なブロックの１つに削除の印を付ける請求項１に記載のシステム。
【請求項７】
前記規則的なブロック群、前記検索可能なブロック群、および前記少なくとも１つの削除元は、前記コンテンツアドレス、前記内部保持キー、および前記内部削除キーを対応する規則的なブロック、検索可能なブロック、および削除元にそれぞれマッピングする分散ハッシュテーブルに記憶される請求項６に記載のシステム。
【請求項８】
削除の印が付けられていないあらゆる検索可能なブロックから到達できないブロックを削除するように構成されたガーベッジコレクションモジュールをさらに有する請求項７に記載のシステム。
【請求項９】
記憶媒体を含む連想記憶システムのデータを管理する方法であって、
ユーザー定義の検索キーとデータ内容とを含む書き込み要求を受け取り、不変の検索可能なブロックを書き込むことと、
前記ユーザー定義の検索キーに基づいて内部保持キーを導き出すことと、
前記検索可能なブロックが不変の規則的なブロックの有向非巡回グラフ（ＤＡＧ）を根づかせるように、前記記憶媒体に前記不変の検索可能なブロックを記憶することとを含み、
前記検索可能なブロックは前記データ内容を含み、前記内部保持キーで場所を特定することができ、前記規則的なブロックの各アドレスは、それぞれの規則的なブロックのコンテンツから導き出されたコンテンツアドレスである方法。
【請求項１０】
前記導き出すことは、前記ユーザー定義の検索キーにハッシュ関数を適用して前記内部保持キーを生成することをさらに含み、前記コンテンツアドレスは、それぞれの規則的なブロックの各々に記憶されたコンテンツに前記ハッシュ関数を適用することによって生成されたハッシュキーから導き出される請求項９に記載の方法。
【請求項１１】
分散ハッシュテーブル（ＤＨＴ）が前記内部保持キーおよび前記コンテンツアドレスを前記検索可能なブロックおよび対応する規則的なブロックにそれぞれマッピングするように、前記検索可能なブロックおよび前記内部保持キーを該分散ハッシュテーブル（ＤＨＴ）に挿入することをさらに含む請求項１０に記載の方法。
【請求項１２】
前記挿入前にＤＨＴルックアップを実行して前記内部保持キーを前記ＤＨＴのエントリと比較することをさらに含み、
前記挿入は、前記ＤＨＴが前記内部保持キーを含んでいない場合、または該ＤＨＴが前記内部保持キーを含みかつ該内部保持キーを前記データ内容と同一の値にマッピングする場合に行われる請求項１１に記載の方法。
【請求項１３】
前記ユーザー定義の検索キーを含む読み出し要求を受け取り、前記データ内容を検索することと、
前記読み出し要求を受け取ることに応答して、前記ハッシュ関数を前記ユーザー定義の検索キーに適用し、前記内部保持キーを導き出すことと、
前記内部保持キーでＤＨＴルックアップを実行し、前記データ内容を検索することとをさらに含む請求項１２に記載の方法。
【請求項１４】
バージョン番号を持つユーザー定義の検索キーを内部的に追加し、検索可能なブロックのバージョン化されたシーケンスの構成要素として前記検索可能なブロックを特定することをさらに含み、
前記内部保持キーは前記ユーザー定義の検索キーおよび前記バージョン番号の両方に基づいている請求項１３に記載の方法。
【請求項１５】
前記読み出し要求は、前記バージョン化されたシーケンスの一部である前記検索可能なブロックのバージョンを検索する前記バージョン番号を含む請求項１４に記載の方法。
【請求項１６】
前記ユーザー定義の検索キーを含む削除要求を受け取り、前記データ内容を削除することと、
前記検索キーに基づいて内部削除キーを導き出すことと、
前記内部削除キーで削除元ブロックを前記記憶媒体に書き込み、前記検索可能なブロックに削除の印を付けることとをさらに含む請求項９に記載の方法。
【請求項１７】
前記検索可能なブロックに関連付けられた規則的なブロックにガーベッジコレクション操作を行うことをさらに含む請求項１６に記載の方法。
【請求項１８】
記憶媒体を含む連想記憶システムのデータを削除する方法であって、
記憶媒体に記憶された検索可能なブロックによって根づかされた規則的なブロックの有向非巡回グラフ（ＤＡＧ）を有する不変のデータブロック群を提供することを含み、各検索可能なブロックはそれぞれの検索可能なブロックのユーザー定義の検索キーで場所を特定することができ、各規則的なブロックはそれぞれの規則的なブロックのコンテンツから導き出されたコンテンツアドレスで場所を特定することができ、
前記ユーザー定義の検索キーの１つである第１の検索キーを含む要求を受け取り、前記ＤＡＧの１つで編成されたデータコンテンツに削除の印を付けることと、
前記第１の検索キーに基づいて内部削除キーを導き出すことと、
前記内部削除キーで削除元ブロックを前記記憶媒体に書き込むことと、
前記記憶媒体から、削除元ブロック、および前記第１の検索キーで場所が特定可能な検索可能なブロックを削除することとを含む方法。
【請求項１９】
前記削除することは、
前記削除元、および前記第１の検索キーで場所を特定することができる検索可能なブロックに削除の印を付けることと、
削除の印を付けられていない任意の検索可能なブロックから到達できない規則的なブロックすべてに反復して削除の印を付けることと、
削除の印を付けられたブロックすべてを取り除くこととをさらに含む請求項１８に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願情報）
本出願は、参照によりここに組み込まれている、２００８年９月１１日に申請された仮特許出願番号第６１／０９５，９９４号、および参照によりここに組み込まれている、２００９年７月２９日に申請された非仮特許出願番号第１２／５１１，１２６号の優先権を主張する。
【０００２】
本発明は、一般に記憶媒体上のデータの記憶を管理することに関し、より詳細には２次記憶システムの検索可能なデータブロックを用いてデータ内容の記憶を管理することに関する。
【背景技術】
【０００３】
情報を記憶するための共通の機構は、所定の記憶場所に基づくよりはむしろコンテンツのデータブロックのアドレスに基づいた連想記憶（ＣＡＳ）システムである。通常、ＣＡＳシステムは、２次記憶装置すなわち「永久」記憶装置の比較的固定されたコンテンツ（ｆｉｘｅｄ  ｃｏｎｔｅｎｔ  ）を高速で記憶、検索するのに用いられる。連想記憶（ＣＡＳ）システムは、コンテンツアドレスの使用によって記憶されたデータへのアクセスを提供する。コンテンツアドレス（ＣＡ）は、一般的にいくつかの情報を結合することによって形成され、該情報の少なくとも１つは記憶されたオブジェクトのコンテンツに依存する。一般的に、コンテンツアドレスの少なくとも一部は、オブジェクトの関連データブロックの内容に、ＳＨＡ−１のような強いハッシュ関数を適用することから導き出される。
【０００４】
従来の記憶システムとは対照的に、ブロックのデータ内容を変えることはそのアドレスを変えることにもなるので、データブロックがひとたび書き込まれたら変更することができないという意味で、コンテンツアドレスに基づいた記憶システムは不変なシステムである。このことは、ユーザーに検索されたデータが記憶されたデータと全く同一であるというある保証を与えるだけでなく、システムが重複ブロックを記憶しないようにすることも可能にする。例えば、ユーザーが同一のデータに対して複数の書き込み操作を行った場合、システムはデータのたった１つのコピーのみを記憶し、書き込み操作の各々に対して同一のコンテンツアドレスを返す。データブロックのアドレスがシステムによって決定されるので、このことが可能になる。しかしながら、ここでＣＡＳシステムは不変であると説明したが、「不変である（ｉｍｍｕｔａｂｌｅ）」ということを、データブロックを削除できないことを意味するように解釈すべきでないことに留意されたい。もっと正確に言えば、「不変の」システムとは、システムが、異なるデータコンテンツに既に用いられたコンテンツアドレスでデータ内容を参照できないようにすることを意味するものと解釈されるべきである。
【０００５】
都合の悪いことに、ＣＡＳシステムを使用する場合、ユーザーは、後でオブジェクトを検索または読み取る能力を保持するために、該オブジェクトを書き込んだ後ＣＡを記憶しなければならない。例えば、ハッシュ関数の使用により、ＣＡは引き出されると必ず元のコンテンツを保持しているので、ユーザーがコンテンツアドレスを記憶せずにブロックを検索する方法はない。さらに、有向非巡回グラフ（ＤＡＧ）の生成を可能にするようにＣＡが記憶されたオブジェクトに埋め込まれている、ＥＭＣのＣ−ｃｌｉｐのような高度なシステムでさえ、ＤＡＧの根源は、コンテンツなしでは引き出せないアドレスビットを含んだＣＡである。オブジェクトを書き込む際、Ｃ−ｃｌｉｐのコンテンツアドレスは、該コンテンツアドレスを異なる場所に記憶しなければならないアプリケーションに返される。
【０００６】
したがって、ＣＡＳを用いた現在の記憶システムは、該記憶システムが複数の根源ブロックのＣＡ、および多くのシステムでは他のブロックのＣＡも同様に保持する別の記憶装置を必要とするので、必要なものをすべて完備しているわけではない。
【発明の概要】
【０００７】
したがって、記憶効率を改善するために、データブロックのアドレスを保持する別の記憶空間の使用を必要としないＣＡＳシステムが必要とされる。本発明の種々の典型的な実施形態によれば、本明細書で下に説明するような「検索可能なブロック」の使用は、データブロック元のアドレス用の別の記憶装置を維持する必要があるいかなるものも不要にする。例えば、保持元として実行される検索可能なブロックは、ブロックのコンテンツのハッシュに基づく必要がなく、ユーザーが簡単に思い出せる、ユーザー定義の検索キーに従って記憶、参照することができる。さらに、本明細書で下に説明するように、ＤＡＧの残りは、ＣＡＳシステムの他のすべての機能のシームレスな動作を可能にするようにアドレスされたコンテンツであってもよい。
【０００８】
本発明の１つの典型的な実施形態は、記憶媒体に記憶された連想データを構築するシステムを含んでおり、該システムは、不変の規則的なブロック群と、不変の検索可能なブロック群とを含み、該不変の規則的なブロック群の各規則的なブロックは、システムによってそれぞれの規則的なブロックのデータ内容から導き出されたコンテンツアドレスで参照することができ、該不変の検索可能なブロック群の各検索可能なブロックは、それぞれの検索可能なブロックのユーザー定義の検索キーで参照することができ、ＤＡＧノードとして前記規則的なブロックの少なくとも部分集合を含む有向非巡回グラフ（ＤＡＧ）の根源である。
【０００９】
本発明の他の典型的な実施形態は、記憶媒体を含んだ連想記憶システムのデータを管理する方法を含み、該方法は、ユーザー定義の検索キーとデータ内容とを含み、不変の検索可能なブロックを書き込む書き込み要求を受け取るステップと、該ユーザー定義の検索キーに基づいて内部保持キーを導き出すステップと、検索可能なブロックが不変の規則的なブロックの有向非巡回グラフ（ＤＡＧ）を根づかせるように、記憶媒体に不変の検索可能なブロックを記憶するステップと、を含み、前記検索可能なブロックは前記データ内容を含み、前記内部保持キーで場所を特定することができ、前記規則的なブロックの各アドレスは、それぞれの規則的なブロックのコンテンツから導き出されたコンテンツアドレスである。
【００１０】
本発明の代替の典型的な実施形態は、記憶媒体を含んだ連想記憶システムのデータを削除する方法を含み、該方法は、記憶媒体に記憶された検索可能なブロックによって根づかされた規則的なブロックの有向非巡回グラフ（ＤＡＧ）を有する不変のデータブロック群を提供するステップであって、各検索可能なブロックはそれぞれの検索可能なブロックのユーザー定義の検索キーで場所を特定することができ、各規則的なブロックは、それぞれの規則的なブロックのコンテンツから導き出されたコンテンツアドレスで場所が特定されるステップと、前記ユーザー定義の検索キーの１つである第１の検索キーを含み、前記ＤＡＧの１つで編成されたデータコンテンツに削除の印を付ける要求を受け取るステップと、前記第１の検索キーに基づいて内部削除キーを導き出すステップと、前記内部削除キーで削除元ブロックを前記記憶媒体に書き込むステップと、前記記憶媒体から、削除元ブロック、および前記第１の検索キーで場所が特定可能な検索可能なブロックを削除するステップとを含む。
【００１１】
これらおよび他の特徴および利点は、添付の図面に関して読まれるべき、その例示となる実施形態に関する以下の詳細な説明から明白になるであろう。
【図面の簡単な説明】
【００１２】
本開示は、次の図面を参照することによって、以下の好ましい実施形態の説明においてその詳細を提供する。
【図１】本発明の１つの典型的な実施形態に係る連想データを構築するシステムを示したブロックダイアグラムである。
【図２】本発明の１つの典型的な実施形態に係る連想記憶システムのデータを管理する方法を示したブロック／フローダイアグラムである。
【図３】本発明の１つの典型的な実施形態に係る連想記憶システムのデータを読み取る方法を示したブロック／フローダイアグラムである。
【図４】本発明の１つの典型的な実施形態に係る連想記憶システムのデータを削除する方法を示したブロック／フローダイアグラムである。
【図５】本発明の１つの典型的な実施形態に係る連想記憶システムのデータを削除する代替方法を示したブロック／フローダイアグラムである。
【図６】本発明の１つの典型的な実施形態に係る連想記憶システムのＤＡＧの少なくとも一部の削除を実行する方法を示したブロック／フローダイアグラムである。
【図７】本発明の典型的な実施形態に係る規則的なブロックおよび検索可能なブロックの表現を示したブロックダイアグラム群である。
【図８】本発明の典型的な実施形態に係る検索可能なブロック、および検索可能なブロックのバージョン化されたシーケンスの表現を示したブロックダイアグラム群である。
【図９】本発明の典型的な実施形態に係る検索可能な保持元ブロックおよび削除元ブロックの表現を示したブロックダイアグラム群である。
【発明を実施するための形態】
【００１３】
データブロックのコンテンツアドレス用に別の記憶装置を維持しないようにするために、本発明の典型的な実施に係る記憶システムは、少なくとも２つの種類のブロック、すなわち規則的なブロック（ｒｅｇｕｌａｒ  ｂｌｏｃｋｓ）と「検索可能なブロック（ｓｅａｒｃｈａｂｌｅ  ｂｌｏｃｋｓ）」とを記憶する機構を提供することができる。
【００１４】
本発明の典型的な実施形態によれば、規則的なブロックは、引数として記憶されるオブジェクトを呼出元が供給するという点において、他のＣＡＳシステムと類似する方法で書き込まれ、恐らく該オブジェクトがどこに他のブロックに対するコンテンツアドレス（ＣＡ）を埋め込んでいるかに関する記述を含んでいるであろう。さらに、そのコンテンツに基づいたＣＡを有する値は、書き込みの完了時にユーザーに返される。
【００１５】
ＣＡ＜−−ｗｒｉｔｅ＿ｒｅｇｕｌａｒ＿ｂｌｏｃｋ（ｄａｔａ，ｌｉｓｔ＿ｏｆ＿ｅｍｂｅｄｄｅｄ＿ＣＡｓ）
本発明の１つの典型的な実施によれば、規則的なブロックを実現するために、ブロックコンテンツ（任意の埋め込まれたＣＡを含む）をハッシュ化してハッシュ値を導き出してもよい。例えば、ここで類似の参照番号が同一または類似の要素を表す図面および先ず図７を詳細に参照して、典型的な規則的なブロック７００の表現が示されている。規則的なブロックのデータ内容は、０または１以上のバイトのバイナリデータ（例えば「ユーザーデータ」）を含んでいてもよく、および／またはＤＡＧポインタとして働く露出したコンテンツアドレスを含んでいてもよい。図７に提供された特定の例では、規則的なブロック７００は、ＣＡでないバイナリデータ７０２とコンテンツアドレスのリスト７０４との両方を含んでいる。ＣＡでないバイナリデータ７０２とコンテンツアドレス群７０４との両方を含んだブロックコンテンツ７０６がシステムによって記憶され、該コンテンツは、ハッシュ関数を適用してブロックのハッシュ値を得ることができる情報である。
【００１６】
例えば分散ハッシュテーブル（ＤＨＴ）に従ってハッシュ値の少なくとも一部を使用して、ブロックを、該ブロックを記憶する責任を負うべき記憶ノードへ送ってもよい。システムは、＜ハッシュ値、ブロック＞ペアを局所的に記憶してもよく、後でブロックの好都合な検索を容易にするかもしれない他のいくつかのオプションのフィールドに加えて、ハッシュ値の一部を含んだＣＡを返してもよい。
【００１７】
規則的なブロックのデータを検索するために、ＣＡは次のように提供される。
【００１８】
（ｄａｔａ，ｌｉｓｔ＿ｏｆ＿ｅｍｂｅｄｄｅｄ＿ＣＡｓ）＜−−ｒｅａｄ＿ｒｅｇｕｌａｒ＿ｂｌｏｃｋ（ＣＡ）
例えば、読み込みは上で述べたハッシュ値の一部を用いて、＜ハッシュ値、ブロック＞ペアを記憶しているノードに送ってもよく、ノード上のペアの局所的な検索の速度を上げるために随意に任意の他のフィールドを用いてもよい。
【００１９】
以前に書き込まれたブロックと重複する任意の次のブロックの書き込みを、以前に書き込まれたブロックを記憶しているノードと同一のノードに送ることができる。ローカルノードは、該ローカルノードが同一のハッシュ値を持つブロックが既に記憶されていることを認識する機構を実現することもできる。該機構は、例えば局所的なハッシュテーブルを用いることによって実現することができる。したがって、（元の）ブロックは他のフィールドを利用せずに検索することができる。
【００２０】
ある意味、ブロック記憶装置は、辞書のキーとして働くＣＡを有する（大きな）辞書に似ていて、データは、辞書の値として働く埋め込まれたＣＡのリストを加えたものである。これはＤＨＴとして実現することができる。規則的なブロックの主たる特徴は、ブロックのキーまたはコンテンツアドレスが該ブロックのコンテンツから内部的に導き出されることである。
【００２１】
本明細書で下に説明するように、ＤＡＧの根源（ｒｏｏｔ）の検索用のＣＡの記憶は、検索可能なブロックを用いることによって回避される。検索可能なブロックは、規則的なブロックとは異なって書き込まれている。検索可能なブロックについては、システムは、ＣＡと同様に処理されるがＣＡでない値を内部的に導き出してもよい、すなわち本明細書では、該値を「内部キー（ｉｎｔｅｒｎａｌ  ｋｅｙ）」と呼ぶ。したがって、規則的なブロックの書き込み操作とは対照的に、本発明の典型的な実施形態によれば、検索可能なブロックの書き込み操作は、コンテンツのブロックのハッシュ化ではなくユーザー定義の検索キーのハッシュ化によりハッシュ値を得ることができる。内部的に、システムは、規則的なブロックに用いられたものと同一のルーティングメカニズムを用いることができる。さらに、重複書き込みの場合のように、他のフィールドを利用しないでペアを検索することができるので、ＣＡを検索可能なブロック用に生成する必要性はない。
【００２２】
したがって、本発明の典型的な実施形態によれば、データ、および／または埋め込まれたＣＡのリストの提供に加えて、呼出元は、検索可能なブロックに対して一意のユーザー定義の「検索キー（ｓｅａｒｃｈ  ｋｅｙ）」を提供することができる。
【００２３】
ｗｒｉｔｅ＿ｓｅａｒｃｈａｂｌｅ＿ｂｌｏｃｋ（ｄａｔａ，ｌｉｓｔ＿ｏｆ＿ｅｍｂｅｄｄｅｄ＿ＣＡｓ，ｓｅａｒｃｈ＿ｋｅｙ）／＊Ｎｏ  ＣＡ  ｒｅｔｕｒｎｅｄ  ｏｎ  ｃｏｍｐｌｅｔｉｏｎ＊／
ここで、ｓｅａｒｃｈ＿ｋｅｙはクライアントの選択であり、書き込まれたコンテンツにハッシュ関数を適用することによって検索キーを得る必要はない。ブロックの検索キーはそのブロックに対するアドレスとして働くが、コンテンツアドレスではない。従来のＣＡＳシステムのユーザーは、新しく書き込まれたブロックの所与で所定のコンテンツアドレスを、このコンテンツアドレスによってブロックを検索できるように返すことをシステムに強いることができないが、本システムのユーザーは、検索可能なブロックを書き込む場合、検索キーを選択することができる。検索キーは、コンテンツアドレスを参照する必要なしに保存データへのユーザーアクセスを可能にする、ユーザーが選択した任意のキーであってもよい。
【００２４】
図７を参照して、本発明の１つの典型的な実施形態に係る検索可能なブロック７５０の表現が示されている。図７に示すように、検索可能なブロック７５０はユーザー定義の検索キー７５２を含んでいてもよい。さらに、検索可能なブロック７５０のデータ内容は、０または１以上のバイトのＣＡでないバイナリデータ７５４、および／または他のブロックへのポインタと働くＣＡのリスト７５６も含むことができる。ここで、検索可能なブロックの内部キーは、全体のブロックコンテンツではなく、ユーザー定義の検索キー７５２をハッシュ化することによって得ることができる。記憶された値７５８は、ユーザー定義の検索キー７５２と、上で述べたように、０または１以上のバイトのＣＡでないバイナリデータ７５４またはポインタと働くＣＡのリスト７５６の少なくとも１つを含んでいてもよいブロックのデータ内容と、から構成することができる。
【００２５】
記憶ブロックが有向非巡回グラフ（ＤＡＧ）構成に配置されている場合、検索可能なブロックは、該検索可能なブロックを用いて規則的なブロックのＤＡＧの根源を記憶できるという点で、「保持元（ｒｅｔｅｎｔｉｏｎ  ｒｏｏｔ）」として実現することができる。データを検索するために、クライアントはＣＡではなく検索キーを提供することができる。
【００２６】
（ｄａｔａ，ｌｉｓｔ＿ｏｆ＿ｅｍｂｅｄｄｅｄ＿ＣＡＳ）＜−−ｒｅａｄ＿ｓｅａｒｃｈａｂｌｅ＿ｂｌｏｃｋ（ｓｅａｒｃｈ＿ｋｅｙ）
なお、記憶システムは、異なるコンテンツを持つブロックが同一の検索キーで既に書き込まれている場合には、書き込みを拒絶するように構成できることに留意されたい。記憶システムは、その検索キーの読み取りを試みる最中に発生する曖昧さを回避するために書き込みを拒絶することができる。したがって、一意と思われるキーを選択することがクライアントの責任である。
【００２７】
例えば、クライアントが衝突のせいで確率的に書き込み要求を拒絶しそうもないＤＡＧに関連付けることが容易なあらゆる情報を、検索キーと結合することができる。なお、ブロック記憶装置を共有している敵対的でないクライアントについては、検索キーのクライアント名の部分を作成するだけでそれらのシーケンス衝突を回避するのはかなり容易であることに留意されたい。敵対的クライアントに関して、クライアントの秘密の暗号化キーのような攻撃者が解読するのが確率的に難しい情報の少なくとも一部が検索キーに含まれていてもよい。例えば、バックエンドの２次記憶システムとして本記憶システムを用いるファイルシステムについては、情報の３つのそのような部分が次のものを含んでいてもよい。（ｉ）他の記憶装置、非ファイルシステム、バックエンド記憶システムのユーザーとの衝突を回避するバックエンド記憶装置を用いたアプリケーション名（例えば「ファイルシステム」）、（ｉｉ）２つの異なるファイルシステムの検索キーのシーケンス間の衝突を回避するファイルシステム名、（ｉｉｉ）より詳細に下に説明するような、カウンタとして働く１で始まる正のシーケンス番号
この点まで、ブロックのコンテンツに基づいてブロック記憶装置によって生成されたコンテンツアドレスを通してアドレス指定することができる規則的なブロックを記憶するプールと、クライアントによって生成される検索キーで場所を特定することができるブロックを記憶するプールと、から構成された２つの別の記憶装置プールの結合としてブロック記憶装置を説明した。しかしながら、規則的なブロックを実現するために用いられるコードを検索可能なブロックを実現するために再使用できるので、２つの別の記憶装置プールを維持する必要はない。例えば、検索可能なブロックの検索キーは、コンテンツアドレスが規則的なブロックから得られる方法と同じ方法でハッシュ関数を適用することができる。したがって、疑似コンテンツアドレスは検索キーから生成され、次のルックアップ用の分散ハッシュテーブル（ＤＨＴ）に記憶されてもよい。この疑似コンテンツアドレスは、上で説明した「内部キー」に対応していてもよい。したがって、ユーザーがブロックを読み取りたくて検索キーを提供する場合、該検索キーはＤＨＴのブロックをルックアップするのに使用される内部キーに変換されてもよい。
【００２８】
その結果、内部的に、検索可能なブロックは、その疑似ＣＡがデータおよび埋め込まれたＣＡのリストからでなく検索キーから導き出されるという点を除いて、規則的なブロックと同一の方法で処理することができる。そのため、検索可能なブロックおよび規則的なブロックは同一の記憶プールに含まれていてもよいが、それらのキーがどのように導き出されるかで異なっている。上述のごとく、ユーザー定義の検索キーをそれ自身検索可能なブロックを検索するのに用いることができるので、ブロックの検索のためにクライアントによって疑似ＣＡが提供される必要はない。これおよび他の理由で、疑似ＣＡは、該ＣＡが返される規則的なブロックの場合とは異なり、書き込みの完了時クライアントに返されない。
【００２９】
本発明の典型的な実施形態に係る検索可能なブロックを書き込むための高度なアルゴリズムが以下の表１に示されている。該アルゴリズムに示すように、ＣＡＳ記憶システムにおいて既に内部的に利用可能な操作（ＤＨＴのエントリのそのような挿入およびルックアップ）を用いて検索可能なブロックを実現することができる。
【００３０】
【表１】
2010157204.tif 000003
【００３１】
以下に示した表２は、本発明の典型的な実施形態に係る検索可能なブロックを読み取る高度なアルゴリズムを提供する。
【００３２】
【表２】
2010157204.tif 000004
【００３３】
ここでは図１を参照して、本発明の１つの典型的な実施に係る検索可能なブロックを用いたデータ記憶システム１００が示されている。なお、ここで説明する実施形態は完全にハードウェアであってもよく、またはハードウェア要素とソフトウェア要素の両方を含んでいてもよいということを理解すべきであろう。好ましい実施形態において、本発明は、ソフトウェア、およびファームウェア、常駐ソフトウェア、マイクロコード等を含むがこれらに限定されないハードウェアによって実行される。
【００３４】
実施形態は、コンピュータまたは任意の命令実行システムによってまたはそれらに関連して使用されるプログラムコードを提供するコンピュータ使用可能媒体またはコンピュータ可読媒体からアクセス可能なコンピュータプログラム製品を含んでいてもよい。コンピュータ使用可能媒体すなわちコンピュータ可読媒体は、命令実行のシステム、装置、またはデバイスによってまたはそれらに関連して、使用されるプログラムを格納する任意の装置を含んでいてもよい。該媒体は、磁気、光学、電子、電磁気、赤外線、または半導体のシステム（すなわち装置またはデバイス）でありえる。媒体は、半導体または固体メモリ、磁気テープ、リムーバブルコンピュータディスケット、ランダムアクセスメモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、剛性磁気ディスクおよび光ディスク等のような、コンピュータ可読媒体を含んでいてもよい。
【００３５】
さらに、本発明の典型的な実施形態では、検索可能なブロックおよび規則的なブロックは、記憶装置のネットワークを含む１つまたは２つ以上の記憶装置を有する記憶媒体に記憶することができる。さらに、ここで開示した方法は、ハードウェアおよび／またはソフトウェアで符号化されたプログラム命令を実行するように構成されたプロセッサおよびメモリを用いて実現することができる。
【００３６】
図１に戻り、システム１００のプログラミングモデル１０１は、記憶媒体に記憶された、可変サイズで、連想的で、高弾力的なブロックの海の抽象的概念に基づいてもよい。システム１００は不変の規則的なブロック群１３０を含んでいてもよく、例えば、上で説明したように、該群の各規則的なブロックは、システムによってそれぞれのデータブロックのデータ内容から導き出されたコンテンツアドレスで参照することができる。上述のごとく、規則的なブロックのアドレスは、例えば該ブロックのコンテンツのＳＨＡ−１ハッシュから導き出すことができる。さらに、内部ハッシュキーのみを用いるよりもより効率的にシステム内のブロックの場所を特定するのに用いることができる他の情報をコンテンツアドレスに用いることができる。該コンテンツアドレスはハッシュキーより短くてもまたは長くてもよい。
【００３７】
さらに、システム１００は不変の検索可能なブロック群１４０を含んでいてもよく、該ブロック群の各々は、上で説明したように、それぞれの検索可能なブロックのユーザー定義の検索キーで参照することができる。例えば、内部キーはユーザー定義の検索キーから導き出され、ブロックの場所を特定するのに使用することができる。なお、ここで用いている「導き出された（ｄｅｒｉｖｅｄ）」とは、例えば、上述のごとくハッシュ関数の適用によってまたは単に内部キーが「導き出された」オブジェクトを用いることによって、内部キーを得ることを含んでいてもよいということを理解すべきであろう。例えば、内部キーは、該内部キーが検索キーであるという点においてユーザー定義の検索キーから導き出すことができる。しかしながら、他の導出手段が用いられてもよい。さらに、内部キー、例えば上で説明した疑似コンテンツアドレスは、規則的なブロックからコンテンツアドレスを導き出すのに使用されたのと同じハッシュ関数をユーザー定義の検索キーに適用することによって、検索キーから導き出すことができることに留意されたい。さらに、検索可能なブロック群１４０および規則的なブロック群１３０は、対応する規則的なブロック１３０および検索可能なブロック１４０にコンテンツアドレスおよび内部キーをそれぞれマッピングするＤＨＴに記憶することもできる。したがって、各検索可能なブロックは対応する導き出された内部キーで場所を特定することができる。
【００３８】
任意のブロックは、０または１以上のバイトのバイナリデータおよび／またはブロックのＤＡＧを定義する既に書き込まれているブロックを指すポインタのリスト１２４の少なくとも１つを含んでいてもよい。上述のごとく、ポインタはコンテンツアドレスとして実現されてもよい。ここで、図１に示すように、各検索可能なブロック１０２および１０４は、規則的なブロック１３０の少なくとも部分集合を含むＤＡＧの根源であってもよい。したがって、検索可能なブロックとして実現された保持元の「内部キー」は、同じ意味合いで「内部保持キー」と呼ぶことができる。重複除外機能を提供する記憶システムでは、ブロックは重複除去比を改善できるように可変サイズであってもよい。下でより十分に説明するように、ポインタ１２４は、ガーベッジコレクションの変形としてガーベッジコレクションモジュール１６０により実行されるデータ削除を容易にするために露出していてもよい。
【００３９】
図１に示すように、ブロックは有向非巡回グラフ（ＤＡＧ）を形成してもよい。重複除外サービスが記憶システムによって提供される場合、これらのＤＡＧは重複除外されたブロックと重複していてもよい。さらに、ブロックアドレスを導き出すのに用いられるハッシュ関数の安全が暗号的に確保されている限り、いかなるサイクルもこれらの構造においては可能ではない。なお、ここで説明した「ＤＡＧ」は、ＤＡＧの特別な事例である「ツリー」を含んでいてもよいということを理解すべきであろう。
【００４０】
上述のごとく、ＤＡＧの原点は、検索可能な保持元と名付けられた、特別な形態のブロックであってもよい。しかしながら、本発明の典型的な実施形態は検索可能なブロックでないＤＡＧの根源を持つことができるということを理解すべきであろう。正規のデータおよび一連のアドレスに加えて、保持元は、上で説明したように、ブロックの場所を特定するのに用いられるユーザー定義の検索キーを持つ検索可能なブロックとして構成されてもよい。そのようなキーは任意のデータであってもよい。上述のごとく、ユーザーは、システムが生成した暗号のブロックコンテンツアドレスの代わりに、該検索キーの提供によって検索可能なブロックを検索することができる。さらに、下でより十分に説明するように、同一ファイルシステムの複数のスナップショットは、例えばファイルシステム名から導き出された検索キーベースおよび各スナップショットでインクリメントされるカウンタで場所を特定することができる検索可能な保持元のバージョン化されたシーケンスとして編成された根源を持っていてもよい。任意の検索キーを指定することによって検索可能なブロックを検索することができるが、該検索可能なブロックは規則的なブロックが持っているようなコンテンツアドレスを持っていない、そのため該検索可能なブロックはシステムでは指されない、それゆえ該検索可能なブロックはブロック構造ではサイクルを生成しない。
【００４１】
図１を再び参照して、ブロック群１０１は３つの原点１０２、１０４、および１０６を含んでいて、その中の２つの原点１０２および１０４は、検索可能なブロックとして実行される保持元である。他の原点１０６は、ＤＡＧのこの部分がまだ構築中であることを示す規則的なブロックＡである。
【００４２】
ＤＡＧ構造化データの動作は、より詳細に下に説明するが、規則的なブロックを書き込むことおよび読み取ること、ユーザー定義の検索キーにより検索可能な保持元を書き込むこと、該検索キーに基づいて保持元を検索すること、ユーザー定義のキーを用いて関連する削除元（ｄｅｌｅｔｉｏｎ  ｒｏｏｔ）１０８を書き込むことにより削除される保持元に印を付けること、を含んでいてもよい。
【００４３】
上に述べたように、検索可能な保持元は、保持元のバージョン化されたシーケンスに編成されてもよい。例えば、記憶システムは、ファイルシステムをＤＡＧの根源であるファイルシステムのスーパーブロックと共に該ＤＡＧに記憶してもよい。新しいファイルシステムを表す新しいＤＡＧ構造および新しいＤＡＧの根源である新しいスーパーブロックを生じさせる、ファイルシステムの新しいバージョンは定期的に更新、記憶されてもよい。アプリケーションがＤＡＧの異なるバージョンに対応する多くの根源を書き込むことに関心を持っている場合、それはシステムが、（ｉ）根源の新しいバージョンを書き込み、（ｉｉ）最新バージョンを読み取るのに便利であり、それらは、次のように記述される。
【００４４】
ｖｅｒｓｉｏｎ＿ｎｕｍｂｅｒ＜−−ＷＲＩＴＥ＿ＮＥＷ＿ＶＥＲＳＩＯＮ（ｓｅａｒｃｈ＿ｋｅｙ＿ｂａｓｅ，ｄａｔａ＿ｗｉｔｈ＿ｅｍｂｅｄｄｅｄ＿ＣＡｓ＿ｅｘｐｏｓｅｄ）；
ｄａｔａ＿ｗｉｔｈ＿ｅｍｂｅｄｄｅｄ＿ＣＡＳ＿ｅｘｐｏｓｅｄ＜−−ＲＥＡＤ＿ＬＡＳＴ＿ＶＥＲＳＩＯＮ（ｓｅａｒｃｈ＿ｋｅｙ＿ｂａｓｅ）
異なるファイルシステムのバージョン番号は時間（１次元に沿って）と共に増加するので、システムは、バージョン化されたシーケンスに関してここで「検索キーベース（ｓｅａｒｃｈ  ｋｅｙ  ｂａｓｅ）」と呼ばれるユーザー定義の検索キー値と、総合的なバージョン番号と、を内部的に結合して、内部キーを生成または導き出すことができる。当業者には理解されようが、本開示を考慮して、必要であれば、これを多次元に一般化することは簡単である。さらに、上述のごとく、ユーザー定義の検索キーまたは検索キーベースは任意のバイト列になりえる。この柔軟性が、全体のバージョン化されたシーケンスをたった１つの検索キーベースを思い出すことによって特定することができる、検索可能なブロックのバージョン化されたシーケンスの実施を可能にする。
【００４５】
図１および７の参照に続き図８を参照して、検索可能なブロック８００および検索可能なブロック８５０のバージョン化されたシーケンスの表現が示されている。上述のごとく、異なるファイルシステムバージョンの可能性を考慮して、システムは、シーケンス番号を検索キーに付加することによって新しいＤＡＧまたは更新されたＤＡＧの全体のシーケンスの内部保持キーを生成するプロセスを実行してもよい。例えば、図８に示すように、検索可能なブロック８００は、バージョン番号８０４が追加された検索キーベース８０２を含んだ結合値８０６を含んでいてもよい。該結合値８０６をシステムで用いて、上で説明したようなシステムが検索可能なブロック７５０のユーザー定義の検索キー７５２から内部キーを導き出した方法と同一の方法で、内部保持キーを導き出すことができる。さらに、結合値８０６から導き出された内部キーを上で説明した方法と同一の方法で用いることができる。例えば、内部キーは、検索可能なブロックに該内部キーをマッピングするＤＨＴへのエントリとして用いることができる。検索可能なブロック８００の残りは、０または１以上のバイトのバイナリデータまたは他のブロックへのポインタとして働くコンテンツアドレスの少なくとも１つを含むコンテンツ８０８を有していてもよい。したがって、バージョン番号を持つ検索可能なブロックとして実行される保持元は、上で説明した方法に類似した方法で、ユーザー定義の検索キーにより参照または場所を特定することができる。
【００４６】
なお、フィールドはすべて、バージョン番号を除いて、すべてのファイルシステムバージョンにわたって結合値８０６内で一貫しているということを理解すべきであろう。例えば、図８に示すように、バージョン化されたシーケンス８５２の各検索可能なブロックは、異なるバージョン番号が追加された同一のユーザー定義の検索キー８５６を含んでいてもよい。例えば、ブロック８５４はバージョン番号１（８５８）を含んでいてもよく、ブロック８６２はバージョン番号２（８６０）を含んでいてもよい、等。さらに、検索可能なブロックは、ユーザーデータ８６４、８６６、および／またはＤＡＧを形成する規則的なブロック群８７２を指すコンテンツアドレス８６８、８７０を含む保持元として実現することができる。
【００４７】
また、ユーザーの観点から、バージョン化されたシーケンスを持つシステムは、上で説明したブロック検索に類似する手法で検索可能なブロックを検索することができることも理解すべきであろう。例えば、ユーザーまたはクライアントはユーザー定義の検索キーを提供することができ、システムは、対応する検索可能なブロックの最新バージョンをユーザーに自動的に返すことができる。代替としてまたは付加的に、ユーザーは、ユーザー定義の検索キーおよびバージョン番号を提供して、システムによって記憶された検索可能なブロックの任意のバージョンを検索することができる。順に、システムはそれぞれの検索可能なブロックの対応するバージョンを返してもよい。
【００４８】
ｄａｔａ＿ｗｉｔｈ＿ｅｍｂｅｄｄｅｄ＿ＣＡＳ＿ｅｘｐｏｓｅｄ＜−−ｒｅａｄ＿ｖｅｒｓｉｏｎ（ｓｅａｒｃｈ＿ｋｅｙ＿ｂａｓｅ，ｖｅｒｓｉｏｎ＿ｎｕｍｂｅｒ）
このような方法で、ユーザーは同一のユーザー定義の検索キーを提供して、バージョン化されたシーケンスの任意の検索可能なブロックを検索することができる。
【００４９】
クライアントが、検索キーベースおよび最新バージョン番号ではなく検索キーベース（例えばバージョン番号を除いた検索キーのすべてのフィールド）だけを思い出すほうがより簡単かもしれないので、システムは、オブジェクトを読み取る際最新のバージョン番号を決定する方式を用いることもできる。
【００５０】
例えば、典型的な実施においてバージョン番号が１で始まるとすれば、最新のバージョン番号を持つ正しい検索キーが決定されるまで、シーケンスを通した拡張検索が行われてもよい。したがって、読み取り／検索がブロックを見つけてはじめて、システムは、結合値８０６が「１」、「２」等の追加によって導き出されるすべてのブロックについて単純に繰り返すことによって、検索キーベースによりシーケンスに書き込まれた最新のバージョンを見つけることができる。失敗がバージョンＮ＋１に対して最初に発生した場合には、バージョンＮを持つブロックは成功裡に記憶された最後のブロックだったことになる。システムが最新のバージョンを見つけ出すに違いないので上述のＲＥＡＤ＿ＬＡＳＴ＿ＶＥＲＳＩＯＮ関数にとっても、およびシステムが書き込みのためにまだ使用されていない最低のバージョンでブロックを書き込むに違いないので上で説明したＷＲＩＴＥ＿ＮＥＷ＿ＶＥＲＳＩＯＮ関数にとっても、これは有用である。当然ではあるが、ある典型的な実施では、検索が起動時のみ行われるように、最新のバージョン番号をメモリに貯え、更新することができる。
【００５１】
上で説明した拡張検索処理は、すべてのバージョン番号の端から端まで連続して検索することによって行われるが一方、同一の機構を用いて、正しいバージョン番号を決定する前に読み取られたブロック数を低減する、最適化された検索の変形を実行することができる。例えば、上で説明した拡張可能な検索方式は、Ｏ（ｎ）、順番Ｎの検索可能なブロックをくまなく調べて、最新に書き込まれたブロックを見つける。該方式は、Ｏ（ｌｏｇ（ｎ））を用いることおよび後にバイナリーサーチが続く拡張検索を使用することによって最適化することができる。拡張検索は、最初の読み取りが例えば２pで失敗するまで、ブロック２0，２1，２2等を検索してもよい、ここで２p-1は成功しているものとする。したがって、最新のバージョンＮは、２p-1≦Ｎ＜２pのようになる。ここで、拡張検索はｐ〜ｌｏｇ（Ｎ）のステップを使用した。
【００５２】
範囲２p-1≦Ｎ＜２pが決定された後、システムは、Ｎを見つけるために間隔（２p-1，２p）でバイナリーサーチを行ってもよい。該バイナリーサーチは間隔長の対数を取り、該間隔長もｐ未満であり、その結果検索に対する全体的な対数のコストが生じる。例えば、システムは、最新バージョン４４を見つけるために、表３に提供される近似シーケンスに従ってブロックを読み取ってもよい。
【００５３】
【表３】
2010157204.tif 000005
【００５４】
表３に提供される例では、バージョン番号４４は成功したがバージョン番号４５は失敗した。したがって、バージョン番号４４はバージョン化されたシーケンスの最新に書き込まれたブロックに対応する。
【００５５】
なお、上述の拡張検索方式は、隣接して記憶されたシーケンス上で動作可能であることに留意されたい。例えばバージョン化されたシーケンスの検索可能なブロックのあるバージョンの削除によって、不明の長さの途切れが、使用されるバージョン番号に存在した場合、他の検索方式を用いて、検索可能なブロックの最新バージョンの自動的な検索をバージョン化されたシーケンスに適応させることができる。
【００５６】
上で説明したデータ編成構造を用いてデータを書き込みおよび読み取る以外の他のサービスは、データ削除を含んでいてもよい。本発明の１つの典型的な実施によれば、他のブロックが単一のブロックを参照できるように、該単一のブロックは削除要求を受け取ってすぐに削除されるべきでない。ユーザーが個々のブロックを削除できるようにすることは、重複排除によるダングリングポインタを発生させる可能性があるので、ガーベッジコレクション操作を用いてブロックの削除を行うことが望ましい。異なる種類のガーベッジコレクション方式の中で、修正済の参照計数動作には、該動作が２つの回収サイクルの間に書き込まれたブロック数に比例した作業を行うという点で利点がある。
【００５７】
図１を再び参照して、ＤＡＧデータ編成構造を用いた記憶システムでは、アプリケーションプログラムインターフェース（ＡＰＩ）が、１つまたは２つ以上のＤＡＧの削除すべき部分に印を付けてもよい。保持元に削除（すなわち現存しない）の印を付けるために、システムは、対応する保持元のユーザー定義の検索キーと同一の検索キーから導き出された内部キーで、検索可能な削除元１０８と名付けられたまたは同様な意味合いで削除元ブロック１０８と名付けられた、一種の検索可能なブロックを書き込んでもよい。ここで、該内部キーは内部削除キーと名付けることもできる。該内部削除キーは対応するユーザー定義の検索キーのハッシュ化によって導き出され、ＤＨＴに挿入されてもよい。図１では、例えば、削除元１０８は保持元ＳＰ１  １０２に関連付けられている。ガーベッジコレクションモジュール１６０は、現存の保持元から到達できないブロックすべてに削除の印を付けてもよい。例えば、図１では、保持元１０２が削除の印を付けられた結果として、ブロック１１２、１１０および１１４が削除の印を付けられる。なお、ブロック１０６は該ブロックを指す保持元を持たないので、ブロック１０６も削除の印を付けられることに留意されたい。対照的に、ブロック１１６は保持元ＳＰ２  １０４から到達できるので、該ブロック１１６は保持される。保持元１０４は一致削除元を持たないので、該保持元１０４は「現存（ａｌｉｖｅ）」している。
【００５８】
なお、根源の削除はダングリングポインタを生成しないので、ユーザーが根源を削除できるようにすることは許容されることに留意されたい。上述のごとく、検索可能なブロックにはコンテンツアドレスがない。通常、参照回数を保持することはカウンタを変更することを含んでいる。しかしながら、カウンタの変更は不変の記憶システムでは可能ではない。
【００５９】
この問題を扱う本発明の典型的な実施形態に係る削除元の１つの典型的な実施を示すために、ここで図９を参照して、検索可能な保持元ブロック９００および削除元ブロック９５０の表現を示している。なお、保持元および削除元は共に検索可能なブロックであるということを理解すべきであろう。ここで、表４に示すように、システムはＲＥＴＡＩＮ関数およびＤＥＬＥＴＥ関数を用いて保持元および削除元を次のように丁重に実行してもよい。
【００６０】
【表４】
2010157204.tif 000006
【００６１】
したがって、ＲＥＴＡＩＮ関数を実行するために、ユーザーは、ユーザー定義の検索キー９０２、および０または１以上のバイナリバイトのデータおよび／またはポインタとして働く任意の露出したＣＡのような任意の対応データコンテンツ９０６を提供する。同様に、ＤＥＬＥＴＥ関数を実行するために、ユーザーはユーザー定義の検索キーを提供する。表４のコードに示すように、連携は、ユーザー定義のキーから、保持元ブロックおよび削除元ブロックの内部保持キーおよび内部削除キーを丁重に導き出すことによって実現することができる。
【００６２】
例えば、図９に示すように、システムは、「保持」９０４をユーザー定義の検索キー９０２に追加することによって保持元９００を書き込んでもよい。システムは、ユーザー定義の検索キー９０２と「保持」ラベル９０４との両方を含んだ結合値９０８から内部保持キーを導き出してもよい。例えば、該内部保持キーは、上で説明したようにハッシュ関数を適用することによって導き出され、書き込み、検索、および削除のためにＤＨＴで用いられてもよい。同様に、システムは、「削除」９５２をユーザー定義の検索キー９０２に追加することによって削除元９５０を書き込んでもよい。システムは、同様に、ユーザー定義の検索キー９０２と「削除」ラベル９５２との両方を含んだ結合値９５４から内部削除キーを導き出してもよい。該内部削除キーは、該内部削除キーを対応するブロック９５０にマッピングできるＤＨＴに含まれていてもよい。なお、「保持」ラベルおよび「削除」ラベルは任意であり、該任意の異なるラベルを使用して、システムが保持元と削除元とを区別することを可能にすることに留意されたい。
【００６３】
図９に従って削除元９５０を書き込むことは、保持ブロック９００に削除の印を付けることである。例えば、図１のガーベッジコレクションモジュール１６０がガーベッジコレクション操作を始める場合、例えばＤＨＴの対応する内部削除キーを見つけることによって削除元に出会うと、モジュール１６０は、その目的に適ったので、保持元を削除してもよく、削除元そのものの削除を行ってもよい。このような方法で、例えば、削除元は対応する検索可能なブロックの削除を開始することができる。削除元を書き込むことは、不変の記憶システムの参照カウンタを調整する問題を解決する、というのは、該書き込みが、該ブロックが削除されるべきことを示す保持元の参照回数を調整するのと同じ効果を持っているからである。
【００６４】
なお、記憶システムの機構を簡単にするために、削除操作を、ブロックに削除の印を付けてユーザーがデータを書き込むことができない読み取り専用段階と、削除の印を付けられたブロックが再生されてユーザーが読み取りと書き込みの両方を行うことができる読み取り／書き込み段階と、の２つの段階に分割することができることに留意されたい。記憶空間再利用は、通常の読み取り／書き込み操作中バックグラウンドで行われてもよい。読み取り専用段階に入る前に、保持されるすべてのブロックは現存の保持元によって指し示されるべきである。読み取り専用段階を持っていることは、該読み取り専用段階が削除／印付け処理に対する書き込みの影響を排除するので、削除の実行を簡単なものにする。
【００６５】
典型的な実施では、削除は、ブロックを指すデータブロックのポインタの数を計数するように構成されたブロックごとの参照カウンタで実行することができる。参照カウンタを書き込みについてすぐに更新する必要はない。これが不変の記憶の利点である。その代りに、該参照カウンタは、以前の読み取り専用段階が処理されてから、カウンタ更新がインクリメントするようにすべてのポインタが書き込まれる読み取り専用段階で、その後更新される必要がある。書き込みの後に検出された各ポインタについては、該ポインタが指すブロックの参照カウンタがインクリメントされる。ポインタがすべて検出され、インクリメントが完了した後、ゼロに等しい参照カウンタを持つブロックがすべて削除の印を付けられる。さらに、既に削除の印を付けられたブロックによって指し示されたブロック（関連する削除元を持つ根源を含む）の参照カウンタは、ディクリメントされてもよい。その後、ディクリメントによってゼロになった参照カウンタを持つ任意のブロックは、削除の印を付けられてもよく、既に削除の印を付けられているブロックによって指し示されているブロックの参照カウンタは、ディクリメントされてもよい。付加のブロックに削除の印を付けることができなくなるまで、印付けおよびディクリメント処理が繰り返されてもよい。この時点で、読み取り専用段階は終わり、削除の印を付けられたブロックをバックグラウンドで取り除くことができる。ガーベッジコレクションを、参照計数を用いて上に例示したが、「マークアンドスイープ（ｍａｒｋ−ａｎｄ−ｓｗｅｅｐ）」のような他のガーベッジコレクション方法も用いることができる。もう１つの選択肢として、削除されるブロックではなく保持されるブロックが、ガーベッジコレクション操作で印を付けられてもよい。
【００６６】
ここで図２を参照して、上で開示された原理を適用した本発明の１つの典型的な実施に係る記憶媒体を含んだ連想記憶システムのデータを管理する方法２００が示されている。該方法２００は、記憶システムが不変の検索可能なブロックを書き込む要求をクライアントから受け取るステップ２０２で始まる。該要求は、上で説明したように、検索可能なブロックに含まれるユーザー定義の検索キーおよびデータ内容のような情報を含んでいてもよい。上述のごとく、該データ内容は、０または１以上のバイトのバイナリデータおよび／またはポインタとして働く露出したコンテンツアドレスを含んでいてもよい。
【００６７】
随意に、ステップ２０４で、記憶システムは、上で説明したように、バージョン番号を持つユーザー定義の検索キーを内部的に追加して、検索可能なブロックのバージョン化されたシーケンスの構成要素として検索可能なブロックを特定するように構成されてもよい。なお、システムは、例えば上で説明した拡張検索処理を用いることによって、検索キーに追加する正しいバージョン番号を決定できることに留意されたい。例えば、システムは、最新の正しいバージョン番号の直後に後続する、最初の失敗したバージョン番号を選択してもよい。表３に提供された例では、正しいバージョン番号は４５に相当するであろう。
【００６８】
ステップ２０６で、記憶システムは、上で説明したように、ユーザー定義の検索キーに基づいて内部保持キーを導き出すように構成することができる。例えば、上で説明したように、記憶システムは、検索キーにＳＨＡ−１のようなハッシュ関数を適用して内部保持キーを生成することができる。さらに、オプションのステップ２０４が実行される場合、該内部保持キーは、上で説明したように、ユーザー定義の検索キーおよびバージョン番号の両方に基づいていてもよい。
【００６９】
随意に、ステップ２０８で、記憶システムは、ＤＨＴルックアップを行って内部保持キーをＤＨＴのエントリと比較してもよい。その後、システムは、書き込みをサービスすべきかどうか判定してもよい。
【００７０】
例えば、システムは、内部保持キーがＤＨＴに存在するかどうかを判定するステップ２１０を随意に行ってもよい。該保持キーがＤＨＴに存在しない場合には書き込みがサービスされてもよく、方法はステップ２１２またはステップ２１４に進んでもよい。内部保持キーがＤＨＴのエントリであって、かつ要求のデータ内容がＤＨＴの保持キーエントリにマッピングされた値と同じでない場合、ユーザー定義の検索キー（またはバージョン化されたシーケンスが用いられている場合にはユーザー定義の検索キーとバージョン番号との組み合わせ）が既に異なるデータコンテンツに用いられているので、書き込みはステップ２１１で拒絶される。それゆえ、メッセージは、衝突を示しながらおよびユーザー定義の検索キー（またはユーザー定義の検索キーとバージョン番号との組み合わせ）の他の選択を促しながら、ユーザーに返されてもよい。保持キーがＤＨＴのエントリであって、要求のデータ内容がＤＨＴの保持キーエントリにマッピングされた値と同じ場合、書き込みがサービスされてもよく、方法はステップ２１２またはステップ２１４に進んでもよい。ここで、ユーザーはユーザー定義の検索キーで既にデータ内容を記憶しているので、２次記憶システムのコンテンツがユーザーの希望と一致している、よって書き込みが拒絶されたことを示す必要性はない。もう１つの選択肢として、保持キーがＤＨＴのエントリであって、要求のデータ内容がＤＨＴの保持キーエントリにマッピングされた値と同じ場合、書き込みがステップ２１１で拒絶されてもよく、ユーザー定義の検索キー（またはユーザー定義の検索キーとバージョン番号との組み合わせで）でデータ内容が既に記憶されたことを示しながら、メッセージがユーザーに返されてもよい。
【００７１】
随意に、ステップ２１２で、記憶システムは、ＤＨＴに検索可能なブロックおよび内部保持キーを挿入してもよい。例えば、内部保持キーがハッシュ関数を適用することによって導き出された場合、該内部キーはＤＨＴに記憶することができる。このような方法で、記憶システムは、上記のように、ＣＡＳシステムに既存の操作を用いて検索可能なブロックを実現することができる。
【００７２】
ステップ２１２と同時に起きてもよいステップ２１４で、記憶システムは、検索可能なブロックが規則的なブロックのＤＡＧを根づかせるように、不変の検索可能なブロックを記憶媒体に記憶してもよい。例えば、検索可能なブロックは、図１に関して上で説明した保持元の１つに対応していてもよい。ここで、上で説明したように、検索可能なブロックはデータ内容を含み、内部保持キーで場所の特定が可能である。さらに、各規則的なブロックのアドレスは、それぞれの規則的なブロックのコンテンツから導き出されたコンテンツアドレスであってもよい。
【００７３】
なお、規則的なブロックは、ＤＡＧを構築する際に、検索可能なブロックを記憶する前にユーザーによって記憶されたブロックに対応していてもよいことに留意されたい。さらに、各規則的なブロックのコンテンツアドレスは、書き込み後ユーザーに返されてもよい。例えば、ユーザーは、ＤＡＧを構築中、ポインタとしてコンテンツアドレスを用いてもよい。しかしながら、規則的なブロックとは対照的に、上記のように、検索可能なブロックのアドレスをユーザーに返す必要はないことにも留意されたい。さらに、ハッシュ関数がステップ２０６で内部検索キーを導き出すのに適用される場合、該ハッシュ関数は、規則的なブロックのコンテンツアドレスを導き出すハッシュキーの生成に用いられた関数と同じであってもよい。したがって、上に述べたＤＨＴは、内部保持キーおよびコンテンツアドレスを検索可能なブロックおよび規則的なブロックにそれぞれマッピングすることができる。
【００７４】
随意に、記憶システムは検索可能なブロックを用いて、データ内容の書き込みに加えて他のデータサービスを行うことができる。例えば、データ内容の読み取り操作および削除操作が、検索可能なブロックを用いて、ステップ２１６および２１８でそれぞれ行われてもよい。
【００７５】
図２の参照に続き図３を参照して、ステップ２１６で行われてもよい、本発明の典型的な実施形態に係るデータ内容を読み取る典型的な１つの方法３００が示されている。該方法３００は、記憶システムがデータ内容を読み取る要求を受け取ることができるステップ３０２で始まってもよい。上で説明したように、読み出し要求は、データ内容の書き込みに使用されるキーと同一のユーザー定義の検索キーを含んでいてもよい。随意に、該読み出し要求は、上で説明したように、バージョン化されたシーケンスの一部である検索可能なブロックのバージョンを検索するバージョン番号も含むことができる。
【００７６】
ステップ３０４で、記憶システムは、該要求の受け取りに応答して、ハッシュ関数をユーザー定義の検索キーに適用し、内部保持キーを導き出して得ることができる。
【００７７】
ステップ３０６で、システムは内部保持キーでＤＨＴルックアップを実行し、検索可能なブロックからデータ内容を検索し、該データ内容をユーザーに提供してもよい。
【００７８】
ここで図１および２の参照に続き図４を参照して、ステップ２１８で行われてもよい、上で説明した原理を用いた本発明の典型的な実施形態に係るデータ内容を削除する典型的な方法４００が示されている。該方法４００は、記憶システがデータ内容を削除する要求をユーザーから受け取ることができるステップ４０２で始まってもよい。上で説明したように、該削除要求は、コンテンツの書き込みに使用されるユーザー定義の検索キーを含んでいてもよい。
【００７９】
ステップ４０４で、記憶システムは、ユーザー定義の検索キーに基づいて内部削除キーを導き出すことができる。例えば、上で説明したように、ハッシュ関数をユーザー定義の検索キーに適用して内部削除キーを生成することができる。さらに、該内部削除キーは、削除元ブロックを対応する保持元ブロックから識別する、「削除」のようなラベルからも導き出すことができる。
【００８０】
ステップ４０６で、記憶システムは内部削除キーで削除元ブロックを書き込み、それぞれの検索可能な保持元に削除の印を付けるように構成されてもよい。例えば、図１に関して上で説明したように、削除元１０８を書き込み、検索可能なブロック１０２に削除の印を付けてもよい。
【００８１】
ステップ４０８で、ガーベッジコレクションモジュール１６０は、検索可能なブロックに関連したブロックにガーベッジコレクション操作を行ってもよい。例えば、ガーベッジコレクションモジュール１６０は、検索可能な保持元ブロック、削除元ブロック、および対応するＤＡＧのあらゆる到達できない規則的なブロックを削除するように構成されてもよい。
【００８２】
ここで図１および９の参照に続き図５を参照して、本発明の１つの典型的な実施形態に係る検索可能なブロックを用いた連想記憶システムのデータ内容を削除するより特定な方法５００が示されている。該方法５００は、記憶媒体に記憶された検索可能なブロックによって根づかされた規則的なブロックのＤＡＧを有するデータブロック群を提供することによって、ステップ５０２で始まってもよい。例えば、該ブロック群は、図１に関して上で説明したように編成されてもよい。例えば、各検索可能なブロックは、異なるユーザー定義の検索キー（または異なる検索キーとバージョン番号との組み合わせ）から導き出された内部保持キーで場所を特定することができる。さらに、各規則的なブロックは、上で説明したように、それぞれの規則的なブロックのコンテンツから導き出されたコンテンツアドレスで場所を特定することができる。
【００８３】
ステップ５０４で、記憶システムは、ＤＡＧの１つで編成されたデータコンテンツに削除の印を付ける要求を受け取ってもよい。削除要求は、データ内容が記憶されたＤＡＧを根づかせる検索可能なブロックを見つけるのに用いられる検索キーと同一の検索キーを含んでいてもよい。ここで、削除要求で提供される検索キーは、「第１の検索キー」と呼ばれてもよい。
【００８４】
ステップ５０６で、記憶システムは第１の検索キーに基づいて内部削除元キーを導き出してもよい。例えば、内部保持元がハッシュ関数を第１の検索キーおよび「保持」に適用することによって導き出される場合、内部削除元は、同一のハッシュ関数を第１の検索キーおよび「削除」に適用することによって導き出すことができる。
【００８５】
ステップ５０８で、記憶システムは、例えば図１および９に関して上で説明したように、内部削除キーを用いて記憶媒体に削除元ブロックを書き込んでもよい。
【００８６】
ステップ５１０で、記憶システムは、記憶媒体から、削除元ブロック、および第１の検索キーで場所を特定することができる検索可能なブロックを削除してもよい。例えば、上で説明したように、ガーベッジコレクションモジュール１６０は、削除元ブロック、対応する検索可能なブロック、およびＤＡＧの任意の対応する到達できない規則的なブロックを削除する指示として、削除元ブロックを用いてもよい。
【００８７】
なお、削除ステップ５１０を実行できる種々の方法があるということを理解すべきであろう。ここで図１および５の参照に続き図６を参照して、本発明の典型的な実施形態に係るＤＡＧに編成されたデータ内容の削除を実現する１つの方法６００が示されている。該方法６００は、記憶システムが、削除元、およびユーザー定義の検索キー（第１の検索キー）で場所を特定することができる検索可能なブロックに削除の印を付けることができるステップ６０２で始まってもよい。例えば、ガーベッジコレクションモジュール１６０は、削除元、および対応する検索可能な保持元に削除の印を付けてもよい。なお、本発明の１つの典型的な実施形態では、ガーベッジコレクション操作はユーザーによって開始されてもよいということを理解すべきであろう。例えば、ユーザーは、削除元が成功裡に書き込まれたというシステムからの指示を受け取った後、関連するＤＡＧのガーベッジコレクションを開始する要求を提出することができる。さらに、ガーベッジコレクション操作は、上で説明したように、関連する削除元を持つすべてのＤＡＧに適用することができる。
【００８８】
ステップ６０４〜６０６で、ガーベッジコレクションモジュール１６０は、削除の印を付けられない任意の検索可能なブロックから到達できない、すべての規則的なブロックに反復して削除の印を付ける。例えば、それを指すポインタがないすべてのブロックに削除の印を付けることができる、上で説明した反復削除方法を実行してもよい。なお、「到達できない（ｕｎｒｅａｃｈａｂｌｅ）」規則的なブロックとは、ＤＡＧポインタまたは一連のＤＡＧポインタを通して、削除の印を付けられていない任意の検索可能なブロックを規則的なブロックに接続するパスがないことを意味すると理解すべきであろう。例えば、図１を参照して、ブロックＥ  １１４は、検索可能な保持元１０４のような、削除の印を付けられていない任意の検索可能なブロックから到達できない。同様に、ブロックＦ  １１６は、削除の印を付けられていない検索可能なブロックであるブロック１０４から到達できる。
【００８９】
ステップ６０８で、ガーベッジコレクションモジュール１６０は、削除の印が付けられたブロックをすべて取り除くように構成されてもよい。しかしながら、当業者には、ここで説明した教示を考慮して、他のガーベッジコレクション法を実行してもよいことを理解すべきであろう。例えば、システムおよび方法は、削除されるブロックに印を付けるのではなく、保持されるブロックに印を付けるように変更されてもよい。この場合、印を付けられていないブロックをすべて記憶媒体から削除または取り除くことができる。
【００９０】
本明細書で上に説明したように、検索可能なブロックの使用は、データ内容を書き込み、読み取り、削除するようなデータサービスを提供する新規で効率的な方法を好都合に可能にする。さらに、上で説明したように、検索可能なブロックの使用は、保持元のコンテンツアドレスを記憶することを不要にする。さらに、たとえ保持元のアドレスが記憶されても、検索可能なブロックの使用は、ユーザーが保持元の前方一致検索を先験的に決定することを可能にし、記憶システムの作業と無関係に該アドレスを記憶することができる。例えば、ユーザーは前方一致検索とシステムとを同期させる必要がないし、システムがコンテンツアドレスを返すのを待つ必要もない。
【００９１】
システムおよび方法の好ましい実施形態（例示として意図したものであり、限定するものではない）を説明したが、当業者には、上記の教示に照らして変更および変形を行うことができることに留意されたい。したがって、添付の請求項によって略述されるような本発明の範囲と精神を逸脱することなく、開示された特定の実施形態において、変更がなされてもよいことを理解すべきであろう。このように、特許法により要求された詳細および特殊性で本発明の態様を説明したが、特許証によって保護された要求および所望のものは、添付の請求項で説明されている。
【符号の説明】
【００９２】
１０２  保持元
１０４  保持元
１０８  削除元
１６０  ガーベッジコレクションモジュール
２０２  ユーザー定義の検索キーを含む書き込みリクエストを受け取る
２０４  バージョン番号を持つユーザー定義の検索キーを内部的に追加する
２０６  検索可能なブロックのユーザー定義の検索キーに基づいて内部保持キーを導き出す
２０８  ＤＨＴルックアップテーブルを実行し内部保持キーをＤＨＴのエントリと比較する
２１０  保持キーが存在しないか、または保持キーおよび同一データ内容が存在するか？
２１２  内部保持キーおよびデータ内容をＤＨＴに挿入する
２１４  規則的なブロックのＤＡＧを根づかせ、検索可能なブロックをユーザー定義の検索キーで場所を特定することができるように、該検索可能なブロックを記憶媒体に記憶する
２１６  データ内容を読み取る
２１８  データ内容を削除する
２１１  書き込みを拒否する
３０２  ユーザー定義の検索キーを含む読み出し要求を受け取る
３０４  ユーザー定義の検索キーにハッシュ関数を適用し内部保持キーを導き出す
３０６  ＤＨＴルックアップテーブルを実行しデータ内容を受け取る
４０２  ユーザー定義の検索キーを含む削除要求を受け取る
４０４  内部削除キーを導き出す
４０６  内部削除キーで削除元ブロックを書き込み、検索可能なブロックに削除の印を付ける
４０８  ガーベッジコレクション操作を実行する
５０２  記憶媒体に記憶された検索可能なブロックによって根づかされた規則的なブロックのＤＡＧを有するデータブロック群を提供する
５０４  検索可能なブロックの１つに対応するユーザー定義の検索キーを含むデータ内容に削除の印を付ける要求を受け取る
５０６  ユーザー定義の検索キーに基づいて内部削除キーを導き出す
５０８  内部削除キーで削除元ブロックを書き込む
５１０  ユーザー定義の検索キーで場所を特定することができる検索可能なブロック、削除元ブロック、および対応するデータ内容を削除する
６０２  削除元、およびユーザー定義の検索キーで場所を特定することができるその検索可能なブロックに削除の印を付ける
６０４  削除の印を付けられていないあらゆる検索可能なブロックから到達できないすべての規則的なブロックに削除の印を付ける
６０６  付加の規則的なブロックに削除の印を付けることは可能か？
６０８  削除の印を付けられたブロックをすべて取り除く
７０２  ＣＡでないバイナリデータ
７０６  記憶された値
７５２  ユーザー定義の検索キー
７５４  ＣＡでないバイナリデータ
８０２  検索キーベース
８０４  バージョン番号
８０６  結合値
８０８  バイナリデータおよび／またはコンテンツアドレスを含むコンテンツ
８５２  バージョン化されたシーケンス
８５６  検索キーベース
８６４  バイナリデータ
８６６  バイナリデータ
８６８  コンテンツアドレス
８７０  コンテンツアドレス
８７２  ＤＡＧを形成する規則的なブロック
９０２  ユーザー定義の検索キー
９０４  「保持」
９０６  バイナリデータおよび／またはコンテンツアドレスを含むコンテンツ
９０８  結合値
９５２  「削除」
９５４  結合値
【図１】
2010157204.tif 000007
【図２】
2010157204.tif 000008
【図３】
2010157204.tif 000009
【図４】
2010157204.tif 000010
【図５】
2010157204.tif 000011
【図６】
2010157204.tif 000012
【図７】
2010157204.tif 000013
【図８】
2010157204.tif 000014
【図９】
2010157204.tif 000015
【外国語明細書】
2010157204.tif 000016
2010157204.tif 000017
2010157204.tif 000018
2010157204.tif 000019
2010157204.tif 000020
2010157204.tif 000021
2010157204.tif 000022
2010157204.tif 000023
2010157204.tif 000024
2010157204.tif 000025
2010157204.tif 000026
2010157204.tif 000027
2010157204.tif 000028
2010157204.tif 000029
2010157204.tif 000030
2010157204.tif 000031
2010157204.tif 000032
2010157204.tif 000033
2010157204.tif 000034
2010157204.tif 000035
2010157204.tif 000036
2010157204.tif 000037
2010157204.tif 000038
2010157204.tif 000039
2010157204.tif 000040
2010157204.tif 000041
2010157204.tif 000042
2010157204.tif 000043
2010157204.tif 000044
2010157204.tif 000045
2010157204.tif 000046
2010157204.tif 000047
2010157204.tif 000048
2010157204.tif 000049
2010157204.tif 000050
2010157204.tif 000051
2010157204.tif 000052
2010157204.tif 000053
2010157204.tif 000054
2010157204.tif 000055
2010157204.tif 000056
2010157204.tif 000057
2010157204.tif 000058
2010157204.tif 000059
2010157204.tif 000060
2010157204.tif 000061
2010157204.tif 000062
2010157204.tif 000063
2010157204.tif 000064
2010157204.tif 000065
2010157204.tif 000066
2010157204.tif 000067
2010157204.tif 000068
2010157204.tif 000069
2010157204.tif 000070
2010157204.tif 000071
2010157204.tif 000072
2010157204.tif 000073
2010157204.tif 000074
2010157204.tif 000075
2010157204.tif 000076