(57)【要約】【課題】クラスタを構成するノードの離脱または追加があった場合に、ノードの処理負荷を抑えながらデータを移行させることができる、データ移行処理システムおよびデータ移行処理方法を提供する。【解決手段】クラスタを構成するデータ移行処理システム１００の各ノード１は、メッセージ処理の対象となるデータを、原本データを記憶する所有者ノードと、当該データの複製を記憶する１つ以上のバディ（複製ノード）とに記憶する。各ノード１は、そのデータに所有者ノードの識別子およびバディの識別子を含むノード情報を付して記憶する。そして、クラスタを構成するノード１に離脱や追加が発生すると、既存の各ノード１は、そのデータについての離脱や追加の発生後の所有者ノードとバディとを特定し、そのデータに付したノード情報と比較して、一致しないデータを移行処理が必要なデータとして抽出し、所定のタイミングで移行処理を実行する。【選択図】図２
2014041550.tif 000002
【特許請求の範囲】
【請求項１】
クラスタを構成する複数のノードのいずれかが、クライアントにサービスを提供するためのデータを原本データとして記憶する所有者ノード、または、前記データの複製データを記憶する１つ以上の複製ノードとして割り当てられて記憶するデータ移行処理システムであって、
前記データ移行処理システムを構成する前記複数のノードそれぞれは、
前記ノードに固有な識別子であるノード識別子を、前記クラスタを構成する複数のノードについて、前記データと前記所有者ノードおよび前記複製ノードとが対応付けられたノード識別子管理情報が記憶される記憶部と、
前記原本データを記憶する前記所有者ノードのノード識別子および前記複製データを記憶する前記複製ノードのノード識別子を、前記原本データおよび前記複製データそれぞれに、ノード情報として付与するノード情報付与部と、
前記ノードの離脱または追加を検知して、前記ノード識別子管理情報を、前記ノードの離脱または追加に応じた、前記データと前記所有者ノードおよび前記複製ノードとの新たな対応付けに変更して格納させるノード識別子管理部と、
変更された前記ノード識別子管理情報に基づいて、自身が記憶している前記原本データ、および、前記原本データが消失した自身が記憶している複製データを、前記所有者ノードまたは前記複製ノードを変更するために行うデータ移行が必要か否かの判定対象となるデータを示す判定対象データとして抽出するデータ抽出部と、
前記データ移行による前記ノード自身の処理負荷を抑制するように設定されたパラメータに基づく所定のタイミングのときに、前記抽出した判定対象データについて、前記変更されたノード識別子管理情報に対応した所有者ノードおよび複製ノードを特定し、前記特定した所有者ノードおよび複製ノードそれぞれのノード識別子が、前記ノード情報と比較して一致しない場合に、当該抽出した判定対象データを、前記データ移行が必要なデータを示すデータ移行対象データとして検出し、前記検出したデータ移行対象データを、前記特定した所有者ノードおよび複製ノードに移行するデータ移行処理部と、
を備えることを特徴とするデータ移行処理システム。
【請求項２】
前記パラメータは、
前記データ移行を並列で実行できる最大スレッド数を示すデータ移行処理スレッド数、前記データ移行を実行した後の待機時間を示すデータ移行処理実行間隔、前記データ移行対象データの検出処理を連続で実行する個数を示すシミュレーション最大個数、の少なくとも１つであること
を特徴とする請求項１に記載のデータ移行処理システム。
【請求項３】
前記複数のノードそれぞれは、
前記ノード自身の処理負荷を監視し、前記処理負荷が所定値を超えた場合に、前記データ移行処理部に処理中断情報を出力するノード負荷監視部を、さらに備え、
前記データ移行処理部は、前記処理中断情報を受け取ると、前記データ移行を中断すること
を特徴とする請求項１または請求項２に記載のデータ移行処理システム。
【請求項４】
クラスタを構成する複数のノードのいずれかが、クライアントにサービスを提供するためのデータを原本データとして記憶する所有者ノード、または、前記データの複製データを記憶する１つ以上の複製ノードとして割り当てられて記憶するデータ移行処理システムであって、
前記データ移行処理システムを構成する前記複数のノードそれぞれは、
前記ノードに固有な識別子であるノード識別子を、前記クラスタを構成する複数のノードについて、前記データと前記所有者ノードおよび前記複製ノードとが対応付けられたノード識別子管理情報が記憶される記憶部と、
前記原本データを記憶する前記所有者ノードのノード識別子および前記複製データを記憶する前記複製ノードのノード識別子を、前記原本データおよび前記複製データそれぞれに、ノード情報として付与するノード情報付与部と、
前記ノードの離脱または追加を検知して、前記ノード識別子管理情報を、前記ノードの離脱または追加に応じた、前記データと前記所有者ノードおよび前記複製ノードとの新たな対応付けに変更して格納させるノード識別子管理部と、
変更された前記ノード識別子管理情報に基づいて、自身が記憶している前記原本データ、および、前記原本データが消失した自身が記憶している複製データを、前記所有者ノードまたは前記複製ノードを変更するために行うデータ移行が必要か否かの判定対象となるデータを示す判定対象データとして抽出するデータ抽出部と、
前記抽出した判定対象データについて、前記変更されたノード識別子管理情報に対応した所有者ノードおよび複製ノードを特定し、前記特定した所有者ノードおよび複製ノードそれぞれのノード識別子が、前記ノード情報と比較して一致しない場合に、当該抽出した判定対象データを、前記データ移行が必要なデータを示すデータ移行対象データとして検出し、前記検出したデータ移行対象データを、前記特定した所有者ノードおよび複製ノードに移行するデータ移行処理部と、
前記ノード自身の処理負荷を監視し、前記処理負荷が所定値を超えた場合に、前記データ移行処理部に処理中断情報を出力するノード負荷監視部と、を備え、
前記データ移行処理部は、前記処理中断情報を受け取ると、前記データ移行を中断すること
を特徴とするデータ移行処理システム。
【請求項５】
前記複数のノードそれぞれは、
前記クライアントから前記データによる前記サービスの提供を要求するメッセージを受信した場合に、前記メッセージの処理を実行すると共に、前記サービスの対象となるデータが前記データ移行対象データである場合に、前記サービスの対象となるデータを、前記変更されたノード識別子管理情報に対応した所有者ノードおよび複製ノードに移行するメッセージ処理部を、さらに備えること
を特徴とする請求項１ないし請求項４のいずれか１項に記載のデータ移行処理システム。
【請求項６】
クラスタを構成する複数のノードのいずれかが、クライアントにサービスを提供するためのデータを原本データとして記憶する所有者ノード、または、前記データの複製データを記憶する１つ以上の複製ノードとして割り当てられて記憶するデータ移行処理システムのデータ移行処理方法であって、
前記データ移行処理システムを構成する前記複数のノードそれぞれは、
前記ノードに固有な識別子であるノード識別子を、前記クラスタを構成する複数のノードについて、前記データと前記所有者ノードおよび前記複製ノードとが対応付けられたノード識別子管理情報が記憶される記憶部を備えており、
前記原本データを記憶する前記所有者ノードのノード識別子および前記複製データを記憶する前記複製ノードのノード識別子を、前記原本データおよび前記複製データそれぞれに、ノード情報として付与するステップと、
前記ノードの離脱または追加を検知して、前記ノード識別子管理情報を、前記ノードの離脱または追加に応じた、前記データと前記所有者ノードおよび前記複製ノードとの新たな対応付けに変更して格納させるステップと、
変更された前記ノード識別子管理情報に基づいて、自身が記憶している前記原本データ、および、前記原本データが消失した自身が記憶している複製データを、前記所有者ノードまたは前記複製ノードを変更するために行うデータ移行が必要か否かの判定対象となるデータを示す判定対象データとして抽出するステップと、
前記データ移行による前記ノード自身の処理負荷を抑制するように設定されたパラメータに基づく所定のタイミングのときに、前記抽出した判定対象データについて、前記変更されたノード識別子管理情報に対応した所有者ノードおよび複製ノードを特定し、前記特定した所有者ノードおよび複製ノードそれぞれのノード識別子が、前記ノード情報と比較して一致しない場合に、当該抽出した判定対象データを、前記データ移行が必要なデータを示すデータ移行対象データとして検出し、前記検出したデータ移行対象データを、前記特定した所有者ノードおよび複製ノードに移行するステップと、
を実行することを特徴とするデータ移行処理方法。
【請求項７】
クラスタを構成する複数のノードのいずれかが、クライアントにサービスを提供するためのデータを原本データとして記憶する所有者ノード、または、前記データの複製データを記憶する１つ以上の複製ノードとして割り当てられて記憶するデータ移行処理システムのデータ移行処理方法であって、
前記データ移行処理システムを構成する前記複数のノードそれぞれは、
前記ノードに固有な識別子であるノード識別子を、前記クラスタを構成する複数のノードについて、前記データと前記所有者ノードおよび前記複製ノードとが対応付けられたノード識別子管理情報が記憶される記憶部を備えており、
前記原本データを記憶する前記所有者ノードのノード識別子および前記複製データを記憶する前記複製ノードのノード識別子を、前記原本データおよび前記複製データそれぞれに、ノード情報として付与するステップと、
前記ノードの離脱または追加を検知して、前記ノード識別子管理情報を、前記ノードの離脱または追加に応じた、前記データと前記所有者ノードおよび前記複製ノードとの新たな対応付けに変更して格納させるステップと、
変更された前記ノード識別子管理情報に基づいて、自身が記憶している前記原本データ、および、前記原本データが消失した自身が記憶している複製データを、前記所有者ノードまたは前記複製ノードを変更するために行うデータ移行が必要か否かの判定対象となるデータを示す判定対象データとして抽出するステップと、
前記抽出した判定対象データについて、前記変更されたノード識別子管理情報に対応した所有者ノードおよび複製ノードを特定し、前記特定した所有者ノードおよび複製ノードそれぞれのノード識別子が、前記ノード情報と比較して一致しない場合に、当該抽出した判定対象データを、前記データ移行が必要なデータを示すデータ移行対象データとして検出し、前記検出したデータ移行対象データを、前記特定した所有者ノードおよび複製ノードに移行するステップと、
前記ノード自身の処理負荷を監視し、前記処理負荷が所定値を超えた場合に、前記データ移行を中断させるステップと、を実行すること
を特徴とするデータ移行処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク上に分散配置されるサーバをクラスタ化してデータを格納する分散処理システムにおいて、分散処理システムを構成するサーバに障害等が発生しクラスタから離脱した際、または、分散処理システムを構成するサーバを追加した際に、データの移行処理（再冗長化処理または再配置処理）を行うデータ移行処理システムおよびデータ移行処理方法に関する。
【背景技術】
【０００２】
近年、クラウドコンピューティングの隆盛に伴い、多量のデータの処理や保持を効率的に行うことが求められている。そこで、複数のサーバを協調動作させることにより効率的な処理を実現する分散処理技術が発展している。
【０００３】
分散処理を行う際には、処理対象のデータを、クラスタを構成する各サーバ（以下、「クラスタメンバ」または「ノード」と称する。）に振り分ける必要がある。このとき、クラスタ全体での処理能力を高めるためには、各ノードが担当するデータ数（データ量）は平均化されていることが望ましい。
【０００４】
代表的なデータの管理（振り分け）手法として、各データのｋｅｙをハッシュ関数にかけた値（以下、「ｈａｓｈ（ｋｅｙ）」と称する。）をノード数Ｎで割った余り、すなわち「ｈａｓｈ（ｋｅｙ） ｍｏｄ Ｎ」を番号として持つノードにデータを振り分ける方法がある。この場合、各ノードに事前に「０」から「Ｎ−１」までの番号を割り当てていることが前提となる。このような管理（振り分け）方法を用いた場合、ノードを追加すると、Ｎの値が変化して、多くのデータについて、そのデータの保存を担当するノードが変更になるため、担当するデータを再配置することが必要になる。
【０００５】
そこで、クラスタメンバの追加に伴い担当するノードが変更になるデータ数を約１／Ｎに抑える方法として、コンシステントハッシュ（Consistent Hashing）法（非特許文献１参照）を用いた管理（振り分け）手法がある。このコンシステントハッシュ法は、Amazon Dynamo（非特許文献２参照）等で用いられる。
【０００６】
このコンシステントハッシュ法を用いたデータ管理（振り分け）手法では、ノードとデータの双方にＩＤ（IDentifier）を割り当てる。そして、データのＩＤから閉じたＩＤ空間を時計回りに辿った場合に最初に出合ったノードをそのデータの担当とする。ノードに対するＩＤの与え方の例としては、ＩＰアドレスをハッシュ関数にかけた値（hash（ＩＰアドレス））が挙げられる。
【０００７】
クラスタ構成の分散処理システムでは、各ノードの処理性能が等しい場合には、各ノードが担当するデータ量を等しくする、すなわち、コンシステントハッシュ法のＩＤ空間における、ノード間の距離（以下、「ノードの担当領域」と称する。）を等しくすることが望ましい。この点を解決するため、各ノードに仮想的に複数のＩＤを持たせる手法が用いられている（非特許文献１参照）。各ノードが複数のＩＤを持つことで、仮想ＩＤ毎の担当領域は異なっていても、大数の法則に従いノードの担当領域は平均化される。
【０００８】
多数のデータ管理をクラスタ構成の分散処理システムで実行する場合、あるノードに障害が発生した場合でも他のノードで処理が継続できるように、データの複製を保持することでデータの冗長化を実現している。コンシステントハッシュ法によるデータ管理手法を用いた分散処理システムにおいても、データの冗長化が必要であり、図１０に示すような複製データの配置手法をとるものがある。
【０００９】
図１０に示すように、コンシステントハッシュ法では、ノード（ノード「１」〜「４」）とデータ（データＡ〜Ｄ。黒丸（●）で表示）の双方にＩＤを割り当て、データのＩＤからＩＤ空間を時計回りに辿り最初に出合ったノードをそのデータの担当として決定する。そして、担当するノードのさらに右隣（時計回りに次）のノードに複製データを担当させる。
【００１０】
例えば、図１０において、データＡについては、ＩＤ空間上を時計回りに辿り最初に出合ったノード「１」が担当となり、その複製データについては、ＩＤ空間上でノード「１」の右隣にあたるノード「２」に担当させることとなる。このように原本データ・複製データを担当するノードを決定することで、ノードが離脱した場合でも複製データを所持しているノードが新しくデータを担当するノードとなることにより処理を継続できるという利点がある。なお、複製データを複数個とる場合には、複製データを担当するノードのさらに右隣のノードに複製データを担当させるようにする。
【先行技術文献】
【非特許文献】
【００１１】
【非特許文献１】David karger et al.,“Consistent Hashing and Random Trees:Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web”，［online］，1997，ACM，［平成24年8月8日検索］，インターネット<ＵＲＬ:http://www.akamai.com/dl/technical_publications/ConsistenHashingandRandomTreesDistributedCachingprotocolsforrelievingHotSpotsontheworldwideweb.pdf>
【非特許文献２】Giuseppe DeCandia，et al.，“Dynamo: Amazon’s Highly Available Key-value Store,” SOSP’07, October 14-17, 2007, Stevenson, Washington, USA，［online］、［平成24年8月8日検索］、インターネット<ＵＲＬ:http://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf>
【発明の概要】
【発明が解決しようとする課題】
【００１２】
コンシステントハッシュ法によるデータ管理手法を用い、図１０に示すような複製データの配置手法をとる分散処理システムにおいて、ノードに障害等が発生し、そのノードがクラスタを離脱するケースを考える。このとき、離脱したノードが保持していたデータは失われるため、一部のデータに関して冗長度が減少することとなる。図１１に示す例では、ノード「２」がクラスタから離脱したため、ノード「２」が保持していたデータＡとデータＢについて冗長度が減少する。
【００１３】
冗長度が減少した状態で、さらにノードの離脱が重なって起こると、クラスタからデータＡやデータＢが完全に失われる可能性があるため、データの冗長度の回復は早急に行われることが望ましい。一方で、各ノードは実際には多数のデータを保持しているため、ノードが離脱した直後にすべてのデータを再冗長化すると負荷が高くなり、クラスタが実行している通常の処理に影響を及ぼす可能性がある。
【００１４】
また、コンシステントハッシュ法によるデータ管理手法を用い、図１０に示すような複製データの配置手法をとる分散処理システムにおいて、クラスタの性能不足等により、ノードをクラスタに追加する場合を考える。追加されたノードは、コンシステントハッシュ法のＩＤ空間情報に従い、既存ノードが担当していたデータの一部を引き継ぐことになる。このとき、データの引き継ぎが完了するまでは、ノードを新たに追加したにも関わらず、各ノードにおいて保持しているデータ量が不均一な状態になる。これに対し、各ノードは多数のデータを保持しているため、ノードを追加した直後にすべてのデータを再配置すると負荷が高くなり、クラスタが実行している通常の処理に影響を及ぼす可能性がある。
【００１５】
このような背景に鑑みて本発明がなされたのであり、本発明は、クラスタを構成するノードの離脱または追加があった場合に、ノードの処理負荷を抑えながらデータを移行させることができる、データ移行処理システムおよびデータ移行処理方法を提供することを課題とする。
【課題を解決するための手段】
【００１６】
前記した課題を解決するため、請求項１に記載の発明は、クラスタを構成する複数のノードのいずれかが、クライアントにサービスを提供するためのデータを原本データとして記憶する所有者ノード、または、前記データの複製データを記憶する１つ以上の複製ノードとして割り当てられて記憶するデータ移行処理システムであって、前記データ移行処理システムを構成する前記複数のノードそれぞれが、前記ノードに固有な識別子であるノード識別子を、前記クラスタを構成する複数のノードについて、前記データと前記所有者ノードおよび前記複製ノードとが対応付けられたノード識別子管理情報が記憶される記憶部と、前記原本データを記憶する前記所有者ノードのノード識別子および前記複製データを記憶する前記複製ノードのノード識別子を、前記原本データおよび前記複製データそれぞれに、ノード情報として付与するノード情報付与部と、前記ノードの離脱または追加を検知して、前記ノード識別子管理情報を、前記ノードの離脱または追加に応じた、前記データと前記所有者ノードおよび前記複製ノードとの新たな対応付けに変更して格納させるノード識別子管理部と、変更された前記ノード識別子管理情報に基づいて、自身が記憶している前記原本データ、および、前記原本データが消失した自身が記憶している複製データを、前記所有者ノードまたは前記複製ノードを変更するために行うデータ移行が必要か否かの判定対象となるデータを示す判定対象データとして抽出するデータ抽出部と、前記データ移行による前記ノード自身の処理負荷を抑制するように設定されたパラメータに基づく所定のタイミングのときに、前記抽出した判定対象データについて、前記変更されたノード識別子管理情報に対応した所有者ノードおよび複製ノードを特定し、前記特定した所有者ノードおよび複製ノードそれぞれのノード識別子が、前記ノード情報と比較して一致しない場合に、当該抽出した判定対象データを、前記データ移行が必要なデータを示すデータ移行対象データとして検出し、前記検出したデータ移行対象データを、前記特定した所有者ノードおよび複製ノードに移行するデータ移行処理部と、を備えることを特徴とするデータ移行処理システムとした。
【００１７】
また、請求項６に記載の発明は、クラスタを構成する複数のノードのいずれかが、クライアントにサービスを提供するためのデータを原本データとして記憶する所有者ノード、または、前記データの複製データを記憶する１つ以上の複製ノードとして割り当てられて記憶するデータ移行処理システムのデータ移行処理方法であって、前記データ移行処理システムを構成する前記複数のノードそれぞれが、前記ノードに固有な識別子であるノード識別子を、前記クラスタを構成する複数のノードについて、前記データと前記所有者ノードおよび前記複製ノードとが対応付けられたノード識別子管理情報が記憶される記憶部を備えており、前記原本データを記憶する前記所有者ノードのノード識別子および前記複製データを記憶する前記複製ノードのノード識別子を、前記原本データおよび前記複製データそれぞれに、ノード情報として付与するステップと、前記ノードの離脱または追加を検知して、前記ノード識別子管理情報を、前記ノードの離脱または追加に応じた、前記データと前記所有者ノードおよび前記複製ノードとの新たな対応付けに変更して格納させるステップと、変更された前記ノード識別子管理情報に基づいて、自身が記憶している前記原本データ、および、前記原本データが消失した自身が記憶している複製データを、前記所有者ノードまたは前記複製ノードを変更するために行うデータ移行が必要か否かの判定対象となるデータを示す判定対象データとして抽出するステップと、前記データ移行による前記ノード自身の処理負荷を抑制するように設定されたパラメータに基づく所定のタイミングのときに、前記抽出した判定対象データについて、前記変更されたノード識別子管理情報に対応した所有者ノードおよび複製ノードを特定し、前記特定した所有者ノードおよび複製ノードそれぞれのノード識別子が、前記ノード情報と比較して一致しない場合に、当該抽出した判定対象データを、前記データ移行が必要なデータを示すデータ移行対象データとして検出し、前記検出したデータ移行対象データを、前記特定した所有者ノードおよび複製ノードに移行するステップと、を実行することを特徴とするデータ移行処理方法とした。
【００１８】
このようにすることで、クラスタを構成するノードが離脱または追加した直後に、データ移行処理（再冗長化処理または再配置処理）を実行するのではなく、所定のタイミングでデータ移行処理の対象となるデータ（データ移行対象データ）を検出するための処理を実行し、そこで検出されたデータについて、データ移行処理を実行する。よって、ノードの負荷を抑えながらデータを移行（再冗長化・再配置）させることができる。
【００１９】
請求項２に記載の発明は、前記パラメータが、前記データ移行を並列で実行できる最大スレッド数を示すデータ移行処理スレッド数、前記データ移行を実行した後の待機時間を示すデータ移行処理実行間隔、前記データ移行対象データの検出処理を連続で実行する個数を示すシミュレーション最大個数、の少なくとも１つであることを特徴とする請求項１に記載のデータ移行処理システムとした。
【００２０】
このようにすることで、データ移行処理スレッド数、データ移行処理実行間隔、シミュレーション最大個数の少なくとも１つをパラメータとして設定し、データ移行を徐々に実行させることができる。
【００２１】
請求項３に記載の発明は、前記複数のノードそれぞれが、前記ノード自身の処理負荷を監視し、前記処理負荷が所定値を超えた場合に、前記データ移行処理部に処理中断情報を出力するノード負荷監視部を、さらに備え、前記データ移行処理部は、前記処理中断情報を受け取ると、前記データ移行を中断することを特徴とする請求項１または請求項２に記載のデータ移行処理システムとした。
【００２２】
このように、各ノードは、自身の処理負荷を監視することにより、処理負荷が所定値を超えた場合に、データ移行を中断することができる。よって、パラメータの設定による所定のタイミングでのデータ移行処理に加えて、ノードの処理負荷が所定値を超えた場合のタイミングでも、データ移行を中断することができるため、確実にノードの負荷を抑制しながらデータ移行させることができる。
【００２３】
請求項４に記載の発明は、クラスタを構成する複数のノードのいずれかが、クライアントにサービスを提供するためのデータを原本データとして記憶する所有者ノード、または、前記データの複製データを記憶する１つ以上の複製ノードとして割り当てられて記憶するデータ移行処理システムであって、前記データ移行処理システムを構成する前記複数のノードそれぞれが、前記ノードに固有な識別子であるノード識別子を、前記クラスタを構成する複数のノードについて、前記データと前記所有者ノードおよび前記複製ノードとが対応付けられたノード識別子管理情報が記憶される記憶部と、前記原本データを記憶する前記所有者ノードのノード識別子および前記複製データを記憶する前記複製ノードのノード識別子を、前記原本データおよび前記複製データそれぞれに、ノード情報として付与するノード情報付与部と、前記ノードの離脱または追加を検知して、前記ノード識別子管理情報を、前記ノードの離脱または追加に応じた、前記データと前記所有者ノードおよび前記複製ノードとの新たな対応付けに変更して格納させるノード識別子管理部と、変更された前記ノード識別子管理情報に基づいて、自身が記憶している前記原本データ、および、前記原本データが消失した自身が記憶している複製データを、前記所有者ノードまたは前記複製ノードを変更するために行うデータ移行が必要か否かの判定対象となるデータを示す判定対象データとして抽出するデータ抽出部と、前記抽出した判定対象データについて、前記変更されたノード識別子管理情報に対応した所有者ノードおよび複製ノードを特定し、前記特定した所有者ノードおよび複製ノードそれぞれのノード識別子が、前記ノード情報と比較して一致しない場合に、当該抽出した判定対象データを、前記データ移行が必要なデータを示すデータ移行対象データとして検出し、前記検出したデータ移行対象データを、前記特定した所有者ノードおよび複製ノードに移行するデータ移行処理部と、前記ノード自身の処理負荷を監視し、前記処理負荷が所定値を超えた場合に、前記データ移行処理部に処理中断情報を出力するノード負荷監視部と、を備え、前記データ移行処理部は、前記処理中断情報を受け取ると、前記データ移行を中断することを特徴とするデータ移行処理システムとした。
【００２４】
また、請求項７に記載の発明は、クラスタを構成する複数のノードのいずれかが、クライアントにサービスを提供するためのデータを原本データとして記憶する所有者ノード、または、前記データの複製データを記憶する１つ以上の複製ノードとして割り当てられて記憶するデータ移行処理システムのデータ移行処理方法であって、前記データ移行処理システムを構成する前記複数のノードそれぞれが、前記ノードに固有な識別子であるノード識別子を、前記クラスタを構成する複数のノードについて、前記データと前記所有者ノードおよび前記複製ノードとが対応付けられたノード識別子管理情報が記憶される記憶部を備えており、前記原本データを記憶する前記所有者ノードのノード識別子および前記複製データを記憶する前記複製ノードのノード識別子を、前記原本データおよび前記複製データそれぞれに、ノード情報として付与するステップと、前記ノードの離脱または追加を検知して、前記ノード識別子管理情報を、前記ノードの離脱または追加に応じた、前記データと前記所有者ノードおよび前記複製ノードとの新たな対応付けに変更して格納させるステップと、変更された前記ノード識別子管理情報に基づいて、自身が記憶している前記原本データ、および、前記原本データが消失した自身が記憶している複製データを、前記所有者ノードまたは前記複製ノードを変更するために行うデータ移行が必要か否かの判定対象となるデータを示す判定対象データとして抽出するステップと、前記抽出した判定対象データについて、前記変更されたノード識別子管理情報に対応した所有者ノードおよび複製ノードを特定し、前記特定した所有者ノードおよび複製ノードそれぞれのノード識別子が、前記ノード情報と比較して一致しない場合に、当該抽出した判定対象データを、前記データ移行が必要なデータを示すデータ移行対象データとして検出し、前記検出したデータ移行対象データを、前記特定した所有者ノードおよび複製ノードに移行するステップと、前記ノード自身の処理負荷を監視し、前記処理負荷が所定値を超えた場合に、前記データ移行を中断させるステップと、を実行することを特徴とするデータ移行処理方法とした。
【００２５】
このように、各ノードは、自身の処理負荷を監視することにより、処理負荷が所定値を超えた場合に、データ移行を中断することができる。よって、各ノードの処理負荷を確実の所定値以下に抑制した上で、データ移行させることが可能となる。
【００２６】
請求項５に記載の発明は、前記複数のノードそれぞれが、前記クライアントから前記データによる前記サービスの提供を要求するメッセージを受信した場合に、前記メッセージの処理を実行すると共に、前記サービスの対象となるデータが前記データ移行対象データである場合に、前記サービスの対象となるデータを、前記変更されたノード識別子管理情報に対応した所有者ノードおよび複製ノードに移行するメッセージ処理部を、さらに備えることを特徴とする請求項１ないし請求項４のいずれか１項に記載のデータ移行処理システムとした。
【００２７】
このようにすることで、各ノードは、メッセージを受信したことにより、それ以降も利用可能性が高いと予測されるデータについては、そのデータに関するメッセージ処理を実行すると共に、データ移行処理（再冗長化処理または再配置処理）を実行し、冗長度の減少の回復や、データの適正な配置を迅速に達成することができる。
【発明の効果】
【００２８】
本発明によれば、クラスタを構成するノードの離脱または追加があった場合に、ノードの処理負荷を抑えながらデータを移行させる、データ移行処理システムおよびデータ移行処理方法を提供することができる。
【図面の簡単な説明】
【００２９】
【図１】本実施形態に係るデータ移行処理システムを含む分散処理システムの全体構成を示す図である。
【図２】本実施形態に係るデータ移行処理システムを構成する各ノードによる、データの再冗長化処理の概要を説明するための図である。
【図３】本実施形態に係るノードの構成例を示す機能ブロック図である。
【図４】本実施形態に係るノード識別子管理テーブルのデータ構成例を示す図である。
【図５】本実施形態に係るデータ移行処理システムにおいて、各サーバが実行するデータ移行処理の全体の流れを示すフローチャートである。
【図６】本実施形態に係るノードのデータ移行処理部が行うデータ移行対象データの検出処理の流れを示すフローチャートである。
【図７】本実施形態に係るノードのデータ移行パラメータ管理部により設定されるデータ移行処理の所定のタイミングを説明するための図である。
【図８】本実施形態の変形例１に係るノードの構成例を示す機能ブロック図である。
【図９】本実施形態の変形例２に係るノードの構成例を示す機能ブロック図である。
【図１０】コンシステントハッシュ法によるデータ管理手法を説明するための図である。
【図１１】コンシステントハッシュ法によるデータ管理手法において、ノードが離脱した例を示す図である。
【発明を実施するための形態】
【００３０】
次に、本発明を実施するための形態（以下、「本実施形態」という）におけるデータ移行処理システム等について説明する。
【００３１】
＜分散処理システムの全体構成＞
まず、本実施形態に係るデータ移行処理システム１００を含む分散処理システム１０００の全体構成について説明する。
図１は、本実施形態に係るデータ移行処理システム１００を含む分散処理システム１０００の全体構成を示す図である。
【００３２】
この分散処理システム１０００は、各クライアント２からのメッセージを受け付けるロードバランサ３と、振り分け装置４と、クラスタを構成する複数のノード１とを含んで構成される。ロードバランサ３は、クライアント２からのメッセージを単純なラウンドロビン等により各振り分け装置４に振り分ける。振り分け装置４は、受信したメッセージを、例えば、コンシステントハッシュ法等に基づき、各ノード１に振り分ける。各ノード１では、メッセージ処理を行い、クライアント２にサービスを提供する。また、本実施形態において、クラスタを構成する複数のノード１をデータ移行処理システム１００として説明する。
【００３３】
なお、図１においては、振り分け装置４とノード１とを別装置として記載したが、同一サーバ上で別々の機能として動作させることも可能である。また、振り分け装置４も、図１に示すように、クラスタ構成をとることができる。さらに、ロードバランサ３が存在せず、クライアント２から任意の振り分け装置４にメッセージを送信することも可能である。
【００３４】
本実施形態では、分散処理システム１０００のデータ管理手法として、ノード１の離脱時および追加時の影響が少ない、コンシステントハッシュ法によるデータ管理手法を例として説明する。ただし、コンシステントハッシュ法に限定されるものではない。また、図１０に示した複製データの配置手法により、コンシステントハッシュ法のＩＤ空間上で右隣（時計回りに次）のノード１に複製データを担当させることとする。
また、本実施形態に係るデータ移行処理システム１００では、ノード１の離脱時と追加時において共に同様の仕組みでデータの再冗長化処理、再配置処理を実行するため、ノード離脱後にデータの再冗長化処理を実行する例を主として説明する。
【００３５】
＜処理概要＞
次に、本実施形態に係るデータ移行処理システム１００の処理概要について説明する。
図２は、本実施形態に係るデータ移行処理システム１００を構成する各ノード１による、データの再冗長化処理（複製数：１）の概要を説明するための図である。図２（ａ）は、再冗長化処理前の初期状態を示し、図２（ｂ）は、ノード１（ここでは、ノード「４」）の減設（離脱）後の状態を示し、図２（ｃ）は、データの再冗長化処理を実行した状態を示す。
【００３６】
まず、図２（ａ）に示すように、初期状態において、データＸ（データＸのＩＤ（データ識別子））については、ＩＤ空間を時計回りに辿り最初に出合ったノード「１」が担当ノードとなる。つまり、データＸの原本データがノード「１」に格納される。なお、原本データを格納し管理するノード１を、以下、「所有者ノード」と称することがある。そして所有者ノードであるノード「１」のさらに右隣のノード「４」がデータＸの複製データを格納する。なお、複製データを格納し管理するノード１（複製ノード）を、以下、「バディ」と称することがある。
このとき、各ノード１は、自身に格納する各データに、所有者ノードの識別子とバディの識別子とを付与する（ステップＳ１）。なお、この所有者ノードの識別子とバディ（複製ノード）の識別子とを併せてノード情報と称する。
【００３７】
次に、図２（ｂ）に示すように、クラスタを構成するノード１のうちの１つ、ここでは、ノード「４」が障害等により離脱したとする。各ノード１は、クラスタを構成するノード１（ノード「４」）の離脱を検知すると、（１）自身が原本として管理しているデータ（原本データ）、および、（２）自身が複製として管理しているデータ（複製データ）のうち、その複製データの原本データを管理している所有者ノードが離脱したノード１と一致するデータ、つまり、原本データが消失した複製データ、を減設後に再冗長化処理が必要か否かの判定対象となるデータ（以下、「判定対象データ」と称する。）として抽出する（ステップＳ２）。
【００３８】
続いて、各ノード１は、所定のタイミングで、抽出した判定対象データについて、減設後に担当すべきノード（所有者ノードおよびバディ）をシミュレーションし、そのシミュレーション結果と、判定対象データのノード情報とを比較する。そして、各ノード１は、その比較の結果、所有者ノードの識別子またはバディの識別子が一致しない判定対象データを、データ移行対象データとして検出し、データ移行処理（ここでは、再冗長化処理）を実行する（ステップＳ３）。
各ノード１が、シミュレーションを実施する所定のタイミングは、複数のパラメータを設定することにより決定される。このパラメータには、例えば、データ移行処理スレッド数（データ移行処理（再冗長化処理または再配置処理）を並列で実行できる最大スレッド数）、データ移行処理実行間隔（データ移行処理を実行した直後の待機時間）、シミュレーション最大個数（各スレッドがシミュレーションを連続で実行する最大個数）等により決定される。なお、これらのパラメータの詳細は後記する。
【００３９】
このように、本実施形態に係るデータ移行処理システム１００等においては、クラスタを構成するノード１が離脱または追加した直後に、データ移行処理（再冗長化処理または再配置処理）を実行するのではなく、所定のタイミングでデータ移行処理の対象となるデータ（データ移行対象データ）を検出するための処理を実行し、そこで検出されたデータについて、データ移行処理を実行する。よって、ノード１の負荷を抑えながらデータを移行（再冗長化または再配置）させることができる。
【００４０】
＜ノードの構成＞
以下、本実施形態に係るデータ移行処理システム１００を構成するノード１の構成例について、具体的に説明する。
【００４１】
図３は、本実施形態に係るノード１の構成例を示す機能ブロック図である。
ノード１は、図１に示したように、振り分け装置４と通信可能に接続されると共に、クラスタを構成する自身以外の他のノード１とも通信可能に接続される。そして、クライアント２からのメッセージを受信し、サービスを提供する。また、このノード１は、クラスタを構成するノード１に離脱または追加があった場合に、移行が必要なデータについて、再冗長化処理または再配置処理を実行する。
このノード１は、図３に示すように、制御部１０と、入出力部１１と、メモリ部１２と、記憶部１３とを含んで構成される。
【００４２】
入出力部１１（入力部）は、振り分け装置４や、自身以外の他のノード１との間の情報の入出力を行う。また、この入出力部１１は、通信回線を介して情報の送受信を行う通信インタフェースと、不図示のキーボード等の入力手段やモニタ等の出力手段等との間で入出力を行う入出力インタフェースとから構成される。
【００４３】
制御部１０は、ノード１全体の制御を司り、ノード識別子管理部１０１、メッセージ処理部１０２、死活監視部１０３、ノード情報付与部１０４、データ抽出部１０５、データ移行処理部１０６およびデータ移行パラメータ管理部１０７を含んで構成される。なお、この制御部１０は、例えば、記憶部１３に格納されたプログラムをＣＰＵ（Central Processing Unit）がメモリ部１２であるＲＡＭ（Random Access Memory）に展開し実行することで実現される。
【００４４】
ノード識別子管理部１０１は、クラスタを構成する各ノード１に関する識別情報をノード識別子管理テーブル４００（ノード識別子管理情報）として管理する。
【００４５】
図４は、本実施形態に係るノード識別子管理テーブル４００（ノード識別子管理情報）のデータ構成例を示す図である。図４に示すように、ノード識別子管理テーブル４００は、クラスタを構成する各ノード１のノード識別子４０１とアドレス４０２とを含んで構成される。
このノード識別子４０１は、コンシステントハッシュ法のＩＤ空間上でのノードＩＤに対応する。また、コンシステントハッシュ法において仮想ＩＤを用いる場合には、ノード識別子４０１は、仮想ＩＤ毎に割り当てられ、ノード識別子管理テーブル４００に登録される。そして、このノード識別子管理テーブル４００では、例えば、ノード識別子４０１を昇順に並べることにより、コンシステントハッシュ法のＩＤ空間におけるＩＤ（または仮想ＩＤ）を昇順に並べて管理することができる。つまり、ノード識別子管理テーブル４００において、ノード識別子を昇順に並べたときの次のノード１が、ＩＤ空間上での右隣（時計回りに次）のノード１となる。
例えば、図４においては、コンシステントハッシュ法のＩＤ空間に基づくデータ識別子が「０」から「５６」であるデータについては、同図の第１行目が指すノード（ノード識別子「５６」、アドレス「１９２．１６８．０．２４」であるノード）が「所有者ノード」として担当し、次の第２行目が指すノード（ノード識別子「１７２」、アドレス「１９２．１６８．１．２５」）がバディとして担当することを示す。同様に、データ識別子が「５６」に１を加えた「５７」から「１７２」であるデータについては、第２行目が指すノードが「所有者ノード」として担当し、次の第３行目が指すノードがバディとして担当することを示す。
このようにして、このノード識別子管理テーブル４００に基づき、データとその所有者ノードとバディとが対応付けられる。
なお、このノード識別子４０１は、ノード識別子管理部１０１が各ノード１に対して付与することもできるし、他のノード１や外部装置（例えば、振り分け装置４等）が生成したノード識別子管理テーブル４００を受信して格納することも可能である。
【００４６】
ノード識別子管理部１０１は、クラスタを構成する複数のノード１において、あるノード１が離脱した際には、そのノード１のノード識別子４０１とアドレス４０２とを含むレコードを削除する。また、ノード識別子管理部１０１は、クラスタを構成する複数のノード１において、ノード１が追加された場合には、そのノード１のノード識別子４０１とアドレス４０２とを含むレコードを新規に登録する。
【００４７】
図３に戻り、メッセージ処理部１０２は、振り分け装置４から振り分けられたメッセージを受信し、そのメッセージの処理を実行し、処理結果をクライアント２に返信することにより、サービスを提供する。このメッセージによりメッセージ処理部１０２が実行する処理は、例えば、データの登録、更新、検索、削除等である。また、メッセージ処理部１０２は、データの登録や更新等のメッセージを受信した場合に、自身以外の他のノード（ここでは、ノード識別子を昇順に並べた場合の次のノード、つまり、コンシステントハッシュ法のＩＤ空間での右隣のノード）にデータの複製を行うことでデータの冗長化を実現する。また、メッセージ処理部１０２は、メッセージの処理に必要なデータをそのノード１自身が保持していなかった場合には、他のノード１に要求すること等により、そのデータを取得することが可能である。
なお、メッセージ処理部１０２は、クラスタを構成するノード１に離脱や追加があった場合において、データの再冗長化や再配置が実行される以前に、データ移行の対象となるデータに関するメッセージを受信したときには、そのメッセージの処理を実行すると共に、そのデータのデータ移行処理（再冗長化処理または再配置処理）を実行する。
【００４８】
死活監視部１０３は、自身以外の他のノード１との間で、所定の時間間隔で死活監視信号の送受信を実行することにより、クラスタを構成するノード１の離脱や追加を監視する。死活監視部１０３が、ノード１の離脱や追加を検出した場合には、自ノード１若しくは他ノード１のノード識別子管理部１０１、または、ノード識別子を設定する外部装置に通知を行い、ノード識別子管理テーブル４００に反映させる。つまり、クラスタを構成する複数のノード１は、常に、同一内容のノード識別子管理テーブル４００を備えるようにする。
【００４９】
ノード情報付与部１０４は、各データに、各データのデータ識別子に対応づけてノード情報を付与する。なお、ノード情報とは、前記したように、原本データを保持しているノード（所有者ノード）のノード識別子と複製データを保持しているノード（バディ：複製ノード）のノード識別子の情報である。ノード情報付与部１０４は、データ移行処理部１０６が、ノード１の離脱や追加によりデータの再冗長化処理または再配置処理を実行した場合に、新たなノード情報をそのデータに付与する。
よって、ノード情報付与部１０４は、新規にデータを登録する際と、ノード１の離脱や追加等によりデータの再冗長化処理または再配置処理を実行する際に、対象となるデータに対し、ノード情報を付与する。
【００５０】
データ抽出部１０５は、ノード識別子管理部１０１により、ノード識別子管理テーブル４００（図４参照）が変更されたことを契機として、（１）自身が原本として管理しているデータ（原本データ）、および、（２）自身が複製として管理しているデータ（複製データ）のうち、その複製データの原本データを管理しているノード１（所有者ノード）が離脱したノード１と一致するデータ、つまり、原本データが消失した複製データ、をデータ移行処理（再冗長化処理または再配置処理）が必要か否かの判定対象となるデータ（判定対象データ）として抽出し、その抽出したデータのデータ識別子を、抽出データ管理テーブル２００に格納する。
本処理の契機は、上述のように、ノード識別子管理テーブル４００（図４参照）の変更であるが、別の実施形態では、一部のノード１または外部装置（例えば、システム管理装置）が他の各ノード１に対して再冗長化処理または再配置処理の開始要求メッセージを送信することとして、当該他の各ノード１はそのメッセージを受信することを本処理の契機にするようにしてもよい。
なお、ノード１が追加された場合には、（２）の原本データが消失した複製データは、存在しないため、そのノード１が原本として管理しているデータ（原本データ）のみが抽出される。
【００５１】
データ移行処理部１０６は、データ移行パラメータ管理部１０７により設定されるパラメータに基づく所定のタイミングで、データ抽出部１０５により抽出され抽出データ管理テーブル２００に格納された判定対象データについて、変更されたノード識別子管理テーブル４００に基づき、コンシステントハッシュ法等の予め定められたデータ管理手法に従った場合の所有者ノードとバディとを特定し（以下、この処理を「シミュレーション」と称す。）、各データ（判定対象データ）に付与されているノード情報と比較する。そして、データ移行処理部１０６は、この比較の結果、所有者ノードの識別子およびバディの識別子が一致（完全一致）しないデータを、データ移行対象データとして検出し、データ移行処理（再冗長化処理または再配置処理）を実行する。
【００５２】
なお、冗長数が３以上（複製データが２以上）の場合、複製データを管理する複数のノード１（ＩＤ空間上で原本データを管理する所有者ノードに近いノードから、バディ「１」，バディ「２」，・・・と呼ぶ。）が同一データに対してデータ移行処理を実行する虞がある。そこで、複数のバディが存在する場合には、番号の若いバディがデータ移行処理を担当することとする。このデータ移行対象データの検出処理の詳細については、図６を参照して後記する。
【００５３】
データ移行パラメータ管理部１０７は、データ移行処理部１０６がデータ移行処理を実行する所定のタイミングを、１つ以上のパラメータを用いて設定する。このデータ移行パラメータ管理部１０７により、データ移行処理の実行タイミングが調整されることで、データ移行処理の負荷が一度に集中して通常の処理を妨げサービス品質の低下を招かないように負荷を調整しながら、データ移行処理を実行できる。
【００５４】
このデータ移行パラメータ管理部１０７に設定されるパラメータは、例えば、データ移行処理スレッド数、データ移行処理実行間隔、シミュレーション最大個数である。
データ移行処理スレッド数とは、再冗長化処理や再配置処理を並列で実行できる最大スレッド数である。このデータ移行処理スレッド数に大きな値を設定すると、データ移行処理にかかる時間を短縮することができるが、ノード１の処理負荷は大きくなる。これに対し、データ移行処理スレッド数に小さな値を設定すると、データ移行処理にかかる時間は増加するが、ノード１の処理負荷は小さくなる。
データ移行処理実行間隔とは、各スレッドで、データ移行処理部１０６がデータ移行対象データの検出処理（図６）を実行した結果、データ移行対象データが検出され、データ移行処理部１０６が、そのデータ移行処理（再冗長化処理または再配置処理）を実行した後に待機する時間を指す。
シミュレーション最大個数とは、各スレッドが前記したシミュレーション（変更後のノード識別子管理テーブル４００（図４参照）に基づく、所有者ノードとバディの特定）を含むデータ移行対象データの検出処理を連続で実行する個数を指す。データ移行処理部１０６は、データ移行対象データの検出処理を連続で実行した後に、所定の時間待機し、その後、再びシミュレーションを含むデータ移行対象データの検出処理を開始する。
このシミュレーション最大個数を少なく設定する、または、データ移行処理実行間隔を長く設定することで、ノード１は、処理負荷を抑えながら徐々にデータ移行処理を実行することが可能となる。
なお、このデータ移行処理スレッド数、データ移行処理実行間隔、シミュレーション最大個数の各パラメータは、データ移行パラメータ管理部１０７により、すべて設定されてもよいし、いずれか１つでもよいし、各パラメータを任意に組み合わせて設定されてもよい。
また、このデータ移行パラメータ管理部１０７により設定されたパラメータにより調整される所定のタイミングでのデータ移行処理の詳細については、図７を参照して後記する。
【００５５】
メモリ部１２は、ＲＡＭ等の一次記憶装置からなり、制御部１０によるデータ処理に必要な情報を一時的に記憶している。なお、このメモリ部１２には、データ抽出部１０５が抽出した判定対象データのデータ識別子を格納する前記した抽出データ管理テーブル２００が記憶される。
【００５６】
記憶部１３は、ハードディスクやフラッシュメモリ等の記憶装置からなり、サービスの対象となる原本データや複製データを含むデータ３００や、前記したノード識別子管理テーブル４００（図４参照）等が記憶される。また、この記憶部１３には、データ移行パラメータ管理部１０７により設定される各パラメータ値（不図示）等が記憶される。
なお、データ３００の各データには、そのデータのデータ識別子、所有者ノードのノード識別子および、バディのノード識別子が含まれる。
【００５７】
＜データ移行処理システムの処理流れ＞
次に、本実施形態に係るデータ移行処理システム１００において、データ移行処理を実行する場合の処理の流れについて説明する。
【００５８】
（データ移行処理の全体の流れ）
図５は、本実施形態に係るデータ移行処理システム１００において、各ノード１が実行するデータ移行処理の全体の流れを示すフローチャートである。
【００５９】
まず、ノード１の死活監視部１０３は、自身以外の他のノード１との間で、所定の時間間隔で死活監視信号を送受信することにより、クラスタを構成するノード１の離脱や追加が発生したか否かを判定する（ステップＳ１０）。そして、死活監視部１０３は、ノード１の離脱や追加が発生したと判定した場合に（ステップＳ１０→Ｙｅｓ）、その離脱または追加の情報をノード識別子管理部１０１に出力する。一方、死活監視部１０３は、ノード１の離脱や追加が発生していないと判定した場合には（ステップＳ１０→Ｎｏ）、ステップＳ１０の判定処理を繰り返す。
なお、死活監視部１０３は、他のノード１との間での死活監視信号の送受信ではなく、外部装置（例えば、振り分け装置４）や他のノード１が検知したノード１の離脱や追加の発生情報を受信することにより、ノード１の離脱や追加の情報を取得するようにしてもよい。
【００６０】
次に、ノード識別子管理部１０１は、死活監視部１０３から受け取った、ノード１の離脱や追加の情報に基づき、ノード識別子管理テーブル４００（図４参照）を変更する（ステップＳ１１）。
具体的には、ノード識別子管理部１０１は、クラスタを構成する複数のノード１において、あるノード１が離脱した場合には、そのノード１のノード識別子４０１とアドレス４０２とを含むレコードを削除する。また、ノード識別子管理部１０１は、クラスタを構成する複数のノード１において、新たなノード１が追加された場合には、そのノード１のノード識別子４０１とアドレス４０２とを含むレコードを新規に登録する。
【００６１】
続いて、データ抽出部１０５は、ノード識別子管理部１０１によりノード識別子管理テーブル４００（図４参照）が変更されたことを契機として、判定対象データを抽出し、その判定対象データのデータ識別子を抽出データ管理テーブル２００に格納する（ステップＳ１２）。
具体的には、データ抽出部１０５は、（１）自身が原本として管理しているデータ（原本データ）、および、（２）自身が複製として管理しているデータ（複製データ）のうち原本データが消失した複製データを、データ移行処理（再冗長化処理または再配置処理）が必要か否かの判定対象となるデータ（判定対象データ）として抽出し、その抽出したデータのデータ識別子を、抽出データ管理テーブル２００に格納する。
【００６２】
そして、データ移行処理部１０６は、データ移行パラメータ管理部１０７により設定された、所定のタイミングであるか否かを判定する（ステップＳ１３）。データ移行処理部１０６は、所定のタイミングであれば（ステップＳ１３→Ｙｅｓ）、次のステップＳ１４に進み、所定のタイミングでなければ（ステップＳ１３→Ｎｏ）、所定のタイミングになるまで待機する。
なお、データ移行パラメータ管理部１０７により設定される所定のタイミングについては、図７において説明する。
【００６３】
ステップＳ１４において、データ移行処理部１０６は、抽出データ管理テーブル２００を参照し、判定対象データ（具体的には判定対象データのデータ識別子）を１つ抽出する（ステップＳ１４）。
【００６４】
次に、データ移行処理部１０６は、ステップＳ１４で抽出した判定対象データが、データ移行処理（再冗長化処理または再配置処理）の対象となるデータ（データ移行対象データ）か否かを検出する処理（データ移行対象データの検出処理）を実行する（ステップＳ１５）。なお、このデータ移行対象データの検出処理の詳細は、図６において説明する。
【００６５】
続いて、データ移行処理部１０６は、ステップＳ１５により、データ移行対象データが検出されたか否かを判定する（ステップＳ１６）。ここで、データ移行処理部１０６は、データ移行対象データが検出された場合には（ステップＳ１６→Ｙｅｓ）、ステップＳ１７に進み、検出されなかった場合には（ステップＳ１６→Ｎｏ）、ステップＳ１８に進む。
【００６６】
ステップＳ１７において、データ移行処理部１０６は、データ移行処理（再冗長化処理または再配置処理）を実行する。なお、このデータ移行処理部１０６によるデータ移行処理は、ノード情報付与部１０４が、移行するデータに付与されたノード情報を、ステップＳ１５のデータ移行対象データの検出処理でシミュレーション（変更後のノード識別子管理テーブル４００（図４参照）に基づく、所有者ノードとバディの特定）した所有者ノードの識別子とバディの識別子とに変更してから実行される。
【００６７】
次に、ステップＳ１８において、データ移行処理部１０６は、抽出データ管理テーブル２００に格納されたすべての判定対象データ（データ識別子）を処理したか否かを判定する。ここで、データ移行処理部１０６は、抽出データ管理テーブル２００に、まだ処理していない判定対象データ（データ識別子）が格納されている場合には（ステップＳ１８→Ｎｏ）、ステップＳ１３に戻り処理を続ける。一方、データ移行処理部１０６は、抽出データ管理テーブル２００に格納されたすべての判定対象データ（データ識別子）の処理を終えている場合には（ステップＳ１８→Ｙｅｓ）、データ移行処理を終了する。
【００６８】
なお、ノード１のデータ移行処理部１０６が、この図５のステップＳ１３〜Ｓ１８によるデータ移行処理を徐々に実行している間においても、そのノード１はクライアント２からメッセージを受信し、メッセージ処理部１０２がそのメッセージに対する処理を実行している。メッセージ処理部１０２は、受信したメッセージについての処理を実行すると共に、そのメッセージの対象となるデータが、データ移行対象データか否かを、そのデータに付されたノード情報を参照して判定する。具体的には、そのノード情報中の所有者ノードとバディのいずれかが、各々自ノード、ＩＤ空間上の右隣ノードと異なれば、データ移行対象データと判定する。そして、メッセージ処理部１０２は、当該データがデータ移行対象データである場合には、そのデータのデータ移行処理（再冗長化処理または再配置処理）を実行する。なお、自ノードが受信したメッセージにかかるデータを保持していない場合（ＩＤ空間上の右隣にノードが追加された場合に発生しうる）には、メッセージ処理部１０２は、他ノードからのデータの取得を含む再配置処理を伴ってメッセージの処理を実行する。データの取得先は、ノード識別子管理テーブル４００を参照して特定する。
このようにすることで、ノード１は、メッセージを受信したことにより、それ以降も利用可能性が高いと予測されるデータについては、そのデータに関するメッセージ処理を実行すると共に、データ移行処理（再冗長化処理または再配置処理）を行い、冗長度の減少の回復や、データの適正な配置を迅速に達成することができる。
【００６９】
（データ移行対象データの検出処理）
次に、図５のステップＳ１５において、ノード１のデータ移行処理部１０６が実行するデータ移行対象データの検出処理について詳細に説明する。
図６は、本実施形態に係るノード１のデータ移行処理部１０６が行うデータ移行対象データの検出処理の流れを示すフローチャートである。
【００７０】
まず、ノード１のデータ移行処理部１０６は、抽出データ管理テーブル２００から抽出した判定対象データについて、シミュレーション（図６において、「Ａ処理」と記載）を実行する（ステップＳ２０）。具体的には、データ移行処理部１０６は、抽出した判定対象データについて、変更されたノード識別子管理テーブル４００に基づき、コンシステントハッシュ法等の予め定められたデータ管理手法に従った場合の所有者ノードとバディとを特定する。
【００７１】
次に、データ移行処理部１０６は、抽出データ管理テーブル２００から抽出した判定対象データに付されたノード情報（所有者ノードの識別子とバディの識別子）を抽出（図６において、「Ｂ処理」と記載）する（ステップＳ２１）。
【００７２】
続いて、シミュレーション（Ａ処理）の結果、自ノードが所有者ノードか否かを判定する（ステップＳ２２）。ここで、シミュレーション（Ａ処理）の結果、自ノードが所有者ノードである場合には（ステップＳ２２→Ｙｅｓ）、次のステップＳ２３に進み、一方、自ノードが所有者ノードでない場合には（ステップＳ２２→Ｎｏ）、ステップＳ２５に進む。
【００７３】
ステップＳ２３において、データ移行処理部１０６は、ノード情報抽出（Ｂ処理）の結果、自ノードが所有者ノードか否かを判定する。ここで、ノード情報抽出（Ｂ処理）の結果、自ノードが所有者ノードでない場合は（ステップＳ２３→Ｎｏ）、そのデータ（判定対象データ）を、データ移行処理の対象となるデータ（データ移行対象データ）として決定する。つまり、同じデータに関して、所有者ノードがＡ処理とＢ処理とで一致しないため、データ移行が必要なデータ（図６において、「データ移行対象」と記載）となる。一方、ノード情報抽出（Ｂ処理）の結果、自ノードが所有者ノードである場合は（ステップＳ２３→Ｙｅｓ）、次のステップＳ２４に進む。
【００７４】
ステップＳ２４において、データ移行処理部１０６は、シミュレーション（Ａ処理）の結果とノード情報抽出（Ｂ処理）の結果とでバディが一致するか否かを判定する。ここで、バディが一致する場合には（ステップＳ２４→Ｙｅｓ）、そのデータ（判定対象データ）は、データ移行の必要のないデータ（図６において、「データ移行対象外」と記載）となる。一方、バディが一致しない場合には（ステップＳ２４→Ｎｏ）、そのデータ（判定対象データ）を、データ移行処理の対象となるデータ（データ移行対象データ）として決定する。つまり、所有者ノードが一致していても、バディが一致していないため、データ移行対象データとなる。
【００７５】
次に、ステップＳ２２において、シミュレーション（Ａ処理）の結果、自ノードが所有者ノードでない場合には（ステップＳ２２→Ｎｏ）、データ移行処理部１０６は、ノード情報抽出（Ｂ処理）の結果、自ノードが所有者ノードか否かを判定する（ステップＳ２５）。ここで、ノード情報抽出（Ｂ処理）の結果、自ノードが所有者ノードある場合には（ステップＳ２５→Ｙｅｓ）、そのデータ（判定対象データ）を、データ移行処理の対象となるデータ（データ移行対象データ）として決定する。つまり、所有者ノードがＡ処理とＢ処理で一致しないため、データ移行対象となる。一方、ノード情報抽出（Ｂ処理）の結果、自ノードが所有者ノードでない場合は（ステップＳ２５→Ｎｏ）、次のステップＳ２６に進む。
【００７６】
ステップＳ２６において、データ移行処理部１０６は、ノード情報抽出（Ｂ処理）の結果、所有者ノードが変更後のノード識別子管理テーブル４００（図４参照）に存在するか否かを判定する。ここで、存在する場合には（ステップＳ２６→Ｙｅｓ）、そのデータ（判定対象データ）は、データ移行対象外となる。一方、存在しない場合には（ステップＳ２６→Ｎｏ）、次のステップＳ２７に進む。
【００７７】
ステップＳ２７において、データ移行処理部１０６は、ノード情報抽出（Ｂ処理）の結果、自身より若いバディ（ノード識別子を昇順に並べた場合に、番号が若いバディ）が存在し、変更後のノード識別子管理テーブル４００（図４参照）にも、その自身より若いバディが存在するか否かを判定する。つまり、複数のバディが存在する場合に、自身が番号の最も若いバディであるか否かを判定する。ここで、自身より若いバディが存在する場合には（ステップＳ２７→Ｙｅｓ）、同一データに対し重複してデータ移行処理を実行するのを避けるため、そのデータ（判定対象データ）を、データ移行対象外とする。一方、自身より若いバディが存在しない場合には（ステップＳ２７→Ｎｏ）、そのデータ（判定対象データ）を、データ移行処理の対象となるデータ（データ移行対象データ）として決定する。
【００７８】
このようにすることで、データ移行処理部１０６は、抽出データ管理テーブル２００に抽出された判定対象データそれぞれについて、データ移行処理を実行すべきか否かを判定し、データ移行対象データを検出することができる。また、複数のバディが存在する場合であっても、離脱や追加されたノード１の両隣にある、所有者ノードと番号が最も若いバディとがトリガとなりデータ移行処理が実行されるので、同一データについて、重複してデータ移行処理を実行することを避けることができる。
【００７９】
（所定のタイミングでのデータ移行処理）
次に、図７を参照して、データ移行パラメータ管理部１０７により設定されるパラメータに基づく、データ移行処理の所定のタイミングについて説明する。
図７においては、データ移行パラメータ管理部１０７に設定されるパラメータの例として、データ移行処理スレッド数、データ移行処理実行間隔、および、シミュレーション最大個数が設定されている例を示す。
【００８０】
図７は、データ移行処理スレッド数（符号Ｐ１）が「３」に設定されている例を示している。
また、各スレッドにおいて、データ移行処理部１０６が、抽出データ管理テーブル２００から判定対象データを取得すると（ステップＳ３０）、データ移行対象データの検出処理を実行し（ステップＳ３１）、データ移行対象データが検出された場合には、そのままデータ移行処理（再冗長化処理または再配置処理）を実行する（ステップＳ３２）。
【００８１】
ここで、データ移行対象データについて、ステップＳ３２において、データ移行処理を実行した後、データ移行処理部１０６は、データ移行処理実行間隔（符号Ｐ２）が設定されているため、所定の時間、次の判定対象データの取得処理（ステップＳ３０）を行わずに待機する。
【００８２】
また、図７のスレッド「１」に示すように、シミュレーション最大個数（符号Ｐ３）のパラメータが「５」に設定されている場合には、データ移行処理部１０６は、抽出データ管理テーブル２００から判定対象データを取得し、データ移行対象データの検出処理を５回連続して実行する。そして、データ移行処理部１０６は、シミュレーション最大個数（ここでは「５」回）のデータ移行対象データの検出処理を行っても、データ移行対象データが検出されなかったときには、所定の時間待機する。
【００８３】
このようにすることで、各パラメータにより設定された所定のタイミングでデータ移行対象データの検出処理を実行し、データ移行対象データが検出された場合に、データ移行処理を実行することができる。よって、クラスタを構成するノード１が離脱したり追加されたりした直後において、他の既存のノード１は、データ移行処理を一時に実行しないため、ノード１が処理負荷を抑えながら徐々にデータ移行処理（再冗長化処理または再配置処理）を実行することができる。
【００８４】
以上説明したように、本実施形態に係る、データ移行処理システム１００およびデータ移行処理方法によれば、クラスタを構成するノード１の離脱または追加があった場合に、ノード１の処理負荷を抑えながらデータを移行させることができる。
【００８５】
＜変形例１＞
次に、本実施形態に係るデータ移行処理システム１００の変形例１について説明する。
図８は、本実施形態の変形例１に係るノード１ａの構成例を示す機能ブロック図である。
図３に示した本実施形態に係るノード１との違いは、制御部１０に、ノード負荷監視部１０８を追加して備えていることである。
【００８６】
ノード負荷監視部１０８は、ノード１ａ自身の処理負荷（例えば、ＣＰＵ使用率、メモリ使用率等）を監視し、その処理負荷に対し予め設定された所定値を超えた場合に、データ移行処理部１０６に処理中断情報を出力することにより、データ移行処理部１０６によるデータ移行処理を中断させる。具体的には、例えば、データ移行処理部１０６が、図７のステップＳ３０で示した、抽出データ管理テーブル２００からの判定対象データの取得を中止することにより、データ移行処理を中断する。
そして、ノード負荷監視部１０８は、ノード１ａ自身の処理負荷が所定値以下になった場合に、データ移行処理部１０６に処理開始情報を出力することにより、データ移行処理部１０６によるデータ移行処理を再開させる。例えば、データ移行処理部１０６が、図７のステップＳ３０で示した判定対象データの取得処理を再開することにより、データ移行処理を実行する。
【００８７】
このようにすることで、データ移行パラメータ管理部１０７で設定されたパラメータに基づき、所定のタイミングでデータ移行処理部１０６がデータ移行処理を実行している場合であっても、何らかの理由（例えば、クライアント２から大量のメッセージを受信した場合等）で、ノード１ａの処理負荷が所定を超えた場合に、データ移行処理（再冗長化処理または再配置処理）を中断することができる。よって、ノード１ａの処理負荷を抑制することが可能となる。
【００８８】
＜変形例２＞
次に、本実施形態に係るデータ移行処理システム１００の変形例２について説明する。
図９は、本実施形態の変形例２に係るノード１ｂの構成例を示す機能ブロック図である。
図８に示した本実施形態の変形例１に係るノード１ａとの違いは、制御部１０にデータ移行パラメータ管理部１０７を備えていないことである。
【００８９】
この場合、ノード１ｂは、データ移行パラメータ管理部１０７を備えていないため、図５のステップＳ１３およびＳ１４で示した、抽出データ管理テーブル２００から判定対象データを、設定したパラメータに基づく所定のタイミングで取得するような処理を、データ移行処理部１０６は実行していない。データ移行処理部１０６は、ステップＳ１３を実行することなく、直ちにステップＳ１４にて抽出データ管理テーブル２００から判定対象データを取得し、データ移行対象データの検出処理を実行し、データ移行対象データが検出された場合には、そのデータのデータ移行処理を実行する。なお、この場合、図５のフローにおいて、ステップＳ１８→Ｎｏのとき、ステップＳ１４に戻る。
そして、ノード負荷監視部１０８は、ノード１ｂ自身の処理負荷（例えば、ＣＰＵ使用率、メモリ使用率等）を監視し、その処理負荷に対し予め設定された所定値を超えた場合に、データ移行処理部１０６に処理中断情報を出力することにより、データ移行処理部１０６によるデータ移行処理を中断させる。また、ノード負荷監視部１０８は、ノード１ｂ自身の処理負荷が所定値以下になった場合に、データ移行処理部１０６に処理開始情報を出力することにより、データ移行処理部１０６によるデータ移行処理を再開させる。
【００９０】
このようにすることで、ノード１ｂは、自身の処理負荷が所定値を超えた場合に、データ移行処理を中断し、処理負荷が所定値以下になった場合に、データ移行処理を再開することができる。よって、ノード１ｂは、自身の処理負荷を直接的に監視し、処理負荷が所定値以上にならないように抑制した上で、データ移行処理を実行することが可能となる。
【符号の説明】
【００９１】
１，１ａ，１ｂ  ノード
２      クライアント
３      ロードバランサ
４      振り分け装置
１０    制御部
１１    入出力部（入力部）
１２    メモリ部
１３    記憶部
１００  データ移行処理システム
１０１  ノード識別子管理部
１０２  メッセージ処理部
１０３  死活監視部
１０４  ノード情報付与部
１０５  データ抽出部
１０６  データ移行処理部
１０７  データ移行パラメータ管理部
１０８  ノード負荷監視部
２００  抽出データ管理テーブル
３００  データ（サービス対象データ）
４００  ノード識別子管理テーブル（ノード識別子管理情報）
１０００  分散処理システム
【図１】
2014041550.tif 000003
【図２】
2014041550.tif 000004
【図３】
2014041550.tif 000005
【図４】
2014041550.tif 000006
【図５】
2014041550.tif 000007
【図６】
2014041550.tif 000008
【図７】
2014041550.tif 000009
【図８】
2014041550.tif 000010
【図９】
2014041550.tif 000011
【図１０】
2014041550.tif 000012
【図１１】
2014041550.tif 000013