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