Systems and Methods for Caching Task Execution

• US 20170185448A1
• Filed: 12/28/2016
• Published: 06/29/2017
• Est. Priority Date: 12/29/2015
• Status: Active Grant

• Current Assignee: Capital One Services LLC (Capital One Financial Corporation)
• Original Assignee: Capital One Services LLC (Capital One Financial Corporation)
• Inventors: Tao, Tao, Bardwaj, Santosh, Kumar, Subodh, Eugley, Brian
• Granted Patent: US 10,394,600 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/5033 considering data affinity
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451
• CPC Class Codes: H04L 67/04 specially adapted for terminals or networks with limited capabilities; specially adapted for terminal portability
• 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/568 Storing data temporarily at an intermediate stage, e.g. caching
• CPC Class Codes: H04L 67/60 Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and optimisation of the required network resources admission control or resource allocation H04L47/70
• CPC Class Codes: H04L 67/61 taking into account QoS or priority requirements
• CPC Class Codes: H04L 67/63 Routing a service request depending on the request content or context

Abstract

Certain disclosed embodiments provide improved systems and methods for processing jobs. The method comprises steps including receiving, from a client device over a network, information representing a job and generating at least two tasks representative of the job. The method further comprises, for each task, assigning, by a processor, a signature to the task representative of whether the task has been processed, determining at least one dataset related to the task, and assigning a signature to the determined at least one dataset. The method further comprises searching, by the processor, a data structure for the task signature, and based on the searching, sending the task over a network to a task executor for processing or locating results associated with the task. The method further comprises sending, over a network, a job result to the client device. Systems and computer-readable media are also provided.

Claims

1. A method for processing a job, comprising:

receiving, from a client device over a network, information representing a job;

generating at least two tasks representative of the job;

for at least one task;

assigning, by a processor, a signature to the task representative of whether the task has been processed;

determining a dataset related to the task;

assigning a signature to the determined dataset;

searching, by the processor, a data structure for the assigned signature;

based on the searching,

sending the task over a network to a task executor device for processing, or

locating results associated with the task; and

sending, over a network, a job result to the client device.

2. The method of claim 1, wherein the data structure comprises a Directed Acyclic Graph (DAG).

3. The method of claim 1, wherein the data structure comprises:

a first node comprising a task signature associated with the task.

4. The method of claim 3, wherein searching the data structure comprises:

searching, by the processor, the data structure for the task signature;

if less than all of the task signatures for a task are located, sending a task to a task executor for processing;

receiving a task result; and

aggregating the received task result into a job result.

5. The method of claim 1, wherein the dataset is related to at least two tasks.

6. The method of claim 1, wherein sending a task to a task executor device further comprises:

determining a value associated with the task;

determining an amount of processor load for at least one task executor device;

selecting a task executor device based upon the determined value and the determined amount of processor load for the at least one task executor device; and

sending the task to the selected task executor device.

7. The method of claim 1, wherein generating at least two tasks comprises dividing the job into tasks that are computable by different task executors in parallel.

8. A system, comprising:

a memory device storing instructions configured to implement a job scheduler module and a task scheduler module; and

at least one processor, configured to execute the instructions to operate the job scheduler module and the task scheduler module;

wherein the instructions configured to implement the job scheduler module are configured to cause the processor to;

receive, from a client device, information representing a job;

generate at least two tasks representative of the job;

for at least one task;

assign a signature to the task representative of whether the task has been processed;

determine a dataset related to the task; and

assign a signature to the determined dataset; and

wherein the instructions configured to implement the task scheduler module are configured to cause the processor to;

for at least one task;

search a data structure for the assigned signature;

based on the searching;

send the task over a network to a task executor device for processing, or

locate results associated with the task; and

send, over a network, a job result to a client device.

9. The system of claim 8, wherein the data structure comprises a Directed Acyclic Graph (DAG).

10. The system of claim 8, wherein the data structure comprises:

a first node comprising a task signature associated with the task.

11. The system of claim 10, wherein searching the data structure comprises:

searching, by the processor, the data structure for the task signature;

if less than all of the task signatures for a task are located, sending a task to a task executor for processing;

receiving a task result; and

aggregating the task result into a job result.

12. The system of claim 8, wherein the dataset is related to at least two tasks.

13. The system of claim 8, wherein sending a task to a task executor device further comprises:

determining a value associated with the task;

determining an amount of processor load for at least one task executor device;

selecting a task executor device based upon the determined value and the determined amount of processor load for the at least one task executor device; and

sending the task to the selected task executor device.

14. The system of claim 8, wherein generating at least two tasks comprises dividing the job into tasks that are computable by different task executors in parallel.

15. A non-transitory computer-readable medium comprising instructions configured to implement a job scheduler module and a task scheduler module,

wherein the instructions configured to implement the job scheduler module are configured to cause at least one processor to:

receive, from a client device, information representing a job;

generate at least two tasks representative of the job;

for at least one task;

assign a signature to the task representative of whether the task has been processed;

determine a dataset related to the task; and

assign a signature to the determined dataset;

wherein the instructions configured to implement the task scheduler module are configured to cause the at least one processor to;

for at least one task;

search a data structure for the assigned signature;

based on the searching;

send the task over a network to a task executor device for processing, or

locate results associated with the task; and

send, over a network, a job result to a client device.

16. The medium of claim 15, wherein the data structure comprises a Directed Acyclic Graph (DAG).

17. The medium of claim 15, wherein the data structure comprises:

a first node comprising a task signature associated with the task.

18. The medium of claim 17, wherein searching the data structure comprises:

searching, by the processor, the data structure for the task signature;

if less than all of the task signatures for a task are located, sending a task to a task executor for processing;

receiving a task result; and

aggregating the task result into a job result.

19. The medium of claim 15, wherein the dataset is related to at least two tasks.

20. The medium of claim 15, wherein sending a task to a task executor device further comprises:

determining a value associated with the task;

determining an amount of processor load for at least one task executor device;

selecting a task executor device based upon the determined value and the determined amount of processor load for the at least one task executor device; and

sending the task to the selected task executor device.