(57)【特許請求の範囲】
【請求項１】
容量消費を管理するためのデータベース管理システム用のプログラムであって、
前記プログラムは、コンピュータ可読命令が記憶されている１つ以上のメモリを有する１つ以上のコンピューティングノード上で動作し、
前記コンピュータ可読命令は、前記１つ以上のコンピューティングノードによって実行される時に、前記データベース管理システムに、少なくとも、
顧客のために遂行される動作を、前記データベース管理システム上で遂行させる要求であって、要求クラスを示す情報を含む要求を受信するステップと、
関連付けられた第１の容量表示を有する第１のトークンバケットを、複数のトークンバケットを含む１つ以上のデータ構造から、前記要求クラスに少なくとも部分的に基づいて選択するステップと、
前記第１の容量表示が、前記動作を遂行するための容量に十分であると示すことを決定するステップと、
前記第１の容量表示が、前記容量に十分であると示す場合、前記動作を遂行するステップと、
前記動作を遂行するステップにより利用された容量を、前記第１のトークンバケットから引き出し、前記第１の容量表示を更新するステップと、
前記動作を遂行するステップにより利用された前記容量に少なくとも部分的に基づいて、前記複数のトークンバケットのうちの第２のトークンバケットから利用された前記容量を引き出し、前記第２のトークンバケットに関連付けられた第２の容量表示を更新するステップと、
を行わせ、
前記第２のトークンバケットは、前記第１のトークンバケットとトークンを共有する親バケットである、
プログラム。
【請求項２】
前記コンピュータ可読命令は、前記１つ以上のコンピューティングノードによって実行される時に、前記データベース管理システムに、少なくとも、
前記要求クラスと前記第１のトークンバケットとの間の関連付けを示す情報を受信するステップを行わせる、
請求項１に記載のプログラム。
【請求項３】
前記コンピュータ可読命令は、前記１つ以上のコンピューティングノードによって実行される時に、前記データベース管理システムに、少なくとも、
前記複数のトークンバケットのうちの第２のトークンバケットに関連付けられた第２の容量表示が、前記顧客のために前記動作を遂行するための容量の不足を示すことを決定するステップを行わせる、
請求項１に記載のプログラム。
【請求項４】
容量消費を管理するための、コンピュータにより実行される方法であって、前記方法は、
顧客のために遂行される動作を、１つ以上のコンピューティングノード上で遂行させる要求であって、要求クラスを示す情報を含む要求を受信するステップと、
関連付けられた第１の容量表示を有する第１のトークンバケットを、複数のトークンバケットを含む１つ以上のデータ構造から、前記要求クラスに少なくとも部分的に基づいて選択するステップと、
前記第１の容量表示が、前記動作を遂行するための容量に十分であると示すことを決定するステップと、
前記第１の容量表示が、前記容量に十分であると示す場合、前記動作を遂行するステップと、
前記動作を遂行するステップにより利用された容量を、前記第１のトークンバケットから引き出し、前記第１の容量表示を更新するステップと、
前記動作を遂行するステップにより利用された前記容量に少なくとも部分的に基づいて、第２のトークンバケットから利用された前記容量を引き出し、前記第２のトークンバケットに関連付けられた第２の容量表示を更新するステップと、
を含み、
前記第２のトークンバケットは、前記第１のトークンバケットとトークンを共有する親バケットである、
方法。
【請求項５】
前記動作は、ウェブサービス、ウェブサイトおよびデータベース管理システムのうちの１つ以上で遂行される、
請求項４に記載の方法。
【請求項６】
前記複数のデータ構造からの第２の容量表示が、前記顧客のために前記動作を遂行するための容量の不足を示すことを決定するステップをさらに含む、
請求項４に記載の方法。
【請求項７】
前記複数のデータ構造からの前記第１の容量表示および１つ以上の追加の容量表示は、前記顧客のために前記動作を遂行するための容量を示す前記複数のデータ構造中の１つ以上のメモリ場所を共有する、
請求項４に記載の方法。
【請求項８】
前記第１の容量表示は、前記顧客のために動作を遂行するのに利用可能な容量単位の計数を含む、
請求項４に記載の方法。
【請求項９】
前記計数は、割り当てられた容量の蓄積速度に少なくとも部分的に基づいて増大される、
請求項８に記載の方法。
【請求項１０】
容量消費を管理するためのシステム用のプログラムであって、
前記プログラムは、コンピュータ可読命令が記憶されている１つ以上のメモリを有する１つ以上のコンピューティングノード上で動作し、
前記コンピュータ可読命令は、前記１つ以上のコンピューティングノードによって実行される時に、前記システムに、少なくとも、
１つ以上の要求クラスを示す情報を受信するステップと、
前記１つ以上の要求クラスと第１の容量表示を含む１つ以上のデータ構造との間のマッピングを示す情報を受信するステップと、
前記マッピングを示す前記情報に基づき、第１のトークンバケットを選択するステップと、
１つ以上のコンピューティングノード上で動作を遂行するための総容量のサブセットを、前記第１の容量表示に割り当てるステップと
前記第１の容量表示が、前記動作を遂行するための容量に十分であると示すことを決定するステップと、
前記第１の容量表示が、前記容量に十分であると示す場合、前記動作を遂行するステップと、
前記動作を遂行するステップにより利用された容量を、前記第１のトークンバケットから引き出し、前記第１の容量表示を更新するステップと、
前記動作を遂行するステップにより利用された前記容量に少なくとも部分的に基づいて、第２のトークンバケットから利用された前記容量を引き出し、前記第２のトークンバケットに関連付けられた第２の容量表示を更新するステップと、
を行わせ、
前記第２のトークンバケットは、前記第１のトークンバケットとトークンを共有する親バケットである、
プログラム。
【請求項１１】
前記コンピュータ可読命令は、前記１つ以上のコンピューティングノードによって実行される時に、前記システムに、少なくとも、
前記１つ以上のコンピューティングノード上のデータベーステーブルを修正する命令を示す情報を受信するステップと、
命令を示す受信した情報に基づいて、前記データベーステーブルに割り当てられた容量を修正するステップと、
を行わせる、
請求項１０に記載のプログラム。
【請求項１２】
前記コンピュータ可読命令は、前記１つ以上のコンピューティングノードによって実行される時に、前記システムに、少なくとも、
前記データベーステーブルの区分の数に少なくとも部分的に基づいて、総容量の前記サブセットを決定するステップを行わせる、
請求項１１に記載のプログラム。
【請求項１３】
前記コンピュータ可読命令は、前記１つ以上のコンピューティングノードによって実行される時に、前記システムに、少なくとも、
顧客に入力させるための命令を含むユーザインターフェース命令を前記顧客に送信するステップを行わせる、
請求項１０に記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
本出願は、２０１３年５月１７日に出願された米国特許出願第１３，８９７，２３２号の利益を主張し、その開示は参照によりその全体が本明細書に組み込まれる。
【０００２】
データベース管理システム（「ＤＢＭＳ」）は、ＤＢＭＳをデータセンターのサーバーでホストし、ＤＢＭＳをサービスとして法人、大学、政府機関、および他の種類の顧客等の種々の事業体に提供する、第三者プロバイダにより運営され得る。ＤＢＭＳをホストし、そのサービスを種々の事業体に提供するために、プロバイダは典型的には、かなりのリソースをハードウェア、ソフトウェア、およびインフラストラクチャ内に維持する。加えて、プロバイダは、電力、保守経費、および技術者の給料等のＤＢＭＳの運営に関連する種々の継続的な諸経費を課され得る。したがって、種々の事業体に応答性に優れるサービスを提供するために、プロバイダは、そのデータセンターに設置されたハードウェアおよび他のリソースの容量および利用度を最大化することを試み得る。
【０００３】
本明細書中に提供される図面は、例となる実施形態を例示するためのもので、本開示の範囲を限定するようには意図されていない。
【図面の簡単な説明】
【０００４】
【図１】ウェブサービスを通してエンドユーザに公開され、トークン割り当ておよび消費メカニズムの使用により容量消費を制限するデータベース管理システムを示すブロック図である。
【図２】トークン割り当ておよび消費メカニズムを用いたプロビジョニングされた容量の実施を示すフローチャートである。
【図３Ａ】トークンのトークンバケットへの割り当ておよびトークンバケットからの複数の要求種類のトークン消費を示す図である。
【図３Ｂ】要求の種類に従って分類される複数のトークンバケットへのトークンの割り当て、および対応する要求種類の処理に基づくバケットからのトークンの引き出しを示す図である。
【図４】要求種類の複数の要求クラスへの割り振り、ならびにクラスの、いずれのトークンバケットが承諾を決定するかおよびいずれのバケットからトークンが引き出されるかを制御し得る承諾ポリシーとの関連付けを示す図である。
【図５】要求の分類に基づいて承諾ポリシーを取得かつ適用するための実施形態を示すフローチャートである。
【図６Ａ】要求種類の複数の要求クラスへの割り振り、ならびにクラスの、要求の承諾および階層的配置のトークンバケットからのトークンの引き出しを調整する承諾ポリシーとの関連付けを示す図である。
【図６Ｂ】階層的配置のトークンバケット中の親バケットからのトークンの差し引きを示す図である。
【図６Ｃ】階層的配置のトークンバケット中の子バケットからのトークンバケットの差し引きを示す図である。
【図６Ｄ】親バケットから、その親に利用可能であるよりも多いトークンの差し引きを示す図である。
【図６Ｅ】子バケットから、子バケットまたは親バケットのいずれかに利用可能であるよりも多いトークンの差し引きを示す図である。
【図６Ｆ】同等の優先度の２つ以上のクラスが親バケットを共有する階層的配置のトークンバケットを示す図である。
【図７Ａ】要求クラス、トークンバケット、および承諾ポリシーに関する顧客提供情報を取得するためのユーザインターフェースの図示実施例を示す図である。
【図７Ｂ】階層的トークンバケットモデルを利用する手法に適合された、要求クラス、トークンバケット、および承諾ポリシーに関する顧客提供情報を取得するためのユーザインターフェースの図示実施例を示す図である。
【図８】新たなテーブルの顧客の定義と連携して容量割り当ておよび承諾ポリシー情報を受信し、ならびにその情報を用いてトークンバケットを作成し、承諾ポリシーを区分毎に適用するためのステップを示すフローチャートである。
【図９】本開示の態様が実施され得るコンピューティング環境の実施形態を示すブロック図である。
【発明を実施するための形態】
【０００５】
上述のように、プロバイダは、ＤＢＭＳをデータセンターでホストし、ＤＢＭＳへのアクセスをサービスとして種々の事業体に対して提供し得る。このことに関して、ＤＢＭＳは、ウェブサービス、ウェブアプリケーション、遠隔手続き呼び出し等を通して、公開され得る。これらのメカニズムおよび他は、本明細書ではサービスと呼ばれ得る。いくつかの実施形態では、ＤＢＭＳは、サービスのうちの１つ以上を公開する統合フロントエンドを、事業体のエンドユーザまたは顧客に提供し得る。サービスを通して、エンドユーザは、サービスに対するアプリケーションプログラミングインターフェース（「ＡＰＩ」）呼び出しを利用して、ＤＢＭＳで遂行される種々の動作および問合せを含む要求を行い得る。要求は、例えば、顧客に代わってのＡＰＩの呼び出し、ならびに顧客に代わってのＤＢＭＳでの動作の呼び出しを含み得る。
【０００６】
プロバイダはまた、この容量の使用の見返りに顧客から報酬を要求し得る。しかし、この努力の収益性は、そのために消費された容量に比例して金額を支払う顧客に依存し得る。容量消費の制限が顧客に課され、スロットリング、キューイング等の種々の技法により実施され得る。使用が顧客にプロビジョニングされた量を超過すると、顧客に代わってのサービスに対する要求は、拒絶されるまたは一時停止される場合がある。このことは、種々の状況で顧客にとって不都合であり得る。例えば、そのサービスは、電子商取引ウェブサイトまたは類似のアプリケーションの構成要素となり得、その場合当該サービスに対する要求が拒絶された場合には機能しなくなる場合がある。しかし、サービスに対する全ての要求が、顧客にとって必ずしも同等に重要であるとは限らない場合がある。電子商取引でのショッピングカートの内容の表示または顧客の注文の処理等の種々の要求は、重要度は高い場合があるが、その他についてはそうでない場合がある。例えば、比較的重要度の低いある特定の種類の要求としては、保守タスク、報告の生成、データ掘り起こし等が含まれ得る。これらのタスクはまた、図らずも比較的大きい容量部分を消費し、そのため顧客のプロビジョニングされた容量を超過したときには、停止、ブラックアウト期間、または遅延を生じやすい。
【０００７】
エンドユーザは、動作の識別子および１つ以上のパラメータを含めて要求を送信することにより、ＤＢＭＳ上に動作を呼び出し得る。任意の数の動作が識別され得、データの読み出しまたは書き込み等の操作、データでの問合せの遂行、ならびにテーブルの作成および削除等の種々のデータ定義およびスキーマ関連の命令を含み得る。要求と共に含まれ得るパラメータは、テキスト値、列挙値、整数等の、任意の種類であり得る。特定の組み合わせのパラメータは、呼び出されている動作の種類に基づいて異なることになる。
【０００８】
ＤＢＭＳは、編成された収集データを維持するためのソフトウェアおよびハードウェアシステムである。ＤＢＭＳでは、データは典型的には、キー値と追加のデータとの間の関連付けにより編成される。関連付けの性質は、収集データ中に存在する実世界の関係に基づき得るか、または任意であり得る。データ定義、問合せ、更新、および管理を含めて、種々の動作がＤＢＭＳにより遂行され得る。いくつかのＤＢＭＳは、構造化問合せ言語（「ＳＱＬ」）等の、問合せ言語を用いてデータベースとのやりとりを規定し、他は、ｐｕｔ（）およびｇｅｔ（）等の動作を含むＡＰＩを使用する。データベースとのやりとりはまた、ハイパーテキストマークアップ言語（「ＨＴＭＬ」）および拡張マークアップ言語（「ＸＭＬ」）等の、種々のプロトコルまたは標準に基づき得る。ＤＢＭＳは、データを、ソリッドステートドライブ等の１つ以上の記憶デバイスに記憶するように作用する記憶エンジン等の、種々の構築要素を含み得る。
【０００９】
プロバイダは、任意の数のＤＢＭＳをそのデータセンター内に提供し得る。ＤＢＭＳは、任意の数のコンピューティングノード上で動作し、種々の記憶デバイスに関連付けられ、様々なネットワーク設備および接続形態を用いて接続され得る。しかも、関連型データベース、オブジェクト指向データベース、無構造化問合せ言語（「ＮｏＳＱＬ」）データベース等を含めて、種々のＤＢＭＳが提供され得る。
【００１０】
上述のように、容量消費の制限が、顧客に課され得る。実施形態では、顧客は、設定された容量消費のレベルを有し得る。顧客の容量消費のレベルは、種々の推定および測定技法により制限され得る。要求の処理に関与し得る様々なコンピューティングリソースに起因して、容量消費は決定するのが困難であり得る。しかし、種々の測定可能量が、容量消費の合理的代理として機能し得る。種々の実施形態では、クライアントアプリケーションに送信されまたはそれから受信されるデータ量等の量が、特定の要求を処理することにより消費される容量を推定するために使用され得る。例えば、問合せ要求が、問合せに特定された制約に従う行を推定するために、データベーステーブルを走査し得る。返される行の数は、容量消費の代理であり得る。例えば、単一行のデータが返されれば、問合せは範囲が制限されており、したがって多数行でデータの返された問合せよりもより少ない容量しか消費しなかった可能性が高い。例となる実施形態のより詳細な事項を、図面と関連して以下に説明する。
【００１１】
上述のように、例示の実施形態では、プロバイダは、１つ以上のＤＢＭＳをデータセンター内に提供し、ウェブサービスを介して種々のＤＢＭＳへのアクセスを提供する。図１は、プロビジョニングされたウェブサービスおよびデータベースをデータセンター内でホストするための環境を示す。エンドユーザ側のアプリケーション１０２は、通信ネットワーク１０３、ゲートウェイ１０４、およびルータ１０６によりデータセンター１００内の要素に接続され得る。当業者であれば、本ネットワーク構成が本開示の実施形態に組み込まれ得る多数の可能な構成のうちの１つであることを認識するであろう。
【００１２】
ウェブサービス１１０は、データベース１１６の動作に関連する諸機能を提供する種々のＡＰＩを提供し得る。いくつかの場合では、ＡＰＩは、より複雑なデータベースインターフェースまたはプロトコル上に構築される軽量ラッパーとして機能し得る。例えば、図示のＡＰＩ１１１は、リプレゼンテーショナルステートトランスファ（「ＲＥＳＴ」）原理に従うインターフェースの使用により、データベース１１６の問合せ機能へのアクセスを提供し得る。エンドユーザ側のアプリケーション１０２は、そこで、比較的単純なＲＥＳＴ意味規則を用いて、ＡＰＩ１１１を呼び出して、データベース１１６の技術的詳細についての理解を要することなく、キー値データベースを問合せ得る。
【００１３】
ウェブサービス１１０およびデータベース１１６は、総括的にコンピューティングノードと呼び得る、１つ以上のコンピュータ、仮想マシンまたは他の形態のコンピューティングサービス等の、種々のプラットフォーム上で動作し得る。これらのノードの動作、ならびに関連する記憶デバイス、ネットワークインフラストラクチャ等は、種々の経費を伴う。これらの経費には、ハードウェアおよびソフトウェアの取得、保守、電力、要員等に関連するものが含まれる。経費には、一顧客によるリソースの消費が他人のサービスの利用を妨げるときに生じる機会経費等の要因も含み得る。
【００１４】
顧客に代わってウェブサービス１１０およびデータベース１１６により遂行される動作は、所与のコンピューティングノード上の容量の量の消費と相関し得る。この相関は、ホスト側サービスプロバイダがサービスを提供することにより生じる経費を計算するのを可能にし得る。例えば、所与の顧客がコンピューティングノードの終日に亘る容量の１００パーセントを利用するウェブサービスを呼び出す場合、サービスを提供する経費は、２４時間の期間に割り当てられるコンピューティングノードに対する取得、保守および動作の経費の合計であり得る。
【００１５】
したがって、容量の消費は、図１に示す実施形態等の種々の手段により制限され得る。承諾ポリシー１０８は、要求が処理されるべきか否かの決定を含む。大まかにいえば、承諾ポリシー１０８の目的は、顧客に代わって遂行される要求が、プロビジョニングされた量の容量を超過するのを許可されないことを確実にし得る。例えば、顧客は、コンピューティングノードの容量の２５パーセントをプロビジョニングされ得る。承諾ポリシー１０８は、そこで、その顧客の容量平均消費量を２５パーセント以下に制限するように作用する。いくつかの実施形態では、使用のピークが限定期間に当該量を上回るのを許可され得る。
【００１６】
顧客の容量が使われ過ぎたとき、承諾ポリシー１０８は入来要求を拒絶し得る。要求の性質に応じて、このことは、顧客にとって重要な結果を招き得る。例えば、顧客は、要求をデータベース１１６に向けて、エンドユーザのショッピングカートのコンテンツを取得するショッピングウェブサイトを運営し得る。要求が拒絶されると、販売完了ではなくエラーメッセージの結果となり得る。他方、いくつかの種類の要求は、重大な結果を生じることなく見合わされる。可能性がある例として、保守タスク、レポートの生成等が含まれる。したがって、承諾ポリシー１０８は、承諾または拒絶の判断をするとき、関連した要求の種類を考慮するように実施され得る。
【００１７】
実施形態は、容量消費を制限するためにトークンバケットモデルを使用し得る。トークンバケットは、概念上トークンの収集として考えることができ、トークンの各々はバケットの所有者が認可を受けて遂行する作業の単位を表す。トークンは、例えば、サービスのレベルに基づき得る蓄積速度でバケットに追加され得る。作業が遂行されると、遂行された作業量に相当する数のトークンがバケットから引き出される。トークンが得られない場合は、作業は遂行されない。この手法を用いて、遂行され得る作業量が、時間経過とともにトークンがバケットに追加される率により制限される。
【００１８】
容量の短期の過剰使用を防止するためには、バケットに追加されるトークンの最大数に制限を課すことができる。当該制限を超えて追加されるいかなるトークンも廃棄され得る。
【００１９】
データベースの動作に関連して、トークンは、データベースの動作の遂行に関連するする経費の単位を表すとみなし得る。例えば、データベース１１６で動作を行うための要求の経費は、その動作が実行されたときに返送されるデータのサイズに対応し得る。トークンで測られた場合の、動作を遂行する経費は、当該データのサイズをトークン値当たりのサイズで除算することにより決定され得る。
【００２０】
要求された動作は、少なくとも１トークンでの経費とみなされ得るが、全体経費は動作が実際に遂行された後まで分からない場合がある。一実施形態では、多くの可能な実施形態の中で、少なくとも１トークンが利用可能であるとき、要求が承諾され得る。この要求は、次いで処理され、要求の総経費が１つ以上の測定量に基づいて決定され得る。
【００２１】
図１で、トークンは、トークンバケット１１２等の仮想容器内に蓄積し得る。トークンバケットは、トークンにより表される許可容量消費量の単位と、顧客またはサービス等の事業体との間の関連付けを表すものとみなし得る。例えば、顧客がデータベース１１６上でテーブルを作成するとき、トークンバケット１１２がこのテーブル上で行われる全ての動作に関連付けられ得る。他の実施形態では、トークンバケットをテーブル区分、顧客、コンピューティングノード等に関連付け得る。
【００２２】
トークン蓄積ポリシー１１４は、トークンバケット１１２内へのトークンの追加を調整し得る。実施形態では、蓄積ポリシー１１４は、追加率および最大トークン容量を含む。例えば、ポリシーは、所与のバケットがトークンを毎秒２０の率で蓄積すべきであるが、百を超えたトークンの蓄積が許可されるべきではないことを示し得る。
【００２３】
トークンおよびトークンバケットは、種々の構造により表され得る。実施形態では、承諾ポリシー１０８、トークンバケット１１２およびトークン蓄積ポリシー１１４は、ソフトウェアライブラリ、実行可能なプログラム等の、機能性モジュールにより実現される。モジュールは、現在のトークン数、最大トークン数、蓄積速度および前回のトークン追加時間を記録することにより、トークンおよびトークンの蓄積を表し得る。要求を承諾または拒絶するか否かを決定するとき、モジュールは先ず、蓄積速度、トークンが追加された最後の時間、および現在の時間に基づいて現在のトークンの数を更新し得る。例えば、トークンバケットに対応するデータ構造を調べて容量が利用可能であるかを決定するとき、蓄積された新たなトークンの数は、蓄積速度を前回の更新から経過した時間量で乗算することにより、利用可能なトークンの計数に決定され得る。この値は、現在利用可能なトークンの計数に加算され得るが、バケットに許可された最大トークン数を超過することは許可され得ない。定期的に呼び出されるルーチンに基づくもの等の、トークンバケットを維持するための他の技法もまた可能である。
【００２４】
図２は、承諾およびトークン蓄積ポリシー適用の実施形態を示す。動作２００で開始すると共に動作２１６で終了する動作の順序として示すが、当業者であれば図示された動作は実施形態を示すように意図されたものであって、図示の動作の少なくとも一部を改変、省略、再順序付け、または並列に遂行させるようにしてもよいことを認識するであろう。
【００２５】
動作２０２で、サービスを遂行する要求が受信される。例として、要求はデータベースの問合せを含み得る。データベースの問合せの経費は、おそらくはエンドユーザに返されるデータのバイト数により測られる、問合せを行うことにより返送されるデータの量に基づいて決定され得る。
【００２６】
動作２０４は、利用可能なトークンの計数の更新を示す。実施形態では、利用可能なトークンの数は、前回の更新の時間、トークン蓄積速度、および現在の時間に基づいて調節され得る。利用可能なトークンの最大数もまた制限され得る。要求が承諾されると、現在のトークンの数からトークンが差し引かれる。しかし、種々の実施形態では現在のトークン計数が零を下回るのを許可するので、差し引きにトークンを利用し得ない場合もあり得る。動作２０６は、差し引きにトークンを利用可能であるかの決定を示す。いくつかの実施形態では、１トークンが要求を承諾するのに十分であるとみなされ得るが、他では、要求の処理により消費されるトークンの数、即ち容量、を推定するように試み得る。本明細書に用いる場合、十分なトークンまたは十分な容量という用語は、１トークン、固定数のトークン、要求を処理することにより利用されることになる容量の推定に基づくトークンの数等を指し得る。不十分なトークンしか利用し得ない場合、要求は動作２０８に示すように拒絶される。クライアントのアプリケーションおよび／または提供するサービスの顧客は、拒絶を通知され得る。
【００２７】
動作２１０は、少なくとも１トークンが利用可能であるとき、要求を承諾することを示す。動作２１２により示すように、利用可能なトークンの計数が１だけ差し引かれ、要求が処理され得る。要求が一旦処理されたら、利用可能なトークンの数は、動作２１４により示すように、要求を遂行する実際の経費に基づいて、更に下方に調節され得る。種々の実施形態では、返送されたデータの量、ＣＰＵの利用、メモリの消費、ネットワーク帯域幅の消費、等の測定基準に基づいて測定され得る。
【００２８】
図２により示される実施形態は、バケット中の現在のトークンの計数が零を下回るのを可能にする。負のトークン残高は、トークンバケットに応じた要求の承諾がされ得ないブラックアウト期間に対応し得る。ブラックアウト期間の長さは、現在の負のトークン計数およびトークン蓄積速度に依存し得る。例えば、トークン蓄積速度が１０毎秒で、利用可能なトークンの数が−１００である場合、ブラックアウト期間の長さは１０秒であり得る。
【００２９】
保守、報告、要約等を含むもの等の、特定の種類の要求は、集約的で高経費として扱われるデータであり得る。したがって、これらの種類の要求は、長いブラックアウト期間を生じるかもしれず、その時には経費は低いが重要性が高いものを含めて、いかなる要求も作動し得ない。図３Ａは、この種類の状況の例を示す。テーブル、区分、コンピューティングノード等の、特定の事業体に割り当てられた総プロビジョニングされた容量は、トークン流入３０８により表され得、その率でトークンバケット３０２にトークンが追加される。例えば、長期の保守タスク３０６は、比較的大量のトークン流出３１０を生じるデータ集約型タスクであり得る。タスクが作動される度に、トークンバケット３０２中の利用可能なトークンの数が負数に低減してブラックアウト期間が結果的に生じるような場合もあり得る。他方、問合せ要求３０４は、データ流出をほとんど要さず、比較的少量のトークン流出３１２を生じ得る。しかし、先に実行された保守タスクがブラックアウト期間を生じたかもしれず、問合せ要求は、それらが低経費であるにも拘わらず拒絶され得る。そのような状況を回避するのが好都合である。
【００３０】
図３Ｂは、プロビジョニングされた容量の２つの別個のトークンバケット３１４および３１６への割り振りを示す。トークン流入は、トークン流入３０８ａおよびトークン流入３０８ｂにより示されるように、等しく割り振られる。長期の保守タスクおよび問合せを遂行する経費は一定のままであり、したがってトークン流出率３１０および３１２は不変である。本配置は、問合せ要求が、長期の保守タスクを実行することにより阻止されるのを防止する。しかし、保守タスクは求められることはほとんどない場合がある。そうであれば、長期のタスクに予蓄された容量の多くが浪費となり得る。
【００３１】
要求の承諾は、１つより多いバケットに基づいて、１つより多いバケットから差し引かれ得るトークンに対して、決定され得る。例えば、実施形態では、要求の種類を、高、中および低の優先度に割り振り得る。高優先度の要求は任意のバケットから、中の要求は３つのバケットのうちの２つから、低優先度の要求はただ１つのバケットから引き出され得る。同様の種類の要求の範疇は、クラスとして表現され得る。これらのクラスは、承諾ポリシーに関連付けられ得る。承諾ポリシーは、要求を承諾すべきか否かを決定するためにいずれのトークンバケットが使用されるべきであるかの表示、およびトークン要求の総経費が一旦既知になったときトークンを引き出すための技法または手法を含み得る。
【００３２】
図４は、要求クラスおよび承諾ポリシーに基づいて容量を割り当てるための実施形態を示す。入来要求は、クラス「Ａ」要求４００、クラス「Ｂ」要求４０２、およびクラス「Ｃ」要求４０４等の、要求クラスに属するようにされ得る。承諾ポリシーが、このように適用されて、要求を承諾または拒絶する際にいずれのバケットを介入させるか、およびこれらのバケットからどのようにトークンを差し引くかを決定し得る。
【００３３】
各要求クラスは、承諾ポリシーに関連付けられ得る。承諾ポリシーは、トークンの使用に関する種々の論理上および手続き上のメカニズムを含む。承諾ポリシーの一態様では、要求を承諾して処理するべきか否かの決定を含む。図４を例に用いれば、ポリシー４０６は、少なくとも１つのトークンがバケット「Ｙ」４１４で利用可能であれば、クラス「Ａ」要求４００は承諾されるべきであることを特定し得る。第２のポリシー４０８は、トークンがバケット「Ｘ」４１２またはバケット「Ｙ」４１４のいずれかに存在すれば、クラス「Ｂ」要求は承諾されるべきであることを特定し得る。クラス「Ｃ」要求４０４に対する第３のポリシー４１０は、バケット「Ｘ」４１２のみに基づいて要求が承諾されるべきことを示し得る。これらの例は説明的なもので、他の多くの組み合わせも可能である。
【００３４】
実施形態では、要求は、可変のまたは事前定義されたトークン閾値に基づいて承諾され得る。一実施例は、消費され得るトークンの予測数と等しい数のトークンをバケットが有するときのみ、要求を承諾することを含む。別の実施例は、最小数のトークンを設定するために以前の経費の移動平均を使用することを含む。多数の追加の実施形態が可能である。
【００３５】
承諾ポリシーはまた、いかにしてトークンが差し引かれるかの決定を含む。要求が先ず承諾されると、１以上のトークンが、承諾の基になったバケットから差し引かれ得る。しかし、要求の総経費は、要求が少なくとも部分的に処理されるまでは知られ得ない場合がある。したがって、要求が承諾された後のある時点で、第２のトークンの差し引きが起こり得る。ポリシーは、１つ以上のバケットを差し引きの対象として特定し、またバケット間の割り振りを特定し得る。
【００３６】
実施形態では、トークンは、承諾が決定された同一のバケットから引き出され得る。例えば、要求が図４に示すバケット「Ｘ」４１２中のトークンの存在に基づいて承諾された場合、全トークン経費もまたバケット「Ｘ」４１２から差し引かれ得る。本手法を採用する１つの理由は、さもなければ、負数の利用可能なトークンを有するバケットが更に落ち込む可能性があり、そのバケットのみに専ら依存する要求に対するブラックアウト期間を引き延ばすことになることである。
【００３７】
別の実施形態は、承諾を決定するのに用いられたバケットから先ず差し引きし、次いで１つ以上の後続のバケットから差し引く。例えば、要求がバケット「Ｘ」４１２中の利用可能なトークンに基づいて許可されたら、一旦決定された総経費の一部分がバケット「Ｘ」４１２から差し引かれ得、一部分がバケット「Ｙ」４１４から差し引かれ得る。第１のバケット４１２から差し引かれる量は、利用可能なトークン計数が零等の閾値を下回るのを防止するように決定され得る。残余は、一連のバケット中の第２のバケットまたは最後のバケットから差し引かれ得、そのバケットの利用可能なトークン計数を零未満にせしめ得る。したがって、図４で、クラス「Ｂ」要求４０２を処理するためにこの手法を使用することは、バケット「Ｙ」４１４に対して利用可能なトークン計数を負にならしめ得る。しかし、バケット「Ｘ」４１２に対する計数は、クラス「Ｂ」要求４０２により負にはならないであろう。本手法は、さもなければクラス「Ｂ」要求４０２を処理することにより引き起こされ得るクラス「Ｃ」要求４０４に対するブラックアウト期間を防止し得るので、好都合である。
【００３８】
図５は、承諾ポリシーを取得かつ適用するための実施形態を示す。動作５００で開始して動作５１６で終了する動作の順序として示すが、当業者であれば図示された動作は例示であるように意図されたものであって、図示の動作の少なくとも一部を改変、省略、再順序付け、または並列に遂行させるようにしてもよいことを認識するであろう。
【００３９】
承諾ポリシーを適用するためのプロセスは、動作５０２により示すように、要求の受信を含み得る。要求が属するクラスが、次いで決定され得る。これは種々の手段を介して行われる。実施形態では、要求の呼び出しに関連付けられたＡＰＩは、クラスを識別する１つ以上のパラメータを可能とし得る。一実施例は、要求が対応するクラスを指定するテキストパラメータを含む。しかし、数値を使用して要求クラスを識別することは、種々の性能を考慮すると、好都合である。
【００４０】
いくつかの実施形態では、要求はそれらの種類に基づいて分類され得る。例えば、書き込み要求は、読み出し要求とは別個に分類され得る。他の実施形態では、要求を分析して、それらの潜在的経費を決定し、また同様の経費レベルの要求を同一のクラスに割り当てる。
【００４１】
要求のクラスは、要求パラメータに特定されたものに加えてまたはそれらに代えて、諸要因に基づき得る。例えば、所与の顧客、識別子、またはセキュリティの役割が、要求クラスに関連付けられ得る。顧客または役割は、要求が呼び出された状況から利用可能であり得、または要求中のパラメータとして特定され得る。他の可能性のある要因には、要求のソースのインターネットプロトコルアドレス、呼び出されている特定のＡＰＩ等が含まれる。加えて、構成または他のメカニズムが、分類ルールを定義付けるために使用され得る。例えば、顧客、ウェブサービス、ＡＰＩまたは他の実体に関連付けられた構成が、要求に関連付けられ得る。おそらくは構成に特定される、種々のデフォルトルール、もまた適用し得る。デフォルト値は、他の分類ルールが適用可能でないとき、適用可能である。実施形態は、デフォルト値が覆されるのを可能にする。実施形態はまた、特定のデフォルト値を、それらが覆され得ないように、固定値とすることを可能にする。
【００４２】
要求クラスが一旦決定されたら、動作５０４により示すように、対応する承諾ポリシーが受信、取得、またはさもなければアプリケーション用に準備され得る。これには、トークンを引き出し得るバケットのリスト等の、承諾ポリシーを記述したレコードへのアクセスを含む。レコードは、例えば、データベースに記憶され、符号リソース、構成ファイル等に埋め込まれ得る。いくつかの実施形態では、バケットを表す構造は、ポリシーの記述の一部であり得、換言すれば、バケットおよびポリシー定義は一体化構造を含み得る。いくつかの実施形態は、このステップを省略して、本明細書に説明された種々の技法を遂行する命令中の適合する実行パスを選択することにより適用され得る。
【００４３】
要求は、動作５０６により承諾または拒絶され得る。承諾ポリシーは、利用可能なトークンに対してチェックされることになる１つ以上のバケットを記述し得る。いくつかの実施形態では、複数のトークンまたは少なくとも閾値レベルを上回っているトークンについての基準承諾を要し得る。いくつかの実施形態では、トークン計数が負のとき、要求が許可されることを可能にし得、ポリシー記述には、下回る要求を承諾しない閾値の負値を示し得る。
【００４４】
動作５０６はまた、少なくとも１トークンを差し引くことを含む。差し引かれるトークン数は、要求が承諾されるべきか否かを決定するために使用されたトークン量と同一であり得る。このように、同一のトークンまたはトークンの組に基づいて別の要求が承諾されることになることはない。実施形態ではまた、同一のトークンまたはトークンの組に基づいて複数の要求が承諾されるのを防止するために、バケットへのアクセスを同期化させ得る。
【００４５】
承諾された後、要求は、動作５０８により示されるように処理され得る。要求の総経費は、要求の処理に少なくとも基づいて決定され得る。種々の実施形態では、サービスのクライアントに返されたデータのサイズを、使用し得る。例えば、要求がデータベースの問合せである場合、トークン経費は、問合せ実行後にクライアントに返されたデータの全サイズから導かれ得る。他の実施形態では、要求が経費決定の基礎として処理および使用される間、種々の性能測定基準を収集し得る。
【００４６】
種々の実施形態では、要求が一旦遂行されると、動作の経費を差し引き得る。このステップは、動作５１４により示すように、承諾ポリシーに従って遂行され得る。承諾ポリシーには、複数のバケットの間に分配する等の、トークン経費の差し引きや、または承諾が決定されるのに用いられたバケットからの経費の差し引きに対する種々の手法を記述し得る。種々の他のポリシーが採用され得る
【００４７】
いくつかの実施形態では、トークンバケットは階層的関係を有し得る。この手法は、優先順位付け方式を要求クラスとトークンバケットとの間の１対１のマッピングで規定するのを可能にするので、選択された承諾ポリシーの好都合な管理を可能にする。階層的トークンバケットは、トークンバケット間で親子の関係を、それぞれの最大トークン容量と共に特定することにより、好都合に規定され得る。図６Ａは、階層的トークンバケットの例を用いた実施形態を示す。２つのトークンバケットが示されている。バケット「Ｘ」６０８は、「Ｙ」６１０の親バケットであり、３０トークンの最大容量を有する。バケット「Ｙ」６１０は、親「Ｘ」６０８の子であり、５トークンの最大容量を有する。トークンは、バケット間で階層様式で共有され、子バケットはその親のトークンにアクセスすることができる。したがって、トークンバケット６０８および６１０の両方が最大容量であるとき、それらの間で共有される３０トークンが存在する。
【００４８】
図６Ａでは、クラス「Ａ」要求６００は、クラス「Ａ」ポリシー６０４の適用に基づいてバケット「Ｙ」６１０に関連付けられる。同様に、クラス「Ｂ」要求は、クラスＢポリシー６０６に基づいてバケット「Ｘ」６０８に関連付けられる。承諾ポリシーは、要求クラスとバケットとの間の１対１のマッピングを含み得、これは、要求を承諾するべきか否か、およびいずれのトークンバケット、またはバケット、からトークンを差し引くかの決定に使用され得る。承諾ポリシーはまた、要求の承諾に必要な利用可能なトークンの最小数等の、追加の要素を含み得る。非階層的手法に関して本明細書に説明する種々の方法および技法が、階層的手法にも適用され得る。
【００４９】
要求は、要求クラスに対してマッピングされたトークンバケット中の少なくとも１つのトークンの利用可能性に基づいて承諾され得る。例えば、クラス「Ａ」要求６００は、バケット「Ｙ」６１０が利用可能なトークンを有するとき、承諾され得る。同様に、クラス「Ｂ」要求６０２は、バケット「Ｘ」６０８が利用可能なトークンを有するとき、承諾され得る。いくつかの実施形態は、例えば、要求の処理の推定経費に基づいて、１より多いトークンが利用可能であることを要し得る。
【００５０】
承諾に要されるトークン（単数または複数）は、要求が処理のために承諾されたとき、差し引かれ得る。実施形態では、要求を承諾するとき、１を差し引かれ得る。残存経費は、一旦既知になれば、承諾を決定するのに用いられた同一のバケットから差し引かれ得る。
【００５１】
図６Ｂは、バケット「Ｘ」６０８から２トークンを減じる動作６５０を示す図である。バケット「Ｘ」６０８および「Ｙ」６１０の差し引き前の状態が、図中要素６５１により示され、差し引き後の状態が要素６５２により示されている。トークンがバケット「Ｘ」６０８から差し引かれた結果、２８のトークン計数となっている。「Ｙ」６１０に利用可能なトークンは、不変である。
【００５２】
図６Ｃで、動作６６０は、バケット「Ｙ」６１０から２トークンを差し引くことを示す。差し引き前の状態は、図中要素６６１で示されている。差し引き後の状態は、要素６６２により示すように、両バケット「Ｘ」６０８および「Ｙ」６１０に利用可能なトークンが２だけ差し引かれていることを示す。この手法は、利用可能なトークンを２つのバケット間で階様式で共有することを反映する。要求が子バケット中の利用可能なトークンに基づいて承諾または処理されるとき、トークンは子バケットおよびその親の各々から差し引かれ得る。加えて、種々の実施形態では、要求が承諾されるためには、トークンは両方の子バケット中およびその親の各々中で利用可能でなければならない。図６Ｃで、バケット「Ｙ」６１０およびその親バケット「Ｘ」６０８の両方が少なくとも１トークンを有するので、要求は、差し引き前の状態６６１に基づいて承諾され得る。他方、実施形態では、子バケット中に不十分なトークンしか存在しない場合であっても、要求を処理するためにバケット「Ｘ」６０８等の、親バケットを承諾する。
【００５３】
図６Ｄ中の動作６７０は、利用可能な数より多い大量のトークンをバケット「Ｘ」６０８から減じることを示す。差し引き前は、要素６７１により示すように、トークンバケット「Ｘ」６０８は、それに利用可能な３０トークンを有する。３５トークンを差し引いた後は、差し引き後状態６７２により示すように、その総数がマイナス５に減じられている。図６Ｄは、バケット「Ｙ」６１０を、差し引き後にそれに利用可能な５トークンを有しているものとして示す。承諾がバケット「Ｙ」６１０に依存する要求に対して、実施形態は、少なくとも１トークンが親バケット「Ｘ」６０８中に存在することを要し得る。したがって、これらの実施形態では、両バケット「Ｘ」６０８およびバケット「Ｙ」６１０に利用可能なトークンの数が零を上回るまで、バケット「Ｙ」６１０に依存する要求は承諾されることはないであろう。しかし、実施形態では、トークンがその親から差し引かれたときに、子バケット中のトークンの数を減少させない場合がある。実施形態では、少なくとも１トークンが子バケットの親の各々中に存在するのを依然要し得る。しかし、子のトークン計数が負になるのを防止することは、子バケットに関連付けられたサービスに対するブラックアウト期間を防止するのに役立ち得る。
【００５４】
諸要因によりブラックアウト期間の長さを決定させる要因には、子バケットおよびその親中のトークン計数が負である程度、および子および親バケットの再充填率が含まれる。例えば、図６Ｄで、バケット「Ｙ」６１０に依存する要求は、少なくとも１トークンがバケット「Ｘ」６０８およびバケット「Ｙ」６１０中両方に利用可能になるまでは、承諾され得ない。バケット「Ｘ」６０８がトークンで再充填される率は、したがって、バケット「Ｙ」６１０に依存する要求で見られるブラックアウト期間の長さに影響を及ぼし得る。しかし、バケット「Ｘ」６０８は、バケット「Ｙ」６１０に割り当てられるものより比例的に高い蓄積速度を割り当てられ得る。
【００５５】
図６Ｅは、バケット「Ｙ」６１０から、それに利用可能であるより多いトークンを差し引く動作６８０を示す。差し引き前は、バケット「Ｙ」６１０は、要素６８１に図の一部分として示すように、それに利用可能な５トークンを有する。３５トークンを差し引いた後は、バケット「Ｙ」６１０は、それに利用可能なマイナス３０トークンを有し、一方バケット「Ｘ」６０８は、マイナス５トークンのままである。この状態は、要素６８２で示され、承諾が基いとする子バケット「Ｙ」６１０から、およびその親バケット「Ｘ」６０８からの差し引きを反映する。
【００５６】
階層的トークンバケットの実施形態は、種々の技法、アルゴリズム、データ構造等を採用することができる。実施形態では、親トークンバケットに利用可能なトークンの数を追跡するために記録が使用され得る。その子に利用可能なトークン数は、その後、ルールの組、アルゴリズム等に基づいて決定され得る。例えば、子トークンバケットに利用可能なトークン数は、親トークンバケットに利用可能なトークン数、および子トークンバケットが蓄積可能なトークンの最大数に基づいて決定され得る。
【００５７】
トークンバケットの階層構造は、新たなトークンをグループとして蓄積し得る。図６Ａに示すトークンバケットを基準点として用いると、トークン蓄積速度は、バケット「Ｘ」６０８および「Ｙ」６１０を含む階層構造に関連付けられ得る。トークンを階層構造に追加したとき、両バケット「Ｘ」６０８および「Ｙ」６１０に利用可能なトークン数は、それらのそれぞれの最大値まで増加し得る。
【００５８】
図６Ｆは、２つ以上の要求クラスが同等の優先度を有するバケットを共有する場合のトークンバケットの階層的配置を示す。クラス「Ａ」要求６０００はバケット「Ｘ」６０１０に向けられ、クラス「Ｂ」要求６００２はバケット「Ｙ」６０１２に向けられ得る。親バケット「Ｐ」６００８は、１００の総容量を有し得、８０トークン毎秒の割り当てを受信するバケット「Ｘ」６０１０および２０トークン毎秒の割り当てを受信するバケット「Ｙ」６０１２に対応する。バケットの最大容量は、それらのそれぞれのトークン割り当て率と同一であり得る。
【００５９】
承諾ポリシーは、子バケットが同等の優先度を共有する図６Ｆに示す配置に対して定義付けられ得る。承諾ポリシーは、以下のように進行し得る。クラス「Ａ」要求６０００に対応する要求の着信時に、バケット「Ｙ」６０１２は、トークンの利用可能性について参照され得る。少なくとも１トークンが利用可能であれば、要求は承諾され得る。バケット「Ｙ」６０１２および親バケット「Ｐ」での利用可能なトークンの計数は、承諾時におよび再度要求の処理時に、各々減少され得る。バケット「Ｙ」６０１２に不十分なトークンしか利用可能でない場合、親バケット「Ｐ」６００８に少なくとも１トークンが存在すれば、要求は承諾され得る。トークンは、承諾時におよび再度要求の処理時に、親バケット「Ｐ」６００８から差し引かれ得る。クラス「Ｂ」要求６００２は、クラス「Ｂ」ポリシー６００６をクラス「Ａ」ポリシー６００４と同様の仕方で定義付けるクラスにより同様に処理され得、トークン割り当て率の差異に対して調節される。
【００６０】
この手法は、結果として、それらのプロビジョニングされた容量にアクセスする各クラスからの要求を含むが、兄弟バケットがそれにプロビジョニングされた容量を十分に利用していなければ、追加の容量を利用し得る。例えば、クラス「Ａ」要求６０００のみが発せられた場合、最大１００トークン毎秒がそれらを処理するために利用可能となる。作業負荷が混合され、クラス「Ａ」要求６０００が１０トークン毎秒を消費するとすれば、クラス「Ｂ」要求６００２は、最大で９０トークン毎秒を消費可能になる。
【００６１】
承諾ポリシーの態様は、提供するプロバイダの顧客により定義付けられ得る。定義は、サービスプロバイダにより提供されるユーザインターフェースとの顧客のやりとりにより遂行され得る。例えば、ウェブページが、ユーザが、クラスおよびトークンが差し引かれ得るそれぞれのバケットを定義付けることを可能にし得る。ユーザはまた、各クラスの要求に対する最小トークン量等の、種々の追加のパラメータを設定し得る。
【００６２】
種々の実施形態では、入力／出力優先順位を調整するポリシーを管理するための手段を提供し得るが、これには、例えば、要求クラス、トークンバケット、承諾ポリシー等の定義付けが含まれ得る。図７Ａで、ユーザインターフェース７００は、ホストされたデータベーステーブルの作成中にユーザに提示されるユーザインターフェースページの順序の一部を含み得る。先行ステップ７０１のユーザインターフェース部品は、提供されたデータベーステーブルを定義付けるためのユーザインターフェースウィザードの以前の箇所にナビゲートするためのボタン、ハイパーリンク、または類似の要素を表し得る。テーブル作成７０２のユーザインターフェース要素は、ユーザがパラメータをテーブル作成プロセスに供給し終えたことおよびテーブルを作成すべきことを表示し得る。図示のユーザインターフェース要素は、そのようなインターフェースを提供する手法の一般例であることを意図するもので、本開示の範囲を限定するように解するべきではない。
【００６３】
ユーザインターフェース７００は、１つ以上のポリシー定義７０４ａ、７０４ｂ、および７０４ｃを含み得るが、これらは、要求クラスとトークンを引き出し得る１つ以上のバケットとの間の関係を示すパラメータ、および可能性として承諾ポリシーの他の種々の要素を供給するために使用され得る。例えば、ポリシー定義要素７０４ａは、クラス表示７０６ａ、一次バケット表示７０８ａおよび二次バケット表示７１０ａを含み得る。クラス表示７０６ａは、クラスを記述する種々のパラメータを含み得、これにはクラス名称および１つ以上の要求の種類が含まれ得る。いくつかの実施形態では、要求クラスおよび要求の種類は提供するサービスプロバイダにより事前定義される。クラス表示７０６ｂ、一次バケット表示７０８ｂ、および二次バケット表示７１０ｂを含むポリシー定義７０４ｂ、およびクラス表示７０６ｃ、一次バケット表示７０８ｃおよび二次バケット表示７１０ｃを含むポリシー定義７０４ｃ等の、多数の追加のクラス表示が、ユーザインターフェース７００に提示され得る。
【００６４】
一次バケット要素７０８ａおよび二次バケット要素７１０ａは、承諾ポリシーの一部を含むトークンバケットを、それらのそれぞれの優先度と共に示す。例えば、７０８ａで示されるトークンバケットは、クラス表示７０６ａにより特定されたクラスに該当する要求に対する承諾判断の適用に際して最初に参照されるであろう。二次トークンバケット７１０ａにより特定されたトークンバケットは、２番目に参照されるであろう。ポリシー定義７０４ａ、７０４ｂ、および７０４ｃは同一のトークンバケット、またはトークンバケットの重複する組を指し得る。
【００６５】
図７Ｂは、階層状トークンバケットを採用した承諾ポリシーを定義付けるユーザインターフェースの図示実施形態である。ユーザインターフェース７５０は、プロセス中の他のステップにナビゲートし、かつプロセスを完了すべきことを表示するための先行ステップ７５１およびテーブル作成７５２のユーザインターフェース要素を採用するテーブル定義プロセスの一部を含み得る。
【００６６】
ユーザインターフェース７５０は、１つ以上のポリシー定義７５４ａ、７５４ｂ、および７５４ｃを含み得、これらは、顧客が承諾ポリシーおよび階層的トークンバケットを作成するためのパラメータを供給するのを可能にする。例えば、ポリシー定義７５４ａは、トークンバケットの名称を示すバケット名７５６ａのユーザインターフェース要素を含み得る。いくつかの実施形態では、これは、事前定義されたバケット名称を含むドロップボックスまたは他のユーザインターフェース要素であり得る。要求クラス７６０ａは、コンボボックス、リストボックスまたは他のユーザインターフェース要素を含み得、これらは、要求クラスを、バケット名称７５６ａにより示されたバケットに割り当てるのを可能にする。子トークンバケット７５８ａのユーザインターフェース要素は、図６Ａに示すバケット「Ｙ」６１０等の、１つ以上の子トークンバケットを特定するために使用され得る。これは、１つ以上の子トークンバケットを選択するのを可能にする、リストボックスまたは他のユーザインターフェース要素であり得る。いくつかの実施形態では、親トークンバケットは、１つ以上の子トークンバケットに代えて特定され得る。ユーザインターフェース７５０は、多数の追加のポリシー定義が定義付けられるのを可能にする。例えば、ユーザインターフェース７５０はまた、バケット名７５６ｂ、要求クラス７６０ｂ、および子バケット７５８ｂを含むポリシー定義７５４ｂ、ならびにバケット名７５６ｃ、要求クラス７６０ｃ、および子バケット７５８ｃを含むポリシー定義７５４ｃを定義付けまたは編集するためのユーザインターフェース要素を含み得る。
【００６７】
図７Ａおよび図７Ｂは、両図共、図７Ａ中の一次バケット７０８ａおよび図７Ｂ中のバケット名７５６ａ等の、トークンバケットを特定するためのユーザインターフェース要素を提供するように示されている。しかし、ユーザインターフェース７００および７５０は、トークンバケットおよび対応する要求クラスを直接または間接的に特定するための代替表現を使用し得る。例えば、ユーザインターフェース７００は、要求クラスに関連付けられ得る高、中または低優先度の選択を提示し得る。バケット間の関係は、ユーザにより選択された優先度レベルから推定され得る。同様の手法を、ユーザインターフェース７５０に採用し得る。
【００６８】
実施形態では、図７Ａおよび７Ｂに示したものと同様のユーザインターフェースを採用し得、顧客が、要求クラス、バケット、バケット間の関係等を引き続き編集するのを可能にする。一例では、テーブルの定義の変更を含む。顧客は、例えば、追加の列を加えることにより、データベーステーブルの定義に対して種々の修正を行い得る。修正されたテーブルは、異なる使用パターンに関連付けられ得る。したがって、顧客はまた、テーブルに割り当てられた容量、承諾ポリシー、バケットの数等の変更を特定し得る。関連する情報を供給するために、種々のユーザインターフェース要素またはＡＰＩを使用し得る。
【００６９】
図７Ａおよび７Ｂに示した例示のユーザインターフェースは、シッククライアント、ｎ階層または他のアーキテクチャを含む、様々な技術を使用して実現され得る。実施形態では、ホスト側プロバイダのデータセンター内で動作するウェブサーバーは、ハイパーテキストマークアップ言語（「ＨＴＭＬ」）フォームを顧客のブラウザに供する。フォームの提出時には、ホスト側プロバイダのデータセンター内のウェブサービスＡＰＩは、顧客により供給された情報の受信および処理を行う。
【００７０】
図８は、関連付けられたトークンバケットおよび承諾ポリシーでデータベーステーブルを作成するためのプロセスを示すフローチャートである。動作８００で開始し、動作８１４で終了する動作の順序として示すが、図示の動作の少なくとも一部を改変、省略、再順序付け、または並列に遂行させるようにしてもよいことが当業者により認識されるであろう。例えば、動作８０２〜８０８により示された情報は、ホスト側プロバイダデータセンターで同時に受信され得る。
【００７１】
動作８０２は、テーブル定義を示す情報の受信を示す。本開示の実施形態は、テーブル毎、または定義付けられテーブルが１つより多い区分を含む場合には区分毎に容量を割り当て得る。区分は、テーブルの細区分を含み得、その各々は１つ以上のコンピューティングノード上で動作するＤＢＭＳにより維持され得る。容量がテーブル毎または区分毎に割り当てられ得るため、承諾ポリシーおよびトークンバケットは、同様に定義付けられ得る。
【００７２】
動作８０４は、１つ以上の要求クラスを示す情報の受信を示す。これらのクラスは、例えば、図７Ａおよび７Ｂに示すもの等のユーザインターフェースを介して、ユーザにより定義付けられ得る。他の実施形態では、ホストするプロバイダは、要求クラスを事前定義し得る。実施形態では、要求クラスは「高」、「中」、および「低」のように、ラベル付けされる。
【００７３】
動作８０６は、作成されるべきバケットを示す情報の受信を示す。いくつかの実施形態では、情報にはバケットのリスティングまたは計数を含み得、他では、情報が推定され得る。例えば、要求クラスとトークンバケットとの間の１対１の対応関係が推定され得る。実施形態では、３つのトークンバケットを形成して、「高」、「中」、および「低」要求クラスに対応させ得る。
【００７４】
動作８０８では、１つ以上の承諾ポリシーを示す情報が受信され得る。この情報は、要求クラスとバケットとの間のマッピングを含み得、承諾を決定するためにバケットを参照する順番、トークンを減じる方法等を示す情報を含み得る。情報は、動作８０２〜８０６により参照された他の情報と組み合わされ得る。その情報のある特定の側面は、推定的に決定され、または動作８０２〜８０６で受信される情報の他の側面を推定するために使用され得る。例えば、いくつかの実施形態では、バケットを参照するポリシー記述は、参照したバケットが作成されるべきことを推定するために使用され得る。
【００７５】
動作８１０では、区分化方式が決定され得る。提供されるテーブルまたは他のサービスは、複数のコンピューティングノードの間で割り振られ得る。したがって、実施形態では、いくつのおよびいずれのコンピューティングノードが関与するか、ならびにテーブルにより維持されるデータの割り振りの仕方の決定等のテーブルを区分ことの他の側面を決定し得る。テーブルを含まないサービスに対して、これは、それぞれの区分により取り扱われる作業負荷の割り振りの仕方の決定を含み得る。
【００７６】
区分化方式に基づいて、容量が種々の区分またはコンピューティングノードに割り当てられ得る。顧客当たりの容量は、例えば、区分間で同等に割り振られるか、または区分またはコンピューティングノードが取り扱う予期される作業負荷の量に基づいて割り振られ得る。例えば、第１の区分がテーブルの作業負荷の４分の３を扱うと予期される場合、それには容量の４分の３が割り当てられ得る。
【００７７】
区分への顧客当たりの容量の割り当ては、トークンの全生成量のある割合の区分への割り当てを含み得る。例えば、顧客のサービス階層に少なくとも部分的に基づいて、顧客が所与のトークン量毎秒を割り当てられるべきことが、決定され得る。先の実施例を続けると、その容量の４分の３が、一つの区分またはコンピューティングノードに割り当てられ、残余の４分の１が別の区分に割り当てられ得る。これは、動作８１０により示されている。
【００７８】
区分に割り当てられた顧客当たりの容量は、動作８１２により示すように、その区分に作成されるトークンバケットに細割り当てられ得る。先の実施例を続けると、総容量の４分の３が毎秒７５トークンの率のトークン生成に対応するとすれば、毎秒７５トークンの計数が、その区分またはコンピューティングノードに関連付けられたトークンバケットに割り当てられ得る。その区分に対して３つのトークンバケットが存在するとすれば、各々には毎秒２５トークンが割り当てられ得る。
【００７９】
一旦決定されると、バケット当たりのトークン割り当て率は、トークンバケットを作成、初期化またはあるいは表現するために使用され得る。種々の実施形態では、バケットの作成は、最大トークン容量、現在の容量、トークン割り当て率、および前回の追加時間を含むレコード等の、種々のデータ構造の初期化を含み得る。多数の他の実施形態も可能である。例えば、いくつかの実施形態では、論理的に定義付けられたバケットとメモリに記憶されたデータ構造との間の１対１の対応関係は存在しない場合がある。
【００８０】
図８に示す動作はまた、更新を可能にするように適合される。例えば、動作８０２は、現存のテーブルの定義の変更を示す情報の受信を含み得る。加えて、要求クラス、バケットの定義および関係、承諾ポリシー、区分化方式等に関する情報は、それらの初期の定義に続いて受信され得、対応する事業体および関係がそれに応じて更新される。
【００８１】
図９は、本発明の態様が実施され得る分散コンピューティング環境の例を示す図である。種々のユーザ９００ａは、任意の種類のコンピューティングデバイス９０２ａ上で動作する種々のクライアントアプリケーションとやりとり可能であり、データセンター９２０内で種々のコンピューティングノード９１０ａ、９１０ｂ、および９１０ｃ上で実行されるプロセスと通信ネットワーク９０４を介して通信を行う。あるいは、クライアントアプリケーション９０２ｂは、ユーザの介入が無くても通信を行い得る。通信ネットワーク９０４は、インターネット、有線および無線のローカルエリアネットワーク、光ファイバネットワーク、衛星通信等を含む、任意の組み合わせの通信技術を含み得る。任意の数のネットワークプロトコルを採用し得る。
【００８２】
データセンター９２０内で動作するコンピューティングノード９１０ａ、９１０ｂ、および９１０ｃ上で実行されるプロセスとの通信は、ゲートウェイ９０６およびルータ９０８を介して提供され得る。多数の他のネットワーク構成もまた、採用し得る。図９には明示的に示していないが、種々の認証メカニズム、ウェブサービス層、ビジネスオブジェクトまたは他の中間層を提供して、コンピューティングノード９１０ａ、９１０ｂ、および９１０ｃ上で実行されるプロセスとの通信をとりなし得る。これらの中間層のいくつかは、それら自体、コンピューティングノードのうちの１つ以上で実行されるプロセスを含み得る。コンピューティングノード９１０ａ、９１０ｂ、および９１０ｃ、ならびにその上で実行されるプロセスはまた、ルータ９０８を介して互いに通信を行い得る。あるいは、別個の通信経路を採用し得る。いくつかの実施形態では、データセンター９２０は、追加のデータセンターと通信を行うように構成され得、コンピューティングノードおよびその上で実行されるプロセスが他のデータセンター内で動作するコンピューティングノードおよびプロセスと通信を行い得るようにする。
【００８３】
コンピューティングノード９１０ａは、１つ以上のプロセッサ９１６、１つ以上のメモリ９１８、および１つ以上の記憶デバイス９１４を備える物理的ハードウェア上に存在するように示されている。コンピューティングノード９１０ａでのプロセスは、オペレーティングシステムと連携して実行され得るか、またはそれに代えて、プロセッサ９１６、メモリ９１８または記憶デバイス９１４等の、物理的リソースと直接とやりとりをするベアメタルプロセスとして実行され得る。
【００８４】
コンピューティングノード９１０ｂ、および９１０ｃは、物理的プロセッサ、メモリおよび記憶デバイス等の、種々の物理的リソースへの共有アクセスを提供し得る仮想マシンホスト９１２上で動作するように示されている。任意の数の仮想化メカニズムを採用して、コンピューティングノードを提供し得る。
【００８５】
図９に示す種々のコンピューティングノードは、ウェブサービス、データベース管理システム、ビジネスオブジェクト、監視および診断施設等を提供するように構成され得る。コンピューティングノードは、パーソナルコンピュータ、サーバー、クラスタ化されたコンピューティングデバイス等の、種々の種類のコンピューティングリソースを指し得る。ハードウェア形態中に実現されたとき、コンピューティングノードは概して、コンピュータ可読命令を記憶するように構成された１つ以上のメモリ、および指示を読み出してそれを実行するように構成された１つ以上のプロセッサに関連付けられる。ハードウェアに基づくコンピューティングノードはまた、１つ以上の記憶デバイス、ネットワークインターフェース、通信バス、ユーザインターフェースデバイス等を備え得る。コンピューティングノードはまた、ハイパーバイザーでまたはそれ無しに実装される仮想マシン等の、仮想化コンピューティングリソース、仮想化ベアメタル環境等を包含する。作製された仮想化に基づくコンピューティングノードは、ハードウェアリソースへの仮想化アクセス、ならびに非仮想化アクセスを有する。コンピューティングノードは、オペレーティングシステム、ならびに１つ以上のアプリケーションプログラムを実行するように構成され得る。いくつかの実施形態では、コンピューティングノードはまた、ベアメタルアプリケーションプログラムを含み得る。
【００８６】
これまでの部分で記載したプロセス、方法、およびアルゴリズムの各々は、１つ以上のコンピュータまたはコンピュータプロセッサにより実行される符号モジュールによって具現化され、かつそれにより完全または部分的に自動化され得る。符号モジュールは、ハードドライブ、ソリッドステートメモリ、光ディスク、および／または同様のもの等の、任意の種類の非一時的コンピュータ可読媒体またはコンピュータ記憶デバイスに記憶される。プロセスおよびアルゴリズムは、特定用途向け回路構成に部分的または全体的に実現され得る。開示したプロセスおよびプロセスステップの結果は、例えば、揮発性または非揮発性の記憶装置等の任意の種類の非一時的コンピュータ記憶装置に、永続的にまたはそれ以外で、記憶され得る。
【００８７】
以上記載を行った種々の特徴およびプロセスは、互いに独立に使用され得るか、または種々の方法で組み合わされ得る。全ての可能な組み合わせおよび部分組み合わせが、本開示の範囲内に収まるように意図される。加えて、ある特定の方法またはプロセスブロックが、一部の実現形態では省略され得る。本明細書に記載する方法およびプロセスはまた、何らかの特定の順序にも限定されず、それに関連するブロックまたは状態は、適切な他の順序で遂行され得る。例えば、記載したブロックまたは状態は、具体的に開示した以外の順番で遂行され得、または複数のブロックまたは状態は、単一のブロックまたは状態に組み合わされ得る。例示のブロックまたは状態は、順次に、並行して、または何らかの他の様式で遂行され得る。ブロックまたは状態は、開示した例示的施形態に追加されるかまたはそれらから除去され得る。本明細書に記載する例示のシステムまたは構成要素は、記載したものとは異なって構成され得る。例えば、要素を開示した例となる実施形態に追加し、それから除去し、またはそれに対して再配置され得る。
【００８８】
種々の要素が、使用される間に、メモリまたは記憶装置に記憶させるように示されること、これらの要素またはそれらの部分がメモリ管理およびデータ完全性の目的でメモリと他の記憶デバイスとの間で転送され得ることが、また認識されるであろう。あるいは、他の実施形態では、ソフトウェアモジュールおよび／またはシステムのいくつかまたは全部が、別のデバイスのメモリで実行され、コンピュータ間通信を介して図示のコンピューティングシステムと通信し得る。更に、いくつかの実施形態では、システムおよび／またはモジュールのいくつかまたは全部は、１つ以上の特定用途向け集積回路（ＡＳＩＣ）、標準集積回路、コントローラ（例えば、適合した指示により実行され、マイクロコントローラおよび／または埋込マイクロコントローラを含む）、フィールドプログラマブルゲートアレー（ＦＰＧＡ）、複合プログラマブル論理デバイス（ＣＰＬＤ）等、を限定されずに含む、少なくとも部分的にファームウェアおよび／またはハードウェア内に等、他の方法で実現または提供され得る。モジュール、システムおよびデータ構造のいくつかまたは全部はまた、適合した接続を介して適合したドライブにより読み出され得るハードディスク、メモリ、ネットワーク、または携帯型媒体物品等の、コンピュータ可読媒体に（例えば、ソフトウェア指示または構造化データとして）記憶され得る。システム、モジュール、およびデータ構造はまた、無線に基づく媒体および有線／ケーブルに基づく媒体を含む、種々のコンピュータ可読伝送媒体で生成データ信号（例えば、搬送波の一部もしくは他のアナログまたはデジタル伝播信号として）送信され、種々の形態（例えば、単一または多重アナログ信号として、または複数の個別デジタルパケットまたはフレームとして）を取り得る。そのようなコンピュータプログラム製品は、他の実施形態で他の形態も取り得る。したがって、本発明は、他のコンピュータシステム構成で実施してもよい。
【００８９】
以上の事項は、以下の付記に鑑みて更に理解され得る。
１．データベース管理システムの容量消費を優先順位付けするためのシステムであって、
データベース管理システムを動作させるように構成された１つ以上のコンピューティングノードと、
コンピュータ可読命令を上に記憶した１つ以上のメモリであって、実行時に、システムに少なくとも
要求クラスを示す情報を含み、かつ顧客に代わって遂行される動作をデータベース管理システム上で遂行させる要求を受信させ、
複数のトークンバケットを備える１つ以上のデータ構造から、関連付けられた第１の容量表示を有する第１のトークンバケットを要求クラスに少なくとも部分的に基づいて選択させ、
第１の容量表示が顧客に代わって動作を遂行するための容量を示すことを決定させ、
動作を遂行させ、かつ
動作を遂行することにより利用された容量に少なくとも部分的に基づいて第１の容量表示を更新させる、
コンピュータ可読命令を上に記憶した１つ以上のメモリと、
を備えるシステム。
２．コンピューティングデバイスによる実行時に、システムに少なくとも、
要求クラスと第１のトークンバケットとの関連付けを示す情報を受信させる、
コンピュータ可読命令を上に記憶した１つ以上のメモリを更に備える、付記１に記載のシステム。
３．コンピューティングデバイスによる実行時に、システムに少なくとも、
動作を遂行することにより利用された容量に少なくとも部分的に基づいて、複数のトークンバケットのうちの第２のトークンバケットに関連付けられた第２の容量表示を更新させる、
コンピュータ可読命令を上に記憶した１つ以上のメモリを備える、付記１に記載のシステム。
４．コンピューティングデバイスによる実行時に、システムに少なくとも、
複数のトークンバケットのうちの第２のトークンバケットに関連付けられた第２の容量表示が、顧客に代わって動作を遂行するための容量の不足を示すことを決定させる、
コンピュータ可読命令を上に記憶した１つ以上のメモリを更に備える、付記１に記載のシステム。
５．容量消費を優先順位付けするためのコンピュータ実装方法であって、
顧客に代わって遂行される動作を１つ以上のコンピューティングノード上で遂行させる要求であって、要求クラスを示す情報を含む要求、を受信することと、
複数のデータ構造から第１の容量表示を含む第１のデータ構造を、要求クラスに少なくとも部分的に基づいて、選択することと、
第１の容量表示が、顧客に代わって動作を遂行するための１つ以上のコンピューティングノードの容量を示すことを決定することと、
動作を遂行することと、
動作を遂行するのに利用された容量に少なくとも部分的に基づいて第１の容量表示を更新することと、
を含む、方法。
６．動作は、ウェブサービス、ウェブサイト、およびデータベース管理システムのうちの１つ以上で遂行される、付記５に記載の方法。
７．要求クラスを示す情報は、パラメータを含む、付記５に記載の方法。
８．要求クラスを示す情報は、構成値を含む、付記５に記載の方法。
９．顧客識別子、セキュリティ役割、およびアプリケーションプログラミングインターフェースのうちの１つ以上を更に備える、付記５に記載の方法。
１０．要求クラスと第１の容量表示との間のマッピングを示す情報を受信すること、
を更に含む、付記５に記載の方法。
１１．複数のデータ構造からの第２の容量表示が、顧客に代わって動作を遂行するための容量の不足を示すことを決定すること、
を更に含む、付記５に記載の方法。
１２．動作を遂行するのに利用された容量に少なくとも部分的に基づいて複数のデータ構造からの第２の容量表示を更新すること、
を更に含む、付記５に記載の方法。
１３．第１の容量表示および複数のデータ構造からの１つ以上の追加の容量表示は、１つ以上のメモリ場所を、顧客に代わって動作を遂行するための容量を示す複数のデータ構造中に、共有する、  付記５に記載の方法。
１４．第１の容量表示は、１つ以上のコンピューティングノードの総容量のサブセットに対応する、付記５に記載の方法。
１５．第１の容量表示は、顧客に代わって動作を遂行するのに利用可能な容量単位の計数を含む、付記５に記載の方法。
１６．計数は、割り当てられた容量の蓄積速度に少なくとも部分的に基づいて増大される、付記１５に記載の方法。
１７．非一時的コンピュータ可読記憶媒体であって、コンピューティングデバイスよる実行時に、コンピューティングデバイスに少なくとも、
動作を１つ以上のコンピューティングノード上で遂行させる要求であって、要求クラスを示す情報を含む要求、を受信させ、
複数のデータ構造から第１の容量表示を含む第１のデータ構造を、要求クラスに少なくとも部分的に基づいて、選択させ、
第１の容量表示が処理のための動作を許可するのに十分な容量を示すことを決定させ
動作を遂行させ、かつ
第１の容量表示を、動作を遂行するために利用された容量に少なくとも部分的に基づいて更新させる、
命令を上に記憶した非一時的コンピュータ可読記憶媒体。
１８．要求クラスを示す情報は、パラメータを含む、付記１７に記載のコンピュータ可読記憶媒体。
１９．コンピューティングデバイスによる実行時に、システムに少なくとも、
複数のデータ構造のうちの第２のデータ構造が、動作を遂行するための容量の不足を示すことを決定させる、
更なる命令を上に記憶した、付記１７に記載のコンピュータ可読記憶媒体。
２０．コンピューティングデバイスによる実行時に、システムに少なくとも、
第１の容量表示が動作を遂行するための容量の不足を示すとき複数のデータ構造からの第２の容量表示を更新させる、
更なる命令を上に記憶し、更新は、動作を遂行するために利用した容量に少なくとも部分的に基づく、付記１７に記載のコンピュータ可読記憶媒体。
２１．第１の容量表示は、動作を遂行するために利用可能な容量の単位の計数を含む、付記１７に記載のコンピュータ可読記憶媒体。
２２．計数は、割り当てられた容量の蓄積速度に少なくとも部分的に基づいて増大される、付記２１に記載のコンピュータ可読記憶媒体。
２３．容量消費を優先順位付けするためのシステムであって、
１つ以上のコンピューティングノードと、
コンピュータ可読命令を上に記憶した１つ以上のメモリであって、コンピューティングデバイスによる実行時に、システムに少なくとも、
１つ以上の要求クラスを示す情報を受信させ、
１つ以上の要求クラスと第１の容量表示を備えた１つ以上のデータ構造との間のマッピングを示す情報を受信させ、
１つ以上のコンピューティングノード上で動作を遂行するための総容量のサブセットを、第１の容量表示に割り当てさせ、かつ
第１の容量表示が動作を１つ以上のコンピューティングノード上で遂行するために利用可能な容量を示すことを決定したとき動作を遂行させる、
コンピュータ可読命令を上に記憶した１つ以上のメモリと、
を備える、システム。
２４．コンピュータ可読命令を上に記憶した１つ以上のメモリであって、コンピューティングデバイスによる実行時に、システムに少なくとも、
顧客に代わってデータベーステーブルを作成するための指示を示す情報を受信させる
コンピュータ可読命令を上に記憶した１つ以上のメモリを更に備える、付記２３に記載のシステム。
２５．コンピュータ可読命令を上に記憶した１つ以上のメモリであって、コンピューティングデバイスによる実行時に、システムに少なくとも、
データベーステーブルを修正するための指示を示す情報を受信させ、かつ
データベーステーブルに割り当てられた容量を修正するための指示を示す情報を受信させる、
コンピュータ可読命令を上に記憶した１つ以上のメモリを更に備える、付記２３に記載のシステム。
２６．コンピュータ可読命令を上に記憶した１つ以上のメモリであって、コンピューティングデバイスによる実行時に、システムに少なくとも、
データベーステーブルの区分の数に少なくとも部分的に基づいて総容量のサブセットを決定させる
コンピュータ可読命令を上に記憶した１つ以上のメモリを更に備える、付記２４に記載のシステム。
２７．コンピュータ可読命令を上に記憶した１つ以上のメモリであって、コンピューティングデバイスによる実行時に、システムに少なくとも、
顧客に入力を承諾させるための命令を含むユーザインターフェース命令を送信させる、
コンピュータ可読命令を上に記憶した１つ以上のメモリを更に備える、付記２３に記載のシステム。
【００９０】
とりわけ、「ｃａｎ」、「ｃｏｕｌｄ」、「ｍｉｇｈｔ」、「ｍａｙ」、「ｅ．ｇ．」等の、本明細書に使用する条件付言い回しは、他に具体的に述べない限り、またはさもなければ使用する前後関係内で理解されない限り、ある特定の特徴、要素および／またはステップをある特定の実施形態が含むが、他の実施形態は含まないことを伝えるように概して意図される。したがって、そのような条件付言い回しは、特徴、要素および／またはステップが、如何様にも１つ以上の実施形態に必要とされること、または１つ以上の実施形態が、これらの特徴、要素および／またはステップが含まれるのかまたは任意の特定の実施形態で遂行されるのかを判断するための論理を必然的に含むことを暗示するようには概して意図されない。「備える（ｃｏｍｐｒｉｓｉｎｇ）」、「含む（ｉｎｃｌｕｄｉｎｇ）」、「有する（ｈａｖｉｎｇ）」等の用語は、同義であり、制約無く包括的に使用され、追加の要素、特徴、作用、動作等を排除しない。また、「または（ｏｒ）」という用語は、その包括的な意味に（かつその排他的意味にではなく）使用され、例えば、要素の一覧を接続するとき、用語「または（ｏｒ）」はその一覧中の要素のうちの１つ、いくつか、または全てを意味する。
【００９１】
ある特定の例となる実施形態を記載したが、これらの実施形態は例として提示したのであり、本明細書に開示した発明の範囲を限定するようには意図されない。したがって、これまでの記載中に何らかの特定の特長、特性、ステップ、モジュール、またはブロックが必要または不可欠であることを暗示するように意図されるものはない。実際、本明細書に記載した新規な方法およびシステムは、様々な他の形態に具体化され得、更に、本明細書に記載した方法およびシステムの形態での種々の省略、置き換え、および変更を、本明細書に開示する本発明の趣旨から逸脱することなく行い得る。添付の特許請求の範囲およびそれらの均等物は、本明細書に記載した本発明の特定の範囲および趣旨内に収まるであろう場合、そのような形態または変形例にも及ぶように意図される。
【図１】
0006584388.tif 000002
【図２】
0006584388.tif 000003
【図３Ａ】
0006584388.tif 000004
【図３Ｂ】
0006584388.tif 000005
【図４】
0006584388.tif 000006
【図５】
0006584388.tif 000007
【図６Ａ】
0006584388.tif 000008
【図６Ｂ】
0006584388.tif 000009
【図６Ｃ】
0006584388.tif 000010
【図６Ｄ】
0006584388.tif 000011
【図６Ｅ】
0006584388.tif 000012
【図６Ｆ】
0006584388.tif 000013
【図７Ａ】
0006584388.tif 000014
【図７Ｂ】
0006584388.tif 000015
【図８】
0006584388.tif 000016
【図９】
0006584388.tif 000017