Dynamic request throttling

• US 8,190,593 B1
• Filed: 04/14/2010
• Issued: 05/29/2012
• Est. Priority Date: 04/14/2010
• Status: Expired due to Fees

• Current Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Original Assignee: A9.com Incorporated (Amazon.com, Inc.)
• Inventors: Dean, Peter J.
• Primary Examiner(s): Mahmoudi, Tony
• Assistant Examiner(s): Khoshnoodi, Fariborz
• Application Number:
  US12/760,459
• Time in Patent Office: 776 Days
• Field of Search: 707/707, 707/708
• US Class Current: 707/707
• CPC Class Codes: G06F 16/90335 Query processing
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• 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: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

Requests for resources can be throttled based on relative allocations, whereby the actual usage of a client or sub-client over time can be monitored in order to make intelligent throttling decisions. A centralized throttling service can maintain throttling information according to a hierarchical allocation tree, and can determine whether to throttle a request based at least in part whether any tokens, or available resource units, are available for a class or node of the tree corresponding to the request. In some cases, an empty token bucket for a node can borrow tokens from a parent node, in order to allow a user to exceed an allocation when the capacity of the system allows for such usage. When a user has been exceeding an allocation or otherwise inappropriately taxing various resources, the system can prevent that user from borrowing tokens for at least a specified period of time.

Claims

1. A computer-implemented method of enabling a user to search for content, comprising:

under control of one or more computer systems configured with executable instructions,

receiving a search request including a search query and identifying information for at least user associated with the search request;

classifying the search request to correspond to a matching node of a hierarchical allocation tree comprising a plurality of nodes, each node having an assigned usage allocation with respect to a type of resource;

determining whether the matching node indicates available capacity, within the usage allocation for the matching node, to process the request, the available capacity of the matching node being based at least in part upon periodic notifications provided by each instance of the type of resource available to process received search requests; and

when the matching node indicates available capacity;

sending the search query in parallel to each of a plurality of partition servers, each partition server configured to execute the search query against a respective portion of a search index;

collating search results from each partition server; and

providing the collated search results in response to the received search request; and

when the matching node does not indicate available capacity;

determining whether the matching node is configured to borrow capacity from at least parent node in the hierarchical allocation tree;

determining whether at least one parent node from which the matching node is able to borrow capacity indicates available capacity, within a respective usage allocation, to process the request when the matching node is configured to borrow capacity; and

sending the search query in parallel to each of a plurality of partition servers for locating search results to return in response to the search request when at least one parent node from which the matching node is able to borrow capacity indicates available capacity.

2. The computer-implemented method of claim 1, further comprising:

determining whether a recent behavior of the user exceeds an allowable usage threshold; and

when the recent behavior exceeds the allowable usage threshold, returning a response to the at least one user without executing the search query.

3. The computer-implemented method of claim 1, wherein the nodes of the hierarchical allocation tree indicate available capacity using a plurality of tokens, each token representing a unit of capacity of a type of resource.

4. A computer-implemented method of managing access to at least one resource, comprising:

under control of one or more computer systems configured with executable instructions,

receiving a request to access a type of resource, the request including identifying information for at least one user associated with the request;

determining for the request a matching class from a plurality of classes, each class corresponding to a node of a hierarchical allocation tree and having an assigned usage allocation with respect to the type of resource, an available capacity of each of the classes determined at least in part based on the assigned usage allocation and periodic notifications provided by each instance of the type of resource indicating capacity of the instance;

when the matching class has available capacity to process the request, granting access to the type of resource, forwarding information for the request to at least one instance of the type of resource, and returning a response including information obtained from said access; and

when the matching class corresponds to a matching node in the hierarchical allocation tree that does not indicate available capacity, determining whether the matching node is configured to borrow capacity from at least parent node in the hierarchical allocation tree and, when the matching node is configured to borrow capacity, determining whether at least one parent node from which the matching node is able to borrow capacity indicates available capacity, within a respective usage allocation, to process the request.

5. The computer-implemented method of claim 4, further comprising:

when access to the type of resource is granted and information is obtained from the access, storing behavior information for the at least one user including at least an amount of capacity of the resource instance needed to process the information for the request, behavior information for each user being stored for each received request from the user for at least a recent period of time.

6. The computer-implemented method of claim 5, further comprising:

determining whether a recent behavior of the at least one user exceeds an allowable usage threshold based at least in part upon the stored behavior information; and

when the recent behavior exceeds the allowable usage threshold, returning a response to the at least one user without executing the request.

7. The computer-implemented method of claim 4, wherein the at least one user includes at least a user initiating the request and any intermediate service forwarding the request.

8. The computer-implemented method of claim 4, where the assigned usage allocation for each class is a percentage or fraction of a current capacity of the type of resource, the current capacity being determined at least in part based on the periodic notifications provided by each instance of the type of resource.

9. The computer-implemented method of claim 4, wherein the nodes of the hierarchical allocation tree indicate available capacity using a plurality of tokens, each token representing a unit of capacity of the type of resource.

10. The computer-implemented method of claim 4, wherein the unit of capacity of the type of resource includes at least one of an amount of processing capacity, processor utilization, memory capacity, I/O resources, disk capacity, resource connections, threads, processes, or system-level resources.

11. The computer-implemented method of claim 4, wherein forwarding information for the request to at least one instance of the type of resource comprises sending the information for the request in parallel to each of a plurality of instances of the type of resource, and further comprising:

collating results from the plurality of instances to generate the information obtained from said access to be returned in response to the request.

12. The computer-implemented method of claim 4, wherein the periodic notifications provided by each instance of the type of resource comprise heartbeat messages sent at substantially regular intervals, each heartbeat message including at least capacity information for a type of resource.

13. The computer-implemented method of claim 12, wherein a determined capacity of the type of resource is automatically increased when a heartbeat message is received for a new instance, and

wherein the determined capacity of the type of resource is automatically decreases when a heartbeat message is not received from an instance for at least a threshold period of time.

14. The computer-implemented method of claim 4, wherein at least a portion of the classes are virtual classes that enable specific users to receive an allocation for the type of resource for at least a minimum period of time, the virtual class being discarded 4 after a period of inactivity.

15. The computer-implemented method of claim 4, wherein the at least one user includes at least one of an end user, service, or application.

16. A system for managing access to at least one resource, comprising:

a processor; and

a memory device including instructions that, when executed by the processor, cause the system to;

receive a request to access a type of resource, the request including identifying information for at least user associated with the request;

determine for the request a matching class from a plurality of classes, each class corresponding to a node of a hierarchical allocation tree and having an assigned usage allocation with respect to the type of resource, an available capacity of each of the classes determined at least in part based on the assigned usage allocation and periodic notifications provided by each instance of the type of resource indicating capacity of the instance;

when the matching class has available capacity to process the request, grant access to the type of resource, forward information for the request to at least one instance of the type of resource, and return a response including information obtained from said access; and

when the matching class corresponds to a matching node in the hierarchical allocation tree that does not indicate available capacity, determine whether the matching node is configured to borrow capacity from at least parent node in the hierarchical allocation tree and, when the matching node is configured to borrow capacity, determine whether at least one parent node from which the matching node is able to borrow capacity indicates available capacity, within a respective usage allocation, to process the request.

17. The system of claim 16, wherein the instructions when executed further cause the system to:

when access to the type of resource is granted and information is obtained from the access, store behavior information for the at least one user including at least an amount of capacity of the resource instance needed to process the information for the request, behavior information for each user being stored for each received request from the user for at least a recent period of time.

18. The system of claim 16, wherein the instructions when executed further cause the system to:

determine whether a recent behavior of the at least one user exceeds an allowable usage threshold based at least in part upon the stored behavior information; and

when the recent behavior exceeds the allowable usage threshold, return a response to the at least one user without executing the request.

19. The system of claim 16, wherein the assigned usage allocation for each class is a percentage or fraction of a current capacity of the type of resource, the current capacity being determined at least in part based on the periodic notifications provided by each instance of the type of resource.

20. A computer-readable storage medium storing instructions for managing access to at least one resource, the instructions when executed by a processor causing the processor to:

receive a request to access a type of resource, the request including identifying information for at least user associated with the request;

determine for the request a matching class from a plurality of classes, each class corresponding to a node of a hierarchical allocation tree and having an assigned usage allocation with respect to the type of resource, an available capacity of each of the classes determined at least in part based on the assigned usage allocation and periodic notifications provided by each instance of the type of resource indicating capacity of the instance;

when the matching class has available capacity to process the request, grant access to the type of resource, forward information for the request to at least one instance of the type of resource, and return a response including information obtained from said access; and

when the matching class corresponds to a matching node in the hierarchical allocation tree that does not indicate available capacity, determine whether the matching node is configured to borrow capacity from at least parent node in the hierarchical allocation tree and, when the matching node is configured to borrow capacity, determine whether at least one parent node from which the matching node is able to borrow capacity indicates available capacity, within a respective usage allocation, to process the request.

21. The computer-readable storage medium of claim 20, wherein the instructions when executed further cause the system to:

when access to the type of resource is granted and information is obtained from the access, store behavior information for the at least one user including at least an amount of capacity of the resource instance needed to process the information for the request, behavior information for each user being stored for each received request from the user for at least a recent period of time.

22. The computer-readable storage medium of claim 20, wherein the instructions when executed further cause the system to:

determine whether a recent behavior of the at least one user exceeds an allowable usage threshold based at least in part upon the stored behavior information; and

when the recent behavior exceeds the allowable usage threshold, return a response to the at least one user without executing the request.

23. The computer-readable storage medium of claim 20, where the assigned usage allocation for each class is a percentage or fraction of a current capacity of the type of resource, the current capacity being determined at least in part based on the periodic notifications provided by each instance of the type of resource.