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