notes/skip-deltas

   1 Skip-Deltas in Subversion
   2 =========================
   3
   4 To keep repositories at a manageable size, essentially all version
   5 control systems use some kind of relative compression technique such
   6 that two similar versions of the same file don't take up much more
   7 space than just one version of that file.  The two most common
   8 techniques are the SCCS "weave", which represents all revisions of a
   9 file as a single data stream with the moral equivalent of #ifdefs, and
  10 the technique of storing deltas (differences) between related
  11 revisions of files (see
  12 http://web.mit.edu/ghudson/thoughts/file-versioning for details).
  13 Subversion uses deltas.
  14
  15 Subversion uses a technique called "skip-deltas" to ensure that only a
  16 reasonable number of deltas need to be composed in order to retrieve
  17 any revisions of a file.  The concept of skip-deltas is inspired by
  18 the concept of skip-lists, but they aren't all that similar.
  19
  20 For the purposes of this document, we will pretend that revisions of a
  21 file are numbered starting from 0.  In reality, this number
  22 corresponds to the "change count" field of a node-revision in each
  23 filesystem back end.
  24
  25 Skip-Deltas in the FSFS Back End
  26 ================================
  27
  28 In the FSFS back end, each revision of a file is represented as a
  29 delta against an older revision of the file.  The first revision is
  30 represented as a delta against the empty stream (i.e. it is
  31 self-compressed).  To reconstruct a revision of a file, the filesystem
  32 code determines the chain of deltas leading back to revision 0,
  33 composes them all together using the delta combiner, and applies the
  34 resulting super-delta to the empty stream in order to reconstruct the
  35 file contents.
  36
  37 The most obvious strategy would be to choose revision N-1 as the delta
  38 base for revision N.  But even with the delta combiner, it would
  39 become very slow to retrieve revision 1000 of a file if we had to
  40 piece together 1000 deltas.  So, to choose the delta base for revision
  41 N, we write out N in binary and flip the rightmost bit whose value is
  42 1.  For instance, if we are storing 54, we write it out in binary as
  43 110110, flip the last '1' bit to get 110100, and thus pick revision 52
  44 of the file as the delta base.  A file with ten versions (numbered
  45 0-9) would have those versions represented as follows:
  46
  47   0 <- 1    2 <- 3    4 <- 5    6 <- 7
  48   0 <------ 2         4 <------ 6
  49   0 <---------------- 4
  50   0 <------------------------------------ 8 <- 9
  51
  52 where "0 <- 1" means that the delta base for revision 1 is revision 0.
  53
  54 Because we flip the rightmost '1' bit each time we pick a delta base,
  55 at most lg(N) deltas are necessary to reconstruct revision N of a
  56 file.
  57
  58 Skip-deltas in the BDB Back End
  59 ===============================
  60
  61 In the BDB back end, each revision of a file is represented as a delta
  62 against a newer revision of the file--the opposite of FSFS.  The
  63 newest version of a file is stored in plain text.  Whereas in FSFS, we
  64 add a new version of a file simply by picking a delta base and writing
  65 out a delta, in BDB the process is more complicated: we write out the
  66 new version of the file in plain text; then, after the commit is
  67 confirmed, we go back and "redeltify" one or more older versions of
  68 the file against the new one.
  69
  70 The goal of the redeltification process is to produce the reverse of
  71 the FSFS diagram:
  72
  73   0 ------------------------------------> 8 -> 9
  74                       4 ----------------> 8
  75             2 ------> 4         6 ------> 8
  76        1 -> 2    3 -> 4    5 -> 6    7 -> 8
  77
  78 To accomplish this, we write out the number in binary, count the
  79 number of trailing zeros, and redeltify that number of ancestor
  80 revisions plus 1.  For instance, when we see revision 8, we write it
  81 out as "1000", note that there are three trailing 0s, and resolve to
  82 redeltify four ancestor revisions: the revisions one back, two back,
  83 four back, and eight back.
  84
  85 As it turns out, the above diagram is a fiction.  To reduce overhead,
  86 the BDB back end makes three compromises to the skip-delta scheme:
  87
  88   * When storing file revisions 0-31, only the immediate predecessor
  89     is redeltified.
  90
  91   * We don't redeltify the ancestor revision which is two back from
  92     the one we are storing.
  93
  94   * We never redeltify revision 0 of a file.
  95
  96 Despite these compromises, the asymptotic behavior of the BDB
  97 skip-delta scheme is the same as the simpler FSFS one: O(lg(N)) deltas
  98 are necessary to reconstruct any revision of a file which has had N
  99 revisions.
 100
 101 Skip-Deltas and Branches
 102 ========================
 103
 104 If a file's history diverges because it is copied and the modified on
 105 both branches, the behavior is as follows:
 106
 107   * In FSFS, we choose delta bases just as we would if each branch
 108     were an isolated linear path leading back to revision 0.  For
 109     instance, if a file has six revisions (0-5), then branches into
 110     revisions 6-7 and revisions 6'-8', they would look like:
 111
 112     0 <- 1    2 <- 3    4 <- 5    6 <- 7
 113     0 <------ 2         4 <------ 6
 114                                   6' <- 7'
 115     0 <-------------------------------------- 8'
 116
 117   * In BDB, we redeltify ancestor revisions just as we would if each
 118     branch were an isolated linear path leading back to revision 0.
 119     The result depends on the order of commits.  If a file has four
 120     revisions (0-3), then branches into revisions 4 and 4', then if 4
 121     was committed first and 4' was committed second, the result would
 122     look like:
 123
 124                             4
 125     0 --------------------> 4'
 126                 2 --------> 4'
 127           1 --> 2     3 --> 4'
 128
 129     but if instead, 4 was committed second, the result would look
 130     like:
 131
 132                             4'
 133     0 --------------------> 4
 134                 2 --------> 4
 135           1 --> 2     3 --> 4
 136
 137     Although this order dependency may be confusing to think about,
 138     it causes no complexity in the code, and the O(lg(N)) asymptotic
 139     behavior is clearly preserved.
 140
 141 Note that in the BDB back end, a branched file has a separate
 142 plain-text representation for each branch head, while in the FSFS back
 143 end, that is not the case.
 144
 145 Costs of Skip-Deltas
 146 ====================
 147
 148 In most workloads, the delta for a file revision becomes larger if the
 149 delta base is farther away--in terms of the diagrams, longer arrows
 150 take up more space.  In the worst case, where all changes to the file
 151 are orthogonal to each other, a delta across N file revisions may be N
 152 times as expensive as a delta across one revision.
 153
 154 In either back end, the average number of revisions crossed by a delta
 155 arrow is O(lg(N)), if the file has had N revisions.  So we may assume
 156 that in the worst case, skip-deltas incur an O(lg(N)) space penalty
 157 while providing an O(N/lg(N)) time benefit.  The practical space
 158 penalty appears to be substantially less than O(lg(N)), because many
 159 files have short histories and many changes are not orthogonal to each
 160 other.