Ensuring properly ordered events in a distributed computing environment

Inventors

Alves, David • Lipcon, Todd

Assignees

Cloudera Inc

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.

Core Innovation

The invention provides a method and system for ensuring properly ordered events in a distributed computing environment despite inaccuracies and errors in local clocks of different computers. It accomplishes this by using hybrid timestamps consisting of a physical component representing the physical time a first event occurred and a logical component indicating an ordering within identical physical times. When a second event is initiated on a different computer with potentially skewed clock time, the first event's timestamp is sent along with the message. The second computer compares the first event's time with its own local clock time and, if the first is later, the alternate timestamp based on the first event's time and an incremented logical value is used for the second event's timestamp. This method enables proper ordering of events as determined by comparing these hybrid timestamps on a third system that needs to order these events.

The problem being solved arises because in distributed computing environments it is difficult to have accurate absolute time measurement due to clock drift, synchronization errors, and network delays. Physical clocks on different machines can have unknown but bounded errors, causing events that happen in a certain order to appear out of order based on timestamps from local clocks. For instance, one event might be recorded by one machine's clock as occurring after a second event recorded earlier by a different machine's clock, leading to incorrect ordering and potential security or operational errors. Existing solutions such as commit wait delay events by the clock error bound but impose undesirable delays.

The invention addresses this by introducing a physical time system that relies on the physical clock reading and a bounded error model for the clock to generate hybrid timestamps combining physical and logical components. Physical clocks are assumed monotonically increasing and bounded in error but are not fully accurate. The method uses the hybrid timestamp of a first event to ensure any causally related second events generated subsequently on different systems receive timestamps no earlier than the first event's timestamp, preserving proper causal ordering without requiring waiting periods for clock error synchronization. This approach allows event ordering using physical timestamps plus a logical sequence number, enabling consistent and correct ordering without sacrificing performance or relying solely on logical clocks.

Claims Coverage

The patent includes three independent claims directed to a method, a system, and a non-transitory computer-readable storage medium implementing the event ordering technique.

The claims cover a technique for reliably ordering distributed events using hybrid physical-logical timestamps, where subsequent event timestamps are adjusted based on received prior event timestamps to address clock errors, and ordering is established by comparing these timestamps without incurring waiting delays.

Stated Advantages

Documented Applications