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

• US 8,086,937 B2
• Filed: 01/28/2010
• Issued: 12/27/2011
• 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:
  US12/695,385
• Publication Number:
  US 20100162044A1
• Time in Patent Office: 698 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. An apparatus, comprising:

one or more processors;

a set of data stores in which data blocks and their associated recovery blocks are stored using an erasure encoding and decoding scheme, the set of data stores interoperably coupled to the one or more processors, the one or more processors programmed with code;

the code executable in the one or more processors during erasure encoding to build and maintain a data structure in a memory, the data structure storing information associated with the data blocks and their associated recovery blocks that identify a sequence of changes to the data blocks, and the code executable in the one or more processors following a given failure event to use the information in the data structure to facilitate a recovery operation, the one or more processors programmed with the executable code to perform at least one of steps (a)-(c);

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

(b) as a given data block is changed, (i) incrementing the sequence number, (ii) associating the incremental sequence number with the given data block, and (iii) associating the incremental sequence number with recovery blocks in the data structure; and

(c) 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 apparatus as described in claim 1 wherein the set of data stores is a group of disks, a group of disk arrays, or a storage area network.

3. The apparatus as described in claim 1 wherein the recovery operation recovers to a consistent state a data set associated with the information in the data structure.

4. The apparatus as described in claim 3 wherein the data set is recovered to the consistent state by rolling the data set forward to a most recent state.

5. The apparatus as described in claim 3 wherein the data set is recovered to the consistent state by rolling the data set backward to a state prior to the failure event.

6. The apparatus as described in claim 1 wherein the information in the data structure is a set of sequence numbers.

7. The apparatus as described in claim 1 wherein step (c) 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 the one or more recoverable subgroups of the uncorrupted blocks.