JP6696941B2 - 負荷分散装置および負荷分散方法 - Google Patents

Description

本発明は、負荷分散装置および負荷分散方法に関する。

サーバ構成技術や仮想化技術の発達、激甚災害対策等により、地域や国をまたいでデータセンタが接続され、そのデータセンタ内に複数の処理サーバが存在するようになった。点在する処理サーバに対して負荷を分散するため、ロードバランサのような負荷分散装置を設置し、当該負荷分散装置を用いて要求信号（リクエスト）を処理サーバに振り分け、各処理サーバの負荷を分散させることが一般的である。

しかし、地域や国をまたいで信号を処理サーバに振り分けることによって、当該信号において、地域や国をまたぐ分の処理遅延が生じることになる。処理遅延が生じると、例えば通信制御サーバにおいては、後続信号が先行信号を追い抜いたりすることも考えられ問題となる。一方で、処理遅延を防止するため、拠点内の処理サーバへ優先して信号を割り振ると、拠点内の処理サーバのみ負荷が重くなってしまい、ハードウェアリソースの非効率化や不要なスケーリング、負荷軽減のためのサービス処理規制につながってしまう。このように、複数拠点に存在する処理サーバへの信号振り分けには、処理負荷と処理ＴＡＴ（Turn Around Time）とのトレードオフ関係がある。

負荷分散に関する従来技術の例が、非特許文献１〜３に開示されている。特に、非特許文献３には、非特許文献１，２を基にして、動的に変動する処理サーバの負荷やＴＡＴを考慮して、高速サーバ（低遅延サーバ）にできるだけ多くの信号を振り分けることによって、要求信号の平均処理ＴＡＴを低減する方法が開示されている。

負荷分散入門(ロードバランサ入門),［online］,［平成２９年６月１９日検索］,インターネット 〈 URL : http://fenics.fujitsu.com/products/ipcom/catalog/data/1/3.html〉 北野 雄大、岡本 光浩 "拠点間通信遅延を考慮した負荷分散方法" 2016年電子情報通信ソサイエティ大会、B-6-13 北野 雄大、岡本 光浩 "動的に変化する処理負荷と処理TATを考慮した負荷分散手法" 2017年電子情報通信総合大会、B-6-32

非特許文献３の方法では、処理サーバを高速サーバと低速サーバ（高遅延サーバ）の２種類に分け、本来（ラウンドロビン方式等で）低速サーバへ振り分けられる信号の処理を高速サーバに肩代わりさせる。しかし、複数の拠点に処理サーバが存在する分散システムにおいては、各拠点で通信遅延の影響度が異なることに起因して、高速とも低速ともいえない処理サーバ（以下、「中速サーバ」と呼ぶ場合がある）が少なからず存在する。非特許文献３の方法によれば、中速サーバを、高速サーバまたは低速サーバに片寄せすることになる。しかし、いずれに片寄せしても平均処理ＴＡＴが増大する可能性がある。

つまり、中速サーバを高速サーバとみなした場合、低速サーバへ振り分けられる信号の処理を肩代わりする処理サーバの数が相対的に多くなる。しかし、高速サーバよりも高遅延となる中速サーバが多くの信号を処理する傾向が強くなり、高速サーバの平均ＴＡＴが増大してしまう。その結果、分散システム全体の平均処理ＴＡＴが増大する可能性がある。

また、中速サーバを低速サーバとみなした場合、低速サーバへ振り分けられる信号の処理を肩代わりできる処理サーバの数が相対的に少なくなる。この場合、肩代わりできる信号の数が少なくなり、高速サーバの処理能力を十分に使い切ることができない。その結果、分散システム全体の平均処理ＴＡＴが増大する可能性がある。

このような背景に鑑みて、本発明は、拠点が複数存在する分散システムの平均処理ＴＡＴを低減させることを課題とする。

前記した課題を解決するため、請求項１に記載の発明は、複数の拠点に配置されている処理サーバに信号を振り分ける負荷分散装置であって、前記処理サーバの各々の処理ＴＡＴ（Turn Around Time）を測定する処理時間測定部と、前記測定した処理ＴＡＴを用いてグループ化することで、各グループの平均ＴＡＴが異なる少なくとも３以上のグループを作成し、前記作成したグループについて、第１のグループと、前記平均ＴＡＴが前記第１のグループの次に長い第２のグループとの組合せを決定し、前記第１のグループに属する処理サーバを高速サーバとし、前記第２のグループに属する処理サーバを低速サーバとするグループ化部と、前記高速サーバの負荷情報を取得する負荷情報取得部と、前記低速サーバの台数と、前記高速サーバの台数と、前記取得した負荷情報の最大値と、前記高速サーバの負荷変動を示す処理サーバの負荷変動率とに基づいて、所定の負荷制限値を超えない範囲で、前記低速サーバに振り分けるべき信号を前記高速サーバに振り分ける肩代わり信号数を、前記組合せごとに算出する信号数算出部と、前記組合せの各々で、前記算出した肩代わり信号数分を、前記低速サーバから前記高速サーバに振り分ける振分部と、を備える、ことを特徴とする。

また、請求項３に記載の発明は、複数の拠点に配置されている処理サーバに信号を振り分ける負荷分散装置における負荷分散方法であって、前記負荷分散装置は、前記処理サーバの各々の処理ＴＡＴを測定する処理時間測定ステップと、前記測定した処理ＴＡＴを用いてグループ化することで、各グループの平均ＴＡＴが異なる少なくとも３以上のグループを作成し、前記作成したグループについて、第１のグループと、前記平均ＴＡＴが前記第１のグループの次に長い第２のグループとの組合せを決定し、
前記第１のグループに属する処理サーバを高速サーバとし、前記第２のグループに属する処理サーバを低速サーバとするグループ化ステップと、前記高速サーバの負荷情報を取得する負荷情報取得ステップと、前記低速サーバの台数と、前記高速サーバの台数と、前記取得した負荷情報の最大値と、前記高速サーバの負荷変動を示す処理サーバの負荷変動率とに基づいて、所定の負荷制限値を超えない範囲で、前記低速サーバに振り分けるべき信号を前記高速サーバに振り分ける肩代わり信号数を、前記組合せごとに算出する信号数算出ステップと、前記組合せの各々で、前記算出した肩代わり信号数分を、前記低速サーバから前記高速サーバに振り分ける振分ステップと、を実行する、ことを特徴とする。

このようにすることで、平均ＴＡＴが異なる３以上のグループを用意することで、通信遅延の観点からは本来的に高速サーバとも低速サーバともいえない中速サーバを、高速サーバにも低速サーバにも扱うように規定することができる。その結果、低速サーバに振り分けられる信号を中速サーバに振り分けることもでき、また、中速サーバに振り分けられる信号を高速サーバに振り分けることもできる。
したがって、拠点が複数存在する分散システムの平均処理ＴＡＴを低減させることができる。

また、請求項２に記載の発明は、請求項１に記載の負荷分散装置であって、前記振分部は、前記処理サーバの各々に信号を振り分ける際、前記作成されたグループに属する処理サーバの台数に応じて決定される振り分け比率に従い、各グループに信号を振り分ける、ことを特徴とする。

また、請求項４に記載の発明は、請求項２に記載の負荷分散方法であって、前記作成されたグループに属する処理サーバの台数に応じて決定される振り分け比率に従い、各グループに信号を振り分ける、ことを特徴とする。

このようにすることで、各グループに属する処理サーバの台数に応じた振り分け比率を用いることで、各グループに属する処理サーバが処理する信号数の偏りを低減させることができる。

本発明によれば、拠点が複数存在する分散システムの平均処理ＴＡＴを低減させることができる。

本発明の概要の説明図であり、（ａ）は、分散システムの概略図、（ｂ）は、処理サーバのグループ化を示す図である。 本実施形態の負荷分散装置が適用される分散システムの構成図である。 グループ化フェーズを説明するための具体例を示す図であり、（ａ）がグループ化する前の処理サーバの状態、（ｂ）、（ｃ）がグループ化の途中状態、（ｄ）がグループ化の最終状態である。 振り分けフェーズを説明するための具体例を示す図であり、（ａ）がグループ化された各処理サーバの状態、（ｂ）がＧ１−Ｇ２での振り分けにおける肩代わり信号数の決定の説明図、（ｃ）がＧ２−Ｇ３での振り分けにおける肩代わり信号数の決定の説明図、（ｄ）がＧ３−Ｇ４での振り分けにおける肩代わり信号数の決定の説明図である。 信号の振り分けの例を示す表である。 信号の振り分け比率の決定に関する説明図である。 本実施形態の負荷分散装置の処理を示すフローチャートである。

以下、図面を参照して本発明を実施するための形態（以下、「本実施形態」という）について説明する。
≪概要≫
図１に示すように、拠点ごとに配置されているデータセンタＤＣａ〜ＤＣｄに処理サーバ２００−１〜２００−９を備えた分散システムを例にして本発明の概要を説明する。データセンタＤＣａに配置されている負荷分散装置１００は、処理サーバ２００−１〜２００−９の各々に信号を振り分ける。なお、説明の便宜上、負荷分散装置１００が配置されている拠点を、「自拠点」と呼ぶ場合がある。すでに説明した通り、負荷分散装置１００が配置される拠点と異なる拠点内にある処理サーバ２００−４〜２００−９への信号の振り分けには、地域や国をまたぐ拠点間遅延が生じる。

処理サーバ２００−１〜２００−９の性能にも起因するが、拠点間遅延のため、処理サーバ２００−１〜２００−９各々の処理ＴＡＴは異なっており、処理サーバ２００−１〜２００−９は、高速サーバ、中速サーバ、低速サーバに分類することができる。高速サーバは、処理ＴＡＴが短い処理サーバである。低速サーバは、処理ＴＡＴが長い処理サーバである。中速サーバは、処理ＴＡＴが、高速サーバよりも長く、中速サーバよりも短い処理サーバである。

本発明では、処理ＴＡＴが近い処理サーバをグループ化する。その結果、図１（ｂ）に示すように、グループＧＲ１〜ＧＲ３を形成することができる。グループＧＲ１は、処理ＴＡＴが短い高速の処理サーバ群（処理サーバ２００−１，２００−２，２００−３）である。グループＧＲ２は、処理ＴＡＴが中程度の中速の処理サーバ群（処理サーバ２００−４，２００−５，２００−７）である。グループＧＲ３は、処理ＴＡＴが長い低速の処理サーバ群（処理サーバ２００−６，２００−８，２００−９）である。

負荷分散装置１００は、隣り合うグループを、非特許文献３で説明される高速サーバ群および低速サーバ群に見立て、低速サーバ群の処理を高速サーバ群に肩代わりさせる。具体的には、グループＧＲ１，ＧＲ２が隣り合うグループであり、グループＧＲ１を高速サーバ群、グループＧＲ２を低速サーバ群と見立てる。負荷分散装置１００は、グループＧＲ２の処理サーバ（例えば、処理サーバ２００−５）への信号の振り分けを、グループＧＲ１の処理サーバ（例えば、処理サーバ２００−２）への信号の振り分けに切り替えて（符号ＡＲ１）、処理を肩代わりさせる。

また、グループＧＲ２，ＧＲ３が隣り合うグループであり、グループＧＲ２を高速サーバ群、グループＧＲ３を低速サーバ群と見立てる。負荷分散装置１００は、グループＧＲ３の処理サーバ（例えば、処理サーバ２００−９）への信号の振り分けを、グループＧＲ２の処理サーバ（例えば、処理サーバ２００−７）への信号の振り分けに切り替えて（符号ＡＲ２）、処理を肩代わりさせる。

上記によれば、従来のように中速サーバを高速サーバまたは低速サーバのいずれかに片寄せするのではなく、高速サーバにも低速サーバにも扱うことができるようにすることで、低速サーバから高速サーバへの処理の肩代わりを調節することができる。その結果、分散システム全体の平均処理ＴＡＴを低減させるように、処理の肩代わりを調節することができる。

≪構成≫
次に、負荷分散装置１００の構成について詳細に説明する。
図２に示すように、本実施形態の分散システムでは、例として、東京を拠点とするデータセンタＤＣ１と、ワシントンを拠点とするデータセンタＤＣ２と、北京を拠点とするデータセンタＤＣ３とが、ネットワークで通信可能に接続されているものとする。

データセンタＤＣ１には、負荷分散装置１００と、処理サーバ２０１〜２０４とが配置されている。負荷分散装置１００および処理サーバ２０１〜２０４は、ネットワークで通信可能に接続されている。
データセンタＤＣ２には、処理サーバ２０５〜２０８が配置されている。処理サーバ２０５〜２０８は、ネットワークで通信可能に接続されている。
データセンタＤＣ３には、処理サーバ２０９〜２１２が配置されている。処理サーバ２０９〜２１２は、ネットワークで通信可能に接続されている。

データセンタＤＣ１に対して、クライアント３１〜３４が通信可能に接続されている。クライアント３１〜３４は、ユーザの端末や対向システムであり、処理サーバ２０１〜２１２に対して信号を送信し、アプリケーションの処理を要求する。

負荷分散装置１００は、処理サーバ２０１〜２１２に対して、クライアント３１〜３４からの要求信号（リクエスト）の振り分けをする。負荷分散装置１００は、クライアント３１〜３４からの要求を受け、データセンタＤＣ１〜ＤＣ３の処理サーバ２０１〜２１２のうちの１台を選択し、その選択した処理サーバに処理を依頼する。選択された処理サーバは、クライアント３１〜３４からのアプリケーションの要求を処理する。

なお、負荷分散装置１００は、分散システムで動作するプログラムの一例としての分散処理ミドルウェアであってもよく、分散システム内の複数台の処理サーバ２０１〜２１２に処理を振り分けるロードバランサのいずれでもよい。
また、図２の分散システムを構成する各装置の台数は、図１に例示した台数に限定されず、任意の台数としてもよい。拠点の数も、図１に例示した数に限定されず、任意の数としてもよい。

負荷分散装置１００の詳細について説明する。
負荷分散装置１００は、処理サーバの処理負荷や台数、通信遅延を考慮しながら、できるだけ通信遅延が小さい処理サーバへ信号を振り分ける。負荷分散装置１００は、各処理サーバの処理ＴＡＴを測定する処理時間測定部１１２としての機能を有する。なお、処理ＴＡＴには、負荷分散装置１００から処理サーバに信号を送信するのに要する時間（通信遅延時間）と処理サーバによる信号処理時間が含まれる。
図２に示すように、負荷分散装置１００は、肩代わり信号数算出部１１１（信号数算出部）を有する振分部１１０と、処理時間測定部１１２と、グループ化部１１３と、サーバ情報取得部１２０（負荷情報取得部）と、情報格納部１３０と、を備える。

<肩代わり信号数算出部１１１>
肩代わり信号数算出部１１１は、本来低速サーバに振り分ける信号を高速サーバに振り分けるとしたときの信号数を肩代わり信号数Ｓとして算出する。肩代わり信号数Ｓの算出は、先述した隣り合うグループ間で行われる。肩代わり信号数Ｓの算出の手順は、後記する、グループ化フェーズおよび振り分けフェーズに分けることができる。

<振分部１１０>
振分部１１０は、肩代わり信号数算出部１１１によって算出された肩代わり信号数Ｓの値に従って、処理サーバへ信号の振り分けを行う。

<サーバ情報取得部１２０>
サーバ情報取得部１２０は、各処理サーバの応答時間（処理ＴＡＴ）を取得する。また、サーバ情報取得部１２０は、各処理サーバの負荷情報（例えば、ＣＰＵ使用率、メモリ使用率等がある。本実施形態では、ＣＰＵ使用率を例にとる）を定期的に収集（取得）する。サーバ情報取得部１２０は、収集したＣＰＵ使用率（負荷情報）を情報格納部１３０に格納するとともに、振分部１１０に通知する。

<情報格納部１３０>
情報格納部１３０は、例えば、各処理サーバの応答時間（処理ＴＡＴ）、および各処理サーバのＣＰＵ使用率を格納する。また、情報格納部１３０は、肩代わり信号数算出部１１１による演算処理の出力結果を格納する。演算処理の出力結果には、例えば、肩代わり信号数Ｓや、後記する、肩代わり信号数Ｓごとの高速サーバの負荷変動率Ａ，平均信号処理ＴＡＴ変動率Ｂ，スコアＣが含まれる。また、情報格納部１３０は、オペレータなどから指定された値、例えば、ＣＰＵ閾値や、後記する差分ＴＡＴ閾値を格納する。

〔グループ化フェーズ〕
負荷分散装置１００は、各処理サーバの処理ＴＡＴを測定し、処理ＴＡＴが近い処理サーバをグループ化するグループ化部１１３としての機能を有する。処理サーバのグループ化は、以下のグループ化アルゴリズムの手順［１ａ］〜［５ａ］に従って実現される。

まず、負荷分散装置１００は、情報格納部１３０に格納されている差分ＴＡＴ閾値を設定する（手順［１ａ］）。「差分ＴＡＴ閾値」とは、グループに属する処理サーバ群の処理ＴＡＴの平均値である平均処理ＴＡＴを用いた、グループ間の平均処理ＴＡＴの最低差分である。

拠点をまたぐとＴＡＴは増大すると想定されるので、拠点間遅延分を差分ＴＡＴ閾値に設定するという考えが望ましい。よって、差分ＴＡＴ閾値を決定する方法としては、例えば、負荷分散装置１００から各拠点の代表サーバ（拠点ごとに決めた代表の処理サーバ）へテスト信号を送信して代表サーバの処理ＴＡＴを取得し、他拠点（自拠点以外の拠点）に配置されている代表サーバの処理ＴＡＴのうちの最低値から、自拠点の代表サーバの処理ＴＡＴを引いた値を差分ＴＡＴ閾値にする、という方法がある。

図３（ａ）には、差分ＴＡＴ閾値の入力欄に「４」が、相対値として入力されていることが示されている。差分ＴＡＴ閾値は、例えば、オペレータが指定することができ、情報格納部１３０に格納される。

次に、負荷分散装置１００のサーバ情報取得部１２０が各処理サーバへテスト信号を送信し、各処理サーバの処理ＴＡＴを取得する（手順［２ａ］）。テスト信号は、例えば、pingとすることができるが、これに限定されない。

次に、負荷分散装置１００は、取得した処理ＴＡＴが短い順に処理サーバをソートする（手順［３ａ］）。

図３（ａ）に示すように、サーバ名「ａ」〜「ｌ」がそれぞれ付された１２台の処理サーバを、分散システムを構成する処理サーバとした場合について説明する。サーバ情報取得部１２０は、処理サーバａ〜ｆの処理ＴＡＴ（図３では、「ＴＡＴ」と表記）を取得する。取得された処理ＴＡＴは、図３（ａ）中のＴＡＴ入力欄に入力される。入力された値は、図３（ａ）に示す通りであったとする。ＴＡＴの数値は相対的なものであり、数値が大きいほどＴＡＴが増大するものとして説明する。手順［３ａ］によって、処理サーバａ〜ｆは、ＴＡＴの昇順にソートされている。

次に、負荷分散装置１００のグループ化部１１３は、各処理サーバ間の処理ＴＡＴの差分を算出し、算出した差分が最低値をとる処理サーバ同士をグループ化する（手順［４ａ］）。図３（ａ）に示すように、負荷分散装置１００は、手順［３ａ］でソートされた処理サーバ群において、隣り合う処理サーバ間のＴＡＴの差分を求める。求められた差分は、図３（ａ）中の差分入力欄に入力される。入力された値は、図３（ａ）に示す通りである。

また、図３（ａ）に示す通り、差分の最低値は「０」であり、差分ＴＡＴ閾値「４」を下回るので、手順［４ａ］にて、差分が「０」となる処理サーバ同士をグループ化する。図３（ａ）では、処理サーバａ，ｂがグループ化され、また、処理サーバｅ，ｆがグループ化される。図３（ａ）に対して、処理サーバ同士のグループ化をしたときの結果が図３（ｂ）に示される。図３（ｂ）には、図３（ａ）のサーバ名「ａ」〜「ｌ」に対して、手順［４ａ］のグループ化をしたときのグループ名が示されている。処理サーバａ，ｂをグループ化したときのグループ名は「ａｂ」、処理サーバｅ，ｆをグループ化したときのグループ名は「ｅｆ」とする。なお、便宜上、グループ化されなかった各処理サーバｃ，ｄ，ｇ〜ｌは、単一の要素からなるグループを形成するとする。このとき、グループ名は、サーバ名と同じとする。

図３（ｂ）に示す通り、負荷分散装置１００は、処理サーバのグループに対して、ＴＡＴを算出する。ここで、処理サーバのグループのＴＡＴは、２値の平均値とする。図３（ｂ）では、グループ名「ａｂ」のグループのＴＡＴは、処理サーバａの取得したＴＡＴ「１」と処理サーバｂの取得したＴＡＴ「１」との平均値「１」であり、図３（ｂ）中のＴＡＴ入力欄に入力される。グループ名「ｅｆ」のグループのＴＡＴは、処理サーバｅの取得したＴＡＴ「８」と処理サーバｆの取得したＴＡＴ「８」との平均値「８」であり、図３（ｂ）中のＴＡＴ入力欄に入力される。

最後に、負荷分散装置１００のグループ化部１１３は、手順［４ａ］を、差分の最低値が、差分ＴＡＴ閾値以上になるまで繰り返す（手順［５ａ］）。図３（ｂ）において、隣り合うグループ間のＴＡＴの差分を求める。求められた差分は、図３（ｂ）中の差分入力欄に入力される。入力された値は、図３（ｂ）に示す通りである。

また、図３（ｂ）に示す通り、差分の最低値は「１」であり、差分ＴＡＴ閾値「４」を下回るので、差分が「１」となるグループ同士をグループ化する。図３（ｂ）では、グループａｂ，ｃがグループ化され（ｃとｄとのグループ化はなくなる）、グループｅｆ，ｇがグループ化され（ｇとｈとのグループ化はなくなる）、グループｉ，ｊがグループ化され、グループｋ，ｌがグループ化される。

図３（ｂ）に対して、グループ同士をさらにグループ化をしたときの結果が図３（ｃ）に示される。図３（ｃ）には、図３（ｂ）のグループ名「ａｂ」、「ｃ」、「ｄ」、「ｅｆ」、「ｇ」〜「ｌ」に対して、さらにグループ化をしたときのグループ名が示されている。グループａｂ，ｃをグループ化したときのグループ名は「ａｂｃ」、グループｅｆ，ｇをグループ化したときのグループ名は「ｅｆｇ」、グループｉ，ｊをグループ化したときのグループ名は「ｉｊ」、グループｋ，ｌをグループ化したときのグループ名は「ｋｌ」とする。

図３（ｃ）に示す通り、負荷分散装置１００は、さらにグループ化されたグループに対して、ＴＡＴを算出する。ここで、グループのＴＡＴは、先述したとおり、２値の平均値とし、図３（ｃ）中のＴＡＴ入力欄に示された通りである。図３（ｃ）において、隣り合うグループ間のＴＡＴの差分を求める。求められた差分は、図３（ｃ）中の差分入力欄に入力される。入力された値は、図３（ｃ）に示す通りである。

図３（ｃ）に示す通り、差分の最低値は「１．５」であり、差分ＴＡＴ閾値「４」を下回るので、差分が「１．５」となるグループ同士をグループ化する。図３（ｃ）では、グループａｂｃ，ｄがグループ化され、グループｅｆｇ，ｈがグループ化される。

図３（ｃ）に対して、グループ同士をさらにグループ化をしたときの結果が図３（ｄ）に示される。図３（ｄ）には、図３（ｃ）のグループ名「ａｂｃ」、「ｄ」、「ｅｆｇ」、「ｈ」，「ｉｊ」，「ｋｌ」に対して、さらにグループ化をしたときのグループ名が示されている。グループａｂｃ，ｄをグループ化したときのグループ名は「ａｂｃｄ」、グループｅｆｇ，ｈをグループ化したときのグループ名は「ｅｆｇｈ」とする。

図３（ｄ）に示す通り、負荷分散装置１００は、さらにグループ化されたグループに対して、ＴＡＴを算出する。ここで、グループのＴＡＴは、先述したとおり、２値の平均値とし、図３（ｄ）中のＴＡＴ入力欄に示された通りである。図３（ｄ）において、隣り合うグループ間のＴＡＴの差分を求める。求められた差分は、図３（ｄ）中の差分入力欄に入力される。入力された値は、図３（ｄ）に示す通りである。

図３（ｄ）に示す通り、差分の最低値は「４．２５」であり、差分ＴＡＴ閾値「４」以上となるので、負荷分散装置１００は、手順［５ａ］を終了する。結果として、グループ名「ａｂｃｄ」、「ｅｆｇｈ」、「ｉｊ」、「ｋｌ」となる、処理ＴＡＴが近い処理サーバが集まった４種類のグループが得られる。

〔振り分けフェーズ〕
負荷分散装置１００は、平均処理ＴＡＴが近いグループ同士を、隣り合うグループとして扱い、高速サーバ群／低速サーバ群と見立てて、本来低速サーバが処理すべき信号を高速サーバに振り分け、処理を肩代わりさせる。高速サーバへの処理の肩代わりは、以下の振り分けアルゴリズムの手順［１ｂ］〜［５ｂ］に従って実現される。

まず、負荷分散装置１００は、情報格納部１３０に格納されているＣＰＵ閾値を設定する（手順［１ｂ］）。「ＣＰＵ閾値」とは、処理サーバのＣＰＵ使用率の上限値（負荷制限値）である。図４（ａ）には、ＣＰＵ閾値の入力欄に「８０」が、相対値（％）として入力されていることが示されている。ＣＰＵ閾値は、例えば、オペレータが指定することができ、情報格納部１３０に格納される。

次に、負荷分散装置１００のサーバ情報取得部１２０が、各処理サーバのＣＰＵ使用率を取得する（手順［２ｂ］）。ただし、グループの平均ＴＡＴが最も長いグループに属する処理サーバ（図３に示す処理サーバｋ、ｌが該当）のＣＰＵ使用率については、取得しなくてもよいし、取得してもよい。本実施形態では、取得しないとして説明する。「グループの平均ＴＡＴ」とは、グループに属する各処理サーバの処理ＴＡＴの加算平均である。

次に、負荷分散装置１００は、グループの平均ＴＡＴが短い順にグループをソートする（手順［３ｂ］）。

図４（ａ）に示すように、グループ化された１２台の処理サーバａ〜ｌ（図３参照）について説明する。サーバ情報取得部１２０は、処理サーバａ〜ｊのＣＰＵ使用率（図４では、「ＣＰＵ使用率」と表記）を取得する。取得されたＣＰＵ使用率は、図４（ａ）中のＣＰＵ使用率入力欄に入力される。入力された値は、図４（ａ）に示す通りであったとする。ＣＰＵ使用率の数値は相対的なものであり、数値が大きいほどＣＰＵ使用率が増大するものとして説明する。

図４（ａ）に示すように、グループ化フェーズでグループ化された処理サーバａ〜ｄのグループ、処理サーバｅ〜ｈのグループ、処理サーバｉ，ｊのグループ、処理サーバｋ，ｌのグループの各々にグループ名Ｇ１〜Ｇ４を付す。グループＧ１〜Ｇ４の平均ＴＡＴは、各グループに属する処理サーバの処理ＴＡＴの加算平均として算出したものであり、図４（ａ）中の「グループの平均ＴＡＴ」入力欄に入力されている。手順［３ｂ］に示すソートにより、グループＧ１〜Ｇ４は、グループの平均ＴＡＴの昇順にソートされている。

次に、負荷分散装置１００の肩代わり信号数算出部１１１は、隣り合うグループ同士を高速サーバ群／低速サーバ群と見立てて、肩代わり信号数ＳごとのスコアＣを算出する（手順［４ｂ］）。図４に示す例において、隣り合うグループとは、（Ｇ１，Ｇ２）と、（Ｇ２，Ｇ３）と、（Ｇ３，Ｇ４）の３種類であり、左成分が高速サーバ群（第１のグループ）、右成分が低速サーバ群（第２のグループ）となる。

隣り合うグループについて、高速サーバの台数をＮｍ、低速サーバの台数をＮｎ、ラウンドロビン方式に従うと本来低速サーバで処理される信号を高速サーバで処理する１ラウンドあたりの肩代わり信号数をＳ（０≦Ｓ≦Ｎｎ）とすると、高速サーバの負荷変動率Ａは、次式（１）で示される。

高速サーバの負荷変動率Ａ＝（Ｎｍ＋Ｓ）／Ｎｍ …（１）

また、１台の高速サーバで処理した場合の処理ＴＡＴを１としたとき、１台の低速サーバで処理した場合の処理ＴＡＴを遅延倍率Ｄとすると、１ラウンドにおける信号処理ＴＡＴ変動率Ｂは、次式（２）で示される。

信号処理ＴＡＴ変動率Ｂ
＝（（Ｎｍ＋Ｓ）＋Ｄ×（Ｎｎ−Ｓ））／（Ｎｍ＋Ｄ×Ｎｎ） …（２）

よって、隣り合うグループの高速サーバ群／低速サーバ群を対象にした場合、１ラウンドにおける平均信号処理ＴＡＴ変動率Ｂは（（Ｎｍ＋Ｓ）＋Ｄ×（Ｎｎ−Ｓ））／（Ｎｍ＋Ｄ×Ｎｎ）倍とする。遅延倍率Ｄは、低速サーバの処理ＴＡＴの平均を高速サーバの処理ＴＡＴの平均で割った値で近似することができる。

また、高速サーバの負荷変動率Ａと平均信号処理ＴＡＴ変動率Ｂを用いて算出される評価関数としてスコアＣを算出する。例えば、スコアＣの一例として、高速サーバの負荷変動率Ａと平均信号処理ＴＡＴ変動率Ｂから算出される減少関数を評価関数として用いることができる。この減少関数は、高速サーバの負荷変動率Ａまたは平均信号処理ＴＡＴ変動率Ｂが減少すると、スコアＣが上昇する関数（例えば（１／Ａ＋１／Ｂ））である。

図４（ｂ）〜（ｄ）には、隣り合うグループ（Ｇ１，Ｇ２）、（Ｇ２，Ｇ３）、（Ｇ３，Ｇ４）に関する上記の計算結果がそれぞれ、Ｇ１−Ｇ２での振り分け、Ｇ２−Ｇ３での振り分け、Ｇ３−Ｇ４での振り分けとして示されている。

次に、負荷分散装置１００の振分部１１０は、高速サーバへの振り分けを行う（手順［５ｂ］）。この振り分けは、高速サーバ群の中で最大のＣＰＵ使用率と、高速サーバの負荷変動率Ａとを掛け合わせても、手順［１ｂ］で設定したＣＰＵ閾値を超えない範囲で最大のスコアＣをとる肩代わり信号数Ｓの値で行われる。

隣り合うグループ（Ｇ１，Ｇ２）に関しては、図４（ｂ）に示すように、低速サーバとなるグループＧ２に属する処理サーバの数Ｎｎが４であるため、肩代わり信号数Ｓは０，１，２，３，４のいずれかの値をとることができる。このとき、最大のスコアＣ＝３．５０をとる肩代わり信号数Ｓ＝４の場合、高速サーバ群（つまり、グループＧ１）の中で最大のＣＰＵ使用率は、サーバｄの「４５」であり、肩代わり信号数Ｓ＝４における高速サーバの負荷変動率Ａ＝２．００と掛け合わせると、９０．００となり、ＣＰＵ閾値＝８０を超える（ＮＧ）。よって、肩代わり信号数Ｓ＝４は、採用されない。

一方、２番目に最大のスコアＣ＝２．５７をとる肩代わり信号数Ｓ＝３の場合、高速サーバ群の中で最大のＣＰＵ使用率＝４５と、肩代わり信号数Ｓ＝３における高速サーバの負荷変動率Ａ＝１．７５と掛け合わせると、７８．７５となり、ＣＰＵ閾値＝８０を超えない（ＯＫ）。よって、肩代わり信号数Ｓ＝３が採用され、Ｓ＝３で信号が振り分けられる。つまり、負荷分散装置１００の振分部１１０は、は、グループＧ２の低速サーバのいずれかに振り分ける予定の３つの信号を、グループＧ１の高速サーバのいずれかに振り分ける。

隣り合うグループ（Ｇ２，Ｇ３）に関しては、図４（ｃ）に示すように、低速サーバとなるグループＧ３に属する処理サーバの数Ｎｎが２であるため、肩代わり信号数Ｓは０，１，２のいずれかの値をとることができる。このとき、最大のスコアＣ＝２．３６をとる肩代わり信号数Ｓ＝２の場合、高速サーバ群（つまり、グループＧ２）の中で最大のＣＰＵ使用率は、サーバｅの「４４」であり、肩代わり信号数Ｓ＝２における高速サーバの負荷変動率Ａ＝１．５０と掛け合わせると、６６．００となり、ＣＰＵ閾値＝８０を超えない（ＯＫ）。よって、肩代わり信号数Ｓ＝２が採用され、Ｓ＝２で信号が振り分けられる。つまり、負荷分散装置１００の振分部１１０は、は、グループＧ３の低速サーバのいずれかに振り分ける予定の２つの信号を、グループＧ２の高速サーバのいずれかに振り分ける。

隣り合うグループ（Ｇ３，Ｇ４）に関しては、図４（ｄ）に示すように、低速サーバとなるグループＧ４に属する処理サーバの数Ｎｎが２であるため、肩代わり信号数Ｓは０，１，２のいずれかの値をとることができる。このとき、最大のスコアＣ＝１．７２をとる肩代わり信号数Ｓ＝２の場合、高速サーバ群（つまり、グループＧ３）の中で最大のＣＰＵ使用率は、サーバｊの「２７」であり、肩代わり信号数Ｓ＝２における高速サーバの負荷変動率Ａ＝２．００と掛け合わせると、５４．００となり、ＣＰＵ閾値＝８０を超えない（ＯＫ）。よって、肩代わり信号数Ｓ＝２が採用され、Ｓ＝２で信号が振り分けられる。つまり、負荷分散装置１００の振分部１１０は、グループＧ４の低速サーバのいずれかに振り分ける予定の２つの信号を、グループＧ３の高速サーバのいずれかに振り分ける。

図４（ｂ）〜（ｄ）に示す、Ｇ１−Ｇ２での振り分け、Ｇ２−Ｇ３での振り分け、Ｇ３−Ｇ４での振り分けは、任意の順番で行うことができる。

図３のグループ化フェーズ、および、図４の振り分けフェーズに従った信号の振り分けの例を図５に示す。この振り分けは、ラウンドロビン方式に従う。図５の表の縦軸は処理サーバによってシーケンシャル処理される信号シーケンス番号１〜２０を示し、横軸は、グループＧ１〜Ｇ４に属する処理サーバａ〜ｌを示す。図５において、実線の白丸（○印）は信号が該当処理サーバに振り分けられることを示している。例えば、図５の信号シーケンス番号１の信号と処理サーバａとが交差する位置の実線の白丸（○印）は、信号シーケンス番号１の信号が処理サーバａに振り分けられることを示している。また、図５において、「肩」印は、本来低速サーバに振り分けられる信号が高速サーバに振り分けられるように肩代わりされ、実際には処理されなかったことを示している。例えば、図５の信号シーケンス番号５の信号と処理サーバｅとが交差する位置の実線の「肩」印は、本来処理サーバｅに振り分けられる信号シーケンス番号５の信号が処理サーバａに振り分けられるように肩代わりされ、処理サーバｅが処理しなかったことを示している。

Ｇ１−Ｇ２での振り分けに関しては、肩代わり信号数Ｓ＝３であるため、例えば、信号シーケンス番号５〜７の信号が、グループＧ２の処理サーバｅ〜ｇではなく、グループＧ１の処理サーバａ〜ｃに振り分けられる。
Ｇ２−Ｇ３での振り分けに関しては、肩代わり信号数Ｓ＝２であるため、例えば、信号シーケンス番号１３，１４の信号が、グループＧ３の処理サーバｉ，ｊではなく、グループＧ２の処理サーバｅ，ｆに振り分けられる。
Ｇ３−Ｇ４での振り分けに関しては、肩代わり信号数Ｓ＝２であるため、例えば、信号シーケンス番号１７，１８の信号が、グループＧ４の処理サーバｋ，ｌではなく、グループＧ３の処理サーバｉ，ｊに振り分けられる。

〔信号の振り分け比率〕
図３に示すグループ化フェーズで、高速サーバ群／低速サーバ群の観点で、処理サーバをグループ化し、図４に示す振り分けフェーズで、高速サーバへの肩代わりを伴う信号の振り分けをした場合、各グループで処理する（捌く）信号数に偏りが生じる。そこで、各グループで処理する信号数が偏らないように、各グループに属する処理サーバ台数に応じて、信号の振り分け比率を決定することが好ましい。

図６に示すように、Ｇ１−Ｇ２での振り分け、Ｇ２−Ｇ３での振り分け、Ｇ３−Ｇ４での振り分けの各々について、信号の振り分け比率を決定する。図６の表中、「サーバ台数」の項目には、該当の隣り合うグループに属する処理サーバの台数の総和数が登録される。図６の表中、「実際に捌くべき量」の項目には、サーバ台数に基づいて、該当の隣り合うグループに属する処理サーバが捌くべき信号数の相対値が登録される。

グループＧ２，Ｇ３については、振り分けが２度行われるが、グループの平均ＴＡＴが最も小さいグループＧ１と、グループの平均ＴＡＴが最も大きいグループＧ４については、振り分けが１度しか行われない。このため、グループＧ１，Ｇ４については、捌くべき信号数を増やすように制御する。具体的には、グループＧ１の処理サーバの台数＝４を２倍にして８とし、グループＧ２の処理サーバの台数＝４と足し合わせた値（４×２＋４＝１２）を、Ｇ１−Ｇ２での振り分けで実際に捌くべき量とする。また、グループＧ４の処理サーバの台数＝２を２倍にして４とし、グループＧ３の処理サーバの台数＝２と足し合わせた値（２＋２×２＝６）を、Ｇ３−Ｇ４での振り分けで実際に捌くべき量とする。Ｇ２−Ｇ３での振り分けについては、特に何もせず、グループＧ２，Ｇ３のサーバ台数の和（４＋２＝６）を、Ｇ２−Ｇ３での振り分けで実際に捌くべき量とする。

図６の表中、「比率」の項目には、実際に捌くべき量を、実際に捌くべき量の合計で除算した値が信号の振り分け比率として登録される。Ｇ１−Ｇ２での振り分け、Ｇ２−Ｇ３での振り分け、Ｇ３−Ｇ４での振り分け各々の、信号の振り分け比率は、５０％（＝１２／（１２＋６＋６））、２５％（＝６／（１２＋６＋６））、２５％（＝６／（１２＋６＋６））となる。

負荷分散装置１００の振分部１１０は、決定した振り分け比率に従い、各グループに信号を振り分ける。例えば、１００信号を捌く場合、５０信号は、隣り合うグループ（Ｇ１，Ｇ２）で振り分けされ、２５信号は、隣り合うグループ（Ｇ２，Ｇ３）で振り分けされ、２５信号は、隣り合うグループ（Ｇ３，Ｇ４）で振り分けされる。

≪処理≫
本実施形態の負荷分散装置１００の処理について説明する。
図７に示すように、まず、負荷分散装置１００は、差分ＴＡＴ閾値およびＣＰＵ閾値を設定する（ステップＳ１）。ステップＳ１は、グループ化フェーズの手順［１ａ］、および、振り分けフェーズの手順［１ｂ］に相当する。

次に、負荷分散装置１００は、すべての処理サーバの処理ＴＡＴを取得する（ステップＳ２）。ステップＳ２は、グループ化フェーズの手順［２ａ］に相当する。

次に、負荷分散装置１００は、差分ＴＡＴ閾値を用いて、処理サーバのグループ化を行う（ステップＳ３）。ステップＳ３は、グループ化フェーズの手順［３ａ］〜手順［５ａ］に相当する。

次に、負荷分散装置１００は、処理サーバのＣＰＵ使用率を取得する（ステップＳ４）。ただし、グループの平均ＴＡＴが最も大きいグループに属する処理サーバについては、ＣＰＵ使用率を取得しない。ステップＳ４は、振り分けフェーズの手順［２ｂ］に相当する。

次に、負荷分散装置１００は、各グループについて、肩代わり信号数ＳごとのスコアＣを算出する（ステップＳ５）。ステップＳ５は、振り分けフェーズの手順［３ｂ］，手順［４ｂ］に相当する。

次に、負荷分散装置１００は、各グループについて、ＣＰＵ閾値を超えない範囲で最大のスコアＣをとる肩代わり信号数Ｓに基づく信号の振り分けを行う（ステップＳ６）。ステップＳ６は、振り分けフェーズの手順［５ｂ］に相当する。ステップＳ６の振り分けの際、ラウンドロビン方式の代わりに、信号の振り分け比率（図６参照）に従って、各処理サーバに振り分けられる信号数が決められた後、肩代わり信号数Ｓによる肩代わりの処理がなされる。

以降、負荷分散装置１００は、クライアントから取得する信号に対して、定期的に、または、所定のタイミングで、ステップＳ２〜Ｓ６を繰り返す。

本実施形態によれば、平均ＴＡＴが異なる３以上のグループを用意することで、通信遅延の観点からは本来的に高速サーバとも低速サーバともいえない中速サーバを、高速サーバにも低速サーバにも扱うように規定することができる。その結果、低速サーバに振り分けられる信号を中速サーバに振り分けることもでき、また、中速サーバに振り分けられる信号を高速サーバに振り分けることもできる。
したがって、拠点が複数存在する分散システムの平均処理ＴＡＴを低減させることができる。
また、各グループに属する処理サーバの台数に応じた振り分け比率を用いることで、各グループに属する処理サーバが処理する信号数の偏りを低減させることができる。

≪その他≫
以上、本発明の実施形態について説明したが、本発明は前記実施形態に限定されず、本発明の要旨を逸脱しない範囲で適宜変更可能である。例えば、本実施形態では、グループの平均ＴＡＴが近い隣り合うグループ同士を高速サーバ群／低速サーバ群として信号の処理の肩代わりをした。しかし、グループの平均ＴＡＴが遠く隣り合っていないグループ同士を高速サーバ群／低速サーバ群として扱ってもよい。

また、上記各実施形態において説明した各処理のうち、自動的に行われるものとして説明した処理の全部または一部を手動的に行うこともでき、あるいは、手動的に行われるものとして説明した処理の全部または一部を公知の方法で自動的に行うこともできる。この他、上述文書中や図面中に示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。

また、上記の各構成、機能、処理部、処理手段等は、それらの一部または全部を、例えば集積回路で設計する等によりハードウェアで実現してもよい。また、上記の各構成、機能等は、プロセッサがそれぞれの機能を実現するプログラムを解釈し、実行するためのソフトウェアで実現してもよい。各機能を実現するプログラム、テーブル、ファイル等の情報は、メモリや、ハードディスク、ＳＳＤ（Solid State Drive）等の記録装置、または、ＩＣ（Integrated Circuit）カード、ＳＤ（Secure Digital）カード、光ディスク等の記録媒体に保持することができる。また、本明細書において、時系列的な処理を記述する処理ステップは、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理（例えば、並列処理あるいはオブジェクトによる処理）をも含むものである。

本実施形態で説明した種々の技術を適宜組み合わせた技術を実現することもできる。
本実施形態で説明したソフトウェアをハードウェアとして実現することもでき、ハードウェアをソフトウェアとして実現することもできる。
その他、ハードウェア、ソフトウェア、フローチャートなどについて、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。

１００ 負荷分散装置
１１０ 振分部
１１１ 肩代わり信号数算出部
１１２ 処理時間測定部
１１３ グループ化部
１２０ サーバ情報取得部
１３０ 情報格納部
２０１〜２１２ 処理サーバ

Claims (4)

1. 複数の拠点に配置されている処理サーバに信号を振り分ける負荷分散装置であって、
   前記処理サーバの各々の処理ＴＡＴ（Turn Around Time）を測定する処理時間測定部と、
   前記測定した処理ＴＡＴを用いてグループ化することで、各グループの平均ＴＡＴが異なる少なくとも３以上のグループを作成し、
   前記作成したグループについて、第１のグループと、前記平均ＴＡＴが前記第１のグループの次に長い第２のグループとの組合せを決定し、
   前記第１のグループに属する処理サーバを高速サーバとし、前記第２のグループに属する処理サーバを低速サーバとするグループ化部と、
   前記高速サーバの負荷情報を取得する負荷情報取得部と、
   前記低速サーバの台数と、前記高速サーバの台数と、前記取得した負荷情報の最大値と、前記高速サーバの負荷変動を示す処理サーバの負荷変動率とに基づいて、所定の負荷制限値を超えない範囲で、前記低速サーバに振り分けるべき信号を前記高速サーバに振り分ける肩代わり信号数を、前記組合せごとに算出する信号数算出部と、
   前記組合せの各々で、前記算出した肩代わり信号数分を、前記低速サーバから前記高速サーバに振り分ける振分部と、を備える、
   ことを特徴とする負荷分散装置。
2. 前記振分部は、前記処理サーバの各々に信号を振り分ける際、
   前記作成されたグループに属する処理サーバの台数に応じて決定される振り分け比率に従い、各グループに信号を振り分ける、
   ことを特徴とする請求項１に記載の負荷分散装置。
3. 複数の拠点に配置されている処理サーバに信号を振り分ける負荷分散装置における負荷分散方法であって、
   前記負荷分散装置は、
   前記処理サーバの各々の処理ＴＡＴを測定する処理時間測定ステップと、
   前記測定した処理ＴＡＴを用いてグループ化することで、各グループの平均ＴＡＴが異なる少なくとも３以上のグループを作成し、
   前記作成したグループについて、第１のグループと、前記平均ＴＡＴが前記第１のグループの次に長い第２のグループとの組合せを決定し、
   前記第１のグループに属する処理サーバを高速サーバとし、前記第２のグループに属する処理サーバを低速サーバとするグループ化ステップと、
   前記高速サーバの負荷情報を取得する負荷情報取得ステップと、
   前記低速サーバの台数と、前記高速サーバの台数と、前記取得した負荷情報の最大値と、前記高速サーバの負荷変動を示す処理サーバの負荷変動率とに基づいて、所定の負荷制限値を超えない範囲で、前記低速サーバに振り分けるべき信号を前記高速サーバに振り分ける肩代わり信号数を、前記組合せごとに算出する信号数算出ステップと、
   前記組合せの各々で、前記算出した肩代わり信号数分を、前記低速サーバから前記高速サーバに振り分ける振分ステップと、を実行する、
   ことを特徴とする負荷分散方法。
4. 前記負荷分散装置は、前記処理サーバの各々に信号を振り分ける際、
   前記作成されたグループに属する処理サーバの台数に応じて決定される振り分け比率に従い、各グループに信号を振り分ける、
   ことを特徴とする請求項３に記載の負荷分散方法。

Images