How Block Cache Eviction Policies Affect the I/O Performance of Applications With Structured Data Access Patterns

Abstract

The Block Cache layer of an operating system stores a subset of recently accessed disk blocks in the main memory to avoid slow disk operations. The performance gain is relative to the likelihood of subsequent accesses for the cached blocks. The eviction policy decides which cached blocks are evicted, and has a huge impact on the system performance. I have developed a testing framework to evaluate different eviction strategies under a cache simulation by using the real world pre-cache access records. The framework also replays post-cache accesses on a real solid state disk to get a more realistic measurement of the performance. I have compared the 2Q, ARC, BRRIP, CAR, CLOCK, CLOCKPRO, LRU, Random2, RRIP, SpatialClock algorithms under various test captures. In addition to classic sequential and random categories, I have focused on database access patterns for B-Tree structured disk files. Testing with disk replay was time consuming but revealed that the reduction of number of I/O requests is not the sole criteria for the performance, and the ordering and locality of the evicted blocks is equally important. The randomized algorithms didn't perform well for this reason, and the 2Q turned out to be the most competitive eviction strategy for the tested workloads.