Computing and tracking client staleness using transaction responses

• US 9,632,828 B1
• Filed: 09/24/2012
• Issued: 04/25/2017
• Est. Priority Date: 09/24/2012
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Mehta, Nirmal, Vermeulen, Allan H.
• Primary Examiner(s): Serrao, Ranodhi
• Assistant Examiner(s): Fiorillo, James
• Application Number:
  US13/625,506
• Time in Patent Office: 1,674 Days
• Field of Search: None
• CPC Class Codes: G06F 15/16 Combinations of two or more digital computers each having at least an arithmetic unit, a program unit and a register, e.g. for a simultaneous processing of several programs coordinating program control therefor G06F9/52; in regulating and control system G05B
• CPC Class Codes: G06F 16/2343 Locking methods, e.g. distributed locking or locking implementation details
• CPC Class Codes: G06F 16/273 Asynchronous replication or reconciliation
• CPC Class Codes: G06F 21/31 User authentication
• CPC Class Codes: G06F 9/466 Transaction processing
• CPC Class Codes: G06F 9/5011 the resources being hardware resources other than CPUs, Servers and Terminals
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms
• CPC Class Codes: H04L 12/00 Data switching networks interconnection of, or transfer of information or other signals between, memories, input/output devices or central processing units G06F13/00
• CPC Class Codes: H04L 65/80 Responding to QoS
• CPC Class Codes: H04L 67/1029 using data related to the state of servers by a load balancer
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

Distributed systems that maintain data items or state on multiple server nodes (e.g., a storage system or lock service) may receive transaction requests from clients that include read requests and/or write requests. If a transaction request includes a read request, a server node may determine a node staleness value for the requested data from the server'"'"'s perspective, and may return a transaction response to the client that includes the requested data and the node staleness value. The client may compute a client staleness value for the requested data dependent on the node staleness value in the transaction response, rather than on a separate heartbeat process. If the transaction also includes a write request, the server may return the transaction response for the read request before the write commits. In this case, the client may not use the requested data until it receives another response indicating that the write committed.

Claims

1. A system, comprising:

one or more processors; and

a memory coupled to the one or more processors, the memory storing program instructions executable by the one or more processors to implement a server node of a distributed data system;

wherein the server node is configured to;

receive a message from a client comprising a request to read a data item; and

in response to receiving the message;

determine a node staleness value that is associated with the data item from a perspective of the server node, wherein the node staleness value represents an upper bound on the amount of time that has elapsed, at the time when the node staleness value is determined, since the data item or a state associated with the data item was known by the server node to be valid and during which the requested data item or the state was subject to invalidation by updates to the requested data item or the state associated with the requested data item at one or more other server nodes of the distributed data system;

assemble a response message, wherein the response message comprises the data item and an indication of the node staleness value, wherein the node staleness value is usable by the client to determine a staleness of the requested data item that includes the amount of time that elapsed prior to the node staleness value being determined; and

send the response message to the client.

2. The system of claim 1,

wherein the message is a transaction request message, and wherein the transaction comprises the request to read the data item and a request to write another data item;

wherein the server node is configured to send the response message to the client without waiting for the write of the other data item to be committed on the server node.

3. The system of claim 2, wherein the server node is further configured to commit the write of the other data item, wherein successfully committing the write of the other data item comprises storing one or more replicas of the other data item on respective server nodes in the system.

4. The system of claim 3, wherein in response to successfully committing the write of the other data item, the server node is further configured to send another response message to the client, wherein the other response message indicates that the write of the other data item was committed, and wherein sending the other response message to the client indicates to the client that the transaction has succeeded and that the data item that was read is valid.

5. The system of claim 3, wherein in response to an unsuccessful commit of the write of the other data item, the server node is further configured to send another response message to the client, wherein the other response message indicates that the write of the other data item failed, and wherein sending the other response message to the client indicates to the client that the transaction has failed and that the data item that was read is invalid.

6. The system of claim 1, wherein the server node is one of a plurality of server nodes that coordinate with one another to maintain a shared state in the system.

7. The system of claim 1, wherein the node staleness value is a single value that represents the staleness of a collection of physically related data items or logically related data items.

8. The system of claim 1, wherein the message comprises a request for a lock on a shared resource, wherein the requested data item comprises an indication of lock ownership, and wherein the node staleness value represents a staleness of a state of the lock from the perspective of the server node.

9. A system, comprising:

one or more processors; and

a memory coupled to the one or more processors, the memory storing program instructions executable by the one or more processors to implement a client;

wherein the client is configured to;

send a message to a server of a distributed data system, wherein the message comprises a request for a data item maintained by the distributed data system;

receive a response message from the server, wherein the response message comprises the requested data item and an indication of a node staleness value that is associated with the requested data item from a perspective of the server, wherein the node staleness value represents an upper bound on the amount of time that has elapsed, prior to the server determining the node staleness value, since the requested data item or a state associated with the requested data item was known by the server to be valid according to the distributed data system;

compute a client staleness value for the requested data item or the state associated with the requested data item from a perspective of the client, wherein said computing is dependent on the indication of the node staleness value that was included in the response message, and wherein the client staleness value represents an upper bound on the amount of time that has elapsed, at the time of said computing, since the requested data item or the state associated with the requested data item, as returned in the response message, could have been considered by the client to be valid according to the distributed data system;

determine whether the client staleness value exceeds a pre-determined value for the requested data item or the state associated with the requested data item; and

in response to determining the client staleness value does not exceed the pre-determined value, use the requested data item received in the response message.

10. The system of claim 9,

wherein the message is a transaction request message, and wherein the requested transaction comprises the request to read the data item and a request to write another data item;

and

wherein the client is configured to refrain from using the requested data item until another response is received from the server indicating whether the other data item was successfully written.

11. The system of claim 10, wherein in response to receiving another response indicating that the write of the other data item was not committed or that the requested transaction has failed, the client is configured to discard the requested data item without using it.

12. The system of claim 10, wherein in response to receiving another response indicating that the write of the other data item was not committed or that the requested transaction has failed, the client is configured to send another transaction request message to the server to retry the requested transaction.

13. The system of claim 10, wherein the client is configured to use the requested data item in response to receiving another response indicating that the write of the other data item was committed and the requested transaction has succeeded.

14. The system of claim 9, wherein the client does not maintain a persistent connection with the server.

15. A method, comprising:

sending, by a client, a transaction request message to a server of a distributed data system, wherein the transaction request comprises a request for a data item that is maintained by the distributed data system;

receiving, by the client, a transaction response message from the server, wherein the transaction response message comprises the requested data item and an indication of a node staleness value that is associated with the requested data item from a perspective of the server, wherein the node staleness value represents an upper bound on the amount of time that has elapsed, prior to the server determining the node staleness value, since the requested data item or a state associated with the requested data item was known by the server to be valid according to the distributed data system;

computing, by the client, a client staleness value for the requested data item or the state associated with the requested data item from a perspective of the client, wherein said computing is dependent on the indication of the node staleness value that was included in the transaction response message, and wherein the client staleness value represents an upper bound on the amount of time that has elapsed, at the time of said computing, since the requested data item or the state associated with the requested data item, as returned in the transaction response message, could have been considered by the client to be valid according to the distributed data store;

determining, by the client, whether the client staleness value exceeds a pre-determined value for the requested data item or the state associated with the requested data item; and

in response to determining the client staleness value does not exceed the pre-determined value, using by the client, the requested data item received in the transaction response message.

16. The method of claim 15, further comprising, subsequent to said sending, said receiving, and said computing:

computing an updated client staleness value for the requested data item or the state associated with the requested data item, wherein said computing an updated client staleness value comprises adding to the client staleness value, an amount of time that has elapsed since the client staleness value was computed;

determining whether the updated client staleness value exceeds a pre-determined maximum staleness tolerance value for the requested data item or the state associated with the requested data item; and

wherein said in response to determining the client staleness value does not exceed the pre-determined value, using by the client, the requested data item comprises;

in response to determining that the updated client staleness value does not exceed the pre-determined maximum staleness tolerance value for the requested data item or the state associated with the requested data item, using the requested data item as received in the transaction response message.

17. The method of claim 16, wherein the maximum staleness tolerance value is configurable on a system basis, on a user basis, on an account basis, on an application basis, or on a data item basis.

18. The method of claim 15, wherein said computing comprises adding to the node staleness value a value representing an amount of time that elapsed between a time at which the client sent the transaction request message and a time at which the client received the transaction response message.

19. The method of claim 15, further comprising, for another request for another data item performing said sending, said receiving, and said computing:

computing an updated client staleness value for the other requested data item or the state associated with the other requested data item, wherein said computing an updated client staleness value comprises adding to the client staleness value, an amount of time that has elapsed since the client staleness value was computed;

determining whether the updated client staleness value exceeds a pre-determined maximum staleness tolerance value for the other requested data item or the state associated with the other requested data item; and

in response to determining that the updated client staleness value exceeds the pre-determined maximum staleness tolerance value for the other requested data item or the state associated with the other requested data item, sending another transaction request message to the server comprising a request for the other data item.

20. A method, comprising:

receiving, at a given server, a transaction request message from a client comprising a request for a data item that is stored in a distributed data store, wherein the given server is one of a plurality of servers that coordinate with one another to maintain a shared state of the distributed data store; and

in response to said receiving;

determining, by the given server, a node staleness value that is associated with the requested data item from a perspective of the server, wherein the node staleness value represents an upper bound on an amount of time that has elapsed, at the time of said determining, since the requested data item or a state associated with the requested data item was known by the given server to be valid and during which the requested data item or the state known to the server was subject to invalidation by updates to the requested data item or the state at one or more other servers of the plurality of servers;

assembling, by the given server, a transaction response message, wherein the transaction response message comprises the requested data item and an indication of the node staleness value, wherein the indication of the node staleness value is usable by the client to determine a staleness of the requested data item that includes the amount of time that elapsed prior to the node staleness value being determined; and

sending, by the given server, the transaction response message to the client.

21. The method of claim 20, wherein two or more of the plurality of servers store replicas of the requested data item, and wherein said determining comprises computing an elapsed time between a time at which the requested data item was updated on a first one of the plurality of servers and a time at which the requested data item was updated on the given server.

22. The method of claim 20, wherein the transaction request message comprises a request for configuration information that is shared by a plurality of clients, and wherein the node staleness value represents a staleness of the shared configuration information from the perspective of the given server.

23. A non-transitory computer-readable storage medium storing program instructions that when executed on one or more computers cause the one or more computers to implement a client;

wherein the client is configured to;

send a transaction request message to a server of a distributed data system, wherein the requested transaction comprises a read request and a write request;

receive a transaction response message from the server, wherein the transaction response message comprises a data item targeted by the read request and an indication of a node staleness value that is associated with the data item from a perspective of the server, wherein the node staleness value represents an upper bound on the amount of time that has elapsed, prior to the server determining the node staleness value, since the data item or a state associated with the data item was known by the server to be valid according to the distributed data system;

compute a client staleness value for the data item or the state associated with the data item from a perspective of the client, wherein said computing is dependent on the indication of the node staleness value that was included in the transaction response message, and wherein the client staleness value represents an upper bound on the amount of time that has elapsed, at the time of said computing, since the data item or the state associated with the data item, as returned in the transaction response message, could have been considered by the client to be valid according to the distributed data system;

determine whether the client staleness value exceeds a pre-determined value for the requested data item or the state associated with the requested data item; and

subsequent to determining the client staleness value does not exceed the pre-determined value, refrain from using the data item until another transaction response message is received from the server indicating whether another data item targeted by the write request was successfully written.

24. The non-transitory computer-readable storage medium of claim 23, wherein the client is further configured to:

use the data item in response to receiving another transaction response message from the sever indicating that the write of the other data item was successfully committed and that the requested transaction has succeeded; and

discard the data item without using it in response to receiving another transaction response message from the server indicating that the write of the other data item was not successfully committed or that the requested transaction has failed.

25. The non-transitory computer-readable storage medium of claim 23, wherein the transaction request message and the transaction response message conform to an application programming interface (API) that defines a transaction-based staleness protocol.

26. A non-transitory computer-readable storage medium storing program instructions that when executed on one or more computers cause the one or more computers to implement a server node in a distributed data system;

wherein the server node is configured to;

receive a transaction request message, wherein the requested transaction comprises a read request and a write request; and

in response to receiving the transaction request message;

determine a node staleness value that is associated with a data item targeted by the read request from a perspective of the server node, wherein the node staleness value represents an upper bound on the amount of time that has elapsed, at the time when the node staleness value is determined, since the data item or a state associated with the data item was known by the server node to be valid and during which the data item or the state known to the server node was subject to invalidation by updates to the data item or the state at one or more other servers of the distributed data system;

assemble a response message, wherein the response message comprises the data item and an indication of the node staleness value, wherein the node staleness value is usable by the client to determine a staleness of the requested data item that includes the amount of time that elapsed prior to the node staleness value being determined; and

send the response message to the client;

wherein the server node is configured to determine the node staleness value, assemble the response message, and send the response message to the client without waiting for the write request to be committed.

27. The non-transitory computer-readable storage medium of claim 26, wherein in response to receiving the transaction request message, the server node is further configured to:

perform the requested write, wherein the requested write comprises an operation to write a new data item or to update an existing data item; and

create or update a node staleness value for the data item targeted by the requested write to reflect that the data item targeted by the requested write was known by the server node to be valid at a time associated with the write request.