ノード決定プログラム、ノード決定装置およびノード決定方法
【課題】指定した割合に応じてデータを分散させた上で、ノード数の増減時におけるノード間のデータ移動を減らすこと。
【解決手段】ノード決定装置１０１は、ノードＮ１〜Ｎ３ごとに、それぞれ異なる関数ｆ＿１（）〜ｆ＿３（）を関連付け、比率ｃ＿１〜ｃ＿３を関連付ける。ノード決定装置１０１は、データＤのキーｋを代入することにより算出したノードＮ１〜Ｎ３ごとの関数値ｆ＿１（ｋ），ｆ＿２（ｋ），ｆ＿３（ｋ）と比率ｃ＿１〜ｃ＿３とを重み付け関数ｇ（）に代入することにより、ノードＮ１〜Ｎ３ごとの重み付け関数値ｇ（ｆ＿１（ｋ），ｃ＿１），ｇ（ｆ＿２（ｋ），ｃ＿２），ｇ（ｆ＿３（ｋ），ｃ＿３）を算出する。ノード決定装置１０１は、ノードＮ１〜Ｎ３ごとの重み付け関数値ｇ（ｆ＿１（ｋ），ｃ＿１），ｇ（ｆ＿２（ｋ），ｃ＿２），ｇ（ｆ＿３（ｋ），ｃ＿３）の大小関係に基づいて、データＤを格納するノードＮを決定する。
【解決手段】ノード決定装置１０１は、ノードＮ１〜Ｎ３ごとに、それぞれ異なる関数ｆ＿１（）〜ｆ＿３（）を関連付け、比率ｃ＿１〜ｃ＿３を関連付ける。ノード決定装置１０１は、データＤのキーｋを代入することにより算出したノードＮ１〜Ｎ３ごとの関数値ｆ＿１（ｋ），ｆ＿２（ｋ），ｆ＿３（ｋ）と比率ｃ＿１〜ｃ＿３とを重み付け関数ｇ（）に代入することにより、ノードＮ１〜Ｎ３ごとの重み付け関数値ｇ（ｆ＿１（ｋ），ｃ＿１），ｇ（ｆ＿２（ｋ），ｃ＿２），ｇ（ｆ＿３（ｋ），ｃ＿３）を算出する。ノード決定装置１０１は、ノードＮ１〜Ｎ３ごとの重み付け関数値ｇ（ｆ＿１（ｋ），ｃ＿１），ｇ（ｆ＿２（ｋ），ｃ＿２），ｇ（ｆ＿３（ｋ），ｃ＿３）の大小関係に基づいて、データＤを格納するノードＮを決定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データを格納するノードを決定するノード決定プログラム、ノード決定装置およびノード決定方法に関する。
【背景技術】
【０００２】
ある種の分散データストアでは、データのキーごとに、キーから特定されるデータを格納するノードが異なるものがある。また、分散データストアでは、耐障害の観点から、同一キーのデータを複数のノードに冗長して格納する場合がある。さらに、データストアとしてのサービスを停止させることなく、分散データストア内のノード数を動的に増減させる場合がある。
【０００３】
このような分散データストアでは、データのキーごとに、キーから特定されるデータを格納するノードを複数のノードの中から決定することになる（いわゆる、キー空間分割）。従来の一手法として、例えば、ハッシュ関数ｈ（）を一つ決め、データのキー「ｋ」をハッシュ関数ｈ（）に与えて得られるハッシュ値ｈ（ｋ）をノード数で割った余りにより、データを格納するノードを決める手法がある。
【０００４】
また、関連する先行技術として、例えば、ノードごとに重みを設定しておき、重みに基づいてノードの担当する識別子空間（例えば、ノードの担当するハッシュ値の範囲）を分けるものがある（例えば、下記特許文献１参照。）。また、関連する先行技術として、例えば、複数の情報処理装置でファイルを分割して保持するものがある（例えば、下記特許文献２参照。）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１０−１３４６３０号公報
【特許文献２】特許第４０６８４７３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、上述した従来技術では、分散データストア内のノード数の増減時に、多くのデータの格納先が変わってしまう場合があり、ノード間のデータ移動が増大するという問題があった。例えば、上述した従来の一手法では、分散データストア内のノード数が１０個から１１個に増えた場合、全データの１１分の１０のデータの格納先が変わってしまう。また、キー空間の割り当てをノードごとに設定するような場合は、考慮されていない。
【０００７】
本発明の一側面では、指定した割合に応じてデータを分散させた上で、ノード数の増減時におけるノード間のデータ移動を減らすことを目的とする。
【課題を解決するための手段】
【０００８】
本発明の一側面によれば、複数のノードに含まれるノードごとに異なる関数であって、当該関数の定義域がデータを一意に特定するためのキーを含む関数をノードごとに関連付け、格納するデータ量を示すノードごとの指標値をノードごとに関連付け、関連付けられたノードごとの関数にキーをそれぞれ代入することにより、ノードごとの関数の値を算出し、定義域がノードごとの関数の値とノードごとの指標値との組み合わせを含む重み付け関数であって、重み付け関数の値域で当該重み付け関数の値の大小関係が定義される重み付け関数に、ノードごとの関数の値とノードごとの指標値とを代入することにより、重み付け関数の値をノードごとに算出し、算出されたノードごとの重み付け関数の値の大小関係に基づいて、データを格納するノードを決定し、決定された決定結果を出力するノード決定プログラム、ノード決定装置およびノード決定方法が提案される。
【発明の効果】
【０００９】
本発明の一側面によれば、指定した割合に応じてデータを分散させた上で、ノード数の増減時におけるノード間のデータ移動を減らすことができるという効果を奏する。
【図面の簡単な説明】
【００１０】
【図１】図１は、実施の形態にかかるノード決定装置のノード決定処理の一実施例を示す説明図である。
【図２】図２は、ノード追加時のデータ移動の一例を示す説明図である。
【図３】図３は、ノード削除時のデータ移動の一例を示す説明図である。
【図４】図４は、実施の形態にかかる分散システムの一例を示す説明図である。
【図５】図５は、実施の形態に用いられるコンピュータのハードウェア構成の一例を示すブロック図である。
【図６】図６は、実施の形態にかかるノード決定装置の機能的構成を示すブロック図である。
【図７】図７は、キーリストの記憶内容の一例を示す説明図である。
【図８】図８は、関数リストの記憶内容の一例を示す説明図である。
【図９】図９は、指標値リストの記憶内容の一例を示す説明図である。
【図１０】図１０は、関数値リストの記憶内容の一例を示す説明図である。
【図１１】図１１は、重み付け関数値リストの記憶内容の一例を示す説明図である。
【図１２】図１２は、ノード／キー対応リストの記憶内容の一例を示す説明図である。
【図１３】図１３は、実施の形態にかかるノード決定装置のノード決定処理手順の一例を示すフローチャートである。
【図１４】図１４は、ステップＳ１３０８のノード決定処理の具体的処理手順の一例を示すフローチャート（その１）である。
【図１５】図１５は、ステップＳ１３０８のノード決定処理の具体的処理手順の一例を示すフローチャート（その２）である。
【図１６】図１６は、ノード追加時のノード決定装置のノード決定処理手順の一例を示すフローチャートである。
【図１７】図１７は、ノード削除時のノード決定装置のノード決定処理手順の一例を示すフローチャートである。
【図１８】図１８は、ノード／キー対応リストの記憶内容の具体例１を示す説明図（その１）である。
【図１９】図１９は、ノード／キー対応リストの記憶内容の具体例１を示す説明図（その２）である。
【図２０】図２０は、ノード／キー対応リストの記憶内容の具体例２を示す説明図（その１）である。
【図２１】図２１は、ノード／キー対応リストの記憶内容の具体例２を示す説明図（その２）である。
【発明を実施するための形態】
【００１１】
以下に添付図面を参照して、本発明にかかるノード決定プログラム、ノード決定装置およびノード決定方法の好適な実施の形態を詳細に説明する。ノード決定プログラム、ノード決定装置およびノード決定方法によれば、指定された指標値に基づいて分散データストア内のノード間でデータを偏らせて分散させた上で、ノード増減時のデータ移動量を減らすことができる。
【００１２】
そのために、ノード決定プログラム、ノード決定装置およびノード決定方法によれば、データのキーから得られたノードごとの関数値（例えばハッシュ値）を、ノードごとに設定された指標値で補正した値が算出される。そして、ノード決定プログラム、ノード決定装置およびノード決定方法によれば、ノードごとの補正された値の大小関係に基づいて、データを格納するノードが決定される。
【００１３】
これにより、ノード決定プログラム、ノード決定装置およびノード決定方法によれば、ノードごとに設定された指標値に応じて、データストア内のノード間でデータを偏らせて分散させることができる。結果として、記憶容量・演算能力・回線速度などの点で高性能なノードに多くのデータを格納させることができ、分散データストアの効率化を図ることができる。そして、ノードの増減時には、増減するノード以外のノード間ではノードごとの補正された値の大小関係は変化しないため、増減するノード以外のノード間ではデータの移動が生じず、ノード増減時のデータ移動量を抑制することができる。
【００１４】
（ノード決定処理の一実施例）
図１は、実施の形態にかかるノード決定装置のノード決定処理の一実施例を示す説明図である。ここでは、分散データストア内のノードＮ１〜Ｎ３の中からデータＤを格納するノードを決定する場合を例に挙げて説明する。
【００１５】
ここで、分散データストアは、複数のノード（ここでは、ノードＮ１〜Ｎ３）にデータ群を分散して格納するシステムである。分散データストアでは、データＤとキーｋがペアになっており、キーｋを指定することでデータＤを参照することができる。データＤのキーｋは、データＤを一意に特定するための情報である。
【００１６】
図１において、まず、ノード決定装置１０１は、ノードＮ１と関数ｆ＿１（）を関連付ける。また、ノード決定装置１０１は、ノードＮ２と関数ｆ＿２（）を関連付ける。また、ノード決定装置１０１は、ノードＮ３と関数ｆ＿３（）を関連付ける。ここで、関数ｆ＿１（），ｆ＿２（），ｆ＿３（）は、それぞれ異なる関数であって、該関数の定義域がデータＤのキーｋを含む関数である。
【００１７】
つぎに、ノード決定装置１０１は、ノードＮ１と比率ｃ＿１を関連付ける。また、ノード決定装置１０１は、ノードＮ２と比率ｃ＿２を関連付ける。また、ノード決定装置１０１は、ノードＮ３と比率ｃ＿３を関連付ける。ここで、比率ｃ＿１，ｃ＿２，ｃ＿３は、ノードＮ１〜Ｎ３に分散して格納されるデータ群の中で、ノードＮ１〜Ｎ３のそれぞれに格納するデータをどの程度の量にするかを示す指標値である。
【００１８】
そして、ノード決定装置１０１は、ノードＮ１〜Ｎ３ごとの関数ｆ＿１（），ｆ＿２（），ｆ＿３（）にデータＤのキーｋをそれぞれ代入することにより、ノードＮ１〜Ｎ３ごとの関数値ｆ＿１（ｋ），ｆ＿２（ｋ），ｆ＿３（ｋ）を算出する。
【００１９】
つぎに、ノード決定装置１０１は、ノードＮ１〜Ｎ３ごとの関数値ｆ＿１（ｋ），ｆ＿２（ｋ），ｆ＿３（ｋ）と、ノードＮ１〜Ｎ３ごとの比率ｃ＿１，ｃ＿２，ｃ＿３と、を重み付け関数ｇ（）に代入する。これにより、ノード決定装置１０１は、ノードＮ１〜Ｎ３ごとの重み付け関数値ｇ（ｆ＿１（ｋ），ｃ＿１），ｇ（ｆ＿２（ｋ），ｃ＿２），ｇ（ｆ＿３（ｋ），ｃ＿３）を算出する。
【００２０】
ここで、重み付け関数ｇ（）は、該関数の定義域がノードＮ１〜Ｎ３ごとの関数値ｆ＿１（ｋ），ｆ＿２（ｋ），ｆ＿３（ｋ）とノードＮ１〜Ｎ３ごとの比率ｃ＿１，ｃ＿２，ｃ＿３との組み合わせを含み、重み付け関数の値域で該重み付け関数の値（重み付け関数値）の大小関係が定義される関数である。
【００２１】
そして、ノード決定装置１０１は、ノードＮ１〜Ｎ３ごとの重み付け関数値ｇ（ｆ＿１（ｋ），ｃ＿１），ｇ（ｆ＿２（ｋ），ｃ＿２），ｇ（ｆ＿３（ｋ），ｃ＿３）の大小関係に基づいて、データＤを格納するノードを決定する。
【００２２】
ここでは一例として、ノード決定装置１０１が、重み付け関数値ｇ（ｆ＿１（ｋ），ｃ＿１），ｇ（ｆ＿２（ｋ），ｃ＿２），ｇ（ｆ＿３（ｋ），ｃ＿３）のうち最小の重み付け関数値ｇ（ｆ＿３（ｋ），ｃ＿３）に対応するノードＮ３を、データＤを格納するノードに決定する。
【００２３】
以上説明した一実施例によれば、分散データストア内のノード数の増減時におけるノード間のデータ移動を減らすことができる。具体的には、分散データストア内のノード数が変化した場合であっても、ノードＮ１〜Ｎ３の重み付け関数値の大小関係は変化しないため、ノード間のデータ移動の発生を抑えることができる。
【００２４】
より具体的には、例えば、分散データストア内のノード数が増える場合、新たに追加されるノードの重み付け関数値が最小とならない限り、データＤの移動は発生しない。一方、分散データストア内のノード数が減る場合、ノードＮ３が削除されない限り、データＤの移動は発生しない。以下、図２および図３を用いて、ノード数の増減時におけるノード間のデータ移動について説明する。
【００２５】
（ノード追加時のデータ移動の一例）
図２は、ノード追加時のデータ移動の一例を示す説明図である。ここでは、ノードＮ３にデータＤが格納されたあと、分散データストアに新たなノードＮ４が追加される場合について説明する。ここで、ノードＮ４が追加された場合であっても、ノードＮ１〜Ｎ３の重み付け関数値ｇ（ｆ＿１（ｋ），ｃ＿１），ｇ（ｆ＿２（ｋ），ｃ＿２），ｇ（ｆ＿３（ｋ），ｃ＿３）の大小関係は変化しない。
【００２６】
したがって、新たなノードＮ４の重み付け関数値ｇ（ｆ＿４（ｋ），ｃ＿４）が算出された結果、重み付け関数値ｇ（ｆ＿１（ｋ），ｃ＿１）〜ｇ（ｆ＿４（ｋ），ｃ＿４）のうち最小となる重み付け関数値は、つぎのパターン１またはパターン２のいずれかである。パターン１は、依然としてノードＮ３の重み付け関数値ｇ（ｆ＿３（ｋ），ｃ＿３）が最小となる場合である。パターン２は、ノードＮ４の重み付け関数値ｇ（ｆ＿４（ｋ），ｃ＿４）が最小となる場合である。
【００２７】
ここで、パターン１の場合、データＤの移動は発生しない。一方、パターン２の場合、データＤを格納するためのノードとしてノードＮ４が決定され、ノードＮ３に格納されているデータＤがノードＮ４に移動することになる。すなわち、ノード追加時は、ノードＮ４の重み付け関数値ｇ（ｆ＿４（ｋ），ｃ＿４）が最小とならない限り、データＤの移動は発生しないため、ノード間のデータ移動の発生を抑えることができる。
【００２８】
（ノード削除時のデータ移動の一例）
図３は、ノード削除時のデータ移動の一例を示す説明図である。ここでは、ノードＮ３にデータＤが格納されたあと、分散データストア内のノードＮ３を削除する場合（パターン３）と、ノードＮ２を削除する場合（パターン４）について説明する。
【００２９】
パターン３の場合、ノードＮ３を削除するため、ノードＮ３に格納されているデータＤの移動が発生する。ただし、ノードＮ３が削除された場合であっても、残余のノードＮ１，Ｎ２の重み付け関数値ｇ（ｆ＿１（ｋ），ｃ＿１），ｇ（ｆ＿２（ｋ），ｃ＿２）の大小関係は変化しない。したがって、ノードＮ３に格納されているデータＤが、ノードＮ３のつぎに重み付け関数値が小さいノードＮ１に移動することになる。一方、パターン４の場合、データＤの移動は発生しない。すなわち、ノード削除時は、データＤを格納しているノードＮ３が削除されない限り、データＤの移動は発生しないため、ノード間のデータ移動の発生を抑えることができる。
【００３０】
（分散システム４００の一例）
図４は、実施の形態にかかる分散システムの一例を示す説明図である。図４において、分散システム４００は、ノード決定装置１０１と、ノードＮ１〜Ｎｎと、クライアント装置Ｃと、を含む構成である。分散システム４００において、ノード決定装置１０１、ノードＮ１〜Ｎｎおよびクライアント装置Ｃは、例えば、インターネット、ＬＡＮ（Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）、ＷＡＮ（Ｗｉｄｅ Ａｒｅａ Ｎｅｔｗｏｒｋ）などのネットワーク４１０を介して相互に通信可能に接続されている。
【００３１】
ここで、ノードＮ１〜Ｎｎは、例えば、ファイルサーバ、データベースサーバなどのサーバである。クライアント装置Ｃは、例えば、データストアのサービスの提供を受けるコンピュータである。クライアント装置Ｃは、分散データストアＤＳ内のいずれかのノードに格納されているデータＤを、データＤのキーｋを用いて参照することができる。
【００３２】
以下の説明では、複数のノードＮ１〜Ｎｎのうち任意のノードを「ノードＮｉ」と表記する（ｉ＝１，２，…，ｎ）。また、ノードＮ１〜Ｎｎのそれぞれに関する比率を「ｃ＿１〜ｃ＿ｎ」と表記し、比率ｃ＿１〜ｃ＿ｎのうちノードＮｉに関する比率を「ｃ＿ｉ」と表記する。また、格納対象となるデータ群を「データＤ１〜Ｄｍ」と表記し、データＤ１〜Ｄｍのうち任意のデータＤを「データＤｊ」と表記する（ｊ＝１，２，…，ｍ）。また、データＤｊを一意に特定するためのキーを「キーｋｊ」と表記する。
【００３３】
（コンピュータのハードウェア構成）
つぎに、実施の形態に用いられるコンピュータ（ノード決定装置１０１、ノードＮ１〜Ｎｎ、クライアント装置Ｃ）のハードウェア構成について説明する。
【００３４】
図５は、実施の形態に用いられるコンピュータのハードウェア構成の一例を示すブロック図である。図５において、コンピュータは、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）５０１と、ＲＯＭ（Ｒｅａｄ‐Ｏｎｌｙ Ｍｅｍｏｒｙ）５０２と、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）５０３と、磁気ディスクドライブ５０４と、磁気ディスク５０５と、光ディスクドライブ５０６と、光ディスク５０７と、ディスプレイ５０８と、Ｉ／Ｆ（Ｉｎｔｅｒｆａｃｅ）５０９と、キーボード５１０と、マウス５１１と、を備えている。また、各構成部はバス５００によってそれぞれ接続されている。
【００３５】
ここで、ＣＰＵ５０１は、コンピュータの全体の制御を司る。ＲＯＭ５０２は、ブートプログラムなどのプログラムを記憶している。ＲＡＭ５０３は、ＣＰＵ５０１のワークエリアとして使用される。磁気ディスクドライブ５０４は、ＣＰＵ５０１の制御にしたがって磁気ディスク５０５に対するデータのリード／ライトを制御する。磁気ディスク５０５は、磁気ディスクドライブ５０４の制御で書き込まれたデータを記憶する。
【００３６】
光ディスクドライブ５０６は、ＣＰＵ５０１の制御にしたがって光ディスク５０７に対するデータのリード／ライトを制御する。光ディスク５０７は、光ディスクドライブ５０６の制御で書き込まれたデータを記憶したり、光ディスク５０７に記憶されたデータをコンピュータに読み取らせたりする。
【００３７】
ディスプレイ５０８は、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。このディスプレイ５０８には、例えば、ＣＲＴ、ＴＦＴ液晶ディスプレイ、プラズマディスプレイなどを採用することができる。
【００３８】
Ｉ／Ｆ５０９は、通信回線を通じてＬＡＮ、ＷＡＮ、インターネットなどのネットワーク４１０に接続され、このネットワーク４１０を介して他の装置に接続される。そして、Ｉ／Ｆ５０９は、ネットワーク４１０と内部のインターフェースを司り、外部装置からのデータの入出力を制御する。Ｉ／Ｆ５０９には、例えば、モデムやＬＡＮアダプタなどを採用することができる。
【００３９】
キーボード５１０は、文字、数字、各種指示などの入力のためのキーを備え、データの入力を行う。また、タッチパネル式の入力パッドやテンキーなどであってもよい。マウス５１１は、カーソルの移動や範囲選択、あるいはウィンドウの移動やサイズの変更などを行う。ポインティングデバイスとして同様に機能を備えるものであれば、トラックボールやジョイスティックなどであってもよい。
【００４０】
（ノード決定装置１０１の機能的構成）
つぎに、実施の形態にかかるノード決定装置１０１の機能的構成について説明する。図６は、実施の形態にかかるノード決定装置の機能的構成を示すブロック図である。図６において、ノード決定装置１０１は、受付部６０１と、第１の関連付け部６０２と、第２の関連付け部６０３と、第１の算出部６０４と、第２の算出部６０５と、決定部６０６と、並換部６０７と、選択部６０８と、出力部６０９と、を含む構成である。
【００４１】
各機能部（受付部６０１〜出力部６０９）は、例えば、図５に示したＲＯＭ５０２、ＲＡＭ５０３、磁気ディスク５０５、光ディスク５０７などの記憶装置に記憶されたプログラムをＣＰＵ５０１に実行させることにより、または、Ｉ／Ｆ５０９により、その機能を実現する。また、各機能部（受付部６０１〜出力部６０９）の処理結果は、特に指定する場合を除いて、ＲＡＭ５０３、磁気ディスク５０５、光ディスク５０７などの記憶装置に記憶される。
【００４２】
受付部６０１は、格納対象となるデータＤｊに関するキー情報を受け付ける機能を有する。ここで、キー情報は、例えば、格納対象となるデータＤｊのデータ名と、キーｋｊと、冗長度Ｒｊと、を含む。データＤｊは、例えば、フォルダ、ファイル、レコード単位の情報である。キーｋｊは、例えば、ファイルのパス名やデータベース内のレコードの主キーなどの文字列である。冗長度Ｒｊは、耐障害の観点から、同一キーｋｊのデータＤｊを複数のノードＮｉに冗長して格納する場合のノード数である。
【００４３】
具体的には、例えば、受付部６０１が、図５に示したキーボード５１０やマウス５１１を用いたユーザの操作入力によりキー情報を受け付ける。また、受付部６０１が、ネットワーク４１０を介して、クライアント装置Ｃからキー情報を受け付けてもよい。受け付けたキー情報は、例えば、図７に示すキーリスト７００に記憶される。
【００４４】
図７は、キーリストの記憶内容の一例を示す説明図である。図７において、キーリスト７００は、データ名、キーおよび冗長度のフィールドを有し、各フィールドに情報を設定することで、キー情報７００−１〜７００−ｍをレコードとして記憶している。ここで、データ名とは、データＤｊの名称である。キーとは、データＤｊを一意に特定するための情報である。冗長度は、データＤｊを複数のノードＮｉに冗長して格納する場合のノード数である。
【００４５】
キーリスト７００の記憶内容は、例えば、キー情報を受け付けた場合、また、分散データストアＤＳからデータＤｊが削除された場合に、その都度更新される。キーリスト７００は、例えば、ＲＯＭ５０２、ＲＡＭ５０３、磁気ディスク５０５、光ディスク５０７などの記憶装置により、その機能を実現する。
【００４６】
図６の説明に戻り、また、受付部６０１は、ノードＮｉに関する指標値を受け付ける機能を有する。ここで、指標値とは、ノードＮ１〜Ｎｎに分散して格納されるデータＤ１〜Ｄｍの中で、ノードＮｉに格納するデータＤをどの程度の量にするかを示す値である。具体的には、例えば、指標値とは、上述した比率ｃ＿ｉであり、ノードＮｉの記憶容量・演算能力・回線速度に基づいて決定された値である。
【００４７】
具体的には、例えば、受付部６０１が、キーボード５１０やマウス５１１を用いたユーザの操作入力によりノードＮｉに関する比率ｃ＿ｉを受け付ける。また、受付部６０１が、ネットワーク４１０を介して、ノードＮｉやクライアント装置ＣからノードＮｉに関する比率ｃ＿ｉを受け付けてもよい。受け付けたノードＮｉに関する指標値は、例えば、後述する第２の関連付け部６０３により、図９に示す指標値リスト９００に記憶される。
【００４８】
また、受付部６０１は、分散データストアＤＳ内のノード数の増減にともなうノード決定指示を受け付ける機能を有する。ここで、ノード決定指示とは、ノード数の増減にともなって、データＤｊの格納先となるノードＮｉを再決定するように指示するものである。
【００４９】
具体的には、ノード追加にともなうノード決定指示には、例えば、分散データストアＤＳに追加されるノードＮｉのノード名が含まれている。また、ノード追加にともなうノード決定指示には、例えば、追加されるノードＮｉに関する比率ｃ＿ｉが含まれている。受け付けたノード決定指示に含まれるノードＮｉに関する指標値は、例えば、後述する第２の関連付け部６０３により、図９に示す指標値リスト９００に記憶される。なお、新たなノードＮｉの追加は、例えば、分散システム４００のパフォーマンスの向上などを目的として行われる。
【００５０】
また、ノード削除にともなうノード決定指示には、例えば、分散データストアＤＳから削除されるノードＮｉのノード名が含まれている。なお、ノードＮｉの削除は、例えば、ノードＮｉの故障時などに行われる。
【００５１】
具体的には、例えば、受付部６０１が、キーボード５１０やマウス５１１を用いたユーザの操作入力によりノード決定指示を受け付ける。また、受付部６０１が、ネットワーク４１０を介して、ノードＮｉやクライアント装置Ｃからノード決定指示を受け付けてもよい。
【００５２】
第１の関連付け部６０２は、ノードＮｉごとに関数を関連付ける機能を有する。以下、ノードＮｉの関数を「関数ｆ＿ｉ（）」と表記する。ここで、関数ｆ＿ｉ（）は、ノードＮｉごとに異なる関数であって、その定義域がデータＤｊのキーｋｊを含む関数である。すなわち、関数ｆ＿ｉ（）は、その定義域がキーｋｊがとりえる値の範囲を含んでいる関数である。
【００５３】
具体的には、例えば、第１の関連付け部６０２が、予め用意されている関数群Ｆの中から、任意の関数を関数ｆ＿ｉ（）として選択して、ノードＮｉと関数ｆ＿ｉ（）とを関連付ける。関連付け結果は、例えば、図８に示す関数リスト８００に記憶される。なお、関数群Ｆは、少なくともノード数ｎ分の関数の集合であり、ＲＯＭ５０２、ＲＡＭ５０３、磁気ディスク５０５、光ディスク５０７などの記憶装置に記憶されている。
【００５４】
また、第１の関連付け部６０２が、二つの引数をとる関数ｆ（）を一つ用意して、関数ｆ＿ｉ（）を、例えば下記式（１）のように定義することにしてもよい。ただし、ｉはノードＮｉのノード名、ｋｊはデータＤｊのキーである。なお、二つの引数をとる関数ｆ（）は、例えば、ＲＯＭ５０２、ＲＡＭ５０３、磁気ディスク５０５、光ディスク５０７などの記憶装置に記憶されている。
【００５５】
ｆ＿ｉ（）＝ｆ（ｉ，ｋｊ） ・・・（１）
【００５６】
また、関数ｆ＿ｉ（）としては、上述の定義域の条件を満たすものであれば、任意の関数を用いることができる。具体的には、例えば、関数ｆ＿ｉ（）として、キーｋｊを引数として与えることで固定長の乱数が得られる関数を用いることにしてもよい。より具体的には、例えば、関数ｆ＿ｉ（）として、ＳＨＡ１（Ｓｅｃｕｒｅ Ｈａｓｈ Ａｌｇｏｒｉｔｈｍ １）などのハッシュ関数を用いることにしてもよい。ＳＨＡ１は、入力が少し異なれば出力が大きく異なるという性質を有する関数である。また、例えば、キーｋｊおよびノード名「ｉ」がともに整数の場合は、関数ｆ＿ｉ（）として、キーｋｊにノード名「ｉ」を加算する「ｆ＿ｉ（）＝ｋｊ＋ｉ」という関数を用いることにしてもよい。
【００５７】
さらに、ノードＮ１〜Ｎｎの関数ｆ＿１（）〜ｆ＿ｎ（）として、関数値の頻度分布が十分に等しく、互いに独立な関数を用いることにしてもよい。具体的には、例えば、第１の関連付け部６０２が、ＳＨＡ１などのハッシュ関数を用いて、関数ｆ＿ｉ（）を下記式（２）のように定義することにしてもよい。ただし、ｃｏｎｃａｔｎａｔｅ（ｉ，ｋｊ）は、ノードＮｉのノード名「ｉ」とデータＤｊのキーｋｊを文字列として連結する関数である。
【００５８】
ｆ＿ｉ（）＝ＳＨＡ１（ｃｏｎｃａｔｎａｔｅ（ｉ，ｋｊ）） ・・・（２）
【００５９】
図８は、関数リストの記憶内容の一例を示す説明図である。図８において、関数リスト８００は、ノードＩＤ、ノード名および関数のフィールドを有し、各フィールドに情報を設定することで、関数情報８００−１〜８００−ｎをレコードとして記憶している。
【００６０】
ノードＩＤは、本明細書において説明上使用するノードＮｉの識別子である。ノード名は、ノードＮｉの名称である。関数は、ノードＮｉと関連付けられている関数ｆ＿ｉ（）である。関数リスト８００は、例えば、ＲＯＭ５０２、ＲＡＭ５０３、磁気ディスク５０５、光ディスク５０７などの記憶装置により、その機能を実現する。
【００６１】
図６の説明に戻り、第２の関連付け部６０３は、格納するデータ量を示すノードＮｉごとの指標値をノードＮｉごとに関連付ける機能を有する。具体的には、例えば、第２の関連付け部６０３は、受付部６０１によって受け付けられたノードＮｉに関する比率ｃ＿ｉを、ノードＮｉに関連付ける。関連付け結果は、例えば、図９に示す指標値リスト９００に記憶される。
【００６２】
図９は、指標値リストの記憶内容の一例を示す説明図である。図９において、指標値リスト９００は、ノードＩＤ、ノード名および指標値のフィールドを有し、各フィールドに情報を設定することで、指標値情報９００−１〜９００−ｎをレコードとして記憶している。指標値は、ノードＮｉと関連付けられている比率ｃ＿ｉである。指標値リスト９００は、例えば、ＲＯＭ５０２、ＲＡＭ５０３、磁気ディスク５０５、光ディスク５０７などの記憶装置により、その機能を実現する。
【００６３】
図６の説明に戻り、第１の算出部６０４は、関連付けられたノードＮｉごとの関数ｆ＿ｉ（）にキーｋをそれぞれ代入することにより、ノードＮｉごとの関数ｆ＿ｉ（）の値（以下、「関数値ｆ＿ｉ（ｋ）」）を算出する機能を有する。具体的には、例えば、第１の算出部６０４が、キーｋを引数として関数ｆ＿ｉ（）に与えることで、ノードＮｉごとの関数値ｆ＿ｉ（ｋ）を算出する。
【００６４】
また、関数ｆ＿ｉ（）として上記式（１）を用いる場合、第１の算出部６０４が、ノードＮｉのノード名「ｉ」およびキーｋを引数として上記式（１）に与えることで、ノードＮｉごとの関数値ｆ＿ｉ（ｋ）を算出する。算出された算出結果は、例えば、図１０に示す関数値リスト１０００に記憶される。
【００６５】
図１０は、関数値リストの記憶内容の一例を示す説明図である。図１０において、関数値リスト１０００は、ノードＩＤ、ノード名および関数値のフィールドを有し、各フィールドに情報を設定することで、関数値情報１０００−１〜１０００−ｎをレコードとして記憶している。関数値リスト１０００は、例えば、ＲＯＭ５０２、ＲＡＭ５０３、磁気ディスク５０５、光ディスク５０７などの記憶装置により、その機能を実現する。
【００６６】
図６の説明に戻り、第２の算出部６０５は、重み付け関数ｇ（）に、ノードＮｉごとの関数値ｆ＿ｉ（ｋ）とノードＮｉごとの指標値とを代入することにより、重み付け関数ｇ（）の値（以下、「重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）」）をノードＮｉごとに算出する機能を有する。
【００６７】
ここで、重み付け関数ｇ（）は、その定義域がノードＮｉごとの関数値ｆ＿ｉ（ｋ）とノードＮｉごとの指標値との組み合わせを含み、その値域で重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）の大小関係が定義される関数である。すなわち、重み付け関数ｇ（）は、その定義域がノードＮｉごとの関数値ｆ＿ｉ（ｋ）がとりうる値とノードＮｉごとの指標値とがとりうる値とを組み合わせた範囲を含んでおり、その値域で重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）の大小関係を比較することができる関数である。
【００６８】
また、重み付け関数ｇ（）は、引数となる関数値ｆ＿ｉ（ｋ）の増加にともなって、重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）が増加する関数、または、重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）が減少する関数である。また、重み付け関数ｇ（）は、引数となる指標値の増加にともなって、重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）が増加する関数、または、重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）が減少する関数である。なお、重み付け関数ｇ（）は、例えば、ＲＯＭ５０２、ＲＡＭ５０３、磁気ディスク５０５、光ディスク５０７などの記憶装置に記憶されている。
【００６９】
重み付け関数ｇ（）としては、上述の条件を満たすものであれば、任意の関数を用いることができる。具体的には、例えば、重み付け関数ｇ（）として、「ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）＝ｆ＿ｉ（ｋ）／ｃ＿ｉ」という関数を用いることにしてもよい。これにより、各ノードＮｉの指標値ｃ＿ｉを反映して、重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）を算出することができる。
【００７０】
また、重み付け関数ｇ（）としては、重み付け関数の値域で定義される当該重み付け関数の値の大小関係が、ノードＮｉごとの指標値ｃ＿ｉの和に対するいずれかのノードＮｉの指標値ｃ＿ｉの割合で、いずれかのノードＮｉの重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）が最大または最小になる関係である関数を用いることができる。
【００７１】
具体的には、例えば、重み付け関数ｇ（）として、「ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）＝ｆ＿ｉ（ｋ）＾ｃ＿ｉ」という関数を用いることにしてもよい。なお、「ｆ＿ｉ（ｋ）＾ｃ＿ｉ」はｆ＿ｉ（ｋ）をｃ＿ｉで冪乗する数式を示す。これにより、各ノードＮｉの指標値ｃ＿ｉを反映して、重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）を算出することができる。
【００７２】
具体的には、第２の算出部６０５は、重み付け関数ｇ（）に、ノードＮｉごとの関数値ｆ＿ｉ（ｋ）とノードＮｉごとの比率ｃ＿ｉとを代入することにより、重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）をノードＮｉごとに算出する。算出された算出結果は、例えば、図１１に示す重み付け関数値リスト１１００に記憶される。
【００７３】
図１１は、重み付け関数値リストの記憶内容の一例を示す説明図である。図１１において、重み付け関数値リスト１１００は、ノードＩＤ、ノード名および重み付け関数値のフィールドを有し、各フィールドに情報を設定することで、重み付け関数値情報１１００−１〜１１００−ｎをレコードとして記憶している。重み付け関数値リスト１１００は、例えば、ＲＯＭ５０２、ＲＡＭ５０３、磁気ディスク５０５、光ディスク５０７などの記憶装置により、その機能を実現する。
【００７４】
図６の説明に戻り、決定部６０６は、算出されたノードＮｉごとの重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）の大小関係に基づいて、データＤｊを格納するノードＮｉを決定する機能を有する。具体的には、例えば、決定部６０６が、重み付け関数値ｇ（ｆ＿１（ｋ），ｃ＿１）〜ｇ（ｆ＿ｎ（ｋ），ｃ＿ｎ）のうち最小（または、最大）の重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）に対応するノードＮｉを、データＤｊを格納するノードＮｉに決定する。
【００７５】
並換部６０７は、算出されたノードＮｉごとの重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）の大小関係に基づいて、ノードＮｉごとの重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）を並び換える機能を有する。具体的には、例えば、並換部６０７が、ノードＮ１〜Ｎｎの重み付け関数値ｇ（ｆ＿１（ｋ），ｃ＿１）〜ｇ（ｆ＿ｎ（ｋ），ｃ＿ｎ）が昇順（または、降順）となるように並び換える。
【００７６】
選択部６０８は、並び換えられたノードＮｉごとの重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）の順序にしたがって、ノードＮ１〜Ｎｎの中から所定数のノードＮｉを選択する機能を有する。ここで、所定数は、例えば、データＤｊの冗長度Ｒｊである。以下の説明では、並び換え後のノードＮ１〜Ｎｎの重み付け関数値ｇ（ｆ＿１（ｋ），ｃ＿１）〜ｇ（ｆ＿ｎ（ｋ），ｃ＿ｎ）を「関数値ｇ［１］〜ｇ［ｎ］」と表記する。
【００７７】
具体的には、例えば、まず、選択部６０８が、並び換え後の関数値ｇ［１］〜ｇ［ｎ］の先頭（または、後尾）からＲｊ個の関数値ｇ［１］〜ｇ［Ｒｊ］を選択する。そして、選択部６０８が、重み付け関数値リスト１１００を参照することにより、選択された関数値ｇ［１］〜ｇ［Ｒｊ］に対応するＲｊ個のノードＮｉを特定して選択する。
【００７８】
以下の説明では、選択されたＲｊ個のノードＮｉを「ノードＮ［１］〜Ｎ［Ｒｊ］」と表記する。なお、冗長度Ｒｊが「Ｒｊ＝１」の場合は、選択部６０８は、並び換え後の関数値ｇ［１］〜ｇ［ｎ］の先頭（または、後尾）から特定の順番のノードＮｉを選択することにしてもよい。
【００７９】
また、決定部６０６は、選択された所定数のノードＮｉを、データＤｊを格納するノードＮｉに決定することにしてもよい。具体的には、例えば、決定部６０６が、選択されたＲｊ個のノードＮ［１］〜Ｎ［Ｒｊ］を、データＤｊを格納するノードＮｉに決定する。決定された決定結果は、図１２に示すノード／キー対応リスト１２００に記憶される。
【００８０】
図１２は、ノード／キー対応リストの記憶内容の一例を示す説明図である。図１２において、ノード／キー対応リスト１２００は、ノードＩＤ、ノード名およびキーのフィールドを有する。各フィールドに情報を設定することで、ノードＮ１〜Ｎｎごとの対応情報１２００−１〜１２００−ｎがレコードとして記憶される。
【００８１】
一例として、ノードＮ１がデータＤ１，Ｄ３，Ｄ９を格納するノードＮｉに決定された場合、対応情報１２００−１の「キー」フィールドに、データＤ１，Ｄ３，Ｄ９のキーｋ１，ｋ３，ｋ９が設定される。また、ノードＮ２がデータＤ４，Ｄ５を格納するノードＮｉに決定された場合、対応情報１２００−２の「キー」フィールドに、データＤ４，Ｄ５のキーｋ４，ｋ５が設定される。なお、各データＤｊのキーｋｊは、例えば、キーリスト７００を参照することで特定することができる。
【００８２】
図６の説明に戻り、出力部６０９は、決定された決定結果を出力する機能を有する。具体的には、例えば、出力部６０９が、図１２に示したノード／キー対応リスト１２００を出力する。出力形式としては、例えば、ディスプレイ５０８への表示、プリンタ（不図示）への印刷出力、Ｉ／Ｆ５０９による外部装置への送信がある。また、ＲＡＭ５０３、磁気ディスク５０５、光ディスク５０７などの記憶領域に記憶することとしてもよい。
【００８３】
より具体的には、例えば、出力部６０９が、ノード間のデータ移動を制御する外部のコンピュータにノード／キー対応リスト１２００を送信してもよい。この場合、例えば、外部のコンピュータが、ノード／キー対応リスト１２００にしたがって、ノード間のデータ移動を制御することになる。また、出力部６０９が、ノード／キー対応リスト１２００にしたがって、データＤｉの移動指示をノードＮｉに送信してもよい。
【００８４】
なお、上述した説明では、ノード決定装置１０１とノードＮｉとを別体に設ける場合について説明したが、これに限らない。具体的には、例えば、ノードＮｉがノード決定装置１０１を備える構成にしてもよい。
【００８５】
（ノード決定装置１０１のノード決定処理手順）
つぎに、実施の形態にかかるノード決定装置１０１のノード決定処理手順について説明する。ここでは、ノードＮ１〜Ｎｎの中から、データＤ１〜Ｄｍの格納先となるノードＮｉを決定する場合を例に挙げて説明する。また、ここでは、受付部６０１により、キーリスト７００が作成されており、第２の関連付け部６０３により指標値リスト９００が作成されているとする。
【００８６】
図１３は、実施の形態にかかるノード決定装置のノード決定処理手順の一例を示すフローチャートである。図１３のフローチャートにおいて、まず、第１の関連付け部６０２により、ノードＮｉの「ｉ」を「ｉ＝１」で初期化して（ステップＳ１３０１）、関数群Ｆの中から関数ｆ＿ｉ（）を選択する（ステップＳ１３０２）。そして、第１の関連付け部６０２により、ノードＮｉのノード名と、選択された関数ｆ＿ｉ（）とを関連付けて関数リスト８００に登録する（ステップＳ１３０３）。
【００８７】
つぎに、第１の関連付け部６０２により、ノードＮｉの「ｉ」をインクリメントして（ステップＳ１３０４）、「ｉ」が「ｎ」より大きいか否かを判断する（ステップＳ１３０５）。ここで、「ｉ」が「ｎ」以下の場合（ステップＳ１３０５：Ｎｏ）、ステップＳ１３０２に戻る。
【００８８】
一方、「ｉ」が「ｎ」より大きい場合（ステップＳ１３０５：Ｙｅｓ）、第１の算出部６０４により、データＤｊの「ｊ」を「ｊ＝１」で初期化する（ステップＳ１３０６）。そして、第１の算出部６０４により、キーリスト７００の中からデータＤｊのキーｋｊおよび冗長度Ｒｊを抽出する（ステップＳ１３０７）。
【００８９】
このあと、決定部６０６により、データＤｊを格納するノードＮｉを決定するノード決定処理を実行する（ステップＳ１３０８）。そして、第１の算出部６０４により、データＤｊの「ｊ」をインクリメントして（ステップＳ１３０９）、「ｊ」が「ｍ」より大きいか否かを判断する（ステップＳ１３１０）。ここで、「ｊ」が「ｍ」以下の場合（ステップＳ１３１０：Ｎｏ）、ステップＳ１３０７に戻る。
【００９０】
一方、「ｊ」が「ｍ」より大きい場合（ステップＳ１３１０：Ｙｅｓ）、出力部６０９により、ノード／キー対応リスト１２００を出力して（ステップＳ１３１１）、本フローチャートによる一連の処理を終了する。
【００９１】
つぎに、図１３に示したステップＳ１３０８のノード決定処理の具体的処理手順について説明する。図１４および図１５は、ステップＳ１３０８のノード決定処理の具体的処理手順の一例を示すフローチャートである。
【００９２】
図１４のフローチャートにおいて、まず、第１の算出部６０４により、ノードＮｉの「ｉ」を「ｉ＝１」で初期化して（ステップＳ１４０１）、関数リスト８００の中からノードＮｉの関数ｆ＿ｉ（）を抽出する（ステップＳ１４０２）。
【００９３】
つぎに、第１の算出部６０４により、抽出された関数ｆ＿ｉ（）に図１３に示したステップＳ１３０７において抽出されたキーｋｊを代入して、ノードＮｉの関数値ｆ＿ｉ（ｋｊ）を算出する（ステップＳ１４０３）。そして、第１の算出部６０４により、算出されたノードＮｉの関数値ｆ＿ｉ（ｋｊ）を関数値リスト１０００に登録する（ステップＳ１４０４）。
【００９４】
つぎに、第２の算出部６０５により、関数値リスト１０００の中からノードＮｉの関数値ｆ＿ｉ（ｋｊ）を抽出する（ステップＳ１４０５）。そして、第２の算出部６０５により、指標値リスト９００の中からノードＮｉに関する比率ｃ＿ｉを抽出する（ステップＳ１４０６）。
【００９５】
つぎに、第２の算出部６０５により、重み付け関数ｇ（）に抽出されたノードＮｉの関数値ｆ＿ｉ（ｋｊ）と比率ｃ＿ｉとを代入して、ノードＮｉの重み付け関数値ｇ（ｆ＿ｉ（ｋｊ），ｃ＿ｉ）を算出する（ステップＳ１４０７）。そして、第２の算出部６０５により、算出されたノードＮｉの重み付け関数値ｇ（ｆ＿ｉ（ｋｊ），ｃ＿ｉ）を重み付け関数値リスト１１００に登録する（ステップＳ１４０８）。
【００９６】
このあと、第２の算出部６０４により、ノードＮｉの「ｉ」をインクリメントして（ステップＳ１４０９）、「ｉ」が「ｎ」より大きいか否かを判断する（ステップＳ１４１０）。ここで、「ｉ」が「ｎ」以下の場合（ステップＳ１４１０：Ｎｏ）、ステップＳ１４０２に戻る。
【００９７】
一方、「ｉ」が「ｎ」より大きい場合（ステップＳ１４１０：Ｙｅｓ）、図１５に示すステップＳ１５０１に移行する。図１５のフローチャートにおいて、並換部６０７により、重み付け関数値リスト１１００を参照して、重み付け関数値ｇ（ｆ＿１（ｋｊ），ｃ＿１）〜ｇ（ｆ＿ｎ（ｋｊ），ｃ＿ｎ）を昇順に並び換える（ステップＳ１５０１）。
【００９８】
このあと、選択部６０８により、並び換え後の重み付け関数値ｇ［１］〜ｇ［ｎ］の先頭からＲｊ個の重み付け関数値ｇ［１］〜ｇ［Ｒｊ］を選択する（ステップＳ１５０２）。ただし、Ｒｊは、図１３に示したステップＳ１３０７において抽出された冗長度Ｒｊである。つぎに、選択部６０８により、重み付け関数値リスト１１００を参照して、選択されたＲｊ個の重み付け関数値ｇ［１］〜ｇ［Ｒｊ］に対応するノードＮ［１］〜Ｎ［Ｒｊ］を選択する（ステップＳ１５０３）。
【００９９】
このあと、決定部６０６により、選択されたノードＮ［１］〜Ｎ［Ｒｊ］を、データＤｊを格納するノードＮｉに決定する（ステップＳ１５０４）。そして、決定部６０６により、決定された決定結果をノード／キー対応リスト１２００に登録して（ステップＳ１５０５）、図１３に示したステップＳ１３０９に移行する。
【０１００】
これにより、重み付け関数ｇ（）にノードＮｉごとの関数値ｆ＿ｉ（ｋｊ）とノードＮｉごとの比率ｃ＿ｉを引数として与えて得られる重み付け関数値ｇ（ｆ＿ｉ（ｋｊ），ｃ＿ｉ）の大小関係から、データＤｊを格納するノードＮｉを決定することができる。この結果、ノードＮｉごとに設定された指標値ｃ＿ｉに応じて、分散データストアＤＳ内の各ノードＮｉにデータＤｊを分散させて格納することができる。また、分散データストアＤＳ内のノード数の増減時におけるノード間のデータ移動を減らすことができる。
【０１０１】
（ノード追加時のノード決定処理手順）
つぎに、ノード追加時のノード決定装置１０１のノード決定処理手順について説明する。ここでは、分散データストアＤＳに新たに追加されるノードＮｉを「ノードＮｘ」と表記する。図１６は、ノード追加時のノード決定装置のノード決定処理手順の一例を示すフローチャートである。
【０１０２】
図１６のフローチャートにおいて、まず、受付部６０１により、ノード追加にともなうノード決定指示を受け付けたか否かを判断する（ステップＳ１６０１）。ここで、ノード決定指示を受け付けるのを待って（ステップＳ１６０１：Ｎｏ）、受け付けた場合（ステップＳ１６０１：Ｙｅｓ）、第１の関連付け部６０２により、関数群Ｆの中からノードＮｘの関数ｆ＿ｘ（）を選択する（ステップＳ１６０２）。
【０１０３】
そして、第１の関連付け部６０２により、ノードＮｘのノード名と、選択された関数ｆ＿ｘ（）とを関連付けて関数リスト８００に登録する（ステップＳ１６０３）。ただし、ノードＮｘのノード名および関数ｆ＿ｘ（）は、関数リスト８００の後尾の関数情報８００−ｎとして登録される。
【０１０４】
つぎに、第２の関連付け部６０３により、ノード決定指示に含まれるノードＮｘの比率ｃ＿ｘが取得される。そして、第２の関連付け部６０３により、ノードＮｘのノード名と、比率ｃ＿ｘとを関連付けて指標値リスト９００に登録する（ステップＳ１６０４）。ただし、ノードＮｘのノード名および比率ｃ＿ｘは、指標値リスト９００の後尾の指標値情報９００−ｎとして登録される。
【０１０５】
つぎに、決定部６０６により、ノード／キー対応リスト１２００を初期化する（ステップＳ１６０５）。そして、第１の算出部６０４により、データＤｊの「ｊ」を「ｊ＝１」で初期化して（ステップＳ１６０６）、キーリスト７００の中からデータＤｊのキーｋｊおよび冗長度Ｒｊを抽出する（ステップＳ１６０７）。
【０１０６】
このあと、決定部６０６により、データＤｊを格納するノードＮｉを決定するノード決定処理を実行する（ステップＳ１６０８）。そして、第１の算出部６０４により、データＤｊの「ｊ」をインクリメントして（ステップＳ１６０９）、「ｊ」が「ｍ」より大きいか否かを判断する（ステップＳ１６１０）。
【０１０７】
ここで、「ｊ」が「ｍ」以下の場合（ステップＳ１６１０：Ｎｏ）、ステップＳ１６０７に戻る。一方、「ｊ」が「ｍ」より大きい場合（ステップＳ１６１０：Ｙｅｓ）、出力部６０９により、ノード／キー対応リスト１２００を出力して（ステップＳ１６１１）、本フローチャートによる一連の処理を終了する。
【０１０８】
これにより、分散データストアＤＳへのノード追加時に、データＤ１〜Ｄｍを格納するノードＮｉを再決定することができる。また、ノードＮｘの追加にともなってデータ移動が発生する場合は、新たに追加されたノードＮｘにデータＤｊが移動することになるため、ノード追加時におけるパフォーマンスを効率的に向上させることができる。なお、ステップＳ１６０８のノード決定処理の具体的処理手順は、図１４および図１５に示したステップＳ１３０８のノード決定処理の具体的処理手順と同様のため、ここでは説明を省略する。
【０１０９】
（ノード削除時のノード決定処理手順）
つぎに、ノード削除時のノード決定装置１０１のノード決定処理手順について説明する。ここでは、分散データストアＤＳから削除されるノードＮｉを「ノードＮｙ」と表記する。図１７は、ノード削除時のノード決定装置のノード決定処理手順の一例を示すフローチャートである。
【０１１０】
図１７のフローチャートにおいて、まず、受付部６０１により、ノード削除にともなうノード決定指示を受け付けたか否かを判断する（ステップＳ１７０１）。ここで、ノード決定指示を受け付けるのを待って（ステップＳ１７０１：Ｎｏ）、受け付けた場合（ステップＳ１７０１：Ｙｅｓ）、第１の関連付け部６０２により、関数リスト８００の中からノードＮｙに対応するレコードを削除する（ステップＳ１７０２）。なお、関数リスト８００内のノードＩＤは、ノードＮｙに対応するレコードが削除されたあと振り直される。
【０１１１】
つぎに、第２の関連付け部６０３により、指標値リスト９００の中からノードＮｙに対応するレコードを削除する（ステップＳ１７０３）。なお、指標値リスト９００内のノードＩＤは、ノードＮｙに対応するレコードが削除されたあと振り直される。
【０１１２】
このあと、決定部６０６により、ノード／キー対応リスト１２００を参照して、ノードＮｙに対応するキー（ここでは、キーｋ［１］〜ｋ［Ｐ］と表記する）を特定する（ステップＳ１７０４）。そして、第１の算出部６０４により、データＤｐの「ｐ」を「ｐ＝１」で初期化して（ステップＳ１７０５）、キーリスト７００の中からデータＤｐのキーｋ［ｐ］および冗長度Ｒ［ｐ］を抽出する（ステップＳ１７０６）。
【０１１３】
このあと、決定部６０６により、データＤｐを格納するノードＮｉを決定するノード決定処理を実行する（ステップＳ１７０７）。そして、第１の算出部６０４により、データＤｐの「ｐ」をインクリメントして（ステップＳ１７０８）、「ｐ」が「Ｐ」より大きいか否かを判断する（ステップＳ１７０９）。
【０１１４】
ここで、「ｐ」が「Ｐ」以下の場合（ステップＳ１７０９：Ｎｏ）、ステップＳ１７０６に戻る。一方、「ｐ」が「Ｐ」より大きい場合（ステップＳ１７０９：Ｙｅｓ）、出力部６０９により、ノード／キー対応リスト１２００を出力して（ステップＳ１７１０）、本フローチャートによる一連の処理を終了する。
【０１１５】
これにより、分散データストアＤＳからのノード削除時に、削除するノードＮｙに格納されているデータＤ［１］〜Ｄ［Ｐ］を格納するノードＮｉを再決定することができる。なお、ステップＳ１７０７のノード決定処理の具体的処理手順は、図１４および図１５に示したステップＳ１３０８のノード決定処理の具体的処理手順と同様のため、ここでは説明を省略する。
【０１１６】
（ノード決定処理の具体例１）
つぎに、ノード決定装置１０１のノード決定処理の具体例１について説明する。ここでは、ノードＮｉの関数ｆ＿ｉ（）として、下記式（３）を用いる。ただし、ｉはノードＮｉのノード名、ｋｊはデータＤｊのキー、（ｉ＋ｋｊ）はノード名とキーの文字列としての結合を表す。
【０１１７】
ｆ＿ｉ（）＝ｆ（ｉ，ｋｊ）＝＜ＳＨＡ１（ｉ＋ｋｊ）の最初の３２ｂｉｔ＞
・・・（３）
【０１１８】
また、ここでは、重み付け関数ｇ（）として、下記式（４）を用いる。ただし、ｃ＿ｉはノードＮｉに関する比率である。
【０１１９】
ｇ（）＝ｇ（ｆ（ｉ，ｋｊ），ｃ＿ｉ）＝ｆ（ｉ，ｋｊ）／ｃ＿ｉ
・・・（４）
【０１２０】
（ｉ）ｎ＝５の場合
まず、分散データストアＤＳ内のノード数ｎを５（ｎ＝５）とし、ノードＮ１〜Ｎ５の中からデータＤ１〜Ｄ２０を格納するノードＮｉを決定する場合について説明する。ただし、ノードＮ１〜Ｎ５のノード名を、それぞれ”ｎ００”，”ｎ０１”，”ｎ０２”，”ｎ０３”，”ｎ０４”とする。
【０１２１】
また、各データＤ１〜Ｄ２０の冗長度Ｒ１〜Ｒ２０を、すべて「２」とする。また、ノードＮ１〜Ｎ５の比率を、それぞれ「１．２」、「１．３」、「１．３」、「１．３」、「２．０」とする。そして、ノード決定装置１０１は、キーｋｊから特定されるデータＤｊの格納先として、ノードＮ１〜Ｎ５の重み付け関数値を昇順に並び換えた場合の先頭から１番目と２番目の重み付け関数値に対応するノードＮｉを決定する。
【０１２２】
ここで、データＤ１のキーｋ１を”ｋ００”とすると、ノード決定装置１０１により、上記式（３）および式（４）を用いてノードＮ１〜Ｎ５の重み付け関数値を算出して昇順に並べ換えると、以下のようになる。
ｇ（ｆ＿ｎ０４（”ｋ００”）， ２．０） ＝ ０．０３３８９５
ｇ（ｆ＿ｎ０１（”ｋ００”）， １．３） ＝ ０．０４２６１６
ｇ（ｆ＿ｎ０２（”ｋ００”）， １．３） ＝ ０．１５１５２２
ｇ（ｆ＿ｎ０３（”ｋ００”）， １．３） ＝ ０．２５４０１６
ｇ（ｆ＿ｎ００（”ｋ００”）， １．２） ＝ ０．４３５００７
【０１２３】
この場合、ノードＮ１〜Ｎ５のうち最小の重み付け関数値をとるノードＮｉはノードＮ５（ノード名：ｎ０４）であり、つぎに小さい重み付け関数値をとるノードＮｉはノードＮ２（ノード名：ｎ０１）である。したがって、キーｋ１（”ｋ００”）から特定されるデータＤ１の格納先はノードＮ５，Ｎ２となる。
【０１２４】
つぎに、データＤ２のキーｋ２を”ｋ０１”とすると、ノード決定装置１０１により、上記式（３）および式（４）を用いてノードＮ１〜Ｎ５の重み付け関数値を算出して昇順に並び換えると、以下のようになる。
ｇ（ｆ＿ｎ０４（”ｋ０１”）， ２．０） ＝ ０．４４１２５３
ｇ（ｆ＿ｎ０１（”ｋ０１”）， １．３） ＝ ０．５１７８８７
ｇ（ｆ＿ｎ０３（”ｋ０１”）， １．３） ＝ ０．５４７２９４
ｇ（ｆ＿ｎ０２（”ｋ０１”）， １．３） ＝ ０．６７５３８０
ｇ（ｆ＿ｎ００（”ｋ０１”）， １．２） ＝ ０．６８６８５６
【０１２５】
この場合、ノードＮ１〜Ｎ５のうち最小の重み付け関数値をとるノードＮｉはノードＮ５（ノード名：ｎ０４）であり、つぎに小さい重み付け関数値をとるノードＮｉはノードＮ２（ノード名：ｎ０１）である。したがって、キーｋ２（”ｋ０１”）から特定されるデータＤ２の格納先はノードＮ５，Ｎ２となる。
【０１２６】
同様に、データＤ３〜Ｄ２０のキーｋ３〜ｋ２０を”ｋ０２”〜”ｋ１９”として、各データＤ３〜Ｄ２０の格納先を決定すると、ノード名およびキーの対応関係は、図１８に示すノード／キー対応リスト１８００のようになる。
【０１２７】
図１８は、ノード／キー対応リストの記憶内容の具体例１を示す説明図（その１）である。図１８において、ノードＮ１〜Ｎ５ごとにノード名およびキーの対応関係が示されている。ここで、ノードＮ１〜Ｎ５の比率通りにキーｋｊを分散させた場合は、ノードＮ１〜Ｎ５には、それぞれ「約６．７個」、「約７．３個」、「約７．３個」、「約７．３個」、「約１１．２個」のキーｋｊが対応付けられることになる。図１８に示す例では、ノードＮ１〜Ｎ５には、それぞれ「６個」、「７個」、「１０個」、「６個」、「１１個」のキーｋｊが対応付けられている。したがって、ノードＮ１〜Ｎ５にそれぞれ対応付けられたキーｋｊの個数は、十分にノードＮ１〜Ｎ５の比率を反映している。
【０１２８】
（ｉｉ）ｎ＝６の場合
つぎに、分散データストアＤＳ内のノード数ｎが５（ｎ＝５）から６（ｎ＝６）に増える場合について説明する。ここで、新たに追加されたノードＮ６のノード名を”ｎ０５”とする。
【０１２９】
上記同様に、データＤ１のキーｋ１を”ｋ００”として、ノード決定装置１０１により、上記式（３）および式（４）を用いてノードＮ１〜Ｎ６の重み付け関数値を算出して昇順に並び換えると、以下のようになる。
ｇ（ｆ＿ｎ０４（”ｋ００”）， ２．０） ＝ ０．０３３８９５
ｇ（ｆ＿ｎ０１（”ｋ００”）， １．３） ＝ ０．０４２６１６
ｇ（ｆ＿ｎ０５（”ｋ００”）， ２．５） ＝ ０．１３４６９０
ｇ（ｆ＿ｎ０２（”ｋ００”）， １．３） ＝ ０．１５１５２２
ｇ（ｆ＿ｎ０３（”ｋ００”）， １．３） ＝ ０．２５４０１６
ｇ（ｆ＿ｎ００（”ｋ００”）， １．２） ＝ ０．４３５００７
【０１３０】
この場合、ノード数ｎが５（ｎ＝５）の場合と同様に、ノードＮ１〜Ｎ６のうち最小の重み付け関数値をとるノードＮｉはノードＮ５（ノード名：ｎ０４）であり、つぎに小さい重み付け関数値をとるノードＮｉはノードＮ２（ノード名：ｎ０１）である。したがって、キーｋ１（”ｋ００”）から特定されるデータＤ１の格納先は変化しない。
【０１３１】
つぎに、データＤ２のキーｋ２を”ｋ０１”として、ノード決定装置１０１により、上記式（３）および式（４）を用いてノードＮ１〜Ｎ６の重み付け関数値を算出して昇順に並び換えると、以下のようになる。
ｇ（ｆ＿ｎ０５（”ｋ０１”）， ２．５） ＝ ０．１３７７３３
ｇ（ｆ＿ｎ０４（”ｋ０１”）， ２．０） ＝ ０．４４１２５３
ｇ（ｆ＿ｎ０１（”ｋ０１”）， １．３） ＝ ０．５１７８８７
ｇ（ｆ＿ｎ０３（”ｋ０１”）， １．３） ＝ ０．５４７２９４
ｇ（ｆ＿ｎ０２（”ｋ０１”）， １．３） ＝ ０．６７５３８０
ｇ（ｆ＿ｎ００（”ｋ０１”）， １．２） ＝ ０．６８６８５６
【０１３２】
この場合、ノードＮ１〜Ｎ６のうち最小の重み付け関数値をとるノードＮｉはノードＮ６（ノード名：ｎ０５）であり、つぎに小さい重み付け関数値をとるノードＮｉはノードＮ５（ノード名：ｎ０４）である。したがって、キーｋ２（”ｋ０１”）から特定されるデータＤ２の格納先はノードＮ５，Ｎ２からノードＮ６，Ｎ５に変化する。
【０１３３】
同様に、データＤ３〜Ｄ２０のキーｋ３〜ｋ２０を”ｋ０２”〜”ｋ１９”として、各データＤ３〜Ｄ２０の格納先を決定すると、ノード名およびキーの対応関係は、図１９に示すノード／キー対応リスト１９００のようになる。
【０１３４】
図１９は、ノード／キー対応リストの記憶内容の具体例１を示す説明図（その２）である。図１９において、ノードＮ１〜Ｎ６ごとにノード名およびキーの対応関係が示されている。ここで、ノード数が変化するときに移動するデータＤｊの総数（すなわち、キーｋｊの総数）が「Ｋ×Ｒ×１／（ｎ＋１）」に十分近い場合は、ノード数が変化するときのデータ移動量が最小に十分近いといえる。
【０１３５】
ここでは、「Ｋ＝２０，Ｒ＝２，ｎ＝５」のため、移動するキーｋｊの総数が「７」に近い場合はデータ移動量が最小に十分近いといえる。図１９に示す例では、ノードＮ６を追加した結果、キー”ｋ０１”，”ｋ０２”，”ｋ０５”，”ｋ０６”，”ｋ０７”，”ｋ０９”，”ｋ１３”，”ｋ１５”，”ｋ１６”，”ｋ１７”，”ｋ１９”から特定されるデータＤ２，Ｄ６，Ｄ７，Ｄ８，Ｄ１０，Ｄ１４，Ｄ２０の格納先が変化している。したがって、ノード数が変化するときのデータ移動量が最小に十分近くなっている。
【０１３６】
また、ノードＮ１〜Ｎ６の比率通りにキーｋｊを分散させた場合は、ノードＮ１〜Ｎ６には、それぞれ「約５個」、「約５．４個」、「約５．４個」、「約５．４個」、「約８．３個」、「約１０．４個」のキーｋｊが対応付けられることになる。図１９に示す例では、ノードＮ１〜Ｎ６には、それぞれ「４個」、「５個」、「６個」、「５個」、「９個」、「１１個」のキーｋｊが対応付けられている。したがって、ノードＮ１〜Ｎ６にそれぞれ対応付けられたキーｋｊの個数は、十分にノードＮ１〜Ｎ６の比率を反映している。
【０１３７】
（ノード決定処理の具体例２）
つぎに、ノード決定装置１０１のノード決定処理の具体例２について説明する。ここでは、ノードＮｉの関数ｆ＿ｉ（）として、上記式（３）を用いる。ただし、ｉはノードＮｉのノード名、ｋｊはデータＤｊのキー、（ｉ＋ｋｊ）はノード名とキーの文字列としての結合を表す。また、ここでは、重み付け関数ｇ（）として、下記式（５）を用いる。ただし、ｃ＿ｉはノードＮｉに関する比率である。なお、「ｆ（ｉ，ｋｊ）＾ｃ＿ｉ」はｆ（ｉ，ｋｊ）をｃ＿ｉで冪乗する数式である。
【０１３８】
ｇ（）＝ｇ（ｆ（ｉ，ｋｊ），ｃ＿ｉ）＝ｆ（ｉ，ｋｊ）＾ｃ＿ｉ
・・・（５）
【０１３９】
（ｉ）ｎ＝５の場合
まず、分散データストアＤＳ内のノード数ｎを５（ｎ＝５）とし、ノードＮ１〜Ｎ５の中からデータＤ１〜Ｄ２０を格納するノードＮｉを決定する場合について説明する。ただし、ノードＮ１〜Ｎ５のノード名を、それぞれ”ｎ００”，”ｎ０１”，”ｎ０２”，”ｎ０３”，”ｎ０４”とする。
【０１４０】
また、各データＤ１〜Ｄ２０の冗長度Ｒ１〜Ｒ２０を、すべて「２」とする。また、ノードＮ１〜Ｎ５の比率を、それぞれ「１．２」、「１．３」、「１．３」、「１．３」、「２．０」とする。そして、ノード決定装置１０１は、キーｋｊから特定されるデータＤｊの格納先として、ノードＮ１〜Ｎ５の重み付け関数値を昇順に並び換えた場合の先頭から１番目と２番目の重み付け関数値に対応するノードＮｉを決定する。
【０１４１】
ここで、データＤ１のキーｋ１を”ｋ００”とすると、ノード決定装置１０１により、上記式（３）および式（５）を用いてノードＮ１〜Ｎ５の重み付け関数値を算出して昇順に並べ換えると、以下のようになる。
ｇ（ｆ＿ｎ０４（”ｋ００”）， ２．０） ＝ ０．００４５９５
ｇ（ｆ＿ｎ０１（”ｋ００”）， １．３） ＝ ０．０２３２５８
ｇ（ｆ＿ｎ０２（”ｋ００”）， １．３） ＝ ０．１２０９８８
ｇ（ｆ＿ｎ０３（”ｋ００”）， １．３） ＝ ０．２３６８３４
ｇ（ｆ＿ｎ００（”ｋ００”）， １．２） ＝ ０．４５８３６７
【０１４２】
この場合、ノードＮ１〜Ｎ５のうち最小の重み付け関数値をとるノードＮｉはノードＮ５（ノード名：ｎ０４）であり、つぎに小さい重み付け関数値をとるノードＮｉはノードＮ２（ノード名：ｎ０１）である。したがって、キーｋ１（”ｋ００”）から特定されるデータＤ１の格納先はノードＮ５，Ｎ２となる。
【０１４３】
つぎに、データＤ２のキーｋ２を”ｋ０１”とすると、ノード決定装置１０１により、上記式（３）および式（５）を用いてノードＮ１〜Ｎ５の重み付け関数値を算出して昇順に並び換えると、以下のようになる。
ｇ（ｆ＿ｎ０１（”ｋ０１”）， １．３） ＝ ０．５９７９０５
ｇ（ｆ＿ｎ０３（”ｋ０１”）， １．３） ＝ ０．６４２４１１
ｇ（ｆ＿ｎ０４（”ｋ０１”）， ２．０） ＝ ０．７７８８１８
ｇ（ｆ＿ｎ００（”ｋ０１”）， １．２） ＝ ０．７９２９６９
ｇ（ｆ＿ｎ０２（”ｋ０１”）， １．３） ＝ ０．８４４３８２
【０１４４】
この場合、ノードＮ１〜Ｎ５のうち最小の重み付け関数値をとるノードＮｉはノードＮ２（ノード名：ｎ０１）であり、つぎに小さい重み付け関数値をとるノードＮｉはノードＮ４（ノード名：ｎ０３）である。したがって、キーｋ２（”ｋ０１”）から特定されるデータＤ２の格納先はノードＮ２，Ｎ４となる。
【０１４５】
同様に、データＤ３〜Ｄ２０のキーｋ３〜ｋ２０を”ｋ０２”〜”ｋ１９”として、各データＤ３〜Ｄ２０の格納先を決定すると、ノード名およびキーの対応関係は、図２０に示すノード／キー対応リスト２０００のようになる。
【０１４６】
図２０は、ノード／キー対応リストの記憶内容の具体例２を示す説明図（その１）である。図２０において、ノードＮ１〜Ｎ５ごとにノード名およびキーの対応関係が示されている。ここで、ノードＮ１〜Ｎ５の比率通りにキーｋｊを分散させた場合は、ノードＮ１〜Ｎ５には、それぞれ「約６．７個」、「約７．３個」、「約７．３個」、「約７．３個」、「約１１．２個」のキーｋが対応付けられることになる。図２０に示す例では、ノードＮ１〜Ｎ５には、それぞれ「６個」、「７個」、「９個」、「８個」、「１０個」のキーｋｊが対応付けられている。したがって、ノードＮ１〜Ｎ５にそれぞれ対応付けられたキーｋｊの個数は、十分にノードＮ１〜Ｎ５の比率を反映している。
【０１４７】
（ｉｉ）ｎ＝６の場合
つぎに、分散データストアＤＳ内のノード数ｎが５（ｎ＝５）から６（ｎ＝６）に増える場合について説明する。ここで、新たに追加されたノードＮ６のノード名を”ｎ０５”とする。
【０１４８】
上記同様に、データＤ１のキーｋ１を”ｋ００”として、ノード決定装置１０１により、上記式（３）および式（５）を用いてノードＮ１〜Ｎ６の重み付け関数値を算出して昇順に並び換えると、以下のようになる。
ｇ（ｆ＿ｎ０４（”ｋ００”）， ２．０） ＝ ０．００４５９５
ｇ（ｆ＿ｎ０１（”ｋ００”）， １．３） ＝ ０．０２３２５８
ｇ（ｆ＿ｎ０５（”ｋ００”）， ２．５） ＝ ０．０６５７９４
ｇ（ｆ＿ｎ０２（”ｋ００”）， １．３） ＝ ０．１２０９８８
ｇ（ｆ＿ｎ０３（”ｋ００”）， １．３） ＝ ０．２３６８３４
ｇ（ｆ＿ｎ００（”ｋ００”）， １．２） ＝ ０．４５８３６７
【０１４９】
この場合、ノード数ｎが５（ｎ＝５）の場合と同様に、ノードＮ１〜Ｎ６のうち最小の重み付け関数値をとるノードＮｉはノードＮ５（ノード名：ｎ０４）であり、つぎに小さい重み付け関数値をとるノードＮｉはノードＮ２（ノード名：ｎ０１）である。したがって、キーｋ１（”ｋ００”）から特定されるデータＤ１の格納先は変化しない。
【０１５０】
つぎに、データＤ２のキーｋ２を”ｋ０１”として、ノード決定装置１０１により、上記式（３）および式（５）を用いてノードＮ１〜Ｎ６の重み付け関数値を算出して昇順に並び換えると、以下のようになる。
ｇ（ｆ＿ｎ０５（”ｋ０１”）， ２．５） ＝ ０．０６９５７４
ｇ（ｆ＿ｎ０１（”ｋ０１”）， １．３） ＝ ０．５９７９０５
ｇ（ｆ＿ｎ０３（”ｋ０１”）， １．３） ＝ ０．６４２４１１
ｇ（ｆ＿ｎ０４（”ｋ０１”）， ２．０） ＝ ０．７７８８１８
ｇ（ｆ＿ｎ００（”ｋ０１”）， １．２） ＝ ０．７９２９６９
ｇ（ｆ＿ｎ０２（”ｋ０１”）， １．３） ＝ ０．８４４３８２
【０１５１】
この場合、ノードＮ１〜Ｎ６のうち最小の重み付け関数値をとるノードＮｉはノードＮ６（ノード名：ｎ０５）であり、つぎに小さい重み付け関数値をとるノードＮｉはノードＮ２（ノード名：ｎ０１）である。したがって、キーｋ２（”ｋ０１”）から特定されるデータＤ２の格納先はノードＮ２，Ｎ４からノードＮ６，Ｎ２に変化する。
【０１５２】
同様に、データＤ３〜Ｄ２０のキーｋ３〜ｋ２０を”ｋ０２”〜”ｋ１９”として、各データＤ３〜Ｄ２０の格納先を決定すると、ノード名およびキーの対応関係は、図２１に示すノード／キー対応リスト２１００のようになる。
【０１５３】
図２１は、ノード／キー対応リストの記憶内容の具体例２を示す説明図（その２）である。図２１において、ノードＮ１〜Ｎ６ごとにノード名およびキーの対応関係が示されている。ここで、ノード数が変化するときに移動するデータＤｊの総数（すなわち、キーｋｊの総数）が「Ｋ×Ｒ×１／（ｎ＋１）」に十分近い場合は、ノード数が変化するときのデータ移動量が最小に十分近いといえる。
【０１５４】
ここでは、「Ｋ＝２０，Ｒ＝２，ｎ＝５」のため、移動するキーｋｊの総数が「７」に近い場合はデータ移動量が最小に十分近いといえる。図２１に示す例では、ノードＮ６を追加した結果、キー”ｋ０１”，”ｋ０２”，”ｋ０５”，”ｋ０６”，”ｋ０７”，”ｋ０９”，”ｋ１３”，”ｋ１５”，”ｋ１６”，”ｋ１９”から特定されるデータＤ２，Ｄ３，Ｄ６，Ｄ７，Ｄ８，Ｄ１０，Ｄ１４，Ｄ１６，Ｄ１７，Ｄ２０の格納先が変化している。したがって、ノード数が変化するときのデータ移動量が最小に十分近くなっている。
【０１５５】
また、ノードＮ１〜Ｎ６の比率通りにキーｋｊを分散させた場合は、ノードＮ１〜Ｎ６には、それぞれ「約５個」、「約５．４個」、「約５．４個」、「約５．４個」、「約８．３個」、「約１０．４個」のキーｋｊが対応付けられることになる。図２１に示す例では、ノードＮ１〜Ｎ６には、それぞれ「４個」、「６個」、「５個」、「６個」、「９個」、「１０個」のキーｋｊが対応付けられている。したがって、ノードＮ１〜Ｎ６にそれぞれ対応付けられたキーｋｊの個数は、十分にノードＮ１〜Ｎ６の比率を反映している。また、重み付け関数ｇ（）として上記式（５）を採用することにより、分散するデータ数が十分に多ければ、ノードＮ１〜Ｎ６にそれぞれ対応付けられるキーｋｊの個数を、ノードＮ１〜Ｎ６の比率通りの個数にすることができる。
【０１５６】
以上説明したように、実施の形態にかかるノード決定装置１０１によれば、ノードＮｉごとに異なる関数ｆ＿ｉ（）を用意し、データＤｊのキーｋｊを引数として関数値ｆ＿ｉ（ｋ）を算出する。そして、ノード決定装置によれば、関数値ｆ＿ｉ（ｋ）とノードＮｉの比率ｃ＿ｉとを引数として得られた重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）の大小関係から、データＤｊを格納するノードＮｉを決定することができる。これにより、ノードＮｉに格納されるデータＤｊの個数は比率ｃ＿ｉの値に応じた個数になる。そのため、比率ｃ＿ｉの設定によって記憶容量の大きいノードＮｉや処理速度の速いノードＮｉにより多くのデータＤｊが格納されるようにすることができる。結果として、記憶容量の小さいノードＮｉや処理の遅いノードＮｉに過負荷がかかることを回避し、分散データストアＤＳの効率化を図ることができる。
【０１５７】
また、ノード決定装置１０１によれば、関数値ｆ＿ｉ（ｋ）とノードＮｉの比率ｃ＿ｉとを引数として得られた重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）の大小関係から、データＤｊを格納するノードＮｉを決定することができる。これにより、以降において、ノード数が増減しても元のノード間での重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）の大小関係は不変のため、追加または削除するノードＮｉ以外のノード間でデータＤｊは移動しない。
【０１５８】
また、ノード決定装置１０１によれば、ノードＮｉごとの重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）を大小関係に基づいて並び換えたあとの順序にしたがって、データＤｊを格納する所定数のノードＮｉを決定することができる。これにより、データＤｊをＲｊ個のノードＮｉに冗長して格納することができ、分散データストアＤＳの耐障害性能を向上させることができる。そして、データＤｊをＲｊ個のノードＮｉに冗長して格納する場合も、以降において、ノード数が増減しても元のノード間での重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）の大小関係は不変のため、追加または削除するノードＮｉ以外のノード間でデータＤｊは移動しない。
【０１５９】
また、ノード決定装置１０１によれば、ノードＮｉごとのノード名と関数ｆ＿ｉ（）のペアを用いて、重み付け関数ｇ（）によりデータＤｊを格納するノードＮｉを決定することができる。このため、データＤｊを格納するノードＮｉをキーｋｊごとに管理して、データＤｊを格納するノードＮｉを決定する手法に比べて、データＤｊの格納先を決定するための情報量を削減することができる。さらに、上記式（１）のような二つの引数をとる関数ｆ（）を用いる場合、関数ｆ（）とノードＮｉごとのノード名を用いてデータＤｊを格納するノードＮｉを決定することができるため、より情報量を削減することができる。
【０１６０】
また、ノード決定装置１０１によれば、関数ｆ＿ｉ（）として、関数値の頻度分布が十分に等しい関数を用いることで、重み付け関数ｇ（）の引数となる関数値ｆ＿ｉ（ｋｊ）を均等に分散させることができる。したがって、キーｋｊの値に依存してデータＤｊの格納先に偏りが生じることはない。
【０１６１】
また、ノード決定装置１０１によれば、関数ｆ＿１（）〜ｆ＿ｎ（）として、関数値の頻度分布が十分に等しい関数を用いることで、データＤｊを冗長して格納する場合の重み付け関数ｇ（）の引数となる関数値ｆ＿ｉ（ｋｊ）を均等に分散させることができる。したがって、キーｋｊの値に依存してデータＤｊを冗長した格納先に偏りが生じることはない。これにより、例えば、データＤｊをノードＮ１〜Ｎ３に冗長して格納している場合、ノードＮ１に障害が発生すると、いつもノードＮ２，Ｎ３に負荷がかかってしまうような状況を回避することができる。
【０１６２】
また、ノード決定装置１０１によれば、重み付け関数ｇ（）として、引数となる関数値ｆ＿ｉ（ｋ）の増加にともなって、重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）が増加する関数、または、重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）が減少する関数が採用される。また、ノード決定装置１０１によれば、重み付け関数ｇ（）として、引数となる指標値の増加にともなって、重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）が増加する関数、または、重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）が減少する関数が採用される。これにより、各ノードＮｉの指標値ｃ＿ｉを反映して、重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）を算出することができ、各ノードＮｉの指標値ｃ＿ｉに応じて分散データストアＤＳ内の各ノードＮｉにデータＤｊを分散させて格納することができる。
【０１６３】
また、ノード決定装置１０１によれば、重み付け関数ｇ（）として、重み付け関数の値域で定義される当該重み付け関数の値の大小関係が、ノードＮｉごとの指標値ｃ＿ｉの和に対するいずれかのノードＮｉの指標値ｃ＿ｉの割合で、いずれかのノードＮｉの重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）が最大または最小になる関係である関数を採用できる。これにより、各ノードＮｉの指標値ｃ＿ｉを反映して、重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）を算出することができ、各ノードＮｉの指標値ｃ＿ｉに応じて分散データストアＤＳ内の各ノードＮｉにデータＤｊを分散させて格納することができる。
【０１６４】
なお、本実施の形態で説明したノード決定方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーション等のコンピュータで実行することにより実現することができる。本ノード決定プログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ等のコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。また本ノード決定プログラムは、インターネット等のネットワークを介して配布してもよい。
【０１６５】
上述した実施の形態に関し、さらに以下の付記を開示する。
【０１６６】
（付記１）複数のノードの中からデータを格納するノードを決定するコンピュータに、
前記複数のノードに含まれるノードごとに異なる関数であって、当該関数の定義域が前記データを一意に特定するためのキーを含む前記関数を前記ノードごとに関連付け、
格納するデータ量を示す前記ノードごとの指標値を前記ノードごとに関連付け、
前記ノードごとの関数に前記キーをそれぞれ代入することにより、前記ノードごとの関数の値を算出し、
定義域が前記ノードごとの関数の値と前記ノードごとの指標値との組み合わせを含む重み付け関数であって、前記重み付け関数の値域で当該重み付け関数の値の大小関係が定義される前記重み付け関数に、前記ノードごとの関数の値と前記ノードごとの指標値とを代入することにより、前記重み付け関数の値を前記ノードごとに算出し、
前記ノードごとの前記重み付け関数の値の大小関係に基づいて、前記データを格納するノードを決定し、
決定結果を出力する、
処理を実行させることを特徴とするノード決定プログラム。
【０１６７】
（付記２）前記ノードごとの前記重み付け関数の値の大小関係に基づいて、前記ノードごとの前記重み付け関数の値を並び換え、
並び換えられた前記ノードごとの前記重み付け関数の値の順序にしたがって、前記複数のノードの中から所定数のノードを選択する処理を、前記コンピュータにさらに実行させ、
前記決定する処理は、選択された前記所定数のノードを、前記データを格納するノードに決定することを特徴とする付記１に記載のノード決定プログラム。
【０１６８】
（付記３）前記複数のノードに新たなノードを追加する場合、前記複数のノードに格納されているデータごとに、前記各処理を前記コンピュータに実行させることを特徴とする付記１または２に記載のノード決定プログラム。
【０１６９】
（付記４）前記複数のノードからノードを削除する場合、当該ノードに格納されているデータごとに、前記各処理を前記コンピュータに実行させることを特徴とする付記１〜３のいずれか一つに記載のノード決定プログラム。
【０１７０】
（付記５）前記関数は、前記キーを引数として与えることで固定長の乱数が得られる関数であることを特徴とする付記１〜４のいずれか一つに記載のノード決定プログラム。
【０１７１】
（付記６）前記重み付け関数は、前記指標値の増加にともなって前記重み付け関数の値が増加する関数または前記指標値の増加に対して前記重み付け関数の値が減少する関数であることを特徴とする付記１〜５のいずれか一つに記載のノード決定プログラム。
【０１７２】
（付記７）前記重み付け関数の値域で定義される当該重み付け関数の値の大小関係は、前記ノードごとの指標値の和に対するいずれかのノードの指標値の割合で、前記いずれかのノードの前記重み付け関数の値が最大または最小になる関係であることを特徴とする付記１〜６のいずれか一つに記載のノード決定プログラム。
【０１７３】
（付記８）複数のノードの中からデータを格納するノードを決定するノード決定装置において、
前記複数のノードに含まれるノードごとに異なる関数であって、当該関数の定義域が前記データを一意に特定するためのキーを含む前記関数を前記ノードごとに関連付ける第１の関連付け手段と、
格納するデータ量を示す前記ノードごとの指標値を前記ノードごとに関連付ける第２の関連付け手段と、
前記第１の関連付け手段によって関連付けられた前記ノードごとの関数に前記キーをそれぞれ代入することにより、前記ノードごとの関数の値を算出する第１の算出手段と、
定義域が前記ノードごとの関数の値と前記ノードごとの指標値との組み合わせを含む重み付け関数であって、前記重み付け関数の値域で当該重み付け関数の値の大小関係が定義される前記重み付け関数に、前記ノードごとの関数の値と前記ノードごとの指標値とを代入することにより、前記重み付け関数の値を前記ノードごとに算出する第２の算出手段と、
前記第２の算出手段によって算出された前記ノードごとの前記重み付け関数の値の大小関係に基づいて、前記データを格納するノードを決定する決定手段と、
前記決定手段によって決定された決定結果を出力する出力手段と、
を備えることを特徴とするノード決定装置。
【０１７４】
（付記９）複数のノードの中からデータを格納するノードを決定するコンピュータが、
前記複数のノードに含まれるノードごとに異なる関数であって、当該関数の定義域が前記データを一意に特定するためのキーを含む前記関数を前記ノードごとに関連付け、
格納するデータ量を示す前記ノードごとの指標値を前記ノードごとに関連付け、
前記ノードごとの関数に前記キーをそれぞれ代入することにより、前記ノードごとの関数の値を算出し、
定義域が前記ノードごとの関数の値と前記ノードごとの指標値との組み合わせを含む重み付け関数であって、前記重み付け関数の値域で当該重み付け関数の値の大小関係が定義される前記重み付け関数に、前記ノードごとの関数の値と前記ノードごとの指標値とを代入することにより、前記重み付け関数の値を前記ノードごとに算出し、
前記ノードごとの前記重み付け関数の値の大小関係に基づいて、前記データを格納するノードを決定し、
決定結果を出力する、
処理を実行することを特徴とするノード決定方法。
【符号の説明】
【０１７５】
１０１ ノード決定装置
４００ 分散システム
６０１ 受付部
６０２ 第１の関連付け部
６０３ 第２の関連付け部
６０４ 第１の算出部
６０５ 第２の算出部
６０６ 決定部
６０７ 並換部
６０８ 選択部
６０９ 出力部
７００ キーリスト
８００ 関数リスト
９００ 指標値リスト
１０００ 関数値リスト
１１００ 重み付け関数値リスト
１２００ ノード／キー対応リスト
Ｃ クライアント装置
Ｎ１〜Ｎｎ ノード
【技術分野】
【０００１】
本発明は、データを格納するノードを決定するノード決定プログラム、ノード決定装置およびノード決定方法に関する。
【背景技術】
【０００２】
ある種の分散データストアでは、データのキーごとに、キーから特定されるデータを格納するノードが異なるものがある。また、分散データストアでは、耐障害の観点から、同一キーのデータを複数のノードに冗長して格納する場合がある。さらに、データストアとしてのサービスを停止させることなく、分散データストア内のノード数を動的に増減させる場合がある。
【０００３】
このような分散データストアでは、データのキーごとに、キーから特定されるデータを格納するノードを複数のノードの中から決定することになる（いわゆる、キー空間分割）。従来の一手法として、例えば、ハッシュ関数ｈ（）を一つ決め、データのキー「ｋ」をハッシュ関数ｈ（）に与えて得られるハッシュ値ｈ（ｋ）をノード数で割った余りにより、データを格納するノードを決める手法がある。
【０００４】
また、関連する先行技術として、例えば、ノードごとに重みを設定しておき、重みに基づいてノードの担当する識別子空間（例えば、ノードの担当するハッシュ値の範囲）を分けるものがある（例えば、下記特許文献１参照。）。また、関連する先行技術として、例えば、複数の情報処理装置でファイルを分割して保持するものがある（例えば、下記特許文献２参照。）。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１０−１３４６３０号公報
【特許文献２】特許第４０６８４７３号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、上述した従来技術では、分散データストア内のノード数の増減時に、多くのデータの格納先が変わってしまう場合があり、ノード間のデータ移動が増大するという問題があった。例えば、上述した従来の一手法では、分散データストア内のノード数が１０個から１１個に増えた場合、全データの１１分の１０のデータの格納先が変わってしまう。また、キー空間の割り当てをノードごとに設定するような場合は、考慮されていない。
【０００７】
本発明の一側面では、指定した割合に応じてデータを分散させた上で、ノード数の増減時におけるノード間のデータ移動を減らすことを目的とする。
【課題を解決するための手段】
【０００８】
本発明の一側面によれば、複数のノードに含まれるノードごとに異なる関数であって、当該関数の定義域がデータを一意に特定するためのキーを含む関数をノードごとに関連付け、格納するデータ量を示すノードごとの指標値をノードごとに関連付け、関連付けられたノードごとの関数にキーをそれぞれ代入することにより、ノードごとの関数の値を算出し、定義域がノードごとの関数の値とノードごとの指標値との組み合わせを含む重み付け関数であって、重み付け関数の値域で当該重み付け関数の値の大小関係が定義される重み付け関数に、ノードごとの関数の値とノードごとの指標値とを代入することにより、重み付け関数の値をノードごとに算出し、算出されたノードごとの重み付け関数の値の大小関係に基づいて、データを格納するノードを決定し、決定された決定結果を出力するノード決定プログラム、ノード決定装置およびノード決定方法が提案される。
【発明の効果】
【０００９】
本発明の一側面によれば、指定した割合に応じてデータを分散させた上で、ノード数の増減時におけるノード間のデータ移動を減らすことができるという効果を奏する。
【図面の簡単な説明】
【００１０】
【図１】図１は、実施の形態にかかるノード決定装置のノード決定処理の一実施例を示す説明図である。
【図２】図２は、ノード追加時のデータ移動の一例を示す説明図である。
【図３】図３は、ノード削除時のデータ移動の一例を示す説明図である。
【図４】図４は、実施の形態にかかる分散システムの一例を示す説明図である。
【図５】図５は、実施の形態に用いられるコンピュータのハードウェア構成の一例を示すブロック図である。
【図６】図６は、実施の形態にかかるノード決定装置の機能的構成を示すブロック図である。
【図７】図７は、キーリストの記憶内容の一例を示す説明図である。
【図８】図８は、関数リストの記憶内容の一例を示す説明図である。
【図９】図９は、指標値リストの記憶内容の一例を示す説明図である。
【図１０】図１０は、関数値リストの記憶内容の一例を示す説明図である。
【図１１】図１１は、重み付け関数値リストの記憶内容の一例を示す説明図である。
【図１２】図１２は、ノード／キー対応リストの記憶内容の一例を示す説明図である。
【図１３】図１３は、実施の形態にかかるノード決定装置のノード決定処理手順の一例を示すフローチャートである。
【図１４】図１４は、ステップＳ１３０８のノード決定処理の具体的処理手順の一例を示すフローチャート（その１）である。
【図１５】図１５は、ステップＳ１３０８のノード決定処理の具体的処理手順の一例を示すフローチャート（その２）である。
【図１６】図１６は、ノード追加時のノード決定装置のノード決定処理手順の一例を示すフローチャートである。
【図１７】図１７は、ノード削除時のノード決定装置のノード決定処理手順の一例を示すフローチャートである。
【図１８】図１８は、ノード／キー対応リストの記憶内容の具体例１を示す説明図（その１）である。
【図１９】図１９は、ノード／キー対応リストの記憶内容の具体例１を示す説明図（その２）である。
【図２０】図２０は、ノード／キー対応リストの記憶内容の具体例２を示す説明図（その１）である。
【図２１】図２１は、ノード／キー対応リストの記憶内容の具体例２を示す説明図（その２）である。
【発明を実施するための形態】
【００１１】
以下に添付図面を参照して、本発明にかかるノード決定プログラム、ノード決定装置およびノード決定方法の好適な実施の形態を詳細に説明する。ノード決定プログラム、ノード決定装置およびノード決定方法によれば、指定された指標値に基づいて分散データストア内のノード間でデータを偏らせて分散させた上で、ノード増減時のデータ移動量を減らすことができる。
【００１２】
そのために、ノード決定プログラム、ノード決定装置およびノード決定方法によれば、データのキーから得られたノードごとの関数値（例えばハッシュ値）を、ノードごとに設定された指標値で補正した値が算出される。そして、ノード決定プログラム、ノード決定装置およびノード決定方法によれば、ノードごとの補正された値の大小関係に基づいて、データを格納するノードが決定される。
【００１３】
これにより、ノード決定プログラム、ノード決定装置およびノード決定方法によれば、ノードごとに設定された指標値に応じて、データストア内のノード間でデータを偏らせて分散させることができる。結果として、記憶容量・演算能力・回線速度などの点で高性能なノードに多くのデータを格納させることができ、分散データストアの効率化を図ることができる。そして、ノードの増減時には、増減するノード以外のノード間ではノードごとの補正された値の大小関係は変化しないため、増減するノード以外のノード間ではデータの移動が生じず、ノード増減時のデータ移動量を抑制することができる。
【００１４】
（ノード決定処理の一実施例）
図１は、実施の形態にかかるノード決定装置のノード決定処理の一実施例を示す説明図である。ここでは、分散データストア内のノードＮ１〜Ｎ３の中からデータＤを格納するノードを決定する場合を例に挙げて説明する。
【００１５】
ここで、分散データストアは、複数のノード（ここでは、ノードＮ１〜Ｎ３）にデータ群を分散して格納するシステムである。分散データストアでは、データＤとキーｋがペアになっており、キーｋを指定することでデータＤを参照することができる。データＤのキーｋは、データＤを一意に特定するための情報である。
【００１６】
図１において、まず、ノード決定装置１０１は、ノードＮ１と関数ｆ＿１（）を関連付ける。また、ノード決定装置１０１は、ノードＮ２と関数ｆ＿２（）を関連付ける。また、ノード決定装置１０１は、ノードＮ３と関数ｆ＿３（）を関連付ける。ここで、関数ｆ＿１（），ｆ＿２（），ｆ＿３（）は、それぞれ異なる関数であって、該関数の定義域がデータＤのキーｋを含む関数である。
【００１７】
つぎに、ノード決定装置１０１は、ノードＮ１と比率ｃ＿１を関連付ける。また、ノード決定装置１０１は、ノードＮ２と比率ｃ＿２を関連付ける。また、ノード決定装置１０１は、ノードＮ３と比率ｃ＿３を関連付ける。ここで、比率ｃ＿１，ｃ＿２，ｃ＿３は、ノードＮ１〜Ｎ３に分散して格納されるデータ群の中で、ノードＮ１〜Ｎ３のそれぞれに格納するデータをどの程度の量にするかを示す指標値である。
【００１８】
そして、ノード決定装置１０１は、ノードＮ１〜Ｎ３ごとの関数ｆ＿１（），ｆ＿２（），ｆ＿３（）にデータＤのキーｋをそれぞれ代入することにより、ノードＮ１〜Ｎ３ごとの関数値ｆ＿１（ｋ），ｆ＿２（ｋ），ｆ＿３（ｋ）を算出する。
【００１９】
つぎに、ノード決定装置１０１は、ノードＮ１〜Ｎ３ごとの関数値ｆ＿１（ｋ），ｆ＿２（ｋ），ｆ＿３（ｋ）と、ノードＮ１〜Ｎ３ごとの比率ｃ＿１，ｃ＿２，ｃ＿３と、を重み付け関数ｇ（）に代入する。これにより、ノード決定装置１０１は、ノードＮ１〜Ｎ３ごとの重み付け関数値ｇ（ｆ＿１（ｋ），ｃ＿１），ｇ（ｆ＿２（ｋ），ｃ＿２），ｇ（ｆ＿３（ｋ），ｃ＿３）を算出する。
【００２０】
ここで、重み付け関数ｇ（）は、該関数の定義域がノードＮ１〜Ｎ３ごとの関数値ｆ＿１（ｋ），ｆ＿２（ｋ），ｆ＿３（ｋ）とノードＮ１〜Ｎ３ごとの比率ｃ＿１，ｃ＿２，ｃ＿３との組み合わせを含み、重み付け関数の値域で該重み付け関数の値（重み付け関数値）の大小関係が定義される関数である。
【００２１】
そして、ノード決定装置１０１は、ノードＮ１〜Ｎ３ごとの重み付け関数値ｇ（ｆ＿１（ｋ），ｃ＿１），ｇ（ｆ＿２（ｋ），ｃ＿２），ｇ（ｆ＿３（ｋ），ｃ＿３）の大小関係に基づいて、データＤを格納するノードを決定する。
【００２２】
ここでは一例として、ノード決定装置１０１が、重み付け関数値ｇ（ｆ＿１（ｋ），ｃ＿１），ｇ（ｆ＿２（ｋ），ｃ＿２），ｇ（ｆ＿３（ｋ），ｃ＿３）のうち最小の重み付け関数値ｇ（ｆ＿３（ｋ），ｃ＿３）に対応するノードＮ３を、データＤを格納するノードに決定する。
【００２３】
以上説明した一実施例によれば、分散データストア内のノード数の増減時におけるノード間のデータ移動を減らすことができる。具体的には、分散データストア内のノード数が変化した場合であっても、ノードＮ１〜Ｎ３の重み付け関数値の大小関係は変化しないため、ノード間のデータ移動の発生を抑えることができる。
【００２４】
より具体的には、例えば、分散データストア内のノード数が増える場合、新たに追加されるノードの重み付け関数値が最小とならない限り、データＤの移動は発生しない。一方、分散データストア内のノード数が減る場合、ノードＮ３が削除されない限り、データＤの移動は発生しない。以下、図２および図３を用いて、ノード数の増減時におけるノード間のデータ移動について説明する。
【００２５】
（ノード追加時のデータ移動の一例）
図２は、ノード追加時のデータ移動の一例を示す説明図である。ここでは、ノードＮ３にデータＤが格納されたあと、分散データストアに新たなノードＮ４が追加される場合について説明する。ここで、ノードＮ４が追加された場合であっても、ノードＮ１〜Ｎ３の重み付け関数値ｇ（ｆ＿１（ｋ），ｃ＿１），ｇ（ｆ＿２（ｋ），ｃ＿２），ｇ（ｆ＿３（ｋ），ｃ＿３）の大小関係は変化しない。
【００２６】
したがって、新たなノードＮ４の重み付け関数値ｇ（ｆ＿４（ｋ），ｃ＿４）が算出された結果、重み付け関数値ｇ（ｆ＿１（ｋ），ｃ＿１）〜ｇ（ｆ＿４（ｋ），ｃ＿４）のうち最小となる重み付け関数値は、つぎのパターン１またはパターン２のいずれかである。パターン１は、依然としてノードＮ３の重み付け関数値ｇ（ｆ＿３（ｋ），ｃ＿３）が最小となる場合である。パターン２は、ノードＮ４の重み付け関数値ｇ（ｆ＿４（ｋ），ｃ＿４）が最小となる場合である。
【００２７】
ここで、パターン１の場合、データＤの移動は発生しない。一方、パターン２の場合、データＤを格納するためのノードとしてノードＮ４が決定され、ノードＮ３に格納されているデータＤがノードＮ４に移動することになる。すなわち、ノード追加時は、ノードＮ４の重み付け関数値ｇ（ｆ＿４（ｋ），ｃ＿４）が最小とならない限り、データＤの移動は発生しないため、ノード間のデータ移動の発生を抑えることができる。
【００２８】
（ノード削除時のデータ移動の一例）
図３は、ノード削除時のデータ移動の一例を示す説明図である。ここでは、ノードＮ３にデータＤが格納されたあと、分散データストア内のノードＮ３を削除する場合（パターン３）と、ノードＮ２を削除する場合（パターン４）について説明する。
【００２９】
パターン３の場合、ノードＮ３を削除するため、ノードＮ３に格納されているデータＤの移動が発生する。ただし、ノードＮ３が削除された場合であっても、残余のノードＮ１，Ｎ２の重み付け関数値ｇ（ｆ＿１（ｋ），ｃ＿１），ｇ（ｆ＿２（ｋ），ｃ＿２）の大小関係は変化しない。したがって、ノードＮ３に格納されているデータＤが、ノードＮ３のつぎに重み付け関数値が小さいノードＮ１に移動することになる。一方、パターン４の場合、データＤの移動は発生しない。すなわち、ノード削除時は、データＤを格納しているノードＮ３が削除されない限り、データＤの移動は発生しないため、ノード間のデータ移動の発生を抑えることができる。
【００３０】
（分散システム４００の一例）
図４は、実施の形態にかかる分散システムの一例を示す説明図である。図４において、分散システム４００は、ノード決定装置１０１と、ノードＮ１〜Ｎｎと、クライアント装置Ｃと、を含む構成である。分散システム４００において、ノード決定装置１０１、ノードＮ１〜Ｎｎおよびクライアント装置Ｃは、例えば、インターネット、ＬＡＮ（Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）、ＷＡＮ（Ｗｉｄｅ Ａｒｅａ Ｎｅｔｗｏｒｋ）などのネットワーク４１０を介して相互に通信可能に接続されている。
【００３１】
ここで、ノードＮ１〜Ｎｎは、例えば、ファイルサーバ、データベースサーバなどのサーバである。クライアント装置Ｃは、例えば、データストアのサービスの提供を受けるコンピュータである。クライアント装置Ｃは、分散データストアＤＳ内のいずれかのノードに格納されているデータＤを、データＤのキーｋを用いて参照することができる。
【００３２】
以下の説明では、複数のノードＮ１〜Ｎｎのうち任意のノードを「ノードＮｉ」と表記する（ｉ＝１，２，…，ｎ）。また、ノードＮ１〜Ｎｎのそれぞれに関する比率を「ｃ＿１〜ｃ＿ｎ」と表記し、比率ｃ＿１〜ｃ＿ｎのうちノードＮｉに関する比率を「ｃ＿ｉ」と表記する。また、格納対象となるデータ群を「データＤ１〜Ｄｍ」と表記し、データＤ１〜Ｄｍのうち任意のデータＤを「データＤｊ」と表記する（ｊ＝１，２，…，ｍ）。また、データＤｊを一意に特定するためのキーを「キーｋｊ」と表記する。
【００３３】
（コンピュータのハードウェア構成）
つぎに、実施の形態に用いられるコンピュータ（ノード決定装置１０１、ノードＮ１〜Ｎｎ、クライアント装置Ｃ）のハードウェア構成について説明する。
【００３４】
図５は、実施の形態に用いられるコンピュータのハードウェア構成の一例を示すブロック図である。図５において、コンピュータは、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）５０１と、ＲＯＭ（Ｒｅａｄ‐Ｏｎｌｙ Ｍｅｍｏｒｙ）５０２と、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）５０３と、磁気ディスクドライブ５０４と、磁気ディスク５０５と、光ディスクドライブ５０６と、光ディスク５０７と、ディスプレイ５０８と、Ｉ／Ｆ（Ｉｎｔｅｒｆａｃｅ）５０９と、キーボード５１０と、マウス５１１と、を備えている。また、各構成部はバス５００によってそれぞれ接続されている。
【００３５】
ここで、ＣＰＵ５０１は、コンピュータの全体の制御を司る。ＲＯＭ５０２は、ブートプログラムなどのプログラムを記憶している。ＲＡＭ５０３は、ＣＰＵ５０１のワークエリアとして使用される。磁気ディスクドライブ５０４は、ＣＰＵ５０１の制御にしたがって磁気ディスク５０５に対するデータのリード／ライトを制御する。磁気ディスク５０５は、磁気ディスクドライブ５０４の制御で書き込まれたデータを記憶する。
【００３６】
光ディスクドライブ５０６は、ＣＰＵ５０１の制御にしたがって光ディスク５０７に対するデータのリード／ライトを制御する。光ディスク５０７は、光ディスクドライブ５０６の制御で書き込まれたデータを記憶したり、光ディスク５０７に記憶されたデータをコンピュータに読み取らせたりする。
【００３７】
ディスプレイ５０８は、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。このディスプレイ５０８には、例えば、ＣＲＴ、ＴＦＴ液晶ディスプレイ、プラズマディスプレイなどを採用することができる。
【００３８】
Ｉ／Ｆ５０９は、通信回線を通じてＬＡＮ、ＷＡＮ、インターネットなどのネットワーク４１０に接続され、このネットワーク４１０を介して他の装置に接続される。そして、Ｉ／Ｆ５０９は、ネットワーク４１０と内部のインターフェースを司り、外部装置からのデータの入出力を制御する。Ｉ／Ｆ５０９には、例えば、モデムやＬＡＮアダプタなどを採用することができる。
【００３９】
キーボード５１０は、文字、数字、各種指示などの入力のためのキーを備え、データの入力を行う。また、タッチパネル式の入力パッドやテンキーなどであってもよい。マウス５１１は、カーソルの移動や範囲選択、あるいはウィンドウの移動やサイズの変更などを行う。ポインティングデバイスとして同様に機能を備えるものであれば、トラックボールやジョイスティックなどであってもよい。
【００４０】
（ノード決定装置１０１の機能的構成）
つぎに、実施の形態にかかるノード決定装置１０１の機能的構成について説明する。図６は、実施の形態にかかるノード決定装置の機能的構成を示すブロック図である。図６において、ノード決定装置１０１は、受付部６０１と、第１の関連付け部６０２と、第２の関連付け部６０３と、第１の算出部６０４と、第２の算出部６０５と、決定部６０６と、並換部６０７と、選択部６０８と、出力部６０９と、を含む構成である。
【００４１】
各機能部（受付部６０１〜出力部６０９）は、例えば、図５に示したＲＯＭ５０２、ＲＡＭ５０３、磁気ディスク５０５、光ディスク５０７などの記憶装置に記憶されたプログラムをＣＰＵ５０１に実行させることにより、または、Ｉ／Ｆ５０９により、その機能を実現する。また、各機能部（受付部６０１〜出力部６０９）の処理結果は、特に指定する場合を除いて、ＲＡＭ５０３、磁気ディスク５０５、光ディスク５０７などの記憶装置に記憶される。
【００４２】
受付部６０１は、格納対象となるデータＤｊに関するキー情報を受け付ける機能を有する。ここで、キー情報は、例えば、格納対象となるデータＤｊのデータ名と、キーｋｊと、冗長度Ｒｊと、を含む。データＤｊは、例えば、フォルダ、ファイル、レコード単位の情報である。キーｋｊは、例えば、ファイルのパス名やデータベース内のレコードの主キーなどの文字列である。冗長度Ｒｊは、耐障害の観点から、同一キーｋｊのデータＤｊを複数のノードＮｉに冗長して格納する場合のノード数である。
【００４３】
具体的には、例えば、受付部６０１が、図５に示したキーボード５１０やマウス５１１を用いたユーザの操作入力によりキー情報を受け付ける。また、受付部６０１が、ネットワーク４１０を介して、クライアント装置Ｃからキー情報を受け付けてもよい。受け付けたキー情報は、例えば、図７に示すキーリスト７００に記憶される。
【００４４】
図７は、キーリストの記憶内容の一例を示す説明図である。図７において、キーリスト７００は、データ名、キーおよび冗長度のフィールドを有し、各フィールドに情報を設定することで、キー情報７００−１〜７００−ｍをレコードとして記憶している。ここで、データ名とは、データＤｊの名称である。キーとは、データＤｊを一意に特定するための情報である。冗長度は、データＤｊを複数のノードＮｉに冗長して格納する場合のノード数である。
【００４５】
キーリスト７００の記憶内容は、例えば、キー情報を受け付けた場合、また、分散データストアＤＳからデータＤｊが削除された場合に、その都度更新される。キーリスト７００は、例えば、ＲＯＭ５０２、ＲＡＭ５０３、磁気ディスク５０５、光ディスク５０７などの記憶装置により、その機能を実現する。
【００４６】
図６の説明に戻り、また、受付部６０１は、ノードＮｉに関する指標値を受け付ける機能を有する。ここで、指標値とは、ノードＮ１〜Ｎｎに分散して格納されるデータＤ１〜Ｄｍの中で、ノードＮｉに格納するデータＤをどの程度の量にするかを示す値である。具体的には、例えば、指標値とは、上述した比率ｃ＿ｉであり、ノードＮｉの記憶容量・演算能力・回線速度に基づいて決定された値である。
【００４７】
具体的には、例えば、受付部６０１が、キーボード５１０やマウス５１１を用いたユーザの操作入力によりノードＮｉに関する比率ｃ＿ｉを受け付ける。また、受付部６０１が、ネットワーク４１０を介して、ノードＮｉやクライアント装置ＣからノードＮｉに関する比率ｃ＿ｉを受け付けてもよい。受け付けたノードＮｉに関する指標値は、例えば、後述する第２の関連付け部６０３により、図９に示す指標値リスト９００に記憶される。
【００４８】
また、受付部６０１は、分散データストアＤＳ内のノード数の増減にともなうノード決定指示を受け付ける機能を有する。ここで、ノード決定指示とは、ノード数の増減にともなって、データＤｊの格納先となるノードＮｉを再決定するように指示するものである。
【００４９】
具体的には、ノード追加にともなうノード決定指示には、例えば、分散データストアＤＳに追加されるノードＮｉのノード名が含まれている。また、ノード追加にともなうノード決定指示には、例えば、追加されるノードＮｉに関する比率ｃ＿ｉが含まれている。受け付けたノード決定指示に含まれるノードＮｉに関する指標値は、例えば、後述する第２の関連付け部６０３により、図９に示す指標値リスト９００に記憶される。なお、新たなノードＮｉの追加は、例えば、分散システム４００のパフォーマンスの向上などを目的として行われる。
【００５０】
また、ノード削除にともなうノード決定指示には、例えば、分散データストアＤＳから削除されるノードＮｉのノード名が含まれている。なお、ノードＮｉの削除は、例えば、ノードＮｉの故障時などに行われる。
【００５１】
具体的には、例えば、受付部６０１が、キーボード５１０やマウス５１１を用いたユーザの操作入力によりノード決定指示を受け付ける。また、受付部６０１が、ネットワーク４１０を介して、ノードＮｉやクライアント装置Ｃからノード決定指示を受け付けてもよい。
【００５２】
第１の関連付け部６０２は、ノードＮｉごとに関数を関連付ける機能を有する。以下、ノードＮｉの関数を「関数ｆ＿ｉ（）」と表記する。ここで、関数ｆ＿ｉ（）は、ノードＮｉごとに異なる関数であって、その定義域がデータＤｊのキーｋｊを含む関数である。すなわち、関数ｆ＿ｉ（）は、その定義域がキーｋｊがとりえる値の範囲を含んでいる関数である。
【００５３】
具体的には、例えば、第１の関連付け部６０２が、予め用意されている関数群Ｆの中から、任意の関数を関数ｆ＿ｉ（）として選択して、ノードＮｉと関数ｆ＿ｉ（）とを関連付ける。関連付け結果は、例えば、図８に示す関数リスト８００に記憶される。なお、関数群Ｆは、少なくともノード数ｎ分の関数の集合であり、ＲＯＭ５０２、ＲＡＭ５０３、磁気ディスク５０５、光ディスク５０７などの記憶装置に記憶されている。
【００５４】
また、第１の関連付け部６０２が、二つの引数をとる関数ｆ（）を一つ用意して、関数ｆ＿ｉ（）を、例えば下記式（１）のように定義することにしてもよい。ただし、ｉはノードＮｉのノード名、ｋｊはデータＤｊのキーである。なお、二つの引数をとる関数ｆ（）は、例えば、ＲＯＭ５０２、ＲＡＭ５０３、磁気ディスク５０５、光ディスク５０７などの記憶装置に記憶されている。
【００５５】
ｆ＿ｉ（）＝ｆ（ｉ，ｋｊ） ・・・（１）
【００５６】
また、関数ｆ＿ｉ（）としては、上述の定義域の条件を満たすものであれば、任意の関数を用いることができる。具体的には、例えば、関数ｆ＿ｉ（）として、キーｋｊを引数として与えることで固定長の乱数が得られる関数を用いることにしてもよい。より具体的には、例えば、関数ｆ＿ｉ（）として、ＳＨＡ１（Ｓｅｃｕｒｅ Ｈａｓｈ Ａｌｇｏｒｉｔｈｍ １）などのハッシュ関数を用いることにしてもよい。ＳＨＡ１は、入力が少し異なれば出力が大きく異なるという性質を有する関数である。また、例えば、キーｋｊおよびノード名「ｉ」がともに整数の場合は、関数ｆ＿ｉ（）として、キーｋｊにノード名「ｉ」を加算する「ｆ＿ｉ（）＝ｋｊ＋ｉ」という関数を用いることにしてもよい。
【００５７】
さらに、ノードＮ１〜Ｎｎの関数ｆ＿１（）〜ｆ＿ｎ（）として、関数値の頻度分布が十分に等しく、互いに独立な関数を用いることにしてもよい。具体的には、例えば、第１の関連付け部６０２が、ＳＨＡ１などのハッシュ関数を用いて、関数ｆ＿ｉ（）を下記式（２）のように定義することにしてもよい。ただし、ｃｏｎｃａｔｎａｔｅ（ｉ，ｋｊ）は、ノードＮｉのノード名「ｉ」とデータＤｊのキーｋｊを文字列として連結する関数である。
【００５８】
ｆ＿ｉ（）＝ＳＨＡ１（ｃｏｎｃａｔｎａｔｅ（ｉ，ｋｊ）） ・・・（２）
【００５９】
図８は、関数リストの記憶内容の一例を示す説明図である。図８において、関数リスト８００は、ノードＩＤ、ノード名および関数のフィールドを有し、各フィールドに情報を設定することで、関数情報８００−１〜８００−ｎをレコードとして記憶している。
【００６０】
ノードＩＤは、本明細書において説明上使用するノードＮｉの識別子である。ノード名は、ノードＮｉの名称である。関数は、ノードＮｉと関連付けられている関数ｆ＿ｉ（）である。関数リスト８００は、例えば、ＲＯＭ５０２、ＲＡＭ５０３、磁気ディスク５０５、光ディスク５０７などの記憶装置により、その機能を実現する。
【００６１】
図６の説明に戻り、第２の関連付け部６０３は、格納するデータ量を示すノードＮｉごとの指標値をノードＮｉごとに関連付ける機能を有する。具体的には、例えば、第２の関連付け部６０３は、受付部６０１によって受け付けられたノードＮｉに関する比率ｃ＿ｉを、ノードＮｉに関連付ける。関連付け結果は、例えば、図９に示す指標値リスト９００に記憶される。
【００６２】
図９は、指標値リストの記憶内容の一例を示す説明図である。図９において、指標値リスト９００は、ノードＩＤ、ノード名および指標値のフィールドを有し、各フィールドに情報を設定することで、指標値情報９００−１〜９００−ｎをレコードとして記憶している。指標値は、ノードＮｉと関連付けられている比率ｃ＿ｉである。指標値リスト９００は、例えば、ＲＯＭ５０２、ＲＡＭ５０３、磁気ディスク５０５、光ディスク５０７などの記憶装置により、その機能を実現する。
【００６３】
図６の説明に戻り、第１の算出部６０４は、関連付けられたノードＮｉごとの関数ｆ＿ｉ（）にキーｋをそれぞれ代入することにより、ノードＮｉごとの関数ｆ＿ｉ（）の値（以下、「関数値ｆ＿ｉ（ｋ）」）を算出する機能を有する。具体的には、例えば、第１の算出部６０４が、キーｋを引数として関数ｆ＿ｉ（）に与えることで、ノードＮｉごとの関数値ｆ＿ｉ（ｋ）を算出する。
【００６４】
また、関数ｆ＿ｉ（）として上記式（１）を用いる場合、第１の算出部６０４が、ノードＮｉのノード名「ｉ」およびキーｋを引数として上記式（１）に与えることで、ノードＮｉごとの関数値ｆ＿ｉ（ｋ）を算出する。算出された算出結果は、例えば、図１０に示す関数値リスト１０００に記憶される。
【００６５】
図１０は、関数値リストの記憶内容の一例を示す説明図である。図１０において、関数値リスト１０００は、ノードＩＤ、ノード名および関数値のフィールドを有し、各フィールドに情報を設定することで、関数値情報１０００−１〜１０００−ｎをレコードとして記憶している。関数値リスト１０００は、例えば、ＲＯＭ５０２、ＲＡＭ５０３、磁気ディスク５０５、光ディスク５０７などの記憶装置により、その機能を実現する。
【００６６】
図６の説明に戻り、第２の算出部６０５は、重み付け関数ｇ（）に、ノードＮｉごとの関数値ｆ＿ｉ（ｋ）とノードＮｉごとの指標値とを代入することにより、重み付け関数ｇ（）の値（以下、「重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）」）をノードＮｉごとに算出する機能を有する。
【００６７】
ここで、重み付け関数ｇ（）は、その定義域がノードＮｉごとの関数値ｆ＿ｉ（ｋ）とノードＮｉごとの指標値との組み合わせを含み、その値域で重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）の大小関係が定義される関数である。すなわち、重み付け関数ｇ（）は、その定義域がノードＮｉごとの関数値ｆ＿ｉ（ｋ）がとりうる値とノードＮｉごとの指標値とがとりうる値とを組み合わせた範囲を含んでおり、その値域で重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）の大小関係を比較することができる関数である。
【００６８】
また、重み付け関数ｇ（）は、引数となる関数値ｆ＿ｉ（ｋ）の増加にともなって、重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）が増加する関数、または、重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）が減少する関数である。また、重み付け関数ｇ（）は、引数となる指標値の増加にともなって、重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）が増加する関数、または、重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）が減少する関数である。なお、重み付け関数ｇ（）は、例えば、ＲＯＭ５０２、ＲＡＭ５０３、磁気ディスク５０５、光ディスク５０７などの記憶装置に記憶されている。
【００６９】
重み付け関数ｇ（）としては、上述の条件を満たすものであれば、任意の関数を用いることができる。具体的には、例えば、重み付け関数ｇ（）として、「ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）＝ｆ＿ｉ（ｋ）／ｃ＿ｉ」という関数を用いることにしてもよい。これにより、各ノードＮｉの指標値ｃ＿ｉを反映して、重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）を算出することができる。
【００７０】
また、重み付け関数ｇ（）としては、重み付け関数の値域で定義される当該重み付け関数の値の大小関係が、ノードＮｉごとの指標値ｃ＿ｉの和に対するいずれかのノードＮｉの指標値ｃ＿ｉの割合で、いずれかのノードＮｉの重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）が最大または最小になる関係である関数を用いることができる。
【００７１】
具体的には、例えば、重み付け関数ｇ（）として、「ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）＝ｆ＿ｉ（ｋ）＾ｃ＿ｉ」という関数を用いることにしてもよい。なお、「ｆ＿ｉ（ｋ）＾ｃ＿ｉ」はｆ＿ｉ（ｋ）をｃ＿ｉで冪乗する数式を示す。これにより、各ノードＮｉの指標値ｃ＿ｉを反映して、重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）を算出することができる。
【００７２】
具体的には、第２の算出部６０５は、重み付け関数ｇ（）に、ノードＮｉごとの関数値ｆ＿ｉ（ｋ）とノードＮｉごとの比率ｃ＿ｉとを代入することにより、重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）をノードＮｉごとに算出する。算出された算出結果は、例えば、図１１に示す重み付け関数値リスト１１００に記憶される。
【００７３】
図１１は、重み付け関数値リストの記憶内容の一例を示す説明図である。図１１において、重み付け関数値リスト１１００は、ノードＩＤ、ノード名および重み付け関数値のフィールドを有し、各フィールドに情報を設定することで、重み付け関数値情報１１００−１〜１１００−ｎをレコードとして記憶している。重み付け関数値リスト１１００は、例えば、ＲＯＭ５０２、ＲＡＭ５０３、磁気ディスク５０５、光ディスク５０７などの記憶装置により、その機能を実現する。
【００７４】
図６の説明に戻り、決定部６０６は、算出されたノードＮｉごとの重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）の大小関係に基づいて、データＤｊを格納するノードＮｉを決定する機能を有する。具体的には、例えば、決定部６０６が、重み付け関数値ｇ（ｆ＿１（ｋ），ｃ＿１）〜ｇ（ｆ＿ｎ（ｋ），ｃ＿ｎ）のうち最小（または、最大）の重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）に対応するノードＮｉを、データＤｊを格納するノードＮｉに決定する。
【００７５】
並換部６０７は、算出されたノードＮｉごとの重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）の大小関係に基づいて、ノードＮｉごとの重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）を並び換える機能を有する。具体的には、例えば、並換部６０７が、ノードＮ１〜Ｎｎの重み付け関数値ｇ（ｆ＿１（ｋ），ｃ＿１）〜ｇ（ｆ＿ｎ（ｋ），ｃ＿ｎ）が昇順（または、降順）となるように並び換える。
【００７６】
選択部６０８は、並び換えられたノードＮｉごとの重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）の順序にしたがって、ノードＮ１〜Ｎｎの中から所定数のノードＮｉを選択する機能を有する。ここで、所定数は、例えば、データＤｊの冗長度Ｒｊである。以下の説明では、並び換え後のノードＮ１〜Ｎｎの重み付け関数値ｇ（ｆ＿１（ｋ），ｃ＿１）〜ｇ（ｆ＿ｎ（ｋ），ｃ＿ｎ）を「関数値ｇ［１］〜ｇ［ｎ］」と表記する。
【００７７】
具体的には、例えば、まず、選択部６０８が、並び換え後の関数値ｇ［１］〜ｇ［ｎ］の先頭（または、後尾）からＲｊ個の関数値ｇ［１］〜ｇ［Ｒｊ］を選択する。そして、選択部６０８が、重み付け関数値リスト１１００を参照することにより、選択された関数値ｇ［１］〜ｇ［Ｒｊ］に対応するＲｊ個のノードＮｉを特定して選択する。
【００７８】
以下の説明では、選択されたＲｊ個のノードＮｉを「ノードＮ［１］〜Ｎ［Ｒｊ］」と表記する。なお、冗長度Ｒｊが「Ｒｊ＝１」の場合は、選択部６０８は、並び換え後の関数値ｇ［１］〜ｇ［ｎ］の先頭（または、後尾）から特定の順番のノードＮｉを選択することにしてもよい。
【００７９】
また、決定部６０６は、選択された所定数のノードＮｉを、データＤｊを格納するノードＮｉに決定することにしてもよい。具体的には、例えば、決定部６０６が、選択されたＲｊ個のノードＮ［１］〜Ｎ［Ｒｊ］を、データＤｊを格納するノードＮｉに決定する。決定された決定結果は、図１２に示すノード／キー対応リスト１２００に記憶される。
【００８０】
図１２は、ノード／キー対応リストの記憶内容の一例を示す説明図である。図１２において、ノード／キー対応リスト１２００は、ノードＩＤ、ノード名およびキーのフィールドを有する。各フィールドに情報を設定することで、ノードＮ１〜Ｎｎごとの対応情報１２００−１〜１２００−ｎがレコードとして記憶される。
【００８１】
一例として、ノードＮ１がデータＤ１，Ｄ３，Ｄ９を格納するノードＮｉに決定された場合、対応情報１２００−１の「キー」フィールドに、データＤ１，Ｄ３，Ｄ９のキーｋ１，ｋ３，ｋ９が設定される。また、ノードＮ２がデータＤ４，Ｄ５を格納するノードＮｉに決定された場合、対応情報１２００−２の「キー」フィールドに、データＤ４，Ｄ５のキーｋ４，ｋ５が設定される。なお、各データＤｊのキーｋｊは、例えば、キーリスト７００を参照することで特定することができる。
【００８２】
図６の説明に戻り、出力部６０９は、決定された決定結果を出力する機能を有する。具体的には、例えば、出力部６０９が、図１２に示したノード／キー対応リスト１２００を出力する。出力形式としては、例えば、ディスプレイ５０８への表示、プリンタ（不図示）への印刷出力、Ｉ／Ｆ５０９による外部装置への送信がある。また、ＲＡＭ５０３、磁気ディスク５０５、光ディスク５０７などの記憶領域に記憶することとしてもよい。
【００８３】
より具体的には、例えば、出力部６０９が、ノード間のデータ移動を制御する外部のコンピュータにノード／キー対応リスト１２００を送信してもよい。この場合、例えば、外部のコンピュータが、ノード／キー対応リスト１２００にしたがって、ノード間のデータ移動を制御することになる。また、出力部６０９が、ノード／キー対応リスト１２００にしたがって、データＤｉの移動指示をノードＮｉに送信してもよい。
【００８４】
なお、上述した説明では、ノード決定装置１０１とノードＮｉとを別体に設ける場合について説明したが、これに限らない。具体的には、例えば、ノードＮｉがノード決定装置１０１を備える構成にしてもよい。
【００８５】
（ノード決定装置１０１のノード決定処理手順）
つぎに、実施の形態にかかるノード決定装置１０１のノード決定処理手順について説明する。ここでは、ノードＮ１〜Ｎｎの中から、データＤ１〜Ｄｍの格納先となるノードＮｉを決定する場合を例に挙げて説明する。また、ここでは、受付部６０１により、キーリスト７００が作成されており、第２の関連付け部６０３により指標値リスト９００が作成されているとする。
【００８６】
図１３は、実施の形態にかかるノード決定装置のノード決定処理手順の一例を示すフローチャートである。図１３のフローチャートにおいて、まず、第１の関連付け部６０２により、ノードＮｉの「ｉ」を「ｉ＝１」で初期化して（ステップＳ１３０１）、関数群Ｆの中から関数ｆ＿ｉ（）を選択する（ステップＳ１３０２）。そして、第１の関連付け部６０２により、ノードＮｉのノード名と、選択された関数ｆ＿ｉ（）とを関連付けて関数リスト８００に登録する（ステップＳ１３０３）。
【００８７】
つぎに、第１の関連付け部６０２により、ノードＮｉの「ｉ」をインクリメントして（ステップＳ１３０４）、「ｉ」が「ｎ」より大きいか否かを判断する（ステップＳ１３０５）。ここで、「ｉ」が「ｎ」以下の場合（ステップＳ１３０５：Ｎｏ）、ステップＳ１３０２に戻る。
【００８８】
一方、「ｉ」が「ｎ」より大きい場合（ステップＳ１３０５：Ｙｅｓ）、第１の算出部６０４により、データＤｊの「ｊ」を「ｊ＝１」で初期化する（ステップＳ１３０６）。そして、第１の算出部６０４により、キーリスト７００の中からデータＤｊのキーｋｊおよび冗長度Ｒｊを抽出する（ステップＳ１３０７）。
【００８９】
このあと、決定部６０６により、データＤｊを格納するノードＮｉを決定するノード決定処理を実行する（ステップＳ１３０８）。そして、第１の算出部６０４により、データＤｊの「ｊ」をインクリメントして（ステップＳ１３０９）、「ｊ」が「ｍ」より大きいか否かを判断する（ステップＳ１３１０）。ここで、「ｊ」が「ｍ」以下の場合（ステップＳ１３１０：Ｎｏ）、ステップＳ１３０７に戻る。
【００９０】
一方、「ｊ」が「ｍ」より大きい場合（ステップＳ１３１０：Ｙｅｓ）、出力部６０９により、ノード／キー対応リスト１２００を出力して（ステップＳ１３１１）、本フローチャートによる一連の処理を終了する。
【００９１】
つぎに、図１３に示したステップＳ１３０８のノード決定処理の具体的処理手順について説明する。図１４および図１５は、ステップＳ１３０８のノード決定処理の具体的処理手順の一例を示すフローチャートである。
【００９２】
図１４のフローチャートにおいて、まず、第１の算出部６０４により、ノードＮｉの「ｉ」を「ｉ＝１」で初期化して（ステップＳ１４０１）、関数リスト８００の中からノードＮｉの関数ｆ＿ｉ（）を抽出する（ステップＳ１４０２）。
【００９３】
つぎに、第１の算出部６０４により、抽出された関数ｆ＿ｉ（）に図１３に示したステップＳ１３０７において抽出されたキーｋｊを代入して、ノードＮｉの関数値ｆ＿ｉ（ｋｊ）を算出する（ステップＳ１４０３）。そして、第１の算出部６０４により、算出されたノードＮｉの関数値ｆ＿ｉ（ｋｊ）を関数値リスト１０００に登録する（ステップＳ１４０４）。
【００９４】
つぎに、第２の算出部６０５により、関数値リスト１０００の中からノードＮｉの関数値ｆ＿ｉ（ｋｊ）を抽出する（ステップＳ１４０５）。そして、第２の算出部６０５により、指標値リスト９００の中からノードＮｉに関する比率ｃ＿ｉを抽出する（ステップＳ１４０６）。
【００９５】
つぎに、第２の算出部６０５により、重み付け関数ｇ（）に抽出されたノードＮｉの関数値ｆ＿ｉ（ｋｊ）と比率ｃ＿ｉとを代入して、ノードＮｉの重み付け関数値ｇ（ｆ＿ｉ（ｋｊ），ｃ＿ｉ）を算出する（ステップＳ１４０７）。そして、第２の算出部６０５により、算出されたノードＮｉの重み付け関数値ｇ（ｆ＿ｉ（ｋｊ），ｃ＿ｉ）を重み付け関数値リスト１１００に登録する（ステップＳ１４０８）。
【００９６】
このあと、第２の算出部６０４により、ノードＮｉの「ｉ」をインクリメントして（ステップＳ１４０９）、「ｉ」が「ｎ」より大きいか否かを判断する（ステップＳ１４１０）。ここで、「ｉ」が「ｎ」以下の場合（ステップＳ１４１０：Ｎｏ）、ステップＳ１４０２に戻る。
【００９７】
一方、「ｉ」が「ｎ」より大きい場合（ステップＳ１４１０：Ｙｅｓ）、図１５に示すステップＳ１５０１に移行する。図１５のフローチャートにおいて、並換部６０７により、重み付け関数値リスト１１００を参照して、重み付け関数値ｇ（ｆ＿１（ｋｊ），ｃ＿１）〜ｇ（ｆ＿ｎ（ｋｊ），ｃ＿ｎ）を昇順に並び換える（ステップＳ１５０１）。
【００９８】
このあと、選択部６０８により、並び換え後の重み付け関数値ｇ［１］〜ｇ［ｎ］の先頭からＲｊ個の重み付け関数値ｇ［１］〜ｇ［Ｒｊ］を選択する（ステップＳ１５０２）。ただし、Ｒｊは、図１３に示したステップＳ１３０７において抽出された冗長度Ｒｊである。つぎに、選択部６０８により、重み付け関数値リスト１１００を参照して、選択されたＲｊ個の重み付け関数値ｇ［１］〜ｇ［Ｒｊ］に対応するノードＮ［１］〜Ｎ［Ｒｊ］を選択する（ステップＳ１５０３）。
【００９９】
このあと、決定部６０６により、選択されたノードＮ［１］〜Ｎ［Ｒｊ］を、データＤｊを格納するノードＮｉに決定する（ステップＳ１５０４）。そして、決定部６０６により、決定された決定結果をノード／キー対応リスト１２００に登録して（ステップＳ１５０５）、図１３に示したステップＳ１３０９に移行する。
【０１００】
これにより、重み付け関数ｇ（）にノードＮｉごとの関数値ｆ＿ｉ（ｋｊ）とノードＮｉごとの比率ｃ＿ｉを引数として与えて得られる重み付け関数値ｇ（ｆ＿ｉ（ｋｊ），ｃ＿ｉ）の大小関係から、データＤｊを格納するノードＮｉを決定することができる。この結果、ノードＮｉごとに設定された指標値ｃ＿ｉに応じて、分散データストアＤＳ内の各ノードＮｉにデータＤｊを分散させて格納することができる。また、分散データストアＤＳ内のノード数の増減時におけるノード間のデータ移動を減らすことができる。
【０１０１】
（ノード追加時のノード決定処理手順）
つぎに、ノード追加時のノード決定装置１０１のノード決定処理手順について説明する。ここでは、分散データストアＤＳに新たに追加されるノードＮｉを「ノードＮｘ」と表記する。図１６は、ノード追加時のノード決定装置のノード決定処理手順の一例を示すフローチャートである。
【０１０２】
図１６のフローチャートにおいて、まず、受付部６０１により、ノード追加にともなうノード決定指示を受け付けたか否かを判断する（ステップＳ１６０１）。ここで、ノード決定指示を受け付けるのを待って（ステップＳ１６０１：Ｎｏ）、受け付けた場合（ステップＳ１６０１：Ｙｅｓ）、第１の関連付け部６０２により、関数群Ｆの中からノードＮｘの関数ｆ＿ｘ（）を選択する（ステップＳ１６０２）。
【０１０３】
そして、第１の関連付け部６０２により、ノードＮｘのノード名と、選択された関数ｆ＿ｘ（）とを関連付けて関数リスト８００に登録する（ステップＳ１６０３）。ただし、ノードＮｘのノード名および関数ｆ＿ｘ（）は、関数リスト８００の後尾の関数情報８００−ｎとして登録される。
【０１０４】
つぎに、第２の関連付け部６０３により、ノード決定指示に含まれるノードＮｘの比率ｃ＿ｘが取得される。そして、第２の関連付け部６０３により、ノードＮｘのノード名と、比率ｃ＿ｘとを関連付けて指標値リスト９００に登録する（ステップＳ１６０４）。ただし、ノードＮｘのノード名および比率ｃ＿ｘは、指標値リスト９００の後尾の指標値情報９００−ｎとして登録される。
【０１０５】
つぎに、決定部６０６により、ノード／キー対応リスト１２００を初期化する（ステップＳ１６０５）。そして、第１の算出部６０４により、データＤｊの「ｊ」を「ｊ＝１」で初期化して（ステップＳ１６０６）、キーリスト７００の中からデータＤｊのキーｋｊおよび冗長度Ｒｊを抽出する（ステップＳ１６０７）。
【０１０６】
このあと、決定部６０６により、データＤｊを格納するノードＮｉを決定するノード決定処理を実行する（ステップＳ１６０８）。そして、第１の算出部６０４により、データＤｊの「ｊ」をインクリメントして（ステップＳ１６０９）、「ｊ」が「ｍ」より大きいか否かを判断する（ステップＳ１６１０）。
【０１０７】
ここで、「ｊ」が「ｍ」以下の場合（ステップＳ１６１０：Ｎｏ）、ステップＳ１６０７に戻る。一方、「ｊ」が「ｍ」より大きい場合（ステップＳ１６１０：Ｙｅｓ）、出力部６０９により、ノード／キー対応リスト１２００を出力して（ステップＳ１６１１）、本フローチャートによる一連の処理を終了する。
【０１０８】
これにより、分散データストアＤＳへのノード追加時に、データＤ１〜Ｄｍを格納するノードＮｉを再決定することができる。また、ノードＮｘの追加にともなってデータ移動が発生する場合は、新たに追加されたノードＮｘにデータＤｊが移動することになるため、ノード追加時におけるパフォーマンスを効率的に向上させることができる。なお、ステップＳ１６０８のノード決定処理の具体的処理手順は、図１４および図１５に示したステップＳ１３０８のノード決定処理の具体的処理手順と同様のため、ここでは説明を省略する。
【０１０９】
（ノード削除時のノード決定処理手順）
つぎに、ノード削除時のノード決定装置１０１のノード決定処理手順について説明する。ここでは、分散データストアＤＳから削除されるノードＮｉを「ノードＮｙ」と表記する。図１７は、ノード削除時のノード決定装置のノード決定処理手順の一例を示すフローチャートである。
【０１１０】
図１７のフローチャートにおいて、まず、受付部６０１により、ノード削除にともなうノード決定指示を受け付けたか否かを判断する（ステップＳ１７０１）。ここで、ノード決定指示を受け付けるのを待って（ステップＳ１７０１：Ｎｏ）、受け付けた場合（ステップＳ１７０１：Ｙｅｓ）、第１の関連付け部６０２により、関数リスト８００の中からノードＮｙに対応するレコードを削除する（ステップＳ１７０２）。なお、関数リスト８００内のノードＩＤは、ノードＮｙに対応するレコードが削除されたあと振り直される。
【０１１１】
つぎに、第２の関連付け部６０３により、指標値リスト９００の中からノードＮｙに対応するレコードを削除する（ステップＳ１７０３）。なお、指標値リスト９００内のノードＩＤは、ノードＮｙに対応するレコードが削除されたあと振り直される。
【０１１２】
このあと、決定部６０６により、ノード／キー対応リスト１２００を参照して、ノードＮｙに対応するキー（ここでは、キーｋ［１］〜ｋ［Ｐ］と表記する）を特定する（ステップＳ１７０４）。そして、第１の算出部６０４により、データＤｐの「ｐ」を「ｐ＝１」で初期化して（ステップＳ１７０５）、キーリスト７００の中からデータＤｐのキーｋ［ｐ］および冗長度Ｒ［ｐ］を抽出する（ステップＳ１７０６）。
【０１１３】
このあと、決定部６０６により、データＤｐを格納するノードＮｉを決定するノード決定処理を実行する（ステップＳ１７０７）。そして、第１の算出部６０４により、データＤｐの「ｐ」をインクリメントして（ステップＳ１７０８）、「ｐ」が「Ｐ」より大きいか否かを判断する（ステップＳ１７０９）。
【０１１４】
ここで、「ｐ」が「Ｐ」以下の場合（ステップＳ１７０９：Ｎｏ）、ステップＳ１７０６に戻る。一方、「ｐ」が「Ｐ」より大きい場合（ステップＳ１７０９：Ｙｅｓ）、出力部６０９により、ノード／キー対応リスト１２００を出力して（ステップＳ１７１０）、本フローチャートによる一連の処理を終了する。
【０１１５】
これにより、分散データストアＤＳからのノード削除時に、削除するノードＮｙに格納されているデータＤ［１］〜Ｄ［Ｐ］を格納するノードＮｉを再決定することができる。なお、ステップＳ１７０７のノード決定処理の具体的処理手順は、図１４および図１５に示したステップＳ１３０８のノード決定処理の具体的処理手順と同様のため、ここでは説明を省略する。
【０１１６】
（ノード決定処理の具体例１）
つぎに、ノード決定装置１０１のノード決定処理の具体例１について説明する。ここでは、ノードＮｉの関数ｆ＿ｉ（）として、下記式（３）を用いる。ただし、ｉはノードＮｉのノード名、ｋｊはデータＤｊのキー、（ｉ＋ｋｊ）はノード名とキーの文字列としての結合を表す。
【０１１７】
ｆ＿ｉ（）＝ｆ（ｉ，ｋｊ）＝＜ＳＨＡ１（ｉ＋ｋｊ）の最初の３２ｂｉｔ＞
・・・（３）
【０１１８】
また、ここでは、重み付け関数ｇ（）として、下記式（４）を用いる。ただし、ｃ＿ｉはノードＮｉに関する比率である。
【０１１９】
ｇ（）＝ｇ（ｆ（ｉ，ｋｊ），ｃ＿ｉ）＝ｆ（ｉ，ｋｊ）／ｃ＿ｉ
・・・（４）
【０１２０】
（ｉ）ｎ＝５の場合
まず、分散データストアＤＳ内のノード数ｎを５（ｎ＝５）とし、ノードＮ１〜Ｎ５の中からデータＤ１〜Ｄ２０を格納するノードＮｉを決定する場合について説明する。ただし、ノードＮ１〜Ｎ５のノード名を、それぞれ”ｎ００”，”ｎ０１”，”ｎ０２”，”ｎ０３”，”ｎ０４”とする。
【０１２１】
また、各データＤ１〜Ｄ２０の冗長度Ｒ１〜Ｒ２０を、すべて「２」とする。また、ノードＮ１〜Ｎ５の比率を、それぞれ「１．２」、「１．３」、「１．３」、「１．３」、「２．０」とする。そして、ノード決定装置１０１は、キーｋｊから特定されるデータＤｊの格納先として、ノードＮ１〜Ｎ５の重み付け関数値を昇順に並び換えた場合の先頭から１番目と２番目の重み付け関数値に対応するノードＮｉを決定する。
【０１２２】
ここで、データＤ１のキーｋ１を”ｋ００”とすると、ノード決定装置１０１により、上記式（３）および式（４）を用いてノードＮ１〜Ｎ５の重み付け関数値を算出して昇順に並べ換えると、以下のようになる。
ｇ（ｆ＿ｎ０４（”ｋ００”）， ２．０） ＝ ０．０３３８９５
ｇ（ｆ＿ｎ０１（”ｋ００”）， １．３） ＝ ０．０４２６１６
ｇ（ｆ＿ｎ０２（”ｋ００”）， １．３） ＝ ０．１５１５２２
ｇ（ｆ＿ｎ０３（”ｋ００”）， １．３） ＝ ０．２５４０１６
ｇ（ｆ＿ｎ００（”ｋ００”）， １．２） ＝ ０．４３５００７
【０１２３】
この場合、ノードＮ１〜Ｎ５のうち最小の重み付け関数値をとるノードＮｉはノードＮ５（ノード名：ｎ０４）であり、つぎに小さい重み付け関数値をとるノードＮｉはノードＮ２（ノード名：ｎ０１）である。したがって、キーｋ１（”ｋ００”）から特定されるデータＤ１の格納先はノードＮ５，Ｎ２となる。
【０１２４】
つぎに、データＤ２のキーｋ２を”ｋ０１”とすると、ノード決定装置１０１により、上記式（３）および式（４）を用いてノードＮ１〜Ｎ５の重み付け関数値を算出して昇順に並び換えると、以下のようになる。
ｇ（ｆ＿ｎ０４（”ｋ０１”）， ２．０） ＝ ０．４４１２５３
ｇ（ｆ＿ｎ０１（”ｋ０１”）， １．３） ＝ ０．５１７８８７
ｇ（ｆ＿ｎ０３（”ｋ０１”）， １．３） ＝ ０．５４７２９４
ｇ（ｆ＿ｎ０２（”ｋ０１”）， １．３） ＝ ０．６７５３８０
ｇ（ｆ＿ｎ００（”ｋ０１”）， １．２） ＝ ０．６８６８５６
【０１２５】
この場合、ノードＮ１〜Ｎ５のうち最小の重み付け関数値をとるノードＮｉはノードＮ５（ノード名：ｎ０４）であり、つぎに小さい重み付け関数値をとるノードＮｉはノードＮ２（ノード名：ｎ０１）である。したがって、キーｋ２（”ｋ０１”）から特定されるデータＤ２の格納先はノードＮ５，Ｎ２となる。
【０１２６】
同様に、データＤ３〜Ｄ２０のキーｋ３〜ｋ２０を”ｋ０２”〜”ｋ１９”として、各データＤ３〜Ｄ２０の格納先を決定すると、ノード名およびキーの対応関係は、図１８に示すノード／キー対応リスト１８００のようになる。
【０１２７】
図１８は、ノード／キー対応リストの記憶内容の具体例１を示す説明図（その１）である。図１８において、ノードＮ１〜Ｎ５ごとにノード名およびキーの対応関係が示されている。ここで、ノードＮ１〜Ｎ５の比率通りにキーｋｊを分散させた場合は、ノードＮ１〜Ｎ５には、それぞれ「約６．７個」、「約７．３個」、「約７．３個」、「約７．３個」、「約１１．２個」のキーｋｊが対応付けられることになる。図１８に示す例では、ノードＮ１〜Ｎ５には、それぞれ「６個」、「７個」、「１０個」、「６個」、「１１個」のキーｋｊが対応付けられている。したがって、ノードＮ１〜Ｎ５にそれぞれ対応付けられたキーｋｊの個数は、十分にノードＮ１〜Ｎ５の比率を反映している。
【０１２８】
（ｉｉ）ｎ＝６の場合
つぎに、分散データストアＤＳ内のノード数ｎが５（ｎ＝５）から６（ｎ＝６）に増える場合について説明する。ここで、新たに追加されたノードＮ６のノード名を”ｎ０５”とする。
【０１２９】
上記同様に、データＤ１のキーｋ１を”ｋ００”として、ノード決定装置１０１により、上記式（３）および式（４）を用いてノードＮ１〜Ｎ６の重み付け関数値を算出して昇順に並び換えると、以下のようになる。
ｇ（ｆ＿ｎ０４（”ｋ００”）， ２．０） ＝ ０．０３３８９５
ｇ（ｆ＿ｎ０１（”ｋ００”）， １．３） ＝ ０．０４２６１６
ｇ（ｆ＿ｎ０５（”ｋ００”）， ２．５） ＝ ０．１３４６９０
ｇ（ｆ＿ｎ０２（”ｋ００”）， １．３） ＝ ０．１５１５２２
ｇ（ｆ＿ｎ０３（”ｋ００”）， １．３） ＝ ０．２５４０１６
ｇ（ｆ＿ｎ００（”ｋ００”）， １．２） ＝ ０．４３５００７
【０１３０】
この場合、ノード数ｎが５（ｎ＝５）の場合と同様に、ノードＮ１〜Ｎ６のうち最小の重み付け関数値をとるノードＮｉはノードＮ５（ノード名：ｎ０４）であり、つぎに小さい重み付け関数値をとるノードＮｉはノードＮ２（ノード名：ｎ０１）である。したがって、キーｋ１（”ｋ００”）から特定されるデータＤ１の格納先は変化しない。
【０１３１】
つぎに、データＤ２のキーｋ２を”ｋ０１”として、ノード決定装置１０１により、上記式（３）および式（４）を用いてノードＮ１〜Ｎ６の重み付け関数値を算出して昇順に並び換えると、以下のようになる。
ｇ（ｆ＿ｎ０５（”ｋ０１”）， ２．５） ＝ ０．１３７７３３
ｇ（ｆ＿ｎ０４（”ｋ０１”）， ２．０） ＝ ０．４４１２５３
ｇ（ｆ＿ｎ０１（”ｋ０１”）， １．３） ＝ ０．５１７８８７
ｇ（ｆ＿ｎ０３（”ｋ０１”）， １．３） ＝ ０．５４７２９４
ｇ（ｆ＿ｎ０２（”ｋ０１”）， １．３） ＝ ０．６７５３８０
ｇ（ｆ＿ｎ００（”ｋ０１”）， １．２） ＝ ０．６８６８５６
【０１３２】
この場合、ノードＮ１〜Ｎ６のうち最小の重み付け関数値をとるノードＮｉはノードＮ６（ノード名：ｎ０５）であり、つぎに小さい重み付け関数値をとるノードＮｉはノードＮ５（ノード名：ｎ０４）である。したがって、キーｋ２（”ｋ０１”）から特定されるデータＤ２の格納先はノードＮ５，Ｎ２からノードＮ６，Ｎ５に変化する。
【０１３３】
同様に、データＤ３〜Ｄ２０のキーｋ３〜ｋ２０を”ｋ０２”〜”ｋ１９”として、各データＤ３〜Ｄ２０の格納先を決定すると、ノード名およびキーの対応関係は、図１９に示すノード／キー対応リスト１９００のようになる。
【０１３４】
図１９は、ノード／キー対応リストの記憶内容の具体例１を示す説明図（その２）である。図１９において、ノードＮ１〜Ｎ６ごとにノード名およびキーの対応関係が示されている。ここで、ノード数が変化するときに移動するデータＤｊの総数（すなわち、キーｋｊの総数）が「Ｋ×Ｒ×１／（ｎ＋１）」に十分近い場合は、ノード数が変化するときのデータ移動量が最小に十分近いといえる。
【０１３５】
ここでは、「Ｋ＝２０，Ｒ＝２，ｎ＝５」のため、移動するキーｋｊの総数が「７」に近い場合はデータ移動量が最小に十分近いといえる。図１９に示す例では、ノードＮ６を追加した結果、キー”ｋ０１”，”ｋ０２”，”ｋ０５”，”ｋ０６”，”ｋ０７”，”ｋ０９”，”ｋ１３”，”ｋ１５”，”ｋ１６”，”ｋ１７”，”ｋ１９”から特定されるデータＤ２，Ｄ６，Ｄ７，Ｄ８，Ｄ１０，Ｄ１４，Ｄ２０の格納先が変化している。したがって、ノード数が変化するときのデータ移動量が最小に十分近くなっている。
【０１３６】
また、ノードＮ１〜Ｎ６の比率通りにキーｋｊを分散させた場合は、ノードＮ１〜Ｎ６には、それぞれ「約５個」、「約５．４個」、「約５．４個」、「約５．４個」、「約８．３個」、「約１０．４個」のキーｋｊが対応付けられることになる。図１９に示す例では、ノードＮ１〜Ｎ６には、それぞれ「４個」、「５個」、「６個」、「５個」、「９個」、「１１個」のキーｋｊが対応付けられている。したがって、ノードＮ１〜Ｎ６にそれぞれ対応付けられたキーｋｊの個数は、十分にノードＮ１〜Ｎ６の比率を反映している。
【０１３７】
（ノード決定処理の具体例２）
つぎに、ノード決定装置１０１のノード決定処理の具体例２について説明する。ここでは、ノードＮｉの関数ｆ＿ｉ（）として、上記式（３）を用いる。ただし、ｉはノードＮｉのノード名、ｋｊはデータＤｊのキー、（ｉ＋ｋｊ）はノード名とキーの文字列としての結合を表す。また、ここでは、重み付け関数ｇ（）として、下記式（５）を用いる。ただし、ｃ＿ｉはノードＮｉに関する比率である。なお、「ｆ（ｉ，ｋｊ）＾ｃ＿ｉ」はｆ（ｉ，ｋｊ）をｃ＿ｉで冪乗する数式である。
【０１３８】
ｇ（）＝ｇ（ｆ（ｉ，ｋｊ），ｃ＿ｉ）＝ｆ（ｉ，ｋｊ）＾ｃ＿ｉ
・・・（５）
【０１３９】
（ｉ）ｎ＝５の場合
まず、分散データストアＤＳ内のノード数ｎを５（ｎ＝５）とし、ノードＮ１〜Ｎ５の中からデータＤ１〜Ｄ２０を格納するノードＮｉを決定する場合について説明する。ただし、ノードＮ１〜Ｎ５のノード名を、それぞれ”ｎ００”，”ｎ０１”，”ｎ０２”，”ｎ０３”，”ｎ０４”とする。
【０１４０】
また、各データＤ１〜Ｄ２０の冗長度Ｒ１〜Ｒ２０を、すべて「２」とする。また、ノードＮ１〜Ｎ５の比率を、それぞれ「１．２」、「１．３」、「１．３」、「１．３」、「２．０」とする。そして、ノード決定装置１０１は、キーｋｊから特定されるデータＤｊの格納先として、ノードＮ１〜Ｎ５の重み付け関数値を昇順に並び換えた場合の先頭から１番目と２番目の重み付け関数値に対応するノードＮｉを決定する。
【０１４１】
ここで、データＤ１のキーｋ１を”ｋ００”とすると、ノード決定装置１０１により、上記式（３）および式（５）を用いてノードＮ１〜Ｎ５の重み付け関数値を算出して昇順に並べ換えると、以下のようになる。
ｇ（ｆ＿ｎ０４（”ｋ００”）， ２．０） ＝ ０．００４５９５
ｇ（ｆ＿ｎ０１（”ｋ００”）， １．３） ＝ ０．０２３２５８
ｇ（ｆ＿ｎ０２（”ｋ００”）， １．３） ＝ ０．１２０９８８
ｇ（ｆ＿ｎ０３（”ｋ００”）， １．３） ＝ ０．２３６８３４
ｇ（ｆ＿ｎ００（”ｋ００”）， １．２） ＝ ０．４５８３６７
【０１４２】
この場合、ノードＮ１〜Ｎ５のうち最小の重み付け関数値をとるノードＮｉはノードＮ５（ノード名：ｎ０４）であり、つぎに小さい重み付け関数値をとるノードＮｉはノードＮ２（ノード名：ｎ０１）である。したがって、キーｋ１（”ｋ００”）から特定されるデータＤ１の格納先はノードＮ５，Ｎ２となる。
【０１４３】
つぎに、データＤ２のキーｋ２を”ｋ０１”とすると、ノード決定装置１０１により、上記式（３）および式（５）を用いてノードＮ１〜Ｎ５の重み付け関数値を算出して昇順に並び換えると、以下のようになる。
ｇ（ｆ＿ｎ０１（”ｋ０１”）， １．３） ＝ ０．５９７９０５
ｇ（ｆ＿ｎ０３（”ｋ０１”）， １．３） ＝ ０．６４２４１１
ｇ（ｆ＿ｎ０４（”ｋ０１”）， ２．０） ＝ ０．７７８８１８
ｇ（ｆ＿ｎ００（”ｋ０１”）， １．２） ＝ ０．７９２９６９
ｇ（ｆ＿ｎ０２（”ｋ０１”）， １．３） ＝ ０．８４４３８２
【０１４４】
この場合、ノードＮ１〜Ｎ５のうち最小の重み付け関数値をとるノードＮｉはノードＮ２（ノード名：ｎ０１）であり、つぎに小さい重み付け関数値をとるノードＮｉはノードＮ４（ノード名：ｎ０３）である。したがって、キーｋ２（”ｋ０１”）から特定されるデータＤ２の格納先はノードＮ２，Ｎ４となる。
【０１４５】
同様に、データＤ３〜Ｄ２０のキーｋ３〜ｋ２０を”ｋ０２”〜”ｋ１９”として、各データＤ３〜Ｄ２０の格納先を決定すると、ノード名およびキーの対応関係は、図２０に示すノード／キー対応リスト２０００のようになる。
【０１４６】
図２０は、ノード／キー対応リストの記憶内容の具体例２を示す説明図（その１）である。図２０において、ノードＮ１〜Ｎ５ごとにノード名およびキーの対応関係が示されている。ここで、ノードＮ１〜Ｎ５の比率通りにキーｋｊを分散させた場合は、ノードＮ１〜Ｎ５には、それぞれ「約６．７個」、「約７．３個」、「約７．３個」、「約７．３個」、「約１１．２個」のキーｋが対応付けられることになる。図２０に示す例では、ノードＮ１〜Ｎ５には、それぞれ「６個」、「７個」、「９個」、「８個」、「１０個」のキーｋｊが対応付けられている。したがって、ノードＮ１〜Ｎ５にそれぞれ対応付けられたキーｋｊの個数は、十分にノードＮ１〜Ｎ５の比率を反映している。
【０１４７】
（ｉｉ）ｎ＝６の場合
つぎに、分散データストアＤＳ内のノード数ｎが５（ｎ＝５）から６（ｎ＝６）に増える場合について説明する。ここで、新たに追加されたノードＮ６のノード名を”ｎ０５”とする。
【０１４８】
上記同様に、データＤ１のキーｋ１を”ｋ００”として、ノード決定装置１０１により、上記式（３）および式（５）を用いてノードＮ１〜Ｎ６の重み付け関数値を算出して昇順に並び換えると、以下のようになる。
ｇ（ｆ＿ｎ０４（”ｋ００”）， ２．０） ＝ ０．００４５９５
ｇ（ｆ＿ｎ０１（”ｋ００”）， １．３） ＝ ０．０２３２５８
ｇ（ｆ＿ｎ０５（”ｋ００”）， ２．５） ＝ ０．０６５７９４
ｇ（ｆ＿ｎ０２（”ｋ００”）， １．３） ＝ ０．１２０９８８
ｇ（ｆ＿ｎ０３（”ｋ００”）， １．３） ＝ ０．２３６８３４
ｇ（ｆ＿ｎ００（”ｋ００”）， １．２） ＝ ０．４５８３６７
【０１４９】
この場合、ノード数ｎが５（ｎ＝５）の場合と同様に、ノードＮ１〜Ｎ６のうち最小の重み付け関数値をとるノードＮｉはノードＮ５（ノード名：ｎ０４）であり、つぎに小さい重み付け関数値をとるノードＮｉはノードＮ２（ノード名：ｎ０１）である。したがって、キーｋ１（”ｋ００”）から特定されるデータＤ１の格納先は変化しない。
【０１５０】
つぎに、データＤ２のキーｋ２を”ｋ０１”として、ノード決定装置１０１により、上記式（３）および式（５）を用いてノードＮ１〜Ｎ６の重み付け関数値を算出して昇順に並び換えると、以下のようになる。
ｇ（ｆ＿ｎ０５（”ｋ０１”）， ２．５） ＝ ０．０６９５７４
ｇ（ｆ＿ｎ０１（”ｋ０１”）， １．３） ＝ ０．５９７９０５
ｇ（ｆ＿ｎ０３（”ｋ０１”）， １．３） ＝ ０．６４２４１１
ｇ（ｆ＿ｎ０４（”ｋ０１”）， ２．０） ＝ ０．７７８８１８
ｇ（ｆ＿ｎ００（”ｋ０１”）， １．２） ＝ ０．７９２９６９
ｇ（ｆ＿ｎ０２（”ｋ０１”）， １．３） ＝ ０．８４４３８２
【０１５１】
この場合、ノードＮ１〜Ｎ６のうち最小の重み付け関数値をとるノードＮｉはノードＮ６（ノード名：ｎ０５）であり、つぎに小さい重み付け関数値をとるノードＮｉはノードＮ２（ノード名：ｎ０１）である。したがって、キーｋ２（”ｋ０１”）から特定されるデータＤ２の格納先はノードＮ２，Ｎ４からノードＮ６，Ｎ２に変化する。
【０１５２】
同様に、データＤ３〜Ｄ２０のキーｋ３〜ｋ２０を”ｋ０２”〜”ｋ１９”として、各データＤ３〜Ｄ２０の格納先を決定すると、ノード名およびキーの対応関係は、図２１に示すノード／キー対応リスト２１００のようになる。
【０１５３】
図２１は、ノード／キー対応リストの記憶内容の具体例２を示す説明図（その２）である。図２１において、ノードＮ１〜Ｎ６ごとにノード名およびキーの対応関係が示されている。ここで、ノード数が変化するときに移動するデータＤｊの総数（すなわち、キーｋｊの総数）が「Ｋ×Ｒ×１／（ｎ＋１）」に十分近い場合は、ノード数が変化するときのデータ移動量が最小に十分近いといえる。
【０１５４】
ここでは、「Ｋ＝２０，Ｒ＝２，ｎ＝５」のため、移動するキーｋｊの総数が「７」に近い場合はデータ移動量が最小に十分近いといえる。図２１に示す例では、ノードＮ６を追加した結果、キー”ｋ０１”，”ｋ０２”，”ｋ０５”，”ｋ０６”，”ｋ０７”，”ｋ０９”，”ｋ１３”，”ｋ１５”，”ｋ１６”，”ｋ１９”から特定されるデータＤ２，Ｄ３，Ｄ６，Ｄ７，Ｄ８，Ｄ１０，Ｄ１４，Ｄ１６，Ｄ１７，Ｄ２０の格納先が変化している。したがって、ノード数が変化するときのデータ移動量が最小に十分近くなっている。
【０１５５】
また、ノードＮ１〜Ｎ６の比率通りにキーｋｊを分散させた場合は、ノードＮ１〜Ｎ６には、それぞれ「約５個」、「約５．４個」、「約５．４個」、「約５．４個」、「約８．３個」、「約１０．４個」のキーｋｊが対応付けられることになる。図２１に示す例では、ノードＮ１〜Ｎ６には、それぞれ「４個」、「６個」、「５個」、「６個」、「９個」、「１０個」のキーｋｊが対応付けられている。したがって、ノードＮ１〜Ｎ６にそれぞれ対応付けられたキーｋｊの個数は、十分にノードＮ１〜Ｎ６の比率を反映している。また、重み付け関数ｇ（）として上記式（５）を採用することにより、分散するデータ数が十分に多ければ、ノードＮ１〜Ｎ６にそれぞれ対応付けられるキーｋｊの個数を、ノードＮ１〜Ｎ６の比率通りの個数にすることができる。
【０１５６】
以上説明したように、実施の形態にかかるノード決定装置１０１によれば、ノードＮｉごとに異なる関数ｆ＿ｉ（）を用意し、データＤｊのキーｋｊを引数として関数値ｆ＿ｉ（ｋ）を算出する。そして、ノード決定装置によれば、関数値ｆ＿ｉ（ｋ）とノードＮｉの比率ｃ＿ｉとを引数として得られた重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）の大小関係から、データＤｊを格納するノードＮｉを決定することができる。これにより、ノードＮｉに格納されるデータＤｊの個数は比率ｃ＿ｉの値に応じた個数になる。そのため、比率ｃ＿ｉの設定によって記憶容量の大きいノードＮｉや処理速度の速いノードＮｉにより多くのデータＤｊが格納されるようにすることができる。結果として、記憶容量の小さいノードＮｉや処理の遅いノードＮｉに過負荷がかかることを回避し、分散データストアＤＳの効率化を図ることができる。
【０１５７】
また、ノード決定装置１０１によれば、関数値ｆ＿ｉ（ｋ）とノードＮｉの比率ｃ＿ｉとを引数として得られた重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）の大小関係から、データＤｊを格納するノードＮｉを決定することができる。これにより、以降において、ノード数が増減しても元のノード間での重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）の大小関係は不変のため、追加または削除するノードＮｉ以外のノード間でデータＤｊは移動しない。
【０１５８】
また、ノード決定装置１０１によれば、ノードＮｉごとの重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）を大小関係に基づいて並び換えたあとの順序にしたがって、データＤｊを格納する所定数のノードＮｉを決定することができる。これにより、データＤｊをＲｊ個のノードＮｉに冗長して格納することができ、分散データストアＤＳの耐障害性能を向上させることができる。そして、データＤｊをＲｊ個のノードＮｉに冗長して格納する場合も、以降において、ノード数が増減しても元のノード間での重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）の大小関係は不変のため、追加または削除するノードＮｉ以外のノード間でデータＤｊは移動しない。
【０１５９】
また、ノード決定装置１０１によれば、ノードＮｉごとのノード名と関数ｆ＿ｉ（）のペアを用いて、重み付け関数ｇ（）によりデータＤｊを格納するノードＮｉを決定することができる。このため、データＤｊを格納するノードＮｉをキーｋｊごとに管理して、データＤｊを格納するノードＮｉを決定する手法に比べて、データＤｊの格納先を決定するための情報量を削減することができる。さらに、上記式（１）のような二つの引数をとる関数ｆ（）を用いる場合、関数ｆ（）とノードＮｉごとのノード名を用いてデータＤｊを格納するノードＮｉを決定することができるため、より情報量を削減することができる。
【０１６０】
また、ノード決定装置１０１によれば、関数ｆ＿ｉ（）として、関数値の頻度分布が十分に等しい関数を用いることで、重み付け関数ｇ（）の引数となる関数値ｆ＿ｉ（ｋｊ）を均等に分散させることができる。したがって、キーｋｊの値に依存してデータＤｊの格納先に偏りが生じることはない。
【０１６１】
また、ノード決定装置１０１によれば、関数ｆ＿１（）〜ｆ＿ｎ（）として、関数値の頻度分布が十分に等しい関数を用いることで、データＤｊを冗長して格納する場合の重み付け関数ｇ（）の引数となる関数値ｆ＿ｉ（ｋｊ）を均等に分散させることができる。したがって、キーｋｊの値に依存してデータＤｊを冗長した格納先に偏りが生じることはない。これにより、例えば、データＤｊをノードＮ１〜Ｎ３に冗長して格納している場合、ノードＮ１に障害が発生すると、いつもノードＮ２，Ｎ３に負荷がかかってしまうような状況を回避することができる。
【０１６２】
また、ノード決定装置１０１によれば、重み付け関数ｇ（）として、引数となる関数値ｆ＿ｉ（ｋ）の増加にともなって、重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）が増加する関数、または、重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）が減少する関数が採用される。また、ノード決定装置１０１によれば、重み付け関数ｇ（）として、引数となる指標値の増加にともなって、重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）が増加する関数、または、重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）が減少する関数が採用される。これにより、各ノードＮｉの指標値ｃ＿ｉを反映して、重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）を算出することができ、各ノードＮｉの指標値ｃ＿ｉに応じて分散データストアＤＳ内の各ノードＮｉにデータＤｊを分散させて格納することができる。
【０１６３】
また、ノード決定装置１０１によれば、重み付け関数ｇ（）として、重み付け関数の値域で定義される当該重み付け関数の値の大小関係が、ノードＮｉごとの指標値ｃ＿ｉの和に対するいずれかのノードＮｉの指標値ｃ＿ｉの割合で、いずれかのノードＮｉの重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）が最大または最小になる関係である関数を採用できる。これにより、各ノードＮｉの指標値ｃ＿ｉを反映して、重み付け関数値ｇ（ｆ＿ｉ（ｋ），ｃ＿ｉ）を算出することができ、各ノードＮｉの指標値ｃ＿ｉに応じて分散データストアＤＳ内の各ノードＮｉにデータＤｊを分散させて格納することができる。
【０１６４】
なお、本実施の形態で説明したノード決定方法は、予め用意されたプログラムをパーソナル・コンピュータやワークステーション等のコンピュータで実行することにより実現することができる。本ノード決定プログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤ等のコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。また本ノード決定プログラムは、インターネット等のネットワークを介して配布してもよい。
【０１６５】
上述した実施の形態に関し、さらに以下の付記を開示する。
【０１６６】
（付記１）複数のノードの中からデータを格納するノードを決定するコンピュータに、
前記複数のノードに含まれるノードごとに異なる関数であって、当該関数の定義域が前記データを一意に特定するためのキーを含む前記関数を前記ノードごとに関連付け、
格納するデータ量を示す前記ノードごとの指標値を前記ノードごとに関連付け、
前記ノードごとの関数に前記キーをそれぞれ代入することにより、前記ノードごとの関数の値を算出し、
定義域が前記ノードごとの関数の値と前記ノードごとの指標値との組み合わせを含む重み付け関数であって、前記重み付け関数の値域で当該重み付け関数の値の大小関係が定義される前記重み付け関数に、前記ノードごとの関数の値と前記ノードごとの指標値とを代入することにより、前記重み付け関数の値を前記ノードごとに算出し、
前記ノードごとの前記重み付け関数の値の大小関係に基づいて、前記データを格納するノードを決定し、
決定結果を出力する、
処理を実行させることを特徴とするノード決定プログラム。
【０１６７】
（付記２）前記ノードごとの前記重み付け関数の値の大小関係に基づいて、前記ノードごとの前記重み付け関数の値を並び換え、
並び換えられた前記ノードごとの前記重み付け関数の値の順序にしたがって、前記複数のノードの中から所定数のノードを選択する処理を、前記コンピュータにさらに実行させ、
前記決定する処理は、選択された前記所定数のノードを、前記データを格納するノードに決定することを特徴とする付記１に記載のノード決定プログラム。
【０１６８】
（付記３）前記複数のノードに新たなノードを追加する場合、前記複数のノードに格納されているデータごとに、前記各処理を前記コンピュータに実行させることを特徴とする付記１または２に記載のノード決定プログラム。
【０１６９】
（付記４）前記複数のノードからノードを削除する場合、当該ノードに格納されているデータごとに、前記各処理を前記コンピュータに実行させることを特徴とする付記１〜３のいずれか一つに記載のノード決定プログラム。
【０１７０】
（付記５）前記関数は、前記キーを引数として与えることで固定長の乱数が得られる関数であることを特徴とする付記１〜４のいずれか一つに記載のノード決定プログラム。
【０１７１】
（付記６）前記重み付け関数は、前記指標値の増加にともなって前記重み付け関数の値が増加する関数または前記指標値の増加に対して前記重み付け関数の値が減少する関数であることを特徴とする付記１〜５のいずれか一つに記載のノード決定プログラム。
【０１７２】
（付記７）前記重み付け関数の値域で定義される当該重み付け関数の値の大小関係は、前記ノードごとの指標値の和に対するいずれかのノードの指標値の割合で、前記いずれかのノードの前記重み付け関数の値が最大または最小になる関係であることを特徴とする付記１〜６のいずれか一つに記載のノード決定プログラム。
【０１７３】
（付記８）複数のノードの中からデータを格納するノードを決定するノード決定装置において、
前記複数のノードに含まれるノードごとに異なる関数であって、当該関数の定義域が前記データを一意に特定するためのキーを含む前記関数を前記ノードごとに関連付ける第１の関連付け手段と、
格納するデータ量を示す前記ノードごとの指標値を前記ノードごとに関連付ける第２の関連付け手段と、
前記第１の関連付け手段によって関連付けられた前記ノードごとの関数に前記キーをそれぞれ代入することにより、前記ノードごとの関数の値を算出する第１の算出手段と、
定義域が前記ノードごとの関数の値と前記ノードごとの指標値との組み合わせを含む重み付け関数であって、前記重み付け関数の値域で当該重み付け関数の値の大小関係が定義される前記重み付け関数に、前記ノードごとの関数の値と前記ノードごとの指標値とを代入することにより、前記重み付け関数の値を前記ノードごとに算出する第２の算出手段と、
前記第２の算出手段によって算出された前記ノードごとの前記重み付け関数の値の大小関係に基づいて、前記データを格納するノードを決定する決定手段と、
前記決定手段によって決定された決定結果を出力する出力手段と、
を備えることを特徴とするノード決定装置。
【０１７４】
（付記９）複数のノードの中からデータを格納するノードを決定するコンピュータが、
前記複数のノードに含まれるノードごとに異なる関数であって、当該関数の定義域が前記データを一意に特定するためのキーを含む前記関数を前記ノードごとに関連付け、
格納するデータ量を示す前記ノードごとの指標値を前記ノードごとに関連付け、
前記ノードごとの関数に前記キーをそれぞれ代入することにより、前記ノードごとの関数の値を算出し、
定義域が前記ノードごとの関数の値と前記ノードごとの指標値との組み合わせを含む重み付け関数であって、前記重み付け関数の値域で当該重み付け関数の値の大小関係が定義される前記重み付け関数に、前記ノードごとの関数の値と前記ノードごとの指標値とを代入することにより、前記重み付け関数の値を前記ノードごとに算出し、
前記ノードごとの前記重み付け関数の値の大小関係に基づいて、前記データを格納するノードを決定し、
決定結果を出力する、
処理を実行することを特徴とするノード決定方法。
【符号の説明】
【０１７５】
１０１ ノード決定装置
４００ 分散システム
６０１ 受付部
６０２ 第１の関連付け部
６０３ 第２の関連付け部
６０４ 第１の算出部
６０５ 第２の算出部
６０６ 決定部
６０７ 並換部
６０８ 選択部
６０９ 出力部
７００ キーリスト
８００ 関数リスト
９００ 指標値リスト
１０００ 関数値リスト
１１００ 重み付け関数値リスト
１２００ ノード／キー対応リスト
Ｃ クライアント装置
Ｎ１〜Ｎｎ ノード
【特許請求の範囲】
【請求項１】
複数のノードの中からデータを格納するノードを決定するコンピュータに、
前記複数のノードに含まれるノードごとに異なる関数であって、当該関数の定義域が前記データを一意に特定するためのキーを含む前記関数を前記ノードごとに関連付け、
格納するデータ量を示す前記ノードごとの指標値を前記ノードごとに関連付け、
前記ノードごとの関数に前記キーをそれぞれ代入することにより、前記ノードごとの関数の値を算出し、
定義域が前記ノードごとの関数の値と前記ノードごとの指標値との組み合わせを含む重み付け関数であって、前記重み付け関数の値域で当該重み付け関数の値の大小関係が定義される前記重み付け関数に、前記ノードごとの関数の値と前記ノードごとの指標値とを代入することにより、前記重み付け関数の値を前記ノードごとに算出し、
前記ノードごとの前記重み付け関数の値の大小関係に基づいて、前記データを格納するノードを決定し、
決定結果を出力する、
処理を実行させることを特徴とするノード決定プログラム。
【請求項２】
前記ノードごとの前記重み付け関数の値の大小関係に基づいて、前記ノードごとの前記重み付け関数の値を並び換え、
並び換えられた前記ノードごとの前記重み付け関数の値の順序にしたがって、前記複数のノードの中から所定数のノードを選択する処理を、前記コンピュータにさらに実行させ、
前記決定する処理は、選択された前記所定数のノードを、前記データを格納するノードに決定することを特徴とする請求項１に記載のノード決定プログラム。
【請求項３】
前記複数のノードに新たなノードを追加する場合、前記複数のノードに格納されているデータごとに、前記各処理を前記コンピュータに実行させることを特徴とする請求項１または２に記載のノード決定プログラム。
【請求項４】
前記複数のノードからノードを削除する場合、当該ノードに格納されているデータごとに、前記各処理を前記コンピュータに実行させることを特徴とする請求項１〜３のいずれか一つに記載のノード決定プログラム。
【請求項５】
複数のノードの中からデータを格納するノードを決定するノード決定装置において、
前記複数のノードに含まれるノードごとに異なる関数であって、当該関数の定義域が前記データを一意に特定するためのキーを含む前記関数を前記ノードごとに関連付ける第１の関連付け手段と、
格納するデータ量を示す前記ノードごとの指標値を前記ノードごとに関連付ける第２の関連付け手段と、
前記第１の関連付け手段によって関連付けられた前記ノードごとの関数に前記キーをそれぞれ代入することにより、前記ノードごとの関数の値を算出する第１の算出手段と、
定義域が前記ノードごとの関数の値と前記ノードごとの指標値との組み合わせを含む重み付け関数であって、前記重み付け関数の値域で当該重み付け関数の値の大小関係が定義される前記重み付け関数に、前記ノードごとの関数の値と前記ノードごとの指標値とを代入することにより、前記重み付け関数の値を前記ノードごとに算出する第２の算出手段と、
前記第２の算出手段によって算出された前記ノードごとの前記重み付け関数の値の大小関係に基づいて、前記データを格納するノードを決定する決定手段と、
前記決定手段によって決定された決定結果を出力する出力手段と、
を備えることを特徴とするノード決定装置。
【請求項６】
複数のノードの中からデータを格納するノードを決定するコンピュータが、
前記複数のノードに含まれるノードごとに異なる関数であって、当該関数の定義域が前記データを一意に特定するためのキーを含む前記関数を前記ノードごとに関連付け、
格納するデータ量を示す前記ノードごとの指標値を前記ノードごとに関連付け、
前記ノードごとの関数に前記キーをそれぞれ代入することにより、前記ノードごとの関数の値を算出し、
定義域が前記ノードごとの関数の値と前記ノードごとの指標値との組み合わせを含む重み付け関数であって、前記重み付け関数の値域で当該重み付け関数の値の大小関係が定義される前記重み付け関数に、前記ノードごとの関数の値と前記ノードごとの指標値とを代入することにより、前記重み付け関数の値を前記ノードごとに算出し、
前記ノードごとの前記重み付け関数の値の大小関係に基づいて、前記データを格納するノードを決定し、
決定結果を出力する、
処理を実行することを特徴とするノード決定方法。
【請求項１】
複数のノードの中からデータを格納するノードを決定するコンピュータに、
前記複数のノードに含まれるノードごとに異なる関数であって、当該関数の定義域が前記データを一意に特定するためのキーを含む前記関数を前記ノードごとに関連付け、
格納するデータ量を示す前記ノードごとの指標値を前記ノードごとに関連付け、
前記ノードごとの関数に前記キーをそれぞれ代入することにより、前記ノードごとの関数の値を算出し、
定義域が前記ノードごとの関数の値と前記ノードごとの指標値との組み合わせを含む重み付け関数であって、前記重み付け関数の値域で当該重み付け関数の値の大小関係が定義される前記重み付け関数に、前記ノードごとの関数の値と前記ノードごとの指標値とを代入することにより、前記重み付け関数の値を前記ノードごとに算出し、
前記ノードごとの前記重み付け関数の値の大小関係に基づいて、前記データを格納するノードを決定し、
決定結果を出力する、
処理を実行させることを特徴とするノード決定プログラム。
【請求項２】
前記ノードごとの前記重み付け関数の値の大小関係に基づいて、前記ノードごとの前記重み付け関数の値を並び換え、
並び換えられた前記ノードごとの前記重み付け関数の値の順序にしたがって、前記複数のノードの中から所定数のノードを選択する処理を、前記コンピュータにさらに実行させ、
前記決定する処理は、選択された前記所定数のノードを、前記データを格納するノードに決定することを特徴とする請求項１に記載のノード決定プログラム。
【請求項３】
前記複数のノードに新たなノードを追加する場合、前記複数のノードに格納されているデータごとに、前記各処理を前記コンピュータに実行させることを特徴とする請求項１または２に記載のノード決定プログラム。
【請求項４】
前記複数のノードからノードを削除する場合、当該ノードに格納されているデータごとに、前記各処理を前記コンピュータに実行させることを特徴とする請求項１〜３のいずれか一つに記載のノード決定プログラム。
【請求項５】
複数のノードの中からデータを格納するノードを決定するノード決定装置において、
前記複数のノードに含まれるノードごとに異なる関数であって、当該関数の定義域が前記データを一意に特定するためのキーを含む前記関数を前記ノードごとに関連付ける第１の関連付け手段と、
格納するデータ量を示す前記ノードごとの指標値を前記ノードごとに関連付ける第２の関連付け手段と、
前記第１の関連付け手段によって関連付けられた前記ノードごとの関数に前記キーをそれぞれ代入することにより、前記ノードごとの関数の値を算出する第１の算出手段と、
定義域が前記ノードごとの関数の値と前記ノードごとの指標値との組み合わせを含む重み付け関数であって、前記重み付け関数の値域で当該重み付け関数の値の大小関係が定義される前記重み付け関数に、前記ノードごとの関数の値と前記ノードごとの指標値とを代入することにより、前記重み付け関数の値を前記ノードごとに算出する第２の算出手段と、
前記第２の算出手段によって算出された前記ノードごとの前記重み付け関数の値の大小関係に基づいて、前記データを格納するノードを決定する決定手段と、
前記決定手段によって決定された決定結果を出力する出力手段と、
を備えることを特徴とするノード決定装置。
【請求項６】
複数のノードの中からデータを格納するノードを決定するコンピュータが、
前記複数のノードに含まれるノードごとに異なる関数であって、当該関数の定義域が前記データを一意に特定するためのキーを含む前記関数を前記ノードごとに関連付け、
格納するデータ量を示す前記ノードごとの指標値を前記ノードごとに関連付け、
前記ノードごとの関数に前記キーをそれぞれ代入することにより、前記ノードごとの関数の値を算出し、
定義域が前記ノードごとの関数の値と前記ノードごとの指標値との組み合わせを含む重み付け関数であって、前記重み付け関数の値域で当該重み付け関数の値の大小関係が定義される前記重み付け関数に、前記ノードごとの関数の値と前記ノードごとの指標値とを代入することにより、前記重み付け関数の値を前記ノードごとに算出し、
前記ノードごとの前記重み付け関数の値の大小関係に基づいて、前記データを格納するノードを決定し、
決定結果を出力する、
処理を実行することを特徴とするノード決定方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【公開番号】特開２０１３−１０９６７２（Ｐ２０１３−１０９６７２Ａ）
【公開日】平成２５年６月６日（２０１３．６．６）
【国際特許分類】
【出願番号】特願２０１１−２５５５５６（Ｐ２０１１−２５５５５６）
【出願日】平成２３年１１月２２日（２０１１．１１．２２）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【公開日】平成２５年６月６日（２０１３．６．６）
【国際特許分類】
【出願日】平成２３年１１月２２日（２０１１．１１．２２）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
[ Back to top ]