Load balancing in a distributed computing environment

• US 7,970,861 B2
• Filed: 11/18/2009
• Issued: 06/28/2011
• Est. Priority Date: 11/18/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Shankar, Ramesh, Simitci, Huseyin, Ogus, Aaron W.
• Primary Examiner(s): Elchanti; Hussein A
• Application Number:
  US12/620,778
• Publication Number:
  US 20110119328A1
• Time in Patent Office: 587 Days
• Field of Search: 709223-226, 709/217
• US Class Current: 709/217
• CPC Class Codes: G06F 2206/1012 Load balancing
• CPC Class Codes: G06F 2209/5022 Workload threshold
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 9/505 considering the load

Abstract

Systems, methods, and computer storage media for load balancing at a client device in a distributed computing environment based on a dynamic validity duration and utilization metrics of one or more data stores are provided. The client device selects a data store from a plurality of data stores that each maintains a copy of a datum. The selection of data stores by a client is based on utilization metrics of the data stores. The utilization metrics are stored at the client. A data store determines if a request for a particular datum may be fulfilled within a validity period associated with a request from the client. The validity period is dynamically changed by the client across multiple requests to aid in the load balancing process. Additionally, a gossip protocol may be used to propagate utilization metrics of a plurality of data stores across the system.

Claims

1. A method for load balancing at a client device in a distributed computing environment based on a dynamic validity period and utilization metrics, the method comprising:

at the client device, selecting a first data store from a plurality of data stores that maintain a copy of a particular datum, wherein the client device maintains utilization metrics describing utilization of resources within the first data store;

communicating a first request having a valid period of a first duration, wherein the first request is a request to the first data store for the particular datum;

receiving, from the first data store, a first response to the first request, wherein the first response indicates an inability of the first data store to fulfill the first request within the first duration;

in response to receiving the first response to the first request, selecting a second data store from the plurality of data stores; and

communicating a second request for the particular datum to the second data store, wherein the second request has a valid period with a second duration.

2. The method of claim 1, further comprising receiving, at the client device, updates of utilization metrics for each of the plurality of data stores through a gossip protocol.

3. The method of claim 2, wherein the first data store is selected from the plurality of data stores based on an analysis of the utilization metrics for each of the plurality of data stores.

4. The method of claim 1, wherein the client device is a front-end server of the distributed computing environment.

5. The method of claim 1, wherein the second duration is longer than the first duration.

6. The method of claim 1, wherein the inability of the first data store to fulfill the first request within the first duration is a predictive determination based on utilization metrics at the first data store.

7. The method of claim 1, wherein the inability of the first data store to fulfill the first request within the first duration is a based on the expiration of the first duration.

8. The method of claim 1, wherein the first response includes utilization metrics of the second data store.

9. The method of claim 8, wherein selecting the second data store from the plurality of data stores is based, at least in part, on the utilization metrics of the second data store.

10. The method of claim 1, wherein the valid period having a first duration is a time-out value associated with the first request.

11. A method for load balancing at a client device in a distributed computing environment based on a dynamic validity duration and utilization metrics, the method comprising:

at a client device, receiving a request from a service for a datum, wherein the datum is data used as part of a service available by way of the distributed computing environment;

identifying a first data store to serve the datum, wherein the first data store is identified from a plurality of data stores based on utilization metrics of the first data store that are stored at the client device;

communicating a first request for the datum to the first data store, wherein the first request includes a validity period with a first duration;

receiving a response to the first request as a result of the first data store predicting that the first request would be unable to be fulfilled within the first duration, wherein the first response includes utilization metrics of one or more of the plurality of data stores;

identifying a second data store to serve the datum, wherein the second data store is identified based, at least in part, on utilization metrics of at least one of the plurality of data stores; and

communicating a second request for the datum to the second data store, wherein the second request includes a validity period with a duration longer than the first duration.

12. One or more computer storage media comprising at least one memory having computer-executable instructions embodied thereon, that when executed by a computing system having a processor and memory, cause the computing system to perform a method for load balancing at a client device in a distributed computing environment based on a dynamic validity period and utilization metrics, the method comprising:

at the client device, selecting a first data store from a plurality of data stores that maintain a copy of a particular datum, wherein the client device maintains utilization metrics describing utilization of resources within the first data store;

communicating a first request having a valid period of a first duration, wherein the first request is a request to the first data store for the particular datum;

receiving, from the first data store, a first response to the first request, wherein the first response indicates an inability of the first data store to fulfill the first request within the first duration;

in response to receiving the first response to the first request, selecting a second data store from the plurality of data stores; and

communicating a second request for the particular datum to the second data store, wherein the second request has a valid period with a second duration.

13. The media of claims 12, wherein the method further comprising receiving, at the client device, updates of utilization metrics for each of the plurality of data stores through a gossip protocol.

14. The media of claim 13, wherein the first data store is selected from the plurality of data stores based on an analysis of the utilization metrics for each of the plurality of data stores.

15. The media of claim 12, wherein the client device is a front-end server of the distributed computing environment.

16. The media of claim 12, wherein the second duration is longer than the first duration.

17. The media of claim 12, wherein the inability of the first data store to fulfill the first request within the first duration is a predictive determination based on utilization metrics at the first data store.

18. The media of claim 12, wherein the inability of the first data store to fulfill the first request within the first duration is a based on the expiration of the first duration.

19. The media of claim 12, wherein the first response includes utilization metrics of the second data store.

20. The media of claim 19, wherein selecting the second data store from the plurality of data stores is based, at least in part, on the utilization metrics of the second data store.