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

• US 8,205,139 B1
• Filed: 09/22/2011
• Issued: 06/19/2012
• Est. Priority Date: 08/09/2004
• Status: Expired due to Fees

• Current Assignee: Quest Software, Inc.
• Original Assignee: Quest Software, Inc.
• Inventors: Sim-Tang, Siew Yong, Ustimenko, Semen Alexandrovich
• Primary Examiner(s): Torres, Joseph D
• Application Number:
  US13/241,004
• Time in Patent Office: 271 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. A system for erasure encoding comprising:

a plurality of computer systems including at least one computer processor forming a distributed computer network, each computer system having a management process operating thereon;

a plurality of distributed persistent memories, each persistent memory interoperably coupled to at least one of the computer systems and operative to receive constant updates, wherein a plurality of data sets are distributed across the distributed persistent memories, each data set including at least one data block and at least one check sum block; and

computer-readable storage storing the management processes, each management process comprising computer-readable instructions, that when executed by the computer processor, cause the computer processor to perform operations defined by the computer-executable instructions, the computer-executable instructions configured to;

initialize the management processes to operate as a cluster;

communicate by each management process with other management processes to determine a responsible management process for each data set of the plurality of data sets;

perform by the responsible management process a consistency check;

communicate by each responsible management process with the other management processes to confirm a completion of the consistency check;

determine 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; and

enter the cluster into an active mode.

2. The system of claim 1 wherein each data set is associated with one responsible management process.

3. The system of claim 1 wherein the plurality of data sets distributed across the distributed persistent memories include at least a portion of the plurality of data sets distributed across a combination of at least one data row and at least one data column of the distributed persistent memories, the at least one data row and the at least one data column each include at least one persistent memory of the plurality of distributed persistent memories.

4. The system of claim 1 wherein the computer-executable instructions are further configured to enable automatic self-recovery of the at least one data set to a consistent and correct state.

5. The system of claim 4 wherein to enable automatic self-recovery includes:

identifying distributed memories associated with each data set;

classifying whether the at least one data block and the at least one checksum block of each data set are good;

verifying if there are enough good blocks to recover each data set;

performing a consistency check of the good data blocks; and

recovering each data set using good blocks.

6. The system of claim 1 wherein to determine a responsible management process uses a common responsibility algorithm.