Schemes for Snapshot Advancement for Multiversion Concurrency Control

Schemes for Snapshot Advancement for Multiversion Concurrency Control

       Multiversion concurrency control is the primary approach
to addressing the issue of interference between concurrent update
transactions and read-only queries (1).  By maintaining  multiple
versions of data objects, interference between them can be reduced or
eliminated: update transactions create a new version of an object
upon each update, while queries access an old, but consistent,
version (2,3).  However, the increases in storage overhead and
version-management complexity, including garbage collection, may
become significant (4,5,6,7).  Recently, a group of different schemes
have been proposed to address these problems by maintaining a finite
number of consistent database snapshots (8,9,10), called QS.

      In this article, a new class of schemes for snapshot
advancement for the multiversion concurrency control methods that
maintain M > 2 snapshots is developed.  In finite-snapshot
multiversioning, a finite number of logical versions for each page is
dynamically maintained.  From these versions, up to M consistent
database snapshots QS0, QS1,..., QSM-1, where QS0 is the oldest
snapshot and QSM-1 is the most recent one, can be derived for queries
to read, and the most up-to- date version of the database is
available for transactions to  access without lock contention from
queries.

      Each snapshot QSi consists of a time-stamp tqsi, a list QLi of
active queries accessing the snapshot, and the latest updates
committed since the  previous  snapshot. Arriving queries access the
most recent snapshot QSM-1, and join active query list QLM-1 .  When
a query completes, it is removed from the active query list of its
snapshot.  On the other hand, the updates committed after the most
recent snapshot are separately maintained for transactions to access.
Thus, transactions may access the latest data without lock contention
from queries.  These newly committed updates can become part of a new
snapshot after the last query accessing an existing snapshot
completes.  The old snapshot is discarded when a new one is taken,
and the process is referred to as snapshot advancement.

      Previous approaches always advance snapshots when the last
active query accessing an existing snapshot completes (10); these are
referred to as completion-triggered schemes. In completion-triggered
schemes, what if there were not active queries accessing QS1 before a
snapshot advancement? Since the new QL0 starts empty, there will be
no completions to trigger the next snapshot advance.  In other words,
the new QSo will never be discarded.  As a result, a
"system-scheduled" snapshot advance has to be inserted at time W in
the future.  However, the choice of W can have a profound impact on
the average time inter val between snapshots, which in turn
determines the average query obsolescence.  When query arrival rates
are low, system-scheduled advances dominate comp...