Method for erasure coding data across a plurality of data stores in a network

• US 7,681,104 B1
• Filed: 08/05/2005
• Issued: 03/16/2010
• Est. Priority Date: 08/09/2004
• Status: Active Grant

• Current Assignee: Quest Software, Inc.
• Original Assignee: BakBone Software, Inc. (Quest Software, Inc.)
• Inventors: Sim-Tang, Siew Yong, Ustimenko, Semen Alexandrovich
• Primary Examiner(s): Torres; Joseph D
• Application Number:
  US11/198,061
• Time in Patent Office: 1,684 Days
• Field of Search: 714/763, 714/769, 714/770
• US Class Current: 714/763
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence

Abstract

An efficient method to apply an erasure encoding and decoding scheme across dispersed data stores that receive constant updates. A data store is a persistent memory for storing a data block. Such data stores include, without limitation, a group of disks, a group of disk arrays, or the like. An encoding process applies a sequencing method to assign a sequence number to each data and checksum block as they are modified and updated onto their data stores. The method preferably uses the sequence number to identify data set consistency. The sequencing method allows for self-healing of each individual data store, and it maintains data consistency and correctness within a data block and among a group of data blocks. The inventive 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 within a set of data stores in which data blocks and their associated recovery blocks are stored using an erasure encoding and decoding scheme comprising:

(a) providing a processor;

(b) providing a memory interoperably coupled to the processor and having computer software code stored thereon;

(c) using the processor and the memory in combination to perform at least one of steps (d)-(g);

(d) initializing a counter;

(e) storing a sequence number in a data structure having positions corresponding to the data blocks and their associated recovery blocks;

(f) as a given data block is changed, (i) incrementing the counter, (ii) assigning a value of the counter to a then current sequence number at a position associated with the given data block, and (iii) assigning the value of the counter to a then current sequence number at each position in the data structure associated with a recovery value;

(g) upon a given failure event, using the sequence numbers in the data structure to recover a data set associated with the sequence numbers in the data structure.

2. The method as described in claim 1 wherein step (g) comprises:

identifying a set of uncorrupted blocks;

determining whether the set of uncorrupted blocks are consistent;

if the set of uncorrupted blocks are consistent, recovering the data set using information in the set of uncorrupted blocks;

if the set of uncorrupted blocks are not consistent, locating one or more recoverable subgroups of the set of uncorrupted blocks; and

recovering the data set using information in a recoverable subgroup of the uncorrupted blocks.

3. The method as described in claim 2 wherein the set of uncorrupted blocks comprises a given subset of data blocks and a given subset of recovery blocks.

4. The method as described in claim 2 wherein the determining step evaluates whether the uncorrupted blocks are partitioned.

5. The method as described in claim 2 wherein a given block is identified as uncorrupted by evaluating a block header or a block trailer.

6. The method as described in claim 2 wherein the step of locating one or more recoverable subgroups of the set of uncorrupted blocks uses a block associated with a highest sequence number in the data structure.