(57)【要約】      （修正有）【課題】データを格納する情報記憶ノードの数が減少したときに、レプリケーション数を迅速に回復する。【解決手段】情報記憶システムは、複数の情報記憶ノードと管理ノードとを備える。管理ノードは、受信したユーザデータのそれぞれに対して、規定数の同一データを格納する、規定数の情報記憶ノードを決定する。上記データのそれぞれは、上記規定数のカテゴリのそれぞれに属する。複数の情報記憶ノードにおける第一の情報記憶ノードの使用停止のために、各情報記憶ノードは、第一の情報記憶ノードに格納されている各データのカテゴリと予め対応づけられているカテゴリの同一データを、予め定められた手順に従って選択した他の情報記憶ノードに複製する。【選択図】図１
2012221419.tif 000002
【特許請求の範囲】
【請求項１】
受信したデータを格納する情報記憶システムであって、
ネットワークと、
前記ネットワークにより通信可能に接続された複数の情報記憶ノードと、
前記複数の情報記憶ノードと通信可能に接続された管理部と、を含み、
前記受信したデータのそれぞれは、規定数の同一内容データに複製され、互いにあるいは一方向に対応付けられ、前記複数の情報記憶ノードのいずれかに格納され、
前記管理部は、前記複製された同一内容データのそれぞれに対して、それぞれ互いに異なるカテゴリを与え、
前記管理部は、前記異なるカテゴリを与えられた同一内容データのそれぞれを格納するための情報記憶ノードを前記複数の情報記憶ノードの中から決定し、
前記管理部は、前記格納する情報記憶ノードの決定において、
一つの情報記憶ノードが格納する同一カテゴリに属するデータのそれぞれに対応する他の情報記憶ノードに記憶される異なるカテゴリに属する同一内容データは、複数の情報記憶ノードに分散するように、前記決定を行い、
前記受信したデータに含まれる情報の一部または全部をカテゴリごとに定めた演算式に代入して前記決定を行い、
前記複数の情報記憶ノードにおける第一の情報記憶ノードの使用停止に際して、前記複数の情報記憶ノードのそれぞれは、
自身が格納しているデータのうち前記第一の情報記憶ノードに格納されているデータと同一内容であり、かつ、前記自身が格納しているデータが属しているカテゴリと前記第一の情報記憶ノードで属しているカテゴリとが予め対応づけられているデータ、を抽出し、
前記抽出したデータを予め定められた手順に従って選択した情報記憶ノードに複製する、情報記憶システム。
【請求項２】
前記情報記憶システムにおける１つもしくは複数の情報記憶ノード、新たに追加された情報記憶ノード、またはそれらの組み合わせは、前記第一の情報記憶ノードの使用停止に起因する前記複製の後に、前記第一の情報記憶ノードに格納されていたデータと同一内容のデータを、前記情報記憶システムに含まれる複数の情報記憶ノードから集める、請求項１に記載の情報記憶システム。
【請求項３】
前記管理ノードは、前記規定数の演算式のそれぞれの演算式の演算値と情報記憶ノードとを関連づける管理情報を備え、
前記規定数の演算式のそれぞれはハッシュ関数を含み、
前記管理ノードは、前記管理情報を参照して、前記受信したデータの前記規定数の演算式によるそれぞれの演算値から、前記規定数の同一内容データのそれぞれを格納する情報記憶ノードを決定する、請求項１又は２に記載の情報記憶システム。
【請求項４】
前記受信したデータは、第一及び第二のデータ項目からなるデータペアであり、
前記管理ノードは、前記データペアにおける前記第一のデータ項目の前記演算式による演算により、当該データペアと同一内容データを格納する前記規定数の情報記憶ノードを決定する、請求項１、２又は３に記載の情報記憶システム。
【請求項５】
前記規定数は３以上の値であり、
前記第一の情報記憶ノードのための前記複製の処理中における第二の情報記憶ノードの使用停止に対して、前記情報記憶ノードは、前記第一及び第二の情報記憶ノードの双方に格納されているデータと同一内容のデータの複製を前記第一及び第二の情報記憶ノードの一方のみに格納されているデータよりも優先して複製する、請求項１〜４のいずれかに記載の情報記憶システム。
【請求項６】
前記複数の情報記憶ノードには、前記演算式の演算値と関連付けられた論理的位置が設定され、
前記予め定められた手順は、各情報記憶ノードに対して特定の相対位置にある他の情報記憶ノードにデータを複製することを規定する、請求項１〜５のいずれかに記載の情報記憶システム。
【請求項７】
前記管理ノードは、新たに追加された第三の情報記憶ノードの論理的位置を決定して、前記複数の情報記憶ノードにおける第四の情報記憶ノードの担当範囲の一部を、前記第三の情報記憶ノードに割り当て、
前記第三の情報記憶ノードは、前記割り当てられた担当範囲のデータと同一内容データを格納している複数の情報記憶ノードからデータを複製する、請求項６に記載の情報記憶システム。
【請求項８】
前記規定数の演算式は、受信したユーザデータから互いに異なる代入数を算出し、
前記規定数の演算式のそれぞれは、データを格納する情報記憶ノードを決定する演算値の算出において、前記算出した代入数をハッシュ関数に代入する、請求項３に記載の情報記憶システム。
【請求項９】
ネットワークにより接続された複数の情報記憶ノードを含む情報記憶システムにおけるデータ複製方法であって、
前記受信したデータのそれぞれを、規定数の同一内容データに複製し、
前記複製された同一内容データのそれぞれに対して、それぞれ互いに異なるカテゴリを与え、
前記異なるカテゴリを与えられた同一内容データのそれぞれを格納するための情報記憶ノードを前記複数の情報記憶ノードの中から決定し、
前記格納する情報記憶ノードの決定において、一つの情報記憶ノードが格納する同一カテゴリに属するデータのそれぞれに対応する他の情報記憶ノードに記憶される異なるカテゴリに属する同一内容データは、複数の情報記憶ノードに分散するように、前記決定を行い、
前記格納する情報記憶ノードの決定において、前記受信したデータに含まれる情報の一部または全部をカテゴリごとに定めた演算式に代入して前記決定を行い、
前記複製された同一内容のデータのそれぞれを、前記決定した情報記憶ノードに格納し、
前記複数の情報記憶ノードにおける第一の情報記憶ノードの使用停止に際して、前記複数の情報記憶ノードのそれぞれにておいて、当該情報記憶ノードが格納しているデータのうち前記第一の情報記憶ノードに格納されているデータと同一内容であり、かつ、前記情報記憶ノードで属しているカテゴリと前記第一の情報記憶ノードで属しているカテゴリとが予め対応づけられているデータ、を抽出し、
前記複数の情報記憶ノードのそれぞれにておいて前記抽出したデータを、予め定められた手順に従って選択された他の情報記憶ノードに複製する、データ複製方法。
【請求項１０】
前記第一の情報記憶ノードの使用停止に起因する前記複製の後に、前記第一の情報記憶ノードに格納されていたデータと同一内容のデータを、前記情報記憶システムに含まれる複数の情報記憶ノードから、前記情報記憶システムにおける１つもしくは複数の情報記憶ノード、新たに追加された情報記憶ノード、またはそれらの組み合わせ、に集める、請求項９に記載のデータ複製方法。
【請求項１１】
前記規定数は３以上の値であり、
前記第一の情報記憶ノードのための前記複製の処理中における第二の情報記憶ノードの使用停止に対して、前記第一及び第二の情報記憶ノードの双方に格納されているデータと同一内容のデータの複製を前記第一及び第二の情報記憶ノードの一方のみに格納されているデータよりも優先して複製する、請求項９又は１０に記載のデータ複製方法。
【請求項１２】
前記複数の情報記憶ノードには、前記演算式の演算値と関連付けられた論理的位置が設定され、
前記予め定められた手順は、各情報記憶ノードに対して特定の相対位置にある他の情報記憶ノードにデータを複製することを規定する、請求項９、１０、又は１１に記載のデータ複製方法。
【請求項１３】
新たに追加された第三の情報記憶ノードの論理的位置を決定して、前記複数の情報記憶ノードにおける第四の情報記憶ノードの担当範囲の一部を、前記第三の情報記憶ノードに割り当て、
前記割り当てられた担当範囲のデータと同一内容データを格納している複数の情報記憶ノードからデータを、前記第三の情報記憶ノードに複製する、請求項１２に記載のデータ複製方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は情報記憶ノードシステム及びそのデータ複製方法に関し、特に、複数の情報記憶ノードを有する情報記憶システムにおけるデータ複製に関する。
【背景技術】
【０００２】
計算機システムにおいて、システムが必要とする情報はデータベースに格納されることが多い。最も広く知られたデータベースの一つは、リレーショナルデータベースである。リレーショナルデータベースは、データの結合及びトランザクションにおけるデータ一貫性のような優れた機能を提供する。一方で、リレーショナルデータベースは、必ずしも高いスケーラビリティを有していない。
【０００３】
クラウド技術のようなインターネットにおける分散技術の発展と共に、多数のサーバで高速分散処理を行うことができると共に、需要に応じてサーバ数を容易に増加することができるシステムが要求されている。その様な要求に応える技術として、キーバリューストアが注目されている。キーバリューストアは、キーとバリューのペアを格納する。システムは、目的のバリューのキーを指定して、そのバリューを取得する。キーバリューストアは、キーの値に応じてその保存先のサーバ（ノード）を変えることで、複数のサーバに分散してデータを保存することができる。このように、キーバリューストアにより、大量のデータを処理するスケールアウト型システムを容易に構築することができる。
キーの値に応じて担当ノードを決定する手法の一つとして、コンシステントハッシングが知られている（例えば非特許文献１）。
【０００４】
さらに、非特許文献２は、キーバリューストアにおいて高可用性を実現する技術を開示している。具体的には、この文献は、高い可用性と耐久性を達成するため、複数のホストでデータを複製することを開示する。各データ項目は複製されインスタンスごとに設定されたＮ台のホストに格納される。各キーは、コーディネータノードが割り当てられる。コーディネータノードは、自分に割り当てられたデータ項目の複製を担当する。コーディネータノードは、自分の担当する各キーを自身の記憶装置に格納するほか、これらのキーをリング配置における時計回りで隣のＮ−１台のノードに複製する。
【０００５】
非特許文献２は、システムに、新たなノードＸを追加する方法及びノードをシステムから外す方法を開示している。新たなノードＸの追加により、特定のキー範囲がＸに割り当てられる。新たにノードＸに割り当てられたキーをこれまで保持していたいくつかの既存ノードは、それらのキーを持つ必要がなくなる。それら既存ノードは、もはや自分が維持する必要がないキーをノードＸに転送する。同様に、ノードがシステムから外されると、ノードの追加とは逆の手順を踏んでキーの再配置が起きる。
【０００６】
非特許文献３は、データ可用性を高めるために、ｋ個の異なるハッシュ関数を使用して、１つのキーを座標空間におけるｋ個のポイントに写像し、これにより、１つのキーバリューペアをシステムにおけるｋ個の異なるノードで複製して格納する。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】D. Karger, E. Lehman, T. Leighton, M. Levine, D. Lewin and R. Panigrahy, Consistent hashing and random trees: distributed cachine protocols for relieving hot spots on the World Wide Web, in: Proc. 29th Annu. ACM Symp. on Theory of Computing, 1997, pp. 654−663.
【非特許文献２】DeCandia, G., Hastorun, D., Jampani, M., Kakulapati, G., Lakshman, A., Pilchin, A., Sivasubramanian, S., Vosshall, P., Vogels, W.: Dynamo: amazon's highly available key-value store. In: SOSP. pp. 205−220 (2007)
【非特許文献３】Sylvia Ratnasamy、Paul Francis、Mark Handley、Richard Karp、Scott Shenker「A Scalable Content-Addressable Network」SIGCOMM'01, August 27-31, 2001, San Diego, California, USA.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
分散データストアにおいては、ノードが追加又は削除された場合に、各データのレプリケーション数を維持することが重要である。レプリケーション数は、複数のノードを含むシステムにおいて、１つのデータが複製されてシステム内のいくつかのノードに格納されている状態において、該当データが格納されているノードの数を意味する、
例えば、システムが多数のノードを含み、システム内の３つのノードに格納されているデータは「レプリケーション数３」の状態である。３つのノードの１つは、オリジナルデータを格納し、他の２つのノードは複製データを格納する。これら３つのノードのうち１つが故障して使用不可能になった場合、当該データを格納するノードの数は１つ減るため、そのデータのレプリケーション数は２に減少する。
【０００９】
上述のように、非特許文献１は、コンシステントハッシングの手法を記載している。しかし、非特許文献１のコンシステントハッシングは、情報を１つのノードのみに格納するため、そのノードが故障により使用不能になった場合に、その情報が失われてしまう。
【００１０】
非特許文献２は、同じデータをＮ個のノードに格納する。具体的には、あるコーディネータノードとそれに続くＮ−１個のノードに同一のデータを格納する。これにより、コーディネータノードが使用不能になっても、それに続くいずれかのノードからデータを読み出すことができる。
【００１１】
しかし、コーディネータノードに格納されているオリジナルデータの全ての複製データは、その後続のノードに格納される。そのため、ノードの故障によりレプリケーション数が減少した時にレプリケーション数を回復する処理には、故障ノードの周囲のノードのみが寄与し、故障ノードから離れたノードはその処理に寄与することがない。このため、故障ノードの近辺のノードはレプリケーション数の回復のために、多くのデータを送受信しなくてはならない。
【００１２】
このように、非特許文献２においてはレプリケーション数の回復のためにシステム内の少数のノードのみが回復処理に寄与することとなり、システム内で処理量の偏りが発生する。従って、クライアントからの要求を処理するノードが回復処理をしているか否かにより応答時間にばらつきが生じ、システムとしての応答時間にばらつきが出る。また、少数のノードのみで回復処理を行う必要があるため、レプリケーション数が回復するまでに多くの時間がかかる。
【００１３】
具体的な例をあげる。ノードの数が１０００、各ノードは１Ｇｂｐｓのネットワークに接続されており、１ノードあたり１ＴＢのオリジナルデータを保持し（つまり各ノードの担当範囲には１ＴＢのデータが存在しており）、レプリケーション数を３に保っているシステムの例を説明する。
【００１４】
それぞれのノードは、１ＴＢのオリジナルデータ、１ＴＢのレプリカ１そして１ＴＢのレプリカ２を持つ。つまり、各ノードの合計データ量は、３ＴＢである。説明のため、１０００個のノードのそれぞれに、時計回りにノード１からノード１０００までの番号が振られているとする。例えば、ノード１保持しているオリジナルデータ（これをノード１の担当範囲のデータと呼ぶことにする）の１番目のレプリカがノード２に、２番目のレプリカがノード３に保持されている。
【００１５】
言いかえれば、ノード３は、ノード１の２番目のオリジナルデータのレプリカ、ノード２のオリジナルデータの１番目のレプリカ、そしてノード３のオリジナルデータを保持している。つまり、ノード３は、ノード１の担当範囲のデータ、ノード２の担当範囲のデータ、そしてノード３の担当範囲のデータを保持している。同様に、ノード４は、ノード２のオリジナルデータの２番目のレプリカ、ノード３のオリジナルデータの１番目のレプリカ、そしてノード４のオリジナルデータを保持している。他のノードも同様である。
【００１６】
ここでノード５が故障により使用不可能になったとする。ノード５の担当範囲は、新しくノード６の担当範囲に付け加わる。つまり、ノード６はノード５のオリジナルデータの１番目のレプリカとして保持していたデータを、ノード６のオリジナルデータとして扱う。ノード６は、さらに、ノード４の２番目のレプリカとして保持していたデータを、ノード４の１番目のレプリカとして扱う。そして、ノード６は、新たにどこかのノード（ノード３かノード４）から、ノード３の担当範囲のデータを複製してきて、そのデータをノード３の２番目のレプリカとして保持する。
【００１７】
同様に、ノード７はノード４の担当範囲のデータを、ノード８はノード５の担当範囲のデータを新たに保持する必要がある。ここでは例えばノード３の担当範囲のデータをノード３からノード６に、ノード４の担当範囲のデータをノード４からノード７に、従来ノード５の担当範囲だったデータ（現在はノード６の担当範囲の一部のデータ）をノード６からノード８に複製することとする。（これらの「もとのレプリケーション数を回復するための処理」を単に「回復処理」と呼ぶこととする。）
このときノード３は、自身の保持している３ＴＢのデータの３分の１に当たる１ＴＢを、送信しなくてはならない。同様に、ノード４及びノード６も、自身の保持するデータの３分の１にあたる１ＴＢを送信しなくてはならない。さらに、ノード６、ノード７及びノード８は、それぞれ、１ＴＢの新たなデータを受信しなくてはならない。
【００１８】
特にノード６の担当範囲は２倍になると共に、ノード３から１ＴＢのデータを受信しつつノード８に１ＴＢのデータを送信しなくてはならず、高負荷状態になってしまうことが多い。また、レプリケーション数３に戻すためにかかる時間は、１ＴＢのデータを転送するために必要な時間である。ネットワークが１Ｇｂｐｓであることから、約２時間１３分を要する。これは、データの冗長化の観点からは非常に長い時間である。もっと早くレプリケーション数を回復することが望ましい。
【００１９】
また、一般にハードディスクに代表される外部記憶装置の故障する確率は、負荷が高くなると高くなる。上記回復処理の間、ノード３、ノード４、ノード６及びノード７は、レプリケーション数が「２」の貴重なデータを保持しているにもかかわらず、それらの記憶装置へのアクセスが高まる（つまり記憶装置の負荷が高くなる）。
【００２０】
負荷が高くなると、故障確率が高くなり。上記ノードのいずれかが故障すると、レプリケーション数が「１」の１ＴＢデータが発生する。このデータを保持しているノードの負荷はさらに高くなるため、その故障確率がさらに高くなる。その結果、そのノードが故障すれば該当データは永遠に失われる。従って、この故障確率増大の連鎖を断ち切ることが重要である。
【００２１】
非特許文献３は、上述のように、ｋ個の異なるハッシュ関数を用いることにより、ｋ個のノードに同一データ（１つのオリジナルデータとｋ−１個のレプリカ）を格納することを開示する。しかし、この文献は、ノードの追加及び削除について開示しておらず、あるノードが故障により使用不可能になった場合には、そのノードに格納されていたデータのレプリケーション数は、システム全体でｋ−１に減少する。さらに、ｋ個のノードが故障した場合、システムからデータが失われる。
【００２２】
本発明はこのような状況に鑑みてなされたものであって、その１つの目的は、ノードの故障や削除などでレプリケーション数が低下したときにレプリケーション数を迅速に回復することである。
【課題を解決するための手段】
【００２３】
上記課題を解決するために、例えば特許請求の範囲に記載の構成を採用する。本願は上記課題を解決する手段を複数含んでいるが、その一例は、受信したデータを格納する情報記憶システムである。この情報記憶システムは、ネットワークと、前記ネットワークにより通信可能に接続された複数の情報記憶ノードと、前記複数の情報記憶ノードと通信可能に接続された管理部とを含む。前記受信したデータのそれぞれは、規定数の同一内容データに複製され、互いにあるいは一方向に対応付けられ、前記複数の情報記憶ノードのいずれかに格納される。前記管理部は、前記複製された同一内容データのそれぞれに対して、それぞれ互いに異なるカテゴリを与える。前記管理部は、前記異なるカテゴリを与えられた同一内容データのそれぞれを格納するための情報記憶ノードを前記複数の情報記憶ノードの中から決定する。前記管理部は、前記格納する情報記憶ノードの決定において、一つの情報記憶ノードが格納する同一カテゴリに属するデータのそれぞれに対応する他の情報記憶ノードに記憶される異なるカテゴリに属する同一内容データは、複数の情報記憶ノードに分散するように前記決定を行い、前記受信したデータに含まれる情報の一部または全部をカテゴリごとに定めた演算式に代入して前記決定を行う。前記複数の情報記憶ノードにおける第一の情報記憶ノードの使用停止に際して、前記複数の情報記憶ノードのそれぞれは、自身が格納しているデータのうち前記第一の情報記憶ノードに格納されているデータと同一内容であり、かつ、前記自身が格納しているデータが属しているカテゴリと前記第一の情報記憶ノードで属しているカテゴリとが予め対応づけられているデータ、を抽出し、前記抽出したデータを予め定められた手順に従って選択した情報記憶ノードに複製する。
【発明の効果】
【００２４】
本発明の一態様によれば、複数の情報記憶ノードを含む情報記憶システムにおいて、データを格納する情報記憶ノードの数が減少した場合に、減少したレプリケーション数を増加するためのデータ複製に必要な時間を短縮することができる。上記以外の課題、構成及び効果は、以下の実施形態の説明により明らかにされる。
【図面の簡単な説明】
【００２５】
【図１】第１の実施形態の情報記憶ノードの論理構成を模式的に示す図である。
【図２】第１の実施形態の情報記憶システム及びその周辺機器の構成例を示すブロック図である。
【図３】第１の実施形態のクライアントの構成例を模式的に示すブロック図である。
【図４】第１の実施形態の管理ノードの構成例を模式的に示すブロック図である。
【図５】第１の実施形態の情報記憶ノードの構成例を模式的に示すブロック図である。
【図６】第１の実施形態において、各情報記憶ノードの担当ハッシュ値範囲及び生死情報を管理するノード管理テーブルの一例を示す図である。
【図７】第１の実施形態において、ノード２のデータを格納するデータ格納テーブルの例である。
【図８】第１の実施形態において、ノード４のデータを格納するデータ格納テーブルの例である。
【図９】第１の実施形態において、ノードＮが死んだときの処理を示すフローチャートである。
【図１０】第１の実施形態において、情報記憶ノード自身が持っているデータのうちノードＮに関係するデータを抽出するフローチャートである。
【図１１】第１の実施形態において、キーの値からデータを格納する（書き込む）情報記憶ノードを決定するフローチャートである。
【図１２】第１の実施形態において、クライアントがキーを用いてバリューを書き込む処理例を示すフローチャートである。
【図１３】第１の実施形態において、クライアントが情報記憶システムから情報を読み出す処理例を示すフローチャートである。
【図１４】第１の実施形態において、キーを用いてＡＬＩＶＥ状態のノードから読み出すべき情報記憶ノードを見つけるためのフローチャートである
【図１５】第１の実施形態において、キーを用いてＳＵＢＳＴＩＴＵＴＥＤ状態の情報記憶ノードのバックアップ先の情報記憶ノードから読み出すべき情報記憶ノードを見つける処理例を示すフローチャートである。
【図１６】第１の実施形態において、２つの情報記憶ノードの間に他の情報記憶ノードを挿入する処理を示すフローチャートである。
【図１７】第１の実施形態において、自身が持っているデータから挿入された情報記憶ノードに関係するデータを抽出する処理を示すフローチャートである。
【図１８】第２の実施形態において、情報記憶ノードが死んだことに対するデータ再配置の実行中に、別の情報記憶ノードが死んだときの処理を示すフローチャートである。
【発明を実施するための形態】
【００２６】
以下において、本発明を実施するための形態を説明する。説明の明確化のため、以下の記載及び図面は、適宜、省略及び簡略化がなされている。又、各図面において、同一要素には同一の符号が付されており、説明の明確化のため、必要に応じて重複説明は省略されている。
【００２７】
＜第１の実施の形態＞
以下において、第１の実施形態を説明する。本実施形態は、分散データストア（分散情報記憶システム）を説明する。分散データストアにおいて、オリジナルデータが複製され、オリジナルデータと１以上の複製データが、異なる情報記憶ノードに格納される。これにより、高速な処理と高い障害耐性を実現できる。
【００２８】
本発明は、２つのデータのペアを単位としてデータを管理するキーバリューストアに特に好適である。そこで、本実施形態においては、キーバリューストアの例を説明する。本発明は、これと異なる分散システムにも適用できる。キーバリューストアは、キーとバリューのペアを格納する。ユーザは、目的のバリューのキーを指定してそのバリュー（及びキー）を取得する。
【００２９】
分散キーバリューストアは、キーの値に応じて、そのオリジナルデータ及びレプリカ（オリジナルデータを複製したデータ）の保存先のサーバ（ノード）を変える。図１を参照して、本実施形態のシステムがオリジナルデータ及びそのレプリカを格納するノードを決定する方法を説明する。図１は、キーであるデータ「東京」１１０の格納先を決定する例を説明する。選択されたサーバは、それぞれ、キーとバリュー（不図示）のペア（オリジナルペア又はびペアの複製）を格納する。図１の説明においては、バリューへの言及は省略する。
【００３０】
図１は、本実施形態の情報記憶システムに含まれる情報記憶ノード（以下においてノードとも呼ぶ）の論理構成の例を示している。システムは、複数の情報記憶ノードを備えている。図１は、リング状に配置された、情報記憶ノード１（１０１）から情報記憶ノード７（１０７）の７つの情報記憶ノードを例示している。情報記憶ノードの配置は、データ（オリジナルデータ及びレプリカ）を格納する情報記憶ノードを決定するための論理空間におけるノード配置（論理位置）を示しており、システムにおける情報記憶ノードの物理配置を意味していない。
【００３１】
図１は、情報記憶システムが、ユーザデータ（キー）「東京」１１０を、システム内の情報記憶ノードに割り当てる方法を模式的に示している。データ「東京」１１０のオリジナルノードはノード２（１０２）であり、この情報記憶ノードはオリジナルデータ１１１を格納している。
【００３２】
第一レプリカ格納ノードはノード４（１０４）であり、第一レプリカ（データ「東京」）１１２を格納している。第二レプリカ格納ノードはノード７（１０７）であり、第二レプリカ（データ「東京」）１１３を格納している。
【００３３】
情報記憶システムは、ユーザデータの３つのカテゴリ（オリジナルデータ、第一レプリカ及び第二レプリカ）のそれぞれのデータを格納する情報記憶ノードを決定するため、３つの異なる演算式を使用する。これら演算式を使用して、ユーザデータから、異なる演算値を得ることができる。
【００３４】
好ましい方法として、情報記憶システムは、ハッシュ関数を使用して、オリジナルデータ及び２つのレプリカを割り当てる情報記憶ノードを決定する。ハッシュ関数としては、ＭＤ５、ＳＨＡ−１、ＳＨＡ−２５６などがよく知られている。例えば、本実施形態の情報記憶システムは、オリジナルデータ、第一レプリカ、第二レプリカのそれぞれに異なるハッシュ関数を用意し、それぞれのハッシュ関数によるキー（本例でデータ「東京」）のハッシュ値により、オリジナルデータ及びレプリカのそれぞれを格納する情報記憶ノードを決定する。
【００３５】
若しくは、好ましい方法の一つとして、情報記憶システムは、規定の演算方法（例えば異なる値の結合）によりキーから異なる３つの値を算出し、その値を同一のハッシュ関数に代入することで、３つの異なるハッシュ値を得ることができる。
【００３６】
このように、各データカテゴリ（オリジナルデータ、第一レプリカ、第二レプリカ）に対応してキーから異なる値を算出することで、データを格納する情報記憶ノードの決定に必要とするハッシュ関数の種類を少なくすることができる。異なる代入値を算出する方法においても、いくつかのカテゴリには異なるハッシュ関数を適用してもよい。また、ハッシュ関数とは異なる関数を使用して、データを格納する情報記憶ノードを決定してもよい。
【００３７】
図１における円（情報記憶ノードの論理的な位置を示す線）上には、あらかじめ時計回りにハッシュ値の最小値からハッシュ値の最大値までの数が振られている。ハッシュ値は、ある値をハッシュ関数に代入して得られる値である。円上に配置されたノード１（１０１）からノード７（１０７）は、それぞれ、ハッシュ値の担当範囲を持っている。
【００３８】
例えば、ノード２（１０２）は、ノード１（１０１）からノード２（１０２）までの円上のハッシュ値範囲が、担当範囲である。格納データの担当ノードを決定は、例えば、データのハッシュ値に対して、担当範囲と担当ノードを結び付けている表を参照することにより行う。各情報格納ノードの論理位置は、データのカテゴリ毎に異なっていてもよい。
【００３９】
任意の２つのデータに関してオリジナルノードが同一であったとしても第一のレプリカ格納ノードは同一であるとは限らず、むしろ多くの場合異なる。同様に第二のレプリカ格納ノードも多くの場合異なる。
【００４０】
例えば、データ「東京」１１０の第一レプリカ格納ノードはノード４（１０４）であり、第二レプリカ格納ノードはノード７（１０７）であるが、オリジナル格納ノードがノード２（１０２）である他のデータは、第一レプリカ格納ノードとして情報記憶ノード４（１０４）と異なるノードに割り当てられ、第二レプリカ格納ノードとして情報記憶ノード７（１０７）と異なるノードに割り当てられうる。例えばデータ「パリ」はオリジナルノードはノード２であるが、第一のレプリカ格納ノードはノード５２１であり、第二のレプリカ格納ノードはノード５４３である。
【００４１】
このように、各ノードの複数の異なるオリジナルデータの第一レプリカは、複数の他ノードに分散されて格納される。同様に、複数の異なるオリジナルデータの第二レプリカも、複数の他ノードに分散されて格納される。
【００４２】
図１の例において、データ「東京」１１０のハッシュ値は、情報記憶ノード１（１０１）から情報記憶ノード２（１０２）の間に入る。そのため、ノード２（１０２）が、データ１１０のオリジナル格納ノード（オリジナルデータを格納するノード）である。情報記憶ノード１以外のノードＮ（Ｎは全ノード数以下の自然数）の担当範囲は、ノードＮ−１の担当ハッシュ値範囲のエンド値に１を加算した値から、ノードＮの担当ハッシュ値範囲のエンド値までの間である。
【００４３】
情報記憶ノード１の担当範囲は、ハッシュ値の最小の値から情報記憶ノード１の担当ハッシュ値のエンド値までの範囲と、最後のノードの担当ハッシュ値のエンド値に１を加算した値からハッシュ値の最大値までの範囲、の両方の範囲をあわせた範囲である。
【００４４】
図１において、円で示されるデータ１２１Ａからデータ１２１Ｆは、それぞれ、ノード２（１０２）が、故障その他の原因によりシステムから外されたことに応答して、各情報記憶ノードが他の情報記憶ノード（図１において隣の情報記憶ノード）に複製するデータの集合を示している。複製されるデータ１２１Ａ〜データ１２１Ｆは、オリジナルデータ、第一レプリカ及び第二レプリカを含む。
【００４５】
各情報記憶ノードは、規定の規則に従って、使用が停止される情報記憶ノードに関係するデータを、他の情報記憶ノードに複製する。複製するデータについては後述する。図１の例において、ノード４（１０４）における第一レプリカ１１２は複製されるデータ１２１Ｂに含まれるが、ノード７（１０７）における第二レプリカ１１３は複製されるデータ１２１Ｅから外れている。
【００４６】
図１の例においては、ノード２（１０２）を除く図示された情報記憶ノード全てが、データを他の情報記憶ノードに複製するように記載されているが、システム内の全ての情報記憶ノードが、複製すべきデータを持っているとは限らない。
【００４７】
各情報記憶ノードは、情報記憶ノードの除去に伴い一時的にデータを複製するための記憶領域を確保する。図１においては、ノード５（１０５）で確保された記憶領域１２４に、例として符号を付している。他の情報記憶ノードも、同様に、複製データを格納する記憶領域を確保する。この記憶領域の利用方法については後述する。
【００４８】
このように、情報記憶システムは、ユーザデータと同一の複数のデータを格納する。上記例は、オリジナルデータ、第一レプリカ及び第二レプリカの３つの同一データを格納する。レプリケーション数は、システム設計に依存する。
【００４９】
このように、格納される同一の３データは、それぞれ異なるカテゴリ（オリジナル、第一レプリカ等）が与えられ、異なるグループ、つまり、オリジナルデータのグループ、第一レプリカのグループそして第二レプリカのグループに属する。
【００５０】
上述のように、１つの情報記憶ノードに格納される任意のカテゴリ（例えばオリジナルデータ）の複数データを考えると、それらに対応する同一の他のカテゴリ（例えば第一レプリカ）の複数データは、他の１つの情報記憶ノードに集中するようなことはなく、複数の情報記憶ノードに分散して格納するように配置する。各データカテゴリのデータの情報記憶ノードの決定に異なる演算式を使用することで、異なるカテゴリの同一データを他の複数の情報記憶ノードに分散して格納する。上述の好ましい演算式は、ハッシュ関数を含む。
【００５１】
次に、図２を参照して、本実施形態の情報記憶システムの構成の概要を説明する。図２は、本実施形態の情報記憶システム２０９及びその周辺機器の構成例を模式的に示すブロック図である。情報記憶システム２０９は、情報記憶ノード（サーバ）２０１、２０２、２０３、管理ノード（管理サーバ）２０４及び通信制御装置２０５を備えている。図２は、一例として、３つの情報記憶ノード２０１、２０２、２０３を示しており、実際のシステムは、典型的に、１００を超える多くの情報記憶ノードを備える。
【００５２】
情報記憶ノード２０１、２０２、２０３、それぞれ、通信制御装置２０５を介して通信可能に接続されており、さらに、管理ノード２０４は、情報記憶ノード２０１、２０２、２０３に、通信制御装置２０５を介して通信可能に接続している。情報記憶システム２０９は、通信制御装置２０５により、外部ネットワーク２０６に接続している。クライアント２０７、２０８は、外部ネットワーク２０６に接続し、通信制御装置２０５を介して、情報記憶ノード２０１、２０２、２０３及び管理ノード２０４と通信することができる。
【００５３】
本システムにおいて、ユーザは、クライアント２０７、２０８を操作して、情報記憶ノード２０１、２０２、２０３にデータを書き込み、そして、情報記憶ノード２０１、２０２、２０３からデータを読み出す。
【００５４】
クライアント２０７、２０８は、データの書き込みにおいて、ネットワーク２０６及び通信制御装置２０５を介して、管理ノード２０４に「キー」を送信し、データ（キーバリューペア）を書き込むべき３つノードを示すように要求する。管理ノード２０４は、クライアント２０７、２０８からのキーを伴う要求に応答して、受信したキーの値から規定の演算に従ってデータを格納するノードを決定し、決定したノードの識別子をクライアント２０７、２０８に返す。
【００５５】
クライアント２０７、２０８は、指示されたノードに、オリジナルデータ及びレプリカを送信する。各ノードは、ネットワーク２０６及び通信制御装置２０５を介して、データを受信し、それを格納する。
【００５６】
これと異なり、オリジナルノードが、第一及び第二のレプリカノードにオリジナルデータの複製（第一及び第二のレプリカ）を格納してもよい。この構成においては、管理ノード２０４は、クライアント２０７、２０８からの格納ノード要求に応答して、オリジナルノードの識別子のみをクライアント２０７、２０８に返す。
【００５７】
クライアント２０７、２０８は、書き込み指示と共にキーバリューペアを指定されたオリジナルノードに送信し、オリジナルノードにキーバリューペアを書き込む（格納する）。書き込み指示とデータを受信したオリジナルノードは、受信したデータをその記憶デバイスに格納すると共に、第一及び第二レプリカをそれぞれ格納するノードを、上記管理ノード２０４に問い合わせるか、または管理ノード２０４と同様の手法により決定する。オリジナルノードは、決定したノードに、通信制御装置２０５を介して、データ書き込みの指示及びデータを送信する。受信したノードは、それぞれ、データを記憶デバイスに格納する。
【００５８】
データの読み出しにおいて、クライアント２０７、２０８は、「キー」を管理ノード２０４に伝え、データを読み出すべきノードを示すように要求する。管理ノード２０４は、クライアント２０７、２０８からのキーを伴う要求に応答して、そのキーから、規定の演算によりデータを格納しているノードを特定する。管理ノード２０４は、データを読み出すノードの識別子を、クライアント２０７、２０８に返す。クライアント２０７、２０８は、管理ノード２０４から指定されたノードに、キーと共に読み出し要求を送信し、そのノードからキーバリューペアを受信する。
【００５９】
上述のように、ユーザは、クライアント２０７、２０８を使用して、データの書き込み及び読み出しを行う。図３は、クライアント２０７の構成を模式的に示すブロック図である。クライアント２０８は、クライアント２０７と同様の構成を有している。クライアント２０７は計算機であり、入力デバイス２７１、プロセッサ２７２、ネットワークインタフェース２７３、ディスプレイ２７４、主記憶デバイス２７５及び二次記憶デバイス２７６を備える。これらは、バス２７８により通信可能に接続されている。
【００６０】
クライアント２０７は、ネットワークインタフェース２７３を介して、ネットワーク２０６に接続し、他の計算機と通信する。ユーザは、入力デバイス２７１（例えばマウス及びキーボード）により必要な情報を入力し、ディスプレイ２７４により必要な情報を視認することができる。
【００６１】
プロセッサ２７２は、主記憶デバイス２７５に記憶されているプログラムを実行することによってクライアント２０７の所定の機能を実現する。主記憶デバイス２７５は、プロセッサ２７２によって実行されるプログラム、及び、プログラムの実行に必要なデータを記憶する。プログラムは、不図示のＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）の他、リードライトクライアントプログラム２７７を含む。プロセッサ２７２は、複数のチップ及び複数のパッケージを含むことができる。
【００６２】
説明の便宜上、リードライトクライアントプログラム２７７は主記憶デバイス２７５内に示されているが、典型的には、プログラムは、二次記憶デバイス２７６の記憶領域から主記憶デバイス２７５の記憶領域にロードされる。記憶デバイス２７５、２７６は、１つの記憶デバイスとして機能することができる。二次記憶デバイス２７６は、クライアント２０７の所定の機能を実現するために必要なプログラム及びデータを格納する、不揮発性の永続的記憶媒体を備える記憶装置である。二次記憶デバイス２７６は、ネットワークを介して接続された外部の記憶装置でもよい。
【００６３】
ユーザは、リードライトクライアントプログラム２７７を使用して、管理ノード２０４及び情報記憶ノード２０１、２０２、２０３と通信する。リードライトクライアントプログラム２７７、入力デバイス２７１によるユーザ入力又は他のプログラムからの入力に応じて、データの書き込み及び読み出しのために必要な情報を管理ノード２０４又は情報記憶ノード２０１、２０２、２０３に送信し、それらから情報を受信する。ディスプレイ２７４は、情報記憶ノード２０１、２０２、２０３から受信したデータを表示する。
【００６４】
次に、図４を参照して、管理ノード２０４の構成を説明する。図４は、管理ノード２０４の構成を模式的に示すブロック図である。管理ノード２０４は、情報記憶ノード２０１、２０２、２０３及びその処理を管理する計算機である。管理ノード２０４は、複数の計算機（計算機システム）で構成されていてもよい。管理ノード２０４は、情報記憶ノード２０１、２０２、２０３へのアクセス（データ書き込み及びデータ読み出し）を管理すると共に、システム内で稼動するノードの追加及び削除に伴う処理を管理する。
【００６５】
管理ノード２０４は、ネットワークインタフェース２４１、プロセッサ２４２、主記憶デバイス２４３及び二次記憶デバイス２４４を備える。これらは、バス２４９により通信可能に接続されている。プロセッサ２４２は、主記憶デバイス２４３に記憶されているプログラムを実行することによって管理ノード２０４の所定の機能を実現する。プロセッサ２４２は、複数のチップ及び複数のパッケージを含むことができる。
【００６６】
主記憶デバイス２４３は、プロセッサ２４２によって実行されるプログラム及びプログラムの実行に必要なデータを記憶する。プログラムは、不図示のＯＳの他、ノード管理プログラム２４５、リードライト管理プログラム２４６及びデータ再配置管理プログラム２４７を含む。
【００６７】
ノード管理プログラム２４５は、情報記憶ノードを管理する処理を行い、システムに含まれる情報記憶ノードの担当範囲及びその状態などを管理する。リードライト管理プログラム２４６は、情報記憶ノードへのデータ書き込み及びデータ読み出し（ノードへアクセス）を管理する処理を行う。データ再配置管理プログラム２４７は、ノードの追加・削除に伴うノード間のデータ再配置を管理する。これらプログラム２４５〜２４７が行う処理の詳細は後述する。
【００６８】
説明の便宜上、図４において、プログラム２４５〜２４７は主記憶デバイス２４３内に示されている。典型的には、プログラムは、二次記憶デバイス２４４の記憶領域から主記憶デバイス２４３の記憶領域にロードされる。記憶デバイス２４３、２４４は、１つの記憶デバイスとして機能することができる。
【００６９】
二次記憶デバイス２４４は、図示するノード管理テーブル２４８の他、管理ノード２０４の所定の機能を実現するために必要なプログラム及びデータを格納する、不揮発性の永続的記憶媒体を備える記憶デバイスである。ノード管理テーブル２４８については、図６を参照して後述する。二次記憶デバイス２４４は、ネットワークを介して接続された外部の記憶デバイスでもよい。管理ノード２０４は、リードライトクライアントプログラム２７７を実行し、入出力装置を介してユーザ操作を受け付けてもよい。
【００７０】
次に、図５を参照して、情報記憶ノード２０１の構成を説明する。他の情報記憶ノード２０２、２０３も、情報記憶ノード２０１と同一構成を有しており、説明を省略する。図５は、情報記憶ノード２０１の構成を模式的に示すブロック図である。情報記憶ノード（サーバ）２０１は、キーバリューペアを格納する計算機である。情報記憶ノードは複数の計算機を含んでいてもよい。
【００７１】
情報記憶ノード２０１は、ネットワークインタフェース２１１、プロセッサ２１２、主記憶デバイス２１３及び二次記憶デバイス２１４を備える。これらは、バス２１５により通信可能に接続されている。プロセッサ２１２は、主記憶デバイス２１３の記憶領域に記憶されているプログラムを実行することによって情報記憶ノード２０１の所定の機能を実現する。
【００７２】
主記憶デバイス２１３は、プロセッサ２１２によって実行されるプログラム及びプログラムの実行に必要なデータを記憶する。プログラムは、不図示のＯＳの他、リードライト処理プログラム２１６及びデータ再配置処理プログラム２１７を含む。プロセッサ２１２は、複数のチップ及び複数のパッケージを含むことができる。
【００７３】
リードライト処理プログラム２１６は、クライアント２０７、２０８からの要求に応じたデータの書き込み及び読み出しの処理を行う。データ再配置処理プログラム２１７は、システム内のノードの削除・追加に伴うノード間でのデータ再配置の処理を行う。これらプログラム２１６、２１７が行う処理の詳細は後述する。
【００７４】
説明の便宜上、図５において、プログラム２１６、２１７は主記憶デバイス２１３内に示されている。典型的には、プログラムは、二次記憶デバイス２１４の記憶領域から主記憶デバイス２１３の記憶領域にロードされる。記憶デバイス２１３、２１４は１つの記憶デバイスとして機能することができる。
【００７５】
二次記憶デバイス２１４は、図示するデータ格納テーブル２１８の他、情報記憶ノード２０１の所定の機能を実現するために必要なプログラム及びデータを格納する、不揮発性の永続的記憶媒体を備える記憶デバイスである。データ格納テーブル２１８については、図７を参照して後述する。二次記憶デバイス２１４は、ネットワークを介して接続された外部の記憶デバイスでもよい。
【００７６】
上述のように、プログラムはプロセッサによって実行されることで、定められた処理を記憶装置及び通信ポート（通信デバイス）を用いながら行う。従って、本実施形態及び他の実施形態においてプログラムを主語とする説明は、プロセッサを主語とした説明でもよい。若しくは、プログラムが実行する処理は、そのプログラムが動作する計算機が行う処理である。プロセッサは、プログラムに従って動作することによって、所定の機能を実現する機能部として動作する。
【００７７】
プログラムの少なくとも一部は、専用ハードウェアによって実現されてもよい。プログラムは、プログラム配布サーバや、計算機読み取り可能な永続的記憶媒体によって各計算機にインストールすることができ、各計算機の不揮発性記憶装置に格納することができる。
【００７８】
図６は、管理ノード２０４が格納しているノード管理テーブル２４８の一例を示す図である。ノード管理テーブル２４８は、ノード管理プログラム２４５（管理ノード２０４）が各情報記憶ノードを管理する、具体的には、各情報記憶ノードの担当ハッシュ値範囲及び生死状態を管理するためのテーブルである。各行（レコード）は、１つのノードについての情報を格納しており、本例のノード管理テーブル２４８は、１０００ノードを管理している。つまり、本情報記憶システム２０９は、１０００のノードを含む。
【００７９】
「ノード名」のカラム６０１は、各ノードのノード名を格納する。具体的には、行（エントリ）６０４は、「ノード名」が「ノード１」であるノードに関する記述である。行６０５は、「ノード名」が「ノード２」であるノードに関する記述である。行６０６は、「ノード名」が「ノード３」であるノードに関する記述である。行６０７は、「ノード名」が「ノード４」であるノードに関する記述である。行６０８は、「ノード名」が「ノード５」であるノードに関する記述である。
【００８０】
行６０９は、「ノード名」が「ノード６」であるノードに関する記述である。行６１０は「ノード名」が「ノード７」であるノードに関する記述である。行６１１は、「ノード名」が「ノード８」であるノードに関する記述である。行６１２は、「ノード名」が「ノード９」であるノードに関する記述である。行６１３は「ノード名」が「ノード１０」であるノードに関する記述である。
【００８１】
行６１４は、「ノード名」が「ノード１１」であるノードに関する記述である。行６１５は、「ノード名」が「ノード１２」であるノードに関する記述である。行６１６は途中のエントリが、図６において省略されていることを示す。行６１７は、「ノード名」が「ノード９９９」であるノードに関する記述である。行６１８は、「ノード名」が「ノード１０００」であるノードに関する記述である。
【００８２】
「担当ハッシュ値範囲のエンド値」のカラム６０２は、各ノードが担当するハッシュ値範囲の最後の値を格納している。具体的には、「ノード１」の「担当ハッシュ値範囲のエンド値」は、「２２６」である。「ノード２」の「担当ハッシュ値範囲のエンド値」は「５３５」である。「ノード１」の「担当ハッシュ値範囲のエンド値」は「２２６」であることから、「ノード２」の「担当ハッシュ値範囲」は、（ノード１のエンド値「２２６」の次の数である）２２７から５３５であることを意味している。
【００８３】
同様に「ノード名」が「ノード３」であるノードの「担当ハッシュ値範囲のエンド値」は「８４２」である。「ノード３」の担当ハッシュ値範囲は５３６から８４２であることを意味する。以下同様に「ノード名」が「ノード４」であるノードの「担当ハッシュ値範囲のエンド値」は、「１２３１」である。「ノード名」が「ノード５」であるノードの「担当ハッシュ値範囲のエンド値」は、「２１４５」である。「ノード名」が「ノード６」であるノードの「担当ハッシュ値範囲のエンド値」は、「２３５２」である。
【００８４】
「ノード名」が「ノード７」であるノードの「担当ハッシュ値範囲のエンド値」は「３１２５」である。「ノード名」が「ノード８」であるノードの「担当ハッシュ値範囲のエンド値」は「４２３１」である。「ノード名」が「ノード９」であるノードの「担当ハッシュ値範囲のエンド値」は「４８４５」である。「ノード名」が「ノード１０」であるノードの「担当ハッシュ値範囲のエンド値」は、「５２５２」である。
【００８５】
「ノード名」が「ノード１１」であるノードの「担当ハッシュ値範囲のエンド値」は、「６６２５」である。「ノード名」が「ノード１２」であるノードの「担当ハッシュ値範囲のエンド値」は、「６７５２」である。「ノード名」が「ノード９９９」であるノードの「担当ハッシュ値範囲のエンド値」は、「６４５２３」である。「ノード名」が「ノード１０００」であるノードの「担当ハッシュ値範囲のエンド値」は、「６５１２３」である。
【００８６】
「生死情報」のカラム６０３は、各ノードの生死状態を示す情報を格納する。具体的には、各ノードが、生きている（ＡＬＩＶＥ状態）、死んでいる（ＤＥＡＤ状態）又は置き換えられた状態（ＳＵＢＳＴＩＴＵＴＥＤ状態）であるかを示す。ＡＬＩＶＥ状態は、情報記憶ノードが正常動作していることを示す。ＤＥＡＤ状態は、情報記憶ノードが故障又は他の理由により正常動作しておらずアクセスを受け付けないと共に、その担当データが、他の情報記憶ノードに再配置されていない（再配置前）であることを意味する。
【００８７】
ＳＵＢＳＴＩＴＵＴＥＤ状態の記憶ノードは、ＤＥＡＤ状態になったあとに、その担当データが他のＡＬＩＶＥ状態の情報記憶ノードに再配置されていることを意味する。ＡＬＩＶＥ状態の情報記憶ノードは、故障又は他の理由によりＤＥＡＤ状態になり、その後、担当データが他の情報記憶ノードに再配置されると、ＳＵＢＳＴＩＴＵＴＥＤ状態に変化する。これらの状態及び状態変化の詳細は後述する。
【００８８】
本例のノード管理テーブル２４８において、「ノード名」が「ノード１」であるノードの「生死情報」は、「ＡＬＩＶＥ」である。「ノード名」が「ノード２」であるノードの「生死情報」は、「ＡＬＩＶＥ」である。「ノード３」であるノードの「生死情報」は「ＡＬＩＶＥ」である。「ノード名」が「ノード４」であるノードの「生死情報」は、「ＡＬＩＶＥ」である。
【００８９】
「ノード名」が「ノード５」であるノードの「生死情報」は、「ＡＬＩＶＥ」である。「ノード名」が「ノード６」であるノードの「生死情報」は、「ＡＬＩＶＥ」である。「ノード名」が「ノード７」であるノードの「生死情報」は、「ＡＬＩＶＥ」である。「ノード名」が「ノード８」であるノードの「生死情報」は、「ＡＬＩＶＥ」である。「ノード名」が「ノード９」であるノードの「生死情報」は、「ＤＥＡＤ」である。
【００９０】
「ノード名」が「ノード１０」であるノードの「生死情報」は、「ＡＬＩＶＥ」である。「ノード名」が「ノード１１」であるノードの「生死情報」は、「ＳＵＢＳＴＩＴＵＴＥＤ」である。「ノード名」が「ノード１２」であるノードの「生死情報」は、「ＡＬＩＶＥ」である。「ノード名」が「ノード９９９」であるノードの「生死情報」は、「ＡＬＩＶＥ」である。「ノード名」が「ノード１０００」であるノードの「生死情報」は、「ＡＬＩＶＥ」である。
【００９１】
図７は、情報記憶ノードが有するデータ格納テーブル２１８の例を示す図である。データ格納テーブル２１８は、情報記憶ノードが格納しているキーバリューペアのそれぞれの値に加え、そのキーバリューペアを格納する格納ノードを、そのキーバリューペアに関連付けて格納している。
【００９２】
図７は、図１における情報記憶ノード２（１０２）が保持しているデータ格納テーブル２１８を例示してある。「キー」のカラム７０１は、該当項目のキーを示す列である。行（エントリ）７０６は、「キー」が「東京」であるペアに関する記述である。行７０７は、「キー」が「パリ」であるペアに関する記述である。行７０８は、「キー」が「ロンドン」であるペアに関する記述である。
【００９３】
行７０９は、「キー」が「ベルリン」であるペアに関する記述である。行７１０は、「キー」が「ワシントン」であるペアに関する記述である。行７１１は、「キー」が「サンノゼ」であるペアに関する記述である。行７１２は、「キー」が「上海」であるペアに関する記述である。行７１３は、図７において途中のエントリが省略されていることを示す。行７１４は、「キー」が「広島」であるペアに関する記述である。行７１５は、「キー」が「長崎」であるペアに関する記述である。
【００９４】
「オリジナル格納ノード」のカラム７０２は、オリジナルデータが格納されているノード名を記述する。例えば、「キー」が「東京」であるペアの「オリジナル格納ノード」は、「ノード２」である。「キー」が「パリ」であるペアの「オリジナル格納ノード」は、「ノード２」である。「キー」が「ロンドン」であるペアの「オリジナル格納ノード」は、「ノード２」である。「キー」が「ベルリン」であるペアの「オリジナル格納ノード」は、「ノード２」である。
【００９５】
「キー」が「ワシントン」であるペアの「オリジナル格納ノード」は、「ノード６２」である。「キー」が「サンノゼ」であるペアの「オリジナル格納ノード」は、「ノード４」である。「キー」が「上海」であるペアの「オリジナル格納ノード」は、「ノード４７５」である。「キー」が「広島」であるペアの「オリジナル格納ノード」は、「ノード７５４」である。「キー」が「長崎」であるペアの「オリジナル格納ノード」は、「ノード３５２」である。
【００９６】
「第一レプリカ格納ノード」のカラム７０３は、第一レプリカが格納されているノード名を記述する。例えば、「キー」が「東京」であるペアの「第一レプリカ格納ノード」は、「ノード４」である。「キー」が「パリ」であるペアの「第一レプリカ格納ノード」は、「ノード５２１」である。「キー」が「ロンドン」であるペアの「第一レプリカ格納ノード」は、「ノード３６」である。
【００９７】
「キー」が「ベルリン」であるペアの「第一レプリカ格納ノード」は、「ノード９６５」である。「キー」が「ワシントン」であるペアの「第一レプリカ格納ノード」は、「ノード２」である。「キー」が「サンノゼ」であるペアの「第一レプリカ格納ノード」は、「ノード２」である。「キー」が「上海」であるペアの「第一レプリカ格納ノード」は、「ノード２３４」である。「キー」が「広島」であるペアの「第一レプリカ格納ノード」は、「ノード８５４」である。「キー」が「長崎」であるペアの「第一レプリカ格納ノード」は、「ノード１２０」である。
【００９８】
「第二レプリカ格納ノード」のカラム７０４は、第二レプリカが格納されているノード名を記述する。例えば、「キー」が「東京」であるペアの「第二レプリカ格納ノード」は「ノード７」である。「キー」が「パリ」であるペアの「第二レプリカ格納ノード」は「ノード５４３」である。「キー」が「ロンドン」であるペアの「第二レプリカ格納ノード」は「ノード３３９」である。
【００９９】
「キー」が「ベルリン」であるペアの「第二レプリカ格納ノード」は「ノード１４５」である。「キー」が「ワシントン」であるペアの「第二レプリカ格納ノード」は「ノード６９５」である。「キー」が「サンノゼ」であるペアの「第二レプリカ格納ノード」は「ノード３０５」である。「キー」が「上海」であるペアの「第二レプリカ格納ノード」は「ノード２」である。「キー」が「広島」であるペアの「第二レプリカ格納ノード」は「ノード２」である。「キー」が「長崎」であるペアの「第二レプリカ格納ノード」は「ノード２」である。
【０１００】
「バリュー」のカラム７０５は、キーのバリュー値を格納する。例えば、「キー」が「東京」であるペアの「バリュー」は「晴れ」である。「キー」が「パリ」であるペアの「バリュー」は「雨」である。「キー」が「ロンドン」であるペアの「バリュー」は「曇り」である。「キー」が「ベルリン」であるペアの「バリュー」は「雪」である。
【０１０１】
「キー」が「ワシントン」であるペアの「バリュー」は「晴れ」である。「キー」が「サンノゼ」であるペアの「バリュー」は「晴れ」である。「キー」が「上海」であるペアの「バリュー」は「快晴」である。「キー」が「広島」であるペアの「バリュー」は「曇り」である。「キー」が「長崎」であるペアの「バリュー」は「雨」である。
【０１０２】
図８は、図１における情報記憶ノード４（１０４）のデータ格納テーブル２１８を示す図である。「キー」のカラム８０１は、各エントリのキーを格納する。行（エントリ）８０６は「キー」が「サンノゼ」であるペアに関する記述である。行８０７は「キー」が「東京」であるペアに関する記述である。行８０８は「キー」が「オタワ」であるペアに関する記述である。行８０９は「キー」が「ワシントン」であるペアに関する記述である。行８１０は、それ以降のエントリが省略されている旨を示す。
【０１０３】
「オリジナル格納ノード」のカラム８０２は、オリジナルデータが格納されているノード名を記述する。例えば、「キー」が「サンノゼ」であるペアの「オリジナル格納ノード」は「ノード４」である。「キー」が「東京」であるペアの「オリジナル格納ノード」は「ノード２」である。「キー」が「オタワ」であるペアの「オリジナル格納ノード」は「ノード４７５」である。「キー」が「ワシントン」であるペアの「オリジナル格納ノード」は「ノード６２」である。
【０１０４】
「第一レプリカ格納ノード」のカラム８０３は、第一レプリカを格納するノード名を記述する。例えば、「キー」が「サンノゼ」であるペアの「第一レプリカ格納ノード」は「ノード２」である。「キー」が「東京」であるペアの「第一レプリカ格納ノード」は「ノード４」である。「キー」が「オタワ」であるペアの「第一レプリカ格納ノード」は「ノード４」である。「キー」が「ワシントン」であるペアの「第一レプリカ格納ノード」は「ノード２」である。
【０１０５】
「第二レプリカ格納ノード」のカラム８０４は、第二レプリカが格納されているノード名を記述する。例えば、「キー」が「サンノゼ」であるペアの「第二レプリカ格納ノード」は「ノード３０５」である。「キー」が「東京」であるペアの「第二レプリカ格納ノード」は、「ノード７」である。「キー」が「オタワ」であるペアの「第二レプリカ格納ノード」は、「ノード２５６」である。「キー」が「ワシントン」であるペアの「第二レプリカ格納ノード」は、「ノード４」である。
【０１０６】
「バリュー」のカラム８０５は、キーのバリュー値を格納する。例えば、「キー」が「サンノゼ」であるペアの「バリュー」は、「晴れ」である。「キー」が「東京」であるペアの「バリュー」は、「晴れ」である。「キー」が「オタワ」であるペアの「バリュー」は、「快晴」である。「キー」が「ワシントン」であるペアの「バリュー」は、「晴れ」である。
【０１０７】
上述のように、管理ノード２０４は、ノード管理テーブル２４８を使用して処理を行い、情報記憶ノード２０１、２０２、２０３はデータ格納テーブル２１８を使用して処理を行う。本実施形態及び他の実施形態において、情報記憶システムが使用する情報（ノード管理のための情報や格納しているデータに関する情報など）は、データ構造に依存せずどのようなデータ構造で表現されていてもよい。例えば、テーブル、リスト、データベースあるいはキューから適切に選択したデータ構造体が、情報を格納することができる。情報記憶システムが使用する情報は、データ記憶装置における対応するデータ記憶領域に格納される。
【０１０８】
以下において、情報記憶システム２０９が行う処理を、図９〜図１７のフローチャートを参照して説明する。図９及び図１０は、正常動作していたノードＮが、故障その他の理由により死んだ場合の処理例を示している。図１１及び図１２は、情報記憶システム２０９の情報記憶ノードにデータを書き込む処理の例を示している。図１３〜図１５は、情報記憶システム２０９の情報記憶ノードからデータを読み出す処理の例を示している。図１６及び図１７は、ノードＮ（Ｎはノードの番号）とノードＮ＋１の間にノードＸを挿入する処理の例を示す。
【０１０９】
〔情報記憶ノード使用停止〕
まず、図９を参照して、ノードＮが死んだときの情報記憶システム２０９の行う処理を説明する。情報記憶ノードが死ぬと、その情報記憶ノードが格納しているデータ（典型的に、複数オリジナルデータ、複数第一レプリカ及び複数第二レプリカを含む）のそれぞれのレプリケーション数が、規定値（本例において３）から１だけ減少する。
【０１１０】
本情報記憶システム２０９は、減少したレプリケーション数を規定値に戻すため、死んだ情報記憶ノードに格納されていたデータ（その担当データ）と同一のデータを、他の情報記憶ノードに複製させることで、死んだ情報記憶ノードに格納されていたデータの再配置を行い、減少したレプリケーション数を規定値に戻す。
【０１１１】
図９は、ノードＮが死んだときの情報記憶システム２０９の処理例を、管理ノード２０４の処理を中心にフローチャートに示した図である。ステップＳ９０１において、管理ノード２０４のノード管理プログラム２４５は、ノードＮが死んだことを検知する。
【０１１２】
ノードＮが死んだことを検知する技術は広く知られているので詳細な説明を省略するが、典型的には、ノード管理プログラム２４５は、各情報記憶ノードに死活監視のための応答要求を送信し、その要求への正常応答を受信しない場合に、情報記憶ノードが死んでいると判定する。
【０１１３】
ステップＳ９０２において、ノード管理プログラム２４５は、ノード管理テーブル２４８において、ノードＮのエントリにおける生死情報フィールドの値を、「ＡＬＩＶＥ」から「ＤＥＡＤ」に変更する。ノード管理プログラム２４５は、管理ノード２０４のデータ再配置管理プログラム２４７に、ノードＮが「ＤＥＡＤ」状態になったことを通知する。
【０１１４】
ステップＳ９０３において、データ再配置管理プログラム２４７は、ノード管理テーブル２４８を参照して、生死のフィールドが「ＡＬＩＶＥ」の情報記憶ノードを特定し、それらの情報記憶ノードに、自身の格納しているデータのうちノードＮに関係するデータを抽出し、自身の時計回り隣の情報記憶ノード（隣のＡＬＩＶＥ状態の情報記憶ノード）に、その抽出したデータを複製することを指示する命令を送信する。
【０１１５】
図示していないが、管理ノード２０４は各情報記憶ノードのアドレスを有しており、上記特定した情報記憶ノードのアドレスに上記指示を送信する。管理ノード２０４は、各ＡＬＩＶＥ状態の情報記憶ノードに、データ複製先の隣のＡＬＩＶＥの情報記憶ノードを指定する情報を送ってもよいし、隣の情報記憶ノードがＡＬＩＶＥ状態ではない情報記憶ノードにのみ、その情報を送ってもよい。若しくは、各情報記憶ノードは、ノード管理テーブル２４８の複製を管理ノード２０４から定期的に及び／又は更新時に取得し、保持していてもよい。
【０１１６】
ステップＳ９０４において、データ再配置管理プログラム２４７は、全ての情報記憶ノードの複製作業が終わるまで待つ。各情報記憶ノードは、データ格納テーブル２１８を参照して、死んだノードＮに関係するデータを特定することができる。情報記憶ノードによる関係データ抽出処理の詳細は、図１０のフローチャートを参照して後述する。
【０１１７】
全ての情報記憶ノードの複製作業が終了すると、ノードＮに格納されていたそれぞれのデータのレプリケーション数は、減少した値である２から規定値の３に戻る。各情報記憶ノードは、複製作業が終了すると、それを管理ノード２０４に通知する。ステップＳ９０５において、データ再配置管理プログラム２４７は、全ての情報記憶ノードの複製作業の終了通知を受信すると、ノード管理テーブル２４８におけるノードＮのエントリの生死フィールドを、「ＤＥＡＤ」から「ＳＵＢＳＴＩＴＵＴＥＤ」に変更する。
【０１１８】
次に、ステップＳ９０６において、データ再配置管理プログラム２４７は、ノードＮの時計回りにおいて隣のノードＮ＋１に、データの収集を指示する。具体的には、ノードＮ＋１に、ノードＮが担当していたデータ（オリジナルデータ、第一レプリカ及び第二レプリカ）を、ノード管理テーブル２４８の生死のフィールドがＡＬＩＶＥの情報記憶ノードから集めるように指示する。具体的には、管理ノード２０４は、ＡＬＩＶＥ状態の情報記憶ノードの識別子を伴うデータ収集の指示を、ノードＮ＋１に送信する。
【０１１９】
ノードＮ＋１のデータ再配置処理プログラム２１７は、管理ノード２０４からの指示に応答して、ノードＮの担当データの収集を開始する。具体的には、データ再配置処理プログラム２１７は、管理ノード２０４からの指示が示すＡＬＩＶＥ状態の情報記憶ノードに対して、複製したデータ（Ｓ９０３における「関系するデータ」）を、ノードＮ＋１に送信するように要求する。
【０１２０】
要求を受けた各情報記憶ノードは、要求元のノードＮ＋１に複製したデータ（ノードＮが格納（担当）していたデータと同一のデータ）を送信する。その後、データ格納テーブル２１８における「ノードN」のフィールドを「ノードＮ＋１」に変更する。なおこの動作はＳ９０７実行後にデータ再配置管理プログラム２４７から指示されることにより実行する形態としても良い。
【０１２１】
ステップＳ９０７において、ノードＮの時計回りにおいて隣のノードＮ＋１が、ノードＮが担当していたすべてのデータを集めたら（その通知をノードＮ＋１のデータ再配置処理プログラム２１７から受信したら）、データ再配置管理プログラム２４７は、ノード管理テーブル２４８のノードＮのエントリを削除する。データ再配置管理プログラム２４７は、ノードＮのエントリにおける生死フィールドを、「ＳＵＢＳＴＩＴＵＴＥＤ」からＤＥＬＥＴＥＤに変更してもよい。以上の処理によりノードＮが死んだときの情報記憶システム２０９の行うべき処理を遂行することができる。
【０１２２】
次に、図１０を参照して、情報記憶ノードが自分の持っているデータのうち「関係するデータ」を抽出する処理の説明を行う。この処理は、図９のフローチャートにおけるステップＳ９０４で行われる。「関係するデータ」は、情報記憶ノードが所有しているデータのうち、他の情報記憶ノードが死んだことにより自身が隣の情報記憶ノードに複製を転送しなくてはならないデータである。
【０１２３】
図１０は、情報記憶ノードが持っているデータのうち、関係するデータを抽出する処理例のフローチャートを示す図である。ステップＳ１００１において、情報記憶ノードのデータ再配置処理プログラム２１７は、データ格納テーブル２１８から「オリジナルノード」が死んだノードＮであり、「第一レプリカ格納ノード」が自身であるエントリを抽出する。
【０１２４】
ステップＳ１００２において、データ再配置処理プログラム２１７は、データ格納テーブル２１８から、「第一レプリカ格納ノード」が死んだノードＮで、「第二レプリカ格納ノード」が自身であるエントリを抽出する。
【０１２５】
ステップＳ１００３において、データ再配置処理プログラム２１７は、データ格納テーブル２１８から、「第二レプリカ格納ノード」が死んだノードＮであり、「オリジナルノード」がそれ自身であるエントリを抽出する。
【０１２６】
ステップＳ１００４において、データ再配置処理プログラム２１７は、上記ステップＳ１００１〜ステップＳ１００３の３工程で抽出したエントリを「関係するデータ」としてまとめて、主記憶装置２１３に格納する。以上の処理により、情報記憶ノードが、自分の持っているデータのうち「関係するデータ」を抽出することができる。
【０１２７】
以上が情報記憶ノードの削除に伴うデータ再配置の処理の流れであるが、この処理をよりわかりやすく説明するため、例として、情報記憶ノード２が死んだときの処理（つまり情報記憶ノード２がＡＬＩＶＥ状態からＤＥＡＤ状態になり、そしてＳＵＢＳＴＩＴＩＵＴＥＤ状態になるまでの処理）を説明する。
【０１２８】
最初にステップＳ９０１において、管理ノード２０４のノード管理プログラム２４５が、ノード２が死んだことを検知する。ステップＳ９０２において、ノード管理プログラム２４５は、ノード管理テーブル２４８のノード２の生死のフィールドを「ＡＬＩＶＥ」から「ＤＥＡＤ」に変更する。
【０１２９】
ステップＳ９０３において、ノード管理テーブル２４８の生死のフィールドが「ＡＬＩＶＥ」の情報記憶ノードに、それ自身が持っているデータのうち「関係するデータ」を抽出して、それ自身の時計回りに隣の情報記憶ノードに複製する、ことを指示する。
【０１３０】
以下において、一例として、ノード４の処理を説明する。抽出する処理の詳細は、図１０のフローチャートを参照して説明した。ノード４のデータを格納しているデータ格納テーブル２１８は、図８に示した。
【０１３１】
具体的に説明する。以下において図１０を参照して説明する処理は、ノード４のデータ再配置処理プログラム２１７により実行される。図１０のフローチャートにおけるステップＳ１００１において、ノード４は、図８のデータ格納テーブル２１８から、「オリジナルノード」が死んだノード２で、「第一レプリカ格納ノード」が自分（情報記憶ノード４）であるエントリを抽出する。例えば、キーが「東京」のエントリ８０７が、抽出される。これは、図１におけるデータ「東京」１１２である。
【０１３２】
ステップＳ１００２において、ノード４は、データ格納テーブル２１８から、「第一レプリカ格納ノード」が死んだノード２であり、「第二レプリカ格納ノード」が自分（情報記憶ノード４）であるエントリを抽出する。例えば、キーが「ワシントン」のエントリ８０９が、抽出される。
【０１３３】
ステップＳ１００３において、ノード４は、データ格納テーブル２１８から「第二レプリカ格納ノード」が死んだノード２であり、「オリジナルノード」が自分（ノード４）であるエントリを抽出する。行８１０が示す省略されたエントリを除いて、明示されているエントリに、そのようなエントリは存在しない。
【０１３４】
ステップＳ１００４において、ノード４は、上記ステップＳ１１０１からステップＳ１１０３の３工程で抽出したエントリをまとめ、「関係するデータ」として主記憶装置の記憶領域に格納する。つまり、ノード４は、「東京」キーとするデータ及び「ワシントン」をキーとするデータを、「関係するデータ」として抽出する。このデータは、図１におけるデータ集合１２１Ｂに相当する。
【０１３５】
本例において、ノード４は、これらの抽出データを、時計回りに隣のノードに複製する。つまり、ノード４はノード５にそれらデータを複製する。これは、図１におけるデータ集合１２１Ｂを記憶領域１２４に複製することを意味する。ノード５は、記憶領域１２４をあらかじめ確保しておいてもよいし、複製作業を行う際に動的に確保してもよい。
【０１３６】
あらかじめ確保しておく場合は、ノード５は、それを、「ノード４の「オリジナルノードが、死んだノード２」のデータのための領域」として確保しておいてもよいし、「ノード４から複製される何らかの複製データのための領域」として確保しておいてもよい。若しくは、「どこかの情報記憶ノードから何らかの複製データを複製してくるための領域」として確保しておいてもよい。
【０１３７】
なお、図１は、このとき同様に複製されるデータの例として、ノード３からノード４に複製されるデータ、ノード５からノード６に複製されデータ、ノード６からノード７に複製されるデータ、そしてノード１からノード３に複製されるデータも示している。
【０１３８】
上述のように、本システムにおいて、一つの情報記憶ノードが保持する任意カテゴリのデータ集合と同一の、他のカテゴリのデータ集合は、他の１つの情報記憶ノードに集中しておらず、複数の情報記憶ノードに分散して格納されている。特に、ハッシュ関数のように偏りの小さい関数を使用することで、１つの情報記憶ノードに格納されているデータを、他の全ての情報記憶ノードに平均的に割り当てることができる。
【０１３９】
このシステムにおいて、ノード２は３ＴＢのデータを持っているとする。ノード２が死んだとき、上記例のノード４などノード２以外の情報記憶ノードが「ノード２に関係するデータ」として持っているデータ量は、３ＴＢの１０００分の１（１０００は全ノード数）である３ＧＢである。ステップＳ９０３において、各情報記憶ノードは、これを隣の情報記憶ノードに複製する。ネットワークが１Ｇｂｐｓであれば、複製における転送時間は約２４秒である。
【０１４０】
つまり、レプリケーション数を２から３に戻すまでにかかる時間は、従来例に比べて、約１／３３３となる。さらに、上記処理において、一部の情報記憶ノードのみに負荷が集中せず、負荷はシステム全体で一様に発生するため、クライアントからの要求に対して、従来例のような原因による応答のばらつきが出ることはない。また、複製処理による情報記憶ノードの故障発生の蓋然性を低減することができる。
【０１４１】
上記処理は、複数情報記憶ノードによるデータ複製の後に、ノードＮ＋１が、ノードＮの担当データを集める。すでにレプリケーション数が回復されているため、ノードＮ＋１は、そのデータ収集を、システムの状況に応じて行うことができる。
【０１４２】
このように、本実施形態は、システム内のデータを格納するノードの数が減少した場合に、レプリケーション数を回復するまでに必要な時間を従来よりも短縮することが可能である。または、レプリケーション数を回復するまでのシステムの負荷集中を抑えることができる。または、システムが定常状態に戻るまでの間、システムの応答時間のばらつきを従来よりも平準化させることが可能である。
【０１４３】
図１０を参照して説明したように、情報記憶ノードは、使用停止ノードに関係するデータを、予め設定されている規則に従って抽出する。この規則は、データの各カテゴリを他のカテゴリに関連付ける。情報記憶ノードは、使用停止ノードにおいて格納されている各データのカテゴリを特定し、そのカテゴリに関連付けられているカテゴリのデータを、他の情報記憶ノードに複製する。
【０１４４】
上記例においては、オリジナルデータのカテゴリは第一レプリカのカテゴリに関連付けられ、第一レプリカのカテゴリは第二レプリカのカテゴリに関連付けられ、第二レプリカのカテゴリはオリジナルデータのカテゴリに関連付けられている。この関連付けは一例であって他の対応関係でもよい。
【０１４５】
上記構成は、ノードＮが死んだことを検知して、それを使用不能ノードと判定して、その情報記憶ノードの使用を停止する。これと異なり、管理ノード２０４は、ノードＮのレスポンスタイムが閾値よりも長くなったことを検知してもよいし、ノードＮのＣＰＵ負荷が閾値よりも高くなったことを検知してもよい。若しくは、他の通常状態とは異なる状態を検知してもよい。
【０１４６】
上記構成は、ノードＮが死んだことを検知してノードＮを使用不能ノードと判定するが、ノードＮ以外の情報記憶ノードの状態から、ノードＮを使用不能ノードと判定してもよい。例えば、情報記憶システムは、ノードＮが特定のノードグループＧに属している場合に、そのノードグループＧが通常とは異なる状態になったことを検知して、ノードＮ又はノードグループＧに属する一つ以上の情報記憶ノードを使用不能ノードと判定し、複製処理を行ってもよい。情報記憶システムは、ノードＮが通常とは異なる状態になったことを検知して、ノードグループＧの一部又は全ての情報記憶ノードを使用不能ノードと判定し複製処理を行ってもよい。
【０１４７】
上記例において、ノードＮは不測の故障により死んだが、ノードＮが計画停止する場合も、上記データ複製処理を同様に適用することができる。この場合、ステップＳ９０１からステップＳ９０７までの間に、ノードＮが動作していてもよい。ノードＮの使用は、その後停止される。
【０１４８】
上記処理において、各情報記憶ノードは、論理的に隣の位置にある情報記憶ノードに対して、ノードＮに関係するデータを複製する。各情報記憶ノードがデータを複製する情報記憶ノードの相対論理位置は、他の位置であってもよい。例えば、一つおきや二つおきなどしてもよいし、論理円上の反対側の情報記憶ノードでもよい。何らかの関数ｆを用いてデータ複製先の情報記憶ノードを決定してもよい。
【０１４９】
複製した先のノードを後で知ることができるのであれば、情報記憶ノードは、乱数を使って複製する先の情報記憶ノードを決定する、各情報記憶ノードの負荷を考慮し負荷の小さい情報記憶ノードに複製するなどの決定方法を使用してもよい。この場合、複製元のノード名（またはノードＩＤ）から複製先のノード名（またはノードＩＤ）を知ることができるよう、テーブルを設ければよい。
【０１５０】
情報記憶ノードの使用停止に伴うデータの複製（複製データの抽出及び他の情報記憶ノードへの複製）は、情報記憶ノードが自律的に行うことが好ましい。これにより、迅速かつ効率的に処理を行うことができる。これと異なり、管理ノード２０４が、各情報記憶ノードに複製先の情報記憶ノードを指示してもよい。
【０１５１】
上記構成において、各情報記憶ノードは、規定の相対位置にある情報記憶ノードにノードＮに関係するデータを複製する。複製先の情報記憶ノードが、複製データと同一データを格納していることがある。この場合、同一データのレプリケーション数は２のままであり、３には戻らない。そのため図１１を用いて後述する方法と同様の方法を用いて新たな複製先ノードを決定する。これによりレプリケーション数３を確保する。
【０１５２】
複製先ノードが同一データを格納している可能性（発生頻度）は小さいため、同一データの有無にかかわらず規定の情報記憶ノードにデータを複製してもよい。これと異なり、情報記憶ノードは、規定相対位置の情報記憶ノードが同一データを格納している場合、それとは異なる情報記憶ノード、例えば、同一データを格納する情報記憶ノードの隣の情報記憶ノードにデータを複製してもよい。情報記憶ノードは、データ格納テーブル２１８を参照することで、複製対象のデータと同一データを格納する情報記憶ノードを特定することができる。
【０１５３】
上記構成において、ノードＮの時計回りに隣のノードＮ＋１がノードＮの担当範囲を、新たに担当する。これと異なり、例えば、（予備として取ってあった）ノードＸをノードＮの代わりに追加し、そのノードＸが、情報記憶ノードＮが元々担当していたデータを集めて、その後、ノードＸが、ノードＮが元々担当していた処理を行ってもよい。これにより、情報記憶システムを、ノードＮの使用停止前の状態に戻すことができる。既存の複数情報記憶ノード又は新たに追加された情報記憶ノードを含む複数情報記憶ノードが、データを集めてもよい。
【０１５４】
上記例において、ノードＮ＋１は、データを複製した情報記憶ノードから、複製したデータと同一データを取得する。ノードＮ＋１は、どの情報記憶ノードからノードＮの担当データを集めてもよい。例えば、ノードＮ＋１は、複製先の情報記憶ノードから、その記憶領域（例えば図１におけるノード５の記憶領域１２４）に格納されているデータを取得することができる。この他、情報記憶システム２０９は、複数情報記憶ノードにより使用停止ノードに関係するデータを複製した後（レプリケーション数を回復した後）、１つの情報記憶ノードに使用停止ノードの担当データを集めることなく処理を終了してもよい。
【０１５５】
〔データ書き込み〕
以下において、図１１及び図１２を参照して、情報記憶システム２０９にデータを書き込む処理を説明する。まず、図１１を参照して、管理ノード２０４のリードライト管理プログラム２４６が、キーの値からデータを格納する（書き込む）情報記憶ノードを決定する処理を説明する。
【０１５６】
図１１は、リードライト管理プログラム２４６が、キーの値から格納ノードを決定する処理のフローチャートを示す。ステップＳ１１０１において、リードライト管理プログラム２４６は、規定のハッシュ関数及びクライアントから受信したキーから、キーのハッシュ値を計算する。
【０１５７】
さらに、リードライト管理プログラム２４６は、そのハッシュ値を用いて、ノード管理テーブル２４８においてオリジナルノードを検索する。リードライト管理プログラム２４６用いるハッシュ関数として、例えば、ＭＤ５、ＳＨＡ−１、ＳＨＡ−２５６などのうち１つまたは複数の組み合わせ（の関数）を用いることができる。これらとは異なる関数を使用してもよい。
【０１５８】
ステップＳ１１０２において、リードライト管理プログラム２４６は、キーに「１」を結合し、その値をハッシュ関数に代入する演算式を使用して、ハッシュ値（演算値）を算出する。使用するハッシュ関数は、オリジナルノード決定の関数と同一である。リードライト管理プログラム２４６は、そのハッシュ値を用いて、ノード管理テーブル２４８において第一レプリカ格納ノードの候補を検索する。キーに「１」を結合する演算は、例えばキーが「東京」であれば、「東京１」という文字列を生成し、例えばキーが「ニューヨーク」であれば「ニューヨーク１」という文字列を生成する。
【０１５９】
ステップＳ１１０３において、リードライト管理プログラム２４６は、オリジナルノードと第一レプリカ格納ノードの候補が等しいかどうか調べる。もしオリジナルノードと第一レプリカ格納ノードの候補が等しければ（Ｓ１１０３：ＹＥＳ）、リードライト管理プログラム２４６は、ステップＳ１１０４へ進む。もしオリジナルノードと第一レプリカ格納ノードの候補が等しくなければ（Ｓ１１０３：ＮＯ）、リードライト管理プログラム２４６は、ステップＳ１１０５へ進む。
【０１６０】
ステップＳ１１０４において、リードライト管理プログラム２４６は、第一レプリカ格納ノードを、第一レプリカ格納ノードの候補の時計回りに隣のノードと決定する。ステップＳ１１０５において、リードライト管理プログラム２４６は、第一レプリカ格納ノードを第一レプリカ格納ノードの候補のノードと決定する。
【０１６１】
ステップＳ１１０６において、リードライト管理プログラム２４６は、キーに「２」を結合し、そのハッシュ値を計算する。ハッシュ関数は上記の関数と同じである。リードライト管理プログラム２４６は、そのハッシュ値を用いて、ノード管理テーブル２４８において第二レプリカ格納ノードの候補を検索する。
【０１６２】
ステップＳ１１０７において、リードライト管理プログラム２４６は、オリジナルノード又は第一レプリカ格納ノードが、第二レプリカ格納ノードの候補と等しいかどうか調べる。もしオリジナルノード又は第一レプリカ格納ノードが、第二レプリカ格納ノードの候補と等しければ（Ｓ１１０７：ＹＥＳ）、リードライト管理プログラム２４６は、ステップＳ１１０８へ進む。第二レプリカ格納ノードの候補が、オリジナルノード及び第一レプリカ格納ノードのいずれともが等しくなければ（Ｓ１１０７：ＮＯ）、リードライト管理プログラム２４６は、ステップＳ１１０９へ進む。
【０１６３】
ステップＳ１１０８において、リードライト管理プログラム２４６は、新しい第二レプリカ格納ノードの候補を、前の第二レプリカ格納ノードの候補の時計回りに隣のノードと決定する。ステップＳ１１０９において、リードライト管理プログラム２４６は、第二レプリカ格納ノードを、第二レプリカ格納ノードの候補のノードと決定する。
【０１６４】
以上の処理によって、キーの値から格納ノードを決定することができる。なお、上記例は、「オリジナルノード」「第一レプリカ格納ノード」「第二レプリカ格納ノード」を検索するために、「キー」「キーに１を結合した値」「キーに２を結合した値」を用いたが、他の文字列を結合してもよいし、キーの文字列を一定の法則により変化させてもよい。例えば、リードライト管理プログラム２４６は、文字列を回転させる、つまり「ＴＯＫＹＯ」を、「ＯＫＹＯＴ」「ＫＹＯＴＯ」と変化させることもできる。
【０１６５】
若しくは、キーを変化させるのではなく、リードライト管理プログラム２４６は、異なる候補ノードの決定のために、異なるハッシュ関数を使用してもよい。例えば、オリジナルノードを検索するためにＭＤ５（”ニューヨーク”）を計算し、第一レプリカ格納ノー
ドを検索するためにＳＨＡ−１（”ニューヨーク”）を計算し、第二レプリカ格納ノード
を検索するためにＳＨＡ−２５６（”ニューヨーク”）を計算することができる。若しく
は、これらを組み合わせた形態をとることもできる。
【０１６６】
好ましい構成において、システムは、同一ハッシュ関数に異なる回数繰り返し値を代入することで、同一データを格納する複数の情報記憶ノードを決定する。例えばオリジナルノードの決定に「ＳＨＡ１（ＫＥＹ）」を用い、第一のレプリカノードの決定に「ＳＨＡ１（ＳＨＡ１（ＫＥＹ））」を用い、第二のレプリカノードの決定に「ＳＨＡ１（ＳＨＡ１（ＳＨＡ１（ＫＥＹ）））」を用いるという構成である。これにより、レプリケーション数が多いシステムも容易かつ適切にデータを格納する複数の情報記憶ノードを決定することができる。又、システムのレプリケーション数の増加に対しても容易に対応することができる。
【０１６７】
次に、データの書き込みにおける、クライアント２０７の処理を、図１２を用いて説明する。他のクライアントの処理も同様である。図１２は、クライアント２０７がキーを用いてバリュー（及びキー）を書き込むためのフローチャートを示す。このフローチャートは、管理ノード２０４とクライアント２０７の工程を含む。
【０１６８】
ステップＳ１２０１において、リードライトクライアントプログラム２７７は、管理ノード２０４に「キー」を送信し、格納すべき３つの情報記憶ノードを教えてくれるよう要求する。ステップ１２０２において、管理ノード２０４は、「キー」から格納すべき３つの情報記憶ノードである「オリジナルノード」「第一レプリカ格納ノード」「第二レプリカ格納ノード」を決定する。
【０１６９】
ステップＳ１２０３において、管理ノード２０４は、ノード管理テーブル２４８を用いて、「オリジナルノード」「第一レプリカ格納ノード」「第二レプリカ格納ノード」が共に「ＡＬＩＶＥ」であるかどうか調べる。
【０１７０】
管理ノード２０４がノード管理テーブル２４８から「オリジナルノード」「第一レプリカ格納ノード」「第二レプリカ格納ノード」が共に「ＡＬＩＶＥ」であることを確認できれば（Ｓ１２０３：ＹＥＳ）、処理はステップＳ１２０４へ進む。もし管理ノード２０４がノード管理テーブル２４８から「オリジナルノード」「第一レプリカ格納ノード」「第二レプリカ格納ノード」のいずれかひとつでも「ＡＬＩＶＥ」であることを確認できなければ（Ｓ１２０３：ＮＯ）、処理はステップＳ１２０９へ進む。
【０１７１】
ステップＳ１２０４において、管理ノード２０４は、書き込むべきノードとして「オリジナルノード」「第一レプリカ格納ノード」「第二レプリカ格納ノード」の３つを、クライアント２０７に返答する。
【０１７２】
ステップＳ１２０５において、クライアント２０７のリードライトクライアントプログラム２７７は、書き込むべきノードとして教えられた３つのノードに「キー」「バリュー」「オリジナルノード名」「第一レプリカ格納ノード名」「第二レプリカ格納ノード名」を書き込むよう指示する。
【０１７３】
ステップＳ１２０６において、リードライトクライアントプログラム２７７は、管理ノード２０４が、３つの情報記憶ノードから正常に書き込みができたとの返事を受け取ったかどうか調べる。もし３つの情報記憶ノードから正常に書き込みができたとの返事を受け取った場合は（Ｓ１２０６：ＹＥＳ）、処理はステップＳ１２０７へ進む。もし３つの情報記憶ノードのいずれかひとつからでも正常に書き込みができたとの返事を受け取れなかった場合は（Ｓ１２０６：ＮＯ）、処理は、ステップＳ１２０８へ進む。
【０１７４】
ステップＳ１２０７において、リードライトクライアントプログラム２７７は、書込み成功と判定する。ステップＳ１２０８において、リードライトクライアントプログラム２７７は書込み失敗と判定する。ステップＳ１２０９において、リードライトクライアントプログラム２７７は、書込み失敗と判定する。書き込み失敗の判定に対応する処理は、本発明と関連性が低いため説明を省略する。
【０１７５】
以上が処理の流れであるが、この処理をよりわかりやすく説明するため、例として、クライアント２０７がデータ「東京」１１０を格納する処理を以下に記述する。最初に、ステップＳ１２０１において、クライアント２０７は、管理ノード２０４に「キー」を送信し、格納すべき３つの情報記憶ノードを教えてくれるよう要求する。
【０１７６】
次にステップＳ１２０２において、管理ノード２０４が「キー」である「東京」から格納すべきノードを検索する。これは図１１に示す処理である。管理ノード２０４は、キー「東京」をハッシュ関数に代入することで「オリジナルノード」を決定し、キー「東京１」をハッシュ関数に代入することで「第一レプリカ格納ノード」を決定し、キー「東京２」ハッシュ関数に代入することで「第二レプリカ格納ノード」を決定する。（ハッシュ値が衝突したときの処理は、図１１で示したとおりである。）
本例では、「東京」のハッシュ値として「３００」、「東京１」のハッシュ値として「１０００」、「東京２」のハッシュ値として「３０００」が得られたとする。次にステップ１２０３において、管理ノード２０４は、ノード管理テーブル２４８を用いてオリジナルノード、第一レプリカ格納ノード、第二レプリカ格納ノードが、共にＡＬＩＶＥ状態であるかどうか調べる。
【０１７７】
図６のノード管理テーブル２４８は、ノード２の担当範囲が２２７から５３５であることを示している。管理ノード２０４は、ハッシュ値が３００である「オリジナルノード」は、情報記憶ノード２であると決定する。その生死情報は「ＡＬＩＶＥ」である。同様に、ハッシュ値１０００の「第一レプリカ格納ノード」は情報記憶ノード４である。生死情報は「ＡＬＩＶＥ」である。同様に、ハッシュ値３０００の「第二レプリカ格納ノード」の生死情報は「ＡＬＩＶＥ」である。３つの情報記憶ノードが「ＡＬＩＶＥ」であるので、処理は、ステップＳ１２０４へ進む。
【０１７８】
次に、ステップＳ１２０４において、管理ノード２０４は、オリジナルノード、第一レプリカ格納ノード、第二レプリカ格納ノードとして、ノード２、情報記憶ノード４、情報記憶ノード７を、クライアント２０７に返答する。
【０１７９】
次に、ステップＳ１２０５において、クライアント２０７は、データを書き込むべき情報記憶ノードとして教えられた３つの情報記憶ノード（情報記憶ノード２、情報記憶ノード４、情報記憶ノード７）に、「キー」として「東京」を、「バリュー」として「晴れ」を、「オリジナルノード名」として「ノード２」を、「第一レプリカ格納ノード名」として「ノード４」を、「第二レプリカ格納ノード名」として「ノード７」を、書き込むよう指示する。
【０１８０】
次にステップＳ１２０６において、管理ノード２０４は、３つの情報記憶ノード（ノード２、ノード４、ノード７）から正常に書き込みができたとの返事を受け取る。管理ノード２０４が３つの情報記憶ノードから正常に書き込みができたとの返事を受け取ると、処理はステップＳ１２０７へ進む。最後に、ステップＳ１２０７において、クライアント２０７は、書込み成功と判定する。以上の処理により、クライアント２０７は、データ「東京」１１０を情報記憶システム２０９に書き込むことができる。
【０１８１】
上記方法により選択したデータ書き込む先の情報記憶ノードがＤＥＡＤ状態又はＳＵＢＳＴＩＴＵＴＥＤ状態にあるとき、書き込み処理は失敗に終わる。これと異なり、情報記憶システム２０９は、選択したデータ書き込む先の情報記憶ノードがＳＵＢＳＴＩＴＵＴＥＤ状態である場合に、特定の情報記憶ノードにデータを書き込んでもよい。
【０１８２】
例えば、管理ノード２０４は、ＡＬＩＶＥである２つの情報記憶ノードの識別子をクライアント２０７に返す。クライアント２０７は、２つの情報記憶ノードにデータを書き込む。図９及び図１０を参照して説明した処理のように、ＳＵＢＳＴＩＴＵＴＥＤ状態の情報記憶ノードに格納されるべきデータのカテゴリ（例えば第一レプリカ）と予め関連づけられているカテゴリ（例えば第二レプリカ）のデータを格納する情報記憶ノードは、そのデータを隣の論理位置の情報記憶ノードに複製する。
【０１８３】
〔データ読み出し〕
以下において、図１３から図１５を参照して、クライアント２０７、２０８が、情報記憶システム２０９から情報を読み出す処理の説明を行う。以下においてはクライアント２０７の処理例を説明する。図１３は、クライアント２０７が情報記憶システム２０９から情報を読み出す処理例のフローチャートを示す。ステップＳ１３０１において、クライアント２０７のリードライトクライアントプログラム２７７が、「キー」を管理ノード２０４に伝え、データを読み出すべきノードを教えるよう要求する。
【０１８４】
ステップＳ１３０２において、管理ノード２０４（リードライト管理プログラム２４６）は、図１４に示す処理（後述する）により、ＡＬＩＶＥ状態の情報記憶ノードから、データを読み出すべきノードを検索する。ステップＳ１３０３において、リードライト管理プログラム２４６は、データを読み出すべき情報記憶ノードが見つかったかどうか調べる。もしデータを読み出すべき情報記憶ノードが見つかっていない場合（Ｓ１３０３：ＮＯ）、処理は、ステップＳ１３０４へ進む。もしもデータを読み出すべきノードが見つかった場合は（Ｓ１３０３：ＹＥＳ）、処理はステップＳ１３０５へ進む。
【０１８５】
ステップＳ１３０４において、リードライト管理プログラム２４６は、図１５に示す処理（後述する）により、ＳＵＢＳＴＩＴＵＴＥＤ状態の情報記憶ノードのバックアップ先の情報記憶ノードから、読み出すべきノードを検索する。ステップＳ１３０５において、管理ノード２０４は、読み出すべき情報記憶ノードが見つかったかどうか調べる。もし読み出すべきノードが見つかっていない場合は（Ｓ１３０５：ＮＯ）、処理はステップＳ１３０６へ進む。もし読み出すべきノードが見つかった場合は（Ｓ１３０５：ＹＥＳ）、処理はステップＳ１３０８へ進む。
【０１８６】
ステップＳ１３０６において、リードライト管理プログラム２４６は、クライアント２０７に、データを読み出すべき情報記憶ノードが見つからなかった旨を返答する。ステップＳ１３０７において、クライアント２０７のリードライトクライアントプログラム２７７は、読出し処理を失敗したと判定する。
【０１８７】
ステップＳ１３０８において、リードライト管理プログラム２４６は、クライアント２０７に、データを読み出すべき情報記憶ノードを返答する。ステップＳ１３０９において、クライアント２０７のリードライトクライアントプログラム２７７は、読み出すべきノードからキーを用いてバリューを読み出す。以上の処理によりクライアント２０７が情報記憶システム２０９から情報を読み出すことができる。
【０１８８】
次に図１４を参照して、キーを用いてＡＬＩＶＥ状態の情報記憶ノードからデータを読み出すべき情報記憶ノードを見つける処理の説明を行う。図１４は、管理ノード２０４が、キーを用いてＡＬＩＶＥ状態のノードから読み出すべきノードを見つける処理のフローチャートを示す。
【０１８９】
ステップＳ１４０１において、管理ノード２０４のリードライト管理プログラム２４６は、キーから、オリジナルノード、第一レプリカ格納ノード、第二レプリカ格納ノードを決定する。この処理の詳細は図１１を参照して説明したとおりである。
【０１９０】
ステップＳ１４０２において、リードライト管理プログラム２４６は、オリジナルノードが「ＡＬＩＶＥ」でないかどうか調べる。もしオリジナルノードが「ＡＬＩＶＥ」でない場合（Ｓ１４０２：ＮＯ）、処理はステップＳ１４０３へ進む。もしオリジナルノードが「ＡＬＩＶＥ」である場合は（Ｓ１４０２：ＹＥＳ）、処理はステップＳ１４０８へ進む。
【０１９１】
ステップＳ１４０３において、リードライト管理プログラム２４６は、第一レプリカ格納ノードが「ＡＬＩＶＥ」でないかどうか調べる。もし第一レプリカ格納ノードが「ＡＬＩＶＥ」でない場合は（Ｓ１４０３：ＮＯ）、ステップＳ１４０４へ進む。もし第一レプリカ格納ノードが「ＡＬＩＶＥ」である場合は（Ｓ１４０３：ＹＥＳ）、処理はステップＳ１４０７へ進む。
【０１９２】
ステップＳ１４０４において、リードライト管理プログラム２４６は、第二レプリカ格納ノードが「ＡＬＩＶＥ」でないかどうか調べる。もし第二レプリカ格納ノードが「ＡＬＩＶＥ」でない場合は（Ｓ１４０４：ＮＯ）、処理はステップＳ１４０５へ進む。もし第二レプリカ格納ノードが「ＡＬＩＶＥ」である場合は（Ｓ１４０４：ＹＥＳ）、処理はステップＳ１４０６へ進む。
【０１９３】
ステップＳ１４０５において、リードライト管理プログラム２４６は、データを読み出すべき情報記憶ノードは見つからないと判定する。ステップＳ１４０６において、リードライト管理プログラム２４６は、第二レプリカ格納ノードを、データを読み出すべき情報記憶ノードと判定する。
【０１９４】
ステップＳ１４０７において、リードライト管理プログラム２４６は、第一レプリカ格納ノードを、データを読み出すべき情報記憶ノードと判定する。ステップＳ１４０８において、リードライト管理プログラム２４６は、オリジナルノードを、データを読み出すべき情報記憶ノードと判定する。
【０１９５】
ステップＳ１４０９において、リードライト管理プログラム２４６は、データを読み出すべき情報記憶ノードのノード名を、返り値として返す（見つからなかったときは「見つからない」と返す）。以上の処理によりキーを用いてＡＬＩＶＥ状態のノードから読み出すべきノードを見つけることができる。
【０１９６】
次に図１５を参照して、管理ノード２０４がキーを用いてＳＵＢＳＴＩＴＵＴＥＤ状態の情報記憶ノードから、データを読み出すべきノードを見つける処理を説明する。図１５は、キーを用いてＳＵＢＳＴＩＴＵＴＥＤ状態の情報記憶ノードのバックアップ先の情報記憶ノードから、データを読み出すべき情報記憶ノードを見つけるための処理例を示すフローチャートである。
【０１９７】
ステップＳ１５０１において、リードライト管理プログラム２４６は、キーから、オリジナルノード、第一レプリカ格納ノード、第二レプリカ格納ノード」を決定する。この処理の詳細は、図１１に示したとおりである。
【０１９８】
ステップＳ１５０２において、リードライト管理プログラム２４６は、オリジナルノードが「ＳＵＢＳＴＩＴＵＴＥＤ」でないかどうか調べる。もしオリジナルノードが「ＳＵＢＳＴＩＴＵＴＥＤ」でない場合は（Ｓ１５０２：ＮＯ）、処理はステップＳ１５０３へ進む。もしオリジナルノードが「ＳＵＢＳＴＩＴＵＴＥＤ」である場合は（Ｓ１５０２：ＹＥＳ）、処理はステップＳ１５０８へ進む。
【０１９９】
ステップＳ１５０３において、リードライト管理プログラム２４６は、第一レプリカ格納ノードが「ＳＵＢＳＴＩＴＵＴＥＤ」でないかどうか調べる。もし第一レプリカ格納ノードが「ＳＵＢＳＴＩＴＵＴＥＤ」でない場合は（Ｓ１５０３：ＮＯ）、処理はステップＳ１５０４へ進む。もし第一レプリカ格納ノードが「ＳＵＢＳＴＩＴＵＴＥＤ」である場合は（Ｓ１５０３：ＹＥＳ）、処理はステップ１５０７へ進む。
【０２００】
ステップＳ１５０４において、リードライト管理プログラム２４６は、第二レプリカ格納ノードが「ＳＵＢＳＴＩＴＵＴＥＤ」でないかどうか調べる。もし第二レプリカ格納ノードが「ＳＵＢＳＴＩＴＵＴＥＤ」でない場合は（Ｓ１５０４：ＮＯ）、処理はステップＳ１５０５へ進む。もし第二レプリカ格納ノードが「ＳＵＢＳＴＩＴＵＴＥＤ」である場合は（Ｓ１５０４：ＹＥＳ）、処理はステップＳ１５０６へ進む。
【０２０１】
ステップＳ１５０５において、リードライト管理プログラム２４６は、データを読み出すべき情報記憶ノードは見つからないと判定する。ステップＳ１５０６において、リードライト管理プログラム２４６は、オリジナルノードの隣のノードを、データを読み出すべき情報記憶ノードと判定する。
【０２０２】
ステップＳ１５０７において、リードライト管理プログラム２４６は、第二レプリカ格納ノードの隣のノードを、データを読み出すべき情報記憶ノードと判定する。ステップＳ１５０８において、リードライト管理プログラム２４６は、第一レプリカ格納ノードの隣のノードを、データを読み出すべき情報記憶ノードと判定する。
【０２０３】
ステップＳ１５０９において、リードライト管理プログラム２４６は、データを読み出すべき情報記憶ノードのノード名を、返り値として返す（見つからなかったときは「見つからない」と返す）。以上の処理により、キーを用いてＳＵＢＳＴＩＴＵＴＥＤ状態のノードから読み出すべきノードを見つけることができる。
【０２０４】
以上が処理の流れであるが、この処理をよりわかりやすく説明するため、例として、クライアント２０７がデータ「東京」１１０を読み出す処理を以下に説明する。最初にステップＳ１３０１において、クライアント２０７が「キー」である「東京」を管理ノード２０４に送信し、データを読み出すべき情報記憶ノードを教えるよう要求する。
【０２０５】
次にステップＳ１３０２において、管理ノード２０４は、図１４に示す処理によりＡＬＩＶＥ状態の情報記憶ノードから、データを読み出すべき情報記憶ノードを検索する。ステップＳ１４０１において、管理ノード２０４は、「東京」「東京１」「東京２」からハッシュ値を計算し、ノード管理テーブル２４８から「ノード２」「ノード４」「ノード７」を取得する。
【０２０６】
ステップＳ１４０２において、管理ノード２０４は、ノード２の生死状態をノード管理テーブル２４８で検索する。ノード２の状態は「ＡＬＩＶＥ」であることから、ステップＳ１４０８において、管理ノード２０４は、データを読み出すべき情報記憶ノードを情報記憶ノード２と判定する。
【０２０７】
ステップＳ１３０３において、管理ノード２０４は、データを読み出すべき情報記憶ノードが見つかったかどうか調べ、見つかったので処理はステップＳ１３０５へ進む。ステップＳ１３０５において、管理ノード２０４は、データを読み出すべき情報記憶ノードが見つかったかどうか調べ、見つかったので処理はステップＳ１３０８へ進む。
【０２０８】
ステップＳ１３０８において、管理ノード２０４は、クライアント２０７に、データを読み出すべき情報記憶ノードとして情報記憶ノード２を返答する。次にステップＳ１３０９において、クライアント２０７は、データを読み出すべきノードである情報記憶ノード２から、キー「東京」を用いてバリューを読み出す。以上の処理により、クライアント２０７が情報記憶システム２０９から情報を読み出すことができる。
【０２０９】
〔情報記憶ノード追加〕
次に、図１６及び図１７を用いて、ノードＮとノードＮ＋１の間に、ノードＸを挿入する処理を説明する。図１６は、ノードＮとノードＮ＋１の間に、ノードＸを挿入する処理例を示すフローチャートである。
【０２１０】
ステップＳ１６０１において、管理ノード２０４のノード管理プログラム２４５は、がノードＸの「担当ハッシュ値範囲のエンド値」を決定する。これはノードＮの担当ハッシュ値範囲のエンド値からノードＮ＋１の担当ハッシュ値範囲のエンド値までの間の値である。
【０２１１】
ステップＳ１６０２において、ノード管理プログラム２４５は、ノード管理テーブル２４８の生死状態のフィールドが「ＡＬＩＶＥ」の情報記憶ノードに、それ自身が持っているデータのうちノードＸが関係するデータを抽出して、ノードＸに複製する（送信する）ように指示する。この指示には、ノードＸの担当ハッシュ値範囲が付加される。
【０２１２】
ステップＳ１６０３において、指示を受けた各情報記憶ノードは、それ自身が持っているデータのうち、ノードＸが関係するデータを抽出して、ノードＸに複製する。この処理を、図１７のフローチャートを参照して説明する。
【０２１３】
ステップＳ１７０１において、各情報記憶ノードのデータ再配置処理プログラム２１７は、データ格納テーブル２１８から、オリジナルノードがノードＮ＋１であって、第一レプリカ格納ノードが自分であるエントリを抽出する。さらに、データ再配置処理プログラム２１７は、それぞれの抽出したデータのキーに対してハッシュ値を計算し、ノードＸの担当ハッシュ値範囲であるデータを抽出する。本例において、データ再配置処理プログラム２１７は、オリジナルノード、第一レプリカ格納ノード及び第二レプリカ格納ノードを決定する演算方法を知っている（プログラム内に規定されている）。
【０２１４】
ステップＳ１７０２において、各情報記憶ノードのデータ再配置処理プログラム２１７は、データ格納テーブル２１８から、第一レプリカ格納ノードがノードＮ＋１であって、第二レプリカ格納ノードが自分であるエントリを抽出する。さらに、データ再配置処理プログラム２１７は、それぞれの抽出したデータのキーに対してハッシュ値を計算し、ノードＸの担当ハッシュ値範囲であるデータを抽出する。
【０２１５】
ステップＳ１７０３において、データ再配置処理プログラム２１７は、データ格納テーブル２１８から、第二レプリカ格納ノードがノードＮ＋１であって、オリジナルノードがそれ自身であるエントリを抽出する。さらに、データ再配置処理プログラム２１７は、それぞれの抽出したデータのキーに対してハッシュ値を計算し、ノードＸの担当ハッシュ値範囲であるデータを抽出する。
【０２１６】
ステップＳ１７０４において、データ再配置処理プログラム２１７は、上記３工程で抽出したエントリをまとめて、「関係するデータ」として主記憶デバイスの記憶領域に格納する。データ再配置処理プログラム２１７は、ステップＳ１７０１からステップＳ１７０４で抽出したデータを、ノードＸに複製する。データ再配置処理プログラム２１７は、ノードＸの挿入に共に、データ格納テーブル２１８を更新する。
【０２１７】
図１６に戻って、ステップＳ１６０４において、管理ノード２０４のノード管理プログラム２４５は、指示をした全ての情報記憶ノードによるノードＸへの複製作業が終わるのを待つ。ステップＳ１６０５において、ノード管理プログラム２４５は、ノード管理テーブル２４８のノードＮとノードＮ＋１の間に、ノードＸのエントリを追加し、担当ハッシュ値範囲のエンド値を記入し、生死のフィールドに「ＡＬＩＶＥ」を記入する。
【０２１８】
ステップＳ１６０６において、ノード管理プログラム２４５は、ノードＮ＋１に対して、新しくノードＸが担当範囲になったデータを削除するように指示する。以上の処理によりノードＮとノードＮ＋１の間に、ノードＸを挿入する処理を遂行することができる。本処理により、ノードＮ＋１のみからデータをノードＸに複製する処理に対して、複製処理を複数の情報記憶ノードに分散して行うことができ、１台当たりの情報記憶ノードの付加を低減することができる。
【０２１９】
＜第２の実施の形態＞
本実施形態は、第１の実施形態におけるレプリケーション数を回復している処理の途中において、さらに障害が発生したときに行うことが好ましい処理を説明する。図１８は、図９に示すフローチャートのステップＳ９０４の実行中にノードＭが死んだときに実行される処理例を示すフローチャートである。
【０２２０】
ステップＳ１８０１において、管理ノード２０４のノード管理プログラム２４５は、ステップＳ９０４の実行中にノードＭが死んだことを検知する。ステップＳ１８０２において、ノード管理プログラム２４５は、ノード管理テーブル２４８のノードＭのエントリの生死情報フィールドを、「ＡＬＩＶＥ」から「ＤＥＡＤ」に変更する。
【０２２１】
ステップＳ１８０３において、管理ノード２０４のデータ再配置管理プログラム２４７は、ノード管理テーブル２４８にける生死情報フィールドが「ＡＬＩＶＥ」の情報記憶ノードに、自分が持っているデータのうちノードＮに関係しかつノードＭにも関係するデータを抽出して、自分の隣の情報記憶ノードに複製するように指示する。この指示は、ステップＳ９０３の複製指示よりも優先するように指示する。
【０２２２】
ノードＮ及びノードＭの双方の担当データ（例えば、ノードＮがオリジナルノードであり、ノードＭが第一レプリカ格納ノードであるデータ）のレプリケーション数は、ノードＭが死んだときに、２から１に減少する。一方、ノードＮ又はノードＭの一方のみに関係する（一方のみが担当している）データ、つまり、一方のみがオリジナルデータ、第一レプリカ又は第二レプリカの１つを格納しているデータのレプリケーション数は２である。
【０２２３】
このように、ノードＮ及びノードＭの双方が担当しているデータのレプリケーション数は、他のデータのレプリケーション数よりも小さいため、他のデータよりも優先してそのレプリケーション数を増加させることが重要である。そこで、本実施形態は、好ましい方法として、自身が持っているデータのうちノードＮに関係しかつノードＭにも関係するデータの抽出及び複製を、ステップＳ９０３の複製指示よりも優先する。
【０２２４】
各情報記憶ノードは、データ格納テーブル２１８において、ノードＮ及びノードＭの双方を含むエントリを検索し、そのエントリを自分の隣の情報記憶ノードに複製する。ノードＮ及びノードＭの双方を含むエントリは、ノードＮ又はノードＭのいずれかについて、図１０を参照して説明した「関係するデータ」の規則を満たす。ステップＳ１８０４において、管理ノード２０４は、全部の情報記憶ノードによる、ノードＭ及びノードＮの双方の関係データの複製作業が終わるのを待つ。ここまでのステップにより、レプリケーション数１であったデータのレプリケーション数が１だけ増加して２になる。
【０２２５】
ステップＳ１８０５において、データ再配置管理プログラム２４７は、ノード管理テーブル２４８における生死情報フィールドが「ＡＬＩＶＥ」の情報記憶ノードに、自分が持っているデータのうちノードＭに関係するデータを抽出して、自分の隣の情報記憶ノードに複製するように指示する。この指示は、ノードＭに関係するデータのうち未複製のデータ、つまり、ノードＮが担当していないデータのみを対象とする。
【０２２６】
ノードＭに関係するデータの特定は、図１０に示す規則に従う。具体的には、図１０を参照して説明したように、ノードＭが格納するオリジナルデータ、第一レプリカ及び第二レプリカの、それぞれの、第一レプリカ、第二レプリカ及びオリジナルデータが、ノードＭに関係しているデータである。これらのデータのエントリにおいて、ノードＮが含まれていないエントリが、未複製のエントリである。
【０２２７】
データ再配置管理プログラム２４７は、ノードＭのみが関係するデータとノードＮのみが関係するデータのいずれを優先する形態としてもよい。つまり、情報記憶ノードは、ノードＭのみが関係するデータと、ノードＮのみが関係するデータの、いずれを先に複製する形態としてもよい。
【０２２８】
各情報記憶ノードは、データ格納テーブル２１８において、ノードＭを含みノードＮを含まないエントリにおいて、図１０を参照して説明した規則を満たすエントリを、隣の情報記憶ノードに複製する。ステップＳ１８０６において、データ再配置管理プログラム２４７は、全部の情報記憶ノードによるステップＳ１８０５の終了を待つ。
【０２２９】
ステップ１８０７において、データ再配置管理プログラム２４７は、ノード管理テーブル２４８におけるノードＭのエントリの生死情報フィールドを、「ＤＥＡＤ」から「ＳＵＢＳＴＩＴＵＴＥＤ」に変更する。ここまでのステップにより、ノードＭが担当しており、ノードＮが担当してないデータのレプリケーション数を規定数の３に戻すことができる。
【０２３０】
図９のフローチャートにおけるステップＳ１８０６及びステップＳ１８０７の後、ステップＳ１８０８において、データ再配置管理プログラム２４７は、ノードＭの隣のノードＭ＋１に、ノードＭが元々担当していたデータを、ノード管理テーブル２４８の生死情報のフィールドが「ＡＬＩＶＥ」の情報記憶ノードから集めてくるよう指示する。
【０２３１】
具体的には、データ再配置管理プログラム２４７は、ノードＭ＋１に、「ＡＬＩＶＥ」の情報記憶ノードを特定する情報と共に、データ収集の指示を送信する。この指示は、ノードＮの担当データの収集指示の後でも前でもよい。ノードＭ＋１は、ＡＬＩＶＥ状態の情報記憶ノードに対して、複製されたノードＭの担当データ（ノードＭの死亡に応答して複製されたデータ）の送信（複製）を要求する。
【０２３２】
ステップＳ１８０９において、ノードＭの隣のノードＭ＋１が、ノードＭが元々担当していたすべてのデータを集めたら、データ再配置管理プログラム２４７は、ノード管理テーブル２４８のノードＭのエントリを削除する。データ再配置管理プログラム２４７は、ノードＭのエントリの生死情報フィールドの値を、「ＳＵＢＳＴＩＴＵＴＥＤ」から「ＤＥＬＥＴＥＤ」に変更してもよい。
【０２３３】
上記処理は、ノードＮとノードＭの双方に格納されるデータと同一のデータを、１つの情報記憶ノードのみに複製するが、これを２つの異なる情報記憶ノードに複製してもよい。これにより、ノードＮとノードＭの双方に格納されるデータのレプリケーション数を、３に戻すことができる。
【０２３４】
以上が処理の流れであるが、この処理をよりわかりやすく説明するため、例として、死んだノード２のためのステップＳ９０４の実行中にノード５が死んだときの処理を以下に記述する。
【０２３５】
ステップＳ１８０１において、ステップＳ９０４の実行中に、管理ノード２０４は情報記憶ノード５が死んだことを検知する。次にステップＳ１８０２において、管理ノード２０４は、ノード管理テーブル２４８のノード５の生死のフィールドを「ＤＥＡＤ」に変更する。
【０２３６】
次にステップＳ１８０３において、管理ノード２０４は、ノード管理テーブル２４８の生死情報フィールドが「ＡＬＩＶＥ」の情報記憶ノードに、自分が持っているデータのうち、ノード２に関係しかつノード５にも関係するデータを抽出して、自分の隣の情報記憶ノードに複製するように指示する。この指示はステップＳ９０３の指示よりも優先するように指示する。
【０２３７】
指示を受けた各情報記憶ノードは、データ格納テーブル２１８において、オリジナルノード、第一レプリカ格納ノード及び第二レプリカ格納ノードのうち、２つのフィールドがノード２及びノード５を格納しているエントリを抽出し、そのエントリを隣の情報記憶ノードに送信する。ステップＳ１８０４において、管理ノード２０４は、全部の情報記憶ノードによる、ノード２及びノード５の双方の担当データの複製作業が終わるのを待つ。
【０２３８】
ステップＳ１８０５において、管理ノード２０４は、ノード管理テーブル２４８における生死情報フィールドが「ＡＬＩＶＥ」の情報記憶ノードに、自分が持っているデータのうちノード５に関係するデータを抽出して、自分の隣の情報記憶ノードに複製するように指示する。この指示は、ノード５に関係するデータのうち未複製のデータ、つまり、ノード２が担当していないデータのみを対象とする。
【０２３９】
各情報記憶ノードは、データ格納テーブル２１８において、ノード２を含まないエントリにおいてノード５と関係するエントリを抽出し、そのエントリを隣の情報記憶ノードに送信する。ステップＳ１８０６において、管理ノード２０４は、全部の情報記憶ノードによる、ノードＭに関係する未複製データの複製処理の終了を待つ。
【０２４０】
ステップ１８０７において、管理ノード２０４は、ノード管理テーブル２４８におけるノード５のエントリの生死情報フィールドを、「ＤＥＡＤ」から「ＳＵＢＳＴＩＴＵＴＥＤ」に変更する。
【０２４１】
図９のフローチャートにおけるステップ９０４及びステップ９０５（ノード２の担当データの複製及びノード管理テーブルの更新）の後、ステップＳ１８０８において、管理ノード２０４は、ノード５の隣のノード６に、ノード５が元々担当していたデータを、ノード管理テーブル２４８の生死情報のフィールドが「ＡＬＩＶＥ」の情報記憶ノードから集めるよう指示する。具体的には、管理ノード２０４は、ノード６に、「ＡＬＩＶＥ」の情報記憶ノードを特定する情報と共に、データ収集の指示を送信する。
【０２４２】
ステップＳ１８０９において、ノード５の隣のノード６が、ノード５が元々担当していたすべてのデータを集めたら、管理ノード２０４は、ノード管理テーブル２４８のノード５のエントリを削除する。
【０２４３】
ステップＳ１８０１からステップＳ１８０４までにかかる時間を計算する。従来例の計算例と同様に、情報記憶ノードの数を１０００とし、各情報記憶ノードは１Ｇｂｐｓのネットワークに接続されており、各情報記憶ノードは、１ＴＢ（テラバイト）のオリジナルデータを保持している（つまり各ノードの担当範囲には１ＴＢのデータが存在している）とする。
【０２４４】
ステップＳ１８０３で各ノードに指示される「複製すべきデータ」は、３ＴＢの１０００分の１のさらに１０００分の１である。つまり約３ＭＢである。これを複製するためにかかる時間は、約０．０２４秒である。従来例が必要とする２時間１３分と比較すると、約３０万分の１の時間である。つまり、非常に短い時間で、「レプリケーション数１」というデータロスの危険性が高い状況を脱出することができる。
【０２４５】
以上、本発明の実施形態を説明したが、本発明が上記の実施形態に限定されるものではない。当業者であれば、上記の実施形態の各要素を、本発明の範囲において容易に変更、追加、変換することが可能である。
【０２４６】
本発明はキーバリューシステムに特に好適であるが、これとは異なる情報記憶システムに適用することができる。例えば、３以上のデータ項目からなるグループによりデータを管理するシステムや単一データ項目によりデータを管理するシステムにも適用できる。データ格納先の情報記憶ノードを決定するための演算は、ハッシュ関数を使用することが好ましいが、これとは異なる関数を使用してもよい。
【０２４７】
上記の各構成、機能、処理部、処理手段等は、それらの一部又は全部を、例えば集積回路で設計する等によりハードウェアで実現してもよい。各機能を実現するプログラム、テーブル、ファイル等の情報は、メモリや、ハードディスク、ＳＳＤ（ＳｏｌｉｄＳｔａｔｅＤｒｉｖｅ）等の記憶デバイス、または、ＩＣカード、ＳＤカード、ＤＶＤ等の永続的データ記憶媒体に格納することができる。
【０２４８】
ある実施形態の構成の一部を他の実施形態の構成に置き換えることが可能であり、ある実施形態の構成に他の実施形態の構成を加えることも可能である。各実施形態の構成の一部について、他の構成の追加・削除・置換をすることが可能である。
【符号の説明】
【０２４９】
１０１〜１０７  情報記憶ノード、１１０  データ「東京」、１１１  「東京」のオリジナルデータ、１１２  「東京」の第一レプリカ、１１３  「東京」の第二レプリカ、１２１Ａ〜１２２Ｅ  ノード２に関係する複製すべきデータ群、１２４  記憶領域、２０１〜２０３  情報記憶ノード、２０４  管理ノード、２０５  通信制御装置、２０６  外部ネットワーク、２０７、２０８  クライアント、２０９  情報記憶システム、２１１  ネットワークインタフェース、２１２  プロセッサ、２１３  主記憶デバイス、２１４  二次記憶デバイス、２１５  バス、２１６  リードライト処理プログラム、２１７  データ再配置処理プログラム、２１８  データ格納テーブル、２４１  ネットワークインタフェース、２４２  プロセッサ、２４３  主記憶デバイス、２４４  二次記憶デバイス、２４５  ノード管理プログラム、２４６  リードライト管理プログラム、２４７  データ再配置管理プログラム、２４８  ノード管理テーブル、２４９  バス、２７１  入力デバイス、２７２  プロセッサ、２７３  ネットワークインタフェース、２７４  ディスプレイ、２７５  主記憶デバイス、２７６  二次記憶デバイス、２７７  リードライトクライアントプログラム、２７８  バス
【図１】
2012221419.tif 000003
【図２】
2012221419.tif 000004
【図３】
2012221419.tif 000005
【図４】
2012221419.tif 000006
【図５】
2012221419.tif 000007
【図６】
2012221419.tif 000008
【図７】
2012221419.tif 000009
【図８】
2012221419.tif 000010
【図９】
2012221419.tif 000011
【図１０】
2012221419.tif 000012
【図１１】
2012221419.tif 000013
【図１２】
2012221419.tif 000014
【図１３】
2012221419.tif 000015
【図１４】
2012221419.tif 000016
【図１５】
2012221419.tif 000017
【図１６】
2012221419.tif 000018
【図１７】
2012221419.tif 000019
【図１８】
2012221419.tif 000020