Hierarchical timestamps

• US 20070208839A1
• Filed: 03/06/2006
• Published: 09/06/2007
• Est. Priority Date: 03/06/2006
• Status: Active Grant

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Jackson, James, Veitch, Alistair, Voigt, Douglas, Reuter, James
• Granted Patent: US 7,644,308 B2
• Time in Patent Office: Days
• US Class Current: 709/223
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory

Abstract

Embodiments of the present invention are directed to digitally encoded hierarchical timestamps that are stored in computer readable mediums. The hierarchical timestamps of the present invention include a first field that stores a timestamp value and a second field that stores a processing-level indication that indicates the scope of the timestamp within a hierarchical processing system.

Claims

1. A method for preventing undesirable detection of time-stamp disparities during processing of timestamp-associated entities in a hierarchical processing system, the method comprising:

employing timestamps that include a processing-level indication, the processing-level indication in each timestamp reflecting a current scope of the timestamp within the hierarchical processing system; and

when processing of a timestamp-associated entity is completed with respect to the timestamp at a processing level, changing the processing-level indication in the timestamp associated with the entity.

2. The method of claim 1 wherein changing the processing-level indication in the timestamp associated with the entity further includes setting the processing-level indication to a lower value.

3. The method of claim 1 wherein changing the processing-level indication in the timestamp associated with the entity further includes setting the processing-level indication to a higher value.

4. The method of claim 1 further including:

at a given processing level, when checking for problems related to entities that can be identified based on timestamps associated with the entities, considering only timestamps within a processing scope, indicated by the processing level indications within the timestamps, that includes the given processing level.

5. The method of claim 4 wherein a timestamp having a processing-level indication equal to or less than the given processing level is within the processing scope of the given processing level.

6. The method of claim 4 wherein a timestamp having a processing-level indication equal to or greater than the given processing level is within the processing scope of the given processing level.

7. The method of claim 1 employed in a distributed storage system in which timestamps are associated with data blocks.

8. The method of claim 7

wherein the distributed storage system comprises interconnected storage-system components;

wherein the distributed storage system distributes data across storage-system components according to one or more redundancy schemes; and

wherein the hierarchical processing levels within each distributed storage system coordinate execution of data-access operations with respect to hierarchical levels of logical data entities.

9. Computer instructions stored within a computer-readable medium that implement the method of claim 1.

10. A distributed storage system comprising:

a number of storage-system components interconnected by one or more communications media;

hierarchical processing logic executed by each of the number of storage-system components, higher levels of the hierarchical processing logic coordinating distributed execution of data-access operations and lower levels of the hierarchical processing logic carrying out data-access within the storage-system components; and

hierarchical timestamps associated with data units stored within the storage-system components, each hierarchical timestamp including a processing-level indication that indicates the scope of the hierarchical timestamp within the hierarchical processing levels.

11. The distributed storage system of claim 10 wherein, when processing of a timestamp-associated data unit related to the associated timestamp is completed at a given processing level, the processing-level indication in the timestamp is changed by the hierarchical processing logic.

12. The distributed storage system of claim 11 wherein the processing-level indication is changed to a value lower than the given processing level.

13. The distributed storage system of claim 11 wherein the processing-level indication is changed to a value higher than the given processing level.

14. The distributed storage system of claim 10 wherein, when a processing level of the hierarchical processing logic checks for problems, related to data units, that can be identified based on timestamps associated with the data units, the hierarchical processing logic checks only for problems identified by timestamps within a processing scope, indicated by the processing level indications within the timestamps, that includes the processing level.

15. The distributed storage system of claim 14 wherein a timestamp having a processing-level indication equal to or less than the processing level is within the processing scope of the given processing level.

16. The distributed storage system of claim 14 wherein a timestamp having a processing-level indication equal to or greater than the processing level is within the processing scope of the given processing level.

17. The distributed storage system of claim 10

wherein the hierarchical processing logic distributes data across storage-system components according to one or more redundancy schemes;

and

wherein the hierarchical processing levels of the hierarchical processing logic within each distributed storage system coordinate execution of data-access operations with respect to hierarchical levels of logical data entities.

18. The distributed storage system of claim 10 wherein timestamps are associated with data blocks stored in internal storage components of the storage-system components of the distributed storage system.

19. The distributed storage system of claim 18 wherein a hierarchical processing level of the hierarchical processing logic within each distributed storage system compares timestamps of redundant copies of a data block stored within different storage-system components in order to detect data inconsistencies.

20. A digitally encoded hierarchical timestamp stored in a computer readable medium, the hierarchical timestamp comprising:

a first field that stores a timestamp value; and

a second field that stores a processing-level indication that indicates a scope of the timestamp within a hierarchical processing system.

21. The digitally encoded hierarchical timestamp of claim 20 wherein the timestamp value is one of:

a sequence number;

a logical time value; and

a time value.

22. A method for controlling a scope of processing levels in which entities associated with timestamps are processed in a hierarchical processing system with a number of processing levels, the method comprising:

providing a scope indication means for the timestamps associated with the entities; and

at a particular processing level,

processing only entities associated with timestamps, the processing-level-indication means for which indicate a scope that includes the particular processing level, and

following processing of a particular entity, directing the scope indication means for the timestamp associated with the particular entity to subsequently indicate a scope that does not include the particular processing level.