PDL Abstract

Parity Logging: Overcoming the small write Problem in Redundant Disk Arrays

Appears in Proc. of the 21th Annual International Symposium on Computer Architecture, 1993, pp. 64-75.

Daniel Stodolsky, Mark Holland, Garth A. Gibson

School of Computer Science
Carnegie Mellon University
Pittsburgh, PA 15213


Parity encoded redundant disk arrays provide highly reliable, cost effective secondary storage with high performance for read accesses and large write accesses. Their performance on small writes, however, is much worse than mirrored disks - the traditional, highly reliable, but expensive organization for secondary storage. Unfortunately, small writes are a substantial portion of the I/O workload of many important, demanding applications such as on-line transaction processing. This paper presents parity logging, a novel solution to the small write problem for redundant disk arrays. Parity logging applies journalling techniques to substantially reduce the cost of small writes. We provide a detailed analysis of parity logging and competing schemes - mirroring, floating storage, and RAID level 5 - and verify these models by simulation. Parity logging provides performance competitive with mirroring, the best of the alternative single failure tolerating disk array organizations. However, its overhead cost is close to the minimum offered by RAID level 5. Finally, parity logging can exploit data caching much more effectively than all three alternative approaches.

FULL PAPER: pdf / postscript