| 失效链接处理 |
|
内存中多版本并发控制的实证评价 PDF 下载
本站整理下载：
相关截图：
主要内容：
ion that each of them is executing alone on a dedicated system [9].
It ensures the atomicity and isolation guarantees of the DBMS.
There are several advantages of a multi-version system that are
relevant to modern database applications. Foremost is that it can
potentially allow for greater concurrency than a single-version sys-
tem. For example, a MVCC DBMS allows a transaction to read an
older version of an object at the same time that another transaction
updates that same object. This is important in that execute read-only
queries on the database at the same time that read-write transactions
continue to update it. If the DBMS never removes old versions,
then the system can also support “time-travel” operations that allow
an application to query a consistent snapshot of the database as it
existed at some point of time in the past [8].
The above benefits have made MVCC the most popular choice
for new DBMS implemented in recent years. Table 1 provides a
summary of the MVCC implementations from the last three decades.
But there are different ways to implement multi-versioning in a
DBMS that each creates additional computation and storage over-
head. These design decisions are also highly dependent on each
other. Thus, it is non-trivial to discern which ones are better than
others and why. This is especially true for in-memory DBMSs
where disk is no longer the main bottleneck.
In the following sections, we discuss the implementation issues
and performance trade-offs of these design decisions. We then
perform a comprehensive evaluation of them in Sect. 7. We note
that we only consider serializable transaction execution in this paper.
Although logging and recovery is another important aspect of a
DBMS’s architecture, we exclude it from our study because there is
nothing about it that is different from a single-version system and
in-memory DBMS logging is already covered elsewhere [33, 49].
2.2 DBMS Meta-Data
Regardless of its implementation, there is common meta-data that
a MVCC DBMS maintains for transactions and database tuples.
Transactions: The DBMS assigns a transaction T a unique,
monotonically increasing timestamp as its identifier (T id ) when
they first enter the system. The concurrency control protocols use
this identifier to mark the tuple versions that a transaction accesses.
Some protocols also use it for the serialization order of transactions.
Tuples: As shown in Fig. 1, each physical version contains four
meta-data fields in its header that the DBMS uses to coordinate
the execution of concurrent transactions (some of the concurrency
control protocols discussed in the next section include additional
fields). The txn-id field serves as the version’s write lock. Every
tuple has this field set to zero when the tuple is not write-locked.
MostDBMSsusea64-bit txn-id sothatitcanuseasinglecompare-
and-swap (CaS) instruction to atomically update the value. If a
transaction T with identifier T id wants to update a tuple A , then the
DBMS checks whether A ’s txn-id field is zero. If it is, then DBMS
will set the value of txn-id to T id using a CaS instruction [27, 44].
begin-ts columns
Content Header
txn-id end-ts … pointer
Figure 1: Tuple Format – The basic layout of a physical version of a tuple.
Any transaction that attempts to update A is aborted if this txn-id
field is neither zero or not equal to its T id . The next two meta-data
fields are the begin-ts and end-ts timestamps that represent the
lifetime of the tuple version. Both fields are initially set to zero. The
DBMS sets a tuple’s begin-ts to INF when the transaction deletes
it. The last meta-data field is the pointer that stores the address of
the neighboring (previous or next) version (if any).
3. CONCURRENCYCONTROLPROTOCOL
Every DBMS includes a concurrency control protocol that coor-
dinates the execution of concurrent transactions [11]. This protocol
determines (1) whether to allow a transaction to access or modify a
particular tuple version in the database at runtime, and (2) whether to
allow a transaction to commit its modifications. Although the funda-
mentals of these protocols remain unchanged since the 1980s, their
performance characteristics have changed drastically in a multi-core
and main-memory setting due to the absence of disk operations [42].
As such, there are newer high-performance variants that remove
locks/latches and centralized data structures, and are optimized for
byte-addressable storage.
In this section, we describe the four core concurrency control
protocols for MVCC DBMSs. We only consider protocols that use
tuple-level locking as this is sufficient to ensure serializable exe-
cution. We omit range queries because multi-versioning does not
bring any benefits to phantom prevention [17]. Existing approaches
to provide serializable transaction processing use either (1) addi-
tional latches in the index [35, 44] or (2) extra validation steps when
transactions commit [27].
3.1 Timestamp Ordering ( MVTO )
The MVTO algorithm from 1979 is considered to be the original
multi-version concurrency control protocol [38, 39]. The crux of
this approach is to use the transactions’ identifiers (T id ) to pre-
compute their serialization order. In addition to the fields described
in Sect. 2.2, the version headers also contain the identifier of the last
transaction that read it ( read-ts ). The DBMS aborts a transaction
that attempts to read or update a version whose write lock is held by
another transaction.
When transaction T invokes a read operation on logical tuple A ,
the DBMS searches for a physical version where T id is in between
the range of the begin-ts and end-ts fields. As shown in Fig. 2a,
T is allowed to read version A x if its write lock is not held by another
active transaction (i.e., value of txn-id is zero or equal to T id )
because MVTO never allows a transaction to read uncommitted
versions. Upon reading A x , the DBMS sets A x ’s read-ts field to T id
if its current value is less than T id . Otherwise, the transaction reads
an older version without updating this field.
|
| Java1234官方群25： | 
|
| Java1234官方群25： | 838462530 |
苏公网安备 32061202001004号
