Ensuring properly ordered events in a distributed computing environment

Patent metadata

Field	Value
Publication number	US-10681190-B2
Application number	US-201816198677-A
Country	US
Kind code	B2
Filing date	Nov 21, 2018
Priority date	Dec 4, 2013
Publication date	Jun 9, 2020
Grant date	Jun 9, 2020

Abstract

A first event occurs at a first computer at a first time, as measured by a local clock. A second event is initiated at a second computer by sending a message that includes the first time. The second event occurs at a second time, as measured by a local clock. Because of clock error, the first time is later than the second time. Based on the first time being later than the second time, an alternate second time, that is based on the first time, is used as the time of the second event. When a third system determines the order of the two events, the first time is obtained from the first computer, and the alternate second time is obtained from the second computer, and the order of the events is determined based on a comparison of the two times.

First claim

The invention claimed is:

1. A method for providing global clock consistency across multiple partitions in a distributed database system, the multiple partitions being located on a number of computing machines, the computing machines having physical clocks that are imperfect, the method comprising:
maintaining a last physical clock value and a next logical value;
receiving, at a first computing machine and from a second computing machine, a request for assigning a hybrid timestamp to an event, the hybrid timestamp including a physical component and a logical component, wherein the physical component represents a physical time at which the event occurred as observed by a local, physical clock, and wherein the logical component represents a logical sequence number that indicates an ordering of events whose physical time representations are the same;
obtaining a current physical clock value from a local, physical clock;
determining the physical component of the hybrid timestamp using either the current physical clock value or the last physical clock value;
determining the logical component of the hybrid timestamp based on a comparison between the current physical clock value and the last physical clock value;
assigning the hybrid timestamp, including the determined physical and logical components, to the event; and
sending, toward another machine, a message including the hybrid timestamp.

2. The method of claim 1 , wherein the physical component of the hybrid timestamp is determined as the greater of the current physical clock value and the last physical clock value.

3. The method of claim 1 , wherein determining the logical component of the hybrid timestamp comprises:
upon determining that the current physical clock value is no less than the last physical clock value, assigning zero to the logical component of the hybrid timestamp.

4. The method of 3 , further comprising:
after said assigning of the hybrid timestamp:
setting the next logical value as one; and
overwriting the last physical clock value with the current physical clock value.

5. The method of claim 1 , wherein determining the logical component of the hybrid timestamp comprises:
upon determining that the current physical clock value is less than the last physical clock value, assigning the next logical value to the logical component of the hybrid timestamp.

6. The method of 5 , further comprising:
after said assigning of the hybrid timestamp, increasing the next logical value by one.

7. The method of claim 1 , wherein determining a correct order of a target event need not wait until all participants agree that a timestamp of the target event has passed a worst case synchronization error bound.

8. A method for providing global clock consistency across multiple partitions in a distributed database system, the multiple partitions being located on a number of computing machines, the computing machines having physical clocks that are imperfect, the method comprising:
receiving, from a sender, an incoming event having a hybrid timestamp, the hybrid timestamp of the incoming event including a physical component and a logical component, the physical component represents a physical time at which the incoming event occurred as observed by a local, physical clock, and wherein the logical component represents a logical sequence number that indicates an ordering of events whose physical time representations are the same; and
selectively setting a next logical value and a last physical clock value based on a comparison between a value of the physical component of the incoming event and an obtained current physical clock value.

9. The method of claim 8 , wherein selectively setting the next logical value and the last physical clock value comprises:
upon determining that a value of the physical component of the incoming event equals the obtained current physical clock value, setting the next logical value as: the greater of {a current logical value, or a value of the logical component of the incoming event}, plus one.

10. The method of claim 8 , wherein selectively setting the next logical value and the last physical clock value comprises:
upon determining that a value of the physical component of the incoming event is higher than the obtained current physical clock value, setting the last physical clock value as the value of the physical component of the incoming event, and setting the next logical value as: a value of the logical component of the incoming event, plus one.

11. The method of claim 8 , wherein selectively setting the next logical value and the last physical clock value comprises:
upon determining that a value of the physical component of the incoming event is lower than the obtained current physical clock value, maintaining the next logical value and the last physical clock value as they are.

12. The method of claim 8 , further comprising:
upon receiving a request for external consistency, executing a commit-wait protocol such that it becomes necessary for determining a correct order of a target event to wait until all participants agree that a timestamp of the target event has passed a worst case synchronization error bound.

13. The method of claim 8 , wherein the hybrid timestamp remains constant in size as time progresses.

14. The method of claim 8 , wherein the physical component of the hybrid timestamp enables association of the event with a physical point of time.

15. The method of claim 8 , wherein both the logical component and the physical component of the hybrid timestamp only monotonically increase.

16. The method of claim 8 , wherein all machines in the distributed database system are configured to attach each event with a hybrid timestamp.

17. The method of claim 8 , wherein the distributed database system includes a mechanism for the imperfect physical clocks among the computing machines to perform synchronization with a reference time, and wherein said mechanism is capable of providing an error bound along with each time measurement against the reference time.

18. A method for providing global clock consistency across multiple partitions in a distributed database system, the multiple partitions being located on a number of computing machines, the computing machines having physical clocks that are imperfect, the method comprising:
locating a target event including a hybrid timestamp, the hybrid timestamp of the target event including a physical component and a logical component, the physical component represents a physical time at which the event occurred as observed by a local, physical clock, and wherein the logical component represents a logical sequence number that indicates an ordering of events whose physical time representations are the same; and
determining a correct order of the target event in relation to other events based on a comparison of the hybrid timestamp of the target event against hybrid timestamps of the other events.

19. The method of claim 18 , wherein, if the physical components of the hybrid timestamps of two events in comparison do not equal each other, determining that whichever event having a hybrid timestamp with a smaller physical component as a preceding event.

20. The method of claim 18 , wherein, if the physical components of the hybrid timestamps of two events in comparison equal each other, determining that whichever event having a hybrid timestamp with a smaller logical component as a preceding event.

21. The method of claim 18 , wherein determining a correct ord

Assignees

• Cloudera Inc

Inventors

• Alves David
• Lipcon Todd

Classifications

• G06F1/14

  Time supervision arrangements, e.g. real time clock · CPC title

• G06Q50/26

  Government or public services (business processes related to the transportation industry G06Q50/40) · CPC title

• G06Q10/00

  Administration; Management · CPC title

• H04L67/10

  in which an application is distributed across nodes in the network (software deployment G06F8/60; multiprogramming arrangements G06F9/46) · CPC title

• H04L69/28 Primary

  Timers or timing mechanisms used in protocols · CPC title