CN116302404B - Resource decoupling data center-oriented server non-perception calculation scheduling method - Google Patents

Abstract

The embodiment of the invention provides a server non-aware computing scheduling method for a resource decoupling data center. Applied to a scheduler, the method comprises: determining a corresponding task type according to the received task request RPC; determining the allocation proportion corresponding to the task type according to the task type; and distributing the tasks in the task types to a computing node or a storage node for execution according to the distribution proportion with corresponding probabilities. The method aims at distributing various tasks to nodes matched with the self-running characteristics for execution, so that the task execution efficiency and the resource utilization rate of the system are improved, and the throughput of the system is further improved.

Description

Server-less computing scheduling method for resource decoupling data center

Technical field

The present invention relates to the field of data center scheduling technology, and in particular to a server-less computing scheduling method oriented to resource decoupling data centers.

Background technique

Server-less computing is a new generation of cloud computing paradigm that allows developers to develop applications based on server-less functions without paying attention to the details of underlying resource management. Server-less computing uses a resource decoupling architecture to decouple computing and storage into two independent resource pools. Server nodes in the computing resource pool obtain data from the storage resource pool through the network and complete calculations. Since the two resource pools are independent of each other, the resource decoupling architecture has good scalability and high resource utilization.

However, the network overhead caused by remote access to data cannot be ignored. For IO-intensive tasks (IO stands for data input/output), moving data from storage nodes to computing nodes may require multiple RTTs (Round-Trip Time network round trip time) or occupy a lot of bandwidth. Although this problem is solved through storage-side computing - using RPC (Remote Procedure Call) to run the stored procedures registered on the storage node. However, because the storage resource pool is specialized in storage, its computing resources are often limited and cannot meet the computing needs of all tasks. Existing technology schedules workloads to storage and computing nodes for execution according to a certain allocation ratio, so that both resource pools are fully utilized. The limitation of the existing technology is that it only makes scheduling decisions at the load level, that is, it only calculates a unified allocation ratio for the overall load. This scheduling method does not consider the attributes of the task itself, resulting in poor scheduling results and inefficient system operation.

Contents of the invention

In view of this, embodiments of the present invention provide a server-insensitive computing scheduling method for resource decoupling data centers. It aims to allocate various types of tasks to nodes that match their own runtime characteristics for execution, thereby improving task execution efficiency and system resource utilization, thereby improving system throughput.

The first aspect of the embodiment of the present invention provides a server-less computing scheduling method for resource decoupling data centers, which is applied to the scheduler. The method includes:

Determine the corresponding task type based on the received task request RPC;

According to the task type, determine the allocation ratio corresponding to the task type;

According to the allocation ratio, tasks in the task type are allocated to computing nodes or storage nodes for execution with corresponding probabilities.

Optionally, determining an allocation ratio corresponding to the task type according to the task type includes:

When the task type is an unprocessed first task type, determine the allocation ratio corresponding to the first task type to be the default allocation ratio;

Allocating tasks in the task type to computing nodes or storage nodes for execution with corresponding probabilities according to the allocation ratio includes:

Allocate the tasks of the first task type to computing nodes or storage nodes for execution according to the default allocation ratio, and calculate the execution costs of a preset number of tasks of the first task type on the computing nodes and storage nodes. , and then determine the runtime characteristics of the first task type;

Determine the optimal allocation ratio of the first task type by inputting the runtime characteristics into a preset scheduling algorithm for calculation;

According to the optimal allocation ratio of the first task type, allocate tasks in the first task type to computing nodes or storage nodes for execution with corresponding probabilities;

When the task type is a processed second task type, obtain the optimal allocation ratio corresponding to the second task type determined by the preset scheduling algorithm;

Allocating tasks in the task type to computing nodes or storage nodes for execution with corresponding probabilities according to the allocation ratio includes:

According to the optimal allocation ratio corresponding to the second task type, tasks in the second task type are allocated to computing nodes or storage nodes for execution with corresponding probabilities.

Optionally, the runtime characteristics include: network overhead of data transmission when the computing node performs the task, and CPU overhead when the storage node performs the task.

Optionally, determining the optimal allocation ratio of the first task type by inputting the runtime characteristics into a preset scheduling algorithm for calculation includes:

Determine the relative cost of the first task type by inputting the runtime characteristics into a preset scheduling algorithm;

Sorting the first task type and the second task type according to the relative cost;

Determine the optimal solution of the split point parameters through the sub-algorithm in the preset scheduling algorithm;

According to the sorting result and the optimal solution of the split point parameters, the optimal allocation ratio of the first task type is determined.

Optionally, the method also includes:

According to the end-to-end delay during task execution and the service level target given by the user, the throughput of the system is adjusted through the current limiter;

According to the throughput of the system, the split point parameters of the scheduler are adjusted to maximize the throughput of the system.

Optionally, the method also includes:

Determine the difference between the runtime characteristics of each task type in the current time window and its own historical runtime characteristics sliding average;

Set the allocation proportion of the third task type whose difference between the runtime characteristics in the current time window and its own historical runtime characteristics sliding average exceeds the first threshold as the default allocation proportion;

Allocate the third task type to the computing nodes or storage nodes for execution according to the default allocation ratio, and calculate the new execution costs of the preset number of tasks of the third task type on the computing nodes and storage nodes, and then determine new runtime features;

Determine the relative cost of the third task type by inputting the new runtime characteristics into a preset scheduling algorithm;

Sort all task types according to their relative cost;

Determine the optimal solution of the split point parameters through the sub-algorithm in the preset scheduling algorithm;

Based on the ranking results of all task types and the optimal solution of the split point parameters, the optimal allocation ratio of all task types is determined.

Optionally, the method also includes:

Determine the request dropping status of the current limiter;

When the current limiter discards requests, increase the capacity of the computing resource pool in a stepwise manner until the current limiter no longer discards requests;

When the current limiter does not discard requests, the number of computing nodes is reduced in a stepwise manner according to the load of the system.

Optionally, the method also includes:

Determine the actual load of each storage node;

When the difference between the actual load of the storage node and the average load of the system exceeds the second threshold, the storage node is divided into a new independent scheduling policy group;

Divide a preset number of computing nodes into the new independent scheduling policy group;

Each policy group operates independently as a subsystem for task scheduling and execution.

Embodiments of the present invention include the following advantages:

The embodiment of the present invention provides a server-less computing scheduling method for resource decoupling data centers. The task type of the task is determined according to the received task request RPC, and the allocation ratio corresponding to the task type is determined based on the task type (for example, for intensive computing) For IO-intensive tasks, all or most of them are allocated to computing nodes with sufficient computing resources for execution, and the rest are allocated to storage nodes for execution; for IO-intensive tasks, all or most of them are allocated to storage nodes with higher IO efficiency. execution, and the remaining small part is allocated to computing nodes for execution), according to the determined allocation ratio, tasks in this task type are allocated to computing nodes or storage nodes for execution with a probability equal to the allocation ratio. The present invention determines the allocation ratio corresponding to the task type according to the task type, and allocates the tasks in the task type to the computing node or the storage node for execution with a probability equal to the allocation ratio, so that the tasks in the task type can It is executed on nodes that match its own runtime characteristics, thereby improving task execution efficiency and system resource utilization, thereby improving system throughput.

Description of the drawings

In order to explain the technical solutions of the embodiments of the present invention more clearly, the drawings needed to be used in the description of the embodiments of the present invention will be briefly introduced below. Obviously, the drawings in the following description are only some embodiments of the present invention. , for those of ordinary skill in the art, other drawings can also be obtained based on these drawings without exerting creative labor.

Figure 1 is a flow chart of a server-less computing scheduling method for a resource decoupling data center oriented to an embodiment of the present invention;

FIG. 2 is a system module diagram illustrating a server-insensitive computing scheduling method for a resource decoupling data center oriented according to an embodiment of the present invention.

Detailed ways

The technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the accompanying drawings in the embodiments of the present invention. Obviously, the described embodiments are part of the embodiments of the present invention, not all of them. Based on the embodiments of the present invention, all other embodiments obtained by those of ordinary skill in the art without making creative efforts fall within the scope of protection of the present invention.

Before describing the present invention, the background of the present invention will be described first. In actual application scenarios, not distinguishing task types and only performing unified scheduling at the overall workload (a collection of all tasks) level will lead to low scheduling accuracy and inefficient system operation. The present invention finds that in actual application scenarios, the types of tasks executed by the system are diverse, and tasks of different task types have different runtime characteristics. The tasks are assigned to nodes that match their runtime characteristics for execution (such as computing-intensive tasks). Place IO-intensive tasks on computing nodes with sufficient computing power for execution, and place IO-intensive tasks on storage nodes with higher IO efficiency for execution to avoid multiple RTTs and large-scale data transmission), which can give full play to the respective advantages of each node, thereby improving Task execution efficiency and system resource utilization, thereby improving the system’s task throughput.

In the present invention, FIG. 1 is a flow chart of a server-less computing scheduling method oriented to a resource decoupling data center according to an embodiment of the present invention. Referring to Figure 1, the present invention provides a server-less computing scheduling method for resource decoupling data centers, which is applied to the scheduler and includes:

Step S11: Determine the corresponding task type according to the received task request RPC;

Step S12: According to the task type, determine the allocation ratio corresponding to the task type;

Step S13: According to the allocation ratio, allocate tasks in the task type to computing nodes or storage nodes for execution with corresponding probabilities.

In the embodiment of the present invention, the user submits the pre-written application code to the system, which is compiled by the system and stored in the computing node and the storage node, where a specific program corresponds to a task type. The user then submits the task call request to the scheduler in RPC. The scheduler is responsible for scheduling tasks to computing nodes or storage nodes for execution. After receiving the task request RPC, the scheduler identifies the corresponding task type by parsing the task request RPC, and then determines the corresponding allocation ratio according to the task type, and according to The current task request is scheduled to the storage node with a probability equal to the allocation ratio of the task type. Specifically, if the allocation ratio of this task type is 60%, then the task has a 60% probability of being scheduled to the storage node and a 40% probability of being scheduled to the computing node. In the present invention, the allocation ratio represents the probability of a task being scheduled to a storage node. In an actual scenario, whether the allocation ratio represents the probability of a task being scheduled to a storage node or a computing node can be freely selected. Macroscopically, according to the law of large numbers, the ratio between the number of tasks executed on computing nodes and storage nodes for a task type will converge to the allocation ratio corresponding to the task type. Continuing with the above example, if the user submits a total of 10,000 tasks belonging to this task type, approximately 6,000 of them will be executed on the storage node (accounting for approximately 60%), and approximately 4,000 of them will be executed on the computing node (accounting for approximately 40%). Therefore, the present invention refers to the ratio of 60% as the distribution ratio.

The scheduler jointly calculates the allocation ratio of each task type based on all task types submitted within the current preset time period. This process is performed asynchronously in the background of the scheduler, that is, the scheduler calculates the task type allocation ratio without affecting the scheduler's allocation ratio. Scheduling work for the current task. When the actual task request RPC arrives, the scheduler identifies the corresponding task type and schedules the task to the computing or storage node for execution according to the allocation ratio corresponding to the task type.

The allocation ratio corresponding to each task type is calculated by a preset scheduling algorithm in the scheduler, and its specific implementation will be described in subsequent embodiments.

The embodiment of the present invention provides a server-less computing scheduling method for resource decoupling data centers. The task type to which the task belongs is determined according to the received task request RPC, and the corresponding allocation proportion is determined according to the task type. According to the determined allocation Proportion, allocate tasks belonging to this task type to computing nodes or storage nodes for execution with corresponding probabilities. The present invention sets allocation ratios for different task types separately for scheduling, so that each type of task can be executed on a node that matches its own runtime characteristics (for example, for computing-intensive tasks, all or most of them are allocated to a node with sufficient computing resources. computing nodes for execution, and the rest is allocated to storage nodes for execution; for IO-intensive tasks, all or most of them are allocated to storage nodes with higher IO efficiency for execution, and the remaining small part is allocated to computing nodes for execution) This improves task execution efficiency and system resource utilization, thereby improving the system's task throughput.

In the present invention, determining the allocation ratio corresponding to the task type according to the task type includes: when the task type is an unprocessed first task type, determining the allocation ratio corresponding to the first task type. is the default allocation ratio; allocating tasks in the task type to computing nodes or storage nodes with corresponding probabilities according to the allocation ratio includes: allocating tasks of the first task type to the default Allocate proportions to computing nodes or storage nodes for execution, and count the execution costs of a preset number of tasks in the first task type on the computing nodes and storage nodes, thereby determining the runtime characteristics of the first task type. ; Determine the optimal allocation ratio of the first task type by inputting the runtime characteristics into the preset scheduling algorithm for calculation; according to the optimal allocation ratio of the first task type, divide the first task type into The tasks are assigned to the computing nodes or storage nodes for execution with corresponding probabilities; when the task type is the processed second task type, the optimal allocation ratio corresponding to the second task type determined by the preset scheduling algorithm is obtained; Allocating tasks in the task type to computing nodes or storage nodes for execution with corresponding probabilities according to the allocation ratio includes: according to the optimal allocation ratio corresponding to the second task type, allocating the first task type to the computing node or the storage node for execution. Tasks in the second task type are assigned to computing nodes or storage nodes for execution with corresponding probabilities.

In an embodiment of the present invention, according to the task type, one implementation method of determining the allocation ratio corresponding to the task type is: when the task type corresponding to the received task request is the first task type that has not been processed by the system, For the first task type, the tasks are allocated to computing nodes or storage nodes in a default allocation ratio for task execution.

In the embodiment of the present invention, the default allocation ratio is preferably 50%. It should be understood that the default allocation ratio can also be other allocation ratios, which are not specifically limited here. The purpose of allocating unprocessed tasks of the first task type to computing nodes or storage nodes for task execution at a default allocation ratio is to obtain the performance of tasks of the first task type when they are executed on computing nodes and storage nodes. Runtime characteristics, so as to calculate the optimal allocation ratio corresponding to the first task type based on the runtime characteristics.

When the number of tasks of the first task type assigned to the computing node reaches a preset number, the execution cost of the preset number of first task types on the computing node is counted; when the number of tasks of the first task type assigned to the storage node reaches a When the number is preset, the execution cost of the preset number of first task types on the storage node is counted; both of them together constitute the runtime characteristics of the first task type. Among them, the value of the preset quantity can be set according to the actual application scenario, and is not specifically limited here.

In the embodiment of the present invention, after both the computing node and the storage node have counted the runtime characteristics of the first task type; by inputting the two obtained runtime characteristics into the preset scheduling algorithm for calculation, the first task type is obtained the optimal allocation ratio. Then according to the optimal allocation ratio, tasks belonging to the first task type are allocated to computing nodes or storage nodes for execution with corresponding probabilities.

In the embodiment of the present invention, when the task type is the second task type processed by the system, it means that the scheduler has previously obtained the runtime characteristics of the second task type when it is executed by the computing node and the storage node, and Based on the runtime characteristics, the optimal allocation ratio corresponding to the second task type is calculated through the preset scheduling algorithm. At this time, it is only necessary to allocate the tasks of the second task type to the corresponding probability according to the optimal allocation ratio. Compute node or storage node for execution.

In the present invention, the runtime characteristics include: network overhead of data transmission when the computing node performs the task, and CPU overhead when the storage node performs the task.

In the embodiment of the present invention, the runtime characteristics of a type of task refer to a tuple ( _ci , si ₎ , where the subscript i is the number of the task type, and c _i is the i-th task type in the calculation The execution cost on the node, s _i is the execution cost of the i-th task type on the storage node. The execution cost of a task on computing nodes and storage nodes can represent the cost of a specific resource (such as CPU overhead, network overhead, etc.), or it can be an abstract execution cost weighted by multiple resources according to a certain heuristic.

In the embodiment of the present invention, since the present invention supports elastic scaling of the computing resource pool, the CPU on the computing node will not become a performance bottleneck. Therefore, the execution cost of the task in the computing node in the present invention is preferably the network overhead of data transmission. Since the number of storage nodes is determined by the amount of data that the application needs to store persistently, and usually does not fluctuate significantly in a short period of time, the CPU resources of the storage nodes are limited, so the execution cost of the tasks in the present invention on the storage nodes is Preferably CPU overhead. At this time, c _i represents the network overhead of data transmission when the task of the i-th task type is executed on the computing node, and s _i represents the CPU overhead generated when the task of the i-th task type is executed on the storage node.

After the task of the i-th task type is executed on the computing node and the storage node to obtain the corresponding c _i and s _i , c _i and s _i are fed back to the scheduler. The scheduler counts the c _i and s _i of the task feedback in all i-th task types and calculates the average. The overall runtime characteristics (c _i , s _i ) of the i-th task type can be obtained, that is, for a class For tasks, c _i and _si in the runtime feature tuples represent mathematical expectation values, while for a single task, c _i and _si represent the specific execution cost. By inputting the overall runtime characteristics (c _i , s _i ) of the i-th task type into the preset scheduling algorithm, the scheduler can further determine the optimal allocation ratio of the i-th task type.

In the embodiment of the present invention, the runtime characteristics of the task are a dynamic change amount. In order to cope with the dynamic changes of the runtime characteristics of the task, the runtime characteristics c _i and s _i recorded by the scheduler in the present invention are calculated by moving average. way to get it.

In the present invention, determining the optimal allocation ratio of the first task type by inputting the runtime characteristics into a preset scheduling algorithm for calculation includes: inputting the runtime characteristics into a preset scheduling algorithm, Determine the relative cost of the first task type; sort the first task type and the second task type according to the relative cost; determine the optimal split point parameter through a sub-algorithm in the preset scheduling algorithm Optimal solution: determine the optimal allocation ratio of the first task type based on the sorting results and the optimal solution of the split point parameters.

In the embodiment of the present invention, the proportion of n task types in the workload of the system in the present invention is: P={p ₀ , p ₁ ,..., p _n-1 }, ∑ _i p _i =1 , where p _i is the proportion of the i-th task type, and i is numbered from 0; the total throughput of the system is R; the throughput of the i-th task type is p _i R; the allocation ratio of n-type tasks is where x _i ∈ [0, 1] represents the proportion of the i-th task type scheduled to the storage node (or the probability that tasks belonging to the i-th task type are scheduled to the storage node); T _i is the tail delay of the i-th task type (For example, the delay of the 99% quantile of the task in the i-th task type); t _i is the delay SLO (ServiceLevelObjective service level objective) of the i-th task type, which represents the constraint on T _i , that is, the tail of the task Delay T _i must not exceed delay SLO.

In the embodiment of the present invention, given the proportion of the i-th task type in all task types, then T _i is R and function, because on the one hand, delay is positively related to the throughput of the system, on the other hand, due to resource sharing, tasks will also be affected by other tasks scheduled to the same node. The goal of the present invention is to maximize the total system throughput on the premise of meeting the delay SLO of each task type. The problem can be formalized as the following formula (1) and formula (2):

For the above problems, it is necessary to solve is an n-dimensional vector, and the search space is too large, so it is difficult to solve directly. This invention uses the mathematical properties of queuing theory to transform the original problem expression composed of the above formula (1) and formula (2) into another set of equivalent expressions, and on this basis, it is deduced that the optimal solution has one Two structures, thus greatly simplifying the search space. Specifically, since tasks are either scheduled to a computing node for execution or to a storage node for execution, the present invention decomposes the above tail delay _Ti into two parts:/> and/> represent the tail latency of the i-th task type when it is executed on the computing node and storage node respectively. According to the allocation ratio x _i of the i-th task type, the relationship between the overall tail delays T _i and T _i ^C and T _i ^S can be expressed by formulas (3) to (5):

T _i =T _i ^C , x _i =0#(3)

T _i =T _i ^S , x _i =1#(4)

T _i ≤ max {T _i ^C , T _i ^S }, x _i ∈ (0, 1) #(5)

Therefore, in order to satisfy the delay SLO constraint in the above formula (2), row selection constraints can be equivalently applied to T _i ^C and T _i ^S respectively.

Further, according to queuing theory, the above T _i ^C and T _i ^S can be related to the load of the system. The advantage of this is that the load on the system can be written as a closed-form expression. For the runtime characteristics (c _i , s _i ) of the i-th task type, the embodiment of the present invention has explained that the execution cost of the task on the computing node is preferably the network overhead of data transmission, and the execution cost of the task on the storage node is preferably for CPU overhead. The network bandwidth resource capacity between the computing node and the storage node and the CPU resource capacity of the storage resource pool are C and S respectively. The network bandwidth and the load on the storage node CPU can be further defined as and/> That is, the ratio between resource occupancy and resource capacity.

In the embodiment of the present invention, when the arrival process of the task request PRC is a Poisson process, it can be inferred according to the queuing theory that Tx ^C is a monotonically increasing function of ρ _C , and T _i ^S is a monotonically increasing function of ρ _S. Thus, T _i ^C and T _i ^S can be adjusted by adjusting the load of the system. On this basis, the present invention further transforms the original problems of formulas (1) and (2) into problems corresponding to the following formulas (6) to (10):

in and/> are the equivalent delay SLOs for T _i ^C and T _i ^S respectively, that is, the delay constraints for T _i ^C and T _i ^S respectively. Can be proven mathematically/> and/> existence, but it is often impossible to obtain the actual values of the two from the delay SLO split given by the user. The main significance of introducing these two equivalent delay constraints is that the original problems of formula (1) and formula (2) can be transformed into the optimization of ρ _c and ρ _S.

Specifically, first by adjusting the allocation ratio Make ρ _C and ρ _S as balanced as possible; secondly, since T _i ^C and T _i ^S are monotonic with respect to ρ _C and ρ _S respectively, so adjust/> The equivalent delay constraints in formulas (9) to (10) can be satisfied; finally, according to the equivalence given by formulas (3) to (5), the feasibility of the two equivalent delay constraints can be further Satisfaction is transformed into the satisfiability of the constraints in formula (2) of the original problem, thereby ensuring that the tail delay of the task does not exceed the delay SLO given by the user.

In an actual system, the current limiter in the scheduler only counts the overall tail delay _Ti . The current limiter gradually increases (or decreases) the total throughput of the system until _Ti reaches the user-given latency SLO. Taking increasing throughput as an example, this process corresponds to formulas (6) to (10), which is the current allocation ratio of the current limiter. By increasing the total throughput R of the system, ρ _C and ρ _S rise, which in turn makes either of formula (9) and formula (10) reach the equivalent delay constraint first, which in turn causes the actual statistic _Ti to reach the user-given Out of delay SLO.

Based on the above ideas, embodiments of the present invention solve the original problems of the above formula (1) and formula (2) by optimizing ρ _C and ρ _S. According to the above formulas (6) to (10) and the monotonicity of T _i ^C and T _i ^S with respect to ρ _C and ρ _S , it can be inferred that the optimal solution should make ρ _C and ρ _S as small as possible. Specifically, we only need to consider the binary group (ρ _C , ρ _S ) that satisfies Pareto optimality. In other words, for fixed ρ _C , the optimal solution should minimize ρ _S ; conversely, for fixed ρ _S , the optimal solution should minimize ρ _C . Consider the initial situation where all tasks are scheduled to computing nodes, that is, x _i =0, and ρ _S =0 at this time. Now, some tasks are gradually scheduled to storage nodes to balance the load of network bandwidth. If you choose to schedule the i-th task type to the storage node, each time the load is reduced by one unit from ρ _C , the corresponding increase in ρ _S is: Therefore, in order to make ρ _S as small as possible, task types with smaller s _i /c _i should be prioritized to be scheduled to the storage node. Therefore, the present invention uses s _i /c _i as the evaluation function to convert the runtime characteristics of the tasks into relative costs, and uses the ranking of relative costs as the priority of scheduling each task type to the storage node, that is, the smaller the relative cost The task type is scheduled to the storage node with a higher priority.

In the embodiment of the present invention, after all task types are sorted from small to large according to their relative costs, the top-ranked task types are prioritized and scheduled to the storage node. Therefore, there is a special split point task type k in the optimal solution. All task types with a smaller relative cost than k are scheduled to the storage node (the allocation ratio is 100%), and all task types with a larger relative cost than k are scheduled. To the computing node (the allocation ratio is 0%), only the exact allocation ratio of task type k at this split point is between 0% and 100%, and tasks are executed on both the storage node and the computing node. Therefore, only the task type k of the split point needs to be determined, and the optimal allocation proportions of all task types can be generated in two, thus simplifying the search space and facilitating rapid convergence. In order to facilitate numerical solution, the present invention represents this bisecting structure through a real number α (split point parameter) on [0, 1]. The mapping relationship between the sorted allocation proportions x _i of various task types and the split point parameter α is the following formula (11):

Through the mapping relationship given by formula (11) and the value of the split point parameter α, the allocation proportion of each task type can be determined. The specific meaning expressed by the above formula (11) is: sort n task types (task type numbers are 0 to n-1) and map them to the [0, 1] interval, where the i-th task is mapped to the sub-interval [(i/n, (i+1)/n)]; and the task type corresponding to the sub-interval where α is located is the split point task type k. For example, there are 10 task types, numbered 0 to 9; if the optimal solution α ^* given by the preset scheduling algorithm is 0.55, then the sub-interval where the optimal solution is located is [0.5, 0.6], corresponding to the 6th The task type is the split point task type, and the number k=5. At the same time, it can also be obtained that the allocation ratio of this task type is αn-i=0.5 (50%). For the first 5 task types whose relative cost is lower than that of category 6, their allocation ratios are all 1 (100%), while the last four task types whose relative cost is higher than that of category 6 have the same allocation ratio. is 0%.

In embodiments of the present invention, the relative cost of the first task type is obtained by inputting the runtime characteristics of the first task type into a preset scheduling algorithm for calculation. For example, when the runtime characteristics of the first task type are (c ₁ , s ₁ ), the relative cost of the first task type is s ₁ /c ₁ . After obtaining the relative cost of the first task type, since the second task type is a task type processed by the system, the system has obtained the relative cost of each second task type, and compares the first task type with the relative cost of each task type. Sort with each second task type to obtain the corresponding sorting result. At the same time, the optimal solution of the split point parameter α is determined through the sub-algorithm in the preset scheduling algorithm.

After obtaining the sorting results of the first task type and the second task type, and the optimal solution of the split point parameter α, based on the mapping relationship expression between the allocation ratio of various task types and the split point parameter, that is, formula (11), The optimal allocation ratio of the first task type can be determined.

In the embodiment of the present invention, the detailed process of the sub-algorithm used to determine the optimal solution α ^* of the split point parameter α in the preset scheduling algorithm is as follows. First of all, the maximum throughput that the system can carry under the premise of meeting the delay SLO given by the user is a function of the split point parameter α, recorded as R(α). For a given α, the corresponding value of R(α) can be approximated by the current limiter in the scheduler, and the curve of R(α) can be fitted by sampling α. The sub-algorithm of the scheduler to solve the optimal solution α ^* of the split point parameter α is based on a basic assumption, that is, the assumption that R(α) is a unimodal function. sub-algorithm by maintaining an upper bound on α ^* and lower bound α , and gradually reduce the search space (i.e. interval/> ). Specifically, the algorithm divides the current search space of α into several small intervals, samples the endpoints of the small intervals one by one, and determines the peak value of R(α) (i.e., α) through the value of R(α) observed at each endpoint. ^* ) is within the interval range. The above process is called an iteration. The initial search space of each iteration is the new interval range determined in the previous iteration, that is, at the beginning of each iteration, the new interval range given in the previous iteration is divided. The new interval range determined in each round of iteration is strictly included in its initial search space, so that the algorithm can gradually reduce the search space until it approaches the optimal solution α ^* .

Specifically, in each iteration, the algorithm will Divide it into M small intervals (M is the parameter of the algorithm), and traverse all interval endpoints in order to find the local maximum; the local maximum is defined as: three consecutive endpoints α _i-1 <α _i <α _i+1 , such that R(α _i )>R(α _i-1 ) and R(α _i )>R(α _i-1 ). Based on the assumption that R(α) is a unimodal function, it can be determined that α ^* is located on [α _i-1 , α _i+1 ], thereby reducing the search space. Since each small interval is 1/M of the original interval, the algorithm can ensure that the search space is reduced by a constant ratio after each iteration. Therefore the algorithm has logarithmic time complexity.

In the embodiment of the present invention, the scheduler will search the interval Initialize to [0, 1], and repeat the iteration until the interval length is less than the threshold δ; at this time, you can choose any/> A point within is used as an approximation to the optimal solution α ^* . After the algorithm converges, the scheduler uses this result until it detects a change in the workload or cluster state. At this time, the scheduler will reinitialize the preset scheduling algorithm and calculate a new α ^* to cope with related changes.

In the present invention, the method further includes: adjusting the throughput of the system through a current limiter according to the end-to-end delay during task execution and the service level target given by the user; adjusting the scheduling according to the throughput of the system split point parameters of the processor to maximize the throughput of the system.

In the embodiment of the present invention, the scheduler and the current limiter in the scheduler form a dual cycle control system. The current limiter in the scheduler acts as an inner loop. In this inner loop, the current limiter counts the end-to-end delay during task execution, obtains the tail delay of each task type, and adjusts the total throughput of the system according to the service level target (delay SLO) given by the user. R, thereby ensuring that user service level objectives are met. The scheduler forms the outer loop. In the outer loop, the scheduler will run the sub-algorithm of the scheduling algorithm, adjust the split point parameter α according to the total throughput R of the system given by the current limiter, and then optimize the optimal allocation ratio of each task type. to maximize the total throughput R of the system. The dual loop control system runs asynchronously in the background of the scheduler, that is, the scheduler can schedule in the foreground at the same time according to the allocation ratio currently given by the dual loop control system.

In the embodiment of the present invention, the inner loop and the outer loop of the control system are continuously optimized iteratively until they converge to the optimal solution. In order to avoid a coupling relationship between the two loops that will lead to failure to converge, the cycle frequencies of the two loops cannot be too close. Therefore, the present invention preferably sets the frequency of the inner circulation to 200HZ and the frequency of the outer circulation to 20HZ. It should be understood that the respective frequencies of the inner circulation and the outer circulation can also be other frequencies, as long as the frequencies of the two are ensured It is sufficient that the difference reaches a set threshold. The set threshold can be set according to actual application scenarios and is not specifically limited here.

In the embodiment of the present invention, if a new task type appears in the system and/or the task type decreases and/or the runtime characteristics of the task type change significantly, it means that the workload of the system has changed. At this time, the optimal solution of the new split point parameters is determined through the sub-algorithm in the preset scheduling algorithm. The specific implementation is the same as the above implementation, and will not be described again here. If there is an increase or decrease in nodes in the system, it means that the cluster status of the system has changed. At this time, the new optimal solution of the split point parameters is determined through the sub-algorithm in the preset scheduling algorithm. The specific implementation is the same as the above implementation. The method is the same and will not be repeated here.

In the present invention, the method further includes: determining the difference between the runtime characteristics of each task type in the current time window and the sliding average of its own historical runtime characteristics; The allocation ratio of the third task type whose difference between the running-time characteristic sliding average exceeds the first threshold is set as the default allocation ratio; the third task type is allocated to the computing node or storage node for execution according to the default allocation ratio, and statistics are collected The new execution costs of the preset number of tasks of the third task type on the computing nodes and storage nodes are then determined, and new runtime characteristics are determined; by inputting the new runtime characteristics into the preset scheduling algorithm, the new execution costs are determined. The relative cost of the third task type; sort all task types according to the relative cost; determine the optimal solution of the split point parameters through the sub-algorithm in the preset scheduling algorithm; according to the sorting results of all task types and the split point The optimal solution of parameters determines the optimal allocation ratio of all task types.

In an embodiment of the present invention, the difference between the runtime characteristics of each task type in the current time window and the respective sliding average of historical runtime characteristics is determined. When the difference between the runtime characteristics of the task type in the current time window and the sliding average of its own historical runtime characteristics exceeds the first threshold, it indicates that the runtime characteristics of the task type have changed significantly. At this time, the task type's runtime characteristics have changed significantly. The relative cost and corresponding optimal allocation ratio will also change. The allocation ratio currently used by this task type will no longer be accurate, and the relative cost and corresponding optimal allocation ratio of this task type need to be corrected.

At this time, the present invention sets the allocation proportion of the third task type whose difference between the runtime characteristics in the current time window and the sliding average of its own historical runtime characteristics exceeds the first threshold as the default allocation proportion, and assigns the third task The type is allocated to computing nodes or storage nodes according to the default allocation ratio for execution, and the new execution costs of the preset number of tasks of the third task type on the computing nodes and storage nodes are counted to determine the new runtime. feature. By inputting the new runtime characteristics into the preset scheduling algorithm, the relative cost of the third task type is determined. The specific implementation is the same as the above implementation, and will not be described again here. All task types are re-sorted according to the relative cost of each task type, and the optimal solution of the split point parameters is re-determined through the sub-algorithm in the preset scheduling algorithm. The specific implementation is the same as the above implementation and will not be described again here. Based on the obtained ranking results of all task types and the optimal solution of the split point parameters, as well as the mapping relationship expression between the distribution ratio of various task types and the split point parameters (that is, the above formula 11), the optimal solution of all task types is re-determined. The specific implementation of the optimal distribution ratio is the same as the above-mentioned implementation, and will not be described again here.

In an embodiment of the present invention, another optional implementation is to actively re-calculate the runtime characteristics of each task type every preset time interval to cope with possible changes in the runtime characteristics.

In the present invention, the method further includes: determining the request discarding situation of the current limiter; when the current limiter discards the request, increasing the capacity of the computing resource pool in a stepwise manner until the current limiter no longer discards the request; When the streamer does not discard requests, the number of computing nodes is reduced in a stepwise manner according to the load of the system.

In the embodiment of the present invention, when the resource capacity is fixed, the current limiter will limit the number of task requests in the system to meet the delay SLO. In real scenarios, the scale of task requests may fluctuate greatly over time. In order to avoid discarding overflow requests when the request volume is large, or causing waste due to idle resources when the request volume is low, the scheduler of the present invention can adjust the capacity of the computing resource pool according to the real-time scale of task requests. Since the demand for computing resources depends on the number of requests submitted by users, it has a large range of change, while the demand for storage resources depends on the amount of data persistently stored by the application, and the range of change is usually small. Therefore, the present invention selects the computing resource pool as the object of resource elastic expansion.

In the embodiment of the present invention, in order to achieve resource elastic expansion, the present invention adds a new outer loop in addition to the existing double loop of the scheduler. The outer loop determines the request discarding situation of the current limiter. If the overflow request is discarded by the current limiter, the outer loop will increase the capacity of the computing resource pool in a stepwise manner until the current limiter no longer discards requests. At the same time, when the current limiter does not discard requests, according to the network bandwidth of the system and the load ρ _C and ρ _S on the storage node CPU, the number of computing nodes is reduced in a stepwise manner without affecting the throughput and delay SLO. Embodiments of the present invention perform elastic scaling of resources at the CPU core level, and can adjust the granularity of elastic scaling according to the specific configuration and implementation of the system.

In the present invention, the method further includes: determining the actual load of each storage node; when the difference between the actual load of the storage node and the average load of the system exceeds a second threshold, dividing the storage node into a new independent Scheduling strategy group; divide a preset number of computing nodes into the new independent scheduling strategy group; each strategy group runs independently as a subsystem for task scheduling and execution.

In real scenarios, application data is usually sharded on multiple storage nodes, and tasks may show a skewed access pattern when accessing data shards, that is, a few hotspot shards carry most accesses. In this case, there will be a large gap between the average values represented by ρ _C and ρ _S and the actual load of the hotspot shards, thus affecting the scheduling effect.

To address this problem, the present invention proposes a scheduling policy group mechanism. This mechanism collects the actual load of each storage node. When the access pattern is not skewed, that is, when there are no hotspot shards, all nodes belong to a default scheduling policy group. When there is a skew in the access pattern such that the difference between the actual load of a storage node and the average load of the system exceeds the second threshold, the storage node is divided into a new independent scheduling policy group and the preset A certain number of computing nodes are divided into the new scheduling policy group, so that each scheduling policy group has independent computing and storage nodes. The number of computing nodes in the new scheduling policy group can be set to an initial value according to the computing intensity of the tasks in the group; since the present invention can achieve elastic expansion and contraction of computing resources, the setting of the initial value will not affect the final performance. As workloads change, storage nodes whose load levels revert to the mean can be re-incorporated into the default scheduling policy group. Each scheduling policy group will independently run the dual-cycle control system and resource elastic expansion in the above embodiment. Since there is no resource sharing between scheduling policy groups, each policy group runs independently as a subsystem for task scheduling and execution. This means that the scheduling algorithms of each scheduling policy group can be parallelized.

In the embodiment of the present invention, the first task type represents a task type that has not been processed by the system, the second task type represents a task type that has been processed by the system, and the third task type represents a significant change in runtime characteristics. , a task type that needs to re-count its own runtime characteristics.

In the embodiment of the present invention, the present invention focuses on the scheduling problem of mixed loads (mixed loads of multiple task types) in resource decoupled data centers, with the goal of meeting the delay SLO (Service Level Objective) of various task types. Maximize the system throughput under the premise. Delay SLO usually stipulates that the tail delay of a task does not exceed a set constant; delay SLO can be set independently for each task type.

The core of the present invention is to schedule various task types separately according to their runtime characteristics, that is, each task type is scheduled according to its own allocation ratio. Specifically, the present invention discovers and proposes that the optimal solution to the mixed load scheduling problem has a special structure, which can greatly simplify the complexity of the problem. On this basis, the present invention designs an efficient algorithm to solve the optimal scheduling plan in real time. In addition, in order to cope with the fluctuation of the number of task requests over time and better utilize resources, the present invention supports elastic expansion and contraction of the computing resource pool. Finally, when the data access pattern is skewed, the present invention provides a scheduling policy group mechanism to cope with the unbalanced load within the cluster.

In the embodiment of the present invention, the prototype system implemented by the present invention consists of three parts, including a scheduler, a computing node, and a storage node, as shown in Figure 2. The scheduler is used to schedule tasks to computing or storage nodes for execution. The scheduler processes different task types separately and calculates a corresponding optimal allocation ratio for each task type. The scheduler obtains the runtime characteristics of the task by counting the task execution costs on the computing nodes and storage nodes, and uses them as input to the preset scheduling algorithm. The scheduler also includes a current limiter, which limits the number of task requests based on the end-to-end latency of the task to meet the latency SLO.

The computing node is used to receive tasks assigned by the scheduler and is responsible for executing them. Computing nodes are equipped with a large number of CPUs (central processing units) and have stronger computing power than storage nodes. The CPU on a compute node is organized into several work units. While executing tasks, these workers remotely access storage nodes to obtain data. Additionally, the compute node contains a monitoring unit that tracks the runtime characteristics of the tasks. When a task completes, a feedback message containing these statistics is sent to the scheduler.

The storage node consists of a data warehouse and several work units. The work unit on the storage node is similar to that on the computing node, but it can directly access local data when executing tasks (that is, perform calculations on the storage side). The number of work units on storage nodes is usually less than that on compute nodes. The storage node is the same as the compute node. The storage node also contains a monitoring unit to track the runtime characteristics of the tasks. When a task completes, a feedback message containing these statistics is sent to the scheduler.

In the embodiment of the present invention, the data accessed by the task may be data fragmented on multiple storage nodes. By default, tasks in this invention only access one shard, that is, the data required by each task can be obtained by accessing only a single storage node. This default assumption is consistent with the reality of stored procedures in existing distributed databases. When users submit a task call request, they need to indicate the data shard they access. If the scheduler chooses to schedule the task to the storage node, the storage node must have relevant shards; if the scheduler chooses to schedule the task to the computing node, there is no restriction because the data needs to be obtained remotely through the network.

In embodiments of the present invention, scheduler instances can be added or removed independently of the computing resource pool and the storage resource pool. Since the preset scheduling algorithm only needs to run periodically, the scheduler is integrated into the load balancer widely deployed within the data center as a background process. Because the preset scheduling algorithm is not on the critical path of task execution, the scheduler usually does not become a system bottleneck. To meet the throughput requirements of large data centers, multiple load balancer nodes can be added according to industry practice.

In order to verify the effectiveness of the scheduling method provided by the present invention, the present invention uses a variety of synthetic loads and application loads to test the implemented prototype system. Experimental results show that the present invention can achieve sub-second level convergence speed, can adapt to a variety of dynamic workloads, and can increase system throughput by 3 to 21 times compared to current scheduling methods. The system also has good horizontal scalability.

The server-less computing scheduling method for resource decoupling data centers provided by the present invention has the following advantages: application performance is more optimized, the present invention can achieve high throughput while ensuring delay SLO, and the resource utilization rate is higher. The present invention can perform load balancing between the computing resource pool and the storage resource pool to improve resource utilization; it can quickly and stably converge. The present invention can respond quickly when the load or cluster configuration changes, and stabilize the system at the optimal level. status; easy to deploy and use, the present invention does not require the upper layer application to change the code.

In embodiments of the present invention, the current limiter adjusts the throughput of the system according to the end-to-end delay of the task to alleviate the queuing of task requests on the computing nodes and storage nodes, thereby ensuring that the delay SLO is met. In the prototype system of the present invention, the current limiter adopts AIMD algorithm. The current limiter can also use other congestion control algorithms. In order to allow applications to be executed on both computing nodes (remote data access) and storage nodes (local data access), the present invention abstracts the remote data warehouse into a local data warehouse on the computing node, providing application-oriented and local data Access a consistent API (Application Programming Interface). The monitoring units on the computing nodes and storage nodes are responsible for counting the runtime characteristics of the tasks and feeding them back to the scheduler. The monitoring unit only counts the end-to-end execution cost of the task, such as the total CPU time occupied, so it is non-intrusive to the application.

Each embodiment in this specification is described in a progressive manner. Each embodiment focuses on its differences from other embodiments. The same and similar parts between the various embodiments can be referred to each other.

Finally, it should be noted that in this article, relational terms such as first and second are only used to distinguish one entity or operation from another entity or operation, and do not necessarily require or imply that these entities or any such actual relationship or sequence between operations. Furthermore, the terms "comprises," "comprises," or any other variation thereof are intended to cover a non-exclusive inclusion such that a process, method, article, or end device that includes a list of elements includes not only those elements, but also elements not expressly listed or other elements inherent to such process, method, article or terminal equipment. Without further limitation, an element defined by the statement "comprises a..." does not exclude the presence of additional identical elements in a process, method, article or terminal device including the stated element.

The above is a detailed introduction to the server-less computing scheduling method for resource decoupling data centers provided by the present invention. Specific examples are used in this article to illustrate the principles and implementation methods of the present invention. The description of the above embodiments It is only used to help understand the method and its core idea of the present invention; at the same time, for those of ordinary skill in the field, there will be changes in the specific implementation and application scope based on the idea of the present invention. In summary, The content of this description should not be construed as limiting the invention.

Claims (7)

1. A server-less computing scheduling method for resource decoupling data centers, characterized in that, applied to a scheduler, the method includes: Determine the corresponding task type based on the received task request RPC; When the task type is an unprocessed first task type, determine the allocation ratio corresponding to the first task type to be the default allocation ratio; Allocate the tasks of the first task type to computing nodes or storage nodes for execution according to the default allocation ratio, and calculate the execution costs of a preset number of tasks of the first task type on the computing nodes and storage nodes. , and then determine the runtime characteristics of the first task type; Determine the optimal allocation ratio of the first task type by inputting the runtime characteristics into a preset scheduling algorithm for calculation; According to the optimal allocation ratio of the first task type, allocate tasks in the first task type to computing nodes or storage nodes for execution with corresponding probabilities; When the task type is a processed second task type, obtain the optimal allocation ratio corresponding to the second task type determined by the preset scheduling algorithm; According to the optimal allocation ratio corresponding to the second task type, tasks in the second task type are allocated to computing nodes or storage nodes for execution with corresponding probabilities. 2. The server-insensitive computing scheduling method for resource decoupling data center according to claim 1, characterized in that the runtime characteristics include: network overhead of data transmission when the computing node performs tasks, and storage node execution CPU overhead during the task. 3. The server-insensitive computing scheduling method for resource decoupling data centers according to claim 1, characterized in that the first task type is determined by inputting the runtime characteristics into a preset scheduling algorithm for calculation. The optimal allocation ratio includes: Determine the relative cost of the first task type by inputting the runtime characteristics into a preset scheduling algorithm; Sorting the first task type and the second task type according to the relative cost; Determine the optimal solution of the split point parameters through the sub-algorithm in the preset scheduling algorithm; According to the sorting result and the optimal solution of the split point parameters, the optimal allocation ratio of the first task type is determined. 4. The server-less computing scheduling method for resource decoupling data centers according to claim 1, characterized in that the method further includes: According to the end-to-end delay during task execution and the service level target given by the user, the throughput of the system is adjusted through the current limiter; According to the throughput of the system, the split point parameters of the scheduler are adjusted to maximize the throughput of the system. 5. The server-less computing scheduling method for resource decoupled data centers according to claim 4, characterized in that the method further includes: Determine the difference between the runtime characteristics of each task type in the current time window and its own historical runtime characteristics sliding average; Set the allocation proportion of the third task type whose difference between the runtime characteristics in the current time window and its own historical runtime characteristics sliding average exceeds the first threshold as the default allocation proportion; Allocate the third task type to the computing nodes or storage nodes for execution according to the default allocation ratio, and calculate the new execution costs of the preset number of tasks of the third task type on the computing nodes and storage nodes, and then determine new runtime features; Determine the relative cost of the third task type by inputting the new runtime characteristics into a preset scheduling algorithm; Sort all task types according to their relative cost; Determine the optimal solution of the split point parameters through the sub-algorithm in the preset scheduling algorithm; Based on the ranking results of all task types and the optimal solution of the split point parameters, the optimal allocation ratio of all task types is determined. 6. The server-less computing scheduling method for resource decoupled data centers according to claim 1, characterized in that the method further includes: Determine the request dropping status of the current limiter; When the current limiter discards requests, increase the capacity of the computing resource pool in a stepwise manner until the current limiter no longer discards requests; When the current limiter does not discard requests, the number of computing nodes is reduced in a stepwise manner according to the load of the system. 7. The server-less computing scheduling method for resource decoupling data centers according to claim 1, characterized in that the method further includes: Determine the actual load of each storage node; When the difference between the actual load of the storage node and the average load of the system exceeds the second threshold, the storage node is divided into a new independent scheduling policy group; Divide a preset number of computing nodes into the new independent scheduling policy group; Each policy group operates independently as a subsystem for task scheduling and execution.