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

• US 9,122,627 B1
• Filed: 06/08/2012
• Issued: 09/01/2015
• Est. Priority Date: 08/09/2004
• Status: Active Grant

• Current Assignee: Quest Software, Inc.
• Original Assignee: Dell Software, Inc. (Dell Technologies Inc.)
• Inventors: Sim-Tang, Siew Yong, Ustimenko, Semen Alexandrovich
• Primary Examiner(s): Torres, Joseph D
• Application Number:
  US13/492,330
• Time in Patent Office: 1,180 Days
• Field of Search: 714/770, 714/767, 714/769, 714/780
• US Class Current: 1/1
• 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:

providing a plurality of computer systems forming a distributed computer network, each computer system having a management process operating thereon;

providing 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;

distributing via an erasure encoding process a plurality of data sets across the distributed persistent memories, each data set including at least one data block and at least one check sum block;

initializing the management processes to operate as a cluster;

wherein during the initializing of the management processes to operate as a cluster, each management process;

agrees to enter into an initialization mode;

enters into initialization mode;

suspends regular run time processing; and

registers its data-set management-process management responsibility;

identifying the distributed persistent memories associated with each data set of the plurality of data sets;

classifying whether the at least one data block and at least one checksum block of each data set 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.

2. The method of claim 1 further comprising, for each management process, registering a data-set management-process management responsibility wherein the data-set management-process management responsibility is determined using a common responsibility distribution algorithm.

3. The method of claim 1 wherein each data set is associated with one management process having responsibility for performing encoding and decoding of the data set.

4. The method of claim 1 further comprising determining by a responsible management process, via a sequence indicator, whether each data block and each checksum block of each data set is modified completely.

5. The method of claim 4 wherein the sequence 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.