(57)【要約】      （修正有）【課題】複数のキャッシュノードの負荷平衡及び動的なスケーリングする装置及び方法を提供する。【解決手段】装置は負荷バランサ２００と負荷バランサに通信可能に結合されたキャッシュスケーラ３００からなる。負荷バランサは、１つ又は複数のクライアントから受信されたオブジェクトの読み出し要求を、オブジェクトの全体的な順位付けに基づいて１つ又は複数のキャッシュノードの少なくとも１つに送る。各キャッシュノードは、キャッシュヒットがあると、自身のローカル記憶域からオブジェクトを要求元のクライアント１００に提供し、キャッシュミスがあると、永続的な記憶域５００からオブジェクトをダウンロードし、オブジェクトを要求元のクライアントに提供する。キャッシュスケーラは、キャッシュ階層の１つ又は複数のキャッシュノードによって測定された性能の統計値に基づき、キャッシュ階層でアクティブなキャッシュノードの数を周期的に調整する。【選択図】図２
2015072682.tif 000002
【特許請求の範囲】
【請求項１】
永続的な記憶域からなる第１の階層と、前記永続的な記憶域に通信可能に結合された１つ又は複数のキャッシュノードからなる第２の階層とを有する２階層の分散キャッシュ記憶システムで使用するための装置であって、
１つ又は複数のクライアントから受信されたオブジェクトの読み出し要求を、オブジェクトの全体的な順位付けに基づいて前記１つ又は複数のキャッシュノードの少なくとも１つに送る負荷バランサであり、キャッシュヒットがあると、前記少なくとも１つのキャッシュノードの各キャッシュノードが、自身のローカル記憶域から前記オブジェクトを要求元のクライアントに提供するか、又はキャッシュミスがあると、前記永続的な記憶域から前記オブジェクトをダウンロードし、前記オブジェクトを前記要求元のクライアントに提供する、負荷バランサと、
前記負荷バランサに通信可能に結合されて、キャッシュ階層の前記１つ又は複数のキャッシュノードによって測定された性能の統計値に基づいて、前記キャッシュ階層でアクティブであるキャッシュノードの数を周期的に調整するキャッシュスケーラと
を備える装置。
【請求項２】
前記全体的な順位付けは、最も長時間使用されていない（ＬＲＵ）ポリシーに基づく請求項１に記載の装置。
【請求項３】
前記負荷バランサは、特定のオブジェクトに対する要求の１つを、前記少なくとも１つのキャッシュノードの複数のキャッシュノードに転送して、当該ファイルをまだキャッシュしていない少なくとも１つのキャッシュノードで前記特定のオブジェクトを複製させる、請求項１に記載の装置。
【請求項４】
前記負荷バランサは、前記１つの要求に関連付けられた前記特定のオブジェクトがある順位の人気度を有すると判定し、前記特定のオブジェクトの人気度の順位が第１のレベルであると判定するのに応じて、前記特定のオブジェクトに対する前記１つの要求を前記複数のキャッシュノードに転送して、当該ファイルをまだキャッシュしていない前記少なくとも１つのキャッシュノードで前記特定のオブジェクトが複製されるようにする請求項３に記載の装置。
【請求項５】
前記負荷バランサは、前記２階層の記憶システムに記憶されているオブジェクトの相対的な人気度の順位をリストを使用して推定する、請求項１に記載の装置。
【請求項６】
前記リストが、前記オブジェクトに対応する索引を記憶する全体的なＬＲＵリストであり、前記リストの一方の端にある索引は、前記リストの他方の端にある索引に関連付けられたオブジェクトよりも人気がある可能性が高いオブジェクトに関連付けられる請求項５に記載の装置。
【請求項７】
前記負荷バランサは、特定のオブジェクトが第１の数のキャッシュノードで既にキャッシュされていると判定するのに応じて、前記オブジェクトが前記リスト内で上位に順位付けられているかどうかを調べ、上位に順位付けられている場合は、前記第１の数のキャッシュノードを増やす、請求項５に記載の装置。
【請求項８】
前記負荷バランサは、あるオブジェクトを現在キャッシュしていないキャッシュノードに当該オブジェクトに対する要求を転送する際に、前記オブジェクトに対する前記要求にフラグを付加して、前記オブジェクトを前記永続的な記憶域から取得して前記要求を満たした後に前記オブジェクトをキャッシュしないように前記キャッシュノードに指示する、請求項１に記載の装置。
【請求項９】
前記性能の統計値が、要求の未処理量、クライアント要求に対応する際の遅延を示す遅延パフォーマンス情報、及びキャッシュヒット率情報、の１つ又は複数を含む、請求項１に記載の装置。
【請求項１０】
前記キャッシュスケーラは、キャッシュノードの数を調整するかどうかを３次関数に基づいて決定する、請求項１に記載の装置。
【請求項１１】
前記キャッシュスケーラは、次の期間に必要とされるキャッシュノードの数を決定し、前記次の期間に必要とされるキャッシュノードの数を満たすためにキャッシュノードを停止させるか、又は作動させるかを決定し、前記次の期間のキャッシュノードの数を減らす場合は停止させるキャッシュノードを決定する、請求項１０に記載の装置。
【請求項１２】
各前記１つ又は複数のキャッシュノードは、ローカルキャッシュのエビクトポリシーを用いて自身のローカル記憶域にキャッシュされるオブジェクトのセットを管理する、請求項１に記載の装置。
【請求項１３】
前記ローカルキャッシュのエビクトポリシーがＬＲＵ又はＬＦＵ（使用頻度が最も低い）である請求項１２に記載の装置。
【請求項１４】
前記少なくとも１つのキャッシュノードの各キャッシュノードがキャッシュサーバ又は仮想機械からなる請求項１に記載の装置。
【請求項１５】
永続的な記憶域からなる第１の階層と、前記永続的な記憶域に通信可能に結合された１つ又は複数のキャッシュノードからなる第２の階層とを有する２階層の分散キャッシュ記憶システムで使用するための方法であって、
１つ又は複数のクライアントから負荷バランサによって受信されたオブジェクトの読み出し要求を、オブジェクトの全体的な順位付けに基づいて前記１つ又は複数のキャッシュノードの少なくとも１つに送るステップと、
キャッシュヒットがあると、前記少なくとも１つのキャッシュノードの各キャッシュノードが、自身のローカル記憶域から前記オブジェクトを要求元のクライアントに提供するか、又はキャッシュミスがあると、前記永続的な記憶域から前記オブジェクトをダウンロードし、前記オブジェクトを前記要求元のクライアントに提供するステップと、
キャッシュ階層の前記１つ又は複数のキャッシュノードによって測定された性能の統計値に基づいて、前記キャッシュ階層でアクティブであるキャッシュノードの数を周期的に調整するステップと
を含む方法。
【請求項１６】
前記全体的な順位付けが最も長時間使用されていない（ＬＲＵ）ポリシーに基づく請求項１５に記載の方法。
【請求項１７】
特定のオブジェクトに対する要求の１つを、前記少なくとも１つのキャッシュノードの複数のキャッシュノードに転送して、当該ファイルをまだキャッシュしていない少なくとも１つのキャッシュノードで前記特定のオブジェクトを複製させるステップをさらに含む請求項１５に記載の方法。
【請求項１８】
前記１つの要求に関連付けられた前記特定のオブジェクトがある順位の人気度を有すると判定し、前記特定のオブジェクトの人気度の順位が第１のレベルであると判定するのに応じて、前記特定のオブジェクトに対する前記１つの要求を前記複数のキャッシュノードに転送して、当該ファイルをまだキャッシュしていない前記少なくとも１つのキャッシュノードで前記特定のオブジェクトが複製されるようにするステップをさらに含む請求項１７に記載の方法。
【請求項１９】
前記２階層の記憶システムに記憶されているオブジェクトの相対的な人気度の順位をリストを使用して推定するステップをさらに含む請求項１５に記載の方法。
【請求項２０】
前記リストは、前記オブジェクトに対応する索引を記憶する全体的なＬＲＵリストであり、前記リストの一方の端にある索引は、前記リストの他方の端にある索引に関連付けられたオブジェクトよりも人気がある可能性が高いオブジェクトに関連付けられる請求項１９に記載の方法。
【請求項２１】
特定のオブジェクトが第１の数のキャッシュノードで既にキャッシュされていると判定するのに応じて、前記オブジェクトが前記リスト内で上位に順位付けられているかどうかを調べ、上位に順位付けられている場合は、前記第１の数のキャッシュノードを増やすステップをさらに含む請求項１９に記載の方法。
【請求項２２】
あるオブジェクトを現在キャッシュしていないキャッシュノードに当該オブジェクトに対する要求を転送する際に、前記オブジェクトに対する前記要求にフラグを付加して、前記オブジェクトを前記永続的な記憶域から取得して前記要求を満たした後に前記オブジェクトをキャッシュしないように前記キャッシュノードに指示するステップをさらに含む請求項１５に記載の方法。
【請求項２３】
前記性能の統計値が、要求の未処理量、要求に応答する際のキャッシュの遅延を示す遅延パフォーマンス情報、及びキャッシュヒット率情報、の１つ又は複数を含む、請求項１５に記載の方法。
【請求項２４】
キャッシュノードの数を調整するかどうかを３次関数に基づいて決定するステップをさらに含む請求項１５に記載の方法。
【請求項２５】
次の期間に必要とされるキャッシュノードの数を決定し、前記次の期間に必要とされるキャッシュノードの数を満たすためにキャッシュノードを停止させるか、又は作動させるかを決定し、前記次の期間のキャッシュノードの数を減らす場合は停止させるキャッシュノードを決定するステップをさらに含む請求項２４に記載の方法。
【請求項２６】
命令を記憶した１つ又は複数の非一時的記憶媒体を有する製造品であって、前記命令は、永続的な記憶域からなる第１の階層と、前記永続的な記憶域に通信可能に結合された１つ又は複数のキャッシュノードからなる第２の階層とを有する２階層の分散キャッシュ記憶システムによって実行されると、前記記憶システムに、
１つ又は複数のクライアントから負荷バランサによって受信されたオブジェクトの読み出し要求を、オブジェクトの全体的な順位付けに基づいて前記１つ又は複数のキャッシュノードの少なくとも１つに送るステップと、
キャッシュヒットがあると、前記少なくとも１つのキャッシュノードの各キャッシュノードが、自身のローカル記憶域から前記オブジェクトを要求元のクライアントに提供するか、又はキャッシュミスがあると、前記永続的な記憶域から前記オブジェクトをダウンロードし、前記オブジェクトを前記要求元のクライアントに提供するステップと、
キャッシュ階層の前記１つ又は複数のキャッシュノードによって測定された性能の統計値に基づいて、前記キャッシュ階層でアクティブであるキャッシュノードの数を周期的に調整するステップと
を含む方法を行わせる製造品。
【発明の詳細な説明】
【技術分野】
【０００１】
優先権
[0001]本特許出願は、２０１３年９月１２日に出願された対応する仮特許出願第６１／８７７，１５８号、発明の名称「Ａ  Ｍｅｔｈｏｄ  ａｎｄ  Ａｐｐａｒａｔｕｓ  ｆｏｒ  Ｌｏａｄ  Ｂａｌａｎｃｉｎｇ  ａｎｄ  Ｄｙｎａｍｉｃ  Ｓｃａｌｉｎｇ  ｆｏｒ  Ｌｏｗ  Ｄｅｌａｙ  Ｔｗｏ−Ｔｉｅｒ  Ｄｉｓｔｒｉｂｕｔｅｄ  Ｃａｃｈｅ  Ｓｔｏｒａｇｅ  Ｓｙｓｔｅｍ」の優先権を主張し、参照により同文献を取り込む。
[0002]本発明の実施形態は分散記憶システムの分野に関し、より詳細には、本発明の実施形態は、２階層の分散キャッシュ記憶システムにおける負荷平衡及びキャッシュのスケーリングに関する。
【背景技術】
【０００２】
[0003]クラウドで提供されるデータの記憶とコンテンツ提供のサービスが現在広く使用されている。一般向けのクラウドは、必要に応じてより多くのリソースをリース又は解約することが可能な低リスクの基本設備（すなわちサービスの基本設備をそれぞれ拡大又は縮小することができる）を利用できることから、サービス提供者にとって魅力的である。
【０００３】
[0004]クラウドで提供されるデータ記憶の１つの種類は、一般に２階層のクラウド記憶システムと呼ばれる。２階層のクラウド記憶システムは、コンピューティングクラウド（例えばＡｍａｚｏｎ  ＥＣ２）からリースされたリソースで構成される分散キャッシュからなる第１の階層と、永続的な分散記憶域（例えばＡｍａｚｏｎ  Ｓ３）からなる第２の階層とを含む。リースされるリソースは多くの場合クラウド提供者からリースされる仮想機械（ＶＭ）であり、負荷を平衡しながらクライアント要求に応えると共に、要求されるコンテンツのためのキャッシュ層も提供する。
【０００４】
[0005]一般利用が可能なクラウドを使用する際の価格設定と性能に差があるために、多くの状況では、同じクラウド提供者又は異なるクラウド提供者からの複数のサービスを組み合わせなければならない。例えば、オブジェクトを記憶する場合は、Ａｍａｚｏｎ  ＥＣ２からリースした仮想機械のメモリ（例えばハードディスク）にオブジェクトを記憶するよりも、Ａｍａｚｏｎ  Ｓ３に記憶する方がはるかに低費用である。一方、費用は高くなるが、ＥＣ２のインスタンスにオブジェクトをローカルにキャッシュすると、より高速且つより予測可能な形でエンドユーザに対応することができる。
【０００５】
[0006]２階層のクラウド記憶システムを使用する際には、キャッシュ階層の負荷平衡とスケーリングに伴う問題が存在する。具体的には、発生する問題の１つは、高い利用率と良好な遅延パフォーマンスを実現するためにキャッシュ階層の負荷平衡及び規模の拡大／縮小の決定をどのように行うという問題である。規模の拡大／縮小の決定については、作業負荷の動的な特性と人気度の分布の変化に応じてリソース（例えばＶＭ）の数をどのように調節するかが主要な問題となる。
【０００６】
[0007]負荷平衡とキャッシングのポリシーは従来技術に多数存在する。サーバのネットワークを利用する従来技術の解決法の１つは、サーバがローカルにジョブに対応するか、又は別のサーバにジョブを転送するものであるが、この解決法では平均の応答時間が短縮され、凸最適化を使用して各サーバが負担する負荷を求める。同じ問題に対する他の解決法が存在する。しかし、それらの解決法では、時間と共に変化する作業負荷や、サーバ数、サービス率などのシステムの動的な特性に対処することができない。さらに、従来技術の解決法は、データの局所性と、負荷平衡の決定が現在及び（キャッシングによる）将来のサービス率に与える影響を考慮しない。
【０００７】
[0008]Ｐ２Ｐ（ピアツーピア）のファイルシステム向けの負荷平衡及びキャッシングポリシーの解決法がいくつか提案されている。そのような解決法の１つはファイルの人気度に比例してファイルを複製するものであるが、この機構は記憶容量の制限がない。すなわち、合計の記憶容量はファイルの合計サイズよりはるかに大きい。また、Ｐ２Ｐの性質上、システム内のピアの数がコントロールされない。別のＰ２Ｐシステムの解決法、すなわち各ピアが一定の接続容量と記憶容量を有するビデオオンデマンドシステムシステムでは、新しい映像要求の拒否率をできるだけ低くするためにコンテンツのキャッシング方針が評定される。
【０００８】
[0009]ファイルシステムにおける協働的キャッシングも過去に検討されている。例えば、全体的なＬＲＵ（least recently used）のリストとどのサーバが何をキャッシュするかを命令するマスタサーバを用いる中央調整型のキャッシングが研究されている。
【０００９】
[0010]大半のＰ２Ｐ記憶システム及び非ＳＱＬデータベースは、記憶ノードを動的に追加及び除去することを念頭において設計されている。既存の記憶ノードのＣＰＵ利用レベルに依拠して記憶ノードを追加する、又は終了させるアーキテクチャが存在する。過負荷の記憶ノードと軽負荷の記憶ノード間でデータを移動させると共に、記憶ノードを追加／削除する解決法も提案されている。
【発明の概要】
【００１０】
[0011]記憶システムのための負荷平衡及び動的なスケーリングの方法及び装置が本明細書に開示される。一実施形態では、装置は、１つ又は複数のクライアントから受信されたオブジェクトの読み出し要求を、オブジェクトの全体的な順位付けに基づいて１つ又は複数のキャッシュノードの少なくとも１つに送る負荷バランサであって、キャッシュヒットがあると、各キャッシュノードが、自身のローカル記憶域からオブジェクトを要求元のクライアントに提供するか、又はキャッシュミスがあると、永続的な記憶域からオブジェクトをダウンロードし、オブジェクトを要求元のクライアントに提供する、負荷バランサと、負荷バランサに通信可能に結合されて、キャッシュ階層の１つ又は複数のキャッシュノードによって測定された性能の統計値に基づいて、キャッシュ階層でアクティブであるキャッシュノードの数を周期的に調整するキャッシュスケーラとを備える。
【図面の簡単な説明】
【００１１】
[0012]以下の詳細な説明と本発明の各種実施形態の添付図面から本発明をより理解することができるが、説明及び図面は本発明を特定の実施形態に限定するものではなく、説明と理解のみを目的とする。
【図１】２階層の記憶システムのシステムアーキテクチャの一実施形態のブロック図である。
【図２】２階層の記憶システムの一実施形態で記憶を行う応用例を説明するブロック図である。
【図３】負荷平衡処理の一実施形態の流れ図である。
【図４】キャッシュスケーリング処理の一実施形態の流れ図である。
【図５】キャッシュスケーラのための状態機械の一実施形態を説明する図である。
【図６】キャッシュスケーラの一実施形態によって行われる動作を示す疑似コードの図である。
【図７】システムの一実施形態のブロック図である。
【図８】図７のシステムの一実施形態のメモリに記憶されるコード（例えばプログラム）及びデータのセットを示す図である。
【発明を実施するための形態】
【００１２】
[0013]本発明の実施形態は、２階層のクラウド記憶システムで高い利用率を実現しつつ、最良の遅延パフォーマンスを得ることができる負荷平衡及び自動的なスケーリングの方法及び装置を含む。一実施形態では、第１の階層が分散キャッシュからなり、第２の階層が永続的な分散記憶域からなる。分散キャッシュは、コンピューティングクラウド（例えばＡｍａｚｏｎ  ＥＣ２）からリースされたリソースを含むことができ、永続的な分散記憶域はリースされたリソース（例えばＡｍａｚｏｎ  Ｓ３）を含むことができる。
【００１３】
[0014]一実施形態では、記憶システムは負荷バランサを含む。分散キャッシュ階層内の所与のキャッシュノードの集合（例えばサーバ、仮想機械（ＶＭ）等）について、負荷バランサは、全体的なキャッシュヒット率を最大近くに維持しながら、オブジェクトの人気度の分布が未知の作業負荷に対して負荷を可能な限り均等に分散させる。
【００１４】
[0015]一実施形態では、キャッシング階層の分散キャッシュは複数のキャッシュサーバを含み、記憶システムはキャッシュスケーラを含む。任意の時点に、本明細書に記載される技術が、記憶システムからサービスを受けるオブジェクトのオブジェクト人気度及び永続的記憶域のサービス率は変化することを考慮して、記憶システム内でアクティブにするキャッシュサーバの数を動的に決定する。一実施形態では、キャッシュスケーラは、キャッシング階層で収集される統計値、例えば要求の未処理量、遅延パフォーマンス、キャッシュヒット率等を使用して、次の（又は将来の）期間にキャッシュ階層で使用するアクティブなキャッシュサーバの数を決定する。
【００１５】
[0016]一実施形態では、本明細書に記載される技術は、２階層の分散キャッシュ記憶システムに記憶されたオブジェクトを読み出す際のロバストな遅延と費用のトレードオフをもたらす。記憶システムへのアクセスを試みるクライアントとのインターフェースをとるキャッシング階層では、要求されるコンテンツに対応するキャッシング層は、クラウド提供者（例えばＡｍａｚｏｎ  ＥＣ２）からリースされた仮想機械（ＶＭ）からなり、それらのＶＭがクライアント要求に応える。バックエンドの永続的な分散記憶階層では、例えばＡｍａｚｏｎ  Ｓ３などの耐久性があり可用性が高いオブジェクト記憶サービスが利用される。作業負荷が軽い状況では、キャッシング層のＶＭの数が少なくても、十分に読み出し要求の遅延を低くすることができる。作業負荷が高い状況では、良好な遅延パフォーマンスを維持するためにより多くのＶＭが必要となる。負荷バランサは、総キャッシュヒット率を高く維持しつつ、負荷を平衡して種々のＶＭに要求を振り分け、一方、キャッシュスケーラは、最小数のＶＭで良好な遅延パフォーマンスを達成するようにＶＭの数を適合することにより、クラウド使用の費用を最適化し、可能性としては最小にする。
【００１６】
[0017]一実施形態では、本明細書に記載される技術は、オブジェクトの人気度の実際の分布についての知識を仮定することなく、ジップ（Zipfian）分布に対して非常に有効であり、最小の費用で低遅延を保証する最適に近い負荷平衡及びキャッシュスケーリングの解決法をもたらす。したがって、本発明の技術は、ユーザに対してはロバストな遅延パフォーマンスを提供し、クラウド記憶サービスを提供する企業に対しては顧客満足度について高い価値が予想される。
【００１７】
[0018]以下の説明では、本発明をより完全に説明するために多数の詳細事項を述べる。ただし、当業者には、本発明はそれらの具体的な詳細事項を用いずに実施可能であることが明らかであろう。他の事例では、本発明を曖昧にするのを避けるために、よく知られる構造及び装置は詳細に図示するのではなく、ブロック図の形態で示される。
【００１８】
[0019]以下の詳細な説明の一部は、コンピュータメモリ内のデータビットに対する操作のアルゴリズム及び記号的表現として提供する。そのようなアルゴリズム的な記述及び表現は、仕事の内容を同じ分野の他の当業者に最も有効に伝えるためにデータ処理技術の当業者に使用される手段である。アルゴリズムとは、本発明で、また一般に、所望の結果をもたらす自己矛盾のない一連の工程と認識される。工程は、物理的な数量の物理的な操作を必要とする工程である。通常、必ずしもこれに限らないが、そのような数量は、記憶、転送、組み合わせ、比較、及びその他の操作が可能な電気又は磁気信号の形態をとる。時に、主として一般に使用されているという理由から、そのような信号をビット、値、要素、記号、文字、項、数等と呼ぶことが利便であることが分かっている。
【００１９】
[0020]ただし、上記及び同様の用語はすべて適切な物理的数量に関連付けられるべきである、単にそのような数量に付加される利便な標識に過ぎないことを念頭に置かれたい。以下の説明から明らかなように、特に指定しない限りは、この説明を通じて、「処理する」又は「算出する」又は「計算する」又は「判定する」又は「表示する」等の用語を利用した説明は、コンピュータシステムのレジスタ及びメモリ内で物理的（電子的）な数量として表されるデータを操作して、コンピュータシステムメモリ若しくはレジスタ、又は他の同様の情報記憶装置、伝送装置、又は表示装置内で物理量として同様に表される他のデータに変換するコンピュータシステム又は同様の電子演算装置の動作又は処理を言うことが理解される。
【００２０】
[0021]本発明は、本明細書に記載される動作を行う装置にも関する。この装置は、要求される目的のために特別に構築しても、又はコンピュータ内に記憶されたコンピュータプログラムによって選択的に作動状態にされる、又は再構成される汎用コンピュータからなってもよい。そのようなコンピュータプログラムはコンピュータで読み取り可能な記憶媒体に記憶することができ、そのような記憶媒体は、これらに限定されないが、フロッピーディスク、光ディスク、ＣＤ−ＲＯＭ、及び光磁気ディスク等の任意種のディスク、読み出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、ＥＰＲＯＭ、ＥＥＰＲＯＭ、磁気カード若しくは光学カード、又は電子命令を記憶するのに適した任意種の媒体であり、各々コンピュータシステムバスに結合される。
【００２１】
[0022]本明細書に提示するアルゴリズム及び表示は、本質的に、どの特定のコンピュータ又は他の装置にも関連しない。各種の汎用システムを本明細書の教示に従うプログラムと共に使用することができ、又は、要求される方法の工程を行うようにより特化された装置を構築することが利便である可能性もある。各種のそのようなシステムに要求される構造は以下の説明から明らかになろう。また、本発明は、特定のプログラミング言語を参照して説明しない。各種のプログラミング言語を使用して本明細書に記載される本発明の教示を実施できることが理解されよう。
【００２２】
[0023]機械可読の媒体には、機械（例えばコンピュータ）による読み取りが可能な形態で情報を記憶又は伝送する機構が含まれる。例えば、機械可読の媒体は、読み出し専用メモリ（「ＲＯＭ」）、ランダムアクセスメモリ（「ＲＡＭ」）、磁気ディスク記憶媒体、光学記憶媒体、フラッシュメモリ装置等を含む。
【００２３】
記憶アーキテクチャの一実施形態の概要
[0024]図１は、２階層記憶システムのシステムアーキテクチャの一実施形態のブロック図である。図２は、２階層記憶システムの一実施形態で記憶を行う応用例を説明するブロック図である。
【００２４】
[0025]図１及び図２を参照すると、クライアント１００がデータオブジェクト（例えばファイル）の入出力（Ｉ／Ｏ）要求２０１（例えばｄｏｗｎｌｏａｄ（ｆｉｌｅｘ））を負荷バランサ（ＬＢ）２００に発行する。ＬＢ２００は、キャッシング階層４００を構成するキャッシュノードの集合を維持している。一実施形態では、キャッシュノードの集合は、サーバの集合
【数１】
2015072682.tif 000003
からなり、ＬＢ２００は、クライアント要求２０１をそれらのキャッシュサーバのいずれかに誘導することができる。各キャッシュサービスは、図２のローカル記憶域４１０などのローカル記憶域を含むか、又はアクセスすることができる。一実施形態では、キャッシング階層４００は、Ａｍａｚｏｎ  ＥＣ２又は他のリースされる記憶リソースからなる。
【００２５】
[0026]一実施形態では、ＬＢ２００は、ロケーションマッパー（例えば図２のロケーションマッパー２１０）を使用して、キャッシュ階層４００のどのキャッシュサーバがどのオブジェクトを持っているかを追跡する。その情報を使用して、クライアント１００のクライアントが特定のオブジェクトを要求すると、ＬＢ２００は、どの（１つ又は複数の）サーバがそのオブジェクトを保持しているかを認識し、要求をそのサーバの１つに送る。
【００２６】
[0027]一実施形態では、ＬＢ２００からキャッシュノードに送信される要求２０１は、オブジェクトとそのオブジェクトを要求したクライアント１００のクライアントを指定する。本明細書では、総負荷をλｉｎと表す。各サーバｊは、ＬＢ２００からλｊの負荷を受け取り、すなわち
【数２】
2015072682.tif 000004
となる。キャッシュサーバが要求オブジェクトをキャッシュしている場合、キャッシュサーバは、Ｉ／Ｏ応答２０２を介してそのオブジェクトをクライアント１００の要求元クライアントに提供する。キャッシュサーバが要求オブジェクトをキャッシュしていない場合、キャッシュサーバは、そのオブジェクトとそれに対応する要求とを指定する読み出し要求（例えばｒｅａｄ（ｏｂｊ１，ｒｅｑ１））を永続的な記憶域５００に送信する。一実施形態では、永続的な記憶域５００は、Ａｍａｚｏｎ  Ｓ３又は他のリースされた記憶リソースのセットからなる。その要求に応じて、永続的な記憶域５００は、要求されるオブジェクトを要求元のキャッシュサーバに提供し、キャッシュサーバはＩ／Ｏ応答２０２を介してそのオブジェクトを要求元のクライアントに提供する。
【００２７】
[0028]一実施形態では、キャッシュサーバは、先入れ先出し（ＦＩＦＯ）方式の要求待ち行列及びワーカースレッドのセットを含む。要求は要求待ち行列で緩衝される。別の実施形態では、要求待ち行列は優先待ち行列として動作し、低遅延が要求される要求は厳格な優先順位が与えられ、要求待ち行列の先頭に置かれる。一実施形態では、各キャッシュサーバが、後にＬｃ個の並列のキャッシュスレッドが続くＦＩＦＯ待ち行列としてモデル化される。読み出し要求が列の先頭（Head-of-Line：ＨｏＬ）になると、その要求は、利用可能になる最初のキャッシュスレッドに割り当てられる。ＨｏＬ要求は要求待ち行列から取り出され、ワーカースレッドのうちそのスレッドに送られる。一実施形態では、キャッシュサーバが、いつ要求を要求待ち行列から取り出すかを決定する。一実施形態では、キャッシュサーバは、少なくとも１つのワーカースレッドが空くと要求待ち行列から要求を取り出す。キャッシュヒットが生じる（すなわちキャッシュサーバのローカルキャッシュに要求されるファイルがある）と、キャッシュサーバは、要求されるオブジェクトを自身のローカル記憶域からレートμｈで要求元のクライアントに直接返す。キャッシュミスが生じる（すなわち要求されるファイルがキャッシュサーバのローカルキャッシュにない）と、キャッシュサーバは、まず、オブジェクトの読み出し要求をバックエンドの永続的な記憶域５００に発行する。要求されるオブジェクトがキャッシュサーバにダウンロードされると、キャッシュサーバは直ちにレートμｈでオブジェクトをクライアントに提供する。
【００２８】
[0029]本明細書では、サーバｊにおけるキャッシュヒット率をｐｈｊと表し、キャッシュミス率をｐｍｊと表す（すなわち、ｐｍｊ＝１−ｐｈｊ）。各サーバｊは、バックエンドの永続的な記憶域に対してλｊ×ｐｍ，ｊの負荷を生じる。一実施形態では、永続的な記憶域５００は、後にＬＳ個の並列な記憶スレッドが続く１つの大きなＦＩＦＯ待ち行列としてモデル化される。永続的な記憶域への到着率は
【数３】
2015072682.tif 000005
であり、各個々の記憶スレッドのサービス率はμｍである。一実施形態では、μｍはμｈより大幅に小さく、サービス提供者による制御が不可能であり、時間の経過と共に変化する。
【００２９】
[0030]別の実施形態では、キャッシュサーバはカットスルー（cut-through）経路選定を用い、バックエンドの永続的な記憶域５００から残りの部分を受け取り次第、オブジェクトの部分的な読み出しを、クライアント１００のうちそのオブジェクトを要求しているクライアントに供給する。
【００３０】
[0031]キャッシュサーバにおけるキャッシングポリシーが定まると、ＬＢ２００によって行われる要求の経路選定の決定が、どのオブジェクトをキャッシュするか、どこにオブジェクトをキャッシュするか、及びどれだけの時間キャッシュするかを最終的に決定する。例えば、ＬＢ２００が同じオブジェクトを求める別々の要求を複数のサーバに発行した場合、要求されるオブジェクトはそれらのキャッシュサーバで複製される。そのため、複製されるファイルに関連する負荷を複数のキャッシュサーバで分担することができる。これを使用して負荷集中箇所（hot spot）の発生を回避することができる。
【００３１】
[0032]一実施形態では、各キャッシュサーバは、自身のローカルキャッシュの内容を独自に管理する。したがって、キャッシュサーバ間で通信を行う必要がない。一実施形態では、キャッシュ階層４００の各キャッシュサーバは、自身のローカルのアクセスパターンとキャッシュサイズのみを使用するローカルキャッシュのエビクト（eviction）ポリシー（例えばＬＲＵ（Least Recently Used：最も長時間使用されていない）ポリシー、ＬＦＵ（Least Frequently Used：使用頻度が最も低い）ポリシー等）を用いる。
【００３２】
[0033]キャッシュスケーラ（ＣＳ）３００は、図２のキャッシュ性能モニタ（ＣＰＭ）３１０を通じて、キャッシュ階層４００の個々のキャッシュノード（例えばサーバ）から、性能の統計値２０３、例えば未処理量、遅延パフォーマンス、及び／又はヒット率などを周期的（例えばＴ秒ごと）に収集する。性能の統計値２０３に基づいて、ＣＳ３００は、集合
【数４】
2015072682.tif 000006
のキャッシュサーバをさらに追加するか、又は集合
【数５】
2015072682.tif 000007
の既存のキャッシュサーバの一部を除去するかを決定する。ＣＳ３００は、集合
【数６】
2015072682.tif 000008
が変更されると必ずＬＢ２００に通知する。
【００３３】
[0034]一実施形態では、各キャッシュノードは、リース期間（例えば１時間）を有する。そのため、実際のサーバの終了は遅れをもって発生する。ＣＳ３００が集合
【数７】
2015072682.tif 000009
にあるサーバの数を減らし、その後一部のサーバが終了する前に集合
【数８】
2015072682.tif 000010
のサーバ数を再度増やすことを決定した場合、ＣＳ３００は終了の決定を取り消すことができる。或いは、新しいサーバが集合
【数９】
2015072682.tif 000011
に追加され、その後サーバ数を減らすことが決定されると、サービス提供者は、使用されていない演算時間について不必要に代金を支払う。一実施形態では、リース時間ＴｌｅａｓｅはＴの整数倍であるとする。
【００３４】
[0035]一実施形態では、キャッシュ階層４００及び永続的な記憶域５００を除くすべての構成要素は同じ物理機械で動作する。そのような物理機械の一例については下記で詳細に説明する。別の実施形態では、そのような構成要素のうち１つ又は複数を異なる物理機械で動作させ、相互に通信することができる。一実施形態では、そのような通信はネットワークを通じて行われる。そのような通信は有線であっても無線であってもよい。
【００３５】
[0036]一実施形態では、各キャッシュサーバは同質であり、すなわち同じＣＰＵ、メモリサイズ、ディスクサイズ、ネットワーク入出力速度、サービスレベルの合意を有する。
【００３６】
負荷バランサの実施形態
[0037]上記のように、ＬＢ２００はクライアントの要求を個々のキャッシュサーバ（ノード）に転送する。一実施形態では、ＬＢ２００は、キャッシュサーバに転送する要求の順序を追跡しているため、各キャッシュサーバのキャッシュ内容を把握している。時に、ＬＢ２００は、同じオブジェクトに対する要求を複数のキャッシュサーバに送り、それによりそのオブジェクトをそれらのキャッシュサーバで複製させる。この理由はキャッシュサーバの１つがオブジェクトをキャッシュしており（ＬＢ２００は要求を追跡しているためそのサーバを把握している）、少なくとも１つのキャッシュサーバがオブジェクトを持っておらず、永続的な記憶域５００からダウンロードするか、その他の方法でオブジェクトを取得しなければならないためである。そのようにして、負荷バランサによる要求の転送の決定で、各キャッシュサーバのキャッシュ内容が時間と共にどのように変化するかが決まる。
【００３７】
[0038]一実施形態では、キャッシュサーバの集合
【数１０】
2015072682.tif 000012
を仮定して、負荷バランサ（ＬＢ）は２つの目的を持つ。
【００３８】
１）総キャッシュヒット率を可能な限り高くする。すなわち、永続的な記憶域に課される負荷
【数１１】
2015072682.tif 000013
を最小に抑えて、キャッシュされていないオブジェクトを永続的な記憶域から取り出すための追加的な遅延が最小になるようにする。
【００３９】
[0039]２）各キャッシュサーバ間のシステム利用を均衡化して、非常に人気のあるオブジェクトをキャッシュしている少数のサーバが過負荷になり、その他のサーバが十分に利用されない状況を回避する。
【００４０】
[0040]この２つの目的は、特に要求されるオブジェクトの人気度の分布が著しく偏っているときには互いと矛盾する可能性もある。負荷が不均衡になる問題を緩和する１つの方法は、非常に人気のあるオブジェクトを複数のキャッシュサーバに複製し、そのオブジェクトに対する要求をそれらのサーバに均等に分散させるものである。しかし、キャッシュサーバ間で作業負荷を均衡化できる可能性は高くなるが、そのようにすると、キャッシュできる別個のオブジェクトの数が減り、結果として全体のヒット率が低下する。したがって、過度に多くのオブジェクトが過度に多くの回数複製された場合は、はるかに低速度のバックエンドの記憶域から過度に多くの要求に対応しなければならないため、そのような手法は遅延が高くなる。
【００４１】
[0041]一実施形態では、負荷バランサは、要求されるファイルの人気度を使用して負荷平衡の決定を調整する。具体的には、負荷バランサは、要求されるファイルの人気度を推定してからその推定結果を使用して、記憶システムのキャッシュ階層でそれらのファイルの複製を増やすかどうかを決定する。すなわち、あるファイルが非常に人気があることを負荷バランサが認識すると、そのファイルの複製の数を増加することができる。一実施形態では、要求されるファイルの人気度の推定は全体的なＬＲＵ（least recently used）テーブルを使用して行われ、このテーブルでは、最後に要求されたオブジェクトが、リストの使用中にリスト内の順位付けされたオブジェクトの最上位に来る。一実施形態では、負荷バランサは、当該ファイルをキャッシュしていないキャッシュサーバにファイルの要求を送信することによって複製の数を増やし、それによりそのキャッシュサーバに強制的に永続的な記憶域からファイルをダウンロードさせ、その後キャッシュさせる。
【００４２】
[0042]図３は、負荷平衡処理の一実施形態の流れ図である。この処理は、ハードウェア（回路、専用ロジック）、ソフトウェア（汎用コンピュータシステム若しくは専用の機械で実行されるものなど）、又はそれらの組み合わせからなる処理ロジックによって行われる。一実施形態では、負荷平衡処理は、図１のＬＢ２００などの負荷バランサによって行われる。
【００４３】
[0043]図３を参照すると、処理は、処理ロジックがクライアントからファイル要求を受け取ることから開始する（処理ブロック３１１）。ファイル要求に応答して、処理ロジックは、要求ファイルがキャッシュされているかどうかを調べ、キャッシュされている場合はどこにキャッシュされているかを調べる（処理ブロック３１２）。
【００４４】
[0044]次に、処理ロジックはファイルの人気度を判定し（処理ブロック３１３）、ファイルの複製を増やすか否かを決定する（処理ブロック３１４）。処理ロジックは、要求と複製（存在する場合）を送信する先の（１つ又は複数の）キャッシュノード（例えばキャッシュサーバ、ＶＭ等）を選択し（処理ブロック３１５）、要求をそのキャッシュノードと、複製をキャッシュする（１つ又は複数の）キャッシュノードに送信する（処理ブロック３１６）。ファイルの１つ又は複数の複製をキャッシュする場合に、負荷バランサが、まだそのファイルをキャッシュしていないキャッシュノードに要求を送信すると、そのキャッシュノードは永続的な記憶域（例えば図１の永続的な記憶域５００）からファイルのコピーを取得し、それにより、別のキャッシュノードに既にファイルのコピーがある場合に複製を作成する。その後、処理は終了する。
【００４５】
[0045]本明細書に記載される負荷バランサのいくつかの実施形態の主要な利点の１つは、キャッシュサーバがシステムに追加されると直ちに等しく重要になり、一旦等しく重要になると、どのキャッシュサーバを停止させてもよいことである。これにより、使用するキャッシュサーバの数の決定をキャッシュサーバの内容に関係なく行うことができ、停止する（１つ又は複数の）キャッシュサーバの決定は、リースの満了時間が最も近づいているキャッシュサーバに基づいて行うことができるため、規模の拡大／縮小の決定が平易になる。一方、システムがキャッシュサーバを増やすことを決定した場合、システムはシステム全体の目標に従って負荷の公平な分担の判断を迅速に開始することができる。
【００４６】
[0046]そのようにして、負荷バランサは、オブジェクトの人気度、到着プロセス、及びサービスの分布についての知識を一切持たずに、２つの目標、すなわちサーバ間の負荷の分散をより均一にすることと、総キャッシュヒット率を最大に近い率に保つことを達成する。
【００４７】
Ａ．オフラインの中央化方式の解決法
[0047]一実施形態では、種々のオブジェクトの人気度について事前の知識があることを前提とする中央化された複製の解決法が使用される。この解決法では、最も人気のあるオブジェクトをキャッシュし、そのうち上位数個のオブジェクトのみを複製する。そのため、総キャッシュヒット率は最大近くに保たれる。一般性を失うことなく、オブジェクトが人気度の高い順に索引付けされるものとする。各オブジェクトｉについて、ｒｉはそのオブジェクトを記憶するために割り当てられたキャッシュサーバの数を表す。ｒｉの値とそれに対応するキャッシュサーバの集合は、種々のオブジェクトの人気度の相対的な順位付けに基づいてオフラインで決定される。ヒューリスティック（Hueristic）がｉ＝１，２，３，．．．に繰り返され、各反復で、オブジェクトｉのコピーを記憶するために
【数１２】
2015072682.tif 000014
個のキャッシュサーバが割り当てられる。一実施形態では、１つのオブジェクトが持つことができるコピーの所定の最大数をＲ≦Ｋとする。ｉ回目の反復で、それに先立つｉ−１回の反復（オブジェクト１〜ｉ−１）で割り当てられたオブジェクトがＣ個未満であれば、そのキャッシュサーバは利用可能である。利用可能なキャッシュサーバごとに、前回までの反復で割り当てられたオブジェクトの合計の人気度を最初に算出し、次いで、オブジェクトの合計の人気度が最も低い
【数１３】
2015072682.tif 000015
個の利用可能サーバがオブジェクトｉを記憶するために選択される。この反復処理は、利用可能なキャッシュサーバがなくなるまで、又はすべてのオブジェクトがいくつかのサーバに割り当てられるまで継続する。この集中型のヒューリスティックでは、各キャッシュサーバは自身に割り当てられたオブジェクトのみをキャッシュする。そのため、一実施形態では、キャッシュされているオブジェクトに対する要求は、無作為に均等に選択される対応するキャッシュサーバの１つに送られ、一方、キャッシュされていないオブジェクトの要求は、均等且つ無作為に選択されたサーバに送られ、そのサーバが永続的な記憶域からオブジェクトを供給するが、オブジェクトをキャッシュすることはしない。オブジェクトの人気度は典型的なジップ分布に従い（ジップ指数＝１）、各オブジェクトのコピーの数はその人気度に比例することに留意されたい。
【００４８】
Ｂ．オンラインの解決法
[0048]別の実施形態では、記憶システムは、人気度の分布の事前の知識を必要としないオンラインの確率的な複製のヒューリスティックを使用し、各キャッシュサーバは、ローカルキャッシュの置き換えポリシーとしてＬＲＵアルゴリズムを使用する。人気度の分布についての知識がないことを前提とするので、個々のキャッシュサーバで保持されるローカルのＬＲＵリストに加えて、負荷バランサは、クライアントから最後にアクセスされた時間に基づいてソートされた固有のオブジェクトの索引を記憶した全体的なＬＲＵリストを維持し、それによりオブジェクトの相対的な人気度の順位を推定する。このリストの先頭（一方の端）には最も最近要求があったオブジェクトの索引が記憶され、リストの末尾（他方の端）には、最後に要求されてからの時間が最も長いオブジェクトの索引が記憶される。
【００４９】
[0049]オンラインのヒューリスティックは、（１）人気度が高いオブジェクトほど複製の度合いを高くする（コピーをより多くする）べきであり、（２）頻繁に全体ＬＲＵリストの先頭に現れるオブジェクトは、末尾にとどまっているオブジェクトよりも人気がある可能性が高い、という考察に基づいて設計される。
【００５０】
[0050]オンラインのヒューリスティックの第１の基本の実施形態では、オブジェクトｉの読み出し要求が到着すると、負荷バランサはまずｉがキャッシュされているか否かを調べる。キャッシュされていない場合、要求は無作為に選択されたキャッシュサーバに送られ、そのサーバにオブジェクトをキャッシュさせる。オブジェクトｉが集合
【数１４】
2015072682.tif 000016
にあるＫ個のサーバすべてで既にキャッシュされている場合には、要求は無作為に選択されたキャッシュサーバに送られる。オブジェクトｉが
【数１５】
2015072682.tif 000017
にあるｒｉ個のサーバ（１≦ｒｉ＜Ｋ）に既にキャッシュされている場合、負荷バランサはさらに、ｉが全体ＬＲＵリストの上位Ｍ個以内にあるかどうかを調べる。上位Ｍ個以内にある場合、オブジェクトは非常に人気があると考えられ、負荷バランサは下記のようにｒｉを確率的に１だけ増分する。１／（ｒｉ＋１）の確率の場合、要求は、
【数１６】
2015072682.tif 000018
にない無作為に選択された１つのキャッシュサーバに送られ、したがってｒｉは１増加される。それ以外の場合（確率ｒｉ／（ｒｉ＋１）の場合）、要求は
【数１７】
2015072682.tif 000019
にあるサーバの１つに送られる。したがってｒｉは変更されない。一方、オブジェクトｉが全体ＬＲＵリストの上位Ｍ個の項目にない場合は、十分には人気がないと考えられる。そのような場合、要求は
【数１８】
2015072682.tif 000020
にあるサーバの１つに送られ、したがってｒｉは変更されない。この際、ｒｉの増大率はｒｉが大きくなるにつれて低下する。この設計は、あまり人気がないオブジェクトの不必要なコピーを作り過ぎないようにする効果がある。
【００５１】
[0051]代替実施形態では、オンラインのヒューリスティックの第２の選択的バージョンが使用される。この選択的バージョンは、キャッシュされていないオブジェクトに対する要求の処理法が基本バージョンと異なる。選択的バージョンでは、負荷バランサは、オブジェクトの順位が全体ＬＲＵリスト内で閾値ＬＲＵｔｈｒｅｓｈｏｌｄ≧Ｍ未満であるかどうかを調べる。閾値未満の場合、オブジェクトは非常に人気がないと考えられ、オブジェクトをキャッシュすると、より人気のあるオブジェクトをエビクトさせる可能性が高い。この場合、キャッシュノード（例えばキャッシュサーバ）に要求を送る際、負荷バランサは要求に「ＣＡＣＨＥ  ＣＯＮＳＣＩＯＵＳＬＹ（意識的にキャッシュする）」フラグを付加する。このフラグが付加された要求を受け取ると、キャッシュノードは通常通り永続的な記憶域からオブジェクトをクライアントに提供するが、自身のローカル記憶域がいっぱいでない場合に限りオブジェクトをキャッシュする。このような選択的なキャッシング機構は、当初人気がなかったオブジェクトｉが急に人気が出た場合にはｒｉの増加を防ぐことができない。この理由はオブジェクトが一旦人気が出ると、全体ＬＲＵリストの応答性のために、その順位がＬＲＵｔｈｒｅｓｈｏｌｄを上回ったままとなるためである。
【００５２】
キャッシュスケーラの実施形態
[0052]一実施形態では、キャッシュスケーラが、必要なキャッシュサーバすなわちノードの数を決定する。一実施形態では、キャッシュスケーラは、次回の期間ごとにこの決定を行う。キャッシュスケーラはキャッシュサーバから統計値を収集し、その統計値を使用して決定を行う。キャッシュスケーラが必要なキャッシュサーバの数を決定すると、キャッシュスケーラは、その必要な数を満たすようにキャッシュサーバを作動開始及び／又は停止させる。そのために、キャッシュスケーラは、数を減らしたい場合は、どの（１つ又は複数の）キャッシュサーバを停止させるかも決定する。この決定は、使用されている記憶リソースに対応するリースの満了時刻に基づくことができる。
【００５３】
[0053]図４は、キャッシュスケーリング処理の一実施形態の流れ図である。この処理は、ハードウェア（回路、専用ロジック）、ソフトウェア（汎用コンピュータシステム若しくは専用の機械で実行されるものなど）、又はそれらの組み合わせからなる処理ロジックによって行われる。
【００５４】
[0054]図４を参照すると、処理は、処理ロジックが各キャッシュノード（例えばキャッシュサーバ、仮想機械（ＶＭ）等）から統計値を収集することから開始する（処理ブロック４１１）。一実施形態では、キャッシュスケーラは、キャッシング階層の要求の未処理量を使用して、アクティブなキャッシュサーバの数を動的に調整する。
【００５５】
[0055]統計値を使用して、処理ロジックは、次の期間のキャッシュノードの数を決定する（処理ブロック４１２）。処理ロジックがキャッシュノードの数を増やすと決定した場合、処理は処理ブロック４１４に進み、処理ロジックがキャッシュ階層に「作動開始」要求を発行する。処理ロジックがキャッシュノードの数を減らすと決定した場合は、処理は処理ブロック４１３に進み、処理ロジックは、停止する（１つ又は複数の）キャッシュノードを選択し、「停止」要求をキャッシュ階層に発行する（処理ブロック４１５）。一実施形態では、現在のリース期間が最初に満了するキャッシュノードが選択される。停止させるキャッシュノードを選択する方法は他にもある（例えば最後に作動を開始するキャッシュノード）。
【００５６】
[0056]「停止」要求又は「作動開始」要求をキャッシュ階層に発行した後、処理は処理ブロック４１６に進み、処理ロジックがキャッシュ階層からの確認を待機する。確認が受信されると、処理ロジックは、使用中のキャッシュノードのリストで負荷バランサを更新し（処理ブロック４１７）、処理が終了する。
【００５７】
[0057]図５は、要求の未処理量に基づいてキャッシュのスケーリングを実施する状態機械の一実施形態を示す図である。図５を参照すると、状態機械は次の３つの状態を含む。
【００５８】
ＩＮＣ  アクティブなサーバの数を増やす
【００５９】
ＳＴＡ  アクティブなサーバの数を固定する
【００６０】
ＤＥＣ  アクティブなサーバの数を減らす
一実施形態では、スケーリングは時間分割方式で動作する。すなわち、時間を同じ大きさ、例えばＴ秒（例えば３００秒）の区間に分割し、状態遷移は区間の境界のみで発生する。１区間内では、アクティブなキャッシュノードの数は固定された状態を保つ。個々のキャッシュノードは、１区間にわたり、時間で平均した状態情報、例えば未処理量、遅延パフォーマンス、ヒット率等を収集する。一実施形態では、遅延パフォーマンスは、クライアント要求に応えるための遅延であり、要求が受信されてから、クライアントがデータを取得するまでの時間である。データがキャッシュされている場合、遅延は、キャッシュノードからクライアントにデータを転送する時間となる。データがキャッシュされていない場合は、データを永続的な記憶域からキャッシュノードにダウンロードする時間が追加される。現在の区間の最後までに、キャッシュスケーラは各キャッシュノードから情報を収集し、図５で次の区間に現在の状態にとどまるか、新しい状態に遷移するかを決定する。そして、それに応じて次の区間に使用するアクティブなキャッシュノードの数が決定される。
【００６１】
[0058]Ｓ（ｔ）及びＫ（ｔ）を使用して、それぞれ区間ｔにおける状態とアクティブなキャッシュノードの数を表す。区間ｔにおけるキャッシュノードｉの時間平均した待ち行列の長さをＢｉ（ｔ）とし、これは、区間内に時間δごとに取得されるサンプリングされた待ち行列の長さの平均である。そして、区間ｔのノードごとの平均未処理量をＢ（ｔ）＝ΣｉＢｉ（ｔ）／Ｋ（ｔ）と表す。
【００６２】
[0059]実行時に、キャッシュスケーラは、（１）遅延を低くするために未処理量が蓄積するのを防ぐために必要なキャッシュノードの最小数Ｋｍｉｎ、及び（２）それを超えると遅延の改善がごく小さくなるキャッシュノードの最大数Ｋｍａｘ、の２つの推定値を維持する。状態ＤＥＣ（又はＩＮＣ）では、ヒューリスティックは（又はＫｍａｘ）に向かうように徐々にＫ（ｔ）を調整する。平均の未処理量Ｂ（ｔ）が所望の範囲内になると、ヒューリスティックは直ちにＳＴＡ状態に遷移し、この状態ではＫ（ｔ）が固定される。図６は、それぞれ状態ＳＴＡ、ＩＮＣ、及びＤＥＣにおける適合動作の一実施形態の疑似コードを含むアルゴリズム１、２、及び３を説明する図である。
【００６３】
Ａ．ＳＴＡ状態−Ｋを固定する
[0060]ＳＴＡは、キャッシュごとの未処理量Ｂ（ｔ）が所定の目標範囲（γ１，γ２）内にある限り大半の時間に記憶システムがあるべき状態である、この状態ではＫ（ｔ）が固定される。Ｋ（ｔ０）個のアクティブなキャッシュノードがある区間ｔ０に、Ｂ（ｔ０）がγ２よりも大きくなった場合には、所望の遅延パフォーマンスを得るには未処理量が多過ぎると考えられる。この状況では、キャッシュスケーラは状態ＩＮＣに遷移し、この状態ではＫｍａｘを目標値としてＫ（ｔ）が増加される。一方、Ｂ（ｔ０）がγ１よりも小さくなると、キャッシュノードは十分に利用されていないと考えられ、システムリソースが無駄になる。この場合、キャッシュスケーラは状態ＤＥＣに遷移し、この状態ではＫ（ｔ）がＫｍｉｎに向かって減らされる。Ｋｍａｘが維持される方式に応じて、ＳＴＡからＩＮＣへの遷移が発生した時にＫ（ｔ０）＝Ｋｍａｘとなり、下記の式１が定数Ｋ（ｔ０）になる可能性がある。この場合は、アルゴリズム１の行５でＫｍａｘが２Ｋ（ｔ０）に更新されて、Ｋ（ｔ）が確実に増大するようにする。
【００６４】
Ｂ．ＩＮＣ状態−Ｋを増加する
[0061]状態ＩＮＣでは、アクティブなキャッシュノード（例えばキャッシュサーバ、ＶＭ等）の数が増やされる。一実施形態では、アクティブなキャッシュノードの数が３次成長関数、
【数１９】
2015072682.tif 000021
に従って増分され、ただし、α＝（Ｋｍａｘ−Ｋ（ｔ０））／Ｉ３＞０であり、ｔ０は状態ＳＴＡにおける直近の区間である。Ｉ≧１は、ＫをＫ（ｔ０）からＫｍａｘまで増加させるために上記関数が要する区間数である。式１を使用すると、アクティブなキャッシュノードの数は、ＳＴＡからＩＮＣに遷移した直後は非常に速く増大するが、Ｋｍａｘに近づくにつれて増大の率を低下させる。Ｋｍａｘ前後では増加はほぼゼロになる。Ｋｍａｘを超えると、キャッシュスケーラは、Ｋ（ｔ）が最初はゆっくり増大するより多くのキャッシュノードを探し始め、Ｋｍａｘから離れるにつれてＫ（ｔ）の増大を加速させる。このようにＫｍａｘの前後で増大を低下させることにより、適合の安定度を高め、一方、Ｋｍａｘから離れるにつれて増大が速くなることで、待ち行列の未処理量が多くなった場合に十分な数のキャッシュノードが迅速にアクティブになることを保証する。
【００６５】
[0062]Ｋ（ｔ）が増加される際、キャッシュスケーラは、未処理量の変動Ｄ（ｔ）＝Ｂ（ｔ）−Ｂ（ｔ−１）も監視する。大きいＤ（ｔ）＞０は、未処理量が現在の区間に大幅に増加したことを意味する。これは、Ｋ（ｔ）が、現在の作業負荷に対応するために必要なアクティブなキャッシュノードの最小数よりも小さいことを示唆する。したがって、Ｄ（ｔ）が所定の閾値Ｄｔｈｒｅｓｈｏｌｄ≧０より大きい場合は、アルゴリズム２の行２でＫｍｉｎがＫ（ｔ）＋１に更新される。式１は狭義単調増加関数であるため、Ｋ（ｔ）は最終的に必要な最小数よりも大きくなる。これが発生すると、変動は負になり、未処理量が減り始める。しかし、変動が負になってすぐにＫ（ｔ）の増加をやめることは望ましくない。その理由は、そのようにすると結果として小さな負の変動になる可能性が非常に高く、既に蓄積した未処理量を減らして望ましい範囲に戻すには長い時間を要するためである。したがって、アルゴリズム２では、キャッシュスケーラは、（１）現在の未処理量を１／γ３≧１区間以内に解消する大きな負の変動Ｄ（ｔ）＜−γ３Ｂ（ｔ）が認められる場合、又は（２）未処理量Ｂ（ｔ）が望ましい範囲である＜γ１に戻った場合にのみＳＴＡ状態に遷移する。この遷移が発生すると、ＫｍａｘはＩＮＣ状態で使用された最後のＫ（ｔ）に更新される。
【００６６】
Ｃ．ＤＥＣ状態−Ｋを減少させる
[0063]ＤＥＣ状態の動作はＩＮＣ状態の動作と同様であるが、方向が逆になる。一実施形態では、Ｋ（ｔ）が次の３次減少関数に従って調整される。
【数２０】
2015072682.tif 000022
ここで、α＝（Ｋｍｉｎ−Ｋ（ｔ０））／Ｒ３＜０であり、ｔ０は状態ＳＴＡにおける直近の区間である。Ｒ≧１は、ＫをＫｍｉｎまで減らすために必要な区間数である。一実施形態では、要求に応えるキャッシュノードが常に少なくとも１つなければならないため、Ｋ（ｔ）の下限を１とする。Ｋ（ｔ）が減少するにつれて、各キャッシュノードの利用レベルと未処理量が増大する。未処理量が増加して望ましい範囲である＞γ１に戻ると、キャッシュスケーラは直ちにＫを減少させるのをやめ、ＳＴＡ状態に切り替わり、ＫｍｉｎをＫ（ｔ）に更新する。一実施形態では、そのような遷移が起こると、Ｋ（ｔ＋１）がＫ（ｔ）＋１に等しく設定されて、その後の区間でＢの些少な揺らぎのためにキャッシュスケーラが不必要にＤＥＣに戻ることを決定しないようにする。
【００６７】
コンピュータシステムの例
[0064]図７は、図１及び図２の構成要素の１つ又は複数を実施するコンピュータシステムのブロック図である。図７を参照すると、コンピュータシステム７１０は、コンピュータシステム７１０の下位システムを相互接続するバス７１２を含み、下位システムには、プロセッサ７１４、システムメモリ７１７（例えばＲＡＭ、ＲＯＭ等）、入出力（Ｉ／Ｏ）コントローラ７１８、ディスプレイアダプタ７２６を介した表示画面７２４などの外部装置、シリアルポート７２７及び７３０、キーボード７３２（キーボードコントローラ７３３とインターフェースをとる）、記憶インターフェース７３４、フロッピーディスク７３７を収容するように動作するフロッピーディスクドライブ７３７、ファイバーチャネルネットワーク７９０に接続するように動作するホストバスアダプタ（ＨＢＡ）インターフェースカード７３５Ａ、ＳＣＳＩバス７３９に接続するように動作するホストバスアダプタ（ＨＢＡ）インターフェースカード７３５Ｂ、並びに光ディスクドライブ７４０などがある。また、マウス７４６（又は、シリアルポート７２７を介してバス７１２に接続された他のポイント・クリック式装置）、モデム７４７（シリアルポート７３０を介してバス７１２に結合される）、及びネットワークインターフェース７４８（バス７１２に直接結合される）も含まれる。
【００６８】
[0065]バス７１２は、中央のプロセッサ７１４とシステムメモリ７１７間のデータ通信を可能にする。システムメモリ７１７（例えばＲＡＭ）は、一般に、オペレーティングシステム及びアプリケーションプログラムがロードされる主記憶とすることができる。ＲＯＭ又はフラッシュメモリは、各種コードの中でも特に、周辺構成要素との対話などの基本的なハードウェア動作を制御する基本入出力システム（ＢＩＯＳ）を保持することができる。コンピュータシステム７１０に常駐するアプリケーションは、一般に、ハードディスクドライブ（例えば固定ディスク７４４）、光学ドライブ（例えば光学ドライブ７４０）、フロッピーディスク装置７３７、又は他の記憶媒体などのコンピュータ読み取り可能な媒体に記憶され、その媒体を介してアクセスされる。
【００６９】
[0066]記憶インターフェース７３４は、コンピュータシステム７１０の他の記憶インターフェースと同様に、固定ディスクドライブ７４４など情報を記憶及び／又は検索するための標準的なコンピュータ読み取り可能な媒体に接続することができる。固定ディスクドライブ７４４は、コンピュータシステム７１０の一部であっても、又は独立し、他のインターフェースシステムを通じてアクセスされてもよい。
【００７０】
[0067]モデム７４７は、電話リンクを介してリモートサーバへの直接の接続、又はインターネットサービスプロバイダ（ＩＳＰ）（例えば図１のキャッシュサーバ）を介してインターネットへの接続を提供することができる。ネットワークインターフェース７４８は、リモートサーバ、例えば図１のキャッシュ階層４００のキャッシュサーバへの直接の接続を提供することができる。ネットワークインターフェース７４８は、ＰＯＰ（point of presence）を介してインターネットへの直接のネットワークリンクを介してリモートサーバ（例えば図１のキャッシュサーバ）への直接の接続を提供することができる。ネットワークインターフェース７４８は、デジタルの携帯電話接続、パケット接続、デジタル衛星データ接続等の無線技術を使用してそのような接続を提供することができる。
【００７１】
[0068]多くの他の装置又は下位システム（図示せず）を同様にして接続することができる（例えば文書スキャナ、デジタルカメラ等）。逆に、図７に示す装置のすべてが本明細書に記載される技術を実施するために存在する必要があるとは限らない。装置及び下位システムは、図７とは異なる形で相互接続することができる。図７に示すようなコンピュータシステムの動作は、当技術分野では容易に理解され、本出願では詳細には説明しない。
【００７２】
[0069]本明細書に記載のコンピュータシステムの動作を実施するコードは、システムメモリ７１７、固定ディスク７４４、光ディスク７４２、又はフロッピーディスク７３７の１つ又は複数などのコンピュータ読み取り可能な記憶媒体に記憶することができる。コンピュータシステム７１０に備えられるオペレーティングシステムは、ＭＳ−ＤＯＳ（登録商標）、ＭＳ−ＷＩＮＤＯＷＳ（登録商標）、ＯＳ／２（登録商標）、ＵＮＩＸ（登録商標）、Ｌｉｎｕｘ（登録商標）、又は別の知られるオペレーティングシステムとすることができる。
【００７３】
[0070]図８は、図７に示すコンピュータシステムなどのコンピュータシステムの一実施形態のメモリに記憶されるコード（例えばプログラム）及びデータのセットを示す。コンピュータシステムは、プロセッサと連携してこのコードを使用して本明細書に記載される    を実施するために必要な動作（例えば論理演算）を実装する。
【００７４】
[0071]図８を参照すると、メモリ８６０は負荷平衡モジュール８０１を含み、このモジュールはプロセッサに実行されると、上記のように負荷平衡を行う役割を担う。メモリはキャッシュスケーリングモジュール８０２も記憶し、このモジュールはプロセッサに実行されると、上記のキャッシュスケーリング動作を行う役割を担う。メモリ８６０は送信モジュール８０３も記憶し、このモジュールはプロセッサに実行されると、例えばネットワーク通信を使用してキャッシュ階層及びクライアントにデータを送信させる。メモリは、他の装置（例えばサーバ、クライアント等）と通信（例えばネットワーク通信）を行うために使用される通信モジュール８０４も含む。
【００７５】
[0072]上述の説明を読むと当業者には多くの本発明の変更及び改変が明らかになるものと思われるが、例示として図示し説明したどの特定の実施形態も制限的と解釈すべきでないことを理解されたい。したがって、各種実施形態の詳細事項の言及は特許請求の範囲を制限するものではなく、特許請求の範囲は基本的に本発明に必須と考えられる特徴のみを列挙する。
【符号の説明】
【００７６】
１００  クライアント
２００  負荷バランサ
２０１  入出力要求
２０２  入出力応答
２１０  ロケーションマッパー
３００  キャッシュスケーラ
３１０  キャッシュ性能モニタ
４００  キャッシュ階層
４１０  ローカル記憶域
５００  永続的な記憶域
７１０  コンピュータシステム
７１２  バス
７１４  プロセッサ
７１７  システムメモリ
７１８  Ｉ／Ｏコントローラ
７２４  表示画面
７２６  ディスプレイアダプタ
７２７、７３０  シリアルポート
７３２  キーボード
７３３  キーボードコントローラ
７３４  記憶インターフェース
７３５Ａ、７３５Ｂ  ＨＢＡインターフェースカード
７３７  フロッピーディスク
７３９  ＳＣＳＩバス
７４０  光ディスクドライブ
７４２  光ディスク
７４４  固定ディスク
７４６  マウス
７４７  モデム
７４８  ネットワークインターフェース
７９０  ファイバーチャネルネットワーク
８０１  負荷平衡モジュール
８０２  スケーリングモジュール
８０３  送信モジュール
８０４  通信モジュール
【図１】
2015072682.tif 000023
【図２】
2015072682.tif 000024
【図３】
2015072682.tif 000025
【図４】
2015072682.tif 000026
【図５】
2015072682.tif 000027
【図７】
2015072682.tif 000028
【図８】
2015072682.tif 000029
【図６】
2015072682.tif 000030
【外国語明細書】
2015072682000001.pdf