Ensuring properly ordered events in a distributed computing environment
Inventors
Assignees
Publication Number
US-11388271-B2
Publication Date
2022-07-12
Expiration Date
2034-08-18
Interested in licensing this patent?
MTEC can help explore whether this patent might be available for licensing for your application.
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 where multiple computing machines have imperfect physical clocks. It recognizes that physical clocks of different machines may be unsynchronized and subject to bounded errors, causing events that occur in one order in reality to appear out of order based on local clock readings. The invention addresses this by associating each event with a hybrid timestamp composed of a physical time component, which indicates the local clock time, and a logical component, which provides additional ordering information when physical times are equal.
The system receives a first timestamp from a first computing machine upon occurrence of a first event, which includes both physical and logical components. When a second event is initiated on a second computing machine, the first timestamp is included in the message initiating the second event. The second machine compares its local clock time to the physical component of the received first timestamp. If the local clock time is earlier, it uses the first timestamp's physical time and increments the logical component to create the timestamp for the second event. This approach ensures correct ordering of causally related events despite clock discrepancies. The system allows external processes to determine correct global event ordering by comparing such hybrid timestamps from multiple machines.
Claims Coverage
The patent includes two independent claims covering the method and system for global clock consistency in distributed systems with imperfect physical clocks. The inventive features center on use of hybrid timestamps combining physical and logical components to maintain event order.
Generation and use of hybrid timestamps for events
Obtaining a first timestamp of a first event that includes a physical component indicative of physical time at the first computing machine and a logical component indicating ordering relative to other events. Sending a message including this first timestamp to a second machine to initiate a second event, allowing the second machine to generate and update a second timestamp that also includes physical and logical components.
Timestamp adjustment and ordering on the second machine
The second machine processes the second event using its local physical clock to create a second physical timestamp component, but adjusts it based on the received first timestamp to ensure correct temporal ordering. When the local clock shows a time earlier than the first event's physical component, the second event's timestamp uses the first physical component and increments the logical component to maintain ordering.
Comparison and ordering of causally related events
Determining the correct order between events by comparing hybrid timestamps. When physical components are equal, the logical components are compared to determine ordering. This enables consistent ordering of events occurring on different machines despite clock inaccuracies.
Distributed system synchronization with error bounds
Using synchronization mechanisms that provide error bounds for physical clocks relative to a reference time, enabling each machine to produce timestamps bounded in error and relying on these bounds to maintain consistency of event ordering across the system.
The independent claims focus on a method and system that generate hybrid timestamps with physical and logical components, enable timestamp adjustments based on received timestamps to ensure proper ordering of causally related events, and determine event order through comparison of these hybrid timestamps in distributed systems having imperfect, bounded-error physical clocks.
Stated Advantages
Ensures correct ordering of causally related events in distributed computing environments despite imperfect and unsynchronized physical clocks.
Enables use of physical time advantages such as point-in-time queries while preserving logical causality guarantees.
Avoids user experience delays associated with commit wait by providing a mechanism to adjust timestamps rather than enforcing strict delays between events.
Supports intuitive and consistent event ordering by combining physical timestamps with logical sequence numbers for tie-breaking.
Documented Applications
Maintaining correct event ordering on social media platforms to ensure privacy controls operate correctly, exemplified by the activist unfriending example where event timestamps prevent a government official from improperly viewing restricted messages.
General use in distributed computing environments where events occur across multiple machines with local clocks subject to error and drift, including synchronizing friend databases, posts databases, and other distributed data stores.
Interested in licensing this patent?