(57)【特許請求の範囲】
【請求項１】
分散データストレージシステムにおいて複製遅延に制約されるデータ削除を引き起こすためのシステムであって、前記システムは、
１以上のプロセッサと、
メモリと、
前記１以上のプロセッサによる実行のための前記メモリに格納された１以上のコンピュータプログラムと、を備え、前記１以上のコンピュータプログラムは、前記システムに動作を実行させるように構成された命令を含み、前記動作は、
データベースサーバに第１のデータベースからデータを削除させる第１の複数のコマンドを、前記データベースサーバへ逐次的に提出することと、
地理的スレーブデータベース複製遅延メトリックを判定することであって、前記地理的スレーブデータベース複製遅延メトリックを判定することは、前記第１のデータベースから前記第１のデータベースとは異なる場所にある第２のデータベースへとデータベースデータを複製する複製プロセスの測定時間を反映するデータ値に基づく、ことと、
ローカルスレーブデータベース複製遅延メトリックを判定することであって、前記ローカルスレーブデータベース複製遅延メトリックを判定することは、前記第１のデータベースから前記第１のデータベースと同じ場所にある第３のデータベースへとデータベースデータを複製する複製プロセスの測定時間を反映するデータ値に基づく、ことと、
（ａ）前記地理的スレーブデータベース複製遅延メトリックが地理的スレーブデータベース複製遅延閾値を上回っていること、及び（ｂ）前記ローカルスレーブデータベース複製遅延メトリックがローカルスレーブデータベース複製遅延閾値を上回っていること、の両方を判定したことに少なくとも部分的に基づいて、前記第１の複数のコマンドに関連する休止間隔を調整することと、
第２の複数のコマンドを前記データベースサーバへ逐次的に提出することにより、前記第１の複数のコマンドを逐次的に提出することにより前記第１のデータベースからデータが削除される削除レートとは異なる削除レートで、前記データベースサーバに前記第１のデータベースからデータを削除させることと、を含み、
前記第２の複数のコマンドを逐次的に提出することは、前記第２の複数のコマンドのうちのコマンドの提出の後に前記調整された休止間隔の間スリープすることに基づく、
システム。
【請求項２】
請求項１に記載のシステムであって、
前記地理的スレーブデータベース複製遅延メトリックは、第１の地理的スレーブデータベース複製遅延メトリックであり、前記ローカルスレーブデータベース複製遅延メトリックは、第１のローカルスレーブデータベース複製遅延メトリックであり、前記休止間隔は、第１の休止間隔であり、前記命令は更に、
（ａ）第２の地理的スレーブデータベース複製遅延メトリックが前記地理的スレーブデータベース複製遅延閾値を上回っていること、及び（ｂ）第２のローカルスレーブデータベース複製遅延メトリックが前記ローカルスレーブデータベース複製遅延閾値を下回っていること、の両方を判定したことに少なくとも部分的に基づいて、前記第１の休止間隔を第２の休止間隔へと増加させることと、
前記データベースからデータを削除する第３の複数のコマンドを、前記データベースサーバへ逐次的に提出することと、を行うように構成され、
前記第３の複数のコマンドを逐次的に提出することは、前記第３の複数のコマンドのうちのコマンドの提出の後に前記第２の休止間隔の間スリープすることに基づく、
システム。
【請求項３】
請求項１に記載のシステムであって、前記地理的スレーブデータベース複製遅延メトリックは、第１の地理的スレーブデータベース複製遅延メトリックであり、前記ローカルスレーブデータベース複製遅延メトリックは、第１のローカルスレーブデータベース複製遅延メトリックであり、前記休止間隔は、第１の休止間隔であり、前記命令は更に、
（ａ）第２の地理的スレーブデータベース複製遅延メトリックが前記地理的スレーブデータベース複製遅延閾値を下回っていること、及び（ｂ）第２のローカルスレーブデータベース複製遅延メトリックが前記ローカルスレーブデータベース複製遅延閾値を下回っていること、の両方を判定したことに少なくとも部分的に基づいて、第３の複数のコマンドのうちのコマンドの各提出の後に休止間隔の間スリープすること無しに、前記データベースからデータを削除する前記第３の複数のコマンドを、前記データベースサーバへ逐次的に提出することを行うように構成される、
システム。
【請求項４】
請求項１に記載のシステムであって、前記第１の複数のコマンドの各コマンド、及び前記第２の複数のコマンドの各コマンドは、構造化照会言語（ＳＱＬ）の削除コマンドである、
システム。
【請求項５】
請求項１に記載のシステムであって、前記休止間隔は、第１の休止間隔であり、前記命令は更に、前記第１の複数のコマンドのうちのコマンドの各提出の後に前記第１の休止間隔よりも短い第２の休止間隔の間スリープすることを行うように構成される、
システム。
【請求項６】
請求項５に記載のシステムであって、前記命令は更に、（ａ）前記地理的スレーブデータベース複製遅延メトリックが前記地理的スレーブデータベース複製遅延閾値を上回っていること、及び（ｂ）前記ローカルスレーブデータベース複製遅延メトリックが前記ローカルスレーブデータベース複製遅延閾値を上回っていること、の両方を判定したことに少なくとも部分的に基づいて、前記第２の休止間隔を前記第１の休止間隔へと増加させることを行うように構成される、
システム。
【請求項７】
請求項１に記載のシステムであって、前記命令は更に、前記地理的スレーブデータベース複製遅延メトリック及び前記ローカルスレーブデータベース複製遅延メトリックのうちの最大値として前記休止間隔を選択することを行うように構成される、
システム。
【請求項８】
請求項１に記載のシステムであって、前記データベースからデータを削除する前記第１の複数のコマンドを、前記データベースサーバへ逐次的に提出することは、前記第１の複数のコマンドのうちのコマンドの各提出の後に休止間隔の間スリープしないことに少なくとも部分的に基づいている、
システム。
【請求項９】
分散データストレージシステムにおいて複製遅延に制約されるデータ削除を引き起こすための方法であって、前記方法は、１以上のプロセッサとメモリとを備えるコンピューティングシステムによって実行され、前記方法は、
データベースサーバにデータベースからデータを削除させる第１の複数のコマンドを、前記データベースサーバへ逐次的に提出することであって、前記第１の複数のコマンドを逐次的に提出することは、前記第１の複数のコマンドのうちのコマンドの提出の後に第１の休止間隔の間休止することに基づく、ことと、
ローカルスレーブデータベース複製遅延メトリックを判定することであって、前記ローカルスレーブデータベース複製遅延メトリックを判定することは、前記データベースから前記データベースに対してローカルな第３のデータベースへとデータベースデータを複製する複製プロセスの測定時間を反映するデータ値に基づく、ことと、
前記ローカルスレーブデータベース複製遅延メトリックがローカルスレーブデータベース複製遅延閾値を上回っていることを判定したことに少なくとも部分的に基づいて、前記第１の休止間隔を第２の休止間隔へと調整することと、
第２の複数のコマンドを前記データベースサーバへ逐次的に提出することにより、前記第１の複数のコマンドを逐次的に提出することにより前記データベースからデータが削除される削除レートとは異なる削除レートで、前記データベースサーバに前記データベースからデータを削除させることと、を備え、
前記第２の複数のコマンドを逐次的に提出することは、前記第２の複数のコマンドのうちのコマンドの提出の後に前記第２の休止間隔の間休止することに基づく、
方法。
【請求項１０】
請求項９に記載の方法であって、前記第１の休止間隔を調整することは、（ａ）前記ローカルスレーブデータベース複製遅延メトリックが前記ローカルスレーブデータベース複製遅延閾値を上回っていることを判定したこと、及び（ｂ）地理的スレーブデータベース複製遅延メトリックが地理的スレーブデータベース複製遅延閾値を上回っていることを判定したこと、の両方に少なくとも部分的に基づく、
方法。
【請求項１１】
請求項９に記載の方法であって、前記ローカルスレーブデータベース複製遅延メトリックは、第１のローカルスレーブデータベース複製遅延メトリックであり、更に、
地理的スレーブデータベース複製遅延メトリックを判定することであって、前記地理的スレーブデータベース複製遅延メトリックを判定することは、前記第１のデータベースから前記第１のデータベースとは異なる場所にある第２のデータベースへとデータベースデータを複製する複製プロセスの測定時間を反映するデータ値に基づく、ことと、
（ａ）第２のローカルスレーブデータベース複製遅延メトリックが前記ローカルスレーブデータベース複製遅延閾値を下回っていること、及び（ｂ）地理的スレーブデータベース複製遅延メトリックが地理的スレーブデータベース複製遅延閾値を下回っていること、の両方を判定したことに少なくとも部分的に基づいて、前記第２の休止間隔を第３の休止間隔へと減少させることと、
前記データベースからデータを削除する第３の複数のコマンドを、前記データベースサーバへ逐次的に提出することであって、前記第３の複数のコマンドのうちのコマンドの各提出の後に前記第３の休止間隔の間休止することを含む、ことと、
を備える、方法。
【請求項１２】
請求項９に記載の方法であって、更に、
第１のタイムスタンプに関連するデータベースレコードを第１のデータベースに書き込むことと、
前記データベースレコードが第２のデータベースへ複製された後に、前記第２のデータベースから前記第１のタイムスタンプを含む前記データベースレコードを読み取ることと、
前記第２のデータベースから読み取られた前記データベースレコードの前記第１のタイムスタンプに少なくとも部分的に基づいて、前記ローカルスレーブデータベース複製遅延メトリックを判定することと、
を備える、方法。
【請求項１３】
請求項９に記載の方法であって、前記ローカルスレーブデータベース複製遅延メトリックは、同じデータセンタ内に配置された２つのデータベース間の複製遅延を評価するものである、
方法。
【請求項１４】
請求項９に記載の方法であって、前記第１の複数のコマンドの各コマンドは、構造化照会言語（ＳＱＬ）の削除コマンドである、
方法。
【請求項１５】
請求項９に記載の方法であって、前記第１の複数のコマンドの各コマンドは、異なるデータベーストランザクションの文脈において前記データベースに対して実行される、
方法。
【請求項１６】
分散データストレージシステムにおいて複製遅延に制約されるデータ削除を引き起こすためのプログラムであって、前記プログラムは１以上のプロセッサとメモリとを備えるコンピューティングシステムによる実行のためのものであり、前記プログラムは、前記コンピューティングシステムに動作を実行させる命令を含み、前記動作は、
データベースからデータを削除する第１の複数のコマンドを、データベースサーバへ逐次的に提出することであって、前記第１の複数のコマンドを逐次的に提出することは、前記複数のコマンドのうちのコマンドの提出の後に第１の休止間隔の間休止することに基づく、ことと、
地理的スレーブデータベース複製遅延メトリックを判定することであって、前記地理的スレーブデータベース複製遅延メトリックを判定することは、前記第１のデータベースから前記第１のデータベースとは異なる場所にある第２のデータベースへとデータベースデータを複製する複製プロセスの測定時間を反映するデータ値に基づく、ことと、
ローカルスレーブデータベース複製遅延メトリックを判定することであって、前記ローカルスレーブデータベース複製遅延メトリックを判定することは、前記第１のデータベースから前記第１のデータベースと同じ場所にある第３のデータベースへとデータベースデータを複製する複製プロセスの測定時間を反映するデータ値に基づく、ことと、
（ａ）前記ローカルスレーブデータベース複製遅延メトリックがローカルスレーブデータベース複製遅延閾値を下回っていること、及び（ｂ）前記地理的スレーブデータベース複製遅延メトリックが地理的スレーブデータベース複製遅延閾値を下回っていること、の両方を判定したことに少なくとも部分的に基づいて、第２の複数のコマンドのうちのコマンドの提出の後に前記第１の休止間隔の間休止すること無しに、前記データベースからデータを削除する前記第２の複数のコマンドを、前記データベースサーバへ逐次的に提出することと、
を含む、プログラム。
【請求項１７】
請求項１６に記載のプログラムであって、前記地理的スレーブデータベース複製遅延メトリックは、第１の地理的スレーブデータベース複製遅延メトリックであり、前記命令は更に、
第２の地理的スレーブデータベース複製遅延メトリックが前記地理的スレーブデータベース複製遅延閾値を上回っていることを判定したことに少なくとも部分的に基づいて、前記データベースからデータを削除する第３の複数のコマンドを、前記データベースサーバへ逐次的に提出することであって、前記第３の複数のコマンドのうちのコマンドの提出の後に休止間隔の間休止することを含む、ことを行うように構成される、
プログラム。
【請求項１８】
請求項１６に記載のプログラムであって、前記ローカルスレーブデータベース複製遅延メトリックは、第１のローカルスレーブデータベース複製遅延メトリックであり、前記命令は更に、
第２のローカルスレーブデータベース複製遅延メトリックが前記ローカルスレーブデータベース複製遅延閾値を上回っていることを判定したことに少なくとも部分的に基づいて、前記データベースからデータを削除する第３の複数のコマンドを、前記データベースサーバへ逐次的に提出することであって、前記第３の複数のコマンドのうちのコマンドの各提出の後に休止間隔の間休止することを含む、ことを行うように構成される、
プログラム。
【請求項１９】
請求項１６に記載のプログラムであって、前記地理的スレーブデータベース複製遅延メトリックは、異なるデータセンタ内に配置された２つのデータベース間の複製遅延を評価するものである、
プログラム。
【請求項２０】
請求項１６に記載のプログラムであって、前記第１の複数のコマンドのうちのコマンドは、前記コマンドにより削除すべきデータベースデータオブジェクトの最大数を指定する、
プログラム。
【請求項２１】
請求項１に記載のシステムであって、前記第１のデータベースと前記第２のデータベースとは、異なるデータセンタ内に配置される、
システム。
【請求項２２】
請求項１に記載のシステムであって、前記第１のデータベースと前記第３のデータベースとは、同じデータセンタ内に同じ場所に配置される、
システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散データストレージシステムに関する。より詳細には、本発明は大規模分散データストレージシステムにおける複製遅延に制約されるデータ削除に関する。
【背景技術】
【０００２】
今日、世界中のユーザによって使用される多くのインターネットサービスを含む多くのオンラインサービスは、複雑で大規模な分散コンピューティングシステムとして実装されている。これらのオンラインサービスはしばしば、異なるソフトウェア開発チームによって、しばしば、異なるソフトウェアプログラミング言語で、開発されたソフトウェアアプリケーションの集合から構築される。ソフトウェアアプリケーションの集合は、複数のデータセンタ設備にわたって、数百または数千のコンピューティングマシンに広がることができる。
【０００３】
この複雑さのために、オンラインサービスのアーキテクチャは、典型的には各階層が多くのコンピューティングマシンから構成される「階層」で構造化される。階層は、エンドユーザデバイスからデータ通信ネットワーク（例えば、インターネット）を介して受信されたネットワーク要求を処理し、データ通信ネットワークを介してエンドユーザデバイスに送り返される、ネットワーク要求に対するネットワーク応答を生成する観点から、概念的に互いの上に積み重ねられる。
【０００４】
階層の１つは、典型的にはオンラインサービスの「アプリケーション層」内のアプリケーションによって使用されるデータを持続させ、取り出すための大規模分散データストレージシステムから構成される。アプリケーション層は概念的にはデータストレージシステム層の上に位置し、オンラインサービスのエンドユーザに面する機能の多くを実装することができる。アプリケーションによって使用される「アプリケーション」データは例えば、エンドユーザによって提供される情報、そのような情報に関するメタデータ、またはエンドユーザにオンラインサービスを提供する一部としてアプリケーションによって使用される任意の他の情報を含むことができる。
【図面の簡単な説明】
【０００５】
【図１】図１は、本発明の一実施形態による大規模分散データストレージシステムを示す。
【０００６】
【図２】図２は、本発明の一実施形態による、分散データストレージシステムクラスタのデータベースサーバエンジンを示す。
【０００７】
【図３】図３は、本発明の一実施形態によるローカル複製プロセスを示す。
【０００８】
【図４】図４は、本発明の一実施形態による地理的複製プロセスを示す。
【０００９】
【図５】図５は、本発明の一実施形態による、複製遅延に制約されるデータ削除のプロセスを示す。
【００１０】
【図６】図６は、本発明の一実施形態による、測定された複製遅延に基づいて休止間隔を調整するためのプロセスを示す。
【００１１】
【図７】図７は、一実施形態による、本発明を実施するために使用され得る基本ハードウェアマシンを示す。
【００１２】
【図８】図８は、一実施形態による、基本ハードウェアマシンの動作を制御するための基本的なソフトウェアシステムの非限定的な例を示す。
【発明を実施するための形態】
【００１３】
オンラインサービスプロバイダは、大規模分散データストレージシステムからデータを削除する必要がある場合がある。データを削除することは、様々な理由で必要とされ得る。一般的な理由は、新しいデータのためにデータストレージスペースを解放することである。例えば、もはやオンラインサービスを使用しないユーザのために記憶されたデータは、新しいユーザデータのための余地を作るために削除されてもよい。
【００１４】
データを削除する際にオンラインサービスプロバイダが直面する１つの課題は、削除すべき大量のデータが存在する可能性があることである。例えば、分散データストレージシステムは、多くのペタバイト以上のデータを記憶することができる。したがって、記憶されたデータの総量の一部を削除することでさえも、相当量のデータ（例えば、数テラバイト以上）を削除することを伴う場合がある。
【００１５】
削除の対象となり得る大量のデータが与えられると、データを可能な限り迅速に削除し、それによってストレージスペースを可能な限り迅速に解放するために、単一のデータベーストランザクションにおいてすべての対象データを削除しようと試みる傾向があり得る。例えば、単一のデータベーストランザクションが、そのそれぞれのデータベース上の操作を処理することができるストレージシステムの各データベースサーバに提出されることができる。しかしながら、トランザクションによってターゲットとされる大量のデータのために、このアプローチは、アプリケーション層からの要求の処理に有害な影響を及ぼす点まで、データベースサーバのかなりのコンピューティングリソースを迅速に消費する可能性がある。この影響は、サービスの通常の応答性の欠如によって、オンラインサービスのエンドユーザにとって顕著であり得る。
【００１６】
別の可能なアプローチは、別々のトランザクションにおいてターゲットデータの部分を削除することであってもよい。この場合、別個のトランザクションは、規則的な所定の時間間隔で各データベースサーバに提出されてもよい。しかしながら、小さすぎる所定の時間間隔が選択された場合、単一の大きなトランザクションに関連する上述の問題に遭遇する可能性がある。一方、大きすぎる所定の時間間隔が選択された場合には、全ての対象データを削除するのに長時間を要しすぎることがある。
【００１７】
複製遅延に制約されるデータ削除の概要
【００１８】
大規模分散データストレージシステムにおいてデータを削除するための可能な手法に関する前述の問題および他の問題に対処するために、本明細書で説明し、提案し、示唆する技法は、大規模分散データストレージシステムにおける複製遅延に制約されるデータ削除のためのシステムおよび方法を含む。本技法は大規模分散データストレージシステムにおいてデータを削除するための既存の手法の代わりに、またはそれと併せて使用することができる。
【００１９】
この技法は、分散データストレージシステム内のデータベースから大量のデータをあまりにも迅速に削除すると、分散データストレージシステムの複製サブシステムがかなりの性能低下を被るか、または失敗さえする可能性があるという認識に対処する。複製サブシステムは、分散データストレージシステムの「マスタ」データベースに記憶されたデータを、分散データストレージシステムの「スレーブ」データベースに複製するために使用することができる。削除レートが高すぎる場合、データの削除の結果として生成された複製イベントを処理するときに、複製サブシステムによって使用されるディスクおよびネットワークＩ／ＯリソースおよびＣＰＵリソースに対して削除レートがもたらす処理負荷のために、複製サブシステムは、かなりの性能低下を被るか、または失敗することさえある。
【００２０】
本発明の一実施形態では、データがデータベースから削除されるレートが測定された複製遅延によって制約される。一般に、複製遅延は、データがマスタデータベースに格納されるときと、複製サブシステムによって複製されたデータがスレーブデータベースに格納されるときとの間の時間遅延を指す。いくらかの複製遅延が予想される。しかしながら、大きな複製遅延は、ストレス下にあり、失敗しようとしている複製サブシステムを示す場合がある。
【００２１】
一実施形態では、本技法が分散データストレージシステムにおける複製遅延に制約されるデータ削除のための方法を含む。この方法は、１つまたは複数のプロセッサおよびメモリを備える「データバキューム(data vacuum)」コンピューティングシステムによって実行される。この方法は、データバキュームが分散データストレージシステムのデータベースサーバにコマンドを逐次的および周期的に提出することを含む。コマンドは、対応するデータベースからデータを削除するものである。コマンドの各提出の後、次のコマンドを提出する前に、データバキュームはある時間休止（スリープ）する。コマンドの提出間にデータバキュームが休止する時間の長さは、本明細書では「休止間隔(pause interval)」と呼ばれる。
【００２２】
一実施形態では、休止間隔が初期デフォルト値を有し、その後、測定された複製遅延に基づいてデータバキュームによって自動的に調整される。データバキュームは、ローカルスレーブデータベース複製遅延メトリックがローカルスレーブ複製遅延閾値未満であり、かつジオスレーブデータベース複製遅延メトリックがジオスレーブ複製遅延閾値未満である間に、休止間隔を初期デフォルト値から始めてデクリメント量ずつ周期的に短縮することができる。ローカルスレーブデータベース複製遅延メトリックは、同じデータセンタ内に同じ場所に配置されたマスタデータベースサーバとスレーブデータベースサーバとの間の複製遅延の単一の測定値または周期的な測定値に基づくことができる。ジオスレーブデータベース複製遅延メトリックは、異なる地理的に分散されたデータセンタ内にあるマスタデータベースサーバとスレーブデータベースサーバとの間の複製遅延の単一の測定または周期的な測定に基づくことができる。
【００２３】
一実施形態ではローカルスレーブデータベース複製遅延メトリックがローカルスレーブ複製遅延閾値より上であり、および／またはジオスレーブデータベース複製遅延メトリックがジオスレーブ複製遅延閾値より上である間、データバキュームは休止間隔をそのときの現在の値から始めてインクリメント量ずつ周期的に延長することができる。データバキュームは、ローカルスレーブデータベース複製遅延メトリックおよびローカルスレーブ複製遅延メトリックの両方が再びそれぞれの閾値未満になった後に、休止間隔を定期的に短縮することに戻ることができる。データバキュームはローカルおよびジオスレーブ複製遅延メトリックに基づいて休止間隔を定期的に短縮および延長するこのプロセスを継続し、それによってローカルおよびジオスレーブ複製遅延閾値によって制約される削除レートを維持することができる。
【００２４】
分散データストレージシステムにおける複製遅延に制約されるデータ削除のための本明細書で開示される技法は、分散データストレージシステムにおけるデータを削除するための１つまたは複数のプロセッサおよびメモリを備えるコンピューティングシステムを改善する。この改善は、削除レートを、ローカル複製遅延および地理的複製遅延の両方に関して測定された複製遅延によって制約される最大許容削除レートへと経時的に調整しつつ、同時に、深刻な複製遅延を引き起こす高すぎる削除レートを防止することから、生じる。
【００２５】
用語
【００２６】
ここで実施形態を詳細に参照するが、その例は添付の図面に示されている。以下の詳細な説明では、各種説明された実施形態の完全な理解を提供するために、多数の特定の詳細が説明される。しかし、当業者には、これらの特定の詳細なしに、各種説明された実施形態を実施できることが明らかであろう。他の例では、周知の方法、手順、コンポーネント、回路、およびネットワークは、実施形態の態様を不必要に曖昧にしないように、詳細には説明されていない。 
【００２７】
また、第１、第２などの用語は場合によっては様々な要素を説明するために本明細書で使用されるが、これらの要素は文脈に応じて、これらの用語によって限定されないことも理解されよう。これらの用語は、文脈に応じて、１つの要素を別の要素から区別するためにのみ使用されてもよい。例えば、各種説明された実施形態の範囲から逸脱することなく、第１のデータベースサーバは第２のデータベースサーバと呼ばれてもよく、同様に、第２のデータベースサーバは第１のデータベースサーバと呼ばれてもよい。第１のデータベースサーバおよび第２のデータベースサーバは両方ともデータベースサーバであってもよいが、同じデータベースサーバでなくてもよい。 
【００２８】
本明細書で説明される各種実施形態の説明で使用される用語は実施形態を説明するためだけのものであり、限定することを意図していない。各種説明された実施形態および添付された特許請求の範囲の説明において使用されるように、単数形「ａ」、「ａｎ」、および「ｔｈｅ」は、そうでないことを文脈が明確に示さない限り、複数形も含むことが意図される。また、本明細書で使用される「および／または」という用語は、１つまたは複数の関連する列挙された項目のすべての可能な組合せを指し、包含することも理解されるであろう。さらに、「含む(includes)」、「含んでいる(including)」、「備える(comprises)」、および／または「備えている(comprising)」という用語は、本明細書で使用される場合、述べられた特徴、整数、ステップ、操作、要素、および／またはコンポーネントの存在を指定するが、１つまたは複数の他の特徴、整数、ステップ、操作、要素、コンポーネント、および／またはそれらのグループの存在または追加を排除しないことを理解されたい。 
【００２９】
本明細書で使用されるように、用語「ｉｆ」は、任意選択で、文脈に応じて、「ｗｈｅｎ」または「ｏｎ」または「判定したことに応じて(in response to determining)」または「検出したことに応じて(in response to detecting)」または「という判定に従って(in accordance with a determination that)」を意味するものと解釈される。同様に、「判定された場合(if it is determined)」または「（述べられた状態またはイベントが）検出された場合(if [a stated condition or event] is detected)」というプレーズは、文脈に応じて、任意選択で、「決定時に」または「決定に応答して」または「述べられた状態または事象を検出したときに」または「述べられた状態または事象を検出したことに応答して」または「述べられた状態または事象が検出されたという決定に従って」を意味すると解釈される。 
【００３０】
本明細書で使用されるように、用語「メトリック」は、単一の測定値またはそれから計算された値、または経時的に取得された測定値のセットの値、またはそれから計算された値または値のセットのいずれかを指す。例えば、２つのサーバ間の複製遅延の単一の測定値の値は、メトリックである。別の例として、経時的に取得された２つのサーバ間の複製遅延の周期的測定値の平均(average)、平均(mean)、加重平均(weighted average)、または加重平均(weighted mean)もメトリックである。
【００３１】
本明細書で使用されるように、閾値を上回るということは、比較中のアイテムの値が特定の他の値を上回ること、比較中のアイテムが最大値を有するある特定の数のアイテムの中にあること、または比較中のアイテムが特定のトップパーセンテージ量内の値を有することを意味する。本明細書で使用するとき、閾値を下回るということは、比較中のアイテムの値が特定の他の量を下回ること、比較中のアイテムが最小値を有するある特定の数のアイテムの中にあること、または比較中のアイテムが特定のボトムパーセンテージ量内の値を有することを意味する。本明細書で使用されるように、閾値内にあるということ(being within a threshold)は、比較中のアイテムの値が２つの指定された他の値の間にあること、比較中のアイテムが中間の指定された数のアイテムの中にあること、または比較中のアイテムが中間の特定のパーセンテージ範囲内の値を有することを意味する。他に定義されない場合、高(high)または重要でない(unimportant)などの相対的用語は、値を割り当て、その値が確立された閾値とどのように比較されるかを判定することとして理解することができる。例えば、「重度の複製遅延」というフレーズは、閾値を超える複製遅延メトリックを意味すると理解することができる。
【００３２】
大規模分散データストレージシステム環境
【００３３】
本発明は単一のコンピューティングマシンを使用して実施することができるが、本発明は分散コンピューティング環境において複数のコンピューティングマシンを使用して実施することが好ましい。図１は、本発明の一実施形態による分散コンピューティング環境１００の一例を示す。
【００３４】
環境１００は、ＤＣ１およびＤＣ２とラベル付けされた２つのデータセンタを含む。各データセンタＤＣ１およびＤＣ２は、コンピューティングシステムと、データネットワーク通信機器、データ記憶機器、および冷却機器などの関連するコンポーネントとを共同配置するための設備または建物を含むことができる。データセンタＤＣ１およびＤＣ２は、互いに地理的距離を置いて配置することができる。地理的距離は多数のマイルであってもよい。例えば、データセンタＤＣ１は米国カリフォルニア州サンフランシスコにあり、データセンタＤＣ２は米国ニューヨーク州ニューヨークにあることがある。データセンタＤＣ１およびＤＣ２が異なる国にあることも可能である。しかしながら、一般に、データセンタＤＣ１とＤＣ２との間の地理的距離は、少なくとも数マイルであり得る。
【００３５】
一実施形態では分散コンピューティング環境が２つのデータセンタのみを含むが、分散コンピューティング環境は別の実施形態では２つより多くのデータセンタを含むことができる。この場合、分散コンピューティング環境は、図１に示す環境１００がそのような各ペア（ピア）を表すデータセンタペア（データセンタピア）から構成されると見なすことができる。
【００３６】
図１に示すように、各データセンタＤＣ１およびＤＣ２は、それぞれ図１のアプリケーション層１およびアプリケーション層２とラベル付けされたアプリケーション層を含むことができる。各アプリケーション層は、それぞれの分散データストレージシステムクラスタのネットワーククライアントとして動作するプロセスを実行する複数のコンピューティングマシンから構成することができる。図１に示すように、クラスタ１とラベル付けされた分散データストレージシステムクラスタはアプリケーション層１のクライアントプロセスにサービスを提供し、クラスタ２とラベル付けされた分散データストレージシステムクラスタはアプリケーション層２のクライアントプロセスにサービスを提供する。各分散データストレージシステムクラスタは、それぞれのデータベースサーバエンジンを実行する複数のコンピューティングマシンからも構成される。クラスタ１のコンピューティングマシンは、データベースサーバエンジンであるサーバエンジン１−１、サーバエンジン１−２、・・・サーバエンジン１−Ｎを実行し、クラスタ２のコンピューティングマシンは、サーバエンジン２−１、サーバエンジン２−２、・・・サーバエンジン２−Ｍを実行する。分散データストレージシステムクラスタであるクラスタ１およびクラスタ２は、同じまたは異なる数のサーバエンジンを有することができる。例示的なデータベースサーバエンジンの詳細は、図２に関して以下に説明される。
【００３７】
一実施形態では異なるコンピューティングマシンがアプリケーション層のクライアントプロセスおよび分散データストレージシステムクラスタのサーバエンジンを実行するために使用されるが、別の実施形態では同じコンピューティングマシンが１つまたは複数のクライアントプロセスおよび１つまたは複数のサーバエンジンを実行することができる。
【００３８】
データセンタ内のアプリケーション層および分散データストレージシステムクラスタの様々なコンピューティングマシンは、１つまたは複数のデータ通信ネットワークによって相互接続することができる。そのようなデータ通信ネットワークは様々なコンピューティングマシン間でネットワークメッセージ（例えば、ネットワーク要求およびそれに対するネットワーク応答）を送受信するための様々なネットワーク通信プロトコルをサポートすることができる。本発明の実施形態を実施するのに適したネットワーク通信プロトコルの非限定的な例には、ハイパーテキスト転送プロトコル（ＨＴＴＰ）、セキュアハイパーテキスト転送プロトコル（ＨＴＴＰＳ）、および／または他のインターネットプロトコル（ＩＰ）ベースのネットワーク通信プロトコルが含まれる。
【００３９】
一実施形態では、分散データストレージシステムクラスタに格納されたデータが分散データストレージシステムクラスタのサーバエンジン上でシャード化される(sharded)（水平に分割される）。本明細書で使用されるように、シャード１１０は、データベースの水平パーティションを指す。サーバエンジンの各々は、複数のシャード(shard)を記憶することができる。非限定的な例示的な実施形態では、分散データストレージシステムクラスタが約２５０個のサーバエンジンにわたって分散された約２，０００個のシャードを含む。
【００４０】
一実施形態によれば、動作中、アプリケーション層で実行されるクライアントプロセスは、データセンタ内の分散データストレージシステムクラスタのサーバエンジンのいずれかに接続し、そこからデータを要求することができる。クライアントプロセスから要求を受信したサーバエンジンは、要求を検査して、要求が関係するデータをどのシャードが保存しているかを判定することができる。要求を受信したサーバエンジンがターゲットシャードを格納していない場合、サーバエンジンは、ターゲットシャードを格納しているクラスタ内の他のサーバエンジンのうちの１つに要求をリダイレクトすることができる。一実施形態では、分散データストレージシステムクラスタが、アプリケーション層からの読取り要求を処理する性能を改善するために、キャッシュ（図１には図示せず）を含むことができる。キャッシュは、高可用性のために分割され、複製されてもよい。キャッシュ内のデータは、アプリケーション層からの書込み要求によって無効にすることができる。無効化は、強い一貫性があってもよいし、または、古い読み取り(stale read)が許容される場合、最終的に一貫性があってもよい。
【００４１】
２つのデータセンタＤＣ１およびＤＣ２は、１つまたは複数のデータ通信ネットワーク１２０によって相互接続することができる。データセンタ内のコンピューティングマシンを相互接続するデータ通信ネットワークの場合のように、データセンタＤＣ１およびＤＣ２を相互接続する１つまたは複数のデータ通信ネットワーク１２０は、データセンタＤＣ１とＤＣ２との間でネットワークメッセージ（たとえば、ネットワーク要求およびそれに対するネットワーク応答）を送受信するための各種ネットワーク通信プロトコル（たとえば、ＨＴＴＰ、ＨＴＴＰＳ、または他のＩＰベースのプロトコル）をサポートすることができる。
【００４２】
データベースサーバエンジン
【００４３】
図２は、一実施形態による、分散データストレージシステムクラスタの例示的なデータベースサーバエンジン２００を示す。サーバエンジン２００は、コアサーバ２０２と、第１のデータベース２０６を処理する第１のデータベースサーバ２０４と、第２のデータベース２１０を処理する第２のデータベースサーバ２０８と、第３のデータベース２１４を処理する第３のデータベースサーバ２１２とを含む。
【００４４】
コアサーバ２０２は、アプリケーション層のクライアントプロセスから「クライアント」要求を受信し、それに対する応答をクライアントプロセスに送信する。コアサーバ２０２は、クライアント要求がデータベースサーバエンジン２００のデータベースシャードに格納されたデータに関係しない場合、いくつかのクライアント要求を分散データストレージシステムクラスタ内の他のサーバエンジンにリダイレクトすることができる。データベースサーバエンジン２００のデータベースシャードに格納されたデータに関係するクライアント要求の場合、コアサーバ２０２は、対応する「データベース」要求を第１のデータベースサーバ２０４に送ることができる。第１のデータベースサーバ２０４が利用不可能であるか、または負荷分散の目的のための、いくつかのシナリオでは、コアサーバ２０２は、データベース要求を第２のデータベースサーバ２０８または第３のデータベースサーバ２１２に送ることができる。
【００４５】
一実施形態では、第１のデータベース２０６、第２のデータベース２１０、および第３のデータベース２１４は、それぞれリレーショナルデータベースである。第１のデータベースサーバ２０４、第２のデータベースサーバ２０８、および第３のデータベースサーバ２１２はそれぞれ、構造化照会言語（ＳＱＬ）などに基づくデータベース要求を処理することができる。一実施形態では、コアサーバ２０２がアプリケーション層からのクライアント要求をデータベースサーバ２０４、２０８、および２１２に送信されるデータベース要求に変換するとき、ならびにデータベースサーバ２０４、２０８、および２１２から受信したデータベース要求に対する応答を、アプリケーション層内のクライアントプロセスに返送されるクライアント要求に対する応答に変換するときに、オブジェクト対リレーショナルマッピング動作を実行することができる。
【００４６】
一実施形態では、データベース２０６、２１０、および２１４はリレーショナルデータベースであるが、別の実施形態では、データベース２０６、２１０、および２１４は異なるデータベースデータモデルによって論理的に構造化される。例えば、データベース２０６、２１０、および２１４は、階層、ネットワーク、オブジェクト、文書、グラフ、キー値、または別の論理データベースデータモデルによって論理的に構造化することができる。同様に、一実施形態ではデータベースサーバ２０４、２０８、および２１２はＳＱＬまたは同様のクエリ言語によって組み立てられたデータベース要求を処理することができるが、別の実施形態ではデータベースサーバ２０４、２０８、および２１２は異なるクエリ言語によって構造化されたデータベース要求を処理するように構成される。一般に、データベース２０６、２１０、および２１４内のデータを作成、読み取り、更新、および削除するためのコマンドをサポートする、実質的に任意のデータベースクエリ言語を使用することができる。
【００４７】
データベースサーバ２０４、２０８、および２１２は、マスタ−スレーブ構成でデータベース２０６、２１０、および２１４の間でデータを複製するように構成することができる。例えば、第１のデータベース２０６に格納されたデータは第２のデータベース２１０に複製されてもよく、第２のデータベース２１０に格納されたデータは第３のデータベース２１４に複製されてもよい。この例ではデータベース２０６が「スレーブ」データベース２１０に関する「マスタ」データベースであり、データベース２１０は「スレーブ」データベース２１４に関する「マスタ」データベースである。したがって、第１のデータベース２０６に適用されるデータベースデータ変更は、最初に第２のデータベース２１０に複製され、次に第２のデータベース２１０から第３のデータベース２１４に複製される。
【００４８】
図２に示すような実施形態では、データベースサーバエンジンが３つのデータベースサーバおよび３つのデータベースを含むが、別の実施形態では、データベースサーバエンジンが２つのデータベースサーバおよび２つのデータベースのみを含む。例えば、データベースサーバエンジン２００は、単に、データベースサーバ２０４および２０８と、マスタ−スレーブ複製構成に配置されたそれぞれのデータベース２０６および２１０とを備えることができる。
【００４９】
図２に示すような実施形態では、データベースサーバエンジンがアプリケーション層のクライアントプロセスからのクライアント要求をデータベースサーバ２０４、２０８、および２１２に送られるデータベース要求に変換するためのコアサーバを含むが、データベースサーバエンジンはコアサーバを含まない。この場合、アプリケーション層内のクライアントプロセスは、データベースサーバ２０４、２０８、および２１２にデータベース要求を直接送信することができる。
【００５０】
ローカル複製
【００５１】
図３は、本発明の一実施形態によるローカル複製プロセス３００を示す。プロセス３００は、同じデータベースサーバエンジン３０６のマスタデータベースサーバ３０２およびスレーブデータベースサーバ３０４を含む。マスタデータベースサーバ３０２は、以下でより詳細に説明するように、アプリケーション層内のクライアントプロセスからの作成コマンド、更新コマンド、及び削除コマンドと、データバキュームコンピューティングシステムからの削除コマンドとを受信する（Ｓ３０８）。作成コマンド、更新コマンド、および削除コマンドは、ＳＱＬ(Structure Query Language)などによって組み立てることができる。例えば、作成コマンド、更新コマンド、および削除コマンドは、それぞれ、ＳＱＬのＩＮＳＥＲＴコマンド、ＵＰＤＡＴＥコマンド、およびＤＥＬＥＴＥコマンドとすることができる。データベースコマンドは、ネットワーク通信プロトコルに従ってデータ通信ネットワークを介して、または他の適切なプロセス間通信機構（例えば、名前付きパイプ、共有メモリなど）を介して受信され得る。
【００５２】
本明細書で使用されるように、文脈において特に明白でない限り、用語「マスタ」はデータベースに格納された特定のデータ（これはデータベースに格納されたすべてのデータのサブセットであり得る）の「マスタ」として指定され、マスタ−スレーブ複製スキームに参加し、それによって、データベース内のデータベースデータに対する変更が、やはり複製スキームに参加する１つまたは複数の「スレーブ」データベースサーバおよび／または１つまたは複数のスレーブデータベースに伝播される、データベースサーバまたはデータベースを指す。データベースサーバとデータベースは、データベース内のすべてのデータのマスタ、またはデータベース内のすべてのデータより少ないデータのマスタと見なすことができる。すべてより少ない場合、データベースサーバおよびデータベースは、それらがマスタするデータに関しては共にマスタのデータベースサーバおよびデータベースであり、データベース内の他のデータに関してはスレーブのデータベースサーバおよびデータベースであり得る。
【００５３】
マスタデータベース３０２は、受信したデータベースコマンドをマスタデータベース３１２に対して実行する（Ｓ３１０）。さらに、マスタデータベース３０２は、実行されたデータベースコマンドに対応する複製イベントをバイナリログ３１６に記録（ログ）する（Ｓ３１４）。バイナリログ３１６に記録される各複製イベントは、ステートメントベースのロギングフォーマットまたは行ベースのロギングフォーマットで記録され得る。ステートメントベースのロギングはデータベースコマンド（例えば、ＳＱＬステートメント）をマスタデータベースサーバ３０２からスレーブデータベースサーバ３０４に伝播するために使用され、それらはスレーブデータベースサーバ３０４によってスレーブデータベース３１８に対して実行される。行ベースのロギングは個々のデータベースデータオブジェクト（例えば、個々のデータベーステーブル行）の変更を記録するために使用される。
【００５４】
マスタデータベースサーバ３０２は、揮発性メモリバッファを介して、不揮発性メモリ内に持続されたバイナリログ３１６に、逐次的に複製イベントを書き込む（ログする）ことができる。したがって、バイナリログ３１６は不揮発性メモリに持続され得るが、揮発性メモリバッファに格納された複製イベント３１６はバイナリログ３１６に格納され得る。
【００５５】
スレーブデータベースサーバ３０４は、マスタデータベースサーバ３０２に対して、ネットワーク通信プロトコルに従うデータ通信ネットワークを介して、または別のプロセス間通信メカニズムを介して、複製イベントを要求することができる（Ｓ３２０）。マスタデータベースサーバ３０４は、バイナリログ３１６内の複製イベントを、ネットワーク通信プロトコルに従うデータ通信ネットワークを介して、または別のプロセス間通信機構を介して、スレーブデータベースサーバ３０４に送信することができる（Ｓ３２２）。代替処理として、スレーブデータベースサーバ３０４は、バイナリログ３１６から直接複製イベントを読み取ることができる。
【００５６】
マスタデータベースサーバ３０２は、不揮発性記憶装置から複製イベントを読み取る必要なしに、揮発性メモリバッファからスレーブデータベースサーバ３０４に新しい複製イベントを提供することができる。しかしながら、スレーブデータベースサーバ３０４が、バイナリログ３１６に記憶された複製イベントに関してマスタデータベースサーバ３０２の背後にある場合、マスタデータベースサーバ３０２はスレーブデータベースサーバ３０４を最新にするために、不揮発性記憶装置から複製イベントを読み取る必要がある場合がある。その後、マスタデータベースサーバ３０２は、バイナリログ３１６の揮発性メモリバッファからスレーブデータベースサーバに新しい複製イベントを提供することができる。
【００５７】
スレーブデータベースサーバ３０４が取得する複製イベントは、リレーログ３２６に記録（ログ記録）されてもよい（Ｓ３２４）。通常、バイナリログ３１６に格納された複製イベントに関して、スレーブデータベースサーバ３０４がマスタデータベースサーバ３０２の実質的に背後にない場合、リレーログ３２６に格納された最新の複製イベントは、バイナリログ３１６に格納された最新の複製イベントから１つ、２つ、少数、または小さな数の複製イベントだけ背後にある。
【００５８】
スレーブデータベースサーバ３０４は、リレーログ３２４から複製イベントを先入れ先出し順序で読み取り（Ｓ３２８）、それらをその順序でスレーブデータベース３１８に適用することができる（Ｓ３２０）。スレーブデータベースサーバ３０４は、複製イベントがステートメントベースであるか行ベースであるかに従って、各複製イベントを適用する。このようにして、ローカル複製プロセス３００は、マスタデータベース３１２からスレーブデータベース３１８へデータを複製する。
【００５９】
マスタデータベースサーバ３０２が複製イベントをバイナリログ３１６に書き込み（Ｓ３１４）、複製イベントをスレーブデータベースサーバ３０４に送信する（Ｓ３２２）こと、および、スレーブデータベースサーバ３０４が複製イベントをリレーログ３２６に書き込み（Ｓ３２４）、複製イベントをリレーログ３２６から読み出し（Ｓ３２８）、複製イベントをスレーブデータベース３１８に適用する（Ｓ３３０）ことを含む、所与の複製イベントに関して、一般にシリアルに実行される動作をマスタデータベースサーバ３０２およびスレーブデータベースサーバ３０４が実行することにより費やされる時間を含む、様々な要因がローカル複製プロセス３００における複製遅延に寄与する可能性がある。
【００６０】
サーバエンジン３０６のコンポーネントは、１つまたは複数のプロセッサおよびメモリを備えるコンピューティングシステム上に実装され得る。コンピューティングシステムの１つまたは複数のプロセッサおよびメモリは、１つまたは複数のコンピューティングマシンによって提供され得る。図３にはコンポーネントが別々に示されているが、様々なコンポーネントを異なるコンピューティングマシンまたは同じコンピューティングマシン上に実装することができる。例えば、マスタサーバ３０２、マスタデータベース３１２、およびバイナリログ３１６は第１のコンピューティングマシン上で実装されてもよく、スレーブサーバ３０４、スレーブデータベース３１８、およびリレーログ２１６は第２の異なるコンピューティングマシン上で実装されてもよい。あるいは、すべてのコンポーネントが１つのコンピューティングマシン上に実装されてもよい。
【００６１】
地理的複製
【００６２】
図４は、本発明の一実施形態による地理的複製プロセス４００を示す。地理的複製プロセス４００は、イベントストリームプロセッサを使用して、データセンタ間で複製イベントを移動させる。図示のように、第１のデータセンタ４０６は、マスタデータベースサーバ４０２、マスタデータベース４１４、およびバイナリログ４１８を収容する。第２の地理的に離れたデータセンタ４０８は、スレーブデータベースサーバ４０４、スレーブデータベース４３４、およびリレーログ４２８を収容する。バイナリログ４１８に記憶されたデータベースイベントのリレーログ４１８への複製は、イベントストリームプロセッサによって促進される。イベントストリームプロセッサは、イベントプロデューサ４２０、イベントストリームログ４２２、およびイベントコンシューマ４２４を含むことができる。イベントストリームプロセッサのコンポーネントは、図４では任意のデータセンタに存在するものとしては示されていないが、コンポーネントのいくつかまたはすべてはデータセンタ４０６および／またはデータセンタ４０８に存在することができる。
【００６３】
地理的複製プロセス４００のステップＳ４１０、Ｓ４１４、およびＳ４１６は、それぞれ、ローカル複製プロセス３００のステップＳ３０８、Ｓ３１０、およびＳ３１４と同様であってもよい。しかし、地理的複製プロセス４００の場合、イベントプロデューサ４２０は、バイナリログ４１８から複製イベントを先入れ先出し順序で読み取るか、さもなければ取得し（Ｓ４３６）、それらを保存するか、さもなければ複製イベントをその順序でイベントストリームログ４２２に保存させる（Ｓ４３８）ことができる。イベントストリームログ４２２は、一実施形態では追加専用の分散コミットログとして実装される。イベントコンシューマ４２４は、イベントストリームログから複製イベントを先入れ先出し順序で読み取るか、さもなければ取得し（Ｓ４４０）、複製イベントをその順序でリレーログ４２８に保存する。次に、スレーブデータベースサーバ４０４は、リレーログ４２８から複製イベントを読み取り（Ｓ４３０）、それらを先入れ先出し順にスレーブデータベース４３４に適用する（Ｓ４３２）。このようにして、複製イベントは、イベントストリームプロセッサを介してマスタデータベース４１４からスレーブデータベース４３４に「ストリーミング」されることができる。
【００６４】
マスタデータベースサーバ４０２、イベントプロデューサ４２０、イベントコンシューマ４２４、およびスレーブデータベースサーバ４０４が所与の複製イベントに関して一般にシリアルに実行される動作を実行するのに費やされる時間を含む様々な要因が、地理的複製プロセス４００における複製遅延に寄与する可能性がある。地理的複製遅延に寄与し得る操作は、マスタデータベースサーバ４０２が複製イベントをバイナリログ４１８に書き込み、またはさもなければ格納させること（Ｓ４１６）、イベントプロデューサがバイナリログ４１８から複製イベントを読み出し、またはさもなければ取得し（Ｓ４３６）、複製イベントをイベントストリームログ４２２に書き込み、またはさもなければ格納させること（Ｓ４３８）、イベントコンシューマがイベントストリームログ４２２から複製イベントを読み出し、またはさもなければ取得し（Ｓ４４０）、複製イベントをリレーログ４２８に書き込み、またはさもなければ格納させること（Ｓ４２６）、および、スレーブデータベースサーバ４０４がリレーログ３２６から複製イベントを読み出し、またはさもなければ取得し（Ｓ４３０）、複製イベントをスレーブデータベース４３４に適用すること（Ｓ４３４）、を含み得る。
【００６５】
図４に示される様々なコンポーネントは、１つまたは複数のプロセッサおよびメモリを備えるコンピューティングシステム上で実装され得る。コンピューティングシステムの１つまたは複数のプロセッサおよびメモリは、コンピューティングマシンによって提供され得る。図４にはコンポーネントが別々に示されているが、様々なコンポーネントを異なるコンピューティングマシンまたは同じコンピューティングマシン上に実装することができる。例えば、マスタサーバ４０２、マスタデータベース４１４、バイナリログ４１８、およびイベントプロデューサ４２０はデータセンタ４０６内の第１のコンピューティングマシン上に実装されてもよいし、スレーブサーバ４０４、スレーブデータベース４３４、リレーログ４２８、およびイベントコンシューマ４２４は、データセンタ４０８内の第２の異なるコンピューティングマシン上で実装されてもよい。
【００６６】
複製遅延に制約されるデータ削除のプロセス
【００６７】
図５は、本発明の一実施形態による、分散データストレージシステムにおける複製遅延に制約されるデータ削除のためのプロセス５００を示す。プロセス５００は、１つまたは複数のプロセッサおよびメモリを備えるコンピューティングシステムによって実装され得る。コンピューティングシステムの１つまたは複数のプロセッサおよびメモリは、１つまたは複数のコンピューティングマシンによって提供され得る。明確な例を提供するために、プロセス５００は、「データバキューム」コンピューティングシステムによって実行されるものとして以下で説明される。
【００６８】
動作Ｓ５０２において、データバキュームは、実行すべき削除タスクを取得する。一実施形態によれば、データバキュームは、コマンドラインインタフェース、グラフィカルユーザインタフェース、および／または設定ファイルインタフェースを介して削除タスクを取得することができる。削除タスクは、データオブジェクトのマスタデータベースである分散データストレージシステムのデータベースに格納されたデータオブジェクトを対象とする。削除タスクは、多くのデータオブジェクトを対象とすることができる。例えば、削除タスクは、数万個以上のデータベーステーブル行をターゲットとすることができる。
【００６９】
ターゲットデータオブジェクトを削除するために、データバキュームは、一連のデータベースコマンドを、データオブジェクトのマスタデータベースのマスタデータベースサーバにシリアルに提出する。各コマンドの提出（Ｓ５０８）の後、データバキュームは休止間隔の間スリープする（Ｓ５１０）。スリープはある長さの時間（例えば、休止間隔）の間、データバキュームプロセスまたはそのスレッドの実行を休止するシステムコールまたは標準ライブラリコールを呼び出すことによって達成され得るものであり、ここで、時間の長さは、コールに対するパラメータとして指定される。
【００７０】
休止間隔は図６に関して以下に説明するように、データバキュームによって周期的に調整することができる。データベースコマンドを提出し（Ｓ５０８）、スリープした後（Ｓ５１０）、削除すべきターゲットデータオブジェクトがさらに存在する場合（Ｓ５０４）、プロセス５００は、別のデータベースコマンドの提出（Ｓ５０８）により継続する。そうではなく、全てのターゲットデータオブジェクトが削除された場合、プロセス５００は終了する（Ｓ５０６）。
【００７１】
一実施形態では、各データベースコマンドは、データベースコマンドによって削除するデータオブジェクトの最大数を指定するＳＱＬ(Structure Query Language)ＤＥＬＥＴＥコマンドである。一実施形態では、削除するデータオブジェクトの最大数をＳＱＬ  ＬＩＭＩＴクローズ(clause)によって指定することができる。一実施形態では、削除するデータオブジェクトの最大数が１，０００〜１０，０００の範囲である。マスタデータベースサーバは、データベーストランザクションのコンテキストでコマンドを実行することができる。
【００７２】
データバキュームは、削除タスクによってターゲットとされるデータオブジェクトが分散データストレージシステム内の２つ以上のデータベースによってマスタリングされる場合、複数のマスタデータベースサーバに対して並列にプロセス５００を実行することができる。この場合、データベースコマンドは、それぞれのマスタデータベースサーバのそれぞれに対して逐次的に提出することができる。
【００７３】
休止間隔の調整
【００７４】
最初に、休止間隔は、所与の削除タスクのデフォルト値を開始することができる。その後、休止間隔は、測定された複製遅延に基づいて、削除タスクの実行中にデータバキュームによって調整することができる。図６は、本発明の一実施形態による、測定された複製遅延に基づいて休止間隔を調整するためのプロセス６００を示す。
【００７５】
プロセス６００は、削除タスクによる削除の対象とされたデータオブジェクトをマスタするデータベースを処理する各マスタデータベースサーバのためのデータバキュームによって実行されてもよい。複数のそのようなマスタデータベースサーバが存在する場合、プロセス６００は、そのようなマスタデータベースサーバの各々について同時に実行されてもよい。
【００７６】
操作Ｓ６０２において、データバキュームは、ローカルスレーブ複製遅延メトリックを判定する。メトリックは、単一のローカルスレーブ複製遅延測定値または複数のローカルスレーブ複製遅延測定値に基づいて判定することができる。複数のローカルスレーブ複製遅延測定値がローカルスレーブ複製遅延メトリックを判定するために使用される場合、メトリックは、複数の測定値の平均(average)、平均(mean)、加重平均(weighted average)、または加重平均(weighted mean)として計算され得る。一実施形態では、ローカルスレーブ複製遅延測定値は、ローカル複製遅延を表す秒またはミリ秒などの時間ベースの値である。
【００７７】
ローカル複製遅延を測定するために、データバキュームによって様々な技法を使用することができる。一実施形態では、「ハートビート」技法が使用される。ハートビート技法によれば、データベースオブジェクト（例えば、データベーステーブルのデータベーステーブル行）は、データバキュームによってマスタデータベースにおいて定期的に（例えば、数秒ごとに）、挿入されるか、または更新時の現在のシステムクロックタイムを反映する現在のタイムスタンプを用いて更新される。データオブジェクトへの挿入または更新がローカルスレーブデータベースに複製された後、タイムスタンプがスレーブデータベースから読み取られ、現在のシステムクロックタイムと比較される。データベースオブジェクトのタイムスタンプと、ローカルセーブデータベースからタイムスタンプが読み取られるときの現在のシステムクロックタイムとの間の時間差を、ローカル複製遅延の測定値として使用することができる。
【００７８】
操作Ｓ６０４において、データバキュームは、地理的複製遅延メトリックを判定する。  メトリックは、単一の地理的スレーブ複製遅延測定値または複数の地理的スレーブ複製遅延測定値に基づいて判定することができる。複数の地理的スレーブ複製遅延測定値がローカルスレーブ複製遅延メトリックを判定するために使用される場合、メトリックは、複数の測定値の平均(average)、平均(mean)、加重平均(weighted average)、または加重平均(weighted mean)として計算され得る。一実施形態では、地理的スレーブ複製遅延測定値は、地理的複製遅延を表す秒またはミリ秒などの時間ベースの値である。
【００７９】
地理的複製遅延を測定するために、上述のハートビート技法を含む様々な技法をデータバキュームによって使用することができる。しかしながら、地理的複製遅延を測定するために、タイムスタンプは、別のデータセンタ内の地理的スレーブデータベースから読み取られる。  データベースオブジェクトのタイムスタンプと、地理的スレーブデータベースからタイムスタンプが読み取られるときの現在のシステムクロックタイムとの間の時間差を、地理的複製遅延の測定値として使用することができる。時間差が地理的スレーブデータベースにおいて計算される場合、時間差の値は、データネットワークを介して地理的マスタデータベースに送信されてもよい。
【００８０】
操作Ｓ６０６において、ローカルスレーブ複製遅延メトリックがローカルスレーブ複製遅延閾値と比較され、地理的スレーブ複製遅延メトリックが地理的複製遅延閾値と比較される。非限定的な実施形態では、ローカルスレーブ複製遅延閾値は１／２ミリ秒〜数ミリ秒の範囲であり、地理的複製遅延閾値は５００ミリ秒〜数秒の範囲である。比較に基づいて、いずれかまたは両方のメトリックがそれぞれの閾値を上回る場合、操作Ｓ６０８で、データバキュームは、所定のインクリメント量だけ休止間隔を増加させる。一実施形態では、所定のインクリメント量がローカルスレーブ複製遅延メトリックおよび地理的スレーブ複製遅延メトリックの最大値に等しい。一方、両方のメトリックがそれぞれの閾値を下回る場合、操作Ｓ６１０において、データバキュームは、所定のデクリメント量だけ休止間隔を減少させる。一実施形態では、所定のデクリメント量がローカルスレーブ複製遅延メトリックの最小値と地理的スレーブ複製遅延メトリックとの間の範囲である。
【００８１】
データバキュームはプロセス６００を周期的に実行して、削除タスクが実行されたときにマスタデータベースからのデータの削除レートがローカルおよび地理的複製遅延によって制約されるように、休止間隔を調整することができる。そうすることによって、データバキュームは、複製サブシステムを含む分散データストレージシステムを削除コマンドで圧倒してしまうことを回避する。
【００８２】
一実施形態では、ローカルスレーブ複製遅延メトリックまたは地理的スレーブ複製遅延メトリックが現在それぞれの閾値を上回っているかどうかにかかわらず、データバキュームはステップＳ５１０で各削除コマンドの提出後に休止間隔の間スリープしてもよいが、別の実施形態では、ローカルスレーブ複製遅延メトリックまたは地理的スレーブ複製遅延メトリックのいずれかが現在それぞれの閾値を上回っている間だけ、データバキュームは休止間隔の間スリープする。この別の実施形態では、ローカルスレーブ複製遅延メトリックおよび地理的スレーブ複製遅延メトリックの両方がそれぞれの閾値未満のままである限り、およびその間、データバキュームは削除コマンドの提出後にいかなる長さの時間もスリープしなくてよい。メトリックの一方または両方が閾値を超えると、データバキュームは、削除コマンドの提出後、休止間隔の間スリープすることができる。そうすることによって、ローカルスレーブおよび地理的スレーブ複製遅延メトリックの両方がそれぞれの閾値未満であってもデータバキュームが削除コマンドの提出後にある時間の間休止する構成と比較して、データバキュームはより速い削除レートで分散データストレージシステムからデータを削除することができる。
【００８３】
基本的な実施メカニズム
【００８４】
本発明は、１つまたは複数のプロセッサおよびメモリを備えるコンピューティングシステムを使用して実施することができる。１つまたは複数のプロセッサおよびメモリは、１つまたは複数のハードウェアマシンによって提供され得る。図７は、本発明の一実施形態による、本発明を実施するために使用することができる基本ハードウェアマシン７００の一例を示す。ハードウェアマシン７００およびそのハードウェアコンポーネント（それらの接続、関係、および機能を含む）は、例示的なものにすぎず、本発明の実装形態を限定することを意味するものではない。本発明を実施するのに適した他のハードウェアマシンは、異なる接続、関係、および機能を有するコンポーネントを含む、異なるコンポーネントを有することができる。
【００８５】
ハードウェアマシン７００は、メインメモリ７０６をアドレス指定し、ハードウェアマシン７００の様々なコンポーネント間でデータを転送するためのバス７０２または他の通信メカニズムを含む。
【００８６】
ハードウェアマシン７００はまた、情報を処理するためにバス７０２に結合されたプロセッサ７０４を含む。プロセッサ７０４は、汎用マイクロプロセッサ、システムオンチップ（ＳｏＣ）、または他のハードウェアプロセッサであってもよい。
【００８７】
ランダムアクセスメモリ（ＲＡＭ）または他のダイナミックストレージデバイスなどのメインメモリ７０６は、情報およびプロセッサ７０４によって実行されるソフトウェア命令を記憶するためにバス７０２に結合される。メインメモリ７０６はまた、プロセッサ７０４によって実行されるソフトウェア命令の実行中に一時変数または他の中間情報を記憶するために使用されてもよい。
【００８８】
ソフトウェア命令は、プロセッサ７０４にアクセス可能な記憶媒体に記憶されると、ハードウェアマシン７００を、ソフトウェア命令に指定された動作を実行するようにカスタマイズされた専用コンピューティングマシンにする。用語「ソフトウェア」、「ソフトウェア命令」、「コンピュータプログラム」、「コンピュータ実行可能命令」、および「プロセッサ実行可能命令」は、人間が読み取り可能であるか否かにかかわらず、特定の動作を実行するようにマシンに命令するための任意のマシン可読情報を包含するように広く解釈されるべきであり、アプリケーションソフトウェア、デスクトップアプリケーション、スクリプト、バイナリ、オペレーティングシステム、デバイスドライバ、ブートローダ、シェル、ユーティリティ、システムソフトウェア、ＪＡＶＡＳＣＲＩＰＴ、ウェブページ、ウェブアプリケーション、モバイルアプリケーション、プラグイン、埋め込みソフトウェア、マイクロコード、コンパイラ、デバッガ、インタープリタ、仮想マシン、リンカ、およびテキストエディタを含むがこれらに限定されない。
【００８９】
ハードウェアマシン７００は、プロセッサ７０４のための静的情報およびソフトウェア命令を記憶するためにバス７０２に結合されたリードオンリメモリ（ＲＯＭ）７０８または他の静的記憶装置を含む。
【００９０】
大容量記憶装置７１０は、磁気、光学、ソリッドステート、磁気−光学、フラッシュメモリ、または任意の他の利用可能な大容量記憶技術などの固定または取外し可能媒体上に情報およびソフトウェア命令を永続的に記憶するためにバス７０２に結合される。大容量記憶装置は、ネットワークで共有されてもよいし、専用大容量記憶装置であってもよい。大容量記憶装置７１０は、オペレーティングシステム、ユーザアプリケーションプログラム、ドライバ、および他のサポートファイル、ならびにあらゆる種類の他のデータファイルを含む、ハードウェアマシン７００の動作を指示するためのプログラムおよびデータの本体を記憶することができる。
【００９１】
ハードウェアマシン７００は、コンピュータユーザに情報を表示するために、バス７０２を介して、液晶ディスプレイ（ＬＣＤ）または他の電子視覚ディスプレイなどのディスプレイ７１２に結合され得る。タッチ検知技術（例えば、抵抗性、容量性等）を組み込んだタッチセンシティブ表面をディスプレイ７１２に組み込んで、タッチジェスチャ（例えば、指またはスタイラス）入力をプロセッサ７０４に通信するためのタッチセンシティブディスプレイを形成することができる。
【００９２】
入力デバイス７１４は、情報およびコマンド選択をプロセッサ７０４に通信するためにバス７０２に結合されてもよい。入力デバイス７１４は、英数字および他のキーを含むことができる。入力デバイス７１４は例えば、電源（オン／オフ）ボタン、「ホーム」ボタン、音量制御ボタンなどの１つまたは複数の物理的ボタンまたはスイッチを含むことができる。
【００９３】
方向情報およびコマンド選択をプロセッサ７０４に通信し、ディスプレイ７１２上のカーソル移動を制御するための、マウス、トラックボール、タッチパッド、タッチセンシティブ表面、またはカーソル方向キーなどのカーソル制御部７１６をバス７０２に結合することができる。カーソル制御部７１６は第１の軸（例えば、ｘ）および第２の軸（例えば、ｙ）の２つの軸において２つの自由度を有することができ、これは、デバイスが平面内の位置を指定することを可能にする。カーソル制御部７１６は第３の軸（例えば、ｚ）によってより多くの自由度を有することができる。例えば、カーソル制御部７１６は３つの垂直軸における３つの並進自由度（例えば、サージ、ヒーブ、およびスウェイ）を有することができ、これは、デバイスが３つの軸における位置を指定することを可能にする、カーソル制御部７１６は、３つの垂直軸の周りに３つの回転自由度（例えば、ピッチ、ヨー、ロール）を有することができ、これにより、デバイスは、３つの軸の周りの向きを指定することができる。
【００９４】
ディスプレイ７１２、入力デバイス７１４、およびカーソル制御部７１６のうちの１つまたは複数は、ハードウェアマシン７００の外部コンポーネント（すなわち、周辺デバイス）とすることができるが、ディスプレイ７１２、入力デバイス７１４、およびカーソル制御部７１６のうちのいくつかまたはすべてはハードウェアマシン７００のフォームファクタの一部として統合することができる。
【００９５】
本発明の機能または動作は、メインメモリ７０６に含まれるソフトウェア命令の１つまたは複数のプログラムをプロセッサ７０４が実行することに応答して、ハードウェアマシン７００によって実行することができる。そのようなソフトウェア命令は、記憶装置７１０などの別の記憶媒体からメインメモリ７０６に読み込まれてもよい。メインメモリ７０６に含まれるソフトウェア命令の実行は、プロセッサ７０４に機能または動作を実行させる。
【００９６】
本発明の機能または操作はソフトウェア命令で完全に実装されてもよいが、ハードウェアマシン７００のハードワイヤードまたはプログラマブル回路（例えば、ＡＳＩＣ、ＦＰＧＡなど）が、機能または操作を実行するために、ソフトウェア命令の代わりに、またはソフトウェア命令と組み合わせて使用されてもよい。
【００９７】
本明細書で使用される「記憶媒体(storage media)」という用語は、ハードウェアマシンを特定の方式で動作させるデータおよび／またはソフトウェア命令を記憶する任意の非一時的媒体を指す。そのような記憶媒体は、不揮発性媒体および／または揮発性媒体を含むことができる。不揮発性媒体は例えば、不揮発性ランダムアクセスメモリ（ＮＶＲＡＭ）、フラッシュメモリ、光ディスク、磁気ディスク、または記憶装置７１０などのソリッドステートドライブを含む。揮発性媒体は、メインメモリ７０６のようなダイナミックメモリを含む。記憶媒体の一般的な形態には、例えば、フロッピーディスク、フレキシブルディスク、ハードディスク、ソリッドステートドライブ、磁気テープ、または任意の他の磁気データ記憶媒体、ＣＤ−ＲＯＭ、任意の他の光データ記憶媒体、穴のパターンを有する任意の物理媒体、ＲＡＭ、ＰＲＯＭ、およびＥＰＲＯＭ、フラッシュＥＰＲＯＭ、ＮＶＲＡＭ、フラッシュメモリ、任意の他のメモリチップまたはカートリッジが含まれる。
【００９８】
記憶媒体は伝送媒体とは異なるが、伝送媒体と併せて使用することができる。伝送媒体は、記憶媒体間で情報を転送することに関与する。例えば、伝送媒体は、バス７０２を構成するワイヤを含む、同軸ケーブル、銅線、および光ファイバを含む。伝送媒体は、電波および赤外線データ通信中に生成されるような音波または光波の形態をとることもできる。
【００９９】
様々な形態の媒体が、実行のために１つまたは複数のソフトウェア命令の１つまたは複数のシーケンスをプロセッサ７０４に搬送することに関与し得る。例えば、ソフトウェア命令は最初に、リモートコンピュータの磁気ディスクまたはソリッドステートドライブ上で搬送されてもよい。リモートコンピュータはソフトウェア命令をそのダイナミックメモリにロードし、データ通信ネットワークを介してソフトウェア命令を送信することができる。ハードウェアマシン７００は、データ通信ネットワークを介してデータを受信することができ、適切な回路は、バス７０２上にデータを配置することができる。バス７０２はデータをメインメモリ７０６に搬送し、そこからプロセッサ７０４はソフトウェア命令を取得して実行する。メインメモリ７０６によって受信されたソフトウェア命令は、オプションとして、プロセッサ７０４による実行の前または後に記憶装置７１０に記憶されてもよい。
【０１００】
ハードウェアマシン７００は、バス７０２に結合された通信インタフェース７１８を含むことができる。通信インタフェース７１８は、ハードウェアマシン７００をデータ通信ネットワーク７２２（例えば、ローカルエリアネットワーク（ＬＡＮ）、ワイドエリアネットワーク（ＷＡＮ）、ワイヤレスローカルエリアネットワーク（ＷＬＡＮ）、メトロポリタンエリアネットワーク（ＭＡＮ）、ストレージエリアネットワーク（ＳＡＮ）など）に接続する有線または無線ネットワークリンク７２０に結合する双方向データ通信を提供する。ネットワークリンク７２０は、ネットワーク７２２を介して１つまたは複数の他のネットワーク化されたデバイスにデータ通信を提供する。
【０１０１】
通信インタフェース７１８は、様々なタイプの情報を表すデジタルデータストリームを搬送する電気信号、電磁気信号、または光信号を送受信することができる。例えば、通信インタフェース７１８は、有線ネットワークインタフェースカード、統合無線アンテナを有する無線ネットワークインタフェースカード、またはモデムによって実装され得る。
【０１０２】
ネットワークリンク７２０は、ネットワーク７２２を介して、ホストコンピュータまたはインターネットサービスプロバイダ（ＩＳＰ）によって運営されるデータ機器への接続を提供することができる。次いでＩＳＰは、現在一般に「インターネット」と呼ばれているワールドワイドパケットデータ通信ネットワークを介してデータ通信サービスを提供することができる。ネットワーク７２２およびインターネットは、デジタルデータストリームを搬送する電気信号、電磁気信号、または光信号を使用する。様々なネットワークを通る信号、およびハードウェアマシン７００との間でデジタルデータを搬送する、ネットワークリンク７２０上のかつ通信インタフェース７１８を通る信号は、伝送媒体の例示的な形態である。
【０１０３】
ハードウェアマシン７００は、ネットワーク７２２、ネットワークリンク７２０、および通信インタフェース７１８を介して、メッセージを送信し、プログラムコードを含むデータを受信することができる。インターネットの例では、サーバがインターネット、ＩＳＰ、ネットワーク７２２、および通信インタフェース７１８を介して、アプリケーションプログラムの要求されたコードを送信することができる。
【０１０４】
受信されたコードは、受信されたときにプロセッサ７０４によって実行されてもよく、および／または後の実行のために記憶装置７１０または他の不揮発性記憶装置に記憶されてもよい。
【０１０５】
図８は、本発明の一実施形態による、図７のハードウェアマシン７００の動作を制御するために使用することができる基本ソフトウェアシステム８００を示す。ソフトウェアシステム８００およびそのソフトウェアコンポーネント（それらの接続、関係、および機能を含む）は、例示的なものにすぎず、本発明の実装形態を限定することを意味するものではない。本発明を実施するのに適した他のソフトウェアシステムは、異なる接続、関係、および機能を有するコンポーネントを含む、異なるコンポーネントを有することができる。
【０１０６】
ソフトウェアシステム８００は、ハードウェアマシン７００の動作を指示するために提供される。ソフトウェアシステム８００は、システムメモリ（ＲＡＭ）７０６および固定記憶装置（例えば、ハードディスクまたはフラッシュメモリ）７１０に記憶することができる。
【０１０７】
ソフトウェアシステム８００は、カーネルまたはオペレーティングシステム（ＯＳ）８１０を含む。ＯＳ８１０はプロセスの実行、メモリ割り当て、ファイル入出力（Ｉ／Ｏ）、およびデバイスＩ／Ｏの管理を含む、コンピュータ動作の低レベルの態様を管理する。
【０１０８】
ソフトウェアシステム８００は、ハードウェアマシン７００による実行のために「ロード」（例えば、固定記憶装置７１０からメモリ７０６に転送）することができる、８０２Ａ、８０２Ｂ、８０２Ｃ．．．８０２Ｎとして表される１つまたは複数のアプリケーションプログラムを含む。ハードウェアマシン７００上での使用を意図されたアプリケーションまたは他のソフトウェアはまた、例えば、インターネットロケーション（例えば、ウェブサーバ、アプリケーションストア、または他のオンラインサービス）からダウンロードおよびインストールするための、ダウンロード可能なコンピュータ実行可能命令のセットとして格納されてもよい。
【０１０９】
ソフトウェアシステム８００は、グラフィカル（例えば、「ポイントアンドクリック」または「タッチジェスチャ」）方式でユーザコマンドおよびデータを受信するためのグラフィカルユーザインタフェース（ＧＵＩ）８１５を含む。次に、これらの入力は、オペレーティングシステム８１０および／またはアプリケーション８０２からの指示に従って、システム８００によって作用され得る。ＧＵＩ８１５はまた、ＯＳ８１０およびアプリケーション８０２からの操作の結果を表示する役割も果たし、その結果、ユーザは追加の入力を供給するか、またはセッションを終了する（例えば、ログオフする）ことができる。
【０１１０】
ソフトウェアシステム８００はベアハードウェア８２０（例えば、マシン７００）上で直接実行することができる。あるいは、「タイプ１」ハイパーバイザ８３０を、ソフトウェアシステム８００の一部としてベアハードウェア８２０とＯＳ８１０との間に挿入することができる。ハイパーバイザ８３０は、ＯＳ８１０とベアハードウェア８２０との間のソフトウェア「クッション」または仮想化層として働く。ハイパーバイザ８３０は、１つまたは複数の仮想マシンインスタンスをインスタンス化し、実行する。各仮想マシンインスタンスは、ＯＳ８１０などの「ゲスト」オペレーティングシステムと、ゲストオペレーティングシステム上で実行するように設計されたアプリケーション８０２などの１つまたは複数のアプリケーションとを含む。ハイパーバイザ８３０は、ゲストオペレーティングシステムに仮想オペレーティングプラットフォームを提供し、ゲストオペレーティングシステムの実行を管理する。
【０１１１】
ハイパーバイザ８３０は、ゲストオペレーティングシステムがベアハードウェア８２０上で直接実行されているかのように、ゲストオペレーティングシステムを実行させることができる。この場合、ベアハードウェア８２０上で実行するように構成されたゲストオペレーティングシステムは、ハイパーバイザ８３０上でも実行することができる。言い換えると、ハイパーバイザ８３０は、ゲストオペレーティングシステムに完全なハードウェア仮想化を提供することができる。あるいは、ハイパーバイザ８３０がゲストオペレーティングシステムにパラ仮想化を提供することができる。この場合、ゲストオペレーティングシステムは、ハイパーバイザ８３０上で実行していることを「認識」しており、ハイパーバイザ８３０上で実行するように特別に設計または構成されている。
【０１１２】
追加例
【０１１３】
本開示の態様の例示的な例を以下に提供する。実施形態は、以下に記載される例のうちの任意の少なくとも１つ、および任意の組み合わせを含んでもよい。例えば、以下に明示的に示されていなくても、方法の態様はシステムに含まれてもよく、システムの態様は方法に含まれてもよい、などである。
【０１１４】
例１において、分散データストレージシステムにおいて複製遅延に制約されるデータ削除を引き起こすためのシステムは、１以上のプロセッサと、メモリと、前記１以上のプロセッサによる実行のための前記メモリに格納された１以上のコンピュータプログラムと、を備え、前記１以上のコンピュータプログラムは、前記システムに動作を実行させるように構成された命令を含み、前記動作は、データベースサーバにデータベースからデータを削除させる第１の複数のコマンドを、前記データベースサーバへ逐次的に提出することと、（ａ）地理的スレーブデータベース複製遅延メトリックが対応する閾値を上回っていること、及び（ｂ）ローカルスレーブデータベース複製遅延メトリックが対応する閾値を上回っていること、の両方を判定したことに少なくとも部分的に基づいて、前記データベースサーバに前記データベースからデータを削除させる第２の複数のコマンドを、前記データベースサーバへ逐次的に提出することであって、前記第２の複数のコマンドのうちのコマンドの各提出の後に休止間隔の間スリープすることを含む、ことと、を含む。
【０１１５】
例２は、例１の主題を含み、前記地理的スレーブデータベース複製遅延メトリックは、第１の地理的スレーブデータベース複製遅延メトリックであり、前記休止間隔は、第１の休止間隔であり、前記命令は更に、（ａ）第２の地理的スレーブデータベース複製遅延メトリックが対応する閾値を上回っていること、及び（ｂ）第２のローカルスレーブデータベース複製遅延メトリックが対応する閾値を下回っていること、の両方を判定したことに少なくとも部分的に基づいて、前記第１の休止間隔を第２の休止間隔へと増加させることと、前記データベースからデータを削除する第３の複数のコマンドを、前記データベースサーバへ逐次的に提出することであって、前記第３の複数のコマンドのうちのコマンドの各提出の後に前記第２の休止間隔の間スリープすることを含む、ことと、を行うように構成される。
【０１１６】
例３は、例１の主題を含み、前記地理的スレーブデータベース複製遅延メトリックは、第１の地理的スレーブデータベース複製遅延メトリックであり、前記休止間隔は、第１の休止間隔であり、前記命令は更に、（ａ）第２の地理的スレーブデータベース複製遅延メトリックが対応する閾値を下回っていること、及び（ｂ）第２のローカルスレーブデータベース複製遅延メトリックが対応する閾値を下回っていること、の両方を判定したことに少なくとも部分的に基づいて、第３の複数のコマンドのうちのコマンドの各提出の後に前記休止間隔の間スリープすること無しに、前記データベースからデータを削除する前記第３の複数のコマンドを、前記データベースサーバへ逐次的に提出することを行うように構成される。
【０１１７】
例４は、例１乃至３のいずれかの主題を含み、前記第１の複数のコマンドの各コマンド、及び前記第２の複数のコマンドの各コマンドは、構造化照会言語（ＳＱＬ）の削除コマンドである。
【０１１８】
例５は、例１又は例４の主題を含み、前記休止間隔は、第１の休止間隔であり、前記命令は更に、前記第１の複数のコマンドのうちのコマンドの各提出の後に前記第１の休止間隔よりも短い第２の休止間隔の間スリープすることを行うように構成される。
【０１１９】
例６は、例５の主題を含み、前記命令は更に、（ａ）前記地理的スレーブデータベース複製遅延メトリックが前記対応する閾値を上回っていること、及び（ｂ）前記ローカルスレーブデータベース複製遅延メトリックが前記対応する閾値を上回っていること、の両方を判定したことに少なくとも部分的に基づいて、前記第２の休止間隔を前記第１の休止間隔へと増加させることを行うように構成される。
【０１２０】
例７は、例１乃至６のいずれかの主題を含み、前記命令は更に、前記地理的スレーブデータベース複製遅延メトリック及び前記ローカルスレーブデータベース複製遅延メトリックのうちの最大値として前記休止間隔を選択することを行うように構成される。
【０１２１】
例８は、例１乃至７のいずれかの主題を含み、前記データベースからデータを削除する前記第１の複数のコマンドを、前記データベースサーバへ逐次的に提出することは、前記第１の複数のコマンドのうちのコマンドの各提出の後に休止間隔の間スリープしないことに少なくとも部分的に基づいている。
【０１２２】
例９は、例１乃至８のいずれかの主題を含み、前記１以上のコンピュータプログラムは、前記システムに動作を実行させるように構成された命令を含み、前記動作は、地理的スレーブデータベース複製遅延メトリックを判定することであって、前記地理的スレーブデータベース複製遅延メトリックを判定することは、前記データベースから前記データベースとは異なる場所にある第２のデータベースへとデータベースデータを複製する複製プロセスの測定時間を反映するデータ値に基づく、ことを含む。
【０１２３】
例１０は、例１乃至９のいずれかの主題を含み、前記１以上のコンピュータプログラムは、前記システムに動作を実行させるように構成された命令を含み、前記動作は、ローカルスレーブデータベース複製遅延メトリックを判定することであって、前記ローカルスレーブデータベース複製遅延メトリックを判定することは、前記データベースから前記データベースと同じ場所にある第３のデータベースへとデータベースデータを複製する複製プロセスの測定時間を反映するデータ値に基づく、ことを含む。 
【０１２４】
例１１は、例９又は例１０の主題を含み、前記１以上のコンピュータプログラムは、前記地理的スレーブデータベース複製遅延メトリックが地理的スレーブデータベース複製遅延閾値を上回っていることを判定することを含む動作を前記システムに実行させるように構成された命令を含む。
【０１２５】
例１２は、例１０又は例１１の主題を含み、前記１以上のコンピュータプログラムは、前記ローカルスレーブデータベース複製遅延メトリックがローカルスレーブデータベース複製遅延閾値を上回っていることを判定することを含む動作を前記システムに実行させるように構成された命令を含む。
【０１２６】
例１３は、例１０乃至１２のいずれかの主題を含み、前記１以上のコンピュータプログラムは、前記システムに動作を実行させるように構成された命令を含み、前記動作は、（ａ）前記地理的スレーブデータベース複製遅延メトリックが対応する地理的スレーブデータベース複製遅延閾値を上回っていること、及び（ｂ）前記ローカルスレーブデータベース複製遅延メトリックが対応するローカルスレーブデータベース複製遅延閾値を上回っていること、の両方を判定したことに少なくとも部分的に基づいて、前記第１の複数のコマンドに関連する休止間隔を調整することを含む。
【０１２７】
例１４は、例１乃至１３のいずれかの主題を含み、前記１以上のコンピュータプログラムは、前記第２の複数のコマンドを前記データベースサーバへ逐次的に提出することにより、前記第１の複数のコマンドを逐次的に提出することにより前記第１のデータベースからデータが削除される削除レートとは異なる削除レートで、前記データベースサーバに前記第１のデータベースからデータを削除させることを含む動作を前記システムに実行させるように構成された命令を含む。
【０１２８】
例１５は、例１４の主題を含み、前記第２の複数のコマンドを逐次的に提出することは、前記第２の複数のコマンドのうちのコマンドの提出の後に調整された休止間隔の間スリープすることに基づく。
【０１２９】
例１６において、１以上のプロセッサとメモリとを備えるコンピューティングシステムによって実行される、分散データストレージシステムにおける複製遅延に制約されるデータ削除のための方法は、データベースからデータを削除する第１の複数のコマンドを、データベースサーバへ逐次的に提出することであって、前記複数のコマンドのうちのコマンドの各提出の後に第１の休止間隔の間休止することを含む、ことと、ローカルスレーブデータベース複製遅延メトリックが対応する閾値を上回っていることを判定したことに少なくとも部分的に基づいて、前記第１の休止間隔を第２の休止間隔へと増加させることと、前記データベースからデータを削除する第２の複数のコマンドを、前記データベースサーバへ逐次的に提出することであって、前記第２の複数のコマンドのうちのコマンドの各提出の後に前記第２の休止間隔の間休止することを含む、ことと、を備える。
【０１３０】
例１７は、例１６の主題を含み、前記第１の休止間隔を増加させることは、（ａ）前記ローカルスレーブデータベース複製遅延メトリックが対応する閾値を上回っていることを判定したこと、及び（ｂ）地理的スレーブデータベース複製遅延メトリックが対応する閾値を上回っていることを判定したこと、の両方に少なくとも部分的に基づく。 
【０１３１】
例１８は、例１６又は例１７の主題を含み、（ａ）第２のローカルスレーブデータベース複製遅延メトリックが対応する閾値を下回っていること、及び（ｂ）地理的スレーブデータベース複製遅延閾値が対応する閾値を下回っていること、の両方を判定したことに少なくとも部分的に基づいて、前記第２の休止間隔を第３の休止間隔へと減少させることと、前記データベースからデータを削除する第３の複数のコマンドを、前記データベースサーバへ逐次的に提出することであって、前記第３の複数のコマンドのうちのコマンドの各提出の後に前記第３の休止間隔の間休止することを含む、ことと、を含む。 
【０１３２】
例１９は、例１６乃至１８のいずれかの主題を含み、第１のタイムスタンプに関連するデータベースレコードを第１のデータベースに書き込むことと、前記データベースレコードが第２のデータベースへ複製された後に、前記第２のデータベースから前記第１のタイムスタンプを含む前記データベースレコードを読み取ることと、前記第２のデータベースから読み取られた前記データベースレコードの前記第１のタイムスタンプに少なくとも部分的に基づいて、前記ローカルスレーブデータベース複製遅延メトリックを判定することと、を含む。
【０１３３】
例２０は、例１６乃至１９のいずれかの主題を含み、前記ローカルスレーブ複製遅延メトリックは、同じデータセンタ内に同じ場所に配置された２つのデータベース間の複製遅延を評価するものであり、前記地理的スレーブ複製遅延メトリックは、異なるデータセンタ内に配置された２つのデータベース間の複製遅延を評価するものである。
【０１３４】
例２１は、例１６乃至２０のいずれかの主題を含み、前記第１の複数のコマンドの各コマンドは、構造化照会言語（ＳＱＬ）の削除コマンドである。
【０１３５】
例２２は、例１６乃至２１のいずれかの主題を含み、前記第１の複数のコマンドの各コマンドは、異なるデータベーストランザクションの文脈において前記データベースに対して実行される。
【０１３６】
例２３は、例１６乃至２２のいずれかの主題を含み、地理的スレーブデータベース複製遅延メトリックを判定することであって、前記地理的スレーブデータベース複製遅延メトリックを判定することは、前記データベースから前記データベースとは異なる場所にある第２のデータベースへとデータベースデータを複製する複製プロセスの測定時間を反映するデータ値に基づく、ことを含む。
【０１３７】
例２４は、例２３の主題を含み、ローカルスレーブデータベース複製遅延メトリックを判定することであって、前記ローカルスレーブデータベース複製遅延メトリックを判定することは、前記データベースから前記データベースと同じ場所にある第３のデータベースへとデータベースデータを複製する複製プロセスの測定時間を反映するデータ値に基づく、ことを含む。 
【０１３８】
例２５は、例２３又は例２４の主題を含み、前記地理的スレーブデータベース複製遅延メトリックが地理的スレーブデータベース複製遅延閾値を上回っていることを判定することを含む。
【０１３９】
例２６は、例２４又は例２５の主題を含み、前記ローカルスレーブデータベース複製遅延メトリックがローカルスレーブデータベース複製遅延閾値を上回っていることを判定することを含む。
【０１４０】
例２７は、例２４乃至２６のいずれかの主題を含み、前記１以上のコンピュータプログラムは、前記システムに動作を実行させるように構成された命令を含み、前記動作は、（ａ）前記地理的スレーブデータベース複製遅延メトリックが対応する地理的スレーブデータベース複製遅延閾値を上回っていること、及び（ｂ）前記ローカルスレーブデータベース複製遅延メトリックが対応するローカルスレーブデータベース複製遅延閾値を上回っていること、の両方を判定したことに少なくとも部分的に基づいて、前記第１の複数のコマンドに関連する休止間隔を調整することを含む。
【０１４１】
例２８は、例１６乃至２７のいずれかの主題を含み、前記第２の複数のコマンドを前記データベースサーバへ逐次的に提出することにより、前記第１の複数のコマンドを逐次的に提出することにより前記第１のデータベースからデータが削除される削除レートとは異なる削除レートで、前記データベースサーバに前記第１のデータベースからデータを削除させることを含む。
【０１４２】
例２９は、例２８の主題を含み、前記第２の複数のコマンドを逐次的に提出することは、前記第２の複数のコマンドのうちのコマンドの提出の後に調整された休止間隔の間スリープすることに基づく。
【０１４３】
例３０において、１以上の非一時的コンピュータ可読媒体は、１以上のプロセッサとメモリとを備えるコンピューティングシステムによる実行のための、分散データストレージシステムにおける複製遅延に制約されるデータ削除のための１以上のプログラムを格納し、例１６乃至２９のいずれかの方法を実行する命令を含む。
【０１４４】
拡張および代替
【０１４５】
様々な図面のいくつかは論理ステージを順序で示すことができるが、順序に依存しないステージは再順序付けされてもよく、他のステージは組み合わされたり分解されたりしてもよい。いくつかの再順序付けまたは他のグループ分けが具体的に言及されてもよいが、他のものは当業者には明らかであり、したがって、本明細書で提示される順序付けおよびグループ分けは代替物の網羅的なリストではない。さらに、これらのステージは、ハードウェア、ファームウェア、ソフトウェア、またはそれらの任意の組合せで実装できることを理解されたい。 
【０１４６】
前述の説明は、説明の目的で、特定の実施形態に関して説明されてきた。しかしながら、上記の例示的な実施形態は、網羅的であること、または特許請求の範囲を開示された正確な形態に限定することを意図していない。上記の教示に鑑みて、多くの修正および変形が可能である。実施形態は、特許請求の範囲の基礎をなす原理およびそれらの実用的なアプリケーションを最もよく説明するように選択され、それによって、他の当業者が企図される使用に適した様々な修正を伴う実施形態を最もよく使用することを可能にした。 
【要約】
分散データストレージシステムにおける複製遅延に制約されるデータ削除のためのコンピュータ実装技法。いくつかの態様では、本技法は、深刻な複製遅延を引き起こす削除レートが高すぎることを防止し、同時に、ローカル複製遅延および地理的複製遅延の両方に関して測定された複製遅延によって制約される最大許容削除レートまで経時的に削除レートを増加および減少させることによって、コンピューティングシステムの動作を改善する。一実施形態では、削除レートは、データベース削除コマンドをデータベースサーバに提出する間にデータベースデータ削除プロセスがどれだけ長く休止するかを決定する休止間隔を増加または減少させることによって調整される。【図１】
0006653789.tif 000002
【図２】
0006653789.tif 000003
【図３】
0006653789.tif 000004
【図４】
0006653789.tif 000005
【図５】
0006653789.tif 000006
【図６】
0006653789.tif 000007
【図７】
0006653789.tif 000008
【図８】
0006653789.tif 000009