(57)【特許請求の範囲】
【請求項１】
ｍ桁の連続数値である管理キーの値の範囲が複数区間に分割されたときの各分割区間の内、自装置に割り当てられた区間の範囲（自範囲）以外の各区間を割り当てられた各々の他のデータ処理装置（他装置）と接続され、
前記自範囲を記憶する管理キー保持手段と、
ｍ桁の数値である基準キーに関連付けられた処理データを受信して、
前記処理データの基準キーが前記自範囲外であれば、前記処理データを、
（ａ）前記処理データの基準キーと下位ｊ（＜ｍ）桁が一致する、前記自範囲より大きな数値の管理キーを含む範囲が割り当てられた正常動作中の他装置の中で、最小の管理キーの範囲を割り当てられた他装置（上位装置）、または、
（ｂ）前記処理データの基準キーと下位ｊ（＜ｍ）桁が一致する、前記自範囲より小さな数値の管理キーを含む範囲が割り当てられた正常動作中の他装置の中で、最大の管理キーの範囲を割り当てられた他装置（下位装置）、
の一方に転送する処理データ転送手段を備えるデータ処理装置。
【請求項２】
前記処理データ転送手段は、前記処理データを、前記上位装置と前記下位装置の内、定められた一方に転送する、または、
自範囲と前記上位装置に割り当てられた管理キーの範囲の距離と自範囲と前記下位装置に割り当てられた管理キーの範囲の距離とを比較して、距離が小さな一方に転送する、請求項１のデータ処理装置。
【請求項３】
格納データ保持手段と、
前記格納データ保持手段内の格納データを用いて所定の処理を実行する処理手段と、
基準キーに関連付けられた格納データを受信して、前記格納データの基準キーと下位ｊ（＜ｍ）桁が一致するキーが前記自範囲内であれば、前記処理データを前記格納データ保持手段に格納し、
前記自範囲外であれば、前記格納データを前記格納データの基準キーと下位ｎ桁が一致する管理キーを含む範囲が割り当てられた複数の他装置に転送する格納データ転送手段を備える請求項１乃至２の何れかのデータ処理装置。
【請求項４】
請求項１乃至３の何れかのデータ処理装置と、
前記自範囲以外の各区間を割り当てられた各々の他装置と、
前記データ処理装置に接続され、前記データ処理装置に処理データを送信する処理データ入力装置を包含するデータ分散処理システム。
【請求項５】
ｍ桁の連続数値である管理キーの値の範囲が複数区間に分割されたときの各分割区間の内、自装置に割り当てられた区間の範囲（自範囲）以外の各区間を割り当てられた各々の他のコンピュータ（他装置）と接続されたコンピュータに、
自装置が備える管理キー保持手段に前記自範囲を記憶する管理キー保持処理と、
ｍ桁の数値である基準キーに関連付けられた処理データを受信して、
前記処理データの基準キーが前記自範囲外であれば、前記処理データを、
（ａ）前記処理データの基準キーと下位ｊ（＜ｍ）桁が一致する、前記自範囲より大きな数値の管理キーを含む範囲が割り当てられた正常動作中の他装置の中で、最小の管理キーの範囲を割り当てられた他装置（上位装置）、または、
（ｂ）前記処理データの基準キーと下位ｊ（＜ｍ）桁が一致する、前記自範囲より小さな数値の管理キーを含む範囲が割り当てられた正常動作中の他装置の中で、最大の管理キーの範囲を割り当てられた他装置（下位装置）、
の一方に転送する前記処理データ転送処理を実行させるデータ処理プログラム。
【請求項６】
前記コンピュータに、
前記処理データを、前記上位装置と前記下位装置の内、定められた一方に転送する、または、
自範囲と前記上位装置に割り当てられた管理キーの範囲の距離と自範囲と前記下位装置に割り当てられた管理キーの範囲の距離とを比較して、距離が小さな一方に転送する前記処理データ転送処理を実行させる、請求項５のデータ処理プログラム。
【請求項７】
前記コンピュータに、
前記コンピュータが備える格納データ保持手段内の格納データを用いて所定の処理を実行する処理実行処理と、
基準キーに関連付けられた格納データを受信して、前記格納データの基準キーと下位ｊ（＜ｍ）桁が一致するキーが前記自範囲内であれば、前記処理データを前記格納データ保持手段に格納し、
前記自範囲外であれば、前記格納データを前記格納データの基準キーと下位ｎ桁が一致する管理キーを含む範囲が割り当てられた複数の他装置に転送する格納データ転送処理を実行させる請求項５乃至６の何れかのデータ処理プログラム。
【請求項８】
ｍ桁の連続数値である管理キーの値の範囲が複数区間に分割されたときの各分割区間の内、自装置に割り当てられた区間の範囲（自範囲）以外の各区間を割り当てられた各々の他のデータ処理装置（他装置）と接続されたデータ処理装置が、
自装置が備える管理キー保持手段に前記自範囲を記憶し、
ｍ桁の数値である基準キーに関連付けられた処理データを受信して、
前記処理データの基準キーが前記自範囲外であれば、前記処理データを
（ａ）前記処理データの基準キーと下位ｊ（＜ｍ）桁が一致する、前記自範囲より大きな数値の管理キーを含む範囲が割り当てられた正常動作中の他装置の中で、最小の管理キーの範囲を割り当てられた他装置（上位装置）、または、
（ｂ）前記処理データの基準キーと下位ｊ（＜ｍ）桁が一致する、前記自範囲より小さな数値の管理キーを含む範囲が割り当てられた正常動作中の他装置の中で、最大の管理キーの範囲を割り当てられた他装置（下位装置）、
の一方に転送するデータ処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ処理装置、データ分散処理システム、データ処理プログラム、及び、データ処理方法に関する。
【背景技術】
【０００２】
特許文献１は、方向が決められたリングトポロジに配列された複数のノードからなるシステムの分散ディレクトリのコンテンツを検索するための方法を開示する。この方法は、分散ハッシュ関数によってコンテンツの格納ノードを特定する。また、バックアップのため、コンテンツが前方ノードで複製される。
【０００３】
特許文献２は、ネットワークに接続された複数のピアを開示する。各ピアは、複数属性のデータを一次元の値に変換して論理識別子を生成し、各ピアに対する論理識別子の割り当てにもとづいて、生成した論理識別子を管理する他のピアを特定し、特定した他のピアにデータを登録する。
【０００４】
特許文献３は、データから生成されたハッシュ値と近いハッシュ値を持つノードに、データの実体の保存場所情報を登録する技術を開示する。
【０００５】
非特許文献１は、キーを割り当てられた複数のノードから成るシステムを開示する。当該システムは、オブジェクトの識別子の少なくとも先頭ｉビットがキーと一致するノードに当該オブジェクトを配置する。ビット数ｉはオブジェクトの人気等によって算出される。当該システムにおいて、各ノードが開始した或るオブジェクトの検索は高々ｉホップで終了する。
【０００６】
非特許文献２は、自装置に割り当てられたキー対応のデータを格納する複数のノードから成るシステムにおけるデータ検索プロトコル（Chord）を開示する。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特表２００９−５４３２３７号公報
【特許文献２】特開２００８−２３４５６３号公報
【特許文献３】特許第４３０６７４０号公報
【非特許文献】
【０００８】
【非特許文献１】V. Ramasubramanian and E. G. Sirer, “Beehive: Exploiting powerlaw query distributions for O(1) lookup performance in peer to peer overlays,” in Proceedings of the 1st USENIX Symposium on Networked Systems Design and Implementation, 2004
【非特許文献２】Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek ,Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
複数のノードからなるシステムが、適切な多重度の複製データ・代替可能装置を有することが出来ない。
【００１０】
特許文献１及び非特許文献１に記載された技術は、複製データの多重度を制御できない。他の文献に記載された技術は、複製データ・代替可能装置の保持を可能にしない。本発明の目的は、上記課題を解決するための技術を提供することにある。
【課題を解決するための手段】
【００１１】
本発明の一実施形態のデータ処理装置は、ｍ桁の連続数値である管理キーの値の範囲が複数区間に分割されたときの各分割区間の内、自装置に割り当てられた区間の範囲（自範囲）以外の各区間を割り当てられた各々の他のデータ処理装置（他装置）と接続され、前記自範囲を記憶する管理キー保持手段と、ｍ桁の数値である基準キーに関連付けられた処理データを受信して、前記処理データの基準キーが前記自範囲内であれば、前記処理データを所定処理の対象とし、前記自範囲外であれば、前記処理データを前記処理データの基準キーと下位ｊ（＜ｍ）桁が一致する数値の管理キーを含む範囲が割り当てられた正常動作中の他の装置のいずれかに転送する処理データ転送手段を備える。
【００１２】
本発明の一実施形態のデータ処理プログラムは、ｍ桁の連続数値である管理キーの値の範囲が複数区間に分割されたときの各分割区間の内、自装置に割り当てられた区間の範囲（自範囲）以外の各区間を割り当てられた各々の他のコンピュータ（他装置）と接続されたコンピュータに、自装置が備える管理キー保持手段に前記自範囲を記憶する管理キー保持処理と、ｍ桁の数値である基準キーに関連付けられた処理データを受信して、前記処理データの基準キーが前記自範囲内であれば、前記処理データを所定処理の対象とし、前記自範囲外であれば、前記処理データを前記処理データの基準キーと下位ｊ（＜ｍ）桁が一致する数値の管理キーを含む範囲が割り当てられた正常動作中の他のコンピュータのいずれかに転送する処理データ転送処理を実行させる。
【００１３】
本発明の一実施形態のデータ処理方法は、ｍ桁の連続数値である管理キーの値の範囲が複数区間に分割されたときの各分割区間の内、自装置に割り当てられた区間の範囲（自範囲）以外の各区間を割り当てられた各々の他のデータ処理装置（他装置）と接続されたデータ処理装置が、自装置が備える管理キー保持手段に前記自範囲を記憶し、ｍ桁の数値である基準キーに関連付けられた処理データを受信して、前記処理データの基準キーが前記自範囲内であれば、前記処理データを所定処理の対象とし、前記自範囲外であれば、前記処理データを前記処理データの基準キーと下位ｊ（＜ｍ）桁が一致する数値の管理キーを含む範囲が割り当てられた正常動作中の他の装置のいずれかに転送する。
【発明の効果】
【００１４】
本発明は、複数のノードからなるシステムにおいて、要求される信頼度、システム内のノードの台数応じて、適切な多重度の複製データ・代替可能な装置を有することを可能とする。
【図面の簡単な説明】
【００１５】
【図１】図１は、第１の実施の形態に係るデータ分散処理システム１０の全体構成を示す。
【図２】図２は、図１のデータ分散処理システム１０のデータの格納動作例を示す。
【図３】図３は、キー生成部２４がシードから生成キーを算出する過程の例を示す。
【図４】図４は、図１のデータ分散処理システム１０のデータの処理動作例を示す。
【図５】図５はデータ処理装置２０の構成を示す。
【図６】図６は、管理キー保持部２５に格納されるデータを示す。
【図７】図７は、処理データ転送部２２の動作フローチャートである。
【図８】図８は、処理データ転送部２２の距離ｄ算出のフローチャートである。
【図９】図９は、キー生成部２４の動作フローチャートである。
【図１０】図１０は、格納データ転送部２１の動作フローチャートである。
【図１１】図１１は、処理部２３の動作フローチャートである。
【図１２】図１２は、第２の実施形態に係るデータ処理装置２０の構成を示す。
【発明を実施するための形態】
【００１６】
図１は、第１の実施の形態に係るデータ分散処理システム１０の全体構成を示す。データ分散処理システム１０は、主ネットワーク１１に接続された複数のデータ処理装置２０を包含する。図１に於いて、円で囲まれたａ乃至ｐの各々はデータ処理装置２０である。以降、図中ａで表されるデータ処理装置２０は、データ処理装置２０ａと表記される。ｂ以降も同様である。
【００１７】
データ分散処理システム１０においては、任意の２つのデータ処理装置２０が、主ネットワーク１１経由で直接通信可能でなくても良い。２つのデータ処理装置２０が、他のデータ処理装置２０を経由して互いに通信可能であってもよい。
【００１８】
データ分散処理システム１０の管理者等は、各データ処理装置２０に管理キーの範囲を割り当てる。管理キーはｍビットの連続２進数値である。管理キーの基数は他の値であっても良い。基数は、データ分散処理システム１０で一意に決まっている。
【００１９】
データ分散処理システム１０の管理者等は、管理キーの値の範囲を複数の連続区間に分割し、各区間を各データ処理装置２０に順次、例えば、データ処理装置２０ａを起点に時計回り方向に割り当てる。データ分散処理システム１０の管理者等は、各区間を各データ処理装置２０に、他のデータ処理装置２０を起点に反時計回りに割り当てても良い。
【００２０】
図１に於いて、データ処理装置２０ａは、値がｓａからｅａの範囲の管理キーが割り当てられている。データ処理装置２０ｂは、値がｓｂからｅｂの範囲の管理キーが割り当てられている。他のデータ処理装置２０も同様に管理キーの範囲が割り当てられている。
【００２１】
ここで、ｓａは管理キーの最小値、ｅｑは最大値であり、ｓａ＜ｅａ＜ｓｂ＜ｅｂ．．．．＜ｅｑの関係にある。１つのデータ処理装置２０、例えばデータ処理装置２０ａが、管理キーの最小値と、最大値を含む区間を割り当てられていても良い。この場合、データ処理装置２０ａに割り当てられた区間は、ｓａから管理キーの最大値までの区間と最小値からｅｂ（＜ｓａ）までの区間を併せたものとなる。
【００２２】
なお、各データ処理装置２０が割り当てられる管理キーの範囲の大きさは、同じであっても良いし、異なっていても良い。各範囲が包含する管理キーは１つでも複数でも良い。
【００２３】
データ処理装置２０のうち、少なくとも１台、例えばデータ処理装置２０ｊは、副ネットワーク１２等を経由して、処理データ入力装置１３、または、格納データ入力装置１４と接続している。なお、副ネットワーク１２と主ネットワーク１１は、同一のネットワークであっても良い。
【００２４】
図２は、図１のデータ分散処理システム１０のデータの格納動作例を示す。図２において、主ネットワーク１１等の記載は省略されている。データ分散処理システム１０の管理者等は、各データ処理装置２０に、例えば、当該装置を示す記号付近にカギ括弧で囲まれた範囲の管理キーを割り当てている。例えば、データ処理装置２０ａは、値が０から１３の範囲の管理キーが割り当てられている。データ処理装置２０ｂは、値が１４から３０の範囲の管理キーが割り当てられている。他のデータ処理装置２０も同様に管理キーの範囲が割り当てられている。
【００２５】
図２のデータ分散処理システム１０において、例えば、データ処理装置２０ｊは、格納データ入力装置１４から格納データを受信し、当該格納データをデータ処理装置２０ｃ、ｈ、ｐ、ｍに転送する。データ処理装置２０ｃ、ｈ、ｐ、ｍは、格納データを受信して記憶する。
【００２６】
このときデータ処理装置２０ｊは、図３に示すような過程を経て転送先のデータ処理装置２０を決定する。
【００２７】
先ず、データ処理装置２０ｊは、格納データに関連付けられた基準キーを得る。格納データに関連付けられた基準キーは、例えば、格納データに含まれるシードから算出されるハッシュ値である。シードは、ハッシュ値算出の基となるデータである。基準キーは、格納データとは別に受信されるシードのハッシュ値であっても良いし、格納データ、または格納データと別に受信されるデータの一部の値であっても良い。
【００２８】
図３に於ける基準キーは、シード”田町駅”から算出されるハッシュ値である。当該基準キーは、２進数で”１０１０１０１０”、即ち１０進数で”１７０”である。
【００２９】
次に、データ処理装置２０ｊは、基準キーの上位ｎ桁を、ｎ桁がとりうる値全ての値で置換して、複数のキー（生成キー）を算出する。
【００３０】
図３に於ける生成キーは、ハッシュ値”１０１０１０１０”の上位２ビットを、｛００，０１，１０，１１｝のそれぞれに置き換えた４個の値である。生成キーは、１０進数でそれぞれ、”４２”、”１０６”、”１７０”、”２３４”となる。
【００３１】
データ処理装置２０ｊは、割り当てられた管理キーの範囲内に各生成キーを包含する４台のデータ処理装置２０ｃ、ｈ、ｐ、ｍに格納データを転送する。
【００３２】
図４は、図１のデータ分散処理システム１０のデータの処理動作例を示す。図４において、主ネットワーク１１等の記載は省略されている。図４のデータ分散処理システム１０の管理者等は、各データ処理装置２０に、例えば、図３と同じ範囲の管理キーを割り当てている。
【００３３】
図４のデータ分散処理システム１０において、例えば、データ処理装置２０ｊは、処理データ入力装置１３から処理データを受信し、当該処理データをデータ処理装置２０ｍに転送する。データ処理装置２０ｍは、処理データを受信して、当該データに対して所定の処理を実行する。
【００３４】
処理データを受信したデータ処理装置２０ｊは、処理データに関連付けられた基準キーから生成キーを算出する。この算出は、格納データを受信したデータ処理装置２０ｊが行った生成キーの算出と同様である。
【００３５】
例えば、処理データに含まれるシードが”田町駅”である場合、図３に示すように、生成キーは、１０進数でそれぞれ、”４２”、”１０６”、”１７０”、”２３４”となる。
【００３６】
データ処理装置２０ｊは、割り当てられた管理キーの範囲内に、自装置に割り当てられた管理キーの範囲（１２７乃至１３９）との距離（図８等を参照）が最も近い生成キー”１７０”を包含するデータ処理装置２０ｍに処理データを転送する。
【００３７】
処理データは、データ処理装置２０ｊからデータ処理装置２０ｍへホップ・バイ・ホップで転送される。当該処理データは、データ処理装置２０ｍに到達するまでにデータ処理装置２０ｋやデータ処理装置２０ｌ等の、他のデータ処理装置２０を経由するかもしれない。どのデータ処理装置２０を経由するかは、データ分散処理システム１０に適用するルーティングプロトコルに依存する。
【００３８】
但し、本実施形態のデータ分散処理システム１０は、割り当てられた管理キーの距離が近いデータ処理装置２０間のポップ数が、割り当てられた管理キーの距離が遠いデータ処理装置２０間のポップ数以下になるようなルーティングプロトコルを使用する。このようなプロトコルの例は、非特許文献２に記載されている。
【００３９】
データ処理装置２０ｍで実行される所定の処理は、データ分散処理システム１０に対応して決まっている。
【００４０】
データ処理装置２０ｊが受信した処理データをデータ処理装置２０ｍに転送する理由は、例えば、所定の処理が、図２で説明した格納データを要求するからである。或いは、例えば、所定の処理が、データ処理装置２０ｃ、ｈ、ｐ、ｍだけが備える高性能プロセッサ、画像処理エンジン等の装置を必要とするからである。
【００４１】
なお、データ処理装置２０ｍが正常に動作していないような場合、処理データは、例えば、データ処理装置２０ｐに転送される。その理由は、データ処理装置２０ｐは、図２が示すようにデータ処理装置２０ｍと同じ格納データの複製を有する、或いはデータ処理装置２０ｍが備える装置と代替可能な装置を備えるからである。
【００４２】
本実施形態のデータ分散処理システム１０は、例えば、publish/subscribe(pub/sub)型のシステムとして動作する。このシステムに於いて、格納データ入力装置１４等で実行されるアプリケーションプログラムは、あらかじめサブスクリプションを格納データとして何れかのデータ処理装置２０、例えば、データ処理装置２０ｊに入力する。サブスクリプションは、何れかのデータ処理装置２０、例えば、データ処理装置２０ｍ等に格納される。
【００４３】
サブスクリプションは、イベントの条件と当該条件を満足するイベントが入力されたときに通知する外部システムのアドレスから構成される。
【００４４】
あるデータ処理装置２０が、処理データ入力装置１３から処理データとしてイベントを入力した場合、当該データ処理装置２０は、当該イベントを、サブスクリプションを格納しているデータ処理装置２０に転送する。例えば、データ処理装置２０ｊが、処理データ入力装置１３から処理データとしてイベントを入力し、当該イベントを、サブスクリプションを格納しているデータ処理装置２０ｍに転送する。
【００４５】
サブスクリプションを格納しているデータ処理装置２０は、転送されたイベントと登録されているサブスクリプションのイベント条件を照合し、合致すれば当該イベントをサブスクリプションで指定された外部システムに通知する。
【００４６】
この場合、入力されたイベントと登録されているイベント条件の照合、外部システムへの通知が、上述した所定の処理に該当する。
【００４７】
なお、イベントは１つ以上のデータ項目からなる処理データである。各データ項目は、属性名と属性値から構成される。例えば、処理データ入力装置１３が、センサが観測した２０℃の温度、６０％の湿度を基にイベントを生成する場合、イベントは、属性名が“温度”で属性値が２０℃であるデータ項目と、属性名が“湿度”で属性値が６０％であるデータ項目から構成される。
【００４８】
本システムのデータ処理装置２０は、サブスクリプション、及びイベントの属性値をシードとして、生成キーを算出する。
【００４９】
また、本実施形態のデータ分散処理システム１０は、オブジェクトデータを分散して格納するストレージとしても機能出来る。この場合、各オブジェクトデータは、各データ処理装置２０が分担して格納する格納データである。
【００５０】
オブジェクトデータを要求する処理データ入力装置１３がデータの条件（クエリ）を処理データとしてデータ分散処理システム１０に入力する。クエリを入力したデータ処理装置２０、例えばデータ処理装置２０ｊは、上述と同様にオブジェクトデータを格納するデータ処理装置２０、例えばデータ処理装置２０ｍを特定する。
【００５１】
データ処理装置２０ｊは、データ処理装置２０ｍからクエリ実行結果としての当該オブジェクトデータを受信して、処理データ入力装置１３に応答する。この場合、クエリを実行して要求されたオブジェクトデータを得ることが、データ処理装置２０が実行する所定の処理となる。
【００５２】
図５は、本実施の形態のデータ処理装置２０の構成を示す。データ処理装置２０は、処理データ転送部２２、管理キー保持部２５を包含する。データ処理装置２０は、格納データ転送部２１、処理部２３、キー生成部２４、通信部２７、格納データ保持部２６を包含していても良い。
【００５３】
格納データ転送部２１は、格納データ入力装置１４から格納データを受信して、他のデータ処理装置２０に転送等する（図２を参照）。処理データ転送部２２は、処理データ入力装置１３から処理データを受信して、他のデータ処理装置２０に転送等する（図４を参照）。キー生成部２４は、シードから生成キーを算出する（図３を参照）。
【００５４】
処理部２３は、処理データを入力して所定の処理を実行する等の機能を有する。通信部２７は、他のデータ処理装置２０との通信を行う。通信部２７は、ルーティングプロトコル処理を実行しても良い。
【００５５】
格納データ転送部２１および処理データ転送部２２は、キー生成部２４の機能を包含しても良い。格納データ転送部２１、処理データ転送部２２および処理部２３は、通信部２７の機能を包含しても良い。更に、処理部２３、格納データ保持部２６は、データ処理装置２０に接続される他の装置、例えばデータベースサーバに存在しても良い。
【００５６】
格納データ転送部２１、処理データ転送部２２および処理部２３は、専用のハードウェアで実現される。格納データ転送部２１、処理データ転送部２２および処理部２３の全部または一部は、データ処理装置２０の図示されないプロセッサが、データ処理プログラム２８を実行することで実現されても良い。
【００５７】
管理キー保持部２５、格納データ保持部２６は、ディスク装置、半導体メモリ等の記憶装置である。格納データ保持部２６は、上述したサブスクリプション、オブジェクトデータ等である格納データを格納する。格納データが具体的にどのようなデータであるかは、データ分散処理システム１０に依存する。
【００５８】
図６は、管理キー保持部２５に格納されるデータを示す。データ分散処理システム１０の管理者等は、管理キー保持部２５に、自範囲３０、キー長３１、複製桁数３２に値を設定する。
【００５９】
自範囲３０は、自装置に割り当てられた管理キーの範囲の最小値と最大値を保持する。例えば、図２、図３におけるデータ処理装置２０ｊにおいて、kminが１２７、kmaxが１３９である。格納データ保持部２６が保持する格納データは、そのシードから算出された生成キーｋが、自範囲３０の範囲内であるものである。
【００６０】
キー長３１は、管理キー、基準キー、生成キーの桁数ｍ（正の整数）を保持する。図３の例に於いて、ｍは８ビットである。キー生成部２４は、キー長３１で指定された長さのキーを生成する。
【００６１】
複製桁数３２は、格納データの複製を格納するデータ処理装置２０の数（複製多重度）の上限を、基準キー、生成キーの上位桁数ｎという形式で保持する。複製多重度の上限は基準キー、生成キーの基数のｎ乗である。図３の例に於いてｎは２ビットであり、複製多重度の上限は２の２乗で４となる。
【００６２】
なお、本発明に於いては、ｍ桁の基準キー、生成キーの上位ｎ桁と下位ｊ（＝ｍ−ｎ）桁に分けて扱う場合がある。
【００６３】
なお、データ分散処理システム１０の格納データの複製多重度が、上限より小さくなる場合がある。格納データ転送部２１は、上限数の分散された値の生成キーを算出し、複製を、各生成キーを自範囲３０内に含むデータ処理装置２０に作成しようとする。しかし、算出された複数の生成キーが、一台のデータ処理装置２０の自範囲３０内に含まれてしまう場合があり、この場合、複製多重度が上限より小さくなる。
【００６４】
図７は、処理データ転送部２２の動作フローチャートである。処理データ転送部２２は、処理データ入力装置１３から処理データを受信する（Ｓ１）と、処理データのシードをキー生成部２４に入力して、キー生成部２４から１以上の生成キーを取得する（Ｓ２）。
【００６５】
次に、処理データ転送部２２は、自装置に割り当てられている管理キーの範囲と、各生成キーとの距離のうち、最小の距離dminと当該dminを与える生成キーである転送ターゲットキーを求める。
【００６６】
先ず、処理データ転送部２２は、dminをＭＡＸとして初期化する（Ｓ３）。ＭＡＸは生成キーがとり得る最大値である。キー長３１がｍである場合、生成キーの最大値は、（基数のｍ乗−１）である。
【００６７】
次に、処理データ転送部２２は、各生成キーｋに対して、ステップＳ４乃至Ｓ６の処理を繰り返し実行する。
【００６８】
処理データ転送部２２は、後述する図８に示される処理を実行して自範囲３０とｋとの距離ｄを求める（Ｓ４）。dmin＞ｄならば（Ｓ５でＹ）、処理データ転送部２２は、新たにｄをdminとし、ｋを転送ターゲットキーとする（Ｓ６）。
【００６９】
各生成キーｋについて上述の処理完了後、dmin＝０でなければ（Ｓ７でＮ）、処理データ転送部２２は、転送ターゲットキーを割り当てられたデータ処理装置２０に処理データを転送する（Ｓ８）。
【００７０】
正常に転送が完了すれば（Ｓ９でＹ）、処理データ転送部２２は処理を終了する。正常に転送が完了しない場合（Ｓ９でＮ）、処理データ転送部２２は現在の転送ターゲットキーであるところの生成キーを削除して（ＳＡ）、Ｓ３から繰り返し実行する。
【００７１】
正常に転送が完了しない場合（Ｓ９でＮ）、処理データ転送部２２は、現在の転送ターゲットキーで示される転送先のデータ処理装置２０に障害が発生していると判断して上記処理を行う。 なお、ステップＳＡで削除された生成キーは、ステップＳ４乃至Ｓ６の処理対象にならない。
【００７２】
dmin＝０であれば（Ｓ７でＹ）、処理データ転送部２２は、自装置の処理部２３に処理データを送信して（ＳＢ）、処理を終了する。
【００７３】
図８は、処理データ転送部２２の距離ｄ算出のフローチャートである。本図は、図２または図３於ける各データ処理装置２０が、処理データを時計回り方向に転送することを前提としたときの距離（時計回り距離）算出のフローチャートである。例えば、非特許文献２に記載のプロトコルを用いると、各データ処理装置２０は処理データを時計回り方向に転送する。
【００７４】
生成キーkについて、kmin＜ｋ＜kmaxが成り立つ場合（Ｓ１１でＹ）、処理データ転送部２２は距離ｄを０とする（Ｓ１２）。kminとkmaxは自範囲３０が保持する値である。
【００７５】
kmin＜ｋ＜kmaxでなく（Ｓ１１でＮ）、かつｋ＞kmaxである場合（Ｓ１４でＹ）、処理データ転送部２２は距離ｄをｋ−kmaxとする（Ｓ１３）。kmin＜ｋ＜kmaxでなく（Ｓ１１でＮ）、かつｋ＞kmaxでない場合（Ｓ１４でＮ）、処理データ転送部２２は距離ｄをＭＡＸ−kmax＋ｋ＋１とする（Ｓ１５）。
【００７６】
なお、非特許文献２に記載のプロトコルを用いる場合、各データ処理装置２０は、時計回り距離で、自装置に割り当てられた管理キーの最大値から、２の（ｉ−１）乗だけ離れた管理キーを割り当てられたデータ処理装置２０のアドレスを保持する。これにより、データ分散処理システム１０に於ける処理データのホップ数は、log(データ処理装置数/２のｎ乗)のオーダとなる。
【００７７】
各データ処理装置２０は、処理データを受信すると、処理データの基準キーに最も近い管理キーが割り当てられたデータ処理装置２０を転送先とする。前記転送データは、ホップ・バイ・ホップで、前記キーを管理するデータ処理装置２０に到達する。
【００７８】
なお、キー間の距離は時計回り距離に限られない。例えば、処理データ転送部２２は、キー間の距離として、逆時計回り距離を用いてもよい。この場合、距離ｄは、図８のＳ１４でｋ＞ｋｍｉｎ、Ｓ１３でＭＡＸ−ｋ＋ｋｍｉｎ＋１、Ｓ１５でＫｍｉｎ−ｋとなる。更に、処理データ転送部２２は、キー間の距離として、時計回り距離と逆時計回り距離のうち、より小さい値を距離としてもよい。
【００７９】
データ分散処理システム１０の管理者等は、システムが実行するルーティングアルゴリズムに応じて、キー間の距離が近いデータ処理装置２０間のポップ数が、距離が遠いデータ処理装置２０間のポップ数以下になるように距離を定義する。処理データ転送部２２は、当該定義に応じて距離を算出する。
【００８０】
また、処理データ転送部２２は、転送先の選択に際し、上記の距離に加えて優先度を加味しても良い。データ分散処理システム１０が複数備える代替可能な装置が全く同等でない場合等に有効である。この場合、処理データ転送部２２は、例えば、上述の距離と優先度を重み付け加算し、加算値の最小値を与えるデータ処理装置２０を転送先とする。
【００８１】
図９は、キー生成部２４の動作フローチャートである。キー生成部２４は、シードを受信する（Ｓ２１）と、まず、シードをハッシュ関数に入力しハッシュ値を得る（Ｓ２２）。次に、キー生成部２４は、複製桁数３２からビット数ｎを取得し（Ｓ２３）、ハッシュ値の上位ｎビットを当該ｎビットの取り得る全ての組み合わせのそれぞれに置き換えて生成キーとする（Ｓ２４）。前述したように、図３は、キー生成部２４の生成キー算出例を示す。
【００８２】
図１０は、格納データ転送部２１の動作フローチャートである。格納データ転送部２１は、格納データ入力装置１４から格納データと要求タイプを受信する（Ｓ３１）と、格納データのシードをキー生成部２４に入力し、１以上の生成キーを取得する（Ｓ３２）。
【００８３】
次に、格納データ転送部２１は、各生成キーｋについてステップＳ３３乃至Ｓ３５の処理を繰り返し実行する。
【００８４】
生成キーkについてkmin＜ｋ＜kmaxが成り立たない場合（Ｓ３３でＮ）、格納データ転送部２１は、生成キーｋを割り当てられたデータ処理装置２０に、格納データ、要求タイプを転送する（Ｓ３４）。kminとkmaxは自範囲３０が保持する値である。
【００８５】
kmin＜ｋ＜kmaxが成り立つ場合（Ｓ３３でＹ）、格納データ転送部２１は、自装置の処理部２３に格納データ、要求タイプを送信する（Ｓ３５）。
【００８６】
なお、要求タイプとは、格納データを登録するか、削除するかを識別するための識別子であり、“登録”、“削除”のいずれかの値を持つ。
【００８７】
図１１は、処理部２３の動作フローチャートである。処理部２３は、他のデータ処理装置２０または自装置の、格納データ転送部２１から格納データを受信する。処理部２３は、他のデータ処理装置２０または自装置の、処理データ転送部２２から処理データを受信する。
【００８８】
受信データが処理データである場合（Ｓ４１でＹ）、処理部２３は当該処理データを対象に所定の処理を実行して（Ｓ４４）動作を終了する。受信データが格納データである場合（Ｓ４１でＮ）、処理部２３は、要求タイプに応じた処理を実行して動作を終了する。
【００８９】
要求タイプが”登録”の場合（Ｓ４２でＹ）、処理部２３は受信した格納データを格納データ保持部２６に格納する（Ｓ４３）。要求タイプが”削除”の場合（Ｓ４２でＮ）、処理部２３は受信した格納データと一致するデータを格納データ保持部２６から削除する（Ｓ４５）。
【００９０】
本実施形態のデータ分散処理システム１０は、複数のデータ処理装置２０からなるシステムである。本実施形態のデータ処理装置２０は、データ分散処理システム１０が、要求される信頼度、システム内のデータ処理装置２０の台数応じて、適切な多重度の複製データ・代替可能な装置を有することを可能とする。
【００９１】
その理由は、処理データ転送部２２が、処理データを、当該処理データの基準キーと下位ｊ桁が一致する管理キーを含む範囲が割り当てられた正常動作中のいずれかの他装置に転送するからである。
【００９２】
データ分散処理システム１０の管理者等は、望ましい多重度に応じて格納データや代替可能な装置等を配置した上で、適切な自範囲３０、複製桁数３２を設定出来る。
【００９３】
本実施形態のデータ処理装置２０は、更に、データ分散処理システム１０が、要求される信頼度、システム内のデータ処理装置２０の台数応じて、適切な多重度の複製データを、装置を作成することを可能とする。
【００９４】
その理由は、格納データ転送部２１が、格納データを、当該処理データの基準キーと下位ｊ桁が一致する管理キーを含む範囲が割り当てられた正常動作中の複数の他装置に転送するからである。
【００９５】
データ分散処理システム１０の管理者等は、望ましい多重度に応じて適切な複製桁数３２を設定出来る。
【００９６】
図１２は、本発明の第２の実施形態に係るデータ処理装置２０の構成を示す。データ処理装置２０は、ｍ桁の連続数値である管理キーの値の範囲が複数区間に分割されたときの各分割区間の内、自装置に割り当てられた区間の範囲（自範囲３０）以外の各区間を割り当てられた各々の他のデータ処理装置２０（他装置）と接続されている。
【００９７】
データ処理装置２０は、自範囲３０を記憶する管理キー保持部２５と処理データ転送部２２を備える。
【００９８】
処理データ転送部２２は、ｍ桁の数値である基準キーに関連付けられた処理データを受信して、処理データの基準キーが自範囲３０内であれば、処理データを所定処理の対象とする。更に、処理データ転送部２２は、処理データの基準キーが自範囲３０外であれば、処理データを処理データの基準キーと下位ｊ（＜ｍ）桁が一致する数値の管理キーを含む範囲が割り当てられた正常動作中の他の装置のいずれかに転送する。
【００９９】
本実施形態のデータ処理装置２０は、データ分散処理システム１０が、要求される信頼度、システム内のデータ処理装置２０の台数応じて、適切な多重度の複製データ・代替可能な装置を有することを可能とする。
【０１００】
その理由は、処理データ転送部２２が、処理データを、当該処理データの基準キーと下位ｊ桁が一致する管理キーを含む範囲が割り当てられた正常動作中のいずれかの他装置に転送するからである。
【符号の説明】
【０１０１】
１０    データ分散処理システム
１１    主ネットワーク
１２    副ネットワーク
１３    処理データ入力装置
１４    格納データ入力装置
２０    データ処理装置
２１    格納データ転送部
２２    処理データ転送部
２３    処理部
２４    キー生成部
２５    管理キー保持部
２６    格納データ保持部
２７    通信部
２８    データ処理プログラム
３０    自範囲
３１    キー長
３２    複製桁数
【図１】
0005544963.tif 000002
【図２】
0005544963.tif 000003
【図３】
0005544963.tif 000004
【図４】
0005544963.tif 000005
【図５】
0005544963.tif 000006
【図６】
0005544963.tif 000007
【図７】
0005544963.tif 000008
【図８】
0005544963.tif 000009
【図９】
0005544963.tif 000010
【図１０】
0005544963.tif 000011
【図１１】
0005544963.tif 000012
【図１２】
0005544963.tif 000013