Space reclamation system and method for use in connection with tape logging system

• US 5,778,394 A
• Filed: 12/23/1996
• Issued: 07/07/1998
• Est. Priority Date: 12/23/1996
• Status: Expired due to Term

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Galtzur, Sharon, Ish-Shalom, Ariel J.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): JUNG, DAVID YIUK
• Application Number:
  US08/771,818
• Time in Patent Office: 561 Days
• Field of Search: 707/1-10, 707/100, 707/200, 707/202, 707/205, 395/182.04, 364/243.41, 364/246.6, 364/944.2, 364/961.2
• US Class Current: 711/162
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1456 Hardware arrangements for backup
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99956 File allocation

Abstract

A digital data processing system comprises a host information generating device, a mass storage subsystem, and a back-up information storage subsystem. The host information generating device generates information and provides it to the mass storage subsystem for storage. The mass storage subsystem receives the generated information from the host information generating device and transfers the generated information to the storage element for storage, and further transfers the generated information to the back-up information storage subsystem. The back-up information storage subsystem receives and stores the generated information from the mass storage subsystem'"'"'s control element. The back-up information storage subsystem includes a filter/buffer module, a tape log module and a reconstruction module. The filter/buffer module filters and buffers the information received from the mass storage subsystem and provides the buffered information to the tape log module for storage. The tape log module stores the information received from the filter/buffer module in logging fashion on tape cartridges. The filter/buffer module filters the information received from the mass storage subsystem so as to reduce the amount of information to be logged, so that, if the host changes the information while it is being buffered, the filter/buffer module will provide only the most recent information to the tape log module for storage. If a failure occurs in the mass storage subsystem, the reconstruction module can reconstruct the information that was on the failed device using the stored information from the tape log module and the buffered information.

Claims

1. A valid data item update retrieval and storage subsystem for copying valid ones of a plurality of data item updates serially recorded on a source storage medium, onto a target storage medium, each data item update having a data item identifier which is one of a set of data item identifier values, the valid data item update retrieval and recording arrangement comprising:

A. a storage medium directory including a series of directory entries each identifying, for a corresponding one of the series of data item updates recorded on said source storage medium, the data item identifier associated with said corresponding one of the series of data item updates;

B. a data item identifier flag set comprising a plurality of data item identifier flags, each associated with a data item identifier, each flag having a valid condition indicating that the source storage medium has a valid data item update associated with the respective data item identifier flag'"'"'s associated data item identifier stored thereon, and at least one other condition;

C. a valid data item update identifier for using the storage medium directory and said data item identifier flag set to identify a set of valid data item updates on said source storage medium, the valid data item update identifier scanning the directory entries in said directory in reverse in reverse order and, for each directory entry, determining whether the data item identifier flag associated with the data item identifier contained in the directory entry indicates that the source cartridge has a valid data item update associated with the respective flag'"'"'s associated data item identifier stored thereon and, if so, determining that the data item update associated with the directory entry is a valid data item update;

D. a valid data item update transfer control for providing valid ones of the data item updates as identified by said valid data item update identifier from the source storage medium for storage on the target storage medium.

2. A valid data item update retrieval and storage subsystem as defined in claim 1 in which the valid data item update identifier further condition the one of the data item identifier flags associated with the data item identifier to said at least one other condition when it determines that the data item update associated with the directory entry is a valid data item update.

3. A valid data item update retrieval and storage subsystem as defined in claim 2 in which said valid data item update identifier includes:

A. a directory entry selector for selecting a directory entry;

B. a validity determination generation element for using the data item identifier flag associated with the data item identifier identified by the selected directory entry generate a validity indication indicating whether the selected directory entry is associated with a valid data item update;

C. a data item identifier flag conditioner responsive to the validity indication generated by the validity determination generation element indicating that the selected directory entry is associated with a valid data item update for conditioning the data item identifier flag associated with the data item identifier identified by the selected directory entry to said at least one other condition; and

D. an iteration control element for controlling the directory entry selector element, said validity determination generation element and said data item identifier flag conditioner through a series of iterations.

4. A valid data item update retrieval and storage subsystem as defined in claim 3 in which said iteration control element enables said directory entry selector to, in each of a series of iterations, select the one of the directory entries which precedes the directory entry selected during the preceding iteration.

5. A valid data item update retrieval and storage subsystem as defined in claim 4 in which said iteration control element enables said directory entry selector to, in a first iteration, select the last directory entry in the storage medium directory.

6. A valid data item update retrieval and storage subsystem as defined in claim 3 in which said iteration control element terminates iterations after the iteration in which the directory entry selector selects the first directory entry in the storage medium directory.

7. A valid data item update retrieval and storage subsystem as defined in claim 1 further comprising a data item update storage control for controlling storage of valid data item updates provided by said valid data item update transfer control on the target storage medium.

8. A valid data item update retrieval and storage subsystem as defined in claim 7 in which said data item update storage control further controls storage of data item updates provided by a data item update source on the target storage medium.

9. A valid data item update retrieval and storage subsystem as defined in claim 8, the target storage medium having associated therewith a target storage medium data item identifier flag set comprising a plurality of target storage medium data item identifier flags, each associated with a data item identifier, the data item update storage control conditioning the target storage medium data item identifier flags in response to the storage of data item updates on the target storage medium.

10. A valid data item update retrieval and storage subsystem as defined in claim 9 in which each target storage medium data item identifier flag has having a valid condition and at least one other condition, the data item update storage control conditioning the target storage medium data item identifier flags associated with data item identifiers for data item updates received from the data item update source and stored on said target storage medium to the valid condition.

11. A valid data item update retrieval and storage subsystem as defined in claim 10, the valid data item update retrieval and storage subsystem being used in a system comprising at least one other storage medium having associated therewith a data item identifier flag set comprising a plurality of data item identifier flags, each associated with a data item identifier, each data item identifier flag having a valid condition indicating that the other storage medium has a valid data item update associated with the respective data item identifier flag'"'"'s associated data item identifier stored thereon, and at least one other condition, the data item update storage control further conditioning the data item identifier flag of the data item identifier flag set associated with the other storage medium to said other condition for each target storage medium data item identifier flag which has the valid condition.

12. A valid data item update retrieval and storage subsystem as defined in claim 9 in which each target storage medium data item identifier flag has has a valid condition and at least one other condition, the data item update storage control conditioning the target storage medium data item identifier flags associated with data item identifiers for data item updates received from the data item update source and stored on said target storage medium to the valid condition.

13. A valid data item update retrieval and storage subsystem as defined in claim 12 in which said data item update storage control further selectively conditions the target storage medium data item identifier flags associated with data item identifiers for data item updates received from the source storage medium to one of the valid condition or the other condition.

14. A valid data item update retrieval and storage subsystem as defined in claim 13, the data item update storage control conditioning the target storage medium data item identifier flags associated with data item identifiers for valid data item updates received from the source storage medium to the valid condition.

15. A valid data item update retrieval and storage subsystem as defined in claim 1, further comprising a data item update storage control for controlling storage of successive data item updates on said target storage medium, the data item update storage control maintaining a storage medium directory for said target storage medium, the data item update storage control providing an entry for each data item update stored on said trget storage medium including the data item identifier, so that the successive entries in the target storage medium'"'"'s storage medium directory identify the successive data item identifiers associated with successive data item updates stored on the target storage medium.

16. A valid data item update retrieval and storage subsystem as defined in claim 15 in which each entry of said target storage medium'"'"'s storage medium directory further includes an invalid flag having an invalid conditin and at least one other condition, the condition of the invalid flag being controlled by said data item update storage control.

17. A valid data item update retrieval and storage subsystem as defined in claim 16, the valid data item update identifier and the valid data item update transfer control operating during a space reclamation operation in which valid data item updates are copied from the source storage medium to the target medium, the data item update storage control during the space reclamation operation maintaining an auxiliary data item identifier flag set comprising a plurality of auxiliary data item identifier flags, each associated with a data item identifier, each flag having a plurality of conditions, the data item update storage control controlling the condition of the invalid flag of selected ones of the entries of said target storage medium'"'"'s storage medium directory in relation to the condition of the auxiliary data item identifier flag asociated with the data item identifier of the respective entries.

18. A valid data item update retrieval and storage subsystem as defined in claim 17, in which said data item update storage control further controls storage of data item updates provided by a data item update source, each being associated with a said data item identifier, on the target storage medium, the data item update storage control including:

A. an auxiliary data item identifier flag conditioner for, during a said space reclamation operation, conditioning the auxiliary data item identifier flag assocaited with the data item identifier of each data item update provided by said data item update source to a predetermined condition; and

B. a target storage medium directory entry generator for generating an entry for the target storage medium'"'"'s storage medium directory, the target storage mdeium directory entry generator conditioning the entry'"'"'s invalid flag to an invalid condition if the data item update stored on the target storage medium was provided by the valid data item update transfer control and the auxiliary data item identifier flag associated with the data item identifier of the data item update had predetermined condition.

19. A method of copying valid ones of a plurality of data item updates serially recorded on a source storage medium, onto a target storage medium, each data item update having a data item identifier which is one of a set of data item identifier values, a set of said valid data item updates for storing on a valid data item update storage medium, the valid data item update retrieval and recording arrangement comprising:

A. providing a storage medium directory including a series of directory entries each identifying, for a corresponding one of the series of data item updates recorded on said source storage medium, the data item identifier associated with said corresponding one of the series of data item updates;

B. providing a data item identifier flag set comprising a plurality of data item identifier flags, each associated with a data item identifier, each flag having a valid condition indicating that the source storage medium has a valid data item update associated with the respective data item identifier flag'"'"'s associated data item identifier stored thereon, and at least one other condition;

C. for using the storage medium directory and said data item identifier flag set to identify a set of valid data item updates on said source storage medium, the valid data item update identifier scanning the directory entries in said directory in reverse in reverse order and, for each directory entry, determining whether the data item identifier flag associated with the data item identifier contained in the directory entry indicates that the source cartridge has a valid data item update associated with the respective flag'"'"'s associated data item identifier stored thereon and, if so, determining that the data item update associated with the directory entry is a valid data item update;

D. providing valid ones of the data item updates as identified by said valid data item update identifier from the source storage medium for storage on the target storage medium.

20. A method as defined in claim 19 in which the valid data item update identification step further includes the step of conditioning the one of the data item identifier flags associated with the data item identifier to said at least one other condition when it determines that the data item update associated with the directory entry is a valid data item update.

21. A method as defined in claim 20 in which said valid data item update identification step includes the steps of iteratively:

A. selecting a directory entry;

B. using the data item identifier flag associated with the data item identifier identified by the selected directory entry generate a validity indication indicating whether the selected directory entry is associated with a valid data item update; and

C. conditioning the data item identifier flag associated with the data item identifier identified by the selected directory entry to said at least one other condition in response to the validity indication indicating that the selected directory entry is associated with a valid data item update.

22. A method as defined in claim 21 in which, during the directory entry selection step, in each iteration the one of the directory entries is selected which precedes the directory entry selected during the preceding iteration.

23. A method as defined in claim 22 in which, during the directory entry selection step of a first iteration, the last directory entry in the storage medium directory is selected.

24. A method as defined in claim 21 in which iterations are terminated after the iteration in which the first directory entry in the storage medium directory is selected during the directory entry selection step.

25. A method as defined in claim 19 further comprising the step of controlling storage of valid data item updates provided by said valid data item update transfer control on the target storage medium.

26. A method as defined in claim 25 in which, during the data item update storage step, data item updates provided by a data item update source are also stored on the target storage medium.

27. A method as defined in claim 26, the target storage medium having associated therewith a target storage medium data item identifier flag set comprising a plurality of target storage medium data item identifier flags, each associated with a data item identifier, the data item update storage step including the step of conditioning the target storage medium data item identifier flags in response to the storage of data item updates on the target storage medium.

28. A method as defined in claim 27 in which each target storage medium data item identifier flag has having a valid condition and at least one other condition, the data item update storage step including the step of conditioning the target storage medium data item identifier flags associated with data item identifiers for data item updates received from the data item update source and stored on said target storage medium to the valid condition.

29. A method as defined in claim 28, the method being used in a system comprising at least one other storage medium having associated therewith a data item identifier flag set comprising a plurality of data item identifier flags, each associated with a data item identifier, each data item identifier flag having a valid condition indicating that the other storage medium has a valid data item update associated with the respective data item identifier flag'"'"'s associated data item identifier stored thereon, and at least one other condition, the data item update storage step further including the step of conditioning the data item identifier flag of the data item identifier flag set associated with the other storage medium to said other condition for each target storage medium data item identifier flag which has the valid condition.

30. A method as defined in claim 27 in which each target storage medium data item identifier flag has has a valid condition and at least one other condition, the data item update storage step further including the step of conditioning the the target storage medium data item identifier flags associated with data item identifiers for data item updates received from the data item update source and stored on said target storage medium to the valid condition.

31. A method as defined in claim 30 in which said data item update storage step further includes the step of selectively conditioning the target storage medium data item identifier flags associated with data item identifiers for data item updates received from the source storage medium to one of the valid condition or the other condition.

32. A method as defined in claim 31, the data item update storage step including the step of conditioning the target storage medium data item identifier flags associated with data item identifiers for valid data item updates received from the source storage medium to the valid condition.

33. A method as defined in claim 19, further comprising the step of storing successive data item updates on said target storage medium, the data item update storage step maintaining a storage medium directory for said target storage medium, the data item update storage step including the step of providing an entry for each data item update stored on said target storage medium including the data item identifier, so that the successive entries in the target storage medium'"'"'s storage medium directory identify the successive data item identifiers associated with successive data item updates stored on the target storage medium.

34. A method as defined in claim 33 in which each entry of said target storage medium'"'"'s storage medium directory further includes an invalid flag having an invalid condition and at least one other condition, the data item update storage step including the step of conditioning the invalid flag.

35. A method as defined in claim 34, the valid data item update identification step and the valid data item update transfer step being performed during a space reclamation operation in which valid data item updates are copied from the source storage medium to the target storage medium, the data item update storage step including the step of, during the space reclamation operation, maintaining an auxiliary data item identifier flag set comprising a plurality of auxiliary data item identifier flags, each associated with a data item identifier, each flag having a plurality of conditions, the data item update storage step including the step of controlling the condition of the invalid flag of selected ones of the entries of said target storage medium'"'"'s storage medium directory in relation to the condition of the auxiliary data item identifier flag associated with the data item identifier of the respective entries.

36. A method as defined in claim 35, in which said data item update storage step further includes the step of storing of data item updates provided by a data item update source, each being associated with a said data item identifier, on the target storage medium, the data item update storage step further including the steps of:

A. during a said space reclamation operation, conditioning the auxiliary data item identifier flag associated with the data item identifier of each data item update provided by said data item update source to a predetermined condition; and

B. generating an entry for the target storage medium'"'"'s storage medium directory, the target storage medium directory entry generator conditioning the entry'"'"'s invalid flag to an invalid condition if the data item update stored on the target storage medium was provided by the valid data item update transfer control and the auxiliary data item identifier flag associated with the data item identifier of the data item update had predetermined condition.

37. A valid data item update retrieval and storage subsystem for copying valid ones of a plurality of data item updates serially recorded on a source storage medium, onto a target storage medium, each data item update having a data item identifier which is one of a set of data item identifier values, a set of said valid data item updates for storing on a valid data item update storage medium, the valid data item update retrieval and recording arrangement comprising:

A. a digital data processor; and

B. a control subsystem for controlling the processor, the control subsystem comprising;

i. a storage medium directory including a series of directory entries each identifying, for a corresponding one of the series of data item updates recorded on said source storage medium, the data item identifier associated with said corresponding one of the series of data item updates;

ii. a data item identifier flag set module for enabling the processor to maintain a data item identifier flag set comprising a plurality of data item identifier flags, each associated with a data item identifier, each flag having a valid condition indicating that the source storage medium has a valid data item update associated with the respective data item identifier flag'"'"'s associated data item identifier stored thereon, and at least one other condition;

iii. a valid data item update identifier use the storage medium directory and said data item identifier flag set to identify a set of valid data item updates on said source storage medium, the valid data item update identifier scanning the directory entries in said directory in reverse in reverse order and, for each directory entry, determining whether the data item identifier flag associated with the data item identifier contained in the directory entry indicates that the source cartridge has a valid data item update associated with the respective flag'"'"'s associated data item identifier stored thereon and, if so, determining that the data item update associated with the directory entry is a valid data item update;

iv. a valid data item update transfer control for enabling the processor to provide valid ones of the data item updates as identified by said valid data item update identifier from the source storage medium for storage on the target storage medium.

38. A valid data item update retrieval and storage subsystem as defined in claim 37 in which the valid data item update identifier module further enables the processor to condition the one of the data item identifier flags associated with the data item identifier to said at least one other condition when it determines that the data item update associated with the directory entry is a valid data item update.

39. A valid data item update retrieval and storage subsystem as defined in claim 38 in which said valid data item update identifier module includes:

A. a directory entry selector module for enabling said processor to select a directory entry;

B. a validity determination generation module for enabling said processor to use the data item identifier flag associated with the data item identifier identified by the selected directory entry generate a validity indication indicating whether the selected directory entry is associated with a valid data item update;

C. a data item identifier flag conditioner module for enabling the processor to, in response to the validity indication indicating that the selected directory entry is associated with a valid data item update, condition the data item identifier flag associated with the data item identifier identified by the selected directory entry to said at least one other condition; and

D. an iteration control module for controlling processor to process the directory entry selector module, said validity determination generation module and said data item identifier flag conditioner module through a series of iterations.

40. A valid data item update retrieval and storage subsystem as defined in claim 39 in which said iteration control module enables said processor to, when processing the directory entry selector in each iteration, select the one of the directory entries which precedes the directory entry selected during the preceding iteration.

41. A valid data item update retrieval and storage subsystem as defined in claim 40 in which said iteration control module enables said processor to, when processing said directory entry selector in a first iteration, select the last directory entry in the storage medium directory.

42. A valid data item update retrieval and storage subsystem as defined in claim 39 in which said iteration control module enables said processor to terminate iterations after the iteration in which, during the directory entry selection step, the first directory entry in the storage medium directory is selected.

43. A valid data item update retrieval and storage subsystem as defined in claim 37 further comprising a data item update storage control module for enabling said processor to control storage of valid data item updates provided by said valid data item update transfer control on the target storage medium.

44. A valid data item update retrieval and storage subsystem as defined in claim 43 in which said data item update storage control module further enables said processor to control storage of data item updates provided by a data item update source on the target storage medium.

45. A valid data item update retrieval and storage subsystem as defined in claim 44, the target storage medium having associated therewith a target storage medium data item identifier flag set comprising a plurality of target storage medium data item identifier flags, each associated with a data item identifier, the data item update storage control module further enabling said processor to condition the target storage medium data item identifier flags in response to the storage of data item updates on the target storage medium.

46. A valid data item update retrieval and storage subsystem as defined in claim 45 in which each target storage medium data item identifier flag has having a valid condition and at least one other condition, the data item update storage control module enabling the processor to condition the target storage medium data item identifier flags associated with data item identifiers for data item updates received from the data item update source and stored on said target storage medium to the valid condition.

47. A valid data item update retrieval and storage subsystem as defined in claim 46, the valid data item update retrieval and storage subsystem being used in a system comprising at least one other storage medium having associated therewith a data item identifier flag set comprising a plurality of data item identifier flags, each associated with a data item identifier, each data item identifier flag having a valid condition indicating that the other storage medium has a valid data item update associated with the respective data item identifier flag'"'"'s associated data item identifier stored thereon, and at least one other condition, the data item update storage control module further enabling said processor to condition the data item identifier flag of the data item identifier flag set associated with the other storage medium to said other condition for each target storage medium data item identifier flag which has the valid condition.

48. A valid data item update retrieval and storage subsystem as defined in claim 47 in which each target storage medium data item identifier flag has has a valid condition and at least one other condition, the data item update storage control module enabling the processor to condition the target storage medium data item identifier flags associated with data item identifiers for data item updates received from the data item update source and stored on said target storage medium to the valid condition.

49. A valid data item update retrieval and storage subsystem as defined in claim 48 in which said data item update storage control module further enabling the processor to selectively condition the target storage medium data item identifier flags associated with data item identifiers for data item updates received from the source storage medium to one of the valid condition or the other condition.

50. A valid data item update retrieval and storage subsystem as defined in claim 49, the data item update storage control module enabling the processor to condition the target storage medium data item identifier flags associated with data item identifiers for valid data item updates received from the source storage medium to the valid condition.

51. A valid data item update retrieval and storage subsystem as defined in claim 37, further comprising a data item update storage control module for enabling said processor to (i) control storage of successive data item updates on said target storage medium, (ii) enable the maintaining a storage medium directory for said target storage medium, and (iii) provide an entry for each data item update stored on said target storage medium including the data item identifier, so that the successive entries in the target storage medium'"'"'s storage medium directory identify the successive data item identifiers associated with successive data item updates stored on the target storage medium.

52. A valid data item update retrieval and storage subsystem as defined in claim 51 in which each entry of said target storage medium'"'"'s storage medium directory further includes an invalid flag having an invalid condition and at least one other condition, the data item update storage control module enabling the processor to condition of the invalid flag.

53. A valid data item update retrieval and storage subsystem as defined in claim 52, the valid data item update identifier and the valid data item update transfer control module controlling said processor during a space reclamation operation in which valid data item updates are copied from the source storage medium to the target medium, the data item update storage control module enabling said processor to, during the space reclamation operation, maintain an auxiliary data item identifier flag set comprising a plurality of auxiliary data item identifier flags, each associated with a data item identifier, each flag having a plurality of conditions, the data item update storage control module further controlling the processor to condition of the invalid flag of selected ones of the entries of said target storage medium'"'"'s storage medium directory in relation to the condition of the auxiliary data item identifier flag associated with the data item identifier of the respective entries.

54. A valid data item update retrieval and storage subsystem as defined in claim 53, in which said data item update storage control further controls storage of data item updates provided by a data item update source, each being associated with a said data item identifier, on the target storage medium, the data item update storage control module including:

A. an auxiliary data item identifier flag conditioning module for, during a said space reclamation operation, enabling said processor to condition the auxiliary data item identifier flag associated with the data item identifier of each data item update provided by said data item update source to a predetermined condition; and

B. a target storage medium directory entry generation module for controlling said processor to generate an entry for the target storage medium'"'"'s storage medium directory, the target storage medium directory entry generation module enabling said processor to condition the entry'"'"'s invalid flag to an invalid condition if the data item update stored on the target storage medium was provided by the valid data item update transfer control and the auxiliary data item identifier flag associated with the data item identifier of the data item update had predetermined condition.

55. A control subsystem for use in connection with a processor to form a valid data item update retrieval and storage subsystem for copying valid ones of a plurality of data item updates serially recorded on a source storage medium, onto a target storage medium, each data item update having a data item identifier which is one of a set of data item identifier values, a set of said valid data item updates for storing on a valid data item update storage medium, the control subsystem comprising:

A. a storage medium directory including a series of directory entries each identifying, for a corresponding one of the series of data item updates recorded on said source storage medium, the data item identifier associated with said corresponding one of the series of data item updates;

B. a data item identifier flag set module for enabling the processor to maintain a data item identifier flag set comprising a plurality of data item identifier flags, each associated with a data item identifier, each flag having a valid condition indicating that the source storage medium has a valid data item update associated with the respective data item identifier flag'"'"'s associated data item identifier stored thereon, and at least one other condition;

C. a valid data item update identifier use the storage medium directory and said data item identifier flag set to identify a set of valid data item updates on said source storage medium, the valid data item update identifier scanning the directory entries in said directory in reverse in reverse order and, for each directory entry, determining whether the data item identifier flag associated with the data item identifier contained in the directory entry indicates that the source cartridge has a valid data item update associated with the respective flag'"'"'s associated data item identifier stored thereon and, if so, determining that the data item update associated with the directory entry is a valid data item update;

D. a valid data item update transfer control for enabling the processor to provide valid ones of the data item updates as identified by said valid data item update identifier from the source storage medium for storage on the target storage medium.

56. A control subsystem as defined in claim 55 in which the valid data item update identifier module further enables the processor to condition the one of the data item identifier flags associated with the data item identifier to said at least one other condition when it determines that the data item update associated with the directory entry is a valid data item update.

57. A control subsystem as defined in claim 56 in which said valid data item update identifier module includes:

A. a directory entry selector module for enabling said processor to select a directory entry;

B. a validity determination generation module for enabling said processor to use the data item identifier flag associated with the data item identifier identified by the selected directory entry generate a validity indication indicating whether the selected directory entry is associated with a valid data item update;

C. a data item identifier flag conditioner module for enabling the processor to, in response to the validity indication indicating that the selected directory entry is associated with a valid data item update, condition the data item identifier flag associated with the data item identifier identified by the selected directory entry to said at least one other condition; and

D. an iteration control module for controlling processor to process the directory entry selector module, said validity determination generation module and said data item identifier flag conditioner module through a series of iterations.

58. A control subsystem as defined in claim 57 in which said iteration control module enables said processor to, when processing the directory entry selector in each iteration, select the one of the directory entries which precedes the directory entry selected during the preceding iteration.

59. A control subsystem as defined in claim 58 in which said iteration control module enables said processor to, when processing said directory entry selector in a first iteration, select the last directory entry in the storage medium directory.

60. A control subsystem as defined in claim 58 in which said iteration control module enables said processor to terminate iterations after the iteration in which, during the directory entry selection step, the first directory entry in the storage medium directory is selected.

61. A control subsystem as defined in claim 55 further comprising a data item update storage control module for enabling said processor to control storage of valid data item updates provided by said valid data item update transfer control on the target storage medium.

62. A control subsystem as defined in claim 61 in which said data item update storage control module further enables said processor to control storage of data item updates provided by a data item update source on the target storage medium.

63. A control subsystem as defined in claim 62, the target storage medium having associated therewith a target storage medium data item identifier flag set comprising a plurality of target storage medium data item identifier flags, each associated with a data item identifier, the data item update storage control module further enabling said processor to condition the target storage medium data item identifier flags in response to the storage of data item updates on the target storage medium.

64. A control subsystem as defined in claim 63 in which each target storage medium data item identifier flag has having a valid condition and at least one other condition, the data item update storage control module enabling the processor to condition the target storage medium data item identifier flags associated with data item identifiers for data item updates received from the data item update source and stored on said target storage medium to the valid condition.

65. A control subsystem as defined in claim 64, the valid data item update retrieval and storage subsystem being used in a system comprising at least one other storage medium having associated therewith a data item identifier flag set comprising a plurality of data item identifier flags, each associated with a data item identifier, each data item identifier flag having a valid condition indicating that the other storage medium has a valid data item update associated with the respective data item identifier flag'"'"'s associated data item identifier stored thereon, and at least one other condition, the data item update storage control module further enabling said processor to condition the data item identifier flag of the data item identifier flag set associated with the other storage medium to said other condition for each target storage medium data item identifier flag which has the valid condition.

66. A control subsystem as defined in claim 65 in which each target storage medium data item identifier flag has has a valid condition and at least one other condition, the data item update storage control module enabling the processor to condition the target storage medium data item identifier flags associated with data item identifiers for data item updates received from the data item update source and stored on said target storage medium to the valid condition.

67. A control subsystem as defined in claim 66 in which said data item update storage control module further enabling the processor to selectively condition the target storage medium data item identifier flags associated with data item identifiers for data item updates received from the source storage medium to one of the valid condition or the other condition.

68. A control subsystem as defined in claim 67, the data item update storage control module enabling the processor to condition the target storage medium data item identifier flags associated with data item identifiers for valid data item updates received from the source storage medium to the valid condition.

69. A control subsystem as defined in claim 65, further comprising a data item update storage control module for enabling said processor to (i) control storage of successive data item updates on said target storage medium, (ii) enable the maintaining a storage medium directory for said target storage medium, and (iii) provide an entry for each data item update stored on said target storage medium including the data item identifier, so that the successive entries in the target storage medium'"'"'s storage medium directory identify the successive data item identifiers associated with successive data item updates stored on the target storage medium.

70. A control subsystem as defined in claim 69 in which each entry of said target storage medium'"'"'s storage medium directory further includes an invalid flag having an invalid condition and at least one other condition, the data item update storage control module enabling the processor to condition of the invalid flag.

71. A control subsystem as defined in claim 70, the valid data item update identifier and the valid data item update transfer control module controlling said processor during a space reclamation operation in which valid data item updates are copied from the source storage medium to the target medium, the data item update storage control module enabling said processor to, during the space reclamation operation, maintain an auxiliary data item identifier flag set comprising a plurality of auxiliary data item identifier flags, each associated with a data item identifier, each flag having a plurality of conditions, the data item update storage control module further controlling the processor to condition of the invalid flag of selected ones of the entries of said target storage medium'"'"'s storage medium directory in relation to the condition of the auxiliary data item identifier flag associated with the data item identifier of the respective entries.

72. A control subsystem as defined in claim 71, in which said data item update storage control further controls storage of data item updates provided by a data item update source, each being associated with a said data item identifier, on the target storage medium, the data item update storage control module including:

A. an auxiliary data item identifier flag conditioning module for, during a said space reclamation operation, enabling said processor to condition the auxiliary data item identifier flag associated with the data item identifier of each data item update provided by said data item update source to a predetermined condition; and

B. a target storage medium directory entry generation module for controlling said processor to generate an entry for the target storage medium'"'"'s storage medium directory, the target storage medium directory entry generation module enabling said processor to condition the entry'"'"'s invalid flag to an invalid condition if the data item update stored on the target storage medium was provided by the valid data item update transfer control and the auxiliary data item identifier flag associated with the data item identifier of the data item update had predetermined condition.