(57)【要約】【課題】クラスタを構成するノードを、そのクラスタ内におけるデータの一貫性を保証した上で離脱させるノード離脱処理システムを提供する。【解決手段】ノード離脱処理システム１００は、ノード離脱処理システム１００内の複数のノード１それぞれが備えるノード識別子管理テーブルに、そのノードが離脱対象のノードであるか否かを示すフラグを設ける。そして、クラスタを構成する各ノード１は、システム保守手段から、ノード離脱開始メッセージを受信すると、離脱対象のノード１についてフラグを設定する。各ノード１は、システム保守手段からデータ移行要求を受信し、フラグが設定されたノード識別子管理テーブルを参照して、離脱対象のノード１が離脱されたものとして移行対象となるデータ（データ移行対象データ）を検出し、データ移行を実行する。【選択図】図１
2014146151.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，［平成25年1月11日検索］，インターネット<ＵＲＬ: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］、［平成25年1月11日検索］、インターネット<ＵＲＬ:http://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf>
【発明の概要】
【発明が解決しようとする課題】
【００１２】
コンシステントハッシュ法によるデータ管理手法は、クラスタを構成するノードの追加や離脱に伴うデータの移行が全データに対する一部のデータに限られるため、クラスタ構成の動的な変更（ノードの追加・離脱）が頻繁に起こるシステムに対して有効である。この特性を活かし、トラヒック変化や管理するデータ量の変化に対して、ノードの追加や離脱を柔軟に行いリソースの利用効率を上げることが可能である。
【００１３】
ここで、コンシステントハッシュ法によるデータ管理手法を用い、図１１に示すような複製データの配置方式を採用する分散システムにおいて、サービス運用者等が保守的な観点からノードを離脱させるケースを考える。なお、保守的な観点とは、分散システムにおいて処理するトラヒックの減少等に伴い余裕が生まれた処理能力を削減する場合やメンテナンス等によりノードを離脱させる場合等である。
従来、分散システムを構成するノードを離脱させる場合においては、システム上に存在するデータ（原本データおよび複製データ）の一貫性を厳密に保証することは現実的に困難であり、データの一貫性が崩れるタイミングを避けることはできないという問題がある。すなわち、ノードの障害発生時と同様に冗長管理された複製データを利用してサービスを継続させることを考えると、ノード離脱後にデータの一貫性が保証できず、処理が失敗するケースが起こる可能性がある。
【００１４】
図１２は、クラスタを構成するノードが離脱する場合において、データの一貫性が保証されないケースを説明するための図である。図１２（ａ）に示す場合には、ノード「Ａ」でデータＸの更新処理が完了し、その後更新されたデータＸをノード「Ｂ」に複製した後、ノード「Ａ」がクラスタを離脱している。この場合、その後のデータＸに関するリクエストは、更新されたデータＸを保存するノード「Ｂ」により処理されるため、データの一貫性が保たれる。
【００１５】
これに対し、図１２（ｂ）に示す場合は、ノード「Ａ」の離脱が、データＸの更新前に実行されることを示す。クラスタを構成するノードの離脱のタイミングには制限がないため、このようなケースが発生し得る。この場合、ノード「Ａ」が更新されたデータをノード「Ｂ」に複製する前にノード「Ａ」が離脱したため、その後にデータＸに関するリクエストがノード「Ｂ」において処理されるときに、ノード「Ｂ」には更新前のデータＸしか存在しないため、データの一貫性が保証されない。
【００１６】
このような背景を鑑みて本発明がなされたのであり、本発明は、クラスタを構成するノードを、そのクラスタ内におけるデータの一貫性を保証した上で離脱させることができるノード離脱処理システムを提供することを課題とする。
【課題を解決するための手段】
【００１７】
前記した課題を解決するため、請求項１に記載の発明は、１つ以上の振り分け装置が振り分けたメッセージを受信する複数のノードにより構成されるクラスタと、前記クラスタを構成する複数のノードの中から離脱対象のノードを決定し、前記クラスタから離脱させる制御を行うシステム保守手段とを備えるノード離脱処理システムであって、前記複数のノードのそれぞれは、クライアントにサービスを提供するためのデータを原本データとして記憶する所有者ノード、または、前記データの複製データを記憶する複製ノードとして機能することにより前記クラスタを構成しており、前記システム保守手段が、前記離脱対象のノードを決定して、前記離脱対象のノードに固有な識別子であるノード識別子を含むノード離脱開始メッセージを生成し、前記決定した離脱対象のノードが離脱したと仮定した場合の新たな前記所有者ノードおよび前記複製ノードに前記データを移行させる処理を要求するデータ移行要求を生成する、ノード離脱制御部を備え、前記複数のノードそれぞれが、前記ノードに固有な識別子であるノード識別子を、前記データと前記所有者ノードおよび前記複製ノードとに対応付ける共に、前記ノード識別子に示されるノードが離脱対象のノードであるか否かを示すフラグを設けたノード識別子管理情報が記憶される記憶部と、前記原本データを記憶する前記所有者ノードのノード識別子および前記複製データを記憶する前記複製ノードのノード識別子を、前記原本データおよび前記複製データそれぞれに、ノード情報として付与するノード情報付与部と、前記システム保守手段から、前記ノード離脱開始メッセージを受信した場合に、前記離脱対象のノードのノード識別子に基づき、前記ノード識別子管理情報における前記離脱対象のノードについての前記フラグを設定する第１のノード識別子管理部と、前記システム保守手段から、前記データ移行要求を受信した場合に、自身が記憶している原本データを、データ移行が必要か否かの判定対象となる判定対象データとして抽出するデータ抽出部と、前記抽出した判定対象データについて、前記フラグが設定されたノード識別子管理情報に基づき、前記離脱対象のノードが離脱されたものとして、前記所有者ノードおよび前記複製ノードを特定し、前記特定した所有者ノードおよび複製ノードそれぞれのノード識別子が、前記ノード情報と比較して一致しない場合に、当該抽出した判定対象データを、前記データ移行が必要なデータを示すデータ移行対象データとして検出し、前記検出したデータ移行対象データを、前記特定した所有者ノードおよび複製ノードに移行するデータ移行処理部と、を備えることを特徴とするノード離脱処理システムとした。
【００１８】
このように、ノード離脱処理システム内の複数のノードそれぞれが備えるノード識別子管理テーブルに、そのノードが離脱対象のノードであるか否かを示すフラグを設ける。そして、クラスタを構成する各ノードは、システム保守手段から、ノード離脱開始メッセージを受信すると、離脱対象のノードについてフラグを設定する。各ノードは、システム保守手段からデータ移行要求を受信し、フラグが設定されたノード識別子管理テーブルを参照して、離脱対象のノードが離脱されたものとして移行対象となるデータ（データ移行対象データ）を検出し、データ移行を実行する。
このようにすることで、ノード離脱処理システムは、クラスタを構成する複数のノードのうちのいずれかを、故障等での離脱ではなくサービス運用者等が保守契機で離脱させる際に、ノード離脱後の適切なデータ配置にデータ（データ移行対象データ）を移行させた後に、離脱対象のノードを離脱させる。よって、クラスタを構成する各ノードおけるデータの一貫性を保証した上で、離脱対象のノードを離脱させることができる。
【００１９】
請求項２に記載の発明は、前記ノード離脱処理システムは、さらに前記１つ以上の振り分け装置を備えており、前記振り分け装置が、前記ノード識別子管理情報が記憶される記憶部と、前記システム保守手段から、前記ノード離脱開始メッセージを受信した場合に、前記離脱対象のノードのノード識別子に基づき、前記ノード識別子管理情報における前記離脱対象のノードについての前記フラグを設定する第２のノード識別子管理部と、前記フラグが設定された前記ノード識別子管理情報に基づき、前記離脱対象のノードが離脱されたものとして、前記メッセージの振り分け先となる前記ノードを決定し、前記クライアントから受信した前記メッセージを前記決定したノードに振り分ける振り分け処理部と、を備えることを特徴とする請求項１に記載のノード離脱処理システムとした。
【００２０】
このようにすることで、ノード離脱処理システムは、クラスタを構成する複数のノードのうちのいずれかを、サービス運用者等が保守契機で離脱させる際に、離脱対象のノードに向けてのクライアントからのメッセージの振り分けを、離脱対象のノードの離脱前に停止することができる。よって、離脱対象のノードにおいて、データが更新されることがないため、クラスタを構成する各ノードおけるデータ一貫性を保証した上で、離脱対象のノードを離脱させることができる。
【００２１】
請求項３に記載の発明は、前記複数のノードそれぞれの前記データ移行処理部が、前記データ移行による前記ノード自身の処理負荷を抑制するように設定されたパラメータに基づく所定のタイミングのときに、前記データ移行対象データの検出処理を実行し、前記パラメータが、前記データ移行を並列で実行できる最大スレッド数を示すデータ移行処理スレッド数、前記データ移行を実行した後の待機時間を示すデータ移行処理実行間隔、前記データ移行対象データの検出処理を連続で実行する個数を示すシミュレーション最大個数、の少なくとも１つであることを特徴とする請求項１または請求項２に記載のノード離脱処理システムとした。
【００２２】
このようにすることで、各ノードは、所定のタイミングでデータ移行処理の対象となるデータ（データ移行対象データ）を検出するための処理を実行し、そこで検出されたデータについて、データ移行処理を実行する。よって、ノードの負荷を抑えながらデータを徐々に移行させることができる。
【００２３】
請求項４に記載の発明は、前記複数のノードそれぞれが、前記ノード自身の処理負荷を監視し、前記処理負荷が所定値を超えた場合に、前記データ移行処理部に処理中断情報を出力するノード負荷監視部を、さらに備え、前記データ移行処理部が、前記処理中断情報を受け取ると、前記データ移行を中断することを特徴とする請求項１ないし請求項３のいずれか１項に記載のノード離脱処理システムとした。
【００２４】
このように、各ノードは、自身の処理負荷を監視することにより、処理負荷が所定値を超えた場合に、データ移行を中断することができる。よって、ノードの処理負荷が所定値を超えた場合のタイミングで、データ移行を中断することができるため、確実にノードの負荷を抑制しながらデータ移行させることができる。
【発明の効果】
【００２５】
本発明によれば、クラスタを構成するノードを、そのクラスタ内におけるデータの一貫性を保証した上で離脱させるノード離脱処理システムを提供することができる。
【図面の簡単な説明】
【００２６】
【図１】本実施形態に係るノード離脱処理システムを含む分散処理システムの全体構成を示す図である。
【図２】本実施形態に係るロードバランサの構成例を示す機能ブロック図である。
【図３】本実施形態に係る振り分け装置の構成例を示す機能ブロック図である。
【図４】本実施形態に係るノード識別子管理テーブル（ノード識別子管理情報）のデータ構成例を示す図である。
【図５】本実施形態に係るノードの構成例を示す機能ブロック図である。
【図６】本実施形態に係るシステム保守手段を備えるノードの構成例を示す機能ブロック図である。
【図７】本実施形態に係る分散処理システムにおけるノード離脱処理の全体の流れを示すフローチャートである。
【図８】本実施形態に係る分散処理システムのノード離脱処理における、システム内の各装置の状況を説明するための図である。
【図９】本実施形態に係るノードのデータ移行処理部が行うデータ移行対象データの検出処理の流れを示すフローチャートである。
【図１０】本実施形態に係るノードのデータ移行パラメータ管理部により設定されるデータ移行処理の所定のタイミングを説明するための図である。
【図１１】コンシステントハッシュ法によるデータ管理手法を説明するための図である。
【図１２】クラスタを構成するノードが離脱する場合において、データの一貫性が保証されないケースを説明するための図である。
【発明を実施するための形態】
【００２７】
次に、本発明を実施するための形態（以下、「本実施形態」と称する。）におけるノード離脱処理システム１００について説明する。
【００２８】
＜分散処理システムの全体構成＞
まず、本実施形態に係るノード離脱処理システム１００を含む分散処理システム１０００の全体構成について説明する。
図１は、本実施形態に係るノード離脱処理システム１００を含む分散処理システム１０００の全体構成を示す図である。
【００２９】
この分散処理システム１０００は、各クライアント２からのメッセージを受け付けるロードバランサ３と、振り分け装置４と、クラスタを構成する複数のノード１とを含んで構成される。ロードバランサ３は、クライアント２からのメッセージを単純なラウンドロビン法等により各振り分け装置４に振り分ける。振り分け装置４は、受信したメッセージを、例えば、コンシステントハッシュ法等に基づき、各ノード１に振り分ける。各ノード１では、メッセージ処理を行い、クライアント２にサービスを提供する。
なお、本実施形態においては、少なくもと１つの振り分け装置４とクラスタを構成する複数のノード１とを含む構成を、ノード離脱処理システム１００として説明する。
【００３０】
図１においては、振り分け装置４とノード１とを別装置として記載したが、同一サーバ上で別々の機能として動作させることも可能である。また、振り分け装置４も、図１に示すように、クラスタ構成をとることができる。さらに、ロードバランサ３が存在せず、クライアント２から任意の振り分け装置４にメッセージを送信することも可能である。
【００３１】
本実施形態では、分散処理システム１０００のデータ管理手法として、ノード１の離脱時時の影響が少ない、コンシステントハッシュ法によるデータ管理手法を例として説明する。ただし、コンシステントハッシュ法に限定されるものではない。また、図１１に示した複製データの配置方式により、コンシステントハッシュ法のＩＤ空間上で右隣（時計回りに次）のノード１に複製データを担当させることとする。
【００３２】
＜処理概要＞
本実施形態に係るノード離脱処理システム１００は、そのノード離脱処理システム１００を構成する複数のノード１のうちのいずれかを、サービス運用者等が保守契機で離脱させる際に、ノード離脱後の適切なデータ配置に該当データ（後記する「データ移行対象データ」）を移行させた後に、離脱対象のノード１を離脱させる。
具体的には、ノード離脱処理システム１００内の振り分け装置４およびノード１が備えるノード識別子管理テーブル４００（後記する図４参照）に、そのノード１が離脱対象のノードであるか否かを示すフラグ４０３を設定する。そして、振り分け装置４は、このフラグ４０３を参照し、離脱対象として設定されたノード１に対しては、メッセージの振り分けを行わない。また、クラスタを構成する各ノード１は、フラグ４０３が設定されたノード識別子管理テーブル４００を参照して、離脱対象のノード１の離脱後の適切なデータ配置に、該当データ（データ移行対象データ）を移行する処理を実行し、データ移行が終了した後に、離脱対象のノード１を実際に離脱させる。
このようにすることで、本実施形態に係るノード離脱処理システム１００は、クラスタを構成する各ノード１おけるデータの一貫性を保証した上で、離脱対象のノード１を離脱させることができる。
【００３３】
＜各装置の構成＞
次に、本実施形態に係る分散処理システム１０００を構成する、ロードバランサ３、振り分け装置４およびノード１について、具体的に説明する。
【００３４】
≪ロードバランサ≫
図２は、本実施形態に係るロードバランサ３の構成例を示す機能ブロック図である。
ロードバランサ３は、クライアント２からのメッセージを各振り分け装置４に振り分ける。また、ロードバランサ３は、各振り分け装置４から受信した情報（データ）をクライアント２に送信する。
【００３５】
このロードバランサ３は、情報の入出力を行う入出力部、制御部、記憶部を備える（図示省略）。そして、記憶部には、各振り分け装置４のＩＰアドレスや、各クライアント２のＩＰアドレス等のアドレス情報が記憶される。
また、制御部は、図２に示す、振り分け装置情報管理部３１および振り分け部３２を含んで構成される。振り分け装置情報管理部３１は、記憶部に記憶された振り分け装置４のアドレス情報（ＩＰアドレス等）を管理する。振り分け部３２は、単純なラウンドロビン法により振り分け装置情報管理部３１で管理している振り分け装置４に対して、クライアントからのメッセージを振り分ける。
【００３６】
≪振り分け装置≫
図３は、本実施形態に係る振り分け装置４の構成例を示す機能ブロック図である。
振り分け装置４は、受信したメッセージを、例えば、コンシステントハッシュ法等に基づき、各ノード１に振り分ける。また、各ノード１から受信した情報（データ）を、ロードバランサ３に送信する。なお、以下の説明においては、図１に示したように、複数の振り分け装置４を備えるものとするが、本実施形態に係るノード離脱処理システム１００は、少なくとも１つの振り分け装置４を備えていればよい。
【００３７】
この振り分け装置４は、情報の入出力を行う入出力部、制御部、記憶部を備える（図示省略）。そして、制御部は、図３に示す、ノード識別子管理部４１および振り分け処理部４２を含んで構成される。また、記憶部には、ノード識別子管理テーブル４００（図３、図４参照）が記憶される。
【００３８】
ノード識別子管理部４１（第２のノード識別子管理部）は、クラスタを構成する各ノード１に関する識別情報をノード識別子管理テーブル４００（ノード識別子管理情報）として管理する。ノード識別子管理部４１は、クラスタへのノード１の追加や離脱が発生した際に、クラスタを構成するノード１に関するノード識別子管理テーブル４００の情報を更新する。
【００３９】
図４は、本実施形態に係るノード識別子管理テーブル４００（ノード識別子管理情報）のデータ構成例を示す図である。図４に示すように、ノード識別子管理テーブル４００は、クラスタを構成する各ノード１のノード識別子４０１、アドレス４０２およびフラグ４０３を含んで構成される。
【００４０】
このノード識別子４０１は、コンシステントハッシュ法のＩＤ空間上でのノードＩＤに対応する。また、コンシステントハッシュ法において仮想ＩＤを用いる場合には、ノード識別子４０１は、仮想ＩＤ毎に割り当てられ、ノード識別子管理テーブル４００に登録される。そして、このノード識別子管理テーブル４００では、例えば、ノード識別子４０１を昇順に並べることにより、コンシステントハッシュ法のＩＤ空間におけるＩＤ（または仮想ＩＤ）を昇順に並べて管理することができる。つまり、ノード識別子管理テーブル４００において、ノード識別子を昇順に並べたときの次のノード１が、ＩＤ空間上での右隣（時計回りに次）のノード１となる。
例えば、図４においては、コンシステントハッシュ法のＩＤ空間に基づくデータ識別子が「０」から「５６」であるデータについては、同図の第１行目に指すノード（ノード識別子「５６」、アドレス「１９２．１６８．０．２４」であるノード）が「所有者ノード」として担当し、次の第２行目が指すノード（ノード識別子「１７２」、アドレス「１９２．１６８．１．２５」）がバディとして担当することを示す。同様に、データ識別子が「５６」に１を加えた「５７」から「１７２」であるデータについては、第２行目に指すノードが「所有者ノード」として担当し、次の第３行目が指すノードがバディとして担当することを示す。
このようにして、このノード識別子管理テーブル４００に基づき、データとその所有者ノードとバディとが対応付けられる。
なお、このノード識別子４０１は、ノード識別子管理部４１が各ノード１に対して付与することもできるし、他のノード１（後記する「システム保守手段５０を備えるノード１Ａ」）や外部装置（例えば、ネットワーク管理装置等）が生成したノード識別子管理テーブル４００を受信して格納することも可能である。ただし、ノード離脱処理システム１００を構成する各振り分け装置４および各ノード１は、他のノード１（システム保守手段５０を備えるノード１Ａ）や外部装置（ネットワーク管理装置等）との間で、ノード１の離脱や追加等の情報を送受信することにより、常に、同一内容のノード識別子管理テーブル４００を備えるようにする。
【００４１】
また、このノード識別子管理テーブル４００には、ノード識別子４０１毎に、そのノード１が離脱対象のノードであるか否かを示すフラグ４０３が設けられる（図４参照）。ノード識別子管理部４１は、他のノード１（システム保守手段５０を備えるノード１Ａ（図６参照））等から、クラスタから離脱させるノード１（離脱対象のノード１）の識別情報を含むノード離脱開始メッセージを受信した場合に、その離脱対象のノード１のフラグ４０３を「０」から「１」に変更する。
なお、このフラグ４０３についても、ノード識別子管理部４１が各ノード１に対して付与することもできるし、他のノード１（システム保守手段５０を備えるノード１Ａ）や外部装置（ネットワーク管理装置等）で生成されたフラグ４０３が付されたノード識別子管理テーブル４００を受信して格納することも可能である。
【００４２】
また、このノード識別子管理部１０１は、他のノード１（システム保守手段５０を備えるノード１Ａ）や外部装置（ネットワーク管理装置等）から、離脱させるノード１の識別情報（例えば、ノード識別子４０１）を含むノード離脱要求を受信した場合に、ノード識別子管理テーブル４００（図４参照）において、その離脱させるノード１の情報（ノード識別子４０１、アドレス４０２およびフラグ４０３）を含むレコードを削除する。
【００４３】
図３に戻り、振り分け処理部４２は、ロードバランサ３等より受信したメッセージから、そのメッセージの処理対象となるデータのkey（データkey）を抽出する。そして、振り分け処理部４２は、その抽出したデータkeyを用いて、ノード識別子管理テーブル４００を参照し、コンシステントハッシュ法に従い、そのメッセージをノード１に振り分ける。
ただし、振り分け処理部４２は、コンシステントハッシュ法に従い振り分け先を決定したノード１が、ノード識別子管理テーブル４００のフラグ４０３が「１」の場合、そのノード１へはメッセージの振り分けを行わない。この場合、振り分け処理部４２は、ノード識別子４０１を昇順に並べた次のノード１のフラグ４０３を順に確認し、つまり、コンシステントハッシュ法のＩＤ空間上での右隣のノード１の状態を確認し、フラグ４０３が「０」のノード１が見つかった時点で、そのノード１に対してメッセージの振り分けを行う。
このようにすることにより、離脱対象のノード１に向けての、クライアント２からの新たなメッセージの送信を行わないようにすることができる。
【００４４】
≪ノード≫
次に、本実施形態に係るノード離脱処理システム１００を構成するノード１の構成例について、具体的に説明する。
図５は、本実施形態に係るノード１の構成例を示す機能ブロック図である。
ノード１は、図１に示したように、各振り分け装置４と通信可能に接続されると共に、クラスタを構成する自身以外の他のノード１とも通信可能に接続される。そして、クライアント２からのメッセージを受信し、サービスを提供する。また、このノード１は、クラスタを構成するいずれかのノード１を離脱させる際に、そのノード１が備えるデータのうち、移行が必要なデータを抽出して、データ移行処理を実行する。
このノード１は、図５に示すように、制御部１０と、入出力部１１と、メモリ部１２と、記憶部１３とを含んで構成される。
【００４５】
入出力部１１は、振り分け装置４や、自身以外の他のノード１との間の情報の入出力を行う。また、この入出力部１１は、通信回線を介して情報の送受信を行う通信インタフェースと、不図示のキーボード等の入力手段やモニタ等の出力手段等との間で入出力を行う入出力インタフェースとから構成される。
【００４６】
制御部１０は、ノード１全体の制御を司り、ノード識別子管理部１０１（第１のノード識別子管理部）、メッセージ処理部１０２、ノード情報付与部１０３、データ抽出部１０４、データ移行処理部１０５およびデータ移行パラメータ管理部１０６を含んで構成される。なお、この制御部１０は、例えば、記憶部１３に格納されたプログラムをＣＰＵ（Central Processing Unit）がメモリ部１２であるＲＡＭ（Random Access Memory）に展開し実行することで実現される。
なお、ノード識別子管理部１０１（第１のノード識別子管理部）は、図３の振り分け装置４で説明したノード識別子管理部４１（第２のノード識別子管理部）と同様の処理を実行する機能を備えるため、ここでの説明を省略する。
【００４７】
メッセージ処理部１０２は、振り分け装置４から振り分けられたメッセージを受信し、そのメッセージの処理を実行し、処理結果をクライアント２に返信することにより、サービスを提供する。同時に、メッセージ処理部１０２は、他のノード１、ここでは、ノード識別子４０１（図４参照）を昇順に並べたときの次のノード１（ＩＤ空間での右隣のノード）にデータの複製を行うことにより、データの冗長化を実現する。また、メッセージ処理部１０２は、複製データを複数持つ場合には、さらに他のノード１、ここでは、ノード識別子４０１を昇順に並べたときのさらに次のノード１（ＩＤ空間での２つ右隣のノード）に、データの複製を行う。ただし、メッセージ処理部１０２は、ノード識別子管理テーブル４００（図４参照）のフラグ４０３が「１」のノード１（離脱対象のノード１）に対してはデータの複製を行わず、ノード識別子４０１を昇順に並べたときの当該ノード１の次のノード１をデータの複製先とする。また、メッセージ処理部１０２は、メッセージの処理に必要なデータをそのノード１自身が保持していなかった場合には、他のノード１に要求すること等により、そのデータを取得することが可能である。
なお、メッセージ処理部１０２は、離脱対象のノード１に関するデータの移行処理が実行される以前に、そのデータ移行の対象となるデータ（後記する「データ移行対象データ」）に関するメッセージを受信したときには、そのメッセージの処理を実行すると共に、そのデータのデータ移行処理を実行する。
【００４８】
ノード情報付与部１０３は、各データに、各データのデータ識別子に対応づけてノード情報を付与する。なお、ノード情報とは、原本データを保持しているノード１（所有者ノード）のノード識別子と複製データを保持しているノード１（バディ：複製ノード）のノード識別子の情報である。ノード情報付与部１０３は、データ移行処理部１０５が、データ移行処理を実行する際に、ノード情報を確認し、ノード１の離脱等が発生してノード情報に変更が必要な場合には、新たなノード情報をそのデータに付与する。よって、ノード情報付与部１０３は、新規にデータを登録する際と、ノード１の離脱等によりデータ移行処理を実行する際に、対象となるデータに対しノード情報を付与する。
【００４９】
データ抽出部１０４は、他のノード１（システム保守手段５０を備えるノード１Ａ）や外部装置（ネットワーク管理装置等）等から保守観点のノード離脱に伴うデータ移行要求（後記する「データ移行開始コマンド」）を受け付けると、そのノード１自身が原本として管理しているデータ（原本データ）を、データ移行処理が必要か否かの判定対象となるデータ（以下、「判定対象データ」と称する。）として抽出し、その抽出したデータのデータ識別子を、抽出データ管理テーブル２００に格納する。
【００５０】
データ移行処理部１０５は、データ移行パラメータ管理部１０６により設定されるパラメータに基づく所定のタイミングで、データ抽出部１０４により抽出され抽出データ管理テーブル２００に格納された判定対象データについて、ノード識別子管理テーブル４００（フラグ４０３に「１」が設定された、つまり、離脱対象のノード１が設定された情報を含むノード識別子管理テーブル４００）に基づき、コンシステントハッシュ法等の予め定められたデータ管理手法に従った場合の所有者ノードとバディとを特定する（以下、この処理を「シミュレーション」と称す。）。そして、データ移行処理部１０５は、このシミュレーション結果や、このシミュレーション結果と各データ（判定対象データ）に付与されているノード情報と比較することにより、所有者ノードの識別子およびバディの識別子が一致（完全一致）しないデータを、データ移行処理の対象となるデータ（以下、「データ移行対象データ」と称する。）として検出し、データ移行処理を実行する。なお、データ移行対象データの検出処理については、後記する図９において詳細に説明する。
【００５１】
また、データ移行処理部１０５は、データ移行の負荷が一度に集中して通常の処理の妨げになり、サービス品質の低下を招かないように、負荷を調整しながらデータ移行処理を実行する。具体的には、データ移行パラメータ管理部１０６により負荷調整のためのパラメータが設定され、データ移行処理部１０５は、そのパラメータに設定された値に従い、データ移行処理を実行する。
【００５２】
データ移行パラメータ管理部１０６は、データ移行処理部１０５がデータ移行処理を実行する所定のタイミングを、１つ以上のパラメータを用いて設定する。このデータ移行パラメータ管理部１０６により、データ移行処理の実行タイミングが調整されることで、データ移行処理の負荷が一度に集中して通常の処理を妨げサービス品質の低下を招かないように負荷を調整しながら、データ移行処理を実行できる。
【００５３】
このデータ移行パラメータ管理部１０６に設定されるパラメータは、例えば、データ移行処理スレッド数、データ移行処理実行間隔、シミュレーション最大個数である。
データ移行処理スレッド数とは、データ移行処理を並列で実行できる最大スレッド数である。このデータ移行処理スレッド数に大きな値を設定すると、データ移行処理にかかる時間を短縮することができるが、ノード１の処理負荷は大きくなる。これに対し、データ移行処理スレッド数に小さな値を設定すると、データ移行処理にかかる時間は増加するが、ノード１の処理負荷は小さくなる。
データ移行処理実行間隔とは、各スレッドで、データ移行処理部１０５がデータ移行対象データの検出処理（図９参照）を実行した結果、データ移行対象データが検出され、データ移行処理部１０５が、そのデータ移行処理を実行した後に待機する時間を指す。
シミュレーション最大個数とは、各スレッドが前記したシミュレーション（フラグ４０３に「１」が設定された、つまり、離脱対象のノード１が設定されたノード識別子管理テーブル４００（図４参照）に基づく、所有者ノードとバディの特定）を含むデータ移行対象データの検出処理を連続で実行する個数を指す。データ移行処理部１０５は、データ移行対象データの検出処理を連続で実行した後に、所定の時間待機し、その後、再びシミュレーションを含むデータ移行対象データの検出処理を開始する。
このシミュレーション最大個数を少なく設定する、または、データ移行処理実行間隔を長く設定することで、ノード１は、処理負荷を抑えながら徐々にデータ移行処理を実行することが可能となる。
なお、このデータ移行処理スレッド数、データ移行処理実行間隔、シミュレーション最大個数の各パラメータは、データ移行パラメータ管理部１０６により、すべて設定されてもよいし、いずれか１つでもよいし、各パラメータを任意に組み合わせて設定されてもよい。
また、このデータ移行パラメータ管理部１０６により設定されたパラメータにより調整される所定のタイミングでのデータ移行処理の詳細については、図１０を参照して後記する。
【００５４】
なお、本実施形態に係るノード１の変形例として、制御部１０にノード負荷監視部を備えるようにしてもよい。ノード負荷監視部は、ノード１自身の処理負荷（例えば、ＣＰＵ使用率、メモリ使用率等）を監視し、その処理負荷に対し予め設定された所定値を超えた場合に、データ移行処理部１０５に処理中断情報を出力することにより、データ移行処理部１０５によるデータ移行処理を中断させる。
このようにすることで、データ移行パラメータ管理部１０６で設定されたパラメータに基づき、所定のタイミングでデータ移行処理部１０５がデータ移行処理を実行している場合であっても、何らかの理由（例えば、クライアント２から大量のメッセージを受信した場合等）で、ノード１の処理負荷が所定値を超えた場合にデータ移行処理を中断し、ノード１の処理負荷を抑制することができる。
【００５５】
また、ノード１の制御部１０が、データ移行パラメータ管理部１０６を備えず、ノード負荷監視部を備える構成にしてもよい。この場合、データ移行処理部１０５は、抽出データ管理テーブル２００に格納された判定対象データについて、直ちに、データ移行対象データの検出処理（図９参照）を実行し、データ移行対象データが検出された場合には、そのデータのデータ移行処理を実行する。
そして、ノード負荷監視部は、ノード１自身の処理負荷（例えば、ＣＰＵ使用率、メモリ使用率等）を監視し、その処理負荷に対し予め設定された所定値を超えた場合に、データ移行処理部１０５に処理中断情報を出力することにより、データ移行処理部１０５によるデータ移行処理を中断させる。
このようにすることで、ノード１は、自身の処理負荷が所定値を超えた場合に、データ移行処理を中断する。よって、ノード１は、自身の処理負荷を直接的に監視し、処理負荷が所定値以上にならないように抑制した上で、データ移行処理を実行することができる。
【００５６】
図５に戻り、メモリ部１２は、ＲＡＭ等の一次記憶装置からなり、制御部１０によるデータ処理に必要な情報を一時的に記憶している。なお、このメモリ部１２には、データ抽出部１０４が抽出した判定対象データのデータ識別子を格納する前記した抽出データ管理テーブル２００が記憶される。
【００５７】
記憶部１３は、ハードディスクやフラッシュメモリ等の記憶装置からなり、サービスの対象となる原本データや複製データを含むデータ３００や、前記したノード識別子管理テーブル４００（図４参照）等が記憶される。このノード識別子管理テーブル４００は、図３に示した振り分け装置４に記憶されるノード識別子管理テーブル４００と同様の情報を記憶するため、その説明を省略する。また、この記憶部１３には、データ移行パラメータ管理部１０６により設定される各パラメータの値（不図示）等が記憶される。
なお、データ３００の各データには、そのデータのデータ識別子、所有者ノードのノード識別子および、バディのノード識別子が含まれる。
【００５８】
≪システム保守手段を備えるノード≫
次に、本実施形態に係るシステム保守手段５０を備えるノード１Ａについて説明する。
以下においては、クラスタを構成する複数のノード１の中から選定されたあるノード１（前記した他のノード１）に、システム保守手段５０の機能が組み入れられた例として説明する。しかしながら、このシステム保守手段５０は、外部装置（例えば、ネットワーク管理装置等）に組み入れられてもよく、ネットワーク内にシステム保守手段５０を含む独立した装置（システム保守装置）として設定されてもよい。
なお、クラスタを構成する複数のノード１の中から、このシステム保守手段５０を備えるノード１Ａを選定する処理は、例えば、ノード識別子管理テーブル４００（図４参照）のノード識別子４０１を昇順に並べた場合の値の小さい順でもよいし、ランダム等でもよい。
【００５９】
図６は、本実施形態に係るシステム保守手段５０を備えるノード１Ａの構成例を示す機能ブロック図である。システム保守手段５０以外の構成は、図５に示したノード１と同様であるので、その説明を省略する。
【００６０】
システム保守手段５０は、サービス運用者等が保守契機でクラスタ内のノード１を離脱させる際に、ノード離脱処理システム１００内の各振り分け装置４及び各ノード１が実行するノード離脱の処理に関する全体的な制御を司る。このシステム保守手段５０は、ノード離脱制御部５１を備える。
【００６１】
ノード離脱制御部５１は、各ノード１の処理負荷やネットワーク内のトラヒック量等の減少に基づき、保守的な観点からノード１を離脱させる必要が発生した場合に、離脱対象となるノード１を決定する。この決定は、例えば、各ノード１の処理能力が同等な場合、ランダムに離脱対象となるノード１を決定する。また、メンテナンス等によりノード１を離脱させる場合に、所定の時期や各ノード１について予め決められた順番で、離脱対象となるノード１を決定する。さらに、ノード離脱制御部５１は、ノード１Ａの入出力部１１から、サービス運用者等が指定した離脱対象となるノード１の情報を取得して、決定するようにしてもよい。
【００６２】
そして、ノード離脱制御部５１は、離脱対象となるノード１の識別情報（例えば、ノード識別子４０１）が付されたノード離脱開始メッセージを生成し、各振り分け装置４および各ノード１に送信する。なお、各振り分け装置４のノード識別子管理部４１および各ノード１のノード識別子管理部１０１は、このノード離脱開始メッセージを受信して、自身が記憶するノード識別子管理テーブル４００（図４参照）の該当するノード１のフラグ４０３を「０」から「１」に変更する。
【００６３】
また、ノード離脱制御部５１は、各振り分け装置４および各ノード１のすべてから、ノード識別子管理テーブル４００のフラグ４０３の変更が完了した旨の応答メッセージを受信すると、各ノード１に対して、データ移行開始メッセージ（データ移行要求）を送信する。これにより、各ノード１のデータ抽出部１０４が、判定対象データの抽出処理を開始する。
【００６４】
そして、ノード離脱制御部５１は、クラスタを構成するすべてのノード１からデータ移行完了メッセージを受信すると、離脱させるノード１の識別情報（例えば、ノード識別子４０１）を含むノード離脱要求を生成し、各振り分け装置４および各ノード１に送信する。
【００６５】
このシステム保守手段５０は、さらに、振り分け装置離脱制御部（不図示）を備えるようにしてもよい。振り分け装置離脱制御部は、保守的な観点から振り分け装置４を離脱させる必要が発生した場合や、前記した離脱対象となるノード１を決定した場合等に、離脱対象となる振り分け装置４を決定する。この決定は、離脱対象となるノード１の決定の場合と同様に、処理性能が同等の場合はランダムでもよいし、メンテナンス順、サービス運用者等による指定等により行われる。振り分け装置離脱制御部は、離脱対象となる振り分け装置４の識別情報が付された振り分け装置削除要求を生成し、ロードバランサ３に送信する。
【００６６】
このようにすることにより、保守的な観点からノード１を離脱させたい場合に、併せて、振り分け装置４も離脱させることができる。
【００６７】
＜処理の流れ＞
次に、本実施形態に係るノード離脱処理システム１００を含む分散処理システム１０００における、処理の流れについて説明する。
≪ノード離脱処理の全体の流れ≫
図７は、本実施形態に係る分散処理システム１０００におけるノード離脱処理の全体の流れを示すフローチャートである。
また、図８は、本実施形態に係る分散処理システム１０００のノード離脱処理における、システム内の各装置の状況を説明するための図である。
なお、本実施形態に係る分散処理システム１０００においては、トラヒック等が減少し、保守的な観点からノード１を離脱させる場合、振り分け装置４についても同様にリソースに余裕が生じている状況が想定されることから、以下に説明する処理においては、ノード離脱と同時に振り分け装置４も離脱させるものとして説明する。ただし、本発明において、振り分け装置４の離脱は必須の処理ではない。
また、クラスタを構成するノード１のうちの１つがシステム保守手段５０を備えるノード１Ａであるものとして説明する。
【００６８】
まず、システム保守手段５０を備えるノード１Ａが、離脱対象となる振り分け装置４およびノード１を決定する（ステップＳ１０）。なお、図８（ａ）は、振り分け装置４のうちの１つと、ノード１のうちの１つとが離脱対象として決定されたことを示している。
【００６９】
次に、ロードバランサ３において、メッセージの振り分け対象から、離脱させる振り分け装置４を削除する（ステップＳ１１）。具体的には、システム保守手段５０を備えるノード１Ａが、離脱させる振り分け装置４の識別情報を含む振り分け装置削除要求を、振り分け装置４を介してロードバランサ３に送信する。振り分け装置削除要求を受信したロードバランサ３の振り分け装置情報管理部３１は、その振り分け装置削除要求に付された離脱させる振り分け装置４の識別情報に基づき、その振り分け装置４のアドレス情報（ＩＰアドレス等）を削除する。こうすることにより、ロードバランサ３から、離脱される振り分け装置４へのメッセージの振り分けが停止される（図８（ｂ）参照）。
【００７０】
続いて、各振り分け装置４および各ノード１は、システム保守手段５０を備えるノード１Ａから、ステップＳ１０で決定した離脱対象となるノード１の識別情報が付されたノード離脱開始メッセージを受信する。そして、各振り分け装置４のノード識別子管理部４１は、自身の記憶部に記憶されたノード識別子管理テーブル４００の離脱対象となるノード１のフラグ４０３を、「０」から「１」に変更する。また、各ノード１のノード識別子管理部１０１は、自身の記憶部１３に記憶されたノード識別子管理テーブル４００の離脱対象となるノード１のフラグ４０３を、「０」から「１」に変更する（ステップＳ１２）。なお、各振り分け装置４および各ノード１は、自身のノード識別子管理テーブル４００のフラグ４０３の変更が完了した旨の応答メッセージを、システム保守手段５０を備えるノード１Ａに返信する。
このステップＳ１２の処理により、各振り分け装置４のメッセージの振り分け先から、離脱対象となるノード１が外れ（図８（ｃ）参照）、さらに、各ノード１のデータの複製先からも、離脱対象となるノード１が外れることとなる。
【００７１】
振り分け装置４およびノード１のすべてから応答メッセージを受信すると、システム保守手段５０を備えるノード１Ａは、各ノード１に対して、データ移行開始メッセージ（データ移行要求）を送信する。
各ノード１は、データ移行開始メッセージを受信すると、データ抽出部１０４が、そのノード１自身が原本として管理しているデータ（原本データ）を、データ移行処理が必要か否かの判定対象となるデータ（判定対象データ）として抽出し、その抽出したデータのデータ識別子を、抽出データ管理テーブル２００に格納する（ステップＳ１３）。
【００７２】
次に、各ノード１のデータ移行処理部１０５は、データ移行パラメータ管理部１０６により設定された、所定のタイミングであるか否かを判定する（ステップＳ１４）。データ移行処理部１０５は、所定のタイミングであれば（ステップＳ１４→Ｙｅｓ）、次のステップＳ１５に進み、所定のタイミングでなければ（ステップＳ１４→Ｎｏ）、所定のタイミングになるまで待機する。
なお、データ移行パラメータ管理部１０６により設定される所定のタイミングについては、図１０において説明する。
【００７３】
ステップＳ１５において、データ移行処理部１０５は、抽出データ管理テーブル２００を参照し、判定対象データ（具体的には判定対象データのデータ識別子）を１つ抽出する。
【００７４】
次に、データ移行処理部１０５は、ステップＳ１５で抽出した判定対象データが、データ移行処理の対象となるデータ（データ移行対象データ）か否かを検出する処理（データ移行対象データの検出処理）を実行する（ステップＳ１６）。なお、このデータ移行対象データの検出処理の詳細は、図９において説明する。
【００７５】
続いて、データ移行処理部１０５は、ステップＳ１６により、データ移行対象データが検出されたか否かを判定する（ステップＳ１７）。ここで、データ移行処理部１０５は、データ移行対象データが検出された場合には（ステップＳ１７→Ｙｅｓ）、ステップＳ１８に進み、検出されなかった場合には（ステップＳ１７→Ｎｏ）、ステップＳ１９に進む。
【００７６】
ステップＳ１８において、データ移行処理部１０５は、データ移行処理を実行する。なお、このデータ移行処理部１０５によるデータ移行処理は、ノード情報付与部１０３が、移行するデータに付与されたノード情報を、ステップＳ１６のデータ移行対象データの検出処理でシミュレーション（フラグ４０３が変更されたノード識別子管理テーブル４００（図４参照）に基づく、所有者ノードとバディの特定）した所有者ノードの識別子とバディの識別子とに変更してから実行される。図８（ｄ）は、離脱対象となるノード１に記憶された原本データおよび複製データがデータ移行の処理中であることを示している。
【００７７】
次に、ステップＳ１９において、データ移行処理部１０５は、抽出データ管理テーブル２００に格納されたすべての判定対象データ（データ識別子）を処理したか否かを判定する。ここで、データ移行処理部１０５は、抽出データ管理テーブル２００に、まだ処理していない判定対象データ（データ識別子）が格納されている場合には（ステップＳ１９→Ｎｏ）、ステップＳ１４に戻り処理を続ける。一方、データ移行処理部１０５は、抽出データ管理テーブル２００に格納されたすべての判定対象データ（データ識別子）の処理を終えている場合には（ステップＳ１９→Ｙｅｓ）、データ移行処理が完了したことを示すデータ移行完了メッセージを生成し、システム保守手段５０を備えるノード１Ａに送信する（ステップＳ２０）。
【００７８】
システム保守手段５０を備えるノード１Ａは、すべてのノード１からデータ移行完了メッセージを受信すると、離脱させるノード１の識別情報を含むノード離脱要求を、各振り分け装置４および各ノード１に送信する。振り分け装置４のノード識別子管理部４１は、ノード離脱要求を受信すると、自身の記憶部に記憶されたノード識別子管理テーブル４００において、離脱させるノード１の情報（レコード）を削除する。また、ノード１のノード識別子管理部１０１は、自身の記憶部１３にされたノード識別子管理テーブル４００において、離脱させるノード１の情報（レコード）を削除する。この処理により離脱対象となるノード１を離脱させる（ステップＳ２１）。
なお、図８（ｅ）は、データの移行処理が終了し、離脱対象のノード１がクラスタから離脱された状況を示している。
【００７９】
なお、ノード１のデータ移行処理部１０５が、この図７のステップＳ１４〜Ｓ２１によるデータ移行処理を徐々に実行している間においても、そのノード１はクライアント２からメッセージを受信し、メッセージ処理部１０２がそのメッセージに対する処理を実行している。メッセージ処理部１０２は、受信したメッセージについての処理を実行すると共に、そのメッセージの対象となるデータが、データ移行対象データか否かを、そのデータに付されたノード情報を参照して判定する。具体的には、そのノード情報中の所有者ノードとバディのいずれかが、各々自ノード、ＩＤ空間上の右隣ノードと異なれば、データ移行対象データと判定する。そして、メッセージ処理部１０２は、当該データがデータ移行対象データである場合には、そのデータのデータ移行処理を実行する。
このようにすることで、ノード１は、メッセージを受信したことにより、それ以降も利用可能性が高いと予測されるデータについては、そのデータに関するメッセージ処理を実行すると共に、データ移行処理を行い、データの適正な配置を迅速に達成することができる。
【００８０】
≪データ移行対象データの検出処理≫
次に、図７のステップＳ１６において、ノード１のデータ移行処理部１０５が実行するデータ移行対象データの検出処理について詳細に説明する。
図９は、本実施形態に係るノード１のデータ移行処理部１０５が行うデータ移行対象データの検出処理の流れを示すフローチャートである。
【００８１】
まず、ノード１のデータ移行処理部１０５は、抽出データ管理テーブル２００から抽出した判定対象データ（そのノード１自身が原本として管理しているデータ）について、シミュレーション（図９において、「Ａ処理」と記載）を実行する（ステップＳ３０）。具体的には、データ移行処理部１０５は、抽出した判定対象データについて、フラグ４０３が変更されたノード識別子管理テーブル４００に基づき、コンシステントハッシュ法等の予め定められたデータ管理手法に従った場合の所有者ノードとバディとを特定する。
【００８２】
次に、データ移行処理部１０５は、抽出データ管理テーブル２００から抽出した判定対象データに付されたノード情報（所有者ノードの識別子とバディの識別子）を抽出（図９において、「Ｂ処理」と記載）する（ステップＳ３１）。
【００８３】
続いて、シミュレーション（Ａ処理）の結果、自ノードが所有者ノードか否かを判定する（ステップＳ３２）。ここで、シミュレーション（Ａ処理）の結果、自ノードが所有者ノードである場合には（ステップＳ３２→Ｙｅｓ）、次のステップＳ３３に進み、一方、自ノードが所有者ノードでない場合には（ステップＳ３２→Ｎｏ）、そのデータ（判定対象データ）を、データ移行処理の対象となるデータ（データ移行対象データ）として決定する（図９において、「移行対象」と記載）。
【００８４】
ステップＳ３３において、データ移行処理部１０５は、シミュレーション（Ａ処理）の結果とノード情報抽出（Ｂ処理）の結果とでバディが一致するか否かを判定する。ここで、バディが一致する場合には（ステップＳ３３→Ｙｅｓ）、そのデータ（判定対象データ）は、データ移行の必要のないデータとなる（図９において、「移行対象外」と記載）。一方、バディが一致しない場合には（ステップＳ３３→Ｎｏ）、そのデータ（判定対象データ）を、データ移行処理の対象となるデータ（データ移行対象データ）として決定する。つまり、所有者ノードが一致していても、バディが一致していないため、データ移行対象データとなる。
【００８５】
このようにすることで、データ移行処理部１０５は、抽出データ管理テーブル２００に抽出された判定対象データそれぞれについて、データ移行処理を実行すべきか否かを判定し、データ移行対象データを検出することができる。
【００８６】
≪所定のタイミングでのデータ移行処理≫
次に、図１０を参照して、データ移行パラメータ管理部１０６により設定されるパラメータに基づく、データ移行処理の所定のタイミングについて説明する。
図１０においては、データ移行パラメータ管理部１０６に設定されるパラメータの例として、データ移行処理スレッド数、データ移行処理実行間隔、および、シミュレーション最大個数が設定されている例を示す。
【００８７】
図１０は、データ移行処理スレッド数（符号Ｐ１）が「３」に設定されている例を示している。
また、各スレッドにおいて、データ移行処理部１０５が、抽出データ管理テーブル２００から判定対象データを取得すると（ステップＳ４０）、データ移行対象データの検出処理（図９参照）を実行し（ステップＳ４１）、データ移行対象データが検出された場合には、そのままデータ移行処理を実行する（ステップＳ４２）。
【００８８】
ここで、データ移行対象データについて、ステップＳ４２において、データ移行処理を実行した後、データ移行処理部１０５は、データ移行処理実行間隔（符号Ｐ２）が設定されているため、所定の時間、次の判定対象データの取得処理（ステップＳ４０）を行わずに待機する。
【００８９】
また、図１０のスレッド「１」に示すように、シミュレーション最大個数（符号Ｐ３）のパラメータが「５」に設定されている場合には、データ移行処理部１０５は、抽出データ管理テーブル２００から判定対象データを取得し、データ移行対象データの検出処理を５回連続して実行する。そして、データ移行処理部１０５は、シミュレーション最大個数（ここでは「５」回）のデータ移行対象データの検出処理を行っても、データ移行対象データが検出されなかったときには、所定の時間待機する。
【００９０】
このようにすることで、各パラメータにより設定された所定のタイミングでデータ移行対象データの検出処理を実行し、データ移行対象データが検出された場合に、データ移行処理を実行することができる。よって、クラスタを構成するノード１が離脱した直後において、他の既存のノード１は、データ移行処理を一時に実行しないため、ノード１が処理負荷を抑えながら徐々にデータ移行処理を実行することができる。
【００９１】
以上説明したように、本実施形態に係るノード離脱処理システム１００によれば、クラスタを構成する複数のノード１のうちのいずれかを、保守契機で離脱させる際に、ノード離脱後の適切なデータ配置に該当データの移行させた後に、離脱対象のノード１を離脱させる。よって、本実施形態に係るノード離脱処理システム１００は、各ノード１おけるデータの一貫性を保証した上で、離脱対象のノード１を離脱させることができる。
【符号の説明】
【００９２】
１      ノード
１Ａ    システム保守手段を備えるノード
２      クライアント
３      ロードバランサ
４      振り分け装置
１０    制御部
１１    入出力部
１２    メモリ部
１３    記憶部
３１    振り分け装置情報管理部
３２    振り分け部
４１    ノード識別子管理部（第２のノード識別子管理部）
４２    振り分け処理部
５０    システム保守手段
５１    ノード離脱制御部
１００  ノード離脱処理システム
１０１  ノード識別子管理部（第１のノード識別子管理部）
１０２  メッセージ処理部
１０３  ノード情報付与部
１０４  データ抽出部
１０５  データ移行処理部
１０６  データ移行パラメータ管理部
２００  抽出データ管理テーブル
３００  データ（サービス対象データ）
４００  ノード識別子管理テーブル（ノード識別子管理情報）
１０００  分散処理システム
【図１】
2014146151.tif 000003
【図２】
2014146151.tif 000004
【図３】
2014146151.tif 000005
【図４】
2014146151.tif 000006
【図５】
2014146151.tif 000007
【図６】
2014146151.tif 000008
【図７】
2014146151.tif 000009
【図８】
2014146151.tif 000010
【図９】
2014146151.tif 000011
【図１０】
2014146151.tif 000012
【図１１】
2014146151.tif 000013
【図１２】
2014146151.tif 000014