Destage algorithms for disk arrays with non-volatile caches

ABSTRACT

In a disk array with a nonvolatile write cache, destages from the cache to the disk are performed in the background asynchronously while read requests from the host system are serviced in the foreground. In this paper, we study a number of algorithms for scheduling destages in a RAID-5 system. We introduce a new scheduling algorithm, called linear threshold scheduling, that adaptively varies the rate of destages to disks based on the instantaneous occupancy of the write cache. The performance of the algorithm is compared with that of a number of alternative scheduling approaches such as least-cost scheduling and high/low mark. The algorithms are evaluated in terms of their effectiveness in making destages transparent to the servicing of read requests from the host, disk utilization, and their ability to tolerate bursts in the workload without causing an overflow of the write cache. Our results show that linear threshold scheduling provides the best read performance of all the algorithms compared, while still maintaining a high degree of burst tolerance. An approximate implementation of the linear-threshold scheduling algorithm is also described. The approximate algorithm can be implemented with much lower overhead, yet its performance is virtually identical to that of the ideal algorithm.

References

1. 1.P. Biswas, K. K. Ramakrishnan, and D. Towsley, "Trace- Driven Analysis of Caching Policies for Disks," Proceedings of the 1993 A CM Szgmetmcs Conference on Measurement and Modeling of Computer Systems, May 1993, pp. 13-23.
2. 2.P.M. Chen, et al., "RAID: High-Performance, Reliable Secondary Storage," A CM Computzng Surveys, Vol. 26, No. 2, June 1994, pp. 145-188.
3. 3.P. J. Denning, "Effect of Scheduling on File Memory Operations," AFIPS Sprang Joznt Computer Conference, April 1967, pp. 9-21.
4. 4.G.R. Ganger, et al., "Disk Arrays: High-Performance High- Reliability Storage Subsystems," IEEE Computer, Vol. 27, No. 3, March 1994, pp. 30-36.
5. 5.R. Geist and S. Daniel, "A Continuum of Disk Scheduling Algorithms," A CM Transactions on Computer Systems, February 1987, pp. 77-92.
6. 6.D.M. Jacobson and J. Wilkes, "Disk Scheduling Algorithms Based on Rotational Position," Technical Report HPL-CSP- 91-7, Hewlett-Packard Laboratories, February 1991.
7. 7.J. Menon and D. Mattson, "Performance of Disk Arrays in Transaction Processing Environments," Proceedings of the 12th International Conference on D~str~buted Computing Systems, June 1992, pp. 302-309.
8. 8.J. Menon and J. Cortney, "The Architecture of a Fault- Tolerant Cached RAID Controller," Proceed2ngs of the 20th Annual International Symposium on Computer Arch~tec. ture, May 1993, pp. 76-86.
9. 9.J. Menon, J. Roche, and J. Kasson, "Floating Parity and Data Disk Arrays," Journal of Parallel and Dzstmbuted Computing, Vol. 17, No. 1-2, 1993, pp. 129-139.
10. 10.J. Menon, "Performance of RAID5 Disk Arrays with Read and Write Caching, D~stmbuted and Parallel Databases, Vol. 2, No. 3, July 1994, pp. 261-293.
11. 11.D.A. Patterson, G. Gibson, and R. H. Katz, "A Case for Redundant Arrays of Inexpensive Disks (RAID)," Proceedzngs of ACM SIGMOD, June 1988, pp. 109-116.
12. 12.C. Ruemmler and J. Wilkes, "UNIX Disk Access Patterns," Proceedzngs of the Wznter 1993 USENIX Conference, January 1993, pp. 405-420.
13. 13.C. Ruemmler and J. Wilkes, "An Introduction to Disk Drive Modeling," IEEE Computer, Vol. 27, No. 3, March 1994, pp. 17-28.
14. 14.M. Seltzer, P. Chert, and J. Ousterhout, "Disk Scheduling Revisited," Proceedings of the Wznter 1990 USENIX Conference, January 1990, pp. 313-324.
15. 15.D. Stodolsky, G. Gibson, and M. Holland, "Parity Logging: Overcoming the Small Write Problem in Redundant Disk Arrays," Proceedings of the ~Oth Annual Internatsonat Symposzum on Computer Architecture, May 1993, pp. 64-75.
16. 16.B. Worthington, G. Ganger, and Y. Patt, "Scheduling Algorithms for Modern Disk Drives," Proceedings of the 1994 A CM Szgmetr:cs Conference on Measurement and Model- ~ng of Computer Systems, May 1994, pp. 241-251.
17. 17.The RAIDBook, The RAID Advisory Board, Lino Lakes, Minnesota, June 1993.

Index Terms

• Hardware

  • Communication hardware, interfaces and storage

    • External storage

  • Hardware test

    • Memory test and repair

    • Test-pattern generation and fault simulation

  • Integrated circuits

    • Semiconductor memory

      • Non-volatile memory

  • Robustness

    • Fault tolerance

      • Redundancy

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

      • Scheduling algorithms

    • Online algorithms

      • Online learning algorithms

        • Scheduling algorithms

  • Theory and algorithms for application domains

    • Machine learning theory

      • Reinforcement learning

        • Sequential decision making