System and method for recovery of unrecoverable data with erasure coding and geo XOR

Patent metadata

Field	Value
Publication number	US-10289488-B1
Application number	US-201715498859-A
Country	US
Kind code	B1
Filing date	Apr 27, 2017
Priority date	Apr 27, 2017
Publication date	May 14, 2019
Grant date	May 14, 2019

Abstract

The disclosure relates data protection management (e.g. data recovery) for distributed storage systems. Specifically, the systems (and methods) of the disclosure provide an advanced mechanism for data recovery based on a notion of a data fragment's peer group, which may be used for “peer” recovery. Peer recovery allows a data fragment to be recovered when all the data fragments from its peer group are available. Accordingly, the described mechanism leverages the power of erasure coding and XOR operations to support recovery of data in situations where such data would previously be considered unrecoverable.

First claim

What is claimed is:

1. A non-transitory machine-readable medium storing instructions which, when executed by one or more processors of a computing device, cause the computing device to perform operations comprising:
determining a loss of fragments within a set of erasure coded data chunks stored within a data storage system, wherein the set of data chunks includes at least a first and second user data chunk, and a redundant data chunk, wherein the fragments of each of the data chunks includes an indexed sequence of k data fragments and m coding fragments, wherein the redundant chunk is formed as a result of performing an XOR operation from the fragments of the first and second user data chunks; and
recovering one or more of the lost fragments within the set of data chunks, including
performing a first recovery of at least a first lost fragment having a first index position within the sequence of fragments of the first user data chunk, wherein the first recovery includes performing an XOR operation from a data fragment at the first index position from each of the second user data chunk and the redundant chunk,
performing a second recovery of at least a second lost fragment having a second index position within the sequence of fragments of the first user data chunk,
performing a third recovery of at least a third lost fragment having the second index position within the sequence of fragments of the second user data chunk,
performing a re-encoding of one or more of the coding fragments of the second user data chunk in response to performing the recovery of at least the third lost fragment within the second user data chunk.

2. The medium of claim 1 , wherein the first recovery is performed in response to the first user data chunk having more than m lost data fragments.

3. The medium of claim 1 , wherein the second recovery includes performing an operation using at least the recovered first lost fragment and one or more other fragments within the first user data chunk.

4. The medium of claim 3 , wherein the second recovery is performed in response to the first user data chunk having no more than m lost data fragments after performing the first recovery.

5. The medium of claim 1 , wherein the third recovery includes performing an operation using at least the recovered second lost fragment of the first user data chunk, and a data fragment at the second index position within the redundant chunk.

6. The medium of claim 5 , wherein the third recovery is performed in response to performing the recovery of the second lost fragment, and wherein the second user data chunk has more than m lost data fragments before performing the third recovery, and no more than m lost data fragments after performing the third recovery.

7. A method of recovering data with a data storage system, comprising:
determining a loss of fragments within a set of erasure coded data chunks stored within a data storage system, wherein the set of data chunks includes at least a first and second user data chunk, and a redundant data chunk, wherein the fragments of each of the data chunks includes an indexed sequence of k data fragments and m coding fragments;
recovering one or more of the lost fragments within the set of data chunks, including
performing a first recovery of at least a first lost fragment having a first index position within the sequence of fragments of the first user data chunk, wherein the first recovery includes performing an operation from a data fragment at the first index position from each of the second user chunk and the redundant chunk,
performing a second recovery of at least a second lost fragment having a second index position within the sequence of fragments of the first user data chunk, wherein the second recovery includes performing an operation using at least the recovered first lost fragment and one or more other fragments within the first user data chunk, and
performing a third recovery of at least a third lost fragment having the second index position within the sequence of fragments of the second user data chunk, wherein the third recovery includes performing an operation using at least the recovered second lost fragment of the first user data chunk, and a data fragment at the second index position within the redundant chunk,
performing a re-encoding of one or more of the coding fragments of the second user data chunk in response to performing the recovery of at least the third lost fragment within the second user data chunk.

8. The method of claim 7 , wherein the redundant chunk is formed as a result of performing an XOR operation from the fragments of the first and second user data chunks.

9. The method of claim 7 , wherein the operations performed in the first, second, and third recovery include an XOR operation.

10. The method of claim 7 , wherein the first recovery is performed in response to the first user data chunk having more than m lost data fragments, and wherein the second recovery is performed in response to the first user data chunk having no more than m lost data fragments after performing the first recovery.

11. The method of claim 7 , wherein the third recovery is performed in response to performing the recovery of the second lost fragment, and wherein the second user data chunk has more than m lost data fragments before performing the third recovery, and no more than m lost data fragments after performing the third recovery.

12. A data storage system, comprising:
a memory storing instructions; and
one or more processors coupled to the memory to execute the instructions from the memory, the one or more processors being configured to perform operations, the operations comprising:
determining a loss of fragments within a set of erasure coded data chunks stored within the data storage system, wherein the set of data chunks includes at least a first and second user data chunk, and a redundant data chunk, wherein the fragments of each of the data chunks includes an indexed sequence of k data fragments and m coding fragments; and
recovering one or more of the lost fragments within the set of data chunks, including
performing a first recovery of at least a first lost fragment having a first index position within the sequence of fragments of the first user data chunk, wherein the first recovery includes performing an XOR operation from a data fragment at the first index position from each of the second user data chunk and the redundant chunk,
performing a second recovery of at least a second lost fragment having a second index position within the sequence of fragments of the first user data chunk,
performing a third recovery of at least a third lost fragment having the second index position within the sequence of fragments of the second user data chunk,
performing a re-encoding of one or more of the coding fragments of the second user data chunk in response to performing the recovery of at least the third lost fragment within the second user data chunk.

13. The system of claim 12 , wherein the second recovery includes performing an operation using at least the recovered first lost fragment and one or more other fragments within the first user data chunk.

14. The system of claim 13 , wherein the first recovery is performed in response to the first user data chunk having more than m lost data fragments, and wherein the second recovery is performed in response to the first user data chunk having no more than m lost data fragments after performing the first recovery.

15. The system of claim 12 , wherein the third recovery includes performing an operation using at least the recovered second lost fragment of t

Assignees

• Emc Ip Holding Co Llc

Inventors

• Danilov Mikhail
• Buinov Konstantin
• Rakulenko Alexander
• Skripko Gregory
• Zakharov Kirill

Classifications

• G06F11/1076 Primary

  Parity data used in redundant arrays of independent storages, e.g. in RAID systems · CPC title

• H04L67/1097

  for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS] · CPC title

• H04L69/40

  for recovering from a failure of a protocol instance or entity, e.g. service redundancy protocols, protocol state redundancy or protocol service redirection (management of faults, events, alarms or notifications in data switching networks H04L41/06) · CPC title

• G11C29/00

  Checking stores for correct operation {; Subsequent repair}; Testing stores during standby or offline operation · CPC title

• H03M13/154

  Error and erasure correction, e.g. by using the error and erasure locator or Forney polynomial · CPC title