(57)【要約】【課題】  データを管理するための方法を提供する。【解決手段】  本方法は、キーによって特定されるエントリに対する挿入操作又は更新操作を表す第１のデータ構造を準備すること、及び、分岐作成操作を表す第２のデータ構造を準備することであって、第２のデータ構造は分岐識別子及び分岐タイミング情報を格納する、ことと、読み取りタイムスタンプにおけるデータのバージョンを検索する要求を受信することと、データのそのバージョンを探し出すために第１のデータ構造及び第２のデータ構造を走査することと、要求されたタイムスタンプにおけるデータのバージョンによって開始する分岐を作成する要求を受信することと、それに応じて第２のデータ構造を更新することと、を含む。【選択図】  図１
2010503094.tif 000002
【特許請求の範囲】
【請求項１】
データを管理するための方法であって、
キーによって特定されるエントリへの挿入操作又は更新操作を表す第１のデータ構造を準備すること、及び、分岐作成操作を表す第２のデータ構造を準備することであって、前記第２のデータ構造は分岐識別子及び分岐タイミング情報を格納する、ことと、
読み取りタイムスタンプにおけるデータのバージョンを検索する要求を受信することと、
データのそのバージョンを探し出すために、前記第１のデータ構造及び前記第２のデータ構造を走査することと、
要求されたタイムスタンプにおけるデータのバージョンによって開始する分岐を作成する要求を受信することと、
それに応じて前記第２のデータ構造を更新することと、
を含む方法。
【請求項２】
前記第１のデータ構造はＢ木である、請求項１に記載の方法。
【請求項３】
所与のキーと関連する値を更新する要求を受信することと、前記第１のデータ構造を更新することとを含む、請求項１に記載の方法。
【請求項４】
前記更新することは、前記所与のキー及び関連するデータ並びに現在のタイムスタンプを持つ新規のエントリを追加することによって実施される、請求項３に記載の方法。
【請求項５】
前記キーは論理ブロック・アドレスである、請求項１に記載の方法。
【請求項６】
分岐を作成する前記要求は差し戻し操作であり、特定のタイムスタンプは差し戻し時間である、請求項１に記載の方法。
【請求項７】
分岐を探すことが、分岐タイミング情報を走査することを含む、請求項１に記載の方法。
【請求項８】
データ・ストレージ・ポリシーに応じて前記第１のデータ構造及び前記第２のデータ構造をリフレッシュすることを含む、請求項１に記載の方法。
【請求項９】
前記リフレッシュすることは、前記第２のデータ構造のエントリの粗分析を実施することを含む、請求項８に記載の方法。
【請求項１０】
前記リフレッシュすることは、前記第１のデータ構造及び前記第２のデータ構造のエントリの精密分析を実施することを含む、請求項８に記載の方法。
【請求項１１】
前記リフレッシュすることは、少なくとも１つの関連ウィンドウに応じて行われる、請求項８に記載の方法。
【請求項１２】
前記リフレッシュすることは、少なくとも１つのデータ・ストレージ粒度に応じて行われる、請求項８に記載の方法。
【請求項１３】
前記リフレッシュすることは、現時点からの時間経過に対応する多数のデータ・ストレージ粒度に応じて行われる、請求項８に記載の方法。
【請求項１４】
前記リフレッシュすることは、前記第１のデータ構造の１つのエントリと前記第１のデータ構造のエントリのサブセットとの間の関係に応じて行われる、請求項８に記載の方法。
【請求項１５】
前記リフレッシュすることは、前記第１のデータ構造の１つのエントリと前記第１のデータ構造のエントリ群との間の関係に応じて行われる、請求項８に記載の方法。
【請求項１６】
前記分岐タイミング情報は、分岐開始時間と分岐終了時間と前記要求されたタイムスタンプとを含む、請求項１に記載の方法。
【請求項１７】
ネットワーク上で顧客にサービスを提供する方法であって、前記サービスは、
ネットワーク上で、読み取りタイムスタンプにおけるデータのバージョンを検索する要求を受信することと、
データのそのバージョンを探し出すために第１のデータ構造及び第２のデータ構造を走査することであって、前記第１のデータ構造はキーによって特定されるエントリへの挿入操作又は更新操作を表し、前記第２のデータ構造は分岐作成操作を表し、前記第２のデータ構造は分岐識別子及び分岐タイミング情報を格納する、ことと、
前記読み取りタイムスタンプにおけるデータの前記バージョンを提供することと、
ネットワーク上で、要求されたタイムスタンプにおけるデータのバージョンによって開始する分岐を作成する要求を受信することと、
それに応じて前記第２のデータ構造を更新することと、
を含む、方法。
【請求項１８】
前記第１のデータ構造はＢ木である、請求項１７に記載の方法。
【請求項１９】
ネットワーク上で、所与キーと関連する値を更新する要求を受信することと、前記第１のデータ構造を更新することとを含む、請求項１７に記載の方法。
【請求項２０】
前記更新することは、前記所与のキー及び関連するデータ並びに現在のタイムスタンプを持つ新規のエントリを追加することによって実施される、請求項１８に記載の方法。
【請求項２１】
前記キーは論理ブロック・アドレスである、請求項１７に記載の方法。
【請求項２２】
分岐を作成する前記要求は差し戻し操作であり、前記特定のタイムスタンプは差し戻し時間である、請求項１７に記載の方法。
【請求項２３】
デジタル・コンピュータの内部メモリにロード可能なコンピュータ・プログラムであって、コンピュータ上で実行されたときに請求項１から請求項１６に記載される本発明を実現するように機能するためのソフトウェア・コード部分を含む、コンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データを管理するための方法に関する。
【背景技術】
【０００２】
データは、時間の経過と共に進化する場合がある。多くの用途において、データの以前のバージョンを取得する必要がある。１つの解決策は、継続的データ保護（ＣＤＰ）である。Ｐｅｒｒｙ他に付与された特許文献１及び特許文献２は、継続的データ保護についての従来技術の装置及び方法を説明している。
【０００３】
時間の経過に伴うデータの進化を追跡するために、種々のデータ構造が提案された。以下の論文、すなわち非特許文献１及び非特許文献２は、ＢＴ木及びＢＴＲ木として知られる２つのデータ構造を説明する。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】米国特許出願公開第２００５／００６６１１８号
【特許文献２】米国特許出願公開第２００５／０１９３２７２号
【非特許文献】
【０００５】
【非特許文献１】"The BT-Tree: A Branched and TemporalAccess Method", Jiang, Salzberg, Lomet, Barrena, Proceedings of the 26thVLDB Conference, 2000
【非特許文献２】"The BTR-Tree: Path-Defined Version-RangeSplitting in a Branched and Temporal Structure", Jiang, Salzberg, Lomet,Barrena, Symposium for Advances in Spatial and Temporal Databases, 2003
【発明の概要】
【発明が解決しようとする課題】
【０００６】
これらの分岐時間インデックス（branched temporal indexes）は、特定の前提が満たされる場合には維持することができる。第１の前提によれば、分岐時間インデックスのエントリは、タイムスタンプの増加する順序で挿入される。
【０００７】
さらに、これらのデータ構造は標準的なものではなく、これらのデータ構造の更新は、比較的複雑であり、データのみならずメタデータを複製することを含む。さらに、これらのデータ構造の維持には、参照カウンタを必要とする場合がある。
上述された問題を解決する必要性はますます高まっている。
【課題を解決するための手段】
【０００８】
データを管理するための方法は、キーによって特定されるエントリへの挿入操作又は更新操作を表す第１のデータ構造を準備すること、及び、分岐作成操作を表す第２のデータ構造を準備することであって、第２のデータ構造は分岐識別子及び分岐タイミング情報を格納する、ことと、読み取りタイムスタンプにおけるデータのバージョンを検索する要求を受信することと、データのそのバージョンを探し出すために第１のデータ構造及び第２のデータ構造を走査することと、要求されたタイムスタンプにおけるデータのバージョンによって開始する分岐を作成する要求を受信し、それに応じて第２のデータ構造を更新することと、を含む。
【０００９】
好ましくは、本発明は、Ｂ木である第１のデータ構造を提供する。
好ましくは、本発明は、所与のキーと関連する値を更新する要求を受信することと、第１のデータ構造を更新することとを含む方法を提供する。
好ましくは、本発明は、所与のキー及び関連するデータ並びに現在のタイムスタンプを持つ新規のエントリを追加することによって更新が実施される方法を提供する。
好ましくは、本発明は、キーが論理ブロック・アドレスである方法を提供する。
好ましくは、本発明は、分岐を作成する要求が差し戻し操作（revertoperation）であり、特定のタイムスタンプが差し戻し時間（revert-to time）である方法を提供する。
好ましくは、本発明は、分岐を探すことが分岐タイミング情報を走査することを含む方法を提供する。
好ましくは、本発明は、データ・ストレージ・ポリシーに応じて第１のデータ構造及び第２のデータ構造をリフレッシュすることを含む方法を提供する。
好ましくは、本発明は、リフレッシュすることが第２のデータ構造のエントリの粗分析（coarseanalysis）を実施することを含む方法を提供する。
好ましくは、本発明は、リフレッシュすることが第１のデータ構造及び第２のデータ構造のエントリの精密分析（fine analysis）を実施することを含む方法を提供する。
好ましくは、本発明は、リフレッシュすることが少なくとも１つの関連ウィンドウ（relevancywindow）に応じて行われる方法を提供する。
好ましくは、本発明は、リフレッシュすることが少なくとも１つのデータ・ストレージ粒度（datastorage granularity）に応じて行われる方法を提供する。
好ましくは、本発明は、リフレッシュすることが、現時点からの時間経過に対応する多数のデータ・ストレージ粒度に応じて行われる方法を提供する。
好ましくは、本発明は、リフレッシュすることが、第１のデータ構造のエントリと第１のデータ構造のエントリのサブセットとの間の関係に応じて行われる方法を提供する。
好ましくは、本発明は、リフレッシュすることが、第１のデータ構造の１つのエントリと第１のデータ構造のエントリ群との間の関係に応じて行われる方法を提供する。
好ましくは、本発明は、分岐タイミング情報が、分岐開始時間と分岐終了時間と要求されたタイムスタンプとを含む方法を提供する。
【図面の簡単な説明】
【００１０】
【図１】本発明の１つの実施形態による、データを管理するためのシステムを示す。
【図２】本発明の１つの実施形態による、ステージング操作及びデステージング操作の例示的なシーケンスを示す。
【図３】本発明の別の実施形態による、データを管理するためのシステムを示す。
【図４】本発明の別の実施形態による、ステージング操作及びデステージング操作の例示的なシーケンスを示す。
【図５】本発明の更なる実施形態による、データを管理するためのシステムを示す。
【図６】本発明の別の実施形態による、読み書きステージング操作及びデステージング操作の例示的なシーケンスを示す。
【図７】本発明のさらに別の実施形態による、読み書きステージング操作及びデステージング操作の例示的なシーケンスを示す。
【図８】本発明の更なる実施形態による、読み書きステージング操作及びデステージング操作の例示的なシーケンスを示す。
【図９】本発明のさらにまた別の実施形態による、読み書きステージング操作及びデステージング操作の例示的なシーケンスの図である。
【図１０】本発明の１つの実施形態による、第１のデータ構造の一部及び第２のデータ構造の一部を示す。
【図１１】本発明の１つの実施形態による、更新操作及び差し戻し操作の例示的なシーケンスを示す。
【図１２】本発明の１つの実施形態による、更新操作及び差し戻し操作の例示的なシーケンスを示す。
【図１３】本発明の別の実施形態による、更新操作及び差し戻し操作の例示的なシーケンスを示す。
【図１４】本発明の１つの実施形態による、データ・バージョンを取得するための方法を示す。
【図１５】本発明の１つの実施形態による粗分析を示す。
【図１６】本発明の１つの実施形態による全体精密分析を示す。
【図１７】本発明の１つの実施形態による全体精密分析を示す。
【図１８】本発明の１つの実施形態による、データを管理するための方法を示す。
【発明を実施するための形態】
【００１１】
本発明は、添付の図面と併せて、以下の詳細な説明から、より完全に理解され認識される。
【００１２】
本発明は、データの多数のバージョンを格納及び取得するための方法、システム、及びコンピュータ・プログラムを提供する。
【００１３】
本発明の１つの実施形態によれば、データ及びデータと関連するメタデータが提供される。データは、データの少なくとも１つの現在のバージョンと、データの少なくとも１つの以前のバージョンとを含むことができる。メタデータは、２つのデータ構造に編成されることが好ましい。第１のデータ構造は、データ更新操作に関する情報を含む。第１のデータ構造は、拡張されたＢ木データ構造であることが好ましい。第２のデータ構造は、差し戻し操作に関する情報を含む（さらにクローン作成情報を含む場合もある）。第２のデータ構造は、分岐テーブルとも呼ばれる。これらの２つのデータ構造が用いられるときに、効率的なデータ更新操作、検索操作、及び差し戻し操作を適用することが可能となる。
【００１４】
好ましくは、更新操作は、Ｂ木データ構造の中のエントリによって表され、一方、差し戻し操作は、第２のデータ構造の中のエントリによって表される。検索操作は、要求されたデータを見つけるために、両方のデータ構造を調べることを含むものとすることができる。
【００１５】
本発明の１つの実施形態によれば、第１のデータ構造は、第２のデータ構造よりはるかに大きい。第１のデータ構造のエントリは、書き込み操作ごとに、又はデステージング操作（destage operation）ごとに、（書き込み又はデステージングのアドレスに応じて）割り当てられ、一方、第２のデータ構造のエントリは、差し戻し操作ごとに割り当てられる。典型的には、差し戻し操作の数は、書き込み操作の数よりはるかに小さい。差し戻し操作によって開始された分岐は、書き込み／デステージング操作に応じて、第１のデータ構造の中の多数のエントリと関連付けることができる。２つの異なるデータ構造を用いることによって、第１のデータ構造（Ｂ木）の更新を簡略化することができ、標準的なＢ木更新アルゴリズムを用いることができる。好ましくは、Ｂ木は、タイムスタンプの順序から外れたエントリを挿入することによって更新することができる。
【００１６】
時間の経過に伴うデータの進化、特に更新操作及び差し戻し操作は、グラフによって表される。グラフは、１つ又は複数の分岐を含むものとすることができるが、（親分岐とも呼ばれる）最初の分岐は、更新操作の第１のシーケンスを示す。各々の差し戻し操作は、多数のエントリを含む場合がある分岐を開始し、各々のエントリは、キーへの更新操作を表す。１つの分岐は、新規の差し戻し操作が実行されたときに終了することができる。グラフは、第１のデータ構造及び第２のデータ構造の内容を示す。
【００１７】
好ましくは、２つのデータ構造は、継続的データ保護（ＣＤＰ）システムに実装され、それによりＣＤＰシステムは、格納されたデータを特定の時点から容易に再構築することができる。差し戻し操作は迅速であり、他の差し戻し操作の実行を妨げない。
【００１８】
メタデータ及びデータは、検索操作、更新操作、及び差し戻し操作の際には複製されない。このことは、データ及びメタデータのサイズを大きく低減する。好ましくは、分岐間におけるデータの共有は最大となり、参照カウントを回避することができる。
【００１９】
本発明の１つの実施形態によれば、いかなる時点においてもアクティブな分岐が１つだけ存在することができる。本発明の別の実施形態によれば、多数のアクティブな分岐が同時に存在することができる。データを管理するのに必要なメタデータは、前者の場合と後者の場合とで異なるものとすることができる。
【００２０】
本発明の１つの実施形態によれば、第１のデータ構造の各々のエントリは、論理ブロック・アドレス（Ｌ）と、書き込み操作が実行された時点を表す書き込みタイムスタンプ（ＷＴＳ）と、論理ブロック・アドレスと関連する物理アドレス（Ｐ）と、を含む。
【００２１】
本発明の別の実施形態によれば、第１のデータ構造の各々のエントリは、論理ブロック・アドレス（Ｌ）と、現在のデータを上書きする後続の書き込み操作が実行された時点を表す上書きタイムスタンプ（ＯＴＳ）と、論理ブロック・アドレスと関連する物理アドレス（Ｐ）と、を含む。
【００２２】
本発明の別の実施形態によれば、各々のエントリは、論理ブロック・アドレスと、オフセットと、長さと、を含む。
【００２３】
好ましくは、論理ブロック・アドレスは、第１のデータ構造にアクセスするのに用いられるキーを形成する。好ましくは、各々のエントリは、特に多数のアクティブな分岐が同時に存在することができる場合には、分岐識別子（ＢＩＤ）も含む。
【００２４】
第１のデータ構造には、キーによってアクセスすることができる。１つの実施形態においては、キーは、論理ブロック・アドレスを含む。強化されたキーは、ＢＩＤ及び／又はタイムスタンプを含むこともできる。
【００２５】
本発明の別の実施形態によれば、第２のデータ構造の各々のエントリは、分岐識別子（ＢＩＤ）と、分岐開始時間と、分岐終了時間と、分岐差し戻し時間と、を含む。好ましくは、各々のエントリは、親分岐の分岐識別子と、分岐識別子も含む。
【００２６】
更新要求は、キーと、書き込まれるデータと、を含む。好ましくは、多数のアクティブな分岐が同時に共存しうる場合には、強化されたキーが必要となることがある。１つの実施形態について、書き込み操作は、第１のデータ構造を更新することと、そのデータを、キーに含まれる論理ブロック・アドレスと関連付けられた物理ブロック・アドレス（Ｐ）に書き込むこととを含む。
【００２７】
差し戻し要求は、分岐開始時間（これは、差し戻し要求が実行された時間とすることも、差し戻し要求が受信された時間とすることもできる）と、差し戻し時間と、必要に応じて親分岐識別子と、を含む。好ましくは、所与の時点においてアクティブな分岐が１つしか存在できない場合には、親分岐識別子を設ける必要はない。差し戻し操作は、第２のデータ構造を更新することを含む。
【００２８】
検索要求は、キーと、検索タイムスタンプと、を含む。多数のアクティブな分岐が同時に共存しうる場合には、強化されたキーが必要となることがある。検索操作は、所与の検索タイムスタンプにおいて有効なエントリを探すことを含む。これは、適切なエントリが見つかるか、又は、親を持たない分岐が見つかり、未検出との回答が得られるまで、要求された分岐から開始し、その親分岐に続くなどといった通常のＢ木検索のシーケンスを含むことができる。
【００２９】
本発明の種々の実施形態によれば、データ・ストレージ・ポリシーを適用することができる。第１の例示的なデータ・ストレージ・ポリシーは、関連ウィンドウを定める。関連ウィンドウ内にあるタイムスタンプにのみ差し戻すことが可能である。関連ウィンドウ内においてアクセス可能なデータと、そのデータに関連するメタデータとは、維持されるべきであり、一方、関連ウィンドウにおいてアクセス可能でないデータと、関連するメタデータとは、削除することができる。タイムスタンプが関連ウィンドウの外部にあるデータが、差し戻し操作及び検索操作のシーケンスの結果としてアクセス可能となることもあるので、データ及び関連するメタデータを削除する前に、検索操作及び差し戻し操作に対するそのデータのアクセス可能性がチェックされることに留意されたい。さらに別のデータ・ストレージ・ポリシーは、多数の関連ウィンドウを定めることができる。
【００３０】
好ましくは、データの全ての古いバージョンが格納されるとは限らない。例えば、データ・ストレージ粒度を定めることができる。データ・ストレージ粒度は、データの１つのバージョンによって表される（又は、データのいかなるバージョンによっても表されない）期間を定める。その期間中にデータの多数のバージョンが生成された場合には、これらのバージョンのうちの１つが格納される。本発明の別の実施形態によれば、データ・バージョンは、イベントが生成されたいずれかのタイムスタンプについて格納されることに留意されたい。好ましくは、イベントが生成されたいずれかのタイムスタンプについて１つのバージョンが格納される。
【００３１】
本発明の１つの実施形態によれば、データ・ストレージ・ポリシーは、多数のデータ・ストレージ粒度を定める。典型的には、データ・ストレージ粒度は、データ・バージョンが古くなるに従って粗くなる。データ・ストレージ粒度は、各々の関連ウィンドウごとに固定することができるが、必ずしもそうしなくてもよい。
説明を簡単にするために、単一の関連ウィンドウが定められると仮定する。
【００３２】
本発明の１つの実施形態によれば、データ・ストレージ・ポリシーは、差し戻し操作及び検索操作のいくつかのシーケンスの後で、どのエントリがアクセス可能であるかを判定する。種々のアクセス可能性検出プロセスを適用することができ、各々のプロセスは、範囲と複雑度（又は実行時間）との間のトレードオフを与える。
【００３３】
好ましくは、アクセス可能性検出プロセスは、粗分析と精密分析とを含む。好ましくは、粗分析は分岐全体を処理することを含み、一方、精密分析はエントリを処理することを含む。
【００３４】
粗分析は、分岐を除去すること、又は、分岐を統合することを含むことができる。粗分析は、完全に関連ウィンドウの外部にあり、その分岐のいずれかの子の最新の差し戻し時間において開始する分岐終了セクションを、除去することを含むこともできる。
【００３５】
好ましくは、分岐は、完全に関連ウィンドウの外部にあり、関連する子分岐を持たない場合には、除去される。分岐が、完全に関連ウィンドウの外部にあるが、子分岐を１つ有する場合には、その分岐と子分岐とは、その分岐を子分岐に移動させることによって統合することができる。
【００３６】
粗分析は第２のデータ構造を走査することを含み、一方、精密分析は第１のデータ構造と第２のデータ構造の両方を走査することを含む。
精密分析は、１度に第１のデータ構造の１ページを走査し、キーを１つずつ走査することが好ましい。単一のキーと関連する分岐は、１つのエントリずつ走査される。
【００３７】
本発明の１つの実施形態によれば、精密分析には少なくとも２つのタイプが存在する。第１のタイプは全体精密分析と呼ばれ、他のタイプは局所精密分析と呼ばれる。所与のキーについて、全体精密分析は、第１のデータ構造のエントリのすべてをこのキーを用いて走査できる可能性があり、一方、局所精密分析は、これらのエントリの一部（サブセット）のみを走査する。
【００３８】
好ましくは、局所精密分析は、アクセス可能なエントリの数がアクセス不可能なエントリの数を超えることを保証することができる。これらの上述された分析に代わる分析を適用できることに留意されたい。
【００３９】
好ましくは、全体精密分析は、特定のキーと特定の分岐との組み合わせの各々について、その特定の分岐の子孫分岐における更新操作を表すエントリを再帰的に走査することによって、この組み合わせを含む第１のデータ構造のエントリがアクセス可能なエントリであるかどうかをチェックする。
【００４０】
好ましくは、局所精密分析は、特定のキーと特定の分岐との組み合わせの各々について、その特定の分岐の子分岐における更新操作を表すエントリを走査することによって、この組み合わせを含む第１のデータ構造のエントリがアクセス可能なエントリであるかどうかをチェックする。
アクセス不可能なエントリは削除することができるが、現れたエントリは残すべきである。
【００４１】
好ましくは、各々の分岐について第１のデータ構造内のエントリの数は維持され、対応するエントリを持たないときには、その分岐は除去される。
【００４２】
本発明の種々の実施形態によれば、ストレージ空間再利用プロセスは、種々の方法で開始させることができ、即ち、継続的に、周期的に、擬似ランダムに、ランダムに、イベントの発生に応じて（例えばユーザのデータ又はメタデータのサイズ制限や、特定の数の検索操作、更新操作、及び／又は差し戻し操作の実行に応じて）、などといった方法で、実行することができる。ストレージ空間再利用プロセスの１つの実行から別の実行までの時間経過は、１つ又は複数の関連ウィンドウのサイズに対応するものとすることができる。好ましくは、プロセスは、イベントが発生したときに開始される。イベントは、第１のデータ構造のページが満たされるか又は別のページに統合されるなどのときに関連ウィンドウから分岐が除外されることを含むことができる。
【００４３】
説明を簡単にするために、以下の図面は、第２のデータ構造が差し戻し操作を表し、差し戻し操作は差し戻し時間におけるデータ・バージョンに対して行われ、書き込み操作のために用いられるキーは論理ブロック・アドレスである、本発明の特定の実施形態を示す。本方法、システム、及びコンピュータ可読媒体は、第２のデータ構造が（差し戻し、既存の分岐の複製などといった）分岐作成操作を表すときには準用が可能であること、分岐作成操作は、要求されたタイムスタンプにおけるデータ・バージョンによって開始する分岐を作成すること（要求されたタイムスタンプは、データのバージョンと関連付けられ、必ずしも分岐の作成時間を反映する必要はない）、及び、キーが論理ブロック・アドレスと異なるものとすることができることを留意されたい。
【００４４】
図１は、本発明の１つの実施形態による、データを管理するためのシステム１００を示す。システム１００は分散型アーキテクチャを有する。システム１００は、アダプタ１４３、第１のストレージ・ユニット１２１、及び第２のストレージ・ユニット１２２に接続された、第１の書き戻し（write back）キャッシュ・ユニット１３１を含む。
【００４５】
システム１００はコントローラ１５１を含むが、コントローラは、第１の書き戻しキャッシュ・ユニット１３１内に含むこともできる。第１の書き戻しキャッシュ・ユニット１３１は、データを読み取る要求を受信し、データを書き込む要求を受信し、他の装置に接続することができるアダプタ１４３からのデータを受信する。第１の書き戻しキャッシュ・ユニット１３１は、アダプタ１４３にデータを出力する。
第１の書き戻しキャッシュ・ユニット１３１は、多数のインターフェース、アダプタなどに接続できることに留意されたい。
【００４６】
システム１００は、４つのデータ構造、即ち（ｉ）書き込み操作を表す第１のデータ構造２００、（ｉｉ）差し戻し操作を表す第２のデータ構造２５０、（ｉｉｉ）どのデータを第１のストレージ・ユニットから第２のストレージ・ユニットに送るかを示す第３のデータ構造（送りデータ構造（forward data structure）とも呼ばれる）２６０、及び、（ｉｖ）最新のデータのバージョンが第１のストレージ・ユニット１２１にあるのか、第２のストレージ・ユニット１２２にあるのかを示す第４のデータ構造（戻しデータ構造（backward data structure）とも呼ばれる）２７０を維持する。
【００４７】
これらのデータ構造の各々は、システム１００の種々の位置に格納することができ、例えば、全てのデータ構造２００、２５０、２６０、及び２７０を第２のストレージ・ユニット１２２に格納することができるが、必ずしもそうである必要はない。
【００４８】
第３のデータ構造２６０は、デステージング期間が開始したとき、及び、データ・バージョンが第１のストレージ・ユニットから第２のストレージ・ユニットにコピーされたときに、更新される。
【００４９】
好ましくは、（１つのデータ割り当てユニットごとに）１つのデータ・バージョンのみがコピーされる。現在のキャッシュ済データ・バージョンがコピーされるべきかどうかを知るために、第１のデータ構造が走査される場合がある。この走査を避けるために、第３のデータ構造２６０は、現在のキャッシュ済データがコピーされるべきかどうかを示す。
【００５０】
好ましくは、第３のデータ構造２６０は、データ割り当てユニットごとに１ビットを含む。このビットは、現在のキャッシュ済データ・バージョンと新しいデータ・バージョンと（どちらも同じキャッシュ・データ割り当てユニットと関連する）が同じデステージング期間に属するかどうかを示す。答えが肯定の場合には、現在のキャッシュ済データ・バージョンはコピーされない。第３のデータ構造のビットは、現在のデステージング期間ごとに最初のキャッシュ操作が生じたときにセットされる。そのデステージング期間の最後に、ビットはリセットされる。
【００５１】
第４のデータ構造２７０は、差し戻し操作並びに差し戻し操作に続くステージング操作及びデステージング操作への応答として更新される。
【００５２】
差し戻し操作は、第２のストレージ・ユニットから第１のストレージ・ユニットに送られるデータを必要とする。このプロセスは時間がかかるものであり、このプロセス中にシステムがデータ要求に対応できるようにするために、第４のデータ構造が用いられる。
【００５３】
（特定の時点への）差し戻し操作の後は、最新のデータ・バージョンはその時点に対応していることに留意されたい。従って、これらは、デステージングされたデータ・バージョン及びより古いデータ・バージョンへの差し戻し操作の前に考慮されたデータ・バージョンとすることができる。
【００５４】
第４のデータ構造２７０は、データ割り当てユニットごとに１ビットを含むことができる。差し戻し操作が要求された場合には、このビットをセットすることができる。第２のストレージ・ユニットのデータ割り当てユニットに格納されたデータが第１のストレージ・ユニットに格納されると、ビットはリセットされる。
【００５５】
データは、第１の書き戻しキャッシュ・ユニット１３１にキャッシュし、次いで第１のストレージ・ユニット１２１にデステージングすることができる。第１のストレージ・ユニット１２１からのデータは、第１の書き戻しキャッシュ・ユニット１３１を経由して、第２のストレージ・ユニット１２２に送ることができる。第１のストレージ・ユニット１２１は、ステージングされた（現在の）データ・バージョンを格納し、第２のストレージ・ユニット１２２は、より古いデータ・バージョンを格納する。差し戻しは、第１のストレージ・ユニット１２１及び／又は第２のストレージ・ユニット１２２からのデータをステージングすることを要求することができる。
【００５６】
コントローラ１５１は、（ｉ）特定のキャッシュ・データ割り当てユニットに新しいデータ・バージョンを書き込む要求を受信し、（ｉｉ）データ・ストレージ・ポリシーに応じて、特定のキャッシュ・データ割り当てユニットに現在キャッシュされているキャッシュ済データ・バージョンを上書きするか、又は、特定のキャッシュ・データ割り当てユニットに新しいデータ・バージョンを書き込む前に、キャッシュ済データ・バージョンの第１のストレージ・ユニットへのデステージングを行うかを判定し、（ｉｉｉ）特定の時点に対応するデータ・バージョンを読み取る要求を受信し、（ｉｖ）要求されたデータ・バージョンの位置を求めるために、書き込み操作を表す第１のデータ構造と、差し戻し操作を表す第２のデータ構造とを走査するように、適合させることができる。第１のデータ構造及び第２のデータ構造は、図１０に示される。
【００５７】
コントローラ１５１は、システム１００の種々の構成要素を制御して、要求されたデータ・バージョンを提供し、（コントローラの判定に応じて）選択的に強制デステージングを実施する。
【００５８】
好ましくは、第１の書き戻しキャッシュ・ユニット１３１は、同一のデータの多数のバージョンを格納するようには適合されない。したがって、新しいデータ・バージョンがキャッシュされる前に、コントローラ１５１は、キャッシュ済データ・バージョンをデータ・ストレージ・ユニットに保存すべきかどうかを決定しなければならない。決定は、データ・ストレージ・ポリシーに応じて行われる。
【００５９】
別の実施形態によれば、第１の書き戻しキャッシュ・ユニット１３１は、同一のデータの多数のバージョンを格納するように適合される。
【００６０】
システム１００、特にコントローラ１５１は、インターセプトを用いることによって、第１の書き戻しキャッシュ・ユニット１３１の操作を制御することができる。
【００６１】
システム１００は、少なくとも１つのデータの関連ウィンドウを定めるデータ・ストレージ・ポリシーを定めるか、部分的に定めるか、部分的に受信するか、又は受信することができる。関連ウィンドウは、第１の書き戻しキャッシュ・ユニット１３１と、第１のストレージ・ユニット１２１及び第２のストレージ・ユニット１２２との間のステージング操作及びデステージング操作に影響を与える。
【００６２】
図２は、本発明の１つの実施形態による、単一の割り当てユニットの単一のデータ・バージョンに対するステージング操作及びデステージング操作の例示的なシーケンスを示す。
シーケンスは、新しいデータ・バージョンを書き込む要求をアダプタ１４３から第１の書き戻しキャッシュ・ユニット１３１の特定のキャッシュ・データ割り当てユニットに送るステップ（文字Ａにより示される）によって開始する。その特定のキャッシュ割り当てユニットに現在キャッシュされているキャッシュ済データ・バージョンを（データ・ストレージ・ポリシーに従って）デステージングすべき場合には、そのバージョンは、第１のデータ・ストレージ・ユニット１２１にデステージングされ（文字Ｂによって示される）、デステージングされたデータ・バージョンとなる。このデステージング・ステップの後、新しいデータ・バージョンが特定のキャッシュ・データ割り当てユニットにキャッシュされる。
【００６３】
デステージングされたデータ・バージョンは、特により新しいデータ・バージョンがキャッシュされ、その後デステージングされた場合には、より古いデータ・バージョンとなることがある。より古いデータ・バージョンは、上書きされる前に、第１のストレージ・ユニット１２１から第１の書き戻しキャッシュ・ユニット１３１にステージングし（文字Ｃにより示される）、次いで第２のストレージ・ユニット１２２にデステージングすることができる（文字Ｄにより示される）。
【００６４】
特定の時点に対応するデータ・バージョンを読み取る要求が受信されると、要求されたデータ・バージョンは、第１のストレージ・ユニット１２１からステージングする（文字Ｅにより示される）か、又は、第２のストレージ・ユニット１２２からステージングする（文字Ｅ’により示される）ことができる。次いで、要求されたデータ・バージョンは、第１の書き戻しキャッシュ・ユニット１３１からアダプタ１４３に送られる。
【００６５】
本発明の１つの実施形態によれば、第１のストレージ・ユニット１２１は書き込みタイムスタンプを格納しない。第２のストレージ・ユニットは、より古いデータ・バージョンがいつ受信されたかを示すダミー・エントリを第１のデータ構造の中に開くことができる。このダミー・エントリは、デステージングされたデータ・バージョンが第２のストレージ・ユニット１２２に送られると、通常のエントリに変換される。
【００６６】
図３は、本発明の別の実施形態による、データを管理するためのシステム１００’を示す。図３は、集中型アーキテクチャを示す。
【００６７】
システム１００’は、アダプタ１４３と第１のストレージ・ユニット１２１とに接続された第１の書き戻しキャッシュ・ユニット１３１を含む。
システム１００’は、第２のストレージ・ユニット１２２を含まない点で図１のシステム１００と異なる。従って、１つのストレージ・ユニットしか存在しないので、送りデータ構造２６０及び戻しデータ構造２７０は必要とされない。
【００６８】
図４は、本発明の１つの実施形態によるステージング操作及びデステージング操作の例示的なシーケンスを示す。
【００６９】
シーケンスは、新しいデータ・バージョンを書き込む要求をアダプタ１４３から第１の書き戻しキャッシュ・ユニット１３１の特定のキャッシュ・データ割り当てユニットに送るステップ（文字Ａにより示される）で開始する。その特定のキャッシュ割り当てユニットに現在キャッシュされているキャッシュ済データ・バージョンを（データ・ストレージ・ポリシーに従って）デステージングすべき場合には、そのバージョンは、第１のデータ・ストレージ・ユニット１２１にデステージングされ（文字Ｂによって示される）、デステージングされたデータ・バージョンとなる。このデステージング・ステップの後、新しいデータ・バージョンが特定のキャッシュ・データ割り当てユニットにキャッシュされる。
【００７０】
デステージングされたデータ・バージョンは、特により新しいデータ・バージョンがキャッシュされ、その後デステージングされた場合には、より古いデータ・バージョンとなることがある。より古いデータ・バージョンもまた、第１のストレージ・ユニット１２１に格納される。
【００７１】
特定の時点に対応するデータ・バージョンを読み取る要求が受信されると、要求されたデータ・バージョンは、第１のストレージ・ユニット１２１からステージングされる（文字Ｃにより示される）。次いで、要求されたデータ・バージョンは、第１の書き戻しキャッシュ・ユニット１３１からアダプタ１４３に送られる。
【００７２】
図５は、本発明の更なる実施形態による、データを管理するためのシステム１００’’を示す。
【００７３】
システム１００’’は、第１の書き戻しキャッシュ・ユニット１３１と、第２の書き戻しキャッシュ・ユニット１３２と、第１の不揮発性メモリ１４１と、第２の不揮発性メモリ１４２と、コントローラ１５１と、アダプタ１４３と、第１のストレージ・ユニット１２１と、第２のストレージ・ユニット１２２と、を含む。不揮発性メモリは、図１、図２、図３、及び図４に示される構成のような、システムの他の構成に含めることができることに留意されたい。
【００７４】
システム１００’’は、実質的に互いに独立した２つの部分を含む。１つの部分は他の部分をバックアップする。好ましくは、各々の部分は、自身の電源供給ユニット、自身のコントローラなどを有する。説明を簡単にするために、単一のコントローラ１５１及び単一のアダプタ１４３が示されるが、これらは二重化することもできる。
【００７５】
システム１００’’の第１の部分は、第１の不揮発性メモリ１４１と、第１の書き戻しキャッシュ・ユニット１３１と、第１のストレージ・ユニット１２１と、を含む。システム１００’’の第２の部分は、第２の不揮発性メモリ１４２と、第２の書き戻しキャッシュ・ユニット１３２と、第２のストレージ・ユニット１２２と、を含む。
【００７６】
コントローラ１５１は、第１の書き戻しキャッシュ・ユニット１３１と、第２の書き戻しキャッシュ・ユニット１３２と、第１の不揮発性メモリ１４１と、第２の不揮発性メモリ１４２と、に接続される。アダプタ１４３は、第１の書き戻しキャッシュ・ユニット１３１と、第２の書き戻しキャッシュ・ユニット１３２と、第１の不揮発性メモリ１４１と、第２の不揮発性メモリ１４２と、に接続される。
【００７７】
第１のストレージ・ユニット１２１は、第１の書き戻しキャッシュ・ユニット１３１と、第２の書き戻しキャッシュ・ユニット１３２と、に接続される。第２のストレージ・ユニット１２２は、第１の書き戻しキャッシュ・ユニット１３１と、第２の書き戻しキャッシュ・ユニット１３２と、に接続される。
【００７８】
第１の書き戻しキャッシュ・ユニット１３１に送られるデータは、第２の不揮発性メモリ１４２にも送られる。第２の書き戻しキャッシュ・ユニット１３２に送られるデータは、第１の不揮発性メモリ１４１にも送られる。
【００７９】
さらに、第１のストレージ・ユニット１２１と第２のストレージ・ユニット１２２の各々は、第１の書き戻しキャッシュ・ユニット１３１からのデータ及び第２の書き戻しキャッシュ・ユニット１３２からのデータを格納することができる。
【００８０】
上述されたように、システム１００’’は、２つの部分を有する。説明を簡単にするために、図６−図１０は、第１の部分（特に第１の書き戻しキャッシュ・ユニット１３１）への読み取り操作及び書き込み操作を示す。当業者であれば、第２の部分への読み取り操作及び書き込み操作は、対称に実行されることが分かるであろう。
【００８１】
図６は、本発明の別の実施形態による読み取り及び書き込みのステージング操作及びデステージング操作の例示的なシーケンスを示す。
図６は、第１のストレージ・ユニット１２１がデステージングされたデータ・バージョンとより古いデータ・バージョンの両方を格納する集中型アーキテクチャを示す。
【００８２】
図６に示されるシーケンスは、新しいデータ・バージョンを第１の書き戻しキャッシュ・ユニット１３１にキャッシュすることに加えて、それを第２の不揮発性メモリ１４２に書き込む（文字Ａ’によって示される）という点で、図４のシーケンスと異なる。従って、第１の部分が故障した場合には、そのデータ・バージョンを第２の不揮発性メモリ・ユニット１４２から取得する（文字Ｄ’によって示される）ことができる。
【００８３】
図７は、本発明のさらに別の実施形態による、読み取り及び書き込みのステージング操作及びデステージング操作の例示的なシーケンスを示す。
図７は、第１のデータ・ストレージ・ユニット１２１がデステージングされたデータ・バージョンを格納し、第２のストレージ・ユニット１２２がより古いデータ・バージョンを格納する、分散型アーキテクチャを示す。
【００８４】
図７に示されるシーケンスは、新しいデータ・バージョンを第１の書き戻しキャッシュ・ユニット１３１にキャッシュすることに加えて、それを第２の不揮発性メモリ１４２に書き込む（文字Ａ’によって示される）という点で、図２のシーケンスと異なる。従って、第１の部分が故障した場合には、そのデータ・バージョンを第２の不揮発性メモリ・ユニット１４２から取得する（文字Ｆ’によって示される）ことができる。
【００８５】
図８は、本発明の更なる実施形態による、読み取り及び書き込みのステージング操作及びデステージング操作の例示的なシーケンスを示す。
図８は、キャッシュ・レベル分割アーキテクチャを示す。キャッシュ・レベル分割アーキテクチャ・システムは、新しいデータ・バージョンを、第１の書き戻しキャッシュ・ユニット１３１と第２の書き戻しキャッシュ・ユニット１３２の両方にキャッシュする。キャッシュ・レベル分割アーキテクチャにおいては、キャッシュ済データ・バージョンは、第１のストレージ・ユニット１２１から（キャッシュ・ユニットを経由して）第２のデータ・ストレージ・ユニット１２２には送られない。キャッシュ済データ・バージョンは、第１の書き戻しキャッシュ・ユニット１３１から第１のストレージ・ユニット１２１に送られ（文字Ａによって示される）、第２の書き戻しキャッシュ・ユニット１３２から第２のストレージ・ユニット１２２に送られる（文字Ａ’によって示される）。より古いデータ・バージョンは、第１のストレージ・ユニット１２１に格納されるのではなく、第２のストレージ・ユニット１２２に格納される。第２のストレージ・ユニット１２２は、デステージングされたデータ・バージョン及びより古いデータ・バージョンを受信し、格納する。
【００８６】
好ましくは、デステージングされたデータ・バージョンは、第１のストレージ・ユニット１２１から提供される（文字Ｃによって示される）。より古いデータ・バージョンは、第２のストレージ・ユニットから提供される（文字Ｃ’によって示される）。デステージングされたデータ・バージョンは、第２のストレージ・ユニット１２２からも提供できることに留意されたい。第２の不揮発性メモリ１４２もまた、新しいデータ・バージョンを受信し（文字Ａ’’によって示される）、これらのデータ・バージョンをアダプタ１４３に提供することができる（文字Ｄ’’によって示される）。
【００８７】
キャッシュ・レベル分割アーキテクチャにおいては、データは、第１のストレージ・ユニット１２１から第２のストレージ・ユニットに送られない。好ましくは、データ・ストレージ粒度が非常に細かい場合には、キャッシュ・レベル分割アーキテクチャは、多数のステージング操作及びデステージングを省くことができる。その一方で、データ・ストレージ粒度が低い場合には、このアーキテクチャは、非分割アーキテクチャにおいて必要とされる可能性のある操作より多くのデステージング操作を実施する。
【００８８】
図９は、本発明の更なる実施形態による、読み取り及び書き込みのステージング操作及びデステージング操作の例示的なシーケンスを示す。
図９は、ストレージ・ユニット・レベル分割アーキテクチャを示す。ストレージ・ユニット・レベル分割アーキテクチャ・システムは、新しいデータ・バージョンを単一の書き戻しキャッシュ・ユニットにキャッシュするが、キャッシュ済データ・バージョンは、第１のストレージ・ユニット１２１（文字Ｂによって示される）及び第２のストレージ・ユニット１２２（文字Ｂ’によって示される）に送る。
【００８９】
第１のストレージ・ユニット１２１は、より古いデータ・バージョンを格納しない。デステージングされたデータ・バージョンは、第１のストレージ・ユニット１２１から第１の書き戻しキャッシュ・ユニットに提供される（文字Ｃによって示される）。より古いデータ・バージョンは、第２のストレージ・ユニット１２２に格納され、後で第２のストレージ・ユニット１２２から第１の書き戻しキャッシュ・ユニット１３１に提供することができる（文字Ｃ’によって示される）。デステージングされたデータ・バージョンは、第２のストレージ・ユニット１２２からも提供できることに留意されたい。第２の不揮発性メモリ１４２もまた、新しいデータ・バージョンを受信し（文字Ａ’によって示される）、これらのデータ・バージョンを提供する（文字Ｄ’によって示される）ことができる。
【００９０】
ストレージ・ユニット・レベル分割アーキテクチャにおいては、データは、第１のストレージ・ユニット１２１から第２のストレージ・ユニットに送られない。好ましくは、データ・ストレージ粒度が非常に細かい場合には、ストレージ・ユニット・レベル分割アーキテクチャは、多数のステージング操作及びデステージングを省くことができる。
【００９１】
本発明の別の実施形態によれば、システム１００’’は、選択的ストレージ・ユニット・レベル分割アーキテクチャを適用することもできる。従って、システム１００’’は、キャッシュ済データ・バージョンをデステージングする前に、そのデータ・バージョンを第１のストレージ・ユニットに送るか、又は、第１のストレージ・ユニット１２１及び第２のストレージ・ユニット１２２の両方に送るかを決定することができる。
【００９２】
好ましくは、システムが、キャッシュ済データ・バージョンがデステージング期間の経過の間にキャッシュされることになるデータ・バージョンのうちの最後のものであることを判別できる場合には、このキャッシュ済データ・バージョンは、第１のストレージ・ユニット及び第２のストレージ・ユニットに送ることができる。キャッシュ済データ・バージョンは、デステージング期間の途中で、又はそのデステージング期間の最初に、デステージングすべき場合には、第１のストレージ・ユニット１２１にデステージングすることができる。
キャッシュ済データ・バージョンは、デステージング期間の所定部分が経過したことに応答して、両方のデータ・ストレージ・ユニットに送ることができることに留意されたい。
【００９３】
選択的ストレージ・ユニット分割アーキテクチャは、データ・ストレージ粒度が粗いときには実質的に分散型アーキテクチャとして作動し、データ・ストレージ粒度が細かいときには実質的にストレージ・ユニット・レベル分割アーキテクチャとして作動する。
【００９４】
図１０は、本発明の１つの実施形態による、第１のデータ構造２００の一部２０１と、第２のデータ構造２５０の一部２５１とを示す。この例においては、キーはタイムスタンプを持つＬＢＡであり、データは物理アドレスである。しかしながら、他の例を用いることもできる。説明を簡単にするために、これらの図は、同じ論理ブロック・アドレス（例えばＬＢＡ＝１２）に対する読み取り操作及び差し戻し操作を示す。
第１のデータ構造２００は、他のＬＢＡに対する書き込み操作に関するメタデータを含むことに留意されたい。
また、一部２０１は、特定のＬＢＡに対する更新操作を表すものとして示されるが、他のＬＢＡに関する操作を表すこともできることに留意されたい。代替的に、他のグラフが他のＬＢＡに関わる操作を表すこともできる。
【００９５】
第１のデータ構造２００は、３つの列２００（１）、２００（２）、及び２００（３）を含む。各々のエントリは、書き込み操作に関する情報を含む。第１列２００（１）は書き込み操作の論理ブロック・アドレスを含み、第２列２００（２）は書き込みタイムスタンプを含み、第３列２００（３）は書き込み操作の物理アドレスを含む。論理ブロック・アドレス及び書き込み時間のフィールドは、第１のデータ構造２００に対するキー（インデックス）として用いることができる。
特定の時点において、多数のＬＢＡに対する書き込み操作が生じた場合には、第１のテーブルは、この書き込み操作を反映する多数のエントリを含むことになることに留意されたい。
【００９６】
第２のデータ構造２５０は、４つの列２５０（１）−２５０（４）を含む。第１列２５０（１）は分岐識別子を含み、第２列２５０（２）は分岐開始時間を含み、第３列２５０（３）は分岐終了時間を含み、第４列２５０（４）は各々の分岐の差し戻し時間を含む。
【００９７】
データ構造２００及び２５０は、所与の時点の各々において１つの分岐のみがアクティブである書き込み操作及び差し戻し操作のシーケンスを制御するように適合される。同時にアクティブな多数の分岐をサポートするためには、これらのテーブルは、分岐識別情報を含むように修正しなければならない。
【００９８】
図１１は、本発明の１つの実施形態による書き込み操作及び差し戻し操作の例示的なシーケンス１０１を示す。シーケンス１０１は、時間１０、３０、４０、６０、９０、及び１１０における論理ユニット（ＬＵＮ）などの仮想アドレス空間への書き込み操作と、それに応じた時間３５及び７０におけるＬＵＮの内容を差し戻す（時間８０及び１００において受信された）要求と、を含む。
破線は差し戻し操作を表す。所与の時点のいずれにおいても１つの分岐のみがアクティブであることに留意されたい。
【００９９】
書き込み操作は、論理ブロック・アドレス１２と関連付けられ、これらの書き込み操作と関連付けられる物理アドレスは、これに応じて、ａ、ｂ、ｃ、ｄ、ｅ、及びｆとされたと仮定する。
【０１００】
第１のデータ構造２００の第１列２００（１）は、書き込み操作が論理ブロック・アドレス１２に対するものであったことを示す。第１のデータ構造２００の第２列２００（２）は、書き込み操作が、時間１０、３０、４０、６０、９０、及び１１０において生じたことを示す。第１のデータ構造２００の第３列２００（３）は、これらの書き込み操作と関連付けられた物理アドレスが、ａ、ｂ、ｃ、ｄ、ｅ、及びｆであったことを示す。
【０１０１】
第２のデータ構造２５０の第１のエントリは、第１の分岐が時間０において開始し、時間８０において終了したことを示す。第１の分岐は、ＬＵＮのコンテンツを差し戻す第１の要求が受け入れられたときに終了した。
【０１０２】
第２のデータ構造２５０の第２のエントリは、第２の分岐が時間８０において開始し、時間１００において終了したことを示す。第２の分岐は、ＬＵＮのコンテンツを差し戻す第２の要求が受け入れられたときに終了した。
【０１０３】
第２のデータ構造２５０の第３のエントリは、第３の分岐が時間１００において開始し、終了しなかったことを示す。
【０１０４】
本発明の別の実施形態によれば、第２のデータ構造は、分岐の統計値などの付加的なメタデータを含む。分岐の統計値は、例えば、その分岐に属する第１のデータ構造のエントリの数、その分岐の持続時間の間に書き込まれた異なる論理ブロック・アドレスの数などを含むことができる。好ましくは、分岐の統計値は、特に読み書きの操作が頻繁に生じる場合に、どの分岐を削除するかの判定を補助することができる。
【０１０５】
図１２は、本発明の１つの実施形態による書き込み操作及び差し戻し操作の例示的なシーケンス３００を示す。
【０１０６】
第１のＬＢＡへの書き込み操作（Ｗ１、Ｗ３、Ｗ５、及びＷ６）は三角形で示される。第２のＬＢＡへの書き込み操作（Ｗ４及びＷ１０）は円形で示される。第３のＬＢＡへの書き込み操作（Ｗ２、Ｗ７、及びＷ９）は四角形で示される。
【０１０７】
シーケンス３００は、４つの分岐Ｂ１  ３０１−Ｂ４  ３０４を含み、Ｔ１４から現時点（Ｔ＿ＣＵＲＲＥＮＴ）までの間にわたる関連ウィンドウ３１０を定める。
【０１０８】
第１の分岐（Ｂ１）３０１は、時間Ｔ０において開始し（Ｓ１）、時間Ｔ８において終了する（Ｅ１）。第１の分岐Ｂ１は、以下の書き込み操作、すなわち、Ｔ１における（第１のＬＢＡへの）書き込み操作Ｗ１と、Ｔ２における（第３のＬＢＡへの）書き込み操作Ｗ２と、Ｔ３における（第１のＬＢＡへの）書き込み操作Ｗ３と、Ｔ４における（第２のＬＢＡへの）書き込み操作Ｗ４と、Ｔ６における（第１のＬＢＡへの）書き込み操作Ｗ５と、を含む。Ｂ１は、Ｔ８において終了する（Ｅ１）。
【０１０９】
第２の分岐（Ｂ２）３０２はＢ１  ３０１の子であり、時間Ｔ５への差し戻し操作（ＲＶ１）によって時間Ｔ８において開始する（Ｓ２）。第２の分岐Ｂ２  ３０２は、以下の書き込み操作、すなわち、Ｔ９における（第１のＬＢＡへの）書き込み操作Ｗ６と、Ｔ１１における（第３のＬＢＡへの）書き込み操作Ｗ７と、を含む。Ｂ２は、Ｔ１２において終了する（Ｅ２）。
【０１１０】
第３の分岐（Ｂ３）３０３はＢ２  ３０２の子であり、時間Ｔ１０への差し戻し操作（ＲＶ２）によって時間Ｔ１２において開始する（Ｓ３）。第３の分岐Ｂ３  ３０３は、Ｔ１３における（第３のＬＢＡへの）単一の書き込み操作Ｗ８を含む。Ｂ３は、Ｔ１５において終了する（Ｅ３）。
【０１１１】
第４の分岐（Ｂ４）３０４はＢ３  ３０３の子であり、時間Ｔ１４への差し戻し操作（ＲＶ３）によって時間Ｔ１５において開始する（Ｓ４）。Ｂ４  ３０４は、Ｔ１６における（第３のＬＢＡへの）書き込み操作Ｗ９と、Ｔ１７における（第２のＬＢＡへの）別の書き込み操作Ｗ１０と、を含む。第４の分岐Ｂ４  ３０４は、Ｔ１８において終了する（Ｅ４）。
【０１１２】
図１３は、本発明の別の実施形態による書き込み操作及び差し戻し操作の例示的なシーケンス３００’を示す。
シーケンス３００’は、第２の差し戻し操作（ＲＶ２’）の差し戻し時間の点でシーケンス３００と異なる。差し戻し時間は、（第１の分岐Ｂ１  ３０１に属する）Ｔ７であり、（第２の分岐Ｂ２  ３０２に属する）Ｔ１０ではない。従って、シーケンス３００では子分岐（Ｂ３  ３０３）を有していた第２の分岐Ｂ２  ３０２は、シーケンス３００’においては子を持たない。
【０１１３】
図１４は、本発明の１つの実施形態による、データ・バージョンを取得するための方法４００を示す。
方法４００は、現在の分岐を選択する又は獲得するステージ４１０で開始する。ステージ４１０の後で、分岐の開始時間において開始し、データ・バージョンの取得要求と関連する要求されたタイムスタンプにおいて終了する、その分岐のセクションにおいて、書き込み操作が存在するかどうかをチェックするステージ４１２が続く。答えが否定の場合にはステージ４１２の後にステージ４１４が続き、それ以外の場合にはステージ４１２の後にステージ４２０が続く。
【０１１４】
ステージ４２０は、方法４００の結果として最新の書き込み操作を戻すことを含む。ステージ４１４は、その分岐が親分岐を有するかどうかをチェックすることを含む。答えが否定の場合には、方法４００は、否定の答え（Ｎｕｌｌ）を戻すステージ４１６で終了する。答えが肯定の場合には、ステージ４１４の後に、分岐の親を獲得するステージ４２２と、その分岐の開始時間において開始し、検査される親分岐の子分岐と関連する差し戻し時間において終了する、その親分岐のセクションにおいて、書き込み操作が存在するかどうかをチェックするステージ４２４と、が続く。答えが否定の場合にはステージ４２４の後にステージ４１４が続き、それ以外の場合にはステージ４２４の後にステージ４２０が続く。
【０１１５】
図１５は、本発明の１つの実施形態による粗分析を示す。
粗分析５００は、分岐インデックス（Ｊ）を１にセットするステージ５１０で開始する。
ステージ５１０の後に、第Ｊ番目の分岐と関連ウィンドウとの間の関係を判定するステージ５２０が続く。
【０１１６】
第Ｊ番目の分岐と関連ウィンドウとが少なくとも部分的に重なる場合には、第Ｊ番目の分岐は削除されず、ステージ５２０の後に、Ｊを増加させるステージ５３０が続き、ステージ５２０にジャンプする。この反復は、第２のデータ構造全体が走査されたときに終了することに留意されたい。
【０１１７】
第Ｊ番目の分岐と関連ウィンドウとが重ならない（部分的にも重ならない）場合には、ステージ５２０の後に、第Ｊ番目の分岐が１つ又は複数の子分岐を含むかどうかをチェックするステージ５４０が続く。
【０１１８】
第Ｊ番目の分岐が単一の子分岐を有する場合には、ステージ５４０の後に、第Ｊ番目の分岐とその子分岐とを統合するステージ５５０が続く。本発明の１つの実施形態によれば、ステージ５５０は、分岐を、統合されるべき分岐として（例えば、子分岐の差し戻し時間の前の最後のエントリを子分岐の開始時間に移動させることによって）マークすることを含む。
【０１１９】
第Ｊ番目の分岐が関連ウィンドウの外部にあり、いかなる子も持たない場合には、ステージ５５０の後に、その分岐と関連するメタデータを削除するステージ５６０が続く。本発明の１つの実施形態によれば、ステージ５６０は、分岐を、削除されるべき分岐としてマークすることを含む。削除は、精密分析の際に行うことができる。
【０１２０】
多数の子分岐が存在する場合には、ステージ５４０の後にステージ５３０が続く。
ステージ５６０及び５５０の後にステージ５３０が続く。
【０１２１】
例えば、図１２を参照すると、第４の分岐Ｂ４  ３０４は関連ウィンドウ内にあり、第１から第３までの分岐は第４の分岐の祖先である。従って、どの分岐も削除されない。
【０１２２】
さらに別の例として、図１３を参照すると、第２の分岐Ｂ２  ３０２は、第４の分岐Ｂ４  ３０４の祖先ではなく、関連ウィンドウの外部にあり、従って削除することができる。
【０１２３】
削除は、分岐を削除候補としてマークし、そのようなマークに対応する精密分析を行い、その後で分岐を削除することを含むことができることに留意されたい。
【０１２４】
図１６及び図１７は、本発明の１つの実施形態による全体精密分析６００を示す。
図１６は、分析６００の最初の部分６００（ａ）を示し、図１７は分析６００の部分６００（ｂ）を示す。
【０１２５】
全体精密分析は、特定の分岐について実施される。次いで、別の分岐について実施することができる。
全体精密分析６００は、その特定の分岐の一部において少なくともアクティブである分岐の各々を探し出すステージ６１０で開始する。このような分岐の各々は関連分岐と呼ばれる。
【０１２６】
ステージ６１０の後に、関連ウィンドウの外部に位置する関連分岐を子分岐の差し戻し時間によって分割されるセクションに分けるステージ６２０が続く。各々のセクションは子分岐と関係付けられる。
【０１２７】
ステージ６２０の後に、分岐の最後のセクション（子分岐の最後の差し戻し時間において開始し、分岐の終了時間において終了するセクション）が関連ウィンドウの外部にあると仮定して、そのセクションにおけるいずれかの書き込み操作を除去するステージ６２５が続く。
【０１２８】
ステージ６２５の後に、（関連ウィンドウの外部にある）セクションが多数の書き込みを有する場合には、そのセクションの全ての書き込み操作（最後の書き込みを除く）を除去するステージ６３０が続く。
【０１２９】
ステージ６３０の後に、多数のセクションのうちの特定のセクションについて、そのセクション及び後続のセクションが書き込み操作を含むかどうかを判定するステージ６３５が続く。答えが肯定の場合には、ステージ６３５の後に、書き込みセクションを子分岐の開始時間に移動させるステージ６４２が続く。答えが否定の場合には、ステージ６３５の後に、現在のセクションが書き込み操作を有していないか、又は局所精密分析が適用されるかどうかを判定するステージ６４０が続く。答えがいいえであれば、ステージ６４０の後にステージ６５０が続き、そうでなければ、多数のセクションの中から次のセクションを選択するステージ６４５が続き、ステージ６３５にジャンプする。
【０１３０】
ステージ６５０は、特定の書き込み操作Ｕと、特定のセクションの子分岐Ｃ１．．．Ｃｎと、を受信することを含む。ステージ６５０の後に、カウンタｘを０にセットし、分岐ｂをｎｕｌｌにセットし、作業リストＷＬを書き込み操作Ｕと子分岐との対、即ちＷＬ＝｛（Ｕ，Ｃ１），．．．（Ｕ，Ｃｎ）｝に等しくなるように定める（即ちセットする）ステージ６５２が続く。
【０１３１】
ステージ６５２の後に、ＷＬが空かどうかを判定するステージ６５４が続く。答えが肯定の場合にはステージ６５４の後にステージ６５６が続き、答えが否定の場合にはステージ６５４の後にステージ６６４が続く。
【０１３２】
ステージ６５６は、＜ｘ，ｂ＞を準備することを含む。ステージ６５６の後に、ｘの値をチェックするステージ６５８が続く。ｘ＝０であれば、ステージ６５８の後にステージ６６０、即ち書き込み操作を除去することが続く。ステージ６６０の後に、ステージ６４５が続く。ｘ＝１であれば、ステージ６５８の後に、書き込み操作を子分岐に移動させるステージ６６２が続く。ｘ＝２であれば、ステージ６５８の後にステージ６４５が続く。ステージ６６２の後にステージ６４５が続く。
【０１３３】
ステージ６６４は、ＷＬから第１のアイテム（（ｗ，ｄ）と呼ばれる）を除去することと、分岐ｄの最初の書き込み操作が関連ウィンドウの開始後に生じたかどうかをチェックすることと、を含む。答えが否定の場合には、ステージ６６４の後にステージ６７４が続き、それ以外の場合にはステージ６６６が続く。ステージ６６６は、ｘを増加させることを含み、その後に、ｘが１より大きいかどうをチェックするステージ６６８が続く。ｘがゼロ又は１であれば、ステージ６６８の後に、＜ｘ，ｂ＞を＜ｘ，ｎｕｌｌ＞にセットするステージ６７０が続き、ステージ６５６にジャンプする。ｘ＞１であれば、ステージ６６８の後に、ｂを２にセットするステージ６７２が続き、ステージ６５４にジャンプする。
【０１３４】
ステージ６７４は、作業リストに、分岐ｄの開始時間と、ｗの時間より小さい差し戻し時間を有する分岐ｄの子分岐との対のセットを加えることを含む。ＷＬ＝｛（開始時間（ｄ），ｄ１），．．．，（開始時間（ｄ），ｄｎ）｝である。ステージ６７４の後にステージ６５４が続く。
【０１３５】
上述された例の殆どは、いずれの時点においてもアクティブな分岐が一つだけ存在するシナリオについて言及していることに留意されたい。上述されたように、これは必須の条件ではない。共存する多数の分岐をサポートするために、共存する多数の分岐の中から選択するための付加的なメタデータが必要となる。この付加的なメタデータは、分岐識別子、親分岐識別子などを含むものとすることができる。
【０１３６】
テスト環境、多数のスナップショットをサポートするホスト・アドレス可能な論理ユニットの実装などを含むがこれらに限定されない種々のシナリオにおいて、多数の分岐は同時に存在することができる。
【０１３７】
多数の分岐が同時に存在する場合には、（例えば、差し戻し操作を実施することによる）新たな分岐の追加は、必ずしも別の分岐を終了させないことに留意されたい。本発明の１つの実施形態によれば、第３のデータ構造が定められる。
【０１３８】
第３のデータ構造は、各々のＬＢＡに対する最初の書き込み操作を含む。このようなテーブルは、種々の走査シーケンスを簡略化することができる。さらに別の例について、分岐ごとの最後の書き込み操作を含む別のデータ構造を定めることもできる。本発明の別の実施形態によれば、Ｂ木はプレフィクスＢ木によって置き換えられる。
【０１３９】
１つの代替的な解決策は、Ｂ木のエントリを時間成分のない論理トラック数のみにすること、並びに、全てのＬＢＡエントリ及びその時間情報を伴う可変長の構造を木の葉に格納することである。
【０１４０】
図１８は、本発明の１つの実施形態による、データを管理するための方法７００を示す。
方法７００は、例えば論理ブロック・アドレスであるがこれに限定されないキーによって特定される情報への書き込み操作を表す第１のデータ構造を準備し、例えば差し戻し操作、分岐クローニング操作などであるがこれらに限定されない分岐作成操作を表す次第２のデータ構造を準備する、ステージ７１０で開始する。好ましくは、第１のデータ構造は、書き込みタイムスタンプと、論理ブロック・アドレスとその関連する物理アドレスとの間のマッピングと、を含むことが好ましい。第２のデータ構造は、分岐識別子、分岐開始時間、分岐終了時間、及び分岐差し戻し時間を含むことが好ましい。第１のデータ構造はＢ木であることが好ましい。
ステージ７１０の後にはステージ７２０、７３０、７４０、及び７５０が続く。
【０１４１】
ステージ７２０は、データを書き込むか又は更新する要求を受信することと、それに応じて第１のデータ構造を更新することと、を含む。
【０１４２】
ステージ７３０は、要求されたタイムスタンプにおけるバージョンのデータによって開始する分岐を作成する要求を受信することと、それに応じて第２のデータ構造を更新することと、を含む。例えば、分岐を作成する要求は、データを特定の差し戻し時間に差し戻す要求の結果である場合がある（差し戻し時間は、要求された時間と見なされる）。さらに別の例について、分岐を作成する要求は、データを論理的に複製する（クローニングする）要求の結果である場合があり、この場合には、要求時間が要求された時間となる。
【０１４３】
ステージ７４０は、読み取りタイムスタンプにおけるデータのバージョンを読み取る要求を受信することと、そのバージョンのデータを探し出すために第１のデータ構造及び第２のデータ構造を走査することと、を含む。ステージ７４０は、方法４００の１つ又は複数のステージを含むことができる。
【０１４４】
ステージ７５０は、データ・ストレージ・ポリシーに応じて、第１のデータ構造及び第２のデータ構造を更新することを含む。ステージ７５０は、粗分析を実施すること、精密分析を実施することなどを含むことができる。ステージ７５０は、図１５、図１６、及び図１７に示される１つ又は複数のステージを含むことができる。
【０１４５】
さらに、本発明は、コンピュータ又はいずれかの命令実行システムによって又はこれらと関連して用いるためのプログラム・コードを提供するコンピュータ使用可能媒体又はコンピュータ可読媒体からアクセス可能なコンピュータ・プログラムの形態を取ることができる。本説明の目的上、コンピュータ使用可能媒体又はコンピュータ可読媒体は、命令実行システム、装置、又はデバイスによって又はこれらと関連して用いるためのプログラムを収容し、格納し、通信し、伝播し、又は移動させることが可能なあらゆる装置とすることができる。
【０１４６】
媒体は、電子式、磁気式、光学式、電磁気式、赤外線式、又は半導体式のシステム（又は、装置若しくはデバイス）であっても、伝播媒体であってもよい。コンピュータ可読媒体の例として、半導体メモリ即ち固体メモリ、磁気テープ、取り外し可能なコンピュータ・ディスケット、ランダム・アクセス・メモリ（ＲＡＭ）、読み取り専用メモリ（ＲＯＭ）、剛体磁気ディスク、及び光ディスクが挙げられる。光ディスクの現在の例として、コンパクト・ディスク−読み取り専用メモリ（ＣＤ−ＲＯＭ）、コンパクト・ディスク−読み取り／書き込み（ＣＤ−Ｒ／Ｗ）、及びＤＶＤが挙げられる。
【０１４７】
プログラム・コードを格納及び／又は実行するのに適したデータ処理システムは、システム・バスを経由してメモリ要素に直接的又は間接的に結合された少なくとも１つのプロセッサを含む。メモリ要素は、プログラム・コードの実際の実行中に用いられるローカル・メモリと、バルク・ストレージと、実行中にバルク・ストレージからコードを取得しなければならない回数を減らすために少なくとも幾つかのプログラム・コードを一時的に格納するキャッシュ・メモリと、を含むことができる。
【０１４８】
入出力デバイス即ちＩ／Ｏデバイス（キーボード、ディスプレイ、ポインティング・デバイスなど含むがこれらに限定されない）は、システムに、直接的に、又は中間のＩ／Ｏコントローラを介して、結合することができる。
【０１４９】
データ処理システムが、介在するプライベート・ネットワーク又は公開ネットワークを通じて、他のデータ処理システム又は遠隔プリンタ若しくはストレージ装置に結合されることを可能にするために、ネットワーク・アダプタをシステムに結合することもできる。モデム、ケーブルモデム、及びイーサネット・カードは、現在利用可能なネットワーク・アダプタのタイプのうちのごく一部である。
【０１５０】
本発明の１つの実施形態によれば、データは書き戻しキャッシュに書き込まれ、データの現在のバージョンも以前のバージョンも、ディスク、ディスク・アレイ、テープなどといった１つ又は複数のストレージ・ユニットに送られる。データ・ストレージ・ポリシーは、データ及びメタデータのリフレッシュに役立つと共に、特定のデータ・バージョンをディスクに送るかどうかの判定を支援する。
【０１５１】
本発明は、ネットワーク上で、顧客に対するサービスとして提供することができる。特に、サービスはデータの格納及び取得を提供することができる。
好ましくは、ネットワーク上で顧客にサービスを提供する方法が提供される。本方法は、ネットワーク上で、読み取りタイムスタンプにおけるデータのバージョンを検索する要求を受信することと、データのそのバージョンを探し出すために第１のデータ構造及び第２のデータ構造を走査することであって、第１のデータ構造はキーによって特定されるエントリへの挿入操作又は更新操作を表し、第２のデータ構造は分岐作成操作を表し、第２のデータ構造は分岐識別子及び分岐タイミング情報を格納する、ことと、読み取りタイムスタンプにおけるデータのバージョンを提供することと、ネットワーク上で、要求されたタイムスタンプにおけるデータのバージョンによって開始する分岐を作成する要求を受信することと、それに応じて第２のデータ構造を更新することと、を含む。
【０１５２】
好ましくは、第１のデータ構造はＢ木である。
好ましくは、本発明は、所与のキーと関連する値を更新する要求をネットワーク上で受信することと、第１のデータ構造を更新することと、を含む。
好ましくは、本発明は、所与のキー及び関連するデータ並びに現在のタイムスタンプを持つ新規のエントリを追加することによって更新することを含む。
好ましくは、キーは論理ブロック・アドレスである。
好ましくは、分岐を作成する要求は差し戻し操作であり、特定のタイムスタンプは差し戻し時間である。
【０１５３】
当業者であれば、請求される本発明の趣旨及び範囲から逸脱することなく、ここで説明されたものの変形、修正、及び他の実装を思いつくであろう。
従って、本発明は、前述の例示的な説明ではなく特許請求の趣旨及び範囲によって定められることとなる。
【図１】
2010503094.tif 000003
【図２】
2010503094.tif 000004
【図３】
2010503094.tif 000005
【図４】
2010503094.tif 000006
【図５】
2010503094.tif 000007
【図６】
2010503094.tif 000008
【図７】
2010503094.tif 000009
【図８】
2010503094.tif 000010
【図９】
2010503094.tif 000011
【図１０】
2010503094.tif 000012
【図１１】
2010503094.tif 000013
【図１２】
2010503094.tif 000014
【図１３】
2010503094.tif 000015
【図１４】
2010503094.tif 000016
【図１５】
2010503094.tif 000017
【図１６】
2010503094.tif 000018
【図１７】
2010503094.tif 000019
【図１８】
2010503094.tif 000020
2010503094.tif 000021
2010503094.tif 000022
2010503094.tif 000023
2010503094.tif 000024
2010503094.tif 000025
2010503094.tif 000026
2010503094.tif 000027
2010503094.tif 000028
2010503094.tif 000029
2010503094.tif 000030
2010503094.tif 000031
2010503094.tif 000032
2010503094.tif 000033
2010503094.tif 000034
2010503094.tif 000035
2010503094.tif 000036
2010503094.tif 000037
2010503094.tif 000038
【手続補正書】
【提出日】平成21年6月16日(2009.6.16)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
データを管理するための方法であって、
キーによって特定されるエントリへの挿入操作又は更新操作を表す第１のデータ構造を準備すること、及び、分岐作成操作を表す第２のデータ構造を準備することであって、前記第２のデータ構造は分岐識別子及び分岐タイミング情報を格納する、ことと、
読み取りタイムスタンプにおけるデータのバージョンを検索する要求を受信することと、
データのそのバージョンを探し出すために、前記第１のデータ構造及び前記第２のデータ構造を走査することと、
要求されたタイムスタンプにおけるデータのバージョンによって開始する分岐を作成する要求を受信することと、
それに応じて前記第２のデータ構造を更新することと、
を含む方法。
【請求項２】
前記第１のデータ構造はＢ木である、請求項１に記載の方法。
【請求項３】
所与のキーと関連する値を更新する要求を受信することと、前記第１のデータ構造を更新することとを含む、請求項１に記載の方法。
【請求項４】
前記更新することは、前記所与のキー及び関連するデータ並びに現在のタイムスタンプを持つ新規のエントリを追加することによって実施される、請求項３に記載の方法。
【請求項５】
前記キーは論理ブロック・アドレスである、請求項１に記載の方法。
【請求項６】
分岐を作成する前記要求は差し戻し操作であり、特定のタイムスタンプは差し戻し時間である、請求項１に記載の方法。
【請求項７】
分岐を探すことが、分岐タイミング情報を走査することを含む、請求項１に記載の方法。
【請求項８】
データ・ストレージ・ポリシーに応じて前記第１のデータ構造及び前記第２のデータ構造をリフレッシュすることを含む、請求項１に記載の方法。
【請求項９】
前記リフレッシュすることは、前記第２のデータ構造のエントリの粗分析を実施することを含む、請求項８に記載の方法。
【請求項１０】
前記リフレッシュすることは、前記第１のデータ構造及び前記第２のデータ構造のエントリの精密分析を実施することを含む、請求項８に記載の方法。
【請求項１１】
前記リフレッシュすることは、少なくとも１つの関連ウィンドウに応じて行われる、請求項８に記載の方法。
【請求項１２】
前記リフレッシュすることは、少なくとも１つのデータ・ストレージ粒度に応じて行われる、請求項８に記載の方法。
【請求項１３】
前記リフレッシュすることは、現時点からの時間経過に対応する多数のデータ・ストレージ粒度に応じて行われる、請求項８に記載の方法。
【請求項１４】
前記リフレッシュすることは、前記第１のデータ構造の１つのエントリと前記第１のデータ構造のエントリのサブセットとの間の関係に応じて行われる、請求項８に記載の方法。
【請求項１５】
前記リフレッシュすることは、前記第１のデータ構造の１つのエントリと前記第１のデータ構造のエントリ群との間の関係に応じて行われる、請求項８に記載の方法。
【請求項１６】
前記分岐タイミング情報は、分岐開始時間と分岐終了時間と前記要求されたタイムスタンプとを含む、請求項１に記載の方法。
【請求項１７】
ネットワーク上で顧客にサービスを提供する方法であって、前記サービスは、
ネットワーク上で、読み取りタイムスタンプにおけるデータのバージョンを検索する要求を受信することと、
データのそのバージョンを探し出すために第１のデータ構造及び第２のデータ構造を走査することであって、前記第１のデータ構造はキーによって特定されるエントリへの挿入操作又は更新操作を表し、前記第２のデータ構造は分岐作成操作を表し、前記第２のデータ構造は分岐識別子及び分岐タイミング情報を格納する、ことと、
前記読み取りタイムスタンプにおけるデータの前記バージョンを提供することと、
ネットワーク上で、要求されたタイムスタンプにおけるデータのバージョンによって開始する分岐を作成する要求を受信することと、
それに応じて前記第２のデータ構造を更新することと、
を含む、方法。
【請求項１８】
前記第１のデータ構造はＢ木である、請求項１７に記載の方法。
【請求項１９】
ネットワーク上で、所与キーと関連する値を更新する要求を受信することと、前記第１のデータ構造を更新することとを含む、請求項１７に記載の方法。
【請求項２０】
請求項１〜１６記載の何れか１項の方法の各ステップをコンピュータに実行させる、コンピュータ・プログラム。
【国際調査報告】
2010503094.tif 000039