Adaptive work distribution in distributed systems

Patent metadata

Field	Value
Publication number	US-10996993-B2
Application number	US-201916447542-A
Country	US
Kind code	B2
Filing date	Jun 20, 2019
Priority date	Jun 20, 2019
Publication date	May 4, 2021
Grant date	May 4, 2021

Abstract

These methods, systems, and other aspects can provide for adaptive distribution/re-distribution of data processing tasks. An example method may create, by a processor in a first node, a status object for a data processing task and assign, by the processor in the first node, the data processing task to a worker of a second node. Further, after a first period of time, the method may query, by the processor in the first node, the status object for a task status of the assigned data processing task reported by the second node. The task status reflects a status of execution of the assigned data processing task by the second node. The method determines, by the processor in the first node, to reassign the assigned data processing task based on a received task status reported by the second node, and reassign, by the processor in the first node, the assigned task.

First claim

What is claimed is:

1. A distributed system, comprising:
a cluster of nodes that includes a first node and a second node, wherein each node of the cluster of nodes includes a processor and a memory; and
a task distribution manager associated with the first node, wherein:
the second node includes a worker configured to perform data processing tasks; and
the task distribution manager is configured to:
create a status object for a task, wherein the status object for the task includes a start marker, a current marker, and an end marker for the task;
assign the task to the worker of the second node;
after a first period of time, query the status object for a task status of the assigned task reported by the second node, wherein the task status indicates a status of execution of the assigned task by the second node;
determine to reassign the assigned task based on a received task status reported by the second node; and
reassign the assigned task.

2. The system of claim 1 , wherein the status object for the task further includes a task identifier for the assigned task in a prefix of the status object.

3. The system of claim 1 , wherein:
the start marker is an empty string that indicates where the assigned task starts;
the current marker indicates a point to which the worker has completed the task when the status object is queried; and
the end marker indicates an end offset of the task.

4. The system of claim 1 , wherein the task status of the assigned task is determined based on a comparison of the current marker and the end marker after the first period of time.

5. The system of claim 1 , wherein, when reassigning the assigned task, the task distribution manager is further configured to regenerate a copy of the assigned task, wherein a start marker for the regenerated copy of the assigned task is set to the current marker of the assigned task after the first period of time.

6. The system of claim 1 , wherein the task distribution manager is further configured to:
create a task identifier for the assigned task; and
create a lease object that includes the task identifier in a prefix of the lease object.

7. The system of claim 6 , wherein the task distribution manager is further configured to periodically override the lease object to advertise a liveliness of the task distribution manager to the second node.

8. The system of claim 6 , wherein the lease object and the status object are 0-byte objects stored in an object store.

9. The system of claim 1 , wherein, to query the status object for the task status of the assigned task reported by the second node, the task distribution manager is further configured to:
periodically check a latest modification of the status object that has been periodically modified by the second node.

10. The system of claim 1 , wherein the task distribution manager is further configured to assign a second task to the worker of the second node after assigning the task to the worker of the second node.

11. A computer-implemented method, comprising:
creating, by a processor in a first node, a status object for a data processing task;
creating a task identifier for the data processing task;
creating a lease object that includes the task identifier in a prefix of the lease object;
assigning, by the processor in the first node, the data processing task to a worker of a second node;
after a first period of time, querying, by the processor in the first node, the status object for a task status of the assigned data processing task reported by the second node, wherein the task status indicates a status of execution of the assigned data processing task by the second node;
determining, by the processor in the first node, to reassign the assigned data processing task based on a received task status reported by the second node; and
reassigning, by the processor in the first node, the assigned data processing task.

12. The computer-implemented method of claim 11 , wherein the status object for the data processing task includes a start marker, a current marker, and an end marker for the data processing task.

13. The computer-implemented method of claim 12 , wherein:
the start marker is an empty string that indicates where the assigned data processing task starts;
the current marker indicates a point to which the worker has completed the data processing task when the status object is queried; and
the end marker indicates an end offset of the data processing task.

14. The computer-implemented method of claim 12 , wherein the task status of the assigned data processing task is determined based on a comparison of the current marker and the end marker after the first period of time.

15. The computer-implemented method of claim 12 , wherein:
reassigning the assigned data processing task further comprises regenerating a copy of the assigned data processing task; and
a start marker for the regenerated copy of the assigned data processing task is set to the current marker of the assigned data processing task after the first period of time.

16. The computer-implemented method of claim 11 , wherein the status object includes the task identifier in a prefix of the status object.

17. The computer-implemented method of claim 11 , further comprising periodically overriding the lease object to advertise a liveliness of a task distribution manager to the second node.

18. The computer-implemented method of claim 11 , wherein the lease object and the status object are 0-byte objects stored in an object store.

19. The computer-implemented method of claim 11 , wherein querying the status object for the task status of the assigned data processing task reported by the second node further includes periodically checking a latest modification of the status object that has been periodically modified by the second node.

20. A system, comprising:
means for creating a status object for a task, wherein the status object for the task includes a start marker, a current marker, and an end marker for the task;
means for assigning the task to a worker of a system node;
means for querying the status object for a task status of the assigned task reported by the system node after a first period of time, wherein the task status indicates a status of execution of the assigned task by the system node;
means for determining to reassign the assigned task based on a received task status reported by the system node; and
means for reassigning the assigned task.

Assignees

• Western Digital Tech Inc

Inventors

• Roy Souvik Kumar
• Pyati Ameet

Classifications

• G06F9/4887

  involving deadlines, e.g. rate based, periodic · CPC title

• G06F9/5066 Primary

  Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451) · CPC title

• G06F9/5083 Primary

  Techniques for rebalancing the load in a distributed system · CPC title

• G06F2209/5017

  Task decomposition · CPC title

• G06F2209/5013

  Request control · CPC title