Sequentiality of reference is an ubiquitous access pattern dating
back at least to Multics. Sequential workloads lend themselves to
highly accurate prediction and prefetching. In spite of the
simplicity of the workload, design and analysis of a good
sequential prefetching algorithm and associated cache replacement
policy turns out to be surprisingly intricate. As first
contribution, we uncover and remedy an anomaly (akin to famous
Belady's anomaly) that plagues sequential prefetching when
integrated with caching. Typical workloads contain a mix of
sequential and random streams. As second contribution, we design a
self-tuning, low overhead, simple to implement, locally adaptive,
novel cache management policy
SARC that dynamically and
adaptively partitions the cache space amongst sequential and
random streams so as to reduce the read misses. As third
contribution, we implemented
SARC along with two popular
state-of-the-art
LRU variants on hardware for IBM's flagship
storage controller Shark. On Shark hardware with
GB cache and
RAID-5 arrays that is serving a workload akin to Storage
Performance Council's widely adopted SPC-1 benchmark,
SARC
consistently and dramatically outperforms the two
LRU
variants shifting the throughput-response time curve to the right
and thus fundamentally increasing the capacity of the system. As
anecdotal evidence, at the peak throughput,
SARC has average
response time of
ms as compared to
ms and
ms
for the two
LRU variants.
