Browse Prior Art Database

Distributed Optimistic Concurrency Control Based On Time-Stamp History Certification

IP.com Disclosure Number: IPCOM000120307D
Original Publication Date: 1991-Apr-01
Included in the Prior Art Database: 2005-Apr-02
Document File: 4 page(s) / 171K

Publishing Venue

IBM

Related People

Dias, DM: AUTHOR [+2]

Abstract

The Concurrency Control (CC) method can drastically affect the performance of Transaction Processing (TP) systems. In the Optimistic CC (OCC) method, transactions run without waiting to ensure non-conflicting access to data, and transactions are aborted if conflicting access is determined. A certification method is used at transaction commit time to determine if a transaction should be aborted or can be committed. Committing transaction may also cause running transactions to abort or be marked for abort. Due to aborts, OCC schemes may consume more resources and, therefore, may be vulnerable to resource contention, but they typically provide more throughput when resource is unlimited and data contention is the issue.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 37% of the total text.

Distributed Optimistic Concurrency Control Based On Time-Stamp History
Certification

      The Concurrency Control (CC) method can drastically
affect the performance of Transaction Processing (TP) systems.  In
the Optimistic CC (OCC) method, transactions run without waiting to
ensure non-conflicting access to data, and transactions are aborted
if conflicting access is determined.  A certification method is used
at transaction commit time to determine if a transaction should be
aborted or can be committed.  Committing transaction may also cause
running transactions to abort or be marked for abort.  Due to aborts,
OCC schemes may consume more resources and, therefore, may be
vulnerable to resource contention, but they typically provide more
throughput when resource is unlimited and data contention is the
issue.  In (1), an improved time-stamp based certification scheme is
described that uses time-stamp history information to significantly
reduce transaction aborts due to read-write conflicts in a
centralized complex under a single CC manager.  This is referred to
as OCC with adaptive time-stamp certification. In this article, we
generalize the adaptive scheme to a distributed environment where
there are multiple processing nodes interconnected by some network
and the databases are partially replicated over the multiple nodes.
We assume that among the multiple sites with a copy of a database,
one of them is designated as the master site.

      The certification protocol is as follows.  At the commit time,
the local CC manager, referred to as the coordinator, assigns a
globally unique time-stamp to transaction X.  It then communicates
with the master sites of data items accessed by transaction X to find
out whether the transaction can be committed on the time stamp or an
alternative time stamp to be determined, or the transaction has to be
aborted.  The CC manager at each participating master site checks the
transaction time stamp against the read or write time stamp of the
data items accessed as defined below.  We maintain a read time stamp
(Tr) and write time stamp (Tw) for each data item.  The read time
stamp is the time stamp of the youngest (i.e., latest in time)
committed transaction which read the data.  The write time stamp is
the time stamp of the youngest committed transaction which updated
the data.  We also maintain k update history time stamps (T1w,....,
Tkw) for the data, with T1w as the oldest update and Tkw as the
latest update, so that Tw = Tkw .  That is the time stamp of the
last k transactions updating the data item.  A transaction views each
data item as a (name, version) pair. For each data item read, we
track the Tw of the data as its version.  Assume that transaction X
is given a time stamp Ts .  For each data item Dir read, i=1,...,m,
the version read is checked with the current Tw of the data item.  If
all match, we further check whether Ts is larger than the read time
stamp of each updated it...