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: Prabuddha Biswas , K. K. Ramakrishnan , Don Towsley, Trace driven analysis of write caching policies for disks, Proceedings of the 1993 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.13-23, May 10-14, 1993, Santa Clara, California, United States
• 2: Peter M. Chen , Edward K. Lee , Garth A. Gibson , Randy H. Katz , David A. Patterson, RAID: high-performance, reliable secondary storage, ACM Computing Surveys (CSUR), v.26 n.2, p.145-185, June 1994 [doi>10.1145/176979.176981]
• 3: P. J. Denning, "Effect of Scheduling on File Memory Operations," AFIPS Sprang Joznt Computer Conference, April 1967, pp. 9-21.
• 4: Gregory R. Ganger , Bruce L. Worthington , Robert Y. Hou , Yale N. Patt, Disk arrays: high-performance, high-reliability storage subsystems, Computer, v.27 n.3, p.30-36, March 1994 [doi>10.1109/2.268882]
• 5: Robert Geist , Stephen Daniel, A continuum of disk scheduling algorithms, ACM Transactions on Computer Systems (TOCS), v.5 n.1, p.77-92, Feb. 1987 [doi>10.1145/7351.8929]
• 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: 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: Jai Menon , Jim Cortney, The architecture of a fault-tolerant cached RAID controller, Proceedings of the 20th annual international symposium on Computer architecture, p.76-87, May 16-19, 1993, San Diego, California, United States
• 9: Jai Menon , James Roche , Jim Kasson, Floating parity and data disk arrays, Journal of Parallel and Distributed Computing, v.17 n.1-2, p.129-139, Jan./Feb. 1993 [doi>10.1006/jpdc.1993.1011]
• 10: Jai Menon, Performance of RAID5 disk arrays with read and write caching, Distributed and Parallel Databases, v.2 n.3, p.261-293, July 1994 [doi>10.1007/BF01266331]
• 11: David A. Patterson , Garth Gibson , Randy H. Katz, A case for redundant arrays of inexpensive disks (RAID), Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.109-116, June 01-03, 1988, Chicago, Illinois, United States
• 12: C. Ruemmler and J. Wilkes, "UNIX Disk Access Patterns," Proceedzngs of the Wznter 1993 USENIX Conference, January 1993, pp. 405-420.
• 13: Chris Ruemmler , John Wilkes, An introduction to disk drive modeling, Computer, v.27 n.3, p.17-28, March 1994 [doi>10.1109/2.268881]
• 14: M. Seltzer, P. Chert, and J. Ousterhout, "Disk Scheduling Revisited," Proceedings of the Wznter 1990 USENIX Conference, January 1990, pp. 313-324.
• 15: Daniel Stodolsky , Garth Gibson , Mark Holland, Parity logging overcoming the small write problem in redundant disk arrays, Proceedings of the 20th annual international symposium on Computer architecture, p.64-75, May 16-19, 1993, San Diego, California, United States
• 16: Bruce L. Worthington , Gregory R. Ganger , Yale N. Patt, Scheduling algorithms for modern disk drives, Proceedings of the 1994 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.241-251, May 16-20, 1994, Nashville, Tennessee, United States
• 17: The RAIDBook, The RAID Advisory Board, Lino Lakes, Minnesota, June 1993.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Mass storage (e.g., magnetic, optical, RAID)

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.3 Performance Analysis and Design Aids**
          Subjects: Simulation**
      B.3.4 Reliability, Testing, and Fault-Tolerance**
          Subjects: Redundant design**

  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Design, Performance, Reliability