ProxyサーバにおけるWebキャッシング効率の評価と分析 096036 加藤

平成１２年度卒業研究発表会(日本大学工学部情報工学科)
B-5
ＰｒｏｘｙサーバにおけるＷｅｂキャッシング効率の評価と分析
Evaluations of Web Caching Efficiency in Proxy Server
０９６０３６
加藤
１．はじめに
現在、インターネットユーザは爆発的な増加の一途
を辿っており、主に Web によるサービスを利用するユ
ーザが急増している。さらに Web で使用されるコンテ
ンツのマルチメディア化に伴って、扱う情報量も増大
している。そのため、レスポンスの悪化や、LAN や
Web サーバ、インターネット全体の負荷の問題が顕著
となっている。
これらの問題の改善策として、クライアントが Web
サーバへコンテンツの取得をリクエストする際、Proxy
サーバのキャッシュを利用する方法が採用されている。
Proxy サーバにおけるキャッシングによって、頻繁にア
クセスされる Web コンテンツを Proxy サーバに保存し、
再利用することにより、Web サーバへのリクエストを
減少させることでき、Web サーバやネットワークの負
荷を軽減することができる。
しかし、キャッシュスペースには物理的な限界があ
るため、その有効利用を図るためには、何らかのアル
ゴリズムに基づいて、将来参照されることがないと判
断したドキュメントをキャッシュから削除する必要が
ある。このアルゴリズムは、置換ポリシーと呼ばれて
おり、現在までに様々な置換ポリシーの提案がなされ
てきたが、その定量的な評価はあまり行われていない
のが現状である。
本研究では、各種置換ポリシーについて、Proxy サー
バでのキャッシュヒット率と Web へのアクセス特性か
ら評価し、その有効性を明らかにすることを狙いとし
ている。
２．置換ポリシー
置換ポリシーついては、種々の方式が提案され実際
に用いられている。ここでは、代表的な置換ポリシー
ついて解説する([1])。
(1) Least Recently Used (LRU)
LRU は、最近参照されたドキュメントを優先的にキ
ャッシュし、長期間参照されないドキュメントを削除
する方法である。これは最近参照されたドキュメント
ほど参照される可能性が高いことに着目した方法で、
アルゴリズムが単純で容易に実現できるため、一般的
に良く用いられている。
(2) Least Frequently Used (LFU)
LFU は、キャッシュされているドキュメントの参照
回数が少ないものから削除し、参照回数の多いドキュ
メントをキャッシュする方法である。この方法には、
キャッシュに存在するドキュメントの参照回数だけを
保持する In-Cache-LFU と、今までキャッシュしたこ
とのあるすべてのドキュメントの参照回数を保持する
Perfect-LFU という方法が考えられている。
(3) LFU with Dynamic Aging (LFUDA)
LFU の問題点として、参照頻度が高かったドキュメ
ントが後々参照されなくなった時、そのドキュメント
の参照回数が多いと、キャッシュから削除されにくい
という点にある。そこで、ドキュメントのアクセス頻
度と、その最終アクセス時刻から算出した年齢を考慮
する LFU-Aging ポリシーが考案された。LFUDA は、
LFU-Aging ポリシーをベースとしたものである。具体
智志
［竹中研究室］
的には、ドキュメントがキャッシュに保存された時、
または、キャッシュに存在するドキュメントが参照さ
れた時に、参照されたドキュメント i のキー値Ｋi を、
ドキュメント i の参照回数を Fi、最後に削除されたド
キュメントのキー値をＬとし、
Ki
=
Fi
+
L
から求める。キャッシュからドキュメントを削除する
ときは、キー値の小さいものから削除する。
(4) SIZE
SIZE は、ドキュメントのサイズが大きいものから削
除し、より多くのドキュメントをキャッシュに保持す
ることでヒット率を高める方法である。しかし、ヒッ
ト率は高くなるものの、結果的にサイズの大きいドキ
ュメントは Web サーバから得ることになり、ネットワ
ークの負荷を軽減できず効果的ではない。
(5) Greedy Dual-Size with Frequency (GDSF)
GDSF は、サイズの小さい、出来るだけ参照されや
すいドキュメントをキャッシュし、キャッシュヒット
率を向上させる方法である。LFUDA と同様に、キャッ
シュ内のドキュメント i のキー値 Ki は、ドキュメント
i のサイズを Si とすると、
Ki
=
Fi
/ Si
+
L
から求められる。L は、最後に削除されたドキュメント
のキー値である
(6) Zipf の法則に基づくポリシー
Web のアクセス頻度分布は、Zipf の法則に従うこと
が知られている。この法則を用いて、参照頻度の高い
ドキュメントをキャッシングする方法である。
現在、フリーProxy サーバとして広く使用されている
Squid では LFUDA と GDSF が採用されており、Proxy
サーバ運用者が選択出来る。
３．Web のアクセス頻度分布の評価
Web のアクセス頻度分布が、Zipf の法則に従うか否
かを検証するために、Proxy サーバへのアクセスログを
用いてアクセス頻度分布の評価を行った。
使用するログは、1998 年 7 月 14 日から 8 月 8 日まで
日本大学工学部情報工学科で稼働していた Squid が出力
したログを用いた。このログから得られたアクセス頻度
分布を図１に示す。
図１
アクセス頻度
Zipf の法則とは、ある事象が起こる頻度を f とし、ｆ
を降順に並べた場合の順位を i とすると、ｆと i の間には、
Ｃ，ｋを定数とした場合、
平成１２年度卒業研究発表会 B-5
f
=
c
i
k
の関係が成り立つことである。Zipf の法則が Web ペー
ジのアクセス頻度と合致することについては、文献[2]
等で確認されているが、図１から収集したアクセスロ
グのアクセス頻度は、k=１の Zipf 則にほぼ従っている
ことがわかる。
４．置換ポリシーの評価
各置換ポリシーを用いた場合のアクセス特性の評価
をシミュレーションにより行う。今回シミュレーショ
ンで使用したポリシーは LRU、LFUDA、GDSF、Zipf
の法則に基づくポリシーの４種類である。
シミュレータは Ruby 環境下で作成した。シミュレ
ーションの条件として、伝送路の速度は Client−Proxy
間を 10Mbps、Proxy−WWW Server 間を 4Mbps とし
た。シミュレーションモデルを図 2 に示す。
図２
シミュレーションモデル
４．１ アクセス頻度の評価
図３に各置換ポリシーのヒット率を示す。横軸に総
リクエスト数、縦軸にヒット率を示している。なお、
キャッシュサイズは 100Mbyte とした。
この図から、Zipf 則によるポリシーのヒット率が最
も良いことがわかる。これは、Proxy サーバがアクセス
頻度の統計的性質を完全に知っており、この性質に従
ってキャッシュしているためである。この値はヒット
率の上限を与える。しかし、Proxy サーバがアクセス頻
度の統計的性質を完全に知るためには、定常状態にお
いて長時間測定する必要がある。
図４にドキュメントの参照頻度比率を示す。横軸に
リクエスト回数からなる順位、縦軸に Zipf でのリクエ
スト回数で正規化したドキュメント参照率を示してい
る。この図から、GDSF の参照頻度比率は LFUDA よ
り高い。
図５に各置換ポリシーのバイトヒット率(総伝送ドキ
ュメントサイズに対する、キャッシュヒットした総ド
キュメントサイズの比率)を示す。横軸に総リクエスト
数、縦軸にバイトヒット率を示している。なお、キャ
ッシュサイズは 100Mbyte とした。
この図から、Zipf 則に基づく置換ポリシーが最も良
いことが分かる。理由は 4.1 と同様であり、Zipf 則に
基づくポリシーはバイトヒット率の上限を与える。ま
た、総合的に見て GDSF よりも LFUDA の方がバイト
ヒット率は高くなると言える。なお、総リクエスト数
が 80000 付近で各ポリシー共にバイトヒット率が大幅
に低下しているのは、この期間に大容量のドキュメン
トが連続してダウンロードされた結果、キャッシュス
ペースが圧迫されたためである。
平均アクセス遅延時間を図６に示す。この図の横軸
はキャッシュサイズ、縦軸は平均遅延時間である。シ
ミュレーションでは、単位時間あたりの転送量から、
純粋に置換ポリシーに起因する遅延時間を測定できる
ように伝送路の転送速度を設定している。
この図から、GDSF は、キャッシュサイズが小さい
場合は効率的なキャッシングを行うが、キャッシュサ
イズが大きくなると他のポリシーよりも悪化している。
これは、GDSF が SIZE と同様に、サイズの小さいド
キュメントをキャッシュに保持しようとする結果、サ
イズの大きいドキュメントを Web サーバから取得する
ため、遅延時間が他ポリシーよりも大きくなるためで
ある。
図５
図６
バイトヒット率
平均アクセス遅延
５．むすび
図３
図４
ヒット率
参照頻度比率
これは、GDSF が LFUDA に比べ参照される可能性
のあるドキュメントをキャッシュに保持していること
を意味し、その結果としてヒット率が高くなっている。
４．２ アクセス遅延の評価
本研究では、Web サーバへのアクセス頻度特性につ
いてアクセスログを用いて評価し、Zipf の法則に従っ
ていることを明らかにした。また、シミュレータによ
り、キャッシュの各種置換ポリシーについてキャッシ
ュヒット率、Web サーバへのアクセス特性から評価を
行った。その結果、各置換ポリシーの有効性を明らか
にした。今後は、こうした方式の特性の理論解析を進
めるとともに、さらに効率的な置換ポリシーの考案を
行う。
参考文献
[1] M. Arlitt ”Evaluating Content Management
Techniques
for
Web
Proxy
Caches”
http://www.hpl.hp.com/techreports/98/HPL-98-17
3.html
[2]醍醐 隆行, “ユーザの Web アクセス特性の局所生に
基づくキャッシュシステムの構築” 電子情報通信学
会信学技報 IN98-161, pp.35-42, 1999.2