Distributed processing of transactions in a network using timestamps

1 . A computer-implemented method for processing a sequence of transactions to maintain consistency and latency in a distributed system, comprising:

receiving, by a node, a first transaction for a data record associated with a first timestamp generated by a timestamp service;

identifying, by the node, a second transaction for the data record that conflicts with the first transaction, wherein the identified second transaction has a second timestamp that is a most recent transaction stored in the node; and

receiving a determination, by the node, of a transmission status of the second transaction;

transmitting, by the node, a result of the first transaction to fulfill the first transaction received from a client based on the determination of the transmission status, fulfillment of the first transaction occurring after a full transmission time period of the first transaction is greater than or equal to a minimum transaction latency (MTL) of the distributed system; and

wherein a maximum error of a standard clock synchronization mechanism, namely the standard clock synchronization error at each timestamp service, in the distributed system is less than a minimum transaction latency (MTL).

2 . The computer-implemented method of claim 1 , wherein the first and second timestamps include an uncertainty window, and the uncertainty window is based on the standard clock synchronization error at the timestamp service issuing the first or second timestamp.

3 . The computer-implemented method of claim 1 , wherein the first timestamp includes a first sequence number and a first uncertainty window, and the second timestamp includes a second sequence number and a second uncertainty window.

4 . The computer-implemented method of claim 3 , wherein the first and second timestamps are issued by different timestamp service instances, and

when the sequence numbers are tied, the tie is broken by a timestamp service instance ID.

5 . The computer-implemented method of claim 1 further comprising sequentially ordering the first transaction and the second transaction according to a first sequence number and a second sequence number, respectively, wherein

the first and second timestamps are issued by a first timestamp service.

6 . The computer-implemented method of claim 5 , wherein the first and second timestamps are issued by different timestamp service instances, and

when the sequence numbers are tied, the tie is broken by a timestamp service instance ID.

7 . The computer-implemented method of claim 1 , wherein

when the first transaction is a read operation and the second transaction is a write intent operation,

the transmission status of the second transaction is determined to be committed, and

the result transmitted to the client is the data record for write intent operation; and

when the first transaction is a write operation and the second transaction is a write intent operation,

the transmission status of the second transaction is determined to be committed, and

the result transmitted to the client is a success message.

8 . The computer-implemented method of claim 1 , wherein

when the first transaction is a read operation and the second transaction is a write intent operation,

the transmission status of the second transaction is determined to be aborted, and

the result transmitted to the client is the data record committed before the write intent operation; and

when the first transaction is a write operation and the second transaction is a write intent operation,

the transmission status of the second transaction is determined to be aborted, and

the result transmitted to the client is a success message.

9 . The computer-implemented method of claim 1 , wherein

the first transaction is a read operation and the second transaction is a write intent operation,

the transmission status of the second transaction is determined to be in-progress, and

the method further comprising:

aborting one of the first transaction or the second transaction based on a lowest priority of respectively assigned priorities; and

when the priorities of the first transaction and the second transaction are the same, aborting one of the first transaction and the second transaction based on an oldest of the first timestamp and the second timestamp.

10 . The computer-implemented method of claim 9 , wherein

when the second transaction is aborted,

marking the second transaction as aborted and issuing an asynchronous transmission cleanup, and

the result transmitted to the client is the data record committed before the write intent operation; and

when the first transaction is aborted, the result transmitted is a failure on the read operation.

11 . The computer-implemented method of claim 9 , wherein when the first and the second transactions are a same transaction, the write intent is returned in response to the read operation.

12 . The computer-implemented method of claim 1 , wherein

the first transaction is a write operation and the second transaction is a write intent operation,

the transmission status of the second transaction is determined to be in-progress, and

the method further comprising:

aborting one of the first transaction or the second transaction based on a lowest priority of respectively assigned priorities; and

when the priorities of the first transaction and the second transaction are the same, aborting one of the first transaction and the second transaction based on an oldest of the first timestamp and the second timestamp.

13 . The computer-implemented method of claim 12 , wherein

when the second transaction is aborted,

marking the second transaction as aborted and issuing an asynchronous transmission cleanup, and

the result transmitted to the client is a success message; and

when the first transaction is aborted, the result transmitted is a failure message.

14 . A node for processing a sequence of transactions to maintain consistency and latency in a distributed system, comprising:

a non-transitory memory storage comprising instructions; and

one or more processors in communication with the memory, wherein the one or more processors execute the instructions to:

generate time stamps including a first timestamp;

receive a first transaction for a data record associated with the first timestamp;

identify a second transaction for the data record that conflicts with the first transaction, wherein the identified second transaction has a second timestamp that is a most recent transaction stored in the node;

receive a determination of a transmission status of the second transaction; and

transmitting a result of the first transaction to fulfill the first transaction received from a client based on the determination of the transmission status, fulfillment of the first transaction occurring after a full transmission time period of the first transaction is greater than or equal to a minimum transaction latency (MTL) of the distributed system; and

wherein a maximum error of a standard clock synchronization mechanism, namely the standard clock synchronization error at each timestamp service, in the distributed system is less than a minimum transaction latency (MTL).

15 . The node of claim 14 , wherein the first and second timestamps include an uncertainty window, and the uncertainty window is based on the standard clock synchronization error at the timestamp service issuing the first or second timestamp.

16 . The node of claim 14 , wherein the first timestamp includes a first sequence number and a first uncertainty window, and the second timestamp includes a second sequence number and a second uncertainty window.

17 . The node of claim 16 , further comprising sequentially ordering the first transaction and the second transaction according to the first sequence number and the second sequence number, respectively, wherein

the first and second timestamps are issued by a first timestamp service.

18 . The node of claim 14 , wherein

when the first transaction is a read operation and the second transaction is a write intent operation,

the transmission status of the second transaction is determined to be committed, and

the result transmitted to the client is the data record for write intent operation; and

when the first transaction is a write operation and the second transaction is a write intent operation,

the transmission status of the second transaction is determined to be committed, and

the result transmitted to the client is a success message.

19 . The node of claim 14 , wherein

when the first transaction is a read operation and the second transaction is a write intent operation,

the transmission status of the second transaction is determined to be aborted, and

the result transmitted to the client is the data record committed before the write intent operation; and

when the first transaction is a write operation and the second transaction is a write intent operation,

the transmission status of the second transaction is determined to be aborted, and

the result transmitted to the client is a success message.

20 . The node of claim 14 , wherein

the first transaction is a read operation and the second transaction is a write intent operation,

the transmission status of the second transaction is determined to be in-progress, and

the one or more processors further execute the instructions to:

aborting one of the first transaction or the second transaction based on a lowest priority of respectively assigned priorities; and

when the priorities of the first transaction and the second transaction are the same, aborting one of the first transaction and the second transaction based on an oldest of the first timestamp and the second timestamp.

21 . The node of claim 20 , wherein

when the second transaction is aborted,

marking the second transaction as aborted and issuing an asynchronous transmission cleanup, and

the result transmitted to the client is the data record committed before the write intent operation; and

when the first transaction is aborted, the result transmitted is a failure on the read operation.

22 . The node of claim 20 , wherein when the first and the second transactions are a same transaction, the write intent is returned in response to the read operation.

23 . The node of claim 20 , wherein

the first transaction is a write operation and the second transaction is a write intent operation,

the transmission status of the second transaction is determined to be in-progress, and

the one or more processors further execute the instructions to:

aborting one of the first transaction or the second transaction based on a lowest priority of respectively assigned priorities; and

when the priorities of the first transaction and the second transaction are the same, aborting one of the first transaction and the second transaction based on an oldest of the first timestamp and the second timestamp.

24 . The node of claim 23 , wherein

when the second transaction is aborted,

marking the second transaction as aborted and issuing an asynchronous transmission cleanup, and

the result transmitted to the client is a success message; and

when the first transaction is aborted, the result transmitted is a failure message.