Method for automatic management capacity and placement for global services

Patent metadata

Field	Value
Publication number	US-9832138-B1
Application number	US-201514688689-A
Country	US
Kind code	B1
Filing date	Apr 16, 2015
Priority date	Apr 16, 2014
Publication date	Nov 28, 2017
Grant date	Nov 28, 2017

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

What is claimed is:

1. A computer-implemented method for providing web service instances to support traffic demands for a particular web service in a large-scale distributed system, the method comprising:
determining a peak historical service load for the web service;
determining service load capacity for each existing web service instance;
determining a sum of the service load capacities of the existing web service instances;
calculating a remaining service load after subtracting the sum of the service load capacities of the existing web service instances from the peak historical service load for the web service;
determining a number of additional web service instances based on the remaining service load;
determining locations for the additional web service instances; and
creating the additional web service instances at the determined locations of the large-scale distributed system.

2. The computer-implemented method of claim 1 , wherein the peak historical service load includes queries per second.

3. The computer-implemented method of claim 1 , wherein
creating the additional web service instances further comprises creating the additional web services instances to accommodate the remaining service load when the remaining service load is greater than zero.

4. The computer-implemented method of claim 1 further comprising
removing web service instances to remove excess service load capacity when the remaining service load is less than zero.

5. The computer-implemented method of claim 4 further comprising shutting down the number of web service instances to be removed from the large-scale distributed system.

6. A computer-implemented method for determining locations of web service instances for a particular web service in a large-scale distributed system, the method comprising:
analyzing historical service load to determine physical origins of web service traffic and a total service load for the web service, wherein the web service is provided from assigned web service instance locations, each assigned web service instance location having a service load capacity;
determining a sum of the service load capacities of the assigned web service instance locations;
determining whether a remaining total service load to be assigned to a web service instance location is greater than the sum of the existing service load capacities of the assigned web service instance locations; and
when a remaining total service load to be assigned to a web service instance location is greater than the sum of the existing service load capacities of the assigned web service instance locations:
assigning a potential web service instance location within the large-scale distributed system a location score calculated by multiplying a service load to be handled at each potential location by a decreasing function of network distance to the determined physical origin of service load traffic;
selecting a web service instance location from the potential web service instance locations by determining the potential web service instance location based on the location score; and
subtracting the service load handled by the selected web service instance location from the total service load to be handled for the web service; and
creating the web service instances in the selected web service instance locations.

7. A system for providing web service instances to support traffic demands 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:
determine a peak historical service load for the web service;
determine a service load capacity for each existing web service instance;
determine a sum of the service load capacities of the existing web service instances;
calculate a remaining service load after subtracting the sum of the service load capacities of the existing web service instances from the peak historical service load for the web service;
determine a number of additional web service instances based on the remaining service load;
determine locations for the additional web service instances; and
create the additional web service instances at the determined locations of the large-scale distributed system.

8. The system of claim 7 , wherein the peak historical service load includes queries per second.

9. The system of claim 7 , wherein
creating the additional web service instances further comprises creating the additional web service instances to accommodate the remaining service load when the remaining service load is greater than zero.

10. The system of claim 7 further comprising
removing web service instances to remove excess service load capacity when the remaining service load is less than zero.

11. The system of claim 10 further comprising shutting down the number of web service instances to be removed from the large-scale distributed system.

Assignees

• Google Inc
• Google Llc

Inventors

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

Classifications

• H04L47/783 Primary

  Distributed allocation of resources, e.g. bandwidth brokers · CPC title

• H04L67/1002

  Electricity · mapped topic

• H04L47/125

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

• G06F9/5083

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

• H04L67/1001

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