Last updated: $Date: 2001/07/02 21:46:52 $ Two things that need to happen in the filesystem: a) We need to operate on file contents without holding the entire contents in RAM. Berkeley DB gives us tools to operate on regions within a value, we just need to use them. b) We need to do reverse-delta storage in the filesystem (with checksums). Some thoughts on them: a) Operate on portions of files efficiently. ============================================ [still pondering this section] We should take advantage of Berkeley DB's partial record stuff, all the way up to the top of the svn fs interfaces. - dag_node_t gets two new fields: contents_offset and contents_len. They apply to the node's cache of the contents, not the header or proplist. - svn_fs__get_node_rev_contents() takes offset and len arguments, fetches only that data. The dag_node_t will remember the offset and len. - svn_fs__put_node_rev_contents() takes offset and len args as well. - change set_node_revision() accordingly. - ... todo thinking here ... So now, whenever you read or write a node revision, you are operating on a range. There will be some way to say "I mean the whole thing", of course, so it won't be necessary to know the size in advance. Thought: possibly we should stop storing data in the dag_node_t itself, and just return the data in a void pointer passed to svn_fs__get_node_rev_contents(). Still pondering. b) Reverse-delta storage. ========================= The naive way to recover an old text is: retrieve_node_rev (N) { grab_node_revision (&N); if (is_fulltext (N)) return N; else if (is_shared (N)) return retrieve_node_rev (get_sharee (N)); else if (is_svndiff (N)) return svnpatch (get_svndiff (N), retrieve_node_rev (get_base (N))) } (Loose pseudo-code, obviously, and the recursion could be a loop, but you get the idea.) The trouble with this is that it constructs and patches each intermediate revision. That'll probably be i/o bound, and anyway much of the intermediate material may not end up in the final target, in which case reconstructing it was a waste of time. What we really want is a way to compose a bunch of svndiffs, and then apply that composition to the current head, to give us the older revision in one step (well, one application anyway). Both the composition and the final application need to happen in a streamy or windowed fashion -- we shouldn't have to hold the entire diff in memory, nor the entire source, nor the target. Here's a way to do this: An svndiff is a series of instructions that are followed to reconstruct the target. There are three possible instructions: a) Insert X bytes of new text into the TARGET, and I'm giving you those bytes right here. b) Copy N bytes, starting from offset F in the SOURCE, into the TARGET. c) Copy N bytes, starting from offset F in the TARGET, into the TARGET. (Note that (c) can actually run past the current end of the target, as long by the time you get there, the target is longer.) To compose two svndiffs... ...and I hate to tantalize you, but I'm late and have to run now, so I'll try to finish this tomorrow... crimminy... The quick summary is, we build a new svndiff (the composition of all the intermediates), and as it gets too large, we windowify as we go and put each window temporarily in the database; this makes the composition as a whole less efficient, but means that at any given time we don't have to have the whole thing in memory. The arithmetic for offset-adjustment is fairly straightforward even when one has to offload windows, I believe. It's nice that the source is already in the db and we get offset+length style operations from Berkeley naturally anyway. Branko or anyone, feel free to continue this recipe and see if you can take it somewhere before I get in tomorrow morning... -kff ------------------------------------------------------------------------ Notes from JimB about optimizing the in-repository delta generation to make deltas that can be composed more quickly: I talked about this with Karl on the phone, and gave pretty bad explanations of my thinking; I'll try to do better today. This will also provide some background for other readers. I'm told that RCS reconstructs older file revisions by walking the list of diffs, ignoring the actual text, and simply recording the line numbers and sizes of the substitutions. Then, it can run over that data and do arithmetic to construct a single `composed' diff against the youngest revision would reconstructs the older revision. Then, you apply that composed diff to get the revision you wanted. For example, if your fulltext is: rev 3: abcdefghijklmnopqrst and your deltas are: rev 2: replace 3--6 with "howdy" (yielding abchowdyghijklmnopqrst) rev 1: replace 6--8 with " are you" (yielding abchow are youghijklmnopqrst) then the RCS algorithm would gather this info: rev 2: replace 3--6 with 5 chars (call them X) rev 1: replace 6--8 with 8 chars (call them Y) Now, without looking at any of the text, it can compose the two deltas to get the following delta, yielding rev 1: replace 3--6 with range 0--3 from X replace 6--6 with range 0--8 from Y (i.e. insert Y at 6) If we then apply this `composed' delta to the original text, we get: abchow are youghijklmnopqrst The point of all this is that you don't need to mess around with actual text until the very end. Until that point, the amount of work depends on the amount of change, not on the amount of text involved. And when you do get around to actually assembling text, the amount of work depends on the size of the output file --- because you're only touching each piece of text once --- and only weakly on the amount of change. Our current svndiff format frustrates this somewhat by compressing the new text, as well as pulling in pieces of the original. The compression process produces a lot of delta ops that deal with small pieces of text. (Or at least, I expect it does...) So even if the change is something simple --- replacing a single block of text in the middle of the file, say --- you end up with an svndiff with a lot of ops, mostly concerned with building the replacement text from pieces of itself. This is great, except that having lots of small ops increases the amount of work the delta composition phase needs to do. In fact, if the ops usually deal with really small pieces of text --- a few dozen bytes or so --- I expect it'd be faster to just throw the actual text around. Memcpy is pretty optimized on real systems; you could copy a lot of bytes in the time it would take to do funky intersections and adjustments on a list of ops talking about those bytes, so those ops had better refer to large blocks of bytes. I'm not sure what to do with that. It almost seems like we want the text delta computation algorithm to optimize deltas for network transmission and deltas for storage differently. ------------------------------------------------------------------------ Notes from Brane: Delta composition Despite JimB's concerns, it turns out that delta composition is straight-forward. The basic idea is that combining two deltas is equivalent to applying the second delta to a representation of the first delta's result. Bear with me while I shamelessly abuse what little I remember about linear algebra. Given two deltas, A and B, and the source stream S, we want to construct a composed delta, AB, that converts S to the target stream T. Let's borrow notation from linear algebra and write this transformation like this: T = AB(S) Abusing algebra some more, I'll assume that a delta behaves like any other linear transformatsion; therefore, AB(S) = B(A(S)) and since I'm not about to develop any rigorous proofs here, I'll just say that it follows from the above that T = B(S'), where S' = A(S) A small note here: Every delta is actually an n-tuple of delta opserations, represented by what I'll call the delta operators [n] (for new data), [s] (for source copies) and [t] (for target copies). [s] and [t] create bits of the target stream by operating on contiguous parts of the source and (existing) target stream, respectively; while [n] does the same by operating on raw data. Now, what we actually want to do is derive some form of AB (which, by the way, does not have a unique representation, sice we're not trying to find the optimal ("normalized") transform) that doesn't in any way rely on the value of S'. We do that by building a representation of S' that relies only on S, and any new data introduced by the [n] operators in A. That's possible because any [t] ops in A merely copy parts of S' that have been previously defined by [s] and [n] ops. Transforming A by (recursively) replacing all [t] ops with the equivalent [s] and [n] ops gives us exactly such a representation, which I'll call A'. [*] Building AB from B and A' is trivial: traversing the list of delta ops in B, copy all [n] and [t] ops into the result; for [s] ops, copy the range of ops from A' that define the appropriate range in S'. For some of the copies, the first or last op from the range in A' will have to be split, and the first op in the copy range can sometimes be merged with the previous op in AB. Of course, stopping here could give a very sub-optimal AB, because it could contain many duplicate copies of the same op ranges from A'. We fix this by doing exactly the opposite transformation than A->A': by transforming [s] ops from B into [t] ops. We do this by recording the source and target of each copy from A' to AB and, whenever the [s] from B describes a range in T that was already defined, converting that into a [t] instead [**]. Unlike the A->A' transform, we can't remove all copies from A' to AB (we can only do that when AB doesn't refer to S at all), but we can significantly reduce the number of such copies. The resulting AB will usually not be the optimal delta from S to T, because we will never actually look at S while constructing AB. Summarizing the above, we get the following delta composition algorithm: ;; X is the set of byte ranges in T defined by copies from S' ;; Y is the current offset in T, defined by the ops in AB foreach OP in B: if (OP = [t]) or (OP = [n]): copy OP to AB else R = (set of ops from A that define S'[OP.offset, OP.length]) [**] using X, find the optimal set O of [t] ops to replace part of R foreach OP' in R: if OP' is in (R - O): if (OP' = [t]): [*] replace OP' with equivalent [s] and [n] ops copy OP' to AB else [**] copy OP's equivalent in O to AB insert S'[OP.offset, OP.length]->[Y, OP.length] into X This algorithm ignores details such as op splitting and merging, ensuring every op from O gets copied exactly once, helper indexes, etc..., but those are implementation details. ------------------------------------------------------------------------ Notes from Brane: Delta storage O.K., now that delta composition is out of the way, let's talk a bit about storing and retrieving deltified text from the filesystem. I'll just jot down a few thoughts about how this could be done, assuming one of two possible models of storage management in the filesystem: a) all data store and retreive operations are synchronous; or, b) deltification can run in the background. 1) Storing new data New data arrives either as fulltext (from add) or as a delta from an existing version (copy, modify). a) if the new data is a delta, convert it to fulltext (possibly combining several existing deltas in the process). Store the fulltext in the tip, and replace the previous tip (which, by induction, contains fulltext) with a delta from the current tip. b) store the fulltext or delta in the tip and mark it for async modification. Do a) in the background. 2) Retreiving old data a) If the data is a delta, follow the delte references (combining the deltas) until a fulltext is found; apply the combined delta to get the required fulltext. If the combined delta reduces to a no-op (the two fulltexts are the same), store the fulltext in the younger of the two nodes and replace the older node's data with a "same" note. b) Same as para 1 of a), then mark the node for async modification. In the background, find the diff between the two fulltexts. If they're equal, do para 2 of a). Otherwise, if the diff is smaller than the current diff in the node, replace the current representation. ("Smaller" could be construed as "more optimal" -- it would make sense to take into account the number of delta combinations that could be skipped by replacing the current representation when comparing sizes.)