Ensuring properly ordered events in a distributed computing environment
Inventors
Assignees
Publication Number
US-11146668-B2
Publication Date
2021-10-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 that events are properly ordered in a distributed computing environment where computing devices have imperfect physical clocks. It addresses the problem of clock inaccuracies and errors causing events that happen in a certain chronological order to appear out of order when comparing timestamps generated by local clocks of different devices.
The core innovation involves receiving a first timestamp for a first event, which includes a physical component based on a physical clock and a logical component representing a logical sequence number. When a second event is initiated at another computing device, the system processes the event, determines the time based on that device's local clock, and compares it with the first timestamp. If the first timestamp is later than the second event time, an alternate timestamp based on the first timestamp is used for the second event, incrementing the logical component to preserve correct ordering. This mechanism allows for the determination of event order based on these hybrid timestamps despite clock discrepancies.
Claims Coverage
The patent includes three independent claims that describe methods, systems, and computer-readable media for providing global clock consistency across distributed computing systems with imperfect physical clocks. Four main inventive features are identified from these claims.
Hybrid timestamp with physical and logical components
Receiving a first timestamp of a first event that includes a physical component based on a physical clock at a first computing device and a logical component representing a logical sequence number indicative of ordering.
Comparison and updating of timestamps for event ordering
Determining that the first timestamp indicates an earlier time than a second event time determined based on a second physical clock, and updating a second timestamp based on the second event time in response to this determination.
Maintaining timestamp structure and synchronization mechanism
Maintaining the physical and logical components as a fixed-size tuple; having a distributed system where physical clocks synchronize with a reference time and provide an error bound with each measurement.
Implementation across methods, systems, and computer-readable media
Providing the above timestamping and ordering mechanisms as method steps, as operations performed by distributed computing machines, and as instructions stored in non-transitory computer-readable media.
The inventive features establish a technique for ensuring proper global event ordering in distributed systems by using hybrid physical and logical timestamps to compensate for clock errors, maintaining consistency across various implementations including methods, systems, and executable media.
Stated Advantages
Preserves correct ordering of events in distributed systems despite imperfect and unsynchronized physical clocks.
Enables unique and incremental timestamping by combining physical time and logical sequence numbers.
Avoids the need for inducing delays such as commit waits, improving responsiveness.
Provides an approach compatible with existing time synchronization mechanisms that can supply error bounds.
Allows for consistent event ordering usable by clients to determine causality and access control correctly.
Documented Applications
Ordering of social media user events such as unfriending and posting to ensure privacy and correct visibility of posts.
Maintaining correct event ordering in distributed computing environments that use databases to track user relationships and posts.
Providing correct ordering for software platforms where causally related events occur across multiple servers or devices with unsynchronized clocks.
Supporting point-in-time queries and causal consistency in distributed databases and systems using synchronized physical clocks with bounded errors.
Interested in licensing this patent?