Method for lock-free clustered erasure coding and recovery of data across a plurality of data stores in a network
View Patent ↗The present invention provides a distributed clustering method to allow multiple active instances of consistency management processes that apply the same encoding scheme to be cooperative and function collectively. The techniques described herein facilitate an efficient method to apply an erasure encoding and decoding scheme across dispersed data stores that receive constant updates. The technique can be applied on many forms of distributed persistent data stores to provide failure resiliency and to maintain data consistency and correctness.
1. An erasure encoding method comprising:
(a) providing a plurality of computer systems forming a distributed computer network, each computer system of the plurality of computer systems having a management process operating thereon, thereby forming a plurality of management processes;
(b) providing a plurality of distributed persistent memories, each persistent memory of the plurality of distributed persistent memories interoperably coupled to at least one of the plurality of computer systems and operative to receive constant updates;
(c) distributing, via an erasure encoding process, a plurality of data sets, wherein each data set of the plurality of data sets comprises at least one data block and at least one checksum block, across a plurality of the plurality of distributed persistent memories;
(d) initializing the plurality of management processes into and operating as a cluster, wherein during the initializing of the cluster, each management process:
agreeing to enter into an initialization mode;
entering into the initialization mode;
suspending regular runtime processing; and
registering data-set management-process management responsibility;
(e) performing a consistency check by the cluster of the plurality of data sets; and
(f) managing the plurality of data sets, comprising:
communicating by each management process to other management processes of the plurality of management processes to determine a responsible management process of each data set of the plurality of data sets, each data set managed by one of the management processes; and
determining by the responsible management process, via a sequencing indicator, whether each data block and each checksum block of each data set of the plurality of data sets is modified completely.
2. The method of claim 1 , wherein steps (a)-(f) are performed in order as listed.
3. The method of claim 1 , wherein the plurality of management processes share the same plurality of distributed persistent memories.
4. The method of claim 1 , further comprising reinitializing the plurality of management processes responsive to at least one of:
adding a new management process to the cluster; and
removing a management process from the cluster.
5. The method of claim 1 , further comprising communicating status information by each management process to other management processes of the plurality of management processes.
6. The method of claim 1 , wherein the sequencing indicator is a sequence number entered into a header and a trailer of the at least one data block and the at least one checksum block of each data set.
7. The method of claim 1 , wherein the sequencing indicator is a sequence number entered into a register.
8. The method of claim 1 , wherein the sequencing indicator is a flag.
9. The method of claim 1 , wherein distributing comprises:
distributing at least a portion of the plurality of data sets across a combination of at least one data row and at least one data column; and
wherein the at least one data row and the at least one data column each comprise at least one persistent memory of the plurality of distributed persistent memories.
10. The method of claim 9 , wherein each data row and each data column is individually encoded using the sequencing indicator.
11. The method of claim 1 , further comprising performing an automatic self-recovery, performing the automatic self-recovery comprising:
identifying the plurality of the plurality of distributed memories associated with each data set of the plurality of data sets;
classifying whether the at least one data block and the at least one checksum block of each data set of the plurality of data sets are good;
verifying if there are enough good blocks to recover each data set of the plurality of data sets;
performing a consistency check of the good blocks; and
recovering each data set of the plurality of data sets using the good blocks.
12. The method of claim 1 , wherein at least one failure is a failure of at least one of the plurality of distributed persistent memories.
13. The method of claim 1 , wherein the data-set management-process management responsibility is determined using a common responsibility distribution algorithm.
14. The method of claim 1 , wherein the consistency check comprises:
communicating by each management process with other management processes of the plurality of management processes to determine a responsible consistency-check management process of each data set of the plurality of data sets;
performing by the responsible consistency check management process the consistency check;
communicating by each management process with the other management processes to confirm a completion of the consistency check; and
entering the cluster into an active mode.
15. The method of claim 1 , wherein step (f) further comprises enabling automatic self-recovery of each data set of the plurality of data sets to a consistent and correct state.
16. A computer-program product comprising a non-transitory computer-usable medium having computer-readable program code embodied therein, the computer-readable program code executed to implement an erasure encoding method comprising:
(a) providing a plurality of computer systems forming a distributed computer network, each computer system of the plurality of computer systems having a management process operating thereon, thereby forming a plurality of management processes;
(b) providing a plurality of distributed persistent memories, each persistent memory of the plurality of distributed persistent memories interoperably coupled to at least one of the plurality of computer systems and operative to receive constant updates;
(c) distributing, via an erasure encoding process, plurality of data sets, wherein each data set of the plurality of data sets comprises at least one data block and at least one checksum block, across a plurality of the plurality of distributed persistent memories;
(d) initializing the plurality of management processes into and operating as a cluster;
(e) performing a consistency check by the cluster of the plurality of data sets, wherein performing the consistency check comprises:
communicating by each management process with other management processes of the plurality of management processes to determine a responsible consistency-check management process of each data set of the plurality of data sets;
performing by the responsible consistency check management process the consistency check;
communicating by each management process with the other management processes to confirm a completion of the consistency check; and
entering the cluster into an active mode; and
(f) managing, the plurality of data sets, comprising:
communicating by each management process to the other management processes of the plurality of management processes to determine a responsible management process of each data set of the plurality of data sets, each data set managed by one of the management process; and
determining by the responsible management process, via a sequencing indicator, whether each data block and each checksum block of each data set of the plurality of data sets is modified completely.
17. The computer-program product of claim 16 , wherein steps (a)-(f) are performed in order as listed.
18. The computer-program product of claim 16 , wherein the plurality of management processes share the same plurality of distributed persistent memories.
19. The computer-program product of claim 16 , wherein the erasure encoding method further comprises reinitializing the plurality of management processes responsive to at least one of:
adding a new management process to the cluster; and
removing a management process from the cluster.
20. The computer-program product of claim 16 , wherein each management process communicates status information to the other management processes of the plurality of management processes.
21. The computer-program product of claim 16 , wherein the sequencing indicator is a sequence number entered into a header and a trailer of the at least one data block and the at least one checksum block of each data set.
22. The computer-program product of claim 16 , wherein the sequencing indicator is a sequence number entered into a register.
23. The computer-program product of claim 16 , wherein the sequencing indicator is a flag.
24. The computer-program product of claim 16 , wherein, during the initialization of the cluster, each management process:
agreeing to enter into an initialization mode;
entering into the initialization mode;
suspending regular runtime processing; and
registering data-set management-process management responsibility.
25. The computer-program product of claim 24 , wherein the data-set management- process management responsibility is determined using a common responsibility distribution algorithm.
26. The computer-program product of claim 16 , the wherein distributing comprises:
distributing at least a portion of the plurality of data sets across a combination of at least one data row and at least one data column; and
wherein the at least one data row and the at least one data column each comprise at least one persistent memory of the plurality of distributed persistent memories.
27. The computer-program product of claim 26 , wherein each data row and each data column is individually encoded using the sequencing indicator.
28. The computer-program product of claim 16 , wherein the erasure encoding method further comprises performing an automatic self-recovery, performing the automatic self-recovery comprising:
identifying the plurality of the plurality of distributed memories associated with each data set of the plurality of data sets;
classifying whether the at least one data block and the at least one checksum block of each data set of the plurality of data sets are good;
verifying if there are enough good blocks to recover each data set of the plurality of data sets;
performing a consistency check of the good blocks; and
recovering each data set of the plurality of data sets using the good blocks.
29. The computer-program product of claim 16 , wherein at least one failure is a failure of at least one of the plurality of distributed persistent memories.
30. The computer-program product of claim 16 , wherein step (f) further comprises enabling automatic self-recovery of each data set of the plurality of data sets to a consistent and correct state.