Scalable leases

• US 7,650,514 B2
• Filed: 12/30/2005
• Issued: 01/19/2010
• Est. Priority Date: 12/30/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Douceur, John R., Howell, Jonathan R.
• Primary Examiner(s): Revak; Christopher A
• Application Number:
  US11/275,435
• Publication Number:
  US 20070156588A1
• Time in Patent Office: 1,481 Days
• Field of Search: None
• US Class Current: 713/193
• CPC Class Codes: G06F 12/0844 Multiple simultaneous or quasi-simultaneous cache accessing
• CPC Class Codes: G06F 2209/522 Manager
• CPC Class Codes: G06F 2209/523 Mode
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms
• CPC Class Codes: G06Q 20/3674 involving authentication

Abstract

Scalable leases reduce latency and reduce the burden on a server in managing data leases. Instead of processing individual lease requests for clients seeking access to the same data, scalable leases provide for blanket leases that all of the clients can use to access the selected data. Leases may be encrypted or selectively distributed to restrict access to the data. Moreover, distributed data structures may be used to cache leases at identifiable nodes in a network to offload work from the server without all clients in the network having to cache all blanket leases issued. Thresholds for issuing blanket leases may be determined or adjusted by considerations such as demand for the selected data and server workload. Similarly, leases may be renewed on the basis of demand for selected data, conflicting lease requests, and other factors. Scalable leases may be issued for read leases and controlled write leases.

Claims

1. A computer-implemented method implemented by a computing device having a processor executing instructions stored in a computer-readable storage media, the method comprising:

receiving, by the computing device, one or more lease requests for access to selected data, wherein the computing device manages access to the selected data based upon issuance of leases to client computers requesting to access the selected data, wherein each lease issued specifies a period of time during which a client computer has access to the data during which period of time the selected data will not be changed by another entity;

in response to receiving a request from one of the client computers for a lease to access the selected data having access managed by the computing device, preparing a blanket scalable lease to be used by more than one client computer to concurrently access the selected data having access managed by the computing device; and

issuing the scalable lease by the computing device to a plurality of the client computers for the plurality of client computers to use the scalable lease for accessing the selected data for the specified period of time during which the selected data is not changed.

2. A method of claim 1, further comprising:

recognizing a request threshold representing a number of lease requests received from the client computers for accessing the selected data, wherein prior to reaching the request threshold, the computing device issues individual leases to particular client computers requesting access to the selected data having access managed by the computing device, wherein when the number of lease requests is at or beyond the request threshold, the computing device issues the scalable lease for the plurality of client computers to use the scalable lease to access the selected data having access managed by the computing device; and

upon reaching the request threshold for requests received from the client computers to access the selected data, issuing the scalable lease by the computing device.

3. A method of claim 2, further comprising changing the request threshold based on at least one of:

demand from the client computers for access to the selected data having access managed by the computing device;

demand on the computing device responsible for responding to the lease requests from the client computers;

an expiration time for the scalable lease; and

likelihood of demand from the client computers for the selected data having access managed by the computing device based on prior demand from the client computers for the selected data.

4. A method of claim 1, further comprising:

identifying, by the computing device managing access to the selected data, when access to the selected data is limited to authorized client computers;

providing the scalable lease, by the computing device, to the authorized client computers for enabling a plurality of the authorized client computers to use the scalable lease to access the selected data having access managed by the computing device, wherein the providing the scalable leased is performed by one of;

encrypting, by the computing device, the scalable lease wherein only the authorized client computers are capable of decrypting the scalable lease following the encrypting; and

providing the scalable lease, by the computing device, only to the authorized client computers by selectively multi-casting the scalable lease via a logical multi-cast tree including only client computers for which the scalable lease is intended.

5. A method of claim 1, further comprising

broadcasting the scalable lease to all client computers.

6. A method of claim 1, further comprising distributing the scalable lease using a distributed data structure, including:

transmitting the scalable lease, by the computing device, to at least one client computer that caches the scalable lease as a caretaking node from which other client computers obtain the scalable lease without sending a request to the computing device managing access to the selected data;

configuring the caretaking node to cache the scalable lease on behalf of the other client computers; and

making the caretaking node identifiable to the other client computers potentially seeking to obtain the scalable lease for accessing the selected data, wherein the other client computers obtain the scalable lease from the caretaking node without send a request to the computing device managing access to the selected data.

7. A method of claim 1, further comprising distributing the scalable lease by the computing device by multi-casting the sealable lease to a subset of the client computers, wherein the subset of client computers are configured to forward the scalable lease to additional client computers for enabling the additional client computers to use the scalable lease for accessing the selected data having accessed managed by the computing device.

8. A method of claim 1, further comprising selectively renewing the scalable lease, by the computing device, prior to an expiration time of the scalable lease, wherein a determination to selectively renew the lease includes the computing device considering at least one of:

a number of requests received by the computing device for accessing the selected data having access managed by the computing device;

a number of times the scalable lease has been renewed by the computing device;

indication of a lack of continuing demand for access to the selected data; and

receipt, by the computing device, of a request by one of the client computers for a lease conflicting with the scalable lease.

9. A method of claim 1, further comprising:

receiving a request for a conflicting lease that conflicts with the scalable lease;

transmitting a hold request message by the computing device to the client computers requesting that the client computers not send further lease requests or lease renewal requests during an interval during which the request for the conflicting lease will be honored;

issuing, by the computing device, the conflicting lease to one of the client computers requesting the conflicting lease for a predetermined period of time;

after the conflicting lease is returned or expires, issuing, by the computing device, a new scalable lease used by a plurality of the client computers for gaining concurrent access by the plurality of client computers to the selected data.

10. A method of claim 1, wherein the scalable lease includes one of:

a blanket read lease;

a black-box lease, wherein the black box lease enables a plurality of client computers party to the black box lease to use the black box lease to access the selected data and write to the selected data; and

a controlled write lease configured to allow the selected data to be accessed by multiple client computers while preventing conflicting writes to the selected data.

11. Computer-readable storage media having a computer readable program code embodied therein, the computer readable program code adapted to be executed by one or more processors to implement a method allowing concurrent access to data over a network, the method comprising:

configuring a server computing device to issue a blanket scalable lease used by a plurality of client computers for allowing more than one client computer to concurrently access selected data managed by the server computing device, wherein the scalable lease enables the plurality of client computers to access the selected data managed by the server computing device for a specified period of time during which the selected data is not changed by another entity;

distributing the scalable lease from the server computing device over the network to one or more of the client computers;

storing the scalable lease within one or more of the client computers on the network;

upon a plurality of the client computers subsequently seeking access to the selected data managed by the server computing device, using the scalable lease by the plurality of client computers to access the selected data managed by the server computing device.

12. The computer-readable storage media of claim 11, further comprising determining a request threshold specifying a number of requests for the selected data received by the server computing device, at or beyond which the scalable lease is issued instead of issuing an individual lease to a requesting client computer to permit access to the selected data managed by the server computing device.

13. The computer-readable storage media of claim 11, further comprising restricting access to the scalable lease to authorized client computers by distributing the scalable lease only to client computers authorized to access the selected data by selectively multi-casting the scalable lease via a logical multi-cast tree including only client computers for which the scalable lease is intended.

14. The computer-readable storage media of claim 11, wherein access to the scalable lease is restricted by encrypting the scalable lease, wherein only client computers authorized to access the selected data are capable of decrypting the scalable lease.

15. The computer-readable storage media of claim 11, further comprising distributing the scalable lease including at least one of:

broadcasting the scalable lease to all client computers;

multi-casting the scalable lease to a subset of the client computers that will forward the scalable lease to additional client computers;

selectively multi-casting the scalable lease via a logical multi-cast tree including only client computers for which the scalable lease is intended; and

distributing and storing the scalable lease using a distributed data structure allowing the client computers to determine where the scalable lease is stored and to obtain the scalable lease.

16. The computer-readable storage media of claim 11, further comprising selectively renewing the scalable lease prior to an expiration time of the scalable lease based upon

a number of requests received for the selected data;

a number of times the scalable lease has been renewed;

indication of a lack of continuing demand for the selected data; and

receipt of a request for a lease conflicting with the scalable lease.

17. The computer-readable storage media of claim 11, wherein the scalable lease includes one of:

a blanket read lease;

a black-box lease, wherein the black box lease enables a plurality of client computers party to the black box lease to use the black box lease to access the selected data and write to the selected data; and

a controlled write lease configured to be accessed by multiple client computers while preventing conflicting writes to the selected data.

18. A server comprising:

one or more processors; and

a memory containing instructions for configuring the one or more processors to control access to selected data managed by the server, wherein a plurality of client computers in communication with the server are configured to request access to the selected data by requesting a lease from the server for accessing the selected data for a period of time specified in the lease;

wherein the one or more processors are further configured to receive a request for access to the selected data from a first one of the client computers;

wherein the one or more processors are configured to issue an individual lease to the first client computer when a threshold for requests for issuing individual leases for access to the selected data has not been exceeded;

wherein the one or more processors are configured to receive a request for access to the selected data from a second one of the client computers, wherein the request from the second client computer is determined to exceed the threshold for requests for issuing individual leases for access to the selected data;

wherein following a determination that the threshold for requests for issuing individual leases is exceeded, the one or more processors are configured to issue a blanket scalable lease that is usable by the plurality of client computers for accessing the selected data;

wherein the scalable lease is distributed to the plurality of client computers for caching by the plurality of client computers, wherein the plurality of client computers use the scalable lease for accessing the selected data without having to request individual leases from the server.

19. The server of claim 18, wherein the one or more processors are further configured to broadcast the scalable lease to the plurality of client computers.

20. The server of claim 18, wherein the one or more processors are further configured to encrypt the scalable least prior to distributing the scalable lease to the plurality of client computers.