(57)【要約】【課題】【解決手段】１つの実施形態は、メモリにキーバリュー・ストアを記憶することを含む方法を提供する。アウトオブプレース動作は、明示セカンダリ・インデックスなしにガベージ・コレクション・トランザクションの存在下でストレージ・レイヤ上の動作の順序を強制することによって、動作の時系列順を維持するように実行される。【選択図】図１３
2021515299.tif 000002
【特許請求の範囲】
【請求項１】
時系列順のアウトオブプレース更新のためのシステムであって、
キーバリュー・ストアおよび命令を記憶するメモリ・デバイスと、
明示セカンダリ・インデックスなしにガベージ・コレクション・トランザクションの存在下でストレージ・レイヤ上の動作の順序を強制することによって、前記動作の時系列順を維持するように構成されるアウトオブプレース動作を実行するための前記命令を実行するように構成されるプロセッサと、
を備える、システム。
【請求項２】
前記動作が、更新、削除、および挿入動作を含む、請求項１に記載のシステム。
【請求項３】
前記プロセッサが、
前記ガベージ・コレクション・トランザクションの前の少なくとも１つの対象スロット内と、犠牲スロットからコピーされたキーの相対順序を同一に保持することによって、前記動作の前記時系列順を維持するように、ガベージ・コレクション・トランザクションを実行するための前記命令を実行するようにさらに構成される、請求項２に記載のシステム。
【請求項４】
前記プロセッサが、
前記ガベージ・コレクション・トランザクション処理前の他のスロット内のキーと比較して、犠牲スロットからコピーされたキーの相対順序を同一に維持するように、ガベージ・コレクション・トランザクションを実行するための前記命令を実行するようにさらに構成される、請求項２に記載のシステム。
【請求項５】
前記プロセッサが、
犠牲スロット内の実データ量を推定し、
少なくとも１つの対象スロットを識別し、
リカバリ・ログにガベージ・コレクション・トランザクションの始まりを記録し、
前記犠牲スロットから前記少なくとも１つの対象スロットに有効コンテンツをコピーし、
コピーされるレコードが更新である場合、前のバージョンを追跡するための廃棄標識を置き、
前記対象スロットにキーの新たな位置を記録するためにメモリ内インデックスを更新する、
ための前記命令を実行するようにさらに構成される、請求項１ないし４のいずれか一項に記載のシステム。
【請求項６】
前記廃棄標識が、前記犠牲スロット内の更新バックポインタが指し示す場所を指し示し、
前記対象スロット内の他のエントリのためのバックポインタが、前記犠牲スロットから前記対象スロット内に移動される有効データのための前記犠牲スロットを指し示し、
有効コンテンツが、実データ・レコードおよび実廃棄標識を含む、請求項５に記載のシステム。
【請求項７】
前記プロセッサが、
前記リカバリ・ログに前記ガベージ・コレクション・トランザクションの終わりを記録するための前記命令を実行するようにさらに構成される、請求項６に記載のシステム。
【請求項８】
時系列順のアウトオブプレース更新のための方法であって、
キーバリュー・ストアをメモリに記憶することと、
明示セカンダリ・インデックスなしにガベージ・コレクション・トランザクションの存在下でストレージ・レイヤ上の動作の順序を強制することによって、前記動作の時系列順を維持するように構成されるアウトオブプレース動作を実行することと、
を含む、方法。
【請求項９】
前記動作が、更新、削除、および挿入動作を含む、請求項８に記載の方法。
【請求項１０】
前記ガベージ・コレクション・トランザクションの前の少なくとも１つの対象スロット内と、犠牲スロットからコピーされたキーの相対順序を同一に保持することによって、前記動作の前記時系列順を維持するように、ガベージ・コレクション・トランザクションを実行することをさらに含む、請求項９に記載の方法。
【請求項１１】
前記ガベージ・コレクション・トランザクション処理前の他のスロット内のキーと比較して、犠牲スロットからコピーされたキーの相対順序を同一に維持するように、ガベージ・コレクション・トランザクションを実行することをさらに含む、請求項９に記載の方法。
【請求項１２】
犠牲スロット内の実データ量を推定することと、
少なくとも１つの対象スロットを識別することと、
リカバリ・ログにガベージ・コレクション・トランザクションの始まりを記録することと、
前記犠牲スロットから前記少なくとも１つの対象スロットに有効コンテンツをコピーすることと、
コピーされるレコードが更新である場合、前のバージョンを追跡するための廃棄標識を置くことと、
前記対象スロットにキーの新たな位置を記録するためにメモリ内インデックスを更新することと、
をさらに含む、請求項８ないし１１のいずれか一項に記載の方法。
【請求項１３】
前記廃棄標識が、前記犠牲スロット内の更新バックポインタが指し示す場所を指し示し、
前記対象スロット内の他のエントリのためのバックポインタが、前記犠牲スロットから前記対象スロット内に移動される有効データのための前記犠牲スロットを指し示し、
有効コンテンツが、実データ・レコードおよび実廃棄標識を含む、請求項１２に記載の方法。
【請求項１４】
前記リカバリ・ログに前記ガベージ・コレクション・トランザクションの終わりを記録することをさらに含む、請求項１３に記載の方法。
【請求項１５】
時系列順のアウトオブプレース更新のためのコンピュータ・プログラム製品であって、
処理回路によって読み出し可能であり、請求項８ないし１４のいずれか一項に記載の方法を実行するための前記処理回路による実行用命令を記憶する、コンピュータ可読記憶媒体を含む、コンピュータ・プログラム製品。
【請求項１６】
コンピュータ可読媒体上に記憶され、デジタル・コンピュータの内部メモリ内にロード可能なコンピュータ・プログラムであって、前記プログラムがコンピュータ上で実行されるときに、請求項８ないし１４のいずれか一項に記載の方法を実行するためのソフトウェア・コード部分を含む、コンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
発明は、概して、ログ構造のストレージ・システムを管理することを目的とする。特に、それは、ガベージ・コレクション中の障害を管理するために提供する。
【背景技術】
【０００２】
典型的なログ構造のストレージ・システムは、レコード・データを時間的順序で「ログ」に記憶する。これらの典型的なシステムは、挿入、更新、削除、読み出しなどの基本的なプリミティブ動作を可能にする。データのそれぞれの更新は、新たなレコードが「ログ」の末尾に挿入されるという結果になる。それぞれの削除は、廃棄（tombstone）オブジェクトがログの末尾に挿入されるという結果になる。さらに、バックグラウンド・ガベージ・コレクション・プロセスは、有効データを含まない空間を再要求するデータを圧縮する。
【０００３】
オブジェクトのその場限りの削除によって、空間のフラグメンテーション、およびそれにより不十分な空間利用がもたらされる。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
したがって、当技術分野において前述した問題に対処する必要がある。
【課題を解決するための手段】
【０００５】
第１の態様によれば、本発明は、時系列順のアウトオブプレース更新のためのシステムであって、キーバリュー・ストアおよび命令を記憶するメモリ・デバイスと、明示セカンダリ・インデックスなしにガベージ・コレクション・トランザクションの存在下でストレージ・レイヤ上の動作の順序を強制することによって、動作の時系列順を維持するように構成されるアウトオブプレース動作を実行するための命令を実行するように構成されるプロセッサと、を備える、システムを提供する。
【０００６】
さらなる態様によれば、本発明は、時系列順のアウトオブプレース更新のための方法であって、キーバリュー・ストアをメモリに記憶することと、明示セカンダリ・インデックスなしにガベージ・コレクション・トランザクションの存在下でストレージ・レイヤ上の動作の順序を強制することによって、動作の時系列順を維持するように構成されるアウトオブプレース動作を実行することと、を含む、方法を提供する。
【０００７】
さらなる態様から見ると、本発明は、時系列順のアウトオブプレース更新のためのコンピュータ・プログラム製品であって、処理回路によって読み出し可能であり、発明のステップを実行する方法を実行するための処理回路による実行用命令を記憶する、コンピュータ可読記憶媒体を含む、コンピュータ・プログラム製品を提供する。
【０００８】
さらなる態様から見ると、本発明は、コンピュータ可読媒体上に記憶され、デジタル・コンピュータの内部メモリ内にロード可能なコンピュータ・プログラムであって、上記プログラムがコンピュータ上で実行されるときに、発明のステップを実行するためのソフトウェア・コード部分を含む、コンピュータ・プログラムを提供する。
【０００９】
実施形態は、キーバリュー・ストレージ・システムにおける時系列順のアウトオブプレース更新に関する。１つの実施形態は、メモリにキーバリュー・ストアを記憶することを含む方法を提供する。アウトオブプレース動作は、明示セカンダリ・インデックスなしにガベージ・コレクション・トランザクション処理の存在下でストレージ・レイヤ上の動作の順序を強制することによって、動作の時系列順を維持するように実行される。
【００１０】
本発明の、これらのおよび他の特徴、態様および利点については、以下の説明、添付の特許請求の範囲および添付図面を参照して理解されることとなる。
【００１１】
本発明の実施形態が、ここで単なる例として添付図面を参照して説明される。
【図面の簡単な説明】
【００１２】
【図１】実施形態による、クラウド・コンピューティング環境を示す図である。
【図２】実施形態による、抽象モデル・レイヤのセットを示す図である。
【図３】実施形態による、ログ構造のストレージ・システムにおける遡及的スナップショットのためのネットワーク・アーキテクチャを示す図である。
【図４】実施形態による、図１のサーバまたはクライアントあるいはその両方に関連付けられ得る代表的なハードウェア環境を示す図である。
【図５】実施形態による、時系列順のアウトオブプレース更新のための例としてのキーバリュー・ストレージ・システムを示す図である。
【図６】実施形態による、ガベージ・コレクション（ＧＣ）・オブジェクト粒度の例を示す図である。
【図７】実施形態による、時系列順のＧＣブレイクの例を示す図である。
【図８】実施形態による、時系列順通りのＧＣの例を示す図である。
【図９】実施形態による、ＧＣ犠牲スロットを含むスロットの例を示す図である。
【図１０】実施形態による、ＧＣ対象スロットを含むスロットの例を示す図である。
【図１１】実施形態による、ＧＣの前の対象スロットおよび犠牲スロットの例としての初期状態を示す図である。
【図１２】実施形態による、ＧＣ後の対象スロットの例としての状態を示す図である。
【図１３】１つの実施形態による、キーバリュー・ストレージ・システムにおける時系列順のアウトオブプレース更新のためのプロセスについてのブロック図である。
【発明を実施するための形態】
【００１３】
多様な実施形態の説明は、例示の目的で提示されているが、網羅的であること、または開示される実施形態に限定することを意図するものではない。多くの修正および変形が、説明される実施形態の範囲から逸脱することなく当業者には明らかであろう。本明細書で使用される専門用語は、実施形態の原理、実用的な適用、もしくは市場で見出される技術に対する技術的改善を最もよく説明するため、または本明細書に開示される実施形態を他の当業者が理解可能にするために、選択された。
【００１４】
本開示は、クラウド・コンピューティングの詳細な説明を含むが、本明細書に列挙される教示の実施は、クラウド・コンピューティング環境に限定されないと予め理解される。むしろ、本発明の実施形態は、現在既知の、または後に開発される任意の他の種類のコンピューティング環境と併せて実施されることが可能である。
【００１５】
１つまたは複数の実施形態は、キーバリュー・ストレージ・システムにおける時系列順のアウトオブプレース更新に関する。１つの実施形態は、メモリにキーバリュー・ストアを記憶することを含む、方法を提供する。アウトオブプレース動作は、明示セカンダリ・インデックスなしにＧＣトランザクション処理の存在下でストレージ・レイヤ上の動作の順序を強制することによって、動作の時系列順を維持するように実行される。
【００１６】
クラウド・コンピューティングは、最小の管理労力またはサービス・プロバイダとの対話で迅速に供給され、リリースされ得る、構成可能なコンピューティング・リソース（例えば、ネットワーク、ネットワーク帯域幅、サーバ、処理、メモリ、ストレージ、アプリケーション、仮想機械（ＶＭ）、およびサービス）の共有プールへの便利なオンデマンド・ネットワーク・アクセスを可能にするためのサービス配信のモデルである。このクラウド・モデルは、少なくとも５つの特性、少なくとも３つのサービス・モデル、および少なくとも４つの配置モデルを含み得る。
【００１７】
特性は、以下の通りである。
オンデマンド・セルフサービス：クラウド消費者は、サービス・プロバイダと人との対話を必要とすることなく、必要に応じてかつ自動的に、サーバ時間およびネットワーク・ストレージなどのコンピューティング・ケイパビリティを一方的に供給し得る。
幅広いネットワーク・アクセス：ケイパビリティは、ネットワーク上で利用可能であり、異種シン・クライアントまたはシック・クライアント・プラットフォーム（例えば、携帯電話、ラップトップ、およびＰＤＡ）による使用を促進する標準的なメカニズムを通してアクセスされる。
リソースの共用：プロバイダのコンピューティング・リソースが、マルチテナント型モデルを使用して複数の消費者にサービスするためにプールされ、異なる物理リソースおよび仮想リソースが要求に従って動的に割り当ておよび再割り当てされる。消費者が、概して、提供されるリソースの正確な場所に対する制御または知識を有しないが、より抽象度の高いレベル（例えば、国、州、またはデータ・センタ）において場所を指定することが可能であり得るという点において、位置独立の意味がある。
スピーディな拡張性：ケイパビリティは、場合によっては自動的に、即座にスケール・アウトするようにスピーディかつ弾力的に供給され、即座にスケール・インするようにスピーディに解放され得る。消費者に対しては、供給に利用可能なケイパビリティが、多くの場合無制限であるように見え、いつでも任意の量で購入可能である。
サービスが計測可能であること：クラウド・システムは、サービスの種類（例えば、ストレージ、処理、帯域幅、アクティブな消費者アカウント）に適したある抽象度レベルにおいて計測ケイパビリティを活用することによって、リソース使用を自動的に制御し、最適化する。リソース使用量は、モニタリングされ、制御され、報告されてもよく、それによって利用サービスのプロバイダおよび消費者の両方に透明性をもたらし得る。
【００１８】
サービス・モデルは、以下の通りである。
サービスとしてのソフトウェア（ＳａａＳ）：消費者に提供されるケイパビリティは、クラウド・インフラ上で実行中のプロバイダのアプリケーションを使用する能力である。アプリケーションは、ウェブ・ブラウザなどのシン・クライアント・インターフェース（例えば、ウェブ・ベースの電子メール）を通して、様々なクライアント・デバイスからアクセス可能である。消費者は、限定された消費者固有アプリケーションの構成設定は例外である可能性があるが、ネットワーク、サーバ、オペレーティング・システム、ストレージ、または個々のアプリケーション・ケイパビリティですら含む、基礎となるクラウド・インフラを管理または制御しない。
サービスとしてのプラットフォーム（ＰａａＳ）：消費者に提供されるケイパビリティは、プロバイダによってサポートされるプログラミング言語およびツールを使用して生成された、消費者が作成または取得したアプリケーションを、クラウド・インフラ上に配置する能力である。消費者は、ネットワーク、サーバ、オペレーティング・システム、またはストレージを含む基礎となるクラウド・インフラを管理または制御しないが、配置されたアプリケーション、および、可能な限りアプリケーション・ホスティング環境構成に対して制御を行う。
サービスとしてのインフラ（ＩａａＳ）：消費者に提供されるケイパビリティは、処理、ストレージ、ネットワーク、ならびに消費者がオペレーティング・システムおよびアプリケーションを含み得る任意のソフトウェアを配置および実行することが可能な、他の基本コンピューティング・リソースを供給する能力である。消費者は、基礎となるクラウド・インフラを管理または制御しないが、オペレーティング・システム、ストレージ、配置されたアプリケーションに対して制御を行い、かつ可能な限り選択ネットワーキング・コンポーネント（例えば、ホスト・ファイアウォール）の限定的な制御を行う。
【００１９】
配置モデルは、以下の通りである。
プライベート・クラウド：クラウド・インフラは、組織のためだけに動作される。クラウド・インフラは、その組織または第三者によって管理されてもよく、構内または構外に存在し得る。
コミュニティ・クラウド：クラウド・インフラは、複数の組織によって共有され、共有の関心事（例えば、任務、セキュリティ要件、ポリシー、およびコンプライアンスの考慮事項）を有する特定のコミュニティをサポートする。クラウド・インフラは、組織または第三者によって管理されてもよく、構内または構外に存在し得る。
パブリック・クラウド：クラウド・インフラは、一般公衆または大きな業界団体に利用可能とされ、クラウド・サービスを販売する組織によって所有される。
ハイブリッド・クラウド：クラウド・インフラは、一意なエンティティのままであるが、データおよびアプリケーション・ポータビリティを可能にする標準化技術または独自技術（例えば、クラウド間のロード・バランシングのためのクラウド・バースティング）によって結合された、２つ以上のクラウド（プライベート、コミュニティ、またはパブリック）の混合物である。
【００２０】
クラウド・コンピューティング環境は、無国籍、低結合、モジュール性、および意味相互運用性を中心としたサービス指向型である。クラウド・コンピューティングの中心は、相互接続されたノードのネットワークを含むインフラである。
【００２１】
ここで図１を参照すると、例示的なクラウド・コンピューティング環境５０が示されている。図示するように、クラウド・コンピューティング環境５０は、クラウド消費者によって使用されるローカル・コンピューティング・デバイス、例えば、携帯情報端末（ＰＤＡ）もしくは携帯電話５４Ａ、デスクトップ・コンピュータ５４Ｂ、ラップトップ・コンピュータ５４Ｃ、または自動車コンピュータ・システム５４Ｎ、あるいはそれらの組合せが通信し得る、１つまたは複数のクラウド・コンピューティング・ノード１０を含む。ノード１０は、互いに通信し得る。それらは、上述のようなプライベート、コミュニティ、パブリック、もしくはハイブリッド・クラウド、またはそれらの組合せなどの、１つまたは複数のネットワーク内で物理的または仮想的にグループ化されてもよい（図示せず）。これによって、クラウド・コンピューティング環境５０が、インフラ、プラットフォーム、またはソフトウェア、あるいはそれらの組合せを、クラウド消費者がローカル・コンピューティング・デバイス上でリソースを維持する必要がないサービスとして提案することが可能となる。図２に示されるコンピューティング・デバイス５４Ａ〜Ｎの種類は、単なる例示であることを意図し、コンピューティング・ノード１０およびクラウド・コンピューティング環境５０は、任意の種類のネットワークまたはネットワーク・アドレス可能な接続あるいはその両方を経て（例えば、ウェブ・ブラウザを用いて）、任意の種類のコンピュータ化デバイスと通信し得ると理解される。
【００２２】
ここで図２を参照すると、クラウド・コンピューティング環境５０（図１）によって提供される機能抽象レイヤのセットが示されている。図２に示されるコンポーネント、レイヤ、および機能は、単なる例示であることを意図し、発明の実施形態は、それらに限定されないと、予め理解されるべきである。図示するように、以下のレイヤおよび対応する機能が、提供される。
【００２３】
ハードウェアおよびソフトウェア・レイヤ６０は、ハードウェアおよびソフトウェア・コンポーネントを含む。ハードウェア・コンポーネントの例は、メインフレーム６１、ＲＩＳＣ（Reduced Instruction Set Computer）アーキテクチャ・ベース・サーバ６２、サーバ６３、ブレード・サーバ６４、ストレージ・デバイス６５、ならびにネットワークおよびネットワーキング・コンポーネント６６を含む。いくつかの実施形態では、ソフトウェア・コンポーネントは、ネットワーク・アプリケーション・サーバ・ソフトウェア６７およびデータベース・ソフトウェア６８を含む。
【００２４】
仮想レイヤ７０は、仮想エンティティの以下の例、仮想サーバ７１、仮想ストレージ７２、仮想プライベート・ネットワークを含む仮想ネットワーク７３、仮想アプリケーションおよびオペレーティング・システム７４、ならびに仮想クライアント７５が提供され得る、抽象レイヤを提供する。
【００２５】
１つの例では、管理レイヤ８０は、後述する機能を提供し得る。リソース供給８１は、クラウド・コンピューティング環境内でタスクを実行するために利用される、コンピューティング・リソースおよび他のリソースの動的な調達を提供する。測定および価格設定８２は、リソースがクラウド・コンピューティング環境内で利用されるときにコスト追跡を提供し、これらのリソースの消費に対する課金または請求を提供する。１つの例では、これらのリソースは、アプリケーション・ソフトウェア・ライセンスを含み得る。セキュリティは、データおよび他のリソースについての保護だけでなく、クラウド消費者およびタスクについての本人確認を提供する。ユーザ・ポータル８３は、消費者およびシステム管理者にクラウド・コンピューティング環境へのアクセスを提供する。サービス・レベル管理８４は、要求されるサービス・レベルが満たされるように、クラウド・コンピューティング・リソース割り当ておよび管理を提供する。サービス水準合意（ＳＬＡ）計画および遂行８５は、ＳＬＡに従って将来の要件が予期されるクラウド・コンピューティング・リソースの事前配置および調達を提供する。
【００２６】
ワークロード・レイヤ９０は、クラウド・コンピューティング環境が利用され得る機能性の例を提供する。このレイヤから提供され得るワークロードおよび機能の例は、マッピングおよびナビゲーション９１、ソフトウェア開発およびライフサイクル管理９２、仮想クラスルーム教育配信９３、データ解析処理９４、トランザクション処理９５、ならびにキーバリュー・ストレージ・システム処理における時系列順のアウトオブプレース更新９６を含む。上述の通り、図２に関して説明した前述の例の全ては、単なる例示であり、発明は、これらの例に限定されない。
【００２７】
本明細書で説明される１つまたは複数の実施形態の全ての機能が、典型的には、処理システム３００（図３）または自律クラウド環境４１０（図４）によって実行されてもよく、それらは、ハードウェア・プロセッサとして、かつプログラム・コードのモジュールで、有形に具現化され得ると理解される。しかしながら、これは非リアルタイム処理のための場合である必要はない。むしろ、非リアルタイム処理については、本明細書で列挙される機能性が、図２に示されるレイヤ６０、７０、８０、および９０のうちのいずれかによって実行され／実施され、または可能にされ、あるいはその両方であり得る。
【００２８】
本開示は、クラウド・コンピューティングについての詳細な説明を含むが、本明細書に列挙される教示の実施は、クラウド・コンピューティング環境に限定されないと再確認する。むしろ、本発明の実施形態は、現在既知の、または後に開発される任意の種類のクラスタ化されたコンピューティング環境を用いて実施されてもよい。図３は、１つの実施形態による、ネットワーク・アーキテクチャ３００を示す。図３に示されるように、第１のリモート・ネットワーク３０４および第２のリモート・ネットワーク３０６を含む複数のリモート・ネットワーク３０２が提供される。ゲートウェイ３０１は、リモート・ネットワーク３０２と近接ネットワーク３０８との間に連結され得る。このネットワーク・アーキテクチャ３００の文脈において、ネットワーク３０４、３０６は、それぞれＬＡＮ、インターネットなどのＷＡＮ、公衆交換電話網（ＰＳＴＮ）、内線電話網などを含むがこれらに限定されない任意の形態を取り得る。
【００２９】
使用中、ゲートウェイ３０１は、リモート・ネットワーク３０２から近接ネットワーク３０８への入口ポイントとしての役割をする。このように、ゲートウェイ３０１は、ゲートウェイ３０１に到達する所与のデータ・パケットを方向付けすることが可能なルータ、および所与のパケットのためにゲートウェイ３０１内外に実際の経路を供給するスイッチとして機能し得る。近接ネットワーク３０８に連結される少なくとも１つのデータ・サーバ３１４がさらに含まれ、データ・サーバ３１４は、ゲートウェイ３０１を介してリモート・ネットワーク３０２からアクセス可能である。データ・サーバ３１４は、任意の種類のコンピューティング・デバイス／グループウェアを含み得ることに留意すべきである。各データ・サーバ３１４に連結されるのは、複数のユーザ・デバイス３１６である。そのようなユーザ・デバイス３１６は、デスクトップ・コンピュータ、ラップトップ・コンピュータ、手持ち式コンピュータ、プリンタ、または任意の他の種類のロジック包含デバイス、あるいはそれらの組合せを含み得る。ユーザ・デバイス３１１もまた、いくつかの実施形態ではネットワークのうちのいずれかに直接連結され得ることに留意すべきである。
【００３０】
例えば、ファクシミリ機械、プリンタ、スキャナ、ハード・ディスク・ドライブ、ネットワーク化記憶ユニットもしくはシステムまたはローカル記憶ユニットもしくはシステムあるいはその両方などの、周辺装置３２０または一連の周辺装置３２０が、ネットワーク３０４、３０６、３０８のうちの１つまたは複数に連結され得る。データベースまたは追加コンポーネントあるいはその両方が、ネットワーク３０４、３０６、３０８に連結される任意の種類のネットワーク要素とともに利用されてもよく、または任意の種類のネットワーク要素に統合されてもよいことに留意すべきである。本説明の文脈において、ネットワーク要素は、ネットワークの任意のコンポーネントを指してもよい。
【００３１】
いくつかの手法によれば、本明細書に説明される方法およびシステムは、ＩＢＭ（Ｒ）ｚ／ＯＳ（Ｒ）環境をエミュレートするＵＮＩＸ（Ｒ）システム、ＭＩＣＲＯＳＯＦＴ（Ｒ）ＷＩＮＤＯＷＳ（Ｒ）環境を仮想的にホストするＵＮＩＸ（Ｒ）システム、ＩＢＭ（Ｒ）ｚ／ＯＳ（Ｒ）環境をエミュレートするＭＩＣＲＯＳＯＦＴ（Ｒ）ＷＩＮＤＯＷＳ（Ｒ）システムなどの、仮想システムまたは１つもしくは複数の他のシステムをエミュレートするシステムあるいはその両方を、用いてまたはその上あるいはその両方で実施されてもよい。この仮想化またはエミュレーションあるいはその両方は、いくつかの実施形態ではＶＭＷＡＲＥソフトウェアの使用を通して実施され得る。
【００３２】
図４は、１つの実施形態による、図３のユーザ・デバイス４１６またはサーバ３１４あるいはその両方に関連付けられた代表的なハードウェア・システム４００の環境を示す。１つの例では、ハードウェア構成は、マイクロプロセッサなどの中央処理装置４１０、およびシステム・バス４１２を介して相互接続された、いくつかの他のユニットを有するワークステーションを含む。図４に示されるワークステーションは、ランダム・アクセス・メモリ（ＲＡＭ）４１４と、読み出し専用メモリ（ＲＯＭ）４１６と、ディスク・ストレージ・ユニット４２０などの周辺デバイスをバス４１２に接続するためのＩ／Ｏアダプタ４１８と、キーボード４２４、マウス４２６、スピーカ４２８、マイクロフォン４３２、またはタッチ・スクリーン、デジタル・カメラ（図示せず）などの他のユーザ・インターフェース・デバイス、あるいはそれらの組合せをバス４１２に接続するためのユーザ・インターフェース・アダプタ４２２と、ワークステーションを通信ネットワーク４３５（例えば、データ処理ネットワーク）に接続するための通信アダプタ４３４と、バス４１２をディスプレイ・デバイス４３８に接続するためのディスプレイ・アダプタ４３６と、を含み得る。
【００３３】
１つの例では、ＭＩＣＲＯＳＯＦＴ（Ｒ）ＷＩＮＤＯＷＳ（Ｒ）オペレーティング・システム（ＯＳ）、ＭＡＣ  ＯＳ、ＵＮＩＸ（Ｒ）ＯＳなどのオペレーティング・システムがその上に常駐し得る。１つの実施形態では、システム４００は、ＰＯＳＩＸ（Ｒ）ベースのファイル・システムを採用する。他の例は、記載されるもの以外のプラットフォームおよびオペレーティング・システム上でも実施され得ると理解されるものとする。そのような他の例は、オブジェクト指向プログラミング方法論とともに、ＪＡＶＡ（Ｒ）、ＸＭＬ、Ｃ、もしくはＣ＋＋言語、またはそれらの組合せ、あるいは他のプログラミング言語を用いて書かれたオペレーティング・システムを含み得る。複雑なアプリケーションを開発するためにますます使用されるようになっているオブジェクト指向プログラミング（ＯＯＰ）も使用され得る。ＭｉｃｒｏｓｏｆｔおよびＷｉｎｄｏｗｓ（Ｒ）は、米国、他の国、またはその両方におけるＭｉｃｒｏｓｏｆｔ  Ｃｏｒｐｏｒａｔｉｏｎの商標である。ＩＢＭおよびｚ／ＯＳは、Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｂｕｓｉｎｅｓｓ  Ｍａｃｈｉｎｅｓ  Ｃｏｒｐｏｒａｔｉｏｎの商標であり、世界中の多くの管轄区域において登録されている。ＵＮＩＸ（Ｒ）は、米国および他の国々におけるＯｐｅｎ  Ｇｒｏｕｐの登録商標である。Ｊａｖａ（Ｒ）およびＪａｖａ（Ｒ）に基づく商標およびロゴは全て、Ｏｒａｃｌｅまたはその関連会社あるいはその両方の商標または登録商標である。ＶＭｗａｒｅは、米国または他の管轄区域あるいはその両方におけるＶＭｗａｒｅ，Ｉｎｃ．またはその子会社の登録商標または商標である。
【００３４】
図５は、実施形態による、時系列順のアウトオブプレース更新のための例としてのキーバリュー・ストレージ・システム５００を示す。「ガベージ・コレクション」（ＧＣ）という用語は、ログ内の古くなったエントリによって占められている「ディスク空間」を再要求することをいう。例えば、レコードが挿入されるとき、エントリは、ログの末尾に追加される。同一レコードが削除されるとき、廃棄エントリが、ログの末尾に追加される。廃棄エントリとは、挿入によって生成されるディスク上のデータの元の位置をいう。元の挿入されたレコードによって占められたディスク空間に対して、ガベージ・コレクションが行われ得る（システムがより古いバージョンを維持していない限り）。古くなったデータは、削除または更新されたレコードの結果であり得る。更新は、ログ内に維持されているデータのより古いバージョンがもはや必要でないため、古くなったデータをもたらす。ログ構造のストアにおいては、あらゆる挿入、更新、または削除動作が、レコードがログの末尾に挿入されるという結果をもたらすことに留意されたい。
【００３５】
小さいオブジェクトのためのログ構造のストレージ・システム（例えば、ログ構造のキーバリュー・ストア）の場合、更新動作が、新たな書込み（追加専用）として扱われる。アプリケーション・プログラミング・インターフェース（ＡＰＩ）は、ＰＵＴ、ＧＥＴ、およびＤＥＬＥＴＥを含む。ＰＵＴ  ＡＰＩは、呼び出し元にアドレスを返す。ＤＥＬＥＴＥ  ＡＰＩは、廃棄標識の挿入をもたらす。削除されたオブジェクトによって占められていた空間は、ＧＣプロセスによって再要求される。オブジェクトのサイズは小さい（典型的には、数十バイトまたは数百バイト）。ＧＣの粒度は大きい（ＭＢまたはＧＢ単位）。
【００３６】
システム５００において、オブジェクト・インデックス・サービス（ＯＩＳ）５１０は、ＰＵＴ、ＧＥＴ、およびＤＥＬＥＴＥ動作を実行する。１つの実施形態では、ＰＵＴ動作のフォーマットは、ＰＵＴ（キー，値，＜前のアドレス＞）であり、これはアドレスを返す。１つの実施形態では、ＧＥＴ動作のフォーマットは、ＧＥＴ（アドレス）であり、これはキーバリュー・レコードを返す。１つの実施形態では、ＤＥＬＥＴＥ動作のフォーマットは、ＤＥＬＥＴＥ（アドレス）である。ＯＩＳ５１０からの出力または返される値は、オブジェクト・ストレージ・サービス（ＯＳＳ）５２０内に入力され、それがＧＣプロセス５３０のために使用される。１つの実施形態では、ＯＩＳ５１０およびＯＳＳ５２０は、併置されてもされなくてもよい。ＯＩＳ５１０およびＯＳＳ５２０は、併置される場合であっても、異なるプロセスの一部であり得る。１つの例としての実施形態では、キーは、ＯＳＳ５２０に公開される。
【００３７】
１つの実施形態では、ＧＣプロセス５３０は、トランザクションとして実行される。トランザクション処理は、情報処理を個々の、トランザクションという非可分操作に分割する。各トランザクションは、完結したユニットとして成功または失敗しなければならず、部分的にのみ完結することは決してない。
【００３８】
図６は、実施形態による、ＧＣオブジェクト粒度の例６００を示す。その場限りの削除によって、空間のフラグメンテーションおよび不十分な利用がもたらされる。ＧＣプロセス５３０（図５）の粒度＞＞オブジェクトの粒度である。スロットのＧＣプロセス５３０は、実オブジェクトに移転するように要求する。
【００３９】
図５に戻って、システム５００は、以下のように動作の時系列順を保持する。１つの実施形態では、時系列順は、明示セカンダリ・インデックスなしで、キーがストアに挿入／更新された順番でキーバリュー・ストアを反復する能力を提供する。ストアはアウトオブプレース更新されるため、全ての書込み／更新が、時系列順で実行され得る。データの時系列順は、「キャプチャ・フィードを変更」などの機能性を効率的にサポートするために重要である。例えば、「以降の全ての有効な変更をリスト化する」などのクエリをサポートするためである。そのようなクエリは、有効（即ち、削除されたレコードではない）のみをリスト化するべきであるが、時系列順でそれらをリスト化しなければならない。時系列順を保持することは、追加専用データ・ストアがログとして扱われている場合に、障害リカバリに対しても有用である。時系列順は、削除／更新動作をサポートしつつ、かつ有効レコードを保持するようにＧＣプロセス５３０を実行しつつ、維持することが困難である。１つの例では、問題は、無効なキーバリューのペアの従来型のＧＣ処理が、時系列順を破壊してデータを再順序付けするということである。１つの実施形態では、システム５００は、セカンダリ・インデックスを維持することなく、ＧＣプロセス５３０の存在下でキーの時系列順を維持するための仕組みを提供する。
【００４０】
１つの実施形態では、システム５００は、以下を実施することによってセカンダリ・インデックスなしで時系列順を提供する。システム５００は、動作が上位レイヤによって発行される順序で、書込み、更新、および削除を実行する。１つの実施形態では、システム５００は、ストレージ・レイヤにおいて、論理的に増加する順序（例えば、ログ構造の順序）で動作を実行することによって、この情報を非明示的に維持する。典型的なＧＣ処理は、この非明示的な順序を破壊する。
【００４１】
図７は、実施形態による、ＧＣの時系列順破壊の例７００を示す。図示するように、例７００は、インデックス７１０、ディスク上レイアウト７２０（ログ位置を示す）、マークされた穴を有するディスク上レイアウト７３０、および時系列順でないＧＣ後のログ位置７４０を含む。時系列順でないＧＣは、第１のスロット（０−４）をガベージ・コレクションすることを含み、位置１１の後の位置１に有効コンテンツを書き込むことが、非時系列の順序付けにつながる。これは、ログ位置７４０が、キー５、６、および１を伴う（時系列順ではない）位置１０、１１、および１２を有するという結果になる。
【００４２】
図８は、実施形態による、時系列順通りのＧＣの例８００を示す。図示するように、システム５００（図５）を用いて、時系列順のＧＣを処理した後、ログ位置８４０は、キー１、５および６の順番を含むログ位置０、１、および２についての結果を示す。順番通りのＧＣは、第１のスロット（０−４）をガベージ・コレクションすること、および順番を維持するために位置１において有効コンテンツを書き込むことを含む。内部の順序付けは、ＧＣの前の通りに犠牲スロットからコピーされたキーの相対順序を維持することを含む。外部の順序付けは、ＧＣの前の通りの他のスロット内の残りのキーと比較して、犠牲スロットからコピーされたキーの相対順序を同一に維持することを含む。
【００４３】
図９は、実施形態による、ＧＣ犠牲スロット９３０（スロット２）を含むスロットの例９００を示す。例９００は、スロット０  ９１０、スロット１  ９２０、およびスロット２  ９３０を含み、スロット２  ９３０は、ＧＣ犠牲スロットである。図１０は、実施形態による、ＧＣ対象スロット（スロット５１  ９４０）を含む例９００を示す。この例９００において、ＧＣ犠牲（スロット２  ９３０）は、実データがＧＣ対象スロット（スロット５１  ９４０）に移動される。例９００によって示される手法において、廃棄レコードは、＜廃棄標識，キー，前のアドレス＞のフォーマットを有する。前のアドレスは、キーについての最後の有効アドレスを参照する。データ・レコードは、「アドレスｘ」：＜データ，キー，値，前のアドレス（「アドレスｘ−ｎ」）＞のフォーマットを有し、ここで、ｘおよびｎが正の整数である。データ・レコードが移動されるとき、以下の新たなレコード、＜データ，キー，値，「アドレスｘ」＞、＜廃棄標識，キー，「アドレスｘ−ｎ」＞が挿入される。
【００４４】
図１１は、実施形態によるＧＣの前の対象スロット（スロット５１  １０３０）および犠牲スロット（スロット３  １０４０）の初期状態の例１０００を示す。例１０００は、スロット１  １０２０、スロット５１  １０３０（対象スロット）、スロット３  １０４０（犠牲スロット）、およびキーバリュー・インデックス１０１０を示す。スロット３  １０４０の位置１（Ｋ８）からスロット１  １０２０の位置４（ｋ８）へと示されるバックポインタ１０５０も示されている。図１２は、実施形態によるＧＣ後の対象スロット（スロット５１  １０３０）の状態の例１０００を示す。図示するように、キーバリュー・インデックス１０１０は、キーバリュー・インデックス１０１５に修正され、キーバリュー・インデックス１０１５は、Ｋ８、Ｋ９、およびＫ１０の、それぞれスロット５１：６、スロット５１：８、およびスロット５１：９への修正を示す。スロット５１  １０３０は、犠牲スロット（今は存在しないスロット３  １０４０、ここで、それは、位置７、８、および９についても同様である）を指し示す位置６（Ｋ８）における対象スロットを含む。追加的に、ＧＣ障害（例えば、未完了のトランザクション）後にクリーンアップが必要とされる。バックポインタ（前のアドレスを指し示す）１０５５は、スロット５１  １０３０の位置７からスロット１  １０２０の位置４へ指し示す。
【００４５】
１つの実施形態では、順序通りの時系列ＧＣ処理は、以下を含む。（１）システム５００（図５）は、犠牲スロット（例えば、スロット３  １０４０）を選択する。１つの実施形態では、犠牲スロット選択は、システム「費用対効果」（即ち、処理時間、帯域幅、メモリ使用率など）分析、連続的なスロット選択などに基づく。次に、（２）システム５００は、犠牲スロット内の実データ量を推定する。（３）対象スロット（例えば、スロット５１  １０３０）が、次いで識別される。前のスロットに空き容量がある場合、対象スロットは、犠牲スロットの前のスロットとして識別される。そうでない場合、より多くの有効コンテンツがコピーされる必要がある場合、システム５００は、空きスロットを対象スロットとして選択し（次の論理スロット識別子（ＩＤ）を割り当て）、スロット・チェーン内の犠牲スロットの前にそれを挿入する。（４）システム５００は、次いで、リカバリ・ログにＧＣトランザクションの始まりを記録する。（５）有効コンテンツは、次いで、犠牲スロットから対象スロットにコピーされる。これは、コピーされるレコードが更新である場合に廃棄標識を置くこと（元の挿入が無効なままであり、見えないようにする必要がある）を含み、廃棄標識は、犠牲スロット内の、更新バックポインタが指し示している場所を指し示す。ＧＣ対象スロット内のエントリについてのバックポインタは、犠牲スロットを指し示さなければならない。有効コンテンツは、「実データ・レコード」および「実廃棄標識」を含む。（６）次に、システム５００は、対象スロットにキーの新たな位置を記録するために、メモリ内インデックス（例えば、ａ  ｂ＋ツリーベースのインデックス）を更新する。（７）より有効なコンテンツがコピーされる必要がある場合、システム５００は、空きスロットを選択し、スロット・チェーン内の犠牲スロットの前にそれを挿入し、（３）に戻って続行する。（８）システム５００は、リカバリ・ログにＧＣトランザクションの終わりを記録する。
【００４６】
１つまたは複数の実施形態は、ガベージ・コレクタがデータの相対位置を再順序付けしないことを明示的に保証することによって、データの時系列順を提供する。したがって、システム５００は、ＧＣ中に再順序付けすることなく時系列順でデータを記憶する。１つまたは複数の実施形態は、セカンダリ・インデックスが必要とされないという点、およびＧＣがオフにされる必要がないという点において従来システムに対する利点を有し、それは、利用可能なストレージ容量の有効使用を改善するために提供される。
【００４７】
図１３は、１つの実施形態による、キーバリュー・ストレージ・システムにおける時系列順のアウトオブプレース更新のためのプロセス１１００についてのブロック図を示す。１つの実施形態では、プロセス１１００内のブロック１１１０は、メモリにキーバリュー・ストアを記憶することを含む。アウトオブプレース動作は、明示セカンダリ・インデックスなしにＧＣトランザクション処理の存在下でストレージ・レイヤ上の動作の順序を強制することによって、動作の時系列順を維持するようにプロセッサによって実行される。
【００４８】
１つの実施形態では、プロセス１１００では、アウトオブプレース動作は、更新、削除、および挿入動作を含む。１つの実施形態では、プロセス１１００は、ＧＣトランザクションの前の少なくとも１つの対象スロット内と、犠牲スロットからコピーされたキーの相対順序を同一に保持することによって動作の時系列順を維持するように、ＧＣトランザクションを実行することをさらに含み得る。
【００４９】
１つの実施形態では、プロセス１１００は、ＧＣトランザクション処理前の他のスロット内のキーと比較して、犠牲スロットからコピーされたキーの相対順序を同一に維持するように、ＧＣトランザクションを実行することを含み得る。１つの実施形態では、プロセス１１００は、犠牲スロット内の実データ量を推定することと、少なくとも１つの対象スロットを識別することと、リカバリ・ログにＧＣトランザクションの始まりを記録することと、犠牲スロットから少なくとも１つの対象スロットに有効コンテンツをコピーすることと、コピーされるレコードが更新である場合、廃棄標識を置くことと、対象スロットにキーの新たな位置を記録するためにメモリ内インデックスを更新することと、をさらに含み得る。１つの実施形態では、プロセス１１００において、廃棄標識は、犠牲スロット内の更新バックポインタが指し示す場所を指し示し、対象スロット内のエントリについてのバックポインタは、犠牲スロットを指し示し、有効コンテンツは、実データ・レコードおよび実廃棄標識を含む。
【００５０】
１つの実施形態では、プロセス１１００は、リカバリ・ログにＧＣトランザクションの終わりを記録することをさらに含み得る。
【００５１】
当業者によって理解されるように、本発明の態様は、システム、方法、またはコンピュータ・プログラム製品として具現化されてもよい。したがって、本発明の態様は、完全なハードウェア実施形態、完全なソフトウェア実施形態（ファームウェア、常駐ソフトウェア、マイクロコードなどを含む）、または本明細書で「回路」、「モジュール」、もしくは「システム」と全て概して呼ばれ得るソフトウェアおよびハードウェア態様を組み合わせる実施形態の形態を取ってもよい。さらに、本発明の態様は、その上で具現化されるコンピュータ可読プログラム・コードを有する、１つまたは複数のコンピュータ可読媒体において具現化されるコンピュータ・プログラム製品の形態を取ってもよい。
【００５２】
１つまたは複数のコンピュータ可読媒体の任意の組合せが、利用されてもよい。コンピュータ可読媒体は、コンピュータ可読信号媒体またはコンピュータ可読記憶媒体であってもよい。コンピュータ可読記憶媒体は、例えば、電子、磁気、光学、電磁気、赤外線、または半導体のシステム、装置、もしくはデバイス、または前述したものの任意の適当な組合せであってもよいが、これらに限定されない。コンピュータ可読記憶媒体のより具体的な例（非網羅的なリスト）は、以下の、１つまたは複数の配線を有する電気接続、ポータブル・コンピュータ・ディスケット、ハード・ディスク、ランダム・アクセス・メモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、消去可能プログラマブル読み取り専用メモリ（ＥＰＲＯＭもしくはフラッシュメモリ）、光ファイバ、ポータブル・コンパクト・ディスク読み取り専用メモリ（ＣＤ−ＲＯＭ）、光記憶デバイス、磁気記憶デバイス、または前述したものの任意の適当な組合せを含む。本文書の文脈において、コンピュータ可読記憶媒体は、命令実行システム、装置、もしくはデバイスによって、または関連して使用するプログラムを含み、または記憶し得る任意の有形媒体であってもよい。
【００５３】
コンピュータ可読信号媒体は、例えば、ベースバンドにおいて、または搬送波の一部として、そこに具現化されたコンピュータ可読プログラム・コードを有する伝搬データ信号を含んでもよい。そのような伝搬信号は、電磁気、光学、またはそれらの任意の適当な組合せを含むが、これらに限定されない多様な形態のいずれかを取ってもよい。コンピュータ可読信号媒体は、コンピュータ可読記憶媒体ではなく、命令実行システム、装置、もしくはデバイスによって、または関連して使用するプログラムを通信、伝搬、または移送することが可能な、任意のコンピュータ可読媒体であってもよい。
【００５４】
コンピュータ可読媒体上に具現化されるプログラム・コードは、無線、有線配線、光ファイバ・ケーブル、ＲＦなどを含むがこれらに限定されない任意の適当な媒体、または前述したものの任意の適当な組合せを用いて送信されてもよい。
【００５５】
本発明の態様のための動作を実行するコンピュータ・プログラム・コードは、Ｊａｖａ（Ｒ）、Ｓｍａｌｌｔａｌｋ、Ｃ＋＋などのオブジェクト指向プログラミング言語、および、「Ｃ」プログラミング言語または類似のプログラミング言語などの従来の手続き型プログラミング言語を含む、１つまたは複数のプログラミング言語の任意の組合せで書かれてもよい。プログラム・コードは、ユーザのコンピュータ上で完全に、ユーザのコンピュータ上で部分的に、スタンドアロン・ソフトウェア・パッケージとして、ユーザのコンピュータ上で部分的におよびリモート・コンピュータで部分的に、またはリモート・コンピュータもしくはサーバ上で完全に、実行してもよい。後者のシナリオでは、リモート・コンピュータは、ローカル・エリア・ネットワーク（ＬＡＮ）またはワイド・エリア・ネットワーク（ＷＡＮ）を含む任意の種類のネットワークを通して、ユーザのコンピュータに接続されてもよい。あるいは、接続は、（例えば、インターネット・サービス・プロバイダを使用してインターネットを通して）外部コンピュータに対して行われてもよい。
【００５６】
本発明の態様は、発明の実施形態による、方法、装置（システム）およびコンピュータ・プログラム製品のフローチャート図またはブロック図あるいはその両方を参照して、以下で説明される。フローチャート図またはブロック図あるいはその両方の各ブロック、ならびにフローチャート図またはブロック図あるいはその両方におけるブロックの組合せは、コンピュータ・プログラム命令によって実施され得ると理解されるものとする。コンピュータまたは他のプログラマブル・データ処理装置のプロセッサによって実行する命令が、フローチャートまたはブロック図あるいはその両方の１つまたは複数のブロックにおいて指定される機能／動作を実施する手段を生成するように、これらのコンピュータ・プログラム命令は、汎用コンピュータ、専用コンピュータ、または機械を製造するために他のプログラマブル・データ処理装置のプロセッサに提供されてもよい。
【００５７】
コンピュータ可読媒体に記憶される命令が、フローチャートまたはブロック図あるいはその両方の１つまたは複数のブロックにおいて指定される機能／動作を実施する命令を含む製品を製造するように、これらのコンピュータ・プログラム命令は、また、コンピュータ、他のプログラマブル・データ処理装置、または他のデバイスが特定の方法で機能するように指示することが可能な、コンピュータ可読媒体に記憶されてもよい。
【００５８】
コンピュータまたは他のプログラマブル装置上で実行する命令が、フローチャートまたはブロック図あるいはその両方の１つまたは複数のブロックにおいて指定される機能／動作を実施するためのプロセスを提供するように、コンピュータ・プログラム命令は、また、コンピュータ、他のプログラマブル装置、または他のデバイス上で実行されるべき一連の動作ステップに、コンピュータ実施プロセスを生成させるように、コンピュータ、他のプログラマブル・データ処理装置、または他のデバイス上にロードされてもよい。
【００５９】
図面中のフローチャートおよびブロック図は、本発明の様々な実施形態によるシステム、方法、およびコンピュータ・プログラム製品の考えられる実施のアーキテクチャ、機能性、および動作を示している。この点に関して、フローチャートまたはブロック図の各ブロックは、指定された論理機能を実施するための１つまたは複数の実行可能命令を含む、モジュール、セグメント、または命令の一部を表し得る。いくつかの代替的な実施において、ブロック内に記載された機能は、図面中に記載された順序以外で発生してもよい。例えば、連続して示される２つのブロックが、実際には、実質的に同時に実行されてもよく、または、ブロックが、関係する機能性次第で逆の順序で実行されることがあってもよい。ブロック図またはフローチャート図あるいはその両方の各ブロック、およびブロック図またはフローチャート図あるいはその両方におけるブロックの組合せが、指定された機能もしくは動作を実行し、または専用ハードウェアおよびコンピュータ命令の組合せを実行する専用ハードウェア・ベース・システムによって実施され得ることにも留意されたい。
【００６０】
特許請求の範囲における単数形の要素への参照は、明示的にそのように述べられない限り、「１つかつただ１つ」ではなく「１つまたは複数」を意味することを意図する。当業者に現在知られている、または後で知られることとなる上述の例示的実施形態の要素の全ての構造的および機能的等価物が、本特許請求の範囲によって包含されることを意図する。要素が「ｍｅａｎｓ  ｆｏｒ」または「ｓｔｅｐ  ｆｏｒ」という語句を用いて明示的に列挙されない限り、本明細書におけるいかなる特許請求の要素も、米国特許法第１１２条第６パラグラフの規定により解釈されるべきでない。
【００６１】
本明細書で使用される専門用語は、特定の実施形態のみを説明する目的のためであり、発明を限定することを意図するものではない。本明細書で使用される、単数形「ａ」、「ａｎ」、および「ｔｈｅ」は、文脈が特段明示していない限り、複数形も同様に含むことを意図するものである。「ｃｏｍｐｒｉｓｅｓ（備える）」または「ｃｏｍｐｒｉｓｉｎｇ（備えている）」という用語、あるいはその両方は、本明細書で使用されるとき、述べられた特徴、整数、ステップ、動作、要素、またはコンポーネント、あるいはそれらの組合せの存在を示しているが、１つまたは複数の他の特徴、整数、ステップ、動作、要素、コンポーネント、またはそれらの集合、あるいはそれらの組合せの存在または追加を排除するものではないと、さらに理解されるものとする。
【００６２】
下記の特許請求の範囲における全てのミーンズ・プラス・ファンクションまたはステップ・プラス・ファンクション要素の対応する構造、物質、動作、および均等物は、他の請求された要素と組み合わせて機能を実行するための任意の構造、物質、または動作を具体的に請求されるものとして含むことを意図する。本発明の説明は、例示および説明の目的で提示されているが、網羅的であるように、または開示された形態に発明を限定されることを意図するものではない。多くの修正および変形が、発明の範囲から逸脱することなく当業者には明らかである。実施形態は、発明の原理および実際の適用を最もよく説明するため、ならびに、考えられる特定の用途に適した多様な修正を伴う多様な実施形態についての発明を他の当業者が理解可能にするために、選択され説明された。
【図１】
2021515299.tif 000003
【図２】
2021515299.tif 000004
【図３】
2021515299.tif 000005
【図４】
2021515299.tif 000006
【図５】
2021515299.tif 000007
【図６】
2021515299.tif 000008
【図７】
2021515299.tif 000009
【図８】
2021515299.tif 000010
【図９】
2021515299.tif 000011
【図１０】
2021515299.tif 000012
【図１１】
2021515299.tif 000013
【図１２】
2021515299.tif 000014
【図１３】
2021515299.tif 000015
【手続補正書】
【提出日】令和3年4月13日(2021.4.13)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
時系列順のアウトオブプレース更新のためのシステムであって、
キーバリュー・ストアおよび命令を記憶するメモリ・デバイスと、
明示セカンダリ・インデックスなしにガベージ・コレクション・トランザクションの存在下でストレージ・レイヤ上の動作の順序を強制することによって、前記動作の時系列順を維持するように構成されるアウトオブプレース動作を実行するための前記命令を実行するように構成されるプロセッサと、
を備える、システム。
【請求項２】
前記動作が、更新、削除、および挿入動作を含む、請求項１に記載のシステム。
【請求項３】
前記プロセッサが、
前記ガベージ・コレクション・トランザクションの前の少なくとも１つの対象スロット内と、犠牲スロットからコピーされたキーの相対順序を同一に保持することによって、前記動作の前記時系列順を維持するように、ガベージ・コレクション・トランザクションを実行するための前記命令を実行するようにさらに構成される、請求項２に記載のシステム。
【請求項４】
前記プロセッサが、
前記ガベージ・コレクション・トランザクション処理前の他のスロット内のキーと比較して、犠牲スロットからコピーされたキーの相対順序を同一に維持するように、ガベージ・コレクション・トランザクションを実行するための前記命令を実行するようにさらに構成される、請求項２に記載のシステム。
【請求項５】
前記プロセッサが、
犠牲スロット内の実データ量を推定し、
少なくとも１つの対象スロットを識別し、
リカバリ・ログにガベージ・コレクション・トランザクションの始まりを記録し、
前記犠牲スロットから前記少なくとも１つの対象スロットに有効コンテンツをコピーし、
コピーされるレコードが更新である場合、前のバージョンを追跡するための廃棄標識を置き、
前記対象スロットにキーの新たな位置を記録するためにメモリ内インデックスを更新する、
ための前記命令を実行するようにさらに構成される、請求項１ないし４のいずれか一項に記載のシステム。
【請求項６】
前記廃棄標識が、前記犠牲スロット内の更新バックポインタが指し示す場所を指し示し、
前記対象スロット内の他のエントリのためのバックポインタが、前記犠牲スロットから前記対象スロット内に移動される有効データのための前記犠牲スロットを指し示し、
有効コンテンツが、実データ・レコードおよび実廃棄標識を含む、請求項５に記載のシステム。
【請求項７】
前記プロセッサが、
前記リカバリ・ログに前記ガベージ・コレクション・トランザクションの終わりを記録するための前記命令を実行するようにさらに構成される、請求項６に記載のシステム。
【請求項８】
時系列順のアウトオブプレース更新のための方法であって、
キーバリュー・ストアをメモリに記憶することと、
明示セカンダリ・インデックスなしにガベージ・コレクション・トランザクションの存在下でストレージ・レイヤ上の動作の順序を強制することによって、前記動作の時系列順を維持するように構成されるアウトオブプレース動作を実行することと、
を含む、方法。
【請求項９】
前記動作が、更新、削除、および挿入動作を含む、請求項８に記載の方法。
【請求項１０】
前記ガベージ・コレクション・トランザクションの前の少なくとも１つの対象スロット内と、犠牲スロットからコピーされたキーの相対順序を同一に保持することによって、前記動作の前記時系列順を維持するように、ガベージ・コレクション・トランザクションを実行することをさらに含む、請求項９に記載の方法。
【請求項１１】
前記ガベージ・コレクション・トランザクション処理前の他のスロット内のキーと比較して、犠牲スロットからコピーされたキーの相対順序を同一に維持するように、ガベージ・コレクション・トランザクションを実行することをさらに含む、請求項９に記載の方法。
【請求項１２】
犠牲スロット内の実データ量を推定することと、
少なくとも１つの対象スロットを識別することと、
リカバリ・ログにガベージ・コレクション・トランザクションの始まりを記録することと、
前記犠牲スロットから前記少なくとも１つの対象スロットに有効コンテンツをコピーすることと、
コピーされるレコードが更新である場合、前のバージョンを追跡するための廃棄標識を置くことと、
前記対象スロットにキーの新たな位置を記録するためにメモリ内インデックスを更新することと、
をさらに含む、請求項８ないし１１のいずれか一項に記載の方法。
【請求項１３】
前記廃棄標識が、前記犠牲スロット内の更新バックポインタが指し示す場所を指し示し、
前記対象スロット内の他のエントリのためのバックポインタが、前記犠牲スロットから前記対象スロット内に移動される有効データのための前記犠牲スロットを指し示し、
有効コンテンツが、実データ・レコードおよび実廃棄標識を含む、請求項１２に記載の方法。
【請求項１４】
前記リカバリ・ログに前記ガベージ・コレクション・トランザクションの終わりを記録することをさらに含む、請求項１３に記載の方法。
【請求項１５】
時系列順のアウトオブプレース更新のためのコンピュータ・プログラムであって、
コンピュータにより実行されることで、前記コンピュータに、請求項８ないし１４のいずれか一項に記載の方法を実行させる、コンピュータ・プログラム。
【請求項１６】
コンピュータの内部メモリ内にロード可能なコンピュータ・プログラムであって、前記プログラムがコンピュータ上で実行されることに応じて、前記コンピュータに請求項８ないし１４のいずれか一項に記載の方法を実行させる、コンピュータ・プログラム。
【国際調査報告】
2021515299.tif 000016
2021515299.tif 000017