Algorithms for exploiting temporal locality have been studied extensively in the context of read caches. Several state-of-the-art algorithms include LRU, CLOCK, FBR, LRU-2, 2Q, LRFU, LIRS, MQ, ARC, and CAR. For a detailed review of these algorithms, please see some recent papers [2,4,5].
These algorithms attempt to reduce the miss ratio. However, as explained in Section I-C, in write caching, it not sufficient to minimize the miss ratio alone, but we must also pay attention to the average cost of destages. The latter factor is completely ignored by the above algorithms. We will demonstrate in the paper that a write caching algorithm has a higher hit ratio than some other algorithm and yet the second algorithm delivers a higher throughput. In other words, decreasing the miss ratio without taking into account its effect on the spatial locality is unlikely to guarantee increased performance. Thus, the problem of designing good write caching algorithms is different from that of designing algorithms for read caching.
In this paper, we focus on LRW as the prototypical temporal locality algorithm. We also exploit a simple approximation to LRU, namely, CLOCK [22], that is widely used in operating systems and databases. CLOCK is a classical algorithm, and is a very good approximation to LRU. For a recent paper comparing CLOCK and LRU, see [4].