# 論文まとめフォーマット ## どんなもの？ CDNオンメモリのキャッシュヒット率を向上させるためにキャッシュサイズの閾値を動的に変える ## 先行研究と比べてどこがすごい？ Nginx と比較しキャッシュヒット率が 47~91% 高い Vernish と比較しキャッシュヒット率が 30~48% 高い 同様にサイズ制限をかけた SLRU と比較しキャッシュヒット率が 33% 高い ## 技術や手法のキモはどこ？ - キャッシュのヒット率の最適化のために1つのキャッシュに対して動的な容量制限をかけること - 最適なキャッシュサイズを計算するマルコフ連鎖の式 ## どうやって有効だと判断した？ Akamaiのトラフィックデータを用いて、同様のリクエストと生成し検証した。
要約
CDNの最大の目標はキャッシュヒット率の最適化にある。
しかし、ファイルのサイズが異なること、リクエストのパターンが多様であることでこの目標の達成を困難にしている。
例えば、メモリキャッシュのトータル容量が1GBの時に、サイズが100 KiBの小さなオブジェクトが9999個と500MBのファイルが1個あったとする。
これらはすべてにランドロビンで常にアクセスされる時と仮定した場合に、既存のキャッシュアルゴリズムでは、500MBのファイルをキャッシュしてしまい、5000個のオブジェクトがキャッシュから排除され、キャッシュヒット率が50％を超えられない。
そこで AdaptSize ではキャッシュ容量の制限を動的にかけることで、キャッシュヒット率の最大化を行った。
また、トラフィックパターンは日中と夜間によって異なり、日中はニュースサイトなどの小さなファイルで、夜間はwebなどの小さなファイルに加え、動画ファイルなどの大きなファイルがリクエストされる傾向にある。
AdaptSizeはトラフィックパターンに応じて、キャッシュサイズを変更するため、トラフィックパターンの変化にも頑健（ロバスト）である。
AdaptSizeはAkamaiのリクエストトレースを用いて実験したところ、VernishやNginxを用いたキャッシュより30~47ポイントキャッシュヒット率が向上した。
また、導入にあたってスループットが劣化するとはなかった。
他の研究成果であるSLRUやLRU-Sと比較しても33%キャッシュヒット率が改善した。
トラフィックパターンの変化によるキャッシュヒット率の変化
図6:AdaptSizeの比較、Hill Climbキャッシュとシャドウキャッシュによるしきい値調整 (HillClimb) 、トラフィックミックスがwebのみからmixed web/videoトラフィックに変化した場合の静的サイズしきい値 (Static) 。AdaptSizeは新しいトラフィックミックスにすぐに適応しますが、HillClimbは次善の構成にとどまり、Staticは (定義上) 適応しません。このトレースでは、AdaptSizeにより、OHRがHillClimbより20%、Staticより25%向上しています。
Vernish、Nginxとの比較
図10:AdaptSizeの実装と、VarnishおよびNginxの本番システムおよびSIZEOPTの比較。AdaptSizeは、本番システムよりもOHRを30~47%改善し、SIZE-OPTのOHRの99%を達成します。これらの結果はHKトレース用です。USトレースの対応する結果を図4に示す。
bootjp注釈: SIZE-OPTというのは100万回のリクエスト情報の事前知識を用いて、最適化させた際のものなので、ここでは理想的な値のときという解釈でいいと思います。
AdaptSizeを実装したVarnishとVarnishのスループット比較
図12: (a) 100% OHRおよび (b) 0% OHRによるマイクロ実験におけるAdaptSizeおよびVarnishのスループットの比較。シナリオ (a) は、ヒット要求パスをテストし、AdaptSizeとVarnishに違いがないことを示します。シナリオ (b) は、ミス・リクエスト・パスをテストし (リクエストごとにアドミッション決定が必要) 、AdaptSizeとVarnishのスループットが非常に近いことを示します (信頼区間内) 。
他の研究成果のキャッシュとの比較
図5:AdaptSizeと最先端の研究用キャッシングシステムとの比較。これらのほとんどは、最新性と頻度を組み合わせた高度なアドミッションポリシーとエビクションポリシーを使用しています (青色の縞模様のバー) 。AdaptSizeにより、次善のシステムに比べてOHRが46%向上します。「++」 で注釈されたポリシーは、実際には楽観的です。これは、トレースのパラメータをオフラインで調整したためです。これらの結果は、USトレースおよびHOCサイズ1.2 GiBに関するものです。
アルゴリズム
これについては自分の知識が足りずに正確に要約ができなさそうなので、原文 Section 4 をみてください
以下翻訳
AdaptSizeは、e−size/cの確率でオブジェクトを許可し、LRU [43] の同時変数を使用してオブジェクトを削除します。関数e−size/cが、より高い確率で小さなサイズを許容するようにバイアスされていることを観察せよ。 なぜ確率的な入場機能なのか?最も単純なサイズベースのアドミッションポリシーは、 size<cのオブジェクトだけが許可される確定的なしきい値cです。 e−size/cのような確率的アドミッション関数はより柔軟である:cより大きいオブジェクトは低いがゼロではないアドミッション確率を保持し、結果的に人気のあるオブジェクト (人気のないオブジェクトではない) のアドミッションとなる。本実験において、e−size/cは、最良決定性閾値よりも10%高いOHRを一貫して達成する。 AdaptSizeがe-size/c関数で使用するパラメータcは何ですか。AdaptSizeの調整ポリシーは、Δリクエストごとに最適なcを再計算します。自然な方法は、シャドウキャッシュを使用したhill-climbing を使用して、最適なcパラメータを決定することです。 残念ながら、これは、現在のcの局所近傍のみを探索することができるという近視眼的な見方につながる。 これは、OHR-vs-c曲線に存在する非凸性を考慮すると、最適ではない結果になります (図3) 。これとは対照的に、キャッシュの完全マルコフ連鎖モデルを導出した。 このモデルにより、AdaptSizeはOHR-vs-c曲線全体を表示し、最適なcのグローバル検索を実行できます。 Markovモデルアプローチの課題は、迅速に解を見つけるためのアルゴリズムを考案し、そのアルゴリズムを本番システムに組み込むことです。以下では、AdaptSizeのMarkovモデルの導出(第4.1章)と、本番システムへのAdaptSizeの組み込み方法(第4.2章)について説明します。
図8:オブジェクトiのAdaptSizeのMarkov連鎖モデルは、LRUリスト内でのiの位置と、オブジェクトがキャッシュ外にある可能性を表します。各オブジェクトは、別個のマルコフ連鎖によって表されるが、すべてのマルコフ連鎖は、共通の 「プッシュダウン」 速度μcによって接続される。これらのモデルを解くと, cの関数としてOHRが得られる。
