CN111459920B - Multi-version concurrency control method and system based on virtual global clock synchronization - Google Patents
Multi-version concurrency control method and system based on virtual global clock synchronization Download PDFInfo
- Publication number
- CN111459920B CN111459920B CN202010409995.2A CN202010409995A CN111459920B CN 111459920 B CN111459920 B CN 111459920B CN 202010409995 A CN202010409995 A CN 202010409995A CN 111459920 B CN111459920 B CN 111459920B
- Authority
- CN
- China
- Prior art keywords
- timestamp
- read
- tuple
- write
- transaction
- Prior art date
- Legal status (The legal status 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 status listed.)
- Active
Links
Images
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; 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
- G06F16/219—Managing data history or versioning
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; 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/27—Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
- G06F16/275—Synchronous replication
Landscapes
- Engineering & Computer Science (AREA)
- Databases & Information Systems (AREA)
- Theoretical Computer Science (AREA)
- Data Mining & Analysis (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Computing Systems (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
The invention discloses a multi-version concurrency control method and a system based on virtual global clock synchronization, wherein the method comprises the following steps: reading data; calculating and verifying a version timestamp; and writing the values of the tuples in the writing set into the positions of tuple storage in the database, and updating the read time stamp and the write time stamp of the related tuples. The system comprises a data reading module, a data processing module and a data processing module, wherein the data reading module is used for reading and copying all tuples involved by the current transaction; the time stamp calculating module is used for calculating the submission time stamp of the current transaction according to the read time stamp and the write time stamp of the currently designed tuple; the timestamp verifying module is used for verifying whether the calculated timestamp is valid; and the data writing module is used for writing the time stamp and the modified tuple which are successfully verified into the database storage. The beneficial effects are that: by examining the accessed tuples, the timestamp of each transaction is calculated lazily at the time of commit of the transaction, so that the limited ordering situation can be avoided.
Description
Technical Field
The invention belongs to a database version control method, and particularly relates to a multi-version concurrent control method of a database.
Background
Under a centralized lock table or timestamp manager, locking of tables is a competing key point in database management systems. By implementing these data structures in tuple units, each transaction latches only the tuples it needs, which can significantly improve scalability. Although the memory overhead may increase, the overhead of these metadata (typically a few bytes) is negligible for large tuples.
The access to the mutex is very costly and requires multiple messages to be sent on the chip. Protecting the critical portion by a mutually exclusive lock will limit the scalability of the system and thus avoid the use of mutually exclusive locks on the critical path. The main bottleneck of the Two-Phase Locking (2 PL) algorithm is the centralized deadlock detector; the main bottleneck of the T/O algorithm is the centralized timestamp distributor.
Hardware support may alleviate timestamp allocation bottlenecks. However, maintaining perfectly synchronized clocks in large, multi-core systems is difficult because the systems use different clock sources that drift over time. Keeping these clocks perfectly synchronized requires adjusting the communication in progress unreasonably or requires a very low frequency global clock source. On a domestic processor, the bottleneck effect of the centralized timestamp distributor is very obvious due to the large number of cores.
Ideally, a concurrency control scheme should limit the inherent parallelism in transactional workloads as little as possible while introducing a small administrative overhead that can scale well with the number of cores. Concurrent control schemes that have emerged in recent years are essentially based on T/O. The T/O scheme assigns a unique, monotonically increasing timestamp to each transaction. The database system then uses these timestamps to process the conflicting operations in the correct order. The two most common variants of T/O are multi-version concurrency control and optimistic concurrency control.
The T/O scheme uses a shared memory counter to generate timestamps, which limits it to millions of transactions per second, orders of magnitude lower than modern On-Line Transaction Processing (OLTP) workload requirements. There have also been some previous studies that proposed hardware and software techniques to increase timestamp allocation throughput, but both of these approaches have serious limitations.
In terms of hardware, centralized asynchronous counters, remote atomic memory operations, and fully synchronous clocks alleviate the timestamp distribution bottleneck, but are very complex to implement and especially not yet usable in the current environment.
In software terms, coarse-grained timestamp periodicity of packet submissions reduces the frequency of timestamp assignments, but still limits concurrency in common scenarios.
Conventional Optimistic Concurrency Control (OCC) algorithms statically assign timestamps to transactions, which, while simplifying collision detection, limits Concurrency. In this example, if transaction A is assigned a lower timestamp than transaction B, A may commit because the interruption of the operation is consistent with the timestamp order. However, if transaction A is assigned a higher timestamp than transaction B, A must eventually abort, as committing it would violate the principle of sequential increase in timestamps.
Disclosure of Invention
The invention aims to provide a multi-version concurrency control method based on virtual global clock synchronization, wherein the commit timestamp of a transaction is calculated in a distributed mode in a delayed mode at the commit time according to an accessed tuple of the transaction.
The technical scheme of the invention is as follows: the multi-version concurrency control method based on virtual global clock synchronization comprises the following steps:
the method comprises the following steps: reading data;
copying the accessed tuple according to the current transaction requirement, and reading the data value of the related tuple and the current read-write timestamp in an atomic mode;
step two: calculating and verifying a version timestamp;
step three: and writing the values of the tuples in the writing set into the positions of tuple storage in the database, and updating the read time stamp and the write time stamp of the related tuples.
In a preferred embodiment of the present invention, the first step comprises the following steps:
step 101: applying locking by affairs;
step 102: maintaining a separate read set and write set for the current transaction, wherein the encoding format of each entry in the read or write set is { tuple, data, write timestamp, read timestamp }, wherein the tuple is a pointer pointing to the tuple in the database, the data is a data value stored in the tuple of the current version, and the write timestamp and the read timestamp are respectively a write timestamp and a read timestamp in the duplicated tuple;
step 103: traversing the tuples accessed by the transaction in sequence;
step 104: copying the accessed tuple entities to a read set, wherein the read set is only visible to the current transaction;
step 105: storing a pointer pointing to a tuple in the tuple of the reading set according to the request type, storing the value of the read tuple in the data of the reading set, storing the write timestamp of the read tuple in the write timestamp of the reading set, and storing the read timestamp of the read tuple in the read timestamp of the reading set;
step 106: optionally, writing the tuple value to be modified into a write set, where the write set is visible only to the current transaction;
step 107: optionally, the pointer pointing to the tuple is stored in the write-in set according to the request type, a new value of the tuple is stored in the data of the write-in set, a write timestamp of the read tuple is stored in the write timestamp of the write-in set, and a read timestamp of the read tuple is stored in the read timestamp of the write-in set;
step 108: loading the recorded data values using an atomic approach;
step 109: and loading the record read-write time stamp in an atomic mode.
In a preferred embodiment of the present invention, the second step comprises the following steps:
step 201: locking all tuples in the transaction write set in order;
step 202: traversing each entry in the read set and the write set, and calculating the commit timestamp of the current transaction;
step 203: for tuples only in the read set but not in the write set, submitting the maximum value of the write timestamp in the timestamp read set and the current computation timestamp;
step 204: for tuples in the transaction write-in set, the commit timestamp takes the maximum value of the read timestamp +1 of the current tuple and the current computation timestamp;
step 205: verifying the tuples in the transaction reading set one by one;
step 206: if the commit timestamp of the transaction is less than or equal to the read timestamp of the read set tuple, the tuple version read by the transaction is valid at the commit timestamp without further operation;
step 207: if the read timestamp of the tuple is smaller than the commit timestamp, and if the write timestamp in the read-write set is different from the latest write timestamp (in the current tuple pointer), the read timestamp of the local version cannot be extended, and at this time, the current transaction rollback is realized in an atomic mode;
step 208: if the write timestamp in the read-write set is matched with the actual write timestamp in the current tuple, the latest read timestamp of the tuple is less than or equal to the commit timestamp of the transaction, but the tuple is locked by another transaction and is not in the write set of the transaction, and the rollback of the current transaction is realized in an atomic mode;
step 209: if the read timestamp is extensible, or if the version is already valid in the commit timestamp, atomically implementing the extension of the read timestamp of the tuple to the commit timestamp of the transaction;
step 210: all tuples accessed by the transaction are validated and the transaction enters the write phase.
In a preferred embodiment of the present invention, the third step includes the following steps:
step 301: traversing each tuple in the transaction write set;
step 302: writing the value of the write tuple in the write set into the position of the tuple pointer in the database;
step 303: the system sets the write timestamp and the read timestamp thereof as a commit timestamp, indicating the new version;
step 304: all locks acquired during the validation phase are released, making the changes visible to all other transactions.
A multi-version concurrency control system based on virtual global clock synchronization comprises the following modules,
the data reading module is used for reading and copying all tuples involved by the current transaction;
the time stamp calculating module is used for calculating the submission time stamp of the current transaction according to the read time stamp and the write time stamp of the currently designed tuple;
the timestamp verifying module is used for verifying whether the calculated timestamp is valid;
and the data writing module is used for writing the time stamp and the modified tuple which are successfully verified into the database storage.
In a preferred embodiment of the present invention, the data reading module is configured to read and copy all tuples involved in the current transaction from the storage, and maintain a separate read set and write set for the current transaction, and in the data reading module, the accessed tuples in the storage are copied to the read set, and the modified tuples are stored in the write set, and the read set and the write set are only visible to the current transaction.
In a preferred embodiment of the present invention, the timestamp calculation module is configured to calculate a commit timestamp of a current transaction according to a read set and a write set generated in the data reading module, lock tuples in the write set, prevent other transactions from updating tuples simultaneously, and ensure that no deadlock exists when other transactions are committed simultaneously by using a fixed locking order.
In a preferred embodiment of the present invention, when the time stamp calculating module calculates the commit time stamp of the current transaction, the commit time stamp is not less than the write time stamp of the tuple in the read set and not less than the read time stamp of the tuple in the write set.
In a preferred embodiment of the present invention, the timestamp verifying module is configured to verify whether the submission timestamp obtained by the timestamp calculating module is valid;
if the submission timestamp is less than or equal to the reading timestamp of the tuple in the reading set, the tuple version read by the transaction is valid at the position of the submission timestamp;
if the commit timestamp is larger than the read timestamp in the read set, the tuple version read in the read set may fail, if no other transaction modifies the tuple, the read timestamp of the tuple is modified to be the commit timestamp, otherwise, the current transaction is terminated;
there is no need to verify tuples in the write set only, which have acquired the lock before the commit timestamp was calculated and will not be modified.
In a preferred embodiment of the present invention, the data writing module is configured to write a write set in which all tuples pass verification to the database storage;
for each tuple in the write set, updating the value of the tuple in the storage, updating the write timestamp and the read timestamp in the storage to be the commit timestamp of the current transaction, and releasing all locks acquired by the timestamp calculation module to make the modified tuple visible to other transactions.
The invention has the beneficial effects that: compared with the existing method, the method does not statically allocate the time stamp, so that the potential sorting condition can not occur. The present invention computes the timestamp of each transaction lazily at the time of commit of the transaction by checking the accessed tuples, thus avoiding the limited ordering situation. For example: when transaction A reaches its commit point, the method computes the command's timestamp using the versions of tuples x and y actually read/written instead of the latest version now in the database (the modified version of transaction B). Since the version of tuple x read by transaction A is older than the version written by B, the x version read by transaction A is queued before transaction B and can commit. As with the standard OCC algorithm, each transaction in the method accesses the database during the read phase, but does not apply for a lock during normal operation. When a transaction performs a commit operation, the transaction is acquired through an authentication phase to check if commit should be allowed. If so, a write phase is entered to apply the changes of the transaction to the shared database. Because all reads and writes in a transaction occur at the same timestamp, serializable execution can be assured, read operations always return the version valid at that timestamp, and write operations are guaranteed to proceed after all reads to the old version of the same tuple have ended.
Drawings
FIG. 1 is a diagram of a multi-version concurrency control process based on virtual global clock synchronization;
FIG. 2 is a process diagram of a read phase;
FIG. 3 is a process diagram of a verification phase;
FIG. 4 is a flowchart of the write step;
FIG. 5 is a time stamp encoding format — the encoding of lock identification bits, write time stamps and read time stamps of tuples;
FIG. 6 is a schematic diagram of a multi-version concurrency control system based on virtual global clock synchronization according to the present invention;
FIG. 7 is a diagram illustrating concurrent transactions in a multi-version concurrency control system based on virtual global clock synchronization.
Detailed Description
In order to make the aforementioned objects, features and advantages of the present invention comprehensible, embodiments accompanied with figures are described in further detail below.
The multi-version concurrency control method based on virtual global clock synchronization comprises the following steps:
the method comprises the following steps: reading data;
and copying the accessed tuple according to the current transaction requirement, and reading the data value of the related tuple and the current read-write timestamp in an atomic mode.
In an embodiment of the present invention, the method specifically includes:
step 101: applying locking by affairs;
step 102: maintaining a separate read set and write set for the current transaction, wherein the encoding format of each entry in the read or write set is { tuple, data, write timestamp, read timestamp }, wherein the tuple is a pointer pointing to the tuple in the database, the data is a data value stored in the tuple of the current version, and the write timestamp and the read timestamp are respectively a write timestamp and a read timestamp in the duplicated tuple;
step 103: traversing the tuples accessed by the transaction in sequence;
step 104: copying the accessed tuple entities to a read set, wherein the read set is only visible to the current transaction;
step 105: storing a pointer pointing to a tuple in the tuple of the reading set according to the request type, storing the value of the read tuple in the data of the reading set, storing the write timestamp of the read tuple in the write timestamp of the reading set, and storing the read timestamp of the read tuple in the read timestamp of the reading set;
step 106: optionally, writing the tuple value to be modified into a write set, where the write set is visible only to the current transaction;
step 107: optionally, the pointer pointing to the tuple is stored in the write-in set according to the request type, a new value of the tuple is stored in the data of the write-in set, a write timestamp of the read tuple is stored in the write timestamp of the write-in set, and a read timestamp of the read tuple is stored in the read timestamp of the write-in set;
step 108: loading the recorded data values using an atomic approach;
step 109: loading and recording a read-write timestamp by using an atomic mode;
loading the read tuple data value and the read-write timestamp by using an atomic mode, and ensuring that the value is matched with the timestamp; every transaction will access the database but will not apply for a lock during normal operation.
Step two: calculating and verifying a version timestamp;
all tuples in the write set are locked from modification by other transactions. Traversing each entry in the read set and the write set one by one, and calculating the timestamp of the tuple only in the read set according to the principle that the current transaction submission timestamp is greater than or equal to the write timestamp in the read set and is greater than or equal to the current calculation timestamp of the tuple only in the read set, wherein the tuple only in the read set is not in the write set; and calculating the commit timestamp of the current transaction according to the principle that the commit timestamp of the current transaction is greater than the read timestamp of the current tuple and is greater than or equal to the current calculation timestamp of the tuple in the write set. And after the calculation is finished, verifying whether the tuples in the reading set are extensible or not one by one. And when the commit timestamp of the current transaction is less than or equal to the read timestamp of the read set entry, the tuple version read by the current transaction is valid, and at the moment, the read timestamp in the tuple is modified into the commit timestamp of the current transaction in an atomic mode.
In an embodiment of the present invention, the method specifically includes:
step 201: locking all tuples in the transaction write set in order;
step 202: traversing each entry in the read set and the write set, and calculating the commit timestamp of the current transaction;
step 203: for tuples only in the read set but not in the write set, submitting the maximum value of the write timestamp in the timestamp read set and the current computation timestamp;
step 204: for tuples in the transaction write-in set, the commit timestamp takes the maximum value of the read timestamp +1 of the current tuple and the current computation timestamp;
step 205: verifying the tuples in the transaction reading set one by one;
step 206: if the commit timestamp of the transaction is less than or equal to the read timestamp of the read set tuple, the tuple version read by the transaction is valid at the commit timestamp without further operation;
step 207: if the read timestamp of the tuple is smaller than the commit timestamp, and if the write timestamp in the read-write set is different from the latest write timestamp (in the current tuple pointer), the read timestamp of the local version cannot be extended, and at this time, the current transaction rollback is realized in an atomic mode;
step 208: if the write timestamp in the read-write set is matched with the actual write timestamp in the current tuple, the latest read timestamp of the tuple is less than or equal to the commit timestamp of the transaction, but the tuple is locked by another transaction and is not in the write set of the transaction, and the rollback of the current transaction is realized in an atomic mode;
step 209: if the read timestamp is extensible, or if the version is already valid in the commit timestamp, atomically implementing the extension of the read timestamp of the tuple to the commit timestamp of the transaction;
step 210: all tuples accessed by the transaction are validated and the transaction enters the write phase.
In a transaction commit rule based on a global virtual clock sequence, there are no concentrated contention points during execution of the transaction, and the lock and atomic portion only protects the tuples that the transaction touches.
Step three: and writing the values of the tuples in the writing set into the positions of tuple storage in the database, and updating the read time stamp and the write time stamp of the related tuples.
In an embodiment of the present invention, the method specifically includes:
step 301: traversing each tuple in the transaction write set;
step 302: writing the value of the write tuple in the write set into the position of the tuple pointer in the database;
step 303: the system sets the write timestamp and the read timestamp thereof as a commit timestamp, indicating the new version;
step 304: all locks acquired during the validation phase are released, making the changes visible to all other transactions.
In this example, the read and verify phases require that the time stamp of the tuple be read or written atomically. Current techniques directly use locks to implement these atomic operations can degrade performance. To avoid this problem, the system encodes the write timestamp, read timestamp of the lock identification bits and tuples into a single 64-bit word of the form (timestamp format encoding):
the most significant bit is used as the lock identification bit and the write timestamp is stored as a 48-bit counter, and to handle write timestamp overflows, tuples in the database are periodically loaded in the background to reset their write timestamps. At the same time, the database management system uses atomic compare-swap instructions to ensure that the encoded timestamps are not modified by other transactions at the same time.
Lock-free implementation of atomic load tuple data and timestamps: the encoded time stamp is loaded twice before and after loading the data. If the two encoded timestamp instances are the same and both have no lock bits set, the data value must not be altered and still remain consistent with the timestamp. Otherwise, the process is repeated until both timestamps coincide. During this process, no shared memory is written. To avoid starvation, if this check fails repeatedly, it can be reverted to a heavyweight lock.
Read timestamp of the tuple is extended atomically: if the commit timestamp is greater than the local read timestamp, this operation is invoked and the system validates the local version at the commit timestamp by extending the read timestamp of the tuple. If the read timestamp of the tuple cannot extend to the commit timestamp, the validation fails.
If the difference value overflows, the write time stamp is increased to keep the difference value within 15 bits, and the operation does not influence the correctness of the virtual global clock sequence.
Finally, the new write timestamp and difference are written to the new encoded timestamp and applied atomically to the tuple. The system uses atomic compare and swap instructions to ensure that the encoded timestamps are not modified by other transactions simultaneously.
Each data version in the method stores a valid range of time stamps, the validity of which is defined by a write time stamp and a read time stamp. In particular, the version-specific timestamp is created when the timestamp is written and is valid before the timestamp is read. The version read by the transaction is valid if and only if the commit timestamp of the transaction lies between the write timestamp and the read timestamp of the version. A write operation of a transaction is valid if and only if the commit timestamp of the transaction is greater than the read timestamp of the previous version.
Taking two concurrent transactions A, B as an example, a transaction call operation sequence as shown in the concurrent transaction operation example of FIG. 1, when transaction A, which starts first in time order, reads tuple x, transaction B modifies x and transaction B commits first. If no tuple record is made, the version of read x at the time transaction A commits has been modified by transaction B.
A multi-version concurrency control system based on virtual global clock synchronization can process a plurality of transactions concurrently, and each transaction processing comprises the following modules:
the data reading module is used for reading and copying all tuples involved by the current transaction;
the time stamp calculating module is used for calculating the submission time stamp of the current transaction according to the read time stamp and the write time stamp of the currently designed tuple;
the timestamp verifying module is used for verifying whether the calculated timestamp is valid;
and the data writing module is used for writing the time stamp and the modified tuple which are successfully verified into the database storage.
As an optional embodiment for implementing the multi-version concurrency control system based on virtual global clock synchronization according to the embodiment of the present invention, fig. 6 is an optional schematic diagram provided in the embodiment of the present invention. Referring to fig. 6, the multi-version concurrency control system based on virtual global clock synchronization of the present invention can concurrently process a plurality of transactions. Each transaction can correctly read and modify data in the database store.
And the data reading module 11 is configured to read and copy all tuples involved in the current transaction from the storage, and maintain a separate read set and write set for the current transaction. In this module, the accessed tuples in storage are copied to the read set and the modified tuples are saved to the write set. The read set and write set are visible only to the current transaction.
And a timestamp calculation module 12, configured to calculate a commit timestamp of the current transaction according to the read set and the write set generated in the data reading module 11. Locking writes to tuples in the set prevents other transactions from updating tuples at the same time. Using a fixed locking order may ensure that there are no deadlocks while other transactions are committed at the same time.
When the time stamp calculating module 12 calculates the commit time stamp of the current transaction, for the tuples only in the read set but not in the write set, the commit time stamp is not less than the write time stamp of the tuple in the read set, and for the tuples in the write set, the commit time stamp is not less than the read time stamp of the current tuple.
And the timestamp verifying module 13 is configured to verify whether the submission timestamp obtained by the timestamp calculating module 12 is valid. If the commit timestamp is less than or equal to the read timestamp of the tuple in the read set, the tuple version read by the transaction is valid at the location of the commit timestamp. If the commit timestamp is greater than the read timestamp in the read set, the tuple version read in the read set may fail, if no other transaction modifies the tuple, the read timestamp of the tuple is modified to the commit timestamp, otherwise the current transaction is terminated. There is no need to verify tuples in the write set only, which have acquired the lock before the commit timestamp was calculated and will not be modified.
A data write module 14 for writing a write set to the database store where all tuples pass validation. For each tuple in the write set, the value of the tuple in the store is updated, the write timestamp and the read timestamp in the store are updated to the commit timestamp of the current transaction, and all locks acquired at the timestamp calculation module 12 are released, so that the modified tuple is visible to other transactions.
Claims (3)
1. The multi-version concurrency control method based on virtual global clock synchronization is characterized by comprising the following steps of:
the method comprises the following steps: reading data;
copying the accessed tuple according to the current transaction requirement, and reading the data value of the related tuple and the current read-write timestamp in an atomic mode;
step two: calculating and verifying a version timestamp;
step three: writing the values of the tuples in the writing set into the positions of tuple storage in the database, and updating the read time stamp and the write time stamp of the related tuples;
the first step comprises the following steps:
step 101: applying locking by affairs;
step 102: maintaining a separate read set and write set for the current transaction, wherein the encoding format of each entry in the read set or the write set is { tuple, data, write timestamp, read timestamp }, wherein the tuple is a pointer pointing to the tuple in the database, the data is a data value stored in the tuple of the current version, and the write timestamp and the read timestamp are respectively a write timestamp and a read timestamp in the duplicated tuple;
step 103: traversing the tuples accessed by the transaction in sequence;
step 104: copying the accessed tuple entities to a read set, wherein the read set is only visible to the current transaction;
step 105: storing a pointer pointing to a tuple in the tuple of the reading set according to the request type, storing the value of the read tuple in the data of the reading set, storing the write timestamp of the read tuple in the write timestamp of the reading set, and storing the read timestamp of the read tuple in the read timestamp of the reading set;
step 106: optionally, writing the tuple value to be modified into a write set, where the write set is visible only to the current transaction;
step 107: optionally, the pointer pointing to the tuple is stored in the write-in set according to the request type, a new value of the modified tuple is stored in the data of the write-in set, a write timestamp of the read tuple is stored in the write timestamp of the write-in set, and a read timestamp of the read tuple is stored in the read timestamp of the write-in set;
step 108: loading the recorded data values using an atomic approach;
step 109: loading and recording a read-write timestamp by using an atomic mode;
the second step comprises the following steps:
step 201: locking all tuples in the transaction write set in order;
step 202: traversing each entry in the read set and the write set, and calculating the commit timestamp of the current transaction;
step 203: for tuples only in the read set but not in the write set, submitting the maximum value of the write timestamp in the timestamp read set and the current computation timestamp;
step 204: for tuples in the transaction write-in set, the commit timestamp takes the maximum value of the read timestamp of the current tuple plus one and the current computation timestamp;
step 205: verifying the tuples in the transaction reading set one by one;
step 206: if the commit timestamp of the transaction is less than or equal to the read timestamp of the read set tuple, the tuple version read by the transaction is valid at the commit timestamp without further operation;
step 207: if the read timestamp of the tuple in the read set is smaller than the commit timestamp, and if the read timestamp in the read set is different from the latest write timestamp, the read timestamp of the local version cannot be extended, and then the current transaction rollback is realized in an atomic mode;
step 208: if the write timestamp in the read set is matched with the actual write timestamp in the current tuple, the latest read timestamp of the tuple is less than or equal to the commit timestamp of the transaction, but the tuple is locked by another transaction and is not in the write set of the transaction, and the rollback of the current transaction is realized in an atomic mode;
step 209: if the read timestamp is extensible, or if the version is already valid in the commit timestamp, atomically implementing the extension of the read timestamp of the tuple to the commit timestamp of the transaction;
step 210: all tuples accessed by the transaction are validated and the transaction enters the write phase.
2. The virtual global clock synchronization-based multi-version concurrency control method according to claim 1, wherein the third step comprises the following steps:
step 301: traversing each tuple in the transaction write set;
step 302: writing the value written into the concentrated write tuple into the position of the tuple pointer in the database;
step 303: the system sets the write timestamp and the read timestamp thereof as a commit timestamp, indicating the new version;
step 304: all locks acquired during the validation phase are released, making the changes visible to all other transactions.
3. A multi-version concurrency control system based on virtual global clock synchronization is characterized in that: the device comprises the following modules,
the data reading module is used for reading and copying all tuples involved by the current transaction;
the time stamp calculating module is used for calculating the submission time stamp of the current transaction according to the read time stamp and the write time stamp of the tuple currently involved;
the timestamp verifying module is used for verifying whether the calculated timestamp is valid;
the data writing module is used for writing the time stamp and the modified tuple which are successfully verified into the database storage;
the data reading module is used for reading and copying all tuples involved by the current transaction from the storage, maintaining a single reading set and a single writing set for the current transaction, copying the accessed tuples in the storage to the reading set and storing the modified tuples in the writing set, wherein the reading set and the writing set are only visible for the current transaction;
the timestamp calculation module is used for calculating the commit timestamp of the current transaction according to the read set and the write set generated in the data reading module, locking the tuple in the write set, preventing other transactions from updating the tuple at the same time, and ensuring that no deadlock exists when other transactions are committed at the same time by using a fixed locking sequence;
when the time stamp calculation module calculates the commit time stamp of the current transaction, the commit time stamp is not less than the write time stamp of the tuple in the read set and not less than the read time stamp of the tuple in the write set;
the time stamp verifying module is used for verifying whether the submission time stamp obtained by the time stamp calculating module is valid or not;
if the submission timestamp is less than or equal to the reading timestamp of the tuple in the reading set, the tuple version read by the transaction is valid at the position of the submission timestamp;
if the commit timestamp is larger than the read timestamp in the read set, the tuple version read in the read set is invalid, if no other transaction modifies the tuple, the read timestamp of the tuple is modified into the commit timestamp, otherwise, the current transaction is terminated;
there is no need to verify tuples in the write set that have acquired the lock before computing the commit timestamp, and that are not modified;
the data writing module is used for verifying all the tuples through the time stamps and writing the writing set of the tuples into the database storage;
for each tuple in the write set, the tuple is updated, the write timestamp and the read timestamp in the store are updated to the commit timestamp of the current transaction, and all locks acquired at the timestamp calculation module are released, making the modified tuple visible to other transactions.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202010409995.2A CN111459920B (en) | 2020-05-15 | 2020-05-15 | Multi-version concurrency control method and system based on virtual global clock synchronization |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202010409995.2A CN111459920B (en) | 2020-05-15 | 2020-05-15 | Multi-version concurrency control method and system based on virtual global clock synchronization |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN111459920A CN111459920A (en) | 2020-07-28 |
| CN111459920B true CN111459920B (en) | 2021-01-15 |
Family
ID=71680342
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202010409995.2A Active CN111459920B (en) | 2020-05-15 | 2020-05-15 | Multi-version concurrency control method and system based on virtual global clock synchronization |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN111459920B (en) |
Families Citing this family (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN112231070B (en) * | 2020-10-15 | 2024-08-30 | 北京金山云网络技术有限公司 | Data writing and reading method, device and server |
| CN112597254B (en) * | 2020-12-07 | 2023-02-03 | 中国科学院计算技术研究所 | An Online Transactional Database System Oriented to Hybrid DRAM-NVM Main Memory |
| CN112463311B (en) | 2021-01-28 | 2021-06-08 | 腾讯科技（深圳）有限公司 | Transaction processing method and device, computer equipment and storage medium |
| CN112800060B (en) * | 2021-01-28 | 2024-06-28 | 百果园技术(新加坡)有限公司 | Data processing method, data processing device, computer readable storage medium and electronic equipment |
| CN112966047B (en) * | 2021-03-05 | 2023-01-13 | 上海沄熹科技有限公司 | Method for realizing table copying function based on distributed database |
| CN115454656B (en) * | 2022-08-09 | 2025-06-27 | 阿里云计算有限公司 | A transaction processing method, device and storage medium |
Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6927615B2 (en) * | 2003-06-05 | 2005-08-09 | International Business Machines Corporation | Low skew, power efficient local clock signal generation system |
| CN103744936A (en) * | 2013-12-31 | 2014-04-23 | 华为技术有限公司 | Multi-version concurrency control method in database and database system |
| CN108228698A (en) * | 2016-12-09 | 2018-06-29 | 谷歌有限责任公司 | High-throughput algorithm for multi-version concurrency control with globally synchronized time |
| CN110502525A (en) * | 2019-08-16 | 2019-11-26 | 华东师范大学 | An Optimistic Concurrency Control Method for Mixed Workloads |
| CN110955672A (en) * | 2019-11-25 | 2020-04-03 | 上海交通大学 | Multi-version support method and system for optimistic concurrency control |
-
2020
- 2020-05-15 CN CN202010409995.2A patent/CN111459920B/en active Active
Patent Citations (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6927615B2 (en) * | 2003-06-05 | 2005-08-09 | International Business Machines Corporation | Low skew, power efficient local clock signal generation system |
| CN103744936A (en) * | 2013-12-31 | 2014-04-23 | 华为技术有限公司 | Multi-version concurrency control method in database and database system |
| CN108228698A (en) * | 2016-12-09 | 2018-06-29 | 谷歌有限责任公司 | High-throughput algorithm for multi-version concurrency control with globally synchronized time |
| CN110502525A (en) * | 2019-08-16 | 2019-11-26 | 华东师范大学 | An Optimistic Concurrency Control Method for Mixed Workloads |
| CN110955672A (en) * | 2019-11-25 | 2020-04-03 | 上海交通大学 | Multi-version support method and system for optimistic concurrency control |
Also Published As
| Publication number | Publication date |
|---|---|
| CN111459920A (en) | 2020-07-28 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN111459920B (en) | Multi-version concurrency control method and system based on virtual global clock synchronization | |
| US9411635B2 (en) | Parallel nested transactions in transactional memory | |
| US11386065B2 (en) | Database concurrency control through hash-bucket latching | |
| Faleiro et al. | Rethinking serializable multiversion concurrency control | |
| Wang et al. | Mostly-optimistic concurrency control for highly contended dynamic workloads on a thousand cores | |
| US11321299B2 (en) | Scalable conflict detection in transaction management | |
| US7962456B2 (en) | Parallel nested transactions in transactional memory | |
| US7840530B2 (en) | Parallel nested transactions in transactional memory | |
| US9396227B2 (en) | Controlled lock violation for data transactions | |
| US8595446B2 (en) | System and method for performing dynamic mixed mode read validation in a software transactional memory | |
| Wu et al. | Transaction healing: Scaling optimistic concurrency control on multicores | |
| US8108627B2 (en) | Array comparison and swap operations | |
| CN112231070A (en) | Data writing and reading method and device and server | |
| Durner et al. | No false negatives: Accepting all useful schedules in a fast serializable many-core system | |
| CN110520845B (en) | Method and system for updating hardware transactional memory (HTM) user abort metadata | |
| Dong et al. | Fine-grained re-execution for efficient batched commit of distributed transactions | |
| US7904668B2 (en) | Optimistic semi-static transactional memory implementations | |
| CN115629822B (en) | Concurrent transaction processing method and system based on multi-core processor | |
| CN110546609B (en) | Method and system for hardware transactional memory (HTM) to assist database transactions | |
| Wang et al. | Dodo: A scalable optimistic deterministic concurrency control protocol | |
| Li et al. | Practical Deterministic Transaction Processing with Low-cost Re-execution | |
| Harris et al. | Software transactional memory | |
| Braga et al. | Towards Adaptive Transactional Consistency for Georeplicated Datastores | |
| Wang et al. | Mostly-Optimistic Concurrency Control for Highly Contended Dynamic Workloads on a Thousand Cores (Extended Version) | |
| Cai et al. | Concurrency Control and Recovery in OLTP Systems: High Scalability and Availability |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |