Method for automatic management of capacity and placement for global services

Patent metadata

Field	Value
Publication number	US-11057314-B1
Application number	US-201715797550-A
Country	US
Kind code	B1
Filing date	Oct 30, 2017
Priority date	Apr 16, 2014
Publication date	Jul 6, 2021
Grant date	Jul 6, 2021

Abstract

Systems and methods for providing web service instances to support traffic demands for a particular web service in a large-scale distributed system are disclosed. An example method includes determining a peak historical service load for the web service. The service load capacity for each existing web service instance may then be determined. The example method may then calculate the remaining service load after subtracting the sum of the service load capacity of the existing web service instances from the peak historical service load for the web service. The number of web service instances necessary in the large-scale distributed system may be determined based on the remaining service load. The locations of the web service instances may be determined and changes may be applied to the large-scale system based on the number of web service instances necessary in the large-scale distributed system.

First claim

The invention claimed is:

1. A computer-implemented method for creating new web service instances for a particular web service in a large-scale distributed system, the method comprising:
analyzing historical service load data to determine a total service load for the web service, wherein the web service is provided from assigned web service instances hosted by a plurality of datacenters included in the large-scale distributed system, each assigned web service instance having an existing service load capacity, and wherein the historical service load data is based at least in part on a model of data traffic assignments according to one or more load balancing rules;
determining whether a capacity needed to support the total service load is greater than the existing service load capacities of the assigned web service instances; and
when the capacity needed to support the total service load is greater than the existing service load capacities of the assigned web service instances, creating one or more new web service instances;
assigning a location score to each of a plurality of potential web service instance locations within the large-scale distributed system calculated, and
wherein assigning the location score for a given one of the plurality of potential web service instance locations includes multiplying a service load to be handled at the given one by a function of network distances associated with physical origins of service load traffic for the given one.

2. The method of claim 1 , wherein creating the one or more new web service instances is further based on the assigned location scores.

3. The method of claim 2 , wherein creating the one or more new web service instances further includes selecting a web service instance location for the one or more new web service instances from the plurality of potential web service instance locations based on the location scores.

4. The method of claim 3 , wherein determining the total service load for the web service includes subtracting a service load handled by the one or more new web service instances at the selected web service instance location from the total service load to be handled for the web service.

5. The method of claim 3 , wherein selecting the selected web service instance location includes selecting one of the plurality of potential web service instance locations having a highest location score.

6. The method of claim 2 , further comprising, determining the physical origins of web service traffic based on the historical service load data.

7. The method of claim 6 , wherein the service load for the given one corresponds to a number of queries that can be handled by the given one.

8. The method of claim 6 , wherein network distance is defined in time between the location of the given one and to the determined physical origins of service load traffic for the given one.

9. The method of claim 6 , further comprising determining one or more first location scores for each traffic source for the given one, and wherein the location score for the given one is determined further based on the one or more first location scores.

10. The method of claim 9 , further comprising, scaling each given one of the first location scores using a percentage of global traffic for the traffic source of the given one, and wherein the location score for the given one is determined further based on the scaled one or more first location scores.

11. The method of claim 9 , wherein the location score for the given one corresponds to a sum of the one or more first location scores.

12. The method of claim 1 , further comprising determining a storage dependency for running the web service.

13. The method of claim 1 , further comprising determining whether a second service is required for running the web service.

14. The method of claim 1 , further comprising determining a web service instance location for the one or more new web service instances based on a constraint on a maximum distance from a traffic source location to a nearest web service instance.

15. The method of claim 1 , further comprising determining a web service instance location for the one or more new web service instances based on a constraint on a round trip latency from a traffic source location to a nearest web service instance.

16. The method of claim 1 , wherein creating one or more new web service instances further comprises subtracting the service load capacity of the one or more new web service instances from the capacity needed to support the total service load, and wherein creating one or more new web service instances is repeated until the capacity needed to support the total service load is not greater than the existing service load capacities of the assigned web service instances.

17. A system for creating new web service instances for a particular web service in a large-scale distributed system, the system comprising:
one or more processing devices and
one or more storage devices storing instructions that, when executed by the one or more processing devices cause the one or more processing devices to:
analyze historical service load data to determine a total service load for the web service, wherein the web service is provided from assigned web service instances hosted by a plurality of datacenters included in the large-scale distributed system, each assigned web service instance having an existing service load capacity, and wherein the historical service load data is based at least in part on a model of data traffic assignments according to one or more load balancing rules;
determine whether a capacity needed to support the total service load is greater than the existing service load capacities of the assigned web service instances;
when the capacity needed to support the total service load is greater than the existing service load capacities of the assigned web service instances, create one or more new web service instances; and
assign a location score to each of a plurality of potential web service instance locations within the large-scale distributed system calculated, and
wherein to assign the location score for a given one of the plurality of potential web service instance locations includes multiplying a service load to be handled at the given one by a function of network distances associated with physical origins of service load traffic for the given one.

18. The system of claim 17 , wherein the instructions, when executed by the one or more processing devices cause the one or more processing devices to assign a location score to each of a plurality of potential web service instance locations within the large-scale distributed system calculated, and wherein creating the one or more new web service instances is further based on the assigned location scores.

19. The system of claim 18 , wherein creating the one or more new web service instances further includes selecting a web service instance location for the one or more new web service instances from the plurality of potential web service instance locations based on the location scores.

20. A system for providing a web service in a large-scale distributed system, the system comprising:
one or more processing devices and
one or more storage devices storing instructions that, when executed by the one or more processing devices cause the one or more processing devices to:
receive web service requests for the web service over a communication network;
route the respective web service requests to particular ones of a plurality of datacenters included in the l

Assignees

• Google Llc

Inventors

• Skalski Kamil
• Czajka Elzbieta
• Grzadkowski Filip
• Grygiel Krzysztof

Classifications

• H04L67/1001

  for accessing one among a plurality of replicated servers · CPC title

• H04L41/5083

  wherein the managed service relates to web hosting · CPC title

• H04L41/5054

  Automatic deployment of services triggered by the service manager, e.g. service implementation by automatic configuration of network components · CPC title

• G06F9/5083

  Techniques for rebalancing the load in a distributed system · CPC title

• H04L47/125

  by balancing the load, e.g. traffic engineering · CPC title