AccuSim: Accurate Simulation of Cache Replacement Algorithms



A critical problem in improving file system performance is to design an effective block replacement algorithm for the buffer cache. Despite the well-known interactions between prefetching and caching, almost all buffer cache replacement algorithms have been proposed and studied comparatively without taking into account file system prefetching which exists in all modern operating systems. It has been shown [1] that kernel prefetching can have a significant impact on the relative performance in terms of the number of actual disk I/Os of many well-known replacement algorithms; it can not only narrow the performance gap but also change the relative performance benefits of different algorithms. Moreover, the response time for all disk I/Os is not the same, and hence the improvement in disk I/Os does not directly translate to improvement in execution time. These results demonstrate the importance for buffer caching research to take file system prefetching into consideration, and to study actual disk I/Os and execution time for comparing different algorithms.

Figure 1: Various kernel subsystems on the path from file system to the disk

Figure 1 shows the various kernel subsystems that come into play before an I/O access from an application is delivered to the actual disk. The complexity of interactions between such subsystems entails that the various buffer caching algorithms are comparatively studied in a realistic setting. However, creating an actual kernel implementation of the algorithm being designed and the algorithms to be compared against can be a laborious task. In addition, even with such a kernel implementation, it is often non-trivial to obtain a controlled environment, e.g., a fixed cache size in the presence of a unified buffer cache, in the actual kernel for comparing various algorithms on an even basis. To overcome this challenge faced by cache replacement algorithm designers, we have developed a buffer cache simulator AccuSim that realistically models all the kernel subsystems involved in buffer cache management in modern operating systems. AccuSim has the following features:

Figure 2: The architecture of AccuSim

Figure 2 shows the various modules of AccuSim.


AccuSim is driven by a trace that records the I/O operations during the execution of an application. In particular, for each I/O operation, the trace contains the identifier (inode) of the file that is accessed, the offset into the file of the first block that is accessed, the number of blocks being accessed, the I/O issue time, and the I/O completion time. A trace with this information can easily be collected using the standard system call tracing tool strace, which can be easily modified to collect only the desired information.

The trace is then processed to caculate the time difference between completion time of an I/O operation and the issue time of the next which is interpreted as the computation time in between the two I/O operations. Afterwards, the I/O issue and completion times are discarded and the processed trace only records the sequence of I/O operations interleaved with the computation time in between.

Each recorded entry in the trace contains a head which has the following format:

typedef struct _tracehead
   unsigned type:5;
   unsigned pid:27;
     unsigned inode;
     unsigned child;
     unsigned fnamesize;
} trace_head;

The trace entry can be for many different types, e.g., TREAD, TWRITE, etc. For example read and write> system calls, the recorded trace entry has the following format:

typedef struct _rwEntry
   unsigned pc;
   unsigned pcf;
   unsigned pcall;
   int iosize;
   int iosizer;
   unsigned filedes:16;
   unsigned execTime;
   unsigned fsize;
} rwEntry;


AccuSim has been made freely available in order to further file system research. You can obtain the source code of AccuSim and the traces used in our study by following the instructions at the download page.


AccuSim has been used extensively for a comparative study [1] of the hit ratios, number of disk requests, and execution time of eight modern cache replacement algorithms. Moreover, AccuSim has also been used for designing a new cache replacement algorithm in [2].




Up till 2005, almost all buffer cache replacement algorithms – one of the fundamental research topics in Computer Systems design -- were proposed and studied comparatively without taking into account the kernel-driven prefetching, supported in the file systems of almost all modern operating systems. The paper "The performance impact of kernel prefetching on buffer cache replacement algorithms" appearing at SIGMETRICS 2005 for the first time showed that prefetching, using Linux as an example, can have a significant impact on a comprehensive set of well-known buffer cache replacement algorithms developed over the decade before, which were largely evaluated and compared without taking into account kernel prefetching. The paper sent a clear wakeup call to the file/storage system research community, that it is paramount for buffer caching research to take file system prefetching into consideration.

The paper has made a significant impact on Computer System design in the past ten years:

Our SIGMETRICS paper has had 84 citations in Google Scholar, 914 downloads from the ACM Digitial Library, and about 2000 total downloads when including the downloads from the authors’ home pages. These are rather significant for a system paper. A list of sampled citations attesting to how the paper influenced future research on caching and prefetching in Computer Systems Design:

User Community

A partial list (60) of Institutions and Companies that have downloaded Accusim since 2008:

Affiliation: Princeton University
Affiliation: Stanford University
Affiliation: University of Arizona
Affiliation: University of Illinois at Chicago
Affiliation: Mcgill University 
Affiliation: York University
Affiliation: Pennsylvania State University
Affiliation: University Of Mining and Metallurgy
Affiliation: North Carolina State University
Affiliation: NCSU CSC Palm Group
Affiliation: University of Arizona
Affiliation: University of Minnesota, Twin Cities
Affiliation: Virginia Tech Student

Affiliation: Huazhong University of Science and Technology, Wuhan, China
Affiliation: National Chung Hsing University, Taiwan R.O.C.
Affiliation: National Cheng Kung University, Taiwan
Affiliation: Peking University
Affiliation: City University of Science and Information Technology, Pakistan.
Affiliation: Wuhan University, P.R.C
Affiliation: University of Seoul
Affiliation: Hanyang University, Seoul, Korea
Affiliation: Hanyang University in Republic of Korea
Affiliation: Computer System lab in Hanyang University in Republic of Korea
Affiliation: Department of Computer Science and Engineering at National Chung-Hsing University in R.O.C
Affiliation: School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan, China
Affiliation: HuaZhong University of Science and Technology
Affiliation: University of technology hcm city
Affiliation: RzeszŰw University of TEchnology
Affiliation: National Chung Hsing University
Affiliation: Department of Computer Science, National ChungHsing Univeristy
Affiliation: northwest polytechnic university in China
Affiliation: south china university of technology
Affiliation: Huazhong university of science and technology, china
Affiliation: Beijing Institute of Technology
Affiliation: universiti Sains Malaysia (USM)
Affiliation: Nile university
Affiliation: KAIST
Affiliation: NCHU,Taiwan
Affiliation: IIT Delhi
Affiliation: Indian Institute of Science
Affiliation: Pune University, India

Affiliation: Nuance Communications, 
Affiliation: IBM T.J. Watson Research Center
Affiliation: Samsung Electronics, Inc.
Affiliation: Mentor AIX Chips
Affiliation: VMware, Inc.
Affiliation: Microsoft