CN102609303B - Slow-task dispatching method and slow-task dispatching device of Map Reduce system - Google Patents

Abstract

The present invention provides a method and device for scheduling slow tasks in a MapReduce system, wherein the method includes: obtaining the computing power values of each computing node in the MapReduce system respectively, arranging each computing node into a queue of slow nodes according to the computing power value, and selecting the queue The first M computing nodes in the set are used as the target computing nodes; obtain the estimated computing power value of the target computing node after loading the slow tasks to be scheduled, and compare the target computing node and other computing nodes according to the computing power value from large to small Sequentially arrange into a new queue of slow nodes, and preset the Nth computing node starting from the end of the slow node queue as the evaluation reference node, where N is a natural number; the estimated computing power value of the target computing node is greater than When evaluating the computing capability value of the reference node, the slow task to be scheduled is scheduled to the target computing node. The invention effectively suppresses the jitter phenomenon during slow task scheduling.

Description

Slow task scheduling method and device for MapReduce system

technical field

The invention relates to computing technology, in particular to a slow task scheduling method and device for a MapReduce system.

Background technique

As a basic computing framework, MapReduce is widely used in Internet applications such as cloud computing environments. With the development of the cloud computing environment, virtualization technology is gradually adopted, and there may be multiple virtual machines on a physical host; due to the large difference in the computing capabilities of different physical hosts, and the differences between virtual machines on the same physical host There is a large performance difference, which leads to the prominent node heterogeneity of the MapReduce system. The node heterogeneity refers to the difference in the processing speed of different computing nodes (one virtual machine is equivalent to one computing node). Computing tasks are scheduled to different computing nodes, and the response time for obtaining processing results is different. When the master control node in the MapReduce system finds that a computing node executes computing tasks too slowly and determines that the computing task is a slow task, In order to improve the processing speed, the slow task is scheduled to be executed on another computing node at the same time, which is called slow task scheduling.

Specifically, Hadoop, one of the implementation mechanisms of the MapReduce system, has a slow task scheduling scheme: Hadoop assumes that all computing nodes in the system process computing tasks at the same speed, and defines a value between 0 and 1 for computing tasks process index, and set a fixed threshold value, as long as the process index satisfies the setting condition of the threshold value, determine that the computing task is a slow task, and execute slow task scheduling. Hadoop performs slow task scheduling according to the adjacent node scheduling principle, that is, the slow task is scheduled to the adjacent node with the closest physical transmission distance. The disadvantage of the above scheme is: there are too many computing tasks identified as slow tasks, and too many slow task scheduling takes up more system resources; and, the adjacent scheduling principle may also appear that adjacent nodes run slower after scheduling. The slow task will be further scheduled, causing the slow task to be scheduled multiple times, that is, the jitter of system scheduling occurs.

LATE, another implementation mechanism of the MapReduce system, optimizes the above-mentioned Hadoop. It stipulates a slow task scheduling ratio, such as 10%, and only 10% of the slow tasks can be scheduled to avoid too many slow tasks being scheduled. Take up more system resources. Moreover, LATE also defines the slow node queue according to the remaining time required for the completion of computing tasks, and stipulates that the last 25% of the nodes in the queue are slow nodes, and will not schedule slow tasks to the slow nodes mentioned above to avoid nodes running more slowly . However, it has been found in practice that LATE still cannot solve the jitter problem of system scheduling. Even if a computing node located outside the last 25% is selected for slow task scheduling, it is still possible that the computing power of the node will drop too much after loading the slow task. If there are too many slow tasks, the scheduled slow tasks are still slow tasks and will be scheduled again, resulting in system jitter in which slow tasks are scheduled multiple times.

Contents of the invention

The first aspect of the present invention is to provide a slow task scheduling method of the MapReduce system, so as to effectively suppress the jitter phenomenon during the slow task scheduling of the MapReduce system.

Another aspect of the present invention is to provide a slow task scheduling device of the MapReduce system, so as to effectively suppress the jitter phenomenon during the slow task scheduling of the MapReduce system.

The slow task scheduling method of the MapReduce system provided by the present invention comprises:

Obtain the computing capability values of each computing node in the MapReduce system respectively, and the computing capability values of the computing nodes The v ₁ ...v _m represents the processing speed of each computing task on the computing node, the Indicates the average processing speed of the work to which each computing task belongs, and the m represents the total number of computing tasks on the computing node;

Arrange the computing nodes into a slow node queue according to the descending order of the computing capability values, and select the first M computing nodes in the slow node queue, and each selected computing node is used as the target computing node node, the M is a natural number;

Obtain the estimated computing capability values of the M target computing nodes after loading the slow tasks to be scheduled, and the estimated computing capabilities The v _i represents the processing speed of the slow task to be scheduled on the target computing node, the Indicates the average processing speed of the work to which the slow task to be scheduled on the target computing node belongs;

According to the estimated computing capability value of the target computing node and the computing capability values of computing nodes other than the target computing node, calculate the target computing node and computing nodes other than the target computing node Ability values are arranged in order from large to small into a new slow node queue, and the Nth computing node from the end of the slow node queue is preset as the evaluation benchmark node, and N is a natural number;

When the estimated computing capability value of the target computing node is greater than the computing capability value of the evaluation reference node, the slow task to be scheduled is scheduled to the target computing node.

The slow task scheduling device of the MapReduce system provided by the present invention includes: a parameter acquisition unit, a capacity estimation unit, a queue arrangement unit and a scheduling processing unit;

The parameter acquisition unit is used to respectively acquire the computing power value of each computing node in the MapReduce system, and the computing power value of the computing node The v ₁ ...v _m represents the processing speed of each computing task on the computing node, the Indicates the average processing speed of the work to which each computing task belongs, and the m represents the total number of computing tasks on the computing node;

The capability estimation unit is configured to select the first M computing nodes in the slow node queue generated by the queue arrangement unit, each of the selected computing nodes is used as a target computing node, and the M is a natural number; and respectively obtain The estimated computing capability value of the M target computing nodes after loading the slow tasks to be scheduled, the estimated computing capability The v _i represents the processing speed of the slow task to be scheduled on the target computing node, the Indicates the average processing speed of the work to which the slow task to be scheduled on the target computing node belongs;

The queue arranging unit is configured to arrange the computing nodes into a queue of slow nodes according to the descending order of the computing capability values; and, according to the estimated computing capability value of the target computing node and the Computing capability values of computing nodes other than the target computing node, arranging the target computing node and computing nodes other than the target computing node into a new slow node queue in descending order of computing capability values;

The scheduling processing unit is configured to preset the Nth computing node starting from the end of the queue in the slow node queue as an evaluation reference node, where N is a natural number; and the estimated calculation of the target computing node When the capability value is greater than the computing capability value of the evaluation reference node, the slow task to be scheduled is scheduled to the target computing node.

The technical effect of the slow task scheduling method of the MapReduce system of the present invention is: before the slow task is scheduled to the target computing node, the computing power value of the target computing node after loading the slow task to be scheduled is estimated, and the estimated When the computing power value is greater than the computing power value of the evaluation benchmark node, the slow task to be scheduled is scheduled to the target computing node, which can ensure that the target computing node will not reduce the computing power too much after loading the slow task, thereby eliminating The slow task prevents the multiple scheduling of the slow task, and effectively suppresses the jitter phenomenon when the slow task is scheduled.

The technical effect of the slow task scheduling device of the MapReduce system of the present invention is: before the slow task is scheduled to the target computing node, the calculation capability value of the target computing node after loading the slow task to be scheduled is estimated, and the estimated When the computing power value is greater than the computing power value of the evaluation benchmark node, the slow task to be scheduled is scheduled to the target computing node, which can ensure that the target computing node will not reduce the computing power too much after loading the slow task, thereby eliminating The slow task prevents the multiple scheduling of the slow task, and effectively suppresses the jitter phenomenon when the slow task is scheduled.

Description of drawings

Fig. 1 is the schematic flow chart of the slow task scheduling method embodiment of MapReduce system of the present invention;

FIG. 2 is a schematic structural diagram of an embodiment of a slow task scheduling device for a MapReduce system according to the present invention.

Detailed ways

In order to make the description of the slow task scheduling method of the MapReduce system of the embodiment of the present invention clearer, at first the structure and working principle of the MapReduce system are briefly described:

A MapReduce system usually includes a master control node (master) and multiple computing nodes (slave); the master control node is responsible for managing the computing nodes. The master control node receives the client's data calculation request, and the requested data calculation can be called a job (Job), which can be of various types, for example, data query job, data averaging job, and so on. The master control node will split the work into multiple computing tasks (tasks), and distribute the computing tasks to each computing node, and each computing node will specifically execute the processing of the computing tasks. The MapReduce system divides work processing into two phases: the Map phase and the Reduce phase, that is, the computing tasks include two types, the Map type computing tasks and the Reduce type computing tasks, and the Map phase mainly distributes the split computing tasks After processing by each computing node, the Reduce stage mainly summarizes the calculation results of each computing node; when all computing tasks of the computing nodes are completed, the master control node summarizes the calculation results and reports them to the client. Among them, during the processing process, there is a heartbeat between the computing node and the master control node, and the computing node can carry the progress of its computing task in the heartbeat message to notify the master control node; and when the computing task is idle after processing, Computing nodes will actively request the distribution of computing tasks to the master control node.

Embodiments of the present invention follow the following assumptions: first, it is assumed that each computing node in the MapReduce system is heterogeneous; second, it is assumed that each job processed by the MapReduce system is heterogeneous: there are obvious differences between different types of jobs , the amount of data generated is different.

On the basis of the above introduction, the slow task scheduling method and device of the embodiments of the present invention are described below:

Fig. 1 is a schematic flow chart of an embodiment of the slow task scheduling method of the MapReduce system of the present invention. It should be noted that the following 101-103 are only enumerations of the actions executed in the method, and there is no order of execution among them Be strictly limited. As shown in Figure 1, the method may include:

101. Obtain the computing capability values of each computing node in the MapReduce system respectively;

In this embodiment, the master control node of the MapReduce system can obtain the computing capability value of each computing node. Optionally, the master control node can obtain the computing capabilities of each computing node in the following way:

Each computing node can calculate the processing speed of the computing task it handles. For example, computing task a and computing task b are processed on computing node A; computing task c and computing task d are processed on computing node B; then computing node A can compute computing tasks respectively To calculate the processing speeds of task a and task b, computing node B can calculate the processing speeds of task c and d respectively.

Different types of computing tasks have different calculation methods for their processing speed. For example, assume that computing task a and computing task b processed on computing node A are computing tasks of the Map type, and computing task c and computing task d processed on computing node B are computing tasks of the Reduce type. Then, for a computing task of the Map type, its processing speed v=p/t, wherein, p is the data volume of the computing task currently processed by the computing node, and the t is the processing time of the computing task of the data volume; For the computing task of the Reduce type, its processing speed v=p/t, wherein, because the Reduce operation is generally divided into three stages: copying, sorting and statute; if the computing task is in the copying stage, then If the computation task is in the sorting phase, then If the computing task is in the reduction phase, then t is the processing time of the computing task.

Each computing node can carry the processing speed of the computing task obtained by the above calculation and report to the master control node through a heartbeat message with the master control node. The master control node may calculate the average processing speed of the work to which the computing task belongs according to the processing speed.

For example, the above computing task a and computing task c are divided into jobs (job) G1, that is, after receiving the job G1 requested by the client, the master control node splits the job G1 into computing tasks a, computing task c, and distribute it to the computing node A and computing node B for processing; the two computing nodes feed back the processing speed of the computing task processed on them to the master control node, and the master control node can obtain The average processing speed of the job G1. The average processing speed The v represents the processing speed of each computing task split into by the work, and the n represents the total number of computing nodes where the computing tasks split into by the work are located; assuming computing task a fed back by computing node A The processing speed of the computing task c fed back by computing node B is v1, and the processing speed of the computing task c fed back by computing node B is v2, then the average processing speed of the work G1 Similarly, assuming that computing task b and computing task d are split by job G2, the processing speed of computing task b is v3, and the processing speed of computing task d is v4, then the average processing speed of job G2

On the basis of the above calculation of the average processing speed of each job, the computing power of each computing node can be calculated according to the following formula: Among them, v ₁ ...v _m represents the processing speed of each computing task on the target computing node, represents the average processing speed of the jobs to which each computing task belongs, and the m represents the number of each computing task on the computing node. For example, computing the computing power of node A

Optionally, the master control node can send the calculated average processing speed of each job to each computing node, and each computing node can obtain its own computing power value, and then report the computing power to the master control node; or, it can also The master control node obtains the computing capability value of each computing node according to the processing speed reported by the computing nodes and the average processing speed of each job calculated by itself.

Through the above-mentioned technical solution, this embodiment provides an evaluation method and evaluation index for the computing power of computing nodes, and, in the computing of the computing power, the heterogeneity of different types of jobs and the heterogeneity of computing nodes are considered, that is, , considering the processing speed of different computing nodes, and, since the various types of jobs are not comparable, adopting for normalization. The above method makes the calculation capability of the calculation node more reasonable to be reflected.

102. Arrange the computing nodes into a slow node queue according to the descending order of computing capability values, and select the first M computing nodes in the slow node queue, and use each selected computing node as a target computing node node; and obtain the estimated computing power value of the target computing node after loading the slow tasks to be scheduled;

Optionally, the master control node may start to schedule slow tasks when receiving a computing task application message sent by a computing node in the MapReduce system.

When the master control node obtains the processing speed of the computing task and the computing power of the computing node, it can maintain two queues, the slow task queue and the slow node queue. Among them, the slow task queue is that the main control node queues the computing tasks being processed in the MapReduce system according to the processing speed of the computing tasks; the slow node queue is that the main control node queues the computing nodes according to the computing power of the computing nodes, which can be Arrange each computing node into a queue of slow nodes according to the descending order of computing power value. Moreover, in this embodiment, the master control node can start from the tail of the slow task queue, and take the last 10% of computing tasks as slow tasks; in specific implementation, this ratio can be changed, for example, the variance of task completion speed can be measured , if the variance is small, this ratio can be appropriately reduced.

In this embodiment, the first M computing nodes in the slow node queue will be selected, and each selected computing node will be used as the target computing node, and the M is a natural number; for example, in specific implementation, the slow node queue can be selected The number of the first two nodes or the first three nodes in the queue can be set independently, but try to choose the first few nodes in the queue. The slow tasks need to be scheduled to the above M computing nodes at the same time, and the above M target computing nodes are all nodes that are scheduled to load the slow tasks. Before the slow task is scheduled to the above-mentioned target computing node, the computing capability of the target computing node after loading the slow task will be pre-evaluated.

Specifically, the computing power of the target computing node Wherein, said v _i represents the processing speed of the slow task to be scheduled on the target computing node, said Indicates the average processing speed of the work to which the slow task to be scheduled on the target computing node belongs, and the v ₁ ... v _m represents the processing of each computing task other than the slow task to be scheduled on the target computing node speed, the Indicates the average processing speed of the jobs to which the computing tasks other than the slow tasks to be scheduled belong respectively, and the m represents the number of computing tasks other than the slow tasks to be scheduled on the target computing node.

For example, assuming that computing task c is planned to be loaded on computing node A, the computing power of computing node A is estimated

103. Arrange the target computing node and computing nodes other than the target computing node into a new slow node queue in descending order of computing capability values;

Since the computing capability of the target computing node in the slow node queue was re-estimated in step 102, in this step, the estimated computing capability of the target computing node and each Calculate the computing power value of the node, and re-queue the queue of the slow node.

104. When the estimated computing capability value of the target computing node is greater than the computing capability value of the evaluation reference node, schedule the slow task to be scheduled to the target computing node.

In this embodiment, the Nth computing node from the end of the slow node queue re-queued in preset 103 is the evaluation reference node, and the N is a natural number; for example, N and the The ratio of the total number of computing nodes in the MapReduce system is 10%. That is, assuming that there are 100 computing nodes in the MapReduce system, in the slow node queue composed of the 100 computing nodes, some nodes behind the queue have low computing power and slow processing speed, which can be called slow nodes; The 10th computing node from the bottom to the front is the evaluation benchmark node.

If the estimated computing power value of the target computing node is greater than the computing power value of the evaluation reference node, it means that if the slow task to be scheduled is loaded to the target computing node, the computing power of the target computing node will drop but not drop to The last 10% of the slow node queue also correspondingly indicate that due to the strong computing power of the target computing node, the loaded slow task will no longer become a new slow task on the target computing node, and the pending scheduling The slow task is scheduled to the target computing node. Otherwise, it means that if the slow task to be scheduled is loaded to the target computing node, the computing power of the target computing node will be severely reduced, and slow tasks will inevitably be generated, and the slow task to be scheduled will not be scheduled to the target computing node.

By estimating the computing power of the loaded target computing node before loading the slow task, the performance decline of the target computing node after loading the slow task can be predicted in advance, and whether the slow task will still be generated after loading can be obtained, and timely Stop the scheduling of slow tasks and prevent the phenomenon of multiple scheduling of slow tasks, thereby effectively suppressing the occurrence of jitter and improving the performance of the MapReduce system; Resource occupation caused by slow task scheduling; in addition, this method uses the slow node queue as the scheduling basis, and requeues according to the estimated computing power of the node after loading the slow task, and can also control the proportion of slow task rescheduling.

The effect of the slow task scheduling method of the MapReduce system of the present embodiment is illustrated below through a set of experimental data:

In this embodiment, a simulation experiment is carried out to compare the effect difference between Hadoop, LATE, and the slow task scheduling scheme of this embodiment. The simulation environment is set as follows: the MapReduce system has a master control node and 50 computing nodes; according to the Hadoop model, each computing node can handle 10 computing capabilities at the same time; the computing capabilities of the computing nodes are selected according to the distribution in Table 1 below. The simulation mainly examines two technical indicators: the response time of the MapReduce system to complete the work, and the number of jitters in the MapReduce system (that is, counting the number of computing tasks that have been scheduled more than twice).

Table 1 Computing capability distribution of computing nodes

Physical machine type Number of units

1 VMs/host 202 2 VMs/host 264 3 VMs/host 201 4 VMs/host 140 5 VMs/host 45 6 VMs/host 12 7 VMs/host 7

The following tables 2 and 3 are the response time comparison table and the average jitter times table of the above three models in this simulation experiment, where Berkeley represents the LATE scheme, and Patent represents the scheme of this embodiment;

Table 2 Response time (unit: tick) comparison table

number of tasks Hadoop Berkeley Patent 1000 21749.4 19990.2 16814.6 2000 38381.2 38223.6 33608.8 3000 57929.4 55130.6 51802.3 4000 81571.7 73063.4 69270.5 5000 99111.3 94638.1 86405.8

Table 3 Average jitter times table

number of tasks Hadoop Berkeley Patent 1000 71.8 45.7 14.1 2000 77.9 47.5 twenty four 3000 79.8 50.4 42.6 4000 90.3 57.7 45.1 5000 94.5 62.2 49.3

It can be known from Table 2 and Table 3 that the solution of this embodiment is superior to Hadoop and LATE in terms of completion time and jitter.

In the slow task scheduling method of the MapReduce system in this embodiment, before scheduling the slow task to the target computing node, the computing power value of the target computing node after loading the slow task to be scheduled is estimated, and the estimated computing power When the value is greater than the computing power value of the evaluation reference node, the slow task to be scheduled is scheduled to the target computing node, which can ensure that the computing power of the target computing node will not drop too much after loading the slow task, thereby avoiding new The generation of slow tasks prevents multiple scheduling of slow tasks, and effectively suppresses the occurrence of jitter during slow task scheduling.

Fig. 2 is a schematic structural diagram of an embodiment of the slow task scheduling device of the MapReduce system of the present invention. The device can execute the slow task scheduling method of any embodiment of the present invention. This embodiment only briefly explains the structure of the device, and the specific working principle Reference may be made to the descriptions in the method embodiments.

As shown in FIG. 2, the slow task scheduling device of this embodiment may include: a parameter acquisition unit 21, a capacity estimation unit 22, a queue arrangement unit 23, and a scheduling processing unit 24; wherein,

The parameter obtaining unit 21 is used to respectively obtain the computing power value of each computing node in the MapReduce system, and the computing power value of the computing node The v ₁ ...v _m represents the processing speed of each computing task on the computing node, the Indicates the average processing speed of the work to which each computing task belongs, and the m represents the total number of computing tasks on the computing node;

The capacity estimation unit 22 is configured to select the first M computing nodes in the slow node queue generated by the queue arrangement unit, each of the selected computing nodes is used as a target computing node, and the M is a natural number; and obtain M respectively. The estimated computing capability value of each target computing node after loading the slow task to be scheduled, and the estimated computing capability The v _i represents the processing speed of the slow task to be scheduled on the target computing node, the Indicates the average processing speed of the work to which the slow task to be scheduled on the target computing node belongs;

A queue arrangement unit 23, configured to arrange the computing nodes into a queue of slow nodes according to the descending order of the computing capability values; and, according to the estimated computing capability value of the target computing node and the target calculating the computing capability values of computing nodes other than the computing node, and arranging the target computing node and computing nodes other than the target computing node into a new slow node queue in order of computing capability values from large to small;

The scheduling processing unit 24 is configured to preset the Nth computing node starting from the end of the queue in the slow node queue as the evaluation reference node, where N is a natural number; and the estimated computing power of the target computing node When the value is greater than the computing capability value of the evaluation reference node, the slow task to be scheduled is scheduled to the target computing node.

Optionally, the parameter acquisition unit 21 may include: a speed receiving subunit 211, an average processing subunit 212, and a capability acquisition subunit 213; wherein,

The speed receiving subunit 211 is configured to receive the processing speed of the calculation task reported by each calculation node in the MapReduce system, and the calculation task is a calculation task processed on the calculation node;

The average processing subunit 212 is configured to obtain the average processing speed of the work to which the computing task belongs according to the processing speed, and the average processing speed The v represents the processing speed of each of the computing tasks into which the work is split, and the n represents the total number of computing nodes where the computing tasks into which the work is split are located;

The capability acquisition subunit 213 is configured to send the average processing speed of the job to the computing nodes respectively, and receive the average processing speed of the computing nodes obtained according to the average processing speed of the job reported by the computing nodes. A computing capability value; or, used to obtain the computing capability value of each computing node according to the average processing speed of the work.

Optionally, the speed receiving subunit 211 is specifically configured to receive the processing speed of the computing task corresponding to the Map type calculated by each computing node when the computing task type is a Map type, and the processing speed v= p/t, the p is the data amount of the computing task currently processed by the computing node, and the t is the processing time of the computing task of the data amount.

Optionally, the device in this embodiment may further include: a scheduling trigger unit 25, configured to receive the MapReduce system before obtaining the estimated computing capability value of the target computing node in the MapReduce system after loading the slow tasks to be scheduled. The application computing task message sent by the computing nodes in .

The slow task scheduling device of the MapReduce system in this embodiment, before scheduling the slow task to the target computing node, estimates the computing power value of the target computing node after loading the slow task to be scheduled, and uses the estimated computing power When the value is greater than the computing power value of the evaluation reference node, the slow task to be scheduled is scheduled to the target computing node, which can ensure that the computing power of the target computing node will not drop too much after loading the slow task, thereby avoiding new The generation of slow tasks prevents multiple scheduling of slow tasks, and effectively suppresses the occurrence of jitter during slow task scheduling.

Those of ordinary skill in the art can understand that all or part of the steps for implementing the above method embodiments can be completed by program instructions and related hardware. The aforementioned program can be stored in a computer-readable storage medium. When the program is executed, it executes the steps including the above-mentioned method embodiments; and the aforementioned storage medium includes: ROM, RAM, magnetic disk or optical disk and other various media that can store program codes.

Finally, it should be noted that: the above embodiments are only used to illustrate the technical solutions of the present invention, rather than limiting them; although the present invention has been described in detail with reference to the foregoing embodiments, those of ordinary skill in the art should understand that: It is still possible to modify the technical solutions described in the foregoing embodiments, or perform equivalent replacements for some or all of the technical features; and these modifications or replacements do not make the essence of the corresponding technical solutions deviate from the technical solutions of the various embodiments of the present invention. scope.

Claims (8)

1. a slow method for scheduling task for Map Reduce system, is characterized in that, comprising:

Obtain the computing power value of each computing node in Map Reduce system respectively, the computing power value of described each computing node described v ₁... v _mrepresent the processing speed of each calculation task on described each computing node, described in represent the average treatment speed of the work belonging to described each calculation task respectively, described m represents the total quantity of the calculation task on described each computing node;

According to described computing power value order from big to small, described each computing node is arranged as slow node queue, and chooses front M computing node in described slow node queue, each described computing node chosen is as target computing nodes, and described M is natural number;

Obtain the computing power value that M described target computing nodes is estimated after loading slow task to be scheduled respectively, described in the computing power value estimated $\tilde{c}=(v_1/{\stackrel{\‾}{v}}_1+v_2/{\stackrel{\‾}{v}}_2+...+v_m/{\stackrel{\‾}{v}}_m+v_i/{\stackrel{\‾}{v}}_i)/(m+1),$ Described v _irepresent and target computing nodes waits the processing speed of dispatching slow task, described in represent and target computing nodes waits the average treatment speed of dispatching the work belonging to slow task;

According to the computing power value of each computing node outside the computing power value estimated of described target computing nodes and described target computing nodes, each computing node outside described target computing nodes and described target computing nodes is arranged in new slow node queue according to computing power value order from big to small, and the N number of computing node preset in described slow node queue from tail of the queue is forward metewand node, described N is natural number;

When the computing power value that described target computing nodes is estimated is greater than the computing power value of described metewand node, by described slow task scheduling to be scheduled to described target computing nodes.

2. the slow method for scheduling task of Map Reduce system according to claim 1, is characterized in that, the computing power value of each computing node in described acquisition Map Reduce system, comprising:

Receive the processing speed of the calculation task that each described computing node in described Map Reduce system reports, described calculation task is the calculation task processed on described computing node;

The average treatment speed of the work belonging to described calculation task is obtained, described average treatment speed according to described processing speed described v represents the described processing speed of each calculation task that described work splits into, and described n represents total number of the computing node at each calculation task place of the split one-tenth of described work;

The average treatment speed of described work is sent to described each computing node respectively, and the computing power value of the described each computing node obtained according to the average treatment speed of described work receiving that described each computing node reports.

3. the slow method for scheduling task of Map Reduce system according to claim 1, is characterized in that, the computing power value of each computing node in described acquisition Map Reduce system, comprising:

Receive the processing speed of the calculation task that each described computing node in described Map Reduce system reports, described calculation task is the calculation task processed on described computing node;

The average treatment speed of the work belonging to described calculation task is obtained, described average treatment speed according to described processing speed described v represents the described processing speed of each described calculation task of the split one-tenth of described work, and described n represents total number of the computing node at each calculation task place of the split one-tenth of described work;

The computing power value of described each computing node is obtained according to the average treatment speed of described work.

4. according to the slow method for scheduling task of the arbitrary described Map Reduce system of claim 1-3, it is characterized in that, before the computing power value that described acquisition target computing nodes is estimated after loading slow task to be scheduled, also comprise:

Receive the application calculation task message that the computing node in described Map Reduce system sends.

5. the slow method for scheduling task of Map Reduce system according to claim 1, is characterized in that, the ratio of the sum of the computing node in described N and described Map Reduce system is 10%.

6. a slow task scheduling apparatus for Map Reduce system, is characterized in that, comprising: parameter acquiring unit, ability estimate unit, queue column unit and scheduling processing unit;

Described parameter acquiring unit, for obtaining the computing power value of each computing node in Map Reduce system respectively, the computing power value of described each computing node described v ₁... v _mrepresent the processing speed of each calculation task on described each computing node, described in represent the average treatment speed of the work belonging to described each calculation task respectively, described m represents the total quantity of the calculation task on described each computing node;

Described ability estimates unit, for choose described queue column unit produce slow node queue in before M computing node, each described computing node chosen is as target computing nodes, and described M is natural number; And obtain the computing power value that M described target computing nodes estimates after loading slow task to be scheduled respectively, described in the computing power value estimated $\tilde{c}=(v_1/{\stackrel{\‾}{v}}_1+v_2/{\stackrel{\‾}{v}}_2+...+v_m/{\stackrel{\‾}{v}}_m+v_i/{\stackrel{\‾}{v}}_i)/(m+1),$ Described v _irepresent and target computing nodes waits the processing speed of dispatching slow task, described in represent and target computing nodes waits the average treatment speed of dispatching the work belonging to slow task;

Described queue column unit, for being arranged as slow node queue according to described computing power value order from big to small by described each computing node; And, according to the computing power value of each computing node outside the computing power value estimated of described target computing nodes and described target computing nodes, each computing node outside described target computing nodes and described target computing nodes is arranged in new slow node queue according to computing power value order from big to small;

Described scheduling processing unit, be metewand node for the N number of computing node preset in described slow node queue from tail of the queue forward, described N is natural number; And when the computing power value that described target computing nodes is estimated is greater than the computing power value of described metewand node, by described slow task scheduling to be scheduled to described target computing nodes.

7. the slow task scheduling apparatus of Map Reduce system according to claim 6, is characterized in that, described parameter acquiring unit comprises:

Speed receives subelement, the processing speed of the calculation task that each described computing node for receiving in described Map Reduce system reports, and described calculation task is the calculation task processed on computing node;

Average treatment subelement, for obtaining the average treatment speed of the work belonging to described calculation task, described average treatment speed according to described processing speed described v represents the described processing speed of each described calculation task of the split one-tenth of described work, and described n represents total number of the computing node at each calculation task place of the split one-tenth of described work;

Ability obtains subelement, for the average treatment speed of described work is sent to described each computing node respectively, and the computing power value of the described each computing node obtained according to the average treatment speed of described work receiving that described each computing node reports; Or, for obtaining the computing power value of described each computing node according to the average treatment speed of described work.

8. the slow task scheduling apparatus of the Map Reduce system according to claim 6 or 7, is characterized in that, also comprise:

Scheduling trigger element, for before the computing power value that the target computing nodes in described acquisition Map Reduce system is estimated after loading slow task to be scheduled, receives the application calculation task message that the computing node in described Map Reduce system sends.