JP2012242975A - Distributed parallel processing cache device and method, resource management node and program - Google Patents

Abstract

PROBLEM TO BE SOLVED: To process a job at high speed and speed up processing which has been done in the past when the job includes a task which is to be done more than one time.SOLUTION: A resource management node requests a hash value of input data from a calculation node having the input data, acquires it with an execution file and assigns a task to the calculation node having the input data. The calculation node executes the assigned task and stores a result in association with the execution file and the input data in calculation result temporal storage means. The resource management node acquires the execution file and the input data as an execution result and stores them in association with the calculation node in calculation result storage means. When assigning a task to a calculation node, the management node searches the calculation result storage means by using the hash value of the input data and the execution file as keys and skips processing of the task if finding a calculation result of the task executed by the calculation node.

Description

  The present invention relates to a distributed parallel processing cache device and method, a resource management node, and a program, and more particularly to a cache device for assigning a task to a computation node having input data when performing distributed parallel processing in a distributed processing framework. The present invention relates to a method, a resource management node, and a program.

  In a distributed processing framework, there is data analysis infrastructure software based on a distributed storage device that divides and stores files on a PC cluster. As shown in FIG. 1, this is based on a program that performs parallel computation on input data that are not dependent on each other by describing an operation flow in the form of a directed graph. In FIG. 1, an edge is a data flow, which means processing contents performed by a vertex. Processing executed on the top is called a task. At the time of execution, the distributed file system is accessed, the input file is divided into processing units, initialization processing is performed, and the program describing the processing contents is placed on the calculation node close to the data node where the divided file is stored When the calculation is completed, the result is written into the distributed file system. The “calculation node” refers to a computer that actually executes a task.

  In such an environment, there is a system that extends MapReduce and specializes in loop processing as a method of dividing the processing result of the previous vertex and processing it as input data (for example, Non-Patent Documents 1 and 2). System) that performs distributed parallel processing of programs described in Map processing and Reduce (for example, see Patent Document 1), and system that performs distributed parallel processing of programs described in acyclic directed graph processing (see Patent Document 2). is there.

  The distributed parallel processing cache processing in the prior art will be described below.

  FIG. 2 is a schematic flowchart of the prior art.

  The resource management node assigns a task to the computation node while considering the cache (step 210), and executes the task to which the computation node is assigned (step 220). The task execution result is stored as a temporary file in the computation node (step 230). If the job has not ended, the process returns to step 210. When the job is finished, delete the temporary file on the compute node. Here, “job” refers to a series of processes performed by a program describing an operation flow, and includes a process executed at each vertex and a data flow expressing a data flow.

  FIG. 3 shows the process of step 210 for assigning a task to the calculation node.

  Based on the technique of Patent Document 1, the resource management node determines a task to be executed next (step 410). Next, the resource management node confirms the declaration of data to be reused in the next execution job (step 420). It is determined whether or not the input of the task selected in step 410 is reusable. If it is the first execution, it is assumed that the processing is completed at the node holding the calculation result, and the calculation is performed. Skip (step 440), the process returns to step 410. On the other hand, if it cannot be reused, or if it is the second or subsequent execution, a calculation node to be executed is determined based on the technique of Patent Document 1 (step 460).

  In step 230, as shown in FIG. 4, the calculation result of the completed task is stored in the external storage device (local disk) of the calculation node (step 610).

  Finally, in step 240, as shown in FIG. 5, the calculation result of the completed task is stored in the external storage device (local disk) of the calculation node (step 610).

United States Patent 7,650,331, System and method for efficient large-scale data processing (Map Reduce) Google, January 19, 2010. USPTO Applicaton # 20080082644, Distributed Parallel Computing (Dryad), Microsoft Corporation, September 29, 2006.

HaLoop: Efficient Iterative Data Processing on Large Clusters, Yingyi Bu, Bill Howe, Magdalena Balazinska, Michael D. Ernst.In VLDB'10: The 36the International Conference on Very Large Data Bases, Singapore, 24-30, September, 2010. Twister: A Runtime for Iterative MapReduce Jaliya Ekanayake, Hui Li, Bingjing Zhang, Thilina Gunarathne, Seung-Hee Bae, Judy Qiu, Geoffrey Fox, Twister: A Runtime for Iterative MapReduce.The first International Workshop on MapReduce and its Applications (MAPREDUCE ' 10)-HPDC2010.

  However, even when a system in which the good parts of the systems of Patent Documents 1 and 2 and Non-Patent Documents 1 and 2 are combined is constructed, there are the following problems.

  (1) In order to reuse a calculation result performed in the past in a job, the user needs to declare data to be reused.

(2) When a job is executed a plurality of times, it is necessary to perform the same calculation and transfer again even for tasks that have been performed in the past. For more information,
Even if a calculation that has been performed in the past is included in the job being executed, it is necessary to perform the same calculation again when executing multiple jobs.

  Even if a calculation that has been performed in the past is included in the job being executed, transfer between the calculation nodes occurs.

  The present invention has been made in view of the above points. When a task to be executed a plurality of times is included in a job, the job is processed at a high speed, and the processing that has been performed in the past is accelerated. It is an object of the present invention to provide a distributed parallel processing cache device, method, and program that can be used.

In order to solve the above-described problem, the present invention (Claim 1) can allocate a resource management node and a task to which a task is allocated when a flow of a program executed in the distributed parallel execution framework is expressed as a circular directed graph. A parallel cache system composed of compute nodes,
The resource management node is:
A hash value acquisition means for requesting calculation of the hash value of the input data to the calculation node having the input data of the task, and acquiring it together with the execution file;
A task management unit that obtains a hash value of an input data acquired from a calculation node that executed the task, an execution file, an input file, and stores the hash value in association with the calculation node in a calculation result storage unit;
The calculation result storage means is searched using the hash value of the input data and the execution file as a search key. If there is data of a calculation node corresponding to the key, the calculation is skipped, and if not, the task is A task assignment means for determining a calculation node to be assigned;
Have
The compute node is
A hash value calculation means for obtaining a hash value of the input data requested from the resource management node and returning the hash value to the resource management node;
Task execution means for executing a task assigned by the resource management node, storing the result in an execution file and input data in association with the input data, and transmitting the result to the resource management node.

The present invention (Claim 2) is the resource management node,
When the job is completed, a calculation node holding the calculation result is extracted from the calculation result storage unit based on the search key, and the data node operating on the same physical computer as the calculation node is extracted from the calculation node. A means for transmitting and storing the calculation result is further included.

As described above, according to the present invention, by recording the execution result of the task executed in the calculation node holding the input data in the resource management node,
(1) When a task that is executed a plurality of times is included in a job, the job can be automatically accelerated.

  (2) When a job is executed a plurality of times, processing that has been performed in the past can be accelerated. Specifically, when a calculation that has been performed in the past is included in the job being executed, the calculation can be skipped by reusing the result in units of input blocks.

It is an operation | movement flow of a directed graph format. It is a schematic flowchart of a prior art. It is the flowchart which detailed S210 of FIG. It is the flowchart which detailed S230 of FIG. It is the flowchart which detailed S240 of FIG. 1 is a system configuration diagram according to an embodiment of the present invention. It is a flowchart of the whole operation | movement in one embodiment of this invention. It is the flowchart which detailed S310 of FIG. 7 in one embodiment of this invention. It is the flowchart which detailed S330 of FIG. 7 in one embodiment of this invention. It is the flowchart which detailed S340 of FIG. 7 in one embodiment of this invention. It is a flowchart of the whole operation | movement in one embodiment of this invention.

  Embodiments of the present invention will be described below with reference to the drawings.

  FIG. 6 shows a system configuration in an embodiment of the present invention.

  The system shown in FIG. 1 is a resource management node 10, a calculation node 21, and a distributed file system node, and includes a plurality of physical computers 20 having data nodes 22 for storing data.

  The resource management node 10 is a computer that manages which task is assigned to which calculation node, and includes a task management unit 11, a search unit 12, and a node management DB 13, and a calculation result storage unit 1 (local disk) as an external storage. Is connected. The node management DB 13 holds a calculation node, a data node, and task input data in association with each physical computer. The calculation result storage unit 1 stores a hash value and an execution file for each calculation node. Although described below as an external storage device, it may be constructed as a disk device or memory in the resource management node.

  The calculation node 21 of the physical computer 20 has a hash calculation unit 211 and is connected to a local disk having a calculation result temporary storage unit 2. The data node 22 has a data storage unit 221.

  Processing of the system having the above configuration will be described.

  FIG. 7 is a flowchart of the overall operation in one embodiment of the present invention.

  Step 310) The task management unit 11 of the resource management node 10 assigns a task to the computation node 21 while considering the cache. Details will be described later with reference to FIG.

  Step 320) The computing node 21 to which the task is assigned executes the task in accordance with an instruction from the resource management node 10.

  Step 330) The calculation node 21 associates the result of step 320 with the execution file and the input data, saves it as a temporary file in the calculation result temporary storage unit 2 (local disk), and transmits the calculation result to the resource management node 10. If the job ends, the process proceeds to step 340, and if not completed, the process returns to step 310. Details will be described later with reference to FIG.

  Step 340) When the job is finished, the task management unit 11 of the resource management node 10 saves the calculation result in the calculation result storage unit 1 so that the calculation result can be reused and makes it permanent. Details will be described later with reference to FIG.

  Next, step 310 will be described.

  FIG. 8 is a detailed flowchart of S310 in FIG. 7 according to the embodiment of the present invention.

  Step 510) The task management unit 11 of the resource management node 10 determines a task to be executed next based on the technique of Patent Document 1.

  Step 520) The task management unit 11 of the resource management node 10 searches the node management DB 13 for the computation node 21 holding the input data of the task selected in Step 510, and hashes the input data to the computation node 21. Requests that a value be calculated. Thereby, the calculation node 21 calculates a hash value of the input data and transmits the hash value and the execution file to the resource management node 10.

  Step 530) The node search unit 12 of the resource management node 10 sends a past calculation result from the calculation result storage unit 1 using the hash value of the input data and the execution file obtained by requesting the calculation node 21 in Step 520 as keys. Search the existence of and the storage location of the calculation result. If there is a calculation result corresponding to the hash value of the input data in the calculation result storage unit 1, it is assumed that the calculation has already been performed, and the process proceeds to step 540, and if it does not exist, the calculation has not been executed yet As shown in FIG.

  Step 540) The task management unit 11 considers the processing to be completed at the calculation node holding the calculation result, skips the calculation, and proceeds to Step 510.

  Step 550) The task management unit 11 determines a calculation node that executes a task based on the technique of Patent Document 1.

  Next, the process at the time of task termination (step 330) in FIG. 7 will be described.

  FIG. 9 is a detailed flowchart of S330 in FIG. 7 according to the embodiment of the present invention.

  Step 710) The calculation node 21 stores the calculation result (the hash value of the input data, the execution file, and the execution result) of the task that has been executed in the calculation result temporary storage unit 2 connected to the own node, and also the resource management node 10 Send to.

  Step 720) The task management unit 11 of the resource management node 10 acquires the key (the hash value of the input data and the execution file) and the execution result from the calculation node, and stores them in the calculation result storage unit 1 in association with the calculation node.

  Next, the job end processing (step 340) in FIG. 7 will be described.

  FIG. 10 is a flowchart of S340 in FIG. 7 according to the embodiment of the present invention.

  Step 910) When the job is completed, the node search unit 12 of the resource management node 10 searches the calculation result storage unit 1 based on the search key (the hash value of the input data and the execution file), and the calculation result corresponding to the key Search for compute nodes that hold

  Step 920) The node search unit 12 searches the node management DB 13 for a data node operating on the same physical computer as the calculation node searched in Step 910. The task management unit 11 transmits the calculation result to the data node 22. As a result, the data node 22 of the physical computer 20 stores the calculation result in the data storage unit 221.

  FIG. 11 is a sequence chart of the overall operation in one embodiment of the present invention. The step numbers in the figure correspond to the step numbers in the flowchart described above.

  By performing the processing as described above, calculation including processing in which input data increases in time series can be performed at high speed.

This
(1) The search engine can be updated at high speed.

  (2) Recommendations to users can be updated at high speed.

  (3) Log analysis can be performed at high speed.

  Note that the operations of the resource management node and the calculation node can be constructed as a program, installed in a computer used as the resource management node and the calculation node, executed, or distributed via a network.

  The present invention is not limited to the above-described embodiments, and various modifications and applications can be made within the scope of the claims.

DESCRIPTION OF SYMBOLS 1 Calculation result memory | storage part 2 Calculation result temporary storage part 10 Resource management node 11 Task management part 12 Search part 13 Node management DB
20 physical computer 21 calculation node 22 data node 211 hash calculation unit 221 data storage unit

Claims (6)

When the flow of a program executed in the distributed parallel execution framework is expressed as a circular directed graph, a parallel cache system including a resource management node to which a task is assigned and a computation node to which the task is assigned,
The resource management node is:
A hash value acquisition means for requesting calculation of the hash value of the input data to the calculation node having the input data of the task, and acquiring it together with the execution file;
A task management unit that obtains a hash value of an input data acquired from a calculation node that executed the task, an execution file, an input file, and stores the hash value in association with the calculation node in a calculation result storage unit;
The calculation result storage means is searched using the hash value of the input data and the execution file as a search key. If there is data of a calculation node corresponding to the key, the calculation is skipped, and if not, the task is A task assignment means for determining a calculation node to be assigned;
Have
The compute node is
A hash value calculation means for obtaining a hash value of the input data requested from the resource management node and returning the hash value to the resource management node;
A task execution unit that executes the task assigned by the resource management node, stores the result in an execution file and input data in association with the input data, and transmits the result to the resource management node; A parallel cache system. The resource management node is:
When the job is completed, a calculation node holding the calculation result is extracted from the calculation result storage unit based on the search key, and the data node operating on the same physical computer as the calculation node is extracted from the calculation node. The parallel cache system according to claim 1, further comprising means for transmitting and storing the calculation result. When the flow of a program executed in the distributed parallel execution framework is expressed as a circular directed graph, a parallel cache method comprising a resource management node to which a task is assigned and a computation node to which the task is assigned,
A hash value acquisition unit of the resource management node requests a hash value of the input data from a calculation node holding the input data, and acquires the hash value together with the execution file;
A task allocation step in which the task allocation means of the resource management node allocates a task to a computation node holding input data;
The task execution means of the calculation node executes the task assigned from the resource management node, and stores the result in the calculation result temporary storage means in association with the execution file and input data;
An execution result management step in which the execution result management unit of the resource management node acquires an execution file and input data as a task execution result from the calculation node, and stores it in the calculation result storage unit in association with the calculation node;
And
In the task assignment step,
When assigning a task to the calculation node, the calculation result storage unit is searched using the hash value of the input data and the execution file as a key, and when the calculation result of the task by the calculation node exists A parallel cache method characterized in that the processing of the task is skipped. In the resource management node,
When the job is completed, a calculation node holding the calculation result is extracted from the calculation result storage unit based on the key, and the calculation is performed on the data node operating on the same physical computer as the calculation node. 4. The parallel cache method according to claim 3, wherein the result is transmitted and stored. A resource management node that assigns a task to a computation node when the flow of a program executed in the distributed parallel execution framework is expressed as a circular directed graph,
Task management means for acquiring a hash value of input data obtained from a calculation node having task input data, an execution file, input data, and storing the calculation data storage means in association with the calculation node;
A hash value acquisition unit that requests the calculation node to calculate a hash value of input data and acquires a hash value and an executable file;
A calculation node that searches the calculation result storage means using the hash value of the input data and the execution file as a search key, skips the calculation when there is data corresponding to the key, and allocates a task when there is no data Task assignment means for determining
A resource management node characterized by comprising: Computer
The parallel cache program for functioning as each means of the resource management node according to claim 5.

Images