(57)【特許請求の範囲】
【請求項１】
複数のストレージノードと、
システムの動作の状態情報を指定する動作状態指定手段と、
を備え、
前記ストレージノードは、
前記システムの動作状態に関してグループ化されてなる前記複数のストレージノードの前記ストレージノード毎の所属するグループと、前記グループ毎に定められた複製数と、前記動作状態指定手段で指定されたシステムの動作の状態情報を記憶する記憶部と、
データ書き込み命令に応答して、前記複数のストレージノードが論理的に配置されたハッシュリング上で隣接ストレージノードを取得し、前記記憶部を参照して、前記隣接ストレージノードが所属するグループを識別し、前記グループで必要な複製数に達していない場合には、前記隣接ストレージノードを前記グループの複製先ノードリストに登録し、
全てのグループに対して必要な複製数の複製先が得られるまで、前記ハッシュリング上で次の隣接ストレージノードを取得して前記次の隣接ストレージノードが所属するグループの複製先ノードリストに登録する処理を順次行うことで、前記複製先ノードリストを作成し、前記複製先ノードリスト上のストレージノードに対してデータの複製を行う手段と、
を備えた分散ストレージシステム。
【請求項２】
前記ストレージノードが、
（ａ）前記複数のストレージノードが論理的に配置された前記ハッシュリング上で、現在のストレージノードに隣接するストレージノードを取得し、
（ｂ）前記記憶部を参照して、前記取得した隣接ストレージノードの所属グループを識別し、前記所属グループに指定されているデータの複製数と、複製先ノードリストに含まれているノードの数とを比較し、
（ｃ）前記所属するグループの複製先のストレージノードの数が指定複製数に達している場合には、前記隣接ストレージノードを前記現在のストレージノードとして、（ａ）の前記ハッシュリング上の隣接ストレージノードの取得処理に戻り、
（ｄ）前記所属するグループの複製先のストレージノードの数が指定複製数に達していない場合には、（ａ）で取得した隣接ストレージノードを複製先ノードリストに追加し、
（ｅ）前記ハッシュリング上のストレージノードが所属するグループの全てに対して必要な複製数に達しているか判定し、
（ｆ）前記判定の結果、前記ハッシュリング上のストレージノードが属する全ての所属グループに対して必要な複製数に達していない場合、前記隣接ストレージノードを前記現在のストレージノードとして、（ａ）の前記ハッシュリング上の隣接ストレージノードの取得処理に戻り、
（ｇ）前記判定の結果、前記ハッシュリング上のストレージノードが属する全ての所属グループに対して必要な複製数に達している場合、複製先ノードリストを複製命令発行手段に送る、
前記（ａ）乃至（ｇ）を実行するアクセスノード算出手段と、
前記複製先ノードリストに含まれるストレージノードに対して複製命令を発行する前記複製命令発行手段と、
を備えた、請求項１記載の分散ストレージシステム。
【請求項３】
複数のストレージノードを備えたストレージシステムの分散ストレージ方法であって、
前記ストレージノードは、
システムの動作状態に関してグループ化されてなる前記複数のストレージノードの前記ストレージノード毎の所属するグループと、前記グループ毎に定められた複製数と、指定されたシステムの動作の状態情報を記憶部で記憶管理し、
データ書き込み命令に応答して、前記複数のストレージノードが論理的に配置されたハッシュリング上で隣接ストレージノードを取得し、前記記憶部を参照して、前記隣接ストレージノードが所属するグループを識別し、前記グループで必要な複製数に達していない場合には、前記隣接ストレージノードを前記グループの複製先ノードリストに登録し、
全てのグループに対して必要な複製数の複製先が得られるまで、前記ハッシュリング上で次の隣接ストレージノードを取得して前記次の隣接ストレージノードが所属するグループの複製先ノードリストに登録する処理を順次行うことで、前記複製先ノードリストを作成し、
前記複製先ノードリスト上のストレージノードに対してデータの複製を行う、ことを特徴とする分散ストレージ方法。
【請求項４】
前記ストレージノードでは、データの複製を作成するにあたり、
（ａ）前記複数のストレージノードが論理的に配置された前記前記ハッシュリング上で、現在のストレージノードに隣接するストレージノードを取得し、
（ｂ）前記記憶部を参照して、前記取得した隣接ストレージノードの所属グループを識別し、前記所属グループに指定されているデータの複製数と、複製先ノードリストに含まれているノードの数とを比較し、
（ｃ）前記所属するグループの複製先のストレージノードの数が指定複製数に達している場合には、前記隣接ストレージノードを前記現在のストレージノードとして、（ａ）の前記ハッシュリング上の隣接ストレージノードの取得処理に戻り、
（ｄ）前記所属するグループの複製先のストレージノードの数が指定複製数に達していない場合には、（ａ）で取得した隣接ストレージノードを複製先ノードリストに追加し、
（ｅ）前記ハッシュリング上のストレージノードが所属するグループの全てに対して必要な複製数に達しているか判定し、
（ｆ）前記判定の結果、前記ハッシュリング上のストレージノードが属する全ての所属グループに対して必要な複製数に達していない場合、前記隣接ストレージノードを前記現在のストレージノードとして、（ａ）の前記ハッシュリング上の隣接ストレージノードの取得処理に戻り、
（ｇ）前記判定の結果、前記ハッシュリング上のストレージノードが属する全ての所属グループに対して必要な複製数に達している場合、複製先ノードリストを複製命令発行手段に送り、
前記複製命令発行手段は、前記複製先ノードリストに含まれるストレージノード対して複製命令を発行する、請求項３記載の分散ストレージ方法。
【請求項５】
複数のストレージノードを備えた分散ストレージシステムを構成する前記ストレージノードを構成するコンピュータに、
システムの動作状態に関してグループ化されてなる前記複数のストレージノードの前記ストレージノード毎の所属するグループと、前記グループ毎に定められた複製数と、指定されたシステムの動作の状態情報に記憶部に記憶する処理と、
データ書き込み命令に応答して、前記複数のストレージノードが論理的に配置されたハッシュリング上で隣接ストレージノードを取得し、前記記憶部を参照して、前記隣接ストレージノードが所属するグループを識別し、前記グループで必要な複製数に達していない場合には、前記隣接ストレージノードを前記グループの複製先ノードリストに登録し、
全てのグループに対して必要な複製数の複製先が得られるまで、前記ハッシュリング上で次の隣接ストレージノードを取得して前記次の隣接ストレージノードが所属するグループの複製先ノードリストに登録する処理を順次行うことで、前記複製先ノードリストを作成し、
前記複製先ノードリスト上のストレージノードに対してデータの複製を行う処理と、
を実行させるプログラム。
【請求項６】
前記ストレージノードが、
（ａ）前記複数のストレージノードが論理的に配置されたハッシュリング上で、現在のストレージノードに隣接するストレージノードを取得し、
（ｂ）前記記憶部を参照して、前記取得した隣接ストレージノードの所属グループを識別し、前記所属グループに指定されているデータの複製数と、複製先ノードリストに含まれているノードの数とを比較し、
（ｃ）前記所属するグループの複製先のストレージノードの数が指定複製数に達している場合には、前記隣接ストレージノードを前記現在のストレージノードとして、（ａ）の前記ハッシュリング上の隣接ストレージノードの取得処理に戻り、
（ｄ）前記所属するグループの複製先のストレージノードの数が指定複製数に達していない場合には、（ａ）で取得した隣接ストレージノードを複製先ノードリストに追加し、
（ｅ）前記ハッシュリング上のストレージノードが所属するグループの全てに対して必要な複製数に達しているか判定し、
（ｆ）前記判定の結果、前記ハッシュリング上のストレージノードが属する全ての所属グループに対して必要な複製数に達していない場合、前記隣接ストレージノードを前記現在のストレージノードとして、（ａ）の前記ハッシュリング上の隣接ストレージノードの取得処理に戻り、
（ｇ）前記判定の結果、前記ハッシュリング上のストレージノードが属する全ての所属グループに対して必要な複製数に達している場合、複製先ノードリストを前記複製命令発行処理に送る、
前記（ａ）乃至（ｇ）を実行するアクセスノード算出処理と、
前記複製先ノードリストに含まれるストレージノード対して複製命令を発行する前記複製命令発行処理と、を前記コンピュータに実行させる、請求項５記載のプログラム。
【請求項７】
動作状態に関してグループ化されてなる複数のストレージノードに対して、グループごとに規定されるデータ複製数分、データの複製を行う分散ストレージシステムを構成するストレージノードであって、
システムの動作状態に関してグループ化されてなる前記複数のストレージノードの前記ストレージノード毎の所属するグループと、前記グループ毎に定められた複製数と、指定されたシステムの動作の状態情報を記憶する記憶部と、
データ書き込み命令に応答して、前記複数のストレージノードが論理的に配置されたハッシュリング上で隣接ストレージノードを取得し、前記記憶部を参照して、前記隣接ストレージノードが所属するグループを識別し、前記グループで必要な複製数に達していない場合には、前記隣接ストレージノードを前記グループの複製先ノードリストに登録し、
全てのグループに対して必要な複製数の複製先が得られるまで、前記ハッシュリング上で次の隣接ストレージノードを取得して前記次の隣接ストレージノードが所属するグループの複製先ノードリストに登録する処理を順次行うことで、前記複製先ノードリストを作成し、
前記複製先ノードリスト上のストレージノードに対してデータの複製を行う手段と、を備えた、ことを特徴とするストレージノード。
【請求項８】
（ａ）前記複数のストレージノードが論理的に配置されたハッシュリング上で、現在のストレージノードに隣接するストレージノードを取得し、
（ｂ）前記取得した隣接ストレージノードの所属グループを識別し、前記所属グループに指定されているデータの複製数と、複製先ノードリストに含まれているノードの数とを比較し、
（ｃ）前記所属するグループの複製先のストレージノードの数が指定複製数に達している場合には、前記隣接ストレージノードを前記現在のストレージノードとして、（ａ）の前記ハッシュリング上の隣接ストレージノードの取得処理に戻り、
（ｄ）前記所属するグループの複製先のストレージノードの数が指定複製数に達していない場合には、（ａ）で取得した隣接ストレージノードを複製先ノードリストに追加し、
（ｅ）前記ハッシュリング上のストレージノードが所属するグループの全てに対して必要な複製数に達しているか判定し、
（ｆ）前記判定の結果、前記ハッシュリング上のストレージノードが属する全ての所属グループに対して必要な複製数に達していない場合、前記隣接ストレージノードを前記現在のストレージノードとして、（ａ）の前記ハッシュリング上の隣接ストレージノードの取得処理に戻り、
（ｇ）前記判定の結果、前記ハッシュリング上のストレージノードが属する全ての所属グループに対して必要な複製数に達している場合、複製先ノードリストを複製命令発行手段に送る、
前記（ａ）乃至（ｇ）を実行するアクセスノード算出手段と、
前記複製先ノードリストに含まれるストレージノードに対して複製命令を発行する前記複製命令発行手段と、
を備えた、請求項７記載のストレージノード。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願についての記載）
本発明は、日本国特許出願：特願２００９−２０２０６１号（２００９年９月１日出願）の優先権主張に基づくものであり、同出願の全記載内容は引用をもって本書に組み込み記載されているものとする。
本発明は、分散ストレージシステム、分散ストレージ方法および分散ストレージ用プログラム及びストレージノードに関する。
【背景技術】
【０００２】
＜コンシステント・ハッシュ法＞
近年、分散ストレージシステム、特にハッシュ関数を用いてデータの分散配置を行うことにより、スケーラブルな性能を持ったストレージシステムを実現する試みが増えている。ハッシュ関数を用いたデータの分散配置方法として、例えばコンシステント・ハッシュ法（非特許文献１、非特許文献２）がある。【０００３】
コンシステント・ハッシュ法は、データを複数のストレージ装置（例えばＩＡサーバ（Ｉｎｔｅｌ社のマイクロプロセッサを搭載したサーバ）のようなＣＰＵとメモリからなるコンピュータ装置が当てはまる）に分散して配置する。コンシステント・ハッシュ法を応用したシステムとしては、分散ハッシュテーブル等がある。【０００４】
このような分散配置手法としてコンシステント・ハッシュ法を用いる理由として以下が挙げられる。
ストレージ装置を追加、削除しても、データの分散記録状態を維持するために、データ全体を分散配置し直す必要がないためである。【０００５】
また複数のストレージ装置の一つに障害が発生しても、復旧が柔軟に行えるためである。【０００６】
非特許文献３には、コンシステント・ハッシュ法により、データの分散配置を行っている分散ストレージシステムの一例が開示されている。図１は、非特許文献３のＦｉｇｕｒｅ２をそのまま引用して掲載したものである。【０００７】
非特許文献３に開示される分散ストレージシステムは、概略次のように動作する。非特許文献３によると、キー（Ｋｅｙ）がＫであるデータ（Ｋｅｙをハッシュ値で求めるとすると、データのハッシュ値がＫであるデータ）の格納するノード（Ｎｏｄｅ）は、コンシステント・ハッシュ法により、ノードＢと決定される。これは、ハッシュリングをＫの位置から時計回りに回って最初に存在するノードがＢであるためである。この時、分散ストレージシステムを構成するストレージ装置は故障する可能性があることから、データを別のストレージ装置にも保存しておくことが望ましい。非特許文献３の分散ストレージシステムでは、キー（Ｋｅｙ）がＫのデータを３つのストレージ装置に保存する事としており、ノードＢを更に時計回りに辿りノードＣ、ノードＤにもデータを保存する。キーＫを含めてＡとＢの範囲のキーは、ノードＢ、Ｃ、Ｄに保存される。【０００８】
また、このようなハッシュ関数を用いた分散ストレージシステムの構築手法は、非特許文献３に記載されるように、マスタデータを格納するために利用されるだけでなく、マスタデータのキャッシュ（一時的な、消えても良いデータ）を格納するための仕組みとしても利用される。この場合、マスタデータを別のストレージシステム（例えばデータベースシステム等が挙げられる）に記録しておき、そのデータを読み出すクライアントがマスタデータのストレージシステムにアクセスするのではなく、キャッシュ用の分散ストレージシステムにアクセスする、といったように動作する。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】Ｄａｖｉｄ  Ｋａｒｇｅｒ，  Ｅｒｉｃ  Ｌｅｈｍａｎ，  Ｔｏｍ  Ｌｅｉｇｈｔｏｎ，  Ｍａｔｔｈｅｗ  Ｌｅｖｉｎｅ，  Ｄａｎｉｅｌ  Ｌｅｗｉｎ，  Ｒｉｎａ  Ｐａｎｉｇｒａｈｙ，  “Ｃｏｎｓｉｓｔｅｎｔ  ｈａｓｈｉｎｇ  ａｎｄ  ｒａｎｄｏｍ  ｔｒｅｅｓ：  Ｄｉｓｔｒｉｂｕｔｅｄ  ｃａｃｈｉｎｇ  ｐｒｏｔｏｃｏｌｓ  ｆｏｒ  ｒｅｌｉｅｖｉｎｇ  ｈｏｔ  ｓｐｏｔｓ  ｏｎ  ｔｈｅ  Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ”，  Ｉｎ  ＡＣＭ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｔｈｅｏｒｙ  ｏｆ  Ｃｏｍｐｕｔｉｎｇ，  １９９７
【非特許文献２】Ｔｏｍ  Ｗｈｉｔｅ’ｓ  Ｂｌｏｇ：  Ｃｏｎｓｉｓｔｅｎｔ  Ｈａｓｈｉｎｇ，  ｈｔｔｐ：／／ｗｅｂｌｏｇｓ．ｊａｖａ．ｎｅｔ／ｂｌｏｇ／ｔｏｍｗｈｉｔｅ／ａｒｃｈｉｖｅ／２００７／１１／ｃｏｎｓｉｓｔｅｎｔ＿ｈａｓｈ．ｈｔｍｌ，  ２００９年２月２７日アクセス
【非特許文献３】Ｇｉｕｓｅｐｐｅ  ＤｅＣａｎｄｉａ，  Ｄｅｎｉｚ  Ｈａｓｔｏｒｕｎ，  Ｍａｄａｎ  Ｊａｍｐａｎｉ，  Ｇｕｎａｖａｒｄｈａｎ  Ｋａｋｕｌａｐａｔｉ，  Ａｖｉｎａｓｈ  Ｌａｋｓｈｍａｎ，  Ａｌｅｘ  Ｐｉｌｃｈｉｎ，  Ｓｗａｍｉｎａｔｈａｎ  Ｓｉｖａｓｕｂｒａｍａｎｉａｎ，  Ｐｅｔｅｒ  Ｖｏｓｓｈａｌｌ  ａｎｄ  Ｗｅｒｎｅｒ  Ｖｏｇｅｌｓ，  “Ｄｙｎａｍｏ：  Ａｍａｚｏｎ’ｓ  Ｈｉｇｈｌｙ  Ａｖａｉｌａｂｌｅ  Ｋｅｙ−Ｖａｌｕｅ  Ｓｔｏｒｅ”，  ｉｎ  ｔｈｅ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２１ｓｔ  ＡＣＭ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍｓ  Ｐｒｉｎｃｉｐｌｅｓ，  Ｓｔｅｖｅｎｓｏｎ，  ＷＡ，  Ｏｃｔｏｂｅｒ  ２００７．
【発明の概要】
【発明が解決しようとする課題】
【００１０】
なお、上記非特許文献の全開示内容はその引用をもって本書に繰込み記載する。
以下に本発明による関連技術の分析を与える。【００１１】
＜分散ストレージシステムに求められる機能＞
近年、例えばデータセンター等で運用されるＩＴシステムの電力消費が問題となっている。電力代や地球環境への影響等を考慮して電力消費をコントロール出来るＩＴシステムが求められている。分散ストレージシステムにおいて、電力消費をコントロールするためには、システムが必要とする性能や機能に応じて、分散ストレージシステムを構成するストレージ装置を柔軟に停止させたり、動作させたりことが必要となる。【００１２】
＜コンシステント・ハッシュ法を用いた分散ストレージシステムの問題点＞
しかしながら、分散ストレージシステムにおいては、多数のストレージ装置をほぼ同時に、そして即時（一斉）に停止させることが出来ない、という問題がある。【００１３】
その理由は、分散ストレージシステムにおいて、例えばシステムを構成する半分のストレージ装置等、多数のストレージ装置（「ストレージノード」ともいう）を即座に停止させると、アクセスできなくなるデータが存在するためである。また、多数のストレージ装置を停止させた後に、データがアクセス出来る状態にあったとしても、システムに要求される可用性・性能を満たさない可能性があるためである。【００１４】
すなわち、コンシステント・ハッシュ法を用いた分散ストレージシステムにおいては、ある特定のストレージ装置を停止させると、データの冗長度や負荷分散を維持するためにデータの移動や再配置が行われる。【００１５】
例えば図１に示したようなルールでデータの複製を作成するとする。このとき、ノードＢに障害が発生し、ノードＢをリングから取り除いた場合、キー（Ｋｅｙ）＝Ｋのデータは、ノードＣおよびノードＤにのみ記録されていることとなる。【００１６】
この場合、２つのノードＣとＤにだけデータが記録されていることになるため、データの冗長度は、最初の状態（ノードＢに障害が発生する前のリングに接続され、データの複製を３つのノードＢ、Ｃ、Ｄで保持するという状態）よりも低くなる。そのため、ノードＢの取り外しにより、可用性やリードパフォーマンスが劣化する可能性がある。【００１７】
そこで、データの複製を３つ保持するという状態を維持するために、ノードＤからノードＥに対してキー（Ｋｅｙ）＝Ｋのデータを複製するように、システムが動作する。【００１８】
このように、ノードＢをリングから取り除いた場合、ノードＤからノードＥにキー（Ｋｅｙ）＝Ｋのデータを複製することにより、可用性やリードパフォーマンスの劣化等は回避され、特に大きな問題は生じない。【００１９】
しかしながら、上記したように、システムの省電力化のためには、分散ストレージシステムの動作ノードの半数を同時に停止させる動作が必要となる場合がある。例えば図１において、分散ストレージシステムの動作ノードを半数にする際に、ノードＢ、Ｃ、Ｄが停止されたとする。【００２０】
すると、キー（Ｋｅｙ）＝Ｋのデータを冗長保存しているすべてのノードが停止されてしまうことになり、その結果、キー（Ｋｅｙ）＝Ｋのデータに対してアクセスできなくなる。【００２１】
クライアントが、キー（Ｋｅｙ）＝Ｋのデータにアクセスする際に、ノードＢ、Ｃ、Ｄのいずれかを再開させないと、当該データへのアクセスはできない。ノードの再開により電力消費が上がり、省電力化の実現には、問題となる。【００２２】
また、データを冗長保存しているノードが全て停止されなかったとしても、動作ノードの半分程度や９割を同時に停止させたりすると、データの冗長度を維持するために、稼動している残りのノード間で、データの複製が大量に発生することになる。このため、データアクセスの可用性や性能が劣化することになる。【００２３】
したがって、本発明の目的は、分散ストレージシステムを構成する複数のストレージ装置を同時に停止できる、分散ストレージシステム、方法、プログラムとストレージノードを提供することにある。【００２４】
また、本発明は上記目的を達成するとともに、複数のストレージ装置を停止させても、データに対する所定の可用性・性能を維持し続ける分散ストレージシステム、方法、プログラムとストレージノードを提供することもその目的の１つとしている。
【課題を解決するための手段】
【００２５】
本発明によれば、システムの動作状態を指定する手段と、データ複製作成手段とを備え、前記システムの動作状態を指定する手段は、分散ストレージシステムに参加する複数のストレージノードをシステムの動作状態に対応したグループに分け、前記データ複製作成手段は、分散ストレージシステムへ参加する複数のストレージノードに対して、グループごとに規定されるデータ複製数分、データの複製を作成する分散ストレージシステムが提供される。【００２６】
本発明によれば、分散ストレージシステムへ参加する複数のストレージノードをシステムの動作状態に対応したグループに分け、
データの書き込み要求を受けたストレージノードは、分散ストレージシステムへ参加する複数のストレージノードに対してグループごとに規定されるデータ複製数分、データの複製を作成する、分散ストレージ方法が提供される。【００２７】
本発明によれば、システムの動作状態を指定する処理と、データ複製作成処理とをストレージノードを構成するコンピュータに実行させるプログラムであって、前記システムの動作状態を指定する処理は、分散ストレージシステムへ参加する複数のストレージノードをシステムの動作状態に対応したグループに分け、前記データ複製作成処理は、分散ストレージシステムへ参加する複数のストレージノードに対してグループごとに規定されるデータ複製数分、データの複製を作成するプログラムが提供される。【００２８】
本発明によれば、分散ストレージシステムに参加する複数のストレージノードをシステムの動作状態に対応したグループに分け、分散ストレージシステムへ参加する複数のストレージノードに対して、グループごとに規定されるデータ複製数分、データの複製を作成する分散ストレージシステムを構成するストレージノードであって、前記複数のストレージノードが論理的に配置されたハッシュリングを辿り、グループごとの規定されるデータ複製数に達成するまで複製先を探索し、複製先ストレージノードのリストを作成するデータ複製作成手段を備えたストレージノードが提供される。【００２９】
本発明によれば、分散ストレージシステムに参加する複数のストレージノードをシステムの動作状態に対応したグループに分け、分散ストレージシステムへ参加する複数のストレージノードに対して、グループごとに規定されるデータ複製数分、データの複製を作成する分散ストレージシステムを構成するストレージノードであって、
前記複数のストレージノードが論理的に配置されたハッシュリングを辿り、ハッシュリング上、所属するグループに対応した隣接ストレージノードに複製命令を発行し、
複製先のストレージノードが前記グループに対応して規定されるデータ複製数に達成したか否かを確認し、前記複製先のストレージノードが前記グループに対応して規定されるデータ複製数に達成していなければ、更なる前記ハッシュリング上の前記グループに対応した隣接ストレージノードに複製命令を発行し、達成していれば複製処理を終了するストレージノードが提供される。
【発明の効果】
【００３０】
本発明によれば、分散ストレージシステムを構成する複数のストレージ装置を同時に停止できる。また本発明によれば、複数のストレージ装置を停止させても、データに対する所定の可用性・性能を維持し続けることができる。
【図面の簡単な説明】
【００３１】
【図１】非特許文献３のＦｉｇｕｒｅ．２より引用した図で、コンシステント・ハッシング法による分散ストレージシステムにおけるデータ複製方法を示す図である。
【図２】本発明の一実施形態の構成を示す図である。
【図３】本発明の一実施形態の構成を示す図である。
【図４】本発明の一実施形態におけるクライアント、ストレージノードの構成の一例を示す図である。
【図５】本発明の一実施形態におけるＰＵＴ処理の全体動作を説明する流れ図である。
【図６】本発明の一実施形態における複製処理動作を説明する流れ図である。
【図７】本発明の一実施形態における複製先算出手順を説明する流れ図である。
【発明を実施するための形態】
【００３２】
＜発明の基本原理＞
本発明の分散ストレージシステムは、システムの動作状態を定義する手段と、データの複製作成手段を備えている。分散ストレージシステムへ参加する複数のストレージノード（ストレージ装置）を予めグループに分けておき、データ複製作成手段は、分散ストレージシステムのストレージノードに、それぞれのグループに対応させて、データの複製を作成する。
【００３３】
本発明において、システムの動作状態を定義する手段は、グループに対応してデータの複製数を設定する。データ複製作成手段は、複数のストレージノードが配置されるハッシュリングを辿り、グループごとの複製数に達成するまでデータの複製を作成する。
【００３４】
このように、本発明によれば、分散ストレージシステムに参加する複数のストレージノードを、システム動作状態に対応したグループに分け、グループ毎に規定のデータ複製数を満たすようにデータを複製して保持する構成としたことにより、分散ストレージシステムにおいて、複数のストレージノードを一度に停止させても、データに対する所定の可用性・性能を維持し続けることを可能としている。
【００３５】
そして、本発明によれば、分散ストレージシステムにおいて複数のストレージノードを一斉に停止することができることから、大規模分散システムの運用時において、負荷や用件に応じて、稼動ストレージノードの数を現在の稼動数等から、例えば半分に減らしたりするといった切替制御が可能となる。これにより、省電力化の分散ストレージシステムを実現することができる。しかも、分散ストレージシステムにおいて、省電力を優先して動作するストレージノード数を減らした場合にも、データの冗長度（複製数）を維持することができることから、予め定められた可用性やデータの読み出し性能を確保することができる。
【００３６】
本発明において、データの冗長度（複製数）を維持することができるのは、システムの状態に対応したグループ毎にデータの複製数が指定され、ハッシュリング上で、複製先を決定しているためである。データ書き込み時、分散ストレージシステムを構成するストレージノードの論理的に配置されるハッシュリング上を、例えば時計回りに、隣接ノードを次々に辿り、該隣接ノードがどのグループであるか識別し、識別されたグループに対して予め指定された複製数に達していない場合、当該ノードを識別されたグループに対応した複製先として決定し、ハッシュリング上のストレージノードが所属するグループの全てに対して、予め指定された複製数の複製先が検出された場合、各グループに対応して決定された複製先に対して、当該データの複製を作成する。
【００３７】
本発明においても、コンシステント・ハッシング法の基本的な効果である、ランダムな負荷分散、ノード障害時におけるノード除去等において、データの再配置が必要無く、少ないデータ複製量でノードの追加・除去が可能という効果を保持し続けることが可能である。次に、本発明の実施形態について図面を参照して詳細に説明する。
【００３８】
＜実施形態＞
図２を参照すると、本発明の第１の実施の形態は、任意の数のストレージノード１と任意の数のクライアント２とを含む。ストレージノード１とクライアント２はネットワーク装置で接続されている。ストレージノード１は、分散ストレージシステムにおいて、データの格納先となるノード（計算機）であり、クライアント２は分散ストレージシステムに対してデータアクセスを行うノード（計算機）である。ネットワークは、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、ＷＡＮ（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、パケット網あるいは回線網、専用線、無線・有線等、任意の通信ネットワーク装置であってよい。
【００３９】
ストレージノード１はプロセッサ等の演算装置と、半導体メモリや磁気記憶装置等の記憶装置、ネットワーク接続機器等を備えた計算機（サーバ）である。また、クライアント２も同様に、プロセッサ等の演算装置とネットワーク接続機器を備えた計算機（サーバ）である。
【００４０】
本実施の形態における分散ストレージシステムは、図３に示すような、リング構造を論理的に保持する（物理的にリング構造である必要はない）。ストレージノード１０〜１９は、分散ストレージシステムを構成するノードである。
【００４１】
クライアント２は、データにアクセスする際に、コンシステント・ハッシュ法により算出されたストレージノードに対してデータアクセスを行う。例えば、ハッシュ空間上で、ストレージノード１９とストレージノード１０の間のデータ（オブジェクト）に対しては、ストレージノード１０（ハッシュリング上で時計回りに最も近いストレージノード）に対してアクセス（読み出しおよび書き込み）するという動作を行う。
【００４２】
＜クライアントとストレージノードの構成＞
図４は、本実施の形態におけるクライアントとストレージノードの構成を示す図である。図４には、クライアント２と、ストレージノード１０〜１１、動作状態指定手段３を備えている。なお、図４では、簡単のため１つのクライアントと２つのストレージノードが示されているが、これらの個数は任意である。
【００４３】
ストレージノード１０〜１１は、同一構成とされる。ストレージノード１は、アクセス要求受信手段１０１と、アクセス要求処理手段１０２と、データアクセス手段１０３と、データ記憶部１０４と、複製命令受信手段１０５と、複製命令発行手段１０６と、アクセスノード算出手段１０７と、ルーティング情報記憶部１０８と、ノード環境情報記憶部１０９とを含む。これらの手段はそれぞれ概略次のように動作する。
【００４４】
アクセス要求受信手段１０１は、クライアント２からのアクセス要求を受け取り、受け取ったアクセス要求をアクセス要求処理手段１０２に渡す。
【００４５】
アクセス要求処理手段１０２は、アクセス要求を解釈し、データアクセス手段１０３に対して渡す。また、アクセス要求処理手段１０２は、アクセス要求を解釈した結果、複製を作成する必要がある場合には、複製命令発行手段１０６に対して複製処理命令の発行を依頼する。
【００４６】
データアクセス手段１０３は、データ記憶部１０４に対してデータの読み出しおよび書き込みの処理を行う。
【００４７】
データアクセス手段１０３は、クライアント２からのアクセス要求をアクセス要求受信手段１０１およびアクセス要求処理手段１０２を介して受け取り、アクセス要求に応じた処理を行い、クライアント２に対して応答を行う。
【００４８】
またデータアクセス手段１０３は、他のストレージノードの複製命令発行手段１０６からの複製命令を複製命令受信手段１０５で受け取った場合、データの複製を、データ記憶部１０４に作成する。
【００４９】
データ記憶部１０４は、分散ストレージシステムのデータを記録する記憶装置である。データ記憶部１０４は、半導体メモリやＨＤＤ（ハードディスクドライブ）等の磁気記憶装置によって実現される。
【００５０】
複製命令受信手段１０５は、他のストレージノードの複製命令発行手段１０６からの複製命令を受信し、データアクセス手段１０３に対して処理を依頼する。
【００５１】
複製命令発行手段１０６は、アクセス要求処理手段１０２からのアクセス要求を受け取り、複製先のストレージノードに対して複製命令を発行し、必要な複製データを転送する。複製先のストレージノードの情報はアクセスノード算出手段１０７に依頼して取得する。
【００５２】
アクセスノード算出手段１０７は、複製先のストレージノードを求める。複製先のストレージノードの算出は、概略次のように行う。
【００５３】
（Ａ）アクセスノード算出手段１０７は、複製先のルーティング情報記憶部１０８に記憶されている情報とハッシュ関数を用いて、ハッシュリング上における隣接ノードを求める。
【００５４】
（Ｂ）次に、アクセスノード算出手段１０７は、ノード環境情報記憶部１０９に記憶されている情報を用いて隣接ノードが複製先であるか否かを判定する。
【００５５】
（Ｃ）アクセスノード算出手段１０７は、さらに隣のストレージノードを算出し、算出した更に隣のストレージノードが複製先であるか否かを判定する、
という処理を繰り返す。
【００５６】
アクセスノード算出手段１０７は、ノード環境情報記憶部１０９に記録されているデータの複製数の規定値に達するまで、処理（Ａ）、（Ｂ）、（Ｃ）を繰り返すことにより、複製先ノードを決定する。この処理手順は、図７を参照して後述される。
【００５７】
ルーティング情報記憶部１０８には、データ配置のルーティングに必要な情報を記憶する。具体的には、ストレージノードの名称およびアクセスするのに必要十分な情報（例えばＩＰアドレスとポート番号）が記憶保持される。また、ルーティング情報記憶部１０８には、ハッシュリングを構成するためのハッシュ関数の種類、アルゴリズム、プログラム等も記憶保持される。なお、アクセスノード算出手段１０７のプログラムに、データ配置のルーティングに必要な情報を組み込む場合、ルーティング情報記憶部１０８にはこれらの情報を記憶していなくてもよい。
【００５８】
ノード環境情報記憶部１０９には、ストレージノード毎の所属するグループの情報や、グループ毎に定められた冗長度（複製数：number-of-Replicas）が記録保持される。ストレージノード毎の所属するグループの情報は、ルーティング情報記憶部１０８にともに記録するようにしてもよい。例えば、ストレージノードの名称で所属するグループが判明するようにしてもよい。
【００５９】
クライアント２は、アクセスノード算出手段２１と、ルーティング情報記憶部２２と、アクセス手段２３とを含む。
【００６０】
アクセスノード算出手段２１は、クライアント２が任意のデータに対するアクセスを行う際に、そのデータにおけるアクセス先のストレージノードを算出する手段である。おおむね、ストレージノードにおけるアクセスノード算出手段１０７と同じ機能を持ち、ルーティング情報記憶部２２に記憶される情報とハッシュ関数を用いて、アクセス先のストレージノードを算出する。
【００６１】
ルーティング情報記憶部２２は、データ配置のルーティングに必要な情報を記憶する。具体的には、ストレージノードの名称およびアクセスするのに十分な情報（例えばＩＰアドレスとポート番号）が記憶される。おおむねストレージノードにおけるルーティング情報記憶部１０８と同等の機能を持つ。
【００６２】
アクセス手段２３は、クライアント２において分散ストレージシステムに対するデータのアクセスを行う。アクセス手段２３は、アクセスノード算出手段２１によって算出されたストレージノードに対してアクセス要求を発行し、当該ストレージノードからアクセス要求に対するアクセス結果を受け取る。
【００６３】
動作状態指定手段３は、システム全体の動作状態の指定を行う。図４に示す例では、説明のため、動作状態指定手段３は、クライアント２およびストレージノード１０〜１９とは別の要素として示されているが、物理的には、任意のクライアント２やストレージノード１０〜１９上で動作するソフトウェア（コンピュータ・プログラム）として実現してもよい。
【００６４】
＜システムの動作状態＞
分散ストレージシステムにおけるシステム全体の動作状態として、下記の表１は、システム全体の動作状態情報の例を示す。
【００６５】
【表１】
0005556816.tif 000002
【００６６】
この例において、分散ストレージシステムは、１０００個のストレージノードから構成される。そして、状態Ａは１０００ノード全てを用いて分散ストレージシステムを動作させ（最大利用）、状態Ｂは１０００個のノードのうちの半分の５００個のノードを動作させ（標準利用）、状態Ｃは１０００個のノードのうちの１００個のノードを動作させる（節電利用）。
【００６７】
また、状態Ａでは、データは６つのノードに複製され、状態Ｂではデータは４つのノードに複製され、状態Ｃではデータは２つのノードに複製されるよう動作する。表１の「冗長度」は、状態に対応するグループにおけるデータ複製数に対応する。
【００６８】
本実施形態の分散ストレージシステムは、状態をＡから状態Ｂ、状態Ｂから状態Ｃ等、状態を切り替えた際にも、動作状態毎に定義された可用性を保証しつつ動作する。
【００６９】
分散ストレージシステムを構成する各々のストレージノードは、それぞれの状態を示すグループのうちのいずれか（グループＡ、グループＢ、グループＣのいずれか）に所属する。
【００７０】
＜ストレージノード集合＞
状態Ｘの際に動作するストレージノードの集合をＮｏｄｅｓ（Ｘ）と表記すると、表１に関して、以下の関係が成り立つ。
【００７１】
Ｎｏｄｅｓ（Ａ）⊃Ｎｏｄｅｓ（Ｂ）⊃Ｎｏｄｅｓ（Ｃ）
【００７２】
すなわち、状態Ａのストレージノード集合（グループ）は、状態Ｂのストレージノード集合（グループ）を含む。また、状態Ｂのストレージノード集合（グループ）は、状態Ｃのストレージノード集合（グループ）を含む。
【００７３】
システムの動作状態として、状態Ｃで動作しているストレージノードは状態Ａ（分散ストレージシステムの全ノードが動作する動作状態）の場合にも、動作する。
【００７４】
本実施の形態における動作状態指定手段３は、システムの動作状態を切り替える指示を与える。各状態の動作状態情報（状態Ａ、Ｂ、Ｃの設定内容）は予め指定されているものとする。また、各ストレージノードがいずれかのグループに所属するかについても予め決められているものとする。ただし、動作状態指定手段３において、動作状態情報およびストレージノードの構成等を変更するようにしてもよいことは勿論である。例えば、動作状態情報の冗長度について、動作状態指定手段３は、各ストレージノードのノード環境情報記憶部１０９の情報を書き換え、冗長度の変更に基づいて、各ストレージノードでデータの複製や削除の動作を行えばよい。
【００７５】
また、ストレージノードの所属グループの変更や、各動作状態のストレージノードの構成数等の変更についても同様であるが、いずれも、本発明の主題に直接関係しない部分であるため、説明を省略する。
【００７６】
動作状態指定手段３は、状態変更により、各ストレージノードのノード環境情報記憶部１０９の更新（変更指示）を行う。例えば、それまでのシステムの状態が、上記表１の状態Ａであったものを、現在の状態として、状態Ｂに変更する。この場合、１０００ノードのうちの半分の５００ノードを、冗長度＝４（データ複製数）で動作させることになる。
【００７７】
また、動作状態指定手段３は、必要があれば、グループＡに所属するが、グループＢとグループＣのいずれにも所属さないストレージノード（Ｎｏｄｅ（Ａ∩ｎｏｔ（Ｂ）∩ｎｏｔ（Ｃ））に対して、ノードの停止命令を発行してもよい。各々のストレージノードは停止命令に応じてシステムを停止する。
【００７８】
＜動作の説明＞
次に、図５、図６、図７のフローチャートを用いて、本実施形態の動作例について説明する。
【００７９】
分散ストレージシステムに対するデータのアクセス動作について説明する。本実施形態においては、Ｗｒｉｔｅ処理（データのＰＵＴ処理）が、一般的なストレージシステムとは異なるため、この点について主に説明する。リードについては、一般的なコンシステント・ハッシング法を用いた分散ストレージシステムと同様であるため、説明を省略する。
【００８０】
＜ＰＵＴ処理＞
図５は、本実施形態におけるデータのＰＵＴ処理の全体の手続きを示すフローチャートである。
【００８１】
まず、クライアント２のアクセス手段２３が分散ストレージシステムを構成するストレージノードのうちアクセス先のストレージノードに対してデータのＰＵＴ命令を発行する（図５のステップＳ１０１）。
【００８２】
クライアント２によるＰＵＴ命令の発行先のストレージノードは、ＰＵＴするデータのＫｅｙに応じて決定される。ＰＵＴ命令の発行先のストレージノードは、クライアント２においてアクセスノード算出手段２１が算出する。特に制限されないが、データのＫｅｙ値のハッシュ値から、リングを時計回りに辿り、最初に到達するストレージノードをＰＵＴ命令の発行先とする（コンシステント・ハッシュ法）。なお、データのＫｅｙ値は、任意の方法で決めてよい。本実施形態では、データのＫｅｙ値は、分散ストレージシステムを利用するクライアント２のアプリケーションが決めるか、データの内容のハッシュ値等で決定する。
【００８３】
次に、クライアント２からのデータＰＵＴ命令を受け取ったストレージノードのアクセス要求処理手段１０２は、アクセス要求受信手段１０１からアクセス要求（ＰＵＴ命令）を受け取り、このＰＵＴ命令を解釈して、データアクセス手段１０３と複製命令発行手段１０６に対して渡す（ステップＳ１０２）。
【００８４】
図５のステップＳ１０２以降、ステップＳ１０３のデータアクセス処理と、ステップＳ１０４の複製処理フローに分かれる。ステップＳ１０３とステップＳ１０４は、並行して実行するようにしてもよい。
【００８５】
次のデータアクセス処理は、データアクセス手段１０３がデータ記憶部１０４に対してＰＵＴ命令のデータの書き込み処理を行う（ステップＳ１０３）。
【００８６】
複製命令発行手段１０６は、他のストレージノードに対して、複製処理を依頼する（ステップＳ１０４）。この複製処理フローについては、後に詳述される。
【００８７】
ステップＳ１０３の次に、必要があれば、複製処理の完了を待つ（ウエイト）（ステップＳ１０５）。
【００８８】
ただし、ステップＳ１０５のウエイト処理は、
（ａ）他のストレージノードに対するデータの複製処理が完了してから、クライアント２に応答する、又は、
（ｂ）自身（クライアント２からのデータＰＵＴ命令を受け取ったストレージノード）のデータ記憶部１０４へのデータの書き込みが完了した時点で、クライアント２に応答する等、
分散ストレージシステムの動作ポリシーに依存する。本実施形態では、いずれかのポリシーにしたがったストレージシステムでもよい。ステップＳ１０５は、必要に応じて実行されるものであるため、ポリシー如何では省略してもよい。
【００８９】
クライアント２からのデータＰＵＴ命令を受け取ったストレージノードは、クライアント２に対して、ＰＵＴ処理の完了通知を発行する（ステップＳ１０６）。
【００９０】
＜複製処理＞
図６は、図５のステップＳ１０４の複製処理の処理手順を示す流れ図（フローチャート）である。
【００９１】
まず、ストレージノード（クライアント２からのデータＰＵＴ命令を受け取ったストレージノード）において、複製命令発行手段１０６が、アクセス要求処理手段１０２からのＰＵＴ命令の複製処理命令を受け取る（図６のステップＳ２０１）。
【００９２】
次に、複製命令発行手段１０６は、アクセスノード算出手段１０７に対して、複製先ノードの情報算出を依頼する（ステップＳ２０２）。
【００９３】
アクセスノード算出手段１０７が複製先ノードを算出し、複製命令発行手段１０６に複製先ストレージノードのリスト（複製先ノードリスト）を渡す（ステップＳ２０３）。アクセスノード算出手段１０７における複製先ノードリストの算出については後述される。
【００９４】
次に、複製命令発行手段１０６は、算出された複製先ノードリストに対して複製命令を発行する（ステップＳ２０４）。
【００９５】
複製命令の発行方法は、
・複製先ノードリストにマルチキャストする、
・複製先ノードリストのうちの任意数のストレージノードに発行し伝搬させる
等、様々な手法で行われる。
【００９６】
そして、最後に、必要であれば、複製処理の完了を待った後に、データアクセス手段１０３に複製終了の通知を発行する（ステップＳ２０５）。
【００９７】
ステップＳ２０５は、図５のステップＳ１０５に関して説明した通り、分散ストレージシステムの動作ポリシーにしたがって行われるステップであり、複製処理の完了を待ってもよい。あるいは、複製処理の完了を待たないで、ＰＵＴ処理を完了するようにしてもよい。
【００９８】
＜グループごとの複製先の算出手順＞
図７は、図６の複製先算出フロー（ステップＳ２０３）における複製先算出の手順を示す流れ図である。
【００９９】
ストレージノードのアクセスノード算出手段１０７は、ルーティング情報記憶部１０８からルーティング情報、ノード環境情報記憶部１０９から状態情報を取得する（図７のステップＳ３０１）。ここで、ルーティング情報は、ストレージノードの名称等のストレージノードのハッシュ値を求めるための情報および、そのノードに対してアクセスするための情報（ＩＰアドレスとポート番号等）である。
【０１００】
ノード状態情報には、システムの動作状態（例えば、Ａ動作状態であるか、Ｂ動作状態であるか等）と、状態毎のデータの複製数（冗長度）の情報が含まれる。
【０１０１】
次に、ルーティング情報を用いて構築したハッシュリングを用いて、現在のストレージノード、最初は自身のストレージノード（クライアント２からのデータＰＵＴ命令を受け取ったストレージノード）から時計回りに隣接したストレージノードを一つ取得する（ステップＳ３０２）。
【０１０２】
なお、ハッシュリング上での隣接ストレージノードを反時計回りに算出してもよいことは勿論である。なお、ハッシュリングは、分散ストレージシステムに参加するストレージノードの構成が変わらない限り、何回でも使い回すことも可能である。このため、予めアクセスノード算出手段１０７で事前に作成しておいてもよい（この場合、ステップＳ３０１の処理はスキップされる）。
【０１０３】
次に、取得した隣接ストレージノードの所属グループを識別する（ステップＳ３０３）。ストレージノードの所属グループの識別にあたり、ノード環境情報記憶部１０９に、グループ識別のための情報（例えば、ストレージノード１１はグループＣに属する等の情報を管理する管理テーブル）を保持しておき、ノード環境情報記憶部１０９から所属グループを識別するようにしてもよい。あるいは、予めストレージノードの名称からグループが識別できるような形を取ってもよい。例えばストレージノード１１の名称を「１１Ｃ」等として、末尾をグループ名「Ｃ」とし、ストレージノード１１の所属グループはＣと識別する。
【０１０４】
次に、所属グループの複製先のノード数が、該所属グループに対応して指定されているデータ複製数（表１の冗長度）に達しているか判定する（ステップＳ３０４）。なお、ステップＳ３０４における所属グループはステップＳ３０３で識別された隣接ストレージノードの所属グループに対応する。
【０１０５】
ステップＳ３０４の判定の結果、所属グループの複製先のノード数が、該所属グループに対応して指定されているデータ複製数に達している場合には、ステップＳ３０２に進む。その際、前回のステップＳ３０２で取得された隣接ストレージノードが、現在のストレージノードに更新され、現在のストレージノードの隣接ストレージノードが取得される。
【０１０６】
一方、ステップＳ３０４において、複製先ノードリストのノードの数が、所属グループの指定複製数に達していない場合、ステップＳ３０２で取得した隣接ストレージノードを複製先ノードリストに追加する（ステップＳ３０５）。この結果、複製先ノードリストのノード数は１つ増加する。なお、複製先ノードリストは、例えば図６の複製先算出フロー（ステップＳ２０３）の読み出し前に空にリセットされる。
【０１０７】
つづいてステップＳ３０６において、全ての所属グループに対して、必要な複製数の複製先が発見されたか否かを確認する。全ての所属グループに対して、必要な複製数の複製先が発見されていない場合、ステップＳ３０２に戻る。その際、前回のステップＳ３０２で取得された隣接ストレージノードが、現在のストレージノードに更新され、ハッシュリング上の次の隣接ストレージノードを辿ることになる。
【０１０８】
ステップＳ３０６の判定の結果、全ての所属グループに対して、必要な複製数の複製先が発見された場合、複製先ノードリストを、複製命令発行手段１０６に送る（ステップＳ３０７）。
【０１０９】
以下、図３のハッシュリングを参照して動作を説明する。最初の現在のストレージノードは、クライアント２からのデータＰＵＴ命令を受け取ったストレージノードである。ステップＳ３０２で隣接ストレージノード１１を取得する。ステップＳ３０３で隣接ストレージノード１１の所属グループをＣと識別する。ステップＳ３０４において、複製先ノードの数は現在０であり（リセット状態であり複製先ノードリストは空）、所属グループＣの指定複製数２に達していないため、ステップＳ３０５で、複製先ノードリストに当該隣接ストレージノード１１を追加する。ステップＳ３０６において、全ての所属グループに対して、必要な複製数の複製先が発見されていないものと判定される。その結果、再び、ステップＳ３０２の処理が行われる。ステップＳ３０２では、隣接ストレージノード１１（図３）を現在のストレージノードとし、現在のストレージノードの時計回りに隣に位置するストレージノード１２（図３）を隣接ストレージノードとして取得する。ここで、ステップＳ３０３において、当該隣接ストレージノード１２の所属グループがＣであると判定されたとする。ステップＳ３０４の判定では、所属グループＣの複製先ノードの数は１つであり、所属グループＣの指定複製数２に達していないため、ステップＳ３０５で、複製先ノードリストに当該隣接ストレージノード１２を追加する。
【０１１０】
この結果、複製先ノードリストにおいて、所属グループＣに関するノード数は２となり、ステップＳ３０６の判定の結果、所属グループＣについては、必要な複製数の複製先は発見されたが、他の所属グループに対して必要な複製数の複製先は発見されていないことになる。このため、再びステップＳ３０２の処理に戻り、当該隣接ストレージノード１２（図３）を現在のストレージノードとして、現在のストレージノードの時計回りに隣に位置するストレージノード１３（図３）を隣接ストレージノードとして取得する。
【０１１１】
ステップＳ３０２で取得した隣接ノードの所属グループがＣの場合、ステップＳ３０４の判定で、所属グループＣは必要な複製数に達しているため、ステップＳ３０２に戻る。当該隣接ストレージノードを現在のストレージノードとして次の隣接ストレージノードを取得する。この隣接ストレージノードが例えばグループＢの場合、ステップＳ３０４、Ｓ３０５、Ｓ３０６、Ｓ３０２、Ｓ３０２の処理を繰り返し、複製ノードリストにノードを追加し、所属グループＣと同様にして、所属グループＢの指定複製数４に対応した複製先を確保する。
【０１１２】
なお、表１の場合、前述したように、状態Ｃとして動作するストレージノードは、状態Ａの場合にも動作する。すなわち、グループＣのストレージノードはグループＡにも属する。このため、ハッシュリング（ハッシュリングのノード数は１００）を辿り、グループＣに対して、複製数が２個の複製先が決定されたのち、さらにステップＳ３０２〜Ｓ３０６の処理を繰り返し、４個の複製先を複製先ノードリストに追加し、合計６個の複製先が決定された場合、所属グループＡとＣに対して必要な複製数が発見されたことになる。
【０１１３】
ステップＳ３０６の判定で、ハッシュリング上のノードが所属するノードの全ての所属グループに対してそれぞれ必要な複製数を発見した場合、複製先ストレージノードリストを、複製命令発行手段１０６に送る（ステップＳ３０７）。
【０１１４】
なお、実装の如何によっては、図７のフローチャートにおいて、ステップＳ３０２のハッシュノード上の隣接ノードの取得処理において、隣接ノードを求める際の基準となる現在のストレージノードが一番目のストレージノードに戻った場合（すなわち、ハッシュリング上のストレージノードの隣接ノードの探索がハッシュリング上を一巡した場合）、ステップＳ３０７に移行するようにしてもよい。
【０１１５】
複製命令発行手段１０６では、複製先ノードリストに対して複製命令を発行する（図６のＳ２０４）。
【０１１６】
本実施例の変形例として、グループに対応してデータの複製先を決定しておき、クライアント２からのデータＰＵＴ命令を受け取ったストレージノードは、データの複製作成にあたり、ハッシュリング上のストレージノードが所属するグループに対応した隣接ストレージノードに複製命令を発行し、複製先ストレージノードが該所属グループに対応して規定されるデータ複製数に達成したか否かを確認し、複製先のストレージノードが所属グループに対応して規定されるデータ複製数に達成していなければ、更にハッシュリング上の所属グループに対応した隣接ストレージノードに複製命令を発行するようにしてもよい。複製先のストレージノードが所属グループに対応して規定されるデータ複製数に達成していれば、複製処理を終了する。
【０１１７】
本実施例において、省電力のために、動作ノード数を減らす（停止させる）場合においても、大量のデータ複製を必要としない。ハッシュリング上のストレージノードが所属するグループの全てに対して、各グループ毎の指定複製数分、データを複製することで、システム動作状態の切替時におけるグループの切替にあたり、大量のデータ複製の発生を抑止し、場合によっては、データ複製は不要とされる。
【０１１８】
省電力のために、動作ノード数を減らす（停止させる）場合として、表１の状態Ａから状態Ｃへの切り替えについて説明する。状態ＡからＣへの切り替えで停止させる９００ノードは予め決められたノードが停止し、Ｃグループに最低限２つの複製をもっていることを保証するように複製が行われる。このため、状態Ａから状態Ｃに切り替えると、Ｃグループの１００ノードの中２つに必ず複製が存在する。例えば、ハッシュリング上にマップされた状態Ａの１０００個のノードを、１０個おきに間引いて状態Ｃとした場合、一番目のストレージノード１０（これがＣに含まれるとすると）に置くべきデータはストレージノード１０と２０に格納される。状態Ａ→状態Ｃに移行する場合、ストレージノード１１〜１９（２１〜２９、３１〜３９、４１〜４９、．．．，）は停止される。例えば状態Ａのときストレージノード１３に置くべきデータは、状態Ｃではストレージノード２０と３０に複製が置かれることが保証される（すなわち、状態Ａのとき１つ目のデータ（プライマリデータ）がストレージノード１１〜１９に置かれるべきデータは、いずれも、状態Ｃで動作する時、２のデータが置かれることを保証するため、ストレージノード２０と３０に置かれる）。
【０１１９】
また、本実施例において、ノード障害等の発生により、障害ノードを除去した場合においても、大量のデータ複製を必要としない。任意の方法でノード障害を検知し、障害が起きたノードが保持しているデータを持っているノード（非特許文献３の方法であればハッシュ隣接ノード）に通知し、ノード障害によりデータの冗長数が減った分だけ、さらに、隣接ノードへのデータの複製が行われる。以下に、データの耐障害性について、比較例と本実施例とについて説明する。
【０１２０】
＜データの耐障害性：比較例１＞
コンシステント・ハッシング法（データ複製を持たない）の場合、単純なノードの除去は可能であるが、データの耐障害性はない。ただし、各ストレージノードが、データをキャッシュに格納して利用する場合、マスタデータを格納したデータベース等が存在する。データはマスタデータベースにアクセスすれば再度取得することができるため、ノード除去は、システム全体としては、必ずしも、データ障害とはならない。障害復旧はマスタデータベースにアクセスして、除去されたノードが保持しているデータを再度コンシステント・ハッシングによりストレージノードにＰＵＴする。ただし、ストレージノードの除去により、ストレージノードが持っていたキャッシュに該当するデータは、マスタデータベースに対するアクセスに切り替えられるため、マスタデータベースに対する負荷が増大する。
【０１２１】
＜データの耐障害性：比較例２＞
非特許文献３等に記載される複製を持ったコンシステント・ハッシング法の場合、データの耐障害性はあるものの、同時に多数のノードが除去されてしまうと失われるデータが出現する可能性がある。すなわち、ノード障害が起きたとき、障害ノード数がデータの冗長数未満であれば、何もしなくても、クライアントは、データに引き続きアクセスできる。しかし、障害ノードが保持していたデータについてはその冗長数が減少する。このため、冗長数を元に戻す復旧処理が必要とされる。データの冗長数を元に戻す復旧処理は、ノード障害を検知し、障害が起きたノードが保持しているデータを冗長保持するストレージノードに対してデータの複製を命令し、さらハッシュリング上における隣接のストレージノードにデータを複製することになる。
【０１２２】
＜データの耐障害性：本発明＞
本発明によれば、データの耐障害性を具備する。予め決められたルールでの一斉停止であれば、ノード障害時に、データは失われることはない。ただし、予め決められたルールに従ってノードを除去するのではなく、例えばランダムに多数のストレージノードを選択して同時に除去すると、データが失われる可能性がある。本実施例においても、ノード障害発生時、データの冗長数を復旧する処理が行われる。ノード障害が検知された場合、データ復旧処理において、障害が起きたストレージノードが持っているデータが、当該ストレージノードが所属するグループの全てのグループに関して、グループ毎のデータ複製数（冗長数）の条件を満たしているか否か確認する。この確認作業を行うノードは、リング上の任意のノードであってよい。
【０１２３】
当該ストレージノードが所属するグループの全てのグループに関して、グループ毎のデータ複製数（冗長数）の条件を満たしていないグループが１つでもある場合、当該グループのデータ複製数（冗長数）の条件を満たすように、複製先ストレージノードを算出する。この算出手順は、図７のフローチャートと同様の手順で行われる。
【０１２４】
複製先のストレージノード（複製先ノードリスト）が決まると、該複製先のストレージノードへのデータ複製を行うように指示する命令を、当該複製データを持っているストレージノードのいずれかに対して送信する。本実施例によれば、グループ毎にデータ複製数が規定されており、グループに対して規定された複製数分、データの複製が存在するか確認し、不足する場合、複製を行う。このため、ノード障害時にも、動作状態（グループ）の切替を行う場合、データの耐障害性は保証される。
【産業上の利用可能性】
【０１２５】
本発明によれば、分散ストレージシステム、分散キャッシュシステムといった用途に適用できる。また、これらを用いたコンピュータシステム全般といった用途にも適用可能である。【０１２６】
なお、上記非特許文献の各開示を、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素の多様な組み合わせないし選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【符号の説明】
【０１２７】
１  ストレージノード
２  クライアント
３  動作状態指定手段
１０〜１９  ストレージノード
２１  アクセスノード算出手段
２２  ルーティング情報記憶部
２３  アクセス手段
１０１  アクセス要求受信手段
１０２  アクセス要求処理手段
１０３  データアクセス手段
１０４  データ記憶部
１０５  複製命令受信手段
１０６  複製命令発行手段
１０７  アクセスノード算出手段
１０８  ルーティング情報記憶部
１０９  ノード環境情報記憶部
【図１】
0005556816.tif 000003
【図２】
0005556816.tif 000004
【図３】
0005556816.tif 000005
【図４】
0005556816.tif 000006
【図５】
0005556816.tif 000007
【図６】
0005556816.tif 000008
【図７】
0005556816.tif 000009