(57)【要約】      （修正有）【課題】クラスタメンバが離脱したときに冗長化数が少なくなるようなデータ領域や期間を低減する。【解決手段】クラスタシステムにおいて、ディスパッチャ２０２は、ＩＤ空間上におけるデータの担当領域を示す情報をプロセッサ毎に記憶する記憶部と、クラスタを構成するプロセッサが離脱した場合に直ちに、記憶された担当領域を示す情報を参照して、ＩＤ空間上におけるデータの担当領域を組み替えることでクラスタを再構成し、変更を自身以外のディスパッチャに通知する保存情報管理部と、を備える。プロセッサ２０３は、クラスタが再構成される度に、ＩＤ空間上におけるデータの担当領域を示す情報をローカルのストレージに記録する担当領域更新記録部と、ローカルのストレージに保存するデータが更新される度に、データが更新されたことを示す情報と、担当領域を示す情報と、をローカルのストレージに記録するデータ更新記録部と、を備える。【選択図】図２
2014164502.tif 000002
【特許請求の範囲】
【請求項１】
入力情報に基づき、ストレージに対してデータの保存を含む処理を実行する複数のプロセッサと、前記複数のプロセッサ毎に設けられた複数の前記ストレージと、前記入力情報を前記複数のプロセッサのいずれかに振り分ける複数のディスパッチャとを備え、前記入力情報に対して１つのクラスタとして分散処理を行うと共に、前記複数のプロセッサそれぞれが当該プロセッサ用のローカルのストレージおよび前記クラスタ内のリモートのストレージにデータを冗長化して記憶するクラスタシステムであって、
前記ディスパッチャは、
前記入力情報のＩＤに対応したＩＤ空間上におけるデータの担当領域を示す情報を前記複数のプロセッサ毎に記憶する記憶部と、
前記クラスタを構成する前記複数のプロセッサのいずれかが離脱した場合に直ちに、前記記憶部に記憶された前記担当領域を示す情報を参照して、前記ＩＤ空間上におけるデータの担当領域を組み替えることで前記クラスタを再構成し、変更を自身以外の前記ディスパッチャに通知する保存情報管理部と、を備え、
前記プロセッサは、
前記クラスタが再構成される度に、前記ＩＤ空間上におけるデータの担当領域を示す情報を、当該プロセッサ用のローカルのストレージに記録する担当領域更新記録部と、
前記ローカルのストレージに保存するデータが更新される度に、データが更新されたことを示す情報と、前記担当領域を示す情報と、を前記ローカルのストレージに記録するデータ更新記録部と、を備えることを特徴とするクラスタシステム。
【請求項２】
前記プロセッサにおいて、
前記担当領域更新記録部は、前記クラスタが再構成された時刻を前記ローカルのストレージにさらに記録し、
前記データ更新記録部は、前記ローカルのストレージに保存するデータが更新された時刻を前記ローカルのストレージにさらに記録することを特徴とする請求項１に記載のクラスタシステム。
【請求項３】
前記プロセッサは、前記ローカルのストレージに記録されている、前記担当領域を示す情報を前記ディスパッチャに通知し、前記離脱したプロセッサであって復帰する前記プロセッサとその代理を務めていたプロセッサとの間における通信処理を行う復帰処理部をさらに備えることを特徴とする請求項２に記載のクラスタシステム。
【請求項４】
前記復帰処理部は、前記ローカルのストレージに記録されている、前記クラスタが再構成された時刻と、データが更新された時刻と、に基づいて、データ要求またはその応答としてのデータ送信を行い、応答側の場合、前記離脱したプロセッサが以前の担当に復帰するまでの期間において代理として保存したデータの分だけ、復帰する前記プロセッサに送信することを特徴とする請求項３に記載のクラスタシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散処理機構のクラスタシステムに係り、特に、分散データベースや不揮発性媒体によるストレージを用いるクラスタシステムに関する。
【背景技術】
【０００２】
従来、分散処理機構のクラスタを構成するクラスタメンバ（例えばサーバ）において、冗長化構成がとられることがある。例えば、非特許文献１には、クラスタを構成するサーバの一部が故障等により停止すると、残存するサーバ集合で直ちにクラスタを組み直し、冗長化構成等を回復する高可用性のクラスタサーバが記載されている。非特許文献１に記載のクラスタモデルは、コンシステントハッシュ法（Consistent Hashing）に基づき、クラスタを構成するメンバについてのＩＤ空間上のアドレスを記した表（アドレス表）を利用したメッセージの振り分けとデータの管理を行っている。
【０００３】
また、従来、分散データベースの分野では、例えばDynamo（アマゾン（登録商標）のダイナモ）やCassandra（アパッチのカサンドラ）といった代表的な分散データベースが知られている（例えばDynamoについては非特許文献２参照）。Cassandraでは、ヒンテッド・ハンドオフ（Hinted Hand off）と呼ばれる方式を採用している。このヒンテッド・ハンドオフ方式は、クラスタ内に停止したサーバが確認されたときに、直ちにクラスタを組み直すことはせずに予め定められた所定時間だけクラスタを再構成せずにそのまま維持するという方式である。
【０００４】
ヒンテッド・ハンドオフ方式では、予め定められた前記所定時間内においては、クラスタ内で停止していない別のサーバにデータアクセスして機能を維持することになる。このときに停止していたサーバが前記所定時間内に復帰した場合、そのサーバには以前と同じデータ領域を担当して貰うことになる。そのため、前記所定時間内に復帰できる場合、サーバ停止および復帰に伴うデータ移動等による負荷が最小限で済む。
【０００５】
前記コンシステントハッシュ法は、非特許文献１に記載の技術以外に、例えばDynamo等でも採用されている。コンシステントハッシュ法を用いたデータ振り分け手法では、クラスタメンバとデータの双方にＩＤ（IDentifier）を割り当て、データのＩＤからＩＤ空間を時計回りに辿った場合に最初に出合ったクラスタメンバをそのデータの担当とする。
【０００６】
また、多量のデータの管理をクラスタ構成の分散処理システムで行う場合、あるクラスタメンバに障害が発生した場合でも他のクラスタメンバで処理を継続できるように、データの複製を保持することでデータ冗長化を実現する必要がある。これは、コンシステントハッシュ法によるデータ管理手法を用いた分散処理システムにおいても同様である。
【０００７】
図４（ａ）に示すように、コンシステントハッシュ法では、クラスタメンバ（メンバ１〜４）とデータの双方にＩＤを割り当てる。なお、図４（ａ）の例では、円（コンシステントハッシュ環：以下ＣＨ環ともいう）の円周上の４つの黒丸（●）でデータａ〜ｄを表示した。そして、コンシステントハッシュ法では、データのＩＤからＩＤ空間を時計回りに辿り最初に出合ったクラスタメンバをそのデータ（原本、マスタデータ）の担当として決定する。そして、担当するクラスタメンバのさらに右隣（時計回りに次）のクラスタメンバに複製データを担当させる。
【０００８】
例えば、図４（ａ）においては、データａはＩＤ空間（ＣＨ環）上を時計回りに辿り最初に出合ったメンバ１がマスタデータの担当となり、その複製データはＩＤ空間上でメンバ１の右隣にあたるメンバ２に担当させる。このようにマスタデータ・複製データを担当するクラスタメンバを決定することで、クラスタメンバに離脱があった場合でも複製データを所持しているクラスタメンバがマスタデータを新しく担当するクラスタメンバとなることで対応できるという利点がある。加えて、冗長化数を上げるために複製データを２個とる場合には、さらに右隣のクラスタメンバに２個目の複製データを担当させるようにすることもできる。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】岩佐絵里子、入江道生、福元健、“高可用サーバクラスタにおける自律的データ再配置方式の一検討”、電子情報通信学会2012年ソサイエティ大会、B-6-71、2012年9月
【非特許文献２】Giuseppe DeCandia, et al.,”Dynamo: Amazon’s Highly Available Key-value Store”, Proceeding 「SOSP '07 Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles Pages 205-220, ACM New York, NY, USA 2007」,［online］、［平成25年2月1日検索］、インターネット<URL: http://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf>
【発明の概要】
【発明が解決しようとする課題】
【００１０】
従来の分散処理機構の方式の１つとして、サーバが停止して離脱すると直ちにクラスタ構成を組み直す方式の場合、停止したサーバをその後再起動させて以前と同じ担当領域に復帰させようとしても、その時点ではクラスタが再構成されてしまっていることになる。そのため、再構成されたクラスタでは担当データ領域や冗長化構成が以前とは全く異なったものとなっている。したがって、一旦停止したサーバを以前と同じデータ担当領域に復帰させる場合、データを再配置させるための負荷が大きくなり、かつ時間もかかることになる。
【００１１】
サーバ離脱時に直ちにクラスタ構成を組み直す方式における、このようなデータ再配置の負荷や時間の問題については、Cassandra等で採用されているヒンテッド・ハンドオフ方式では解消される。しかしながら、ヒンテッド・ハンドオフ方式では、予め定められた前記所定時間内であって、一旦停止したサーバが復帰するまでの期間内では、冗長化数が少なくなるデータ領域が発生してしまうことになる。そのため、この期間内では、耐障害性が低下するという問題が存在していた。
【００１２】
このような背景に鑑みて本発明がなされたのであり、本発明は、クラスタを構成するクラスタメンバが離脱したときに冗長化数が少なくなるようなデータ領域や期間を低減することができるクラスタシステムを提供することを課題とする。
【課題を解決するための手段】
【００１３】
前記した課題を解決するため、請求項１に記載の発明は、入力情報に基づき、ストレージに対してデータの保存を含む処理を実行する複数のプロセッサと、前記複数のプロセッサ毎に設けられた複数の前記ストレージと、前記入力情報を前記複数のプロセッサのいずれかに振り分ける複数のディスパッチャとを備え、前記入力情報に対して１つのクラスタとして分散処理を行うと共に、前記複数のプロセッサそれぞれが当該プロセッサ用のローカルのストレージおよび前記クラスタ内のリモートのストレージにデータを冗長化して記憶するクラスタシステムであって、前記ディスパッチャが、前記入力情報のＩＤに対応したＩＤ空間上におけるデータの担当領域を示す情報を前記複数のプロセッサ毎に記憶する記憶部と、前記クラスタを構成する前記複数のプロセッサのいずれかが離脱した場合に直ちに、前記記憶部に記憶された前記担当領域を示す情報を参照して、前記ＩＤ空間上におけるデータの担当領域を組み替えることで前記クラスタを再構成し、変更を自身以外の前記ディスパッチャに通知する保存情報管理部と、を備え、前記プロセッサが、前記クラスタが再構成される度に、前記ＩＤ空間上におけるデータの担当領域を示す情報を、当該プロセッサ用のローカルのストレージに記録する担当領域更新記録部と、前記ローカルのストレージに保存するデータが更新される度に、データが更新されたことを示す情報と、前記担当領域を示す情報と、を前記ローカルのストレージに記録するデータ更新記録部と、を備えることを特徴とするクラスタシステムとした。
【００１４】
このようにすることで、本発明に係るクラスタシステムの各プロセッサは、ローカルのストレージに、データだけではなく、データの更新履歴およびデータの担当領域の更新履歴も記録しておくので、一旦離脱した後でクラスタに復帰する際には、以前と同じデータ領域を担当することができる。加えて、本発明に係るクラスタシステムのディスパッチャは、クラスタメンバが離脱した場合に直ちにクラスタ構成を組み直すので、冗長化数が少なくなる期間を低減する。
【００１５】
請求項２に記載の発明は、前記プロセッサにおいて、前記担当領域更新記録部は、前記クラスタが再構成された時刻を前記ローカルのストレージにさらに記録し、前記データ更新記録部は、前記ローカルのストレージに保存するデータが更新された時刻を前記ローカルのストレージにさらに記録することを特徴とする請求項１に記載のクラスタシステムとした。
【００１６】
このようにすることで、本発明に係るクラスタシステムは、各プロセッサが、ローカルのストレージに、クラスタが再構成された時刻と、データが更新された時刻とを更新履歴と共に記録しておくので、データ更新が、どの時点のクラスタ構成のときに発生したかを正確に特定することができる。
【００１７】
請求項３に記載の発明は、前記プロセッサが、前記ローカルのストレージに記録されている、前記担当領域を示す情報を前記ディスパッチャに通知し、前記離脱したプロセッサであって復帰する前記プロセッサとその代理を務めていたプロセッサとの間における通信処理を行う復帰処理部をさらに備えることを特徴とする請求項２に記載のクラスタシステムとした。
【００１８】
このようにすることで、本発明に係るクラスタシステムは、プロセッサが、ＩＤ空間上におけるデータの担当領域を示す情報をディスパッチャに通知するので、ディスパッチャは、離脱したプロセッサにおけるデータの担当領域についての代理を務めているプロセッサと、離脱したプロセッサとを特定することができる。そして、離脱したプロセッサがクラスタに復帰する前の準備段階において、この離脱したプロセッサと、代理を務めているプロセッサとが引き継ぎの通信を行うことで、クラスタへの復帰をスムーズに行うことができる。
【００１９】
請求項４に記載の発明は、前記復帰処理部が、前記ローカルのストレージに記録されている、前記クラスタが再構成された時刻と、データが更新された時刻と、に基づいて、データ要求またはその応答としてのデータ送信を行い、応答側の場合、前記離脱したプロセッサが以前の担当に復帰するまでの期間において代理として保存したデータの分だけ、復帰する前記プロセッサに送信することを特徴とする請求項３に記載のクラスタシステムとした。
【００２０】
このようにすることで、本発明に係るクラスタシステムは、一部のプロセッサが離脱中のクラスタ構成において、データ要求に応答する側のプロセッサは、代理期間中に更新が発生したデータのみをローカルのストレージから抽出して、離脱した後でクラスタに復帰するプロセッサの方へデータ転送して、整合性を回復することができる。したがって、代理期間中に更新されたデータのみを転送するため、短時間の停止であれば、整合性回復のための負荷を低減すると同時に時間も短縮できる。これにより、短時間のネットワーク分断や、瞬間的な停電によるサーバダウンからの復帰時間を短縮することができる。
【発明の効果】
【００２１】
本発明によれば、クラスタを構成するクラスタメンバが離脱したときに冗長化数が少なくなるようなデータ領域や期間を低減することができる。その結果、クラスタメンバが離脱したときに耐障害性が低下するような期間を低減して信頼性を高めることができる。
【図面の簡単な説明】
【００２２】
【図１】本発明の実施形態に係るクラスタシステムを含む全体構成を示す図である。
【図２】本発明の実施形態に係るクラスタシステムの内部構成を示す図である。
【図３】図２のディスパッチャの構成例を示す機能ブロック図である。
【図４】図３の振り分け処理部による通常処理の説明図であって、（ａ）はコンシステントハッシュ環の模式図、（ｂ）はサーバの担当領域の模式図である。
【図５】図２のプロセッサの構成例を示す機能ブロック図である。
【図６】図２のストレージに記憶された情報の一例を示す図である。
【図７】図３の振り分け処理部による減設処理の説明図であって、（ａ）はコンシステントハッシュ環の模式図、（ｂ）はサーバの担当領域の模式図である。
【図８】図２のストレージに記憶された情報の他の例を示す図である。
【図９】本発明の実施形態に係るクラスタシステムにおける動作例の模式図である。
【発明を実施するための形態】
【００２３】
［システム構成の概要］
図１に示すように、ネットワーク１００上に配置されたクラスタシステム１０１は、例えばキャッシュデータを格納するものであり、クライアント端末１０２や外部システム１０３から、リクエスト（入力情報）１０４を受け取り、例えばリクエスト１０４が読み込み（リード）であればレスポンス１０５としてデータを提供する。また、リクエスト１０４がデータの書き込み（ライト）であれば、クラスタシステム１０１は、データの保存や更新を行う。
【００２４】
クラスタシステム１０１の内部構造とデータアクセスの流れを図２に示す。クラスタシステム１０１は、図２に内部構成を示すように、ロードバランサ装置２０１と、サーバ群（サーバ２１１，２１２，２１３）とを備え、入力情報に対して１つのクラスタとして分散処理を行う。なお、ロードバランサ装置２０１の振り分け先として３台のサーバを図示したが、振り分け先の台数は複数であればよい。
【００２５】
各サーバ２１１，２１２，２１３は、ディスパッチャ２０２の機能と、プロセッサ２０３の機能とを備える。サーバが外部からのリードやライトのリクエストを処理することは、プロセッサ２０３がリクエストを処理することを意味する。ディスパッチャ２０２は、自らのサーバまたは他のサーバにリクエストを割り当てる処理を行う。
【００２６】
一例として、ディスパッチャ２０２と、プロセッサ２０３と、ストレージ２０４とが同一のサーバ筐体においてプロセスとして分離されている形で実装することができる。図１、図２、図９はこのような形式でサーバを分かり易く示した概念図である。
ただし、本発明はこれに限定されるものではない。つまり、ディスパッチャ２０２とプロセッサ２０３とを同一のサーバ筐体、ストレージ２０４を別筐体のように構成してもよい。さらに、３つとも別々のサーバ筐体に実装してもよい。図３、図５、図６、図８はこのような形式でサーバを示した機能ブロック図である。
【００２７】
クラスタシステム１０１に対する入力データ（リクエスト）がリードの場合、例えば、ＳＱＬ（Structured Query Language）のクエリやＸＣＡＰ（XML Configuration Access Protocol）のような、データベースからデータを取得するための要求を含む。
このようなリクエストに対して、図２を参照して、矢印で示すデータアクセスの流れ（Ｓ１〜Ｓ８の動作）と、その一部であるＳ２〜Ｓ６に対応して破線の矢印で示す分岐した流れ（Ｓ１２〜Ｓ１６またはＳ２２〜Ｓ２６の動作）と、Ｓ４に対応して分岐した動作（Ｓ９またはＳ１０の動作）とについて説明する。
【００２８】
ロードバランサ装置２０１は、クライアント端末１０２からのリクエスト（入力情報）を最初に受け付け（Ｓ１）、リクエストをいずれかのサーバに割り振る（Ｓ２，Ｓ１２，Ｓ２２のいずれか）。この割り振りは、例えばラウンドロビン等の非常に単純なアルゴリズムに従うものである。
【００２９】
ディスパッチャ２０２は、入力情報をいずれかのプロセッサ２０３に振り分けるものである。すなわち、サーバにリクエストが到着すると、リクエストをディスパッチャ２０２が取得し、自分宛のリクエストであれば、自身のプロセッサ２０３に転送する（Ｓ２３）。一方、自分宛のリクエスト以外については、コンシステントハッシュ等のアルゴリズムにより、適切なサーバに対してリクエストを転送する（Ｓ３またはＳ１３）。ディスパッチャ２０２は、ロードバランサ装置２０１と異なり、入力データの内容に基づき適切なサーバを特定してデータ転送できるようになっている。
【００３０】
プロセッサ２０３は、入力データに従い、プロセッサ２０３が制御する専用のストレージ（ローカルのストレージ２０４）からデータを検索したり、データの保存や更新をしたりする手段である（Ｓ４，Ｓ１４，Ｓ２４のいずれか）。本実施形態では、プロセッサ２０３で担当するデータ領域は、コンシステントハッシュ等のアルゴリズムの割振りに従うものとする。プロセッサ２０３で処理した結果のデータは、リクエストを転送してきたディスパッチャ２０２を経由し（Ｓ６，Ｓ１６，Ｓ２６のいずれか）、ロードバランサ装置２０１を経由して（Ｓ７，Ｓ１７，Ｓ２７のいずれか）、最終的にクライアント端末１０２にデータを返信する（Ｓ８）。
【００３１】
ストレージ２０４は、クラスタシステム１０１の外部から取得したデータや、プロセッサ２０３が記録するデータ等を記憶するものである。ストレージ２０４は、一般的な永続性記憶装置であって、例えばハードディスクやソリッドステートドライブ（ＳＳＤ）等といった不揮発性媒体から構成されている。外部から取得したデータは、例えばＸＭＬ（Extensible Markup Language）ファイルで保存される。
【００３２】
１つのサーバにおいて、ストレージ２０４は、その接続されたプロセッサ２０３毎に設けられており、ローカルのストレージとして機能する。これに対して、他のサーバのストレージ２０４のことをリモートのストレージと呼ぶ。各プロセッサ２０３は、当該プロセッサ２０３用のローカルのストレージ２０４およびクラスタ内のリモートのストレージ２０４にデータを冗長化して記憶する。例えば、プロセッサＰ2がストレージＳ2にマスタデータを保存した場合（Ｓ４）、冗長数が２ならば、その後の所定のタイミングで、プロセッサＰ2はストレージＳ1に複製データを保存する（Ｓ９）。冗長数が３ならば、その後、プロセッサＰ2はストレージＳ3にも複製データを保存する（Ｓ１０）。
【００３３】
［ディスパッチャの構成例］
図３は、図２のディスパッチャの構成例を示す機能ブロック図である。
ディスパッチャ２０２は、ロードバランサ装置２０１および複数のプロセッサ２０３と通信可能に接続され、ロードバランサ装置２０１から取得した入力データ（クエリ）を、プロセッサ２０３に振り分ける装置であり、図３に示すように、入出力部２と、メモリ部３と、記憶部４と、制御部５とを含んで構成される。
【００３４】
＜入出力部２＞
入出力部２は、ロードバランサ装置２０１や、各プロセッサ２０３との間の情報の入出力を行う。例えば、入出力部２は、ロードバランサ装置２０１が送信した入力データ（クエリ）を受信し、各プロセッサ２０３に対し、その入力データ（クエリ）の送信を行う。また、入出力部２は、ストレージ２０４に保存されるデータ等の検索結果をプロセッサ２０３から受信し、ロードバランサ装置２０１に対して送信する等の処理を行う。また、この入出力部２は、通信回線を介して情報の送受信を行う通信インタフェースと、不図示のキーボード等の入力手段やモニタ等の出力手段等との間で入出力を行う入出力インタフェースとから構成される。
【００３５】
＜メモリ部３＞
メモリ部３は、ＲＡＭ（Random Access Memory）等の一次記憶装置からなり、制御部５によるデータ処理に必要な情報を一時的に記憶している。
【００３６】
＜記憶部４＞
記憶部４は、ハードディスクやフラッシュメモリ等の記憶装置からなり、例えば、ディスパッチャ２０２の動作プログラムを記憶する。また、記憶部４は、ロードバランサ装置２０１や、自身以外の各ディスパッチャ２０２、各プロセッサ２０３のアドレス（ＩＰアドレス）等を記憶する。また、記憶部４は、入力情報のＩＤに対応したＩＤ空間上におけるデータの担当領域を示す情報をプロセッサ２０３毎に記憶する。記憶部４に記憶するこの情報をアドレス表と呼ぶ。アドレス表の一例を図４（ｂ）に示す。
【００３７】
≪アドレス表≫
図４（ｂ）に示すように、アドレス表は、データのＩＤと、マスタデータを格納するサーバのＩＤとを対応付けた表である。
ここで、データのＩＤは、クラスタシステム１０１内において担当領域を特定するための固有な番号である。
マスタデータを格納するサーバのＩＤは、入力データの振り分け先となるサーバを、クラスタシステム１０１内において特定するための固有な番号である。
なお、これらのＩＤは、クラスタシステム１０１内において、一意に特定されるＩＤであればよく、図４（ｂ）に示した表記方法に限定されるものではない。
【００３８】
図４（ｂ）に示すアドレス表は、図４（ａ）に示すコンシステントハッシュ法のＩＤ空間（ＣＨ環）に対応している。この例において、マスタデータ・複製データを担当するクラスタメンバを決定する方法は前記した通りなので説明を省略する。ここでは、ＣＨ環に０〜８００のＩＤを付し、これをデータのＩＤとした。また、クラスタメンバのＩＤを、メンバ１，メンバ２，メンバ３，メンバ４とした。
【００３９】
図４（ａ）においては、ＣＨ環の領域Ａとしてシングルハッチングで表示した範囲のＩＤ（0000〜0200）が付されたデータは、ＩＤ空間（ＣＨ環）上を時計回りに辿り最初に出合ったメンバ２がマスタデータを格納する担当となっている。
同様に、図４（ａ）においては、ＣＨ環の領域Ｂとしてダブルハッチングで表示した範囲のＩＤが付されたデータ（0201〜0400）は、ＩＤ空間（ＣＨ環）上を時計回りに辿り最初に出合ったメンバ３がマスタデータを格納する担当となっている。
以下同様に、データのＩＤが0401〜0550の場合、メンバ４がマスタデータを格納する担当であり、データのＩＤが0551〜0800の場合、メンバ１がマスタデータを格納する担当となっている。
【００４０】
図３に戻って、ディスパッチャ２０２の構成を説明する。
＜制御部５＞
制御部５は、ディスパッチャ２０２全体の制御を司り、情報受信部６と、構文解析部７と、振り分け処理部８と、保存情報管理部９と、情報送信部１０とを含んで構成される。なお、この制御部５は、例えば、ディスパッチャ２０２の記憶部４に格納されたプログラムをＣＰＵ（Central Processing Unit）がメモリ部３であるＲＡＭに展開し実行することで実現される。
【００４１】
＜情報受信部６＞
情報受信部６は、入出力部２を介して、ロードバランサ装置２０１からの入力データ（クエリ）や、プロセッサ２０３からの出力データを取得する。
【００４２】
＜構文解析部７＞
構文解析部７は、情報受信部６から入力データ（クエリ）を受け取り、そのクエリの内容を構文解析する。例えば、構文解析部７は、その入力データ（クエリ）が、ストレージ２０４に格納されたデータに対する検索要求（GET）であり、「keyの完全一致検索」や、「keyの範囲検索」等であるかを解析したり、新規のデータの登録要求（PUT）や、既存データの更新要求（UPDATE）等のクエリの内容を解析したりする。そして、構文解析部７は、その解析結果を振り分け処理部８に引き渡す。
【００４３】
＜振り分け処理部８＞
振り分け処理部８は、入力情報に対して予め定められた関数による演算を行い、演算結果からＩＤ空間上の担当領域を特定し、記憶部４に記憶された担当領域を示す情報によってクラスタの中から振り分け先となるプロセッサ２０３を決定し、決定したプロセッサ２０３に入力情報を送信する。
【００４４】
本実施形態では、振り分け処理部８は、ハッシュ値計算部１１を備え、このハッシュ値計算部１１が、構文解析部７から取得した解析結果に基づき、予め設定された順序性を保持したハッシュ関数、つまり、連続かつ単調増加するハッシュ関数を用いて、コンシステントハッシュを適用し、入力データのハッシュ値を計算する。
また、振り分け処理部８は、ハッシュ値計算部１１が計算したハッシュ値に基づき、記憶部４に記憶されたアドレス表（図４（ｂ））を参照し、振り分け先となるコンシステントハッシュ環上のクラスタメンバを決定する。そして、振り分け処理部８は、この決定されたクラスタメンバの物理ノードであるサーバを、振り分け先のサーバとして選択する。
【００４５】
＜保存情報管理部９＞
保存情報管理部９は、構文解析部７が入力データ（クエリ）を構文解析した結果に応じて、各サーバに保存される情報を管理する全体的な制御を行う機能（リクエスト管理機能）と、コンシステントハッシュ環上のクラスタメンバの配置を決定する機能（クラスタ再構成機能）とを備えている。
【００４６】
≪リクエスト管理機能≫
保存情報管理部９のリクエスト管理機能は、振り分け処理部８にてデータの取得要求（検索）、保存、変更等を実行するサーバが決定されると、その決定した振り分け先となるサーバに対して、入力データ（クエリ）を、情報送信部１０を介して送信する。
また、このリクエスト管理機能は、データの取得要求を示す入力データ（クエリ）の場合に、各サーバから取得したデータを、出力データとしてロードバランサ装置２０１に送信する制御を行う。
【００４７】
≪クラスタ再構成機能≫
保存情報管理部９のクラスタ再構成機能は、クラスタシステム１０１内において、各サーバの負荷にばらつきが生じる等したことにより、サーバを追加したり削除したりする場合に、当該サーバの削除に対応した、新たな仮想ノードのコンシステントハッシュ環上の配置を決定する。また、クラスタ再構成機能は、クラスタを構成するクラスタメンバ（プロセッサ２０３）が故障等によって離脱した場合に直ちに、クラスタを再構成する。
【００４８】
なお、保存情報管理部９のクラスタ再構成機能は、自身のディスパッチャ２０２がコーディネータとして機能する場合に実行されるものである。このコーディネータは、複数のディスパッチャ２０２のうちの１つが管理者等により、または、任意に設定される。また、コーディネータとして機能するディスパッチャ２０２が故障等した場合には、他のディスパッチャ２０２のうちの１つが、代わりにコーディネータの役割を果たすものである。
【００４９】
保存情報管理部９のクラスタ再構成機能は、サーバを追加する場合に、例えば、追加するサーバを管理するディスパッチャ２０２から、サーバが新たに追加されたことを示す参加通知を受け取ると、担当領域に配置する。このとき、保存情報管理部９は、新たなアドレス表を生成し、その生成した新たなアドレス表を、追加するサーバを管理するディスパッチャ２０２を含めた各ディスパッチャ２０２に送信する。
【００５０】
保存情報管理部９のクラスタ再構成機能は、クラスタシステム１０１の管理者等により、既存のサーバのうちの一つの削除指示を受けた場合や、故障等によって既存のサーバが離脱する場合、当該サーバを、コンシステントハッシュ環上から取り除いた新たなアドレス表を生成し、その生成した新たなアドレス表を、削除するサーバを管理するディスパッチャ２０２を除いた、各ディスパッチャ２０２に送信する。また、保存情報管理部９は、削除するサーバを管理するディスパッチャ２０２に対して、削除通知を送信する。
【００５１】
＜情報送信部１０＞
情報送信部１０は、振り分け処理部８が決定した振り分け先となるプロセッサ２０３に対して、入力データ等を送信したり、入力データ（クエリ）の内容に応じた各サーバへの制御情報等を送信したりする。また、プロセッサ２０３から受信したデータ等を、ロードバランサ装置２０１へ送信する等の制御を行う。
【００５２】
［プロセッサの構成例］
図５は、図２のプロセッサの構成例を示す機能ブロック図である。
プロセッサ２０３は、図５に示すように、入出力部２２と、メモリ部２３と、記憶部２４と、制御部２５とを含んで構成される。
【００５３】
＜入出力部２２＞
入出力部２２は、ディスパッチャ２０２やストレージ２０４との間の情報の入出力を行う。ここで、ディスパッチャ２０２との間の情報とは、例えば入力データ（クエリ）であり、ディスパッチャ２０２やストレージ２０４との間の情報とは、例えばストレージ２０４に保存されるデータ等の検索結果のことである。この入出力部２２は、通信回線を介して情報の送受信を行う通信インタフェースと、不図示のキーボード等の入力手段やモニタ等の出力手段等との間で入出力を行う入出力インタフェースとから構成される。
【００５４】
＜メモリ部２３＞
メモリ部２３は、ＲＡＭ等の一次記憶装置からなり、制御部２５によるデータ処理に必要な情報を一時的に記憶している。
【００５５】
＜記憶部２４＞
記憶部２４は、ハードディスクやフラッシュメモリ等の記憶装置からなり、例えば、プロセッサ２０３の動作プログラムを記憶する。また、記憶部２４は、ディスパッチャ２０２やストレージ２０４のアドレス（ＩＰアドレス）等を記憶する。
【００５６】
＜制御部２５＞
制御部２５は、プロセッサ２０３全体の制御を司り、情報受信部２６と、解析処理部２７と、担当領域更新記録部２８と、データ更新記録部２９と、検索処理部３０と、復帰処理部３１と、情報送信部３２とを含んで構成される。なお、この制御部２５は、例えば、プロセッサ２０３の記憶部２４に格納されたプログラムをＣＰＵがメモリ部２３であるＲＡＭに展開し実行することで実現される。
【００５７】
＜情報受信部２６＞
情報受信部２６は、入出力部２２を介して、ディスパッチャ２０２からの入力データ（クエリ）や、ストレージ２０４からの検索結果データを取得する。
【００５８】
＜解析処理部２７＞
解析処理部２７は、入出力部２２を介して、ディスパッチャ２０２から取得した入力データ（リクエスト）のプロトコル解析や、ファイル形式の確認を行う。具体的には、ディスパッチャ２０２から受信したリクエストに含まれるＸＭＬファイル等について、スキーマ定義が記述されたＸＳＤ（XML Schema Definition）ファイルと照合することで、ファイル形式が正しいか等の判定を行った上で、ストレージ２０４に対して、そのＸＭＬファイル等を書き込む処理を指示する。これにより、ストレージ２０４では、図６に示すように、プロセッサ２０３から受信したＸＭＬファイル等のデータ２１０Ａを保存する（ライト）。ここで、データ２１０Ａの記録は、ライトスルー方式とするかライトバック方式とするかは問わない。なお、検索のリクエストの場合、検索処理部３０に処理を渡す。
【００５９】
＜担当領域更新記録部２８＞
担当領域更新記録部２８は、クラスタが再構成される度に、ＩＤ空間上におけるデータの担当領域を示す情報を、当該プロセッサ２０３用のローカルのストレージ２０４に記録する。これにより、ストレージ２０４では、図６に示すように、担当領域更新履歴３２０が保存される。ここで、図６に示すストレージ２０４は、図４（ａ）においてＣＨ環の領域Ａに対応したＩＤ（0000〜0200）が付されたデータをマスタデータとして格納するメンバ２のストレージＳ2を示している。
本実施形態では、担当領域更新記録部２８は、図６に示すように、クラスタが再構成された時刻３２１と、担当領域３２２とを記録することとした。
担当領域３２２は、当該サーバが、これまでどのデータ領域を担当してきたかという情報を示す。クラスタ内に別のサーバが追加されることで担当領域が縮小されたり、故障等により他のサーバが離脱することで担当領域が拡大したりする。これらの内容が時刻３２１毎に記録されている。また、ここでは、コンシステントハッシュのアルゴリズムを想定しているため、環上のHash空間（ＣＨ環）の何処から何処までを担当としたかを記録する様子を示している。
【００６０】
データ更新記録部２９は、ローカルのストレージ２０４に保存するデータが更新される度に、データが更新されたことを示す情報と、担当領域を示す情報と、をローカルのストレージ２０４に記録する。これにより、ストレージ２０４では、図６に示すように、データ更新履歴３３０が保存される。データ更新履歴３３０は、当該サーバに更新アクセスしてきたデータの履歴を記録するものである。
本実施形態では、データ更新記録部２９は、データ更新履歴３３０の内容として、図６に示すように、更新された時刻３３１と、データのハッシュ値３３２と、担当領域を示す領域３３３とをセットで記録することとした。データ更新履歴３３０は、更新時刻順にソートされている。
【００６１】
＜検索処理部３０＞
検索処理部３０は、解析処理部２７にてディスパッチャ２０２から取得した入力データ（クエリ）のＸＳＤファイルとの照合等を行ったリクエストで指定されたＸＭＬデータをストレージ２０４から検索して取得し（リード）、ディスパッチャ２０２、ロードバランサ装置２０１を経由して、そのＸＭＬデータをクライアント端末１０２に送信する。
【００６２】
＜復帰処理部３１＞
復帰処理部３１は、ローカルのストレージ２０４に記録されている、担当領域を示す情報をディスパッチャ２０２に通知し、復帰するプロセッサ２０３とその代理を務めていたプロセッサ２０３との間における通信処理を行う。
復帰処理部３１は、ローカルのストレージ２０４に記録されている、クラスタが再構成された時刻と、データが更新された時刻と、に基づいて、データ要求またはその応答としてのデータ送信を行う。復帰処理部３１は、応答側の場合、除外されたプロセッサ２０３が以前の担当に復帰するまでの期間において代理として保存したデータの分だけ、復帰するプロセッサ２０３に送信する。
【００６３】
＜情報送信部３２＞
情報送信部３２は、リクエストを送信してきたディスパッチャ２０２に対して、ストレージ２０４からの検索結果データを送信したり、ローカルのストレージ２０４に対する保存データ（マスタデータ）の複製データをリモートのストレージ２０４に対して送信したりする。
【００６４】
［サーバ離脱時の記憶構造の例］
ここでは、図４，６，７，８を参照して、サーバ離脱時の記憶構造の例について説明する。図７は、図４に示すメンバ２が離脱した後の状態を示す点が図４と相違している。また、図６は、クラスタから離脱したメンバ２のローカルのストレージ２０４を示し、図８は、再構成後のクラスタに残ったメンバ３のローカルのストレージ２０４を示している。
【００６５】
図７（ａ）に示すように、メンバ２が離脱した後の状態では、これまでメンバ２が担当していた領域Ａについては、例えばＩＤ空間上でメンバ２の右隣にあたるメンバ３が引き継ぐ。このとき、アドレス表は、図７（ｂ）に示すように、ＩＤ（0000〜0200）が付されたデータのマスタデータを格納するサーバのＩＤが、メンバ２（図４（ｂ）参照）からメンバ３（図７（ｂ）参照）に書き換えられる。これにより、メンバ３は、図７（ａ）に示すように、ＣＨ環の領域Ｂ（例えばデータｃ）に加えてＣＨ環の領域Ａ（例えばデータｂ）についてもマスタデータを格納することになる。
【００６６】
また、複製データの格納ルールに則って、メンバ３は、例えばＩＤ空間上でメンバ３の新たに左隣になったメンバ１で格納するデータの複製（データａのコピー）を格納することとなる（図７（ａ）参照）。
さらに、これまでメンバ３で格納していた複製データ（データｂのコピー：図４（ａ）参照）については、例えばＩＤ空間上でメンバ３の右隣にあたるメンバ４で格納することとなる（図７（ａ）参照）。
【００６７】
次に、担当領域が増加したメンバ３のローカルのストレージ（Ｓ3：図８）と、クラスタから離脱したメンバ２のローカルのストレージ（Ｓ2：図６）とを対比して説明する。
図６に示すストレージＳ2には、担当領域更新履歴３２０に示すように、時刻「500」を開始時刻として領域Ａを担当していたことが記録されている。また、データ更新履歴３３０によれば、時刻が600、900、および1800のときに、いずれも領域Ａのデータ更新アクセスがあったことが記録されている。なお、領域Ａのデータとして保存または更新されたデータをデータ２１０Ａと表記した。メンバ２は、例えば時刻「2000」には停止していたものとする。
【００６８】
一方、図８に示すストレージＳ3には、担当領域更新履歴３２０に示すように、時刻「500」を開始時刻として領域Ｂを担当していたことが記録されており、さらに、時刻「2000」を開始時刻として領域Ａおよび領域Ｂを担当していたことが記録されている。
また、データ更新履歴３３０によれば、時刻が2000になる以前には、いずれも領域Ｂのデータ更新アクセスがあったことが記録されており、時刻が2000以降には、領域Ａと領域Ｂのデータ更新アクセスがあったことが記録されている。なお、領域Ｂのデータとして保存または更新されたデータをデータ２１０Ｂと表記した。
【００６９】
このように各メンバは、ローカルのストレージＳ2，Ｓ3に、データ２１０Ａ，２１０Ｂだけではなく、データ更新履歴３３０および担当領域更新履歴３２０も記録しておくので、一旦離脱したメンバがクラスタに復帰する際には、以前と同じデータ領域を担当することができる。具体的には、停止しているメンバ２が、再起動をして停止前に担当していた領域Ａを再度担当する場合、例えば時刻が4000になるときに復帰するならば、例えば時刻が2000〜4000の間に代理として残って更新データアクセスを受け付けたメンバ３から、その間の更新分のデータを引き継ぐことができる。
【００７０】
［クラスタシステムにおける動作例］
図９は、本発明の実施形態に係るクラスタシステムにおける動作例の模式図である。
まず、通常時において、クラスタ内の各サーバにおいて、プロセッサ２０３は、自身の担当領域が何処であるかを示す情報を、自分のストレージ２０４に、担当領域更新履歴３２０（図６および図８参照）として記録し、保存しておく（ステップＳ３１）。
また、当然、データ更新アクセスも存在するため、この更新情報もデータ更新履歴３３０（図６および図８参照）の方に更新時刻と共に記録し、かつ更新データも記録しておく（ステップＳ３２）。
【００７１】
この状態で、一部のサーバに故障が発生したとする。これにより、サーバが停止したり、データ欠損が生じたりする。この例では、６台のサーバのうち、３台が停止したものとする（図９において破線で模式的に示す）。
一部のサーバ集合が停止をしたら、残されたサーバ集合のディスパッチャ２０２は、直ちに減設処理を実行する。これにより、残されたサーバ集合は、クラスタ構成を再構築して冗長化数を回復する（ステップＳ３３）。それと同時に、残されたサーバ集合は、担当領域更新履歴３２０（図８参照）に、停止したサーバの分だけ増えた領域を記録する。つまり、担当領域を更新する（ステップＳ３４）。
また、この後もデータ更新アクセスは存在するので、残されたサーバ集合は、通常通り、データ更新履歴３３０（図８参照）に記録しておく。
【００７２】
停止したサーバは、再起動等をすると、自分のストレージに保存された担当領域更新履歴３２０（図６参照）の担当領域（ＣＨ環）を読み込み、自分が停止する直前の担当領域を把握し、元のクラスタの元の場所に復帰するための準備状態（スタンバイ）として戻る（ステップＳ３５）。但し、この状態では、コンシステントハッシュの担当領域はまだ変更されていないので、スタンバイ状態のサーバにデータアクセスが発生することはない。
【００７３】
残存したクラスタのサーバでは、自らの担当領域更新履歴３２０（図８参照）から、停止サーバ（復帰準備に入っているサーバ）の担当領域を割り出し、さらに、自らのデータ更新履歴３３０（図８参照）から、故障後（停止後）に更新されたデータを割り出して、停止後に更新されたデータのみを抽出する（ステップＳ３６）。
【００７４】
残存したクラスタのサーバでは、停止サーバ（復帰準備に入っているサーバ）の担当領域の更新分のデータのみを、復帰準備に入っているサーバに転送する（ステップＳ３７）。これにより、復帰準備に入っているサーバではデータ整合性が回復する。なお、転送途中において、該当領域に更に更新がかかった場合は、それを再送することになる。
【００７５】
残存したクラスタのサーバは、全ての転送が完了すると、担当領域を、復帰準備に入っているサーバに渡すと同時に、担当領域更新履歴３２０（図８参照）も更新する。これにより、復帰準備に入っていたサーバは、復帰完了サーバとして、以前と同じデータ領域を再度担当することになり、以降、データアクセスを受け付ける。
【００７６】
以上説明したように、クラスタシステム１０１の各プロセッサ２０３は、ローカルのストレージ２０４に、データだけではなく、そのデータの更新履歴およびデータの担当領域の更新履歴も記録しておく。そのため、クラスタメンバが一旦離脱した後でクラスタに復帰する際には、以前と同じデータ領域を担当することができる。加えて、クラスタシステム１０１のディスパッチャ２０２は、クラスタメンバが離脱した場合に直ちにクラスタ構成を組み直すので、冗長化数が少なくなる期間を低減することができる。
【００７７】
以上、本発明の実施形態について説明したが、本発明はこれに限定されるものではなく、その趣旨を変えない範囲で実施することができる。例えば、本実施形態では、コンシステントハッシュ法に基づき、クラスタを構成するメンバについてのＩＤ空間上のアドレスを記した表（アドレス表）を利用したメッセージの振り分けとデータの管理を行ったが、本発明は、コンシステントハッシュ法に限るものではない。
【００７８】
また、本実施形態では、一例として、検索（リード）とデータ更新（ライト）との両方を行うものとしたが、データ更新（ライト）のみを行うこととしてもよい。
【符号の説明】
【００７９】
１００  ネットワーク
１０１  クラスタシステム
１０２  クライアント端末
１０３  外部システム
１０４  リクエスト
１０５  レスポンス
２０１  ロードバランサ装置
２０２  ディスパッチャ
２０３  プロセッサ
２０４  ストレージ
２１１，２１２，２１３  サーバ
２      入出力部
３      メモリ部
４      記憶部
５      制御部
６      情報受信部
７      構文解析部
８      振り分け処理部
９      保存情報管理部
１０    情報送信部
１１    ハッシュ値計算部
２２    入出力部
２３    メモリ部
２４    記憶部
２５    制御部
２６    情報受信部
２７    解析処理部
２８    担当領域更新記録部
２９    データ更新記録部
３０    検索処理部
３１    復帰処理部
３２    情報送信部
【図１】
2014164502.tif 000003
【図２】
2014164502.tif 000004
【図３】
2014164502.tif 000005
【図４】
2014164502.tif 000006
【図５】
2014164502.tif 000007
【図６】
2014164502.tif 000008
【図７】
2014164502.tif 000009
【図８】
2014164502.tif 000010
【図９】
2014164502.tif 000011