main.pdf (375.6 kB)
0/0

Computing the probability for data loss in two-dimensional parity RAIDs

Download (375.6 kB)
conference contribution
posted on 06.02.2018 by Lars Nagel, Tim Suss
Parity RAIDs are used to protect storage systems against disk failures. The idea is to add redundancy to the system by storing the parity of subsets of disks on extra parity disks. A simple two-dimensional scheme is the one in which the data disks are arranged in a rectangular grid, and every row and column is extended by one disk which stores the parity of it. In this paper we describe several two-dimensional parity RAIDs and analyse, for each of them, the probability for data loss given that f random disks fail. This probability can be used to determine the overall probability using the model of Hafner and Rao. We reduce subsets of the forest counting problem to the different cases and show that the generalised problem is #Phard. Further we adapt an exact algorithm by Stones for some of the problems whose worst-case runtime is exponential, but which is very efficient for small fixed f and thus sufficient for all real-world applications.

Funding

This work was partly developed in the ADA-FS project funded by the DFG Priority Program “Software for Exascale Computing” (SPPEXA, SPP 1648).

History

School

  • Science

Department

  • Computer Science

Published in

13th European Dependable Computing Conference (EDCC) 2017 13TH EUROPEAN DEPENDABLE COMPUTING CONFERENCE (EDCC 2017)

Pages

58 - 65

Citation

NAGEL, L. and SUSS, T., 2017. Computing the probability for data loss in two-dimensional parity RAIDs. Presented at the 2017 13th European Dependable Computing Conference (EDCC 2017), Geneva, Switzerland, 4-8 Sept , pp. 58-65.

Publisher

© Institute of Electrical and Electronics Engineers (IEEE)

Version

AM (Accepted Manuscript)

Publication date

2017

Notes

© 2017 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.

ISBN

9781538606025

Language

en

Location

Geneva, Switzerland

Exports

Logo branding

Exports