受信したデータを格納する情報記憶システムであって、ネットワークと、前記ネットワークにより通信可能に接続された複数の情報記憶ノードと、前記複数の情報記憶ノードと通信可能に接続された管理部と、を含み、前記受信したデータのそれぞれは、規定数の同一内容データに複製され、互いにあるいは一方向に対応付けられ、前記複数の情報記憶ノードのいずれかに格納され、前記管理部は、前記複製された同一内容データのそれぞれに対して、それぞれ互いに異なるカテゴリを与え、前記管理部は、前記異なるカテゴリを与えられた同一内容データのそれぞれを格納するための情報記憶ノードを前記複数の情報記憶ノードの中から決定し、前記管理部は、前記格納する情報記憶ノードの決定において、一つの情報記憶ノードが格納する同一カテゴリに属するデータのそれぞれに対応する他の情報記憶ノードに記憶される異なるカテゴリに属する同一内容データは、複数の情報記憶ノードに分散するように、前記決定を行い、前記受信したデータに含まれる情報の一部または全部をカテゴリごとに定めた演算式に代入して前記決定を行い、前記複数の情報記憶ノードにおける第一の情報記憶ノードの使用停止に際して、前記複数の情報記憶ノードのそれぞれは、自身が格納しているデータのうち前記第一の情報記憶ノードに格納されているデータと同一内容であり、かつ、前記自身が格納しているデータが属しているカテゴリと前記第一の情報記憶ノードで属しているカテゴリとが予め対応づけられているデータ、を抽出し、前記抽出したデータを予め定められた手順に従って選択した情報記憶ノードに複製する、情報記憶システム。前記情報記憶システムにおける1つもしくは複数の情報記憶ノード、新たに追加された情報記憶ノード、またはそれらの組み合わせは、前記第一の情報記憶ノードの使用停止に起因する前記複製の後に、前記第一の情報記憶ノードに格納されていたデータと同一内容のデータを、前記情報記憶システムに含まれる複数の情報記憶ノードから集める、請求項1に記載の情報記憶システム。前記管理ノードは、前記規定数の演算式のそれぞれの演算式の演算値と情報記憶ノードとを関連づける管理情報を備え、前記規定数の演算式のそれぞれはハッシュ関数を含み、前記管理ノードは、前記管理情報を参照して、前記受信したデータの前記規定数の演算式によるそれぞれの演算値から、前記規定数の同一内容データのそれぞれを格納する情報記憶ノードを決定する、請求項1又は2に記載の情報記憶システム。前記受信したデータは、第一及び第二のデータ項目からなるデータペアであり、前記管理ノードは、前記データペアにおける前記第一のデータ項目の前記演算式による演算により、当該データペアと同一内容データを格納する前記規定数の情報記憶ノードを決定する、請求項1、2又は3に記載の情報記憶システム。前記規定数は3以上の値であり、前記第一の情報記憶ノードのための前記複製の処理中における第二の情報記憶ノードの使用停止に対して、前記情報記憶ノードは、前記第一及び第二の情報記憶ノードの双方に格納されているデータと同一内容のデータの複製を前記第一及び第二の情報記憶ノードの一方のみに格納されているデータよりも優先して複製する、請求項1~4のいずれかに記載の情報記憶システム。前記複数の情報記憶ノードには、前記演算式の演算値と関連付けられた論理的位置が設定され、前記予め定められた手順は、各情報記憶ノードに対して特定の相対位置にある他の情報記憶ノードにデータを複製することを規定する、請求項1~5のいずれかに記載の情報記憶システム。前記管理ノードは、新たに追加された第三の情報記憶ノードの論理的位置を決定して、前記複数の情報記憶ノードにおける第四の情報記憶ノードの担当範囲の一部を、前記第三の情報記憶ノードに割り当て、前記第三の情報記憶ノードは、前記割り当てられた担当範囲のデータと同一内容データを格納している複数の情報記憶ノードからデータを複製する、請求項6に記載の情報記憶システム。前記規定数の演算式は、受信したユーザデータから互いに異なる代入数を算出し、前記規定数の演算式のそれぞれは、データを格納する情報記憶ノードを決定する演算値の算出において、前記算出した代入数をハッシュ関数に代入する、請求項3に記載の情報記憶システム。ネットワークにより接続された複数の情報記憶ノードを含む情報記憶システムにおけるデータ複製方法であって、前記受信したデータのそれぞれを、規定数の同一内容データに複製し、前記複製された同一内容データのそれぞれに対して、それぞれ互いに異なるカテゴリを与え、前記異なるカテゴリを与えられた同一内容データのそれぞれを格納するための情報記憶ノードを前記複数の情報記憶ノードの中から決定し、前記格納する情報記憶ノードの決定において、一つの情報記憶ノードが格納する同一カテゴリに属するデータのそれぞれに対応する他の情報記憶ノードに記憶される異なるカテゴリに属する同一内容データは、複数の情報記憶ノードに分散するように、前記決定を行い、前記格納する情報記憶ノードの決定において、前記受信したデータに含まれる情報の一部または全部をカテゴリごとに定めた演算式に代入して前記決定を行い、前記複製された同一内容のデータのそれぞれを、前記決定した情報記憶ノードに格納し、前記複数の情報記憶ノードにおける第一の情報記憶ノードの使用停止に際して、前記複数の情報記憶ノードのそれぞれにておいて、当該情報記憶ノードが格納しているデータのうち前記第一の情報記憶ノードに格納されているデータと同一内容であり、かつ、前記情報記憶ノードで属しているカテゴリと前記第一の情報記憶ノードで属しているカテゴリとが予め対応づけられているデータ、を抽出し、前記複数の情報記憶ノードのそれぞれにておいて前記抽出したデータを、予め定められた手順に従って選択された他の情報記憶ノードに複製する、データ複製方法。前記第一の情報記憶ノードの使用停止に起因する前記複製の後に、前記第一の情報記憶ノードに格納されていたデータと同一内容のデータを、前記情報記憶システムに含まれる複数の情報記憶ノードから、前記情報記憶システムにおける1つもしくは複数の情報記憶ノード、新たに追加された情報記憶ノード、またはそれらの組み合わせ、に集める、請求項9に記載のデータ複製方法。前記規定数は3以上の値であり、前記第一の情報記憶ノードのための前記複製の処理中における第二の情報記憶ノードの使用停止に対して、前記第一及び第二の情報記憶ノードの双方に格納されているデータと同一内容のデータの複製を前記第一及び第二の情報記憶ノードの一方のみに格納されているデータよりも優先して複製する、請求項9又は10に記載のデータ複製方法。前記複数の情報記憶ノードには、前記演算式の演算値と関連付けられた論理的位置が設定され、前記予め定められた手順は、各情報記憶ノードに対して特定の相対位置にある他の情報記憶ノードにデータを複製することを規定する、請求項9、10、又は11に記載のデータ複製方法。新たに追加された第三の情報記憶ノードの論理的位置を決定して、前記複数の情報記憶ノードにおける第四の情報記憶ノードの担当範囲の一部を、前記第三の情報記憶ノードに割り当て、前記割り当てられた担当範囲のデータと同一内容データを格納している複数の情報記憶ノードからデータを、前記第三の情報記憶ノードに複製する、請求項12に記載のデータ複製方法。分散データストアにおいては、ノードが追加又は削除された場合に、各データのレプリケーション数を維持することが重要である。レプリケーション数は、複数のノードを含むシステムにおいて、1つのデータが複製されてシステム内のいくつかのノードに格納されている状態において、該当データが格納されているノードの数を意味する、例えば、システムが多数のノードを含み、システム内の3つのノードに格納されているデータはレプリケーション数3の状態である。3つのノードの1つは、オリジナルデータを格納し、他の2つのノードは複製データを格納する。これら3つのノードのうち1つが故障して使用不可能になった場合、当該データを格納するノードの数は1つ減るため、そのデータのレプリケーション数は2に減少する。上述のように、非特許文献1は、コンシステントハッシングの手法を記載している。しかし、非特許文献1のコンシステントハッシングは、情報を1つのノードのみに格納するため、そのノードが故障により使用不能になった場合に、その情報が失われてしまう。非特許文献2は、同じデータをN個のノードに格納する。具体的には、あるコーディネータノードとそれに続くN-1個のノードに同一のデータを格納する。これにより、コーディネータノードが使用不能になっても、それに続くいずれかのノードからデータを読み出すことができる。しかし、コーディネータノードに格納されているオリジナルデータの全ての複製データは、その後続のノードに格納される。そのため、ノードの故障によりレプリケーション数が減少した時にレプリケーション数を回復する処理には、故障ノードの周囲のノードのみが寄与し、故障ノードから離れたノードはその処理に寄与することがない。このため、故障ノードの近辺のノードはレプリケーション数の回復のために、多くのデータを送受信しなくてはならない。このように、非特許文献2においてはレプリケーション数の回復のためにシステム内の少数のノードのみが回復処理に寄与することとなり、システム内で処理量の偏りが発生する。従って、クライアントからの要求を処理するノードが回復処理をしているか否かにより応答時間にばらつきが生じ、システムとしての応答時間にばらつきが出る。また、少数のノードのみで回復処理を行う必要があるため、レプリケーション数が回復するまでに多くの時間がかかる。具体的な例をあげる。ノードの数が1000、各ノードは1Gbpsのネットワークに接続されており、1ノードあたり1TBのオリジナルデータを保持しつまり各ノードの担当範囲には1TBのデータが存在しており、レプリケーション数を3に保っているシステムの例を説明する。それぞれのノードは、1TBのオリジナルデータ、1TBのレプリカ1そして1TBのレプリカ2を持つ。つまり、各ノードの合計データ量は、3TBである。説明のため、1000個のノードのそれぞれに、時計回りにノード1からノード1000までの番号が振られているとする。例えば、ノード1保持しているオリジナルデータこれをノード1の担当範囲のデータと呼ぶことにするの1番目のレプリカがノード2に、2番目のレプリカがノード3に保持されている。言いかえれば、ノード3は、ノード1の2番目のオリジナルデータのレプリカ、ノード2のオリジナルデータの1番目のレプリカ、そしてノード3のオリジナルデータを保持している。つまり、ノード3は、ノード1の担当範囲のデータ、ノード2の担当範囲のデータ、そしてノード3の担当範囲のデータを保持している。同様に、ノード4は、ノード2のオリジナルデータの2番目のレプリカ、ノード3のオリジナルデータの1番目のレプリカ、そしてノード4のオリジナルデータを保持している。他のノードも同様である。ここでノード5が故障により使用不可能になったとする。ノード5の担当範囲は、新しくノード6の担当範囲に付け加わる。つまり、ノード6はノード5のオリジナルデータの1番目のレプリカとして保持していたデータを、ノード6のオリジナルデータとして扱う。ノード6は、さらに、ノード4の2番目のレプリカとして保持していたデータを、ノード4の1番目のレプリカとして扱う。そして、ノード6は、新たにどこかのノードノード3かノード4から、ノード3の担当範囲のデータを複製してきて、そのデータをノード3の2番目のレプリカとして保持する。同様に、ノード7はノード4の担当範囲のデータを、ノード8はノード5の担当範囲のデータを新たに保持する必要がある。ここでは例えばノード3の担当範囲のデータをノード3からノード6に、ノード4の担当範囲のデータをノード4からノード7に、従来ノード5の担当範囲だったデータ現在はノード6の担当範囲の一部のデータをノード6からノード8に複製することとする。これらのもとのレプリケーション数を回復するための処理を単に回復処理と呼ぶこととする。このときノード3は、自身の保持している3TBのデータの3分の1に当たる1TBを、送信しなくてはならない。同様に、ノード4及びノード6も、自身の保持するデータの3分の1にあたる1TBを送信しなくてはならない。さらに、ノード6、ノード7及びノード8は、それぞれ、1TBの新たなデータを受信しなくてはならない。特にノード6の担当範囲は2倍になると共に、ノード3から1TBのデータを受信しつつノード8に1TBのデータを送信しなくてはならず、高負荷状態になってしまうことが多い。また、レプリケーション数3に戻すためにかかる時間は、1TBのデータを転送するために必要な時間である。ネットワークが1Gbpsであることから、約2時間13分を要する。これは、データの冗長化の観点からは非常に長い時間である。もっと早くレプリケーション数を回復することが望ましい。また、一般にハードディスクに代表される外部記憶装置の故障する確率は、負荷が高くなると高くなる。上記回復処理の間、ノード3、ノード4、ノード6及びノード7は、レプリケーション数が2の貴重なデータを保持しているにもかかわらず、それらの記憶装置へのアクセスが高まるつまり記憶装置の負荷が高くなる。負荷が高くなると、故障確率が高くなり。上記ノードのいずれかが故障すると、レプリケーション数が1の1TBデータが発生する。このデータを保持しているノードの負荷はさらに高くなるため、その故障確率がさらに高くなる。その結果、そのノードが故障すれば該当データは永遠に失われる。従って、この故障確率増大の連鎖を断ち切ることが重要である。非特許文献3は、上述のように、k個の異なるハッシュ関数を用いることにより、k個のノードに同一データ1つのオリジナルデータとk-1個のレプリカを格納することを開示する。しかし、この文献は、ノードの追加及び削除について開示しておらず、あるノードが故障により使用不可能になった場合には、そのノードに格納されていたデータのレプリケーション数は、システム全体でk-1に減少する。さらに、k個のノードが故障した場合、システムからデータが失われる。本発明はこのような状況に鑑みてなされたものであって、その1つの目的は、ノードの故障や削除などでレプリケーション数が低下したときにレプリケーション数を迅速に回復することである。上記課題を解決するために、例えば特許請求の範囲に記載の構成を採用する。本願は上記課題を解決する手段を複数含んでいるが、その一例は、受信したデータを格納する情報記憶システムである。この情報記憶システムは、ネットワークと、前記ネットワークにより通信可能に接続された複数の情報記憶ノードと、前記複数の情報記憶ノードと通信可能に接続された管理部とを含む。前記受信したデータのそれぞれは、規定数の同一内容データに複製され、互いにあるいは一方向に対応付けられ、前記複数の情報記憶ノードのいずれかに格納される。前記管理部は、前記複製された同一内容データのそれぞれに対して、それぞれ互いに異なるカテゴリを与える。前記管理部は、前記異なるカテゴリを与えられた同一内容データのそれぞれを格納するための情報記憶ノードを前記複数の情報記憶ノードの中から決定する。前記管理部は、前記格納する情報記憶ノードの決定において、一つの情報記憶ノードが格納する同一カテゴリに属するデータのそれぞれに対応する他の情報記憶ノードに記憶される異なるカテゴリに属する同一内容データは、複数の情報記憶ノードに分散するように前記決定を行い、前記受信したデータに含まれる情報の一部または全部をカテゴリごとに定めた演算式に代入して前記決定を行う。前記複数の情報記憶ノードにおける第一の情報記憶ノードの使用停止に際して、前記複数の情報記憶ノードのそれぞれは、自身が格納しているデータのうち前記第一の情報記憶ノードに格納されているデータと同一内容であり、かつ、前記自身が格納しているデータが属しているカテゴリと前記第一の情報記憶ノードで属しているカテゴリとが予め対応づけられているデータ、を抽出し、前記抽出したデータを予め定められた手順に従って選択した情報記憶ノードに複製する。本発明の一態様によれば、複数の情報記憶ノードを含む情報記憶システムにおいて、データを格納する情報記憶ノードの数が減少した場合に、減少したレプリケーション数を増加するためのデータ複製に必要な時間を短縮することができる。上記以外の課題、構成及び効果は、以下の実施形態の説明により明らかにされる。以下において、本発明を実施するための形態を説明する。説明の明確化のため、以下の記載及び図面は、適宜、省略及び簡略化がなされている。又、各図面において、同一要素には同一の符号が付されており、説明の明確化のため、必要に応じて重複説明は省略されている。<第1の実施の形態>以下において、第1の実施形態を説明する。本実施形態は、分散データストア分散情報記憶システムを説明する。分散データストアにおいて、オリジナルデータが複製され、オリジナルデータと1以上の複製データが、異なる情報記憶ノードに格納される。これにより、高速な処理と高い障害耐性を実現できる。本発明は、2つのデータのペアを単位としてデータを管理するキーバリューストアに特に好適である。そこで、本実施形態においては、キーバリューストアの例を説明する。本発明は、これと異なる分散システムにも適用できる。キーバリューストアは、キーとバリューのペアを格納する。ユーザは、目的のバリューのキーを指定してそのバリュー及びキーを取得する。分散キーバリューストアは、キーの値に応じて、そのオリジナルデータ及びレプリカオリジナルデータを複製したデータの保存先のサーバノードを変える。図1を参照して、本実施形態のシステムがオリジナルデータ及びそのレプリカを格納するノードを決定する方法を説明する。図1は、キーであるデータ東京110の格納先を決定する例を説明する。選択されたサーバは、それぞれ、キーとバリュー不図示のペアオリジナルペア又はびペアの複製を格納する。図1の説明においては、バリューへの言及は省略する。図1は、本実施形態の情報記憶システムに含まれる情報記憶ノード以下においてノードとも呼ぶの論理構成の例を示している。システムは、複数の情報記憶ノードを備えている。図1は、リング状に配置された、情報記憶ノード1101から情報記憶ノード7107の7つの情報記憶ノードを例示している。情報記憶ノードの配置は、データオリジナルデータ及びレプリカを格納する情報記憶ノードを決定するための論理空間におけるノード配置論理位置を示しており、システムにおける情報記憶ノードの物理配置を意味していない。図1は、情報記憶システムが、ユーザデータキー東京110を、システム内の情報記憶ノードに割り当てる方法を模式的に示している。データ東京110のオリジナルノードはノード2102であり、この情報記憶ノードはオリジナルデータ111を格納している。第一レプリカ格納ノードはノード4104であり、第一レプリカデータ東京112を格納している。第二レプリカ格納ノードはノード7107であり、第二レプリカデータ東京113を格納している。情報記憶システムは、ユーザデータの3つのカテゴリオリジナルデータ、第一レプリカ及び第二レプリカのそれぞれのデータを格納する情報記憶ノードを決定するため、3つの異なる演算式を使用する。これら演算式を使用して、ユーザデータから、異なる演算値を得ることができる。好ましい方法として、情報記憶システムは、ハッシュ関数を使用して、オリジナルデータ及び2つのレプリカを割り当てる情報記憶ノードを決定する。ハッシュ関数としては、MD5、SHA-1、SHA-256などがよく知られている。例えば、本実施形態の情報記憶システムは、オリジナルデータ、第一レプリカ、第二レプリカのそれぞれに異なるハッシュ関数を用意し、それぞれのハッシュ関数によるキー本例でデータ東京のハッシュ値により、オリジナルデータ及びレプリカのそれぞれを格納する情報記憶ノードを決定する。若しくは、好ましい方法の一つとして、情報記憶システムは、規定の演算方法例えば異なる値の結合によりキーから異なる3つの値を算出し、その値を同一のハッシュ関数に代入することで、3つの異なるハッシュ値を得ることができる。このように、各データカテゴリオリジナルデータ、第一レプリカ、第二レプリカに対応してキーから異なる値を算出することで、データを格納する情報記憶ノードの決定に必要とするハッシュ関数の種類を少なくすることができる。異なる代入値を算出する方法においても、いくつかのカテゴリには異なるハッシュ関数を適用してもよい。また、ハッシュ関数とは異なる関数を使用して、データを格納する情報記憶ノードを決定してもよい。図1における円情報記憶ノードの論理的な位置を示す線上には、あらかじめ時計回りにハッシュ値の最小値からハッシュ値の最大値までの数が振られている。ハッシュ値は、ある値をハッシュ関数に代入して得られる値である。円上に配置されたノード1101からノード7107は、それぞれ、ハッシュ値の担当範囲を持っている。例えば、ノード2102は、ノード1101からノード2102までの円上のハッシュ値範囲が、担当範囲である。格納データの担当ノードを決定は、例えば、データのハッシュ値に対して、担当範囲と担当ノードを結び付けている表を参照することにより行う。各情報格納ノードの論理位置は、データのカテゴリ毎に異なっていてもよい。任意の2つのデータに関してオリジナルノードが同一であったとしても第一のレプリカ格納ノードは同一であるとは限らず、むしろ多くの場合異なる。同様に第二のレプリカ格納ノードも多くの場合異なる。例えば、データ東京110の第一レプリカ格納ノードはノード4104であり、第二レプリカ格納ノードはノード7107であるが、オリジナル格納ノードがノード2102である他のデータは、第一レプリカ格納ノードとして情報記憶ノード4104と異なるノードに割り当てられ、第二レプリカ格納ノードとして情報記憶ノード7107と異なるノードに割り当てられうる。例えばデータパリはオリジナルノードはノード2であるが、第一のレプリカ格納ノードはノード521であり、第二のレプリカ格納ノードはノード543である。このように、各ノードの複数の異なるオリジナルデータの第一レプリカは、複数の他ノードに分散されて格納される。同様に、複数の異なるオリジナルデータの第二レプリカも、複数の他ノードに分散されて格納される。図1の例において、データ東京110のハッシュ値は、情報記憶ノード1101から情報記憶ノード2102の間に入る。そのため、ノード2102が、データ110のオリジナル格納ノードオリジナルデータを格納するノードである。情報記憶ノード1以外のノードNNは全ノード数以下の自然数の担当範囲は、ノードN-1の担当ハッシュ値範囲のエンド値に1を加算した値から、ノードNの担当ハッシュ値範囲のエンド値までの間である。情報記憶ノード1の担当範囲は、ハッシュ値の最小の値から情報記憶ノード1の担当ハッシュ値のエンド値までの範囲と、最後のノードの担当ハッシュ値のエンド値に1を加算した値からハッシュ値の最大値までの範囲、の両方の範囲をあわせた範囲である。図1において、円で示されるデータ121Aからデータ121Fは、それぞれ、ノード2102が、故障その他の原因によりシステムから外されたことに応答して、各情報記憶ノードが他の情報記憶ノード図1において隣の情報記憶ノードに複製するデータの集合を示している。複製されるデータ121A~データ121Fは、オリジナルデータ、第一レプリカ及び第二レプリカを含む。各情報記憶ノードは、規定の規則に従って、使用が停止される情報記憶ノードに関係するデータを、他の情報記憶ノードに複製する。複製するデータについては後述する。図1の例において、ノード4104における第一レプリカ112は複製されるデータ121Bに含まれるが、ノード7107における第二レプリカ113は複製されるデータ121Eから外れている。図1の例においては、ノード2102を除く図示された情報記憶ノード全てが、データを他の情報記憶ノードに複製するように記載されているが、システム内の全ての情報記憶ノードが、複製すべきデータを持っているとは限らない。各情報記憶ノードは、情報記憶ノードの除去に伴い一時的にデータを複製するための記憶領域を確保する。図1においては、ノード5105で確保された記憶領域124に、例として符号を付している。他の情報記憶ノードも、同様に、複製データを格納する記憶領域を確保する。この記憶領域の利用方法については後述する。このように、情報記憶システムは、ユーザデータと同一の複数のデータを格納する。上記例は、オリジナルデータ、第一レプリカ及び第二レプリカの3つの同一データを格納する。レプリケーション数は、システム設計に依存する。このように、格納される同一の3データは、それぞれ異なるカテゴリオリジナル、第一レプリカ等が与えられ、異なるグループ、つまり、オリジナルデータのグループ、第一レプリカのグループそして第二レプリカのグループに属する。上述のように、1つの情報記憶ノードに格納される任意のカテゴリ例えばオリジナルデータの複数データを考えると、それらに対応する同一の他のカテゴリ例えば第一レプリカの複数データは、他の1つの情報記憶ノードに集中するようなことはなく、複数の情報記憶ノードに分散して格納するように配置する。各データカテゴリのデータの情報記憶ノードの決定に異なる演算式を使用することで、異なるカテゴリの同一データを他の複数の情報記憶ノードに分散して格納する。上述の好ましい演算式は、ハッシュ関数を含む。次に、図2を参照して、本実施形態の情報記憶システムの構成の概要を説明する。図2は、本実施形態の情報記憶システム209及びその周辺機器の構成例を模式的に示すブロック図である。情報記憶システム209は、情報記憶ノードサーバ201、202、203、管理ノード管理サーバ204及び通信制御装置205を備えている。図2は、一例として、3つの情報記憶ノード201、202、203を示しており、実際のシステムは、典型的に、100を超える多くの情報記憶ノードを備える。情報記憶ノード201、202、203、それぞれ、通信制御装置205を介して通信可能に接続されており、さらに、管理ノード204は、情報記憶ノード201、202、203に、通信制御装置205を介して通信可能に接続している。情報記憶システム209は、通信制御装置205により、外部ネットワーク206に接続している。クライアント207、208は、外部ネットワーク206に接続し、通信制御装置205を介して、情報記憶ノード201、202、203及び管理ノード204と通信することができる。本システムにおいて、ユーザは、クライアント207、208を操作して、情報記憶ノード201、202、203にデータを書き込み、そして、情報記憶ノード201、202、203からデータを読み出す。クライアント207、208は、データの書き込みにおいて、ネットワーク206及び通信制御装置205を介して、管理ノード204にキーを送信し、データキーバリューペアを書き込むべき3つノードを示すように要求する。管理ノード204は、クライアント207、208からのキーを伴う要求に応答して、受信したキーの値から規定の演算に従ってデータを格納するノードを決定し、決定したノードの識別子をクライアント207、208に返す。クライアント207、208は、指示されたノードに、オリジナルデータ及びレプリカを送信する。各ノードは、ネットワーク206及び通信制御装置205を介して、データを受信し、それを格納する。これと異なり、オリジナルノードが、第一及び第二のレプリカノードにオリジナルデータの複製第一及び第二のレプリカを格納してもよい。この構成においては、管理ノード204は、クライアント207、208からの格納ノード要求に応答して、オリジナルノードの識別子のみをクライアント207、208に返す。クライアント207、208は、書き込み指示と共にキーバリューペアを指定されたオリジナルノードに送信し、オリジナルノードにキーバリューペアを書き込む格納する。書き込み指示とデータを受信したオリジナルノードは、受信したデータをその記憶デバイスに格納すると共に、第一及び第二レプリカをそれぞれ格納するノードを、上記管理ノード204に問い合わせるか、または管理ノード204と同様の手法により決定する。オリジナルノードは、決定したノードに、通信制御装置205を介して、データ書き込みの指示及びデータを送信する。受信したノードは、それぞれ、データを記憶デバイスに格納する。データの読み出しにおいて、クライアント207、208は、キーを管理ノード204に伝え、データを読み出すべきノードを示すように要求する。管理ノード204は、クライアント207、208からのキーを伴う要求に応答して、そのキーから、規定の演算によりデータを格納しているノードを特定する。管理ノード204は、データを読み出すノードの識別子を、クライアント207、208に返す。クライアント207、208は、管理ノード204から指定されたノードに、キーと共に読み出し要求を送信し、そのノードからキーバリューペアを受信する。上述のように、ユーザは、クライアント207、208を使用して、データの書き込み及び読み出しを行う。図3は、クライアント207の構成を模式的に示すブロック図である。クライアント208は、クライアント207と同様の構成を有している。クライアント207は計算機であり、入力デバイス271、プロセッサ272、ネットワークインタフェース273、ディスプレイ274、主記憶デバイス275及び二次記憶デバイス276を備える。これらは、バス278により通信可能に接続されている。クライアント207は、ネットワークインタフェース273を介して、ネットワーク206に接続し、他の計算機と通信する。ユーザは、入力デバイス271例えばマウス及びキーボードにより必要な情報を入力し、ディスプレイ274により必要な情報を視認することができる。プロセッサ272は、主記憶デバイス275に記憶されているプログラムを実行することによってクライアント207の所定の機能を実現する。主記憶デバイス275は、プロセッサ272によって実行されるプログラム、及び、プログラムの実行に必要なデータを記憶する。プログラムは、不図示のOSOperatingSystemの他、リードライトクライアントプログラム277を含む。プロセッサ272は、複数のチップ及び複数のパッケージを含むことができる。説明の便宜上、リードライトクライアントプログラム277は主記憶デバイス275内に示されているが、典型的には、プログラムは、二次記憶デバイス276の記憶領域から主記憶デバイス275の記憶領域にロードされる。記憶デバイス275、276は、1つの記憶デバイスとして機能することができる。二次記憶デバイス276は、クライアント207の所定の機能を実現するために必要なプログラム及びデータを格納する、不揮発性の永続的記憶媒体を備える記憶装置である。二次記憶デバイス276は、ネットワークを介して接続された外部の記憶装置でもよい。ユーザは、リードライトクライアントプログラム277を使用して、管理ノード204及び情報記憶ノード201、202、203と通信する。リードライトクライアントプログラム277、入力デバイス271によるユーザ入力又は他のプログラムからの入力に応じて、データの書き込み及び読み出しのために必要な情報を管理ノード204又は情報記憶ノード201、202、203に送信し、それらから情報を受信する。ディスプレイ274は、情報記憶ノード201、202、203から受信したデータを表示する。次に、図4を参照して、管理ノード204の構成を説明する。図4は、管理ノード204の構成を模式的に示すブロック図である。管理ノード204は、情報記憶ノード201、202、203及びその処理を管理する計算機である。管理ノード204は、複数の計算機計算機システムで構成されていてもよい。管理ノード204は、情報記憶ノード201、202、203へのアクセスデータ書き込み及びデータ読み出しを管理すると共に、システム内で稼動するノードの追加及び削除に伴う処理を管理する。管理ノード204は、ネットワークインタフェース241、プロセッサ242、主記憶デバイス243及び二次記憶デバイス244を備える。これらは、バス249により通信可能に接続されている。プロセッサ242は、主記憶デバイス243に記憶されているプログラムを実行することによって管理ノード204の所定の機能を実現する。プロセッサ242は、複数のチップ及び複数のパッケージを含むことができる。主記憶デバイス243は、プロセッサ242によって実行されるプログラム及びプログラムの実行に必要なデータを記憶する。プログラムは、不図示のOSの他、ノード管理プログラム245、リードライト管理プログラム246及びデータ再配置管理プログラム247を含む。ノード管理プログラム245は、情報記憶ノードを管理する処理を行い、システムに含まれる情報記憶ノードの担当範囲及びその状態などを管理する。リードライト管理プログラム246は、情報記憶ノードへのデータ書き込み及びデータ読み出しノードへアクセスを管理する処理を行う。データ再配置管理プログラム247は、ノードの追加削除に伴うノード間のデータ再配置を管理する。これらプログラム245~247が行う処理の詳細は後述する。説明の便宜上、図4において、プログラム245~247は主記憶デバイス243内に示されている。典型的には、プログラムは、二次記憶デバイス244の記憶領域から主記憶デバイス243の記憶領域にロードされる。記憶デバイス243、244は、1つの記憶デバイスとして機能することができる。二次記憶デバイス244は、図示するノード管理テーブル248の他、管理ノード204の所定の機能を実現するために必要なプログラム及びデータを格納する、不揮発性の永続的記憶媒体を備える記憶デバイスである。ノード管理テーブル248については、図6を参照して後述する。二次記憶デバイス244は、ネットワークを介して接続された外部の記憶デバイスでもよい。管理ノード204は、リードライトクライアントプログラム277を実行し、入出力装置を介してユーザ操作を受け付けてもよい。次に、図5を参照して、情報記憶ノード201の構成を説明する。他の情報記憶ノード202、203も、情報記憶ノード201と同一構成を有しており、説明を省略する。図5は、情報記憶ノード201の構成を模式的に示すブロック図である。情報記憶ノードサーバ201は、キーバリューペアを格納する計算機である。情報記憶ノードは複数の計算機を含んでいてもよい。情報記憶ノード201は、ネットワークインタフェース211、プロセッサ212、主記憶デバイス213及び二次記憶デバイス214を備える。これらは、バス215により通信可能に接続されている。プロセッサ212は、主記憶デバイス213の記憶領域に記憶されているプログラムを実行することによって情報記憶ノード201の所定の機能を実現する。主記憶デバイス213は、プロセッサ212によって実行されるプログラム及びプログラムの実行に必要なデータを記憶する。プログラムは、不図示のOSの他、リードライト処理プログラム216及びデータ再配置処理プログラム217を含む。プロセッサ212は、複数のチップ及び複数のパッケージを含むことができる。リードライト処理プログラム216は、クライアント207、208からの要求に応じたデータの書き込み及び読み出しの処理を行う。データ再配置処理プログラム217は、システム内のノードの削除追加に伴うノード間でのデータ再配置の処理を行う。これらプログラム216、217が行う処理の詳細は後述する。説明の便宜上、図5において、プログラム216、217は主記憶デバイス213内に示されている。典型的には、プログラムは、二次記憶デバイス214の記憶領域から主記憶デバイス213の記憶領域にロードされる。記憶デバイス213、214は1つの記憶デバイスとして機能することができる。二次記憶デバイス214は、図示するデータ格納テーブル218の他、情報記憶ノード201の所定の機能を実現するために必要なプログラム及びデータを格納する、不揮発性の永続的記憶媒体を備える記憶デバイスである。データ格納テーブル218については、図7を参照して後述する。二次記憶デバイス214は、ネットワークを介して接続された外部の記憶デバイスでもよい。上述のように、プログラムはプロセッサによって実行されることで、定められた処理を記憶装置及び通信ポート通信デバイスを用いながら行う。従って、本実施形態及び他の実施形態においてプログラムを主語とする説明は、プロセッサを主語とした説明でもよい。若しくは、プログラムが実行する処理は、そのプログラムが動作する計算機が行う処理である。プロセッサは、プログラムに従って動作することによって、所定の機能を実現する機能部として動作する。プログラムの少なくとも一部は、専用ハードウェアによって実現されてもよい。プログラムは、プログラム配布サーバや、計算機読み取り可能な永続的記憶媒体によって各計算機にインストールすることができ、各計算機の不揮発性記憶装置に格納することができる。図6は、管理ノード204が格納しているノード管理テーブル248の一例を示す図である。ノード管理テーブル248は、ノード管理プログラム245管理ノード204が各情報記憶ノードを管理する、具体的には、各情報記憶ノードの担当ハッシュ値範囲及び生死状態を管理するためのテーブルである。各行レコードは、1つのノードについての情報を格納しており、本例のノード管理テーブル248は、1000ノードを管理している。つまり、本情報記憶システム209は、1000のノードを含む。ノード名のカラム601は、各ノードのノード名を格納する。具体的には、行エントリ604は、ノード名がノード1であるノードに関する記述である。行605は、ノード名がノード2であるノードに関する記述である。行606は、ノード名がノード3であるノードに関する記述である。行607は、ノード名がノード4であるノードに関する記述である。行608は、ノード名がノード5であるノードに関する記述である。行609は、ノード名がノード6であるノードに関する記述である。行610はノード名がノード7であるノードに関する記述である。行611は、ノード名がノード8であるノードに関する記述である。行612は、ノード名がノード9であるノードに関する記述である。行613はノード名がノード10であるノードに関する記述である。行614は、ノード名がノード11であるノードに関する記述である。行615は、ノード名がノード12であるノードに関する記述である。行616は途中のエントリが、図6において省略されていることを示す。行617は、ノード名がノード999であるノードに関する記述である。行618は、ノード名がノード1000であるノードに関する記述である。担当ハッシュ値範囲のエンド値のカラム602は、各ノードが担当するハッシュ値範囲の最後の値を格納している。具体的には、ノード1の担当ハッシュ値範囲のエンド値は、226である。ノード2の担当ハッシュ値範囲のエンド値は535である。ノード1の担当ハッシュ値範囲のエンド値は226であることから、ノード2の担当ハッシュ値範囲は、ノード1のエンド値226の次の数である227から535であることを意味している。同様にノード名がノード3であるノードの担当ハッシュ値範囲のエンド値は842である。ノード3の担当ハッシュ値範囲は536から842であることを意味する。以下同様にノード名がノード4であるノードの担当ハッシュ値範囲のエンド値は、1231である。ノード名がノード5であるノードの担当ハッシュ値範囲のエンド値は、2145である。ノード名がノード6であるノードの担当ハッシュ値範囲のエンド値は、2352である。ノード名がノード7であるノードの担当ハッシュ値範囲のエンド値は3125である。ノード名がノード8であるノードの担当ハッシュ値範囲のエンド値は4231である。ノード名がノード9であるノードの担当ハッシュ値範囲のエンド値は4845である。ノード名がノード10であるノードの担当ハッシュ値範囲のエンド値は、5252である。ノード名がノード11であるノードの担当ハッシュ値範囲のエンド値は、6625である。ノード名がノード12であるノードの担当ハッシュ値範囲のエンド値は、6752である。ノード名がノード999であるノードの担当ハッシュ値範囲のエンド値は、64523である。ノード名がノード1000であるノードの担当ハッシュ値範囲のエンド値は、65123である。生死情報のカラム603は、各ノードの生死状態を示す情報を格納する。具体的には、各ノードが、生きているALIVE状態、死んでいるDEAD状態又は置き換えられた状態SUBSTITUTED状態であるかを示す。ALIVE状態は、情報記憶ノードが正常動作していることを示す。DEAD状態は、情報記憶ノードが故障又は他の理由により正常動作しておらずアクセスを受け付けないと共に、その担当データが、他の情報記憶ノードに再配置されていない再配置前であることを意味する。SUBSTITUTED状態の記憶ノードは、DEAD状態になったあとに、その担当データが他のALIVE状態の情報記憶ノードに再配置されていることを意味する。ALIVE状態の情報記憶ノードは、故障又は他の理由によりDEAD状態になり、その後、担当データが他の情報記憶ノードに再配置されると、SUBSTITUTED状態に変化する。これらの状態及び状態変化の詳細は後述する。本例のノード管理テーブル248において、ノード名がノード1であるノードの生死情報は、ALIVEである。ノード名がノード2であるノードの生死情報は、ALIVEである。ノード3であるノードの生死情報はALIVEである。ノード名がノード4であるノードの生死情報は、ALIVEである。ノード名がノード5であるノードの生死情報は、ALIVEである。ノード名がノード6であるノードの生死情報は、ALIVEである。ノード名がノード7であるノードの生死情報は、ALIVEである。ノード名がノード8であるノードの生死情報は、ALIVEである。ノード名がノード9であるノードの生死情報は、DEADである。ノード名がノード10であるノードの生死情報は、ALIVEである。ノード名がノード11であるノードの生死情報は、SUBSTITUTEDである。ノード名がノード12であるノードの生死情報は、ALIVEである。ノード名がノード999であるノードの生死情報は、ALIVEである。ノード名がノード1000であるノードの生死情報は、ALIVEである。図7は、情報記憶ノードが有するデータ格納テーブル218の例を示す図である。データ格納テーブル218は、情報記憶ノードが格納しているキーバリューペアのそれぞれの値に加え、そのキーバリューペアを格納する格納ノードを、そのキーバリューペアに関連付けて格納している。図7は、図1における情報記憶ノード2102が保持しているデータ格納テーブル218を例示してある。キーのカラム701は、該当項目のキーを示す列である。行エントリ706は、キーが東京であるペアに関する記述である。行707は、キーがパリであるペアに関する記述である。行708は、キーがロンドンであるペアに関する記述である。行709は、キーがベルリンであるペアに関する記述である。行710は、キーがワシントンであるペアに関する記述である。行711は、キーがサンノゼであるペアに関する記述である。行712は、キーが上海であるペアに関する記述である。行713は、図7において途中のエントリが省略されていることを示す。行714は、キーが広島であるペアに関する記述である。行715は、キーが長崎であるペアに関する記述である。オリジナル格納ノードのカラム702は、オリジナルデータが格納されているノード名を記述する。例えば、キーが東京であるペアのオリジナル格納ノードは、ノード2である。キーがパリであるペアのオリジナル格納ノードは、ノード2である。キーがロンドンであるペアのオリジナル格納ノードは、ノード2である。キーがベルリンであるペアのオリジナル格納ノードは、ノード2である。キーがワシントンであるペアのオリジナル格納ノードは、ノード62である。キーがサンノゼであるペアのオリジナル格納ノードは、ノード4である。キーが上海であるペアのオリジナル格納ノードは、ノード475である。キーが広島であるペアのオリジナル格納ノードは、ノード754である。キーが長崎であるペアのオリジナル格納ノードは、ノード352である。第一レプリカ格納ノードのカラム703は、第一レプリカが格納されているノード名を記述する。例えば、キーが東京であるペアの第一レプリカ格納ノードは、ノード4である。キーがパリであるペアの第一レプリカ格納ノードは、ノード521である。キーがロンドンであるペアの第一レプリカ格納ノードは、ノード36である。キーがベルリンであるペアの第一レプリカ格納ノードは、ノード965である。キーがワシントンであるペアの第一レプリカ格納ノードは、ノード2である。キーがサンノゼであるペアの第一レプリカ格納ノードは、ノード2である。キーが上海であるペアの第一レプリカ格納ノードは、ノード234である。キーが広島であるペアの第一レプリカ格納ノードは、ノード854である。キーが長崎であるペアの第一レプリカ格納ノードは、ノード120である。第二レプリカ格納ノードのカラム704は、第二レプリカが格納されているノード名を記述する。例えば、キーが東京であるペアの第二レプリカ格納ノードはノード7である。キーがパリであるペアの第二レプリカ格納ノードはノード543である。キーがロンドンであるペアの第二レプリカ格納ノードはノード339である。キーがベルリンであるペアの第二レプリカ格納ノードはノード145である。キーがワシントンであるペアの第二レプリカ格納ノードはノード695である。キーがサンノゼであるペアの第二レプリカ格納ノードはノード305である。キーが上海であるペアの第二レプリカ格納ノードはノード2である。キーが広島であるペアの第二レプリカ格納ノードはノード2である。キーが長崎であるペアの第二レプリカ格納ノードはノード2である。バリューのカラム705は、キーのバリュー値を格納する。例えば、キーが東京であるペアのバリューは晴れである。キーがパリであるペアのバリューは雨である。キーがロンドンであるペアのバリューは曇りである。キーがベルリンであるペアのバリューは雪である。キーがワシントンであるペアのバリューは晴れである。キーがサンノゼであるペアのバリューは晴れである。キーが上海であるペアのバリューは快晴である。キーが広島であるペアのバリューは曇りである。キーが長崎であるペアのバリューは雨である。図8は、図1における情報記憶ノード4104のデータ格納テーブル218を示す図である。キーのカラム801は、各エントリのキーを格納する。行エントリ806はキーがサンノゼであるペアに関する記述である。行807はキーが東京であるペアに関する記述である。行808はキーがオタワであるペアに関する記述である。行809はキーがワシントンであるペアに関する記述である。行810は、それ以降のエントリが省略されている旨を示す。オリジナル格納ノードのカラム802は、オリジナルデータが格納されているノード名を記述する。例えば、キーがサンノゼであるペアのオリジナル格納ノードはノード4である。キーが東京であるペアのオリジナル格納ノードはノード2である。キーがオタワであるペアのオリジナル格納ノードはノード475である。キーがワシントンであるペアのオリジナル格納ノードはノード62である。第一レプリカ格納ノードのカラム803は、第一レプリカを格納するノード名を記述する。例えば、キーがサンノゼであるペアの第一レプリカ格納ノードはノード2である。キーが東京であるペアの第一レプリカ格納ノードはノード4である。キーがオタワであるペアの第一レプリカ格納ノードはノード4である。キーがワシントンであるペアの第一レプリカ格納ノードはノード2である。第二レプリカ格納ノードのカラム804は、第二レプリカが格納されているノード名を記述する。例えば、キーがサンノゼであるペアの第二レプリカ格納ノードはノード305である。キーが東京であるペアの第二レプリカ格納ノードは、ノード7である。キーがオタワであるペアの第二レプリカ格納ノードは、ノード256である。キーがワシントンであるペアの第二レプリカ格納ノードは、ノード4である。バリューのカラム805は、キーのバリュー値を格納する。例えば、キーがサンノゼであるペアのバリューは、晴れである。キーが東京であるペアのバリューは、晴れである。キーがオタワであるペアのバリューは、快晴である。キーがワシントンであるペアのバリューは、晴れである。上述のように、管理ノード204は、ノード管理テーブル248を使用して処理を行い、情報記憶ノード201、202、203はデータ格納テーブル218を使用して処理を行う。本実施形態及び他の実施形態において、情報記憶システムが使用する情報ノード管理のための情報や格納しているデータに関する情報などは、データ構造に依存せずどのようなデータ構造で表現されていてもよい。例えば、テーブル、リスト、データベースあるいはキューから適切に選択したデータ構造体が、情報を格納することができる。情報記憶システムが使用する情報は、データ記憶装置における対応するデータ記憶領域に格納される。以下において、情報記憶システム209が行う処理を、図9~図17のフローチャートを参照して説明する。図9及び図10は、正常動作していたノードNが、故障その他の理由により死んだ場合の処理例を示している。図11及び図12は、情報記憶システム209の情報記憶ノードにデータを書き込む処理の例を示している。図13~図15は、情報記憶システム209の情報記憶ノードからデータを読み出す処理の例を示している。図16及び図17は、ノードNNはノードの番号とノードN1の間にノードXを挿入する処理の例を示す。情報記憶ノード使用停止まず、図9を参照して、ノードNが死んだときの情報記憶システム209の行う処理を説明する。情報記憶ノードが死ぬと、その情報記憶ノードが格納しているデータ典型的に、複数オリジナルデータ、複数第一レプリカ及び複数第二レプリカを含むのそれぞれのレプリケーション数が、規定値本例において3から1だけ減少する。本情報記憶システム209は、減少したレプリケーション数を規定値に戻すため、死んだ情報記憶ノードに格納されていたデータその担当データと同一のデータを、他の情報記憶ノードに複製させることで、死んだ情報記憶ノードに格納されていたデータの再配置を行い、減少したレプリケーション数を規定値に戻す。図9は、ノードNが死んだときの情報記憶システム209の処理例を、管理ノード204の処理を中心にフローチャートに示した図である。ステップS901において、管理ノード204のノード管理プログラム245は、ノードNが死んだことを検知する。ノードNが死んだことを検知する技術は広く知られているので詳細な説明を省略するが、典型的には、ノード管理プログラム245は、各情報記憶ノードに死活監視のための応答要求を送信し、その要求への正常応答を受信しない場合に、情報記憶ノードが死んでいると判定する。ステップS902において、ノード管理プログラム245は、ノード管理テーブル248において、ノードNのエントリにおける生死情報フィールドの値を、ALIVEからDEADに変更する。ノード管理プログラム245は、管理ノード204のデータ再配置管理プログラム247に、ノードNがDEAD状態になったことを通知する。ステップS903において、データ再配置管理プログラム247は、ノード管理テーブル248を参照して、生死のフィールドがALIVEの情報記憶ノードを特定し、それらの情報記憶ノードに、自身の格納しているデータのうちノードNに関係するデータを抽出し、自身の時計回り隣の情報記憶ノード隣のALIVE状態の情報記憶ノードに、その抽出したデータを複製することを指示する命令を送信する。図示していないが、管理ノード204は各情報記憶ノードのアドレスを有しており、上記特定した情報記憶ノードのアドレスに上記指示を送信する。管理ノード204は、各ALIVE状態の情報記憶ノードに、データ複製先の隣のALIVEの情報記憶ノードを指定する情報を送ってもよいし、隣の情報記憶ノードがALIVE状態ではない情報記憶ノードにのみ、その情報を送ってもよい。若しくは、各情報記憶ノードは、ノード管理テーブル248の複製を管理ノード204から定期的に及び/又は更新時に取得し、保持していてもよい。ステップS904において、データ再配置管理プログラム247は、全ての情報記憶ノードの複製作業が終わるまで待つ。各情報記憶ノードは、データ格納テーブル218を参照して、死んだノードNに関係するデータを特定することができる。情報記憶ノードによる関係データ抽出処理の詳細は、図10のフローチャートを参照して後述する。全ての情報記憶ノードの複製作業が終了すると、ノードNに格納されていたそれぞれのデータのレプリケーション数は、減少した値である2から規定値の3に戻る。各情報記憶ノードは、複製作業が終了すると、それを管理ノード204に通知する。ステップS905において、データ再配置管理プログラム247は、全ての情報記憶ノードの複製作業の終了通知を受信すると、ノード管理テーブル248におけるノードNのエントリの生死フィールドを、DEADからSUBSTITUTEDに変更する。次に、ステップS906において、データ再配置管理プログラム247は、ノードNの時計回りにおいて隣のノードN1に、データの収集を指示する。具体的には、ノードN1に、ノードNが担当していたデータオリジナルデータ、第一レプリカ及び第二レプリカを、ノード管理テーブル248の生死のフィールドがALIVEの情報記憶ノードから集めるように指示する。具体的には、管理ノード204は、ALIVE状態の情報記憶ノードの識別子を伴うデータ収集の指示を、ノードN1に送信する。ノードN1のデータ再配置処理プログラム217は、管理ノード204からの指示に応答して、ノードNの担当データの収集を開始する。具体的には、データ再配置処理プログラム217は、管理ノード204からの指示が示すALIVE状態の情報記憶ノードに対して、複製したデータS903における関系するデータを、ノードN1に送信するように要求する。要求を受けた各情報記憶ノードは、要求元のノードN1に複製したデータノードNが格納担当していたデータと同一のデータを送信する。その後、データ格納テーブル218におけるノードNのフィールドをノードN1に変更する。なおこの動作はS907実行後にデータ再配置管理プログラム247から指示されることにより実行する形態としても良い。ステップS907において、ノードNの時計回りにおいて隣のノードN1が、ノードNが担当していたすべてのデータを集めたらその通知をノードN1のデータ再配置処理プログラム217から受信したら、データ再配置管理プログラム247は、ノード管理テーブル248のノードNのエントリを削除する。データ再配置管理プログラム247は、ノードNのエントリにおける生死フィールドを、SUBSTITUTEDからDELETEDに変更してもよい。以上の処理によりノードNが死んだときの情報記憶システム209の行うべき処理を遂行することができる。次に、図10を参照して、情報記憶ノードが自分の持っているデータのうち関係するデータを抽出する処理の説明を行う。この処理は、図9のフローチャートにおけるステップS904で行われる。関係するデータは、情報記憶ノードが所有しているデータのうち、他の情報記憶ノードが死んだことにより自身が隣の情報記憶ノードに複製を転送しなくてはならないデータである。図10は、情報記憶ノードが持っているデータのうち、関係するデータを抽出する処理例のフローチャートを示す図である。ステップS1001において、情報記憶ノードのデータ再配置処理プログラム217は、データ格納テーブル218からオリジナルノードが死んだノードNであり、第一レプリカ格納ノードが自身であるエントリを抽出する。ステップS1002において、データ再配置処理プログラム217は、データ格納テーブル218から、第一レプリカ格納ノードが死んだノードNで、第二レプリカ格納ノードが自身であるエントリを抽出する。ステップS1003において、データ再配置処理プログラム217は、データ格納テーブル218から、第二レプリカ格納ノードが死んだノードNであり、オリジナルノードがそれ自身であるエントリを抽出する。ステップS1004において、データ再配置処理プログラム217は、上記ステップS1001~ステップS1003の3工程で抽出したエントリを関係するデータとしてまとめて、主記憶装置213に格納する。以上の処理により、情報記憶ノードが、自分の持っているデータのうち関係するデータを抽出することができる。以上が情報記憶ノードの削除に伴うデータ再配置の処理の流れであるが、この処理をよりわかりやすく説明するため、例として、情報記憶ノード2が死んだときの処理つまり情報記憶ノード2がALIVE状態からDEAD状態になり、そしてSUBSTITIUTED状態になるまでの処理を説明する。最初にステップS901において、管理ノード204のノード管理プログラム245が、ノード2が死んだことを検知する。ステップS902において、ノード管理プログラム245は、ノード管理テーブル248のノード2の生死のフィールドをALIVEからDEADに変更する。ステップS903において、ノード管理テーブル248の生死のフィールドがALIVEの情報記憶ノードに、それ自身が持っているデータのうち関係するデータを抽出して、それ自身の時計回りに隣の情報記憶ノードに複製する、ことを指示する。以下において、一例として、ノード4の処理を説明する。抽出する処理の詳細は、図10のフローチャートを参照して説明した。ノード4のデータを格納しているデータ格納テーブル218は、図8に示した。具体的に説明する。以下において図10を参照して説明する処理は、ノード4のデータ再配置処理プログラム217により実行される。図10のフローチャートにおけるステップS1001において、ノード4は、図8のデータ格納テーブル218から、オリジナルノードが死んだノード2で、第一レプリカ格納ノードが自分情報記憶ノード4であるエントリを抽出する。例えば、キーが東京のエントリ807が、抽出される。これは、図1におけるデータ東京112である。ステップS1002において、ノード4は、データ格納テーブル218から、第一レプリカ格納ノードが死んだノード2であり、第二レプリカ格納ノードが自分情報記憶ノード4であるエントリを抽出する。例えば、キーがワシントンのエントリ809が、抽出される。ステップS1003において、ノード4は、データ格納テーブル218から第二レプリカ格納ノードが死んだノード2であり、オリジナルノードが自分ノード4であるエントリを抽出する。行810が示す省略されたエントリを除いて、明示されているエントリに、そのようなエントリは存在しない。ステップS1004において、ノード4は、上記ステップS1101からステップS1103の3工程で抽出したエントリをまとめ、関係するデータとして主記憶装置の記憶領域に格納する。つまり、ノード4は、東京キーとするデータ及びワシントンをキーとするデータを、関係するデータとして抽出する。このデータは、図1におけるデータ集合121Bに相当する。本例において、ノード4は、これらの抽出データを、時計回りに隣のノードに複製する。つまり、ノード4はノード5にそれらデータを複製する。これは、図1におけるデータ集合121Bを記憶領域124に複製することを意味する。ノード5は、記憶領域124をあらかじめ確保しておいてもよいし、複製作業を行う際に動的に確保してもよい。あらかじめ確保しておく場合は、ノード5は、それを、ノード4のオリジナルノードが、死んだノード2のデータのための領域として確保しておいてもよいし、ノード4から複製される何らかの複製データのための領域として確保しておいてもよい。若しくは、どこかの情報記憶ノードから何らかの複製データを複製してくるための領域として確保しておいてもよい。なお、図1は、このとき同様に複製されるデータの例として、ノード3からノード4に複製されるデータ、ノード5からノード6に複製されデータ、ノード6からノード7に複製されるデータ、そしてノード1からノード3に複製されるデータも示している。上述のように、本システムにおいて、一つの情報記憶ノードが保持する任意カテゴリのデータ集合と同一の、他のカテゴリのデータ集合は、他の1つの情報記憶ノードに集中しておらず、複数の情報記憶ノードに分散して格納されている。特に、ハッシュ関数のように偏りの小さい関数を使用することで、1つの情報記憶ノードに格納されているデータを、他の全ての情報記憶ノードに平均的に割り当てることができる。このシステムにおいて、ノード2は3TBのデータを持っているとする。ノード2が死んだとき、上記例のノード4などノード2以外の情報記憶ノードがノード2に関係するデータとして持っているデータ量は、3TBの1000分の11000は全ノード数である3GBである。ステップS903において、各情報記憶ノードは、これを隣の情報記憶ノードに複製する。ネットワークが1Gbpsであれば、複製における転送時間は約24秒である。つまり、レプリケーション数を2から3に戻すまでにかかる時間は、従来例に比べて、約1/333となる。さらに、上記処理において、一部の情報記憶ノードのみに負荷が集中せず、負荷はシステム全体で一様に発生するため、クライアントからの要求に対して、従来例のような原因による応答のばらつきが出ることはない。また、複製処理による情報記憶ノードの故障発生の蓋然性を低減することができる。上記処理は、複数情報記憶ノードによるデータ複製の後に、ノードN1が、ノードNの担当データを集める。すでにレプリケーション数が回復されているため、ノードN1は、そのデータ収集を、システムの状況に応じて行うことができる。このように、本実施形態は、システム内のデータを格納するノードの数が減少した場合に、レプリケーション数を回復するまでに必要な時間を従来よりも短縮することが可能である。または、レプリケーション数を回復するまでのシステムの負荷集中を抑えることができる。または、システムが定常状態に戻るまでの間、システムの応答時間のばらつきを従来よりも平準化させることが可能である。図10を参照して説明したように、情報記憶ノードは、使用停止ノードに関係するデータを、予め設定されている規則に従って抽出する。この規則は、データの各カテゴリを他のカテゴリに関連付ける。情報記憶ノードは、使用停止ノードにおいて格納されている各データのカテゴリを特定し、そのカテゴリに関連付けられているカテゴリのデータを、他の情報記憶ノードに複製する。上記例においては、オリジナルデータのカテゴリは第一レプリカのカテゴリに関連付けられ、第一レプリカのカテゴリは第二レプリカのカテゴリに関連付けられ、第二レプリカのカテゴリはオリジナルデータのカテゴリに関連付けられている。この関連付けは一例であって他の対応関係でもよい。上記構成は、ノードNが死んだことを検知して、それを使用不能ノードと判定して、その情報記憶ノードの使用を停止する。これと異なり、管理ノード204は、ノードNのレスポンスタイムが閾値よりも長くなったことを検知してもよいし、ノードNのCPU負荷が閾値よりも高くなったことを検知してもよい。若しくは、他の通常状態とは異なる状態を検知してもよい。上記構成は、ノードNが死んだことを検知してノードNを使用不能ノードと判定するが、ノードN以外の情報記憶ノードの状態から、ノードNを使用不能ノードと判定してもよい。例えば、情報記憶システムは、ノードNが特定のノードグループGに属している場合に、そのノードグループGが通常とは異なる状態になったことを検知して、ノードN又はノードグループGに属する一つ以上の情報記憶ノードを使用不能ノードと判定し、複製処理を行ってもよい。情報記憶システムは、ノードNが通常とは異なる状態になったことを検知して、ノードグループGの一部又は全ての情報記憶ノードを使用不能ノードと判定し複製処理を行ってもよい。上記例において、ノードNは不測の故障により死んだが、ノードNが計画停止する場合も、上記データ複製処理を同様に適用することができる。この場合、ステップS901からステップS907までの間に、ノードNが動作していてもよい。ノードNの使用は、その後停止される。上記処理において、各情報記憶ノードは、論理的に隣の位置にある情報記憶ノードに対して、ノードNに関係するデータを複製する。各情報記憶ノードがデータを複製する情報記憶ノードの相対論理位置は、他の位置であってもよい。例えば、一つおきや二つおきなどしてもよいし、論理円上の反対側の情報記憶ノードでもよい。何らかの関数fを用いてデータ複製先の情報記憶ノードを決定してもよい。複製した先のノードを後で知ることができるのであれば、情報記憶ノードは、乱数を使って複製する先の情報記憶ノードを決定する、各情報記憶ノードの負荷を考慮し負荷の小さい情報記憶ノードに複製するなどの決定方法を使用してもよい。この場合、複製元のノード名またはノードIDから複製先のノード名またはノードIDを知ることができるよう、テーブルを設ければよい。情報記憶ノードの使用停止に伴うデータの複製複製データの抽出及び他の情報記憶ノードへの複製は、情報記憶ノードが自律的に行うことが好ましい。これにより、迅速かつ効率的に処理を行うことができる。これと異なり、管理ノード204が、各情報記憶ノードに複製先の情報記憶ノードを指示してもよい。上記構成において、各情報記憶ノードは、規定の相対位置にある情報記憶ノードにノードNに関係するデータを複製する。複製先の情報記憶ノードが、複製データと同一データを格納していることがある。この場合、同一データのレプリケーション数は2のままであり、3には戻らない。そのため図11を用いて後述する方法と同様の方法を用いて新たな複製先ノードを決定する。これによりレプリケーション数3を確保する。複製先ノードが同一データを格納している可能性発生頻度は小さいため、同一データの有無にかかわらず規定の情報記憶ノードにデータを複製してもよい。これと異なり、情報記憶ノードは、規定相対位置の情報記憶ノードが同一データを格納している場合、それとは異なる情報記憶ノード、例えば、同一データを格納する情報記憶ノードの隣の情報記憶ノードにデータを複製してもよい。情報記憶ノードは、データ格納テーブル218を参照することで、複製対象のデータと同一データを格納する情報記憶ノードを特定することができる。上記構成において、ノードNの時計回りに隣のノードN1がノードNの担当範囲を、新たに担当する。これと異なり、例えば、予備として取ってあったノードXをノードNの代わりに追加し、そのノードXが、情報記憶ノードNが元々担当していたデータを集めて、その後、ノードXが、ノードNが元々担当していた処理を行ってもよい。これにより、情報記憶システムを、ノードNの使用停止前の状態に戻すことができる。既存の複数情報記憶ノード又は新たに追加された情報記憶ノードを含む複数情報記憶ノードが、データを集めてもよい。上記例において、ノードN1は、データを複製した情報記憶ノードから、複製したデータと同一データを取得する。ノードN1は、どの情報記憶ノードからノードNの担当データを集めてもよい。例えば、ノードN1は、複製先の情報記憶ノードから、その記憶領域例えば図1におけるノード5の記憶領域124に格納されているデータを取得することができる。この他、情報記憶システム209は、複数情報記憶ノードにより使用停止ノードに関係するデータを複製した後レプリケーション数を回復した後、1つの情報記憶ノードに使用停止ノードの担当データを集めることなく処理を終了してもよい。データ書き込み以下において、図11及び図12を参照して、情報記憶システム209にデータを書き込む処理を説明する。まず、図11を参照して、管理ノード204のリードライト管理プログラム246が、キーの値からデータを格納する書き込む情報記憶ノードを決定する処理を説明する。図11は、リードライト管理プログラム246が、キーの値から格納ノードを決定する処理のフローチャートを示す。ステップS1101において、リードライト管理プログラム246は、規定のハッシュ関数及びクライアントから受信したキーから、キーのハッシュ値を計算する。さらに、リードライト管理プログラム246は、そのハッシュ値を用いて、ノード管理テーブル248においてオリジナルノードを検索する。リードライト管理プログラム246用いるハッシュ関数として、例えば、MD5、SHA-1、SHA-256などのうち1つまたは複数の組み合わせの関数を用いることができる。これらとは異なる関数を使用してもよい。ステップS1102において、リードライト管理プログラム246は、キーに1を結合し、その値をハッシュ関数に代入する演算式を使用して、ハッシュ値演算値を算出する。使用するハッシュ関数は、オリジナルノード決定の関数と同一である。リードライト管理プログラム246は、そのハッシュ値を用いて、ノード管理テーブル248において第一レプリカ格納ノードの候補を検索する。キーに1を結合する演算は、例えばキーが東京であれば、東京1という文字列を生成し、例えばキーがニューヨークであればニューヨーク1という文字列を生成する。ステップS1103において、リードライト管理プログラム246は、オリジナルノードと第一レプリカ格納ノードの候補が等しいかどうか調べる。もしオリジナルノードと第一レプリカ格納ノードの候補が等しければS1103:YES、リードライト管理プログラム246は、ステップS1104へ進む。もしオリジナルノードと第一レプリカ格納ノードの候補が等しくなければS1103:NO、リードライト管理プログラム246は、ステップS1105へ進む。ステップS1104において、リードライト管理プログラム246は、第一レプリカ格納ノードを、第一レプリカ格納ノードの候補の時計回りに隣のノードと決定する。ステップS1105において、リードライト管理プログラム246は、第一レプリカ格納ノードを第一レプリカ格納ノードの候補のノードと決定する。ステップS1106において、リードライト管理プログラム246は、キーに2を結合し、そのハッシュ値を計算する。ハッシュ関数は上記の関数と同じである。リードライト管理プログラム246は、そのハッシュ値を用いて、ノード管理テーブル248において第二レプリカ格納ノードの候補を検索する。ステップS1107において、リードライト管理プログラム246は、オリジナルノード又は第一レプリカ格納ノードが、第二レプリカ格納ノードの候補と等しいかどうか調べる。もしオリジナルノード又は第一レプリカ格納ノードが、第二レプリカ格納ノードの候補と等しければS1107:YES、リードライト管理プログラム246は、ステップS1108へ進む。第二レプリカ格納ノードの候補が、オリジナルノード及び第一レプリカ格納ノードのいずれともが等しくなければS1107:NO、リードライト管理プログラム246は、ステップS1109へ進む。ステップS1108において、リードライト管理プログラム246は、新しい第二レプリカ格納ノードの候補を、前の第二レプリカ格納ノードの候補の時計回りに隣のノードと決定する。ステップS1109において、リードライト管理プログラム246は、第二レプリカ格納ノードを、第二レプリカ格納ノードの候補のノードと決定する。以上の処理によって、キーの値から格納ノードを決定することができる。なお、上記例は、オリジナルノード第一レプリカ格納ノード第二レプリカ格納ノードを検索するために、キーキーに1を結合した値キーに2を結合した値を用いたが、他の文字列を結合してもよいし、キーの文字列を一定の法則により変化させてもよい。例えば、リードライト管理プログラム246は、文字列を回転させる、つまりTOKYOを、OKYOTKYOTOと変化させることもできる。若しくは、キーを変化させるのではなく、リードライト管理プログラム246は、異なる候補ノードの決定のために、異なるハッシュ関数を使用してもよい。例えば、オリジナルノードを検索するためにMD5ニューヨークを計算し、第一レプリカ格納ノードを検索するためにSHA-1ニューヨークを計算し、第二レプリカ格納ノードを検索するためにSHA-256ニューヨークを計算することができる。若しくは、これらを組み合わせた形態をとることもできる。好ましい構成において、システムは、同一ハッシュ関数に異なる回数繰り返し値を代入することで、同一データを格納する複数の情報記憶ノードを決定する。例えばオリジナルノードの決定にSHA1KEYを用い、第一のレプリカノードの決定にSHA1SHA1KEYを用い、第二のレプリカノードの決定にSHA1SHA1SHA1KEYを用いるという構成である。これにより、レプリケーション数が多いシステムも容易かつ適切にデータを格納する複数の情報記憶ノードを決定することができる。又、システムのレプリケーション数の増加に対しても容易に対応することができる。次に、データの書き込みにおける、クライアント207の処理を、図12を用いて説明する。他のクライアントの処理も同様である。図12は、クライアント207がキーを用いてバリュー及びキーを書き込むためのフローチャートを示す。このフローチャートは、管理ノード204とクライアント207の工程を含む。ステップS1201において、リードライトクライアントプログラム277は、管理ノード204にキーを送信し、格納すべき3つの情報記憶ノードを教えてくれるよう要求する。ステップ1202において、管理ノード204は、キーから格納すべき3つの情報記憶ノードであるオリジナルノード第一レプリカ格納ノード第二レプリカ格納ノードを決定する。ステップS1203において、管理ノード204は、ノード管理テーブル248を用いて、オリジナルノード第一レプリカ格納ノード第二レプリカ格納ノードが共にALIVEであるかどうか調べる。管理ノード204がノード管理テーブル248からオリジナルノード第一レプリカ格納ノード第二レプリカ格納ノードが共にALIVEであることを確認できればS1203:YES、処理はステップS1204へ進む。もし管理ノード204がノード管理テーブル248からオリジナルノード第一レプリカ格納ノード第二レプリカ格納ノードのいずれかひとつでもALIVEであることを確認できなければS1203:NO、処理はステップS1209へ進む。ステップS1204において、管理ノード204は、書き込むべきノードとしてオリジナルノード第一レプリカ格納ノード第二レプリカ格納ノードの3つを、クライアント207に返答する。ステップS1205において、クライアント207のリードライトクライアントプログラム277は、書き込むべきノードとして教えられた3つのノードにキーバリューオリジナルノード名第一レプリカ格納ノード名第二レプリカ格納ノード名を書き込むよう指示する。ステップS1206において、リードライトクライアントプログラム277は、管理ノード204が、3つの情報記憶ノードから正常に書き込みができたとの返事を受け取ったかどうか調べる。もし3つの情報記憶ノードから正常に書き込みができたとの返事を受け取った場合はS1206:YES、処理はステップS1207へ進む。もし3つの情報記憶ノードのいずれかひとつからでも正常に書き込みができたとの返事を受け取れなかった場合はS1206:NO、処理は、ステップS1208へ進む。ステップS1207において、リードライトクライアントプログラム277は、書込み成功と判定する。ステップS1208において、リードライトクライアントプログラム277は書込み失敗と判定する。ステップS1209において、リードライトクライアントプログラム277は、書込み失敗と判定する。書き込み失敗の判定に対応する処理は、本発明と関連性が低いため説明を省略する。以上が処理の流れであるが、この処理をよりわかりやすく説明するため、例として、クライアント207がデータ東京110を格納する処理を以下に記述する。最初に、ステップS1201において、クライアント207は、管理ノード204にキーを送信し、格納すべき3つの情報記憶ノードを教えてくれるよう要求する。次にステップS1202において、管理ノード204がキーである東京から格納すべきノードを検索する。これは図11に示す処理である。管理ノード204は、キー東京をハッシュ関数に代入することでオリジナルノードを決定し、キー東京1をハッシュ関数に代入することで第一レプリカ格納ノードを決定し、キー東京2ハッシュ関数に代入することで第二レプリカ格納ノードを決定する。ハッシュ値が衝突したときの処理は、図11で示したとおりである。本例では、東京のハッシュ値として300、東京1のハッシュ値として1000、東京2のハッシュ値として3000が得られたとする。次にステップ1203において、管理ノード204は、ノード管理テーブル248を用いてオリジナルノード、第一レプリカ格納ノード、第二レプリカ格納ノードが、共にALIVE状態であるかどうか調べる。図6のノード管理テーブル248は、ノード2の担当範囲が227から535であることを示している。管理ノード204は、ハッシュ値が300であるオリジナルノードは、情報記憶ノード2であると決定する。その生死情報はALIVEである。同様に、ハッシュ値1000の第一レプリカ格納ノードは情報記憶ノード4である。生死情報はALIVEである。同様に、ハッシュ値3000の第二レプリカ格納ノードの生死情報はALIVEである。3つの情報記憶ノードがALIVEであるので、処理は、ステップS1204へ進む。次に、ステップS1204において、管理ノード204は、オリジナルノード、第一レプリカ格納ノード、第二レプリカ格納ノードとして、ノード2、情報記憶ノード4、情報記憶ノード7を、クライアント207に返答する。次に、ステップS1205において、クライアント207は、データを書き込むべき情報記憶ノードとして教えられた3つの情報記憶ノード情報記憶ノード2、情報記憶ノード4、情報記憶ノード7に、キーとして東京を、バリューとして晴れを、オリジナルノード名としてノード2を、第一レプリカ格納ノード名としてノード4を、第二レプリカ格納ノード名としてノード7を、書き込むよう指示する。次にステップS1206において、管理ノード204は、3つの情報記憶ノードノード2、ノード4、ノード7から正常に書き込みができたとの返事を受け取る。管理ノード204が3つの情報記憶ノードから正常に書き込みができたとの返事を受け取ると、処理はステップS1207へ進む。最後に、ステップS1207において、クライアント207は、書込み成功と判定する。以上の処理により、クライアント207は、データ東京110を情報記憶システム209に書き込むことができる。上記方法により選択したデータ書き込む先の情報記憶ノードがDEAD状態又はSUBSTITUTED状態にあるとき、書き込み処理は失敗に終わる。これと異なり、情報記憶システム209は、選択したデータ書き込む先の情報記憶ノードがSUBSTITUTED状態である場合に、特定の情報記憶ノードにデータを書き込んでもよい。例えば、管理ノード204は、ALIVEである2つの情報記憶ノードの識別子をクライアント207に返す。クライアント207は、2つの情報記憶ノードにデータを書き込む。図9及び図10を参照して説明した処理のように、SUBSTITUTED状態の情報記憶ノードに格納されるべきデータのカテゴリ例えば第一レプリカと予め関連づけられているカテゴリ例えば第二レプリカのデータを格納する情報記憶ノードは、そのデータを隣の論理位置の情報記憶ノードに複製する。データ読み出し以下において、図13から図15を参照して、クライアント207、208が、情報記憶システム209から情報を読み出す処理の説明を行う。以下においてはクライアント207の処理例を説明する。図13は、クライアント207が情報記憶システム209から情報を読み出す処理例のフローチャートを示す。ステップS1301において、クライアント207のリードライトクライアントプログラム277が、キーを管理ノード204に伝え、データを読み出すべきノードを教えるよう要求する。ステップS1302において、管理ノード204リードライト管理プログラム246は、図14に示す処理後述するにより、ALIVE状態の情報記憶ノードから、データを読み出すべきノードを検索する。ステップS1303において、リードライト管理プログラム246は、データを読み出すべき情報記憶ノードが見つかったかどうか調べる。もしデータを読み出すべき情報記憶ノードが見つかっていない場合S1303:NO、処理は、ステップS1304へ進む。もしもデータを読み出すべきノードが見つかった場合はS1303:YES、処理はステップS1305へ進む。ステップS1304において、リードライト管理プログラム246は、図15に示す処理後述するにより、SUBSTITUTED状態の情報記憶ノードのバックアップ先の情報記憶ノードから、読み出すべきノードを検索する。ステップS1305において、管理ノード204は、読み出すべき情報記憶ノードが見つかったかどうか調べる。もし読み出すべきノードが見つかっていない場合はS1305:NO、処理はステップS1306へ進む。もし読み出すべきノードが見つかった場合はS1305:YES、処理はステップS1308へ進む。ステップS1306において、リードライト管理プログラム246は、クライアント207に、データを読み出すべき情報記憶ノードが見つからなかった旨を返答する。ステップS1307において、クライアント207のリードライトクライアントプログラム277は、読出し処理を失敗したと判定する。ステップS1308において、リードライト管理プログラム246は、クライアント207に、データを読み出すべき情報記憶ノードを返答する。ステップS1309において、クライアント207のリードライトクライアントプログラム277は、読み出すべきノードからキーを用いてバリューを読み出す。以上の処理によりクライアント207が情報記憶システム209から情報を読み出すことができる。次に図14を参照して、キーを用いてALIVE状態の情報記憶ノードからデータを読み出すべき情報記憶ノードを見つける処理の説明を行う。図14は、管理ノード204が、キーを用いてALIVE状態のノードから読み出すべきノードを見つける処理のフローチャートを示す。ステップS1401において、管理ノード204のリードライト管理プログラム246は、キーから、オリジナルノード、第一レプリカ格納ノード、第二レプリカ格納ノードを決定する。この処理の詳細は図11を参照して説明したとおりである。ステップS1402において、リードライト管理プログラム246は、オリジナルノードがALIVEでないかどうか調べる。もしオリジナルノードがALIVEでない場合S1402:NO、処理はステップS1403へ進む。もしオリジナルノードがALIVEである場合はS1402:YES、処理はステップS1408へ進む。ステップS1403において、リードライト管理プログラム246は、第一レプリカ格納ノードがALIVEでないかどうか調べる。もし第一レプリカ格納ノードがALIVEでない場合はS1403:NO、ステップS1404へ進む。もし第一レプリカ格納ノードがALIVEである場合はS1403:YES、処理はステップS1407へ進む。ステップS1404において、リードライト管理プログラム246は、第二レプリカ格納ノードがALIVEでないかどうか調べる。もし第二レプリカ格納ノードがALIVEでない場合はS1404:NO、処理はステップS1405へ進む。もし第二レプリカ格納ノードがALIVEである場合はS1404:YES、処理はステップS1406へ進む。ステップS1405において、リードライト管理プログラム246は、データを読み出すべき情報記憶ノードは見つからないと判定する。ステップS1406において、リードライト管理プログラム246は、第二レプリカ格納ノードを、データを読み出すべき情報記憶ノードと判定する。ステップS1407において、リードライト管理プログラム246は、第一レプリカ格納ノードを、データを読み出すべき情報記憶ノードと判定する。ステップS1408において、リードライト管理プログラム246は、オリジナルノードを、データを読み出すべき情報記憶ノードと判定する。ステップS1409において、リードライト管理プログラム246は、データを読み出すべき情報記憶ノードのノード名を、返り値として返す見つからなかったときは見つからないと返す。以上の処理によりキーを用いてALIVE状態のノードから読み出すべきノードを見つけることができる。次に図15を参照して、管理ノード204がキーを用いてSUBSTITUTED状態の情報記憶ノードから、データを読み出すべきノードを見つける処理を説明する。図15は、キーを用いてSUBSTITUTED状態の情報記憶ノードのバックアップ先の情報記憶ノードから、データを読み出すべき情報記憶ノードを見つけるための処理例を示すフローチャートである。ステップS1501において、リードライト管理プログラム246は、キーから、オリジナルノード、第一レプリカ格納ノード、第二レプリカ格納ノードを決定する。この処理の詳細は、図11に示したとおりである。ステップS1502において、リードライト管理プログラム246は、オリジナルノードがSUBSTITUTEDでないかどうか調べる。もしオリジナルノードがSUBSTITUTEDでない場合はS1502:NO、処理はステップS1503へ進む。もしオリジナルノードがSUBSTITUTEDである場合はS1502:YES、処理はステップS1508へ進む。ステップS1503において、リードライト管理プログラム246は、第一レプリカ格納ノードがSUBSTITUTEDでないかどうか調べる。もし第一レプリカ格納ノードがSUBSTITUTEDでない場合はS1503:NO、処理はステップS1504へ進む。もし第一レプリカ格納ノードがSUBSTITUTEDである場合はS1503:YES、処理はステップ1507へ進む。ステップS1504において、リードライト管理プログラム246は、第二レプリカ格納ノードがSUBSTITUTEDでないかどうか調べる。もし第二レプリカ格納ノードがSUBSTITUTEDでない場合はS1504:NO、処理はステップS1505へ進む。もし第二レプリカ格納ノードがSUBSTITUTEDである場合はS1504:YES、処理はステップS1506へ進む。ステップS1505において、リードライト管理プログラム246は、データを読み出すべき情報記憶ノードは見つからないと判定する。ステップS1506において、リードライト管理プログラム246は、オリジナルノードの隣のノードを、データを読み出すべき情報記憶ノードと判定する。ステップS1507において、リードライト管理プログラム246は、第二レプリカ格納ノードの隣のノードを、データを読み出すべき情報記憶ノードと判定する。ステップS1508において、リードライト管理プログラム246は、第一レプリカ格納ノードの隣のノードを、データを読み出すべき情報記憶ノードと判定する。ステップS1509において、リードライト管理プログラム246は、データを読み出すべき情報記憶ノードのノード名を、返り値として返す見つからなかったときは見つからないと返す。以上の処理により、キーを用いてSUBSTITUTED状態のノードから読み出すべきノードを見つけることができる。以上が処理の流れであるが、この処理をよりわかりやすく説明するため、例として、クライアント207がデータ東京110を読み出す処理を以下に説明する。最初にステップS1301において、クライアント207がキーである東京を管理ノード204に送信し、データを読み出すべき情報記憶ノードを教えるよう要求する。次にステップS1302において、管理ノード204は、図14に示す処理によりALIVE状態の情報記憶ノードから、データを読み出すべき情報記憶ノードを検索する。ステップS1401において、管理ノード204は、東京東京1東京2からハッシュ値を計算し、ノード管理テーブル248からノード2ノード4ノード7を取得する。ステップS1402において、管理ノード204は、ノード2の生死状態をノード管理テーブル248で検索する。ノード2の状態はALIVEであることから、ステップS1408において、管理ノード204は、データを読み出すべき情報記憶ノードを情報記憶ノード2と判定する。ステップS1303において、管理ノード204は、データを読み出すべき情報記憶ノードが見つかったかどうか調べ、見つかったので処理はステップS1305へ進む。ステップS1305において、管理ノード204は、データを読み出すべき情報記憶ノードが見つかったかどうか調べ、見つかったので処理はステップS1308へ進む。ステップS1308において、管理ノード204は、クライアント207に、データを読み出すべき情報記憶ノードとして情報記憶ノード2を返答する。次にステップS1309において、クライアント207は、データを読み出すべきノードである情報記憶ノード2から、キー東京を用いてバリューを読み出す。以上の処理により、クライアント207が情報記憶システム209から情報を読み出すことができる。情報記憶ノード追加次に、図16及び図17を用いて、ノードNとノードN1の間に、ノードXを挿入する処理を説明する。図16は、ノードNとノードN1の間に、ノードXを挿入する処理例を示すフローチャートである。ステップS1601において、管理ノード204のノード管理プログラム245は、がノードXの担当ハッシュ値範囲のエンド値を決定する。これはノードNの担当ハッシュ値範囲のエンド値からノードN1の担当ハッシュ値範囲のエンド値までの間の値である。ステップS1602において、ノード管理プログラム245は、ノード管理テーブル248の生死状態のフィールドがALIVEの情報記憶ノードに、それ自身が持っているデータのうちノードXが関係するデータを抽出して、ノードXに複製する送信するように指示する。この指示には、ノードXの担当ハッシュ値範囲が付加される。ステップS1603において、指示を受けた各情報記憶ノードは、それ自身が持っているデータのうち、ノードXが関係するデータを抽出して、ノードXに複製する。この処理を、図17のフローチャートを参照して説明する。ステップS1701において、各情報記憶ノードのデータ再配置処理プログラム217は、データ格納テーブル218から、オリジナルノードがノードN1であって、第一レプリカ格納ノードが自分であるエントリを抽出する。さらに、データ再配置処理プログラム217は、それぞれの抽出したデータのキーに対してハッシュ値を計算し、ノードXの担当ハッシュ値範囲であるデータを抽出する。本例において、データ再配置処理プログラム217は、オリジナルノード、第一レプリカ格納ノード及び第二レプリカ格納ノードを決定する演算方法を知っているプログラム内に規定されている。ステップS1702において、各情報記憶ノードのデータ再配置処理プログラム217は、データ格納テーブル218から、第一レプリカ格納ノードがノードN1であって、第二レプリカ格納ノードが自分であるエントリを抽出する。さらに、データ再配置処理プログラム217は、それぞれの抽出したデータのキーに対してハッシュ値を計算し、ノードXの担当ハッシュ値範囲であるデータを抽出する。ステップS1703において、データ再配置処理プログラム217は、データ格納テーブル218から、第二レプリカ格納ノードがノードN1であって、オリジナルノードがそれ自身であるエントリを抽出する。さらに、データ再配置処理プログラム217は、それぞれの抽出したデータのキーに対してハッシュ値を計算し、ノードXの担当ハッシュ値範囲であるデータを抽出する。ステップS1704において、データ再配置処理プログラム217は、上記3工程で抽出したエントリをまとめて、関係するデータとして主記憶デバイスの記憶領域に格納する。データ再配置処理プログラム217は、ステップS1701からステップS1704で抽出したデータを、ノードXに複製する。データ再配置処理プログラム217は、ノードXの挿入に共に、データ格納テーブル218を更新する。図16に戻って、ステップS1604において、管理ノード204のノード管理プログラム245は、指示をした全ての情報記憶ノードによるノードXへの複製作業が終わるのを待つ。ステップS1605において、ノード管理プログラム245は、ノード管理テーブル248のノードNとノードN1の間に、ノードXのエントリを追加し、担当ハッシュ値範囲のエンド値を記入し、生死のフィールドにALIVEを記入する。ステップS1606において、ノード管理プログラム245は、ノードN1に対して、新しくノードXが担当範囲になったデータを削除するように指示する。以上の処理によりノードNとノードN1の間に、ノードXを挿入する処理を遂行することができる。本処理により、ノードN1のみからデータをノードXに複製する処理に対して、複製処理を複数の情報記憶ノードに分散して行うことができ、1台当たりの情報記憶ノードの付加を低減することができる。<第2の実施の形態>本実施形態は、第1の実施形態におけるレプリケーション数を回復している処理の途中において、さらに障害が発生したときに行うことが好ましい処理を説明する。図18は、図9に示すフローチャートのステップS904の実行中にノードMが死んだときに実行される処理例を示すフローチャートである。ステップS1801において、管理ノード204のノード管理プログラム245は、ステップS904の実行中にノードMが死んだことを検知する。ステップS1802において、ノード管理プログラム245は、ノード管理テーブル248のノードMのエントリの生死情報フィールドを、ALIVEからDEADに変更する。ステップS1803において、管理ノード204のデータ再配置管理プログラム247は、ノード管理テーブル248にける生死情報フィールドがALIVEの情報記憶ノードに、自分が持っているデータのうちノードNに関係しかつノードMにも関係するデータを抽出して、自分の隣の情報記憶ノードに複製するように指示する。この指示は、ステップS903の複製指示よりも優先するように指示する。ノードN及びノードMの双方の担当データ例えば、ノードNがオリジナルノードであり、ノードMが第一レプリカ格納ノードであるデータのレプリケーション数は、ノードMが死んだときに、2から1に減少する。一方、ノードN又はノードMの一方のみに関係する一方のみが担当しているデータ、つまり、一方のみがオリジナルデータ、第一レプリカ又は第二レプリカの1つを格納しているデータのレプリケーション数は2である。このように、ノードN及びノードMの双方が担当しているデータのレプリケーション数は、他のデータのレプリケーション数よりも小さいため、他のデータよりも優先してそのレプリケーション数を増加させることが重要である。そこで、本実施形態は、好ましい方法として、自身が持っているデータのうちノードNに関係しかつノードMにも関係するデータの抽出及び複製を、ステップS903の複製指示よりも優先する。各情報記憶ノードは、データ格納テーブル218において、ノードN及びノードMの双方を含むエントリを検索し、そのエントリを自分の隣の情報記憶ノードに複製する。ノードN及びノードMの双方を含むエントリは、ノードN又はノードMのいずれかについて、図10を参照して説明した関係するデータの規則を満たす。ステップS1804において、管理ノード204は、全部の情報記憶ノードによる、ノードM及びノードNの双方の関係データの複製作業が終わるのを待つ。ここまでのステップにより、レプリケーション数1であったデータのレプリケーション数が1だけ増加して2になる。ステップS1805において、データ再配置管理プログラム247は、ノード管理テーブル248における生死情報フィールドがALIVEの情報記憶ノードに、自分が持っているデータのうちノードMに関係するデータを抽出して、自分の隣の情報記憶ノードに複製するように指示する。この指示は、ノードMに関係するデータのうち未複製のデータ、つまり、ノードNが担当していないデータのみを対象とする。ノードMに関係するデータの特定は、図10に示す規則に従う。具体的には、図10を参照して説明したように、ノードMが格納するオリジナルデータ、第一レプリカ及び第二レプリカの、それぞれの、第一レプリカ、第二レプリカ及びオリジナルデータが、ノードMに関係しているデータである。これらのデータのエントリにおいて、ノードNが含まれていないエントリが、未複製のエントリである。データ再配置管理プログラム247は、ノードMのみが関係するデータとノードNのみが関係するデータのいずれを優先する形態としてもよい。つまり、情報記憶ノードは、ノードMのみが関係するデータと、ノードNのみが関係するデータの、いずれを先に複製する形態としてもよい。各情報記憶ノードは、データ格納テーブル218において、ノードMを含みノードNを含まないエントリにおいて、図10を参照して説明した規則を満たすエントリを、隣の情報記憶ノードに複製する。ステップS1806において、データ再配置管理プログラム247は、全部の情報記憶ノードによるステップS1805の終了を待つ。ステップ1807において、データ再配置管理プログラム247は、ノード管理テーブル248におけるノードMのエントリの生死情報フィールドを、DEADからSUBSTITUTEDに変更する。ここまでのステップにより、ノードMが担当しており、ノードNが担当してないデータのレプリケーション数を規定数の3に戻すことができる。図9のフローチャートにおけるステップS1806及びステップS1807の後、ステップS1808において、データ再配置管理プログラム247は、ノードMの隣のノードM1に、ノードMが元々担当していたデータを、ノード管理テーブル248の生死情報のフィールドがALIVEの情報記憶ノードから集めてくるよう指示する。具体的には、データ再配置管理プログラム247は、ノードM1に、ALIVEの情報記憶ノードを特定する情報と共に、データ収集の指示を送信する。この指示は、ノードNの担当データの収集指示の後でも前でもよい。ノードM1は、ALIVE状態の情報記憶ノードに対して、複製されたノードMの担当データノードMの死亡に応答して複製されたデータの送信複製を要求する。ステップS1809において、ノードMの隣のノードM1が、ノードMが元々担当していたすべてのデータを集めたら、データ再配置管理プログラム247は、ノード管理テーブル248のノードMのエントリを削除する。データ再配置管理プログラム247は、ノードMのエントリの生死情報フィールドの値を、SUBSTITUTEDからDELETEDに変更してもよい。上記処理は、ノードNとノードMの双方に格納されるデータと同一のデータを、1つの情報記憶ノードのみに複製するが、これを2つの異なる情報記憶ノードに複製してもよい。これにより、ノードNとノードMの双方に格納されるデータのレプリケーション数を、3に戻すことができる。以上が処理の流れであるが、この処理をよりわかりやすく説明するため、例として、死んだノード2のためのステップS904の実行中にノード5が死んだときの処理を以下に記述する。ステップS1801において、ステップS904の実行中に、管理ノード204は情報記憶ノード5が死んだことを検知する。次にステップS1802において、管理ノード204は、ノード管理テーブル248のノード5の生死のフィールドをDEADに変更する。次にステップS1803において、管理ノード204は、ノード管理テーブル248の生死情報フィールドがALIVEの情報記憶ノードに、自分が持っているデータのうち、ノード2に関係しかつノード5にも関係するデータを抽出して、自分の隣の情報記憶ノードに複製するように指示する。この指示はステップS903の指示よりも優先するように指示する。指示を受けた各情報記憶ノードは、データ格納テーブル218において、オリジナルノード、第一レプリカ格納ノード及び第二レプリカ格納ノードのうち、2つのフィールドがノード2及びノード5を格納しているエントリを抽出し、そのエントリを隣の情報記憶ノードに送信する。ステップS1804において、管理ノード204は、全部の情報記憶ノードによる、ノード2及びノード5の双方の担当データの複製作業が終わるのを待つ。ステップS1805において、管理ノード204は、ノード管理テーブル248における生死情報フィールドがALIVEの情報記憶ノードに、自分が持っているデータのうちノード5に関係するデータを抽出して、自分の隣の情報記憶ノードに複製するように指示する。この指示は、ノード5に関係するデータのうち未複製のデータ、つまり、ノード2が担当していないデータのみを対象とする。各情報記憶ノードは、データ格納テーブル218において、ノード2を含まないエントリにおいてノード5と関係するエントリを抽出し、そのエントリを隣の情報記憶ノードに送信する。ステップS1806において、管理ノード204は、全部の情報記憶ノードによる、ノードMに関係する未複製データの複製処理の終了を待つ。ステップ1807において、管理ノード204は、ノード管理テーブル248におけるノード5のエントリの生死情報フィールドを、DEADからSUBSTITUTEDに変更する。図9のフローチャートにおけるステップ904及びステップ905ノード2の担当データの複製及びノード管理テーブルの更新の後、ステップS1808において、管理ノード204は、ノード5の隣のノード6に、ノード5が元々担当していたデータを、ノード管理テーブル248の生死情報のフィールドがALIVEの情報記憶ノードから集めるよう指示する。具体的には、管理ノード204は、ノード6に、ALIVEの情報記憶ノードを特定する情報と共に、データ収集の指示を送信する。ステップS1809において、ノード5の隣のノード6が、ノード5が元々担当していたすべてのデータを集めたら、管理ノード204は、ノード管理テーブル248のノード5のエントリを削除する。ステップS1801からステップS1804までにかかる時間を計算する。従来例の計算例と同様に、情報記憶ノードの数を1000とし、各情報記憶ノードは1Gbpsのネットワークに接続されており、各情報記憶ノードは、1TBテラバイトのオリジナルデータを保持しているつまり各ノードの担当範囲には1TBのデータが存在しているとする。ステップS1803で各ノードに指示される複製すべきデータは、3TBの1000分の1のさらに1000分の1である。つまり約3MBである。これを複製するためにかかる時間は、約0.024秒である。従来例が必要とする2時間13分と比較すると、約30万分の1の時間である。つまり、非常に短い時間で、レプリケーション数1というデータロスの危険性が高い状況を脱出することができる。以上、本発明の実施形態を説明したが、本発明が上記の実施形態に限定されるものではない。当業者であれば、上記の実施形態の各要素を、本発明の範囲において容易に変更、追加、変換することが可能である。本発明はキーバリューシステムに特に好適であるが、これとは異なる情報記憶システムに適用することができる。例えば、3以上のデータ項目からなるグループによりデータを管理するシステムや単一データ項目によりデータを管理するシステムにも適用できる。データ格納先の情報記憶ノードを決定するための演算は、ハッシュ関数を使用することが好ましいが、これとは異なる関数を使用してもよい。上記の各構成、機能、処理部、処理手段等は、それらの一部又は全部を、例えば集積回路で設計する等によりハードウェアで実現してもよい。各機能を実現するプログラム、テーブル、ファイル等の情報は、メモリや、ハードディスク、SSDSolidStateDrive等の記憶デバイス、または、ICカード、SDカード、DVD等の永続的データ記憶媒体に格納することができる。ある実施形態の構成の一部を他の実施形態の構成に置き換えることが可能であり、ある実施形態の構成に他の実施形態の構成を加えることも可能である。各実施形態の構成の一部について、他の構成の追加削除置換をすることが可能である。