(57)【要約】【課題】  複数工程を有する処理を行うサーバにおいて、過剰に処理の実行を要求された場合における処理性能の維持を実現する。【解決手段】  処理単位のスケジューリングではなく、より粒度の細かい工程単位のスケジューリングによって処理性能の維持を試みる。すなわち、（１）複数工程を有する処理では、少ない工程数で完了する可能性が高い処理を優先処理する、さらに、（２）複数工程からなる処理が単一工程からなる処理より重要である場合は、複数工程からなる処理を優先処理する。【選択図】  図１
2007233559.tif 000002
【特許請求の範囲】
【請求項１】
サーバとクライアントとの間の複数工程からなる処理における、並行して実行される処理の実行制御をする実行制御装置であって、
処理の完了までの工程数を進行度として評価する進行度評価手段と、
当該進行度に基づき処理のスケジューリングを行うスケジューリング手段と
を備えたことを特徴とする実行制御装置。
【請求項２】
前記処理は、各工程がクライアントからのリクエストの受信によって起動されるページ処理からなるセッション処理である請求項１記載の実行制御装置。
【請求項３】
前記スケジューリング手段は、前記サーバの負荷が所定の値を超えないようにスケジューリングを行う手段を備えた請求項１または２記載の実行制御装置。
【請求項４】
前記進行度評価手段は、予め一つのセッション処理において使用される複数のＵＲＬの情報を保持し、クライアントから受信したリクエストに含まれるＵＲＬの情報と前記登録されているＵＲＬの情報との一致を判定することにより当該セッション処理の進行度を求める手段を備えた請求項２記載の実行制御装置。
【請求項５】
前記進行度評価手段は、予め一つのセッション処理においてアクセスされるページに対応した当該セッション処理の進行状態の情報を保持し、クライアントから受信したリクエストに含まれるページアクセス要求に基づき当該セッション処理の進行状態を認識することにより当該セッション処理の進行度を求める手段を備えた請求項２記載の実行制御装置。
【請求項６】
前記進行度評価手段は、処理が既に実行を完了している工程数を認識することによって、当該処理の進行度を求める手段を備えた請求項１または２記載の実行制御装置。
【請求項７】
前記進行度評価手段は、処理の工程が、当該処理における初期工程にあるか、初期工程より後の工程にあるかに基づき当該処理の進行度を求める手段を備えた請求項１または２記載の実行制御装置。
【請求項８】
一つのセッション処理の進行度および当該セッション処理を実行中のサーバの負荷に応じて受信したリクエストに基づく実行を受理するか否かをリアルタイムに決定する手段を備えた請求項２記載の実行制御装置。
【請求項９】
受信したリクエストをこのリクエストの要求先セッション処理の進行度に応じて複数のキューのいずれかに分配し、前記サーバの負荷に応じて前記キューから所定のリクエストを読み出す手段を備えた請求項２記載の実行制御装置。
【請求項１０】
サーバとクライアントとの間の複数工程からなる処理において、並行して実行される処理の実行制御をする実行制御方法であって、
処理の完了までの工程数を進行度として評価する進行度評価ステップと、
当該進行度に基づき処理のスケジューリングを行うスケジューリングステップと
を有することを特徴とする実行制御方法。
【請求項１１】
情報処理装置にインストールすることにより、その情報処理装置に、請求項１ないし９のいずれかに記載の実行制御装置の機能に相応する機能を実現させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、サーバとクライアントとの間の複数工程からなる処理における並行して実行される処理の実行制御に利用する。特に、複数ページに跨がって閲覧または情報入力することにより初めて１つのサービスが完了するセッション処理を実行するサーバに利用するに適する。
【背景技術】
【０００２】
インターネットの普及に伴い、ネットワークを介して様々なサービスを利用できるようになっている。メール、ホームページの閲覧、検索、オンライン取引、ＩＰ電話、ビデオオンデマンドなどは、その一例である。これらのネットワークサービスは様々な形態で提供し得るが、近年、クライアントとのインタフェースとして、Ｗｅｂサーバの利用が主流となっている。以下、本明細書では、本発明の適用先として、Ｗｅｂサーバに注目して議論するが、必ずしも他のサーバへの適用を制限するものではない。
【０００３】
Ｗｅｂサーバを用いたサービス（Ｗｅｂサービス）の基本的な仕組みは以下のとおりである。まず、クライアントがＷｅｂサーバに対して、取得したいコンテンツを識別するＵＲＬ(Uniform Resource Locator)を付与したリクエストを送信する。Ｗｅｂサーバがリクエストを受け取ると、リクエスト中のＵＲＬに対応するコンテンツをレスポンスとしてクライアントに送り返す。Ｗｅｂサービスは、このリクエストの受信に対するレスポンスの返信を基本工程とし、その繰り返しによって、より高度なＷｅｂサービスを提供する。複数の工程を要するＷｅｂサービスとして、後述するページ処理や、セッション処理がある。リクエスト・レスポンスを転送する通信プロトコルとして、ＨＴＴＰ(Hyper
Text Transfer Protocol)が用いられる。本明細書では、Ｗｅｂサービスを行うサーバシステム全体をＷｅｂサーバ、また、Ｗｅｂサーバ上でＨＴＴＰプロトコルを処理する機能をＨＴＴＰサーバ、リクエストに応じたコンテンツを生成する機能をＷｅｂアプリケーションと呼ぶ。
【０００４】
Ｗｅｂサーバから取得できるコンテンツとして、レイアウト情報を含むテキスト（ｈｔｍｌファイルなど）、画像、音声、動画などがある。さらにコンテンツは、静的コンテンツと動的コンテンツとに分類できる。静的なコンテンツとは、時間が経っても変化しないコンテンツをいう。一方、動的コンテンツとは、リクエストの内容やＷｅｂサーバの状態に応じて変化するコンテンツをいう。動的コンテンツは、Ｗｅｂサーバがリクエスト受信した際に、Ｗｅｂアプリケーションによって動的に生成される。
【０００５】
クライアントのＷｅｂブラウザに表示される一つのページ（Ｗｅｂページ）を、複数のコンテンツで構成することもできる。このような場合は、ＨＴＭＬファイルに構成要素となるコンテンツのＵＲＬを、ＳＲＣタグを用いて記述しておく。Ｗｅｂブラウザは、受信したＨＴＭＬファイル中にＳＲＣタグを見つけると、そのＵＲＬに対して自動的にリクエストを発行する。Ｗｅｂブラウザ上の１ページを表示するための、リクエストレスポンスの繰り返しを、本明細書ではページ処理と呼ぶ。
【０００６】
さらに、Ｗｅｂサービスには、ページ処理を一つの工程とし、複数ページに跨がって閲覧または情報入力することで、初めて１つのサービスが完了する場合がある。本明細書では、複数ページに跨がるＷｅｂサービスにおいて、クライアントが先頭ページを取得してから最終ページの取得が完了するまでをセッションと呼ぶ。例えば、オンラインショッピングでは、購入商品の選択、クライアント情報の入力、購入内容の確認をすることで、初めて購入手続きが完了する。
【０００７】
ＨＴＴＰはリクエスト間で状態を受け渡さないステートレスなプロトコルである。したがって、セッション処理を行う場合は、一般的にＷｅｂアプリケーションが、セッションの状態（クライアント情報、入力履歴、ページ進行など）を管理する。Ｗｅｂアプリケーションでは、クライアントからセッション開始に対応するリクエストを受信すると、当該セッションを識別するためのセッションＩＤを発行する。そして、セッションＩＤをキーとして、セッションの状態を管理する。
【０００８】
セッションＩＤは、クライアントからのリクエストに含まれるように、Ｗｅｂアプリケーションからクライアントに通知される。クライアントへのセッションＩＤの通知方法として、ａ）レスポンス中のＵＲＬにセッションＩＤを埋め込む、ｂ）レスポンス中のＦＯＲＭタグのｈｉｄｄｅｎフィールドにセッションＩＤを埋め込む、ｃ）Ｃｏｏｋｉｅを用いて、クライアントのブラウザにセッションＩＤを記憶させる、などが挙げられる。クライアントのブラウザは、リクエストをサーバに送信する際に、受け取ったセッションＩＤをリクエストのＵＲＬ、コンテンツ、またはＣｏｏｋｉｅに格納する。
【０００９】
セッション処理を、図２０の具体例を用いて説明する。図２０は、カタログを用いて商品販売を行うサイトのページ遷移図である。まずクライアントが「カタログ」ページ(www.example.ntt.co.jp/shopping/catalog.cgi)にアクセスすることで、セッションが開始される。「カタログ」ページでは、購入可能な商品の一覧が表示され、クライアントは当該ページで購入商品を選択できる。また「カタログ」ページでは、新しいセッションに対してセッションＩＤを発行し、クライアント情報やクライアントが選択した商品をセッション毎に記憶する。すなわち、カタログページを生成するｃａｔａｌｏｇ．ｃｇｉは、クライアントからリクエストを受信すると、リクエスト中に有効なセッションＩＤが含まれるか否かを検査する。リクエスト中にセッションＩＤが存在しない、または、リクエスト中のセッションＩＤが無効な場合は、新たなセッションＩＤを発行する。有効なセッションＩＤを含む場合は、継続中のセッションとみなす。
【００１０】
クライアントは、商品を選択すると、ｉｔｅｍ．ｃｇｉにアクセスする。ｉｔｅｍ．ｃｇｉは「商品詳細」ページを生成し、ユーザが選択した商品の詳細情報を提示する。クライアントは当該ページにて、商品を買物カゴに加えるか否かを選択できる。選択した商品を買物カゴに加える場合は、ｃａｒｔ．ｃｇｉにアクセスし、当該セッションの買物カゴ情報を更新する。選択した商品を買物カゴに加えない場合は、ｃａｔａｌｏｇ．ｃｇｉに再アクセスし、商品の選択を継続する。
【００１１】
ｃａｒｔ．ｃｇｉは、現在の買物カゴの内容を表示するための「買物カゴ」ページを返す。「買物カゴ」ページでは、商品の削除や、数量変更などを行うことができる。クライアントは、ｃａｒｔ．ｃｇｉに変更内容を送信することで、買物カゴを更新する。また、購入商品を選択し終え、購入手続きを開始する場合は、ｕｓｅｒｉｎｆｏ．ｃｇｉにアクセスする。
【００１２】
ｕｓｅｒｉｎｆｏ．ｃｇｉは、購入者の氏名、商品の届け先、支払い方法などの入力をするための「クライアント情報入力」ページを返す。クライアントは、必要な情報を入力し終えると、購入内容の確認を行うためｃｏｎｆｉｒｍ．ｃｇｉにアクセスする。
【００１３】
ｃｏｎｆｉｒｍ．ｃｇｉは、クライアントから送信されたクライアント情報を検査する。問題が無い場合は「最終確認」ページを返す。一方で、入力情報に誤りがある場合は、エラー内容を付与して、再度「クライアント情報入力」ページを返す。
【００１４】
クライアントは「最終確認」ページの内容を確認し、問題が無い場合は購入確定ボタンを押し、ｔｈａｎｋｓ．ｃｇｉにアクセスする。ｔｈａｎｋｓ．ｃｇｉは、クライアントの購入内容を記録し、セッションＩＤを無効化する。そして、購入完了ページをクライアントに返す。以上により、セッション処理が完了する。
【００１５】
Ｗｅｂサービスが普及するにつれて、サービスを快適に利用していくための課題も明らかになりつつある。その課題の一つとして、サービス利用の集中時におけるＷｅｂサーバの有効性能の維持が挙げられる。
【００１６】
サービス利用の集中の例として、人気の高い銘柄の株やチケットの売買によるリクエスト集中や、災害発生時の見舞呼などがある。また、悪意のあるクライアントによって、Ｆ５アタックなどの無意味なリクエストが大量に送信される場合もある。これらの要因によって、Ｗｅｂサーバにリクエストが過剰に送信されると、第一の問題としてリクエスト処理能力低下、あるいは第二の問題として、複数工程からなる処理の途中失敗、といった問題が生じる。
【００１７】
まず、第一の問題であるリクエスト処理能力低下について議論する。Ｗｅｂサーバにリクエストが過剰に送信されると、リクエスト間でＷｅｂサーバの計算リソースが競合する。加えて、入出力や、プロセス切替えなどのオーバーヘッドが増加し、サービスの実行に割当てられるＷｅｂサーバの計算リソース自体も減少する。これらの結果、Ｗｅｂサーバが混雑すればするほど、Ｗｅｂサーバの処理性能が低下するという問題が生じる。
【００１８】
図２１は、リクエスト過剰によるＷｅｂサーバの処理性能の低下を示す実験結果である。横軸に入力リクエストレート（ｒｐｓ:request/sec）をとり、縦軸にスループット（ｒｐｓ）をとる。図２１では、あるＷｅｂサーバに対して、入力リクエストレート、すなわち、単位時間当たりのリクエスト数（ｒｐｓ）を変化させてリクエストを送信する。そして、スループット、すなわち、Ｗｅｂサーバが単位時間当たりに完了できたリクエスト数（ｒｐｓ）を計測している。
【００１９】
図２１に示されるように、入力リクエストレートが一定範囲内であるならば、入力レートに対してスループットは比例する（図２１破線（ａ））。しかしながら、Ｗｅｂサーバの最大スループットに達すると、スループットが低下に転じる（図２１破線（ｃ））。故に、Ｗｅｂサーバの最大性能を超えるリクエストを受信した場合でも、図２１破線（ｂ）にそって、Ｗｅｂサーバの最大性能を維持できる技術が必要といえる。
【００２０】
第一の問題が解決されても、次に複数工程からなる処理の途中失敗によって、ページ処理性能の低下、セッション処理性能の低下が問題となる。リクエスト過剰による性能の低下がない、すなわち、図２１破線（ｂ）を維持できるＷｅｂサーバを仮定する。さらに、リクエストはその種類によらず、全て負荷が等しいとする。このとき、入力リクエストレートをλ（ｒｐｓ）、Ｗｅｂサーバの最大スループットをＴmax（ｒｐｓ）とすると、リクエスト成功率γsは、以下の式によって与えられる。
【００２１】
γs＝ｍｉｎ（１，Ｔmax／λ）
すなわち、入力リクエストレートがＷｅｂサーバの最大スループットを超えると、リクエスト間のリソース競合が発生するようになる。その結果、リクエスト成功率が入力リクエストレートに反比例して低下する。
【００２２】
Ｗｅｂサービスでは、ブラウザが表示する１ページが複数リクエストによって構成されている場合もある。この場合のページ成功率は、リクエスト成功率を、さらにページあたりのリクエスト数で累乗したものとなる。さらに、セッション処理では複数のページを処理することで、初めて一つの処理が完結する。特に、セッション途中でのリクエスト失敗によって、セッション処理が最初からやり直しになる場合もある。このため、リクエスト過剰によって、セッションの完了率がセッションあたりのページ数に対して指数関数的に減少する。
【００２３】
この結果、Ｗｅｂサーバがリクエストを最大性能で処理しているにも関わらず、リソース競合によるセッション中断によって、セッションスループット（単位時間当たりのセッション完了数）がほぼ０となる、といった状況が生じる。Ｗｅｂサービスでは、リクエストの種類によって、その重要度が大きく異なる。特に、セッション処理は、金品を用いた取引や個人情報を扱うことが多く、他の非セッション処理よりも重要度が高いといえる。したがって、リクエスト過剰によるセッション処理性能の低下を回避できる技術が不可欠である。
【００２４】
【非特許文献１】Ｎ．Ｂｈａｔｔｉ  ａｎｄ  Ｒ．Ｆｒｉｅｄｒｉｃｈ．Ｗｅｂ  ｓｅｒｖｅｒ  ｓｕｐｐｏｒｔ  ｆｏｒ  ｔｉｅｒｅｄ  ｓｅｒｖｉｃｅｓ．Ｉｎ  ＩＥＥＥ  Ｎｅｔｗｏｒｋ，１３（５），ｐｐ．６４−７１，１９９９．
【非特許文献２】Ｌ．Ｃｈｅｒｋａｓｏｖａ  ａｎｄ  Ｐ．Ｐｈａａｌ．Ｓｅｓｓｉｏｎ  ｂａｓｅｄ  ａｄｍｉｓｓｉｏｎ  ｃｏｎｔｒｏｌ：ａ  ｍｅｃｈａｎｉｓｍ  ｆｏｒ  ｉｍｐｒｏｖｉｎｇ  ｔｈｅ  ｐｅｒｆｏｒｍａｎｃｅ  ｏｆ  ｏｖｅｒｌｏａｄｅｄ  ｗｅｂ  ｓｅｒｖｅｒ．Ｉｎ  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ｔｈｅ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｗｏｒｋｓｈｏｐ  ｏｎ  Ｑｕａｌｉｔｙ  ｏｆ  Ｓｅｒｖｉｃｅ，１９９８．
【非特許文献３】“過負荷時のＷｅｂアプリケーションの性能劣化を改善するＳｅｓｓｉｏｎ−ｌｅｖｅｌ  Ｑｕｅｕｅ  Ｓｃｈｅｄｕｌｉｎｇ”、松沼正浩、日比野秀章、佐藤芳樹、光来健一、千葉滋、第２回ディペンダブルソフトウェアワークショップ（ＤＳＷ’０５）、東京大学、２００５年１月．
【発明の開示】
【発明が解決しようとする課題】
【００２５】
Ａｐａｃｈｅなどの汎用ＨＴＴＰサーバでは、ＴＣＰコネクション数の上限を定めることによって、リクエスト過剰対策を試みている。すなわち、リクエスト・レスポンスの送受信のためのＴＣＰコネクションがクライアント−Ｗｅｂサーバ間で確立されると、ＨＴＴＰサーバは対応するスレッドを起動し、ＴＣＰコネクション毎にリクエストを並列処理する。ＴＣＰコネクション数が予め設定した上限を超えた場合は、新規に確立されたＴＣＰコネクションをキューに格納し、ＦＩＦＯ(First-In First-Out)ベースで順番に処理する。キュー中の処理待ちＴＣＰコネクションが予め設定された上限に達した場合は、新規ＴＣＰコネクションを廃棄する。この手法の問題は以下のとおりである。
（１）ＴＣＰコネクション数が負荷を正確に反映しない。すなわち、リクエストの種類、クライアントの回線速度や思考時間によって、ＴＣＰコネクション毎に負荷が大きく異なる。このため、ＴＣＰコネクション数が上限に達する前に、Ｗｅｂサーバが過負荷となる場合が生じる。逆に、Ｗｅｂサーバの計算リソースが余っていても、ＴＣＰコネクション数が上限に達することによって、新たなＴＣＰコネクションに対する処理を開始できなくなる、といった問題も生じる。
（２）リクエストの重要度を区別しない。ＨＴＴＰサーバは、ＴＣＰコネクション単位でリクエストを処理するが、このとき全てのＴＣＰコネクションを公平に扱う。逆にいえば、リクエスト過剰時において、セッション処理を行うＴＣＰコネクションを何ら保護しない。
【００２６】
これに対して、セッション処理の保護を目的としたスケジューリング・アドミッション制御技術が幾つか提案されている。
【００２７】
非特許文献１では、特定のクライアントをプレミアムクライアントとして設定し、プレミアムクライアントを優先的に処理する手法を提案している。これにより、プレミアムクライアントによるセッション処理の途中失敗が防止され、プレミアムクライアント数分のセッションスループットを確保できる。ただし、プレミアムクライアント以外のセッション処理は何ら保護されないため、本来サーバが達成できるセッションスループットの実現は困難である。
【００２８】
また、プレミアムクライアントが、正規のセッションを、完了手続きを行わずにセッションを中断した場合に、タイムアウトが生じるまで次のプレミアムクライアントを選出できない、といった問題が生じる。
【００２９】
非特許文献２では、セッション単位でアドミッション制御を行う手法を提案している。すなわち、セッション処理に必要な計算リソースを予め見積もっておく。そして、サーバの計算リソースを監視し、セッション処理に必要な空きリソースが生じた場合に、次のクライアントにセッション処理の実行を許可する。しかし、クライアントの回線速度、思考時間、アクセスするページ数などの違いから、クライアント毎にセッション処理の負荷は大きく異なる。故に、事前見積もりに基づくアドミッション制御では、サーバのリソースを十分に活用することが困難である。
【００３０】
また、セッション処理と非セッション処理とが混在する場合には、非セッション処理によって計算リソースが占有され、セッション処理の開始に必要な空きリソースを確保できなくなる場合が生じる。
【００３１】
非特許文献３では、セッション処理の開始レートを、実行待ちリクエストのキュー長に応じて制御する。すなわち、実行待ちリクエストのキュー長が長くなると、サーバが過負荷であるとみなし、セッション処理の開始レートを減少させ、セッション処理による負荷を軽減させる。一方、キュー長が短くなると、サーバが過負荷から回復しているとみなし、セッション処理開始レートを増加させ、より高いセッションスループットを得ようとする。しかしながら、非特許文献２と同様に、セッション毎の負荷の違いから、セッション単位の制御では、サーバの計算リソースを十分に活用できない。また、大量の非セッション処理によって、セッション処理のリソースが確保できなくなる、といった問題が生じる。
【００３２】
本発明は、このような背景の下に行われたものであって、上記第二の問題、すなわち、過剰リクエスト時において複数工程からなる処理の途中失敗によってサーバの処理性能が低下する問題、を解決するための実行制御装置および方法を提供することを目的とする。
【課題を解決するための手段】
【００３３】
従来手法の問題は、複数工程からなる処理にも関わらず、処理全体をまとめてスケジューリングすることによって、サーバの処理性能の維持を試みている点にある。処理の負荷は、回線速度、工程間の思考時間、処理完了までの工程数によって、処理毎に大きく異なる。したがって、処理全体でのスケジューリングによって、サーバの計算リソースを有効に活用することは困難である。そこで、本発明は、処理単位のスケジューリングではなく、より粒度の細かい工程単位でのスケジューリングによって処理性能の維持を試みる。すなわち、（１）複数工程を有する処理では、少ない工程数で完了する可能性が高い（以下、進行度が高い）処理を優先処理する、さらに、（２）複数工程からなる処理が単一工程からなる処理より重要である場合は、複数工程からなる処理を優先処理する。
【００３４】
すなわち、本発明は、サーバとクライアントとの間の複数工程からなる処理における、並行して実行される処理の実行制御をする実行制御装置であって、本発明の特徴とするところは、処理の完了までの工程数を進行度として評価する進行度評価手段と、当該進行度に基づき処理のスケジューリングを行うスケジューリング手段とを備えたところにある。
【００３５】
これにより、本発明では、スケジューリングを、従来手法の処理単位からより粒度の細かい工程単位で行うことができる。よって、処理毎の負荷の違いに影響を受けなくなるため、Ｗｅｂサーバの計算リソースを有効に活用できる。また、複数の工程を有する処理を単一工程処理より優先させることで、単一工程処理による計算リソースの占有を回避している。さらに、同時に実行される処理間で計算リソースが競合しても、進行度が高い複数工程を有する処理が優先されるため、高い処理スループットを維持できる。
【００３６】
例えば、前記処理は、各工程がクライアントからのリクエストの受信によって起動されるページ処理からなるセッション処理である。
【００３７】
このときに、前記スケジューリング手段は、前記サーバの負荷が所定の値を超えないようにスケジューリングを行う手段を備えることが望ましい。これにより、過剰に処理の実行を要求された場合でも、サーバの負荷が正常範囲内に維持されるため、サーバの処理性能の低下が生じない。
【００３８】
前記進行度評価手段は、例えば、予め一つのセッション処理において使用される複数のＵＲＬの情報を保持し、クライアントから受信したリクエストに含まれるＵＲＬの情報と前記登録されているＵＲＬの情報との一致を判定することにより当該セッション処理の進行度を求める手段を備える。これにより、一意に定まるＵＲＬを用いて進行度を求めることができるので、セッション処理毎の状態管理が必要ないという利点がある。
【００３９】
あるいは、前記進行度評価手段は、予め一つのセッション処理においてアクセスされるページに対応した当該セッション処理の進行状態の情報を保持し、クライアントから受信したリクエストに含まれるページアクセス要求に基づき当該セッション処理の進行状態を認識することにより当該セッション処理の進行度を求める手段を備える。これにより、セッション処理毎の状態管理が必要となるが、同じページへのアクセスでも状態に応じて異なる進行度を与えることができ、より正確にセッション処理の進行度を評価できる。また、異常な順序でページアクセスを行うクライアントを規制することが可能となる。
【００４０】
あるいは、前記進行度評価手段は、処理が既に実行を完了している工程数を認識することによって、当該処理の進行度を求める手段を備える。これにより、セッション処理毎の状態管理が必要となるが、後述するセッション状態遷移図の設定を必要としないという利点がある。
【００４１】
また、前記進行度評価手段は、処理の工程が、当該工程の初期工程にあるか、初期工程より後の工程にあるかに基づき当該処理の進行度を求める手段を備えることができる。これにより、初期工程が既に完了している処理を継続中処理とみなし、初期工程が未完了の処理よりも優先的に実行することができる。
【００４２】
また、リクエストのキューを設けることなく、一つのセッション処理の進行度および当該セッション処理を実行中のサーバの負荷に応じて受信したリクエストに基づく実行を受理するか否かをリアルタイムに決定する手段を備えることにより、メモリリソースを節約することができる。あるいは、スケジューリング手段の遅延を無くすことができる。
【００４３】
また、リクエストのキューを設け、受信したリクエストをこのリクエストの要求先セッション処理の進行度に応じて複数のキューのいずれかに分配し、前記サーバの負荷に応じて前記キューから所定のリクエストを読み出す手段を備えることにより、拒絶されるリクエストを減らし、ネットワークリソースを有効利用することができる。
【００４４】
また、本発明を方法の発明の観点から捉えることができる。すなわち、本発明は、サーバとクライアントとの間の複数工程からなる処理において、並行して実行される処理の実行制御をする実行制御方法であって、本発明の特徴とするところは、処理の完了までの工程数を進行度として評価する進行度評価ステップと、当該進行度に基づき処理のスケジューリングを行うスケジューリングステップとを有するところにある。
【００４５】
また、本発明をプログラムの発明の観点から捉えることができる。すなわち、本発明は、汎用の情報処理装置にインストールすることにより、その情報処理装置に、本発明の実行制御装置の機能に相応する機能を実現させるプログラムである。
【００４６】
本発明のプログラムは、記録媒体に記録されることにより、前記情報処理装置は、この記録媒体を用いて本発明のプログラムをインストールすることができる。あるいは、本発明のプログラムを保持するサーバからネットワークを介して直接前記情報処理装置に本発明のプログラムをインストールすることもできる。
【００４７】
これにより、汎用の情報処理装置を用いて、本発明の実行制御装置を実現し、本発明の実行制御方法を実行させることができる。
【発明の効果】
【００４８】
本発明によれば、処理毎の負荷の違いの影響を受けることなく、サーバの計算リソースを有効に活用することができる。また、過剰に処理の実行を要求された場合でも、サーバの処理性能の低下を防ぐことができ、高い処理スループットを維持できる。
【発明を実施するための最良の形態】
【００４９】
本発明の実施形態の一例について図面を参照して説明する。本発明の適用範囲は、サーバとクライアントとの間の複数工程からなるあらゆる処理に適用できるが、本発明の実施形態の説明では、説明をわかりやすくするために、処理は、各工程がクライアントからのリクエストの受信によって起動されるページ処理からなるセッション処理であるとして説明を行う。
【００５０】
図１は本発明の実施形態を示すブロック図である。図１に示す本発明の実施形態による実行制御装置は、リクエスト制御部１、Ｗｅｂアプリケーション部２、負荷監視部３の各処理部からなる。Ｗｅｂアプリケーション部２はリクエスト制御部１からリクエストを受け取ると、リクエストされた内容に応じたレスポンスを返信する。負荷監視部３では、Ｗｅｂアプリケーション部２の実行状況を監視し、得られた負荷情報をリクエスト制御部１に通知する。
【００５１】
リクエスト制御部１では、過剰リクエスト時においてもセッション処理性能が維持できるように、負荷監視部３から受け取った負荷情報に基づきリクエストをスケジューリングする。ここで、スケジューリングには、リクエスト送信の許可、遅延、廃棄、拒絶、転送、順序変更が含まれる。本発明では、リクエスト制御部１にて、セッションの進行度を考慮したスケジューリングを行う。以下では、負荷監視部３、リクエスト制御部１について詳述する。
【００５２】
負荷監視部３は、Ｗｅｂアプリケーション部２の実行状況を監視し、Ｗｅｂサーバの負荷を評価する。そして負荷評価結果をリクエスト制御部１に対して送信する。監視項目の例として、ＷｅｂサーバのＣＰＵ使用率、メモリ量、利用帯域、ＴＣＰコネクション数、セッション数、応答時間、実行中のリクエスト数などがある。実行するＷｅｂアプリケーションの性質や、Ｗｅｂサーバのシステム構成によって、柔軟に監視する項目数とその種類を選択できる。負荷監視部３は、Ｗｅｂアプリケーション部２と同じＷｅｂサーバ上で実行することも、外部装置上で、Ｗｅｂサーバとは計算リソースを独立させて実行させることもできる。また、各項目毎に、異なる計算リソース上で監視を実行してもよい。例えば、ＣＰＵ負荷、メモリ量といったＷｅｂサーバでのみ取得できる項目に関してはＷｅｂサーバで監視を行い、それ以外の項目を外部装置上で監視してもよい。
【００５３】
負荷監視部３の負荷監視結果は、数値、ベクトル、文字列などを用いて、様々に表現され得る。例えば、リクエスト制御部１において、受信したリクエストの種類や、そのリクエストが必要とする計算リソースから、リクエスト制御に用いる負荷監視項目を変更してもよい。本明細書では、セッションの進行度に基づくリクエスト制御に注目して議論するため、負荷評価結果を０から１までの実数で表現するものとする。以下、本明細書では、負荷評価結果を、負荷度Ｌ（０≦Ｌ≦１）で表す。負荷度Ｌが０に近いほどＷｅｂサーバの負荷が低く、逆に、負荷度Ｌが１に近いほど、Ｗｅｂサーバの負荷が高くなる。負荷度Ｌの計算例を以下に示す。ｎ個の監視項目があり、それぞれの監視項目に対して１，…，ｎまでの識別子ｉが与えられているものとする。さらに、各監視項目ｉの計算結果をｖi、その最大値をＭiとする。このとき、
Ｌ＝ｍａｘi,…,n(vi/Mi)
と表せる。
【００５４】
リクエスト制御部１は、過剰リクエスト時でもセッション処理性能を高水準に維持できるように、受信したリクエストの実行順序をスケジューリングする。ここで本発明では、セッションの進行度を考慮してスケジューリングする。負荷監視部３と同様に、リクエスト制御部１をＷｅｂアプリケーション部２と同一のＷｅｂサーバ上で実行することもできる。同一のＷｅｂサーバ上で実行する場合は、ＯＳ、ＨＴＴＰサーバなどを拡張する。また、外部装置上で実行する場合は、Ｐｒｏｘｙ、Ｆｉｒｅｗａｌｌ、負荷分散装置、Ｗｅｂアクセラレータなどを拡張する。
【００５５】
図２はリクエスト制御部１のブロック図である。リクエスト制御部１は、進行度評価部４、およびリクエストスケジューリング部５からなる。進行度評価部４は、受信したリクエストが属するセッションの進行度を評価する。ここで、セッションの進行度とは、セッションが完了するまでの必要リクエスト数（またはページ数）を表したものである。進行度もまた、数値、ベクトル、文字列などによって様々に表現され得る。本明細書では、リクエストスケジューリング部５とのインタフェースを統一して議論するため、進行度を０から１までの実数で表現し、記号ｃ（０≦ｃ≦１）で表す。セッションが完了に近付くほど、進行度ｃは１に近づくものとする。また、セッションに属さない非セッション処理のリクエストの進行度としてｃ＝０を与える。
【００５６】
リクエストスケジューリング部５は、負荷監視部３からの負荷度Ｌ、および、進行度評価部４からの進行度ｃを基に、リクエストをスケジューリングし、適切なタイミングでリクエストをＷｅｂアプリケーション部２に転送する。また、スケジューリングの結果、リクエストを拒絶する場合には、リクエストを廃棄しても、サーバビジーメッセージ（ＨＴＴＰ５０３エラーレスポンスなど）を返却してもよい。
【００５７】
進行度評価部４は、現在受信しているリクエスト、および過去に受信したリクエスト・レスポンスから、現在受信しているリクエストが属するセッションの進行度ｃを評価する。以下では、進行度評価部４の応用例として、図２０のセッション処理を行うＷｅｂサーバ(www.example.ntt.co.jp)を用いて説明する。このとき、セッションＩＤの変数名としてｓｅｓｓｉｏｎ＿ｉｄを用いるものとする。また、クライアントのブラウザがＣｏｏｋｉｅに対応しているならば、セッションＩＤをレスポンスのＳｅｔ−Ｃｏｏｋｉｅフィールドに格納して通知し、Ｃｏｏｋｉｅに非対応ならば、セッションＩＤをＦｏｒｍタグのｈｉｄｄｅｎフィールドに格納して通知するものとする。また、クライアントは、ＷｅｂブラウザがＣｏｏｋｉｅに対応している場合は、ｓｅｓｓｉｏｎ＿ｉｄをリクエストのヘッダＣｏｏｋｉｅフィールドに格納して返送し、Ｃｏｏｋｉｅに非対応ならば、リクエストのコンテンツ中に格納して返送するものとする。また、文字列Ａが文字列Ｂにマッチするという表現を用いる場合は、文字列Ｂが文字列Ａに含まれることを意味する。図中で、“／”で囲まれている文字列は、プログラミング言語Ｐｅｒｌと同様の正規表現を用いたマッチ演算である。
【００５８】
（進行度評価部の実施例１）
セッション処理を行うページのＵＲＬと進行度の組とを登録しておく。受信したリクエストのＵＲＬが登録されているＵＲＬに一致する場合には、登録されている進行度で当該セッションの進行度を更新する。そして、受信したリクエストの進行度として当該セッションの進行度を返す。
【００５９】
図３は、進行度評価部４の実施例１のブロック図である。進行度評価部４の実施例１は、ページＩＤ検査部６、進行度読み出し部７からなる。
【００６０】
ページＩＤ検査部６は、受信したリクエストがアクセスしているページのページＩＤを取得する。ページＩＤの取得は、ページ表を用いて行う。ページ表には、ページＩＤと対応するリクエストのマッチング条件の組が登録される。このとき、非セッション処理用のページを登録しておく必要はない。図４に、図２０のセッション処理を想定した場合のページ表の登録例を示す。図４のページ表では、マッチング条件として、スキーム、ホスト、パスのみを用いているが、ポート番号やクエリ、そしてＵＲＬ以外のヘッダフィールド、コンテンツを用いてもよい。
【００６１】
ページＩＤ検査部６では、まず、図４のページ表に、受信したリクエストにマッチング条件が成立するエントリが存在するか否かを検査する。マッチング条件が成立するエントリが存在する場合は、そのエントリのページＩＤを、当該リクエストのページＩＤとする。マッチング条件が成立するエントリが存在しない場合は、非セッション用ページＩＤとして、０を出力する。
【００６２】
進行度読み出し部７において、ページＩＤに対応する進行度を取得する。進行度の与え方として以下がある。
・Ｗｅｂサーバの管理者が任意に設定する。
・各ページにアクセスしてからセッションが終了するまでの平均リクエスト回数を予め学習しておく。そして、各ページの平均リクエスト回数の関数を進行度とする。例えば、セッション用のページ数をＮとし、ページｊ（ｊ＝１，…，Ｎ）の平均リクエスト回数をＲjとする。また、非セッション用ページの平均リクエスト回数を
Ｒ0＝（ｍａｘj=1,…,NＲj）＋ｋ
とする。ここでｋは正の定数である。同様にページｉ（ｉ＝０，…，Ｎ）の進行度をｃiとする。このとき、
ｃi＝（Ｒ0−Ｒi）／Ｒ0
である。
【００６３】
当該実施例は、他の進行度評価部４の実施例と比較し、セッション毎の状態管理が必要ない、という利点がある。
・非セッション用ページ（ページ０）の進行度を０に、セッション用ページのうちセッションの開始用ページ（図４の例では、ページ１）の進行度をｋ（０＜ｋ＜１）に、それ以外を１に設定する。本実施例では、セッション開始用ページへのアクセスが完了しているセッションを継続中セッションとみなし、セッション開始用ページへのアクセスが未完了のセッションよりも優先的に実行することができる。
【００６４】
（進行度評価部の実施例２）
ページアクセスに対するセッションの状態遷移、および各状態の進行度を設定しておく。リクエストを受信するたびに、当該セッションの状態を更新し、その状態に対応する進行度を返す。
【００６５】
図５は、進行度評価部４の実施例２のブロック図である。進行度評価部４の実施例２は、セッションＩＤ検査部８、ページＩＤ検査部１０、進行度読み出し部１１、セッション進行検査部９、および、進行度補正部１２からなる。また、セッション進行検査部９は、セッション表を有し、このセッション表をセッションの状態管理のために用いる。図６に、セッション表の実施例を示す。セッション表に格納される項目を以下に示す。
・セッションＩＤ：セッション表を参照する際のキーとして用いられる。
・有効期限：当該エントリが無効となる期日。有効期限を設定しておくことで、セッション処理終了後に、使用済みセッションＩＤを不正に利用されることを回避する。
・状態ＩＤ：当該セッションの状態のＩＤ。セッションの状態遷移についてはセッション進行検査部９の説明において詳述する。
・ページアクセス異常回数：当該セッションにおいて、異常なページアクセスが行われた回数。
【００６６】
セッションＩＤ検査部８は、当該リクエストからセッションＩＤを取得する。このとき、取得したセッションＩＤが有効であるか否かを検査してもよい。
【００６７】
まず、リクエスト中のセッションＩＤを取得するため、リクエスト用のセッションＩＤの格納先と変数名とを設定しておく。登録例を図７に示す。また、レスポンス中のセッションＩＤを取得するため、レスポンス用のセッションＩＤの格納先と変数名とを設定しておく。登録例を図８に示す。
【００６８】
次に、セッションＩＤ検査部８の処理手順を図９に示す。図９は、リクエスト、またはレスポンスの受信によって開始される。図９に示すように、レスポンスを受信した場合は（Ｓ２）、レスポンスのセッションＩＤ格納先に、セッションＩＤが含まれるか否かを検査する（Ｓ３）。セッションＩＤが含まれている場合は、当該セッションＩＤをセッション表に登録する（Ｓ４）。そして、セッションＩＤの有効期限、状態ＩＤ、ページアクセス異常回数を初期化する。状態ＩＤは、当該レスポンスに対応するリクエスト受信時に、セッション進行検査部９から出力された状態ＩＤで初期化する。
【００６９】
一方、リクエストを受信した場合は（Ｓ２）、予め設定した格納先にセッションＩＤが含まれているか検査する（Ｓ５）。セッションＩＤが含まれる場合は、当該セッションＩＤがセッション表に登録されているか否か調べる（Ｓ６）。セッションＩＤがセッション表に登録されている場合は、有効なセッションＩＤとみなし、そのセッションＩＤを出力する（Ｓ８）。このとき、当該セッションＩＤの有効期限を更新してもよい（Ｓ７）。
【００７０】
また、リクエスト中にセッションＩＤが含まれていない、または、検出したセッションＩＤがセッション表に登録されていない場合は（Ｓ５）、非セッション処理用セッションＩＤとして０（無効セッションＩＤ）を出力する（Ｓ９）。さらに常時、セッション表中の各セッションＩＤの有効期限を検査し、有効期限切れのセッションＩＤをセッション表から削除する（Ｓ１）。
【００７１】
セッション表はリストによって実装することも、ハッシュ表を用いて実装することもできる。さらに、ハッシュ表を用いる場合には、ハッシュ値が衝突するセッションＩＤを区別しないで一つのエントリとして登録することで、セッション表のエントリ数の削減や、検索速度の向上が可能になる。
【００７２】
セッション進行検査部９では、セッション毎に、セッションの進行が正しく行われているか否かを評価する。そして、不正なページアクセスが生じた場合は、セッション表中のページアクセス異常回数をインクリメントする。不正なページアクセスであるか否かは、セッション状態遷移図を用いて評価する。セッション状態遷移図は、ページアクセスに対するセッションの状態変化を表現したものである。図１０に、図２０のセッション処理を想定した場合のセッション状態遷移図の一例を示す。図１０中の、ノードに振られた番号は、状態の識別子（状態ＩＤ）を示している。また、図１０中のアークは可能な状態遷移を表し、アーク上にその状態遷移を引き起こすページＩＤが示される。ここでページＩＤは、図４のページ表に従うものとする。図１０中の状態０は非セッション状態を表し、状態０からページ１（ｃａｔａｌｏｇ．ｃｇｉ）へのページアクセスによってセッションが開始される。また、状態６は最終状態であり、状態６に遷移することで当該セッションは完了する。
【００７３】
セッション状態遷移図は、Ｗｅｂサーバの管理者が任意に設定することも、機械的に学習させることもできる。機械的に学習する場合は、現在アクセスしているページＩＤと、過去ｎ（ｎ≧０）回にアクセスされたページの各ＩＤを状態の識別に用いればよい。すなわち、あるセッションｓがｉ回目にアクセスするページのＩＤをａisとすると、現在ｋ回目のアクセスを行っているセッションの状態は、ａk-ns…ａk-1sａksと表される。状態が定義されると、当該Ｗｅｂサーバのページアクセスログなどから、状態間の遷移があるか否かを検査することができる。さらに、セッション遷移図中の各アークに、その状態遷移が可能な最大回数を設けてもよい。
【００７４】
セッション進行検査部９では、まず、当該セッションＩＤが有効である（０以外）か否かを検査する。無効セッション用ＩＤである場合は、遷移前の状態ＩＤを非セッション用の０とする。有効なセッションＩＤである場合は、当該セッションＩＤをキーとしてセッション表にアクセスし、当該セッションの遷移前の状態ＩＤを取得する。
【００７５】
次に、セッション状態遷移図を参照して、遷移後の状態ＩＤを得る。このとき、ａ）状態遷移図に遷移前の状態から現在アクセスしているページＩＤに対応する状態遷移が無い場合、ｂ）状態遷移が可能な最大回数が設定され、かつその最大回数を超えている場合、に不正なページアクセスとみなす。例えば、図１０の状態が１である場合は、ページ２、またはページ３以外のページアクセスは不正とみなす。セッションＩＤが有効であり、かつ不正なページアクセスが行われた場合は、セッション表中のページアクセス異常回数をインクリメントする。状態遷移図にないページアクセスが行われていた場合の遷移後状態は、ａ）遷移後状態を０とする、ｂ）状態を０にリセットし現在アクセスしているページＩＤで状態遷移を再評価する、ｃ）不正なページアクセスが行われた場合の状態遷移を別途定義しておく、などによって取得する。
【００７６】
次に、セッションＩＤが有効な場合は、セッション表の当該セッションの状態を更新する。最後に、ページアクセス異常回数、遷移後の状態ＩＤを出力する。
【００７７】
クライアントが一つのページを表示するために複数リクエストが必要となる場合は、各ページのルートとなるＵＲＬのリクエストを取得した場合にのみ、セッションの状態遷移を評価するようにしてもよい。ルート以外のＵＲＬのリクエストを受信し、かつ、そのリクエストがセッションに属している場合は、セッション表を参照して当該セッションの状態ＩＤとページアクセス異常回数とをそのまま出力すればよい。
【００７８】
進行度読み出し部１１において、状態ＩＤに対応する進行度を取得する。進行度の与え方として、以下がある。
・Ｗｅｂサーバの管理者が、状態ＩＤ毎に進行度を任意に設定する。
・セッション状態遷移図を用いて、各状態から最終状態に遷移するまでに要した平均ページアクセス回数を予め学習しておく。そして、この各状態の平均ページアクセス回数の関数を進行度とする。例えば、状態数をＮとし、状態０を非セッション状態とする。また、状態ｊ（ｊ＝１，…，Ｎ−１）の最終状態までの遷移に要した平均ページアクセス回数をＲjとする。さらに、非セッション状態である状態０の平均ページアクセス回数を
Ｒ0＝（ｍａｘj=1,…,N-1Ｒj）＋ｋ
とする。ここでｋは正の定数である。このとき、状態ｉ（ｉ＝０，…，Ｎ−１）の進行度ｃiは、
ｃi＝（Ｒ0−Ｒi）／Ｒ0
として計算できる。なお、本実施例は、ページアクセス回数の代わりに、リクエスト回数を用いてもよい。
・セッション状態遷移図に、状態間の遷移確率をさらに付与する。そして、状態遷移図から求められる、各状態から最終状態までの平均遷移回数の関数を進行度とする。状態遷移確率は、当該Ｗｅｂサーバのページアクセスログなどから、状態間の遷移確率を機械的に学習することができる。図１０を想定した場合の状態遷移確率の例を図１１に示す。なお、図１１では、状態０から状態１への遷移確率を便宜的に１．０としている。次に、図１２に、各状態の最終状態までの平均遷移回数および進行度を示す。ここで、Ｅiは状態ｉの最終状態までの平均遷移回数、ｃiは状態ｉの進行度とする。このとき、最終状態までの平均遷移回数は、連立方程式
Ｅi＝ΣNj=0Ｐj,i（Ｅj＋１）
を解くことで得られる。ここで、Ｎは状態数を、Ｐj,iは、状態ｊから状態ｉへの遷移確率を表す。ただし、状態遷移図に無い状態遷移の場合は、Ｐj,i＝０とする。また、状態ｌを最終状態とするとＥｌ＝０である。また、進行度を、
ｃi＝（Ｅmax−Ｅi）／Ｅmax
としている。ここで、Ｅmax＝ｍａｘi=0,…,N-1Ｅiである。
【００７９】
悪意のあるクライアントによって正常ユーザのサービスが拒絶されることを回避するため、オプションとして、進行度補正部を設けることができる。進行度補正部１２では、ページアクセス異常回数に基づき、進行度ｃを補正する。例えば、ｎを当該セッションのページアクセス異常回数とし、補正前の進行度をｃ′、補正後の進行度をｃとする。このとき、定数ｋを用いて、
ｃ＝ｋnｃ′（０＜ｋ＜１）
と補正できる。
【００８０】
当該実施例は、セッション毎の状態管理が必要となるが、同じページへのアクセスでも状態に応じて異なる進行度を与えることができ、より正確にセッションの進行度を評価できる。また、異常な順序でページアクセスを行うクライアントを規制することが可能となる。
・非セッション状態（状態０）の進行度を０に、セッションの開始状態（セッションの開始によって、非セッション状態の次に移る状態、図１０の例では状態１）の進行度をｋ（０＜ｋ＜１）に、それ以外の状態の進行度を１に設定する。本実施例では、セッション開始状態から他の状態に遷移済みであるセッションを継続中セッションとみなし、未だセッション開始状態にあるセッションよりも優先的に実行することができる。
【００８１】
（進行度評価部の実施例３）
進行度をリクエスト回数の関数として設定しておき、セッションＩＤ毎にこれまで受信したリクエスト回数をカウントする。すなわち、リクエスト回数をｘとしたとき、
ｃ＝ｆ（ｘ）
である。なお本実施例では、リクエスト回数の代わりとして、ページアクセス回数を用いてもよい。
【００８２】
図１３は、本進行度評価部の実施例３のブロック図である。本進行度評価部の実施例３におけるセッション表は、図１４に示すように、リクエスト回数の項目が設けられ、セッション毎でこれまでに受信したリクエスト数をカウントできるようにする。なお、リクエスト回数は、セッションＩＤ登録時に１に初期化される。
【００８３】
セッションＩＤ検査部１３は、図３で示した進行度評価の実施例２と同様である。リクエスト数カウント部１４では、まず入力されたセッションＩＤが０か否かを検査する。セッションＩＤが０以外である場合は、当該セッションＩＤをキーとして、セッション表を参照する。セッションＩＤが０以外であり、かつセッションＩＤがセッション表に登録されている場合は、セッション表中のリクエスト回数をインクリメントし、その値を出力する。
【００８４】
一方、セッションＩＤが０の場合、またはセッションＩＤが０以外であるがセッション表に登録されていない場合は、当該リクエストがアクセスしているページがセッション開始用のページ（図４の例では、ページ１）か否かを検査する。セッション開始用ページであるか否かは、予めセッション開始用ページのＵＲＬを図４と同様のページ表に登録しておくことで判定できる。セッション開始用ページではない場合は、そのリクエスト回数を０として出力する。セッション開始用ページである場合は、そのリクエスト回数を１として出力する。
【００８５】
進行度計算部１５では、リクエスト回数に基づき進行度を計算する。ｆ（ｘ）の例を以下に列挙する。
・ｆ（ｘ）＝ｘ／（ｘ＋１）：リクエスト回数が多いほど、進行度が高いとみなす。
・ｆ（ｘ）＝ｍｉｎ（１，ｘ／^Ｒ）：^Ｒを１セッションあたりの平均リクエスト回数とする。平均リクエスト回数以上のリクエストは、全て同じ進行度となる。
・ｆ（ｘ）＝｛ｘ／Ｒ：ｘ＜^Ｒ  ｏｒ  ｍａｘ（０，−ｋｘ＋１＋ｋ^Ｒ）：ｘ≧^Ｒ
ｋは正の定数。平均リクエスト回数以上のアクセスには進行度にペナルティを与える。
・ｆ（ｘ）＝｛ｘ／^Ｒ：ｘ＜^Ｒ  ｏｒ  １：^Ｒ≦ｘ＜^Ｒ＋ｋ0Ｒd  ｏｒ  ｍａｘ（０，−ｋ1ｘ＋１＋ｋ1（^Ｒ＋ｋ0Ｒd）：ｘ≧^Ｒ＋ｋ0Ｒd
Ｒdは、セッション辺りのリクエスト回数の標準偏差、ｋ0、ｋ1は正の定数である。リクエスト回数が平均リクエスト回数と標準偏差にｋ0を掛けた値の和を超えた場合には、進行度にペナルティを与える。
・ｆ（ｘ）＝０：ｘ＝０  ｏｒ  ｆ（ｘ）＝ｋ：ｘ＝１  ｏｒ  ｆ（ｘ）＝１：ｘ＞１
【００８６】
ここで、ｋは定数であり、０＜ｋ＜１。本実施例では、リクエスト回数が２以上であるセッションを継続中セッションとみなし、優先的に実行することができる。
【００８７】
上述の例では、リクエスト回数から進行度を計算しているが、リクエスト回数の代わりに、ページ取得回数を用いてもよい。この場合は、各ページのルートとなるＵＲＬのリクエストを受信した場合にのみ、リクエスト回数をインクリメントする。そして、ルート以外のリクエストを受信した場合は、セッション表を参照して、当該セッションのリクエスト回数をそのまま用いればよい。
【００８８】
当該実施例は、進行度評価部の実施例２と同様にセッション毎の状態管理が必要となる。ただし、セッション状態遷移図の設定を必要としないという利点が得られる。
【００８９】
上記進行度評価部の実施例１、実施例２、実施例３を組み合わせ、セッションの進行度をページの種類、状態、リクエスト回数から評価することができる。この場合は、各実施例から得られた進行度の積、平均値、最小値などを最終的な進行度とする。
【００９０】
次に、リクエストスケジューリング部５の実施例について詳述する。
【００９１】
リクエストスケジューリング部５は大きく２種類の方法に分類できる。すなわち、（１）キューを用いた遅延制御をしない方法、（２）キューを用いて遅延制御を行う方法、である。
【００９２】
まず、キューを用いて遅延制御をしない方法について述べる。キューを使わないで実装することで、メモリリソースの節約や、リクエストスケジューリング部５による遅延を無くすことができる。
【００９３】
キューを用いない方法では、リクエストの受信時に、リクエストの送信を許可するか否かを決定する。リクエストの送信を許可する場合は、そのままリクエストをＷｅｂアプリケーション部２に転送する。リクエストの送信を許可しない場合は、そのリクエストを廃棄してもよい（廃棄）。または、クライアントに対してサーバビジーメッセージを返送してもよい（拒絶）。または、当該リクエストを第三のサーバに転送してもよい（転送）。廃棄だけでなく、拒絶または転送を行うことで、クライアントからの連続アクセスを緩和できる。
【００９４】
リクエストの送信を許可するか否かを決定する方法の実施例を以下に示す。
・リクエストの送信許可に必要な負荷度の条件を進行度の範囲毎に設定しておく。図１５に、設定例を示す。
・ｃ＞Ｌならば、そのリクエストの通過を許可する。
・ｃ＞Ｃならば、そのリクエストの通信を許可する。ここで、Ｃ（０≦Ｃ≦１）を以下のように求める。ターゲット負荷度の上限αＨとターゲット負荷度の下限αＬを定めておく。このとき、αＬ≦Ｌ≦αＨならば、負荷が正常範囲にあるとみなす。次に、定期的にＬを取得する。Ｌの値がＬ＞αＨならば、リクエスト量を減らして負荷が低くなるように、Ｃを増加させる。一方で、Ｌ＜αＬならば、リクエスト量を増やして負荷が高まるように、Ｃを減少させる。例えば、増減幅をΔＣとすると、Ｃの増加時にｍｉｎ（１，Ｃ＋ΔＣ）で、Ｃの減少時にｍａｘ（０，Ｃ−ΔＣ）で更新できる。また、係数ｋ（ｋ＞１，０）を設定しておき、Ｃの増加時にｍｉｎ（１，ｋＣ）で、Ｃの減少時に（１／ｋ）ＣでＣを更新してもよい。
【００９５】
次に、リクエストスケジューリング部５内において、キュー制御を行う場合の実施例を示す。図１７は、キュー制御を行うリクエストスケジューリング部５のブロック図である。
【００９６】
リクエストを受信すると、リクエスト分配部１６で、リクエストの進行度に応じて、その格納先キュー１９−１〜１９−ｎを選択する。キューの格納先の指定例を図１６に示す。キューが最大長に達している場合は、受信したリクエスト、または、キュー中のいずれかのリクエストを、キューを用いない方法と同様に、廃棄、拒絶、または転送する。また、各リクエストにタイムアウトを設定てしおき、キュー中にタイムアウトに達したリクエストを検出したら、そのリクエストを拒絶してもよい。キュー１９−１〜１９−ｎにおけるリクエストの順序は、ＦＩＦＯを用いてもよい。また、リクエスト毎に異なるタイムアウトを設定し、タイムアウトまでの時間長が昇順となるようにリクエストを並べるＥＤＦ(Earliest Deadline First)を用いてもよい。
【００９７】
次に、リクエスト送信判定部１７において、負荷度に応じて、サーバアプリケーションにリクエストを送信すべきタイミングを決定する。そして、送信すべきタイミングとなった時点で、リクエストの送信要求をリクエスト選択部１８に発行する。リクエスト送信判定部１７の実施例を以下に示す。
・負荷度Ｌが予め設定した閾値を下回り、かつ、キュー中にリクエストが存在する場合に次の送信要求を発行する。
・リクエスト送信判定部１７が送信要求をλ（ｒｐｓ）のレートで発行する。ただし、キュー中にリクエストが存在しない場合は、送信要求の発行を取りやめる。さらに、負荷度Ｌに応じてλを調整する。例えば、負荷度のターゲット値の上限αＨと負荷度のターゲット値の下限αＬとを定めておく。このとき、αＬ≦Ｌ≦αＨならば、負荷が正常範囲にあるとみなす。次に、定期的にＬを取得する。Ｌ＜αＬならば、λを増加させ、Ｌ＞αＨならば、λを減少させる。例えば、増減幅をΔλとすると、λの増加時はλ＋Δλで、λの減少時はｍａｘ（０，λ−Δλ）で更新する。また、係数ｋ（ｋ＞１．０）を設定し、λの増加時はｋλで、λの減少時は（１／ｋ）λで更新することもできる。
【００９８】
リクエスト選択部１８は、リクエスト送信判定部１７から、リクエスト送信要求を受け取ると、リクエストを取り出すキュー１９−ｈ（ｈは１〜ｎのいずれか）を選択する。選択方法として、リクエストが存在するキューのうち最も優先度が高いキューを選択するＰｒｉｏｒｉｔｙ  Ｑｕｅｕｉｎｇ、キュー毎に重みをつけてレート制御するＷａｉｔｅｄ  Ｆａｉｒ  Ｑｕｅｕｉｎｇ、Ｗａｉｔｅｄ  Ｒｏｕｎｄ  Ｒｏｂｉｎなど、既存のキューイング手法を利用できる。例えば、図１６の設定で、かつ、Ｐｒｉｏｒｉｔｙ  Ｑｕｅｕｉｎｇを用いる場合は、各キューは、キュー６、５、４、３、２、１、０の順で優先度が高くなるように設定する。これにより、最も進行度が高いリクエストが存在するキューが選択されるようになる。リクエストの選択が完了すると、選択したキューに対して送信要求を発行し、キューの先頭のリクエストを取り出し、Ｗｅｂアプリケーションに対して送信する。
【００９９】
本発明の効果をシミュレーションによって評価する。本発明は、過剰リクエスト時におけるセッション処理性能の維持を目的として、進行度が高いセッションに属するリクエストを優先処理する。そこで、多数のクライアントが同一のサーバに対してほぼ同時刻に一斉にセッション処理を開始する場合を想定する。そして、全クライアントがセッション処理を完了するまでをシミュレーションし、サーバが単位時間あたりに処理できたセッション数を評価する。
【０１００】
評価対象の構成を図１８に示す。本構成では、複数のクライアント２０−１〜２０−ｎが一つのサーバ２１に接続される。各クライアント２０−１〜２０−ｎは予め定められた行動シナリオに基づき、リクエストを送信する。サーバ２１は、各クライアントから受信したリクエストを、図１７で示したリクエストスケジューリング部５を用いて逐次的に処理する。また、ＣＰＵ２３上で同時に実行可能なリクエスト数を１とし、負荷度としてサーバ２１のＣＰＵ２３で実行中のリクエスト数（０または１）を評価する。すなわち、ＣＰＵ２３で実行中のリクエスト数が０となると、リクエスト送信要求が発行される。そして、キュー２２中のリクエストが一つ取り出され、サーバ２１のＣＰＵ２３に送信される。ＣＰＵ２３上でリクエストの処理が完了すると、サーバ２１は送信元のクライアント２０−ｈにレスポンスを返送する。クライアント２０−１〜２０−ｎとサーバ２１との間の伝送遅延は１ｍｓで一定とする。
【０１０１】
クライアント２０−１〜２０−ｎの行動シナリオについて説明する。クライアント２０−１〜２０−ｎは、シミュレーションが開始されると、図２０の例で示した、全６ページから構成されるセッション処理を試みる。図２０のセッション処理以外のページにアクセスするクライアントは存在しないものとする。セッションの各ページあたりのリクエスト回数は１とする。また、サーバ２１のＣＰＵ２３が各リクエストに要する実行時間は、リクエストの種別によらず、全て５０ｍｓとする。クライアント２０−１〜２０−ｎは、先頭の「カタログページ」からアクセスし、順に、「商品詳細」、「買物カゴ」、「ユーザ情報入力」、「最終確認」ページにアクセスし、最後に、「購入完了通知」ページにアクセスすることで、セッションを完了する。図２０では、「買物カゴ」から「カタログ」へのページ遷移など後戻りが可能である。しかし、本評価では、このような後戻りはないものとする。
【０１０２】
本評価では、１）シミュレーションが開始されてからクライアントが先頭ページにアクセスするまで、および、２）あるページを取得してから次のページへのリクエストを発行するまでに、思考時間を設けている。思考時間は、平均１０（ｓｅｃ）の指数分布に従うものとする。さらに、あるページにリクエストを発行してから、一定時間以内にレスポンスが返ってこなかった場合は、タイムアウトとみなす。タイムアウトが発生した場合は、セッションを先頭ページからやり直す。本評価では、タイムアウト時間を８秒とする。
【０１０３】
評価に用いたキューの構成は以下の２つである。
・ＦＩＦＯ：最初に届いたリクエストからサーバで処理させる。キューの最大長を８０とする。リクエスト数が８０を超えた場合は、新しく取得したリクエストを廃棄する。
・本発明：本発明に基づき、設定された進行度が高いページへのリクエストを先にサーバで処理させる。進行度は図１２の表に基づいて評価する。ただし、本評価では、セッション処理のページ遷移に後戻りや分岐がない。故に、進行度評価部の実施例１〜３のいずれを用いても、本シミュレーション結果と同様の結果を得ることができる。また、リクエストのキューへの割当ては図１６の表に従うものとし、リクエストを取り出すキューの選択方法としてＰｒｉｏｒｉｔｙ  Ｑｕｅｕｉｎｇを用いる。これにより、異なるページへのリクエストは全て異なるキューに格納され、かつ「最終確認」ページに近いリクエストほど、優先的にＣＰＵ上で処理されることになる。キューに格納できるリクエスト数は、ＦＩＦＯと同じく８０とする。各キュー中のリクエスト数の合計が８０を超えた場合は、進行度が最も低いリクエストの中で、最もサーバに遅く到着したリクエストが廃棄される。
【０１０４】
各手法のセッション処理性能（単位時間あたりのセッション完了数）を図１９に示す。図１９は横軸にクライアント数をとり、縦軸にセッション処理性能をとる。クライアント数が少ない領域ではＦＩＦＯ、本発明、共に、クライアント数の増加にともなって思考時間によるサーバ空き時間が減少していくため、セッション処理性能が増加する。クライアント数が５００を超えると、キューの溢れによるタイムアウトが生じ始める。ＦＩＦＯでは、各セッションでタイムアウトが同じ確率で生じるため、クライアント数の増加にともないセッション性能は低下していく。そして、およそ４０００クライアントでセッションが全く完了しなくなる。一方で、本発明では、より進行しているセッションのリクエストが保護されるため、クライアント数の増加に関わらずセッション性能をほぼ一定に維持できている。本評価モデルにおける理想的なセッション処理性能は３．３３(session/sec)である。
【０１０５】
３．３３(session/sec)＝１０００（ｍｓ）／（５０（ｍｓ）×６（ページ））
本発明によるセッション処理性能は４０９６クライアントで３．２４（session/sec)であり、本モデルの理論値である３．３３(session/sec)とほぼ等しい。以上の結果は、本発明の有効性を示すものといえる。
【０１０６】
また、本実施例は、汎用の情報処理装置にインストールすることにより、その情報処理装置に、本実施例の実行制御装置に相応する機能を実現させるプログラムとして実施することができる。このプログラムは、記録媒体に記録されて情報処理装置にインストールされ、あるいは通信回線を介して情報処理装置にインストールされることにより当該情報処理装置に本実施例の実行制御装置に相応する機能を実現させることができる。
【産業上の利用可能性】
【０１０７】
本発明によれば、処理を実行するサーバにおける計算リソースを有効に活用でき、また、過剰に処理の実行を要求された場合でもサーバの処理性能の低下を防ぐことができ、高いスループットを維持できるので、ネットワーク運用者がネットワークを効率よく運用することに寄与し、また、ネットワークユーザの利便性の向上に寄与することができる。
【図面の簡単な説明】
【０１０８】
【図１】本実施例の実行制御装置のブロック図。
【図２】リクエスト制御部のブロック図。
【図３】進行度評価部の実施例１のブロック図。
【図４】ページ表の登録例を示す図。
【図５】進行度評価部の実施例２のブロック図。
【図６】セッション表の実施例を示す図。
【図７】セッションＩＤ格納先の設定例（リクエスト）を示す図。
【図８】セッションＩＤ格納先の設定例（レスポンス）を示す図。
【図９】セッションＩＤ検査部の処理手順を示すフローチャート。
【図１０】セッション状態遷移図。
【図１１】状態遷移確率表を示す図。
【図１２】最終ページまでの遷移回数と進行度を記録した表を示す図。
【図１３】進行度評価部の実施例３のブロック図。
【図１４】セッション表の実施例２を示す図。
【図１５】進行度と負荷度に基づくリクエストの送信許可・拒絶を判定するための表を示す図。
【図１６】進行度に基づくキュー割当表を示す図。
【図１７】キュー制御を行うリクエストスケジューリング部のブロック図。
【図１８】評価対象の構成を示す図。
【図１９】シミュレーションによる評価結果を示す図。
【図２０】セッション処理の具体例を示すフローチャート。
【図２１】リクエスト過剰によるＷｅｂサーバの処理性能低下の状況を示す図。
【符号の説明】
【０１０９】
１  リクエスト制御部
２  Ｗｅｂアプリケーション部
３  負荷監視部
４  進行度評価部
５  リクエストスケジューリング部
６  ページＩＤ検査部
７  進行度読み出し部
８  セッションＩＤ検査部
９  セッション進行検査部
１０  ページＩＤ検査部
１１  進行度読み出し部
１２  進行度補正部
１３  セッションＩＤ検査部
１４  リクエスト数カウント部
１５  進行度計算部
１６  リクエスト分配部
１７  リクエスト送信判定部
１８  リクエスト選択部
１９−１〜１９−ｎ、２２  キュー
２０−１〜２０−ｎ  クライアント
２１  サーバ
２３  ＣＰＵ
【図１】
2007233559.tif 000003
【図２】
2007233559.tif 000004
【図３】
2007233559.tif 000005
【図４】
2007233559.tif 000006
【図５】
2007233559.tif 000007
【図６】
2007233559.tif 000008
【図７】
2007233559.tif 000009
【図８】
2007233559.tif 000010
【図９】
2007233559.tif 000011
【図１０】
2007233559.tif 000012
【図１１】
2007233559.tif 000013
【図１２】
2007233559.tif 000014
【図１３】
2007233559.tif 000015
【図１４】
2007233559.tif 000016
【図１５】
2007233559.tif 000017
【図１６】
2007233559.tif 000018
【図１７】
2007233559.tif 000019
【図１８】
2007233559.tif 000020
【図１９】
2007233559.tif 000021
【図２０】
2007233559.tif 000022
【図２１】
2007233559.tif 000023