(57)【要約】【課題】分散システムのノード数が変動しても個々のノードの負荷を均一化することを可能にする識別子割当て方法及びプログラムを提供することである。【解決手段】本発明の一態様は、複数のノード装置が協調して動作する分散システムにおいて、前記ノード装置に識別子を割り当てる識別子割当て方法であって、前記分散システムのノード装置に対する識別子割当てイベントを検出するステップと、前記識別子割当てイベントを検出すると、前記分散システムにおける割当て済みの識別子を格納した識別子一覧表にアクセスするステップと、前記識別子一覧表を参照して、前記識別子一覧表に格納されている隣り合う識別子の間の領域が最大となる隣り合う識別子を決定するステップと、前記決定された隣り合う識別子の間の領域を二等分から乱数分移動させた値で分割し、分割点に対応する識別子を前記ノード装置に割り当てるステップとを有する方法に関する。【選択図】図６
2018036793.tif 000002
【特許請求の範囲】
【請求項１】
複数のノード装置が協調して動作する分散システムにおいて、前記ノード装置に識別子を割り当てる識別子割当て方法であって、
前記分散システムのノード装置に対する識別子割当てイベントを検出するステップと、
前記識別子割当てイベントを検出すると、前記分散システムにおける割当て済みの識別子を格納した識別子一覧表にアクセスするステップと、
前記識別子一覧表を参照して、前記識別子一覧表に格納されている隣り合う識別子の間の領域が最大となる隣り合う識別子を決定するステップと、
前記決定された隣り合う識別子の間の領域を二等分から乱数分移動させた値で分割し、分割点に対応する識別子を前記ノード装置に割り当てるステップと、
を有する方法。
【請求項２】
前記最大となる隣り合う識別子を決定するステップは、
前記最大となる領域が複数検出された場合、前記検出された複数の最大となる領域からランダムソートによって１つ以上の領域を選択することを含む、請求項１記載の方法。
【請求項３】
複数のノード装置が協調して動作する分散システムにおいて、前記ノード装置に識別子を割り当てる識別子割当て方法であって、
前記分散システムのノード装置に対する識別子割当てイベントを検出するステップと、
前記識別子割当てイベントを検出すると、前記分散システムにおける割当て済みの識別子を格納した識別子一覧表にアクセスするステップと、
前記識別子一覧表を参照して、前記識別子一覧表に格納されている隣り合う識別子の間の領域が最大となる隣り合う識別子を決定するステップと、
前記決定された隣り合う識別子の間の領域を二等分する識別子を前記ノード装置に割り当てるステップと、
を有し、
前記最大となる隣り合う識別子を決定するステップは、
前記最大となる領域が複数検出された場合、前記検出された複数の最大となる領域からランダムソートによって１つ以上の領域を選択することを含む方法。
【請求項４】
前記識別子は、前記分散システムにおいて各ノード装置を識別すると同時に、前記分散システムにおける各ノード装置に割り当てられるデータ複製量の決定に用いられる、請求項１乃至３何れか一項記載の方法。
【請求項５】
前記ノード装置に割り当てられた識別子を前記識別子一覧表に格納し、前記識別子一覧表を更新するステップをさらに有する、請求項１乃至４何れか一項記載の方法。
【請求項６】
前記識別子割当てイベントは、前記ノード装置に所定数の識別子を割り当てる複数識別子割当てイベントを含み、
前記識別子割当てイベントが前記複数識別子割当てイベントである場合、前記決定するステップ、前記割り当てるステップ及び前記更新するステップが、前記所定数の回数だけ繰り返される、請求項５記載の方法。
【請求項７】
前記識別子割当てイベントは、前記分散システムへの新たなノード装置の追加を含む、請求項１乃至６何れか一項記載の方法。
【請求項８】
請求項１乃至７何れか一項記載の方法をコンピュータに実行させるためのコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のノードが協調して動作する分散システムに関し、より詳細には、分散システムにおいてノード間の負荷の分散を可能にするノードに対する識別子割当て方法及びプログラムに関する。
【背景技術】
【０００２】
一般に、複数のノードが協調して動作する分散システムでは、分散システム内の個々のノードを認識し識別するための識別子が割り当てられる。一部の分散システムでは、識別子は、単に個々のノードの識別を可能にしさえすればよいという役割しか有していない。その場合、識別子の割当ては、ノード間で同じ値が使われることがないよう、一意な値を割当てるものであればよい。一方で、コンシステント・ハッシング（非特許文献１）のように、識別子の役割が、識別子の値によって個々のノードが担当する処理負荷量等が決定されるなど、個々のノードの識別以上の意味を持つような分散システムも存在する。
【０００３】
このような分散システムにおいて、コンシステント・ハッシング（Consistent  Hashing）などに基づくデータ管理方法が利用されている。コンシステント・ハッシングによると、各ノードを識別するための識別子と、これらのノードにより管理される各データを識別するための識別子とが割り当てられる。あるノードが管理するデータの識別子の範囲は、典型的には、当該ノードの識別子と、当該ノードより小さな値の識別子を有するノードのうち最も大きな値の識別子を有するノードの識別子との間で定められる。そして、これらのノードやデータの識別子をハッシュ関数などを用いて返される無作為な値により割当てることによって、個々のノードが担当するデータの量は確率的に均等になり、このような分散データ管理プログラムによりノード間の負荷を均等にすることが可能となる。
【０００４】
図１は、コンシステント・ハッシングによる識別子の割当ての一例を示す。図１では、識別子の値の小さいものから、円形にノードが並べて示されている。ここで円形に並べているのは、コンシステント・ハッシング等では識別子の最大値の次に最小値が来るためである。この円のことを、コンシステント・ハッシングの用語に倣いＩＤ空間と呼称する。なお、ＩＤ空間上では時計周りに行くほど識別子の値が大きくなるものとする。ここで、ノードの担当する領域とは、そのノードの識別子から反時計周りに別のノードの識別子までの円弧に相当する。この領域の大小に比例して、ノードの担当するデータや処理の負荷量が決まる。図１は、コンシステント・ハッシングにおける最も基本的なノードの識別子の割り当て方法の具体例である。ここではノードは５つまで追加されており、それぞれに無作為な値の識別子が与えられてＩＤ空間上に存在している。識別子の値が無作為に決められているため、ノード間の領域の大きさにもばらつきが見られる。
【０００５】
このように、このコンシステント・ハッシングにおいては、ノードとデータの識別子の割り当ては、ハッシュ関数によって行われる。ハッシュ関数は入力に対して、無作為な出力を返す関数である。ある入力に対しては常に同じ出力を返すことから、完全にランダムな値を返す関数ではなく、元々の入力の持っていた意味等を無視した出力を返すという意味で、無作為な出力を行う関数である。このハッシュ関数に、ノードやデータ毎に決まった一意な値、例えばノードの名前やアドレス、データの名前等を入力することで得られた値を、識別子として利用する。
【０００６】
このような識別子の割り当て方法を用いる場合、個々のノードの担当するデータの識別子の範囲は、高い確率で平均値よりも大きくなる。これはランダウの漸近記法によって記すならば、各ノードの担当する負荷の量が、平均負荷のΘ（ｌｏｇＮ）倍になると記述することができる（Ｎはノードの総数）。これは、ノード数が多いほど平均よりも多くの負荷を担当しなければならないノードが存在することを意味する。コンシステント・ハッシングではこの問題の緩和のために、１つのノードに対し複数の識別子を割り当てることによって、確率的にこの担当する負荷を均一化することを行っている。
【０００７】
このような各ノードに複数の識別子を割り当てるための具体的な手法として、二等分割割当て手法が提案されている（特許文献１）。二等分割割当て手法では、分散システムに計算資源を追加（増設／スケールアウト）する際、追加する計算資源を仮想的に分割し、分割した計算資源（以降、仮想ノードと称する）を、コンシステント・ハッシング空間の割当て済み領域の大きいところを二分割して割り当てる。
【０００８】
図２は、二等分割割当て手法を示す図である。図２では、ノード１つにつき３つの識別子を割り当てる場合に、３つのノードが追加されている状態を表している。各ノードは３つの識別子のそれぞれの担当する３つの領域を束ねただけの領域を担当する形となる。大数の法則により、１つのノードに割り当てる識別子の数を増やすほど、ノード単位での領域は平均化される。二等分割割当て手法によると、ノードＡ，Ｂの２つのノードに加えてノードＣが追加されるとき、ノードＡとノードＢとの間の最大領域から順に３つの領域を選択し、各領域を二等分する中央値を新規ノードＣの識別子として割り当てる。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開2012-48424号公報
【非特許文献】
【００１０】
【非特許文献１】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.
【発明の概要】
【発明が解決しようとする課題】
【００１１】
上述した二等分割割当て手法によると、分散システムを構成する計算資源（物理サーバ、仮想サーバ等）毎の処理負担を可能な限り均等にすることができる。一方、分散システムにおいて、サーバの故障などの障害耐性を高めるため、コンシステント・ハッシング空間において隣接する仮想ノード（例えば、時計回り方向の隣接ノード）のデータを複製する方式がある。
【００１２】
上述した従来技術によると、計算資源毎の領域の大きさはほぼ均等になるが、データの複製が各計算資源に対して均等に配分されることは保証できないなど、依然としてノード間の負荷は均一でない。実際、複製されるデータ量に応じてサーバ毎の処理量に影響が生じるため、メッセージキューのオーバフロー、メモリ／ＣＰＵ使用率のばらつきなど、クラスタ全体の性能劣化を招く可能性がある。
【００１３】
上記問題点に鑑み、本発明の課題は、分散システムのノード数が変動しても個々のノードの負荷を均一化することを可能にする識別子割当て方法及びプログラムを提供することである。
【課題を解決するための手段】
【００１４】
上記課題を解決するため、本発明の一態様は、複数のノード装置が協調して動作する分散システムにおいて、前記ノード装置に識別子を割り当てる識別子割当て方法であって、前記分散システムのノード装置に対する識別子割当てイベントを検出するステップと、前記識別子割当てイベントを検出すると、前記分散システムにおける割当て済みの識別子を格納した識別子一覧表にアクセスするステップと、前記識別子一覧表を参照して、前記識別子一覧表に格納されている隣り合う識別子の間の領域が最大となる隣り合う識別子を決定するステップと、前記決定された隣り合う識別子の間の領域を二等分から乱数分移動させた値で分割し、分割点に対応する識別子を前記ノード装置に割り当てるステップとを有する方法に関する。
【発明の効果】
【００１５】
本発明によると、分散システムの識別子の間隔を均一化することにより、各ノードの担当する処理量や複製データ量を均一化し、ノード間の負担量を均等にすることが可能になる。また、分散システムにおけるノードの追加・削除などの状況に関わらず、ノード間の負担を公平化することができ、システム全体の利用効率を向上させることが可能になる。
【図面の簡単な説明】
【００１６】
【図１】図１は、コンシステント・ハッシングによる識別子の割当ての一例を示す図である。
【図２】図２は、二等分割割当て手法を示す図である。
【図３】図３は、本発明の一実施例による識別子割当て装置の構成を示すブロック図である。
【図４】図４は、本発明の一実施例による識別子割当て装置を備えた分散システムの構成を示すブロック図である。
【図５】図５は、本発明の一実施例による識別子割当て装置を備えた分散システムの他の構成を示すブロック図である。
【図６】図６は、本発明の一実施例による識別子割当て方法の処理を示すフロー図である。
【発明を実施するための形態】
【００１７】
以下、図面に基づいて本発明の実施の形態を説明する。
【００１８】
以下の実施例では、複数のノード装置が協調して動作する分散システムにおいて、各ノード装置に識別子を割り当てる識別子割当て装置及び方法が開示される。後述される実施例を概略すると、識別子割当て装置は、分散システムにノード装置を追加する際、追加するノード装置の計算資源を仮想的に分割し、後述されるように乱数を用いてコンシステント・ハッシング空間の最大となる割当て済み領域を二分割し、分割したノード装置の計算資源を割り当てる。また、最大割当て済み領域が複数存在する場合、ランダムソートを実行することによって何れかの領域を選択する。
【００１９】
まず、本発明の一実施例による識別子割当て装置を説明する。図３は、本発明の一実施例による識別子割当て装置の構成を示すブロック図である。なお、識別子割当て装置１００は、典型的には、補助記憶装置、メモリ装置、ＣＰＵ、通信装置などの各種ハードウェアリソースの１以上から構成される。補助記憶装置は、ハードディスクやフラッシュメモリなどから構成され、後述される各種処理及び機能を実現するプログラムやデータを格納する。メモリ装置は、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）などから構成され、プログラムの起動指示があった場合に、補助記憶装置からプログラムを読み出して格納する。ＣＰＵは、情報を処理するプロセッサとして機能し、メモリ装置に格納されたプログラムに従って後述される各種機能を実現する。通信装置は、ネットワークを介し他の装置と接続するための各種通信回路から構成される。通信装置は、典型的には、各種ネットワークと接続するための通信インタフェースなどを有する。なお、識別子割当て装置１００は、上述したハードウェア構成に限定されるものでなく、ネットワークを介し各ノードと双方向通信するための機能を有する他の何れか適切なハードウェア構成を有してもよい。
【００２０】
図３に示されるように、識別子割当て装置１００は、識別子一覧表格納部１０１と、識別子決定部１１０とを有する。
【００２１】
識別子一覧表格納部１０１は、分散システム内のノードに対してすでに割当てられている識別子を記述した識別子一覧表を格納する。上述したように、本発明による識別子は、個々のノードを特定するだけでなく、識別子の値によって個々のノードが担当する処理負荷の量等が決定されるなど、個々のノードの識別以上の意味を有している。識別子一覧表は、典型的には、分散システム内の既存のノードに割当て済みの識別子を、ノード名やノードが分散システムに接続された順番などに関連付けて格納する。これにより、ノード削除時に、削除対象のノードに割り当てられている識別子を迅速に特定することができる。
【００２２】
識別子決定部１１０は、新たなノードの追加など識別子割当てイベントに応答して、識別子一覧表を参照して、後述される処理により割り当てるべき識別子を決定する。さらに、識別子を決定した後、識別子決定部１１０は、当該識別子を識別子一覧表格納部１０１に通知し、識別子一覧表を更新させる。
【００２３】
識別子決定部１１０は、決定的識別子決定部１１１と、複数識別子割当て部１１２とを有する。決定的識別子決定部１１１は、まず識別子一覧表を参照することで、分散システムの全ノードの識別子を取得し、それらを識別子の大きさの順に並べ、識別子間の距離を計算する。この識別子間の距離は、例えば、図１及び２に示されたＩＤ空間上の距離であり、隣り合う識別子間の距離は、当該識別子間の円弧の長さ、当該識別子と円の中心とにより画成される扇型領域の面積などとして定義されてもよい。なお、本明細書における「隣り合う」、「値の間隔が大きい」、「領域が大きい」などの表現は、このような識別子間の距離の定義に基いた表現である。一般に、距離の定義にはユークリッドノルムや排他論理和等が用いられる。本明細書では特に断りなくユークリッドノルムを距離の定義として用いるが、本発明はこれに限定されるものでなく、排他論理和やあるいはその他の距離の定義を用いてもよい。
【００２４】
決定的識別子決定部１１１は、計算した距離の情報をもとに、識別子間の間隔の大きい順に、分散システムから要求された識別子の個数だけ領域（上述したＩＤ空間では、識別子間の円弧）を選択し、選択された各領域を二等分から乱数分移動させた値で分割し、分割点に対応する識別子をノードに割り当てる。例えば、各領域を二等分する中央値から移動させる乱数は、正規乱数λに従って決定されてもよく、−０．０１≦λ≦０．０１であってもよい。なお、決定的識別子決定部１１１は、当該識別子割当て処理を通じて予め決定された乱数を使用してもよいし、選択された各領域に対して個別に乱数を選択してもよい。
【００２５】
例えば、識別子ＩＤＸからＩＤＸ＋１との間の領域Ｘが最大領域として検出された場合、決定的識別子決定部１１１は、
ＮｅｗＩＤ＝｜ＩＤＸ−ＩＤＸ＋１｜／（２＋λ）
により分割点に対応する識別子を計算し、取得した識別子をノードに割り当てる。なお、上記式による計算結果が整数とならない場合、決定的識別子決定部１１１は、計算結果を切り捨て又は切り上げることによって識別子を決定してもよい。
【００２６】
このようにしてノードに新たな識別子ＮｅｗＩＤが割り当てられると、当該ノードは、反時計回りに関して隣接するノードの識別子ＩＤＸと割り当てられた識別子ＮｅｗＩＤとの間の領域の負荷量に対応してデータ処理を実行し、また、当該隣接ノードに対する複製データを保持する。あるいは、当該ノードは、時計回りに関して隣接するノードの識別子ＩＤＸ＋１と割り当てられた識別子ＮｅｗＩＤとの間の領域の負荷量に対応してデータ処理を実行し、また、当該隣接ノードに対する複製データを保持する。すなわち、当該識別子は、分散システムにおいて各ノードを識別すると同時に、分散システムにおける各ノードに割り当てられるデータ複製量を決定するのに用いられる。
【００２７】
なお、識別子の割り当ての際に識別子の間隔が大きい順に領域を選択するものとしたが、決定的識別子決定部１１１は、最大領域が複数検出された場合、検出された複数の最大領域からランダムソートによって１つ以上の領域を選択してもよい。例えば、３つの最大領域Ｘ，Ｙ，Ｚが検出された場合、決定的識別子決定部１１１は、ランダムに１つの領域を選択する。例えば、Ｘが選択されると、決定的識別子決定部１１１は、領域Ｘについて上述したように分割点に対応する識別子を計算し、取得した識別子をノードに割り当てる。更なる識別子を割り当てるとき、決定的識別子決定部１１１は、残りの領域Ｙ，Ｚからランダムに１つの領域を選択する。例えば、Ｙが選択されると、決定的識別子決定部１１１は、領域Ｙについて上述したように分割点に対応する識別子を計算し、取得した識別子をノードに割り当てる。
【００２８】
なお、ランダムソートを利用する上記実施例は、上述した乱数を用いた領域の二分割と組み合わせて実施されてもよいし、あるいは、単独で実施されてもよい。後者の場合、例えば、ランダムソートにより選択された各領域は二等分されてもよいし、又は、他の何れか適切な分割方式によって二分割されてもよい。
【００２９】
上述した識別子の決定方法により、各ノードの担当する領域が均一化され、各ノードの担当する処理量や複製データ量についても均一化されることになる。すなわち、複数の仮想マシンを用いたり、分散システムのプログラムを複数起動することで、１つの計算機上で複数の仮想ノードが存在するケースを考える。例えば、ＩＤ空間が０〜９９であり、２台の物理マシンＡ，Ｂが用いられ、４つの仮想ノード（＝物理マシン２台×各物理マシン当たりの仮想ノード数２）が既に組み込まれている場合、ＩＤ空間が以下のように分割されていると仮定する。
【００３０】
０〜２４：物理Ａ＃１
２５〜４９：物理Ｂ＃１
５０〜７４：物理Ａ＃２
７５〜９９：物理Ｂ＃２
この空間に対して、新たに１台の物理マシンＣ、すなわち、２つの仮想ノードを追加する際、上述した４つの分割領域から２つを選択する必要がある。ここで、ランダムソートを行わない場合、例えば、ＩＤ空間の若番から順に選択すると、ＩＤ空間は以下の用に分割される。
【００３１】
０〜１２：物理Ａ＃１
１３〜２４：物理Ｃ＃１
２５〜３７：物理Ｂ＃１
３８〜４９：物理Ｃ＃２
５０〜７４：物理Ａ＃２
７５〜９９：物理Ｂ＃２
このように、新たに追加された物理マシンＣに対応する仮想ノードはＩＤ空間の右半分のみに展開されることになる。ここで、データ複製がＩＤ空間の右隣（時計回り方向）の仮想ノードに実施される設定となっているため、ＩＤ空間に物理マシンが一様に分布していないと、データ複製に偏りが生じることになることが理解されるであろう。
【００３２】
なお、コンシステント・ハッシングの仕組みを使って、データの格納位置の決定ではなく分散システムの処理を行う位置を決定する場合がある。本明細書では以下特に断りなく、データの分散の仕組みにおいて本発明による識別子割当て装置を適用することを前提として説明を行うが、分散システムの処理を行う位置を決定する場合にも本発明を適用可能であり、データの格納位置の決定のみに本発明の適用対象を限定するものではない。
【００３３】
複数識別子割当て部１１２は、分散システムから要求された個数だけ、各ノードに対して決定的識別子決定部１１１を繰り返し使用して複数の識別子を割り当てる。具体的には、複数識別子割当て部１１２は、分散システムから要求された識別子の個数に対応して、上述した決定的識別子決定部１１１の処理を複数回実行させ、決定された複数の識別子を当該ノードに割当てる。
【００３４】
なお、識別子割当て装置１００は、図４に示されるように、サーバ・クライアントタイプの分散システムのサーバとして配置されてもよい。すなわち、識別子割当て装置１００は、分散システムの各ノードと接続することで、ノードから識別子割当て要求を受け、これに応答して識別子を割当てるサーバとして機能する。
【００３５】
あるいは、識別子割当て装置１００は、図５に示されるように、分散システムの各ノード内に配置されてもよい。すなわち、識別子割当て装置１００は、分散システムのノード上に、独立した装置又はプログラムもしくは分散システムのプログラムの一部として組み込まれてもよい。
【００３６】
なお、本発明の識別子割当て装置１００は、独立した物理的装置である必要はなく、プロセッサとメモリとを備えた汎用コンピュータに後述される識別子割当て機能及び方法を実行させるためのコンピュータプログラムとして実現されてもよい。この場合、そのプログラムの動作する位置は限定されず、分散システムから識別子割当て要求が受けられ、分散システムのノードの識別子の一覧表を保持し、もしくは参照可能であれば、どのような接続構成であっても動作可能である。
【００３７】
なお、本明細書で記述するノードとは、分散システムの処理の構成要素のことであり、具体的には分散システムを構成する各計算機がノードとして実現される。一方で、複数の仮想マシンを用いたり、分散システムのプログラムを複数起動することで、１つの計算機上で複数の仮想ノードが存在する形を実現することも可能である。
【００３８】
次に、図６を参照して、本発明の一実施例による識別子割当て方法を説明する。図６は、本発明の一実施例による識別子割当て方法の処理を示すフロー図である。なお、図６に示される処理フローは例示的なものにすぎず、本発明は図示された処理フローに限定されるものでない。
【００３９】
本実施例による識別子割り当て方法は、ステップＳ１０１において、識別子割当て装置１００が、新たに追加されたノードに対する識別子の割当て要求に応答して開始される。
【００４０】
ステップＳ１０２において、１ノードごとに割当てる識別子の個数ｖと、この時点で存在している全ての識別子の総数ａと、これらの識別子を記述した識別子一覧表とが入力される。
【００４１】
ステップＳ１０３において、初期化処理としてカウンタ変数ｉに０が設定される。
【００４２】
ステップＳ１０４において、現時点で割当て済みの識別子の総数が０であるか、すなわち、ａ＝０であるか判定される。現時点で割当て済みの識別子の総数が０である場合（ステップＳ１０４：ｙｅｓ）、すなわち、現在割当てようとしている識別子がこの分散システムにおける最初のノードの最初の識別子である場合、ステップＳ１０５において、識別子割当て装置１００は、割当てられる識別子の値を０に設定する。例えば、これは、コンシステント・ハッシング空間の上端の識別子に相当する。
【００４３】
他方、現時点で割当て済みの識別子の総数が０でない場合（ステップＳ１０４：ｎｏ）、ステップＳ１０６において、さらに現時点で割当て済みの識別子の総数が１であるか、すなわち、ａ＝１であるか判定される。現時点で割当て済みの識別子の総数が１である場合（Ｓ１０６：ｙｅｓ）、すなわち、現在割当てようとしている識別子がこの分散システムにおける２番目の識別子である場合、ステップＳ１０７において、割当てられる識別子の値を（識別子の取りうる上限値÷２）に設定する。例えば、これは、コンシステント・ハッシング空間の下端の識別子に相当する。
【００４４】
他方、現時点で割当て済みの識別子の総数が１でない場合（Ｓ１０６：ｎｏ）、本実施例の識別子割当て装置１００は、ステップＳ１０８以降において、識別子一覧表を参照して割当てる識別子の値を決定する。
【００４５】
ステップＳ１０８において、識別子割当て装置１００は、識別子一覧表を参照し、隣り合う識別子間の距離が最大となる領域を決定する。
【００４６】
ステップＳ１０９において、決定された最大領域の開始点及び終了点に相当する識別子をそれぞれＩＤｋ及びＩＤｋ＋１としたとき、割当てられる識別子ＮｅｗＩＤは、二等分から乱数分移動させた値で当該領域を分割し、すなわち、
ＮｅｗＩＤ＝｜ＩＤＸ−ＩＤＸ＋１｜／（２＋λ）
により算出される識別子をノード装置に割り当てる。なお、厳密には、最大の領域｜ＩＤｋ−ＩＤｋ＋１｜が識別子の上限値をまたいで存在する場合がある。この場合、上記の式では分割することができないが、その場合も適切に領域の中央値から乱数分移動させた値を返す式を適用するものとする。
【００４７】
このようにしてステップＳ１０５，Ｓ１０７及びＳ１０９で新しい識別子が取得された後、ステップＳ１１０において、識別子割当て装置１００は、カウンタ変数ｉと識別子の総数ａの値をそれぞれ１だけインクリメントすると共に、識別子一覧表を更新する。
【００４８】
ステップＳ１１１において、カウンタ変数ｉが１ノード毎に割当てられる識別子の個数ｖに満たない場合（Ｓ１１１：ｎｏ）、更なる識別子を割当てるため、ステップＳ１０６に戻って、同様の手順を実行することによって更なる識別子を割り当てる。他方、カウンタ変数ｉが１ノード毎に割当てられる識別子の個数ｖに等しい場合（Ｓ１１１：ｙｅｓ）、必要なｖ個の識別子の割当てが完了したことになるため、当該処理を終了する（ステップＳ１１２）。
【００４９】
なお、上述した識別子割当て装置１００の各機能部及び各ステップは、コンピュータのメモリ装置に記憶されたプログラムをプロセッサが実行することによって実現されてもよい。
【００５０】
本発明の識別子割当て装置及び方法では、ノードによって管理されるデータのそれぞれに識別子を割当て、あるノードが管理するデータの識別子の範囲を、ノード自身の識別子と、当該ノードよりも値の小さい識別子を持つノードの中では最も大きい値の識別子を持つノードの識別子との間と定める。また、各ノードの担当するデータ量等の負荷が均等に分散されるよう識別子の間隔が最も大きい領域から順に、１つのノードにつき複数の識別子を割り当てる。
【００５１】
なお、上述した実施例では、主にコンシステント・ハッシングのフレームワークにおいて、本発明の識別子割当て装置及び方法を用いる場合が説明されるが、本発明は、これに限定されるものでなく、識別子が識別以上の意味を持つ任意の分散プログラムに適用可能である。
【００５２】
本発明の識別子割当て装置及び方法によると、分散システムの識別子の間隔を均一化することができ、それによりノードの担当する処理量や複製データ量を均一化し、ノード間の負担量が公平になる。また、ノードの削除時に均一性が崩れる問題についても、各ノードに複数の識別子を割り当てることによって、これを軽減する。これらの特性により、分散システムにおいて、ノードの追加・削除などの状況に関わらずに、ノード間の負担を公平化することができ、システム全体の利用効率を上昇させることが可能になる。
【００５３】
以上、本発明の実施例について詳述したが、本発明は上述した特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【符号の説明】
【００５４】
１００  識別子割当て装置
１０１  識別子一覧表格納部
１１０  識別子決定部
１１１  決定的識別子決定部
１１２  複数識別子割当て部
【図１】
2018036793.tif 000003
【図２】
2018036793.tif 000004
【図３】
2018036793.tif 000005
【図４】
2018036793.tif 000006
【図５】
2018036793.tif 000007
【図６】
2018036793.tif 000008