The good folks who created the SVN version control system use a structure they refer to as "skip deltas" to store the revision history of files internally. A revision is stored as a delta against an earlier revision. However, revision N is not necessarily stored as a delta against revision N-1, like this:

0 <- 1 <- 2 <- 3 <- 4 <- 5 <- 6 <- 7 <- 8 <- 9

Instead, revision N is stored as a delta against N-f(N), where f(N) is the greatest power of two that divides N:

0 <- 1    2 <- 3    4 <- 5    6 <- 7
0 <------ 2         4 <------ 6
0 <---------------- 4
0 <------------------------------------ 8 <- 9

(Superficially it looks like a skip list but really it's not that similar - for instance, skip deltas are not interested in supporting insertion in the middle of the list.) You can read more about it here.

My question is: Do other systems use skip deltas? Were skip deltas known/used/published before SVN, or did the creators of SVN invent it themselves?

  • 1
    Might find this cached note from MIT interesting as pertains to some other VCS's. Author didn't know of other implementations. Saw a note here regarding Bazaar, but was having trouble finding out the current status. My gut says this probably did start with SVN as a variation on an existing theme. – J Trana Jul 10 '14 at 5:57

Starting from your link Skip-Deltas in Subversion I read through this note Notes on keeping version histories of files and there it's written:

The author does not know of papers or other references describing the technique [skip deltas]. .. This document was written by Greg Hudson on 2002-06-24. It was last updated on 2002-10-03.

So my guess is that skip delta were invented by the SVN team somewhere before 2002. One could contact this Greg Hudson in case he knows more.

Or maybe they used a versioning system (CVS) to develop SVN and there are still commit logs?

I also searched for delta compression and didn't find any earlier reference. I think it would make sense, because this skip delta technique is specialized on fast retrieval and maybe before SVN nobody needed fast retrieval of delta compressed data. Delta compression itself is in the literature since 70s/80s. One of the earliest papers is Experiences with delta compression of data produced by DIII.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.