"複数のマシンのメモリ状態を1組の1つ又は複数のバックアップノード上に同期させるための方法であって、事前に符号化された変更を前記1つ又は複数のバックアップノードの各々において受信するステップであって、事前に符号化された変更が、前記複数のマシンの各1つ又は複数についての前記メモリ状態に対する変更を事前に符号化することによって生成されるステップと、前記複数のマシンの2つ以上にわたって、前記事前に符号化された変更を符号化することによって、符号化されたメモリ状態を生成するステップと、を含む方法。前記複数のマシンの前記1つ又は複数についての前記メモリ状態に対する、前記事前に符号化された変更が、各マシンのメモリ状態に対する更新と、前記各マシンの前記メモリ状態の直前のバージョンとに基づいて計算される、請求項1に記載の方法。各マシンの前記メモリ状態に対する前記更新と、前記各マシンの前記メモリ状態の前記直前のバージョンとの間のビット毎の排他的ORXOR演算を実行して、前記事前に符号化された変更を生成するステップと、前記事前に符号化された変更を前記1つ又は複数のバックアップノードの各々に送信するステップと、をさらに含む、請求項1に記載の方法。前記事前に符号化された変更を符号化することによって、前記符号化されたメモリ状態を生成するステップが、前記1つ又は複数のバックアップノードの前記各々において行われる、請求項1に記載の方法。前記符号化されたメモリ状態を生成するステップが、前記複数のマシンのうちの異なるマシンのメモリページにわたって、ビット毎の排他的ORXOR演算を実行するサブステップを含む、請求項4に記載の方法。1つの物理ロケーションに配置された前記バックアップノードの1つにおいて、前記複数のマシンの1つについてのメモリ状態を、前記1つのマシンが故障した場合に、復旧するステップと、その後、前記物理ロケーションにおいて、前記復旧されたメモリ状態を用いて、仮想マシンを活動化するステップと、をさらに含む、請求項5に記載の方法。1つの物理ロケーションに配置された前記バックアップノードの1つにおいて、前記複数のマシンの1つについてのメモリ状態を、前記1つのマシンが故障した場合に、復旧されたメモリ状態のサブセットを復号することによって復旧するステップと、その後、復旧されたメモリ状態の前記サブセットを用いて、仮想マシンを活動化するステップと、をさらに含む、請求項1に記載の方法。前記符号化されたメモリ状態を生成するステップが、前記複数のマシンと前記1つ又は複数のバックアップノードとの間に通信可能に結合された仲介ノードにおいて、ネットワーク符号化を実行するサブステップであって、前記複数のマシンのうちの異なるマシンのメモリページにわたって、ビット毎の排他的ORXOR演算を実行することを含むサブステップを含み、前記方法が、前記符号化されたメモリ状態を前記1つ又は複数のバックアップノードに送信するステップをさらに含む、請求項1に記載の方法。前記1つ又は複数のバックアップノードの1つにおいて、前記複数のマシンのうちの故障した1つについての1つ又は複数のメモリ状態を、前記複数のマシンのうちの故障していない異なるマシンのメモリページにわたって、ビット毎の排他的ORXOR演算を実行することによって、前記仲介ノードにおいて、ネットワーク符号化を実行して、新しい符号化されたメモリ状態を生成し、前記新しい符号化されたメモリ状態を前記1つ又は複数のバックアップノードのうちの少なくとも1つに送信し、前記新しい符号化されたメモリ状態と、前記少なくとも1つのバックアップノードに以前に記憶された符号化されたメモリ状態との間のビット毎の排他的ORXOR演算を実行することによって、故障した前記マシンのメモリページを生成することによって復旧するステップをさらに含む、請求項8に記載の方法。前記マシンが、仮想マシン又は物理マシンである、請求項1に記載の方法。1組の1つ又は複数のバックアップノードに通信可能に結合された複数のマシンを備え、前記複数のマシンが、事前に符号化された変更を生成し、前記1つ又は複数のバックアップノードの各々に送信し、複数のマシンが、前記複数のマシンの各1つ又は複数についての前記メモリ状態に対する変更を事前に符号化することによって、事前に符号化された変更を生成し、さらに、前記1組のうちの少なくとも1つのバックアップノードが、前記複数のマシンの2つ以上にわたって、前記事前に符号化された変更を符号化することによって、符号化されたメモリ状態を生成する、ネットワーク環境。少なくとも1つのマシンが、各マシンのメモリ状態に対する更新と、前記各マシンの前記メモリ状態の直前のバージョンとに基づいて、前記複数のマシンの前記1つ又は複数についての前記メモリ状態に対する、前記事前に符号化された変更を計算する、請求項11に記載のネットワーク環境。前記複数のマシンのうちの少なくとも1つのマシンが、前記1つのマシンの前記メモリ状態に対する前記更新と、前記1つのマシンの前記メモリ状態の前記直前のバージョンとの間のビット毎の排他的ORXOR演算を実行して、前記事前に符号化された変更を生成し、その後、前記事前に符号化された変更を前記1つ又は複数のバックアップノードの各々に送信する、請求項11に記載のネットワーク環境。前記1組のうちの少なくとも1つのバックアップノードが、前記事前に符号化された変更を符号化することによって、前記符号化されたメモリ状態を生成し、この生成が、前記1つ又は複数のバックアップノードの前記各々において行われる、請求項11に記載のネットワーク環境。前記少なくとも1つのバックアップノードが、前記複数のマシンのうちの異なるマシンのメモリページにわたって、ビット毎の排他的ORXOR演算を実行することによって、前記符号化されたメモリ状態を生成する、請求項14に記載のネットワーク環境。前記1組のうちの前記バックアップノードの前記少なくとも1つが、1つの物理ロケーションに配置され、前記複数のマシンの1つについてのメモリ状態を、前記1つのマシンが故障した場合に、復旧し、その後、前記物理ロケーションにおいて、前記復旧されたメモリ状態を用いて、仮想マシンを活動化する、請求項15に記載のネットワーク環境。1つ又は複数の仲介ノードを介して、1組の1つ又は複数のバックアップノードに通信可能に結合された複数のマシンを備え、前記複数のマシンが、事前に符号化された変更を生成し、前記1つ又は複数のバックアップノードの各々に送信し、複数のマシンが、前記複数のマシンの各1つ又は複数についての前記メモリ状態に対する変更を事前に符号化することによって、事前に符号化された変更を生成し、さらに、前記仲介ノードの少なくとも1つが、前記複数のマシンのうちの異なるマシンのメモリページにわたって、ビット毎の排他的ORXOR演算を実行することを含むネットワーク符号化を実行することによって、符号化されたメモリ状態を生成し、前記符号化されたメモリ状態を前記1つ又は複数のバックアップノードに送信する、ネットワーク環境。前記1つ又は複数のバックアップノードのうちの1つが、前記複数のマシンのうちの故障した1つのマシンについての1つ又は複数のメモリ状態を、新しい符号化されたメモリデータを使用し、前記新しい符号化されたメモリ状態と、前記少なくとも1つのバックアップノードに以前に記憶された符号化されたメモリ状態との間のビット毎の排他的ORXOR演算を実行することによって、故障した前記マシンのメモリページを生成することによって復旧し、さらに、前記新しい符号化されたメモリデータが、前記複数のマシンのうちの故障していない異なるマシンのメモリページにわたって、ビット毎の排他的ORXOR演算を実行することによって、新しい符号化されたメモリ状態を生成した前記仲介ノードの1つから受信される、請求項17に記載のネットワーク環境。前記マシンが、仮想マシン又は物理マシンである、請求項17に記載のネットワーク環境。システムによって実行された場合に、複数のマシンのメモリ状態を1組の1つ又は複数のバックアップノード上に同期させるための方法を前記システムに実行させる命令が記憶された、1つ又は複数の非一時的なコンピュータ可読記憶媒体を有する製造物品であって、前記方法が、事前に符号化された変更を前記1つ又は複数のバックアップノードの各々において受信するステップであって、事前に符号化された変更が、前記複数のマシンの各1つ又は複数についての前記メモリ状態に対する変更を事前に符号化することによって生成されるステップと、前記複数のマシンの2つ以上にわたって、前記事前に符号化された変更を符号化することによって、符号化されたメモリ状態を生成するステップと、を含む、製造物品。前記方法が、各マシンの前記メモリ状態に対する更新と、前記各マシンの前記メモリ状態の直前のバージョンとの間のビット毎の排他的ORXOR演算を実行して、前記事前に符号化された変更を生成するステップと、前記事前に符号化された変更を前記1つ又は複数のバックアップノードの各々に送信するステップと、をさらに含む、請求項20に記載の製造物品。前記符号化されたメモリ状態を生成するステップが、前記複数のマシンのうちの異なるマシンのメモリページにわたって、ビット毎の排他的ORXOR演算を実行するサブステップを含む、請求項20に記載の製造物品。前記符号化されたメモリ状態を生成するステップが、前記複数のマシンと前記1つ又は複数のバックアップノードとの間に通信可能に結合された仲介ノードにおいて、ネットワーク符号化を実行するサブステップであって、前記複数のマシンのうちの異なるマシンのメモリページにわたって、ビット毎の排他的ORXOR演算を実行することを含むサブステップを含み、前記方法が、前記符号化されたメモリ状態を前記1つ又は複数のバックアップノードに送信するステップをさらに含む、請求項20に記載の製造物品。前記方法が、前記1つ又は複数のバックアップノードの1つにおいて、前記複数のマシンのうちの故障した1つについての1つ又は複数のメモリ状態を、前記複数のマシンのうちの故障していない異なるマシンのメモリページにわたって、ビット毎の排他的ORXOR演算を実行することによって、前記仲介ノードにおいて、ネットワーク符号化を実行して、新しい符号化されたメモリ状態を生成し、前記新しい符号化されたメモリ状態を前記1つ又は複数のバックアップノードのうちの少なくとも1つに送信し、前記新しい符号化されたメモリ状態と、前記少なくとも1つのバックアップノードに以前に記憶された符号化されたメモリ状態との間のビット毎の排他的ORXOR演算を実行することによって、故障した前記マシンのメモリページを生成することによって復旧するステップをさらに含む、請求項23に記載の製造物品。本発明は、物理マシン及び/又は仮想マシンを含む、バックアップストレージを使用するデータセンタ及びシステムの信頼性、並びにそれらの同期の分野に関し、より詳細には、本発明は、仮想ネットワーク、分散システムにおけるフォールトトレランス、及びインフラストラクチャ仮想化に関する。0008データセンタ及び他のバックアップ環境において符号化を使用するための方法及び装置が、本明細書で開示される。一実施形態では、複数のマシンのメモリ状態を1組の1つ又は複数のバックアップノード上に同期させるための方法は、事前に符号化された変更を1つ又は複数のバックアップノードの各々において受信するステップであって、複数のマシンの各1つ又は複数についてのメモリ状態に対する変更を事前に符号化することによって、事前に符号化された変更が生成されるステップと、複数のマシンの2つ以上にわたって、事前に符号化された変更を符号化することによって、符号化されたメモリ状態を生成するステップとを含む。本発明の実施形態の1つの利点は、本発明が、ちょうど適正な数のプライマリノードの間でバックアップリソースを共用することによって、適切な量のリソースを使用して、特定のレベルの信頼性例えば99.99の稼働時間を提供することを可能にすることである。別の利点は、本明細書で説明される技法を使用して、異なる仮想サーバの信頼性を独自のバックアップノード上に多重化することによって、事業者は、効率的でコスト効果のよい方式で、仮想サーバを運営するアプリケーションプロバイダに信頼性を提供することができるので、事業者がサービスとして信頼性を提供することを可能にすることである。本発明の詳細な説明0010本発明の実施形態は、複数のライブすなわち実際に動作中のマシンを1組のバックアップノード上に同期させる方法を含み、その結果、バックアップノードの数が削減される。一実施形態では、これは、ライブマシンにわたってメモリ状態を符号化し、線形独立な符号化を各バックアップノードに記憶することによって達成される。一般性を失うことなく、本開示の残りの部分は、もっぱら仮想マシンの観点から本発明を開示するが、本明細書で説明される技法は、仮想マシン及び物理マシンの両方に適用される。0011開示される本発明の実施形態は、ライブチェックポインティングlivecheckpointingのために、すべての仮想マシンVMにわたって非同期及び分散方式で行うことができる高速な符号化方式及び復号方式を提供する。アベイラビリティを高めるためにライブチェックポインティングを提供するこれらの既存のシステムとは対照的に、本発明の実施形態は、バックアップロケーションにおけるメモリフットプリントmemoryfootprintを削減する。この利点は、プライマリノード故障が、バックアップノードに記憶された符号化されたメモリ状態からメモリを復旧するステージを必要とするため、アベイラビリティの減少という犠牲を払って実現される。0012本発明の実施形態は、ネットワーク符号化networkcodingを使用することによって、ネットワークにおける同期帯域幅の量を削減するための機構を含む。本発明の実施形態は、n個の複数のプライマリノードを任意の個数kのバックアップノード上に記憶することを可能にするネットワーク符号化を提供するために、ネットワーク符号networkcodeを計算する。個数kは、信頼性要件及び故障確率に基づいて、計算することができる。0013以下の説明では、本発明のより完全な説明を提供するために、多くの詳細が説明される。しかし、これらの特定の詳細を伴わずとも本発明を実施できることは、当業者には明らかであろう。他の例では、本発明を曖昧にすることを避けるため、よく知られた構造及びデバイスは、詳細にではなくブロック図形式で示される。0014以下の詳細な説明には、コンピュータメモリ内のデータビットに施される操作のアルゴリズム及びシンボル表現によって提示される部分がある。これらのアルゴリズムによる説明及び表現は、仕事の内容を他の当業者に最も効果的に伝えるために、データ処理分野の当業者によって使用される手段である。アルゴリズムは、ここでは、また一般には、所望の結果をもたらす自己矛盾のないステップ系列であると考えられている。ステップは、物理的な量の物理的な操作を必要とするステップである。必ずしも必要ではないが、通常、これらの量は、記憶、転送、組み合わせ、比較、及び他の操作が可能な、電気的信号又は磁気的信号の形態を取る。主として一般的な用法上の理由から、これらの信号をビット、値、要素、シンボル、文字、項、又は数などと呼ぶことが、時に便利であることが分かっている。0015しかし、これらの用語及び類似の用語はすべて、適切な物理的な量に関連付けられており、これらの量に付けられた便利なラベルであるにすぎないことに留意されたい。別途特別に述べられない限り、以下の説明から明らかなように、説明の全体において、処理する、計算する、算定する、決定する又は表示するなどの用語を利用した説明は、コンピュータシステムのレジスタ及びメモリ内の物理的な電子的な量として表現されたデータを操作及び変形して、コンピュータシステムメモリ若しくはレジスタ、又は他のそのような情報記憶、伝送、若しくは表示デバイス内の物理的な量として同様に表現される他のデータに変える、コンピュータシステム又は類似の電子的コンピューティングデバイスのアクション及びプロセスを指していることが理解されよう。0016本発明は、本明細書のオペレーションを実行するための装置にも関する。この装置は、必要な目的のために特別に構成することができ、又はコンピュータ内に記憶されたコンピュータプログラムによって選択的に活動化若しくは再構成される汎用コンピュータを含むことができる。そのようなコンピュータプログラムは、フロッピー登録商標ディスク、光ディスク、CD-ROM、及び磁気光ディスクを含む任意のタイプのディスク、リードオンリメモリROM、ランダムアクセスメモリRAM、EPROM、EEPROM、磁気カード若しくは光カード、又は電子的命令を記憶するのに適した任意のタイプの媒体などの、しかしそれらに限定されない、コンピュータ可読記憶媒体内に記憶することができ、各コンピュータ可読記憶媒体は、コンピュータシステムバスに結合される。0017本明細書で提示されるアルゴリズム及び表示は、いずれか特定のコンピュータ又は他の装置に、本質的に関連するわけではない。本明細書の教示に従ったプログラムとともに、様々な汎用システムを使用することができ、又はより専門化された装置を構成して、必要な方法ステップを実行することが便利であると分かることもある。様々なこれらのシステムに必要な構成は、以下の説明から明らかになる。加えて、本発明は、いずれか特定のプログラミング言語に関連して説明されず、様々なプログラミング言語を使用して、本明細書で説明される本発明の教示を実施できることが理解されよう。0018マシン可読媒体は、マシン例えばコンピュータによって可読な形式で情報を記憶又は伝送するための任意の機構を含む。例えば、マシン可読媒体は、リードオンリメモリROM、ランダムアクセスメモリRAM、磁気ディスク記憶媒体、光記憶媒体、フラッシュメモリデバイスなどを含む。概要0019本発明の実施形態は、複数のアクティブな物理マシン又は仮想マシン本明細書ではプライマリノードと呼ばれるの現在のメモリ状態を、同じ1組のバックアップノード本明細書ではパリティノードと呼ばれる上に同期させるための機構を提供する。一実施形態では、この同期は、プライマリノードのメモリ状態に対して実行された変更を複数のバックアップノードにストリーミングすることによって実行される。重要なことに、本発明の実施形態は、バックアップノードにおいて、いくつかのストリームが受信され、一緒に符号化されて、任意の目標信頼性レベルすなわち故障から復旧する確率でマシン故障からの復旧を可能にするのに必要なメモリ量を圧縮するという点で、ライブチェックポインティングにおける現在の最先端技術とは対照的である。0020一実施形態では、バックアップノードにおける符号化は、次元がk×nのファンデルモンド行列Vandermondematrix又はコーシー行列Cauchymatrixの係数に基づいた線形符号化であり、ここで、nは、プライマリノードの数であり、kは、システムを復旧できる故障の数である。一実施形態では、本方法は、他のバックアップノードからデータを送信し、ファンデルモンド行列の逆行列を効率的に求めてデータを復旧することによって、故障の場合に復旧機構を使用して復旧を実行するステップも含む。0021各プライマリノードが、1~Lまでのインデックスを付けられた同じサイズのメモリページを有する場合に、N個のプライマリノードのメモリ状態をK個のバックアップノード上にライブチェックポインティングする一実施形態では、異なるプライマリノードが、様々な数のメモリページを有する場合、最も多数のメモリページを有するプライマリノードが、基準として使用され、パリティノードのメモリページは、すべてのプライマリノードにおける最大のメモリフットプリントに従って設定される。本発明の実施形態は、パリティノードzにおけるインデックスjのメモリページに対して、以下の線形符号化を使用する。ここで、は、ビット毎のXOR演算を表し、乗算は、線形独立な符号化を保証するために、十分に大きなガロア体、例えばGF216上で実行され、また、α値は、ファンデルモンド行列又はバックアップノードにおけるプライマリイメージの線形結合の係数である。0022図1は、一実施形態による、完全な分散及び非同期方式でライブチェックポイントがどのように実行されるかについてのデータフロー図を示している。図1を参照すると、時刻T1において、仮想マシン1VM1において動作するプロセスが、メモリページiを変更する書き込みオペレーションを実行する。この書き込みイベントは、メモリページに対してコミットされる前に捕捉される。メモリページが、値m1,iを有し、書き込み要求をコミットした後にm’1,iに更新される場合、VM1は、を計算し、すなわち、現在の値と新しい値の間のXORを計算する。したがって、VM1は、データを事前に符号化して、符号化されたデータメモリページデータを生成する。0023その後、VM1は、信頼できる通信例えばネットワークを介した有線又は無線通信を使用して、update1,iを各パリティノードに送信する。update1,iをパリティノードに送信するのと平行して、又はその後に、VM1は、書き込みオペレーションをメモリに対してコミットして、現在のメモリページ値m1,iを新しいメモリページ値m□1,iで置き換える。メッセージは、中継に異なる時間を費やすので、各パリティノードは、ある期間の後、最終的にupdate1,iを受信する。0024いったんパリティノードでは、各パリティノードが、線形符号化を実行する。一実施形態では、パリティノードzは、以下に従って新しいパリティ値を計算する。上記の演算を展開した場合、これは以下の式と等価である。言い換えると、古いエントリm1,iは、新しいエントリm’1,iによって置き換えられる。したがって、最終的な書き込みオペレーションは、VM1においてコミットされた書き込みオペレーションと同期して、符号化値を正常に維持する。0025XOR演算では、交換則及び結合則が成り立ち、これは、同じVMからの更新の順序を入れ替えることができ、又は複数のVMが更新を非同期に送信できることを意味することに留意されたい。図1は、2つのVMが、2つの異なる時刻に、パリティノードにおいて一緒に符号化されるそれぞれのローカルメモリページを更新しているケースを示している。時刻がT2<T1である場合でも、ステップ6の後に最後にコミットされる状態に変わりはないことに留意されたい。一実施形態では、プライマリノードは、特定の更新がコミットされたことを通知する肯定応答をパリティノードから受信するまで、タイムスタンプを有する更新をローカルに記憶する。復旧00261つ又は複数のVM故障が検出された場合、システムは、復旧ステージに入る。故障VMの数がKよりも、すなわちパリティノードの数よりも少ない場合、システムは、故障から正常に復旧することができる。故障復旧は、複数の方法で実行することができる。2つのそのような実施形態が、以下で開示される。0027一実施形態では、最初に、故障VMのすべてのメモリ状態が、異なるパリティノードにおいて復旧され、その後、VMが、パリティノードと同じ物理ロケーションにおいて活動化される。このモードは、復旧時間に関して時間がかかり、したがって、システム稼働時間は、負の影響を受ける。一実施形態では、復旧プロセスは、以下のように進行する。0028ステップ1:すべての機能中のVMは、未決の更新メッセージすなわち、パリティノードによってコミットされた旨の肯定応答を受信していない上述のように計算された更新と、各メモリページの現在の値を、すべての機能中のパリティノードに送信する。0029ステップ2:各パリティノードzは、VMxによって送信されたいずれかの未決の更新メッセージがすでにコミットされているかどうかを、シーケンス番号及びタイムスタンプを使用してチェックする。すでにコミットされている場合、対応するメッセージは無視される。コミットされていない更新は、現在の値との間でXORを求められ、今度は、その値と現在のパリティ値との間でXORが求められ、そのXORはαxz-1倍され、この最後の値と各メモリページにおける現在のパリティ値ez,iとの間のXORは、現在の符号化からVMxの情報を排除する。したがって、各パリティノードzのメモリページiにおける現在のパリティ値は、であり、ここで、Fは、故障VMの集合である。0030ステップ3:各パリティノードzは、すべてのiについてのez,iを、他のパリティノードに送信し、行列E=PrMFiがもたらされ、ここで、Prは、エントリがPij=αji-1の、K×Nのパリティ行列Pの縮小行列reducedmatrixであり、故障しなかったプライマリノードに対応する列を排除することによって獲得され、MFiは、x∈Fについてのエントリmx=x,iを有する、F×1の列ベクトルである。パリティ行列Pは事前に知られているので、Prも知られている。パリティ行列Pは、後で以下において、行列GのV部分として示される。0031ステップ4:各パリティノードは、Pr-1Eを計算して、紛失シンボルを復旧し、パリティノードxは、その第iのメモリページを、第xの故障ノードを用いて更新する。0032別の実施形態では、ステップ3及びステップ4が、以下のように変更される。ステップ3:各パリティノードは、各z□≠zについて、Pr-1x,zezを計算し、計算結果をパリティノードz□に送信し、ここで、Pr-1x,zは、行列の逆行列の第x行第x列である。ステップ4:各パリティノードzは、各メモリページiについて、各z□≠zからPr-1x,zezを収集し、mx,i=ΣPr-1x,zezを計算し、ここで、総和記号は、XOR演算を表す。0033別の実施形態では、復旧速度又は稼動時間を改善するため、各VMのメモリページには優先順位が付けられ、優先順位が記憶される。故障が検出された後、各故障VMについて、優先順位が最も高いメモリページが、上に列挙されたステップ1~ステップ4を使用して最初に復旧され、VMは、上位D個のメモリページが復号された後に活動化され、ここで、Dは、事前に設定された整数である例えば1、2、3など。プロセスが復号されていないメモリページにアクセスしようと試みた場合、要求されたメモリページが復号されるまで、プロセスはブロックされる。優先順位は、どのメモリページが最も頻繁にアクセスされるか、及び/又は直近にアクセスされたかを監視することによって、設定することができる。0034一実施形態では、本明細書で説明される技法は、多くの仮想マシンがサーバとして使用されるデータセンタ及びその信頼性に関する状況において使用され、本明細書で説明される技法は、低いハードウェアリソースコストで信頼性を提供するための方法を含む。他の実施形態は、データセンタの外部の分散ネットワーク環境において、仮想マシンに信頼性を与えることを含む。0035本発明の実施形態の1つの利点は、本発明が、ちょうど適正な数のプライマリノードの間でバックアップリソースを共用することによって、適切な量のリソースを使用して、特定のレベルの信頼性例えば99.99の稼働時間を提供することを可能にすることである。別の利点は、本明細書で説明される技法を使用して、異なる仮想サーバの信頼性を独自のバックアップノード上に多重化することによって、事業者は、効率的でコスト効果のよい方式で、仮想サーバを運営するアプリケーションプロバイダに信頼性を提供することができるので、事業者がサービスとして信頼性を提供することを可能にすることである。ネットワーク同期0036本発明のいくつかの実施形態は、複数のバックアップノードが、複数のプライマリマシン例えば、仮想マシン上でホストされ、REMUSに類似した機構によって同期が取られるサーバの符号化されたバックアップ状態を保持することを仮定する。本発明の実施形態は、バックアップ状態の符号化を、ネットワーク符号化の使用によってネットワークに分散させるための機構を含む。これは、バックアップノードにおける符号化処理を削減し、ネットワークにおける帯域幅利用を削減する。0037図3は、これらの技法の一例を示している。図3を参照すると、プライマリノードS1及びS2が、ノードBによってバックアップされ、ネットワーク内の経路が、S1からB及びS2からBへのトラフィックがRを通過するように、ルータRを含む場合、Rは、符号化ポイントとして識別され、RがS1からBへの同期ストリームをS2からBへの同期ストリームと合同で符号化できるように、符号化係数がRに分配される。この例では、メモリページs1及びs2は、Rにおいて、b=XORs1,s2として符号化され、したがって、RからBへのトラフィックは、p1及びp2ではなくbである。このケースでは、帯域幅削減は2分の1である。本発明の実施形態は、単一バックアップの場合における任意のトポロジを扱う。すなわち、本明細書で説明される技法は、任意のトポロジにおいてBによってバックアップされる任意の集合P1,...,PNのための符号化パラメータを識別できるように使用することができる。本発明の実施形態は、ツリートポロジの場合の複数バックアップケースも扱うことができる。複数のバックアップを有する他のトポロジの場合、既存のトポロジを利用して、トポロジ内のx個のツリーを見出し、見出されたすべてのツリーに本発明の実施形態を適用する拡張を使用することができる。0038本発明の実施形態を用いて構成された同じ符号を使用して、復旧帯域幅を削減し、可能性としては最小化することができる。例えば、ノードBが、3つのプライマリノードを、XORs1,s2,s3という符号化を用いてバックアップする場合に、プライマリノードS3が故障したとき、仲介ルータRにおける故障ノードS3が存在しない同じ符号化を使用して、バックアップノードBにおいてs3のメモリページを復旧することができる。ルータRにおいて符号化が実行されない場合、このケースにおける帯域幅削減は、2分の1である。0039本発明の実施形態は、x>1であるx個のプライマリノードが故障した場合は、復旧の第2ステージを規定する。このステージは、部分的に復号されたデータをx個のバックアップノードの間で交換することによって、x個のプライマリノードを完全に復旧するために必要である。基本的に、それは、逆行列を求めるための分散実行である。ネットワーク内で実行される場合、それは、x個のバックアップノードを用いる同期方法の、x個のバックアップノード自体への適用である。0040少なくとも1つの実施形態は、WAN又はワイヤレスインタフェースを介したネットワークなど、同期帯域幅と比較した場合に帯域幅が制限されたネットワークを介して、1組のプライマリノードが、別の1組のバックアップノードを使用するためのものである。0041少なくとも1つの実施形態の1つの利点は、おそらく最少量の帯域幅を使用して、プライマリノードとバックアップノードを同期させることである。本発明の少なくとも1つの実施形態の別の利点は、その実施形態が、故障したバックアップされたノードの状態を最大でk個まで復旧するための、ネットワーク分散型の復旧機構を提供することである。同期のための符号化0042以下の式は、バックアップノードにおける符号化方式の一実施形態を記述している。ここで、s1...snは、それぞれプライマリノードS1...Snのメモリページの列ベクトルであり、b1...bkは、それぞれバックアップノードB1...Bkの符号化されたメモリページの列ベクトルであり、Gは、符号を生成する生成行列であり、単位行列Iとファンデルモンド行列Vの連結を表す。Gの第nj列は、メモリページs1...snがどのように符号化され、バックアップノードBjに記憶されるかを表す。一実施形態では、復号を効率的に行うことができるので、ファンデルモンド行列がここで選択される。別の実施形態では、コーシー行列を使用することができる。0043データbjがバックアップノードBjに記憶されることを保証するための1つの明らかな方法は、すべてのプライマリノードS1...Snにそれぞれのデータs1...snをノードB1...Bkにユニキャストさせ、符号化がバックアップノードのみで実行されるようにすることである。これは、nk個の接続を使用する帯域幅集約的な動作である。マルチキャストは、帯域幅を削減するのに役立つことがあるが、ネットワーク内での符号化の実行は、帯域幅をさらに削減し、また符号化タスクをネットワークに委譲する。本発明の実施形態は、バックアップノードが、Gに従って符号化された適切なデータを受信するように、ネットワークにおいて符号化を実行するための方法を提供する。これは、後により詳細に説明される。プライマリノード故障が1つの場合の復旧手順0044プライマリノードSiをノードBj上で復旧する場合、その目標は、符号化されたデータを、Si内の元のメモリページであるsiに復号することである。それを行うため、残りのn-1個のプライマリノードは、それらのメモリページを、同期のために設計された同じネットワーク符号を使用して、バックアップノードBjに送信する。その後、ノードBjは、に等しい符号化されたデータを受信する。0045バックアップノードBjは、この符号化されたデータとそれ自体の符号化されたデータbjとの間のXORを求め、XOR演算の結果を係数を用いて正規化することによって、プライマリノードSiへの復旧を完了する。0046図4は、復旧の一例を示している。図4を参照すると、ノードBは、一緒にXORを求めたS1、S2、S3を表す符号化されたデータを記憶する。ノードS3が故障した場合、Rは、S1及びS2からのデータの間でXORを求めて、それらのデータを符号化し、符号化されたデータをノードBに送信する。ノードBは、Rから受信した符号化されたデータとノードBに記憶された符号化されたデータとの間でXORを求めて、S3を復旧する。プライマリノード故障が2つ以上の場合の復旧手順0047Sが、故障したVMのインデックス集合を表すとし、Bが、復旧を行うためのそれぞれのバックアップノードのインデックス集合を表すとする。一実施形態では、復旧は、2つのステージにおいて実行される。第1のステージは、上で説明された1つのプライマリノード故障から復旧する際のステージと同じである。正常に動作しているn-|S|個のプライマリノードは、同期のために設計された同じネットワーク符号を使用して、それぞれのメモリページをBに属するバックアップノードに送信し、その後、Bに属するバックアップノードは、受信した符号化されたデータとそれ自体の符号化されたデータとの間のXORを求める。その結果、各バックアップノードBjは、以下のような部分的に復号されたデータb□jを有するようになる。0048上のものは、基本的に、ファンデルモンド行列Vの部分行列である。それは、行列GS,Bによって記述することができ、ここで、各エントリi,jは、以下のようになる。これは、一般化ファンデルモンド行列としても知られており、逆行列GS,B-1を効率的に計算することができる。0049第2のステージは、Bに属するすべてのバックアップノードが、それらの部分的に復号されたデータを交換することを必要とし、逆行列を乗算することによって、b□jを効率的に復号する。最初に、バックアップノードBj□が、その部分的に復号されたデータb□j□を分配のためにネットワークに送信し、それをを用いて正規化する。その後、という形式のすべての符号化されたデータについて、バックアップノードBj□は、別のバックアップノードBjから受信し、XOR演算を実行し、正規化されたデータを上記の符号化されたデータで置き換える。復旧は、Bj□が符号化されたデータの|B|-1個の部分を受信した後に完了する。0050ネットワークは、行列VをGS,Bに設定し、ノードがデータをそれ自体の上に同期させるように符号を構成することによって、すべてのb□jの様々な符号化されたコピーを分配することができる。したがって、ツリートポロジの場合に複数のバックアップに同期させるための以下で説明されるのと同じアルゴリズムを使用することができる。0051図14は、ネットワーク符号化を使用して、複数の異なる符号化を複数の異なるバックアップノード上に記憶する一例を示している。図14を参照すると、VM1~VM4が、X11、X21、X31、X41と呼ばれるそれぞれのデータを提供する。ネットワーク符号化の結果、データの2つの異なる符号化が生じ、2つの異なるバックアップノードに記憶される。具体的には、2つの符号化は、であり、これらの符号化は、バックアップノードである物理マシン1PM1及び物理マシン2PM2上にそれぞれ記憶される。0052VM1及びVM3が故障した場合、復旧手順は、PM1がデータX11を復旧し、そのデータにVMを介してアクセスできるようにすることを可能にし、またPM2がデータX31を復旧し、そのデータにVMを介してアクセスできるようにすることを可能にする。1つのバックアップノードに同期させるケース0053図5は、n個のプライマリノードS1...Snを、レートr1、r2、...、rnで、1つのバックアップノードBに同期させるためのアルゴリズムの一実施形態を示している。これは、レートが整数単位であることを仮定する。一実施形態では、仲介ルータでは、XOR演算のみが必要とされる。0054一実施形態では、アルゴリズムは、4つの主要ステップを含む。0055ステップ1:すべてのプライマリノードについて、プライマリノードSiからBへの最大フローmaxflowを計算し、ri個の最短経路を選択するために、エドモンズ-カープEdmonds-Karpなどの最大フローアルゴリズムを使用する。0056ステップ2:すべての選択された経路に基づいて、リンク依存グラフlinkdependencygraphを構築する図5の4行~7行。リンク依存グラフの一例が、図6のA及び図6のBに示されている。S1からBへの最大フローは、黒矢印によって示される{5,1}及び{8,6,4,2}であり、S2からBへの最大フローは、白抜き矢印によって示される{7,2}及び{9,6,3,1}である。0057ステップ3:各ソースにおいて、リンクに、符号化されていない符号語、すなわち、サイズがri×riの単位行列の行を供給し10行、リンク依存グラフをトポロジカルに辿る図5の11行~14行。リンク依存グラフ内の各ノードの出力は、その子ノードのすべての符号語の間でXORを求めた結果である。このステップは、データが符号化されずにプライマリノードから送信された場合に、バックアップノードで受信される符号語を評価する。0058ステップ4:各リンクからの符号語をプライマリノードIDによってグループ化する図5の16行これは、ノードiについて、サイズがri×riの正方行列を形成する。例えば、グループ化の後に形成されたn個の行列は、各ノードiに対してである。これらの行列は、逆行列が求められ図5の17行、その結果は、バックアップノードBにおいて正しいパリティが受信されるように、プライマリノードにおいて各リンクに対してどのページを符号化すべきであるかを与える。図6のA及び図6のBの例では、S1の逆行列は、であり、S2の逆行列は、である。0059図7は、図6の例に対して図5のアルゴリズムを適用した結果を示している。ツリートポロジの場合に複数のバックアップに同期させるためのアルゴリズム0060上で説明された符号構成アルゴリズムは、すべてのノードにおけるすべてのリンクについて、データのどの部分を符号化せずに転送すべきか、及び、データのどの部分を符号化し、既存の符号化されたストリームと組み合わせて、ツリーの残りに分配するべきか、を決定する。決定は、そのリンクを通過しているレートr1...rnと、ツリーの他方の側のバックアップノードのサイズに依存する。この決定と、したがって最小化された帯域幅とは、以下の最適化によって評価することができる。ここで、であり、ここで、Sは、ツリーの一方の側のプライマリノードの集合であり、Bは、ツリーの他方の側のバックアップノードの集合である。最適化から評価された集合Xは、プライマリノードからのどのデータをその仲介ノードにおいて符号化すべきかを示す。最適化手順の一実施形態が、図8にコード形式で示されている。0061データが符号化される場合、ファンデルモンド行列Vの適切なエントリから係数がコピーされる。仲介ノードにおける各リンクに対する符号化オペレーションは、サイズがn×kの行列Mと、1×nの2値ベクトルfによって記述することができる。ここで、Fは、符号化すべきではないが、そのリンク上で転送すべきプライマリノードからのフローを表し、fは、そのリンクについて、その仲介ノードにおいて符号化すべきプライマリノードからのフローを表し、gは、符号化オペレーションの出力であり、行列Mは、符号化手順の係数を与え、gINは、それ以前のノードからのすでに符号化されているフローを表す。g及びgINの第jのエントリは、バックアップノードjに向かう符号化されたデータを表す。0062図8は、以下の3つの主要ステップを有する主要アルゴリズムの一実施形態をコード形式で示している。0063ステップ1:ノードηにルートを有する各サブツリーについて、ネットワークの残りに寄与すべきプライマリノードデータの集合cηと、ネットワークの残りから得る必要があるプライマリノードデータの集合dηと、そのサブツリー内のバックアップノードの数βηとを計算する。図9のリストは、ツリーの底部から上方に向けての1回のスイープで、この計算アクションを実行する。0064アルゴリズムは、深さHのノードであるツリーのリーフにおいて開始し、ここで、Hは、ツリーのレベルの数であるHはリーフであり、0はツリーのルートである。このレベルにおける各ノードついて、アルゴリズムは、ノードがソースであるか、それともバックアップであるかをチェックする3行。ノードがソースである場合3行、アルゴリズムは、このノードをデータソースのリストに追加し、ノードがバックアップである場合4行、アルゴリズムは、このノードをバックアップのリストに追加し5行、このツリーの外部のノードを潜在的ソースのリストに追加する5行。0065その後、アルゴリズムは、1度に1レベルだけツリーを上昇することによって、再帰的に進行する。各レベルにおいて、アルゴリズムは、このレベルのすべてのノードを検討する8行。各ノードについて、アルゴリズムは、そのサブツリー内のすべてのソース9行と、そのサブツリー内のすべてのバックアップ10行とを調べる。サブツリー内にバックアップノードが存在する場合11行、これらのソースのインデックスを除去することによって、1組のデマンドdemandを計算する。これは、集合d\etaが、そのサブツリーの外部のソースのインデックスのみから構成されることを意味する。そのサブツリー内にソースが存在する場合、ソースのリストには、これらのソースのインデックスが投入される12行。0066したがって、このアルゴリズムの結果は、グラフ内の各ノードについての、そのサブツリーの内部のバックアップのリスト\betaと、そのサブツリーの外部のソースのリストdと、そのサブツリーの内部のソースのリストcである。0067ステップ2:アップリンクのレート及び符号化決定を、ツリーの最低ノードから開始して最高ノードまで、図8に示されたアルゴリズムを使用して評価する。0068アルゴリズムは以下のように機能し、すなわち、アルゴリズムは、ツリーの最低レベル上で説明されたようにレベルHから開始して、その後、各レベルを再帰的に検討し、最後に、ルート直下のレベルに到達する6行。各ノードについて、アルゴリズムは、図10のアルゴリズムを使用して、最小達成可能レートを計算する8行。アルゴリズムは、図10のアルゴリズムに、入力として、サブツリー内のバックアップの数とサブツリー内のソースの集合とを与え、この図10のアルゴリズムから、戻りとして、符号化されるソースの集合Xとしてのソースの集合の一区分と、符号化されないソースの集合F_\eta^Uと、最小達成可能レートを受け取る。0069その後、図8のアルゴリズムは、この最小達成可能レートをサポートするのに十分な帯域幅が存在するかどうかをチェックする10行。存在しない場合は、ソース/バックアップ同期をネットワークによってサポートすることができず、存在する場合は、アルゴリズムは、図11のアルゴリズムを使用して、レートを更新する。0070図11のアルゴリズムは、入力として、X内の符号化されるソースからのフローの集合fと、F_\eta^∪内の符号化されないソースからのフローの集合Fを取る。f内の各フローについて、アルゴリズムは、この特定のフローのため、及びサブツリーの外部の宛先の集合のため、ファンデルモンド係数を使用することによって符号を計算する4行、ここで、iは、f内のフローに対応し、jは、サブツリーの外部のバックアップインデックスに対応する。0071符号化決定が行われると、図11に示されたアルゴリズムは、アップリンクのためにそのノードに符号を植え付ける。集合Λは、すでに符号化されたフローを記録する。0072ステップ3:ツリーのルートからリーフノードに向かう各ダウンリンクのレートを評価する。符号化決定は、図8の12行~19行に示されたアルゴリズムを使用して獲得される。図12に示されるアルゴリズムは、符号化係数を適切に設定するためのアルゴリズムの一実施形態である。0073ダウンリンクを設定するため、図8のアルゴリズムは、ツリーを下降し12行、各ノードについて、アルゴリズムは、親ノードからの寄与を受ける符号化されていないフローF^D_\etaと、子ノードからの符号化されていないフローF^U_\eta’の和集合としての、符号化されていないフローのその集合をチェックする14行。各子ノードについて、ノードは、その子ノードのサブツリー内のバックアップソースの数と、この子ノードのサブツリーの内部のバックアップに寄与する、この子ノードのサブツリーの外部のソースとに基づいて、最小レートをチェックする16行。そのレートが利用可能な帯域幅よりも大きい場合18行、ソース/バックアップの組み合わせは達成可能ではない。それが達成可能な場合、符号化されたフローは、図12のアルゴリズムを使用して計算される。0074図12のアルゴリズムは、符号化されないフローFを手付かずのまま残し1行、符号化されるフローのうちのフローfについて2行、アルゴリズムは、フローiの寄与がどのバックアップノードjに行くかを考慮して3行、ファンデルモンド行列Vi,jから適切な係数を抽出する。0075ステップ2及びステップ3のいかなる時点でも、それらのリンクの残余の帯域幅が、同期レートr1...rnをサポートするのに十分でない場合、アルゴリズムは、これを検出し、エラーを返す。例示的な同期プロセス0076図13は、複数のマシンのメモリ状態を1組の1つ又は複数のバックアップノード上に同期させるためのプロセスの一実施形態を示している。プロセスは、ハードウェア回路、専用ロジックなど、汎用コンピュータシステム若しくは専用マシン上で実行されるソフトウェア、又は両方の組み合わせを含み得る、処理ロジックによって実行される。一実施形態では、このプロセスは、1組の1つ又は複数のバックアップノードに通信可能に結合された複数のマシンを有するネットワーク環境において生じる。一実施形態では、マシンは、仮想マシン又は物理マシンである。0077図13を参照すると、プロセスは、処理ロジックが、各マシンのメモリ状態に対する更新と各マシンのメモリ状態の直前のバージョンとの間でビット毎の排他的ORXOR演算を実行して、事前に符号化された変更を生成することによって開始する処理ブロック1301。一実施形態では、これは、プライマリノードによって実行される。一実施形態では、メモリ状態は、メモリページを含む。0078次に、処理ロジックは、事前に符号化された変更を1つ又は複数のバックアップノードの各々に送信する処理ブロック1302。一実施形態では、これは、プライマリノードによって実行される。0079次に、処理ロジックは、事前に符号化された変更を1つ又は複数のバックアップノードの各々において受信し、事前に符号化された変更は、複数のマシンの各1つ又は複数についてのメモリ状態に対する変更を事前に符号化することによって生成される処理ブロック1303。一実施形態では、マシンの1つ又は複数についてのメモリ状態に対する事前に符号化された変更は、各マシンのメモリ状態に対する変更と、前記各マシンのメモリ状態の直前のバージョンとに基づいて計算される。0080次に、処理ロジックは、マシンの2つ以上にわたって、事前に符号化された変更を符号化することによって、符号化されたメモリ状態を生成する処理ブロック1304。0081その後、処理ロジックは、1つ又は複数のバックアップノードの1つにおいて、マシンのうちの故障した1つについての1つ又は複数のメモリ状態を復旧する処理ブロック1305。0082一実施形態では、事前に符号化された変更を符号化することによって符号化されたメモリ状態を生成するステップは、1つ又は複数のバックアップノードの各々において行われ、符号化されたメモリ状態を生成するステップは、複数のマシンのうちの異なるマシンのメモリページの間でビット毎の排他的ORXOR演算を実行するサブステップを含む。そのようなケースでは、少なくとも1つのマシンのメモリ状態の復旧は、1つの物理ロケーションに配置されたバックアップノードの1つにおいて行われ、その後、仮想マシンが、復旧されたメモリ状態を用いて、その物理ロケーションにおいて活動化されて、故障したマシンに取って代わる。0083一実施形態では、符号化されたメモリ状態を生成するステップは、複数のマシンと1つ又は複数のバックアップノードの間に通信可能に結合された仲介ノードにおいてネットワーク符号化を実行するサブステップを含み、そのサブステップは、複数のマシンのうちの異なるマシンのメモリページの間でビット毎の排他的ORXOR演算を実行することを含む。そのようなケースでは、符号化されたメモリ状態は、1つ又は複数のバックアップノードに送信される。複数のマシンのうちの故障した1つについての1つ又は複数のメモリ状態を復旧する場合、復旧は、1つ又は複数のバックアップノードにおいて行われ、複数のマシンのうちの故障していない異なるマシンのメモリページの間でビット毎の排他的ORXOR演算を実行することによって、仲介ノードにおいてネットワーク符号化を実行して、新しい符号化されたメモリ状態を生成し、新しい符号化されたメモリ状態を1つ又は複数のバックアップノードのうちの少なくとも1つに送信し、新しい符号化されたメモリ状態と、少なくとも1つのバックアップノードに以前に記憶された符号化されたメモリ状態との間でビット毎の排他的ORXOR演算を実行することによって、故障したマシンのメモリページを生成することによって実行される。0084物理マシン、仮想マシン、プライマリノード、及びバックアップノードの各々は、情報を伝達するための通信機構又は機能、上で説明されたように情報を処理するための1つ又は複数のプロセッサ又は処理コア、並びに情報及びプロセッサ又は処理コアによって実行される命令を記憶するためのランダムアクセスメモリRAM又は他のストレージを含むことに留意されたい。0085上述の説明を読んだ後には、本発明の多くの修正形態及び変更形態が、当業者には疑いもなく明らかになるが、例として示され、説明されたどの特定の実施形態も、限定と見なされることを決して意図していないことを理解されたい。したがって、様々な実施形態の詳細についての言及は、本発明に必須と見なされる特徴のみをそれこそが列挙する特許請求の範囲を限定することを意図してしない。"