[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

WO2022242401A1 - 一种数据库系统的事务处理方法、装置、电子设备、计算机可读存储介质及计算机程序产品 - Google Patents

一种数据库系统的事务处理方法、装置、电子设备、计算机可读存储介质及计算机程序产品 Download PDF

Info

Publication number
WO2022242401A1
WO2022242401A1 PCT/CN2022/087848 CN2022087848W WO2022242401A1 WO 2022242401 A1 WO2022242401 A1 WO 2022242401A1 CN 2022087848 W CN2022087848 W CN 2022087848W WO 2022242401 A1 WO2022242401 A1 WO 2022242401A1
Authority
WO
WIPO (PCT)
Prior art keywords
transaction
target
read
exception
write
Prior art date
Application number
PCT/CN2022/087848
Other languages
English (en)
French (fr)
Inventor
李海翔
Original Assignee
腾讯科技（深圳）有限公司
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 腾讯科技（深圳）有限公司 filed Critical 腾讯科技（深圳）有限公司
Priority to JP2023521163A priority Critical patent/JP2023546818A/ja
Priority to EP22803726.3A priority patent/EP4239475A4/en
Publication of WO2022242401A1 publication Critical patent/WO2022242401A1/zh
Priority to US18/072,629 priority patent/US20230107958A1/en

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46—Multiprogramming arrangements
    • G06F9/466—Transaction processing
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46—Multiprogramming arrangements
    • G06F9/466—Transaction processing
    • G06F9/467—Transactional memory
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/21—Design, administration or maintenance of databases
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/23—Updating
    • G06F16/2308—Concurrency control
    • G06F16/2315—Optimistic concurrency control
    • G06F16/2329—Optimistic concurrency control using versioning
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/23—Updating
    • G06F16/2365—Ensuring data consistency and integrity
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46—Multiprogramming arrangements
    • G06F9/48—Program initiating; Program switching, e.g. by interrupt
    • G06F9/4806—Task transfer initiation or dispatching
    • G06F9/4843—Task transfer initiation or dispatching by program, e.g. task dispatcher, supervisor, operating system
    • G06F9/4881—Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46—Multiprogramming arrangements
    • G06F9/50—Allocation of resources, e.g. of the central processing unit [CPU]
    • G06F9/5005—Allocation of resources, e.g. of the central processing unit [CPU] to service a request
    • G06F9/5027—Allocation of resources, e.g. of the central processing unit [CPU] to service a request the resource being a machine, e.g. CPUs, Servers, Terminals
    • G06F9/5038—Allocation of resources, e.g. of the central processing unit [CPU] to service a request the resource being a machine, e.g. CPUs, Servers, Terminals considering the execution order of a plurality of tasks, e.g. taking priority or time dependency constraints into consideration
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2209/00—Indexing scheme relating to G06F9/00
    • G06F2209/48—Indexing scheme relating to G06F9/48
    • G06F2209/481—Exception handling
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2209/00—Indexing scheme relating to G06F9/00
    • G06F2209/48—Indexing scheme relating to G06F9/48
    • G06F2209/484—Precedence
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2209/00—Indexing scheme relating to G06F9/00
    • G06F2209/50—Indexing scheme relating to G06F9/50
    • G06F2209/5021—Priority

Definitions

  • the present application relates to the field of database technology, and relates to a database system transaction processing method, device, electronic equipment, computer-readable storage medium and computer program product.
  • Embodiments of the present application provide a database system transaction processing method, device, electronic equipment, computer-readable storage medium, and computer program product, which can improve the transaction processing efficiency of the database system.
  • An embodiment of the present application provides a transaction processing method of a database system, the method comprising:
  • Determine the concurrent transaction of the target transaction, the concurrent transaction and the target transaction include read and write operations acting on the same variable, and the target transaction is a transaction to be committed;
  • the target transaction conflicts with the concurrent transaction, based on the same effect of the target transaction and the concurrent transaction.
  • the number of version changes of the variable and the target variable list determine the type of data exception, and the target variable list includes the same variable acted on by the target transaction and the concurrent transaction.
  • An embodiment of the present application provides a transaction processing device, which includes:
  • the first determination module is configured to determine a concurrent transaction of the target transaction, the concurrent transaction and the target transaction include read and write operations acting on the same variable, and the target transaction is a transaction to be committed;
  • the second determination module is configured to obtain a first intersection between the read set of the target transaction and the write set of the concurrent transaction, and obtain a first intersection between the write set of the target transaction and the read set of the concurrent transaction The second intersection; when at least one of the first intersection and the second intersection is a non-empty data set, and the target transaction conflicts with the concurrent transaction, based on the target transaction and the concurrent transaction.
  • the number of version changes of the same variable acted on and the target variable list determine the data exception type, and the target variable list includes the same variable acted on by the target transaction and the concurrent transaction.
  • An embodiment of the present application provides an electronic device.
  • the electronic device includes a processor and a memory, and the memory is used to store at least one computer program.
  • the at least one computer program is loaded and executed by the processor, the electronic device provided by the embodiment of the present application is realized The transaction processing method of the database system.
  • An embodiment of the present application provides a computer-readable storage medium, and at least one computer program is stored in the computer-readable storage medium.
  • the database system provided by the embodiment of the present application is implemented. transaction processing method.
  • An embodiment of the present application provides a computer program product, where the computer program product includes a computer program or an instruction.
  • the computer program or instruction is executed by a processor, the transaction processing method of the database system provided by the embodiment of the present application is implemented.
  • the beneficial effects brought by the technical solution provided by the embodiment of the present application at least include: after determining the concurrent transaction of the target transaction, the first intersection between the read set of the target transaction and the write set of the concurrent transaction and the In the second intersection between the write set and the read set of the concurrent transaction, if there is a non-empty data set, it is judged whether the target transaction conflicts with the concurrent transaction. If the target transaction conflicts with the concurrent transaction, the The same variable and the number of version changes of the same variable acted by the transaction are used to determine the data anomaly type; in this way, it is possible to confirm whether the target transaction and the concurrent transaction actually constitute a conflict during the execution of the target transaction. The same variable is used to determine the type of data anomaly, which can identify various data anomalies in the database system and ensure the consistency of the data state, thereby improving the transaction processing efficiency of the database system.
  • FIG. 1 is a schematic diagram of an implementation environment of a transaction processing method provided according to an embodiment of the present application
  • FIG. 2 is a schematic diagram of a conflict ring diagram provided according to an embodiment of the present application.
  • FIG. 3 is a schematic diagram of another conflict ring diagram provided according to an embodiment of the present application.
  • FIG. 4 is a schematic diagram of another conflict ring diagram provided according to an embodiment of the present application.
  • FIG. 5 is a flowchart of a transaction processing method provided according to an embodiment of the present application.
  • FIG. 6 is a flowchart of another transaction processing method provided according to an embodiment of the present application.
  • FIG. 7 is a schematic diagram of a cell data abnormality CCG diagram provided according to an embodiment of the present application.
  • FIG. 8 is a schematic diagram of a dual-data abnormal CCG diagram provided according to an embodiment of the present application.
  • FIG. 9 is a schematic diagram of a multivariate data abnormality CCG diagram provided according to an embodiment of the present application.
  • FIG. 10 is a schematic diagram of acquiring a target conflict ring diagram according to an embodiment of the present application.
  • Fig. 11 is a schematic structural diagram of a transaction processing device provided according to an embodiment of the present application.
  • Fig. 12 is a schematic structural diagram of a server provided according to an embodiment of the present application.
  • first and second are used to distinguish the same or similar items with basically the same function and function. It should be understood that “first”, “second”, ..., “seventh” "There is no logical or timing dependency between them, and there is no limitation on the number and execution order. It should also be understood that although the following description uses the terms first, second, etc. to describe various elements, these elements should not be limited by the terms.
  • first transaction could be termed a second transaction, and, similarly, a second transaction could be termed a first transaction, without departing from the scope of the various examples.
  • Both the first transaction and the second transaction may be transactions, and in some cases, separate and distinct transactions.
  • At least one refers to one or more than one.
  • at least one transaction may be any integer number of transactions greater than or equal to one, such as one transaction, two transactions, or three transactions.
  • a plurality refers to two or more, for example, a plurality of transactions may be any integer number of transactions greater than or equal to two such as two transactions or three transactions.
  • Cloud Technology refers to a hosting technology that unifies a series of resources such as hardware, software, and network in a wide area network or a local area network to realize data calculation, storage, processing, and sharing, that is, a business model based on cloud computing
  • the general term for applied network technology, information technology, integration technology, management platform technology and application technology, etc. can form a resource pool, which can be used on demand and is flexible and convenient.
  • the transaction processing method of the database system (hereinafter simply referred to as the transaction processing method) provided in the embodiment of the present application may be implemented based on cloud technology.
  • Cloud Storage It is a new concept extended and developed from the concept of cloud computing.
  • Distributed cloud storage system (hereinafter referred to as storage system) refers to the functions of cluster application, grid technology and distributed storage file system.
  • a storage system that integrates a large number of different types of storage devices (storage devices are also called storage nodes) in the network to work together through application software or application interfaces, and jointly provide data storage and service access functions.
  • the transaction processing method provided by the embodiment of the present application can be applied to cloud storage to identify anomalies in the cloud storage.
  • Database system An electronic file cabinet, that is, a place where electronic files are stored. Users can perform operations such as adding, querying, updating, and deleting data in files.
  • database system is a data collection that is stored together in a certain way, can be shared with multiple users, has as little redundancy as possible, and is independent of the application program.
  • the transaction processing method provided by the embodiment of the present application can be applied to a database system to identify anomalies in the database system.
  • the database system involved in the embodiment of the present application may be a stand-alone database system, a stand-alone transaction-based database system, a stand-alone analysis-based database system that requires transaction processing capabilities, and may generally refer to a non-relational database (Non -relational SQL, NoSQL) system can also be a distributed database system, a distributed big data processing system, for a distributed database system, when different variables are distributed and stored on different physical nodes, it corresponds to the consistency of the data state When there are two or more variables in the model, the data state consistency model and the corresponding transaction processing flow will be described in detail in the subsequent description.
  • the database system may include at least one node device, and multiple data tables may be stored in the database of each node device, and each data table may be used to store one or more data items (also called variable versions).
  • the database of the node device can be any type of distributed database, and can include at least one of a relational database or a non-relational database, such as a Structured Query Language (Structured Query Language, SQL) database, NoSQL, generally referring to various A new type of scalable/high-performance database (NewSQL), etc., and the type of database is not limited in the embodiment of the present application.
  • a relational database such as a Structured Query Language (Structured Query Language, SQL) database, NoSQL, generally referring to various A new type of scalable/high-performance database (NewSQL), etc.
  • NewSQL scalable/high-performance database
  • blockchain system a database system based on blockchain technology
  • the above-mentioned blockchain system is essentially a decentralized distributed
  • the database system uses a consensus algorithm to keep the ledger data recorded by different node devices on the blockchain consistent, and uses a cryptographic algorithm to ensure the encrypted transmission of ledger data between different node devices and cannot be tampered with.
  • the script system is used to expand the ledger function. Network routing To perform interconnection between different node devices.
  • the blockchain system can include one or more blockchains.
  • the blockchain is a series of data blocks associated with cryptographic methods. Each data block contains a batch of network transaction information for Verify the validity of its information (anti-counterfeiting) and generate the next block.
  • Node devices in the blockchain system can form a peer-to-peer (Peer To Peer, P2P) network.
  • the P2P protocol is an application layer protocol that runs on top of the Transmission Control Protocol (TCP).
  • TCP Transmission Control Protocol
  • any node device can have the following functions.
  • Routing the basic function of node devices, used to support communication between node devices;
  • Application used to deploy in the blockchain, realize specific business according to actual business needs, record the data related to the realization function to form ledger data, carry digital signature in the ledger data to indicate the data source, and send the ledger data to the district
  • Other node devices in the block chain system are used for other node devices to add ledger data to temporary blocks when they verify the source and integrity of the ledger data successfully; among them, the business implemented by the application can include wallets, shared ledgers and smart contracts, etc. ;
  • Block chain including a series of blocks that are connected to each other in chronological order. Once a new block is added to the block chain, it will not be removed again.
  • the block records the submission of node devices in the block chain system. account data.
  • each block may include the hash value of the transaction records stored in this block (the hash value of this block) and the hash value of the previous block, and each block is formed by connecting the hash values Blockchain; in addition, the block can also include information such as the time stamp when the block was generated.
  • the transaction isolation level is defined by whether certain data anomalies can be avoided, and the data anomalies that may be involved include: A. Dirty read, which means that one transaction reads data items that have not yet been committed by another transaction; B. Non-repeatable read means that a transaction repeatedly reads the same data item twice but gets different results; C, phantom read means that the transaction performs two predicate queries (range queries) during the operation, and the result of the second query Contains data items that did not appear in the results of the first query or are missing data items that appeared in the results of the first query.
  • A. Dirty read which means that one transaction reads data items that have not yet been committed by another transaction
  • B. Non-repeatable read means that a transaction repeatedly reads the same data item twice but gets different results
  • C phantom read means that the transaction performs two predicate queries (range queries) during the operation, and the result of the second query Contains data items that did not appear in the results of the first query or are missing data items that appeared in
  • isolation levels including: a. Read uncommitted: allow the above ABC three data exceptions to occur; b. Read committed: Dirty reads are not allowed; c. Repeatable read: Dirty reads are not allowed, Non-repeatable reading occurs; d. Serializable: the above three data exceptions of ABC cannot occur. It is easy to know that these four isolation levels do not allow dirty write exceptions to occur. Dirty write exceptions mean that two uncommitted transactions modify the same data item. When the ANSI SQL standard was formulated, there were not many known types of data anomalies, and new data anomalies were discovered continuously.
  • data anomalies also include: lost update anomalies, read partial order anomalies, and write partial order anomalies. Anomalies, read-write partial order exceptions, sawtooth wave write partial order exceptions, serial-concurrent-phenomenon (Serial-Concurrent-Phenomenon) exceptions, cross-phenomenon (Cross-Phenomenon) exceptions, causal loss exceptions, causal reversal exceptions, old read exceptions, and Future read exceptions etc.
  • Anomalies read-write partial order exceptions, sawtooth wave write partial order exceptions, serial-concurrent-phenomenon (Serial-Concurrent-Phenomenon) exceptions, cross-phenomenon (Cross-Phenomenon) exceptions, causal loss exceptions, causal reversal exceptions, old read exceptions, and Future read exceptions etc.
  • Consistency In database technology, the word “consistency” can express two meanings, one refers to transaction consistency, and the other refers to distributed consistency.
  • the transactional consistency of the database is: under the operation of the transaction, the data state of the database changes from one consistent state to another consistent state.
  • the above "consistent state” refers to the data state that satisfies some rules predefined by the database system.
  • these rules can include constraints, cascades, triggers, and any combination of the three (belonging to the logical semantics of the data); write Partial order exceptions violate the constraints between specific data, where the constraints belong to the consistency of data defined by user semantics.
  • Concurrent access control technology in database transaction processing technology is used to discover and solve the problem of whether concurrent operations of transactions will cause data exceptions on data items and how to eliminate data exceptions.
  • ANSI SQL proposes four data exceptions and isolation levels.
  • Various concurrent access control algorithms have also been developed; for example, concurrent access control technology based on blocking, concurrent access control technology based on timestamp, concurrent access control technology based on multi-version concurrency control (Mutil-Version Concurrency Control, MVCC), based on Optimistic Concurrency Control (OCC) concurrent access control technology, etc.
  • the distributed consistency of the database is also called the operation consistency of shared data objects. It is a system-level meaning for the entire database system. It means that in order to ensure that the data is consistent in the database system, the database system is also required to meet two characteristics. One is Serializability (Serializability), the other is recoverability (Recoverability). Serializability refers to the above-mentioned serializable isolation level in isolation. Serializability guarantees the correctness of concurrent operations, while recoverability means that transactions that have been committed have never been read and rolled back. The data written by the transaction (meaning that dirty read exceptions will not occur), the recoverability ensures that the data returns to the previous consistent state after the transaction is rolled back, and the rolled back transaction will not affect the consistency of the data. The database The consistent state of the system is recoverable.
  • the database exceptions involved may include: dirty read data exception, dirty write data exception, non-repeatable read data exception, phantom read data exception, lost updated data exception, read partial sequence data exception, write partial sequence data exception, serial And find phenomenon data anomalies, cross phenomenon data anomalies, etc.
  • SSI Snapshot Isolation
  • PostgreSQL PostgreSQL
  • SSI technology can identify in advance the necessary and insufficient conditions that may cause a cycle in the dependency graph: a transaction has a read-write conflict entry edge and a read-write conflict exit edge; if any transaction satisfies the above conditions, it is considered that there is data abnormal.
  • cognitive fragmentation is not unified: blockade technology, dependency graph technology, and SSI technology have all separated the identification methods of each data anomaly, so that when identifying data anomalies, they can only recognize whether they meet each data anomaly one by one ; That is to say, it is impossible to use a unified perspective to identify and recognize these different types of data anomalies, resulting in complex and unclear cognitive thinking for data anomalies, with high complexity.
  • the cognition is limited and incomplete: none of the blockade technology, dependency graph technology, and SSI technology can exhaust whether there are unknown new data anomalies.
  • the data exception exists, it will bring losses to the entire database system; for example, when the database system is under the non-serializable isolation level, if there is a new data exception, it will cause a data inconsistency error in the system.
  • the embodiment of the present application provides a transaction processing method, provides a way to identify data anomalies and avoid data anomalies during transaction processing, and provides a general form of conflict ring diagram to define data anomalies.
  • the definition of data anomalies can be visualized; moreover, the classification of data anomalies can improve the transaction processing efficiency of the database system, which will be described in detail below.
  • FIG. 1 is a schematic diagram of an implementation environment of a transaction processing method provided by an embodiment of the present application.
  • the embodiment of the present application can be applied to a distributed database system in a database system, which may include a gateway server 101 (three gateway servers are shown in an example), a global time stamp generation cluster 102, a distributed Storage cluster 103 and distributed coordination system 104 (such as ZooKeeper);
  • a gateway server 101 three gateway servers are shown in an example
  • a global time stamp generation cluster 102 such as a distributed Storage cluster 103 and distributed coordination system 104 (such as ZooKeeper);
  • node devices 1 to m may be included, and each node device may be a data node device , and can also be a coordinating node device.
  • the gateway server 101 is used to receive external read and write requests, and distribute the read and write transactions corresponding to the read and write requests to the distributed storage cluster 103; for example, after the user logs in to the application client on the terminal, the application client is triggered to generate Read and write requests, calling the application programming interface (Application Programming Interface, API) provided by the distributed database system to send the read and write requests to the gateway server 101;
  • the API can be an API provided by any relational database system, such as , the API can be a MySQL API.
  • the gateway server 101 and any data node device or any coordinating node device in the distributed storage cluster 103 may be the same physical machine, that is, a certain data node device or coordinating node device The device also functions as the gateway server 101 .
  • the global timestamp generation cluster 102 is used to generate the global commit timestamp (Global Timestamp, Gts) of the global transaction.
  • the global transaction is also called a distributed transaction, which refers to a transaction involving multiple data node devices; for example, a global read transaction can It involves reading data stored on multiple data node devices. For another example, a global write transaction may involve writing data on multiple data node devices.
  • the global time stamp generation cluster 102 can be regarded as a single point logically, and can also provide higher availability through the architecture of one master and three slaves (respectively a master device and three auxiliary devices corresponding to the master device).
  • the service adopts the form of a cluster to realize the generation of the global submission timestamp; when a device in the one-master-three-slave architecture fails, the generation of the global submission timestamp can be continued through other devices in the one-master-three-slave architecture. In this way, single point of failure can be prevented, and the problem of single point of bottleneck can be avoided.
  • the global commit timestamp is a globally unique and monotonically increasing timestamp identifier in the distributed database system, which can be used to mark the order of global commit of each transaction, so as to reflect the The sequence relationship in real time (total sequence relationship of transactions), the global commit timestamp can use at least one of physical clock, logical clock, hybrid physical clock or hybrid logical clock (Hybrid Logical Clock, HLC), the embodiment of this application is not correct The type of global commit timestamp is qualified.
  • the global commit timestamp can be generated by mixing a physical clock, and the global commit timestamp can be composed of eight bytes, each byte includes eight bits, a total of 64 bits; wherein, the first 44 bits can be the physical timestamp Take the value (that is, the Unix timestamp, accurate to milliseconds), so that a total of 244 unsigned integers can be represented, so in theory, a total of about 557.8 can be represented
  • the physical timestamp of the year; among them, the last 20 digits can be monotonically increasing counts within a certain millisecond, so that there are 2 20 (about 1 million) counts per millisecond.
  • the number of global commit timestamps represents the total number of transactions that the system can theoretically support, based on The above data structure, in theory, the system can support (2 44 -1)*2 20 transactions.
  • the number of digits in the global commit timestamp can be extended to support more nodes and transactions. The embodiment of this application does not limit the definition method of the global commit timestamp.
  • the global timestamp generation cluster 102 may be physically independent, or may be merged with the distributed coordination system 104 .
  • the distributed storage cluster 103 may include a data node device and a coordinating node device, and each coordinating node device may correspond to at least one data node device, and the data node device and the coordinating node device are divided based on different transactions; Take a global transaction as an example.
  • the originating node of the global transaction can be called a coordinating node device, and other node devices involved in the global transaction are called data node devices.
  • the number of data node devices or coordinating node devices can be one or more. The embodiment of the application does not limit the number of data node devices or coordination node devices in the distributed storage cluster 103 .
  • the organization distributed transaction specification eXtended Architecture, XA
  • two-phase commit Two-Phase Commit, 2PC
  • the coordinating node device is equivalent to the coordinator in the 2PC algorithm
  • each data corresponding to the coordinating node device Node devices are equivalent to participants in the 2PC algorithm.
  • each data node device or coordinating node device can be a stand-alone device, and can also adopt a master-standby structure (that is, a master-multiple-standby cluster); as shown in Figure 1, the node device (data Node device or coordinating node device) is an example of a master and two backup clusters.
  • Each node device includes a master and two backup devices.
  • Each master or backup device is equipped with an agent (Agent) device. It can be a different physical device from the main machine or the standby machine.
  • the agent device can also be used as an agent module on the main machine or the standby machine; taking node device 1 as an example, node device 1 includes a main database and an agent device (main Database+Agent , referred to as the main DB+A gent), and also includes two standby databases and agent devices (standby Database+A gent, referred to as standby DB+A gent).
  • main Database+Agent referred to as the main DB+A gent
  • standby Database+A gent standby Database+A gent
  • the set of database instances of the master or backup corresponding to each node device is called a set (SET); for example, if a node device is a stand-alone device, then the SET of the node device is only the Database instance, assuming that a node device is a master and two backup clusters, then the SET of the node device is a collection of the master database instance and the two backup database instances; at this time, the data of the host can be guaranteed based on the strong synchronization technology of the cloud database. Consistency with the copy data of the standby machine; here, each SET can be linearly expanded to meet the business processing requirements in big data scenarios. In some financial business scenarios, global transactions usually refer to transfers across SETs.
  • the distributed coordination system 104 can be used to manage at least one of the gateway server 101, the global timestamp generation cluster 102 or the distributed storage cluster 103; in the embodiment of this application, it can be accessed through the scheduler (Scheduler) on the terminal
  • the distributed coordination system 104 controls the back-end distributed coordination system 104 based on the front-end scheduler to realize the management of each cluster or server.
  • the scheduler may be used to control ZooKeeper to delete a certain node device from the distributed storage cluster 103, that is, to make a certain node device invalid.
  • the above Figure 1 provides a lightweight global transaction processing architecture diagram, which is a kind of distributed database system.
  • the entire distributed database system can be regarded as jointly maintaining a logical data table.
  • the data stored in this data table is scattered to each node device in the distributed storage cluster 103 through the primary key.
  • the data stored on each node device Data is independent of other node devices, thus realizing the horizontal segmentation of node devices to logical data tables. Since in the above system, each data table in each database can be horizontally segmented and then stored in a distributed manner, this system can also be called a "sub-database and sub-table" architecture.
  • the distributed sub-table architecture shown in Figure 1 is a local transaction manager, not a global transaction manager. Therefore, there is also the problem of data consistency during read operations; and the transaction processing method provided by the embodiment of the present application can realize distributed transaction processing, and by constructing a lightweight, decentralized distributed transaction processing mechanism, it can provide distributed
  • the distributed database system provides capabilities such as horizontal expansion, which improves the application scope of the distributed database system, and then can solve the atomicity and consistency of data during write operations, and the consistency of data during read operations, thereby improving transaction processing efficiency.
  • the transaction processing method provided by the embodiment of the present application can be applied to the above-mentioned distributed database system using the sub-database and sub-table architecture; for example, the distributed database system is a distributed transactional database system, and of course it can also be a distributed relationship
  • the transaction processing method provided by the embodiment of the present application can also be applied to some stand-alone database systems; when the transaction processing method provided by the embodiment of the present application is applied to a distributed database system, distributed transaction processing can be realized, And it can improve transaction processing efficiency through flexible isolation levels.
  • the distributed database system composed of the above-mentioned gateway server 101, global timestamp generation cluster 102, distributed storage cluster 103, and distributed coordination system 104 can be regarded as a server that provides data services to user terminals
  • the server can be an independent physical server, or a server cluster or distributed system composed of multiple physical servers, or it can provide cloud services, cloud databases, cloud computing, cloud functions, cloud storage, network services, cloud communication Cloud servers for basic cloud computing services such as middleware services, domain name services, security services, content delivery network (Content Delivery Network, CDN), and big data and artificial intelligence platforms.
  • the above-mentioned user terminal may be a smart phone, a tablet computer, a notebook computer, a desktop computer, a smart speaker, a smart watch, etc., but is not limited thereto.
  • the terminal and the server may be connected directly or indirectly through wired or wireless communication, which is not limited in this application.
  • Transaction It is a logical unit in the process of performing operations of the database management system. It is composed of a limited sequence of database operations and is the smallest execution unit of database system operations.
  • a variable a transaction is a data unit in a database relational system, and a variable is an actor of a database operation (or an operated data object); in some embodiments, a variable is also called a data item.
  • a variable can be a tuple (Tuple) or a record (Record), or a page (Page) or a table (Table) object, etc.
  • a variable can contain several variable versions (referred to as "versions"). Whenever a transaction updates the variable, a new variable version will be added. Each variable version of the variable can be identified by a natural number as the version number. The larger the version number, the Indicates that the variable version is newer.
  • a database operation consists of three parts: operation type, transaction, and variable version; among them, the operation type can include two types: read (Read, R) and write (Write, W).
  • the transaction T i reads the variable x and generates a new version x m of the variable x.
  • the above read operation can be recorded as R i [x m ]; another example, the transaction T j updates the variable y and generates the new version of the variable y
  • the above write operation can be recorded as W j [y n ]; where i and j are natural numbers, respectively the transaction numbers to which the corresponding operation belongs, and m and n are natural numbers, respectively the version numbers of the corresponding variables.
  • O can also be used to represent an operation.
  • Serialization is a scheduling, which can also be understood as the execution method between multiple transactions; the execution of multiple transactions has a sequence, if there are no variables that are jointly operated between transactions, then the It doesn't matter if the order of execution between transactions is replaced before and after; but if there are variables with common operations between transactions, the order of execution between transactions needs to be distinguished; for multiple concurrently executed transactions with variables with common operations, if the execution results "Equivalent” to a "serializable schedule", then this schedule is a "serializable schedule”. Satisfying "serializable scheduling” has serializable properties. Therefore, serialization ensures that the execution order of multiple concurrent transactions has no effect on data consistency.
  • Each transaction in the database system has two transaction data sets, namely the write set of the transaction and the read set of the transaction, which means: the write set DSW(T) is used to store the new data version written by the transaction T, Read set DSR(T) is used to store the data version read by transaction T.
  • the transaction processing method provided by the embodiment of the present application operates on the basis of the data state consistency model (also referred to as "data state model").
  • the embodiment of the present application is based on the theory of conflict serialization, and the Unification is carried out, and a general form of conflict ring diagram is provided, which is used to represent the relationship between transactions and the variables affected by the read and write operations corresponding to the transactions.
  • the basic concepts involved in this application are introduced below.
  • Scheduling refers to a sequence composed of multiple operations of a group of transactions, denoted as s. All transactions in a schedule s are recorded as TS(s), all operations in a schedule s are recorded as O(s), and all sets of variables with version numbers in a schedule s are recorded as VS(s).
  • schedule s R 1 [x 0 ]R 2 [y 0 ]W 3 [x 1 ]W 4 [y 1 ]R 2 [x 1 ]R 1 [y 1 ], which means that the operation sequence of this schedule s comes from 4 transactions, namely TS ⁇ T 1 , T 2 , T 3 , T 4 ⁇ , involve 2 variables x and y, and the variables x and y have two versions respectively.
  • conflict is also called conflict operation.
  • conflict operations When two operations meet the following three conditions, the two operations are called conflict operations. Among them, the three conditions are: 1) the two operations belong to different transactions; 2) at least one operation is a write operation; 3) the objects operated by the two operations are the same object (read the same object or write the same object) , in this embodiment of the application, an object is also called a variable.
  • O i [x m ]O j [x n ] belongs to R i [x m ]W j [x m +1], W i [x m ]R j [x m ] and W i [x m ]W j [x m + 1] any one of the three conflicts, then O i [x m ]O j [x n ] is called a conflict, and the conflict constitutes a partial order relationship between Oi and Oj, which will be included in the scheduling s
  • the set of all conflicts is denoted as conf(s).
  • the above three types of conflicts may be abbreviated as RW, WR, and WW respectively in turn.
  • conflict Equivalence For different schedules s and s′, if the following two conditions are met, then s and s′ are called conflict equivalence. Among them, two conditions are: 1) schedule s and s′ include the same set of transactions, that is, the order of operations in each transaction is fixed and cannot change under different schedules; 2) schedule s and s ' includes the same set of conflicts.
  • CCG conflict Cycle Graph
  • V VS(s), expressed as a vertex set of the CCG graph, the elements in the vertex set are called vertices, and a vertex corresponds to a transaction; among them, a vertex T i satisfies T i ⁇ TS(s);
  • E is a subset of V ⁇ V, which can also be called an edge set.
  • the elements in this edge set are called directed edges, which are denoted as ⁇ T i , T j >, and can also be called edges for short. Among them, Therefore, the directed edge may also be recorded in a form similar to the above "conflict". For example, the directed edge is recorded as W i [x m ]W j [x m+1 ], which is not limited in this embodiment of the present application.
  • the CCG graph is a A graph composed of circles.
  • FIG. 2 is a schematic diagram of a conflict ring graph provided in an embodiment of the present application.
  • T 1 and T 2 in the figure are the vertices of the conflict ring graph 2-1, and T 1 and T 2 are connected by two edges to form a conflict ring graph; where the two edges represent for R 1 [x 0 ] W 2 [x 1 ] and W 2 [x 1 ] R 1 [x 1 ].
  • a conflict ring graph has at least two edges.
  • the conflict ring graph has only one edge, there are only two transactions in the conflict ring graph, and these two transactions are serial transactions, so they will not form a directed ring; if there are two edges forming a directed ring , for example, the first edge in the conflict cycle makes T i happen before T j , and the second edge in the conflict cycle makes T j happen before T i , that is, there is no equivalent possible Serialized scheduling, the two transactions T i and T j conflict.
  • a conflict ring graph has at most infinite edges.
  • an infinite number of transactions may exist in the TS(s) corresponding to a schedule s, and correspondingly, an infinite number of vertices may exist in a conflict ring graph, that is, an infinite number of edges may exist.
  • a vertex v i satisfies vi ⁇ VS(s), and the vertex is composed of two types of data, One is the transaction identification (Identification, ID), and the other is a list (List), which is used to store different versions of variables.
  • E is a subset of V ⁇ V, which can also be called an edge set.
  • the elements in this edge set are called directed edges.
  • edges are divided into the following two types. For the following two types of edges, they are uniformly expressed is ⁇ V i , V j >, such an edge is derived from the equivalent deformation of the edge of the CCG graph, so it belongs to the deformation of the conflict operation. The two sides are described separately below.
  • the first type of edge is a consistent state edge, denoted as ⁇ x m , y n >, referred to as a transaction edge E T .
  • Edges of this type include operations of the same transaction, so the data state within the transaction satisfies the consistency requirement.
  • x y and m ⁇ n; or x ⁇ y. Since the CCSG graph is equivalent to the CCG graph, the consistent state edge can also be expressed as R i [x m ]R i [y n ], and E T can be used as the label of the edge.
  • the second type of edge is the state transition edge, denoted as ⁇ xi , xi+1 >, referred to as the state edge E S .
  • This type of edge is composed of a variable written by a write transaction, resulting in a change in the data state, so the version of the variable changes. Since the CCSG graph is equivalent to the CCG graph, the consistent state edge can also be expressed as W j [x m+1 ].
  • V 1 ⁇ E 1 ⁇ V 2 ⁇ E 2 ...V k ⁇ E k ⁇ V 1 is a graph composed of a directed cycle.
  • the first is an edge split.
  • any edge of the CCG graph consists of two operations, that is, a conflict, which can be split into two separate edges.
  • the edge splitting methods include the following three types, each of which splits into two sub-edges, and the three splitting methods are described below.
  • an edge is expressed as R 1 [x 0 ]W 2 [x 1 ], split this edge to get R 1 [x 0 ] and W 2 [x 1 ], and get two versions of the variable x at the same time x 0 and x 1 .
  • an edge is expressed as W 2 [y 1 ] R 3 [y 1 ], split this edge to get W 2 [y 1 ] and R 3 [y 1 ], and get a version y of the variable y 1 .
  • an edge is expressed as W 3 [z 1 ] W 1 [z 2 ], split this edge to get W 3 [z 1 ] and W 1 [z 2 ], and get two versions of the variable z at the same time z 1 and z 2 .
  • the second one is vertex transformation.
  • the version of the variable is used as the vertex of the CCSG graph, that is, the version in the previous step is converted into a vertex; here, taking the vertex obtained in the first example above as an example, the vertices of the CCSG graph include x 0 , x 1 , y 1 , z 1 and z 2 .
  • Multiple versions of the same variable are arranged vertically, and versions of different variables affected by the same transaction are arranged horizontally.
  • the vertical direction can refer to the horizontal direction corresponding to the information displayed on the screen, or it can refer to the direction corresponding to the information displayed on the screen.
  • the horizontal direction, the vertical direction, etc. are not limited in the embodiment of this application; however, the arrangement direction of multiple versions of the same variable is relative to the arrangement direction of the versions of different variables that have been affected by the same transaction of. It should be noted that there is no specific requirement for the arrangement of vertices here, and in some embodiments, they may also be arranged in other arrangements, which are not limited in this embodiment of the present application.
  • the third is to add edges between vertices corresponding to the same variable in adjacent versions.
  • the transition relationship between the new vertices obtained by the second item above is the new edge of the CCSG graph.
  • the relevant sub-edges of the aforementioned transaction T 2 include: W 2 [x 1 ] and W 2 [y 1 ], then x 1 and y 1 are paralleled horizontally, so that there is a line W 2 [ x 1 ] side.
  • the fourth is to add edges between vertices corresponding to variables that act on the same transaction. Among them, between the same transaction, construct the consistent state edge of the CCSG graph. For example, continuing to take the aforementioned vertex as an example, an edge is added between x 1 and y 1 , and the label of the edge is transaction T 2 .
  • the first one is vertex merging.
  • the variables operated by the same transaction are merged into one vertex, and the vertex is named as the transaction identifier of the transaction.
  • the representation of the vertex is equivalent to the vertex representation of the aforementioned CCG graph. Repeat the description again.
  • the second is to add edges between adjacent vertices; it includes the following two points, the first point is to preserve the state transition of variables. For example, from the edge R 1 [x 0 ]W 2 [x 1 ], it can be seen that the state transition of the variable is from T 1 to T 2 , so the added new edge is T 1 ⁇ T 2 .
  • the second point is that if no write operation occurs, new edges are constructed according to the conflict relationship that occurred in the original CCG graph. It should be noted that it is applied to the situation where there is a WR conflict relationship. In the case of a WR conflict relationship, the corresponding edge is from the transaction where W is to the transaction where R is.
  • the third point is that the obtained CCG graph has a cycle, and its directed attribute can be ignored, that is, the CCG graph obtained by converting the CCSG is an undirected cyclic graph.
  • the CCSG graph is the basis of the data state consistency model. That is to say, the graph composed of the version of the variable as the vertex, the read and write operations of the transaction as the edge of the state transition or the edge of the consistent state of the transaction as the edge, is the data state consistency model.
  • this data state consistency model if there is a ring, there is a data anomaly, and if there is no ring, there is no data anomaly.
  • Data anomalies (Data Anomalies, DA); in a schedule s, if there is a sub-schedule s′, that is And s' has a conflict ring graph, it is said that there is a data anomaly in scheduling s, and s' is a specific data anomaly.
  • a data anomaly corresponds to a subset of the schedule s in which the conflict ring graph exists, so a fine-grained data anomaly can be represented by an expression that constitutes the subset of the schedule s in the conflict ring graph.
  • FIG. 3 is a schematic diagram of another conflict ring graph provided by an embodiment of the present application.
  • V ⁇ T 1 , T 2 ⁇
  • E ⁇ R 1 [x 0 ]W 2 [x 1 ]>, ⁇ W 2 [x 1 ]W 1 [x 2 ]> ⁇
  • the formal definition of the lost update exception is R i [x m ]...W j [x m+1 ]...W i [x m+2 ].
  • the conflict ring diagram corresponding to the read partial order anomaly refers to FIG. 4 .
  • Rollback rate when blocking technology is used to suppress concurrency and avoid data anomalies, transactions that could have been committed are rolled back, that is, false rollbacks.
  • the rollback information involved in the embodiment of the present application will be described respectively below.
  • Data abnormal rollback for scheduling s, when the transaction is rolled back due to data abnormality, it is called data abnormal rollback, also known as True Rollback (True Rollback, TR).
  • Algorithm rollback for scheduling s, when there is no data exception, it is determined that data inconsistency may occur through the concurrent access algorithm, and the resulting transaction rollback is called algorithm rollback, also known as false rollback (False Rollback) , FR).
  • False rollback rate Assuming that among the P schedules, if each of the V schedules has a false rollback, then V/P is called the false rollback rate.
  • the false rollback rate reflects the concurrent execution capability of concurrent transactions. The lower the false rollback rate, the higher the concurrency, and the higher the utilization rate of computing resources, the higher the transaction concurrency efficiency.
  • Table 1 describes some symbols and corresponding meanings involved in the embodiment of the present application.
  • Fig. 5 is a flow chart of a transaction processing method provided by the embodiment of the present application.
  • the transaction processing method provided by the embodiment of the present application is applied to any node device in the database system.
  • the node device may be a stand-alone device;
  • the node device may be a coordinating node device or a data node device;
  • the embodiment of the present application includes step 501 and step 502, and the following steps are respectively performed illustrate.
  • Step 501 the node device determines the concurrent transaction of the target transaction, the concurrent transaction and the target transaction include read and write operations acting on the same variable, and the target transaction is a transaction to be committed.
  • the target transaction is a global transaction or a local transaction; wherein, the global transaction refers to a transaction involving cross-node operations, and a global transaction is also called a distributed transaction; while a local transaction refers to a transaction involving only a single Node-operated transactions, local transactions are also referred to as local transactions; the embodiment of the present application does not limit the type of target transactions.
  • the read/write operation refers to at least one of a read operation and a write operation.
  • the target transaction can be initiated by the terminal.
  • the terminal and the node device establish a session for processing the target transaction.
  • the terminal sends the execution request of the target transaction to the node device.
  • the node device responds to the execution request of the target transaction and starts to execute the target transaction. .
  • a session has been established between the terminal and the node device, there is no need to establish a new session between the two, and only the currently established session needs to be reused.
  • Step 502 the node device obtains the first intersection between the read set of the target transaction and the write set of the concurrent transaction, and obtains the second intersection between the write set of the target transaction and the read set of the concurrent transaction, when the first intersection and the At least one of the two intersections is a non-empty data set, and the target transaction conflicts with the concurrent transaction, based on the number of version changes and the target variable list of the same variable affected by the target transaction and the concurrent transaction, determine the data exception type, the target variable list Include the same variables that target transactions and concurrent transactions act on.
  • the conflict between the target transaction and the concurrent transaction means that at least two operations between the target transaction and the concurrent transaction are conflicting operations. If the target transaction is committed at this time, data exceptions will occur in the database system.
  • the node device determines that at least one of the first intersection and the second intersection is a non-empty data set, and the target transaction conflicts with the concurrent transaction, based on the number of version changes and the target variable list, determine the data exception type and send the data Exception type is reported.
  • the non-empty data set refers to a data set that is not an empty set, that is, a data set that includes set elements.
  • the node device determines the concurrent transaction of the target transaction
  • the first intersection between the read set of the target transaction and the write set of the concurrent transaction and the write set of the target transaction In the second intersection with the read set of the concurrent transaction, if at least one item is not empty, judge whether the target transaction conflicts with the concurrent transaction. If the target transaction conflicts with the concurrent transaction, then based on the two The same variables that are affected by the transaction and the number of version changes of the same variables are used to determine the type of data exception.
  • This method can confirm whether the target transaction and the concurrent transaction really constitute a conflict during the execution of the target transaction; and, by using the same variable that the two transactions act to determine the type of data anomaly, it can be identified based on the serialization theory
  • Various data exceptions in the database system ensure the consistency of the data state and improve the transaction processing efficiency of the database system.
  • FIG. 5 is a brief description of the transaction processing method provided in the present application.
  • the transaction processing method provided in the embodiment of the present application will be described in detail below in conjunction with FIG. 6 .
  • Figure 6 is a flow chart of another transaction processing method provided by the embodiment of the present application. As shown in Figure 6, the transaction processing method provided by the embodiment of the present application is applied to any node device in the database system.
  • the node device When the database system is a stand-alone database system, the node device can be a stand-alone device; when the database system is a distributed database system, the node device can be a coordinating node device or a data node device; the embodiment of the present application includes the following steps 601 to 609, the following for each The steps are explained separately.
  • Step 601 the node device initializes the read set and write set of the target transaction in response to the execution instruction of the target transaction.
  • the node device initializes the read set and write set of the target transaction to an empty set in response to the execution instruction of the target transaction, and assigns a globally unique transaction ID, that is, a transaction identifier, to the target transaction.
  • a globally unique transaction ID that is, a transaction identifier
  • the transaction IDs of different transactions are incremented according to the order in which the node device receives the corresponding execution instruction. For example, the node device receives the execution instruction of the target transaction at time t1, and the transaction ID of the target transaction is named 1000. If the node device When receiving an execution instruction of another transaction at time t2, the node device names the transaction ID of the other transaction as 1001, which is not limited in this embodiment of the present application.
  • the operating system of the node device allocates a memory space, which is used to maintain the read set and write set of at least one transaction; when the target transaction At the beginning of execution, the node device applies for a block of memory from the memory space, which is used to manage the read set and write set of the target transaction, so that the creation of the read set and write set of the target transaction is completed on the node device, and, Initialize the created read set and write set as empty sets.
  • the update strategy for the read set and write set of the target transaction is introduced below.
  • the node device determines whether the target transaction involves the update operation of the variable according to the execution statement of the target transaction. When it is determined that the update operation of the variable is involved, the node device responds to the target transaction. Any variable is updated, the variable is added to the write set of the target transaction, and a version number is assigned to the variable. For example, when a certain transaction T updates the variable x, the variable x is added to the write set of the transaction T, and a version number is assigned to the variable x. The version number of the write operation of the same variable by different transactions is incremented by an integer; at this time, the node device can obtain the version number of the variable by performing a read operation. That is, the database system maintains an incremental version number for each variable. In addition, when the node device reads any variable according to the execution statement of the target transaction, the read variable is the latest variable that satisfies the read-committed rule.
  • the above update strategy can also be understood as the read set and write set of the target transaction are maintained in real time as the transaction operation proceeds. If a read operation occurs, the read variable enters the read set; if a write operation occurs, the read variable enters the write set. If the same transaction writes the same variable multiple times, there are multiple different new versions, and the latest variable version is used to replace the old variable version in the write set.
  • this step 601 is the process of forming the transactional read set and write set involved in the above step 501, which is the step of forming the transactional read-write set in the read-write phase.
  • Step 602. The node device acquires at least one candidate concurrent transaction of the target transaction in response to the execution instruction of each operation in the target transaction.
  • the operation for each operation of the target transaction (the operation can be a read operation or a write operation), when the operation occurs, it enters the preparation phase, and the node device enters the critical area to traverse the read and write operations of the target transaction. set and write set, and obtain the transaction ID of at least one candidate concurrent transaction (such as all concurrent transactions) of the target transaction, and store the transaction ID of the at least one candidate concurrent transaction into a linked list (Typescript, TS).
  • a linked list Typescript, TS
  • each variable in the memory records the transaction ID of the transaction that has read and written the variable but has not yet committed (referred to as the active transaction ID)
  • the active transaction ID recorded on each variable can be one, or multiple, or empty.
  • the node device can obtain the transaction ID of the at least one candidate concurrent transaction by obtaining each active transaction ID recorded in each variable in the read set and the write set.
  • Step 602 can also be understood as that the node device starts to make preparations when each operation of the target transaction occurs, and enters the preparation phase of the target transaction; wherein, the preparation phase is to check whether the transaction T can be submitted before the transaction concurrent access control exception verification
  • the preparation work after the node device finds the transaction ID of at least one candidate concurrent transaction in the critical section, it exits the critical section.
  • step 602 is the preparation phase in step 501 above, and is used to screen out at least one candidate concurrent transaction.
  • Step 603 the node device determines a concurrent transaction of the target transaction from at least one candidate concurrent transaction, and the concurrent transaction and the target transaction include read and write operations acting on the same variable.
  • the node device obtains at least one candidate concurrent transaction of the target transaction when each operation of the target transaction occurs; for any candidate concurrent transaction in the at least one candidate concurrent transaction, the node device transaction, and the read set and write set of the target transaction, judge whether the candidate concurrent transaction is the concurrent transaction of the target transaction; if the candidate concurrent transaction and the target transaction include read and write operations on the same variable, then the The candidate concurrent transaction is determined to be the concurrent transaction of the target transaction, and steps 604 to 607 are executed; otherwise, the candidate concurrent transaction is re-added to the tail of the linked list TS.
  • the node device performs a consistency check based on whether a conflict ring graph is formed between the at least one candidate concurrent transaction and the target transaction.
  • a conflict ring graph is formed between the at least one candidate concurrent transaction and the target transaction.
  • Step 6031 the node device obtains the first candidate intersection between the read set of the target transaction and the write set of the candidate concurrent transaction, the second candidate intersection between the write set of the target transaction and the read set of the candidate concurrent transaction, and the A third candidate intersection between the write set and the write set of the candidate concurrent transaction.
  • the node device sets the number of directed edges between the target transaction T and the candidate concurrent transaction TL to 0, and the target transaction and the candidate concurrent transaction have the same effect
  • the number of version changes of the variable is set to 0, and the target variable list is set to an empty set.
  • the number of directed edges is used to indicate whether there is a conflict between the target transaction and the candidate concurrent transaction;
  • the number of version changes is used to indicate the data status of the same variable that the target transaction and the candidate concurrent transaction act on;
  • the target variable list Used to store the same variable that the target transaction acts on as this candidate concurrent transaction.
  • DLI Dynamic Line Intersection
  • VSL variable List
  • the node device when it obtains the first candidate intersection, the second candidate intersection and the third candidate intersection, it can use a hash table to store the respective read and write sets of the target transaction and the candidate concurrent transaction, so that it can The corresponding intersection is obtained within the complexity.
  • Step 6032 If the union among the first candidate intersection, the second candidate intersection and the third candidate intersection is an empty set, the node device re-adds the candidate concurrent transaction to the tail of the linked list TS; if the first candidate intersection, the second candidate If at least one item in the intersection set and the third candidate intersection set is not an empty set, the node device executes the following steps 6033 to 6035.
  • the union among the first candidate intersection, the second candidate intersection, and the third candidate intersection is an empty set (that is, the first intersection, the second intersection, and the third intersection are all empty sets), it means that the candidate concurrent transaction A concurrent transaction that is not the target transaction. If at least one of the first candidate intersection, the second candidate intersection, and the third candidate intersection is not an empty set, it means that the candidate concurrent transaction is the concurrent transaction of the target transaction, and the node device determines the candidate concurrent transaction as the concurrent transaction of the target transaction.
  • the transaction that is, the concurrent transaction involved in this step 603, executes the following steps 6033 to 6035; in addition, when the node device determines that the candidate concurrent transaction is the concurrent transaction of the target transaction, the first candidate intersection is the first intersection, The second candidate intersection is the second intersection, and the third candidate intersection is the third intersection.
  • Step 6033 to step 6035 will be described below by taking the candidate concurrent transaction as an example of a confirmed concurrent transaction.
  • Step 6033 If the first intersection is not an empty set, the node device increments the number of directed edges, and adds the variables in the first intersection to the target variable list; Variable, the node device performs incremental processing on the number of version changes.
  • the increment processing refers to incrementing the corresponding value by one.
  • DLI number of directed edges
  • VS number of version changes as VS
  • adding the variables in the first intersection to the target variable list by the node device refers to sequentially adding variables to the target variable list according to a preset order.
  • Step 6034 if the second intersection is not empty, the node device increments the number of directed edges, and adds the variables in the second intersection to the target variable list; if there are variables with different versions in the second intersection, the node The device performs incremental processing on the number of version changes.
  • step 6034 is similar to the above-mentioned step 6033 in implementation process, so the description will not be repeated here.
  • Step 6035 If the third intersection is not an empty set, the node device determines the data exception type based on the commit status of the concurrent transaction; if the third intersection is an empty set, the node device executes the subsequent step 604.
  • the node device determines the type of data exception based on the commit status of the concurrent transaction, reports the occurrence of a write exception, ends the current process, and rolls back the target transaction.
  • the node device executes the subsequent step 604 .
  • the node device determines that the data exception type is a dirty write exception; wherein, the target parameter T.no_committed is used to represent the target The number of committed transactions corresponding to the read-write set of the transaction; because in the loop process, if there is no data exception between the previous concurrent transaction and the target transaction, then before executing this loop, the previous concurrent transaction and the target transaction must be Transactions are merged, and the new transaction obtained after the merger is determined as the target transaction of this cycle, and the merger can be realized by merging the read-write sets of the two transactions; therefore, in any cycle, the read-write sets of the target transaction have It may be a merged read-write set.
  • the target parameter T.no_committed is used to describe the corresponding committed transaction in the read-write set. quantity.
  • the data exception type is a lost update exception.
  • the node device may execute the foregoing steps 6031 to 6035 synchronously, or may execute the foregoing steps 6031 to 6035 in any order, which is not limited in this embodiment of the present application.
  • the node device determines the concurrent transaction of the target transaction from at least one candidate concurrent transaction, and if the third intersection between the target transaction and the concurrent transaction is an empty set, the node device performs the following step 604.
  • Step 604 If at least one item in the first intersection and the second intersection is not an empty set, and the target transaction conflicts with the concurrent transaction, then the number of version changes and the target variable of the same variable that the node device acts on based on the target transaction and the concurrent transaction list, which determines the data exception type, and the target variable list includes the same variables that the target transaction and concurrent transactions act on.
  • the node device determines the data exception type based on the number of version changes and the target variable list.
  • the node device determines whether the target transaction conflicts with the concurrent transaction based on the number of directed edges between the target transaction and the concurrent transaction, that is, if the number of directed edges between the target transaction and the concurrent transaction is greater than or Equal to two, it is determined that the target transaction conflicts with the concurrent transaction.
  • step 604 The process of determining the data anomaly type in step 604 will be described below. Firstly, through the following four points, the category, subcategory, and isolation level of the data exception types involved in the embodiment of the present application are respectively introduced.
  • the first point is the category of the data exception type.
  • the types of data anomaly types include Write Anomaly Type (WAT), Read Anomaly Type (RAT) and Intersect Anomaly Type (IAT).
  • WAT Write Anomaly Type
  • RAT Read Anomaly Type
  • IAT Intersect Anomaly Type
  • the category of the data exception type is the write exception category; If there are no at least two write operations acting on the same variable of different versions in a schedule (called the write exception condition is not satisfied), and there are read and write operations acting on the same variable of the same version in the schedule (called meet the read exception condition), then the category of the data exception type is the read exception category; if there are no at least two write operations that act on the same variable of different versions in a schedule (it is called not meeting the write exception condition), and the There are no read operations and write operations that act on the same variable of the same version in the schedule (called not satisfying the read exception condition), and there are read operations and write operations that act on the same variable in different versions in the schedule (called satisfying the crossover condition). exception condition), the category of the data exception type is the cross exception category.
  • the category of the data exception type is the write exception category.
  • the category of the data exception type is the read exception category.
  • the category of the data anomaly type is a cross anomaly category.
  • the second point is the subcategory of the data exception type.
  • the first point describes that data anomaly types are divided into three categories: write anomaly category, read anomaly category, and cross anomaly category according to the differences in conflicts; here, in order to improve the precision of data anomaly identification, continue to The types of data anomalies are divided into subcategories.
  • the subcategory of the data anomaly type belongs to the single-meta data anomalies (Single-Meta Data Anomalies, SDA); if a data anomaly occurs two times (called the third specified number ) variables, the subcategory of the data anomaly type belongs to the double-meta data anomalies (Double-Meta Data Anomalies, DDA); if a data anomaly does not belong to the above two subcategories, the data anomaly type belongs to the category A subcategory of Multivariate Data Anomalies (Multi-Meta Data Anomalies, MDA).
  • the unit data is abnormal.
  • the third point is the subdivision of data anomaly types.
  • the category of data anomaly in each subcategory is given , name, corresponding formal representation, corresponding CCG diagram and corresponding subcategory.
  • Table 2 and Figures 7 to 9 are shown in Table 2 and Figures 7 to 9; among them, Figure 7 is a schematic diagram of a cell data abnormal CCG diagram provided by the embodiment of the present application; Figure 8 is a dual-element data abnormal CCG provided by the embodiment of the present application A schematic diagram of a graph; FIG. 9 is a schematic diagram of a multivariate data abnormality CCG graph provided in an embodiment of the present application.
  • the conflict loop in Figure 9-1 is a stepwise write exception
  • the scheduling contains WW conflicts.
  • the conflict loop in Figure 9-2 is a stepped read exception
  • the scheduling includes WR conflicts, but does not include WW conflicts.
  • the conflict ring in Figure 9-3 is a stepped cross anomaly
  • the scheduling includes RW conflicts, but does not include WW conflicts and WR conflicts.
  • the fourth point is the isolation level of the data exception type.
  • NRW Read-Write Anomalies
  • NA No Anomalies
  • the grading of the isolation level is based on the allowable degree of data abnormality, and the complexity of concurrent access control processing can be reduced through the isolation level.
  • NRW means that WAT and RAT data exceptions are not allowed, but IAT data exceptions cannot be eliminated
  • NA means that no data exceptions are allowed, which is equivalent to the serializable isolation level defined by the ANSI-SQL standard. Therefore, the NRW level is lower than the NA level.
  • the node device determines the concurrent access control processing based on the relevant information of the isolation level described in Table 3.
  • the node device can avoid data anomalies by setting rules, reaching the NRW level.
  • the WAT exception is avoided by adopting the rule of prohibiting the appearance of the WW side; and for example, the RAT exception is avoided by adopting methods such as read committed and snapshot read.
  • the number of layers of isolation levels can be reduced, and the efficiency of concurrent access control processing can be improved.
  • the serializable snapshot isolation (Serializable Snapshot Isolation, SSI) technology can reach the NA level by identifying whether two consecutive RW edges are abnormal, so the efficiency of concurrent access control processing can be improved.
  • step 604 is described in detail below based on the information described in the above four points. ; Wherein, step 604 includes step 6041 to step 6043, each step will be described separately below.
  • Step 6041 the node device determines the category it belongs to based on the read and write operations that act on the same variable in the target transaction and the concurrent transaction.
  • Step 6041 includes the following three situations, which will be described respectively below.
  • Case 1 If the target transaction and the concurrent transaction have a first specified number (for example, two) of write operations acting on the same variable of different versions, the node device determines that the category belongs to the write exception category.
  • a first specified number for example, two
  • the target transaction is T i
  • the concurrent transaction is T j
  • the node device determines that the category it belongs to is the write exception category.
  • Case 2 If there are no two write operations on the same variable of different versions in the target transaction and the concurrent transaction, and there are read and write operations on the same variable in the same version in the target transaction and the concurrent transaction , the node device determines that the category it belongs to is the abnormal read category.
  • the node device determines that the category it belongs to is the abnormal read category.
  • Case 3 If there are no two write operations on the same variable of different versions in the target transaction and the concurrent transaction, and there are no read and write operations on the same variable in the same version in the target transaction and the concurrent transaction operation, and the target transaction and the concurrent transaction have read and write operations on the same variable of different versions, then the node device determines that the category belongs to the cross exception category.
  • the node device determines that the category it belongs to is a cross-abnormal category.
  • Step 6042 the node device determines a subcategory in the category based on the category of the data anomaly type and the list of target variables.
  • the target variable list stores the same variables that the target transaction and the concurrent transaction act on, that is, the node device obtains the target transaction and the concurrent transaction based on the target variable list.
  • the number of identical variables thus combining the descriptions of the three subcategories above, determines the subcategory within the category to which it belongs.
  • this step 6042 includes the following three situations, which will be described respectively below.
  • Case 1 If the number of variables in the target variable list is the second specified number (for example, one), the node device determines that the subcategory in the category to which it belongs belongs to abnormal unit data.
  • the second specified number for example, one
  • Case 2 If the number of variables in the target variable list is the third specified number (for example, two), the node device determines that the subcategory in the category to which it belongs belongs to the dual metadata exception.
  • the third specified number for example, two
  • Case 3 If the number of variables in the target variable list is the fourth designated number, wherein the fourth designated number is different from the second designated number and the third designated number; It does not belong to the unit data anomaly, nor does it belong to the dual-element data anomaly; then the node device determines that the subcategory in the category belongs to the multi-element data anomaly.
  • Step 6043 the node device determines the type of data exception based on the subcategory of the category, the number of version changes, and the read and write operations on the same variable in the concurrent transaction and the target transaction.
  • the node device determines the data exception type based on the number of version changes and the read and write operations on the same variable in the concurrent transaction and the target transaction .
  • step 6043 includes the following three situations, which will be described respectively below.
  • the node device determines that the data anomaly type is a lost self-update anomaly.
  • the node device determines that the data exception type is an all-write exception .
  • the node device determines that the data exception type is Missing update exception.
  • step 6043 includes the following three situations, which will be described separately below.
  • the node device determines that the data anomaly type is a read-write partial sequence anomaly; wherein, satisfying the first condition means that the target read-write operation includes the first read-write operation acting on different versions For write operations and read operations of a variable, satisfying the second condition means that the target read and write operations include a first specified number of write operations acting on different versions of the second variable.
  • satisfying the third condition there are write operations and read operations that act on the first variable of the same version in the target transaction and the concurrent transaction (called satisfying the third condition), and there are second variables that act on different versions.
  • Two write operations of two variables (called satisfying the second condition)
  • the node device determines that the data anomaly type is a repeated write partial sequence anomaly; wherein, satisfying the third condition means that the target read and write operations include Write operation and read operation of a variable.
  • the node device determines that the data anomaly type is an all-write partial sequence anomaly; among them, satisfying the fourth condition means that the target read and write operations include the first The first specified number of write operations to a variable.
  • step 6043 includes the following two cases, which will be described separately below.
  • the node device determines that the data exception type is a non-repeatable read exception.
  • the node device determines that the data exception type is an intermediate read exception.
  • step 6043 includes the following two cases, which will be described separately below.
  • the node device determines that the data exception type is a write-read partial order exception.
  • the node device determines that the type of data anomaly is read partial order anomaly.
  • step 6043 includes: if the number of changes of the version is one, the node device determines that the data anomaly type is a write bias The sequence is abnormal.
  • step 6043 includes: the node device determines that the data anomaly type is a stepped write anomaly.
  • step 6043 includes: the node device determines that the data anomaly type is a stepped read anomaly.
  • step 6043 includes: the node device determines that the data anomaly type is a stepped cross anomaly.
  • the node device executes in the order from step 6041 to step 6043, that is, the node device first determines the category of the data anomaly type, then determines the subcategories, and finally determines the subcategories of data anomaly types.
  • the above steps 6041 to 6043 are replaced by the following steps 1 to 3.
  • Step 1 The node device determines the subcategory based on the target variable list.
  • Step 2 The node device determines the category it belongs to based on the target transaction and the read and write operations on the same variable in the concurrent transaction;
  • Step 3 The node device determines the data anomaly type based on the subcategory of the category, the number of changes of the version, and the read and write operations on the same variable in the concurrent transaction and the target transaction.
  • the node device first determines the subcategory of the data anomaly type, then determines the category to which it belongs, and finally determines the subcategory of the data anomaly type.
  • the node device may also simultaneously determine the category and subcategory of the data anomaly type, which is not limited in this embodiment of the present application.
  • the node device executes the following steps 605 to 607 after determining the data anomaly type. It should be noted that, if at least one item in the first intersection and the second intersection is not an empty set, and the target transaction does not conflict with the concurrent transaction, the node device executes the following step 608 .
  • Step 605 the node device determines the transaction to be rolled back from the target transaction and concurrent transactions.
  • the node device determines that a data anomaly occurs, and the target transaction or the concurrent transaction needs to be rolled back, and the transaction to be rolled back is determined from the two transactions.
  • Method 1 The node device determines the transaction with the lowest transaction priority among the target transaction and the concurrent transaction as the transaction to be rolled back according to the transaction priority.
  • the transaction priority is a preset priority
  • the database system pre-allocates transaction priorities for each type of transaction, for example, according to the processing time of the transaction, the type of operation of the transaction, and the number of variables used, etc. At least one is to determine the transaction priority of each transaction.
  • This embodiment of the present application does not limit the way of setting the transaction priority.
  • step 605 will be described below by taking the setting manners of four transaction priorities as examples.
  • the node device determines the current transaction as the transaction with the lowest transaction priority; thus, the transaction to be rolled back is the current transaction.
  • the transaction priority is determined according to the processing time of the transaction.
  • a transaction whose processing time is longer than the reference time is a long transaction, and a transaction whose processing time is less than or equal to the reference time is determined to be a short transaction, and the transaction priority of the long transaction is higher than that of the short transaction.
  • the current transaction is any one of the target transaction and the concurrent transaction, and other transactions are transactions other than the current transaction among the target transaction and the concurrent transaction.
  • the processing duration of the concurrent transaction is used as the reference duration. If the processing duration of the target transaction is shorter than the concurrent transaction, the node device determines the target transaction as a transaction to be rolled back; otherwise, the concurrent The transaction is identified as a transaction to be rolled back.
  • the node device determines the read transaction as a transaction with the lowest transaction priority; thus, the transaction to be rolled back is the read transaction.
  • the transaction priority is determined according to the operation type of the transaction, and the transaction priority of the write transaction is higher than the transaction priority of the read transaction;
  • the operation type of the transaction includes the write transaction type and the read transaction type, and the transaction of the write transaction type is a write transaction, and a read transaction is a read transaction.
  • the node device determines the target transaction as a transaction to be rolled back.
  • the node device determines the write transaction as the transaction with the lowest transaction priority; thus, waiting The transaction that is rolled back is the current transaction.
  • the transaction priority is determined in combination with the processing duration and operation type of the transaction, that is, when the write transaction is a short transaction, its transaction priority is lower than that of a long read transaction.
  • the node device determines the target transaction as a transaction to be rolled back.
  • the transaction priority can be set in other forms, for example, the transaction priority of the short transaction is higher than the transaction priority of the long transaction, and for example, the transaction priority of the read transaction is higher
  • the transaction priority of the write transaction, etc. is not limited in this embodiment of the present application.
  • the transaction can be rolled back in a targeted manner to ensure that important transactions are processed first, thereby improving the utilization of computing resources and improving transaction efficiency. processing efficiency.
  • the node device determines the current transaction as the transaction with the lowest transaction priority; The rolled transaction is the current transaction.
  • the node device traverses the target conflict ring graph of the target transaction and the concurrent transaction (the introduction of the target conflict ring graph will be introduced later in step 607, and the description will not be repeated here), and in the current transaction role When the number of variables is the largest, the current transaction is determined as the transaction to be rolled back.
  • rolling back transactions involving a large number of variables can reduce the possibility of conflicts with other transactions in the subsequent transaction processing, thereby reducing the conflict rate of transaction processing and improving the efficiency of transaction processing. efficiency.
  • the node device determines a transaction randomly selected from the target transaction and the concurrent transaction as the transaction to be rolled back.
  • Step 606 the node device rolls back the transaction to be rolled back.
  • the node device determines whether the target transaction and the concurrent transaction constitute a conflict, and determines the transaction to be rolled back only in the case of data abnormality.
  • the node device determines the transaction to be rolled back according to a certain strategy, instead of directly rolling back the target transaction, which can effectively reduce the false rollback rate, thereby improving the utilization of computing resources , improve the efficiency of transaction processing.
  • Step 607 the node device deletes the variable and the corresponding read and write operation of the transaction to be rolled back in the target conflict ring graph, wherein the vertices in the target conflict ring graph are used to represent the transaction identifier corresponding to the transaction and the read and write operations corresponding to the transaction.
  • the variables that the operation acts on, and the edges in the target conflict ring graph are used to represent the association relationship between transactions and the version changes between variables.
  • the target conflict cycle graph is a detail conflict cycle graph (Detail Conflict Cycle Graph, DCCG), which is a conflict cycle graph equivalent to the CCG graph and the CCSG graph, and is also the data in the embodiment of the present application.
  • DCCG Detail conflict Cycle Graph
  • the node device deletes the variable and the corresponding read and write operations of the transaction to be rolled back in the target conflict ring graph to maintain the structure of the target conflict ring graph.
  • Step 1 Obtain the first conflict ring graph between the target transaction and the concurrent transaction, the vertices in the first conflict ring graph are used to represent the transaction identification corresponding to the transaction, and the edges in the first conflict ring graph are used to represent The relationship between transactions and the variables that the read and write operations corresponding to the transactions act on.
  • the first conflict loop graph is a CCG graph between the target transaction and the concurrent transaction.
  • the meanings of the vertices and edges in the first conflict ring graph please refer to the introduction to the vertices and edges of the CCG graph above, and the description will not be repeated here.
  • Step 2 Convert the first conflict ring graph to obtain a second conflict ring graph, the vertices in the second conflict ring graph are used to represent multiple different versions of variables, and the edges in the second conflict ring graph are used to Represents version changes between variables and variables that are acted on by the same transaction.
  • the second conflict ring graph is a CCSG graph between the target transaction and the concurrent transaction.
  • the meanings of the vertices and edges in the second conflicting ring graph please refer to the introduction to the vertices and edges of the CCSG graph above, and the description will not be repeated here.
  • CCG and CCSG are equivalent. The following is based on the equivalent conversion rules from CCG to CCSG, and briefly describes the implementation of this step 2, including the following step A and Step B, each step will be described separately below.
  • Step A splitting the edges of the first conflict ring graph to obtain the multiple different versions of variables.
  • Step B Use the multiple different versions of variables as vertices, and add edges between vertices corresponding to the same variable in adjacent versions, and add edges between vertices corresponding to variables that act on the same transaction, to obtain the second Conflict Ring Diagram.
  • Step 3 Transform the second conflict ring graph to obtain the target conflict ring graph.
  • the target conflict ring graph is a new CCG graph obtained by converting the CCSG graph .
  • the vertices in the first conflict ring graph are used to represent the transaction identification corresponding to the transaction, and in the target conflict ring graph (that is, the new CCG graph), the vertexes of the target conflict ring graph Compared with the vertex information in the first conflict ring graph, the vertex information is more detailed, including not only the transaction identifier corresponding to the transaction, but also the variables used by the read and write operations corresponding to the transaction; in addition, the target conflict ring graph
  • the variables corresponding to the vertices retain the necessary variables to form the conflict ring, because there may be many variables operated by a transaction, but not all variables and their versions are sufficient conditions to form the conflict ring graph.
  • step 3 Based on the above-mentioned equivalent conversion rules from CCSG graph to CCG graph, the specific implementation of step 3 will be described below, including the following steps C to E, and each step will be described separately below.
  • Step C merging the vertices corresponding to the variables acting on the same transaction in the second conflict loop graph, and determining the transaction ID corresponding to the same transaction as the merged vertex. That is, the node device names the merged vertex as the transaction ID corresponding to the same transaction.
  • Step D adding edges between adjacent vertices of the merged second conflict ring graph to obtain a third conflict ring graph.
  • Step E If there are variables of the same version in any two adjacent vertices of the third conflicting ring graph, merge any two adjacent vertices, and delete the variable of the same version corresponding to the merged vertices, Obtain the target conflict ring graph; if there are different versions of the same variable in any two adjacent vertices of the third conflict ring graph, merge the arbitrary two adjacent vertices to obtain the target conflict ring graph.
  • the third conflict ring graph is the CCG graph obtained by converting the CCSG graph according to the equivalent conversion rules.
  • the The third conflict ring graph is applicable to the reduction rule, so that the node device merges the two vertices and deletes the variable of the same version; if there are different versions of the same variable in any two adjacent vertices, the third conflict The ring graph is applicable to the merge rule but not to the reduction rule, so the node device merges the two vertices; if the same variable does not exist in any two adjacent vertices, the node device directly takes the third conflicting ring graph Conflicting ring diagram as a goal.
  • V i and V i+1 can be merged into one vertex; in the new vertex merged, x m and y n can be removed, and the disjoint parts of the two vertices can be retained , that is, V i ⁇ V i+1 -V i ⁇ V i+1 . That is, the new vertex after reduction retains the difference between the two sets V i and V i+1 .
  • a minimum DCCG graph is equivalent to a certain data anomaly in Table 2 above.
  • the two vertices are irreducible; if That is, there is at least one same variable, and the reduction rule is not applicable, then the two adjacent vertices are applicable to the merge rule; that is, the transaction corresponding to the two adjacent vertices is called a mergeable transaction, and V i and V i+1 are merged into one vertex, the read set of the transaction corresponding to the merged new vertex is the collection of the read sets corresponding to V i and V i+1 , and the write set of the transaction corresponding to the merged new vertex It is a collection of write sets corresponding to V i and V i+1 .
  • the data anomaly represented by the dccg graph of a schedule s will not affect the equivalence of the original dccg graph after merging the mergeable transactions
  • the data is abnormal.
  • FIG. 10 An example is given to illustrate the method of obtaining the target conflict ring diagram; wherein, FIG. 10 is provided by the embodiment of the present application.
  • the edges in the CCG graph (that is, the first conflict cycle graph) of the schedule s are used to represent the relationship between transactions and the variables that are acted on by the read and write operations corresponding to the transactions.
  • E 1 (T 1 ⁇ T 2 , R 1 [x 0 ]W 2 [x 1 ])
  • E 2 (T 2 ⁇ T 3 , W 2 [y 1 ]R 3 [y 1 ])
  • E 3 (T 3 ⁇ T 1 , W 3 [z 1 ]W 1 [z 2 ]); corresponding to the three variables x, y and .
  • the CCG graph includes three variables x, y, and z, which are located on edges E 1 , E 2 , and E 3 respectively, and the variables are used as vertices to split the three edges. point.
  • vertices in the CCG graph are deleted.
  • the CCSG graph is a graph composed of a directed cycle, then the edges W 3 [z 1 ] and W 2 [y 1 ] and the variable versions z 0 and y 0 form a directed cycle It has no effect, so these two edges and these two variable versions are deleted, and the CCSG graph shown in (e) in Figure 10 is obtained.
  • the vertices in the CCSG graph (that is, the second conflict ring graph) are used to represent multiple different versions of variables, and the edges in the second conflict ring graph are used to represent the Version changes between and variables that act on the same transaction.
  • vertex V ⁇ x 0 , x 1 , y 1 , z 1 , z 2 ⁇ ;
  • E ⁇ W 2 [x 1 ], R 2 [x 1 ]R 2 [y 1 ], R 3 [ y 1 ]R 3 [z 1 ], W 1 [z 2 ], R 1 [x 2 ]R 1 [x 0 ] ⁇ ;
  • E T ⁇ R 2 [x 1 ]R 2 [y 1 ], R 3 [y 1 ] R 3 [z 1 ], R 1 [x 2 ] R 1 [x 0 ] ⁇ ;
  • E s ⁇ W 2 [x 1 ], W 1 [z 2 ] ⁇ .
  • (f) in FIG. 10 is a new CCG graph (that is, the third conflict loop graph) obtained by converting the CCSG graph shown in (e) in FIG. 10 .
  • the conversion process includes: the node device merges the variable versions involved in the same transaction in the CCSG graph into the same vertex to obtain (f) in FIG. 10 .
  • each vertex becomes a transaction as a vertex again, showing the relationship between transactions.
  • the graph may also be an undirected loop graph.
  • vertices V 2 and V 3 satisfy the above reduction rules, that is, both vertices contain the same version of variable y 1 , therefore, for vertices V 2 and V 3 Merging is performed, and the variable y 1 in the merged vertices is deleted to obtain the DCCG graph shown in (h) in FIG. 10 (that is, the target conflict cycle graph).
  • the method of obtaining the target conflict ring graph has been introduced by way of example above, which can also be understood as the process of determining the directed ring graph between concurrent transactions.
  • this step 607 after determining the transaction to be rolled back, the node device maintains the structure of the target conflict ring graph, so as to facilitate the subsequent execution of the next cycle, that is, other candidate concurrent transactions in at least one candidate concurrent transaction The transaction is checked for consistency.
  • step 608 will be used to illustrate the case that the target transaction and the concurrent transaction do not conflict.
  • Step 608 the node device merges the target transaction and the concurrent transaction to obtain the merged target transaction, and executes the above step 603 again until the linked list TS is empty.
  • the target transaction does not conflict with the concurrent transaction. It can also be understood that the target transaction and the If there is no target conflict ring graph between concurrent transactions, there is no data anomaly between the target transaction and the concurrent transaction.
  • the node device merges the two transactions to obtain the merged target transaction, and continues to select candidate concurrent transactions from the linked list TS until The linked list TS is empty.
  • step 608 by taking the target transaction as T and the concurrent transaction as TL as an example.
  • the node device merges the read set of the concurrent transaction TL into the read set of the target transaction T, and merges the write set of the concurrent transaction TL into the write set of the target transaction T to realize transaction merging and obtain a new merged transaction T-new ;In addition, if the concurrent transaction TL is not committed, then incremental processing is performed on the target parameter (no_committed) of T-new, that is, T-new. Constituents of the read-write set of committed transactions.
  • Step 609 If there is no data anomaly between the last candidate concurrent transaction in the linked list TS and the target transaction, the node device submits the target transaction.
  • the serializable level can be satisfied at this time, otherwise, the isolation level set in Table 3 above can be satisfied.
  • Fig. 11 is a schematic structural diagram of a transaction processing device provided according to an embodiment of the present application.
  • the transaction processing device is used to execute the steps when the above transaction processing method is executed.
  • the transaction processing device 1100 includes: a first determining module 1101 and a second determining module 1102 .
  • the first determination module 1101 is configured to determine a concurrent transaction of the target transaction, the concurrent transaction and the target transaction include read and write operations acting on the same variable, and the target transaction is a transaction to be committed;
  • the second determination module 1102 is configured to obtain the first intersection between the read set of the target transaction and the write set of the concurrent transaction, and obtain the intersection between the write set of the target transaction and the read set of the concurrent transaction the second intersection; when at least one of the first intersection and the second intersection is a non-empty data set, and the target transaction conflicts with the concurrent transaction, based on the target transaction and the concurrent.
  • the number of version changes of the same variable acted on by the transaction and the target variable list determine the type of data exception, and the target variable list includes the target transaction and the same variable acted on by the concurrent transaction.
  • the transaction processing device 1100 also includes a third determination module and a rollback module; the third determination module is configured to determine the transaction to be rolled back from the target transaction and the concurrent transaction; the rollback module , configured to rollback the transaction to be rolled back.
  • the third determination module is configured to determine, based on transaction priorities, the transaction with the lowest transaction priority among the target transaction and the concurrent transactions as the transaction to be rolled back.
  • the third determining module is configured to determine the current transaction as the The transaction with the lowest transaction priority, the current transaction is any one of the target transaction and the concurrent transaction, and the other transaction is the target transaction and the concurrent transaction except the current transaction transaction; in the target transaction and the concurrent transaction, when the current transaction is a read transaction, determine the current transaction as the transaction with the lowest priority of the transaction; in the target transaction and the concurrent transaction In, when the current transaction is a write transaction and the processing duration of the current transaction is less than a reference duration, the current transaction is determined as the transaction with the lowest priority of the transaction; when the target transaction and the concurrent transaction In, when the number of variables acted on by the current transaction is greater than the number of variables acted on by the other transactions, the current transaction is determined as the transaction with the lowest priority of the transaction.
  • the transaction processing device 1100 further includes a delete module configured to delete the variable and the corresponding read and write operations of the transaction to be rolled back in the target conflict ring graph, wherein, in the target conflict ring graph
  • the vertices of are used to represent the transaction identification corresponding to the transaction and the variables on which the read and write operations corresponding to the transaction act.
  • the edges in the target conflict ring graph are used to represent the association relationship between transactions and the version changes between variables.
  • the transaction processing apparatus 1100 further includes an acquisition module configured to acquire the target conflict ring graph between the target transaction and the concurrent transaction.
  • the acquisition module includes a sub-acquisition module, a first conversion module, and a second conversion module; the acquisition module is configured to acquire a first conflict ring graph between the target transaction and the concurrent transaction, and the first The vertices in the conflict ring graph are used to represent the transaction identifiers corresponding to the transactions, and the edges in the first conflict ring graph are used to represent the association relationship between transactions and the variables acted on by the read and write operations corresponding to the transactions; the first conversion module, It is configured to convert the first conflict ring graph to obtain a second conflict ring graph, the vertices in the second conflict ring graph are used to represent multiple different versions of variables, and the edges in the second conflict ring graph are used to represent The version changes between variables and the variables affected by the same transaction; the second conversion module is configured to convert the second conflict loop graph to obtain the target conflict loop graph.
  • the first conversion module is configured to split the edges of the first conflict ring graph to obtain the multiple different versions of variables; use the multiple different versions of variables as vertices, and Edges are added between vertices corresponding to the same variable in adjacent versions, and edges are added between vertices corresponding to variables that act on the same transaction to obtain the second conflict loop graph.
  • the second conversion module is configured to merge the vertices corresponding to the variables of the same transaction in the second conflict loop graph, and determine the transaction identifier corresponding to the same transaction as the merged vertex ; Add edges between adjacent vertices of the second conflict ring graph after merging to obtain a third conflict ring graph; when two adjacent vertices of the third conflict ring graph include variables of the same version, Merge the two adjacent vertices, and delete the variables of the same version in the merged vertices to obtain the target conflict ring graph; when two adjacent vertices in the third conflict ring graph include different versions When the same variable, the two adjacent vertices are merged to obtain the target conflict ring graph.
  • the transaction processing device 1100 further includes a first processing module, a second processing module, and a third processing module;
  • the first processing module is configured to , incrementally process the number of directed edges between the target transaction and the concurrent transaction, and add the variables in the first intersection to the target variable list, and when the first intersection
  • incremental processing is performed on the number of version changes, and the number of directed edges is used to indicate whether there is a conflict between the target transaction and the concurrent transaction
  • the second processing module is configured as When the second intersection is the non-empty data set, incrementally process the number of directed edges, and add the variables in the second intersection to the target variable list, and when the The second intersection includes variables with different versions, and performs incremental processing on the number of version changes
  • the third processing module is configured to, when the third intersection is the non-empty data set, based on the commit status of the concurrent transaction , determining the data exception type, and the third intersection is an intersection between the write set of the target transaction and the write set of the
  • the second determination module 1102 includes a first sub-determination module, a second sub-determination module, and a third sub-determination module; the first sub-determination module is configured to The target read and write operations acting on the same variable in the medium determine the category; the second sub-determining module is configured to determine the sub-category in the category based on the target transaction and the target read and write operations acting on the same variable in the concurrent transaction category; a third sub-determining module configured to determine the data anomaly type based on at least one of the subcategory in the category, the number of version changes, and the target read and write operations.
  • the first sub-determining module is further configured to determine that the category to which it belongs is a write exception category when the target transaction and the target read and write operations in the concurrent transaction meet the write exception condition , satisfying the write exception condition means that the target read and write operations include the first specified number of write operations acting on different versions of the same variable; when the target read and write operations do not meet the write exception condition and meet the When the exception condition is present, it is determined that the category to which it belongs is a read exception category, and meeting the read exception condition means that the target read and write operations include read and write operations acting on the same variable of the same version; when the target read and write operation When the write exception condition and the read exception condition are not satisfied, and the cross exception condition is met, it is determined that the category belongs to the cross exception category, and the cross exception condition is met when the target read and write operations include actions on different versions read and write operations of the same variable.
  • the second sub-determining module is further configured to determine that the subcategory in the category to which it belongs is abnormal unit data when the number of variables in the target variable list is the second specified number ; When the number of variables in the target variable list is the third designated number, determine that the subcategory in the category to which it belongs is anomaly of binary data; when the number of variables in the target variable list is the fourth designated number When the quantity is determined, it is determined that the subcategory in the belonging category is a multivariate data anomaly, wherein the fourth specified quantity is different from both the second specified quantity and the third specified quantity.
  • the third sub-determining module is further configured to: when the number of version changes is the second specified number , based on the write exception type and the unit data exception, it is determined that the data exception type is a lost self-update exception; when the number of version changes is the third specified number, and the target read and write operation is the fifth specified quantity of write operations, based on the write exception category and the unit data exception, it is determined that the data exception type is an all-write exception; when the number of version changes is the third specified number, and the target read When the write operations are the first specified number of write operations and the sixth specified number of read operations, based on the write exception type and the unit data exception, it is determined that the data exception type is a lost update exception.
  • the third sub-determining module is further configured to When the target read/write operation satisfies the first condition and the second condition, based on the write exception type, the dual data exception and the second specified number, determine that the data exception type is a read/write partial order exception , satisfying the first condition means that the target read and write operations include write operations and read operations acting on different versions of the first variable, and satisfying the second condition means that the target read and write operations include acting on different versions of the first variable.
  • the third sub-determining module is further configured to The target read and write operations include a first specified number of read operations and a sixth specified number of write operations acting on the same variable, and based on the read exception type, the cell data exception, and the second specified number, determine the The data exception type is a non-repeatable read exception; when the target read and write operations include the first specified number of write operations and the sixth specified number of read operations acting on the same variable, based on the read exception type, The unit data exception and the second specified number determine that the data exception type is an intermediate read exception.
  • the third sub-determining module is further configured to: when the number of version changes is the seventh specified number , based on the read exception category and the binary data exception, determine that the data exception type is a write-read partial sequence exception; when the number of version changes is a second specified number, based on the read exception category and the For binary data exception, it is determined that the data exception type is read partial order exception.
  • the third sub-determining module is further configured to: when the category to which it belongs is a cross anomaly category, the subcategory is a dual metadata anomaly, and the number of version changes is the second specified number, It is determined that the data exception type is a write partial order exception.
  • the third sub-determining module is further configured to determine that the data exception type is a stepped write exception when the category to which it belongs is a write exception category and the subcategory is a multivariate data exception; When the category to which it belongs is a read exception category, and the subcategory is the multivariate data exception, then determine that the data exception type is a stepped read exception; when the category to which it belongs is a cross exception category, and the subcategory When the category is the multivariate data anomaly, it is determined that the data anomaly type is a stepped cross anomaly.
  • the transaction processing device provided by the above-mentioned embodiment handles a transaction
  • the division of the above-mentioned functional modules is used as an example for illustration.
  • the above-mentioned function allocation can be completed by different functional modules according to needs.
  • the internal structure of the device is divided into different functional modules to complete all or part of the functions described above.
  • the transaction processing device and the transaction processing method provided in the embodiment of the present application belong to the same idea, and the implementation process is detailed in the method embodiment, and will not be described again here.
  • the embodiment of the present application also provides an electronic device (such as a computer device), the electronic device includes a processor and a memory, and the memory is used to store at least one computer program, and the at least one computer program is loaded and executed by the processor to realize The transaction processing method in the embodiment of this application.
  • an electronic device such as a computer device
  • the electronic device includes a processor and a memory
  • the memory is used to store at least one computer program
  • the at least one computer program is loaded and executed by the processor to realize The transaction processing method in the embodiment of this application.
  • the computer programs involved in the embodiments of the present application can be deployed and executed on one computer device, or executed on multiple computer devices located at one location, or distributed in multiple locations and via wired Executed on multiple computer devices interconnected by network or wireless network, multiple computer devices distributed in multiple locations and interconnected by wired network or wireless network can form a blockchain system.
  • FIG. 12 is a schematic structural diagram of a server provided according to an embodiment of the present application.
  • the server 1200 may have relatively large differences due to different configurations or performances, and may include one or more processors ( Central Processing Units (CPU) 1201 and one or more memory 1202, wherein at least one computer program is stored in the memory 1202, and the at least one computer program is loaded and executed by the processor 1201 to realize the above-mentioned various method embodiments provided Transaction method.
  • the server can also include components such as wired or wireless network interfaces, keyboards, and input and output interfaces for input and output, and the server can also include other components for implementing device functions, which will not be described again here.
  • the embodiment of the present application also provides a computer-readable storage medium, the computer-readable storage medium is applied to a computer device, and at least one computer program is stored in the computer-readable storage medium, and the at least one computer program is loaded by a processor and Execute to realize the transaction processing method of the embodiment of the present application.
  • An embodiment of the present application also provides a computer program product, including a computer program or an instruction, where the computer program or instruction is stored in a computer-readable storage medium.
  • the processor of the computer device reads the computer program or instruction from the computer-readable storage medium, and the processor executes the computer program or instruction, so that the computer device executes the transaction processing method provided by the embodiment of the present application.
  • the program can be stored in a computer-readable storage medium.
  • the above-mentioned The storage medium mentioned may be a read-only memory, a magnetic disk or an optical disk, and the like.

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Software Systems (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Databases & Information Systems (AREA)
  • Data Mining & Analysis (AREA)
  • Computer Security & Cryptography (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

一种数据库系统的事务处理方法、装置、电子设备、计算机可读存储介质及计算机程序产品。事务处理方法包括：确定目标事务的并发事务，并发事务与目标事务之间包括作用于同一变量的读写操作，目标事务为待提交事务（S501）；获取目标事务的读集和并发事务的写集之间的第一交集，并获取目标事务的写集和并发事务的读集之间的第二交集；当第一交集和第二交集中的至少一项为非空数据集、且目标事务与并发事务冲突时，基于目标事务和并发事务所作用的同一变量的版本变更次数和目标变量列表，确定数据异常类型，目标变量列表包括目标事务和并发事务所作用的同一变量（S502）。

Description

一种数据库系统的事务处理方法、装置、电子设备、计算机可读存储介质及计算机程序产品
相关申请的交叉引用
本申请基于申请号为202110546080.0、申请日为2021年05月19日的中国专利申请提出，并要求该中国专利申请的优先权，该中国专利申请的全部内容在此引入本申请作为参考。
技术领域
本申请涉及数据库技术领域，涉及一种数据库系统的事务处理方法、装置、电子设备、计算机可读存储介质及计算机程序产品。
背景技术
随着数据库技术的发展，在数据库系统中如何识别数据异常成为了一个关键问题。目前有两种识别数据异常的方法，其一是利用封锁技术，依赖锁的互斥机制，来识别数据异常，其二是利用依赖图技术，在由并发事务构成的依赖图中确认是否存在环，如果存在环，则说明存在数据异常。然而，封锁技术限制了数据库系统的并发度，导致事务处理效率低下，而依赖图技术又需要遍历每个并发事务以识别出环的存在，导致事务处理效率较低。
发明内容
本申请实施例提供了一种数据库系统的事务处理方法、装置、电子设备、计算机可读存储介质及计算机程序产品，能够提高数据库系统的事务处理效率。
本申请实施例提供了一种数据库系统的事务处理方法，该方法包括：
确定目标事务的并发事务，所述并发事务与所述目标事务之间包括作用于同一变量的读写操作，所述目标事务为待提交事务；
获取所述目标事务的读集和所述并发事务的写集之间的第一交集，并获取所述目标事务的写集和所述并发事务的读集之间的第二交集；
当所述第一交集和所述第二交集中的至少一项为非空数据集、且所述目标事务与所述并发事务冲突时，基于所述目标事务和所述并发事务所作用的同一变量的版本变更次数和目标变量列表，确定数据异常类型，所述目标变量列表包括所述目标事务和所述并发事务所作用的同一变量。
本申请实施例提供了一种事务处理装置，该装置包括：
第一确定模块，配置为确定目标事务的并发事务，所述并发事务与所述目标事务之间包括作用于同一变量的读写操作，所述目标事务为待提交事务；
第二确定模块，配置为获取所述目标事务的读集和所述并发事务的写集之间的第一交集，并获取所述目标事务的写集和所述并发事务的读集之间的第二交集；当所述第一交集和所述第二交集中的至少一项为非空数据集、且所述目标事务与所述并发事务冲突时，基于所述目标事务和所述并发事务所作用的同一变量的版本变更次数和目标变量列 表，确定数据异常类型，所述目标变量列表包括所述目标事务和所述并发事务所作用的同一变量。
本申请实施例提供了一种电子设备，该电子设备包括处理器和存储器，该存储器用于存储至少一条计算机程序，该至少一段计算机程序由该处理器加载并执行时，实现本申请实施例提供的数据库系统的事务处理方法。
本申请实施例提供了一种计算机可读存储介质，该计算机可读存储介质中存储有至少一条计算机程序，该至少一条计算机程序由处理器加载并执行时，实现本申请实施例提供的数据库系统的事务处理方法。
本申请实施例提供了一种计算机程序产品，该计算机程序产品包括计算机程序或指令，该计算机程序或指令被处理器执行时，实现本申请实施例提供的数据库系统的事务处理方法。
本申请实施例提供的技术方案带来的有益效果至少包括：在确定目标事务的并发事务后，在该目标事务的读集和该并发事务的写集之间的第一交集和该目标事务的写集和该并发事务的读集之间的第二交集中，存在非空数据集的情况下，对目标事务与并发事务是否冲突进行判断，若目标事务与并发事务冲突，则根据这两个事务所作用的相同变量以及相同变量的版本变更次数，来确定数据异常类型；如此，能够在目标事务的执行过程中，确认目标事务与并发事务是否真正构成冲突，另外通过两个事务所作用的相同变量来确定数据异常类型，能够识别数据库系统中的各种数据异常，保证数据状态的一致性，从而提高数据库系统的事务处理效率。
附图说明
为了更清楚地说明本申请实施例中的技术方案，下面将对本申请实施例描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本申请的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
图1是根据本申请实施例提供的一种事务处理方法的实施环境示意图；
图2是根据本申请实施例提供的一种冲突环图的示意图；
图3是根据本申请实施例提供的另一种冲突环图的示意图；
图4是根据本申请实施例提供的又一种冲突环图的示意图；
图5是根据本申请实施例提供的一种事务处理方法的流程图；
图6是根据本申请实施例提供的另一种事务处理方法的流程图；
图7是根据本申请实施例提供的一种单元数据异常CCG图的示意图；
图8是根据本申请实施例提供的一种双元数据异常CCG图的示意图；
图9是根据本申请实施例提供的一种多元数据异常CCG图的示意图；
图10是根据本申请实施例提供的一种获取目标冲突环图的示意图；
图11是根据本申请实施例提供的一种事务处理装置的结构示意图；
图12是根据本申请实施例提供的一种服务器的结构示意图。
具体实施方式
为使本申请的目的、技术方案和优点更加清楚，下面将结合附图对本申请实施方式作进一步地详细描述。
这里将详细地对示例性实施例进行说明，其示例表示在附图中。下面的描述涉及附图时，除非另有表示，不同附图中的相同数字表示相同或相似的要素。以下示例性实施 例中所描述的实施方式并不代表与本申请相一致的所有实施方式。相反，它们仅是与如所附权利要求书中所详述的、本申请的一些方面相一致的装置和方法的例子。
本申请中术语“第一”“第二”等字样用于对作用和功能基本相同的相同项或相似项进行区分，应理解，“第一”、“第二”、……、“第七”之间不具有逻辑或时序上的依赖关系，也不对数量和执行顺序进行限定。还应理解，尽管以下描述使用术语第一、第二等来描述各种元素，但这些元素不应受术语的限制。
这些术语只是用于将一个元素与另一个元素区别开。例如，在不脱离各种示例的范围的情况下，第一事务能够被称为第二事务，并且类似地，第二事务也能够被称为第一事务。第一事务和第二事务都可以是事务，并且在某些情况下，可以是单独且不同的事务。
其中，至少一个是指一个或一个以上，例如，至少一个事务可以是一个事务、两个事务、三个事务等任意大于等于一的整数个事务。而多个是指两个或者两个以上，例如，多个事务可以是两个事务、三个事务等任意大于等于二的整数个事务。
在介绍本申请实施例之前，需要引入一些云技术领域内的基本概念。
云技术(Cloud Technology)：是指在广域网或局域网内将硬件、软件、网络等系列资源统一起来，实现数据的计算、储存、处理和共享的一种托管技术，也即是基于云计算商业模式应用的网络技术、信息技术、整合技术、管理平台技术和应用技术等的总称，可以组成资源池，按需所用，灵活便利。本申请实施例所提供的数据库系统的事务处理方法(以下简称为事务处理方法)，可以是基于云技术实现的。
云存储(Cloud Storage)：是在云计算概念上延伸和发展出来的一个新的概念，分布式云存储系统(以下简称存储系统)是指通过集群应用、网格技术以及分布存储文件系统等功能，将网络中大量各种不同类型的存储设备(存储设备也称之为存储节点)通过应用软件或应用接口集合起来协同工作，共同对外提供数据存储和业务访问功能的一个存储系统。本申请实施例所提供的事务处理方法，可以应用于云存储中，以对云存储中的异常进行识别。
数据库系统(Database)：一种电子化的文件柜，也即是存储电子文件的处所，用户可以对文件中的数据进行新增、查询、更新和删除等操作。所谓“数据库系统”是以一定方式储存在一起、能与多个用户共享、具有尽可能小的冗余度、与应用程序彼此独立的数据集合。本申请实施例所提供的事务处理方法，可以应用于数据库系统中，以对数据库系统中的异常进行识别。
本申请实施例所涉及的数据库系统，可以是单机数据库系统、单机以事务为主的数据库系统、单机以分析型为主但需要事务处理能力的数据库系统，可以是泛指非关系型数据库(Non-relational SQL，NoSQL)体系，还可以是分布式数据库系统、分布式大数据处理系统，对于分布式数据库系统而言，当不同变量分布存储在不同的物理节点上时，对应于数据状态一致性模型中存在两个及两个以上变量的情况，数据状态一致性模型以及相应的事务处理流程均将在后续描述中进行详细说明。
在数据库系统中可以包括至少一个节点设备，每个节点设备的数据库中可以存储有多个数据表，每个数据表可以用于存储一个或多个数据项(也称为变量版本)。其中，节点设备的数据库可以为任一类型的分布式数据库，可以包括关系型数据库或者非关系型数据库中至少一项，例如结构化查询语言(Structured Query Language，SQL)数据库、NoSQL、泛指各种新式的可拓展/高性能数据库(NewSQL)等，在本申请实施例中对数据库的类型不作限定。
在一些实施例中，还可以应用于一种基于区块链技术的数据库系统(以下简称为“区块链系统”)，上述区块链系统在本质上属于一种去中心化式的分布式数据库系统，采用 共识算法保持区块链上不同节点设备所记载的账本数据一致，通过密码算法保证不同节点设备之间账本数据的加密传送以及不可篡改，通过脚本系统来拓展账本功能，通过网络路由来进行不同节点设备之间的相互连接。
在区块链系统中可以包括一条或多条区块链，区块链是一串使用密码学方法相关联产生的数据块，每一个数据块中包含了一批次网络交易的信息，用于验证其信息的有效性(防伪)和生成下一个区块。
区块链系统中节点设备之间可以组成点对点(Peer To Peer，P2P)网络，P2P协议是一个运行在传输控制协议(Transmission Control Protocol，TCP)协议之上的应用层协议。在区块链系统中，任一节点设备可以具备如下功能。
1)路由，节点设备具有的基本功能，用于支持节点设备之间的通信；
2)应用，用于部署在区块链中，根据实际业务需求而实现特定业务，记录实现功能相关的数据形成账本数据，在账本数据中携带数字签名以表示数据来源，将账本数据发送至区块链系统中的其他节点设备，供其他节点设备在验证账本数据来源以及完整性成功时，将账本数据添加至临时区块中；其中，应用实现的业务可以包括钱包、共享账本和智能合约等；
3)区块链，包括一系列按照先后的时间顺序相互接续的区块，新区块一旦加入到区块链中就不会再被移除，区块中记录了区块链系统中节点设备提交的账本数据。
在一些实施例中，每个区块中可以包括本区块存储交易记录的哈希值(本区块的哈希值)以及前一区块的哈希值，各区块通过哈希值连接形成区块链；另外，区块中还可以包括有区块生成时的时间戳等信息。
由于数据库系统中事务并发控制的正确程度可以通过一致性和隔离性来描述，因此在介绍本申请实施例之前，下面先对一致性和隔离性进行解释说明。
一、隔离性；事务隔离级别通过能否规避某种数据异常而进行定义，可能涉及到的数据异常包括：A、脏读，指一个事务读取到了另一事务尚未提交的数据项；B、不可重复读，指一个事务对同一数据项重复读取两次却得到了不同的结果；C、幻读，指事务在操作过程中进行两次谓词查询(范围查询)，第二次查询的结果包含了第一次查询的结果中未出现的数据项或者缺少了第一次查询的结果中出现的数据项。
基于能够解决上述ABC三种数据异常，数据库国际标准国家标准学会(A-National Standards Institute，ANSI)SQL提出四种隔离级别，以对上述ABC三种已知的数据异常加以区分，以在允许某些数据异常存在的情况下提高事务处理效率。
另外，还包括四种隔离级别，分别包括：a、读未提交：允许如上ABC三种数据异常发生；b、读已提交：不允许脏读发生；c、可重复读：不允许脏读、不可重复读发生；d、可串行化：如上ABC三种数据异常均不能发生。易知，这四种隔离级别均不允许脏写异常发生，脏写异常是指两个未提交事务修改了同一个数据项。在ANSI SQL制定标准时已知的数据异常种类不多，后续不断有新的数据异常被发现，除了上述几种数据异常之外，数据异常还包括：丢失更新异常、读偏序异常、写偏序异常、读写偏序异常、锯齿波写偏序异常、串行并发现象(Serial-Concurrent-Phenomenon)异常、交叉现象(Cross-Phenomenon)异常、因果丢失异常、因果反转异常、旧读异常和未来读异常等。
二、一致性；在数据库技术中，“一致性”一词可以表达两重含义，一是指事务一致性，二是指分布式一致性。
数据库的事务一致性为：在事务的操作下，数据库的数据状态从一个一致的状态变迁为另一个一致的状态。上述“一致的状态”是指满足数据库系统预先定义的一些规则的数据状态，比如，这些规则可以包括约束、级联、触发器以及三者之间任意的组合(属于数据的逻辑语义)；写偏序异常违反的就是特定数据之间的约束，这里的约束属于用 户语义所限定的数据的一致性。
数据库的事务处理技术中的并发访问控制技术，用于发现和解决事务并发操作在数据项上是否会造成数据异常、以及如何消除数据异常的问题，ANSI SQL提出了四种数据异常和隔离级别，各种并发访问控制算法也得以发展；例如，基于封锁的并发访问控制技术、基于时间戳的并发访问控制技术、基于多版本并发控制(Mutil-Version Concurrency Control，MVCC)的并发访问控制技术、基于乐观并发控制(Optimistic Concurrency Control，OCC)的并发访问控制技术等。
数据库的分布式一致性也称为共享数据对象操作一致性，是针对整个数据库系统的系统级含义，是指要想保证数据在数据库系统中保持一致，还要求数据库系统符合两个特性，一个是可串行性(Serializability)，另一个是可恢复性(Recoverability)。可串行性也即是说上述在隔离性中的可串行化隔离级别，可串行性保证了并发操作的正确性，而可恢复性是指已经提交的事务未曾读过被回滚的事务写过的数据(指不会发生脏读异常)，可恢复性保证了事务被回滚后数据回到之前的一致的状态，被回滚的事务不会对数据的一致性造成影响，数据库系统的一致性状态是可恢复的。
基于上述概念可知一致性和隔离性均与数据异常是息息相关的，故需要在数据库系统中识别并规避数据异常。这里，涉及到的数据库异常可以包括：脏读数据异常、脏写数据异常、不可重复读数据异常、幻读数据异常、丢失更新数据异常、读偏序数据异常、写偏序数据异常、串行并发现象数据异常、交叉现象数据异常等。
一般来说，在识别数据异常时依赖于可串行化原理，通常可以采用两种识别数据异常的策略。一是利用封锁技术，依赖锁的互斥机制来避免数据异常的发生，比如DB2、Informix合MySQL等数据库系统的可串行化隔离级别都是使用封锁技术；二是利用依赖图技术，通过在并发事务所构成的依赖图中确认是否存在环，如果存在环则需要打破环的存在从而消除潜在的数据异常。
然而，封锁技术严重限制了数据库系统的并发度，导致事务处理效率低下，而依赖图技术则需要在并发事务之间遍历每个事务以识别出环的存在，导致事务处理效率较低；而为了识别出环是否存在，不仅需要借助各种衍生出的算法，而且需要复杂的数据结构来表示并发事务与被操作的数据项(也即是变量版本)之间的关联关系，提高了数据库系统的复杂性。
此外，为了进行事务处理，还可采用基于依赖图和冲突可串行化技术(该技术基于可串行化原理)的简化实现方式，比如数据库(PostgreSQL)的快照隔离(Snapshot Isolation，SSI)技术，SSI技术中能够提前识别出可能会造成依赖图中存在环的必要不充分条件：一个事务存在一条读写冲突入边和读写冲突出边；如果任一事务满足上述条件，则认为存在数据异常。
另外，上述识别数据异常的方法还存在如下问题。
第一，认知割裂不统一：封锁技术、依赖图技术和SSI技术，均割裂了每一种数据异常的识别方式，使得在识别数据异常时只能逐个去认知是否符合每一种数据异常；也即是说，不能用统一的角度去识别、认知这些不同种类的数据异常，导致针对数据异常的认知思路复杂且不清晰统一，复杂度较高。
第二，认知有限不全面：封锁技术、依赖图技术和SSI技术，均不能穷尽是否还有未知的新的数据异常。而当数据异常存在时，将会为整个数据库系统带来损失；比如，当数据库系统处于非可串行化隔离级别下，如有新的数据异常，那么会导致系统中出现数据不一致错误。
第三，识别原理不精准：可串行化是数据存在异常的充分不必要条件，如此在数据库系统实现中虽然可避免出现新的数据异常，但是也有可能会把一些不存在数据异常的 情况也当作了数据异常，相当于对于数据异常进行了误判；比如事务1写入了变量版本X1且读取了变量版本Y1，事务2读取了变量版本X1且写入了变量版本Y1，上述一系列的数据库操作可以记为“W1(X1)R2(X1)W2(Y1)R1(Y1)C2C1”，这一系列的操作是不可串行化的，但并不存在数据异常。
有鉴于此，本申请实施例提供一种事务处理方法，给出了在事务处理过程中识别数据异常并规避数据异常的方式，提供了一种通用形式的冲突环图来定义数据异常，在确保数据异常定义的正确性的前提下，使得数据异常定义形象化；并且，对数据异常进行了细化分类，能够提高数据库系统的事务处理效率，下面将进行详述。
图1是本申请实施例提供的一种事务处理方法的实施环境示意图。参见图1，本申请实施例可以应用于数据库系统中的分布式数据库系统，该系统中可以包括网关服务器101(示例性地示出了三个网关服务器)、全局时间戳生成集群102、分布式存储集群103以及分布式协调系统104(例如ZooKeeper)；在分布式存储集群103中可以包括节点设备1至m(m为大于或等于1的正整数)，每个节点设备包括可以是数据节点设备，还可以是协调节点设备。
其中，网关服务器101用于接收外部的读写请求，并将读写请求对应的读写事务分发至分布式存储集群103；比如，用户在登录终端上的应用客户端之后，触发应用客户端生成读写请求，调用分布式数据库系统提供的应用程序编程接口(Application Programming Interface，API)将该读写请求发送至网关服务器101；其中，API可以是任意一种关系型数据库系统提供的API，比如，该API可以是MySQL API。
在一些实施例中，该网关服务器101可以与分布式存储集群103中的任一个数据节点设备或任一协调节点设备可以是同一个物理机，也即是，让某个数据节点设备或协调节点设备兼具网关服务器101的功能。
全局时间戳生成集群102用于生成全局事务的全局提交时间戳(Global Timestamp，Gts)，该全局事务又称为分布式事务，是指涉及到多个数据节点设备的事务；例如全局读事务可以涉及到对多个数据节点设备上存储数据的读取，又例如，全局写事务可以涉及到对多个数据节点设备上的数据写入。全局时间戳生成集群102在逻辑上可以视为一个单点，也可以通过一主三从(分别是一个主设备和与该主设备对应的三个辅助设备)的架构来提供具有更高可用性的服务，采用集群的形式来实现该全局提交时间戳的生成；当一主三从架构中的一个设备故障时，可以通过一主三从架构中的其他设备继续实现该全局提交时间戳的生成，从而可以防止单点故障，也就规避了单点瓶颈问题。
在本申请实施例中，全局提交时间戳是一个在分布式数据库系统中全局唯一且单调递增的时间戳标识，能够用于标志每个事务全局提交的顺序，以此来反映出事务之间在真实时间上的先后关系(事务的全序关系)，全局提交时间戳可以采用物理时钟、逻辑时钟、混合物理时钟或者混合逻辑时钟(Hybrid Logical Clock，HLC)中至少一项，本申请实施例不对全局提交时间戳的类型进行限定。
示例性地，全局提交时间戳可以采用混合物理时钟的方式生成，全局提交时间戳可以由八字节组成，每字节包括八位，共64位；其中，前44位可以为物理时间戳的取值(也即Unix时间戳，精确到毫秒)，这样共计可以表示2 44个无符号整数，因此理论上一共可以表示约为557.8
Figure PCTCN2022087848-appb-000001
年的物理时间戳；其中，后20位可以为在某一毫秒内的单调递增计数，这样每毫秒有2 20个(约100万个)计数，基于上述数据结构，如果单机(任一数据节点设备)的事务吞吐量为10w/s，理论上可以支持包含1万个节点设备的分布式存储集群103；同时，全局提交时间戳的数量代表了系统理论上所能支持的总事务数，基于上述数据结构，理论上系统可以支持(2 44-1)*2 20个事务。这里是对一种全局提交时间戳的定义方法的示例性说明，根据业务需求的不同， 可以对全局提交时间戳的位数进行扩展，以满足对更多的节点数、事务处理数的支持，本申请实施例不对全局提交时间戳的定义方法进行限定。
在一些实施例中，该全局时间戳生成集群102可以是物理独立的，也可以和分布式协调系统104合并到一起。
其中，分布式存储集群103可以包括数据节点设备和协调节点设备，每个协调节点设备可以对应于至少一个数据节点设备，数据节点设备与协调节点设备的划分是基于事务的不同而划分的；以某一全局事务为例，全局事务的发起节点可以称为协调节点设备，全局事务所涉及的其他节点设备称为数据节点设备，数据节点设备或协调节点设备的数量可以是一个或多个，本申请实施例不对分布式存储集群103中数据节点设备或协调节点设备的数量进行限定。由于本申请实施例所提供的分布式数据库系统中缺乏全局事务管理器，因此在该系统中可以采用组织分布式事务规范(eXtended Architecture，XA)/二阶段提交(Two-Phase Commit，2PC)技术来支持跨节点的事务(全局事务)，保证跨节点写操作时数据的原子性和一致性；此时，协调节点设备相当于2PC算法中的协调者，而该协调节点设备所对应的各个数据节点设备相当于2PC算法中的参与者。
在本申请实施例中，每个数据节点设备或协调节点设备可以是单机设备，也可以采用主备结构(也即是为一主多备集群)；如图1所示，以节点设备(数据节点设备或协调节点设备)为一主两备集群为例进行示意，每个节点设备中包括一个主机和两个备机，每个主机或备机都对应配置有代理(Agent)设备，代理设备可以与主机或备机是不同的物理设备，当然，代理设备还可以作为主机或备机上的一个代理模块；以节点设备1为例，节点设备1包括一个主数据库及代理设备(主Database+Agent，简称主DB+A gent)，此外还包括两备数据库及代理设备(备Database+A gent，简称备DB+A gent)。
示例性地，每个节点设备所对应的主机或备机的数据库实例集合称为一个集合(SET)；例如，假设某一节点设备为单机设备，那么该节点设备的SET仅为该单机设备的数据库实例，假设某一节点设备为一主两备集群，那么该节点设备的SET为主机数据库实例以及两个备机数据库实例的集合；此时可以基于云数据库的强同步技术来保证主机的数据与备机的副本数据之间的一致性；这里，每个SET可以进行线性扩容，以应付大数据场景下的业务处理需求，在一些金融业务场景下，全局事务通常是指跨SET的转账。
分布式协调系统104可以用于对网关服务器101、全局时间戳生成集群102或者分布式存储集群103中至少一项进行管理；在本申请实施例中，可以通过终端上的调度器(Scheduler)访问该分布式协调系统104，从而基于前端的调度器来控制后端的分布式协调系统104，实现对各个集群或服务器的管理。例如，可以通过调度器来控制ZooKeeper将某一个节点设备从分布式存储集群103中删除，也即是使得某一个节点设备失效。
上述图1提供了一种轻量级的全局事务处理的架构图，是一种类分布式数据库系统。整个分布式数据库系统可以看作是共同维护一个逻辑上的数据表，这个数据表中存储的数据通过主键被打散到分布式存储集群103中的各个节点设备中，每个节点设备上存储的数据是独立于其他节点设备的，从而实现了节点设备对逻辑数据表的水平切分。由于在上述系统中能够将各个数据库中各个数据表水平切分后进行分布式地存储，因此，这种系统也可以称为具有“分库分表”的架构。
在上述分布式数据库系统中，已经基于XA/2PC技术实现了写操作时数据的原子性和一致性，如图1中示出的分布分表架构，为一个局部事务管理器，不是全局的，故还存在读操作时数据的一致性问题；而本申请实施例提供的事务处理方法，能够实现分布式事务处理，并且通过构造轻量的、去中心化的分布式事务处理机制，能够为分布式数据库系统提供水平扩展等能力，提升分布式数据库系统的应用范围，进而能够解决写操 作时数据的原子性和一致性、以及读操作时数据的一致性问题，从而提升事务处理效率。
本申请实施例提供的事务处理方法，可以应用于上述采用了分库分表架构的分布式数据库系统中；例如，该分布式数据库系统为分布式事务型数据库系统，当然也可以是分布式关系型数据库系统；此外，本申请实施例提供的事务处理方法也可以应用于一些单机数据库系统中；当本申请实施例提供的事务处理方法应用于分布式数据库系统时，能够实现分布式事务处理，且能够通过灵活地隔离级别，提高事务处理效率。
在一些实施例中，上述网关服务器101、全局时间戳生成集群102、分布式存储集群103以及分布式协调系统104所构成的分布式数据库系统，可以视为一种向用户终端提供数据服务的服务器，该服务器可以是独立的物理服务器，也可以是多个物理服务器构成的服务器集群或者分布式系统，还可以是提供云服务、云数据库、云计算、云函数、云存储、网络服务、云通信、中间件服务、域名服务、安全服务、内容分发网络(Content Delivery Network，CDN)、以及大数据和人工智能平台等基础云计算服务的云服务器。这里，上述用户终端可以是智能手机、平板电脑、笔记本电脑、台式计算机、智能音箱、智能手表等，但并不局限于此。终端以及服务器可以通过有线或无线通信方式进行直接或间接地连接，本申请在此不作限制。
下面将对数据库系统中所涉及到的一些基本术语以及符号表示进行介绍。
事务：是数据库管理系统在执行操作的过程中的一个逻辑单位，由一个有限的数据库操作序列构成，是数据库系统操作的最小执行单位。
变量，事务是数据库关系系统中的一个数据单位，变量是数据库操作的作用者(或者说被操作的数据对象)；在一些实施例中，变量也称为数据项。其中，一个变量可以是一个元组(Tuple)或者记录(Record)，也可以是一个页面(Page)或者一个表(Table)对象等。一个变量可以包含若干变量版本(简称为“版本”)，每当事务对变量进行更新时，则会添加新的变量版本，变量的各个变量版本可以以自然数作为版本号标识，版本号越大，表示变量版本越新。
操作：一个数据库操作由操作类型、事务和变量版本三部分构成；其中，操作类型可以包括读(Read，R)和写(Write，W)两种。例如，事务T i读取变量x，生成了变量x的新版本x m，上述读操作可以记为R i[x m]；又例如，事务T j对变量y进行更新，生成了变量y的新版本y n，上述写操作可以记为W j[y n]；其中，i和j为自然数，分别为对应操作所属的事务号，m和n为自然数，分别为对应变量的版本号。另外，在无需区别R和W时，也可以用O来代表一个操作。
可串行化：可串行化是一个调度，也可以理解为多个事务之间的执行方式；多个事务之间的执行有先后顺序，如果事务之间没有共同操作的变量，则事务之间的执行顺序前后置换是没有关系的；但是如果事务间存在共同操作的变量，则事务间先后执行的顺序则需要区分；对于存在共同操作的变量的多个并发执行的事务，如果其执行结果“等价”于某个“串行化调度”，则这个调度为“可串行化的调度”。满足“可串行化的调度”则具有了可串行化属性。因此，可串行化保证了多个事务并发时的执行顺序对数据的一致性没有影响。
数据库系统中的每个事务拥有两个事务数据集合，分别为事务的写集和事务的读集，其含义为：写集DSW(T)用于存储事务T所写入的新的数据版本，读集DSR(T)用于存储事务T所读取的数据版本。
本申请实施例所提供的事务处理方法，是在数据状态一致性模型(也可以简称为“数据状态模型”)的基础上运行的，本申请实施例基于冲突可串行化理论，对数据异常进行了统一，并提供了一种通用形式的冲突环图，用于表示事务之间的关联关系以及事务对应的读写操作所作用的变量，下面对本申请涉及的基础概念进行介绍。
1、调度；一个调度是指由一组事务的多个操作组成的序列，记为s。一个调度s中所有的事务记为TS(s)，一个调度s中所有的操作记为O(s)，一个调度s中所有的带有版本号标识变量的集合记为VS(s)。例如，调度s＝R 1[x 0]R 2[y 0]W 3[x 1]W 4[y 1]R 2[x 1]R 1[y 1]，表示该调度s的操作序列来自4个事务，即TS{T 1，T 2，T 3，T 4}，涉及2个变量x和y，且变量x和y分别有两个版本。
示意性地，如果一个调度s中，任意两个事务的操作各自以事务为单位相邻，也即是，当执行完一个事务的全部操作后再执行下一个事务，则称该调度s为串行调度。例如，一个串行调度s表示为s＝R 1[x 0]R 1[y 0]R 2[y 0]R 2[x 0]W 3[x 1]W 4[y 1]。
2、冲突(Conflict)；冲突也称为冲突操作，当有两个操作满足如下三个条件，则称这两个操作为冲突操作。其中，三个条件为：1)两个操作属于不同的事务；2)至少一个操作为写操作；3)两个操作所操作的对象为同一个对象(读同一个对象或写同一个对象)，在本申请实施例中，对象也称为变量。
示意性地，设O i[x m]O j[x n](i≠j，m<n)为调度s中的两个事务的操作，分别为事务T i和T j作用于同一个变量x上的两个操作。若O i[x m]O j[x n]属于R i[x m]W j[x m+1]、W i[x m]R j[x m]和W i[x m]W j[x m+1]三种冲突中的任一种，则称O i[x m]O j[x n]为冲突，冲突在Oi和Oj之间构成偏序关系，将包含有调度s中全部冲突的集合记为conf(s)。在本申请实施例中，上述三种冲突可以依次分别简写为RW、WR以及WW。
3、冲突等价(Conflict Equivalence)；对于不同的调度s和s′，若满足如下两个条件，则称s和s′为冲突等价。其中，两个条件为：1)调度s和s′包括同样的事务集合，也即是每个事务中的操作的顺序是固定的，不能在不同的调度下发生变化；2)调度s和s′包括同样的冲突集合。
示意性地，对于不同的调度s和s′，若O(s)＝O(s′)，且conf(s)＝conf(s′)，则称s和s′为冲突等价，记为s≈s′。
例如，以下为两个冲突等价的调度。
s＝R 1[x 0]R 1[y 0]W 2[x 1]W 1[y 1]R 2[z 0]W 1[x 2]W 2[y 2]；
s′＝R 1[x 0]R 1[y 0]W 2[x 1]W 1[y 1]R 2[z 0]W 1[x 2]W 2[y 2]。
4、冲突可串行化(Conflict Serializability)；若一个调度s存在一个串行化调度s′，使得这两个调度为冲突等价(也即是满足s≈s′)，则称s为冲突可串行化调度。
5、冲突环图(Conflict Cycle Graph，CCG)；示意性地，在一个调度s中，存在多个事务t∈TS(s)，若多个事务t构成的图满足如下三个条件，则称该环图为冲突环图，其中，CCG(s)＝(V,E)。下面对三个条件进行说明。
1)V＝VS(s)，表示为CCG图的顶点集，该顶点集中的元素称为顶点，一个顶点对应一个事务；其中，一个顶点T i满足T i∈TS(s)；
2)E为V×V的子集，也可以称为边集，该边集中的元素称为有向边，记为<T i，T j>，也可以简称为边，其中，
Figure PCTCN2022087848-appb-000002
因此，有向边也可以记为与上述“冲突”相似的形式，例如，将有向边记为W i[x m]W j[x m+1]，本申请实施例对此不作限定。
3)<T i，T j>∈E，<T j，T k>∈E，…，<T p，T i>∈E，i≠j≠k≠…≠p，则CCG图为一个有向环构成的图。
例如，参考图2，图2是本申请实施例提供的一种冲突环图的示意图。如图2所示，图中T 1和T 2分别为冲突环图2-1的顶点，且T 1和T 2之间通过两条边相连，构成冲突环图；其中，两条边分别表示为R 1[x 0]W 2[x 1]和W 2[x 1]R 1[x 1]。
在本申请实施例中，基于冲突环图，得到下述三种推论，下面分别进行说明。
1)一个冲突环图至少有两条边。
示意性地，如果冲突环图只有一条边，则冲突环图中仅存在两个事务，且这两个事务是串行事务，因此不会构成有向环；如果有两条边构成有向环，例如，冲突环图中的第一条边使得T i在T j之前先发生，冲突环图中的第二条边使得T j在T i之前先发生，也即是不存在等价的可串行化调度，则这两个事务T i和T j冲突。
2)一个冲突环图至多有无数条边。
示意性地，一个调度s对应的TS(s)中可以存在无数个事务，相应地，一个冲突环图中可以存在无数个顶点，也即可以存在无数条边。
3)一个冲突环图如果去掉任何一条边，则不再构成环。
示意性地，根据上述冲突环图的第三个条件得知，在冲突环图构成的有向环中，存在i≠j≠k≠…≠p，也即是任意两条边是不同的，因此对于一个冲突环图，若去掉任何一条边，则不再构成环。
6、冲突一致性状态图(Conflict Consistency State Graph，CCSG)；示意性地，在一个调度s中，存在多个事务t∈TS(s)，若多个事务t构成的图满足如下四个条件，则称该图为冲突一致性状态图，其中，CCSG(s)＝(V,E)。下面对四个条件分别进行说明。
1)CCSG图中调度s的定义满足上述CCG图中调度s的定义，即CCG(s)和CCSG(s)之间可以等价转换。
2)对于CCSG(s)，V＝VS(s)称为CCSG图的顶点集，其元素称为顶点，一个顶点v i满足vi∈VS(s)，该顶点由两种类型的数据构成，一是事务标识(Identification，ID)，二是一个列表(List)，该列表用于存放变量的不同版本。
3)E为V×V的子集，也可以称为边集，该边集中的元素称为有向边，在CCSG图中，边分为下述两种，对于以下两种边，统一表达为<V i，V j>，这样的边源自CCG图的边的等价变形，故属于冲突操作的变形。下面对两种边分别进行说明。
第一种边为一致性状态边，记为<x m，y n>，简称事务边E T。该类型的边包括同一个事务的操作，因此该事务内的数据状态满足一致性要求。其中，x＝y且m≠n；或者x≠y。由于CCSG图等价于CCG图，故一致性状态边也可表示为R i[x m]R i[y n]，E T可以作为该边的标签。
第二种边为状态变迁边，记为<x i，x i+1>，简称状态边E S。该类型的边是由某个写事务写某个变量，致使数据状态发生变迁而构成，因此变量的版本发生变化。由于CCSG图等价于CCG图，故一致性状态边也可表示为W j[x m+1]。
4)
Figure PCTCN2022087848-appb-000003
也
Figure PCTCN2022087848-appb-000004
使得CCSG图为一个有向环构成的图。也即是：V 1→E 1→V 2→E 2…V k→E k→V 1为一个有向环构成的图。
7、CCG图向CCSG图转换的等价转换规则；其中，CCG图向CCSG图的等价转换规则包括下述四条，下面分别进行说明。
第一条为边拆分。其中，CCG图的任何一条边，由两个操作即一个冲突构成，其可以拆分为两个单独的边。示意性地，边的拆分方式包括如下三种，每一种拆分出两个子边，下面对三种拆分方式进行说明。
1)例如，边表示为R 1[x 0]W 2[x 1]，对该边进行拆分，得到R 1[x 0]和W 2[x 1]，同时得到变量x的两个版本x 0和x 1。
2)例如，边表示为W 2[y 1]R 3[y 1]，对该边进行拆分，得到W 2[y 1]和R 3[y 1]，同时得到变量y的一个版本y 1。
3)例如，边表示为W 3[z 1]W 1[z 2]，对该边进行拆分，得到W 3[z 1]和W 1[z 2]，同时得到变量z的两个版本z 1和z 2。
第二条为顶点转换。其中，将变量的版本作为CCSG图的顶点，也即是把上一步的版本转换为顶点；这里，以上述第一条举例得到的顶点为例，CCSG图的顶点包括x 0、x 1、y 1、z 1以及z 2。同一个变量的多个版本纵向排列，被同一个事务作用过的不同变量的版本之间横向排列，其中，纵向可以是指与屏幕显示信息对应的水平方向，还可以是指与屏幕显示信息对应的水平方向垂直的方向，等等，本申请实施例对此不作限定；但同一个变量的多个版本的排列方向，与被同一个事务作用过的不同变量的版本之间的排列方向是相对的。需要说明的是，此处顶点的排列方式并非特定要求，在一些实施例中，还可以按照其他排列方式进行排列，本申请实施例对此不作限定。
第三条为在相邻版本的同一变量对应的顶点之间添加边。其中，以上述第二条得到的新顶点之间的变迁关系为CCSG图的新边。例如，前述的事务T 2的相关子边包括：W 2[x 1]和W 2[y 1]，则把x 1和y 1水平并列，从而x 0和x 1之间存在一条W 2[x 1]边。
第四条为在同一事务所作用的变量对应的顶点之间添加边。其中，在同一个事务之间，构造CCSG图的一致性状态边。例如，继续以前述顶点为例，在x 1和y 1之间添加边，其边的标签为事务T 2。
8、CCSG图向CCG图转换的等价转换规则；其中，CCSG图向CCG图的等价转换规则主要包括下述三条，下面分别进行说明。
第一条为顶点合并。其中，对于CCSG图，将同一个事务操作过的变量合并为一个顶点，并将该顶点命名为该事务的事务标识，该顶点的表示方式，等价于前述CCG图的顶点表示方式，这里不再重复描述。
第二条为在相邻顶点之间添加边；包括以下两点，第一点是保留变量的状态变迁。例如，由边R 1[x 0]W 2[x 1]可知，变量的状态变迁由T 1指向T 2，因此添加的新边为T 1→T 2。第二点是如果没有写操作发生，则按照原始的CCG图中发生的冲突关系构造新边。需要说明的是，应用于存在WR冲突关系的情况，在存在WR冲突关系的情况下，对应的边由W所在的事务指向R所在的事务。
第三条为得到的CCG图存在环，且可以忽略其有向的属性，也即是对CCSG进行转换得到的CCG图为一个无向有环图。
需要说明的是，在本申请实施例中，CCSG图即为数据状态一致性模型的基础。也即是，以变量的版本为顶点，以事务的读写操作为状态变迁的边或以事务的一致性状态边为边，构成的图，即为数据状态一致性模型。在该数据状态一致性模型中，若存在环则存在数据异常，如不存在环，则不存在数据异常。
9、数据异常(Data Anomalies，DA)；一个调度s中，若存在一个子调度s′，也即是
Figure PCTCN2022087848-appb-000005
且s′存在冲突环图，则称调度s存在数据异常，s′即为某一个具体的数据异常。
另外，基于上述描述的冲突环图以及数据异常，得到下述三种推论，下面分别进行说明。
1)数据异常有无数个。基于冲突环图中的第二条推论得知，冲突环图中可以存在 无数个顶点和无数条边，因此，数据异常有无数个。
2)存在无数个细分类的数据异常。由于冲突环图中的顶点不同则数据异常不同，冲突环图中的边不同则数据异常不同，冲突环图中的顶点和边中的至少一种的个数不同则数据异常不同，因此存在无数个细分类的数据异常。
3)采用形式化表达式对每个细分类的数据异常用表达，并为该细分类的数据异常命名。
应理解，一个数据异常是对应存在冲突环图的调度s的子集，因此一个细粒度的数据异常可以由构成冲突环图的该调度s的子集部分的表达式来表示。
例如，以丢失更新异常为例，该丢失更新异常对应的冲突环图参考图3，图3是本申请实施例提供的另一种冲突环图的示意图。如图3所示，在该冲突环图3-1中，V＝{T 1，T 2}，E＝{<R 1[x 0]W 2[x 1]>，<W 2[x 1]W 1[x 2]>}，则该丢失更新异常的形式化定义为R i[x m]...W j[x m+1]...W i[x m+2]。
又例如，以读偏序异常为例，该读偏序异常对应的冲突环图参考图4，图4是本申请实施例提供的又一种冲突环图的示意图，如图4所示，在该冲突环图4-1中，V＝{T 1，T 2}，E＝{<R 1[x 0]W 2[x 1]>，<W 2[y 1]R 1[y 1]>}，则该读偏序异常的形式化定义为R i[x m]...W j[x m+1]...Wi[y n]...R i[y n]。
需要说明的是，此处以上述两种数据异常为例，结合对应的冲突环图，对数据异常的形式化进行了举例说明，其他数据异常对应的冲突环图以及数据异常的形式化定义将在后续进行介绍。
10、回滚率；当利用封锁技术来抑制并发并避免数据异常产生时，使得原本可以提交的事务被回滚，也就是假回滚。下面对在本申请实施例所涉及的回滚的信息分别进行说明。
1)、数据异常回滚；对于调度s，当由于数据异常出现而导致的事务的回滚，称为数据异常回滚，也称为真回滚(True Rollback，TR)。
2)、算法回滚；对于调度s，当没有数据异常存在时，通过并发访问算法确定可能发生数据不一致，而致使的事务回滚，称为算法回滚，也称为假回滚(False Rollback，FR)。
3)真回滚率；假设P个调度中，如果U个调度中每个调度都存在真回滚，则U/P称为真回滚率。真回滚率反应了应用背景下数据异常出现的概率。
4)假回滚率：假设P个调度中，如果V个调度中每个调度都存在假回滚，则V/P称为假回滚率。假回滚率反应了并发事务的并发执行能力，假回滚率越低则并发度越高，且计算资源的利用率越高，事务并发效率越高。
以上对本申请实施例涉及的基础概念进行了介绍，下面将对本申请的事务处理方法进行说明。在本申请实施例中，以上述基础概念为理论基础，利用事务与事务之间构成的冲突环图来进行数据异常的识别，能够有效识别出事务在执行过程中出现的数据异常，从而提高事务处理的效率。
参考表1，表1描述了本申请实施例涉及到的一些符号及对应含义。
表1
Figure PCTCN2022087848-appb-000006
Figure PCTCN2022087848-appb-000007
基于上述描述的基础概念以及表1所示的符号和对应含义，下面参考图5，对本申请实施例提供的一种事务处理方法进行说明。图5是本申请实施例提供的一种事务处理方法流程图，如图5所示，本申请实施例提供的事务处理方法应用于数据库系统中任一节点设备，当数据库系统为单机数据库系统时，该节点设备可以是单机设备；当数据库系统为分布式数据库系统时，该节点设备可以是协调节点设备或者数据节点设备；本申请实施例包括步骤501和步骤502，下面对各步骤分别进行说明。
步骤501、节点设备确定目标事务的并发事务，并发事务与该目标事务之间包括作用于同一变量的读写操作，目标事务为待提交事务。
在本申请实施例中，该目标事务是全局事务或局部事务；其中，该全局事务是指涉及到跨节点操作的事务，全局事务也称为分布式事务；而局部事务则是指仅涉及单个节点操作的事务，局部事务也称为本地事务；本申请实施例对于目标事务的类型不进行限定。这里，读写操作是指读操作和写操作中的至少一种。
其中，节点设备在执行目标事务时，通过事务读集和写集，并对至少一个候选并发事务进行筛选，以从筛选出的至少一个候选并发事务中确定出目标事务的并发事务(确定并发事务的具体实施方式将在后续进行介绍)。这里，目标事务可以由终端发起，此时终端与节点设备建立用于处理目标事务的会话，终端向节点设备发送目标事务的执行请求，节点设备响应于目标事务的执行请求，开始执行该目标事务。在一些实施例中，如果终端与节点设备已经建立过一个会话，那么无需在两者之间建立新的会话，只需要复用当前已建立的会话即可。
步骤502、节点设备获取目标事务的读集和并发事务的写集之间的第一交集，并获取目标事务的写集和并发事务的读集之间的第二交集，当第一交集和第二交集中的至少一项为非空数据集，且目标事务与并发事务冲突时，基于目标事务和并发事务所作用的同一变量的版本变更次数和目标变量列表，确定数据异常类型，目标变量列表包括目标事务和并发事务所作用的同一变量。
在本申请实施例中，目标事务与并发事务冲突是指目标事务与并发事务中存在至少两个操作为冲突操作，若此时提交目标事务，将导致数据库系统出现数据异常。节点设备在确定上述第一交集和第二交集中存在至少一项为非空数据集，且目标事务与并发事务冲突时，基于该版本变更次数和该目标变量列表，确定数据异常类型并将数据异常类 型进行上报。其中，非空数据集是指不为空集的数据集，即为包括集合元素的数据集。
在本申请实施例提供的事务处理方法中，节点设备在确定目标事务的并发事务后，在该目标事务的读集和该并发事务的写集之间的第一交集和该目标事务的写集和该并发事务的读集之间的第二交集中，存在至少一项不为空的情况下，对目标事务与并发事务是否冲突进行判断，若目标事务与并发事务冲突，则根据这两个事务所作用的相同变量以及相同变量的版本变更次数，来确定数据异常类型。这种方式能够在目标事务的执行过程中，确认目标事务与并发事务是否真正构成冲突；并且，通过两个事务所作用的相同变量来确定数据异常类型，能够基于可串行化理论，识别出数据库系统中各种各样的数据异常，保证了数据状态的一致性，也提高了数据库系统的事务处理效率。
上述图5是对本申请提供的事务处理方法的简要说明，下面结合图6，对本申请实施例提供的事务处理方法进行详细介绍。图6是本申请实施例提供的另一种事务处理方法流程图，如图6所示，本申请实施例提供的事务处理方法应用于数据库系统中任一节点设备，当数据库系统为单机数据库系统时，该节点设备可以是单机设备；当数据库系统为分布式数据库系统时，该节点设备可以是协调节点设备或者数据节点设备；本申请实施例包括下述步骤601至步骤609，下面对各步骤分别进行说明。
步骤601、节点设备响应于目标事务的执行指令，对目标事务的读集和写集进行初始化。
在本申请实施例中，节点设备响应于目标事务的执行指令，将该目标事务的读集和写集初始化为空集，并为目标事务分配全局唯一的事务ID，也即是事务标识。这里，不同事务的事务ID按照节点设备接收到相应执行指令的时间顺序整数递增，例如，节点设备在t1时刻接收到目标事务的执行指令，将该目标事务的事务ID命名为1000，若节点设备在t2时刻接收到另一事务的执行指令，则节点设备将该另一事务的事务ID命名为1001，本申请实施例对此不作限定。
在本申请实施例中，在该初始化过程中，节点设备在数据库系统启动时，节点设备的操作系统分配一块内存空间，该内存空间用于维护至少一个事务的读集和写集；当目标事务开始执行时，节点设备从该内存空间中申请一块内存，该内存用于管理该目标事务的读集和写集，从而在节点设备上完成了目标事务的读集和写集的创建，并且，将创建出的读集和写集均初始化为空集。
下面对目标事务的读集和写集的更新策略进行介绍。
在完成读集和写集进行初始化后，节点设备根据目标事务的执行语句，确定该目标事务是否涉及对变量的更新操作，当确定涉及对变量的更新操作时，节点设备响应于该目标事务对任一变量进行更新，将该变量添加至该目标事务的写集中，并为该变量分配版本号。例如，当某一事务T对变量x进行更新时，将变量x添加至事务T的写集中，并为变量x分配版本号。不同事务对同一个变量的写操作的版本号按整数递增；此时，节点设备执行读操作即可获得变量的版本号。即数据库系统为每个变量维护一个递增的版本号。另外，节点设备根据目标事务的执行语句，对任一变量进行读取时，所读取的变量是最新的且满足读已提交规则的变量。
上述更新策略也可以理解为目标事务的读集和写集随着事务操作的进行而实时维护。若发生读操作，则被读取的变量进入读集；若发生写操作，则被读取的变量进入写集。同一个事务写同一个变量多次则有多个不同的新版本，在写集中用最新的变量版本替代旧的变量版本。
需要说明的是，本步骤601也即是上述步骤501中涉及的事务读集和写集形成的过程，为读写阶段事务读写集合的形成步骤。
步骤602、节点设备响应于目标事务中每个操作的执行指令，获取目标事务的至少 一个候选并发事务。
在本申请实施例中，对于目标事务的每一个操作(该操作可以是读操作也可以是写操作)，在该操作发生时，进入准备阶段，节点设备进入临界区，遍历该目标事务的读集和写集，以及获取目标事务的至少一个候选并发事务(比如所有并发事务)的事务ID，并将该至少一个候选并发事务的事务ID存入到一个链表(Typescript，TS)中。
在本申请实施例中，节点设备在获取至少一个候选并发事务的过程中，内存中的每个变量上都记载曾经读写过该变量但尚未提交的事务的事务ID(简称为活跃事务ID)，每个变量上记载的活跃事务ID可以是一个，也可以是多个，还可以为空。节点设备通过获取读集和写集中各个变量上所记载的各个活跃事务ID，即可得到该至少一个候选并发事务的事务ID。
步骤602也可以理解为节点设备在目标事务的每个操作发生时，开始做准备工作，进入目标事务的准备阶段；其中，准备阶段是为事务T是否可以提交做好事务并发访问控制异常验证前的准备工作，节点设备在临界区中找到至少一个候选并发事务的事务ID之后，退出临界区。
需要说明的是，步骤602也即是上述步骤501中的准备阶段，用于筛选出至少一个候选并发事务。
步骤603、节点设备从至少一个候选并发事务中确定目标事务的并发事务，并发事务与目标事务之间包括作用于同一变量的读写操作。
在本申请实施例中，节点设备在目标事务的每个操作发生时，获取该目标事务的至少一个候选并发事务；对于至少一个候选并发事务中的任一个候选并发事务，节点设备根据该候选并发事务、以及目标事务的读集和写集，对该候选并发事务是否为目标事务的并发事务进行判断；若该候选并发事务与目标事务之间包括作用于同一变量的读写操作，则将该候选并发事务确定为该目标事务的并发事务，执行步骤604至步骤607；否则，将该候选并发事务重新加入链表TS的尾部。
其中，节点设备基于可串行化理论，以该至少一个候选并发事务和目标事务之间是否构成冲突环图，来进行一致性检验。下面以链表TS中的任一个候选并发事务为例，对本步骤603的实施过程进行详细说明；这里，步骤603的实施过程包括步骤6031至步骤6035，下面对各步骤分别进行说明。
步骤6031、节点设备获取目标事务的读集和候选并发事务的写集之间的第一候选交集、目标事务的写集和候选并发事务的读集之间的第二候选交集、以及目标事务的写集和候选并发事务的写集之间的第三候选交集。
其中，当目标事务为T，候选并发事务为TL时，节点设备将目标事务T与该候选并发事务TL之间的有向边的数量置为0，将目标事务与候选并发事务所作用的相同变量的版本变更次数置为0，将目标变量列表置为空集。其中，该有向边的数量用于表示目标事务与该候选并发事务之间是否冲突；该版本变更次数用于表示目标事务与该候选并发事务所作用的相同变量的数据状态；该目标变量列表用于存储目标事务与该候选并发事务所作用的相同变量。
在本申请实施例中，节点设备用动边交叉值(Dynamic Line Intersection，DLI)来表示有向边的数量，用变量状态值(Variable State，VS)来表示版本变更次数，用变量列表(Variable List，VL)来表示目标变量列表，也即令DLI＝0；VS＝0；VL＝空集。
在本申请实施例中，第一候选交集表示为“S1＝DSR(T)∩DSW(TL)”；第二候选交集表示为“S2＝DSR(TL)∩DSW(T)”；第三候选交集表示为“S3＝DSW(T)∩DSW(TL)”。
在本申请实施例中，节点设备在获取第一候选交集、第二候选交集以及第三候选交集时，可以使用哈希表存储目标事务和候选并发事务各自的读写集合，从而能够在线性 时间复杂度内得到对应的交集。
步骤6032、若第一候选交集、第二候选交集以及第三候选交集之间的并集为空集，则节点设备将候选并发事务重新加入链表TS的尾部；若第一候选交集、第二候选交集以及第三候选交集中存在至少一项不是空集，则节点设备执行下述步骤6033至步骤6035。
其中，若第一候选交集、第二候选交集以及第三候选交集之间的并集为空集(即第一交集、第二交集以及第三交集均为空集)，说明该候选并发事务并不是目标事务的并发事务。若第一候选交集、第二候选交集以及第三候选交集中存在至少一项不是空集，说明该候选并发事务为目标事务的并发事务，则节点设备将该候选并发事务确定为目标事务的并发事务，也即是本步骤603所涉及的并发事务，执行下述步骤6033至步骤6035；另外，当节点设备确定候选并发事务为目标事务的并发事务时，第一候选交集即为第一交集，第二候选交集即为第二交集，第三候选交集即为第三交集。
下面以该候选并发事务为确定好的并发事务为例，对步骤6033至步骤6035进行说明。
步骤6033、若该第一交集不为空集，节点设备对有向边的数量进行增量处理，并将第一交集中的变量添加到目标变量列表中；若第一交集中存在版本不同的变量，节点设备对版本变更次数进行增量处理。
其中，增量处理是指将对应的值自增一。示意性地，以有向边的数量为DLI，版本变更次数为VS为例，上述两种增量处理分别表示为DLI＝DLI++和VS＝VS++。另外，节点设备将该第一交集中的变量添加到该目标变量列表中是指按照预设顺序，将变量有序添加到该目标变量列表中。
步骤6034、若第二交集不为空，节点设备对有向边的数量进行增量处理，将第二交集中的变量添加到目标变量列表中；若第二交集中存在版本不同的变量，节点设备对版本变更次数进行增量处理。
其中，步骤6034与上述步骤6033在实现过程上类似，故在此不再重复描述。
步骤6035、若第三交集不为空集，节点设备基于并发事务的提交状态，确定数据异常类型；若第三交集为空集，节点设备执行后续步骤604。
其中，若第三交集不为空集，说明目标事务与并发事务之间出现了写写冲突，而写写冲突是数据一致性状态模型下导致数据错误的原因之一，也即为禁止脏写数据异常；因此，在这种情况下，节点设备基于该并发事务的提交状态，确定数据异常类型，并报告写写异常发生，结束当前流程，对目标事务进行回滚。而当第三交集为空集时，表明写写冲突未发生，从而节点设备执行后续步骤604。
在一些实施例中，若该并发事务未提交且该目标事务的目标参数T.no_committed为一，则节点设备确定数据异常类型为脏写异常；其中，该目标参数T.no_committed用于表示该目标事务的读写集合所对应的已提交事务数量；由于在循环过程中，如果上一个并发事务与目标事务之间不存在数据异常，那么在执行本次循环之前，需要将上一个并发事务与目标事务进行合并，并将合并后得到的新的事务确定为本次循环的目标事务，而合并可通过对两事务的读写集合进行合并实现；因此在任一次循环中，目标事务的读写集合有可能是经过合并后的读写集合，在目标事务的读写集合中包括已经提交的事务的读写集合的成分的情况下，目标参数T.no_committed用于描述读写集合中对应的已提交事务数量。
在一些实施例中，若该并发事务已提交且该第一交集与该第三交集之间的交集不是空集，确定数据异常类型为丢失更新异常。
示意性地，以第一交集、第二交集以及第三交集分别表示为S1、S2以及S3为例， 若
Figure PCTCN2022087848-appb-000008
当满足如下任一条件时，节点设备确定数据异常类型，报告写写异常发生，循环终止；其中，待满足的条件包括：1)该并发事务没有提交完成且该目标事务的目标参数T.no_committed＝1，此时构成写写冲突，数据异常类型为脏写异常；2)该并发事务已经提交，且S1∩S3不是空集，此时数据异常类型为丢失更新异常。
需要说明的是，节点设备可以同步执行上述步骤6031至步骤6035，还可以按照任意顺序执行上述步骤6031至步骤6035，本申请实施例对此不作限定。
经过上述步骤603，节点设备从至少一个候选并发事务中确定出目标事务的并发事务，若目标事务与并发事务之间的第三交集为空集，则节点设备执行下述步骤604。
步骤604、若第一交集和第二交集中存在至少一项不为空集，且目标事务与并发事务冲突，则节点设备基于目标事务和并发事务所作用的相同变量的版本变更次数和目标变量列表，确定数据异常类型，目标变量列表包括目标事务和并发事务所作用的相同变量。
其中，该第一交集和该第二交集中，存在至少一项不为空集包括以下三种情况：1)第一交集不为空集，第二交集为空集；2)第一交集为空集，第二交集不为空集；3)第一交集不为空集，第二交集不为空集。若第一交集和第二交集满足上述三种情况中的任一种，且该目标事务与该并发事务冲突，则节点设备基于版本变更次数和目标变量列表，来确定数据异常类型。其中，节点设备基于目标事务与并发事务之间的有向边的数量，来确定目标事务与并发事务是否冲突，也即是，若目标事务与该并发事务之间的有向边的数量大于或等于二，则确定目标事务与并发事务冲突。
下面将对步骤604中确定数据异常类型的过程进行说明。首先通过以下四点，对本申请实施例所涉及的数据异常类型的所属类别、子类别、以及隔离级别分别进行介绍。
第一点、数据异常类型的所属类别。
在本申请实施例中，数据异常类型的所属类别包括写异常类别(Write Anomaly Type，WAT)、读异常类别(Read Anomaly Type，RAT)以及交叉异常类别(Intersect Anomaly Type，IAT)。
其中，若一个调度中存在作用于不同版本的同一变量的至少两个(称为第一指定数量)写操作(称为满足写异常条件)，则该数据异常类型的所属类别为写异常类别；若一个调度中不存在作用于不同版本的同一变量的至少两个写操作(称为不满足写异常条件)，且该调度中存在作用于相同版本的同一变量的读操作和写操作(称为满足读异常条件)，则该数据异常类型的所属类别为读异常类别；若一个调度中不存在作用于不同版本的同一变量的至少两个写操作(称为不满足写异常条件)，且该调度中不存在作用于相同版本的同一变量的读操作和写操作(称为不满足读异常条件)，且该调度中存在作用于不同版本的同一变量的读操作和写操作(称为满足交叉异常条件)，则该数据异常类型的所属类别为交叉异常类别。
下面结合上述表1所示的符号及对应含义，当一个调度s对应的CCG图中
Figure PCTCN2022087848-appb-000009
且i≠j，则数据异常类型的所属类别可以表示为下述三种形式，下面分别进行说明。
1、写异常类别。
若
Figure PCTCN2022087848-appb-000010
则该调度s存在数据异常，且该数据异常类型的所属类别为写异常类别。
2、读异常类别。
若
Figure PCTCN2022087848-appb-000011
且
Figure PCTCN2022087848-appb-000012
则该调度s存在数据异常，且该数据异常类型的所属类别为读异常类别。
3、交叉异常类别。
若
Figure PCTCN2022087848-appb-000013
且
Figure PCTCN2022087848-appb-000014
且
Figure PCTCN2022087848-appb-000015
则该调度s存在数据异常，且该数据异常类型的所属类别为交叉异常类别。
第二点、数据异常类型的子类别。
在本申请实施例中，第一点描述了根据冲突的差异，将数据异常类型分为写异常类别、读异常类别以及交叉异常类别三类；这里，为了提升数据异常识别的精细度，继续对数据异常的类型进行划分，得到子类别。
其中，若一个数据异常发生同一个变量上，则数据异常类型在所属类别中的子类别属于单元数据异常(Single-Meta Data Anomalies，SDA)；若一个数据异常发生两(称为第三指定数量)个变量上，则数据异常类型在所属类别中的子类别属于双元数据异常(Double-Meta Data Anomalies，DDA)；若一个数据异常不属于上述两种子类别，则数据异常类型在所属类别中的子类别属于多元数据异常(Multi-Meta Data Anomalies，MDA)。
示意性地，假设一个数据异常(Data Anomalies，DA，简写为da)中变量的个数表示为NV，事务的个数表示为NT，将NV和NT的组合称为数据异常的特征，记为Cda＝(NV，NT)，则上述数据异常类型的子类别表示为下述三种情况，下面分别进行说明。
1、单元数据异常。
若Cda＝(1，2)，则数据异常发生在两个事务一个变量上，则数据异常类型在所属类别中的子类别属于单元数据异常。
2、双元数据异常。
若Cda＝(2，2)，则数据异常发生在两个事务两个变量上，则数据异常类型在所属类别中的子类别属于双元数据异常。
3、多元数据异常。
若Cda≠(1，2)，且Cda≠(2，2)，则数据异常类型在所属类别中的子类别属于多元数据异常。
第三点、数据异常类型的细分类。
在本申请实施例中，按照上述第一点(数据异常类型的所属类别)和第二点(数据异常类型的子类别)所示的分类，给出了每种细分类的数据异常的所属类别、名称、对应的形式化表示、对应的CCG图以及对应的子类别。具体如表2以及图7至图9所示；其中，图7为本申请实施例提供的一种单元数据异常CCG图的示意图；图8为本申请实施例提供的一种双元数据异常CCG图的示意图；图9为本申请实施例提供的一种多元数据异常CCG图的示意图。
表2
Figure PCTCN2022087848-appb-000016
Figure PCTCN2022087848-appb-000017
需要说明的是，图7至图9所示的CCG图的示意图的相关描述，参见图2至图4对应的描述文段，本申请实施例在此不再重复描述。
需要说明的是，相比于单元数据异常和双元数据异常，多元数据异常的发生概率较小。下面对图9所示的多元数据异常CCG图对应的调度表达式进行示意性说明。
如图9中(a)图所示，冲突环图9-1中为台阶式写异常，台阶式写异常的调度表达 式为s＝R 1[x 0]W 2[x 1]W 2[y 1]W 3[y 2]R 3[z 0]W 1[z 1]，该调度中包含了WW冲突。
如图9中(b)图所示，冲突环图9-2中为台阶式读异常，台阶式读异常的调度表达式为s＝R 1[x 0]W 2[x 1]W 2[y 1]R 3[y 1]R 3[z 0]W 1[z 1]，该调度中包含了WR冲突，但没有包含WW冲突。
如图9中(c)图所示，冲突环图9-3中为台阶式交叉异常，台阶式交叉异常的调度表达式为s＝R 1[x 0]W 2[x 1]R 2[y 0]W 3[y 1]R 3[z 0]W 1[z 1]，该调度中包含了RW冲突，但没有包含WW冲突和WR冲突。
第四点、数据异常类型的隔离级别。
在本申请实施例中，按照上述第三点所示的数据异常的细分类，提供了两种隔离级别，分别为无读写异常(No Read-Write Anomalies，NRW)和无任何异常(No Anomalies，NA)；其中，隔离级别的分级依据是数据异常出现的允许程度，通过隔离级别，能够降低并发访问控制处理的复杂度。其中，NRW是指不允许出现WAT和RAT类数据异常，但不能消除IAT类数据异常；NA是指不允许任何数据异常发生，等价于ANSI-SQL标准定义的可串行化隔离级别。因此，NRW级别低于NA级别。
下面参考表3，描述了本申请实施例提供的隔离级别。
表3
Figure PCTCN2022087848-appb-000018
需要说明的是，节点设备基于表3中描述的隔离级别的相关信息，确定并发访问控 制处理。
在本申请实施例中，按照表3中描述的隔离级别，节点设备能够通过设置规则避免出现数据异常，达到NRW级别。例如，采用禁止WW边出现的规则来避免出现WAT异常；又例如，采用读已提交，快照读等方式来避免出现RAT异常。如此，能够减少隔离级别的层级个数，提高并发访问控制处理的效率。例如，采用可串行化快照隔离(Serializable Snapshot Isolation，SSI)技术，通过识别连续的2个RW边是否出现异常，即能达到NA级别，因此能够提高并发访问控制处理的效率。
经过上述四点，对本申请实施例所涉及的数据异常类型的所属类别、子类别、以及隔离级别进行了描述，下面以上述四点所描述的信息为基础，对本步骤604的实现过程进行详细说明；其中，步骤604包括步骤6041至步骤6043，下面对各步骤分别进行说明。
步骤6041、节点设备基于目标事务与并发事务中作用于同一变量的读写操作，确定所属类别。
其中，所属类别是指数据异常类型所属的类别；步骤6041包括下述三种情况，下面对该三种情况分别进行说明。
情况一、若目标事务与该并发事务中存在作用于不同版本的同一变量的第一指定数量(比如为两个)的写操作，则节点设备确定所属类别为写异常类别。
示意性地，当该目标事务为T i，该并发事务为T j，若
Figure PCTCN2022087848-appb-000019
则节点设备确定所属类别为写异常类别。
情况二、若该目标事务与该并发事务中不存在作用于不同版本的同一变量的两个写操作，且该目标事务与该并发事务中存在作用于相同版本的同一变量的读操作和写操作，则节点设备确定所属类别为读异常类别。
示意性地，假设该目标事务为T i，该并发事务为T j，若
Figure PCTCN2022087848-appb-000020
且
Figure PCTCN2022087848-appb-000021
则该节点设备确定所属类别为读异常类别。
情况三、若该目标事务与该并发事务中不存在作用于不同版本的同一变量的两个写操作，且该目标事务与该并发事务中不存在作用于相同版本的同一变量的读操作和写操作，且该目标事务与该并发事务中存在作用于不同版本的同一变量的读操作和写操作，则节点设备确定所属类别为交叉异常类别。
示意性地，假设该目标事务为T i，该并发事务为T j，若
Figure PCTCN2022087848-appb-000022
且
Figure PCTCN2022087848-appb-000023
且
Figure PCTCN2022087848-appb-000024
则节点设备确定所属类别为交叉异常类别。
步骤6042、节点设备基于数据异常类型的所属类别以及目标变量列表，确定在所属类别中的子类别。
其中，由上述步骤603中可知，目标变量列表中存储有该目标事务与该并发事务所作用的相同变量，也即是，节点设备基于目标变量列表，获取该目标事务与该并发事务所作用的相同变量的数量，从而结合上述三种子类别的描述，确定在所属类别中的子类别。
示意性地，本步骤6042包括下述三种情况，下面对该三种情况分别进行说明。
情况一、若该目标变量列表中的变量数量为第二指定数量(比如为一)，则节点设备确定该在所属类别中的子类别属于单元数据异常。
情况二、若该目标变量列表中的变量数量为第三指定数量(比如为二)，则节点设备确定该在所属类别中的子类别属于双元数据异常。
情况三、若该目标变量列表中的变量数量为第四指定数量，其中，第四指定数量与第二指定数量和第三指定数量均不同；也即是，该在所属类别中的子类别既不属于该单元数据异常，也不属于该双元数据异常；则节点设备确定该在所属类别中的子类别属于多元数据异常。
步骤6043、节点设备基于在所属类别中的子类别、版本变更次数以及并发事务与目标事务中作用于同一变量的读写操作，确定数据异常类型。
其中，由上述步骤603可知，版本变更次数用于表示该目标事务与该并发事务所作用的相同变量的数据状态；另外，又由上述表2可知，不同的数据异常对应的版本变更次数以及两个事务作用于同一变量的读写操作不同；因此，在本步骤6043中，节点设备基于版本变更次数以及该并发事务与该目标事务中作用于同一变量的读写操作，来确定该数据异常类型。
示意性地，下面以八种场景为例，对本步骤6043的实施过程分别进行说明。
场景一、若所属类别为写异常类别，该子类别为单元数据异常，则本步骤6043包括下述三种情况，下面对该三种情况分别进行说明。
1)若该版本变更次数为一，则节点设备确定该数据异常类型为丢失自更新异常。
2)若该版本变更次数为二，该目标事务与该并发事务中存在作用于同一变量的第五指定数量(比如三个)的写操作，则节点设备确定该数据异常类型为全写入异常。
3)若该版本变更次数为二，该目标事务与该并发事务中存在作用于同一变量的两个写操作和第六指定数量(比如一个)的读操作，则节点设备确定该数据异常类型为丢失更新异常。
场景二、若该数据异常类型的所属类别为写异常类别，该子类别为双元数据异常，则本步骤6043包括下述三种情况，下面对该三种情况分别进行说明。
1)若该版本变更次数为一，该目标事务与该并发事务中存在作用于不同版本的第一变量的写操作和读操作(称为满足第一条件)、以及存在作用于不同版本的第二变量的两个写操作(称为满足第二条件)，则节点设备确定该数据异常类型为读写偏序异常；其中，满足第一条件是指目标读写操作包括作用于不同版本的第一变量的写操作和读操作，满足第二条件是指目标读写操作包括作用于不同版本的第二变量的第一指定数量的写操作。
2)若该版本变更次数为一，该目标事务与该并发事务中存在作用于相同版本的第一变量的写操作和读操作(称为满足第三条件)、以及存在作用于不同版本的第二变量的两个写操作(称为满足第二条件)，则节点设备确定该数据异常类型为重复写偏序异常；其中，满足第三条件是指目标读写操作包括作用于同一版本的第一变量的写操作和读操作。
3)若该版本变更次数为一，该目标事务与该并发事务中存在作用于不同版本的第一变量的两个写操作(称为满足第四条件)、以及存在作用于不同版本的第二变量的两个写操作(称为满足第二条件)，则节点设备确定该数据异常类型为全写入偏序异常；其中，满足第四条件是指目标读写操作包括作用于不同版本的第一变量的第一指定数量的写操作。
场景三、若该数据异常类型的所属类别为读异常类别，该子类别为单元数据异常，则本步骤6043包括下述两种情况，下面对该两种情况分别进行说明。
1)若该版本变更次数为一，该目标事务与该并发事务中存在作用于同一变量的两个读操作和一个写操作，则节点设备确定该数据异常类型为不可重复读异常。
2)若该版本变更次数为一，该目标事务与该并发事务中存在作用于同一变量的两个写操作和一个读操作，则节点设备确定该数据异常类型为中间读异常。
场景四、若该数据异常类型的所属类别为读异常类别，该子类别为双元数据异常，则本步骤6043包括下述两种情况，下面对该两种情况分别进行说明。
1)若该版本变更次数为第七指定数量(比如为零)，则节点设备确定该数据异常类型为写读偏序异常。
2)若该版本变更次数为一，则节点设备确定该数据异常类型为读偏序异常。
场景五、若该数据异常类型的所属类别为交叉异常类别，该子类别为双元数据异常，则本步骤6043包括：若该版本变更次数为一，则节点设备确定该数据异常类型为写偏序异常。
场景六、若该数据异常类型的所属类别为写异常类别，该子类别为多元数据异常，则本步骤6043包括：节点设备确定该数据异常类型为台阶式写异常。
场景七、若该数据异常类型的所属类别为读异常类别，该子类别为多元数据异常，则本步骤6043包括：节点设备确定该数据异常类型为台阶式读异常。
场景八、若该数据异常类型的所属类别为交叉异常类别，该子类别为多元数据异常，则本步骤6043包括：节点设备确定该数据异常类型为台阶式交叉异常。
需要说明的是，节点设备是按照步骤6041至步骤6043的顺序执行的，也即是，节点设备先确定数据异常类型的所属类别，再确定子类别，最后确定细分类的数据异常类型。在一些实施例中，上述步骤6041至步骤6043替换为下述步骤一至步骤三。
步骤一、节点设备基于该目标变量列表，确定子类别。
步骤二、节点设备基于该目标事务与该并发事务中作用于同一变量的读写操作，确定所属类别；
步骤三、节点设备基于在所属类别中的子类别、该版本变更次数以及该并发事务与该目标事务中作用于同一变量的读写操作，确定该数据异常类型。
也即是，节点设备先确定数据异常类型的子类别，再确定所属类别，最终确定细分类的数据异常类型。
在一些实施例中，节点设备还可以同步确定数据异常类型的所属类别和子类别，本申请实施例对此不作限定。
经过上述步骤604，节点设备确定数据异常类型后，执行下述步骤605至步骤607。需要说明的是，若该第一交集和该第二交集中，存在至少一项不为空集，且该目标事务与该并发事务不冲突，则节点设备执行下述步骤608。
步骤605、节点设备从目标事务和并发事务中，确定待回滚的事务。
在本申请实施例中，经过上述步骤604，节点设备确定出现数据异常，需要对该目标事务或该并发事务进行回滚，从这两个事务中确定出待回滚的事务。
下面对本步骤605所涉及的两种可选实施方式进行说明。
方式一、节点设备按照事务优先级，将该目标事务和该并发事务中事务优先级最低的事务确定为该待回滚的事务。
在本申请实施例中，事务优先级为预先设置的优先级，数据库系统预先为每类事务分配事务优先级，例如，按照事务的处理时长、事务的操作类型和所作用的变量数量等中的至少一种，确定每个事务的事务优先级，本申请实施例对于事务优先级的设置方式不作限定。
示意性地，下面以四种事务优先级的设置方式为例，对本步骤605的实施方式进行说明。
第一种、若该目标事务和该并发事务中的当前事务的处理时长小于其他事务的处理时长，则节点设备将该当前事务确定为事务优先级最低的事务；从而，该待回滚的事务即为该当前事务。
其中，事务优先级是按照事务的处理时长来确定的。处理时长大于参考时长的事务为长事务，处理时长小于或等于参考时长的事务确定为短事务，长事务的事务优先级高于短事务的事务优先级。这里，当前事务为目标事务和并发事务中的任一事务，其他事务为目标事务和并发事务中除当前事务之外的事务。
示意性地，对于目标事务来说，以并发事务的处理时长为参考时长，若目标事务的处理时长小于该并发事务，则节点设备将该目标事务确定为待回滚的事务；否则，将并发事务确定为待回滚的事务。
第二种、若该目标事务和该并发事务中任一事务为读事务，则节点设备将该读事务确定为事务优先级最低的事务；从而，待回滚的事务即为该读事务。
其中，事务优先级是按照事务的操作类型来确定的，写事务的事务优先级高于读事务的事务优先级；这里，事务的操作类型包括写事务类型和读事务类型，写事务类型的事务为写事务，读类型的事务为读事务。
示意性地，若目标事务为写事务，并发事务为读事务，则节点设备将该目标事务确定为待回滚的事务。
第三种、若该目标事务和该并发事务中的当前事务为写事务，且该写事务的处理时长小于参考时长，则节点设备将该写事务确定为事务优先级最低的事务；从而，待回滚的事务即为该当前事务。
其中，事务优先级是结合事务的处理时长以及操作类型来确定的，也即是，当写事务为短事务时，其事务优先级低于长的读事务。示意性地，若该目标事务为写事务，且该目标事务的处理时长小于参考时长，则节点设备将该目标事务确定为待回滚的事务。
需要说明的是，在一些实施例中，事务优先级的设置方式还可以有其他形式，例如，短事务的事务优先级高于长事务的事务优先级，又例如，读事务的事务优先级高于写事务的事务优先级，等等，本申请实施例对此不作限定。
可以理解的是，通过这种基于事务优先级来确定待回滚的事务的方式，能够有针对性地回滚事务，保证重要的事务优先处理，从而提高了计算资源的利用率，提高了事务处理的效率。
第四种、若该目标事务与该并发事务中的当前事务所作用的变量数量大于其他事务所作用的变量数量，则节点设备将该当前事务确定为事务优先级最低的事务；从而，待回滚的事务即为该当前事务。
在本申请实施例中，节点设备遍历目标事务与并发事务的目标冲突环图(有关目标冲突环图的介绍会在后文步骤607中介绍，在此不再重复描述)，在当前事务所作用的变量数量最多时，将该当前事务确定为待回滚的事务。
通过这种可选地实施方式，将涉及变量数量较多的事务进行回滚，能够减少后续事务处理过程中与其他事务冲突的可能性，从而减少了事务处理的冲突率，提高了事务处理的效率。
方式二，节点设备将从目标事务与并发事务中随机选择的事务，确定为待回滚的事务。
步骤606、节点设备对该待回滚的事务进行回滚。
需要说明的是，通过上述步骤601至步骤606，节点设备确定了目标事务与并发事务是否构成冲突，只有在存在数据异常的情况下，才确定待回滚的事务。
可以理解的是，节点设备在确定待回滚的事务时是按照一定的策略来确定的，而不是直接将目标事务进行回滚，这样能够有效降低假回滚率，从而提高计算资源的利用率，提高事务处理的效率。
步骤607、节点设备删除目标冲突环图中待回滚的事务所作用的变量以及对应的读 写操作，其中，目标冲突环图中的顶点用于表示事务对应的事务标识以及事务对应的读写操作所作用的变量，目标冲突环图中的边用于表示事务之间的关联关系以及变量之间的版本变化。
在本申请实施例中，目标冲突环图是一种细节冲突环图(Detail Conflict Cycle Graph，DCCG)，是等价于CCG图和CCSG图的一种冲突环图，也是本申请实施例中数据状态一致性模型的实现基础。在经过上述步骤606，将待回滚的事务进行回滚后，节点设备删除目标冲突环图中待回滚的事务所作用的变量以及对应的读写操作，来维护目标冲突环图的结构。
下面将对目标冲突环图的获取方式进行详细阐述，包括如下步骤一至步骤三，下面对各步骤分别进行说明。
步骤一、获取该目标事务与该并发事务之间的第一冲突环图，该第一冲突环图中的顶点用于表示事务对应的事务标识，该第一冲突环图中的边用于表示事务之间的关联关系以及事务对应的读写操作所作用的变量。
其中，第一冲突环图为该目标事务与该并发事务之间的CCG图。关于第一冲突环图中的顶点以及边的含义请参考前述对CCG图的顶点和边的介绍，此处不再重复描述。
步骤二、对该第一冲突环图进行转换，得到第二冲突环图，该第二冲突环图中的顶点用于表示多个不同版本的变量，该第二冲突环图中的边用于表示变量之间的版本变化以及同一事务所作用的变量。
其中，第二冲突环图为该目标事务与该并发事务之间的CCSG图。关于第二冲突环图中的顶点以及边的含义请参考前述对CCSG图的顶点和边的介绍，此处不再重复描述。基于前述对CCG图和CCSG图的介绍可知，CCG图和CCSG图等价，下面以CCG图向CCSG图的等价转换规则为基础，对本步骤二的实施方式进行简要说明，包括下述步骤A和步骤B，下面对各步骤分别进行说明。
步骤A、对该第一冲突环图的边进行拆分，得到该多个不同版本的变量。
步骤B、将该多个不同版本的变量作为顶点，并在相邻版本的同一变量对应的顶点之间添加边，以及在同一事务所作用的变量对应的顶点之间添加边，得到该第二冲突环图。
步骤三、对该第二冲突环图进行转换，得到该目标冲突环图。
其中，基于前述对CCG图和CCSG图的介绍可知，CCG图和CCSG图等价，CCSG图能够等价转换为CCG图，该目标冲突环图是通过对CCSG图进行转换得到的新的CCG图。在上述第一冲突环图中，该第一冲突环图中的顶点用于表示事务对应的事务标识，而在目标冲突环图(也即是新的CCG图)中，该目标冲突环图的顶点信息相比于第一冲突环图中的顶点信息更为细化，既包括了事务对应的事务标识，也包括了事务对应的读写操作所作用的变量；另外，该目标冲突环图的顶点对应的变量保留了构成冲突环的必要变量，因为一个事务所操作过的变量可能很多，但不是所有的变量及其版本都是构成冲突环图的充分条件。
下面以前述CCSG图向CCG图的等价转换规则为基础，对本步骤三的具体实施方式进行说明，包括下述步骤C至步骤E，下面对各步骤分别进行说明。
步骤C、将该第二冲突环图中同一事务所作用的变量对应的顶点进行合并，并将同一事务对应的事务标识确定为合并后的顶点。即节点设备将合并后的顶点命名为同一事务对应的事务标识。
步骤D、在合并后的第二冲突环图的相邻顶点之间添加边，得到第三冲突环图。
步骤E、若该第三冲突环图的任意两个相邻顶点中存在相同版本的变量，将该任意两个相邻顶点合并，并删去合并后的顶点所对应的该相同版本的变量，得到该目标冲突 环图；若该第三冲突环图的任意两个相邻顶点中存在不同版本的同一变量，将该任意两个相邻顶点合并，得到该目标冲突环图。
其中，该第三冲突环图即为对CCSG图按照等价转换规则进行转换得到的CCG图，在该第三冲突环图中，若任意两个相邻顶点中存在相同版本的变量，则该第三冲突环图适用于约简规则，从而节点设备对这两个顶点进行合并，且删去相同版本的变量；若任意两个相邻顶点中存在不同版本的同一变量，则该第三冲突环图适用于合并规则但不适用于约简规则，从而节点设备对这两个顶点进行合并；若任意两个相邻顶点中不存在相同的变量，则节点设备直接将该第三冲突环图作为目标冲突环图。
下面对上述约简规则以及合并规则进行介绍。
第一、约简规则。
对于一个冲突环图中任意两个相邻顶点V i和V i+1，若
Figure PCTCN2022087848-appb-000025
即存在至少一个相同版本的变量，则V i和V i+1可以合并为一个顶点；该合并出的新顶点中，x m和y n等可以被去除，保留两个顶点中不相交的部分，也即是V i∪V i+1-V i∩V i+1。即约简后的新顶点保留V i和V i+1这两个集合的差集。
基于上述对目标冲突环图的介绍以及该约简规则，能够得到以下三条推论，下面对各推论分别进行说明。
推论1、若一个调度s，
Figure PCTCN2022087848-appb-000026
该dccg图的任意两个相邻顶点的交集为空集，则该dccg称为最小DCCG图，也即是该dccg图中满足约简规则的顶点完成约简后，得到的DCCG图最精简。
推论2、一个最小DCCG图等价于上述表2中的某一种数据异常。
推论3、若一个调度s中，任意两个并发事务之间存在WR关系，则这两个并发事务可适用约简规则。
第二、合并规则。
对于一个冲突环图中任意两个相邻顶点V i和V i+1，若
Figure PCTCN2022087848-appb-000027
则这两个顶点不可约简；若
Figure PCTCN2022087848-appb-000028
即存在至少一个相同的变量，且不适用于约简规则，则这两个相邻顶点适用于合并规则；也就是说，将这两个相邻顶点对应的事务称为可合并事务，将V i和V i+1合并为一个顶点，该合并出的新顶点对应的事务的读集为V i和V i+1对应的读集的合集，该合并出的新顶点对应的事务的写集为V i和V i+1对应的写集的合集。
另外，基于上述对目标冲突环图的介绍以及该合并规则，能够得到以下推论：一个调度s的dccg图所表示的数据异常，在通过对可合并事务进行合并后，不影响原dccg图等价的数据异常。
以上对目标冲突环图的获取方式以及相关规则进行了介绍，下面参考表4和图10，结合示例，对目标冲突环图的获取方式进行举例说明；其中，图10是本申请实施例提供的一种获取目标冲突环图的示意图；一个调度s包括三个事务T1、T2以及T3，其执行序列如表4所示。
表4
时刻 T 1 T 2 T 3
t 0 R 1[x 0]     
t 1   W 2[x 1]  
t 2   W 2[y 1]  
t 3     R 3[y 1]
t4     W 3[z 1]
t5 W 1[z 2]    
如图10中(a)所示，该调度s的CCG图(也即是第一冲突环图)中的边用于表示事务之间的关联关系以及事务对应的读写操作所作用的变量，包括以下三条边：E 1＝(T 1→T 2，R 1[x 0]W 2[x 1])，E 2＝(T 2→T 3，W 2[y 1]R 3[y 1])，E 3＝(T 3→T 1，W 3[z 1]W 1[z 2])；对应三个变量x，y和。
如图10中(b)和(c)所示，该CCG图中包括三个变量x，y和z，分别处于边E 1，E 2以及E 3，以变量为顶点，对三条边进行拆分。例如，E 1表示为R 1[x 0]W 2[x 1]，对该边进行拆分，得到E 11＝R 1[x 0]和E 12＝W 2[x 1]；E 2表示为W 2[y 1]R 3[y 1]，对该边进行拆分，得到E 21＝W 2[y 1]和E 22＝R 3[y 1]；E 3表示为W 3[z 1]W 1[z 2]，对该边进行拆分，得到E 31＝W 3[z 1]和E 32＝W 1[z 2]。由此，删除CCG图中的顶点。
如图10中(d)所示，在经过上述边拆分的过程后，得到变量x的两个版本x 0和x 1，变量y的一个版本y 1以及变量z的两个版本z 1和z 2。将这些变量的版本作为CCSG图的顶点，同一个变量的多个版本纵向排列，被同一个事务作用过的不同变量的版本之间横向排列(应理解，图10中(d)中还包括变量z的初始版本z 0，这样才能与边E 31对应)。这里，在相邻版本的同一变量对应的顶点之间添加边；在同一事务所作用的变量对应的顶点之间添加边。另外，基于前述对CCSG图的描述可知，CCSG图为一个有向环构成的图，则边W 3[z 1]和W 2[y 1]以及变量版本z 0和y 0对构成有向环没有作用，因此删去这两条边和这两个变量版本，得到如图10中(e)所示的CCSG图。
如图10中(e)所示，该CCSG图(也即是第二冲突环图)中的顶点用于表示多个不同版本的变量，该第二冲突环图中的边用于表示变量之间的版本变化以及同一事务所作用的变量。示意性地，顶点V＝{x 0、x 1、y 1、z 1，z 2}；E＝{W 2[x 1]，R 2[x 1]R 2[y 1]，R 3[y 1]R 3[z 1]，W 1[z 2]，R 1[x 2]R 1[x 0]}；其中，E T＝{R 2[x 1]R 2[y 1]，R 3[y 1]R 3[z 1]，R 1[x 2]R 1[x 0]}；E s＝{W 2[x 1]，W 1[z 2]}。
如图10中(f)所示，该图10中(f)是通过对图10中(e)所示的CCSG图进行转换得到的新的CCG图(也即是第三冲突环图)。转换的过程包括：节点设备将CCSG图中同一个事务涉及的变量版本合并到同一个顶点里面，得到该图10中(f)。如图10中(f)所示，每个顶点重新变为以事务为顶点，示出了事务之间的关联关系。需要说明的是，在一些实施例中，该图也可以为一个无向的环图。
如图10中(g)所示，顶点V 2和V 3满足上述约简规则，也即是在这两个顶点中，均包括相同版本的变量y 1，因此，对顶点V 2和V 3进行合并，删去合并后的顶点中的变量y 1，得到图10中(h)所示的DCCG图(也即是目标冲突环图)。
以上通过举例的方式对目标冲突环图的获取方式进行了介绍，也可以理解为确定并发事务之间的有向环图的过程。在本步骤607中，节点设备在确定了待回滚的事务后，对该目标冲突环图的结构进行维护，便于后续执行下一次循环，也即是对至少一个候选并发事务中的其他候选并发事务进行一致性检验。
下面将通过步骤608，对目标事务和并发事务不冲突的情况进行说明。
步骤608、节点设备对目标事务和并发事务进行合并，得到合并后的目标事务，再次执行上述步骤603，直至链表TS为空。
在本申请实施例中，经过上述步骤604，第一交集和第二交集中，存在至少一项不 为空集，且该目标事务与该并发事务不冲突，也可以理解为该目标事务与该并发事务之间不构成目标冲突环图，则目标事务与并发事务不存在数据异常，节点设备对这两个事务进行合并，得到合并后的目标事务，继续从链表TS中选取候选并发事务，直至链表TS为空。
下面以目标事务为T，并发事务为TL为例，对本步骤608的实施方式进行说明。
节点设备将该并发事务TL的读集并入目标事务T的读集中，将该并发事务TL的写集并入目标事务T的写集中，以实现事务合并，得到合并后的新事务T-new；此外，如果并发事务TL没有提交，则对T-new的目标参数(no_committed)进行增量处理，也即令T-new.no_committed++(自增1)，表示合并得到的新事务中拥有某个已经提交的事务的读写集合的成分。基于此，节点设备将T-new确定为新的目标事务T’(即为T’＝T-new)，从链表TS中取出第二个候选并发事务定为TL’，执行步骤603(判断新的T-new与TL’之间是否冲突)。
步骤609、若链表TS中最后一个候选并发事务与该目标事务之间不存在数据异常，则节点设备提交该目标事务。
在本申请实施例中，若链表TS中最后一个候选并发事务与该目标事务之间不存在数据异常，则表明目标事务可提交。这里，如果隔离级别参数＝S，也即隔离级别是可串行化级别，此时即可满足可串行化级别，否则，满足前述表3所设定的隔离级别。
上述所有可选技术方案，可以采用任意结合形成本申请实施例，在此不再一一描述。
图11是根据本申请实施例提供的一种事务处理装置的结构示意图。该事务处理装置用于执行上述事务处理方法执行时的步骤，参见图11，该事务处理装置1100包括：第一确定模块1101和第二确定模块1102。
第一确定模块1101，配置为确定目标事务的并发事务，所述并发事务与所述目标事务之间包括作用于同一变量的读写操作，所述目标事务为待提交事务；
第二确定模块1102，配置为获取所述目标事务的读集和所述并发事务的写集之间的第一交集，并获取所述目标事务的写集和所述并发事务的读集之间的第二交集；当所述第一交集和所述第二交集中的至少一项为非空数据集，且所述目标事务与所述并发事务冲突时，基于所述目标事务和所述并发事务所作用的同一变量的版本变更次数和目标变量列表，确定数据异常类型，所述目标变量列表包括所述目标事务和所述并发事务所作用的同一变量。
在本申请实施例中，该事务处理装置1100还包括第三确定模块和回滚模块；第三确定模块，配置为从该目标事务和该并发事务中，确定待回滚的事务；回滚模块，配置为对该待回滚的事务进行回滚。
在本申请实施例中，第三确定模块，配置为基于事务优先级，将所述目标事务和所述并发事务中事务优先级最低的事务确定为所述待回滚的事务。
在本申请实施例中，该第三确定模块，配置为在所述目标事务和所述并发事务中，在当前事务的处理时长小于其他事务的处理时长时，将所述当前事务确定为所述事务优先级最低的事务，所述当前事务为所述目标事务和所述并发事务中的任一事务，所述其他事务为所述目标事务和所述并发事务中除所述当前事务之外的事务；在所述目标事务和所述并发事务中，当所述当前事务为读事务时，将所述当前事务确定为所述事务优先级最低的事务；在所述目标事务和所述并发事务中，当所述当前事务为写事务、且所述当前事务的处理时长小于参考时长时，将所述当前事务确定为所述事务优先级最低的事务；在所述目标事务与所述并发事务中，当所述当前事务所作用的变量数量大于所述其他事务所作用的变量数量时，将所述当前事务确定为所述事务优先级最低的事务。
在本申请实施例中，该事务处理装置1100还包括删除模块，配置为删除目标冲突 环图中该待回滚的事务所作用的变量以及对应的读写操作，其中，该目标冲突环图中的顶点用于表示事务对应的事务标识以及事务对应的读写操作所作用的变量，该目标冲突环图中的边用于表示事务之间的关联关系以及变量之间的版本变化。
在本申请实施例中，该事务处理装置1100还包括获取模块，配置为获取该目标事务与该并发事务之间的该目标冲突环图。
在本申请实施例中，该获取模块包括子获取模块、第一转换模块和第二转换模块；获取模块，配置为获取该目标事务与该并发事务之间的第一冲突环图，该第一冲突环图中的顶点用于表示事务对应的事务标识，该第一冲突环图中的边用于表示事务之间的关联关系以及事务对应的读写操作所作用的变量；第一转换模块，配置为对该第一冲突环图进行转换，得到第二冲突环图，该第二冲突环图中的顶点用于表示多个不同版本的变量，该第二冲突环图中的边用于表示变量之间的版本变化以及同一事务所作用的变量；第二转换模块，配置为于对该第二冲突环图进行转换，得到该目标冲突环图。
在本申请实施例中，该第一转换模块，配置为对该第一冲突环图的边进行拆分，得到该多个不同版本的变量；将该多个不同版本的变量作为顶点，并在相邻版本的同一变量对应的顶点之间添加边，以及在同一事务所作用的变量对应的顶点之间添加边，得到该第二冲突环图。
在本申请实施例中，该第二转换模块，配置为将所述第二冲突环图中同一事务所作用的变量对应的顶点进行合并，并将同一事务对应的事务标识确定为合并后的顶点；在合并后的所述第二冲突环图的相邻顶点之间添加边，得到第三冲突环图；当所述第三冲突环图的两个相邻顶点中包括同一版本的变量时，将所述两个相邻顶点合并，并删去合并后的顶点中的同一版本的变量，得到所述目标冲突环图；当所述第三冲突环图的两个相邻顶点中包括不同版本的同一变量时，将所述两个相邻顶点合并，得到所述目标冲突环图。
在本申请实施例中，该事务处理装置1100还包括第一处理模块、第二处理模块和第三处理模块；第一处理模块，配置为当所述第一交集为所述非空数据集时，对所述目标事务和所述并发事务之间的有向边的数量进行增量处理，并将所述第一交集中的变量添加到所述目标变量列表中，以及当所述第一交集中包括版本不同的变量时，对所述版本变更次数进行增量处理，所述有向边的数量用于指示所述目标事务与所述并发事务之间是否冲突；第二处理模块，配置为当所述第二交集为所述非空数据集时，对所述有向边的数量进行增量处理，并将所述第二交集中的变量添加到所述目标变量列表中，以及当所述第二交集中包括版本不同的变量，对所述版本变更次数进行增量处理；第三处理模块，配置为当第三交集为所述非空数据集时，基于所述并发事务的提交状态，确定所述数据异常类型，所述第三交集为所述目标事务的写集和所述并发事务的写集之间的交集。
在本申请实施例中，该第二确定模块1102包括第一子确定模块、第二子确定模块和第三子确定模块；第一子确定模块，配置为基于所述目标事务与所述并发事务中作用于同一变量的目标读写操作，确定所属类别；第二子确定模块，配置为基于所述目标事务与所述并发事务中作用于同一变量的目标读写操作，确定所属类别中的子类别；第三子确定模块，配置为基于在所述所属类别中的所述子类别、所述版本变更次数以及所述目标读写操作中的至少一种，确定所述数据异常类型。
在本申请实施例中，该第一子确定模块，还配置为当所述目标事务与所述并发事务中的所述目标读写操作满足写异常条件时，确定所述所属类别为写异常类别，满足所述写异常条件是指所述目标读写操作包括作用于不同版本的同一变量的第一指定数量的写操作；当所述目标读写操作不满足所述写异常条件，且满足读异常条件时，确定所述 所属类别为读异常类别，满足所述读异常条件是指所述目标读写操作包括作用于同一版本的同一变量的读操作和写操作；当所述目标读写操作不满足所述写异常条件和所述读异常条件，且满足交叉异常条件时，确定所述所属类别为交叉异常类别，满足所述交叉异常条件是指所述目标读写操作包括作用于不同版本的同一变量的读操作和写操作。
在本申请实施例中，该第二子确定模块，还配置为当所述目标变量列表中的变量数量为第二指定数量时，确定在所述所属类别中的所述子类别为单元数据异常；当所述目标变量列表中的变量数量为第三指定数量时，确定在所述所属类别中的所述子类别为双元数据异常；当所述目标变量列表中的变量数量为第四指定数量时，确定在所述所属类别中的所述子类别为多元数据异常，其中，所述第四指定数量与所述第二指定数量和所述第三指定数量均不同。
在本申请实施例中，当所述所属类别为写异常类别，且所述子类别为单元数据异常时，则该第三子确定模块，还配置为当所述版本变更次数为第二指定数量时，基于所述写异常类别和所述单元数据异常，确定所述数据异常类型为丢失自更新异常；当所述版本变更次数为第三指定数量，且所述目标读写操作为第五指定数量的写操作时，基于所述写异常类别和所述单元数据异常，确定所述数据异常类型为全写入异常；当所述版本变更次数为所述第三指定数量，且所述目标读写操作为第一指定数量的写操作和第六指定数量的读操作时，基于所述写异常类别和所述单元数据异常，确定所述数据异常类型为丢失更新异常。
在本申请实施例中，当所述所属类别为写异常类别，且所述子类别为双元数据异常，以及所述版本变更次数为第二指定数量时，第三子确定模块，还配置为当所述目标读写操作满足第一条件和第二条件时，基于所述写异常类别、所述双元数据异常和所述第二指定数量，确定所述数据异常类型为读写偏序异常，满足所述第一条件是指所述目标读写操作包括作用于不同版本的第一变量的写操作和读操作，满足所述第二条件是指所述目标读写操作包括作用于不同版本的第二变量的第一指定数量的写操作；当所述目标读写操作满足第三条件和所述第二条件时，基于所述写异常类别、所述双元数据异常和所述第二指定数量，确定所述数据异常类型为重复写偏序异常，满足所述第三条件是指所述目标读写操作包括作用于同一版本的所述第一变量的写操作和读操作；当所述目标读写操作满足第四条件和所述第二条件时，基于所述写异常类别、所述双元数据异常和所述第二指定数量，确定所述数据异常类型为全写入偏序异常，满足所述第四条件是指所述目标读写操作包括作用于不同版本的所述第一变量的所述第一指定数量的写操作。
在本申请实施例中，当所述所属类别为读异常类别，且所述子类别为单元数据异常，以及所述版本变更次数为第二指定数量时，第三子确定模块，还配置为当所述目标读写操作包括作用于同一变量的第一指定数量的读操作和第六指定数量的写操作，基于所述读异常类别、所述单元数据异常和所述第二指定数量，确定所述数据异常类型为不可重复读异常；当所述目标读写操作包括作用于同一变量的所述第一指定数量的写操作和所述第六指定数量的读操作，基于所述读异常类别、所述单元数据异常和所述第二指定数量，确定所述数据异常类型为中间读异常。
在本申请实施例中，当所述所属类别为读异常类别，且所述子类别为双元数据异常时，第三子确定模块，还配置为当所述版本变更次数为第七指定数量时，基于所述读异常类别和所述双元数据异常，确定所述数据异常类型为写读偏序异常；当所述版本变更次数为第二指定数量时，基于所述读异常类别和所述双元数据异常，确定所述数据异常类型为读偏序异常。
在本申请实施例中，第三子确定模块，还配置为当所述所属类别为交叉异常类别，且所述子类别为双元数据异常，以及所述版本变更次数为第二指定数量时，确定所述数 据异常类型为写偏序异常。
在本申请实施例中，该第三子确定模块，还配置为当所述所属类别为写异常类别，且所述子类别为多元数据异常时，确定所述数据异常类型为台阶式写异常；当所述所属类别为读异常类别，且所述子类别为所述多元数据异常时，则确定所述数据异常类型为台阶式读异常；当所述所属类别为交叉异常类别，且所述子类别为所述多元数据异常时，确定所述数据异常类型为台阶式交叉异常。
需要说明的是，上述实施例提供的事务处理装置在处理事务时，是以上述各功能模块的划分进行举例说明，实际应用中，可以根据需要而将上述功能分配由不同的功能模块完成，即将装置的内部结构划分成不同的功能模块，以完成以上描述的全部或者部分功能。另外，本申请实施例提供的事务处理装置与事务处理方法属于同一构思，实现过程详见方法实施例，这里不再重复描述。
本申请实施例还提供了一种电子设备(比如计算机设备)，该电子设备包括处理器和存储器，该存储器用于存储至少一条计算机程序，该至少一段计算机程序由该处理器加载并执行以实现本申请实施例中的事务处理方法。
在一些实施例中，本申请实施例所涉及的计算机程序可被部署在一个计算机设备上执行，或者在位于一个地点的多个计算机设备上执行，又或者，在分布在多个地点且通过有线网络或无线网络互连的多个计算机设备上执行，分布在多个地点且通过有线网络或无线网络互连的多个计算机设备可以组成区块链系统。
以计算机设备为服务器为例，图12是根据本申请实施例提供的一种服务器的结构示意图，该服务器1200可因配置或性能不同而产生比较大的差异，能够包括一个或一个以上处理器(Central Processing Units，CPU)1201和一个或一个以上的存储器1202，其中，该存储器1202中存储有至少一条计算机程序，该至少一条计算机程序由处理器1201加载并执行以实现上述各个方法实施例提供的事务处理方法。当然，该服务器还能够包括有线或无线网络接口、键盘以及输入输出接口等部件，以便进行输入输出，该服务器还能够包括其他用于实现设备功能的部件，在此不再重复描述。
本申请实施例还提供了一种计算机可读存储介质，该计算机可读存储介质应用于计算机设备，该计算机可读存储介质中存储有至少一条计算机程序，该至少一条计算机程序由处理器加载并执行以实现本申请实施例的事务处理方法。
本申请实施例还提供了一种计算机程序产品，包括计算机程序或指令，该计算机程序或指令存储在计算机可读存储介质中。计算机设备的处理器从计算机可读存储介质读取该计算机程序或指令，处理器执行该计算机程序或指令，使得该计算机设备执行本申请实施例提供的事务处理方法。
本领域普通技术人员可以理解实现上述实施例的全部或部分步骤可以通过硬件来完成，也可以通过程序来指令相关的硬件完成，所述的程序可以存储于一种计算机可读存储介质中，上述提到的存储介质可以是只读存储器，磁盘或光盘等。
可以理解的是，在本申请实施例中，涉及到用户信息等相关的数据，当本申请实施例运用到具体产品或技术中时，需要获得用户许可或者同意，且相关数据的收集、使用和处理需要遵守相关国家和地区的相关法律法规和标准。
以上所述仅为本申请的可选实施例，并不用以限制本申请，凡在本申请的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本申请的保护范围之内。

Claims (22)

  1. 一种数据库系统的事务处理方法，所述方法由电子设备执行，所述方法包括：
    确定目标事务的并发事务，所述并发事务与所述目标事务之间包括作用于同一变量的读写操作，所述目标事务为待提交事务；
    获取所述目标事务的读集和所述并发事务的写集之间的第一交集，并获取所述目标事务的写集和所述并发事务的读集之间的第二交集；
    当所述第一交集和所述第二交集中的至少一项为非空数据集，且所述目标事务与所述并发事务冲突时，基于所述目标事务和所述并发事务所作用的同一变量的版本变更次数和目标变量列表，确定数据异常类型，所述目标变量列表包括所述目标事务和所述并发事务所作用的同一变量。
  2. 根据权利要求1所述的方法，其中，所述方法还包括：
    从所述目标事务和所述并发事务中，确定待回滚的事务；
    对所述待回滚的事务进行回滚。
  3. 根据权利要求2所述的方法，其中，所述从所述目标事务和所述并发事务中，确定待回滚的事务，包括：
    基于事务优先级，将所述目标事务和所述并发事务中事务优先级最低的事务确定为所述待回滚的事务。
  4. 根据权利要求3所述的方法，其中，所述基于事务优先级，将所述目标事务和所述并发事务中事务优先级最低的事务确定为所述待回滚的事务之前，所述方法还包括下述任一项：
    在所述目标事务和所述并发事务中，在当前事务的处理时长小于其他事务的处理时长时，将所述当前事务确定为所述事务优先级最低的事务，所述当前事务为所述目标事务和所述并发事务中的任一事务，所述其他事务为所述目标事务和所述并发事务中除所述当前事务之外的事务；
    在所述目标事务和所述并发事务中，在所述当前事务为读事务时，将所述当前事务确定为所述事务优先级最低的事务；
    在所述目标事务和所述并发事务中，在所述当前事务为写事务、且所述当前事务的处理时长小于参考时长时，将所述当前事务确定为所述事务优先级最低的事务；
    在所述目标事务与所述并发事务中，在所述当前事务所作用的变量数量大于所述其他事务所作用的变量数量时，将所述当前事务确定为所述事务优先级最低的事务。
  5. 根据权利要求2至4任一项所述的方法，其中，所述对所述待回滚的事务进行回滚之后，所述方法还包括：
    删除目标冲突环图中所述待回滚的事务所作用的变量以及对应的读写操作，其中，所述目标冲突环图中的顶点用于表示事务对应的事务标识以及事务对应的读写操作所作用的变量，所述目标冲突环图中的边用于表示事务之间的关联关系以及变量之间的版本变化。
  6. 根据权利要求5所述的方法，其中，所述方法还包括：
    获取所述目标事务与所述并发事务之间的第一冲突环图，所述第一冲突环图中的顶点用于表示事务对应的事务标识，所述第一冲突环图中的边用于表示事务之间的关联关系以及事务对应的读写操作所作用的变量；
    对所述第一冲突环图进行转换，得到第二冲突环图，所述第二冲突环图中的顶点用于表示多个不同版本的变量，所述第二冲突环图中的边用于表示变量之间的版本变化以及同一事务所作用的变量；
    对所述第二冲突环图进行转换，得到所述目标冲突环图。
  7. 根据权利要求6所述的方法，其中，所述对所述第一冲突环图进行转换，得到第二冲突环图，包括：
    对所述第一冲突环图的边进行拆分，得到所述多个不同版本的变量；
    将所述多个不同版本的变量作为顶点，并在相邻版本的同一变量对应的顶点之间添加边，以及在同一事务所作用的变量对应的顶点之间添加边，得到所述第二冲突环图。
  8. 根据权利要求6所述的方法，其中，所述对所述第二冲突环图进行转换，得到所述目标冲突环图，包括：
    将所述第二冲突环图中同一事务所作用的变量对应的顶点进行合并，并将同一事务对应的事务标识确定为合并后的顶点；
    在合并后的所述第二冲突环图的相邻顶点之间添加边，得到第三冲突环图；
    当所述第三冲突环图的两个相邻顶点中包括同一版本的变量时，将所述两个相邻顶点合并，并删去合并后的顶点中的同一版本的变量，得到所述目标冲突环图；
    当所述第三冲突环图的两个相邻顶点中包括不同版本的同一变量时，将所述两个相邻顶点合并，得到所述目标冲突环图。
  9. 根据权利要求1至4任一项所述的方法，其中，所述方法还包括：
    当所述第一交集为所述非空数据集时，对所述目标事务和所述并发事务之间的有向边的数量进行增量处理，并将所述第一交集中的变量添加到所述目标变量列表中，以及当所述第一交集中包括版本不同的变量时，对所述版本变更次数进行增量处理，所述有向边的数量用于指示所述目标事务与所述并发事务之间是否冲突；
    当所述第二交集为所述非空数据集时，对所述有向边的数量进行增量处理，并将所述第二交集中的变量添加到所述目标变量列表中，以及当所述第二交集中包括版本不同的变量，对所述版本变更次数进行增量处理；
    当第三交集为所述非空数据集时，基于所述并发事务的提交状态，确定所述数据异常类型，所述第三交集为所述目标事务的写集和所述并发事务的写集之间的交集。
  10. 根据权利要求1至4任一项所述的方法，其中，所述基于所述目标事务和所述并发事务所作用的同一变量的版本变更次数和目标变量列表，确定数据异常类型，包括：
    基于所述目标事务与所述并发事务中作用于同一变量的目标读写操作，确定所属类别；
    基于所述所属类别以及所述目标变量列表，确定在所述所属类别中的子类别；
    基于在所述所属类别中的所述子类别、所述版本变更次数以及所述目标读写操作中的至少一种，确定所述数据异常类型。
  11. 根据权利要求10所述的方法，其中，所述基于所述目标事务与所述并发事务中作用于同一变量的目标读写操作，确定所属类别，包括下述任一项：
    当所述目标事务与所述并发事务中的所述目标读写操作满足写异常条件时，确定所述所属类别为写异常类别，满足所述写异常条件是指所述目标读写操作包括作用于不同版本的同一变量的第一指定数量的写操作；
    当所述目标读写操作不满足所述写异常条件，且满足读异常条件时，确定所述所属类别为读异常类别，满足所述读异常条件是指所述目标读写操作包括作用于同一版本的同一变量的读操作和写操作；
    当所述目标读写操作不满足所述写异常条件和所述读异常条件，且满足交叉异常条件时，确定所述所属类别为交叉异常类别，满足所述交叉异常条件是指所述目标读写操作包括作用于不同版本的同一变量的读操作和写操作。
  12. 根据权利要求10所述的方法，其中，所述基于所述所属类别以及所述目标变量列表，确定在所述所属类别中的子类别，包括下述任一项：
    当所述目标变量列表中的变量数量为第二指定数量时，确定在所述所属类别中的所述子类别为单元数据异常；
    当所述目标变量列表中的变量数量为第三指定数量时，确定在所述所属类别中的所述子类别为双元数据异常；
    当所述目标变量列表中的变量数量为第四指定数量时，确定在所述所属类别中的所述子类别为多元数据异常，其中，所述第四指定数量与所述第二指定数量和所述第三指定数量均不同。
  13. 根据权利要求10所述的方法，其中，当所述所属类别为写异常类别，且所述子类别为单元数据异常时，所述基于在所述所属类别中的所述子类别、所述版本变更次数以及所述目标读写操作中的至少一种，确定所述数据异常类型，包括下述任一项：
    当所述版本变更次数为第二指定数量时，基于所述写异常类别和所述单元数据异常，确定所述数据异常类型为丢失自更新异常；
    当所述版本变更次数为第三指定数量，且所述目标读写操作为第五指定数量的写操作时，基于所述写异常类别和所述单元数据异常，确定所述数据异常类型为全写入异常；
    当所述版本变更次数为所述第三指定数量，且所述目标读写操作为第一指定数量的写操作和第六指定数量的读操作时，基于所述写异常类别和所述单元数据异常，确定所述数据异常类型为丢失更新异常。
  14. 根据权利要求10所述的方法，其中，当所述所属类别为写异常类别，且所述子类别为双元数据异常，以及所述版本变更次数为第二指定数量时，所述基于在所述所属类别中的所述子类别、所述版本变更次数以及所述目标读写操作中的至少一种，确定所述数据异常类型，包括下述任一项：
    当所述目标读写操作满足第一条件和第二条件时，基于所述写异常类别、所述双元数据异常和所述第二指定数量，确定所述数据异常类型为读写偏序异常，满足所述第一条件是指所述目标读写操作包括作用于不同版本的第一变量的写操作和读操作，满足所述第二条件是指所述目标读写操作包括作用于不同版本的第二变量的第一指定数量的写操作；
    当所述目标读写操作满足第三条件和所述第二条件时，基于所述写异常类别、所述双元数据异常和所述第二指定数量，确定所述数据异常类型为重复写偏序异常，满足所述第三条件是指所述目标读写操作包括作用于同一版本的所述第一变量的写操作和读操作；
    当所述目标读写操作满足第四条件和所述第二条件时，基于所述写异常类别、所述双元数据异常和所述第二指定数量，确定所述数据异常类型为全写入偏序异常，满足所述第四条件是指所述目标读写操作包括作用于不同版本的所述第一变量的所述第一指定数量的写操作。
  15. 根据权利要求10所述的方法，其中，当所述所属类别为读异常类别，且所述子类别为单元数据异常，以及所述版本变更次数为第二指定数量时，所述基于在所述所属类别中的所述子类别、所述版本变更次数以及所述目标读写操作中的至少一种，确定所述数据异常类型，包括下述任一项：
    当所述目标读写操作包括作用于同一变量的第一指定数量个读操作和第六指定数量的写操作，基于所述读异常类别、所述单元数据异常和所述第二指定数量，确定所述数据异常类型为不可重复读异常；
    当所述目标读写操作包括作用于同一变量的所述第一指定数量的写操作和所述第六指定数量的读操作，基于所述读异常类别、所述单元数据异常和所述第二指定数量，确定所述数据异常类型为中间读异常。
  16. 根据权利要求10所述的方法，其中，当所述所属类别为读异常类别，且所述子类别为双元数据异常时，所述基于在所述所属类别中的所述子类别、所述版本变更次数以及所述目标读写操作中的至少一种，确定所述数据异常类型，包括下述任一项：
    当所述版本变更次数为第七指定数量时，基于所述读异常类别和所述双元数据异常，确定所述数据异常类型为写读偏序异常；
    当所述版本变更次数为第二指定数量时，基于所述读异常类别和所述双元数据异常，确定所述数据异常类型为读偏序异常。
  17. 根据权利要求10所述的方法，其中，所述基于在所述所属类别中的所述子类别、所述版本变更次数以及所述目标读写操作中的至少一种，确定所述数据异常类型，包括：
    当所述所属类别为交叉异常类别，且所述子类别为双元数据异常，以及所述版本变更次数为第二指定数量时，确定所述数据异常类型为写偏序异常。
  18. 根据权利要求10所述的方法，其中，所述基于在所述所属类别中的所述子类别、所述版本变更次数以及所述目标读写操作中的至少一种，确定所述数据异常类型，包括下述任一项：
    当所述所属类别为写异常类别，且所述子类别为多元数据异常时，确定所述数据异常类型为台阶式写异常；
    当所述所属类别为读异常类别，且所述子类别为所述多元数据异常时，则确定所述数据异常类型为台阶式读异常；
    当所述所属类别为交叉异常类别，且所述子类别为所述多元数据异常时，确定所述数据异常类型为台阶式交叉异常。
  19. 一种事务处理装置，所述装置包括：
    第一确定模块，配置为确定目标事务的并发事务，所述并发事务与所述目标事务之间包括作用于同一变量的读写操作，所述目标事务为待提交事务；
    第二确定模块，配置为获取所述目标事务的读集和所述并发事务的写集之间的第一交集，并获取所述目标事务的写集和所述并发事务的读集之间的第二交集；当所述第一交集和所述第二交集中的至少一项为非空数据集，且所述目标事务与所述并发事务冲突时，基于所述目标事务和所述并发事务所作用的同一变量的版本变更次数和目标变量列表，确定数据异常类型，所述目标变量列表包括所述目标事务和所述并发事务所作用的同一变量。
  20. 一种电子设备，所述电子设备包括处理器和存储器，所述存储器用于存储至少一条计算机程序，所述至少一条计算机程序由所述处理器加载并执行时，实现权利要求1至权利要求18中任一项所述的数据库系统的事务处理方法。
  21. 一种计算机可读存储介质，所述计算机可读存储介质中存储有至少一条计算机程序，所述至少一条计算机程序由处理器加载并执行时，实现权利要求1至权利要求18中任一项所述的数据库系统的事务处理方法。
  22. 一种计算机程序产品，包括计算机程序或指令，所述计算机程序或指令被处理器执行时，实现权利要求1至权利要求18中任一项所述的数据库系统的事务处理方法。
PCT/CN2022/087848 2021-05-19 2022-04-20 一种数据库系统的事务处理方法、装置、电子设备、计算机可读存储介质及计算机程序产品 WO2022242401A1 (zh)

Priority Applications (3)

Application Number Priority Date Filing Date Title
JP2023521163A JP2023546818A (ja) 2021-05-19 2022-04-20 データベースシステムのトランザクション処理方法、装置、電子機器、及びコンピュータプログラム
EP22803726.3A EP4239475A4 (en) 2021-05-19 2022-04-20 TRANSACTION PROCESSING METHOD AND APPARATUS FOR A DATABASE SYSTEM AND ELECTRONIC DEVICE, COMPUTER READABLE STORAGE MEDIUM AND COMPUTER PROGRAM PRODUCT
US18/072,629 US20230107958A1 (en) 2021-05-19 2022-11-30 Transaction processing method for database system, apparatus, electronic device, computer-readable storage medium, and computer program product

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
CN202110546080.0 2021-05-19
CN202110546080.0A CN115098228B (zh) 2021-05-19 2021-05-19 事务处理方法、装置、计算机设备及存储介质

Related Child Applications (1)

Application Number Title Priority Date Filing Date
US18/072,629 Continuation US20230107958A1 (en) 2021-05-19 2022-11-30 Transaction processing method for database system, apparatus, electronic device, computer-readable storage medium, and computer program product

Publications (1)

Publication Number Publication Date
WO2022242401A1 true WO2022242401A1 (zh) 2022-11-24

Family

ID=83287066

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/CN2022/087848 WO2022242401A1 (zh) 2021-05-19 2022-04-20 一种数据库系统的事务处理方法、装置、电子设备、计算机可读存储介质及计算机程序产品

Country Status (5)

Country Link
US (1) US20230107958A1 (zh)
EP (1) EP4239475A4 (zh)
JP (1) JP2023546818A (zh)
CN (1) CN115098228B (zh)
WO (1) WO2022242401A1 (zh)

Families Citing this family (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US12067219B2 (en) 2022-12-01 2024-08-20 Truist Bank Graphical user interface enabling entry manipulation
CN118733604A (zh) * 2024-09-03 2024-10-01 天翼视联科技有限公司 一种数据库更新方法、装置、电子装置和存储介质

Citations (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20170220617A1 (en) * 2016-02-01 2017-08-03 Yahoo! Inc. Scalable conflict detection in transaction management
CN111143389A (zh) * 2019-12-27 2020-05-12 腾讯科技（深圳）有限公司 事务执行方法、装置、计算机设备及存储介质
CN111209093A (zh) * 2020-01-16 2020-05-29 华东师范大学 一种分布式数据库系统中分布式事务的处理方法
CN111708615A (zh) * 2020-05-20 2020-09-25 腾讯科技（深圳）有限公司 事务处理方法、装置、计算机设备及存储介质
CN111736964A (zh) * 2020-07-02 2020-10-02 腾讯科技（深圳）有限公司 事务处理方法、装置、计算机设备及存储介质

Family Cites Families (7)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7933881B2 (en) * 2006-03-17 2011-04-26 Microsoft Corporation Concurrency control within an enterprise resource planning system
WO2017128028A1 (zh) * 2016-01-26 2017-08-03 华为技术有限公司 一种事务处理方法及装置
US10204130B2 (en) * 2016-03-23 2019-02-12 International Business Machines Corporation Transactional table truncation for concurrent transactions
CN108874587B (zh) * 2018-06-06 2022-01-14 亚信科技（中国）有限公司 一种事务的最终一致性保障方法及系统
CN109710388B (zh) * 2019-01-09 2022-10-21 腾讯科技（深圳）有限公司 数据读取方法、装置、电子设备以及存储介质
CN111444027B (zh) * 2020-03-24 2022-11-18 腾讯科技（深圳）有限公司 事务处理方法、装置、计算机设备及存储介质
CN112069196B (zh) * 2020-11-12 2021-03-23 腾讯科技（深圳）有限公司 基于数据库的数据处理方法、装置、设备及可读存储介质

Patent Citations (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US20170220617A1 (en) * 2016-02-01 2017-08-03 Yahoo! Inc. Scalable conflict detection in transaction management
CN111143389A (zh) * 2019-12-27 2020-05-12 腾讯科技（深圳）有限公司 事务执行方法、装置、计算机设备及存储介质
CN111209093A (zh) * 2020-01-16 2020-05-29 华东师范大学 一种分布式数据库系统中分布式事务的处理方法
CN111708615A (zh) * 2020-05-20 2020-09-25 腾讯科技（深圳）有限公司 事务处理方法、装置、计算机设备及存储介质
CN112231071A (zh) * 2020-05-20 2021-01-15 腾讯科技（深圳）有限公司 事务处理方法、装置、计算机设备及存储介质
CN111736964A (zh) * 2020-07-02 2020-10-02 腾讯科技（深圳）有限公司 事务处理方法、装置、计算机设备及存储介质

Non-Patent Citations (1)

* Cited by examiner, † Cited by third party
Title
See also references of EP4239475A4

Also Published As

Publication number Publication date
CN115098228B (zh) 2023-04-14
JP2023546818A (ja) 2023-11-08
EP4239475A1 (en) 2023-09-06
US20230107958A1 (en) 2023-04-06
CN115098228A (zh) 2022-09-23
EP4239475A4 (en) 2023-12-27

Similar Documents

Publication Publication Date Title
JP7546832B2 (ja) トランザクション処理方法、装置、コンピュータ機器及びコンピュータプログラム
CN111338766B (zh) 事务处理方法、装置、计算机设备及存储介质
WO2021233167A1 (zh) 事务处理方法、装置、计算机设备及存储介质
CN111736964B (zh) 事务处理方法、装置、计算机设备及存储介质
CN111597015B (zh) 事务处理方法、装置、计算机设备及存储介质
CN111444027B (zh) 事务处理方法、装置、计算机设备及存储介质
WO2022242401A1 (zh) 一种数据库系统的事务处理方法、装置、电子设备、计算机可读存储介质及计算机程序产品
US12111817B2 (en) Log execution method and apparatus, computer device and storage medium
CN115114374B (zh) 事务执行方法、装置、计算设备及存储介质
Waqas et al. Transaction management techniques and practices in current cloud computing environments: A survey
Krechowicz et al. Highly scalable distributed architecture for NoSQL datastore supporting strong consistency
WO2023065868A1 (zh) 事务执行方法、装置、计算设备及存储介质
WO2023124242A1 (zh) 事务执行方法、装置、设备和存储介质
Kanungo et al. Original Research Article Concurrency versus consistency in NoSQL databases
US11940972B2 (en) Execution of operations on partitioned tables
Ardekani et al. Non-monotonic snapshot isolation
Mukherjee et al. Data mining-based hierarchical transaction model for multi-level consistency management in large-scale replicated databases
Thakare et al. NoSQL Databases: Modern Data Systems for Big Data Analytics-Features, Categorization and Comparison
Cao Big Data Database for Business
Demchenko et al. Data Structures for Big Data, Modern Big Data SQL and NoSQL Databases
Shahida Examining and juxtaposing the two NoSQL databases MongoDB and CouchDB
Jolson A Method for Selective Update Propagation in Replicated Databases
Bukhari et al. NoSQL Data Stores

Legal Events

Date Code Title Description
121 Ep: the epo has been informed by wipo that ep was designated in this application

Ref document number: 22803726

Country of ref document: EP

Kind code of ref document: A1

ENP Entry into the national phase

Ref document number: 2023521163

Country of ref document: JP

Kind code of ref document: A

ENP Entry into the national phase

Ref document number: 2022803726

Country of ref document: EP

Effective date: 20230601

NENP Non-entry into the national phase

Ref country code: DE