CN104536806A - Workflow application flexible resource supplying method in cloud environment - Google Patents

Abstract

The invention discloses a flexible resource supply method for workflow application in a cloud environment, which considers a time interval-based on-demand charging model, data transmission time, virtual machine start-up time, software installation (download) time, and the like. The multi-rule-based heuristic method (MRH) disclosed in the present invention mainly includes: A) division of subtask deadlines; B) matching method of multi-rule-based subtasks and virtual machine time slots; the main feature of step A is to pass Delete the constraint of charging by interval in the original problem, simplify the original problem, and then solve the integer programming model of the problem to obtain the deadline of each subtask. The main feature of step B is to propose three priority rules that consider multiple factors, and match tasks to appropriate virtual machine idle time slots. The invention fully reduces the resource leasing cost of the entire workflow application through the appropriate subtask deadline division and multi-rule time slot matching method.

Description

A Method for Elastic Resource Supply of Workflow Application in Cloud Environment

technical field

The invention relates to a workflow application flexible resource supply method in a cloud environment, and belongs to the technical field of cloud computing resource scheduling.

Background technique

Based on the development of distributed computing, especially grid computing, a new service computing model has emerged: Cloud Computing. Cloud computing is a mode that can access a configurable shared pool of computing resources in a convenient and on-demand manner through the network. This shared pool of resources can be quickly configured, Provide or release resources. The main advantages of cloud computing are: it can quickly reduce hardware costs and increase computing power and storage capacity; Maintenance and upgrades.

Due to the above advantages, many companies and research institutions are trying to migrate their real-time analysis, online advertising, and scientific computing applications to the existing commercial cloud to solve the data processing problem when the amount of data grows on a large scale. It is a huge challenge for users to achieve a reasonable mapping between computing or storage tasks and purchased resources. The self-scaling nature of the cloud (acquiring or releasing appropriate types and quantities of resources at any time according to the volume of the application, and billing according to the usage) provides a more flexible resource supply solution. Too low resource allocation will lead to the decline of system performance, resulting in the delay of the deadline; and too high resource allocation will cause idle time slots, increasing unnecessary overhead. Therefore, users need to propose a reasonable resource self-scaling strategy to save rental costs while ensuring system performance.

Analytical and scientific computing applications are an important class of applications based on commercial clouds, and usually need to solve a large amount of data. In order to reduce the execution time, the data can be divided and solved with parallel tasks. At the same time, these applications are also composed of multiple sequential steps and data transfer between parallel and sequential tasks. Such applications containing parallel and sequential tasks can be modeled with workflows. At the same time, most of these applications have deadlines. Therefore, in order to seek a balance between resource rental costs and workflow completion time, cloud users need to assign workflow tasks to appropriate types and numbers of VM instances.

However, because in practical applications, the renting of cloud environments usually adopts an hourly billing model, and factors such as software preparation time, data transmission time, complex network structure, and task diversity need to be considered, resource supply and scheduling issues are difficult. solve.

At present, there are methods and projects focusing on solving the workflow scheduling problem of complex factors in the cloud environment. However, these methods do not take into account the dynamic adjustment strategies in the cloud computing environment under sudden demand and constraints, and rarely take into account the constraints of large-scale data transmission time and software unit switching time in practical applications, so they cannot be applied to this paper. In the context of the invention discussed.

Contents of the invention

Purpose of the invention: Aiming at the problems and deficiencies in the prior art, the present invention provides a flexible resource supply method for workflow applications in a cloud environment, so as to reduce virtual machine rent on the premise of ensuring system performance.

Technical solution: a workflow application elastic resource supply method in a cloud environment, comprising the following steps:

A. Workflow deadline division: Calculate the execution time and cost of each task in the workflow on each virtual machine type, with the goal of minimizing the total rental cost of the virtual machine without violating the workflow deadline, regardless of the interval According to the constraints of billing, the workflow problem is simplified into an integer programming problem, and the virtual machine type selected by each task is solved to determine the task execution time; according to the workflow deadline, the prior relationship between tasks and the task execution time, determine each task deadline;

B. Task scheduling according to priority rules: Schedule tasks in order according to the depth of tasks in the workflow from small to large. For each task, calculate the priority of all virtual machine time slots according to its deadline and based on priority rules. Assign the task to the virtual machine time slot with the highest priority, the priority rules include the least new lease time interval priority, the lowest total processing cost priority, and the best matching degree of task processing time and time slot length priority .

The execution time of each task on each virtual machine type in step A includes data transmission time, virtual machine and software preparation time.

In the step A, the specific steps for determining the deadline of each task according to the deadline of the workflow, the prior relationship between tasks and the execution time of the task include:

S1. For each task v in the task set V, set Initialize as the sum of data transmission time, VM preparation time, software preparation time and task execution time, calculate the earliest start time EST _v , the earliest end time EFT _v and the latest end time LFT _v of each task;

S2. Using the critical path generation method to iteratively generate the initial critical path CP, CP _[i] represents the i-th task of the CP;

S3. Determine whether the CP is empty, if it is empty, go to step S10; otherwise, go to step S4;

S4. Calculate the total time float of CP $T_{\mathrm{CP}}^{\mathrm{float}}={\mathrm{\Σ}}_{{\mathrm{CP}}_{\left[k\right]\∈{\mathrm{CP}}^{\′}}}({\mathrm{EST}}_{{\mathrm{CP}}_{[k+1]}}-{\mathrm{EFT}}_{{\mathrm{CP}}_{\left[k\right]}})+{\mathrm{LFT}}_{{\mathrm{CP}}_{\left[l\right]}}-$ ${\mathrm{EFT}}_{{\mathrm{CP}}_{\left[l\right]}};$ Wherein, CP′=CP/V ^fix /{CP _[l] };, l is the length of CP.

S5. Judgment Whether it is greater than 0, if greater than 0, go to step S6; otherwise, go to step S12;

S6. Initialize i=1;

S7. judge i≤l, if so, go to step S8; otherwise, go to step S11;

S8. For the task CP _[i] in the CP, judge whether CP _[i] belongs to the fixed task set V ^fix , where the fixed task set V ^fix satisfies the time floating A set composed of all tasks v of ; if it belongs to, go to step S10;

S9. Compute the allocated float of CP _[i] $T_{C{P}_{\left[i\right]}}^{\mathrm{dis}}=T_{\mathrm{CP}}^{\mathrm{float}}\×T_{{\mathrm{CP}}_{\left[i\right]}}^{\mathrm{float}}/{\mathrm{\Σ}}_{v_k\∈\mathrm{CP}/V^{\mathrm{fix}}}\left\{T_{v_k}^{\mathrm{float}}\right\},$ update its time float Update the earliest start and earliest end times of its successor tasks;

S10. Update i=i+1;

S11. Update the latest end time and V ^fix of all tasks in V, go to step S4;

S12. Generate the next critical path CP, and turn to step S3;

S13. Set the task deadline for each task for

In the step B, including:

B1. Initialize the prepared task set θ as a set {v ₀ } containing only start tasks, and calculate the earliest start time of each task in θ;

B2. Divide θ into subsets according to the depth of each task in the prepared task set θ, select the subset θ _s with the smallest depth, sort the tasks in non-ascending order according to the execution time, and select the first task v _t is the task to be scheduled; if v _t is empty, go to step B5;

B3. For the current task v _t , temporarily add an instance of the selected virtual machine type to the rented virtual machine instance set I in the cloud environment; obtain v _t according to the earliest start time and deadline of the task The set of currently available time slots

B4. According to the priority rules, calculate the task v _t in The priority value on each time slot slot in , including the priority value obtained according to the least new lease time interval priority rule According to the lowest total processing cost priority rule And according to the priority rule of the best matching degree between task processing time and time slot length by putting and Integrate according to the set weight to obtain the final priority value of v _t on the slot, select the time slot slot _s with the highest priority among them, and assign the task v _t to slot _s ; remove unused VM instances in I; update The prepared task set θ, if θ is not empty, go to step B2;

B5. The task matches the time slot of the virtual machine and exits.

Beneficial effects: Compared with the prior art, the present invention simplifies the original problem into a DTCTP (Discrete Time Cost Tradeoff Problem) problem, and uses the integer programming model (IP) to solve the virtual machine type of each task; after the sub-deadline of the task is determined, According to the proposed three priority rules that consider multiple factors (such as reuse of leased intervals, VM loading time, software preparation time, data transmission time, execution efficiency, matching of time slots and task execution time lengths, etc.), for each A task selects a suitable virtual machine (VM) time slot, assigns tasks to VM instances one by one, and guarantees that the sub-deadlines are not violated; when all task assignments are completed, a scheduling result that can be used for actual execution is obtained. The multi-rule-based heuristic Multiple-Rules based Heuristc (MRH) resource supply method provided by the present invention considers the workflow based on the time interval charging model, data transmission time, VM startup time and software preparation time in the cloud environment Scheduling problem in maximizing resource reuse and installed software reuse.

Description of drawings

FIG. 1 is a structural diagram of an embodiment of the present invention implementing a workflow application flexible resource supply method in a cloud environment;

Fig. 2 is a flow chart of the workflow deadline division part in the embodiment of the present invention;

Fig. 3 is a flow chart of the task scheduling part according to the priority rules in the embodiment of the present invention.

Detailed ways

Below in conjunction with specific embodiment, further illustrate the present invention, should be understood that these embodiments are only used to illustrate the present invention and are not intended to limit the scope of the present invention, after having read the present invention, those skilled in the art will understand various equivalent forms of the present invention All modifications fall within the scope defined by the appended claims of the present application.

The embodiment of the present invention realizes the structural diagram of the workflow application elastic resource supply method in the cloud environment as shown in Figure 1, including the cloud service provider 11, workflow application 12, elastic intermediary 13, workflow scheduler 14 and leased A data center 15 composed of virtual machines. In this embodiment, it is assumed that the cloud environment mainly includes two roles, that is, cloud service providers (such as IaaS providers) and cloud service users. Cloud service providers provide resource leasing services (such as virtual machines and storage resources) to cloud service users, and resource leasing is billed according to time intervals. Cloud service users rent resources from cloud service providers to build their own virtual data centers to serve their own workflow applications. Elastic intermediaries and workflow schedulers provide cloud service users with an automatic scaling mechanism to help users minimize resource rental costs without violating workflow application deadlines.

Workflow G={V, E} is a directed acyclic graph, where V={v ₀ , v ₁ ,...,v _N+1 } is a collection of N+2 tasks, E={(i, j)∨i<j} is the preorder constraint between tasks, that is, v _j cannot start before v _i is completed, P _i and S _i are the direct predecessor set and direct successor set of task v _i respectively; D represents the workflow Deadline.

When a workflow G={V, E} is submitted to the system, the workflow scheduler is responsible for combining the tasks V={v ₀ ,v ₁ ,…,v _N+1 } contained in the workflow with the virtual The machine instance time slot slot is matched, that is, the lease cost is minimized under the premise of meeting the workflow deadline. According to the scheduling result of the workflow scheduler, the elastic intermediary leases or releases the resources at the cloud service provider. The scheduling of workflow scheduler is divided into two parts: workflow deadline division and task scheduling according to priority rules.

Fig. 2 is a flow chart of the workflow deadline division part in the embodiment of the present invention. As shown in Figure 2, the specific steps of workflow deadline division are as follows:

In step s201, for the original problem, it is assumed that the task processing time includes data transmission time and virtual machine and software preparation time, and virtual machine instances are billed in a continuous manner (rather than in a discrete manner). First, we add data transmission time and virtual machine and software preparation time to the execution time of each mode; accordingly, the execution time p _i,t and execution cost c i of task v _i on virtual machine type δ _t are calculated _{, t} . After deleting the original problem according to the constraint of interval charging, the problem can be simplified as a type decision problem, which is modeled by integer programming (IP).

In step s202, an integer programming solver, such as CPLEX, is used to obtain an approximate optimal solution to the simplified problem, and the obtained solution is R; in R, the selected virtual machine type for each subtask is given, that is, the execution mode. in Indicates the virtual machine type number of task v _i in R.

Step s202, use CPLEX to find an approximate optimal solution to the simplified problem, and the obtained solution is R, where Indicates the virtual machine type number of task v _i in R.

Step s203, for each task v in V, It is initialized as the sum of data transmission time, VM preparation time, software preparation time and task execution time, and calculates the earliest start time EST _v , the earliest end time EFT _v and the latest end time LFT _v of each task.

In step s204 , iteratively generate an initial critical path CP by using the critical path generation method proposed by Abrishami et al., and CP _[i] represents the ith task of the CP.

Step s205, judging whether the CP is empty, if not, go to step s212; otherwise, go to step s206.

Step s206, calculating the total time float of CP $T_{\mathrm{CP}}^{\mathrm{float}}={\mathrm{\&Sigma;}}_{{\mathrm{CP}}_{\left[k\right]\&Element;{\mathrm{CP}}^{\&prime;}}}({\mathrm{EST}}_{C{P}_{[k+1]}}-{\mathrm{EFT}}_{{\mathrm{CP}}_{\left[k\right]}})+$ ${\mathrm{LFT}}_{{\mathrm{CP}}_{\left[l\right]}}-{\mathrm{EFT}}_{{\mathrm{CP}}_{\left[l\right]}}.$ Wherein, CP'=CP/V ^fix /{CP _[l] }, l is the length of CP.

Step s207, judge Whether it is greater than 0, if greater than 0, go to step s208; otherwise, go to step s214.

Step s208, initialize i=1.

Step s209, judge i≤l, if yes, go to step s210; otherwise, go to step s213.

Step s210, for the task CP _[i] in the CP, judge whether CP _[i] belongs to the fixed task set V ^fix , where the fixed task set V ^fix satisfies the time floating A set composed of all tasks v; if it belongs to, go to step s212;

Step s211, calculate the allocated float of CP _[i] $T_{C{P}_{\left[i\right]}}^{\mathrm{dis}}=T_{\mathrm{CP}}^{\mathrm{float}}\&times;T_{{\mathrm{CP}}_{\left[i\right]}}^{\mathrm{float}}/{\mathrm{\&Sigma;}}_{v_k\&Element;\mathrm{CP}/V^{\mathrm{fix}}}\left\{T_{v_k}^{\mathrm{float}}\right\},$ update its time float Update the earliest start and earliest end times of its successor tasks.

Step s212, updating i=i+1.

Step s213, update the latest end time and V ^fix of all tasks in V, go to step s206.

Step s214, generate the next critical path CP, go to step s205.

Step s215, setting the task deadline for each task for Go to step s301.

Fig. 3 is a flow chart of the task scheduling part according to the priority rules in the embodiment of the present invention. As shown in Figure 3, the specific steps for task scheduling according to priority rules are as follows:

Step s301, initialize the prepared task set θ as a set {v ₀ } containing only start tasks, and calculate the earliest start time of each task in θ.

Step s302, divide θ into subsets according to the depth of each task in the prepared task set θ.

Step s303 , select the subset θ _s with the smallest depth, sort the tasks in it according to the execution time in non-ascending order, and select the first task v _t among them as the task to be scheduled.

Step s304, judging whether v _t is empty, if v _t is empty, the method ends; otherwise, go to step s305.

Step s305, for the VM type of v _t selection mode, select an instance and temporarily add it to the leased VM instance set I in the cloud environment.

Step s306, according to the earliest start time and subtask deadline, obtain the set of time slots currently available for v _t

Step s307, yes For each time slot slot in , calculate its priority value according to three priority rules and select has the smallest (i.e. the highest priority) time slot slot _s . The three priority rule calculations are:

1) The least new lease time interval is preferred

The number of new lease time intervals assigned to the task v _t is the number of billing intervals required on the virtual machine and the actual number of new lease time slices to obtain the rule value The specific calculation method is: 1) Calculate the number of billing intervals required by v _t on the slot type virtual machine, add 1 to obtain the maximum number of intervals required; 2) calculate the actual new billing intervals caused by v _t on the slot Divide the number of leased time slices by the maximum number of intervals obtained in step 1), thus obtaining

2) The lowest total processing cost is preferred

When calculating the priority value of the rule for task v _t on the slot, first obtain the task execution time of v _t according to the type of virtual machine where the slot is located; then, check whether it is a newly leased virtual machine, and if so, the processing time Add the loading time of the virtual machine; if it is an existing virtual machine instance, check whether there are software and controls required by _vt on the slot, if not, you need to add the download and installation time of the software to the task execution time. Finally, calculate the total time of all pre-order task data transmission to the slot, and add it to the task execution time; finally get the total processing time of v _t on the slot. Normalize this value to get the priority value for the second rule

3) The best match between task processing time and time slot length is preferred

Definition: The matching degree of task v _t on the slot is the length of the remaining segments at both ends of the billing interval used by v _t after it is assigned to the slot divided by twice the length of the billing interval. The priority value of this rule is The specific calculation method is: 1) Obtain the set of continuous billing intervals occupied by v _t on the slot; 2) Calculate the sum of the waste at both ends of the billing interval occupied by v _t ; 3) Divide the sum of waste by two times the billing interval length, get

by putting and Integrate according to a certain weight (for example, 100:10:1) to get the final priority value of v _t on the slot.

Step s308, assign task v _t to slot _s ; remove unused VM instances in I.

Step s309, adding tasks whose predecessor tasks are scheduled to θ for updating; go to step s302.

Through the above process, the present invention realizes the dynamic supply of cloud environment resources, and minimizes the leasing cost of the total system resources under the condition of effectively ensuring the system performance. Although the embodiments of the present invention have been shown and described, those skilled in the art can understand that various changes, modifications, substitutions and modifications can be made to these embodiments without departing from the principle and spirit of the present invention. The scope of the invention is defined by the claims and their equivalents.

Claims (7)

1. A workflow application elastic resource supply method under cloud environment, it is characterized in that, the method comprises the following steps: A. Workflow deadline division: Calculate the execution time and cost of each task in the workflow on each virtual machine type, with the goal of minimizing the total rental cost of the virtual machine without violating the workflow deadline, regardless of the interval According to the constraints of billing, the workflow problem is simplified into an integer programming problem, and the virtual machine type selected by each task is solved to determine the task execution time; according to the workflow deadline, the prior relationship between tasks and the task execution time, determine each task deadline; B. Task scheduling according to priority rules: Schedule tasks in order according to the depth of tasks in the workflow from small to large. For each task, calculate the priority of all virtual machine time slots according to its deadline and based on priority rules. Assign the task to the virtual machine time slot with the highest priority, the priority rules include the least new lease time interval priority, the lowest total processing cost priority, and the best matching degree of task processing time and time slot length priority . 2. The workflow application elastic resource supply method under the cloud environment as claimed in claim 1, characterized in that, the execution time of each task on each virtual machine type in the step A includes data transmission time, virtual machine and Software preparation time. 3. The workflow application elastic resource supply method under the cloud environment as claimed in claim 1, characterized in that, in said step A, the deadline for each task is determined according to the workflow deadline, the prior relationship between tasks and the task execution time. Specific steps for this period include: S1. For each task v in the task set V, set Initialize as the sum of data transmission time, VM preparation time, software preparation time and task execution time, calculate the earliest start time EST _v , the earliest end time EFT _v and the latest end time LFT _v of each task; S2. Using the critical path generation method to iteratively generate the initial critical path CP, CP _[i] represents the i-th task of the CP; S3. Determine whether the CP is empty, if it is empty, go to step S10; otherwise, go to step S4; S4. Calculate the total time float of CP $T_{\mathrm{CP}}^{\mathrm{float}}={\mathrm{\&Sigma;}}_{{\mathrm{CP}}_{\left[k\right]\&Element;{\mathrm{CP}}^{\&prime;}}}({\mathrm{EST}}_{{\mathrm{CP}}_{[k+1]}}-{\mathrm{EFT}}_{{\mathrm{CP}}_{\left[k\right]}})+{\mathrm{LFT}}_{{\mathrm{CP}}_{\left[l\right]}}-$ Wherein, CP'=CP/V ^fix /{CP _[l] };, l is the length of CP; S5. Judgment Whether it is greater than 0, if greater than 0, go to step S6; otherwise, go to step S12; S6. Initialize i=1; S7. judge i≤l, if so, go to step S8; otherwise, go to step S11; S8. For the task CP _[C] in the CP, judge whether CP _[i] belongs to the fixed task set V ^fix , where the fixed task set V ^fix satisfies the time floating A set composed of all tasks C; if it belongs to, go to step S10; S9. Compute the allocated float of CP _[i] $T_{{\mathrm{CP}}_{\left[i\right]}}^{\mathrm{dis}}=T_{\mathrm{CP}}^{\mathrm{float}}\&times;T_{{\mathrm{CP}}_{\left[i\right]}}^{\mathrm{float}}\&times;T_{{\mathrm{CP}}_{\left[i\right]}}^{\mathrm{float}}/{\mathrm{\&Sigma;}}_{v_k\&Element;\mathrm{CP}/V}\mathrm{fix}\left\{T_{v_k}^{\mathrm{float}}\right\},$ update its time float Update the earliest start and earliest end times of its successor tasks; S10. Update i=i+1; S11. Update the latest end time and V ^fix of all tasks in V, go to step S4; S12. Generate the next critical path CP, and turn to step S3; S13. Set the task deadline for each task for 4. The workflow application elastic resource supply method under the cloud environment according to claim 1, characterized in that, in the step B, comprising: B1. Initialize the prepared task set θ as the set {v ₀ } containing only the starting tasks, and calculate The earliest start time of each task in B2. Divide θ into subsets according to the depth of each task in the prepared task set θ, select the subset θ _s with the smallest depth, sort the tasks in non-ascending order according to the execution time, and select the first task L _t is the task to be scheduled; if v _t is empty, go to step B5; B3. For the current task v _t , temporarily add an instance of the selected virtual machine type to the rented virtual machine instance set I in the cloud environment; obtain v _t according to the earliest start time and deadline of the task The set of currently available time slots B4. According to the priority rules, calculate the task v _t in The priority value on each time slot slot in , including the priority value obtained according to the least new lease time interval priority rule According to the lowest total processing cost priority rule And according to the priority rule of the best matching degree between task processing time and time slot length by putting and Integrate according to the set weight to obtain the final priority value of v _t on the slot, select the time slot slot _s with the highest priority among them, and assign the task v _t to slot _s ; remove unused VM instances in I; update The prepared task set θ, if θ is not empty, go to step B2; B5. The task matches the time slot of the virtual machine and exits. 5. The workflow application elastic resource supply method under the cloud environment according to claim 4, characterized in that, the The calculation method of is: 1) Calculate the number of billing intervals required by v _t on the slot type virtual machine, add 1 to obtain the maximum number of intervals required; 2) calculate the actual new billing intervals caused by v _t on the slot Divide the number of leased time slices by the maximum number of intervals obtained in step 1), thus obtaining 6. The workflow application elastic resource supply method under cloud environment as claimed in claim 4, characterized in that, the The calculation method is: First, according to the type of virtual machine where the slot is located, the task execution time of v _t is obtained; Then, check whether it is a newly leased virtual machine, if so, add the loading time of the virtual machine to the task execution time; if it is an existing virtual machine instance, check whether there is any software required by v _t on the slot, if not , add the software download and installation time to the task execution time; Finally, calculate the total time of all pre-order task data transmission to the slot, and add it to the task execution time to obtain the total processing time of v _t on the slot, after normalization, get 7. The workflow application elastic resource supply method under cloud environment as claimed in claim 4, characterized in that, the It is obtained by calculating the time wasted in the two periods of the task after v _t is assigned to the slot. The specific calculation method is: 1) Obtain the set of continuous billing intervals occupied by v _t on the slot; 2) Calculate v _t in the occupied billing interval 3) Divide the sum of waste by twice the length of the billing interval to get