Addressing data skew using map-reduce
AssigneeRoblox Corporation
InventorsAswath Manoharan, Nikolaus Sonntag, Shailendra Rathore
Life of this patent
Estimating the term…
Abstract
A system and method includes using a queue with reduce operations. A method can include, responsive to generation of one or more markers by a first node or a second node, causing a submission of one or more markers to a queue associated with a computing cluster. Additionally, responsive to a determination that the first node has completed a first reduce operation, directing the first node to perform a first copy operation to copy first data identified by a first marker of the one or more markers in the queue, where the first copy operation is performed concurrently with the second reduce operation.
Claims20
A method comprising:
- directing, by a master node of a computing cluster, a first node of a plurality of nodes of the computing cluster to execute a first reduce operation on a first location of data to generate a first plurality of markers associated with the first location of data;
- directing a second node of the plurality of nodes to execute a second reduce operation on a second location of data to generate a second plurality of markers associated with the second location of data;
- responsive to generation of one or more markers by the first node or the second node, causing a submission of the one or more markers to a queue associated with the computing cluster;
- responsive to a determination that the first node has completed the first reduce operation, directing the first node to perform a first copy operation to copy first data identified by a first marker of the one or more markers in the queue, wherein the first copy operation is performed concurrently with the second reduce operation;
- and
- responsive to a determination that the first node has completed the first copy operation, removing the first marker from the queue.
A system comprising:
- a hardware computer cluster comprising a plurality of nodes including a master node, the master node arranged to perform operations that comprise:
- directing a first node of the plurality of nodes of the computing cluster to execute a first reduce operation on a first location of data to generate a first plurality of markers associated with the first location of data;
- directing a second node of the plurality of nodes to execute a second reduce operation on a second location of data to generate a second plurality of markers associated with the second location of data;
- responsive to generation of one or more markers by the first node or the second node, causing a submission of the one or more markers to a queue associated with the computing cluster;
- responsive to a determination that the first node has completed the first reduce operation, directing the first node to perform a first copy operation to copy first data identified by a first marker of the one or more markers in the queue, wherein the first copy operation is performed concurrently with the second reduce operation;
- and
- responsive to a determination that the first node has completed the first copy operation, removing the first marker from the queue.
A non-transitory computer-readable storage medium comprising instructions that, responsive to execution by a processing device, cause the processing device to perform operations comprising:
- directing, by a master node of a computing cluster, a first node of a plurality of nodes of the computing cluster to execute a first reduce operation on a first location of data to generate a first plurality of markers associated with the first location of data;
- directing a second node of the plurality of nodes to execute a second reduce operation on a second location of data to generate a second plurality of markers associated with the second location of data;
- responsive to generation of one or more markers by the first node or the second node, causing a submission of the one or more markers to a queue associated with the computing cluster;
- responsive to a determination that the first node has completed the first reduce operation, directing the first node to perform a first copy operation that copies first data identified by a first marker of the one or more markers in the queue, wherein the first copy operation is performed concurrently with the second reduce operation;
- and
- responsive to a determination that the first node has completed the first copy operation, removing the first marker from the queue.
Dependencies are inferred from the claim text.