コンピューター科学者は、新しいアイテムのためのスペースを確保するために Web キャッシュからどのアイテムを破棄するかを決定する、非常に効果的でありながら、信じられないほどシンプルなアルゴリズムを発明しました。SIEVE として知られるこの新しいオープンソース アルゴリズムは、Web トラフィックの管理を大規模に変革する可能性を秘めています。

SIEVEは以下の共同プロジェクトです。コンピュータ科学者エモリー大学、カーネギーメロン大学、ペリカン財団で。SIEVEに関するチームの論文は、ネットワーク化されたシステムの設計と実装 (NSDI) に関する第 21 回 USENIX シンポジウム4月にカリフォルニア州サンタクララで。

この論文のプレプリントはすでに話題になっている。

「SIEVE は私たちだけよりも大きく、偉大です」とエモリー博士の Yazhuo Zhang 氏は言います。学生であり、論文の共同筆頭著者。「すでにパフォーマンスは良好ですが、さらに改善するための良い提案がたくさん得られています。それがオープンソースの世界の美しさです。」

Zhang 氏は、エモリー大学でコンピュータ サイエンスの修士号を取得し、現在は博士号を取得している Juncheng (Jason) Yang 氏とこの論文の第一著者を共有しています。カーネギーメロン大学の候補者。

「SIEVE は実証済みの機能を簡単に改良したものですキャッシュ-立ち退きこのアルゴリズムは何十年にもわたって使用されており、これはコンピューティングの世界では文字通り何世紀にもわたるようなものです」とエモリー大学コンピューターサイエンス学科の准教授、ユミル・ヴィグフソン氏は語ります。

ヴィグフソン氏は、カーネギーメロン大学コンピュータサイエンス学部准教授のラシュミ・ビナヤック氏とともに、この論文の共同上級著者である。ペリカン財団のコンピューターエンジニアであるヤオ・ユエ氏も共著者です。

SIEVE への関心を呼び起こす重要な要素は、そのスピードと有効性に加えて、そのシンプルさ、つまりスケーラビリティです。

「シンプルさは究極の洗練です」とヴィグフソン氏は言います。「数十億人に数秒以内にサービスを提供するように設計されたシステム内の要素がシンプルであればあるほど、そのシステムを効率的に実装して維持することが容易になります。」

「熱い物体」を手元に置いておく

多くの人は、衣類クローゼットを定期的に整理することの価値を理解しています。決して使用されないアイテムは捨てられ、めったに使用されないアイテムは屋根裏部屋または他の離れた場所に移動できます。これにより、最も頻繁に着用するアイテムが手の届くところに置かれるため、探し回らなくてもすぐに見つけることができます。

キャッシュは、コンピューター データを保管するための整理整頓されたクローゼットのようなものです。キャッシュには、ユーザーが要求した最も人気のあるオブジェクト (IT 用語では「ホット オブジェクト」) のコピーが格納されます。キャッシュは、このホット オブジェクトの小さなコレクションをコンピュータ ネットワークのメイン データベースとは別に管理します。メイン データベースは、システムが提供できるすべての情報が詰まった広大な倉庫のようなものです。

ホット オブジェクトをキャッシュすると、ネットワーク システムがより効率的に実行され、ユーザーからのリクエストに迅速に応答できるようになります。Web アプリケーションは、リクエストごとに倉庫に行って大規模なデータベースを検索するのではなく、便利なクローゼットに飛び込み、ユーザーが必要とするオブジェクトのほとんどを取得することで、より多くのトラフィックを効果的に処理できます。

「キャッシュはどこにでもあります」と Zhang 氏は言います。「大小を問わず、Web アプリケーションを使用するすべての企業にとって重要です。すべての Web サイトにはキャッシュ システムが必要です。」

しかし、コンピュータ サイエンスの分野では、キャッシングの研究は比較的進んでいません。

キャッシュの仕組み

キャッシュはコンピューター用に整理されたクローゼットのようなものと考えることができますが、ニーズが常に変化する何百万もの人々がそのクローゼットを使用している場合、そのクローゼットに何を入れるべきかを知るのは困難です。

キャッシュの高速メモリは実行コストが高くなりますが、Web ユーザーの優れたエクスペリエンスには不可欠です。目標は、将来最も役立つ情報をキャッシュ内に保持することです。他のオブジェクトは、変化するホット オブジェクトの配列のためのスペースを確保するために、継続的に選り分け、または技術用語で「排除」する必要があります。

キャッシュ削除アルゴリズムは、どのオブジェクトをいつ廃棄するかを決定します。

FIFO (「先入れ先出し」) は、1960 年代に開発された古典的なエビクション アルゴリズムです。ベルトコンベア上に物体が並べられているところを想像してください。新しくリクエストされたオブジェクトは左側に入り、最も古いオブジェクトは右側の行の終端に到達すると削除されます。

LRU (「最も最近使用されていない」) アルゴリズムでは、オブジェクトも最後に削除に向けてラインに沿って移動します。ただし、オブジェクトがベルトコンベアを移動中に再度要求されると、そのオブジェクトはラインの先頭に戻されます。

エビクション アルゴリズムには何百ものバリエーションが存在しますが、効率を高めるために複雑になる傾向があります。これは一般に、特に大規模なワークロードを処理する場合には、それらを推論するのが不透明であり、多大なメンテナンスが必要であることを意味します。

「アルゴリズムが非常に複雑な場合、バグが増える傾向にあり、それらのバグはすべて修正する必要があります」と Zhang 氏は説明します。