System and method for determining staleness of data received from a distributed lock manager

• US 8,719,432 B1
• Filed: 04/30/2010
• Issued: 05/06/2014
• Est. Priority Date: 04/30/2010
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Vermeulen, Allan H., Rath, Timothy Andrew
• Primary Examiner(s): Dharia, Rupal
• Assistant Examiner(s): MCADAMS, BRAD
• Application Number:
  US12/771,861
• Time in Patent Office: 1,467 Days
• Field of Search: 709/229, 707/704, 707/999.008
• US Class Current: 709/229
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

A method and system are disclosed for implementing a client of a distributed lock manager comprising a plurality of nodes. The client is configured to send a request to the distributed lock manager, the request including a local time of the client. The client receives a response to the request from a node of the distributed lock manager where the request includes an echo of the local time included in the request. The response also indicates that a lock corresponding to a given resource has been granted to the client and the client subsequently utilizes the resource. The client subsequently determines that a safe period of time has elapsed for using the resource. This determination is dependent at least on a client staleness corresponding to a difference between the echoed time and current local time at the client.

Claims

1. A method, comprising:

one or more computer systems implementing a client of a distributed lock manager, the distributed lock manager comprising a plurality of nodes maintaining a shared state;

the client sending a request to the distributed lock manager, the request including a local time of the client;

the client receiving a response to the request from a node of the plurality of nodes, the response indicating that a lock corresponding to a given resource has been granted to the client, wherein the response also includes an echo of the local time that was included in the request;

the client utilizing the resource subsequent to receiving the response;

the client determining that a safe period of time has elapsed, said determining being dependent at least on a client staleness, the client staleness corresponding to a difference between the echoed local time and a current local time;

in response to determining that the safe period of time has elapsed, the client ceasing to utilize the resource, said ceasing being irrespective of whether the lock has been revoked from the client by the distributed lock manager.

2. The method as recited of claim 1, wherein said determining that a safe period of time has elapsed is further dependent on a given wait time of the distributed lock manager, wherein the distributed lock manager is configured to wait for at least the given wait time before revoking a granted lock.

3. The method as recited of claim 1, wherein the client determining the safe period of time is further dependent on a node staleness of the node, the node staleness corresponding to an age of data included in the response at a time when the response was sent.

4. The method as recited of claim 3, wherein the node staleness is indicated in the response.

5. The method as recited of claim 1, further comprising:

subsequent to ceasing to utilize the resource, the client receiving a revocation of the lock from the distributed lock manager; and

in response to receiving the revocation, the client conveying a release of the lock to the distributed lock manager.

6. The method as recited of claim 1, further comprising:

subsequent to ceasing to utilize the resource, the client receiving from the distributed lock manager an updated local time previously reported to the distributed lock manager by the client;

dependent upon the current local time of the client and the updated local time, the client newly determining whether a safe period of time for utilizing the resource has elapsed; and

in response to determining that the newly-determined safe period has not yet elapsed, the client resuming utilization of the resource.

7. The method as recited of claim 1, further comprising:

at intervals of time, the client conveying a heartbeat message to the distributed lock manager wherein the heartbeat message includes a timestamp indicative of a current local time at the client.

8. The method as recited of claim 7, further comprising:

in response to determining that the safe period of time has elapsed, the client ceasing to convey heartbeat messages to the distributed lock manager.

9. A non-transitory computer-readable storage medium storing program instructions executable by a processor to implement:

a client of a distributed lock manager, the distributed lock manager comprising a plurality of nodes maintaining a shared state, wherein the client is configured to;

send a request to the distributed lock manager, the request including a local time of the client;

receive a response to the request from a node of the plurality of nodes, the response indicating that a lock corresponding to a given resource has been granted to the client, wherein the response also includes an echo of the local time that was included in the request;

utilize the resource subsequent to receiving the response;

determine that a safe period of time has elapsed, said determining being dependent at least on a client staleness, the client staleness corresponding to a difference between the echoed local time and a current local time;

in response to determining that the safe period of time has elapsed, cease to utilize the resource, said ceasing being irrespective of whether the lock has been revoked from the client by the distributed lock manager.

10. The non-transitory computer-readable storage medium of claim 9, wherein said determining that a safe period of time has elapsed is further dependent on a given wait time of the distributed lock manager, wherein the distributed lock manager is configured to wait for at least the given wait time before revoking a granted lock.

11. The non-transitory computer-readable storage medium of claim 9, wherein the client determining the safe period of time is further dependent on a node staleness of the node, the node staleness corresponding to an age of data included in the response at a time when the response was sent.

12. The non-transitory computer-readable storage medium of claim 11, wherein the node staleness is indicated in the response.

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

subsequent to ceasing to utilize the resource, receive a revocation of the lock from the distributed lock manager; and

in response to receiving the revocation, convey a release of the lock to the distributed lock manager.

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

subsequent to ceasing to utilize the resource, receive from the distributed lock manager an updated local time previously reported to the distributed lock manager by the client;

dependent upon the current local time of the client and the updated local time, newly determine whether a safe period of time for utilizing the resource has elapsed; and

in response to determining that the newly-determined safe period has not yet elapsed, resume utilization of the resource.

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

at intervals of time, convey a heartbeat message to the distributed lock manager wherein the heartbeat message includes a timestamp indicative of a current local time at the client.

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

in response to determining that the safe period of time has elapsed, cease to convey heartbeat messages to the distributed lock manager.

17. A computer system comprising:

a processor;

a memory coupled to the processor and storing program instructions executable by the processor to implement;

a client of a distributed lock manager, the distributed lock manager comprising a plurality of nodes maintaining a shared state, wherein the client is configured to;

send a request to the distributed lock manager, the request including a local time of the client;

receive a response to the request from a node of the plurality of nodes, the response indicating that a lock corresponding to a given resource has been granted to the client, wherein the response also includes an echo of the local time that was included in the request;

utilize the resource subsequent to receiving the response;

determine that a safe period of time has elapsed, said determining being dependent at least on a client staleness, the client staleness corresponding to a difference between the echoed local time and a current local time;

in response to determining that the safe period of time has elapsed, cease to utilize the resource, said ceasing being irrespective of whether the lock has been revoked from the client by the distributed lock manager.

18. The system of claim 17, wherein said determining that a safe period of time has elapsed is further dependent on:

a given wait time of the distributed lock manager, wherein the distributed lock manager is configured to wait for at least the given wait time before revoking a granted lock; and

on a node staleness of the node, the node staleness corresponding to an age of data included in the response at a time when the response was sent.

19. The system of claim 17, wherein the client is further configured to perform:

at intervals of time, convey a heartbeat message to the distributed lock manager wherein the heartbeat message includes a timestamp indicative of a current local time at the client.

20. The system of claim 17, wherein the client is further configured to perform:

in response to determining that the safe period of time has elapsed, cease to convey heartbeat messages to the distributed lock manager.