Over the last three decades, processor speeds have increased at an astounding average annual rate of 60%. In contrast, disks which are electro-mechanical devices have improved their access times at a comparatively meager annual rate of about 8%. Moreover, disk capacity grows 100 times per decade, implying fewer available spindles for the same amount of storage [1]. These trends dictate that a processor must wait for increasingly larger number of cycles for a disk read/write to complete. A huge amount of performance literature has focused on hiding this I/O latency for disk bound applications.
Caching is a fundamental technique in hiding I/O latency and is widely used in storage controllers (IBM Shark, EMC Symmetrix, Hitachi Lightning), databases (IBM DB2, Oracle, SQL Server), file systems (NTFS, EXT3, NFS, CIFS), and operating systems (UNIX variants and Windows). SNIA (www.snia.org) defines a cache as ``A high speed memory or storage device used to reduce the effective time required to read data from or write data to a lower speed memory or device.'' We shall study cache algorithms in the context of a storage controller wherein fast, but relatively expensive, random access memory is used as a cache for slow, but relatively inexpensive, disks. A modern storage controller's cache typically contains volatile memory used as a read cache and a non-volatile memory used as a write cache.
Read cache management is a well studied discipline, for a survey and for some recent work, see [2,3,4,5]. There are a large number of cache replacement algorithms in this context, see, for example, LRU, CLOCK, FBR, LRU-2, 2Q, LRFU, LIRS, MQ, ARC, and CAR. In contrast, write caching is a relatively less developed subject. Here, we shall focus on algorithms for write cache management in the context of a storage controller equipped with fast, non-volatile storage (NVS).