Method and system for data recovery using a distributed and scalable data structure

• US 6,122,754 A
• Filed: 05/22/1998
• Issued: 09/19/2000
• Est. Priority Date: 05/22/1998
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Litwin, Witold, Menon, Jaishankar Moothedath, Risch, Tore Johan Martin
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): REVAK, CHRISTOPHER A
• Application Number:
  US09/083,599
• Time in Patent Office: 851 Days
• Field of Search: 714/3, 714/4, 714/5, 714/6, 714/7, 714/710, 714/711, 711/100, 711/111, 711/112, 711/113, 711/114, 711/161, 711/162
• US Class Current: 714/4.3
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity

Abstract

Disclosed is a system for recovering data objects stored in a data bucket in a computer system comprised of servers interconnected by a network. Each server includes a storage area. Data buckets are included in a plurality of the storage areas throughout the network. A failure of a data bucket and nth bucket group number associated with the failed data bucket are determined, wherein n is an integer value greater than zero. Parity data in a parity bucket associated with the nth bucket group number is then located. The data objects in the failed data bucket are then recovered from the parity data in the located parity bucket. After determining that the recovery of data objects using the parity data in the parity bucket associated with the nth bucket group number was unsuccessful, for each n'"'"' not equal to n and while the data objects have not been recovered and all n'"'"' have not been considered, performing the steps of: determining an n'"'"'th bucket group number associated with the failed data bucket; locating parity data in a parity bucket associated with the n'"'"'th bucket group number; and recovering the data objects in the failed data bucket from the parity data in the located parity bucket associated with the n'"'"'th bucket group number. Recovery can also be made of the parity data using the data objects.

Claims

1. A method for recovering data objects stored in a data bucket in a computer system comprised of servers interconnected by a network, wherein each server includes a storage area, wherein data buckets are included in a plurality of the storage areas throughout the network, comprising the steps of:

determining a failure of a data bucket;

determining an nth bucket group number associated with the failed data bucket, wherein n is an integer value greater than zero;

locating parity data in a parity bucket associated with the nth bucket group number;

recovering the data objects in the failed data bucket from the parity data in the located parity bucket associated with the nth bucket group number;

determining whether the recovery of data objects was successful; and

after determining that the recovery of data objects using the parity data in the parity bucket associated with the nth bucket group number was unsuccessful, whereby n'"'"' is created by splitting a bucket from the nth bucket group to create a new bucket grouping, for each n'"'"', not equal to n and while the data objects have not been recovered and all n'"'"' have not been considered, performing the steps of;

(i) determining an n'"'"'th bucket group number associated with the failed data bucket that has not been considered;

(ii) locating parity data in a parity bucket associated with the n'"'"'th bucket group number; and

(iii) recovering the data objects in the failed data bucket from the parity data in the located parity bucket associated with the n'"'"'th bucket group number.

2. The method of claim 1, wherein a first value of n'"'"' is (n+1) and wherein further values of n'"'"' are determined by incrementing the previous value of n'"'"' by one.

3. The method of claim 1, wherein for a given n'"'"', the data objects are recovered from the located parity data in the parity bucket associated with a bucket group number in the n'"'"'th set of bucket group numbers and from the data objects in data buckets, other than the failed bucket, associated with the n'"'"'th bucket group number.

4. The method of claim 1, wherein data buckets are assigned nth and n'"'"'th bucket group numbers such that for a first data bucket and second data bucket, if the first data bucket and second data bucket are associated with the same nth bucket group number, then the first data bucket and second data bucket are associated with different n'"'"'th bucket group numbers.

5. The method of claim 1, wherein data objects are arranged in a data bucket according to a rank value r, wherein the parity data in a parity bucket comprises a plurality of parity records, wherein each parity record is associated with a given bucket group number and a given rank r, such that the parity record maintains parity data for the data objects having the given rank r in data buckets associated with the given bucket group number, and wherein the step of recovering a data object at given rank r in a data bucket associated with the given bucket group number comprises reconstructing the data object from the parity record having given rank r in the parity bucket associated with the given bucket group number.

6. The method of claim 5, wherein the step of recovering the data objects from the located second parity bucket comprises reconstructing a data object having given rank r in a data bucket associated with the second bucket group number from the parity record having given rank r in the parity bucket associated with the second bucket group number.

7. The method of claim 1, further comprising the step of recovering a failed parity bucket, comprising the steps of:

determining a bucket group number of the failed parity bucket;

querying the data objects from all data buckets associated with the bucket group number of the failed parity bucket; and

reconstructing the parity data in the failed parity bucket from the queried data objects.

8. The method of claim 7, wherein data objects are arranged in a data bucket according to a rank value r, and wherein the parity data in a parity bucket comprises a plurality of parity records, wherein parity records are associated with a given bucket group number and a given rank r, such that the parity record maintains parity data for the data objects having the given rank r in data buckets associated with the given bucket group number, wherein parity data is reconstructed by reconstructing each parity record, wherein the step of querying the data objects comprises querying the data objects at a given rank r in data buckets associated with the given bucket group number of the parity record, and wherein the step of reconstructing the parity data comprises reconstructing each parity record from the data objects having the given rank r of the parity record.

9. The method of claim 7, further comprising the steps of:

determining whether the parity data could not be recovered;

indicating a failed data bucket that prevented the recovery of the parity data after determining that parity data could not be recovered;

recovering the indicated failed data bucket; and

recovering the parity data after recovering the indicated failed data bucket.

10. The method of claim 7, further comprising the step of indicating all failed parity and data buckets, wherein all indicated data buckets are recovered before recovering any parity buckets.

11. The method of claim 1, wherein the step of determining the failure of a data bucket comprises the steps of:

processing a search request from a requesting device for at least one data object;

querying the data buckets storing the requested data objects; and

determining a failure of at least one of the data buckets storing the requested data objects, wherein the steps of recovering the data objects are only performed with respect to the requested data objects, wherein after recovering the requested data objects, performing the step of transmitting the requested data objects to the requesting device.

12. A computer system for recovering data objects, comprising:

a plurality of computer devices including storage areas;

a network providing communication among the computer systems;

a plurality of data buckets included within storage areas of the computer devices, wherein the data objects are stored in data buckets throughout the network; and

program logic implemented in at least one of the computer devices for;

(i) determining a failure of a data bucket;

(ii) determining an nth bucket group number associated with the failed data bucket, wherein n is an integer greater than zero;

(iii) locating parity data in a parity bucket associated with the nth bucket group number;

(iv) recovering the data objects in the failed data bucket from the parity data in the located parity bucket associated with the nth bucket group number;

(v) determining whether the recovery of data objects was successful; and

(vi) after determining that the recovery of data objects using the parity data in the parity bucket associated with the nth bucket group number was unsuccessful, recovering the data objects in the failed data bucket from parity data in a located parity bucket associated with an n'"'"' bucket group number, whereby n'"'"' is created by splitting a bucket from the nth bucket group to create a new bucket grouping, wherein n'"'"' is an integer value not equal to n.

13. The computer system of claim 12, wherein data buckets are assigned n th and n'"'"'th bucket group numbers such that for a first data bucket and a second data bucket, if the first data bucket and second data bucket are associated with the same n th bucket group number, then the first data bucket and second data bucket are associated with different n'"'"'th bucket group numbers.

14. The computer system of claim 12, wherein the program logic for recovering a data object at given rank r in a data bucket associated with the n th bucket group number reconstructs the data object from a parity record having given rank r in a parity bucket associated with the nth bucket group number.

15. The computer system of claim 12, wherein the program logic for recovering the data objects from the located parity bucket associated with the n'"'"'th bucket group number reconstructs a data object having given rank r in a data bucket associated with the n'"'"' the bucket group number from the parity record having given rank r in the parity bucket associated with the n'"'"'th bucket group number.

16. The computer system of claim 12, wherein the program logic further:

determines a bucket group number of the failed parity bucket;

queries the data objects from all data buckets associated with the bucket group number of the failed parity bucket; and

reconstructs the parity data in the failed parity bucket from the queried data objects.

17. The computer system of claim 16, wherein parity data is reconstructed by reconstructing parity records, wherein the program logic for querying the data objects queries the data objects at a given rank r in data buckets associated with the bucket group number of the parity record, and wherein the program logic for reconstructing the parity data reconstructs each parity record from the data objects having the given rank r of the parity record.

18. The computer system of claim 16, wherein the program logic further:

determines whether the parity data could not be recovered;

indicates a failed data bucket that prevented the recovery of the parity data after determining that parity data could not be recovered;

recovers the indicated failed data bucket; and

recovers the parity data after recovering the indicated failed data bucket.

19. The computer system of claim 12, wherein the program logic further:

processes a search request from a requesting device for at least one data object;

queries the data buckets storing the requested data objects; and

determines a failure of at least one of the data buckets storing the requested data objects, wherein the steps of recovering the data objects are only performed with respect to the requested data objects, wherein after recovering the requested data objects, performing the step of transmitting the requested data objects to the requesting device.

20. An article of manufacture for use in programming a computer system comprised of a plurality of computer devices interconnected by a network system, the article of manufacture comprising at least one computer readable storage device including at least one computer program embedded therein that causes computer devices within the computer system to perform the steps of:

determining a failure of a data bucket;

determining an nth bucket group number associated with the failed data bucket, wherein n is an integer value greater than zero;

locating parity data in a parity bucket associated with the nth bucket group number;

recovering the data objects in the failed data bucket from the parity data in the located parity bucket associated with the nth bucket group number;

determining whether the recovery of data objects was successful; and

after determining that the recovery of data objects using the parity data in the nth parity bucket was unsuccessful, whereby n'"'"' is created by splitting a bucket from the nth bucket group to create a new bucket grouping, for each n'"'"' not equal to n and while the data objects have not been recovered and all n'"'"' have not been considered, performing the steps of;

(i) determining an n'"'"'th bucket group number associated with the failed data bucket that has not been considered;

(ii) locating parity data in the parity bucket associated with the n'"'"'th bucket group number; and

(iii) recovering the data objects in the failed data bucket from the parity data in the located parity bucket associated with the n'"'"'th bucket group number.

21. The article of manufacture of claim 20, wherein a first value of n'"'"' is (n+1) and wherein further values of n'"'"' are determined by incrementing the previous value of n'"'"' by one.

22. The article of manufacture of claim 20, wherein for a given n'"'"', the data objects are recovered from the located parity data in the parity bucket associated with a bucket group number in the n'"'"'th set of bucket group numbers and from the data objects in data buckets, other than the failed bucket, associated with the n'"'"'th bucket group number.

23. The article of manufacture of claim 20, wherein data buckets are assigned nth and n'"'"'th bucket group numbers such that for a first data bucket and second data bucket, if the first data bucket and second data bucket are associated with the same nth bucket group number, then the first data bucket and second data bucket are associated with different n'"'"'th bucket group numbers.

24. The article of manufacture of claim 20, wherein data objects are arranged in a data bucket according to a rank value r, wherein the parity data in a parity bucket comprises a plurality of parity records, wherein each parity record is associated with a given bucket group number and a given rank r, such that the parity record maintains parity data for the data objects having the given rank r in data buckets associated with the given bucket group number, and wherein the step of recovering a data object at given rank r in a data bucket associated with the given bucket group number comprises reconstructing the data object from the parity record having given rank r in the parity bucket associated with the given bucket group number.

25. The article of manufacture of claim 24, wherein the step of recovering the data objects from the located parity bucket comprises reconstructing a data object having given rank r in a data bucket associated with the n'"'"'th bucket group number from the parity record having given rank r in the parity bucket associated with the second bucket group number.

26. The article of manufacture of claim 20, further comprising the step of recovering a failed parity bucket, comprising the steps of:

determining a bucket group number of the failed parity bucket;

querying the data objects from all data buckets associated with the bucket group number of the failed parity bucket; and

reconstructing the parity data in the failed parity bucket from the queried data objects.

27. The article of manufacture of claim 26, wherein data objects are arranged in a data bucket according to a rank value r, and wherein the parity data in a parity bucket comprises a plurality of parity records, wherein parity records are associated with a given bucket group number and a given rank r, such that the parity record maintains parity data for the data objects having the given rank r in data buckets associated with the given bucket group number, wherein parity data is reconstructed by reconstructing each parity record, wherein the step of querying the data objects comprises querying the data objects at a given rank r in data buckets associated with the given bucket group number of the parity record, and wherein the step of reconstructing the parity data comprises reconstructing each parity record from the data objects having the given rank r of the parity record.

28. The article of manufacture of claim 26, further comprising the steps of:

determining whether the parity data could not be recovered;

indicating a failed data bucket that prevented the recovery of the parity data after determining that parity data could not be recovered;

recovering the indicated failed data bucket; and

recovering the parity data after recovering the indicated failed data bucket.

29. The article of manufacture of claim 26, further comprising the step of indicating all failed parity and data buckets, wherein all indicated data buckets are recovered before recovering any parity buckets.

30. The article of manufacture of claim 20, wherein the step of determining the failure of a data bucket comprises the steps of:

processing a search request from a requesting device for at least one data object;

querying the data buckets storing the requested data objects; and

determining a failure of at least one of the data buckets storing the requested data objects, wherein the steps of recovering the data objects are only performed with respect to the requested data objects, wherein after recovering the requested data objects, performing the step of transmitting the requested data objects to the requesting device.