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...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.展开更多
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. Despi...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.展开更多
One way to increase storage density is using a shingled magnetic recording(SMR)disk.We propose a novel use of SMR disks with RAID(redundant array of independent disks)arrays,specifically building upon and compared wit...One way to increase storage density is using a shingled magnetic recording(SMR)disk.We propose a novel use of SMR disks with RAID(redundant array of independent disks)arrays,specifically building upon and compared with a basic RAID 4 arrangement.The proposed scheme(called RAID 4SMR)has the potential to improve the performance of a traditional RAID 4 array with SMR disks.Our evaluation shows that compared with the standard RAID 4,when using update in-place in RAID arrays,RAID 4SMR with garbage collection not just can allow the adoption of SMR disks with a reduced performance penalty,but offers a performance improvement of up to 56%.展开更多
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 redundan...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.展开更多
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 c...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.展开更多
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...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展开更多
基金supported by the National Basic Research Program of China (Grant Nos.2011CB302300, 2011CB302301)the National High-Technology Research and Development Program of China (Grant Nos.2009AA01A401,2009AA01A402)+1 种基金the National Natural Science Foundation of China (Grant Nos.60873028, 60933002, 61025008)the Changjiang Innovation Group of Education of China (Grant No.IRT0725)
文摘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.
基金Supported in part by the National High Technology Re-search and Development Program of China (2008 AA01Z-401)the National Science Foundation of China (No.60903028)+1 种基金Doctoral Fund of Ministry of Education of China (20070055054)Science and Technology De-velopment Plan of Tianjin (08JCYBJC13000)
文摘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.
文摘One way to increase storage density is using a shingled magnetic recording(SMR)disk.We propose a novel use of SMR disks with RAID(redundant array of independent disks)arrays,specifically building upon and compared with a basic RAID 4 arrangement.The proposed scheme(called RAID 4SMR)has the potential to improve the performance of a traditional RAID 4 array with SMR disks.Our evaluation shows that compared with the standard RAID 4,when using update in-place in RAID arrays,RAID 4SMR with garbage collection not just can allow the adoption of SMR disks with a reduced performance penalty,but offers a performance improvement of up to 56%.
基金Supported by the National Natural Science Foundation of China(60873216)the Key Project of Sichuan Provincial Department of Education(12ZA223)
文摘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.
基金the National Natural Science Foundation of China (No. 60403043)
文摘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.
基金Supported by the National High Technology Research and Development 863 Program of China under Grant No.2013AA013201the National Natural Science Foundation of China under Grant Nos.61025009,61232003,61120106005,61170288
文摘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
