(57)【特許請求の範囲】
【請求項１】
データ管理システムを構成するノード装置を特定するノード特定情報を含んだノードテーブルを記憶するとともに、前記ノード特定情報とノードＩＤとの対応付けを示すキー検索用ノードテーブルを記憶する記憶部と、
前記データ管理システムに参加したノード装置のノード特定情報を前記ノードテーブルに書き込み、前記データ管理システムから離脱したノード装置のノード特定情報を前記ノードテーブルから削除するノードテーブル管理部と、
前記キー検索用ノードテーブルに設定されているノードＩＤと、前記ノードＩＤに対応付けられた前記ノード特定情報とに基づいて、各ノード装置が管理対象とするキーの管理範囲長を算出する管理範囲長演算部と、
前記ノードテーブル内のノード特定情報と、前記ノード特定情報により特定されるノード装置に対して生成されたノードＩＤとの対応付けを設定したキー検索用ノードテーブルを前記記憶部に書き込み、生成した前記キー検索用ノードテーブルに基づいて前記管理範囲長演算部により算出された各ノード装置の管理範囲長のうち最大の管理範囲長と最小の管理範囲長との差異が所定以内であると判断するまで、前記管理範囲長が最小の前記ノード装置に仮想ノードを追加し、前記仮想ノードが追加された前記ノード装置のノード特定情報と前記仮想ノードに対して生成されたノードＩＤとの対応付けを前記キー検索用ノードテーブルに追加して更新する処理を繰り返す仮想ノード登録部と、
前記キー検索用ノードテーブル内のノードＩＤと、指定されたキーに基づいて、前記キーに対応した値を管理している前記ノード装置のノード特定情報を取得するキーテーブル処理部と、
を備えることを特徴とする負荷分散装置。
【請求項２】
前記管理範囲長演算部は、前記ノード装置の管理範囲長を、前記ノード装置の性能を示す値に応じて重み付けし、
前記仮想ノード登録部は、前記ノード装置の性能を示す値に応じて重み付けされた前記管理範囲長のうち最大の管理範囲長と最小の管理範囲長との差異が所定以内であるかを判断する、
ことを特徴とする請求項１に記載の負荷分散装置。
【請求項３】
前記管理範囲長演算部は、前記仮想ノード登録部により前記仮想ノードが追加された前記ノード装置のノード特定情報と前記仮想ノードに対して生成されたノードＩＤとの対応付けが前記キー検索用ノードテーブルに追加された場合、前記キー検索用ノードテーブルに追加された前記仮想ノードのノードＩＤと隣接するノードＩＤを特定してキーの管理範囲長を算出し、前記仮想ノードが追加された前記ノード装置の管理範囲長を、算出した前記管理範囲長を加算した値に更新するとともに、前記キー検索用ノードテーブルから前記仮想ノードのノードＩＤに隣接するノードＩＤに対応したノード特定情報を読み出し、読み出したノード特定情報により特定される前記ノード装置のキー管理範囲長を、算出した前記管理範囲長を減算した値に更新する、
ことを特徴とする請求項１または請求項２に記載の負荷分散装置。
【請求項４】
前記ノード特定情報は、前記ノード装置のアドレスであることを特徴とする請求項１から請求項３のいずれかの項に記載の負荷分散装置。
【請求項５】
負荷分散装置として用いられるコンピュータを、
データ管理システムを構成するノード装置を特定するノード特定情報を含んだノードテーブルを記憶するとともに、前記ノード特定情報とノードＩＤとの対応付けを示すキー検索用ノードテーブルを記憶する記憶部、
前記データ管理システムに参加したノード装置のノード特定情報を前記ノードテーブルに書き込み、前記データ管理システムから離脱したノード装置のノード特定情報を前記ノードテーブルから削除するノードテーブル管理部、
前記キー検索用ノードテーブルに設定されているノードＩＤと、前記ノードＩＤに対応付けられた前記ノード特定情報とに基づいて、各ノード装置が管理対象とするキーの管理範囲長を算出する管理範囲長演算部、
前記ノードテーブル内のノード特定情報と、前記ノード特定情報により特定されるノード装置に対して生成されたノードＩＤとの対応付けを設定したキー検索用ノードテーブルを前記記憶部に書き込み、生成した前記キー検索用ノードテーブルに基づいて前記管理範囲長演算部により算出された各ノード装置の管理範囲長のうち最大の管理範囲長と最小の管理範囲長との差異が所定以内であると判断するまで、前記管理範囲長が最小の前記ノード装置に仮想ノードを追加し、前記仮想ノードが追加された前記ノード装置のノード特定情報と前記仮想ノードに対して生成されたノードＩＤとの対応付けを前記キー検索用ノードテーブルに追加して更新する処理を繰り返す仮想ノード登録部、
前記キー検索用ノードテーブル内のノードＩＤと、指定されたキーに基づいて、前記キーに対応した値を管理している前記ノード装置のノード特定情報を取得するキーテーブル処理部、
として機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散型データベースシステムや分散ファイルシステムにおける負荷分散に関し、特にＤＨＴ（分散ハッシュテーブル、Distributed Hash Table）によるKey-Value型データ管理システムの負荷分散装置及びプログラムに関する。
【背景技術】
【０００２】
ネットワークで接続された複数のノードを見かけ上１台の蓄積装置とみなしてデータやファイルを管理するシステムとして、分散型データベースシステムや分散ファイルシステムなどがある。このような分散型データベースシステムや分散ファイルシステムでは、「キー」と「値」を組みとしたデータ（以下、「キー」と「値」の組みを（キー、値）と記載する。）を管理するKey-Value型のデータ管理システムが使われている。大規模なKey-Value型のデータ管理システムを実現する方法としては、ＤＨＴが提案されている。ＤＨＴではシステムを構成する複数のノードにおいて、（キー、値）を分散して保管管理する。
【０００３】
ＤＨＴの代表的な方式としてChordがある（例えば、非特許文献１参照。）。Chordでは、システムに参加するノードは、ハッシュ関数を使ってノードアドレスなどからシステム内で一意なノードＩＤを生成し、ノードＩＤを値の順序で円状に配置したオーバーレイネットワークを構成する。システムに（キー、値）を保管する場合、ノードは、キーからハッシュ関数を使ってキーＩＤを生成し、オーバーレイネットワーク上でそのキーＩＤに時計周りに近いノードＩＤのノードにその（キー、値）を保管する。そして、ノードがキーを検索する場合、キーからハッシュ関数を使ってキーＩＤを生成し、そのキーＩＤに近いノードＩＤのノードを発見し、発見したノードからキーに対応する値を取得する。
【０００４】
例えば、「キー」をシステムで分散管理する対象のデータのデータ名とし、「値」をそのデータを記憶しているノードのアドレスとする。データを記憶しているノードは、データ名からハッシュ関数によりキーＩＤを生成し、オーバーレイネットワーク上でこのキーＩＤに時計周りに近いノードＩＤのノードに、データ名等を示す「キー」と自ノードのノードアドレスを示す「値」との対応付けを登録する。データを利用する利用ノードは、利用したいデータのデータ名からキーＩＤを生成し、このキーＩＤに時計周りに近いノードＩＤのノードに問合せを行なって、「キー」に対応した「値」を取得する。利用ノードは、この取得した「値」により、データを記憶しているノードのアドレスを知ることができる。
【０００５】
ＤＨＴでは、キーＩＤに近いノードＩＤのノードを発見することが必要である。ノードを発見する方式として、システムに参加している各ノードにおいて、システムに参加しているノードの一部を管理するノードテーブルを保有することにより、システム全体でノードテーブルを分散して保管する方式と、システムに参加している全ノードが登録されている完全なノードテーブルを全ノードにおいて共通に持つ方式とがある。
【０００６】
ノードテーブルを分散して保管する方式では、多数のノードから構成される大規模なシステムを構成することが可能であり、完全なノードテーブルを保管する方式は、分散してノードテーブルを保管する方式に比べて大規模なシステムを構成が難しい。一方、ノードテーブルを分散して保管する方式では、キーを検索する場合、複数のノードをルーティングしながら探すため検索時間がかかるが、完全なノードテーブルを持つ方式では、ルーティングの必要がなくO(1)の検索ができる。言い換えれば、定数オーダーの検索ができる。Chordはノードテーブルを各ノードで分散して保管する方式であり、システムに参加しているノードの数をNとすると、キーを管理しているノードを発見するまでのホップ数はO(log2N)（Ｎの対数のオーダー）となる。
【０００７】
完全なノードテーブルを保管する方式として非特許文献２、非特許文献３が提案されている。全ノードが完全なノードテーブルを共通に保管する方式では、システムへのノードの参加や離脱があった場合、全ノードがそれにあわせてノードテーブルを修正する。そのため、非特許文献２では、ハッシュ空間を分割した中に、Slice Leaderおよび、Unit Leaderのノードをそれぞれ割り当て、それらのノードを経由して階層的に全ノードに参加や離脱の通知を行っている。また、各ノードはノードテーブルを正しく保つために、ノードテーブルのノードおよび隣接ノードへの生存確認を定期的に行っている。非特許文献３では、各ノードはノードテーブの中からランダムにノードを選択し、定期的にノードテーブルを交換し合っている。
【０００８】
ＤＨＴにおけるハッシュ空間内で、各ノードが管理する範囲は、時計回りと逆方向の隣接ノード（predecessor）のＩＤから自ノードＩＤまでとなる。ＳＨＡ−１などのハッシュ関数を使うことによって生成されるノードＩＤはランダムな値であるが、一般的に、生成されるノードＩＤには偏りが生じる。このハッシュ空間上でのノードＩＤの偏りは、各ノードが管理するキーＩＤの管理範囲長の偏りとなり、結果として、システムに参加しているノードが管理する（キー、値）のデータ量に差が生じてしまう。
【０００９】
これに対処する方式として仮想ノード方式がある。仮想ノード方式では、１つのノードが複数の異なるノードＩＤを生成し、オーバーレイネットワークに参加させることで、各ノードのキー管理範囲長を均等化させる。生成する仮想ノード数は、非特許文献１では１ノード当たりlog(N)個であり、非特許文献３では１ノード当たり６０という経験的な値である。仮想ノードのノードＩＤの生成方法としては、予め決められた方法、例えば、ノードアドレスに１，２，３・・・を順番に追加した値からハッシュ関数により生成する方法や、非特許文献２で提案しているように、元のノードＩＤからハッシュ空間上で等間隔な位置に配置する方法などがある。
【００１０】
仮想ノード方式は、各ノードのキー管理範囲長を均等化するだけではなく、ノードの性能が異なる場合に、その性能に応じてノードのキー管理範囲長を調整することにも利用することができる。すなわち、性能が高いノードの仮想ノード数を増やすことで、そのノードのキー管理範囲長を広くさせることができる。しかし、ノードの性能差に応じて仮想ノード数を制御する場合、システム内のノードの性能差が大きいと仮想ノード数を多くする必要がある。そのため、ノードテーブルサイズの増大や、管理オーバーヘッドの増加などの問題が生じる。これを解決するために、特許文献１では、ハッシュ空間上でノードが管理する境界を、隣接ノード間の性能差に応じて各ノード間で調整している。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特開２００４−２５２６６３号公報
【非特許文献】
【００１２】
【非特許文献１】I. Stoica他, “Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications,” Proc. ACM SIGCOMM, 2001
【非特許文献２】金子他, “ノードの局所性と管理の公平性を考慮したOneHop-P2P拡張方式,” FIT2008, no.4, RL-006, 2008
【非特許文献３】前橋他, “大規模データ処理のための分散システムの実装とその応用”, 信学論D, Vol.J93-D, No.7, 2010
【発明の概要】
【発明が解決しようとする課題】
【００１３】
上述のように、ＤＨＴでは、ハッシュ関数を使って生成したノードＩＤを用いた場合、ハッシュ空間上でのノードの配置に偏りが生じ、その結果として各ノードが管理するキー管理範囲長に差が生じる。そこで、これを解決するために、各ノードに仮想ノードを割り当てる方法が用いられている。しかし、各ノードに固定数の仮想ノードを割り当てると、ノードテーブルサイズの増加や、管理オーバーヘッドの増加などによって必要な記憶容量が増大し、リソースの負荷が生じる。そのため、むやみに多数の仮想ノードを割り当てることには問題がある。
また、特許文献１のように、隣接ノード間の割り当て範囲を調整する方式であっても、ノードの配置がもともと偏っている場合には、割り当て範囲の調整範囲が狭くあるいは広くなりすぎてしまう。そのため、固定的数を割り当てる仮想ノード手法を併用することが必要となり、根本的な解決にはならない。
【００１４】
本発明は、このような事情を考慮してなされたもので、複数のノード装置によりデータを分散して管理するシステムにおいて、システムに参加しているノード装置を管理するために使用する記憶容量の増加を抑えながら、各ノード装置におけるデータの管理範囲長に偏りをなくすことができる負荷分散装置及びプログラムを提供する。
【課題を解決するための手段】
【００１５】
［１］  本発明の一態様は、データ管理システムを構成するノード装置を特定するノード特定情報を含んだノードテーブルを記憶するとともに、前記ノード特定情報とノードＩＤとの対応付けを示すキー検索用ノードテーブルを記憶する記憶部と、前記データ管理システムに参加したノード装置のノード特定情報を前記ノードテーブルに書き込み、前記データ管理システムから離脱したノード装置のノード特定情報を前記ノードテーブルから削除するノードテーブル管理部と、前記キー検索用ノードテーブルに設定されているノードＩＤと、前記ノードＩＤに対応付けられた前記ノード特定情報とに基づいて、各ノード装置が管理対象とするキーの管理範囲長を算出する管理範囲長演算部と、前記ノードテーブル内のノード特定情報と、前記ノード特定情報により特定されるノード装置に対して生成されたノードＩＤとの対応付けを設定したキー検索用ノードテーブルを前記記憶部に書き込み、生成した前記キー検索用ノードテーブルに基づいて前記管理範囲長演算部により算出された各ノード装置の管理範囲長のうち最大の管理範囲長と最小の管理範囲長との差異が所定以内であると判断するまで、前記管理範囲長が最小の前記ノード装置に仮想ノードを追加し、前記仮想ノードが追加された前記ノード装置のノード特定情報と前記仮想ノードに対して生成されたノードＩＤとの対応付けを前記キー検索用ノードテーブルに追加して更新する処理を繰り返す仮想ノード登録部と、前記キー検索用ノードテーブル内のノードＩＤと、指定されたキーに基づいて、前記キーに対応した値を管理している前記ノード装置のノード特定情報を取得するキーテーブル処理部と、を備えることを特徴とする負荷分散装置である。
この態様によれば、キーに対応した値を保持するノード装置を検索するためにノード装置の特定情報とノードＩＤとを対応づけたキー検索用ノードテーブルを用いるKey-Value型データ管理システムにおいて、ノード装置の参加や離脱が発生した際、負荷分散装置は、各ノード装置のキーの管理範囲長の差異が所定の範囲内になるまで、管理範囲長が最も狭いノード装置に対して仮想ノードのノードＩＤを割り当ててキーの管理範囲長を増加させる処理を繰り返し、ノード装置の特定情報と当該ノード装置に対して生成されたノードＩＤとからなるキー検索用ノードテーブルを生成する。
なお、ノード装置のキーの管理範囲は、そのノード装置のノード特定情報に対応してキー検索用ノードテーブルに登録されているノードＩＤに基づいて決まる。ノード装置に割り当てるノードＩＤは、そのノード装置のノード特定情報と、当該ノード装置に割り当て済みのノードＩＤ毎に固有の情報とを元に算出されたハッシュ値を用いることができる。
一例として、ノードＩＤに対応した管理範囲は、隣接するノードＩＤから自ノードＩＤまでである。但し、範囲の境界がどちらに属するかは適宜予め定める。
管理範囲長は、上記の管理範囲の長さであり、各ノード装置のキーの管理範囲長は、そのノード装置に割り当てられた各ノードＩＤに対応した管理範囲の長さの総計である。
各ノードのキーの管理範囲長の差異を所定の範囲内とすることは、各ノード装置の負荷を同等に近くするということである。
これにより、各ノード装置のキーの管理範囲長の不均衡を効率的に是正し、システム全体に割り当てる仮想ノードの数を抑えることができる。キーの管理範囲長の不均衡を是正することによって各ノード装置の負荷の偏りも是正され、従って、キー検索用ノードテーブルの増加を抑えながら、各ノード装置の負荷分散を行なうことが可能となる。
【００１６】
［２］  本発明の一態様は、上述する負荷分散装置であって、前記管理範囲長演算部は、前記ノード装置の管理範囲長を、前記ノード装置の性能を示す値に応じて重み付けし、前記仮想ノード登録部は、前記ノード装置の性能を示す値に応じて重み付けされた前記管理範囲長のうち最大の管理範囲長と最小の管理範囲長との差異が所定以内であるかを判断する、ことを特徴とする。
この態様によれば、負荷分散装置は、ノード性能の指標値によって各ノード装置におけるキーの管理範囲長を重み付けし、重み付けした管理範囲長が同等に近くなるまで、重み付けした管理範囲長が最も狭いノード装置に対して仮想ノードのノードＩＤを割り当てる。一例として、キーの管理範囲長の重み付けは、キーの管理範囲長に、ＣＰＵの性能を示す値の逆数を乗算したり、総ディスク容量の逆数を乗算したりすることにより行なう。言い換えれば、ノードの性能値に対するキーの管理範囲長の比の値を用いる。
従って、ノード装置の処理能力やメモリ容量などに応じた管理範囲長を各ノード装置に割り当てることができる。
【００１７】
［３］  本発明の一態様は、上述する負荷分散装置であって、前記管理範囲長演算部は、前記仮想ノード登録部により前記仮想ノードが追加された前記ノード装置のノード特定情報と前記仮想ノードに対して生成されたノードＩＤとの対応付けが前記キー検索用ノードテーブルに追加された場合、前記キー検索用ノードテーブルに追加された前記仮想ノードのノードＩＤと隣接するノードＩＤを特定してキーの管理範囲長を算出し、前記仮想ノードが追加された前記ノード装置の管理範囲長を、算出した前記管理範囲長を加算した値に更新するとともに、前記キー検索用ノードテーブルから前記仮想ノードのノードＩＤに隣接するノードＩＤに対応したノード特定情報を読み出し、読み出したノード特定情報により特定される前記ノード装置のキー管理範囲長を、算出した前記管理範囲長を減算した値に更新する、ことを特徴とする。
この態様によれば、負荷分散装置は、一旦算出した各ノード装置のキーの管理範囲長を記憶しておき、ノード装置に仮想ノードのノードＩＤが追加されてキー検索用ノードテーブルが更新されたときは、追加されたノードＩＤの仮想ノードについてキーの管理範囲長を算出する。そして、記憶していた管理範囲長のうち、仮想ノードが追加されたノード装置と、仮想ノードに隣接するノードに対応したノード装置とについて記憶していたキー管理範囲長のみを変更する。
これにより、各ノード装置のキーの管理範囲長を高速に算出することが可能となる。
【００１８】
［４］  本発明の一態様は、上述する負荷分散装置であって、前記ノード特定情報は、前記ノード装置のアドレスであることを特徴とする。
この態様によれば、キー検索用ノードテーブルに、ノード特定情報としてノードアドレスが設定される。
これにより、キーテーブル処理部は、キー検索用ノードテーブルからキーを管理するノード装置のアドレスを取得することができるため、読み出したアドレスを宛先に用いてキーに対応する値の問合せを行なうことが可能となる。
【００１９】
［５］  本発明の一態様は、負荷分散装置として用いられるコンピュータを、データ管理システムを構成するノード装置を特定するノード特定情報を含んだノードテーブルを記憶するとともに、前記ノード特定情報とノードＩＤとの対応付けを示すキー検索用ノードテーブルを記憶する記憶部、前記データ管理システムに参加したノード装置のノード特定情報を前記ノードテーブルに書き込み、前記データ管理システムから離脱したノード装置のノード特定情報を前記ノードテーブルから削除するノードテーブル管理部、前記キー検索用ノードテーブルに設定されているノードＩＤと、前記ノードＩＤに対応付けられた前記ノード特定情報とに基づいて、各ノード装置が管理対象とするキーの管理範囲長を算出する管理範囲長演算部、前記ノードテーブル内のノード特定情報と、前記ノード特定情報により特定されるノード装置に対して生成されたノードＩＤとの対応付けを設定したキー検索用ノードテーブルを前記記憶部に書き込み、生成した前記キー検索用ノードテーブルに基づいて前記管理範囲長演算部により算出された各ノード装置の管理範囲長のうち最大の管理範囲長と最小の管理範囲長との差異が所定以内であると判断するまで、前記管理範囲長が最小の前記ノード装置に仮想ノードを追加し、前記仮想ノードが追加された前記ノード装置のノード特定情報と前記仮想ノードに対して生成されたノードＩＤとの対応付けを前記キー検索用ノードテーブルに追加して更新する処理を繰り返す仮想ノード登録部、前記キー検索用ノードテーブル内のノードＩＤと、指定されたキーに基づいて、前記キーに対応した値を管理している前記ノード装置のノード特定情報を取得するキーテーブル処理部、として機能させることを特徴とするプログラムである。
【発明の効果】
【００２０】
本発明によれば、複数のノード装置によりデータを分散して管理するKey-Value型データ管理システムにおいて、システムに参加しているノード装置を管理するために使用する記憶容量の増加を抑えながら、各ノード装置におけるデータの管理範囲長に偏りをなくすことができる。
【図面の簡単な説明】
【００２１】
【図１】本発明の第１の実施形態によるデータ管理システムの構成図である。
【図２】同実施形態による負荷分散装置の構成を示すブロック図である。
【図３】同実施形態によるノードテーブルのデータ構成例を示す図である。
【図４】同実施形態によるキー検索用ノードテーブルのデータ構成例を示す図である。
【図５】同実施形態によるキーテーブルのデータ構成例を示す図である。
【図６】同実施形態によるノードテーブル管理部のノードテーブル更新処理フローを示す図である。
【図７】同実施形態による仮想ノード登録部のキー検索用ノードテーブル更新処理フローを示す図である。
【図８】同実施形態による管理範囲長演算部の管理範囲長算出処理を説明するための図である。
【図９】同実施形態によるデータ管理システムの実験結果を示す図である。
【図１０】第２の実施形態による管理範囲長演算部の管理範囲長算出処理を説明するための図である。
【図１１】第３の実施形態によるノードテーブルのデータ構成例を示す図である。
【図１２】同実施形態によるキー検索用ノードテーブルのデータ構成例を示す図である。
【図１３】同実施形態による管理範囲長演算部の管理範囲長算出処理を説明するための図である。
【発明を実施するための形態】
【００２２】
以下、図面を参照しながら本発明の実施形態を詳細に説明する。
【００２３】
[１．第１の実施形態]
[１．１  全体構成]
図１は、本発明の第１の実施形態によるデータ管理システムの構成図である。本実施形態のデータ管理システムは、ＤＨＴを用いたKey-Value（キー（鍵）−値）型データ管理システムであり、例えば、分散型データベースシステムや、分散ファイルシステムなどである。同図に示すように、データ管理システムは、通信ネットワーク５を介して複数のノード装置１を接続することにより構成される。通信ネットワーク５は、例えば、ルータなどの通信装置やケーブルなどの通信線等の各種ネットワーク装置から構成されるＩＰ（Internet Protocol、インターネットプロトコル）通信網である。ノード装置１は、負荷分散装置１０とデータ記憶部３０とを備える。データ記憶部３０は、データ管理システムにおいて管理対象となるファイル等のデータを記憶する。
【００２４】
[１．２  負荷分散装置とデータ管理システムとの関係]
負荷分散装置１０は、各ノード装置１内で動作する。ノード装置１は、例えば、ノードを実行するコンピュータ装置であり、負荷分散装置１０は、ノード装置１がアプリケーションプログラムを実行することにより実行されるプロセスに相当する。各負荷分散装置１０は、Key-Value型データ管理システムに参加しているノード装置１を管理するノードテーブルと、キー管理を行っているノード装置１の発見に用いるキー検索用ノードテーブルを保持している。Key-Value型データ管理システムへの新たなノード装置１の参加や、Key-Value型データ管理システムに参加していたノード装置１の離脱が発生した場合に、負荷分散装置１０が動作してノードテーブル及びキー検索用ノードテーブルを修正する。全ての負荷分散装置１０は同じ動作をするため、Key-Value型データ管理システム内の全ての負荷分散装置１０のノードテーブルとキー検索用ノードテーブルは同一に保たれる。
【００２５】
本実施形態において、ノードテーブルには、Key-Value型データ管理システムに参加しているノード装置１のみがノードとして登録される。一方、キーの登録や検索に使用されるキー検索用ノードテーブルには、ＤＨＴにおける円状のオーバーレイネットワークを構成するノードが登録される。オーバーレイネットワークを構成するノードには、ノード装置１のように実体があるノードと、ノード装置１に対して仮想的に生成された仮想ノードとが含まれる。本実施形態では、キー検索用ノードテーブルに仮想ノードを登録することにより負荷分散を実現する。
【００２６】
なお、ＤＨＴを用いたKey-Value型データ管理システムの構成方法や、ノードの参加・離脱の通知方法は、既存のKey-Value型データ管理システムの技術を適用する。
【００２７】
[１．３  負荷分散装置の構成]
図２は、本実施形態による負荷分散装置１０の構成を示すブロック図であり、本実施形態と関係する機能ブロックのみ抽出して示している。同図に示すように、負荷分散装置１０は、ノードテーブル管理部１１、仮想ノード登録部１２、ノードＩＤ生成部１３、管理範囲長演算部１４、記憶部１５、及び、キーテーブル処理部１６を備えて構成される。
【００２８】
記憶部１５は、ハードディスク装置や半導体メモリなどで実現され、ノードテーブル２１、キー検索用ノードテーブル２２、及び、キーテーブル２３を記録する。ノードテーブル２１は、データ管理システムを構成するノード装置１のノードＩＤとアドレスを対応付けたデータである。キー検索用ノードテーブル２２は、オーバーレイネットワークに参加しているノードのノードＩＤとアドレスを対応付けたデータである。キーテーブル２３は、「キー」と「値」の組みを示すデータである。
【００２９】
ノードテーブル管理部１１は、データ管理システムに新たなノード装置１が参加した場合や、データ管理システムに参加していたノード装置１が離脱した場合に、記憶部１５に記憶されているノードテーブル２１を更新する。ノードＩＤ生成部１３は、ノード装置１のアドレスと仮想ノードの数に基づいてノードＩＤを生成する。管理範囲長演算部１４は、キー検索用ノードテーブル２２に設定されているノードＩＤに基づいて各ノード装置１が管理するキーの範囲の広さである管理範囲長を算出する。
【００３０】
仮想ノード登録部１２は、管理範囲長演算部１４が算出した管理範囲長が最も狭いノード装置１に対して仮想ノードを生成し、記憶部１５に記憶されているキー検索用ノードテーブル２２を更新する処理を、各ノード装置１の管理範囲長の差異が所定以下になるか、仮想ノード数が上限に達するまで繰り返す。仮想ノード登録部１２が備えるメモリ１２１は、各ノード装置１の管理範囲長の差異が所定以下であると判断するための条件である管理範囲しきい値Ｔｈと、仮想ノード数の上限を示す最大仮想ノード数Ｖｍａｘを記憶する。管理範囲しきい値Ｔｈは、最も狭い管理範囲長と最も広い管理範囲長の比についてのしきい値である。キーテーブル処理部１６は、記憶部１５に保存されているキーテーブル２３を参照して、キーに対応した値を読み出す。
【００３１】
[１．４  データ構成]
図３は、本実施形態によるノードテーブル２１のデータ構成例を示す図である。
同図に示すように、ノードテーブル２１は、データ管理システムを構成するノード装置１のノードＩＤとノードアドレスと対応付けたデータのリストである。ノードテーブル２１は、ノードＩＤの数値順にソートされている。ノードテーブル２１のノードＩＤには、仮想ノードのノードＩＤは含まれない。本実施形態では、ノード装置１のＩＰ（Internet Protocol）アドレスとポート番号の組み合わせをノードアドレスとして用いる。
【００３２】
図４は、本実施形態によるキー検索用ノードテーブル２２のデータ構成例を示す図である。
同図に示すように、キー検索用ノードテーブル２２は、オーバーレイネットワークを構成するノードのノードＩＤ、ノードアドレス、及び、仮想ノード数を対応付けたデータのリストである。キー検索用ノードテーブル２２は、ノードＩＤの数値順にソートされている。キー検索用ノードテーブル２２のノードＩＤには、ノード装置１のノードＩＤに加え、仮想ノードのノードＩＤも含まれる。ＤＨＴを用いたKey-Value型データ管理システムである本実施形態のデータ管理システムは、キー管理を行うノードの発見にこのキー検索用ノードテーブル２２を用いる。すなわち、キー検索用ノードテーブル２２がＤＨＴにおける円状のオーバーレイネットワークを示している。ノードアドレスは、ノード装置１を特定するノード特定情報として用いることができる。
【００３３】
図５は、本実施形態によるキーテーブル２３のデータ構成例を示す図である。
同図に示すように、キーテーブル２３は、データ管理システムで管理するキーと値との組み合わせを対応付けたデータのリストである。本実施形態では、キーがデータを特定するデータＩＤであり、値がデータを記憶しているノード装置１のノードアドレスである場合を例に説明する。
【００３４】
[１．５  負荷分散装置の動作]
次に、負荷分散装置１０の動作について説明する。
まず、ＤＨＴを用いたKey-Value型データ管理システムにおける参加及び離脱の通知手順の一例について説明する。ノード装置１がオーバーレイネットワークに参加する場合、当該ノード装置１内の負荷分散装置１０は、既にオーバーレイネットワークに参加しているいずれかのノード装置１内の負荷分散装置１０に対して参加を要求する。参加の要求を受信した負荷分散装置１０は、ノードの参加をスライス・リーダー（Slice Leader）へ通知し、スライス・リーダーは他のスライス・リーダーへ通知を行い、さらに、スライス・リーダーから自領域内のユニット・リーダー（Unit Leader）への通知を行なう。このように、ノードの参加情報をオーバーレイネットワーク内の全ノードに通知する。なお、負荷分散装置１０は、ノードテーブル２１に登録されているノードＩＤに基づいてスライス・リーダー、ユニット・リーダーなどの通知先を決定する。
【００３５】
また、負荷分散装置１０がノード装置１の離脱を検出した場合、参加の通知の場合と同様に、ノードの離脱をスライス・リーダーへ通知し、スライス・リーダーは他のスライス・リーダーへ通知を行い、さらに、スライス・リーダーから自領域内のユニット・リーダーへの通知を行なう。負荷分散装置１０は、オーバーレイネットワークから離脱した他のノード装置１内の負荷分散装置１０から離脱の通知を受けるか、定期的に他のノード装置１に送信する生存確認信号に対する応答を受信しないことによって離脱を検出する。なお、生存確認信号は、ノードテーブル２１に登録されているノードアドレスを宛先として送信される。
【００３６】
なお、上述した参加・離脱の通知手順は、ＤＨＴを用いたオーバーレイネットワークの構成方法の一つであるOne Hoopの例であり、ＤＨＴを用いたKey-Value型データ管理システムの他の既存の技術により、全ノード装置１に参加や離脱を通知することができる。
【００３７】
[１．５．１  ノードテーブル管理部の動作]
図６は、本実施形態によるノードテーブル管理部１１のノードテーブル更新処理フローを示す図である。
ノードテーブル管理部１１は、他の負荷分散装置１０からノードの参加の通知あるいは離脱の通知を受信する。参加の通知には、「参加」を示す通知種別、及び、参加したノード装置１のノードアドレスが含まれる。また、離脱の通知には、「離脱」を示す通知種別、及び、離脱したノード装置１のノードアドレスが含まれる。ノードテーブル管理部１１は、参加の通知または離脱の通知に含まれるノードアドレスと、仮想ノード数「０」とをノードＩＤ生成部１３に出力し、ノードＩＤの生成を指示する。ノードＩＤ生成部１３はノードアドレスと仮想ノード数の組み合わせからノードＩＤを生成し、ノードテーブル管理部１１に通知する（ステップＳ１１）。
【００３８】
続いて、ノードテーブル管理部１１は、通知種別が「参加」であると判断した場合（ステップＳ１２：ＹＥＳ）、記憶部１５に記憶されているノードテーブル２１に、ステップＳ１１において管理範囲長演算部１４から受信したノードＩＤと、参加の通知に設定されているノードアドレスとを対応付けたデータを追加する（ステップＳ１３）。
【００３９】
一方、ノードテーブル管理部１１は、通知種別が「離脱」であると判断した場合（ステップＳ１２：ＮＯ）、記憶部１５に記憶されているノードテーブル２１から、ステップＳ１１において管理範囲長演算部１４から受信したノードＩＤと、当該ノードＩＤに対応付けられたノードアドレスの組のデータを削除する（ステップＳ１４）。
【００４０】
ステップＳ１３またはステップＳ１４の処理の後、ノードテーブル管理部１１は、仮想ノード登録部１２に実行指示を出力し、更新後のノードテーブル２１に基づくキー検索用ノードテーブルの生成を指示する（ステップＳ１５）。
【００４１】
なお、ノードテーブル管理部１１は、ノードテーブル２１に登録されているノードアドレスを宛先として定期的に他の負荷分散装置１０に生存確認信号を送信し、応答がなかった場合、その宛先のノードアドレスが設定されたノードの離脱の通知を受信したものとして、上記処理を行なう。
また、ノードテーブル管理部１１は、離脱の通知を受信した場合、ステップＳ１１の処理を行なわず、ステップＳ１３において、離脱の通知に設定されているノードアドレスと、当該ノードアドレスに対応付けられたノードＩＤの組のデータを削除してもよい。
【００４２】
以上の動作により、ＤＨＴを用いたKey-Value型データ管理システムに参加しているノードを記録したノードテーブル２１が維持される。
【００４３】
[１．５．２  仮想ノード登録部の動作]
図７は、本実施形態による仮想ノード登録部１２のキー検索用ノードテーブル更新処理フローを示す図である。このキー検索用ノードテーブル更新処理により、仮想ノード登録部１２は、ノードテーブル２１からキー検索用ノードテーブル２２を生成する。仮想ノード登録部１２のメモリ１２１には、図示しない入力手段などにより設定された管理範囲しきい値Ｔｈと、最大仮想ノード数Ｖｍａｘが予め記憶される。
【００４４】
仮想ノード登録部１２は、図６のステップＳ１５においてノードテーブル管理部１１が出力したキー検索用ノードテーブル生成の実行指示を受信する。仮想ノード登録部１２は、記憶部１５に現在記憶されているキー検索用ノードテーブル２２の内容を削除し、ノードテーブル２１の現在の設定内容をキー検索用ノードテーブル２２へコピーする（ステップＳ２１）。このとき、仮想ノード登録部１２は、キー検索用ノードテーブル２２にコピーした各データのノードＩＤ及びノードアドレスの組に対応させて、仮想ノード数のフィールドに「０」を設定する。
【００４５】
続いて、仮想ノード登録部１２は、生成済みの仮想ノード数のカウンタとして利用するパラメータＮに「０」をセットする（ステップＳ２２）。仮想ノード登録部１２は、パラメータＮがメモリ１２１に記憶されている最大仮想ノード数Ｖｍａｘより小さいか否かを判断する（ステップＳ２３）。仮想ノード登録部１２は、パラメータＮが最大仮想ノード数Ｖｍａｘより小さいと判断した場合（ステップＳ２３：ＮＯ）、ＤＨＴを用いたKey-Value型データ管理システムに参加しているノード装置１の管理範囲長のうち、最も大きい管理範囲長である最大管理範囲長Ｌｍａｘと、最も小さい管理範囲長である最小管理範囲長Ｌｍｉｎを出力するよう管理範囲長演算部１４に指示する（ステップＳ２４）。管理範囲長演算部１４は、キー検索用ノードテーブル２２を参照し、最大管理範囲長Ｌｍａｘ、及び、最小管理範囲長Ｌｍｉｎと、最小管理範囲長Ｌｍｉｎのノード装置１（以下、「最小管理範囲長ノード装置」と記載する。）のノードアドレスと、最小管理範囲長ノード装置の仮想ノード数を返送する。
【００４６】
仮想ノード登録部１２は、最大管理範囲長Ｌｍａｘ／最小管理範囲長Ｌｍｉｎが管理範囲しきい値Ｔｈより大きいか否かを判断する（ステップＳ２５）。仮想ノード登録部１２は、最大管理範囲長Ｌｍａｘ／最小管理範囲長Ｌｍｉｎが管理範囲しきい値Ｔｈより大きいと判断した場合（ステップＳ２５：ＹＥＳ）、現時点で管理範囲長が最小である最小管理範囲長ノード装置に仮想ノードを１つ追加する（ステップＳ２６）。具体的には、以下のように動作する。
【００４７】
仮想ノード登録部１２は、ステップＳ２４において受信した仮想ノード数に１を加算して、追加対象の仮想ノード数を算出する。仮想ノード登録部１２は、最小管理範囲長ノード装置のノードアドレスと、追加対象の仮想ノード数とを管理範囲長演算部１４に出力し、ノードＩＤの生成を指示する。管理範囲長演算部１４はノードアドレスと仮想ノード数の組み合わせからノードＩＤを生成し、仮想ノード登録部１２に通知する。仮想ノード登録部１２は、管理範囲長演算部１４から受信した仮想ノードのノードＩＤ、最小管理範囲長ノード装置のノードアドレス、及び、追加対象の仮想ノード数を対応付けたデータを、キー検索用ノードテーブル２２に追加する。
【００４８】
仮想ノードの追加後、仮想ノード登録部１２は、現在のパラメータＮの値に１を加算し（ステップＳ２７）、ステップＳ２３からの処理を繰り返す。
そして、最終的に、ステップＳ２３において、仮想ノード数の合計が最大仮想ノード数Ｖｍａｘに達し、パラメータＮが最大仮想ノード数Ｖｍａｘ以上であると判断した場合（ステップＳ２３：ＹＥＳ）、あるいは、ステップＳ２５において、最大管理範囲長Ｌｍａｘ／最小管理範囲長Ｌｍｉｎが管理範囲しきい値Ｔｈ以下であると判断した場合（ステップＳ２５：ＮＯ）、仮想ノード登録部１２は、処理を終了する。
【００４９】
以上のように、本実施形態では、キーの管理範囲長が最小のノード装置１に対して仮想ノードを追加する処理を繰り返す。これにより、効率的に管理範囲長の不均衡を是正し、各ノード装置１のキーの管理範囲長が同程度になるように仮想ノード数を決定することができる。
なお、管理しきい値Ｔｈが１に近いほど、各ノード装置１において管理されるキーの数が均等に近くなるが、その反面、仮想ノード数が増え、結果としてキー検索用ノードテーブル２２のサイズが増加してしまう。そのため、実験等の結果に基づいて、キー検索用ノードテーブル２２のサイズが大きくなりすぎない範囲で管理しきい値Ｔｈを決定する。また、最大仮想ノード数Ｖｍａｘが大きいほど、キー検索用ノードテーブル２２のサイズが大きくなる可能性がある。そのため、最大仮想ノード数Ｖｍａｘは、記憶部１５として使用されるメモリの容量に基づいて決定される。
【００５０】
本実施形態では、ステップＳ２５において、最大管理範囲長Ｌｍａｘ／最小管理範囲長Ｌｍｉｎと管理範囲のしきい値Ｔｈとを比較し、処理が終了したかを判定しているが、これに限定されるものではない。例えば、最大管理範囲長Ｌｍａｘと所定のしきい値を比較してもよく、最小管理範囲長Ｌｍｉｎと所定のしきい値を比較してもよい。あるいは、キー検索用ノードテーブル２２に登録されている全てのノード装置１及び仮想ノードの管理範囲長の標準偏差や分散と所定のしきい値を比較してもよい。
【００５１】
[１．５．３  ノードＩＤ生成部の動作]
次に、本実施形態によるノードＩＤ生成部１３のノードＩＤ生成処理を説明する。
ノードテーブル管理部１１または仮想ノード登録部１２からノードアドレス及び仮想ノード数を受信すると、ノードＩＤ生成部１３は、ノードアドレスと仮想ノード数とを結合したデータにハッシュ関数を用いてノードＩＤを生成する。仮想ノード数は０からはじまる整数である。本実施形態では、ハッシュ関数としてＳＨＡ−１（Secure Hash Algorithm 1）を用いる。従って、ノードＩＤ生成部１３は、ノードＩＤとして１６０ビットの値を生成する。例えば、ノードアドレスが「192.168.100.10:3939」であり、仮想ノード数が「3」である場合、ノードＩＤ生成部１３は、ノードアドレスと仮想ノード数を結合したデータ「192.168.100.10:3939_3」を生成する。ＳＨＡ-１のハッシュ関数をHash()とすると、ノードＩＤ生成部１３は、Hash(“192.168.100.10:3939_3”)によりノードＩＤを算出する。ノードＩＤ生成部１３は、ノードアドレス及び仮想ノード数の出力元であるノードテーブル管理部１１または仮想ノード登録部１２に、算出したノードＩＤを返送する。
【００５２】
[１．５．４  管理範囲長演算部の動作]
次に、本実施形態による管理範囲長演算部１４の管理範囲長算出処理を説明する。管理範囲長演算部１４は、管理範囲長算出処理において、オーバーレイネットワークに参加している各ノードのハッシュ空間上での管理範囲長を計算する。
【００５３】
図８は、管理範囲長演算部１４の管理範囲長算出処理を説明するための図である。上述したように、本実施形態では１６０ビット長のノードＩＤを利用しているが、説明を簡単にするため、同図においては、ノードＩＤを８ビット長として説明する。ノードＩＤが８ビット長であるため、ノードＩＤは０以上かつ２５５以下の範囲の整数値となる。
【００５４】
図８（ａ）は、オーバーレイネットワークを示す図であり、図８（ｂ）は、図８（ａ）に示すオーバーレイネットワークが形成されているときのキー検索用ノードテーブル２２を示す。図８（ａ）及び図８（ｂ）に示す例においては、３つのノード装置１がオーバーレイネットワークに参加している状態を示しており、これらの３つのノード装置１を大文字のＡ，Ｂ，Ｃを用いてそれぞれノードＡ、ノードＢ、ノードＥとする。また、ノードＡ、ノードＢ、ノードＥそれぞれの仮想ノードを、小文字のａ、ｂ、ｃを用いてノードａ、ノードｂ、ノードｅとする。
以下、ノードＩＤ＝ｉのノードｘをノードｘ[ｉ]と記載する。
【００５５】
図８（ｃ）は、各ノード装置１の管理範囲長を示す図である。各ノードのキーの管理範囲は、時計回りに反対方向の隣接ノードであるpredecessorとの距離である。例えば、ノードＥ[９０]のpredecessorは、ノードｂ[７０]である。従って、ノードＥ単独のキー管理範囲は「７１〜９０」であり、管理範囲長は「２０」となる。また、ノードＥには、ノードｅ[６０]、ノードｅ[１９０]の２つの仮想ノードがある。ノードｅ[１９０]のpredecessorは、ノードａ[１６０]であるため、キー管理範囲は「１６１〜１９０」であり、管理範囲長は「３０」となる。また、ノードｅ[６０]のpredecessorは、ノードａ[１０]であるため、キー管理範囲は「１１〜６０」であり、管理範囲長は「５０」となる。よって、ノードＥ全体の管理範囲長は、２０＋３０＋５０＝１００である。
【００５６】
同様にして、ノードＡ全体の管理範囲長は、ノードＡ[１０]単独のキー管理範囲「２４１〜２５５、０〜１０」の管理範囲長「２６」と、ノードａ[１６０]単独のキー管理範囲「１４１〜１６０」の管理範囲長「２０」を合計した「４６」となる。
また、ノードＢ全体の管理範囲長は、ノードＢ[１４０]単独のキー管理範囲「９１〜１４０」の管理範囲長「５０」と、ノードｂ[２４０]単独のキー管理範囲「１９１〜２４０」の管理範囲長「５０」と、ノードｂ[７０]単独のキー管理範囲「６１〜７０」の管理範囲長「１０」を合計した「１１０」である。
【００５７】
このように、各ノード装置１の合計の管理範囲長は、当該ノード装置１のノード単独の管理範囲長と、当該ノード装置１について生成された各仮想ノード単独の管理範囲長の合計となる。結果として、管理範囲長演算部１４は、最大管理範囲長ＬｍａｘとしてノードＢの管理範囲長「１１０」を、最小管理範囲長ＬｍｉｎとしてノードＡの管理範囲長「４６」を出力する。
【００５８】
上記の動作を行うため、管理範囲長演算部１４は、キー検索用ノードテーブル２２を参照し、全ノード装置１の管理範囲長を計算する。具体的には、以下のように動作する。
管理範囲長演算部１４は、キー検索用ノードテーブル２２に設定されているノードＩＤに順に注目していき、注目しているノードＩＤと、注目しているノードＩＤよりも小さい隣接するノードＩＤとの差から、注目しているノードＩＤ単独の管理範囲長を求める。
【００５９】
キー検索用ノードテーブル２２に注目しているノードＩＤよりも小さい隣接するノードＩＤが設定されていない場合、その注目しているノードＩＤは、オーバーレイネットワークに参加している中で最も小さいノードＩＤである。従って、predecessorのノードＩＤは、キー検索用ノードテーブル２２に登録されている中でも最も大きいノードＩＤである。管理範囲長演算部１４は、注目しているノードＩＤ（例えば、図８（ｂ）に示すノードＩＤ＝１０）に、ノードＩＤが取りうる最大の値（ノードＩＤが8ビット長である場合「２５５」）を加算した後、predecessorのノードＩＤ（図８（ｂ）に示すノードＩＤ＝２４０）を減算することによって管理範囲長を算出する。
【００６０】
管理範囲長演算部１４は、キー検索用ノードテーブル２２に登録されている各ノードＩＤについて管理範囲長を算出した後、キー検索用ノードテーブル２２に同じノードアドレスが対応付けられているノードＩＤについて算出した管理範囲長を合計する。これによって、各ノード装置１の管理範囲長が算出される。管理範囲長演算部１４は、算出した管理範囲長のうち最大である最大管理範囲長Ｌｍａｘ、最小である最小管理範囲長Ｌｍｉｎを選択する。管理範囲長演算部１４は、最小管理範囲長Ｌｍｉｎに対応したノードアドレスと対応付けてキー検索用ノードテーブル２２に設定されている仮想ノード数の中から、最も大きい仮想ノード数を読み出す。管理範囲長演算部１４は、最大管理範囲長Ｌｍａｘ、最小管理範囲長Ｌｍｉｎ、最小管理範囲長ノード装置のノードアドレス、読み出した仮想ノード数を仮想ノード登録部１２に返送する。
【００６１】
[１．５．５  キーテーブル処理部の動作]
続いて、キーテーブル処理部の動作例について説明する。
いずれかのノード装置１がデータ記憶部３０に新たなデータを記憶すると、キーテーブル処理部１６は、この新たなデータのデータ名からＳＨＡ−１ハッシュ関数によりデータＩＤを生成する。キーテーブル処理部１６は、データ記憶部３０に保存されているキー検索用ノードテーブル２２から、生成したデータＩＤに時計回りに近いノードＩＤを検索し、そのノードＩＤに対応したノードアドレスを取得する。キーテーブル処理部１６は、取得したノードアドレスを宛先として、データＩＤと自ノード装置１のノードアドレスを設定したキー登録要求を送信する。キー登録要求を受信したノード装置１において、負荷分散装置１０のキーテーブル処理部１６は、キー登録要求内のデータＩＤとノードアドレスの組をデータ記憶部３０に記憶しているキーテーブル２３に追加する。
【００６２】
いずれかのノード装置１がデータにアクセスする場合、負荷分散装置１０のキーテーブル処理部１６は、そのデータのデータ名からＩＤを生成する。キーテーブル処理部１６は、データ記憶部３０に保存されているキー検索用ノードテーブル２２から、生成したデータＩＤに時計回りに近いノードＩＤを検索し、そのノードＩＤに対応したノードアドレスを取得する。キーテーブル処理部１６は、取得したノードアドレスを宛先として、データＩＤをキーとして設定した問合せを送信する。問合せを受信したノード装置１において、負荷分散装置１０のキーテーブル処理部１６は、データ記憶部３０に記憶されているキーテーブル２３から、問合せに設定されているキーに対応した値を読み出して返送する。この値は、データを記憶しているノード装置１のノードアドレスを示す。問合せ送信元のノード装置１は、受信した「値」により示されるノードアドレス宛先として、データを記憶しているノード装置１にアクセスし、アクセス先のノード装置１が備えるデータ記憶部３０に記憶されている操作対象のデータの読み出し、書替え、削除などを行なう。
【００６３】
上記においては、キーがデータを特定するデータＩＤであり、値がデータを記憶しているノード装置１のノードアドレスである場合の例を説明したが、ＤＨＴを用いたKey-Value型データ管理システムの既存の技術を用い、他のキーとデータの組を分散して管理することもできる。
【００６４】
[１．６  性能]
図９は、本実施形態による負荷分散装置１０を使った実験結果を示す。図９（ａ）は、データ管理システムに参加しているノード装置１の数と、全ノード装置１の管理範囲長の標準偏差との関連を示し、図９（ｂ）は、データ管理システムに参加しているノード装置１の数と、キー検索用ノードテーブルのサイズとの関係を示す。
実験では、管理範囲しきい値Ｔｈ=１．５、最大仮想ノード数Ｖｍａｘ=１００００とし、ノード装置１の数を３〜１０００の範囲とした。なお、比較として、全ノード装置それぞれに０、１０、１００個の固定数の仮想ノードを割り当てる方式を用いた場合における全ノード装置の管理範囲長の標準偏差と、キー検索用ノードテーブルのサイズを示している。
【００６５】
図９（ａ）に示す管理範囲長の標準偏差の結果から、本実施形態では、データ管理システムに参加している各ノード装置１の負荷分散を行なう場合に、１００個の固定数の仮想ノードを割り当てる方式と同等の性能が得られることがわかる。一方、図９（ｂ）に示すの結果から、本実施形態の負荷分散装置１０を用いたときのキー検索用ノードテーブル２２のサイズは、各ノード装置に１０個の固定数の仮想ノードを割り当てる方式において用いられるキー検索用ノードテーブルのサイズと同程度であることがわかる。
これらの実験結果から、本実施形態によれば、各ノード装置に固定数１００の仮想ノードを割り当てるの場合と同程度の性能を、１０分の１のサイズのキー検索用ノードテーブルによりで実現できることがわかる。
【００６６】
[２．  第２の実施形態]
上述した第１の実施形態において、管理範囲長演算部１４は、キー検索用ノードテーブル２２に登録されている全てのノードの管理範囲長を求めた後、各ノード装置１が管理しているキーの管理範囲長を算出しているが、算出方法はこれに限定されるものではない。本実施形態では、各ノードが管理しているキーの管理範囲長を高速に算出する。
以下では、第１の実施形態との差分を説明する。
【００６７】
図１０は、本実施形態による管理範囲長演算部１４の処理を説明するための図である。
図１０（ａ）は、図７のステップＳ２６の処理によって、図８（ａ）に示すオーバーレイネットワークにノードＡの仮想ノードであるノードａ[２３０]が追加された場合の例を示している。また、図１０（ｂ）は、ノードａ[２３０]の追加後の各ノード装置１の管理範囲長を示している。
【００６８】
図１０（ａ）に示すノードａ[２３０]の追加により、ノードＡの管理範囲長には、追加されたノードａ[２３０]とそのpredecessorのノードｅ[１９０]との距離である「４０」が追加される。一方、追加されたノードａ[２３０]のsuccessor（時計回り方向の隣接ノード）のノードｂ[２４０]の管理範囲長は「４０」だけ短くなる。この例では、追加されたノードａ[２３０]のsuccessorであるノードｂ[２４０]は、ノードＢの仮想ノードであるので、ノードＢの管理範囲長を「４０」だけ短くする。
結果として、図１０（ｂ）に示すように、管理範囲長の演算は、ノードＡの管理範囲長に「４０」を加算し、ノードＢの管理範囲長から「４０」を減算するだけで求めることが可能である。
【００６９】
以上の動作を行うため、管理範囲長演算部１４は、図７のステップＳ２４において各ノードアドレスについて算出した管理範囲長を記憶部１５に書き込む。そして、ステップＳ２６において仮想ノードが追加され、次のループでステップＳ２４を実行する際、仮想ノード登録部１２からステップＳ２６において追加された仮想ノードのノードＩＤを受信する。追加されたノードＩＤを追加ノードＩＤと記載する。
【００７０】
管理範囲長演算部１４は、キー検索用ノードテーブル２２から追加ノードＩＤよりも小さい隣接するノードＩＤとの差から、追加された仮想ノードの管理範囲長を求めるとともに、追加ノードＩＤに対応したノードアドレスを読み出す。管理範囲長演算部１４は、読み出したノードアドレスに対応して記憶部１５に記憶されている管理範囲長を、追加された仮想ノードの管理範囲長を加算した値に更新する。
【００７１】
さらに、管理範囲長演算部１４は、キー検索用ノードテーブル２２から追加ノードＩＤよりも大きい隣接するノードＩＤを特定し、特定したノードＩＤに対応したノードアドレスを読み出す。管理範囲長演算部１４は、読み出したノードアドレスに対応して記憶部１５に記憶されている管理範囲長を、追加された仮想ノードの管理範囲長を減算した値に更新する。
【００７２】
上記処理の後、管理範囲長演算部１４は、仮想ノード追加後の各ノード装置１のアドレスに対応した管理範囲長を記憶部１５から読み出す。
【００７３】
[３．  第３の実施形態]
第３の実施形態には、各ノード装置１のノード性能が異なる場合に適用する。つまり、ＤＨＴに参加する各ノード装置１の性能が同一ではない場合、それらのノード性能に応じて各負荷分散装置１０が管理及び保管する（キー、値）のデータ量を制御する。以下、第１の実施形態及び第２の実施形態との差分を説明する。
【００７４】
[３．１  データ構成]
図１１は、本実施形態のノードテーブル２１のデータ構成例を示す図である。同図に示すノードテーブル２１が、図３に示すノードテーブル２１と異なる点は、ノードＩＤ及びノードアドレスに対応付けて、ノード性能値が設定される点である。ノード性能値は、ノードの性能を示す指標についての定量的な値であり、例えば、ＣＰＵ（central processing unit）の性能を示す値や、ノードが保管できる総ディスク容量などがある。
【００７５】
図１２は、本実施形態のキー検索用ノードテーブル２２のデータ構成例を示す図である。同図に示すキー検索用ノードテーブル２２が、図４に示すキー検索用ノードテーブル２２と異なる点は、ノードＩＤ、ノードアドレス、及び、仮想ノード数に対応付けて、ノード性能値が設定される点である。
【００７６】
[３．２  負荷分散装置の動作]
次に、負荷分散装置１０の動作について説明する。
【００７７】
[３．２．１  ノードテーブル管理部の動作]
図６のステップＳ１１において、ノードテーブル管理部１１が受信するノードの参加の通知には、通知種別「参加」、参加したノード装置１のノードアドレス、及び、参加したノード装置１の性能値が含まれる。ステップＳ１３において、ノードテーブル管理部１１は、記憶部１５に記憶されているノードテーブル２１に、ステップＳ１１において管理範囲長演算部１４から受信したノードＩＤと、参加の通知に含まれるノードアドレス及びノード性能値とを対応付けたデータを新たに追加する。また、ステップＳ１４において、ノードテーブル管理部１１は、記憶部１５に記憶されているノードテーブル２１から、ステップＳ１１においてノードＩＤ生成部１３から受信したノードＩＤと、当該ノードＩＤに対応付けられたノードアドレス及び性能値の組のデータを削除する。
【００７８】
[３．２．２  仮想ノード登録部の動作]
図７のステップＳ２１において、仮想ノード登録部１２が、ノードテーブル２１の設定内容をキー検索用ノードテーブル２２にコピーする際、ノードＩＤ、ノードアドレス及び性能値の組がそのままコピーされる。また、ステップＳ２６において、仮想ノード登録部１２は、仮想ノードのノードＩＤ、最小管理範囲長ノード装置のノードアドレス及び性能値に、追加対象の仮想ノード数を対応付けたデータを、キー検索用ノードテーブル２２に追加する。
【００７９】
[３．２．３  管理範囲長演算部の動作]
本実施形態による管理範囲長演算部１４は、上述した第１の実施形態、または、第２の実施形態のように算出した各ノード装置１の管理範囲長に、当該ノード装置１の性能値に応じて重み付けを行う。
【００８０】
管理範囲長演算部１４は、第１の実施形態または第２の実施形態と同様に、各ノード装置１のノードアドレス毎に管理範囲長を算出する。管理範囲長演算部１４は、各ノードアドレスに対応付けてノードテーブル２１またはキー検索用ノードテーブル２２に設定されている性能値を読み出すと、ノードアドレス毎に算出した管理範囲長を、そのノードアドレスについて読み出した性能値によって除算する。管理範囲長演算部１４は、除算した結果の管理範囲長の中で最大の管理範囲長を最大管理範囲長Ｌｍａｘ、最小の管理範囲長を最小管理範囲長Ｌｍｉｎとして選択する。管理範囲長演算部１４は、最小管理範囲長Ｌｍｉｎに対応したノードアドレスと対応付けてキー検索用ノードテーブル２２に設定されている仮想ノード数の中から、最も大きい仮想ノード数を読み出す。管理範囲長演算部１４は、最大管理範囲長Ｌｍａｘ、最小管理範囲長Ｌｍｉｎ、最小管理範囲長ノード装置のノードアドレス、読み出した仮想ノード数をノードテーブル管理部１１に返送する。
【００８１】
図１３は、ノード性能を考慮した場合の管理範囲長演算を説明するための図である。オーバーレイネットワークは、図８（ａ）と同様に構成されており、ノードＡ、ノードＢ、ノードＣについて第１の実施形態と同様の処理により算出された管理範囲長はそれぞれ「４６」、「１１０」、「１００」である。また、ノードＡ、ノードＢ、ノードＣのノード性能値はそれぞれ「１」、「２」、「３」である。この場合、ノードＡの管理範囲長は、ノードＡの管理範囲長「４６」を、ノードＡのノード性能値「１」によって除算した値「４６」となる。また、ノードＢの管理範囲長は、ノードＢの管理範囲長「１１０」をノードＢのノード性能値「２」によって除算した値「５５」となる。また、ノードＥの管理範囲長は、ノードＥの管理範囲長「１００」をノードＥのノード性能値「３」によって除算した値「３３」となる。従って、最大管理範囲長Ｌｍａｘは、ノードＢの管理範囲長「５５」となり、最小管理範囲長Ｌｍｉｎは、ノードＥの最小管理範囲長ノード装置の管理範囲長となる。
この結果、性能が高いノードＥの仮想ノードを増加させることになる。
【００８２】
[４．  本発明の実施形態の効果]
以上説明したように、本発明の実施形態によれば、ＤＨＴを用いたKey-Value型データ管理システムを構成するノード装置に実装される負荷分散装置は、システムを構成しているノード装置の参加や離脱が発生した際、各ノード装置の管理範囲長が同等に近くなるまで、管理範囲長が最も狭いノード装置へ仮想ノードの割り当てを行う処理を繰り返し、ノード装置のアドレスと当該ノード装置に対して生成された仮想ノードのノードＩＤとからなるキー検索用ノードテーブルを生成する。よって、従来技術と比較して各ノード装置のキーの管理範囲長の不均衡を効率的に是正し、仮想ノードの数を抑えることが可能となるため、キー検索用ノードテーブルの増加が少ない。
また、各ノード装置を均等に負荷分散したり、各ノード装置のノード性能に応じて負荷分散したりすることが可能となる。
【００８３】
［５．  その他］
なお、上述した実施形態では、各負荷分散装置１０においてノードテーブル２１及びキー検索用ノードテーブル２２を生成しているが、一部の負荷分散装置１０においてノードテーブル２１及びキー検索用ノードテーブル２２を生成し、他の負荷分散装置１０に配信してもよい。
【００８４】
上述した負荷分散装置１０を実装するノード装置１は、内部にコンピュータシステムを有している。そして、負荷分散装置１０の動作の過程は、プログラムの形式でコンピュータ読み取り可能な記録媒体に記憶されており、このプログラムをコンピュータシステムが読み出して実行することによって、上記処理が行われる。ここでいうコンピュータシステムとは、ＣＰＵ及び各種メモリやＯＳ、周辺機器等のハードウェアを含むものである。
【００８５】
また、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶部のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間、動的にプログラムを保持するもの、その場合のサーバーやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含むものとする。また上記プログラムは、前述した機能の一部を実現するためのものであっても良く、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであっても良い。
【００８６】
以上、この発明の実施形態について図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【符号の説明】
【００８７】
１…ノード装置
１０…負荷分散装置
１１…ノードテーブル管理部
１２…仮想ノード登録部
１２１…メモリ
１３…ノードＩＤ生成部
１４…管理範囲長演算部
１５…記憶部
１６…キーテーブル処理部
２１…ノードテーブル
２２…キー検索用ノードテーブル
２３…キーテーブル
３０…記憶部
５…通信ネットワーク
【図１】
0005600573.tif 000002
【図２】
0005600573.tif 000003
【図３】
0005600573.tif 000004
【図４】
0005600573.tif 000005
【図５】
0005600573.tif 000006
【図６】
0005600573.tif 000007
【図７】
0005600573.tif 000008
【図８】
0005600573.tif 000009
【図９】
0005600573.tif 000010
【図１０】
0005600573.tif 000011
【図１１】
0005600573.tif 000012
【図１２】
0005600573.tif 000013
【図１３】
0005600573.tif 000014