(57)【特許請求の範囲】
【請求項１】
クラスタシステムに含まれるサーバ装置であって、
前記サーバ装置は、
メタデータと実データとを含む、複製データまたは／および原本データを保持するメモリと、
前記メモリの利用率を測定するメモリ利用率測定部と、
前記メモリの利用率が第１の閾値を超え、かつ、前記複製データの実データが有るならば，前記複製データへのアクセスを契機に当該複製データの実データを前記メモリから削除し、前記メモリの利用率が前記第１の閾値よりも小さい第２の閾値以下ならば、前記複製データへのアクセスを契機に、アクセスされた当該複製データの実データの有無を判断し、当該複製データの実データが無いならば、当該複製データのメタデータに基づき当該複製データに対応する前記原本データの実データを他のサーバ装置から取得する実データ削除／取得部と、
を備えることを特徴とするクラスタシステムのサーバ装置。
【請求項２】
前記原本データおよび前記複製データは、コンシステント・ハッシュ法によるＩＤ空間によって管理される、
ことを特徴とする請求項１に記載のクラスタシステムのサーバ装置。
【請求項３】
メタデータと実データとを含む原本データを複製した複製データへのアクセスを受け付けるステップ、
前記原本データまたは／および前記複製データを保持するメモリの利用率を測定するステップ、
前記メモリの利用率が第１の閾値を超えたならば、アクセスされた当該複製データの実データの有無を判断するステップ、および、当該複製データの実データが有るならば、前記メモリから当該複製データの実データを削除するステップ、
または、前記メモリの利用率が前記第１の閾値よりも小さい第２の閾値以下ならば、前記複製データへのアクセスを契機に、アクセスされた当該複製データの実データの有無を判断するステップ、および、当該複製データの実データが無いならば、当該複製データのメタデータに基づき当該複製データに対応する前記原本データの実データを他のサーバ装置から取得するステップ、
をクラスタシステムのサーバ装置に実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データの冗長度を管理するクラスタシステムを構成する各サーバ装置、および、そのプログラムに関する。
【背景技術】
【０００２】
近年、複数のサーバを協調動作させて、全体で１台のコンピュータのように動作させるクラスタシステムが利用されている。クラスタシステムは、多量なデータの処理や再配置を効率的に実行するためにコンシステント・ハッシュ法などによってデータを管理することが多い。
非特許文献１には、コンシステント・ハッシュ法によるデータ管理方法が記載されている。非特許文献２には、コンシステント・ハッシュ法より実際に運用されている例が記載されている。
【０００３】
コンシステント・ハッシュ法では、各サーバが持つ複数の仮想的なＩＤ（メンバ）を、ＩＤ空間上に配置することで、各メンバが担当する領域を平均化し、各サーバの処理負荷を分散させている。また、コンシステント・ハッシュ法では、障害発生時に他のメンバでも処理を行えるように、冗長化した原本データと複製データとをクラスタシステム内に保持する。これにより、クラスタシステムは、サーバ故障などの障害発生時にもサービスを継続することが可能となる。
【０００４】
クラスタシステムは、複数のサーバ装置で構成される。各サーバ装置は、信号処理を行うメンバを１つ以上保持する。各メンバは、コンシステント・ハッシュ法などを用いたＩＤ空間上に配置される。
各メンバは、信号の受信／データの保持／データの操作／信号の送信の一連の処理を行い、ユーザへサービスを提供する。サービスで利用されるユーザデータは、実際のデータである「実データ」と、ユーザやデータの状態などを表す「メタデータ」とを含んでいる。各メンバは、ユーザ単位のユーザデータを保持する。
【０００５】
ユーザデータは、クラスタシステム上で原本データと、原本データのバックアップ用としての１以上の複製データが存在する。クラスタシステムは、同一のユーザデータを冗長度の数だけ保持することで、冗長性を担保する。冗長度の数とは、同一のクラスタシステム内に存在する原本データと複製データの総数である。
激甚災害などによるサーバの障害や故障により、メンバの一部が停止して冗長度が不足した場合、クラスタシステムは、残存するサーバ集合でクラスタを組み直し、自律的に冗長化構成などを回復する。クラスタシステムは、自律的にデータの探索およびデータの再配置（原本昇格・複製データの作成・削除）を行う。具体的にいうと、クラスタシステムは、故障してクラスタから離脱したサーバが保持しているデータを、残存している他のサーバへ自律的に引き継き、処理を行わせる。
これによりクラスタシステムは、激甚災害の発生時においても、サービスの継続が可能である。クラスタシステムは、故障したサーバが持つ冗長度が低下したデータについて、自動的に他のサーバがそのデータの複製を作成し、冗長度を回復する。
【０００６】
図１７（ａ），（ｂ）は、比較例のメモリ閾値超え時の複製データ保持動作を示す説明図である。
図１７（ａ）は、障害や故障により冗長度が不足した場合のデータの再配置動作を示している。
コンシステント・ハッシュ法などを用いたＩＤ空間６には、メンバ６１−１〜６１−５が配置される。原本データを保持するメンバ６１−２は、障害や故障により停止する。クラスタシステムは、メンバ６１−３〜６１−５上に、複製データを作成する。この状況は、冗長度が低下した過渡状態である。
このときメンバ６１−５は、メモリ利用率が閾値を超えている。図１７（ａ）では、メモリ利用率が閾値を超えたメンバ６１−５を、ハッチングで示している。
【０００７】
図１７（ｂ）は、データの再配置後のＩＤ空間６を示している。
ＩＤ空間６には、メンバ６１−１，６１−３，６１−４が配置される。障害や故障により停止したメンバ６１−２は、消滅する。メンバ６１−３は、原本データを保持する。メンバ６１−４，６１−５は、複製データを保持する。このとき、メンバ６１−５は、サーバのメモリ量を超えたデータを保持したため、処理不可に陥り故障する。図１７（ｂ）では、故障したメンバ６１−５を、「×」印で示している。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】David Karger、他５名、“Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web”、［ｏｎｌｉｎｅ］、［２０１４年２月１９日検索］、インターネット<URL：http://www.akamai.com/dl/technical_publications/ConsistenHashingandRandomTreesDistributedCachingprotocolsforrelievingHotSpotsontheworldwideweb.pdf>
【非特許文献２】Giuseppe DeCandia他８名、“Dynamo: Amazon’s Highly Available Key-value Store”、［ｏｎｌｉｎｅ］、［２０１４年２月１９日検索］、インターネット<URL：http://www.allthingsdistributed.com/files/amazon-dynamo-sosp2007.pdf>
【発明の概要】
【発明が解決しようとする課題】
【０００９】
データの冗長度を自律的に確保するクラスタシステムにおいて、激甚災害などにより第１のサーバの故障が発生すると、ユーザのデータは第２のサーバへ引き継がれる。第２のサーバは、自装置の利用可能なメモリの許容量を超えてデータを保持すると、処理不可に陥り故障となる。故障となった第２のサーバの持つデータは、第３サーバへ割り振られる。第３のサーバも、自装置の利用可能なメモリの許容量を超えてデータを保持すると、処理不可に陥り故障となる。
大規模な激甚災害や多数のサーバの故障により、メモリ不足のサーバが多数存在する場合には、このようにメモリ不足によるサーバの故障が連鎖的に発生する虞がある。このとき、クラスタシステム全体が解体して、サービスが継続不能となる。
【００１０】
本発明は、前記した問題を解決し、データの冗長度を自律的に確保しつつ、クラスタシステムの解体を抑制してサービスを継続するクラスタシステムのサーバ装置およびプログラムを提供することを課題とする。
【課題を解決するための手段】
【００１１】
前記課題を解決するため、請求項１に記載の発明では、クラスタシステムに含まれるサーバ装置とした。前記サーバ装置は、メタデータと実データとを含む、複製データまたは／および原本データを保持するメモリと、前記メモリの利用率を測定するメモリ利用率測定部と、前記メモリの利用率が第１の閾値を超え、かつ、前記複製データの実データが有るならば，前記複製データへのアクセスを契機に当該複製データの実データを前記メモリから削除し、前記メモリの利用率が前記第１の閾値よりも小さい第２の閾値以下ならば、前記複製データへのアクセスを契機に、アクセスされた当該複製データの実データの有無を判断し、当該複製データの実データが無いならば、当該複製データのメタデータに基づき当該複製データに対応する前記原本データの実データを他のサーバ装置から取得する実データ削除／取得部と、を備える。
【００１２】
このようにすることで、サーバ装置は、データの冗長度を自律的に確保しつつ、メモリの利用率が増えたときには、自律的にデータの冗長度を低下させる。よって、クラスタシステムの解体を抑制して、サービスを継続することができる。更にサーバ装置は、データの冗長度を自律的に低下させたのちにメモリの利用率が低下（回復）したときに、自律的にデータの冗長度を回復させることができる。
【００１５】
請求項２に記載の発明では、前記原本データおよび前記複製データは、コンシステント・ハッシュ法によるＩＤ空間で管理される、ことを特徴とする請求項１または請求項２に記載のクラスタシステムのサーバ装置とした。
【００１６】
このようにすることで、サーバ装置は、コンシステント・ハッシュ法によるＩＤ空間でデータを管理すると共に、データの冗長度を自律的に確保しつつ、クラスタシステムの解体を抑制して、サービスを継続することができる。
【００１７】
請求項３に記載の発明では、メタデータと実データとを含む原本データを複製した複製データへのアクセスを受け付けるステップ、前記原本データまたは／および前記複製データを保持するメモリの利用率を測定するステップ、前記メモリの利用率が第１の閾値を超えたならば、アクセスされた当該複製データの実データの有無を判断するステップ、および、当該複製データの実データが有るならば、前記メモリから当該複製データの実データを削除するステップ、または、前記メモリの利用率が前記第１の閾値よりも小さい第２の閾値以下ならば、前記複製データへのアクセスを契機に、アクセスされた当該複製データの実データの有無を判断するステップ、および、当該複製データの実データが無いならば、当該複製データのメタデータに基づき当該複製データに対応する前記原本データの実データを他のサーバ装置から取得するステップ、をクラスタシステムのサーバ装置に実行させるためのプログラムとした。
【００１８】
このようにすることで、プログラムは、サーバ装置に、データの冗長度を自律的に確保させつつ、メモリの利用率が増えたときには、自律的にデータの冗長度を低下させることができる。よって、クラスタシステムの解体を抑制して、サービスを継続することができる。更にプログラムは、サーバ装置に、データの冗長度を自律的に低下させたのちにメモリの利用率が低下（回復）したときに、自律的にデータの冗長度を回復させることができる。
【発明の効果】
【００１９】
本発明によれば、データの冗長度を自律的に確保しつつ、クラスタシステムの解体を抑制してサービスを継続するクラスタシステムのサーバ装置およびプログラムを提供することが可能となる。
【図面の簡単な説明】
【００２０】
【図１】第１の実施形態におけるクラスタシステムを示す概略の構成図である。
【図２】クラスタシステム内のユーザデータ例を示す図である。
【図３】第１の実施形態におけるクラスタシステムのＩＤ空間上のメンバ配置の説明図である。
【図４】第１の実施形態の変形例のクラスタシステムのＩＤ空間上のメンバ配置の説明図である。
【図５】第１の実施形態における各サーバ装置の信号処理を示すフローチャートである。
【図６】通常時のメンバとユーザデータの例を示す説明図である。
【図７】激甚災害発生によるメモリ不足時のメンバとユーザデータの例を示す説明図である。
【図８】複製データ削除時のメンバとユーザデータの例を示す説明図である。
【図９】冗長度回復時のメンバとユーザデータの例を示す説明図である。
【図１０】複製データの取得ができないパターンを示す説明図である。
【図１１】第２の実施形態における過渡状態のデータ探索範囲を示す説明図である。
【図１２】データ探索範囲の根拠を示す説明図である。
【図１３】複製データ保持メンバの隣接時における通常状態のＩＤ空間を示す説明図である。
【図１４】複製データ保持メンバの隣接時におけるデータ探索処理を示す説明図である。
【図１５】複製データ保持メンバの非隣接時における通常状態を示す説明図である。
【図１６】複製データ保持メンバの隣接時におけるデータ探索処理を示す説明図である。
【図１７】比較例のメモリ閾値超え時の複製データ保持動作を示す説明図である。
【発明を実施するための形態】
【００２１】
次に、本発明を実施するための形態（「実施形態」という）について、適宜図面を参照して詳細に説明する。
【００２２】
（第１の実施形態）
図１は、第１の実施形態におけるクラスタシステム１を示す概略の構成図である。
クラスタシステム１は、複数のサーバ２−１〜２−ｎ（サーバ装置）からなるクラスタ３と、振分装置４−１〜４−ｍと、ロードバランサ５とを含んで構成される。以下、サーバ２−１〜２−ｎを特に区別しない場合には、単にサーバ２と記載する。振分装置４−１〜４−ｍを特に区別しない場合には、単に振分装置４と記載する。
【００２３】
各サーバ２は、コンピュータなどの物理装置や仮想マシンなどの論理装置である。サーバ２は、信号処理部２１と、メモリ利用率測定部２２と、実データ削除／取得部２３と、記憶部２４と、メモリ２５とを備えている。記憶部２４は、例えばハードディスクやフラッシュメモリなどの二次記憶装置であり、信号処理プログラム２４１を格納する。メモリ２５は、例えばＤＲＡＭ（Dynamic Random Access Memory）などの一次記憶装置であり、各メンバ６１を保持する。
信号処理部２１は、他のサーバ２の信号のアクセスを受け付けて処理する。
メモリ利用率測定部２２は、メモリ利用率を測定する。メモリ利用率測定部２２は、メモリ測定命令によって、その都度測定を行うだけでなく、定期的に測定を行うことも可能である。ここでメモリ利用率とは、例えばメモリ２５の実装量に対する使用量の割合である。
実データ削除／取得部２３は、後記する図２に示すユーザデータの実データを削除／取得する。
信号処理プログラム２４１は、このサーバ２上の不図示のＣＰＵ（Central Processing Unit）によって実行されて、信号処理部２１と、メモリ利用率測定部２２と、実データ削除／取得部２３と、各メンバ６１とを具現化する。
振分装置４は、コンピュータなどの物理装置であり、受信したメッセージを振り分ける振分部４１と、不図示の入出力部、制御部、記憶部などを備える。
クライアント端末９や、ロードバランサ５は、コンピュータなどの物理装置であり、それぞれ不図示の入出力部、制御部、記憶部などを備える。
【００２４】
クライアント端末９からのメッセージは、ロードバランサ５にて、単純なラウンドロビン法などにより、振分装置４に振り分けられる。振分装置４は、例えばコンシステント・ハッシュ法などに基づき、受信したメッセージが要求するデータの識別子を参照して、このデータを管理しているサーバ２を特定する。振分装置４は、特定したサーバ２に、受信したメッセージを振り分ける。
【００２５】
各サーバ２は、信号を処理する１つ以上の論理的な処理機能であるメンバ６１を保持している。各サーバ２は、データの識別子により処理するメンバ６１を特定してメッセージに記載された処理を行わせ、クライアント端末９にサービスを提供する。
【００２６】
なお、第１の実施形態では、振分装置４と各サーバ２とを別に記載したが、同一筐体上で別々の機能として動作させてもよい。また、振分装置４をクラスタ構成としてもよい。更に、ロードバランサ５が存在せず、クライアント端末９から任意の振分装置４にメッセージを送信するように構成してもよい。
【００２７】
図２は、クラスタシステム１内のユーザデータ例を示す図である。
メンバ６１−１〜６１−Ｍは、メモリ２５（図１参照）にユーザデータを保持している。このユーザデータは、クライアント端末９などのユーザへサービスを提供するためのユーザ個別のデータである。ユーザデータは、データに係る情報を表す「メタデータ」と、実際のサービスで用いられる「実データ」とを含む。「メタデータ」は、例えば、原本として保持するメンバ６１の識別子や、データへのアクセス時刻などの情報である。
メンバ６１−１は、メモリ２５（図１参照）にユーザデータの原本である原本データを格納している。メンバ６１−２〜６１−Ｍは、メモリ２５（図１参照）に原本データの複製である複製データを格納している。これにより、クラスタシステム１（図１参照）は、ユーザデータの冗長性を確保することができる。冗長度Ｍは、原本データと複製データとを併せた数である。クラスタシステム１には、同一データが冗長度Ｍだけ存在する。
クラスタシステム１は、複製データが消失した場合には原本データより復元して冗長性を回復し、原本データが消失した場合には複製データより実データを取得してサービスを継続する。
【００２８】
図３は、第１の実施形態におけるクラスタシステム１のＩＤ空間６上のメンバ６１の配置の説明図である。
クラスタシステム１は、複数のサーバ２を含む分散システムである。各サーバ２は、拠点７−１〜７−３のいずれかに相互に通信可能に配置されて分散システムを構成する。
第１の実施形態では、コンシステント・ハッシュ法のＩＤ空間６上に、メンバ６１を配置している。各サーバ２は、１個以上のメンバ６１を保持している。例えば拠点７−１のサーバ２−１は、２個のメンバ６１−１，６１−２を保持している。
各サーバ２は、メンバ６１とデータの双方にＩＤを割り当て、データのＩＤから仮想ノードＩＤ空間であるＩＤ空間６を時計回りに辿り、最初に当たったメンバ６１を担当とする。ノードに対するＩＤの与え方は、例えば、ＩＰアドレスのハッシュ関数値などがある。
【００２９】
各サーバ２は、担当となったメンバ６１が持つデータを原本データと判断し、データの更新・削除などは原本データのみに実施する。各サーバ２は、原本データが変更された場合、定期的もしくは逐次的に複製データへ変更差分を反映する。データの取得・更新・削除も、同様な方法により各データに対してメンバ６１を特定する。
【００３０】
図４は、第１の実施形態の変形例のクラスタシステム１ＡのＩＤ空間６上のメンバ６１の配置の説明図である。
クラスタシステム１Ａは、複数のサーバ２を含み、複数の現用系が並列に動作するＮ−ＡＣＴ構成のシステムである。各サーバ２は、相互に通信可能に配置される。
このように、信号処理を行う論理的なメンバ６１は、分散システムの不特定のサーバ２上に限られず、Ｎ−ＡＣＴ構成の特定のサーバ２上に配置されてもよい。
【００３１】
図５は、第１の実施形態における各サーバの信号処理を示すフローチャートである。
事前にサーバ２毎にメモリ２５の利用率の閾値Ｘ，Ｙを設定する。閾値Ｘは、メモリ２５の利用率がこの閾値Ｘを超過した場合に、複製データを削除するための第１の閾値である。閾値Ｙは、メモリ２５の利用率がこの閾値Ｙを下回った場合に、削除した複製データを回復するための第２の閾値である。閾値Ｘと閾値Ｙとは、異なる値または同値となる。メモリ利用率の対象となるメモリ２５とは、例えば、物理メモリ・仮想メモリ・永続メモリなどを含めた記憶リソースである。
【００３２】
サーバ２が、クライアント端末９のメッセージを受信すると、図５の信号処理が開始する。
ステップＳ１０において、サーバ２は、メッセージによるデータへのアクセスを受け付ける。
ステップＳ１１において、サーバ２は、複製データへのアクセスであったか否かを判断する。サーバ２は、複製データへのアクセスであったならば（Ｙｅｓ）、ステップＳ１２の処理を行い、複製データへのアクセスではなかったならば（Ｎｏ）、図５の処理を終了する。
なお、複製データへのアクセスとは、原本データへの登録や変更、削除を契機に複製データへアクセスする処理と，整合処理や浮きチェックなどの定期的な複製データへのアクセスを含む処理とが含まれる。
【００３３】
ステップＳ１２において、サーバ２は、メモリ利用率測定部２２（図１参照）により、メモリ利用率を測定するか、または、メモリ利用率測定部２２により定期的に読み込んだ値を取得する。
ステップＳ１３において、サーバ２は、測定したメモリ利用率を閾値Ｘ，Ｙと比較して判定する。サーバ２は、メモリ利用率が閾値Ｘ（第１の閾値）を超えていたならば、ステップＳ１４の処理を行い、メモリ利用率が閾値Ｙ（第２の閾値）未満ならば、ステップＳ１６の処理を行い、メモリ利用率が閾値Ｙ以上かつ閾値Ｘ以下ならば、図５の処理を終了する。ここで閾値Ｙは、閾値Ｘよりも小さい値である。
【００３４】
ステップＳ１４において、サーバ２は、アクセスされた複製データに実データが存在するか否かを判断する。サーバ２は、この複製データに実データが存在するならば（Ｙｅｓ）、ステップＳ１５の処理を行い、この複製データに実データが存在しないならば（Ｎｏ）、図５の処理を終了する。
ステップＳ１５において、サーバ２は、実データ削除／取得部２３（図１参照）により、この複製データの実データを削除する。ステップＳ１５の処理が終了すると、サーバ２は、図５の処理を終了する。
【００３５】
ステップＳ１６において、サーバ２は、アクセスされた複製データに実データが存在するか否かを判断する。サーバ２は、この複製データに実データが存在するならば（Ｙｅｓ）、図５の処理を終了し、この複製データに実データが存在しないならば（Ｎｏ）、ステップＳ１７の処理を行う。
ステップＳ１７において、サーバ２は、実データ削除／取得部２３により、この複製データのメタデータに基づき、原本データを有するサーバ２から実データを取得する。ステップＳ１７の処理が終了すると、サーバ２は、図５の処理を終了する。
【００３６】
コンシステント・ハッシュ法を用いてメンバ６１をＩＤ空間６上に配置した例を、以下の図６から図９に示す。ここでは、クラスタシステム１が保持するユーザデータの冗長度を３としている。
図６は、通常時のメンバ６１とユーザデータの例を示す説明図である。
各メンバ６１−１〜６１−５は、同一のサーバ２または異なるサーバ２内に存在する。各メンバ６１−１〜６１−５は、ＩＤ空間６上に配置される。
メンバ６１−１は、データＡの原本と、データＨ，Ｇの複製とを保持する。メンバ６１−２は、データＢの原本と、データＡ，Ｈの複製とを保持する。メンバ６１−３は、データＣの原本と、データＢ，Ａの複製とを保持する。メンバ６１−４は、データＤの原本と、データＣ，Ｂの複製とを保持する。メンバ６１−５は、データＥの原本と、データＤ，Ｃの複製とを保持する。各データは、メタデータと実データとを含む。
【００３７】
図７は、激甚災害発生によるメモリ不足時のメンバ６１とユーザデータの例を示す説明図である。
激甚災害により、メンバ６１−１，６１−２が減設する。これにより、メンバ６１−１，６１−２が持つ下記のデータがメンバ６１−３〜６１−５へ引き継がれる。図７は、各データ引き継ぎの際の過渡状態を示している。データを新たに取得することにより、メンバ６１−３〜６１−５を保持するサーバ２は、メモリ不足に陥る。
【００３８】
メンバ６１−１は、データＡの原本と、データＨの複製と、データＧの複製とを保持していた。メンバ６１−２は、データＢの原本と、データＡの複製と、データＨの複製とを保持していた。
メンバ６１−３は、データＣの原本と、データＢ，Ａの複製とに加えて、データＨ，Ｇの複製を新たに引き継ぐ。データＨ，Ｇの引き継ぎにより、メンバ６１−３を保持するサーバ２のメモリ利用率は、閾値Ｘを超える。メンバ６１−３は、データＢ，Ａの複製を原本に昇格させる。
【００３９】
メンバ６１−４は、データＤの原本と、データＣ，Ｂの複製とに加えて、データＡ，Ｈの複製を新たに引き継ぐ。データＡ，Ｈの引き継ぎにより、メンバ６１−４を保持するサーバ２のメモリ利用率は、閾値Ｘを超える。
メンバ６１−５は、データＥの原本と、データＤ，Ｃの複製とに加えて、データＢ，Ａの複製を新たに引き継ぐ。データＢ，Ａの引き継ぎにより、メンバ６１−５を保持するサーバ２のメモリ利用率は、閾値Ｘを超える。
メンバ６１−３，６１−４，６１−５は、複製データ削除フェーズへ移行する。
図７では、メンバ６１−３，６１−４，６１−５を保持するサーバ２のメモリ利用率が、閾値Ｘを超えたことを示すため、ハッチングで示している。
【００４０】
図８は、複製データ削除時のメンバ６１とユーザデータの例を示す説明図である。
複製データ削除フェーズにおいて、複製データへのアクセスがあった場合、アクセスされたメンバ６１は、アクセスされた複製データに対して実データを保持せず、メタデータのみを保持する。既に実データを保持している場合は実データを削除し、システムにおけるデータの冗長度を一時的に低下させる。
【００４１】
メンバ６１−３は、データＡ，Ｂへアクセスがあった場合、これらデータＡ，Ｂが原本であるため実データを削除しない。メンバ６１−３は、データＧ，Ｈへアクセスがあった場合、これらデータＧ，Ｈが複製であるためメタデータのみを保持し、実データを削除する。図８では、メンバ６１−３が保持するデータＧ，Ｈは、実データが削除されている。
【００４２】
メンバ６１−４は、データＤへアクセスがあった場合、このデータＤが原本であるため実データを削除しない。メンバ６１−４は、データＣ，Ｂ，Ａ，Ｈへアクセスがあった場合、これらデータＣ，Ｂ，Ａ，Ｈが複製であるためメタデータのみを保持し、実データを削除する。図８では、メンバ６１−４が保持するデータＢ，Ａ，Ｈは、これらに対するアクセスがあったので、実データが削除されている。
【００４３】
メンバ６１−５は、データＥへアクセスがあった場合、このデータＥが原本であるため実データを削除しない。メンバ６１−４は、データＤ，Ｃ，Ｂ，Ａへアクセスがあった場合、これらデータＤ，Ｃ，Ｂ，Ａが複製であるためメタデータのみを保持し、実データを削除する。図８では、メンバ６１−５が保持するデータＤ，Ｂ，Ａは、これらに対するアクセスがあったので、実データが削除されている。メンバ６１−５が保持するデータＣは、これに対するアクセスが無かったので、実データが削除されていない。
【００４４】
各サーバ２のメモリ利用率が閾値Ｙを下回るまで、各メンバ６１は、この複製データ削除フェーズを継続し、上記の動作を行う。
【００４５】
図９は、冗長度回復時のメンバ６１とユーザデータの例を示す説明図である。
冗長度回復とは、サーバ２のメモリ・リソースが十分に回復し、複数のサーバ２にてメモリ２５の利用率が閾値Ｙを下回った場合のことをいう。
保守者やシステムにより充分なメモリ・リソースが確保されると、メンバ６１−３，６１−４を保持するサーバ２は、メモリ利用率が閾値Ｙを下回る。
閾値Ｙを下回ることで、各メンバ６１−３，６１−４は、通常状態へ遷移する。通常状態で複製データにアクセスされたとき、各メンバ６１は、この複製データの実データがないことを判断し、原本データを保持する他のメンバ６１から実データを取得する。クラスタシステム１は、このようにしてデータの冗長度を自律的に回復する。
【００４６】
ここでは、データＧ，Ｈ，Ａ，Ｄに対してデータのアクセスがあった場合を示している。
メンバ６１−３は、データＧ，Ｈへのアクセスにより、原本データを保持する他のメンバ６１からデータＧ，Ｈの実データを取得する。メンバ６１−４は、データＡ，Ｈへのアクセスにより、原本データを保持する他のメンバ６１からデータＡ，Ｈの実データを取得する。
なお、メンバ６１−５を保持するサーバ２は、メモリ２５の利用率が閾値Ｙを下回っていないため、メンバ６１−５は、通常状態には遷移しない。この後、メンバ６１−５を保持するサーバ２のメモリ利用率が閾値Ｙを下回ると、メンバ６１−５も通常状態に遷移し、データの冗長度を回復する。このようにクラスタシステム１は、自律的にデータの冗長度を回復する。
【００４７】
比較例のクラスタシステム（図１７参照）は、自律的な機能によりシステムの解体へ発展してしまう機能を持っている。大規模な激甚災害や複数のサーバ２が故障しメモリ２５が不足している状況でデータの複製を作成することで、メモリ２５の枯渇による故障が発生する。このデータの引き継ぎ先の他サーバ２においても、メモリ２５の枯渇による故障が連鎖して発生することで、クラスタシステム１の全体が解体し、サービスが停止してしまう。
【００４８】
第１の実施形態のクラスタシステム１（図１参照）は、一時的に冗長度を低下させることによりメモリ２５を確保しつつ、データの探索・取得を行う。これにより、クラスタシステム１は、原本のデータは救済かつ確保しつつ、自身の解体を抑制してサービスの継続を可能とする。
第１の実施形態のクラスタシステム１によれば、メモリ２５が不足している状況においては、メタデータのみを保持しつつメモリ２５の利用を抑制することで、クラスタシステム１の解体を回避でき、激甚災害時においてもサービスの継続を可能とする。また、第１の実施形態のクラスタシステム１によれば、激甚災害時などの一時的にメモリ２５が必要になる場合に備えて多量のメモリ・リソースを用意せずともよく、効率的にメモリ２５を利用することが可能となる。
【００４９】
第１の実施形態により、多数のサーバ２が故障した場合であっても、クラスタシステム１は、サービスの継続が可能である。
更に各サーバ２が故障から回復し、またはサーバ２が増設されて利用可能なメモリ２５が増えた場合に、クラスタシステム１は、データの冗長度を自律的に回復する。この冗長度の低下と回復とは、各データへのアクセスが契機である。これにより、アクセスされたデータのみに処理を限定して、処理負荷を低減することができる。
なお、メモリの利用率が閾値を超えたことを契機に、複製データの実データを削除してもよい。メモリの利用率が閾値を下回ったことを契機に、複製データの実データを回復してもよい。
【００５０】
（第２の実施形態）
サーバ２の増減設などでメンバ６１の追加／削除が発生することにより原本データが消失した場合、新たなメンバ６１は、複製データを保持する他のメンバ６１から実データを取得して原本データとして復旧させる。
このような過渡状態において、新たなメンバ６１は、適切な範囲だけ他のメンバ６１を探索しなければならない。探索範囲が適切でないならば、複製データを保持しているメンバ６１のいずれかが探索範囲外になる。ここで、探索範囲内のメンバ６１がメモリ不足により複製データの実データを削除していた場合を考える。この場合、新たなメンバ６１は、クラスタシステム１内に複製データを保持しているメンバ６１が存在するにも関わらず、その複製データを取得できず、そのデータが消失する。
【００５１】
第２の実施形態では、このような追加課題を解決するため、過渡状態時のデータの探索範囲を適切に設定している。これにより、原本データが消失した際に、新たなメンバ６１は、複製データを保持するメンバ６１全てを探索することが可能となる。
【００５２】
図１０（ａ），（ｂ）は、複製データの取得ができない事例を示す説明図である。
図１０（ａ）は、原本データを持つメンバ６１−１の減設と新たなメンバ６１−９の増設とが行われた場合を示している。図１０（ａ）の事例において、冗長度Ｍ＝４である。
増設されたメンバ６１−９は、データの探索範囲Ｈ０を、増設されたメンバ６１の数と減設されたメンバ６１の数との和である増減設数ΔＮとしている。この場合、増設されたメンバ６１−９は、複製データを保持するメンバ６１−２〜６１−４のうちいずれかから複製データの実データを取得する必要がある。しかし、本事例では、メンバ６１−２，６１−３は、メモリ２５の不足が発生している。よって、メンバ６１−２，６１−３は、複製データの実データを削除する。増設されたメンバ６１−９は、メンバ６１−２，６１−３を探索しても、実データを取得できない。
【００５３】
図１０（ｂ）は、データの探索後のＩＤ空間６を示している。
メンバ６１−９は、複製データを取得できない。メンバ６１−２，６１−３は、メモリ２５の不足などにより実データを保持していない。この状態およびこの状態後において、メンバ６１−４がメモリ２５の不足などにより複製データの実データを削除すると、このユーザデータの実データは、クラスタシステム１から消失してしまう。
この課題を解決するため、原本データが消失した際に、新たに原本データを保持するメンバ６１は、複製データを保持するメンバ６１の全てを探索範囲に含めるように、過渡状態時のデータの探索範囲を設定しなければならない。
【００５４】
図１１（ａ），（ｂ）は、第２の実施形態における過渡状態のデータ探索範囲を示す説明図である。
図１１（ａ）は、原本データを持つメンバ６１−１の減設と新たなメンバ６１−９の増設とが行われた場合を示している。
データ探索を行う際の増減設数をΔＮ、冗長度をＭとする。冗長度Ｍとは、あるユーザデータに対する原本データと複製データの総数である。図１１（ａ）において、冗長度Ｍ＝４であり、増減設数ΔＮ＝２である。
データが再配置中である過渡状態において、新たに原本データを保持するメンバ６１−９は、（ΔＮ＋Ｍ−３）＝３の探索範囲に対して、ユーザデータを探索する。メンバ６１−９は、ホップ数３の範囲を探索することで、複製データを保持するメンバ６１−２〜６１−４全てを探索対象とすることができる。
【００５５】
データ探索範囲Ｈ０は、新たに原本を保持するメンバ６１−９から旧複製データを保持する左端のメンバ６１−２への最大ホップ数Ｈ１と、旧複製データを保持する左端のメンバ６１−２から右端のメンバ６１−４への最大ホップ数Ｈ２との和である。
最大ホップ数Ｈ１は、増減設数ΔＮから１を減ずることで求める。ここでは、最大ホップ数Ｈ１＝１である。
最大ホップ数Ｈ２は、旧複製データを保持するメンバ６１の数であり、冗長度Ｍから２を減ずることで求める。ここでは、最大ホップ数Ｈ２＝２である。
よって、データ探索範囲Ｈ０＝（ΔＮ＋Ｍ−３）＝３となる。
新たなメンバ６１−９は、ＩＤ空間６をホップ数３だけ探索することで、複製データを持つ全てのメンバ６１−２〜６１−４を探索できる。
【００５６】
図１１（ｂ）は、データの探索後のＩＤ空間６を示している。
新たなメンバ６１−９は、メンバ６１−４が保持するデータを取得して、新たな原本データとして、これを保持する。これにより、クラスタシステム１からのユーザデータの消失を防止することができる。
【００５７】
以下、データ探索範囲Ｈ０＝（ΔＮ＋Ｍ−３）とすることで、複製データを保持するメンバ６１全てを探索することができることを別事例で説明する。
図１２（ａ），（ｂ）は、データ探索範囲の根拠を示す説明図である。
図１２（ａ）は、データ探索時を示している。
本事例では、冗長度Ｍ＝５とする。各メンバ６１が保持するデータは、図１２（ｂ）に示すデータαの保持メンバリストに従う。
この状態において、原本データを保持するメンバ６１−１が減設し、原本データは一時的に消失する。更にメンバ６１−２，６１−３が増設され、増減設数ΔＮ＝３となる。このとき、メンバ６１−２は、新たに原本データを探索する。
【００５８】
図１２（ｂ）は、メンバ６１−１の減設前におけるデータαの保持メンバリストを示している。
保持メンバリストには、原本データを保持するメンバ６１−１が第１行に記載される。以降、複製データを保持するメンバ６１−４〜６１−７が、第２行〜第５行に記載される。
【００５９】
最初に、新たに原本を保持するメンバ６１−２から、旧複製データを保持する最も近いメンバ６１−４までの最大ホップ数Ｈ１を計算する。
最大ホップ数Ｈ１は、旧原本を保持していたメンバ６１−１から旧複製データを保持する最も近いメンバ６１−４までの区間に、メンバ６１が増設された場合に最大となる。本事例では、メンバ６１−２，６１−３の２台が増設されている。この場合、増減設数ΔＮ＝３である。つまり、増減設数ΔＮから旧原本を保持していたメンバ６１−１を引いた（ΔＮ−１）だけホップすることで、最も近い旧複製データ保持メンバ６１−４へ辿り着くことができる。最大ホップ数Ｈ１は、以下の式（１）となる。
【数１】
0005890452.tif 000002
【００６０】
次に旧複製データを保持する最も近いメンバ６１−４から、旧複製データを保持する最も遠いメンバ６１−７への最大ホップ数Ｈ２を計算する。複製データ保持メンバ数は、（Ｍ−１）である。複製データ保持メンバ数（Ｍ−１）から、旧複製データを保持する左端のメンバ６１−４の１台を引いた（Ｍ−２）だけホップすることで、旧複製データを保持する左端のメンバ６１−４から旧複製データを保持する右端のメンバ６１−７へ辿り着くことができる。最大ホップ数Ｈ２は、以下の式（２）となる。
【数２】
0005890452.tif 000003
【００６１】
新たに原本データを保持するメンバ６１−２から、旧複製データを保持する右端のメンバ６１−７へ探索を行うためのデータ探索範囲Ｈ０は、最大ホップ数Ｈ１，Ｈ２の和であり、以下の式（３）となる。
【数３】
0005890452.tif 000004
【００６２】
本事例においても、メンバ６１−２は、データ探索範囲Ｈ０＝（ΔＮ＋Ｍ−３）＝５により、新たに原本データを保持するメンバ６１−２から旧複製データを保持する右端のメンバ６１−７まで探索することができる。
【００６３】
図１３（ａ），（ｂ）は、複製データ保持メンバの隣接時における通常状態のＩＤ空間を示す説明図である。ここでは、ＩＤ空間６上で連続したメンバ６１の群が原本データおよび複製データを保持する例を示している。
図１３（ａ）は、メンバ６１−１の減設時のＩＤ空間６を示している。
当初、メンバ６１−１は、データαの原本データを保持する。メンバ６１−２，６１−３，６１−４が複製データを保持する。図１３（ｂ）に示す保持メンバリストにより、このデータαを保持する各メンバ６１と冗長度Ｍ＝４とを把握できる。この状態において、データαの原本データを保持するメンバ６１−１が減設し、新たにメンバ６１−９が増設された場合を想定する。
メンバ６１−１の減設に伴い、原本データが消失する。クラスタシステム１は、他のメンバ（新原本保持メンバ）が原本データを保持するように、データを自律的に再配置する。本事例において、データαの新原本保持メンバは、メンバ６１−９と決定される。増設されたメンバ６１−９は、原本データを保持していないため複製データを探索する。この探索処理の詳細は、後記する図１４（ａ），（ｂ）で説明する。
【００６４】
図１３（ｂ）は、ＩＤ空間６上でＩＤが連続したメンバ６１がデータを保持する場合の保持メンバリストの例である。
保持メンバリストには、原本データを保持するメンバ６１−１が第１行に記載される。以降、複製データを保持するメンバ６１−２〜６１−４が、第２行〜第４行に記載される。
【００６５】
図１４（ａ），（ｂ）は、複製データ保持メンバの隣接時におけるデータ探索処理を示す説明図である。
図１４（ａ）は、データ探索時のＩＤ空間６を示している。図１４（ａ）に示すＩＤ空間６は、図１３（ａ）に示したＩＤ空間６の後の状態を示している。
新原本保持メンバであるメンバ６１−９は、ホップ数３の範囲のメンバ６１−２〜６１−４に対して複製データの探索を行い、これらのうちいずれかからデータを取得する。
メンバ６１−９は、取得したデータを原本データとして保持する。以降のデータαの信号処理は、メンバ６１−９が実行する。これによりクラスタシステム１は、サービスを継続して提供することができる。
【００６６】
図１４（ｂ）は、データ探索後の保持メンバリストの例である。
保持メンバリストには、原本データを保持するメンバ６１−９が第１行に記載される。以降、複製データを保持するメンバ６１−２〜６１−４が、第２行〜第４行に記載される。
【００６７】
ＩＤ空間６上で連続しないメンバ６１が原本データおよび複製データを保持するには、ＩＤの値の剰余によりメンバ６１を規定する方法や、ランダムなＩＤ値によりメンバ６１を規定する方法がある。この状態において、データαの原本データを保持するメンバ６１−１が減設し、新たにメンバ６１−９が増設された場合を、図１５・図１６に基づき説明する。
【００６８】
図１５（ａ），（ｂ）は、複製データ保持メンバの非隣接時における通常状態を示す説明図である。
図１５（ａ）は、メンバ６１−１の減設時のＩＤ空間６を示している。
当初、メンバ６１−１は、データαの原本データを保持する。メンバ６１−４，６１−６，６１−８は、複製データを保持する。図１５（ｂ）に示す保持メンバリストにより、このデータαを保持する各メンバ６１と冗長度Ｍ＝４とを把握できる。この状態において、データαの原本データを保持するメンバ６１−１が減設し、新たにメンバ６１−９が増設された場合を想定する。
メンバ６１−１の減設に伴い、原本データが消失する。クラスタシステム１は、他のメンバ（新原本保持メンバ）が原本データを保持するように、データを自律的に再配置する。本事例においても、データαの新原本保持メンバは、メンバ６１−９と決定される。増設されたメンバ６１−９は、原本データを保持していないため複製データを探索する。この探索処理の詳細は、後記する図１６（ａ），（ｂ）で説明する。
【００６９】
図１５（ｂ）は、ＩＤ空間６上でＩＤが連続しないメンバ６１がデータを保持する場合の保持メンバリストの例である。
保持メンバリストには、原本データを保持するメンバ６１−１が第１行に記載される。以降、複製データを保持するメンバ６１−４，６１−６，６１−８が、第２行〜第４行に記載される。
【００７０】
図１６（ａ），（ｂ）は、複製データ保持メンバの隣接時におけるデータ探索処理を示す説明図である。
図１６（ａ）は、データ探索時のＩＤ空間６を示している。図１６（ａ）に示すＩＤ空間６は、図１５（ａ）に示したＩＤ空間６の後の状態を示している。
新原本保持メンバであるメンバ６１−９は、保持メンバリストの１行目に自装置を追加し、この保持メンバリスト上のホップ数３の範囲のメンバ６１−４，６１−６，６１−８に対して複製データの探索を行い、これらのうちいずれかからデータを取得する。
メンバ６１−９は、取得したデータを原本データとして保持する。以降のデータαの信号処理は、メンバ６１−９が実行する。これによりクラスタシステム１は、サービスを継続して提供することができる。
【００７１】
図１６（ｂ）は、データ探索後の保持メンバリストの例である。
保持メンバリストには、原本データを保持するメンバ６１−９が第１行に記載される。以降、複製データを保持するメンバ６１−４，６１−６，６１−８が、第２行〜第４行に記載される。
【００７２】
クラスタシステム１上にて、サーバ２の増減設などでメンバ６１の追加／削除が発生し、原本データが消失した場合、新原本保持メンバを選定して、複製データを保持するメンバ６１のいずれかからデータを取得して原本データとする。この複製データを保持するメンバ６１は、メモリ２５の不足などにより一時的にデータを削除している場合がある。このような場合に、新原本保持メンバは実データを取得できず、救済するべきデータが消失してしまう虞がある。新原本保持メンバは、複製データを保持している全てのメンバ６１に対してデータの探索を行うことが望ましい。
第２の実施形態では、複製データを保持している全てのメンバ６１に対してデータの探索を行う。これにより、過渡状態においても冗長度によらず複製データを持つ全てのメンバ６１に対してデータの探索を行うことができ、データの取得および救済を可能とする。
【００７３】
上記実施形態は、前記したような処理を実行させる装置またはプログラムによって実現することができ、そのプログラムをコンピュータによる読み取り可能な記録媒体（ＣＤ−ＲＯＭなど）に記憶して提供することが可能である。また、そのプログラムを、インターネットなどのネットワークを通して提供することも可能である。
【００７４】
上記実施形態は、コンシステント・ハッシュ法でデータ管理するクラスタシステムに限定されず、データを冗長化して管理するクラスタシステムであればよい。
【符号の説明】
【００７５】
１  クラスタシステム
１Ａ  Ｎ−ＡＣＴシステム  （クラスタシステムの一例）
２，２−１〜２−ｎ  サーバ  （サーバ装置）
２１  信号処理部
２２  メモリ利用率測定部
２３  実データ削除／取得部
２４  記憶部
２４１  信号処理プログラム
２５  メモリ
４，４−１〜４−ｍ  振分装置
４１  振分部
５  ロードバランサ
６  ＩＤ空間
６１，６１−０〜６１−９  メンバ
７，７−１〜７−３  拠点
９  クライアント端末
Ｘ  閾値  （第１の閾値）
Ｙ  閾値  （第２の閾値）
【図１】
0005890452.tif 000005
【図２】
0005890452.tif 000006
【図３】
0005890452.tif 000007
【図４】
0005890452.tif 000008
【図５】
0005890452.tif 000009
【図６】
0005890452.tif 000010
【図７】
0005890452.tif 000011
【図８】
0005890452.tif 000012
【図９】
0005890452.tif 000013
【図１０】
0005890452.tif 000014
【図１１】
0005890452.tif 000015
【図１２】
0005890452.tif 000016
【図１３】
0005890452.tif 000017
【図１４】
0005890452.tif 000018
【図１５】
0005890452.tif 000019
【図１６】
0005890452.tif 000020
【図１７】
0005890452.tif 000021