Sequencing technique to account for a clock error in a backup system

• US 8,028,194 B2
• Filed: 07/25/2008
• Issued: 09/27/2011
• Est. Priority Date: 07/25/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: InMage Systems, Inc. (Microsoft Corporation)
• Inventors: Kumar, Satish, Lanka, Sridhara, Shah, Jayesh, Kumar, Srin, Atluri, Rajeev
• Primary Examiner(s): Beausoliel, Jr.; Robert
• Assistant Examiner(s): Arcos; Jeison C
• Application Number:
  US12/179,591
• Publication Number:
  US 20100023797A1
• Time in Patent Office: 1,159 Days
• Field of Search: 715/968, 715/229, 714/6, 714/15, 714/16, 714/19, 714/229, 702/202, 702/204, 707/787
• US Class Current: 714/20
• CPC Class Codes: G06F 11/0727 in a storage system, e.g. in a DASD or network based storage system drivers for digital recording or reproducing units G06F3/06; circuits for error detection or correction within digital recording or reproducing units G11B20/18; for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS], H04L67/1097
• CPC Class Codes: G06F 11/0751 Error or fault detection not based on redundancy power supply failures G06F1/30; network fault management H04L41/06
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 2201/82 Solving problems relating to consistency ensuring consistency in mirrored systems G06F11/2064
• CPC Class Codes: G06F 2201/835 Timestamp

Abstract

A method, apparatus, and system of a sequencing technique to account for a clock error in a storage area network are disclosed. In one embodiment, a system of a backup server includes a processing module to examine a data timestamped with a sequence of characters denoting a time according to a clock source, an analysis module to determine that the data has been timestamped at an earlier time than an other data previously received, a substitution module to provide the data an incremental sequence number placed with the data using an algorithm until a new data is received that includes a future timestamp with a later timestamp than the timestamp of the other data, and a storage module to store the data.

Claims

1. A system of a backup server, comprising:

a processing module configured to examine a received data that is timestamped with a sequence of characters denoting a time according to a clock source through a computer processor associated with the backup server, the timestamp associated with the data received through the computer network from at least one of a client device and other servers, the received data from at least one of the client device and the other servers is stored in the backup storage through the backup server as a part of an information backup service offered by the backup server, wherein the received data is associated with a write I/O received at the backup server from the client device;

an analysis module configured to determine through the computer processor that the data having the timestamp received from at least one of a client device and other servers has been time stamped at an earlier time than the timestamp associated with another data previously received through the computer network from at least one of a client device and other servers;

a substitution module of the backup server to provide an incremental sequence number that is placed along with the timestamp of the other data denoting a relative time interval when a clock runs in a reverse order using an algorithm until a new data is received that includes a future timestamp with a timestamp later than a timestamp of the other data, wherein the incremental sequence number is generated through the backup server, wherein when a granularity of an increment of a timestamp associated with the data received from client device through the computer network cannot be used to delineate an order of the data associated with the I/O from the client device, then the sequence number is also used to determine the accurate location of the data having the timestamp from the client device stored in the backup storage, the time stamp is associated with the received data that is stored in the backup storage through the backup server; and

a storage module to store the data in a data storage medium of the backup server, wherein the storage module to store the data in a continuous data protection repository for a threshold value such that the data is persistently stored, wherein the threshold value is an amount of time, an allocated storage space, an available storage space.

2. The system of claim 1 wherein a sequence number is a global sequence number that increments across a plurality of sources of the data, and wherein the sequence number is changed based on an event in a network associated with the backup server, wherein the event is at least one of a write I/O being received and a shutdown event in the network, wherein the global sequence number is used for the new data received when the timestamp of the data time stamped with a sequence of numbers is unavailable.

3. The system of claim 1 wherein the sequence number is an incremental value timestamp generated by incrementing the timestamp of the other data previously received.

4. The system of claim 3 further comprising:

a setting module to reset the incremental sequence number to a first value when the new data is received that includes the future timestamp with the later timestamp later than the timestamp of the other data.

5. The system of claim 1 wherein the sequence number is a relative time interval value placed with the timestamp of the other data denoting a relative time interval according to an independent clock source.

6. The system of claim 1, further comprising:

an association module to associate the incremental sequence number with an equivalent timestamp; and

a sequence module to algorithmically determine a chronological sequence and arrange a set of data based on successive ones of the incremental sequence number and another set of data not based on successive ones of the incremental sequence number according to the chronological sequence.

7. The system of claim 6, further comprising:

a collation module to collate a plurality of sets of data based on successive ones of the incremental sequence number of a plurality of storage modules and a plurality of the sets of data not based on successive ones of the incremental sequence number of the plurality of storage modules according to the chronological sequence.

8. The system of claim 7, further comprising:

a retrieval module to access the data stored according to the chronological sequence through a lookup algorithm that examines the timestamp of the other data to determine an accurate location of a target data in a data stream between the other data and a plurality of sequence numbers to recover at least one of a within a volume and across volumes to the accurate location of the target data.

9. A system of a backup server, comprising:

an interface module configured to collect a data packet with a timestamp received from a computer network, the computer network coupled to at least one of the client device and other servers that sends the data packet with the timestamp to store the data packet through the backup server, wherein the data packet is associated with a write I/O received at the backup server from the client device;

a monitor module configured to determine through a processor if the timestamp is received from the computer network in a proper chronological sequence by comparing the timestamp of the received data packet to a timestamp of a previously received data packet;

an identifier module to affix through a processor of the backup server a relative sequential identifier to the timestamp of the previously received data packet when a subsequent timestamp is received from the computer network with a chronological value that is less than the previously received timestamp and until a later timestamp is received from the computer network with the chronological value that is greater than the previously received timestamp, the chronological value of the timestamp of the received data packet is less than the previously received timestamp when a clock associated with the timestamp of the received data packet runs in a reverse order; and

a write module to store the data packet to a data storage medium, wherein the storage module to store the data in a continuous data protection repository for a threshold value such that the data is persistently stored, wherein the threshold value is an amount of time, an allocated storage space, an available storage space.

10. The system of claim 9, further comprising:

a comparison module to equate the timestamp with the relative sequential identifier with a corresponding timestamp.

11. The system of claim 10, further comprising:

an assembly module to assemble a set of data packets with timestamps with the relative sequential identifier with the set of data packets with timestamps without the relative sequential identifier into the proper chronological sequence.

12. The system of claim 11, further comprising:

a synchronization module to chronologically synchronize the plurality of data packets of a plurality of data storage mediums into the proper chronological sequence.

13. A method of storing data comprising:

examining a data timestamped with a sequence of characters denoting a time according to a clock source, the data is collected from a computer network, the computer network to receive the data from at least one of a client device and other servers, wherein the received data is associated with a write I/O received at the backup server from the client device;

determining that the data has been timestamped at an earlier time than another data previously received;

providing the data an incremental sequence number generated by incrementing the timestamp of the other data previously received until a new data is received that includes a future timestamp with a later timestamp than the timestamp of the other data; and

storing the data, the incremental sequence number placed along with the timestamp of the other data previously received.

14. The method of claim 13, wherein the incremental sequence number is an incremental number placed with the data.

15. The method of claim 14, further comprising:

resetting the incremental sequence number to a first value when a new data is received that includes a future timestamp with the later timestamp than the timestamp of the other data.

16. The method of claim 15, wherein the incremental sequence number is a relative time interval value placed with the timestamp of the other data denoting a relative time interval according to an independent clock source.

17. The method of claim 15, further comprising:

associating the incremental sequence number with an equivalent timestamp.

18. The method of claim 17, further comprising:

algorithmically determining a chronological sequence and arranging a set of data based on successive ones of the incremental sequence number and another set of data not based on successive ones of the incremental sequence number according to the chronological sequence.

19. The method of claim 18, further comprising:

retrieving the data stored according to a chronological sequence.

20. A method of a backup server comprising:

algorithmically locating a time stamp time nearest to a user specified time within a set of storage modules;

algorithmically mapping a global sequence number with the user specified time; and

algorithmically locating a proceeding global sequence number of an incremental sequence of global sequence numbers across other storage modules of the set of storage modules until a set of required global sequence numbers of the storage modules have been identified that correspond to the user specified time, wherein the storage module to store the data in a continuous data protection repository for a threshold value such that the data is persistently stored, wherein the threshold value is an amount of time, an allocated storage space, an available storage space.

21. The method of claim 20 further comprising using an approximation algorithm to use the global sequence number as an equivalent of a specified number of clock ticks.

22. The method of claim 20 further comprising mapping a user specified event to the user specified time.