\documentclass[a4paper,11pt]{article}
\usepackage{fullpage}
\twocolumn

% Draftification
\newif\ifdraft
%\drafttrue
\draftfalse

\usepackage{times}
\newcommand{\bptree}{B\textsuperscript{+}-tree}
\newcommand{\bptrees}{B\textsuperscript{+}-trees}
\newcommand{\PersiFS}{PersiFS}
\addtolength{\oddsidemargin}{-0.5cc}
\addtolength{\textwidth}{1cc}
\addtolength{\textheight}{3cc}
\addtolength{\topmargin}{-1.5cc}
\addtolength{\columnsep}{8pt}

\hyphenation{time-stamp}

\begin{document}

% XXX Too long
%\title{PersiFS: \LARGE{Efficient Persistent Data Structures for
%    Continuously Versioned File Systems}}
\title{PersiFS: \LARGE{A Versioned File System with an Efficient
    Representation}}
% XXX Funky formatting
% XXX Demaine?  RTM?  Hector?  Ben?
\author{Dan R. K. Ports, Austin T. Clements, and Erik D. Demaine
  \footnote{MIT Computer Science and Artificial Intelligence
  Laboratory;
  \texttt{\{drkp,aclements,edemaine\}@mit.edu}}}
\date{}
\maketitle

\thispagestyle{empty}

% Efficient representations for versioned file systems
% A versioned file system with an efficient representation

% Things to mention
% * Saves all versions
% * Interface
% * Representation
% ** Partially-persistent B+-tree to store and retrieve inodes
% ** Superblob (how does one sum this up?)
% *** Content-addressable block store
% *** Variable-sized blocks, split on content-based boundaries
% *** Chunk fusion
% *** ``Chunks'' versus ``Blocks''
% **** ``Blocks'' would be more generally understood, but could get
%      confused with disk blocks
% *** Probably best to not treat the superblob index as a separate
%     entity, at least for the purposes of the abstract
% * Preliminary measurements of our prototype indicate...

% Presentation notes
% * On title slide, have subsubtitle ``bringing the past to the
%   present for a better future!''

The availability of previous file versions is invaluable for
recovering from file corruption or user errors such as accidental
deletions.  \emph{Versioned} file systems address this need by
retaining earlier versions of changed files. Many existing file
systems, such as Plan 9, WAFL, AFS, and others, use a
\emph{snapshotting} approach: they record and archive the state of the
file system at periodic intervals.  However, this fails to capture
modifications that are made between snapshots.
% and often leads to performance degradation during the snapshotting
% process. (wrong place for this, but it should be mentioned
% somewhere)
Our system, \PersiFS, is \emph{continuously versioned}, meaning that
it stores every modification, and thus allows access to the file
system state as it appeared at any specified time.  To make this
feasible, we use a number of efficient data structures to optimize
both access time and disk space.
% Other continuously versioned file systems include [XXX: list].
% (I don't think we want to laundry-list these, but just bring them up
% as we can make useful comparisons to them)

% Comparisons
% * Snapshotting systems (WAFL, AFS, Plan 9)
% ** No periodic down/grind-time/performance degradation
% ** No Planck length on mistakes that can be undone
% * Log-based systems
% ** No need for space-consuming log snapshots
% ** No need for slow log replays
% * All other systems?
% ** Efficient contents fusion
% *** Space saving, but higher fragmentation
% *** Similar to Venti, but LBFS chunking adds a whole new dimension

% * Retention (future work)
% ** For the per-user configuration, perhaps in addition to things
%    like "don't version .o files" we could have full control of
%    retention policy, parameterized over things like directory,
%    extension, etc. Somehow it would have to be combinable with
%    administrative retention policy

%% \PersiFS\ is a persistent, or versioned, file system -- it allows
%% users to access previous states of the file system. This has obvious
%% utility in cases of accidental deletion, file corruption, version
%% control, etc.  Unlike snapshotting file systems like Plan 9's, WAFL,
%% or AFS, \PersiFS\ stores every modification to the file system, so it
%% can recover the state of the file system at any specified time.

\PersiFS\ directly exposes access to past file revisions through the file
system interface, allowing convenient access with standard file system
tools. The current version of the file system tree is available
read-write at \texttt{\small /persifs/now}, and read-only views of
previous versions are automatically mounted simply by specifying a
timestamp instead of ``\texttt{\small now}''.
%% So, for example, a
%% file might be at \texttt{/persifs/now/foo/bar}, and viewing
%% \texttt{/persifs/2005-08-20-12-00-00/foo/bar} would show how the file
%% appeared at noon, August 20\textsuperscript{th}.
No special tools or per-file version numbers are required, though
convenience tools exist, e.g. for listing all revisions of a
particular file.
% * Mention automounting of past version directories
% * Less of specific examples

Efficiently storing all previous revisions of each file presents a new
set of challenges because of the volume of data involved. Our major
contribution is a compact representation that supports efficient
queries and modifications. Most previous continuously versioned
systems, such as CVFS, VersionFS, and Wayback, use a log-based
representation that requires an expensive scan of the log to access
earlier revisions, and periodic snapshots. Instead, \PersiFS\ uses
\emph{partially persistent} data structures, which are data structures
that can answer queries about any of their previous states.

\PersiFS\ stores all past and present file metadata in a
\emph{partially persistent \bptree}, eliminating the need for logs and
snapshots.  Our partially persistent \bptree\ provides read-write
access to the current revision and read-only access to previous
revisions with theoretical guarantees on worst-case performance.
Reading from \emph{any} revision or modifying the current revision
requires disk accesses only logarithmic in the size of that revision,
and committing the current revision does not require any disk
accesses.  Thus, accesses and modifications require approximately as
little time as standard, unversioned \bptree-based file systems take
to operate on the current revision.  Moreover, unlike logging designs,
\PersiFS\ can access \emph{any} previous revision with the same
efficiency, and there is no need to maintain a separate copy of the
current revision.


Since disk sizes are not yet infinite, \PersiFS\ exploits the
similarity between files in different revisions in order to minimize
the amount of storage space required. This is achieved with indirect
storage: the \bptree\ contains only metadata and pointers to file
contents stored in a separate structure called the \emph{superblob}.
File contents are divided into \emph{chunks} using the LBFS
variable-sized segmentation algorithm, which places chunk boundaries
based on content rather than at fixed offsets. Like Venti, \PersiFS\
identifies chunks by a hash of their contents, so it does not need to
store identical chunks more than once. The result is that \PersiFS\
can share identical content on disk between any revision of any file,
thus greatly reducing file storage costs.

%% Our major contributions are the above interface and a data
%% representation that makes it feasible.  Unlike traditional, log-based
%% versioned file systems, \PersiFS\ stores all past and present metadata
%% in a partially persistent \bptree\, eliminating the need for snapshots
%% and making the number of disk accesses required to retrieve data from
%% any point in the time asymptotically optimal.  Actual file data is
%% stored in a content-addressable structure that uses a chunk
%% fingerprint index to coalesce identical file chunks.  To exploit this
%% content-addressable storage, \PersiFS\ splits file contents into
%% variable sized chunks using content-sensitive chunking.  By placing
%% chunk boundaries based on content instead of at fixed offsets,
%% \PersiFS\ is able to exploit similarity between new and past versions
%% of files, as well as similarity between files.  Identical content
%% shared between any versions of any files is shared on disk as well,
%% thus greatly reducing file storage costs.

% * Flexible version retention policy?

% It uses LBFS chunking and content-addressible storage (like Venti) to
% store file content, minimizing the amount of disk space required by
% taking advantage of similar data in different revisions of files. To
% track file and revision metadata, we designed a simple new persistent
% B+-tree data structure based on a technique by Sleator and Tarjan.
% This allows efficient access to both current and past versions of file
% state, substantially faster than the standard approach of replaying a
% log.

% * Preliminary measurements

Our early prototype of \PersiFS\ includes both the representation
described above and a standard log-based backend. Comparison
measurements indicate that \PersiFS's representation yields
substantially better performance than logging for many workloads, as
well as significant improvements in storage costs, without
sacrificing the speed of regular access. This system also provides
worst-case guarantees per operation, whereas snapshotting generally
significantly slows down system performance during snapshot
operations.

Current work focuses on refining our implementation and optimizing
performance. In particular, we are researching techniques for
rearranging file chunks on disk to exploit locality. We are also
adding support for flexible retention and expiration policies to
reduce storage usage.

\ifdraft \vfill \hfill \verb|$Rev$ $Date$| \fi
\end{document}