Real-time transactionally consistent change notifications

Patent metadata

Field	Value
Publication number	US-10509778-B2
Application number	US-201615163832-A
Country	US
Kind code	B2
Filing date	May 25, 2016
Priority date	May 25, 2016
Publication date	Dec 17, 2019
Grant date	Dec 17, 2019

Abstract

A method includes executing an initial instance of a change log process for a distributed system, each instance of the change log process configured to store, on memory hardware in communication with the data processing hardware, a transaction history of transactions executed on the distributed system. The method also includes receiving transaction requests for executing corresponding transactions on the distributed system and determining a change log load based on the received transaction requests. The method includes executing at least one subsequent instance of the change log process when the change log load satisfied a threshold load. When multiple instances of the change log process are executing, the method includes ceasing execution of the at least one subsequent instance of the change log process and merging the transaction history of the initial instance of the change log process and the transaction history of the at least one subsequent instance of the change log process.

First claim

What is claimed is:

1. A method comprising:
executing, by data processing hardware, an initial instance of a change log process for a distributed system, each instance of the change log process configured to store, in at least one change log cache of memory hardware in communication with the data processing hardware, a transaction history of transactions executed on the distributed system, wherein the at least one change log cache is non-durable and shardable in the memory hardware;
receiving, at the data processing hardware, transaction requests for executing corresponding transactions on the distributed system;
determining, by the data processing hardware, a change log load based on a number of the received transaction requests;
when the change log load satisfies a threshold load, executing, by the data processing hardware, at least one subsequent instance of the change log process;
after executing the at least one subsequent instance of the change log process, determining, by the data processing hardware, whether the change log load of the change log process, based on the number of received transaction requests, dissatisfies the threshold load;
determining, by the data processing hardware, whether multiple instances of the change log process are executing; and
when multiple instances of the change log process are executing and when the change log load of the change log process dissatisfies the threshold load:
ceasing, by the data processing hardware, execution of the at least one subsequent instance of the change log process; and
merging, by the data processing hardware, the transaction history of the initial instance of the change log process and the transaction history of the at least one subsequent instance of the change log process.

2. The method of claim 1 , further comprising storing each transaction history in the change log cache of the memory hardware.

3. The method of claim 2 , wherein the storing each transaction history comprises:
sharding, by the data processing hardware, the transaction history into data stripes;
replicating each data stripe; and
storing the data stripes and the replicated data stripes at multiple storage locations of the memory hardware.

4. The method of claim 1 , further comprising, in response to receiving each transaction request:
obtaining, by the data processing hardware, a true time;
determining, by the data processing hardware, a maximum commit time based on the true time, the maximum commit time specifying a maximum time to complete execution of the corresponding transaction on the distributed system; and
communicating the maximum commit time from the data processing hardware to the at least one change log cache of the memory hardware.

5. The method of claim 4 , wherein the at least one change log cache sets a notification lock from the true time until the maximum commit time, the notification lock preventing the corresponding change log cache from notifying one or more subscribing watchers for completed transactions having corresponding commit times earlier than the maximum commit time.

6. The method of claim 5 , wherein the at least one change log cache removes the notification lock at an end of the maximum commit time, the removed notification lock permitting the corresponding change log cache to notify the one or more subscribing watchers for each completed transaction having the corresponding commit time earlier than the maximum commit time.

7. The method of claim 4 , further comprising, after communicating the maximum commit time:
committing, by the data processing hardware, execution of the corresponding transaction on the distributed system, the transaction comprising the maximum commit time;
obtaining, by the data processing hardware, a transaction result indicating execution of the corresponding transaction on the distributed system is accepted when the corresponding transaction comprises a respective commit time at or before the maximum commit time; and
communicating the transaction result from the data processing hardware to the at least one change log cache, the received transaction result causing the at least one change log cache to record at least one mutation associated with the corresponding transaction.

8. The method of claim 7 , wherein the at least one change log cache communicates the recorded mutation to one or more watcher proxies executing on the data processing hardware, each watcher proxy configured to provide a notification to a respective subscribing watcher of the corresponding transaction at an end of the maximum commit time, the notification comprising the recorded mutation.

9. The method of claim 8 , wherein the notification further comprises a consistent snapshot of the transaction history at the end of the maximum commit time, the consistent snapshot comprising the corresponding transaction and any completed transactions having corresponding commit times earlier than the maximum commit time.

10. The method of claim 4 , further comprising, after communicating the maximum commit time:
committing, by the data processing hardware, execution of the corresponding transaction on the distributed system, the transaction comprising the maximum commit time;
obtaining, by the data processing hardware, a transaction result indicating execution of the corresponding transaction on the distributed system is rejected when the corresponding transaction fails to commit at or before the maximum commit time; and
communicating the transaction result from the data processing hardware to the at least one change log cache, the received transaction result causing the at least one change log cache to create a gap in the transaction history between the true time when the transaction process communicated the maximum commit time to the at least one change log cache and the maximum commit time.

11. The method of claim 10 , wherein the at least one change log cache communicates the gap in the transaction history to one or more watcher proxies executing on the data processing hardware, each watcher proxy configured to provide a notification to a respective subscribing watcher of the corresponding transaction at an end of the maximum commit time, the notification comprising a cache miss during the gap in the transaction history.

12. The method of claim 1 , further comprising:
determining, by the data processing hardware, a restart of the change log process after an off-line event;
obtaining, at the change log process executing on the data processing hardware, a true time;
determining, by the data processing hardware, a current sequence number based on the true time when the change log process restarts; and
waiting, by the data processing hardware, a global max commit time delay from the current sequence number before updating the transaction history for any transactions executed on the distributed system.

13. The method of claim 12 , wherein transactions executing on the distributed system prior to the restart of the change log process complete within the global max commit time delay.

14. The method of claim 1 , further comprising transmitting the merged transaction history to one or more subscribing watchers, each subscribing watcher having a standing query to receive a change notification for data stored on the memory hardware.

15. A system comprising:
data processing hardware of a distributed system; and
memory hardware in communication with the data processing hardware, the memory hardware storing instructions that when executed on the data processing hardware cause the data processing hardware to perform operations comprising:
executing an

Assignees

• Google Inc
• Google Llc

Inventors

• Fuller Alfred
• Kumar Vijay
• Hessmer Rainer

Classifications

• G06F9/466 Primary

  Transaction processing · CPC title

• G06F16/2358 Primary

  Change logging, detection, and notification (replication G06F16/27) · CPC title

• G06F16/2379

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

• G06F16/273

  Asynchronous replication or reconciliation · CPC title

• G06F16/27

  Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor · CPC title