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.