US 8,190,593 B1Granted

Dynamic request throttling

AssigneeA9.com, Inc.

InventorPeter J. Dean

Life of this patent

Estimating the term…

Loading patent…

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.

Claims23

Dependent claims

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.

13 more elements

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.

3 more elements

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.

5 more elements

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.

2 more elements

Dependencies are inferred from the claim text.