Method for lock-free clustered erasure coding and recovery of data across a plurality of data stores in a network

• US 8,051,361 B2
• Filed: 01/28/2010
• Issued: 11/01/2011
• Est. Priority Date: 08/09/2004
• Status: Active Grant

• Current Assignee: Quest Software, Inc.
• Original Assignee: Quest Software, Inc.
• Inventors: Ustimenko, Semen Alexandrovich, Sim-Tang, Siew Yong
• Primary Examiner(s): Torres; Joseph D
• Application Number:
  US12/695,407
• Publication Number:
  US 20100162076A1
• Time in Patent Office: 642 Days
• Field of Search: 714/769, 714/780
• US Class Current: 714/769
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/108 Parity data distribution in semiconductor storages, e.g. in SSD
• CPC Class Codes: G06F 11/1088 Reconstruction on already foreseen single or plurality of spare disks
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/2909 Product codes
• CPC Class Codes: H03M 13/293 with erasure setting
• CPC Class Codes: H03M 13/3776 using a re-encoding step during the decoding process

Abstract

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.

Claims

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.