(57)【要約】【課題】データ配置をユーザの要件に基づいて調整しつつ、システム全体としては自律負荷分散制御ができる、分散ストレージシステムを提供する。【解決手段】本発明による分散ストレージシステムは、データを保持するための記憶手段を備える複数の構成ノードがネットワークを介して接続されてなる。各構成ノードは、それぞれ論理的に接続された任意の数の論理的接続先ノードに対しデータを転送するデータ転送手段と、前記記憶手段のデータ保持状態情報及び前記任意の数の論理的接続先ノードと構成ノード自身の負荷情報を負荷状態として取得する状態取得手段と、取得した負荷状態から転送すべきデータ量を転送先ノード毎に計算する制御内容計算手段と、外部に転送しないデータの条件を保持する転送除外ルールを格納する転送除外ルール保持手段と、計算された転送すべきデータ量から前記転送除外ルールに該当しない転送データを選択するデータ選択／ルールチェック手段と、を備える。【選択図】    図３
2014032578.tif 000002
【特許請求の範囲】
【請求項１】
データを保持するための記憶手段を備える複数の構成ノードがネットワークを介して接続された分散ストレージシステムであって、
各構成ノードが、それぞれ論理的に接続された任意の数の論理的接続先ノードに対しデータを転送するデータ転送手段と、
前記記憶手段のデータ保持状態情報及び前記任意の数の論理的接続先ノードと構成ノード自身の負荷情報を負荷状態として取得する状態取得手段と、
取得した負荷状態から転送すべきデータ量を転送先ノード毎に計算する制御内容計算手段と、
外部に転送しないデータの条件を保持する転送除外ルールを格納する転送除外ルール保持手段と、
計算された転送すべきデータ量から前記転送除外ルールに該当しない転送データを選択するデータ選択／ルールチェック手段と、
を備えたことを特徴とする分散ストレージシステム。
【請求項２】
前記各構成ノードが、それぞれ自身以外の構成ノードからの転送データを受信し前記記憶手段へ保持するデータ受信手段と、
前記複数の構成ノードの負荷情報を取得し、前記状態取得手段と前記任意の数の論理的接続先ノードに送信する負荷監視手段と、をさらに備えることを特徴とする請求項１に記載の分散ストレージシステム。
【請求項３】
単一あるいは複数の構成ノードの前記転送除外ルール保持手段に対し、任意のデータに対する転送除外条件を付与するルール更新手段を更に備えることを特徴とする請求項１または２に記載の分散ストレージシステム。
【請求項４】
単一あるいは複数の構成ノードの前記転送除外ルール保持手段に対して、前記任意のデータに対する転送除外条件を付与されたときに、指定の構成ノードと同時に被災しない構成ノードを１つあるいは複数選び、その選んだ構成ノードに同一の転送除外条件を付与することを特徴とする請求項３に記載の分散ストレージシステム。
【請求項５】
前記指定の構成ノードと同時に被災しない構成ノードの条件として、一定距離以上物理的距離が離れている条件を含むことを特徴とする請求項４に記載の分散ストレージシステム。
【請求項６】
前記指定の構成ノードと同時に被災しない構成ノードの条件として、電力供給源が別系統である条件を含むことを特徴とする請求項４に記載の分散ストレージシステム。
【請求項７】
単一あるいは複数の構成ノードの前記転送除外ルール保持手段に対し、前記任意のデータに対する転送除外条件を付与された際に、条件を付与された構成ノードの論理的接合形態を変更することを特徴とする請求項３に記載の分散ストレージシステム。
【請求項８】
データを保持するための記憶手段を備える複数の構成ノードがネットワークを介して接続された分散ストレージシステムにおけるデータ配置制御方法であって、
各構成ノードは、それぞれ外部に転送しないデータの条件を保持する転送除外ルールをあらかじめ転送除外ルール保持手段に格納しており、
各構成ノードはまた、
それぞれ論理的に接続された任意の数の論理的接続先ノードに対しデータを転送するステップと、
前記記憶手段のデータ保持状態情報及び前記任意の数の論理的接続先ノードと構成ノード自身の負荷情報を負荷状態として取得するステップと、
取得した負荷状態から転送すべきデータ量を転送先ノード毎に計算するステップと、
計算された転送すべきデータ量から前記転送除外ルールに該当しない転送データを選択するステップと、
を実行することを特徴とする分散ストレージデータ配置制御方法。
【請求項９】
前記各構成ノードは更に、単一あるいは複数の構成ノードの前記転送除外ルール保持手段に対し、任意のデータに対する転送除外条件を付与するステップを実行することを特徴とする請求項８に記載の分散ストレージデータ配置制御方法。
【請求項１０】
データを保持するための記憶手段を備える複数の構成ノードがネットワークを介して接続された分散ストレージシステムであって各構成ノードは、それぞれ外部に転送しないデータの条件を保持する転送除外ルールをあらかじめ転送除外ルール保持手段に格納している分散ストレージシステムに適用されるデータ配置制御用プログラムであって、
各構成ノードのコンピュータに、論理的に接続された任意の数の論理的接続先ノードに対しデータを転送するステップと、
前記記憶手段のデータ保持状態情報及び前記任意の数の論理的接続先ノードと構成ノード自身の負荷情報を負荷状態として取得するステップと、
取得した負荷状態から転送すべきデータ量を転送先ノード毎に計算するステップと、
計算された転送すべきデータ量から前記転送除外ルールに該当しない転送データを選択するステップと、
を実行させための分散ストレージデータ配置制御用プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は分散ストレージシステム、分散ストレージデータ配置制御方法及び分散ストレージデータ配置制御用プログラムに関し、データ配置に関する条件を保護することができる分散ストレージシステム、分散ストレージデータ配置制御方法及び分散ストレージデータ配置制御用プログラムに関する。
【背景技術】
【０００２】
分散ストレージシステムは、ネットワークを介して接続された多数の計算機を有し、これらの計算機のハードディスクドライブ（ＨＤＤ：Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）、メモリ等を用いてデータの格納及びデータの提供を行う。分散ストレージシステムでは、いずれの計算機にデータを配置し、いずれの計算機によってデータを処理するのかを、ソフトウェアまたは特別なハードウェアが決定する。また、分散ストレージシステムの動作を動的に変更することにより、システム内のリソース使用量を調整するとともに、クライアント端末及びその利用者に対する性能を向上させることが要求される。
【０００３】
分散ストレージシステムにおいては、データは複数のストレージノード（以下、単に「ノード」という）に分散して格納されている。非特許文献１に記載された技術のように、複数のノードにデータの複製を保持することで高可用性を維持する分散ストレージシステムが知られている。また、遠隔地にデータの複製を配置することにより、災害などで分散システムの一部分にアクセス出来なくなってもサービスを継続させる技術が特許文献１に記載されている。また、広域分散ストレージシステムにおいて、データの複製を利用者の近くに配置することでアクセス性能を向上させることも特許文献２などに記載されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００６−１４６５８０号公報
【特許文献２】特開２００６−１７２２１７号公報
【非特許文献】
【０００５】
【非特許文献１】Giuseppe DeCandia， Deniz Hastorun， Madan Jampani， Gunavardhan Kakulapati， Avinash Lakshman， Alex Pilchin， Swaminathan Sivasubramanian， Peter Vosshall， and Werner Vogels. 2007. Dynamo: amazon's highly available key-value store. In Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles (SOSP '07). ACM， New York， NY， USA， 205-220. DOI=10.1145/1294261.1294281 http://doi.acm.org/10.1145/1294261.1294281
【発明の概要】
【発明が解決しようとする課題】
【０００６】
第１の問題点は、任意の既存の自律負荷分散アルゴリズムに基づいてデータ配置制御を行うことにより、データ配置をユーザやシステムの管理者の要件に応じて恣意的に調整することが難しい、ということである。その理由は、負荷分散アルゴリズムがユーザやシステムの管理者の要件を考慮せずに開発されていることがあるためである。そのため、既に実績がある負荷分散アルゴリズムに対して、システム管理者やユーザの要望に合わせてデータ配置調整をするためには、それらの負荷分散アルゴリズムの修正が必要になる。その修正作業には高度な技術的知見を必要としてしまうため、広く利用するシステムとしての応用は困難になってしまう。
【０００７】
例えば、災害対策などの理由のために、広域に複製データを分散配置する分散ストレージシステムにおいて、システムを構成している各ノードが自律分散的にデータの転送を行う事で、負荷分散を実現する制御アルゴリズムを動作させるものとする。その場合、負荷分散のために各ノードはデータをランダムに転送してしまうため、全ての複製データが地理的に近いノードに配置されたり、電力供給源が同一のエリア内のノードに格納されたり、あるいは同一ラックや同一ノードに格納されてしまうようなことが発生しうる。そのようなデータ配置状態になってしまうと、一部のエリアが被災した際にあるデータの全ての複製に対してアクセスが不可能になってしまうため、災害対策システムとして意味を成さなくなってしまう。
【０００８】
また、地理的に分散された拠点毎にデータセンタ（分散ストレージシステムの一部の構成ノードを動作させる）を置き、ユーザのファイルを格納するようなユースケースの場合、例えばあるユーザが拠点ＡとＢにおいて主にファイルアクセスを行う場合には、ユーザのファイルを拠点ＡとＢに複製を格納することがアクセス性能として有利となる。しかし、ランダムにデータを転送する自律負荷分散アルゴリズムにおいては、そのような配置調整は困難である。
【０００９】
第２の問題点は、災害対策やユーザへのアクセス性能向上に向けた要件を満たすためのデータ配置状態へ移行するまでに時間が掛かる、ということにある。これは、本発明で対象とするような、構成ノードが限られた論理的な接合先ノードとの負荷監視だけで、自律的にデータの転送をしあう自律負荷分散システムにおいては、データが確率的に伝搬されて転送されるのを待つしかないためである。
【００１０】
本発明の課題は、データ配置をユーザの要件に基づいて調整しつつ、システム全体としては自律負荷分散制御ができる、分散ストレージシステムを提供することにある。
【課題を解決するための手段】
【００１１】
本発明の第１の態様によれば、データを保持するための記憶手段を備える複数の構成ノードがネットワークを介して接続された分散ストレージシステムであって、各構成ノードが、それぞれ論理的に接続された任意の数の論理的接続先ノードに対しデータを転送するデータ転送手段と、前記記憶手段のデータ保持状態情報及び前記任意の数の論理的接続先ノードと構成ノード自身の負荷情報を負荷状態として取得する状態取得手段と、取得した負荷状態から転送すべきデータ量を転送先ノード毎に計算する制御内容計算手段と、外部に転送しないデータの条件を保持する転送除外ルールを格納する転送除外ルール保持手段と、計算された転送すべきデータ量から前記転送除外ルールに該当しない転送データを選択するデータ選択／ルールチェック手段と、を備えたことを特徴とする分散ストレージシステムが提供される。
【００１２】
以上のような構成を採用し、転送データを決定する際に転送除外ルールに含まれないデータを選択して、転送除外ルールを満たすデータを構成ノード内に格納させ続けるように動作することにより、本発明の課題を達成することができる。
【００１３】
本発明の第２の態様によれば、データを保持するための記憶手段を備える複数の構成ノードがネットワークを介して接続された分散ストレージシステムにおけるデータ配置制御方法であって、各構成ノードは、それぞれ外部に転送しないデータの条件を保持する転送除外ルールをあらかじめ転送除外ルール保持手段に格納しており、各構成ノードはまた、それぞれ論理的に接続された任意の数の論理的接続先ノードに対しデータを転送するステップと、前記記憶手段のデータ保持状態情報及び前記任意の数の論理的接続先ノードと構成ノード自身の負荷情報を負荷状態として取得するステップと、取得した負荷状態から転送すべきデータ量を転送先ノード毎に計算するステップと、計算された転送すべきデータ量から前記転送除外ルールに該当しない転送データを選択するステップと、を実行することを特徴とする分散ストレージデータ配置制御方法が提供される。
【００１４】
本発明の第３の態様によれば、データを保持するための記憶手段を備える複数の構成ノードがネットワークを介して接続された分散ストレージシステムであって各構成ノードは、それぞれ外部に転送しないデータの条件を保持する転送除外ルールをあらかじめ転送除外ルール保持手段に格納している分散ストレージシステムに適用されるデータ配置制御用プログラムであって、各構成ノードのコンピュータに、論理的に接続された任意の数の論理的接続先ノードに対しデータを転送するステップと、前記記憶手段のデータ保持状態情報及び前記任意の数の論理的接続先ノードと構成ノード自身の負荷情報を負荷状態として取得するステップと、取得した負荷状態から転送すべきデータ量を転送先ノード毎に計算するステップと、計算された転送すべきデータ量から前記転送除外ルールに該当しない転送データを選択するステップと、を実行させための分散ストレージデータ配置制御用プログラムが提供される。
【発明の効果】
【００１５】
本発明の第１の効果は、ユーザの要件（災害対策やアクセス性能向上等）に基づいてデータの配置調整を、それを考慮していない自律負荷分散制御アルゴリズム上で実現できることにある。その理由は、各構成ノードが転送データを選択する際に、転送除外条件に含まれないデータを選んで転送することで、配置調整に必要なデータを構成ノードの外部へ転送させないためである。
【図面の簡単な説明】
【００１６】
【図１】本発明の第１の実施の形態の構成の概要を示すブロック図である。
【図２】図１に示された第１の実施の形態における、論理的なノード接続形態を示すブロック図である。
【図３】図１に示された第１の実施の形態の構成のうち、構成ノード１００を中心として制御手段２の構成を詳細に示したブロック図である。
【図４】図３に示された制御内容計算手段２２の実施例における評価関数について説明するための図である。
【図５】図３に示された制御内容計算手段２２の実施例における起動停止判断の指標について説明するための図である。
【図６】本発明の第１の実施の形態の動作を説明するための流れ図である。
【図７】本発明の第１の実施の形態の動作のうち、転送データ選択処理動作を説明するための流れ図である。
【図８】本発明の第２の実施の形態の構成を示すブロック図である。
【図９】本発明の第３の実施の形態の構成を示すブロック図である。
【発明を実施するための形態】
【００１７】
次に、本発明を実施するための形態について図面を参照して詳細に説明する。
【００１８】
図１は本発明の第１の実施の形態におけるシステムの概要を示す構成図である。図１を参照すると、本発明の第１の実施の形態は、ネットワーク２００によって結合された構成ノード１００〜１０８から構成される。以下では、構成ノード１０Ｘと記載する場合、Ｘは０から８の値を取り得ることを意味する。構成ノードの数は図１では９個であるが、任意の複数の数となることは言うまでもない。また、複数の構成ノードの一部は離れた拠点（例えばデータセンタ）にあることを前提とする。災害対策を目的とする場合には、任意の１つ以上の拠点がその他の拠点と同時に被災しない充分離れた場所や、電力供給源（例えば発電所）が別となる場所に設置されることとする。しかし、災害対策以外の目的（例えば拠点間のファイル共有システム）の場合には、必ずしもこのように限定されない。
【００１９】
構成ノード１０Ｘ（すなわち１００〜１０８）は、分散ストレージシステムを構成するストレージノードである。構成ノード１０Ｘは、データを保持するための記憶装置（例えばＨＤＤ、半導体メモリ等）と、ストレージ機能を実現するための演算装置（例えばＣＰＵ：Central Processing Unit）を備える計算機（コンピュータ）によって実現される。
【００２０】
構成ノード１０Ｘは、データストア（記憶手段）１と、ＣＰＵ等により実現される制御手段２と、データ受信手段３と、負荷監視手段４とを備える。データストア１は分散ストレージシステムに格納されるデータを格納する機能を果たす。データストア１は、構成ノード１０Ｘが保持する記憶装置と、それに対する記憶処理を実現するソフトウェアによって実現され、構成ノードの計算機リソースによって実現される。制御手段２は、それぞれの構成ノード１０Ｘのデータストア１に格納されているデータのうち、任意のデータを別のノードに配置制御（マイグレーションや複製数の増加）を行う。データ受信手段３は、制御手段２によって行われる配置制御処理によって転送される、自身以外の構成ノードからの転送データを受信しデータストア１へ保持する。負荷監視手段４は、構成ノード１０Ｘのノード負荷情報（例として、データアクセス量、構成ノード１０ＸのＣＰＵ利用率やＩＯ（Input-Output）量などの計算機負荷量）を既存の監視ソフトウェアなどによって取得し、制御手段２と、自身以外の構成ノード１０Ｘの一部に送信する機能を果たす。
【００２１】
ネットワーク２００は、構成ノード１００〜１０８間を接続し、データ及び制御メッセージをやり取りするために用いられる。ネットワーク２００は、１拠点内のネットワーク（例えばデータセンタ内のネットワーク）だけでなく、複数の拠点間を接続する広域ネットワークの双方を含む。ネットワーク２００は、例えば、Ethernet（登録商標）、Fibre ChannelやFCoE(Fibre Channel over Ethernet、InfiniBand、または、これらを利用するTCP/IP(Transmission Control Protocol/Internet Protocol)、RDMA（Remote Direct Memory Access）などの上位プロトコルにより実現されるが、実現方法としてはこれらに限られない。また、地理的に離れた拠点間を接続することもあり、インターネットや専用線により拠点間を接続することも可能である。
【００２２】
分散ストレージシステムに格納されるデータは、固定長または意味的に区切られたデータ断片（以下「オブジェクト」という）の集合として、構成ノード１０Ｘのそれぞれのデータストア１のいずれか１つまたは、複数に格納される。複数のノードに格納される場合には、オブジェクトの複製として格納される。分散ストレージシステムのクライアントは、オブジェクト単体あるいは集合に対して、一意の識別子（キー）によってアクセスする。各オブジェクトの他に、オブジェクトに基づいて計算された冗長符号情報が複製として他のノードに格納されるようにしてもよい。冗長符号情報は、ノード故障時において、データの消失を防ぐために用いられる。
【００２３】
オブジェクトの例として、例えば、ファイルシステムのファイル、ファイルと関連するメタデータの集合、関係データベースのタプルもしくはテーブル、オブジェクトデータベースのデータ、Ｋｅｙ−Ｖａｌｕｅデータ格納システムのＶａｌｕｅ、ＪＳＯＮ（Ｊａｖａ  Ｓｃｒｉｐｔ（登録商標）  Ｏｂｊｅｃｔ  Ｎｏｔａｔｉｏｎ）、ＢＳＯＮ（Ｂｉｎａｒｙ  ＪＳＯＮ）で記載されたドキュメント等が挙げられる。しかし、本発明におけるオブジェクトは、これらのオブジェクトに限られない。また、これらの例について、さらに固定長または意味的に区切ったデータ断片をデータストア１への格納単位としてもよい。
【００２４】
［制御手法の概要］
本発明の第１の実施の形態による分散ストレージデータ配置制御手法は、各構成ノード１０Ｘの制御手段２によってデータ転送の必要性と、データ転送量及び転送先を決定し実行する手法である。各構成ノード１０Ｘは、図１に示した通り、ネットワークを介して結合されているため、どのノードに対してもデータを転送することは可能である。ただ、全てのノードを転送先にしてデータ転送量を計算することは計算コストが大きくなるため、各構成ノードを任意のトポロジーで論理的に結合し、その論理的な結合先のノードだけを各制御手段２における転送先候補ノードとし、その転送先候補ノードに対するデータの転送必要性可否判断やデータ転送量及び転送先を算出するための計算処理を行う事で、計算量を削減する。
【００２５】
各構成ノード１０Ｘの論理的な結合形式としては、メッシュ型、ツリー型、フルコネクト型、スター型、キューブ型などや、これら複数の結合方式を階層的に接続したり、複合的に組み合わせたりする形式がある。本実施の形態としては、説明を簡略化するために、図２に示すような２次元メッシュ構造で接続されることとする。この場合、構成ノード１００における論理的な接続ノード（転送先候補ノード）は、構成ノード１０１及び１０３である。この接続形態に関する情報は、論理的接続情報として各構成ノード１０Ｘが保持しており、変更された場合には各構成ノードに通知されるものとする。
【００２６】
また、論理的な結合形式については自由であるが、基本的には近隣の構成ノードと多く接続し、離れた構成ノードとは限られた接続数となるトポロジー構成を取ることが基本である（例えばツリー構造）。これは、後述する制御内容計算手段２２（図３）の制御アルゴリズムに依存するが、結合された構成ノード間はデータの転送が多く起きるため、遠隔地のノードと接続されるとデータ転送ボトルネックが大きくなってしまい、ストレージ性能に問題を引き起こすためである。
【００２７】
［構成］
図３は、第１の実施の形態の構成のうち、構成ノード１００を中心として、制御手段２の構成をより詳細に示したブロック図である。制御手段２は、状態取得手段２１、制御内容計算手段２２、データ選択／ルールチェック手段２３、データ移動制御手段（データ転送手段）２４、転送除外ルール保持手段２５、論理的接合形態管理手段２６、ルール更新手段５から構成される。それぞれの手段は、構成ノード１０Ｘを実現するハードウェア装置を用いたソフトウェアとして動作する。また、構成ノード１０Ｘ上の特殊なハードウェアがその機能を果たしても良い。
【００２８】
構成ノード１００の状態取得手段２１は、データストア１のデータ保持状態情報（例えば、データ保持量、種類）及び構成ノード１００とその論理的接続先ノード（図３の場合、構成ノード１０１及び１０３）の負荷情報を負荷状態として構成ノード１００、１０１、１０３の負荷監視手段４から取得する。このデータ保持状態情報及び負荷情報の詳細内容は、制御内容計算手段２２のアルゴリズムによって決定される。また、この論理的接続先ノードは、論理的接合形態管理手段２６から取得する。
【００２９】
制御内容計算手段２２は、以下に説明するアルゴリズムに基づいて、状態取得手段２１が取得したデータ保持状態情報及び負荷情報を用い、転送すべきデータ量を転送先候補ノード毎に算出し決定する機能を果たす。
【００３０】
まず、図４のような、データストア１と関係する評価関数を導入する。この場合、横軸λはデータストア１の負荷量に相当する。縦軸ｆｉ（λ）は、何らかの効率または利潤に関わる指標である。データストア１の場合、レスポンス効率、エネルギー効率に関する指標を設定する。レスポンス効率によれば、系全体のレスポンスを好適にし、エネルギー効率によれば系全体のエネルギー効率を好適にすることができる。この効率に関わる評価関数を凸関数で表す。凸関数を使用するのも本制御手法の特徴である。図４のような、上に凸な関数を凹関数と呼び、下に凸な関数を凸関数と呼ぶこともあるが、ここでは、関数の性質上で区別する表現を採用し、凹関数も凸関数と表現することにする。
【００３１】
評価関数が凸関数である要素を連携させて、全体で最適化（各要素の評価関数の値の総和が最大となる状態)する問題は、「凸計画問題」として知られており、各要素の動作レベルにおける評価関数の微分値が等しい状況で最適化が達成されることが数学的に明らかにされている。本実施の形態はこの原理を応用している。本実施の形態において、評価関数として凸関数を使った理由がここにある。
【００３２】
この原理を勘案し、各要素の状態変化（本実施の形態のサーバのケースでは負荷分散）を以下の式（１）に従い制御する。
【数１】
2014032578.tif 000003
【００３３】
ここで、λiはデータストア１の負荷量であり、K1は状態変更のゲインに相当する係数である。この制御をかけることで、各要素は評価関数の微分値ｄｆｉ／ｄλiを等しくするように状態を変更しようとする。これは「凸計画問題」のところで説明したように、全体利潤を最大化するポイントに各要素の状態（負荷量）を制御するのと等価である。つまり、上記式（１）に基づく制御により、評価関数の縦軸で設定された効率が系全体として最大化される。kは要素iに隣接する要素の番号（図２の構成で論理的に接合されている場合には、要素iが構成ノード１００の場合、構成ノード１０１、１０３）を意味する。このように隣接要素が複数個有る場合は、順次、上記式（１）に基づく制御を繰り返せばよい。
【００３４】
上記までの説明の手法で、負荷の配置の問題をリアルタイムに解くことができるが、場合によっては、データストア１（及び構成ノード１０Ｘ）が停止していた方が、効率の上がる場合がある。また、停止していたデータストア１（構成ノード１０Ｘ）を起動したほうが、効率の上がる場合もある。上記式（１）だけでは、この起動停止の判断ができないので、以下の指標を使って、データストア１の起動停止の判断を行う。
【００３５】
まず、要素自身と、その要素に隣接するノードの評価関数間に、ある指標を定義する。図５は、その評価関数を説明するための図である。図５において、負荷量λが０のときに、効率または利潤（縦軸）ｆｉ（λ）が負の値を取っている意味は、起動によりコストが発生することを意味している。縦軸を利潤と考えれば、運転（起動）しているにも関わらず、需要がなければ、運転コストが回収（需要家から集める金額）を上回り、利潤がマイナスになるというイメージである。評価関数の値が０になったところが、運転コストと回収が均衡した点であり、評価関数の値がプラスになるということは利益が発生している事を意味する。
【００３６】
ここで、ノードi（自身）のゼロクロス点をλ0,i、隣接ノードｊの評価関数における、ノードｉのゼロクロス点と同じ傾きの点をZij、隣接ノードｊの現在の負荷をλjとする。この場合、Zijは以下の式（２）で表すことができる。
【数２】
2014032578.tif 000004
【００３７】
そして、ここで以下の式（３）の指標Siを定義する。
【数３】
2014032578.tif 000005
【００３８】
この指標Siは、現在の隣接ノードの負荷（総和）が、自身のゼロクロス点よりどれだけ大きいかを意味している。もしノードiが停止しているとして、ノードiを起動すべき条件は、起動することでノードiがゼロクロス点以上の負荷を担当する状況にあるかどうかである。そうすれば利潤はマイナス（評価関数値が負）にならないため、ノードiを起動することで不利はない。指標Siはそれを数値化したものである。隣接ノードがノードiのゼロクロス点における評価関数微分値と等価なZijよりどれだけ負荷を担当しているかを示すのが式（３）の右辺第１項であり、それをゼロクロス点λ0,iで減算することで（右辺第２項）、自身のゼロクロス点以上の負荷が周りに存在しているかを示す指標となっている。指標Siが０より大きければ、ノードiを起動したときにいずれ隣接ノードが担当している負荷はノードiが担当することになり、かつノードiの担当負荷はゼロクロス点以上となる。逆に、指標Siが０より小さければ、ノードiが隣接ノードの担当負荷を新たに担っても、ゼロクロス点以下となり、ノードiの起動により利潤をマイナスにしてしまう。指標Siはこのようなものであり、指標Siの正負を見ることでノードiを起動すべきか停止すべきかがわかる。指標Siが負のときとは、その時点でノードiの負荷は評価関数が負の値をとる領域にあるということで、起動しているノードは評価関数が０以下になった時点で停止すると考えても良い。
【００３９】
以上のように、上記式（１）で各要素の状態変化を制御しながら、上記式（３）の指標Siをモニタすることで、リアルタイムにデータストア１の好適な負荷量の算出、及びノードを起動すべきか停止すべきかの判断をすることができる。これは従来のように予め予測シナリオでスケジューリングして制御していたものに比べ画期的なアルゴリズムとなっている。なぜなら、想定外の外乱や需給変化があってもリアルタイムに即応できるからである。
【００４０】
また、このアルゴリズムは、自律分散的に独立に動くので、どこかが故障したりしても、故障した要素からの信号が途絶えた分だけ、他の要素が自律的にリカバーするという動作を行う。また、突然要素を増やしたり、減らしたりしても、徐々に自律的に適正な動作に向かうことができる。つまり、外乱に対して、非常にロバストであり、また、要素の増減を自由にできるスケーラビリティを有している。
【００４１】
従来のシステムは、故障に対して無力であったり、様々なエラー用のシーケンスを用意したりしなければならなかった。また、勝手に要素（リソース）を増やしたり、減らしたりすればシステム全体の安定性が保たれるか保証はなく、そのたびにプログラム、処理を見直さなければならなかった。本実施の形態のアルゴリズムはこれらの問題を自律分散適応的な制御ですべて解決することができる。
【００４２】
データ選択/ルールチェック手段２３は、制御内容計算手段２２によって決定される、接続先毎のノード及び、転送すべきデータ量及びその転送先ノードの情報から、実際にデータを選択する。その際に、データ選択/ルールチェック手段２３は、転送除外ルール保持手段２５に格納されているルールを参照し、転送除外ルールとして登録されている条件に一致するデータを転送データとして選ばず、その他のデータから転送データを選択する。
【００４３】
データ移動制御手段２４は、データ選択/ルールチェック手段２３によって選択指定されたデータを、データストア１から取得し、転送先ノードに対してデータを転送する。転送先ノードのデータ受信手段３がそのデータを受信し、転送先ノードのデータストア１に反映する。
【００４４】
転送除外ルール保持手段２５は、構成ノード（ここでは構成ノード１００）に格納された際にその構成ノードから外部に転送しないデータの条件を保持するものであり、１つあるいは複数の条件を保持する。当然ながら、転送してもよい条件を格納し、条件に適合しないデータを転送不可にしてもよい。
【００４５】
[転送除外ルールの実施例]
制約ルールを保持する実施例としては、転送しないデータを示す識別子｛キー、ファイルパス及びファイル名、ID（オブジェクトやレコード毎に付与される識別子）｝のリスト、データに付与されるメタデータのリスト（例えばファイルの所有者、グループ名など）といったことが挙げられる。これらの情報をファイルやデータベースなどに記録しておくということが簡素な実装方式として考えられる。
【００４６】
論理的接合形態管理手段２６は、構成ノードの論理的接続先ノードについて保持管理し、要求に応答する手段である。構成ノードの論理的接合形態が図２に示すような形になっている場合、構成ノード１００の論理的接合形態管理手段２６は構成ノード１０１及び１０３を論理的接続先ノードとして応答する。論理的接合形態管理手段２６は、外部の任意の手段によって変更されてもよい。第１の実施の形態では、論理的接続先ノードは静的に決まっているためノード毎にあらかじめ決められた情報を応答すればよい。
【００４７】
論理的接合形態管理手段２６の実施例としては、データベースやファイルなどに各構成ノード自身の接続先ノードリスト（構成ノード１００であれば１０１と１０３を示す情報）を記録する、あるいは全ての結合関係（すなわち図２相当の情報）を各構成ノードに保持していてもよい。
【００４８】
ルール更新手段５は１つあるいは複数の構成ノード１０Ｘ上の転送除外ルール保持手段２５に保持されているルールを変更・更新・追加する手段である。構成ノード１つだけのルールを変更してもよいし、２つ以上あるいは全ての構成ノードのルールを変更しても良い。ルール更新手段５は任意の構成ノード１０Ｘ上で動作させても良いし、分散ストレージシステムの構成ノード以外のノードで動作しても良い（例えば、ファイルシステムのユーザが利用するパソコンなどであってもよい）。
【００４９】
ルール更新手段５は、ユーザやシステム管理者から例えば、構成ノード１００と１０８にユーザＡのデータを保持させたい場合に、構成ノード１００と１０８の転送除外ルール保持手段２５の除外ルールにユーザＡの保持データの情報を追加する。例えば、ファイルシステムを対象にする場合、メタデータの所有者がユーザＡを除外リストに追加する。
【００５０】
また、例えば構成ノード１００はユーザＡが利用する拠点の近隣にあるノードで、構成ノード１０８に複製を保持する理由は充分離れた拠点で災害対策用に離れた場所に複製を保持したい、というユースケースの場合には次のように動作してもよい。ユーザやシステム管理者は、構成ノード１００に除外設定を追加させる。それに対してルール更新手段５は、構成ノード１００と同時に被災しない拠点（地理的に十分離れた距離にある、あるいは電力供給が区分されている、または別のネットワーク経路を持つなど）にある構成ノード１０Ｘから１つ選んで構成ノード１０８にも同一の条件を追加する。この際、ルール更新手段５は構成ノードの位置（あるいは電力供給状態、システム構成状態）を認識しているものとしてよい。
【００５１】
また、あるデータに対して、構成ノード１００から構成ノード１０１、１０２以外のノードに転送してはならない、というような条件記述でもよい。この場合、転送先ノードが構成ノード１０３の場合には該当データは転送できないが、転送先ノードが構成ノード１０１の場合には転送が可能である。例えば、構成ノード１００〜１０２が同一の拠点に存在し、いずれか１つのノードに複製が１つ以上あれば目的を達成できる場合に、このような条件指定を行う。
【００５２】
[全体動作]
次に、図６、図７のフローチャートを参照して、第１の実施の形態の全体動作について詳細に説明する。図６は各構成ノード１０Ｘにおけるデータの転送制御処理フローである。このフローが定期的に実行されることによりシステムを安定的に負荷分散させ動作させる。図７は図６のステップＳ１０３を詳細に説明するフローチャートであり、ある転送先ノードに対し、実際に転送するデータ断片を選択する処理である。
【００５３】
まず、図３、図６を用いて基本的なデータ転送制御処理フローについて説明する。状態取得手段２１は、データストア１からデータの保持状態情報を取得すると共に、自身及び論理的接続先ノードである、構成ノード１００、１０１、１０３の負荷監視手段４から負荷情報を取得し、負荷状態として制御内容計算手段２２に渡す（ステップＳ１０１）。制御内容計算手段２２は、渡されたデータ保持状態情報と負荷情報を用いて、制御内容（転送先毎の転送データ量）を算出する（ステップＳ１０２）。ステップＳ１０２の具体的方法については制御内容計算手段２２の項に示す。
【００５４】
続いて、データ選択／ルールチェック手段２３は、転送除外ルール保持手段２５に格納されているルールに該当するデータ以外から、転送先ノード毎に転送データ断片を選択し、選択した転送データ断片を指定する情報をデータ移動制御手段２４に渡し、データ移動制御の実行を要求する（ステップＳ１０３）。ステップＳ１０３については詳細を図７のフローチャートによって後述する。
【００５５】
データ移動制御手段２４は、データ選択／ルールチェック手段２３からの転送データ断片を指定する情報に基づいてデータストア１から転送すべきデータ断片を取得し、転送先のデータ受信手段３へデータを転送する（ステップＳ１０４）。
【００５６】
[ステップＳ１０３における転送データ選択］
次に、図７を用いてデータ選択／ルールチェック手段２３によるステップＳ１０３の動作について説明する。前述したように、データ選択／ルールチェック手段２３は、制御内容計算手段２２によって決定された、接続先毎のノード、データ転送量及びその転送先ノードの情報から、データ転送量を満たす分のデータ断片を、状態取得手段２１を介してデータストア１から選ぶ（ステップＳ２０１）。例えば、決定されたデータ転送量がデータ断片１００個分に相当するのであれば、データ選択／ルールチェック手段２３はデータストア１に格納されているデータ断片を１００個選ぶ。選ぶ方法としてはランダムに選ぶ、FIFO（First in First out）順に選ぶ、FILO（First in Last out）順に選ぶ、など様々な方法が考えられるが、ここではどのような方法に基づいてもよい。
【００５７】
次に、データ選択／ルールチェック手段２３は、転送除外ルール保持手段２５から除外ルールを取り出す（ステップＳ２０２）。ステップＳ２０１とＳ２０２は独立して実行できるため、任意の順序で実行して良い。
【００５８】
データ選択／ルールチェック手段２３はさらに、ステップＳ２０２で取得した制約ルールと、ステップＳ２０１で選択した（転送候補となる）データ断片から、各データ断片が転送除外ルールに該当するかどうか判定する（ステップＳ２０３）。
【００５９】
データ選択／ルールチェック手段２３は次に、ステップＳ２０１で選択された転送候補データ断片全てが、ステップＳ２０３での判定で転送除外ルールに該当していないかどうか確認する（ステップＳ２０４）。転送候補データ断片全てが転送除外ルールに該当していない場合（ステップＳ２０４でＹＥＳの場合）、指定データ量の転送データ断片のリストアップが完了したことになるため、本処理は終了し、図６のステップＳ１０４に進む。
【００６０】
転送候補データ断片のうち、転送除外ルールに該当するデータがある場合（ステップＳ２０４でＮＯの場合）、データ選択／ルールチェック手段２３は、転送除外ルールに該当したデータ量分の新たなデータ断片を再度データストア１に格納されているデータ断片から選択する（ステップＳ２０５）。なお、転送除外ルールに該当しなかった転送候補データ断片はそのまま転送候補とする。ステップＳ２０５における、基本的な選択方法としてはステップＳ２０１と同様にしてよいが、以前に選択され、除外ルールに該当したデータ断片は選択候補から外すべきである。データ選択／ルールチェック手段２３は、新しい転送データ断片候補を選んだ後に、ステップＳ２０３に戻り再度のルール判定処理を行う。
【００６１】
また、この動作フローにおいてステップＳ２０１の時点で転送除外ルールを判断しながら転送候補データの選択をしてもよいことは言うまでもない。
【００６２】
［第２の実施の形態：論理的接合形態の変更］
次に、本発明による第２の実施の形態について説明する。第１の実施の形態では、各構成ノードに転送除外ルールを付与することで課題を達成した。しかし、これでは自律分散制御アルゴリズムによって該当データが偶然、対象構成ノードにデータが転送されてくるまで配置状態を満たすことが出来ない。この問題を解決するために、ルール更新手段５がルールを更新した時点において、構成ノードの接続先を増やす機構を導入する。
【００６３】
例えば、構成ノード１００にユーザＡのデータを外部に転送させない条件を追加した際に、ユーザＡのデータを構成ノード１００へ転送させる場合には、その論理的接続先ノード（図２においては構成ノード１０１及び１０３）からデータが転送されてくるのを待つ必要がある。このデータ転送の確率を上昇させるためには、論理的接続先ノードを増加させればよい。すなわち構成ノード１０２、１０４〜１０８のうち１つ以上の構成ノードを論理的接続先ノードとして追加すればよい。
【００６４】
なお、本発明で述べた制御アルゴリズムは、論理的接続先ノードが増加するほど計算コストが増加し、またネットワーク利用帯域も増加する傾向にあるため、論理的接続先ノードの追加はユーザの求める配置状態への移行への高速化と計算コストとのトレードオフである。従って、あらかじめ指定された時間を超えたら、元に戻す、という処理を入れることが望ましい。
【００６５】
また、データの配置状態への移行に求められる時間に応じて、増加させる接続先ノード数を変更してもよい。例えば、短時間でのデータ移行が必要であれば、接続先ノード数を増大させるようなインタフェースを備えても良い。
【００６６】
次に、図８を参照して、本発明の第２の実施の形態について説明する。図８に示す第２の実施の形態は、図３に示された第１の実施の形態とほぼ同じであるが、制御手段２における転送除外ルール保持手段２５が、ルール更新手段５からのルール更新要求に基づいて論理的接合形態管理手段２６の情報を変更する機能を持つ点が異なる。また、論理的接合形態管理手段２６は、その論理的接続先ノードの論理的接合形態管理手段２６に対しても更新を要求する必要がある。すなわち、図２の接続形態において、構成ノード１００と構成ノード１０８の結合を追加する際には、構成ノード１０８の論理的接合形態管理手段２６を変更する必要がある（但し、図８では矢印を省略している）。なお、必ずしも転送除外ルール保持手段２５を介して論理的接合形態管理手段２６を変更する必要はない。例えばルール更新手段５が直接変更するような構成を取っても良い。
【００６７】
［第３の実施の形態］
本発明の第３の実施の形態として、ユーザアクセスに対して自動的に転送除外ルールを追加する機構を付与した構成について説明する。第１の実施の形態においては、ルール更新手段５を用いてシステム管理者やユーザが、ユーザＡのアクセス先拠点（あるいは構成ノード）の情報に基づいて転送除外ルールを追加する必要がある。
【００６８】
本発明の第３の実施の形態では、あるユーザが分散ストレージシステムの構成ノードにアクセスした際に、そのアクセスを構成ノードで検出すると、その該当ユーザに関するデータの転送除外ルールを追加するよう動作する。
【００６９】
図９は、本発明の第３の実施の形態の構成を示す。第３の実施の形態は、第１及び２の実施の形態の構成とほぼ同じであるが、ユーザクライアント６からのアクセスを検出するためのアクセス検出手段７を備えることが異なる。
【００７０】
ユーザクライアント６は、本発明を実現するサービスである分散ストレージシステムにアクセスするクライアントであり、任意の端末（計算機や、携帯端末など）によって実現される。アクセス検出手段７は構成ノード１０Ｘ上で動作するソフトウェアであり、アクセス要求のユーザを識別する。実施例としては、分散ストレージシステムのアクセス要求を受け付けるソフトウェア内で実現することが考えられる。アクセス検出手段７はアクセス元のユーザを識別した後に、そのユーザに関するデータをアクセスされる構成ノードにデータが格納されるように制御させるために、転送除外ルール保持手段２５に転送除外条件を追加する（例えば、所有者がアクセスユーザのデータを除外条件に追加）。
【００７１】
また、アクセス検出手段７はアクセスの履歴を保持してもよい。アクセス履歴を保持することによって、一定期間該当構成ノードに対して、ユーザのアクセスが無ければ、そのユーザのための転送除外条件を削除する。このように動作することによって、ユーザのアクセス性能を向上させることが出来る。また、自動的に条件を削除することで、効率的な負荷分散制御を維持することが出来る。
【００７２】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【００７３】
「付記」
付記１
データを保持するための記憶手段を備える複数の構成ノードがネットワークを介して接続された分散ストレージシステムであって、
各構成ノードが、それぞれ論理的に接続された任意の数の論理的接続先ノードに対しデータを転送するデータ転送手段と、
前記記憶手段のデータ保持状態情報及び前記任意の数の論理的接続先ノードと構成ノード自身の負荷情報を負荷状態として取得する状態取得手段と、
取得した負荷状態から転送すべきデータ量を転送先ノード毎に計算する制御内容計算手段と、
外部に転送しないデータの条件を保持する転送除外ルールを格納する転送除外ルール保持手段と、
計算された転送すべきデータ量から前記転送除外ルールに該当しない転送データを選択するデータ選択／ルールチェック手段と、
を備えたことを特徴とする分散ストレージシステム。
【００７４】
付記２
前記各構成ノードが、それぞれ自身以外の構成ノードからの転送データを受信し前記記憶手段へ保持するデータ受信手段と、
前記複数の構成ノードの負荷情報を取得し、前記状態取得手段と前記任意の数の論理的接続先ノードに送信する負荷監視手段と、をさらに備えることを特徴とする付記１に記載の分散ストレージシステム。
【００７５】
付記３
単一あるいは複数の構成ノードの前記転送除外ルール保持手段に対し、任意のデータに対する転送除外条件を付与するルール更新手段を更に備えることを特徴とする付記１または２に記載の分散ストレージシステム。
【００７６】
付記４
単一あるいは複数の構成ノードの前記転送除外ルール保持手段に対して、前記任意のデータに対する転送除外条件を付与されたときに、指定の構成ノードと同時に被災しない構成ノードを１つあるいは複数選び、その選んだ構成ノードに同一の転送除外条件を付与することを特徴とする付記３に記載の分散ストレージシステム。
【００７７】
付記５
前記指定の構成ノードと同時に被災しない構成ノードの条件として、一定距離以上物理的距離が離れている条件を含むことを特徴とする付記４に記載の分散ストレージシステム。
【００７８】
付記６
前記指定の構成ノードと同時に被災しない構成ノードの条件として、電力供給源が別系統である条件を含むことを特徴とする付記４に記載の分散ストレージシステム。
【００７９】
付記７
単一あるいは複数の構成ノードの前記転送除外ルール保持手段に対し、前記任意のデータに対する転送除外条件を付与された際に、条件を付与された構成ノードの論理的接合形態を変更することを特徴とする付記３に記載の分散ストレージシステム。
【００８０】
付記８
データを保持するための記憶手段を備える複数の構成ノードがネットワークを介して接続された分散ストレージシステムにおけるデータ配置制御方法であって、
各構成ノードは、それぞれ外部に転送しないデータの条件を保持する転送除外ルールをあらかじめ転送除外ルール保持手段に格納しており、
各構成ノードはまた、
それぞれ論理的に接続された任意の数の論理的接続先ノードに対しデータを転送するステップと、
前記記憶手段のデータ保持状態情報及び前記任意の数の論理的接続先ノードと構成ノード自身の負荷情報を負荷状態として取得するステップと、
取得した負荷状態から転送すべきデータ量を転送先ノード毎に計算するステップと、
計算された転送すべきデータ量から前記転送除外ルールに該当しない転送データを選択するステップと、
を実行することを特徴とする分散ストレージデータ配置制御方法。
【００８１】
付記９
前記各構成ノードは更に、単一あるいは複数の構成ノードの前記転送除外ルール保持手段に対し、任意のデータに対する転送除外条件を付与するステップを実行することを特徴とする付記８に記載の分散ストレージデータ配置制御方法。
【００８２】
付記１０
前記各構成ノードは、前記単一あるいは複数の構成ノードの前記転送除外ルール保持手段に対して、前記任意のデータに対する転送除外条件を付与したときに、指定の構成ノードと同時に被災しない構成ノードを１つあるいは複数選び、その選んだ構成ノードに同一の転送除外条件を付与することを特徴とする付記９に記載の分散ストレージデータ配置制御方法。
【００８３】
付記１１
前記指定の構成ノードと同時に被災しない構成ノードの条件として、一定距離以上物理的距離が離れている条件を含むことを特徴とする付記１０に記載の分散ストレージデータ配置制御方法。
【００８４】
付記１２
前記指定の構成ノードと同時に被災しない構成ノードの条件として、電力供給源が別系統である条件を含むことを特徴とする付記１０に記載の分散ストレージデータ配置制御方法。
【００８５】
付記１３
前記各構成ノードは、前記単一あるいは複数の構成ノードの前記転送除外ルール保持手段に対して、前記任意のデータに対する転送除外条件を付与した際に、条件を付与した構成ノードの論理的接合形態を変更することを特徴とする付記９に記載の分散ストレージデータ配置制御方法。
【００８６】
付記１４
データを保持するための記憶手段を備える複数の構成ノードがネットワークを介して接続された分散ストレージシステムであって各構成ノードは、それぞれ外部に転送しないデータの条件を保持する転送除外ルールをあらかじめ転送除外ルール保持手段に格納している分散ストレージシステムに適用されるデータ配置制御用プログラムであって、
各構成ノードのコンピュータに、論理的に接続された任意の数の論理的接続先ノードに対しデータを転送するステップと、
前記記憶手段のデータ保持状態情報及び前記任意の数の論理的接続先ノードと構成ノード自身の負荷情報を負荷状態として取得するステップと、
取得した負荷状態から転送すべきデータ量を転送先ノード毎に計算するステップと、
計算された転送すべきデータ量から前記転送除外ルールに該当しない転送データを選択するステップと、
を実行させための分散ストレージデータ配置制御用プログラム。
【産業上の利用可能性】
【００８７】
本発明によれば、複数のノードによってストレージシステムを実現する、分散ストレージシステムといった用途に適用できる。特に、耐災害システム、拠点間でファイルを共有する分散ファイルシステム、といった用途に適用できる。
【符号の説明】
【００８８】
１    データストア
２    制御手段
３    データ受信手段
４    負荷監視手段
５    ルール更新手段
６    ユーザクライアント
２１    状態取得手段
２２    制御内容計算手段
２３    データ選択／ルールチェック手段
２４    データ移動制御手段
２５    転送除外ルール保持手段
２６    論理的接合形態管理手段
１００〜１０８    構成ノード
２００    ネットワーク
【図１】
2014032578.tif 000006
【図２】
2014032578.tif 000007
【図３】
2014032578.tif 000008
【図４】
2014032578.tif 000009
【図５】
2014032578.tif 000010
【図６】
2014032578.tif 000011
【図７】
2014032578.tif 000012
【図８】
2014032578.tif 000013
【図９】
2014032578.tif 000014