VARIABLE-LENGTH RECORD, CORRUPTION RECOVERY APPARATUS, SYSTEM, AND METHOD

• US 20100185688A1
• Filed: 01/19/2009
• Published: 07/22/2010
• Est. Priority Date: 01/19/2009
• Status: Active Grant

• Current Assignee: AirBNB Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Malinowski, Joseph V., Sheridan, Jeffrey T., Reed, David C., Smith, Max D.
• Granted Patent: US 8,370,405 B2
• Time in Patent Office: Days
• US Class Current: 707/803
• 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 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 forward from a front of said data block, one record at a time, to identify a second span of good records;

identifying a problem region by identifying data that resides between said first span and said second span; and

creating a new record between said first span and said second span that comprises said problem region.

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

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

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

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

3. The method of claim 1, wherein scanning forward from said front of said 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 said front of said 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 said running total and a length of said first span; and

determining a length of said second span based on said running total upon a number of units equal to the value of a bit pattern at said present location being greater than said 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 said new record after said data block has been read into a memory.

6. The method of claim 1, further comprising rewriting a number of units in said new record.

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

8. A computer program product, the computer program product comprising a computer-usable medium having computer-usable program code for identifying variable-length records within a data block containing corrupted data, the computer-usable program code comprising:

computer-usable program code 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;

computer-usable program code to scan forward from a front of said data block, one record at a time, to identify a second span of good records;

computer-usable program code to identify a problem region by identifying data that resides between said first span and said second span; and

computer-usable program code to create a new record between said first span and said second span that comprises said problem region.

9. The computer program product of claim 8, wherein said computer-usable program code to scan backward from said end of said data block comprises:

computer-usable program code to maintain a count value of units traversed while reading bit patterns in said data block, backward from said end of said data block;

computer-usable program code to record said count value and to reset said count value upon reading a bit pattern having a value equal to said count value; and

computer-usable program code to determine, upon arriving at said front of said data block, a length of said first span by summing each recorded count.

10. The computer program product of claim 8, wherein scanning forward from said front of said data block comprises;

computer-usable program code to scan forward from bit pattern to bit pattern by scanning a number of units equal to the value of each bit pattern;

computer-usable program code to store a running total of units from said front of said data block to a present location;

computer-usable program code to obtain a result, upon arriving at each bit pattern, by subtracting from a total block length a sum of both said running total and a length of said first span; and

computer-usable program code to determine a length of said second span based on said running total upon a number of units equal to the value of a bit pattern at said present location being greater than said result.

11. The computer program product of claim 10, further comprising computer-usable program code to select a first bit pattern from which to scan forward using one of a default offset and user input.

12. The computer program product of claim 8, further comprising computer-usable program code to skip over said new record after said data block has been read into a memory.

13. The computer program product of claim 8, further comprising computer-usable program code to rewrite a number of units in said new record.

14. The computer program product of claim 8, further comprising computer-usable program code to apply one or more data recovery algorithms to said new record.

15. An apparatus for identifying variable-length records within a data block containing corrupted data, the apparatus 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 said 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 said first span and said second span; and

a record creation module configured to create a new record between said first span and said second span that comprises said problem region.

16. The apparatus of claim 15, wherein said backward scan module comprises:

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

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

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

17. The apparatus of claim 15, wherein said forward scan module 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 said front of said 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 said running total and a length of said first span; and

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

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

19. 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 said data block;

a transfer module configured to transfer said data block between said memory and said 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 said 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 said first span and said second span; and

create a new record between said first span and said second span that comprises said problem region.

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