Back-up data storage facility incorporating filtering to select data items to be backed up

Claim 2

A digital data processing system comprising a host information generating device, a mass storage subsystem and a back-up information storage subsystem, A. the host information generating device generating information in the form of data item updates and providing the data item updates to the mass storage subsystem for storage; B. the mass storage subsystem including a storage element and a control element, the control element receiving the data item updates from the host information generating device and transferring the data item updates to the storage element for storage, the control element further transferring the data item updates to the back-up information storage subsystem; C. the back-up information storage subsystem receiving the data item updates from the mass storage subsystem's control element, and filtering the data item updates to select ones of the data item updates for back-up storage.

Claim 3

A digital data processing system as defined in claim 1 in which said mass storage subsystem further includes a back-up information storage subsystem interface, the control element enabling the back-up information storage subsystem interface to transfer the data item updates to the back-up information storage subsystem.

Claim 4

A digital data processing system as defined in claim 2 in which said control element provides a pointer to a location in said storage element containing said generated information, the back-up information storage subsystem interface using the pointer during transfer of the generated information from the storage location pointed to by the pointer.

Claim 5

A digital data processing system as defined in claim 3 in which said back-up information storage subsystem interface retrieves data item updates from the location identified by said pointer for transfer to the back-up information storage subsystem.

Claim 6

A digital data processing system as defined in claim 1 in which said back-up information storage subsystem comprises: A. a back-up storage element; and B. a filter for filtering data item updates provided by said mass storage subsystem, the filter providing selected ones of said data item updates to said back-up storage element for storage.

Claim 7

A digital data processing system as defined in claim 5, the filter comprising: A. a filter queue including a plurality of queue elements, each queue element including a data item update received from said data item update source; B. a data item identifier table for storing, for the data item identification values associated with data item updates in the filter queue, a pointer to the one of the queue elements containing the most recently received data item update for the particular data item identification value; and C. a data item update selection element for selectively coupling respective ones of the queue elements of the filter queue whose data item updates for use by the downstream data item utilization subsystem, the data item update selection element selectively coupling the one of the queue elements whose data item update is pointed to by one of said pointers associated with the data item identification value contained in said one of said queue elements.

Claim 8

A digital data processing system as defined in claim 6 in which said queue elements comprising said filter queue define a series of queue elements extending from a head queue element, the data item update selection element selectively coupling the head queue element to said downstream data item utilization subsystem if the data item identifier table stores, associated with the one of said data item identification values associated with the data item included in said head queue element, a pointer to the head queue element.

Claim 9

A digital data processing system as defined in claim 7 in which said data item identifier table includes a plurality of pointer entries, at least some of said pointer entries containing a said data item identification value and an associated one of said pointers, the data item update selection element coupling the head queue element to said downstream data item utilization subsystem if the pointer that is contained in the one of the data item entries in said data item identifier table whose data item identification value corresponds to the data item identification value of said head queue element's data item, points to the head queue element.

Claim 10

A digital data processing system as defined in claim 7 further including a data item update input element for receiving data item updates and for generating queue elements including said data item updates and linking the queue elements to said filter queue.

Claim 11

A digital data processing system as defined in claim 9, said filter further including a free queue comprising a plurality of free queue elements, said data item update input element generating each said queue element for said filter queue by retrieving one of said free queue elements from said free queue, loading a said data item update received thereby into the retrieved free queue element thereby to form a queue element for said filter queue and linking the queue element to said filter queue.

Claim 12

A digital data processing system as defined in claim 9 in which said data item update input element, for the data item update contained in a said queue element that it links to said filter queue, further enables said data item identifier table to associate a said data item identification value that is associated with the data item update to point to the queue element.

Claim 13

A digital data processing system as defined in claim 11 in which said data item identifier table includes a plurality of pointer entries, at least some of said pointer entries containing a said data item identification value and an associated one of said pointers, the data item update input element providing a pointer for one of said pointer entries containing the data item identification value associated with the data item update associated with a said queue element.

Claim 14

A digital data processing system as defined in claim 12 in which said data item identifier table is in the form of a hash table comprising a plurality of said pointer entries, said data item update input element processing the data item identification value associated with the one of said data item updates for which it is generating a queue element in accordance with a hashing function to generate a data item identifier table entry pointer, the data item update input element using the data item identifier table entry pointer to identify one of said pointer entries in the data item identifier table in which it will provide a said pointer to the queue element containing the data item update.

Claim 15

A digital data processing system as defined in claim 13 in which each said pointer entry includes a data item identifier value field and a pointer field, said data item update input element providing the data item identification value associated with the data item update for which it is generating a queue element in the data item identifier value field of the identified one of said pointer entries, and the pointer to the queue element containing the data item update in the pointer field of the identified one of said pointer entries.

Claim 16

A digital data processing system as defined in claim 13 in which the data item update input element, when it generates a pointer to a queue element that it is generating, further determines whether the identified pointer entry contains a queue element pointer, and if so generates an overflow entry for the pointer to the queue entry and links it to the identified pointer entry in said data item identifier table.

Claim 17

A digital data processing system as defined in claim 9 the data item update input element, when generating a queue element, aggregates one or more data item updates to form each queue element.

Claim 18

A digital data processing system as defined in claim 5 in which the back-up storage element includes a serial storage medium for serially storing a series of data item updates received from the mass storage subsystem.

Claim 19

A digital data processing system as defined in claim 17 further comprising a valid data item update retrieval and recording arrangement for copying valid ones of a plurality of data item updates serially recorded on a source serial storage medium, onto a target serial 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 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.

Claim 20

A digital data processing system as defined in claim 18 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.

Claim 21

A digital data processing system as defined in claim 19 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.

Claim 22

A digital data processing system as defined in claim 20 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.

Claim 23

A digital data processing system as defined in claim 21 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.

Claim 24

A digital data processing system as defined in claim 20 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.

Claim 25

A digital data processing system as defined in claim 18 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.

Claim 26

A digital data processing system as defined in claim 24 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.

Claim 27

A digital data processing system as defined in claim 25, 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.

Claim 28

A digital data processing system as defined in claim 26 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.

Claim 29

A digital data processing system as defined in claim 27, 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 meidum data item identifier flag which has the valid condition.

Claim 30

A digital data processing system as defined in claim 28 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.

Claim 31

A digital data processing system as defined in claim 29 in which said data item update storage control farther 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.

Claim 32

A digital data processing system as defined in claim 30, 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.

Claim 33

A digital data processing system as defined in claim 18, 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 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.

Claim 34

A digital data processing system as defined in claim 32 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 condition of the invalid flag being controlled by said data item update storage control.

Claim 35

A digital data processing system as defined in claim 33, 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 associated with the data item identifier of the respective entries.

Claim 36

A digital data processing system as defined in claim 34, 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 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.

Claim 37

A digital data processing system as defined in claim 6 further including a reconstruction element for selectively reconstructing a set of valid data item updates from the data item updates stored on said storage medium.

Claim 38

A digital data processing system as defined in claim 36, the data item reconstruction element during a reconstruction operation, reconstructing information stored on a back-up information storage subsystem associated with at least one protected volume, the back-up information storage subsystem including a plurality of storage media each associated with one of a plurality of sets, the information associated with said at least one protected volume being stored on storage media associated with one of said sets, said data item reconstruction element during said reconstruction operation retrieving in parallel information from a plurality of said storage media associated with the one of said sets on which information associated with the at least one protected volume is stored, to obtain the information which is associated with said protected volume.

Claim 39

A digital data processing system as defined in claim 37 in which said back-up information storage subsystem comprises a plurality of drives for storing information on and retrieving information from said storage media, the number of drives being related to the number of sets, the back-up information storage subsystem normally utilizing one of said drives in connection with storage of information onto storage media associated with an associated one of said sets.

Claim 40

A digital data processing system as defined in claim 38 in which, during a reconstruction operation in connection with said at least one protected volume, said data item reconstruction element enables at least a plurality of said drives to be used in connection with retrieval of information from storage media associated with the set on which information associated with the at least one protected volume is stored.

Claim 41

A digital data processing system as defined in claim 37 in which said information comprises a plurality of data item updates each associated with one of a plurality of data item identifiers, the data item reconstruction element comprising: A. a valid data item update identifier for identifying valid ones of the data item updates associated with the protected volume stored on the storage media of the set on which information associated with the at least one protected volume is stored; and B. a valid data item retriever for retrieving from said storage media the ones of the data item updates identified by said valid data item update identifier as being valid.

Claim 42

A digital data processing system as defined in claim 40 in which the valid data item retriever retrieves valid data item updates from a plurality of storage media in parallel.

Claim 43

A digital data processing system as defined in claim 40 in which said valid data item update identifier during a reconstruction operation in connection with said at least one protected volume processes (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, a data item identifier associated with said corresponding one of the series of data item updates, and (ii) 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, in connection with each of said storage media of the set on which information associated with the at least one protected volume is stored, thereby to identify valid ones of the data item updates associated with the protected volume stored on the storage media of the set on which information associated with the at least one protected volume is stored.

Claim 44

A digital data processing system as defined in claim 42 in which said valid data item update identifier, for each storage medium in the set on which information associated with the at least one protected volume is stored, scans the directory entries in said directory in reverse in reverse order and, for each directory entry, determines whether the data item identifier flag associated with the data item identifier contained in the directory entry indicates that the storage medium has a valid data item update associated with the respective flag's associated data item identifier stored thereon and, if so, determines that the data item update associated with the directory entry is a valid data item update.

Claim 45

A digital data processing system as defined in claim 43 in which the valid data item update identifier further conditions 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.

Claim 46

A digital data processing system as defined in claim 44 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.

Claim 47

A digital data processing system as defined in claim 45 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.

Claim 48

A digital data processing system as defined in claim 46 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.

Claim 49

A digital data processing system as defined in claim 45 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.

Claim 50

A digital data processing system as defined in claim 37, said back-up information storage subsystem further including a buffer for buffering information prior to being stored on said storage media, the data item reconstruction element during a said reconstruction operation further retrieving information from said buffer associated with the at least one protected volume to obtain the information which is associated with said protected volume and merging the information retrieved from said buffer with the information retrieved from said storage media.

Claim 51

A digital data processing system as defined in claim 49, in which said information comprises a plurality of data item updates each associated with one of a plurality of data item identifiers, the buffer comprising (i) a plurality of storage locations each for storing a data item update and (ii) a data item identifier table for storing for storing, for the data item identification values associated with data item updates in the buffer, a pointer to the one of the storage locations containing a valid one of data item updates for the particular data item identification value, the data item reconstruction element retrieving data from storage locations identified by pointers in said data item identifier table and merging the data item retrieved therefrom with the information retrieved from said storage media.

Claim 54

A digital data processing system comprising a host information generating device, a mass storage subsystem and a back-up information storage subsystem, A. the host information generating device generating dated item updates and providing the data item updates to the mass storage subsystem for storage; B. the mass storage subsystem including a storage element and a control element, the control element receiving the data item updates from the host information generating device and transferring the data item updates to the storage element for storage, the storage element storing the data item updates in a first predetermined logical storage organization, the control element further transferring the data item updates to the back-up information storage subsystem; C. the back-up information storage subsystem including a backup storage control element and a backup storage element, the backup storage control element receiving the data item updates from the mass storage subsystem's control element and storing the data item updates in a backup storage element in a second predetermined logical storage organization that is independent of the first predetermined logical storage organization.

Claim 55

A digital data processing system comprising a host information generating device, a mass storage subsystem and a back-up information storage subsystem, A. the host information generating device generating dated item updates and providing the data item updates to the mass storage subsystem for storage; B. the mass storage subsystem including a storage element and a control element, the control element receiving the data item updates from the host information generating device and transferring the data item updates to the storage element for storage, the storage element storing the data item updates in a first predetermined logical storage organization, the control element further transferring the data item updates to the back-up information storage subsystem; C. the back-up information storage subsystem including a backup storage control element and a backup storage element, the backup storage control element receiving the data item updates from the mass storage subsystem's control element and storing the data item updates in a backup storage element in a second predetermined logical storage organization that is independent of the first predetermined logical storage organization.

Claim 56

A digital data processing system as defined in claim 52 in which the mass storage subsystem's storage element is a random access storage element.

Claim 57

A digital data processing system as defined in claim 52 in which the back-up information storage element is a linear access storage element.