OCTP. An optimistic transactional cache protocol with low abort rates

Since the early nineties transactional cache protocols have been
intensively studied in the context of client-server database
systems.
Research has developed a variety of
protocols and compared different aspects of their quality.

In this paper, we present a new transactional cache protocol, called
"Optimistic Caching Timestamp Protocol" (OCTP). OCTP is a pure
optimistic
protocol and represents a strong improvement over OCC - a classical
optimistic transactional cache protocol. OCC is known to have
very low
message overhead
but suffers from high transaction abort rates. In contrast, OCTP's
message overhead is the same as that of OCC but its abort rates are
considerably
lower. OCTP does not require locks to coordinate concurrent
transactions but
uses a
backward validating timestamp-based approach instead. As opposed
to all
other known transactional cache protocols, it can allow
transactions to
commit which have read stale cached data elements while
still asserting serializability. Its computational complexity is
moderate
and in particular, it does apply a potentially costly
serializability graph
test.
We also present an extension
... mehrof OCTP called "Semi-Optimistic Caching Timestamp Procotol"
(SOCTP), which
reduces abort
rates further. In certain cases, SOCTP efficiently uses locks to
prevent
transaction aborts.

This paper explains the concepts behind OCTP and proves its
correctness
using a
multiversion transaction formalism. It sketches an efficient
implementation
of OCTP and
compares OCTP as well as SOCTP against two leading conventional
protocols,
namely OCC and CBR.
Simulation experiments show that both SOCTP and OCTP outperform
OCC and CBR
given that
the network represents the bottleneck of a related database
system.