Non-blocking processing of federated transactions for distributed data partitions

Patent metadata

Field	Value
Publication number	US-9959308-B1
Application number	US-201414500756-A
Country	US
Kind code	B1
Filing date	Sep 29, 2014
Priority date	Sep 29, 2014
Publication date	May 1, 2018
Grant date	May 1, 2018

Abstract

Non-blocking processing of federated transactions may be implemented for distributed data partitions. A transaction may be received that specifies keys at data nodes to lock in order to perform the transaction. Lock requests are generated and sent to the data nodes which identify sibling keys to be locked at other data nodes for the transaction. In response to receiving the lock requests, data nodes may send to lock queues indicating other lock requests for the keys at the data node. An evaluation of the lock queues based, at least in part, on an ordering of the lock requests in the lock queues may be performed to identify a particular transaction to commit. Once identified, a request to commit the identified transaction may be sent to the particular data nodes indicated by the sibling keys in a lock request for the identified transaction.

First claim

What is claimed is:

1. A system, comprising:
at least one compute node that implements a transaction manager;
a plurality of data nodes that maintain respective data partitions;
the transaction manager, configured to:
for a given transaction received at the transaction manager from a client to commit at particular ones of the plurality of data nodes:
send to at least the particular data nodes respective lock requests, wherein a respective lock request sent to a respective data node identifies to lock a key to at least a portion of the respective data partition maintained at the respective data node and respective sibling keys to lock at nodes other than the respective data node of the particular nodes to perform the transaction;
receive, responsive to the respective lock requests from at least the particular data nodes sent the respective lock requests, respective lock queues for the keys to the portions of the respective data partitions, wherein the respective lock queues comprise one or more lock requests for a respective one or more transactions including the respective lock request for the transaction, wherein the one or more lock requests identify respective sibling keys to lock as part of the one or more respective transactions, wherein at least one of the respective lock queues includes a respective lock request for a respective transaction that is different than the transaction;
evaluate the respective lock queues from at least the particular data nodes to identify a particular transaction of the one or more respective transactions to commit, wherein the evaluation is based, at least in part, on an ordering of the one or more lock requests within the respective lock queues; and
send a request to commit the identified transaction to the data nodes identified according to the sibling keys included in a respective lock request for the identified transaction.

2. The system of claim 1 , wherein the send of the respective lock requests, the receive of the respective lock queues, the evaluation of the respective lock queues, and the send of the request to commit are performed as part of a current round of transaction processing, wherein the send of the respective lock requests, the receive of the respective lock queues, and the evaluation of the respective lock queues are performed as part of one or more prior rounds of transaction processing, wherein the particular transaction of the one or more respective transactions was not identified to be committed as part of the one or more prior rounds of transaction processing.

3. The system of claim 2 , wherein prior to the send of the respective lock requests, the receive of the respective lock queues, the evaluation of the respective lock queues, and the send of the request to commit performed as part of a current round of transaction processing, identify one or more additional keys for portions of a respective data partition at one or more other data nodes of the plurality of data nodes based, at least in part, on respective lock queues received as part of a prior round of transaction processing, wherein the one or more other data nodes are included with the particular data nodes sent the respective lock requests as part of the current round of transaction processing.

4. The system of claim 1 , wherein the transaction manager is one of a plurality of transaction managers, wherein the plurality of data nodes are part of a larger collection of data nodes, and wherein the plurality of transaction managers and the larger collection of data nodes are implemented as part of a network-based transaction service, wherein the client is one of a plurality of clients of the network-based transaction service.

5. A method, comprising:
performing, by one or more computing devices:
for a given transaction received at a transaction manager from a client to commit at particular ones of a plurality of data nodes that maintain respective partitions of data:
sending to at least the particular data nodes of the plurality of data nodes respective lock requests, wherein a respective lock request sent to a respective data node identifies to lock a key to at least a portion of the respective data partition maintained at the respective data node and respective sibling keys to lock at nodes other than the respective data node of the particular nodes to perform the transaction;
receiving, responsive to the respective lock requests from at least the particular data nodes sent the respective lock requests, respective lock queues for the keys to the portions of the respective data partitions, wherein the respective lock queues comprise one or more lock requests for a respective one or more transactions including the respective lock request for the transaction, wherein the one or more lock requests identify respective sibling keys to lock as part of the one or more respective transactions, wherein at least one of the respective lock queues includes a respective lock request for a respective transaction that is different than the transaction;
evaluating the respective lock queues from at least the particular data nodes to identify a particular transaction of the one or more respective transactions to commit, wherein the evaluation is based, at least in part, on an ordering of the one or more lock requests within the respective lock queues; and
sending a request to commit the identified transaction to the data nodes identified according to the sibling keys included in a respective lock request for the identified transaction.

6. The method of claim 5 , wherein sending the respective lock requests, receiving the respective lock queues, evaluating the respective lock queues, and sending the request to commit are performed as part of a current round of transaction processing, wherein sending the respective lock requests, receiving the respective lock queues, and evaluating the respective lock queues are performed for one or more prior rounds of transaction processing, wherein the particular transaction of the one or more respective transactions is not identified to be committed as part of the one or more prior rounds of transaction processing.

7. The method of claim 6 , wherein prior to sending the respective lock requests, receiving the respective lock queues, evaluating the respective lock queues, and sending the request to commit as part of a current round of transaction processing, identifying one or more additional keys for portions of a respective data partition at one or more other data nodes of the plurality of data nodes based, at least in part, on respective lock queues received as part of a prior round of transaction processing, wherein the one or more other data nodes are included with the particular data nodes sent the respective lock requests as part of the current round of transaction processing.

8. The method of claim 7 , wherein including the particular data nodes sent the respective lock requests as part of the current round of transaction processing is performed in response to determining that the one or more additional keys are below a key expansion threshold, wherein another transaction determined to include additional keys in excess of the key expansion threshold aborts transaction processing.

9. The method of claim 5 , wherein evaluating the respective lock queues from at least the particular data nodes to identify the particular transaction of the one or more respective transactions to commit comprises determining that respective lock requests for the particular transaction were first to arrive at the respective lock queues for the data nodes for the particular transaction.

10. The method of claim 5 , further comprising:
performing, by another one or more computing devices:
for a di

Assignees

• Amazon Tech Inc

Inventors

• Carman Charles Alexander
• Suver Claire Elizabeth
• Davis Melissa Elaine
• Buddington Paul Matthew
• Suver Christopher Allen
• Cwik Lukasz Wojciech
• Krueger Chelsea Celest

Classifications

• G06F9/466

  Transaction processing · CPC title

• G06F17/30362 Primary

  Physics · mapped topic

• G06F17/30371

  Physics · mapped topic

• G06F16/2365

  Ensuring data consistency and integrity · CPC title

• G06F16/2343 Primary

  Locking methods, e.g. distributed locking or locking implementation details · CPC title