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.
Claims16
A method for providing global clock consistency across a distributed computing system, the distributed computing system including a plurality of computing machines, the plurality of computing machines including imperfect physical clocks, the method comprising:
- obtaining a first timestamp of a first event, the first timestamp including:
- a physical component indicative of a physical time at which the first event occurred at a first computing machine;
- and
- a logical component indicative of an ordering of the first event relative to one or more other events;
- and
- sending a message to initiate a second event to a second computing machine, the message including the first timestamp,
- wherein the message causes the second computing machine to process the second event,
- wherein the first timestamp is usable by the second computing machine to update a second timestamp indicative of when the second event occurred,
- wherein the physical component of the first timestamp is a first physical component based on a first physical clock at the first computing machine of the plurality of computing machines,
- wherein the logical component of the first timestamp is a first logical component, and
- wherein sending the message to initiate the second event causes the second computing machine of the plurality of the plurality of computing machines to:
- process the second event;
- and
- generate the second timestamp, wherein the second timestamp includes:
- a second physical component indicative of a physical time at which the second event occurred, the second physical component based on a second physical clock at the second computing machine;
- and
- a second logical component indicative of an ordering of the second event relative to one or more other events.
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:
- obtaining a first timestamp of a first event, the first timestamp including:
- a physical component indicative of a physical time at which the first event occurred at a first computing machine;
- and
- a logical component indicative of an ordering of the first event relative to one or more other events;
- and
- sending a message to initiate a second event to a second computing machine, the message including the first timestamp,
- wherein the message causes the second computing machine to process the second event,
- wherein the first timestamp is usable by the second computing machine to update a second timestamp indicative of when the second event occurred,
- wherein the physical component of the first timestamp is a first physical component based on a first physical clock at the first computing machine of the plurality of computing machines,
- wherein the logical component of the first timestamp is a first logical component, and
- wherein sending the message to initiate the second event causes the second computing machine of the plurality of the plurality of computing machines to:
- process the second event;
- and
- generate the second timestamp, wherein the second timestamp includes:
- a second physical component indicative of a physical time at which the second event occurred, the second physical component based on a second physical clock at the second computing machine;
- and
- a second logical component indicative of an ordering of the second event relative to one or more other events.
Dependencies are inferred from the claim text.