# US 2022/0067025 A1 · Ordering transaction requests in a distributed database according to an independently assigned sequence

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2022/0067025 A1
- Document ID: US20220067025A1
- Status: Published application
- Kind: A1
- Application number: 17/472,449
- Filed: 2021-09-10
- Published: 2022-03-03
- Earliest claimed: 2018-06-21
- Assignees: Amazon Technologies, Inc.
- Applicants: Amazon Technologies, Inc.
- Inventors: Douglas Brian Terry; Tate Andrew Certain; Amit Gupta; Rishabh Jain; Vaibhav Jain; Alexander Richard Keyes; Somasundaram Perianayagam; Nathan Pellegrom Riley; Akshat Vig; Ming-Chuan Wu
- Web page: https://patentgrep.com/patent/US20220067025A1

## CPC

- G06F 9/466: {Transaction processing}
- G06F 16/2365: {Ensuring data consistency and integrity}
- G06F 9/4881: {Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues}
- G06F 9/5038: {considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration (scheduling strategies G06F9/4881 and subgroups)}
- G06F 16/1805: {Append-only file systems, e.g. using logs or journals to store data}
- G06F 16/182: Distributed file systems
- G06F 16/2308: {Concurrency control (transaction processing G06F9/466)}
- G06F 16/2379: {Updates performed during online database operations; commit processing}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Transaction requests may be ordered in a distributed database according to an independently assigned sequence. Different distributed system nodes, such as a transaction coordinator and a storage node may independently assign sequence numbers to requests to access a distributed database. A storage node may receive the request from a transaction coordinator with an assigned sequence number and another request to which the storage node may assign a sequence number. The storage node can then order performance of the requests based on the sequence numbers.

## Claims

### Claim 1

A system, comprising:
a memory to store program instructions which, if performed by at least one processor, cause the at least one processor to perform a method to at least:
receive, by a transaction coordinator node, a request to perform a transaction at a distributed database;
assign, by the transaction coordinator node, a first sequence number to order performance of the transaction at a storage node of the distributed database;
receive, by the storage node, a non-transactional request to access the distributed database;
assign, by the storage node, a second sequence number by the storage node to order performance of the non-transactional request at the storage node; and
perform, by the storage node, the transaction request and the non-transactional request at the storage node according to an order determined based, at least in part, on the assigned sequence numbers.

### Claim 2 (depends on 1)

The system of claim 1, wherein the program instructions cause the at least one processor to further perform the method to at least:
send, by the transaction coordinator node a request to the storage node to prepare the storage node to perform the transaction; and
after receipt of responses from the storage node and one or more other storage nodes that acknowledge acceptance of the transaction for performance, send, by the transaction coordinator a request to the storage node to perform the transaction, wherein the performance of the transaction request is performed after receipt of the request to perform the transaction.

### Claim 3 (depends on 2)

The system of claim 2, wherein the program instructions cause the at least one processor to further perform the method to at least:
responsive to the receipt of the request to perform the transaction, store an entry for the transaction in a transaction ledger;
responsive to the receipt of the responses from the storage node and the one or more other storage nodes that acknowledge acceptance of the transaction for performance, update the entry for the transaction in the transaction ledger to indicate that the transaction is committed; and
responsive to receipt of completions of the transaction from the storage node and the one or more other storage nodes, update the entry for the transaction in the transaction ledger to indicate that the transaction is completed.

### Claim 4 (depends on 1)

The system of claim 1, wherein the distributed database is a non-relational database service offered by a provider network, wherein the request to perform the transaction and the non-transactional request are received via a programmatic interface for the non-relational database service, and wherein the wherein the request to perform the transaction and the non-transactional request are routed to the transaction coordinator node and the storage node respectively by a request routing node implemented as part of the database service.

### Claim 5

A method, comprising:
receiving a first request to access a distributed database that corresponds to a transaction coordinator node and is assigned a first sequence number by the transaction coordinator node to order performance of the first request at a storage node of the distributed database;
receiving a second request to access the distributed database that corresponds to the storage node and is assigned a second sequence number by the storage node to order performance of the second request at the storage node; and
performing the first request and the second request at the storage node according to an order determined based, at least in part, on the assigned sequence numbers.

### Claim 6 (depends on 5)

The method of claim 5, further comprising:
sending, by the transaction coordinator node, a request to the storage node to prepare the storage node to perform the first request; and
after receiving responses from the storage node and one or more other storage nodes that acknowledge acceptance of the first request for performance, sending a request to the storage node to perform the first request, wherein the performance of the transaction request is performed after receipt of the request to perform the transaction.

### Claim 7 (depends on 6)

The method of claim 6, further comprising:
responsive to receiving the request to perform the first request, storing an entry for the first request in a transaction ledger;
responsive to receiving the responses from the storage node and the one or more other storage nodes that acknowledge acceptance of the first request for performance, updating the entry for the first request in the transaction ledger to indicate that the first request is committed; and
responsive to receiving completions of the first request from the storage node and the one or more other storage nodes, updating the entry for the transaction in the transaction ledger to indicate that the first request is completed.

### Claim 8 (depends on 7)

The method of claim 7, wherein the updating the entry for the first request in the transaction ledger to indicate that the first request is committed is performed by the transaction coordinator node, and wherein the updating the entry for the transaction in the transaction ledger to indicate that the first request is completed is performed by a second transaction coordinator node.

### Claim 9 (depends on 6)

The method of claim 6, further comprising sending, by the transaction coordinator node, a second request to the storage node to prepare the storage node to perform the first request.

### Claim 10 (depends on 5)

The method of claim 5, further comprising:
receiving a third request to access the distributed database that corresponds to a second transaction coordinator node and is assigned a third sequence number by the second transaction coordinator node to order performance of the first request at a storage node of the distributed database;
after receiving an indication that the third request is rejected by the storage node, sending, by the second transaction coordinator node, an indication that the third request is aborted for a client that submitted the third request.

### Claim 11 (depends on 10)

The method of claim 10, further comprising sending, by the second transaction node to at least one other storage node that acknowledged the third request as accepted a notification that the third request is aborted.

### Claim 12 (depends on 5)

The method of claim 5, wherein the second request is a request to read data, wherein the second request specifies a consistency level for the request to read data, and wherein the order is further determined based on the consistency level for the request to read data.

### Claim 13 (depends on 5)

The method of claim 5, wherein the first sequence number is a first timestamp assigned according to a first clock for the transaction coordinator and wherein the second sequence number is a second timestamp assigned according to a second clock for the storage node.

### Claim 14

A non-transitory, computer-readable storage medium, storing program instructions that when executed by one or more computing devices cause the one or more computing devices to implement:
receiving a first request to access a distributed database that corresponds to a transaction coordinator node;
assigning a first sequence number by the transaction coordinator node to order performance of the first request at a storage node of the distributed database;
receiving a second request to access the distributed database that corresponds to the storage node;
assigning a second sequence number by the storage node to order performance of the second request at the storage node; and
performing the first request and the second request at the storage node according to an order determined based, at least in part, on the assigned sequence numbers.

### Claim 15 (depends on 14)

The non-transitory, computer-readable storage medium of claim 14, wherein the program instructions cause the one or more computing devices to further implement:
sending, by the transaction coordinator node a request to the storage node to prepare the storage node to perform the first request; and
after receiving responses from the storage node and one or more other storage nodes that acknowledge acceptance of the first request for performance, sending, by the transaction coordinator, a request to the storage node to perform the first request, wherein the performance of the transaction request is performed after receipt of the request to perform the transaction.

### Claim 16 (depends on 14)

The non-transitory, computer-readable storage medium of claim 14, wherein the program instructions cause the one or more computing devices to further implement:
responsive to receiving the request to perform the first request, storing an entry for the first request in a transaction ledger;
responsive to receiving the responses from the storage node and the one or more other storage nodes that acknowledge acceptance of the first request for performance, updating the entry for the first request in the transaction ledger to indicate that the first request is committed; and
responsive to receiving completions of the first request from the storage node and the one or more other storage nodes, updating the entry for the transaction in the transaction ledger to indicate that the first request is completed.

### Claim 17 (depends on 14)

The non-transitory, computer-readable storage medium of claim 14, wherein the program instructions cause the one or more computing devices to further implement:
receiving a third request to access the distributed database that corresponds to a second transaction coordinator node and is assigned a third sequence number by the second transaction coordinator node to order performance of the first request at a storage node of the distributed database;
after receiving an indication that the third request is rejected by the storage node, sending, by the second transaction coordinator node, an indication that the third request is aborted.

### Claim 18 (depends on 14)

The non-transitory, computer-readable storage medium of claim 14, wherein the second sequence number assigned to the second request by the storage node is received from a request routing node that routed the second request to the storage node.

### Claim 19 (depends on 14)

The non-transitory, computer-readable storage medium of claim 14, wherein the second request is a request to read data, wherein the second request specifies a consistency level for the request to read data, and wherein the order is further determined based on the consistency level for the request to read data.

### Claim 20 (depends on 14)

The non-transitory, computer-readable storage medium of claim 14, wherein the distributed database is a database service offered by a provider network and wherein the request to perform the transaction and the non-transactional request are received via a programmatic interface for the non-relational database service.
