Task packing scheduling process for long running applications

• US 10,733,024 B2
• Filed: 05/24/2018
• Issued: 08/04/2020
• Est. Priority Date: 05/24/2017
• Status: Active Grant

• Current Assignee: Qubole Inc.
• Original Assignee: Qubole Inc.
• Inventors: Sarma, Joydeep Sen, Modi, Abhishek
• Primary Examiner(s): Wathen, Brian W
• Application Number:
  US15/988,535
• Publication Number:
  US 20180341524A1
• Time in Patent Office: 803 Days
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/4887 involving deadlines, e.g. rate based, periodic
• CPC Class Codes: G06F 9/505 considering the load
• CPC Class Codes: G06F 9/5072 Grid computing
• CPC Class Codes: G06F 9/5083 Techniques for rebalancing the load in a distributed system

Abstract

In general, the invention is directed to systems and methods of distributing tasks amongst servers or nodes in a cluster in a cloud-based big data environment, including: establishing a high_server_threshold; dividing active servers/nodes into at least three (3) categories of high usage servers, comprising servers on which usage is greater than the high_server_threshold; medium usage servers, comprising servers on which usage is less than the high_server_threshold, but is greater than zero; and low usage servers, comprising servers that are currently not utilized; receiving one or more tasks to be performed; scheduling the tasks by: first requesting that medium usage servers take tasks; if tasks remain that are not scheduled on the medium usage servers, schedule remaining tasks on low usage servers; if any tasks remain that are not scheduled on medium usage servers or low usage servers, scheduling remaining tasks on high usage servers.

Claims

1. A method of distributing tasks amongst servers or nodes in a cluster in a cloud-based big data environment, comprising:

establishing a high_server_threshold;

dividing active servers/nodes into at least three (3) categories comprising;

(i) high usage servers, comprising servers on which usage is greater than the high_server_threshold;

(ii) medium usage servers, comprising servers on which usage is less than the high_server_threshold, but is greater than zero; and

(iii) low usage servers, comprising servers that are currently not utilized;

receiving one or more tasks to be performed;

scheduling the received one or more tasks by;

first requesting that medium usage servers take the one or more tasks;

if tasks remain that are not scheduled on the medium usage servers, schedule remaining tasks on low usage servers;

if any tasks remain that are not scheduled on medium usage servers or low usage servers, scheduling remaining tasks on high usage servers.

2. The method of claim 1, wherein the high_server_threshold is approximately sixty percent (60%).

3. The method of claim 1, wherein the high_server_threshold is approximately eighty percent (80%).

4. The method of claim 1, wherein the method is initiated after the cluster is above a minimum size.

5. The method of claim 1, wherein for new clusters that have not begun processing where all servers have zero utilization, the division of servers into medium usage servers and low usage servers is arbitrary or governed by external considerations including cost.

6. The method of claim 1, wherein task assignment to medium usage servers takes into account any resource requirements and any locality constraints.

7. The method of claim 1, wherein tasks assigned to medium usage servers are assigned evenly so that each medium usage server is allocated substantially the same amount of tasks.

8. The method of claim 1, wherein before tasks are scheduled to a low usage server, a locality delay may be used.

9. The method of claim 1, wherein selection of low usage servers for task assignment may be arbitrary or random, or may be governed by external considerations including cost.

10. The method of claim 1, wherein selection of high usage servers may be given to high usage servers with lower usage, to avoid hot-spots.

11. The method of claim 1, wherein the method has no impact on upscaling of the system.

12. The method of claim 1, wherein the method may be disabled if system downscaling results in the cluster being set to a minimum size.

13. The method of claim 1, further comprising determining if any task has been in a queue for an undesirably long period of time, and assigning such task to a first available server.

14. The method of claim 1, further comprising task rescheduling, comprising periodically stopping and restarting tasks, thereby automatically rescheduling tasks.

15. The method of claim 1, further comprising rescheduling tasks by identifying more optimal servers and migrating tasks to identified more optimal servers.

16. A method of distributing tasks amongst servers or nodes in a cluster in a cloud-based big data environment, comprising:

establishing a high_server_threshold;

dividing active servers/nodes into at least three (3) categories comprising;

high usage servers, comprising servers on which usage is greater than the high_server_threshold;

(ii) medium usage servers, comprising servers on which usage is less than the high_server_threshold, but is greater than zero; and

(iii) low usage servers, comprising servers that are currently not utilized;

receiving one or more tasks to be performed;

scheduling the received one or more tasks by;

first requesting that high usage servers take the one or more tasks;

if tasks remain that are not scheduled on the high usage servers, schedule remaining tasks on medium usage servers;

if any tasks remain that are not scheduled on high usage servers or medium usage servers, scheduling remaining tasks on low usage servers.

17. The method of claim 16, wherein the high_server_threshold is approximately eighty percent (80%).

18. The method of claim 16, further comprising sorting a list from high to low each category of active servers/nodes by the number tasks each has running for a specific application, and wherein tasks are scheduled in each category of servers/nodes into the first available server/node in this sorted list.

19. A method of distributing tasks for a specific application amongst servers or nodes in a cluster in a cloud-based big data environment, the method having no impact on upscaling of the system and initiated after the cluster is above a minimum size and disabled when the cluster is at a minimum size, the method comprising:

establishing a high_server_threshold;

dividing active servers/nodes into at least three (3) categories comprising;

(i) high usage servers, comprising servers on which usage is greater than the high_server_threshold;

(ii) medium usage servers, comprising servers on which usage is less than the high_server_threshold, but is greater than zero; and

(iii) low usage servers, comprising servers that are currently not utilized;

receiving one or more tasks to be performed;

scheduling the received one or more tasks by;

first requesting that medium usage servers take the one or more tasks, wherein medium usage servers are assigned tasks in accordance with any applicable resource requirement or locality constraint, and wherein such tasks are assigned evenly so that each medium usage server is allocated substantially the same amount of tasks;

if tasks remain that are not scheduled on the medium usage servers, schedule remaining tasks on low usage servers, wherein such scheduling on low usage servers is performed after a locality delay;

if any tasks remain that are not scheduled on medium usage servers or low usage servers, scheduling remaining tasks on high usage servers; and

if any task has been in a queue for an undesirably long period of time, such task is assigned to a first available server.

20. The method of claim 19, further comprising sorting a list from high to low each category of active servers/nodes by the number tasks each has running for the specific application, and wherein tasks are scheduled in each category of servers/nodes into the first available server/node in this sorted list.