Fault-tolerant timestamp generation for multi-node parallel databases
First Claim
1. A method for maintaining logical clocks in a multi-node parallel database system that includes a plurality of nodes, wherein each node of said plurality of nodes is associated with a logical clock, the method comprising the computer-implemented steps of:
- causing each node of said plurality of nodes to maintain a watermark that represents a time at least as recent as the latest time represented by the logical clocks on each of said plurality of nodes; and
when the time represented on a logical clock of a node of said plurality of nodes is within a predetermined threshold of the time represented by said watermark, then causing all nodes of said plurality of nodes to increase said watermark.
2 Assignments
0 Petitions
Accused Products
Abstract
Every node in a multi-node parallel database system maintains a logical clock for generating timestamps. The logical clocks are synchronized by attaching a current timestamp to every message that is sent by a node. When a node receives an incoming timestamp that is greater than the value indicated by the associated logical clock, it sets the associated logical clock forward to at least the value of the timestamp. Each node continually sends and receives a message including a timestamp at least once in a prescribed period of time. Moreover, each node maintains a high watermark that represents a time greater or equal to the highest time of any logical clock in the multi-node parallel database system.
95 Citations
22 Claims
-
1. A method for maintaining logical clocks in a multi-node parallel database system that includes a plurality of nodes, wherein each node of said plurality of nodes is associated with a logical clock, the method comprising the computer-implemented steps of:
-
causing each node of said plurality of nodes to maintain a watermark that represents a time at least as recent as the latest time represented by the logical clocks on each of said plurality of nodes; and when the time represented on a logical clock of a node of said plurality of nodes is within a predetermined threshold of the time represented by said watermark, then causing all nodes of said plurality of nodes to increase said watermark. - View Dependent Claims (2, 3, 4)
-
-
5. A method for maintaining logical clocks in a distributed system that includes a plurality of nodes, wherein each node of said plurality of nodes is associated with a logical clock, the method comprising the computer-implemented step of:
-
causing each node of said plurality of nodes to perform the following steps within each of a plurality of successive periods having a common prescribed duration; (a) transmitting a first message that contains a first message timestamp representing time indicated by the logical clock associated with said node to another node of said plurality of nodes; (b) receiving a second message from another node of said plurality of nodes, wherein said second message contains a second message timestamp; and (c) causing the logical clock associated with said node to reflect a time at least as recent as the time in the second message timestamp; wherein the step of causing the logical clock associated with said node to reflect a time at least as recent as the time in the second message timestamp includes the steps of; inspecting the logical clock associated with the node to determine a time indicated by said logical clock, comparing the time indicated by said logical clock with a time indicated by the second message timestamp, and if the time indicated by the second message timestamp is more recent than the time indicated by the logical clock, then setting the logical clock associated with the node to reflect a time that is at least as recent as the time reflected in the second message timestamp. - View Dependent Claims (6, 7, 8)
-
-
9. A multi-node parallel database clock control system, comprising:
-
a plurality of nodes, wherein each node of said plurality of nodes is associated with a logical clock; wherein each node of said plurality of nodes is configured to maintain a watermark that represents a time at least as recent as the latest time represented by the logical clocks on each of said plurality of nodes; wherein a watermark node of said plurality of nodes is to configured to cause all nodes of said plurality of nodes to increase said watermark, when the time represented on a logical clock of said watermark node of said plurality of nodes is within a predetermined threshold of the time represented by said watermark. - View Dependent Claims (10, 11)
-
-
12. A distributed clock synchronizing system comprising:
-
a plurality of nodes, wherein each node of said plurality of nodes is associated with a logical clock; wherein each node of said plurality of nodes is configured to perform the following steps within each of a plurality of successive periods having a common prescribed duration; (a) transmitting a first message that contains a first message timestamp representing time indicated by the logical clock associated with said node to another node of said plurality of nodes; (b) receiving a second message from another node of said plurality of nodes, wherein said second message contains a second message timestamp, and (c) causing the logical clock associated with the node to reflect a time that is at least as recent as the time reflected in the second message timestamp; wherein the step of causing the logical clock associated with said node to reflect a time at least as recent as the time in the second message timestamp includes the steps of; inspecting the logical clock associated with the node to determine a time indicated by said logical clock, comparing the time indicated by said logical clock with a time indicated by the second message timestamp, and if the time indicated by the second message timestamp is more recent than the time indicated by the logical clock, then setting the logical clock associated with the node to reflect a time that is at least as recent as the time reflected in the second message timestamp. - View Dependent Claims (13)
-
-
14. A computer readable medium having stored thereon sequences of instructions for maintaining a logical clock of a node in a multi-node parallel database system of a plurality of nodes, said sequences of instructions including instructions for performing the steps of:
-
maintaining a watermark that represents a time at least as recent as the latest time represented by the logical clocks on each of said plurality of nodes; when the time represented on said logical clock is within a predetermined threshold of the time represented by said watermark, then increasing said watermark. - View Dependent Claims (15, 16, 17)
-
-
18. A computer readable medium having stored thereon sequences of instructions for maintaining a logical clock of a node in a distributed system of a plurality of nodes, wherein each node of said plurality of nodes is associated with a logical clock, said sequences of instructions including instructions for performing the step of:
-
causing said node to perform the following steps within each of a plurality of successive periods having a common prescribed duration; (a) transmitting a first message that contains a first message timestamp representing time indicated by said logical clock to another node of said plurality of nodes; (b) receiving a second message from another node of said plurality of nodes, wherein said second message contains a second message timestamp; and (c) causing the logical clock associated with said node to reflect a time at least as recent as the time in the second message timestamp; wherein the step of causing the logical clock associated with said node to reflect a time at least as recent as the time in the second message timestamp includes the steps of; inspecting the logical clock associated with the node to determine a time indicated by said logical clock, comparing the time indicated by said logical clock with a time indicated by the second message timestamp, and if the time indicated by the second message timestamp is more recent than the time indicated by the logical clock, then setting the logical clock associated with the node to reflect a time that is at least as recent as the time reflected in the second message timestamp. - View Dependent Claims (19, 20, 21, 22)
-
Specification