Throttling queue for a request scheduling and processing system

• US 10,728,166 B2
• Filed: 06/27/2017
• Issued: 07/28/2020
• Est. Priority Date: 06/27/2017
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Balakrishnan, Venkates Paramasivam, Varadarajan, Krishnan
• Primary Examiner(s): Osman, Ramy M
• Assistant Examiner(s): Mendaye, Kidest
• Application Number:
  US15/634,938
• Publication Number:
  US 20180375784A1
• Time in Patent Office: 1,127 Days
• CPC Class Codes: H04L 47/621 Individual queue per connection or flow, e.g. per VC
• CPC Class Codes: H04L 47/627 policing
• CPC Class Codes: H04L 47/6275 based on priority
• CPC Class Codes: H04L 47/805 QOS or priority aware
• CPC Class Codes: H04L 47/822 Collecting or measuring resource availability data
• CPC Class Codes: H04L 47/83 based on usage prediction
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• CPC Class Codes: H04L 67/61 taking into account QoS or priority requirements

Abstract

Various methods and systems for implementing request scheduling and processing in a multi-tenant distributed computing environment are provided. Requests to utilize system resources in the distributed computing environment are stored in account queues corresponding to tenant accounts. If storing a request in an account queue would exceed a throttling threshold such as a limit on the number of requests stored per account, the request is dropped to a throttling queue. A scheduler prioritizes processing requests stored in the processing queue before processing requests stored in the account queues. The account queues can be drained using dominant resource scheduling. In some embodiments, a request is not picked up from an account queue if processing the request would exceed a predefined hard limit on system resource utilization for the corresponding tenant account. In some embodiments, the hard limit is defined as a percentage of threads the system has to process requests.

Claims

1. A system for scheduling and processing requests in a distributed computing environment, the system comprising:

account queues, each account queue being assigned to a corresponding tenant account of the distributed computing environment;

a throttling queue; and

a scheduler configured to;

populate the account queues with requests from the corresponding tenant accounts;

populate the throttling queue with requests for which storage in the account queues would cause a number of stored requests to exceed a throttling threshold;

prioritize processing requests from the throttling queue above processing requests from the account queues; and

determine not to pick up a request stored in one of the account queues based on a determination that processing the request would exceed a defined hard limit on resource usage for a corresponding one of the tenant accounts, wherein at least one of (i) the hard limit on resource usage is a limit on threads processing requests for the corresponding tenant account, or (ii) the hard limit on resource usage excludes resources utilized to process requests from the throttling queue.

2. The system of claim 1, wherein the throttling threshold is at least one of an account queue capacity or a system request capacity.

3. The system of claim 1, wherein the scheduler is additionally configured to prioritize account queues using dominant resource scheduling, wherein dominant resource scheduling provides fairness across multiple resources.

4. The system of claim 1, further comprising a pre-processing queue, wherein the scheduler is configured to prioritize the pre-processing queue over the throttling queue.

5. A computer-implemented method for scheduling and processing requests in a distributed computing environment, the method comprising:

receiving a plurality of requests to utilize one or more resources in the distributed computing environment, the plurality of requests directed to corresponding account queues for tenant accounts of the distributed computing environment;

determining whether storing each request of the plurality of requests in its corresponding account queue would cause a number of stored requests to exceed a throttling threshold;

storing a first subset of requests of the plurality of requests that would not cause the number of stored requests to exceed the throttling threshold in their corresponding account queue;

storing a second subset of requests of the plurality of requests that would cause the number of stored requests to exceed the throttling threshold in a throttling queue;

processing the plurality of requests based on a queue prioritization scheme that prioritizes processing requests stored in the throttling queue before processing requests from the account queues; and

determining not to pick up a request stored in one of the account queues based on a determination that processing the request would exceed a defined hard limit on resource usage, distinct from the throttling threshold, for a corresponding one of the tenant accounts, wherein at least one of (i) the hard limit on resource usage is a limit on threads processing requests for the corresponding tenant account, or (ii) the hard limit on resource usage excludes resources utilized to process requests from the throttling queue.

6. The method of claim 5, wherein the throttling threshold is at least one of an account queue capacity or a system request capacity.

7. The method of claim 5, wherein the queue prioritization scheme additionally prioritizes the account queues using dominant resource scheduling, wherein dominant resource scheduling provides fairness across multiple resources.

8. The method of claim 5, wherein the queue prioritization scheme additionally prioritizes draining a pre-processing queue before processing requests from the throttling queue.

9. One or more computer storage media having computer-executable instructions embodied thereon that, when executed, by one or more processors, causes the one or more processors to perform a method for scheduling and processing requests in a distributed computing environment, the method comprising:

storing in a pre-processing queue incoming requests to utilize one or more resources in the distributed computing environment;

storing in account queues requests generated by corresponding tenant accounts of the distributed computing environment;

storing in a throttling queue requests that would exceed a throttling threshold;

assigning worker threads based on a queue prioritization scheme comprising a first priority tier for draining the pre-processing queue, a second priority tier for processing requests stored in the throttling queue and third priority tier for processing requests stored in the account queues; and

determining not to pick up a request stored in one of the account queues based on a determination that processing the request would exceed a defined hard limit on resource usage, distinct from the throttling threshold, for a corresponding one of the tenant accounts, wherein at least one of (i) the hard limit on resource usage is a limit on threads processing requests for the corresponding tenant account, or (ii) the hard limit on resource usage excludes resources utilized to process requests from the throttling queue.

10. The media of claim 9, wherein the throttling threshold is at least one of an account queue capacity or a system request capacity.

11. The media of claim 9, wherein the third priority tier of the queue prioritization scheme prioritizes the account queues using dominant resource scheduling, wherein dominant resource scheduling provides fairness across multiple resources.