CN116775315B - Multi-core CPU concurrent transaction allocation method based on dependency graph - Google Patents

Abstract

A multi-core CPU concurrent transaction allocation method based on a dependency graph comprises the following steps: constructing a dependency graph based on execution relevance among transactions in a database, and determining the pheromone quantity of sides corresponding to two adjacent nodes based on the dependency relationship among the two adjacent nodes of the dependency graph; determining heuristic information of each node based on transaction attributes of transactions corresponding to each node of the dependency graph; and executing the transaction in the database according to the dependency graph based on the ant colony behavior model, and updating pheromones on each side of the dependency graph. According to the method, the dependence graph is built based on the defined relation among the transactions, the problem of scheduling and distributing the concurrent transactions of the multi-core CPU in the database is solved by utilizing the ant colony algorithm with the distributed characteristic, the method has better performance in the complex dependence relation and interweaving condition of processing a plurality of transactions, the advantages of the multi-core CPU are fully exerted, and the resource utilization rate of the database system and the execution efficiency of data are improved.

Description

A multi-core CPU concurrent transaction allocation method based on dependency graph

Technical Field

The present invention relates to the technical field of database transaction allocation, and in particular to a multi-core CPU concurrent transaction allocation method based on a dependency graph.

Background Art

In recent years, the rapid development of the Internet has not only promoted the rapid expansion of application scale, but also triggered the emergence of massive data and the urgent need for database systems to support high-throughput transaction processing. Backend database systems are facing the challenge of coping with the growing amount of data and concurrent requests. In this context, database systems, as key data management and transaction processing platforms, have been further optimized and developed. Transaction processing is one of the most critical features of database systems. It involves processing concurrent transaction requests, among which multi-core CPU concurrent transaction allocation has become an important part of improving system performance. The goal of the multi-core CPU concurrent transaction allocation method in the database is to maximize system performance by reasonably scheduling concurrent transactions.

In order to cope with the challenges brought by multi-core processors, there are currently a variety of technologies for multi-core CPU transaction scheduling, such as priority scheduling algorithm, time slice round-robin scheduling algorithm, multi-level feedback queue scheduling algorithm, etc. For example, the priority scheduling method determines the scheduling order of transactions according to the priority of the transaction. When a high-priority transaction is blocked or waiting for some reason, it may lead to uneven resource allocation and cause starvation of low-priority transactions; the time slice round-robin scheduling algorithm, each transaction is assigned a time slice. When the time slice is used up, the transaction will be suspended and placed at the end of the ready queue waiting for the next round of scheduling, which may lead to low resource utilization and increased transaction switching overhead; multi-level feedback queue scheduling algorithm: a scheduling algorithm that integrates multiple queues, each queue has different priorities and time slice sizes, and the multi-level queue scheduling algorithm may lead to increased transaction switching overhead, especially when the number of transactions is large, the transaction switching overhead may become significant.

Therefore, there is an urgent need for a multi-core CPU concurrent transaction allocation method based on a dependency graph to solve the above technical problems.

Summary of the invention

The present invention provides a multi-core CPU concurrent transaction allocation method based on a dependency graph, which is used to solve the technical problems of low database resource utilization and high transaction switching overhead in the prior art. The specific technical solution is as follows:

In a first aspect, the present invention provides a multi-core CPU concurrent transaction allocation method based on a dependency graph, the method comprising:

Building a dependency graph based on the execution association between transactions in the database, wherein each transaction in the database serves as a node in the graph, and the dependency relationships between transactions form directed edges in the graph;

Determine the pheromone amount of the edge corresponding to the two adjacent nodes based on the dependency relationship between the two adjacent nodes in the dependency graph;

Determining heuristic information of each node based on a transaction metric attribute of a transaction corresponding to each node of the dependency graph;

Based on the pheromone quantity and the heuristic information, the transaction in the database is executed through the behavior model of the ant colony and the dependency graph, and the pheromone quantity of each edge on the dependency graph is updated according to the execution result.

Furthermore, the step of constructing a dependency graph based on the execution association between transactions in the database includes:

Establishing a corresponding node based on each transaction in the database;

Based on the data flow relationship, timestamp information, value information, and submission order between the transactions corresponding to each of the nodes, the edges between the nodes are determined, and the edges are used to represent the association between the nodes.

Furthermore, based on the data flow relationship, timestamp information, value information, and submission order between the transactions corresponding to each node, the edges between the nodes are determined, specifically:

The data dependency relationship R1 between corresponding nodes is marked by recording data source, data destination and version information:

The control dependency relationship R2 between corresponding nodes is marked by recording the timestamp information of transactions or data:

By recording the transaction value information, the transaction priority dependency R3 between the corresponding nodes is marked:

The parallel execution relationship R4 between corresponding nodes is marked by recording the transaction submission order.

Furthermore, the step of determining the pheromone amount of the edge corresponding to two adjacent nodes based on the dependency relationship between the two adjacent nodes in the dependency graph includes:

Determine the data weight D1 corresponding to the data dependency R1, the control weight D2 corresponding to the control dependency R2, the priority weight D3 corresponding to the transaction priority dependency R3, and the parallel weight D4 corresponding to the parallel execution relationship R4;

Based on the initial pheromone quantity, the pheromone evaporation coefficient, the dependency relationship between the two adjacent nodes and the weight corresponding to each of the dependency relationships, the pheromone quantity of the edge corresponding to the two adjacent nodes is determined.

Furthermore, the determining of the heuristic information of each node based on the transaction attribute of the transaction corresponding to each node of the dependency graph includes:

Determine attribute heuristic information corresponding to each attribute in the transaction attribute;

Determine the weight corresponding to each attribute heuristic information;

Determining heuristic information of the transaction based on the respective attribute heuristic information and the weight;

A heuristic information mapping value is determined based on the heuristic information of the transaction and the maximum and minimum values of the heuristic information of each attribute, and the heuristic information mapping value is used as the heuristic information between adjacent nodes.

Furthermore, the transaction attributes corresponding to each node include: node transaction resource utilization, node transaction execution time, node transaction priority, and node transaction waiting time.

Furthermore, the ant colony-based behavior model executes the transactions in the database according to the dependency graph and updates the pheromone on each edge of the dependency graph, specifically:

Based on the heuristic information of each node in the dependency graph and the pheromone amount of each edge, simulating an ant colony to concurrently execute transactions in the database;

The pheromone amount of the edge corresponding to the executed transaction is updated based on the completion quality of the executed transaction.

Furthermore, the pheromone quantity of the edge corresponding to the executed transaction is updated based on the completion quality of the executed transaction, and the formula adopted is:

It is the evaporation rate of pheromones, which is used to control the volatilization of pheromones and reduce the amount of pheromones;

is the pheromone increment of ant k through edge (i, j), and the pheromone increment is related to the quality of ant k's scheduling plan.

In a second aspect, the present invention further provides a multi-core CPU concurrent transaction allocation system based on a dependency graph, the system comprising: a dependency graph module, a pheromone quantity module, a heuristic information module, and an update module;

The dependency graph module is used to construct a dependency graph based on the execution association between transactions in the database, wherein each transaction in the database serves as a node in the graph, and the dependency relationships between transactions form directed edges in the graph;

The pheromone quantity module is used to determine the pheromone quantity of the edge corresponding to the two adjacent nodes based on the dependency relationship between the two adjacent nodes in the dependency graph;

The heuristic information module is used to determine the heuristic information of each node based on the transaction attributes of the transaction corresponding to each node of the dependency graph;

The updating module is used to execute the transaction in the database through the behavior model of the ant colony and the dependency graph based on the pheromone quantity and the heuristic information, and to update the pheromone quantity of each edge on the dependency graph according to the execution result.

In a third aspect, the present invention further provides a database, wherein the database is provided with a memory and a processor, the memory is used to store a computer program, and the processor is used to call the computer program in the memory to perform the following steps:

Building a dependency graph based on the execution association between transactions in the database, wherein each transaction in the database serves as a node in the graph, and the dependency relationships between transactions form directed edges in the graph;

Determine the pheromone amount of the edge corresponding to the two adjacent nodes based on the dependency relationship between the two adjacent nodes in the dependency graph;

Determine heuristic information of each node based on the transaction attributes of the transaction corresponding to each node of the dependency graph;

Based on the pheromone quantity and the heuristic information, the transaction in the database is executed through the behavior model of the ant colony and the dependency graph, and the pheromone quantity of each edge on the dependency graph is updated according to the execution result.

Effect of the invention:

For the problem solved by this method, a dependency graph is constructed for the first time for the allocation and scheduling of concurrent transactions on multi-core CPUs. In database system applications, multi-core CPUs can execute multiple transactions at the same time. This concurrent processing capability can better support the needs of database systems when accessed by multiple users, and improve the throughput and response time of the database under high concurrency. This method solves the problem of scheduling and allocating concurrent transactions on multi-core CPUs in the database based on the constructed dependency graph, more effectively utilizes the advantages of multi-core CPUs, improves concurrent processing capabilities, and has breakthroughs in transaction flexibility, reliability, resource utilization, etc.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG1 is a flow chart of a multi-core CPU concurrent transaction allocation method based on a dependency graph according to the present invention;

FIG2 is a DAG dependency graph based on dependency relationships of a multi-core CPU concurrent transaction allocation method based on a dependency graph according to the present invention;

FIG3 is an architectural relationship diagram of a multi-core CPU concurrent transaction allocation method based on a dependency graph according to the present invention.

DETAILED DESCRIPTION

The following will be combined with the drawings in the embodiments of the present invention to clearly and completely describe the technical solutions in the embodiments of the present invention. Obviously, the described embodiments are only part of the embodiments of the present invention, not all of the embodiments. Based on the embodiments of the present invention, all other embodiments obtained by ordinary technicians in this field without making creative work are within the scope of protection of the present invention.

Specific embodiment 1:

The present invention provides a multi-core CPU concurrent transaction allocation method based on a dependency graph, which is used to solve the technical problems of low database resource utilization and high transaction switching overhead in the prior art. The specific technical solution is as follows:

In the first aspect, the present invention provides a multi-core CPU concurrent transaction allocation method based on a dependency graph, the method comprising: constructing a dependency graph based on the execution correlation between transactions in a database, wherein each transaction in the database serves as a node in the graph, and the dependency relationship between transactions forms a directed edge in the graph; determining the pheromone amount of the edge corresponding to two adjacent nodes based on the dependency relationship between the two adjacent nodes in the dependency graph; determining the heuristic information of each node based on the transaction metric attributes of the transaction corresponding to each node in the dependency graph; executing the transactions in the database through the behavior model of an ant colony and the dependency graph based on the pheromone amount and the heuristic information, and updating the pheromone amount of each edge on the dependency graph according to the execution result.

In this embodiment, in the system, transactions are identified and constructed into a dependency graph. Each transaction is a node in the graph, and the dependencies between transactions form directed edges in the graph. The dependency edge can be a data dependency, that is, the execution of one transaction depends on the output data of another transaction, or a control dependency, that is, the execution of one transaction is affected by the execution of another transaction, or other dependencies. The execution association between transactions also includes data association, control association, etc. Transaction measurement attributes include node transaction resource utilization, node transaction execution time, node transaction priority, node transaction waiting time and other attributes. The dependency graph is used to represent the dependency relationship between transactions, and the ant colony algorithm is used to simulate the scheduling behavior of transactions. The path graph taken by ants does not refer to the dependency graph, but to the process of ant colonies selecting paths in the search space in the ant colony algorithm.

Furthermore, the construction of a dependency graph based on the execution correlation between transactions in the database includes: establishing a corresponding node based on each transaction in the database; determining the edges between the nodes based on the data flow relationship, timestamp information, value information, and submission order between the transactions corresponding to each of the nodes, wherein the edges are used to represent the correlation between the nodes.

Furthermore, based on the data flow relationship, timestamp information, value information, and submission order between the transactions corresponding to each of the nodes, the edges between the nodes are determined, specifically: the data dependency relationship R1 between the corresponding nodes is marked by recording the data source, data destination, and version information; the control dependency relationship R2 between the corresponding nodes is marked by recording the timestamp information of the transaction or data; the transaction priority dependency R3 between the corresponding nodes is marked by recording the transaction value information; and the parallel execution relationship R4 between the corresponding nodes is marked by recording the transaction submission order.

Furthermore, the method of determining the pheromone amount of the edge corresponding to two adjacent nodes based on the dependency relationship between the two adjacent nodes in the dependency graph includes: determining the data weight D1 corresponding to the data dependency R1, the control weight D2 corresponding to the control dependency R2, the priority weight D3 corresponding to the transaction priority dependency R3, and the parallel weight D4 corresponding to the parallel execution relationship R4; and determining the pheromone amount of the edge corresponding to the two adjacent nodes based on the initial pheromone amount, the pheromone evaporation coefficient, the dependency relationship between the two adjacent nodes and the weights corresponding to each of the dependency relationships.

Furthermore, the heuristic information of each node is determined based on the transaction attributes of the transactions corresponding to each node of the dependency graph, including: determining the attribute heuristic information corresponding to each attribute in the transaction attributes; determining the weight corresponding to each attribute heuristic information; determining the heuristic information of the transaction based on each attribute heuristic information and the weight; determining the heuristic information mapping value based on the heuristic information of the transaction and the maximum and minimum values of each attribute heuristic information, and the heuristic information mapping value is used as the heuristic information between the adjacent nodes.

Furthermore, the transaction attributes corresponding to each node include: node transaction resource utilization, node transaction execution time, node transaction priority, and node transaction waiting time.

Furthermore, the ant colony-based behavior model executes transactions in the database according to the dependency graph and updates the pheromones on each edge of the dependency graph. Specifically, based on the heuristic information of each node in the dependency graph and the pheromone quantity of each edge, the ant colony is simulated to concurrently execute transactions in the database; based on the completion quality of the executed transactions, the pheromone quantity of the edge corresponding to the executed transaction is updated.

Furthermore, the pheromone quantity of the edge corresponding to the executed transaction is updated based on the completion quality of the executed transaction, and the formula adopted is:

It is the evaporation rate of pheromones, which is used to control the volatilization of pheromones and reduce the amount of pheromones; is the pheromone increment of ant k through edge (i, j), and the pheromone increment is related to the quality of ant k's scheduling plan.

Specific embodiment 2:

The multi-core CPU concurrent transaction allocation method based on dependency graph aims to maximize data concurrency and database system performance by identifying and resolving dependencies between transactions to arrange scheduling reasonably. Such a method helps to avoid resource competition between database transactions, reduce context switching, and use core computing resources for effective parallel computing as much as possible. The following is a specific embodiment of a multi-core CPU concurrent transaction allocation method based on dependency graph:

The first step is to build a dependency graph:

In the system, transactions are identified and constructed into a dependency graph. Each transaction is a node in the graph, and the dependencies between transactions form directed edges in the graph (hereinafter referred to as dependency edges, directed edges or edges). Dependency edges connect transaction nodes and represent the dependencies between transactions. Dependency edges can be data dependencies, that is, the execution of one transaction depends on the output data of another transaction, or control dependencies, that is, the execution of one transaction is affected by the execution of another transaction, or other dependencies.

Building a dependency graph: First, the transactions of multi-core CPUs are represented as a directed acyclic graph (DAG).

It is a graph consisting of a set of vertices and directed edges, where each edge has a direction and there is no path that forms a loop. In other words, in a DAG, starting from any vertex and following the direction of the directed edge, you cannot eventually return to the starting point, and will not form a loop or cycle, while avoiding transaction deadlock or circular dependency.

1. Mark the data dependency R1 by recording the data source, data destination, version and other information:

(1) Read-Write Dependencies: If one transaction reads data written by another transaction, a read-write dependency exists. This dependency requires special consideration to ensure data consistency.

(2) Write-Write Dependencies: If two transactions write the same data item, there is a write-write dependency. This may lead to data conflicts and race conditions, and the execution order of transactions needs to be properly scheduled.

(3) Read-Read Dependencies: If two transactions read the same data item, a read-read dependency exists.

2. Control dependency R2 by recording the timestamp information of transactions or data:

(4) Control flow dependency: The execution order of one transaction is affected by the execution order of another transaction. For example, the execution branch of one transaction depends on the execution result of another transaction, or one transaction must wait before another transaction executes.

(5) Waiting dependency: A transaction waits for another transaction to complete before it can continue to execute. For example, a transaction needs to wait for the lock of another transaction to be released before it can continue to execute.

(6) Predecessor dependency: The execution of one transaction must occur before another transaction. For example, one transaction is the predecessor of another transaction and must be completed before the subsequent transaction can be executed.

3. Mark the transaction priority dependency R3 by recording the transaction value information:

(7) Priority tag: In a database system, different priority tags can be set for transactions, and transactions with higher priorities will be scheduled for execution first.

4. By recording the transaction submission order, the parallel execution relationship R4 can be marked:

(8) Parallel execution relationship: Two transactions can be executed simultaneously and have no dependency on each other. In a directed graph, this can be represented by adding independent transaction nodes without directed edges.

Step 2: Dependency graph analysis:

Analyze the dependency graph and use the directed edges between transactions to determine the dependencies between transactions.

(1) Dependency graph representation: First, the transactions in the database are represented as nodes of the dependency graph. Each transaction can be a node, or if a transaction is split into multiple subtasks, each subtask can also be a node. The dependency relationship between transactions is represented by edges.

(2) Data dependency analysis: Analyze the data dependency between transactions. Data dependency means that one task requires the output data of another task as input data. In the dependency graph, if node A has a directed edge pointing to node B, then node B depends on node A, indicating that task B requires the output data of task A. By analyzing the direction of the edge, the data dependency can be determined.

(3) Control dependency analysis: Analyze the control dependency relationship between tasks. Control dependency means that the execution of one task is affected by the execution of another task. For example, if task A is the predecessor task of task B, then the execution of task B can only start after the execution of task A. By analyzing the order of tasks, the control dependency relationship can be determined.

(4) Priority assignment: Based on the analysis results of the dependency graph, a priority is assigned to each task or node to indicate the execution importance and real-time requirements of the task.

(5) Parallel execution possibility analysis: Based on the dependencies between transactions, determine whether it is possible to execute some transactions in parallel. If there is no data dependency and control dependency between two transactions, they can be executed in parallel on a multi-core CPU. Identify which transactions can be executed concurrently, that is, unrelated transactions or parallel transactions.

Step 3: Transaction Scheduling:

Ant Colony Optimization (ACO) is an optimization algorithm that simulates an ant colony searching for food paths. In multi-core CPU transaction scheduling, the ant colony algorithm can help find a set of optimal concurrent transaction scheduling allocation schemes. The behavior of ants in the ant colony algorithm can correspond to the execution order of transactions. The ant colony algorithm simulates the process of ants releasing pheromones in the search space and making decisions based on the amount of pheromones and heuristic information. In multi-core CPU transaction scheduling, a similar method can be used to simulate ants searching for the optimal scheduling scheme on the dependency graph to maximize CPU utilization and system performance. However, existing ant colony algorithms are mostly used for path planning research. There is no application in the prior art that directly applies the ant colony algorithm to database transaction allocation. To this end, the present invention proposes an improved ant colony algorithm, the specific contents of which are as follows:

In multi-core CPU transaction scheduling, the dependency graph can be regarded as a directed acyclic graph (DAG), the transaction set E = {S1, S2, S3, S4, S5, S6, …, Sn}, W contains the dependencies between transactions, and the transaction dependency set is W = {R1, R2, R3, R4}.

The application process of the improved ant colony algorithm in multi-core CPU transaction scheduling is as follows:

Pheromone representation: The edges in the dependency graph are considered as paths, and the amount of pheromone is associated with the edges. Pheromones represent the quality or fitness of the path and can usually be initialized to a small positive value. In this method, pheromones are measured using the dependency relationships of the dependency graph established in step 1, such as data dependency R1, control dependency R2, transaction priority dependency R3, and parallel execution dependency R4.

1) Define the pheromone amount of the edge:

Assume that there is an edge e connecting nodes i and j, and the amount of pheromone is represented by τ(i, j).

2) Consider the impact of dependency on pheromone quantity: Determine the pheromone quantity through dependency relationship

Dependencies include data dependency R1, control dependency R2, transaction priority dependency R3, parallel execution dependency R4, and their corresponding weights are D1, D2, D3, and D4. The influence of dependencies can be combined into the pheromone quantity by weighted sum, as shown in the following formula:

Among them, τ0(i, j) is the initial pheromone amount, is the pheromone evaporation coefficient, R1(i, j), R2(i, j), R3 (i, j), and R4(i, j) represent the impact values of different dependencies, respectively.

(2) Ant behavior simulation: Simulate the process of multiple ants moving and selecting paths on the dependency graph. Each ant selects the next transaction to be executed based on the amount of pheromone and heuristic information until all transactions are scheduled. Create a group of ants and let them simulate the process of moving and selecting paths on the dependency graph. Each ant starts from a starting node and then selects the next node to be executed based on the amount of pheromone and heuristic information. Ants execute transactions according to their selection until all transactions are scheduled. In this step, the ant's selection strategy can be determined using the formula of the ant colony algorithm. When selecting the next node, the ant can use a probabilistic method to make decisions based on the amount of pheromone and heuristic information. Generally, the probability that an ant selects the next node j on node i can be calculated by the following formula:

This formula is the path selection probability formula. When the ant chooses the next transaction to be executed, it calculates the probability of path selection based on the amount of pheromone and heuristic information, where:

represents the probability that an ant chooses node j from node i.

Represents the amount of pheromone on edge (i, j).

is a parameter that adjusts the weight of pheromone and heuristic information in the selection.

Represents heuristic information, computed using problem-specific metrics.

Maps values for heuristic information.

Represents the set of nodes that ant k has not visited.

(3) Heuristic information: Heuristic information helps ants choose paths that may be more promising without the guidance of pheromones. The most important factors affecting the multi-core CPU concurrent transaction allocation method are node transaction resource utilization, node transaction execution time, node transaction priority, and node transaction waiting time, which are updated as the ants search to better guide path selection.

1) Node transaction resource utilization: If nodes i and j share the same resources (such as shared cache, shared memory, etc.), the execution of node i may affect the performance of node j, thereby affecting The value of .

2) Node transaction execution time: The transaction execution time on node i will affect the scheduling of transactions on other nodes. Longer execution time may cause more dependent nodes to wait, thus affecting The value of .

3) Node transaction priority: Some transactions may have higher priority and need to be executed as soon as possible. The nodes corresponding to the transactions with higher priority may become dependent objects of other nodes, thus affecting The value of .

4) Node transaction waiting time: The proportion of transaction waiting time on node i will affect the waiting time of transactions on other nodes. Longer waiting time may cause more nodes to wait for resources, increasing the total waiting time, thus affecting The value of .

Furthermore, based on node resource utilization:

= Resource utilization Ui/total resources U

Among them, resource utilization Ui represents the proportion of resources currently occupied by the transactions allocated to node i, and the total amount of resources represents the total resource capacity. This formula means that the higher the resource utilization of node i, The larger it is, the greater the influence of node i’s resources on the node, and the more attractive this path is.

Based on transaction execution time:

=1-(transaction execution time Ti/maximum transaction execution time T)

Among them, the transaction execution time Ti represents the time required to execute a transaction on node i, and the maximum transaction execution time represents the longest execution time of all transactions. If the time required to execute transaction i on node i is shorter, A larger value indicates that the execution time of node i has a greater impact on the node, and this path is more attractive.

Based on the priority of the transaction:

=Transaction priority Pi / highest priority P

Among them, priority Pi represents the priority of transaction i, and the highest priority represents the highest priority among all transactions. It means that the node i corresponding to the transaction with higher priority has a greater impact on the node, The larger the value, the more attractive it is to ants.

Based on transaction wait time:

=1-(transaction waiting time Wi / maximum transaction waiting time W)

Among them, the maximum transaction waiting time W represents the longest waiting time among all transactions. If the transaction waiting time on node i is short, A larger value indicates that the waiting time of node i has a greater impact on the node, and the path is more attractive.

Among them, H1, H2, H3, and H4 are the weights of the influencing factors.

Since different factors may have different dimensions, directly combining them together may result in large differences in the range of values. In order to ensure that their influence on the decision-making in the ant colony algorithm is reasonable, Normalize them to map them into the same range.

Using linear normalization method, Mapped to the range [0, 1]:

in, Yes all The minimum value in Yes all In this way, all The values are all between [0, 1], ensuring that they have the same dimension and weight processing effect.

In this way, when the ant chooses the next node, it will consider both the pheromone amount and the heuristic information and make a choice based on probability.

(4) Pheromone update: When all ants complete an iteration, the amount of pheromone is updated according to the quality of the scheduling plan. Generally, a better scheduling plan will release more pheromones.

in:

It is the evaporation rate of pheromone, which is used to control the volatilization of pheromone and reduce the amount of pheromone.

is the pheromone increment of ant k through edge (i, j), which is usually related to the quality of ant k ’s scheduling plan.

During the pheromone update process, a better scheduling scheme will release more pheromones to the relevant edges, thereby increasing the possibility of these edges being selected by ants.

(4) Repeated iteration: Repeat the ant behavior simulation and pheromone update process until the maximum number of iterations K is met.

(5) Select the optimal solution: After multiple iterations, multiple scheduling solutions are obtained from the behavior of the ants. F is a constant, Lk represents the quality of the path taken by the ants, and the optimal solution is selected by comparison, and finally The set represents the optimal concurrent transaction allocation scheme found by the ant colony in the iteration, that is, the scheduling scheme with the best performance as the final result.

Step 4: Execute and update dependency tracking:

By using the ant colony algorithm to perform parallel transaction allocation on a multi-core CPU, the optimal scheduling group can be obtained, thereby maximizing system performance. During the execution of the scheduling group, the satisfaction of the dependencies is tracked. If the dependency of a scheduling group cannot be satisfied, the execution of the transaction group may need to be suspended until the dependency is satisfied.

Through the parallel actions of multiple ants, the ant colony algorithm can better utilize the parallel performance of multi-core CPUs. Each ant is equivalent to a parallel execution unit, which can independently explore different scheduling schemes, thereby accelerating the search process. At the same time, the parallelism of the ant colony algorithm also helps to avoid falling into the local optimal solution, increasing the possibility and adaptability of the algorithm to search for the global optimal solution. The ant colony algorithm selects the optimal path solution by optimizing high resource utilization, low transaction execution time, high transaction priority, and short transaction waiting time, thereby improving the execution efficiency of multi-core CPU concurrent transactions.

Specific embodiment 3:

In a second aspect, the present invention further provides a multi-core CPU concurrent transaction allocation system based on a dependency graph, the system comprising: a dependency graph module, a pheromone quantity module, a heuristic information module, and an update module;

The dependency graph module is used to construct a dependency graph based on the execution association between transactions in the database, wherein each transaction in the database serves as a node in the graph, and the dependency relationships between transactions form directed edges in the graph;

The pheromone quantity module is used to determine the pheromone quantity of the edge corresponding to the two adjacent nodes based on the dependency relationship between the two adjacent nodes in the dependency graph;

The heuristic information module is used to determine the heuristic information of each node based on the transaction attributes of the transaction corresponding to each node of the dependency graph;

The updating module is used to execute the transactions in the database according to the dependency graph based on the behavior model of the ant colony, and to update the pheromone on each edge of the dependency graph.

Preferably, the dependency graph module is specifically used to: establish a corresponding node based on each transaction in the database;

Based on the data flow relationship, timestamp information, value information, and submission order between the transactions corresponding to each of the nodes, the edges between the nodes are determined, and the edges are used to represent the association between the nodes.

Preferably, the dependency graph module is further used to: mark the data dependency relationship R1 between corresponding nodes by recording data source, data destination and version information:

The control dependency relationship R2 between corresponding nodes is marked by recording the timestamp information of transactions or data:

By recording the transaction value information, the transaction priority dependency R3 between the nodes is marked:

The parallel execution relationship R4 between corresponding nodes is marked by recording the transaction submission order.

Preferably, the pheromone quantity module is used to: determine the data weight D1 corresponding to the data dependency R1, the control weight D2 corresponding to the control dependency R2, the priority weight D3 corresponding to the transaction priority dependency R3, and the parallel weight D4 corresponding to the parallel execution relationship R4;

Based on the initial pheromone quantity, the pheromone evaporation coefficient, the dependency relationship between the two adjacent nodes and the weight corresponding to each of the dependency relationships, the pheromone quantity of the edge corresponding to the two adjacent nodes is determined.

Preferably, the heuristic information module is used to: determine the attribute heuristic information corresponding to each attribute in the transaction attribute;

Determine the weight corresponding to each attribute heuristic information;

Determining heuristic information of the transaction based on the respective attribute heuristic information and the weight;

A heuristic information mapping value is determined based on the heuristic information of the transaction and the maximum and minimum values of the heuristic information of each attribute, and the heuristic information mapping value is used as the heuristic information between the adjacent nodes.

Preferably, the transaction attributes corresponding to each node include: node transaction resource utilization, node transaction execution time, node transaction priority, and node transaction waiting time.

Preferably, the update module is used to: simulate ant colonies to concurrently execute transactions in the database based on the heuristic information of each node and the pheromone amount of each edge in the dependency graph;

The pheromone amount of the edge corresponding to the executed transaction is updated based on the completion quality of the executed transaction.

Preferably, the pheromone quantity of the edge corresponding to the executed transaction is updated based on the completion quality of the executed transaction, and the formula adopted is:

It is the evaporation rate of pheromone, which is used to control the volatilization of pheromone and reduce the amount of pheromone.

is the pheromone increment of ant k through edge (i, j), and the pheromone increment is related to the quality of ant k's scheduling plan.

Specific embodiment 4:

In a third aspect, the present invention further provides a database, wherein the database is provided with a memory and a processor, the memory is used to store a computer program, and the processor is used to call the computer program in the memory to perform the following steps:

Building a dependency graph based on the execution association between transactions in the database, wherein each transaction in the database serves as a node in the graph, and the dependency relationships between transactions form directed edges in the graph;

Determine the pheromone amount of the edge corresponding to the two adjacent nodes based on the dependency relationship between the two adjacent nodes in the dependency graph;

Determine heuristic information of each node based on the transaction attributes of the transaction corresponding to each node of the dependency graph;

The transaction in the database is executed according to the dependency graph based on the behavior model of the ant colony, and the pheromone on each edge of the dependency graph is updated.

Furthermore, the step of constructing a dependency graph based on the execution association between transactions in the database includes:

Establishing a corresponding node based on each transaction in the database;

Based on the data flow relationship, timestamp information, value information, and submission order between the transactions corresponding to each of the nodes, the edges between the nodes are determined, and the edges are used to represent the association between the nodes.

Furthermore, based on the data flow relationship, timestamp information, value information, and submission order between the transactions corresponding to each node, the edges between the nodes are determined, specifically:

The data dependency relationship R1 between corresponding nodes is marked by recording data source, data destination and version information:

The control dependency relationship R2 between corresponding nodes is marked by recording the timestamp information of transactions or data:

By recording the transaction value information, the transaction priority dependency R3 between the corresponding nodes is marked:

The parallel execution relationship R4 between corresponding nodes is marked by recording the transaction submission order.

Furthermore, the step of determining the pheromone amount of the edge corresponding to two adjacent nodes based on the dependency relationship between the two adjacent nodes in the dependency graph includes:

Determine the data weight D1 corresponding to the data dependency R1, the control weight D2 corresponding to the control dependency R2, the priority weight D3 corresponding to the transaction priority dependency R3, and the parallel weight D4 corresponding to the parallel execution relationship R4;

Based on the initial pheromone quantity, the pheromone evaporation coefficient, the dependency relationship between the two adjacent nodes and the weight corresponding to each of the dependency relationships, the pheromone quantity of the edge corresponding to the two adjacent nodes is determined.

Furthermore, the determining of the heuristic information of each node based on the transaction attribute of the transaction corresponding to each node of the dependency graph includes:

Determine attribute heuristic information corresponding to each attribute in the transaction attribute;

Determine the weight corresponding to each attribute heuristic information;

Determining heuristic information of the transaction based on the respective attribute heuristic information and the weight;

A heuristic information mapping value is determined based on the heuristic information of the transaction and the maximum and minimum values of the heuristic information of each attribute, and the heuristic information mapping value is used as the heuristic information between the adjacent nodes.

Furthermore, the transaction attributes corresponding to each node include: node transaction resource utilization, node transaction execution time, node transaction priority, and node transaction waiting time.

Furthermore, the ant colony-based behavior model executes the transactions in the database according to the dependency graph and updates the pheromone on each edge of the dependency graph, specifically:

Based on the heuristic information of each node in the dependency graph and the pheromone amount of each edge, simulating an ant colony to concurrently execute transactions in the database;

The pheromone amount of the edge corresponding to the executed transaction is updated based on the completion quality of the executed transaction.

Furthermore, the pheromone quantity of the edge corresponding to the executed transaction is updated based on the completion quality of the executed transaction, and the formula adopted is:

It is the evaporation rate of pheromone, which is used to control the volatilization of pheromone and reduce the amount of pheromone.

is the pheromone increment of ant k through edge (i, j), and the pheromone increment is related to the quality of ant k's scheduling plan.

Claims (7)

1. A multi-core CPU concurrent transaction allocation method based on dependency graph, characterized in that the method includes: Construct a dependency graph based on the execution correlation between transactions in the database, each transaction in the database serves as a node in the graph, and the dependency relationship between transactions forms a directed edge in the graph; Determine the pheromone amount of the edge corresponding to the two adjacent nodes based on the dependency relationship between the two adjacent nodes in the dependency graph; Determine the heuristic information of each node based on the transaction metric attributes of the transactions corresponding to each node of the dependency graph; The ant colony-based behavioral model executes transactions in the database according to the dependency graph, and updates the pheromone amount of each edge on the dependency graph according to the execution results; The construction of a dependency graph based on execution correlations between transactions in the database includes: Establish a corresponding node based on each transaction in the database; Based on the data flow relationship, timestamp information, value information, and submission order between the transactions corresponding to each node, the edges between the nodes are determined, and the edges are used to represent the correlation between the nodes; specifically: : Mark the data dependencies between the corresponding nodes by recording the data source, data destination and version information R1: Mark the control dependencies between the corresponding nodes by recording the timestamp information of the transaction or data R2: Mark the corresponding nodes by recording the transaction value information The transaction priority dependency relationship R3 between them: the parallel execution relationship R4 between corresponding nodes is marked by recording the transaction submission order; Determining the pheromone amount of the edge corresponding to the two adjacent nodes based on the dependency relationship between the two adjacent nodes of the dependency graph includes: Determine the data weight D1 corresponding to the data dependency R1, the control weight D2 corresponding to the control dependency R2, the priority weight D3 corresponding to the transaction priority dependency R3, and the parallel weight D4 corresponding to the parallel execution relationship R4; Based on the initial pheromone amount, the pheromone evaporation coefficient, the dependence relationship between the two adjacent nodes and the weight corresponding to each of the dependence relationships, the pheromone amount of the edge corresponding to the two adjacent nodes is determined. 2. A multi-core CPU concurrent transaction allocation method based on a dependency graph as claimed in claim 1, characterized in that the heuristic information of each node is determined based on the transaction attributes of the transactions corresponding to each node of the dependency graph, including: Determine the attribute heuristic information corresponding to each attribute in the transaction attributes; Determine the weight corresponding to each attribute heuristic information; Determine heuristic information of the transaction based on the respective attribute heuristic information and the weight; A heuristic information mapping value is determined based on the heuristic information of the transaction, the maximum value and the minimum value of the heuristic information of each attribute, and the heuristic information mapping value serves as the heuristic information between adjacent nodes. 3. A multi-core CPU concurrent transaction allocation method based on a dependency graph according to claim 2, characterized in that the transaction attributes corresponding to each node include: node transaction resource utilization, node transaction execution time, node transaction priority Level, node transaction waiting time. 4. A multi-core CPU concurrent transaction allocation method based on a dependency graph as claimed in claim 1, characterized in that the ant colony-based behavioral model executes transactions in the database according to the dependency graph and updates all The pheromones on each edge of the dependence graph are as follows: Based on the heuristic information of each node in the dependency graph and the pheromone amount of each edge, simulate an ant colony to concurrently execute transactions in the database; The pheromone amount of the edge corresponding to the execution transaction is updated based on the completion quality of the execution transaction. 5. A multi-core CPU concurrent transaction allocation method based on a dependency graph as claimed in claim 4, characterized in that the pheromone amount of the edge corresponding to the execution transaction is updated based on the completion quality of the execution transaction. The formula is: ; It is the evaporation rate of pheromone, used to control the volatilization of pheromone and reduce the amount of pheromone; is the pheromone increment of ant k passing through edge (i, j), and the pheromone increment is related to the quality of ant k’s scheduling plan. 6. A multi-core CPU concurrent transaction allocation system based on a dependency graph, characterized in that the system includes: a dependency graph module, a pheromone module, a heuristic information module, and an update module; The dependency graph module is used to construct a dependency graph based on the execution correlation between transactions in the database. Each transaction in the database serves as a node in the graph, and the dependency relationship between transactions forms a directed edge in the graph. ; The pheromone amount module is configured to determine the pheromone amount of the edge corresponding to the two adjacent nodes based on the dependency relationship between two adjacent nodes of the dependency graph; The heuristic information module is used to determine the heuristic information of each node based on the transaction attributes of the transactions corresponding to each node of the dependency graph; The update module is configured to execute the transaction in the database according to the dependency graph based on the behavior model of the ant colony, and update the pheromone amount of each edge on the dependency graph according to the execution results; The dependency graph module is specifically used for: Establish a corresponding node based on each transaction in the database; Based on the data flow relationship, timestamp information, value information, and submission order between the transactions corresponding to each node, the edges between the nodes are determined, and the edges are used to represent the correlation between the nodes; specifically: : Mark the data dependencies between the corresponding nodes by recording the data source, data destination and version information R1: Mark the control dependencies between the corresponding nodes by recording the timestamp information of the transaction or data R2: Mark the corresponding nodes by recording the transaction value information The transaction priority dependency relationship R3 between them: the parallel execution relationship R4 between corresponding nodes is marked by recording the transaction submission order; Determining the pheromone amount of the edge corresponding to the two adjacent nodes based on the dependency relationship between the two adjacent nodes of the dependency graph includes: Determine the data weight D1 corresponding to the data dependency R1, the control weight D2 corresponding to the control dependency R2, the priority weight D3 corresponding to the transaction priority dependency R3, and the parallel weight D4 corresponding to the parallel execution relationship R4; Based on the initial pheromone amount, the pheromone evaporation coefficient, the dependence relationship between the two adjacent nodes and the weight corresponding to each of the dependence relationships, the pheromone amount of the edge corresponding to the two adjacent nodes is determined. 7. A database, characterized in that the database is provided with a memory and a processor, the memory is used to store a computer program, and the processor is used to call the computer program in the memory to perform the following steps: Construct a dependency graph based on the execution correlation between transactions in the database, each transaction in the database serves as a node in the graph, and the dependency relationship between transactions forms a directed edge in the graph; Determine the pheromone amount of the edge corresponding to the two adjacent nodes based on the dependency relationship between two adjacent nodes of the dependency graph; Determine the heuristic information of each node based on the transaction attributes of the transactions corresponding to each node of the dependency graph; The ant colony-based behavioral model executes transactions in the database according to the dependency graph, and updates the pheromone amount of each edge on the dependency graph according to the execution results; The construction of a dependency graph based on execution correlations between transactions in the database includes: Establish a corresponding node based on each transaction in the database; Based on the data flow relationship, timestamp information, value information, and submission order between the transactions corresponding to each node, the edges between the nodes are determined, and the edges are used to represent the correlation between the nodes; specifically: : Mark the data dependencies between the corresponding nodes by recording the data source, data destination and version information R1: Mark the control dependencies between the corresponding nodes by recording the timestamp information of the transaction or data R2: Mark the corresponding nodes by recording the transaction value information The transaction priority dependency relationship R3 between them: the parallel execution relationship R4 between corresponding nodes is marked by recording the transaction submission order; Determining the pheromone amount of the edge corresponding to the two adjacent nodes based on the dependency relationship between the two adjacent nodes of the dependency graph includes: Determine the data weight D1 corresponding to the data dependency R1, the control weight D2 corresponding to the control dependency R2, the priority weight D3 corresponding to the transaction priority dependency R3, and the parallel weight D4 corresponding to the parallel execution relationship R4; Based on the initial pheromone amount, the pheromone evaporation coefficient, the dependence relationship between the two adjacent nodes and the weight corresponding to each of the dependence relationships, the pheromone amount of the edge corresponding to the two adjacent nodes is determined.