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), at least a subset of the data elements are assigned only to corresponding unique combinations of parity elements of size (d−1), where d>2 and k>m.
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), where d>1 and k>1,
- wherein, if data elements remain after all unique combinations of parity elements of size (d−1) are assigned, the remaining data elements are assigned to only corresponding unique combinations of parity elements of an iteratively stepped size.
An article comprising a tangible computer-accessible storage medium containing instructions 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(d−1), assign the data elements only to corresponding unique combinations of parity elements of size (d−1) until no unique combinations of parity elements of size (d−1) remain, where d>2 and k≧m.
An article comprising a tangible computer-accessible storage medium containing instructions 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;
- 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 parity elements of size (d−1) remain, where d>1 and k>1;
- and
- wherein, if unassigned data elements remain,
- iteratively increase the size of unique combinations of parity elements, and
- assign the remaining unassigned data elements to corresponding unique combinations of parity elements of increased size.
A method of constructing an erasure code for a storage system having a fault tolerance (d−1), a number of data storage devices k, and a number of parity storage devices m, where d>1, k>1, and m≧(d−1), 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);
- storing the data elements and the parity elements across the data storage devices and the parity storage devices in accordance with the assignment;
- determining if unassigned data elements remain;
- if so, determining unique combinations of parity elements of a stepped up size;
- and
- assigning the remaining unassigned data elements to corresponding unique combinations of the stepped up size.
Dependencies are inferred from the claim text.