\svnInfo $Id$ The validity intervals that \txcache uses in its cache are derived from validity information generated by the database. To make this possible, \txcache uses a modified DBMS that has similar versioning properties to the cache. Specifically, it can run queries on slightly stale snapshots, and it computes validity intervals for each query result it returns. Though standard databases do not provide these features, they can be implemented without much difficulty by taking advantage of the same mechanisms that are used to implement multiversion concurrency control techniques like snapshot isolation. In this section, we describe how we modified an existing DBMS, PostgreSQL~\cite{postgresql}, to provide the necessary support. The modifications are not extensive; our implementation required changing less than a thousand lines of code. Moreover, they are not Postgres-specific; the approach is applicable to other databases that use multiversion concurrency. \subsection{Exposing Multiversion Concurrency} Because our cache allows read-only transactions to run slightly in the past, the database must be able to perform queries against a past snapshot of a database. This situation arises when a read-only transaction is assigned a timestamp in the past as a result of using some cached data and then a later operation in the same transaction results in a cache miss, requiring the application to query the database. The database query must return results consistent with the previously-returned cached values, so the query must execute at the same timestamp in the past. One solution is to use a \emph{temporal database}, which tracks the history of its data and allows ``time travel'' --- running queries against previous database state. Although such databases exist, they are not commonly used, because retaining historical data introduces substantial storage and indexing cost.\footnote{The POSTGRES research database was one such system. However, time travel support was removed early in transition to an open-source production database, precisely because it was considered too expensive.} Therefore, we do not consider this a practical solution. Instead, we note that the form of history query support required by our cache is much more limited than general time-travel queries. We simply require the ability to run a transaction on a stale, but recent snapshot, not the ability to perform complex queries over the entire history of the database. In addition, the historical data does not need to be recoverable after a crash, since we assume the cache is cleared after the database restarts. Our insight is that these requirements are essentially identical to those required for supporting multiversion concurrency control techniques such as snapshot isolation~\cite{berenson95:_critiq_of_ansi_sql_isolat_level}, so many databases already have the necessary infrastructure to support them. We modified Postgres to support running transactions on recent snapshots by exposing the multiversion storage it uses internally to implement snapshot isolation. We added a \command{pin} command, which can be called from a read-only transaction; it assigns an identifier to the transaction's snapshot. When starting a new transaction, if this ID is specified using the new \command{snapshotid} argument to the \command{begin} command, the new transaction will see the same view of the database as the erstwhile read-only transaction. The database state as of that snapshot is guaranteed to be retained until it is released with the \command{unpin} command. A pinned snapshots is identified by the transaction ID of the last committed transaction visible to it. (Here, we assume that transaction IDs are ordered by their commit time; Postgres actually uses a different representation internally, so this requires a simple mapping.) Postgres is especially well-suited to this modification because of its ``no-overwrite'' storage manager~\cite{stonebraker87:_desig_of_postg_storag_system}, which already retains recent versions of data. Because stale data is only removed periodically by an asynchronous ``vacuum cleaner'' process, the fact that we keep data around slightly longer has little impact on performance. However, our technique is not Postgres-specific; any database that implements snapshot isolation must have a way to keep a similar history of recent database states. \subsection{Tracking Result Validity} \label{sec:database:validity} When a read-only transaction executes a query, the returned result is guaranteed valid at the timestamp associated with that transaction. Therefore, any values the application computes from that query result can be stored in the cache, and used by other transactions assigned to the same timestamp. However, this is overly restrictive, as it requires other transactions to have exactly the same timestamp in order to use the shared data. In fact, a query result is valid for a \emph{range} of time, because other transactions may not have affected the query result. We call this range the result's \emph{validity interval}. In this section, we describe how to efficiently compute the validity interval for a query result. A query result's validity interval is a range of timestamps. The lower bound is the commit time of the most recent transaction that caused any tuple in the result to become valid, and the upper bound is the commit time of the most recent subsequent transaction that changed any tuple in the result, making it invalid, or infinity if the result is still current. \edatnote{DRKP}{Maybe this belongs earlier.} The validity interval is computed as the intersection of two ranges, the \emph{result tuple validity} and the \emph{invalidity mask}, which we track separately. % XXX Even though this figure isn't referenced for a while, it's good % if it appears near the beginning of the section so people can have % it in their minds. \begin{figure}[tp] \centering \includegraphics[scale=0.4]{db-intervals.pdf} \caption{An example of how validity intervals are tracked for read-only queries. All four tuples match the query predicate. Tuples 1 and 2 match the timestamp, so their intervals intersect to form the result validity. Tuples 3 and 4 fail the visibility test, so their intervals join to form the invalidity mask. The final validity interval is the difference between the result validity and the invalidity mask.} \label{fig:db-intervals} \end{figure} The result tuple validity is the intersection of the validity times of the tuples returned by the query. This reflects the fact that the results of the query would have been different before any of the returned tuples had been created, or after any had been deleted. Computing this interval is relatively straightforward, because multiversion concurrency requires that each tuple in the database be tagged with the ID of its creating transaction and deleting transaction (if any). We simply propagate these tags throughout query execution. For any operator that combines multiple tuples to produce a single result, such as a join or aggregate, the validity interval of the output tuple is the intersection of the validity intervals of all inputs. Finally, once the entire result set has been produced, we take the intersection of the tuples' validity intervals. The result tuple validity, however, does not completely capture the validity of a query. The tuples that did \emph{not} appear in the result, but would have if the query were run at a different timestamp, also have an impact. For example, a matching tuple that was deleted just before the querying transaction's timestamp will not appear in its results, but does mean the results would have been different if computed slightly earlier in the past. We capture this effect with the invalidity mask, which is the union of the validity times for all tuples that failed the \emph{visibility check}, causing them to be discarded because their timestamps made them invisible to the transaction's snapshot. Throughout query execution, whenever a tuple is encountered that was deleted before or created after the transaction's snapshot time, that tuple's validity interval is added to the invalidity mask. The invalidity mask is a conservative estimate because visibility checks are performed as early as possible in the query plan to avoid processing unnecessary tuples. Some of these tuples might have been discarded anyways if they failed the query conditions later in the query plan. If timestamps were only checked after the query executed to completion, the validity interval would be completely accurate, but tuples that could never appear in the result would be subjected to potentially expensive query processing. While this preserves the correctness of the cached results, it might reduce the cache hit rate by unnecessarily constraining the validity intervals of cached items. Though the visibility check is generally performed as early as possible, in the case of sequential scans and index lookups, we evaluate the predicate before the visibility check. This differs from regular Postgres with respect to sequential scans: unmodified Postgres evaluates the visibility check first because it is marginally cheaper. Delaying visibility checks in these two cases improves the quality of the invalidity mask while incurring minimal overhead. The final validity interval for a query is computed by subtracting the invalidity mask from the result tuple validity. This interval is reported to the client, piggybacked on the result of all \command{select} queries. Section~\ref{sec:library} describes how the \txcache library combines these intervals to obtain validity intervals for all items it stores in the cache. If a result returned by a query is still valid in the present (\ie running the query on the latest snapshot would return the same result), then the upper bound of the query's validity interval is unknown. The database can either indicate that the upper bound is presently unknown, or it can assign the validity interval some conservative upper bound. Because the former route would require an invalidation scheme in order to assign upper bounds to cached values once they become known, \txcache takes the latter approach, upper bounding any returned validity intervals at the latest timestamp known to the database when the query begins executing. As a concrete example, figure~\ref{fig:db-intervals} shows a simple select query running at timestamp 46 that considers four tuples, all of which match the query predicate, but only two of which satisfy the visibility check. For example, tuple 1 was created with commit 43 and deleted with commit 47, so it appears in the result of the query, while tuple 3 was deleted by commit 45, before the query's timestamp, so it does not appear in the result of the query. The result tuple validity is the intersection of the validity intervals of the tuples returned by the query; in this case, tuples 1 and 2 yield a result tuple validity of 44-47. Tuples that match the query predicate but are discarded by the visibility check contribute to the invalidity mask; in this case, tuples 3 and 4 would have affected the query result had the query been run sufficiently earlier or sufficiently later. The final validity interval of 45-47 is simply the difference of the result tuple validity and the invalidity mask. Together, these guarantee that if the query were run at any other timestamp in the final validity interval, it would have returned the same result. % \begin{ednote}{DRKP} % Should say something here about either invalidations, or how % unbounded intervals are bounded (for the no-invalidations design), % or both --- haven't decided which is best yet. % \end{ednote} \subsection{Pincushion} \txcache needs to be able to identify currently pinned snapshots satisfying a read-only transaction's freshness requirement, and to eventually unpin unused snapshots. To do this, it must keep track of what snapshots are currently pinned on the database, and which pinned snapshots are currently being used by running transactions. In principle, the DBMS itself could be responsible for tracking this information. However, to reduce the overall load on the database, we chose to place this functionality instead in a separate daemon known as the \emph{pincushion} (so named because it holds the pinned snapshot IDs). The pincushion is lightweight, so can be placed anywhere, \eg{on the same host as the database, or on one of the cache servers}. The pincushion maintains a table of currently pinned snapshots. For each snapshot, it records the snapshot's ID, the corresponding wall-clock timestamp, and the number of running transactions that might be using that snapshot. When beginning a read-only transaction, the \txcache library running on some application node requests from the pincushion all sufficiently fresh pinned snapshots, \eg{any pinned in the last 30 seconds}. The pincushion returns a list of matching snapshots and records that any of these pinned snapshots might be in use for the duration of the transaction. If the pincushion does not have any pinned snapshots that satisfy the requested freshness requirement, the \txcache library must create a new snapshot. It does so by starting a new read-only transaction that runs in the present, and pinning its snapshot. Whenever the library does so, it registers the snapshot's ID and wall-clock time with the pincushion for tracking. To ensure correct ordering despite network latency and unsynchronized clocks, we always use the snapshot's wall-clock time as reported by the database. Finally, the pincushion is responsible for unpinning snapshots on the database when they are no longer needed. Periodically, it scans the list of pinned snapshots for snapshots older than a maximum staleness, and which no transaction may be using. Any such snapshots are removed by sending an \command{unpin} command to the database. % LocalWords: multiversion Postgres timestamp tuple tuples DRKP tuple's %%% Local Variables: %%% mode: latex %%% TeX-command-default: "Make" %%% TeX-PDF-mode: t %%% TeX-master: "paper.tex" %%% End: % LocalWords: unsynchronized versioning