\chapter{Related Work}
\label{cha:related-work}

Many different forms of caching and replication have been proposed to
improve the throughput of high-performance web applications.  Since
there are so many such systems (both research and practical) to make a
comprehensive list impractical, this section discusses some of the
systems most closely related to \txcache.

We discuss two broad classes of related systems: application-level
caches and cache management systems for them
(\autoref{sec:related-work:app}), and database-level caches and
replication systems (\autoref{sec:related-work:db}). We also discuss
other systems that have proposed using multiversion storage and
relaxing freshness guarantees (\autoref{sec:related-work:freshness}).

\section{Application-Level Caching}
\label{sec:related-work:app}

Applying caching at the application layer is an appealing option
because it can improve performance of both the application servers and
the database.

\subsection{Web Caches}

Dynamic web caches operate at the highest layer, storing entire web
pages produced by the application. Typically, they require cached
pages to be regenerated in entirety when any content changes. Such
caches have been widely used since the Web became popular (when
content was mostly static) and remain in common use today. % Two
% examples of popular open-source whole-page caches are
% Squid~\cite{squid} and Varnish~\cite{varnish}.

When used for dynamic content, caches need to invalidate pages when
the underlying data changes. Typically, this is done in one of three
ways. First, timeouts can be used to expire cached data
periodically. Second, the cache can require the application to
explicitly invalidate pages when they are
modified~\cite{yu99:_scalab_web_cache_consis_archit}. Finally, the
system can track data dependencies to identify which objects need to
be invalidated when the underlying database is modified. Challenger
et~al.\cite{challenger04:_effic_servin_dynam_data_highl,
  challenger99:_scalab_system_for_consis_cachin} describe a web cache
that models the dependencies between cacheable objects and underlying
data objects as a graph; this system requires the application
developer to provide this object dependency
graph. Cachuma~\cite{zhu01:_class_based_cache_manag_for} groups
dynamic pages into classes by their URL, and requires the developer to
specify data dependencies for each class.  \txcache also uses
invalidations, but integrates with the database to automatically
identify dependencies.

As we noted in the introduction, full-page caching is becoming less
appealing to application developers as more of the web becomes
personalized and dynamic. When a different version of a page is served
to each user, caching them has little value.

\subsection{Application Data Caches}

As a consequence of increased personalization and dynamic content, web
developers are increasingly turning to application-level data
caches. These caches allow the application to choose what to store,
including query results, arbitrary application data (such as Java or
.NET objects), and fragments of or whole web pages.  \txcache falls
into this category, as do many existing systems.

We have already discussed \memcached~\cite{memcached}, which provides
the abstraction of a distributed hash table into which the application
can store arbitrary binary objects using a
\command{get}/\command{put}/\command{delete} interface. The hash-table
interface, where objects are identified by application-specified keys,
is a fairly standard one among other caches, though they often differ
in terms of what types of objects they can store. Other
application-level caches often integrate into a specific language
runtime, \eg caches that cache
Java~\cite{jboss,ehcache,bakalova04:_websp_dynam_cache} or
.NET~\cite{sampathkumar09:_introd_cachin_window_server_appfab_beta,ncache}
objects. Redis~\cite{redis} (which can be used either as a cache or as
a persistent store) can cache a variety of data structures such as
strings, lists, and sets, and provides operations to manipulate them
such as set intersections and unions. In all cases, the hash-table
interface requires application developers to choose keys and correctly
invalidate objects, which we argued can be a source of unnecessary
complexity and application bugs.

Most application object caches have no notion of transactions, so they
cannot ensure even that two accesses to the cache return consistent
values. Some caches do support transactions within the cache. JBoss
Cache~\cite{jboss}, for example, can use either locking or optimistic
concurrency control to allow transactions to update multiple cached
objects atomically. Windows Server
AppFabric~\cite{sampathkumar09:_introd_cachin_window_server_appfab_beta}
(formerly known as Velocity) provides locking functions that can be
used to implement similar functionality. Other caches provide
single-object atomic operations; for example, \memcached has a
compare-and-set operation that acts on a single key. However, even the
caches that support transactions differ from \txcache in that they
only support atomic operations \emph{within} the cache, whereas
\txcache provides transactions that operate across both the cache and
storage layer.

Some caches provide support for replicated data~\cite{ncache,
  sampathkumar09:_introd_cachin_window_server_appfab_beta,jboss}. Though
replication is a useful technique for ensuring the availability of
data despite node failures, this usually isn't the reason that these
systems support it. Rather, replication is used for performance: making
multiple copies of frequently accessed objects allows multiple servers
(possibly located in different data centers) to handle requests for
that object. This technique is suitable for objects that are accessed
frequently but infrequently modified. Our cache does not use
replication, but it could easily be extended to do so, as discussed in
\autoref{sec:programming-model:implementation:cache}.

We noted in \autoref{sec:consistency-model:relaxing-freshness} that it
is impossible to guarantee that the cache always reflects the latest
state of the backing store unless using an atomic commitment protocol
between the cache and the storage layer, which would be prohibitively
expensive. Ehcache~\cite{ehcache}, a Java object cache, does allow the
cache to participate in a two-phase commit protocol, allowing the
cache to be updated atomically with the database. However, this is not
intended to ensure serializability, as this cache supports only the
weaker \command{read committed} isolation level. It is instead
intended for durability (the cache stores data on disk, and therefore
can recover from crashes).

The interface of these application-level caches has some similarity to
distributed hash tables (DHTs) from peer-to-peer systems
research~\cite{stoica03:_chord, rowstron01:_pastr, zhao04:_tapes,
  ratnasamy01:_scalab_conten_addres_networ}. Indeed, some similar
techniques have been used in their implementation, such as the use of
consistent hashing~\cite{karger97:_consis_hashin_and_random_trees} for
data partitioning. However, peer-to-peer DHTs are designed to scale to
millions of nodes and use sophisticated routing protocols to identify
the node responsible for storing a particular object without full
knowledge of the system membership. Our cache assumes that the system
is small enough that each node can maintain the entire system
membership, as in the OneHop
DHT~\cite{gupta04:_effic_routin_for_peer_to_peer_overl}. DHTs are also
typically intended for persistent storage, so must address issues of
data
durability~\cite{sit06:_proac_replic_data_durab,
  chun06:_effic_replic_maint_for_distr_storag_system} that our cache
can ignore.

\subsection{Cache Management}

Several others have observed the problems that explicit cache
management poses for developers of applications that use
application-level caching, and proposed systems to address these
challenges. Typically, these systems take the form of a library that
mediates interactions with an existing application-layer cache such as
\memcached.

One approach is to have the application (or a library in the
application) update or invalidate the cache. For example,
Cache-Money~\cite{cache_money} is a library for the Ruby on Rails
object-relational mapping system that implements a write-through
cache: the library updates the cache before making any changes to the
database. This library restricts the application to caching only a
specific set of objects, corresponding to database tuples and indexes;
it does not allow arbitrary application computations to be cached, or
even more sophisticated database queries such as joins.
Wasik~\cite{wasik07:_manag_cache_consis_scale_dynam_web_system}
proposed a system for managing consistency in an application that uses
\memcached. This system analyzes the application code and rewrites it
to insert the appropriate invalidations for each database
modification; however, the analysis requires programmers to indicate
what data in the database each cached object depends on. Because this
class of solutions modifies the application to provide dependencies,
it assumes that only one application modifies the database. This can
be a serious restriction in environments where multiple applications
share a database, as changes
made by other applications will not trigger the necessary cache
invalidations. In practice, even systems where a database is used
primarily to support a single application may still have other tools
modifying the database, \eg to support bulk-loading new data
or to allow administrators to manually correct data errors.

A second approach is to involve the database, using triggers to
invalidate cached objects after each update. This approach avoids the
aforementioned problem with multi-application databases, as \emph{any}
modification will invoke the trigger. However, the database must be
told which triggers to create and which cached objects they should
invalidate. Application developers can indicate these dependencies
manually~\cite{hagander10:_data}, though this approach could be
error-prone.  CacheGenie~\cite{gupta11:_trigg_based_middl_cache_orms,
  gupta10:_provid_cachin_abstr_web_applic} is a system that
automatically creates database triggers for cache invalidation. This
system integrates with an object-relational mapping framework (Django)
and allows caching application objects corresponding to a fixed set of
common query patterns.

Several of these cache management systems rely on object-relational
mapping (ORM) frameworks like Ruby on Rails, Django, or Java Entity
Beans~\cite{cache_money, gupta11:_trigg_based_middl_cache_orms,
  gupta10:_provid_cachin_abstr_web_applic,
  perez-sorrosal11:_elast_si_cache}.  These frameworks provide
persistent objects for an application (written in an object-oriented
language) by mapping the objects to a corresponding schema in a
relational database, and automatically generating queries to access
it. Caching systems for these frameworks typically cache fixed
categories of objects defined by the ORM framework; often, these
objects have a one-to-one correspondence with database
tuples. \txcache uses a more general programming model, caching the
results of calls to cacheable functions. This allows \txcache to cache
arbitrary application computations, unlike ORM-based caches. However,
because these ORM-based caches have well-defined classes of cached
objects, they can update cached objects in place rather than
invalidating and recomputing them, as discussed in
\autoref{sec:programming-model:discussion:limitations}.

Most of the systems described above do not provide transaction
isolation, \ie they do not ensure the consistency of cached data read
during a transaction. One exception is
SI-Cache~\cite{perez-sorrosal11:_elast_si_cache}, which provides
snapshot isolation in a cache of Java Entity
Beans.
%\drkp{say something about the differences between their cache
%  and ours}.
CacheGenie~\cite{gupta11:_trigg_based_middl_cache_orms} also
describes an extension that provides serializability by using strict
two-phase locking in both the cache and the database.


\section{Database Caching and Replication}
\label{sec:related-work:db}


Another popular approach to improving web application performance is
to deploy a caching or replication system within the database
layer, or between the database and the application. These systems
address only database performance; unlike application-level caches,
they offer no benefit for application server load. However, they
require no modifications to the application.

Query caches are one way to address load in the database layer. These
add an additional layer in front of the database that caches the
results of recent queries. As a simple example, the MySQL database
itself includes a query cache that can avoid the need to process
queries that are character-for-character identical to previous ones;
it invalidates a cache entry whenever one of the relations it depended
on is modified. A more sophisticated example is the ABR query
cache~\cite{degenaro00:_middl_system_which_intel_caches_query_resul}
which uses a dependency graph to determine which values need to be
invalidated. Ferdinand~\cite{garrod08:_scalab_query_resul_cachin_for_web_applic}
is a query cache that distributes invalidations using a
publish-subscribe multicast system; such a strategy could be applied
to improve the performance of \txcache.  None of these query caches
support serializablility for transactions that make multiple queries.


Middle-tier caches also sit in front of the database, but perform more
complex processing. DBProxy~\cite{amiri03:_dbprox}, for example,
caches the results to previous queries, like a query cache. However,
it incorporates a query processor that allows it to also answer other
queries that can be computed from a subset of the cached results.
DBCache~\cite{bornhoevd04:_adapt_datab_cachin_dbcac} and
MTCache~\cite{mtcache} both run a full DBMS at the cache node,
populated with full or partial tables from the underlying database;
the cache determines which queries can be executed locally and which
must be executed by the backing database. These systems also do not
attempt to guarantee serializability for transactions that make
multiple queries.

Materialized views are a form of in-database caching that creates a
view table containing the result of a query over one or more base
tables, and updates it as the base tables change. Most
work on materialized views seeks to incrementally update the view
rather than recompute it in its
entirety~\cite{gupta93:_maint_views_increm}. This requires placing
restrictions on view definitions, \eg{requiring them to be expressed
  in the select-project-join algebra}. \txcache's application-level
functions, in addition to being computed outside the database, can
include arbitrary computation, making incremental updates
infeasible. Instead, it uses invalidations, which are easier for
the database to
compute~\cite{candan02:_view_inval_dynam_conten_cachin_multit_archit}.

% Some replication systems guarantee transactional consistency by using
% group communication to execute
% queries~\cite{elnikety05:_datab_replic_using_gener_snaps_isolat,
%   kemme00:_new_approac_to_devel_and}, which can be difficult to scale
% to large numbers of
% replicas~\cite{gray96:_danger_of_replic_and_solut}. Others offer
% weaker guarantees (eventual consistency)~\cite{downing90:_oscar,
%   petersen97:_flexib_updat_propag_for_weakl_consis_replic}, which can
% be difficult to reason about and use correctly. Still others require
% the developer to know the access pattern
% beforehand~\cite{amza03:_distr} or statically partition the
% data~\cite{cecchet04:_c_jdbc}.

A different approach to improving database performance is to replicate
the database. Of the many replication approaches that exist, we focus
on those that provide transactional consistency semantics. (Others
offer weaker guarantees, such as eventual
consistency~\cite{downing90:_oscar,
  petersen97:_flexib_updat_propag_for_weakl_consis_replic}.)  Most
replication schemes used in practice take a primary copy approach,
where all modifications are processed at a master and shipped to slave
replicas. This replication can be performed synchronously to improve
durability, but is often performed asynchronously for performance
reasons. One way to do implement primary-copy replication is to
transfer a copy of the master database's write-ahead log records to
the slaves and replay them there; this ``log shipping'' approach is
widely used in commercial products. Another way is to use a middleware
component that executes all update transactions on each replica in the
same order~\cite{cecchet04:_c_jdbc,
  vandiver07:_toler_byzan_fault_in_datab}.  In either case, each
replica then maintains a complete, if slightly stale, copy of the
primary database.


Several systems defer update processing to improve performance for
applications that can tolerate limited amounts of staleness. In
FAS~\cite{roehm02:_fas}, clients send their queries to a ``scheduler''
proxy. This scheduler executes read/write transactions on the primary,
then lazily propagates them to the other replicas. In the meantime, it
keeps track of how far each replica's state lags behind the primary,
and routes read-only transactions to an appropriate replica based on
an application-specified staleness
limit. Ganymed~\cite{plattner04:_ganym} takes a similar approach, but
relies on each replica database to provide snapshot isolation so that
slave replicas can process read-only transactions from clients
concurrently with updates that are being propagated from the master.

% These protocols assume that each
% replica is a single, complete snapshot of the database, making them
% infeasible for use in an application object cache setting where it is
% not possible to maintain a copy of every object that could be
% computed. In contrast, \txcache's protocol allows it to ensure
% consistency even though its cache contains cached objects that were
% generated at different times.


\subsection{Caching vs. Replication}

Caching and replication are closely related subjects. Like \txcache,
both FAS and Ganymed use the idea of allowing read-only transactions
to see slightly stale data in order to improve their
performance. However, \txcache's design differs significantly from
these two systems. One might wonder, then, if techniques like those
used in FAS and Ganymed could be applied in \txcache's context of
application-level caching.

These database replication systems take a \emph{proactive} approach:
after an update to the master database, they update the other
replicas' state. Such an approach is well-suited for data
replication. After processing a read/write transaction, the set of
objects that need to be updated on each replica is easy to identify:
it is exactly the same set of tuples modified on the master.  This
approach can be applied to application-level caching where each
application object is a representation of a particular database
tuple~\cite{roehm07:_fresh_j2ee}.
However, the approach isn't suitable for \txcache's cache of arbitrary
application computations. The set of objects that would need to be
updated is large (there are many possible cacheable function calls),
and recomputing them is expensive.

Therefore, \txcache must take a \emph{reactive} approach: it
opportunistically caches the results of previous computations. Because
these objects were computed at different times, \txcache uses validity
intervals to ensure that the application sees a
transactionally-consistent view of the system, even while reading
objects that were not generated at the same time. This mechanism isn't
necessary in database replication systems that proactively update the
replicas, as each replica has a complete, consistent copy of the
entire database at any moment.

\section{Relaxing Freshness}
\label{sec:related-work:freshness}


\txcache builds on a long history of previous work on multiversion
concurrency control. Many different approaches to using multiple
versions to ensure isolation
exist~\cite{reed78:_namin_and_synch_in_decen_comput_system,
  adya95:_effic_optim_concur_contr_using,
  berenson95:_critiq_of_ansi_sql_isolat_level,
  bernstein81:_concur_contr_in_distr_datab_system}. The most prevalent
such approach in production systems today is snapshot
isolation~\cite{berenson95:_critiq_of_ansi_sql_isolat_level}.  In
snapshot isolation, all data read by a transaction comes from a
snapshot of the database taken at the time the transaction started.
Snapshot isolation permits some ``write-skew'' anomalies that would
not occur in serializable executions. \txcache provides the same
guarantee as snapshot isolation: within a transaction, applications
see state corresponding to a snapshot of the database, even though
some of it may come from the cache. However, \txcache does not
introduce write skew anomalies into applications, because it
does not use the cache for read/write transactions.

Unlike snapshot isolation, where transactions use a snapshot current
as of the time they started, \txcache can assign transactions a
snapshot slightly earlier than their actual start time. A similar
technique, called Generalized Snapshot
Isolation~\cite{elnikety05:_datab_replic_using_gener_snaps_isolat} was
proposed for use in a replicated database system. Liskov and Rodrigues~\cite{liskov04:_trans_file_system_can_be_fast}
also proposed running transactions on past snapshots to improve the
performance of a distributed transactional file system. Our work is
inspired by this proposal. The proposed file system uses a backing
store similar to the block store we described in
\autoref{cha:storage-layer}. Because our system supports caching
application-level objects derived from database queries, rather than
file system blocks, it requires new mechanisms such
as dependency tracking (invalidation tags) and validity interval
computation mechanisms suitable for use in a relational database.  The
transactional file system also assumes an environment where each
client has its own local cache; \txcache has a different model
consisting of a single shared distributed cache.

Bernstein~et~al.\ defined a notion of relaxed-currency
serializability~\cite{bernstein06:_relax_curren_serial_for_middl} that
encompasses \txcache's use of stale data, and relies on a similar notion
of validity intervals. They assume a model similar to that of the
replicated database systems previously discussed, in which validity
intervals are more readily available. Our contributions include a
technique for easily generating validity intervals using existing
database concurrency control mechanisms, and using them to generate
validity information for application-level objects.

As we argued in \autoref{sec:consistency-model:relaxing-freshness}, assigning
transactions an earlier timestamp is safe as long as it does not
permit any causality anomalies. Other systems also allow operations to
be reordered when there are no causal dependencies. Lamport introduced
the happens-before relation, wherein transactions are considered
concurrent if they do not depend on each
other~\cite{lamport78:_time_clock_and_order_of}. This idea was notably
used in the ISIS
system~\cite{birman87:_exploit_virtual_synch_in_distr_system}, whose
virtual synchrony communication model enforced ordering constraints
only on causally-dependent messages.

%\section{Invalidations}


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

%  LocalWords:  cacheable Cachuma invalidations personalization ABR
%  LocalWords:  runtime AppFabric Ehcache serializablility multicast
%  LocalWords:  MySQL transactionally serializable serializability