Maintaining an aggregate including active files in a storage pool in a random access medium

Provided are a method, system, and program for maintaining an aggregate including active files in a storage pool in a random access medium. An active-only storage pool is configured in a random access device. The active-only storage pool is intended to include only active files and not inactive versions of files. A plurality of files in the active-only storage pool are associated with a precursor aggregate in the active-only storage pool. One file associated with the precursor aggregate in the active only storage pool is deactivated to produce an inactive version of the deactivated file. The precursor aggregate is associated with the inactive version of the file in response to the deactivation. A determination is made of the inactive version of at least one file in the precursor aggregate. The determined inactive version of the at least one file is deleted from the active only storage pool.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to a method, system, and program for maintaining an aggregate including active files in a storage pool in a random access device.

2. Description of the Related Art

Storage management software maintains a repository for data by backing-up, archiving or migrating data from client nodes in a computer network. A storage management server stores data objects or files in one or more storage pools maintained in storage devices. The storage management server may use a database to track information about the stored files, including their location, status, policy information on the files, etc. The storage management software may also be used to restore data. The storage management software may maintain a hierarchy of storage devices, where a first level of the hierarchy includes the faster access devices, such as disk drives, storing more frequently used and accessed files. Lower levels in the hierarchy provide slower access storage devices, such as lower performance disk drives and tape drives, to store less frequently accessed or inactive data. One example of storage management software is the Tivoli® Storage Manager product marketed by International Business Machines Corporation (IBM®). (Tivoli and IBM are registered trademarks of IBM).

To improve data transfer performance, the storage management software may aggregate individual files in a storage pool, so that moving and copying operations may be performed with respect to an aggregate of files instead of single files. U.S. Pat. No. 6,098,074 describes an aggregation technique in which objects being stored are aggregated into a “managed file.” The objects may thereafter be tracked and moved as a single managed file within the storage hierarchy. When appropriate, individual objects can be processed individually such as for deletion or retrieval operations. The co-pending and commonly assigned patent application entitled “Method, System, And Program For Storing Data For Retrieval And Transfer”, having Ser. No. 10/766,576 and filed on Jan. 27, 2004, describes further techniques for managing files in aggregates.

As the amount of data users store in storage pools continues to increase, files and aggregates of files are increasingly migrated to lower levels in the storage hierarchy. Thus, data that may need to be restored may have been migrated to a slower access device, such as a tape storage media, which has a low restore performance. Further, to restore data from tape, the data may first be staged from tape to a hard disk drive pool and then restored from the hard disk drive.

Further improvements in data storage may be useful in a variety of applications.

SUMMARY

Provided are a method, system, and program for maintaining an aggregate including active files in a storage pool in a random access medium. An active-only storage pool is configured in a random access device. The active-only storage pool is intended to include only active files and not inactive versions of files. A plurality of files in the active-only storage pool are associated with a precursor aggregate in the active-only storage pool. One file associated with the precursor aggregate in the active only storage pool is deactivated to produce an inactive version of the deactivated file. The precursor aggregate is associated with the inactive version of the file in response to the deactivation. A determination is made of the inactive version of at least one file in the precursor aggregate. The determined inactive version of the at least one file is deleted from the active only storage pool.

In a further embodiment, the file is deactivated as a result of an update to the file. Updating the file produces an active version of the file in addition to the inactive version of the file. Indication of the association of the deleted inactive version of the at least one file with the precursor aggregate is removed. The precursor aggregate is associated with only the active version of files in response to removing the indication.

In a further embodiment, the files associated with the precursor aggregate are copied to an aggregate managed file in an additional storage pool before deleting the determined inactive version of the at least one file. The aggregate managed file maintains the inactive version of the at least one file deleted from the active only storage pool.

In a further embodiment, the files are written sequentially to the aggregate managed file and the aggregate managed file comprises a sequential file.

In a further embodiment, the additional storage pool is implemented in a sequential access device.

In a further embodiment, the precursor aggregate has a first identifier and the aggregate managed file has a second identifier. A data structure is provided having information on defined aggregates including an aggregate identifier and storage pool including the aggregate for each indicated aggregate. Indication is made in the information for the aggregate identified by one aggregate identifier whether the aggregate is a precursor aggregate comprising an association of files or an aggregate managed file in which files are written.

In a further embodiment, indicating in the data structure information that the aggregate is the precursor aggregate comprises indicating that the precursor aggregate has an aggregate size of zero. Indicating in the information that the aggregate is the aggregate managed file comprises indicating that the aggregate managed file has an aggregate size that is a cumulative size of the files written in the aggregate managed file.

In a further embodiment, the information for each aggregate in the data structure includes a logical size and an actual size. Indicating that the precursor aggregate has the aggregate size of zero comprises indicating that the actual size of the precursor aggregate is zero and indicating that the aggregate managed file has the aggregate size that is the cumulative size comprises indicating that the actual size of the aggregate managed file is the cumulative size. Indication is made in the information for the precursor aggregate and the aggregate managed file that the logical size is the cumulative size of the files associated with the precursor aggregate and written to the aggregate managed file, respectively.

In a further embodiment, the file is deactivated as a result of an update to the file. Updating the file produces an active version of the file in addition to the inactive version of the file. Information is added to the data structure for the updated file having a third identifier and indicating that the updated file is in the active-only storage pool.

In a further embodiment, the data structure comprises a first data structure. A second data structure has information on each file grouped in one aggregate including the aggregate identifier of the aggregate including the file. The aggregate identifier for the files associated with the precursor aggregate comprises the first identifier and the aggregate identifier for the files written to the aggregate managed file comprises the second identifier.

In a further embodiment, the information is deleted in the second data structure for the inactive version of the at least one file having the first identifier that was deleted from the active storage pool. The second data structure includes information on the inactive version of the at least one file having the second identifier maintained in the aggregate managed file.

In a further embodiment, the information for the files in the second data structure indicates an offset and file size of the file. Files associated with one precursor aggregate have an offset of zero and files included in one aggregate managed file have an offset at which the file is stored in the aggregate managed file.

DETAILED DESCRIPTION

FIG. 1illustrates a computing environment in which embodiments are implemented. A plurality of clients2a,2b. . .2n, storage devices4a,4b, and a storage management server6are in communication over a network8. The storage management server6may access storage devices4a,4bover the network8. Alternatively, a storage device may be attached directly to the storage management server6and accessed over a bus. The clients2a,2b. . .2ninclude client storage agents10a,10b. . .10nand the storage management server6includes storage management software12. The client storage agents10a,10b. . .10nand the storage management software12interact to manage the storage of files in storage pools14a,14bimplemented in the storage devices4a,4b. The storage management software12may maintain a storage hierarchy system in which storage pools14a,14bare defined to have level information, such that files at a higher level may be migrated to a lower level according to a hierarchical storage policy, e.g., to move less frequently accessed files to storage pools at a lower level in the hierarchy having slower access devices. The storage in the higher level may comprise faster access devices, such as hard disk drives, whereas the storage at lower levels may comprise slower access devices, such as slower hard disk drives, tape drives, etc. For instance, storage pools high in the hierarchy include more frequently or recently used data and are implemented in relatively faster access storage devices, whereas storage pools lower in the hierarchy may provide more long term storage of data and be implemented in a tape storage medium. In certain embodiments, the client storage agents10a,10b. . .10nmay access, backup, archive and restore data through the storage management software12, which manages access to files in the storage pools14a,14b. Further, the storage management software12may backup and archive data from the clients2a,2b,2c.

The storage management software12maintains information on the files in the storage pools, including file information16, aggregate information18, and storage pool information20. The information16,18, and20may be implemented in one or more database tables of a relational database or other suitable data structures known in the art. The file information16may comprise an inventory table having information on every file in the storage pools14a,14b, including client and policy information. The aggregate information18comprises information on aggregates defined in the storage pools14a,14b. A precursor aggregate comprises an association of files in the storage pools14a,14b, an aggregate managed file comprises a file or object in one storage pool in which one or more files are written and associated. Files grouped by a precursor aggregate are not stored in an aggregate managed file, but remain stored as separate files in the file system. An aggregate simplifies file movement operations (e.g., storage pool backup, restore, reclamation or movement to another pool which includes migration to another location within the hierarchy) because the storage management software12need only specify a data transfer operation with respect to an aggregate (precursor or aggregate managed file), and the storage management software12will then perform the requested operation with respect to the files grouped by the aggregate.

The storage pool information20contains information about where each managed file is stored in the storage hierarchy implemented in the storage pools14a,14b. The storage table contains an entry for each managed file.

A storage pool14a,14bmay be implemented in a random access device or as a sequential access storage pool. A sequential access storage pool may be implemented in a sequential access media, e.g., tape, or in a sequential file volume in a random access media. When data is stored sequentially in a sequential file volume in a random access device, the volume is a file in the underlying file system. Space from a deleted file in a sequential-access disk pool is recovered by consolidating valid data on a new file volume during a reclamation operation. In a random-access disk pool, space is allocated in random blocks, such that once a file is deleted from a random-access storage pool, the space is immediately available for use.

In one embodiment, a storage pool may be defined as an active only storage pool22, such that only active files are maintained in that storage pool22, not inactive files. An inactive file is any file that has been deactivated according to some criteria. For instance, a file may be considered inactive if it is updated, deleted or is a file whose age exceeds an aging policy. A file may be updated or deleted on a client system2a,2b. . .2n, and then when that update is supplied to the storage management server6, the deactivated file may be marked as inactive. A file may also be deactivated directly by the storage management software12. An update to a file results in both an active version of the file having the update and an inactive version of the pre-updated file.

The clients2a,2b. . .2nmay comprise a suitable computational device known in the art, such as a workstation, desktop computer, server, mainframe, hand held computer, telephony device, etc. The storage management server6may comprise a suitable server class machine. The network8may comprise a Local Area Network (LAN), Storage Area Network (SAN), Wide Area Network (WAN), wireless network, etc. The storage devices4a,4bmay be implemented in storage devices known in the art, such as one hard disk drive, a plurality of interconnected hard disk drives configured as Direct Access Storage Device (DASD), Redundant Array of Independent Disks (RAID), Just a Bunch of Disks (JBOD), etc., a tape device, an optical disk device, a non-volatile electronic memory device (e.g., Flash Disk), a tape library, etc. The storage devices4a,4bmay comprise random access devices, such as hard disk drives, electronic memory or storage, etc., where data may be written randomly to blocks in the storage device or sequential access devices where data must be written sequentially to the storage media, such as tape media.

FIG. 2illustrates an embodiment of file/aggregate information50maintained for every aggregate managed file and file outside of an aggregate managed file within a storage pool. The file/aggregate information50may be part of the aggregate information18. Each file/aggregate information50instance includes an identifier (ID)52of the file or aggregate managed file; a size54(e.g., byte length) of the file or aggregate, where an aggregate size is the size of all files included in the aggregate managed file; and a storage pool56identifying the storage pool14a,14b,22including the file or aggregate managed file. A precursor aggregate may have a size54of zero, indicating it is a logical entity and an aggregate managed file may have a size54including its actual size, which includes the cumulative size of all files written to the aggregate managed file. For entries50for files, as opposed to aggregates, an active status field58indicates whether the file is active or inactive.

FIG. 3illustrates an embodiment of aggregate information70maintained for every aggregate. The aggregate information70may be part of the aggregate information18. Each aggregate information70instance includes: an identifier72of the aggregate; an actual size74of the aggregate managed file or a value indicating that the aggregate is a precursor aggregate, such as zero (a precursor aggregate may not have an actual size because it comprises an association of files and is not an object storing files); a logical size76including the size of all files associated with that aggregate; and a number of files78grouped by the aggregate (precursor or managed file). An aggregate managed file may have a logical size76equal to the cumulative size of the files written to the aggregate managed file and a precursor aggregate has a logical size of the files associated with the precursor aggregate.

FIG. 4illustrates an embodiment of aggregate file information80maintained for every file associated with an aggregate, i.e., a precursor aggregate or included in one aggregate managed file. The aggregate file information80may be part of the file information16or the aggregate information18. Each aggregate file information80instance includes: a file identifier82, such as the file name and location; an aggregate identifier84indicating the aggregate (precursor or managed file) in which the file is grouped; an offset86indicating the byte offset from the beginning of the aggregate managed file at which the file starts; a length88of the file; and an active status90indicating whether the file is active or inactive. A file associated with a precursor aggregate may have an offset86of zero or some other value indicating that the file is associated with a precursor aggregate. A file associated with a precursor aggregate may have a length88equal to the byte length of the file.

FIG. 5illustrates an active-only storage pool94implemented as a random access device in one of the storage devices4a,4bincluding one precursor aggregate96having three files A, B, C. The files A, B, C may be stored at non-sequential or sequential locations in the storage pool94, and are shown as stored at non-sequential random locations. The active-only storage pool94may include additional precursor aggregates or aggregate managed files as well as files not included in an aggregate, such as large files that do not get aggregated. A file D is not associated with the precursor aggregate96.

FIG. 5further illustrates an active/inactive storage pool98in which data may be written sequentially and an aggregate managed file100in which files A, B, C are written sequentially. An active/inactive storage pool comprises either a copy storage pool or a primary storage pool. A copy storage pool is a secondary storage pool for receiving a copy of data from an active-only storage pool or maintaining a backup copy for disaster recovery. A primary storage pool contains both active and inactive files, and inactive files may be restored from the primary storage pool. The active/inactive storage pool98may be implemented in a sequential access media or in a sequential file volume in a random access media in which data is written sequentially. A sequential file volume comprises a file on a random access media, such as a hard disk drive, that is managed as a tape device where data is written sequentially. A storage pool can have multiple sequential file volumes including aggregate managed files. When the sequential file volume reaches a predefined size, then the sequential file volume is closed and a new sequential file volume is added to the storage pool to fill-up.

FIG. 6illustrates operations performed by the storage management software12to create a precursor aggregate96in the active-only storage pool94. The invocation of the storage management software12(at block100) to create a precursor aggregate may be initiated by one client storage agent10a,10b. . .10nor an administrator at the storage management server6. A file/aggregate information50(FIG. 2) instance is added (at block102) to the file information16identifying the precursor aggregate52being created, a size54indicating a precursor aggregate (e.g., 0), and an identifier in field56of the active-only storage pool94in which the precursor aggregate is created. For each file to associate with a precursor aggregate, an aggregate file information instance80(FIG. 4) is added (at block104) to the file16or aggregate18information identifying the file82associated with the precursor aggregate, the precursor aggregate ID84, an offset86of zero, a length88of the file, and a status90of the file being associated. The storage management software12further adds (at block106) an aggregate information instance70(FIG. 3) identifying the created precursor aggregate ID72, actual size74indicating a precursor aggregate (e.g., 0), a logical size76of the size of all files associated with the precursor aggregate and a number of files78associated with the precursor aggregate. When associating a new file with the precursor aggregate, the logical size76and number of files78would be updated to reflect the added file.

FIG. 7illustrates an embodiment of operations performed by the storage management software12to copy a precursor aggregate96from the active-only storage pool94to a target aggregate managed file100in an active/inactive storage pool98, which may comprise a sequential access device or sequential file. The operations ofFIG. 7may further apply to the copying of files not included in an aggregate, such as file D (FIG. 5). Upon initiating (at block150) the copy operation, the storage management software12creates (at block152) an aggregate managed file100in the active/inactive storage pool98and creates an aggregate information instance70(FIG. 3) for the aggregate managed file, initializing the aggregate ID72and other values, and creates a file/aggregate information instance50(FIG. 2) identifying the created aggregate managed file52and the active/inactive storage pool56. The files associated with the precursor aggregate96are copied (at block154) to the created aggregate managed file100in the active/inactive storage pool98in which the files are written sequentially. The storage management software12adds (at block156) an aggregate file information instance80(FIG. 4) for each file written to the aggregate100object including the aggregate managed file identifier84, the offset86at which the file was written, the length of the file88and the status90as inactive or active. Further, the size field54in the file aggregate information50and the actual size74, logical size78, and number of files78fields in the aggregate information70are updated to reflect the size of the aggregate managed file100including the number of files written thereto.

FIG. 8illustrates an embodiment of operations performed by the storage management software12to process (at block170) a deactivation of a file associated with one precursor aggregate96in the active-only storage pool94. As mentioned a file may be deactivated if the file is updated, producing both an active version having the update and an inactive version. Certain deactivations may produce only an inactive version of the file, such as if the file is deleted or the file's age exceeds a policy criteria. In response to the deactivation, the storage management software12indicates (at block172) the active status fields58,90in the file/aggregate information50and aggregate file information80of the deactivated file associated with the precursor aggregate96as inactive. If (at block174) the file was deactivated as a result of an update operation, then the active version is added (at block176) to the active-only storage pool by updating the file/aggregate information50to identify the file or aggregate and the active-only storage pool. This operation may involve adding a file/aggregate information instance50(FIG. 2) for the updated file and assigning a new ID52and indicating the size54and storage pool56including the updated file. At this point, the active-only storage pool94includes inactive and active versions of the updated file. Further, files not part of an aggregate may have their status field58in their file/aggregate information50updated to indicate inactive when they are updated. Yet further, the updated active file may be stored in an aggregate with other files and/or copied to other storage pools, such as the active/inactive storage pool98. If (at block174) the file was not deactivated in a manner that results in both an active and inactive version, then control ends.

FIG. 9illustrates an embodiment of operations implemented by the storage management software12to expire inactive files in the active-only storage pool94in a random access device. In certain embodiments, a copy of the precursor aggregate in the active/inactive storage pool (made according to the operations ofFIG. 7) occurs before inactive files are expired according to the operations ofFIG. 9. At block200, an operation is invoked to expire inactive files on one precursor aggregate96in the active-only storage pool94. This operation may be invoked periodically or in response to an event, such as an update to files in the active-only aggregate. For each file in the active-only storage pool94, a loop is performed at blocks202through216. Files in the active only storage pool94may be determined as those files whose file/aggregate information instances50(FIG. 2) indicate in field56the active-only storage pool. If (at block204) the file is active or inactive (which may be determined from status field58in the file/aggregate information50(FIG. 2) for the file being considered) and not migrated to the active/inactive storage pool98, then control proceeds (at block216) to consider a next file in the active-only storage pool94. If (at block204) the file is both inactive and migrated to the active/inactive storage pool98, then the file is deleted (at block206) from the active-only storage pool94and the file/aggregate information entry50(FIG. 2) for the deleted file identified in field56as in the active-only storage pool96is also removed (at block208). The aggregate file information entry80for the deleted file that is also maintained in the aggregate managed file100in the active/inactive storage pool98may remain because the copy of the inactive file removed from the active-only storage pool96is maintained in the active/inactive storage pool98.

If (at block210) the deleted file is not in a precursor aggregate, then control proceeds to block216to consider a next file in the active-only storage pool94. The storage management software12may determine that a removed file is in a precursor aggregate by determining whether there is an aggregate file information entry80for the removed file identifying the removed file as included in a precursor aggregate, which has an actual size74(FIG. 3) of zero. Otherwise, if (at block210) the removed file is in a precursor aggregate, then the aggregate file information entry80having the ID82of the file deleted from the active only storage pool that is associated with another aggregate (precursor or managed file), as indicated in field84, is updated (at block214) to indicate the status90to inactive. In this way, only the entry80for the file removed from the active-only storage pool94is removed, and not entries80for the file in other storage pools. Thus, during expiration, files having an inactive status are deleted from precursor aggregates in the active-only storage pool94, yet may remain as inactive files in other storage pools, such as the active/inactive storage pool98.

FIG. 10illustrates an example of storage pools and tables having information on the aggregates in the storage pools. An active only storage pool300, having an ID of “1”, is implemented in a random access media including three files A, B, C having IDs of100,200,300, respectively. These files A, B, C are grouped in a precursor aggregate302having an ID of400. Before updating files in the active-only storage pool300, a copy is made of the files associated with the precursor aggregate302to an aggregate managed file304, having an ID of500, in the active/inactive storage pool306, having an ID of “−1”. The active/inactive storage pool306may comprise a sequential access device or store files and aggregate managed files in a sequential file volume. File B600comprises an updated version of file B200associated with the precursor aggregate302. Any changes to files associated with the precursor aggregate302does not effect the copy of the files in the aggregate managed file304in the active/inactive storage pool306, other than changing the status of the copy of the files from active to inactive. File B may also be copied to the active/inactive storage pool306.

In one embodiment, the storage management software12maintains a file/aggregate information table310, an aggregate information table312, and an aggregate file information table314having information on the files and aggregates in the storage pools300and306. The file/aggregate information table310includes entries, such as entry50(FIG. 2), for each aggregate, including entries for precursor aggregate400and aggregate managed file500(having reference numbers302and304, respectively) that are in the storage pools identified as 1 and “−1” (having reference numbers300and306, respectively) and the updated file B having identifier600.

The aggregate file information table314includes entries, such as entry80(FIG. 4), for each file in the aggregates302and304. The files in the precursor aggregate302have offsets of zero and the files in the aggregate managed file304have offsets of their location in the aggregate managed file. InFIG. 10, the aggregate information312has information on the precursor aggregate302and the aggregate managed file304, including an actual size field of zero for precursor aggregate400indicating that the aggregate is a precursor. The table314further indicates whether the file is active, “Y” or active and “N” for inactive.

FIG. 11illustrates an example of storage pools and tables having information on the aggregates in the storage pools after expiration occurs with respect to the storage pool302inFIG. 10.FIG. 11shows storage pools300and306as inFIG. 10and precursor aggregate302in storage pool300and aggregate managed file304in storage pool306. However, in the active-only storage pool300, the updated file B was deleted from the precursor aggregate302by updating the information defining the precursor aggregate according to the operations ofFIG. 9. However, the inactive file B200remains in the aggregate managed file304(having ID500) in the active/inactive storage pool306. The updated file B600is also in the active-only storage pool300.

The updated file/aggregate information table322forFIG. 11includes the entries fromFIG. 10, with the entry for the inactive file B200removed from the active-only storage pool as a result of expiration, leaving only an entry for the updated file B600. The entry in the updated aggregate information table324for the precursor aggregate400is updated to include the new logical size of 20 to reflect that a file was removed. The entry in the aggregate file information table326for file B200in the precursor aggregate400is updated to indicate the inactive status. However, the length is set to 0 to indicate that that file B200is no longer included in the precursor aggregate96. In this embodiment, all inactive files are removed from the precursor aggregate96in the active-only storage pool94and the inactive file is maintained in the aggregate managed file304in the active/inactive storage pool306.

Described embodiments provide an active only storage pool implemented in a random access media, such that any files in a precursor aggregate in the active-only storage pool that become inactive as a result of an update or other deactivation are removed from the active only storage pool and precursor aggregate during an expiration operation. Further, by maintaining only active only files in a storage pool, the client may restore the active data faster from either the active-only storage pool or a backup copy of the precursor aggregate having active data, which may be on disk or tape. In this way, the active files may be streamed from the aggregate managed file on the tape or disk media. This allows the client to restore the active files faster, which the client is more likely to need than inactive files.

ADDITIONAL EMBODIMENT DETAILS

The described operations may be implemented as a method, apparatus or article of manufacture using standard programming and/or engineering techniques to produce software, firmware, hardware, or any combination thereof. The described operations may be implemented as code maintained in a “computer readable medium”, where a processor may read and execute the code from the computer readable medium. A computer readable medium may comprise media such as magnetic storage medium (e.g., hard disk drives, floppy disks, tape, etc.), optical storage (CD-ROMs, DVDs, optical disks, etc.), volatile and non-volatile memory devices (e.g., EEPROMs, ROMs, PROMs, RAMs, DRAMs, SRAMs, Flash Memory, firmware, programmable logic, etc.), etc. The code implementing the described operations may further be implemented in hardware logic (e.g., an integrated circuit chip, Programmable Gate Array (PGA), Application Specific Integrated Circuit (ASIC), etc.). Still further, the code implementing the described operations may be implemented in “transmission signals”, where transmission signals may propagate through space or through a transmission media, such as an optical fiber, copper wire, etc. The transmission signals in which the code or logic is encoded may further comprise a wireless signal, satellite transmission, radio waves, infrared signals, Bluetooth, etc. The transmission signals in which the code or logic is encoded is capable of being transmitted by a transmitting station and received by a receiving station, where the code or logic encoded in the transmission signal may be decoded and stored in hardware or a computer readable medium at the receiving and transmitting stations or devices. An “article of manufacture” comprises computer readable medium, hardware logic, and/or transmission signals in which code may be implemented. Of course, those skilled in the art will recognize that many modifications may be made to this configuration without departing from the scope of the present invention, and that the article of manufacture may comprise suitable information bearing medium known in the art.

In described embodiments, the aggregate managed files in which files are written were contained in a sequential access media, such as a sequential disk or tape. In an alternative embodiment, the described operations may apply to an aggregate managed file in a random access media.

Further, when a reference letter, such as “a”, “b”, or “n” is used to denote a certain number of items, the reference “a”, “b” or “n” used with different elements may indicate the same or different number of such elements.

FIGS. 2,3,4,10, and11show information maintained in a certain format. In alternative embodiments, the information shown inFIGS. 2,3,4,10, and11may be maintained in alternative data structures and formats, and in different combinations.