過負荷時のWebアプリケーションの性能劣化を改善する Session-level Queue Scheduling 東京工業大学大学院　情報理工学研究科 数理・計算科学専攻　千葉研究室 松沼正浩　指導教官:千葉滋 修士論文発表

セッション処理性能の重要性 消化セッション数がサイトの利益に直結 セッション処理とは？ 複数のWebページを通して行う処理 例:ログインからログアウトまでの一連の処理 最後のページ(ログアウト)まで処理して完了 例：商用サイトの物品購入アプリケーション セッション ログ イン 商品 検索 商品 決定 購入 送信 ログ アウト ページ 修士論文発表

過負荷時のセッション処理性能 リクエスト殺到時には増加比率以上に低下 処理性能低下の原因は 成功 10倍のリクエストで100分の1以下の性能になることも 一定の数を超えるとセッション処理性能がゼロになる場合も 処理性能低下の原因は リソース競合による各ページの処理性能の低下 途中失敗の増加によるセッション完了数の低下 成功 殺到 購入完了 ログイン 空き状況 観戦予約 修士論文発表

原因1:ページ処理性能の低下 リクエスト殺到時にページ処理性能が低下 各ページのリソース競合を解消する必要 計算リソースが競合するため 重いページの並列処理によりリソースが不足 大規模アプリケーションが増加傾向 競合にともなう余計な処理増加 例:メモリ競合によりGC,スワップイン・アウト増加 各ページのリソース競合を解消する必要 ページ処理性能が低下すると、集合体であるセッションの処理性能も低下 修士論文発表

原因2:セッションの途中失敗 過負荷時にセッションが途中失敗する可能性大 セッションの途中失敗を抑制する必要 ページの処理失敗が原因 サーバタイムアウトやブラウザタイムアウト Safari 1.2.3で1分、Mozilla系ブラウザでは2分 ユーザが待ちきれずにリクエストを中止 11秒以上待たされるとイライラを感じる[Jakob’02] ページの数だけ失敗する危険性も高まる 重要な処理ほどセッションが長くなる[Cherkasova’98] セッションの途中失敗を抑制する必要 途中で失敗するとそれまでの処理が全て無駄になる 修士論文発表

Session-level Queue Scheduling の提案 ページ単位制御とセッション単位制御の両方を連動 ユーザの挙動を考慮したスケジューリング シンクタイム 次のページに移動するまでの時間 タイムアウト 一定時間以内にレスポンスが得られない場合にリクエストを中断 途中退場 正規手続きを踏まずに途中でセッション処理を中断 セッション スケジューラ ページ スケジューラ ページ スケジューラ ページ スケジューラ 修士論文発表

ページスケジューラ ページ単位で並列度を設定してリソース競合を解消 並列度は各ページの進捗状況により決定 リソース競合を起こさない最大の並列度を動的に決定 並列度をこえるリクエストはページキューで待機させる 並列度は各ページの進捗状況により決定 Progress-based Regulation [Douceur’99] を応用 進捗が悪化しているとリソース競合を起こしていると判定 個別のリソースを監視する必要はない 進捗状況を フィードバック リクエスト ページスケジューラ 　３ ページキュー 進捗測定 並列制御 クライアント 処理実行

セッションスケジューラ 同時に処理するセッション数を制御 同時セッション数の動的な決定 制御はセッション参加時の1回のみ キュー 同時に処理するセッション数を制御 同時セッション数の動的な決定 ページスケジューラからの情報を利用 ページキューの長さを一定に保つ キューが長い：途中失敗の可能性大 キューが短い：リソース使用の効率低下 制御はセッション参加時の1回のみ 許可を得られるまで、リクエストはセッションキューで待機させる キューの長さを フィードバック セッションスケジューラ ページ スケジューラ 修士論文発表

セッションスケジューラによる 同時セッション数の制御方法 リクエストの投入間隔(遅延)を制御 長くすれば、同時セッション数が減少 短くすれば、同時セッション数が増加 全てのページキューの長さを監視し遅延を変化 待機リクエスト数の総和が多い＝ページキューが長い 同時セッション数が多すぎると判断し、遅延を長くする 待機リクエスト数の総和が少ない＝ページキューが短い 同時セッション数が少なすぎると判断し、遅延を短くする 修士論文発表

プロトタイプ実装 Tomcat上にて実装 単純なアルゴリズムを用いて効果を検証 ページ単位の並列度の決定 セッション開始の時間的遅れの決定 各ページのスループットを進捗とした セッション開始の時間的遅れの決定 セッション開始時に次回の遅延を変更 ページキューの平均長を算出し、しきい値と比較 しきい値以上なら間隔を長くし、以下なら間隔を短くする 修士論文発表

性能比較実験 同時クライアント数を変動させセッション処理性能を測定 対象アプリケーション クライアントの挙動 商品購入アプリケーションに見立てたServlet群 クライアントの挙動 シンクタイム:一定時間が経過した後で次のページに移動 タイムアウト:リクエストを送ってから一定時間応答がなければリクエストを破棄 リトライ:途中失敗した場合は最初から 5.商品検索 400ms 1.login 30ms ２.閲覧 30ms 3.閲覧 30ms 4.閲覧 30ms 6.購入 30ms ７.logout 30ms 修士論文発表

比較対象 制御なし ページスケジューラのみ使用 セッション参加人数を固定(1or30) セッションを保護しない 途中失敗しない(1) 競合するがシンクタイムを有効利用する(30) サーバ　CPU：Intel Xeon 2.40GHz×2 メモリ：2GB OS：Linux2.4.2ギガビットイーサネット WebAppサーバ:Tomcat3.3.1 クライアント CPU：Intel Xeon 3.06GHz メモリ：2GB　OS：Linux2.6.8　ギガビットイーサネット 修士論文発表

タイムアウトがない場合の性能 ページスケジューラが リソース競合解消 処理が逐次的 スループット[sessions/sec] シンクタイム3秒 タイムアウト無制限 処理が逐次的 タイムアウト1分 シンクタイム3秒 クライアント数

タイムアウトが1分の場合の 性能 過負荷時でも性能維持 途中から急激に 性能が低下 スループット[sessions/sec] シンクタイム3秒 タイムアウト1分 クライアント数

レスポンスタイム (125クライアント) ページ単位・本手法とも レスポンスタイムに関しても向上 タイムアウト1分 シンクタイム3秒 クライアント数 経過時間　[sec]

レスポンスタイム (400クライアント) 本手法のレスポンスタイムは クライアント殺到時でも高性能 タイムアウト1分 シンクタイム3秒 クライアント数 経過時間　[sec]

セッションの途中失敗数 急激に失敗数が増加 ほぼ同比率で増加 失敗の内訳 失敗セッション数 シンクタイム3秒 タイムアウト1分 クライアント数

失敗したページの内訳 クライアント数125の時の失敗数の内訳 クライアント数400の時の失敗数の内訳 ページ番号 1ページ 2~4ページ 5ページ 6~7ページ 制御無し ０ ３ １５０ ページ単位 本手法 150 クライアント数400の時の失敗数の内訳 本手法を用いない場合は、重い処理を行っているページで起きている ページ番号 1ページ 2~4ページ 5ページ 6~7ページ 制御無し ー ページ単位 ０ ７３５ 本手法 ２２６ 本手法を用いた場合には、セッション失敗は 全てセッションの先頭ページでのみ発生した 735 226

スケジューラの挙動の時間変化 セッションスケジューラの挙動 ページスケジューラの挙動 キューが長くなると セッション間隔が伸びる ページキューの長さ セッション間隔　[msec] 並列度 キューが長くなると セッション間隔が伸びる 制御すべきページの並列度 が頻繁に変動 経過時間　[sec] 経過時間　[sec]

タイムアウトを短縮 (1分→30秒) 高い処理性能を依然維持することができた より少ないクライアント数でも タイムアウトが発生する スループット[sessions/sec] シンクタイム3秒 タイムアウト30秒 より少ないクライアント数でも タイムアウトが発生する クライアント数

シンクタイムを短縮 (3秒→1秒) シンクタイムの長さは性能 にあまり影響を与えない スループット[sessions/sec] シンクタイム1秒 タイムアウト1分 シンクタイムの長さは性能 にあまり影響を与えない クライアント数

関連研究 Application-aware admission Control [Carlstorm’02] ページ単位制御、セッション単位制御の組み合わせ それぞれが個別に動作 SEDA Architecture[Welsh’03] リクエスト処理をステージに分割して負荷を制御 より細かいリソース管理を実現 ページスケジューラと直交する ハートビート 通信にタグを埋め込み ブラウザのタイムアウトの抑制 修士論文発表

まとめ Session-level Queue Scheduling[DSW’05]を提案 プロトタイプ実装を用いた実験により有効性を示した ページスケジューラ[SPA’04]とセッションスケジューラを連動させることで過負荷時のセッション処理性能を向上・維持 プロトタイプ実装を用いた実験により有効性を示した ユーザの複雑な挙動を考慮したモデルを使用した性能比較 シンクタイム・タイムアウト・リトライを考慮 過負荷時においても一定のセッション処理性能を維持 単純なアルゴリズムでも効果あり 修士論文発表

今後の課題 より複雑なユーザの挙動を考慮したモデルで対応できるかの確認 修士論文発表