System and method for data re-protection with erasure coding
View Patent ↗The disclosure relates data protection management (e.g. data re-protection) for distributed storage systems. Specifically, the systems (and methods) of the disclosure implement erasure coding to protect replicated data efficiently while reducing the storage capacity overhead. Traditional approaches for data re-protection that implement erasure coding often require performing a complete re-encoding to reflect changes in data (e.g. a removal of data). The disclosure provides an improved mechanism for data re-protection by implementing an efficient re-encoding (or un-encoding) process that reduces the requirements for data reads and operations, and thus, reduces the resource requirements for data re-protection.
1. A computer-implemented method to provide data re-protection, comprising:
encoding data using an erasure coding technique, wherein the encoding includes dividing the data into k data fragments (D), and
creating, from the data fragments, m redundant coding fragments (C) using a coding matrix, wherein the redundant coding fragments allow for recovery of one or more of the data fragments;
storing the data fragments and redundant coding fragments across a set of storage nodes of a distributed data storage system;
identifying a data fragment for removal from the set of storage nodes; and
performing a re-encoding to reflect the removal of the identified data fragment, wherein the re-encoding includes for each of the redundant coding fragments,
performing a calculation to obtain an updated coding fragment (C′), wherein the calculation is based on an operation performed using at least a portion of the coding matrix and the identified data fragment.
2. The method of claim 1 , wherein re-encoding the one or more of the redundant coding fragments includes accessing at most m+1 fragments, wherein m is the number of coding fragments used for encoding the data.
3. The method of claim 1 , wherein for each of the redundant coding fragments, the calculation to obtain the updated coding fragment is based on an operation performed using a coefficient (X) of the coding matrix and the identified data fragment, wherein the coefficient corresponds to the identified data fragment to be removed.
4. The method of claim 1 , wherein for each of the redundant coding fragments, the calculation to obtain the updated coding fragment is a formula comprising:
C′ i =C i −X i,j *D j , wherein X i,j is a coefficient of the coding matrix, C i is an index of the redundant coding fragment to be updated, and D j is an index of the identified data fragment to be removed.
5. The method of claim 1 , creating m redundant coding fragments includes creating a matrix-vector product from a vector including the k data fragments and a distribution matrix of (k+m)×k size, wherein the first k rows of the distribution matrix compile a k×k identity matrix and the bottom m rows of the distribution matrix form the coding matrix.
6. The method of claim 1 , further comprising reclaiming a storage capacity of the identified data fragment by performing the removal the data fragment from the distributed data storage system.
7. The method of claim 1 , wherein the data fragment to be removed is identified based on a garbage collection process.
8. 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:
encoding data using an erasure coding technique, wherein the encoding includes
dividing the data into k data fragments (D), and
creating, from the data fragments, m redundant coding fragments (C) using a coding matrix, wherein the redundant coding fragments allow for recovery of one or more of the data fragments;
storing the data fragments and redundant coding fragments across a set of storage nodes of a distributed data storage system;
identifying a data fragment for removal from the set of storage nodes; and
performing a re-encoding to reflect the removal of the identified data fragment, wherein
the re-encoding includes for each of the redundant coding fragments,
performing a calculation to obtain an updated coding fragment (C′), wherein the calculation is based on an operation performed using at least a portion of the coding matrix and the identified data fragment.
9. The system of claim 8 , wherein re-encoding the one or more of the redundant coding fragments includes accessing at most m+1 fragments, wherein m is the number of coding fragments used for encoding the data.
10. The system of claim 8 , wherein for each of the redundant coding fragments, the calculation to obtain the updated coding fragment is based on an operation performed using a coefficient (X) of the coding matrix and the identified data fragment, wherein the coefficient corresponds to the identified data fragment to be removed.
11. The system of claim 8 , wherein for each of the redundant coding fragments, the calculation to obtain the updated coding fragment is a formula comprising:
C′ i =C i −X i,j *D j , wherein X i,j is a coefficient of the coding matrix, C i is an index of the redundant coding fragment to be updated, and D j is an index of the identified data fragment to be removed.
12. The system of claim 8 , creating m redundant coding fragments includes creating a matrix-vector product from a vector including the k data fragments and a distribution matrix of (k+m)×k size, wherein the first k rows of the distribution matrix compile a k×k identity matrix and the bottom m rows of the distribution matrix form the coding matrix.
13. The system of claim 8 , further comprising reclaiming a storage capacity of the identified data fragment by performing the removal the data fragment from the distributed data storage system.
14. The method of claim 1 , wherein the data fragment to be removed is identified based on a garbage collection process.
15. A non-transitory computer-readable storage medium having instructions stored therein, which when executed by a processor, cause the processor to perform operations in a data storage system, the operations comprising:
encoding data using an erasure coding technique, wherein the encoding includes
dividing the data into k data fragments (D), and
creating, from the data fragments, m redundant coding fragments (C) using a coding matrix, wherein the redundant coding fragments allow for recovery of one or more of the data fragments;
storing the data fragments and redundant coding fragments across a set of storage nodes of a distributed data storage system;
identifying a data fragment for removal from the set of storage nodes; and
performing a re-encoding to reflect the removal of the identified data fragment, wherein
the re-encoding includes for each of the redundant coding fragments,
performing a calculation to obtain an updated coding fragment (C′), wherein the calculation is based on an operation performed using at least a portion of the coding matrix and the identified data fragment.
16. The medium of claim 15 , wherein re-encoding the one or more of the redundant coding fragments includes accessing at most m+1 fragments, wherein m is the number of coding fragments used for encoding the data.
17. The medium of claim 15 , wherein for each of the redundant coding fragments, the calculation to obtain the updated coding fragment is based on an operation performed using a coefficient (X) of the coding matrix and the identified data fragment, wherein the coefficient corresponds to the identified data fragment to be removed.
18. The medium of claim 15 , wherein for each of the redundant coding fragments, the calculation to obtain the updated coding fragment is a formula comprising:
C′ i =C i −X i,j *D j , wherein X i,j is a coefficient of the coding matrix, C i is an index of the redundant coding fragment to be updated, and D j is an index of the identified data fragment to be removed.
19. The medium of claim 15 , creating m redundant coding fragments includes creating a matrix-vector product from a vector including the k data fragments and a distribution matrix of (k+m)×k size, wherein the first k rows of the distribution matrix compile a k×k identity matrix and the bottom m rows of the distribution matrix form the coding matrix.
20. The medium of claim 15 , further comprising reclaiming a storage capacity of the identified data fragment by performing the removal the data fragment from the distributed data storage system.