Reliable Storage

Description

The emergence of low-power archival, petabyte-scale storage systems and novel flash-based systems motivates tradeoffs between erasure encoding schemes. While new erasure codes are being developed within both the coding theory and storage systems community, no clear winner has emerged from the performance, reliability and space efficiency tradeoff space. Obviously, both the underlying storage system and application have a huge effect on how to encode data for fault tolerance. Thus, each scheme must be thoroughly analyzed for use in a particular system. We divide erasure codes into three classes: linear MDS codes, XOR-based array codes and XOR-based flat codes. Linear MDS codes, such as Reed-Solomon codes, exhibit optimal space-efficiency and flexible fault tolerance, but turn out to be computationally expensive in practice. Most array codes are space-optimal and less computationally expensive than Reed-Solomon, but are only able to sustain a fixed-maximum number of faults. Finally, XOR-based flat codes, such as Low-Density Parity Check (LDPC) codes, are not generally space-optimal, but tend to be computationally inexpensive, facilitate irregular fault tolerance and interesting localization properties.

First and foremost, we aim to provide the proper application of erasure codes to storage systems. For instance, in the Pergamum project, we found that the use of a Product code can effectively eliminate latent sector faults. Going forward we plan to explore how the structure and layout of certain erasure codes can be exploited to save power (through fragment recovery) in an archival system and how these choices affect reliability. Much of our research is also focused on the use of non-volatile memories, such as Flash, for reliable and power-efficient mass storage. Flash memory exhibits bit error rates that are much higher than disk, while device failure rates are much lower. Our aim is to exploit this disparity and provide robust reliability mechanisms in Flash without compromising performance. We are currently exploring reliable Flash-based storage systems with Network Appliance.

Second, given the inherent structural differences between the classes of codes, we developed a robust and general framework for analyzing the reliability of erasure codes codes in an apples-to-apples fashion. We found that specific assumptions made with respect to current modeling techniques (e.g. Markov models) lack flexibility, become very complicated as fault tolerance increases and may produce inaccurate reliability estimates beyond single disk fault tolerance. To this end, we have developed a generalized simulation framework. Given a storage system configuration and device failure characteristics (whole device and block-level), we are able to compare the reliability of array codes, flat codes and MDS codes for any given system configuration. In addition, previous analytic models assumed homogeneity among the devices; our framework can handle heterogeneous devices. We have recently performed a study that shows how code fragment layout affects reliability when a system contains devices with heterogeneous failure rates.

Status

Past research focused on reliability mechanisms and their analysis in very large storage systems. Most of this research was carried out within the object-based storage project and influenced some of the reliability mechanisms in the Ceph distributed file system.

In addition to our primary research projects, we have also developed large-stripe erasure codes called Disaster Recovery Codes and techniques for efficient Galois field multiplication. We are also currently working on ramp-like schemes for secure information dispersal. We have developed software packages for Galois field arithmetic, Reed-Solomon erasure codes and solving Markov models. We are currently in the process of releasing all three packages along with Python modules used to efficiently examine the recoverability of fragments generated by XOR-based codes in a power-managed system.

Publications

• Kevin Greenan, Ethan L. Miller, Jay Wylie, Reliability of XOR-based erasure codes on heterogeneous devices, Proceedings of the 38th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN 2008), June 2008.
• Neerja Bhatnagar, Kevin Greenan, Rosie Wacha, Ethan L. Miller, Darrell D. E. Long, Energy-Reliability Trade-offs in Sensor Networks, Proceedings of the Fifth Workshop on Embedded Networked Sensors (HotEmNets 2008), June 2008.
• Mark W. Storer, Kevin Greenan, Ethan L. Miller, Kaladhar Voruganti, Pergamum: Replacing Tape with Energy Efficient, Reliable, Disk-Based Archival Storage, Proceedings of the 6th USENIX Conference on File and Storage Technologies (FAST '08), February 2008, pages 1-16. [slides]
• Kevin Greenan, Ethan L. Miller, Thomas Schwarz, Darrell D. E. Long, Disaster Recovery Codes: Increasing Reliability with Large-Stripe Error Correction Codes, Proceedings of the 3rd International Workshop on Storage Security and Survivability (StorageSS 2007), held in conjunction with the 14th ACM Conference on Computer and Communications Security (CCS 2007), October 2007.
• Kevin Greenan, Ethan L. Miller, Thomas Schwarz, Analysis and Construction of Galois Fields for Efficient Storage Reliability, Technical Report UCSC-SSRC-07-09, August 2007.
• Kevin Greenan, Ethan L. Miller, PRIMS : Making NVRAM Suitable for Extremely Reliable Storage, short paper in Proceedings of the 3rd Workshop on Hot Topics in System Dependability (HotDep '07), June 2007.
• Jehan-François Pâris, Thomas Schwarz, Darrell D. E. Long, Self-Adaptive Two-Dimensional RAID Arrays, Proceedings of the International Performance Conference on Computers and Communication (IPCCC '07), April 2007.
• Mark W. Storer, Kevin Greenan, Ethan L. Miller, Long-Term Threats to Secure Archives, Proceedings of the 2nd ACM Workshop on Storage Security and Survivability (StorageSS 2006), October 2006.
• Kevin Greenan, Ethan L. Miller, Reliability Mechanisms for File Systems Using Non-Volatile Memory as a Metadata Store, Proceedings of the 6th ACM & IEEE Conference on Embedded Software (EMSOFT '06), October 2006, pages 178-187.
• Mark W. Storer, Kevin Greenan, Ethan L. Miller, Kaladhar Voruganti, POTSHARDS: Secure Long-Term Archival Storage Without Encryption, Technical Report UCSC-SSRC-06-03, Storage Systems Research Center, University of California, Santa Cruz, September 2006.
• Thomas Schwarz, Ethan L. Miller, Store, forget, and check: Using algebraic signatures to check remotely administered storage, Proceedings of the IEEE Int'l Conference on Distributed Computing Systems (ICDCS '06), July 2006. [slides]
• Thomas Schwarz, Qin Xin, Ethan L. Miller, Darrell D. E. Long, Andy Hospodor, Spencer Ng, Disk Scrubbing in Large Archival Storage Systems, Proceedings of the 12th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS '04), October 2004, pages 409-418. Won Best Paper award.
• Qin Xin, Ethan L. Miller, Thomas Schwarz, Evaluation of Distributed Recovery in Large-Scale Storage Systems, Proceedings of the 13th IEEE International Symposium on High Performance Distributed Computing (HPDC 2004), June 2004, pages 172-181.
• Qin Xin, Ethan L. Miller, Thomas Schwarz, Darrell D. E. Long, Scott A. Brandt, Witold Litwin, Reliability Mechanisms for Very large Storage Systems, Proceedings of the 20th IEEE / 11th NASA Goddard Conference on Mass Storage Systems and Technologies, April 2003, pages 146-156.