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

research-article

Sector-Disk (SD) Erasure Codes for Mixed Failure Modes in RAID Systems

Authors:

James S. Plank,

Mario BlaumAuthors Info & Claims

ACM Transactions on Storage (TOS), Volume 10, Issue 1

Article No.: 4, Pages 1 - 17

https://doi.org/10.1145/2560013

Published: 01 January 2014 Publication History

Abstract

Traditionally, when storage systems employ erasure codes, they are designed to tolerate the failures of entire disks. However, the most common types of failures are latent sector failures, which only affect individual disk sectors, and block failures which arise through wear on SSD’s. This article introduces SD codes, which are designed to tolerate combinations of disk and sector failures. As such, they consume far less storage resources than traditional erasure codes. We specify the codes with enough detail for the storage practitioner to employ them, discuss their practical properties, and detail an open-source implementation.

References

[1]

Amvrosiadis, G., Oprea, A., and Schroeder, B. 2012. Practical scrubbing: Getting to the bad sector at the right time. In Proceedings of the International Conference on Dependable Systems and Networks (DSN’12). IEEE.

Digital Library

[2]

Bairavasundaram, L. N., Goodson, G., Schroeder, B., Arpaci-Dusseau, A. C., and Arpaci-Dusseau, R. H. 2008. An analysis of data corruption in the storage stack. In Proceedings of the 6th USENIX Conference on File and Storage Technologies (FAST’08).

Digital Library

[3]

Balakrishnan, M., Kadav, A., Prabhakaran, V., and Malkhi, D. 2010. Differential RAID: Rethinking RAID for SSD reliability. ACM Trans. Storage 6, 2.

Digital Library

[4]

Blaum, M. and Plank, J. S. 2013. Construction of two SD codes. arXiv:1305.1221 {cs.IT}.

[5]

Blaum, M. and Roth, R. M. 1999. On lowest density MDS codes. IEEE Trans. Inf. Theory 45, 1, 46--59.

Digital Library

[6]

Blaum, M., Brady, J., Bruck, J., and Menon, J. 1995. EVENODD: An efficient scheme for tolerating double disk failures in RAID architectures. IEEE Trans. Comput. 44, 2, 192--202.

Digital Library

[7]

Blaum, M., Hafner, J. L., and Hetzler, S. 2012. Partial-MDS codes and their application to RAID type of architectures. IBM Res. rep. RJ10498 (ALM1202-001).

[8]

Blomer, J., Kalfane, M., Karpinski, M., Karp, R., Luby, M., and Zuckerman, D. 1995. An XOR-based erasure-resilient coding scheme. Tech. rep. TR-95-048, International Computer Science Institute.

[9]

Bowers, K., Juels, A., and Oprea, A. 2009. HAIL: A high-availability and integrity layer for cloud storage. In Proceedings of the 16th ACM Conference on Computer and Communications Security.

Digital Library

[10]

Cadambe, V., Huang, C., Li, J., and Mehrotra, S. 2011. Compound codes for optimal repair in MDS code based distributed storage systems. In Proceedings of the Asilomar Conference on Signals, Systems and Computers.

[11]

Calder, B., Wang, J., Ogus, A., Nilakantan, N., Skjolsvold, A., McKelvie, S., Xu, Y., Srivastav, S., Wu, J., Simitci, H., Haridas, J., Uddaraju, C., Khatri, H., Edwards, A., Bedekar, V., Mainali, S., Abbasi, R., Agarwal, A., ul Haq, M. F., ul Haq, M. I., Bhardwaj, D., Dayanand, S., Adusumilli, A., McNett, M., Sankaran, S., Manivannan, K., and Rigas, L. 2011. Windows Azure Storage: A highly available cloud storage service with strong consistency. In Proceedings of the 23rd ACM Symposium on Operating Systems Principles (SOSP’11).

Digital Library

[12]

Chen, B., Curtmola, R., Ateniese, G., and Burns, R. 2010. Remote data checking for network coding-based distributed storage systems. In Proceedings of the Cloud Computing Security Workshop.

Digital Library

[13]

Corbett, P., English, B., Goel, A., Grcanac, T., Kleiman, S., Leong, J., and Sankar, S. 2004. Row diagonal parity for double disk failure correction. In Proceedings of the 3rd USENIX Conference on File and Storage Technologies (FAST’04).

Digital Library

[14]

Dholakia, A., Eleftheriou, E., Hu, X. Y., Iliadis, I., Menon, J., and Rao, K. K. 2008. A new intra-disk redundancy scheme for high-reliability RAID storage systems in the presence of unrecoverable errors. ACM Trans. Storage 4, 1, 1--42.

Digital Library

[15]

Dimakis, A. G., Ramchandran, K., Wu, Y., and Suh, C. 2011. A survey on network codes for distributed storage. Proc. IEEE 99, 3.

[16]

Edwards, J. K., Ellard, D., Everhart, C., Fair, R., Hamilton, E., Kahn, A., Kanevsky, A., Lentini, J., Prakash, A., Smith, K. A., and Zayas, E. 2008. FlexVol: Flexible, efficient file volume virtualization in WAFL. In Proceedings of the USENIX Annual Technical Conference. 129--142.

Digital Library

[17]

Elerath, J. G. and Pecht, M. 2009. A highly accurate method for assessing reliability of redundant arrays of inexpensive disks. IEEE Trans. Comput. 58, 3, 289--299.

Digital Library

[18]

Ghemawat, S., Gobioff, H., and Leung, S. T. 2003. The Google file system. In Proceedings of the 19th ACM Symposium on Operating Systems Principles (SOSP’03).

Digital Library

[19]

Gopalan, P., Huang, C., Simitci, H., and Yekhanin, S. 2012. On the locality of codeword symbols. IEEE Trans. Inf. Theory 58, 11.

Digital Library

[20]

Greenan, K., Miller, E., and Schwartz, T. J. 2008. Optimizing galois field arithmetic for diverse processor architectures and applications. In Proceedings of the 16th IEEE Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS’08).

[21]

Greenan, K. M., Long, D. D., Miller, E. L., Schwarz, T. J. E., and Wildani, A. 2009. Building flexible, fault-tolerant flash-based storage systems. In Proceedings of the 5th Workshop on Hot Topics in Dependability.

[22]

Greenan, K. M., Li, X., and Wylie, J. J. 2010. Flat XOR-based erasure codes in storage systems: Constructions, efficient recovery and tradeoffs. In Proceedings of the 26th IEEE Symposium on Massive Storage Systems and Technologies (MSST’10).

Digital Library

[23]

Hafner, J. L. 2006. HoVer erasure codes for disk arrays. In Proceedings of the IEEE International Conference on Dependable Systems and Networks (DSN’06).

Digital Library

[24]

Hafner, J. L., Deenadhayalan, V., Belluomini, W., and Rao, K. 2008. Undetected disk errors in RAID arrays. IBM J. Res. Devel. 52, 4/5, 418--425.

Digital Library

[25]

Hu, Y., Chen, H. C. H., Lee, P. P. C., and Tang, Y. 2012. NCCloud: Applying network coding for the storage repair in a cloud-of-clouds. In Proceedings of the 10th USENIX Conference on File and Storage Technologies (FAST’12).

Digital Library

[26]

Huang, C., Chen, M., and Li, J. 2007. Pyramid codes: Flexible schemes to trade space for access efficienty in reliable data storage systems. In Proceedings of the 6th IEEE International Symposium on Network Computing Applications (NCA’07).

[27]

Huang, C., Simitci, H., Xu, Y., Ogus, A., Calder, B., Gopalan, P., Li, J., and Yekhanin, S. 2012. Erasure coding in Windows Azure storage. In Proceedings of the USENIX Annual Technical Conference.

Digital Library

[28]

Josephson, W. K., Bongo, L. A., Flynn, D., and Li, K. 2010. DFS: A file system for virtualized flash storage. In Proceedings of the 8th USENIX Conference on File and Storage Technologies (FAST’10).

Digital Library

[29]

Kenchammana-Hosekote, D., He, D., and Hafner, J. L. 2007. REO: A generic RAID engine and optimizer. In Proceedings of the 5th USENIX Conference on File and Storage Technologies (FAST’07). 261--276.

Digital Library

[30]

Khan, O., Burns, R., Plank, J. S., Pierce, W., and Huang, C. 2012. Rethinking erasure codes for cloud file systems: Minimizing I/O for recovery and degraded reads. In Proceedings of the 10th USENIX Conference on File and Storage Technologies (FAST’12).

Digital Library

[31]

Klein, H. and Keller, J. 2009. Storage architecture with integrity, redundancy and encryption. In Proceedings of the 23rd IEEE International Symposium on Parallel and Distributed Processing.

Digital Library

[32]

Lastras-Montaño, L. A., Meaney, P. J., Stephens, E., Trager, B. M., O’Connor, J., and Alves, L. C. 2011. A new class of array codes for memory storage. In Proceedings of the Information Theory and Applications Workshop (ITA).

[33]

Li, M., Shu, J., and Zheng, W. 2009. GRID codes: Strip-based erasure codes with high fault tolerance for storage systems. ACM Trans. Storage 4, 4.

Digital Library

[34]

Li, X., Marchant, A., Shah, M. A., Smathers, K., Tucek, J., Uysal, M., and Wylie, J. J. 2010. Efficient eventual consistency in Pahoehoe, an erasure-coded key-blob archive. In Proceedings of the International Conference on Dependable Systems and Networks (DSN’10). IEEE.

[35]

Luby, M. 2002. LT codes. In Proceedings of the IEEE Symposium on Foundations of Computer Science.

Digital Library

[36]

Luo, J., Bowers, K. D., Oprea, A., and Xu, L. 2012. Efficient software implementations of large finite fields GF(2ⁿ) for secure storage applications. ACM Trans. Storage 8, 2.

Digital Library

[37]

MacWilliams, F. J. and Sloane, N. J. A. 1977. The Theory of Error-Correcting Codes, Part I. North-Holland Publishing Company, Amsterdam.

[38]

Oh, Y., Choi, J., Lee, D., and Noh, S. H. 2012. Caching less for better performance: Balancing cache size and update cost of flash memory cache in hybrid storage systems. In Proceedings of the 10th USENIX Conference on File and Storage Technologies (FAST’12).

Digital Library

[39]

Onion Networks. 2001. Java FEC Library v1.0.3. Open source code distribution: http://onionnetworks.com/fec/javadoc/.

[40]

Oprea, A. and Juels, A. 2010. A clean-slate look at disk scrubbing. In Proceedings of the 8th USENIX Conference on File and Storage Technologies (FAST’10). 57--70.

Digital Library

[41]

Ousterhout, J. K. and Douglis, F. 1989. Beating the I/O bottleneck: A case for log-structured file systems. Oper. Syst. Rev. 23, 1, 11--27.

Digital Library

[42]

Partow, A. 2000-2007. Schifra Reed-Solomon ECC Library. Open source code distribution: http://www.schifra.com/downloads.html.

[43]

Peterson, W. W. and Weldon, Jr., E. J. 1972. Error-Correcting Codes 2nd Ed. The MIT Press, Cambridge, MA.

[44]

Plank, J. S. 1997. A tutorial on Reed-Solomon coding for fault-tolerance in RAID-like systems. Softw. Pract. Exper. 27, 9, 995--1012.

Digital Library

[45]

Plank, J. S. and Huang, C. 2013. Tutorial: Erasure coding for storage applications. In Proceedings of the 11th USENIX Conference on File and Storage Technologies (FAST’13).

[46]

Plank, J. S., Luo, J., Schuman, C. D., Xu, L., and Wilcox-O’Hearn, Z. 2009. A performance evaluation and examination of open-source erasure coding libraries for storage. In Proceedings of the 7th USENIX Conference on File and Storage Technologies (FAST’09). 253--265.

Digital Library

[47]

Plank, J. S., Blaum, M., and Hafner, J. L. 2013a. SD codes: Erasure codes designed for how storage systems really fail. In Proceedings of the 11th USENIX Conference on File and Storage Technologies (FAST’13).

Digital Library

[48]

Plank, J. S., Greenan, K. M., and Miller, E. L. 2013b. Screaming fast Galois Field arithmetic using Intel SIMD instructions. In Proceedings of the 11th USENIX Conference on File and Storage Technologies (FAST’13).

Digital Library

[49]

Resch, J. K. and Plank, J. S. 2011. AONT-RS: Blending security and performance in dispersed storage systems. In Proceedings of the 9th USENIX Conference on File and Storage Technologies (FAST’11). 191--202.

Digital Library

[50]

Rhea, S., Eaton, P., Geels, D., Weatherspoon, H., Zhao, B., and Kubiatowitz, J. 2003. Pond: The OceanStore prototype. In Proceedings of the 2nd USENIX Conference on File and Storage Technologies (FAST’03).

Digital Library

[51]

Schroeder, B. and Gibson, G. 2007. Disk failures in the real world: What does an MTTF of 1,000,000 mean to you? In Proceedings of the 5th USENIX Conference on File and Storage Technologies (FAST’07).

Digital Library

[52]

Schroeder, B., Damouras, S., and Gill, P. 2010. Understanding latent sector errors and how to protect against them. In Proceedings of the 8th USENIX Conference on File and Storage Technologies (FAST’10). 71--84.

Digital Library

[53]

Seltzer, M., Bostic, K., McKusick, M., and Staelin, C. 1993. An implementation of a log-structured file system for UNIX. In Conference Proceedings of the USENIX Winter 1993 Technical Conference. 307--326.

Digital Library

[54]

Storer, M. W., Greenan, K. M., Miller, E. L., and Voruganti, K. 2008. Pergamum: Replacing tape with energy efficient, reliable, disk-based archival storage. In Proceedings of the 6th USENIX Conference on File and Storage Technologies (FAST’08). 1--16.

Digital Library

[55]

Storer, M. W., Greenan, K. M., Miller, E. L., and Voruganti, K. 2009. POTSHARDS -- A secure, long-term storage system. ACM Trans. Storage 5, 2.

Digital Library

[56]

Suh, C. and Ramchandran, K. 2010. Exact regeneration codes for distributed storage repair using interference alignment. In Proceedings of the IEEE International Symposium on Information Theory (ISIT).

[57]

Wang, Z., Dimakis, A. G., and Bruck, J. 2010. Rebuilding for array codes in distributed storage systems. In Proceedings of the GLOBECOM ACTEMT Workshop. 1905--1909.

[58]

Warner, B., Wilcox-O’Hearn, Z., and Kinninmont, R. 2008. Tahoe: A secure distributed filesystem. White paper. http://allmydata.org/~warner/pycon-tahoe.html.

[59]

Welch, B., Unangst, M., Abbasi, Z., Gibson, G., Mueller, B., Small, J., Zelenka, J., and Zhou, B. 2008. Scalable performance of the Panasas parallel file system. In Proceedings of the 6th USENIX Conference on File and Storage Technologies (FAST’08). 17--33.

Digital Library

[60]

Xiang, L., Xu, Y., Lui, J. C. S., and Chang, Q. 2010. Optimal recovery of single disk failure in RDP code storage systems. In Proceedings of the ACM SIGMETRICS.

Digital Library

[61]

Xu, L. 2005. Hydra: A platform for survivable and secure data storage systems. In Proceedings of the ACM International Workshop on Storage Security and Survivability (StorageSS’05).

Digital Library

Cited By

Commey DMai BHounsinou SCrosby G(2024)Securing Blockchain-Based IoT Systems: A ReviewIEEE Access10.1109/ACCESS.2024.342849012(98856-98881)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3428490
Cai HSchwartz M(2023)A Bound on the Minimal Field Size of LRCs, and Cyclic MR Codes That Attain ItIEEE Transactions on Information Theory10.1109/TIT.2022.322595369:4(2240-2260)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1109/TIT.2022.3225953
Blaum M(2022)Multiple-Layer Integrated Interleaved Codes: A Class of Hierarchical Locally Recoverable CodesIEEE Transactions on Information Theory10.1109/TIT.2022.316621068:8(5098-5111)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1109/TIT.2022.3166210
Show More Cited By

Index Terms

Sector-Disk (SD) Erasure Codes for Mixed Failure Modes in RAID Systems

Recommendations

Minimum density RAID-6 codes

RAID-6 codes protect disk array storage systems from two-disk failures. This article presents a complete treatment of a class of RAID-6 codes, called minimum density RAID-6 codes, that have an optimal blend of performance properties. There are two ...
HPDA: A hybrid parity-based disk array for enhanced performance and reliability

Flash-based Solid State Drive (SSD) has been productively shipped and deployed in large scale storage systems. However, a single flash-based SSD cannot satisfy the capacity, performance and reliability requirements of the modern storage systems that ...
Hierarchical RAID: Design, performance, reliability, and recovery

Hierarchical RAID (HRAID) extends the RAID paradigm to mask the failure of whole Storage Nodes (SNs) or bricks, where each SN is a disk array with a certain RAID level. HRAIDk/@? with N SNs and M disks per SN tolerates k SN failures and @? disk failures ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Storage

ACM Transactions on Storage Volume 10, Issue 1

January 2014

94 pages

ISSN:1553-3077

EISSN:1553-3093

DOI:10.1145/2578042

Editor:
Darrell Long
University of California Santa Cruz, USA

Issue’s Table of Contents

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 2014

Accepted: 01 June 2013

Received: 01 May 2013

Published in TOS Volume 10, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

49
Total Citations
View Citations
666
Total Downloads

Downloads (Last 12 months)21
Downloads (Last 6 weeks)1

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Commey DMai BHounsinou SCrosby G(2024)Securing Blockchain-Based IoT Systems: A ReviewIEEE Access10.1109/ACCESS.2024.342849012(98856-98881)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3428490
Cai HSchwartz M(2023)A Bound on the Minimal Field Size of LRCs, and Cyclic MR Codes That Attain ItIEEE Transactions on Information Theory10.1109/TIT.2022.322595369:4(2240-2260)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1109/TIT.2022.3225953
Blaum M(2022)Multiple-Layer Integrated Interleaved Codes: A Class of Hierarchical Locally Recoverable CodesIEEE Transactions on Information Theory10.1109/TIT.2022.316621068:8(5098-5111)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1109/TIT.2022.3166210
Cai HMiao YSchwartz MTang X(2022)A Construction of Maximally Recoverable Codes With Order-Optimal Field SizeIEEE Transactions on Information Theory10.1109/TIT.2021.312001668:1(204-212)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1109/TIT.2021.3120016
Cai HSchwartz M(2022)A Bound on the Minimal Field Size of LRCs, and Cyclic MR Codes That Attain It2022 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT50566.2022.9834854(2625-2630)Online publication date: 26-Jun-2022
https://dl.acm.org/doi/10.1109/ISIT50566.2022.9834854
Tang DCai H(2021)A Novel Decoding Method for the Erasure CodesSecurity and Communication Networks10.1155/2021/87556972021Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1155/2021/8755697
Kong XWang XGe G(2021)New Constructions of Optimal Locally Repairable Codes With Super-Linear LengthIEEE Transactions on Information Theory10.1109/TIT.2021.310333067:10(6491-6506)Online publication date: Oct-2021
https://doi.org/10.1109/TIT.2021.3103330
Cai HSchwartz M(2021)On Optimal Locally Repairable Codes and Generalized Sector-Disk CodesIEEE Transactions on Information Theory10.1109/TIT.2020.303726867:2(686-704)Online publication date: Feb-2021
https://doi.org/10.1109/TIT.2020.3037268
Kim CNo J(2021)New Design and Analysis of Error-Resilient LRCs for DSSs With Silent Disk ErrorsIEEE Access10.1109/ACCESS.2021.31078389(124463-124477)Online publication date: 2021
https://doi.org/10.1109/ACCESS.2021.3107838
Kolosov OYadgar GLiram MTamo IBarg A(2020)On Fault Tolerance, Locality, and Optimality in Locally Repairable CodesACM Transactions on Storage10.1145/338183216:2(1-32)Online publication date: 22-May-2020
https://dl.acm.org/doi/10.1145/3381832
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents