MP-RAID: Mirroring and parity protected disk array

Redundant array of inexpensive disk （RAID）10 is known as the most reliable disk array architecture to tolerate up to half of total disk failures, but failure of two disks in the same mirror set still results in data loss. In this paper, we propose a new disk array architecture, mirroring and parity protected RAID （MP-RAID）, which combines both mirroring and parity techniques to further improve reliability of disk arrays. The main idea behind MP-RAID is to protect the data by both mirroring and parity techniques： keep two copies of data in the same mirror set and update the parity block in the log disk within the same parity groups. Reliability analysis shows that the reliability of MP-RAID, in terms of mean time to data loss （MTTDL）, is much better than RAID10 and RAID5.

A CASCADING LATIN SCHEME TO TOLERATE DOUBLE DISK FAILURES IN RAID ARCHITECTURES

In recent years,a lot of XOR-based coding schemes have been developed to tolerate double disk failures in Redundant Array of Independent Disks (RAID) architectures,such as EVENODD-code,X-code,B-code and BG-HEDP. Despite those researches,the decades-old strategy of Reed-Solomon (RS) code remains the only popular space-optimal Maximum Distance Separable (MDS) code for all but the smallest storage systems. The reason is that all those XOR-based schemes are too difficult to be implemented,it mainly because the coding-circle of those codes vary with the number of disks. By contrast,the coding-circle of RS code is a constant. In order to solve this problem,we develop a new MDS code named Latin code and a cascading scheme based on Latin code. The cascading Latin scheme is a nearly MDS code (with only one or two more parity disks compared with the MDS ones). Nev-ertheless,it keeps the coding-circle of the basic Latin code (i.e. a constant) and the low encod-ing/decoding complexity similar to other parity array codes.

Construction of Wrapped ρ-Labellings for RAID

The desire to speed up secondary storage systems has lead to the development of redundant arrays of independent disks （RAID） which incorporate redundancy utilizing erasure codes. A ＇cluttered ordering＇ is utilized for designing an effective writing order to a RAID system. Cohen, Colboum and Froncek （2001） gave a cyclic construction of cluttered orderings for the complete graph by utilizing the notion of a ＇wrapped p-labelling＇. Since wrapped p-labellings as cluttered orderings for the complete graph look such as ladders, they are also called as ladder orderings. Cohen and Colboum （2004） gave a characteristic of ladder orderings. In this paper, we give an algorithm in order to generate ladder orderings.

Extending and analysis of X-Code

X-Code is one of the most important redundant array of independent disk （RAID）-6 codes which are capable of tolerating double disk failures. However, the code length of X-Code is restricted to be a prime number, and such code length restriction of X-Code limits its usage in the real storage systems. Moreover, as a vertical RAID-6 code, X-Code can not be extended easily to an arbitrary code length like horizontal RAID-6 codes. In this paper, a novel and efficient code shortening algorithm for X-Code is proposed to extend X-Code to an arbitrary length. It can be further proved that the code shortening algorithm maintains the maximum-distance-separable （MDS） property of X-Code, and namely, the shortened X-Code is still MDS code with the optimal space efficiency. In the context of the shortening algorithm for X-Code, an in-depth performance analysis on X-Code at consecutive code lengths is conducted, and the impacts of the code shortening algorithm on the performance of X-Code in various performance metrics are revealed.

TSHOVER:A Novel Coding Scheme for Tolerating Triple Disk Failures in RAID/DRAID

This paper presents a novel method, called TSHOVER, for tolerating up to triple disk failures in RAID/DRAID architectures or others reliable storage systems. TSHOVER is two-dimensional code, which employs horizontal code and vertical code at the same time with simple exclusive-OR (XOR) computations. This paper shows the new step ascending concepts used in encoding, and it has the capability of realizing fault tolerance. TSHOVER has better data recovery ability to those disk network storage systems with relatively more dynamic changes in the number of disks. Compared with RS and STAR code, TSHOVER has better encoding performance. When updating a data strip, only 6 XOR operations are needed. Both experimental results and theoretical analyses show that TSHOVER has better performance and higher efficiency than other algorithms.

RDDP:An Efficient MDS Array Code on Toleration Triple Node Failures in Storage System

It is well known that erasure coding can be used in storage systems to efficiently store data while protecting against failures. Conventionally, the design of erasure codes has focused on the tradeoff between redundancy and reliability. Under this criterion, an maximum distance separable（MDS） code has optimal redundancy. In this paper, we address a new class of MDS array codes for tolerating triple node failures by extending the row di- agonal parity（RDP） code, named the RDDP（row double diagonal parity） code. The RDDP code takes advantages of good perform- ances of the RDP code with balanced I/0. A specific triple-erasure decoding algorithm to reduce decoding complexity is depicted by geometric graph, and it is easily implemented by software and hardware. The theoretical analysis shows that the comprehensive properties of the RDDP code are optimal, such as encoding and decoding efficiency, update efficiency and I/0 balance performance.

CSWL:Cross-SSD Wear-Leveling Method in SSD-Based RAID Systems for System Endurance and Performance

Flash memory has limited erasure/program cycles. Hence, to meet their advertised capacity all the time, flash-based solid state drives （SSDs） must prolong their life span through a wear-leveling mechanism. As a very important part of flash translation layer （FTL）, wear leveling is usually implemented in SSD controllers, which is called internal wear leveling. However, there is no wear leveling among SSDs in SSD-based redundant array of independent disks （RAIDs） systems, making some SSDs wear out faster than others. Once an SSD fails, reconstruction must be triggered immediately, but the cost of this process is so high that both system reliability and availability are affected seriously. We therefore propose cross-SSD wear leveling （CSWL） to enhance the endurance of entire SSD-based RAID systems. Under the workload of random access pattern, parity stripes suffer from much more updates because updating to a data stripe will cause the modification of other all related parity stripes. Based on this principle, we introduce an age-driven parity distribution scheme to guarantee wear leveling among flash SSDs and thereby prolong the endurance of RAID systems. Furthermore, age-driven lc,arity distribution benefits performance by maintaining better load balance the life span and performance of SSD-based RAID. With insignificant overhead, CSWL can significantly improve both