Search

CN-116303495-B - Database system and method supporting parallel updating

CN116303495BCN 116303495 BCN116303495 BCN 116303495BCN-116303495-B

Abstract

The invention provides a database system and a method supporting parallel updating, which relate to the technical field of databases and comprise that a concurrency control protocol caches a maximum reading time stamp, a maximum writing time stamp and a maximum common writing time stamp for each data item in a database; the method comprises the steps of recording a common log and an increment log by a pre-write log module, caching the common record with the largest version number of a data item and all increment records after the common record, storing the record in the cache to a persistence medium by a persistence module, controlling write operation by a write flow control module, judging and executing common write and increment write respectively and generating the common record and the increment record if a transaction time stamp is larger than a maximum read time stamp, updating the maximum write time stamp and the maximum common write time stamp, maintaining a dependency graph according to dependency between read transactions and write transactions by the read flow control module, and executing the read transactions after all the write transactions in the dependency graph are executed. The invention supports parallel updating, ensures the ACID and the serializable isolation level, and is stepless in rollback.

Inventors

  • CHEN XIAOFAN

Assignees

  • 陈晓帆

Dates

Publication Date
20260505
Application Date
20230224

Claims (11)

  1. 1. The database system supporting parallel updating is characterized by comprising a concurrency control protocol, a pre-write log module, a cache module, a persistence module, a write flow control module and a read flow control module; the concurrency control protocol is used for: when each transaction is controlled to start, a timestamp is obtained from a timestamp service and used as the version numbers of all records following the transaction; For each read data item Q in the database, caching the timestamp of the maximum transaction of the read data item in the memory as the maximum read timestamp, inquiring the range in the database, decomposing the range into disjoint intervals, and caching the timestamp of the maximum transaction of the read intervals in the memory as the gap maximum read timestamp; For each written data item in the database, respectively caching the time stamp of the maximum transaction written with the data item and the maximum transaction time stamp of the common record written with the data item in the memory as the maximum writing time stamp and the maximum common writing time stamp; the pre-write log module is used for: recording logs in two formats of a common log and an incremental log, wherein the pre-written log needs to be synchronously stored in a sustainable medium; The cache module is used for: the method comprises the steps of caching a common record with the largest version number of each data item and all subsequent increment records in a memory, storing the common record and the increment records which are written for transactions in a cache module, respectively generating a Writer object corresponding to each common record or increment record, wherein the common record records a specific determined value, the increment records only record increment operation, the increment operation is only limited to operation which can be expressed as a function which only receives the data item as an independent variable, and for updating operation which can not be expressed as a function which only receives the data item as an independent variable, the operation needs to be converted into a read-change-write operation and generates the common record, and the read-change-write operation does not support parallel update; The persistence module is used for: asynchronously storing the records in the cache into a persistence medium, wherein the persistence module also supports the fast searching of the database records according to the data item primary key and version number; the write flow control module is used for: Judging the time stamp of the transaction for writing the data item, if the time stamp is smaller than the maximum reading time stamp of the data item cached in the memory, rolling back the transaction, otherwise, respectively executing writing operation aiming at common writing operation and increment updating operation: The method comprises the steps of performing normal writing operation on a data item, further judging whether the time stamp of a transaction for writing the data item is smaller than the maximum writing time stamp of the data item cached in a memory, and rolling back the transaction if the time stamp is smaller than the maximum writing time stamp of the data item; the increment updating operation of the data item further judges whether the time stamp of the transaction for writing the data item is smaller than the maximum common writing time stamp of the data item cached in the memory, if so, the transaction is rolled back, otherwise, the maximum writing time stamp of the data item is updated, and an increment log and an increment record are generated; The read flow control module is used for: generating a Reader object according to the transaction of the read data item; For the data item to be read by the transaction, acquiring the last common record and all increment records after the last common record which is cached in the memory and is smaller than the transaction time stamp; if the cache is not hit, loading the last common record smaller than the transaction time stamp and all the records after the last common record from the persistence module into the cache; maintaining a dependency graph of a Reader object based on a last normal record and all subsequent incremental records according to a dependency relationship between transactions of the read data item and transactions of the write data item; executing the Reader object after the execution of the Writer object corresponding to the common record and all subsequent increment records in the dependency graph is finished; The Reader object merges the values of all the Writer objects it depends on from the dependency graph, obtains the value of the data item to be read, and atomically updates the maximum read timestamp.
  2. 2. The database system supporting parallel updating according to claim 1, wherein said maintaining a dependency graph based on a last normal record and all incremental records thereafter based on a dependency relationship between transactions for reading data items and transactions for writing data items, comprises: Each common record or incremental record respectively forms a Writer object, the Writer corresponding to the common record is called as a common Writer, the Writer corresponding to the incremental record is called as an incremental Writer, and the value of the Writer is the corresponding common or incremental record; All sides of the dependency graph start from one Writer object to the end of the Reader object.
  3. 3. The database system supporting parallel updating according to claim 1, wherein maintaining a dependency graph of a Reader object based on a last normal record and all incremental records after the last normal record comprises: When the dependency graph of the Reader object is established, if a new transaction for writing the data item corresponding to the data item to be read of the Reader object arrives, updating the dependency graph of the Reader object; When the transaction of the write database corresponding to the last common record or any increment record rolls back, the dependency graph of all data items written by the transaction also needs to be updated.
  4. 4. The database system supporting parallel updating of claim 1, further comprising a dependency graph optimization module for periodically and quantitatively fusing incremental records, comprising: When the common record of the data item and the corresponding transaction of the subsequent continuous increment record are submitted, merging all the records and generating a new common record, wherein the new common record adopts the version number of the last increment record and updates the maximum common writing time stamp, and meanwhile, the merged record is saved in a persistence module and is deleted from a cache.
  5. 5. The database system supporting parallel updating according to claim 1, further comprising a dependency graph optimization module for: And generating a dependency graph for the Reader of the placeholder transaction, wherein the subsequent transaction which reads the data item and has the timestamp larger than the Reader version number in the placeholder transaction only needs to depend on the Writer of the placeholder transaction, and when the Reader object corresponding to the placeholder transaction is executed, replacing the value of the Writer corresponding to the placeholder transaction with the read value and submitting the placeholder transaction.
  6. 6. The database system supporting parallel updating according to claim 1, further comprising a constraint updating and conditional updating module; The constraint updating and condition updating module is used for: When the transaction of writing the data item is incremental updating operation, calculating the value range of the data item after the current incremental updating operation, judging whether an intersection exists between the current incremental updating operation and the constraint range, if not, proving that the incremental updating operation is illegal, and rolling back the transaction, otherwise, further judging whether the transaction is a subset of the constraint range, if the transaction is a subset of the constraint range, proving that the operation is legal, continuing to execute the transaction, and finishing the incremental updating of the data item with the constraint condition, otherwise, converting the operation into read-change-write operation, and not performing parallel updating; When the transaction of writing data item is increment updating operation, calculating the definition domain range of the data item before the current increment updating operation, judging whether the intersection exists with the updating condition, if not, proving that the increment updating operation is illegal, and rolling back the transaction, otherwise, further judging whether the increment updating operation is a subset of the updating condition, if so, proving that the operation is legal, and continuing to execute the transaction, otherwise, converting the operation into read-change-write operation, and not carrying out parallel updating.
  7. 7. The database system supporting parallel updating according to claim 6, wherein the defining and updating method of the definition domain range and the value domain range comprises: Assuming that the initial submitted value of the data item is v, the value range of the data item is [ v, v ], denoted range key , and the definition range is also [ v, v ], denoted domain key ; For each incremental update operation DELTAWRITERW, w.f represents the function corresponding to the w update operation, then: range key ＝w.f.map(domain key ) domain′ key ＝domain key ∪range key the value range and the definition range are updated according to the size sequence of the transaction time stamp for the non-exchangeable updating operation, and the updating operation is irrelevant to the sequence and can be updated out of order.
  8. 8. The database system supporting parallel updating according to claim 1, further comprising an index updating module; the index updating module is used for: when a unique index exists on an update column of the updated data item, the update operation needs to be converted into a read-change-write operation, and parallel update is not performed any more; When a non-unique index exists on the update column of the updated data item, the parallel update is still performed at the moment, and the method comprises the following steps: Creating a non-unique index item while updating the data item, the non-unique index item comprising: The main key column is coded into an index name-index value-main key value-transaction version number of the indexed data item, wherein the index value is the value of the index column, and the transaction version number is the transaction version number for creating the index; For the data item of the increment record, the index value is set to be ambiguous, and the value of the index metadata column is the value field of the data item; For the query index_column E C using the index, setting the timestamp of the query transaction as TS q , firstly updating the maximum gap read timestamp of the query condition C { undefined } and then scanning the index item with the index value not undefined and adding the index item meeting the query condition and the transaction visibility into the result set R, then scanning the index item with the index value undefined, firstly judging whether the visibility is met or not, if not, skipping the index item, otherwise, continuing judging the relation between the value field of the index item and the query condition set, if not, skipping the data item, otherwise, if the value field of the index item is a subset of the query condition set, adding the index item into the result set R, otherwise, registering a Reader object for the data item corresponding to the main key value of the indexed data item, setting the timestamp of the Reader object as the version number of the index item, executing the Reader, if not met, and if not meeting the index value read condition, and if not meeting the query condition, then skipping the result set R.
  9. 9. The database system supporting parallel updating according to claim 1, 6 or 8, wherein the update operation is converted into a read-modify-write operation by first registering a Reader and a placeholder Writer with a current transaction time stamp as a version number, performing the read process to obtain a value of a current data item, applying the update operation, then replacing the value in the placeholder Writer with the updated value, and performing the write process.
  10. 10. The database system supporting parallel updating of claim 8, wherein said index updating module is further configured to clean up ambiguous indexes, comprising: When a large number of ambiguous indexes exist in the system, the query performance is obviously slowed down, the ambiguous indexes need to be cleaned regularly, and the cleaning method is as follows: Scanning the ambiguous index, for each ambiguous index, registering a Reader object for the data item corresponding to the main key value of the indexed data item, waiting for the total submission of the Writer object relied on by the Reader object, changing the value of the index item into a determined value, creating a new index item, using the determined value by the index value, and deleting the corresponding ambiguous index item after the creation is completed.
  11. 11. A method of applying the database system supporting parallel updating according to any one of claims 1 to 10, comprising a read transaction concurrency control method and a write transaction concurrency control method; the write transaction concurrency control method comprises the following steps: when each transaction starts, a timestamp is obtained from a timestamp service and is used as a version number of a subsequent record of each transaction; If the timestamp of the transaction is smaller than the maximum read timestamp, rollback is performed, otherwise, write operations are respectively performed for normal write operations and incremental update operations: The method comprises the steps of performing normal writing operation on a data item, further judging whether the time stamp of a transaction for writing the data item is smaller than the maximum writing time stamp of the data item cached in a memory, and rolling back the transaction if the time stamp is smaller than the maximum writing time stamp of the data item; the increment updating operation of the data item further judges whether the time stamp of the transaction for writing the data item is smaller than the maximum common writing time stamp of the data item cached in the memory, if so, the transaction is rolled back, otherwise, the maximum writing time stamp of the data item is updated, and an increment log and an increment record are generated; the read transaction concurrency control method comprises the following steps: when each transaction starts, a timestamp is obtained from a timestamp service and is used as a version number of a subsequent record of each transaction; reading each data item for the transaction to generate a Reader object respectively; for each data item to be read by the transaction, respectively acquiring the last common record and all subsequent increment records which are cached in the memory and are smaller than the corresponding transaction time stamp, and if the cache is not hit, loading the last common record and all subsequent records which are smaller than the transaction time stamp from the persistence module into the cache; maintaining a dependency graph of a Reader object based on a last normal record and all subsequent incremental records according to a dependency relationship between transactions of the read data item and transactions of the write data item; Executing the Reader object when the last common record and all increment records after the last common record in the dependency graph are submitted data; The Reader object merges the values of all the Writer objects it depends on from the dependency graph, obtains the value of the data item to be read, and atomically updates the maximum read timestamp.

Description

Database system and method supporting parallel updating Technical Field The present invention relates to the field of database technologies, and in particular, to a database system and method supporting parallel update. Background Concurrency control is a mechanism for protecting database integrity, ensuring timely correction of errors caused by concurrent operations when multiple users are performing write transactions at the same time. The basic unit of concurrency control is a transaction. Incorrect concurrency mechanisms may lead to dirty, phantom, and unrepeatable reads. The purpose of concurrency control is to ensure that one user's work does not have an unreasonable impact on another user's work. In some cases, these measures ensure that when a user operates with other users, the results obtained are the same as when he operates alone. Traditionally, database systems use four schemes to serialize conflicting concurrent transactions, (1) two-phase-locking, (2) timestamp-based protocols, typically represented by timestamp ordering protocol (TIMESTAMP ORDERING), (3) optimistically concurrent transaction control (optimistic concurrencycontrol), (4) allow for dirty reads, i.e., allow for cascading rollbacks (e.g., rubatoDB, hyper, etc.), the first three methods support only concurrent updates (concurrent update) and cannot support concurrent updates (parallel updates), and the fourth method supports concurrent updates (parallel updates), but with cascaded scheduling, i.e., requiring cascading rollbacks, which is typically a poor design because rollbacks of one transaction can result in subsequent thousands of transaction rollbacks, greatly affecting system performance, and creating severe performance jitter. The concurrent update refers to that the concurrent transactions are handed to the processor for processing at different time points, and the concurrent transactions do not run simultaneously at the same time point, and the concurrent update refers to that the conflicting update transactions can be independently performed, and the conflicting transactions can run simultaneously at the same time point. Microsoft corporation 2018 proposed fasterKV that although parallel update can be supported, ACID cannot be guaranteed, and ACID is four characteristics that a database management system (DBMS) must possess to ensure that a transaction (transaction) is correct and reliable during writing or updating data, namely, atomicity (atomicity), consistency, isolation (independence), and persistence (durability), so fasterKV is not a database system in a strict sense, but is not a reliable database system supporting parallel update. Disclosure of Invention Aiming at the problems that when the database system processes concurrent transactions, the traditional scheme part cannot support parallel update, and the traditional scheme part adopts dirty reading which allows cascade rollback to carry out parallel update, so that the performance of the database is seriously influenced, and the novel scheme fasterKV cannot guarantee ACID. In order to achieve the above purpose, the invention provides a database system supporting parallel update, which comprises a concurrency control protocol, a pre-writing log module, a cache module, a persistence module, a writing flow control module and a reading flow control module; the concurrency control protocol is used for: when each transaction is controlled to start, a timestamp is obtained from a timestamp service and used as the version numbers of all records following the transaction; For each read data item Q in the database, caching the timestamp of the maximum transaction of the read data item in the memory as the maximum read timestamp, inquiring the range in the database, decomposing the range into disjoint intervals, and caching the timestamp of the maximum transaction of the read intervals in the memory as the gap maximum read timestamp; For each written data item in the database, respectively caching the time stamp of the maximum transaction written with the data item and the maximum transaction time stamp of the common record written with the data item in the memory as the maximum writing time stamp and the maximum common writing time stamp; the pre-write log module is used for: recording logs in two formats of a common log and an incremental log, wherein the pre-written log needs to be synchronously stored in a sustainable medium; The cache module is used for: the method comprises the steps of caching a common record with the largest version number of each data item and all subsequent increment records in a memory, storing the common record and the increment records which are written for transactions in a cache module, respectively generating a Writer object corresponding to each common record or increment record, wherein the common record records a specific determined value, the increment records only record increment operation, the increment operation is only limited t