NAP-Web の時間予測に関する評価と優先アクセス機構の設計

11G491 山田茂和 (最所研究室)
本稿では，これまで NAP-Web の時間予測に関する評価が未実施であった項目に関しての実験について述べる．さらに優先アクセスの設計について述べる．

2.

NAP-Web の概要
NAP-Web では次回アクセスを保証するため，ユー
ザからのアクセスをサーバの状態に応じて以下の 4つのグループに振り分け，アプリケーションレベルでスケジューリングを行なっている．
Run_Ready：OS によって通常通り処理が行われる．
Wait：Run Ready からあふれたアクセスが入り，到着順にキューイングされる．Run_Ready に空きができしだい，先頭からRun_Ready に移動する．
Next_Wait：Wait からもあふれたアクセスが入る．
一旦処理を拒絶され，整理券を配布される．
Re_Access：整理券を持ったアクセスが指定された時刻に行われた場合に振り分けられ，Wait に空きができしだい，先頭から Wait に移動する．
NAP-Web の問題点として，Next_Wait で整理券を発行していても Wait に空きがあると初回アクセス(割込アクセス)を受け付けていることが挙げられる．
次節では，割込アクセスに関する実験と，NAP-Webのオーバーヘッドに関する実験について述べる．

10000080000

処理時間(過渡状態）
処理時間（定常状態）
スループット（過渡状態）
スループット（定常状態）

60000
40000
20000
0

次回アクセスまでの時間（秒）3.

図 1.通知時間の頻度
空きメモリ量(掲示板投稿)
4000
空き
メ 3000モ
リ 2000の差 1000

ApacheNAP-Web(MB)NAP-Web の時間予測に関する評価
加地が実装した平均処理時間を用いた時間予測方式[1]と，松浦が実装した平均スループットを用いた時間予測方式[2]をそれぞれ用いた NAP-Web に対して，これまで行なわれていなかった同時接続数 4000という大きな負荷を掛けた場合の評価を行なった．また，平均スループットを用いた場合に NAP-Web のパラメタである Run_Ready の最大処理個数と Wait での最大待ち時間を変更して評価実験を行ない最適なパラメタを調査した．
図 1 に，平均処理時間方式とスループット方式それぞれの，次回アクセスの通知時間の頻度を示す．なお
本稿では，実験開始初期の予測時間のバラツキが大きい期間を過渡状態，予測時間のバラツキが小さい期間のことを定常状態と呼ぶ．平均処理時間方式の過渡状態においてバラツキが顕著であり，定常状態においてもバラツキが残っている．平均スループット方式では過渡状態でのバラツキが抑えられ，定常状態においてはバラツキが大幅に軽減されている．平均処理時間方式では整理券の発行枚数が少なく，一部のクライアントに対して非常に長い時間を通知しているため割込アクセスが多くなっているが，それに対して平均スループット方式では予測が安定し，割込アクセス数が減少しているため公平性が向上している．また，平均スループット方式においてパラメタを変更した実験の結果，今回の実験において最適なパラメタはRun_Ready の最大処理個数が 10 個，Wait での最大待ち時間が 4 秒であることを確認した．
図 2 はオリジナルの Apache と NAP-Web それぞれについて，同時接続数を変えメモリ使用量の調査を行なった結果を示す．NAP-Web は Apache と比較してメモリ使用量が大きいことが確認できる．また，同時接続数が 1000 以降はそれ程変化していないことが分かる．この実験では Wait と Re_Access キューに入る
アクセス数は最大でも約 1000 アクセスとなっており，それ以上のアクセスは整理券によって次回アクセスに回されている．このことから，キューでサスペンド

10以下
2030405060708090100110120130140150160
170180
190
200
210以上

はじめにWeb サーバへのアクセス集中によるレスポンス性能低下の不満を解決するため我々の研究室では，次回アクセス時間を通知し，その時間に行われるアクセスを 受 け 付 け る こ と を 保 証 す る Web シ ス テ ム
NAP-Web（Next Access Promised - Web）[1]の開発が行なわれた．さらに，従来の NAP-Web における問題点であった時間予測精度やアクセスの公平性についての改良と，その評価が行なわれた[2]．
しかし，これまでの評価では，サービスの公平性やNAP-Web のオーバーヘッドなどの項目が不十分であった．そこで本研究では，それらの項目に関して評価実験を行なった．さらに，当研究室で研究を行なっている分散 Web システムや，会話的なサービスへの対応を目的とし，優先アクセス機構の設計を行なった．

頻度

1.

0010002000
同時アクセス数

30004000

図 2.掲示板投稿実験での空きメモリ量

状態となっているプロセスが使用メモリの増加につながっており，整理券の発行枚数は影響していないことが確認できた．なお，単位時間あたりの処理個数は掲示板投稿実験では 1 割程度のオーバーヘッドが確認できた．ファイル取得実験では逆に NAP-Web の方が良い結果となった．これは，ファイル取得によってディスク I/O に負荷が掛かった結果，同時処理数をRun_Ready で一定に保っている NAP-Web は影響を軽減でき，Apache ではサーバ全体の性能が悪化したためと考えられる．
4.

優先アクセス機構の設計
4.1 優先アクセス機構の目的●分散 Web システムへの対応
当研究室ではキャッシュサーバを用いた分散 Webシステムの研究を進めている[3]．優先アクセス機構
では，キャッシュサーバからのキャッシュ更新を優先して行なう機能を実現する．
●会話的なサービスへの対応
会話的なサービスを提供する場合は，初めに行なわれたアクセスからサービスの提供完了まで，一連のアクセスに対するレスポンスを保証しなければならない．このため，優先アクセス機構では一連のアクセスに対して優先して処理を行なうことを実現する．
4.2 優先アクセス機構の概要
優先アクセス機構は，処理待ちのためのキューイングを行なっている Wait と Re_Access という今までのスケジューリンググループに加えて，優先的に処理すべきアクセスを受け入れてキューイングするための新たなグループを追加することで実装できる．新たなグループに振り分けられたアクセスを，Wait よりも優先的に Run_Ready へ移動させることによって，優先的に処理を行なうことができる．
図 3 に優先アクセス機構の概要図を示す．既存のキューである Wait と Re_Access と同じ構造のキューを，新たに並列に追加することで，従来のアクセススケジューリングと並行して優先アクセスを処理することが可能となる．
キャッシュサーバの更新と会話的なサービスに関しては，それぞれ別なキューを用意することで，それぞれの優先度を変えることができる．どのキューに割り振るかをスケジューラで決定する方法としては，キRun_Ready

Wait

Re_Access

キャッシュ
サーバ用

Next_Wait

セッション
保護
Etc…

新たに追加する
優先アクセス用
スケジューリンググループ

スケジューラ図 3.優先アクセス機構の概要

ャッシュサーバに関しては指定ポートを使った通信と IP アドレスによって判別が可能である．会話的なサービスに関しては，あらかじめ特別なディレクトリにリソースを置き，一度ディレクトリ下のリソースにアクセスしたクライアントに対して，IP アドレスから生成した ID を Cookie で配布することで，優先アクセスであると判別することが可能である．
4.3 優先アクセス機構の検討事項
優先アクセスのそれぞれの優先度は同一ではないと考えられる．例えば，分散 Web システムにおけるキャッシュの更新は最優先で行なわなければならな
い．優先アクセス機構では用途に合わせたキューを複数実装することを提案したが，それぞれのキューの優先度を設定すべきであると考えられる．複数キューから Run_Ready キューへと，優先度を考慮してアクセスを移すアルゴリズムについての検討を行なった結果，以下に挙げたアルゴリズムを用いることとした．
①キュー毎に変数を用意し，優先度として値を設定する．
②最大値の大きなキューのリクエストを処理し，変数を 1 減算する．全ての変数が 0 になるまでこれを繰り返す．
③ ①に戻る．
さらに，②の処理中に変数が同じ値になった場合に備えて，各キューに処理が行なわれなかった回数のカウンタを備えておく．変数が同じ値になった時，カウンタを比較することで，優先度の高いものを優先しつつ，全体の処理を行なうことができる．
5.

おわりに平均スループット方式は，平均処理時間方式に比べて予測時間のバラツキが少なく，公平性が高くなっていることが確認できた．また，今回の環境では
Run_Ready の最大処理個数を 10 とし，Wait での待ち時間を 4 秒としたもので最も良い結果が確認できた．また，オーバーヘッドを調査した結果，使用メモリ量は Wait および Re_Access キューのアクセス数に比例して増加し，整理券の発行枚数とは関係がないことを確認できた．掲示板投稿実験において NAP-Webのオーバーヘッドが大きいことが確認できたが，NAP-Web はユーザの不満軽減が目的であるため，問題ないと考えている．
また，新たに NAP-Web に追加する優先アクセス機構の設計について述べた．本研究では優先アクセスに用いるキューの設計を行ない，優先アクセスを決定するアルゴリズムについての検討と，キュー毎の優先度に対しての検討を行なった．
今後の課題は、優先アクセス機構の実装である。
参考文献[1] 加地智彦，最所圭三, “過負荷時のユーザの不満を抑えるために次回アクセスを保証する Web システム”， 情処学論，Vol50，no.2, pp-872-881, 2009[2] 松浦正尚. "次回アクセスを保証する Web システ
ムにおけるアクセススケジューリング機構の改良",
香川大学工学部, 学士論文, 2012
[3] 小笹光来, 最所圭三, “クラウドに適した Web シ
ステムについて” 平成 24 年度電気関係学会四国支部連合大会, 17-14, p360, 2012