Database reconstruction using embedded database backup codes

• US 5,963,961 A
• Filed: 11/25/1997
• Issued: 10/05/1999
• Est. Priority Date: 11/25/1997
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Hannigan, Kenneth Eugene, Cannon, David Maxwell, Martin, Howard Newton
• Primary Examiner(s): Kulik, Paul V.
• Application Number:
  US08/978,526
• Time in Patent Office: 679 Days
• Field of Search: 395/180, 395/182.13, 395/182.03, 707/200, 707/202
• US Class Current: 707/812
• CPC Class Codes: G06F 11/1448 Management of the data involved in backup or backup restore
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

Files are stored along with embedded codes containing information useful in reconstructing a failed database that normally contains information about the files. Multiple user files are stored in the form of a managed file, identified by a managed filename. Storage of the managed file includes a number of sub-steps, among them the generation and storage of a first frame marker including a recognition pattern, the managed filename, a next-frame locator, and a sequence number distinguishing the first frame marker from other frame markers. Next, a self-describing header is generated and stored adjacent to the first frame marker. A first one of the user files is stored adjacent to the self-describing header. The self-describing header and following user file are exclusively associated with each other, and the header contains certain information about the adjacent user file. Storage of the user file and self-describing header may be punctuated by one or more intermittent frame markers, which are preferably stored at fixed intervals along the managed file. The sequence of storing a self-describing header, a user file, and any intermittent frame markers is repeated until a predetermined condition is satisfied, such as reaching the last user file for inclusion in the managed file. Then, a table-of-contents is generated and stored substantially adjacent the last user file. A frame trailer is then stored substantially adjacent the table-of-contents, the frame trailer containing information representing the position of the table-of-contents. Another aspect of the invention concerns database reconstruction using information including the embedded codes.

Claims

1. A method of storing machine-readable data on a data storage medium, the method comprising:

storing multiple user files in substantially contiguous arrangement, the user files forming a managed file having a managed filename;

storing multiple self-describing headers, each self-describing header substantially immediately preceding an associated user file and including predetermined information about that user file;

storing a table-of-contents following a last one of the user files, the table-of-contents containing information representing positions of the self-describing headers; and

storing multiple frame markers, each including;

a predetermined recognition pattern;

the managed filename;

a sequence indicator representing a sequence of the frame marker relative to other frame markers associated with the managed filename;

a next-frame locator containing information representing a position of a next frame marker;

wherein the frame markers are placed at a beginning of the managed file, at an end of the table-of-contents, and within the substantially contiguous arrangement; and

wherein a final one of the frame markers includes indicia identifying the frame marker as the final one and additionally includes information representing a position of the table-of-contents.

2. The method of claim 1, the storing of the user files, self-describing headers, table-of-contents, and frame markers being performed in an order comprising:

(a) storing a first one of the frame markers;

(b) storing a self-describing header adjacent to the frame marker most recently stored and storing a user file adjacent to the self-describing header most recently stored, the user file or self-describing header being interrupted by one or more intervening frame markers;

(c) repeating step (b) until all user files have been stored, and then;

storing the table-of-contents substantially adjacent to the user file most recently stored; and

storing the final frame marker substantially adjacent to the table-of-contents.

3. The method of claim 1, the positions of the self-describing headers comprising offsets from a predetermined storage position.

4. The method of claim 1, the next-frame locator comprising an address of the next frame marker.

5. The method of claim 1, the next-frame locator comprising an offset from a predetermined point on the data storage medium to the next frame marker.

6. The method of claim 1, the next-frame locator of each frame marker comprising a length of storage space between that frame marker and the next frame marker.

7. A method of storing data, comprising:

(a) receiving multiple user files;

(b) storing a first managed file, having a first managed filename, comprising;

(1) generating and storing a first frame marker, the frame marker comprising;

a predetermined recognition pattern;

the first managed filename;

a next-frame locator indicating a location of a second frame marker; and

a sequence number of the first frame marker;

(2) generating and storing a self-describing header including predetermined information about a next one of the user files;

(3) storing the next user file and any intermittent frame markers that occur within the next user file in accordance with a prescribed frame marker pattern;

(4) repeating steps (2) and (3) for each received user file received until a predetermined condition is satisfied, and thereupon;

generating and storing a table-of-contents substantially adjacent a last one of the stored user files; and

storing a frame trailer substantially adjacent the table-of-content, the frame trailer containing information representing a storage position of the table-of-contents.

8. A method for collecting information from source data stored on a recording medium for use in constructing a database describing the data;

where the source data comprises;

multiple user files in substantially contiguous arrangement, the user files forming a managed file having a managed filename;

multiple self-describing headers, each self-describing header substantially immediately preceding an associated user file and including predetermined information about that user file;

a table-of-contents following a last one of the user files, the table-of-contents containing information representing positions of the self-describing headers; and

multiple frame markers, each including;

a predetermined recognition pattern;

the managed filename;

a sequence indicator representing a sequence of the frame marker relative to other frame markers associated with the managed filename; and

a next-frame locator containing information representing a position of a next frame marker;

wherein the frame markers are placed at a beginning of the managed file, at an end of the table-of-contents, and within the substantially contiguous arrangement;

wherein a final one of the frame markers includes indicia identifying the frame marker as the final one and additionally includes information representing a position of the table-of-contents;

the method comprising;

locating a first one of the frame markers by running a read sensor past the recording medium to scan for the recognition pattern;

finding the final frame marker by repeatedly;

reading a next-frame locator of the frame where the read sensor is positioned, determining a position of the next frame marker using the read next-frame locator, advancing the read sensor to the determined position of the next frame marker, and reading the next frame marker to determine whether this is the final frame marker;

in response to finding the final frame marker;

reading from the final frame marker the information representing the position of the table-of-contents; and

positioning the read sensor at the position of the table-of-contents and reading the table-of-contents including the information representing the positions of the self-describing headers.

9. The method of claim 8, further comprising:

using the information representing the positions of the self-describing headers, individually positioning the read sensor at each self-describing header and reading the information about the user file associated with that self-describing header.

10. The method of claim 9, the method further comprising constructing the database by compiling the information about the user files from each self-describing header and storing the compiled information in a predetermined database format.

11. The method of claim 8, the method further comprising constructing the database, including:

using the information read from the table-of-contents to determine, for each user file in the managed file, the user file'"'"'s length and the user file'"'"'s starting position within the managed file relative to other user files; and

writing to the database data associating each user file with its length, its offset, and the managed file.

12. A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method for storing machine-readable data on a data storage medium, the method comprising:

storing multiple user files in substantially contiguous arrangement, the user files forming a managed file having a managed filename;

storing multiple self-describing headers, each self-describing header substantially immediately preceding an associated user file and including predetermined information about that user file;

storing a table-of-contents following a last one of the user files, the table-of-contents containing information representing positions of the self-describing headers; and

storing multiple frame markers, each including;

a predetermined recognition pattern;

the managed filename;

a sequence indicator representing a sequence of the frame marker relative to other frame markers associated with the managed filename;

a next-frame locator containing information representing a position of a next frame marker;

wherein the frame markers are placed at a beginning of the managed file, at an end of the table-of-contents, and within the substantially contiguous arrangement; and

wherein a final one of the frame markers includes indicia identifying the frame marker as the final one and additionally includes information representing a position of the table-of-contents.

13. The medium of claim 12, the storing of the user files, self-describing headers, table-of-contents, and frame markers being performed in an order comprising:

(a) storing a first one of the frame markers;

(b) storing a self-describing header adjacent to the frame marker most recently stored and storing a user file adjacent to the self-describing header most recently stored, the user file or self-describing header being interrupted by one or more intervening frame markers;

(c) repeating step (b) until all user files have been stored, and then;

storing the table-of-contents substantially adjacent to the user file most recently stored; and

storing the final frame marker substantially adjacent to the table-of-contents.

14. The medium of claim 12, the positions of the self-describing headers comprising offsets from a predetermined storage position.

15. The medium of claim 12, the next-frame locator comprising an address of the next frame marker.

16. The medium of claim 12, the next-frame locator comprising an offset from a predetermined point on the data storage medium to the next frame marker.

17. The medium of claim 12, the next-frame locator of each frame marker comprising a length of storage space between that frame marker and the next frame marker.

18. A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method for storing data, the method comprising:

(a) receiving multiple user files;

(b) storing a first managed file, having a first managed file name, comprising;

(1) generating and storing a first frame marker, the frame marker comprising;

a predetermined recognition pattern;

the first managed filename;

a next-frame locator indicating a location of a second frame marker; and

a sequence number of the first frame marker;

(2) generating and storing a self-describing header including predetermined information about a next one of the user files;

(3) storing the next user file and any intermittent frame markers that occur within the next user file in accordance with a prescribed frame marker pattern;

(4) repeating steps (2) and (3) for each received user file received until a predetermined condition is satisfied, and thereupon;

generating and storing a table-of-contents substantially adjacent a last one of the stored user files; and

storing a frame trailer substantially adjacent the table-of-content, the frame trailer containing information representing a storage position of the table-of-contents.

19. A signal-bearing medium tangibly embodying a program of machine-readable instructions executable by a digital processing apparatus to perform a method for collecting self-describing information from source data stored on a recording medium for use in constructing a database describing the data, where the source data comprises:

multiple user files in substantially contiguous arrangement, the user files forming a managed file having a managed filename;

multiple self-describing headers, each self-describing header substantially immediately preceding an associated user file and including predetermined information about that user file;

a table-of-contents following a last one of the user files, the table-of-contents containing information representing positions of the self-describing headers; and

multiple frame markers, each including;

a predetermined recognition pattern;

the managed filename;

a sequence indicator representing a sequence of the frame marker relative to other frame markers associated with the managed filename; and

a next-frame locator containing information representing a position of a next frame marker;

wherein the frame markers are placed at a beginning of the managed file, at an end of the table-of-contents, and within the substantially contiguous arrangement;

wherein a final one of the frame markers includes indicia identifying the frame marker as the final one and additionally includes information representing a position of the table-of-contents;

the method comprising;

locating a first one of the frame markers by running a read sensor past the recording medium to scan for the recognition pattern;

finding the final frame marker by repeatedly;

reading a next-frame locator of the frame where the read sensor is positioned, determining a position of the next frame marker using the read next-frame locator, advancing the read sensor to the determined position of the next frame marker, and reading the next frame marker to determine whether this is the final frame marker;

in response to finding the final frame marker;

reading from the final frame marker the information representing the position of the table-of-contents; and

positioning the read sensor at the position of the table-of-contents and reading the table-of-contents including the information representing the positions of the self-describing headers.

20. The medium of claim 19, the method further comprising:

using the information representing the positions of the self-describing headers, individually positioning the read sensor at each self-describing header and reading the information about the user file associated with that self-describing header.

21. The medium of claim 20, the method further comprising constructing the database by compiling, the information about the user files from each self-describing header and storing the compiled information in a predetermined database format.

22. The medium of claim 19, the method further comprising constructing the database, including:

using the information read from the table-of-contents to determine, for each user file in the managed file, the user file'"'"'s length and the user file'"'"'s starting position within the managed file relative to other user files; and

writing to the database data associating each user file with its length, its offset, and the managed file.

23. A data storage subsystem, comprising:

a data storage;

a digital data processor, programmed to perform a method of storing machine-readable data on a data storage medium, the method comprising;

storing multiple user files in substantially contiguous arrangement, the user files forming a managed file having a managed filename;

storing multiple self-describing headers, each self-describing header substantially immediately preceding an associated user file and including predetermined information about that user file;

storing a table-of-contents following a last one of the user files, the table-of-contents containing information representing positions of the self-describing headers; and

storing multiple frame markers, each including;

a predetermined recognition pattern;

the managed filename;

a sequence indicator representing a sequence of the frame marker relative to other frame markers associated with the managed filename;

a next-frame locator containing information representing a position of a next frame marker;

wherein the frame markers are placed at a beginning of the managed file, at an end of the table-of-contents, and within the substantially contiguous arrangement; and

wherein a final one of the frame markers includes indicia identifying the frame marker as the final one and additionally includes information representing a position of the table-of-contents.

24. The subsystem of claim 23, the storing of the user files, self-describing headers, table-of-contents, and frame markers being performed in an order comprising:

(a) storing a first one of the frame markers;

(b) storing a self-describing header adjacent to the frame marker most recently stored and storing a user file adjacent to the self-describing header most recently stored, the user file or self-describing header being interrupted by one or more intervening frame markers;

(c) repeating, step (b) until all user files have been stored, and then;

storing the table-of-contents substantially adjacent to the user file most recently stored; and

storing the final frame marker substantially adjacent to the table-of-contents.

25. The subsystem of claim 24, the positions of the self-describing headers comprising offsets from a predetermined storage position.

26. The subsystem of claim 24, the next-frame locator comprising an address of the next frame marker.

27. The subsystem of claim 24, the next-frame locator comprising an offset from a predetermined point on the data storage medium to the next frame marker.

28. The subsystem of claim 24, the next-frame locator of each frame marker comprising a length of storage space between that frame marker and the next frame marker.

29. A data storage subsystem, comprising:

a data storage;

a digital data processor, programmed to perform a method of storing data, the method comprising;

(a) receiving multiple user files;

(b) storing a first managed file, having a first managed filename, comprising;

(1) generating and storing a first frame marker, the frame marker comprising;

a predetermined recognition pattern;

the first managed filename;

a next-frame locator indicating a location of a second frame marker; and

a sequence number of the first frame marker;

(2) generating and storing a self-describing header including predetermined information about a next one of the user files;

(3) storing the next user file and any intermittent frame markers that occur within the next user file in accordance with a prescribed frame marker pattern;

(4) repeating steps (2) and (3) for each received user file received until a predetermined condition is satisfied, and thereupon;

generating and storing a table-of-contents substantially adjacent a last one of the stored user files; and

storing a frame trailer substantially adjacent the table-of-content, the frame trailer containing information representing a storage position of the table-of-contents.

30. A data storage subsystem, comprising:

a data storage containing source data, including;

multiple user files in substantially contiguous arrangement, the user files forming a managed file having a managed filename;

multiple self-describing headers, each self-describing header substantially immediately preceding an associated user file and including predetermined information about that user file;

a table-of-contents following a last one of the user files, the table-of-contents containing information representing positions of the self-describing headers; and

multiple frame markers, each including;

a predetermined recognition pattern;

the managed filename;

a sequence indicator representing a sequence of the frame marker relative to other frame markers associated with the managed filename; and

a next-frame locator containing information representing a position of a next frame marker;

wherein the frame markers are placed at a beginning of the managed file, at an end of the table-of-contents, and within the substantially contiguous arrangement;

wherein a final one of the frame markers includes indicia identifying the frame marker as the final one and additionally includes information representing a position the table-of-contents;

the method comprising;

locating a first one of the frame markers by running a read sensor past the recording medium to scan for the recognition pattern;

finding the final frame marker by repeatedly;

reading a next-frame locator of the frame where the read sensor is positioned, determining a position of the next frame marker using the read next-frame locator, advancing the read sensor to the determined position of the next frame marker, and reading the next frame marker to determine whether this is the final frame marker;

in response to finding the final frame marker;

reading from the final frame marker the information representing the position of the table-of-contents; and

positioning the read sensor at the position of the table-of-contents and reading the table-of-contents including the information representing the positions of the self-describing headers.

31. The subsystem of claim 30, further comprising:

using the information representing the positions of the self-describing headers, individually positioning the read sensor at each self-describing header and reading the information about the user file associated with that self-describing header.

32. The subsystem of claim 30, the method further comprising constructing the database by compiling the information about the user files from each self-describing header and storing the compiled information in a predetermined database format.

33. The subsystem of claim 30, the method further comprising constructing the database, including:

using the information read from the table-of-contents to determine, for each user file in the managed file, the user file'"'"'s length and the user file'"'"'s starting position within the managed file relative to other user files; and

writing to the database data associating each user file with its length, its offset, and the managed file.

34. A data storage subsystem, comprising:

a data storage means;

a digital data processing means for storing machine-readable data on a data storage medium, by;

storing multiple user files in substantially contiguous arrangement, the user files forming a managed file having a managed filename;

storing multiple self-describing headers, each self-describing header substantially immediately preceding an associated user file and including predetermined information about that user file;

storing a table-of-contents following a last one of the user files, the table-of-contents containing information representing positions of the self-describing headers; and

storing multiple frame markers, each including;

a predetermined recognition pattern;

the managed filename;

a sequence indicator representing a sequence of the frame marker relative to other frame markers associated with the managed filename;

a next-frame locator containing information representing a position of a next frame marker;

wherein the frame markers are placed at a beginning of the managed file, at an end of the table-of-contents, and within the substantially contiguous arrangement; and

wherein a final one of the frame markers includes indicia identifying the frame marker as the final one and additionally includes information representing a position of the table-of-contents.

35. A data storage subsystem, comprising:

a data storage means;

a digital data processing means for storing data, by;

(a) receiving multiple user files;

(b) storing a first managed file, having a first managed filename, comprising;

(1) generating and storing a first frame marker, the frame marker comprising;

a predetermined recognition pattern;

the first managed filename;

a next-frame locator indicating a location of a second frame marker; and

a sequence number of the first frame marker;

(2) generating and storing a self-describing header including predetermined information about a next one of the user files;

(3) storing the next user file and any intermittent frame markers that occur within the next user file in accordance with a prescribed frame marker pattern;

(4) repeating steps (2) and (3) for each received user file received until a predetermined condition is satisfied, and thereupon;

generating and storing a table-of-contents substantially adjacent a last one of the stored user files; and

storing a frame trailer substantially adjacent the table-of-content, the frame trailer containing information representing a storage position of the table-of-contents.

36. A data storage subsystem, comprising:

a means for storing source data that includes;

multiple user files in substantially contiguous arrangement, the user files forming a managed file having a managed filename;

multiple self-describing headers, each self-describing header substantially immediately preceding an associated user file and including predetermined information about that user file;

a table-of-contents following a last one of the user files the, table-of-contents containing information representing positions of the self-describing headers; and

multiple frame markers, each including;

a predetermined recognition pattern;

the managed filename;

a sequence indicator representing a sequence of the frame marker relative to other frame markers associated with the managed filename; and

a next-frame locator containing information representing a position of a next frame marker;

wherein the frame markers are placed at a beginning of the managed file, at an end of the table-of-contents, and within the substantially contiguous arrangement;

wherein a final one of the frame markers includes indicia identifying the frame marker as the final one and additionally includes information representing a position of the table-of-contents;

the method comprising;

locating a first one of the frame markers by running a read sensor past the recording medium to scan for the recognition pattern;

finding the final frame marker by repeatedly;

reading a next-frame locator of the frame where the read sensor is positioned, determining a position of the next frame marker using the read next-frame locator, advancing the read sensor to the determined position of the next frame marker, and reading the next frame marker to determine whether this is the final frame marker;

in response to finding the final frame marker;

reading from the final frame marker the information representing the position of the table-of-contents; and

positioning the read sensor at the position of the table-of-contents and reading the table-of-contents including the information representing the positions of the self-describing headers.

37. The data storage subsystem of claim 36, the digital data processing means further constructing the database, by:

using the information read from the table-of-contents to determine, for each user file in the managed file, the user file'"'"'s length and the user file'"'"'s starting position within the managed file relative to other user files; and

writing to the database data associating each user file with its length, its offset, and the managed file.

38. An article of manufacture comprising:

a data storage medium;

machine-readable digital data tangibly embodied by the data storage medium the data including;

a managed file, having a managed filename, the managed file comprising multiple user files stored in a substantially contiguous arrangement;

multiple self-describing headers each self-describing header substantially immediately preceding an associated user file and including predetermined information about that user file;

a table-of-contents following a last one of the user files, the table-of-contents containing information representing positions of the self-describing headers; and

multiple frame markers, each including;

a predetermined recognition pattern;

the managed filename;

a sequence indicator representing a sequence of the frame marker relative to other frame markers associated with the managed filename;

a next-frame locator containing information representing a position of a next frame marker;

wherein the frame markers are placed at a beginning of the managed file, at an end of the table-of-contents and within the substantially contiguous arrangement; and

wherein a final one of the frame markers includes indicia identifying the frame marker as the final one and additionally includes information representing a position of the table-of-contents.

39. The article of claim 38, the medium comprising magnetic tape.

40. The article of claim 38, the medium comprising one or more magnetic disk surfaces.

41. The article of claim 38, the storing of the user files, self-describing headers, table-of-contents, and frame markers being performed in an order comprising:

(a) storing a first one of the frame markers;

(b) storing a self-describing header adjacent to the frame marker most recently stored and storing a user file adjacent to the self-describing header most recently stored, the user file or self-describing header being interrupted by one or more intervening frame markers;

(c) repeating step (b) until all user files have been stored, and then;

storing the table-of-contents substantially adjacent to the user file most recently stored; and

storing the final frame marker substantially adjacent to the table-of-contents.

42. The article of claim 38, the positions of the self-describing headers comprising offsets from a predetermined storage position.

43. The article of claim 38, the next-frame locator comprising an address of the next frame marker.

44. The article of claim 38, the next-frame locator comprising an offset from a predetermined point on the data storage medium to the next frame marker.

45. The article of claim 38, the next-frame locator of each frame marker comprising a length of storage space between that frame marker and the next frame marker.

46. An article of manufacture, prepared by a process comprising:

forming a digital data storage medium;

storing multiple user files upon the medium in substantially contiguous arrangement, the user files forming a managed file having a managed filename;

storing multiple self-describing headers upon the medium, each self-describing header substantially immediately preceding an associated user file and including predetermined information about that user file;

storing a table-of-contents upon the medium following a last one of the user files, the table-of-contents containing information representing positions of the self-describing headers; and

storing multiple frame markers upon the medium, each including;

a predetermined recognition pattern;

the managed filename; and

a sequence indicator representing a sequence of the frame marker relative to other frame markers associated with the managed filename;

a next-frame locator containing information representing a position of a next frame marker;

wherein the frame markers are placed at a beginning of the managed file, at an end of the table-of-contents, and within the substantially contiguous arrangement; and

wherein a final one of the frame markers includes indicia identifying the frame marker as the final one and additionally includes information representing a position of the table-of-contents.

47. The article of claim 46, the storing of the user files, self-describing headers, table-of-contents, and frame markers being performed in an order comprising:

(a) storing a first one of the frame markers;

(b) storing a self-describing header adjacent to the frame marker most recently stored and storing a user file adjacent to the self-describing header most recently stored, the user file or self-describing header being interrupted by frame markers,

(c) repeating step (b) until all user files have been stored, and then;

storing the table-of-contents substantially adjacent to the user file most recently stored; and

storing the final frame marker substantially adjacent to the table-of-contents.

48. The article of claim 46, the positions of the self-describing headers comprising offsets from a predetermined storage position.

49. The article of claim 46, the next-frame locator comprising an address of the next frame marker.

50. The article of claim 46, the next-frame locator comprising an offset from a predetermined point on the data storage medium to the next frame marker.

51. The article of claim 46, the next-frame locator of each frame marker comprising a length of storage space between that frame marker and the next frame marker.

52. An article of manufacture, prepared by a process comprising:

forming a digital data storage medium;

storing data on the medium, comprising;

(a) receiving multiple user files;

(b) storing a first managed file, having a first managed filename, comprising;

(1) generating and storing a first frame marker, the frame marker comprising;

a predetermined recognition pattern;

the first managed filename;

a next-frame locator indicating a location of a second frame marker; and

a sequence number of the first frame marker;

(2) generating and storing a self-describing header including predetermined information about a next one of the user files;

(3) storing the next user file and any intermittent frame markers that occur within the next user file in accordance with a prescribed frame marker pattern;

(4) repeating steps (2) and (3) for each received user file received until a predetermined condition is satisfied, and thereupon;

generating and storing a table-of-contents substantially adjacent a last one of the stored user files; and

storing a frame trailer substantialiy adjacent the table-of-content, the frame trailer containing information representing a storage position of the table-of-contents.