METHOD FOR LOCK-FREE CLUSTERED ERASURE CODING AND RECOVERY OF DATA ACROSS A PLURALITY OF DATA STORES IN A NETWORK

• US 20100162076A1
• Filed: 01/28/2010
• Published: 06/24/2010
• Est. Priority Date: 08/09/2004
• Status: Active Grant

• Current Assignee: Quest Software, Inc.
• Original Assignee: Quest Software, Inc.
• Inventors: Sim-Tang, Siew Yong, Ustimenko, Semen Alexandrovich
• Granted Patent: US 8,051,361 B2
• Time in Patent Office: Days
• US Class Current: 714/752
• 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 method operative across a set of dispersed data stores, comprising:

having a distributed set of instances of a management process initialize into a cluster that is responsible for erasure encoding and decoding of data sets to be stored across the dispersed data stores;

following initialization of the cluster, having given management process instances in the cluster erasure encode and decode data sets across the dispersed data stores.

2. The method as described in claim 1 wherein the management process instances initialize into the cluster by ceasing any runtime processing and then negotiating for given management responsibilities.

3. The method as described in claim 2 further including the step of having a given management process instance perform a consistency check on a given data set.

4. The method as described in claim 3 further including the step of recovering inconsistent data in the given data set.

5. The method as described in claim 1 wherein the given management process instances erasure encode a data set across the dispersed data stores during a write operation.

6. The method as described in claim 1 wherein the given management process instances erasure decode a data set following an unsuccessful read operation.

7. The method as described in claim 1 wherein the given management processes comprise at least one data I/O processor and a set of one or more erasure coding processors.

8. The method as described in claim 7 wherein the set of one or more erasure coding processors share given data stores for storing recovery blocks.

9. The method as described in claim 1 further including the step of re-initializing the cluster upon a given occurrence.

10. The method as described in claim 9 wherein the given occurrence is one of:

adding a new management process instance to the cluster, or removing a management process instance from the cluster.

11. The method as described in claim 1 wherein management process instances communicate with one another by a heartbeat.

12. A method operative across a set of dispersed data stores, comprising:

having a distributed set of instances of a management process initialize into a cluster that is responsible for erasure encoding and decoding of data sets to be stored across the dispersed data stores;

during initialization of the cluster, having a given management process instance perform a consistency check on a given data set;

as necessary, recovering any inconsistent data in the given data set; and

following initialization of the cluster, having a given management process instance erasure encode or decode a data set across the dispersed data stores.

13. The method as described in claim 12 wherein management process instances initialize into the cluster by ceasing any runtime-processing and then negotiating for given management responsibilities.

14. The method as described in claim 12 wherein given management process instances erasure encode a data set across the dispersed data stores during a write operation.

15. The method as described in claim 12 wherein given management process instances erasure decode a data set following an unsuccessful read operation.