Ensuring properly ordered events in a distributed computing environment
AssigneeCloudera, Inc.
InventorsDavid Alves, Todd Lipcon
Life of this patent
Estimating the term…
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.
Claims15
A method for providing global clock consistency across a distributed computing system, the distributed computing system including a plurality of computing devices, the plurality of computing devices including imperfect physical clocks, the method comprising:
- receiving a first timestamp of a first event, the first timestamp of the first event including:
- a physical component based on a first physical clock at a first computing device in the distributed computing system;
- and
- a logical component representing a logical sequence number indicative of an ordering of the first event;
- receiving a message to initiate a second event;
- causing a second computing device in the distributed computing system to process the second event in response to receiving the message;
- determining a second event time indicative of a time the second event was processed by the second computing device based on a second physical clock at the second computing device;
- determining that the first timestamp is indicative of an earlier time than the second event time;
- and
- updating a second timestamp based on the second event time in response to determining that the first timestamp is indicative of an earlier time than the second event time.
A distributed computing system capable of providing global clock consistency, the distributed computing system including a plurality of computing machines, one or more of the computing machines configured to perform operations comprising:
- receiving a first timestamp of a first event, the first timestamp of the first event including:
- a physical component based on a first physical clock at a first computing machine in the distributed computing system;
- and
- a logical component representing a logical sequence number indicative of an ordering of the first event;
- receiving a message to initiate a second event;
- causing a second computing machine in the distributed computing system to process the second event in response to receiving the message;
- determining a second event time indicative of a time the second event was processed by the second computing machine based on a second physical clock at the second computing machine;
- determining that the first timestamp is indicative of an earlier time than the second event time;
- and
- updating a second timestamp based on the second event time in response to determining that the first timestamp is indicative of an earlier time than the second event time.
A non-transitory computer readable storing instructions, execution of which by a computing machine in a distributed computing system, causes the computing machine to perform operations for providing global clock consistency across the distributed computing system, the operations comprising:
- receiving a first timestamp of a first event, the first timestamp of the first event including:
- a physical component based on a first physical clock at a first computing machine in the distributed computing system;
- and
- a logical component representing a logical sequence number indicative of an ordering of the first event;
- receiving a message to initiate a second event;
- causing a second computing machine in the distributed computing system to process the second event in response to receiving the message;
- determining a second event time indicative of a time the second event was processed by the second computing machine based on a second physical clock at the second computing machine;
- determining that the first timestamp is indicative of an earlier time than the second event time;
- and
- updating a second timestamp based on the second event time in response to determining that the first timestamp is indicative of an earlier time than the second event time.
Dependencies are inferred from the claim text.