System and method for avoiding system overload by maintaining an ideal request rate

• US 8,429,282 B1
• Filed: 03/22/2011
• Issued: 04/23/2013
• Est. Priority Date: 03/22/2011
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Ahuja, Sohel R., McHugh, Jason G.
• Primary Examiner(s): Luu, Le H
• Application Number:
  US13/069,139
• Time in Patent Office: 763 Days
• Field of Search: 709/229, 709/224, 709/225, 709/226, 709/219, 714/55, 707/769, 705/34, 705/8, 370/230.1, 718/103
• US Class Current: 709/229
• CPC Class Codes: G06F 2209/504 Resource capping
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: H04L 12/6418 Hybrid transport
• CPC Class Codes: H04L 47/19 at layers above the network layer network arrangements for networked applications for scheduling or organising the servicing of application requests H04L67/60
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A computer system that provides services to clients may adaptively throttle incoming service requests in order to reach and then maintain operation at an ideal request rate. An ideal request rate may be a maximum rate at which incoming service requests can be serviced such that client-specified quality of service (QoS) expectations are met for most or all incoming service requests, or a rate within a range of rates defined by that maximum rate. Determining whether the system is operating at an ideal request rate may include determining the minimum difference between the expected and actual QoS for a group of recently serviced requests. The system may gradually modify a throttle multiplier value in order to reach or maintain an ideal request rate. Maintaining operation at an ideal request rate may allow the system to avoid entering an overloaded state, and/or oscillating between an overloaded state and a non-overloaded state.

Claims

1. A method, comprising:

performing, by a computer system that provides services to clients;

receiving a plurality of incoming service requests;

determining that the computer system is in an overloaded state with respect to the incoming service requests;

in response to determining that the computer system is in an overloaded state, throttling incoming service requests by an aggressive amount;

subsequent to aggressively throttling incoming service requests, determining that the computer system is no longer in an overloaded state; and

in response to determining that the computer system is no longer in an overloaded state;

iteratively reducing throttling of incoming requests by an amount less than the aggressive amount by which incoming requests were throttled until an ideal request rate is reached, wherein an ideal request rate is a request rate within a pre-determined range of request rates that comprises a maximum rate at which incoming service requests can be accepted and serviced such that client-specified quality of service expectations are met for all incoming service requests that are accepted and serviced.

2. The method of claim 1, wherein said iteratively reducing comprises:

servicing one or more incoming service requests;

comparing the difference between a quality of service expectation and the actual quality of service for each of the one or more incoming service requests to a pre-determined ideal request rate threshold;

adjusting the amount of throttling dependent on said comparing; and

repeating said servicing, said comparing, and said adjusting until an ideal request rate is reached.

3. The method of claim 1, further comprising:

subsequent to reaching an ideal request rate, monitoring the servicing of incoming service requests to determine whether the computer system is no longer operating at an ideal request rate.

4. The method of claim 3, further comprising:

in response to determining that the computer system is no longer operating at an ideal request rate, adjusting the amount of throttling in an attempt to return to an ideal request rate.

5. A system, comprising:

one or more processors; and

a memory coupled to the one or more processors and storing program instructions that when executed by the one or more processors cause the one or more processors to perform;

receiving and servicing a plurality of incoming requests for a service on behalf of one or more clients;

determining whether the system is servicing incoming requests at an ideal request rate, wherein an ideal request rate is a request rate within a range of request rates bounded on one side by a maximum rate at which incoming service requests can be accepted and serviced such that client-specified quality of service expectations are met for a targeted percentage of incoming service requests that are accepted and serviced;

in response to determining that the system is not servicing incoming requests at an ideal request rate, modifying the amount of service request throttling performed by the system in an attempt to reach an ideal request rate.

6. The system of claim 5, wherein in response to determining that the system is accepting and servicing incoming service requests at a rate that is higher than an ideal request rate, said modifying comprises increasing the amount of service request throttling performed by the system by a pre-determined incremental amount.

7. The system of claim 5, wherein in response to determining that the system is accepting and servicing incoming service requests at a rate that is lower than an ideal request rate, said modifying comprises reducing the amount of service request throttling performed by the system by a pre-determined incremental amount.

8. The system of claim 5, wherein in response to determining that the system is operating in an overloaded state with respect to incoming service requests, said modifying comprises increasing the amount of service request throttling performed by the system by an amount that is aggressive enough to return the system to a non-overloaded state.

9. The system of claim 8, wherein when executed by the one or more processors, the program instructions further cause the one or more processors to perform:

in response to determining that the system has been returned to a non-overloaded state;

iteratively reducing throttling of incoming service requests by an amount less than the aggressive amount by which incoming requests were throttled until an ideal request rate is reached.

10. The system of claim 9, wherein said iteratively reducing comprises:

servicing one or more incoming service requests;

comparing the difference between a quality of service expectation and the actual quality of service for each of the one or more incoming service requests to a pre-determined ideal request rate threshold;

adjusting the amount of throttling dependent on said comparing; and

repeating said servicing, said comparing, and said adjusting until an ideal request rate is reached.

11. The system of claim 5, wherein when executed by the one or more processors, the program instructions further cause the one or more processors to perform:

subsequent to said modifying, determining that the system is operating at an ideal request rate; and

monitoring the servicing of incoming service requests to determine whether the computer system is no longer operating at an ideal request rate.

12. The system of claim 11, wherein when executed by the one or more processors, the program instructions further cause the one or more processors to perform:

in response to determining that the computer system is no longer operating at an ideal request rate, adjusting the amount of throttling in an attempt to return to an ideal request rate.

13. The system of claim 5, wherein said determining whether the system is servicing incoming requests at an ideal request rate comprises:

determining the actual quality of service achieved in servicing each of a plurality of recently received service requests;

calculating the minimum difference between an expected quality of service and the actual quality of service achieved in servicing each of the plurality of recently received service requests; and

comparing the calculated minimum difference to a pre-determined ideal request rate threshold.

14. The system of claim 13, wherein the plurality of recently received service requests comprises service requests that were received within a moving window of time having a pre-determined length.

15. The system of claim 13, wherein the ideal request rate threshold is configurable at initialization of the system or during runtime.

16. The system of claim 5, wherein targeted percentage of incoming service requests is one hundred percent.

17. A method, comprising:

performing, by a computer system that provides services to clients;

initializing the value of a throttle multiplier to zero, wherein a throttle multiplier value of zero indicates that all incoming service requests should be serviced and no incoming service requests should be throttled;

servicing a plurality of incoming service requests;

determining whether the system was operating at an ideal request rate during said servicing, wherein an ideal request rate is a request rate within a pre-determined range of request rates that comprises a maximum rate at which incoming service requests can be accepted and serviced such that client-specified quality of service expectations are met for a targeted percentage of incoming service requests that are accepted and serviced;

in response to determining that the system was not operating at an ideal request rate, modifying the value of the throttle multiplier in an attempt to reach an ideal request rate.

18. The method of claim 17, wherein the plurality of incoming service requests comprises service requests that were received within a moving window of time having a pre-determined length.

19. The method of claim 17, wherein in response to determining that the computer system was accepting and servicing incoming service requests at a rate that is higher than an ideal request rate, said modifying comprises increasing the value of the throttle multiplier by a pre-determined incremental amount, wherein increasing the value of the throttle multiplier causes an increase in the percentage of incoming requests that are throttled.

20. The method of claim 17, wherein in response to determining that the computer system was operating in an overloaded state, said modifying comprises increasing the value of the throttle multiplier by an amount that is aggressive enough to return the computer system to a non-overloaded state.

21. The method of claim 20, further comprising:

in response to the computer system returning to a non-overloaded state, iteratively reducing the value of the throttle multiplier by an amount less than the aggressive amount by which it was increased until an ideal request rate is reached;

wherein said iteratively reducing comprises;

servicing one or more incoming service requests;

comparing the difference between a quality of service expectation and the actual quality of service for each of the one or more incoming service requests to a pre-determined ideal request rate threshold;

adjusting the value of the throttle multiplier dependent on said comparing; and

repeating said servicing, said comparing, and said adjusting until an ideal request rate is reached.

22. The method of claim 17, further comprising:

subsequent to said modifying, determining that the system is operating at an ideal request rate; and

monitoring the servicing of incoming service requests to determine whether the computer system is no longer operating at an ideal request rate.

23. The method of claim 17, wherein said determining whether the system was operating at an ideal request rate comprises:

determining the actual quality of service achieved in servicing each of the plurality of incoming service requests;

calculating the minimum difference between an expected quality of service and the actual quality of service achieved in servicing each of the plurality of incoming service requests; and

comparing the calculated minimum difference to a pre-determined ideal request rate threshold.

24. A non-transitory, computer-readable storage medium storing program instructions that when executed on one or more computers cause the one or more computers to perform:

initializing the value of a throttle parameter of a computer system that provides services to clients to a value that indicates that all incoming service requests should be serviced and no incoming service requests should be throttled;

determining whether the computer system is in an overloaded state with respect to incoming service requests;

in response to determining that the computer system is in an overloaded state, modifying the throttling parameter such that the system throttles incoming service requests by an aggressive amount;

subsequent to aggressively throttling incoming service requests, determining that the computer system is no longer in an overloaded state; and

in response to determining that the computer system is no longer in an overloaded state;

iteratively adjusting the value of the throttle parameter such that throttling of incoming requests is reduced by an amount less than the aggressive amount by which incoming requests were throttled until an ideal request rate is reached, wherein an ideal request rate is a request rate within a range of request rates whose upper bound is a maximum rate at which incoming service requests can be accepted and serviced such that client-specified quality of service expectations are met for all incoming service requests that are accepted and serviced.

25. The storage medium of claim 24, wherein said determining whether the system is servicing incoming requests at an ideal request rate comprises:

determining the actual quality of service achieved in servicing each of a plurality of recently received service requests;

calculating the minimum difference between an expected quality of service and the actual quality of service achieved in servicing each of the plurality of recently received service requests; and

comparing the calculated minimum difference to a pre-determined ideal request rate threshold.

26. The storage medium of claim 24, wherein said iteratively reducing comprises:

servicing one or more incoming service requests;

comparing the difference between a quality of service expectation and the actual quality of service for each of the one or more incoming service requests to a pre-determined ideal request rate threshold;

modifying the value of the throttle parameter dependent on said comparing; and

repeating said servicing, said comparing, and said modifying until an ideal request rate is reached.

27. The storage medium of claim 26, wherein one or more incoming service requests comprise service requests that were received within a moving window of time having a pre-determined length.

28. The storage medium of claim 24, wherein when executed on the one or more computers, the program instructions further cause the one or more computers to perform:

subsequent to reaching an ideal request rate, monitoring the servicing of incoming service requests to determine whether the computer system is no longer operating at an ideal request rate; and

in response to determining that the computer system is no longer operating at an ideal request rate, modifying the value of the throttle parameter in an attempt to return to an ideal request rate.

29. The storage medium of claim 28, wherein in response to determining that the computer system is accepting and servicing incoming service requests at a rate that is higher than an ideal request rate, said modifying comprises modifying the value of the throttle parameter such that the amount of service request throttling performed by the system is increased by a pre-determined incremental amount.

30. The storage medium of claim 28, wherein the ideal request rate threshold is configurable at initialization of the computer system or during runtime.