System and method for recovery of unrecoverable data with enhanced erasure coding and replication

• US 10,642,688 B2
• Filed: 04/12/2018
• Issued: 05/05/2020
• Est. Priority Date: 04/12/2018
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Danilov, Mikhail, Buinov, Konstantin
• Primary Examiner(s): McMahon, Daniel F.
• Application Number:
  US15/952,176
• Publication Number:
  US 20190317858A1
• Time in Patent Office: 754 Days
• Field of Search: None
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H03M 13/154 Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial
• CPC Class Codes: H03M 13/373 with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes
• CPC Class Codes: H03M 13/616 Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations

Abstract

In geographically-distributed object storage systems that utilize erasure coding, non-intersecting sub matrices of a great encoding matrix can be utilized to erasure code data fragments of a chunk at the zone level and generate coding fragments. Accordingly, the data fragments that are stored within different zones are identical, while the coding fragments stored within the different zones are disparate. Subsequent to a multi-zone data failure, wherein it is determined that a decoding operation cannot be performed at the zone level, available fragments associated with the chunk can be collected from the zones and collectively decoded to recover the chunk. In one aspect, the fragments can be decoded by utilizing a great decoding matrix that corresponds to the great encoding matrix.

Claims

1. A system, comprising:

a processor; and

a memory that stores executable instructions that, when executed by the processor, facilitate performance of operations, comprising;

determining a coding matrix that is to be employed to erasure code a chunk stored within a distributed storage system;

determining non-intersecting sub matrices of the coding matrix; and

encoding data fragments of the chunk by utilizing the non-intersecting sub matrices, wherein the encoding results in a generation of different coding fragments that are to be stored within respective zones of the distributed storage system.

2. The system of claim 1, wherein the operations further comprise:

in response to determining that a failure condition is satisfied, collecting available fragments from the respective zones.

3. The system of claim 2, wherein the operations further comprise:

decoding the available fragments based on a decoding matrix that corresponds to the coding matrix, and wherein the decoding results in a recovery of the data fragments.

4. The system of claim 3, wherein the operations further comprise:

subsequent to the decoding, re-encoding the data fragments based on the non-intersecting sub matrices.

5. The system of claim 2, wherein the determining that the failure condition is satisfied comprises determining that the data fragments are unable to be recovered at a zone level without inter-zone communication.

6. The system of claim 1, wherein the determining the coding matrix comprises determining the coding matrix based on a number of zones within the distributed storage system.

7. The system of claim 1, wherein the determining the coding matrix comprises determining the coding matrix based on an erasure coding protection protocol utilized at a zone level.

8. The system of claim 1, wherein the operations further comprise:

facilitating a storage of copies of the data fragments within the respective zones.

9. The system of claim 1, wherein the determining the non-intersecting sub matrices comprises splitting the coding matrix based on a number of the respective zones to which the chunk is to be replicated.

10. The system of claim 1, wherein the distributed storage system comprises a distributed object storage system.

11. A method, comprising:

configuring, by a system comprising a processor, a coding matrix that is to be employed during an erasure coding of a chunk stored within a distributed storage system;

determining first coding fragments based on encoding data fragments of the chunk in accordance with a first sub matrix of the coding matrix, wherein the first coding fragments are to be stored within a first zone of the distributed storage system; and

determining second coding fragments based on encoding the data fragments in accordance with a second sub matrix of the coding matrix, wherein the first sub matrix and the second sub matrix are non-intersecting matrices, and wherein the second coding fragments are to be stored within a second zone of the distributed storage system.

12. The method of claim 11, further comprising:

facilitating a storage of a first copy of data fragments within the first zone and a second copy of data fragments within the second zone.

13. The method of claim 12, further comprising:

determining that a multi-zone failure has occurred resulting in a loss of information stored within the first zone and the second zone; and

in response to determining that the multi-zone failure satisfies a defined failure criterion, facilitating a transfer of available fragments from the second zone to the first zone.

14. The method of claim 13, further comprising:

decoding the available fragments based on a decoding matrix that corresponds to the coding matrix, wherein the decoding results in a recovery of the data fragments.

15. The method of claim 11, wherein the configuring comprises configuring a size of the coding matrix based on a number of zones within the distributed storage system.

16. The method of claim 11, wherein the configuring comprises configuring a size of the coding matrix based on an erasure coding protection scheme utilized for data protection at a zone level.

17. A non-transitory computer-readable storage medium comprising instructions that, in response to execution, cause a server device comprising a processor to perform operations, comprising:

configuring a coding matrix that is to be employed to erasure code a chunk stored within a distributed storage system;

encoding data fragments of the chunk in accordance with a first sub matrix of the coding matrix to generate first coding fragments that are to be stored within a first zone of the distributed storage system; and

encoding the data fragments in accordance with a second sub matrix of the coding matrix to generate second coding fragments that are to be stored within a second zone of the distributed storage system, wherein the first sub matrix and the second sub matrix are non-intersecting matrices.

18. The non-transitory computer-readable storage medium of claim 17, wherein the operations further comprise:

storing a first copy of the data fragments with the first coding fragments within the first zone; and

storing a second copy of the data fragments with the second coding fragments within the second zone.

19. The non-transitory computer-readable storage medium of claim 18, wherein fragments comprise the first copy of the data fragments, the second copy of the data fragments, the first coding fragments and the second coding fragments, and wherein the operations further comprise:

in response to determining that at least a portion of the fragments is unavailable, decoding a remaining portion of the fragments other than the at least the portion that is unavailable in accordance with a decoding matrix that corresponds to the coding matrix to recover the data fragments.

20. The non-transitory computer-readable storage medium of claim 17, wherein the distributed storage system comprises a distributed object storage system.