(57)【要約】【課題】  分散データ管理プログラムを用いて失われては困るデータを扱う全てのアプリケーションにおいて、障害に対してもデータの失われることのない、耐障害性が高くかつ各ノードの利用効率を向上させる。【解決手段】  本発明は、分散データ管理プログラムにおける、ノードが管理するデータの決定方法（データＩＤに近いノードＩＤを持つノードが対象データを管理）はそのままに、ある物理的なノードにおいては、ハッシュ関数によって得られた複数の仮想ノードＩＤ全てに共通となるノード固有値を設定する。また、あるデータの複製のデータＩＤを算出する際には、データＩＤのノード固有値に相当する箇所を変更することで、データのオリジナルと複製を管理するノードが物理的に別のものになる確率を高める。【選択図】  図１
2011095976.tif 000002
【特許請求の範囲】
【請求項１】
入力値の法則とは無関係な法則性のない出力を返す関数であるハッシュ関数を用いて求めたハッシュ値であるデータＩＤに近いノードＩＤを持つノードが対象データを管理する分散データ管理装置であって、
ハッシュ関数を保持するハッシュ関数記憶手段と、
ある物理的なノードに設定する複数の仮想ノードＩＤを生成する仮想ノードＩＤ生成手段を有し、
前記仮想ノードＩＤ生成手段は、
任意の手段によって算出された上位無作為値と下位無作為値との間に、物理的なノード毎の固有の値に前記ハッシュ関数記憶手段の前記ハッシュ関数を用いて算出されたノード固有値を設定することにより前記仮想ノードＩＤを生成するノード固有値挿入手段を有することを特徴とする分散データ管理装置。
【請求項２】
他のノードから自装置が担当すべきデータのデータＩＤ、キー、データを取得する通信手段と、
前記データの複製を示す複製のＩＤを算出する複製データＩＤ算出手段と、を更に有し、
前記複製データＩＤ算出手段は、
前記通信手段により取得した元のデータＩＤの前記ノード固有値に相当する箇所を、元のデータを保持しているノードＩＤとは別のノードＩＤの値をハッシュ値と組み合わせて変換する固有値部分変換手段を有することを特徴とする請求項1記載の分散データ管理装置。
【請求項３】
入力値の法則とは無関係な法則性のない出力を返す関数であるハッシュ関数を用いて求めたハッシュ値であるデータＩＤに近いノードＩＤを持つノードが対象データを管理する装置における分散データ管理方法であって、
前記装置の仮想ノードＩＤ生成手段が、
任意の手段によって算出された上位無作為値と下位無作為値との間に、物理的なノード毎の固有の値に前記ハッシュ関数を用いて算出されたノード固有値を設定することにより前記仮想ノードＩＤを生成する
ことを特徴とする分散データ管理方法。
【請求項４】
前記装置の複製データＩＤ算出手段が、
他のノードから通信手段を介して自装置が担当すべきデータのデータＩＤ、キー、データを取得し、
前記通信手段により取得した元のデータＩＤの前記ノード固有値に相当する箇所を変換する
ことを特徴とする請求項３記載の分散データ管理方法。
【請求項５】
請求項１または２に記載の分散データ管理装置の各手段としてコンピュータを機能させるための分散データ管理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散データ管理装置及び方法及びプログラムに係り、特に、ネットワーク上の複数のノード（サーバなど）上に分散しているデータを管理するための分散データ管理装置及び方法及びプログラムに関する。
【０００２】
本発明の対象である分散データ管理プログラムは、インターネットに代表されるＩＰ等を用いた各種ネットワークにおいて、複数のノード（計算機等）に跨ってデータを管理することに用いられる。これは計算機科学においてハッシュ表と呼ばれる、あるデータについて、その目印となるキー情報とデータの内容とを対にして保持するデータ管理技術を複数のノードによる分散環境に適用し、分割したハッシュ表を各ノードで分散して管理するものである。これにより実際の処理は各ノードに分散させつつ、ノード間で共通に用いるデータについては分散データ管理プログラムによって共有することができる。そのため、その適用分野は並列・分散処理等の分散コンピューティング全域に亘っている。
【背景技術】
【０００３】
本明細書において用いる分散データ管理プログラムという用語は、計算機科学においては、コンシステント・ハッシング（例えば、非特許文献１参照）、分散ハッシュテーブル（例えば、非特許文献２参照）、分散キー・バリュー・ストア（例えば、非特許文献３参照）と呼ばれる方式及びその方式を実装したプログラム類を総称したものである。これらに共通した特徴として、ハッシュ表と呼ばれるデータ管理方式を物理的に分散した複数のノード上で分割して管理するという点が挙げられる。
【０００４】
ハッシュ表とは、あるデータとそのデータを識別するキーという情報を対として持ち、このキーをハッシュ関数と呼ばれる関数に与えて得られた値（ハッシュ値）を索引として利用するものである。ハッシュ関数は入力に対して法則性のない出力を返す関数である。これにより、似たようなキーが連続する場合も、キーの索引として使われるハッシュ値はキューの連続性とは無関係な値となり、特定の領域にデータが集中することを防ぐ。
【０００５】
コンシステント・ハッシングにおいては、このハッシュ表を１つの物理的なノード（計算機等の単位）で保持するのではなく、複数のノードで分割して持つ。どのノードが分割されたハッシュ表のどの領域を担当するかは、ノードに設定されたＩＤ（本明細書ではノードＩＤと記述する）とデータキーをハッシュ関数にかけて得られたハッシュ値（本明細書では「データＩＤ」と記述する）との距離等によって決定される。
【０００６】
代表的な例では、あるＩＤを持つノードは、自身のＩＤと、自身のＩＤよりも小さいＩＤを持つノードのうち直近のノードのＩＤとの間の領域に位置するデータＩＤを持つデータを担当する仕組みになっている。
【０００７】
分散ハッシュテーブルはコンシステント・ハッシングの考え方を拡張したものである。コンシステント・ハッシングにおいては、あるノードは他のノードと通信を行うために、他の全てのノードのＩＤとアドレスとを表によって管理する。一方で、このアドレス表の管理は全体のノード数が多くなるにつれてコストが高くなり、困難になる。そこで、分散ハッシュテーブルでは、ハッシュ表だけではなくこのアドレス表についても、その全体ではなく一部だけを管理することで、管理を簡単化することを行う。一方で、データ管理方式についての多くの機能はコンシステント・ハッシングと同様のため、本発明では両者を同様に分散データ管理プログラムとして一語で同一視する。
【０００８】
分散キー・バリュー・ストアについても、コンシステント・ハッシングと同様の考え方で分散したデータ管理方式に、例えばデータの複製やキャッシュ化、トランザクションの管理といった処理を拡張したものである。やはり根本となるデータ管理方式についてはコンシステント・ハッシングと同様であるため、本発明ではこれら３つの技術を総称して分散データ管理プログラムと呼ぶ。
【０００９】
分散データ管理プログラムでは、一般にあるデータについてはそのデータＩＤと近い値のノードＩＤを持つノードにデータが管理されるため、ノードＩＤの偏りはそのままノード間のデータ管理量の偏りとなって表れる。ノードＩＤとデータＩＤの取りうる値の範囲のことを「ＩＤ空間」と呼び、上記の偏りについてはＩＤ空間内でのノードＩＤの偏りといった言い方ができる。
【００１０】
分散データ管理プログラムではこのようなＩＤ空間内でのノードＩＤの偏りについて、一般に１つの物理的なノードに対して複数の仮想的なノードＩＤを割り当てるという、確率的な対策を行う。即ち、大数の法則によって、ある物理的なノードの仮想ノードＩＤがＩＤ空間上にたくさん散らばることで、偏りを平均化し、軽減する。１つのノードに割り当てる仮想ノードＩＤの数に比例して、ＩＤ空間上の分布の偏りは軽減される。
【００１１】
ここで、分散データ管理プログラムの利用法の１つの形態について説明する。分散データ管理プログラムでは１つのハッシュ表を複数のノードで分割して管理するため、ある特定のノードが故障やプログラムの終了といった理由によってハッシュ表の構成要素としての役目を終える際、そのノードが管理していたデータは一般に失われてしまう。分散データ管理プログラムをキャッシュとして用い、データの原本は別の装置で管理しているような場合は問題ないが、分散データ管理プログラム上でデータの原本を管理していて、かつそのデータを失うことができない場合はこの構成要素の離脱に伴うデータの損失は致命的である。
【００１２】
この問題に対し、一般に失いたくないデータに対しては、そのデータの複製を生成し、別のデータＩＤを与えることで、ハッシュ表にオリジナルのデータとは全く別の新しいデータとして登録しておく利用形態が用いられる。ここで、複製のデータＩＤはオリジナルのデータＩＤから類推可能なように生成する。例えば、データキーからデータＩＤを算出するハッシュ関数をｆ（ｘ）と置く場合、その複製の算出には関数ｇ（ｘ）といったようにオリジナルのデータキーを入力として別のハッシュ関数にかけるなどの算出方法が考えられる。この形態においては、あるデータのオリジナルを管理するノードが離脱した場合も、そのデータを取得しようとしていたノードが上記のような算出論理に従ってデータの複製のデータＩＤを算出することで、このデータＩＤを管理するノードからデータの複製を取得することができる。
【００１３】
あるデータのオリジナルと複製とを管理するノードが同時に故障する等の理由によって同時に離脱した場合は、オリジナルと複製のデータが両方とも失われ、そのデータは完全に失われてしまうことになる。このような同時離脱に対して、一般にはあるデータについて複数の複製を生成することで、確率的にオリジナルと全ての複製が同時に失われてしまうことを回避する。つまり、１つのデータについて生成する複製の数に比例して、あるデータのオリジナルか複製の何れかがＩＤ空間上に存在する確率が高まる。
【先行技術文献】
【非特許文献】
【００１４】
【非特許文献１】D. Karger, E. Lehman, T. Leighton, M. Levine, D. Lewin, and R. Panigrahy, "Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web," in Proceedings of the 29th ACM Symposium on Theory of Computing (STOC'97), pp.654-663, May 1997.
【非特許文献２】I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan, "Chord: A Scalable Peertopeer Lookup Service for Internet Applications," in Proceedings of the Annual Conference of the Special Interest Group on Data Communication (SIGCOMM'01), pp.149-160, August 2001.
【非特許文献３】G. DeCandia, D. Hastorun, M. Jampani, G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall and W. Vogels, "Dynamo: Amazon's Highly Available Key-value Store,"  in Proceedings of the 21st ACM Symposium on Operating Systems Principles (SOSP'07), pp.205-220, October 2007.
【発明の概要】
【発明が解決しようとする課題】
【００１５】
上述のＩＤ空間におけるノードＩＤの偏りを回避するため、物理的なノードに複数の仮想的なノードＩＤを付与することと、データの複製の利用とを同時に用いることを考える場合、オリジナルのデータと複製のデータを管理する物理的なノードが同じになってしまう可能性が存在する。ノードやデータのＩＤを生成するハッシュ関数は入力に対して法則性を持たないため、あるデータのオリジナルと複製のデータＩＤが、ある物理的なノードのそれぞれ別の仮想ノードＩＤにマッピングされてしまう可能性がある。
【００１６】
このようなマッピングがなされた場合、オリジナルと複製の両方を別々の仮想ノードＩＤで管理している物理的なノードが故障等の理由により分散データ管理プログラムのノード同士で構成する分散データ管理システムより離脱した場合に、対象のデータを管理しているノードがシステム上に存在せず、データが失われてしまうということが、データの複製を利用しているにも関わらず一定確率で発生してしまう。
【００１７】
また、データが失われない場合も、オリジナルや幾つかの複製のうちの一定量が同時にシステムより失われることで、残りの複製等を管理するノードが離脱する際にデータが失われてしまう確率を上げていることには変わりがない。
【００１８】
この課題は、単純にデータの複製のデータＩＤの算出時に、物理的に同じノードから管理されそうであればデータＩＤの算出をやり直すといったような対処ではその場限りの対処に止まる。なぜならば、ノードは常に参加と離脱をする可能性があり、参加や離脱に伴いあるデータＩＤのデータを管理するノードは変わり続けるためである。
【００１９】
この課題に対する従来の解決手段としては、確率的な手段とＩＤ生成規則に一定の法則性を与えるものとの２種類が存在する。
【００２０】
前者（確率的な手段）は、複製の生成数を上げることで、物理的に同じノードが幾つかのオリジナルや複製を同時に管理した場合にも、幾つかの残りの複製を他の物理的に異なるノードが管理する確率を高めるものである。
【００２１】
このアプローチはシステムから特定のデータが完全に失われてしまう確率を低減するものの、各ノードで管理するデータの量は複製数に比例するため、システム全体で管理するデータ量がその最大データ量に対して大きい場合、この複製コストを無視することができない。
【００２２】
後者（ＩＤ生成規則に一定の法則性を与える）は、ある物理的なノードの仮想ノードＩＤについては、その最上位数ビットについてノードに固有の値を用い、データのオリジナルと各複製との間では該当する最上位数ビットの値を一定の法則性に従って変更することで、ある物理的なノードがデータのオリジナルと複製とを同時に管理する確率を低減するものである。
【００２３】
例えば、ある物理的なノードのノード固有値を「０１０１」（２進数にて表記）とした場合、そのノードの全ての仮想ノードＩＤの上位４ビットは全て「０１０１」になるものとする。これに対し、あるデータのオリジナルのデータＩＤが「０１０１」で始まる場合、このデータは高確率で先のノード固有値「０１０１」のノードによって管理される。この際、データの複製のデータＩＤの算出規則に、上位４ビットを必ず変えるような仕組みを入れることで、データの複製については他のノード固有値を持つ別の物理的なノードにおいて管理される確率が高くなる。
【００２４】
このアプローチは、複製の数を一般的な用法よりも増やす必要がないため、システム全体で管理するデータ量は変わらないという利点と、データがシステムから失われる確率を下げるという利点とを備える。
【００２５】
一方で、ノードＩＤの生成規則に、物理的なノード毎に固有のノード固有値という法則性を与えたがために、ＩＤ空間上でのノードＩＤの偏りは、全てこのノード固有値の偏りによって引き起こされることになってしまう。ノード固有値は物理的なノードに１つであるため、ノード毎に仮想的なノードＩＤを幾ら割り当てようとも、ノード固有値が偏ってしまった場合にはＩＤ空間上でのノードＩＤの偏りを回避することができなくなるという課題を持つ。
【００２６】
本発明は、上記の点に鑑みなされたもので、ネットワーク上の複数のノード（サーバなど）上に分散しているデータを管理する場合に、ＩＤ空間上でのノードＩＤの偏りを抑え、かつ、データのオリジナルと複製の両方を物理的に同一のノードが管理する確率を低減することが可能な分散データ管理装置及び方法及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００２７】
本発明では、この分散データ管理プログラムを用いる際、データの複製を置くことでノード故障時のデータの耐障害性を高める手法において発生する問題点をノードのＩＤの生成方法とデータの複製のＩＤの算出方法に、単純なハッシュ関数以上の処理を施すことで、確率的に解決する。
【００２８】
図１は、本発明の原理構成図である。
【００２９】
本発明（請求項１）は、入力値の法則とは無関係な法則性のない出力を返す関数であるハッシュ関数を用いて求めたハッシュ値であるデータＩＤに近いノードＩＤを持つノードが対象データを管理する分散データ管理装置であって、
ハッシュ関数を保持するハッシュ関数記憶手段９００と、
ある物理的なノードに設定する複数の仮想ノードＩＤを生成する仮想ノードＩＤ生成手段１０００を有し、
仮想ノードＩＤ生成手段１０００は、
任意の手段によって算出された上位無作為値と下位無作為値との間に、物理的なノード毎の固有の値にハッシュ関数記憶手段９００のハッシュ関数を用いて算出されたノード固有値を設定することにより仮想ノードＩＤを生成するノード固有値挿入手段１０１０を有する。
【００３０】
また、本発明（請求項２）は、他のノードから自装置が担当すべきデータのデータＩＤ、キー、データを取得する通信手段と、
データの複製を示す複製のＩＤを算出する複製データＩＤ算出手段と、を更に有し、
複製データＩＤ算出手段は、
通信手段により取得した元のデータＩＤの前記ノード固有値に相当する箇所を、元のデータを保持しているノードＩＤとは別のノードＩＤの値をハッシュ値と組み合わせて変換する固有値部分変換手段を有する。
【００３１】
本発明（請求項３）は、入力値の法則とは無関係な法則性のない出力を返す関数であるハッシュ関数を用いて求めたハッシュ値であるデータＩＤに近いノードＩＤを持つノードが対象データを管理する装置における分散データ管理方法であって、
装置の仮想ノードＩＤ生成手段が、
任意の手段によって算出された上位無作為値と下位無作為値との間に、物理的なノード毎の固有の値にハッシュ関数を用いて算出されたノード固有値を設定することにより前記仮想ノードＩＤを生成する。
【００３２】
また、本発明（請求項４）は、装置の複製データＩＤ算出手段が、
他のノードから通信手段を介して自装置が担当すべきデータのデータＩＤ、キー、データを取得し、
通信手段により取得した元のデータＩＤの前記ノード固有値に相当する箇所を変換する。
【００３３】
本発明（請求項５）は、請求項１または２に記載の分散データ管理装置の各手段としてコンピュータを機能させるための分散データ管理プログラムである。
【発明の効果】
【００３４】
上記のように本発明は、ノードＩＤの途中、上位数ビットと下位数ビットの間の残り数ビット部分に、物理的なノード毎に固有の値をもち、そのノードの全ての仮想ノードＩＤに共通の値（ノード固有値）を持つ。また、オリジナルのデータＩＤからノード固有値に相当する箇所を変更することでデータの複製のデータＩＤを算出する。これにより、分散データ管理プログラムにおけるデータ複製によるデータ冗長性の向上と、仮想ノードＩＤの生成によるＩＤ空間上のＩＤの偏りの回避とを両立することができるため、分散データ管理プログラムを用いて失われては困るデータを扱う全てのアプリケーションにおいて、障害に対してもデータの失われることのない、耐障害性が高くかつ各ノードの利用効率に優れたデータ管理を行うことができる。
【図面の簡単な説明】
【００３５】
【図１】本発明の原理構成図である。
【図２】ノードＩＤの構成を示す図である。
【図３】本発明の一実施の形態におけるシステム構成図である。
【図４】本発明の一実施の形態におけるノードの構成図である。
【図５】本発明の一実施の形態における仮想ノードＩＤの生成例である。
【図６】本発明の一実施の形態における分散データ管理プログラムにおける複製データＩＤの生成例（その１）である。
【図７】本発明の一実施の形態における分散データ管理プログラムにおける複製データＩＤの生成例（その２）である。
【発明を実施するための形態】
【００３６】
以下、図面と共に本発明の実施の形態を説明する。
【００３７】
図２は、ノードＩＤの構成を示す。同図（Ａ）は、従来のノードＩＤ２００であり、同図（Ｂ）は本発明のノードＩＤ１００の構成を示す。
【００３８】
前述の課題に対し、本発明ではノードＩＤ１００の途中の、上位数ビット１１０と下位数ビット１３０の間の残り数ビット部分に、物理的なノード毎に固有のノード固有値１２０を設定する（図２（Ｂ））。このノード固有値は上述の既存解決手段における最上位数ビットに設定したノード固有値と同様、物理的なノード毎に固有の値を持ち、そのノードの全ての仮想ノードＩＤに共通の値を持つ。
【００３９】
例えば、あるノードのノード固有値が「００１０」で、これがノードＩＤの９〜１２ビット目に相当する場合、そのノードの全ての仮想ノードＩＤの９〜１２ビット目はノード固有値である「００１０」となる。
【００４０】
また、データの複製のデータＩＤの算出方法についても、オリジナルのデータＩＤから、ノード固有値に相当する箇所を変更することで算出するものとする。
【００４１】
例えば、ノードＩＤ中のノード固有値が９〜１２ビット目に存在するとした場合、データの複製のデータＩＤは、９〜１２ビット目が異なった値を取る。仮にオリジナルのデータのデータＩＤの９〜１２ビット目が「１０１１」であった場合、複製のデータＩＤの９〜１２ビット目は「１１００」、「１１０１」、「１１１０」といったように、「１０１１」以外の値を取る。この際、「１０１１」以外の値の取り方・法則性については、オリジナルのデータＩＤにおける該当箇所と「離れている」ことが条件であるが、この「離れている」という概念については本発明を適用する分散データ管理プログラム毎に異なるため、本明細書では値の変更の仕方については限定しない。なお、代表的な例については後述する。
【００４２】
本発明の分散データ管理プログラムは、パーソナルコンピュータやサーバ等の一般に広く用いられている計算機（ノード）上のプログラムであり、複数のノード上で実行されたプログラム同士で協調し、データの管理を行うものである。
【００４３】
分散データ管理プログラムをデータ管理に利用するアプリケーションからは、擬似的に１つのハッシュ表のようなデータ管理システムに見え、実際には分散されていることを意識することなくデータ管理に利用することができる。
【００４４】
分散データ管理プログラムは、主にインターネットやインターネット・プロトコル（ＩＰ）によるローカルエリアネットワークにおいて用いられることを想定されている。
【００４５】
図３は、本発明の一実施の形態におけるシステム構成図であり、ネットワーク１２００に接続された分散データ管理プログラムのノードの関係を示すものである。各ノード（３００Ａ〜３００Ｆ）間にはどれが主でどれが従であるといったような主従関係はなく、全てのノードの関係が平等である。ＩＤ空間の偏りによっては各ノード間で担当するデータ量に大小が発生する可能性があるが、各ノードの役割としては平等である。
【００４６】
図４は、本発明の一実施の形態におけるノードの構成図である。以下、ノード３００が備える各機能について説明する。ノード３００は、自ノードＩＤ管理部４００、他ノード管理部５００、ハッシュ表管理部６００、通信部７００、探索部８００、ハッシュ関数９００、仮想ノードＩＤ生成部１０００、複製データＩＤ算出部１１００からなる。これらの各構成要素のうち、自ノードＩＤ管理部４００、他ノード管理部５００、ハッシュ表管理部６００、通信部７００、探索部８００、ハッシュ関数９００は、従来の構成と共通のものであり、本発明に特有となる部分は仮想ノードＩＤ生成部１０００中のノード固有値挿入部１０１０と、複製データＩＤ算出部１１００中の固有値部分変換部１１１０である。
【００４７】
自ノードＩＤ管理部４００は自ノードＩＤ４１０を、他ノード管理部５００は、ノードＩＤ５１０とアドレス５２０を、ハッシュ表管理部６００は、データＩＤ６１０、キー６２０、データ値６３０を、それぞれメモリ等の記憶手段に格納している。また、ハッシュ関数９００は、メモリ等の記憶手段に格納されているものとする。
【００４８】
ノード３００はその起動時に、自らのノードＩＤの算出を行うとき、他のノードの構成する分散データ管理システムに通信部７００を用いて接続を行い、システムのその時点の状態や他のノードの情報等を取得する。
【００４９】
通信部７００は分散データ管理プログラムを実行する各ノードが他のノードと通信し情報のやり取りを行うことに用いられる。
【００５０】
自らのノードＩＤは、一般にＩＰアドレスやその他の一意な識別子等のノードに固有の値を入力として、ハッシュ関数９００を用いて算出される。ここで言うハッシュ関数とは前述の通り、入力値の法則とは無関係な、法則性のない出力を返す関数のことである。代表的なハッシュ関数にはＳＨＡ−１やＭＤ５といったものが挙げられるが、本発明の手法ではハッシュ関数９００を特定のハッシュ関数には限定せず、またハッシュ関数９００によって得られるハッシュ値の大きさについても限定しない。
【００５１】
自ノードＩＤ管理部４００は、このようなハッシュ関数９００によって算出されたノード自身のノードＩＤ４１０Ａを管理する機能であると共に、後述する自身の仮想ノードＩＤをノードＩＤ４１０Ｂ〜４１０Ｃとして管理する。
【００５２】
ノード３００は分散データ管理プログラムの起動後、自身のノードＩＤを計算すると共に、他のノードからシステムの現在の状態（参加している他のノードの情報と、参加したノードが管理すべきデータの情報）を、通信部７００を用いて受け取る。
【００５３】
参加している他のノードの情報（ノード毎のノードＩＤと通信部７００で用いるノードの通信先情報（アドレス））は、ノード３００の他ノード管理部５００において、ノードＩＤ５１０とアドレス５２０の対として、他のノード毎にノードＩＤ５１０Ａ〜５１０Ｃ、アドレス５２０Ａ〜５２０Ｃとして管理される。
【００５４】
ここで、仮想ノードＩＤのような仕組みを用いる場合、他ノード管理部５００において物理的なノード毎にその仮想ノードＩＤとアドレスの対を管理する形も考えられるが、本発明においては物理的なノード毎の管理は必要条件ではないため、簡略化してノードＩＤとアドレスの対という形で記述する。この場合、他の物理的なノードの複数の仮想ノードＩＤが非連続に他ノード管理機能に表れ、場合によっては同じアドレスを指し示すような形で格納される。
【００５５】
なお、自ノードＩＤ管理部４００および他ノード管理部５００におけるノードＩＤの形式は、ここでは省略しているが図２（Ｂ）におけるノードＩＤ１００に相当する構造を取る。
【００５６】
ノード３００は他のノードから通信部７００を介して、自身が担当すべきデータについて、そのデータＩＤ、キー、データの値の３つの情報を受け取る。
【００５７】
これはハッシュ表管理部６００において、データ毎にデータＩＤ６１０、キー６２０、データ値６３０の組み合わせとして、データＩＤ６１０Ａ〜６１０Ｃ、キー６２０Ａ〜６２０Ｃ、値６３０Ａ〜６３０Ｃとして管理される。なお、データキー６１０Ａ〜６１０Ｃの形は基本的にはノードＩＤ１００と同様の構成となり、データの複製毎にノード固有値１２０に相当する箇所を後述する複製データＩＤ算出部１１００の固有値部分変換部１１１０によって変換する形となる。
【００５８】
これらの分散データ管理プログラムの起動時に行われる初期化処理が終了した後は、アプリケーションからのデータの探索要求や格納要求を通信部７００によって受け、対応する処理を行うこととなる。
【００５９】
探索要求はノード３００の探索部８００に送られる。探索要求はデータのキー６２０に相当するデータを取得するもので、ノード３００の探索部８００は、キー６２０をハッシュ関数にかけて得られたデータＩＤ６１０を管理するノードを他ノード管理部５００から探し出す。ここでもし自身がキー６１０で指定されたデータを管理するノードだった場合は、自身のハッシュ表管理部６００から対応するデータを取り出し、これを要求元へと送信する。もし自身以外のノードが管理するデータだった場合は、そのノードのアドレスを他ノード管理部５００を参照して取得し、このノードに対し要求を転送する。
【００６０】
この際、対象のデータを管理しているはずのノードが故障等によりシステムから離脱しており、対象のデータが取得できない場合には、後述する複製データＩＤ算出部１１００においてその複製のデータＩＤ６１０をキー６２０より算出し、その複製データＩＤ６１０を管理するノードへと要求を転送する形となる。また、複製データの取得にはこのような要求の失敗時にのみ行う形の他、高速化のためにオリジナルと一定数の複製へと要求を転送し、もっとも速く返ってきたデータを要求の結果として採用するといった形が考えられる。
【００６１】
アプリケーションからのデータの格納要求は、アプリケーションより渡されたデータのキーをハッシュ関数にかけ、データＩＤを算出するところから始まる。ここで得られたデータＩＤを管理すべきノードを、他ノード管理部５００を参照することで取得し、そのノードのアドレスに対しデータＩＤとアプリケーションより渡されたキーと値を送る。このデータを受け取ったノードは自身のハッシュ表管理部６００においてこのデータを管理する。
【００６２】
データの複製を用いる場合は、格納要求の受信時に、複製のデータＩＤを複製データＩＤ算出部１１００において算出する。固有値部分変換部１１１０における算出方法の具体例については後述する。
【００６３】
以下、オリジナルのデータの格納時の動作と同様に、生成された複製データＩＤを管理するノードを他ノード管理部５００によって取得し、対象のノードに対して複製のデータＩＤ、キー、値を送る。複製データを受け取ったノードは自身のハッシュ表管理部６００においてこの複製データを管理する。
【００６４】
なお、データのオリジナルと複製との間で一貫性を維持するため、一般には何らかのトランザクション管理の仕組みを適用することが考えられるため、本発明ではオリジナルと複製のデータの書き込みの順序を本実施例における順序に限定するものではない。
【００６５】
以下、本発明におけるノード固有値挿入部１０１０と固有値部分変換部１１１０のそれぞれの動作の例について説明する。
【００６６】
図５は、本発明の一実施の形態における仮想ノードＩＤの生成例であり、仮想ノードＩＤ生成部１０００及びノード固有値挿入部１０１０による仮想ノードＩＤの生成例を示している。ここでは例としてノードＩＤを３２ビットの値としている。この例では上位８ビットが上位無作為値１１０であり、続く４ビットがノード固有値１２０、下位の２０ビットが下位無作為値１３０に相当する。ここでノードＩＤａをオリジナルのノードＩＤとした場合、このノードＩＤａにおけるノード固有値（０１１０）をこの物理的なノードにおけるノード固有値として固定する。以後、仮想ノードＩＤ（ノードＩＤｂ、ノードＩＤｃ、…）の算出時には常にノード固有値部分（上位９〜１２ビット目）をこのノード固有値（０１１０）に固定する。
【００６７】
なお、仮想ノードＩＤ算出時における上位無作為値と下位無作為値は任意の手段によって算出された無作為値である。一般には、ノードのＩＰアドレスの末尾に仮想ノードＩＤの順番を付与したものを入力としてハッシュ関数に掛けた戻り値等を用いる。
【００６８】
次に、複製データＩＤ算出部１１００における固有値部分変換部１１１０による複製データＩＤの算出方法を、図６及び図７の例を用いて述べる。
【００６９】
図６は、本発明の一実施の形態における分散データ管理プログラムにおける複製データＩＤの生成例（ＩＤを生成として扱い、その差を距離と置いた場合）を示し、図７は、本発明の一実施の形態における複製データＩＤの生成例（（ＩＤビット列間の排他論理和の値を距離としておいた場合）を示す。ここで、どのノードがどのデータを格納するかを判定する基準によって、複製のデータＩＤの算出方法が変わってくる。
【００７０】
図６は最も一般的な、ノードＩＤおよびデータＩＤを整数と見立てて、データＩＤに対して最も近いノードＩＤ、あるいはデータＩＤよりも整数としての値が小さくかつ最も近いノードＩＤを持つノードにおいてデータを格納する、という判定基準を持つ分散データ管理プログラムにおける複製データＩＤの生成例である。
【００７１】
オリジナルのデータＩＤ（本来データＩＤ）の、ノードＩＤにおけるノード固有値に相当する箇所（９〜１２ビット目）が（００１０）である。複製データＩＤはこのノード固有値に相当する箇所を固有値部分変換部１１１０によって変換することで生成される。この例では、データＩＤ中の固有値部分（００１０）に、複製データＩＤ毎のビットマスク（１０００、０１００、１１００、００１０）の排他的論理和（ＸＯＲ）をかけることで、固有値部分をそれぞれ（１０１０、０１１０、１１１０、００００）に変換している。
【００７２】
これにより複製データＩＤは、本来データＩＤと上位８ビットについては良く似た値を持ちながら、固有値に相当する４ビットについては本来データＩＤと整数の差による距離の概念においてかけ離れた値を取ることとなり、本来データＩＤを仮想ノードＩＤの１つとして持つ物理的ノードが、複製データについても管理する確率を減らしている。
【００７３】
図７は、ノードＩＤとデータＩＤとの排他的論理和の値（整数）をＩＤ間の距離と考え、この距離が最も小さいノードＩＤを持つノードにおいてデータを格納する、という判定基準を持つ分散データ管理プログラムにおける複製データＩＤの生成例である。
【００７４】
オリジナルのデータＩＤ（本来データＩＤ）の、ノードＩＤにおけるノード固有値に相当する箇所（９〜１２ビット目）は上記の例と同様に（００１０）である。複製データＩＤはこのノード固有値に相当する箇所を固有値部分変換部１１１０によって変換することで生成される。この例では、データＩＤ中の固有値部分（００１０）に、複製データＩＤ毎のビットマスク（１１１１、０１１１、１０１１、００１１）の排他的論理和（ＸＯＲ）をかけることで、固有値部分をそれぞれ（１１０１、０１０１、１００１、０００１）に変換している。
【００７５】
これにより複製データＩＤは、本来データＩＤと上位８ビットについては良く似た値を持ちながら、固有値に相当する４ビットについては本来データＩＤと排他的論理和による距離の概念においてかけ離れた値を取ることとなり、本来データＩＤを仮想ノードＩＤの１つとして持つ物理的ノードが、複製データについても管理する確率を減らしている。
【００７６】
上記の実施の形態に示した方法により、前述の課題におけるＩＤ空間上でのノードＩＤの偏りを抑え、かつデータのオリジナルと複製の両方を物理的に同一のノードが管理する確率を減らす。この２つの特徴はトレードオフの関係になっており、ノード固有値の上位に位置する無作為値（ハッシュ関数によって得られた法則性のない値）のサイズが小さければＩＤ空間の偏りが大きくなり、逆に大きくすると同一のノードがオリジナルと複製の両方を管理する確率が大きくなる。
【００７７】
本発明では、ノードＩＤの生成手法とデータＩＤの生成・算出方法のみを変更するため、それ以外の分散データ管理プログラムの仕様はそのまま引き継ぐことが可能であり、前述したコンシステント・ハッシングや分散ハッシュテーブル、分散キー・バリュー・ストアの全てに適用することができる。
【００７８】
また、図４に示すノード３００の各構成要素の機能をプログラムとして構築し、ノードとして利用されるコンピュータにインストールして実行させる、または、ネットワークを介して流通させることが可能である。
【００７９】
また、構築されたプログラムをハードディスクや、フレキシブルディスク・ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。
【００８０】
なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。
【符号の説明】
【００８１】
１００  ノードＩＤ
１１０  上位無作為値
１２０  ノード固有値
１３０  下位無作為値
２００  ノードＩＤ
２１０  無作為値
３００  ノード
４００  自ノードＩＤ管理部
４１０  ノードＩＤ
５００  他ノード管理部
５１０  ノードＩＤ
５２０  アドレス
６００  ハッシュ表管理部
６１０  データＩＤ
６２０  キー
６３０  データの値
７００  通信部
８００  探索部
９００  ハッシュ関数
１０００  仮想ノードＩＤ生成部
１０１０  ノード固有値挿入部
１１００  複製データＩＤ算出部
１１１０  固有値部分変換部
１２００  ネットワーク
【図１】
2011095976.tif 000003
【図２】
2011095976.tif 000004
【図３】
2011095976.tif 000005
【図４】
2011095976.tif 000006
【図５】
2011095976.tif 000007
【図６】
2011095976.tif 000008
【図７】
2011095976.tif 000009