CN116302578B - A QoS-constrained streaming application delay assurance method and system - Google Patents

Abstract

The present invention provides a QoS-constrained stream application delay guarantee method and system, which relate to the field of streaming computing technology, including: constructing a delay-constrained model by modeling the topology as a queuing network; evaluating system delay through the delay-constrained model, for The components with priority in the system are assigned executors, and the parallelism of the components in the topology task is adjusted online, and the processing delay under different QoS constraints is optimized; the communication overhead model is constructed; based on the greedy algorithm, the components after the parallelism are adjusted Task scheduling, to obtain task scheduling that minimizes communication overhead. Implemented the data monitoring module and performance optimization module of Lg‑Stream, and integrated it into Apache Storm, a typical distributed stream computing system, to conduct a comprehensive evaluation of system indicators from the perspective of system delay, throughput, resource utilization and resource usage . Compared with the existing Apache Storm framework, the proposed Lg‑Stream has a significant improvement in system performance.

Description

A QoS-constrained streaming application delay assurance method and system

technical field

The present invention relates to the technical field of streaming computing, in particular to a QoS-constrained stream application delay guarantee method and system.

Background technique

Effective use of computing resources in stream computing environments is critical to system performance. It is difficult for existing scheduling strategies to guarantee latency under QoS constraints, not to mention that scheduling itself will also bring communication costs. How to reasonably allocate resources under QoS constraints while maintaining low latency remains a challenge.

In terms of schema conversion, traditional heterogeneous database migration usually uses the ETL method, which often requires customization, and the data schema conversion strategy usually can only rely on the experience of the database administrator, requiring a lot of manpower and material resources for development and testing, and the cost is too high. High and not universal.

The development of distributed streaming computing has attracted the attention of experts and scholars at home and abroad. Various streaming computing frameworks such as Storm and Heron have emerged as the times require. They have high real-time computing capabilities and can perform various computing tasks. Storm's model is simple and has the characteristics of high fault tolerance, high reliability, high scalability, and support for multiple programming languages, making Storm a mainstream real-time streaming computing framework [Wei X, Li L, Li X, et al. Pec : Proactive elasticcollaborative resource scheduling in data stream processing[J]. IEEETransactions on Parallel and Distributed Systems, 2019, 30(7): 1628-1642]. Storm has excellent performance on the timeliness of data, and has strong fault tolerance and scalability, so it is widely used in many fields. However, Storm's technology in task allocation and resource scheduling still has flaws, and it cannot be based on real-time data. Rational allocation of tasks and use of computing resources results in a large waste of resources and system overhead. Currently, the Storm scheduling strategy is divided into three steps: component parallelism setting, assigning Executors to Workers, and assigning Workers to Worker nodes. Storm's existing scheduling strategy usually relies on the user to configure component parallelism in the task topology. The parallelism is set by the user based on their experience, which may not be ideal for the current component and may result in higher latency for tuple processing. Longer and lower throughput. At the same time, Storm's default scheduling algorithm does not consider the cost of data transmission between cluster nodes, which will also affect system performance. Therefore, reasonable scheduling is very important for Storm.

Contents of the invention

The present invention provides a QoS-constrained flow application delay guarantee method and system, which solves the problem that the existing Storm scheduling strategy usually relies on the user to configure the component parallelism in the task topology, which is not ideal for the current component and may cause tuples With higher latency and lower throughput, Storm's default scheduling algorithm does not take into account the cost of data transfer between cluster nodes.

In order to solve the above-mentioned object of the invention, the technical solution provided by the present invention is as follows: a QoS-constrained stream application delay ensuring method, characterized in that the steps include:

S1. Model the topological tasks of the system as a queuing network and build a delay constraint model;

S2. Evaluate the topology delay in the system through the delay constraint model, assign executors to the components with priority in the system, adjust the parallelism of the components in the topology task online, and optimize the processing delay of different QoS constraints;

Wherein, the different QoS constraints include: limited resources and delay constraints;

S3. Construct a communication overhead model; based on a greedy algorithm, combined with the communication overhead model, perform task scheduling on the components after adjusting the degree of parallelism, obtain task scheduling that minimizes communication overhead, and complete QoS-constrained flow application delay guarantee.

Preferably, in step S1, the topological task of the system is modeled as a queuing network, and a delay constraint model is constructed, including:

Based on the parameters of the inflow queuing network, construct a delay constraint model to evaluate the average processing delay of the entire topology;

Among them, the parameters include: the average arrival rate λ ₀ of tuples flowing into the queuing network, a single component S _i ; the average arrival rate λ _i of input tuples, the number of executors ci allocated by S _{i ;} the average processing rate of each executor µ _i ; allocate the maximum number of executors c _max ; add an executor to reduce the average processing delay of tuples L _i ;

in, , i is a positive integer variable that records subscripts, 1≤i≤N; E represents expectation; T _i represents the average processing delay of a single component S _i .

Preferably, in step S2, the topology delay in the system is evaluated through the delay constraint model, executors are assigned to components with priority in the system, the parallelism of components in the topology task is adjusted online, and the processing delay for different QoS constraints is Optimize, including:

In a scenario with limited resources, the number of executors is limited, then calculate λ ₀ , λ _i , µ _i within the statistical period, and calculate the average processing delay E[T _i ](S _i ); give priority to assigning executors to the components that have the greatest impact on the average processing delay of the entire topology input tuple until the executors are allotted. optimal allocation plan;

In the case of delay constraints, through the greedy algorithm, each time the executor is preferentially assigned to the component that has the greatest impact on the total residence time of the input tuple of the entire topology. At this time, the delay will decrease with the number of executors gradually increasing until Just satisfy the delay limit T _max , and obtain the optimal allocation scheme.

Preferably, in step S3, a communication overhead model is constructed, including:

Model the communication overhead for the topology by evaluating the amount of communication between nodes.

Preferably, in step S3, based on a greedy algorithm, task scheduling is performed on the components after adjusting the degree of parallelism to obtain task scheduling that minimizes communication overhead, including:

The tuple transmission rate E _i,j between executors communicating with each other in the collection period, the tuple transmission rate W _i, j between Workers, the CPU usage rate U _wi of Workers, and the CPU usage rate U of all Worker nodes in the cluster _ni ; Among them, j is a positive integer variable that records subtitles, 1≤j≤N, and i≠j;

Based on a greedy algorithm, combined with the communication overhead model, allocating the executors communicating with each other to the same node;

The greedy algorithm executes the optimal allocation plan every time to obtain the final allocation result, which is the optimal solution to reduce the network communication overhead between Worker nodes.

In the allocation process, increase the performance optimization threshold and the Worker node CPU utilization threshold to control the trigger frequency of the allocation plan, and obtain task scheduling that minimizes communication overhead.

Preferably, based on a greedy algorithm, in combination with the communication overhead model, the executors communicating with each other are allocated to the same node, including:

Based on the greedy algorithm, combine the communication overhead model to optimize the communication overhead between Workers, arrange E _{i, j} in descending order, and select the two executors Executor _i and Executor _j corresponding to the largest communication volume in the E _{i, j} sequence based on the greedy algorithm , put the two executors into the Worker with the least CPU utilization;

Based on the greedy algorithm, combined with the communication overhead model to optimize the communication overhead between Worker nodes, arrange W _i,j in descending order, and use the greedy algorithm to select the two Workers with the largest communication volume in the W _i,j sequence each time: Worker _i and Worker _j , put the two Workers into the Worker node with the smallest CPU utilization;

Repeat the above two optimization processes until all executors and workers are allocated.

Preferably, a performance optimization threshold is added during the allocation process to control the triggering frequency of the allocation scheme, so as to obtain task scheduling that minimizes communication overhead, including:

In the allocation process, increase the performance optimization threshold to control the trigger frequency of the allocation plan, and judge whether to perform scheduling operations. Only when the percentage of traffic improvement between nodes after scheduling reaches the performance optimization threshold or above, the scheduling operation can be performed.

Preferably, the method further includes: setting a utilization threshold for the CPU utilization of the Worker node, and if the distribution result exceeds the utilization threshold of the CPU of the Worker node, allocating the load to other Worker nodes with a small load.

On the one hand, a QoS-constrained flow application delay guarantee system is provided, and the system includes:

The scheduling module is used to build a delay constraint model by modeling the topology as a queuing network; evaluate the topology delay in the system through the delay constraint model, assign executors to components with priority in the system, and adjust components in the topology task online The degree of parallelism optimizes the processing delay of different QoS constraints;

The parallelism optimization module is used to build a communication overhead model; based on the greedy algorithm, combined with the communication overhead model, the components after adjusting the parallelism are scheduled for tasks, to obtain task scheduling that minimizes communication overhead, and to complete the QoS-constrained flow application delay guarantee .

Preferably, the scheduling module is further configured to construct a delay constraint model to evaluate the average processing delay of the entire topology based on the parameters of the inflow queuing network;

Among them, the parameters include: the average arrival rate λ ₀ of tuples flowing into the queuing network, a single component S _i ; the average arrival rate λ _i of input tuples, the number of executors ci allocated by S _{i ;} the average processing rate of each executor µ _i ; allocate the maximum number of executors c _max ; add an executor to reduce the average processing delay of tuples L _i ;

in, , i is a positive integer variable that records subscripts, 1≤i≤N; E represents expectation; T _i represents the average processing delay of a single component S _i .

In one aspect, an electronic device is provided, the electronic device includes a processor and a memory, at least one instruction is stored in the memory, and the at least one instruction is loaded and executed by the processor to realize the flow of the above-mentioned QoS constraints Applies a delay-assured method.

In one aspect, a computer-readable storage medium is provided, wherein at least one instruction is stored in the storage medium, and the at least one instruction is loaded and executed by a processor to implement the above QoS-constrained flow application delay ensuring method.

Compared with the prior art, the above-mentioned technical solution has at least the following beneficial effects:

The above scheme, the present invention realizes the data monitoring module and the performance optimization module of Lg-Stream, and integrates it into the typical distributed stream computing system Apache Storm, from the perspective of system delay, throughput, resource utilization and resource usage A comprehensive evaluation of the system indicators. Experimental results show that compared with the existing Apache Storm framework, the proposed Lg-Stream has a significant improvement in system performance. Compared with the existing Apache Storm's default scheduling strategy and online scheduling strategy, the proposed Lg-Stream system reduces delay and resource usage, and improves throughput and resource utilization.

Description of drawings

In order to more clearly illustrate the technical solutions in the embodiments of the present invention, the drawings that need to be used in the description of the embodiments will be briefly introduced below. Obviously, the drawings in the following description are only some embodiments of the present invention. For those skilled in the art, other drawings can also be obtained based on these drawings without creative effort.

FIG. 1 is a schematic flowchart of a QoS-constrained stream application delay guarantee method provided by an embodiment of the present invention;

FIG. 2 is a diagram of a parallelism elastic scaling algorithm 1 provided in an embodiment of the present invention in a scenario with limited resources;

Fig. 3 is a diagram of parallelism elastic scaling algorithm 2 in the resource limited scenario provided by the embodiment of the present invention;

Fig. 4 is a task allocation model diagram provided by an embodiment of the present invention;

Fig. 5 is a diagram of scheduling algorithm 1 for optimizing inter-Worker communication overhead provided by an embodiment of the present invention;

Fig. 6 is a diagram of the scheduling algorithm 2 for optimizing the communication overhead between Workers provided by the embodiment of the present invention

FIG. 7 is a block diagram of a QoS-constrained flow application delay guarantee system provided by an embodiment of the present invention;

Fig. 8 is a schematic structural diagram of an electronic device provided by an embodiment of the present invention.

Detailed ways

In order to make the purpose, technical solutions and advantages of the embodiments of the present invention more clear, the following will clearly and completely describe the technical solutions of the embodiments of the present invention in conjunction with the drawings of the embodiments of the present invention. Apparently, the described embodiments are some, not all, embodiments of the present invention. Based on the described embodiments of the present invention, all other embodiments obtained by persons of ordinary skill in the art without creative efforts shall fall within the protection scope of the present invention.

Aiming at the problem that the existing scheduling strategy is difficult to guarantee the delay under the QoS constraint, the present invention provides a delay-guaranteed scheduling strategy Lg-Stream under the QoS constraint.

As shown in FIG. 1 , an embodiment of the present invention provides a QoS-constrained flow application delay guarantee method, which can be implemented by electronic devices. As shown in FIG. 1 , the QoS-constrained flow application delay guarantee method flow chart, the processing flow of the method may include the following steps:

S101. Construct a delay constraint model.

In a feasible implementation, based on the parameters of the inflow queuing network, a delay constraint model is constructed to evaluate the average processing delay of the entire topology;

Among them, the parameters include: the average arrival rate λ ₀ of tuples flowing into the queuing network, a single component S _i ; the average arrival rate λ _i of input tuples, the number of executors ci allocated by S _{i ;} the average processing rate of each executor µ _i ; allocate the maximum number of executors c _max ; add an executor to reduce the average processing delay of tuples L _i ;

in, , i is a positive integer variable that records subscripts, 1≤i≤N; E represents expectation; T _i represents the average processing delay of a single component S _i .

S102. Evaluate the system delay through the delay constraint model, assign executors to the components with priority in the system, adjust the parallelism of the components in the topology task online, and optimize the processing delay under different QoS constraints; wherein, different QoS Constraints include: limited resources and delay constraints;

In a feasible implementation manner, in S102, the delay constraint model is used to evaluate the system delay, assign executors to the components with priority in the system, adjust the parallelism of the components online, and perform processing delay under different QoS constraints Optimization; wherein, different QoS constraints include: limited resources and delay constraints, including:

In a scenario where resources are _limited and the number of executors is limited, _the average processing delay E[T _{i ]} ( S _i ); Each time the executor is assigned priority to the component that has the greatest impact on the average processing delay of the entire topology input tuple, until the executor is allocated, the result of the executor allocation at this time is the average processing delay of the topology input tuple The smallest; as shown in Figure 2, it is the parallelism elastic scaling algorithm in the resource limited scenario, that is, Algorithm 1. First, initialize the number of executors ci (1≤i≤N) allocated to all components of the topology to meet the minimum operating requirements minci of each component, then sum up ci and determine whether it is greater than the maximum number of allocated executors cmax, if the minimum If the operation requirements cannot be met, no subsequent allocation will be made. Based on the idea of greedy algorithm, under the condition that the total number of components assigned to the topology does not exceed cmax, the Executor is assigned to maxS each time, so that the total processing time of the overall tuple is minimized, and the above steps are executed until the Executor is allocated, and the parallelism allocation plan is output . Among them, maxS is the component that has the greatest impact on the average processing delay of the entire topology input tuple after adding an Executor.

In the case of delay constraints, through the greedy algorithm, each time the executor is preferentially assigned to the component that has the greatest impact on the total residence time of the entire topology input tuple. At this time, the delay will decrease with the number of executors gradually increasing until just Satisfy the delay limit T _max . At this time, the Executor allocation result of the executor is to minimize the number of Executors under the condition that the delay limit is just met, saving the computing resources of the system.

In a feasible implementation manner, another parallelism elastic scaling algorithm in a delay-constrained scenario is shown in Algorithm 2 in FIG. 3 .

S103. Construct a communication overhead model; based on a greedy algorithm, perform task scheduling on the components after adjusting the degree of parallelism, and obtain task scheduling that minimizes communication overhead.

In a feasible implementation manner, in S103, building a communication overhead model includes:

Model the communication overhead for the topology by evaluating the amount of communication between nodes.

In a feasible implementation, as shown in Figure 4, there are the following three different task communication modes in the Storm cluster:

(1) Communication between Executors. Two Executors communicate in the same Worker in the same Worker node, such as the communication between E4 and E7 is the communication between Executors.

(2) Communication among workers. When two Executors communicate in different Workers in the same Worker node, they need to go through two routes, and the communication overhead is larger than that between Executors. For example, the communication between E1 and E3 is between Workers.

(3) Communication between Worker nodes. Two Executors communicate in different Worker nodes, which need to occupy network bandwidth resources between Worker nodes, and the communication overhead is the largest. For example, between E1 and E4 is the communication between Worker nodes.

Therefore, reducing the communication between Worker nodes and Workers in the topology is beneficial to improve the overall system performance. In order to minimize the overall communication overhead of the topology, it is necessary to convert the communication between Worker nodes and Workers into communication between Executors as much as possible.

Define R _j,k as the data flow size between two communicating Executor j and Executor k, E is the set of Executors, D ₁ is the Worker where the Executor is located, and D ₂ is the Worker node where the Worker is located, such as Executor i The Worker where D ₁ (E _i ) is located can be expressed as D ₁ (E _i ), and the Worker node where D 1 (E i ) is located can be expressed as D ₂ (D ₁ (E _i )). After the topology is submitted, the entire The total amount of data flow in the topology is a fixed value, which satisfies:

, so when the total amount of data flow between Worker nodes /> The total amount of data flow between and Worker At the minimum, the total amount of data flow between Executors is the largest, which can be expressed as , using CT _m,n to represent the communication overhead between Worker node m and Worker node n, it can be expressed as formula (1), where B _m,n is the network bandwidth between m and n, if two Executors are in the same On the Worker node, the communication overhead between them is considered negligible:

(1)

Among them, j is a positive integer variable that records subtitles, 1≤j≤N, and i≠j;

Because system overhead will affect system performance during the execution of resource scheduling, we add a performance optimization threshold to determine whether to perform resource adjustment according to the calculated scheduling scheme. Let the traffic between nodes before scheduling be Traffic _old , the traffic between nodes after scheduling is Traffic _new , let Traffic _change be the traffic improvement percentage between nodes after scheduling, expressed as formula (2), Traffic _improve is set by the user, only if Traffic _change is at least The scheduling operation is performed only when Traffic _improve is reached.

(2)

Pay attention to the Worker node overload problem during the scheduling process. Once the Worker node is overloaded, the average job processing time will skyrocket, tuples will start to fail, and tuples will start to queue until they eventually time out. Therefore, it is necessary to set a threshold for the CPU utilization of the Worker node. If the allocation result exceeds the CPU utilization threshold of the Worker node, the load will be allocated to other Worker nodes with a small load.

The Worker node of the Storm cluster is represented by N={n ₁ ,n ₂ ,...,n _N }, the available CPU resources of the Worker node are represented by C={c _n1 ,c _n2 ,...,c _nN }, and u is The maximum CPU utilization allowed by Worker node, c _Ej is the CPU resources occupied by Executor j running on Worker node, then for any n _s ∈ N, the threads running on it must satisfy .

In a feasible implementation manner, in S103, based on a greedy algorithm, task scheduling is performed on the components after adjusting the degree of parallelism to obtain task scheduling that minimizes communication overhead, including:

The tuple transmission rate E _{i, j between executors communicating with each other within the collection period T,} the tuple transmission rate W _i, j between Workers, the CPU usage rate U _wi of Workers, and the CPU usage rate of all Worker nodes in the cluster U _ni ;

Based on the greedy algorithm, the executors that communicate with each other are assigned to the same node;

The greedy algorithm executes the optimal solution every time, and the final allocation result is also the optimal solution to reduce the network communication overhead between Worker nodes.

Increase the performance optimization threshold to control its trigger frequency in the allocation process, and obtain the task scheduling that minimizes the communication overhead.

In a feasible implementation manner, as shown in FIG. 5 , it is a scheduling algorithm 1 for optimizing communication overhead between Workers. Based on the greedy algorithm, the executors that communicate with each other are assigned to the same node, including:

Optimize the communication overhead between Workers, arrange E _{i, j} in descending order, select E _{i, j} sequence based on the greedy algorithm, and select the two executors Executor _i and Executor _j with the largest communication volume in the sequence, and put them into the central processing unit (Central Processing Unit, CPU) to the Worker with the smallest utilization;

Optimize the communication overhead between Worker nodes. Similar to the algorithm in the first stage, W _{i, j} are sorted in descending order, and the greedy algorithm is used to select the two workers with the largest communication volume in the W _{i, j} sequence each time: Worker _i and Worker _j , put it into the Worker node with the smallest CPU utilization;

Repeat the above two optimization processes until all executors and workers are allocated.

In an embodiment of the present invention, as shown in FIG. 6 , a scheduling algorithm 2 for optimizing communication overhead between Worker nodes is shown.

In a feasible implementation manner, a performance optimization threshold is added in the allocation process to control its triggering frequency, so as to obtain task scheduling that minimizes communication overhead.

In a feasible implementation, attention needs to be paid to the worker node overload problem during the allocation process. Once the worker node is overloaded, the average job processing time will skyrocket, tuples will start to fail, and tuples will start to queue until they eventually time out. Therefore, it is necessary to set a threshold for the CPU utilization of the Worker node. If the allocation result exceeds the CPU utilization threshold of the Worker node, the load will be allocated to other Worker nodes with a small load. During the task scheduling process, there will be costs that affect system performance. This application adds a performance optimization threshold to determine whether to adjust tasks according to the calculated scheduling scheme. Scheduling can only be performed when the scheduling effect reaches the set performance optimization threshold or above.

In the embodiment of the present invention, the present invention proposes a delay-guaranteed scheduling strategy under QoS constraints, which is called Lg-Stream. The Lg-Stream strategy is discussed from the following aspects: (1) Modeling the topology as a queuing network, constructing a delay-constrained model to evaluate the system delay, and constructing a communication overhead model to calculate the communication overhead (2) For limited resources and delay constraints scenario, we ensure that the allocation of each executor to a component maximizes the processing latency of the system, thus varying the parallelism of the components (3) based on the greediness of placing as many communicating executors on the same node as possible Algorithm idea, reduce communication overhead through scheduling, and increase performance optimization threshold to control its trigger frequency.

The present invention realizes the data monitoring module and the performance optimization module of Lg-Stream, and integrates it into Apache Storm, a typical distributed stream computing system, and conducts system indicators from the perspectives of system delay, throughput, resource utilization and resource usage Comprehensive assessment. Experimental results show that compared with the existing Apache Storm framework, the proposed Lg-Stream has a significant improvement in system performance. Compared with the existing default scheduling strategy and online scheduling strategy of Apache Storm, the proposed Lg-Stream (latency guaranteed Stream) system reduces delay and resource usage, and improves throughput and resource utilization.

FIG. 7 is a schematic diagram of a QoS-constrained stream application delay guarantee system according to the present invention, and the system 200 includes:

The scheduling module 210 is used to model the topological tasks of the system as a queuing network and build a delay constraint model; evaluate the topology delay in the system through the delay constraint model, and assign executors to components with priority in the system; adjust the topology online The parallelism of the components in the task optimizes the processing delay of different QoS constraints;

The parallelism optimization module 220 is used to build a communication overhead model; based on a greedy algorithm, perform task scheduling on the components after adjusting the parallelism, obtain task scheduling that minimizes communication overhead, and complete QoS-constrained flow application delay guarantee.

Preferably, the scheduling module 210 is further configured to construct a delay constraint model to evaluate the average processing delay of the entire topology based on the parameters of the inflow queuing network;

Among them, the parameters include: the average arrival rate λ ₀ of tuples flowing into the queuing network, a single component S _i ; the average arrival rate λ _i of input tuples, the number of executors ci allocated by S _{i ;} the average processing rate of each executor µ _i ; allocate the maximum number of executors c _max ; add an executor to reduce the average processing delay of tuples L _i ;

in, , i is a positive integer variable that records subscripts, 1≤i≤N; E represents expectation; T _i represents the average processing delay of a single component S _i .

Preferably, the scheduling module 210 is further used to calculate λ ₀ , λ _i , µ _i in the statistical period of the cycle T in a scenario with limited resources and a limited number of executors, and calculate the input elements of all components through the delay constraint model The average processing delay E[T _i ](S _i ) of the group; the priority allocation of executors has the greatest influence on the average processing delay of the input tuples of the entire topology until the executors are allocated, and the result of the executor allocation is that the topology The result of the minimum average processing delay of the input tuples is obtained to obtain the optimal allocation scheme;

In the case of delay constraints, through the greedy algorithm, each time the executor is preferentially assigned to the component that has the greatest impact on the total residence time of the input tuple of the entire topology. At this time, the delay will decrease with the number of executors gradually increasing until Just satisfy the delay limit T _max , and obtain the optimal allocation scheme.

Preferably, the parallelism optimization module 220 is further configured to construct a communication overhead model for the topology by evaluating communication traffic between nodes.

Preferably, the parallelism optimization module 220 is further used to collect the tuple transmission rate E _i,j between the executors communicating with each other in the period T, the tuple transmission rate W _i,j between the Workers, and the CPU usage of the Worker rate U _wi , the CPU usage rate U _ni of all Worker nodes in the cluster;

Based on a greedy algorithm, combined with the communication overhead model, allocating the executors communicating with each other to the same node;

The greedy algorithm executes the optimal allocation scheme each time to obtain the final allocation result, which is an optimal solution for reducing network communication overhead between Worker nodes.

In the allocation process, a performance optimization threshold is added to control the trigger frequency of the allocation scheme, and task scheduling with minimum communication overhead is obtained.

Increase the performance optimization threshold to control its trigger frequency in the allocation process, and obtain the task scheduling that minimizes the communication overhead.

Preferably, based on the greedy algorithm, the executors communicating with each other are assigned to the same node, including:

Based on the greedy algorithm, combine the communication overhead model to optimize the communication overhead between Workers, arrange E _{i, j} in descending order, and select the two executors Executor _i and Executor _j corresponding to the largest communication volume in the E _{i, j} sequence based on the greedy algorithm , put the two executors into the Worker with the least CPU utilization;

Based on the greedy algorithm, combined with the communication overhead model to optimize the communication overhead between Worker nodes, arrange W _i,j in descending order, and use the greedy algorithm to select the two Workers with the largest communication volume in the W _i,j sequence each time: Worker _i and Worker, put the two Workers into the Worker node with the smallest CPU utilization;

Repeat the above two optimization processes until all executors and workers are allocated.

Preferably, a performance optimization threshold is added during the allocation process to control the triggering frequency of the allocation scheme, so as to obtain task scheduling that minimizes communication overhead, including:

In the allocation process, increase the performance optimization threshold to control the trigger frequency of the allocation plan, and judge whether to perform scheduling operations. Only when the percentage of traffic improvement between nodes after scheduling reaches the performance optimization threshold or above, the scheduling operation can be performed.

Preferably, the method further includes: setting a utilization threshold for the CPU utilization of the Worker node, and if the distribution result exceeds the utilization threshold of the CPU of the Worker node, allocating the load to other Worker nodes with a small load.

Preferably, it also includes:

A data monitoring module 230, configured to collect load information and the size of the data flow between the actuators;

The storage module 240 is used to store the assignment information of each task and the load information collected by the data monitoring module Data Monitor and the size of the data flow between the executors and keep it updated.

In the embodiment of the present invention, the present invention proposes a delay-guaranteed scheduling strategy under QoS constraints, which is called Lg-Stream. The Lg-Stream strategy is discussed from the following aspects: (1) Modeling the topology as a queuing network, constructing a delay-constrained model to evaluate the system delay, and constructing a communication overhead model to calculate the communication overhead (2) For limited resources and delay constraints scenario, we ensure that the allocation of each executor to a component maximizes the processing latency of the system, thus varying the parallelism of the components (3) based on the greediness of placing as many communicating executors on the same node as possible Algorithm idea, reduce communication overhead through scheduling, and increase performance optimization threshold to control its trigger frequency.

The present invention realizes the data monitoring module and the performance optimization module of Lg-Stream, and integrates it into Apache Storm, a typical distributed stream computing system, and conducts system indicators from the perspectives of system delay, throughput, resource utilization and resource usage Comprehensive assessment. Experimental results show that compared with the existing Apache Storm framework, the proposed Lg-Stream has a significant improvement in system performance. Compared with the existing Apache Storm's default scheduling strategy and online scheduling strategy, the proposed Lg-Stream system reduces delay and resource usage, and improves throughput and resource utilization.

FIG. 8 is a schematic structural diagram of an electronic device 300 provided by an embodiment of the present invention. The electronic device 300 may have relatively large differences due to different configurations or performances, and may include one or more central processing units (CPU) 301 and one or more memories 302, wherein at least one instruction is stored in the memory 302, and the at least one instruction is loaded and executed by the processor 301 to implement the steps of the following QoS-constrained flow application delay ensuring method :

S1. Construct a delay constraint model by modeling the topology as a queuing network;

S2. Evaluate the system delay through the delay constraint model, assign executors to the components with priority in the system, adjust the parallelism of the components in the topology task online, and optimize the processing delay under different QoS constraints; among them, different QoS Constraints include: limited resources and delay constraints;

S3. Construct a communication overhead model; based on a greedy algorithm, perform task scheduling on the components after adjusting the degree of parallelism, and obtain task scheduling that minimizes communication overhead.

In an exemplary embodiment, there is also provided a computer-readable storage medium, such as a memory including instructions, which can be executed by a processor in a terminal to implement the above QoS-constrained stream application delay ensuring method. For example, the computer readable storage medium may be ROM, random access memory (RAM), CD-ROM, magnetic tape, floppy disk, optical data storage device, and the like.

Those of ordinary skill in the art can understand that all or part of the steps for implementing the above embodiments can be completed by hardware, and can also be completed by instructing related hardware through a program. The program can be stored in a computer-readable storage medium. The above-mentioned The storage medium mentioned may be a read-only memory, a magnetic disk or an optical disk, and the like.

Claims (7)

1. A stream application delay guarantee method of QoS constraints, characterized in that the method steps include: S1. Model the topological tasks of the system as a queuing network and build a delay constraint model; In the step S1, the topological task of the system is modeled as a queuing network, and a delay constraint model is constructed, including: Based on the parameters of the inflow queuing network, construct a delay constraint model to evaluate the average processing delay of the entire topology; Among them, the parameters include: the average arrival rate λ ₀ of tuples flowing into the queuing network, a single component S _i ; the average arrival rate λ _i of input tuples, the number of executors ci assigned by S _{i ;} the average processing rate µ _i ; assign the maximum number of executors c _max ; add an executor to reduce the average tuple processing delay L _i ; in, , i is a positive integer variable that records subscripts, 1≤i≤N , N is a positive integer greater than 1; E represents expectation; T _i represents the average processing delay of a single component S _i ; S2. Evaluate the topology delay in the system through the delay constraint model, and assign executors to the components with priority in the system; adjust the parallelism of the components in the topology task online, and optimize the processing delay of different QoS constraints; Wherein, the different QoS constraints include: limited resources and delay constraints; In the step S2, the topological delay in the system is evaluated through the delay constraint model, and executors are assigned to the components with priority in the system; the parallelism of the components in the topology task is adjusted online, and the processing of different QoS constraints Latency is optimized, including: In a scenario with limited resources, the number of executors is limited, then calculate λ ₀ , λ _i , µ _i within the statistical period, and calculate the average processing delay E[T _i ](S _i ); give priority to assigning executors to the components that have the greatest impact on the average processing delay of the entire topology input tuple until the executors are allotted. optimal allocation plan; In the case of delay constraints, through the greedy algorithm, each time the executor is preferentially assigned to the component that has the greatest impact on the total residence time of the input tuple of the entire topology. At this time, the delay will decrease with the number of executors gradually increasing until It just satisfies the delay limit T _max and obtains the optimal allocation scheme; S3. Construct a communication overhead model; based on a greedy algorithm, combined with the communication overhead model, perform task scheduling on the components after adjusting the degree of parallelism, obtain task scheduling that minimizes communication overhead, and complete QoS-constrained flow application delay guarantee. 2. The method according to claim 1, wherein, in the step S3, building a communication overhead model includes: Model the communication overhead for the topology by evaluating the amount of communication between nodes. 3. The method according to claim 2, characterized in that, in the step S3, based on the greedy algorithm, combined with the communication overhead model, the components after adjusting the degree of parallelism are task-scheduled to obtain task scheduling that minimizes the communication overhead ,include: The tuple transmission rate E _i,j between executors communicating with each other in the collection period, the tuple transmission rate W _i,j between workers, the CPU usage rate U _wi of Workers, and the CPU usage of all Worker nodes in the cluster Rate U _ni ; Among them, j is a positive integer variable that records subscripts, 1≤ j ≤ N, and i ≠ j ; Based on a greedy algorithm, combined with the communication overhead model, allocating the executors communicating with each other to the same node; The greedy algorithm executes the optimal allocation scheme every time to obtain the final allocation result, which is the optimal solution for reducing the network communication overhead between the Worker nodes; In the allocation process, a performance optimization threshold is added to control the trigger frequency of the allocation scheme, and task scheduling with minimum communication overhead is obtained. 4. The method according to claim 3, wherein the greedy algorithm, in combination with the communication overhead model, assigns the executors communicating with each other to the same node, comprising: Based on the greedy algorithm, combine the communication overhead model to optimize the communication overhead between Workers, arrange E _{i, j} in descending order, and select the two executors Executor _i and Executor _j corresponding to the largest communication volume in the E _{i, j} sequence based on the greedy algorithm , put the two executors into the Worker with the least CPU utilization; Based on the greedy algorithm, combined with the communication overhead model to optimize the communication overhead between Worker nodes, arrange W _i,j in descending order, and use the greedy algorithm to select the two Workers with the largest corresponding traffic in the W _i,j sequence each time: Worker _i and Worker _j , put the two Workers into the Worker node with the smallest CPU utilization; Repeat the above two optimization processes until all executors and workers are allocated. 5. The method according to claim 4, characterized in that, increasing the trigger frequency of the performance optimization threshold control allocation scheme in the allocation process, and obtaining task scheduling that minimizes communication overhead, including: In the allocation process, increase the performance optimization threshold to control the trigger frequency of the allocation plan, and judge whether to perform scheduling operations. Only when the percentage of traffic improvement between nodes after scheduling reaches the performance optimization threshold or above, the scheduling operation can be performed. 6. The method according to claim 5, further comprising: setting a utilization threshold for the Worker node CPU utilization, if the allocation result exceeds the utilization threshold of the Worker node CPU, then the load is distributed to other Worker node with light load. 7. A QoS-constrained flow application delay guarantee system, characterized in that the system comprises: The scheduling module is used to model the topological tasks of the system as a queuing network and build a delay constraint model; evaluate the system delay through the delay constraint model, assign executors to components with priority in the system, and adjust the components in the topological task online Parallelism, optimize the processing delay under different QoS constraints; among them, different QoS constraints include: limited resources and delay constraints; The scheduling module is configured to construct a delay constraint model to evaluate the average processing delay of the entire topology based on the parameters of the inflow queuing network; Among them, the parameters include: the average arrival rate λ ₀ of tuples flowing into the queuing network, a single component S _i ; the average arrival rate λ _i of input tuples, the number of executors ci allocated by S _{i ;} the average processing rate of each executor µ _i ; allocate the maximum number of executors c _max ; add an executor to reduce the average processing delay of tuples L _i ; in, , i is a positive integer variable that records subscripts, 1≤ i ≤ N; E represents expectation; T _i represents the average processing delay of a single component S _i ; The parallelism optimization module is used to build a communication overhead model; based on the greedy algorithm, combined with the communication overhead model, the components after adjusting the parallelism are scheduled for tasks, to obtain task scheduling that minimizes communication overhead, and to complete the QoS-constrained flow application delay guarantee ; The scheduling module is used to calculate λ ₀ , λ _i , µ _i in the statistical period of period T in a scenario with limited resources and a limited number of executors, and calculate the average processing delay of input tuples of all components through the delay constraint model E [ T _i ]( S _i ); Prioritize the allocation of executors to the components that have the greatest impact on the average processing delay of the entire topology input tuple until the executors are allocated, and the result of the executor allocation is to make the average of the topology input tuples Process the result with the least delay to obtain the optimal allocation plan; In the case of delay constraints, through the greedy algorithm, each time the executor is preferentially assigned to the component that has the greatest impact on the total residence time of the input tuple of the entire topology. At this time, the delay will decrease with the number of executors gradually increasing until Just satisfy the delay limit T _max , and obtain the optimal allocation scheme.