Variable-length record, corruption recovery apparatus, system, and method

• US 8,370,405 B2
• Filed: 01/19/2009
• Issued: 02/05/2013
• Est. Priority Date: 01/19/2009
• Status: Expired due to Fees

• Current Assignee: AirBNB Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Reed, David Charles, Sheridan, Jeffrey Thomas, Smith, Max Douglas, Malinowski, Joseph Vincent
• Primary Examiner(s): Ehichioya, Fred I
• Assistant Examiner(s): SMITH, GARRETT A
• Application Number:
  US12/355,981
• Publication Number:
  US 20100185688A1
• Time in Patent Office: 1,478 Days
• Field of Search: None
• US Class Current: 707/822
• CPC Class Codes: G06F 11/0763 by bit configuration check, e.g. of formats or tags

Abstract

A method for identifying records of variable length within a data block containing corrupted data is disclosed herein. In certain embodiments, such a method may include scanning backward from an end of a data block containing variable-length records. The backward scan may proceed, one record at a time, to identify a first span of good (i.e., non-corrupt) records. The method may further include scanning forward from a front of the data block, also proceeding one record at a time, to identify a second span of good records. The method may include identifying a problem region by identifying data that resides between the first span and the second span. The method may also include creating a new record between the first span and the second span that contains the problem region. A corresponding computer program product, apparatus, and system are also disclosed.

Claims

1. A method for identifying variable-length records within a data block containing corrupted data, the method comprising:

scanning, by at least one processor, backward from an end of a data block comprising records of variable length, one record at a time, to identify a first span of good records;

scanning, by the at least one processor, forward from a front of the data block, one record at a time, to identify a second span of good records;

identifying, by the at least one processor, a problem region by identifying data that resides between the first span and the second span, wherein the problem region comprises at least one variable-length record having a corrupt control information field; and

creating, by the at least one processor, a new record between the first span and the second span that encapsulates the problem region, wherein creating the new record comprises creating a control information field for the new record with a length indicator storing the length of the problem region.

2. The method of claim 1, wherein scanning backward from the end of the data block comprises:

maintaining a count value of units traversed while reading bit patterns in the data block, backward from the end of the data block;

recording the count value and resetting the count value upon reading a bit pattern having a value equal to the count value; and

determining, upon arriving at the front of the data block, a length of the first span by summing each recorded count value.

3. The method of claim 1, wherein scanning forward from the front of the data block comprises;

scanning forward from bit pattern to bit pattern by scanning a number of units equal to the value of each bit pattern;

storing a running total of units from the front of the data block to a present location;

obtaining a result, upon arriving at each bit pattern, by subtracting from a total block length a sum of both the running total and a length of the first span; and

determining a length of the second span based on the running total upon a number of units equal to the value of a bit pattern at the present location being greater than the result.

4. The method of claim 3, further comprising selecting a first bit pattern from which to traverse forward using one of a default offset and user input.

5. The method of claim 1, further comprising skipping over the new record after the data block has been read into a memory.

6. The method of claim 1, further comprising applying one or more data recovery algorithms to the new record.

7. A computer program product for identifying variable-length records within a data block containing corrupted data, the computer program product comprising a non-transitory computer-readable storage medium storing computer instructions which when executed by at least one computer cause the at least one computer to perform the following:

scan backward from an end of a data block comprising records of variable length, one record at a time, to identify a first span of good records;

scan forward from a front of the data block, one record at a time, to identify a second span of good records;

identify a problem region by identifying data that resides between the first span and the second span, wherein the problem region comprises at least one variable-length record having corrupt control information field; and

create a new record between the first span and the second span that encapsulates the problem region, wherein creating the new record comprises creating a control information field for the new record with a length indicator storing the length of the problem region.

8. The computer program product of claim 7, wherein scanning backward from the end of the data block comprises:

maintaining a count value of units traversed while reading bit patterns in the data block, backward from the end of the data block;

recording the count value and resetting the count value upon reading a bit pattern having a value equal to the count value; and

determining, upon arriving at the front of the data block, a length of the first span by summing each recorded count.

9. The computer program product of claim 7, wherein scanning forward from the front of the data block comprises:

scanning forward from bit pattern to bit pattern by scanning a number of units equal to the value of each bit pattern;

storing a running total of units from the front of the data block to a present location;

obtaining a result, upon arriving at each bit pattern, by subtracting from a total block length a sum of both the running total and a length of the first span; and

determining a length of the second span based on the running total upon a number of units equal to the value of a bit pattern at the present location being greater than the result.

10. The computer program product of claim 9, wherein the computer instructions further cause the at least one computer to select a first bit pattern from which to scan forward using one of a default offset and user input.

11. The computer program product of claim 7, wherein the computer instructions further cause the at least one computer to skip over the new record after the data block has been read into a memory.

12. The computer program product of claim 7, wherein the computer instructions further cause the at least one computer to apply one or more data recovery algorithms to the new record.

13. An apparatus for identifying variable-length records within a data block containing corrupted data, the apparatus comprising:

at least one processor; and

at least one memory device coupled to the at least one processor and storing modules for execution on the at least one processor, the modules comprising;

a backward scan module configured to scan backward from an end of a data block comprising records of variable length, one record at a time, to identify a first span of good records;

a forward scan module configured to scan forward from a front of the data block, one record at a time, to identify a second span of good records;

an identification module configured to identify a problem region by identifying data that resides between the first span and the second span, wherein the problem region comprises at least one variable-length record having a corrupt control information field; and

a record creation module configured to create a new record between the first span and the second span that encapsulates the problem region, wherein creating the new record comprises creating a control information field for the new record with a length indicator storing the length of the problem region.

14. The apparatus of claim 13, wherein the backward scan module further comprises:

a count module configured to maintain a record of a count value of units traversed while reading bit patterns in the data block, backward from the end of the data block;

a detection module configured to record the count value and to reset the count value upon reading a bit pattern having a value equal to the count value; and

a determination module configured to determine, upon arriving at the front of the data block, a length of the first span by summing each recorded count value.

15. The apparatus of claim 13, wherein the forward scan module further comprises:

a step module configured to scan forward from bit pattern to bit pattern by scanning a number of units equal to the value of each bit pattern;

a count module configured to store a running total of units from the front of the data block to a present location;

a computation module configured to obtain a result, upon arriving at each bit pattern, by subtracting from a total block length a sum of both the running total and a length of the first span; and

a determination module configured to determine a length of the second span based on the running total upon a number of units equal to the value of a bit pattern at the present location being greater than the result.

16. The apparatus of claim 13, wherein the modules further comprise a skip module configured to skip over the new record after the data block has been read into a memory.

17. A system for identifying variable-length records within a data block containing corrupted data, the system comprising:

a storage device configured to store a data block comprising variable-length records;

a memory configured to receive the data block;

a transfer module configured to transfer the data block between the memory and the storage device;

a recovery module configured to;

scan backward from an end of a data block comprising variable-length records, one record at a time, to identify a first span of good records;

scan forward from a front of the data block, one record at a time, to identify a second span of good records;

identify a problem region by identifying data that resides between the first span and the second span, wherein the problem region comprises at least one variable-length record having a corrupt control information field; and

create a new record between the first span and the second span that encapsulates the problem region, wherein creating the new record comprises creating a control information field for the new record with a length indicator storing the length of the problem region.

18. The system of claim 17, further comprising a skip module configured to skip over the new record after the data block has been read into the memory.