Non-mds erasure codes for storage systems
AssigneeHewlett-Packard Development Company, L. P.
InventorsJohn Johnson Wylie, Xiaozhou Li
Life of this patent
Estimating the term…
Abstract
Erasure-encoded data is stored across a plurality of storage devices in a data storage system. The erasure-encoded data includes k data elements to store on k data storage devices and m parity elements to store on m parity storage devices, wherein for a given minimum Hamming distance d of the data storage system and m≧(d−1), data elements are assigned only to corresponding unique combinations of parity elements of size (d−1).
Claims19
A data storage system, comprising:
- an interconnect;
- and
- a plurality of storage devices coupled by the interconnect, the storage devices including data storage devices and parity storage devices to store erasure-encoded data, the erasure-encoded data including k data elements to store on k data storage devices and m parity elements to store on m parity storage devices, wherein for a given minimum Hamming Distance d of the data storage system and m≧(d−1), data elements are assigned only to corresponding unique combinations of parity elements of size (d−1).
An article comprising a tangible computer-accessible storage medium containing instructions of software code that, when executed by a computer processing device, cause the computer processing device to:
- encode data into a plurality of erasure-encoded elements for storage across a plurality of storage devices in a storage system, the erasure-encoded elements comprising k data elements and m parity elements;
- and
- for a given fault tolerance (d−1) for the storage system, and where m≧(d−1), assign a data element only to a corresponding unique combination of parity elements of size (d−1) until no unique combinations of size (d−1) parity elements remain.
A method of constructing an erasure code for a storage system having a desired fault tolerance (d−1), a number of data storage devices k, and a number of parity storage devices m, the method comprising:
- receiving data for storage in the storage system;
- encoding the data into a plurality of k erasure-encoded data elements for storage across the k data storage devices and m erasure-encoded parity elements for storage across the m parity storage devices;
- determining unique combinations of parity elements of size (d−1);
- assigning data elements only to corresponding unique combinations of parity elements of size (d−1);
- and
- storing the data elements and the parity elements across the data storage devices and the parity storage devices in accordance with the assignment.
Dependencies are inferred from the claim text.