\svnInfo $Id$

Current work involves extending the base system described in the
preceding sections. This section describes several planned extensions.


\subsection{Read/Write Transaction Support}
\label{sec:future:read/write}

\txcache currently supports caching only within read-only
transactions. It would be clearly desirable to allow read/write
transactions to also make use of cached objects. We would like to
extend our system to support this, which presents two challenges:

\begin{itemize}
\item during a read/write transaction, operations expect to see the
  results of modifications made earlier in the same transaction, and
  any cached objects used should reflect this. At the same time, other
  transactions must not see the effects of a read/write transaction
  until it commits.
\item read/write transactions that see stale data may perform
  modifications based on that stale data, and thus cause anomalies
  similar to those in snapshot isolation. We will investigate whether
  these anomalies are problematic and whether they can be mitigated.
\end{itemize}

\subsection{Serializability and Snapshot Isolation}
\label{sec:future:ssi}

As described in Section~\ref{sec:model:consistency}, \txcache provides
the same transactional consistency guarantees as the underlying
database, typically either serializability or snapshot
isolation. Serializability is a stronger criterion and provides more
desirable semantics: users do not need to concern themselves with
anomalies between concurrent transactions. However, it is easier to
build the database support for \txcache atop a snapshot isolation
database: the database modifications in
Section~\ref{sec:database:multiversion} require precisely the same
multiversion concurrency techniques used to support snapshot
isolation.

Serializable Snapshot Isolation (SSI) is a new technique for
modifying a snapshot isolation database to provide
serializability~\cite{cahill08:_serial_isolat_snaps_datab}. Rather
than using locks to force transactions to wait, it uses a predicate
lock manager to monitor each transaction's read and write dependencies
and aborts transactions that could potentially become part of a cycle
in the serialization graph.  It is well suited for \txcache because it
provides serializability yet reuses existing snapshot isolation
mechanisms, allowing them to be used to support \txcache's needs.

We are developing an implementation of SSI for PostgreSQL, the first
such implementation in a production DBMS. To make it practical for use
with limited memory, it incorporates new aggressive optimizations for
replacing detailed information about committed transactions with
summary information. We also introduce new optimizations for read-only
transactions.

This work is particularly relevant to \txcache because, in addition to
providing a practical serializable database option, it provides a new
predicate lock infrastructure which will be used to implement the new
invalidation scheme described in Section~\ref{sec:future:repl}.

\subsection{Invalidations}
\label{sec:future:invalidations}

Automatic invalidations, where the database produces a notification
when a previous query result has changed, are a critical part of the
\txcache system. \txcache requires invalidations to keep validity data
in the cache up to date. Other systems can also benefit from an
automatic invalidation mechanism. For example, correctly invalidating
cache entries is equally important (and equally difficult) for
existing caches such as \memcached, and other applications may want to
recompute dependent computations (such as generated reports) when the
underlying data changes.

Sections~\ref{sec:cache:invalidations} and
\ref{sec:database:invalidations} describe our current scheme for
invalidations. This simple approach has some limitations. It does not
effectively support certain types of queries, such as index range
queries, which must be represented as overly-coarse
relation-granularity tags. It also generates invalidations for every
modification to the database, even those that affect no cached values,
and it distributes every invalidation to each cache node regardless of
whether it is useful to do so.

We propose a new invalidation mechanism based on \emph{revocable read
  locks} to address these problems. In this scheme, each access to the
database acquires an ``invalidation lock'' on every object it reads,
and produces an invalidation tag corresponding to the lock. Unlike
typical locks (but similar to the SIREAD locks in
\cite{cahill08:_serial_isolat_snaps_datab} and to callback
locks~\cite{lamb91:_objec}), these locks persist even
after the transaction that created them commits, and they do not block
conflicting accesses. Rather, if another transaction modifies an
object with an associated invalidation lock, that lock is removed and
an invalidation is generated.

This approach offers several benefits over the current one:

\begin{itemize}
\item it leverages existing database lock mechanisms to
  comprehensively track read dependencies. In particular, it can take
  advantage of techniques like next-key locking to handle range
  lookups~\cite{lomet93:_key_range_lockin_strat_improv_concur}.
\item both locks and invalidation tags are hierarchical; this allows
  multiple fine-granularity locks/tags to be converted to a single
  coarser-granularity one in order to reduce the number that must be
  tracked
\item changes that affect no cache items generate no invalidations,
  because no invalidation locks will be present
\item it may be possible to tag invalidation locks with information as
  to which cache nodes the invalidation should be distributed to,
  rather than broadcasting all invalidation messages
\end{itemize}

\subsection{Replicated and Partitioned Databases}
\label{sec:future:repl}

The system as describe above assumes that all data is stored in a
single database system. This assumption is overly limiting, as most
applications facing scalability challenges requiring application-level
caching also make heavy use of database replication and
partitioning. We would like to extend our system to support these
environments.

In the most common configuration for a replicated database system, one
server acts as the primary replica and processes all updates; the
results of the updates are sent to the other replicas, which process
only read-only transactions. When replication is done asynchronously,
the read-only slave replicas offer an older snapshot than the
master. Dealing with this ``replication lag'' poses a challenge for
application developers, because unexpectedly stale data may be
problematic.  \txcache's model of application-controlled staleness is
well suited for this environment. \txcache can ensure that requests
are directed to the master when they need data more fresh than is
available on the slaves. It can also correctly sequence queries, cache
inserts, and invalidations, which has been challenging for
applications using both caches and
replication~\cite{mediawiki-bugzilla}.

We would also like to support partitioned databases, where each server
holds only part of the data. Accesses to cached objects should reflect
a consistent view of the system, even when the object was derived from
data in multiple partitions. This will require extending the notion of
validity intervals to reflect the state of multiple database
partitions, possibly using version vectors or logical
clocks~\cite{lamport78:_time_clock_and_order_of}.



%%% Local Variables: 
%%% mode: latex
%%% TeX-PDF-mode: t
%%% TeX-master: "main.tex"
%%% End: 

% LocalWords:  serializability multiversion Invalidations invalidations
% LocalWords:  serializable