Systems and methods for allocating shared resources in multi-tenant environments

Patent metadata

Field	Value
Publication number	US-10965610-B1
Application number	US-202016789395-A
Country	US
Kind code	B1
Filing date	Feb 12, 2020
Priority date	Nov 10, 2017
Publication date	Mar 30, 2021
Grant date	Mar 30, 2021

Abstract

The disclosed computer-implemented method may include (1) for each tenant in a plurality of tenants within a multi-tenant service system, assigning a probability factor to the tenant that indicates a likelihood that the tenant will be selected when a resource of the multi-tenant service system is available, (2) detecting that the resource of the multi-tenant service system is available, (3) probabilistically selecting a tenant from the plurality of tenants by using the probability factors assigned to the tenants in the plurality of tenants, and (4) directing the multi-tenant service system to allocate the resource to the selected tenant for execution of a work item received from the selected tenant. Various other methods, systems, and computer-readable media are also disclosed.

First claim

What is claimed is:

1. A computer-implemented method comprising:
for each tenant in a plurality of tenants within a multi-tenant service system, assigning a probability factor to the tenant that indicates a likelihood that the tenant will be selected when a resource of the multi-tenant service system is available by determining a work value corresponding to the tenant based on:
a number of work items in a work item queue associated with the tenant that includes at least one enqueued work item; and
a cost factor representative of a cost of execution of the enqueued work item;

detecting that the resource of the multi-tenant service system is available;
probabilistically selecting a tenant from the plurality of tenants by using the probability factors assigned to the tenants in the plurality of tenants; and
directing the multi-tenant service system to allocate the resource to the selected tenant for execution of a work item received from the selected tenant.

2. The computer-implemented method of claim 1 , wherein determining the work value corresponding to the tenant is based on a weight factor corresponding to the tenant that indicates an importance of the tenant relative to at least one additional tenant in the plurality of tenants.

3. The computer-implemented method of claim 1 , wherein:
determining the work value corresponding to the tenant comprises tracking a recency factor corresponding to the tenant that is representative of a number of selections that have been made since the tenant was previously selected; and
determining the work value corresponding to the tenant is based on the tracked recency factor.

4. The computer-implemented method of claim 3 , wherein tracking the recency factor corresponding to the tenant comprises:
setting the recency factor corresponding to the tenant to a predetermined value when the tenant is selected; and
adding a predetermined amount to the recency factor corresponding to the tenant when a different tenant in the plurality of tenants is selected.

5. The computer-implemented method of claim 1 , wherein assigning the probability factor to the tenant comprises:
determining:
a sum of a plurality of work values, each work value in the plurality of work values corresponding to a different tenant in the plurality of tenants; and
a quotient of the work value corresponding to the tenant divided by the sum of the work values; and

designating the quotient as the probability factor corresponding to the tenant.

6. The computer-implemented method of claim 1 , wherein determining the work value corresponding to the tenant comprises:
calculating a product of:
a weight factor corresponding to the tenant that indicates an importance of the tenant relative to at least one additional tenant in the plurality of tenants,
a number of work items in the work item queue associated with the tenant;
a recency factor corresponding to the tenant that is representative of a number of selections that have been made since the tenant was previously selected; and

designating the calculated product as the work value corresponding to the tenant.

7. The computer-implemented method of claim 6 , wherein assigning the probability factor to the tenant further comprises determining:
a sum of a plurality of work values, each work value in the plurality of work values corresponding to a different tenant in the plurality of tenants; and
assigning the probability factor to the tenant is further based on the work value corresponding to the tenant and the sum of the plurality of work values.

8. The computer-implemented method of claim 7 , wherein probabilistically selecting the tenant from the plurality of tenants by using the probability factors assigned to the tenants in the plurality of tenants comprises:
randomly selecting a number based on the sum of the plurality of work values; and
mapping the randomly selected number to the tenant based on the work value corresponding to the tenant.

9. The computer-implemented method of claim 1 , wherein the resource of the multi-tenant service system comprises a worker of the multi-tenant service system that is configured to process a task associated with the work item.

10. The computer-implemented method of claim 1 , wherein detecting that the resource of the multi-tenant service system is available comprises:
tracking a usage of the resource of the multi-tenant service system; and
anticipating, based on the tracked usage of the multi-tenant service system, that the resource is likely to be available at a particular time.

11. A system comprising:
an assigning module, stored in memory, that, for each tenant in a plurality of tenants within a multi-tenant service system, assigning a probability factor to the tenant that indicates a likelihood that the tenant will be selected when a resource of the multi-tenant service system is available by determining a work value corresponding to the tenant based on:
a number of work items in a work item queue associated with the tenant that includes at least one enqueued work item; and
a cost factor representative of a cost of execution of the enqueued work item;

a detecting module, stored in memory, that detects that the resource of the multi-tenant service system is available;
a selecting module, stored in memory, that probabilistically selects a tenant from the plurality of tenants by using the probability factors assigned to the tenants in the plurality of tenants;
a directing module, stored in memory, that directs the multi-tenant service system to allocate the resource to the selected tenant for execution of a work item received from the selected tenant; and
at least one physical processor that executes the assigning module, the detecting module, the selecting module, and the directing module.

12. The system of claim 11 , wherein the assigning module determines the work value corresponding to the tenant based on a weight factor corresponding to the tenant that indicates an importance of the tenant relative to at least one additional tenant in the plurality of tenants.

13. The system of claim 11 , wherein:
the assigning module determines the work value corresponding to the tenant by tracking a recency factor corresponding to the tenant that is representative of a number of selections that have been made since the tenant was previously selected; and
determines the work value corresponding to the tenant based on the tracked recency factor.

14. The system of claim 13 , wherein the assigning module tracks the recency factor corresponding to the tenant by:
setting the recency factor corresponding to the tenant to a predetermined value when the tenant is selected; and
adding a predetermined amount to the recency factor corresponding to the tenant when a different tenant in the plurality of tenants is selected.

15. The system of claim 11 , wherein the assigning module assigns the probability factor to the tenant by:
determining:
a sum of a plurality of work values, each work value in the plurality of work values corresponding to a different tenant in the plurality of tenants; and
a quotient of the work value corresponding to the tenant divided by the sum of the work values; and

designating the quotient as the probability factor corresponding to the tenant.

16. The system of claim 11 , wherein the assigning module further determines the work value corresponding to the tenant by:
calculating a product of:
a weight factor corresponding to the tenant that indicates an importance of the tenant relative to at least one additional tenant in the plurality of tenants,
a n

Assignees

• Facebook Inc

Inventors

• Mchugh Jason George
• Mcduff Mark Warren

Classifications

• H04L47/70 Primary

  Admission control; Resource allocation · CPC title

• H04L67/10 Primary

  in which an application is distributed across nodes in the network (software deployment G06F8/60; multiprogramming arrangements G06F9/46) · CPC title

• H04L67/1001

  for accessing one among a plurality of replicated servers · CPC title

• G06F9/5072

  Grid computing · CPC title

• G06F9/50

  Allocation of resources, e.g. of the central processing unit [CPU] · CPC title