THROTTLING QUEUE FOR A REQUEST SCHEDULING AND PROCESSING SYSTEM

• US 20180375784A1
• Filed: 06/27/2017
• Published: 12/27/2018
• 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
• Granted Patent: US 10,728,166 B2
• Time in Patent Office: 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 that would exceed a throttling threshold; and

prioritize processing requests from the throttling queue above processing requests from the account queues.

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, wherein the scheduler is additionally configured not to pick up a request stored in an account queue if processing the request would exceed a defined hard limit on resource usage for the corresponding tenant account.

5. The system of claim 4, wherein the hard limit on resource usage is a limit on threads processing requests for the corresponding tenant account.

6. The system of claim 4, wherein the hard limit on resource usage excludes resources utilized to process requests from the throttling queue.

7. 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.

8. 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 exceed a throttling threshold;

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

storing a second subset of requests of the plurality of requests that would exceed the throttling threshold in a throttling queue; and

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.

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

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

11. The method of claim 8, wherein a request stored in an account queue is not picked up if processing the request would exceed a defined hard limit on resource usage for the corresponding tenant account.

12. The method of claim 11, wherein the hard limit on resource usage is a limit on threads processing requests for the corresponding tenant account.

13. The method of claim 11, wherein the hard limit on resource usage excludes resources utilized to process requests from the throttling queue.

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

15. 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; and

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.

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

17. The media of claim 15, 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.

18. The media of claim 15, wherein a request stored in an account queue is not picked up if processing the request would exceed a defined hard limit on resource usage for the corresponding tenant account.

19. The media of claim 18, wherein the hard limit on resource usage is a limit on threads processing requests for the corresponding tenant account.

20. The media of claim 18, wherein the hard limit on resource usage excludes resources utilized to process requests from the throttling queue.