Write caches using fast, non-volatile storage are now widely used
in modern storage controllers since they enable hiding latency on
writes.
Effective algorithms for write cache management are extremely
important since (i) in RAID-5, due to read-modify-write and parity
updates, each write may cause up to four separate disk seeks while
a read miss causes only a single disk seek; and (ii) typically,
write cache size is much smaller than the read cache size - a
proportion of
is
typical.
A write caching policy must decide:
what data to destage. On one hand, to exploit temporal
locality, we would like to destage data that is least likely to
be re-written soon with the goal of minimizing the total number of
destages. This is normally achieved using a caching algorithm such
as LRW (least recently written). However, a read cache has a
very small uniform cost of replacing any data in the cache,
whereas the cost of destaging depends on the state of the disk
heads. Hence, on the other hand, to exploit spatial
locality, we would like to destage writes so as to minimize the
average cost of each destage. This can be achieved by using a disk
scheduling algorithm such as CSCAN, that destages data in
the ascending order of the logical addresses, at the higher level
of the write cache in a storage controller. Observe that LRW
and CSCAN focus, respectively, on exploiting either temporal
or spatial locality, but not both simultaneously. We propose a new
algorithm, namely, Wise Ordering for Writes (WOW), for write cache
management that effectively combines and balances temporal and
spatial locality.
Our experimental set-up consisted of an IBM xSeries 345 dual
processor server running Linux that is driving a (software) RAID-5
or RAID-10 array using a workload akin to Storage Performance
Council's widely adopted SPC-1 benchmark. In a cache-sensitive
configuration on RAID-5, WOW delivers peak throughput that
is 129% higher than CSCAN and 9% higher than LRW.
In a cache-insensitive configuration on RAID-5, WOW and CSCAN deliver peak throughput that is 50% higher than LRW. For a random write workload with nearly 100% misses, on
RAID-10, with a cache size of 64K, 4KB pages (256MB), WOW
and CSCAN deliver peak throughput that is 200% higher than
LRW. In summary, WOW has better or comparable peak
throughput to the best of CSCAN and LRW across a wide
gamut of write cache sizes and workload configurations. In
addition, even at lower throughputs, WOW has lower average
response times than CSCAN and LRW.
Need help?
