Back to results
US 11,886,422 B1Granted
Transactional protocol for snapshot isolation without synchronized clocks
AssigneeAmazon Technologies, Inc.
InventorsBohou Li, Vijayan Prabhakaran, Mehul A. Shah, Benjamin Sowell, Douglas Brian Terry
Life of this patent
Estimating the term…
Abstract
A protocol for implementing ACID transactions that provides snapshot isolation in a distributed setting that does not require synchronized clocks is described. The protocol ensures at commit time that transactions touching common objects do not commit out of order. The protocol can be used in the context of a distributed data lake built on an object store in which clients can transactionally add or remove objects from logical tables.
Claims20
A computer-implemented method comprising:
- receiving a request to commit a transaction, wherein the transaction includes an update to at least a first table and a second table;
- obtaining, based on a first version history data structure associated with the first table, a first commit time of a most recent committed transaction that modified the first table and a first read time indicative of a start time of a most recent other transaction that read from the first table;
- obtaining, based on a second version history data structure associated with the second table, a second commit time of a most recent committed transaction that modified the second table and a second read time indicative of a start time of a most recent other transaction that read from the second table;
- generating a commit time for the transaction based at least in part on the first commit time, the second commit time, the first read time and the second read time, the generated commit time to be later than the first commit time, the first read time, the second commit time, and the second read time;
- and
- updating the first commit time and the second commit time to be the generated commit time.
3 more elements
A computer-implemented method comprising:
- receiving a request to commit a transaction, wherein the transaction includes an update to data of at least a first table;
- obtaining, from a first version history data structure associated with the first table, a commit time of a most recent committed transaction that modified the first table and a read time of a most recent other transaction that read from the first table;
- generating a commit time for the transaction that is based at least in part on, and is later than the commit time of the most recent committed transaction that modified the first table and the read time of the most recent other transaction that read from the first table;
- and
- updating the first version history data structure to indicate that the commit time of the most recent committed transaction is the generated commit time.
2 more elements
A system comprising:
- a first one or more electronic devices to implement a first service in a multi-tenant provider network to store data objects;
- and
- a second one or more electronic devices to implement a second service in the multi-tenant provider network, the second one or more electronic devices storing instructions that upon execution by one or more processors of the second one or more electronic device cause the second service to:
- receive a request to commit a transaction, wherein the transaction includes an update to data of at least a first table, wherein the data is stored by the first service;
- obtain, based on a first version history data structure associated with the first table, a commit time of a most recent committed transaction that modified the first table and a read time of a most recent other transaction that read from the first table;
- generate a commit time for the transaction that is based at least in part on, and is later than the commit time of the most recent committed transaction that modified the first table and the read time of the most recent other transaction that read from the first table;
- and
- update the first version history data structure to indicate that the commit time of the most recent committed transaction is the generated commit time.
5 more elements
Dependencies are inferred from the claim text.