Self-Adjusting Two-Failure Tolerant Disk Arrays

Introduction

While flash and Storage Class Memory (SCM) technologies stand to replace magnetic disk technology as the mainstay for high end applications, the sheer amount of data to be stored, the attractive cost-to-capacity ratios of disks, and the high streaming throughput in comparison with not only tape but also with high-end flash and SCM, give magnetic disk technology a continuing and important role in the storage hierarchy. This is true whether disks are relegated to tertiary storage roles or remain as the secondary storage technology behind flash/SCM-based caches. A practical disk-based storage system at petabyte scale is both dynamic and heterogeneous, as the number of devices it would require means that new disks with better performance, reliability, and capacity will continuously enter the system as old disks leave due to failure, age, or technical obsolescence.

Data stored in a peta-scale system needs to be protected, but its size will make disk failure a daily occurence. Observed data on the life expectancy of disks and the occurrence of latent disk sector errors suggest that tolerance of at least two failures is necessary, possibly in conjunction with disk scrubbing or intra-disk redundancy.

While replication offers operational advantages, the storage overhead with its associated costs in hardware and energy is too large. Many two-failure resilient systems have been proposed in the past. We propose an old, simple scheme in which every piece of client data is part of two different reliability stripes encompassing data disks and one additional parity each. Managing this simple layout over the lifetime of an evolving system is difficult. Our contribution is a graph-based representation that transforms layout decisions into the construction of (almost) regular graphs and coloring their edges and vertices with many colors. For this, we can use simple, greedy and heuristic graph algorithms.