複数の大学・研究機関の研究者らによって、ブラウジング速度を大幅に向上させる新たなアルゴリズムが開発された。「SIEVE」と名付けられた、この非常に効果的でありながら驚くほどシンプルなアルゴリズムは、大規模なWebトラフィックの管理を一変させる可能性を秘めている。
SIEVEは、エモリー大学、カーネギーメロン大学、ペリカン財団のコンピューター科学者の共同プロジェクトである。同チームのSIEVEに関する論文は、4月にカリフォルニア州サンタクララで開催される第21回USENIX Symposium on Networked Systems Design and Implementation (NSDI)で発表される。
SIEVEは、Webキャッシングを処理する新しい方法だ。
我々がWebブラウザを使ってインターネットサーフィンを行うと、画像や、ロゴ、文章など、Webページ全体をサーバーから取得していることはご存じだろう。こうしたオブジェクトは再利用のためにハードドライブに保存される。これは、Webを経由してサーバーからデータを取得するよりも、ユーザー自身のハードドライブからデータを取得する方が圧倒的に早いからだ。
しかし、ローカル・ストレージには限りがあるため、キャッシュ回避アルゴリズムは、オブジェクトをどれくらいの期間保存するか、また、ユーザーがアクセスする頻度の低い古いオブジェクトを、新しいオブジェクトや人気の高いオブジェクト (IT 用語では「ホット オブジェクト」) に置き換えるタイミングを決定するために働く。
ホットオブジェクトをキャッシュすることで、ネットワーク化されたシステムはより効率的に動作し、ユーザーからのリクエストに迅速に対応することができる。Webアプリケーションは、サーバーまで移動してリクエストごとに巨大なデータベースを検索するよりも、手近なローカル・ストレージからユーザーが望むオブジェクトのほとんどを取得することで、より多くのトラフィックを効率的に処理することができる。
しかし、コンピューターサイエンスの分野では、キャッシングは比較的研究されていなかった。
「コンピューターやインターネットが高速である主な理由はキャッシュです。我々は、ソフトウェア・キャッシュは、現代のウェブを機能させるための、どこにでもある、しかし過小評価されている柱であり、そのため、それらに取り組むことは、非常に大きな影響を与える可能性があると感じています」と、論文の共同筆頭著者であるアトランタのエモリー大学の博士課程学生Yazhuo Zhangは、Live Science誌に語っている。
Zhang氏は、エモリーでコンピューターサイエンスの修士号を取得し、現在カーネギーメロン大学の博士候補生であるJuncheng (Jason) Yangと論文の筆頭著者を共有している。
キャッシュの高速メモリは実行コストが高いが、Webユーザーの良いエクスペリエンスには欠かせない。目標は、最も有用で将来必要になる情報をキャッシュ内に保つことである。その他のオブジェクトは、変化するホットオブジェクトのためのスペースを確保するために、継続的に選別され、技術用語では「追い出され」なければならない。
そこで必要となるのが、キャッシュアルゴリズムだ。これは、どのオブジェクトをいつ追い出すかを決定する。
FIFO（First In, First Out: 先入れ先出し）は、1960年代に開発された古典的なページ置換えアルゴリズムである。ベルトコンベアーに並んだオブジェクトがイメージしやすいかも知れない。新しく要求されたオブジェクトは左から入り、古いオブジェクトは右の列の最後尾に達すると追い出される。
LRU（Least Recently Used）は、データが最後に使われたのはいつであるかを記録し、最近最も使われなかったデータをキャッシュから削除するアルゴリズムだ。LRUでは、オブジェクトも終端での退去に向けてラインに沿って移動する。しかし、オブジェクトがベルトコンベアを移動する間に再び要求された場合、そのオブジェクトはラインの先頭に戻される。
こうしたアルゴリズムのバリエーションは何百と存在するが、効率を上げるために複雑さを増す傾向にある。それは一般的に、理由付けが不透明で、特に巨大なワークロードを扱う場合には高いメンテナンスが必要であることを意味する。
今回新たに考案された「SIEVE」は、LRUや他のいくつかのアルゴリズムと同様に、基本的なFIFO方式に簡単な手を加え、拡張させた物だ。
SIEVEは、「レイジープロモーション」と呼ばれる手法を採用している。ここでは、要求されたオブジェクトに最初は “0”とラベルを付ける。もしそのオブジェクトがベルトを移動する際に再度要求された場合、そのステータスは “1”に変わる。”1″とラベル付けされたオブジェクトが最後尾に到達すると、それは自動的に “0”にリセットされ、追い出される。
ポインタもまた、オブジェクトがラインを移動する際にスキャンする。ポインターはラインの終端から始まり、連続した円を描きながら頭へとジャンプする。ポインタが “0”と書かれたオブジェクトに当たると、そのオブジェクトは退場させられる。
SIEVEは、このように素早くオブジェクトを降格させるだけでなく、コンピュータ用語で「遅延昇格」と呼ばれる、最小限の計算労力でキャッシュ内の人気オブジェクトを維持することにも成功している。研究者たちは、SIEVEは迅速な降格と遅延昇格の両方を効果的に実現する最もシンプルなキャッシュ消去アルゴリズムだと考えている。
キャッシュの目的は、低いミス率（リクエストされたオブジェクトのうち、”倉庫”からフェッチしなければならないオブジェクトの割合）を達成することである。
SIEVEは、20 行未満のコードで実装できるシンプルさにも関わらず、そのパフォーマンスにおいて際立っている。これを評価するために、研究者たちはMeta、Wikimedia、X、および他の4つの大規模データセットからのオープンソースのWebキャッシュトレースで実験を行った。実際の Web キャッシュ データを使用して実施された一連の 1,500 回のテストを行った結果、SIEVEはトレースの45％以上において、9つの最先端アルゴリズムよりも低いミス率を達成した。次に優れたアルゴリズムのミス率はわずか15%であった。
この成果は非常に印象的なものであり、すでに 10 を超える人気ライブラリが SIEVE を使用しており、Meta や Google などの大手テクノロジー企業もその実装を検討している。
論文
- Juncheng Yang: SIEVE is Simpler than LRU: an Efficient Turn-Key Eviction Algorithm for Web Caches [PDF]
参考文献
研究の要旨
キャッシュは、低コストで高速なデータ配信に不可欠な技術である。キャッシュの心臓部である立ち退きアルゴリズムは、主にキャッシュ・ミス率を低減して効率を最大化するように設計されてきた。過去数十年の間に、多くの立ち退きアルゴリズムが設計されてきた。しかし、それらはすべて、より高い効率のために、スループット、シンプルさ、またはその両方をトレードオフにしている。このような妥協は、本番システムでの採用の妨げとなることが多い。この研究では、LRUよりもシンプルで、ウェブキャッシュのワークロードに対して最先端よりも優れた効率性とスケーラビリティを提供するアルゴリズムであるSIEVEを紹介する。SIEVE を 5 つの実運用キャッシュライブラリに実装し、平均 20 行未満のコード変更で済むようにした。7つのソースからの1559のキャッシュトレースで評価した結果、SIEVEはARCよりも最大63.2%低いミス率を達成した。さらに、SIEVEは1559のトレースの45%以上で9つの最先端アルゴリズムよりもミス比率が低く、次に優れたアルゴリズムは15%でしかミス比率が低くなっていません。SIEVEのシンプルさは、キャッシュヒットにロックが必要ないため、優れたスケーラビリティをもたらす。我々のプロトタイプは、最適化された16スレッドLRU実装の2倍のスループットを達成した。 スレッドLRU実装の2倍のスループットを達成した。SIEVEは単なる立ち退きアルゴリズムではなく、FIFOやLRUのような高度な立ち退きアルゴリズムを構築するためのキャッシュプリミティブとして使用することができる。
Sources
コメントを残す