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

Article

Free access

Declustered disk array architectures with optimal and near-optimal parallelism

Authors:

Guillermo A. Alvarez,

Walter A. Burkhard,

Larry J. Stockmeyer,

Flaviu CristianAuthors Info & Claims

ISCA '98: Proceedings of the 25th annual international symposium on Computer architecture

Pages 109 - 120

https://doi.org/10.1145/279358.279374

Published: 16 April 1998 Publication History

Abstract

This paper investigates the placement of data and parity on redundant disk arrays. Declustered organizations have been traditionally used to achieve fast reconstruction of a failed disk's contents. In previous work, Holland and Gibson identified six desirable properties for ideal layouts; however, no declustered layout satisfying all properties has been published in the literature. We present a complete, constructive characterization of the collection of ideal declustered layouts possessing all six properties. Given that ideal layouts exist only for a limited set of configurations, we also present two novel layout families. PRIME and RELPR can tolerate multiple failures in a wide variety of configurations with slight deviations from the ideal. Our simulation studies show that the new layouts provide excellent parallel access performance and reduced incremental loads during degraded operation, when compared with previously published layouts. For large accesses and under high loads, response times for the new layouts are typically smaller than those of previously published declustered layouts by a factor of 2.5.

References

[1]

G. Alvarez, W. Burkhard, and F. Cristian. Tolerating multiple failures in RAID architectures with optimal storage and uniform declustering. In Proc. of the International Symposium on Computer Architecture, pages 62-72, 1997.

Digital Library

[2]

G. Alvarez, W. Burkhard, L. Stockmeyer, and E Cristian. Declustered disk array architectures with optimal and near-optimal parallelism. CS98-576, UCSD, 1998. http : //www- cse. ucsd. edu /groups /gemini /papers. html.

[3]

M. Blaum, J. Brady, J. Bruck, and J. Menon. Evenodd: An efficient scheme for tolerating double disk failures in RAID architectures, in Proc. of the International Symposium on Computer Architecture, pages 245-54, 1994.

Digital Library

[4]

W. Burkhard and J. Menon. Disk array storage system reliability. In Proc. of the International Symposium on Fault-tolerant Computing, pages 432-41, 1993.

[5]

P. Chen and E. Lee. Striping in a RAID level 5 disk array. In Proc. ofACM SIGMETRICS, pages 136--45, 1995.

Digital Library

[6]

W. Courtright, G. Gibson, M. Holland, and J. Zelenka. A structured approach to redundant disk array implementation. In Proc. of the International Symposium on Performance and Dependability, pages 11-20, 1996.

Digital Library

[7]

G. Gibson, L. Hellerstein, R. Karp, R. Katz, and D. Patterson. Coding techniques for handling failures in large disk arrays. In Proc. of the international Conference on Architectural Support for Programming Languages and Operating Systems, pages 123-32, 1989.

Digital Library

[8]

G. Gibson, D. Nagle, K. Amiri, E Chang, E. Feinberg, H. Gobioff, C. Lee, B. Ozceri, E. Riedel, D. Rochberg, and J. Zelenka. File server scaling with networkattached secure disks. In Proc. ofACM SIGMETRICS, pages 272-84, 1997.

Digital Library

[9]

M. Hall. Combinatorial Theory. Wiley, New York, 1986.

[10]

H. Hanani. Balanced Incomplete Block Designs and Related Designs. Discrete Mathematics, 1975.

[11]

M. Holland and G. Gibson. Parity declustering for continuous operation on redundant disk arrays. In Proc. of the International Conference on Architectural Support for Programming Languages and Operating Systems, pages 23-35, 1992.

Digital Library

[12]

M. C. Holland. On-Line Data Reconstruction In Redundant Disk Arrays. PhD thesis, Department of Electrical and Computer Engineering, Carnegie Mellon University, 1994.

Digital Library

[13]

E. Lee and R. Katz. Performance consequences of parity placement in disk arrays, in Proc. of the international Conference on Architectural Support for Programming Languages and Operating Systems, pages 190-99, 1991.

Digital Library

[14]

R. Muntz and J. Lui. Performance analysis of disk arrays under failure. In Proceedings of the 16th VLDB Conference, pages 162-73, 1990.

Digital Library

[15]

D. Patterson, G. Gibson, and R. Katz. A case for redundant arrays of inexpensive disks (RAID). In Proc. of the A CM SIGMOD International Conference on Management of Data, pages 109-16, 1988.

Digital Library

[16]

E. Schwabe and I. Sutherland. Improved paritydeclustered layouts for disk arrays. In Proc. of the Symposium on Parallel Algorithms and Architectures, pages 76-84, 1994.

Digital Library

[17]

A. Tomkins, H. Patterson, and G. Gibson. Informed multi-process prefetching and caching. In Proc. of ACM SIGMETRICS, pages 100-14, 1997.

Digital Library

[18]

X. Wu, J. Li, and H. Kameda. Reliability analysis of disk array organizations by considering uncorrectable bit errors. In Proc. of the 16th Symposium on Reliable Distributed Systems, pages 2-9, October 1997.

Digital Library

Cited By

Wang MMao JRana RBent JOlmez SGeorge ARansom GLi JGunawi HMohror KArnold DBadia R(2023)Design Considerations and Analysis of Multi-Level Erasure Coding in Large-Scale Data CentersProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1145/3581784.3607072(1-13)Online publication date: 12-Nov-2023
https://dl.acm.org/doi/10.1145/3581784.3607072
Zhang GWang ZMa XYang SHuang ZZheng W(2019)Determining Data Distribution for Large Disk Enclosures with 3-D Data TemplatesACM Transactions on Storage10.1145/334285815:4(1-38)Online publication date: 6-Dec-2019
https://dl.acm.org/doi/10.1145/3342858
Zhang GHuang ZMa XYang SWang ZZheng WAgrawal NRangaswami R(2018)RAID+Proceedings of the 16th USENIX Conference on File and Storage Technologies10.5555/3189759.3189786(279-293)Online publication date: 12-Feb-2018
https://dl.acm.org/doi/10.5555/3189759.3189786
Show More Cited By

Index Terms

Declustered disk array architectures with optimal and near-optimal parallelism

Recommendations

Declustered disk array architectures with optimal and near-optimal parallelism
Special Issue: Proceedings of the 25th annual international symposium on Computer architecture (ISCA '98)

This paper investigates the placement of data and parity on redundant disk arrays. Declustered organizations have been traditionally used to achieve fast reconstruction of a failed disk's contents. In previous work, Holland and Gibson identified six ...
Improved Parity-Declustered Layouts for Disk Arrays

Recently, parity-declustered layouts have been studied as a tool for reducing the time needed to reconstruct a failed disk in a disk array. Construction of such layouts for large disk arrays generally involves the use of a balanced incomplete block ...
Improved parity-declustered layouts for disk arrays
SPAA '94: Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures
Recently, parity-declustered layouts have been studied as a tool for reducing the time needed to reconstruct a failed disk in a disk array [5, 9]. Construction of such layouts for large disk arrays generally involves the use of a balanced incomplete ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ISCA '98: Proceedings of the 25th annual international symposium on Computer architecture

April 1998

402 pages

ISBN:0818684917

Chairmen:
Mateo Valero
Univ. Politecnica de Catalunya
,
Gurindar S. Sohi
Univ. of Wisconsin-Madison, Madison
,
Editor:
Doug DeGroot

ACM SIGARCH Computer Architecture News Volume 26, Issue 3
Special Issue: Proceedings of the 25th annual international symposium on Computer architecture (ISCA '98)
June 1998
379 pages
ISSN:0163-5964
DOI:10.1145/279361
Chairmen:
Mateo Valero
Univ. Politecnica de Catalunya, Barcelona, Spain
,
Gurindar S. Sohi
Univ. of Wisconsin-Madison, Madison
,
Editor:
Doug DeGroot
Issue’s Table of Contents

Copyright © Copyright © 1998 IEEE. All Rights Reserved.

Sponsors

SIGARCH: ACM Special Interest Group on Computer Architecture
IEEE-CS\TCCA: TC on Computer Arhitecture

Publisher

IEEE Computer Society

United States

Publication History

Published: 16 April 1998

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

ISCA98

Sponsor:

SIGARCH
IEEE-CS\TCCA

ISCA98: International Symposium on Computer Architecture

June 27 - July 2, 1998

Barcelona, Spain

Acceptance Rates

Overall Acceptance Rate 543 of 3,203 submissions, 17%

Upcoming Conference

ISCA '25

Sponsor:
sigarch

The 52nd Annual International Symposium on Computer Architecture

June 21 - 25, 2025

Tokyo , Japan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

35
Total Citations
View Citations
449
Total Downloads

Downloads (Last 12 months)55
Downloads (Last 6 weeks)11

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang MMao JRana RBent JOlmez SGeorge ARansom GLi JGunawi HMohror KArnold DBadia R(2023)Design Considerations and Analysis of Multi-Level Erasure Coding in Large-Scale Data CentersProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1145/3581784.3607072(1-13)Online publication date: 12-Nov-2023
https://dl.acm.org/doi/10.1145/3581784.3607072
Zhang GWang ZMa XYang SHuang ZZheng W(2019)Determining Data Distribution for Large Disk Enclosures with 3-D Data TemplatesACM Transactions on Storage10.1145/334285815:4(1-38)Online publication date: 6-Dec-2019
https://dl.acm.org/doi/10.1145/3342858
Zhang GHuang ZMa XYang SWang ZZheng WAgrawal NRangaswami R(2018)RAID+Proceedings of the 16th USENIX Conference on File and Storage Technologies10.5555/3189759.3189786(279-293)Online publication date: 12-Feb-2018
https://dl.acm.org/doi/10.5555/3189759.3189786
Pelley SMeisner DZandevakili PWenisch TUnderwood JHoe JAdve V(2010)Power routingProceedings of the fifteenth International Conference on Architectural support for programming languages and operating systems10.1145/1736020.1736047(231-242)Online publication date: 13-Mar-2010
https://dl.acm.org/doi/10.1145/1736020.1736047
Pelley SMeisner DZandevakili PWenisch TUnderwood J(2010)Power routingACM SIGPLAN Notices10.1145/1735971.173604745:3(231-242)Online publication date: 13-Mar-2010
https://dl.acm.org/doi/10.1145/1735971.1736047
Pelley SMeisner DZandevakili PWenisch TUnderwood J(2010)Power routingACM SIGARCH Computer Architecture News10.1145/1735970.173604738:1(231-242)Online publication date: 13-Mar-2010
https://dl.acm.org/doi/10.1145/1735970.1736047
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
Zhu HGu PWang JPapatheodorou TBanerjee UMendelson AGallivan K(2008)Shifted declusteringProceedings of the 22nd annual international conference on Supercomputing10.1145/1375527.1375549(134-144)Online publication date: 7-Jun-2008
https://dl.acm.org/doi/10.1145/1375527.1375549
Liu XWang GLiu J(2007)A double-objective genetic algorithm for parity declustering optimization in networked RAIDProceedings of the 7th international conference on Algorithms and architectures for parallel processing10.5555/1769115.1769159(415-420)Online publication date: 11-Jun-2007
https://dl.acm.org/doi/10.5555/1769115.1769159
Schwabe ESutherland I(2004)Efficient data mappings for parity-declustered data layoutsTheoretical Computer Science10.1016/j.tcs.2004.02.042325:3(391-407)Online publication date: 6-Oct-2004
https://dl.acm.org/doi/10.1016/j.tcs.2004.02.042
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 Publication

Media

Figures

Other

Tables

View Table of Contents