技术领域Technical Field
本发明属于云计算资源调度技术领域，具体地说，是一种云计算环境中spark集群多作业调度方法。The present invention belongs to the technical field of cloud computing resource scheduling, and in particular, is a spark cluster multi-job scheduling method in a cloud computing environment.
背景技术Background technique
基于分布式计算特别是网格计算的发展，产生了一种新型服务计算模型：云计算(Cloud Computing)。云计算是一种能够通过网络以便利的、按需的方式访问一个可配置的计算资源共享池的模式，这个资源共享池能以最少的管理开销和最少的与供应商的交互，迅速配置、提供或释放资源。云计算的主要优势在于：能够迅速地降低硬件成本和提升计算能力以及存储容量等；用户可以以极低的成本投入获得极高的计算品质，而不用再投资购买昂贵的硬件设备，进行频繁的保养与升级。Based on the development of distributed computing, especially grid computing, a new service computing model has emerged: cloud computing. Cloud computing is a model that can access a configurable computing resource sharing pool in a convenient and on-demand manner through the network. This resource sharing pool can quickly configure, provide or release resources with minimal management overhead and minimal interaction with suppliers. The main advantages of cloud computing are: it can quickly reduce hardware costs and improve computing power and storage capacity; users can obtain extremely high computing quality at a very low cost, without having to invest in expensive hardware equipment and perform frequent maintenance and upgrades.
随着大数据处理需求的不断增长，将Spark集群部署到云环境中的趋势逐渐受到广泛欢迎。云环境提供了弹性的计算资源，使得Spark集群能够根据实际需求灵活伸缩，从而更有效地应对变化的工作负载。这种部署方式不仅提高了资源利用率，同时降低了维护和管理的成本，成为许多企业进行大数据处理的首选方式。在这一大数据处理趋势中，Spark批任务(bag of tasks(BoT))工作流调度的重要性凸显。调度算法的优化直接关系到任务执行效率和整个工作流的性能。然而，目前现有的调度算法主要是启发式的，缺乏对于云环境和Spark集群特性的深入理解。现有的工作流调度算法并不适合spark集群，因为spark集群调度算法需要将任务部署到虚拟机具体的执行器上，大多数算法并没有考虑到执行器这一层面。With the growing demand for big data processing, the trend of deploying Spark clusters in cloud environments has gradually become widely popular. The cloud environment provides elastic computing resources, allowing Spark clusters to flexibly scale according to actual needs, thereby more effectively coping with changing workloads. This deployment method not only improves resource utilization, but also reduces maintenance and management costs, becoming the preferred method for many companies to process big data. In this big data processing trend, the importance of Spark batch task (bag of tasks (BoT)) workflow scheduling is highlighted. The optimization of the scheduling algorithm is directly related to the efficiency of task execution and the performance of the entire workflow. However, the existing scheduling algorithms are mainly heuristic and lack a deep understanding of the characteristics of cloud environments and Spark clusters. Existing workflow scheduling algorithms are not suitable for spark clusters because spark cluster scheduling algorithms need to deploy tasks to specific executors of virtual machines, and most algorithms do not take the executor level into consideration.
当前的挑战在于寻找适用于云环境的精准调度算法，能够根据任务的性质、数据特征以及云资源的动态变化来进行智能决策。尽管启发式算法在某些情况下取得了一定效果，但由于云环境的复杂性，现阶段尚未出现普遍适用的理论模型。因此，研究人员和工程师正积极探索新的调度算法，以满足在云环境中Spark批处理任务工作流调度上的需求，提高任务执行的效率，降低资源成本，以更好地满足大数据处理的挑战。The current challenge is to find an accurate scheduling algorithm suitable for cloud environments, which can make intelligent decisions based on the nature of tasks, data characteristics, and dynamic changes in cloud resources. Although heuristic algorithms have achieved certain results in some cases, due to the complexity of cloud environments, there is no generally applicable theoretical model at this stage. Therefore, researchers and engineers are actively exploring new scheduling algorithms to meet the needs of Spark batch task workflow scheduling in cloud environments, improve the efficiency of task execution, and reduce resource costs to better meet the challenges of big data processing.
强化学习作为一种基于智能体与环境交互学习的范式，近年来在解决复杂的调度和优化问题中展现出独特的优势。其核心特点包括在不断试错的过程中学习最优策略，适应性强、能够处理不确定性、并且具备对动态环境的自适应性。这些优势使得强化学习成为解决大规模数据处理中Spark批任务工作流调度问题的潜在利器。在Spark批任务工作流调度中，强化学习算法通过将工作流的状态、动作和奖励建模为学习问题，能够有效地应对复杂的调度决策。与传统的启发式算法相比，强化学习能够在不断的实践中动态地调整策略，从而更好地适应不同的工作负载和环境变化。这种自适应性和泛化能力使得强化学习算法在面对具有动态特性的大数据处理场景时显得更为灵活和强大。强化学习算法的优越性还体现在其对于任务间关系和资源分配的综合考虑上。通过学习任务执行的时序信息和相互影响，强化学习能够更加智能地调度批处理任务，优化整个工作流的执行效率，进而提高大规模数据处理的整体性能。因此，强化学习算法在Spark批任务工作流调度中的优越性主要表现在其灵活性、自适应性以及对于动态环境的适应能力，为解决大规模数据处理中的调度挑战提供了一种新颖而有效的方法。As a paradigm based on interactive learning between agents and environments, reinforcement learning has shown unique advantages in solving complex scheduling and optimization problems in recent years. Its core features include learning optimal strategies in a continuous trial-and-error process, strong adaptability, ability to handle uncertainty, and adaptability to dynamic environments. These advantages make reinforcement learning a potential tool for solving the Spark batch task workflow scheduling problem in large-scale data processing. In Spark batch task workflow scheduling, reinforcement learning algorithms can effectively deal with complex scheduling decisions by modeling the state, action, and reward of the workflow as learning problems. Compared with traditional heuristic algorithms, reinforcement learning can dynamically adjust strategies in continuous practice to better adapt to different workloads and environmental changes. This adaptability and generalization ability make reinforcement learning algorithms more flexible and powerful when facing big data processing scenarios with dynamic characteristics. The superiority of reinforcement learning algorithms is also reflected in their comprehensive consideration of the relationship between tasks and resource allocation. By learning the timing information and mutual influence of task execution, reinforcement learning can more intelligently schedule batch tasks, optimize the execution efficiency of the entire workflow, and thus improve the overall performance of large-scale data processing. Therefore, the superiority of reinforcement learning algorithm in Spark batch task workflow scheduling is mainly reflected in its flexibility, adaptability and adaptability to dynamic environments, which provides a novel and effective method to solve the scheduling challenges in large-scale data processing.
发明内容Summary of the invention
本发明的目的在于提供一种云计算环境中spark集群多作业调度方法，以保证满足截止期的前提下减少虚拟机调度开销。The purpose of the present invention is to provide a method for scheduling multiple jobs of a spark cluster in a cloud computing environment, so as to reduce the virtual machine scheduling overhead while ensuring that the deadline is met.
实现本发明目的技术解决方案为：一种云计算环境中spark集群多作业调度方法，包括以下方案：The technical solution to achieve the purpose of the present invention is: a method for scheduling multiple jobs of a spark cluster in a cloud computing environment, including the following schemes:
对于基于Spark批任务的工作流，此类工作流由多个具有偏序约束的批任务构成，每个批批任务含多个并行任务；不同的批任务通常代表不同的业务过程，同一个批任务中的多个并行任务通常是由于需要分布式处理同一个业务过程的不同数据块或者参数产生的，因此每个任务都属于一个批任务。Spark中的执行器(Executor)是分布式计算框架中的关键组件，负责执行具体的计算任务。每个执行器在集群中的节点上启动，担当一线线程的角色。在一个Spark集群中，每个节点都可以启动一个或多个执行器实例，这样就能够实现任务的并行执行，从而提高整个应用程序的性能和吞吐量。For workflows based on Spark batch tasks, such workflows are composed of multiple batch tasks with partial order constraints, and each batch task contains multiple parallel tasks; different batch tasks usually represent different business processes, and multiple parallel tasks in the same batch task are usually generated by the need to distribute different data blocks or parameters of the same business process, so each task belongs to a batch task. The executor in Spark is a key component in the distributed computing framework, responsible for executing specific computing tasks. Each executor is started on a node in the cluster and plays the role of a first-line thread. In a Spark cluster, each node can start one or more executor instances, so that tasks can be executed in parallel, thereby improving the performance and throughput of the entire application.
对于Spark集群中随机到达的批任务工作流，方案A利用DQN网络给出工作流需要的执行器个数，作为方案B的输入；方案B将工作流需要的执行器部署到Spark集群的虚拟机中；等到工作流需要的所有执行器准备就绪后，方案C将工作流的任务调度到执行器上执行，完成整个工作流的执行。For batch task workflows that arrive randomly in a Spark cluster, Scheme A uses the DQN network to give the number of executors required by the workflow as the input of Scheme B; Scheme B deploys the executors required by the workflow to the virtual machines of the Spark cluster; after all the executors required by the workflow are ready, Scheme C schedules the tasks of the workflow to the executors for execution, completing the execution of the entire workflow.
方案A.基于DQN网络的执行器数量分配算法(DEA)：采用强化学习算法(DQN)建立基于强化学习的工作流执行器数量分配模型，强化学习模型为单个用户工作流分配满足工作流截止期限的最小执行器数量，所述DQN模型的网络结构为以循环神经网络作为隐含层的指针网络。DQN是处理复杂环境、高维状态空间和离散动作空间的强化学习问题的一种强大算法。使用DQN算法时，需要精确设置状态空间、动作空间和奖励函数。以下是对这三者的详细说明：Solution A. DQN-based executor quantity allocation algorithm (DEA): A reinforcement learning algorithm (DQN) is used to establish a workflow executor quantity allocation model based on reinforcement learning. The reinforcement learning model allocates the minimum number of executors that meet the workflow deadline for a single user workflow. The network structure of the DQN model is a pointer network with a recurrent neural network as the hidden layer. DQN is a powerful algorithm for dealing with reinforcement learning problems in complex environments, high-dimensional state spaces, and discrete action spaces. When using the DQN algorithm, the state space, action space, and reward function need to be accurately set. The following is a detailed description of these three:
1.状态空间(State Space)：状态空间是系统可能处于的所有状态的集合。对于DQN，状态通常表示为一个向量，其中包含每个工作流的负载信息和截止期限。确保状态空间能够充分表达问题的关键特征，并且能够提供足够的信息以支持智能体做出良好的决策。1. State Space: The state space is the set of all possible states that the system may be in. For DQN, the state is usually represented as a vector that contains the load information and deadline of each workflow. Make sure that the state space can fully express the key features of the problem and provide enough information to support the agent to make good decisions.
2.动作空间(Action Space)：动作空间包含智能体可以执行的所有可能动作。对于每个状态，对应的动作是单个工作流需要的执行器个数。合理定义动作空间是确保智能体能够在环境中采取有效行动的关键。2. Action Space: The action space contains all possible actions that the agent can perform. For each state, the corresponding action is the number of actuators required for a single workflow. Properly defining the action space is key to ensuring that the agent can take effective actions in the environment.
3.奖励函数(Reward Function)：奖励函数用于衡量智能体在执行某个动作后获得的反馈。它对智能体的行为提供了明确的指导，帮助算法学习最优策略。设计奖励函数时，需要考虑到平衡问题的难易度和学习过程中的稳定性，以及对所期望行为的明确奖惩信号。在确认了状态和动作与工作流以及执行器个数的对应关系后，将工作流调度到所有执行器上执行。若在截止期限内无法完成，奖励值将为负数；反之，执行器成本越高，奖励值越低且为正，执行器成本越低则奖励值越高且为正。3. Reward Function: The reward function is used to measure the feedback that the agent receives after performing an action. It provides clear guidance on the agent's behavior and helps the algorithm learn the optimal strategy. When designing a reward function, it is necessary to consider the difficulty of the balance problem and the stability of the learning process, as well as clear reward and punishment signals for the desired behavior. After confirming the correspondence between the state and action and the workflow and the number of executors, the workflow is scheduled to execute on all executors. If it cannot be completed within the deadline, the reward value will be negative; conversely, the higher the executor cost, the lower the reward value and the positive value, and the lower the executor cost, the higher the reward value and the positive value.
方案B.基于启发式的执行器部署策略(HEP)：执行完方案A后，通过DQN算法可以得到工作流的最佳执行器个数。一旦获取了每个工作流所需的执行器数量，我们将所有执行器按照最小新增成本的方式部署到Spark集群的虚拟机中。在现有的研究中，通常将执行器部署到虚拟机中，然而，并未充分考虑执行器的运行时间。相比之下，HEP方法能够通过计算得出一个工作流中所有执行器的运行时间。HEP方法分为两个主要阶段：将执行器部署到已租赁的虚拟机中，以及将执行器部署到新的虚拟机中。以下是HEP方法的详细步骤：Solution B. Heuristic-based executor deployment policy (HEP): After executing Solution A, the optimal number of executors for the workflow can be obtained through the DQN algorithm. Once the number of executors required for each workflow is obtained, we deploy all executors to the virtual machines of the Spark cluster in a way that minimizes the additional cost. In existing research, executors are usually deployed to virtual machines, however, the running time of the executors is not fully considered. In contrast, the HEP method can calculate the running time of all executors in a workflow. The HEP method is divided into two main stages: deploying executors to leased virtual machines and deploying executors to new virtual machines. The following are the detailed steps of the HEP method:
步骤1：计算当前工作流的执行时间，即为执行器的运行时间；Step 1: Calculate the execution time of the current workflow, which is the running time of the executor;
步骤2：遍历所有当前租用的虚拟机，对于每个虚拟机：首先检查是否可以继续部署执行器；如果是，计算该虚拟机的租赁结束时间(租赁时间为虚拟机时间间隔的倍数)，若执行器能在此时间之前完成运行，则将其部署到该虚拟机；Step 2: Traverse all currently leased virtual machines. For each virtual machine: first check whether the executor can continue to be deployed; if so, calculate the lease end time of the virtual machine (the lease time is a multiple of the virtual machine time interval). If the executor can complete the operation before this time, deploy it to the virtual machine;
步骤3：完成步骤2后，检查剩余待部署的执行器数量是否为零。如果是，则直接结束；如果不是，则继续执行；Step 3: After completing step 2, check whether the number of remaining executors to be deployed is zero. If yes, end directly; if not, continue to execute;
步骤4：此步骤涉及将执行器部署到已租赁的虚拟机上，为了选择最佳方案，需要综合考虑虚拟机的租赁时间和价格。在进行综合判断时，选取价格最低的方案；Step 4: This step involves deploying the executor to the leased virtual machine. In order to select the best solution, it is necessary to comprehensively consider the lease time and price of the virtual machine. When making a comprehensive judgment, select the solution with the lowest price;
步骤5：完成步骤4后，检查剩余待部署的执行器数量是否为零。若为零，则返回所有部署方案；若不为零，则说明集群无法在当前阶段成功部署所有执行器，因此放弃之前的部署方案，返回空方案。Step 5: After completing step 4, check whether the number of remaining executors to be deployed is zero. If it is zero, all deployment plans are returned; if it is not zero, it means that the cluster cannot successfully deploy all executors at the current stage, so the previous deployment plan is abandoned and an empty plan is returned.
方案C.基于任务最快完成时间的任务调度方案(EFT)：EFT方法是任务调度领域中的经典方法，其核心思想是将任务调度到完成时间最快的执行器上。Solution C. Task scheduling scheme based on the fastest task completion time (EFT): The EFT method is a classic method in the field of task scheduling. Its core idea is to schedule tasks to the executor with the fastest completion time.
本发明与现有技术相比，其显著优点为：本发明构建基于强化学习策略的执行器数量分配模型，使得DQN模型能适用于不同大小、不同类型的批任务工作流的执行器数量分配问题，在保证较高时效性的同时，提升模型的泛化能力；本发明提出了一种以最小化虚拟机成本为基础的执行器部署方法。通过巧妙设计和深度优化，该方法在部署执行器时注重降低整体成本。通过有效利用虚拟机资源，实现了成本的最小化。Compared with the prior art, the present invention has the following significant advantages: the present invention constructs an executor quantity allocation model based on reinforcement learning strategy, so that the DQN model can be applied to the executor quantity allocation problem of batch task workflows of different sizes and types, while ensuring high timeliness and improving the generalization ability of the model; the present invention proposes an executor deployment method based on minimizing virtual machine costs. Through clever design and deep optimization, this method focuses on reducing the overall cost when deploying executors. Cost minimization is achieved by effectively utilizing virtual machine resources.
附图说明BRIEF DESCRIPTION OF THE DRAWINGS
图1是本发明实施例中云环境下Spark批任务工作流执行流程总架构图。FIG1 is a general architecture diagram of the Spark batch task workflow execution process in a cloud environment in an embodiment of the present invention.
图2是本发明实施例中DQN算法的网络结构图。FIG. 2 is a network structure diagram of a DQN algorithm in an embodiment of the present invention.
表1和表2是本发明实施例中HEP方案的实例表。Table 1 and Table 2 are example tables of the HEP scheme in the embodiments of the present invention.
图3和图4是本发明实施例中EFT方案的实例图。3 and 4 are diagrams showing examples of the EFT scheme in the embodiment of the present invention.
具体实施方式Detailed ways
下面结合实施例和说明书附图对本发明作进一步说明。The present invention will be further described below in conjunction with the embodiments and the accompanying drawings.
本发明实施例中云环境下Spark批任务工作流执行流程总架构图如图1所示。此图已经包含了云服务提供商、工作流批任务、弹性中介、工作流调度器和各种类型虚拟机组成的数据中心。The overall architecture diagram of the Spark batch task workflow execution process in the cloud environment in the embodiment of the present invention is shown in Figure 1. This figure already includes a cloud service provider, workflow batch tasks, elastic intermediaries, workflow schedulers, and a data center composed of various types of virtual machines.
首先，对作业进行预处理，提取任务数组、任务的前驱任务数组以及后继任务数组等相关信息。然后，进行特征提取，包括作业的BoT信息(包含所有BoT的任务个数、平均任务长度以及BoT之间的最大数据量)以及作业的截止期限等特征。这些特征将作为输入传递给DQN算法。在使用DQN算法时，目标是得出满足作业截止期限的最少执行器数量。DQN算法将根据输入的特征来学习和优化执行器数量分配策略。通过训练，DQN可以自主地决定在满足作业要求的前提下，分配所需的最少执行器数量。接下来，根据DQN算法给出的执行器数量，将执行器部署到虚拟机上。此步骤旨在降低虚拟机成本，确保资源利用效率的最大化。最后，就绪的任务将通过EFT(任务最快完成时间)方法进行调度。EFT方法是一种启发式方法，旨在优化任务的调度顺序，以最小化整体作业完成时间。通过EFT方法，任务可以以最快的速度完成，从而进一步提高系统的效率和性能。First, the job is preprocessed to extract relevant information such as the task array, the task's predecessor task array, and the successor task array. Then, feature extraction is performed, including the job's BoT information (including the number of tasks in all BoTs, the average task length, and the maximum amount of data between BoTs) and the job's deadline. These features will be passed as input to the DQN algorithm. When using the DQN algorithm, the goal is to obtain the minimum number of executors that meet the job deadline. The DQN algorithm will learn and optimize the executor number allocation strategy based on the input features. Through training, DQN can autonomously decide to allocate the minimum number of executors required while meeting the job requirements. Next, according to the number of executors given by the DQN algorithm, the executors are deployed to the virtual machines. This step aims to reduce the cost of virtual machines and ensure maximum resource utilization efficiency. Finally, the ready tasks will be scheduled using the EFT (Fastest Task Completion Time) method. The EFT method is a heuristic method that aims to optimize the scheduling order of tasks to minimize the overall job completion time. With the EFT method, tasks can be completed at the fastest speed, further improving the efficiency and performance of the system.
图2是本发明实施例中DQN算法的网络结构图。如图所示，算法执行步骤如下：Figure 2 is a network structure diagram of the DQN algorithm in an embodiment of the present invention. As shown in the figure, the algorithm execution steps are as follows:
首先，提取作业WFl的两个特征：graArrl(t)和Dl(t)，graArrl(t)为工作流WFl的图结构的二维数组，Dl(t)为WFl的截止期限，得到状态sl(t)＝(graArrl,Dl)∈S(S为DQN的状态空间)。然后生成一个在0到1之间的随机小数r，epsilon为DQN的参数，也是在0到1之间，如果r小于epsilon，那么选择在状态sl(t)下最大Q值对应的动作al(t)(一个介于0到EDMAX之间的整数，EDMAX的值需根据Spark集群和工作流相关信息来确定)，否则随机选择动作al(t)。在确定al(t)后，可以得到相应的执行器需求数量Ol(t)(all(t)+1)。然后根据公式计算奖励rl(t)(如果工作流在Ol(t)个执行器上通过EFT算法成功完成，并且满足截止期限，则执行器成本(将执行器看做是按照间隔收费的虚拟机，所有执行器的CPU核数、内存容量和MIPS参数都一样，所以价格也都一样)越低，r_l(t)值越大且为正；而执行器成本越高，则r_l(t)值越小且为正。若未能满足截止期限，则r_l(t)值为负)，于是进入下一状态sl(t+1)。然后将样本(sl(t),al(t),rl(t),sl(t+1))存入回放池B。最后从回放池中选择N个样本，更新当前值网络和目标值网络的参数；First, extract two features of job WFl : graArrl (t) and Dl (t), graArrl(t) is the two-dimensional array of the graph structure of workflow WFl , Dl (t) is the deadline of WFl , and get the state sl (t) = (graArrl , Dl ) ∈ S (S is the state space of DQN). Then generate a random decimal r between 0 and 1, epsilon is the parameter of DQN, also between 0 and 1. If r is less than epsilon, then select the action al (t) corresponding to the maximum Q value in state sl (t) (an integer between 0 and EDMAX, the value of EDMAX needs to be determined according to the Spark cluster and workflow related information), otherwise randomly select the action al (t). After determining al (t), the corresponding number of executors required Ol (t) (all (t) + 1) can be obtained. Then calculate the reward rl (t) according to the formula (if the workflow is successfully completed on Ol (t) executors through the EFT algorithm and meets the deadline, the lower the executor cost (the executor is regarded as a virtual machine charged at intervals, and the number of CPU cores, memory capacity and MIPS parameters of all executors are the same, so the price is also the same), the larger the r_l(t) value is and the more positive it is; the higher the executor cost, the smaller the r_l(t) value is and the more positive it is. If the deadline is not met, the r_l(t) value is negative), and then enter the next state sl (t+1). Then store the sample (sl (t), al (t), rl (t), sl (t+1)) in the replay pool B. Finally, select N samples from the replay pool and update the parameters of the current value network and the target value network;
表1Table 1
表2Table 2
表1和表2是本发明实施例中HEP方案的实例表。HEP方案的执行步骤如下：Table 1 and Table 2 are example tables of the HEP scheme in the embodiment of the present invention. The execution steps of the HEP scheme are as follows:
在开始HEP方案之前，需要先通过DQN网络得到作业需要的执行器个数。Before starting the HEP solution, it is necessary to obtain the number of executors required for the job through the DQN network.
算法分为两个主要阶段：已租赁虚拟机的执行器部署和新虚拟机的执行器部署。对于作业WFl,用n表示它需要的执行器个数。在第一个阶段，执行以下步骤：已租赁的虚拟机集合A中的虚拟机按照空闲执行器个数从小到大排序。对于每台虚拟机vm，判断是否可以在其结束时间之前完成作业WFl的执行。用m表示虚拟机vm的空闲执行器数量。如果m<n，则利用全部m个空闲执行器，将此方案添加到方案集合pl中，并更新n＝n-m；否则，在虚拟机vm上部署n个执行器，将此方案添加到方案集合pl中，将n更新为0，并跳出第一阶段的循环。在第一阶段结束后，检查n的值是否为0。若为0，表示无需部署新的执行器，算法结束并直接返回。在第二个阶段，执行以下步骤：首先，确认作业所需的最大虚拟机数量。考虑到集群中存在多种虚拟机类型，使用n除以最低配置的虚拟机可以部署的执行器数量，然后取最小整数上限值，得到最大虚拟机数量。确定了最大虚拟机数量后，从1到最大数量，针对每个数量选择合适的虚拟机方案。例如，当虚拟机数量为2时，从虚拟机集群中任意选择2台新虚拟机，检查它们是否可以满足所需的执行器数量。如果满足条件，则将这两台虚拟机作为一个方案添加到集合Fl中。按照这个操作，确定虚拟机数量为2时的所有方案。综上所述，按照以上步骤，确定从1到最大数量对应的所有方案。在确定了方案集合Fl之后，按照产生的租赁成本从小到大对Fl中的方案进行排序。对于Fl中的每个方案，逐一检查其是否可以执行，即集群中是否有符合该方案的新虚拟机。如果方案可执行，则将其添加到pl中，并作为返回值返回。如果Fl中的所有方案都不满足，意味着集群资源紧张，需要延迟作业的执行器部署，直接返回空值。The algorithm consists of two main phases: executor deployment for leased virtual machines and executor deployment for new virtual machines. For job WFl , let n represent the number of executors it requires. In the first phase, perform the following steps: Sort the virtual machines in the leased virtual machine set A from the smallest to the largest number of idle executors. For each virtual machine vm , determine whether the execution of job WFl can be completed before its end time. Let m represent the number of idle executors of virtual machine vm . If m<n , use all m idle executors, add this solution to the solution set pl , and update n=nm ; otherwise, deploy n executors on virtual machine vm , add this solution to the solution set pl , update n to 0 , and jump out of the loop of the first phase. After the first phase ends, check whether the value of n is 0. If it is 0, it means that no new executors need to be deployed, and the algorithm ends and returns directly. In the second phase, perform the following steps: First, confirm the maximum number of virtual machines required for the job. Considering that there are multiple types of virtual machines in the cluster, divide n by the number of executors that can be deployed by the lowest-configured virtual machine, and then take the minimum integer upper limit value to get the maximum number of virtual machines. After determining the maximum number of virtual machines, select the appropriate virtual machine solution for each number from 1 to the maximum number. For example, when the number of virtual machines is 2, select 2 new virtual machines from the virtual machine cluster at random and check whether they can meet the required number of executors. If the conditions are met, add these two virtual machines as a solution to the set Fl . According to this operation, all solutions when the number of virtual machines is 2 are determined. In summary, according to the above steps, all solutions corresponding to the number from 1 to the maximum number are determined. After determining the solution set Fl , sort the solutions in Fl from small to large according to the rental cost generated. For each solution in Fl , check whether it can be executed one by one, that is, whether there are new virtual machines in the cluster that meet the solution. If the solution is executable, add it to pl and return it as the return value. If all solutions in Fl are not satisfied, it means that the cluster resources are tight and the executor deployment of the job needs to be delayed, and a null value is directly returned.
关于执行器部署算法，假设需要在新的虚拟机上部署13个执行器，假设集群不同的虚拟机配置下所示：t1虚拟机：能够部署8个执行器，时间间隔价格为0.8；t_2虚拟机：能够部署16个执行器，时间间隔价格为1.6；t_3虚拟机：能够部署24个执行器，时间间隔价格为2.4。配置最低的虚拟机类型为t_1，它能部署8个执行器，用13除以8，取小数最接近的上限整数值，为2。表1为虚拟机个数分别为1和2的时候对应的所有方案表。表2为所有方案经过租赁成本排序后的方案表。按照如图所示的方案表，优先尝试价格较低的方案，如果方案无法实施，比如说集群中资源无法满足，则向下尝试方案，直到方案可以被满足为止。Regarding the executor deployment algorithm, suppose that 13 executors need to be deployed on a new virtual machine. Assume that the cluster has different virtual machine configurations as shown below:t1 virtual machine: can deploy 8 executors, time interval price is 0.8; t_2 virtual machine: can deploy 16 executors, time interval price is 1.6; t_3 virtual machine: can deploy 24 executors, time interval price is 2. The lowest configured virtual machine type is t_1, which can deploy 8 executors. Divide 13 by 8 and take the nearest upper integer value, which is 2. Table 1 shows all the corresponding solutions when the number of virtual machines is 1 and 2 respectively. Table 2 shows the solution table after all solutions are sorted by rental cost. According to the solution table shown in the figure, the solution with lower price is tried first. If the solution cannot be implemented, for example, the resources in the cluster cannot be met, then try the solution downward until the solution can be met.
图3和图4是本发明实施例中EFT方案的实例图,EFT方案的执行步骤如下：FIG. 3 and FIG. 4 are example diagrams of the EFT scheme in the embodiment of the present invention. The execution steps of the EFT scheme are as follows:
在开始EFT方案之前，需要确保作业需要的所有执行器都已经部署到虚拟机并处于就绪状态。Before starting the EFT solution, you need to ensure that all executors required by the job have been deployed to the virtual machines and are in a ready state.
首先需要将作业WF_l的所有任务部署到执行器上。具体步骤如下：收集作业WF_l的所有就绪任务，放入集合U。将集合U中的任务按照任务长度从大到小排序，以便优先调度较长的任务。依次取出U中的任务进行调度。对于任务Task_i，计算它在所有执行器E上的完成时间。将task_i调度到完成时间最快的执行器上执行。将task_i从U中删除，因为该任务已经被调度。更新集合U，重复上述步骤，直到所有任务都被调度完成。EFT调度算法通过优先调度较长的任务，并将任务调度到完成时间最快的执行器上，以最大程度地减少作业的执行时间，提高系统的执行效率。First, all tasks of job WF_l need to be deployed to the executor. The specific steps are as follows: Collect all ready tasks of job WF_l and put them into set U. Sort the tasks in set U from large to small according to task length so that longer tasks can be scheduled first. Take out the tasks in U one by one for scheduling. For task Task_i, calculate its completion time on all executors E. Schedule task_i to execute on the executor with the fastest completion time. Delete task_i from U because the task has been scheduled. Update set U and repeat the above steps until all tasks are scheduled. The EFT scheduling algorithm minimizes the execution time of jobs and improves the execution efficiency of the system by giving priority to longer tasks and scheduling tasks to the executors with the fastest completion time.
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202410076765.7ACN118152084A (en) | 2024-01-19 | 2024-01-19 | Spark cluster multi-job scheduling method in cloud computing environment |
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202410076765.7ACN118152084A (en) | 2024-01-19 | 2024-01-19 | Spark cluster multi-job scheduling method in cloud computing environment |
| Publication Number | Publication Date |
|---|---|
| CN118152084Atrue CN118152084A (en) | 2024-06-07 |
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202410076765.7APendingCN118152084A (en) | 2024-01-19 | 2024-01-19 | Spark cluster multi-job scheduling method in cloud computing environment |
| Country | Link |
|---|---|
| CN (1) | CN118152084A (en) |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN118409848A (en)* | 2024-07-03 | 2024-07-30 | 通号通信信息集团有限公司 | A cloud computing workflow scheduling method, system, processing device and medium |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111209104A (en)* | 2020-04-21 | 2020-05-29 | 南京南软科技有限公司 | Energy perception scheduling method for Spark application under heterogeneous cluster |
| CN114281528A (en)* | 2021-12-10 | 2022-04-05 | 重庆邮电大学 | An energy-saving scheduling method and system based on deep reinforcement learning and heterogeneous Spark cluster |
| CN115686788A (en)* | 2022-10-31 | 2023-02-03 | 北京工业大学 | Heuristic task scheduling and energy consumption optimization method for cloud data center based on deep Q network |
| CN116302519A (en)* | 2023-03-04 | 2023-06-23 | 西安电子科技大学青岛计算技术研究院 | Micro-service workflow elastic scheduling method, system and equipment based on container cloud platform |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN111209104A (en)* | 2020-04-21 | 2020-05-29 | 南京南软科技有限公司 | Energy perception scheduling method for Spark application under heterogeneous cluster |
| CN114281528A (en)* | 2021-12-10 | 2022-04-05 | 重庆邮电大学 | An energy-saving scheduling method and system based on deep reinforcement learning and heterogeneous Spark cluster |
| CN115686788A (en)* | 2022-10-31 | 2023-02-03 | 北京工业大学 | Heuristic task scheduling and energy consumption optimization method for cloud data center based on deep Q network |
| CN116302519A (en)* | 2023-03-04 | 2023-06-23 | 西安电子科技大学青岛计算技术研究院 | Micro-service workflow elastic scheduling method, system and equipment based on container cloud platform |
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN118409848A (en)* | 2024-07-03 | 2024-07-30 | 通号通信信息集团有限公司 | A cloud computing workflow scheduling method, system, processing device and medium |
| CN118409848B (en)* | 2024-07-03 | 2024-09-13 | 通号通信信息集团有限公司 | Cloud computing workflow scheduling method, system, processing equipment and medium |
| Publication | Publication Date | Title |
|---|---|---|
| CN112416585B (en) | Deep learning-oriented GPU resource management and intelligent scheduling method | |
| CN110737529B (en) | Short-time multi-variable-size data job cluster scheduling adaptive configuration method | |
| CN105159762B (en) | Heuristic cloud computing method for scheduling task based on Greedy strategy | |
| CN109857535B (en) | Spark JDBC-oriented task priority control implementation method and device | |
| CN104331321B (en) | Cloud computing task scheduling method based on tabu search and load balancing | |
| CN108154317B (en) | Workflow group scheduling method based on example self-adaptive distribution integration in multi-cloud environment | |
| CN114217966A (en) | Deep learning model dynamic batch processing scheduling method and system based on resource adjustment | |
| CN107329815A (en) | A kind of cloud task load equalization scheduling method searched for based on BP Tabu | |
| US12386658B2 (en) | Pull mode and push mode combined resource management and job scheduling method and system, and medium | |
| CN108108245A (en) | The mixed type dispatching method and system of a kind of cloud platform wide node scientific workflow | |
| CN112231081A (en) | Monotonic rate resource scheduling method and system based on PSO-AHP in cloud environment | |
| Yang et al. | A fully hybrid algorithm for deadline constrained workflow scheduling in clouds | |
| CN115033357B (en) | Microservice workflow scheduling method and device based on dynamic resource selection strategy | |
| CN105005503B (en) | Cloud computing load balancing method for scheduling task based on cellular automata | |
| CN118152084A (en) | Spark cluster multi-job scheduling method in cloud computing environment | |
| CN118585329A (en) | A cluster computing task resource allocation method and device based on Q learning | |
| CN116010064A (en) | Method, system and device for DAG job scheduling and cluster management | |
| CN119376894A (en) | A distributed task resource scheduling system and method | |
| CN117909061A (en) | Model task processing system and resource scheduling method based on GPU hybrid cluster | |
| CN116882697A (en) | Method and system for scheduling energy efficiency of carrying task flows for reload train group | |
| Wei et al. | Optimizing production with deep reinforcement learning | |
| CN110084507B (en) | A hierarchical-aware scientific workflow scheduling optimization method in cloud computing environment | |
| CN110008002B (en) | Job scheduling method, device, terminal and medium based on stable distribution probability | |
| CN118963272A (en) | A reconfigurable workshop dynamic scheduling method based on reinforcement learning and rule evolution | |
| Liu et al. | A microservice workflow scheduling algorithm based on dynamic resource selection strategy |
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination |