[Sugar-devel] Tech note on versioning

Benjamin M. Schwartz bmschwar at fas.harvard.edu
Tue Apr 21 14:51:09 EDT 2009


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Thanks to Sascha Silbe, versioning is actually going to happen! Woot!

One of the things that's often talked about with versioning is
differential compression.  The purpose of this e-mail is to note a
particular technology for differential compression: VCDIFF.

VCDIFF is an IETF standard for differential compression.[1]  Its most
famous implementation is Xdelta, which is GPL.[2]  Google has also
released a VCDIFF implementation, under Apache 2.0.[3]

Most "diff" algorithms that we're familiar with as developers work on a
line-by-line basis.  They are designed for source code, and their output
is human readable.  Their purpose is principally to facilitate
collaborative development.  Revision control systems like git typically
use these algorithms to maintain version history.

VCDIFF is different.  Its purpose is to store deltas as compactly as
possible, and to work on arbitrary binary data.  Its output is not
human-readable.  It should also work well on plain text.

I am particularly impressed with VCDIFF because of the following
capability in Xdelta:
"""
The new merge command allows you to combine a sequence of deltas, to
produce a single output that represents the net effect of the sequence.
The command is reasonably efficient because it computes the result
directly, without constructing any intermediate copies (and without access
to the first-of-chain source).
"""
If versions are stored as deltas against the current head (reverse
deltas), then removing a version is as simple as merging two deltas, and
should be quite fast.

I do not think that differential version storage is coming soon, but I
think when it does, we should give great consideration to Xdelta and VCDIFF.

- --Ben

[1] http://www.ietf.org/rfc/rfc3284.txt
[2] http://xdelta.org/
[3] http://code.google.com/p/open-vcdiff/
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.10 (GNU/Linux)

iEYEARECAAYFAknuFZ0ACgkQUJT6e6HFtqRtJwCgg3eP3//x0wsI5dDa4hbFV381
45cAn1/1g/iHvevU0gTV2xIwTUSNC7Ai
=JhKZ
-----END PGP SIGNATURE-----


More information about the Sugar-devel mailing list