Granted Patent B1

US 7,681,104 · App. 11/198,061 · Granted Mar 16, 2010

Abstract

Claims (18)

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.

Assignments (29)