Method and system for tracking files pending processing

• US 5,590,318 A
• Filed: 11/18/1993
• Issued: 12/31/1996
• Est. Priority Date: 11/18/1993
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Berkowitz, Brian T., Zbikowski, Mark, Ferguson, Robert I.
• Primary Examiner(s): Kulik, Paul V.
• Application Number:
  US08/154,582
• Time in Patent Office: 1,139 Days
• Field of Search: 395/600, 395/575, 395/180, 395/182.03, 395/182.13, 395/182.17, 395/182.18, 371/16.5, 371/29.1
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A portion of a first storage stores identifying information of files to be processed by a computer. The files are stored in a second storage, with each file having associated identifying information which identifies the file, and each file including an update sequence value which indicates an order in which the file is to be processed by the computer. A threshold value is provided which is set equal to a largest update sequence value retrieved from the file that have been processed by the computer. In response to a loss of the file identifiers stored in the portion of the first storage, the file identifier for each file whose update sequence value is beyond the threshold value is stored in the portion of the first storage.

Claims

1. A computer implemented method of restoring data lost from a volatile storage, the computer including a second storage for storing a plurality of files, each file including associated file identifying information which identifies the file, the computer including a processor for processing the files, the method comprising the steps of:

providing update sequence values for files, each update sequence value indicating an order in which the file is to be processed relative to the other files;

storing identifying information for files to be processed by the computer in a portion of the volatile storage;

selecting a next file to be processed by examining the identifying information and update sequence value of files to be processed that are stored in the portion of the volatile storage;

processing the next file to be processed;

providing a threshold value equal to a largest update sequence value for the files that have been processed by the processor; and

in response to a loss of the file identifiers stored in the portion of the volatile storage, storing in the portion of the volatile storage the file identifier for each file whose update sequence value surpasses the threshold value.

2. The method of claim 1, further comprising the step of providing a monotonically increasing counter whose value is incremented each time a file is created or changed and wherein the step of providing an update sequence value includes assigning to a file an update sequence value that is the current value of the monotonically increasing counter.

3. The method of claim 1, further comprising the step of providing a monotonically decreasing counter whose value is decremented each time a file is created or changed and wherein the step of providing an update sequence value includes assigning to a file an update sequence value that is a current value of the monotonically decreasing counter.

4. The method of claim 1, further including the steps of:

providing an upper limit value which indicates a maximum value that can be assigned to the update sequence value without first increasing the upper limit value;

providing a delta value;

in response to a loss of the update sequence value setting the update sequence value to a value greater than the upper limit value; and

setting the upper limit value to a summation of a current value of the upper limit value and the delta value.

5. A computer implemented method of restoring data lost from a volatile storage, the computer including a second storage for storing a plurality of files, the computer including a processor for processing the files, the method comprising the steps of:

providing a monotonically increasing counter whose value is incremented each time a file is created or changed;

assigning to files a current value of the monotonically increasing counter as a sequence value;

maintaining a list of files awaiting processing in the first storage;

rebuilding the list of files in the volatile storage in the event that the list of files is lost, by examining the values assigned to the files and adding to the list, files having sequence values greater than a sequence value of a last file to be processed before the loss occurred.

6. A computer implemented method of restoring data lost from a volatile storage, the data including file identifiers which identify files stored on the computer, the computer including a processor for processing the files, each file including a file identifier which identifies the file, the method comprising the steps of:

changing contents of a selected file;

assigning an update sequence value for the selected file as a current value of a monotonically increasing counter, said update sequence value indicating an order in which the selected file will be processed relative to the other files;

storing the update sequence value in the selected file;

storing the selected file with the update sequence value in a second storage, the second storage being arranged such that when the volatile storage loses data, the second storage does not lose data;

storing the file identifier identifying the selected file in the volatile storage;

processing by the processor at least one of the files listed in the volatile storage;

determining a largest processed update sequence value from the files that have been processed by the computer;

in response to a loss of the file identifiers stored in the volatile storage, determining if the update sequence value stored in the selected file is greater than the largest processed update sequence value; and

in response to a determination that the update sequence value stored in the selected file is greater than the largest processed update sequence value, storing in the volatile storage the file identifier for the selected file.

7. The method of claim 6, further including the steps of:

providing an upper limit value which indicates a maximum value that can be assigned to the update sequence value without first increasing the upper limit value;

providing a delta value;

in response to a loss of the update sequence value, setting the update sequence value to a value greater than the upper limit value; and

setting the upper limit value to a summation of the upper limit value and the delta value.

8. A computer implemented method of restoring data lost from a volatile storage, the data including file identifiers which identify files stored on the computer, the computer including a processor for processing the files, each file including identifying information which identifies the file, the method comprising the steps of:

selecting a file;

determining an update sequence value which indicates an order in which the selected file will be processed relative to the other files;

storing the identifying information and the update sequence value of the selected file in a second storage, the second storage being arranged such that when the first storage loses data, the second storage does not lose data;

processing by the processor at least one of the files listed in the volatile storage;

determining a most extreme processed update sequence value from the files that have been processed by the computer;

in response to a loss of identifying information for files stored in the volatile storage, determining if the update sequence value of the selected file surpasses the most extreme processed update sequence value; and

in response to a determination that the update sequence value of the selected file surpasses the most extreme processed update sequence value, storing in the volatile storage the file identifier of the selected file.

9. The method of claim 8, further including the steps of:

providing an upper limit value which indicates a maximum value that can be assigned to the update sequence value without first increasing the upper limit value;

providing a delta value which indicates a value by which to increase the upper limit value;

in response to a loss of the update sequence value setting the update sequence value to a value greater than the upper limit value; and

setting the upper limit value to a summation of the upper limit value and the delta value.

10. The method of claim 8 wherein the step of determining an update sequence value further comprises the step of providing a monotonically increasing counter whose value is incremented each time a file is created or changed.

11. The method of claim 8 wherein the step of determining an update sequence value further comprises the step of providing a monotonically decreasing counter whose value is decremented each time a file is created or changed.

12. A method in a computer system for automatically generating an index representing data contained in a file, the computer system including a volatile storage, a processor for processing said method, and a second storage for storing at least one file comprising data, the method comprising the steps of:

providing identifying information for at least one of the files which identifies the file and an update sequence value indicating an order, relative to the other files, in which the file was processed by the computer;

providing a portion of the volatile storage for storing the identifying information of files awaiting processing by the processor;

providing a threshold value equal to the largest update sequence value from the files that have been processed by the computer;

in response to a loss of the identifying information for files stored in the portion of the volatile storage, storing in the portion of the volatile storage the file identifier for each file whose update sequence value surpasses the threshold value;

selecting one of the file identifiers stored in the volatile storage;

retrieving the file indicated by the selected file identifier; and

automatically generating the index for the retrieved file from the data stored in the retrieved file.

13. The method of claim 12 wherein the index comprises at least a first and second data element, the first data element comprising a portion of the data from the retrieved file, and the second data element comprising a position of the portion of the data in the retrieved file, and wherein said step of automatically generating an index further comprising storing the portion of the data and the position of the portion of the data in the index.

14. The method of claim 12 wherein the index comprises at least a first and second data element, the first data element comprising a portion of the data from the retrieved file and the second data element comprising the identifying information of the file, and wherein said step of automatically generating an index further comprising storing the portion of the data and the identifying information in the index.

15. A computer system for processing a file, the file having at least one index representing data contained in the file, the computer system comprising:

a plurality of files stored in a second storage, each file having identifying information which identifies the file and each file including an update sequence value indicating an order in which the file was processed;

a portion of a volatile storage for storing identifying information for files to be processed by the computer;

a threshold value equal to a most extreme update sequence value from the files that have been processed by the computer;

in response to a loss of the identifying information for the files stored in the portion of the volatile storage, means for storing in the portion of the volatile storage the file identifying information for each file whose update sequence value is beyond the threshold value;

means for retrieving identifying information from the volatile storage;

means for retrieving the file indicated by the retrieved identifying information; and

means for automatically storing in the index for the retrieved file, data from the retrieved file in order to complete processing the file in a preferred manner.

16. The computer system of claim 15 wherein the index further comprising at least a first and second data element, the first data element comprising a portion of the data from the retrieved file, and the second data element comprising a position of the portion of the data in the retrieved file and wherein said means for automatically storing in the index further comprises storing the portion of the data and the position of the portion of the data in the index.

17. The computer system of claim 15 where the index further comprising at least a first and second data element, the first data element comprising a portion of the data from the retrieved file, and the second data element comprising identifying information, and wherein said means for automatically storing in the index further comprises storing the portion of the data and the identifying information in the index.