(57)【特許請求の範囲】
【請求項１】
ストレージ中のデータを管理するためのコンピュータ・プログラムであって、
ログ中のレコードに対する索引を提供することであって、前記索引中の各索引エントリが、前記レコードのうちの１つの、前記ログ中のログ・アドレスを識別し、前記ログ中の
各レコードがキーおよび値を含み、前記ログ・アドレスが前記ストレージ中の物理アドレスにマッピングされる、前記提供することと、
前記ログ中の複数の処理対象ログ・アドレスを処理することとを含み、前記処理することは、前記ログ・アドレスのそれぞれにつき、
前記処理対象ログ・アドレスが前記ログ中の前記レコードの現バージョンを含むことを前記索引が示すかどうかを決定することと、
前記処理対象ログ・アドレスが前記レコードの前記現バージョンを含むことを前記索引が示すと決定されるのに応答して、前記処理対象ログ・アドレスにおける前記レコードの現バージョンを前記ログの末尾において選択されたログ・アドレスに追加することと、
前記処理対象ログ・アドレスが現バージョンを含まないことを決定されるのに応答して、前記処理対象ログ・アドレスがマッピングされる前記ストレージ中の前記物理アドレスにおけるレコードを削除することと、
前記処理対象ログ・アドレスにおける前記レコードの現バージョンを前記ログの末尾において選択されたログ・アドレスに追加されるのに応答して、前記処理対象ログ・アドレスがマッピングされる前記ストレージ中の前記物理アドレスにおけるレコードを削除することと、を含む動作をコンピュータに実行させる、コンピュータ・プログラム。
【請求項２】
前記処理対象ログ・アドレスが前記レコードの前記現バージョンを有することを前記索
引が示すかどうかを決定することが、
前記処理対象ログ・アドレスにおける前記レコードの前記キーに対して前記処理対象ログ・アドレスを前記索引が示すかどうかを決定することを含み、前記処理対象ログ・アド
レスにおける前記レコードの前記キーを有する前記索引エントリ中で前記処理対象ログ・アドレスが示されることに応答して、前記処理対象ログ・アドレスが前記レコードの前記現バージョンを含むことを前記索引が示す、請求項１に記載のコンピュータ・プログラム。
【請求項３】
前記処理対象ログ・アドレスを処理することがさらに、
前記ログ中の前記選択されたログ・アドレスを示し、前記処理対象ログ・アドレスを示さないように、前記索引を更新することを含む、請求項１に記載のコンピュータ・プログ
ラム。
【請求項４】
前記処理対象ログ・アドレスを処理することがガベージ・コレクション・プロセスによって実施され、処理される前記複数のログ・アドレスが前記ログ中のログ・アドレスのサブセットを含み、前記ログ中の前記ログ・アドレスが、前記処理対象ログ・アドレスを有する前記サブセットを含む複数のサブセットにグループ化される、請求項１に記載のコンピュータ・プログラム。
【請求項５】
前記ストレージが複数のストレージ・デバイスを含み、前記処理対象ログ・アドレスが前記複数のストレージ・デバイス中の物理アドレスにマッピングされ、前記ログ中の前記レコードについてのデータが、前記レコードを識別する前記処理対象ログ・アドレスにマッピングする前記ストレージ・デバイス中の前記物理アドレスに記憶される、請求項１に記載のコンピュータ・プログラム。
【請求項６】
前記ストレージ・デバイスが固体ドライブとハード・ディスク・ドライブとのうちの少なくとも一方を含み、前記コンピュータ・プログラム、索引、およびログが、前記ストレージ・デバイスの外部の、前記ストレージ・デバイスが結合されたシステム中で実装される、請求項５に記載のコンピュータ・プログラム。
【請求項７】
前記処理対象ログ・アドレスと、前記処理対象ログ・アドレスにおける前記レコードのキーとのエントリを前記索引が含まないと決定されるのに応答して、前記処理対象ログ・アドレスにおける前記レコードが、選択されたログ・アドレスに書き込まれない、請求項１に記載のコンピュータ・プログラム。
【請求項８】
前記動作がさらに、  前記処理対象ログ・アドレスと前記処理対象ログ・アドレスのキーとを含むｌｉｖｅコマンドをストレージ・サービスによって索引サービスに送ることであって、前記索引サービスが、前記ｌｉｖｅコマンドに応答して、前記処理対象ログ・アドレスが前記レコードの前記現バージョンを有するかどうかの決定を実施する、前記送ることと、
前記処理対象ログ・アドレスにおける前記レコードを前記選択されたログ・アドレスに書き込むことを実施するために、ｐｕｔコマンドを前記索引サービスによって前記ストレージ・サービスに送ることと、
前記処理対象ログ・アドレスにおける前記レコードを前記選択されたログ・アドレスに書き込むのに応答して、前記レコードの前記選択されたログ・アドレスを前記ストレージ・サービスによって前記索引サービスに送ることと、
前記選択されたログ・アドレスを前記ストレージ・サービスから受け取るのに応答して、前記索引サービスによって、前記ｐｕｔコマンド中の前記処理対象ログ・アドレスと前記キーとを有する前記索引エントリを、前記選択されたログ・アドレスを示すように更新することと、  を含む、請求項１に記載のコンピュータ・プログラム。
【請求項９】
前記動作がさらに、
前記ｌｉｖｅコマンドに応答して前記処理対象ログ・アドレスが前記レコードの前記現バージョンを含むことを前記索引サービスが示すのに応答して、前記キーと前記処理対象ログ・アドレスとを含むｍｏｖｅコマンドを前記ストレージ・サービスによって送ることと、
前記ｍｏｖｅコマンドを前記索引サービスによって受け取ることであって、前記索引サービスが、前記ｍｏｖｅコマンドに応答して、前記処理対象ログ・アドレスにおけるレコードを前記選択されたログ・アドレスに書き込むために前記ｐｕｔコマンドを前記ストレージ・サービスに送ることを実施し、前記ｐｕｔコマンドが前記キーに対する前記値を含む、前記受け取ることとを含む、請求項８に記載のコンピュータ・プログラム。
【請求項１０】
前記ストレージ・サービスが、前記処理対象ログ・アドレスがマッピングされる前記ストレージ中の前記物理アドレスにおける前記レコードの削除を実施する、請求項８に記載
のコンピュータ・プログラム。
【請求項１１】
ストレージ中のデータを管理するためのシステムであって、
プロセッサを含む、
ログ中のレコードに対する索引を提供することであって、前記索引中の各索引エントリが、前記レコードのうちの１つの、前記ログ中のログ・アドレスを識別し、前記ログ中の
各レコードがキーおよび値を含み、前記ログ・アドレスが前記ストレージ中の物理アドレスにマッピングされる、前記提供することと、
前記ログ中の複数の処理対象ログ・アドレスを処理することとを含み、前記処理することは、前記ログ・アドレスのそれぞれにつき、
前記処理対象ログ・アドレスが前記ログ中の前記レコードの現バージョンを含むことを前記索引が示すかどうかを決定することと、
前記処理対象ログ・アドレスが前記レコードの前記現バージョンを含むことを前記索引が示すと決定されるのに応答して、前記処理対象ログ・アドレスにおける前記レコードの現バージョンを前記ログの末尾において選択されたログ・アドレスに追加することと、
前記処理対象ログ・アドレスが現バージョンを含まないことを決定されるのに応答して、前記処理対象ログ・アドレスがマッピングされる前記ストレージ中の前記物理アドレスにおけるレコードを削除することと、
前記処理対象ログ・アドレスにおける前記レコードの現バージョンを前記ログの末尾において選択されたログ・アドレスに追加されるのに応答して、前記処理対象ログ・アドレスがマッピングされる前記ストレージ中の前記物理アドレスにおけるレコードを削除することと、
を含む動作を前記プロセッサに実施させる、システム。
【請求項１２】
ストレージ中のデータを管理するための方法であって、
ログ中のレコードに対する索引を提供することであって、前記索引中の各索引エントリが、前記レコードのうちの１つの、前記ログ中のログ・アドレスを識別し、前記ログ中の
各レコードがキーおよび値を含み、前記ログ・アドレスが前記ストレージ中の物理アドレスにマッピングされる、前記提供することと、
前記ログ中の複数の処理対象ログ・アドレスを処理することとを含み、前記処理することは、前記ログ・アドレスのそれぞれにつき、
前記処理対象ログ・アドレスが前記ログ中の前記レコードの現バージョンを含むことを前記索引が示すかどうかを決定することと、
前記処理対象ログ・アドレスが前記レコードの前記現バージョンを含むことを前記索引が示すと決定されるのに応答して、前記処理対象ログ・アドレスにおける前記レコードの現バージョンを前記ログの末尾において選択されたログ・アドレスに追加することと、
前記処理対象ログ・アドレスが現バージョンを含まないことを決定されるのに応答して、前記処理対象ログ・アドレスがマッピングされる前記ストレージ中の前記物理アドレスにおけるレコードを削除することと、
前記処理対象ログ・アドレスにおける前記レコードの現バージョンを前記ログの末尾において選択されたログ・アドレスに追加されるのに応答して、前記処理対象ログ・アドレスがマッピングされる前記ストレージ中の前記物理アドレスにおけるレコードを削除することと、
を実施することによって行う、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ログ構造に従ったストレージ中のデータを管理するための、コンピュータ・プログラム、システム、および方法に関する。
【背景技術】
【０００２】
ログ構造化ストレージ・システム中では、データに対する更新は、本来の場所には書かれず、選択された論理および物理アドレスに書かれる。データは、キー−値ストアに記憶されてよく、この場合、データは、そのレコードに関連するキーおよび値からなる、非構造化レコードに記憶される。ログ中のレコードに対するキーおよびログ・アドレスを有する索引を使用して、レコードについてのログ中でのログ・アドレスをルックアップすることができる。各索引エントリは、名前空間中でまたはデータのセット中で特有の索引付きキーと、ログ中でのデータのアドレスとを有する。
【０００３】
ログ構造化ストレージ中では、更新はログの末尾に書かれ、ログ中のレコードの前バージョンは残る。ログ中のログ・アドレスにおけるエントリが、ログ・アドレスを識別する対応する索引エントリをもはや有しないときは、ログ中のエントリは未使用と見なされ、ガベージ・コレクトされることが可能である。しかし、ガベージ・コレクションの粒度（「領域／スロット」）は、データ（キー−値レコード）の粒度よりもずっと大きい（粗い）ので、スロット全体をガベージ・コレクトするためには、スロット中の潜在的に有効ないくつかのエントリが再配置されなければならないことがある。索引が古い場所をまだ指している再配置されたエントリをルックアップするために、ストレージ層は、古いエントリを新しいエントリにマッピングする間接参照テーブルを維持することができる。レコードについての現アドレスを提供するために索引が利用可能でないとき、間接参照テーブルを使用して、レコードを求める要求を古いアドレスから新しいアドレスにリダイレクトする。間接参照の結果、ルックアップ時間はより長くなり、古いアドレスから新しいアドレスにマッピングするための性能ペナルティが生じ、この新しいアドレスは、次いで、レコードにアクセスするために物理アドレスにマッピングされなければならない。
【０００４】
ガベージ・コレクションを実施するための別の技法は、すべてのデータを読み取って再利用空間に書き直す、圧縮プロセスである。この技法は、ライブ・データと古いデータの両方を移動させて、後で受け取られるデータに利用可能にするための空間を解放することを必要とする。圧縮は、ライブ・データと削除されるデータの両方が読み取られて新しい空間に書き込まれる必要があるので、入出力集約的である。
【０００５】
古くなったレコードを示すトゥームストーン（tombstone）レコードをストレージ層がログ中に配置する実施形態では、ガベージ・コレクションは、削除すべきレコードを決定するために、ログを走査してトゥームストーン・レコードを処理しなければならない。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ストレージ・システムのガベージ・コレクションを、特にログ構造化ストレージ・システム中で実施するための改善された技法が、当技術分野で必要とされている。
【課題を解決するための手段】
【０００７】
第１の態様によれば、ストレージ中のデータを管理するためのコンピュータ・プログラムが提供される。コンピュータ・プログラムは、動作を実施するために実行されるコンピュータ可読プログラム・コードが組み入れられたコンピュータ可読ストレージ媒体を含む。動作は、ログ中のレコードに対する索引を提供することであって、索引中の各索引エントリが、レコードのうちの１つの、ログ中のログ・アドレスを識別し、ログ中の各レコードがキーおよび値を含み、ログ・アドレスがストレージ中の物理アドレスにマッピングされる、提供することと、ログ中の複数の処理対象ログ・アドレスを処理することとを含み、処理することは、ログ・アドレスのそれぞれにつき、処理対象ログ・アドレスがログ中のレコードの現バージョンを含むことを索引が示すかどうかを決定することと、処理対象ログ・アドレスがレコードの現バージョンを含むことを索引が示すと決定されるのに応答して、処理対象ログ・アドレスにおけるレコードをログ中の選択されたログ・アドレスに追加することと、処理対象ログ・アドレスがマッピングされるストレージ中の物理アドレスにおけるレコードを削除することと、を実施することによって行う。
【０００８】
第２の態様によれば、ストレージ中のデータを管理するためのシステムが提供される。システムは、プロセッサと、実行されたときに動作を実施するコンピュータ可読プログラム・コードが組み入れられたコンピュータ可読ストレージ媒体とを備える。動作は、ログ中のレコードに対する索引を提供することであって、索引中の各索引エントリが、レコードのうちの１つの、ログ中のログ・アドレスを識別し、ログ中の各レコードがキーおよび値を含み、ログ・アドレスがストレージ中の物理アドレスにマッピングされる、提供することと、ログ中の複数の処理対象ログ・アドレスを処理することとを含み、処理することは、ログ・アドレスのそれぞれにつき、処理対象ログ・アドレスがログ中のレコードの現バージョンを含むことを索引が示すかどうかを決定することと、処理対象ログ・アドレスがレコードの現バージョンを含むことを索引が示すと決定されるのに応答して、処理対象ログ・アドレスにおけるレコードをログ中の選択されたログ・アドレスに追加することと、処理対象ログ・アドレスがマッピングされるストレージ中の物理アドレスにおけるレコードを削除することと、を実施することによって行う。
【０００９】
第３の態様によれば、ストレージ中のデータを管理するための方法が提供される。方法は、ログ中のレコードに対する索引を提供することであって、索引中の各索引エントリが、レコードのうちの１つの、ログ中のログ・アドレスを識別し、ログ中の各レコードがキーおよび値を含み、ログ・アドレスがストレージ中の物理アドレスにマッピングされる、提供することと、ログ中の複数の処理対象ログ・アドレスを処理することとを含み、処理することは、ログ・アドレスのそれぞれにつき、処理対象ログ・アドレスがログ中のレコードの現バージョンを含むことを索引が示すかどうかを決定することと、処理対象ログ・アドレスがレコードの現バージョンを含むことを索引が示すと決定されるのに応答して、処理対象ログ・アドレスにおけるレコードをログ中の選択されたログ・アドレスに追加することと、処理対象ログ・アドレスがマッピングされるストレージ中の物理アドレスにおけるレコードを削除することと、を実施することによって行う。
【００１０】
好ましい一実施形態によれば、ログ構造に従ったストレージ中のデータを管理するための、コンピュータ・プログラム、システム、および方法が提供される。この好ましい実施形態によれば、ログ中のレコードに対する索引はエントリを有し、索引中の各索引エントリは、レコードのうちの１つの、ログ中のログ・アドレスを識別する。ログ中の各レコードは、キーおよび値を含むことが好ましく、ログ・アドレスは、ストレージ中の物理アドレスにマッピングされることが好ましい。ログ中の複数の処理対象ログ・アドレスが処理されるが、これは、各ログ・アドレスにつき、処理対象ログ・アドレスがログ中のレコードの現バージョンを含むことを索引が示すかどうかを決定することと、処理対象ログ・アドレスがレコードの現バージョンを含むことを索引が示すと決定されるのに応答して、処理対象ログ・アドレスにおけるレコードをログ中の選択されたログ・アドレスに追加することと、処理対象ログ・アドレスがマッピングされるストレージ中の物理アドレスにおけるレコードを削除することと、を実施することによって行う。
【００１１】
次に、本発明の好ましい実施形態について、後続の図面を参照しながら単なる例として述べる。
【図面の簡単な説明】
【００１２】
【図１】ストレージ環境の実施形態を示す図である。
【図２】索引エントリの実施形態を示す図である。
【図３】ログ・ストレージ中のレコードの実施形態を示す図である。
【図４】論理−物理マッピングの実施形態を示す図である。
【図５】ｍｏｖｅコマンドの実施形態を示す図である。
【図６】ＰＵＴコマンドの実施形態を示す図である。
【図７】ログ構造化ストレージのガベージ・コレクションを実施するための動作の実施形態を示す図である。
【図８】ログ構造化ストレージのガベージ・コレクションを実施するための動作の実施形態を示す図である。
【図９】述べる実施形態と共に使用されるコンピュータ・アーキテクチャの実施形態を示す図である。
【発明を実施するための形態】
【００１３】
述べる実施形態は、ログ構造化ストレージのガベージ・コレクションを実施するための技法を提供し、この場合、ログは、ログ構造に従って、１つまたは複数のストレージ・デバイス中の物理アドレスにマッピングするログ・アドレスにおけるレコードを有する。ログの索引は、キーとログ・アドレスとを有する索引エントリを有する。ログ中の各レコードは、そのレコードに対する索引エントリ中で識別される、キー−値を含む。ログ・アドレスは、ストレージ中の物理アドレスにマッピングするログ・オフセットを記述することができる。ログ中の複数のレコードは、処理対象レコードがログ中のレコードの現バージョンを含むことを索引が示すかどうかを決定することによって、処理される。レコードが現バージョンである場合は、レコードは、ログ中の選択されたログ・アドレスに書き込まれる。処理対象レコードはログ中で削除されて、削除された処理対象レコードのログ・アドレスにマッピングするストレージ中のストレージ空間が再利用される。さらに、選択されたログ・アドレスに移動させるデータの現バージョンである処理されたレコードに対する索引エントリは、ログ中の新しい選択されたログ・アドレスを示すように更新される。
【００１４】
いくつかの実施形態は、間接参照テーブルを使用する必要をなくすことができる。というのは、ガベージ・コレクション・プロセスの一部として、索引がレコードの新しいアドレスで更新され、したがって、ログ中のレコードについて古いアドレスと新しいアドレスとの間で変換する必要がないからである。さらに、述べる実施形態によれば、ログ中の、ライブ・データすなわち有効なデータを有するレコードのみが、ログ中の新しい場所に書き込まれ、それにより、すべてのデータ・レコードを読み取って移動させる必要がなくなる。その代り、述べる実施形態では、索引を使用して、ログの末尾に移動させる必要のあるライブ・レコードを決定する。ライブ・データを有するすべてのレコードをログの末尾に移動させた後、処理されたログ・エントリ中のすべてのレコードは削除されてよく、したがって、圧縮ガベージ・コレクション動作に必要とされる集約的な入出力動作が回避される。
【００１５】
図１に、１つまたは複数のストレージ・デバイス１０２上のデータのストレージを管理するストレージ・マネージャ１００を有するストレージ環境を示す。ホスト・システム（図示せず）が、入出力（Ｉ／Ｏ）要求をストレージ・マネージャ１００に通信して、ストレージ・デバイス１０２中のデータにアクセスすることができる。ストレージ・マネージャ１００は、１つまたは複数のプロセッサ・デバイスを含むプロセッサ１０４と、メモリ１０６とを備え、メモリ１０６には、プロセッサ１０４によって実行されるようにオペレーティング・システム１０８がロードされる。オペレーティング・システム１０８は、ログ１１２を管理するためのストレージ・サービス１１０を備え、ログ１１２は、ストレージ・デバイス１０２中の場所に記憶されたデータを識別するレコードを有する。ストレージ・サービス１１０は、論理−物理マッピング４００を維持し、論理−物理マッピング４００は、ログ１１２中のレコードのログ・アドレスを、ストレージ・デバイス１０２中の物理アドレスにマッピングする。索引サービス１１６が、索引２００を維持し、ログ１１２中のレコードの、キー−ログ・アドレス・ルックアップを可能にする。索引サービス１１６は、ログ・アドレスに対する示されたキーを有するレコードの現バージョンを有するログ・アドレスを示す。ログ１１２は連続的なログを含むことができ、ログ構造化アレイ・データ構造などのように、新しいレコードはログの末尾に、すなわち一番最近使用された末尾に追加される。ストレージ・サービス１１０は、索引２００を使用して、ログ１１２中のレコードをルックアップし、ログ１１２中のログ・アドレスにおけるレコードがレコードの現バージョンまたはライブ・バージョンを有するかどうかを決定する。ストレージ・マネージャ１００は、複数のホスト・システムからのＩ／Ｏ要求を管理するサーバ中で実装されてもよく、または、システム中のストレージ・コントローラ・ファームウェアもしくは他のコンポーネント中で実装されてもよい。
【００１６】
提供されたキーおよび値を有するレコードに関連するデータを求める要求が受け取られると、ストレージ・サービス１１０は、索引サービス１１６を呼び出して、その指定されたキーを有する索引２００中のレコードのログ・アドレスをルックアップすることができる。索引から返されたログ・アドレスから、ストレージ・サービス１１０は、要求されたレコードのキーおよび値を有するログ・アドレス・レコードを決定することができる。ログ１１２中のログ・アドレスから、ストレージ・サービス１１０は、論理−物理マッピング４００を使用して、ストレージ・デバイス１０２のうちの１つにおける、ログ・アドレスにおけるレコードについてのデータが記憶された物理アドレスを決定することができる。
【００１７】
ストレージ・マネージャ１００は、接続１２０を介してストレージ・デバイス１０２と通信する。接続１２０は、ローカル・エリア・ネットワーク（ＬＡＮ）、ストレージ・エリア・ネットワーク（ＳＡＮ）、ワイド・エリア・ネットワーク（ＷＡＮ）、ピアツーピア・ネットワーク、ワイヤレス・ネットワーク、インターネット、イントラネットなど、１つまたは複数のネットワークを含むことができる。別法として、接続１２０は、ＰＣＩ（Peripheral Component Interconnect）バスやシリアル・インタフェースなど、バス・インタフェースを含むこともできる。
【００１８】
ストレージ・デバイス１０２は、固体電子回路からなる固体ストレージ・デバイス（ＳＳＤ）、ＥＥＰＲＯＭ（電気的に消去可能プログラム可能な読取専用メモリ）、フラッシュ・メモリ、フラッシュ・ディスク、ランダム・アクセス・メモリ（ＲＡＭ）ドライブ、ストレージクラス・メモリ（ＳＣＭ）、相変化メモリ（ＰＣＭ）、抵抗変化型メモリ（ＲＲＡＭ）、スピン・トランスファ・トルク・メモリ（ＳＴＭ−ＲＡＭ）、導電性ブリッジングＲＡＭ（ＣＢＲＡＭ）、磁気ハード・ディスク・ドライブ、光学ディスク、テープなど、様々なタイプまたは種類のストレージ・デバイスを含むことができる。ストレージ・デバイス１０２はさらに、ＪＢＯＤ（Just a Bunch of Disks）、直接アクセス・ストレージ・デバイス（ＤＡＳＤ）、ＲＡＩＤ（Redundant Array of Independent Disks）アレイ、仮想化デバイスなど、デバイスのアレイに構成されてもよい。さらに、ストレージ・デバイス１０２は、異なるベンダまたは同じベンダからの異種ストレージ・デバイスを含むこともできる。
【００１９】
図１では、ストレージ・サービス１１０と索引サービス１１６とを、同じオペレーティング・システム１０８中のコンポーネントとして示す。別法として、ストレージ・サービス１１０または索引サービス１１６あるいはその両方は、オペレーティング・システム１０８のカーネル空間ではなく、ユーザ空間で実行されるアプリケーション・プログラムを含むこともできる。さらに、ストレージ・サービス１１０と索引サービス１１６とは、異なるコンピュータもしくは異なるコンピュータ・ノード中で実装して、ネットワークを介して通信するようにしてもよく、または、ストレージ・コントローラ以外のシステム中で実装してもよい。別法として、ストレージ・サービス１１０と索引サービス１１６とは、特定用途向け集積回路（ＡＳＩＣ）などのハードウェア・ロジックを用いて実装してもよく、または、コンピュータ可読ストレージ媒体中のコードを実行するプログラム可能プロセッサとして実装してもよい。ストレージ・サービス１１０と索引サービス１１６とはまた、仮想マシン中で実装してもよい。
【００２０】
図２は、索引２００中の索引エントリ２００ｉのインスタンスの一実施形態を示し、キー２０２とログ・アドレス２０４とのペアを含む。ログ・アドレス２０４は、索引エントリ２００ｉによって識別されるレコードの、ログ１１２中の場所を識別する。ログ１１２中には、レコードの、すなわち一意のキー−値ペアの、複数のバージョンがある場合があるが、索引２００は、レコードの現バージョンを有するログ・アドレスを提供するために、キーおよびログ・アドレスに対して、１つの索引エントリ２００ｉのみを含むことになる。ログ１１２中の、ログ・アドレスが索引２００に含まれないキー−値ペアについての他のレコードは、レコードによって識別されるデータの最新バージョンを有しないストレージ・デバイス１０２中の物理アドレスにマッピングする、レコードの非アクティブなまたは前のバージョンを含む。
【００２１】
図３は、ログ１１２に含まれるレコード３００ｉのインスタンスの一実施形態を示し、キー３０２と値３０４とのペアを含む。レコード３００ｉはさらに、ログ１１２中の、レコードの前バージョンを有するログ・アドレスへのポインタを含むこともできる。ログ１１２は、レコードを連続的な順序で記憶することができ、したがって、新しいレコードは、図１に示されるエントリ１１２ｅなど、ログの末尾に追加される。レコード３００ｉはさらに、キー・サイズおよび値サイズを示すこともできる。
【００２２】
図４は、論理−物理マッピング４００中のエントリ４００ｉの一実施形態を示し、ログ・アドレス４０２と、ストレージ・デバイス１０２のうちの１つにおける対応するデバイス物理アドレス４０４とを含む。デバイス物理アドレス４０４は、ネットワーク・アドレス（例えば、インターネット・プロトコル・アドレス、ＭＡＣアドレス）と、一意のデバイスＩＤと、ストレージ・デバイス１０２中の物理的場所とを含むことができる。このようにして、マッピング４００は、場合に応じて複数のストレージ・デバイス１０２にわたってまたは単一のストレージ・デバイス１０２中で、ログ１１２中のログ１１２のアドレスまたはエントリを物理アドレスにマッピングする。例えば、２つのストレージ・デバイスがある場合、ログ１１２は、第１のストレージ・デバイス中の連続的なアドレスにデータを記憶し、次いで第２のストレージ・デバイス中のアドレスにデータを記憶することを可能にする、抽象化を含むことができる。代替実施形態では、論理−物理マッピング４００は、ストレージ・デバイス間で交互配置するように連続的なログ・アドレスのマッピングを提供することができ、それにより、データの記憶は、論理−物理マッピング４００中で実装される事前定義済みのシーケンスに従って、ストレージ・デバイスのうちの異なるストレージ・デバイス中で交互に行われる。
【００２３】
図５に、ガベージ・コレクションまたは他の動作の一部として、レコードをログの末尾１１２ｅの新しいログ・アドレスに移動させることを索引サービス１１６に行わせるために、ストレージ・サービス１１０が発行できるｍｏｖｅコマンド５００の一実施形態を示す。ｍｏｖｅコマンド５００は、ｍｏｖｅコマンドを識別するｍｏｖｅコマンド・コード５０２と、キー５０４と、キー値５０６と、ログの末尾１１２ｅに移動すべき、キー５０４と値５０６とのペアを有するレコードのログ・アドレス５０８とを含む。
【００２４】
図６に、ログの末尾１１２ｅに、またはどのような場所であろうとログ１１２の一番最近使用された末尾に、新しいレコードを追加するために、索引サービス１１６によって使用されるＰＵＴコマンド６００の一実施形態を示す。ＰＵＴコマンド６００は、ＰＵＴコマンド・コード６０２と、キー６０４と、キー値６０６と、キー６０４および値６０６によって更新されているレコードのログ・アドレス６０８とを含み、追加されるレコードは、ログの一番最近使用された末尾１１２ｅに追加される。ストレージ・サービス１１０は、コマンド６００のキー６０４および値６０６を有するレコードが追加された、ログ中の場所１１２ｅのログ・アドレスを返すことができる。
【００２５】
図５および６の情報を含めるのに使用されるコマンドは、ＭＯＶＥコマンドおよびＰＵＴコマンド以外のコマンド・タイプも含み得る。
【００２６】
図７に、ガベージ・コレクションを実施してログ１１２およびストレージ１０２中または他のコンポーネント中の空間を再利用するために、ストレージ・サービス１１０や索引サービス１１６などのストレージ・マネージャ１００のコンポーネントによって実施される動作の一実施形態を示す。ガベージ・コレクション動作を開始すると（ブロック７００で）、ログ１１２中のログ・アドレスのサブセットの複数の処理対象ログ・アドレスのそれぞれにつき、動作のループがブロック７０２〜７１６で実施される。各サブセットは、ログ１１２中の固定範囲の連続的なログ・アドレス・レコードを含むことができる。サブセットの処理対象ログ・アドレスｉについて、処理対象ログ・アドレスｉがレコードの現バージョンを含むことを索引２００が示すかどうかが決定される（ブロック７０４で）。いくつかの実施形態では、ログ・アドレスがレコードの現バージョンを有するかどうかの決定は、ログ１１２中のレコードのログ・アドレスが、処理対象ログ・アドレスｉにおけるレコードのキーを有する、索引２００ｉのエントリ中で示されるかどうかを決定することを含むことができる。このような実施形態では、索引２００は、示されたキーを有するレコードの現バージョンを有するログ・アドレスを示すエントリを含む。このようにして、処理対象ログ・アドレスｉは、ログ１１２中のこのログ・アドレスｉが、処理対象ログ・アドレスｉについてのレコード３００ｉ中のキー２０２を有する索引エントリ２００ｉのログ・アドレス２０４中で示されるとき、レコードの現バージョンを有する。
【００２７】
処理対象ログ・アドレスｉがこのレコード（キー−値ペア）の現バージョンを有する（ブロック７０４で）場合は、ログの一番最近に使用された（ＭＲＵ）末尾１１２ｅにおけるログ・アドレスなど、ログ１１２中の選択されたログ・アドレスに、このレコードｉが書き込まれる（ブロック７０６で）。選択されたログ・アドレスにマッピングする、ストレージ・デバイス１０２のうちの１つにおける物理アドレスの決定が、論理−物理マッピング４００から行われる（ブロック７０８で）。次いで、ストレージ・サービス１１０は、ストレージ・デバイス１０２中のレコードｉの現バージョンについてのデータを、ストレージ・デバイス１０２中の決定された物理アドレスに書き込むことができる（ブロック７１０で）。次いで、索引サービス１１６は、処理対象ログ・アドレスｉにおけるレコードをコピーまたは移動させた先である、ログ１１２中の選択されたログ・アドレス２０６を示すように、キー２０２と処理対象ログ・アドレスｉとを有する索引エントリ２００ｉを更新することができる（ブロック７１２で）。次いで、処理対象ログ・アドレスｉがマッピングされるストレージ・デバイス１０２中の空間を再利用するために、処理対象ログ・アドレスｉに対する論理−物理マッピング・エントリ４００ｉに従って処理対象ログ・アドレスｉがマッピングされるストレージ・デバイス１０２中の物理アドレスにおけるレコードは、ログ１１２から削除されてよい（ブロック７１４で）。さらに、レコードｉがレコードの現バージョンでない（すなわち、そのログ・アドレスがレコードｉに対する索引エントリ中で示されない）（ブロック７０４で）場合は、制御はブロック７１４に進み、レコードのサブセット中でレコードｉが処理されたログ・アドレスから、レコードｉが削除される。このようにして、非アクティブなデータを有するログ・アドレスにマッピングするストレージ・デバイス１０２中のデータは削除される。ブロック７１４から、制御はブロック７１６に進み、サブセット中のまだ処理されていないログ・アドレスが他にあればそれらが処理される。
【００２８】
述べた図７の動作により、ログ１１２中のログ・アドレスのサブセットが処理されて、現レコードまたはアクティブなレコードがあればそれらはログの一番最近使用された末尾１１２ｅにコピーされ、処理対象ログ・アドレスにおけるレコードのより古いバージョンについてのデータは除去される。ログ・アドレスのサブセットの処理の終わりには、アクティブなレコードがあればそれらはログの末尾１１２ｅに移動させており、ストレージ・デバイス１０２中のデータのより古いバージョンは削除され、他のレコードについては、ストレージ・デバイス１０２中のデータは、選択された新しいログ・アドレスに対応する物理アドレスにコピーされる。次いで、ストレージ・デバイス１０２中の、サブセット中の処理対象ログ・アドレスにマッピングする物理アドレスにおけるデータを削除することによって、サブセット中のレコードは再利用することができる。これにより、レコードおよびデータのより古いバージョンを除去して、新しい書込みのためにストレージ・デバイス１０２中の空間を解放することができる。さらに、処理対象ログ・アドレスは、さらに他のアクティブなデータに利用可能になるように無効化されてよい。
【００２９】
図８に、ログ１１２中のログ・アドレスのサブセットに対してガベージ・コレクション動作を実施するために、ストレージ・サービス１１０および索引サービス１１６によって実施される動作の一実施形態を示す。制御は、ストレージ・サービス１１０がガベージ・コレクション動作を開始する（ブロック８００で）ことで開始し、これは、ログ１１２中のログ・アドレスのサブセットからの複数のログ・アドレスの各処理対象ログ・アドレスｉにつき、動作のループをブロック８０２〜８２６で実施することによって行う。ブロック８０４で、ストレージ・サービス１１０は、処理対象ログ・アドレスｉがレコードの現バージョンを有するかどうかを索引サービス１１６に決定させるために、ログ・アドレスｉと処理対象ログ・アドレスｉに対するキーとを含むｌｉｖｅコマンドを送る。ｌｉｖｅコマンドに応答して、索引サービス１１６は、ｌｉｖｅコマンド中で示されるキーおよび処理対象ログ・アドレスｉに対するエントリ２００ｉを索引２００が有するかどうかを決定する（ブロック８０８で）。エントリ２００ｉが存在することは、処理対象ログ・アドレスｉがレコードの現バージョンを有することを示す。
【００３０】
処理対象ログ・アドレスｉおよびキーに対するエントリを索引２００が有しない（ブロック８０８で）場合は、索引サービス１１６は、処理対象ログ・アドレスｉがレコードの現バージョンを有しないことを示す応答をｌｉｖｅコマンドに対して返す（ブロック８１２で）。そうではなく、ｌｉｖｅコマンドからの処理対象ログ・アドレスｉおよびキーを有するエントリ２００ｉを索引２００が含む（ブロック８０８で）場合は、索引サービス１１６は、処理対象ログ・アドレスｉが現バージョンであることを示す応答をｌｉｖｅコマンドに対して返す（ブロック８１０で）。 
【００３１】
ブロック８１０または８１２からの応答が受け取られると、処理対象ログ・アドレスｉがレコード３００ｉの現バージョンを有することを応答が示す（ブロック８１４で）場合は、ストレージ・サービス１１０は、キー３０２、値３０４、および処理対象ログ・アドレスｉをフィールド５０４、５０６、および５０８中で示すＭＯＶＥコマンド５００を、索引サービス１１６に送る（ブロック８１６で）。ｍｏｖｅコマンド５００が受け取られると（ブロック８１８で）、索引サービス１１６は、ｍｏｖｅコマンド５００からのキー５０４および値５０６と処理対象ログ・アドレスｉとをＰＵＴコマンド６００のフィールド６０４、６０６、および６０８にそれぞれ含むＰＵＴコマンド６００を、ストレージ・サービス１１０に送る（ブロック８２０で）。ＰＵＴコマンド６００に応答して、ストレージ・サービス１１０は、ログ・アドレス６０８におけるキー６０４および値６０６を有するレコードを、ログの末尾または一番最近使用された末尾１１２ｅにおけるログ・アドレスなど、選択されたログ・アドレスに書き込む（ブロック８２２で）。レコードが書き込まれる選択されたログ・アドレス１１２ｅは、ＰＵＴコマンド６００に応答して、索引サービス１１６に返される（ブロック８２４で）。選択されたログ・アドレス１１２ｅへのポインタは、ログに追加すべき次のレコードに使用するために、ログ１１２中の次のエントリにインクリメントしてよい。
【００３２】
レコードに対する選択された新しいログ・アドレスを返した後、ストレージ・サービス１１０は、ブロック８０２に戻って（ブロック８２６で）、ログ１１２中の一連の連続的なレコードなど、処理されているログ１１２中のレコードのサブセット中の、次のレコードを処理することができる。
【００３３】
ＰＵＴコマンド６００に対する、新しいログ・アドレスを有する応答を受け取るのに応答して、索引サービス１１６は、ログ・アドレスｉに対する索引エントリ２００ｉを、レコードの現バージョンを今や有するログ中の選択されたログ・アドレス１１２ｅを示すように更新する（ブロック８２８で）。
【００３４】
述べる実施形態では、索引サービス１１６は、キー値を、ＰＵＴコマンド６００に含めることによって使用するが、ＭＯＶＥコマンド５００中のキー値５０６を索引２００に記憶することはしない。代替の一実施形態では、ＭＯＶＥコマンド５００は、キー値５０６を含まずキー５０４およびログ・アドレス５０８のみを提供することができ、次いで索引サービス１１６は、ＰＵＴコマンド６００に含めるためにキー値をストレージ・サービス１１０から取り出すことができる。
【００３５】
一実施形態では、索引サービス１１６は、選択されたログ・アドレスにレコードが移動した古いログ・アドレスｉを有する削除コマンドを、ストレージ・サービス１１０に送って（ブロック８３０で）、ストレージ・サービス１１０に、古いログ・アドレスについてのストレージ・デバイス１０２中のデータを削除させることができる。さらに、ｌｉｖｅコマンドに対する返された応答が、レコードが現バージョンでないことを示した（ブロック８１４で）場合は、ストレージ・サービス１１０は、古いログ・アドレスｉについて論理−物理マッピング４００ｉ中で示される処理対象ログ・アドレスｉにマッピングする物理アドレスにおける、ストレージ・デバイス１０２中のデータを削除することができる（ブロック８３２で）。このようにして、索引サービス１１６およびストレージ・サービス１１０は、協働して、索引２００を更新し、ログ１１２およびストレージ・デバイス１０２からのレコードおよびストレージ空間を再利用する。
【００３６】
代替の一実施形態では、ステップ８３０および８３４は行わなくてよく、その代り、ストレージ・サービス１１０は、ブロック８３２で、レコードの現バージョンを有しないログ中のログ・アドレスを処理するときに、レコードを削除することになる。
【００３７】
さらに他の実施形態では、索引サービス１１６はまた、ＰＵＴ動作の一部として、選択されたログ・アドレスにレコードが移動する場合の古いログ・アドレスｉを含めることもでき、レコードの前ログ・アドレスを指すバック・チェーンをストレージ・マネージャが維持できるようにすることができる。
【００３８】
本発明は、システム、方法、またはコンピュータ・プログラム、あるいはそれらの組合せとすることができる。コンピュータ・プログラムは、本発明の態様をプロセッサに遂行させるためのコンピュータ可読プログラム命令を有する（１つまたは複数の）コンピュータ可読ストレージ媒体を含むことができる。
【００３９】
コンピュータ可読ストレージ媒体は、命令実行デバイスによって使用される命令を保持および記憶できる有形デバイスとすることができる。コンピュータ可読ストレージ媒体は、例えば、以下のものに限定されないが、電子ストレージ・デバイス、磁気ストレージ・デバイス、光学ストレージ・デバイス、電磁ストレージ・デバイス、半導体ストレージ・デバイス、またはこれらの任意の適切な組合せとすることができる。コンピュータ可読ストレージ媒体のより具体的な例の非網羅的なリストは、ポータブル・コンピュータ・ディスケット、ハード・ディスク、ランダム・アクセス・メモリ（ＲＡＭ）、読取専用メモリ（ＲＯＭ）、消去可能プログラム可能な読取専用メモリ（ＥＰＲＯＭまたはフラッシュ・メモリ）、スタティック・ランダム・アクセス・メモリ（ＳＲＡＭ）、ポータブル・コンパクト・ディスク読取専用メモリ（ＣＤ−ＲＯＭ）、ディジタル多用途ディスク（ＤＶＤ）、メモリ・スティック、フロッピー（Ｒ）・ディスク、機械的にエンコードされるデバイス（命令が記録される、パンチカード、または溝の中の隆起構造）、およびこれらの任意の適切な組合せを含む。本明細書におけるコンピュータ可読ストレージ媒体は、電波もしくは他の自由伝搬する電磁波、導波管もしくは他の伝送媒体を介して伝搬する電磁波（例えば、光ファイバ・ケーブルの中を通る光パルス）、またはワイヤを介して伝送される電気信号など、一時的な信号自体であると解釈されるべきではない。
【００４０】
本明細書に記載のコンピュータ可読プログラム命令は、コンピュータ可読ストレージ媒体からそれぞれのコンピューティング／処理デバイスにダウンロードされてよく、あるいは、ネットワーク（例えば、インターネット、ローカル・エリア・ネットワーク、ワイド・エリア・ネットワーク、もしくはワイヤレス・ネットワーク、またはそれらの組合せ）を介して外部コンピュータまたは外部ストレージ・デバイスにダウンロードされてよい。ネットワークは、銅伝送ケーブル、光伝送ファイバ、ワイヤレス伝送、ルータ、ファイアウォール、スイッチ、ゲートウェイ・コンピュータ、またはエッジ・サーバ、あるいはそれらの組合せを含むことができる。各コンピューティング／処理デバイス中の、ネットワーク・アダプタ・カードまたはネットワーク・インタフェースが、コンピュータ可読プログラム命令をネットワークから受け取り、これらのコンピュータ可読プログラム命令を、それぞれのコンピューティング／処理デバイス内のコンピュータ可読ストレージ媒体に記憶されるように転送する。
【００４１】
本発明の動作を遂行するためのコンピュータ可読プログラム命令は、アセンブラ命令、命令セット・アーキテクチャ（ＩＳＡ）命令、機械命令、機械依存命令、マイクロコード、ファームウェア命令、状態設定データであってよく、または、Ｊａｖａ（Ｒ）やＳｍａｌｌｔａｌｋ（Ｒ）やＣ＋＋などのオブジェクト指向プログラミング言語、および、「Ｃ」プログラミング言語や類似のプログラミング言語などの従来の手続き型プログラミング言語を含めた、１つもしくは複数のプログラミング言語の任意の組合せで書かれたソース・コードとオブジェクト・コードとのいずれかであってよい。コンピュータ可読プログラム命令は、完全にユーザのコンピュータ上で実行されるか、スタンドアロン・ソフトウェア・パッケージとして部分的にユーザのコンピュータ上で実行されるか、部分的にユーザのコンピュータ上で実行され部分的にリモート・コンピュータ上で実行されるか、または完全にリモート・コンピュータもしくはサーバ上で実行される場合がある。後者のシナリオでは、リモート・コンピュータは、ローカル・エリア・ネットワーク（ＬＡＮ）もしくはワイド・エリア・ネットワーク（ＷＡＮ）を含めた任意のタイプのネットワークを介してユーザのコンピュータに接続されてもよく、または、接続は、外部コンピュータに対して（例えば、インターネット・サービス・プロバイダを使用してインターネット経由で）行われてもよい。いくつかの実施形態では、プログラマブル・ロジック回路、フィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）、またはプログラマブル・ロジック・アレイ（ＰＬＡ）、を例えば含む電子回路が、本発明の態様を実施するために、コンピュータ可読プログラム命令の状態情報を利用して電子回路を個人化することによって、コンピュータ可読プログラム命令を実行することができる。
【００４２】
本明細書では、本発明の態様が、本発明の実施形態による方法、装置（システム）、およびコンピュータ・プログラムの、フローチャート説明またはブロック図あるいはその両方に関して記述される。フローチャート説明またはブロック図あるいはその両方の各ブロック、および、フローチャート説明またはブロック図あるいはその両方の中のブロックの組合せを、コンピュータ可読プログラム命令によって実装できることは理解されるであろう。
【００４３】
これらのコンピュータ可読プログラム命令は、コンピュータまたは他のプログラム可能データ処理装置のプロセッサを介して実行される命令が、フローチャートまたはブロック図あるいはその両方の１つまたは複数のブロック中で指定される機能／行為を実装する手段をもたらすように、汎用コンピュータ、専用コンピュータ、または他のプログラム可能データ処理装置のプロセッサに提供されて、マシンを生み出すものであってよい。これらのコンピュータ可読プログラム命令はまた、命令が記憶されたコンピュータ可読ストレージ媒体が、フローチャートまたはブロック図あるいはその両方の１つまたは複数のブロック中で指定される機能／行為の態様を実装する命令を含む製造品を構成するように、コンピュータ可読ストレージ媒体に記憶され、コンピュータ、プログラム可能データ処理装置、または他のデバイス、あるいはそれらの組合せに、特定の方式で機能するよう指示するものであってもよい。
【００４４】
コンピュータ可読プログラム命令はまた、コンピュータ、他のプログラム可能装置、または他のデバイス上で実行される命令が、フローチャートまたはブロック図あるいはその両方の１つまたは複数のブロック中で指定される機能／行為を実装するように、コンピュータ実装プロセスを作り出すべく、コンピュータ、他のプログラム可能データ処理装置、または他のデバイスにロードされ、コンピュータ、他のプログラム可能装置、または他のデバイス上で一連の動作ステップを実施させるものであってもよい。
【００４５】
図中のフローチャートおよびブロック図は、本発明の様々な実施形態によるシステム、方法、およびコンピュータ・プログラムの可能な実装形態の、アーキテクチャ、機能性、および動作を示す。これに関して、フローチャートまたはブロック図の中の各ブロックは、モジュール、セグメント、または命令の一部を表すことができ、これは、指定される論理機能を実装するための１つまたは複数の実行可能命令を含む。いくつかの代替実装形態では、ブロック中で示される機能は、図中で示される順序とは異なる順序で生じる場合がある。例えば、関連する機能性に応じて、連続して示される２つのブロックが実際にはほぼ同時に実行される場合もあり、またはこれらのブロックが逆の順序で実行されることもある。また、ブロック図またはフローチャート説明あるいはその両方の各ブロック、および、ブロック図またはフローチャート説明あるいはその両方の中のブロックの組合せは、指定される機能もしくは行為を実施するかまたは専用ハードウェアとコンピュータ命令との組合せを遂行する、専用ハードウェアベースのシステムによって実装できることにも留意されるであろう。
【００４６】
ストレージ・マネージャ１００、および、索引サービス１１６やストレージ・サービス１１０など、その中のコンポーネントは、図９に示されるコンピュータ・システム９０２など、１つまたは複数のコンピュータ・システム中で実装されてよい。コンピュータ・システム／サーバ９０２は、プログラム・モジュールなど、コンピュータ・システムによって実行されるコンピュータ・システム実行可能命令の一般的なコンテキストで記述することができる。一般に、プログラム・モジュールは、特定のリソースを実施するかまたは特定の抽象データ型を実装するルーチン、プログラム、オブジェクト、コンポーネント、ロジック、データ構造などを含む場合がある。コンピュータ・システム／サーバ９０２は、分散クラウド・コンピューティング環境で実践されてよく、その場合、リソースは、通信ネットワークを介してリンクされたリモート処理デバイスによって実施される。分散クラウド・コンピューティング環境では、プログラム・モジュールは、メモリ・ストレージ・デバイスを含めたローカルとリモートの両方のコンピュータ・システム・ストレージ媒体中に位置する場合がある。
【００４７】
図９に示されるように、コンピュータ・システム／サーバ９０２は、汎用コンピューティング・デバイスの形で示されている。コンピュータ・システム／サーバ９０２のコンポーネントは、以下のものに限定されないが、１つまたは複数のプロセッサまたは処理ユニット９０４と、システム・メモリ９０６と、システム・メモリ９０６を含めた様々なシステム・コンポーネントをプロセッサ９０４に結合するバス９０８と、を含むことができる。バス９０８は、様々なバス・アーキテクチャのいずれかを使用する、メモリ・バスまたはメモリ・コントローラ、周辺バス、アクセラレーテッド・グラフィックス・ポート、およびプロセッサまたはローカル・バスを含めた、いくつかのタイプのバス構造のいずれかの１つまたは複数を表す。限定ではなく例として、このようなアーキテクチャは、ＩＳＡ（Industry Standard Architecture）バス、ＭＣＡ（MicroChannel Architecture）バス、ＥＩＳＡ（Enhanced ISA）バス、ＶＥＳＡ（Video Electronics Standards Association）ローカル・バス、およびＰＣＩ（Peripheral Component Interconnects）バスを含む。
【００４８】
コンピュータ・システム／サーバ９０２は通常、様々なコンピュータ・システム可読媒体を備える。このような媒体は、コンピュータ・システム／サーバ９０２からアクセス可能な任意の利用可能な媒体とすることができ、揮発性と不揮発性の媒体、取外し可能と取外し不能の媒体の両方を含む。
【００４９】
システム・メモリ９０６は、ランダム・アクセス・メモリ（ＲＡＭ）９１０またはキャッシュ・メモリ９１２あるいはその両方など、揮発性メモリの形のコンピュータ・システム可読媒体を含むことができる。コンピュータ・システム／サーバ９０２はさらに、他の取外し可能／取外し不能、揮発性／不揮発性コンピュータ・システム・ストレージ媒体を備えることもできる。例に過ぎないが、取外し不能な不揮発性の磁気媒体（図示せず。典型的には「ハード・ドライブ」と呼ばれる）に対して読取りおよび書込みを行うために、ストレージ・システム９１３が設けられてよい。図示されていないが、取外し可能な不揮発性の磁気ディスク（例えば「フロッピー（Ｒ）・ディスク」）に対して読取りおよび書込みを行うための磁気ディスク・ドライブと、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ、または他の光学媒体など、取外し可能な不揮発性の光学ディスクに対して読取りまたは書込みを行うための光学ディスク・ドライブとが設けられてよい。このような事例では、各ドライブは、１つまたは複数のデータ媒体インタフェースによってバス９０８に接続されてよい。後でさらに図示および記述されるように、メモリ９０６は、本発明の実施形態の機能を遂行するように構成された１組の（例えば少なくとも１つの）プログラム・モジュールを有する少なくとも１つのプログラムを含むことができる。
【００５０】
１組の（少なくとも１つの）プログラム・モジュール９１６を有するプログラム／ユーティリティ９１４が、限定ではなく例としてメモリ９０６に記憶されてよく、また、オペレーティング・システム、１つまたは複数のアプリケーション・プログラム、他のプログラム・モジュール、およびプログラム・データも記憶されてよい。オペレーティング・システム、１つもしくは複数のアプリケーション・プログラム、他のプログラム・モジュール、およびプログラム・データ、またはこれらの何らかの組合せはそれぞれ、ネットワーキング環境の一実装形態を含むことができる。コンピュータ・システム／サーバ９０２のコンポーネントは、プログラム・モジュール９１６として実装されてよく、プログラム・モジュール９１６は一般に、本明細書に記載の本発明の実施形態の、機能または方法あるいはその両方を遂行する。
【００５１】
コンピュータ・システム／サーバ９０２はまた、１つまたは複数の外部デバイス９１８と通信することができる。外部デバイス９１８は、キーボード、ポインティング・デバイス、ディスプレイ９２０など、ユーザがコンピュータ・システム／サーバ９０２と対話できるようにする１つもしくは複数のデバイス、または、コンピュータ・システム／サーバ９０２が１つもしくは複数の他のコンピューティング・デバイスと通信できるようにする任意のデバイス（例えば、ネットワーク・カード、モデムなど）、あるいはそれらの組合せ、などである。このような通信は、入出力（Ｉ／Ｏ）インタフェース９２２を介して行うことができる。さらに、コンピュータ・システム／サーバ９０２は、ネットワーク・アダプタ９２４を介して、ローカル・エリア・ネットワーク（ＬＡＮ）、一般的なワイド・エリア・ネットワーク（ＷＡＮ）、または公衆ネットワーク（例えばインターネット）、あるいはそれらの組合せなど、１つまたは複数のネットワークと通信することができる。図示のように、ネットワーク・アダプタ９２４は、バス９０８を介して、コンピュータ・システム／サーバ９０２の他のコンポーネントと通信する。図示されていないが、他のハードウェア・コンポーネントまたはソフトウェア・コンポーネントあるいはその両方が、コンピュータ・システム／サーバ９０２と共に使用されてもよいことを理解されたい。例としては、以下のものに限定されないが、マイクロコード、デバイス・ドライバ、冗長処理ユニット、外部ディスク・ドライブ・アレイ、ＲＡＩＤシステム、テープ・ドライブ、およびデータ・アーカイバル・ストレージ・システムなどが挙げられる。本発明の様々な実施形態についての以上の記述は、例証および記述の目的で提示したものである。これは、網羅的なもの、または開示される正確な形に本発明を限定するものとはしない。上記の教示に鑑みて、多くの変更および変形が可能である。本発明の範囲は、この詳細な記述によって限定されるのではなく、本明細書に添付された特許請求の範囲によって限定されるものとする。上記の明細、例、およびデータは、本発明の構成の製作および使用に関する完全な記述を提供する。本発明の思想および範囲を逸脱することなく本発明の多くの実施形態をなすことができるので、本発明は、本明細書の後に添付される特許請求の範囲にある。
【図１】
0006704207.tif 000002
【図２】
0006704207.tif 000003
【図３】
0006704207.tif 000004
【図４】
0006704207.tif 000005
【図５】
0006704207.tif 000006
【図６】
0006704207.tif 000007
【図７】
0006704207.tif 000008
【図８】
0006704207.tif 000009
【図９】
0006704207.tif 000010