More Web Proxy on the site http://driver.im/

article

Free access

Parity logging disk arrays

Editor: Ken Birman Authors:

Daniel Stodolsky,

William V. Courtright, II,

Garth A. GibsonAuthors Info & Claims

ACM Transactions on Computer Systems (TOCS), Volume 12, Issue 3

Pages 206 - 235

https://doi.org/10.1145/185514.185516

Published: 01 August 1994 Publication History

Abstract

Parity-encoded redundant disk arrays provide highly reliable, cost-effective secondary storage with high performance for reads and large writes. 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 reduce substantially the cost of small writes. We provide detailed models 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, but with capacity overhead close to the minimum offered by RAID level 5. Finally, parity logging can exploit data caching more effectively than all three alternative approaches.

References

[1]

BHIDE, A, AND DIAS, D. 1992. RAID architectures for OLTP. Computer Science Research Report RC 17879, IBM Corp., Almaden, Cahf

[2]

CAO, P., LIM, S. B, VENKATARAMAN, S., AND WILKES, J. 1993. The TickerTAIP parallel RAID architecture. In Proceedings of the 20th Annuul Internantzonal Syraposiourn on Computer Architecture. Corrzput. Arch. News 21, 2, 52-63.

[3]

CHEN, P. M., AND PATTERSON, D.h. 1990. Maximizing performance in a striped disk array. In Proceedzngs of the 17th Annuel Internattonal Symposzum ol~ Computer Architecture. IEEE Computer Society Press, Los Alamitos, Calif., 322-331.

[4]

DISK/TREND, INc. 1994.1994 DISK/TREND Report. Disk Drive Arrays. DISK/TREND, Inc., Mountain View, Calif.

[5]

FEIGEL, C. 1994. Flash memory heads toward mainstream. Microprocess. Rep. 8, 7, 19-25.

[6]

GEIST, R. M., AND DANIEL, S. 1987. A continuum of disk scheduling algorithms. ACM Trans. Comput. Syst. 5, 1, 77 92.

[7]

GIBSON, G. 1992. Redundant Disk Arrays: Reliable, Parallel Secondary Storage. MIT Press, Cambridge, Mass.

[8]

GIBSON, G., AND PATTERSON, D. 1993. Designing disk arrays for high data reliability. J. Parallel Distrib. Comput. 17, 1-2, 4-27.

[9]

HOLLAND, M., AND GIBSON, G. 1992. Parity Declustering for Continuous Operation in Redundant Disk Arrays. In Proceedings of the 5th International Conference on Architectural Support for Programming Languages and Operating' Systems. SIGPLAN Not. 27, 9, 23-35.

[10]

IBM CORP. 1989. IBM 0661 Dtsk Drive Product Descr~ptwn, Model 370, First Edition, Low End Storage Products, 504/114-2. IBM Corp., Armonk, New York.

[11]

MENON, J. 1993. Performance of RAID5 disk arrays with read and write caching. Computer Science Res. Rep. RJ9485(83363). IBM Corp., Alamaden, Calif.

[12]

MENON, J., AND KASSON, J. 1992. Methods for improved update performance of disk arrays. In Proceedtngs of the Hawalt International Conference on System Sctences. IEEE Computer Society Press, Los Alamitos, Calif., vol. 1, 74-83.

[13]

O~I, C. U., ANn SOLWORTH, J.A. 1993. Doubly distorted mirrors, In Proceedings of the 1993 ACM SIGMOD Internatwnal Conference on Management of Data. SIGMOD Rec. 22, 2, 307-318.

[14]

OI~STER~OUT, J. K., CHERENSON, A. R., DOU(~LIS, F., NELSON, M. N., A~D WELCH, B.B. 1988. The Sprite network operating system. Computer 21, 2, 23-36.

[15]

PATTERSON, D., GIBSON, G., AND KATZ, R. 1988. A case for redundant arrays of inexpensive disks (RAID). In Proceedings of the 1988 ACM SIGMOD Internatwnal Conference on Management of Data. SIGMOD Rec. 17, 3, 109-116.

[16]

PoLYzoIs, C. A., BHIDE, A., A~D DIAS, D.M. 1993. Disk mirroring with alternating deferred updates In Proceedings of the 19th Conference on Very Large Databases. Morgan Kaufmann, Palo Alto, Calif., 604 617.

[17]

RA~IAKRISHNAN, K. K., BISWAS, P., AND KAREDLA, R. 1992. Analysis of file I/O traces in commercial computing environments. In Proceedings of the 1992 ACM SIGMETRICS Conference on Performance. Per. Eval. Rev. 20, 1, 78-90.

[18]

ROSENBLUM, a. AND OUSTERHOUT, J. 1991. The design and implementation of a log-structured file system. In Proceedings of the 13th ACM Symposium on Operatzng System Principles. Oper. Syst. Rev. 25, 5, 1-15.

[19]

SALEM, K., AND GARCIA-MOLINA, H. 1986. Disk striping. In Proceedings of the 2nd IEEE International Con/~rence on Data Engineering. IEEE Computer Society Press, Los Alamitos, Calif.

[20]

SC~ULZE, M. E., GmSON, G. A., KATZ, R. H., AND PATTERSON, D.A. 1989. How reliable is s RAID? In Proceedings of the 1989 IEEE Computer Society Internatwnal Conference. IEEE Computer Society Press, Los Alamitos, Calif., 118 123.

[21]

SEbTZ~R, M., CHEN, P., AND OUSTERHOUT, J. 1990. Disk scheduling revisited In Proceedings of the Winter 1990 USENIX Conference. USENIX Assoc., Berkeley, Calif., 313-324.

[22]

SOLWORTI~, J. A. AND ORJI, C.U. 1990. Wr~te-only disk caches. In Proceedu~gs of the 1990 ACM SIGMOD International Con/~rence on Manegement of Data. SIGMOD Rec. 19, 2, 123 132.

[23]

SOLWORTH, J A. AND O~l, C U. 1991. Distorted mirrors. In Proceedings of the 1st Internatwnal Conference on Parallel and Distributed Information Systems. IEEE Computer Society Press, Los Alamitos, Calif., 10-17.

[24]

STODOLSR~Y, D., GIBSON, G., AND HOLLAND, M. 1993. Parity logging: Overcoming the small write problem in redundant disk arrays. In Proceedings of the 20th Annual International Symposium on Computer Architecture. Comput. Arch. News. 21, 2, 64 75.

[25]

STODOLSKY, D., HOLLAND M., COURTRICHT, W., AND GIBSON, G. 1994. Parity logging disk arrays. Computer Science Research CMU-CS-94-170, Carnegie Mellon Univ., Pittsburgh, Penn.

[26]

TPC 1989. The TPC-A Benchmark: A Standard Specifzcation. Transaction Processing Performance Council.

Cited By

(2022)BibliographyStorage Systems10.1016/B978-0-32-390796-5.00023-1(641-693)Online publication date: 2022
https://doi.org/10.1016/B978-0-32-390796-5.00023-1
Thomasian A(2022)Redundant Arrays of Independent Disks - RAIDStorage Systems10.1016/B978-0-32-390796-5.00014-0(269-336)Online publication date: 2022
https://doi.org/10.1016/B978-0-32-390796-5.00014-0
Grawinkel MNagel LBrinkmann A(2016)LoneStar RAIDACM Transactions on Storage10.1145/284081012:1(1-29)Online publication date: 7-Jan-2016
https://dl.acm.org/doi/10.1145/2840810
Show More Cited By

Index Terms

Parity logging disk arrays
1. Hardware
  1. Communication hardware, interfaces and storage
    1. Buses and high-speed links

Recommendations

Parity logging overcoming the small write problem in redundant disk arrays
Special Issue: Proceedings of the 20th annual international symposium on Computer architecture (ISCA '93)

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 ...
Higher reliability redundant disk arrays: Organization, operation, and coding

Parity is a popular form of data protection in redundant arrays of inexpensive/independent disks (RAID). RAID5 dedicates one out of N disks to parity to mask single disk failures, that is, the contents of a block on a failed disk can be reconstructed by ...
The Performance of Parity Placements in Disk Arrays

Due to recent advances in central processing unit (CPU) and memory system performance, input/output (I/O) systems are increasingly limiting the performance of modern computer systems. Redundant arrays of inexpensive disks (RAID) have been proposed to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Computer Systems

ACM Transactions on Computer Systems Volume 12, Issue 3

Aug. 1994

95 pages

ISSN:0734-2071

EISSN:1557-7333

DOI:10.1145/185514

Editor:
Ken Birman
Cornell Univ., Ithaca, NY

Issue’s Table of Contents

Copyright © 1994 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 1994

Published in TOCS Volume 12, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

39
Total Citations
View Citations
678
Total Downloads

Downloads (Last 12 months)61
Downloads (Last 6 weeks)12

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

(2022)BibliographyStorage Systems10.1016/B978-0-32-390796-5.00023-1(641-693)Online publication date: 2022
https://doi.org/10.1016/B978-0-32-390796-5.00023-1
Thomasian A(2022)Redundant Arrays of Independent Disks - RAIDStorage Systems10.1016/B978-0-32-390796-5.00014-0(269-336)Online publication date: 2022
https://doi.org/10.1016/B978-0-32-390796-5.00014-0
Grawinkel MNagel LBrinkmann A(2016)LoneStar RAIDACM Transactions on Storage10.1145/284081012:1(1-29)Online publication date: 7-Jan-2016
https://dl.acm.org/doi/10.1145/2840810
Yu HLan YRen HChen Y(2012)Power-down Protection Technology in Embedded SystemProceedings of the 2012 4th International Conference on Intelligent Human-Machine Systems and Cybernetics - Volume 0210.1109/IHMSC.2012.139(179-182)Online publication date: 26-Aug-2012
https://dl.acm.org/doi/10.1109/IHMSC.2012.139
Thomasian A(2010)Why specialized disks for composite operations may be unnecessaryACM SIGARCH Computer Architecture News10.1145/1978907.197891238:5(20-27)Online publication date: 29-Apr-2010
https://dl.acm.org/doi/10.1145/1978907.1978912
Li MShu J(2010)DACOIEEE Transactions on Computers10.1109/TC.2010.2259:10(1350-1362)Online publication date: 1-Oct-2010
https://dl.acm.org/doi/10.1109/TC.2010.22
Thomasian ABlaum M(2009)Higher reliability redundant disk arraysACM Transactions on Storage10.1145/1629075.16290765:3(1-59)Online publication date: 30-Nov-2009
https://dl.acm.org/doi/10.1145/1629075.1629076
Ruan XShu Yin Manzanares AJiong Xie Zhiyang Ding Majors JQin X(2009)ECOS: An energy-efficient cluster storage system2009 IEEE 28th International Performance Computing and Communications Conference10.1109/PCCC.2009.5403814(79-86)Online publication date: Dec-2009
https://doi.org/10.1109/PCCC.2009.5403814
Carrera EBianchini R(2006)NWCache: Optimizing disk accesses via an optical network/write cache hybridParallel and Distributed Processing10.1007/BFb0097971(845-858)Online publication date: 28-Oct-2006
https://doi.org/10.1007/BFb0097971
Thomasian A(2005)Reconstruct versus read-modify writes in RAIDInformation Processing Letters10.5555/1062041.171102193:4(163-168)Online publication date: 28-Feb-2005
https://dl.acm.org/doi/10.5555/1062041.1711021
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents