(57)【要約】  リモートバックアップのネットワークトラフィックを低減しながらノード間データレプリケーションを行うためのシステム、方法、およびコンピュータ可読ストレージ媒体。システムは、ソースネットワークノード上にある、データセットをリモートネットワークノードに複製するコマンドを受信し、ソースネットワークノード上で、データセットの以前のスナップショットのシグネチャおよびデータセットの現在のスナップショットのシグネチャにアクセスし、ソースネットワークノードにおいて、一致しない１つまたは複数のシグネチャを識別するために、以前のスナップショットと現在のスナップショットとのローカルシグネチャ比較を実行し、一致しないシグネチャをリモートネットワークノードに送信し、リモートネットワークノードにおいて、一致しないシグネチャを検索し、一致しないシグネチャが現在のリモートネットワークノードに存在しない場合、それらに関連付けられたデータを、現在のリモートスナップショットに組み入れるためにリモートネットワークノードに送信する。
2018506088.tif 000002
【特許請求の範囲】
【請求項１】
ソースネットワークノードおよびリモートネットワークノードを含むシステムであって、各ノードは、プロセッサと、前記プロセッサによって実行されるとき、前記ソースネットワークノード上にあるデータセットの前記リモートネットワークノード上のリモートバックアップコピーを生成するためのオペレーションを前記プロセッサに実行させる命令を記憶するメモリとを有し、
前記ソースネットワークノード上にある、前記データセットを前記リモートネットワークノードに複製するコマンドを受信することであって、前記データセットはツリー構造のファイルシステムのデータおよびメタデータのシグネチャを含み、前記ファイルシステムのデータおよびメタデータは、オブジェクトストアにオブジェクトとして記憶され、各オブジェクトは、グローバルに一意のコンテンツ由来のシグネチャを有する、ことと、
前記コマンドに応答して、前記ソースネットワークノード上で、前記データセットの以前記憶されたスナップショットのシグネチャおよび前記データセットの現在のスナップショットのシグネチャにアクセスすることであって、前記以前のスナップショットは、ツリー構造のファイルシステムの前記データおよびメタデータのオブジェクトの前記シグネチャのツリーを含み、前記ソースネットワークノードに記憶された前記以前のスナップショットは、前記リモートネットワークノードにおいて記憶された以前のリモートスナップショットに対応する、ことと、
前記ソースネットワークノードにおいて、前記以前のスナップショットと前記現在のスナップショットとの間で一致しない１つまたは複数のシグネチャを識別するために、前記以前のスナップショットと前記現在のスナップショットとのローカルシグネチャ比較を実行することであって、前記ローカルシグネチャ比較は、前記ツリーのルートにおいて開始する反復トップダウンの比較であり、一致しない前記シグネチャは、前記ツリー内の異なるコンテンツまたは異なる配置のうちの少なくとも１つを有する、ことと、
一致しない前記シグネチャを前記リモートネットワークノードに送信することと、
前記リモートネットワークノードにおいて、一致しない前記シグネチャの検索を実行することと、
前記リモートネットワークノードから、一致しない前記シグネチャが前記リモートネットワークノードに存在するかどうかの応答を受信することと、
一致しない前記シグネチャが前記リモートネットワークノードに存在しない場合、一致しない前記シグネチャに関連付けられたデータを、現在のリモートスナップショットに組み入れるために前記リモートネットワークノードに送信することと
を含む、システム。
【請求項２】
請求項１に記載のシステムであって、前記ソースネットワークノードおよび前記リモートネットワークノードは、ワイドエリアネットワーク（ＷＡＮ）にわたり通信する、システム。
【請求項３】
請求項２に記載のシステムであって、一致しない前記シグネチャは、前記ＷＡＮにわたり非同期的に送信される、システム。
【請求項４】
請求項２に記載のシステムであって、一致しない前記シグネチャは、前記ＷＡＮにわたり送信される前にバッチ処理される、システム。
【請求項５】
請求項４に記載のシステムであって、バッチ処理される前記シグネチャは、前記ツリーのさまざまな兄弟ノードからのシグネチャを含む、システム。
【請求項６】
前記ソースネットワークノード上にあるデータセットの前記リモートネットワークノード上のリモートバックアップコピーを生成するための方法であって、
ソースネットワークノード上にあるデータセットをリモートネットワークノードに複製するコマンドを受信するステップであって、前記データセットはツリー構造のファイルシステムのデータおよびメタデータのシグネチャを含み、前記ファイルシステムのデータおよびメタデータは、オブジェクトストアにオブジェクトとして記憶され、各オブジェクトは、グローバルに一意のコンテンツ由来のシグネチャを有する、ステップと、
前記コマンドに応答して、前記ソースネットワークノード上で、前記データセットの以前記憶されたスナップショットのシグネチャおよび前記データセットの現在のスナップショットのシグネチャにアクセスするステップであって、前記以前のスナップショットは、ツリー構造のファイルシステムの前記データおよびメタデータのオブジェクトの前記シグネチャのツリーを含み、前記ソースネットワークノードに記憶された前記以前のスナップショットは、前記リモートネットワークノードにおいて記憶された以前のリモートスナップショットに対応する、ステップと、
前記ソースネットワークノードにおいて、前記以前のスナップショットと前記現在のスナップショットとの間で一致しない１つまたは複数のシグネチャを識別するために、前記以前のスナップショットと前記現在のスナップショットとのローカルシグネチャ比較を実行するステップであって、前記ローカルシグネチャ比較は、前記ツリーのルートにおいて開始する反復トップダウンの比較であり、一致しない前記シグネチャは、前記ツリー内の異なるコンテンツまたは異なる配置のうちの少なくとも１つを有する、ステップと、
一致しない前記シグネチャを前記リモートネットワークノードに送信するステップと、
前記リモートネットワークノードにおいて、一致しない前記シグネチャの検索を実行するステップと、
前記リモートネットワークノードから、一致しない前記シグネチャが前記リモートネットワークノードに存在するかどうかの応答を受信するステップと、
一致しない前記シグネチャが前記リモートネットワークノードに存在しない場合、一致しない前記シグネチャに関連付けられたデータを、現在のリモートスナップショットに組み入れるために前記リモートネットワークノードに送信するステップと
を含む方法。
【請求項７】
請求項６に記載の方法であって、前記ソースネットワークノードおよびリ前記モートネットワークノードは、ワイドエリアネットワーク（ＷＡＮ）にわたり通信する、方法。
【請求項８】
請求項７に記載の方法であって、一致しない前記シグネチャは、前記ＷＡＮにわたり非同期的に送信される、方法。
【請求項９】
請求項７に記載の方法であって、
一致しない前記シグネチャを前記ＷＡＮにわたり送信する前にバッチ処理するステップ
をさらに含む方法。
【請求項１０】
請求項９に記載の方法であって、バッチ処理される前記シグネチャは、前記ツリーのさまざまな兄弟ノードからのシグネチャを含む、方法。
【請求項１１】
非一時的コンピュータ可読ストレージ媒体であって、プロセッサによって実行されるときに前記プロセッサにオペレーションを実行させる命令を記憶し、前記オペレーションは、
ソースネットワークノード上にあるデータセットをリモートネットワークノードに複製するコマンドを受信することであって、前記データセットはツリー構造のファイルシステムのデータおよびメタデータのシグネチャを含み、前記ファイルシステムのデータおよびメタデータは、オブジェクトストアにオブジェクトとして記憶され、各オブジェクトは、グローバルに一意のコンテンツ由来のシグネチャを有する、ことと、
前記コマンドに応答して、前記ソースネットワークノード上で、前記データセットの以前記憶されたスナップショットのシグネチャおよび前記データセットの現在のスナップショットのシグネチャにアクセスすることであって、前記以前のスナップショットは、ツリー構造のファイルシステムの前記データおよびメタデータのオブジェクトの前記シグネチャのツリーを含み、前記ソースネットワークノードに記憶された前記以前のスナップショットは、前記リモートネットワークノードにおいて記憶された以前のリモートスナップショットに対応する、ことと、
前記ソースネットワークノードにおいて、前記以前のスナップショットと前記現在のスナップショットとの間で一致しない１つまたは複数のシグネチャを識別するために、前記以前のスナップショットと前記現在のスナップショットとのローカルシグネチャ比較を実行することであって、前記ローカルシグネチャ比較は、前記ツリーのルートにおいて開始する反復トップダウンの比較であり、一致しない前記シグネチャは、前記ツリー内の異なるコンテンツまたは異なる配置のうちの少なくとも１つを有する、ことと、
一致しない前記シグネチャを前記リモートネットワークノードに送信することと、
前記リモートネットワークノードにおいて、一致しない前記シグネチャの検索を実行することと、
前記リモートネットワークノードから、一致しない前記シグネチャが前記リモートネットワークノードに存在するかどうかの応答を受信することと、
一致しない前記シグネチャが前記リモートネットワークノードに存在しない場合、一致しない前記シグネチャに関連付けられたデータを、現在のリモートスナップショットに組み入れるために前記リモートネットワークノードに送信することと
を含む、非一時的コンピュータ可読ストレージ媒体。
【請求項１２】
請求項１１に記載の非一時的コンピュータ可読ストレージ媒体であって、前記ソースネットワークノードおよび前記リモートネットワークノードは、ワイドエリアネットワーク（ＷＡＮ）にわたり通信する、非一時的コンピュータ可読ストレージ媒体。
【請求項１３】
請求項１２に記載の非一時的コンピュータ可読ストレージ媒体であって、一致しない前記シグネチャは、前記ＷＡＮにわたり非同期的に送信される、非一時的コンピュータ可読ストレージ媒体。
【請求項１４】
請求項１２に記載の非一時的コンピュータ可読ストレージ媒体であって、前記プロセッサによって実行されるときに、前記プロセッサに、
一致しない前記シグネチャを、前記ＷＡＮにわたり送信する前にバッチ処理すること
を含むオペレーションを実行させる追加の命令を記憶した非一時的コンピュータ可読ストレージ媒体。
【請求項１５】
請求項１４に記載の非一時的コンピュータ可読ストレージ媒体であって、バッチ処理される前記シグネチャは、前記ツリーのさまざまな兄弟ノードからのシグネチャを含む、非一時的コンピュータ可読ストレージ媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
優先権
[0001]本出願は、開示が参照により全体として本明細書に組み入れられる、２０１５年１月１３日に出願した米国仮出願第６２／１０２、８０８号の利益を主張するものである。
【０００２】
[0002]本発明は、データレプリケーション（複製）に関し、具体的には、データストレージバックアップまたはその他のデータコピーオペレーションのためのシグネチャ比較を実行するためのシステムおよび方法に関する。
【背景技術】
【０００３】
[0003]コンピュータサーバおよびコンピュータサーバのクラスタは、コンピューティングサービスを提供するために、ますます仮想マシンへと向かいつつある。そのような環境において、管理者は、仮想マシンのリモートバックアップタスクを構成することも多い。リモートバックアップ中、ソース仮想マシンのデータのスナップショットは、ターゲット（たとえば、リモートデータセンター）にレプリケート（複製）される。
【０００４】
[0004]現在の解決策において、シグネチャはターゲットに送信されて、ターゲットで比較が実行されるが、ターゲットは通常、ＷＡＮ接続にわたり存在する。ＷＡＮ接続は通常、遅く、コストがかかり、ＷＡＮ接続上の帯域幅を奪い合う他の多くのタスクを伴う。単一のリモートバックアップタスクが数百万のシグネチャ比較をトリガーできることにより、ますます一般的で大規模なバックアップタスクが重大な遅延を引き起こし、ＷＡＮ接続を輻輳させて、サーバリソースを占有する可能性がある。
【発明の概要】
【０００５】
[0005]ＷＡＮトラフィックおよびリモートバックアップ継続期間を短縮することができる改善されたリモートバックアップオペレーションのためのシステム、方法、およびコンピュータ可読媒体が提供される。リモートバックアップコマンドに応答して、ソースネットワークノードは、データセットの以前のスナップショットと現在のスナップショットとのローカルシグネチャ比較を実行する。このようにして、ソースネットワークノードが送信する必要があるのは、リモートネットワークノードとローカルに一致しないシグネチャのみである。次いで、リモートネットワークノードは、一致しないシグネチャを検索し、リモートネットワークノード上に存在しないシグネチャを識別する応答をソースネットワークノードに送信することができる。続いて、ソースネットワークノードは、リモートネットワークノード上に存在しないシグネチャのみに関連付けられたデータを、データセットのリモートスナップショットに組み入れるために送信する。
【０００６】
[0006]本開示により動作するシステムは、シグネチャ比較の大部分が一致という結果に至るような、頻繁なランダム書き込み使用パターンを伴い、数百ギガバイトまたはそれ以上のサイズに及ぶ特に大型の仮想ディスク（ＶＭＤＫ）のような、特定のリモートバックアップのユースケースに特に利益をもたらす。システムは、ＷＡＮにわたり送信されるリモートシグネチャ比較の大きな割合を減少させることができる。システムはまた、リモートシグネチャ比較の数が減少することにより、全般的なＷＡＮ使用を低減する。加えて、システムは、高遅延ＷＡＮ環境にわたるリモートバックアップの継続時間を短縮する。システムは、たとえ低遅延ＬＡＮ環境であっても、リモートバックアップを完了するために必要とされる時間をさらに短縮することができる。
【０００７】
[0007]一部の実施形態において、システムは、低パフォーマンスにつながる使用パターンを検出する認識アルゴリズムを含む。そのような使用パターンを認識すると、システムは、異なる特化されたバックアップルーチンを適用するか、デフォルトで標準または従来型バックアップルーチンになるかには関わりなく、異なるバックアップ手法を適用する。
【０００８】
[0008]本開示の１つの実施形態によれば、ソースネットワークノードおよびリモートネットワークノードを含むシステムであって、各ノードは、プロセッサと、プロセッサによって実行されるとき、ソースネットワークノード上にあるデータセットのリモートネットワークノード上のリモートバックアップコピーを生成するためのオペレーションをプロセッサに実行させる命令を記憶するメモリとを有し、
ソースネットワークノード上にある、データセットをリモートネットワークノードに複製するコマンドを受信するステップであって、データセットはツリー構造のファイルシステムのデータおよびメタデータのシグネチャを備え、ファイルシステムのデータおよびメタデータは、オブジェクトストアにオブジェクトとして記憶され、各オブジェクトは、グローバルに一意のコンテンツ由来のシグネチャを有するステップと、
コマンドに応答して、ソースネットワークノード上で、データセットの以前記憶されたスナップショットのシグネチャおよびデータセットの現在のスナップショットのシグネチャにアクセスするステップであって、以前のスナップショットは、ツリー構造のファイルシステムのデータおよびメタデータオブジェクトのシグネチャのツリーを備え、ソースネットワークノードに記憶された以前のスナップショットは、リモートネットワークノードにおいて記憶された以前のリモートスナップショットに対応するステップと、
ソースネットワークノードにおいて、以前のスナップショットと現在のスナップショットとの間で一致しない１つまたは複数のシグネチャを識別するために、以前のスナップショットと現在のスナップショットとのローカルシグネチャ比較を実行するステップであって、ローカルシグネチャ比較は、ツリーのルートから開始する反復トップダウンの比較であり、一致しないシグネチャは、ツリー内の異なるコンテンツまたは異なる配置のうちの少なくとも１つを有するステップと、
一致しないシグネチャをリモートネットワークノードに送信するステップと、
リモートネットワークノードにおいて、一致しないシグネチャの検索を実行するステップと、
リモートネットワークノードから、一致しないシグネチャがリモートネットワークノードに存在するかどうかの応答を受信するステップと、
一致しないシグネチャがリモートネットワークノードに存在しない場合、一致しないシグネチャに関連付けられたデータを、現在のリモートスナップショットに組み入れるためにリモートネットワークノードに送信するステップとを備えるシステムが提供される。
【０００９】
[0009]１つの実施形態において、ソースネットワークノードおよびリモートネットワークノードは、ワイドエリアネットワーク（ＷＡＮ）にわたり通信する。
[0010]１つの実施形態において、一致しないシグネチャは、ＷＡＮにわたり非同期的に送信される。
【００１０】
[0011]１つの実施形態において、一致しないシグネチャは、ＷＡＮにわたり送信される前にバッチ処理される。
[0012]１つの実施形態において、バッチ処理されたシグネチャは、ツリーのさまざまな兄弟ノードからのシグネチャを含む。
【００１１】
[0013]本開示のもう１つの実施形態によれば、ソースネットワークノード上にあるデータセットのリモートネットワークノード上のリモートバックアップコピーを生成するための方法であって、
ソースネットワークノード上にある、データセットをリモートネットワークノードに複製するコマンドを受信するステップであって、データセットはツリー構造のファイルシステムのデータおよびメタデータのシグネチャを備え、ファイルシステムのデータおよびメタデータは、オブジェクトストアにオブジェクトとして記憶され、各オブジェクトは、グローバルに一意のコンテンツ由来のシグネチャを有するステップと、
コマンドに応答して、ソースネットワークノード上で、データセットの以前記憶されたスナップショットのシグネチャおよびデータセットの現在のスナップショットのシグネチャにアクセスするステップであって、以前のスナップショットは、ツリー構造のファイルシステムのデータおよびメタデータオブジェクトのシグネチャのツリーを備え、ソースネットワークノードに記憶された以前のスナップショットは、リモートネットワークノードにおいて記憶された以前のリモートスナップショットに対応するステップと、
ソースネットワークノードにおいて、以前のスナップショットと現在のスナップショットとの間で一致しない１つまたは複数のシグネチャを識別するために、以前のスナップショットと現在のスナップショットとのローカルシグネチャ比較を実行するステップであって、ローカルシグネチャ比較は、ツリーのルートから開始する反復トップダウンの比較であり、一致しないシグネチャは、ツリー内の異なるコンテンツまたは異なる配置のうちの少なくとも１つを有するステップと、
一致しないシグネチャをリモートネットワークノードに送信するステップと、
リモートネットワークノードにおいて、一致しないシグネチャの検索を実行するステップと、
リモートネットワークノードから、一致しないシグネチャがリモートネットワークノードに存在するかどうかの応答を受信するステップと、
一致しないシグネチャがリモートネットワークノードに存在しない場合、一致しないシグネチャに関連付けられたデータを、現在のリモートスナップショットに組み入れるためにリモートネットワークノードに送信するステップとを備える方法が提供される。
【００１２】
[0014]１つの実施形態において、ソースネットワークノードおよびリモートネットワークノードは、ワイドエリアネットワーク（ＷＡＮ）にわたり通信する。
[0015]１つの実施形態において、一致しないシグネチャは、ＷＡＮにわたり非同期的に送信される。
【００１３】
[0016]１つの実施形態において、方法は、一致しないシグネチャを、ＷＡＮにわたり送信する前にバッチ処理するステップを含む。
[0017]１つの実施形態において、バッチ処理されたシグネチャは、ツリーのさまざまな兄弟ノードからのシグネチャを含む。
【００１４】
[0018]本開示のもう１つの実施形態によれば、プロセッサによって実行されるとき、プロセッサに、
ソースネットワークノード上にある、データセットをリモートネットワークノードに複製するコマンドを受信するステップであって、データセットはツリー構造のファイルシステムのデータおよびメタデータのシグネチャを備え、ファイルシステムのデータおよびメタデータは、オブジェクトストアにオブジェクトとして記憶され、各オブジェクトは、グローバルに一意のコンテンツ由来のシグネチャを有するステップと、
コマンドに応答して、ソースネットワークノード上で、データセットの以前記憶されたスナップショットのシグネチャおよびデータセットの現在のスナップショットのシグネチャにアクセスするステップであって、以前のスナップショットは、ツリー構造のファイルシステムのデータおよびメタデータオブジェクトのシグネチャのツリーを備え、ソースネットワークノードに記憶された以前のスナップショットは、リモートネットワークノードにおいて記憶された以前のリモートスナップショットに対応するステップと、
ソースネットワークノードにおいて、以前のスナップショットと現在のスナップショットとの間で一致しない１つまたは複数のシグネチャを識別するために、以前のスナップショットと現在のスナップショットとのローカルシグネチャ比較を実行するステップであって、ローカルシグネチャ比較は、ツリーのルートから開始する反復トップダウンの比較であり、一致しないシグネチャは、ツリー内の異なるコンテンツまたは異なる配置のうちの少なくとも１つを有するステップと、
一致しないシグネチャをリモートネットワークノードに送信するステップと、
リモートネットワークノードにおいて、一致しないシグネチャの検索を実行するステップと、
リモートネットワークノードから、一致しないシグネチャがリモートネットワークノードに存在するかどうかの応答を受信するステップと、
一致しないシグネチャがリモートネットワークノードに存在しない場合、一致しないシグネチャに関連付けられたデータを、現在のリモートスナップショットに組み入れるためにリモートネットワークノードに送信するステップとを備えるオペレーションを実行させる命令を記憶した、非一時的コンピュータ可読ストレージ媒体が提供される。
【００１５】
[0019]１つの実施形態において、ソースネットワークノードおよびリモートネットワークノードは、ワイドエリアネットワーク（ＷＡＮ）にわたり通信する。
[0020]１つの実施形態において、一致しないシグネチャは、ＷＡＮにわたり非同期的に送信される。
【００１６】
[0021]１つの実施形態において、非一時的コンピュータ可読ストレージ媒体は、プロセッサによって実行されるとき、プロセッサに、一致しないシグネチャを、ＷＡＮにわたり送信する前にバッチ処理するステップを含むオペレーションを実行させる追加の命令を含む。
【００１７】
[0022]１つの実施形態において、バッチ処理されたシグネチャは、ツリーのさまざまな兄弟ノードからのシグネチャを含む。
用語解説
[0023]以下に示すのは、本出願のさまざまな実施形態において使用される用語の解説である。
【００１８】
[0024]ＨＡ：高可用性。
[0025]ハイブ：データセット、すなわち、ツリー構造のファイルシステムのデータおよびメタデータ。
【００１９】
[0026]リモートバックアップジョブ（またはレプリケーションジョブ）：リモートバックアップを追跡するコントロールプレーンジョブ。
[0027]レプリケートタスク：高遅延のリンクのため、およびリモートバックアップ用にソースネットワークノードのソーススナップショットから大量のデータをリモートネットワーク（ターゲット）ノードにコピーするために最適化されたファイルシステムスレッドまたはスレッドグループ。スレッドまたはスレッドグループは、ソースノード上で稼働する。
【００２０】
[0028]ＨＡ保護されたバックアップ：ターゲットハイブＨＡペアを有するリモートバックアップ。ターゲットハイブのＨＡペアは、それぞれ受動１次および３次と称される。
[0029]本発明は、以下の図面と併せて、詳細な説明を参照することにより、より深く理解されよう。
【図面の簡単な説明】
【００２１】
【図１】[0030]本発明の１つの実施形態において使用するノードの１つの実施形態を示す概略ブロック図である。
【図２】[0031]データパスサブシステムの１つの実施形態を示す概略ブロック図である。
【図３】[0032]オペレーティングシステムのカーネルスペースを含む本発明において使用する仮想ファイルシステムの１つの実施形態を示す概略ブロック図である。
【図４】[0033]オブジェクトストアの１つの実施形態の主要コンポーネントを示す概略ブロック図である。
【図５】[0034]ファイル、ディレクトリ、およびｉノードマップのような、ファイルシステムによる必要に応じてデータ構造を伴うオブジェクトストアを利用するファイルシステムの１つの実施形態を示す概略ブロック図である。
【図６】[0035]従来技術のリモートバックアップシステムの例を示す図である。
【図７】[0036]ローカルシグネチャ比較を利用する本発明によるリモートバックアップシステムの実施形態を示す図である。
【図８Ａ】[0037]本発明の１つの実施形態によるリモートバックアップのための以前のスナップショットおよび新しいスナップショットを含むデータセットを示す概略ブロック図である。
【図８Ｂ】[0038]反復トップダウンシグネチャ比較を実行するための例示的な方法を示す図である。
【図８Ｃ】[0039]バッチ処理済みシグネチャをリモートターゲットに送信して、応答を分析するための、図８Ｂに示される方法の例示的なサブルーチンを示す図である。
【図９】[0040]例示のコンピュータシステムの実施形態を示す概略ブロック図である。
【発明を実施するための形態】
【００２２】
[0041]本開示のさまざまな実施形態は、後段において詳細に説明される。特定の実施態様について説明されるが、これは例示のために行われているに過ぎないことを理解されたい。当業者であれば、その他のコンポーネントおよび構成が、本開示の精神および範囲を逸脱することなく使用されてもよいことを理解するであろう。
【００２３】
[0042]本開示の追加の特徴および利点は、後続の説明において示され、部分的には説明から明らかとなるか、または本明細書において開示される原理の実施により理解され得るであろう。本開示の特徴および利点は、添付の特許請求の範囲において具体的に指摘される機器および組合せを用いて実現され取得されてもよい。本開示のこれらおよびその他の特徴は、後続の説明および添付の特許請求の範囲からより完全に明らかとなるか、または以下に示される原理の実施により理解され得るであろう。
【００２４】
[0043]説明を簡潔かつ明瞭にするため、適切である場合、対応するかまたは類似する要素を示すように、さまざまな図面の間で参照番号が繰り返されていることが理解されるであろう。加えて、本明細書において説明される実施形態の深い理解をもたらすために、多数の具体的な詳細が示される。しかし、本明細書において説明される実施形態は、それらの具体的な詳細を伴うことなく実施され得ることが、当業者には理解されるであろう。その他の例において、方法、手順、およびコンポーネントについては、説明される関連の該当する特徴を不明瞭にしないようにするため、詳細に説明されることはない。図面は、必ずしも一定の縮尺ではなく、詳細および特徴をよりよく説明するために、特定の部分の比率が強調されることもある。説明は、本明細書において説明される実施形態の範囲を限定するものと見なされるべきではない。
【００２５】
ノードシステム
[0044]図１は、ノード１００の１つの実施形態を示す概略ブロック図である。ノード１００は、コンピューティング、ストレージ、ネットワーキング、および仮想化のリソース、ならびにその他の技術を強固に一体化するソフトウェア中心のアーキテクチャを伴う超集中型インフラストラクチャノードであってもよい。たとえば、ノード１００は、米国マサチューセッツ州ＷｅｓｔｂｏｒｏｕｇｈのＳｉｍｐｌｉＶｉｔｙ  Ｃｏｒｐｏｒａｔｉｏｎから入手可能なＯｍｎｉＳｔａｃｋ（登録商標）ファイルシステムを組み入れたＯｍｎｉＣｕｂｅ（登録商標）のような、市販されているシステムであってもよい。ノード１００は、多数のゲスト仮想マシン（ＶＭ）１０２、１０４、および１０６をホスティングすることができ、仮想マシンのローカルおよびリモートバックアップ、ならびにスナップショットを生成するように構成されてもよい。本発明の実施において、複数のそのようなノードは、後段において説明されるようにネットワークに配列されてもよい。
【００２６】
[0045]配列を行うために、ノード１００は、ハイパーバイザー１１０の上に仮想アプライアンス１０８を含むことができる。仮想アプライアンス１０８は、制御プレーン１１４およびデータパス１１６と通信する仮想ファイルシステム１１２を含むことができる。制御プレーン１１４は、アプリケーションとノード１００内のリソースとの間のデータフローを処理することができる。データパス１１６は、仮想ファイルシステム１１２とオペレーティングシステム（ＯＳ）１１８との間の適切なＩ／Ｏインターフェイスを提供することができ、またデータ圧縮、非重複化、および最適化のような機能を使用可能にすることもできる。
【００２７】
[0046]ノード１００はまた、ハイパーバイザー１１０の下に多数のハードウェアコンポーネントを含むことができる。たとえば、ノード１００は、多数のハードディスクドライブ（ＨＤＤ）１２２および／またはソリッドステートドライブ（ＳＳＤ）１２４を有するＲＡＩＤストレージであってもよいストレージ１２０を含むことができる。ノード１００はまた、メモリ１２６（たとえば、ＲＡＭ、ＲＯＭ、フラッシュなど）および１つまたは複数のプロセッサ１２８を含むことができる。最後に、ノード１００は、その他のノードと通信できるようにする無線および／または有線ネットワークインターフェイスコンポーネント１３０を含むことができる。
【００２８】
[0047]図２を参照すると、データパス１１６は、さらに分解される。示されているように、データパス１１６は、図７を参照して詳細に説明されるように、シグネチャ比較を使用してリモートバックアップを実行するように構成されたレプリケーションマネージャ２００を含む。データパス１１６はまた、制御プレーン１１４と通信するファイルシステム２０２を含む。ファイルシステム２０２は、ファイルシステムコンポーネントをインスタンス化すること、ディレクトリおよびそれらのディレクトリ内のファイルを保持することなどによって、データパス１１６内のファイルシステムコンポーネントを管理する責任を負う。ファイルシステム２０２はまた、ノードのＩ／Ｏ処理能力を決定し、１次ノード（たとえば、ノード１００）から２次ノードへのデータ書き込みをミラーリングすることによって高可用性を実施する。
【００２９】
[0048]ファイルシステム２０２は、データパス１１６内のさまざまなコンポーネントの同期および非同期データ転送インターフェイスをさらに提供する。図３〜図４を参照して詳細に説明されるように、オブジェクトストア２０４およびストレージマネージャ２０６は、データパス１１６とＩ／Ｏサブシステム２０８との間のデータオブジェクトＩ／Ｏオペレーションに責任を負う。
【００３０】
仮想ファイルシステム
[0049]これ以降図３を参照すると、示されているのは、開示が参照により全体として本明細書に組み入れられる、Ｂｅａｖｅｒｓｏｎ他に２０１３年７月２日に許可された米国特許番号８、４７８、７９９号明細書に説明されるように、オペレーティングシステムのカーネルスペースを含む本発明において使用する仮想ファイルシステムの１つの実施形態を示す概略ブロック図である。示されるように、さまざまなストレージコンポーネントは、オペレーティングシステムカーネル３０１に含まれてもよい。Ｌｉｎｕｘ環境から描かれているが、図は、Ｗｉｎｄｏｗｓ（登録商標）、Ｓｏｌａｒｉｓ（登録商標）およびその他のＵｎｉｘクラスのオペレーティングシステムのような他のオペレーティングシステムに適用することができる。
【００３１】
[0050]ＰＯＳＩＸ（登録商標）３０４スタイルのファイルシステムの例が示され、ここでＰＯＳＩＸ（登録商標）は、汎用性を失うことなく、ＲｅｓｉｅｒＦｓ、Ｅｘｔｓ、ｂｔｆｒｓ、およびｚｆｓのような任意の数のファイルシステムのいずれか１つであってもよい。仮想ファイルシステム（ＶＦＳ）レイヤ３０３は、ファイルシステムの多くの共通機能を抽象化するために使用され、ユーザスペース３００およびその他のコンポーネントに整合性のあるインターフェイス３６０を提供する。ＶＦＳ３０３は、ＶＦＳ３０３レイヤによって認識されるために任意のファイルシステムが使用することができる明確に定義された「下縁」インターフェイス３５０ａ、３５０ｂを有することができる。実際には、通常、並行して機能する多くのファイルシステムがある。この例において、ＰＯＳＩＸ（登録商標）ファイルシステム３０４およびＯｍｎｉＳｔａｃｋ（登録商標）（ネームスペース）ファイルシステム３０７は、並行して動作することができる。
【００３２】
[0051]ファイルシステムは通常、ブロックドライバ３０５によって実施される、ブロックストレージ抽象化の上に位置する。ブロックストレージは、論理ユニット番号ＬＵＮローカルストレージデバイス３０９上にあってもよいか、またはｉＳＣＳＩプロトコルを使用するリモートＬＵＮ上にあってもよい。ブロックドライバ３０５はまた、オブジェクトストア３０８に接続するインターフェイス３５６ａ、ＤＩＣＥライブラリ３１０に接続するインターフェイス３５６ｂ、およびＰＯＳＩＸ（登録商標）３０４に接続するインターフェイス３５６ｃのような、明確に定義されたインターフェイスをオペレーティングシステムに有することもできる。
【００３３】
[0052]この実施形態において、ファイルシステムは、（たとえば、Ｂｅａｖｅｒｓｏｎ他の米国特許第８、４７８、７９９号明細書に説明されるような）オブジェクトストア３０８の上にスタックされるＯｍｎｉＳｔａｃｋ（登録商標）（ネームスペース）ファイルシステム３０７で構成される。ＯｍｎｉＳｔａｃｋ（登録商標）ファイルシステム３０７とオブジェクトストア３０８との間のインターフェイス３５２は、ＡＮＳＩ  Ｔ−１０オブジェクト標準のようなさまざまな業界標準のオブジェクトインターフェイスのいずれかであってもよいか、またはＯｍｎｉＳｔａｃｋ（登録商標）ファイルシステム３０７および／またはオブジェクトストア３０８の要件に基づく非標準のオブジェクトインターフェイスであってもよい。
【００３４】
[0053]オブジェクトストア３０８は、共通に使用される機能のライブラリ、Ｄｉｇｅｓｔ、Ｉｎｄｅｘｉｎｇ、Ｃｏｍｐｒｅｓｓｉｏｎ、Ｅｎｃｒｙｐｔｉｏｎ（ＤＩＣＥ）ライブラリ３１０が抽象化されるように、パーティション化されてもよく、インターフェイス３５３を通じてＤＩＣＥライブラリ３１０に接続されてもよい。ライブラリ３１０は、ソフトウェアにおいて完全に実現されてもよいか、またはさまざまなハードウェアアクセラレーション３１３技法を利用してもよく、その１つが示される。ハードウェアアクセラレータ３１３を使用する場合、そのアクセラレータは、計算主体のオペレーション３１１（圧縮、暗号化、フィンガープリンティング）のために１つ、およびインデックスのようなメモリ主体のオペレーション３１２のためにもう１つ、というサービスの２つの広範なクラスを有することができる。ハードウェア実施は、１つまたはもう一方、もしくは両方を有することができる。
【００３５】
[0054]オブジェクトストア３０８は、未加工ＬＵＮの上に位置し得るオブジェクトコンテナ、ディスク上のパーティション、または大容量ファイルを作成する。これはまた、ｉＳＣＳＩまたはその他のリモートアクセスブロックプロトコル（ＦＣｏＥはもう１つの例）のようなプロトコルを使用してインターフェイス３５５に沿ってネットワークスタック３０６を介してコンテナを参照することもできる。ネットワークファイルシステム（ＮＦＳ）３０２は、（インターフェイス３５４を介して）ネットワークスタック３０６の上に位置し、ＮＦＳは、ＶＦＳ３０３に接続される。ネットワークスタック３０６は、インターフェイス３６０を介してＬＵＮ３０９に接続され、インターフェイス３５９を介してクラウド３１０に接続される。
【００３６】
[0055]図４を参照すると、オブジェクトストア３０８は、さらに分解される。オブジェクトストア３０８は、バイナリの不透明なオブジェクトを含み、その例はＰ４０１、Ｑ４０２、およびＲ４０３である。オブジェクトは、さまざまなサイズであってもよいが、好ましい実施態様においては、２の累乗である。オブジェクトは、コンテナ内の一部のオブセットに属し、これはバイトオフセット、または最小オブジェクトサイズを法とするオフセット（つまり、最小オブジェクトが５１２バイトである場合、オフセットは５１２で乗算されてバイトオフセットが得られる）であってもよい。
【００３７】
[0056]各オブジェクトは、本明細書においてシグネチャまたはフィンガープリントと称される名前を有し、これはオブジェクトの全コンテンツの暗号ダイジェスト（ハッシュ）である。たとえば、図４において、オブジェクト名（シグネチャ）は、Ｈ（ｐ）、Ｈ（ｑ）、およびＨ（ｒ）によって示される。このようにして、データおよび／またはメタデータを含むことができる各オブジェクトは、そのデータのコンテンツから派生するグローバルに一意のシグネチャを有することができる。
【００３８】
[0057]インデックス構造４０４は、オブジェクト名、オブジェクト位置、およびオブジェクト参照を追跡（マップ）する。この非重複ファイルシステムおよびオブジェクトストアにおいて、各一意のデータまたはメタデータオブジェクトの単一のコピーは、記憶されて、そのシグネチャによって識別されてもよい。オブジェクトの参照は、オブジェクトが書き込まれるごとに増分される。言い換えれば、ＯｍｎｉＳｔａｃｋファイルシステム３０７が、同一オブジェクトの多数のコピーであると考えるものを生成することができる一方、オブジェクトストア３０８は１つだけを記憶するが、ネームスペースが実際に有すると考える数を追跡する。このようにすることで、非重複はシステムに固有のものである。
【００３９】
[0058]オブジェクトストア３０８は、複数のインターフェイスクラス３５２ａ〜ｄを有することができる。読み出し、書き込み、削除インターフェイス３５２ａは、規定された機能を実行する。このコンテキストにおいて、オブジェクト削除は、実際には、オブジェクトの参照カウントの減分である。オブジェクトストア内のオブジェクトのストレージは、参照カウントが０になる場合に限り解除される。インデックス付けオペレーション３５２ｂは、名前によるオブジェクトの列挙、参照カウント調整、および名前によるオブジェクトのルックアップを可能にする。オブジェクトストア３０８は、トランザクションのセマンティクス（ＡＣＩＤ特性）を有し、トランザクション境界は、トランザクションオペレーション３５２ｃを通じて管理される。これは、保留トランザクションをリスティングすることに加えて、トランザクションを開始、コミット、およびアボートすることを含む。プロビジョニングインターフェイス３５２ｄは、オブジェクトストアが、作成、削除、マージ、分割、および集約されるようにすることができる。
【００４０】
[0059]インデックス４０４は、１次キーがオブジェクト名（シグネチャ）であるマップである。システム内のあらゆるオブジェクトについてインデックスエントリがある。各エントリは、以下のものを含む。
【００４１】
ａ）オブジェクトのコンテンツのシグネチャ。シグネチャは、コンテンツの暗号ダイジェスト（ハッシュ）によって生成される。
ｂ）オブジェクトが何回参照されるかを指示する参照カウント。参照カウントは、スペースを節約するために飽和演算を使用することができる。たとえば、これは、参照を追跡するために８ビットしか使用せず、参照カウントは追加され減分されてもよいが、２５５以上になる場合、カウントは「飽和」して、それ以上の減分は許容されない。同一のオブジェクトであるという程度まで、オブジェクトが参照カウントを有するので、非重複はシステムに固有のものである。
【００４２】
ｃ）物理ロケータ。オブジェクトが物理ディスク上にある場合、これは論理ブロック番号ＬＢＮであってもよい。オブジェクトがホスティングプロバイダ（たとえば、アマゾンＳ３）によってホストされる場合、これはクラウドオブジェクトの参照であってもよい。
【００４３】
ｄ）さまざまな使用のためのフラグ。１つのフラグは、オブジェクトが記憶され圧縮されるかどうかを指示し、もう１つのフラグは、暗号化されるかどうかを指示する。その他のフラグは使用可能であるが、特定の用途に割り当てられることはない。
【００４４】
[0060]割り当てマップ４２０は、オブジェクトコンテナ４０６上の割り当てられたブロックに使用されるビットマップである。オブジェクトコンテナ４０６は、ランダムにアドレス可能な永続ストレージ抽象化である。例は、ワイドエリアネットワーク（ＷＡＮ）（つまり、９６．５６ｋｍ（６０マイル）を超える距離のような、大きい地理的距離に及ぶ通信ネットワークまたはコンピュータネットワーク）にわたる、未加工ＬＵＮ、ファイル、ディスク上のパーティション、またはｉＳＣＳＩデバイスを含む。オブジェクトコンテナ４０６は、複数のコンポーネント４０７〜４１１（一定の縮尺では示されていない）を有することができる。既知のオフセットで稼働中の、コンテナ記述子ブロック４０７を除いて、その他のコンポーネントの順序は、重要ではない。オブジェクトインデックス４０８は、Ｂツリーまたは別のツリー構造のような、コンテナ常駐部分、またはインデックス４０４の部分、または両方を有することができる。割り当てマップ４２０はまた、部分的にディスク上およびインデックス４０４内にあってもよい。２つの間の移行は、ページング技法により達成されてもよい。
【００４５】
[0061]オブジェクトストアが変更される際、トランザクションログ４１１は、永続ストレージに保持される。ログは、読み出し、書き込み、削除、参照調整などを含むすべてのオブジェクトアクティビティを追跡する。ログは、時間順に保持され、メインインデックス４０８に定期的にロールされる。オブジェクトアクティビティは、メインインデックスを検索する前に最初にログを「ヒット」する必要がある。各ログエントリは、オペレーションタイプ３５２ａ、３５２ｂ、３５２ｃ、３５２ｄ、フィンガープリント、参照カウント、トランザクションＩＤ、またはエポック番号、およびプール位置から構成される。ログエントリは、トランザクションＩＤが加わり、インデックスエントリと構造的に類似している。
【００４６】
[0062]グローバルオブジェクトネーミングは、オブジェクトストアが、オブジェクトを移動させながら、引き続き整合性のあるネーミングおよびアクセスを保持できるようにする。オブジェクトを移動させる理由は、以下の事項を含む。
【００４７】
ａ）関連するオブジェクトを、パフォーマンスの理由から、物理ディスク上で相互に近づけて移動させる。
ｂ）障害境界にわたりオブジェクトをレプリケートする。これは、２つの別個のローカルディスク、ローカルディスクおよびリモートディスク、またはその複数にわたってもよい。レプリケーションはまた、読み出しパフォーマンスの利点をもたらすことができる。レプリケーションはまた、消去コードによるような、オブジェクトを分割することを含むこともできる。
【００４８】
ｃ）圧縮、圧縮解除、暗号化、復号のような、オブジェクトへのバックグラウンドオペレーション。
ｄ）オブジェクトをその使用の頻度または予想される頻度に基づいて移動する。
【００４９】
[0063]図５は、ファイル、ディレクトリ、およびｉマップのような、ファイルシステムによる必要に応じてその他のデータ構造に特化され得る、本明細書において「ｈノード」と称される、データ構造にグループ化されるオブジェクトのセット１つの実施形態を示す概略ブロック図である。本明細書において称されるように、ｈノードは、ファイルのようなコンテンツを結び合わせるデータ構造である。場合によっては、コンテンツは非常に大きい（数ＧＢ）可能性もあり、ディスクまたは永続媒体上で隣接して適合しない。コンテンツは、分割されて、別々のユニットとして記憶される。従来のファイルシステムの場合、これはディスク上のブロックとなる。本開示において、これらはオブジェクト名（シグネチャ）である。ｈノードは、すべてのオブジェクト名のリストをマッピング構造に保持する。線形リストは、そのようなマッピング構造の１つの例であるが、さらに複雑な間接参照テーブルもまた可能である。
【００５０】
[0064]ｈノードは、オブジェクトのコンテンツを識別するオブジェクト名（シグネチャ）を備える。したがって、ｈノード自身は、明確に定義された、グローバルに一意の、名前またはシグネチャ（コンテンツのハッシュ）を有する。
【００５１】
[0065]図５に示されるように、ｈノード５００は、ファイルと類似する、ランダムにアドレス可能なコンテンツのシーケンスである。そのコンテンツがどのように解釈されるかは、コンテキストにより異なる。ｈノードは、ファイル、ディレクトリ、およびｉノードマップ（ｉマップ、後段においてさらに説明される）にさらに特化されてもよい。オブジェクト指向プログラミングの専門用語において、クラスファイル、ディレクトリ、およびｉノードマップ（ｉマップ）は、基底クラスｈノードから派生する。
【００５２】
[0066]ファイル５０４は、ｈノードが、オープン、クローズ、読み出し、書き込みなどされ得る通常のＰＯＳＩＸ（登録商標）ファイルとして表示されるようにするシンラッパーであってもよい。ディレクトリ５０５は、ｈノード５００のもう１つの解釈である。ディレクトリ５０５は、ファイルシステムｉノード番号（整数）のファイル名（ストリング）へのマッピング５０１である。マッピングは、線形リスト、Ｂツリー、ハッシュマップ、その他のツリー構造などを含む、さまざまな形態をとることができる、ただしこれらに限定されることはない。マップ５０１が完全にメモリ内にある場合、マップは、直列化および非直列化されてもよい。
【００５３】
[0067]ｉマップ（「ｉノードマップ」）５０２は、ファイルシステムｉノード番号（ディレクトリ５０５から）をオブジェクトダイジェスト（つまり、「ダイジェスト」はオブジェクトコンテンツのハッシュであり、本明細書における「シグネチャ」と同じ）に変換する。オブジェクトは、ｈノード（したがって、拡張により、ファイル、ディレクトリ、またはその他のｉマップ）、スーパーブロックのような構造、または仮想マシンに関連付けられたデータのようなその他のデータを表すことができる。ｉマップ５０２は、既知のオブジェクトに対して、インデックス０、インデックス１などのような、予約された位置を有することができる。例は、以前のｉマップ、ファイルシステムスーパーブロックなどを含む。
【００５４】
[0068]全般に、ｉマップ５０２は、ｉノード番号とオブジェクトシグネチャ（ダイジェスト）との間のマッピング（変換）である。これは、ネームスペースファイルシステムが、通常のファイルシステムのｉノード番号に対応（使用）できるようにする。この間接参照テーブルを使用することにより、ｉノード番号は、一定を維持することができるが、関連するオブジェクト名（シグネチャ）は、ｉノード番号に対応するファイルデータおよびメタデータが変化するのに応じて変化することができる。ｉマップ自身がオブジェクトであるため、その名前もまた、ファイルシステムが変更されるのに応じて変化する。この実施形態において、ファイルシステムのすべてのデータおよびメタデータはオブジェクトであり、各々がグローバルに一意のコンテンツ由来のシグネチャを有し、各ファイルシステムディレクトリは、ファイル構成体（つまり、ファイルのディレクトリ）を備えるオブジェクトのシグネチャのツリーである。
【００５５】
[0069]従来のファイルシステムと同様に、ファイルシステムツリーのルートは、ｉマップの場合、知られているｉノード番号におけるものであってもよい（ダイジェスト（ルート）に対するｉマップ５０２のインデックス２を参照）。このようにして、時間ｔにおけるｉマップのシグネチャは、基本的に、時間ｔにおけるファイルシステムの完全な「スナップショット」を表す。このシグネチャの下のあらゆる可視オブジェクトの参照カウントを増大させることは、スナップショットをロックし、その他のファイルシステムのアクティビティにはかかわりなく削除されることを防止する。
【００５６】
[0070]スナップショットシグネチャが作成されると、ファイルシステムでの作業を続行すること（書き込み可能スナップショット）、または将来の使用に備えてバックアップを作成するためにローカルに記憶することが可能である。スナップショットシグネチャはまた、リモートバックアップを作成するため、別個のオブジェクトストア上に存在する（リモートネットワークノード上の）別のシステムに送信されて記憶されてもよい。オブジェクトストアが特定のシグネチャの読み出し要求を解決することができない場合、他のオブジェクトストアを認識する程度まで、それらの他のオブジェクトストアに要求を転送することができる。したがって、スナップショットのシグネチャは、オブジェクトストアがスナップショットのデータ（オブジェクト）のすべてを完全にホスティングしないシステムに移動することができるが、先ほど説明されたメカニズムを介することは引き続き完全に整合性があり使用可能である。
【００５７】
[0071]本発明において使用され得るコンピューティングシステムおよびファイルストレージシステムのさまざまなコンポーネントを開示してきたが、これ以降、本開示はシグネチャ比較を使用するリモートバックアップを作成するステップのさらに詳細な説明を行う。
【００５８】
従来技術のリモートバックアップシステム
[0072]図６は、知られているシステム６００、およびリモートレプリケーションを実行するための方法を示す。システム６００において、制御プレーンは、レプリケーションジョブを開始することができ、これは基本的に、ソースネットワークノード６０２上のファイルシステム内のレプリケートタスクスレッドまたはスレッドグループを生成する。レプリケートタスクが開始する前に、制御プレーンは、ソースネットワークノード６０２、およびターゲットノード６０４、６０６のような、１つまたは複数のリモートターゲットネットワークノードを準備することができる。ソースノード６０２において、制御プレーンは、ハイブ（データセット）６０７を１次として開くことができる。ここから、システム６００は、休止して、データセット６０７をロールアップすることができる。次いで、制御プレーンは、データセット６０７のスナップショットを取り、１次として開かれるデータセット６９７の新しいスナップショット１次６０８を生成することができる。新しいスナップショット６０８は、ソースハイブまたはソースデータセットとして表示され、リモートバックアップのために新しいスナップショットに関連付けられたデータおよびメタデータオブジェクトのシグネチャのツリーを含む。ターゲットノード６０４において、制御プレーンは、空の受動１次ハイブ（データセット）６１０を１次として開くことができる。制御プレーンはまた、データセット６１０を、ソースデータセット６０８のリモートバックアップの受信側として追加することができる。ターゲットノード６０６において、制御プレーンは、空の３次ハイブ（データセット）６１２を２次として開くことができ、データセット６１２を、データセット６１０の２次レプリカ（複製）として追加することができる。
【００５９】
[0073]制御プレーンがノード６０２、６０４、および６０６をセットアップすると、新しいスナップショット６０８に関連付けられたシグネチャは、ＷＡＮ６１４を介してターゲットノード６０４に送信される。新しいスナップショット６０８に関連付けられたシグネチャはまた、ターゲットノード６０４からターゲットノード６０６に（たとえば、ＬＡＮ、ＷＡＮなどを介して）送信される。次いで、ターゲットノード６０４は、既存のデータ６１６を検索して、ある場合、シグネチャのいずれがターゲットノード６０４上に存在するのかを決定することができる。同様に、場合によっては、ターゲットノード６０６は、既存のデータ６１８を検索して、ある場合、シグネチャのいずれがターゲットノード６０６上に存在するのかを決定することができる。
【００６０】
[0074]検索オペレーションの完了後、ターゲットノード６０４は、ターゲットノード６０４および／またはターゲットノード６０６上に存在しないシグネチャを識別して、応答をソースノード６０２に送信することができる。次いで、ソースノード６０２は、存在しないシグネチャに関連付けられたデータを、ＷＡＮ６１４を介してターゲットノード６０４に送信する。次いで、送信されたデータは、データセット６１０、６１２に組み入れられて、新しいスナップショット６０８のリモートバックアップを作成することができる。レプリケートタスクが完了すると、制御プレーンは、データセット６０８、６１０、６１２を閉じることができる。
【００６１】
ローカルシグネチャ比較を伴うリモートバックアップシステム
[0075]図７は、本発明の１つの実施形態によるシグネチャ比較を使用してリモートバックアップを作成するためのシステム７００を示す図である。この新しいシステムおよび方法は、図６の従来技術のシステムおよび方法と比較すると、時間およびネットワークリソースの使用の観点から、実質的にさらに効率的である。
【００６２】
[0076]システム７００において、制御プレーンは、リモートバックアップを実行するよう求める要求に応答して、レプリケーションジョブを開始することができる。レプリケーションジョブを開始するステップは、基本的に、ローカルソースネットワークノード７０２上のファイルシステム内のレプリケートタスクスレッドまたはスレッドグループを生成する。レプリケートタスクが開始する前に、制御プレーンは、ソースネットワークノード７０２、およびターゲットノード７０４、７０６のような、１つまたは複数のリモートターゲットネットワークノードを準備することができる。ソースノード７０２において、制御プレーンは、ハイブ（データセット）７０７を１次として開くことができる。ここから、システム７００は、休止して、データセット７０７をロールアップすることができる。次いで、制御プレーンは、データセット７０７のスナップショットを取り、１次として開かれるデータセット７０７の新しいスナップショット１次７０８を生成することができる。新しいスナップショット７０８は、ソースハイブまたはソースデータセットとして表示され、リモートバックアップのために新しいスナップショットに関連付けられたデータおよびメタデータオブジェクトのシグネチャのツリーを含む。
【００６３】
[0077]制御プレーンはまた、以前のスナップショット１次７２０を１次として開く。開くと、システム７００は、以前のスナップショット１次７２０が、最新のリモートバックアップ（つまり、以前のスナップショット）のスナップショット、およびその関連するデータ、メタデータ、シグネチャなどを含むかどうかを決定することができる。そうではない（たとえば、以前のスナップショットが存在しない）場合、システム７００は、リモートバックアップオペレーションのための従来型レプリケーションジョブ（たとえば、図６）にフォールバックする。
【００６４】
[0078]ターゲットノード７０４において、制御プレーンは、空の受動１次ハイブ（データセット）７１０を１次として開くことができる。制御プレーンはまた、最新のバックアップ（つまり、以前のスナップショット７２０に対応するバックアップ）のルートシグネチャで、以前のスナップショット受動１次７２２と称されるハイブ（データセット）７２２を１次として開く。制御プレーンはまた、データセット７１０を、新しいスナップショット７０８のリモートバックアップの受信側として追加することができる。ターゲットノード７０６において、制御プレーンは、空の３次ハイブ（データセット）７１２を２次として開くことができる。制御プレーンはまた、最新のリモートバックアップのルートシグネチャで、以前のスナップショット３次７２４と称されるハイブ（データセット）７２４を２次として開き、データセット７１２を受動１次データセットのレプリカセットに２次として追加することができる。データセット７０７、７０８、７１０、７１２、７２０、７２２、および７２４のそれぞれは、ツリー構造化ファイルシステムのデータおよびメタデータのシグネチャを含む。ファイルシステムデータおよびメタデータは、オブジェクトストアにおいてオブジェクトとして記憶され、各オブジェクトは、以前説明されたように、グローバルに一意のコンテンツ由来のシグネチャを有する。
【００６５】
[0079]ソースおよびターゲットノードをセットアップした後、システム７００は、以前のスナップショット７２２、７２４のルートシグネチャが、以前のスナップショット７２０のルートシグネチャと一致することを確認する。最新のリモートバックアップが以前のスナップショット７２０に存在する場合、そのデータは、事前のレプリケーションオペレーションに基づいて、ターゲットノード７０４、７０６上の以前のスナップショット７２２、７２４にすでに存在するはずである。したがって、ソースノード７０２は、新しいスナップショットデータセット７０８と以前のスナップショット７２０との間で最初にローカルにシグネチャ比較を実行することができる。ローカルに一致しないシグネチャ比較のみが、ＷＡＮ７１４にわたりリモートターゲット７０４（および３次ターゲット７０６）に送信される必要がある。次いで、リモートターゲットは、シグネチャがその他のデータセットからリモートノード上にすでに存在し得る（記憶されて）ので、シグネチャをローカルに検査することができる。
【００６６】
[0080]次に、システム７００は、新しいスナップショット７０８のメタデータシグネチャを、以前のスナップショット７２０のシグネチャと最初に比較することによって、メタデータを同期させる。この比較は、ルートシグネチャから開始して、（たとえば、深さ優先技法、幅優先技法、またはその組合せを使用して）反復方式でツリー構造を下に移動する。一致しない各シグネチャについて、システム７００は、シグネチャメタデータを、ＷＡＮ７１４を介してターゲットノード７０４、７０６に送信することができる。
【００６７】
[0081]ここから、システム７００は、新しいスナップショット７０８上のハイブのサブツリー高さが、以前のバックアップ７２０のサブツリー高さと一致するかどうかを検査する。一致しない場合、システム７００は、この特定のファイルについて従来型レプリケーションジョブ（たとえば、図６）にフォールバックする。それ以外の場合、ルートシグネチャから開始して、トップダウンの反復方式で進行し、システム７００は、新しいスナップショット７０８のシグネチャを、以前のスナップショット７２０のシグネチャとローカルに比較する。そのような比較プロセスは、図８Ａ、図８Ｂ、および図８Ｃに関して後段においてさらに詳細に説明される。シグネチャがローカルに一致する場合、システムは、対応するファイルデータおよび／またはメタデータがターゲットノード７０４、７０６で一致するはずであるため、そのシグネチャをスキップする。本明細書において説明されるように、シグネチャは、データセットツリー内で同じコンテンツ（たとえば、名前）および配置をいずれも有する場合に一致するものと見なされる。シグネチャがローカルに一致しない場合（たとえば、異なるコンテンツまたは配置）、システム７００は、ターゲットノード７０４、７０６における比較のためにＷＡＮ７１４を介してシグネチャコンテンツおよび配置を送信して、データおよび／またはメタデータがその他のデータセットからリモートにすでに存在するかどうかを調べる。
【００６８】
[0082]比較のためにシグネチャをターゲットノード７０４、７０６に送信する場合、１つの方法は、同じツリーノードに属するシグネチャのみを単一のネットワークメッセージで（ソースノードからターゲットノードに）送信して、データセットツリー上のノード単位で処理することである。したがって、異なる兄弟ツリーノードに属するシグネチャは、別個のネットワークメッセージで送信されることになる。これは結果として、たとえば、ごく少数のシグネチャ（たとえば、１つ）が１つのネットワークメッセージで送信されるということになり得る。そのような手法は、比較的小さいサイズのシグネチャが送信される場合に比べて各メッセージのオーバーヘッドが大きいため、および特にＷＡＮわたり、長いラウンドトリップ時間を有するメッセージの数が多いので、あまり効率的ではなくなることもある。
【００６９】
[0083]したがって、１つの実施形態において、システム７００は、たとえシグネチャが異なる兄弟ツリーノードに属する場合であっても、多くのシグネチャを単一のメッセージでバッチ処理することができる。そうすることで、システム７００は、メッセージの送信を、データセットツリーのノード単位の処理から切り離す。送信されるべきシグネチャは、いくつのシグネチャがバッファに収まり得るかに応じて、バッファに入れられ、次いでパックされて、１つのネットワークメッセージで送信されてもよい。システム７００は、バッチ処理されたシグネチャを、比較のために、非同期的にターゲットノードに送信することができる。
【００７０】
[0084]ターゲットノード７０４においてシグネチャが受信されると、シグネチャはターゲットノード７０４から３次ターゲット７０６に（たとえば、ＬＡＮ、ＷＡＮなどを介して）送信されてもよい。このようにすることで、リモートバックアップは、高い可用性をもたらすことができるようになる。システム７００は、すでにローカルに一致しているので、（同じツリー位置における）シグネチャの一致がターゲットにおいてリモートに存在しないことをすでに決定している。したがって、ターゲットノード７０４、７０６は、既存のデータ７１６、７１８を検索して、シグネチャがリモートノードおいて存在する（記憶されている）のかどうかを決定することができる。シグネチャがターゲットノード７０４、７０６のいずれかに見出される場合、システム７００は、対応するファイルデータがターゲットノード上で使用可能であるので、そのシグネチャの処理を完了している。それ以外の場合、シグネチャはリモートに記憶されず、ターゲットノード７０４は、シグネチャがターゲットノード７０４、７０６上に存在しないことを識別して、応答をソースノード７０２に送信することができる。場合によっては、ターゲットノード７０４は、ソースノード７０２への応答をバッチ処理することができる。リモートに存在しないシグネチャがメタデータシグネチャに対応する場合、システム７００は、そのデータセットツリーの子シグネチャを引き続き比較することができる。そのシグネチャがファイルデータシグネチャに対応する場合、システム７００は、シグネチャに関連付けられたデータを、ターゲットノード７０４に送信するために、バッチ処理することができる。システム７００は、バッチ処理されたデータを非同期的にターゲットノード７０４に送信することができ、場合によっては、データをターゲットノード７０６に転送することができる。送信されたデータは、ターゲットノード７０４、７０６において、リモートバックアップ（つまり、データセット７１０、７１２）に組み入れられてもよい。
【００７１】
[0085]本発明は、（以前のスナップショットとの）大量のシグネチャ比較が一致する結果に至るようなリモートバックアップにおいて特に有益である。そのような場合、システム７００は、ＷＡＮ７１４を介するトラフィックを低減し、さらに、大容量のローカルシグネチャ一致による高遅延を回避することでバックアップ時間を短縮することもできる。余分なシグネチャ比較の正確な影響は、ソースノード７０２における、データセットメタデータ読み出し、およびその他の要因によって異なる。
【００７２】
[0086]予備テストは、ＩｏＭｅｔｅｒからのような、重いランダム書き込みを伴う仮想マシンディスク（ＶＭＤＫ）のバックアップが、好ましいユースケースと協調することを明らかにする。１つの例は、非重複化可能な圧縮可能データによりＩｏＭｅｔｅｒ  ６４Ｋランダム書き込みを使用するバックアップである。各バックアップには、２０分の書き込みが先行された。第１のバックアップは、リモートデータストア（ターゲットノード）上にデータがない場合であった。このシナリオは、リモートデータセンター上でいくつのシグネチャ比較が一致したかを示す。以下の表は、以前の手法と比較した、現在開示されるシステムの潜在的な利益を示す。
表１：非重複化可能な圧縮可能データによりＩｏＭｅｔｅｒ  ６４Ｋランダム書き込みを使用するバックアップ
【００７３】
【表１】
2018506088.tif 000003
【００７４】
[0087]非限定的な例として、以下に示すのは、現在開示されるシステムの一部を実施するための例示のインターフェイスである。
ｖｏｉｄ  ＦｉｌｅＳｙｓｔｅｍＭａｎａｇｅｒ：：ｒｅｐｌｉｃａｔｅＰｅｅｒ（ｃｏｎｓｔ  ＨｉｖｅＩｄ＆  ｈｉｖｅＩｄ，ｃｏｎｓｔ  ＮｏｄｅＩｄ＆  ｔａｒｇｅｔ，ｃｏｎｓｔ  ＲｅｂｕｉｌｄＣｏｍｐｌｅｔｅ＆  ｆｉｎｉｓｈｅｄ，ｃｏｎｓｔ  ＨｉｖｅＩｄ＆  ｐｒｅｖＢａｃｋｕｐＨｉｖｅＩｄ  ＝  ＮＵＬＬ＿ＧＵＩＤ）
[0088]ｐｒｅｖＢａｃｋｕｐＨｉｖｅＩｄがＮＵＬＬ＿ＧＵＩＤである場合、システムは、全リモートバックアップオペレーションのために従来型の方式でファイルシステムレプリケーションを実行することができる。それ以外の場合、ｐｒｅｖＢａｃｋｕｐＨｉｖｅＩｄ（スナップショット）が提供される（ローカルに記憶される）のであれば、システムは、以前のバックアップスナップショットを使用してローカルシグネチャ比較を実行しようと試みることができる。以前のバックアップスナップショットおよびデータセットは、このＡＰＩを呼び出す前にソースノード上で１次として制御プレーンによってすでに開かれている必要があり、レプリケーション中に開かれた状態でなければならない。また、ターゲットデータセット（たとえば、受動１次および３次）は、制御プレーンによって以前のバックアップスナップショットとして同じルートシグネチャにすでに設定されているべきである。それ以外の場合、ファイルシステムレプリケーションは、リモートバックアップオペレーションのために従来型レプリケーションジョブにフォールバックする。ＡＰＩは、理解されたかまたは仮定されたデフォルトの以前のバックアップデータセットまたはスナップショットが提供されないかどうかを最初にチェックするように変更されてもよい。
【００７５】
[0089]ファイルシステムは、レプリケーション中に、ソースデータセットでの仮定と同様に、以前のバックアップデータセットに並行するＩ／Ｏがないと仮定する。ファイルシステムは、制御プレーンが、同じスナップショットから複数のレプリケーションを実行できるようにすることができる。以前のバックアップスナップショットまたはデータセットへの任意の書き込みは、誤ったデータがターゲットデータセットにバックアップされる原因となり得る。
【００７６】
[0090]１つの実施形態において、システムは、最新のリモートバックアップのスナップショットをソースノード上に保持して、後続のリモートバックアップが同じターゲットノードのペアに確実に向かうようにする。ソースノードにおいて、システムは、存在する場合、多くの最新のリモートバックアップスナップショットまたはデータセットを開き、ハイブＩＤをｓｖｔｆｓ：：ＦｉｌｅＳｙｓｔｅｍＭａｎａｇｅｒ：：ｒｅｐｌｉｃａｔｅＰｅｅｒ  ＡＰＩに渡す（または指示する）必要がある。レプリケーション中に、このデータセットは開かれた状態を維持する必要があり、ファイルシステムは、並行するＩ／Ｏがないか、または少なくとも書き込みがないと仮定する。ターゲット受動１次ノードおよびターゲット３次ノードにおいて、システムは、新しい空のデータセットを開き、（ソース上でｓｖｔｆｓ：：ＦｉｌｅＳｙｓｔｅｍＭａｎａｇｅｒ：：ｒｅｐｌｉｃａｔｅＰｅｅｒ  ＡＰＩを呼び出す前に）データセットのルートシグネチャを、最新のリモートバックアップのルートシグネチャに設定する。
【００７７】
[0091]図８Ａは、最新のリモートバックアップ（つまり、以前のスナップショット）に関連付けられたデータおよびメタデータオブジェクトに対応するシグネチャのツリーを含む例示的なデータセット８００を示す。加えて、図８Ａは、リモートバックアップが意図された新しいスナップショットに関連付けられたデータおよびメタデータオブジェクトに対応するシグネチャのツリーを含むデータセット８０２を示す。示されるように、データセット８００、８０２内の各シグネチャは、それぞれのツリー内で個々のノードを形成する。たとえば、シグネチャ「１」および「１０」は、それぞれ、データセット８００、８０２の最上位レベル（レベル１（ルート）と表示される）において、ルートツリーノード８０４および８１８を形成する。ルートノード８０４、８１８から分岐するのは、データセット８００、８０２の中間レベル（レベル２と表示される）に位置する複数の子ツリーノード（つまり、ノード８０６、８０８、８２０、および８２２）である。最後に、ノード８０６、８０８、８２０、および８２２の各々から分岐するのは、データセット８００、８０２の最下位レベル（レベル３と表示される）に位置する複数の子ツリーノード（つまり、ノード８１０、８１２、８１４、８１６、８２４、８２６、８２８、および８３０）である。ノード８１０、８１２、８１４、８１６、８２４、８２６、８２８、および８３０は、さらなるメタデータの子を有していない（つまり、これらは各自のツリーの最下位を構成する）ので、これらはリーフツリーノードとして知られる。
【００７８】
[0092]新しいスナップショットと以前のスナップショットとの相違を決定するため、以前のスナップショットのシグネチャと現在のスナップショットのシグネチャとの反復トップダウンシグネチャ比較が、図８Ｂに示されるように実行されてもよい。図８Ｂにおいて説明される方法は、限定的であることを意図されておらず、代替的な実施形態は、シグネチャ比較を実行する場合に、深さ優先技法、幅優先技法、またはその組合せを使用することができる。説明を明確にするため、図８Ｂに示される方法は、方法を実施するように構成されたシステム（たとえば、システム７００）に関連して、図８Ａに示されるデータセット８００、８０２を参照して説明される。
【００７９】
[0093]方法は、新しいスナップショットのルートツリーノードシグネチャを、ステップ８５０において比較される必要のあるツリーノードシグネチャのリストに付加するステップで開始する。たとえば、データセット８０２内のルートツリーノード８１８のシグネチャ（「１０」）は、比較される必要のあるツリーノードシグネチャのリストに付加されてもよい。次に、ステップ８５２において、システム（たとえば、システム７００）は、第１の項目を、比較される必要のあるツリーノードシグネチャのリストから除去することができ、新しいスナップショットのツリーノードシグネチャと以前のスナップショットの対応する子ツリーノードシグネチャとのローカル比較を実行することができる。たとえば、データセット８０２内のルートツリーノード８１８のシグネチャ（「１０」）は、リストから除去されてもよく、データセット８００内のルートツリーノード８０４のシグネチャ（「１」）とローカルに（たとえば、システム７００のソース７０２において）比較されてもよい。
【００８０】
[0094]ローカル比較に基づいて、システム７００は、新しいスナップショット内のシグネチャのコンテンツおよび配置が、以前のスナップショット内のシグネチャのコンテンツおよび配置と一致するかどうかを決定することができる（ステップ８５４）。シグネチャが一致する場合、システム７００は、そのシグネチャ（または、ある場合、その子シグネチャ）にはさらなる比較が必要ではないと決定し、シグネチャをリモートターゲットに送信することなく、ステップ８６０に進むことができる。たとえば、データセット８０２内の子ツリーノード８２０のシグネチャ（「２」）が、ツリー内のコンテンツおよび配置のいずれにおいても、データセット８００内の子ツリーノード８０６のシグネチャ（「２」）と一致する場合、システムは、ノード８２０内のシグネチャ（「２」）、およびリーフノート８２４および８２６内のシグネチャ（「４」）および（「５」）がリモートターゲット（たとえば、ターゲットノード７０４、７０６）に送信される必要はないと決定することができる。ステップ８５４においてシグネチャが一致しない場合、システム７００は、ステップ８５６において、シグネチャを、リモートターゲット（たとえば、システム７００のターゲットノード７０４、７０６）に送信するためにバッチ処理することができる。
【００８１】
[0095]リモートターゲットに送信するためにシグネチャをバッチ処理した後、システム７００は、バッチが満杯であるかどうかを決定することができる（ステップ８５８）。バッチに少なくともあとシグネチャ１つ分の余裕がある場合、システム７００は、ステップ８６０に進むことができる。それ以外の場合、バッチが満杯であれば、システム７００は、図８Ｃに示されるサブルーチンへと移動することができ、バッチ処理されたシグネチャを（同期的または非同期的に）リモートターゲットに送信することができる（ステップ８６４）。ステップ８６６において、システム７００は、リモートターゲットにおいて送信されたシグネチャのステータス（つまり、シグネチャがリモートターゲットに存在するかどうか）を識別するリモートターゲットからの応答を受信することができる。ここから、システム７００は、評価のために応答で識別されたシグネチャを選択することができ（ステップ８６８）、応答が、選択されたシグネチャを存在するかまたは存在しないのいずれに識別するかを決定することができる（ステップ８７０）。応答が、選択されたシグネチャがリモートに存在することを指示する場合、システムは、シグネチャに関連付けられたデータをリモートターゲットに送信する必要はないことを決定し、ステップ８７８に進むことができる。それ以外の場合、選択されたシグネチャがリモートに存在しないのであれば、システム７００は、ステップ８７２において、選択されたシグネチャに関連付けられたツリーノードがリーフレベル（たとえば、図８Ａのレベル３）にあるかどうかを決定することができる。選択されたシグネチャのツリーノードがリーフレベルにある場合、システム７００は、シグネチャに関連付けられたデータを、リモートスナップショット内に組み入れるためにリモートネットワークノードに送信することができ（ステップ８７４）、引き続きステップ８７８に進むことができる。選択されたシグネチャがリーフノードに対応しない場合、システム７００は、選択されたシグネチャに関連付けられた子ツリーノードのシグネチャを、比較される必要のあるシグネチャのリストに付加することができる（ステップ８７６）。ここから、システム７００は、ステップ８７８に進むことができる。ステップ８７８において、システム７００は、ターゲットノードからの応答で識別されたすべてのシグネチャを評価したかどうかを決定することができる。すべてのシグネチャを評価してない場合、システム７００は、ステップ８６８に戻って、新しいシグネチャを選択し、上記で説明されるプロセスを繰り返すことができる。それ以外の場合、システム７００は、ステップ８６０に進むことができる。
【００８２】
[0096]図８Ｂに戻って参照すると、ステップ８６０において、システム７００は、比較される必要のあるツリーノードシグネチャのリストが空であるかどうかを決定することができる。リストが空である場合、システム７００は、比較が完了したことを指示することができる（ステップ８６２）。それ以外の場合、リストが空ではなければ、システム７００はステップ８５２に戻り、新しいスナップショットと以前のスナップショットとのシグネチャ比較が完了したかどうかをシステム７００が決定するまで、比較プロセスを繰り返すことができる。
【００８３】
コンピュータシステムアーキテクチャ
[0097]図９を参照すると、例示的なシステムおよび／またはコンピューティングデバイス９００は、処理ユニット（ＣＰＵまたはプロセッサ）９２０、および読取り専用メモリ（ＲＯＭ）９４０およびランダムアクセスメモリ（ＲＡＭ）９５０のようなシステムメモリ９３０を含むさまざまなシステムコンポーネントをプロセッサ９２０に結合するシステムバス９１０を含む。システム９００は、プロセッサ９２０と直接に、接近して、接続されるか、またはその一部として統合された高速メモリのキャッシュ９２２を含むことができる。システム９００は、プロセッサ９２０による迅速なアクセスのために、メモリ９３０および／またはストレージデバイス９６０からキャッシュ９２２にデータをコピーする。このようにして、キャッシュは、プロセッサ９２０がデータを待つ間に遅延することを回避するパフォーマンスブーストをもたらす。これらのおよびその他のモジュールは、プロセッサ９２０がさまざまなオペレーションまたはアクションを実行するように制御することができるか、または制御するように構成されてもよい。その他のシステムメモリ９３０は、同様に使用可能であってもよい。メモリ９３０は、さまざまなパフォーマンス特性を備える多数の異なるタイプのメモリを含むことができる。本開示が、複数のプロセッサ９２０を備えるコンピューティングデバイス９００上、またはより大きい処理能力をもたらすために相互にネットワークされたコンピューティングデバイスのグループまたはクラスタ上で動作できることが理解され得る。プロセッサ９２０は、任意の汎用プロセッサ、およびストレージデバイス９６０に記憶され、プロセッサ９２０を制御するように構成された、モジュール１  ９６２、モジュール２  ９６４、およびモジュール３  ９６６のようなハードウェアモジュールまたはソフトウェアモジュール、ならびにソフトウェア命令がプロセッサに組み込まれる特殊用途プロセッサを含むことができる。プロセッサ９２０は、複数のコアまたはプロセッサ、バス、メモリコントローラ、キャッシュなどを含む、内蔵型のコンピューティングシステムであってもよい。マルチコアプロセッサは、対称または非対称であってもよい。プロセッサ９２０は、異なるソケットに複数の物理的に別個のプロセッサを有するシステム、または単一の物理チップに複数のプロセッサコアを有するシステムのような、複数のプロセッサを含むことができる。同様に、プロセッサ９２０は、複数の別個のコンピューティングデバイス内に位置するが、通信ネットワークなどを介して共同する、複数の分散されたプロセッサを含むことができる。複数のプロセッサまたはプロセッサコアは、メモリ９３０またはキャッシュ９２２などのリソースを共有することができるか、または独立したリソースを使用して動作することができる。プロセッサ９２０は、１つまたは複数の状態マシン、特定用途向け集積回路（ＡＳＩＣ）、またはフィールドＰＧＡを含むプログラマブルゲートアレイ（ＰＧＡ）のうちの１つまたは複数を含むことができる。
【００８４】
[0098]システムバス９１０は、メモリーバスまたはメモリコントローラ、周辺バス、およびさまざまなバスアーキテクチャのいずれかを使用するローカルバスを含む、複数タイプのバス構造のいずれかであってもよい。ＲＯＭ９４０などに記憶された基本入出力（ＢＩＯＳ）は、起動時などにコンピューティングデバイス９００内の要素間の情報の転送を助ける基本ルーチンを提供することができる。コンピューティングデバイス９００は、ハードディスクドライブ、磁気ディスクドライブ、光ディスクドライブ、テープドライブ、ソリッドステートドライブ、ＲＡＭドライブ、取り外し可能ストレージデバイス、ＲＡＩＤ（Ｒｅｄｕｎｄａｎｔ  Ａｒｒａｙ  ｏｆ  Ｉｎｅｘｐｅｎｓｉｖｅ  Ｄｉｓｋｓ）、ハイブリッドストレージデバイスなどのような、ストレージデバイス９６０またはコンピュータ可読ストレージ媒体をさらに含む。ストレージデバイス９６０は、プロセッサ９２０を制御するためのソフトウェアモジュール９６２、９６４、９６６を含むことができる。システム９００は、その他のハードウェアまたはソフトウェアモジュールを含むことができる。ストレージデバイス９６０は、ドライブインターフェイスによってシステムバス９１０に接続される。ドライブおよび関連するコンピュータ可読ストレージデバイスは、コンピュータ可読命令、データ構造、プログラムモジュール、およびコンピューティングデバイス９００のその他のデータの不揮発性ストレージを提供する。１つの態様において、特定の機能を実行するハードウェアモジュールは、特定の機能を実施するために、プロセッサ９２０、バス９１０、ディスプレイ９７０などのような必要なハードウェアコンポーネントと接続して有形のコンピュータ可読ストレージデバイスに記憶されたソフトウェアコンポーネントを含む。もう１つの態様において、システムは、プロセッサによって実行されるとき、プロセッサに、オペレーション、方法、またはその他の特定のアクションを実行させる命令を記憶するために、プロセッサおよびコンピュータ可読ストレージデバイスを使用することができる。基本コンポーネントおよび適切な変形は、デバイス９００が小型の、ハンドヘルドコンピューティングデバイス、デスクトップコンピュータ、またはコンピュータサーバのいずれであるかのような、デバイスのタイプに応じて変更されてもよい。プロセッサ９２０が、「オペレーション」を実行するために命令を実行する場合、プロセッサ９２０は、オペレーションを直接に実行することができる、および／または別のデバイスまたはコンポーネントがオペレーションを実行できるように手助け、指示、もしくは協調することができる。
【００８５】
[0099]本明細書において説明される例示的な実施形態は、ハードディスク９６０を採用するが、磁気カセット、フラッシュメモリカード、デジタル多用途ディスク（ＤＶＤ）、カートリッジ、ランダムアクセスメモリ（ＲＡＭ）９５０、読取り専用メモリ（ＲＯＭ）９４０、ビットストリームを含むケーブルなどのような、コンピュータによってアクセス可能なデータを記憶することができるその他のタイプのコンピュータ可読ストレージデバイスもまた、例示的な動作環境において使用されてもよい。有形のコンピュータ可読ストレージ媒体、コンピュータ可読ストレージデバイス、またはコンピュータ可読メモリデバイスは、一時的な波、エネルギー、キャリア信号、電磁波、および信号自体のような媒体を明示的に除外する。
【００８６】
[0100]コンピューティングデバイス９００とのユーザインタラクションを可能にするため、入力デバイス９９０は、音声のためのマイクロフォン、ジェスチャまたはグラフィカル入力のためのタッチセンシティブスクリーン、キーボード、マウス、モーション入力、音声などのような、任意の数の入力メカニズムを表す。出力デバイス９７０はまた、当業者に知られている複数の出力メカニズムのうちの１つまたは複数であってもよい。場合によっては、マルチモーダルシステムは、ユーザが、コンピューティングデバイス９００と通信するための多様なタイプの入力を提供できるようにする。通信インターフェイス９８０は概して、ユーザ入力およびシステム出力を統率および管理する。任意の特定のハードウェア配列における動作への制約がないので、示される基本ハードウェアは、改良されたハードウェアまたはファームウェア配列が、開発されるのに応じて、容易に置換えられてもよい。
【００８７】
[0101]説明を明確にするため、例示的なシステム実施形態は、「プロセッサ」またはプロセッサ９２０とラベル表示された機能ブロックを含む個々の機能ブロックを含むものとして表される。これらのブロックが表す機能は、ソフトウェアを実行することができるハードウェア、および汎用プロセッサ上で実行するソフトウェアの等価として動作することに特化されて作られた、プロセッサ９２０のようなハードウェアを含む、共有または専用のハードウェアの使用を通じて提供されてもよいが、これらに限定されることはない。たとえば、図９に提示される１つまたは複数のプロセッサの機能は、単一の共有プロセッサまたは複数のプロセッサによって提供されてもよい。（「プロセッサ」という用語の使用は、ソフトウェアを実行することができるハードウェアを排他的に示すものと解釈されるべきではない。）例示的な実施形態は、マイクロプロセッサおよび／またはデジタル信号プロセッサ（ＤＳＰ）ハードウェア、後段において説明されるオペレーションを実行するソフトウェアを記憶するための読み出し専用メモリ（ＲＯＭ）９４０、結果を記憶するためのランダムアクセスメモリ（ＲＡＭ）９５０を含むことができる。超大規模集積回路（ＶＬＳＩ）ハードウェア実施形態、および汎用ＤＳＰ回路と組み合わせたカスタムＶＬＳＩ回路もまた、提供されてもよい。
【００８８】
[0102]さまざまな実施形態の論理的オペレーションは、（１）汎用コンピュータ内のプログラマブル回路で実行する、コンピュータ実施のステップ、オペレーション、または手順のシーケンス、（２）特殊用途のプログラマブル回路で実行する、コンピュータ実施のステップ、オペレーション、または手順のシーケンス、および／または、（３）プログラマブル回路内の相互接続されたマシンモジュールまたはプログラムエンジン、として実施される。図９に示されるシステム９００は、列挙される方法のすべてまたは一部を実施することができ、列挙されるシステムの一部であってもよく、および／または列挙される有形のコンピュータ可読ストレージデバイス内の命令に従って動作することができる。そのような論理的オペレーションは、モジュールのプログラミングに従って特定の機能を実行するためにプロセッサ９２０を制御するように構成されたモジュールとして実施されてもよい。たとえば、図９は、３つのモジュール、つまりＭｏｄ１  ９６２、Ｍｏｄ２  ９６４、およびＭｏｄ３  ９６６を示し、これらはプロセッサ９２０を制御するように構成されたモジュールである。これらのモジュールは、ストレージデバイス９６０に記憶されて、実行時にＲＡＭ９５０またはメモリ９３０にロードされるか、または他のコンピュータ可読メモリ位置に記憶されてもよい。
【００８９】
[0103]例示のコンピューティングデバイス９００の１つまたは複数の部分は、コンピューティングデバイス９００全体を含むまで、仮想化されてもよい。たとえば、仮想プロセッサは、たとえ仮想プロセッサと同じタイプの物理プロセッサが使用できない場合であっても、特定の命令セットに従って実行するソフトウェアオブジェクトであってもよい。仮想化レイヤまたは仮想「ホスト」は、仮想化オペレーションを実際のオペレーションに変換することによって、１つまたは複数の異なるコンピューティングデバイスまたはデバイスタイプの仮想化コンポーネントを使用可能にすることができる。しかし最終的に、あらゆるタイプの仮想化ハードウェアは、一部の基礎をなす物理ハードウェアによって実施されるかまたは実行される。したがって、仮想化計算レイヤは、物理計算レイヤの上で動作することができる。仮想化計算レイヤは、仮想マシン、オーバーレイネットワーク、ハイパーバイザー、仮想スイッチング、および任意の他の仮想化アプリケーションのうちの１つまたは複数を含むことができる。
【００９０】
[0104]プロセッサ９２０は、仮想プロセッサを含む、本明細書において開示されるすべてのタイプのプロセッサを含むことができる。しかし、仮想プロセッサに言及する場合、プロセッサ９２０は、仮想化レイヤにおいて仮想プロセッサを実行することに関連付けられたソフトウェアコンポーネント、および仮想化レイヤを実行するために必要な基礎をなすハードウェアを含む。システム９００は、プロセッサ９２０に特定のオペレーションを実行させる、コンピュータ可読ストレージデバイスに記憶された命令を受信する物理または仮想プロセッサ９２０を含むことができる。仮想プロセッサ９２０に言及する場合、システムはまた、仮想プロセッサ９２０を実行する基礎をなす物理ハードウェアを含む。
【００９１】
[0105]本開示の範囲内の実施形態はまた、コンピュータ実行可能命令またはデータ構造を搬送または記憶するための有形および／または非一時的コンピュータ可読ストレージデバイスを含むことができる。そのような有形のコンピュータ可読ストレージデバイスは、上記で説明されるような任意の特殊用途プロセッサの機能設計を含む、汎用または特殊用途コンピュータによってアクセスされ得る任意の使用可能なデバイスであってもよい。限定的ではなく、一例として、そのような有形のコンピュータ可読デバイスは、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、ＣＤ−ＲＯＭまたはその他の光ディスクストレージ、磁気ディスクストレージまたはその他の磁気ストレージデバイス、もしくは望ましいプログラムコードをコンピュータ実行可能命令、データ構造、またはプロセッサチップ設計の形態で搬送または記憶するために使用され得る任意の他のデバイスを含むことができる。情報または命令がネットワークまたは別の通信接続（配線、無線、またはその組合せのいずれか）を介してコンピュータに提供される場合、コンピュータは、適正に、接続をコンピュータ可読媒体とみなす。したがって、任意のそのような接続が、適切に、コンピュータ可読媒体と称される。上記の組合せも、コンピュータ可読ストレージデバイスの範囲に含まれるものとする。
【００９２】
[0106]コンピュータ実行可能命令は、たとえば、汎用コンピュータ、特殊用途コンピュータ、または特殊用途処理デバイスに、特定の機能または機能のグループを実行させる命令およびデータを含む。コンピュータ実行可能命令はまた、スタンドアロンまたはネットワークの環境においてコンピュータによって実行されるプログラムモジュールを含む。一般に、プログラムモジュールは、特定のタスクを実行するかまたは特定の抽象データタイプを実施する、特殊用途プロセッサなどの設計に固有のルーチン、プログラム、コンポーネント、データ構造、オブジェクト、および機能を含む。コンピュータ実行可能命令、関連するデータ構造、およびプログラムモジュールは、本明細書において開示される方法のステップを実行するためのプログラムコード手段の例を表す。そのような実行可能命令または関連するデータ構造の特定のシーケンスは、そのようなステップで説明される機能を実施するための対応する動作の例を表す。
【００９３】
[0107]本開示のその他の実施形態は、パーソナルコンピュータ、ハンドヘルドデバイス、マルチプロセッサシステム、マイクロプロセッサベースまたはプログラマブル家庭用電化製品、ネットワークＰＣ、ミニコンピュータ、メインフレームコンピュータなどを含む、多くのタイプのコンピュータシステム構成を備えるネットワークコンピューティング環境において実施され得る。実施形態はまた、タスクが通信ネットワークを通じて（配線リンク、無線リンク、またはその組合せのいずれかにより）リンクされるローカルおよびリモート処理デバイスによって実行される分散コンピューティング環境において実施されてもよい。分散コンピューティング環境において、プログラムモジュールは、ローカルおよびリモートのメモリストレージデバイスに配置されてもよい。
【００９４】
[0108]上記で説明されるさまざまな実施形態は、ほんの一例として提供されているに過ぎず、本開示の範囲を限定するものとして解釈されるべきではない。たとえば、本明細書における原理は、概して、音声対話システムに適用し、その任意のアプリケーションに使用されてもよい。本明細書において示され説明される例示の実施形態およびアプリケーションに従うことなく、本開示の精神および範囲を逸脱することなく、本明細書において説明される原理にさまざまな修正および変更が行われてもよい。セットの「少なくとも１つ」を述べる請求項の用語は、セットの１つの構成要素またはセットの複数の構成要素が請求項を満足することを示す。
【図１】
2018506088.tif 000004
【図２】
2018506088.tif 000005
【図３】
2018506088.tif 000006
【図４】
2018506088.tif 000007
【図５】
2018506088.tif 000008
【図６】
2018506088.tif 000009
【図７】
2018506088.tif 000010
【図８Ａ】
2018506088.tif 000011
【図８Ｂ】
2018506088.tif 000012
【図８Ｃ】
2018506088.tif 000013
【図９】
2018506088.tif 000014
【国際調査報告】
2018506088.tif 000015
2018506088.tif 000016
2018506088.tif 000017