Check out the new USENIX Web site. next up previous
Next: WOW : The Algorithm Up: WOW Previous: WOW


We are working in the context of a storage controller. Typically, a storage controller connects to a RAID controller which, in turn, connects to physical disks. We assume that there is no write cache at lower levels such as RAID and disks. In other words, there is no fast write at lower levels and I/O scheduling is limited to concurrent requests issued by the storage controller. Also, note that a typical RAID controller may choose to implement FCFS or such simpler scheduling algorithm, while an individual disk may implement a smarter disk scheduling algorithm such as SATF. We can make no assumptions about these algorithms at the level of a storage controller. Also, typically the amount of write cache in storage controllers per RAID array or per disk is much larger than the amount of cache in the RAID array or disks.

We will use 4KB pages as the smallest unit of cache management. We will divide each disk into strips, where each strip is a logically and physically contiguous set of pages. Here, we use 64KB as the strip size. In RAID, we will define a stripe as a collection of strips where each participating disk contributes one strip to a stripe. Due to mirroring in RAID-10 and parity in RAID-5, the effective storage provided by a stripe is less than its physical size.

The notion of a hit is straightforward in read caching, but is somewhat involved for write caching. In write caching, a hit can be a hit on a page, a hit on a strip, or a hit on a stripe. These different hits may have different payoffs, for example, in RAID-5, a page hit saves four seeks, whereas a stripe hit and a page miss saves two seeks because of shared parity. In RAID-5, we will manage cache in terms of stripe groups. In RAID-10, we will manage cache in terms of strip groups. This allows a better exploitation of temporal locality by saving seeks and also spatial locality by coalescing writes together. We will refer to a strip or stripe group as a write group.

next up previous
Next: WOW : The Algorithm Up: WOW Previous: WOW
Binny Gill 2005-10-17