Ensuring globally consistent transactions

Patent metadata

Field	Value
Publication number	US-9569253-B1
Application number	US-201313905637-A
Country	US
Kind code	B1
Filing date	May 30, 2013
Priority date	Jun 4, 2012
Publication date	Feb 14, 2017
Grant date	Feb 14, 2017

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.

First claim

The invention claimed is:

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.

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.

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.

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
determinin

Assignees

• Google Inc

Inventors

• Hsieh Wilson Cheng-Yi
• Lloyd Alexander
• Hochschild Peter
• Epstein Michael James Boyer
• Quinlan Sean

Classifications

• G06F9/466 Primary

  Transaction processing · CPC title

• G06F16/148

  File search processing · CPC title

• G06F16/2322

  using timestamps · CPC title

• G06F16/2379 Primary

  Updates performed during online database operations; commit processing · CPC title

• G06F16/2477

  Temporal data queries · CPC title