(57)【要約】  本システムおよび方法の実施形態は、現在の技法に比べメモリ使用量および複雑さを削減し、計算の複雑さを抑え、ならびにリシャッフルしなければならないキー数を比較的少数とするコンシステント・ハッシュ関数を提供することができる。例えば、一実施形態では、計算リソースを制御するためのコンピュータ実施方法が、実リソースに割り振られたワーキング・リソースの複数のラベルと、割り振られるように使用可能な予約リソースの複数のラベルとを含む潜在的リソースのラベルのセットを記憶することと、潜在的リソースのラベルのセットのうちの１つのラベルへの初期割当てを生成することと、潜在的リソースのラベルのセットのうちの１つのラベルへの割当てが、予約リソースのラベルのうちの１つのラベルへの割当てであるときに、リクエストを、潜在的リソースのラベルのサブセットから選択されたリソースの別のラベルに再割当てすることと、リクエストがワーキング・リソースのラベルに割り当てられるまで、再割当てすることを繰り返すこととを含むことができる。
2021530060.tif 000002
【特許請求の範囲】
【請求項１】
計算リソースを制御するためのコンピュータ実施方法であって、
実リソースに割り振られたワーキング・リソースの複数のラベルと、割り振られるように使用可能な予約リソースの複数のラベルとを含む潜在的リソースのラベルのセットを記憶することと、
潜在的リソースのラベルの前記セットのうちの１つのラベルへの初期割当てを生成することと、
潜在的リソースのラベルのセットのうちの１つのラベルへの前記割当てが、予約リソースの前記ラベルのうちの１つのラベルへの割当てであるときに、リクエストを、潜在的リソースの前記ラベルのサブセットから選択されたリソースの別のラベルに再割当てすることと、
前記リクエストがワーキング・リソースのラベルに割り当てられるまで、前記再割当てすることを繰り返すことと
を含む方法。
【請求項２】
前記サブセットが、ワーキング・リソースの前記複数のラベルと、予約リソースの前記ラベルのうち、リソースの現在割り当てられているラベルを境界とする部分とを含む、請求項１に記載の方法。
【請求項３】
リソースの前記別のラベルが、潜在的リソースのラベルの前記セットまたは潜在的リソースのラベルの前記サブセットからランダムに選択される、請求項２に記載の方法。
【請求項４】
実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することによって前記実リソースを除去することをさらに含み、前記実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することが、潜在的リソースのラベルの記憶された前記セットの中のワーキング・リソースの最後のラベルを示すレンジ値を減らして、前記リソースに割り振られた除去される前記ラベルを排除することにより実行される、請求項１に記載の方法。
【請求項５】
実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することによって前記実リソースを除去することをさらに含み、前記実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することが、
前記除去の前に、前記除去の前のワーキング・リソースの最後のラベルを、除去される前記リソースに割り振られた前記ラベルの代わりにして、潜在的リソースのラベルの前記セットを記憶することと、
潜在的リソースのラベルの記憶された前記セットの中のワーキング・リソースの最後のラベルを示すレンジ値を減らして、除去される前記リソースに割り振られた前記ラベルを排除することと
により実行される、請求項１に記載の方法。
【請求項６】
実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することによって前記実リソースを除去することをさらに含み、前記実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することが、
前記除去の前の最後のワーキング・リソースのラベルを、除去される前記リソースに割り振られた前記ラベルの代わりとなるように移動させ、除去される前記リソースに割り振られた前記ラベルの代わりとなった前記リソースの前記ラベルだけを記憶することと、
潜在的リソースのラベルの記憶された前記セットの中の最後のワーキング・リソースのラベルを示すレンジ値を減らすことと
により実行される、請求項１に記載の方法。
【請求項７】
最後に除去されたリソースのラベルの除去を元に戻し、元に戻された前記ラベルを、追加される実リソースに割り振ることによって前記実リソースを追加することをさらに含む、請求項１に記載の方法。
【請求項８】
潜在的リソースのラベルの前記セットが、前記潜在的リソースのうちの少なくともいくつかの潜在的リソースに対する複数のラベルを含み、それぞれの潜在的リソースに対するいくつかのラベルが、前記潜在的リソースに与えられた重みを含む、請求項１に記載の方法。
【請求項９】
計算リソースを制御するためのシステムであって、前記システムが、プロセッサと、前記プロセッサによってアクセス可能なメモリと、前記メモリに記憶されたコンピュータ・プログラム命令とを含み、前記コンピュータ・プログラム命令が、
実リソースに割り振られたワーキング・リソースの複数のラベルと、割り振られるように使用可能な予約リソースの複数のラベルとを含む潜在的リソースのラベルのセットを記憶することと、
潜在的リソースのラベルの前記セットのうちの１つのラベルへの初期割当てを生成することと、
潜在的リソースのラベルのセットのうちの１つのラベルへの前記割当てが、予約リソースの前記ラベルのうちの１つのラベルへの割当てであるときに、リクエストを、潜在的リソースの前記ラベルのサブセットから選択されたリソースの別のラベルに再割当てすることと、
前記リクエストがワーキング・リソースのラベルに割り当てられるまで、前記再割当てすることを繰り返すことと
を実行するように、前記プロセッサによって実行可能である、システム。
【請求項１０】
前記サブセットが、ワーキング・リソースの前記複数のラベルと、予約リソースの前記ラベルのうち、リソースの現在割り当てられているラベルを境界とする部分とを含む、請求項９に記載のシステム。
【請求項１１】
リソースの前記別のラベルが、潜在的リソースのラベルの前記セットまたは潜在的リソースのラベルの前記サブセットからランダムに選択される、請求項１０に記載のシステム。
【請求項１２】
実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することによって前記実リソースを除去することをさらに含み、前記実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することが、潜在的リソースのラベルの記憶された前記セットの中のワーキング・リソースの最後のラベルを示すレンジ値を減らして、前記リソースに割り振られた除去される前記ラベルを排除することにより実行される、請求項９に記載のシステム。
【請求項１３】
実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することによって前記実リソースを除去することをさらに含み、前記実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することが、
前記除去の前に、前記除去の前のワーキング・リソースの最後のラベルを、除去される前記リソースに割り振られた前記ラベルの代わりにして、潜在的リソースのラベルの前記セットを記憶することと、
潜在的リソースのラベルの記憶された前記セットの中のワーキング・リソースの最後のラベルを示すレンジ値を減らして、除去される前記リソースに割り振られた前記ラベルを排除することと
により実行される、請求項９に記載のシステム。
【請求項１４】
実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することによって前記実リソースを除去することをさらに含み、前記実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することが、
前記除去の前の最後のワーキング・リソースのラベルを、除去される前記リソースに割り振られた前記ラベルの代わりとなるように移動させ、除去される前記リソースに割り振られた前記ラベルの代わりとなった前記リソースの前記ラベルだけを記憶することと、
潜在的リソースのラベルの記憶された前記セットの中の最後のワーキング・リソースのラベルを示すレンジ値を減らすことと
により実行される、請求項９に記載のシステム。
【請求項１５】
最後に除去されたリソースのラベルの除去を元に戻し、元に戻された前記ラベルを、追加される実リソースに割り振ることによって前記実リソースを追加することをさらに含む、請求項９に記載のシステム。
【請求項１６】
潜在的リソースのラベルの前記セットが、前記潜在的リソースのうちの少なくともいくつかの潜在的リソースに対する複数のラベルを含み、それぞれの潜在的リソースに対するいくつかのラベルが、前記潜在的リソースに与えられた重みを含む、請求項９に記載のシステム。
【請求項１７】
計算リソースを制御するためのコンピュータ・プログラム製品であって、前記コンピュータ・プログラム製品が、プログラム命令が具現化された非一過性コンピュータ可読ストレージを含み、前記プログラム命令が、
実リソースに割り振られたワーキング・リソースの複数のラベルと、割り振られるように使用可能な予約リソースの複数のラベルとを含む潜在的リソースのラベルのセットを記憶することと、
潜在的リソースのラベルの前記セットのうちの１つのラベルへの初期割当てを生成することと、
潜在的リソースのラベルのセットのうちの１つのラベルへの前記割当てが、予約リソースの前記ラベルのうちの１つのラベルへの割当てであるときに、リクエストを、潜在的リソースの前記ラベルのサブセットから選択されたリソースの別のラベルに再割当てすることと、
前記リクエストがワーキング・リソースのラベルに割り当てられるまで、前記再割当てすることを繰り返すことと
を含む方法をコンピュータに実行させるように、前記コンピュータによって実行可能である、コンピュータ・プログラム製品。
【請求項１８】
前記サブセットが、ワーキング・リソースの前記複数のラベルと、予約リソースの前記ラベルのうち、リソースの現在割り当てられているラベルを境界とする部分とを含む、請求項１７に記載のコンピュータ・プログラム製品。
【請求項１９】
リソースの前記別のラベルが、潜在的リソースのラベルの前記セットまたは潜在的リソースのラベルの前記サブセットからランダムに選択される、請求項１８に記載のコンピュータ・プログラム製品。
【請求項２０】
実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することによって前記実リソースを除去することをさらに含み、前記実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することが、潜在的リソースのラベルの記憶された前記セットの中のワーキング・リソースの最後のラベルを示すレンジ値を減らして、前記リソースに割り振られた除去される前記ラベルを排除することにより実行される、請求項１７に記載のコンピュータ・プログラム製品。
【請求項２１】
実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することによって前記実リソースを除去することをさらに含み、前記実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することが、
前記除去の前に、前記除去の前のワーキング・リソースの最後のラベルを、除去される前記リソースに割り振られた前記ラベルの代わりにして、潜在的リソースのラベルの前記セットを記憶することと、
潜在的リソースのラベルの記憶された前記セットの中のワーキング・リソースの最後のラベルを示すレンジ値を減らして、除去される前記リソースに割り振られた前記ラベルを排除することと
により実行される、請求項１７に記載のコンピュータ・プログラム製品。
【請求項２２】
実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することによって前記実リソースを除去することをさらに含み、前記実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することが、
前記除去の前の最後のワーキング・リソースのラベルを、除去される前記リソースに割り振られた前記ラベルの代わりとなるように移動させ、除去される前記リソースに割り振られた前記ラベルの代わりとなった前記リソースの前記ラベルだけを記憶することと、
潜在的リソースのラベルの記憶された前記セットの中の最後のワーキング・リソースのラベルを示すレンジ値を減らすことと
により実行される、請求項１７に記載のコンピュータ・プログラム製品。
【請求項２３】
最後に除去されたリソースのラベルの除去を元に戻し、元に戻された前記ラベルを、追加される実リソースに割り振ることによって前記実リソースを追加することをさらに含む、請求項１７に記載のコンピュータ・プログラム製品。
【請求項２４】
潜在的リソースのラベルの前記セットが、前記潜在的リソースのうちの少なくともいくつかの潜在的リソースに対する複数のラベルを含み、それぞれの潜在的リソースに対するいくつかのラベルが、前記潜在的リソースに与えられた重みを含む、請求項１７に記載のコンピュータ・プログラム製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、処理の初期分散（initial distribution of processing）を用いるコンシステント・ハッシング技法（consistent hashing technique）を使用してオブジェクトまたは処理タスクの分散を実行するための技法に関する。
【背景技術】
【０００２】
分散処理に関係する１つの問題は、オブジェクトまたは処理タスク（キー）を、それらのオブジェクトおよびタスクの記憶もしくは処理またはその両方を実行するために使用可能なリソース（バケット）間で分散することである。従来のシステムは、従来のハッシュ関数を使用してキーを分散することがある。例えば、オブジェクトまたはタスクのハッシュを生成し、次いでバケットの数の底（base）に対する法（modulus）を見つけ、それに従って分散することがある。この状況では、バケットを追加または除去する場合、全てのキーまたはほぼ全てのキーを再分散しなければならない。
【０００３】
コンシステント・ハッシュ関数として知られている特殊なハッシュ関数を使用することによって、バケットの数が変化したときに再分散しなければならないキーを大幅に減らすことができる。例えば、既存のコンシステント・ハッシュ関数は、キーを、バケットのセットにマップすることがある。従来のハッシュ関数と同様に、キー・セット（例えばウェブ・リクエスト）は非常に大きいことがあり、また、均等に分散されないことがあり、その一方で、バケット・セット（例えばウェブ・サーバの集団）は有限であることがある。ハッシュ関数は、決定論的に（deterministically）、キーをバケット間で均等に分散することができる。従来のハッシングとは異なり、既存のコンシステント・ハッシングは、バケットのセットが変化したとき（例えばウェブ・サーバが追加または除去されたとき）のマッピング変更（「リシャッフリング（reshuffling）」と呼ばれる）を最小にする。既存のコンシステント・ハッシングは多くの用途を有し、ウェブ・キャッシング、ストレージ、インメモリ・キャッシュ、分散ハッシュ・テーブルなどの基礎をなす。
【０００４】
従来のハッシュ関数および実施態様は、既存のコンシステント・ハッシュ関数、既存のランデブー（rendezvous）・コンシステント・ハッシュ関数、既存のジャンプ（jump）・コンシステント・ハッシュ関数、既存のＧｏｏｇｌｅ（Ｒ）  Ｍａｇｌｅｖハッシュ関数、および既存の順列ベースの（permutation-based）ハッシュ関数など、いくつかある。これらの関数および実施態様はそれぞれ利点および欠点を有する。しかしながら、典型的な欠点には、高いメモリ使用量および複雑さ、高度に複雑な計算、ならびにリシャッフルしなければならない比較的多数のキー数が含まれることがある。
【０００５】
現在の技法に比べメモリ使用量および複雑さを削減し、計算の複雑さを抑え、ならびにリシャッフルしなければならないキー数を比較的少数とするコンシステント・ハッシュ関数を実施する技法が求められている。
【発明の概要】
【０００６】
本システムおよび方法の実施形態は、現在の技法に比べメモリ使用量および複雑さを削減し、計算の複雑さを抑え、ならびにリシャッフルしなければならないキー数を比較的少数とするコンシステント・ハッシュ関数を提供することができる。
【０００７】
例えば、一実施形態では、計算リソース（computing resource）を制御するためのコンピュータ実施方法は、実リソース（actual resource）に割り振られたワーキング・リソース（working resource）の複数のラベルと、割り振られるように使用可能な予約リソース（reserved resource）の複数のラベル（label）とを含む潜在的リソースのラベルのセットを記憶することと、潜在的リソースのラベルのセットのうちの１つのラベルへの初期割当てを生成することと、潜在的リソースのラベルのセットのうちの１つのラベルへの割当てが、予約リソースのラベルのうちの１つのラベルへの割当てであるときに、リクエストを、潜在的リソースのラベルのサブセットから選択されたリソースの別のラベルに再割当てすることと、リクエストがワーキング・リソースのラベルに割り当てられるまで、再割当てすることを繰り返すこととを含むことができる。
【０００８】
実施形態では、サブセットは、ワーキング・リソースの複数のラベルと、予約リソースのラベルのうち、リソースの現在割り当てられているラベルを境界とする部分とを含むことができる。リソースの別のラベルは、潜在的リソースのラベルのセットまたは潜在的リソースのラベルのサブセットからランダムに選択され得る。この方法は、リソースに割り振られたラベルをワーキング・リソースのラベルから除去することによって実リソースを除去することをさらに含むことができ、リソースに割り振られたラベルを除去することは、潜在的リソースのラベルの記憶されたセットの中のワーキング・リソースの最後のラベルを示すレンジ（range）値を減らして（decrement）、リソースに割り振られた除去されるラベルを排除することにより実行される。この方法は、リソースに割り振られたラベルをワーキング・リソースのラベルから除去することによって実リソースを除去することをさらに含むことができ、リソースに割り振られたラベルを除去することは、除去の前に、除去の前のワーキング・リソースの最後のラベルを、除去されるリソースに割り振られたラベルの代わりにして、潜在的リソースのラベルのセットを記憶することと、潜在的リソースのラベルの記憶されたセットの中のワーキング・リソースの最後のラベルを示すレンジ値を減らして、除去されるリソースに割り振られたラベルを排除することとにより実行される。この方法は、リソースに割り振られたラベルをワーキング・リソースのラベルから除去することによって実リソースを除去することをさらに含むことができ、リソースに割り振られたラベルを除去することは、除去の前の最後のワーキング・リソースのラベルを、除去されるリソースに割り振られたラベルの代わりとなるように移動させ、除去されるリソースに割り振られたラベルの代わりとなったリソースのラベルだけを記憶することと、潜在的リソースのラベルの記憶されたセットの中の最後のワーキング・リソースのラベルを示すレンジ値を減らすこととにより実行される。この方法は、最後に除去されたリソースのラベルの除去を元に戻し（undo）、元に戻されたラベルを、追加される実リソースに割り振ることによって実リソースを追加することをさらに含むことができる。潜在的リソースのラベルのセットは、潜在的リソースのうちの少なくともいくつかの潜在的リソースに対する複数のラベルを含むことができ、それぞれの潜在的リソースに対するいくつかのラベルは、潜在的リソースに与えられた重みを含むことができる。
【０００９】
一実施形態では、計算リソースを制御するためのシステムは、プロセッサと、プロセッサによってアクセス可能なメモリと、メモリに記憶されたコンピュータ・プログラム命令とを含むことができ、コンピュータ・プログラム命令は、実リソースに割り振られたワーキング・リソースの複数のラベルと、割り振られるように使用可能な予約リソースの複数のラベルとを含む潜在的リソースのラベルのセットを記憶することと、潜在的リソースのラベルのセットのうちの１つのラベルへの初期割当てを生成することと、潜在的リソースのラベルのセットのうちの１つのラベルへの割当てが、予約リソースのラベルのうちの１つのラベルへの割当てであるときに、リクエストを、潜在的リソースのラベルのサブセットから選択されたリソースの別のラベルに再割当てすることと、リクエストがワーキング・リソースのラベルに割り当てられるまで、再割当てすることを繰り返すこととを実行するように、プロセッサによって実行可能である。
【００１０】
一実施形態では、計算リソースを制御するためのコンピュータ・プログラム製品は、プログラム命令が具現化された非一過性コンピュータ可読ストレージを含むことができ、プログラム命令は、実リソースに割り振られたワーキング・リソースの複数のラベルと、割り振られるように使用可能な予約リソースの複数のラベルとを含む潜在的リソースのラベルのセットを記憶することと、潜在的リソースのラベルのセットのうちの１つのラベルへの初期割当てを生成することと、潜在的リソースのラベルのセットのうちの１つのラベルへの割当てが、予約リソースのラベルのうちの１つのラベルへの割当てであるときに、リクエストを、潜在的リソースのラベルのサブセットから選択されたリソースの別のラベルに再割当てすることと、リクエストがワーキング・リソースのラベルに割り当てられるまで、再割当てすることを繰り返すこととを含む方法をコンピュータに実行させるように、コンピュータによって実行可能である。
【００１１】
本発明の詳細は、その構造と動作の両方に関して、添付図面を参照することによって最もよく理解することができる。添付図面中、同様の参照符号および呼称は同様の要素を指す。
【図面の簡単な説明】
【００１２】
【図１】記載された実施形態を実施することができる例示的なシステムを示す図である。
【図２】本技法に含まれる処理の一実施形態の例示的な流れ図である。
【図３】本技法に含まれる記憶技法の一実施形態の例示的な図である。
【図４ａ】本技法に含まれる処理の一実施形態の例示的な図である。
【図４ｂ】本技法に含まれる処理の一実施形態の例示的な図である。
【図４ｃ】本技法に含まれる処理の一実施形態の例示的な図である。
【図５】本明細書に記載された実施形態に含まれる処理を実施することができるコンピュータ・システムの例示的なブロック図である。
【発明を実施するための形態】
【００１３】
本システムおよび方法の実施形態は、現在の技法に比べて低いメモリ使用量および複雑さ、低い計算の複雑さ、ならびにリシャッフルしなければならない比較的少数のキー数を提供するコンシステント・ハッシュ関数を提供することができる。
【００１４】
実施形態では、本技法が、いくつかの単純な（通常はコンシステントでない）ハッシュ関数による、バケットの「仮定的な」より大きなセットへの初期マッピングから始まることができる。この関数は、アンカー分散関数（anchor distribution function）と呼ばれることがある。この初期アンカー分散は、任意のハッシュまたは任意の分散によって実行することができる。アンカー・セットが十分には大きくなく、アンカー・セットを超えてバケットが追加される場合には、ハッシュ関数、例えばジャンプ・ハッシュ関数またはその一般化を利用することができる。例えば、ジャンプ・コンシステント・ハッシングの手法の幅広い一般化であるコンシステント・ハッシュ関数を使用することができる。この例では、キーがリマップ（remap）される（リシャッフルされる）前に、何個のバケットを追加または除去する必要があるのかを繰り返し計算することによって、マップされるバケットを選ぶことができる。アンカー分散から開始することにより、計算の複雑さは、バケットの全数よりもむしろ、アンカー・バケット・セットと現在のバケット・セットとの間の差異に関係する。このことは、（故障したサーバの代わりにサーバが追加される典型的なケースなど）アンカー・セットに近い方のバケット・セットの変更が、計算の複雑さを増大させない可能性があることを意味する（実際、このような変更は、計算の複雑さを低下させることがある）。さらに、ジャンプ・コンシステント・ハッシングとは異なり、バケット・セットへの任意の（故障による）除去および追加が許されることがある。この例のメモリ必要量は、変更回数程度であり、計算の複雑さはほとんど不変である。例えば、アンカー・セットの１０％までの除去に関して、予想される繰返し回数は１０／９よりも小さく、アンカー・セットの５０％までの除去に関して、予想される繰返し回数は２よりも小さい。順序付けられた（ordered）変更の特別なケースに関しては、メモリ使用量が不変であることがある。
【００１５】
本システムおよび方法の技法を実施することができるシステム１００の例示的なブロック図が図１に示されている。この例では、システム１００が、複数のオブジェクトもしくはタスクまたはその両方１０２Ａ〜Ｎ、ハッシュ関数１０４、複数のキー１０６Ａ〜Ｎ、オブジェクト／タスク分散ブロック１０８および複数のリソース１１０Ａ〜Ｚを含む。オブジェクトもしくはタスクまたはその両方１０２Ａ〜Ｎは、データ・ファイル、トランザクション、実行可能ファイルなど、記憶リソース（バケット）にマップし、割り振り、または割り当てることができる複数の計算オブジェクトを含むことができる。オブジェクトもしくはタスクまたはその両方１０２Ａ〜Ｎは、実行中の処理、実行される処理など、処理リソースにマップし、割り振り、または割り当てることができる、複数の計算タスクを含むことができる。リソース１１０Ａ〜Ｚは、オブジェクトもしくはタスクまたはその両方１０２Ａ〜Ｎがマップされ、割り振られ、または割り当てられる、複数の記憶リソースもしくは処理リソースまたはその両方を含むことができる。例えば、リソース１１０Ａ〜Ｚは、計算もしくは記憶またはその両方を実行するサーバ、記憶リソース、ネットワーク・リソースなどを含むことができる。本技法は、ストレージ・コントローラ、分散キャッシュ、ウェブ・キャッシュ、キー値ストレージならびに組込みシステム（embedded system）、例えばハードウェア・ルータおよびスイッチなどの任意のタイプの計算リソースに適用可能である。たとえこれらのデバイスのアーキテクチャが異なる可能性がある場合であっても、本技法は、そのようなデバイスに有利に適用することができる。ハッシュ関数１０４は、オブジェクトもしくはタスクまたはその両方１０２Ａ〜Ｎに対するハッシュ・キー１０６Ａ〜Ｎを生成することができる１つまたは複数のハッシュ関数および処理を含むことができる。オブジェクト／タスク分散ブロック１０８は、生成されたハッシュ・キー１０６Ａ〜Ｎに基づいて、リソース１１０Ａ〜Ｚへのオブジェクトもしくはタスクまたはその両方１０２Ａ〜Ｎのマッピング、割振りまたは割当てを分散することができる。
【００１６】
本技法に含まれる処理２００の例示的なデータ流れ図が図２に示されている。この例では、この処理が擬似コードの形態で示されている。コンシステント・ハッシュ・アルゴリズムを実施する本システムおよび方法の実施形態は、最小の混乱特性（minimal disruption property）およびバランスを達成することに加えて、ワーキング・バケット・セットに対する動的な、しばしば構造化されていない変更をサポートすることができる。このような変更は、偶発バケット故障などの予期しない事象もしくは保守などの標準的な事前操作（standard proactive operation）によって、またはある所与のポリシーに従ってシステムをスケールアップもしくはスケールダウンするときに実施されることがある。
【００１７】
本システムおよび方法の実施形態は、バケットのいくつかのセットを利用することができる。そのような１つのセットは、「ワーキング・セット」と呼ばれることがあり、ワーキング・セットは「Ｗ」２０３で示される。ワーキング・セットは、所与の時点で使用されているバケットのセットを含む。別のセットは、「アンカー・セット」と呼ばれることがある。アンカー・セットは、最初に使用されているバケット・セット、すなわち初期ワーキング・セットＷよりも大きなバケット・セットである。アンカー・セットは「Ａ」２０２で示されることがある。このような実施形態は、ワーキング・バケット・セットＷに対して高速で任意の変更（fast and arbitrary change）を実行することができ、その一方で、アンカー・セット・サイズに対する感応性（sensitivity）をほとんど示さない。別のセットは、「予約セット」と呼ばれることがあり、予約セットは「Ｒ」２０４で示される。上述のとおり、本システムおよび方法は、いつでも、ワーキング・セットＷ⊂Ａよりも大きなバケット・セットＡと共に機能することができる。Ｒは、Ｒ＝Ａ＼Ｗと定義することができる。
【００１８】
セットＲ内では後入れ先出し（ＬＩＦＯ）順序を維持することができる。したがって、Ｒに入れられた最後に除去されたバケットが、バケット追加時にＲを出る最初のバケットになる。他の実施形態を使用することもできるが、この実施形態は、効率的な実施態様を提供することができる。この実施形態では、バケット追加時に、システムが、システムの以前の状態、すなわち最後のバケット除去前の状態に戻る。これによって、メモリ使用量を低減させることができ、優れた性能を提供することができる。
【００１９】
それぞれのキーを、アンカー・セット内のパス（path）、例えばアンカー・セットの順序付けられたサブセットに関連づけることができ、そのパスの最後のホップ（hop）は、そのキーが入れられるバケットである。この最後のホップは、パスに沿った最初のワーキング・バケットである。最初に、それぞれのキーに関して、このパスは、初期予約バケットを含んでいることまたは含んでいないことがあり、このパスは、最初の初期ワーキング・バケットで終わる。２０１で、アンカー・セットＡ２０２のバケットのうちの１つのバケットにそれぞれのキーを均等に分散することによって、キーの初期分散を実行することができる。２０５〜２０７で、それぞれのライブ（live）・キーをワーキング・バケット・セット上にプッシュすることができる。初期バケット配列の一例が図３に示されている。
【００２０】
ライブ・バケットを除去するための処理２０９が、図２の２１０〜２１２に示されている。この処理では、図３に示されたバケット１５などのワーキング・バケット・セットＷ２０３の最後のバケットを、予約バケット・セットＲ２０４に移動させる。ライブ・バケットを追加するための処理２１４が、図２の２１５〜２１７に示されている。この処理では、図３に示されたバケット１６などの予約バケット・セットＲ２０４の最初のバケットを、ワーキング・バケット・セットＷ２０３に移動させる。
【００２１】
新たなバケットｂが２１４で追加されたとき、すなわち、新たなバケットｂが予約セットからワーキング・セットに移動したときには、ｂを含んでいたいくつかのキー・パスが短くされており、ｂのところでより早期に終わる。同様に、バケットｂが２０９で除去されたときには、以前はｂで終わっていたそれぞれのキーのパスが延長されており、このようなパスに対する新たな（そして最後の）ホップが、（適切なハッシュ関数を使用して）存続するワーキング・セットの中で均等に選ばれている。
【００２２】
キーのアンカー・パス上のそのキーの最初のホップを決定するための処理２１９が、図２の２２０〜２２３に示されている。入力するキーに適用された最初のハッシュが、そのキーのアンカー・パス上のキーの最初のホップを決定する。この最初のハッシュは、初期設定処理２０１によって生み出されたものなどのアンカー・セットの全体にわたって均等とすることができる。しかしながら、入力するキーが最初に予約バケットにハッシュされる状況が生じることもある。ライブ・バケットが見つかるまで、アンカー・セットの厳密に減少するサブセット（strictly decreasing subset）に対してキーを繰り返しハッシュすることができる。この処理は、初期ケースとバケットが動的に除去（または追加）されたケースの両方に適用することができる。これは、初期ケースを、初期予約セットが既に除去されたバケットを含むケースとみなすことができるためである。これらは順序付けられた除去であり、そのため再列挙する必要はなく、新たな状態情報はほとんどなく、ただ現在長だけであることに留意されたい。この処理のメモリ効率は、順序付けられた除去に関しては（たとえランダムな除去と混在する場合であっても）非常に高いことがあるため、この処理は、アンカー・セットＡとワーキング・セットＷの間の差異に対する感応性がより低いことがある。計算的探索労力（computational lookup effort）はＡ／Ｗのログに関係し、計算的労力の感応性もあまり高くないことがある。したがって、多くの追加をサポートするために大きなアンカー・セットを使用することができる。同様に、後述するように、多数のバックエンド・サーバ／リソースまたは重みを有するバックエンド・サーバ／リソースをサポートするために、大きなワーキング・セットを使用することができる。
【００２３】
このケースでは、処理２１９を使用することができる。例えば、実行時にバケットが除去されたときには、除去されたバケットにマップされていたキーだけを別のバケットにリマップすることによって、コンシステンシー（consistency）を維持することができる。図３では、例えば処理２１９の２２０でハッシュ関数「２４（アンカー・セット２０２のサイズ）＊ｒａｎｄｏｍ（ｓｅｅｄ＝ｋ）＝２１」を使用することによって、キーが、３０１のバケット２１への初期ハッシュを得ることができる。３０１のバケット２１は、例えば以前に除去されたためにワーキング・セットＷ２０３の中にないため、次いで、２２１〜２２２で、例えば２２２でハッシュ関数「２１（直前の繰返しからのバケット）＊ｒ．ｎｅｘｔ（）＝１６」を使用することによって、ハッシングをもう１回繰り返すことができる。この繰返しによって３０２のバケット１６が得られ、このバケットは、例えば以前に除去されたために、まだワーキング・セットＷ２０３の中にない。２２１〜２２２で、１６（直前の繰返しからのバケット）＊ｒ．ｎｅｘｔ＝１１を使用することによって、別の繰返しを実行することができる。この繰返しは３０３のバケット１１を与え、このバケットはワーキング・セットＷ２０３の中にある。ワーキング・バケットが選択されると繰返しは停止する。これに応じて、２２３で、割り当てられたバケットにおいて３０３のバケット１１が返される。
【００２４】
バケットが除去されるときに限り（「パス」）、ますます小さなセットに対してバケットの選択を繰り返すことによって、コンシステンシーを維持することができる。コンシステンシーを維持する処理の一実施形態の例４００が図４ａに示されている。この例では、アンカー・セットＡ＝｛１，２，．．．，７｝、初期ワーキング・セットＷ＝｛１，２，．．．，５｝である。図４ａに示された処理は、これらのセットを保存すること、および簡単なランダム選択のためにそれらを列挙することに関する。初期（「自然」）列挙（enumeration）が行４０２に示されている。この例のこの単純な（naive）実施態様は、毎回、セット（行）全体を保存するが、それでも再列挙を最小化する。実行時にバケットが除去されたときには、除去されたバケットにマップされていたキーだけを別のバケットにリマップすることによって、コンシステンシーを維持することができる。例えば、行４０２においてバケット７が除去されたときには（順序付けられた除去）、新たな行４０４を保存することができる。バケット７が除去され、存続するバケットは不変であるため、再列挙は必要ない。順序付けられていない（unordered）除去またはランダムな除去が実行されたときには、再列挙が必要となることがある。例えば、行４０８では、バケット２が（例えば故障のために）除去されている。その以前の列挙「５」は存続するセットよりも大きいため、バケット５だけを再列挙すればよい。その新たな列挙は「２」であり、これは、行４０８に対するランダム選択がアイテム＃２を選んだ場合には、バケット５が使用されることを意味する。この例には、バケット７、６、２、４、次いで５の連続する除去が示されており、バケット６および７は初期設定中に除去される。この例において、７、６および４の除去は順序付けられた除去であり、２および５の除去は順序付けられていない除去である。
【００２５】
コンシステンシーを維持する処理の一実施形態の例４５０が図４ｂに示されている。この実施形態では、除去が順序付けられているときに、バケットの新たな状態を新たな行にコピーする必要がなく、むしろ、バケットのレンジ（最後のバケットまたはバケットの数）が減らされる同じ行を使用することができる。したがって、その行を維持することができ、最後のワーキング・バケットはレンジ情報によって示される。例えば、図４ｂに示されているように、初期設定で、値順序を低減させることによって予約バケットが入れられる場合、これらの全てのバケットは、対応する減少するレンジを有する最初の行４５２を指すことができる。
【００２６】
除去されるバケットが、直前に除去されたバケットによって観察された最後のバケットでない場合、そのバケット除去は順序付けられていない。このような除去が実行されたときには新たな行を生成することができ、この行では、除去されたバケットの位置に直前の行の最後のエントリが割り当てられていてもよい。例えば、行４５２においてバケット２が除去されることがある。バケット２によって空になった位置に行４５２の最後のワーキング・バケットであるバケット５が割り当てられた新たな行４５４を生成することができ、ワーキング・バケット・レンジを減らすことができる。図４ａと同様に、その以前の列挙「５」は存続するセットよりも大きいため、バケット５だけを再列挙すればよい。その新たな列挙は「２」であり、これは、行４５４に対するランダム選択がアイテム＃２を選んだ場合には、バケット５が使用されることを意味する。この例には、バケット７、６、２、４、次いで５の連続する除去が示されており、バケット６および７は初期設定中に除去される。この例において、７、６および４の除去は順序付けられた除去であり、２および５の除去は順序付けられていない除去である。
【００２７】
順序付けられた除去を図４ｂに示されているように利用することにより、特に初期設定において、例えば大きな予約セットを含む初期設定において、メモリ使用量を減らすことができ、または、実行時にシステムをスケーリングするとき、例えばサーバ／リソースが意図的に除去されるときには、サーバ／リソースを順番に除去することができる。
【００２８】
コンシステンシーを維持する処理の一実施形態の例４７０が図４ｃに示されている。この実施形態では、除去が順序付けられているときに、バケットの新たな状態を新たな行にコピーする必要がなく、むしろ、バケットのレンジ（最後のバケットまたはバケットの数）が減らされる同じ行を使用することができる。したがって、その行を維持することができ、最後のワーキング・バケットはレンジ情報によって示される。例えば、図４ｃに示されているように、初期設定で、値順序を低減させることによって予約バケットが入れられる場合、これらの全てのバケットは、対応する減少するレンジ４７３を有する最初の行４７２を指すことができる。順序付けられていない除去に関しては、それらの初期列挙から変更されたバケットだけ、例えば図４ｃのバケット５および３だけを保存／コピーすることによって、メモリ使用量をよりいっそう低減させることができる。
【００２９】
この技法は、偶発故障を処理するために状態が保存される手法において非常に効率的であることがある。具体的には、一般的なスケールダウン事象によるものなどの順序付けられた除去およびアンカー・セットからの初期設定「除去」など、最後のサーバ／リソースが除去される場合には、（除去自体の識別以外は）新たな状態を保存する必要がない。それぞれの偶発故障または順序付けられていない故障に関しては、少数のエントリだけをコピーすればよい。最初に、バケットを、それらのＩＤによって列挙することができる。バケット故障時には、この列挙を、バケットの最小セットに対してのみ、変更することができ、これによってリシャッフリングを最小化することができる。偶発故障に限り列挙の変更が必要となり、せいぜい１つの変更で済むため、現在の状態として保存される列挙変更の総数を偶発故障の数よりも少なくすることができる。さらに、状態変更の数も、偶発故障の総数よりも少なくすることができる。ランダムな除去は通常、予定に入れられておらず、修復され再追加されるか、または交換サーバ／リソースが使用される。除去を「忘れる」ことによってサーバ／リソースを追加することができるため、状態は、総数よりはむしろ、ランダムな除去の「正味の」数に関係する。
【００３０】
例えば、図４ｃでは、行４７２からバケット２が除去されたときに、新たな行４７４を生成することができ、この行では、行４７２の最後のワーキング・バケットであるバケット５が、バケット２によって空になった位置に割り当てられていてもよく、ワーキング・バケット・レンジが減らされていてもよい。その以前の列挙「５」は存続するセットよりも大きいため、バケット５だけを再列挙すればよい。同様に、存続するバケットの割当ては行４７２から得ることができるため、行４７４にはバケット５だけを記憶すればよい。その新たな列挙は「２」であり、これは、行４７４に対するランダム選択がアイテム＃２を選んだ場合には、バケット５が使用されることを意味する。この例には、バケット７、６、２、４、次いで５の連続する除去が示されており、バケット６および７は初期設定中に除去される。この例において、７、６および４の除去は順序付けられた除去であり、２および５の除去は順序付けられていない除去である。同様に、バケット５が除去されたときには、新たな行４７４を生成することができ、この行では、行４７２の最後のワーキング・バケットであるバケット３が、バケット５によって空になった位置に割り当てられていてもよく、ワーキング・バケット・レンジが減らされていてもよい。
【００３１】
除去操作を事実上、元に戻し、そのバケット（ラベル）を、直前に除去されたリソースから新たに追加されたリソースに再割当てすることによって、リソースを追加することができる。除去されたラベル（バケット）は「ランダム」であり、故障のためにリソースを除去する必要があることがあるが、追加されるリソース・ラベルはランダムである必要はなく、処理は、使用されていない任意のラベルを選ぶことができる。バケットは、バックエンド・サーバまたは他のリソースでないことに留意すべきである。むしろ、（コンシステント）ハッシュはキーをバケットにマップし、次いでそれらのバケットは、サーバ／リソースにマップされる。これは、バケット識別が完全に制御可能であることを意味する。
【００３２】
例えば、図４ａにおいてバケットが追加される場合、単純にワーキング・バケット・レンジを増やす（increment）ことにより、最後のワーキング・バケットの次の予約バケットを使用し、その予約バケットをワーキング・セットに移動させることができる。したがって、図４ａの行４０６においてバケットを追加する場合には、最後に除去されたバケットであるバケット６  ４１６を、ワーキング・セットに再び追加することができる。同様に、図４ｂの行４５２では、行４５２のレンジ情報をバケット６を含むように更新することによって、バケット６をワーキング・セットに再び追加することができる。
【００３３】
別の例として、図４ａの行４１２は、何回かの順序付けられた除去および順序付けられていない除去の結果、生成されたものである。ワーキング・バケット・レンジを増やすことにより、最後のワーキング・バケットの次の予約バケットを使用することによって、行４１２にバケットを追加することができる。このケースでは、まだ使用されていない任意のバケットを、ワーキング・バケット・レンジに追加するバケットとして選択することができる。同様に、ワーキング・バケット・レンジを増やすことにより、図４ｂの行４５６および図４ｃの行４７６にバケットを追加することができる。これらの例では、まだ使用されていない任意のバケットを、ワーキング・バケット・レンジに追加するバケットとして選択することができる。
【００３４】
本システムおよび方法では、（何回の追加／除去動作が実行されたかに関わらず）サーバ／リソースの数はあまり変化しないため、最終状態は初期状態に非常に近くなる。さらに、ランダムな除去に予め備える必要はない。このケースでは、準備において状態をコピーすることができるが、除去のための余分の計算は、除去が実行されるときだけ、および除去されるバケットが実際に選択されたときだけ必要である。サーバ／リソースを追加することによって、計算的労力を低減させることができ、保存された状態を除去することができる。
【００３５】
予約バケットおよびワーキング・バケットの数は、過大な計算オーバヘッドまたはメモリ・オーバヘッドなしに大きくなることがあるため、実施形態では、それぞれのサーバまたは他のリソースに２つ以上のバケットを割り当てることができる。さらに、さまざまなサーバまたは他のリソースの計算パワーもしくは記憶容量またはその両方は異なることがあるため、それぞれのサーバまたは他のリソースに割り当てられるバケットの数も異なることがある。これは、それぞれのサーバまたは他のリソースの分散に希望に応じて重み付けする機能を提供することができる。さらに、バケットの総数は非常に大きくなることがあるため、重み付けの粒度を非常に細かくすることができる。例えば、平均的なサーバまたは他のリソースを１０個のバケットに割り当てることができ、よりパワーの大きなサーバ／リソースを２０個のバケットに割り当てることができ、よりパワーの小さいサーバ／リソースを５つのバケットに割り当てることができる。より細かい粒度が所望である場合、同じサーバ／リソースをそれぞれ１００、２００および５００個のバケットに割り当てることができる。実際の割当て、重み付けおよび粒度は、希望に応じて調整することができる。
【００３６】
本明細書に記載された実施形態に含まれる処理を実施することができるコンピュータ・システム５０２の例示的なブロック図が図５に示されている。コンピュータ・システム５０２は、組込みプロセッサ、チップ上のシステム、パーソナル・コンピュータ、ワークステーション、サーバ・システムおよびミニコンピュータもしくはメインフレーム・コンピュータなどの１つもしくは複数のプログラムされた汎用コンピュータ・システムを使用して、またはネットワーク化された分散計算環境で実施することができる。コンピュータ・システム５０２は、１つまたは複数のプロセッサ（ＣＰＵ）５０２Ａ〜５０２Ｎ、入力／出力回路５０４、ネットワーク・アダプタ５０６およびメモリ５０８を含むことができる。ＣＰＵ５０２Ａ〜５０２Ｎは、本通信システムおよび方法の機能を実行するためにプログラム命令を実行する。通常、ＣＰＵ５０２Ａ〜５０２Ｎは、ＩＮＴＥＬ  ＣＯＲＥ（Ｒ）プロセッサなどの１つまたは複数のマイクロプロセッサである。図５は、メモリ５０８、入力／出力回路５０４およびネットワーク・アダプタ５０６などのシステム・リソースを多数のプロセッサ５０２Ａ〜５０２Ｎが共有する単一のマルチプロセッサ・コンピュータ・システムとしてコンピュータ・システム５０２が実施された一実施形態を示している。しかしながら、本通信システムおよび方法は、シングルプロセッサ・コンピュータ・システム、マルチプロセッサ・コンピュータ・システムまたはこれらの混成システムとすることができるネットワーク化された複数のコンピュータ・システムとしてコンピュータ・システム５０２が実施された実施形態も含む。
【００３７】
本技法は、ストレージ・コントローラ、分散キャッシュ、ウェブ・キャッシュ、キー値ストレージならびに組込みシステム、例えばハードウェア・ルータおよびスイッチなどの任意のタイプの計算リソースに適用可能である。たとえこれらのデバイスのアーキテクチャが異なる可能性がある場合であっても、本技法は、そのようなデバイスに有利に適用することができる。
【００３８】
入力／出力回路５０４は、コンピュータ・システム５０２にデータを入力し、またはコンピュータ・システム５０２からデータを出力する機能を提供する。例えば、入力／出力回路は、キーボード、マウス、タッチパッド、トラックボール、スキャナ、アナログ−ディジタル変換器などの入力デバイス、ビデオ・アダプタ、モニタ、プリンタなどの出力デバイス、およびモデムなどの入力／出力デバイスを含むことができる。ネットワーク・アダプタ５０６は、デバイス５００とネットワーク５１０とをインタフェースする。ネットワーク５１０は、限定はされないがインターネットを含む、公衆または専有ＬＡＮまたはＷＡＮとすることができる。
【００３９】
メモリ５０８は、コンピュータ・システム５０２の機能を実行するためにＣＰＵ５０２Ａ〜５０２Ｎによって実行されるプログラム命令、ならびにコンピュータ・システム５０２の機能を実行するためにＣＰＵ５０２Ａ〜５０２Ｎによって使用および処理されるデータを記憶している。メモリ５０８は例えば、ランダム・アクセス・メモリ（ＲＡＭ）、リードオンリ・メモリ（ＲＯＭ）、プログラマブル・リードオンリ・メモリ（ＰＲＯＭ）、電気的に消去可能なプログラマブル・リードオンリ・メモリ（ＥＥＰＲＯＭ）、フラッシュ・メモリなどの電子式メモリ・デバイス、および磁気ディスク・ドライブ、テープ・ドライブ、光ディスク・ドライブなどの電気機械式メモリを含むことができ、電気機械式メモリは、インテグレーテッド・ドライブ・エレクトロニクス（ＩＤＥ）インタフェースまたはその変形物もしくは拡張物、例えばエンハンストＩＤＥ（ＥＩＤＥ）またはウルトラダイレクト・メモリ・アクセス（ＵＤＭＡ）、もしくはスモール・コンピュータ・システム・インタフェース（ＳＣＳＩ）ベースのインタフェースまたはその変形物もしくは拡張物、例えばファストＳＣＳＩ、ワイドＳＣＳＩ、ファスト・アンド・ワイドＳＣＳＩなど、もしくはシリアル・アドバンスト・テクノロジ・アタッチメント（ＳＡＴＡ）またはその変形物もしくは拡張物、またはファイバ・チャネル・アービトレーテッド・ループ（ＦＣ−ＡＬ）インタフェースを使用することができる。
【００４０】
メモリ５０８の内容は、それを実行するようにコンピュータ・システム５０２がプログラムされた機能に応じて異なっていてもよい。図５に示された例には、上で説明した処理の実施形態のためのルーチンおよびデータを表す例示的なメモリ内容が示されている。しかしながら、それらのルーチンはそれらのルーチンに関係したメモリ内容と共に、１つのシステムまたはデバイス上に含まれていなくてもよく、むしろ、工学技術上のよく知られた配慮に基づいて複数のシステムまたはデバイス間で分散されていてもよいことを当業者は認識していよう。本通信システムおよび方法はそのような全ての構成を含むことができる。
【００４１】
実施形態では、図５に示されたソフトウェアの少なくとも一部分を、現在の先端サーバ（current leader server）上で実施することができる。同様に、実施形態では、図５に示されたソフトウェアの少なくとも一部分を、現在の先端サーバ以外のコンピュータ・システム上で実施することもできる。
【００４２】
図５に示された例では、メモリ５０８が、ハッシュ関数ルーチン５１２、分散ルーチン５１４、キー・データ５１６、分散データ５１８およびオペレーティング・システム５２０を含むことができる。ハッシュ関数ルーチン５１２は、分散する対象であるオブジェクトもしくはタスクまたはその両方に対するハッシュ・キーを生成するためのソフトウェア・ルーチンを含むことができ、ハッシュ・キーは、キー・データ５１６として記憶することができる。分散ルーチン５１４は、オブジェクトもしくはタスクまたはその両方を、リソース間で、例えば図２および３に示された処理に従って、分散するためのソフトウェア・ルーチンを含むことができる。分散データ５１８は、図２および３に関して上で説明したデータなど、分散ルーチン５１４によって使用されるデータを含むことができる。オペレーティング・システム５２０は、システム機能全般を提供することができる。
【００４３】
図５に示されているように、本通信システムおよび方法は、マルチプロセッサ、マルチタスキング、マルチプロセスもしくはマルチスレッド計算、またはこれらの組合せを提供する１つまたは複数のシステム上での実施態様、およびシングル・プロセッサ、シングル・スレッド計算だけを提供するシステム上での実施態様を含むことができる。マルチプロセッサ計算は、２つ以上のプロセッサを使用して計算を実行することを含む。マルチタスク計算は、２つ以上のオペレーティング・システム・タスクを使用して計算を実行することを含む。タスクは、実行されているプログラムとオペレーティング・システムによって使用される管理情報（bookkeeping information）との組合せを指すオペレーティング・システムの概念である。プログラムが実行されるときはいつでも、オペレーティング・システムは、そのプログラムに対して新たなタスクを生成する。このタスクは、タスク番号によってそのプログラムを識別し、そのプログラムに他の管理情報を付加するという点で、そのプログラムの封筒のようなものである。Ｌｉｎｕｘ、ＵＮＩＸ（Ｒ）、ＯＳ／２（Ｒ）およびＷｉｎｄｏｗｓ（Ｒ）を含む多くのオペレーティング・システムが、多くのタスクを同時に走らせることができ、それらのシステムはマルチタスキング・オペレーティング・システムと呼ばれている。マルチタスキングは、２つ以上の実行ファイル（executable）を同時に実行するオペレーティング・システムの能力である。それぞれの実行ファイルは、その実行ファイル自体のアドレス空間で走っており、このことは、実行ファイルが、その実行ファイルのメモリを共有する手段を持たないことを意味する。どのプログラムも、システム上で走っている他のプログラムの実行に損害を与えることがないため、このことは有利である。しかしながら、プログラムは、オペレーティング・システムを通すこと（またはファイル・システム上に記憶されたファイルを読むこと）を除いて、情報を交換する手段を持たない。いくつかの動作システムはマルチプロセス計算とマルチタスク計算を区別するが、タスクという用語とプロセスという用語はしばしば相互に交換可能に使用されるように、これら２つの計算は似ている。
【００４４】
本発明は、インテグレーションの可能な技術的詳細レベルにおいて、システム、方法もしくはコンピュータ・プログラム製品、またはこれらの組合せであることができる。コンピュータ・プログラム製品は、本発明の諸態様をプロセッサに実行させるためのコンピュータ可読プログラム命令をその上に有するコンピュータ可読記憶媒体を含むことができる。このコンピュータ可読記憶媒体は、命令実行デバイスが使用するための命令を保持および記憶することができる有形のデバイスとすることができる。
【００４５】
このコンピュータ可読記憶媒体は例えば、限定はされないが、電子記憶デバイス、磁気記憶デバイス、光学記憶デバイス、電磁気記憶デバイス、半導体記憶デバイスまたはこれらの適当な組合せとすることができる。コンピュータ可読記憶媒体のより具体的な例の非網羅的なリストは、ポータブル・コンピュータ・ディスケット、ハード・ディスク、ランダム・アクセス・メモリ（ＲＡＭ）、リードオンリ・メモリ（ＲＯＭ）、消去可能なプログラマブル・リードオンリ・メモリ（ＥＰＲＯＭまたはフラッシュ・メモリ）、スタティック・ランダム・アクセス・メモリ（ＳＲＡＭ）、ポータブル・コンパクト・ディスク・リードオンリ・メモリ（ＣＤ−ＲＯＭ）、ディジタル・バーサタイル・ディスク（ＤＶＤ）、メモリ・スティック、フロッピー（Ｒ）・ディスク、パンチカードまたはその上に命令が記録された溝の中の一段高くなった構造体などの機械的にコード化されたデバイス、およびこれらの適当な組合せを含む。本明細書で使用されるコンピュータ可読記憶媒体は、電波もしくは他の自由に伝搬する電磁波、ウェーブガイドもしくは他の伝送体内を伝搬する電磁波（例えば光ファイバ・ケーブル内を通る光パルス）、または電線を通して伝送される電気信号などの、それ自体が一過性の信号であると解釈されるべきではない。
【００４６】
本明細書に記載されたコンピュータ可読プログラム命令は、コンピュータ可読記憶媒体から対応するそれぞれの計算／処理デバイスにダウンロードすることができ、またはネットワーク、例えばインターネット、ローカル・エリア・ネットワーク、ワイド・エリア・ネットワークもしくは無線ネットワークまたはそれらの組合せを介して外部コンピュータまたは外部記憶デバイスにダウンロードすることができる。このネットワークは、銅伝送ケーブル、光伝送ファイバ、無線伝送、ルータ、ファイアウォール、スイッチ、ゲートウェイ・コンピュータもしくはエッジ・サーバ、またはこれらの組合せを含んでもよい。それぞれの計算／処理デバイス内のネットワーク・アダプタ・カードまたはネットワーク・インタフェースは、コンピュータ可読プログラム命令をネットワークから受け取り、それらのコンピュータ可読プログラム命令を、対応するそれぞれの計算／処理デバイス内のコンピュータ可読記憶媒体に記憶するために転送する。
【００４７】
本発明の動作を実行するためのコンピュータ可読プログラム命令は、アセンブラ命令、命令セット・アーキテクチャ（ＩＳＡ）命令、機械語命令、機械依存命令、マイクロコード、ファームウェア命令もしくは状態設定データ、集積回路用の構成データであってもよく、またはＳｍａｌｌｔａｌｋ（Ｒ）、Ｃ＋＋または他の同種のものなどのオブジェクト指向プログラミング言語、および「Ｃ」プログラミング言語または同種のプログラミング言語などの手続き型プログラミング言語を含む、１つまたは複数のプログラミング言語の任意の組合せで書かれた、ソース・コードもしくはオブジェクト・コードであってもよい。このコンピュータ可読プログラム命令は、全体がユーザのコンピュータ上で実行されてもよく、一部がユーザのコンピュータ上で実行されてもよく、独立型ソフトウェア・パッケージとして実行されてもよく、一部がユーザのコンピュータ上で、一部が遠隔コンピュータ上で実行されてもよく、または全体が遠隔コンピュータもしくはサーバ上で実行されてもよい。上記の最後のシナリオでは、遠隔コンピュータが、ローカル・エリア・ネットワーク（ＬＡＮ）もしくはワイド・エリア・ネットワーク（ＷＡＮ）を含む任意のタイプのネットワークを介してユーザのコンピュータに接続されてもよく、またはこの接続が、外部コンピュータに対して（例えばインターネット・サービス・プロバイダを使用してインターネットを介して）実施されてもよい。いくつかの実施形態では、本発明の諸態様を実施するために、例えばプログラム可能論理回路、フィールドプログラマブル・ゲート・アレイ（ＦＰＧＡ）またはプログラマブル論理アレイ（ＰＬＡ）を含む電子回路が、このコンピュータ可読プログラム命令の状態情報を利用してその電子回路を個別化することにより、このコンピュータ可読プログラム命令を実行してもよい。
【００４８】
本明細書では、本発明の諸態様が、本発明の実施形態に基づく方法、装置（システム）およびコンピュータ・プログラム製品の流れ図もしくはブロック図またはその両方の図を参照して説明される。それらの流れ図もしくはブロック図またはそれらの両方の図のそれぞれのブロック、およびそれらの流れ図もしくはブロック図またはその両方の図のブロックの組合せは、このコンピュータ可読プログラム命令によって実施することができることが理解される。
【００４９】
これらのコンピュータ可読プログラム命令は、コンピュータまたは他のプログラム可能データ処理装置のプロセッサによって実行される命令が、流れ図もしくはブロック図またはその両方の図の１つまたは複数のブロックに指定された機能／動作を実施する手段を生成するように、汎用コンピュータ、専用コンピュータまたは他のプログラム可能データ処理装置のプロセッサに提供されてマシンを作り出すものであってよい。これらのコンピュータ可読プログラム命令はさらに、命令が記憶されたコンピュータ可読記憶媒体が、流れ図もしくはブロック図またはその両方の図の１つまたは複数のブロックに指定された機能／動作の態様を実施する命令を含む製造物品を含むように、コンピュータ可読記憶媒体に記憶され、コンピュータ、プログラム可能データ処理装置もしくは他のデバイスまたはこれらの組合せに特定の方式で機能するように指示することができるものであってもよい。
【００５０】
コンピュータ可読プログラム命令はさらに、コンピュータ、他のプログラム可能装置または他のデバイス上で実施される命令が、流れ図もしくはブロック図またはその両方の図の１つまたは複数のブロックに指定された機能／動作を実施するように、コンピュータによって実施されるプロセスを生み出すために、コンピュータ、他のプログラム可能データ処理装置または他のデバイス上にロードされ、コンピュータ、他のプログラム可能装置または他のデバイス上で一連の動作ステップを実行させるものであってもよい。
【００５１】
図中の流れ図およびブロック図は、本発明のさまざまな実施形態に基づくシステム、方法およびコンピュータ・プログラム製品の可能な実施態様のアーキテクチャ、機能および動作を示す。この点に関して、それらの流れ図またはブロック図のそれぞれのブロックは、指定された論理機能を実施する１つまたは複数の実行可能命令を含む、モジュール、セグメントまたは命令の部分を表すことがある。いくつかの代替実施態様では、ブロックに示された機能を、図に示された順序とは異なる順序で実施することができる。例えば、連続して示された２つのブロックが、実際は、実質的に同時に実行されることがあり、または、含まれる機能によってはそれらのブロックが逆の順序で実行されることもある。それらのブロック図もしくは流れ図またはその両方の図のそれぞれのブロック、ならびにそれらのブロック図もしくは流れ図またはその両方の図のブロックの組合せを、指定された機能もしくは動作を実行しまたは専用ハードウェアとコンピュータ命令の組合せを実施するハードウェアベースの専用システムによって実施することができることにも留意すべきである。
【００５２】
本発明の特定の実施形態を説明したが、説明した実施形態と等価の他の実施形態が存在することを当業者は理解するであろう。したがって、本発明は、例示された特定の実施形態によっては限定されず、添付の特許請求の範囲によってのみ限定されることを理解すべきである。
【図１】
2021530060.tif 000003
【図２】
2021530060.tif 000004
【図３】
2021530060.tif 000005
【図４ａ】
2021530060.tif 000006
【図４ｂ】
2021530060.tif 000007
【図４ｃ】
2021530060.tif 000008
【図５】
2021530060.tif 000009
【手続補正書】
【提出日】令和3年5月19日(2021.5.19)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
計算リソースを制御するためのコンピュータ実施方法であって、
実リソースに割り振られたワーキング・リソースの複数のラベルと、割り振られるように使用可能な予約リソースの複数のラベルとを含む潜在的リソースのラベルのセットを記憶することと、
潜在的リソースのラベルの前記セットのうちの１つのラベルへの初期割当てを生成することと、
潜在的リソースのラベルのセットのうちの１つのラベルへの前記割当てが、予約リソースの前記ラベルのうちの１つのラベルへの割当てであるときに、リクエストを、潜在的リソースの前記ラベルのサブセットから選択されたリソースの別のラベルに再割当てすることと、
前記リクエストがワーキング・リソースのラベルに割り当てられるまで、前記再割当てすることを繰り返すことと
を含む方法。
【請求項２】
前記サブセットが、ワーキング・リソースの前記複数のラベルと、予約リソースの前記ラベルのうち、リソースの現在割り当てられているラベルを境界とする部分とを含む、請求項１に記載の方法。
【請求項３】
リソースの前記別のラベルが、潜在的リソースのラベルの前記セットまたは潜在的リソースのラベルの前記サブセットからランダムに選択される、請求項２に記載の方法。
【請求項４】
実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することによって前記実リソースを除去することをさらに含み、前記実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することが、潜在的リソースのラベルの記憶された前記セットの中のワーキング・リソースの最後のラベルを示すレンジ値を減らして、前記リソースに割り振られた除去される前記ラベルを排除することにより実行される、請求項１に記載の方法。
【請求項５】
実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することによって前記実リソースを除去することをさらに含み、前記実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することが、
前記除去の前に、前記除去の前のワーキング・リソースの最後のラベルを、除去される前記リソースに割り振られた前記ラベルの代わりにして、潜在的リソースのラベルの前記セットを記憶することと、
潜在的リソースのラベルの記憶された前記セットの中のワーキング・リソースの最後のラベルを示すレンジ値を減らして、除去される前記リソースに割り振られた前記ラベルを排除することと
により実行される、請求項１に記載の方法。
【請求項６】
実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することによって前記実リソースを除去することをさらに含み、前記実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することが、
前記除去の前の最後のワーキング・リソースのラベルを、除去される前記リソースに割り振られた前記ラベルの代わりとなるように移動させ、除去される前記リソースに割り振られた前記ラベルの代わりとなった前記リソースの前記ラベルだけを記憶することと、
潜在的リソースのラベルの記憶された前記セットの中の最後のワーキング・リソースのラベルを示すレンジ値を減らすことと
により実行される、請求項１に記載の方法。
【請求項７】
最後に除去されたリソースのラベルの除去を元に戻し、元に戻された前記ラベルを、追加される実リソースに割り振ることによって前記実リソースを追加することをさらに含む、請求項１に記載の方法。
【請求項８】
潜在的リソースのラベルの前記セットが、前記潜在的リソースのうちの少なくともいくつかの潜在的リソースに対する複数のラベルを含み、それぞれの潜在的リソースに対するいくつかのラベルが、前記潜在的リソースに与えられた重みを含む、請求項１に記載の方法。
【請求項９】
計算リソースを制御するためのシステムであって、前記システムが、プロセッサと、前記プロセッサによってアクセス可能なメモリと、前記メモリに記憶されたコンピュータ・プログラム命令とを含み、前記コンピュータ・プログラム命令が、
実リソースに割り振られたワーキング・リソースの複数のラベルと、割り振られるように使用可能な予約リソースの複数のラベルとを含む潜在的リソースのラベルのセットを記憶することと、
潜在的リソースのラベルの前記セットのうちの１つのラベルへの初期割当てを生成することと、
潜在的リソースのラベルのセットのうちの１つのラベルへの前記割当てが、予約リソースの前記ラベルのうちの１つのラベルへの割当てであるときに、リクエストを、潜在的リソースの前記ラベルのサブセットから選択されたリソースの別のラベルに再割当てすることと、
前記リクエストがワーキング・リソースのラベルに割り当てられるまで、前記再割当てすることを繰り返すことと
を実行するように、前記プロセッサによって実行可能である、システム。
【請求項１０】
前記サブセットが、ワーキング・リソースの前記複数のラベルと、予約リソースの前記ラベルのうち、リソースの現在割り当てられているラベルを境界とする部分とを含む、請求項９に記載のシステム。
【請求項１１】
リソースの前記別のラベルが、潜在的リソースのラベルの前記セットまたは潜在的リソースのラベルの前記サブセットからランダムに選択される、請求項１０に記載のシステム。
【請求項１２】
実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することによって前記実リソースを除去することをさらに含み、前記実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することが、潜在的リソースのラベルの記憶された前記セットの中のワーキング・リソースの最後のラベルを示すレンジ値を減らして、前記リソースに割り振られた除去される前記ラベルを排除することにより実行される、請求項９に記載のシステム。
【請求項１３】
実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することによって前記実リソースを除去することをさらに含み、前記実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することが、
前記除去の前に、前記除去の前のワーキング・リソースの最後のラベルを、除去される前記リソースに割り振られた前記ラベルの代わりにして、潜在的リソースのラベルの前記セットを記憶することと、
潜在的リソースのラベルの記憶された前記セットの中のワーキング・リソースの最後のラベルを示すレンジ値を減らして、除去される前記リソースに割り振られた前記ラベルを排除することと
により実行される、請求項９に記載のシステム。
【請求項１４】
実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することによって前記実リソースを除去することをさらに含み、前記実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することが、
前記除去の前の最後のワーキング・リソースのラベルを、除去される前記リソースに割り振られた前記ラベルの代わりとなるように移動させ、除去される前記リソースに割り振られた前記ラベルの代わりとなった前記リソースの前記ラベルだけを記憶することと、
潜在的リソースのラベルの記憶された前記セットの中の最後のワーキング・リソースのラベルを示すレンジ値を減らすことと
により実行される、請求項９に記載のシステム。
【請求項１５】
最後に除去されたリソースのラベルの除去を元に戻し、元に戻された前記ラベルを、追加される実リソースに割り振ることによって前記実リソースを追加することをさらに含む、請求項９に記載のシステム。
【請求項１６】
潜在的リソースのラベルの前記セットが、前記潜在的リソースのうちの少なくともいくつかの潜在的リソースに対する複数のラベルを含み、それぞれの潜在的リソースに対するいくつかのラベルが、前記潜在的リソースに与えられた重みを含む、請求項９に記載のシステム。
【請求項１７】
計算リソースを制御するためのコンピュータ・プログラムであって、
実リソースに割り振られたワーキング・リソースの複数のラベルと、割り振られるように使用可能な予約リソースの複数のラベルとを含む潜在的リソースのラベルのセットを記憶することと、
潜在的リソースのラベルの前記セットのうちの１つのラベルへの初期割当てを生成することと、
潜在的リソースのラベルのセットのうちの１つのラベルへの前記割当てが、予約リソースの前記ラベルのうちの１つのラベルへの割当てであるときに、リクエストを、潜在的リソースの前記ラベルのサブセットから選択されたリソースの別のラベルに再割当てすることと、
前記リクエストがワーキング・リソースのラベルに割り当てられるまで、前記再割当てすることを繰り返すことと
を含む方法をコンピュータに実行させるための、コンピュータ・プログラム。
【請求項１８】
前記サブセットが、ワーキング・リソースの前記複数のラベルと、予約リソースの前記ラベルのうち、リソースの現在割り当てられているラベルを境界とする部分とを含む、請求項１７に記載のコンピュータ・プログラム。
【請求項１９】
リソースの前記別のラベルが、潜在的リソースのラベルの前記セットまたは潜在的リソースのラベルの前記サブセットからランダムに選択される、請求項１８に記載のコンピュータ・プログラム。
【請求項２０】
前記コンピュータに、実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することによって前記実リソースを除去することをさらに実行させ、前記実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することが、潜在的リソースのラベルの記憶された前記セットの中のワーキング・リソースの最後のラベルを示すレンジ値を減らして、前記リソースに割り振られた除去される前記ラベルを排除することにより実行される、請求項１７に記載のコンピュータ・プログラム。
【請求項２１】
前記コンピュータに、実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することによって前記実リソースを除去することをさらに実行させ、前記実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することが、
前記除去の前に、前記除去の前のワーキング・リソースの最後のラベルを、除去される前記リソースに割り振られた前記ラベルの代わりにして、潜在的リソースのラベルの前記セットを記憶することと、
潜在的リソースのラベルの記憶された前記セットの中のワーキング・リソースの最後のラベルを示すレンジ値を減らして、除去される前記リソースに割り振られた前記ラベルを排除することと
により実行される、請求項１７に記載のコンピュータ・プログラム。
【請求項２２】
前記コンピュータに、実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することによって前記実リソースを除去することをさらに実行させ、前記実リソースに割り振られたラベルをワーキング・リソースの前記ラベルから除去することが、
前記除去の前の最後のワーキング・リソースのラベルを、除去される前記リソースに割り振られた前記ラベルの代わりとなるように移動させ、除去される前記リソースに割り振られた前記ラベルの代わりとなった前記リソースの前記ラベルだけを記憶することと、
潜在的リソースのラベルの記憶された前記セットの中の最後のワーキング・リソースのラベルを示すレンジ値を減らすことと
により実行される、請求項１７に記載のコンピュータ・プログラム。
【請求項２３】
前記コンピュータに、最後に除去されたリソースのラベルの除去を元に戻し、元に戻された前記ラベルを、追加される実リソースに割り振ることによって前記実リソースを追加することをさらに実行させる、請求項１７に記載のコンピュータ・プログラム。
【請求項２４】
潜在的リソースのラベルの前記セットが、前記潜在的リソースのうちの少なくともいくつかの潜在的リソースに対する複数のラベルを含み、それぞれの潜在的リソースに対するいくつかのラベルが、前記潜在的リソースに与えられた重みを含む、請求項１７に記載のコンピュータ・プログラム。
【国際調査報告】
2021530060.tif 000010
2021530060.tif 000011