A Fundamental Decision: What to Destage

In this paper, we shall focus on the central question of the order in which the writes are destaged from the NVS. Due to its asynchronous nature, the contents of the write cache may be destaged in any desired order without being concerned about starving any write requests. As long as NVS is drained at a sufficiently fast rate, the precise order in which contents of NVS are destaged does not affect fast write performance. However, the decision of what to destage can crucially affect (i) the peak write throughput and (ii) the performance of concurrent reads.

The capacity of disks to support sequential or nearly sequential write traffic is significantly higher than their capacity to support random writes, and, hence, destaging writes while exploiting this physical fact can significantly improve the peak write throughput of the system. This was one of the fundamental motivations for development of log-structured file systems [14,15] in a slightly different context. Thus, any good write caching algorithm should leverage sequentiality or spatial locality to improve the write throughput and hence the aggregate throughput of the system.

In the presence of concurrent reads, both the writes being destaged and the reads compete for the attention of the disk head. From the perspective of the applications, writes represent a background load on the disks and, indirectly, make read response times higher and read throughput lower. Less obtrusive the writes, the lesser the response time for the reads. We argue that the effect of writes on reads is significant:

• The widely accepted storage benchmark SPC-1 [16,17] contains 60% writes and 40% reads. While fast writes to NVS enable low response times for writes, these writes, when destaged, do interfere with the reads, increasing the read response times.

• When RAID is used at the back-end, writes are significantly more expensive than the reads. For example, for RAID-5, a read miss on a page may cause only one disk head to move, whereas due to read-modify-write and due to parity updates a write destage may cause up to four separate disk seeks. Similarly, for RAID-10, a write destage causes two disk heads to move.

• NVS is commonly built using battery-backed volatile RAM. The size of NVS is limited by the life of the battery which should be sufficient to dump the contents to a non-battery-backed non-volatile store like disks in case of a power failure. A write cache size of one-sixteenth of the read cache size is not unusual. Given the small relative size of the NVS, it tends to produce relatively fewer write hits, and, hence, a significantly large fraction of writes must be destaged. Further, unlike reads, writes do not benefit significantly from client side caching.

The first two arguments imply that for the SPC-1 benchmark using RAID-5 ranks, writes constitute at least six times the load of the read misses on the back-end! This underscores the tremendous influence that writes have on read performance and the peak throughput of the system. In summary, improving the order in which writes are destaged can significantly improve the overall throughput and response times of the storage controller.