電腦科學家發明了一種高效且極其簡單的演算法來決定從網路快取中丟棄哪些項目，為新項目騰出空間。這種新的開源演算法被稱為 SIEVE，具有大規模改變網路流量管理的潛力。

SIEVE 是一個聯合項目電腦科學家埃默里大學、卡內基美隆大學和百利金基金會。該團隊關於 SIEVE 的論文將在第 21 屆 USENIX 網路系統設計與實現研討會 (NSDI)四月在加州聖克拉拉。

論文的預印本已經引起了轟動。

「SIEVE 的規模越來越大，不僅僅是我們，」埃默里大學博士張亞卓說。學生和論文的共同第一作者。“它已經表現良好，但我們收到了很多很好的建議來讓它變得更好。這就是開源世界的美妙之處。”

張與 Jun Cheng (Jason) Yang 共同擔任該論文的第一作者，後者在埃默里大學獲得計算機科學碩士學位，現為該大學的博士學位。卡內基美隆大學的候選人。

「SIEVE 是對久經考驗的方法的簡單改進快取-驅逐埃默里大學計算機科學系副教授 Ymir Vigfusson 表示：“這種演算法已經使用了幾十年，這實際上就像計算世界中的幾個世紀一樣。”

Vigfusson 和卡內基美隆大學計算機科學系副教授 Rashmi Vinayak 是這篇論文的共同高級作者。百利金基金會的電腦工程師姚躍也是合著者。

除了速度和有效性之外，引起人們對 SIEVE 興趣的關鍵因素是它的簡單性以及可擴展性。

「簡單就是終極的複雜，」Vigfusson 說。“旨在在幾分之一秒內為數十億人提供服務的系統中的各個部分越簡單，就越容易有效地實施和維護該系統。”

將「熱物體」放在手邊

許多人都了解定期整理衣櫃的價值。從未使用過的物品可以丟棄，很少使用的物品可以移至閣樓或其他遠端位置。這樣一來，最常穿戴的物品就可以放在觸手可及的地方，這樣就可以快速找到它們，而無需到處翻找。

快取就像一個組織良好的電腦資料儲藏室。快取中充滿了使用者請求的最受歡迎物件的副本，或 IT 術語中的「熱物件」。快取將這個小型熱物件集合與電腦網路的主資料庫分開維護，這就像一個巨大的倉庫，裡面裝滿了系統可以提供的所有資訊。

快取熱物件使網路系統能夠更有效地運行，快速回應使用者的請求。Web 應用程式可以透過彈出一個方便的儲藏室來獲取使用者想要的大部分對象，而不是前往倉庫並在龐大的資料庫中搜尋每個請求，從而有效地處理更多流量。

「快取無所不在，」張說。“這對於使用 Web 應用程式的每個公司（無論大小）都很重要。每個網站都需要快取系統。”

然而，在電腦科學領域，快取的研究相對較少。

快取的工作原理

雖然快取可以被認為是電腦的一個組織良好的儲藏室，但當數百萬人在不斷變化的需求中使用它時，很難知道應該放入該儲藏室中的內容。

高速緩存的快速記憶體運行成本昂貴，但對於網路使用者的良好體驗至關重要。目標是將未來最有用的信息保留在快取中。其他物件必須不斷地被篩選出來，或者用技術術語來說是“驅逐”，以便為不斷變化的熱物件陣列騰出空間。

快取驅逐演算法決定要丟棄哪些物件以及何時丟棄。

FIFO，即“先進先出”，是 20 世紀 60 年代開發的經典驅逐演算法。想像一下物體在傳送帶上排列。新請求的物件從左側進入，最舊的物件在到達右側行尾時被驅逐。

在 LRU（「最近最少使用」）演算法中，物件最終也會沿著線移動到驅逐。然而，如果一個物件在沿著傳送帶向下移動時再次被要求，它就會被移回隊列的頭部。

驅逐演算法有數百種變體，但它們往往會變得更加複雜以提高效率。這通常意味著它們推理起來不透明並且需要大量維護，尤其是在處理大量工作負載時。

「如果一個演算法非常複雜，它往往會有更多的錯誤，而所有這些錯誤都需要修復，」張解釋道。