Abstract: This paper analyzed the performance characteristics of classic 2Q algorithm when it was performed on mail-service workloads,and proposed an improved algorithm, called 2Q*.The simulation results show that 2Q* algorithm can outperform the other replacement algorithms,including the classic 2Q algorithm,for all the cache sizes and various mail-service workloads. To verify the simulation results in real practice, we implemented the algorithm in FIexiCache, a partitioned buffer cache system, and integrated it with a popular adaptive sectuential prefect policy properly. The experiment results in real system further confirm the effectiveness of 2Q* algorithm for mail service kind of applications in improving their physical I/O performance. Moreover, its runtime overhead is also fairly low.

Key words: Buffer cache, Mail service, Replacement algorithm, 2Q*