JP5690296B2 - 負荷分散プログラムおよび負荷分散装置 - Google Patents

Description

本発明は、分散処理を行う分散システムにおける負荷分散の技術に関する。

分散システムは、複数の物理的なノード（サーバ）を含み、所定のセッション制御を実現する。必要であればこれらのノードを仮想化してもよい。セッション接続要求、データ取得要求、データ保管要求などの要求を含むメッセージが、ラウンドロビンなどを行うロードバランサを介して、端末（クライアント）から各ノードに振り分けられると、各ノードは、所定の方法に従ってメッセージを他のノードにさらに振り分けることができる。つまり、分散システムの各ノードは、負荷を分担する。各ノードは、振り分けられたメッセージを呼処理し、端末に対して所定のサービスを提供する。

前記所定の方法としては、例えば、コンシステント・ハッシュ法がある。なお、非特許文献１は、コンシステント・ハッシュ法について開示している。コンシステント・ハッシュ法は、ノードを識別するノード識別子と、呼処理で書き換えを要求されるデータを識別するデータ識別子とに基づいて、どのノードにどのメッセージを振り分けるかを決定する方法である。データ識別子は、クライアントから送信されるメッセージに含まれている。各ノードは、データ識別子で識別されるデータを保管（記憶）しており、振り分けられたメッセージに含まれる要求に応じて保管しているデータを適宜書き換える。

具体的に、どのようにしてメッセージが振り分けられるかを、図６を参照して説明する。図６は、コンシステント・ハッシュ法を説明するためのＩＤ（Identifier）空間の概念図である。ノード識別子は、例えば、ノードのＩＰ（Internet Protocol）アドレス、ノード名などに、ハッシュ関数を作用させて得られた値である。図６において、ノード識別子は、「●」で示されている。

ＩＤ空間は、図６に示すようにリング状で描写されるハッシュ空間である。ノード識別子は、例えば、その値に基づいてＩＤ空間において時計回りに昇順に配置される。メッセージがあるノードに振り分けられるとき、データ識別子は、その値に基づいてハッシュ空間に写像して配置される。データ識別子も、その値に基づいてＩＤ空間において時計回りに昇順に配置される。図６において、データ識別子は、「○」で示されている。

このとき、ノードは、自身のノード識別子の直近のノード識別子の配置場所から自身のノード識別子の配置場所まで時計回りに辿る円弧上に配置されるデータ識別子を含むメッセージを呼処理する。ここで、「直近のノード識別子」とは、ＩＤ空間において、対象のノード識別子の値よりも小さな値を持つノード識別子のうち最も大きな値を持つノード識別子を意味する。しかし、対象のノード識別子がＩＤ空間において最も小さな値を持つ場合には、直近のノード識別子は、ＩＤ空間において最も大きな値を持つこととする。すると、直近のノード識別子の配置場所から対象のノード識別子の配置場所まで時計回りに辿る円弧が、対象のノード識別子で識別されるノードがメッセージの呼処理を担当する範囲である。図６において、ＩＤ空間に配置される対象のデータ識別子で識別されるデータと、そのデータ識別子を含むメッセージの呼処理を担当するノードとの関係を示す担当関係は、矢印で示されている。

図６によれば、ノード識別子Ａ、Ｂ、Ｃの値にＡの値＜Ｂの値＜Ｃの値という関係があるとすると、時計回りにＡ→Ｂ→Ｃの順番にノード識別子が配置される。また、データ識別子Ｘの値について、Ａの値＜Ｘの値＜Ｂの値という関係があるとすると、データ識別子Ｘは、ノード識別子Ａおよびノード識別子Ｂの間に配置される。よって、データ識別子Ｘを含むメッセージについては、ノード識別子Ｂで識別されるノードが呼処理を担当する。つまり、図６において、ノード識別子Ａからノード識別子Ｂまでに辿る円弧が、ノード識別子Ｂで識別されるノードがメッセージを担当する範囲となる。

コンシステント・ハッシュ法によれば、ノード識別子の値およびデータ識別子の値は、例えば、ハッシュ関数を作用させることで無作為な値となる。よって、各ノードが担当するメッセージの処理量は確率的に均一に近づき、確率的に均一な負荷分散が実現される。

前記コンシステント・ハッシュ法には、１つの実際のノードに複数の仮想的なノード識別子を割り当て、１つのノードを複数の仮想的なノードの集合として実現する手段がある。この手段により、ある実際のノードが担当するメッセージの処理量は、複数の仮想的なノードが各々担当するメッセージの処理量の合計値となる。大数の法則により、仮想的なノードの数が多いほど、実際のノードのそれぞれに対するこの合計値の分布は平均値に近づく。よって、複数の仮想的なノード識別子を用いることにより、負荷分散が確率的に決まる影響を抑え、さらに負荷分散を均一に近づけることができる。つまり、負荷分散性を向上することができる。

しかし、一般的に、分散システムを構成するノードの性能は、各ノード間で異なっている。よって、負荷分散を確率的に決める手法を用いると、性能の高いノードが僅かな負荷しか分担せず、遊休資源が発生したり、性能の低いノードが、処理しきれない程の膨大な負荷を分担したりする場合が生じる。このような場合、分散システム全体の負荷分散性の低下を招く。このような事態を解消するために、各ノード間の性能の違いを考慮して各ノードが分担する負荷の量を変化させることが望まれている。

例えば、非特許文献２には、前記した仮想的なノード識別子の数量を、実際のノードの性能に応じて変更し、性能が大きい程、多くの仮想的なノード識別子を実際のノードに割り当てる技術が開示されている。この技術によれば、各ノード間の性能の違いを考慮した負荷分散性をある程度は実現することができる。

一方、コンシステント・ハッシュ法では、ノードが保管するデータ（原本データ）の複製（複製データ）を１または複数作成し、作成した複製データを、別のノードが保管する手法がある。この手法により、分散システムの障害やノードの削除などに起因するデータの損失を回避することができる。前記手法の代表的なものとしては、原本データを保管するノードに対し、ＩＤ空間において時計回りに隣接するノードが複製データを保管する手法がある。また、原本データのデータ識別子に再度ハッシュ関数を作用させ、その作用させた値をデータ識別子とみなした場合にどのノードが担当するかを、図６を用いて上述した法則に従って決定し、そのノードに複製データを保管させる方法がある。分散システムを構築する際には、前記負荷分散性の向上とともに、データを複製することで得られるデータ信頼性の向上も実現することが望まれている。

David Karger、外５名、"Consistent Hashing and Random Trees:Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web"、［online］、［平成２４年２月２１日検索］、インターネット〈URL：http://www.akamai.com/dl/technical_publications/ConsistenHashingandRandomTreesDistributedCachingprotocolsforrelievingHotSpotsontheworldwideweb.pdf〉 D. Dabek, M. Kaashoek, D. Karger, R. Morris, and I. Stoica, "Wide-area cooperative storage with CFS"、［online］、［平成２４年２月２１日検索］、インターネット〈URL：http://pdos.csail.mit.edu/papers/cfs:sosp01/cfs_sosp.pdf〉

しかし、非特許文献２の技術では、ノードの性能に関する取り扱いが単純すぎるため、分散システムにおける負荷分散性の向上とデータ信頼性の向上との両立を実現することは困難である。

このような事情に鑑みて、本発明は、分散システムにおける負荷分散性の向上とデータ信頼性の向上との両立を実現することを目的とする。

前記課題を解決するため、請求項１に記載の発明は、自身のサーバ以外の他のサーバと協調動作することでコンシステント・ハッシュ法により振り分けられたメッセージを呼処理する複数の前記サーバが通信可能に接続されている分散システムにおいて、前記サーバそれぞれに対して１または複数の識別子を割り当てることで、前記サーバそれぞれがどのメッセージの呼処理を担当するかを決定する負荷分散装置として機能させる負荷分散プログラムであって、前記負荷分散装置の記憶部が、前記サーバの演算性能と、前記サーバの記憶容量とを、前記サーバごとに記憶しており、前記負荷分散装置の制御部に、前記サーバそれぞれの演算性能を用いて、前記メッセージの呼処理のために必要となる原本データを処理するサーバそれぞれに割り当てる前記識別子となる原本データ処理用識別子の個数と、前記原本データ処理用識別子の値とを設定する処理と、前記サーバそれぞれの記憶容量を用いて、前記原本データを複製した複製データを保管するサーバそれぞれに割り当てる前記識別子となる複製データ保管用識別子の個数と、前記複製データ保管用識別子の値とを設定する処理と、を実行させることを特徴とする。

また、請求項２に記載の発明は、請求項１の発明において、前記負荷分散装置の制御部に、前記サーバの演算性能が大きいほど、前記サーバに割り当てる前記原本データ処理用識別子の個数を多くする処理と、前記サーバの記憶容量が大きいほど、前記サーバに割り当てる前記複製データ保管用識別子の個数を多くする処理と、を実行させることを特徴とする。

また、請求項３に記載の発明は、請求項１または請求項２に記載の発明において、前記負荷分散装置の制御部に、前記分散システムに追加したサーバを検出する処理と、前記追加したサーバの演算性能と、記憶容量とを特定し、前記記憶部に記憶する処理と、前記追加したサーバの演算性能を用いて、前記追加したサーバに割り当てる前記原本データ処理用識別子の個数と、前記原本データ処理用識別子の値とを設定する処理と、前記追加したサーバの記憶容量を用いて、前記追加したサーバに割り当てる前記複製データ保管用識別子の個数と、前記複製データ保管用識別子の値とを設定する処理と、を実行させることを特徴とする。

また、請求項４に記載の発明は、自身のサーバ以外の他のサーバと協調動作することでコンシステント・ハッシュ法により振り分けられたメッセージを呼処理する複数の前記サーバが通信可能に接続されている分散システムにおいて、前記サーバそれぞれに対して１または複数の識別子を割り当てることで、前記サーバそれぞれがどのメッセージの呼処理を担当するかを決定する負荷分散装置であって、前記負荷分散装置の記憶部が、前記サーバの演算性能と、前記サーバの記憶容量とを、前記サーバごとに記憶しており、前記負荷分散装置の制御部が、前記サーバそれぞれの演算性能を用いて、前記メッセージの呼処理のために必要となる原本データを処理するサーバそれぞれに割り当てる前記識別子となる原本データ処理用識別子の個数と、前記原本データ処理用識別子の値とを設定する制御と、前記サーバそれぞれの記憶容量を用いて、前記原本データを複製した複製データを保管するサーバそれぞれに割り当てる前記識別子となる複製データ保管用識別子の個数と、前記複製データ保管用識別子の値とを設定する制御と、を実行することを特徴とする。

請求項１、４に記載の発明によれば、サーバに割り当てる識別子として、サーバの演算性能に応じて個数と値を設定した原本データ処理用識別子と、サーバの記憶容量に応じて個数と値を設定した複製データ保管用識別子と、を別々に設けたので、分散システムにおける負荷分散性の向上とデータ信頼性の向上との両立を実現することができる。

請求項２に記載の発明によれば、サーバの演算性能に見合う原本データ処理用識別子と、サーバの記憶容量に見合う複製データ保管用識別子と、を設定できるので、サーバ資源の利用効率を最大限に高めることができる。

請求項３に記載の発明によれば、追加したサーバに相応しい識別子を割り当てることができる。

本発明によれば、分散システムにおける負荷分散性の向上とデータ信頼性の向上との両立を実現することができる。

分散システムの構成図である。 ノードで使用されるソフトウェアの構成図である。 （ａ）が性能情報管理テーブルのデータ構造を示す図であり、（ｂ）が処理用識別子管理テーブルのデータ構造を示す図であり、（ｃ）が複製用識別子管理テーブルのデータ構造を示す図である。 ノードを追加したときに、分散システムを構成する各ノードが実行する処理を示すフローチャートである。 （ａ）が処理データ用ＩＤ空間の概念図であり、（ｂ）が複製データ用ＩＤ空間の概念図である。 コンシステント・ハッシュ法を説明するためのＩＤ空間の概念図である。

≪構成≫
まず、本実施形態の構成について説明する。
図１は、分散システムの構成図である。この分散システムは、ノード１（サーバ）と、ロードバランサ３とを含む。クライアント２は、この分散システムと通信可能に接続している。この分散システムは、複数のノード１が協調動作してセッション制御を行い、クライアント２に所定のサービスを提供する。ノード１は、前記した協調動作を実現するための負荷分散プログラム１ａを備えている。前記セッション制御は、例えば、呼制御であり、ＳＩＰ（Session Initiation Protocol）を使用して、インターネット電話などのサービスが提供される。

ノード１は、例えばコンシステント・ハッシュ法によって、ロードバランサ３を介してクライアント２から受信したメッセージを、そのメッセージの呼処理を担当している他のノード１に振り分けることができる。前記メッセージは、例えばＳＩＰ信号であり、セッション接続要求、データ取得要求、データ保管要求などといったクライアント２からの要求を含む。結果的に、各ノード１は、自身が担当するメッセージを呼処理して、クライアント２にサービスを提供する。ノード１は、計算機やコンピュータなどの物理的な装置であってもよいし、仮想マシンなどの論理的な装置であってもよい。分散システムは、複数のノード１などのコンピュータ資源を仮想化して動作するクラスタシステムとすることができる。コンピュータ資源の仮想化には、例えば、VMware（登録商標）を用いることができる。

クライアント２は、メッセージをロードバランサ３に送信し、ノード１が提供するサービスを利用する。

ロードバランサ３は、例えばラウンドロビンによって、クライアント２から受信したメッセージをノード１のそれぞれに無作為に振り分ける。ロードバランサ３が、呼処理の担当外となるメッセージをノード１に振り分けた場合、そのメッセージの呼処理を担当しているノード１は、前記担当外のノードに要求して、そのメッセージを取得することができる。

ノード１と、クライアント２と、ロードバランサ３とはいずれも、入力部、出力部、制御部および記憶部といったハードウェアを含むコンピュータである。入力部は、例えば、入力インタフェースから構成される。出力部は、例えば、出力インタフェースから構成される。制御部は、例えば、ＣＰＵ（Central Processing Unit）や専用回路から構成される。記憶部は、例えば、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ＨＤＤ（Hard Disk Drive）、フラッシュメモリの記憶媒体から構成される。前記制御部がＣＰＵから構成される場合、その制御部を含むコンピュータによる情報処理は、ＣＰＵによるプログラム実行処理で実現する。また、そのコンピュータが含む記憶部は、ＣＰＵが指令し、そのコンピュータの機能を実現するためのプログラム（負荷分散プログラム１ａを含む）を記憶する。これによりソフトウェアとハードウェアの協働が実現される。

本実施形態は、前記情報処理を実行させるプログラムによって実現することができ、そのプログラムをコンピュータによる読み取り可能な記録媒体（例：ＣＤ−ＲＯＭ）に記憶して提供することができる。また、そのプログラムを、インターネットのネットワークを通して提供することもできる。

本実施形態の分散システムで使用されるソフトウェア（負荷分散プログラム１ａ）について説明する。
図２は、ノード１で使用されるソフトウェアの構成図である。ノード１は、ノード検出部１１と、性能情報特定部１２と、識別子割当設定部１３と、性能情報管理テーブルＴ１と、処理用識別子管理テーブルＴ２と、複製用識別子管理テーブルＴ３といった構成要素を備える。なお、ノード１が備える構成要素は他にも存在するが、その説明は省略する。

ノード検出部１１は、分散システムに追加された、つまり増設されたノード１を検出する。また、ノード検出部１１は、分散システムからノード１が削除された、つまり減設されたことを検出することができる。例えば、分散システムを構成する各ノード１は、他のノード１に対して生存信号を定期的に送信している。もし、あるノード１からの生存信号の受信が所定期間以上なかったときには、そのノード１は分散システムから削除されたとみなす。

なお、前記したとおり、コンシステント・ハッシュ法では、分散システムを構成するノード１には、１または複数の仮想的なノード識別子を割り当てることで、１つの実際のノード１を１または複数の仮想的なノードの集合として実現することができる。そのような仮想的なノード識別子は、ＩＤ空間（図６参照）に配置することができる。本実施形態では、１つの実際のノード１に割り当てる１または複数の仮想的なノード識別子を「仮想識別子」と呼ぶ。仮想識別子を用いることで、複数の仮想的なノードのそれぞれを識別することができる。仮想識別子の値は、例えば、ノード１のＩＰアドレスや名称などを用いた文字数値列に、ハッシュ関数を作用させたハッシュ値である。分散システムを構成する既存のノード１および分散システムに追加されたノード１に対して、１または複数の仮想識別子が割り当てられる。なお、本実施形態では、特に断らない限り、単にノード識別子と述べるときは、仮想識別子（特許請求の範囲の「識別子」に相当）を意味することとする。

性能情報特定部１２は、ノード１の性能情報を特定する。「性能情報」とは、ノード１の性能を特定する情報であるが、主に、演算性能と、記憶容量と、の２つのパラメータを含む情報である。ただし、性能情報が含むパラメータはこの２つに限定されない。

「演算性能」とは、ノード１が処理することができる単位時間あたりの情報量の大きさを示すパラメータである。演算性能の具体例としては、ノードのＣＰＵ周波数があげられる。演算性能の値が大きいほど、ノード１が処理することができる単位時間あたりの情報量が大きい。演算性能の値が大きいノード１は、担当するメッセージを呼処理するために保管しているデータ、つまり原本データを書き換えたり、クライアント２からの要求に応答したりするなどの処理に長けている。なお、原本データの処理には、原本データを複製し、複製データを生成することも含まれる。

「記憶容量」とは、ノード１が記憶することができる情報量の大きさを示すパラメータである。記憶容量の具体例としては、ノード１の記憶部の記憶容量があげられる。また、ノード１がデータストアを使用してデータを記憶するリソース（例：ディスク）の記憶容量でもよい。記憶容量の値が大きいほど、ノード１が記憶することができる情報量が大きい。記憶容量の大きいノード１は、原本データを複製した複製データを保管し、複製データを保管することに長けている。

性能情報は、演算性能の値と、記憶容量の値と、をそのまま用いた二次元の値を持つ情報であってもよい。また、ノード１の総合的な性能を判断するために、ベンチマークプログラムを用いて、演算性能の値や記憶容量の値を用いて算出されるスコアを性能情報としてもよい。前記スコアは、一次元の値とすることもできるし、二次元以上の値とすることもできる。

識別子割当設定部１３は、ノード１に割り当てる仮想識別子の値と個数を設定する。つまり、各ノード１について、ＩＤ空間にいくつの仮想識別子をどこに配置するかを決定する。本実施形態では、ＩＤ空間として、原本データを処理するための原本データ用ＩＤ空間と、複製データを保管するための複製データ用ＩＤ空間とを設ける。原本データ用ＩＤ空間に仮想識別子を配置することで、その仮想識別子を持つノード１は、原本データを処理することができる。複製データ用ＩＤ空間に仮想識別子を配置することで、その仮想識別子を持つノード１は、複製データを保管することができる。

性能情報管理テーブルＴ１は、ノード１の性能情報を管理する。図３（ａ）には、性能情報管理テーブルのデータ構造が示されている。性能情報管理テーブルＴ１は、「アドレス」と、「演算性能」と、「記憶容量」といったフィールドを含み、ノード１ごとにレコードが作成される。

「アドレス」のフィールドには、ノード１のＩＰアドレスの値が格納されている。
「演算性能」のフィールドには、ノード１の演算性能の値が格納されている。
「記憶容量」のフィールドには、ノード１の記憶容量の値が格納されている。

処理用識別子管理テーブルＴ２は、ノード１に割り当てられる仮想識別子のうち原本データの処理のために割り当てられる仮想識別子が、原本データ用ＩＤ空間にどのように配置されているかを管理するテーブルである。図３（ｂ）には、処理用識別子管理テーブルのデータ構造が示されている。処理用識別子管理テーブルＴ２は、「アドレス」と、「仮想識別子」と、「順位」といったフィールドを含み、原本データの処理のために割り当てられる仮想識別子ごとにレコードが作成される。

処理用識別子管理テーブルＴ２の「アドレス」のフィールドは、性能情報管理テーブルＴ１の「アドレス」のフィールドと同等であり、互いに関連付けられている。
「仮想識別子」のフィールドには、１つのノード１に対して、原本データの処理のために割り当てられる仮想識別子（原本データ処理用識別子）の値（ハッシュ値）が格納されている。
「順位」のフィールドには、１つのノード１に対して、原本データの処理のために割り当てられる仮想識別子に付す順位を表す数値（例：１、２、・・・、Ｐ１）が格納されている。

基本的には、ノード１の演算性能の値が大きいほど、原本データの処理のために割り当てられる仮想識別子の個数を多くする。そうすることで、原本データを処理するためのノード１のＩＤ空間内の担当範囲が大きくなり、演算性能の値に見合う処理量（演算量）を達成することができる。

原本データの処理のために割り当てられる仮想識別子の個数の設定方法としては、例えば、演算性能に関する基準値を用いる方法がある。この基準値は、分散システムの運用者が経験的に妥当と定めた任意の数値である。ノード１の演算性能が基準値と同程度であれば、相応の個数（例：１００個）の仮想識別子を割り当てる。もし、ノード１の演算性能が基準値の２倍であれば、２倍の個数分の仮想識別子を割り当てる。また、ノード１の演算性能が基準値の０．５倍であれば、０．５倍の個数分の仮想識別子を割り当てる。１つのノード１に割り当てる仮想識別子の個数は、そのノード１のＩＰアドレスに対応する「順位」のフィールドに格納される順位の個数、つまりレコード数（例：Ｐ１個、Ｐ２個）に等しい。

一方、原本データの処理のために割り当てられる仮想識別子の値の設定方法としては、例えば、上記の順位を用いる方法がある。つまり、１つのノード１のＩＰアドレスに前記順位を加味した文字数値列に対してハッシュ関数を作用させてハッシュ値を生成し、そのハッシュ値を、原本データの処理のために割り当てられる仮想識別子の値とする。

順位の数値を用いることで、１つのノード１に割り当てられる複数個（順位の個数分）の仮想識別子は、各ノード１間だけでなく、そのノード１においても一意に定まる。なお、１つのノード１において複数個の仮想識別子が一意に定まればよいので、順位の代わりに、互いに異なる適当な値を用いてもよい。さらに、前記適当な値において、順位のように順番が定められているか否かは問わない。また、ＩＰアドレスに順位を加味するときの「加味」の方法は、例えば、四則演算のような所定の演算方法でよい。

さらに、ハッシュ関数を用いているので、原本データ用ＩＤ空間において、複数個の仮想識別子を無作為に、つまり満遍なく配置することができる。その結果、負荷分散性を向上させることができる。

複製用識別子管理テーブルＴ３は、ノード１に割り当てられる仮想識別子のうち複製データの保管のために割り当てられる仮想識別子が、複製データ用ＩＤ空間にどのように配置されているかを管理するテーブルである。図３（ｃ）には、複製用識別子管理テーブルのデータ構造が示されている。複製用識別子管理テーブルＴ３は、「アドレス」と、「仮想識別子」と、「順位」といったフィールドを含み、複製データの処理のために割り当てられる仮想識別子ごとにレコードが作成される。

複製用識別子管理テーブルＴ３の「アドレス」のフィールドは、性能情報管理テーブルＴ１の「アドレス」のフィールドと同等であり、互いに関連付けられている。
「仮想識別子」のフィールドには、１つのノード１に対して、複製データの保管のために割り当てられる仮想識別子（複製データ保管用識別子）の値（ハッシュ値）が格納されている。
「順位」のフィールドには、１つのノード１に対して、複製データの保管のために割り当てられる仮想識別子に付す順位を表す数値（例：１、２、・・・、Ｃ１）が格納されている。

基本的には、ノード１の記憶容量の値が大きいほど、複製データの保管のために割り当てられる仮想識別子の個数を多くする。そうすることで、複製データを保管するためのノード１のＩＤ空間内の担当範囲が大きくなり、記憶容量の値に見合う使用記憶容量を達成することができる。

複製データの保管のために割り当てられる仮想識別子の個数（例：Ｃ１個、Ｃ２個）および値の設定方法は、原本データの処理のために割り当てられる仮想識別子の個数および値を設定するときの上記した方法と同様にすることができるため、説明を省略する。

≪処理≫
次に、本実施形態の処理について説明する。
図４は、ノードを追加したときに、分散システムを構成する各ノードが実行する処理を示すフローチャートである。この処理の主体は、分散システムを構成する各ノード１の制御部である。この処理は、ステップＳ０１から開始する。

ステップＳ０１において、ノード１の制御部は、分散システムに新たに追加されたノード１である追加ノードを検出する。ステップＳ０１の処理は、主に、ノード検出部１１の機能に従う。ステップＳ０１の後、ステップＳ０２に進む。

ステップＳ０２において、ノード１の制御部は、追加ノードの性能情報を特定する。ステップＳ０２の処理は、主に、性能情報特定部１２の機能に従う。特定した性能情報は、ノード１の記憶部に記憶され、性能情報管理テーブルＴ１に登録される。ステップＳ０２の後、ステップＳ０３に進む。

ステップＳ０３において、ノード１の制御部は、追加ノードに対して、原本データを処理するための仮想識別子の個数と値を設定する。設定された前記仮想識別子の個数と値は、処理用識別子管理テーブルＴ２に所定の形式で登録される。ステップＳ０３の処理は、主に、識別子割当設定部１３の機能に従う。ステップＳ０３の後、ステップＳ０４に進む。

ステップＳ０４において、ノード１の制御部は、追加ノードに対して、複製データを保管するための仮想識別子の個数と値を設定する。設定された前記仮想識別子の個数と値は、複製用識別子管理テーブルＴ３に所定の形式で登録される。ステップＳ０４の処理は、主に、識別子割当設定部１３の機能に従う。ステップＳ０４の後、ステップＳ０５に進む。

ステップＳ０５において、ノード１の制御部は、設定した値を持つ設定個数分の仮想識別子を追加ノードに割り当てる。つまり、追加ノードに割り当てる仮想識別子を原本データ用ＩＤ空間と、複製データ用ＩＤ空間とにそれぞれ配置する。

ステップＳ０１〜ステップＳ０５の処理を行うことにより、追加ノードの演算性能に見合う個数と値を設定した仮想識別子を原本データ用ＩＤ空間に配置するとともに、追加ノードの記憶容量に見合う個数と値を設定した仮想識別子を複製データ用ＩＤ空間に配置することができる。その結果、性能情報に見合う負荷分散性と、データ信頼性とを実現することができる。
以上で、図４の処理の説明を終了する。

≪具体例≫
図５を参照して、図４の処理を終えた後の分散システムの様子の具体例を説明する。
図５は、（ａ）が処理データ用ＩＤ空間の概念図であり、（ｂ）が複製データ用ＩＤ空間の概念図である。なお、複製データ用ＩＤ空間における、複製データの複製数Ｍは、例えば、Ｍ＝２とし、１つの原本データに対して２つの複製データを生成する場合を想定するが、複製数はこれに限定されない。

処理データ用ＩＤ空間において、追加ノードには、原本データを処理するためのノード識別子ａが割り当てられたとし、ノード識別子ａは、図５（ａ）に示す位置に配置されたとする。ここで、図５（ａ）に示す位置に配置されることになるデータ識別子Ｘを含むメッセージがロードバランサ３から振り分けられた場合には、データ識別子Ｘの時計回りに辿って右隣に配置されているノード識別子ａが割り当てられた追加ノードが、そのメッセージの呼処理を行い、呼処理の対象となる原本データを処理する。

一方、複製データ用ＩＤ空間において、分散システムを構成する既存のノード１の一つには、複製データを処理するためのノード識別子ｂが割り当てられており、追加ノードには、複製データを処理するためのノード識別子ｃが割り当てられているとする。そして、ノード識別子ｂ、ｃは、図５（ｂ）に示す位置に配置されているとする。図５（ｂ）に示すデータ識別子Ｘが配置される位置は、図５（ａ）に示す位置と同じである。よって、データ識別子Ｘを含むメッセージがロードバランサ３から振り分けられた場合には、データ識別子Ｘの時計回りに辿って右隣に配置されているノード識別子ｂが割り当てられたノード１、そしてさらに右隣に配置されているノード識別子ｃが割り当てられた追加ノードが、そのメッセージの呼処理の対象となる原本データの複製データを保管する。

なお、所定のデータ識別子を含むメッセージが原本データ用ＩＤ空間に配置された場合、そのメッセージの呼処理を担当するノード１は、原本データの書き換えを行うとともに、クライアント２からの要求に応答することで、クライアント２所定のサービスを提供する。また、前記ノード１は、前記原本データの複製データの保管を担当している他のノード１に対し、書き換え前の原本データと書き換え後の原本データとの差分となる差分データを送信する。一方、そのメッセージが複製データ用ＩＤ空間に配置された場合、そのメッセージの呼処理の対象となる原本データの複製データの保管を担当するノード１は、原本データの処理を担当するノード１から前記差分データを受信し、複製データを更新する。複製データの保管を担当するノード１は、クライアント２からの要求に応答することはなく、原本データの処理を担当するノード１の故障などの障害が発生するまで、複製データの保管を継続する。

≪まとめ≫
本発明によれば、分散システムにおける負荷分散性の向上とデータ信頼性の向上との両立を実現することができる。従来では分散システムに対して１つのＩＤ空間を適用してメッセージの振り分けを行っていたが、原本データ用ＩＤ空間、複製データ用ＩＤ空間、という独立した２種類のＩＤ空間を適用することで、ノードの性能情報に見合った仮想識別子の配置を実現することができるからである。２種類のＩＤ空間を設定する際、仮想識別子の管理テーブル（Ｔ２、Ｔ３）は、同等のデータ構造を備えるように設計できる。

演算性能が大きなノードが追加されたときには、原本データを処理するための仮想識別子をそのノードに多く割り当て、原本データ用ＩＤ空間に多くの仮想識別子を配置する。また、記憶容量が大きなノードが追加されたときには、複製データを保管するための仮想識別子をそのノードに多く割り当て、複製データ用ＩＤ空間に多くの仮想識別子を配置する。このような配置により、それぞれで値が異なるノードの演算性能と記憶容量とに応じたメッセージの振り分けが可能となる。その結果、性能情報の異なるノードで構成される分散システムにおいて、ノードの性能を最大限に生かすことができ、ノード資源の利用効率を最大限に高めることができる。

≪その他≫
前記実施形態は、本発明を実施するために好適のものであるが、その実施形式はこれらに限定されるものでなく、本発明の要旨を変更しない範囲内において種々変形することが可能である。

例えば、ノード１が実際に原本データの処理や複製データの保管などを行うときの演算量や使用記憶容量は、さまざまな要因によって変化する。前記要因は、例えば、複製データの保管には、複製データの受信、更新などに伴う演算量があること、複製データの複製数の設定、性能情報に用いる新たなパラメータを採用すること、その他さまざまな要因である。よって、ノード１に割り当てる仮想識別子の値と個数を設定するときは、これらの要因を考慮することが好ましい。

また、例えば、ノード１がＨＴＴＰ（HyperText Transfer Protocol）サーバである場合、メッセージに含まれているデータ識別子には、メッセージが要求するＵＲＬ（Uniform Resource Locator）、クライアント２のＩＰアドレス、Ｃｏｏｋｉｅなど、といったさまざまな情報を用いることができる。

また、例えば、仮想識別子の値を求めるために、ノード１のＩＰアドレスの代わりに、例えばＭＡＣ（Media Access Control address）アドレスを用いてもよい。また、分散システム上でノード１を特定できる機能を持つのであればどのような種類のアドレスを用いてもよい。

また、例えば、分散システムにノード１を１つだけでなく、２つ以上同時増設する場合についても、本発明を適用できる。つまり、２つ以上同時増設するノード１のそれぞれに対して割り当てる原本データを処理するための、および複製データを保管するための仮想識別子を、２種類のＩＤ空間に一度にまとめて配置することができる。

また、負荷分散プログラム１ａを備え、その命令に従う負荷分散装置を、ロードバランサ３の代わりに備えた、またはロードバランサ３と併設した分散システムを構成することもできる。よって、負荷分散装置は、ノード１とは別の装置とすることもできるし、ノード１が含む装置とすることもできる。概して本発明の負荷分散装置とは、負荷分散プログラム１ａに記述された命令に従うコンピュータを意味している。よって、負荷分散プログラム１ａは、負荷分散装置とは別のコンピュータに導入されており、遠隔的に負荷分散装置に命令することもできる。また、コンピュータとしての機能を担保できるのであれば、負荷分散装置のハードウェアの形態は、どのようにしても構わない。負荷分散装置は、１または複数のコンピュータから構成してもよい。

また、本実施形態で説明した種々の技術を適宜組み合わせた技術を実現することもできる。
また、本実施形態で説明したソフトウェアをハードウェアとして実現することもでき、ハードウェアをソフトウェアとして実現することもできる。

その他、ハードウェア、ソフトウェア、テーブル、フローチャートなどの具体的な構成について、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。

１ ノード（サーバ）
２ クライアント
３ ロードバランサ
１１ ノード検出部
１２ 性能情報特定部
１３ 識別子割当設定部
Ｔ１ 性能情報管理テーブル
Ｔ２ 処理用識別子管理テーブル
Ｔ３ 複製用識別子管理テーブル

Claims (4)

1. 自身のサーバ以外の他のサーバと協調動作することでコンシステント・ハッシュ法により振り分けられたメッセージを呼処理する複数の前記サーバが通信可能に接続されている分散システムにおいて、前記サーバそれぞれに対して１または複数の識別子を割り当てることで、前記サーバそれぞれがどのメッセージの呼処理を担当するかを決定する負荷分散装置として機能させる負荷分散プログラムであって、
   前記負荷分散装置の記憶部が、
   前記サーバの演算性能と、前記サーバの記憶容量とを、前記サーバごとに記憶しており、
   前記負荷分散装置の制御部に、
   前記サーバそれぞれの演算性能を用いて、前記メッセージの呼処理のために必要となる原本データを処理するサーバそれぞれに割り当てる前記識別子となる原本データ処理用識別子の個数と、前記原本データ処理用識別子の値とを設定する処理と、
   前記サーバそれぞれの記憶容量を用いて、前記原本データを複製した複製データを保管するサーバそれぞれに割り当てる前記識別子となる複製データ保管用識別子の個数と、前記複製データ保管用識別子の値とを設定する処理と、を実行させる
   ことを特徴とする負荷分散プログラム。
2. 前記負荷分散装置の制御部に、
   前記サーバの演算性能が大きいほど、前記サーバに割り当てる前記原本データ処理用識別子の個数を多くする処理と、
   前記サーバの記憶容量が大きいほど、前記サーバに割り当てる前記複製データ保管用識別子の個数を多くする処理と、を実行させる
   ことを特徴とする請求項１に記載の負荷分散プログラム。
3. 前記負荷分散装置の制御部に、
   前記分散システムに追加したサーバを検出する処理と、
   前記追加したサーバの演算性能と、記憶容量とを特定し、前記記憶部に記憶する処理と、
   前記追加したサーバの演算性能を用いて、前記追加したサーバに割り当てる前記原本データ処理用識別子の個数と、前記原本データ処理用識別子の値とを設定する処理と、
   前記追加したサーバの記憶容量を用いて、前記追加したサーバに割り当てる前記複製データ保管用識別子の個数と、前記複製データ保管用識別子の値とを設定する処理と、を実行させる
   ことを特徴とする請求項１または請求項２に記載の負荷分散プログラム。
4. 自身のサーバ以外の他のサーバと協調動作することでコンシステント・ハッシュ法により振り分けられたメッセージを呼処理する複数の前記サーバが通信可能に接続されている分散システムにおいて、前記サーバそれぞれに対して１または複数の識別子を割り当てることで、前記サーバそれぞれがどのメッセージの呼処理を担当するかを決定する負荷分散装置であって、
   前記負荷分散装置の記憶部が、
   前記サーバの演算性能と、前記サーバの記憶容量とを、前記サーバごとに記憶しており、
   前記負荷分散装置の制御部が、
   前記サーバそれぞれの演算性能を用いて、前記メッセージの呼処理のために必要となる原本データを処理するサーバそれぞれに割り当てる前記識別子となる原本データ処理用識別子の個数と、前記原本データ処理用識別子の値とを設定する制御と、
   前記サーバそれぞれの記憶容量を用いて、前記原本データを複製した複製データを保管するサーバそれぞれに割り当てる前記識別子となる複製データ保管用識別子の個数と、前記複製データ保管用識別子の値とを設定する制御と、を実行する
   ことを特徴とする負荷分散装置。

Images