System and method for determining the age of objects in the presence of unreliable clocks

• US 8,423,517 B2
• Filed: 02/07/2011
• Issued: 04/16/2013
• Est. Priority Date: 02/09/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kesselman, Alexander, Drobychev, Alexandre, Ford, Daniel J.
• Primary Examiner(s): Casanova, Jorge A
• Application Number:
  US13/022,551
• Publication Number:
  US 20110196901A1
• Time in Patent Office: 799 Days
• Field of Search: 707/689, 707/746, 707/813
• US Class Current: 707/689
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/2477 Temporal data queries

Abstract

A system and method for determining an age of an object is provided. A first index for a timestamp entry in a sequence of timestamps corresponding to a time at which an object was created is identified. At least one subsequence of timestamps from the sequence of timestamps having indexes for entries in the sequence of timestamps that are between the first index in the sequence of timestamps and a last index for a last timestamp entry in the sequence of timestamps is identified, wherein the at least one subsequence of timestamps conforms to a function of a time interval between storage of consecutive current timestamps reported by clock of the computer system. Timestamps from the sequence of timestamps that are not included in the at least one subsequence of timestamps are removed. An age of the object is determined based on the at least one subsequence of timestamps.

Claims

1. A computer-implemented method for determining an age of an object, comprising:

at a computer system including one or more processors and memory storing one or more programs for execution by the one or more processors;

identifying a first index for a timestamp entry in a sequence of timestamps corresponding to a time at which an object was created, wherein the sequence of timestamps is generated by periodically storing a current timestamp reported by a clock of the computer system into the sequence of timestamps;

identifying at least one subsequence of timestamps from the sequence of timestamps having indexes for entries in the sequence of timestamps that are between the first index in the sequence of timestamps and a last index for a last timestamp entry in the sequence of timestamps, wherein the at least one subsequence of timestamps conforms to a function of a time interval between storage of consecutive current timestamps reported by clock of the computer system, wherein identifying the at least one subsequence of timestamps from the sequence of timestamps includes;

identifying a longest increasing subsequence of timestamps having indexes for timestamp entries that are between the first index in the sequence of timestamps and the last index for the last timestamp entry in the sequence of timestamps; and

identifying a plurality of consecutive sequences of timestamps from the longest increasing subsequence of timestamps, wherein a respective consecutive sequence of timestamps includes at least a predetermined number of timestamps, and wherein the time interval between consecutive timestamps in the respective consecutive sequence of timestamps is less than a predetermined factor of the time interval between storage of consecutive current timestamps reported by the clock of the computer system; and

determining an age of the object based on the at least one subsequence of timestamps.

2. The method of claim 1, wherein determining the age of the object based on the at least one subsequence of timestamps includes:

for each subsequence of timestamps in the at least one subsequence of timestamps, calculating a time interval between a last timestamp in the subsequence of timestamps and a first time stamp in the subsequence of timestamps; and

determining the age of the object as a sum of the time intervals.

3. The method of claim 1, wherein determining the age of the object based on the at least one subsequence of timestamps includes determining the age of the object as a time interval between a last timestamp of a last subsequence of timestamps in the at least one subsequence of timestamps and a timestamp in the timestamp entry having the first index in the sequence of timestamps.

4. The method of claim 1, further comprising performing a garbage collection operation if the age of the object is greater than a predetermined threshold.

5. The method of claim 1, further comprising performing a garbage collection operation if the age of the object is greater than a predetermined threshold and if metadata is not associated with the object.

6. The method of claim 1, further comprising performing a garbage collection operation if the age of the object is greater than a predetermined threshold and if the object has not been accessed within a predetermined time period.

7. The method of claim 1, wherein the object is stored in a distributed storage system.

8. The method of claim 1, further comprising:

removing timestamps from the sequence of timestamps that are not included in the at least one subsequence of timestamps.

9. The method of claim 1, wherein clock of the computer system is an unreliable clock.

10. A system for determining an age of an object, comprising:

one or more processors;

memory; and

one or more programs stored in the memory, the one or more programs comprising instructions to;

identify a first index for a timestamp entry in a sequence of timestamps corresponding to a time at which an object was created, wherein the sequence of timestamps is generated by periodically storing a current timestamp reported by a clock of the computer system into the sequence of timestamps;

identify at least one subsequence of timestamps from the sequence of timestamps having indexes for entries in the sequence of timestamps that are between the first index in the sequence of timestamps and a last index for a last timestamp entry in the sequence of timestamps, wherein the at least one subsequence of timestamps conforms to a function of a time interval between storage of consecutive current timestamps reported by clock of the computer system, wherein the instructions to identify the at least one subsequence of timestamps from the sequence of timestamps include instructions to;

identify a longest increasing subsequence of timestamps having indexes for timestamp entries that are between the first index in the sequence of timestamps and the last index for the last timestamp entry in the sequence of timestamps; and

identify a plurality of consecutive sequences of timestamps from the longest increasing subsequence of timestamps, wherein a respective consecutive sequence of timestamps includes at least a predetermined number of timestamps, and wherein the time interval between consecutive timestamps in the respective consecutive sequence of timestamps is less than a predetermined factor of the time interval between storage of consecutive current timestamps reported by the clock of the computer system; and

determine an age of the object based on the at least one subsequence of timestamps.

11. The system of claim 10, wherein the instructions to determine the age of the object based on the at least one subsequence of timestamps include instructions to:

for each subsequence of timestamps in the at least one subsequence of timestamps, calculate a time interval between a last timestamp in the subsequence of timestamps and a first time stamp in the subsequence of timestamps; and

determine the age of the object as a sum of the time intervals.

12. The system of claim 10, wherein the instructions to determine the age of the object based on the at least one subsequence of timestamps include instructions to determine the age of the object as a time interval between a last timestamp of a last subsequence of timestamps in the at least one subsequence of timestamps and a timestamp in the timestamp entry having the first index in the sequence of timestamps.

13. The system of claim 10, further comprising instructions to perform a garbage collection operation if the age of the object is greater than a predetermined threshold.

14. The system of claim 10, further comprising instructions to perform a garbage collection operation if the age of the object is greater than a predetermined threshold and if metadata is not associated with the object.

15. The system of claim 10, further comprising instructions to perform a garbage collection operation if the age of the object is greater than a predetermined threshold and if the object has not been accessed within a predetermined time period.

16. The system of claim 10, wherein the object is stored in a distributed storage system.

17. The system of claim 10, further comprising instructions to remove timestamps from the sequence of timestamps that are not included in the at least one subsequence of timestamp.

18. The system of claim 10, wherein clock of the computer system is an unreliable clock.

19. A non-transitory computer readable storage medium storing one or more programs configured for execution by a computer, the one or more programs comprising instructions to:

identify a first index for a timestamp entry in a sequence of timestamps corresponding to a time at which an object was created, wherein the sequence of timestamps is generated by periodically storing a current timestamp reported by a clock of the computer system into the sequence of timestamps;

identify at least one subsequence of timestamps from the sequence of timestamps having indexes for entries in the sequence of timestamps that are between the first index in the sequence of timestamps and a last index for a last timestamp entry in the sequence of timestamps, wherein the at least one subsequence of timestamps conforms to a function of a time interval between storage of consecutive current timestamps reported by clock of the computer system, wherein the instructions to identify the at least one subsequence of timestamps from the sequence of timestamps include instructions to;

identify a longest increasing subsequence of timestamps having indexes for timestamp entries that are between the first index in the sequence of timestamps and the last index for the last timestamp entry in the sequence of timestamps; and

identify a plurality of consecutive sequences of timestamps from the longest increasing subsequence of timestamps, wherein a respective consecutive sequence of timestamps includes at least a predetermined number of timestamps, and wherein the time interval between consecutive timestamps in the respective consecutive sequence of timestamps is less than a predetermined factor of the time interval between storage of consecutive current timestamps reported by the clock of the computer system; and

determine an age of the object based on the at least one subsequence of timestamps.

20. The computer readable storage medium of claim 19, wherein the instructions to determine the age of the object based on the at least one subsequence of timestamps include instructions to:

for each subsequence of timestamps in the at least one subsequence of timestamps, calculate a time interval between a last timestamp in the subsequence of timestamps and a first time stamp in the subsequence of timestamps; and

determine the age of the object as a sum of the time intervals.

21. The computer readable storage medium of claim 19, wherein the instructions to determine the age of the object based on the at least one subsequence of timestamps include instructions to determine the age of the object as a time interval between a last timestamp of a last subsequence of timestamps in the at least one subsequence of timestamps and a timestamp in the timestamp entry having the first index in the sequence of timestamps.

22. The computer readable storage medium of claim 19, further comprising instructions to perform a garbage collection operation if the age of the object is greater than a predetermined threshold.

23. The computer readable storage medium of claim 19, further comprising instructions to perform a garbage collection operation if the age of the object is greater than a predetermined threshold and if metadata is not associated with the object.

24. The computer readable storage medium of claim 19, further comprising instructions to perform a garbage collection operation if the age of the object is greater than a predetermined threshold and if the object has not been accessed within a predetermined time period.

25. The computer readable storage medium of claim 19, wherein the object is stored in a distributed storage system.

26. The computer readable storage medium of claim 19, further comprising instructions to remove timestamps from the sequence of timestamps that are not included in the at least one subsequence of timestamp.

27. The computer readable storage medium of claim 19, wherein clock of the computer system is an unreliable clock.