1.7 A home on the Internet — Ludovic Courtès — Versioning
  • Xdelta3: tools and library to read/write compressed diffs [macdonald05:xdelta3]
    Joshua MacDonald, 2005

    Written by the author of PRCS.

  • Using Content-Derived Names for Configuration Management [hollingsworth97:cdn-scm]
    Jeffrey K. Hollingsworth, Ethan L. Miller (University of Maryland College Park, USA; University of Maryland Baltimore County, USA), Proceedings of the ACM Symposium on Software Reusability, May 1997

    One of the first documents describing content-based indexing, not unlike Shapiro's papers on OpenCM shapiro03:opencm.

  • A State-of-the-Art Survey on Software Merging [mens02:merging]
    Tom Mens, appeared in IEEE Transactions on Software Engineering, May 2002
  • Towards XML Version Control of Office Documents [ronnau05:xml-versioning]
    Sebastian R?nnau, Jan Scheffczyk, Uwe Borghoff (Institute for Software Technology, Universit?t der Bundeswehr M?nchen, Germany), Proceedings of the ACM Symposium on Document Engineering, 2005

    Application of the algorithms behind XyDiff cobena02:xydiff to OpenOffice.org (OASIS) documents.

  • The GNU Arch Distributed Revision Control System [lord05:gnu-arch]
    Tom Lord, 2005

    GNU arch is a cutting-edge Free version control system that is becoming more and more widely used. It most important Free competitors are Darcs and Torvalds' GIT. Read here for details on how arch will "adopt" GIT. Update : so-called GNU Arch 2 or revc, relying on GIT, is being developed by Tom Lord. Re-update: Tom Lord has left.

  • The Design and Implementation of Distributed, Disconnected Operation in PRCS [macdonald:prcs-disconnected]
    Joshua MacDonald, 1998

    This paper explains how Xdelta was meant to be used in PRCS2 to support disconnected operation. It briefly mentions the resemblance between Xdelta's algorithm and Rsync's tridgell96:rsync.

  • OpenCM: Early Experiences and Lessons Learned [shapiro03:opencm]
    Jonathan Shapiro, John Vanderburgh, Jack Lloyd (Systems Research Laboratory, Department of Computer Science, Johns Hopkins University, USA), Proceedings of the USENIX Annual Technical Conference, FREENIX Track, 2003

    Discusses issues encountered with OpenCM in its early design stages. In particular, the paper discusses error in the ``schema'' used to store file and revision meta-data. Notably, the authors show the consequences of their failure to respect separation of concerns when designing some data structures (namely, inlining the vector of Entity objects into the Change object) as well as inefficiencies regarding compression. #;(FIXME: Finish!)

  • CPCMS: A Configuration Management System Based on Cryptographic Names [shapiro02:cpcms]
    Jonathan S. Shapiro, John Vanderburgh (Systems Research Laboratory, Johns Hopkins University, USA), Proceedings of the USENIX Annual Technical Conference, FREENIX Track, 2002

    As the name suggests, this paper is one of the ``targets'' of Henson's paper henson03:cmpbyhash. CPCMS is the former name of OpenCM.

  • Deciding When to Forget in the Elephant File System [santry99:deciding]
    Douglas S. Santry, Michael J. Feeley, Norman C. Hutchinson, Alistair C. Veitch, Ross W. Carton, Jacob Ofir (Department of Computer Science, University of British Columbia; Storage Systems Program, Hewlett-Packard Laboratories), Proceedings of the 17th ACM Symposium on Operating Systems Principles, December 1999

    Here is the Holly Grail. The Elephant File System (EFS), is an exhaustive (as opposed to checkpointing, as in quinlan02:venti -- here, a new version is created each time close () is called) versioning file system implemented on top of FreeBSD, within the kernel (source code is not available unfortunately). The paper focuses mainly on the integration of policies responsible for deciding which files need versioning and which versions need to be kept based on file systems' usage patterns -- i.e., it does not assume infinite storage as in Venti quinlan02:venti. Studies of file system contents show that 1/3rd of files do not need to be versioned (e.g. cache, temporary files, derived files) while those that do need versioning represent less than half of the total amount of data stored in the file system. Retaining versions for these files would only cost about 1.4 MB per user per day. EFS implements four per-file storage reclamation policies: no versioning (i.e. traditional file system semantics), complete versioning, short-term history only (i.e. undo protection), and the use of landmarks to manage long-term history and let the user/system select which versions are important (EFS can automatically define landmarks using heuristics). A user-level privileged cleaner process periodically looks for files whose policy allows to reclaim storage and does so. Note that file groups may be defined for inter-dependent files so that a landmark version of one file is automatically considered as a landmark version of the other files of the group. EFS allows to implement new retention policies in the form of a user-space untrusted process that communicates with the cleaner. For non-versioned and newly created files, EFS uses a simple inode as the root pointer to the file's data; it automatically switches to an inode log (which is bigger than an inode) when a versioned file is being modified. The inode log is a vector (that may span on several blocks) storing the list of root inodes for each version of the file. For each directory, EFS associates an active partition and a history partition, both of which contain a list of file entries consisting of a file name, its inode/inode log number, and its creation and deletion time. The active partition contains only entries corresponding to files that are currently present in the directory and to recently deleted files; EFS periodically moves deleted file entries to the history partition. EFS comes with a number of tools for dealing with files' history, and allows for dated file lookups in a way similar to that of Ext3Cow. Last but not least: it performs almost as well as FFS.

  • Evaluation of Efficient Archival Storage Techniques [you04:evaluation]
    Lawrence L. You, Christos Karamanolis (University of California, Santa Cruz, CA, USA; Hewlett-Packard Labs, MS, USA), Proceedings of 21st IEEE/12th NASA Goddard Conference on Mass Storage Systems and Technologies, April 2004

    An interesting comparison of inter-file compression techniques (data ``chunking'' ? la Manber manber94:finding and delta encoding) and traditional intra-file compression techniques (gzip). The authors also combine both types of compression. See also you05:deepstore.

  • GIT---A Stupid Content Tracker [hamano06:git]
    Junio C. Hamano (Twin Sun, Inc.), Proceedings of the Linux Symposium, Volume One, July 2006

    A presentation published at OLS of the GIT content tracker and distributed revision control system initially written by Linus Torvalds for the Linux kernel development. The document provides a nice introduction to Git's internals, and shows that they are really straightforward. The author then shows how higher level features are built on top of ``core Git'' (aka. ``Plumbing''). A few optimizations are sketched, notably the ability to limit diffs to partial tree diffs. Looks like an interesting tool, although the implementation is too much ``works for me'' in spirit. It's also too stupidly bound to SHA-1.

  • The Vesta Approach to Software Configuration Management [heydon01:vesta]
    Allan Heydon, Roy Levin, Timothy Mann, Yuan Yu (Compaq Systems Research Center, USA), March 2001

    Compaq's software configuration management (SCM) system. One of the goals of Vesta is to allow for reproducible builds. Vesta handles this by allowing developers to precisely define each revision of each dependency or build tool (in a way not unlike ``configs'' in GNU Arch). Vesta can then handle the build by itself and supports incremental build. The system is implemented using a purely functional languages, which allows caching the result of some functions, notably compilation.

  • An Empirical Study of Delta Algorithms [hunt96:delta]
    James J. Hunt, Kiem-Phong Vo, Walter F. Tichy (University of Karlsruhe, Germany; AT&T Research, NJ, USA), Software configuration management: ICSE 96 SCM-6 Workshop, 1996

    Detailed evaluation of various differential algorithms including traditional Unix diff, bdiff, and vdelta.

  • J. MacDonald's Page on Xdelta [macdonald00:xdelta-personal-page]
    Joshua MacDonald, 2000

    This page explicitly states that Xdelta uses Rsync's algorithm tridgell96:rsync.

  • File System Design for an NFS File Server Appliance [hitz94:file]
    Dave Hitz, James Lau, Michael Malcolm (NetworkAppliance, Inc., USA), Proceedings of the USENIX Winter Technical Conference, January 1994

    Describes NetAppliance's snapshot file system, WAFL (Write Anywhere File Layout). The file system uses copy-on-write to implement snapshots. Snapshots are made available under a (hidden) .snapshot sub-directory in each directory. WAFL makes frequent snapshots called consistency points whose purpose is to aid recovery: upon recovery (e.g., after a machine crash), the last consistency point can be used right away, removing the need for an fsck-like operation. The snapshot operation is effectively made atomic through the use of copy-on-write and shadow paging.

  • Concurrency Control and Recovery in Database Systems [bernstein87:concurrency]
    Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman, 1987

    Large book (freely available online) with an interesting and well-written chapter on recovery (see Chaper 6, ``Centralize Recovery'', about transactions, checkpointing, atomicity, recovery, etc.), among other things.

  • The Monotone Versioning System [monotone05:website]
    Graydon Hoare, 2005

    This Free (GPL'd) SCM system relies on cryptographic identification of a file's versions, pretty much like what Venti does, indeed quinlan02:venti. It actually uses a database for storing archives. The manual contains an interesting discussion that aims at showing why (SHA1) hashes are good version identifiers, unlike stated in An Analysis of Compare-by-hash by Val Henson henson03:cmpbyhash. The authors' counter-argument are mostly the following:

    • using random input when computing the probability of accidental collisions is relevant since a cryptographic hash function is designed to have a strong avalanche property;
    • the paper mixes accidental and malicious collisions; if the hash function gets ``broken'', it makes it unsafe against collision attacks, it doesn't make it unusable in the presence of trusted users; in fact, for this reason, I believe Henson might agree that Monotone and versioning is an appropriate use of compare-by-hash.
    In other words, the authors argue that accidental collisions are practically way too rare. It does not say anything about the other arguments of the paper, such as the fact than however rare collisions are, relying on this does increase by some epsilon the likeliness of the occurrence of a fault. See also black06:cmpbyhash on that topic.

  • Torvalds' GIT, the Stupid Content Tracker [torvalds05:git]
    Linus Torvalds (OSDL), 2005

    Code itself is available by FTP from kernel.org:/pub/linux/kernel/people/torvalds/. GIT features an object database which is "literally just a content-addressable collection of objects" (quoting the README file). All objects "are all in deflated with zlib, and have a header that not only specifies their tag, but also size information about the data in the object. It's worth noting that the SHA1 hash that is used to name the object is always the hash of this _compressed_ object, not the original data." This all seems to be very influenced by Monotone monotone05:website and Darcs (no archive). However, note that only entire files (stored as ``blobs'') are content-addressed. This seriously limits the amount of data that may be shared across subsequent revisions of a tree and within a given tree revision (see manber94:finding for improvements). Update: GNU Arch 2 by Tom Lord adopts `git'. Re-update: GNU Arch 2 is born-dead.

  • Versioned File Archiving, Compression, and Distribution [macdonald99:versioned]
    Joshua MacDonald, 1999

    The initial paper describing XDelta.

  • Metadata Efficiency in Versioning File Systems [soules03:metadata]
    Craig A.N. Soules, Garth R. Goodson, John D. Strunk, Gregory R. Ganger (Carnegie Mellon University, USA), Proceedings of the Second USENIX Conference on File and Storage Technologies, April 2003

    An ode to efficient meta-data structures, easing lossless inter-version compression. The author explores part of the design space for meta-data structures for their a comprehensive versioning file system, called CVFS. They advocate the use of journal for each block of a file, containing pointers to the various successive versions of that block. At the same time, "only the current version of the inode and indirect blocks are kept, significantly reducing the amount of space required for meta-data". Major weaknesses:

    1. This data structure really comprises two data structures: the per-block journal to keep track of historical versions, and a conventional inode tree to access the current version; this lacks the elegance of the tree structure used by Venti, GNUnet, et. al quinlan02:venti;
    2. As highlighted by the authors, this structure does not impact access time for the current version but yields bad performance for access to older versions (the more versions there are, the longer the journal, and the longer the traversal till we reach the requested version);
    3. In order to mitigate this problem, CVFS adds a checkpoint mechanism atop this journal mechanism where a checkpoint contains pointers to all the blocks that comprise the revision it represents; this is similar to GNU Arch's cached revisions and revision libraries in a way: trading access time against space efficiency; this contributes to the complexity of the system;
    4. Time-stamps are used throughout the data structure as a way to identify revisions; this seems extremely naive and unreliable, especially since real comprehensive versioning (not on-close) is being performed (this may require sub-second accuracy).
    A table shows a comparison of various data and meta-data versioning techniques. The authors compare their journal-based meta-data versioning technique to the so-called ``conventional'' meta-data versioning technique. This conventional technique precludes sharing of information among successive versions of the meta-data, which is obviously inefficient. Anyway, it would be interesting to compare the amount of meta-data that may be shared among successive versions using this technique and the one used in Venti et. al quinlan02:venti.

  • Redundancy Elimination Within Large Collections of Files [kulkarni04:redundancy]
    Purushottam Kulkarni, Fred Douglis, Jason LaVoie, John M. Tracey ( University of Massachusetts, MA, USA; IBM T. J. Watson Research Center, NY, USA), Proceedings of the USENIX Annual Technical Conference, 2004

    An evaluation similar to that found in you05:deepstore and you04:evaluation.

  • RCS---A System for Version Control [tichy85:rcs]
    Walter F. Tichy (Purdue University, West Lafayette, IN, USA), appeared in Software---Practice & Experience, 1985

    About GNU RCS, the Revision Control System.

  • PRCS: The Project Revision Control System [macdonald98:prcs]
    Josh MacDonald, Paul N. Hilfinger, Luigi Semenzato, Proceedings of the SCM-8 Symposium on System Configuration Management, July 1998

    This paper does not describe Xdelta. Another one does on the PRCS web site.

  • Wayback: A User-level Versioning File System for Linux [cornell04:wayback]
    B. Cornell, P. Dinda, F. Bustamante (Department of Computer Science, Northwestern University, USA), Proceedings of the USENIX Annual Technical Conference, FREENIX Track, 2004

    Although this paper was awarded best paper at USENIX 2004, I don't find it so interesting, especially in the light of other papers published years earlier quinlan02:venti. Anyway, the paper describes a relatively naive implementation of a comprehensive versioning filesystem (as opposed to Ext3Cow peterson03:ext3cow which is checkpoint-based) for GNU/Linux as a user-space filesystem based on FUSE fuse:web. Wayback can work on top of any filesystem. What it does is that it logs every write (), truncate (), etc., calls in a magic log file of the underlying filesystem ("magic" in the sense that Wayback hides it to the user). When a write () is performed, Wayback fetches the file portion that is to be overwritten and stores it in the log file. This is not very elegant, and probably not too efficient either. Performance comparisons include versioning of binary files by Wayback versus RCS which is in my opinion irrelevant since RCS was not designed with binary files in mind.

  • Detecting Changes in XML Documents [cobena02:xydiff]
    Gr?gory Cobena, Serge Abiteboul, Am?lie Marian (INRIA, Rocquencourt, France; Columbia University, NY, USA), Proceedings of the 18th International Conference on Data Engineering, February 2002
  • bsdiff: binary diff/patch utility [percival05:bsdiff]
    Colin Percival, 2005
  • Atomic Transactions [lampson91:atomic-transactions]
    Butler W. Lampson, Distributed Systems---Architecture and Implementation, An Advanced Course, 1981

    One of the first documents dealing with the implementation of atomic transactions.

  • Ext3cow: The Design, Implementation, and Analysis of Metadata for a Time-Shifting File System [peterson03:ext3cow]
    Z.N.J. Peterson, R.C. Burns (Hopkins Storage Systems Lab, Department of Computer Science, Johns Hopkins University, USA), 2003

    Ext3Cow is a checkpointing versioning file system based on ext3. The paper focuses on performance and space-efficiency and doesn't take into account storage reclamations issues highlighted in the EFS paper santry99:deciding. Ext3Cow is not an exhaustive versioning filesystem, unlike EFS: instead, users must execute a snapshot utility (which in turns invokes a snapshot ioctl) whenever a new version of a file should be created. The new version is actually created the next file data are written to the file, in a copy-on-write fashion. In order to access a file's history, Ext3Cow only has a kernel-level mechanism which consists in interpreting paths containing the @ symbol followed by an Epoch date, as in EFS. Unlike EFS, it does not provide a new set of syscalls for accessing files' histories, which I consider unfortunate. Instead of using an inode log stored in a single block like EFS does, Ext3Cow uses an inode chain, i.e. each inode has a pointer to the previous version's inode. One advantage over the inode log used in EFS is that it removes a level of indirection (and it removes the adaptive use of inodes or inode logs in EFS). However, (i) it makes retrieval of older versions O(n) (where n is the number of versions to traverse), potentially slower than EFS (note that EFS chains inode logs anyway) and (ii) it makes it impossible to ever add a branching facility (e.g. modifying an old version of a file). In order to preserve files' inode numbers over time, the top-level inode is copied (the copy becomes the top-level inode of the previous version) and then modified in place. In order to improve file data locality, it might have been wiser to use a newly allocated inode for the new version, not the old one; however, the inode numbers of the two inodes would need to be exchanged which is probably not efficient and might introduce consistency problems. When an inode is duplicated, none of the blocks it points to is duplicated; instead, each inode embeds a bitmap that indicates which blocks are marked as copy-on-write. In ext3, directories are implemented using an inode pointing to blocks that map file names to inode numbers. Ext3Cow simply adds a birth epoch and a death epoch to each directory entry. Final remarks: ext3 inodes can now be more 128 bytes long while still retaining backwards compatibility, and ext3 supports extended attributes. These two features should make it possible to implement a less intrusive version of ext3cow.

  • The EDelta Binary Diff Algorithm [hansen05:edelta]
    Jacob Gorm Hansen (DIKU, Denmark), 2005

    A diff algorithm (and implementation) that focuses executable files.

(made with skribilo)