|
4th USENIX Conference on File and Storage Technologies—Abstract
Pp. 129–142 of the Proceedings
WOW:Wise Ordering for Writes—Combining Spatial and
Temporal Locality in Non-Volatile Caches
Binny S. Gill and Dharmendra S. Modha, IBM Almaden Research Center,
Abstract
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 1 : 16
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.
- View the full text of this paper in HTML and PDF.
Until December 2006, you will need your USENIX membership identification in order to access the full papers. The Proceedings are published as a collective work, © 2005 by the USENIX Association. All Rights Reserved. Rights to individual papers remain with the author or the author's employer. Permission is granted for the noncommercial reproduction of the complete work for educational or research purposes. USENIX acknowledges all trademarks within this paper.
- If you need the latest Adobe Acrobat Reader, you can download it from Adobe's site.
|
Need help? Use our Contacts page.
