Rectifying corrupt sequence values in distributed systems

• US 8,918,675 B2
• Filed: 12/19/2011
• Issued: 12/23/2014
• Est. Priority Date: 12/19/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Buban, Garret J., Kumar, Ritesh
• Primary Examiner(s): Baderman, Scott
• Assistant Examiner(s): BRYAN, JASON B
• Application Number:
  US13/329,470
• Publication Number:
  US 20130159769A1
• Time in Patent Office: 1,100 Days
• US Class Current: 714/21
• CPC Class Codes: G06F 1/14 Time supervision arrangements, e.g. real time clock
• CPC Class Codes: G06F 11/0709 in a distributed system consisting of a plurality of standalone computer nodes, e.g. clusters, client-server systems
• CPC Class Codes: G06F 11/076 by exceeding a count or rate limit, e.g. word- or bit count limit
• CPC Class Codes: G06F 11/0793 Remedial or corrective actions recovery from an exception in an instruction pipeline G06F9/3861; by retry G06F11/1402; for recovering from a failure of a protocol instance or entity H04L69/40
• CPC Class Codes: G06F 2201/81 Threshold

Abstract

Embodiments of the present invention relate to detecting and rectifying corruption in a distributed clock in a distributed system. Aspects may include receiving a sequence number used as part of the distributed clock at a node and determining if the sequence number is corrupt. In order to provide an effective mechanism for determining a sequence number is corrupt and taking corrective actions, a valid sequence number range may be determined, a propagation count associated with the sequence number may be evaluated, an estimated sequence number may be calculated, and an epoch number associated with the sequence number may be evaluated. Additionally, in exemplary aspects node with a corrupt trusted sequence values may self diagnosis and terminate associated processes to prevent further propagation of the corrupt sequence number.

Claims

1. A method in a distributed computing environment utilizing a processor and memory for detecting and rectifying corrupt sequence numbering in a distributed clock system of the distributed computing environment, the method comprising:

receiving, at a first node within the distributed computing environment, a first sequence number from a second node;

receiving, from a primary controller in the distributed computing environment, a peak rate of sequence number incrementing by the primary controller;

determining, with the processor, the first sequence number is greater than a stored sequence number;

determining a propagation number associated with the first sequence number is less than a predefined maximum propagation number;

determining the first sequence number is within a valid sequence number range, and

updating the stored sequence number to represent the first sequence number.

2. The method of claim 1, wherein the valid sequence number range is calculated, in part, based on the peak rate.

3. The method of claim 2 wherein the valid sequence number range is calculated, in part, based on the peak rate of the primary controller and a time elapsed since receiving the stored sequence number.

4. The method of claim 3, wherein the valid sequence number range is also calculated, in part, based on the propagation number associated with the first sequence number.

5. The method of claim 1 further comprising determining an elapsed time from a time stamp associated with the first sequence number is greater than a threshold time period.

6. The method of claim 5 further comprising increasing the propagation number associated with the first sequence number to the predefined maximum propagation number.

7. The method of claim 1 further comprising determining an elapsed amount of time from a time stamp associated with the first sequence number is less than a threshold time period.

8. The method of claim 7 further comprising increasing the propagation number associated with the first sequence number by one.

9. The method of claim 1 further comprising:

receiving an epoch number associated with the first sequence number and an epoch check number; and

determining the epoch number is different from a second epoch number associated with the stored sequence number.

10. The method of claim 9 further comprising:

determining the epoch number is not represented by the epoch check number; and

identifying the epoch number as a corrupted epoch number.

11. The method of claim 9 further comprising:

determining the epoch number is represented by the epoch check number; and

determining that the epoch number is incremented by one from the second epoch number associated with the stored sequence number.

12. One or more computer storage media, embodied within a hardware device, having computer-executable instructions embodied thereon, that when executed by a computing system having a processor and memory, cause the computing system to perform a method for rectifying corrupt sequence numbering in a distributed clock system of a distributed computing environment, the method comprising:

receiving, at a first node within the distributed computing environment, a first sequence number from a second node;

receiving a peak rate of a primary controller;

determining, with the processor, the first sequence number is not within a valid sequence number range; and

estimating, based in part on the peak rate, a sequence number, wherein the estimated sequence number is greater a stored sequence number.

13. The media of claim 12, wherein the method further comprises determining, with the processor, the estimated sequence number is greater than a stored sequence number.

14. The media of claim 12, wherein the method further comprises incrementing a bad counter associated with the first node in response to identifying the first sequence is not within the valid sequence range.

15. The media of claim 14, wherein the method further comprises suspending the first node in response to the bad counter achieving a predefined bad counter threshold.

16. The media of claim 12, wherein the method further comprises:

determining a second sequence number is within a valid sequence number range;

determining the second sequence number is less than a stored sequence number; and

decrementing a bad counter by a predefined value.

17. The media of claim 12, wherein the estimating the sequence number is comprised of:

increasing the stored sequence number based on an elapsed time multiplied by the peak rate.

18. The media of claim 12, wherein the estimating the sequence number is further comprised of:

increasing the sequence number based on the propagation number multiplied by a maximum propagation number threshold time.

19. The media of claim 12, wherein the method further comprises:

determining the peak rate is less than a stored peak rate; and

decrementing the stored peak rate by a predefined number.

20. A system for rectifying corrupt sequence numbering in a distributed clock system of a distributed computing environment, the system comprising:

a primary controller of the distributed clock system, wherein a communication from the primary controller to one or more nodes of the distributed computing environment include a sequence number, an epoch number, a peak rate, and an epoch number check;

a first node, wherein communications from the first node include a first sequence number; and

a second node of the distributed computing environment, wherein communications from the second node include a second sequence number, wherein the second sequence number is an estimated sequence number calculated, in part, based on the peak rate from the primary controller.