CN104935523B - The processing method and equipment of a kind of load balancing - Google Patents

Abstract

The invention discloses a processing method and equipment for load balancing, comprising: obtaining the running time information of each task in an iteration cycle of a working node; according to the obtained running time information of each task and an analysis strategy for the task to be migrated , determine the task to be migrated by the working node within the iteration period; when the number of tasks determined to be migrated exceeds the set value, migrate the task to be migrated to a task other than the working node whose task processing volume is less than the set threshold In this way, the task migration method is used to perform a task migration in multiple iterations of the work point, effectively achieving task load balancing between the work points, avoiding the problem of time consumption in the load balancing strategy in Giraph, and also avoiding Hadoop The speculative execution strategy in the middle has the problem of increasing the network overhead of message communication, which improves the efficiency of task migration in the BSP model and improves the load balance of the system.

Description

A processing method and device for load balancing

technical field

The present invention relates to the technical field of wireless communication, in particular to a load balancing processing method and equipment.

Background technique

The BSP (Bulk-Synchronous Parallel) model is a model based on iterative processing of big data, which is different from the Map Reduce model. In the BSP model, data processing is divided into several tasks, and each task goes through the same iterative phase: synchronization phase, calculation phase and message communication phase.

For the multitasks executed in parallel in the BSP model, dynamic load balancing is a key point in parallel computing. However, the BSP model inevitably has unbalanced load in the high-frequency iteration scenario in the parallel environment.

At present, two solutions are proposed for the problem of load imbalance: one is the load balancing strategy in Giraph; the other is the speculative execution strategy in Hadoop.

Among them, the load balancing strategy in Giraph is the dynamic data partitioning strategy. Three processing methods are used in the dynamic division of data: the first is static division; the second is balanced according to the number of edges; the third is balanced according to the number of vertices.

Specifically, a simple heuristic algorithm is used to realize the dynamic division and balance of data among working points. Including: the first step, sort all the data fragments according to the balance value from large to small; the second step, sort the work points according to the total balance value of each work point to form a work point pile; the third step, the The data fragments are put into the top of the work point heap in order from large to small. After each data fragment is placed, the work point with the data fragment placed is put into the work point heap again, so as to ensure that each time the The data fragmentation is placed in the working point with the smallest used capacity; the fourth step is to return the information list of the balanced data fragmentation; the fifth step is to perform data dynamics according to the returned information list of the balanced data fragmentation Divide the migration.

The speculative execution strategy in Hadoop is mainly that Hadoop detects the slow tasks that exist in a job, and performs speculative execution on the detected slow tasks to start the Map task respectively, and finally selects the output of the fastest-executing task from the slow tasks as The input of the Reduce task.

To sum up, the load balancing strategy in Giraph is used in the BSP model, and data migration is required before each iterative calculation, so that the adjustment takes a lot of time as the cost of load balancing; the speculation in Hadoop is used in the BSP model Since the speculative task starts from superstep 0, which is different from the corresponding slow task, the message communication of the current superstep cannot be carried out. Therefore, the network overhead of message communication needs to be increased.

Contents of the invention

In view of this, the embodiment of the present invention provides a load balancing processing method and equipment, which are used to solve the time-consuming problem of using the load balancing strategy in Giraph in the BSP model at present, and the problem of using Hadoop in the BSP model The speculative execution strategy of , has the problem of increasing the network overhead of message communication.

A processing method for load balancing, comprising:

Obtain the running time information of each task in an iteration cycle of a worker node;

According to the obtained running time information of each task and the analysis strategy of the task to be migrated, determine the task to be migrated of the working node within the iteration period;

When it is determined that the number of tasks to be migrated exceeds a set value, the task to be migrated is migrated to a working node other than the working node whose task processing volume is less than a set threshold.

According to the obtained running time information of each task and the analysis strategy of the task to be migrated, determining the task to be migrated of the working node in the iteration cycle includes:

sorting the running time information of each task according to the acquired running time information of each task;

Using the obtained sorting information, determine the quasi-migration tasks of the worker nodes within the iteration period; and

Using the migration cost model, calculate the migration benefit value of the determined quasi-migration task;

For quasi-migration tasks whose migration income value is greater than the set threshold value, when the task processing volume of the working node where the migration income value is greater than the set threshold value is greater than the set threshold value within the set time, the migration is determined. The quasi-migration tasks whose revenue value is greater than the set threshold value are tasks to be migrated by the working node within the iteration period.

Using the obtained sorting information, determine the quasi-migration tasks of the working nodes in the iteration period, including:

For each run time information in the sorting information, when it is determined that the run time information is greater than the set run time information, determine that the task corresponding to the set run time information is the quasi-migration task of the working node within the iteration period;

Wherein, the set running time information is determined in the following manner:

T=T ₂ +(T ₂ -T ₁ )*1.5; T is the set running time information, T ₂ is the time information corresponding to three-quarters of the sorting information determined according to the obtained sorting information; T ₁ is According to the obtained sorting information, the running time information corresponding to a quarter position in the sorting information is determined.

Using the migration cost model, calculate the migration benefit value of the determined quasi-migration task, including:

Calculate the migration benefit value for the identified quasi-migration tasks by:

G(T)＝ _{T.remainSuperStep} *( _T.runTime -avgRunTime) _{-T.migrateCost} ;

Among them, G(T) is the migration benefit value of the determined quasi-migration task, _{T.remainSuperStep} is the remaining superstep running time information of the determined quasi-migration task, _T.runTime is the running time information of the determined quasi-migration task, and avgRunTime is The average running time information of the non-quasi-migration task of the working node in the iteration cycle, T. _migrateCost is the migration cost time information of the determined quasi-migration task, which is equal to the time length of data loading and the time length of message reading or writing and.

When it is determined that the number of tasks to be migrated exceeds a set value, migrating the task to be migrated to a working node other than the working node whose task processing volume is less than a set threshold includes:

Judging whether the working node has a task to be migrated that is determined to be a task to be migrated for a number of times exceeding a set value within N consecutive iteration cycles;

When there is a task to be migrated whose number of times is determined to be a task to be migrated exceeds a set value, it is determined that a task to be migrated whose number of times is determined to be a task to be migrated exceeds a set value is a migration task, and the determined migration task is migrated to a location other than In the working nodes other than the working nodes, the task processing volume is smaller than the set threshold.

A load balancing processing device comprising:

An acquisition module, configured to acquire the running time information of each task in an iteration cycle of a working node;

A determining module, configured to determine the task to be migrated of the working node within the iteration period according to the obtained running time information of each task and the analysis strategy of the task to be migrated;

The migration module is configured to migrate the task to be migrated to a working node other than the working node whose task processing volume is less than a set threshold when it is determined that the number of times of the task to be migrated exceeds a set value.

The determining module is specifically configured to sort the running time information of each task according to the acquired running time information of each task; use the obtained sorting information to determine that the working node is in the iterative cycle and use the migration cost model to calculate the migration income value of the determined quasi-migration task; for the quasi-migration task whose migration income value is greater than the set threshold value, when the migration income value is greater than the set threshold value of the quasi-migration task When the task processing volume of the working node where the migration task is located is greater than the set threshold within the set time, it is determined that the quasi-migration task whose migration benefit value is greater than the set threshold is the task to be migrated by the working node within the iteration period .

The determining module is specifically configured to, for each piece of running time information in the sorting information, when it is determined that the running time information is greater than the set running time information, determine that the task corresponding to the greater than the set running time information is the task of the working node in the quasi-migration tasks within the iterative cycle;

Wherein, the set running time information is determined in the following manner:

T=T ₂ +(T ₂ -T ₁ )*1.5; T is the set running time information, T ₂ is the time information corresponding to three-quarters of the sorting information determined according to the obtained sorting information; T ₁ is According to the obtained sorting information, the running time information corresponding to a quarter position in the sorting information is determined.

The determination module is specifically used to calculate the migration benefit value of the determined quasi-migration task in the following manner:

G(T)＝ _{T.remainSuperStep} *( _T.runTime -avgRunTime) _{-T.migrateCost} ;

Among them, G(T) is the migration benefit value of the determined quasi-migration task, _{T.remainSuperStep} is the remaining superstep running time information of the determined quasi-migration task, _T.runTime is the running time information of the determined quasi-migration task, and avgRunTime is The average running time information of the non-quasi-migration task of the working node in the iteration cycle, T. _migrateCost is the migration cost time information of the determined quasi-migration task, which is equal to the time length of data loading and the time length of message reading or writing and.

The migration module is specifically used to judge whether there are tasks to be migrated in the working node that are determined to be migrated tasks whose number of times exceeds a set value within N consecutive iteration cycles;

When there is a task to be migrated whose number of times is determined to be a task to be migrated exceeds a set value, it is determined that a task to be migrated whose number of times is determined to be a task to be migrated exceeds a set value is a migration task, and the determined migration task is migrated to a location other than In the working nodes other than the working nodes, the task processing volume is smaller than the set threshold.

The beneficial effects of the present invention are as follows:

The embodiment of the present invention obtains the running time information of each task in an iteration cycle of a working node; according to the acquired running time information of each task and the analysis strategy of the task to be migrated, determine that the working node is in the iteration Tasks to be migrated within the period; when it is determined that the number of tasks to be migrated exceeds a set value, the task to be migrated is migrated to a working node whose task processing capacity is less than the set threshold except the working node, so that by According to the running time information of the task and the analysis strategy of the task to be migrated, the task to be migrated of the working node is screened out, and when the number of tasks determined to be migrated exceeds the set value, the migration of the task to be migrated to all The processing capacity of tasks other than the above-mentioned working nodes is less than the set threshold. That is to say, the task migration method is used to perform a task migration in multiple iterations of the working point, which can effectively achieve task load balancing among the working points and avoid The problem of time consumption in the load balancing strategy in Giraph is eliminated, and the method of real-time monitoring of task running time information avoids the problem of increasing message communication network overhead in the speculative execution strategy in Hadoop, effectively improving the BSP model The efficiency of medium task migration improves the load balance of the system.

Description of drawings

FIG. 1 is a schematic flowchart of a load balancing method provided by Embodiment 1 of the present invention;

Fig. 2 is a schematic flow chart of determining the task to be migrated of the working node within the iterative period;

FIG. 3 is a schematic flowchart of a load balancing method provided by Embodiment 2 of the present invention.

Detailed ways

In order to achieve the purpose of the present invention, the embodiment of the present invention provides a load balancing method and device, by obtaining the running time information of each task in an iteration cycle of a working node; according to the acquired running time information of each task Time information and the analysis strategy of the tasks to be migrated, determine the tasks to be migrated of the working node in the iteration period; when the number of tasks determined to be migrated exceeds the set value, migrate the tasks to be migrated The task processing capacity of other than the above-mentioned working nodes is less than the set threshold. In this way, according to the running time information of the tasks and the analysis strategy of the tasks to be migrated, the tasks to be migrated of the working nodes are screened out, and when determined as the tasks to be migrated When the number of tasks exceeds the set value, start to migrate the task to be migrated to a working node other than the working node whose task processing volume is less than the set threshold, that is to say, using the task migration method, multiple Perform a task migration in the iterative operation, effectively realize task load balancing among work points, avoid the problem of time consumption in the load balancing strategy in Giraph, and use real-time monitoring of task running time information to avoid the use of Hadoop The speculative execution strategy has the problem of increasing the network overhead of message communication, which effectively improves the efficiency of task migration in the BSP model and improves the load balance of the system.

Various embodiments of the present invention will be described in detail below in conjunction with the accompanying drawings.

Embodiment one:

As shown in FIG. 1 , it is a schematic flowchart of a load balancing method provided by Embodiment 1 of the present invention. The method can be described as follows.

Step 101: Obtain the running time information of each task in an iteration period of a worker node.

In step 101, when the task of the working node starts to run, the running time information of each task in the current iteration cycle, the data volume information of the local task, and the messages for the next iteration cycle generated in this iteration cycle The estimated amount information obtained by pre-estimating the amount (it can also be represented by the time information of the read/write checkpoint).

It should be noted that the data volume information of the local tasks obtained through statistics and the estimated volume information obtained by pre-estimating the amount of messages generated in this iteration cycle for the next iteration cycle will involve the calculation task migration. Migration costs.

When there are M tasks executed by the working point in this iteration period, then the statistically obtained running time information of each task is: T ₁ , T ₂ , T ₃ , . . . , T _m .

Step 102: According to the obtained running time information of each task and the analysis policy of the task to be migrated, determine the task to be migrated of the working node within the iteration period.

In step 102, according to the obtained running time information of each task and the analysis strategy of the task to be migrated, the manner of determining the task to be migrated of the working node in the iteration cycle includes but not limited to the following manners:

As shown in FIG. 2 , it is a schematic flowchart of determining tasks to be migrated of the working nodes within the iteration period.

Step 201: sort the running time information of each task according to the acquired running time information of each task.

In step 201, when the running time information of each task is acquired, the running time information of each task is sorted according to a set sorting rule.

For example: the set sorting rule is the order from small to large according to the running time information; or the order from large to small according to the running time information; there is no limitation here.

Specifically, it is assumed that the obtained running time information of each task (wherein, the subscript represents the task identifier) is T ₁ =1s, T ₂ =2s, T ₃ =4s, T ₄ =5s, T ₅ =7s , T ₆ =3.5s, T ₇ =1.5s, T ₈ =9s, T ₉ =3s, T ₁₀ =0.5s, T ₁₁ =4.5s, T ₁₂ =6s, according to the order of running time information from small to large Sorting, the obtained sequence is: {T ₁₀ , T ₁ , T ₇ , T ₂ , T ₉ , T ₆ , T ₃ , T ₁₁ , T ₄ , T ₁₂ , T ₅ , T ₈ }.

Step 202: Using the obtained sorting information, determine the quasi-migration tasks of the working nodes within the iteration period.

In step 202, for each piece of running time information in the sorting information, when it is determined that the running time information is greater than the set running time information, it is determined that the task corresponding to the set running time information is greater than the set running time information as the task of the working node within the iteration cycle quasi-migration tasks.

Wherein, the set running time information is determined in the following manner:

T=T ₂ +(T ₂ -T ₁ )*1.5; T is the set running time information, T ₂ is the time information corresponding to three-quarters of the sorting information determined according to the obtained sorting information; T ₁ is According to the obtained sorting information, the running time information corresponding to a quarter position in the sorting information is determined.

Specifically, firstly, according to the obtained sorting information, the first running time information corresponding to the 1/4 position and the second running time information corresponding to the 3/4 position in the sorting information are determined.

Still taking the above example as an example, the obtained sequence is: {T ₁₀ , T ₁ , T ₇ , T ₂ , T ₉ , T ₆ , T ₃ , T ₁₁ , T ₄ , T ₁₂ , T ₅ , T ₈ }, According to the obtained sequence information, the first running time information corresponding to the quarter position is T ₇ , that is, the running time information corresponding to the task ID 7, and the second running time information corresponding to the three-quarter position is T ₄ , that is, the running time information corresponding to task ID 4.

Secondly, for each running time information in the sorting information, it is judged whether the running time information is greater than the set running threshold, and if the running time information is greater than the set running threshold, then it is determined that the task corresponding to the running time information is the working node A quasi-migration task within the iterative period; otherwise, it is determined that the task corresponding to the running time information is not a quasi-migration task of the working node within the iterative period.

Wherein, the set operating threshold may be the sum of the second operating time information and (second operating time information-first operating time information)*1.5, and may also be determined through experimental data or actual experience, where No limit.

Specifically, when it is determined that the running time information is greater than [second running time information+(second running time information-first running time information)*1.5], it is determined that it is greater than [second running time information+(second running time information- The task corresponding to the running time information of the first running time information)*1.5] is the quasi-migration task of the working node in the iteration period.

For example: still taking the above example as an example, according to the obtained sequence information, the first running time information corresponding to the quarter position is T ₇ , that is, the running time information corresponding to the task ID 7, and the three-quarter position corresponds to The second running time information of T ₄ is T 4 , that is, the running time information corresponding to task ID 4, and the set running threshold value obtained is 7.75s. Therefore, the task whose running time information is greater than 7.75s is task 8, that is, In this example, the determined quasi-migration task of the working node within the iteration period is task 8 .

Step 203: Using the migration cost model, calculate the migration benefit value of the determined quasi-migration task.

In step 203, the migration benefit value of the determined quasi-migration task is calculated in the following manner:

G(T)＝ _{T.remainSuperStep} *( _T.runTime -avgRunTime) _{-T.migrateCost} ;

Among them, G(T) is the migration benefit value of the determined quasi-migration task, _{T.remainSuperStep} is the remaining superstep running time information of the determined quasi-migration task, _T.runTime is the running time information of the determined quasi-migration task, and avgRunTime is The average running time information of the non-quasi-migration task of the working node in the iteration cycle, T. _migrateCost is the migration cost time information of the determined quasi-migration task, which is equal to the time length of data loading and the time length of message reading or writing and.

It should be noted that _{T.migrateCost} is the migration cost information obtained when the running time information of each task is obtained in step 101, which can be obtained from the graph data and message read/write checkpoint time. Among them, the reading and writing time of graph data can be approximated by the time of reading and writing checkpoint graph data (or twice the loading time of graph data); the read/write time of message data can be evaluated by reading the amount of message data used in this iteration. Write time, the calculation formula is: read and write message data time = read and write map data time / map data size (bytes) * total message data size (bytes).

Step 204: For quasi-migration tasks whose migration income value is greater than the set threshold value, when the task processing volume of the working node where the migration income value is greater than the set threshold value is greater than the set threshold value within the set time , it is determined that the quasi-migration task whose migration benefit value is greater than the set threshold is the task to be migrated by the working node within the iterative period.

Wherein, the threshold value is generally set to 0, which means that the transfer benefit value may be a negative value, but the research object of step 204 is a task corresponding to a transfer benefit value greater than 0.

In step 204, after obtaining the quasi-migration task whose migration benefit value is greater than the set threshold value, it is necessary to judge the task processing capacity of the working point where the quasi-migrating task is located within the set time. The task processing capacity of the point within the set time is not large, so that the work point has more idle resources. At this time, the quasi-migration task determined at this time will not be considered as the task to be migrated; only when the work point where the quasi-migration task is located is within the set time When the amount of task processing within is greater than the set threshold, it means that the load of the working point is relatively heavy within the set time, and the task processing pressure of the working point is reduced by the necessary migration tasks, so the quasi-migration tasks determined at this time will be used as the described Tasks to be migrated of the working nodes within the iteration period.

Among them, the set time can be 20% of the product of the remaining superstep running time of the determined quasi-migration task and the average running time of the tasks in the work waiting point (that is, avgRunTime* _{T.remainSuperStep} ), or it can be experimental data or through It needs to be determined actually, and there is no limitation here.

The set threshold can be one-half of the task processing capacity of the working point, or can be determined by experimental data or actual needs, and is not limited here.

This effectively avoids the possibility of a large number of task migration in the work point, reduces the consumption of system resources, and improves the accuracy of task migration.

Step 103: When it is determined that the number of tasks to be migrated exceeds a set value, migrate the task to be migrated to a working node other than the working node whose task processing volume is less than a set threshold.

In step 103, firstly, it is judged whether there is a task to be migrated in the working node within N consecutive iteration periods, the number of times of which the task is determined to be migrated exceeds a set value.

Among them, N is a natural number and is less than the total number of iteration cycles of the working point where the task to be migrated is located.

Here, an error in determining the migration task due to an iterative statistical data error is avoided, and the accuracy of the task migration is improved.

Secondly, when there is a task to be migrated whose number of tasks determined to be migrated exceeds a set value, it is determined that the task to be migrated whose number of times exceeds a set value is determined to be a migration task, and the determined migration task is migrated To the working nodes other than the working nodes whose task processing volume is less than the set threshold.

Through the solution of Embodiment 1 of the present invention, the running time information of each task in one iteration cycle of a working node is obtained; according to the obtained running time information of each task and the analysis strategy of the task to be migrated, the work is determined The task to be migrated by the node within the iterative period; when it is determined that the number of tasks to be migrated exceeds the set value, the task to be migrated is migrated to a task whose processing volume is less than the set threshold except the working node In this way, according to the running time information of the task and the analysis strategy of the task to be migrated, the task to be migrated of the working node is screened out, and when the number of tasks determined to be migrated exceeds the set value, the task to be migrated is started. The task is migrated to a working node other than the working node whose task processing volume is less than the set threshold, that is to say, the task migration method is used to perform a task migration in multiple iterations of the working point, effectively realizing the task between the working points. Task load balancing avoids the time consumption problem of using the load balancing strategy in Giraph, and adopts the method of real-time monitoring of task running time information to avoid the problem of increasing message communication network overhead in Hadoop's speculative execution strategy, which is effective It greatly improves the efficiency of task migration in the BSP model and improves the load balance of the system.

Embodiment two:

As shown in Figure 3, it is a schematic structural diagram of a load balancing processing device provided by Embodiment 2 of the present invention. Embodiment 2 of the present invention is an invention under the same inventive concept as Embodiment 1 of the present invention. The device includes: Obtaining module 11, determining module 12 and migration module 13, wherein:

An acquisition module 11, configured to acquire the running time information of each task in an iteration cycle of a working node;

A determining module 12, configured to determine the task to be migrated of the working node within the iteration period according to the acquired running time information of each task and the analysis strategy of the task to be migrated;

The migration module 13 is configured to migrate the task to be migrated to a working node other than the working node whose task processing capacity is less than a set threshold when it is determined that the number of times of the task to be migrated exceeds a set value.

Specifically, the determining module 12 is specifically configured to sort the running time information of each task according to the acquired running time information of each task; use the obtained sorting information to determine that the working node is quasi-migration tasks within the iterative cycle; and use the migration cost model to calculate the migration income value of the determined quasi-migration task; for quasi-migration tasks whose migration income value is greater than the set threshold value, when the migration income value is greater than the set threshold When the task processing capacity of the working node where the quasi-migration task of the limit value is located is greater than the set threshold within the set time, it is determined that the quasi-migration task whose migration benefit value is greater than the set threshold value is that the working node is within the iteration period. tasks to be migrated.

The determining module 12 is specifically configured to, for each piece of running time information in the sorting information, when it is determined that the running time information is greater than the set running time information, determine that the task corresponding to the set running time information is greater than the set running time information as the task of the working node. quasi-migration tasks within the above iteration cycle;

Wherein, the set running time information is determined in the following manner:

T=T ₂ +(T ₂ -T ₁ )*1.5; T is the set running time information, T ₂ is the time information corresponding to three-quarters of the sorting information determined according to the obtained sorting information; T ₁ is According to the obtained sorting information, the running time information corresponding to a quarter position in the sorting information is determined.

The determination module 12 is specifically configured to calculate the migration benefit value of the determined quasi-migration task in the following manner:

G(T)＝ _{T.remainSuperStep} *( _T.runTime -avgRunT ⁱ me) _{-T.migrateCost} ;

Among them, G(T) is the migration benefit value of the determined quasi-migration task, _{T.remainSuperStep} is the remaining superstep running time information of the determined quasi-migration task, _T.runTime is the running time information of the determined quasi-migration task, and avgRunTime is The average running time information of the non-quasi-migration task of the working node in the iteration cycle, T. _migrateCost is the migration cost time information of the determined quasi-migration task, which is equal to the time length of data loading and the time length of message reading or writing and.

The migration module 13 is specifically used to judge whether there are tasks to be migrated in the working node that are determined to be migration tasks whose number of times exceeds a set value within N consecutive iteration cycles;

When there is a task to be migrated whose number of times is determined to be a task to be migrated exceeds a set value, it is determined that a task to be migrated whose number of times is determined to be a task to be migrated exceeds a set value is a migration task, and the determined migration task is migrated to a location other than In the working nodes other than the working nodes, the task processing volume is smaller than the set threshold.

Among them, N is a natural number and is less than the total number of iteration cycles of the working point where the task to be migrated is located.

It should be noted that the processing device described in the embodiment of the present invention may be implemented by means of hardware or software, which is not limited here.

Those skilled in the art should understand that the embodiments of the present invention may be provided as methods, devices (devices), or computer program products. Accordingly, the present invention can take the form of an entirely hardware embodiment, an entirely software embodiment, or an embodiment combining software and hardware aspects. Furthermore, the present invention may take the form of a computer program product embodied on one or more computer-usable storage media (including but not limited to disk storage, CD-ROM, optical storage, etc.) having computer-usable program code embodied therein.

The present invention is described with reference to flowchart illustrations and/or block diagrams of methods, apparatus (devices) and computer program products according to embodiments of the invention. It should be understood that each procedure and/or block in the flowchart and/or block diagram, and a combination of procedures and/or blocks in the flowchart and/or block diagram can be realized by computer program instructions. These computer program instructions may be provided to a general purpose computer, special purpose computer, embedded processor, or processor of other programmable data processing equipment to produce a machine such that the instructions executed by the processor of the computer or other programmable data processing equipment produce a An apparatus for realizing the functions specified in one or more procedures of the flowchart and/or one or more blocks of the block diagram.

These computer program instructions may also be stored in a computer-readable memory capable of directing a computer or other programmable data processing apparatus to operate in a specific manner, such that the instructions stored in the computer-readable memory produce an article of manufacture comprising instruction means, the instructions The device realizes the function specified in one or more procedures of the flowchart and/or one or more blocks of the block diagram.

These computer program instructions can also be loaded onto a computer or other programmable data processing device, causing a series of operational steps to be performed on the computer or other programmable device to produce a computer-implemented process, thereby The instructions provide steps for implementing the functions specified in the flow chart or blocks of the flowchart and/or the block or blocks of the block diagrams.

While preferred embodiments of the invention have been described, additional changes and modifications to these embodiments can be made by those skilled in the art once the basic inventive concept is appreciated. Therefore, it is intended that the appended claims be construed to cover the preferred embodiment as well as all changes and modifications which fall within the scope of the invention.

Obviously, those skilled in the art can make various changes and modifications to the present invention without departing from the spirit and scope of the present invention. Thus, if these modifications and variations of the present invention fall within the scope of the claims of the present invention and their equivalent technologies, the present invention also intends to include these modifications and variations.

Claims (8)

1. a kind of processing method of load balancing, which is characterized in that including：

Obtain the run time information of each task in an iteration cycle of a working node；

The analysis strategy of the run time information of each task and task to be migrated according to acquisition, determines the work Make to be migrated task of the node in the iteration cycle；

When the number for being determined as task to be migrated is more than setting numerical value, by the task immigration to be migrated in addition to the work Task treating capacity except node is less than the working node of given threshold；

When the number for being determined as task to be migrated is more than setting numerical value, by the task immigration to be migrated in addition to the work Task treating capacity except node is less than the working node of given threshold, including：

Judge that the working node whether there is the number for being determined as task to be migrated more than setting in continuous N number of iteration cycle The task to be migrated of numerical value；

When there is the task to be migrated that the number for being determined as task to be migrated is more than setting numerical value, judgement is determined as to be migrated The number of business is more than to set the task to be migrated of numerical value as migration task, and by the migration task immigration of judgement in addition to institute The task treating capacity except working node is stated to be less than in the working node of given threshold.

2. processing method as described in claim 1, which is characterized in that the run time of each task according to acquisition The analysis strategy of information and task to be migrated determines to be migrated task of the working node in the iteration cycle, packet It includes：

The run time information of each task according to acquisition carries out the run time information of each task Sequence；

Using obtained sequencing information, quasi- migration task of the working node in the iteration cycle is determined；And

Using Cost Model is migrated, the migration financial value of determining quasi- migration task is calculated；

It is more than the quasi- migration task of setting threshold value for migration financial value, when the standard that migration financial value is more than setting threshold value is moved When task treating capacity of the working node in setting time where shifting task is more than given threshold, determine that migration financial value is more than The task to be migrated that the quasi- migration task for setting threshold value is the working node in the iteration cycle.

3. processing method as claimed in claim 2, which is characterized in that using obtained sequencing information, determine the work section Quasi- migration task of the point in the iteration cycle, including：

For each run time information in sequencing information, run time information is set determining that run time information is more than When, it determines to be more than set that the corresponding task of run time information be the working node in the iteration cycle accurate and migrates times Business；

Wherein, the setting run time information determines in the following manner：

T=T₂+(T₂-T₁)*1.5；T is sets run time information, T₂According to obtained sequencing information, determine in sequencing information Corresponding temporal information at 3/4ths；T₁According to obtained sequencing information, determine in sequencing information at a quarter position Corresponding run time information.

4. processing method as claimed in claim 2 or claim 3, which is characterized in that using Cost Model is migrated, calculate determining standard and move The migration financial value of shifting task, including：

The migration financial value of determining quasi- migration task is calculated in the following manner：

G (T)=T._{remainSuperStep}*(T._runTime-avgRunTime)-T._migrateCost；

Wherein, G (T) is the migration financial value of determining quasi- migration task, T._{remainSuperStep}For determining quasi- migration task Remaining superledge run time information, T._runTimeFor the run time information of determining quasi- migration task, avgRunTime is described The average operating time information of working node non-quasi- migration task in the iteration cycle, T._migrateCostIt is moved for determining standard The migration cost temporal information of shifting task, equal to time span and the sum of the message reading or the time span write of data loading.

5. a kind of processing equipment of load balancing, which is characterized in that including：

Acquisition module, for obtaining the run time information of each task in an iteration cycle of a working node；

Determining module, for the analysis plan of the run time information of each task and task to be migrated according to acquisition Slightly, to be migrated task of the working node in the iteration cycle is determined；

Transferring module, for when be determined as task to be migrated number be more than setting numerical value when, by the task immigration to be migrated It is less than the working node of given threshold to the task treating capacity other than the working node；

The transferring module is determined as treating specifically for judging that the working node whether there is in continuous N number of iteration cycle The number of migration task is more than the task to be migrated of setting numerical value；

When there is the task to be migrated that the number for being determined as task to be migrated is more than setting numerical value, judgement is determined as to be migrated The number of business is more than to set the task to be migrated of numerical value as migration task, and by the migration task immigration of judgement in addition to institute The task treating capacity except working node is stated to be less than in the working node of given threshold.

6. processing equipment as claimed in claim 5, which is characterized in that

The determining module, specifically for the run time information of each task according to acquisition, will it is described each The run time information of task is ranked up；Using obtained sequencing information, determine the working node in the iteration cycle Interior quasi- migration task；And using Cost Model is migrated, calculate the migration financial value of determining quasi- migration task；Migration is received Benefit value is more than the quasi- migration task of setting threshold value, the work where migration financial value is more than the quasi- migration task of setting threshold value When making task treating capacity of the node in setting time more than given threshold, determine that migration financial value is more than the standard of setting threshold value Migration task is to be migrated task of the working node in the iteration cycle.

7. processing equipment as claimed in claim 6, which is characterized in that

The determining module specifically for each the run time information being directed in sequencing information, is determining run time letter When breath is more than setting run time information, determine to be more than that set the corresponding task of run time information be the working node in institute State the quasi- migration task in iteration cycle；

Wherein, the setting run time information determines in the following manner：

T=T₂+(T₂-T₁)*1.5；T is sets run time information, T₂According to obtained sequencing information, determine in sequencing information Corresponding temporal information at 3/4ths；T₁According to obtained sequencing information, determine in sequencing information at a quarter position Corresponding run time information.

8. processing equipment as claimed in claims 6 or 7, which is characterized in that

The determining module, specifically for calculating the migration financial value of determining quasi- migration task in the following manner：

G (T)=T._{remainSuperStep}*(T._runTime-avgRunTime)-T._migrateCost；

Wherein, G (T) is the migration financial value of determining quasi- migration task, T._{remainSuperStep}For determining quasi- migration task Remaining superledge run time information, T._runTimeFor the run time information of determining quasi- migration task, avgRunTime is described The average operating time information of working node non-quasi- migration task in the iteration cycle, T._migrateCostIt is moved for determining standard The migration cost temporal information of shifting task, equal to time span and the sum of the message reading or the time span write of data loading.