In this paper, we study the performance of solid-state drives that employ flash technology as storage medium. Our prime objective is to understand how the scheduling of the user-generated read and write commands and the read, write, and erase operations induced by the garbage-collection process affect the basic performance measures throughput and latency. We demonstrate that the most straightforward scheduling that prioritizes the processing of garbage-collection-related commands over user-related commands suffers from severe latency deficiencies. These problems can be overcome by using a more sophisticated priority scheme that minimizes the user-perceived latency without throughput penalty or deadlock exposure. Using both analysis and simulation, we investigate how these schemes perform under a variety of system design parameters and workloads. Our results can be directly applied to the engineering of a performance-optimized solid-state-drive system.

This paper presents a data-placement scheme for log-structured flash translation layers (FTLs), with the dual aims of reducing write amplification due to garbage collection and flash wear-out due to block erasing and programming. The central idea is to identify and place data that is expected to change frequently together in young flash blocks that are far from wearing out, and infrequently changing data in old blocks where it can be expected to stay longer. In previous work, garbage collection and wear levelling were treated separately, and the importance of data placement was largely ignored. We propose a new scheme, called container marking, to combine data placement, garbage collection, and wear levelling in a single mechanism, thus improving both the random write performance and the endurance. Each flash block is a data container that is assigned an activeness marker indicating how frequently the data it stores is updated. A simple solution for dynamically tracking data's activeness that adapts to utilizations is presented. The system is implemented in a Java1-based flash simulator, and is shown to reduce write amplification and wear-out in synthetic and trace-driven workloads.

Two schemes proposed to cope with unrecoverable or latent media errors and enhance the reliability of RAID systems are examined. The first scheme is the established, widely used, disk scrubbing scheme, which operates by periodically accessing disk drives to detect media-related unrecoverable errors. These errors are subsequently corrected by rebuilding the sectors affected. The second scheme is the recently proposed intradisk redundancy scheme, which uses a further level of redundancy inside each disk, in addition to the RAID redundancy across multiple disks. A new model is developed to evaluate the extent to which disk scrubbing reduces the unrecoverable sector errors. The probability of encountering unrecoverable sector errors is derived analytically under very general conditions regarding the characteristics of the read/write process of uniformly distributed random workloads and for a broad spectrum of disk scrubbing schemes, which includes the deterministic and random scrubbing schemes. We show that the deterministic scrubbing scheme is the most efficient one. We also derive closed-form expressions for the percentage of unrecoverable sector errors that the scrubbing scheme detects and corrects, the throughput performance, and the minimum scrubbing period achievable under operation with random, uniformly distributed I/O requests. Our results demonstrate that the reliability improvement due to disk scrubbing depends on the scrubbing frequency and the load of the system, and, for heavy-write workloads, may not reach the reliability level achieved by a simple interleaved parity-check (IPC)-based intradisk redundancy scheme, which is insensitive to the load. In fact, for small unrecoverable sector error probabilities, the IPC-based intradisk redundancy scheme achieves essentially the same reliability as that of a system operating without unrecoverable sector errors. For heavy loads, the reliability achieved by the scrubbing scheme can be orders of magnitude less than that of the intradisk redundancy scheme. Finally, the I/O and throughput performances are evaluated by means of analysis and event-driven simulation.

Replication is a widely used method to protect large-scale data storage systems from data loss when storage nodes fail. It is well known that the placement of replicas of the different data blocks across the nodes affects the time to rebuild. Several systems described in the literature are designed based on the premise that minimizing the rebuild times maximizes the system reliability. Our results however indicate that the reliability is essentially unaffected by the replica placement scheme. We show that, for a replication factor of two, all possible placement schemes have mean times to data loss (MTTDLs) within a factor of two for practical values of the failure rate, storage capacity, and rebuild bandwidth of a storage node. The theoretical results are confirmed by means of event-driven simulation. For higher replication factors, an analytical derivation of MTTDL becomes intractable for a general placement scheme. We therefore use one of the alternate measures of reliability that have been proposed in the literature, namely, the probability of data loss during rebuild in the critical mode of the system. Whereas for a replication factor of two this measure can be directly translated into MTTDL, it is only speculative of the MTTDL behavior for higher replication factors. This measure of reliability is shown to lie within a factor of two for all possible placement schemes and any replication factor. We also show that for any replication factor, the clustered placement scheme has the lowest probability of data loss during rebuild in critical mode among all possible placement schemes, whereas the declustered placement scheme has the highest probability. Simulation results reveal however that these properties do not hold for the corresponding MTTDLs for a replication factor greater than two. This indicates that some alternate measures of reliability may not be appropriate for comparing the MTTDL of different placement schemes.

Write amplification is a critical factor limiting the random write performance and write endurance in storage devices based on NAND-flash memories such as solid-state drives (SSD). The impact of garbage collection on write amplification is influenced by the level of over-provisioning and the choice of reclaiming policy. In this paper, we present a novel probabilistic model of write amplification for log-structured flash-based SSDs. Specifically, we quantify the impact of over-provisioning on write amplification analytically and by simulation assuming workloads of uniformly-distributed random short writes. Moreover, we propose modified versions of the greedy garbage-collection reclaiming policy and compare their performance. Finally, we analytically evaluate the benefits of separating static and dynamic data in reducing write amplification, and how to address endurance with proper wear leveling.

Two schemes proposed to cope with unrecoverable or latent media errors and enhance the reliability of RAID systems are examined. The first scheme is the established, widely used disk scrubbing scheme, which operates by periodically accessing disk drives to detect media-related unrecoverable errors. These errors are subsequently corrected by rebuilding the sectors affected. The second scheme is the recently proposed intradisk redundancy scheme which uses a further level of redundancy inside each disk, in addition to the RAID redundancy across multiple disks. Analytic results are obtained assuming Poisson arrivals of random I/O requests. Our results demonstrate that the reliability improvement due to disk scrubbing depends on the scrubbing frequency and the workload of the system, and may not reach the reliability level achieved by a simple IPC-based intra-disk redundancy scheme, which is insensitive to the workload. In fact, the IPC-based intra-disk redundancy scheme achieves essentially the same reliability as that of a system operating without unrecoverable sector errors. For heavy workloads, the reliability achieved by the scrubbing scheme can be orders of magnitude less than that of the intra-disk redundancy scheme.

Today's data storage systems are increasingly adopting low-cost disk drives that have higher capacity but lower reliability, leading to more frequent rebuilds and to a higher risk of unrecoverable media errors. We propose an efficient intradisk redundancy scheme to enhance the reliability of RAID systems. This scheme introduces an additional level of redundancy inside each disk, on top of the RAID redundancy across multiple disks. The RAID parity provides protection against disk failures, whereas the proposed scheme aims to protect against media-related unrecoverable errors. In particular, we consider an intradisk redundancy architecture that is based on an interleaved parity-check coding scheme, which incurs only negligible I/O performance degradation. A comparison between this coding scheme and schemes based on traditional Reed--Solomon codes and single-parity-check codes is conducted by analytical means. A new model is developed to capture the effect of correlated unrecoverable sector errors. The probability of an unrecoverable failure associated with these schemes is derived for the new correlated model, as well as for the simpler independent error model. We also derive closed-form expressions for the mean time to data loss of RAID-5 and RAID-6 systems in the presence of unrecoverable errors and disk failures. We then combine these results to characterize the reliability of RAID systems that incorporate the intradisk redundancy scheme. Our results show that in the practical case of correlated errors, the interleaved parity-check scheme provides the same reliability as the optimum, albeit more complex, Reed--Solomon coding scheme. Finally, the I/O and throughput performances are evaluated by means of analysis and event-driven simulation.

Various log-likelihood-ratio-based belief-propagation (LLR-BP) decoding algorithms and their reduced-complexity derivatives for low-density parity-check (LDPC) codes are presented. Numerically accurate representations of the check-node update computation used in LLR-BP decoding are described. Furthermore, approximate representations of the decoding computations are shown to achieve a reduction in complexity by simplifying the check-node update, or symbol-node update, or both. In particular, two main approaches for simplified check-node updates are presented that are based on the so-called min-sum approximation coupled with either a normalization term or an additive offset term. Density evolution is used to analyze the performance of these decoding algorithms, to determine the optimum values of the key parameters, and to evaluate finite quantization effects. Simulation results show that these reduced-complexity decoding algorithms for LDPC codes achieve a performance very close to that of the BP algorithm. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate scheme from performance, latency, computational-complexity, and memory-requirement perspectives.

We propose a general method for constructing Tanner graphs having a large girth by establishing edges or connections between symbol and check nodes in an edge-by-edge manner, called progressive edge-growth (PEG) algorithm. Lower bounds on the girth of PEG Tanner graphs and on the minimum distance of the resulting low-density parity-check (LDPC) codes are derived in terms of parameters of the graphs. Simple variations of the PEG algorithm can also be applied to generate linear-time encodeable LDPC codes. Regular and irregular LDPC codes using PEG Tanner graphs and allowing symbol nodes to take values over GF(q) (q>2) are investigated. Simulation results show that the PEG algorithm is a powerful algorithm to generate good short-block-length LDPC codes.

We derive the average symbol and Hamming weight spectrum functions of the random ensemble of regular low-density parity-check (LDPC) codes over GF(2/sup b/) when used with the binary-input noisy channel. This work confirms theoretically that the near-Shannon-limit performance of Gallager's binary LDPC codes can be significantly enhanced by moving to fields of higher order. We construct a family of error-correcting codes based on the binary representation of GF(2/sup b/) codes defined on a cycle Tanner graph that appears to be "good" for both optimum and iterative decoding over the binary-input noisy channel. In particular, we report a short-block-length (1008 bits), rate-1/2 progressive-edge-growth-based cycle Tanner-graph code over GF(2/sup b/) with a block-error rate <10/sup -4/ at E/sub b//N/sub 0/=1.89 dB, which appears to exhibit the best iterative-decoding performance at this short block length known to date.

Low-density parity-check (LDPC) codes in their broader-sense definition are linear codes whose parity-check matrices have fewer 1s than 0s. Finding their minimum distance is therefore in general an NP-hard problem. We propose a randomized algorithm called nearest nonzero codeword search (NNCS) approach to tackle this problem for iteratively decodable LDPC codes. The principle of the NNCS approach is to search codewords locally around the all-zero codeword perturbed by minimal noise, anticipating that the resultant nearest nonzero codewords will most likely contain the minimum-Hamming- weight codeword whose Hamming weight is equal to the minimum distance of the linear code. This approach has its roots in Berrou et al.'s error-impulse method and a form of Fossorier's list decoding for LDPC codes.

We propose a family of randomized approximate algorithms, called nearest nonzero codewords search (NNCS), for computing the minimum distance of low-density parity-check (LDPC) codes, including Gallager-type and finite-geometry-type codes.

We propose a general method for constructing Tanner (1981) graphs with large girth by progressively establishing edges or connections between symbol and check nodes in an edge-by-edge manner, called progressive edge-growth (PEG) construction. Lower bounds on the girth and on the minimum distance of the resulting low-density parity-check (LDPC) codes are derived in terms or parameters of the graphs. Encoding of LDPC codes based on the PEG principle is also investigated. We show how to exploit the PEG graph construction to obtain LDPC codes that allow linear time encoding. The advantages of PEG Tanner graphs over randomly constructed graphs are demonstrated by extensive simulation results on code performance.

Efficient implementations of the sum-product algorithm (SPA) are presented for decoding low-density parity-check (LDPC) codes using log-likelihood ratios (LLR) as messages between symbol and parity-check nodes. Various reduced-complexity derivatives of the LLR-SPA are proposed. Both serial and parallel implementations are investigated, leading to trellis and tree topologies, respectively. Furthermore, by exploiting the inherent robustness of LLRs, it is shown, via simulations, that coarse quantization tables are sufficient to implement complex core operations with negligible or no loss in performance. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate design point in high-speed applications from a performance, latency and computational complexity perspective.