A New, Simple Method to Speed Cache Sifting

Emory University, Atlanta, GA

A logo for SIEVE, created by Zhang, portrays hotter objects in shades of red and colder ones in shades of blue. Zhang also designed a web site for SIEVE, including a motion graphic demonstrating how it works. (Image: emory.edu)

Computer scientists have invented a highly effective, yet incredibly simple, algorithm to decide which items to toss from a web cache to make room for new ones. Known as SIEVE — a joint project of computer scientists at Emory University, Carnegie Mellon University, and the Pelikan Foundation — the new open-source algorithm holds the potential to transform the management of web traffic on a large scale.

In addition to its speed and effectiveness, a key factor sparking interest in SIEVE is its simplicity, lending it scalability.

“Simplicity is the ultimate sophistication,” said Co-Senior Author and Associate Professor Ymir Vigfusson. “The simpler the pieces are within a system designed to serve billions of people within a fraction of a second, the easier it is to efficiently implement and maintain that system.”

A cache is like a well-organized closet for computer data. The cache is filled with copies of the most popular objects requested by users, or “hot objects” in IT terminology. The cache maintains this small collection of hot objects separately from a computer network’s main database, which is like a vast warehouse filled with all the information that could be served by the system.

Caching hot objects allows a networked system to run more efficiently, rapidly responding to requests from users. A web application can effectively handle more traffic by popping into a handy closet to grab most of the objects users want rather than traveling down to the warehouse and searching through a massive database for each request.

“Caching is everywhere,” said Co-First Author Yazhuo Zhang. “It’s important to every company, big or small, that is using web applications. Every website needs a cache system.”

SIEVE initially labels a requested object as a “zero.” If the object is requested again as it moves down the belt, its status changes to “one.” When an object labeled “one” makes it to the end of the line it is automatically reset to “zero” and evicted.

A pointer, or “moving hand,” also scans the objects as they travel down the line. The pointer starts at the end of the line and then jumps to the head, moving in a continuous circle. Anytime the pointer hits an object labeled “zero,” the object is evicted.

“It’s important to evict unpopular objects as quickly as possible, and SIEVE is very fast at this task,” Zhang said.

In addition to this quick demotion of objects, SIEVE manages to maintain popular objects in the cache with minimal computational effort, known as “lazy promotion” in computer terminology. The researchers believe that SIEVE is the simplest cache-eviction algorithm to effectively achieve both quick demotion and lazy promotion.

The purpose of caching is to achieve a low miss ratio — the fraction of requested objects that must be fetched from “the warehouse.”

To evaluate SIEVE, the researchers conducted experiments on open-source web-cache traces from Meta, Wikimedia, X, and four other large datasets. The results showed that SIEVE achieves a lower miss ratio than nine state-of-the-art algorithms on more than 45 percent of the traces. The next best algorithm has a lower miss ratio on only 15 percent.

The ease and simplicity of SIEVE raises the question of why no one came up with the method before. The SIEVE team’s focus on how patterns of web traffic have changed in recent years may have made the difference, Zhang theorizes.

“For example,” she said, “new items now become ‘hot’ quickly but also disappear quickly. People continuously lose interest in things because new things keep coming up.”

Web-cache workloads tend to follow what are known as generalized Zipfian distributions, where a small subset of objects account for a large proportion of requests. SIEVE may have hit a Zipfian sweet spot for current workloads.

For more information, contact Emory University at This email address is being protected from spambots. You need JavaScript enabled to view it..