(57)【特許請求の範囲】
【請求項１】
クラスタシステムにおけるデータ処理方法であって、
現在の物理ノードが、受信されたデータストリームをｍ個のデータブロックに分割し、各データブロックのフィンガープリントを取得し、第１アルゴリズムに従って前記データストリームを表すｎ個の第１スケッチ値を取得するステップであって、ｍは１以上の整数であり、ｎは１以上であって、ｍ以下の整数である、取得するステップと、
第２アルゴリズムに従って前記ｎ個の第１スケッチ値の各第１スケッチ値に対応し、前記クラスタシステム内にある第１物理ノードを特定し、各第１スケッチ値をクエリのため前記対応する第１物理ノードに送信するステップと、
前記ｎ個の第１スケッチ値に対応する第１物理ノードから少なくとも１つのレスポンスメッセージを受信し、前記レスポンスメッセージから第１ストレージアドレスを取得するステップと、
前記第１ストレージアドレスにより指示されるストレージ領域に格納されるデータブロックのフィンガープリントと、前記データストリームの分割を介し取得された各データブロックのフィンガープリントとを比較し、重複データブロックをクエリするステップであって、取得された非重複データブロックが新たなデータブロックとして利用される、クエリするステップと、
前記新たなデータブロックを表す少なくとも１つの第２スケッチ値を取得し、前記第２アルゴリズムに従って各第２スケッチ値に対応する第２物理ノードを前記第２スケッチ値により特定し、各第２スケッチ値と各第２スケッチ値により表されるデータブロックのストレージアドレスとの間の対応関係を前記対応する第２物理ノードに格納するステップと、
を有する方法。
【請求項２】
少なくとも１つのバーチャルノードが、前記クラスタシステムの各物理ノードの分割を介し論理的に取得され、前記クラスタシステムにおけるバーチャルノードと物理ノードとの間の対応関係が、各物理ノードに含まれ、
前記第２アルゴリズムに従って前記ｎ個の第１スケッチ値の各第１スケッチ値に対応し、前記クラスタシステム内にある第１物理ノードを特定するステップは、
前記第２アルゴリズムに従って前記ｎ個の第１スケッチ値の各第１スケッチ値に対応し、前記クラスタシステム内にある第１バーチャルノードを特定し、バーチャルノードと物理ノードとの間の対応関係をクエリにすることによって、前記第１バーチャルノードに対応する第１物理ノードを取得するステップを有し、
前記第２アルゴリズムに従って各第２スケッチ値に対応する第２物理ノードを前記第２スケッチ値により特定し、各第２スケッチ値と各第２スケッチ値により表されるデータブロックのストレージアドレスとの間の対応関係を前記対応する第２物理ノードに格納するステップは、
前記第２アルゴリズムに従って各第２スケッチ値に対応する第２バーチャルノードを前記第２スケッチ値により特定し、バーチャルノードと物理ノードとの間の対応関係に従って前記第２バーチャルノードが配置される第２物理ノードを特定し、各第２スケッチ値と各第２スケッチ値により表されるデータブロックのストレージアドレスとの間の対応関係を前記対応する第２物理ノードの第２バーチャルノードに格納するステップを有する、請求項１記載の方法。
【請求項３】
前記第２アルゴリズムに従って前記ｎ個の第１スケッチ値の各第１スケッチ値に対応し、前記クラスタシステム内にある第１物理ノードを特定するステップは、
各第１スケッチ値に対応し、前記クラスタシステム内にある前記第１バーチャルノードを取得するため、前記クラスタシステムの全てのバーチャルノードの個数に対して各第１スケッチ値によるモジュロ演算を実行するステップを有する、請求項２記載の方法。
【請求項４】
データ移行状態を充足すると、移行が必要なデータを有する物理ノードの少なくとも１つのバーチャルノードをターゲット物理ノードに一体的に移行するステップと、
前記現在の物理ノードの移行されるバーチャルノードと物理ノードとの間の対応関係を更新し、前記クラスタシステムの他の物理ノードに前記移行されるノードと物理ノードとの間の対応関係を更新したことを通知するステップと、
を更に有する、請求項２又は３記載の方法。
【請求項５】
前記第２アルゴリズムに従って前記ｎ個の第１スケッチ値の各第１スケッチ値に対応し、前記クラスタシステム内にある第１物理ノードを特定するステップは、
各第１スケッチ値に対応し、前記クラスタシステム内にある前記第１物理ノードを取得するため、前記クラスタシステムの全ての物理ノードの個数に対して各第１スケッチ値によるモジュロ演算を実行するステップを有する、請求項１記載の方法。
【請求項６】
前記新たなデータブロックを表す少なくとも１つの第２スケッチ値を取得するステップは、前記第１アルゴリズムに従って前記新たなデータブロックを表す少なくとも１つの第２スケッチ値を取得するステップを有する、請求項１乃至５何れか一項記載の方法。
【請求項７】
前記第１アルゴリズムに従って前記データストリームを表すｎ個の第１スケッチ値を取得するステップは、
前記データブロックのｍ個のデータブロックのフィンガープリントをｎ個の第１フィンガープリントグループにグループ化するステップであって、各第１フィンガープリントグループは、少なくとも２つのデータブロックのフィンガープリントを有する、グループ化するステップと、
前記ｎ個の第１スケッチ値を取得するため、各フィンガープリントグループを表す第１スケッチ値を取得するステップと、
を有する、請求項１乃至６何れか一項記載の方法。
【請求項８】
前記レスポンスメッセージから第１ストレージアドレスを取得するステップは、
前記レスポンスメッセージから前記第１スケッチ値に対応するストレージアドレスを取得し、前記レスポンスメッセージに搬送される各ストレージアドレスのヒット数に関する統計量を収集し、前記第１ストレージアドレスとして最大ヒット数を有するｓ個のストレージアドレスを選択するステップを有し、ｓは１以上である、請求項１乃至５何れか一項記載の方法。
【請求項９】
所定のストレージ条件が充足すると、所定のストレージポリシーに従って前記新たなデータブロックと前記新たなデータブロックのフィンガープリントとが書き込まれるストレージアドレスを選択し、前記新たなデータブロックと前記新たなデータブロックのフィンガープリントとを前記選択されたストレージアドレスにより指示されるストレージ領域に書き込むステップを更に有する、請求項１乃至５何れか一項記載の方法。
【請求項１０】
前記所定のストレージポリシーに従って前記新たなデータブロックと前記新たなデータブロックのフィンガープリントとが書き込まれるストレージアドレスを選択するステップは、
前記クラスタシステムの物理ノードのロード情報を取得し、前記ロード情報に従ってデータが移行される物理ノードを選択し、前記データが移行される物理ノードから、前記新たなデータブロックと前記新たなデータブロックのフィンガープリントとが書き込まれるストレージアドレスを取得するステップを有する、請求項９記載の方法。
【請求項１１】
前記クラスタシステムの物理ノードのロード情報を取得し、前記ロード情報に従ってデータが移行される物理ノードを選択し、前記データが移行される物理ノードから、前記新たなデータブロックと前記新たなデータブロックのフィンガープリントとが書き込まれるストレージアドレスを取得するステップは、
前記クラスタシステムの物理ノードのロード情報を取得し、前記クラスタシステムの全ての物理ノードの平均ロード値が第１所定閾値を超過すると、前記平均ロード値より小さなロード値を有する物理ノードから、データが移行されるノードを選択し、前記データが移行されるノードから、前記新たなデータブロックと前記新たなデータブロックのフィンガープリントとが書き込まれるストレージアドレスを取得するステップと、
前記クラスタシステムの全ての物理ノードの平均ロード値が前記第１所定閾値以下であるとき、前記現在の物理ノードから、前記新たなデータブロックと前記新たなデータブロックとのフィンガープリントとが書き込まれるストレージアドレスとを取得するステップと、
を有する、請求項１０記載の方法。
【請求項１２】
前記所定のストレージポリシーに従って前記新たなデータブロックと前記新たなデータブロックのフィンガープリントとが書き込まれるストレージアドレスを選択するステップは、
前記現在の物理ノードから、前記新たなデータブロックと前記新たなデータブロックのフィンガープリントとが書き込まれるストレージアドレスを取得するステップを有する、請求項９記載の方法。
【請求項１３】
前記所定のストレージ条件が充足することは、前記新たなデータブロックが前記現在の物理ノードのキャッシュに格納されることを含み、
前記現在の物理ノードのキャッシュのデータが第２所定閾値に達すると、前記所定のストレージ条件が充足される、請求項９記載の方法。
【請求項１４】
前記各フィンガープリントグループを表す第１スケッチ値を取得するステップは、各フィンガープリントグループから最小のフィンガープリントを、前記最小のフィンガープリントが属するフィンガープリントグループを表す第１スケッチ値として選択するステップを有する、請求項７記載の方法。
【請求項１５】
前記第１ストレージアドレスにより指示されるストレージ領域に格納されるデータブロックのフィンガープリントと、前記データストリームの分割を介し取得された各データブロックのフィンガープリントとを比較し、重複データブロックをクエリするステップは、
前記第１ストレージアドレスにより指示されるストレージ領域のデータブロックのフィンガープリントを前記現在の物理ノードにロードし、前記データストリームの分割を介し取得されたｍ個のデータブロックのフィンガープリントとの比較を実行し、前記重複データブロックをクエリするステップを有する、請求項１乃至１４何れか一項記載の方法。
【請求項１６】
前記第１ストレージアドレスにより指示されるストレージ領域に格納されるデータブロックのフィンガープリントと、前記データストリームの分割を介し取得された各データブロックのフィンガープリントとを比較し、重複データブロックをクエリするステップは、
前記第１ストレージアドレスにより指示される物理ノードにクエリ指示を送信し、前記第１ストレージアドレスにより指示される前記物理ノードにより返されたクエリ結果を受信するステップを有し、
前記データストリームの分割を介し取得されるｍ個のデータブロックのフィンガープリントは、前記クエリ指示により搬送される、請求項１乃至１４何れか一項記載の方法。
【請求項１７】
各第１スケッチ値をクエリのため前記対応する第１物理ノードに送信した後、当該方法は更に、前記ｎ個の第１スケッチ値に対応する前記第１物理ノードにより返されるストレージアドレスが受信されない場合、前記データストリームの分割を介し取得されるデータブロックを非重複データブロックとして利用するステップを有する、請求項１乃至１４何れか一項記載の方法。
【請求項１８】
クラスタシステムにおけるデータ処理装置であって、
現在の物理ノードにより受信されたデータストリームをｍ個のデータブロックに分割し、各データブロックのフィンガープリントを取得する分割部であって、ｍは１以上の整数である、分割部と、
第１アルゴリズムに従って前記データストリームを表すｎ個の第１スケッチ値を取得するスケッチ値取得部であって、ｎは１以上であって、ｍ以下の整数である、スケッチ値取得部と、
第２アルゴリズムに従って前記ｎ個の第１スケッチ値の各第１スケッチ値に対応し、前記クラスタシステム内にある第１物理ノードを特定する特定部と、
各第１スケッチ値をクエリのため前記対応する第１物理ノードに送信する送信部と、
前記ｎ個の第１スケッチ値に対応する第１物理ノードから少なくとも１つのレスポンスメッセージを受信し、前記レスポンスメッセージから第１ストレージアドレスを取得する受信部と、
前記第１ストレージアドレスにより指示されるストレージ領域に格納されるデータブロックのフィンガープリントと、前記データストリームの分割を介し取得された各データブロックのフィンガープリントとを比較し、重複データブロックをクエリするクエリ部であって、前記クエリ部により取得された非重複データブロックが新たなデータブロックとして利用される、クエリ部と、
前記新たなデータブロックを表す少なくとも１つの第２スケッチ値を取得し、前記第２アルゴリズムに従って各第２スケッチ値に対応する第２物理ノードを前記第２スケッチ値により特定し、各第２スケッチ値と各第２スケッチ値により表されるデータブロックのストレージアドレスとの間の対応関係を前記対応する第２物理ノードに格納する更新部と、
を有する装置。
【請求項１９】
所定のストレージポリシーに従って、前記新たなデータブロックと前記新たなデータブロックのフィンガープリントとが書き込まれるストレージアドレスを選択するよう構成されるライトアドレス取得部と、
所定のストレージ条件が充足すると、前記新たなデータブロックと前記新たなデータブロックのフィンガープリントとを、前記選択されたストレージアドレスに対応するストレージ領域に書き込むよう構成される書き込み部と、
を更に有する、請求項１８記載の装置。
【請求項２０】
少なくとも１つのバーチャルノードが、前記クラスタシステムの各物理ノードの分割を介し論理的に取得され、前記クラスタシステムにおけるバーチャルノードと物理ノードとの間の対応関係が、各物理ノードに含まれ、
前記特定部は、前記第２アルゴリズムに従って前記ｎ個の第１スケッチ値の各第１スケッチ値に対応し、前記クラスタシステム内にある第１バーチャルノードを特定し、バーチャルノードと物理ノードとの間の対応関係をクエリにすることによって、前記第１バーチャルノードに対応する第１物理ノードを取得するよう構成され、
前記クエリ部により取得される非重複データブロックは、前記新たなデータブロックとして利用され、
前記更新部は、前記新たなデータブロックを表す少なくとも１つの第２スケッチ値を取得し、前記第２アルゴリズムに従って各第２スケッチ値に対応する第２バーチャルノードを前記第２スケッチ値により特定し、バーチャルノードと物理ノードとの間の対応関係に従って前記第２バーチャルノードが配置される第２物理ノードを特定し、各第２スケッチ値と各第２スケッチ値により表されるデータブロックのストレージアドレスとの間の対応関係を前記対応する第２物理ノードの第２バーチャルノードに格納するよう構成される、請求項１９記載の装置。
【請求項２１】
前記書き込む部は更に、データ移行状態を充足すると、移行が必要なデータを有する物理ノードの少なくとも１つのバーチャルノードをターゲット物理ノードに一体的に移行するよう構成され、
前記更新部は更に、前記現在の物理ノードの移行されるバーチャルノードと物理ノードとの間の対応関係を更新し、前記クラスタシステムの他の物理ノードに前記移行されるノードと物理ノードとの間の対応関係を更新したことを通知するよう構成される、請求項２０記載の装置。
【請求項２２】
前記特定部は、各第１スケッチ値に対応し、前記クラスタシステム内にある前記第１物理ノードを取得するため、前記クラスタシステムの全ての物理ノードの個数に対して各第１スケッチ値によるモジュロ演算を実行するよう構成される、請求項１８記載の装置。
【請求項２３】
前記スケッチ値取得部は、
前記データストリームのｍ個のデータブロックのフィンガープリントをｎ個の第１フィンガープリントグループにグループ化するよう構成されるフィンガープリントグループ化サブ部であって、各第１フィンガープリントグループは、少なくとも２つのデータブロックのフィンガープリントを有する、フィンガープリントグループ化サブ部と、
前記ｎ個の第１スケッチ値を取得するため、各フィンガープリントグループを表す第１スケッチ値を取得するよう構成される取得サブ部と、
を有する、請求項１８乃至２１何れか一項記載の装置。
【請求項２４】
前記受信部は、
前記レスポンスメッセージから前記第１スケッチ値に対応するストレージアドレスを取得し、前記レスポンスメッセージに搬送される各ストレージアドレスのヒット数に関する統計量を収集するよう構成される統計量収集サブ部と、
前記統計量収集サブ部の統計結果に従って、前記第１ストレージアドレスとして最大ヒット数を有するｓ個のストレージアドレスを選択するよう構成されるアドレス取得サブ部であって、ｓは１以上である、アドレス取得サブ部と、
を有する、請求項１８乃至２１何れか一項記載の装置。
【請求項２５】
前記ライトアドレス取得部は、
前記クラスタシステムの物理ノードのロード情報を取得するよう構成されるロード情報取得サブ部と、
前記ロード情報取得サブ部により取得されたロード情報に従って、データが移行される物理ノードを選択し、前記データが移行される物理ノードから、前記新たなデータブロックと前記新たなデータブロックのフィンガープリントとが書き込まれるストレージアドレスを取得するよう構成されるアドレス選択サブ部と、
を有する、請求項１９乃至２１何れか一項記載の装置。
【請求項２６】
前記ライトアドレス取得部は、前記現在の物理ノードから、前記新たなデータブロックと前記新たなデータブロックのフィンガープリントとが書き込まれるストレージアドレスを取得するよう構成される、請求項１９乃至２１何れか一項記載の装置。
【請求項２７】
前記書き込む部は、前記新たなデータブロックを前記現在の物理ノードのキャッシュに格納するよう構成され、前記現在の物理ノードのキャッシュのデータが第２所定閾値に達し、前記所定のストレージ条件が充足されると、前記新たなデータブロックと前記新たなデータブロックのフィンガープリントとを前記選択されたストレージアドレスに対応するストレージ領域に書き込むよう構成される、請求項２５記載の装置。
【請求項２８】
前記受信部は更に、各第１スケッチ値をクエリのため前記対応する第１物理ノードに送信した後、前記ｎ個の第１スケッチ値に対応する前記第１物理ノードにより返されるストレージアドレスが受信されない場合、前記データストリームの分割を介し取得されるデータブロックを非重複データブロックとして利用するよう構成される、請求項１８乃至２７何れか一項記載の装置。
【請求項２９】
クラスタシステムにおけるデータ処理装置であって、
プロセッサと、
メモリと、
バスと、
を有し、
前記プロセッサと前記メモリとは、前記バスを介し互いに通信し、
前記メモリは、プログラムを格納するよう構成され、
前記プロセッサは、前記メモリのプログラムを実行し、請求項１乃至１７何れか一項記載の方法を実行するよう構成される装置。
【請求項３０】
請求項１乃至１７何れか一項記載の方法をコンピュータに実行させるためのコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施例は、ストレージ技術に関し、特にクラスタシステムにおけるデータ処理方法及び装置に関する。
【背景技術】
【０００２】
データ重複排除（略して重複排除）はまた、インテリジェント圧縮又はシングルインスタンスストレージと呼ばれ、冗長データを排除し、ストレージ容量を低減するための要求を充たすため、重複データを自動的にサーチし、同一のデータについて一意的な複製のみを確保し、単一の複製を指示するポインタを用いて他の重複した複製を置換することが可能なストレージ技術である。
【０００３】
クラスタデータ重複排除（略してクラスタ重複排除）は、重複排除パフォーマンス及びキャパシティを向上するため、複数の重複排除物理ノードを整理する技術を表す。従来技術によるクラスタ重複排除技術では、一般に、データストリームを受信する物理ノードは、データストリームを複数のデータブロックに分割し、取得したデータブロックをグループ化し、各グループについて、当該グループのデータブロックのメタデータ情報からメタデータ情報の一部をサンプリングし、クエリのためクラスタシステムの全ての物理ノードにメタデータ情報の一部を送信する。クラスタシステムの各物理ノードは、既知のデータブロックと対応するメタデータ情報とを格納し、サンプリングされたメタデータ情報と各物理ノードに格納されているメタデータ情報とを比較し、クリエ結果から最も多くの重複データブロックを有するターゲット物理ノードを取得し、重複データクエリのためサンプリングされたメタデータ情報に対応するデータグループの全てのデータブロック情報をターゲット物理ノードに送信する。
【０００４】
研究を通じて、発明者は、従来技術のクラスタ重複排除技術では、サンプリングされたメタデータ情報は、クエリのため全ての物理ノードに送信される必要があり、これは、重複排除プロセスにおける物理ノード間の多数のインタラクション回数を導き、クラスタシステムに多数の物理ノードが存在する場合、各物理ノードが重複排除を実行すると、クラスタシステムの物理ノードの個数の増加に従って計算量が増大し、システムの重複排除パフォーマンスの低下を導く。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明の実施例は、クラスタシステムの重複排除パフォーマンスを効果的に改善するため、クラスタシステムにおけるデータ処理方法及び装置を提供する。
【課題を解決するための手段】
【０００６】
本発明の課題を解決するため、本発明の第１の態様は、クラスタシステムにおけるデータ処理方法であって、
現在の物理ノードにより受信されたデータストリームをｍ個のデータブロックに分割し、各データブロックのフィンガープリントを取得し、第１アルゴリズムに従って前記データストリームを表すｎ個の第１スケッチ値を取得するステップであって、ｍは１以上の整数であり、ｎは１以上であって、ｍ以下の整数である、取得するステップと、
第２アルゴリズムに従って前記ｎ個の第１スケッチ値の各第１スケッチ値に対応し、前記クラスタシステム内にある第１物理ノードを特定し、各第１スケッチ値をクエリのため前記対応する第１物理ノードに送信するステップと、
前記ｎ個の第１スケッチ値に対応する第１物理ノードから少なくとも１つのレスポンスメッセージを受信し、前記レスポンスメッセージから第１ストレージアドレスを取得するステップと、
受信した全てのストレージアドレスから第１ストレージアドレスを取得し、前記第１ストレージアドレスにより指示されるストレージ領域に格納されるデータブロックのフィンガープリントと、前記データストリームの分割を介し取得された各データブロックのフィンガープリントとを比較し、重複データブロックをクエリするステップとであって、取得された非重複データブロックが新たなデータブロックとして利用される、クエリするステップと、
前記新たなデータブロックを表す少なくとも１つの第２スケッチ値を取得し、前記第２アルゴリズムに従って各第２スケッチ値に対応する第２物理ノードを前記第２スケッチ値により特定し、各第２スケッチ値と各第２スケッチ値により表されるデータブロックのストレージアドレスとの間の対応関係を前記対応する第２物理ノードに格納するステップと、
を有する方法を提供する。
【０００７】
第１の態様に関連して、第１の態様の第１の可能な方法では、全ての受信したストレージアドレスから第１ストレージアドレスを取得するステップは、レスポンスメッセージから第１スケッチ値に対応するストレージアドレスを取得し、レスポンスメッセージに搬送される各ストレージアドレスのヒット数に関する統計量を収集し、第１ストレージアドレスとして最大ヒット数を有するｓ個のストレージアドレスを選択するステップを有し、ｓは１以上である。
【０００８】
第１の態様の第１の可能な方法に関連して、第２の可能な方法では、本方法は更に、所定のストレージ条件が充足すると、所定のストレージポリシーに従って前記新たなデータブロックと前記新たなデータブロックのフィンガープリントとが書き込まれるストレージアドレスを選択し、前記新たなデータブロックと前記新たなデータブロックのフィンガープリントとを前記選択されたストレージアドレスにより指示されるストレージ領域に書き込むステップを更に有する。
【０００９】
第１の態様の第２の可能な方法に関連して、第３の可能な方法では、所定のストレージ条件が充足することは、前記新たなデータブロックが前記現在の物理ノードのキャッシュに格納されることを含み、前記現在の物理ノードのキャッシュのデータが第２所定閾値に達すると、前記所定のストレージ条件が充足される。
【００１０】
本発明の実施例の第２の態様は、クラスタシステムにおけるデータ処理装置であって、
現在の物理ノードにより受信されたデータストリームをｍ個のデータブロックに分割し、各データブロックのフィンガープリントを取得する分割部であって、ｍは１以上の整数である、分割部と、
第１アルゴリズムに従って前記データストリームを表すｎ個の第１スケッチ値を取得するスケッチ値取得部であって、ｎは１以上であって、ｍ以下の整数である、スケッチ値取得部と、
第２アルゴリズムに従って前記ｎ個の第１スケッチ値の各第１スケッチ値に対応し、前記クラスタシステム内にある第１物理ノードを特定する特定部と、
各第１スケッチ値をクエリのため前記対応する第１物理ノードに送信する送信部と、
前記ｎ個の第１スケッチ値に対応する第１物理ノードから少なくとも１つのレスポンスメッセージを受信し、前記レスポンスメッセージから第１ストレージアドレスを取得する受信部と、
前記第１ストレージアドレスにより指示されるストレージ領域に格納されるデータブロックのフィンガープリントと、前記データストリームの分割を介し取得された各データブロックのフィンガープリントとを比較し、重複データブロックをクエリするクエリ部であって、前記クエリ部により取得された非重複データブロックが新たなデータブロックとして利用される、クエリ部と、
前記新たなデータブロックを表す少なくとも１つの第２スケッチ値を取得し、前記第２アルゴリズムに従って各第２スケッチ値に対応する第２物理ノードを前記第２スケッチ値により特定し、各第２スケッチ値と各第２スケッチ値により表されるデータブロックのストレージアドレスとの間の対応関係を前記対応する第２物理ノードに格納する更新部と、
を有する装置を提供する。
【００１１】
第２の態様に関連して、第１の可能な実現方法では、前記受信部は、
前記レスポンスメッセージに搬送される各ストレージアドレスのヒット数に関する統計量を収集するよう構成される統計量収集サブ部と、
前記統計量収集サブ部の統計結果に従って、前記第１ストレージアドレスとして最大ヒット数を有するｓ個のストレージアドレスを選択するよう構成されるアドレス取得サブ部であって、ｓは１以上である、アドレス取得サブ部と、
を有する。
【００１２】
第２の態様及び第２の態様の第１の可能な方法に関連して、第２の可能な実現方法では、本装置は更に、
所定のストレージポリシーに従って、前記新たなデータブロックと前記新たなデータブロックのフィンガープリントとが書き込まれるストレージアドレスを選択するよう構成されるライトアドレス取得部と、
所定のストレージ条件が充足すると、前記新たなデータブロックと前記新たなデータブロックのフィンガープリントとを、前記選択されたストレージアドレスに対応するストレージ領域に書き込むよう構成される書き込み部と、
を更に有する。
【００１３】
第２の態様の第２の可能な方法に関連して、第３の可能な実現方法では、前記書き込む部は、前記新たなデータブロックを前記現在の物理ノードのキャッシュに格納するよう構成され、前記現在の物理ノードのキャッシュのデータが第２所定閾値に達し、前記所定のストレージ条件が充足されると、前記新たなデータブロックと前記新たなデータブロックのフィンガープリントとを前記選択されたストレージアドレスに対応するストレージ領域に書き込むよう構成される。
【００１４】
本発明の実施例の第３の態様は更に、クラスタシステムにおけるデータ処理装置であって、プロセッサと、メモリと、バスとを有し、
前記プロセッサと前記メモリとは、前記バスを介し互いに通信し、
前記メモリは、プログラムを格納するよう構成され、
前記プロセッサは、前記メモリのプログラムを実行し、
当該プログラムは、
現在の物理ノードにより受信されたデータストリームをｍ個のデータブロックに分割し、各データブロックのフィンガープリントを取得する分割部であって、ｍは１以上の整数である、分割部と、
第２アルゴリズムに従って前記ｎ個の第１スケッチ値の各第１スケッチ値に対応し、前記クラスタシステム内にある第１物理ノードを特定する特定部と、
各第１スケッチ値をクエリのため前記対応する第１物理ノードに送信する送信部と、
第１物理ノードから少なくとも１つのレスポンスメッセージを受信し、前記レスポンスメッセージから第１ストレージアドレスを取得する受信部と、
前記第１ストレージアドレスにより指示されるストレージ領域に格納されるデータブロックのフィンガープリントと、前記データストリームの分割を介し取得された各データブロックのフィンガープリントとを比較し、重複データブロックをクエリするクエリ部であって、前記取得された非重複データブロックが新たなデータブロックとして利用される、クエリ部と、
前記新たなデータブロックを表す少なくとも１つの第２スケッチ値を取得し、前記第２アルゴリズムに従って各第２スケッチ値に対応する第２物理ノードを前記第２スケッチ値により特定し、各第２スケッチ値と各第２スケッチ値により表されるデータブロックのストレージアドレスとの間の対応関係を前記対応する第２物理ノードに格納する更新部と、
を有するデータ処理装置を提供する。
【００１５】
第３の態様に関連して、第１の可能な実現方法では、
前記受信部は、
前記レスポンスメッセージから前記第１スケッチ値に対応するストレージアドレスを取得し、前記レスポンスメッセージに搬送される各ストレージアドレスのヒット数に関する統計量を収集するよう構成される統計量収集サブ部と、
前記統計量収集サブ部の統計結果に従って、前記第１ストレージアドレスとして最大ヒット数を有するｓ個のストレージアドレスを選択するよう構成されるアドレス取得サブ部であって、ｓは１以上である、アドレス取得サブ部と、
を有する。
【００１６】
第２の態様及び第２の態様の第１の可能な方法に関連して、第２の可能な実現方法では、本装置は更に、
所定のストレージポリシーに従って、前記新たなデータブロックと前記新たなデータブロックのフィンガープリントとが書き込まれるストレージアドレスを選択するよう構成されるライトアドレス取得部と、
所定のストレージ条件が充足すると、前記新たなデータブロックと前記新たなデータブロックのフィンガープリントとを、前記選択されたストレージアドレスに対応するストレージ領域に書き込むよう構成される書き込み部と、
を更に有する。
【００１７】
第２の態様の第２の可能な方法に関連して、第３の可能な実現方法では、前記書き込む部は、前記新たなデータブロックを前記現在の物理ノードのキャッシュに格納するよう構成され、前記現在の物理ノードのキャッシュのデータが第２所定閾値に達し、前記所定のストレージ条件が充足されると、前記新たなデータブロックと前記新たなデータブロックのフィンガープリントとを前記選択されたストレージアドレスに対応するストレージ領域に書き込むよう構成される。
【００１８】
本発明の実施例の第４の態様は、データ処理のためのコンピュータプログラムであって、当該コンピュータプログラムは、プログラムコードを格納するコンピュータ可読記憶媒体を有し、プログラムコードに含まれる命令は、
現在の物理ノードにより受信されたデータストリームをｍ個のデータブロックに分割し、各データブロックのフィンガープリントを取得し、第１アルゴリズムに従って前記データストリームを表すｎ個の第１スケッチ値を取得するステップであって、ｍは１以上の整数であり、ｎは１以上であって、ｍ以下の整数である、取得するステップと、
第２アルゴリズムに従って前記ｎ個の第１スケッチ値の各第１スケッチ値に対応し、前記クラスタシステム内にある第１物理ノードを特定し、各第１スケッチ値をクエリのため前記対応する第１物理ノードに送信するステップと、
前記ｎ個の第１スケッチ値に対応する第１物理ノードから少なくとも１つのレスポンスメッセージを受信し、前記レスポンスメッセージから第１ストレージアドレスを取得するステップと、
受信した全てのストレージアドレスから第１ストレージアドレスを取得し、前記第１ストレージアドレスにより指示されるストレージ領域に格納されるデータブロックのフィンガープリントと、前記データストリームの分割を介し取得された各データブロックのフィンガープリントとを比較し、重複データブロックをクエリするステップとであって、取得された非重複データブロックが新たなデータブロックとして利用される、クエリするステップと、
前記新たなデータブロックを表す少なくとも１つの第２スケッチ値を取得し、前記第２アルゴリズムに従って各第２スケッチ値に対応する第２物理ノードを前記第２スケッチ値により特定し、各第２スケッチ値と各第２スケッチ値により表されるデータブロックのストレージアドレスとの間の対応関係を前記対応する第２物理ノードに格納するステップと、
を実行するのに利用される。
【発明の効果】
【００１９】
本発明の実施例では、重複データクエリが受信されたデータストリームに対して実行されると、各第１スケッチ値に対応し、クラスタシステム内にある第１物理ノードが、データストリームを表す第１スケッチ値に従って特定され、その後、データストリームを表す第１スケッチ値が、重複データクエリのため特定された物理ノードに送信され、重複データクエリを実行するための特定された物理ノードの個数は、クラスタシステムのノード数の増加により増加せず、各ノードの計算量は、クラスタシステムのノード数の増加により増加せず、クラスタシステムの重複解除パフォーマンスが効果的に向上する。
【図面の簡単な説明】
【００２０】
本発明の実施例又は従来技術における技術手段をより明確に説明するため、以下において、実施例又は従来技術を説明するのに要求される添付した図面が概略的に紹介される。明らかに、以下の説明における添付した図面は、本発明のいくつかの実施例を単に示し、当業者は、創作的な努力なく添付した図面から他の図面を依然と導出してもよい。
【図１】図１は、本発明によるクラスタシステムにおけるデータ処理方法の実施例のフローチャートである。
【図２】図２は、本発明の実施例によるデータストリームの受信後の物理ノードにより実行されるブロック分割及びサンプリングの概略図である。
【図３】図３は、本発明の実施例による物理ノードの内部構造の概略図である。
【図４】図４は、本発明によるクラスタシステムにおける他のデータ処理方法の実施例のフローチャートである。
【図５】図５は、本発明によるクラスタシステムにおける他のデータ処理方法の実施例のフローチャートである。
【図６】図６は、本発明の実施例による他の物理ノードの内部構造の概略図である。
【図７】図７は、本発明によるクラスタシステムにおける他のデータ処理方法の実施例のフローチャートである。
【図８】図８は、本発明の実施例によるデータマイグレーションの概略図である。
【図９】図９は、本発明の実施例によるクラスタシステムにおけるデータ処理装置の構成図である。
【図１０】図１０は、本発明の実施例によるクラスタシステムにおける他のデータ処理装置の構成図である。
【発明を実施するための形態】
【００２１】
以下において、本発明の実施例における添付した図面を参照して、本発明の実施例における技術的手段が明確かつ完全に説明される。明らかに、説明される実施例は本発明の実施例の全てでなく単なる一部である。創作的な努力なく本発明の実施例に基づき当業者により取得される他の全ての実施例は、本発明の保護範囲に属する。
【００２２】
本発明の実施例は、クラスタシステムが複数の物理ノードを含むストレージのためのクラスタシステムにおいて適用可能である。重複排除エンジンを有する物理ノードは、本発明の実施例の実行主体として利用されてもよく、重複排除タスクの取得後に本発明の実施例の方法を実行する。
【００２３】
図１は、本発明によるクラスタシステムにおけるデータ処理方法の実施例のフローチャートであり、図１に示されるように、本実施例の方法は以下を含むものであってもよい。
【００２４】
ステップ１０：現在の物理ノードにより受信されたデータストリームをｍ個のデータブロックに分割し、各データブロックのフィンガープリントを取得する。ただし、ｍは１以上の整数である。
【００２５】
クラスタシステムにおいて、物理ノードは、本発明の実施例のデータ処理方法を実行する装置が当該物理ノードにインストールされている限り、クラスタ重複排除タスクを実行するためのノードとして利用されてもよい。
【００２６】
データストリームの受信後、現在の物理ノードは、データストリームのデータをｍ個のデータブロックに分割し、各データブロックのフィンガープリントを取得する。
【００２７】
ステップ１１：第１アルゴリズムに従ってデータストリームを表すｎ個の第１スケッチ値を取得する。ただし、ｎは１以上であって、ｍ以下の整数である。
【００２８】
データストリームを表すｎ個の第１スケッチ値が、所定のアルゴリズムを介して取得され、説明の便宜上、データストリームを表す第１スケッチ値を取得するためのアルゴリズムは第１アルゴリズムと呼ばれ、受信したデータストリームを表すスケッチ値は第１スケッチ値と呼ばれる。
【００２９】
第１アルゴリズムは、それがデータストリームを表す第１スケッチ値を取得可能である限り、本発明の実施例に限定されるものでない。例えば、分割を介し取得されるデータブロックは直接サンプリングされ、サンプリングされたｎ個のデータブロックのスケッチ値が計算され、計算されたスケッチ値が、受信したデータストリームを表すスケッチ値として利用される。
【００３０】
任意的には、サンプリングされたデータをより均等にするため、本発明の実施例では、第１アルゴリズムによるデータストリームを表すｎ個のスケッチ値の取得は、以下のステップを含むものであってもよい。
【００３１】
受信したデータブロックにより取得されるデータブロックのフィンガープリントは、ｎ個の第１フィンガープリントグループにグループ化され、各第１フィンガーグループは少なくとも２つのデータブロックのフィンガープリントを含む。
【００３２】
各第１フィンガープリントグループについて、ｎ個の第１スケッチ値を取得するため、各フィンガープリントグループを表す第１スケッチ値が取得される。
【００３３】
ｎが１に等しい場合、それは、受信したデータストリームから取得されるデータブロックに対応するフィンガープリントが１つの第１フィンガープリントグループにグループ化され、１つのフィンガープリントは、分割を介し取得されたデータブロックに対応するフィンガープリントから第１フィンガープリントグループの第１スケッチ値として直接サンプリングされる。
【００３４】
本発明の実施例では、複数の連続するデータブロックが１つの第１フィンガープリントグループにグループ化され、おそらく、第１フィンガープリントグループを取得するためデータブロックを分割するための複数の方法が存在し、本実施例に限定されるものでない。
【００３５】
本発明の実施例では、第１スケッチ値がデータストリームをデータブロックに分割し、データブロックに対応するフィンガープリントをグループ化する方法により取得される場合、第１スケッチ値が対応する第１フィンガープリントグループを表すことができる限り、各フィンガープリントグループから第１スケッチ値を取得する複数の方法があってもよい。例えば、データブロックのフィンガープリントのうち最大のフィンガープリントは第１スケッチ値として選択されてもよく、あるいは、１以上のデータブロックのフィンガープリント情報が第１フィンガープリントグループから第１スケッチ値としてランダムに選択され、これは、本発明の実施例において限定されるものでない。
【００３６】
本実施例では、最小のフィンガープリント、すなわち、最小フィンガープリントの値がまた、最小フィンガープリントが属するフィンガープリントグループを表す第１スケッチ値として、第１フィンガープリントグループの全てのデータブロックのフィンガープリント情報から選択されてもよい。
【００３７】
ステップ１２：第２アルゴリズムに従ってｎ個の第１スケッチ値の各第１スケッチ値に対応し、クラスタシステム内にある第１物理ノードを特定する。
【００３８】
本発明の実施例では、説明の便宜上、特定された第１スケッチ値に対応する物理ノードは第１物理ノードと呼ばれ、第１物理ノードを特定するためのアルゴリズムは第２アルゴリズムと呼ばれ、１つの第１スケッチ値が１つの第１物理ノードに対応する場合、ｎ個の第１スケッチ値はｎ個の第１物理ノードに対応してもよく、本発明の実施例はおそらくこれに限定されない。
【００３９】
複数の第２アルゴリズムがあってもよい。例えば、ルート抽出及び丸め処理が、当該値がｍより小さくなるまで第１スケッチ値に対して実行され、最終的な結果は、対応する第１物理ノードを取得するため丸められる。
【００４０】
本実施例では、採用される第２アルゴリズムは更に、第１スケッチ値によるモジュロ演算が、クラスタシステムの全ての物理ノードの個数に対して実行され、第１スケッチ値に対応し、クラスタシステム内にある第１物理ノードが取得される。
【００４１】
ステップ１３：クエリのため各第１スケッチ値を対応する第１物理ノードに送信し、ｎ個の第１スケッチ値に対応する第１物理ノードから少なくとも１つのレスポンスメッセージを受信し、レスポンスメッセージから第１ストレージアドレスを取得する。
【００４２】
本発明の実施例では、クラスタシステムにおいて、各物理ノード又は大部分の物理ノードはインデックステーブルを格納し、スケッチ値と当該スケッチ値により表される格納されているデータブロックのストレージアドレスとの間の対応関係が、インデックステーブルに格納され、インデックステーブルは、所定のプリシーに従ってクラスタシステムの物理ノードに格納され、データブロックと当該データブロックに対応するフィンガープリント情報とが、異なるストレージアドレスによって指示されるストレージ領域に格納される。
【００４３】
各物理ノードのインデックステーブルは、完全なインデックステーブルであってもよく、格納されているデータの全てのスケッチ値とクラスタシステムにおける当該スケッチ値により表される格納されているデータブロックのストレージアドレスとの間の対応関係を含むものであってもよいことに留意すべきであり、完全なインデックステーブルの一部はまた、物理ノードにおける重複ブロックをクエリするための計算量を低減するため、所定のポリシーに従って各物理ノードに格納されてもよい。後者の方法が本実施例において採用されてもよい。物理ノードにおいてインデックステーブルの各インデックスエントリをどのように格納するかが、以下において詳細に説明される。
【００４４】
本発明の実施例では、インデックステーブルは、所定のポリシーに従って物理ノードに格納され、特定の物理ノードのインデックステーブルのデータと物理ノードのデータとの間には直接的な関係はなく、インデックステーブルのみが所定の割当ポリシーに従って当該物理ノードに格納される。
【００４５】
具体的な実現形態では、１つのストレージアドレスに対応するストレージ領域は複数のグループのデータを有してもよいため、各グループからスケッチ値が選択される場合、１つのストレージアドレスが複数の異なるスケッチ値に対応するケースが生じる可能性があり、従って、インデックステーブルの同一のストレージアドレスが複数の異なるスケッチ値に対応する可能性がある。しかしながら、１つの同一のスケッチ値は１つのストレージアドレスに対応する。複数の第１スケッチ値がインデックステーブルにおいてクエリされるとき、複数の対応するストレージアドレスが取得されてもよく、第１ストレージアドレスが第１スケッチ値に対応するストレージアドレスにから選択されるとき、第１ストレージアドレスを選択するためのルールは予め設定されてもよいし、あるいは、実際の状況に応じてユーザにより設定されてもよく、本実施例では限定されない。
【００４６】
例えば、第１スケッチ値に対応するストレージアドレスは、レスポンスメッセージから取得されてもよく、レスポンスメッセージに搬送される各ストレージアドレスのヒット数に関する統計量が収集され、最大ヒット数を有するｓ個のストレージアドレスが第１ストレージアドレスとして選択される。ただし、ｓは１以上である。
【００４７】
具体的な実現形態では、第１スケッチ値を搬送するクエリリクエストを受信すると、第１物理ノードは、ローカルに格納されているインデックステーブルに従って第１スケッチ値と同じスケッチ値をマッチングし、レスポンスメッセージを介し一致したスケッチ値に対応するストレージアドレスを当該クエリリクエストを送信した物理ノードにフィードバックする。各第１スケッチ値は１つの第１物理ノードに対応し、従って、複数の第１物理ノードがクエリリクエストを受信し、当該クエリリクエストに従ってクエリをローカルに実行する。ストレージアドレスがクエリを介し検出された場合、ストレージアドレスは、クエリリクエストを送信したノードに返され、クエリリクエストを送信したノードは異なる第１物理ノードにより返された複数のストレージアドレスを受信してもよく、ストレージアドレスがクエリを介し検出されなかった場合、例えば、０などのヌル値がフィードバックされるか、又はフィードバックが返されず、ストレージアドレスがクエリを介し検出されなかったことを具体的に表す方法は、ユーザにより設定されてもよい。
【００４８】
第１物理ノードによりフィードバックされるストレージアドレスが、各第１スケッチ値がクエリのため対応する第１物理ノードに送信された後に受信されなかった場合、データストリームの分割を介し取得されるデータブロックが非重複データブロックとして利用され、その後、ステップ１５が実行される。
【００４９】
ステップ１４：第１ストレージアドレスにより指示されるストレージ領域に格納されるデータブロックのフィンガープリントと、受信したデータブロックの分割を介し取得される各データブロックのフィンガープリントとを比較し、重複データブロックをクエリする。ただし、取得された非重複データブロックは新たなデータブロックとして利用される。
【００５０】
具体的な実現形態では、現在の物理ノードは、受信したデータストリームの処理後にデータブロックとフィンガープリント情報とをキャッシュに格納し、複数の方法を利用して、データブロックのフィンガープリントを比較してもよい。例えば、方法１では、第１ストレージアドレスに対応するストレージ領域のデータブロックが、現在の物理ノードのキャッシュにロードされ、受信したデータストリームに対応する各データブロックのフィンガープリントが、重複ブロッククエリに対して実行される。方法２では、クエリ指示が、第１ストレージアドレスにより指示される物理ノードに送信される。ここで、データストリームの分割を介し取得されるｍ個のデータブロックのフィンガープリントが当該クエリ指示に搬送され、第１ストレージアドレスにより指示される物理ノードにより返されるクエリ結果が受信される。方法１では、現在ノードのキャッシュに格納されるフィンガープリント情報が重複データクエリにおいて利用されてもよく、これは重複排除レートを更に向上させることができる。
【００５１】
インデックステーブルのインデックスエントリが初期化されるとき、ユーザはまた、インデックステーブルにおいてシステムに格納されているデータに従って、既知のスケッチ値と当該既知のスケッチ値により表されるデータブロックのストレージアドレスとの間の対応関係を予め格納してもよく、特定の方法が本発明の実施例において限定されるものでない。インデックステーブルはまた、初期化中にヌルであってもよく、重複データクエリ中、取得した新たなデータブロックがストレージシステムに格納されると、取得したスケッチ値と当該スケッチ値により表される新たなデータブロックのストレージアドレスとがインデックステーブルに挿入され、これにより、インデックステーブルは定期的に更新される。従って、本発明の実施例は更に以下を含む。
【００５２】
ステップ１５．新たなデータブロックを表す少なくとも１つの第２スケッチ値を取得し、第２アルゴリズムに従って各第２スケッチ値に対応する第２物理ノードを第２スケッチ値により特定し、各第２スケッチ値と各第２スケッチ値により表されるデータブロックのストレージアドレスとの間の対応関係を対応する第２物理ノードに格納する。
【００５３】
本発明の実施例では、クエリを介し検出された非重複データブロックが新たなデータブロックとして利用され、クエリを介し検出された新たなデータブロックがあるサイズに到達し、格納される必要があるとき、システムにおける新たなデータブロックのストレージ位置がインデックステーブルにおいて示される必要があり、インデックステーブルは、定期的に更新される必要がある。ストレージアドレスが新たなデータブロックについて取得されると、当該新たなデータブロックを表すスケッチ値が取得され、説明の便宜上、第２スケッチ値と呼ばれ、第２物理ノードが第２アルゴリズムに従って特定され、各第２スケッチ値と各第２スケッチ値により表されるデータブロックのストレージアドレスとの間の対応関係が、対応する第２物理ノードに格納され、これにより、クラスタシステムのインデックスエントリの定期的な更新を実現できる。
【００５４】
第２スケッチ値を取得するための方法は、第１スケッチ値を取得するためのアルゴリズムと同じであってもよい。例えば、第１アルゴリズムが採用されてもよく、第１スケッチ値のセットが第２スケッチ値のセットのサブセットであることが保証される場合、又は第２スケッチ値のセットが第１スケッチ値のセットである場合、他のアルゴリズムが採用されてもよい。
【００５５】
本実施例の手段が、以下において具体的な実現方法の具体例を参照して詳細に説明される。図２は、データストリームの受信後に現在の物理ノードにより実行されるブロック分割及びサンプリングの概略図である。本実施例では、複数のデータブロックが１つのスーパーデータブロック（スーパーチャンク）として見なされてもよく、具体的な実現形態では、より正確なグループ化のため、データブロックに対応するフィンガープリントがグループ化され、グループのフィンガープリントに対応するデータブロックがスーパーデータブロックであり、第１スケッチ値はまたスーパーデータブロックスケッチ値（スーパーチャンクＩＤ、ＳＩＤ）と呼ばれてもよい。おそらく、データストリームの分割を介し取得されるデータブロックはまた直接グループ化されてもよい。図２を参照して、データストリームの受信後、現在の物理ノードは、受信したデータをデータブロックに分割し、複数の連続するデータブロックが１つのグループにグループ化され、すなわち、添付図面のスーパーチャンクにグループ化される。グループ化の方法は、可変長ブロックの分割や固定長ブロックの分割などの方法を含み、本実施例ではこれに限定されるものでない。データブロックは各スーパーチャンクから取得され、取得されたデータブロックに対応するフィンガープリントは、各スーパーチャンクを表すＳＩＤとして利用される。
【００５６】
一例としてクラスタシステムの物理ノードを抽出することによって、物理ノードの内部構造の一例となる概略図のための図３が参照されてもよい。キャッシュとストレージ領域とが各物理ノードに含まれてもよく、具体的な実現形態では、クリアパフォーマンスを向上させるため、インデックステーブルが物理ノードのキャッシュに格納され、第２スケッチ値と当該第２スケッチ値により表される格納されているデータブロックのストレージアドレスとの間の対応関係が、インデックステーブルに格納される。上述されるように、各物理ノードのインデックステーブルは、完全なインデックステーブルであってもよく、全ての第２スケッチ値とクラスタシステムにおける第２スケッチ値により表される格納されているデータブロックのフィンガープリントのストレージアドレスとの間の対応関係を含む。完全なインデックステーブルの一部はまた、所定のポリシーに従って各物理ノードに格納されてもよい。具体的な実現形態では、メモリの使用を低下させるため、後者の方法が採用されてもよく、完全なインデックステーブルの一部が、所定のポリシーに従って各物理ノードに格納される。例えば、一例としてスケッチ値Ａを抽出することによって、物理ノードは、クラスタシステムの全ての物理ノードの合計に対するＡによるモジュロ演算を実行することによって特定される。ＡとＡにより表される格納されているデータブロックのストレージアドレスとの間の対応関係が特定された物理ノードに格納され、重複データクエリ中、第１スケッチ値に対応する第１物理ノードを取得するため、取得された第１スケッチ値によるモジュロ演算が、クラスタシステムの物理ノードの合計に対して実行される。
【００５７】
各物理ノードは、ストレージ装置を有し、当該ストレージ装置は、各物理ノードが長時間データを格納する機能を有することを可能にし、それは磁気ディスクであってもよく、ＳＳＤなどの他のストレージ装置であってもよい。各物理ノードのストレージ装置は、単一のインスタンスレポジトリ（シングルインスタンスレポジトリＳＩＲ）と呼ばれ、図３において、磁気ディスクが一例として取り上げられる。物理ノードのストレージ装置には多数のストレージ領域があってもよく、各ストレージ領域は、データを格納するためのコンテナとして例示的にみなされてもよく、各ストレージコンテナは、クラスタシステムにおける１つの一意的なシリアル番号を有し、それはストレージコンテナシリアル番号（コンテナＩＤＣＩＤ）と呼ばれてもよい。コンテナシリアル番号は、例えば、クラスタシステムの何れの物理ノードの何れのストレージ領域であるかなど、クラスタシステムにおけるストレージコンテナの位置を示す。従って、具体的な実現形態では、格納されているデータブロックの上述したストレージアドレスは、データブロックが何れの物理ノードの何れのストレージアドレスに格納されているかを示すＣＩＤとして実現され、スケッチ値と上述したインデックステーブルにおける当該スケッチ値により表される格納されているデータブロックのストレージアドレスとの間の対応関係は、ＳＩＤとＣＩＤとの間の対応関係として示されてもよく、ストレージデータブロックに加えて、データブロックに対応するフィンガープリント情報が更に各ストレージ領域に格納されてもよい。バッファストレージ領域（コンテナバッファ）が更に、各物理ノードのキャッシュに含まれてもよく、特定を介し取得される新たなデータブロックを一時的に格納するよう構成される。
【００５８】
従来技術では、サンプリングされたフィンガープリント情報は、クエリのため全てのノードに送信され、このようにして、クラスタシステムのノード数が増える場合、計算量はますます大きくなる。実験は、クラスタシステムのノード数が１６を超えると、システムの重複排除パフォーマンスがかなりの程度低下することを示す。本発明の実施例では、サンプリングされたスケッチ値がクエリのため全てのノードに送信される従来技術と異なって、重複データクエリが受信されたデータストリームに対して実行されるとき、各第１スケッチ値に対応し、クラスタシステム内にある第１物理ノードが、データストリームを表す第１スケッチ値に従って特定され、その後、データストリームを表す第１スケッチ値は、重複データクエリのため特定された物理ノードに送信され、重複データクエリの手順は、クラスタシステムのノード数の増加によっては変化せず、各ノードの計算量は、クラスタシステムのノード数の増加によっては増加しない。
【００５９】
図４を参照して、本発明は更に、他のクラスタデータ処理方法の実施例を提供し、図１に対応するクラスタシステムにおけるデータ処理方法との相違は、クラスタシステムにおける重複データクエリが終了した後、受信したデータストリームに新たなデータブロックがあるか判断し、当該新たなデータブロックを格納することが要求されることであり、他のステップは図１に対応する実施例と同じである。従って、図１に対応する実施例に基づき、本方法は更に以下を含むものであってもよい。
【００６０】
ステップ４６：所定のストレージポリシーに従って、新たなデータブロックと当該新たなデータブロックのフィンガープリントとが書き込まれるストレージアドレスを選択する。
【００６１】
新たなデータブロックのストレージポリシーは、ユーザにより予め設定されてもよく、複数のポリシーがあってもよい。例えば、ポリシー１では、クラスタシステムの各物理ノードのロード情報がまず取得され、データが移行される物理ノードがロード情報に従って選択され、新たなデータブロックと当該新たなデータブロックのフィンガープリントとが書き込まれるストレージアドレスが、データが移行される選択された物理ノードから取得され、このようにして、全ての物理ノードにおけるロードバランシングが実行される。ポリシー２では、ロード情報は決定されなくてもよく、新たなデータブロックと当該新たなデータブロックのフィンガープリントとが書き込まれるストレージアドレスが現在の物理ノードから直接取得され、このようにして、ノード間のやりとりが低減される。従って、具体的なストレージポリシーは実際の状況に従ってユーザにより設定されてもよく、本発明の実施例において限定されるものでない。
【００６２】
ポリシー１が採用される場合、ロード情報に従ってデータを書き込む複数の方法があってもよい。例えば、閾値が予め設定され、第１所定閾値と呼ばれてもよい。クラスタシステムの全ての物理ノードの平均ロード値が第１所定閾値を超過するとき、データが書き込まれるノードが、平均ロード値よりロード値が小さい物理ノードから選択され、新たなデータブロックと当該新たなデータブロックのフィンガープリントとが書き込まれるストレージアドレスが、データが書き込まれるノードから取得され、クラスタシステムの全ての物理ノードの平均ロード値が第１所定閾値以下であるとき、新たなデータブロックと当該新たなデータブロックのフィンガープリントとが書き込まれるストレージアドレスが、現在の物理ノードから取得される。
【００６３】
ロード値に従ってデータ移行を実行するための他の方法は以下を含むものであってもよい。
【００６４】
Ａ１：クラスタシステムの物理ノードのロード情報を取得し、クラスタシステムの何れか２つの物理ノードの間のロード差が第１閾値より大きいとき、データが移行されるノードが、より低いロードの物理ノードから選択され、データが移行されるノードから新たなデータブロックと当該新たなデータブロックのフィンガープリントとが書き込まれるストレージアドレスを取得する。
【００６５】
Ａ２：クラスタシステムの何れか２つの物理ノードの間のロード差が第１閾値以下であるとき、現在の物理ノードから新たなデータブロックと当該新たなデータブロックのフィンガープリントとが書き込まれるストレージアドレスを取得する。
【００６６】
ロード情報は、現在の物理ノードから取得されてもよく、ロード情報はまた、第三者がロード情報を取得した後、現在の物理ノードによって第三者から直接取得されてもよい。
【００６７】
ステップ４７：所定のストレージ条件が充足されると、新たなデータブロックと当該新たなデータブロックのフィンガープリントとを、選択されたストレージアドレスに対応するストレージ領域に書き込む。
【００６８】
任意的には、所定のストレージが条件が充足されることは、新たなデータブロックが現在の物理ノードのキャッシュに格納され、現在の物理ノードのキャッシュのデータが第２所定閾値に達すると、所定のストレージ条件が充足されることを含むものであってもよい。
【００６９】
図３の具体例に説明されるように、コンテナバッファが各物理ノードに含まれてもよく、特定を介して取得された新たなデータブロックを一時的に格納するよう構成され、コンテナバッファに格納されるデータのサイズが第２閾値を超過すると、所定のストレージ条件が充足されたとみなされ、ユーザは実際の状況に従って第２閾値を設定してもよい。このことは、本実施例では限定されるものでない。
【００７０】
本発明の実施例では、新たなデータブロックのストレージアドレスが取得された後、第２スケッチ値と当該第２スケッチ値により表されるデータブロックの対応する第２物理ノードにおけるストレージアドレスとの間の対応関係を格納するための具体的な機会は、本発明の実施例において限定されるものでない。
【００７１】
図４に対応する実施例により提供されるクラスタシステムにおけるデータ処理方法では、新たなデータブロックが格納されるとき、ロードバランシングが実現され、システムパフォーマンスが向上する。
【００７２】
図１に対応するデータ処理方法に基づき、図５を参照して、バーチャルノードがクラスタシステムに含まれるケースについて、本発明は他の実施例を提供する。少なくとも１つのバーチャルノードが、クラスタシステムの物理ノードの分割を介し論理的に取得され、クラスタシステムの全てのバーチャルノードと全ての物理ノードとの間の対応関係（ＶＰＴ）が各物理ノードに格納され、本発明の実施例では、少なくとも１つのバーチャルノードが各物理ノードの分割を介し論理的に取得されることが仮定される。重複データクエリ方法は以下を含む。
【００７３】
ステップ５０：ｍ個のデータブロックを取得するため、現在の物理ノードにより受信されたデータストリームを処理し、各データブロックのフィンガープリントを取得する。
【００７４】
ステップ５１：第１アルゴリズムに従ってデータストリームを表すｎ個の第１スケッチ値を取得する。ここで、ｎは１以上であって、ｍ以下の整数である。
【００７５】
データストリームを処理する方法と、ステップ５０及び５１において第１スケッチ値を取得する方法とは、図１に対応する実施例と同じであり、ここでは繰り返し説明されない。
【００７６】
ステップ５２：第２アルゴリズムに従ってｎ個の第１スケッチ値の各スケッチ値に対応し、クラスタシステム内にある第１バーチャルノードを特定し、現在の物理ノードのバーチャルノードと物理ノードとの間の対応関係をクエリすることによって、第１バーチャルノードに対応する第１物理ノードを取得する。ここで、各第１スケッチ値は１つの第１バーチャルノードに対応し、１つの第１バーチャルノードは同時に複数の第１スケッチ値に対応してもよい。
【００７７】
説明の便宜上、第１スケッチ値に従って特定される対応するバーチャルノードは第１バーチャルノードと呼ばれ、少なくとも１つのバーチャルノードは、クラスタストレージシステムの各物理ノードの分割を介し取得されてもよく、具体的な実現手段では、２以上のバーチャルノードが各物理ノードの分割を介し取得されてもよく、各バーチャルノードは一意的なシリアル番号を有し、クラスタシステムにおけるバーチャルノードと物理ノードとの間の対応関係が各物理ノードに格納されてもよく、それは、バーチャルノードが何れの物理ノードにあるかを示す。
【００７８】
ステップ５３：各第１スケッチ値をクエリのための対応する第１物理ノードの第１バーチャルノードに送信し、第１物理ノードからレスポンスメッセージを受信し、レスポンスメッセージから第１スケッチ値に対応するストレージアドレスを取得し、第１スケッチ値に対応するストレージアドレスから第１ストレージアドレスを選択する。
【００７９】
本発明の実施例では、クラスタシステムの各物理ノード又は大部分の物理ノードはインデックステーブルを格納し、予め取得されたスケッチ値と当該スケッチ値により表される格納されているデータブロックのストレージアドレスとの間の対応関係がインデックステーブルに格納される。インデックステーブルは、所定のポリシーに従ってクラスタシステムの物理ノードに格納され、バーチャルノードが物理ノードの分割を介し取得された後、インデックステーブルは、物理ノードの分割を介し取得されたバーチャルノードに格納されてもよい。インデックステーブルの各インデックスエントリをバーチャルノードに格納する方法が、以下において詳細に説明される。
【００８０】
データブロックのクラスタシステムにバーチャルノードがない場合、インデックステーブルのストレージアドレスは、具体的には、何れかの物理ノードの何れかのストレージ領域を示し、クラスタシステムにバーチャルノードがある場合、ストレージアドレスは、具体的には、何れかのバーチャルノードの何れかのストレージ領域を示す。
【００８１】
同様に、各バーチャルノードのインデックステーブルは、完全なインデックステーブルであってもよく、全てのスケッチ値とクラスタシステムにおけるスケッチ値により表される格納されているデータブロックのフィンガープリントのストレージアドレスとの間の対応関係を含み、完全なインデックステーブルの一部はまた、メモリの利用を低減するため、所定のポリシーに従って各バーチャルノードに格納されてもよい。
【００８２】
ｎ個の第１スケッチ値の各スケッチ値に対応し、クラスタシステム内にある第１バーチャルノードが、第２アルゴリズムに従って特定される。同様に、第１スケッチ値がクラスタシステムの１つの一意的なバーチャルノードに対応させることが有効とすることができる限り、複数の第２アルゴリズム存在する。例えば、一例として第１スケッチ値Ａを抽出することによって、重複データクエリがデータブロックに対して実行されると、第１スケッチ値に対応する第１バーチャルノードを取得するため、クラスタシステムの全てのバーチャルノードの個数に対して取得された第１スケッチ値によるモジュロ演算が実行され、その後、第１バーチャルノードに対応する第１物理ノードが、バーチャルノードと物理ノードとの間の対応関係に従って特定される。第１物理ノードが検出されると、第１物理ノードの第１バーチャルノードが検出される。
【００８３】
多数のストレージ領域が各バーチャルノードに含まれ、具体的な実現形態では、各ストレージ領域は、データを格納するためのコンテナとして例示的にみなされてもよく、各コンテナは、クラスタシステムにおける一意的なシリアル番号ＣＩＤを有し、当該番号は、クラスタシステムの何れのバーチャルノードの何れのストレージ領域に当該ストレージ領域が配置されているかを示す。データブロックに加えて、データブロックに対応するフィンガープリント情報がまた、各ストレージ領域に格納されてもよい。
【００８４】
バッファストレージ領域（コンテナバッファ）がまた、各物理ノードのキャッシュに含まれてもよく、特定を介し取得された新たなデータブロックを一時的に格納するよう構成される。
【００８５】
図１に対応する実施例と同様に、具体的な実現形態では、インデックステーブルの１つの同一のストレージアドレスが複数の異なるスケッチ値に対応してもよいが、１つのスケッチ値は１つのストレージアドレスに対応する。複数の第１スケッチ値がインデックステーブルにおいてクエリされるとき、複数の対応するストレージアドレスが取得されてもよく、第１ストレージアドレスが第１スケッチ値に対応するストレージアドレスから選択されるとき、第１ストレージアドレスを選択するためのルールは予め設定されてもよいし、あるいは、実際の状況に従ってユーザにより設定されてもよい。図１に対応する方法において第１ストレージアドレスを選択する説明が参照されるが、これは、本実施例において限定されるものでない。
【００８６】
本発明の実施例では、クエリリクエストを受信した後、物理ノードは、ローカルバーチャルノードにおいてクエリを実行し、ストレージアドレスがクエリを介し検出された場合、物理ノードは、当該クエリリクエストを送信したノードにクエリ結果をフィードバックする。具体的な実現形態では、クエリリクエストを受信した後、物理ノードは、ローカルバーチャルノードにおいてクエリを実行し、レスポンスメッセージにクエリ結果を配置することによって、クエリリクエストを送信した物理ノードにクエリ結果をフィードバックする。ストレージアドレスがクエリを介し検出された場合、クエリを介し検出されたストレージアドレスがレスポンスメッセージに配置され、ストレージアドレスがクエリを介し検出されない場合、ヌル値がレスポンスメッセージによりフィードバックされるか、あるいは、具体的な実現形態において、ストレージアドレスがクエリを介し検出されない場合、フィードバックは返されない。ユーザは、実際の状況に従って具体的な実現方法を設定してもよい。
【００８７】
現在の物理ノードがｎ個の第１スケッチ値に対応する第１物理ノードにより返されたストレージアドレスを受信しない場合、データストリームの分割を介し取得されたデータブロックが、非重複データブロックとして利用される。
【００８８】
ステップ５４：第１ストレージアドレスにより指示されたストレージ領域に格納されるデータブロックのフィンガープリントと、受信したデータストリームの分割を介し取得された各データブロックのフィンガープリントとを比較し、重複したデータブロックをクエリする。ここで、取得された非重複データブロックは、新たなデータブロックとして利用される。
【００８９】
具体的な実現形態では、現在の物理ノードは、受信したデータストリームの処理後にデータブロックとフィンガープリント情報とをキャッシュに格納し、データブロックのフィンガープリントを比較するための複数の方法が採用されてもよく、図１に対応する方法における説明が参照されてもよい。
【００９０】
ステップ５５：新たなデータブロックを表す少なくとも１つの第２スケッチ値を取得し、第２アルゴリズムに従って各第２スケッチ値に対応する第２バーチャルノードを第２スケッチ値により特定し、バーチャルノードと物理ノードとの間の対応関係に従って、第２バーチャルノードが配置される第２物理ノードを特定し、各第２スケッチ値と第２スケッチ値により表されるデータブロックのストレージアドレスとの間の対応関係を対応する第２物理ノードの第２バーチャルノードに格納する。
【００９１】
２つのバーチャルノードが一例としてクラスタシステムの物理ノードの分割を介し取得されるとすることによって、物理ノードの内部構造の一例となる概略図の図６が参照される。図６において、２つのバーチャルノード（ＶＮ）が１つの物理ノード（ＰＮ）の分割を介し取得され、インデックステーブルと長期間データを格納可能なストレージ装置とが１つのバーチャルノードに含まれる。バーチャルノードと物理ノードとの間の対応関係テーブル（ＶＰＴ）は、同時に各物理ノードに格納される。
【００９２】
従来技術では、サンプリングされたフィンガープリント情報は、クエリのため全てのノードに送信される。ノードにおけるクエリを実行する計算量はｚであり、ｍ個の物理ノードがあるとき、計算量はｍと乗算されたｚであることが仮定される。本実施例により提供されるバーチャルノードを有するクラスタシステムにおける重複排除方法では、重複データクエリが受信したデータストリームに対して実行されると、各第１スケッチ値に対応し、クラスタシステム内にある第１物理ノードが、データストリームを表す第１スケッチ値に従って特定され、その後、データストリームを表す第１スケッチ値が、重複データクエリのための特定されたバーチャルノードに送信される。特定されたバーチャルノードの個数は、クラスタシステムの物理ノードの個数の増加により増加せず、重複データクエリの手順は、クラスタシステムの重複排除パフォーマンスを効果的に向上させるため、クラスタシステムのノードの個数の増加により変化しない。
【００９３】
図７を参照して、本発明は更に、クラスタシステムにおけるデータ処理方法の実施例を提供し、図５に対応するクラスタシステムにおけるデータ処理方法との相違は、クラスタシステムにおける重複データクエリが終了した後、受信したデータストリームに新たなデータブロックがあるか判断し、新たなデータブロックを格納することが要求されることであり、他のステップは図５に対応する実施例と同じである。従って、図５に対応する実施例に基づき、本方法は更に以下を含むものであってもよい。
【００９４】
ステップ７６：所定のストレージポリシーに従って、新たなデータブロックと当該新たなデータブロックのフィンガープリントとが書き込まれるストレージアドレスを選択する。
【００９５】
新たなデータブロックのストレージポリシーは、ユーザにより予め設定されてもよく、複数のストレージポリシーがあってもよい。図４に対応する実施例において新たなデータブロックと当該新たなデータブロックに対応するフィンガープリントとが書き込まれるストレージアドレスを選択する方法に関する説明が参照されてもよく、データが移行される物理ノードが決定された後、物理ノード内のバーチャルノードのロードが考慮され、新たなデータブロックと当該新たなデータブロックのフィンガープリントとが書き込まれるストレージアドレスが、データが移行される選択された物理ノードにおいてロードがより低いバーチャルノードから取得されるという相違がある。
【００９６】
ステップ７７：所定のストレージ条件が充足されると、新たなデータブロックと当該新たなデータブロックのフィンガープリントとを選択されたストレージアドレスに対応するストレージ領域に書き込む。
【００９７】
図６の具体例に説明されるように、コンテナバッファが各物理ノードに含まれてもよく、特定を介し取得された新たなデータブロックを一時的に格納するよう構成され、コンテナバッファに格納されているデータのサイズが第２閾値を超過すると、所定のストレージ条件が充足されたとみなされてもよく、ユーザは、実際の状況に従って第２閾値を設定してもよく、これは、本実施例において限定されるものでない。
【００９８】
新たなデータブロックのストレージアドレスが取得された後、第２スケッチ値と当該第２スケッチ値により表されるデータブロックのストレージアドレスとの間の対応関係を対応する第２物理ノードに格納する具体的な機会は、本発明の実施例において限定されるものでない。
【００９９】
図７に対応する実施例により提供されるクラスタシステムにおけるデータ処理方法では、バーチャルノードのインデックステーブルは、重複データを検出する確率を更に向上させるため、定期的に更新される。
【０１００】
図８を参照して、バーチャルノードがクラスタシステムに含まれることに基づき、クラスタシステムの物理ノードにおけるデータ移行のための手段が提供される。例えば、図８において、１つの物理ノードが２つの物理ノードに拡張されるケースにおけるデータ移行の概略図が説明される。
【０１０１】
データ移行条件が充足されると、物理ノードＰＮ１のバーチャルノードの１つが他の物理ノードＰＮ２に一体的に移動され、これは、バーチャルノードＶＮ１のインデックステーブルと、ＶＮ１に属する単一のインスタンスレポジトリのデータとをＰＮ２に移動し、クラスタシステムにおける移行されるバーチャルノードと物理ノードとの間の対応関係を更新し、移行されるノードと物理ノードとの間の対応関係の更新をクラスタシステムにおける他の物理ノードに通知することを含む。クラスタシステムにおける全てのバーチャルノードと全ての物理ノードとの間の更新された対応関係は、新たに追加されたＰＮ２に格納される。
【０１０２】
データ移行条件は、データがクラスタシステムの物理ノードのキャパシティ拡張中に新たに追加された物理ノードに移行される必要があることであってもよく、また、ロードバランシングのため、ロードが高い物理ノードのデータがロードが低い物理ノードに移行されることであってもよい。データ移行条件は本発明の実施例において限定されるものでない。
【０１０３】
バーチャルノードがクラスタシステムにおける分割を介し取得されず、物理ノードのデータが移行されると、データブロックと当該データブロックのフィンガープリントのストレージアドレスとが変更されるため、データブロックの論理アドレスとＣＩＤとの間の対応関係が変更される必要があり、関連するＣＩＤのデータは多数の物理ノードに格納され、この結果、計算量は大変大きくなる。しかしながら、バーチャルノードにおけるデータは一体的に移動されるため、データ移行中に本発明の実施例により提供されるクラスタシステムを利用することによって、インデックステーブルのＣＩＤは、データがバーチャルノードに格納される位置を示し、従って、バーチャルノードの識別子が変更されない限り、ＣＩＤは変更される必要はなく、関連するバーチャルノードと物理ノードとの間の対応関係のみが変更され、これは、ノード拡張中の処理手順を簡単化し、計算量を大きく低減する。
【０１０４】
本発明の実施例は、ストレージのためクラスタシステムにおいて適用され、複数のストレージノードがクラスタシステムに含まれる。本発明の実施例により提供されるクラスタシステムのデータ処理装置は、クラスタシステムの上述されたデータ処理方法を実行するよう構成され、クラスタシステムの物理ノードに設定されるか、クラスタシステムのマネージャに設定されるか、又はクラスタシステムの別のノードとして設定されてもよい。データ処理装置が設定される具体的な位置は、本発明の実施例において限定されるものでない。
【０１０５】
図９を参照して、本発明の実施例は、クラスタシステムにおけるデータ処理装置９００を提供し、当該装置は以下を含む。
【０１０６】
分割部９０は、現在の物理ノードにより受信されたデータストリームをｍ個のデータブロックに分割し、各データブロックのフィンガープリントを取得するよう構成される。ここで、ｍは１以上の整数である。
【０１０７】
スケッチ値取得部９１は、第１アルゴリズムに従ってデータストリームを表すｎ個の第１スケッチ値を取得するよう構成される。ここで、ｎは１以上であって、ｍ以下の整数である。
【０１０８】
第１スケッチ値を取得するための第１アルゴリズムの上述した方法における説明が参照されてもよく、ここでは繰り返し説明されない。
【０１０９】
特定部９２は、第２アルゴリズムに従ってｎ個の第１スケッチ値の各第１スケッチ値に対応し、クラスタシステム内にある第１物理ノードを特定するよう構成される。
【０１１０】
特定部９２が第１物理ノードを特定する方法は多数あってもよい。例えば、当該値がｍ未満になるまで、第１スケッチ値に対してルート抽出及び丸め処理が実行され、最終的な結果が、対応する第１物理ノードを取得するため丸められ、各第１スケッチ値に対応し、クラスタシステム内にある第１物理ノードを取得するため、各第１スケッチ値によるモジュロ演算が、クラスタシステムの全ての物理ノードの個数に対して実行されてもよく、本発明の実施例では、特定部９２が、具体的に、各第１スケッチ値に対応し、クラスタシステム内にある第１物理ノードを取得するため、クラスタシステムの全ての物理ノードの個数に対して各第１スケッチ値によるモジュロ演算を実行するよう構成されてもよい。
【０１１１】
送信部９３は、各第１スケッチ値をクエリのため対応する第１物理ノードに送信するよう構成される。
【０１１２】
送信部９３により送信されたクエリリクエストの受信後、クラスタシステムの他のノードは、ローカルに格納されたインデックステーブルに従って、第１スケッチ値に対応するストレージアドレスがあるかクエリする。本発明の実施例は、クラスタシステムの各物理ノード又は大部分の物理ノードはインデックステーブルを格納し、スケッチ値と当該スケッチ値により表される格納されているデータブロックのストレージアドレスとの間の対応関係がインデックステーブルに格納され、インデックステーブルは、所定のポリシーに従ってクラスタシステムの物理ノードに格納され、データブロックと当該データブロックに対応するフィンガープリントとが、異なるストレージアドレスにより指示されるストレージ領域に格納される。
【０１１３】
受信部９４は、ｎ個の第１スケッチ値に対応する第１物理ノードから少なくとも１つのレスポンスメッセージを受信し、レスポンスメッセージから第１ストレージアドレスを取得するよう構成される。
【０１１４】
受信部９４は、レスポンスメッセージから第１スケッチ値に対応するストレージアドレスを取得し、レスポンスメッセージに搬送される各ストレージアドレスのヒット数に関する統計量を収集するよう構成される統計量収集サブ部９４１と、統計量収集サブ部９４１の統計結果に従って、第１ストレージアドレスとして最大ヒット数を有するｓ個のストレージアドレスを選択するよう構成されるアドレス取得サブ部９４２とを有してもよく、ここで、ｓは１以上である。
【０１１５】
クエリ部９５は、第１ストレージアドレスにより指示されるストレージ領域に格納されるデータブロックのフィンガープリントと、受信したデータストリームの分割を介し取得された各データブロックのフィンガープリントとを比較し、重複データブロックをクエリするよう構成され、クエリ部９５により取得された非重複データブロックが新たなデータブロックとして利用される。
【０１１６】
更新部９６は、新たなデータブロックを表す少なくとも１つの第２スケッチ値を取得し、第２アルゴリズムに従って各第２スケッチ値に対応する第２物理ノードを第２スケッチ値により特定し、各第２スケッチ値と各第２スケッチ値により表されるデータブロックのストレージアドレスとの間の対応関係を対応する第２物理ノードに格納するよう構成される。
【０１１７】
更新部９６による新たなデータブロックを表す第２スケッチ値を取得するためのアルゴリズムは、ここで限定されることなく、第１スケッチ値を取得するための第１アルゴリズムと同じであってもよい。
【０１１８】
各第２スケッチ値と各第２スケッチ値により表されるデータブロックのストレージアドレスとの間の対応関係は、インデックステーブルの１つのインデックスエントリとして利用される。本発明の実施例では、更新部９６は、設定されたポリシーに従って物理ノードにインデックステーブルを格納し、ある物理ノードのインデックステーブルのデータと当該物理ノードのデータとの間には直接的な関係はなく、インデックステーブルは、設定された割当ポリシーに従って当該物理ノードに格納されるだけである。インデックステーブルの説明のため上述した方法の説明が参照されてもよく、詳細はここでは繰り返し説明されない。
【０１１９】
上述した方法の説明を参照して、具体的な実現形態では、スケッチ値取得部９１が第１アルゴリズムに従ってデータストリームを表すｎ個の第１スケッチ値を取得する方法は複数あってもよい。例えば、スケッチ値取得部９１は、フィンガープリントグループ化サブ部９１１と取得サブ部９１２とを有してもよい。
【０１２０】
フィンガープリントグループ化サブ部９１１は、データブロックのｍ個のデータブロックのフィンガープリントをｎ個の第１フィンガープリントグループにグループ化するよう構成され、各第１フィンガープリントグループは、少なくとも２つのデータブロックのフィンガープリントを有する。
【０１２１】
取得サブ部９１２は、ｎ個の第１スケッチ値を取得するため、各フィンガープリントグループを表す第１スケッチ値を取得するよう構成される。
【０１２２】
取得サブ部９１２は、具体的には、各フィンガープリントグループから最小のフィンガープリントを、当該最小のフィンガープリントが属するフィンガープリントグループを表す第１スケッチ値として選択するよう構成されてもよい。
【０１２３】
クラスタシステムのデータ処理装置の受信部９４は更に、各第１スケッチ値をクエリのため対応する第１物理ノードに送信した後、第１物理ノードにより返されるストレージアドレスが受信されない場合、データストリームの分割を介し取得されるデータブロックを非重複データブロックとして利用し、その後に更新部９６をトリガするよう構成されてもよい。
【０１２４】
本発明の実施例により提供される装置は、クラスタシステムのストレージノードのコントローラに設定されてもよく、上述したデータ処理方法を実行するよう構成される。全てのユニットの機能の詳細な説明について、方法の実施例における説明が参照されてもよく、詳細はここでは繰り返し説明されない。
【０１２５】
本発明の実施例により提供されるクラスタシステムにおけるデータ処理装置を通じて、受信したデータストリームに対して重複データクエリが実行されると、各第１スケッチ値に対応し、クラスタシステム内にある第１物理ノードが、データストリームを表す第１スケッチ値に従って特定され、その後、データストリームを表す第１スケッチ値は、重複データクエリのため特定された物理ノードに送信される。重複データクエリの手順は、クラスタシステムにおけるノード数の増加により変化せず、各ノードの計算量は、クラスタシステムのノード数の増加により増加しない。
【０１２６】
クエリを介し非重複データを検出すると、クエリ部９５は、非重複データを新たなデータブロックとみなし、当該新たなデータブロックを単一のインスタンスレポジトリに格納してもよい。従って、本発明の実施例は更に以下を含むものであってもよい。
【０１２７】
ライトアドレス取得部９７は、所定のストレージポリシーに従って、新たなデータブロックと当該新たなデータブロックのフィンガープリントとが書き込まれるストレージアドレスを選択するよう構成される。
【０１２８】
書き込み部９８は、所定のストレージ条件が充足すると、新たなデータブロックと当該新たなデータブロックのフィンガープリントとを、選択されたストレージアドレスに対応するストレージ領域に書き込むよう構成される。
【０１２９】
ライトアドレス取得部９７の新たなデータブロックのストレージポリシーは複数あってもよい。例えば、ライトアドレス取得部９７は、
クラスタシステムの各物理ノードのロード情報を取得するよう構成されるロード情報取得サブ部９７１と、
ロード情報に従って、データが移行される物理ノードを選択し、データが移行される選択された物理ノードから、新たなデータブロックと当該新たなデータブロックのフィンガープリントとが書き込まれるストレージアドレスを取得するよう構成されるアドレス選択サブ部９７２と、
を有する。
【０１３０】
アドレス選択サブ部９７２がロード情報に従って新たなデータが書き込まれるストレージアドレスを選択する方法は複数あってもよい。例えば、クラスタシステムの全ての物理ノードの平均ロード値が第１所定閾値を超過したことが、ロード情報取得サブ部９７１により取得されたロード情報に従って特定されると、データが書き込まれるノードが、平均ロード値より小さいロード値の物理ノードから選択され、新たなデータブロックと当該新たなデータブロックのフィンガープリントとが書き込まれるストレージアドレスが、データが書き込まれるノードから取得され、クラスタシステムの全ての物理ノードの平均ロード値が第１所定閾値以下であるとき、新たなデータブロックと当該新たなデータブロックのフィンガープリントとが書き込まれるストレージアドレスが、現在の物理ノードから取得される。
【０１３１】
確かに、ライトアドレス取得部９７の新たなデータブロックのストレージポリシーでは、ロード情報はまた特定されなくてもよく、アドレスは現在の物理ノードから直接選択され、ライトアドレス取得部９７は、具体的には、現在の物理ノードから新たなデータブロックと当該新たなデータブロックのフィンガープリントとが書き込まれるストレージアドレスを取得するよう構成されてもよい。
【０１３２】
書き込み部９８は、例えば、現在の物理ノードのキャッシュに新たなデータブロックを格納し、現在の物理ノードのキャッシュのデータが第２所定閾値に達し、所定のストレージ条件が充足されると、新たなデータブロックと当該新たなデータブロックのフィンガープリントとを選択されたストレージアドレスに対応するストレージ領域に書き込むよう構成されてもよい。
【０１３３】
バーチャルノードがクラスタシステムに含まれるケースについて、少なくとも１つのバーチャルノードが、クラスタシステムの物理ノードの分割を介し論理的に取得され、クラスタシステムにおける全てのバーチャルノードと全ての物理ノードとの間の対応関係（ＶＰＴ）が各物理ノードに含まれ、本発明の実施例では、少なくとも１つのバーチャルノードが、前記クラスタシステムの各物理ノードの分割を介し論理的に取得され、
特定部９２は、具体的には、第２アルゴリズムに従ってｎ個の第１スケッチ値の各第１スケッチ値に対応し、クラスタシステム内にある第１バーチャルノードを特定し、現在の物理ノードのバーチャルノードと物理ノードとの間の対応関係をクエリにすることによって、第１バーチャルノードに対応する第１物理ノードを取得するよう構成され、取得される非重複データブロックは、新たなデータブロックとして利用される。
【０１３４】
更新部９６は、具体的には、第２アルゴリズムに従って各第２スケッチ値に対応する第２バーチャルノードを第２スケッチ値により特定し、バーチャルノードと物理ノードとの間の対応関係に従って第２バーチャルノードが配置される第２物理ノードを特定し、新たなデータブロックのストレージアドレスの取得後、各第２スケッチ値と各第２スケッチ値により表されるデータブロックのストレージアドレスとの間の対応関係を対応する第２物理ノードの第２バーチャルノードに格納するよう構成される。
【０１３５】
第２アルゴリズムに従ってｎ個の第１スケッチ値の各スケッチ値に対応し、クラスタシステム内にある第１バーチャルノードを特定する機能を実現する際、特定部９２は、各第１スケッチ値に対応し、クラスタシステム内にある第１バーチャルノードを取得するため、各第１スケッチ値によるクラスタシステムの全てのバーチャルノードの個数に対するモジュロ演算を実行してもよい。
【０１３６】
バーチャルノードがクラスタシステムに含まれるケースについて、クラスタシステムの物理ノードのデータ移行手段が実行されると、書き込み部９８は更に、データ移行状態を充足すると、移行が必要なデータを有する物理ノードの少なくとも１つのバーチャルノードをターゲット物理ノードに一体的に移行するよう構成され、更新部９８は更に、現在の物理ノードの移行されるバーチャルノードと物理ノードとの間の対応関係を更新し、クラスタシステムの他の物理ノードに移行されるノードと物理ノードとの間の対応関係を更新したことを通知するよう構成される。
【０１３７】
データ移行条件は、ユーザにより予め設定されるか、クラスタシステムの物理ノードのキャパシティ拡張中に新たに追加された物理ノードにデータが移行される必要があることであってもよく、また、ロードバランシングのため、ロードが高い物理ノードのデータがロードが低い物理ノードに移行される。当該データ移行条件は、本発明の実施例では限定されない。
【０１３８】
クラスタシステムのデータ処理装置は、新たな物理ノードに移行されるバーチャルノードのシリアル番号が変更されない間、物理ノードにおけるバーチャルノードの一体的な移行を実現してもよい。インデックステーブルのスケッチ値に対応するデータストレージアドレスはバーチャルノードにおけるデータが格納される位置を表し、バーチャルノードの識別子が変更されない限り、データストレージアドレスは変更される必要はなく、関連するバーチャルノードと物理ノードとの間の対応関係が変更され、これは、ノード拡張中の処理手続を簡単化し、計算量を大きく低減する。
【０１３９】
図１０を参照して、本発明の実施例は更に、クラスタシステムにおけるデータ処理装置１００を提供する。当該装置は、クラスタシステムのストレージノードに設定されてもよく、プロセッサ１０１、メモリ１０２、ネットワークコントローラ１０３及び磁気ディスクコントローラ１０４を有し、プロセッサ１０１、プライマリメモリ１０２、ネットワークコントローラ１０３及び磁気ディスクコントローラ１０４は、バス１０５を介し接続される。
【０１４０】
ストレージコントローラ１０２は、プログラム１０２１を格納するよう構成される。
【０１４１】
プロセッサ１０１は、プライマリメモリ１０２のプログラム１０２１を実行するよう構成される。
【０１４２】
プロセッサ１０１は、ネットワークコントローラ１０３を介しクラスタシステムの他のノードと通信し、例えば、図１０の磁気ディスクなど、ローカルノードにおいて長時間データを格納可能なストレージ装置と磁気ディスクコントローラ１０４を介し通信する。磁気ディスクコントローラ１０４により制御されるストレージ装置は、磁気ディスクに限定されず、他の記憶媒体により形成される装置であってもよい。
【０１４３】
具体的な実現形態では、メモリ１０２は、メモリなどのプライマリメモリであってもよく、具体的な実現形態は本発明の実施例では限定されない。
【０１４４】
具体的には、プログラム１０２１は、コンピュータ処理指示を含むプログラムコードを有してもよい。
【０１４５】
プロセッサ１０２は、中央処理ユニットＣＰＵ又は特定用途向け集積回路ＡＳＩＣであってもよく、あるいは、本発明の実施例を実現するための１以上の集積回路として構成されてもよい。
【０１４６】
図９を参照して、プログラム１０２１は以下を含むものであってもよい。
【０１４７】
分割部９０は、現在の物理ノードにより受信されたデータストリームをｍ個のデータブロックに分割し、各データブロックのフィンガープリントを取得するよう構成され、ｍは１以上の整数である。
【０１４８】
スケッチ値取得部９１は、第１アルゴリズムに従ってデータストリームを表すｎ個の第１スケッチ値を取得するよう構成され、ｎは１以上であって、ｍ以下の整数である。
【０１４９】
第１スケッチ値を取得するための第１アルゴリズムについて、上述した方法の説明が参照されてもよく、詳細はここでは繰り返し説明されない。
【０１５０】
特定部９２は、第２アルゴリズムに従ってｎ個の第１スケッチ値の各第１スケッチ値に対応し、クラスタシステム内にある第１物理ノードを特定するよう構成される。
【０１５１】
特定部９２が第１物理ノードを特定する方法は多数あるかもしれない。例えば、ルート抽出及び丸め処理が、当該値がｍ未満になるまで、第１スケッチ値に対して実行され、対応する第１物理ノードを取得するため、最終結果が丸められる。各第１スケッチ値に対応し、クラスタシステム内にある第１物理ノードを取得するため、各第１スケッチ値によるモジュロ演算がまた、クラスタシステムの全ての物理ノードの個数に対して実行されてもよい。
【０１５２】
本発明の実施例では、特定部９２は、各第１スケッチ値に対応し、クラスタシステム内にある第１物理ノードを取得するため、クラスタシステムの全ての物理ノードの個数に対して各第１スケッチ値によるモジュロ演算を実行するよう構成される。
【０１５３】
送信部９３は、各第１スケッチ値をクエリのため対応する第１物理ノードに送信するよう構成される。
【０１５４】
送信部９３により送信されたクエリリクエストの受信後、クラスタシステムの他のノードは、ローカルに格納されるインデックステーブルに従って、第１スケッチ値に対応するストレージアドレスがあるかクエリする。本発明の実施例では、クラスタシステムの各物理ノード又は大部分の物理ノードは、インデックステーブルを格納し、スケッチ値と当該スケッチ値により表される格納されているデータブロックのストレージアドレスとの間の対応関係が、インデックステーブルに格納される。当該インデックステーブルは、所定のポリシーに従ってクラスタシステムの物理ノードに格納され、データブロックと当該データブロックに対応するフィンガープリント情報とが、異なるストレージアドレスによって指示されるストレージ領域に格納される。
【０１５５】
受信部９４は、ｎ個の第１スケッチ値に対応する第１物理ノードから少なくとも１つのレスポンスメッセージを受信し、レスポンスメッセージから第１ストレージアドレスを取得する。
【０１５６】
受信部９４は、レスポンスメッセージから第１スケッチ値に対応するストレージアドレスを取得し、レスポンスメッセージに搬送される各ストレージアドレスのヒット数に関する統計量を収集するよう構成される統計量収集サブ部９４１と、統計量収集サブ部９４１の統計結果に従って、第１ストレージアドレスとして最大ヒット数を有するｓ個のストレージアドレスを選択するよう構成されるアドレス取得サブ部９４２とを有してもよい。ここで、ｓは１以上である。
【０１５７】
クエリ部９５は、第１ストレージアドレスにより指示されるストレージ領域に格納されるデータブロックのフィンガープリントと、受信したデータストリームの分割を介し取得された各データブロックのフィンガープリントとを比較し、重複データブロックをクエリするよう構成される。取得された非重複データブロックは、新たなデータブロックとして利用される。
【０１５８】
更新部９６は、新たなデータブロックを表す少なくとも１つの第２スケッチ値を取得し、第２アルゴリズムに従って各第２スケッチ値に対応する第２物理ノードを第２スケッチ値により特定し、各第２スケッチ値と各第２スケッチ値により表されるデータブロックのストレージアドレスとの間の対応関係を対応する第２物理ノードに格納するよう構成される。
【０１５９】
更新部９６により新たなデータブロックを表す第２スケッチ値を取得するためのアルゴリズムは、ここでは限定されないが、第１スケッチ値を取得するための第１アルゴリズムと同じであってもよい。
【０１６０】
各第２スケッチ値と各第２スケッチ値により表されるデータブロックのストレージアドレスとの間の対応関係が、インデックステーブルの１つのインデックスエントリとして利用される。本発明の実施例では、更新部９６は、所定のポリシーに従ってインデックステーブルを物理ノードに格納し、特定の物理ノードのインデックステーブルのデータと当該物理ノードのデータとの間には直接的な関係はなく、インデックステーブルのみが、設定された割当ポリシーに従って特定の物理ノードに格納される。インデックステーブルの説明については、上述した方法の説明が参照されてもよく、詳細はここでは繰り返し説明されない。
【０１６１】
上述した方法の説明を参照して、特定の実現形態では、スケッチ値取得部９１が第１アルゴリズムに従ってデータストリームを表すｎ個のスケッチ値を取得する方法が複数あってもよい。例えば、スケッチ値取得部９１は、フィンガープリントグループ化サブ部９１１と取得サブ部９１２とを有してもよく、フィンガープリントグループ化サブ部９１１は、データストリームのｍ個のデータブロックのフィンガープリントをｎ個の第１フィンガープリントグループにグループ化するよう構成され、各第１フィンガープリントグループは、少なくとも２つのデータブロックのフィンガープリントを有する。
【０１６２】
取得サブ部９１２は、ｎ個の第１スケッチ値を取得するため、各フィンガープリントグループを表す第１スケッチ値を取得するよう構成される。
【０１６３】
取得サブ部９１２は、最小のフィンガープリントが属するフィンガープリントグループを表す第１スケッチ値として、各フィンガープリントグループから最小のフィンガープリントを選択するよう構成されてもよい。
【０１６４】
クラスタシステムのデータ処理装置の受信部９４は更に、例えば、第１物理ノードによりフィードバックされるストレージアドレスが、各第１スケッチ値がクエリのため対応する第１物理ノードに送信された後に受信されない場合、非重複データブロックとしてデータストリームの分割を介し取得されるデータブロックを利用し、その後、更新部９６をトリガするよう構成されてもよい。
【０１６５】
本発明の実施例により提供される装置は、クラスタシステムのストレージノードのコントローラにおいて設定されてもよく、上述したデータ処理方法を実行するよう構成される。全てのユニットの機能の詳細な説明について、方法の実施例の説明が参照されてもよく、詳細はここでは繰り返し説明されない。
【０１６６】
本発明の実施例により提供されるクラスタシステムのデータ処理装置を介して、受信したデータストリームに対して重複データクエリが実行されると、サンプリングされたスケッチ値が、重複データクエリのため特定された物理ノードに送信され、重複データクエリの手順は、クラスタシステムのノード数の増加により変化しない。従って、各ノードの計算量は、クラスタシステムのノード数の増加により増加しない。
【０１６７】
クエリを介し非重複データを検出すると、クエリ部９５は、非重複データを新たなデータブロックとみなし、当該新たなデータブロックをシングルインスタンスレポジトリに格納する。このため、本発明の実施例は更に以下を含む。
【０１６８】
ライトアドレス取得部９７は、所定のストレージポリシーに従って、新たなデータブロックと当該新たなデータブロックのフィンガープリントとが書き込まれるストレージアドレスを選択するよう構成される。
【０１６９】
書き込み部９８は、所定のストレージ条件が充足すると、新たなデータブロックと当該新たなデータブロックのフィンガープリントとを、選択されたストレージアドレスに対応するストレージ領域に書き込むよう構成される。
【０１７０】
ライトアドレス取得部９７の新たなデータブロックの複数のストレージポリシーがあってもよい。例えば、ライトアドレス取得部９７は、
クラスタシステムの各物理ノードのロード情報を取得するよう構成されるロード情報取得サブ部９７１と、
ロード情報に従って、データが移行される物理ノードを選択し、データが移行される物理ノードから、新たなデータブロックと当該新たなデータブロックのフィンガープリントとが書き込まれるストレージアドレスを取得するよう構成されるアドレス選択サブ部９７２と、
を有する。
【０１７１】
アドレス選択サブ部９７２がロード情報に従って新たなデータが書き込まれるストレージアドレスを選択する方法は複数あってもよい。例えば、ロード情報取得サブ部９７１により取得されるロード情報に従って、クラスタシステムの全ての物理ノードの平均ロード値が第１所定閾値を超過したことが特定されると、データが書き込まれるノードは、平均ロード値より小さいロード値の物理ノードから選択され、新たなデータブロックと当該新たなデータブロックのフィンガープリントとが書き込まれるストレージアドレスが、データが書き込まれるノードから取得され、クラスタシステムの全ての物理ノードの平均ロード値が第１所定閾値以下であるとき、新たなデータブロックと当該新たなデータブロックのフィンガープリントとが書き込まれるストレージアドレスが、現在の物理ノードから取得される。
【０１７２】
確かに、ライトアドレス取得部９７の新たなデータブロックのストレージポリシーでは、ロード情報はまた特定されなくてもよく、アドレスは現在の物理ノードから直接選択される。従って、ライトアドレス取得部９７は、現在の物理ノードから、新たなデータブロックと当該新たなデータブロックのフィンガープリントとが書き込まれるストレージアドレスを取得するよう構成されてもよい。
【０１７３】
書き込み部９８は、例えば、現在の物理ノードのキャッシュに新たなデータブロックを格納し、現在の物理ノードのキャッシュが第２所定閾値に達し、所定のストレージ条件を充足すると、新たなデータブロックと当該新たなデータブロックのフィンガープリントとを選択されたストレージアドレスに対応するストレージ領域に書き込むよう構成されてもよい。
【０１７４】
バーチャルノードがクラスタシステムに含まれるケースについて、少なくとも１つのバーチャルノードがクラスタシステムの物理ノードの分割を介し論理的に取得され、クラスタシステムの全てのバーチャルノードと物理ノードとの間の対応関係（ＶＰＴ）が各物理ノードに含まれ、本発明の実施例では、少なくとも１つのバーチャルノードが各物理ノードの分割を介し論理的に取得される。
【０１７５】
特定部９２は、第２アルゴリズムに従ってｎ個の第１スケッチ値の各第１スケッチ値に対応し、クラスタシステム内にある第１バーチャルノードを特定し、バーチャルノードと物理ノードとの間の対応関係をクエリにすることによって、第１バーチャルノードに対応する第１物理ノードを取得するよう構成され、取得される非重複データブロックは、新たなデータブロックとして利用され、
更新部９６は、新たなデータブロックを表す少なくとも１つの第２スケッチ値を取得し、第２アルゴリズムに従って各第２スケッチ値に対応する第２バーチャルノードを第２スケッチ値により特定し、バーチャルノードと物理ノードとの間の対応関係に従って第２バーチャルノードが配置される第２物理ノードを特定し、新たなデータブロックのストレージアドレスの取得後、各第２スケッチ値と各第２スケッチ値により表されるデータブロックのストレージアドレスとの間の対応関係を対応する第２物理ノードの第２バーチャルノードに格納するよう構成される。
【０１７６】
第２アルゴリズムに従ってｎ個の第１スケッチ値の各スケッチ値に対応し、クラスタシステム内にある第１バーチャルノードを特定する機能を実現するとき、特定部９２は、各第１スケッチ値に対応し、クラスタシステム内にある第１バーチャルノードを取得するため、各第１スケッチ値によるモジュロ演算をクラスタシステムの全てのバーチャルノードの個数に対して実行してもよい。
【０１７７】
バーチャルノードがクラスタシステムに含まれるケースについて、クラスタシステムの物理ノードのデータ移行手段が実行されるとき、書き込み部９８は更に、データ移行状態を充足すると、移行が必要なデータを有する物理ノードの少なくとも１つのバーチャルノードをターゲット物理ノードに一体的に移行するよう構成され、更新部９６は更に、現在の物理ノードの移行されるバーチャルノードと物理ノードとの間の対応関係を更新し、クラスタシステムの他の物理ノードに移行されるノードと物理ノードとの間の対応関係を更新したことを通知するよう構成される。
【０１７８】
データ移行条件は、ユーザにより予め設定されてもよく、クラスタシステムの物理ノードのキャパシティ拡張中にデータが新たに追加された物理ノードに移行される必要があるというものであってもよく、また、ロードバランシングのため、ロードが高い物理ノードのデータがロードが低い物理ノードに移行されるというものであってもよい。データ移行条件は本発明の実施例では限定されない。
【０１７９】
クラスタシステムのデータ処理装置は、新たな物理ノードに移行されるバーチャルノードのシリアル番号が変わらない間、物理ノードのバーチャルノードの一体的な移行を実現してもよく、インデックステーブルのスケッチ値に対応するデータストレージアドレスは、データがバーチャルノードに格納される位置を表す。従って、バーチャルノードの識別子が変更しない限り、データストレージアドレスは変更される必要はなく、関係するバーチャルノードと物理ノードとの間の対応関係のみが変更され、これは、ノード拡張中の処理手順を簡単化し、計算量を大きく低減する。
【０１８０】
本発明の実施例は更に、データ処理のためのコンピュータプログラムを提供し、当該コンピュータプログラムは、プログラムコードを格納するコンピュータ可読記憶媒体を有し、プログラムコードに含まれる命令は、
現在の物理ノードにより受信されたデータストリームをｍ個のデータブロックに分割し、各データブロックのフィンガープリントを取得し、第１アルゴリズムに従って前記データストリームを表すｎ個の第１スケッチ値を取得するステップであって、ｍは１以上の整数であり、ｎは１以上であって、ｍ以下の整数である、取得するステップと、
第２アルゴリズムに従って前記ｎ個の第１スケッチ値の各第１スケッチ値に対応し、前記クラスタシステム内にある第１物理ノードを特定し、各第１スケッチ値をクエリのため前記対応する第１物理ノードに送信するステップと、
前記ｎ個の第１スケッチ値に対応する第１物理ノードから少なくとも１つのレスポンスメッセージを受信し、前記レスポンスメッセージから第１ストレージアドレスを取得するステップと、
前記第１ストレージアドレスにより指示されるストレージ領域に格納されるデータブロックのフィンガープリントと、前記データストリームの分割を介し取得された各データブロックのフィンガープリントとを比較し、重複データブロックをクエリするステップとであって、取得された非重複データブロックが新たなデータブロックとして利用される、クエリするステップと、
前記新たなデータブロックを表す少なくとも１つの第２スケッチ値を取得し、前記第２アルゴリズムに従って各第２スケッチ値に対応する第２物理ノードを前記第２スケッチ値により特定し、各第２スケッチ値と各第２スケッチ値により表されるデータブロックのストレージアドレスとの間の対応関係を前記対応する第２物理ノードに格納するステップと、
を実行するのに利用される。
【０１８１】
本発明の実施例により提供されるデータ処理のためのコンピュータプログラムは、プログラムコードを格納するコンピュータ可読記憶媒体を有し、プログラムコードに含まれる命令は、上述した方法の実施例の方法を実行するのに利用されてもよく、具体的な実現形態について、方法の実施例が参照されてもよく、詳細はここでは繰り返し説明されない。
【０１８２】
便宜上及び説明の簡単化のため、上述したシステム、装置及びユニットの具体的な作業処理について、方法の実施例の対応する処理が参照されてもよく、詳細はここでは繰り返し説明されない。
【０１８３】
本出願に提供される複数の実施例では、開示されたシステム、装置及び方法は他の方法により実現されてもよいことが理解されるべきである。例えば、ユニットの分割は単に一種の論理機能の分割であり、実際の実現形態では他の分割方法があってもよい。例えば、複数のユニット又はコンポーネントが他のシステムに合成又は統合されてもよいし、あるいは、一部の特徴は無視又は実行されなくてもよい。更に、図示又は説明された相互の結合、直接的な結合又は通信接続は、いくつかの通信インタフェースを介し実現されてもよい。装置又はユニットの間の間接的な結合又は通信接続は、電子的、機械的又は他の形態により実現されてもよい。
【０１８４】
別個のパーツとして説明されるユニットは、物理的に分離されていてもよいし又はそうでなくてもよく、ユニットとして示されるパーツは物理的ユニットであってもよいし、そうでなくてもよく、１つのポジションに配置されてもよいし、あるいは、複数のネットワークユニットに分散されてもよい。ユニットの一部又は全ては、実施例の手段の課題を達成するための実際のニーズに従って選択されてもよい。
【０１８５】
更に、本発明の実施例の機能部は１つの処理部に一体化されてもよく、各部はまた物理的に単独で存在してもよく、２つ以上のユニットがまた１つのユニットに統合される。
【０１８６】
機能がソフトウェア機能部の形態で実現され、独立した製品として販売又は利用されるとき、これらの機能はコンピュータ可読記憶媒体に格納されてもよい。このような理解に基づき、実質的に又は部分的に従来技術に貢献する本発明の技術的手段又は当該技術的手段の一部は、ソフトウェアプロダクトの形態により実現されてもよい。コンピュータソフトウェアプロダクトは、記憶媒体に格納され、本発明の実施例に説明される方法のステップの全て又は一部を実行するようコンピュータ装置（パーソナルコンピュータ、サーバ、ネットワーク装置などであってもよい）に指示するための複数の命令を含む。上述した記憶媒体は、ＵＳＢフラッシュディスク、着脱可能なハードディスク、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、磁気ディスク又は光ディスクなど、プログラムコードを格納可能な何れかの媒体を含む。
【０１８７】
上記説明は、本発明の単なる特定の実施例であり、本発明の保護範囲を限定することを意図していない。本発明に開示される技術的範囲内において当業者により容易に理解される何れかの変形又は置換は、本発明の保護範囲内に属する。従って、本発明の保護範囲は、請求項の保護範囲に従う。
【図１】
0005824167.tif 000002
【図２】
0005824167.tif 000003
【図３】
0005824167.tif 000004
【図４】
0005824167.tif 000005
【図５】
0005824167.tif 000006
【図６】
0005824167.tif 000007
【図７】
0005824167.tif 000008
【図８】
0005824167.tif 000009
【図９】
0005824167.tif 000010
【図１０】
0005824167.tif 000011