\chapter{Evaluation}
\label{cha:evaluation}

This chapter analyzes the effectiveness of \txcache using the \rubis
web application benchmark. The evaluation seeks to answer the
following questions:

\begin{itemize}
\item What changes are required to modify an existing web application to
  use \txcache? (\autoref{sec:eval:rubis}).
\item How much does caching improve the application's performance, and
  how does the cache size affect the benefit? (\autoref{sec:eval:size})
\item Does allowing transactions to see slightly stale data improve
  performance? (\autoref{sec:eval:staleness})
\item How much of a performance penalty does \txcache's
  guarantee of transactional consistency impose?
  (\autoref{sec:eval:consistency})
\item How much overhead is caused by \txcache's modifications to the
  database? (\autoref{sec:eval:db})
\end{itemize}

\section{Implementation Notes}
\label{sec:eval:impl}

We implemented all the components of \txcache, including the cache
server, database modifications to PostgreSQL to support validity
tracking and invalidations, and the cache library with PHP language
bindings.

\paragraph{Cache Server.}
The cache server implements the versioned cache described in
\autoref{sec:consistency-protocol:cache}. It provides a versioned hash
table interface, and maintains an index from invalidation tags to
cached objects necessary to process invalidation messages. The server
accepts requests from the \txcache library over a simple TCP-based RPC
protocol. It is single-threaded, allowing it to avoid locking. This
contributes to the simplicity of the server: our implementation
only requires about 2500 lines of C code.

Our cache server is not optimized for maximum throughput, as cache
throughput was not a bottleneck in any of our experiments. Several
performance optimizations have been developed for \memcached that
could be applied to the \txcache cache server. For example, a custom
slab allocator can be used to reduce the cost of allocating cached
objects (our implementation uses the standard system
\texttt{malloc}). Using a UDP-based RPC protocol can also improve
performance by reducing memory overhead and avoiding contended locks
in the kernel~\cite{saab08:_scalin_memcac_at_faceb}. 


\paragraph{Database Modifications.}
We modified \postgres 8.2.11 to provide the necessary support for use
with \txcache: pinned snapshots, validity interval computation, and
invalidations. This version of \postgres provides snapshot isolation
as its highest isolation level rather than serializability, so we use
this configuration in our experiments.

Our implementation generates invalidations using a simplified version
of the protocol in \autoref{cha:invalidations}. It does not attempt to
store invalidation locks; it simply generates all appropriate
invalidations for every update.  Our implementation tracks
invalidation tags using two granularities: relation-level tags and
index-entry tags. Because this version of \postgres does not
incorporate index-range locking, fine-granularity invalidation tags
cannot be used for range queries; this limitation was not an issue for
the queries used in our benchmark application. Subsequently, we
incorporated index-range locking into \postgres as part of a new
serializable isolation
level~\cite{ports12:_serial_snaps_isolat_postg}.

The modifications required to add \txcache support to \postgres were
not extensive; we added or modified about a thousand lines of code to
implement pinned snapshots and validity interval tracking, and another
thousand lines to implement invalidations.

The modified database interacts with the pincushion, which creates new
pinned snapshots and notifies application servers about them. We also
use a separate daemon to receive invalidation notices from the
database and distribute them to cache nodes. It currently sends
unicast messages to each cache server rather than using a more
sophisticated application-level multicast mechanism.

\paragraph{Client Library.}
The \txcache library is divided into two parts: a language-independent
component that accesses the cache and ensures consistency, and a set
of language-specific bindings. The language-independent part uses the
lazy timestamp selection protocol of
\autoref{sec:consistency-protocol:lazy} to ensure consistency between
objects read from the cache and those obtained from the database. It
also mediates interactions between the application and the database:
applications must use the \txcache library's interface to send queries
to the database. This interface always passes queries directly to the
database (it does not try to parse or otherwise interpret them), but
the library may also insert commands to start a transaction at an
appropriate snapshot, and monitors the validity intervals and
invalidation tags associated with each query result.

\paragraph{PHP Bindings.}
The \rubis benchmark is implemented in PHP, so we provided a set of PHP
language bindings for \txcache. These bindings provide the support for
applications to designate cacheable functions, and marshal and
unmarshal objects when they are stored in or retrieved from the cache.

We previously presented the \txcache interface in terms of a
\command{make-cacheable} higher-order procedure. PHP lacks support for
higher-order procedures, so the syntax is a bit more awkward. Instead,
the PHP library provides a \texttt{txcache\_call} function that takes
as arguments the name of a function to call and the arguments to pass
to it. This function checks for an appropriate result in the cache,
and, if none is found, invokes the function. \autoref{fig:php-example}
demonstrates a typical use: users invoke a 
\texttt{getItem} function which is actually
a wrapper function that calls \texttt{txcache\_call}.

\begin{figure}[tbp]
  \centering
  \ttfamily\small
  \begin{lstlisting}[escapechar={@},language={php},columns=fullflexible]
function getItemImpl($itemId)
{
  $res = sql_query("SELECT * FROM users ...");
  @\llangle\textit{some computation on query result} \rrangle@
  $user = @\llangle\textit{result} \rrangle@
  return $user;
}
function getItem($itemId)
{
  global $TX;  // this contains the cache configuration
  return txcache_call($TX, 'getItemImpl', $itemId);
}    
  \end{lstlisting}
  \caption{Example of a cacheable function in PHP}
  \label{fig:php-example}
\end{figure}

\section{Porting the \rubis Benchmark}
\label{sec:eval:rubis}

\rubis~\cite{amza02:_specif_and_implem_of_dynam} is a benchmark that
implements an auction website modeled after eBay where users can
register items for sale, browse listings, and place bids on items. We
ported its PHP implementation to use \txcache.  Like many small PHP
applications, the PHP implementation of \rubis consists of 26 separate
PHP scripts, written in an unstructured way, which mainly make
database queries and format their output. Besides changing code that
begins and ends transactions to use \txcache's interfaces, porting
\rubis to \txcache involved identifying and designating
cacheable functions. The existing implementation had few functions, so
we had to begin by dividing it into functions; this was not difficult
and would be unnecessary in a more modular implementation.

We cached objects at two granularities. First, we cached large
portions of the generated HTML output (except some headers and
footers) for each page. This meant that if two clients viewed the same
page with the same arguments, the previous result could be
reused. Second, we cached common functions such as authenticating a
user's login, or looking up information about a user or item by
ID. Even these fine-grained functions were often more complicated than
an individual query; for example, looking up an item requires
examining both the active items table and the old items table.  These
fine-grained cached values can be shared between different pages; for
example, if two search results contain the same item, the description
and price of that item can be reused.

\paragraph{Determinism.}
Cacheable functions must be deterministic and depend only on database
state. Generally, identifying such functions is easy; indeed, nearly
every read-only function in the system has this property. However,
while designating functions as cacheable, we discovered that one of
\rubis's actions inadvertently made a nondeterministic SQL
query. Namely, one of the search results pages divides results into
pages using a ``\command{select} \ldots\@ \command{limit} 20
\command{offset} $n$'' statement, \ie returning only the $n$ through
$n+20$th results. However, it does not enforce an ordering on the
items it returned (\ie it lacks an \command{order by} clause) so the
database is free to return \emph{any} 20 results. This caused search
results to be divided into pages in an unpredictable and inconsistent
way. This turned out to be a known bug in the PHP implementation,
which was not written by the original authors of \rubis.

\txcache generally leaves determining which functions are cacheable up
to the application developer. However, it incorporates a simple sanity
check that was sufficient to detect this error. The cache issued a
warning when it detected an attempt to insert two versions of the same
object that had overlapping validity intervals, but different
values. This warning indicated a possible non-determinism.

\paragraph{Optimizations.}
We made a few modifications to \rubis that were not strictly necessary
but improved its performance. To take better advantage of the cache,
we modified the code that performs a search and displays lists of
matching items. Originally, this function performed a join in the
database, returning the list of matching items and their
description. We modified it to instead perform a database query that
obtains the list of matching items, then obtain details about each
item by calling our \texttt{getItem} cacheable function. This allowed
the individual item descriptions to be cached separately.

Several other optimizations were not related to caching, but simply
eliminated other bottlenecks with the benchmark workload. For example,
we observed that one interaction, finding all the items for sale in a
particular region and category, required performing a sequential scan
over all active auctions, and joining it against the users table. This
severely impacted the performance of the benchmark with or without
caching, to the point where the system spent the majority of this time
processing this query. We addressed this by adding a new table and
index containing each item's category and region IDs. We also removed
a few queries that were simply redundant.

\section{Experimental Setup}
\label{sec:eval:setup}

We used \rubis as a benchmark to explore the performance benefits of
caching. In addition to the PHP auction site implementation described
above, \rubis provides a client emulator that simulates many
concurrent user sessions: there are 26 possible user interactions
(\eg{browsing items by category, viewing an item, or placing a bid}),
each of which corresponds to a transaction.  The emulator repeatedly
selects the next interaction for each client by following a transition
matrix and each client's interactions are separated by a
randomly-chosen ``think time''.  We used the standard \rubis
``bidding'' workload, a mix of 85\% read-only interactions (browsing)
and 15\% read/write interactions (placing bids). The think time
between interactions was chosen from a negative exponential
distribution with 7-second mean, the standard for this benchmark (as
well as the TPC-W benchmark~\cite{tpc-w}).

We ran our experiments on a cluster of 10 servers, each a Dell
PowerEdge {\liningnumerals SC1420} with two 3.20 GHz Intel Xeon CPUs,
2 GB RAM, and a Seagate {\liningnumerals ST31500341AS 7200 RPM} hard
drive. The servers were connected via a gigabit Ethernet switch, with
0.1 ms round-trip latency. One server was dedicated to the database;
it ran PostgreSQL 8.2.11 with our modifications. The others acted as
front-end web servers running Apache 2.2.12 with PHP 5.2.10 (using
\texttt{mod\_fcgi} to invoke the PHP interpreter), or as
cache nodes. Four other machines, connected via the same switch,
served as client emulators. Except as otherwise noted, database server
load was the bottleneck.

We used two different database configurations. One configuration was
chosen so that the dataset would fit easily in the server's buffer
cache, representative of applications that strive to fit their working
set into the buffer cache for performance. This configuration had
about 35,000 active auctions, 50,000 completed auctions, and 160,000
registered users, for a total database size about 850 MB. The larger
configuration was disk-bound; it had 225,000 active auctions, 1
million completed auctions, and 1.35 million users, for a total
database size of 6 GB.

For repeatability, each test ran on an identical copy of the
database. We ensured the cache was warm by restoring its contents from
a snapshot taken after one hour of continuous processing for the
in-memory configuration and one day for the disk-bound configuration.

For the in-memory configuration, we used seven hosts as web servers,
and two as dedicated cache nodes. For the larger configuration, eight
hosts ran both a web server and a cache server, in order to make a
larger cache available. 


\section{Cache Sizes and Performance}
\label{sec:eval:size}

\begin{figure}[tp]
  \centering
  \subfigure[In-memory database]{
    \includegraphics[keepaspectratio,width=0.8\textwidth]{data/size.pdf}
    \label{fig:eval:size:small}
  }
  
  \subfigure[Disk-bound database]{
    \includegraphics[keepaspectratio,width=0.8\textwidth]{data/size-big.pdf}
    \label{fig:eval:size:big}
  }
  \caption{Effect of cache size on peak throughput (30 second
    staleness limit)}
  \label{fig:eval:size}
\end{figure}

We evaluated \rubis's performance in terms of the peak throughput
achieved (requests handled per second) as we varied the number of
emulated clients. Our baseline measurement evaluates \rubis
running directly on an unmodified \postgres database, without \txcache. This achieved a peak throughput of 928 req/s with the
in-memory configuration and 136 req/s with the disk-bound configuration.

We then ran the same experiment with \txcache enabled, using a 30
second staleness limit and various cache sizes. The resulting peak
throughput levels are shown in Figure~\ref{fig:eval:size}. Depending
on the cache size, the speedup achieved ranged from $2.2\times$ to
$5.2\times$ for the in-memory configuration and from $1.8\times$ to
$3.2\times$ for the disk-bound configuration. This throughput
improvement comes primarily from reduced load on the database server.

The \rubis PHP benchmark does not perform significant
application-level computation. Even so, we see a 15\% reduction in
total web server CPU usage. We could expect a greater reduction in
application server load on a more realistic workload than this simple
benchmark, as it would likely perform more application-level
computation, \eg to do more sophisticated formatting of
results. Furthermore, our measurement of web server CPU usage takes
into account not just time spent on legitimate application processing
but also the time the PHP interpreter spends parsing source code on
each request.

Cache server load is low. Even on the in-memory workload, where the
cache load is spread across only two servers, each cache server's load
remained below 60\% utilization of a single CPU core.  Most of this
CPU overhead in kernel time, suggesting inefficiencies in the kernel's
TCP stack as the cause; switching to a UDP protocol might alleviate
some of this overhead~\cite{saab08:_scalin_memcac_at_faceb}. The
average cache lookup latency is 0.7~ms, significantly lower than even
the in-memory database's average query latency of 5.5~ms (and even
before the database reaches its capacity). There are an average of 2.4
invalidation tags per cached object, and the tags themselves average
16 bytes.

\subsection{Cache Contents and Hit Rate}

We analyzed the contents of the cache (after the warmup period) for
both the in-memory and disk-bound configurations. As shown in
\autoref{fig:cache-contents}, the cache contains many items -- over
500,000 for the in-memory configuration and over 4.5 million for the
disk-bound configuration. Nearly all of the cache server's memory
(over 95\%) goes to storing the cached values themselves; another 2\%
goes to storing the names (keys) for these values. Validity intervals
are small (9 bytes per object), so storing them does not require much
space. Invalidation tags are slightly larger (16 bytes, on average)
and more numerous (an average of 2.4 tags per cache entry).  However,
the cost of storing invalidation tags is still small: about 2\% of
memory.

\autoref{fig:cache-size-histo} shows the distribution of the sizes of
cached objects. Half of the cached
objects are smaller than 400~bytes; these objects typically represent
the results of a single database query, such as looking up the name of
a user. Most of the rest of the objects are under 8~KB in size; these
objects are typically generated HTML fragments or the results of more
complex queries. There are a handful of objects as large as 100~KB,
\eg the detailed bid history of especially popular items,
but there are sufficiently few of them that they do not make up a
significant fraction of the cache workload.

\begin{table}[tbp]
  \centering
  \begin{tabular}{lrrrr}
    \toprule
    & \multicolumn{2}{c}{\bf In-memory workload} & \multicolumn{2}{c}{\bf Disk-bound workload}\\
    \midrule
    \textbf{Cache entries} & $560{,}756$ && $4{,}506{,}747$ \\
    \midrule
    \textbf{Total cache size} & $817.9$ MB && $7.820$ GB \\
    \quad\textrm{Cached values} & $778.5$ MB & ($95.2\%$) & $7.477$ GB & ($95.6\%$)  \\
    \quad\textrm{Cache keys} & $18.1$ MB & ($2.2\%$) & $145$ MB & ($1.8\%$) \\
    \quad\textrm{Validity intervals} & $4.9$ MB & ($0.6\%$) & $40$ MB & ($0.5\%$)\\
    \quad\textrm{Invalidation tags} & $16.4$ MB & ($2.0\%$) & $166$ MB & ($2.1\%$)\\
    \bottomrule
  \end{tabular}
  \caption{Cache contents breakdown}
  \label{fig:cache-contents}
\end{table}

\begin{figure}[tbp]
  \centering
  \subfigure[In-memory database]{
    \includegraphics[width=0.9\textwidth]{data/object-size-histo}
  }
  \subfigure[Disk-bound database]{
    \includegraphics[width=0.9\textwidth]{data/object-size-histo-big}
  }
  \caption{Distribution of cache object sizes. Note the logarithmic x-axis.}
  \label{fig:cache-size-histo}
\end{figure}

Figure~\ref{fig:eval:hitrate:small} shows that for the in-memory
configuration, the cache hit rate ranged from $27\%$ to $90\%$, increasing
linearly until the working set size is reached, and then growing
slowly. On the in-memory workload, the cache hit rate directly
translates into an overall
performance improvement because each cache hit represents load removed
from the database -- and a single cache hit might eliminate the need
to perform several queries. 

\begin{figure}[tp]
  \centering
  \subfigure[In-memory database]{
    \includegraphics[keepaspectratio,width=0.8\textwidth]{data/hitrate.pdf}
    \label{fig:eval:hitrate:small}
  }
  \subfigure[Disk-bound database]{
    \includegraphics[keepaspectratio,width=0.8\textwidth]{data/hitrate-big.pdf}
    \label{fig:eval:hitrate:big}
  }
  \caption{Effect of cache size on cache hit rate (30 second staleness
    limit)}
  \label{fig:eval:hitrate}
\end{figure}

Interestingly, we always see a high hit rate on the disk-bound
database (Figure~\ref{fig:eval:hitrate:big}), but this hit rate does
not always translate into a large performance improvement. This
illustrates an important point about application-level caching: the
value of each cached object is not equal, so hit rates alone rarely
tell the whole story. This workload exhibits some very frequent
queries, such as looking up a user's nickname by ID. These can be
stored in even a small cache, and contribute heavily to the cache hit
rate. However, they are also likely to remain in the database's buffer
cache, limiting the benefit of caching them. This workload also has a
large number of data items that are individually accessed rarely (\eg
the full bid history for auctions that have already ended). The latter
category of objects collectively makes up the bottleneck in this
workload, as the database must perform random I/O to load the
necessary information. The speedup of the cache is primarily
determined by how much of this data it can hold.


\section{The Benefit of Staleness}
\label{sec:eval:staleness}

The staleness limit is an important parameter. By raising this value,
applications may be exposed to increasingly stale data, but are able
to take advantage of more cached data. An invalidated cache entry
remains useful for the duration of the staleness limit, which is
valuable for values that change (and are invalidated) frequently.

\begin{figure}[t]
  \centering
  \includegraphics[keepaspectratio,width=0.8\textwidth]{data/freshness.pdf}
  \caption{Impact of staleness limit on peak throughput}
  \label{fig:eval:freshness}
\end{figure}

Figure~\ref{fig:eval:freshness} compares the peak throughput obtained
by running transactions with staleness limits from 1 to 120 seconds.
Even a small staleness limit of 5-10 seconds provides a significant
benefit.  The \rubis workload includes some objects that are expensive
to compute and have many data dependencies: for example, indexes of
all items in a particular category along with their current prices.
These objects are invalidated frequently, but the staleness limit
permits them to be used.  The benefit begins to diminish at around a
staleness limit of 30 seconds. This reflects the fact that the bulk of
the data either changes infrequently (such as information about
inactive users or auctions), or is modified frequently but also
accessed multiple times every 30 seconds (such as the aforementioned
index pages).



\section{The Cost of Consistency}
\label{sec:eval:consistency}

A natural question is how \txcache's guarantee of transactional
consistency affects its performance. We explore this question in two
ways: we examine cache statistics to analyze the causes of cache
misses, and we compare \txcache's performance against a
non-transactional cache.

\subsection{Cache Miss Analysis}

We classified cache misses into four types, inspired by the common
classification for CPU cache
misses~\cite{hill89:_evaluat_assoc_cpu_caches}: 
\begin{itemize}
\item \emph{compulsory miss}: the object was never in the cache, \ie
  the cacheable function was never previously called with the same
  arguments
\item \emph{staleness miss}: the object has been invalidated, and is
  sufficiently old that it exceeds the application's staleness limit
\item \emph{capacity miss}: the object was previously evicted from the
  cache
\item \emph{consistency miss}: some sufficiently fresh version of
  the object was available, but it was inconsistent with previous data
  read by the transaction
\end{itemize}
The last category, consistency misses, are precisely the category of
interest to us, as these are the cache misses that would be caused by
\txcache but would not occur in a non-transactional cache.

The \txcache cache server records statistics about the cache hit rate
and cache misses of various
types. Figure~\ref{fig:eval:cache-miss-types} shows the breakdown of
misses by type for four different configurations of the \rubis
workload. Our cache server cannot distinguish staleness
and capacity misses, because it discards the associated validity
information when removing an item from the cache either due to
staleness or cache eviction.

We see that consistency misses are the least common by a large
margin. Consistency misses are rare, as items in the cache are likely
to have validity intervals that overlap with the transaction's
request, either because the items in the cache change
rarely or the cache contains multiple versions. Workloads with higher
staleness limits experience a higher proportion of consistency misses
(but fewer overall misses) because they have more stale data that must
be matched to other items valid at the same time. The 64~MB-sized
cache's workload is dominated by capacity misses, because the cache is
smaller than the working set. The disk-bound experiment sees more
compulsory misses because it has a larger dataset with limited
locality, and few consistency misses because the update rate is
slower.

\begin{table}[tb]
  \centering{
  \begin{tabular}{rcccc}
    \toprule
    & \multicolumn{3}{c}{\bf\liningnumerals in-memory DB} & \bf\liningnumerals disk-bound\\
    & \bf\liningnumerals 512 MB & \bf\liningnumerals 512 MB  & \bf\liningnumerals 64 MB & \bf\liningnumerals 9 GB \\
    & \bf\liningnumerals 30 s stale & \bf\liningnumerals 15 s stale & \bf\liningnumerals 30 s stale & \bf\liningnumerals 30 s stale\\
    \midrule
    \input{data/missstats.tex}\\
    \bottomrule
  \end{tabular}}
\caption[Breakdown of cache misses by type]{Breakdown of cache misses
  by type. Figures are percentage of total misses.}
  \label{fig:eval:cache-miss-types}
\end{table}


\subsection{Experimental Comparison}

The low fraction of consistency misses suggests that providing
consistency has little performance cost. We verified this
experimentally by comparing against a non-transactional version of our
cache. That is, we modified our cache to continue to use our
invalidation mechanism, but configured the \txcache library to
blithely ignoring consistency: it
accepted
any data that was valid within the last 30 seconds, rather than the
usual protocol that requires the validity intervals to intersect.

\begin{figure}[tp]
  \centering
    \includegraphics[keepaspectratio,width=0.8\textwidth]{data/size-memcache.pdf}
  \caption{Comparison of \txcache and a non-transactional cache for
    varying cache sizes; in-memory workload}
  \label{fig:eval:memcached}
\end{figure}

The results of this comparison are shown in
\autoref{fig:eval:memcached}, which reproduces the experiment in
\autoref{fig:eval:size:small}: it measures \rubis system throughput
for varying cache sizes on the in-memory configuration. Now, however,
the non-transactional version of our cache is shown as the ``No
consistency'' line.  As predicted, the benefit that this configuration
provides over consistency is small. On the disk-bound configuration,
the results could not be distinguished within experimental error.

\section{Database Overhead}
\label{sec:eval:db}

The \txcache system requires some modifications to the database, to
compute validity intervals, provide access to recent snapshots, and
generate invalidations.  The experiments described earlier compare the
performance of \rubis running with \txcache to a baseline
configuration running directly on a unmodified \postgres database. Not
surprisingly, the benefit of caching exceeds the additional overhead
incurred by the database modifications. Nevertheless, we would like to
know how much overhead these modifications cause.


To answer this question, we first performed the baseline \rubis
performance experiment (without \txcache) with both a stock copy of
\postgres and our modified version. We found no observable difference
between the two cases: our modifications had negligible performance
impact. Because the system
already maintains multiple versions to implement snapshot isolation,
keeping a few more versions around adds little cost, and tracking
validity intervals and invalidation tags simply adds an additional
bookkeeping step during query execution.

Because our end-to-end web application benchmark saw negligible
overhead, we performed a database-level benchmark to more precisely
measure the cost of these modifications. We used the \texttt{pgbench}
benchmark~\cite{pgbench}, a simple transaction-processing benchmark
loosely based on TPC-B~\cite{tpc-b}. This benchmark runs transactions
directly on the database server; there is no cache or application
server involved. The modified database, however, still computes
validity intervals and generates invalidation messages (which are sent
to a ``multicast'' daemon that simply discards them, since there are
no cache servers). A simulated pincushion contacted the database every
second to obtain a new pinned snapshot, then released after 1--180
seconds.

We ran these benchmarks on a different system configuration than the
\rubis benchmark. We used a 2.83 GHz Core 2 Quad Q9550 system with 8
GB RAM running Ubuntu 11.10. The most significant difference is that
the database was not stored on disk at all; rather, it was stored on
an in-memory file system (\texttt{tmpfs}). As a result, the workload
is purely CPU-bound -- even more so than the in-memory \rubis
configurations, where modifications and write-ahead log updates still
had to be written to disk. This is a ``worst-case'' configuration
intended to expose the overhead of our modifications. In particular,
it stresses the invalidation mechanism, because this in-memory
configuration can support an unusually high update rate because
updates do not need to be synchronously written to disk.

Even on this worst-case, in-memory configuration, the overhead of
\txcache's database modifications is low. \autoref{fig:pgbench}
compares the performance of our modified database to stock \postgres
8.2.11. The modifications impose an overhead of less than 7\% for
computing validity intervals and generating invalidations. The amount
of overhead also depends on the age of the pinned snapshots that are
being held, as the system must retain all tuple versions that are
newer than the earliest pinned snapshot. This makes query processing
slightly more expensive, because the system must examine these
versions and decide which ones should be visible to a running
transaction. However, the performance impact is not large: the cost of
retaining an extra 180 seconds of state is under 3\%, even with the
unusually high update rate of this benchmark.

\begin{figure}[tbp]
  \centering
  \includegraphics[width=0.9\textwidth]{data/pgbench}
  \caption{\texttt{pgbench} transactions per second for modified and unmodified \postgres}
  \label{fig:pgbench}
\end{figure}

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

%  LocalWords:  versioned allocator optimizations invalidations TCP
%  LocalWords:  granularities serializability serializable RPC PHP
%  LocalWords:  unicast multicast timestamp cacheable unmarshal SQL
%  LocalWords:  transactional UDP
