Computing and tracking client staleness using transaction responses

Patent metadata

Field	Value
Publication number	US-9632828-B1
Application number	US-201213625506-A
Country	US
Kind code	B1
Filing date	Sep 24, 2012
Priority date	Sep 24, 2012
Publication date	Apr 25, 2017
Grant date	Apr 25, 2017

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.

First claim

What is claimed is:

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 accordin

Assignees

• Mehta Nirmal
• Vermeulen Allan H
• Amazon Tech Inc

Inventors

• Mehta Nirmal
• Vermeulen Allan H

Classifications

• G06F9/5011 Primary

  the resources being hardware resources other than CPUs, Servers and Terminals · CPC title

• H04L12/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 title

• G06F21/31

  User authentication · CPC title

• G06F15/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 title

• H04L67/1029 Primary

  using data related to the state of servers by a load balancer · CPC title