We now describe our main contribution which is a new algorithm that combines the strengths of CLOCK, a predominantly read cache algorithm, and CSCAN, an efficient write cache algorithm, to produce a very powerful and widely applicable write cache algorithm. See Figures 3 and 4 for a depiction of the data structures and the algorithm.
 |
The basic idea is to proceed as in CSCAN by maintaining a sorted list of write groups. The smallest and the highest write groups are joined forming a circular queue. The additional new idea is to maintain a ``recency'' bit akin to CLOCK with each write group. The algorithm now proceeds as follows.
A write group is always inserted in its correct sorted position. Upon insertion, its recency bit is set to zero. However, on a write hit, the recency bit is set to one. The destage operation proceeds as in CSCAN, wherein a destage pointer is maintained that traverses the circular list looking for destage victims. In CSCAN every write group that is encountered is destaged. However, we only allow destage of write groups whose recency bit is zero. The write groups with a recency bit of one are skipped, however, their recency bit is turned off, and reset to zero. The basic idea is to give an extra life to those write groups that have been hit since the last time the destage pointer visited them. This allows us to incorporate recency representing temporal locality on one hand, and small average distance between consecutive destages representing spatial locality. The simplicity of the algorithm is intentional so that it succeeds in real systems. The superiority of the algorithm (demonstrated in Section VI) to the current state-of-the-art should encourage its widespread use.
