Ensuring globally consistent transactions

• US 9,569,253 B1
• Filed: 05/30/2013
• Issued: 02/14/2017
• Est. Priority Date: 06/04/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Hsieh, Wilson Cheng-Yi, Lloyd, Alexander, Hochschild, Peter, Epstein, Michael James Boyer, Quinlan, Sean
• Primary Examiner(s): Kim, Taelor
• Application Number:
  US13/905,637
• Time in Patent Office: 1,356 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/148 File search processing
• CPC Class Codes: G06F 16/2322 using timestamps
• CPC Class Codes: G06F 16/2379 Updates performed during online database operations; commit processing
• CPC Class Codes: G06F 16/2477 Temporal data queries
• CPC Class Codes: G06F 9/466 Transaction processing

Abstract

The present technology proposes techniques for ensuring globally consistent transactions. This technology may allow distributed systems to ensure the causal order of read and write transactions across different partitions of a distributed database. By assigning causally generated timestamps to the transactions based on one or more globally coherent time services, the timestamps can be used to preserve and represent the causal order of the transactions in the distributed system. In this regard, certain transactions may wait for a period of time after choosing a timestamp in order to delay the start of any second transaction that might depend on it. The wait may ensure that the effects of the first transaction are not made visible until its timestamp is guaranteed to be in the past. This may ensure that a consistent snapshot of the distributed database can be determined for any past timestamp.

Claims

1. A method, comprising:

identifying a set of transaction events originating from one or more database clients in a distributed computing system;

receiving a first time interval from at least one globally coherent time service, the first time interval determined based on timestamps generated by a plurality of time masters serving as references in the distributed computing system for the database clients, the first time interval including a current true time and representing a difference between an earliest one of the plurality of time masters and a latest one of the plurality of time masters;

determining, using a processor, a causal timestamp based on the first time interval;

associating the causal timestamp with the set of transaction events;

waiting a period of time for a given transaction event, the period of time corresponding to when the first time interval will pass the causal timestamp;

executing the given transaction event; and

publishing a result of the given transaction event after the period of time.

2. The method of claim 1, further comprising:

identifying a second set of transaction events;

receiving a second time interval from at least one globally coherent time service, wherein the second time interval is after the first time interval;

determining, using the processor, a second causal timestamp based on the second time interval;

associating the second causal timestamp with the second set of transaction events;

waiting a period of time for a second given transaction event from the second set of transaction events;

executing the second given transaction event; and

publishing a result of the second given transaction event.

3. The method of claim 2, further comprising assuming a causal dependency of the second set of transaction events on the first set of transaction events.

4. The method of claim 1, wherein determining a causal timestamp comprises selecting a latest time from the first time interval.

5. The method of claim 2, wherein determining a second causal timestamp comprises selecting a latest time from the second time interval.

6. The method of claim 1, wherein waiting comprises executing a consensus protocol to determine whether the given transaction event can occur, and wherein executing the consensus protocol comprises determining whether a predetermined number of devices agree on executing the given transaction event.

7. The method of claim 1, wherein the given transaction event comprises reading information from a database.

8. The method of claim 1, wherein the given transaction event comprises writing information to a database.

19. The method of claim 1, further comprising determining when the period of time is over, the determining comprising:

receiving a second time interval; and

determining whether the second time interval is past the causal timestamp.

9. A system, comprising:

a memory; and

a processor coupled to the memory, the processor configured to;

identify a set of transaction events originating from one or more database clients in a distributed computing system;

receive a first time interval from at least one globally coherent time service, the first time interval determined based on timestamps generated by a plurality of time masters serving as references in the distributed computing system for the database clients, the first time interval including a current true time and representing a difference between an earliest one of the plurality of time masters and a latest one of the plurality of time masters;

determine a causal timestamp based on the first time interval;

associate the causal timestamp with the set of transaction events;

wait a period of time for a given transaction event, the period of time corresponding to when the first time interval will pass the causal timestamp;

execute the given transaction event; and

publish a result of the given transaction event after the period of time.

10. The system of claim 9, wherein the processor is further configured to:

identify a second set of transaction events;

receive a second time interval from at least one globally coherent time service, wherein the second time interval is after the first time interval;

determine, using the processor, a second causal timestamp based on the second time interval;

associate the second causal timestamp with the second set of transaction events;

wait a second period of time for a second given transaction event from the second set of transaction events;

execute the second given transaction event; and

publish a result of the second given transaction event.

11. The system of claim 9, wherein to determine a causal timestamp the processor is further configured to select a latest time from the first time interval.

12. The system of claim 10, wherein to determine a second causal timestamp the processor is further configured to select a latest time from the second time interval.

13. The system of claim 9, wherein the given transaction event comprises processor instruction to read information from a database.

14. The system of claim 9, wherein the given transaction event comprises processor instruction to write information to a database.

20. The system of claim 9, wherein the processor is further configured to determine when the period of time is over, the determining comprising:

receiving a second time interval; and

determining whether the second time interval is past the causal timestamp.

15. A non-transitory computer-readable storage medium comprising instructions that, when executed by a processor, cause the processor to implement a method of ordering transactions, the method, comprising:

identifying a set of transaction events originating from one or more database clients in a distributed computing system;

receiving a first time interval from at least one globally coherent time service, the first time interval determined based on timestamps generated by a plurality of time masters serving as references in the distributed computing system, the first time interval including a current true time and representing a difference between an earliest one of the plurality of time masters and a latest one of the plurality of time masters;

determining, using the processor, a causal timestamp based on the first time interval;

associating the causal timestamp with the set of transaction events;

waiting a period of time for a given transaction event, the period of time corresponding to when the first time interval will pass the causal timestamp;

executing the given transaction event; and

publishing a result of the given transaction event after the period of time.

16. The computer-readable storage medium of claim 15, wherein the method further comprising:

identifying a second set of transaction events;

receiving a second time interval from at least one globally coherent time service, wherein the second time interval is after the first time interval;

determining, using the processor, a second causal timestamp based on the second time interval;

associating the second causal timestamp with the second set of transaction events;

waiting a period of time for a second given transaction event from the second set of transaction events;

executing the second given transaction event; and

publishing a result of the second given transaction event.

17. The computer-readable storage medium of claim 15, wherein the method further comprises assuming a causal dependency of the second set of transaction events on the first set of transaction events.

18. The computer-readable storage medium of claim 15, wherein waiting comprises executing a consensus protocol to determine whether the given transaction event can occur, and wherein executing the consensus protocol comprises determining whether a predetermined number of devices agree on executing the given transaction event.