Conclusions

Sequential prefetching is the most widely used prefetching technique in storage subsystems. We have argued the need for an algorithm that can adapt both the prefetch degree and the trigger distance on a per stream basis in response to evolving workloads. We have provided a theoretical analysis and proved the sufficient conditions for optimal online cache management for steady-state sequential streams. We also presented a novel, simple, adaptive and practical implementation called AMP. We have demonstrated through a series of wide ranging experiments including realistic benchmarks, that AMP provides the highest possible aggregate throughput when a cache is shared among multiple sequential streams. Even in scenarios where the sequential streams are not steady, comprise of short sequences, or are intermixed with random workloads (as in SPC1-Read), we demonstrated that AMP convincingly outperforms all competing algorithms by wasting the least amount of cache while providing the best overall throughput.

We anticipate AMP to be widely applicable not only in storage subsystems, but in any system that services sequential workload.