分散データベースの制御方法
【課題】データの挿入処理や検索処理のアクセス時に送受されるトラヒック量を抑制し、常に正当が検索結果を得られる分散データベースの制御方法を提供する。
【解決手段】制御ノード１から受信したメッセージを各ストレージノードNへマルチキャストで転送する中継ノード２を備え、各ストレージノードは、自ノードのマルチキャストグループアドレスを中継ノード２へ予め登録し、制御ノード１は、メッセージの宛先となるストレージノードのマルチキャストグループアドレスを識別して、このマルチキャストグループアドレス宛にメッセージを送信し、中継ノード２は、メッセージを受信して前記マルチキャストグループアドレスと対応付けられている複数のストレージノードを識別して前記メッセージを転送する。
【解決手段】制御ノード１から受信したメッセージを各ストレージノードNへマルチキャストで転送する中継ノード２を備え、各ストレージノードは、自ノードのマルチキャストグループアドレスを中継ノード２へ予め登録し、制御ノード１は、メッセージの宛先となるストレージノードのマルチキャストグループアドレスを識別して、このマルチキャストグループアドレス宛にメッセージを送信し、中継ノード２は、メッセージを受信して前記マルチキャストグループアドレスと対応付けられている複数のストレージノードを識別して前記メッセージを転送する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散データベースの制御方法に係り、特に、データ転送にIPマルチキャストを採用する分散データベースの制御方法に関する。
【背景技術】
【０００２】
検索対象のデータをテーブル形式で保存する従来のRDB (Relational Data Base) に対して、KVS (Key Value Store) と呼ばれるデータベースが提案されている。KVSは、キー(KEY)と値(VALUE)とのペア形式でデータが各ノードに保持され、多くの場合、データは分散データベースの形式で管理される。このようなKVSは、シンプルなデータ構造であるが故に拡張性／可用性が高く、運用コストが低いという利点がある。KVSの主なものとしては、Amazon社がウェブストレージシステムとして採用するDynamoがある（非特許文献１，２）。
【０００３】
図６は、従来のKVSの構成を示したブロック図であり、ここで、KVSは一般的なConsistent Hashing（非特許文献３）を利用しているもとする。KVSは、多数のデータを分散保持する複数のストレージノードNと、各ストレージノードNへのデータの挿入/検索/削除を管理する制御ノードとから構成される。このような制御ノードは複数台存在しても良いし、ストレージノードNと物理的に同一であっても良いが、ここでは、１台の制御ノードがストレージノードとは別に独立して設けられている場合を例にして説明する。
【０００４】
各ストレージノードNiには、予め固有のノードIDiが割り当てられており、ノードIDの値域は0≦ID≦ID_MAXであって整数値をとるものとする。各ストレージノードNは、ノードID順かつID＝0のストレージノードN0とID＝ID_MAXのストレージノードNmaxとが連結される環状に配置されていると考える。ここでは、あるストレージノードNiから見て時計回り方向に隣接するストレージノードNi+1を後ノード、反時計回り方向に隣接するストレージノードNi-1を前ノードと表現する。また、各ストレージノードNならびに制御ノードは、他の全てのストレージノードNのIDと通信に必要な情報(IPアドレス)を知っているものとする。
【０００５】
各ストレージノードNに分散配置されるデータは、キー(KEY)と値(VALUE)とのペアで構成され、キーの値をノードIDの値域にマッピングするハッシュ関数HASH(KEY)が定義されている。各データは、KEYの値をHASH関数で変換した値(ハッシュ値)で一意に定義される前記IDの円上の位置に配置されている。
【０００６】
各ストレージノードNiは、自ノードよりも１つ前のストレージノードNi-1から自ノードNiまでの間に配置されたデータを保持する。ただし、ストレージノードNiが故障などの理由で動作しなくなった場合にデータが紛失してしまう事を防ぐため、前後の各ストレージノードNi+1，Ni-1にデータのコピーが保持される。すなわち、各ストレージノードNiは、実質的に２つ前のノードのID-2から１つ後ろのノードのIDi+1までのデータを保持することになる。
【０００７】
次いで、図６を参照してデータ挿入時の処理手順について説明する。なお、削除処理は空の値を持つデータを挿入する事と等価なので、ここでは説明を省略する。
【０００８】
(1)制御ノードは、KEYのハッシュ値HASH(KEY)を算出し、データを保持するべきストレージノードNiにアクセスしてデータの挿入メッセージを送信する。挿入メッセージを受信したストレージノードNiは、当該メッセージに記述されているデータを保持する。
【０００９】
(2)ストレージノードNiまたは制御ノードは、ストレージノードNiの前後の各ストレージノードNi-1，Ni+1へデータのコピーメッセージを送信する。コピーメッセージを受信した各ストレージノードNi-1，Ni+1は、当該コピーメッセージに記述されているデータを保持する。
【００１０】
次いで、図７を参照してデータ検索時の処理手順について説明する。
【００１１】
(1)制御ノードは、検索要求されたKEYのハッシュ値HASH(KEY)を算出することでデータを保持しているストレージノードNiを識別し、当該ストレージノードNiおよびその前後の各ストレージノードNi-1，Ni+1へ検索要求メッセージを送信する。
【００１２】
(2)検索要求メッセージを受信した各ストレージノードNi，Ni-1，Ni+1は自ノードのストレージを検索し、前記KEYと対応付けられているVALUEの記述された検索応答メッセージを制御ノードへ返信する。
【００１３】
(3)制御ノードは、各ストレージノードNi，Ni-1，Ni+1から検索結果を受信し、同一の検索結果が２つ以上返信されると、それを検索結果として処理する。
【先行技術文献】
【非特許文献】
【００１４】
【非特許文献１】http://www.allthingsdistributed.com/2007/10/amazons_dynamo.html
【非特許文献２】"NoSQLの世界"，電子情報処理学会会誌, Vol. 51, No. 10, pp.1327-1331.
【非特許文献３】D. Karger他 "Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web" 29th annual ACM Symposium on Theory of Computing.
【発明の概要】
【発明が解決しようとする課題】
【００１５】
従来のKVSには、ストレージノードの障害などに対応するため、同一データを複数のノードにコピーして保持する複製処理が実装されているが、この複製処理が全てユニキャストで行われ、制御ノードから各ストレージノードNへメッセージが別々に送信されるので、メッセージ数が増加によりトラヒック量が増えてしまう。
【００１６】
また、データの複製処理が挿入処理の後で行われ、各処理に時差が生じるので、図８に一例を示したような不都合が生じ得る。
【００１７】
すなわち、時刻t1において制御ノードがストレージノードNiへアクセスして挿入要求メッセージを送信すると、ストレージノードNiは、受信データを自ノードのストレージに保持した後、時刻t2，t3において、コピー用の挿入要求メッセージをストレージノードNi+1，Ni-1へそれぞれ転送する。各ストレージノードNi+1，Ni-1は、ストレージノードNiから転送されたデータを自ノードのストレージにそれぞれ保持する。
【００１８】
その後、制御ノードにおいて、「KEY」に対応付ける値を「VALUE1」から「VALUE2」に変更する更新要求が検知されると、時刻t4では、制御ノードからストレージノードNiへ更新用の挿入要求メッセージが送信される。
【００１９】
しかしながら、隣接する各ストレージノードNi+1，Ni-1へ前記コピー用の挿入要求メッセージが転送（時刻t11t，12）されるよりも前に、時刻t5，t6，t7において、制御ノードから各ストレージノードNi，Ni+1，Ni-1へ検索要求メッセージが送信されてしまうと、ストレージノードNiは、時刻t8において、更新後の検索結果(KEY，VALUE2)を応答できるものの、ストレージノードNi+1，Ni-1は、時刻t9，t10において、それぞれ更新前の検索結果(KEY，VALUE1)を応答することになる。その結果、制御ノードでは更新前のデータ(KEY，VALUE1)が検索結果として処理されてしまう。
【００２０】
本発明の目的は、上記した従来技術の課題を全て解決し、データの挿入処理や検索処理の際に送受されるメッセージのトラヒック量を抑制し、常に正当な検索結果を得られる分散データベースの制御方法を提供することにある。
【課題を解決するための手段】
【００２１】
上記の目的を達成するために、本発明は、複数のストレージノードにノードIDと対応付けられたデータが分散保持され、各ストレージノードは、制御ノードから受信したメッセージに応答してデータを処理する分散データベースの制御方法において、制御ノードから受信したメッセージを各ストレージノードへマルチキャストで転送する中継ノードを備え、各ストレージノードが、自ノードおよび他の一部のノードの各マルチキャストグループアドレスを中継ノードへ通知して同一のマルチキャストグループへ参加する手順と、制御ノードが、メッセージの宛先となるストレージノードのマルチキャストグループアドレスを識別する手順と、制御ノードが、前記マルチキャストグループアドレス宛にメッセージを送信する手順と、中継ノードが、前記メッセージを受信して前記マルチキャストグループアドレスに対応するグループに参加しているストレージノードを識別する手順と、中継ノードが、前記識別されたストレージノードへ前記メッセージを転送する手順とを有することを特徴とする。
【発明の効果】
【００２２】
本発明によれば、以下のような効果が達成される。
【００２３】
(1)中継ノードは、一のストレージノード宛のメッセージを受信すると、当該一のストレージノードアドレスと同一のマルチキャストグループへ参加している他のストレージノードへも当該メッセージをマルチキャストアドレスで同位に送信するので、複数のストレージノードへ同一メッセージを少ないトラヒック量で同時に転送できるようになる。
【００２４】
(2)同一のマルチキャストグループへ参加している複数のストレージノードへはメッセージが同時に送信され、各ストレージノードに保持されているデータが同時に更新されるので、挿入処理の直後に検索処理が要求された場合でも、常に正当な検索結果を提供できるようになる。
【図面の簡単な説明】
【００２５】
【図１】KVSのネットワークにおける本発明の挿入処理を模式的に表現した図である。
【図２】KVSのネットワークにおける本発明の検索処理を模式的に表現した図である。
【図３】本発明を適用した挿入処理および検索処理のシーケンスフローである。
【図４】マルチキャストグループアドレスの生成方法を示した図である。
【図５】マルチキャストグループアドレスが衝突する例を示した図である。
【図６】従来のKVSのネットワークにおける挿入処理を模式的に表現した図である。
【図７】従来のKVSのネットワークにおける検索処理を模式的に表現した図である。
【図８】従来技術の課題を説明するためのシーケンスフローである。
【発明を実施するための形態】
【００２６】
以下、図面を参照して本発明の実施の形態について詳細に説明する。図１，２は、本発明が適用されるKVSのネットワーク構成を模式的に表現した図であり、多数のデータを分散保持する複数のストレージノードNと、各ストレージノードNへのデータの挿入/検索/削除を管理する制御ノード１と、制御ノード１から受信したメッセージをIPマルチキャストで各ストレージノードNへ転送する中継ノード２からと構成され、本実施形態では、前記中継ノード２としてIPマルチキャストルータが用いられている。
【００２７】
前記制御ノード１は複数台存在しても良いし、ストレージノードNと物理的に同一であっても良いが、ここでは、１台の制御ノード１がストレージノードNとは別に独立して設けられている場合を例にして説明する。
【００２８】
各ストレージノードNには、予め固有のIDが割り当てられており、IDの値域は0≦ID≦ID_MAXであって整数値をとるものとする。各ストレージノードNは、ID順かつID＝0のストレージノードN0とID＝ID_MAXのストレージノードNmaxとが連結されて環状に配置されていると考える。ここでは、あるストレージノードNiから見て時計回り方向に隣接するストレージノードNi+1を後ノード、反時計回り方向に隣接するストレージノードNi-1を前ノードと表現する。また、各ストレージノードN、制御ノード１および中継ノード２は、他の全てのストレージノードNとの通信に必要な情報(IPアドレス)を知っているものとする
【００２９】
[JOIN処理]
図３のタイムチャートを参照し、各ストレージノードNiは、自ノードに割り当てられているノードIDiから生成されるマルチキャストグループアドレスGroup(IDi)、および前後に隣接する２つのストレージノードNi+1，Ni-1に割り当てられるノードIDi+1，IDi-1から生成される２つのマルチキャストグループアドレスGroup(IDi+1)，Group(IDi-1)への参加（JOIN）を、時刻t21において中継ノード２へ通知する。
【００３０】
同様に、時刻t22ではストレージノードNi+1が、自ノードおよび各隣接ノードの３つのマルチキャストグループアドレスGroup(IDi)，Group(IDi+1)，Group(IDi+2)へのJOINを中継ノード２へ通知し、時刻t23ではストレージノードNi-1が、自ノードおよび各隣接ノードの３つのマルチキャストグループアドレスGroup(IDi-2)，Group(IDi-1)，Group(IDi)へのJOINを中継ノード２へ通知する。
【００３１】
図４は、本実施形態におけるマルチキャストグループアドレスGroup(ID)の生成方法を示した図であり、３２ビットのGroup(ID)の下位２４ビットには、ノードIDの上位２４ビットが採用され、上位８ビットには、マルチキャストグループアドレスに固有の固定値(ここでは、"２３９（１０進数）")が採用される。
【００３２】
[挿入処理]
図１，３を参照し、制御ノード１においてデータの挿入要求が検知されると、そのKEYのハッシュ値に基づいて、当該データが挿入されるストレージノードNiのIDiが一意に特定される。次いで、前記IDiに基づいてマルチキャストグループアドレスGroup(IDi)が上記と同様に生成され、時刻t24において、当該マルチキャストグループアドレスGroup(IDi)に対して、前記挿入メッセージ(KEY，VALUE1)がIPマルチキャストパケットで送信される。
【００３３】
前記挿入メッセージを受信した中継ノード２は、そのマルチキャストグループアドレスGroup(IDi)にJOINしているグループのストレージノードN（図３ではNi，Ni+1、Ni-1）を識別し、時刻t25において、各ストレージノードNへ前記挿入メッセージを転送する。
【００３４】
各ストレージノードNは、受信メッセージに記述されている挿入データを自ノードが保持すべきか否かを判定し、保持すべきデータと判定されれば自ノードのストレージに保持する。これにより、前記挿入データはストレージノードNiに保持されると同時に、隣接する２つのノードNi-1，Ni+1にもバックアップされることになる。
【００３５】
[検索処理]
図２，３を参照し、制御ノード１においてデータの検索要求が検知されると、そのKEYのハッシュ値に基づいて、検索対象のデータを保持するストレージノードNiのIDiが一意に特定される。次いで、前記IDiに基づいてマルチキャストグループアドレスGroup(IDi)が算出され、時刻t26において、当該マルチキャストグループアドレスGroup(IDi)に対して、前記検索メッセージ(KEY)がIPマルチキャストパケットで送信される。
【００３６】
前記メッセージを受信した中継ノード２は、そのマルチキャストグループアドレスGroup(IDi)にJOINしているグループのストレージノードN（図３ではNi，Ni+1、Ni-1）を識別し、時刻t27において、各ストレージノードNへ前記検索メッセージを転送する。
【００３７】
前記検索メッセージを受信した各ストレージノードNは、自ノードのストレージを前記検索キーで検索し、時刻t28，t29，t30において、検索結果の値をそれぞれ制御ノード１へ応答する。制御ノード１は、検索結果のうち同じ結果が２つ以上あれば、その値を検索結果として処理する。
【００３８】
ところで、上記のように各ストレージノードNiが、自ノードに割り当てられているノードIDiから生成されるマルチキャストグループアドレスGroup(IDi)、および前後に隣接する２つのストレージノードNi+1，Ni-1に割り当てられるノードIDi+1，IDi-1から生成される２つのマルチキャストグループアドレスGroup(IDi+1)，Group(IDi-1)へJOINすると、複数の異なるストレージノードNに同一のマルチキャストグループアドレスが割り当てられてしまう「衝突」が生じ得る。これは、マルチキャストグループアドレスの値域がノードIDの値域よりも狭いことに起因する。
【００３９】
図５は、マルチキャストグループアドレスが衝突する例を示した図であり、ストレージノードNi-1，Ni+2およびNi+3には、それぞれのノードID(IDi-1，IDi+2およびIDi+3)の上位ビットを利用して生成された固有のマルチキャストグループアドレスGroup(IDi-1)＝Gj-1、Group(IDi+2)＝Gj+1、Group(IDi+3)＝Gj+2が割り当てられている。
【００４０】
これに対して、ストレージノードNiおよびNi+1は、それぞれのノードID(IDiおよびIDi+1)の上位ビットを利用して生成されたマルチキャストグループアドレスが同値Group(IDi)＝Group(IDi+1)となるために共通のグループアドレスGjが割り当てられている。
【００４１】
したがって、例えばデータの挿入処理において、そのKEYのハッシュ値に基づいてストレージノードNiのIDiが一意に特定され、当該IDiから生成されたマルチキャストグループアドレスGroup(IDi)＝Gjに対して挿入メッセージがIPマルチキャストパケットで送信されると、前記データは４つのストレージノードNi-1，Ni，Ni+1およびNi+2に保持されることになる。
【００４２】
このため、マルチキャストグループアドレスの衝突時であっても、本実施形態では、ノードIDの上位ビットがマルチキャストグループアドレスの下位ビットであり、衝突するグループアドレス同士は必ずID空間で隣接することが保障されているので、マルチキャストグループアドレスの衝突処理が不要である。
【符号の説明】
【００４３】
１…制御ノード
２…中継ノード
【技術分野】
【０００１】
本発明は、分散データベースの制御方法に係り、特に、データ転送にIPマルチキャストを採用する分散データベースの制御方法に関する。
【背景技術】
【０００２】
検索対象のデータをテーブル形式で保存する従来のRDB (Relational Data Base) に対して、KVS (Key Value Store) と呼ばれるデータベースが提案されている。KVSは、キー(KEY)と値(VALUE)とのペア形式でデータが各ノードに保持され、多くの場合、データは分散データベースの形式で管理される。このようなKVSは、シンプルなデータ構造であるが故に拡張性／可用性が高く、運用コストが低いという利点がある。KVSの主なものとしては、Amazon社がウェブストレージシステムとして採用するDynamoがある（非特許文献１，２）。
【０００３】
図６は、従来のKVSの構成を示したブロック図であり、ここで、KVSは一般的なConsistent Hashing（非特許文献３）を利用しているもとする。KVSは、多数のデータを分散保持する複数のストレージノードNと、各ストレージノードNへのデータの挿入/検索/削除を管理する制御ノードとから構成される。このような制御ノードは複数台存在しても良いし、ストレージノードNと物理的に同一であっても良いが、ここでは、１台の制御ノードがストレージノードとは別に独立して設けられている場合を例にして説明する。
【０００４】
各ストレージノードNiには、予め固有のノードIDiが割り当てられており、ノードIDの値域は0≦ID≦ID_MAXであって整数値をとるものとする。各ストレージノードNは、ノードID順かつID＝0のストレージノードN0とID＝ID_MAXのストレージノードNmaxとが連結される環状に配置されていると考える。ここでは、あるストレージノードNiから見て時計回り方向に隣接するストレージノードNi+1を後ノード、反時計回り方向に隣接するストレージノードNi-1を前ノードと表現する。また、各ストレージノードNならびに制御ノードは、他の全てのストレージノードNのIDと通信に必要な情報(IPアドレス)を知っているものとする。
【０００５】
各ストレージノードNに分散配置されるデータは、キー(KEY)と値(VALUE)とのペアで構成され、キーの値をノードIDの値域にマッピングするハッシュ関数HASH(KEY)が定義されている。各データは、KEYの値をHASH関数で変換した値(ハッシュ値)で一意に定義される前記IDの円上の位置に配置されている。
【０００６】
各ストレージノードNiは、自ノードよりも１つ前のストレージノードNi-1から自ノードNiまでの間に配置されたデータを保持する。ただし、ストレージノードNiが故障などの理由で動作しなくなった場合にデータが紛失してしまう事を防ぐため、前後の各ストレージノードNi+1，Ni-1にデータのコピーが保持される。すなわち、各ストレージノードNiは、実質的に２つ前のノードのID-2から１つ後ろのノードのIDi+1までのデータを保持することになる。
【０００７】
次いで、図６を参照してデータ挿入時の処理手順について説明する。なお、削除処理は空の値を持つデータを挿入する事と等価なので、ここでは説明を省略する。
【０００８】
(1)制御ノードは、KEYのハッシュ値HASH(KEY)を算出し、データを保持するべきストレージノードNiにアクセスしてデータの挿入メッセージを送信する。挿入メッセージを受信したストレージノードNiは、当該メッセージに記述されているデータを保持する。
【０００９】
(2)ストレージノードNiまたは制御ノードは、ストレージノードNiの前後の各ストレージノードNi-1，Ni+1へデータのコピーメッセージを送信する。コピーメッセージを受信した各ストレージノードNi-1，Ni+1は、当該コピーメッセージに記述されているデータを保持する。
【００１０】
次いで、図７を参照してデータ検索時の処理手順について説明する。
【００１１】
(1)制御ノードは、検索要求されたKEYのハッシュ値HASH(KEY)を算出することでデータを保持しているストレージノードNiを識別し、当該ストレージノードNiおよびその前後の各ストレージノードNi-1，Ni+1へ検索要求メッセージを送信する。
【００１２】
(2)検索要求メッセージを受信した各ストレージノードNi，Ni-1，Ni+1は自ノードのストレージを検索し、前記KEYと対応付けられているVALUEの記述された検索応答メッセージを制御ノードへ返信する。
【００１３】
(3)制御ノードは、各ストレージノードNi，Ni-1，Ni+1から検索結果を受信し、同一の検索結果が２つ以上返信されると、それを検索結果として処理する。
【先行技術文献】
【非特許文献】
【００１４】
【非特許文献１】http://www.allthingsdistributed.com/2007/10/amazons_dynamo.html
【非特許文献２】"NoSQLの世界"，電子情報処理学会会誌, Vol. 51, No. 10, pp.1327-1331.
【非特許文献３】D. Karger他 "Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web" 29th annual ACM Symposium on Theory of Computing.
【発明の概要】
【発明が解決しようとする課題】
【００１５】
従来のKVSには、ストレージノードの障害などに対応するため、同一データを複数のノードにコピーして保持する複製処理が実装されているが、この複製処理が全てユニキャストで行われ、制御ノードから各ストレージノードNへメッセージが別々に送信されるので、メッセージ数が増加によりトラヒック量が増えてしまう。
【００１６】
また、データの複製処理が挿入処理の後で行われ、各処理に時差が生じるので、図８に一例を示したような不都合が生じ得る。
【００１７】
すなわち、時刻t1において制御ノードがストレージノードNiへアクセスして挿入要求メッセージを送信すると、ストレージノードNiは、受信データを自ノードのストレージに保持した後、時刻t2，t3において、コピー用の挿入要求メッセージをストレージノードNi+1，Ni-1へそれぞれ転送する。各ストレージノードNi+1，Ni-1は、ストレージノードNiから転送されたデータを自ノードのストレージにそれぞれ保持する。
【００１８】
その後、制御ノードにおいて、「KEY」に対応付ける値を「VALUE1」から「VALUE2」に変更する更新要求が検知されると、時刻t4では、制御ノードからストレージノードNiへ更新用の挿入要求メッセージが送信される。
【００１９】
しかしながら、隣接する各ストレージノードNi+1，Ni-1へ前記コピー用の挿入要求メッセージが転送（時刻t11t，12）されるよりも前に、時刻t5，t6，t7において、制御ノードから各ストレージノードNi，Ni+1，Ni-1へ検索要求メッセージが送信されてしまうと、ストレージノードNiは、時刻t8において、更新後の検索結果(KEY，VALUE2)を応答できるものの、ストレージノードNi+1，Ni-1は、時刻t9，t10において、それぞれ更新前の検索結果(KEY，VALUE1)を応答することになる。その結果、制御ノードでは更新前のデータ(KEY，VALUE1)が検索結果として処理されてしまう。
【００２０】
本発明の目的は、上記した従来技術の課題を全て解決し、データの挿入処理や検索処理の際に送受されるメッセージのトラヒック量を抑制し、常に正当な検索結果を得られる分散データベースの制御方法を提供することにある。
【課題を解決するための手段】
【００２１】
上記の目的を達成するために、本発明は、複数のストレージノードにノードIDと対応付けられたデータが分散保持され、各ストレージノードは、制御ノードから受信したメッセージに応答してデータを処理する分散データベースの制御方法において、制御ノードから受信したメッセージを各ストレージノードへマルチキャストで転送する中継ノードを備え、各ストレージノードが、自ノードおよび他の一部のノードの各マルチキャストグループアドレスを中継ノードへ通知して同一のマルチキャストグループへ参加する手順と、制御ノードが、メッセージの宛先となるストレージノードのマルチキャストグループアドレスを識別する手順と、制御ノードが、前記マルチキャストグループアドレス宛にメッセージを送信する手順と、中継ノードが、前記メッセージを受信して前記マルチキャストグループアドレスに対応するグループに参加しているストレージノードを識別する手順と、中継ノードが、前記識別されたストレージノードへ前記メッセージを転送する手順とを有することを特徴とする。
【発明の効果】
【００２２】
本発明によれば、以下のような効果が達成される。
【００２３】
(1)中継ノードは、一のストレージノード宛のメッセージを受信すると、当該一のストレージノードアドレスと同一のマルチキャストグループへ参加している他のストレージノードへも当該メッセージをマルチキャストアドレスで同位に送信するので、複数のストレージノードへ同一メッセージを少ないトラヒック量で同時に転送できるようになる。
【００２４】
(2)同一のマルチキャストグループへ参加している複数のストレージノードへはメッセージが同時に送信され、各ストレージノードに保持されているデータが同時に更新されるので、挿入処理の直後に検索処理が要求された場合でも、常に正当な検索結果を提供できるようになる。
【図面の簡単な説明】
【００２５】
【図１】KVSのネットワークにおける本発明の挿入処理を模式的に表現した図である。
【図２】KVSのネットワークにおける本発明の検索処理を模式的に表現した図である。
【図３】本発明を適用した挿入処理および検索処理のシーケンスフローである。
【図４】マルチキャストグループアドレスの生成方法を示した図である。
【図５】マルチキャストグループアドレスが衝突する例を示した図である。
【図６】従来のKVSのネットワークにおける挿入処理を模式的に表現した図である。
【図７】従来のKVSのネットワークにおける検索処理を模式的に表現した図である。
【図８】従来技術の課題を説明するためのシーケンスフローである。
【発明を実施するための形態】
【００２６】
以下、図面を参照して本発明の実施の形態について詳細に説明する。図１，２は、本発明が適用されるKVSのネットワーク構成を模式的に表現した図であり、多数のデータを分散保持する複数のストレージノードNと、各ストレージノードNへのデータの挿入/検索/削除を管理する制御ノード１と、制御ノード１から受信したメッセージをIPマルチキャストで各ストレージノードNへ転送する中継ノード２からと構成され、本実施形態では、前記中継ノード２としてIPマルチキャストルータが用いられている。
【００２７】
前記制御ノード１は複数台存在しても良いし、ストレージノードNと物理的に同一であっても良いが、ここでは、１台の制御ノード１がストレージノードNとは別に独立して設けられている場合を例にして説明する。
【００２８】
各ストレージノードNには、予め固有のIDが割り当てられており、IDの値域は0≦ID≦ID_MAXであって整数値をとるものとする。各ストレージノードNは、ID順かつID＝0のストレージノードN0とID＝ID_MAXのストレージノードNmaxとが連結されて環状に配置されていると考える。ここでは、あるストレージノードNiから見て時計回り方向に隣接するストレージノードNi+1を後ノード、反時計回り方向に隣接するストレージノードNi-1を前ノードと表現する。また、各ストレージノードN、制御ノード１および中継ノード２は、他の全てのストレージノードNとの通信に必要な情報(IPアドレス)を知っているものとする
【００２９】
[JOIN処理]
図３のタイムチャートを参照し、各ストレージノードNiは、自ノードに割り当てられているノードIDiから生成されるマルチキャストグループアドレスGroup(IDi)、および前後に隣接する２つのストレージノードNi+1，Ni-1に割り当てられるノードIDi+1，IDi-1から生成される２つのマルチキャストグループアドレスGroup(IDi+1)，Group(IDi-1)への参加（JOIN）を、時刻t21において中継ノード２へ通知する。
【００３０】
同様に、時刻t22ではストレージノードNi+1が、自ノードおよび各隣接ノードの３つのマルチキャストグループアドレスGroup(IDi)，Group(IDi+1)，Group(IDi+2)へのJOINを中継ノード２へ通知し、時刻t23ではストレージノードNi-1が、自ノードおよび各隣接ノードの３つのマルチキャストグループアドレスGroup(IDi-2)，Group(IDi-1)，Group(IDi)へのJOINを中継ノード２へ通知する。
【００３１】
図４は、本実施形態におけるマルチキャストグループアドレスGroup(ID)の生成方法を示した図であり、３２ビットのGroup(ID)の下位２４ビットには、ノードIDの上位２４ビットが採用され、上位８ビットには、マルチキャストグループアドレスに固有の固定値(ここでは、"２３９（１０進数）")が採用される。
【００３２】
[挿入処理]
図１，３を参照し、制御ノード１においてデータの挿入要求が検知されると、そのKEYのハッシュ値に基づいて、当該データが挿入されるストレージノードNiのIDiが一意に特定される。次いで、前記IDiに基づいてマルチキャストグループアドレスGroup(IDi)が上記と同様に生成され、時刻t24において、当該マルチキャストグループアドレスGroup(IDi)に対して、前記挿入メッセージ(KEY，VALUE1)がIPマルチキャストパケットで送信される。
【００３３】
前記挿入メッセージを受信した中継ノード２は、そのマルチキャストグループアドレスGroup(IDi)にJOINしているグループのストレージノードN（図３ではNi，Ni+1、Ni-1）を識別し、時刻t25において、各ストレージノードNへ前記挿入メッセージを転送する。
【００３４】
各ストレージノードNは、受信メッセージに記述されている挿入データを自ノードが保持すべきか否かを判定し、保持すべきデータと判定されれば自ノードのストレージに保持する。これにより、前記挿入データはストレージノードNiに保持されると同時に、隣接する２つのノードNi-1，Ni+1にもバックアップされることになる。
【００３５】
[検索処理]
図２，３を参照し、制御ノード１においてデータの検索要求が検知されると、そのKEYのハッシュ値に基づいて、検索対象のデータを保持するストレージノードNiのIDiが一意に特定される。次いで、前記IDiに基づいてマルチキャストグループアドレスGroup(IDi)が算出され、時刻t26において、当該マルチキャストグループアドレスGroup(IDi)に対して、前記検索メッセージ(KEY)がIPマルチキャストパケットで送信される。
【００３６】
前記メッセージを受信した中継ノード２は、そのマルチキャストグループアドレスGroup(IDi)にJOINしているグループのストレージノードN（図３ではNi，Ni+1、Ni-1）を識別し、時刻t27において、各ストレージノードNへ前記検索メッセージを転送する。
【００３７】
前記検索メッセージを受信した各ストレージノードNは、自ノードのストレージを前記検索キーで検索し、時刻t28，t29，t30において、検索結果の値をそれぞれ制御ノード１へ応答する。制御ノード１は、検索結果のうち同じ結果が２つ以上あれば、その値を検索結果として処理する。
【００３８】
ところで、上記のように各ストレージノードNiが、自ノードに割り当てられているノードIDiから生成されるマルチキャストグループアドレスGroup(IDi)、および前後に隣接する２つのストレージノードNi+1，Ni-1に割り当てられるノードIDi+1，IDi-1から生成される２つのマルチキャストグループアドレスGroup(IDi+1)，Group(IDi-1)へJOINすると、複数の異なるストレージノードNに同一のマルチキャストグループアドレスが割り当てられてしまう「衝突」が生じ得る。これは、マルチキャストグループアドレスの値域がノードIDの値域よりも狭いことに起因する。
【００３９】
図５は、マルチキャストグループアドレスが衝突する例を示した図であり、ストレージノードNi-1，Ni+2およびNi+3には、それぞれのノードID(IDi-1，IDi+2およびIDi+3)の上位ビットを利用して生成された固有のマルチキャストグループアドレスGroup(IDi-1)＝Gj-1、Group(IDi+2)＝Gj+1、Group(IDi+3)＝Gj+2が割り当てられている。
【００４０】
これに対して、ストレージノードNiおよびNi+1は、それぞれのノードID(IDiおよびIDi+1)の上位ビットを利用して生成されたマルチキャストグループアドレスが同値Group(IDi)＝Group(IDi+1)となるために共通のグループアドレスGjが割り当てられている。
【００４１】
したがって、例えばデータの挿入処理において、そのKEYのハッシュ値に基づいてストレージノードNiのIDiが一意に特定され、当該IDiから生成されたマルチキャストグループアドレスGroup(IDi)＝Gjに対して挿入メッセージがIPマルチキャストパケットで送信されると、前記データは４つのストレージノードNi-1，Ni，Ni+1およびNi+2に保持されることになる。
【００４２】
このため、マルチキャストグループアドレスの衝突時であっても、本実施形態では、ノードIDの上位ビットがマルチキャストグループアドレスの下位ビットであり、衝突するグループアドレス同士は必ずID空間で隣接することが保障されているので、マルチキャストグループアドレスの衝突処理が不要である。
【符号の説明】
【００４３】
１…制御ノード
２…中継ノード
【特許請求の範囲】
【請求項１】
複数のストレージノードにノードIDと対応付けられたデータが分散保持され、各ストレージノードは、制御ノードから受信したメッセージに応答してデータを処理する分散データベースの制御方法において、
制御ノードから受信したメッセージを各ストレージノードへマルチキャストで転送する中継ノードを備え、
各ストレージノードが、自ノードおよび他の一部のノードの各マルチキャストグループアドレスを中継ノードへ通知して同一のマルチキャストグループへ参加する手順と、
制御ノードが、メッセージの宛先となるストレージノードのマルチキャストグループアドレスを識別する手順と、
制御ノードが、前記マルチキャストグループアドレス宛にメッセージを送信する手順と、
中継ノードが、前記メッセージを受信して前記マルチキャストグループアドレスに対応するグループに参加しているストレージノードを識別する手順と、
中継ノードが、前記識別されたストレージノードへ前記メッセージを転送する手順とを有することを特徴とする分散データベースの制御方法。
【請求項２】
前記各ストレージノードは、自ノードのノードIDの上位のビット列に基づいて自ノードのマルチキャストグループアドレスを生成することを特徴とする請求項１に記載の分散データベースの制御方法。
【請求項３】
前記各ストレージノードに保持されるデータが、KEYとVARUEとのペアであることを特徴とする請求項１または２に記載の分散データベースの制御方法。
【請求項４】
前記中継ノードが、IPマルチキャストルータであることを特徴とする請求項１ないし３のいずれかに記載の分散データベースの制御方法。
【請求項５】
前記制御ノードから中継ノードへ送信されるメッセージが、各ストレージにデータを保持させる挿入メッセージであることを特徴とする請求項１ないし４のいずれかに記載の分散データベースの制御方法。
【請求項６】
前記制御ノードから中継ノードへ送信されるメッセージが、各ストレージに保持されているデータから検索キーに対応したデータを検索させる検索要求メッセージであることを特徴とする請求項１ないし４のいずれかに記載の分散データベースの制御方法。
【請求項１】
複数のストレージノードにノードIDと対応付けられたデータが分散保持され、各ストレージノードは、制御ノードから受信したメッセージに応答してデータを処理する分散データベースの制御方法において、
制御ノードから受信したメッセージを各ストレージノードへマルチキャストで転送する中継ノードを備え、
各ストレージノードが、自ノードおよび他の一部のノードの各マルチキャストグループアドレスを中継ノードへ通知して同一のマルチキャストグループへ参加する手順と、
制御ノードが、メッセージの宛先となるストレージノードのマルチキャストグループアドレスを識別する手順と、
制御ノードが、前記マルチキャストグループアドレス宛にメッセージを送信する手順と、
中継ノードが、前記メッセージを受信して前記マルチキャストグループアドレスに対応するグループに参加しているストレージノードを識別する手順と、
中継ノードが、前記識別されたストレージノードへ前記メッセージを転送する手順とを有することを特徴とする分散データベースの制御方法。
【請求項２】
前記各ストレージノードは、自ノードのノードIDの上位のビット列に基づいて自ノードのマルチキャストグループアドレスを生成することを特徴とする請求項１に記載の分散データベースの制御方法。
【請求項３】
前記各ストレージノードに保持されるデータが、KEYとVARUEとのペアであることを特徴とする請求項１または２に記載の分散データベースの制御方法。
【請求項４】
前記中継ノードが、IPマルチキャストルータであることを特徴とする請求項１ないし３のいずれかに記載の分散データベースの制御方法。
【請求項５】
前記制御ノードから中継ノードへ送信されるメッセージが、各ストレージにデータを保持させる挿入メッセージであることを特徴とする請求項１ないし４のいずれかに記載の分散データベースの制御方法。
【請求項６】
前記制御ノードから中継ノードへ送信されるメッセージが、各ストレージに保持されているデータから検索キーに対応したデータを検索させる検索要求メッセージであることを特徴とする請求項１ないし４のいずれかに記載の分散データベースの制御方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１２−１７４０２０（Ｐ２０１２−１７４０２０Ａ）
【公開日】平成２４年９月１０日（２０１２．９．１０）
【国際特許分類】
【出願番号】特願２０１１−３５８２２（Ｐ２０１１−３５８２２）
【出願日】平成２３年２月２２日（２０１１．２．２２）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
【公開日】平成２４年９月１０日（２０１２．９．１０）
【国際特許分類】
【出願日】平成２３年２月２２日（２０１１．２．２２）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
[ Back to top ]