確率モデルにおける性能の最適化

確率モデルにおける性能の最適化とは

どのようにリクエストがあるか(リクエストの確率過程)によって、ウェブシス テムの性能(例えばリクエストを処理するのに要する時間、すなわち応答時間)は大きく変 わってきます。したがって、ウェブシステムの性能を知るには、

1. リクエストの確率過程を推定する
2. 推定された確率過程に従って、リクエストを生成する
3. 生成されたリクエストをウェブサーバに与え、その応答時間を測定する

ウェブシステムの性能を測定する目的のひとつに、性能を最大にするような最 適な構成を見出すことがあげられます。例えばウェブシステムには「最大接続 数」、「初期ヒープ・サイズ」、「最大ヒープ・サイズ」、「最大スレッド・ サイズ」、「最大プール・サイズ」などの構成パラメータがありますが、これ らの構成パラメータの値によってウェブシステムの性能は大きく異なり、また 性能を最大にするような構成パラメータの最適値はどのようにリクエストがあ るか(リクエストの確率過程)によって大きく異なってきます。

推定されたリクエストの確率過程のもとで、平均応答時間を最短にするウェブ システムの構成(構成パラメータの値)を求める問題を考えます。原理的には、 全ての可能な構成パラメータの値の組み合わせについて、その平均応答時間を 測定し、平均応答時間の測定値が最短となる構成パラメータの値を見つけるこ とで、最適なウェブシステムの構成が見つかりそうです。ところが、平均の応 答時間を精度良く測定しようとすると、30分くらいの時間が必要になります。 また、構成パラメータが「最大接続数」、「初期ヒープ・サイズ」、「最大ヒー プ・サイズ」、「最大スレッド・サイズ」、「最大プール・サイズ」の5つだ けで、それぞれ「大」「中」「小」の3つの値しかとりえないとしても、3^5 = 243通りの構成が考えられます。これら243通りの構成全てについて、30分間 かけて平均の応答時間を測定しようとすると、243 x 30分 = 5日も要してしまいます。 実際のウェブシステムにおいては、より多くの構成パラメータがあるので、 全てのウェブシステムの構成について性能を精度良く測定することは 現実には不可能であることが用意に想像できるでしょう。

確率モデルにおける性能の最適化のプロジェクトにおいては、 ウェブシステムのように、

• 性能を精度良く測定するのに時間がかかる
• 多数の構成があり、構成によって性能が大きく変わる

目標の一つは、専門家が最適化したウェブサーバの構成よりも良い構成をより 高速に自動的に見つけることです。現在は、専門家が経験と知識そして試行錯 誤によって、ウェブサーバの構成を最適化しています。単に自動化しただけで は、豊富な経験と知識を持つ専門家が見つけるような構成を、自動的に発見す ることはできません。どの構成をどの順番でどのくらいの時間測定するかの 指針を科学的に与えることで、専門家の職人技を凌駕することを目指します。

確率モデルにおける性能の最適化はウェブシステムに限らず、 その他のコンピュータシステム、コールセンターなどのサービスシステム の性能の最適化に広く応用が考えられます。

これまでの研究成果：最適なシステム構成を高速に選択

これだけ候補となるシステム構成が少なくても、それぞれのシステム構成の性 能を30分間かけて高い精度で測定しようとすると、243x30分=5日もかかってし まいます。もっと短い時間しか使えなければ、測定時間を短くするか、一部の システム構成だけしか測定しないことが考えられます。しかし、測定時間を短 くすると、精度が低くなってしまい、誤った選択をしてしまいます。また、一 部のシステム構成だけしか測定しないと、最適なシステム構成が測定されず、 最適なシステム構成として選択されないことがあります。

私たちのアルゴリズムは、全てのシステム構成を測定するけど、どれも高精度 で測定するわけではなく、それぞれのシステム構成を最低限の精度で測定する、 というものです。例えば、極めて性能の悪いシステム構成であれば15分程度測 定した段階で、最適なシステム構成ではないと精確に判定できるかもしれませ ん。15 分程度ではその性能は精確に測定できていませんが、「最適なシステ ム構成ではない」という判定は精確にできるということです。この原理を最大 限に利用して、それぞれの性能は精確に測定しないけれども、精確に短時間で 最適なシステム構成を選択するアルゴリズムができます。

このアルゴリズムで重要になるのは、どのような基準で「最適なシステム構成 ではない」と判定するかです。できるだけ測定時間が短くなるように、かつ誤っ た判定をしないように基準を設けることが必要です。私たちのアルゴリズムで はその基準に図のような三角形を使います。これまでに測定されたシステム構 成の中で最も性能が良かったシステム構成の性能の測定値と、現在測定してい るシステム構成の性能の測定値の差を比較していきます。図の赤い折れ線はそ の測定値の差を縦軸に、測定時間を横軸にして示してあります。

性能の差が三角形の中にある限り測定を続け、性能の差が三角形の外に出たと きに、2つのシステム構成の性能の良し悪しを判定します。三角形の上の方に 性能の差のグラフが出て行ったときには、現在測定しているシステム構成のほ うが性能値が大きいと判定します。例えば、性能値がスループットを表してい るなら、現在測定しているシステム構成のほうがこれまでに最も性能が良かっ たシステム構成よりも性能が良いと判定されます。反対に、三角形の下の方に 性能の差のグラフが出て行ったときには、現在測定しているシステム構成のほ うが性能値が小さいと判定します。

三角形を用いることによって、必要十分な測定精度が得られたときに性能の良 し悪しを判定できます。すなわち、測定時間が短いときには測定値の精度が低 いので、性能の測定値の差が大きくないと性能の良し悪しを判定しません。長 い間測定を続けるにしたがって測定値の精度が上がるので、性能の測定値の差 が小さくても性能の良し悪しを判定するようになります。

残された問題はどのように三角形のサイズを決めるかです。三角形のサイズが 大きすぎると、性能の良し悪しの判定に時間がかかってしまい、三角形のサイ ズが小さすぎると、誤った判定をしてしまいます。私たちのアルゴリズムでは、 ブラウン運動と正規分布の性質を解析することによって、最適な三角形のサイ ズを求めています。

発表論文

• [TOMACS08] Takayuki Osogami, "Finding probably best systems quickly via simulations," ACM Transactions on Modeling and Computer Simulation, accepted for publication, 2008.
• [QEST07] Takayuki Osogami, "Relations in the central limit theorem version of the response time law," The 4th International Conference on the Quantitative Evaluation of SysTems (QEST 2007) , pages 69-78, Edinburgh, Scotland, September 2007.
• [SIGMETRICS07] Takayuki Osogami and Sei Kato, "Optimizing system configurations quickly by guessing at the performance," The ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS 2007), pages 145-156, San Diego, CA, June 2007.
• [MAMA07] Takayuki Osogami, "Accuracy of measured throughputs and mean response times," The Ninth Workshop on Mathematical Performance Modeling and Analysis (MAMA 2007), San Diego, CA, June 2007; ACM Performance Evaluation Review, 25(2):9-11.
• [SIGMETRICS06] Takayuki Osogami and Toshinari Itoko, "Finding probably better system configurations quickly," The ACM International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS 2006), pages 264-275, Saint-Malo, France, June 2006.
• [MAMA06] Takayuki Osogami, "Finding probably best system configurations quickly," The Eighth Workshop on Mathematical Performance Modeling and Analysis (MAMA 2006), Saint-Malo, France, June 2006; Performance Evaluation Review, 34(3):39-41.