(57)【要約】複製書き込みのためのトークンベースの承認制御のための方法及び装置が開示される。データオブジェクトは、区画に分けられ、各区画に対応して、少なくともマスター複製とスレーブ複製とが記憶される。区画に向けられる書き込み要求を承諾するべきかどうかについての決定は、（ａ）マスター複製で利用可能なスループット容量、及び（ｂ）スレーブ複製で利用可能なスループット容量のトークンベースのプロトコルを使用して取得される指標のうちの１つ以上に少なくとも部分的に基づく。書き込み要求が承諾されると、１つ以上のデータ修正動作が開始される。
2016517080.tif 000002
【特許請求の範囲】
【請求項１】
１つ以上の論理区画を含むデータオブジェクトの論理区画に対応して、前記論理区画のマスター複製及び前記論理区画のうちの１つ以上のスレーブ複製を記憶することであって、複製方針に従って、前記論理区画への書き込みが、前記マスター複製及び少なくとも１つのスレーブ複製で複製される、記憶することと、
前記マスター複製に対応して、１つ以上のバケットを含むマスターバケット集合、及び１つ以上のバケットを含むスレーブスナップショットバケット集合を記憶することであって、前記マスターバケット集合及び前記スレーブスナップショットバケット集合の各バケットが、（ａ）前記論理区画に向けられる動作のスループットを制限するように使用可能なトークンの各々の補充可能な集まりを含み、（ｂ）許可された動作のために消費されるトークンの数を示すトークン消費方針を有する、記憶することと、
スレーブバケット更新プロトコルに少なくとも部分的に基づいて、前記スレーブスナップショットバケット集合のうちの特定のバケットのトークン母集団を更新することであって、前記スレーブバケット更新プロトコルに従って、前記マスター複製が、前記１つ以上のスレーブ複製のうちの特定のスレーブ複製のデータの少なくとも一部が記憶される共用記憶デバイスで利用可能なスループット容量の指標を取得するように構成され、前記共用記憶デバイスが、１つ以上のデータオブジェクトのうちの１つ以上の論理区画に対応するデータを記憶するように構成可能である、更新することと、
前記論理区画に向けられる書き込み要求を受信することに応答して、
前記マスターバケット集合及び前記スレーブスナップショットバケット集合の前記バケットの各々のトークン消費方針に従って、十分な数のトークンが前記マスターバケット集合及び前記スレーブスナップショットバケット集合のうちの少なくとも１つのバケット集合において利用可能であるかどうかに少なくとも部分的に基づいて、前記書き込み要求が実行のために承諾されるべきであるかどうかを決定することと、
前記書き込み要求が実行のために承諾されるべきであると決定することに応答して、前記書き込み要求に対応する１つ以上のデータ修正動作を開始することと、を含む方法。
【請求項２】
前記マスターバケット集合のうちの特定のバケットのトークン母集団に少なくとも部分的に基づいて、前記論理区画が動作のバーストモードにあるかどうかを決定することと、
前記論理区画が動作のバーストモードにあると決定することに応答して、十分な数のトークンが（ａ）前記マスターバケット集合及び（ｂ）前記スレーブスナップショットバケット集合において利用可能であるかどうかに少なくとも部分的に基づいて、前記書き込み要求が実行のために承諾されるべきであるかどうかを決定することと、をさらに含む、請求項１に記載の前記方法。
【請求項３】
前記１つ以上のスレーブ複製が前記特定のスレーブ複製及び第２のスレーブ複製を含み、
前記特定のスレーブ複製に対応して、第１の共用デバイスバケットであって、前記第１の共用デバイスバケットのトークン母集団が前記共用記憶デバイスで利用可能なスループット容量を示す、前記第１の共用デバイスバケットを記憶することと、
前記第２のスレーブ複製に対応して、第２の共用デバイスバケットであって、前記第２の共用デバイスバケットのトークン母集団が、前記第２のスレーブ複製のデータの少なくとも一部が記憶される第２の共用記憶デバイスで利用可能なスループット容量を示す、前記第２の共用デバイスバケットを記憶することであって、前記第２の共用記憶デバイスが１つ以上のデータオブジェクトのうちの１つ以上の論理区画に対応するデータを記憶するように構成可能である、記憶することと、をさらに含み、
前記スレーブバケット更新プロトコルを実装することが、前記マスター複製が、前記（ａ）前記第１の共用デバイスバケットの前記トークン母集団及び（ｂ）前記第２の共用デバイスバケットの前記トークン母集団の各々の時点スナップショットを取得することを含む、請求項１に記載の前記方法。
【請求項４】
前記マスター複製から前記特定のスレーブ複製に、前記書き込み要求に対応する書き込み複製要求を送信することと、
前記マスター複製で、前記書き込み複製要求の確認応答を受信することであって、前記スレーブバケット更新プロトコルに従って、前記確認応答が、前記共用記憶デバイスでの、前記利用可能なスループット容量の指標を含む、受信することと、をさらに含む、請求項１に記載の前記方法。
【請求項５】
１つ以上のプロセッサと、
前記１つ以上のプロセッサに連結されるメモリであって、前記１つ以上のプロセッサによって実行されるとき、前記１つ以上のプロセッサに、
データオブジェクトのうちの１つ以上の論理区画の論理区画のマスター複製に対応して、１つ以上のバケットを含むマスターバケット集合及び１つ以上のバケットを含むスレーブスナップショットバケット集合を記憶することであって、前記マスターバケット集合及び前記スレーブスナップショットバケット集合の各バケットが、前記論理区画に向けられる書き込み動作のスループットを制限するように使用可能なトークンの各々の集まりを含む、記憶することと、
前記論理区画のうちの特定のスレーブ複製のデータの少なくとも一部が記憶される共用記憶デバイスにおける、利用可能なスループット容量の指標に少なくとも部分的に基づいて、前記スレーブスナップショットバケット集合のうちの特定のバケットのトークン母集団を更新することと、
前記論理区画に向けられる書き込み要求を受信することに応答して、
前記マスターバケット集合及び前記スレーブスナップショットバケット集合の前記バケットの各々のトークン消費方針に従って、十分な数のトークンが（ａ）前記マスターバケット集合及び（ｂ）前記スレーブスナップショットバケット集合のうちの少なくとも１つのバケット集合において利用可能であるかどうかに少なくとも部分的に基づいて、前記書き込み要求が実行のために承諾されるべきであるかどうかを決定することと、
実行に対して前記書き込み要求が承諾されるべきであると決定することに応答して、前記書き込み要求に対応する１つ以上のデータ修正動作を開始することと、を行わせる、というプログラム命令を記憶しているメモリと、を備えるシステム。
【請求項６】
前記プログラム命令が、前記１つ以上のプロセッサによって実行されるとき、前記１つ以上のプロセッサに、
前記特定のスレーブ複製及び第２のスレーブ複製を含む、前記論理区画の複数のスレーブ複製を記憶することと、
前記特定のスレーブ複製に対応して、第１の共用デバイスバケットであって、前記第１の共用デバイスバケットのトークン母集団が、前記共用記憶デバイスで利用可能なスループット容量を示す前記第１の共用デバイスバケットを記憶することと、
前記第２のスレーブ複製に対応して、第２の共用デバイスバケットであって、前記第２の共用デバイスバケットのトークン母集団が、前記第２のスレーブ複製のデータの少なくとも一部が記憶される第２の共用記憶デバイスで利用可能なスループット容量を示す前記第２の共用デバイスバケットを記憶することと、を行わせ、
前記特定のバケットの前記トークン母集団の前記更新が、（ａ）前記第１の共用デバイスバケットの前記トークン母集団のスナップショット及び（ｂ）前記第２の共用デバイスバケットの前記トークン母集団のスナップショットを取得する前記マスター複製に少なくとも部分的に基づく、請求項５に記載の前記システム。
【請求項７】
前記特定のバケットが、少なくとも前記特定のスレーブ複製及び前記第２のスレーブ複製の組み合わせに対応するコモンプロキシバケットを含み、前記プログラム命令が、前記１つ以上のプロセッサによって実行されるとき、前記１つ以上のプロセッサに、
前記第１及び第２の共用デバイスバケットの各々のスナップショットを取得することに少なくとも部分的に基づいて、前記第１及び第２の共用デバイスバケットの前記トークン母集団のなかの最小トークン母集団の推測を決定することと、
前記推測に基づいて、前記コモンプロキシバケットのトークン母集団を更新することと、
前記コモンプロキシバケットが少なくとも１つのトークンを含むという指標に少なくとも部分的に基づいて、実行のために前記書き込み要求を承諾することと、を行わせる、請求項６に記載の前記システム。
【請求項８】
前記スレーブスナップショットバケット集合が前記特定のスレーブ複製に対応する第１のスナップショットバケット及び前記第２のスレーブ複製に対応する第２のスナップショットバケットを含み、前記プログラム命令が、前記プログラムが、前記１つ以上のプロセッサによって実行されるとき、前記１つ以上のプロセッサに、
前記第１の共用デバイスバケットの前記トークン母集団の指標に基づいて、前記第１のスナップショットバケットの前記トークン母集団を更新することと、
前記第２の共用デバイスバケットの前記トークン母集団の指標に基づいて、前記第２のスナップショットバケットの前記トークン母集団を更新することと、
前記第１のスナップショットバケットが少なくとも１つのトークンを含み、前記第２のスナップショットバケットが少なくとも１つのトークンを含むという決定に少なくとも部分的に基づいて、実行のために前記書き込み要求を承諾することと、を行わせる、請求項６に記載の前記システム。
【請求項９】
前記プログラム命令が、前記１つ以上のプロセッサによって実行されるとき、前記１つ以上のプロセッサに、
前記マスター複製から前記特定のスレーブ複製に、前記書き込み要求に対応する複製要求を送信することと、
前記マスター複製で、前記複製要求の確認応答を受信することであって、前記確認応答が、前記共用記憶デバイスでの、前記利用可能なスループット容量の指標を含む、受信することと、を行わせる、請求５に記載の前記システム。
【請求項１０】
前記プログラム命令が、前記１つ以上のプロセッサによって実行されるとき、前記１つ以上のプロセッサに、
前記マスター複製で、前記特定のスレーブ複製から、前記特定のスレーブ複製の健康状態を示す心拍メッセージを受信することを行わせ、前記心拍メッセージが、前記共用記憶デバイスでの前記利用可能なスループット容量の指標を含む、請求５に記載の前記システム。
【請求項１１】
前記マスターバケット集合が準備された容量バケットを含み、前記プログラム命令が、前記１つ以上のプロセッサによって実行されるとき、前記１つ以上のプロセッサに、
前記データオブジェクトにアクセスするように権限を与えられたクライアントによって提供された標的とされるスループットの指標に少なくとも部分的に基づいて、その最初のトークン母集団及び補充速度を含む、前記準備された容量バケットのうちの１つ以上のパラメータを構成することと、
前記準備された容量バケットが少なくとも１つのトークンを含むという決定に少なくとも部分的に基づいて、前記書き込み要求が、実行のために承諾されるべきであると決定することと、を行わせる、請求５に記載の前記システム。
【請求項１２】
前記マスターバケット集合がバーストハンドリングバケットを含み、前記プログラム命令が、前記１つ以上のプロセッサによって実行されるとき、前記１つ以上のプロセッサに、
トークンを前記バーストハンドリングバケットに追加することであって、追加されたトークンの数が、前記論理区画に向けられる測定された動作速度が、特定の期間、前記標的とされるスループットより低いという決定に少なくとも部分的に基づく、追加することと、
（ａ）異なる書き込み要求を受信することと、（ｂ）前記異なる書き込み要求が受信されるとき、前記準備された容量バケットがトークンを含有しないことを決定することと、に応答して、前記バーストハンドリングバケットが少なくとも１つのトークンを含むという決定に少なくとも部分的に基づいて、実行のために前記異なる書き込み要求を承諾することと、を行わせる、請求項１１に記載の前記システム。
【請求項１３】
前記マスターバケット集合が、マスター共用デバイスバケットであって、前記マスター共用デバイスバケットのトークン母集団が前記マスター複製のデータの少なくとも一部を記憶するために使用される異なる共用記憶デバイスの利用可能なスループット容量に少なくとも部分的に基づく、前記マスター共用デバイスバケットを含み、前記プログラム命令が、１つ以上のプロセッサによって実行されるとき、前記１つ以上のプロセッサに、
前記マスター共用デバイスバケットが少なくとも１つのトークンを含むという決定に少なくとも部分的に基づいて、実行のために前記書き込み要求を承諾することと、を行わせる、請求５に記載の前記システム。
【請求項１４】
前記マスターバケット集合がノード能力バケットであって、前記ノード能力バケットのトークン母集団が、前記マスター複製のデータの少なくとも一部が記憶される記憶ノードの性能能力の測定基準に少なくとも部分的に基づく前記ノード能力バケットを含み、前記プログラム命令が、前記１つ以上のプロセッサによって実行されるとき、前記１つ以上のプロセッサに、
前記ノード能力バケットが少なくとも１つのトークンを含むという決定に少なくとも部分的に基づいて、実行のための前記書き込み要求を承諾することを行わせる、請求５に記載の前記システム。
【請求項１５】
システムであって、
１つ以上のプロセッサと、
１つ以上のメモリと、を備え、前記１つ以上のメモリが、その上にプログラム命令を記憶しており、前記プログラム命令が、１つ以上のプロセッサ上で実行されるとき、前記１つ以上のプロセッサに、
データオブジェクトの論理区画に対応して、マスター複製及び特定のスレーブ複製を含む１つ以上のスレーブ複製を記憶することであって、前記マスター複製が第１の記憶デバイスに記憶されたデータを含み、前記特定のスレーブ複製が第２の記憶デバイスに記憶されたデータを含む、記憶することと、
前記論理区画の少なくとも一部に向けられる書き込み要求を受信することと、
（ａ）前記マスター複製で利用可能なスループット容量、及び（ｂ）前記特定のスレーブ複製で利用可能なスループット容量のトークンベースのプロトコルを使用して取得される指標、のうちの１つ以上に少なくとも部分的に基づいて、実行のために前記書き込み要求を承諾すべきであるかどうかを決定することと、
実行に対して前記書き込み要求を承諾することに応答して、前記書き込み要求に対応する１つ以上のデータ修正動作を開始することと、を行わせる、前記システム。
【発明の詳細な説明】
【背景技術】
【０００１】
いくつかの先導的技術組織は、「サービスとしてのソフトウェア」を販売する建築技術に投資している。このようなサービスは、共用記憶装置（例えば、データベースシステム）へのアクセスを提供する、及び／またはコンピューティングリソースをクライアントまたは加入者に提供する。多層の電子商取引システム内において、異なるタイプのリソースの組み合わせが、物理的または仮想の機械全体、ＣＰＵ、メモリ、ネットワーク帯域幅、またはＩ／Ｏ容量などの加入者及び／または彼らのアプリケーションに割り当てられてもよい。
【０００２】
サービスをクライアントに提供するすべてのシステムは、システムを潜在的にオーバーロードし得るサービス要求の膨大な荷重から自身を保護する必要がある。概して、それが、それが受信するクライアント要求のなんらかの部分に対するサービスの予想品質を提供できない場合、ウェブサービスまたは遠隔手続呼び出し（ＲＰＣ）サービスに対して、システムは「オーバーロードされた」状態にあるとみなされる。オーバーロードされたシステムによって適用される一般的な解決策は、システムがオーバーロードされた状態から抜け出すまで、クライアントへのサービスを拒否することまたは一定数の着信要求を絞り込むことを含む。
【０００３】
いくつかの現在のシステムには、要求速度を固定または変動グローバル閾値と比較して、この閾値が超えられてしまうと、クライアントに対するサービスを選択的に拒絶することにより、オーバーロードシナリオを避けるものもある。しかしながら、このアプローチは、異なるタイプ及び／またはインスタンスのサービスに対するサービス要求を承諾することに応答して行われ得る作業量の違いを考慮してはいない。さらに、不可能ではないにしても、変動し、かつ予測不可能な速度の異なるタイプの要求を受信するシステムにおいて、（承諾可能な性能を提供するだけでなく）重要である単一のグローバル閾値を定義することは困難であり、そのために要求を満たすことを要求される作業量も、変動し、かつ予測不可能である。クライアント要求ストリームが、データ修正をもたらし得るいくつかの動作を含む一方、他の動作が読取り専用であるシナリオにおいて、作業負荷管理の問題は、任意の所定のデータ修正が複数の別々の記憶デバイスで持続されていることを規定した耐久性要求によってさらに複雑になり得る。
【図面の簡単な説明】
【０００４】
【図１】図１は、少なくともいくつかの実施形態によるシステム環境の実施例を示す。
【図２】図２は、少なくともいくつかの実施形態によるトークンベースの承認制御機構のハイレベル概観図を提供する。
【図３】図３は、少なくともいくつかの実施形態による承認制御のために使用されるトークンバケットの構成特性の実施例を示す。
【図４】図４は、少なくともいくつかの実施形態による、オブジェクト区画及び関連するクォーラムに基づくデータ修正方針の実施例を示す。
【図５】図５は、少なくともいくつかの実施形態による、データオブジェクト区画のマスター複製で維持され得る、トークンバケットのタイプの実施例を示す。
【図６】図６は、少なくともいくつかの実施形態による、データオブジェクト区画のスレーブ複製で維持され得る、トークンバケットのタイプの実施例を示す。
【図７】図７は、少なくともいくつかの実施形態による、データオブジェクト区画のマスター複製で維持され得る、トークンバケットのタイプの別の実施例を示す。
【図８】図８ａ及び８ｂは、少なくともいくつかの実施形態による、マスター複製において容量情報を通してスレーブを取得するための相互作用の各集合を示す。
【図９】図９は、少なくともいくつかの実施形態による、ネットワークにアクセス可能なサービスにおける書き込みのためのトークンベースの承認制御機構を実装するように行われてもよい動作の態様を示すフロー図である。
【図１０】図１０は、少なくともいくつかの実施形態による、動作のバーストモードの間の書き込みのためのトークンベースの承認制御機構を実装するように行われてもよい動作の態様を示すフロー図である。
【図１１】図１１ａ及び１１ｂは少なくともいくつかの実施形態による、マスター複製でスレーブ複製共用記憶バケット母集団を取得するように行われてもよい動作の態様を示すフロー図である。
【図１２】は、少なくともいくつかの実施形態で使用され得るコンピューティングデバイスの実施例を示すブロック図である。
【０００５】
実施形態は、本願においていくつかの実施形態及び例示的な図面についての実施例として示される一方、当業者は、実施形態が記載される実施形態または図面に限定されないことを認識するであろう。図面とそれら対する詳細な記載は、実施形態を開示される特定の形態に限定するものではないが、一方で添付の請求項により定義される趣旨及び範囲内に含まれる、すべての修正、相当物、及び代替案を網羅することが意図されることが理解されるべきである。本願において使用される表題は、組織的な目的のみのためであって、記載または請求項の範囲を限定するために使用される意図はない。本願を通して使用されるように、用語「〜かもしれない、〜し得る」は、義務の意味（すなわち、「〜しなければいけない」の意味）ではなく許容の意味（すなわち、「〜する可能性を有する」の意味）で使用される。同様に、「含む」や「含んでいる」という用語は、含んでいるが限定されないことを意味する。
【発明を実施するための形態】
【０００６】
複製書き込みのためのトークンベースの承認制御を実装するための方法及び装置の種々の実施形態が記載される。このようなプロトコルは、例えば、ネットワークにアクセス可能なサービス（雑居ストレージまたはデータベースサービスなど）が、記憶されている所定のデータ集合の複数のコピーまたは複製を取り込むデータ耐久性モデルを支持する種々の環境において、利用され得、ここで異なるコピーは、そのＩ／Ｏ関連作業負荷が互いに異なっていてもよいデバイスで記憶されてもよい。用語「承認制御」は、本願において、受信された作業要求（ストレージサービスに向けられる書き込み要求など）が実装のために承諾されるべきであるかどうかを決定するために行われる動作を表すために使用されてもよく、また、承認制御を行うことに関与するソフトウェア及び／またはハードウェアエンティティの集合は、集合的に「承認制御器」と称されてもよい。一般的に言えば、種々の実施形態において使用されるトークンベースの承認制御機構において、少なくとも１つのトークンバケットまたはコンテナは、所定のリソースまたは複製のために維持されてもよく、所定の着信作業要求を承諾するまたは拒否する決定がなされるときのこれらのバケット（複数を含む）の少なくとも１つにおけるいくつかの作業トークンの利用可能性は、所定のリソースまたは複製が要求された作業を取り扱いできるインジケータとして役立ってもよい。しかしながら、書き込みが複製される必要があるため、少なくとも以下に記載されるようなバーストモード動作などのいくつかの状況の下で、特別の考慮が書き込み動作要求を承認するために必要とされてもよく、従って、単一の複製における利用可能なスループット容量についての情報は、書き込みに対する良好な承認制御の決定をなすために不十分であってもよい。いくつかの実施形態によると、以下に記載される保守的な承認制御プロトコルは、データ書き込み動作（例えば、作成、更新、または削除動作）が、サービスによって、実行に対して承諾される場合、さもなければ生じ得るデータ損失または不一致の可能性を除外、または少なくとも著しく減少させてもよく、その後、承諾された書き込みは、複製のうちのいくつかにおけるオーバーロードまたは十分なスループット容量の欠如のために、所望の数の複製で複製されることが不可能である。用語「スループット容量」は、本願において、所与の速度で作業動作（例えば、読取りまたは書き込み動作）を終えるためのリソース（例えば、区画の複製）の能力を表すために使用される。スループット容量は、例えば、論理的または物理的Ｉ／Ｏ動作毎秒などの単位で表現されてもよい。用語「利用可能なスループット容量」は、その現在の作業負荷を仮定して、本願において、リソースが、どのくらいの量の追加的なスループットの推測または測定量を提供し得るかを表すために使用されてもよい。例えば、所定の記憶デバイスは最大１００Ｉ／Ｏ動作毎秒までを行うように構成されてもよいし、所定の秒数間、６０Ｉ／Ｏ動作毎秒の作業負荷を支持していてもよいし、この実施例において、その利用可能なスループット容量は、（１００〜６０）、または４０Ｉ／Ｏ動作毎秒であってもよい。所定のリソースの利用可能なスループット容量は、潜在的なハードウェアまたはソフトウェアの能力などの異なる実施形態における種々の異なる要因のいずれかの組み合わせに依存してもよいし、及び／または（負荷バランシング考慮、フェアネス考慮、ビジネス／価格設定考慮、またはハードウェア／ソフトウェアの天然の能力以外の要因のいくつかの組み合わせに基づいて）リソースでスループットを制御または制限するように実装されている方針に依存してもよいことに留意されたい。いくつかの実施形態において、リソースの利用可能なスループット容量はリソースでの現在の作業負荷の間接的な表現として役立ってもよい、例えば、作業負荷が上昇するにつれて、利用可能なスループット容量は徐々に下降してもよく、また、作業負荷が下降するにつれて、利用可能なスループット容量は（少なくとも方針で定義された限界まで）徐々に上昇してもよい。
【０００７】
以下に記載されるように、承認制御プロトコルに従って、いくつかの実施形態において、所定のデータオブジェクトの種々の複製で維持される作業トークンは、複製を記憶し、他のデータオブジェクトの複製間で共用されてもよい記憶デバイス（例えば、ソリッドステート記憶デバイス、またはディスクベースの記憶デバイス）で現在、利用可能なＩ／Ｏスループット容量の指標として使用されてもよい。用語「作業トークン」及び「トークン」は、本願においては、同意語として使用され得る。いくつかのこのような実施形態において、このようなトークンについてのデータは、新しい書き込み動作を承諾することまたは拒否することについての決定をなすときに使用される情報が、実現可能であるぐらい新しく正確であることを確実にする試みにおける異なる複製間で、効率的（及び少なくともいくつかの場合において頻繁に）に送信され得る一方、過剰な通信関連のオーバーヘッドを避ける。トークンベースの承認制御もまた、特定の記憶オブジェクトに対するＩ／Ｏ速度が、（少なくとも平均で）記憶オブジェクトの所有者と合意され準備されたスループット限界まで支持され得ることを確実にするために使用され得る。少なくともいくつかの実施形態において、準備されたスループット限界は、ストレージサービスのプロバイダが支持する義務がある（例えば、契約により支持する義務がある）作業負荷レベルを指示してもよい。いくつかのこのような実施形態において、サービスは、Ｉ／Ｏ要求速度が準備されたスループット限界より高くない限り、そのＩ／Ｏ要求（書き込みを含む）を承諾する義務がある場合がある。したがって、要求速度が準備されたスループット限界を下回る限り、オーバーロードにより書き込み複製が失敗する可能性が、典型的に、非常に低いままとなるように、サービスは、典型的に、データオブジェクトの複製を記憶するために使用されているデバイスを構成してもよい。しかしながら、クライアントは、彼らの要求を、常に均一に分散できなくてもよい、または、そうこうするうちに均一とは程遠い場合もあり、その結果、サービスが、少なくともいくらかの短い期間、要求到着速度が準備されたスループット限界を超えるシナリオを取り扱わなければならなくなる場合もある。特定の論理区画に対する要求速度が準備された限界を超えるとき、論理区画は、動作の「バーストモード」であるように称されてもよい。バーストモードの間、いくつかの実施形態において、ベストエフォート型作業負荷管理アプローチはサービスに使用されてもよく、サービスは準備された限界を超える要求のバーストを支持する義務はないが、それにもかかわらず、受信された要求を支持するために最善を尽くす。他の実施形態において、機構の態様は、着信要求負荷が準備されたスループット限界より低い期間でさえも利用され得るが、少なくともいくつかの実施形態において、以下に記載された書き込みに対する承認制御機構は、バーストモードの間、主に使用され得る。いくつかの実施形態において、トークンバケットの異なる集合及び対応する方針が読取りではなく書き込みのために使用されてもいい一方、他の実施形態においては、承認制御機構の少なくともいくつかの態様は、読取り及び書き込みのために共通して使用されてもよいことに留意されたい。
【０００８】
１つの実施形態によると、本願に記載されるトークンベースの承認制御機構は、少なくとも２つのタイプの目標、すなわち、（ａ）記憶オブジェクトに対して合意され準備されたスループット限界まで、Ｉ／Ｏ動作速度を支持することと、（ａ）バーストモードの間、動作要求が到着する速度が準備されたスループット限界を超えるときに、記憶オブジェクトに向けられる書き込み動作が所望の数の複製に成功裏に複製され得ることを確実にするベストエフォート型の試みを行うこと、を達成するように概して設計されていてもよい。他の実施形態において、承認制御機構は、（バーストモードか、通常の非バースト条件かのどちらかで）連続した書き込み複製を確実に行うことを試みるために主に使用され得る。用語「書き込み動作」または「書き込み」は、例えば、創造（新しいまたは追加的なデータの書き込み）、更新（インプレースの重ね書きを含んでもよい事前のデータに対する変化、または、例えば、いくつかの一回だけ書き込める環境において、新しいバージョンのデータの創造）、削除、名前の変更、及び／または移動を含む、データ及び／またはデータベース表、ファイル、またはボリュームなどのオブジェクトのメタデータが修正される種々のタイプの動作を言及してもよい。
【０００９】
インターネット及び／または他のネットワークを介してクライアントの分散された集合にアクセス可能な、１つ以上のこのようなサービス（種々のタイプのクラウド型ストレージ、コンピューティングまたはデータベースサービスなどの）を提供するための会社または公共機関などのエンティティによってセットアップされたネットワークは、本明細書においては、プロバイダネットワークと称されてもよい。所定のプロバイダネットワークは、プロバイダによって提供されるインフラストラクチャ及びサービスを実装、構成、及び分散させるのに必要な、種々のリソースプールをホストする、物理的な及び／または仮想化されたコンピュータサービス、各々が１つ以上の記憶デバイスを備えたストレージサーバ、ネットワーク装置などの集まりなどの多くのデータセンター（異なる地理的領域にわたって分散され得る）を含んでもよい。そのうちのいくつかが、異なるデータセンターで、または異なる地理的領域においてインスタンス化されるまたは実行され得る、いくつかの異なるハードウェア及び／またはソフトウェアコンポーネントは、書き込み承認制御プロトコルを種々の実施形態に実装するために集合的に使用されてもよい。例示する目的のために、承認制御プロトコルのための技術が記憶またはデータベースサービスの前後関係で以下に大きく示されているが、例えば、コンテンツが種々の終点に押し出され得る分散されたコンテンツ管理アプリケーション内で、または分散されたソフトウェア開発／展開シナリオ内で、また少なくともいくつかの実施形態でも、同様のアプローチが他の前後関係で使用されてもよいことに留意されたい。「Ｉ／Ｏ要求」及び「動作要求」（及び対応する用語「読取り要求」、「書き込み要求」、「読取り動作要求」、及び「書き込み動作要求」）は、本願において使用されるように、単一の論理的または物理的なＩ／Ｏ動作の要求に必ずしも対応する必要はないことにも留意されたい。その代わり、異なる実施形態において、本願において使用されるようなこれらの用語は、各々、いくつかの数の論理的及び／または物理的なＩ／Ｏ動作をもたらしてもよい、要求された「作業単位」を表してもよく、論理的及び／または物理的なＩ／Ｏ動作の数及び性質は、例えば、アプリケーションの性質または作業負荷条件に基づいて変更する。
【００１０】
１つの実施形態によると、（データベース表、ファイルまたは記憶ボリュームなどの）データオブジェクトのコンテンツは、サービスによって１つ以上の論理区画の中に分散されてもよい。例えば、データベースサービスのクライアントは、表が、およそＸテラバイト（ＴＢ）のデータを保持するべきで、かつ、Ｙ  Ｉ／Ｏ動作毎秒の作業負荷を支持することが予想されるべきであることを特定してもよく、データベースサービスは、Ｐ論理区画を備えた表をセットアップすることを決定してもよく、十分なリソースは、Ｘ／Ｐ  ＴＢを記憶し、Ｙ／Ｐ  Ｉ／Ｏ動作の準備されたスループット容量限界を各々、支持する論理区画ごとに、最初に指定されている。（例えば、いくつかの区画が知られている、または「よりホットである」と予想されている場合、または他のものより高い平均の要求速度を有する場合、区画にわたる準備されたスループット容量の不均一な分散が、いくつかの実施形態において、使用されてもよい。）承認制御の決定は、少なくともいくつかの実施形態において、論理区画レベルでなされてもよい。各論理区画に対応して、区画のデータのマスター複製及び１つ以上のスレーブ複製は、データオブジェクトに対するデータ耐久性方針またはデータ複製方針に従って、セットアップされてもよい。耐久性／複製方針は、データ書き込みが、装置の故障、電力損失、及び／または自然災害などの要因によるデータ損失の可能性が閾値を下回って維持される十分な数の別々の物理的な位置に複製されることを確実に行うように設計され得る。いくつかの実施形態において、書き込み要求に対する承認制御の決定はマスター複製でなされてもよい一方、読取りに対する承認制御の決定は、マスター複製、または（特に、クライアントが、潜在的に多少古いデータからの読取りを、進んで承諾する場合、）スレーブ複製のどちらかでなされてもよい。複製方針に従って、クライアントからの書き込み要求が承諾されると、いくつかの実施形態において、修正されたデータは、例えば、書き込みが成功した確認応答がクライアントに提供される前に、Ｎ個の複製（マスター複製及びＮ−１スレーブ複製）で成功裏に複製されなければならない。１つの実施形態において、セットアップされるスレーブ複製の数は、複製方針に必要とされる最小数を超えてもよい。複製方針は、書き込みが成功であるとみなされる前に、書き込みのＱ個のコピーのクォーラムが持続されるべきであることを要求してもよく、その結果、（Ｑ−１）個のスレーブ複製の最小値が必要とされる場合もある。しかしながら、読取り負荷バランシング、高い利用可能性などの種々の理由のため、維持されるスレーブ複製の数は、このような実施形態において、Ｑ−１を超えてもよい。後続の記載において、用語「マスター」及び「スレーブ」は、「マスター複製」及び「スレーブ複製」の語句をそれぞれ表すために本願において使用されてもよい。スレーブまたはマスターとしての特定の複製の指定が、種々の実施形態において徐々に変化し、例えば、所定の論理区画のためのマスターがインスタンス化されるデバイスが故障する、または手が届かなくなる場合、スレーブが先に指定された異なる複製がマスターとして選択されてもよいことに留意されたい。いくつかの実施形態において、例えば、データオブジェクトを所有するクライアントからの要求に応答して、スレーブ複製の数はデータオブジェクトの寿命にわたって変化してもよい。承認制御のために本願に記載される技術は、複製が必ずしもマスターまたはスレーブとして指定されないいくつかの実施形態においても、ピアツーピアの環境で適用されてもよく、このような実施の形態で、着信書き込み要求に対する承認制御の決定がなされる複製は、本願に記載されるように、（行われる動作のタイプという観点で）マスター複製に対応してもよい。このように、複製の大部分が責任について互いに同等であるピアツーピアの複製を利用するいくつかの実施形態において、書き込み要求が所定のピアＰ１で受信される場合、少なくとも１つの他のピアＰ２の利用可能なスループット容量についての情報は、書き込み要求が実行のために承諾されるべきであるかどうかを決定するために使用されてもよい。
【００１１】
いくつかの実施形態において、保守的な書き込み承認制御を実装するための方法は、マスター、マスターバケット集合、及びスレーブスナップショットバケット集合に対応して、記憶することを含んでもよい。マスターバケット集合及びスレーブスナップショットバケット集合は、例えば、新しい要求を実行のために承諾し、新しい動作が実行のために承諾されるときにトークンを消費し、トークン母集団が閾値を下回るときに、新しい動作を遅延させる、再試行する、また拒否する前に、十分なトークンが存在するかどうかを決定することにより、Ｉ／Ｏ動作のスループットを区画に制限するために使用されるトークンに対して、１つ以上のバケットまたはコンテナを含んでもよい。（用語「トークン母集団」及び「トークンカウント」は、本願において、同意語として用いられてもよい。）その母集団が書き込み要求を承諾する前に検査されるバケットの特定の組み合わせは、種々の実装において異なってもよく、及び／または対応する論理区画がバーストモードにあるかないかに依存して異なってもよい。例えば、１つの実施形態において、任意の他のバケットの母集団にもかかわらず、少なくとも１つのトークンがマスターバケット集合の特定のバケット（準備された容量バケットと称される）において利用可能である場合、書き込みは承認されてもよく、そのようなバケット内のトークンの存在は、論理区画が動作の通常の（非バースト）モードにあるという指標として役立ってもよい。書き込み要求がそのような実施形態で受信されるときに、準備された容量バケットが任意のトークンを含有しない場合、マスターバケットの１つ以上の他のバケット及びスレーブスナップショットバケット集合における少なくとも１つのバケットにおけるトークンカウントは、以下に詳細に述べられるように、書き込み要求を承諾すべきであるかどうかを決定するために考慮されてもよい。
【００１２】
いくつかの実施形態において、所定のバケットのトークンは、読取り及び書き込みの両方を承認するまたは制限するために使用されてもよい一方、他の実施形態において、トークンは、読取りのためにのみに使用されてもよい、または書き込みのためにのみ使用されてもよい。各バケットは、いくつかのこのような実施形態において、各々の最初のトークン母集団、トークン消費方針、トークン補充方針、母集団の最大値、母集団の最小値（以下に説明されるように、いくつかの場合、負数になってもよい）、及び／またはトークン欠損方針などの、構成特性の各々の集合を有してもよい。種々の実施形態におけるバケット構成パラメータの実施例に関するさらなる詳細が、図３の説明と併せて下記に提供される。マスターバケット集合は、概して、マスター独自の作業負荷及び利用可能な容量に関連付けられたバケットを含んでもよい一方、スレーブスナップショットバケット集合は、作業負荷及び／または利用可能な容量のマスターの見解をスレーブで反映する１つ以上のバケットを含んでもよい。このように、マスターバケット集合及びスレーブスナップショットバケット集合の組み合わせを使用して、マスター及びいくつかのスレーブの利用可能なスループット容量の統一見解が取得されてもよく、このような見解は、実行のための新しい書き込み要求を承諾することが望ましいかどうか、または書き込み要求を拒否するかどうかを決定するために（例えば、バーストモードの間、または通常モード及びバーストモードの両方で）使用されてもよい。少なくともいくつかの実施形態において、読取り要求は複製のうちのいずれか１つから満たされてもよく、その結果として、所定の複製におけるローカル作業負荷／容量条件のみが、新しい読取り動作を承諾すべきであるかどうかを決定するときに考慮されてもよい。このように、例えば、マスターに向けられる読取りのための承認決定は、このような実施形態において、マスターバケット集合のみのコンテンツを使用してなされ得、特定のスレーブに向けられる読取りのための承認決定は、そのスレーブのみで、作業負荷容量条件に基づいてなされ得る。
【００１３】
スレーブバケット更新プロトコルは、少なくともいくつかの実施形態において、スレーブスナップショットバケット集合でスレーブ状態（複数を含む）についての情報をリフレッシュするために使用されてもよい（例えば、スレーブスナップショットバケット集合は、マスターでそのバケットのうちの１つ以上におけるトークンの数を修正することによって、マスターでスレーブから受信された情報に基づいて更新されてもよい）。いくつかの実施形態において、トークンバケットはまた、バケットがマスターで使用される方法に類似した（しかし同一ではない）方法で、スループット管理のためのスレーブで使用されてもよい。スレーブバケット更新プロトコルに従って、１つのこのような実施形態において、スレーブは、スレーブのローカルトークンバケットのうちの１つ以上の母集団スナップショット（例えば、所定の時点におけるローカルトークンバケットの母集団の表現）をマスターに提供してもよい。例えば、１つの特定のスレーブ側のトークンバケットは、スレーブのデータの少なくとも一部が記憶される共用記憶デバイスで利用可能な容量を表してもよい。このような共用記憶デバイスはいくつかの論理区画の記憶するデータ（マスター複製、スレーブ複製のどちらか、または両方）のために使用されてもよく、その結果、共用記憶デバイスで経験される作業負荷はいくつかの異なるデータオブジェクトに対する使用量プロファイルに依存し得、予測することは容易ではないこともある。例えば、共用のデバイスＳＤ１及びＳＤｊ上の他の複製が論理区画の異なる組み合わせに所属し得、したがって、非常に異なる使用量パターンを有してもよいため、所定の論理区画Ｌの１つのスレーブＳ１のために使用される共用記憶デバイスＳＤ１は、異なるスレーブＳｊために使用される共用記憶デバイスＳＤｊとは非常に異なる作業負荷を有してもよい。所定の論理区画のスレーブによって使用され異なる共用記憶デバイス上の複製の組み合わせにおけるこのような変動の実施例は、いくつかの実施形態に対して下記の図１の考察と連動して記載される。用語「Ｘのスナップショット」または「Ｘスナップショット」は、本願において、語句「所定の時点におけるＸの表現」の代わりに使用されてもよい。このように、例えば、所定のトークンバケットＢに対する用語「バケット母集団スナップショット」は、所定の時点におけるＢのバケット母集団の表現を示してもよい。
【００１４】
所定の論理区画に向けられる書き込み要求を受信することに応答して、いくつかの実施形態において、保守的な書き込み承認制御のための方法は、マスターバケット集合及びスレーブスナップショットバケット集合のバケットの各々のトークン消費方針に従って、十分な数のトークンが（ａ）マスターバケット集合及び（ｂ）スレーブスナップショットバケット集合のうちの１つ以上において利用可能であるかどうかに少なくとも部分的に基づいて、書き込み要求が実行のために承諾されるべきであるかどうかを決定することを含んでもよい。１つの実施形態において、以下にさらに詳細に記載されるように、書き込み要求が承諾される場合、トークンは両方のバケット集合から消費されてもよいものの、動作の通常（非バースト）モードの間、マスターバケット集合（例えば、上述の通り、特に、マスターバケット集合内の準備された容量バケット）のみが、書き込み要求を承諾すべきであるかどうかを決定するために使用されてもよい。それに対して、バーストモードの間、トークンは書き込みを承諾するための両方のバケット集合で要求されてもよく、また、書き込みが承諾される場合には、両方のバケット集合から消費されてもよい。以下にも記載されるように、少なくともいくつかの実施形態において、区画がバーストモードにあるか通常モードにあるかは、それ自身、マスターバケット集合の特定のバケットのトークン母集団を使用して決定されてもよい。
【００１５】
いくつかの実施形態において、トークンは、通常モード間でさえ（例えば、区画に向けられる要求速度が、区画の準備されたスループット容量限界より高くないとき）両方のバケット集合から要求されてもよい。例えば、成功であるとみなされるために、書き込みがＭ及びＳ１の両方で持続されるべきである場合の、１つのスレーブＳ１及びマスターＭを備える１つの単純な実装の実施例について考える。このような実装において、マスターバケット集合ＭＢＳは、Ｍによって使用される記憶デバイスで利用可能なＩ／Ｏスループット容量を表しているトークンを含有する１つのバケットＭＢ１を含んでもよく、スレーブスナップショットバケット集合ＳＳＢＳは、Ｓ１の共用記憶デバイスで利用可能なスループット容量について最も新しく受信されたスナップショットを反映している単一のバケットＳＢ１を含んでもよい。単純な実施例を続けると、ＭＢＳ及びＳＳＢＳに適用可能な消費方針は、承諾されるべき書き込み要求のために、バケットＭＢ１及びＳＢ１の各々から消費されるべき１つのトークンを要求してもよい。したがって、両方のバケットのトークン母集団が検査されてもよい。このような実施例において、書き込み要求が受信されるときに、ＭＢ１に少なくとも１つのトークンがあり、ＳＢ１に少なくとも１つのトークンがある場合、要求は承諾され得る（潜在的な仮定が、各バケット内のトークンの存在が、書き込みを進行させるために、現在、マスター及びスレーブの両方で十分な容量が利用可能であることを示す）。ＭＢ１またはＳＢ１のどちらかにおいて、１つのトークンより小さいトークンがある場合、要求は拒否されてもよく、クライアントは、拒否（または書き込みが遅延されたり、再試行されたりしてもよい）に関して通知されてもよい。要求が承諾される場合、１つ以上のデータ修正動作が開始されてもよく（例えば、Ｍにおける１つの書き込み及びＳ１における書き込みの複製）、マスターにおけるバケットＭＢ１及びＳＢ１の両方において、トークンのカウントはデクリメントされる（トークンはまた、少なくともいくつかの実装において、書き込みがスレーブで複製されるときに、スレーブのローカルバケットでデクリメントされてもよい）。実行のために特定のＩ／Ｏ要求を承諾するために、トークンが複数のバケットから消費される少なくともいくつかの実施形態において、アトミックな動作（トランザクション、またはロックによって保護されるソフトウェアルーチンなど）は、関与するバケットすべてからトークンを消費するために使用されてもよい。書き込みがＳ１で複製された後に、クライアントは、いくつかの実施形態において修正が成功したことを通知されてもよい。
【００１６】
このように、少なくともいくつかの実施形態において、マスターは、１つ以上のスレーブから取得された情報に頼って書き込みに関する承認制御を決定することを助けてもよい。承認制御の決定の品質は、概して、決定のために使用されるマスター側データ及びスレーブ側データの両方の正確さに依存してもよい。少なくともいくつかの実施形態において、少なくとも書き込みに対する承認制御は、典型的に、マスターで行われてもよく、その結果、承認制御のために利用可能なマスター側データ（マスターバケット集合の種々のバケットのトークン母集団など）は、概して、非常に正確であり得る。それに対して、どのくらいの頻度でスレーブが、それらの共用記憶デバイスの状態で、更新をマスターに提供するかに依存して、承認制御のために使用されるスレーブについての情報（スレーブ側データと称されてもよい）は、潜在的に、古いものとなりかつ／または不正確になり得る。したがって、少なくともいくつかの実施形態において、スレーブバケット更新プロトコルは、スレーブ作業負荷容量についての頻繁な更新をマスターに提供するように設計されてもよい一方、同時に、スレーブ側情報の転送に対する過剰なオーバーヘッドを避ける。１つの実装において、例えば、マスターが書き込み複製要求を（例えば、書き込みに対する複製要求に従うために）スレーブに送るとき、スレーブは、スレーブの現在の利用可能な容量の「ピギーバックされる」時点における表現を含む、書き込み確認応答を送ってもよい（例えば、スレーブのローカル共用デバイストークンバケットの現在の母集団は、書き込み確認応答内に含まれてもよい）。スレーブが定期的な心拍または「私は生きている」というメッセージを少なくともマスターに送るように構成される別の実装において、スレーブの共用記憶デバイスにおける現在利用可能な容量の時点スナップショットは、心拍メッセージに含まれてもよい。いくつかの実装において、すべての書き込み確認応答及び／またはすべての心拍メッセージを備えるピギーバックされる母集団情報を送る代わりに、書き込み確認応答及び／または心拍のいくつかの部分集合のみが母集団の情報の転送のために使用され得る。スレーブ状態スナップショットは、書き込み確認応答、心拍メッセージ、及び／または種々の実装におけるスレーブ及びマスター間の他の通信のうちの任意の組み合わせに含まれてもよい。マスターは、例えば、いくつかの数学関数を、スナップショットに含有される情報に適用して、スレーブスナップショットバケットの母集団を数学関数の結果に設定することによって、スレーブスナップショットバケット集合内のバケットの母集団を変更するためにスレーブスナップショットを用いてもよい。種々の数学関数のいずれかは、以下に示されるように、異なる実装において、例えば、１つの単純な実装において、使用されてもよく、スレーブスナップショットバケット集合内のコモンプロキシバケットの母集団は、すべてのスレーブの共用デバイスバケットの最新の利用可能な母集団の最小値に設定され得る。別の実装において、時間依存性の関数は、スレーブ母集団情報に適用されて、スレーブスナップショットバケットの更新された母集団を決定してもよい（例えば、スレーブスナップショットの母集団は、どのくらい前に最新のスレーブ母集団スナップショットがマスターで受信されたかに依存して徐々に変更されてもよい）。いくつかの実施形態において、マスターが、いくらかの特定の期間、利用可能なスループット容量に関する情報を所定のスレーブから受信しない場合、所定のスレーブは、動作不可能またはアクセス不可能であると仮定されてもよく、スレーブスナップショットバケット集合の母集団はそれにより（例えば、代用スレーブが見つかるまで）調整されてもよい。
【００１７】
心拍メッセージ及び／または書き込み確認応答などのすでに他の目的に必要とされている通信上のピギーバックするスレーブ容量情報は、種々の実施形態において、保守的な書き込み承認制御プロトコルに関連付けられたオーバーヘッドを最小限にすることを助けてもよい。この目的のための書き込み確認応答を使用することは、論理区画の作業負荷の書き込み関連（読取り関連とは対照的に）部分が増加するのに伴って、書き込みがスレーブに伝播する速度も同様に増し、そのため、スレーブ側容量情報がマスターに送り返される速度もまた増加し得るような少なくともいくつかの実施形態において、追加的な利点を有し得る。これは、今度は、増加する書き込み負荷に対するより良い承認制御の決定の重要性もまた増加するとき、利用可能なスレーブスループット容量のマスターの見解のフレッシュさまたは新しいこと（したがっておそらく正確性）を期間中、増加させてもよい。
【００１８】
システム環境の実施例
図１は、少なくともいくつかの実施形態による、システム環境の実施例を示す。図示されるように、システム１００は、オブジェクト１０１Ａ、１０１Ｂ、１０１Ｃ、及び１０１Ｄなどの、多くのデータオブジェクト１０１（例えば、非リレーショナルまたはリレーショナルデータベース、ファイル、またはボリュームの表）を記憶するために使用されてもよい。オブジェクトのうちの少なくともいくつかは、オブジェクト１０１Ｄの論理区画Ｏ４−Ｐ１、Ｏ４−Ｐ２、…、Ｏ４−Ｐｎ、データオブジェクト１０１Ａの論理区画Ｏ１−Ｐ１、Ｏ１−Ｐ２、及びＯ１−Ｐ３、オブジェクト１０１Ｂの論理区画Ｏ２−Ｐ１及びＯ２−Ｐ２、データオブジェクト１０１Ｃの及び論理区画Ｏ３−Ｐ１及びＯ３−Ｐ２などの論理区画１０３を含んでもよい。表記「Ｏｘ−Ｐｙ」は、図１で、Ｏｘと称されるデータオブジェクトのｙ番目の論理区画を表すために使用される。
【００１９】
所定の論理区画Ｏｘ−Ｐｙに対応して、論理区画のデータの（表記「Ｏｘ−Ｐｙ−Ｍ」を使用して図１で表示される）少なくとも１つのマスターの物理的な複製、及び（ｋ番目のスレーブに対して、表記「Ｏｘ−Ｐｙ−Ｓｋ」を使用して表記される）少なくとも１つ以上のスレーブの物理的な複製は、図示される実施形態において維持され得る。各複製は各々の記憶デバイス１０２（例えば、デバイス１０２Ａ、１０２Ｂ、及び１０２Ｃ）で記憶されているように示される。（論理区画Ｏ１−Ｐ１に対する）マスター複製Ｏ１−Ｐ１−Ｍ及び（論理区画Ｏ２−Ｐ１に対する）スレーブＯ２−Ｐ１−Ｓ１及び（論理区画Ｏ３−Ｐ１に対する）Ｏ３−Ｐ１−Ｓ２は、記憶デバイス１０２Ａ上に存在するところが示される。記憶デバイス１０２は、例えば、ソリッドステートメモリデバイス、種々のタイプのＲＡＩＤ（独立したディスクの冗長アレイ）アレンジメント内に配置されたディスクドライブ、個々のディスクドライブ、ネットワーク接続ストレージ（ＮＡＳ）デバイス、ストレージエリアネットワーク（ＳＡＮ）デバイス、または持続的データのための任意の他の適切なデバイスを備えてもよい。図示される実施形態において、システム１００は、ノード１１０Ａ及び１１０Ｂなどの複数のストレージノード１１０を備えてもよいし、各ストレージノード１１０は、それに接続された１つ以上の記憶デバイス１０２を有してもよいし、または任意の所定の時点において、それからアクセス可能であってもよい。
【００２０】
図示される実施形態において、所定の記憶デバイス１０２は、種々のデータオブジェクト１０１及び論理区画１０３のマスター及び／またはスレーブ複製の間で共用されてもよい。例えば、記憶デバイス１０２Ａは、各々が異なる（オブジェクト、区画）の組み合わせの複製の部分を記憶する、１つのマスター（Ｏ１−Ｐ１−Ｍ）及び２つのスレーブ（Ｏ２−Ｐ１−Ｓ１及びＯ３−Ｐ１−Ｓ２）を備える。所定の時点で、（マスターＯ２−Ｐ１−Ｍ及びＯ４−Ｐ２−Ｍ及びスレーブＯ１−Ｐ１−Ｓ１を備えるデバイス１０２Ｂなどの）いくつかの記憶デバイスは、複数のマスターを含有してもよく、デバイス１０２Ｃなどの他の記憶デバイスは、スレーブのみを記憶してもよい一方、デバイス１０２Ａなどの他の記憶デバイスは、１つのマスター及び複数のスレーブを記憶してもよい。乱雑さを減らすため、オブジェクト１０１Ａ−１０１Ｄのすべての区画のすべての複製が、図１におけるそれらの各々の記憶デバイス１０２で図示されているわけではないことに留意されたい。多くの大型の実装において、数十または数百の論理区画の数十または数百の複製は、いくつかの大きい記憶デバイスで記憶され得る。概して、少なくともいくつかの実施形態において、複製及び記憶デバイス間のマッピング、複製のタイプ（マスター／スレーブ）及び記憶デバイス間のマッピング、及び記憶デバイス及びストレージノード間のマッピングにはかなりの柔軟性があってもよい。さらに、いくつかの実施形態において、所定の論理区画のいくつかの複製は、いくつかの理由のために、同じ論理区画の他の複製とは異なる地理的位置（例えば、異なるデータセンター）に記憶されてもよい。少なくともいくつかの実施形態において、論理区画の所定の複製が正確にどこに記憶されるべきかについての決定（例えば、どのストレージノードにおけるどの記憶デバイスが使用されるべきか）は、動的に変化する、種々のデバイス及びノードにおける利用可能な空間などの要因、種々のデバイス及びノードにおける予想されるまたは測定される作業負荷レベル、クライアントの嗜好、他の区画または複製に対する位置類似性または一時的な類似性、任意配置ヒューリスティック、デバイス故障測定基準、ネットワークトラフィック条件などに基づいてなされてもよい。
【００２１】
図１に図示される実施形態において、トークンバケットの少なくとも１つの集合は、例えば、その複製に関連付けられた動作のための承認制御を支援するために、複製ごとに維持される。Ｏ１−Ｐ１−Ｍなどのマスターに対して、例えば、１つのマスターバケット集合１５２（例えば、１５２Ａ、１５２Ｂまたは１５２Ｃ）及び１つのスレーブスナップショットバケット集合１５５（例えば、１５５Ａ、１５５Ｂ、または１５５Ｃ）などの少なくとも２つのトークンバケット集合が実装されてもよい。いくつかの実施形態において、スレーブバケット集合１７２は、対応する区画に関連付けられた書き込み承認制御の目的のため、利用されないまたはインスタンス化されない場合があるものの、スレーブに対して、対応するスレーブバケット集合１７２（例えば、１７２Ａ、１７２Ｂ、１７２Ｃ、１７２Ｄ、１７２Ｅまたは１７２Ｆ）は、少なくともいくつかの実施形態において維持されてもよい。マスターバケット集合１５２は、例えば、マスターが通常の動作条件下で、持続すると予想される平均値に準備されたＩ／Ｏ動作の速度、短期間の作業負荷バーストの間、持続され得るＩ／Ｏ動作の速度など、及び／またはマスターのデータが記憶される共用記憶デバイス１０２で利用可能なＩ／Ｏ容量などの、マスターそれ自身における作業負荷／容量条件及び／または制約を表している１つ以上のトークンバケット１５０（例えば、１５０Ａ、１５０Ｄ、１５０Ｅ）を含んでもよい。所定のマスターにおけるスレーブスナップショットバケット集合１５５は、そのマスターの１つ以上のスレーブにおける作業負荷条件に関するマスターにおいて利用可能な情報を表す、１つ以上のトークンバケット１５７（例えば、１５７Ａ、１５７Ｋ、及び１５７Ｐ）を含んでもよい。スレーブバケット集合１７２が使用されるいくつかの実施形態において、各々のこのようなスレーブバケット集合は、スレーブにおけるローカル作業負荷／容量条件及び／または制約を表している、対応するバケット１７１（例えば、１７１Ａ、１７１Ｄ、１７１Ｅ、１７１Ｆ、１７１Ｇ、または１７１Ｈ）を含んでもよい。
【００２２】
いくつかの実施形態において、マスターのスレーブスナップショットバケット集合１５５のコンテンツは、そのマスターのスレーブから取得される情報に基づいて、マスターによって更新されてもよい。図１に示されるシナリオにおいて、例えば、マスターＯ１−Ｐ１−Ｍに対応する論理区画Ｏ１−Ｐ１は、Ｏ１−Ｐ１に対応する２つのスレーブの各々で、すなわち、スレーブＯ１−Ｐ１−Ｓ１のバケット１７１Ｃ及びスレーブＯ１−Ｐ１−Ｓ２のバケット１７１Ｄで、バケットのスナップショットまたは母集団時点表現を取得してもよい。例えば、スレーブＯ１−Ｐ１−Ｓ１及びＯ１−Ｐ１−Ｓ２からマスターＯ１−Ｐ１−Ｍに送られた少なくともいくつかの書き込み確認応答メッセージにおいて、またはスレーブからマスターに送られた少なくともいくつかの心拍メッセージにおいて、または他の通信において、スナップショットは送信されてもよい。
【００２３】
図示される実施形態において、承認制御器１８０は、クライアント１９０であって、そのクライアント１９０のデータがデータオブジェクト１０１に記憶される、そのクライアント１９０からの着信クライアント作業要求１７８（例えば、読取り要求または書き込み要求）を承諾するまたは拒否することに関与してもよい。承認制御器は図１で単一の別個のエンティティとして示されるものの、種々の実施形態において、承認制御機能性の少なくとも一部は、ストレージノード１１０及び／またはシステム１００の他のデバイスに実装されてもよいことに留意されたい。前に述べたように、いくつかの実施形態において、承認制御の決定は、（例えば、Ｏ１−Ｐ１に対する承認制御の決定は、Ｏ１−Ｐ２に対する承認制御の決定から独立してなされてもよいように、）論理区画レベルでなされてもよい。書き込み要求に対する承認制御の決定は、図示される実施形態において、論理区画のマスター複製でなされてもよく、例えば、区画Ｏ１−Ｐ１に対する書き込み承認制御の決定は、ストレージノード１１０Ａなどの上に存在する承認制御器１８０のコンポーネントによってなされてもよい。
【００２４】
図示される実施形態における承認制御器１８０は、論理区画Ｏ１−Ｐ１に向けられる書き込み要求のために、Ｏ１−Ｐ１−Ｍに関連付けられたマスターバケット集合１５２Ａ及びスレーブスナップショットバケット集合１５５Ａの１つ以上のバケットの母集団を検査してもよい。いくつかの実装において、Ｏ１−Ｐ１が動作の通常モード（例えば、要求されたＩ／Ｏ速度がＯ１−Ｐ１に対して準備された容量限界より低い）にあるか、動作のバーストモードにあるかに依存して、書き込み要求を承諾する前に、バケットの異なる集合は検査されてもよい。十分なトークンがこれらのバケットのうちの少なくとも１つからの消費のために取得され得るときに、この前後関係で所定のバケットにとって十分な数がバケットに関連付けられたトークン消費方針によって定義されてもよい場合、書き込み要求は承諾されてもよく、さもなければ、書き込み要求は拒否されることもあり、クライアントは拒否１７４について通知され得る。承諾された書き込み要求１７０は、マスターＯ１−Ｐ１−Ｍで対応する書き込み動作（例えば、作成、更新、または削除動作）の開始をもたらし得、また、図示される実施例シナリオにおいて、マスターからスレーブＯ１−Ｐ１−Ｓ１及びＯ１−Ｐ１−Ｓ２に伝播され得る。いくつかの実施形態において、要求しているクライアント１９０に対する応答は、オブジェクト１０１Ａの冗長性／耐久性要求に依存して、例えば、以下の図４の前後関係において説明されるクォーラム要求を使用して、書き込みが十分な数の複製で成功裏に完了された後に提供されてもよい。例えば、１つの実施形態において、書き込みは、書き込みが成功したことがクライアントに知らされる前に、Ｏ１−Ｐ１のすべての３つの複製を完了する必要があるかもしれない一方、別の実施形態において、またはオブジェクト１０１Ａに対する異なる構成の設定によって、書き込みは、クライアントが通知される前に、Ｏ１−Ｐ１−Ｍ及びスレーブ（Ｏ１−Ｐ１−Ｓ１またはＯ１−Ｐ１−Ｓ２）のうちの１つで完了されるだけでもよい。少なくともいくつかの実施形態において、クォーラム要求にかかわらず、書き込みは、マスターからすべてのスレーブに、最終的に、伝播され得る。
【００２５】
トークンベースの承認制御の概要
図２は、少なくともいくつかの実施形態によるトークンベースの承認制御機構のハイレベル概観図を提供する。トークンの単一のバケット２０２を使用する機構は、提示の簡潔さのために図示される。その機構によると、特定のデータオブジェクト、オブジェクト区画、または区画複製に関連付けられた承認制御目的に対してセットアップされたバケット２０２（例えば、少なくともいくつかの実施形態におけるソフトウェアプログラム内のデータ構造として実装されてもよい論理的コンテナ）には、バケット初期化の間、矢印２０４Ａを介して示されるように、トークン２０８の最初の集合が取り込まれ得る。最初の母集団は、例えば、作業負荷の予想、サービスレベルの一致、対応するデータオブジェクトを所有するまたは管理するクライアントによって特定されるプロビジョニング予算、または種々の実施形態におけるこのような要因のいくつかの組み合わせに基づいて、決定され得る。いくつかのタイプのバケットに対して、最初の母集団は、いくつかの実施形態において、ゼロに設定されてもよい。いくつかの実装において、少なくとも１つのバケットの最初の母集団は、バケットが構成される最大母集団に対して設定されてもよい。
【００２６】
少なくとも通常の動作条件で、新しい作業要求１７８（読取り要求または書き込み要求など）が承認制御器１８０で受信されるとき、図示される実施形態において、承認制御器は、なんらかの数、Ｎ個のトークン（ここで、Ｎは、実装または構成パラメータに依存して、１以上であってよい）がバケット２０２に存在するかどうかを決定するように試み得る。その数のトークンがバケットで利用可能である場合、作業要求１７８は、実行のために、承諾されるまたは承認されてもよく、トークンは、バケットから消費されるまたは取り除かれてもよい（矢印２１０）。さもなければ、Ｎ個のトークンもまた存在しない場合、作業要求１７８は拒否されることもある。図示される実施例において、作業要求１７８Ａは承諾され、作業要求１７８Ｂは拒否され、作業要求１７８Ｃ、１７８Ｄ、及び１７８Ｅは、まだ、承認制御器１８０によってまだ考慮されていない。
【００２７】
矢印が付された２０４Ｂによって示されるように、例えば、バケットに関連付けられた補充速度などの構成パラメータに基づいて、図３を参照して以下に記載されるように、バケット２０２はまた、補充されてもよい、または徐々に再度取り込まれてもよい。いくつかの実装において、トークン補充動作は消費動作に伴って、または消費動作に近接した閉鎖時間で行われてもよく、例えば、単一のソフトウェアルーチン内で、Ｎ個のトークンは要求を承認するために消費されてもよく、Ｍ個のトークンは、補充速度及びバケットが最後に補充されてからの時間に基づいて追加されてもよい。バケットはまた、これも以下に記載されるように、いくつかのシナリオにおける他のバケット内の使用されないトークンカウントに基づいて取り込まれてもよい。限界は、バケットがいくつかの実施形態において保持し得るトークンの最大数に設定されてもよい、及び／または、例えば、構成パラメータを使用してトークンの最小数に設定されてもよい。特に、所定のオブジェクトまたはリソースに対する承認を制御するために、複数のバケットが共に使用されるとき、構成パラメータ設定の種々の組み合わせを使用して、非常に洗練された承認制御スキームが異なる実施形態に実装され得る。
【００２８】
１つの単純な実施例シナリオにおいて、毎秒１００個の作業要求の定常負荷を支持するために、図２のバケット２０２は、１００個のトークンの最初の母集団、１００個のトークンの最大許容母集団、及びゼロ個のトークンの最小値で構成されてもよく、Ｎは１に設定されてもよく、補充速度は毎秒１００個のトークンに設定されてもよく、（最大母集団限界は超えられていないと仮定すると）１０ミリ秒に一回、１つのトークンは補充目的のために追加されてもよい。作業要求１７８が到着すると、１つのトークンは作業要求ごとに消費され得る。毎秒１００個の作業要求で、一秒間に均一に分散される定常状態作業負荷が適用される場合、補充速度及び作業負荷の到着速度は互いに平衡を保ってもよい。いくつかの実施形態において、上記に掲載されたバケットパラメータを仮定して、このような定常状態作業負荷は無期限に持続され得る。
【００２９】
上記の実施例を拡大解釈して、到着速度及び／または補充速度が均一でない場合、バケット２０２がなんらかの（典型的に小さい）時間間隔の間、空白のままであるシナリオが生じてもよい（例えば、作業要求のいくつかの集合が、高速で連続的に、補充機構が置換できるより多くのトークンを消費する場合）。このような場合、到着作業要求は拒否されてもよい（または遅延後に再試行されてもよい）。作業負荷の不均一性に取り組むために、種々の技術は異なる実施形態において利用されてもよく、例えば、バーストハンドリング方針は、１つの実施形態において、「バーストハンドリング」バケットと称されてもよい別のバケットにおいて、未使用のトークンをバンクすることを許してもよく、また要求速度における短期間のバーストのためのバーストハンドリングバケットからトークンを消費してもよい。
【００３０】
図３は、少なくともいくつかの実施形態による、種々のタイプの承認制御方針を実装するために使用され得るバケット２０２などのトークンバケットの構成特性３０２の実施例を示す。トークン消費方針３１０は、どのようにしてトークンが承認制御のために消費されるべきかを示してもよい。いくつかの実施形態において、消費方針３１０は異なる事前承認方針及び事後承認方針を含んでもよく、いくつかの実施形態において、及び／または他のバケットの状態または論理区画の動作のモードに依存してもよい。例えば、１つの実施形態において、２つのバケットは、所定の論理区画、すなわち、準備された容量のバケットＰＣ及びバーストハンドリングバケットＢＨに対する承認制御のために使用されてもよい。本実施例で有効な事前承認方針によると、新しい要求を承認するために、ＰＣの母集団は、少なくとも１つのトークンが存在するかどうかを決定するためにチェックされ得、事後承認方針によると、要求が承認されると、ＰＣの母集団は１つだけ減少するかもしれない。ＰＣがトークンを有する場合、論理区画は通常（非バースト）モードにあるとみなされてもよく、ＢＨの母集団は要求を承認する前にチェックされる必要がない場合もある。しかしながら、有効な事後承認方針に従って、ＢＨからの１つのトークンは、要求が承諾される場合、それにもかかわらず消費されてもよい。それに対して、実施例を続けると、ＰＣがトークンを全く有していない場合、論理区画はバーストモードにあるとみなされてもよく、ＢＨの母集団はＢＨが少なくとも１つのトークンを有するかどうかを決定するためにチェックされてもよい。バーストモードでは、ＢＨが利用可能なトークンを有する場合にのみ、要求は承認されてもよく、要求が承認される場合、トークンはＢＨから消費されてもよい。（いくつかの実装において、バーストモードでは、ＰＣのトークン母集団はまた、要求承認の際、デクリメントされてもよく、潜在的に、ＰＣの母集団を負数にする。）いくつかの実施形態において、異なる数のトークンは、その消費方針に基づいて、異なるタイプの動作に対して所定のバケットから消費されてもよい。いくつかの実施形態において、トークン消費方針はまた、対応するデータオブジェクトが作業要求に対してしばらくの間、標的にされない場合、トークンがバケットから削除されるべきかどうか（及びどのくらいの速度で）を示すアイドリング中の減衰パラメータを特定してもよい、または、しばらくの時間間隔の間、トークンが使用されない場合、トークンが１つのバケットから別のバケットに転送されるべきかどうかを示すアイドリング時転送パラメータを特定してもよい。
【００３１】
特性３０２は、図示される実施形態において、開始時または初期化時に何個のトークンがバケット内に設けられるべきかを示す、最初のトークン母集団パラメータ３０６を含み得る。トークン補充方針パラメータ３１４は、例えば、それに対してバケットに関連付けられたデータオブジェクトが構成された作業の速度を維持することを助けるために、どのくらいの速度で、及び／またはどんな状況下で、トークンがバケットに追加されるべきかを示してもよい。いくつかの実施形態において、バケットのパラメータのうちの１つ以上は徐々に変化してもよく、例えば、初期設定の補充速度はバケットに適用されてもよいが、一定の条件下で初期設定でない速度が使用されてもよい。最大母集団パラメータ３１８はバケットの最大容量を示す一方、最小母集団パラメータ３２２はバケットの母集団に対する下限を示してもよい。いくつかの実装において、バケットの母集団は、いくつかの状況下で、負数になるとみなされてもよい（例えば、最小母集団がゼロより小さくてもよい）。例えば、１つの実施形態において、承認制御器１８０は、簡単にするために、着信クライアント要求がそれぞれ、およそ１つの実際のＩ／Ｏ動作をもたらすだろうということを仮定してもよい。しかしながら、動作要求Ｒが承諾された後、いくつかの場合に、Ｒを承認した結果として必要とされる作業の実際の量は仮定された１つのＩ／Ｏよりかなり大きくてもよく、例えば、１つの読取りによって満たされると予想される読取り要求は、最終的に、１０００個の読取りを要求する表のスキャンになり得る。このようなシナリオにおいて、予期されない余分の作業の影響が確実に後続の承認制御の決定に反映されるようにするために、余分な作業に対応するトークンの数（例えば、１０００−１＝９９９トークン）は、バケットから差し引かれてもよく、これによって、少なくとも一時的に、トークンカウントを負数にしてもよい。トークンカウントは、例えば、バケットの補充速度及び着信要求速度に基づいて、最終的に、再び正数の領域に入ってもよい。トークン欠損方針パラメータ３２４は、その下で、トークン欠損（または負数母集団）が許可されるか、どのくらいの間、欠損がそのままであってもよいか、欠損から復旧するためにどんな行動が取られなければならなかなどの条件についての規則を特定してもよい。いくつかの実施形態において、異なるタイプの動作は異なる承認制御規則を有してもよく、そのためにバケットが使用されることになる動作のタイプは適用可能な動作のタイプのパラメータ３２６で特定されてもよい。異なる実施形態において、図３に示されるパラメータの実施例の部分集合のみが利用されてもよい一方、他の実施形態において、図３に示されるパラメータ以外の追加的なバケット構成パラメータが使用されてもよい。少なくともいくつかの実施形態において、バーストモード動作が支持されるべきかどうかなどの他の承認制御設定だけでなく、図３に示される種々の特性に対する値及び／または設定も（例えば、ウェブサービスコールを使用して）プログラムで設定または修正されてもよい。前に述べたように、いくつかの実施形態において、異なるバケットは、読取り及び書き込みのためにそれぞれ使用されてもよい。所定のバケットがただ１つの特定のタイプのＩ／Ｏ動作（例えば、読取りまたは書き込みであるが、その両方ではない）に対する承認制御のために使用されている実施形態において、以下の記載におけるそのバケットについて使用されるときの総称「Ｉ／Ｏ動作」は、その特定のタイプのＩ／Ｏ動作について言及するとみなされてもよい。
【００３２】
図４は、少なくともいくつかの実施形態による、オブジェクト区画の実施例及び関連クォーラムに基づくデータ修正方針を示す。データオブジェクト１０１Ａは、図示されるように、３つの論理区画Ｏ１−Ｐ１、Ｏ１−Ｐ２、及びＯ１−Ｐ３を含む。論理区画ごとに、（Ｎ＋１）個の物理的な複製４１０、すなわち、１つのマスター複製（区画Ｏ１−Ｐ１に対するＯ１−Ｐ１−Ｍ、区画Ｏ１−Ｐ２に対するＯ１−Ｐ２−Ｍ、及び区画Ｏ１−Ｐ３に対するＯ１−Ｐ３−Ｍなど）及びＮ個のスレーブ複製が記憶される。書き込み動作が承諾されるとき、対応するデータ修正は、図示される実施形態において、書き込み動作が成功であるとみなされる前に、マスター４１２及び２つのスレーブ４１６を含むクォーラム４３０に伝播される。このため、書き込み複製のためのクォーラムの大きさは、図示される実施例において３に設定される。最終的に、図示される実施形態において、書き込みはすべてのＮ個のスレーブ複製に伝播されてもよい。
【００３３】
少なくともいくつかの実装において、マスターだけでなく各々のトークンバケットも各スレーブで維持されてもよいが、クォーラムのバケット集合のみが書き込みに対する承認制御目的のために使用されてもよい。先述のように、スレーブのローカルバケット集合（例えば、Ｏ１−Ｐ１−Ｓ１及びＯ１−Ｐ１−Ｓ２のバケット集合）についての情報は、マスターに搬送されてもよく、マスターのスレーブスナップショットバケット集合は搬送される情報に基づいて更新されてもよく、マスターのローカルバケット集合は、スレーブスナップショットバケット集合とともに、承認制御のために使用されてもよい。他の実施形態において、すべてのスレーブ複製のバケット集合についての情報は、クォーラムに関与するこれらのスレーブのみでなく、マスターでの承認制御に対して考慮されてもよい。
【００３４】
バケット集合コンテンツ
図５は、少なくともいくつかの実施形態による、データオブジェクト１０１の論理区画１０３のマスター複製４１２で維持されてもよい、トークンバケットのタイプの実施例を示す。図示されるように、マスターバケット集合１５２における３つのバケット、及びスレーブスナップショットバケット集合１５５における単一のバケットを有する、バケットの２つの集合は図示される実施形態で使用されてもよい。いくつかの実装において、バケット集合１５２及び１５５は承認制御器１８０のインメモリデータ構造として実装されてもよく、必要に応じて、永続記憶装置に書き込まれてもよい。少なくともいくつかの実施形態において、図５に示され（また図７に示される）バケットは、書き込み承認制御のみのために使用されてもよく、また異なるバケットは読取りのために使用されてもよい。所定のバケットがただ１つの特定のタイプのＩ／Ｏ動作（例えば、読取りまたは書き込みであるが、その両方ではない）に対する承認制御のために使用されている実施形態において、以下の記載におけるそのバケットについて使用されるときの総称「Ｉ／Ｏ動作」は、その特定のタイプのＩ／Ｏ動作のみについて言及するとみなされてもよい。
【００３５】
図示される実施形態において、データオブジェクト１０１を所有するクライアント１９０は、準備されたスループットと称されてもよい、区画１０３に対する特定の平均スループットレベルを特定してもよい（及び／または契約により支払う義務がある）。このような準備されたスループットは、例えば、オブジェクトが作成される時点で、少なくともいくつかの実施形態においてクライアントによって推測されるような標的とされるまたは予想されるスループット速度に基づいてクライアントによって特定されてもよい。１つの実施形態において、クライアント（及び／またはストレージサービス）は、オブジェクトの作成後、準備されたスループットレベルを変化させることを許されてもよい。準備された容量バケット１５０Ａは、少なくとも比較的均一な作業負荷条件の下で、データオブジェクトが記憶されるサービスがＩ／Ｏ速度を準備されたスループットまで確実に支持し得るようにするために用いられてもよい。準備された容量バケットの種々の構成パラメータは、クライアントによって特定される標的とされるスループットに対して少なくとも部分的に決定されてもよい。例えば、標的とされるスループットが毎秒１００個のＩ／Ｏの場合、準備された容量バケット１５０Ａは１００個のトークンが最初に取り込まれてもよく、その最大母集団は１００に設定されてもよく、その初期設定の補充速度は１００個のトークン／秒に設定されてもよい。クライアント要求が平均１００個の要求／秒で到着し、時間的にかなり均一に分散される限り、標的とされるスループットは概して、上記の実施例において持続されてもよい。１５０Ａなどの準備された容量バケットが、少なくともいくつかの実施形態において実装されない場合があることに留意されたい。
【００３６】
（上記の実施例を続けると）数秒間でＩ／Ｏ要求が毎秒２００個の要求として到着するＩ／Ｏ要求の突然のバーストを取り扱うために、バーストハンドリングバケット１５０Ｂは、いくつかの実施形態に実装されてもよい。バーストハンドリングバケットは、（矢印５５２で示されるように）準備された容量バケット１５０Ａからの未使用のトークンが記憶される「バンク」とみなされてもよく、そこから、これらのバンクされたトークンが、必要に応じて、要求バーストを取り扱うために消費されてもよい。例えば、クライアントが１００個の要求／秒という準備されたスループットに、区画を準備したが、５秒間で毎秒５０個の要求を発行するのみの場合、準備された容量バケット１５０Ａからの毎秒５０個の未使用のトークンが、これらの５秒ごとに、バーストハンドリングバケット１５０Ｂバンクされてもよい。こうして、２５０個のトークンは、５秒後にバーストハンドリングバケットにバンクされてもよく、バーストハンドリングバケットの消費方針に基づいて、図示される実施形態で準備された１００／秒の速度より大きい速度で要求が受信される場合及び受信されるとき、これらのバンクされたトークンは消費されてもよい。いくつかの実施形態において、バケット１５０Ａから未使用のトークンをバンクすることの代わりにまたはそれに加えて、バーストハンドリングバケット１５０Ｂの母集団は、ストレージノードでの利用可能な過剰なＩ／Ｏ容量やバーストに対してクライアントが進んで支払う価格などの他の要因に基づいて決定されてもよい。少なくともいくつかの実施形態において、バーストハンドリングバケットが実装される必要はないことに留意されたい。
【００３７】
マスター共用デバイスバケット１５０Ｃは、図５に示される実施形態においてマスター４１２のデータが存在する共用のデバイス１０２（複数の区画の複製が存在する共用のデバイス１０２の実施例が図１に示される）の利用可能なスループット容量を示すトークンを記憶してもよい。そのため、例えば、１つの実施形態において、マスターのデータが記憶される共用のソリッドステートドライブ１０２Ａが、毎秒１０００個のＩ／Ｏ要求まで取り扱いできる場合、共用デバイスバケット１５０Ｃは１０００個のトークンが取り込まれてもよく、その最大母集団集合を１０００個のトークンで有してもよく、Ｉ／Ｏ要求ごとに１個の消費速度及び１０００個のトークン／秒の初期設定のトークン補充速度を有してもよい。同じ共用デバイスバケットは、少なくともいくつかの実施形態において、所定の共用記憶デバイス１０２に存在するいくつかのまたはすべての複製によって承認制御のために使用されてもよく、例えば、図１に示される構成の実施例において、記憶デバイス１０２Ａに設けられたＯ１−Ｐ１−Ｍ１、Ｏ２−Ｐ１−Ｓ１、及びＯ３−Ｐ１−Ｓ２は、共通の共用デバイスバケット１５０Ｃ（または、同じ共用デバイスバケット１５０Ｃの各々の論理的相当物）を使用してもよい。共用記憶デバイス１０２に設けられた異なる複製に対する作業負荷が異なってもよいため、区画のいずれかの１つに対する承認制御の決定は、デバイス上の他の複製の作業負荷を考慮する必要がある場合があり（少なくともバーストモードの間）、図示される実施形態においてそれを行うために共用デバイス１５０Ｃが使用されてもよい。他の実施形態において、またはいくつかの条件下で（例えば、記憶デバイスが１つの複製を最大限に記憶するように構成されている場合）、共用デバイスバケット１５０はマスターに実装されなくてもよい。マスターバケット集合に含まれるバケットの数（及び特定のタイプ）は、異なる実施形態で異なってもよい。いくつかの実施形態において、図５に示されるタイプのバケットとは異なる他のタイプのバケットが利用されてもよい。
【００３８】
図示される実施形態において、スレーブスナップショットバケット集合１５５は、コモンプロキシスレーブ共用デバイスバケット１５７（これは、本願において、「コモンプロキシバケット」とも称され得る）を含んでもよい。マスター複製４１２は、例えば、以下に記載されるように各スレーブで維持される共用デバイスバケットの母集団のスナップショット（時点表現）の形で、その対応するスレーブで作業負荷条件の指標を受信するように構成されてもよく、スレーブのために使用されている記憶デバイス１０２で利用可能なスループット容量のインジケータとして役立ち得る。１つ以上のスレーブの各々からスループット容量の最新の利用可能な指標を使用して、スレーブ間の利用可能なスループット容量の最小値の推測が、図示される実施形態において決定されてもよい。（少なくともいくつかの実装において、利用可能な容量指標が異なるスレーブに対する多少異なる時点に対応するので、またスナップショットがマスターに達して処理されるためにいくらかの時間を費やす場合があるので、最小値の推測は、特に、利用可能なスループット容量が任意の所定の記憶デバイス１０２で急速に変化し得る高スループット環境において完全に正確でないこともあることに留意されたい。）。コモンプロキシバケット１５７の母集団は、推測された最小の利用可能な容量を１つ以上のスレーブで反映させるように設定されてもよい。例えば、マスター４１２が２つのスレーブ４１６Ａ及び４１６Ｂを有し、書き込みが成功であるとみなされる前に、両方スレーブに対して複製される必要があるシナリオの実施例を考慮されたい。各複製は異なる記憶デバイス１０２の上に設けられ、また各記憶デバイスは他の区画の複数の複製のデータを有してもよく、その各々は各々の記憶デバイス上の全体のＩ／Ｏ作業負荷に貢献し得る。バーストモードの間、マスター４１２で書き込み要求を承諾する前に、マスター４１２に対する承認制御器１８０は、（マスターバケット集合１５２が使用され得るマスターの利用可能なＩ／Ｏ容量に加えて）スレーブ４１６Ａ及び４１６Ｂの両方のために使用されている共用記憶デバイス１０２が書き込みを複製するために十分なＩ／Ｏ容量を有するかどうかを進んで決定し得る。したがって、コモンプロキシバケット１５７におけるトークン母集団は、マスターにおける最新の利用可能なスレーブ情報に基づいて、２つのスレーブ４１６Ａ及び４１６Ｂの共用のデバイスでより小さい（すなわち最小の）利用可能な容量を表すために設定されてもよい。マスターにおけるスレーブ４１６Ａからの最も新しい通信が、スレーブ４１６Ａの共用記憶デバイスが５０個のトークンに相当する現在の利用可能な容量を有すると示し、スレーブ４１６Ｂからの最も新しい通信が、スレーブ４１６Ｂの共用記憶デバイスが３０個のトークンに相当する現在利用可能な容量有すると示した場合、バケット１５７の母集団は、本実施例において３０個のトークンに設定されるであろう。
【００３９】
新しい書き込み要求が受信されると、そのバケット集合が図５に示した実施形態で示されるマスター４１２のための承認制御器は、まず、バケット１５０Ａが十分なトークンを有するかどうかを決定するように構成され得る。１つの実施形態において、単一のトークンは、書き込み要求を承認するように要求されることもある。このようなシナリオでバケット１５０Ａが少なくとも１つのトークンを有する場合、論理区画は（準備された限界より下の）通常または非バーストモードにあるとみなされてもよく、ストレージサービスは要求を承諾する義務があってもよい。書き込み要求はそれにより承諾されてもよく、１つのトークンはバケット１５０Ａから消費されてもよい。さらに、少なくともいくつかの実施形態において、１つのトークンは、バケット１５０Ｂ、１５０Ｃ、及び１５７の各々から消費されてもよい。大部分の状況下で、承認制御パラメータは、大部分の状況下で、バケット１５０Ａがトークンを有している場合、バケット１５０Ｂ、１５０Ｃ、及び１５７はまた、トークンを含有することが大いにありうるように設定されてもよい。しかしながら、これらの他のバケットのうちのいずれかが通常モード下でトークンを含有しない場合、それらの母集団は、いずれの場合にもデクリメントされてもよく、負数トークン母集団をもたらす。
【００４０】
書き込み要求が受信されるときにバケット１５０Ａがトークンを有さない（または負数トークン母集団を有する）場合、論理区画はバーストモードにあるとみなされてもよい。バケット１５０Ｂ、１５０Ｃ、及び１５７は各々、それらが少なくとも１つのトークンを有するかどうかを決定するためにチェックされてもよく、これらのバケットのすべてが少なくとも１つのトークンをそれぞれ有する場合、書き込みが承諾され得る。それらがそれぞれ少なくとも１つのトークンを含有する場合、書き込みは承諾されてもよく、各バケットの１５０Ｂ、１５０Ｃ、１５７、及び１５０Ａトークンカウントはデクリメントされてもよい。バケット１５０Ｂ、１５Ｃ、及び１５７のいずれかが空白の場合、書き込み要求は拒否され得る（または十分なトークンが利用可能になるまで、承諾が遅延されてもよい）。このような承認制御方針は、区画の複製のために使用されるすべてのデバイス間で最もリソースに拘束された記憶デバイスを考慮する点において、「保守的」または「安全」とみなされてもよい。例えば、上記の実施例において、書き込み要求が受信されると、スレーブ４１６Ａの記憶デバイスが５０個のトークンに値する容量を有し、スレーブ４１６Ｂの記憶デバイスが３０個のトークンに値する容量を有し、バケット１５０Ｃが４０個のトークンを有するシナリオを考慮されたい。バケット１５７の母集団が３０（５０及び３０の最小値）に設定されるであろうため、また１つのトークンが４つすべてのバケットから要求されるため、４１６Ｂのデバイスの利用可能な容量は、たとえ他の複製がより高い利用可能な容量を有しているとしても、バーストモードの間、承認制御の決定をなす際に考慮されるべきであろう。なんらかの（典型的に速度）状況下で、１つの実施形態において、例えば、マスターとの最後の通信以来、スレーブの共用記憶デバイスにおける作業負荷が非常に早く増加したため、マスターにおける最近の容量情報をスレーブから取得しようとする、また最近の情報に基づいて承認制御の決定をなそうとする最大限の努力にもかかわらず、スレーブが依然として承認制御機構によって承諾される書き込み動作の複製を完成させることができない場合があることに留意されたい。このような状況において、スレーブでの書き込み複製が失敗することもあり、要求しているクライアントは、いくつかの実装において書き込み要求が成功しなかったと知らされることもある。書き込みが失敗したことを要求者に知らせる代わりの他の実施形態において、書き込み複製は、例えば、片方が利用可能な場合、同じスレーブまたは異なるスレーブを使用して、遅延される及び／または何回か再試行されてもよい。いくつかの実施形態において、書き込み要求が受信されると、バケット１５０Ａ、１５０Ｂ、１５０Ｃ、及び１５７の母集団はチェックされて（例えば、バケット１５０Ａがトークンを有するかどうかにかかわらず）、書き込みを承認する前に、各バケットが少なくとも１つのトークンを確実に有するようにし得る。
【００４１】
他の実施形態において、この基本的なアプローチのバリエーションが利用されてもよく、例えば、いくつかの実施形態において、所定のバケットは、必要とあれば、異なるバケットからトークンを借りて、一定の特別な状況下で書き込みを許すことができる。概して、マスターバケット集合１５２のバケットは、マスターにおいて利用可能なＩ／Ｏ容量の指標（及び／または準備された容量限界）として使用されてもいい一方、スレーブスナップショットバケット集合１５５のバケットは、スレーブにおけるスループット容量条件についての、マスターにおける最新の利用可能な情報を表してもよい。異なる実施形態において、マスターバケット集合におけるバケットの異なる組み合わせが実装されてもよく、例えば、１つの実施形態において、バケット１５０Ｃのみが使用されてもよく（準備されたスループットまたはバースト専用のバケットはない）、別の実施形態において、バケット１５０Ａ及び１５０Ｃのみが使用されてもよい（バーストの取り扱い専用のバケットはない）などである。
【００４２】
図６は、少なくともいくつかの実施形態による、論理区画１０３のデータオブジェクト１０１のスレーブ複製４１６で維持され得るトークンバケットのタイプの実施例を示す。図示されるように、図示される実施形態において、スレーブバケット集合１７２のコンテンツは図５のマスターバケット集合１５２のコンテンツに類似しており、主要な違いは、スレーブバケット集合のバケットが、マスターではなくスレーブで条件を表し、マスターではなくスレーブで承認制御のために使用されることである。図６に示されるように、少なくともいくつかの実施形態において、所定の論理区画のすべての複製に対する書き込み承認制御の決定がマスター複製でなされ得るため、図示されたバケット１７１は（たとえそれらが、現在の書き込み活動をスレーブで、及び／または準備された書き込みスループット限界をスレーブで反映するようにセットアップされているとしても）、スレーブにおける書き込み承認制御の決定のために使用されないこともある。図６に示されるバケットの書き込み承認制御の決定に対する貢献は、以下に記載されるように、マスターに対して、例えば、バケット１７１Ｃの母集団スナップショットを送ることを介して、間接的であってもよい。
【００４３】
準備された容量バケット１７１Ａは、区画を所有するクライアントによって合意された（スレーブに）準備されたスループットレベルを表すトークンを保持し得、バーストハンドリングバケット１７１Ｂは、Ｉ／Ｏバーストをスレーブ４１６で取り扱うために使用され得、スレーブ共用デバイスバケット１７１Ｃは、スレーブ４１６のデータが記憶される共用のデバイスで利用可能な容量を示すトークンを記憶し得る。少なくともいくつかの実施形態において、バーストハンドリングバケット１７１Ｂは、矢印６５２で示されるように、図５に示される、バケット１５０Ａからバケット１５０Ｂへの未使用のトークンの転送に似ている方法で、未使用の準備されたトークンをバケット１７１Ａから論理的に転送することにより少なくとも部分的に取り込まれ得る。１つの実施形態において、類似したまたは同一のデバイス１０２及び／またはストレージノード１１０は、異なるデータオブジェクトの種々の区画のために使用され得、例えば、種々の複製のために使用される記憶デバイスは類似した性能仕様を有してもよく、また、ストレージノード１１０は各々が同一の計算及び全体の記憶仕様を有し得る。結果として、図６に示されるスレーブ側バケット１７１Ａ、１７１Ｂ、及び１７１Ｃに関するパラメータ（例えば、それらの最初の容量、補充速度など）は、いくつかの実施形態において、少なくとも初期設定により、対応するマスターバケット１５０Ａ、１５０Ｂまたは１５０Ｃに関するパラメータと同じ値に設定されてもよい。他の実施形態において、異なるバケットパラメータ設定はマスターのためではなく、スレーブのために使用され得る。概して、読取り要求に対する承認制御に関して、所定のスレーブにおけるバケット１７１は、バケット１５０がマスターにおける読取り承認制御のために使用される方法と類似した方法で使用され得る。所定の読取り要求は、いくつかの実施形態において、単一の複製で、例えば、スレーブかマスターかのどちらかで取り扱われてもよく、このため、他の複製で利用可能な容量についての情報は、読取り承認制御の決定に必要とされないこともある。読取りは、クライアントが潜在的に多少古いスレーブ複製から満たされた読取りを進んで有する実施形態において、例えば、「最もビジーでない」複製（スレーブかマスターかのどちらか）に向けられてもよい。少なくともいくつかの実施形態において、論理区画１０３に向けられる書き込み要求に対する承認制御の決定は、マスターで利用可能な情報（マスターで利用可能なスレーブについての情報を含む）に基づいて、すべての複製のためのマスターで行われてもよい。承認制御の決定が書き込みのためのマスターで行われるときでさえも、トークンは、このような実施形態において書き込みがスレーブで複製されるときに、適用可能な消費方針によりスレーブで消費され得ることに留意されたい。
【００４４】
先述のように、スレーブ複製４１６が存在する共用のデバイス１０２における利用可能なＩ／Ｏ容量についての情報は、マスターに搬送されて、例えば、スレーブ更新方針に従って、マスターにおける保守的な書き込み承認制御を支援し得る。図６に図示される実施形態において、スレーブ共用デバイスバケット１７１Ｃの母集団スナップショット６５０を含有するメッセージは、例えば、図８ａまたは８ｂに示される技術のうちの１つを使用してマスター複製４１２に送られてもよい。いくつかの実装において、バケットはスレーブ複製４１６のすべてで維持される必要はない、例えば、スレーブによって使用される共用のデバイスにおける利用可能な容量についての情報は、スレーブに固有のバケット１７１を必ずしも実装することなく、マスター４１２に定期的に供給されてもよいことに留意されたい。
【００４５】
図５に示す実施形態において、コモンプロキシバケット１５７は、マスターにおけるスレーブデバイス情報を維持するために使用された。すべてのスレーブを表すコモンプロキシバケットを使用することと、コモンプロキシバケットの母集団を決定するために、マスターにおける利用可能なスレーブデバイス容量の最小値をコンピューティングすることの代わりに、いくつかの実施形態において、他のアプローチが使用されてもよい。図７は、少なくともいくつかの実施形態による、データオブジェクト区画のマスター複製で維持され得るタイプのトークンバケットの別の実施例を示す。総数ｎ個のスレーブは、図７の実施形態において、マスターごとに実装される。図７のバケットのマスター側アレンジメントは、図５に示されるアレンジメントと同一である。しかしながら、図７に示される実施形態におけるスレーブスナップショットバケット集合は、図５の単一のコモンプロキシバケットの代わりに、スレーブごとに１つのバケットを含む。スレーブ−スナップショット共用デバイスバケット１５７Ａは、スレーブ＃１の共用記憶デバイスにおける利用可能な容量についての最新の利用可能な情報を示すトークンを記憶し、バケット１５７Ｂは、スレーブ＃２の共用記憶デバイスにおける利用可能な容量についての最新の利用可能な情報を示すトークンを記憶する、などである。スレーブ−スナップショット共用デバイスバケットは、本願において、単に「スレーブスナップショットバケット」または「スナップショットバケット」と称され得る。書き込み要求が受信されると、バケット１５０Ａがまずチェックされてもよい。図５に示す実施形態の場合のように、バケット１５０Ａ内に十分なトークンがある場合、要求速度が準備された限界を下回るため、書き込みは承認され得る。通常モードの間でさえ、書き込みが承認される場合、トークンは図７に示されるバケットの各々から消費されてもよい。
【００４６】
準備された容量バケット１５０Ａ内に十分なトークンがない場合、論理区画はバーストモードにあるとみなされてもよい。バーストモードの間、承認制御器１８０は、トークンがマスターバケット集合のバケット１５０Ｂ及び１５０Ｃの各々及びスレーブスナップショットバケット集合１５５のＱ個のバケットの各々で利用可能な場合にのみ、書き込みを進行させるように構成されてもよい。ただし、成功であるとみなされる前に書き込みが完成されなければならない複製の数は（Ｑ＋１）（例えば、Ｑスレーブ及び１つのマスター複製）である。このように、承認制御器１８０は、バーストモードでの書き込み要求を承認する前に、そのバケット母集団が（スレーブからの最新の利用可能な通信が許す限り密に）スレーブの共用ドライブバケット１７１Ｃのバケット母集団を追跡するスレーブスナップショットバケット集合を使用して、少なくともクォーラム数の複製が、確実に成功裏に書き込まれ得るようにしてもよい。いくつかの実施形態において、トークンは、書き込みに関するクォーラムの大きさにかかわらず、スレーブスナップショットバケット集合においてＮ個のバケットの各々から消費されてもよい。トークンがスレーブ共用デバイスバケットのクォーラム（各々ではなく）のみから消費される実施形態において、書き込みは、そのトークンが消費される、対応するスレーブ複製に、最初に（すなわち、書き込みが他のスレーブに複製される前に）複製されてもよい。１つの実施形態において、バケット１５０Ａがトークンを十分に有するかどうかにかかわらず、図７のマスターバケット集合１５２のすべてのバケットは、それらが、書き込みを進行させるために十分なトークンを確実に有するようにチェックされてもよく、さらに、スレーブスナップショットバケット集合１５５の少なくともＱ個のバケットは、書き込みが進行を許される前に、それらが十分なトークンを確実に有するようにチェックされてもよい。
【００４７】
少なくともいくつかの実施形態において、図５〜図７に示されるタイプの複製に基づくトークンバケット及び／または共用デバイストークンバケットに加えてまたはそれらの代わりに、１つ以上のノードレベルトークンバケットは書き込み承認制御に対して利用され得る。例えば、マスター複製のデータの少なくとも一部が記憶されるストレージノード１１０に対応して、ノード能力バケットは、１つの実施形態に実装されてもよい。ただし、ノード能力バケットのトークン母集団は、全体から見て、ストレージノード１１０の性能能力のまたは限界のなんらかの集合の測定基準に少なくとも部分的に基づいている。そのような測定基準は、例えば、ストレージノードの利用可能な処理容量（例えば、ＣＰＵサイクル、利用限界、または速度の観点から）、メモリ限界、スレッドカウント限界、オペレーティングシステムの論理的リソース限界（例えば、オープンファイルまたはソケットの数）、ネットワークの限界、または書き込みまたは読取りのために使用され得る任意の他のタイプの能力に対する限界を示す。このような実施形態において、書き込みに対する少なくともいくつかの承認制御の決定は、ノード能力バケットにおいて利用可能なトークンの数に基づいてもよい。所定のノード能力バケットは、いくつかの実施形態において、そのデータが所定のストレージノード１１０に記憶される、複数の複製の各々（例えば、１を越えるマスター、または１を越えるスレーブ、またはマスター及びスレーブの組み合わせ）に対する承認制御の決定のために使用されてもよい。少なくとも１つの実施形態において、ノード能力バケットは、マスターバケット集合に（及び／またはスレーブバケット集合に）含まれてもよい。
【００４８】
承認制御方針の種々の特性は、いくつかの実施形態において、プログラマチックインターフェース（例えば、ウェブサービスアプリケーションプログラミングインターフェース（ＡＰＩ）または他のＡＰＩ、ウェブページ、コマンドラインツール、またはカスタムグラフィカルユーザインターフェース）を介して構成されてもよいことに留意されたい。このように、例えば、バーストモード書き込み動作がすべてのまたは所定のデータオブジェクトまたは区画に対して支持されるべきかどうか、いくつのトークンが種々のモードの動作でどのバケットの集合から消費されるか、または図３に示される種々の他のバケット特性に対する値／設定、に関する決定は、このような実施形態において、（データオブジェクトを所有するクライアントなどの）権限を与えられたエンティティからこのようなプログラマチックインターフェースを介して受信される構成要求に少なくとも部分的に基づいてもよい。
【００４９】
先述のように、実行に対して特定のＩ／Ｏ要求を承諾するために、トークンが（図５のバケット１５０Ａ、１５０Ｂ、１５０Ｃ、及び１５７などの、または図６または図７に示されるバケットなどの）複数のバケットから消費される少なくともいくつかの実施形態において、アトミックな動作（トランザクション、またはロックによって保護されるソフトウェアルーチンなど）は、関与するバケットの集まりからトークンを消費するために使用されてもよい。いくつかの実施形態において、アトミックな動作は、バケットのトークン母集団を検査することと、さらにバケットを補充することを含んでもよい、すなわち、全部で３つのタイプのバケット動作、すなわち、バケットの母集団の検査、母集団の減少、及び補充動作は、単一のアトミックな動作において行われてもよい。このようなアトミックな動作は、例えば、Ｉ／Ｏ要求を許す決定が受信された後、バケットのうちの１つは、適切な数のトークンがそれから消費される前に、（別のＩ／Ｏ要求によって）トークンを切らす矛盾した状態に達する可能性を減少させることを助けてもよい。いくつかの実施形態において、消費及び／または補充動作の少なくともいくつかは、このような組み合わされたアトミックな動作内で行われなくてもよい。
【００５０】
マスターにおけるスレーブ側情報の収集
図８ａ及び８ｂは、少なくともいくつかの実施形態による、マスター複製でスレーブスループット容量情報を取得するための相互作用の各集合を示す。図８ａに図示される実施形態において、マスター複製４１２は、承諾される書き込み要求８１０に対応して、耐久性方針及び／または書き込みが向けられるデータオブジェクトに関して有効な複製方針に従って、書き込み複製要求８１５をスレーブ複製４１６に送る。スレーブ複製４１６は書き込み複製要求を受信し、適切な書き込み動作を行い、書き込み確認応答８２０をマスターに送り戻す。スレーブの書き込み動作の結果に加えて、書き込み確認応答８２０はまた、スレーブの記憶デバイス１０２で利用可能なスループット容量（例えば、書き込み複製が試みられる時点で、スレーブのデータが存在する共用のデバイスのためのバケット１７１Ｃの母集団）を示すピギーバックされる母集団スナップショット６５０も含む。（本願において使用される、用語「ピギーバックされる」は、使用されている承認制御に対する特定のアプローチにかかわらず、または承認制御が全く使用されていなかった場合でさえ、スレーブの共用記憶デバイスについての情報が、とにかく生じた通信に追加されることを示し、このため、スナップショットの通信は、典型的に、特に、スナップショットを独立したメッセージとして送るコストに比べてオーバーヘッドがほとんど発生しない）。スナップショット６５０は、上述のように、スレーブスナップショットバケット集合の母集団を更新するためにマスターで使用されてもよい。少なくともいくつかの実施形態において、スナップショットは、スレーブが、成功裏に、書き込みを複製したかどうかにかかわらず、送られてもよく、例えば、書き込みが、いくつかの理由で、スレーブで複製され得なかった場合でさえも、共用のデバイスの容量の更新された見解がマスターに提供され得ることに留意されたい。１つの実装において、書き込み確認応答の部分集合のみが、ピギーバックされる母集団スナップショットを含んでもよく、例えば、スレーブ複製４１６は、母集団スナップショットを無作為に選択された書き込み確認応答に追加することを選択してもよいし、またはピギーバックされる情報を１００ミリ秒ごとに多くても１つの書き込み確認応答に追加することを選択してもよい。
【００５１】
いくつかの実施形態において、書き込み確認応答８２０を使用してスレーブのスループット利用可能性のマスターの見解をリフレッシュするかわりに、またはそれに加えて、心拍機構は、図８ｂに示されるように、使用されてもよい。図示される実施例において、スレーブは、スレーブの健康状態を示す（例えば、スレーブが作動してネットワークにアクセス可能なことを示している）定期的な心拍メッセージ８３０をマスターに（及び／または他のスレーブに）送るように構成されてもよい。母集団スナップショット６５０は、図示される実施形態において、心拍メッセージ８３０にピギーバックされ得る。いくつかの実施形態において、マスター４１２に送られたすべての心拍メッセージは、母集団スナップショット６５０を含んでもよい一方、他の実施形態において、心拍メッセージのいくつかの選択された部分集合は、スループット容量情報をピギーバックするために使用されてもよい。いくつかの実施形態において、他の機構は、スレーブのデバイスのスルーアウト容量をマスターに伝えるために使用されてもよく、例えば、１つの実施形態において、Ｘ分間に書き込み複製要求が全く受信されず、かつ心拍が使用されない場合、スレーブは、母集団スナップショットのみを含む専用メッセージをマスターに送信し得る（すなわち、ピギーバックすることは利用されなくてもよい）ことに留意されたい。いくつかの実施形態において、マスターは、スレーブのスループット容量についての情報を所有する、または更新するために、定期的に、または必要に応じて容量更新要求をスレーブに送ってもよい。
【００５２】
トークンに基づく書き込み承認制御のための方法
図９は、少なくともいくつかの実施形態による、ネットワークにアクセス可能なサービスにおける書き込みのためのトークンベースの承認制御機構を実装するように行われてもよい動作の態様を示すフロー図である。図９のエレメント９０２に示されるように、（リレーショナルまたは非リレーショナルデータベースの表、ファイルまたはファイルシステム、ボリューム、または任意の他のタイプのデータオブジェクトなどの）所定のデータオブジェクト１０１に関するストレージパラメータが決定されてもよい。データオブジェクトが分散されなければならない論理区画１０３の数、耐久性及び／または利用可能性の理由で維持されるべき論理区画ごとの物理的な複製の数、書き込み複製クォーラムの大きさ（例えば、いくつの複製において、書き込みは、対応する書き込み要求が成功したとみなされる前に、持続する必要があるか）などのいくつかの異なるパラメータに関する値が決定されてもよい。パラメータの値は、クライアントが提供した仕様（例えば、オブジェクト作成時間に）または嗜好、クライアントの代わりにデータオブジェクトが維持されなければならないクライアントと締結したサービスレベル合意、システムの初期設定、類似した作業負荷を有することが予想される他のデータオブジェクトのために取得された測定基準などの異なる実施形態における種々の要因の任意の組み合わせに基づいて選択されてもよい。図示される実施形態において、少なくとも１つのマスター複製４１２及び少なくとも１つのスレーブ複製４１６は、データオブジェクト１０１の各論理区画１０３に対応して維持され得る。
【００５３】
図９のエレメント９０６に示されるように、サービスは、所定の論理区画１０３のマスター複製４１２、マスターバケット集合１５２及びスレーブスナップショットバケット集合１５７に対応して、１つ以上のトークンバケット２０２を含む各集合を初期化して記憶してもよい。各バケットは、論理区画１０３に向けられる入力／出力（Ｉ／Ｏ）動作のスループットを制限するために使用可能なトークンの各々の補充可能な集まりを含んでもよく、各バケットは、どの状況下で（また、いくらかでもあるとすると、どのくらいの個数で）トークンが許可されたＩ／Ｏ動作に対するそのバケットから消費されるべきかを示している、各々のトークン消費方針を有してもよい。マスターバケット集合１５２は、マスターに対してローカルな少なくともいくつかの情報を含んでもよく、例えば、１つの実装において、マスターバケット集合の特定のバケット１５０Ｃの現在のトークンカウントは、マスターのデータが記憶される共用記憶デバイスで利用可能なスループット容量を反映してもよい。マスターバケット集合の他のバケットは、論理区画に関連付けられた準備されたスループットレベル（例えば、データオブジェクトの所有者が要求した及び／または支払ったＩ／Ｏ動作の速度）を達成するために、またはＩ／Ｏ作業負荷における短期間のバーストを取り扱うために、使用されてもよい。スレーブスナップショットバケット集合は、１つ以上のスレーブ４１６における利用可能なスループット容量を表すバケットを含んでもよく、例えば、１つのそのようなバケットは、スレーブのデータが記憶される共用記憶デバイスに関連付けられたバケットに存在するトークンの数のマスターの見解を示してもよい。いくつかの実施形態において、バケット異なる集合は、書き込みに対する承認制御のために使用されるのではなく、読取りに対する承認制御のために使用されてもよい。
【００５４】
マスターは、図示される実施形態における特定のスレーブバケット更新プロトコル（エレメント９１０）を使用して、スレーブにおいて利用可能なスループット容量についての情報を取得してもよい。例えば、スレーブで維持され、スレーブによって使用される共用記憶デバイスの利用可能なスループット容量を示す（図６のバケット１７１Ｃなどの）トークンバケットの母集団のスナップショットまたは時点の値は、１つの実施形態における書き込み確認応答メッセージ内のマスターに、及び／またはスレーブからマスターに送られた心拍メッセージ内に送られてもよい。マスターは、図示される実施形態（エレメント９１４）において、プロトコルを介して取得された情報を使用して、スレーブスナップショットバケット集合の１つ以上のバケットにおけるトークン母集団を更新してもよい。スレーブ側の利用可能な容量のスナップショットを、（例えば、書き込み複製要求を認めるために、またはスレーブが作動して起動していることを確認するために）他の理由ですでにマスターに送られたであろうメッセージ内に追加するまたはピギーバックすることによって、書き込み承認制御機構によって導入されたオーバーヘッドは、少なくともいくつかの実施形態において最小化されてもよい。
【００５５】
例えば、論理区画が、そのデータが共用記憶デバイスＤ１及びＤ２にそれぞれ記憶されるマスターＭ及び２つのスレーブ複製Ｓ１及びＳ２を有する実施形態を考慮されたい。デバイスに固有のトークンバケットＳＢ１及びＳＢ２は、Ｄ１及びＤ２それぞれの現在、利用可能なスループット容量を示す、各々のスレーブＳ１及びＳ２で維持されてもよい。コモンプロキシバケットＣＰＢは、Ｄ１及びＤ２間で最小のスループット容量について利用可能な最新の情報を記憶するために、マスターでスレーブスナップショットバケット集合内に維持されてもよい。Ｓ１は、母集団（ＳＢ１）、すなわち、現在、ＳＢ１におけるトークンの数を、時間Ｔ１での書き込み確認応答内でピギーバックされるマスターに提供してもよい。同様に、Ｓ２は、母集団（ＳＢ２）を時間（Ｔ１＋デルタ１）における書き込み確認応答で、マスターに提供してもよい。マスターが母集団（ＳＢ１）を受信したとき、それは母集団（ＳＢ１）を母集団（ＣＰＢ）、コモンプロキシバケットの現在のトークンカウントと比較してもよく、母集団（ＳＢ１）が母集団（ＣＰＢ）より小さい場合、母集団（ＣＰＢ）は母集団（ＳＢ１）に対して設定されてもよい。類似したチェックは、母集団（ＳＢ２）がマスターで受信されるときに行われてもよい。従って、どのくらいの頻度でスレーブ側情報が更新されるかに依存して、マスターの見解がスレーブの１つまたは両方について多少古い可能性がある所与のいずれかの時点で、マスターは、コモンプロキシバケットを使用して、２つのスレーブのデバイスに固有のバケットの最小スループット容量の追跡を続けてもよい。いくつかの実装において、コモンプロキシバケットの代わりに、各々のスナップショットバケットは、図７に示されるように、各スレーブに対応するマスターで維持されてもよい。
【００５６】
エレメント９１８に示されるように、（論理区画のなんらかの部分に対する作成、更新、または削除要求などの）論理区画に向けられる書き込み要求が受信されてもよい。図示される実施形態において、書き込みに対する承認制御は、論理区画のすべての複製のマスター複製についてまたはそこで取り扱われ得る。承認制御機構は、十分なトークンがマスターバケット集合及びスレーブスナップショットバケット集合の１つのまたは両方のバケット集合に存在するかどうかを決定してもよい。ただし、トークンの十分性は、バケットのための各々の消費方針に基づいて、バケット集合のバケットごとに解釈され得る。１つの実装において、例えば、特定のバケット（例えば、図５のマスターバケット集合のバケット１５０Ａなどの準備された容量バケット）がその消費方針に基づいて十分なトークンを有する場合、要求は、他のバケットの状態にかかわらず、承認され得る。このような実装において、図１０に図示されるように、また以下に記載されるように、特定のバケットが十分なトークンを有さない場合、他のバケットの母集団が検査されてもよく、要求は、これらの他のバケットのコンテンツに基づいて、承認されてもよい。別の実装において、１つのトークンは、書き込み要求を許すために、各集合の各バケットで必要とされてもよい。複数のバケットが所定のバケット集合内に実装される１つの実装において、ゼロトークンは集合の１つ以上のバケットから要求されてもよい一方、１つ以上のトークンは集合の１つ以上の他のバケットの各々から要求されてもいい。他の実装において、異なる数のトークンは、書き込み要求のパラメータに依存して種々のバケットから要求されてもよく、例えば、承認制御機構が、書き込み要求が多数の物理的なまたは論理的書き込みをもたらすだろうことを決定することができる場合、１を越えるトークンは特定のバケットから消費され得る。
【００５７】
十分なトークンがバケット集合の各々で発見されると、有効な一または複数の消費方針に基づいて、図９のエレメント９２２に対応する動作において決定されるように、書き込み要求は実行に対して承諾されてもよい（エレメント９２６）。適切な数のトークンはバケット集合の各々から消費され得、書き込み複製要求はマスターから適切な数のスレーブに送られてもよい。書き込みがクォーラム数の複製で成功裏に複製される場合（エレメント９２８で決定されるように）、要求しているクライアントとは、書き込みが成功したと知らされ得る（エレメント９３２）。十分なトークンが発見されない場合（エレメント９２２で決定されるように）または書き込みがクォーラム複製のいずれかで成功していない場合（エレメント９２８で決定されるように）、クライアントは、いくつかの実施形態において、書き込みが失敗したと知らされ得る（エレメント９３６）。他の実施形態において、書き込みは遅延の後、再試行され得る。
【００５８】
図１０は、少なくともいくつかの実施形態による、ネットワークにアクセス可能なサービスにおけるバーストモード書き込みのためのトークンベースの承認制御機構を実装するように行われてもよい動作の態様を示すフロー図である。図示される実施形態におけるマスターバケット集合は、図５のそれらと類似した、準備された容量バケット１５０Ａ、バーストハンドリングバケット１５０Ｂ、及びマスター共用デバイス１５０Ｃを含んでもよい。スレーブスナップショットバケット集合は、図５のそれと類似した、コモンプロキシバケット１５７を含んでもよい。エレメント１００１に示されるように、書き込み要求は書き込みが向けられる論理区画のマスター複製に関連付けられた承認制御器１８０で受信されてもよい。
【００５９】
マスターの準備された容量バケット１５０Ａが、その消費方針に基づく十分なトークンを有する場合（エレメント１００４で決定されるように）、論理区画は通常の（非バースト）モードにあるとみなされてもよく、また、書き込み要求は承諾されてもよい（エレメント１００７）。１以上のトークンは準備された容量バケットから消費され（取り除かれ）、書き込みの承諾を反映してもよい（エレメント１０１０）。少なくともいくつかの実施形態において、トークンはまた、バケットの各々の消費方針に基づいて、マスターバケット集合及び／またはスレーブスナップショットバケット集合の他のバケットから取り除かれてもよく、例えば、１つの単純な実装において、１つのトークンは、バケット１５０Ａ、１５０Ｂ、１５０Ｃ、及び１５７の各々から消費され得る。種々のバケットの補充速度に依存して、図示される実施形態において、トークンは、マスターバケット集合の１つ以上のバケットに追加されてもよい（エレメント１０３４）。（スレーブスナップショットバケット集合の母集団に対する変化は、上述のように、スレーブ複製から受信される通信に基づいていてもよく、このような通信に関連する動作の実施例は、図１１ａ及び１１ｂに図示される。）
【００６０】
しかしながら、マスターの準備された容量バケット１５０Ａが十分なトークンを有していない場合（エレメント１００４で決定されるように）、論理区画はバーストモードにあるとみなされてもよい。図示される実施形態において、バーストモードで、バケット１５０Ｂ、１５０Ｃ、及び１５０Ｄの各々がチェックされて、それらがそれぞれ、それらの消費方針に基づいて、十分なトークンを有するかどうかを決定してもよい。エレメント１０１４に図示されるように、バーストハンドリングバケット１５０Ｂが最初にチェックされて、例えば、論理区画が構成されたバーストピーク容量限界内にあるかどうか、及び／またはバーストを許すために十分なバンクされたトークンを有するかどうかを決定してもよい。バケット１５０Ｂが十分なトークンを有する場合、マスターの共用デバイスバケット１５０Ｃが次にチェックされて（エレメント１０１８）、例えば、十分なスループット容量がマスターのデータのために使用される共用記憶デバイスで利用可能であるかどうかを決定してもよい。その後、マスターの共用デバイスバケット１５０Ｃが十分なトークンを有する場合、スレーブ−スナップショットコモンプロキシバケット１５７がチェックされて、例えば、スレーブ複製（複数を含む）がそれらの各々の共用のデバイスで十分なスループット容量を有しやすいかどうかを決定してもよい（エレメント１０２２）。（スレーブスナップショットバケット集合がスレーブごとに１つのスナップショットバケットを有する実施形態において、図７に図示されるように、少なくともスナップショットバケットの部分集合の各々がコモンプロキシバケットをチェックする代わりに、チェックされてもよいことに留意されたい。）エレメント１０１４、１０１８及び１０２２に対応する動作でチェックされるすべてのバケットが十分なトークンを有する場合、書き込み要求は承諾される実行に対して承諾され得る（エレメント１０２６）。適切な数のトークンは各バケット１５０Ｂ、１５０Ｃ、及び１５７から消費され得る（エレメント１０３０）。いくつかの実施形態において、その上、トークンは準備された容量バケット１５０Ａからも随意に「消費」されてもよい（準備された容量バケットの負数母集団をもたらしてもよい）。マスターバケット集合の種々のバケットは、それらの各々の補充速度（エレメント１０３４）により補充されてもよい。エレメント１０１４、１０１８及び１０２２に図示される動作が、対応するバケットが十分なトークンを有していないことを示した場合、書き込み要求は拒否されることもあり（または遅延される／再試行される）、いくつかの実装において、クライアントは拒否に関して通知され得る（エレメント１０３８）。バケットがバーストモード間でチェックされる順序は異なる実装において異なることもあり、また、すべてのバケットのチェック、トークン消費動作及び／または種々のバケットのための補充が少なくともいくつかの実施形態におけるトランザクションなどの単一のアトミックな動作内で行われ得ることに留意されたい。
【００６１】
図１１ａ及び１１ｂは、少なくともいくつかの実施形態による、マスター複製でスレーブ複製共用記憶バケット母集団を取得するように行われてもよい動作の態様を示すフロー図である。エレメント１１０２に示されるように、書き込み複製要求８１５は、データオブジェクトの耐久性要求に従ってマスター４１２からスレーブ４１６に送信されてもよい。書き込み確認応答８２０は、スレーブからマスターで取得され得（エレメント１１０６）、スレーブによって使用中の共用記憶デバイス１０２の利用可能なスループット容量を示すピギーバックされるスレーブ母集団スナップショット６５０を含んでも良い。いくつかの実施形態において、前に述べたように、書き込み確認応答の部分集合のみが、ピギーバックされるスレーブ母集団スナップショットを含有してもよい。いくつかの実施形態において、書き込みがスレーブで成功したか失敗したかにかかわらず、スレーブ母集団スナップショットを有する書き込み確認応答はマスターに送られてもよく、その結果、ピギーバックされるスレーブ状態情報は、書き込み複製の失敗から独立してマスターで受信されてもよい。確認応答がピギーバックされるスレーブ母集団スナップショットを含んでいた場合、必要とあれば、スナップショットは、マスターのスレーブスナップショットバケット集合１５５（エレメント１１０８）内の１つ以上のバケットの母集団を調整または更新するために使用されてもよく、更新されたスレーブスナップショットバケット集合は、例えば、バーストモード間で、マスターにおける後続の書き込み要求に対して承認制御の決定をなすために使用されてもよい（エレメント１１１２）。いくつかの場合、例えば、図５に示されるようなコモンプロキシバケットが使用され、新しく受信されるスナップショットが、異なるスレーブの共用デバイスバケットに関してすでに知られているものより高いトークン母集団を示す場合、コモンプロキシバケットの母集団に対して何の変化もない場合があるように、スレーブスナップショットバケット集合に対する調整が必要とされないことがあることに留意されたい。
【００６２】
図１０ｂのエレメント１１５２に示されるように、いくつかの実施形態において、マスター４１２は、スレーブの健康状態を示す心拍または「私は生きている」というメッセージをスレーブから受信するように構成されてもよい。スレーブのデータのために使用されている共用記憶デバイス１０２における利用可能なスループット容量を表している母集団スナップショット６５０は、心拍メッセージにおいてピギーバックされ得る。スレーブの健康状態を検証することに加えて、マスターは母集団スナップショット６５０を心拍メッセージから抽出してもよい（エレメント１１５６）。スレーブスナップショットバケット集合の１つ以上の表の母集団はスナップショットに従って調整され得（エレメント１１５８）、更新されたスレーブスナップショットバケット集合は後続の書き込み承認制御の決定をなすために使用され得る（エレメント１１６２）。いくつかの場合、例えば、図５に示されるようなコモンプロキシバケットが使用され、新しく受信されるスナップショットが、異なるスレーブの共用デバイスバケットに関して最後に受信された高いトークン母集団を示す場合、図１０ａに示される実施形態の場合におけるように、スレーブスナップショットバケット集合に対する調整が必要とされないこともある。いくつかの実装において、心拍メッセージの部分集合のみがピギーバックされるスレーブ母集団スナップショットを含有してもよい。
【００６３】
種々の実施形態において、図９、１０、１１ａ、及び１１ｂのフロー図に示される動作のいくつかは省略されるまたは図示されるものとは異なる順序で行われてもよい、または連続的ではなく並行して行われてもよいことに留意されたい。
【００６４】
使用する場合
書き込みに対する保守的なトークンベースの承認制御の上述の技術は、種々の異なるシナリオにおいて有益であり得る。例えば、いくつかのデータベース環境において、クライアントは非常に大きい（テラバイトまたはペタバイト）表または表の集合を有してもよく、また、非常に高いＩ／Ｏ速度は表に向けられてもよい。耐久性／冗長性要求がいくつかの複製が表ごとに維持されていること、また、書き込みが成功していると宣言する前にすべての書き込みがいくつかの複製で持続されていることを規定していてもよい。このようなシナリオにおいて、表は、異なるストレージノード及び／またはデバイスにわたって、頻繁に共用されるまたは区画されてもよく、所定の記憶デバイスに存在するデータの集合は多くの異なる表の多くの異なる区画の複製からの部分を含んでもよい。概して、所定の記憶デバイスに向けられる作業負荷のバリエーションを徐々に予期することは非常に難しいかもしれない。さらにまた、所定の区画の複製は１を越えるデータセンターにわたって、または異なる市、州または国においても分散されてもよい。このため、所定の書き込み要求を承諾するか拒否するかについて決定をなすとき、特に、書き込み要求速度がクライアントの代わりに実施されている準備されたスループット限界を超えるときの動作のバーストモード間に、１を越える複製からの効率的に送信された最近のスループット容量情報または作業負荷条件の利用可能性は、本願に記載されるように、非常に有益になり得る。このような承認制御機構は、承諾される書き込み要求複製の失敗の発生率（または、書き込みの再試行から生じる予想しないほど長いとクライアントが感じる待ち時間）を減らすのに役立ち得、それによって、全体的な顧客満足度を上げ得る。
【００６５】
例示的なコンピュータシステム
少なくともいくつかの実施形態において、トークンベースの承認制御及び／またはオブジェクト区画が複製されるストレージノードを実装するための技術を含む、本願に記載される技術のうちの１つ以上の一部またはすべてを実装するサーバは、１つ以上のコンピュータアクセス可能媒体を含むまたはこれにアクセスするように構成される汎用コンピュータシステムを含んでもよい。図１２は、このような汎用コンピューティングデバイス３０００を図示する。図示される実施形態において、コンピューティングデバイス３０００は、入力／出力（Ｉ／Ｏ）インターフェース３０３０を介してシステムメモリ３０２０に連結される１つ以上のプロセッサ３０１０を含む。コンピューティングデバイス３０００はさらに、Ｉ／Ｏインターフェース３０３０に連結されるネットワークインターフェース３０４０をさらに含む。
【００６６】
種々の実施形態において、コンピューティングデバイス３０００は、１つのプロセッサ３０１０を含むユニプロセッサシステム、またはいくつか（例えば、２つ、４つ、８つ、または別の適切な数の）のプロセッサ３０１０を含むマルチプロセッサシステムであってもよい。プロセッサ３０１０は、命令を実行することが可能ないずれかの適切なプロセッサであり得る。例えば、種々の実施形態において、プロセッサ３０１０は、ｘ８６、ＰｏｗｅｒＰＣ、ＳＰＡＲＣ、またはＭＩＰＳのＩＳＡ、またはいずれかの他の適切なＩＳＡなどの種々の命令セットアーキテクチャ（ＩＳＡ）のうちのいずれかを実装する汎用または埋め込まれたプロセッサであってもよい。マルチプロセッサシステムにおいて、プロセッサ３０１０の各々は、一般に同じＩＳＡを実装してもよいが必ずしも実装しなくてもよい。
【００６７】
システムメモリ３０２０は、命令及びプロセッサ（複数を含む）３０１０によってアクセス可能データを記憶するように構成され得る。種々の実施形態において、システムメモリ３０２０は、スタティックランダムアクセスメモリ（ＳＲＡＭ）、同期型ダイナミックＲＡＭ（ＳＤＲＡＭ）、不揮発性／フラッシュタイプのメモリ、またはいずれかの他のタイプのメモリなどのいずれかの適切なメモリ技術を使用して実装され得る。図示される実施形態において、プログラム命令及びこれらの方法、技術、及び上述のデータなどの１つ以上の所望の機能を実装するデータは、システムメモリ３０２０内に記憶されるコード３０２５及びデータ３０２６として示される。
【００６８】
１つの実施形態において、Ｉ／Ｏインターフェース３０３０は、プロセッサ３０１０、システムメモリ３０２０、及びデータオブジェクト区画の物理的な複製を記憶するために使用される種々のタイプの持続型及び／または揮発性記憶デバイスなどのネットワークインターフェース３０４０または他の周辺インターフェースを含むデバイス内のいずれかの周辺デバイス間でＩ／Ｏトラフィックを統合するように構成されてもよい。いくつかの実施形態において、Ｉ／Ｏインターフェース３０３０は、いずれかの必要なプロトコル、タイミングまたは他のデータ変換を行って、データ信号を１つのコンポーネント（例えば、システムメモリ３０２０）から別のコンポーネント（例えば、プロセッサ３０１０）によって使用されるのに適したフォーマットに変換してもよい。いくつかの実施形態において、Ｉ／Ｏインターフェース３０３０は、例えば、周辺コンポーネントインターコネクト（ＰＣＩ）バス標準またはユニバーサルシリアルバス（ＵＳＢ）標準の変形などの種々のタイプの周辺バスを通して取り付けられるデバイスの支持を含み得る。いくつかの実施形態において、Ｉ／Ｏインターフェース３０３０の機能は、例えば、ノースブリッジ及びサウスブリッジなどの２つ以上のコンポーネントに分かれてもよい。また、いくつかの実施形態において、システムメモリ３０２０に対するインターフェースなどのＩ／Ｏインターフェース３０３０の機能性のうちのいくつかまたはすべては、プロセッサ３０１０に直接、組み込まれてもよい。
【００６９】
ネットワークインターフェース３０４０は、例えば、図１から図１１ｂに図示されるような他のコンピュータシステムまたはデバイスなどの、１つのネットワーク３０５０または複数のネットワーク３０５０に取り付けられたコンピューティングデバイス３０００及び他のデバイス３０６０間でデータが交換されるように構成されてもよい。種々の実施形態において、ネットワークインターフェース３０４０は、例えば、イーサネット（登録商標）ネットワークのタイプなどの、いずれかの適切な有線または無線の一般的なデータネットワークを介して通信を支持し得る。さらに、ネットワークインターフェース３０４０は、アナログ音声ネットワークまたはデジタルファイバー通信ネットワークなどの電気通信／電話網を介して、ファイバーチャネルＳＡＮなどのストレージエリアネットワークを介して、またはいずれかの他の適切なタイプのネットワーク及び／またはプロトコルを介して通信を支持し得る。
【００７０】
いくつかの実施形態において、システムメモリ３０２０は、図１から図１１ｂに関して上述するような対応する方法及び装置の実施形態を実装するための、プログラム命令及びデータを記憶するように構成されたコンピュータアクセス可能媒体の１つの実施形態であってもよい。しかしながら、他の実施形態において、プログラム命令及び／またはデータは、異なるタイプのコンピュータアクセス可能媒体に受信され、送られまたは記憶されてもよい。一般的に言えば、コンピュータアクセス可能媒体は、磁気または光学媒体などの非一時的ストレージ媒体またはメモリ媒体、例えば、Ｉ／Ｏインターフェース３０３０を介してコンピューティングデバイス３０００に連結されるディスクまたはＤＶＤ／ＣＤを含んでもよい。非一時的コンピュータ−アクセス可能記憶媒体はまた、システムメモリ３０２０または別のタイプのメモリとしてコンピューティングデバイス３０００のいくつかの実施形態に含まれてもよい、ＲＡＭ（例えばＳＤＲＡＭ、ＤＤＲ  ＳＤＲＡＭ、ＲＤＲＡＭ、ＳＲＡＭ等）、ＲＯＭなどのいずれかの揮発性または不揮発性媒体も含んでよい。さらに、コンピュータアクセス可能媒体は、ネットワークインターフェース３０４０を介して実装され得るような、ネットワーク及び／または無線リンクなどの通信媒体を介して搬送される、電気、電磁的、またはデジタル信号などの送信媒体または信号を含んでもよい。図１２に図示されるような複数のコンピューティングデバイスの部分またはすべては、種々の実施形態において記載される機能性を実装するために使用されてもよく、例えば、種々の異なるデバイス及びサーバ上で起動しているソフトウェアコンポーネントは、機能性を提供するために共同してもよい。いくつかの実施形態において、記載される機能性の部分は、汎用コンピュータシステムを使用して実装されることに加えてまたはその代わりに、記憶デバイス、ネットワークデバイス、または特別の目的のコンピュータシステムを使用して実装されてもよい。本願において使用されるような用語「コンピューティングデバイス」は、少なくともすべてのこれらのタイプのデバイスを言及し、これらのタイプのデバイスに限定されない。
【００７１】
以上の実施形態は、以下の付記を考慮してより良く理解され得る。
１．１つ以上の論理区画を含むデータオブジェクトの論理区画に対応して、論理区画のマスター複製及び論理区画のうちの１つ以上のスレーブ複製を記憶することであって、複製方針に従って、論理区画への書き込みが、マスター複製及び少なくとも１つのスレーブ複製で複製される、記憶することと、
マスター複製に対応して、１つ以上のバケットを含むマスターバケット集合、及び１つ以上のバケットを含むスレーブスナップショットバケット集合を記憶することであって、マスターバケット集合及びスレーブスナップショットバケット集合の各バケットが、（ａ）論理区画に向けられる動作のスループットを制限するように使用可能なトークンの各々の補充可能な集まりを含み、（ｂ）許可された動作のために消費されるトークンの数を示すトークン消費方針を有する、記憶することと、
スレーブバケット更新プロトコルに少なくとも部分的に基づいて、スレーブスナップショットバケット集合のうちの特定のバケットのトークン母集団を更新することであって、スレーブバケット更新プロトコルに従って、マスター複製が、１つ以上のスレーブ複製のうちの特定のスレーブ複製のデータの少なくとも一部が記憶される共用記憶デバイスで利用可能なスループット容量の指標を取得するように構成され、共用記憶デバイスが、１つ以上のデータオブジェクトのうちの１つ以上の論理区画に対応するデータを記憶するように構成可能である、更新することと、
論理区画に向けられる書き込み要求を受信することに応答して、
マスターバケット集合及びスレーブスナップショットバケット集合のバケットの各々のトークン消費方針に従って、十分な数のトークンがマスターバケット集合及びスレーブスナップショットバケット集合のうちの少なくとも１つのバケット集合において利用可能であるかどうかに少なくとも部分的に基づいて、書き込み要求が実行のために承諾されるべきであるかどうかを決定することと、
書き込み要求が実行のために承諾されるべきであると決定することに応答して、書き込み要求に対応する１つ以上のデータ修正動作を開始することと、を含む方法。
２．マスターバケット集合のうちの特定のバケットのトークン母集団に少なくとも部分的に基づいて、論理区画が動作のバーストモードにあるかどうかを決定することと、
論理区画が動作のバーストモードにあると決定することに応答して、十分な数のトークンが（ａ）マスターバケット集合及び（ｂ）スレーブスナップショットバケット集合において利用可能であるかどうかに少なくとも部分的に基づいて、書き込み要求が実行のために承諾されるべきであるかどうかを決定することと、をさらに含む、付記１に記載の方法。
３．１つ以上のスレーブ複製が特定のスレーブ複製及び第２のスレーブ複製を含み、
特定のスレーブ複製に対応して、第１の共用デバイスバケットであって、第１の共用デバイスバケットのトークン母集団が共用記憶デバイスで利用可能なスループット容量を示す、第１の共用デバイスバケットを記憶することと、
第２のスレーブ複製に対応して、第２の共用デバイスバケットであって、第２の共用デバイスバケットのトークン母集団が、第２のスレーブ複製のデータの少なくとも一部が記憶される第２の共用記憶デバイスで利用可能なスループット容量を示す、第２の共用デバイスバケットを記憶することであって、第２の共用記憶デバイスが１つ以上のデータオブジェクトのうちの１つ以上の論理区画に対応するデータを記憶するように構成可能である、記憶することと、をさらに含み、
該スレーブバケット更新プロトコルを実装することが、マスター複製が、（ａ）第１の共用デバイスバケットのトークン母集団及び（ｂ）第２の共用デバイスバケットのトークン母集団の各々の時点スナップショットを取得することを含む、付記１に記載の方法。
４．スレーブスナップショットバケット集合がコモンプロキシバケットを含み、該スレーブバケット更新プロトコルを実装することが、
各々の時点スナップショットに少なくとも部分的に基づいて、第１及び第２の共用デバイスバケットのトークン母集団のなかのトークン母集団の最小値の推測を決定することと、
推測に少なくとも部分的に基づいて、コモンプロキシバケットのトークン母集団を更新することと、を含み、
コモンプロキシバケットに関連付けられたトークン消費方針に従って、本方法が、
コモンプロキシバケットが少なくとも１つのトークンを含み、マスターバケット集合の少なくとも１つのバケットが少なくとも１つのトークンを含むという決定に基づいて、実行のために書き込み要求を承諾することをさらに含む、付記３に記載の方法。
５．スレーブスナップショットバケット集合が、特定のスレーブ複製に対応する第１のスナップショットバケット及び第２のスレーブ複製に対応する第２のスナップショットバケットを含み、該スレーブバケット更新プロトコルを実装することが、
第１の共用デバイスバケットのトークン母集団の時点指標に基づいて、第１のスナップショットバケットのトークン母集団を更新することと、
共用デバイスバケット第２の共用デバイスバケットのトークン母集団の時点指標に基づいて、第２のスナップショットバケットのトークン母集団を更新することと、を含み、
本方法が、
第１のスナップショットバケットが少なくとも１つのトークンを含み、第２のスナップショットバケットが少なくとも１つのトークンを含み、マスターバケット集合の少なくとも１つのバケットが少なくとも１つのトークンを含むという決定に基づいて、実行のために書き込み要求を承諾することをさらに含む、付記３に記載の方法。
６．マスター複製から特定のスレーブ複製に、書き込み要求に対応する書き込み複製要求を送信することと、
マスター複製で、書き込み複製要求の確認応答を受信することであって、スレーブバケット更新プロトコルに従って、確認応答が、共用記憶デバイスで利用可能なスループット容量の指標を含む、受信することと、をさらに含む、付記１に記載の方法。
７．１つ以上のプロセッサと、
１つ以上のプロセッサに連結されるメモリであって、１つ以上のプロセッサによって実行されるとき、１つ以上のプロセッサに、
データオブジェクトのうちの１つ以上の論理区画の論理区画のマスター複製に対応して、１つ以上のバケットを含むマスターバケット集合及び１つ以上のバケットを含むスレーブスナップショットバケット集合を記憶することであって、マスターバケット集合及びスレーブスナップショットバケット集合の各バケットが、論理区画に向けられる書き込み動作のスループットを制限するように使用可能なトークンの各々の集まりを含む、記憶することと、
論理区画のうちの特定のスレーブ複製のデータの少なくとも一部が記憶される共用記憶デバイスにおける、利用可能なスループット容量の指標に少なくとも部分的に基づいて、スレーブスナップショットバケット集合のうちの特定のバケットのトークン母集団を更新することと、
論理区画に向けられる書き込み要求を受信することに応答して、
マスターバケット集合及びスレーブスナップショットバケット集合のバケットの各々のトークン消費方針に従って、十分な数のトークンが（ａ）マスターバケット集合及び（ｂ）スレーブスナップショットバケット集合のうちの少なくとも１つのバケット集合において利用可能であるかどうかに少なくとも部分的に基づいて、書き込み要求が実行のために承諾されるべきであるかどうかを決定することと、
実行に対して書き込み要求が承諾されるべきであるという決定に応答して、書き込み要求に対応する１つ以上のデータ修正動作を開始することと、を行わせるというプログラム命令を記憶しているメモリと、を備えるシステム。
８．プログラム命令が、１つ以上のプロセッサによって実行されるとき、１つ以上のプロセッサに、
特定のスレーブ複製及び第２のスレーブ複製を含む、複数の論理区画のスレーブ複製を記憶することと、
特定のスレーブ複製に対応して、第１の共用デバイスバケットであって、第１の共用デバイスバケットのトークン母集団が、共用記憶デバイスで利用可能なスループット容量を示す第１の共用デバイスバケットを記憶することと、
第２のスレーブ複製に対応して、第２の共用デバイスバケットであって、第２の共用デバイスバケットのトークン母集団が、第２のスレーブ複製のデータの少なくとも一部が記憶される第２の共用記憶デバイスで利用可能なスループット容量を示す第２の共用デバイスバケットを記憶することと、を行わせ、
特定のバケットのトークン母集団の該更新が、（ａ）第１の共用デバイスバケットのトークン母集団のスナップショット及び（ｂ）第２の共用デバイスバケットのトークン母集団のスナップショットを取得するマスター複製に少なくとも部分的に基づく、付記７に記載のシステム。
９．特定のバケットが、少なくとも特定のスレーブ複製及び第２のスレーブ複製の組み合わせに対応するコモンプロキシバケットを含み、プログラム命令が、１つ以上のプロセッサによって実行されるとき、１つ以上のプロセッサに、
共用デバイスバケット第１及び第２の共用デバイスバケットの各々のスナップショットを取得することに少なくとも部分的に基づいて、第１及び第２の共用デバイスバケットのトークン母集団のなかの最小トークン母集団の推測を決定することと、
推測に基づいて、コモンプロキシバケットのトークン母集団を更新することと、
コモンプロキシバケットが少なくとも１つのトークンを含むという指標に少なくとも部分的に基づいて、実行のために書き込み要求を承諾することと、を行わせる、付記８に記載のシステム。
１０．スレーブスナップショットバケット集合が特定のスレーブ複製に対応する第１のスナップショットバケット及び第２のスレーブ複製に対応する第２のスナップショットバケットを含み、プログラム命令が、プログラムが、１つ以上のプロセッサによって実行されるとき、１つ以上のプロセッサに、
第１の共用デバイスバケットのトークン母集団の指標に基づいて、第１のスナップショットバケットのトークン母集団を更新することと
第２の共用デバイスバケットのトークン母集団の指標に基づいて、第２のスナップショットバケットのトークン母集団を更新することと、
第１のスナップショットバケットが少なくとも１つのトークンを含み、第２のスナップショットバケットが少なくとも１つのトークンを含むという決定に少なくとも部分的に基づいて、実行のために書き込み要求を承諾することと、を行わせる、付記８に記載のシステム。
１１．プログラム命令が、１つ以上のプロセッサによって実行されるとき、１つ以上のプロセッサに、
マスター複製から特定のスレーブ複製に、書き込み要求に対応する複製要求を送信することと、
マスター複製で、複製要求の確認応答を受信することであって、確認応答が、共用記憶デバイスで、利用可能なスループット容量の指標を含む、受信することと、を行わせる、付記７に記載のシステム。
１２．プログラム命令が、１つ以上のプロセッサによって実行されるとき、１つ以上のプロセッサに、
マスター複製で、特定のスレーブ複製から、特定のスレーブ複製の健康状態を示す心拍メッセージを受信することを行わせ、心拍メッセージが、共用記憶デバイスで利用可能なスループット容量の指標を含む、付記７に記載のシステム。
１３．マスターバケット集合が準備された容量バケットを含み、プログラム命令が、１つ以上のプロセッサによって実行されるとき、１つ以上のプロセッサに、
データオブジェクトにアクセスするように権限を与えられたクライアントによって提供された標的とされるスループットの指標に少なくとも部分的に基づいて、その最初のトークン母集団及び補充速度を含む、準備された容量バケットの１つ以上のパラメータを構成することと、
少なくとも１つのトークン準備された容量バケットが少なくとも１つのトークンを含むという決定に少なくとも部分的に基づいて、書き込み要求が、実行のために承諾されるべきであると決定することと、を行わせる、付記７に記載のシステム。
１４．マスターバケット集合がバーストハンドリングバケットを含み、プログラム命令が、１つ以上のプロセッサによって実行されるとき、１つ以上のプロセッサに、
トークンをバーストハンドリングバケットに追加することであって、追加されたトークンの数が、論理区画に向けられる測定された動作速度が、特定の期間、標的とされるスループットより低いという決定に少なくとも部分的に基づく、追加することと、
（ａ）異なる書き込み要求を受信することと、（ｂ）異なる書き込み要求が受信されるとき、準備された容量バケットがトークンを含有しないことを決定することと、に応答して、バーストハンドリングバケットが少なくとも１つのトークンを含むという決定に少なくとも部分的に基づいて、実行のために異なる書き込み要求を承諾することと、を行わせる、付記１３に記載のシステム。
１５．マスターバケット集合が、マスター共用デバイスバケットであって、マスター共用デバイスバケットのトークン母集団がマスター複製のデータの少なくとも一部を記憶するために使用される異なる共用記憶デバイスの利用可能なスループット容量に少なくとも部分的に基づく、マスター共用デバイスバケットを含み、プログラム命令が、１つ以上のプロセッサによって実行されるとき、１つ以上のプロセッサに、
少なくとも１つのトークン、マスター共用デバイスバケットが少なくとも１つのトークンを含むという決定に少なくとも部分的に基づいて、実行のために書き込み要求を承諾することと、を行わせる、付記７に記載のシステム。
１６．マスターバケット集合が、ノード能力バケットであって、ノード能力バケットのトークン母集団が、マスター複製のデータの少なくとも一部が記憶される記憶ノードの性能能力の測定基準に少なくとも部分的に基づくノード能力バケットを含み、プログラム命令が、１つ以上のプロセッサによって実行されるとき、１つ以上のプロセッサに、
ノード能力バケットが少なくとも１つのトークンを含むという決定に少なくとも部分的に基づいて、実行のための書き込み要求を承諾することと、を行わせる、付記７に記載のシステム。
１７．プログラム命令が、１つ以上のプロセッサによって実行されるとき、１つ以上のプロセッサに、
プログラマチックインターフェースを介して受信される構成要求に従って、承認制御方針の特性を修正することと、
論理区画に向けられる異なる書き込み要求を受信することに応答して、特性に少なくとも部分的に基づいて、異なる書き込み要求が実行に対して承諾されるべきかどうかを決定することと、を行わせる、付記７に記載のシステム。
１８．１つ以上のプロセッサ上で実行されるとき、１つ以上のプロセッサに、
データオブジェクトの論理区画に対応して、マスター複製及び特定のスレーブ複製を含む１つ以上のスレーブ複製を記憶することであって、マスター複製が第１の記憶デバイスに記憶されたデータを含み、特定のスレーブ複製が第２の記憶デバイスに記憶されたデータを含む、記憶することと、
論理区画の少なくとも一部に向けられる書き込み要求を受信することと、
（ａ）マスター複製で利用可能なスループット容量、及び（ｂ）特定のスレーブ複製で利用可能なスループット容量のトークンベースのプロトコルを使用して取得される指標、のうちの１つ以上に少なくとも部分的に基づいて、実行のために書き込み要求を承諾すべきであるかどうかを決定することと、
実行に対して書き込み要求を承諾することに応答して、書き込み要求に対応する１つ以上のデータ修正動作を開始することと、を行わせるというプログラム命令を記憶している非一時的コンピュータ−アクセス可能記憶媒体。
１９．１つ以上のプロセッサ上で実行されるとき、プログラム命令が、プロセッサに、
マスター複製に対応して、１つ以上のバケットを含むマスターバケット集合及び１つ以上のバケットを含むスレーブスナップショットバケット集合を記憶することであって、マスターバケット集合及びスレーブスナップショットバケット集合の各バケットが、トークンの各々の集まりを含む、記憶することと、
マスター複製で利用可能なスループット容量を表すために、マスターバケット集合の少なくとも特定のバケットのトークン母集団を更新することと、
特定のスレーブ複製で利用可能なスループット容量を表すために、スレーブスナップショットバケット集合の少なくとも特定のバケットのトークン母集団を更新することと、を行わせ、
実行に対して書き込み要求を承諾するかどうかの該決定が、
論理区画が動作のバーストモードにあると決定することに応答して、マスターバケット集合の特定のバケットのトークン母集団及びスレーブスナップショットバケット集合の特定のバケットのトークン母集団を検査することを含む、付記１８に記載の非一時的コンピュータ−アクセス可能記憶媒体。
２０．１つ以上のプロセッサ上で実行されるとき、プログラム命令が、１つ以上のプロセッサに、
実行に対して書き込み要求を該承諾することに従って、マスターバケット集合の特定のバケットから少なくとも１つのトークンを、また、スレーブスナップショットバケット集合の特定のバケットから少なくとも１つのトークンを消費することを行わせる、付記１９に記載の非一時的コンピュータ−アクセス可能記憶媒体。
２１．アトミックな動作内で、マスターバケット集合の特定のバケットから少なくとも１つのトークンが、また、スレーブスナップショットバケット集合の特定のバケットから少なくとも１つのトークンが消費される、付記２０に記載の非一時的コンピュータ−アクセス可能記憶媒体。
２２．１つ以上のプロセッサ上で実行されるとき、プログラム命令が、プロセッサに、
特定のスレーブ複製及び第２のスレーブ複製を含む、論理区画の複数のスレーブ複製を記憶することと、
特定のスレーブ複製に対応して、第１の共用デバイスバケットであって、第１の共用デバイスバケットのトークン母集団が、第２の記憶デバイスで利用可能なスループット容量を示す第１の共用デバイスバケットを記憶することと、
第２のスレーブ複製に対応して、第２の共用デバイスバケットであって、第２の共用デバイスバケットのトークン母集団が、第２のスレーブ複製のデータの少なくとも一部が記憶される第３の記憶デバイスで利用可能なスループット容量を示す第２の共用デバイスバケットを記憶することと、を行わせ、
スレーブスナップショットバケット集合の特定のバケットのトークン母集団の該更新が、（ａ）第１の共用デバイスバケットのトークン母集団及び（ｂ）第２の共用デバイスバケットのトークン母集団の各スナップショットを取得することに少なくとも部分的に基づく、付記１９に記載の非一時的コンピュータ−アクセス可能記憶媒体。
２３．スレーブスナップショットバケット集合の特定のバケットがコモンプロキシバケットを含み、１つ以上のプロセッサ上で実行されるとき、プログラム命令が、１つ以上のプロセッサに、
第１及び第２の共用デバイスバケットのトークン母集団のなかの最小トークン母集団の推測を決定することと、
推測に基づいて、コモンプロキシバケットの母集団を更新することと、
コモンプロキシバケットが少なくとも１つのトークンを含むという決定に少なくとも部分的に基づいて、実行のために書き込み要求を承諾することと、を行わせる、付記２２に記載の非一時的コンピュータ−アクセス可能記憶媒体。
２４．１つ以上のプロセッサ上で実行されるとき、プログラム命令が、１つ以上のプロセッサに、
マスター複製から特定のスレーブ複製に、書き込み要求に対応する複製要求を送信することと、
マスター複製で、複製要求の確認応答を受信することであって、確認応答が、特定のスレーブ複製で、利用可能なスループット容量の指標を含む、受信することと、を行わせる、付記１８に記載の非一時的コンピュータ−アクセス可能記憶媒体。
２５．１つ以上のプロセッサ上で実行されるとき、プログラム命令が、１つ以上のプロセッサに、
マスター複製で、特定のスレーブ複製から、特定のスレーブ複製の健康状態を示す心拍メッセージを受信することを行わせ、心拍メッセージが、共用記憶デバイスで利用可能なスループット容量の指標を含む、付記１８に記載の非一時的コンピュータ−アクセス可能記憶媒体。
２６．データオブジェクトがデータベース表のコンテンツを含む、付記１８に記載の非一時的コンピュータ−アクセス可能記憶媒体。
【００７２】
結論
種々の実施形態は、コンピュータアクセス可能媒体に対する前記記載に従って実装された命令及び／またはデータを受信すること、送ることまたは記憶することをさらに含む。一般的に言えば、コンピュータアクセス可能媒体は、例えば、ディスクまたはＤＶＤ／ＣＤ−ＲＯＭなどの磁気または光学媒体などの記憶媒体またはメモリ媒体、ＲＡＭ（例えばＳＤＲＡＭ、ＤＲ、ＲＤＲＡＭ、ＳＲＡＭ等）、ＲＯＭなどの揮発性または不揮発性媒体を含んでもよく、さらに、ネットワーク及び／または無線リンクなどの通信媒体を介して搬送される、電気、電磁的、またはデジタル信号などの送信媒体または信号を含んでもよい。
【００７３】
本願において図面に示され説明されるような種々の方法は、方法の模範的な実施形態を表す。方法はソフトウェア、ハードウェア、またはそれらの組み合わせに実装され得る。方法の順序は変化し得、種々のエレメントは追加され、再度順序付けされ、組み合わされ、省略され、修正されるなどしてもよい。
【００７４】
種々の修正及び変化は、本開示の利益を有する当業者に自明であるようになされるであろう。すべてのこのような修正及び変化を包含することが意図されるため、上記の記載は、限定的な意味ではなく例示的な意味でみなされることが意図される。
【図１】
2016517080.tif 000003
【図２】
2016517080.tif 000004
【図３】
2016517080.tif 000005
【図４】
2016517080.tif 000006
【図５】
2016517080.tif 000007
【図６】
2016517080.tif 000008
【図７】
2016517080.tif 000009
【図８】
2016517080.tif 000010
【図９】
2016517080.tif 000011
【図１０】
2016517080.tif 000012
【図１１】
2016517080.tif 000013
【図１２】
2016517080.tif 000014
【国際調査報告】
2016517080.tif 000015