RAID0.5: design and implementation of a low cost disk array data protection method

RAID has long been established as an effective way to provide highly reliable as well as high-performance disk subsystems. However, reliability in RAID systems comes at the cost of extra disks. In this paper, we describe a mechanism that we have termed RAID0.5 that enables striped disks with very high data reliability but low disk cost. We take advantage of the fact that most disk systems use offline backup systems for disaster recovery. With the use of these offline backup systems, the disk system needs to only replicate data since the last backup, thus drastically reducing the storage space requirement. Though RAID0.5 has the same data loss characteristics of traditional mirroring, the lower storage space comes at the cost of lower availability. Thus, RAID0.5 is a tradeoff between lower disk cost and lower availability while still preserving very high data reliability. We present analytical reliability models and experimental results that demonstrate the enhanced reliability and performance of the proposed RAID0.5 system.     

MT2RAID:一种高可靠大规模磁盘阵列结构

传统的磁盘阵列一般采用集中式控制结构,其连接的底层磁盘数受系统总线的制约,容易出现性能瓶颈,且不能容两个以上磁盘出错。从模块化系统的组织方法出发,提出一种采用标准模块化存储单元组成的通过胖树结构互连的大规模磁盘阵列结构MT2RAID,分别就其各种数据分布的性能和可靠性进行了分析和讨论。原型系统测试结果表明,相比集中式磁盘阵列结构,MT2RAID也具有较高的性能。     

Stripped mirroring RAID architecture

Redundant arrays of independent disks (RAID) provide an efficient stable storage system for parallel access and fault tolerance. The most common fault tolerant RAID architecture is RAID-1 or RAID-5. The disadvantage of RAID-1 lies in excessive redundancy, while the write performance of RAID-5 is only 1/4 of that of RAID-0. In this paper, we propose a high performance and highly reliable disk array architecture, called stripped mirroring disk array (SMDA). It is a new solution to the small-write problem for disk array. SMDA stores the original data in two ways, one on a single disk and the other on a plurality of disks in RAID-0 by stripping. The reliability of the system is as good as RAID-1, but with a high throughput approaching that of RAID-0. Because SMDA omits the parity generation procedure when writing new data, it avoids the write performance loss often experienced in RAID-5.     

自修复磁盘阵列技术研究

以数据为中心的计算模式对数据的可靠性提出新的需求,高可靠存储设备成为高性能计算的基础.自从Xiotech公司提出ISE结构并取得成功后,关注磁盘失效之前的征兆而不是失效后的具体处理的"自修复"概念已成为磁盘阵列设计新的指导思想之一.提出存储系统可靠性系数的概念,分析单个磁盘可靠性与磁盘阵列可靠性关系,选择合适的磁盘S.M.A.R.T属性结合磁盘当前利用率和历史信息建立评定磁盘状态的T~2US算法,接着介绍RAID 5结合T2US监测的高可靠、自修复的RAID 5T结构,说明RAID 5T结构的运行方式和磁盘不符合T~2US监测标准时数据迁移策略,最后对结构的可靠性利用存储系统可靠性系数和MTTF分别进行了分析.     

Performance vs. cost of redundant arrays of inexpensive disks

Data redundancy has been widely used to increase data availability in critical applications and several methods have been proposed to organize redundant data across a disk array. Data redundancy consists of either total data replication or the spreading of the data across the disk array along with parity information which can be used to recover missing data in the event of disk failure. In this paper we present an extended comparative analysis, carried out by using discrete event simulation models, between two disk array architectures: the Redundant Arrays of Inexpensive Disks (RAID) level 1 architecture, based on data replication; and the RAID level 5 architecture, based on the use of parity information. The comparison takes both performance and cost aspects into account. We study the performance of these architectures simulating two application environments characterized by different sizes of the data accessed by I/O operations. In addition, several scheduling policies for I/O requests are considered and the impact of non-uniform access to data on performance is investigated.     

Orthogonal striping and mirroring in distributed RAID forI/O-centric cluster computing

This paper presents a new distributed disk-array architecture for achieving high I/O performance in scalable cluster computing. In a serverless cluster of computers, all distributed local disks can be integrated as a distributed-software redundant array of independent disks (ds-RAID) with a single I/O space. We report the new RAID-x design and its benchmark performance results. The advantage of RAID-x comes mainly from its orthogonal striping and mirroring (OSM) architecture. The bandwidth is enhanced with distributed striping across local and remote disks, while the reliability comes from orthogonal mirroring on local disks at the background. Our RAID-x design is experimentally compared with the RAID-5, RAID-10, and chained-declustering RAID through benchmarking on a research Linux cluster at USC. Andrew and Bonnie benchmark results are reported on all four disk-array architectures. Cooperative disk drivers and Linux extensions are developed to enable not only the single I/O space, but also the shared virtual memory and global file hierarchy. We reveal the effects of traffic rate and stripe unit size on I/O performance. Through scalability and overhead analysis, we find the strength of RAID-x in three areas: 1) improved aggregate I/O bandwidth especially for parallel writes, 2) orthogonal mirroring with low software overhead, and 3) enhanced scalability in cluster I/O processing. Architectural strengths and weakness of all four ds-RAID architectures are evaluated comparatively. The optimal choice among them depends on parallel read/write performance desired, the level of fault tolerance required, and the cost-effectiveness in specific I/O processing applications     

Buffer flush and address mapping scheme for flash memory solid-state disk

The flash memory solid-state disk (SSD) is emerging as a killer application for NAND flash memory due to its high performance and low power consumption. To attain high write performance, recent SSDs use an internal SDRAM write buffer and parallel architecture that uses interleaving techniques. In such architecture, coarse-grained address mapping called superblock mapping is inevitably used to exploit the parallel architecture. However, superblock mapping shows poor performance for random write requests. In this paper, we propose a novel victim block selection policy for the write buffer considering the parallel architecture of SSD. We also propose a multi-level address mapping scheme that supports small-sized write requests while utilizing the parallel architecture. Experimental results show that the proposed scheme improves the I/O performance of SSD by up to 64% compared to the existing technique.     

RAID5 performance with distributed sparing

Distributed sparing is a method to improve the performance of RAID5 disk arrays with respect to a dedicated sparing system with N+2 disks (including the spare disk), since it utilizes the bandwidth of all N+2 disks. We analyze the performance of RAID5 with distributed sparing in normal mode, degraded mode, and rebuild mode in an OLTP environment, which implies small reads and writes. The analysis in normal mode uses an M/G/1 queuing model, which takes into account the components of disk service time. In degraded mode, a low-cost approximate method is developed to estimate the mean response time of fork-join requests resulting from accesses to recreate lost data on the failed disk. Rebuild mode performance is analyzed by considering an M/G/1 vacationing server model with multiple vacations of different types to take into account differences in processing requirements for reading the first and subsequent tracks. An iterative solution method is used to estimate the mean response time of disk requests, as well as the time to read each disk, which is shown to be quite accurate through validation against simulation results. We next compare RAID5 performance in a system (1) without a cache; (2) with a cache; and (3) with a nonvolatile storage (NVS) cache. The last configuration, in addition to improved read response time due to cache hits, provides a fast-write capability, such that dirty blocks can be destaged asynchronously and at a lower priority than read requests, resulting in an improvement in read response time. The small write penalty is also reduced due to the possibility of repeated writes to dirty blocks in the cache and by taking advantage of disk geometry to efficiently destage multiple blocks at a time     

Performance Comparison of Mirrored Disk Scheduling Methods with a Shared Non-Volatile Cache

Mirrored disks or RAID1 is a popular disk array paradigm, which in addition to fault-tolerance, doubles the data access bandwidth. This is important in view of rapidly increasing disk capacities and the slow improvement in disk access time. Caching of dirty data blocks in a non-volatile storage (NVS) cache allows the destaging of dirty blocks to be deferrable, so as to improve the response time of read requests by giving them a higher priority than write requests. Destaging of dirty blocks in batches to take advantage of disk geometry entails in lowered disk utilization due to writes and improved performance for reads. Polyzois et al. [12] propose a scheduling policy for mirrored disks equipped with an NVS cache, so that one disk processes read requests, while the other disk is processing a write batch according to the CSCAN policy. We propose an improved scheduling policy as follows: (i) eliminating the forced idleness caused by the batch processing paradigm for write requests, i.e., allowing write requests to be processed individually; (ii) using SATF or even an exhaustive search, to reduce destaging time compared to CSCAN; (iii) introducing a threshold for the number of read requests, which when exceeded defers the destaging of dirty blocks. We compare these two scheduling policies with each other and also against prioritizing the processing of reads versus writes: (i) the head-of-the-line (HOL) priority queueing discipline, (ii) SATF with conditional priorities. It follows from simulation results that the new method outperforms Polyzois' method, which is even outperformed by the HOL priority policy. SATF with conditional priorities slightly outperforms the proposed method from the viewpoint of its throughput and response time, but is susceptible to more variability in response time. Recommended by: Ahmed Elmagarmid     

RAID控制器中I/O调度算法研究

介绍应用于RAID控制器的I/O调度算法的设计与实现.主要目标是把来自RAID模块针对每个磁盘的具体读写请求按照响应的策略放入对应磁盘的读写I/O队列.然后根据具体请求的优先级和读写特性,对响应请求在队列中的次序进行调整或者对前后项进行合并,实现I/O请求的调度策略.     

一种高可用对象存储系统的数据组织研究

通过对现有不同存储系统的容错能力进行认真分析,提出了一种新的高可用对象存储系统架构HAOSS(High Availability Object Storage System).HAOSS系统分两层:上层存储的对象采用在多个设备之间的数据备份的方式来实现高可靠性,多个备份能够同时对外提供服务,保证系统的高性能,但是磁盘利用率比较低.下层采用RAID5,RAID6以及RAID_Blaurn等不同的容错编码来实现多盘容错功能,磁盘利用率较高,但是由于编码越来越复杂,容错编码需要大量的计算,性能受到很大的影响.在数据组织上,新对象和热点对象放上层,这样大部分请求都能够在上层命中,从而保证系统的性能.下层主要用来放不常用的数据.磁盘利用率比较高.在1000Mbps以太网环境下对HAOSS性能进行了测试,结果表明,HAOSS顺序读写性能都比较好,最大可以达到104MB/s,达到1000Mb以太网的理论最大物理带宽.     

A reliable and energy-efficient storage system with erasure coding cache

In modern energy-saving replication storage systems, a primary group of disks is always powered up to serve incoming requests while other disks are often spun down to save energy during slack periods. However, since new writes cannot be immediately synchronized into all disks, system reliability is degraded. In this paper, we develop a high-reliability and energy-efficient replication storage system, named RERAID, based on RAID10. RERAID employs part of the free space in the primary disk group and uses erasure coding to construct a code cache at the front end to absorb new writes. Since code cache supports failure recovery of two or more disks by using erasure coding, RERAID guarantees a reliability comparable with that of the RAID10 storage system. In addition, we develop an algorithm, called erasure coding write (ECW), to buffer many small random writes into a few large writes, which are then written to the code cache in a parallel fashion sequentially to improve the write performance. Experimental results show that RERAID significantly improves write performance and saves more energy than existing solutions.     

Reconstruct versus read-modify writes in RAID

RAID5 (Redundant Arrays of Independent Disk level 5) is a popular paradigm, which uses parity to protect against single disk failures. A major shortcoming of RAID5 is the small write penalty, i.e., the cost of updating parity when a data block is modified. Read-modify writes and reconstruct writes are alternative methods for updating small data and parity blocks. We use a queuing formulation to determine conditions under which one method outperforms the other. Our analysis shows that in the case of RAID6 and more generally disk arrays with k check disks tolerating k disk failures, RCW outperforms RMW for higher values of N and G. We note that clustered RAID and variable scope of parity protection methods favor reconstruct writes. A dynamic scheme to determine the more desirable policy based on the availability of appropriate cached blocks is proposed.     

基于块I/O的RAID设计

磁盘阵列(RAID)是当前能够提供存储系统高可用性和高可靠性的一项重要技术。它通过软硬件的冗余和奇偶校验提供数据的重构和恢复。针对当前在RAID控制软件设计的过程中面临多次数据拷贝的问题,文中提出了一种基于块I/O的RAID系统设计。它利用最新的Linux内核所提供的BIO机制,插入到SCSI Target的中间层进行数据I/O的处理。它能屏蔽掉上层不同的设备驱动类型,提供到IP-SAN的无缝链接。实验表明,该设计能够减少数据的传输延迟,最大限度地提高数据传输过程中的吞吐率,避免了多次昂贵的内存拷贝操作。     

连续数据存储中面向RAID5的写操作优化设计

针对连续数据存储应用,如视频监控、连续数据保护(CDP)、虚拟磁带库(VTL)等,提出一种面向RAID5的写操作优化方法：首先进行基于区间映射(area mapping)的地址转换(AT),把非连续的I/O请求虚拟地址转换为连续的物理地址,以实现对磁盘阵列的连续写;然后,在缓冲区内保存应用程序发出的写数据块,并构造一个与RAID5的完整条带长度相等的对齐数据块,对齐数据块在RAID5上恰好占满整个条带,再发送给RAID5,以实现对RAID5的完全写.这样写入的数据块恰好占满RAID5的整个条带,不仅避免了因生成校验数据而产生重构写、读改写等额外I/O开销,而且数据块的连续写入有效降低了磁头的寻道时间,提高了RAID5的吞吐能力.实验表明,该写优化方法在有限降低RAID5读性能的同时,可大幅提高RAID5的写性能,在80%连续的负载下,使RAID5的数据传输率接近其最大值.在连续数据存储中该方法同样适用于RAID4和RAID6.     

APEX: adaptive disk scheduling framework with QoS support

APEX is an adaptive disk scheduling framework with Quality-of-Service (QoS) support designed for environments with highly varying disk bandwidth usage. APEX is based on a three-layer scheduling architecture: (1) the upper layer realizes different service classes using a set of queues; (2) the mid-layer distributes available disk bandwidth among these queues; and (3) the lower layer is handled by the disk itself, which does the final ordering of disk requests. We demonstrate the use of APEX in an example scenario, a Learning-on-Demand (LoD) application supported by a multimedia system, where students can search for and playback multimedia-based learning material. In this paper, we present the scheduling concepts of APEX which are based on an extended token bucket algorithm. The disk requests scheduled for service are assembled into batches in order to exploit the intelligence of modern disks. Combined with a specialized work-conservation scheme, this enables APEX to apply bandwidth where it is needed, without the loss of efficiency. We demonstrate, through simulations, that APEX provides both higher throughput and lower response times than other mixed-media disk schedulers while still avoiding deadline violations for real-time requests. We also show its robustness with respect to misaligned bandwidth allocation. The work was conducted while Ketil Lund was an employee at UniK – University Graduate Center, Kjeller, Norway.     

A multiple disk failure recovery scheme in RAID systems

In this paper, we propose a practical disk error recovery scheme tolerating multiple simultaneous disk failures in a typical RAID system, resulting in improvement in availability and reliability. The scheme is composed of the encoding and the decoding processes. The encoding process is defined by making one horizontal parity and a number of vertical parities. The decoding process is defined by a data recovering method for multiple disk failures including the parity disks. The proposed error recovery scheme is proven to correctly recover the original data for multiple simultaneous disk failures regardless of the positions of the failed disks. The proposed error recovery scheme only uses exclusive OR operations and simple arithmetic operations, which can be easily implemented on current RAID systems without hardware changes.     

构造高可靠性盘阵列结构的研究

本文比较分析了纠单错阵列与纠双错盘阵列的可靠性；指出若只考虑盘一级可靠性，纠双错阵列平均无故障时间（ＭＴＴＦ）是纠单错阵列的几千倍；介绍了一种新型的适用于阵列的纠双错编码——ＥＶＥＮＯＤＤ码，以及两种考虑阵列支撑硬件容错能力的阵列结构：正交结构和Ｃｒｏｓｓｈａｔｃｈ结构；指明将纠双错编码应用于正交结构或Ｃｒｏｓｓｈａｔｃｈ结构的盘阵列中，可大大提高阵列可靠性，并提出了一种应用现有单端口盘构造Ｃｒｏｓｓｈａｔｃｈ结构的方案     

Performance analysis of advanced I/O architectures for PC-based video servers

In the personal computing and workstation environments, more and more I/O adapters are becoming complete functional subsystems that are intelligent enough to handle I/O operations on their own without much intervention from the host processor. The IBM subsystem control block (SCB) architecture has been defined to enhance the potential of these intelligent adapters by defining services and conventions that deliver command information and data to and from the adapters. In recent years, a new storage architecture, the redundant array of independent disks (RAID), has been quickly gaining acceptance in the world of computing. In this paper, we discuss and present a performance analysis of the SCB architecture and disk array technology in typical video server environments. In particular, we would like to see whether a disk array can outperform a group of disks (of the same type, the same data capacity, and same cost) operating independently (not in parallel as in a disk array) in a video server environment where most disk I/O operations are large sequential reads.     

Reducing I/O variability using dynamic I/O path characterization in petascale storage systems

In petascale systems with a million CPU cores, scalable and consistent I/O performance is becoming increasingly difficult to sustain mainly because of I/O variability. The I/O variability is caused by concurrently running processes/jobs competing for I/O or a RAID rebuild when a disk drive fails. We present a mechanism that stripes across a selected subset of I/O nodes with the lightest workload at runtime to achieve the highest I/O bandwidth available in the system. In this paper, we propose a probing mechanism to enable application-level dynamic file striping to mitigate I/O variability. We implement the proposed mechanism in the high-level I/O library that enables memory-to-file data layout transformation and allows transparent file partitioning using subfiling. Subfiling is a technique that partitions data into a set of files of smaller size and manages file access to them, making data to be treated as a single, normal file to users. We demonstrate that our bandwidth probing mechanism can successfully identify temporally slower I/O nodes without noticeable runtime overhead. Experimental results on NERSC’s systems also show that our approach isolates I/O variability effectively on shared systems and improves overall collective I/O performance with less variation.