(57)【要約】本発明は、複数のノードによりデータを処理するシステムにおいて、データを担当するノード（担当ノード）の冗長化を実現しながら、より高速に担当ノードまでデータを転送できる技術を提供する。  データ処理装置１は、処理データ転送部１２と、管理キー記憶部１５と、ルーティングテーブル記憶部１７とを備える。管理キー記憶部１５は、ｍ桁（ｍは正の整数）の数値である管理キーが採り得る数値範囲（キー空間）を複数に区分することにより設定された複数の区間のうち、自装置が担当する担当区間に含まれる前記管理キーの範囲を表す情報を記憶する。ルーティングテーブル記憶部１７は、前記管理キーとしての数値の基数のｎ乗（ｎはｍ未満の正の整数）を多重度とした場合に、多重度に基づいて定まる転送候補の他装置のアドレスと、当該他装置の担当区間を表す情報とを含む装置情報を記憶する。処理データ転送部１２は、処理対象の処理データと、当該処理データに関連付けられたｍ桁の数値である基準キーとを受信した場合に、前記基準キーが自装置の前記担当区間の範囲内であれば、前記処理データを自装置で処理すると判断し、前記基準キーが自装置の前記担当区間外であれば、前記基準キーにおける下位ｊ桁（ｊ＝ｍ−ｎ）が一致する数値（生成キー）を担当する他装置に向けて、前記ルーティングテーブル記憶部に格納されている前記装置情報に基づき前記処理データを他装置に転送する。
2013027784.tif 000002
【特許請求の範囲】
【請求項１】
ｍ桁（ｍは正の整数）の数値である管理キーが採り得る数値範囲（キー空間）を複数に区分することにより設定された複数の区間のうち、自装置が担当する担当区間に含まれる前記管理キーの範囲を表す情報を記憶する管理キー記憶手段と、
前記管理キーとしての数値の基数のｎ乗（ｎはｍ未満の正の整数）を多重度とした場合に、前記キー空間を前記多重度の個数に等分割あるいは略等分割することにより設定された複数の範囲のうち、自装置の前記担当区間を含む前記範囲内の前記管理キーを担当する他装置のアドレスと、当該他装置の担当区間を表す情報とを含む装置情報を記憶するルーティングテーブル記憶手段と、
処理対象の処理データと、当該処理データに関連付けられたｍ桁の数値である基準キーとを受信した場合に、前記基準キーが自装置の前記担当区間の範囲内であれば、前記処理データを自装置で処理すると判断し、前記基準キーが自装置の前記担当区間外であれば、前記基準キーにおける下位ｊ桁（ｊ＝ｍ−ｎ）が一致する数値（生成キー）を担当する他装置に向けて、前記ルーティングテーブル記憶手段に格納されている前記装置情報に基づき前記処理データを他装置に転送する処理データ転送手段と
を有するデータ処理装置。
【請求項２】
前記キー空間において、或る区間ｐから或る管理キーｋまでの距離を、前記区間ｐ内における或る管理キーから前記管理キーｋまでの距離のうちの最小の距離を用いるとした場合に、前記ルーティングテーブル記憶手段は、自装置の前記担当区間からの距離が１から［前記基数のｊ乗−自装置の前記担当区間の長さ］までの範囲である転送範囲内の管理キーを担当する他装置の装置情報を格納し、
前記処理データ転送手段は、前記生成キーを担当する他装置のうち、自装置の前記担当区間からの距離が最小の前記生成キーを担当する他装置に向けて、前記処理データを転送する請求項１記載のデータ処理装置。
【請求項３】
前記ルーティングテーブル記憶手段には、前記転送範囲に含まれる前記管理キーを担当する全ての他装置における前記装置情報が格納されている請求項２記載のデータ処理装置。
【請求項４】
前記ルーティングテーブル記憶手段には、前記転送範囲に含まれる前記管理キーのうち自装置の前記担当区間の最小値からの距離が前記基数のｉ（ｉ＝０，１，２・・・）乗である前記管理キーを担当する前記他装置における前記装置情報が格納されている請求項２記載のデータ処理装置。
【請求項５】
前記他装置の担当区間が変更された場合に、該他装置の装置情報がルーティングテーブル記憶手段に格納され、かつ、変更後の前記他装置の担当区間が、自装置の前記転送範囲とオーバラップしない場合には、該他装置の装置情報を削除し、また、
前記担当区間が変更された他装置の装置情報がルーティングテーブル記憶手段に格納されておらず、かつ、変更後の前記他装置の担当区間が、自装置の前記転送範囲とオーバラップする場合には、該他装置の装置情報をルーティングテーブル記憶手段に登録するルーティングテーブル更新手段をさらに備える請求項３に記載のデータ処理装置。
【請求項６】
前記他装置の担当区間が変更された場合に、該他装置の装置情報がルーティングテーブル記憶手段に格納され、かつ、変更後の前記他装置の担当区間が、自装置の前記転送範囲内において自装置の前記担当区間の最小値からの距離が基数のｉ乗であるいずれの管理キーも含まない場合には、該他装置の装置情報をルーティングテーブル記憶手段から削除し、また、前記担当区間が変更された他装置の装置情報がルーティングテーブル記憶手段に格納されておらず、かつ、変更後の前記他装置の担当区間が、自装置の前記転送範囲内において自装置の担当区間の最小値からの距離が基数のｉ乗であるいずれかの管理キーを含む場合には、該他装置の装置情報をルーティングテーブル記憶手段に登録するルーティングテーブル更新手段をさらに備える請求項４に記載のデータ処理装置。
【請求項７】
前記処理データを処理する際に用いる格納データを記憶する格納データ記憶手段と、
前記格納データを用いて、前記処理データを処理する処理手段と、
前記格納データを基準キーと共に受信した場合に、その基準キーと前記下位ｊ桁が一致する生成キーのうち、自装置の担当区間内の生成キーがあれば、前記格納データを前記格納データ記憶手段に登録し、前記生成キーのうち、自装置の担当区間外の生成キーがあれば、当該生成キーを担当する前記他装置に向けて、前記格納データを転送する格納データ転送手段と、
をさらに備える請求項１乃至請求項６の何れか１項記載のデータ処理装置。
【請求項８】
請求項１乃至請求項７の何れか１項記載のデータ処理装置を備え、
外部または他のデータ処理装置から処理対象の処理データを受信した前記データ処理装置は、前記処理データに関連付けられている基準キーに基づいた生成キーが自装置の担当区間内である場合には、前記処理データを処理対象と判断し、また、前記生成キーが自装置の担当区間外である場合には、前記生成キーを担当する前記データ処理装置に向けて、ルーティングテーブル記憶手段に記憶されている装置情報に基づいて、前記処理データを転送するデータ分散処理システム。
【請求項９】
ｍ桁（ｍは正の整数）の数値である管理キーが採り得る数値範囲（キー空間）を複数に区分することにより設定された複数の区間のうち、自装置が担当する担当区間に含まれる前記管理キーの範囲を表す情報をコンピュータ装置が記憶し、
前記管理キーとしての数値の基数のｎ乗（ｎはｍ未満の正の整数）を多重度とした場合に、前記キー空間を前記多重度の個数に等分割あるいは略等分割することにより設定された複数の範囲のうち、自装置の前記担当区間を含む前記範囲内の前記管理キーを担当する他装置のアドレスと、当該他装置の担当区間を表す情報とを含む装置情報をコンピュータ装置が記憶し、
処理対象の処理データと、当該処理データに関連付けられたｍ桁の数値である基準キーとを受信した場合に、前記基準キーが自装置の前記担当区間の範囲内であれば、前記処理データを自装置で処理するとコンピュータ装置が判断し、
前記基準キーが自装置の前記担当区間外であれば、前記基準キーにおける下位ｊ桁（ｊ＝ｍ−ｎ）が一致する数値（生成キー）を担当する他装置に向けて、前記装置情報に基づいて前記処理データをコンピュータ装置が他装置に転送するデータ処理方法。
【請求項１０】
ｍ桁（ｍは正の整数）の数値である管理キーが採り得る数値範囲（キー空間）を複数に区分することにより設定された複数の区間のうち、自装置が担当する担当区間に含まれる前記管理キーの範囲を表す情報を記憶する処理と、
前記管理キーとしての数値の基数のｎ乗（ｎはｍ未満の正の整数）を多重度とした場合に、前記キー空間を前記多重度の個数に等分割あるいは略等分割することにより設定された複数の範囲のうち、自装置の前記担当区間を含む前記範囲内の前記管理キーを担当する他装置のアドレスと、当該他装置の担当区間を表す情報とを含む装置情報を記憶する処理と、
処理対象の処理データと、当該処理データに関連付けられたｍ桁の数値である基準キーとを受信した場合に、前記基準キーが自装置の前記担当区間の範囲内であれば、前記処理データを自装置で処理するとコンピュータ装置が判断し、前記基準キーが自装置の前記担当区間外であれば、前記基準キーにおける下位ｊ桁（ｊ＝ｍ−ｎ）が一致する数値（生成キー）を担当する他装置に向けて、前記装置情報に基づいて前記処理データを他装置に転送する処理と
をコンピュータ装置に実行させるコンピュータプログラムを記憶しているプログラム記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データを複数のノードにより処理するデータ分散処理の技術に関する。
【背景技術】
【０００２】
複数のノードによってデータを処理するデータ分散処理システムが特許文献１に示されている。特許文献１の技術では、管理対象のデータに関連付けられているキーの値における分布範囲が複数の区間に分割され、これら区間が各ノードに割り当てられている。
非特許文献１には、データ分散処理システムに関する技術である、管理対象のデータにおける複製フレームワークが示されている。非特許文献１の技術では、データに対応するキーの少なくとも先頭ｉビット（ｉは正の整数）と一致する先頭ｉビットを持つキーが割り当てられたノードに、当該データが配置される。当該技術では、そのビット数ｉは、例えばデータの人気によって算出される。この技術では、各ノードが開始するデータの検索は、高々ｉホップで終了する。
また、非特許文献２には、データ分散処理システムにおけるデータ検索プロトコル（Ｃｈｏｒｄ）が記載されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開平０５−２４２０４９号公報
【非特許文献】
【０００４】
【非特許文献１】Ｖ．Ｒａｍａｓｕｂｒａｍａｎｉａｎ  ａｎｄ  Ｅ．Ｇ．Ｓｉｒｅｒ，“Ｂｅｅｈｉｖｅ：Ｅｘｐｌｏｉｔｉｎｇ  Ｐｏｗｅｒ  Ｌａｗ  Ｑｕｅｒｙ  Ｄｉｓｔｒｉｂｕｔｉｏｎｓ  ｆｏｒ  ０（１）  Ｌｏｏｋｕｐ  Ｐｅｒｆｏｒｍａｎｃｅ  ｉｎ  Ｐｅｅｒ  ｔｏ  Ｐｅｅｒ  Ｏｖｅｒｌａｙｓ”，ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  １ｓｔ  ＵＳＥＮＩＸ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｎｅｔｗｏｒｋｅｄ  Ｓｙｓｔｅｍｓ  Ｄｅｓｉｇｎ  ａｎｄ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ，２００４
【非特許文献２】Ｉｏｎ  Ｓｔｏｉｃａ，Ｒｏｂｅｒｔ  Ｍｏｒｒｉｓ，Ｄａｖｉｄ  Ｋａｒｇｅｒ，Ｍ．Ｆｒａｎｓ  Ｋａａｓｈｏｅｋ，Ｈａｒｉ  Ｂａｌａｋｒｉｓｈｎａｎ，“Ｃｈｏｒｄ：Ａ  Ｓｃａｌａｂｌｅ  Ｐｅｅｒ−ｔｏ−ｐｅｅｒ  Ｌｏｏｋｕｐ  Ｓｅｒｖｉｃｅ  ｆｏｒ  Ｉｎｔｅｒｎｅｔ  Ａｐｐｌｉｃａｔｉｏｎｓ”，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  ２００１  ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ａｐｐｌｉｃａｔｉｏｎｓ，ｔｅｃｈｎｏｌｏｇｉｅｓ，ａｒｃｈｉｔｅｃｔｕｒｅｓ，ａｎｄ  ｐｒｏｔｏｃｏｌｓ  ｆｏｒ  ｃｏｍｐｕｔｅｒ  ｃｏｍｍｕｎｉｃａｔｉｏｎｓ，ｐ．１４９−１６０，Ａｕｇｕｓｔ  ２００１，Ｓａｎ  Ｄｉｅｇｏ，Ｃａｌｉｆｏｒｎｉａ，Ｕｎｉｔｅｄ  Ｓｔａｔｅｓ
【発明の概要】
【発明が解決しようとする課題】
【０００５】
非特許文献１に示されている技術では、データは、当該データに対応しているキーの上位ｉビットと一致する上位ｉビットを持つキーを管理するノードに配置される。それら上位ｉビットが一致するキー同士は連続するキーである。このため、それらのキーを管理するノードは、同一ノードである可能性が高い。この場合には、データを複数のノードに配置できないので、データを担当するノードの冗長化を充分に実現できない。なお、データを担当するノードとは、当該データが配置されることにより当該データを格納するノードや、当該データを処理するノードである。また、非特許文献１に示されている技術では、データの複製フレームワークにおいて、或るデータを担当するノードを検索するのにホップ数ｉを要している。
また、非特許文献２に示されているルーティングプロトコルでは、或るデータを、当該データを担当するノードに転送するために、Ｏ（ｌｏｇ（ノード数））のホップ数が必要である。つまり、データを担当するノードまでのデータ転送に要するホップ数を低減することが望まれる。
本発明は上記課題を解決するためになされている。すなわち、本発明の主な目的は、複数のノードによりデータを処理するシステムにおいて、データを担当するノード（担当ノード）の冗長化を実現しながら、より高速に担当ノードまでデータを転送できる技術を提供することである。
【課題を解決するための手段】
【０００６】
上記目的を達成するために、本発明のデータ処理装置は、
ｍ桁（ｍは正の整数）の数値である管理キーが採り得る数値範囲（キー空間）を複数に区分することにより設定された複数の区間のうち、自装置が担当する担当区間に含まれる前記管理キーの範囲を表す情報を記憶する管理キー記憶手段と、
前記管理キーとしての数値の基数のｎ乗（ｎはｍ未満の正の整数）を多重度とした場合に、前記キー空間を前記多重度の個数に等分割あるいは略等分割することにより設定された複数の範囲のうち、自装置の前記担当区間を含む前記範囲内の前記管理キーを担当する他装置のアドレスと、当該他装置の担当区間を表す情報とを含む装置情報を記憶するルーティングテーブル記憶手段と、
処理対象の処理データと、当該処理データに関連付けられたｍ桁の数値である基準キーとを受信した場合に、前記基準キーが自装置の前記担当区間の範囲内であれば、前記処理データを自装置で処理すると判断し、前記基準キーが自装置の前記担当区間外であれば、前記基準キーにおける下位ｊ桁（ｊ＝ｍ−ｎ）が一致する数値（生成キー）を担当する他装置に向けて、前記ルーティングテーブル記憶手段に格納されている前記装置情報に基づき前記処理データを他装置に転送する処理データ転送手段と
を有する。
また、本発明のデータ分散処理システムは、
本発明のデータ処理装置を備え、
外部または他のデータ処理装置から処理対象の処理データを受信した前記データ処理装置は、前記処理データに関連付けられている基準キーに基づいた生成キーが自装置の担当区間内である場合には、前記処理データを処理対象と判断し、また、前記生成キーが自装置の担当区間外である場合には、前記生成キーを担当する前記データ処理装置に向けて、ルーティングテーブル記憶手段に記憶されている装置情報に基づいて、前記処理データを転送する。
さらに、本発明のデータ処理方法は、
ｍ桁（ｍは正の整数）の数値である管理キーが採り得る数値範囲（キー空間）を複数に区分することにより設定された複数の区間のうち、自装置が担当する担当区間に含まれる前記管理キーの範囲を表す情報をコンピュータ装置が記憶し、
前記管理キーとしての数値の基数のｎ乗（ｎはｍ未満の正の整数）を多重度とした場合に、前記キー空間を前記多重度の個数に等分割あるいは略等分割することにより設定された複数の範囲のうち、自装置の前記担当区間を含む前記範囲内の前記管理キーを担当する他装置のアドレスと、当該他装置の担当区間を表す情報とを含む装置情報をコンピュータ装置が記憶し、
処理対象の処理データと、当該処理データに関連付けられたｍ桁の数値である基準キーとを受信した場合に、前記基準キーが自装置の前記担当区間の範囲内であれば、前記処理データを自装置で処理するとコンピュータ装置が判断し、
前記基準キーが自装置の前記担当区間外であれば、前記基準キーにおける下位ｊ桁（ｊ＝ｍ−ｎ）が一致する数値（生成キー）を担当する他装置に向けて、前記装置情報に基づいて前記処理データをコンピュータ装置が他装置に転送する。
さらにまた、本発明のプログラム記憶媒体は、
ｍ桁（ｍは正の整数）の数値である管理キーが採り得る数値範囲（キー空間）を複数に区分することにより設定された複数の区間のうち、自装置が担当する担当区間に含まれる前記管理キーの範囲を表す情報を記憶する処理と、
前記管理キーとしての数値の基数のｎ乗（ｎはｍ未満の正の整数）を多重度とした場合に、前記キー空間を前記多重度の個数に等分割あるいは略等分割することにより設定された複数の範囲のうち、自装置の前記担当区間を含む前記範囲内の前記管理キーを担当する他装置のアドレスと、当該他装置の担当区間を表す情報とを含む装置情報を記憶する処理と、
処理対象の処理データと、当該処理データに関連付けられたｍ桁の数値である基準キーとを受信した場合に、前記基準キーが自装置の前記担当区間の範囲内であれば、前記処理データを自装置で処理するとコンピュータ装置が判断し、前記基準キーが自装置の前記担当区間外であれば、前記基準キーにおける下位ｊ桁（ｊ＝ｍ−ｎ）が一致する数値（生成キー）を担当する他装置に向けて、前記装置情報に基づいて前記処理データを他装置に転送する処理と
をコンピュータ装置に実行させるコンピュータプログラムを記憶している。
【発明の効果】
【０００７】
本発明によれば、複数のノードによりデータを処理するシステムにおいて、担当ノードの冗長化を実現しながら、より高速に担当ノードまでデータを転送できる。
【図面の簡単な説明】
【０００８】
図１は、本発明に係る第１実施形態のデータ処理装置の機能構成を表すブロック図である。
図２は、第１実施形態のデータ処理装置におけるハードウェア構成を表すブロック図である。
図３は、第１実施形態のデータ処理装置の動作例を表すフローチャートである。
図４は、本発明に係る第２実施形態のデータ分散処理システムの構成を表す図である。
図５は、第２実施形態のデータ分散処理システムの一具体例を表す図である。
図６は、第２実施形態のデータ分散処理システムを構成するデータ処理装置の機能構成を表すブロック図である。
図７は、第２実施形態における管理キー記憶部が格納する情報の一例を表す図である。
図８は、第２実施形態におけるルーティングテーブル記憶部が格納する情報の一例を表す図である。
図９は、第２実施形態のデータ分散処理システムにおいてデータを格納する動作の一例を説明する図である。
図１０は、第２実施形態において、生成キーを生成する処理の一例を説明する図である。
図１１は、第２実施形態において、データを処理する動作の一例を説明する図である。
図１２は、第２実施形態において、データを転送する動作の一例を説明するフローチャートである。
図１３は、第２実施形態において、生成キーを生成する動作の詳細を説明するフローチャートである。
図１４は、第２実施形態において、データ処理装置の距離算出動作の詳細を説明するフローチャートである。
図１５は、第２実施形態において、データ処理装置の処理データを転送する動作の詳細を説明するフローチャートである。
図１６は、第２実施形態において、データ処理装置が格納データを転送する動作の一例を説明するフローチャートである。
図１７は、第２実施形態において、データ処理装置の処理部による動作を説明するフローチャートである。
図１８は、本発明に係る第３実施形態のデータ処理装置の機能構成を表すブロック図である。
図１９は、第３実施形態のデータ処理装置がルーティングテーブルを初期化する動作の一例を説明するフローチャートである。
図２０は、第３実施形態におけるルーティングテーブル記憶部が格納する情報の一例を表す図である。
図２１は、第３実施形態のデータ処理装置がルーティングテーブルを更新する動作の一例を説明するフローチャートである。
【発明を実施するための形態】
【０００９】
以下に、本発明に係る実施形態を図面を参照しながら説明する。
（第１実施形態）
図１は、本発明に係る第１実施形態のデータ処理装置の機能構成を表すブロック図である。この第１実施形態のデータ処理装置１は、他のデータ処理装置１（以下、他装置ともいう）と通信可能に接続される。それら複数のデータ処理装置１は、データを分散処理するデータ分散処理システムを構成する。データ分散処理システムで管理（処理）されるデータには、管理キーと呼ぶｍ桁（ｍは正の整数）の数値が関連付けられる。管理キーの数値はデータ毎に異なり、各管理キーの数値は連続している。
データ処理装置１には、担当する管理キーの範囲を示す担当区間が割り当てられる。つまり、管理キーが採り得る数値範囲（以下、キー空間ともいう）が複数の区間に分割される。データ分散処理システムを構成する各データ処理装置１には、それぞれ別々の区間が担当区間として割り当てられる。なお、各データ処理装置１の担当区間は重複していない。
図２は、データ処理装置１のハードウェアの概略構成を示すブロック図である。データ処理装置１はコンピュータ装置である。当該データ処理装置１は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）１００１と、一時記憶媒体であるＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）１００２と、記憶媒体であるＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）１００３と、記憶媒体であるハードディスク装置（ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ））１００４と、ネットワークインタフェース１００５とを有している。
ＲＯＭ１００３またはＨＤＤ１００４には、データ処理に関わるコンピュータプログラム（プログラム）が記憶されている。ＣＰＵ１００１は、そのプログラムをＲＯＭ１００３またはＨＤＤ１００４から読み出し、当該プログラムをＲＡＭ１００２に書き込み、当該プログラムを実行する機能を有する。そのＣＰＵ１００１の機能により、コンピュータ装置はデータ処理装置１として機能する。なお、データ処理装置１は、上記以外の記憶媒体（記憶装置）を備えていてもよい。
次に、データ処理装置１の機能構成を、図１を利用して説明する。
データ処理装置１は、機能部として、処理データ転送部（処理データ転送手段）１２と、管理キー記憶部（管理キー記憶手段）１５と、ルーティングテーブル記憶部（ルーティングテーブル記憶手段）１７とを備える。管理キー記憶部１５およびルーティングテーブル記憶部１７は、ＨＤＤ１００４によって構成される。処理データ転送部１２は、ＣＰＵ１００１およびネットワークインタフェース１００５によって構成される。なお、データ処理装置１の各機能部を構成するハードウェア構成は上記構成に限定されない。
管理キー記憶部１５は、自装置に割り当てられた管理キーの担当区間を示す情報を記憶する機能を備えている。
ルーティングテーブル記憶部１７は、装置情報を記憶する。装置情報とは、キー空間が所定の多重度の個数に等分割あるいは略等分割された各範囲のうち自装置の担当区間を含む範囲に含まれる管理キーを担当する他装置のアドレスと、該他装置の担当区間を表す情報とを含む情報である。ここで、所定の多重度とは、データ処理装置１および他装置が属するデータ分散処理システムにおいて、或るデータの複製が格納されるノード数の上限、または、或るデータを処理可能なノード数の上限をいう。第１実施形態では、多重度を決定する定数ｎが予め定められており、多重度は、例えば、管理キーである数値の基数のｎ乗（ｎはｍ未満の正の整数）である。
処理データ転送部１２は、処理対象の処理データを基準キーと共に受信する。ここで、基準キーとは、管理キーが採り得る数値範囲内の数値であり、かつ、データ分散処理システムで管理されるデータに関連付けられるｍ桁の数値をいう。そして、処理データ転送部１２は、処理データの基準キーが自装置の担当区間の範囲内であれば、処理データを処理の対象と判断する。この場合、処理データ転送部１２は、処理データを他装置には転送しない。
一方、処理データ転送部１２は、処理データの基準キーが自装置の担当区間の範囲外であれば、処理データを、該処理データの基準キーに基づいて算出される生成キーを担当区間に含む他装置（最終的な転送先）に向けて転送する。なお、生成キーとは、管理キーが採り得る数値範囲内のｍ桁の数値であり、かつ、基準キーと下位ｊ桁（ただし、ｊ＝ｍ−ｎ）が一致する数値である。
例えば、処理データ転送部１２は、自装置の担当区間からの距離がもっとも近い生成キーを担当区間に含む他装置を、処理データの最終的な転送先とする。なお、データ処理装置１が属するデータ分散処理システムにおいて採用されるキー空間において、キー間の距離は、所定の算出方法によりあらかじめ定められているとする。
処理データ転送部１２は、処理データを転送する場合には、ルーティングテーブル記憶部１７に装置情報が格納されている他装置のいずれかに、処理データを転送する。もし、最終的な転送先の装置情報がルーティングテーブル記憶部１７に格納されていれば、処理データ転送部１２は、その最終的な転送先に向けて、処理データを直接に転送する。
以下に、データ処理装置１の動作例を図３を参照して説明する。なお、図３のフローチャートは、データ処理装置１が実行するプログラムに表されている制御手順を表す。
まず、処理データ転送部１２は、基準キーに関連付けられた処理データを受信する（ステップＳ１）。
次に、処理データ転送部１２は、基準キーが自装置の担当区間の範囲に含まれるか否かを判断する（ステップＳ２）。
基準キーが自装置の担当区間の範囲に含まれる場合には、処理データ転送部１２は、処理データを処理対象として判断する。そして、データ処理装置１は、予め定められた処理手法により処理データを処理する（ステップＳ３）。
一方、基準キーが自装置の担当区間の範囲に含まれない場合には、データ処理装置１は、生成キーを生成する（ステップＳ４）。すなわち、データ処理装置１は、基準キーの上位ｎ桁を、該ｎ桁が採り得る全パターンに置き換えることにより、複数の生成キーを生成する。
その後、処理データ転送部１２は、各生成キーを担当区間に含む他装置のうちのいずれかまで最終的に転送されるように、ルーティングテーブル記憶部１７に格納されている装置情報に基づいて、他装置に向けて処理データを送信（転送）する（ステップＳ５）。
以下に、本発明に係る第１実施形態の効果を述べる。
第１実施形態のデータ処理装置１は、データ分散処理システムにおいて、データを担当するノードの冗長化を実現しながら、対象となるデータを、担当ノードまで高速に転送できる。
その理由について説明する。ルーティングテーブル記憶部１７は、キー空間を所定の多重度の個数に等分割あるいは略等分割した範囲のうち自装置の担当区間を含む範囲の管理キーを担当する他装置の装置情報を格納している。したがって、第１実施形態のデータ処理装置１は、自装置を含めて、キー空間における［１／多重度］（なお、／は除算を示す）を担当するデータ処理装置の装置情報を格納している。一方で、処理データ転送部１２は、対象となる処理データの基準キーが自装置の担当区間に含まれない場合には、その基準キーと下位ｊ桁が一致する値を持つ生成キーを生成する。ｊは、管理キーをｍ桁とし、所定の多重度を基数のｎ乗で表したとき、ｊ＝ｍ−ｎで表される値である。したがって、生成される生成キーの個数は［基数のｎ乗］個となり、これらの生成キーはキー空間において等間隔に離れていることになる。
したがって、第１実施形態のデータ処理装置１は、自装置が認識しているキー空間の［１／多重度］の範囲に、生成キーのいずれかを含むことになる。すなわち、自装置の担当区間に生成キーが含まれない場合には、ルーティングテーブル記憶部１７には、いずれかの生成キーを担当する他装置の装置情報を格納していることになる。その結果、処理データ転送部１２は、各生成キーを担当区間に含む他装置のいずれかに、処理データを直接に転送できる。つまり、第１実施形態のデータ処理装置１に処理データを入力する外部の装置は、該処理データを処理可能なデータ処理装置１まで、該処理データを高々１ホップで送信できる。
なお、第１実施形態において、ルーティングテーブル記憶部１７は、上述した範囲を担当する他装置の装置情報に加えて、さらに他の範囲を担当するデータ処理装置１の装置情報を記憶していても構わない。
（第２実施形態）
次に、本発明に係る第２実施形態を図面を参照しながら説明する。なお、第２実施形態の説明において、第１実施形態と同一構成には同一符号を付し、その重複説明を省略する。
図４は、本発明に係る第２実施形態のデータ分散処理システムの全体構成を表すモデル図である。第２実施形態のデータ分散処理システム１０は、Ｎ台（Ｎは正の整数）のデータ処理装置２０＿１〜２０＿Ｎを有する。なお、データ処理装置２０＿１〜２０＿Ｎを総称してデータ処理装置２０とも記載する。また、図４において、“２０＿ｉ（ｉは１〜Ｎの正の整数）”を円で囲んだ図形は、データ処理装置２０を表している。
データ処理装置２０は、主ネットワークを介して他のデータ処理装置２０と通信可能に接続されている。なお、データ処理装置２０は、さらに、主ネットワークを経由せずに他のデータ処理装置２０と通信可能に接続されていてもよい。例えば、２つのデータ処理装置２０は、別のデータ処理装置２０を経由して互いに通信可能であってもよい。
また、図４に示すデータ処理装置２０＿１０のように、データ処理装置２０のうちの少なくとも１台は、副ネットワークを経由して、処理データ入力装置８０および格納データ入力装置９０に接続されている。
なお、主ネットワークおよび副ネットワークは、それぞれ、インターネット、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、公衆回線網、無線通信網またはこれらの組合せによって構成される。また、この第２実施形態では、処理データ入力装置８０あるいは格納データ入力装置９０と、データ処理装置２０とは、副ネットワークを介して接続されているが、副ネットワークではなく、主ネットワークを介して接続されていてもよい。さらに、処理データ入力装置８０と接続するデータ処理装置２０と、格納データ入力装置９０と接続するデータ処理装置２０とは、別のデータ処理装置２０であってもよい。
各データ処理装置２０には、担当する管理キーの範囲（担当区間）が予め割り当てられている。管理キーとは、データ分散処理システム１０が管理するデータに関連付けられる数値である。第２実施形態では、管理キーはｍビットの２進数値である。また、管理キーとして利用される数値は連続している。なお、管理キーの基数は２とは限らず、他の値であってもよい。管理キーの基数は、データ分散処理システム１０で一意に決まっていればよい。
この第２実施形態では、管理キーが採り得る範囲（キー空間）が、複数の区間（キー区間）に分割され、連続する各キー区間が順次、データ処理装置２０＿１〜２０＿Ｎに割り当てられている。例えば、図４に示される例では、データ処理装置２０＿１を起点に時計回り方向に、各データ処理装置２０に各キー区間が割り当てられている。
例えば、図４では、データ処理装置２０＿１は、管理キーの数値がｓ１からｅ１の範囲を担当区間としている。また、データ処理装置２０＿２は、管理キーの値がｓ２からｅ２の範囲を担当区間としている。他のデータ処理装置２０も同様に管理キーのキー空間における予め定められた範囲を担当区間としている。ここで、ｓ１は、データ分散処理システム１０における管理キーの最小値であり、ｅＮは最大値である。また、ｓ１〜ｓＮおよびｅ１〜ｅＮの大小関係は、ｓ１＜ｅ１＜ｓ２＜ｅ２．．．．＜ｓＮ＜ｅＮである。さらに、ｅｉと、ｓ［ｉ＋１］とは、連続する数値である（ｉは１〜Ｎ−１の正の整数）。
なお、図４では、管理キーの最小値をｓ１、最大値をｅＮとしているが、ｓ１およびｅＮは、必ずしも管理キーの最小値および最大値でなくても構わない。すなわち、１つのデータ処理装置２０が、管理キーの最小値および最大値を含む区間を担当していてもよい。例えば、データ処理装置２０＿１の担当区間は、ｅ１から管理キーの最大値までの区間と最小値からｅ１までの区間とを併せたものであってもよい。また、各データ処理装置２０の担当区間の長さは、全て同じであってもよいし、少なくとも１つが他と異なっていてもよい。また、各担当区間が包含する管理キーは１つでもよいし、複数でもよい。
さらに、この第２実施形態では、キー区間を割り当てる場合の起点をデータ処理装置２０＿１としているが、他のデータ処理装置２０を起点としてもよい。また、この第２実施形態では、起点のデータ処理装置２０から時計回りにキー区間を割り当てているが、反時計回りにキー区間を割り当ててもよい。さらに、この第２実施形態では、連続する各キー区間が、順に、図４に示すデータ処理装置２０の並び順に、割り当てられているが、各キー空間は、データ処理装置２０の並び順に限定されず、適宜に割り当ててもよい。
図５は、データ分散処理システム１０の具体例を表すモデル図である。図５に示す例では、データ分散処理システム１０は、１６台のデータ処理装置２０ａ〜２０ｐを備える。なお、図５において、円で囲まれたａ〜ｐの各図形は、データ処理装置２０を表している。
図５に示すデータ分散処理システム１０は、管理キーとして、２進８桁の数値であるキーを管理している。図５では、これらの管理キーを１０進数（０〜２５５）で表記している。各データ処理装置２０の担当区間（担当する管理キーの範囲）は、予め設定されている。図５では、各データ処理装置２０を表す図形付近に表される括弧内に、そのデータ処理装置２０の担当区間における最小値と最大値が示されている。例えば、データ処理装置２０ａは、管理キーの値が０から１３までの範囲を担当区間としている。データ処理装置２０ｂは、管理キーの値が１４から３０までの範囲を担当区間としている。
図５に示されるように、各データ処理装置２０の担当区間は、連続する区間である。また、図５の例では、各データ処理装置２０の担当区間は、隣接するデータ処理装置２０の担当区間と連続している。さらに、図５の例では、１６台のデータ処理装置２０の担当区間の長さの少なくとも１つは他の担当区間の長さと同一ではない。なお、図５では、１６台のデータ処理装置２０を示しているが、データ分散処理システムを構成するデータ処理装置２０の数は１６台に限定されない。
また、データ分散処理システム１０は、格納データ入力装置９０から受信する格納データを、予め定められた多重度の個数に複製して格納する。すなわち、格納データは、多重度を上限とする台数のデータ処理装置２０に格納される。また、データ分散処理システム１０は、処理データ入力装置８０から受信する処理データを処理可能なノードを、前述の多重度で冗長化している。すなわち、処理データを処理可能なデータ処理装置２０は、多重度を上限とする台数存在する。つまり、データ分散処理システム１０における多重度とは、同一のデータを格納するノード数の上限を表す。あるいは、データ分散処理システム１０における多重度とは、同一のデータを処理することが可能なノード数の上限を表す。
次に、第２実施形態のデータ処理システム１０を構成するデータ処理装置２０の構成を図６を参照して説明する。なお、データ処理装置２０のハードウェア構成は、図２に示すデータ処理装置１と同様な構成を有しているので、その説明を省略する。
図６に示すデータ処理装置２０は、格納データ転送部２１と、処理データ転送部２２と、処理部２３と、キー生成部２４と、管理キー記憶部２５と、格納データ記憶部２６と、ルーティングテーブル記憶部２７とを備えている。
格納データ転送部２１および処理データ転送部２２は、ＲＯＭ１００３またはＨＤＤ１００４に記憶されたプログラムをＲＡＭ１００２に読み込んで実行するＣＰＵ１００１、および、ネットワークインタフェース１００５によって構成される。また、処理部２３およびキー生成部２４は、ＲＯＭ１００３またはＨＤＤ１００４に記憶されたプログラムをＲＡＭ１００２に読み込んで実行するＣＰＵ１００１によって構成される。格納データ記憶部２６は、ＨＤＤ１００４によって構成される。なお、データ処理装置２０の各機能を実現するハードウェア構成は、上述の構成に限定されない。例えば、格納データ転送部２１と、処理データ転送部２２と、処理部２３と、キー生成部２４とは、それぞれ、専用の集積回路によって構成されていてもよい。
格納データ転送部２１は、格納データ入力装置９０または他のデータ処理装置２０（以下、他装置ともいう）から格納データを受信する機能を備えている。さらに、格納データ転送部２１は、キー生成部２４によって生成された生成キーが自装置の担当区間の範囲内であると判断した場合には、受信した格納データを格納データ記憶部２６に格納する機能を備えている。
格納データ転送部２１は、さらにまた、キー生成部２４により生成された生成キーが自装置の担当区間の範囲外であると判断した場合には、生成キーを担当区間に含む他装置に最終的に転送されるように、受信した格納データを転送する機能を備えている。つまり、格納データ転送部２１は、ルーティングテーブル記憶部２７に装置情報が格納されている他装置に格納データを転送する。
処理データ転送部２２は、第１実施形態における処理データ転送部１２と同様の、処理データを転送する機能を備えている。つまり、処理データ転送部２２は、自装置の担当区間からの距離が最も近い生成キーを担当区間に含む他のデータ処理装置２０まで処理データが最終的に転送されるように、転送処理を行う。
なお、自装置の担当区間から或るキーまでの距離は、自装置の担当区間に含まれるキーから或るキーまでの距離のうち最小の距離と定義する。また、データ分散処理システム１０で採用されているキー空間において、或るキーから他のキーまでの距離（キー間の距離）は、時計回り距離で定義されていてもよいし、反時計回り距離で定義されていてもよい。第２実施形態では、キー間の距離は、時計回り距離と定義する。例えば、非特許文献２に記載されているＣｈｏｒｄでは、キー間の時計回り距離は、次のように定義されている。すなわち、或るキーｋからの距離がｄであるキーは、モジュロ演算による［（ｋ＋ｄ）ｍｏｄ  ２ｍ］と定められている。
処理部２３は、処理データに対して予め定められた処理を実行する機能を有する。その処理とは、例えば、格納データ記憶部２６に格納された格納データを用いて実行される処理である。
キー生成部２４は、格納データまたは処理データに関連付けられている基準キーを利用して生成キーを算出する機能を備えている。この第２実施形態では、生成キーは、管理キーが採り得る数値範囲内の数値であり、かつ、下位ｊ桁が基準キーの下位ｊ桁と一致する値を持つキーである。例えば、キー生成部２４は、基準キーの上位ｎ桁を、当該ｎ桁が採り得る全パターンで置き換えることにより、生成キーを生成する。なお、ｎは、データ分散処理システム１０における多重度を決定する定数であり、当該多重度は、２のｎ乗で規定される。管理キーの桁数をｍとした場合に、ｊは、ｊ＝ｍ−ｎで定義される数値である。
管理キー記憶部２５は、第１実施形態に示す管理キー記憶部１５と同様に、自装置の担当区間の範囲の情報を記憶する機能を備えている。さらに、管理キー記憶部２５は、データ分散処理システム１０において予め定められている各種情報を記憶してもよい。図５に示すデータ処理装置２０ｊの管理キー記憶部２５が格納するデータの一例が図７に表されている。図７に示される例では、管理キー記憶部２５は、自装置であるデータ処理装置２０ｊの担当区間の情報、キー長の情報、および、複製桁数の情報を格納している。これらの情報（数値）は、予め与えられる。
図７の例では、担当区間を表す情報は、自装置の担当区間の最小値ｋｍｉｎと最大値ｋｍａｘである。具体的には、データ処理装置２０ｊの担当区間の最小値ｋｍｉｎである１２７と、最大値ｋｍａｘである１３９とが担当区間を表す情報として管理キー記憶部２５に格納される。この担当区間の情報は、格納データ転送部２１および処理データ転送部２２によって参照される。
キー長を表す情報は、管理キー（基準キーおよび生成キーを含む）の桁数ｍ（正の整数）である。第２実施形態では、管理キーの桁数ｍである８がキー長の情報として管理キー記憶部２５に格納される。このキー長の情報は、キー生成部２４によって参照される。
複製桁数を表す情報は、格納データの複製を格納するデータ処理装置２０の数の上限（多重度）を規定する値である。つまり、この第２実施形態では、多重度は、管理キーの基数（この第２実施形態では、２）をｎ乗した値であり、当該多重度は、そのべき数ｎにより決定される。当該べき数ｎは、予め定められ、複製桁数を表す情報として管理キー記憶部２５に格納される。この第２実施形態では、ｎは２と定められている。これにより、多重度は、４（基数２の２乗）と決定される。
なお、データ分散処理システム１０における格納データの実際の多重度は、上記のように規定される多重度（基数のｎ乗）よりも小さくなる場合がある。なぜなら、格納データ転送部２１は、前記のように定まる多重度の各生成キーを担当区間に含むデータ処理装置２０に向けて、格納データを転送する。しかし、算出された生成キーのうち、複数の生成キーが同じ担当区間に含まれてしまう場合がある。この場合には、複数の生成キーが同じデータ処理装置２０に転送されることになるので、実際の多重度は、基数のｎ乗よりも小さくなる。
格納データ記憶部２６は、自装置の担当区間に含まれる基準キーに関連付けられている格納データを格納する機能を備えている。格納データは、処理データを処理する際に利用するデータであり、当該格納データは、前述の処理部２３によって用いられる。格納データが具体的にどのようなデータであるかは、データ分散処理システム１０に依存する。
ルーティングテーブル記憶部２７は、転送候補の他装置に関する装置情報を記憶する機能を備えている。転送候補の他装置とは、自装置の担当区間からの距離が１から、［（基数のｊ乗）−（自装置の担当区間の長さ）］により算出される値までの範囲（以下、転送範囲ともいう）内に担当する管理キーを持つデータ処理装置２０である。また、装置情報とは、転送候補のデータ処理装置２０が担当すキー区間を表す情報およびそのアドレスとを少なくとも含む情報である。なお、担当区間を表す情報とは、或るキーが、データ処理装置２０の担当区間に含まれるか否かを判別可能な情報であればよい。例えば、ルーティングテーブル記憶部２７は、担当区間を表す情報として、転送候補のデータ処理装置２０が担当する区間（キー区間）の最小値を記憶していてもよい。
上記転送範囲は、例えば、次のようにして特定される。つまり、転送範囲の最小値は、管理キー記憶部２５に格納されている担当区間の最小値（ｋｍｉｎ）と、キー空間における管理キーの総数（ｎｕｍ＿ｋｅｙｓ）とを利用したモジュロ演算［（ｋｍａｘ＋１）ｍｏｄ  ｎｕｍ＿ｋｅｙｓ］により求まる。また、転送範囲の最大値は、管理キー記憶部２５に格納されている担当区間の最大値（ｋｍａｘ）と、前記多重度を規定する値ｎと、キー空間における管理キーの総数（ｎｕｍ＿ｋｅｙｓ）とを利用したモジュロ演算［（ｋｍｉｎ＋（ｎｕｍ＿ｋｅｙｓ／２ｎ）−１）ｍｏｄ  ｎｕｍ＿ｋｅｙｓ］により求まる。なお、モジュロ演算を表す数式における“／”は除算を示す。また、転送範囲は、キー空間において時計回り距離が定められていることを前提としている。
ルーティングテーブル記憶部２７は、上記のような転送範囲に含まれるキーを担当する全てのデータ処理装置２０（転送候補のデータ処理装置２０）に関する装置情報を格納する。この第２実施形態では、ルーティングテーブル記憶部２７は、転送候補のデータ処理装置２０における担当区間を表す情報（ここでは、担当区間の最小値）と、該データ処理装置２０のアドレスとを関連付けた情報を格納する。
図８は、データ処理装置２０ｊ（図５参照）におけるルーティングテーブル記憶部２７に記憶される装置情報の具体例が表されている。データ処理装置２０ｊの担当範囲の最小値ｋｍｉｎは、図５に示されるように、１２７であり、担当範囲の最大値ｋｍａｘは１３９である。このことから、データ処理装置２０ｊにおける転送範囲は、（１３９＋１）ｍｏｄ  ２５６（＝１４０）から（１２７＋２５６／２２−１）ｍｏｄ  ２５６（＝１９０）である。これにより、データ処理装置２０ｊがデータを転送する候補となる転送候補のデータ処理装置２０は、転送範囲１４０〜１９０に含まれる管理キーを担当するデータ処理装置２０ｋ，２０ｌ，２０ｍ，２０ｎである。したがって、データ処理装置２０ｊのルーティングテーブル記憶部２７は、転送候補の各データ処理装置２０ｋ，２０ｌ，２０ｍ，２０ｎ毎に、そのアドレスと担当区間の最小値とを関連付けた情報を装置情報として格納する。
以下に、データ分散処理システム１０の動作を図面を参照しながら説明する。
まず、データ分散処理システム１０が格納データを格納する動作を、図９および図１０を利用して説明する。この説明では、データ分散処理システム１０は、図５に示すような担当区間が割り当てられた１６台のデータ処理装置２０によって構成されている。
例えば、データ処理装置２０ｊは、格納データ入力装置９０から格納データを受信すると、次のようにして格納データの転送先のデータ処理装置２０を決定する。
まず、データ処理装置２０ｊの格納データ転送部２１は、受信した格納データに関連付けられた基準キーを得る。格納データに関連付けられた基準キーは、例えば、格納データまたはその一部をシードとして算出されるハッシュ値である。シードとは、ハッシュ値を算出する際に基となるデータである。
具体的には、例えば、“田町駅”という文字列を含む格納データを格納データ転送部２１が受信したとする。この場合に、格納データ転送部２１は、その格納データに含まれる“田町駅”という文字列をシードとしてハッシュ値を算出する。当該格納データ転送部２１は、そのハッシュ値を基準キーとして取得する。基準キー（ハッシュ値）は、図１０に示されるように、２進数で“１０１０１０１０”と表されるとする。なお、この第２実施形態では、説明の分かり易さ等を考慮して、管理キー（基準キーおよび生成キーを含む）を１０進数でも記載する。上記基準キー“１０１０１０１０”は、１０進数で“１７０”と表される。
次に、キー生成部２４は、基準キーの上位ｎ桁を、ｎ桁が採り得る全ての値で置換することにより、［基数のｎ乗］個の生成キーを算出する。第２実施形態では、管理キーの基数が２であるから、基数のｎ乗は、２２＝４となる。したがって、キー生成部２４は、図１０に示す基準キー“１０１０１０１０”の上位２ビットを、｛００，０１，１０，１１｝のそれぞれに置き換えた４個の生成キーを生成する。すなわち、キー生成部２４は、１０進数でそれぞれ、“４２”、“１０６”、“１７０”、“２３４”で表される生成キーを生成する。
そして、データ処理装置２０ｊの格納データ転送部２１は、その生成キーと、ルーティングテーブル記憶部２７に格納されている情報とに基づいて、格納データを転送する。具体的には、データ処理装置２０ｊの格納データ転送部２１は、図９に示されるように、各生成キーを担当区間に含む４台のデータ処理装置２０ｃ，２０ｈ，２０ｍ，２０ｐに向けて、格納データを転送する。この第２実施形態では、格納データは、データ処理装置２０ｊから各データ処理装置２０ｃ，２０ｈ，２０ｍ，２０ｐまで、ホップ・バイ・ホップで転送される。
すなわち、データ処理装置２０ｊにおける転送範囲に基づいた転送候補は、データ処理装置２０ｋ，２０ｌ，２０ｍ，２０ｎである。このことから、上記のように格納データの転送先として決定された４台のデータ処理装置２０ｃ，２０ｈ，２０ｍ，２０ｐのうちのデータ処理装置２０ｃ，２０ｈ，２０ｐには、データ処理装置２０ｊは、格納データを直接に転送できない。この場合には、データ処理装置２０ｊの格納データ転送部２１は、各生成キー“４２”，“１０６”，“２３４”までの距離が最も近い転送候補のデータ処理装置２０に、格納データを転送する。このとき、格納データ転送部２１は、格納データと共に、最終的な転送先であるデータ処理装置２０の情報も送信する。これにより、格納データは、最終的な転送先であるデータ処理装置２０ｃ，２０ｈ，２０ｐに転送される。つまり、格納データは、データ処理装置２０ｊからデータ処理装置２０ｍには直接に転送され、また、データ処理装置２０ｊからデータ処理装置２０ｃ，２０ｈ，２０ｐには他のデータ処理装置２０を介して転送される。
格納データを受信した各データ処理装置２０ｃ，２０ｈ，２０ｍ，２０ｐは、それぞれ、格納データを格納する。
なお、上記例では、基準キーは、格納データあるいはその一部をシードとして算出されるハッシュ値であるが、基準キーは、格納データに関連付けられている、別途受信されるデータまたはその一部をシードとして算出されるハッシュ値であってもよい。
次に、データ分散処理システム１０が処理データを処理する動作の具体例を、図１１を参照して説明する。
例えば、データ処理装置２０ｊの処理データ転送部２２は、処理データ入力装置８０から処理データを受信すると、次のようにして処理データの転送先を決定する。すなわち、まず、処理データ転送部２２は、受信した処理データに関連付けられている基準キー（ハッシュ値）を取得する。その基準キーは、格納データに関連付けられる基準キーを取得した処理と同様な処理により取得できる。
そして、データ処理装置２０ｊのキー生成部２４が、その基準キーに基づいて生成キーを生成する。この第２実施形態では、生成キーの生成処理は、格納データに関連付けられている基準キーから生成キーを生成する処理と同様である。ここでは、キー生成部２４は、図１０に示される基準キーと同一の基準キーから、１０進数で“４２”，“１０６”，“１７０”，“２３４”と表される生成キーを生成したとする。
その後、データ処理装置２０ｊの処理データ転送部２２は、その生成キーと、ルーティングテーブル記憶部２７に格納されている情報とに基づいて、処理データの最終的な転送先を決定する。つまり、処理データ転送部２２は、自装置の転送範囲（１４０〜１９０）のうち、自装置の担当区間（１２７〜１３９）からの距離が最も近い生成キー“１７０”を担当区間に含むデータ処理装置２０ｍを、処理データの最終的な転送先として決定する。
これにより、データ処理装置２０ｊの処理データ転送部２２は、ルーティングテーブル記憶部２７を参照することにより、処理データの最終的な転送先であるデータ処理装置２０ｍに向けて、処理データを直接に転送する。処理データを受信したデータ処理装置２０ｍの処理部２３は、受信した処理データに対して予め定められた処理を実行する。
例えば、その処理データに対する処理は、その処理データの基準キーから生成される生成キーを管理キーとして担当するデータ処理装置２０ｃ，２０ｈ，２０ｍ，２０ｐの格納データ格納部２５に格納される格納データのいずれかを必要とする処理である。この処理は、ＣＰＵ１００１だけでなく、データ処理装置２０ｃ，２０ｈ，２０ｍ，２０ｐが備える高性能プロセッサや画像処理エンジン等の装置を利用する処理であってもよい。
なお、生成キー“１７０”を担当するデータ処理装置２０ｍが正常に動作していない等の要因により、処理データをデータ処理装置２０ｍに転送できない場合がある。この場合には、データ処理装置２０ｊの処理データ転送部２２は、処理データを、残る生成キー“４２”，“１０６”，“２３４”を管理キーとして担当するデータ処理装置２０ｃ，２０ｈ，２０ｐのいずれかに転送する。例えば、データ処理装置２０ｊの処理データ転送部２２は、自装置の担当区間（１２７〜１３９）からの距離が生成キー“１７０”の次に近い生成キー“２３４”を管理キーとして担当区間に含むデータ処理装置２０ｐを最終的な転送先として決定する。
この場合、データ処理装置２０ｊの処理データ転送部２２は、処理データを直接にデータ処理装置２０ｐに転送できないので、他のデータ処理装置２０を介して、処理データをデータ処理装置２０ｐに転送する。その他のデータ処理装置２０は、例えば、データ処理装置２０ｊにおける転送候補のデータ処理装置２０ｋ，２０ｌ，２０ｍ，２０ｎのうち、生成キー“２３４”までの距離が最も近い区間を担当するデータ処理装置２０ｎである。このデータ処理装置２０ｎは、転送範囲に生成キー“２３４”を含む。このために、データ処理装置２０ｎは、ルーティングテーブル記憶部２７に格納されている情報を参照することにより、データ処理装置２０ｐに処理データを転送できる。
このように、データ処理装置２０ｍが正常に動作していない場合であっても、データ処理装置２０ｊの処理データ転送部２２は、処理データの最終的な転送先であるデータ処理装置２０ｐまで、１ホップで処理データを転送する。
上記のように、データ分散処理システム１０は、或る処理データに対する予め定められた処理を実行可能なノードを、設定された多重度で冗長化している。これにより、処理データ入力装置８０は、処理データを処理可能に冗長化されたノードのいずれかが正常動作していれば、最大でも基数のｎ乗ホップで、処理データを処理可能なノードまで転送できる。
例えば、第２実施形態のデータ分散処理システム１０は、ｐｕｂｌｉｓｈ／ｓｕｂｓｃｒｉｂｅ（以下、ｐｕｂ／ｓｕｂとも記載する）型のシステムとして機能する。この場合には、データ分散処理システム１０は、ｐｕｂ／ｓｕｂ型システムにおけるサブスクリプションを、格納データとして適用してもよい。例えば、サブスクリプションは、イベントの条件と、当該条件を満足するイベントが入力されたときに情報を通知する外部システムのアドレスとにより構成される。
また、データ分散処理システム１０は、ｐｕｂ／ｓｕｂ型システムにおけるイベントを、処理データとして適用してもよい。例えば、イベントは、１つ以上のデータ項目からなる処理データである。各データ項目は、属性名と属性値により構成される。
この場合には、データ分散処理システム１０は、格納データ入力装置９０から、格納データとしてのサブスクリプションを、いずれかのデータ処理装置２０（例えば、データ処理装置２０ｊ）で受信する。そして、データ分散処理システム１０は、上述のように動作することにより、このサブスクリプションを、所定の多重度を上限とする台数のデータ処理装置２０（例えば、データ処理装置２０ｃ，２０ｈ，２０ｍ，２０ｐ）にそれぞれ格納する。
また、データ分散処理システム１０は、処理データ入力装置８０から、処理データとしてのイベントを、いずれかのデータ処理装置２０（例えば、データ処理装置２０ｊ）で受信する。そして、データ分散処理システム１０は、上述のように動作することにより、このイベントを、対応するサブスクリプションを格納しているデータ処理装置２０（例えば、データ処理装置２０ｃ，２０ｈ，２０ｍ，２０ｐ）のいずれか（例えば、データ処理装置２０ｍ）に転送する。また、そのデータ処理装置２０ｍが正常動作していなければ、データ分散処理システム１０は、冗長化されている他のデータ処理装置２０ｃ，２０ｈ，２０ｐのいずれかに処理データを転送する。
サブスクリプションを格納しているデータ処理装置２０（例えば、データ処理装置２０ｍ）は、転送されたイベントと、登録されているサブスクリプションのイベント条件とを照合する。そして、合致すれば、データ処理装置２０ｍは、受け取ったイベントをサブスクリプションで指定された外部システムに通知する。このような場合には、入力されたイベントと登録されているイベント条件との照合処理、および、外部システムへの通知処理が、処理データに対する予め定められた処理に該当する。
なお、データ分散処理システム１０がｐｕｂ／ｓｕｂ型システムとして動作する場合には、キー生成部２４は、イベントの属性値やサブスクリプションをシードとして生成キーを算出してもよい。
また、例えば、データ分散処理システム１０は、オブジェクトデータを分散して格納する分散ストレージシステムに適用してもよい。この場合には、分散ストレージシステムにおけるオブジェクトデータが、格納データに対応する。また、分散ストレージシステムにおいてオブジェクトデータを要求するクエリが、処理データに対応する。データ分散処理システム１０は、格納データ入力装置９０から、いずれかのデータ処理装置２０において受信するオブジェクトデータを、予め定められた多重度を上限とする台数のデータ処理装置２０（例えば、データ処理装置２０ｃ，２０ｈ，２０ｍ，２０ｐ）に格納する。
また、データ分散処理システム１０は、処理データ入力装置８０から、要求対象のオブジェクトデータの条件（クエリ）を処理データとして、いずれかのデータ処理装置２０に受信する。クエリを受信したデータ処理装置２０（例えば、データ処理装置２０ｊ）は、上記のように要求対象のオブジェクトデータを格納しているデータ処理装置２０（例えば、データ処理装置２０ｃ，２０ｈ，２０ｍ，２０ｐ）のいずれか（例えば、データ処理装置２０ｍ）に、クエリを転送する。そして、そのデータ処理装置２０ｍが正常動作していなければ、データ処理装置２０ｊは、冗長化されている他のデータ処理装置２０ｃ，２０ｈ，２０ｐのいずれかにクエリを転送する。
その後、データ処理装置２０ｊは、クリエを処理したデータ処理装置２０からクエリ実行結果としてのオブジェクトデータを受信すると、処理データ入力装置８０に応答する。この場合には、クエリを実行して要求対象のオブジェクトデータを得る処理が、処理データの処理に該当する。
以下に、データ分散処理システム１０を構成する各構成部の動作を、フローチャートを参照して説明する。
まず、処理データ転送部２２の動作を図１２のフローチャートに基づいて説明する。なお、図１２のフローチャートは、データ処理装置２０（ＣＰＵ）が実行するコンピュータプログラムに表されている制御手順を表している。
まず、処理データ転送部２２は、処理データ入力装置８０から処理データを受信する（ステップＳ１１）。
そして、処理データ転送部２２は、処理データあるいはその一部をキー生成部２４に出力する。これにより、キー生成部２４が処理データあるいはその一部をシードとして基準キー（ハッシュ値）を生成（算出）し、さらに、当該基準キーを利用して生成キーを生成する。処理データ転送部２２は、その生成された生成キーを取得する（ステップＳ１２）。
その後、処理データ転送部２２は、変数ｄｍｉｎを、値ＭＡＸに初期化する（ステップＳ１３）。ＭＡＸは管理キーが採り得る最大値である。キー長ｍが８である場合には、管理キーの最大値は、（基数のｍ乗−１）である。この第２実施形態では、ＭＡＸは、２の８乗から１を差し引いた値である。つまり、ＭＡＸは２５５である。
そして、処理データ転送部２２は、担当区間から、キー生成部２４により生成された生成キーの一つである生成キーｋまでの距離ｄを求める（ステップＳ１４）。この距離ｄの算出処理については、後述する。
さらに、処理データ転送部２２は、変数ｄｍｉｎが距離ｄよりも大きい（ｄｍｉｎ＞ｄ）か否かを判断する（ステップＳ１５）。
処理データ転送部２２は、変数ｄｍｉｎが距離ｄよりも大きくないと判断した場合（ｄｍｉｎ≦ｄ）には、キー生成部２４により生成された生成キーのうちの残りの生成キーの一つを新たに生成キーｋとして、ステップＳ１４以降の処理を繰り返す。
一方、処理データ転送部２２は、変数ｄｍｉｎが距離ｄよりも大きいと判断した場合（ｄｍｉｎ＞ｄ）には、距離ｄをｄｍｉｎに変更し、生成キーｋを転送ターゲットキーとする（ステップＳ１６）。
その後、処理データ転送部２２は、変数ｄｍｉｎが零に等しい（ｄｍｉｎ＝０）か否かを判断する（ステップＳ１７）。
ここで、変数ｄｍｉｎが零でなければ、処理データ転送部２２は、転送ターゲットキーを担当区間に含む他のデータ処理装置２０に最終的に転送されるように、処理データを転送する（ステップＳ１８）。このとき、処理データ転送部２２は、処理データをホップ・バイ・ホップにより転送する。
その後、処理データ転送部２２は、処理データを正常に転送できたか否かを判断する（ステップＳ１９）。
正常に転送できていれば、処理データ転送部２２は処理を終了する。
一方、正常に転送できていない場合には、処理データ転送部２２は、転送ターゲットキーである生成キーを削除し（ステップＳ２０）、ステップＳ１３以降の処理を繰り返す。なお、ステップＳ２０で削除された生成キーは、ステップＳ１４〜Ｓ１６における処理対象にならない。
前記ステップＳ１７において、変数ｄｍｉｎが零であれば、処理データ転送部２２は、自装置の処理部２３に処理データを送信し（ステップＳ２１）、当該処理データ転送部２２は処理を終了する。
次に、前記ステップＳ１２における処理（キー生成部２４が生成キーを生成する処理）を図１３のフローチャートに基づいて説明する。なお、図１３のフローチャートは、データ処理装置２０（ＣＰＵ）が実行するコンピュータプログラムに表されている制御手順を示している。
まず、キー生成部２４は、シードを受信する（ステップＳ３１）。
次に、キー生成部２４は、シードをハッシュ関数に入力することにより、基準キーとしてのハッシュ値を得る（ステップＳ３２）。
次に、キー生成部２４は、管理キー記憶部２５から、複製桁数ｎを取得する（ステップＳ３３）。
次に、キー生成部２４は、基準キーの上位ｎビットを、当該ｎビットの採り得る全ての組み合わせのそれぞれに置き換えて生成キーを生成する（ステップＳ３４）。
次に、図１２におけるステップＳ１４で実行される処理（距離ｄを算出する処理）を図１４を参照して説明する。なお、ここでは、図５に示される各データ処理装置２０が、処理データを時計回り方向に転送することを前提としたときの距離ｄ（時計回り距離）を算出する処理について説明する。また、図１４のフローチャートは、データ処理装置２０（ＣＰＵ）が実行するコンピュータプログラムに表されている制御手順を示している。
まず、処理データ転送部２２は、生成キーｋが自装置の担当区間内であるか否か、つまり、ｋｍｉｎ≦ｋ≦ｋｍａｘが成り立つか否かを判断する（ステップＳ４１）。なお、担当区間の最小値ｋｍｉｎおよび担当区間の最大値ｋｍａｘは、管理キー記憶部２５が格納している。
処理データ転送部２２は、ｋｍｉｎ≦ｋ≦ｋｍａｘが成り立つ場合には、距離ｄを０とする（ステップＳ４２）。
一方、処理データ転送部２２は、ｋｍｉｎ≦ｋ≦ｋｍａｘでない場合には、生成キーｋが担当区間よりも大きいか否か、つまり、ｋ＞ｋｍａｘであるか否かを判断する（ステップＳ４３）。
処理データ転送部２２は、ｋ＞ｋｍａｘである場合には、距離ｄをｋ−ｋｍａｘとする（ステップＳ４４）。
一方、処理データ転送部２２は、ｋ＞ｋｍａｘでない場合には、距離ｄをＭＡＸ−ｋｍａｘ＋ｋ＋１とする（ステップＳ４５）。なお、ＭＡＸは管理キーが採り得る最大値である。
上記のようにして、距離ｄが算出される。
なお、キー間の距離は、時計回り距離に限らない。例えば、処理データ転送部２２は、キー間の距離として、反時計回り距離を用いてもよい。この場合には、処理データ転送部２２は、図１４に示すステップＳ４４において、ｄ＝ＭＡＸ−ｋ＋ｋｍｉｎ＋１により求まる値を距離ｄとする。また、図１４に示すステップＳ４５において、処理データ転送部２２は、ｄ＝Ｋｍｉｎ−ｋにより求まる値を距離ｄとする。この場合には、ルーティングテーブル記憶部２７は、自装置の担当区間からの反時計回り距離が、１から［基数のｊ乗−自装置の担当区間の長さ］となる値までを転送範囲とし、当該転送範囲の情報を格納する。
次に、図１２に示すステップＳ１８における処理（処理データを転送する処理）について、図１５のフローチャートを参照して説明する。なお、図１５のフローチャートは、データ処理装置２０が実行するコンピュータプログラムに表されている制御手順を示している。
まず、処理データ転送部２２は、変数ｍｉｎにｎｕｍ＿ｋｅｙｓを代入し（ステップＳ５１）、変数ａｄｄに空文字列である“ＮＵＬＬ”を代入する（ステップＳ５２）。なお、ｎｕｍ＿ｋｅｙｓは、データ分散処理システム１０のキー空間における管理キーの総数を示す。
その後、処理データ転送部２２は、ルーティングテーブル記憶部２７に格納されている装置情報に基づいて、転送候補のデータ処理装置２０における担当区間の最小値から転送ターゲットキーまでの距離ｄを算出する（ステップＳ５３）。
そして、処理データ転送部２２は、変数ｍｉｎが距離ｄよりも大きいか否か、つまり、ｍｉｎ＞ｄであるか否かを判断する（ステップＳ５４）。
処理データ転送部２２は、ｍｉｎ＞ｄである場合には、変数ｍｉｎにｄを代入するとともに、変数ａｄｄにデータ処理装置２０のアドレスを代入する（ステップＳ５５）。
一方、ｍｉｎ＞ｄではない場合には、処理データ転送部２２は、ステップＳ５５を実行しない。
処理データ転送部２２は、ルーティングテーブル記憶部２７に記憶される転送候補のデータ処理装置２０について、ステップＳ５３〜Ｓ５５の処理を繰り返す。これにより、変数ａｄｄには、転送候補のデータ処理装置２０のうち、転送ターゲットキーまでの距離が最も近い担当区間を持つデータ処理装置２０のアドレスが記憶される。
その後、処理データ転送部２２は、変数ａｄｄをアドレスに持つデータ処理装置２０に向けて、処理データを転送ターゲットキーと共に転送する（ステップＳ５６）。これにより、処理データ転送部２２による転送に関する処理が終了する。
以下に、データ分散処理システム１０による処理データを転送する処理の具体例を説明する。ここで、データ分散処理システム１０は、図５に示す構成を有しているとする。また、データ処理装置２０ｊのルーティングテーブル記憶部２７は、図８に示される情報を記憶しているとする。また、データ処理装置２０ｊは、受信した処理データの基準キーから、生成キーの集合｛４２，１０６，１７０，２３４｝を生成したとする。
この場合には、データ処理装置２０ｊの処理データ転送部２２が図１２に示されるステップＳ１４〜Ｓ１６の処理を実行することにより、データ処理装置２０ｊの担当区間からの距離が最小となる生成キー（転送ターゲットキー）が、１７０であることが求まる。
そして、データ処理装置２０ｊの処理データ転送部２２は、図１２のステップＳ１８の処理（図１５に示される処理）を行う。すなわち、処理データ転送部２２は、変数ｍｉｎに管理キーの総数２５６を代入する（図１５に示すステップＳ５１）。
その後、処理データ転送部２２は、変数ａｄｄに空文字列である“ＮＵＬＬ”を代入する（ステップＳ５２）。
そして、処理データ転送部２２は、図８に示すルーティングテーブル記憶部２７に格納されている４つの転送候補のデータ処理装置２０ｋ，２０ｌ，２０ｍ，２０ｎの装置情報について、以下の処理を行う。
＜１つ目のデータ処理装置２０ｋの装置情報に関する処理＞
処理データ転送部２２は、データ処理装置２０ｋの担当区間の最小値１４０から転送ターゲットキー“１７０”までの距離ｄを算出する。これにより、ｄ＝３０が算出される（ステップＳ５３）。
そして、変数ｍｉｎ（＝２５６）＞ｄ（＝３０）であるから（ステップＳ５４でＹｅｓ）、処理データ転送部２２は、変数ｍｉｎに３０を代入する。また、処理データ転送部２２は、変数ａｄｄにデータ処理装置２０ｋのアドレスを代入する（ステップＳ５５）。
＜２つ目のデータ処理装置２０１の装置情報に関する処理＞
処理データ転送部２２は、データ処理装置２０ｌの担当区間の最小値１５０から転送ターゲットキー“１７０”までの距離ｄを計算する。これにより、ｄ＝２０が算出される（ステップＳ５３）。
そして、変数ｍｉｎ（＝３０）＞ｄ（＝２０）であるから（ステップＳ５４でＹｅｓ）、処理データ転送部２２は、変数ｍｉｎに２０を代入する。また、処理データ転送部２２は、変数ａｄｄにデータ処理装置２０ｌのアドレスを代入する（ステップＳ５５）。
＜３つ目のデータ処理装置２０ｍの装置情報に関する処理＞
処理データ転送部２２は、データ処理装置２０ｍの担当区間の最小値１６４から転送ターゲットキー“１７０”までの距離ｄを計算する。これにより、ｄ＝６が算出される（ステップＳ５３）。
そして、変数ｍｉｎ（＝２０）＞ｄ（＝６）であるから（ステップＳ５４でＹｅｓ）、処理データ転送部２２は、変数ｍｉｎに６を代入する。また、処理データ転送部２２は、変数ａｄｄにデータ処理装置２０ｍのアドレスを代入する（ステップＳ５５）。
＜４つ目のデータ処理装置２０ｎの装置情報に関する処理）
処理データ転送部２２は、データ処理装置２０ｎの担当区間の最小値１８４から転送ターゲットキー“１７０”までの距離ｄを計算する。これにより、ｄ＝２４２が算出される（ステップＳ５３）。
この場合には、変数ｍｉｎ（＝６）＜ｄ（＝２４２）であるから（ステップＳ５４でＮｏ）、処理データ転送部２２は、変数ｍｉｎおよび変数ａｄｄに対する代入処理を行わない。
上記のように、転送候補のデータ処理装置２０における装置情報に関し、図１５におけるステップＳ５３〜Ｓ５５の処理が繰り返されることにより、変数ａｄｄには、データ処理装置２０ｍ（つまり、転送ターゲットキーまでの距離が最も近い担当区間を持つデータ処理装置２０）のアドレスが代入される。
したがって、処理データ転送部２２は、データ処理装置２０ｍに向けて、処理データを転送する（ステップＳ５６）。
なお、データ処理装置２０ｍは、転送ターゲットキー１７０をその担当区間１６４〜１８３に含んでいる。つまり、この場合には、処理データを受信したデータ処理装置２０ｊの処理データ転送部２２は、転送ターゲットキーを担当するデータ処理装置２０ｍに向けて、処理データを直接に転送する。
以下に、データ処理装置２０が格納データを転送する動作を図１６のフローチャートを参照して説明する。なお、図１６のフローチャートは、データ処理装置２０が実行するコンピュータプログラムに表されている制御手順を示す。
まず、格納データ転送部２１は、格納データ入力装置９０から、格納データおよび要求タイプを受信する（ステップＳ６１）。なお、要求タイプとは、格納データを登録するか、削除するかのいずれかを表すデータであるとする。
その後、格納データ転送部２１は、格納データあるいはその一部をキー生成部２４に出力する。これにより、キー生成部２４が、受信した格納データあるいはその一部をシードとして基準キー（ハッシュ値）を算出し、さらに、その基準キーを利用して生成キーを生成する。格納データ転送部２１は、キー生成部２４により生成された生成キーを取得する（ステップＳ６２）。
そして、格納データ転送部２１は、キー生成部２４から取得した生成キーの一つを処理対象の生成キーｋとし、当該生成キーｋが担当区間内であるか否か、つまり、ｋｍｉｎ≦ｋ≦ｋｍａｘが成り立つか否かを判断する（ステップＳ６３）。なお、担当区間の最小値ｋｍｉｎと最大値ｋｍａｘの情報は、管理キー記憶部２５に格納されている。
格納データ転送部２１は、ｋｍｉｎ≦ｋ≦ｋｍａｘが成り立たない場合には、生成キーｋを担当するデータ処理装置２０に向けて、格納データおよび要求タイプを転送する（ステップＳ６４）。
一方、ｋｍｉｎ≦ｋ≦ｋｍａｘが成り立つ場合には、格納データ転送部２１は、自装置の処理部２３に向けて、格納データおよび要求タイプを送信する（ステップＳ６５）。
そして、格納データ及び要求タイプを転送あるいは送信した後には、キー生成部２４から取得した生成キーのうちの残りの生成キーの一つを処理対象の生成キーｋとし、ステップＳ６３〜Ｓ６５の処理を繰り返す。全ての生成キーについてステップＳ６３〜Ｓ６５の処理が終了することにより、格納データ転送部２１による転送処理が終了する。
以下に、データ処理装置２０における処理部２３の動作例を、図１７のフローチャートを参照して説明する。なお、図１７のフローチャートは、データ処理装置２０が実行するコンピュータプログラムに表されている制御手順を示している。
まず、処理部２３は、自装置の格納データ転送部２１、処理データ転送部２２、あるいは、他のデータ処理装置２０から、格納データまたは処理データを受信する（ステップＳ７０）。そして、処理部２３は、その受信したデータが処理データであるか否かを判断する。
受信データが処理データである場合（ステップＳ７１でＹｅｓ）には、処理部２３は、その処理データを対象にした所定の処理を実行する（ステップＳ７４）。処理が終了することにより、処理部２３は、処理動作を終了する。
一方、受信データが格納データである場合（ステップＳ７１でＮｏ）には、処理部２３は、格納タイプと共に受信した要求タイプが登録であるか否かを判断する（ステップＳ７２）。要求タイプが登録である場合（ステップＳ７２でＹｅｓ）には、処理部２３は、受信した格納データを格納データ記憶部２６に格納する（ステップＳ７３）。
一方、要求タイプが削除である場合（ステップＳ７２でＮｏ）には、処理部２３は、受信した格納データに一致するデータを、格納データ記憶部２６から削除する（ステップＳ７５）。
以下に、第２実施形態の効果について述べる。
第２の実施形態のデータ分散処理システム１０およびデータ処理装置２０は、処理データの処理に関連する格納データを格納するノードを冗長化しながら、そのようなノードまで処理データを高速に転送できる。
その理由について述べる。この第２実施形態では、キー生成部２４は、所定の多重度［基数のｎ乗］個の生成キーを生成する。つまり、キー生成部２４は、格納データの基準キーの上位ｎビットを、該ｎビットが採り得る全ての組合せに置き換えることにより、生成キーを生成している。このようにして生成された生成キーは、キー空間において等間隔に離れたキーとなる。また、ルーティングテーブル記憶部２７に装置情報が格納されるデータ処理装置２０は、自装置の担当区間の最大値＋１から最小値＋（キー総数／多重度）−１までの範囲（転送範囲）に含まれるキーを管理する他のデータ処理装置２０（転送候補のデータ処理装置２０）である。これにより、各データ処理装置２０は、自装置を含めて、キー空間における［１／多重度］により求まる個数の管理キーを担当するデータ処理装置の装置情報を格納していることになる。
このような場合には、データ処理装置２０は、外部から受信する処理データを、該処理データの処理に関連する格納データの複製を格納するデータ処理装置のいずれか１つに転送すればよい。このような格納データの複製を格納するデータ処理装置は、等間隔に離れた多重度の個数の生成キーを担当する。また、そのような等間隔に離れた多重度の個数の生成キーの１つは、キー空間の［１／多重度］に含まれることになる。したがって、処理データを受信したデータ処理装置のルーティングテーブル記憶部は、その処理データに関連する格納データの複製を格納するデータ処理装置のいずれかの装置情報を格納していることになる。
よって、データ処理装置２０は、受信した処理データを、該処理データを処理可能な他のデータ処理装置に直接に転送できることになる。つまり、処理データ入力装置８０は、データ分散処理システム１０に向けた処理データを、処理可能なデータ処理装置２０まで高々１ホップで送信することができる。また、もしも、その処理データを受け取ったデータ処理装置が正常に動作していない場合には、格納データ転送部２１は、自装置の担当区間からの距離がその次に近い生成キーを担当するデータ処理装置２０に転送することになる。この場合にも、各データ処理装置２０がキー空間の［１／多重度］個数のデータ処理装置に関する装置情報を格納していることにより、処理データを受信したデータ処理装置２０から、該処理データを処理する格納データを格納する他のデータ処理装置２０に直接に転送できる。つまり、このデータ分散処理システム１０は、処理データを処理可能なデータ処理装置２０に送信するまでのホップ数を低減できる。
なお、第２実施形態において、ルーティングテーブル記憶部２７は、転送範囲内の管理キーを担当するデータ処理装置２０（転送候補のデータ処理装置２０）の装置情報に加えて、さらに、転送範囲以外の範囲の管理キーを担当するデータ処理装置２０の装置情報を記憶していてもよい。
また、第２実施形態において、所定の多重度を２ｎ（管理キーの基数２のｎ乗）として説明しているが、管理キー（基準キーおよび生成キーを含む）の基数は２に限らない。そして、所定の多重度は、管理キーの基数ｃ（ｃは２以上の正の整数）のｎ乗として規定してもよい。この場合にも、データ処理装置２０は、上記同様の効果を得ることができる。
（第３の実施形態）
以下に、本発明に係る第３実施形態を図面を参照して説明する。なお、第３実施形態の説明において、第１および第２の実施形態と同一構成部分には同一符号を付し、その共通部分の重複説明は省略する。
第３実施形態のデータ分散処理システム３０は、第２実施形態のデータ分散処理システム１０と同様な構成を備えている。ただ、当該データ分散処理システム３０は、データ処理装置２０に代えて、次のようなデータ処理装置４０を備えている。
図１８は、データ処理装置４０の構成を表すブロック図である。データ処理装置４０は、第２実施形態におけるデータ処理装置２０の構成に加えて、ルーティングテーブル更新部（ルーティングテーブル更新手段）４８を備えている。また、データ処理装置４０は、第２実施形態におけるルーティングテーブル記憶部２７に代えて、ルーティングテーブル記憶部４７を備えている。
前記第２実施形態におけるルーティングテーブル記憶部２７は、転送範囲（ｋｍａｘ＋１からｋｍｉｎ＋（ｎｕｍ＿ｋｅｙｓ／ｃｎ）−１までの範囲）に含まれる管理キーを担当する全てのデータ処理装置２０の装置情報を記憶している。これに対して、第３実施形態におけるルーティングテーブル記憶部４７は、転送範囲に含まれるキーを担当する全てのデータ処理装置４０のうちの一部のデータ処理装置４０の装置情報を記憶する。
例えば、データ分散処理システム３０を構成するデータ処理装置４０の数が多い場合には、各データ処理装置４０が、転送範囲のキーを管理する全データ処理装置４０の装置情報を管理すると、管理コストがかかる。管理コストとは、装置情報を記憶するリソースや、ルーティングテーブルの更新処理に係る処理負荷などをいう。なお、ルーティングテーブルの更新処理とは、データ分散処理システム３０にデータ処理装置４０が新規追加されたときに、その追加されたデータ処理装置４０の装置情報を追加（登録）する処理と、データ分散処理システム３０からデータ処理装置４０が削除されたときに当該データ処理装置４０の装置情報をルーティングテーブル記憶部４７から削除する処理とを含む処理である。
例えば、ルーティングテーブル記憶部４７は、転送範囲の管理キーを担当する転送候補のデータ処理装置４０に予め定めたホップ数（転送上限値）以下でデータを転送できるように、一部の転送候補のデータ処理装置４０に関する装置情報を記憶する。具体的には、例えば、転送候補のデータ処理装置４０の総数がｘであるとする。この場合に、転送上限値は、Ｏ（ｌｏｇ（ｘ））ホップとする。ルーティングテーブル記憶部４７は、全ての転送候補のデータ処理装置４０の中から、その転送上限値（Ｏ（ｌｏｇ（ｘ））ホップ）以下でデータを転送できるように選択された一部のデータ処理装置４０の装置情報を記憶する。
例えば、ルーティングテーブル記憶部４７は、転送範囲内において、自装置の担当区間の最小値からの距離が基数のｉ乗（ｉは正の整数）となるキーを担当する転送候補のデータ処理装置４０の装置情報を記憶する。このようにすることにより、転送範囲内の管理キーを担当する全ての転送候補のデータ処理装置４０について、データ処理装置４０は、転送上限値（Ｏ（ｌｏｇ（ｘ））ホップ）以下のホップ数でデータを転送できる。このことは、非特許文献２にも記載されている。
ルーティングテーブル更新部４８は、ルーティングテーブル記憶部４７に記憶される情報の初期化処理および更新処理を実行する機能を備えている。
具体的には、ルーティングテーブル更新部４８は、自装置が新規にデータ分散処理システム３０に参加したときに、初期化処理を行う。つまり、ルーティングテーブル更新部４８は、転送範囲内の管理キーを担当する転送候補のデータ処理装置４０の一部をルーティングテーブル記憶部４７に格納する。
また、ルーティングテーブル更新部４８は、データ分散処理システム３０を構成する他のデータ処理装置４０の担当区間の範囲が変更になった場合に、自装置のルーティングテーブル記憶部４７の装置情報を更新する。具体的には、ルーティングテーブル更新部４８は、他のデータ処理装置４０の担当区間が変更になったことを表す情報を、その他のデータ処理装置４０から直接、または、ホップ・バイ・ホップで受信する。
より具体的には、データ分散処理システム３０において、或るデータ処理装置４０αが担当していた区間（ｋｍｉｎ＿αからｋｍａｘ＿βまでの区間）の一部を、新たに追加されたデータ処理装置４０βが代わりに担当することになったとする。これにより、データ処理装置４０αの変更後の担当区間は、ｋｍｉｎ＿αからｋｍａｘ＿αまでの区間になる。また、データ処理装置４０βの担当区間は、ｋｍｉｎ＿βからｋｍａｘ＿βまでの区間になる。なお、この説明では、ｋｍｉｎ＿α≦ｋｍａｘ＿α＜ｋｍｉｎ＿β≦ｋｍａｘ＿βの大小関係が成り立つとする。ただし、ｋｍａｘ＿αおよびｋｍｉｎ＿βは連続する数値である。
このような場合に、ルーティングテーブル記憶部４７を更新する必要があるデータ処理装置４０は、データ処理装置４０αの装置情報をルーティングテーブル記憶部４７に記憶するデータ処理装置４０である。すなわち、ルーティングテーブル記憶部４７を更新する必要があるデータ処理装置４０は、ｋｍｉｎ＿α−（ｎｕｍ＿ｋｅｙｓ／２ｎ）＋１からｋｍｉｎ＿α−１までの管理キーを担当するデータ処理装置４０の一部である。したがって、データ処理装置４０αは、それらの変更対象のデータ処理装置４０に向けて、担当区間が変更になったことを示す情報を更新要求として送信する。
具体的には、例えば、データ処理装置４０αは、自装置の担当区間を変更すると、担当区間が変更になったことを表す情報を更新要求として、ｋｍｉｎ＿α−（ｎｕｍ＿ｋｅｙｓ／２ｎ）＋１を含む担当区間を持つデータ処理装置４０に送信する。担当区間が変更になったことを表す情報は、例えば、データ処理装置４０αの新たな担当区間の最小値（ｋｍｉｎ＿α）、最大値（ｋｍａｘ＿α）、アドレス（ａｄｄ＿α）を含む。さらに、当該情報は、新規のデータ処理装置４０βの担当区間の最小値（ｋｍｉｎ＿β）、最大値（ｋｍａｘ＿β）、および、アドレス（ａｄｄ＿β）を含む。
このような情報を受信した（つまり、ルーティングテーブル記憶部４７を更新することを要求された）データ処理装置４０は、自装置のルーティングテーブル記憶部４７を更新する。また、当該更新を要求されたデータ処理装置４０は、自装置の担当区間から見て時計回り方向に隣接する区間を担当するデータ処理装置４０（以降、サクセッサともいう）に向けて、更新要求（担当区間が変更になったことを示す情報）を転送する。これにより、更新要求は、順次サクセッサに転送される。そして、担当区間を変更したデータ処理装置４０αが更新要求を受信した場合には、当該データ処理装置４０αは更新要求を転送しない。なお、担当区間が変更されたデータ処理装置４０αは、ルーティングテーブル記憶部４７を更新する。また、新規に追加される処理装置４０βは、自装置のルーティングテーブル記憶部４７を初期化する。
ルーティングテーブル更新部４８は、更新要求を受信した場合に、担当区間が変更されたデータ処理装置４０が次の削除条件を満たす場合には、その変更になったデータ処理装置４０の装置情報をルーティングテーブル記憶部４７から削除する。その削除条件とは、変更後の担当区間が、自装置の転送範囲内であって、かつ、自装置の担当区間の最小値からの距離が基数のｉ乗であるいずれのキーも含まない場合である。ただし、ルーティングテーブル記憶部４７に、その担当区間が変更されたデータ処理装置４０の装置情報が格納されていない場合には、ルーティングテーブル更新部４８は、その削除処理を行わない。
また、ルーティングテーブル更新部４８は、更新要求を受信した場合に、担当区間が変更されたデータ処理装置４０が次の登録条件を満たす場合には、その変更になったデータ処理装置４０の装置情報をルーティングテーブル記憶部４７に登録する。その登録条件とは、変更後の担当区間が、自装置の転送範囲内であって、かつ、自装置の担当区間の最小値からの距離が基数のｉ乗であるいずれかのキーを含む場合である。ただし、ルーティングテーブル記憶部４７に、担当区間が変更されたデータ処理装置４０の装置情報が既に格納されている場合には、ルーティングテーブル更新部４８は、その登録処理を行わない。
また、ルーティングテーブル更新部４８は、上述の例のように、複数のデータ処理装置４０（上述の例では４０αおよび４０β）に関する更新要求を受信した場合には、それぞれのデータ処理装置４０（４０α，４０β）について、削除または登録が必要であるか否かを判断する。
以下に、第３実施形態のデータ分散処理システム３０の動作について説明する。なお、データ分散処理システム３０は、上述したルーティングテーブル更新部４８の初期化処理および更新処理以外は、第２実施形態のデータ分散処理システム１０と同様に動作する。したがって、ここでは、ルーティングテーブル更新部４８の初期化処理および更新処理について説明し、他の動作の説明は省略する。
まず、ルーティングテーブル更新部４８の初期化動作について、図１９のフローチャートを参照して説明する。なお、図１９のフローチャートは、データ処理装置４０が実行するコンピュータプログラムに表されている制御手順を示している。
まず、ルーティングテーブル更新部４８は、自装置の担当区間の最大値ｋｍａｘを取得し（ステップＳ８１）、当該最大値を変数ｋｍａｘに代入する。
その後、ルーティングテーブル更新部４８は、変数ｋにｋｍｉｎ＋ｃｉを代入する（ステップＳ８２）。なお、ｋｍｉｎは、自装置の担当区間の最小値であり、ｃは、管理キーの基数である。
そして、ルーティングテーブル更新部４８は、変数ｋが変数ｋｍａｘ以上（ｋ＞ｋｍａｘ）であるか否かを判断する（ステップＳ８３）。そして、ｋ＞ｋｍａｘの場合、すなわち、管理キーｋを自装置が担当しない場合（ステップＳ８３でＹｅｓ）には、ルーティングテーブル更新部４８は、管理キーｋを担当するデータ処理装置４０を特定する（ステップＳ８４）。なお、管理キーｋを担当するデータ処理装置４０を特定する手法は、例えば、図１５を用いて説明した処理（処理データを転送する処理）を応用して実現できる。つまり、図１５に示す処理では、転送ターゲットキーおよび処理データのペアを、該転送ターゲットキーを担当するデータ処理装置（ｎｏｄｅ＿ｂとする）にホップ・バイ・ホップで転送する。これを応用し、ルーティングテーブル更新部４８は、管理キーｋおよび自装置のアドレス（ａｄｄ＿ａとする）のペアを、図１５の手順にしたがって、ｎｏｄｅ＿ｂにホップ・バイ・ホップで転送する。ｎｏｄｅ＿ｂは、管理キーｋおよびアドレス（ａｄｄ＿ａ）を受信すると、管理キーｋおよび自装置のアドレス（ａｄｄ＿ｂとする）のペアを、ａｄｄ＿ａに対して送信する。このようにして、ルーティングテーブ更新部４８は、管理キーｋを担当するデータ処理装置４０を特定することができる。
次に、ルーティングテーブル更新部４８は、特定したデータ処理装置４０の装置情報をルーティングテーブル記憶部４７に格納していない場合（ステップＳ８５でＮｏ）には、該データ処理装置４０の装置情報をルーティングテーブル記憶部４７に登録する（ステップＳ８６）。そして、ルーティングテーブル更新部４８はステップＳ８２以降の動作を繰り返す。
一方、特定したデータ処理装置４０の装置情報をルーティングテーブル記憶部４７に格納している場合（ステップＳ８５でＹｅｓ）には、ルーティングテーブル更新部４８はステップＳ８２以降の動作を繰り返す。
また、ステップＳ８３において、ｋ＞ｋｍａｘでない場合には、すなわち、管理キーｋを自装置が担当する場合も、ルーティングテーブル更新部４８はステップＳ８２以降の動作を繰り返す。
ｉがｊ（ｊはｊ＝ｍ−ｎ）に達し、かつ、ステップＳ８３〜Ｓ８６の動作が終了することにより、ルーティングテーブル更新部４８の初期化動作が終了する。
当該ルーティングテーブル更新部４８の初期化動作を具体例で説明する。この例では、データ分散処理システム３０を構成する各データ処理装置４０は、図５の各データ処理装置２０と同様に構成されているとする。また、管理キーの桁数ｍは８であり、その基数ｃは２であり、所定の多重度をＣｎで規定するｎは２であるとする。このとき、データ処理装置４０ｊのルーティングテーブル更新部４８は、以下のようにして、ルーティングテーブル記憶部４７を図２０に示すように初期化する。
まず、データ処理装置４０ｊのルーティングテーブル更新部４８は、変数ｋｍａｘに自装置の担当区間の最大値１３９を代入する（ステップＳ８１）。
次に、ルーティングテーブル更新部４８は、ｉ＝０〜ｊ（＝ｍ−ｎ＝６）について、ステップＳ８２〜Ｓ８６の処理を実行する。
まず、ｉ＝０のとき、ルーティングテーブル更新部４８は、ｋにｋｍｉｎ＋１を代入する（ステップＳ８２）。これにより、ｋは１２８になる（ｋ＝１２８）。この場合には、ｋ＞ｋｍａｘでないため（ステップＳ８３でＮｏ）、ルーティングテーブル更新部４８は、ステップＳ８４〜Ｓ８６を実行しない。
次に、ｉ＝１のとき、ルーティングテーブル更新部４８は、ｋにｋｍｉｎ＋２を代入する（ステップＳ８２）。これにより、ｋは１２９になる（ｋ＝１２９）。この場合には、ｋ＞ｋｍａｘでないため（ステップＳ８３でＮｏ）、ルーティングテーブル更新部４８は、ステップＳ８４〜Ｓ８６を実行しない。
次に、ｉ＝２のとき、ルーティングテーブル更新部４８は、ｋにｋｍｉｎ＋４を代入する（ステップＳ８２）。これにより、ｋは１３１になる（ｋ＝１３１）。この場合には、ｋ＞ｋｍａｘでないため（ステップＳ８３でＮｏ）、ルーティングテーブル更新部４８は、ステップＳ８４〜Ｓ８６を実行しない。
次に、ｉ＝３のとき、ルーティングテーブル更新部４８は、ｋにｋｍｉｎ＋８を代入する（ステップＳ８２）。これにより、ｋは１３５になる（ｋ＝１３５）。この場合には、ｋ＞ｋｍａｘでないため（ステップＳ８３でＮｏ）、ルーティングテーブル更新部４８は、ステップＳ８４〜Ｓ８６を実行しない。
次に、ｉ＝４のとき、ルーティングテーブル更新部４８は、ｋにｋｍｉｎ＋１６を代入する（ステップＳ８２）。これにより、ｋは１４３になる（ｋ＝１４３）。この場合には、ｋ＞ｋｍａｘである（ステップＳ８３でＹｅｓ）。そこで、ルーティングテーブル更新部４８は、管理キーｋ（１４３）を担当するデータ処理装置４０がデータ処理装置４０ｋであることを特定する（ステップＳ８４）。そして、ルーティングテーブル記憶部４７がデータ処理装置４０ｋに関する装置情報を格納していないため（ステップＳ８５でＮｏ）、ルーティングテーブル更新部４８は、データ処理装置４０ｋの装置情報をルーティングテーブル記憶部４７に登録する（ステップＳ８６）。
次に、ｉ＝５のとき、ルーティングテーブル更新部４８は、ｋにｋｍｉｎ＋３２を代入する（ステップＳ８２）。これにより、ｋは１５９になる（ｋ＝１５９）。この場合には、ｋ＞ｋｍａｘである（ステップＳ８３でＹｅｓ）。そこで、ルーティングテーブル更新部４８は、管理キーｋ（１５９）を担当するデータ処理装置４０がデータ処理装置４０ｌであることを特定する（ステップＳ８４）。そして、ルーティングテーブル記憶部４７がデータ処理装置４０ｌに関する装置情報を格納していないため（ステップＳ８５でＮｏ）、ルーティングテーブル更新部４８は、データ処理装置４０ｌの装置情報をルーティングテーブル記憶部４７に登録する（ステップＳ８６）。
次に、ｉ＝６のとき、ルーティングテーブル更新部４８は、ｋにｋｍｉｎ＋６４を代入する（ステップＳ８２）。これにより、ｋは１９１になる（ｋ＝１９１）。この場合には、ｋ＞ｋｍａｘである（ステップＳ８３でＹｅｓ）。そこで、ルーティングテーブル更新部４８は、管理キーｋ（１９１）を担当するデータ処理装置４０がデータ処理装置４０ｎであることを特定する（ステップＳ８４）。そして、ルーティングテーブル記憶部４７がデータ処理装置４０ｎに関する装置情報を格納していないため（ステップＳ８５でＮｏ）、ルーティングテーブル更新部４８は、データ処理装置４０ｎの装置情報をルーティングテーブル記憶部４７に登録する（ステップＳ８６）。
次に、ルーティングテーブル更新部４８の更新動作について図２１のフローチャートを参照して説明する。なお、図２１のフローチャートは、データ処理装置４０が実行するコンピュータプログラムに表されている制御手順を示している。
まず、ルーティングテーブル更新部４８は、更新要求（他装置の担当区間の変更を表す情報）として、前述の（ｋｍｉｎ＿α，ｋｍａｘ＿α，ａｄｄ＿α）、ならびに、（ｋｍｉｎ＿β，ｋｍａｘ＿β，ａｄｄ＿β）を受信する（ステップＳ９１）。
その後、ルーティングテーブル更新部４８は、受信した情報に含まれるｋｍｉｎ＿αが、自装置の担当区間の最小値ｋｍｉｎに等しいか否かを判断する（ステップＳ９２）。
ｋｍｉｎ＿α＝ｋｍｉｎである場合には、ルーティングテーブル更新部４８は、ルーティングテーブル更新動作を終了する。
一方、ｋｍｉｎ＿α＝ｋｍｉｎでない場合には、ルーティングテーブル更新部４８は、変数ｅｘｉｔ＿ｉｎｆｏ＿αに、条件を満たさない旨を表す文字列“ｆａｌｓｅ”を代入し、当該変数ｅｘｉｔ＿ｉｎｆｏ＿αを初期化する（ステップＳ９３）。その変数ｅｘｉｔ＿ｉｎｆｏ＿αは、データ処理装置４０αの装置情報をルーティングテーブル記憶部４７に記憶するか否かを表すフラグである。
その後、ルーティングテーブル更新部４８は、変数ｅｘｉｔ＿ｉｎｆｏ＿βに“ｆａｌｓｅ”を代入し、ｅｘｉｔ＿ｉｎｆｏ＿βを初期化する（ステップＳ９４）。その変数ｅｘｉｔ＿ｉｎｆｏ＿βは、データ処理装置４０βの装置情報をルーティングテーブル記憶部４７に記憶するか否かを表すフラグである。
然る後に、ルーティングテーブル更新部４８は、変数ｋにｋｍｉｎ＋ｃｉを代入する（ステップＳ９５）。ｋｍｉｎは、自装置の担当区間の最小値であり、ｃは、管理キーの基数である。
そして、ルーティングテーブル更新部４８は、ｋｍｉｎ＿α≦ｋ≦ｋｍａｘ＿αであるか否かを判断する（ステップＳ９６）。
ｋｍｉｎ＿α≦ｋ≦ｋｍａｘ＿αであれば、ルーティングテーブル更新部４８は、自装置の担当区間の最小値からの距離がｃｉの管理キーｋをデータ処理装置４０αが担当していると判断する。したがって、ルーティングテーブル更新部４８は、変数ｅｘｉｔ＿ｉｎｆｏ＿αを“ｔｒｕｅ”に設定する（ステップＳ９７）。
その後、ルーティングテーブル更新部４８は、ｋｍｉｎ＿β≦ｋ≦ｋｍａｘ＿βであるか否かを判断する（ステップＳ９８）。
ｋｍｉｎ＿β≦ｋ≦ｋｍａｘ＿βであれば、ルーティングテーブル更新部４８は、自装置の担当区間の最小値からの距離がｃｉの管理キーをデータ処理装置４０βが担当していると判断する。したがって、ルーティングテーブル更新部４８は、変数ｅｘｉｔ＿ｉｎｆｏ＿βを“ｔｒｕｅ”に設定する（ステップＳ９９）。
ルーティングテーブル更新部４８は、ステップＳ９５〜Ｓ９９の動作をｉ＝０，１，・・・ｊまで終了すると、次の動作に進む。
次に、ルーティングテーブル更新部４８は、変数ｅｘｉｔ＿ｉｎｆｏ＿αが“ｔｒｕｅ”であるか否かを判断する（ステップＳ１００）。
変数ｅｘｉｔ＿ｉｎｆｏ＿αが“ｔｒｕｅ”でなければ（“ｆａｌｓｅ”であれば）、ルーティングテーブル更新部４８は、データ処理装置４０αの装置情報をルーティングテーブル記憶部４７から削除する（ステップＳ１０１）。なお、データ処理装置４０αの装置情報がルーティングテーブル記憶部４７に格納されていなければ、ルーティングテーブル更新部４８は、削除処理を行う必要はない。
その後、ルーティングテーブル更新部４８は、変数ｅｘｉｔ＿ｉｎｆｏ＿βが“ｔｒｕｅ”であるか否かを判断する（ステップＳ１０２）。
変数ｅｘｉｔ＿ｉｎｆｏ＿βが“ｔｒｕｅ”であれば、ルーティングテーブル更新部４８は、データ処理装置４０βの装置情報をルーティングテーブル記憶部４７に登録する（ステップＳ１０３）。なお、データ処理装置４０βの装置情報がルーティングテーブル記憶部４７に登録されていれば、ルーティングテーブル更新部４８は、登録処理を行う必要はない。
そして、ルーティングテーブル更新部４８は、自装置のサクセッサに、更新要求（他装置の担当区間の変更を表す情報）として、前述の（ｋｍｉｎ＿α，ｋｍａｘ＿α，ａｄｄ＿α）、ならびに、（ｋｍｉｎ＿β，ｋｍａｘ＿β，ａｄｄ＿β）を送信する。
これにより、ルーティングテーブル更新部４８は、ルーティングテーブル更新動作を終了する。
このような、ルーティングテーブル更新部４８の更新動作を具体例で説明する。この例では、データ分散処理システム３０を構成する各データ処理装置４０は、図５の各データ処理装置２０と同様に構成されているとする。また、管理キーの桁数ｍは８であり、その基数ｃは２であり、所定の多重度をｃｎで規定するｎは２であるとする。
ここで、データ分散処理システム３０に、データ処理装置４０ｑが新規に追加されたことを想定する。また、データ処理装置４０ｑは、データ処理装置４０ｏがそれまで担当していた区間［２０２，２２５］の一部を分担するとする。具体的には、データ処理装置４０ｏが区間［２０２，２１０］を担当し、データ処理装置４０ｑが区間［２１１，２２５］を担当するとする。すなわち、データ処理装置４０ｏが上述のデータ処理装置４０αに相当し、データ処理装置４０ｑが、上述のデータ処理装置４０βに相当する。
ここで、データ処理装置４０ｏは、自装置の担当区間の最小値ｋｍｉｎ＿α（２０２）に基づいて、ｋｍｉｎ＿α−（ｎｕｍ＿ｋｅｙｓ／２ｎ）＋１＝１３９を担当するデータ処理装置４０ｊに向けて、更新要求（担当区間の変更を表す情報）を送信する。
これにより、データ処理装置４０ｊは、データ処理装置４０ｏから、更新要求として、担当区間の変更を表す情報「（２０２，２１０，データ処理装置４０ｏのアドレス）、（２１１，２２５，データ処理装置４０ｑのアドレス）」を受信する（図２１のステップＳ９１）。
その後、データ処理装置４０ｊのルーティングテーブル更新部４８は、自装置の担当区間の最小値ｋｍｉｎ（１２７）が、ｋｍｉｎ＿α（２０２）と等しくないため（ステップＳ９２でＮｏ）、変数ｅｘｉｓｔ＿ｉｎｆｏ＿αおよび変数ｅｘｉｓｔ＿ｉｎｆｏ＿βにそれぞれ“ｆａｌｓｅ”を代入する（ステップＳ９３、Ｓ９４）。
そして、ルーティングテーブル更新部４８は、ｉ＝０のとき、変数ｋを１２８に設定する（ステップＳ９５）。この値ｋは、データ処理装置４０ｏが担当するキー範囲［２０２，２１０］には含まれないため（ステップＳ９６でＮｏ）、ルーティングテーブル更新部４８は、ステップＳ９７を実行しない。また、変数ｋは、データ処理装置４０ｑが担当するキー範囲［２１１，２２５］にも含まれないため（ステップＳ９８でＮｏ）、ルーティングテーブル更新部４８は、ステップＳ９９を実行しない。
以降、ルーティングテーブル更新部４８は、ｉ＝１〜６についても、ｉ＝０のときと同様に、ステップＳ９５〜Ｓ９９の動作を繰り返す。ステップＳ９５〜Ｓ９９の動作をｉ＝６まで繰り返した後の状態でも、変数ｅｘｉｓｔ＿ｉｎｆｏ＿αおよび変数ｅｘｉｓｔ＿ｉｎｆｏ＿βは“ｆａｌｓｅ”のままである。
このようにｅｘｉｓｔ＿ｉｎｆｏ＿α＝ｆａｌｓｅであるので、削除処理が実行されるところであるが（ステップＳ１００でＮｏ）、ルーティングテーブル記憶部４７がデータ処理装置４０ｏの装置情報を格納していないので、ルーティングテーブル更新部４８は、削除処理は実行しない。
次に、ルーティングテーブル更新部４８は、ｅｘｉｓｔ＿ｉｎｆｏ＿β＝ｆａｌｓｅであるため（ステップＳ１０２でＮｏ）、データ処理装置４０ｏの装置情報を登録する処理は行わない。
そして、ルーティングテーブル更新部４８は、ステップＳ９１で受信した更新要求（担当区間の変更を表す情報）を、自装置のサクセッサであるデータ処理装置４０ｋに転送する（ステップＳ１０４）。これにより、ルーティングテーブル更新部４８は、更新処理を終了する。上記した具体例では、データ処理装置４０ｊのルーティングテーブル記憶部４７に記憶されている情報は変更されない。
その後、データ処理装置４０ｊから、更新要求（担当区間の変更を表す情報）を受信したデータ処理装置４０ｋでは、ルーティングテーブル更新部４８が、ステップＳ９１〜ステップＳ９９の処理を実行する。これにより、ｉ＝６のときに、変数ｋが２０４＝ｋｍｉｎ（１４０）＋２６となる。つまり、変数ｋは、データ処理装置４０ｏが担当する担当区間［２０２，２１０］に含まれる。したがって、変数ｅｘｉｓｔ＿ｉｎｆｏ＿αは、“ｔｒｕｅ”となる。なお、変数ｅｘｉｓｔ＿ｉｎｆｏ＿βは“ｆａｌｓｅ”のままである。
これにより、ルーティングテーブル更新部４８は、ｅｘｉｓｔ＿ｉｎｆｏ＿α＝ｔｒｕｅであるから（ステップＳ１００でＹｅｓ）、データ処理装置４０ｏの装置情報をルーティングテーブル記憶部４７に記憶しているので、登録処理を行わない。
また、ルーティングテーブル更新部４８は、ｅｘｉｓｔ＿ｉｎｆｏ＿β＝ｆａｌｓｅであるから（ステップＳ１０２でＮｏ）、登録処理を行わない。
その後、ルーティングテーブル更新部４８は、ステップＳ９１で受信した更新要求（担当区間の変更を表す情報）を、自装置のサクセッサであるデータ処理装置４０ｌに転送する（ステップＳ１０４）。これにより、ルーティングテーブル更新部４８は、更新動作を終了する。上記のような更新処理を行っても、データ処理装置４０ｋのルーティングテーブル記憶部４７が記憶する情報は変更されない。
その後、更新要求を受信したデータ処理装置４０ｌでは、ルーティングテーブル更新部４８が、ステップＳ９１〜ステップＳ９９の処理を実行する。これにより、ｉ＝６のときに、変数ｋが２１４＝ｋｍｉｎ（１５０）＋２６となる。つまり、変数ｋは、データ処理装置４０ｑが担当する担当区間［２１１，２２５］に含まれる。したがって、変数ｅｘｉｓｔ＿ｉｎｆｏ＿βは、“ｔｒｕｅ”となる。なお、変数ｅｘｉｓｔ＿ｉｎｆｏ＿αは“ｆａｌｓｅ”のままとなる。
これにより、ルーティングテーブル更新部４８は、ｅｘｉｓｔ＿ｉｎｆｏ＿α＝ｆａｌｓｅであるので（ステップＳ１００でＮｏ）、データ処理装置４０ｏの装置情報を、ルーティングテーブル記憶部４７から削除する（ステップＳ１０１）。
また、ｅｘｉｓｔ＿ｉｎｆｏ＿β＝ｔｒｕｅであるから（ステップＳ１０２でＹｅｓ）、ルーティングテーブル更新部４８は、データ処理装置４０ｑの装置情報をルーティングテーブル記憶部４７に登録する（ステップＳ１０３）。
その後、ルーティングテーブル更新部４８は、ステップＳ９１で受信した更新要求（担当区間の変更を表す情報）を、自装置のサクセッサであるデータ処理装置４０ｍに転送する（ステップＳ１０４）。これにより、ルーティングテーブル更新部４８は、更新動作を終了する。このような動作により、データ処理装置４０ｋのルーティングテーブル記憶部４７からは、データ処理装置４０ｏの装置情報が削除され、データ処理装置４０ｑの装置情報が登録される。
以降、各データ処理装置４０ｍ〜４０ｎは、上記同様に、順次、更新要求（担当区間の変更を表す情報）を受信することにより、ルーティングテーブル更新動作を行う。
そして、データ処理装置４０ｏは、データ処理装置４０ｎから、更新要求（担当区間の変更を表す情報「（２０２，２１０，データ処理装置４０ｏのアドレス）、（２１１，２２５，データ処理装置４０ｑのアドレス）」）を受信する（ステップＳ９１）。
これにより、データ処理装置４０ｏのルーティングテーブル更新部４８は、自装置の担当区間の最小値ｋｍｉｎ（２０２）が、受信した情報に含まれるｋｍｉｎ＿α（２０２）と等しいため（ステップＳ９２でＹｅｓ）、更新動作を終了する。
なお、データ処理装置４０ｏ（４０αに該当）のルーティングテーブル更新部４８は、変更前の自装置の転送範囲に含まれるｋｍｉｎ＿α＋ｃｉで表されるキーのうち、データ処理装置４０ｑ（４０βに該当）の新たな担当区間に含まれるものがあれば、データ処理装置４０ｑに関する装置情報をルーティングテーブル記憶部４７に登録する。
なお、データ処理装置４０ｑのルーティングテーブル更新部４８は、図１９に示したルーティングテーブル初期化動作を行う。
次に、第３実施形態における効果について述べる。
第３実施形態のデータ分散処理システム３０およびデータ処理装置４０は、処理データを、該処理データの処理に関連する格納データを格納するノードまで高速に転送しながらも、ルーティングテーブルの管理コストを抑えることができる。
その理由は、各データ処置装置４０のルーティングテーブルが、転送範囲の管理キーを担当する全ての他のデータ処理装置ではなく、そのうち一部の装置情報を記憶するからである。この第３実施形態においても、処理データを受信したデータ処理装置は、該処理データの処理に関連する格納データを格納するデータ処理装置の少なくとも１つを転送範囲に含むことは第２実施形態と同様である。これにより、この第３実施形態のデータ処理装置４０も、第２実施形態と同様に、一定のホップ数以下で処理データを転送できる。これにより、転送範囲の管理キーを担当する全ての他のデータ処理装置がルーティングテーブル記憶部に記憶されている場合に比べて、第３実施形態のデータ分散処理システム３０およびデータ処理装置４０は、ルーティングテーブルに必要なリソースや更新にかかる処理を軽減することができる。
また、第３実施形態のデータ分散処理システム３０およびデータ処理装置４０は、ノードの担当区間に変更があった場合でも、処理データを、該処理データの処理に関連する格納データを格納するノードまで、高速に転送できる。
その理由について述べる。第３実施形態におけるルーティングテーブル更新部４８は、更新要求（他装置の担当区間の変更を表す情報）を受信すると、担当区間が変更されたデータ処理装置の装置情報を追加または削除するか否かの判断を行う。その判断は、変更された担当区間が、自装置の転送範囲内であり、かつ、自装置の担当区間の最小値からの距離が基数のｉ乗であるキーを含むか否かに基づいて、行われる。これにより、第３実施形態のデータ処理装置４０は、他装置の担当区間の変更にも柔軟に対応して、キー空間の［１／多重度］の範囲を担当する装置の最新情報を格納していることになる。
なお、第３実施形態では、ルーティングテーブル記憶部４７が、転送範囲の管理キーを担当する一部の転送候補のデータ処理装置の装置情報を記憶する場合に、ルーティングテーブル更新部４８がこれを初期化および更新する例について説明した。さらに、第３実施形態のルーティングテーブル更新部４８は、第２実施形態のデータ処理装置２０にも適用可能である。この場合には、ルーティングテーブル更新部４８は、担当区間が変更されたデータ処理装置４０の新たな担当区間が、自装置の転送範囲とオーバラップするか否かに基づいて、担当区間が変更されたデータ処理装置４０の装置情報を追加または削除する処理を行えばよい。
なお、本発明は上記各実施形態に限定されることはなく、様々な実施の形態を採り得る。例えば、上記各実施形態において、データ処理装置の各機能は、コンピュータ装置（ＣＰＵ）がプログラム記憶媒体から読み出したコンピュータプログラムを実行することにより実現する例について説明している。つまり、上記各実施形態では、本発明がハードウェア資源とそのハードウェア資源において実行されるコンピュータプログラム（ソフトウェア）との協働により実現される例を示しているが、本発明は、コンピュータプログラム（ソフトウェア）が記憶されたプログラム記憶媒体により実現されるとも言える。
また、本発明は、上記各実施形態を適宜組み合わせて実施することが可能である。
以上、実施形態を参照して本願発明を説明したが、本願発明は上記実施形態に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
なお、この出願は、２０１１年８月２２日に出願された日本出願特願２０１１−１８０４６２を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【００１０】
本発明は、データを分散して処理する様々なシステムに適用可能である。
【符号の説明】
【００１１】
１，２０，４０  データ処理装置
１０，３０  データ分散処理システム
８０  処理データ入力装置
９０  格納データ入力装置
２１  格納データ転送部
１２，２２  処理データ転送部
２３  処理部
２４  キー生成部
１５，２５  管理キー記憶部
２６  格納データ記憶部
１７，２７，４７  ルーティングテーブル記憶部
４８  ルーティングテーブル更新部
１００１  ＣＰＵ
１００２  ＲＡＭ
１００３  ＲＯＭ
１００４  記憶装置
１００５  ネットワークインタフェース
【図１】
2013027784.tif 000003
【図２】
2013027784.tif 000004
【図３】
2013027784.tif 000005
【図４】
2013027784.tif 000006
【図５】
2013027784.tif 000007
【図６】
2013027784.tif 000008
【図７】
2013027784.tif 000009
【図８】
2013027784.tif 000010
【図９】
2013027784.tif 000011
【図１０】
2013027784.tif 000012
【図１１】
2013027784.tif 000013
【図１２】
2013027784.tif 000014
【図１３】
2013027784.tif 000015
【図１４】
2013027784.tif 000016
【図１５】
2013027784.tif 000017
【図１６】
2013027784.tif 000018
【図１７】
2013027784.tif 000019
【図１８】
2013027784.tif 000020
【図１９】
2013027784.tif 000021
【図２０】
2013027784.tif 000022
【図２１】
2013027784.tif 000023
【国際調査報告】
2013027784.tif 000024
2013027784.tif 000025
2013027784.tif 000026
2013027784.tif 000027