Improving Data Access for Energy-Intensive Computing

When a website loads quickly, or an operating system runs smoothly, you can thank caching — a widely used computing process for fast data access that works by storing frequently-used pieces of data inside a computer’s memory. 

Caching algorithms haven’t changed much since they were invented in the 1960s. Now, a team of researchers at the Harvard John A. Paulson School of Engineering and Applied Sciences (SEAS), led by Assistant Professor of Computer Science Juncheng Yang, is working to update these critical computing strategies as power-hungry data centers process more and more information in the AI age. 

“Caching has been out for more than 60 years and is one of the fundamental ideas of computer science,” Yang said. “Our work is rooted in measurement, and in trying to understand how our modern systems work.” 

A paper by Yang and colleagues describing new solutions for software caching received a Best Paper Honorable Mention award at the recent Very Large Data Bases (VLDB) computer science conference held in Boston. 

The paper, “Demystifying and Improving Lazy Promotion in Cache Eviction,” was led by Yang in collaboration with researchers at Carnegie Mellon University, where Yang received his Ph.D. 

Not only do large-scale data centers use vast amounts of memory for caching, which consumes energy both during operation and manufacturing, but caches operate through the computer stack – from processors to operating systems to databases, cloud services, and edge-computing infrastructure, Yang continued. Improving cache efficiency could have many benefits beyond faster applications. 

Caching is driven by eviction algorithms, which decide which data should be stored and which should be discarded. A commonly used algorithm today is called Least Recently Used, which performs an operation that “promotes” a piece of data to the front of the queue every time it is accessed. These operations are energy intensive, Yang said, and not scalable — creating major bottlenecks in web and server traffic. 

In their paper, Yang and his team analyzed the major existing techniques used today in software caching, including LRU, ranking them in order of effectiveness and describing their tradeoffs. The researchers also introduce a new metric called promotion efficiency, which measures how many cache hits are generated, on average, by each promotion. Based on these insights, they proposed two advanced techniques to further improve scalability and efficiency of a cache system, called Delayed FIFO Re-Insertion and Age-Guided Eviction. These improve existing algorithms that reduce the need for performing promotion operations while preserving cache efficiency. The team’s evaluations found that the techniques reduced cache promotion operations by 20-60 percent. 

Earlier caching algorithms invented by Yang’s group have been deployed by hundreds of open-source software libraries as well as large tech companies that process petabytes of data per day. Their VLDB award is the research group’s fifth honored paper on caching from various computer science conferences since 2023. 

Link to paper